Wireless Netw DOI 10.1007/s11276-017-1538-6

Anchor node path planning for localization in wireless sensor networks Ketan Sabale1 • S. Mini1

Ó Springer Science+Business Media, LLC 2017

Abstract Localization is one of the most important challenges of wireless sensor networks because the location information is typically used in other domains such as coverage, deployment, routing, and target tracking. There exist some localization algorithms that facilitate the sensor nodes to locate itself using the mobile anchor node position. Some crucial attempts have been made in the past for optimizing the mobile anchor node trajectory with good accuracy. This paper presents a novel path planning scheme, D-connect, which ensures the localization of all the sensor nodes with minimum trajectory length. The performance of the proposed scheme is evaluated through a series of simulations. Experimental results reveal that the shortest path for traversing the whole area can be traced with the minimum localization error using this method. It also shows that D-connect outperforms the existing methods in terms of the anchor node trajectory length as well as the localization error. Keywords Sensor network  Localization  Anchor node  Path planning mechanisms

& S. Mini [email protected] Ketan Sabale [email protected] 1

Department of Computer Science and Engineering, National Institute of Technology Goa, Farmagudi, Goa, India

1 Introduction Wireless sensor networks (WSNs) are composed of large collection of sensors that may be randomly deployed in a certain geographical region. The sensor nodes collect environmental data and forward that data to a remote device where the data is analyzed and processed. If the sensors cannot pass the information to the remote device directly, some intermediate nodes have to forward the data [8]. Sensor networks have a wide range of application areas such as home, environment monitoring, military surveillance, animal tracking, etc. WSNs can be used in the disaster relief services where human operations are difficult. Increased accuracy and minimizing time for location estimation are the important factors to be considered in emergency services. Sensor nodes have limited power resources, computational power, and memory availability [1]. Coverage, deployment, tracking and localization are some challenges in WSNs. Since the location information is used in other domains, it is necessary to determine the origin of the information, prior to any information processing. Localization can be defined as estimating the exact physical location of the sensor node in a certain geographical area. Sensors can be located with the help of the Global Positioning System (GPS). Due to the high cost and poor performance of GPS indoors, it becomes inefficient to equip all sensor nodes with GPS [3]. There have been some localization algorithms that were proposed in the past, and are still being used to locate unknown sensors. The classification of localization algorithms along several axes is presented in Fig. 1. In centralized algorithms, the sensor nodes send their data to the central processing unit where the data is analyzed and processed to extract the positional information. The approach in which each sensor node can locate itself is

123

Wireless Netw Fig. 1 Classification of localization algorithms

known as distributed localization. The main advantages of the centralized approach is accuracy, precision and the ability to process greater amounts of data. The disadvantages of these algorithms are poor scalability and a single point of failure. The distributed algorithms do not require a central base station. In the distributed localization approach, localization is done through node-to-node communication. Localization which is carried out with the help of signal properties is known as Range-based localization [13]. The common techniques used in range-based localization are Angle of Arrival (AOA), Time of Arrival (TOA), Time Difference of Arrival (TDOA) and Received Signal Strength Indicator (RSSI). These localization algorithms are based on time and distance dependent measurements. In the Angle of Arrival (AOA) method, the location is estimated with the help of the angle at which a signal arrives at a sensor. Distance information is obtained in the Time of Arrival (TOA) and Time Difference of Arrival (TDOA) methods by computing the transmission time of the wireless signal. These approaches give better location accuracy but use extra hardware. Received Signal Strength Indicator (RSSI) is a measurement of the power present in a received signal. There is no requirement of extra hardware for estimating the distance using RSSI technique. Estimated distance travelled by the signal up to the receiver point is calculated with effective path loss. Range-free techniques do not need extra hardware but localization depends on the connectivity of the network. Localization based on range-free techniques in which the anchor node moves along a hexagonal pattern is discussed in [18]. Cost-effective ways of localization with less accuracy are provided by range-free techniques. The methods in which a sensor node can locate itself by using the location information of some specific nodes is known as Anchor-based approach. The position of Anchor nodes is predefined or can be located with the help of GPS. An anchor node is also referred to as a Beacon or a Reference

123

node. Anchor-free localization does not depend on the anchor nodes. In this approach, each node computes the relative coordinates by measuring the distance to its neighboring nodes by using either range-free or rangebased techniques. Usually WSN is used in remote geographical areas where human operations are impossible. It is infeasible to deploy beacons at known positions. So beacon nodes must be equipped with GPS receivers. Cost effective WSN is dependent on the minimum number of anchor nodes used. So the motivation behind designing the D-connect trajectory is to locate all the sensor nodes with the help of a single beacon node. The beacon node broadcasts its location information while travelling in the region of interest. Beacons do not broadcast constantly. Advertising Interval describes the time between each broadcast. Stability of the signal depends on the Advertising Interval. The signal is more stable for shorter intervals. It is very beneficial to use such anchor nodes for localization. The fundamental issue is to find an optimum path for a mobile beacon trajectory in the region of interest. Before defining any path planning mechanism, certain properties of optimum path planning mechanisms should be investigated. Due to the poorly designed trajectory, some sensor nodes may not be localized. The existing anchor node trajectories are different from one another in the pattern they follow. The Mobile Anchor Centroid Localization [8] traverses the region along a spiral path. Due to the spiral nature of the path taken by the anchor node, sensor nodes present in the corner of the network do not get sufficient number of beacon positions, which leads to an increase in the localization error. [9] presents the Hilbert curve approach that solves the localization and coverage problems. In this approach the unknown sensor estimates its position by using h keys. Scan and Double Scan [11] minimizes the anchor node trajectory length but increases the localization time as the

