Network Information

Location:

Pullman, WA

Posted:

January 02, 2013

Contact this candidate

Resume:

Relative Localization with *-Hop Neighborhood

Christopher J. Mallery Sirisha Medidi and Muralidhar Medidi

School of EECS, Washington State University Dept. of CS, Boise State University

Pullman, WA 99164-2752 Boise, ID 83725-2075

{sirishamedidi,MMedidi}@boisestate.edu

********@****.***.***

Abstract In most WSN applications, the precise location of each

sensor node in the network (absolute localization) is not

Localization is the process in which nodes in a wireless strictly necessary; instead overall topology identi cation

sensor network self-determine their positions in the net- (relative localization) is critical for sensor identi cation,

work. While there are many effective mathematical tech- routing, data fusion and data analysis [13]. Towards this

niques for solving the problem of localization, most are goal, we propose a straightforward, iterative, anchor-free,

not suitable for the resource-constrained distributed envi- range-aware relative localization technique for wireless

ronment of sensor networks. We propose ANIML an iter- sensor networks, called Anchor-free, local Neighborhood-

ative, range-aware relative localization technique for wire- based, Iterative MultiLateration (ANIML). Using only dis-

less sensor networks that requires no anchor nodes. ANIML tance estimates between a node and its 1- and 2-hop neigh-

restricts itself to the use of only local 1- and 2-hop neigh- bors, ANIML is capable of providing robust relative lo-

bor information, avoiding the need for information ooding calization through least-squares multilateration without ex-

and thus controlling cascading ranging errors that bedevil plicit error control or costly anchors. Also by restricting

other localization techniques. While least-squares mini- distance estimates to only 1- and 2-hop neighbors, instead

mization is a mathematically simple constraint optimization of global information, we reduce the effects of cascading

technique, utilizing 1- and 2-hop neighbor information as ranging errors; such cascading errors signi cantly affect the

constraints, ANIML provides better localization without the accuracy of many range-aware localization techniques [15].

need for more sophisticated error control and/or global in-

formation. We implemented ANIML in ns-2 and conducted 2 Related Work

extensive experimentation to evaluate its performance. Ex-

perimental results show that ANIML provides robust local-

Previous attempts at localization in WSN fall into two

ization and scales well.

groups: range-aware and hop-based. In range-aware tech-

niques, such as SPA [2] and ILS [6], the calculation of node

1 Introduction position estimates use inferred distances. A common as-

sumption, which can provide more accuracy, is estimation

Wireless sensor networks (WSN) are application- of the distance between a normal sensor node and (one or

speci c wireless ad-hoc networks populated with small, more) beacons or (three or more) anchor nodes, which are

low-cost, resource-constrained immobile nodes equipped nodes that can self-determine their own absolute positions.

with one, or more, external sensors [10]. Regardless of Hop-based methods, such as DV-Hop [8] and HCRL [14],

speci c application, WSN are envisioned to be densely de- require no ranging hardware, with the distance between

ployed over large monitoring areas where knowledge of the nodes often simpli ed to the hops in the shortest path. Both

deployed topology becomes critical for effective data dis- range-aware and hop-based approaches often employ tra-

semination. Many proposals sprang from the need for low- ditional methods, such as triangulation or optimization, to

cost, lightweight and effective localization for WSN is im- calculate node positions. However, often overburdened by

portant. The prohibitive cost of equipping sensors with GPS constraints, most techniques reduce the problem such that

is the reason many localization techniques restrict GPS to traditional mathematical techniques can solve the problem.

only a small subset of the total network nodes, called an- Most localization techniques for WSN provide absolute lo-

chors [10]. Considering the cost increase of equipping just calization, however there are some techniques that do pro-

a single node with GPS, localization techniques that mini- vide relative localization, such as MDS-MAP [11], SPA [2],

mizes the use of anchors become critical [14]. the convex optimization technique in [3] and the distributed

978-1-4244-2100-8/08/$25.00 c 2008 IEEE

Kalman lter approach [12]. Node k :

For the sake of space we now focus only on iterative while termination condition not met do

multilateration localization techniques that directly relate to BroadcastMessage ANIML, interested readers should refer to and [5] and [7] collect messages from neighbors

for a more complete review of related works. Iterative mul- for each message rcvd from a node i do

tilateration localization approaches iteratively converge on dk,i measured distance estimate from node i

a network topology [1]. These techniques are primarily update stored information for node i

range-aware, but can also be hop-based. Capkun et al. [2] for each node j in rcvd list of i s neighbors do

have shown that nodes in MANETs without any anchor dk,j dk,i + rcvd dist of node j from i

nodes can estimate positions by means of iteration, using update stored information for node j

