Friendly Anchor Based Range Free Localization (FABL) in
Anisotropic Wireless Sensor Network
Anup Kumar Paul,1 Yanwei Li,1 and Takuro Sato1
11Graduate School of Global Information and Telecommunication Studies, Waseda University, Nishi waseda, Shinjuku,
Tokyo 169-0051, Japan

Introduction

The accurate distance estimation between anchor nodes
and sensor nodes based on the hop count information is
an important research problem in Wireless Sensor Networks (WSNs). The location information is indispensable
in topology control, geographic routing protocols and clustering [1]. In anisotropic network where the transmission path between anchor nodes and sensor nodes is notstraight but curved, Euclidean distance between a pair ofsensor nodes is not always proportional to their hop countdistance, which undermines the assumption of many existing range free localization algorithms. Most of the existing works focus on increasing the accuracy by using theheuristics or mathematical techniques. In this paper, weshow that the selection of some good anchor nodes (which
we call friendly) instead of using all the anchor nodes for
accurate localization is a very important factor especiallyin anisotropic network. we devised the method of selecting friendly anchor nodes for each sensor node in orderto get accurate localization. Compared with the existing
approach, our approach does not require global knowledgeof network topology for boundary recognition nor uniform
distribution of anchor nodes. Therefore our approach is robust and applicable in practical environments. Extensive
simulations are performed and comparative studies withthe state-of-the-art hop-count based localization methods
show that the proposed approach is superior.
2Related Work

Many range free approaches have been proposed to determine sensor locations in WSNs. DV-Hop [2], employing
a constant number of anchors. The system estimates theaverage distance per hop from anchor locations and thehop count among anchors. Each node measures the hopcount to at least 3 anchors and translates these into distances. By triangulation, the location is then calculated.
APIT [3] lets each node estimate whether it resides insideor outside of several triangular regions bounded by theanchors and refines the computed location by overlapping
the regions a sensor could possibly reside in. For accuracy,
APIT needs many anchors and assumes that the anchors
have radio ranges that are 10 times larger than those of ordinary nodes. Another pattern driven localization scheme
is proposed in [4] to tolerate network anisotropy. The paper proposes three different methods of anchor-sensor distance calculation based on three patterns. Another work
solves the localization problem in a centralized mannerby using optimization techniques such as convex optimization [5]. However distributed localization systems such asFig. 1. Friendly anchor selection strategy in a simple scenario with an obstacle inside[6] are most likely to be used in WSNs.
3

Proposed Method

We consider one simple anisotropic scenario as shownin Fig. 1. The anchor nodes are denoted by Ai , wherei = {1, 2, . . . , 6}, and sensor nodes are denoted by Sj ,where j = {1, 2, . . . , 14}. To determine the friendly anchor
sets, we utilize the angle of the curved transmission path
between anchors and based on the small value of angle, theanchors are sorted in ascending order and the friendly anchors are on top of the sorted list. To determine the angleof the curved transmission path , we present one example
as follows:
Suppose the anchor nodes A′i s positions are (15, 20),
(5, 35), (30, 5), (40, 20), (36, 33) and (5, 10) respectively.
The Euclidean distance between anchor node A1 and A2is 18 (approximately), A1 and A3 is 21, A1 and A4 is 25,
A1 and A5 is 24 and A1 and A6 is 14. The corresponding
hop count is 3, 3, 6, 4 and 2 respectively. Then A1 cancalculate its Average Hop Distance (AHD) as follows:
AHDA1 =

18 + 21 + 25 + 24 + 14
= 5.72
3+3+6+4+2

After calculating the average hop distance, it can calculate the transmission path distance by multiplying AHDA1and the number of hop between A1 and other anchors. For
example, the transmission path distance between A1 andA4 is 5.72 × 6 = 34.32, which is greater than the Euclidean
distance (25) between them. So A1 can assume that, thetransmission path is not straight but curved. To calculate
the angle, of the curved transmission path, we draw theline A1 H from A1 to H and draw another line from A4 toH in such a way that, the triangle A1 A4 H is a right angle
triangle. The length of the line A1 H is equal to the lengthof the transmission path, i.e., in our example, 34.32. The
angle of the curved transmission path is θ. From triangle
A1 A4 H, we know that,
1,4A1 H

987
6
5
43(1)

