• unlimited access with print and download
    $ 37 00
  • read full document, no print or download, expires after 72 hours
    $ 4 99
More info
Unlimited access including download and printing, plus availability for reading and annotating in your in your Udini library.
  • Access to this article in your Udini library for 72 hours from purchase.
  • The article will not be available for download or print.
  • Upgrade to the full version of this document at a reduced price.
  • Your trial access payment is credited when purchasing the full version.
Buy
Continue searching

Location and topology discovery in wireless sensor networks

ProQuest Dissertations and Theses, 2009
Dissertation
Author: Christopher Jerry Mallery
Abstract:
Although the specifics of sensor network deployment scenarios are entirely application domain specific, it is envisioned that wireless sensor networks are densely deployed over large monitoring areas. The post-deployment discovery of location and topological information in arbitrarily deployed wireless sensor network is critical to the effective use of a wireless sensor network. Fundamental to wireless sensor networks is the problem of developing a low-cost GPS-free localization technique. Therefore, we first present ANIML, a straightforward, iterative, anchor-free, range-aware, relative localization technique for wireless sensor networks. Through simulation, despite using a non-idealized MAC, we show that ANIML provides good relative localization in uniform, C-shaped and non-uniform topologies. However, while knowing the physical positions of every node in the network provides information about the deployed topology of a wireless sensor network, it does not provide a complete view of a network's topology, such as the shape of the network deployment. The boundaries of the network have a physical correspondence to the environment in which the sensors are deployed. Therefore, we next present a robust, distributed technique that addresses the problem of boundary recognition in wireless sensor networks. We show that our boundary recognition technique constructs accurate perimeters (i.e. correctly bounding all nodes) in randomly deployed topologies of varying densities, perturbed grid topologies of varying densities and in sparsely populated/low-density topologies, in addition to highly irregularly shaped connectivity holes and networks. Lastly, we address the problem of edge detection in wireless sensor networks. Edge detection is the idea of reducing data analysis overhead through the geometric identification of sensed phenomena within a sensor network. We adapt our boundary recognition technique to address the more general problem of edge detection in wireless sensor networks. Our edge detection technique keeps inter-group communication to a minimum, while still constructing correct outer perimeters in the presence of anomalous perimeter crossings and phenomena wholly surrounded by other phenomena. We show that our technique constructs accurate perimeters in randomly deployed topologies of varying densities, perturbed grid topologies of varying densities and in sparsely populated/low-density topologies, in addition to highly irregularly shaped phenomena and networks.

T ABLE OF CONTENTS Page ACKNOWLEDGEMENTS..................................iii ABSTRACT..........................................v LIST OF TABLES.......................................ix LIST OF FIGURES......................................x CHAPTER 1.INTRODUCTION....................................1 2.BACKGROUND.....................................6 2.1 Overview.......................................6 2.2 Geographic Routing..................................6 2.3 Simple Distance Estimation using RSSI.......................7 3.LOCALIZATION....................................9 3.1 Overview.......................................9 3.2 Related Work.....................................12 3.2.1 Range-Aware Localization..........................12 3.2.2 Hop-Based Localization...........................13 3.2.3 Iterative Multilateration...........................14 3.2.4 Underwater Sensor Networks........................16 3.3 Approach.......................................18 3.3.1 ANIML....................................18 vi

3.3.2 Improving ANIML..............................22 3.3.3 ANIML-Abs &ANIML-Hop........................26 3.4 Performance Evaluation................................26 3.4.1 Comparison of Basic ANIML using 1-Hop vs.2-Hop Information.....27 3.4.2 Basic ANIML vs.Improved ANIML....................28 3.4.3 UniformNetworks..............................30 3.4.4 C-shaped Networks..............................34 3.4.5 Non-UniformNetworks...........................34 3.4.6 In the Presence of Obstacles.........................35 3.4.7 Using RSSI to Estimate Distance......................37 3.5 Sea-ANIML......................................38 3.5.1 Sea-ANIML.................................39 3.5.2 Performance Evaluation...........................39 3.6 Summary.......................................42 4.BOUNDARY RECOGNITION.............................43 4.1 Overview.......................................43 4.2 Related Work.....................................47 4.3 Approach.......................................50 4.3.1 Outer perimeter................................52 4.3.2 Inner perimeter(s)...............................62 4.4 Performance Evaluation................................65 4.4.1 Effect of node distribution and density....................67 4.4.2 Further examples...............................72 4.5 Summary.......................................74 vii