Wireless Netw

sensor has to wait for non collinear positions for location estimation. The Z-curve [10] follows the path in a Z pattern while LMAT [12] follows an equilateral triangle pattern. All these trajectories differ in terms of construction and work, but all try to achieve the same goal. To the best of our knowledge, no literature provides a sufficient and optimal trajectory to solve the problems of localization and coverage. In this paper, we propose a path planning scheme, D-connect, for anchor-based localization using a rangebased technique. It guarantees the localization of all unknown sensor nodes from a certain geographical region with minimized localization error. It uses two signals with two different transmitted signal powers which are required to increase the accuracy while taking care of the collinearity issue. For maximum accuracy, the anchor node has to travel near the boundary of the region. In D-connect, the increased power of the signal resolves this problem. For locating any unknown sensor accurately, at least three noncollinear beacon signals are required. If the sensor node receives more than three beacon node positions, at least one non-collinear position is required to eliminate any collinear beacon. The rest of the paper is organized as follows: Sect. 2 summarizes the related work on different existing localization algorithms and path planning mechanisms with more clarity. Section 3 defines the problem and describes the D-connect method. The experimental results are reported and discussed in Sect. 4. Sect. 5 concludes the paper.

2 Related work There have been several research efforts on tackling problems related to localization in WSN. The various hierarchical architectures of WSN are presented in [2]. Most existing localization schemes for WSNs are mainly classified into two groups, computation based and range based. A detailed classification is provided in [3]. Distributed computation based methods are discussed in [4, 5] and [6]. The Monte-Carlo Localization algorithm is presented in [4]. The Monte-Carlo algorithm estimates the position of an unknown sensor by considering the near and the farther anchor node constraints. At first, the sensor node constructs a possible location set which denotes the possible location of the sensor. In the filtering phase the locations which are not satisfying the anchor node constraints are removed and the average of the remaining location set gives the final estimated location of the unknown node. The efforts for increasing the efficiency of the Monte-Carlo algorithm are done in [5]. Drawing samples is a time consuming process, so Monte-Carlo

Localization Boxed algorithm constrains the area from which the sensor draws samples. This method is known as Monte-Carlo Localization Boxed (MCB) algorithm. The increased accuracy and reduced localization time can be obtained by using relay nodes. Self Localization Scheme using relay nodes and anchor nodes is presented in [6]. Relay nodes are also sensor nodes which get their positional information from the anchor node. Sensor nodes calculate their position by the received information about the relay node position. The various conditions for relay node selection are discussed in [6]. The efficiency of anchor based localization algorithms is dependent on the trajectory of the anchor node. For defining any new beacon node trajectory certain conditions must be satisfied by the trajectory. First of all, trajectory should pass closely to the unknown sensor for best position estimation. Also each sensor node should have at least three non-collinear anchor node positions to locate itself. [7] illustrates the conditions that are to be satisfied by the anchor node trajectory. The various schemes to reduce the trajectory length of the anchor node are discussed in [8–11] and [12]. [8] presents the trajectory in a spiral form. The position estimation of sensor nodes is done with the help of the range-free localization technique called Centroid algorithm. The position of each sensor is calculated by taking the average of the total received beacon messages in the time interval t. The length of the Spiral trajectory is more than all other trajectories. The localization algorithm that uses the Spiral trajectory is known as the Mobile Anchor Centroid Localization (MACL). The trajectory based on the Hilbert space filling curve is presented in [9]. The Hilbert space filling curve is a one-dimensional curve, which visits every point exactly once without crossing itself within a two or three-dimensional space. The Hilbert curve is generated recursively. A superior path planning mechanism called Z-curve is explained in [10]. Z-curve handles the collinearity issue occurring in the anchor node trajectory by using the determinant of the matrix that contains consecutive beacon positions received by the sensor node. The received beacon positions are said to be non-collinear if the determinant of the matrix is non-zero. The Z-curve trajectory is tested for an obstacle presence scenario. Scan and Double Scan methods are explained in [11]. The Scan method has the disadvantage of collinearity. In the Scan method, the mobile beacon node travels along one dimension and when it reaches the end of the network it travels along the second dimension where the length of the path along the second dimension is equal to the resolution. The procedure is repeated till the entire network is traversed. The Double Scan method traverses the network along both directions. The collinearity problem of the Scan method is resolved by the Double Scan strategy up to some extent. But the length of the Double Scan trajectory is