their range-aware Self-Positioning Algorithm (SPA), to fa- end for

cilitate geographical routing. Using only local neighbor- end for

hood (both 1- and 2-hops), each node builds a local map RecalculateCoordinates of its entire neighborhood and then aligns these individual end while

maps. However, facing node mobility typical in MANETs,

Figure 1. Iterative ANIML Technique

the estimated positions attempt to preserve inter-node dis-

tances in the local neighborhood and need not correlate with

node is identical in capability to all other sensor nodes in

the physical network topology. Robinson and Marshall [9]

the network. We assume that the sensors are equipped with

present a distributed iterative multilateration approach of

ranging hardware to estimate, from received transmissions,

nodes guessing and re-guessing their position estimates.

the distances to the direct 1-hop neighbors: thus, ANIML is

This series of guesses, by means of linear regressions, will

a range-aware localization technique.

converge to a topology that satis es all distance estimates

The underlying multilateration technique in ANIML is

measured within the network and requires global network

the well-known least-squares constraint optimization. Fig.

knowledge and a subset of anchors. Another iterative mul-

1 outlines ANIML s iterative localization process, run inde-

tilateration approach, although computationally expensive,

pendently on each node. ANIML iterations do not require

uses distributed Kalman ltering and a subset of anchor

any tight synchronization. In each iteration, every node cal-

nodes to handle localization [12]. Doherty et al. [3] pro-

culates an updated position estimate, x, given the received

posed a centralized localization through convex optimiza-

position estimates from its 2-hop neighborhood and associ-

tion on local neighborhood geometric constraints. Liu et al.

ated distance estimates, using least-squares multilateration.

have recently proposed ILS which is a 1-hop neighborhood-

Initially, every node will only be aware of its own estimated

based, iterative least-squares localization technique, which

position, making it unable to recalculate a new estimated

controls cascading ranging errors by scoring distance esti-

position. In which case, it will broadcast its current esti-

mates [6]. This allows only known good estimates to be

mated position to its 1-hop neighbors. In the next iteration,

used for localization and the bad seeds to be ltered out.

each node will be aware of its estimated position, those of

While ILS and ANIML have much in common, ILS strictly

its 1-hop neighbors and the estimated distances of its 1-hop

requires anchors in order to perform its localization. Re-

neighbors made through direct ranging. This information

cently proposed Sweeps [4] also is similar to ILS, designed

allows a node to begin recalculating its own position esti-

speci cally for sparse networks and uses graph theoretical

mate. Since each node s initial position is the origin, this

methods instead of least-squares optimization.

rst recalculation will place a node roughly the average es-

timated distance it is from all of its 1-hop neighbors away

3 The ANIML Technique from the origin in an arbitrary direction. Each node then

broadcasts its new position estimate, in addition to the posi-

The basic idea behind our iterative localization technique tion estimates it has received from its 1-hop neighbors and

is for nodes to expand their positions outward, from their the distance estimates it has made for its 1-hop neighbors.

starting positions at the origin, towards their actual relative In the third, and subsequent iterations, each node is aware of

positions in the network, with each iteration. Since there are its own estimated position, those of its 1- and 2-hop neigh-

no anchors to provide absolute positions in the network, the bors, the estimated distance of its 1-hop neighbors made

localizing sensor nodes have no prede ned coordinate sys- through direct ranging and the estimated distances of its 2-

tem available on which they can converge. ANIML handles hop neighbors. ANIML infers a node s distance from a 2-

this by choosing a single node, the reference node, to remain hop neighbor by adding the received distance estimate be-

stationary at the origin through all iterations. This gives tween the intermediate 1-hop neighbor and the 2-hop neigh-

nodes a common absolute position from which to expand bor to the directly calculated distance estimate of the inter-

outwards. Other than remaining at the origin, the reference mediate 1-hop neighbor. Now every node is fully able to

erative nature of ANIML naturally places a node into its

400 400

correct position when its neighborhood is well distributed

300 300 7

7 26

around it. Problems occur when a node s neighbors are bi-

17 14 14

200 200

2835 15

ased in one direction from the node (i.e. corner and edge

41 49

9 19

100 100

19 41

30 4 5

5 25

44 25

40 40

29 38

18 36

23 18

nodes). Corner and edge nodes can end up estimating their

0 *-**-**-*-*-**-**

324*-****-**

1 24

34 48 12 12

43 34 6

1646 20

33 6

20 43 42

42 16 13

-100 -100

38 1

position on the wrong side of their 1-hop neighborhood.

23 2

47 11 48

37 37

-200 -200 29

These inappropriately placed nodes appear ipped into

-300 -300

-200 -100-*-***-*** 300 400 -200 -100-*-***-*** 300 400