5. EDGE DETECTION..................................75 5.1 Overview.......................................75 5.2 Related Work.....................................78 5.3 Approach.......................................83 5.3.1 Outer perimeter(s)..............................84 5.3.2 Identifying the relationships between sensed phenomena..........87 5.3.3 Inner perimeter(s)...............................93 5.3.4 Mitigate unresolved relationships between outer perimeters.........95 5.4 Performance Evaluation................................96 5.4.1 Effect of node distribution and density....................97 5.4.2 Further examples...............................100 5.5 Summary.......................................101 6.CONCLUSIONS....................................103 BIBLIOGRAPHY.......................................108 viii

LIST OF TABLES Page 3.1 Reported Results of ILS,MDS-MAP(P) and SDP..................33 5.1 Sensed Phenomena Outer Perimeter Relationship Identification Criteria......92 ix

LIST OF FIGURES Page 3.1 Basic Iterative ANIML Technique..........................19 3.2 Least-squares Multilateration (k = 4)........................20 3.3 Comparison of ANIML using 1-hop and 2-hop Information.............23 3.4 1-Hop ANIML vs.2-Hop ANIML..........................29 3.5 Enhanced ANIML vs.the Basic ANIML Technique.................30 3.6 ANIML Convergence Time..............................31 3.7 Localization Effectiveness of ANIML in UniformTopologies............33 3.8 Localization in C-shaped Networks..........................35 3.9 Localization in Irregular Densities..........................36 3.10 Localization with Obstacles..............................37 3.11 Distance Estimates fromTwoRayGround Propagation Model............38 3.12 Localization accuracy of Sea-ANIML........................40 3.13 Localization accuracy of Zhou et al.’s technique,taken from[95,96]........41 3.14 Localization coverage of Zhou et al.’s technique,taken from[95,96]........41 4.1 Our technique executed on an example topology with one concave hole.......53 4.2 The self-identified boundary nodes (black squares) for (a) a single hole topology (4050 nodes with an average degree of 10) and (b) a multi-hole topology (4050 nodes with an average degree of 10)..........................54 4.3 The initial group for (a) a single hole topology and (b) a multi-hole topology....55 4.4 Graham’s Scan....................................56 4.5 The identified convex hull nodes (black squares) for (a) a single hole topology and (b) a multi-hole topology................................57 x

4.6 The initial external perimeter for a (a) single hole topology and (b) multi-hole topology,in addition to the groups of remaining uncaptured nodes..........58 4.7 An example of capturing a small set of nodes left uncaptured by the construction of the initial rough outer perimeter...........................59 4.8 The identified perimeters after all nodes are captured for (a) a single hole topology and (b) a multi-hole topology.............................59 4.9 An example of merging on the of the perimeters identified in Figure 4.7.......60 4.10 The final rough outer perimeter after all perimeters are merged for (a) a single hole topology and (b) a multi-hole topology........................61 4.11 The final external perimeter after refinement for (a) a single hole topology and (b) a multi-hole topology..................................63 4.12 The first perimeter split for (a) a single hole topology and (b) a multi-hole topology.65 4.13 The final internal and external perimeters for (a) a single hole topology and (b) a multi-hole topology...................................66 4.14 Randomly distributed sensor field...........................68 4.15 Wang et al.’s technique,taken directly from[85],in a uniformly distributed sensor field...........................................69 4.16 Results for randomly perturbed grids.........................70 4.17 Wang et al.’s technique,taken directly from[85],in a randomly perturbed grid...70 4.18 Results when the density of the graph decreases....................71 4.19 Wang et al.’s technique,taken directly from [85],as the density of the graph de- creases.........................................72 4.20 Results for more interesting examples,adapted from[85]...............73 4.21 Wang et al.’s technique,taken directly from[85],for more interesting examples...73 5.1 Our technique executed on an example topology with one sensed phenomena....85 xi