123

Wireless Netw

double, compared to the Scan mehod for the same resolution. The Hilbert curve method overcomes the disadvantages of the Scan and Double Scan methods. Since the Hilbert curve trajectory takes more turns, it gives better position estimation compared to the Scan and Double Scan trajectories. As Hilbert curve connects the centers of two successive cells in the network, it will never move along the border of the deployment area. This is a drawback of the Hilbert curve method. Localization with a Mobile Anchor node based on Trilateration (LMAT) is presented in [12]. In LMAT trajectory, an anchor node moves along the boundaries of the region based on an equilateral triangle pattern. After designing the optimum trajectory for an anchor node, the next main task is to estimate the physical position of the unknown sensor nodes using anchor node positions. For estimating the position of an unknown node various range-free and range-based methods can be used. The range-free and range-based techniques are discussed in [13]. The cost effective method in range-based localization algorithm called RSSI is presented in detail in [14] and [15]. Distance estimation using RSSI is dependent on path loss. Various propagation models for mobile communication are discussed in [16]. Path loss and fading are the main characteristics of the radio channel. The RSSI calculations are basically influenced by path loss and fading. Free space model, Two ray ground model and Log-normal shadowing model are the RSSI propagation models used in wireless sensor networks. When the transmitter and receiver have a clear unobstructed line of sight between them, the free space propagation model is used [16]. The Two ray ground model is considered only when there exists a single direct path between the transmitter and the receiver for the propagation of the radio signal. The directed path and a ground reflected propagation between the transmitter and the receiver is considered in two ray propagation model. The Log-normal shadowing model is the most suitable radio propagation model as it provides a number of parameters for configuration for different environments (indoor and outdoor). This study mainly focuses on the development of optimal anchor node trajectory for localization of unknown sensors using the Log normal shadowing model.

3 Proposed work 3.1 Problem statement Given a geographic region R, and a single anchor node A to locate m sensor nodes S ¼ fS1 ; S2 ; S3 ; :::; Sm g, the objective is to identify the minimum length trajectory for anchor node A, such that all unknown sensor nodes are located with minimum localization error.

123

If the mobile anchor node A, is at position ðx1 ; y1 Þ and the sensor node Si , ð1  i  mÞ is at location ðx2 ; y2 Þ then A can locate sensor Si iff sensor node Si lies within the communication range r of A. That is, qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ð1Þ ðx1  x2 Þ2 þ ðy1  y2 Þ2  r where r is the communication range of anchor node A. Let (X, Y) and ðxi ; yi Þ represent the estimated and original coordinates of sensor Si , respectively. Then the localization error is calculated by, qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ð2Þ ErrorSi ¼ ðX  xi Þ2 þ ðY  yi Þ2 The average localization error for all unknown sensors is calculated by, Erroraverage ¼

n X ErrorS

i

i¼1

m

ð3Þ

where m denotes the total number of unknown sensors deployed throughout the region. 3.2 Mobile beacon node trajectory The proposed strategy, D-connect, assumes that the anchor node can transmit different signals with different power from predefined points to overcome the collinear beacon problem and creates an optimum path for traversing the region in order to reduce the localization time. As D-connect trajectory is deterministic and the anchor node positions for message transmission are already known, the anchor node can send the signal with more power from some fixed positions. The basic curve of the trajectory is shown in Fig. 2. The region is divided into sub-squares based on the level. The concept of level is used in such a way that for level n, the region is divided into 4n sub-squares. The mobile anchor connects the centres of the sub-squares such that it will form D-connect trajectory. The centres of the sub-squares are c1 ; c2 ; c3 . The sub-squares are named as Sq1, Sq2 and Sq3 respectively. The level 3 and 4 are illustrated in Figs. 3 and 4 respectively. The resolution of a trajectory is equal to the length of the side of each sub-square. The resolution is given by l=2n , where l is the length of the geographical region. The D-connect anchor node trajectory construction is divided into 3 phases: – – –

Phase 1: Localizability relation Phase 2: Communication range definition Phase 3: Non-collinearity checking

Localizability Relation phase mainly focuses on deriving the relation for locating unknown sensors with the help of anchor node positions. Communication Range phase

Wireless Netw Fig. 2 D-connect travelling mechanism

Fig. 3 D-connect travelling mechanism

Fig. 4 D-connect travelling mechanism

defines the communication ranges for different anchor node positions. For estimating the sensor node position, at least three non-collinear anchor node positions are required. The obtained positions are checked for collinearity in Non-Collinearity Checking phase. –

Localizability relation All unknown sensors are localizable only if:

8si ði¼1;::::;nÞ 9faj ðj ¼ 1; 2; 3Þjðdistðaj ; si Þ  r1 Þ Vðdistðaj ; si Þ  r2 g where si denotes unknown sensors and aj denotes the anchor node messages which have been transmitted from three different positions. r1 and r2 are communication ranges from two different positions. distðaj ; si Þ