their 2-hop neighbors, towards the center of the network. In

order to combat the problem of anomalous ipped nodes we

(a) 1-hop (b) 2-hop

extended ANIML with a simple sanity check technique to

Figure 2. ANIML with 1- and 2-hops

detect a ip and correct it if necessary.

take advantage of least-squares multilateration to recalcu-

late a more accurate position estimate, because those neigh- 4 Performance Evaluation

bors estimated positions have spread apart. Additionally,

the availability of 2-hop neighbor information allows the

We implemented ANIML in ns-2 and compared its effec-

nodes of a neighborhood to begin moving closer towards

tiveness to APS (DV-Hop) [8], a popular technique for base-

their actual distance away from the reference node and any

line comparisons. Since the authors own results show that

adjoining 1-hop neighborhoods.

DV-Hop outperforms DV-Distance, we compare against

By restricting distance estimates to only 1- and 2-hop DV-Hop instead of the range-aware DV-Distance. The sim-

neighbors, instead of globally propagated information, such ulation environment for ANIML uses 802.11 MAC. We ob-

as the positions of anchors, we reduce the effects of cascad- tained all DV-Hop data by replicating the experiments us-

ing ranging errors; such cascading errors signi cantly affect ing the DV-Hop authors CAML implementation of APS.

the accuracy of many range-aware localization techniques We used both 5% and 10% anchor distributions in the DV-

[15]. To control the message and computation complexity, Hop experiments. We generated topologies in four different

sizes (250 x 250, 500 x 500, 750 x 750 and 1000 x 1000 m2 )

we would have preferred to restrict ANIML to use only 1-

and two different node densities (400 and 800 nodes/km2 )

hop neighbor information. However, we found that while

this can provide accurate localization in some cases, often in order to investigate ANIML s scalability. The maximum

individual neighborhoods localize too rapidly based on only transmission range of each sensor is 250 meters, although

their own 1-hop neighborhood s information, fold onto each our presented results scale to smaller transmission ranges.

other, and get stuck at a local optimum. This problem is also Distance estimates for ANIML are obtained by adding a

encountered in ILS [6] and other techniques [8, 12]. Such uniformly distributed error (0-90%) to the true distance

folding of neighborhoods cannot be either detected or recti- between two neighboring nodes to mimic experiments re-

ed with only 1-hop neighbor information. Fig. 2(a) shows ported in [8]. Each data point presented in our plots is the

the localization of a network by ANIML using only 1-hop average of ten runs with differing random seeds, with no

neighbor information (estimated positions are denoted by discarding of outliers.

circles with the arrows pointing to the true positions). The The metric for localization effectiveness, used in the lit-

accuracy of the localization is poor with an average posi- erature, is the average distance away their estimated posi-

tioning error of 90 meters; however the average pairwise tions are from the nodes actual positions in the network.

distance error is only 21 meters. However, by basing nodes We give the measurement of effectiveness as a percentage

position calculations on 1- and 2-hop information, ANIML of the transmission range of the sensor nodes in the network.

can prevent the folding of neighborhoods and from getting Since ANIML produces relative localization, the deter-

stuck at a local optimum. Two-hop neighbor information mined network coordinates may have undergone a global

acts as a natural dampener to the localization process, slow- ip, rotation and/or shift making direct comparisons to the

ing down the changes of nodes in each iteration. This al- actual coordinates dif cult. Therefore, comparisons are

lows neighborhoods that would otherwise rapidly reach a done post localization by (i) shifting the real coordinates by

local optimum extra time to receive additional information the difference between the origin and the reference node s

that could prevent it from getting stuck. Fig. 2(b) shows true position, (ii) globally rotating both the real and relative

the same topology as Fig. 2(a) localized by ANIML using coordinates to place node 1 on the y-axis and (iii) if needed,

1- and 2-hop neighbor information. The localization has an ipping the relative set of coordinates to place them in the

average localization error of only 8 meters with an average same coordinate space. No scaling of position estimates is

pairwise distance error of 3 meters. involved in this transformation.

Even after introducing signi cant ranging error in the 2- Providing only 1-hop neighbor information to ANIML

hop neighbor distances, due to triangular inequality, the it- can lead to poor overall localization due to neighbors get-

120 100

ANIML (1hop/400) ANIML (400)

ANIML (1hop/800) DV-Hop (5/400)

ANIML (2hop/400) DV-Hop (10/400)

ANIML (2hop/800)

100

Inaccuracy (% of transmission range)

0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Network Area (square kilometers) Network Area (square kilometers)

Figure 3. 1-Hop ANIML vs. 2-Hop ANIML Figure 4. Localization in Uniform Topologies