5.2 The self-identified boundary nodes (black squares) for (a) a single phenomenon topology (4050 nodes with an average degree of 10) and (b) a multi-phenomena topology (4050 nodes with an average degree of 10).................86 5.3 The initial groups for (a) a single phenomenon topology and (b) a multi-phenomena topology........................................87 5.4 The identified convex hull nodes for (a) a single phenomenon topology and (b) a multi-phenomena topology...............................88 5.5 The initial connected perimeters for a (a) single phenomenon topology and (b) multi-phenomenon topology,in addition to the groups of remaining uncaptured nodes..........................................88 5.6 The identified perimeters after all nodes are captured for (a) a single phenomenon topology and (b) a multi-phenomena topology.....................89 5.7 The final rough perimeters after all perimeters are merged for (a) a single phe- nomenon topology and (b) a multi-phenomena topology...............89 5.8 The final outer perimeters after refinement for (a) a single phenomenon topology and (b) a multi-phenomena topology..........................90 5.9 Possible relationships between constructed outer perimeters.Fromleft to right:(a) true overlap;(b) surrounding;(c) surrounded;(d) crossing;(e) crossed........92 5.10 The first round of perimeter splits for (a) a single phenomenon topology and (b) a multi-phenomena topology...............................94 5.11 The final internal and external perimeters for (a) a single phenomenon topology and (b) a multi-phenomena topology..........................95 5.12 An example of our technique mitigating crossings perimeters.............96 5.13 Randomly distributed sensor field...........................98 5.14 Results for randomly perturbed grids.........................99 5.15 Results when the density of the graph decreases....................100 xii

5.16 Results for more interesting shaped phenomena....................101 xiii

Dedication I dedicate this dissertation to my daughter Kalie, the greatest gift I have ever known. xiv

CHAPTER 1 INTRODUCTION Wireless sensor networks are application-specific,wireless ad-hoc networks populated with small, low-cost,resource-constrained immobile nodes equipped with one,or more,external sensors [77]. Wireless sensor networks also contain one or more base stations,which are less resource-constrained devices that are responsible for connecting the wireless sensor network to the users of the network. Initially military applications,such as target acquisition/tracking and battlefield surveillance,drove the development of wireless sensor networking technology [4].However sensor networks are now commonplace in civilian monitoring applications,such as environment and habitat monitoring, healthcare applications,home automation,traffic control and fire detection/control [15].In many sensor network applications,such as battlefield surveillance or hostile environment monitoring, there is no viable node recovery plan making each sensor node a disposable asset [64].Addition- ally,some sensor network applications require that the sensor nodes do not influence the deployed environment,such as habitat monitoring.Therefore,for the practical deployment of many sensor network applications the cost and physical size of each sensor node is critical,which makes hard- ware selection crucial.In general,the sensor nodes that compose a typical wireless sensor network contain five key components:microcontroller,wireless transceiver,external memory,power source and sensor(s) [84].While the microcontroller and external memory components of a sensor node dictate the processing power and storage capacity of a sensor node,these two components are not key indicators of the suitability of a sensor node to a particular sensor network application.Ad- ditionally,most sensor node hardware currently in production have a modular sensor interface,so the choice of sensor node hardware is independent of specific sensor needs.This makes the power source and wireless transceiver the key indicators of the suitability of a sensor node to a sensor network application.Since there is no way to replace sensor batteries for many sensor network applications the correct choice of power supply is critical to the longevity of the wireless sensor 1