123

Wireless Netw

–

r1 is the distance between c3 and s1 . From this we can say that the unknown sensor can receive the beacon position qffiffi from an adjacent sub-square centroid only if r1  52d.

indicates the distance between the unknown sensor and the anchor node position. Communication range definition To locate any unknown sensor, the first requirement is that the unknown sensor should receive an anchor node position. The unknown sensor can receive a beacon position only if it is within the communication range of the beacon node. The communication range of the beacon node should be adjusted in such a way that all unknown sensors are covered. Each sub-square has resolution d. To obtain three beacon node positions, it is required that the unknown sensor should receive the beacon node position from the same square or from adjacent sub-squares whichever is nearer.

Sometimes the beacon positions from adjacent subsquares are not sufficient. To receive three beacon messages and also to complete D-connect trajectory, we need the third beacon position from another sub-square, other than the same sub-square and the neighboring one. Let s2 be the most distant sensor from c4 which is not in the neighboring sub-square. If s2 receives beacon message from c4 then s2 can receive beacon messages from subsquares other than adjacent sub-squares. Applying Pythagoras theorem as shown in Fig. 5, r22 ¼ðdÞ2 þ ð2dÞ2 pffiffiffi r2 ¼ 5d:

The sub-squares with centres at distance d from the considered sub-square are called adjacent sub-squares. For example, c7 and c8 in Fig. 5 are the centres of adjacent subsquares. This phase defines the communication range for different anchor positions. In Fig. 5, let s1 denote the most distant sensor from c3 which is the centroid of the neighbor sub-square. If s1 receives beacon message from c3 then s1 can receive beacon messages from all adjacent sub-squares. According to the Pythagoras theorem, in Fig. 5, d 3d r12 ¼ ð Þ2 þ ð Þ2 2 2 rffiffiffi 5 r1 ¼ d: 2

ð5Þ

r2 is the distance between c4 and s2 . From this we can say that an unknown sensor can receive a beacon position from a sub-square other than the adjacent sub-squares only if pffiffiffi r2  5d. The anchor node positions with communication range r2 are fixed as the movement and beacon positions for message transmission are already known and the D-connect trajectory is deterministic. The transmitted signal power is varied as a function of distance. The transmitted signal power for the points using r2 communication range increases as the ratio r1 to r2 increases. Thus, the transmitted signal power for the communication range r2 is 1.41 times transmitted signal

ð4Þ

c10

c

14

c

c

c9

11

13

c

12

c

8

3d/2 s1

d/2

r1

c7

c

3

c4

c

2

c

6

r2 c

1

d

s2 2d

Fig. 5 Communication range definition for an anchor node

123

c

5

Wireless Netw

power of the communication range r1 . The communication range depends on the resolution d. – Non-Collinearity Checking As shown in Fig. 5, any unknown sensor can use the beacon message from the intersection of sub-squares eg. c2 ; c4 ; :::. After receiving three beacon messages collinearity condition should be checked to eliminate the third collinear point. The three coordinates are collinear if they lie on the same line.

Table 1 Path loss exponents for different environments [17]

Let MAT represent a matrix formed by the coordinates of the three received beacons ðxc1 ; yc1 Þ,ðxc2 ; yc2 Þ,ðxc3 ; yc3 Þ from positions c1 ; c2 and c3 .   y c 2  y c1 x  x c1 MAT ¼ c2 ð6Þ x c3  x c1 y c 3  y c1 The three received beacons are non-collinear, when jMATj ¼ ðxc2  xc1 Þðyc3  yc1 Þ  ðyc2  yc1 Þðxc3  xc1 Þ 6¼ 0 ð7Þ where jMATj represents the determinant of matrix MAT. The total length of the trajectory is determined by adding the length of the segments connecting the non adjacent sub-square centres (c1 and c2 in Fig. 5) and the length of segments connecting the adjacent sub-square centres (c7 and c8 in Fig. 5). The total number of segments connecting the non-adjacent sub-squares in one-side traversing from c1 to c7 is ð2n  1Þ. The total number of such one-sided traversals in the whole region is ð2n1 Þ. The length of an individual segment connecting two non-adjapffiffiffi cent sub-squares is ð 2  dÞ. The total number of segments joining adjacent sub-squares having length equal to resolution (d) is ð2n1  1Þ. Therefore the total length of the D-connect trajectory is given by, pffiffiffi DDconnect ¼ ð2n  1Þð2n1  2  dÞ þ ðð2n1  1Þ  dÞ ð8Þ

Environment

Path loss exponent(g)

Free space

2

Urban area cellular radio

2.7–3.5

Shadowed urban cellular radio

3–5

In building line-of-sight

1.6–1.8

Obstructed in building

4–6

Obstructed in factories

2–3

