Mobile Assisted Localization in Wireless Sensor Networks N B Priyantha H Balakrishnan E D Demaine S Teller MIT Computer Science Presenters Puneet Gupta Sol Lederer Case 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 difficult Overview 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 discarded Theorem 1 A graph is globally rigid if it is formed by starting from a clique of 4 noncoplanar 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 n1 Case 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 equations Case 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 needed Case of 3 nodes Solution Restriction All mobile positions lie in a common plane mobile locations k 3 additional coplanarity constraints k 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 2 Case 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 1 Case 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 coplanar MAL 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 node AFL Anchor free localization Elect five nodes as shown Get crude coordinates based on hop count to anchors AFL Use non linear optimization algorithm to minimize sum squared energy E Coordinate assignments satisfy all 1hop node distances when E 0 Graph from running AFL using RF connectivity information Graph obtained by MAL Performance Layout of nodes in test scenario Estimate error Critique Pros Innovative stategy Cons In a cumbersome terrain e g forest it may not be feasible to deploy a roving node The End
View Full Document
Unlocking...