netw ork,coupled to the fact that the most energy consuming task on a sensor node is the wireless transmission of data.Therefore,the selection of the least powerful wireless transceiver,in terms of data speed and transmission range,to meet the needs of the sensor network application is ideal. For example,The Mica2 Mote,developed by U.C.Berkeley,has a Atmel ATmega128L microcon- troller with 128k of program flash memory and 512k of external memory,typically operates on 2 AA batteries,is built upon a 51 pin modular sensor system and capable of wireless transmissions of 38.4 kbits/sec with an outdoor line-of-sight range of about 500 feet [1]. Although the specifics of sensor network deployment scenarios are entirely application domain specific,it is envisioned that wireless sensor networks are densely deployed over large monitoring areas.Deployment scenarios range between manual deployment to completely random scatter- ing over a specific region,such as aerial or artillery-based deployment.Regardless of deployment mechanismor application,most general purpose sensor networking services,such as sensor identi- fication,routing,data fusion and data analysis,require some knowledge of a network’s topology in order to operate effectively [87].For example,one or more sensor nodes detecting a fire are useless if the location of the sensors is unknown.Identifying the positions of each node in a sensor deploy- ment is considered a fundamental operation in wireless sensor network and almost every wireless sensor network has some knowledge of node positions,or localization technique in place [85]. There remain many unsolved problems in the field of wireless sensor network research.One fundamental wireless sensor network problemthat remains unsolved is the development of a low- cost GPS-free localization technique.Localization is the process by which the nodes of a sensor network self-determine the network’s topology,by identifying the physical coordinates of every node in the network.The most straightforward methods of localization are GPS and manual entry. Manually entering the positions of every node in large,dense sensor deployment is not a scalable or realistic option in most situations [16].On the other hand,equipping every sensor node with GPS technology,while obviating the need for localization,increases the cost of each individual node and greatly increases the deployment costs of deploying a sensor network.Greatly increasing the 2

cost of each sensor node directly conflicts with the overall goal of sensor network nodes becoming low enough in cost that they are considered disposable [64].Additionally,depending on GPS for localization limits the applicability of sensor networks to outdoor environments [61].The prohibitive cost of equipping sensors with GPS is the reason many localization techniques restrict GPS ability to only a small subset of the total network nodes,called anchors [77].Deploying even a small set of anchors into a sensor network provides the ability for the network to be localized absolutely (i.e.estimated positions are directly related to GPS positions),whereas a network with no deployed anchors can only be localized relatively (i.e.estimated positions are only meaningful relative to other positions in the same network).However,in most sensor network applications, absolute localization is not strictly necessary;instead it is overall topology identification,or relative localization,that is critical for sensor identification,routing,data fusion and data analysis [87]. Considering the cost increase of equipping just a single node with GPS technology,localization techniques that minimizes the use of anchors become critical [89].However,an ideal relative localization technique should take advantage of the additional information provided by anchors in the event of their availability;just not strictly depend on them. While knowing the physical positions of every node in the network provides a large amount of information about the deployed topology of a wireless sensor network,it does not provide a complete viewof a network’s topology.Knowing the coordinates of each node in the network only allows for the gathering of sensor data values associated with discrete locations.While obtaining location/value pairs is the purpose of a sensor deployment,it may not provide everything about the deployed environment of a sensor network.Specifically,the shape of the network deployment can provide important information about the region under observation.The boundaries of the network, both the inner (i.e.internal connectivity holes) and the outer (i.e.the network’s external perime- ter),almost always have a physical correspondence to the environment in which the sensors are deployed [85].For example,consider an internal connectivity hole caused by a previously uniden- tified body of water in the middle of the sensor deployment.Knowing the shape of the connectivity 3