loss exponent increases with obstructions in the environment. The path loss exponent value lies between 2 and 6. The random variation in RSSI is modeled as a Gaussian random variable Xr ¼ Nð0; r2 Þ. The values of g and r can be set depending on the propagation environment. Table 1 lists path loss exponents for various mobile radio environments. The value for shadowing deviation rdB is different for different environment. It ranges from 4 to 12 for outdoors. For every unknown sensor, after getting sufficient distances between unknown sensor and beacon positions, the triangulation method is used to obtain the possible location for the unknown sensor. In Fig. 6, let s be the unknown sensor to be localized. a1 ; a2 and a3 are the three non-collinear anchor node positions. Let d1 ; d2 ; d3 denote the euclidean distances between anchor node positions a1 ; a2 and a3 and the sensor node. ðx1 ; y1 Þ; ðx2 ; y2 Þ; ðx3 ; y3 Þ are the known anchor node positions. The possible coordinates for sensor s can be obtained by [6], ðy2  y1 Þc  ðy3  y2 Þe 2ððx2  x1 Þðy3  y2 Þ  ðx3  x2 Þðy2  y1 ÞÞ ðx2  x1 Þc  ðx3  x2 Þe Y¼ 2ððx3  x2 Þðy2  y1 Þ  ðx2  x1 Þðy3  y2 ÞÞ

X¼

where DDconnect represents the total length travelled by the D-connect strategy for level n and resolution d. 3.3 Location estimation After receiving three non-collinear beacon positions, the location estimation is to be done using the RSSI technique. In a realistic channel model like log normal shadowing, the RSSI value at a distance d from the transmitter is given by [15], RSSIðdÞ ¼ PTrans  PLðd0 Þ  10g log10

d þ Xr d0

ð9Þ

where PTrans is the transmission power of the signal at the source, PLðd0 Þ is the path loss at a reference distance (i.e. d0 ), and g is the path loss exponent. The value of the path

Fig. 6 Localization of a sensor node using triangulation

123

Wireless Netw

where c ¼ ðx22  x23 þ y22  y23  d22 þ d32 Þ and 2 2 2 2 2 2 e ¼ ðx1  x2 þ y1  y2  d1 þ d2 Þ Let (X, Y) and ðxi ; yi Þ represent the estimated and original coordinates of sensor Si , respectively. Based on the calculated position, the localization error is calculated by (2). The average localization error for all unknown sensors is calculated by (3).

Table 3 Trajectory length comparison for 100 m  100 m region Level (n)

Res.(d)

LMAT

Spiral

Scan

D-connect

2

25

514.8

1495.9

375

237.1

3

12.5

827

2611.7

787.5

532.4

4

6.25

1387.3

4100.4

1593.8

1104.4

5

3.12

2533.4

7161.5

3196.9

2238.9

6

1.56

4838.5

13345

6398.4

4503.2

4 Results and discussion Table 4 Trajectory length comparison for 100 m  100 m region

The performance of the proposed trajectory was evaluated by a series of simulations using MATLAB. The parameters are listed in Table 2. We consider a 100 m100 m grid for experimentation. The number of sensors to be localized are 100 with the help of a single anchor node. The communication range of the anchor node varies with respect to resolution (d). The resolution depends on the level (n). For experimental results for all trajectories except qffiffi D-connect the communication range is set to r ¼ 52d. This communication range varies with resolution. D-connect uses two communication ranges r1 and r2 from equation 4 and equation 5 respectively. The transmitted signal power for r2 is 1.41 times r1 as the transmitted signal power is a function of distance. Other trajectories have transmission power equal to the transmitted signal power for r1 . Path loss exponent is taken as 3.3 for shadowed urban cellular radio network. The standard deviation for noise is taken from 2 to 8. Path loss PL ðd0 Þ at a reference distance 1 meter is considered as 55 dB. Results are reported as an average of 50 different instances. The length of geographical region is considered as 100 m. The communication range depends on the resolution and level. The resolution corresponding to specified level is shown in Tables 3 and 4. The results for trajectory length have been evaluated for each level. The trajectory length

Table 2 Simulations parameters Parameter

Value

Network size

100 m100 m

Unknown sensors

100

Beacon nodes

1

Path loss exponent(g)

3.3

Standard deviation

2,4,6,8

PL ðd0 Þ

55 dB

d0

1m

Transmission power

-28–14.1 dBm

Simulation runs

50

123

Level (n)

Res. (d)

Double scan

Hilbert

Z-curve

D-connect

2

25

758.8

375

437.1

237.1

3

12.5

1579.4

787.5

911.7

532.4

4 5

6.25 3.12

3189.7 6394.9

1593.8 3196.9

1842.3 3693.9

1104.4 2238.9

6

1.56

12797

6398.4

7392.6

4503.2

for an anchor node in LMAT, SPIRAL algorithms are calculated respectively as [12] pffiffiffi 2 L DLMAT ¼ pffiffiffi  L  d e þ ðL þ 3rÞ ð10Þ r 3 L

