Mobile Assisted Localization in Wireless Sensor Networks N.B. Priyantha, H. Balakrishnan, E.D. Demaine, S. Teller MIT Computer ScienceCase for Mobile Assisted LocalizationOverview of schemeTheorem 1MAL: Distance MeasurementCase of 2 nodes solvedCase of 3 nodesCase of 3 nodes  SolutionCase of 4 or MoreCase of 4 or more  SolutionMAL: Movement StrategyAFL: Anchor-free localizationAFLSlide 14PerformanceEstimate errorCritiqueThe EndMobile Assisted Localization in Wireless Sensor NetworksN.B. Priyantha, H. Balakrishnan, E.D. Demaine, S. TellerMIT Computer SciencePresenters:Puneet GuptaSol LedererCase for Mobile Assisted LocalizationObstructions, especially in indoor environmentsSparse node deploymentsGeometric dilution of precision (GDOP)Hence, finding 4 reference points for each node for localization is difficultOverview of schemeInitially no nodes know their locationMobile node finds cluster of nearby nodesExplores “visibility region” and measures distance# of measurements required is linear in the # of nodesVirtual nodes are discardedTheorem 1A graph is globally rigid if it is formed by starting from a clique of 4 non-coplanar nodes and repeatedly adding a node connected to at least 4 nodes.MAL: Distance MeasurementFirst case: Two nodes, n0 and n1 , single unknown ||n0 - n1||Adding mobile node, m, introduces 3 unknowns (mx, my, mz), making problem more difficultNecessary condition: # deg of freedom (unknowns – knowns) ≤ 0.Solution: Use three mobile locations along the same line in a plane containing n0 and n1Case of 2 nodes solved6 constraints from measurements of ||ni – mj|| for I = 0,1 and j = 0,1,2Extra constraint obtained from colinearity of mobile points unknowns – knowns = 0Solve system of polynomial equationsCase of 3 nodesThree nodes, n0 n1 n2, three unknowns, ||n0 - n1|| ||n1 - n2|| ||n0 - n2||Each mobile position gives #unknowns (mx, my, mz) = 3 #constraints (||m – ni||, i = 0,1,2) = 3Three additional constraints neededCase of 3 nodes  SolutionRestriction: All mobile positions lie in a common planek mobile locations  k-3 additional co-planarity constraintsSolution: k = 6, geometry of n0, n1, n2 above the plane containing 6 coplanar points m0, m1, m2, m3, m4, m5 no three of which are collinear, determined by the distances ||mi - nj||, i = 0…5 & j = 0...2Case of 4 or MoreNumber of nodes = j ≥ 4Initially: Number of unknowns = (3j – 5)3 coordinates per nodeMinus 3 deg of translational motionMinus 2 deg of rotational motionEach mobile node adds (j – 3) deg of freedom (j distances – 3 coordinates of mobile position)j – 3 >= 1Case of 4 or more  SolutionRequire at least (3j – 5)/(j – 3) mobile positionsE.g. for j = 4, required mobile positions to uniquely determine the geometry = 7But, no 4 of the 11 nodes (4 + 7) may be coplanarMAL: Movement StrategyInitialize: Find 4 nodes that can all be seen from a common locationMove the mobile to 7 nearby locations & measure distancesCompute pair-wise distancesLoop: Pick a localized stationary node (not yet considered by this loop)Move mobile in perimeter of this node, searching for positions to hear a non-localized nodeLocalize this nodeAFL: Anchor-free localizationElect five nodes as shownGet crude coordinates based on hop count to anchorsAFLUse non-linear optimization algorithm to minimize sum-squared energy ECoordinate assignments satisfy all 1-hop node distances when E = 0Graph from running AFL—using RF connectivity informationGraph obtained by MALPerformanceLayout of nodes in test scenarioEstimate errorCritiquePros:Innovative stategyCons:In a cumbersome terrain (e.g. forest) it may not be feasible to deploy a roving node.The