hole provides previously unknown information about the body of water,or other entity,that caused the hole.The same also goes for the shape of the entire network deployment,for example if the monitored region is the bottom of a large ravine.Additionally,not being aware of the boundaries within a sensor network can lead to degradation in performance over time.For example,in shortest path routing,nodes along the boundary of a hole tend to receive more intermediate route requests, increasing their overall load and ultimately reducing their power sources faster than other nodes in the network [27].This can cause a small hole to grow over the lifetime of the network due to failing boundary nodes. Another key aspect of topology discovery is the geometric identification of sensed phenomena currently within a wireless sensor network.Obtaining how the sensed data relates to the physical topology is fundamentally the goal of deploying a sensor network.Again,while knowing the co- ordinates of each node in the network does allowfor the gathering of sensor data values associated with discrete locations,it does not directly provide any relationships between obtained data.For example,it is difficult to identify whether or not two relatively close nodes in a sensor network with the same or reasonably similar sensed data are identifying the same sensed phenomena or are identifying different phenomena that just happen to have the same sensed data value.Traditionally, each individual sensor node forwards its data to a single less resource-constrained location for cen- tralized analysis.However,this approach hides or removes any relationships between the gathered sensed data fromthe network,can cause high network overhead and even reduce the lifetime of the network.The potential drawbacks of the centralized collect and analyze paradigm for sensor data analysis makes the development of more advanced data analysis techniques for sensor networks important,which has led to several distinct approaches to solve the problem.The most recent of which is broadly referenced in the literature as edge detection.Edge detection aims to reduce data analysis overhead by providing a more concise view of sensed data through the geometric identification of sensed phenomena within a sensor network. 4

Our research efforts target the discovery of location and topological information in arbitrar- ily deployed wireless sensor network in the absence of any accessible global information about the deployed topology.The first topic addressed in this dissertation is the design of an anchor- free relative localization for wireless sensor networks.The creation of a distributed boundary recognition requiring only a relative coordinate system is address next.Lastly,we generalize our boundary recognition technique into a general edge detection technique.The organization of this dissertation follows.Chapter 2 provides some background information specific to our localiza- tion,boundary recognition and edge detection techniques in WSN.The contents of Chapters 3–5 provided presents our anchor-free relative localization technique,distributed boundary recogni- tion technique and unified technique for both edge detection and boundary detection,respectively. Chapter 6 presents conclusions and discusses possible future work. 5

CHAPTER 2 BACKGROUND 2.1 Overview In this chapter,we provide a brief required background on wireless sensor networks.These topics are discussed as they directly relate to the research presented later in this dissertation.They are included for the purpose of completeness and are not intended as exhaustive discussions on the topics.This chapter is organized as follows.Section 2.2 presents a brief introduction to geographic forwarding in wireless ad-hoc networks.Section 2.3 discusses the basic technique behind distance estimation using received signal strength in a wireless network. 2.2 Geographic Routing Traditional routing techniques in wireless sensor networks depend heavily on network flooding to determine suitable paths between two non-neighboring nodes.Unfortunately,floods are a source of high communication overhead,which in turn increases the energy expenditure of the entire net- work deployment.Flooding in of itself is not necessarily a bad thing and in some cases it is the most effective and efficient way to disseminate information throughout a sensor network,however requiring a flood for every route request,considered a fundamental operation in ad-hoc sensor net- works,can be incredibly detrimental to the health of a network consisting of resource-constrained sensor nodes.The newest class of ad hoc routing protocols are geographical,or location aware, routing protocols.The general principles of geographical routing have been widely applied in other types of networks,such as cellular networks [45].Geographic routing protocols take advantage of knowing the physical location of hosts in order to facilitate efficient,effective and scalable routing in ad hoc networking environments.This is accomplished through various approaches fromsimply using location information to reduce the overhead of traditional ad hoc routing protocols to the de- sign of completely coordinate-dependent routing protocols.The limitation of geographic routing 6