Our future work on ANIML focuses on further reducing the

ting stuck at local optima. Fig. 3 shows the localization ef-

message complexity without sacri cing accuracy or conver-

fectiveness of ANIML using 1-hop information compared

gence time and implementing it on actual sensor motes. We

to ANIML using 1- and 2-hop information. The data points

are also adapting ANIML to address localization in three

are shifted slightly left and right of the real values (0.0625,

dimensional sensor networks.

.25, .5625, 1) on the x-axis to allow for clear presentation

of the error bars. Fig. 3 shows that ANIML using 1- and

References

2-hop information provides better overall localization ac-

curacy than ANIML using only 1-hop information. More

[1] T. Adebutu, L. Sacks, and I. Marshall. Simple position esti-

importantly, the results also show that the problem with us-

mation for wireless sensor networks. In Proc. of LCS 2003.

ing only 1-hop information is not necessarily the accuracy, [2] S. Capkun, M. Hamdi, and J.-P. Hubaux. GPS-free position-

but the consistency of localization. By simply adding 2- ing in mobile ad-hoc networks. In HICSS-34, 2001.

hop information, ANIML is able to signi cantly improve [3] L. Doherty, K. Pister, and L. El Ghaoui. Convex position es-

the consistency of its localization results, as can be seen by timation in wireless sensor networks. In Proc. of INFOCOM

2001, volume 3, pages 1655 1663.

the much tighter error bars.

[4] D. K. Goldenberg, P. Bihler, M. Cao, J. Fang, B. D. O. An-

Fig. 4 shows the localization effectiveness of ANIML

derson, A. S. Morse, and Y. R. Yang. Localization in sparse

and DV-Hop in uniform topologies. For clarity we only

networks using sweeps. In MobiCom 2006, pages 110 121.

present the 400 nodes/km2 results, naturally as density in- [5] J. Hightower and G. Borriello. A survey and taxonomy of lo-

creases so does accuracy. The results show ANIML pro- cation systems for ubiquitous computing. Technical report,

vides more accurate localization than DV-Hop. As a com- Univ. of Washington.

parison, ILS s localization effectiveness, based on the au- [6] J. Liu, Y. Zhang, and F. Zhao. Robust distributed node local-

ization with error management. In Proc. of MobiHoc 2006,

thors results presented in [6], is approximately 20%. More

pages 250 261.

importantly, the results show ANIML does not need any an-

[7] M. Medidi, R. Slaaen, Y. Zhou, C. Mallery, and S. Medidi.

chors to provide accurate localization.

Scalable localization in wireless sensor networks. In Proc.

of HiPC, LNCS 4297, pages 522 533, 2006.

5 Conclusions & Future Work [8] D. Niculescu and B. Nath. Ad hoc positioning system

(APS). In GLOBECOM 2001, volume 5, pages 2926 2931.

[9] D. P. Robinson and I. W. Marshall. An iterative approach to

We have presented ANIML, an iterative, anchor-free, locating simple devices in an ad-hoc network. In Proc. of

range-aware relative localization technique for wireless sen- LCS 2002.

sor networks that requires no explicit error control or global [10] Y. Sang and W. Ruml. Improved MDS-based localization.

information. By explicitly basing a nodes positioning off In Proc. of INFOCOM, volume 4, pages 2640 2651, 2004.

[11] Y. Sang, W. Ruml, and Y. Zang. Localization from mere

of its 1- and 2-hop neighborhood, instead of just its 1-

connectivity. In Proc. of MobiHoc, pages 202 212, 2003.

hop neighborhood, ANIML is capable of providing accu-

[12] A. Savvides, H. Park, and M. Srivastava. The bits and ops

rate localization, even in the presence of packet losses, us-

of the n-hop multilateration primitive for node localization

ing nothing more than simple iterative least-squares. While problems. In Proc. of ACM WSNA, pages 112 121, 2002.

adding 2-hop information does slightly increase the com- [13] M. Wong and D. Aksoy. Relative accuracy based location

putational complexity of ANIML s least-squares multilater- estimation in wireless ad hoc sensor networks. In Proc. of

ation by a constant factor, using 1- and 2-hop information ICC 2007.

[14] S. Yang, J. Yi, and H. Cha. HCRL: A hop-count-ratio based

allows ANIML the ability to provide resilient localization.

localization in wireless sensor networks. In SECON 2007.

Through simulation, despite using a non-idealized MAC,

[15] J. Yi, S. Yang, and H. Cha. Multi-hop-based monte carlo

we showed that ANIML provides good relative localization

localization for mobile sensor networks. In SECON 2007.

and better accuracy than DV-Hop in uniform topologies.

Contact this candidate