DSpiral

d r e pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi X ¼ r 2 þ 4r 2 p2 t2 þ 4r 2 t sin 4pt

ð11Þ

t¼1

where r is the communication range and L is the length of the geographical region. The Scan trajectory consists of ðLd  1Þ segments of length L parallel to the x axis and ðLd  1Þ segments of length d parallel to the y axis as shown in Fig. 7. The trajectory length for the Scan algorithm is given by,     L L 1 Lþ 1 d ð12Þ DScan ¼ d d   L  1  ðL þ dÞ ð13Þ DScan ¼ d Basically the Double Scan trajectory doubles the distance travelled by the Scan trajectory. The Double Scan trajectory is presented in Fig. 8. The total length for Double Scan trajectory is given by,    L DDoubleScan ¼ 2  1  ðL þ dÞ þ T ð14Þ d where T is the turn taken by the anchor node when it pffiffiffi completes one Scan trajectory. In this case T ¼ 2  d4. A hybrid localization approach explained in [9] uses the Hilbert curve mechanism for the anchor node trajectory as shown in Fig. 9. In the Hilbert curve method, the region is divided into 4n square cells. The anchor node connects the

Wireless Netw Fig. 7 Scan travelling mechanism

100

90

80

70

60

50

40

30

20

10

0 0

Fig. 8 Double scan travelling mechanism

10

20

30

40

50

60

70

80

90

100

10

20

30

40

50

60

70

80

90

100

100

90

80

70

60

50

40

30

20

10

0 0

centres of these cells by using ð4n  1Þ lines of length equal to the resolution d. The travelling length of the Hilbert trajectory is given by, DHilbert ¼ ð4n  1Þ  d

ð15Þ

The total distance travelled by the anchor node using Zcurve trajectory is given by [10], pffiffiffi 5 3 DZcurve ¼ dð  4n Þ  1ed þ bð  4n Þc 2d 8 8

ð16Þ

Table 3 shows the path length comparison for LMAT, Spiral, Scan and D-connect strategies. Table 4 compares the path length for Double Scan, Hilbert, Z-curve and D-connect strategies. From Tables 3 and 4, we deduce that when the level is 2, resolution i.e. the length of the subsquare will be 25 m. At this resolution, the path length travelled by an anchor node using LMAT strategy is 514.8 m whereas the Spiral strategy takes 1495.9 m to complete

the trajectory. Although the Scan method gives better results as compared to the Spiral and LMAT methods, it still suffers from the collinearity problem for high resolution. It gives three collinear beacon points for localization. The Double Scan strategy resolves the collinearity problem faced by the Scan method but it also increases the path length. The Hilbert and Z-curve methods take 375 and 437.13 m to complete their trajectories respectively. However, they also take more path length as compared to the D-connect trajectory. As the level increases, the resolution decreases. At level 3, resolution will be 12.5 m. The path length taken by the D-connect method is still less compared to all other strategies. Small resolutions result in more path length which is unacceptable for a 100 m 100 m area. The Spiral trajectory length is always more than any other trajectory. The results over other methods show the efficiency of D-connect in terms of the trajectory length.

123

Wireless Netw 100

90

80

70

60

50

40

30

20

10

0 0

10

20

30

40

50

60

70

80

90

100

Fig. 9 Hilbert travelling mechanism

In a real time environment, the resolution for a grid is considered by the power of a transmitted signal. For high resolution, transmission power should be more. Given a 100 m100 m region, with small resolution, if the trajectory length exceeds 2000 m then it will not be an efficient trajectory. As we have power constraints, it is always a good choice to keep resolution high with respect to the power of the transmitted signal. While traversing the region, the beacon node periodically transmits a position message packet with its coordinates. In Scan, Double Scan and Hilbert strategies, an unknown sensor node receives three message packets that are transmitted from three different beacon positions and using those positions, the unknown sensor node calculates the position using the centroid method. We estimate the position of the unknown sensor in the D-connect method using the RSSI technique. Figure 10 represents the comparison of the localization error for the Scan, Double Scan, Hilbert, Z-curve and D-connect strategies. The localization error depends on the environment and reliable wireless communication devices. In a real time environment, various multipath fading factors cause large random signal variations. We have done simulations to calculate the localization error for the communication range 4.93–39.53 m for regular anchor node positions. At the same time, the communication range for special anchor node positions varies from 6.98 m to 55.90 m. Figure 10 shows the localization error for different strategies for standard deviation 2. The average localization error produced by the D-connect trajectory after 50 simulation runs for level 2 is equal to 0.8315 m. The

123