protocols is their complete dependence on every host in the network having the ability to ascertain its own physical location.However,unlike mobile ad-hoc networks,most sensor networks have some formof localization in place [85].This allows themto take advantage of geographic routing protocols. The most basic geographic routing technique is simple geographic forwarding.In simple geo- graphic forwarding there is no route identification process,instead nodes simply forward packets to their neighboring host that is located closer to the intended receivers than they are.In uniformly dense ad hoc networks,simple geographic forwarding works extremely well.However,in net- works that contain large voids,simple geographic forwarding does a terrible job routing packets around the void [70].GPSR [43],or greedy perimeter stateless routing,is a routing protocol that consists of two packet forwarding methods:greedy and perimeter forwarding.GPSR’s greedy for- warding technique is just simple geographic routing and the protocol tries to take advantage of this form of forwarding as much as possible.GPSR switches to perimeter forwarding when it deter- mines that greedy forwarding is unable to get a packet to its destination.Perimeter forwarding uses the graph traversal concept of the right-hand rule.The right hand rule states that when arriving at a vertex x from a vertex y the next edge that is traversed is the edge that is next counterclockwise edge from yx leaving x.Using the right-hand rule the traversal of the outside of a polygon,or face,is possible.The idea is that a void in an ad hoc network is simply a face that to be routed around.GPSR then forwards a packet along faces trying to keep on a line fromthe last host where perimeter forwarding was required and the known position of the destination. 2.3 Simple Distance Estimation using RSSI There are many methods by which wireless receivers are capable of estimating their distance from a transmitter.The simplest of which is using the received signal strength (RSSI) of a transmission to infer the distance the transmission traveled between the receiver and the sender.In order to accurately determine the distance between a transmitter and receiver using RSSI requires that the 7

original transmission power used by the transmitter to send the transmission is known [47].In traditional wireless networks assuming to know the transmission power of a received transmission is not safe due to differing transmission power settings,however in wireless sensor networks where it is usually assumed that all nodes use the same wireless transmitters,or at the very least,that any differing hardware is known prior to deployment.Since it is nearly impossible to completely quantify the propagation characteristics of any uncontrolled environments due to unknown sources of interference,in order to get an estimated distance between the sender and receiver,freespace propagation of radio signals is often assumed.In freespace only distance traveled causes a loss to signal strength,therefore easily allowing for the calculation of distance from RSSI.Obviously, using the distance traveled in freespace only provides an estimate in real environments.In order to calculate distance traveled,in freespace,of a transmission,assuming we know the received signal strength and the original transmission strength,we use Friis Equation [47]: P R x = P T x G T x G R x λ 2 16π 2 d 2 L ,(2.1) where G T x is transmitter antenna gain,G R x is receiver antenna gain,λ is wavelength,d is distance separating T x and R x antennas and L is the systemloss factor (≥1).Solving for d we get: d =

P T x G T x G R x λ 2 16π 2 LP R x .(2.2) Simplifying, we assume perfect antennas,G R x = G T x = 1,and no external signal loss,L = 1, leaving us with: d =

P T x λ 2 16π 2 P R x .(2.3) Despite being error-prone,this equation is usable as a means to estimate the distance between a sender and a receiver knowing only minimumrequired information. 8

CHAPTER 3 LOCALIZATION 3.1 Overview Localization is the process by which the nodes of a sensor network self-determine the network’s topology.This typically involves identifying the physical coordinates of every node in the network. Equipping every node in a wireless sensor deployment with GPS or manually placing every node in predetermined locations does technically solve the problem of localization.However,a well- designed localization technique should minimize the cost of localizing a network.Unfortunately, equipping every node with GPS is financially costly and manual placement is labor intensive.A significant challenge faced in the design of a cost effective localization techniques is the depen- dence on globally available information (i.e.network-wide flooded information).While using globally available information provides a technique with more information on which to base its solution,it also introduces the problem of cascading errors.Cascading errors are the result of compounding estimation errors propagating through the network.Since many localization tech- nique depend on estimated inter-node distances in order to localize the network,cascading ranging errors significantly affect the accuracy of many localization techniques [90].A common approach to reduce the effects of cascading ranging errors is to restrict information propagation to only lo- cal neighborhoods.ILS [55] implements this strategy to control the effects of cascading ranging errors.However,the restriction of information propagation to handle cascading ranging errors creates another problem.Information propagation restrictions introduce the problemof nodes in a single neighborhood getting stuck at a local optimum.That is,there is not enough external infor- mation to keep a single neighborhood from choosing wildly inaccurate final positions in a global sense,while the positions are accurate in a local sense.This tends to happen in neighborhoods that not well surrounded by other neighborhoods,such as corner and edge neighborhoods.ILS [55] is 9