where D1,4 is the Euclidean distance between Anchor A1and A4 . From (1), anchor A1 can calculate the curvedangle θ.
In a similar way A1 can calculate the angle between A1and A5 and so on. If the transmission path is less than orequal to Euclidean distance, then the value of θ is set to0o . After calculating all the angles, A1 then sort the angles
in ascending order. The purpose of sorting in ascendingorder is to make sure to put the unfriendly anchors in thelast of the list. After sorting the anchor sets, each anchor will broadcast the average hop distance and the ID offirst eight anchors in the sorted list, i.e., friendly anchors.
We choose the threshold eight since eight is beneficial tomitigate the bad geometry effect of anchors [3].The sensor
node will receive such information from every anchor node
but will keep only that information which is coming fromnearby anchor node (in terms of hop number) and discard
all others. Because the friendly anchor sets of a nearby
anchor is the same as the friendly anchor sets of a nearby
sensor. Then each sensor will apply multilateral mathod
to calculate its location.

2100246810Fig. 2. Initial node deployment in anisotropic C-shapenetwork.
The average localization error Graph, Sensor Density=81DVHOPPattern−DrivenFABL

0.9

0.8

Average Localization errorθ = cos−1DThe nodes initial position, Sensor Density=810

0.7

0.6

0.5

0.4

0.3

0.2

0.1

020

2530

3540

45

50

55

60

65

No of Anchor nodes: [Anisotropic C−Shape Network]

Fig. 3. Location error vs. number of anchor nodes.
4Simulation Results and Performance Analysis

To evaluate the performance of our proposed scheme inanisotropic WSNs, where anchor nodes are deployed randomly and a series of simulations are conducted. We simulate in C-shape anisotropic network as shown in Fig. 2.
We perform 25 rounds of running the simulation and takethe average over 25 runs, during which the quantity of the
deployed sensors nodes are kept unchanged. However, thetopology of the network varies because we establish connectivity between pair of sensor nodes randomly. To measure the accuracy of localization, the average localization
error is used. We consider 10m × 10m network area, 200
sensor nodes, 20 anchor nodes and radio range of sensor
and anchor nodes are set to be 2m.
As can be seen from Fig. 3 that in anisotropic network
condition our proposed algorithm perform better than [2]and [4]. This is because the transmission paths are morecurved and our proposed algorithm carefully select friendly
anchor nodes using angular information.
5Conclusion

In this paper we mainly focus on the impact of selecting good anchors, which is a critical factor for accurate
localization specially in anisotropic WSNs. However inanisotropic network the average hop distance is also a critical factor for accurate localization. This opens up a newchallege for creating an intelligent localization algorithm
which can calculate the average hop distance in detourtransmission path accurately and combine the anchor selection strategy for satisfactory localization accuracy will
be our future investigation.

References[1] A. K. Paul and T. Sato, “Effective data gatheringand energy efficient communication protocol in wireless sensor network,” in Wireless Personal Multimedia
Communication (WPMC’11), Brest, France, October
2011, pp. 1–5.
[2] D. Niculescu and B. Nath, “Dv based positioning in
ad hoc networks,” J. Telecommun. Syst., vol. 22, no.
1-4, pp. 267–280, January 2003.
[3] T. He, C. Huang, B. M. Blum, J. A. Stankovic, andT. Abdelzaher, “Range-free localization schemes forlarge scale sensor networks,” in Proc. of the ACM MobiCom 2003, San Diego, 2003, pp. 81–95.
[4] Q. Xiao, B. Xiao, J. Cao, and J. Wang, “Multihop
range-free localization in anisotropic wireless sensor
networks: A pattern-driven scheme,” IEEE Transaction on Mobile Computing, vol. 9, no. 11, pp. 1592–1607, November 2010.
[5] L. Doherty, K. S. Pister, and L. E. Ghaoui, “Convex
position estimation in wireless sensor networks,” IEEE
Conference on Computer Communications, vol. 3, pp.
1655–1663, April 2001.
[6] A. K. Paul, T. Muhammad, L. Yanwei, and T. Sato,“Range free angle calculation (rfac) based sensor localization in wireless sensor networks,” in International
Conference on Modeling and Simulation Technology,
JSST-2011, Tokyo, Japan, October 2011, pp. 5–8.