localization error decreases as the level increases. Similarly when the resolution of the grid is 12.5 m, the localization error produced by the D-connect method is 0.3307 m. The localization error produced by the D-connect strategy is 0.0698 m when the resolution is small (d\5 m). The localization errors for Scan, Double Scan and Hilbert trajectories are more than the D-connect trajectory error for level 2. They are 9.16, 6.7157 and 9.15 m respectively. For Z-curve, the error is less than D-connect and all other trajectories but the length of the Z-curve trajectory is more than the D-connect trajectory length. Z-curve gives 0.4256 m error for level 2 and gives 0.0430 m for level 5. The difference between the errors produced by D-connect and Z-curve decreases as the communication range increases. Figure 11 presents the localization error comparison for standard deviation 4. For r ¼ 4, the error produced by D-connect is still less than Scan, Double Scan and Hilbert trajectories. When standard deviation of noise is equal to 4, the localization error for D-connect trajectory is 0.6738 m and error for Scan, Double Scan and Hilbert trajectories are 3.6264, 2.9025 and 3.6377 m respectively. The error for Scan, Double Scan and Hilbert strategies decreases as the level increases. The Scan, Double Scan and Hilbert strategies have collinearity problem. For large resolution an unknown sensor may get collinear beacon node positions for location estimation. The value of localization error increases if the sensor gets collinear beacon positions. The collinearity issue is handled by increasing the level and decreasing the communication range. When the communication range is less, the sensor may get non-collinear beacon positions as it may receive more number of beacon node positions. If any of the unknown sensors get the collinear beacon positions for location estimation, it affects the average localization error. The performance of the Scan, Double Scan and Z-curve increases with reduction in communication range. D-connect and Z-curve methods resolve the problem of collinearity before position estimation. Because of the collinearity checking done by D-connect and Z-curve trajectories, the performance of these trajectories is always better than the others. The trajectories considered for evaluation performs better for small resolution than for large resolution. Figure 12 gives the comparison for localization error when r ¼ 8. The performance of Scan, Double Scan, Hilbert strategies does not depend on the standard deviation of noise. These trajectories estimate the position of an unknown sensor by taking the average of the three received beacon positions. Techniques which use RSSI calculations for position estimation depend on the noise produced in the environment. The accuracy of the position estimation depends on the quality of the signal. The quality of the signal degrades as noise in the environment increases. The

Wireless Netw Fig. 10 Level versus localization error (r ¼ 2)

Fig. 11 Level versus localization error (r ¼ 4)

performance of D-connect decreases for standard deviation of noise equal to 8. For communication range 39.53 m, Dconnect produces 3.3336 m error which is greater than the error produced for small values of r for the same communication range. With the same conditions Z-curve produces 1.7272 m error while Scan, Double Scan and Hilbert trajectories gives 9.3990, 6.7174, 9.3924 m respectively. If we increase the level, the communication range decreases. This increases the performance of all trajectories. For level 3 with communication range 19.76 m, the errors produced

by D-connect, Scan, Double Scan, Hilbert and Z-curve methods are 1.2947, 3.6095, 2.8867, 3.6043 and 0.7779 m respectively. The Z-curve gives better performance in terms of minimum localization error as compared to D-connect and all other trajectories, but the length it takes for completing the trajectory is 911.7 m which is almost 380 m more than that taken by the D-connect method. The error produced by the following D-connect trajectory is about 0.50 m more than the Z-curve trajectory, but the length of trajectory decreases by about 380 m.

123

Wireless Netw Fig. 12 Level versus localization error (r ¼ 8)

D-connect trajectory is susceptible to noise like other methods. However it consistently gives better results in terms of localization error. Figures 10, 11 and 12 show that D-connect performs more efficiently than all other methods in terms of length and localization error. A relay node can be used to propagate beacon node positions to sensors for minimizing the trajectory length. But D-connect achieves the same goal by varying the transmitted signal power. Simulations are done for regular regions that can be divided in the grid. It is necessary to partition the region in equal parts to fix the communication range. For irregular regions, results may differ based on how the regions can be divided. Thus, it is challenging to adjust the power in irregular regions with multipath, obstacles, etc.

efficient in terms of length of trajectory and localization error. D-connect follows a different approach by varying the power of the transmitted signal and ensures that the sensor node will receive sufficient number of beacon positions for location estimation. D-connect also solves the coverage problem by providing beacon information to each and every sensor which leads to the localization of all sensors. We plan to test the D-connect strategy on networks with sensors in the presence of obstacles and multipaths to study real-time performance. We also plan to improve the energy efficiency of the scheme by designing efficient power transmission schemes in the future. Acknowledgements The authors would like to thank Dr. Ankit Dubey, Assistant Professor, Department of Electronics and Communication Engineering, National Institute of Technology Goa, India for his valuable and constructive suggestions during the development of this research work.

5 Conclusion and future work This paper presented D-connect, a strategy that gives three non-collinear beacon node positions for the location estimation of an unknown sensor while maintaining the shortest trajectory. This paper also provides some existing approaches for localization that are applied to WSN. The proposed D-connect strategy is compared with other existing strategies. The results show that D-connect outperforms LMAT, Spiral, Scan, Double Scan, Hilbert and Z-curve methods in terms of the length of its trajectory. D-connect gives better results for localization error as compared to the Scan, Double Scan and Hilbert trajectories. The results confirm that the D-connect trajectory is