the only localization technique in the literature to address this phenomenon.It deals with it using an error control mechanism that prevents “bad seeds” from contaminating the position estimation of other nodes.Championed as not requiring additional message overhead to implement,control mechanisms are not without cost.The computational overhead of error control mechanisms can be significant depending on the underlying filtering technique used. While wireless sensor networks have become commonplace in many different areas of monitor- ing,current wireless sensor networking technology is not necessarily suitable for all environments. In recent years,there has been increasing interest in the extensive monitoring of large-scale un- derwater environments.The ideal solution to extensive monitoring of large-scale environments is the deployment of wireless sensor networks.However,terrestrial sensor networking technology is not readily deployable in aquatic environments.The need for large-scale monitoring in aquatic locations has given rise to the research field of underwater sensor networks [96].Many different fields of research benefit from the use and continued improvement of underwater sensor network- ing technology.Archeology,seismic research and ocean life observations are just a fewof the fields that directly benefit from the use of underwater sensor networks [22].While the overall goal and basic operation of underwater sensor networks is the same as terrestrial wireless sensor networks, there are several important differences.Foremost,underwater sensor nodes are deployable into true three-dimensional topologies,capable of controlling and measuring their own depth.Also, communications between underwater sensor nodes is done using acoustic communication,which has much lower bandwidth,higher propagation delay and higher bit error rates than traditional RF wireless communication [60].Most research topics of importance to the development of terres- trial wireless sensor networks remain important in the development underwater sensor networks, with some even being more important to the development of underwater sensor networks due to the adverse nature of underwater environments.Localization is a critical challenge in underwater sensor networks,even more so than in terrestrial networks,because GPS is not readily available due to GPS signals not propagating correctly through water [22].Additionally,the differences 10

between acoustic and RF communication channels render many terrestrial localization techniques impractical or infeasible [82]. In this chapter,we present a straightforward,iterative,anchor-free,range-aware relative lo- calization technique for wireless sensor networks,called Anchor-free,local Neighborhood-based, Iterative MultiLateration (ANIML).ANIML is capable of providing accurate relative localization without making assumptions about a deployed topology.ANIML does not depend on globally flooded information,reducing the effects of cascading ranging errors by restricting its derived distance estimates to a node’s 1- and 2-hop neighbors.While least-squares minimization is a mathematically simple constraint optimization technique,by utilizing 1- and 2-hop neighbor in- formation as constraints,ANIML provides accurate relative localization without the need for an- chors,sophisticated error control and/or global information.In addition to presenting ANIML,we also introduce three ANIML variants:ANIML-Abs,ANIML-Hop and Sea-ANIML.While AN- IML does not require anchors in order to provide accurate relative localization,ANIML-Abs takes advantage of any deployed anchor nodes to allow for absolute localization.ANIML-Hop is capa- ble of localizing a network using only hop counts,in the absence of ranging equipment.Neither ANIML-Abs nor ANIML-Hop requires changes to the underlying ANIML technique.Extensive performance analysis shows that ANIML,ANIML-Abs and ANIML-Hop provide accurate local- ization and scale well.Lastly,we adapted ANIMLinto a range-aware localization technique for use in underwater wireless sensor networks,called Sea-ANIML.Simulations showthat Sea-ANIML is able to provide accurate localization in three-dimensional deployments where each sensor directly measures its own depth. The rest of this chapter’s organization follows.Section 3.2 presents related work on localization in wireless sensor network and underwater sensor networks.Section 3.3 introduces our ANIML technique as well as ANIML-Abs and ANIML-Hop.Section 3.4 contains performance analysis. Section 3.5 presents Sea-ANIML and Section 3.6 presents a summary of the chapter. 11

