قالب پایان نامه

صفحه 1:
Fine-Grained Localization in Sensor and Ad-Hoc Networks Ph.D. Dissertation David Goldenberg Dissertation Advisor: Y. Richard Yang Committee Members: Jim Aspnes, A. Stephen Morse, Avi Silberschatz, Nitin Vaidya (UIUC) 

صفحه 2:
Overview ™ This dissertation provides a theoretical basis for the localization problem, demonstrating conditions for its so/vability and defining its computational complexity. " We apply our fundamental results on localization to identify conditions under which the problem is efficiently solvable and to develop /ocalization algorithms for a broader class of networks than previous approaches could localize. 

صفحه 3:
Collaborators (2003- = Brian D.O. ( scrson (Australia National University and NICTA) = James Aspnes = P.N. Belhumeur (Columbia University) = Pascal Bihler = Ming Cao = Tolga Eren = Jia Fang ™ Arvind Krishnamurthy ® Jie (Archer) Lin ™ Wesley Maness 8 A. Stephen Morse ™ Brad Rosen ™ Andreas Savvides = Walter Whiteley (York University) = Y. Richard Yang = Anthony Young 

صفحه 4:
Outline ™ Introduction to Localization ™ Conditions for Unique Localization = Computational Complexity of Localization " Localization in Sparse Networks 

صفحه 5:
۲ ۳۲۲۲۲۲۲۲۲۲ ‏اس‎ are Locations rtant? 7 Im 5 00 rt networks are an important emerging technology Small, low-cost, low-power, multi-functional sensors will soon be a reality. Accurate locations of individual sensors are useful for many applications = “Sensing data without knowing the sensor location is meaningless.” [IEEE Computer, Vol. 33, 2000] = New applications enabled by availability of sensor locations. = Location-aware computing Resource selection (server, printer, etc.). Location aware information services (web-search, advertisement, etc.). ™ Sensor network applications | Inventory management, intruder detection, traffic monitoring, emergency crew coordination, air/water quality monitoring, military/intelligence apps. 

صفحه 6:
۰ ‏ال‎ 6 Example: Great Duck Island Sensor Network = Monitoring breeding of Leach’s Storm Petrels without human presence. — 15 minute human visit leads to 20% offspring mortality. ™ Sensors need to be small to avoid disrupting bird behavior. 

صفحه 7:
Sh Great Duck Island Deployment Goals = Occupancy pattern of nests? "= Environmental changes around the nests over time? = Environmental variation across Drukepberew | . gs nests? "Correlation with breeding 0 success? 9 9 t i i 9 ° ™ Light, temperature, infrared, and 8۰ humidity sensors installed. ‏هو و‎ « Infrared sensors detect presence 5 of birds in nests. ° ™ Sensor locations critical to interpreting 9 ‏مق‎ ‎data. eng ‏كن‎ PY "Locations determined by manual configuration, but this will not be possibte inthe generat case: 

صفحه 8:
ple ZebraNet Sensor 7 a Networ] track animals to study: Interactions between individuals. Interactions between species. Impact of human development. = Current tracking technology: VHF collar transmitters = Wishlist: 24/7 position, data, and interaction logs. Wireless connectivity for mobility Data storage to tolerate an intermittent base station. = ZebraNet: Mobile sensor net with intermittent base station. = Records position using GPS every 3 minutes. Records Sun/shade info. Detailed movement information (speed, movement signature) 3 minutes each hour. Future: head up/head down, body temperature, heart rate, camera. 9 Goal. full ecosystem monitoring (zebras, hyenas, ions: 

صفحه 9:
ee eee 9 a Military Application Intelligence gathering (troop movements, events of interest) = Detection and localization of chemical, biological, radiological, nuclear, and explosive materials. "Sniper localization. Signal jamming over a specific area ™ Visions for sensor network deployment: Dropped in large numbers from UAV. Mortar-Launched 

صفحه 10:
1 10 Why is Localization a Non-Trivial Problem? = Manual configuration Unscalable and sometimes impossible. = Why not use GPS to localize? Hardware requirements vs. small sensors. Obstructions to GPS satellites common. ™ GPS satellites not necessarily overhead. ™ Doesn’t work indoors or underground. GPS jammed by sophisticated adversaries. GPS accuracy (10-20 feet) poor for short range sensors. 

صفحه 11:
5 8 11 Fine-Crained Localization (Savvides, 200 1) Network of n nodes, m of which have known location, existing in space at locations: {X,...XpiXmsar-+ Xp} Set of some pair-wise inter-node distance measurements. = Usually between proximal nodes (iff d < rin unit disk networks). ™ Abstraction - Given: Graph Gy, {X,,....X,,}, and 6, the edge weight function. | Find: Realization of the graph. لكوتي @eacons: nodes with known position @gular nodes: nodes with unknown posito| 

صفحه 12:
Ranging Systems = TDOoA - Time Difference of Arrival “ Uses ultrasound and radio : signals to determine distance. 3 9 / = Range of meters, cm accuracy. © ™ Possible to increase sensing iT wicket mote range by increasing transmission power. UCLA medusa mote 2 (2002), Yale ENALAB XYZ Motes UCLA medusa mote (2001) 

صفحه 13:
13 اتکی Our Contributions Graph-theoretic conditions for the unique solvability of the localization problem in the plane. Proof that the problem is NP-complete even for the idealized case of unit-disk networks. Constructive characterization of classes of uniquely locallzable and easily localizable networks for the plane and 3D. A localization algorithm that localizes a wider class of networks than was possible with existing approaches. In-depth study of the /ocalizability properties of random networks: ~ New adaptive localizability-optimizing deployment strategies. — Impact of non-uniquely localizable nodes on network performance. 

صفحه 14:
Outline ™ Introduction to Localization ™ Conditions for Unique Localization = Computational Complexity of Localization " Localization in Sparse Networks 

صفحه 15:
15 7۳۳۳۳22 Unique Localizability = Network is uniquely localizable if there is exactly one set of points {X,,,,,-...X,} Consistent with G,,, {X,,...X,} and 6:E to R. ™ Can we determine localizability by graph properties alone? (as opposed to the properties of 6). = In the plane, yes (more or less). Properties of the graph determine solvability in the generic case. Probability 1 for randomly generated node locations. 

صفحه 16:
“pegererate cases Fool ۳ Abstraction 

صفحه 17:
35 5 Continuous Non-Uniqueness wie IY ‏هم‎ ™ Continuous non-uniqueness: “ Can move points from one configuration to another while respecting constraints. — Excess degrees of freedom present in configuration. “ A formation is RIGID if it cannot be continuously deformed. 

صفحه 18:
18 ا سس اين Condition for Rigidity = Purely combinatorial characterization of generic rigidity in the plane. ™ 2n-3 edges necessary for rigidity, and: ‏موی و مورا‎ سود من لب و ول ‎tk CeO‏ 6 مب 6 ول 69-6 مد سس عم ۳ اوه ‎Porn poly Po‏ "08 م ‎oP vertices‏ بای سب او مان * اهب وق اه بو و سوا ای و مخت وی لو نوه ادا موه و سا له ج مورا ‎chet right‏ تست ‎ecker but oot‏ اه ‎eckes‏ مس تا ‎ ‎ 

صفحه 19:
0 Non-Uniqueness in Rigid Graphs Flip Ambiguities: J ۳2 & \ 2 configs Discontinuous Flex Ambiguities: 

صفحه 20:
20 © wast be recherkray right: الغ با بسح ظ) @ ast be O-cowerted. ۱ ‏و اسجه‎ rigid poo rewovd oP cap siete eke. A graph has a unique realization in the plane iff it is redundantly rigid and 3-connected (globally rigid). Hendrickson, ‘94 

صفحه 21:
tte 21 “Is The Network Uniquely Localizable? «۶ Problem: By looking only at the physical connectivity structure, we would neglect our 2 priori knowledge of beacon positions. ™ Solution: The distances between beacons are implicitly known! By adding all edges between beacons to Gy, we get the rounded Graph of the network, whose properties determine network localizability. Theorem: A network is generically uniquely localizable iff its grounded graph is globally rigid and it contains at least three beacons. " By augmenting graph structure in this way, we fully express all available constraint information in a grap 26 oN 7۹ 

صفحه 22:
xamples of GR graphs - Constructions subgraph that is minimally globally rigid. "= Every minimally globally rigid graph can be constructed inductively starting from K, by a series of extensions (Berg-Jordan ‘01): New node wand edges uw and vw replace edge uv. Edge wx added for some node x distinct from uw, ۷۰ = Minimal globally rigid graphs have 2 Light edges are those subdivided by the extension operation. 

صفحه 23:
۰ ‏ال‎ 23 Examples of Global Rigidity ‎ree.‏ و وی لاو ابا ‎ ‎ 

صفحه 24:
۰ 0( امن مه ۰۰ هو ما[ . references. "= Minimal trilateration graphs formed by trilateration extension: New node wand edges uw, vw, xw added, for u, v, x distinct. = Minimal trilateration graphs are globally rigid. "= Minimal trilateration graphs have 3n-6 edges. Light edges are those removed in extension for minimally GR graph but not in trilateration 

صفحه 25:
a 25 Trilateration Graphs " Atrilateration graph G is one with an trilaterative ordering: an ordering of the vertices 1,...,0 such that the complete ‏و‎ on the initial 3 vertices is in G and from ely vertex j> 3, there are at least 3 edges to vertices earlier in the sequence. = Trilateration graphs are globally rigid. Hand-made trilateration - avg degree 6. Trilateration graph from mobile network - avg degree 9. 

صفحه 26:
26 اتکی ‎“Tripled” Connected Graphs‏ ‎are Trilateration Graphs‏ = Theorem: Let G = (V,E) be a connected graph. Let G3 = (V,EU Eu E3) be the graph formed from G by adding an edge between any two vertices connected by paths of 2 or 3 edges in E. Then G3is a trilateration graph. Crcxople where 6 ‏عدم و‎ 

صفحه 27:
"۳9۲۳۳576۳6۲556۲5 7 are Globally Rigid in 2D Let G be a 2-connected graph. One gets G by doubling sensing radius or measuring angles between adjacent edges. than a minimally GR =| Lgraph, so they are \| “globally rigid. a Then G?is globally rigid. OO Minimally GR gra, have two edges more Doubled cycle: & 

صفحه 28:
riple iconnected Graphs are Globally Rigid in 3D = There is no known generic characterization of global rigidity in 3D, but our result on doubled graphs extends to 3D. = Theorem: Let G be a 2-connected graph. Then G3is globally rigid in 3D. 

صفحه 29:
“eSTmary of Constructive Characterization of Globally Rigid Graphs = 2D - 3-connectivity necessary for GR. 7 062 66 ۱۲ 6 ۰ 7 63 68 1۲ 6 ۰ 9 ( G? GR in 3D if G 2-connected. “ G* GR in 3D if G connected. ™ Unique localizability by increasing sensing range, given initial connectivity. ™ Conditions under which additional information can help. 

صفحه 30:
Sh 30 Outline ™ Introduction to Localization ™ Conditions for Unique Localization = Computational Complexity of Localization " Localization in Sparse Networks 

صفحه 31:
31 Localization Decision problem 4 4, Search problem on 2 ١ 3 ‏توا‎ ‎\ {dig Gog, dys, das, dys} This graph has a Does this have a unique realization. unique realization? What is it? This problem is | eB in general NP- 35 5 Yes/No 

صفحه 32:
SS 2 Computational Mplexity sities are i = Intuitively, reflectton possibilities are linked with computational complexity Suppose all edge distances known for small triangles. ..and reflection possibilities are only sorted out when one gets to another beacon. ELD, Localization goes working out from any beacon. Triangle reflection possibilities grow exponentially... 

صفحه 33:
Complexity of GR Graph 0 5 0 Realization eal 122 LOD bie, how does one go about localizing it? = It is NP-hard to localize a network in R? even when it is known to be uniquely localizable. = We will use two tools in our argument: The NP-hard set-partition problem. ~ The globally rigid wheel graph W,,. ‎set portion probe:‏ با ‎vet of archers G.‏ فصو ‏0 له ‎be partiowed tr tuo‏ © و( فص اه ‎cent -® suck thot he sure of‏ سس مجح له اتب ‎ ‎ ‎ ‎ 

صفحه 34:
۰ ‏ال‎ 34 NP-hardness of Realization تسم( ‎DP -rard‏ & اجه ۵ وی ای لب رال ۴و مستل ۳ rock sketch: Ose uve we hove ceri OC thot toes os puto redizoble qobdly rigid uetghted graph ocd puipuis is unique ‏تا‎ Oe wil Bad he set partion of he pantionable set © soded wlir.ci ‏مد‎ rt the sur of vicrcte t0 @ ‏حصا حدما جا‎ 77/© by wk ‏ا جلت‎ X. ‎Wik 0 setpaniion, Oowirunt a yrapk © dow wih te‏ يس سر )0۳ سع سب موی )ا عونا سملب سلس ‎ven wikout Get Portion, ‎uve rove the ede weights oP (B: duc=Cam(e/2) ‎thot voiquely deterwice te ‏برع ‏جات عبن اطع 6 مدال | محا 2 ميجر ‎Be EE °‏ لل لله سس م سلا ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 35:
35 تج ی موی و Networks for Sparse = Problem with previous result is that edges exist arbitrarily. “ Graphs used in previous proof unlikely to arise in practice. = In realistic networks, edges are more likely to exist between close nodes, and do not exist between distant nodes. Unit Disk Graphs: edge present if distance between nodes less than parameter r. Therefore: if edge absent, distance between nodes is greater than r. ™ Does this information help us solve the localization problem? Red edge would exist in unit disk graph, so unit disk graph localization would not solve Set Partition. 

صفحه 36:
5 36 Complexity of i ocalizing Unit ۰ Disk Graphs Theorem: Localization for sparse sensor networks is NP-hard. Method: Reduction from Circuit Satisfiability to Unit Disk Graph Reconstruction. Reduction is by construction of a family of graphs that represent Boolean circuits. Rigid bodies in the graph represent wires. "Relative position of rigid bodies in the graph represent signals on wires. NOT and AND gates built out of constraints between these bodies expressed in the graph structure. There is a polynomial-time reduction from Circuit Satisfiability to Unit Disk Graph Reconstruction, in which there is a one-to-one correspondence between satisfying assignments to the circuit and solutions to the resulting localization problem. Unit Disk Graph Reconstruction (decision problem) Circuit Satisfiability (NP-hard): input: Graph G along with a parameter r, and the Input: A boolean combinatorial square of each edge length (1, (to avoid irrational circuit. edge lengths). Composed of AND, OR, and NOT gates Output: YES iff there exists a set of points in R? such Output: YES iff the circuit is that distance from u to vis /,, if uvis an edge in G satisfiable. and greater than rotherwise. 

صفحه 37:
Trilateration Graphs ™ As one adds more edges, localization becomes easier: There are classes of globally rigid graph which are easy to localize. = Trilateration graphs are localizable in polynomial time. ™ Remember: One gets a trilateration graph from a connected network by tripling the sensing radius. = Algorithm: [If initial 3 vertices known, localize vertices one at a'time until all vertices localized. Else starting with each triangle in the graph, proceed as above untif all localized. = O(|V|?) or O(|V|°). 

صفحه 38:
38 ان ‎Connectivity in Random‏ ‎Networks‏ The random geometric graph G,(r) is the The following guarantees G,(r) is random ape ‘associated with formations k-connected with high probability with 7 vertices with all links of length less for some constant ¢ large than r, where the vertices are points in enough and constant k: [0,1} generated by a two dimensional li ne, Poisson point process of intensity n. Mn Togn Penrose, ‘99 = Note: Need nP/(log n) > c, for some c, to guarantee even connectivity. = Theorem: If nr/(log n) > 8, with تسج 4 trilateration graph. ™ This identifies conditions under which a simple iterated trilateration algorithm will succeed in localization. 

صفحه 39:
39 | Ffateration in Random Networks ی لاهسا ‎Orodbest posta,‏ Odoodied wo: Leica Por bromo B broxket Prow (x) bead, Drterone donne © (1). Bohrer brankant: head ‏و‎ ‏لا انس‎ = Sensors have 2 modes. ™ Sensors determine distance from heard transmitter. All sensors are pre-placed and plugged in @ukow Post? 

صفحه 40:
40 ۴], Otro? 0/1097 00 LY ‏5د‎ ‎Asymptotics of Trilateration in Random Sensing radiu AAP) aloe) alee) Quonicg fees ty cor plete Ipoakzoiog usta ‏دصنمج هاه‎ Por dPPeredt bearod deceities. Networks Beacons ) 007 77 109 an 

صفحه 41:
Re ee 41 NP-hardness of Localization ® Fine-grained localization is NP-hard due to NP- hardness of realizing globally rigid graphs. = This means that localization of networks in complete generality is unlikely to be efficiently solvable. = Motivates search for reasonable special cases and heuristics. Explains hit-or-miss character of previous approaches. Changing sensing radius can predictably convert connectedness to global rigidity and trilateration. 

صفحه 42:
Outline ™ Introduction to Localization ™ Conditions for Unique Localization = Computational Complexity of Localization " Localization in Sparse Networks 

صفحه 43:
Sh ‏ده‎ ‎Motivation ™ Being able to precisely localize only trilateration networks is unsatisfying. Trilateration networks contain significantly more constraints than necessary for unique localizability. Can we localize networks with closer to the minimal number of constraints? Red edges unnecessary for unique localizability. Trilateration graph Globally rigid subgraph 

صفحه 44:
Sh 44 Bilateration Graphs * A bilateration graph G's one with a bilateration ordering: an ordering of the vertices 1,...,1 such that the complete graph on the initial 3 vertices is in G and from every vertex j > 3, there are at least 2 edges to vertices earlier in the sequence Theorem: Bilateration graphs are rigid (but not globally rigid). = Theorem: Let G = (V,E) be a connected graph. Then G?is a bilateration graph. « Bilateration graphs are finitely localizable in 0(2™) aimaigorithm: If initial 3 vertices known, finitely localize vertices one at a'time by computing all possible positions consistent with neighbor positions until all vertices finitely localized. Else starting with each triangle in th localized. 

صفحه 45:
“fOcalization in Doubled ~*~ Cycles ™ Based on finite localization of bilateration raphs, localization is uniquely computable for globally rigid doubled cycles. = Completes in O(2™!) time. ™ Assumes nodes in general position. = “Sweep” Algorithm: “Fix the position of three vertices. Until no progress made: « Finitely localize each vertex connected to two finitely localized vertices. = Remove possibilities with no consistent descendants. 

صفحه 46:
ocalization in Doubled 2 » Connected Graphs... (ney have an Ear Decomposition) = The ear decomposition gives a ordering in which cycles may be localized using previous algorithm. ™ Note: This means if we have angles, we can localize 2-connected networks. Biconnected network with its ear decomposition. Doubled biconnected network. 

صفحه 47:
a5 Petahieation on General Sparse Networks = Worst-case exponential time algorithm for localization in sparse networks: = For which types of network does sweep localization work? Theorem: Shell sweep finitely localizes bilateration networks. Theorem: Shell sweep uniquely localizes globally rigid bilateration networks. If G is connected, when run on G2, shell sweep produces all possible positions for each node. If G? globally rigid, gives the unique positions. Questio. low many globally rigid networks are also 

صفحه 48:
Shell Sweep on Random Network = Typical random graph. = Starting nodes randomly chosen. Shell sweep uniquely localizes localizable portion. Also non-uniquely localizes nodes rigidly connected to localized region. 

صفحه 49:
Network ™ 500 node graph with considerable anisotropy and 4.5 average degree. = Shell sweep computes in <5 seconds* with no intermediate position set exceeding 128. * As a JAVA applet on a 200 node with a dual 2.8GHz CPU and 268 RAM 

صفحه 50:
a ‘Failing Case ™ Globally rigid network. ™ Connection between clusters unbridgeable by bilateration. 

صفحه 51:
a Tanne natn Localization of Largest Loctite Component Sweep Localization in Regus Newouk 10 0 oo [Lentils —— ۳ 5 Tettement a , 2 4 on ‏سم زو‎ gon 2 ‏م‎ 2 o ‏سب مرن‎ S50 5 See ‏لسلس‎ ‎00 ‏ام‎ ۳۵ 3 30 x 4% ‏ود‎ 20 2 ‏م‎ ‎a ° eo 100 ‏هه 170 هد میا مد میا ها هن‎ 6 3۲ ۳ Smig Range ‏سوت سورد مود‎ Sweeps in Random Network Sweeps in Regular Network ما امه موم اس تسم درگ مت 5 ‎sweeps localizes more nodes than‏ = trilateration, and almost all localizable nodes! "In regular networks, sweeps localizes significantly more nodes than trilateration. "Most incremental localization I algorithms are trilateration based. ‏لللللاوو‎ ee ‏سس‎ = Key point: Many globally rigid random wea en ‏دوم میا رز بایدر یی سر رز برقع‎ 9 

صفحه 52:
a5 v@immary or Localizat of Localization Density Spectr ID hard in general, but there are classes of graphs that are easy to localize. Complete graphs. Trilateration graphs. = Graphs that we know how to localize in worst-case exponential time: Doubled biconnected graphs. = Basic idea: more edges make localization easier. ™ Goal: to understand which networks can be localized and which are problematic. Onwerter ol poreble cetworke ‏ون من‎ t t 1 4 Gowe wtworke car be booted Sows wiworke vos be bodied Ope wetuurke vac be bodted ‏عامط هدن‎ ۰ 0)0[۴( 00 ‏صم اوه‎ وی مالسلا ی بت و مت مد ای او و اف بلس 0 

صفحه 53:
« ‏ان‎ 53 ‏و130 م۷۷‎ ۵ Become Easy? Orwe a Cup Covnplete Braph: @kterctioa Brapk ere ‏سوه‎ ‎<n ISS cern won cos Ml | ‏ممم ومسو ديصي‎ meses OPod ‏امین‎ ro Gparse @: Ousvhoble Oxcober oP eckev 

صفحه 54:
Ree 54 Conclusion and Future Work Formalized the localization problem and its solvability. ™ Showed that the problem is fundamentally computationally hard. ™ Constructively characterized easily localizable networks. ® Provided algorithm that localizes more nodes than previous incremental algorithms. ™ Next: Localization using maps. Localization using angular order information. Localization in networks of mobile nodes. Localization in 3D or on 3D surfaces. Full system from deployment to localization. 

صفحه 55:
re eee 55 Our Work in the Field “Rigidity, Computation, and Randomization in Network Localization” - [Infocom 2004) Conditions for unique fine-grained localization. Initial computational complexity results. “On the Computational Complexity of Sensor Network Localization” - [Algosensors 2004] Computational complexity results. “A Theory of Network Localization” - [Transactions on Mobile Computing 2006] “Graphical Properties of Easily Localizable Sensor Networks’ - [under review] Characterizing easily localizable ad-hoc networks “Precise Localization in Sparse Sensor Networks” Algorithm for localization in sparse ad-hoc networks. [Accepted to Mobicom 2006] “Localization in Partially Localizable Networks” - [Infocom 2005] Investigation of partially localizable networks. Localizability-aware network deployment. “Towards Mo! ity as a Network Control Primitive” - (Mobihoc 2004] Location-aware controlled node-mobility algorithm for sensor network optimization. 

صفحه 56:
eee 56 w Acknowledgements = | would like to thank all my collaborators, without whom this work would not have been possible. ™ Brian D.O. Anderson (Australia National University and NICTA) = James Aspnes P.N. Belhumeur (Columbia University) Pascal Bihler = Ming Cao = Tolga Eren Jia Fang THANK YOU FOR LISTENING Arvind Krishnamurthy ۳ Jie (Archer) Lin ANY QUESTIONS? Wesley Maness A. Stephen Morse Brad Rosen Andreas Sawvides Walter Whiteley (York University) Y. Richard Yang Anthony Young