123

References 1. Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002). A survey on sensor networks. IEEE Communications Magazine, 40(8), 102–114. 2. Munir, S. A., Ren, B., Jiao, W., Wang, B., Xie, D., & Ma, J. (2007). Mobile wireless sensor network: Architecture and enabling technologies for ubiquitous computing. In Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops (AINAW07), USA, May 21–23, 113–120. 3. Nazir, U., Arshad, M. A., Shahid, N., & Raza, S. H. (2012). Classification of localization algorithms for wireless sensor network: A survey. In Proceedings of the IEEE International

Wireless Netw

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

Conference on Open Source Systems and Technologies (ICOSST), Lahore, Pakistan, Dec 20–22, 1–5. Baggio, A., & Langendoen, K. (2006). Monte-carlo localization for mobile wireless sensor networks. In Proceedings of the Mobile Ad-hoc and Sensor Networks, Hong Kong, China, December 13–15, 317–328. Sheu, J.-P., Hu, W.-K., & Lin, J.-C. (2010). Distributed localization scheme for mobile sensor networks. IEEE Transactions on Mobile Computing, 9(4), 516–526. Kim, K., Kim, H., & Hong, Y. (2009). A self localization scheme for mobile wireless sensor networks. In Proceedings of the IEEE Fourth International Conference on Computer Sciences and Convergence Information Technology, Seoul, TBD, Korea (South), Nov 24–26, 774–778. Sichitiu, M. L., & Ramadurai, V. (2004). Localization of wireless sensor networks with a mobile beacon. In Proceedings of the IEEE International Conference on, Mobile Ad-hoc and Sensor Systems, Fort Lauderdale, FL, USA, Oct 25–27, 174–183. Hu, Z., Gu, D., Song, Z., & Li, H. (2008). Localization in wireless sensor networks using a mobile anchor node. In Proceedings of the IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM), Xian, China, Jul 2–5, 602–607. Bahi, J. M., Makhoul, A., & Mostefaoui, A. (2008). Hilbert mobile beacon for localisation and coverage in sensor networks. International Journal of Systems Science, 39(11), 1081–1094. Rezazadeh, J., Moradi, M., Ismail, A. S., & Dutkiewicz, E. (2014). Superior path planning mechanism for mobile beaconassisted localization in wireless sensor networks. IEEE Sensors Journal, 14(9), 3052–3064. Koutsonikolas, D., Das, S. M., & Hu, Y. C. (2007). Path planning of mobile landmarks for localization in wireless sensor networks. Computer Communications, 30(13), 2577–2592. Jiang, J., Han, G., Xu, H., Shu, L., & Guizani, M. (2011). Lmat: Localization with a mobile anchor node based on trilateration in wireless sensor networks. In Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), Houston, TX, USA, Dec 5–9, 1–6. Munoz, D., Lara, F. B., Vargas, C., & Enriquez-Caldera, R. (2009). Position location techniques and applications. New York: Academic Press. Shang, F., Su, W., Wang, Q., Gao, H., & Fu, Q. (2014). A location estimation algorithm based on RSSI vector similarity degree. International Journal of Distributed Sensor Networks, 2014, 371350. doi:10.1155/2014/371350. Sahu, P. K., Wu, E. H.-K., & Sahoo, J. (2013). DuRT: dual RSSI trend based localization for wireless sensor networks. IEEE Sensors Journal, 13(8), 3115–3123.

16. Sarkar, T. K., Ji, Z., Kim, K., Medouri, A., & Salazar-Palma, M. (2003). A survey of various propagation models for mobile communication. IEEE Antennas and Propagation Magazine, 45(3), 51–82. 17. Rappaport, T. S., et al. (1996). Wireless communications: Principles and practice. Upper Saddle River, NJ: Prentice Hall PTR. 18. Mondal, K., Karmakar, A., & Mandal, P. S. (2016). Path planning algorithms for mobile anchors towards range-free localization. Journal of Parallel and Distributed Computing, 97, 35–46.

Ketan Sabale received the B.E. degree in Computer Engineering from University of Pune, Maharashtra, India, in 2012 and the M.Tech. Degree in Computer Science and Engineering from National Institute of Technology, Goa, in 2016. He is currently pursuing the Ph.D. degree with the Department of Computer Science and Engineering, National Institute of Technology, Goa. His research interests include wireless sensor networks, mobile ad hoc networks, and swarm intelligence. S. Mini received the master’s degree in Computer and Communication from Anna University, Chennai, India, and the Ph.D. degree in Computer Science from University of Hyderabad. She is currently an Assistant Professor in the Department of Computer Science and Engineering, National Institute of Technology, Goa. She is the principal investigator of a project sanctioned under the Early Career Research Award Scheme of Science and Engineering Research Board, Department of Science and Technology, Government of India. Her research interests include wireless sensor networks, internet of things, swarm intelligence, and combinatorial optimization.

123