3.2 Related Work Previous attempts at solving the problemof localization in sensor networks can be categorized into two groups:range-aware and hop-based.In range-aware techniques a distance metric is somehow derived and used to estimate node positions.In hop-based localization no ranging hardware is needed,and in many ways the distance estimates between nodes are simplified to the number of hops in the shortest path.Both range-aware and hop-based approaches often employ traditional methods,such as triangulation or optimization techniques,in order to calculate node positions. However,localization techniques are often overburdened by constraints,such as specific node dis- tribution and approximated transmission ranges in order to reduce the problem so that traditional mathematical techniques can be applied.Additionally,most localization techniques for WSN pro- vide absolute localization,however there are some techniques that do provide relative localization for use when absolute localization is not strictly necessary,such as MDS-MAP [78],SPA[83],Rao et al.’s localization technique for mobile ad-hoc networks [70],the convex optimization technique in [21],the distributed Kalman filter approach [74],VCap [13],CBL [58] and nQUAD [87]. The rest of this section’s organization follows.Sections 3.2.1 and Section 3.2.2 present brief related work on range-aware and hop-based localization techniques,respectively.Section 3.2.3 provides a more detailed survey of iterative multilateration localization techniques,which is the class of localization approaches that are the most closely related to ANIML.Section 3.2.4 presents related work on localization in underwater sensor networks. 3.2.1 Range-Aware Localization Range-aware localization techniques typically derive inter-node distances based on received signal strength measurements from another transmitting node [3,6–8,10,16,21,23,31,33,41,50,53, 55,61,65,68,71–74,79–81,83].Most techniques calculate the distances that transmissions have supposedly traveled between two nodes in the network directly from signal strength [3,7,10,16, 33,41,50,55,65,68,71–74,79,83].However,inter-node distances may also be estimated by other 12

Full document contains 133 pages
Abstract: Although the specifics of sensor network deployment scenarios are entirely application domain specific, it is envisioned that wireless sensor networks are densely deployed over large monitoring areas. The post-deployment discovery of location and topological information in arbitrarily deployed wireless sensor network is critical to the effective use of a wireless sensor network. Fundamental to wireless sensor networks is the problem of developing a low-cost GPS-free localization technique. Therefore, we first present ANIML, a straightforward, iterative, anchor-free, range-aware, relative localization technique for wireless sensor networks. Through simulation, despite using a non-idealized MAC, we show that ANIML provides good relative localization in uniform, C-shaped and non-uniform topologies. However, while knowing the physical positions of every node in the network provides information about the deployed topology of a wireless sensor network, it does not provide a complete view of a network's topology, such as the shape of the network deployment. The boundaries of the network have a physical correspondence to the environment in which the sensors are deployed. Therefore, we next present a robust, distributed technique that addresses the problem of boundary recognition in wireless sensor networks. We show that our boundary recognition technique constructs accurate perimeters (i.e. correctly bounding all nodes) in randomly deployed topologies of varying densities, perturbed grid topologies of varying densities and in sparsely populated/low-density topologies, in addition to highly irregularly shaped connectivity holes and networks. Lastly, we address the problem of edge detection in wireless sensor networks. Edge detection is the idea of reducing data analysis overhead through the geometric identification of sensed phenomena within a sensor network. We adapt our boundary recognition technique to address the more general problem of edge detection in wireless sensor networks. Our edge detection technique keeps inter-group communication to a minimum, while still constructing correct outer perimeters in the presence of anomalous perimeter crossings and phenomena wholly surrounded by other phenomena. We show that our technique constructs accurate perimeters in randomly deployed topologies of varying densities, perturbed grid topologies of varying densities and in sparsely populated/low-density topologies, in addition to highly irregularly shaped phenomena and networks.