A Localization Scheme with Dual Mobile Beacons in Wireless Sensor Networks

INTRODUCTION

---

Localization which is one of the key supporting technologies in WSN (Wireless Sensor Network) is widely used to acquire node’s location in many aspects such as some routing mechanisms, target tracking, load balancing, topology control and so on. As a consequence, to acquire the location of an unknown node efficiently has a great significance for WSN’s application, running and management.

In the conventional location methods, the unknown node will estimate its location through a certain method which uses the distance between the unknown node and the beacon node (deployed in the network by a certain proportion). This distance is calculated by some mechanisms such as RSSI (Received Signal Strength Indicator), TOA (Time of Arrival), TDOA (Time Difference of Arrival), AOA (Angle of Arrival) and so on. There is a close relationship between the location effect and the density of beacon nodes. That is to say, the accuracy of the localization method will be improved with the increasing of beacon nodes’ density. But unfortunately, the cost of network deployment will also rise. To reduce network deployment cost, attentions have been paid to the mobile sink technology which is introduced into WSN in recent years. GPSs have been installed in the mobile sinks to convert them into mobile beacon nodes and achieve the purpose of reducing the fixed beacon nodes’ number in WSN.

In the earlier research of Mobile Beacon localization technologies, for instance the methods proposed by Sichitiu and Ramadurai (2004) and Ssu et al. (2005), there are not any breakthroughs in the localization method. The reason for this is that how to design a better mobile beacon’s track whose motion position can be used to replace the fixed beacon is the main focus of the researchers. After 2006, concentrations have been moved to how to propose a new localization method which can make full use of beacon’s mobility to acquire better localization accuracy through distance measurement with low cost (Guo et al., 2010; Chen et al., 2010; Kim and Lee, 2007; Lee et al., 2007, 2009; Urie and Chugg, 2010; Munir et al., 2007; Liao et al., 2011). Literatures (Guo et al., 2010; Chen et al., 2010; Urie and Chugg, 2010; Munir et al., 2007; Liao et al., 2011) all employ the ranging-free scheme or partial ranging-based scheme while the methods by Guo et al. (2010) and Munir et al. (2007) have distinguishing features. Guo et al. (2010) proposed a direction measurement localization method based on RSSI. Mobile Beacon in this method will move along a triangle track and consider the intersection point of two perpendiculars through two sub-points of the triangle’s two sides as the localization result. The measuring point with strongest RSSI of the triangle’s each side is regarded as the unknown node’s sub-point on each side. The study wrote by Munir et al. (2007) which has no relationship with distance measurement, presents a method that utilize Mobile Beacon to broadcast beacon message periodically. Mobile Beacon records the first and last response time of the unknown node to compose an isosceles triangle, then uses the communication range as the triangle’s side to calculate the unknown node’s coordinates. Both the two methods mentioned above have given some novel thoughts of localization. But the performance of localization by Guo et al. (2010) is influenced by the measurement of RSSI. The fluctuation of RSSI will bring wrong sub-points and lead to a larger error while the method by Munir et al. (2007) needs the unknown node to respond to the beacon message frequently which consumes WSN node’s energy.

A ranging-free localization method which is based on dual Mobile Beacon has been put forward on the basis of Munir et al. (2007) in this paper. Using two Mobile Beacons which have different communication ranges, the localization can be accomplished only by one information interaction between unknown node and two beacons. Compared with Munir’s work that sensor node need frequently respond to beacon message, the method proposed in this paper is benefit for energy consumption control of the WSN nodes. Since this paper’s method adopts ranging-free scheme, the error caused by the fluctuation of RSSI by Guo et al. (2010) won’t appear. The research of this study can be used as theoretical reference in the study of WSN localization technology.

SYSTEM MODEL AND LOCALIZATION METHOD

Basic localization method: Assuming there are n senor nodes that distribute randomly in a square area with side length a(m) (Fig. 1), two Mobile Beacons with fixed distance move along the horizontal midline or vertical midline of the square area at a speed of v(m/s); Mobile Beacon 1 denoted as M₁ has a communication range of R₁(m), Mobile Beacon 2 denoted as M₂ has a communication range of R₂(m) (the same as the unknown node’s), R₁>R₂. Both the two Mobile Beacons periodically broadcast the beacon message which contains current message sending time, broadcast time interval, current beacon coordinates (obtained from GPS in the Mobile Beacon). The time period is T_f(S) and the two Mobile Beacons keep time synchronization. Mobile Beacon’ coordinates will be recorded in case of locating the unknown node when it sends a beacon message.

Fig. 1:	A square scenario with random-deployed nodes

Fig. 2:	System model under no error condition

Description of localization method: For a node P which lies in front of the Mobile Beacon’s moving path (left or right side) and needs to be localized will receive the beacon messages successively from the two Mobil Beacons. In an ideal situation, we can believe that the distance between node P and M₁/M₂ is R₁(m)/R₂(m) when node P first receives a beacon message from M₁/M₂.

As Fig. 2 shows, T_i is assumed to represent the message sending time when P receives the first beacon message from M₁ and at the same time M₁ is at M_1,i with the coordinates (x₁, y₁); T_j is assumed to represent the message sending time when P receives the first beacon message from M₂ and at the same time M₂ is at M₂ with the coordinates (x₁, y₁), M₁ is already at M_1,j. A data packet “ACK” will be sent back to M₂ when node P receives a beacon message from M₂ at the first time. “ACK” contains time messages of T_i and T_j, M₁’s coordinates (x₁, y₁) at time T_i, M₂’s coordinates (x₂, y₂) at time T_j and the list of node P’s neighbor nodes. According to the list of node P’s neighbor nodes, M₂ estimates which side node P lies.

Fig. 3:	Pseudo-code of the process in sink

Fig. 4:	Pseudo-code of the process in unknown node

In no error condition, the angle θ can be calculated by using the sides R₁, R₂, (T_j-T_i)xv of triangle ΔPM_1,iM_2,j and then with the help of M_1,i’s or M_2,j’s coordinates, node P ’s coordinates can be confirmed. Figure 3 and 4 show the detailed description of method.

Localization of the unknown node in condition of error: Figure 5 and 6 show two basic errors which will influence the localization of the unknown node in this study’s method.

Fig. 5:	Demonstration of the first class localization error

Fig. 6:	Demonstration of the second class localization error

First class error: The location of the Mobile Beacon whose beacon message is received by node P at the first time will be ahead of the ideal location α(m), α∈[0, T_fxv], since the beacon message is sent by the Mobile Beacon every T_f time. In an ideal situation (Fig. 5), the distance between node P and node M_1,i is R₁ while in fact M₁ will be at M'_1,i ahead of the ideal location α(m) when node P receives the beacon message from M₁ for the first time. When node P receives the beacon message from M₂ for the first time, M₂ will be at M'_1,i ahead of the ideal location α(m) since we assume the two Mobile Beacons keep time synchronization. So, the localization result P' will deviate from node P’s true location (horizontal or vertical translation from α(m)).

Second class error: GPS that equipped on the Mobile Beacon will also bring error during Mobile Beacon’s movement. Shown as Fig. 6, if we use ε(m) to denote localization error, then at T_i, the coordinates (x'₁, y'₁) identified by M₁ is on a circle centered in M₁’s real coordinates and the radius of the circle is ε. So, is M₂’s coordinates (x'₂, y'₂).

At this time localization error which is direct proportion to ε will arise if we use (x'₁, y'₁),(x'₂, y'₂) and ΔPM_1,iPM_2,j to calculate the unknown’s coordinates. Furthermore, the bottom side of ΔPM_1,iPM_2,j calculated by (x'₁, y'₁),(x'₂, y'₂) will lead the triangle have no solution. Since the time T_i and T_j is known and v the velocity of beacon is constant, we use (T_i-T_j)xv as the length of the bottom side M_1,iM_2,j to solve ΔPM_1,iPM_2,j.

In addition, the error that is caused by some environment factors (such as environment obstacles) in channel and lead M₁ to be ahead of its ideal location is equivalent to Error 1. So, we omit the discussion.

By a comprehensive consideration of the two kinds of error, the location of the unknown node can be calculated by the follow equations:

(1)

where, (x, y) is the coordinates needed to solve, R₁, R₂ are the ranges of M₁, M₂; (x₁", y₁") is the coordinates with error of M₁ in time T_i, Eq. 2; (x₂", y₂") is the coordinates with error of M₂ in time T_j, Eq. 3. In Eq. 2 and 3,(x₁, y₁), (x₂, y₂) are coordinates of beacon M₁ and M₂ in the condition without error:

or:

(2)

or:

(3)

When d>2ε, if |y₁"-y₂"|≤2ε, then we consider the two Mobile Beacons move along the horizontal direction and when d>2ε and |y₁"-y₂"|≤2ε, we think the two Mobile Beacons move along the vertical direction. In the horizontal motion circumstance, y₁ = y₂, so (y-y₁")² and (y-y₂")² are offset while subtracted is made between the two equations in Eq. 1, then we get a simplified result:

(x-x1")2-(x-x2")2 = R21-R22

namely:

(4)

Solve the Eq. 4 directly, we can obtain the x coordinate of the unknown node (Eq. 5). If Eq. 2 and 3 are substituted into 4, we can analysis the error of x coordinate:

(5)

In ΔPM_1,iM_2,j, angle θ is:

(6)

So, the y coordinate of the unknown node is:

(7)

In Eq. 7, we use the means of y₁" and y₂" to reduce the error since and they may have some measurement error; symbol‘ ± ’denotes which side of Mobile Beacon (up or down side) the unknown node lies at; the judgment is made by M₂ according to the list of neighbor node in “ACK”.

Similar to the horizontal motion circumstance, if the two Mobile Beacons move along vertical direction, the results are in Eq. 8 and θ is still calculated by Eq. 6.

(8)

However, we consider the unknown node already lies in the range of M₁ and M₂, if the time difference between beacon message that unknown node receives from M₁ and M₂ for the first time is less than (R₁-R₂/v), for instance, the nodes nearby two Mobile Beacons’ initial locations. In this circumstance, the method in this study becomes invalid and localization of the round fails. The unknown node will discard the beacon message received from M₁ for the first time and go to sleep when M₁ and M₂ return next time localization will be made again.

SIMULATION AND ANALYSIS

The simulation scenario is to be shown in Fig. 1. Assuming the range of M₁ is R₁ = 100(m), M₂ is R₂ = 50(m). The two Mobile Beacons move along the square area’s horizontal midline in a even velocity and they keep a fixed distance d = 50(m). It is Mobile Beacon’s velocity v, self-localization error ε and interval between beacon messages T_f that will affect the accuracy of localization’s result. So, the simulation is conducted with three factors changes which are mentioned above. Root-mean-square (RMSE) is employed to describe the localization error in the simulation with 10000 independent experiments. RMSE is calculated by formula 9, where, (x, y) is the true coordinates of the unknown node while () is the estimated coordinates:

(9)

Considering the Mobile Beacon’s mobility (v) and interval of two beacon messages (T_f), the localization error of unknown node increases in a linear relationship when the product of v and T_f rises in the condition of ε = 0. Figure 7 shows when T_fv = 2(m), the error is 1.17(m); when T_fv = 50(m) the error is 39(m). It is suggested that the product of T_fv should be controlled under 10(m) to achieve a preferable localization result. That is to say, when the velocity of the Mobile Beacon rises, the interval of two beacon message should be cut down.

The influence of self-localization error is shown in Fig. 8. It is obvious to conclude that the error of method is mainly determined by beacon’s self-localization error when this error exists and the value of T_fv has little influence on the localization result. Three curves in Fig. 8 are so close when ε>5 and T_fv varies from 2(m) to 10(m), namely the error is small. But this result deteriorates quickly (from 6(m) to 30(m) when ε varies from 5(m) to 20(m).

Fig. 7:	Localization errors under different beacon velocity and beacon message interval

This phenomenon means the self-localization error has a significant influence on the result of method. So, the improvement of self-localization accuracy will bring well localization result.

Figure 9 shows a sample of random simulation in the scenario shown in Fig. 1 under the condition of T_f, 5(S), v = 2(m)/S, ε = 2(m); Fig. 10 shows a sample of random simulation under the condition of T_f, 2(S), v = 2(m)/S, ε = 6(m). In these figures, the diamond symbol presents the estimated location of node while the star symbol presents the original location. When ε the self-localization error of Mobile beacon is small, the localization error in Fig. 9 is about 6(m). It means the localization result is preferable though T_f is a little large. As ε increases, the result becomes badly though T_f is small. This can be seen in Fig. 10, the diamond symbols obviously separate from its original position than Fig. 9.

Fig. 8:	Localization errors under different Beacon self-localization error and beacon message interval

Fig. 9:	Localization result for test scenario under the condition of Tf = 5s, v = 2M/s, ε = 2 m

Fig. 10:	Localization result for test scenario under the condition of Tf = 2s, v = 2M/s, ε = 6 m

The localization error in Fig. 10 is slightly higher than 8(m). The results in Fig. 9 and 10 describe the actual effect of localization of our method in further.

Furthermore we do some comparisons to the previous researches, the similar work is the method proposed by Munir et al. (2007). In Munir’s work, only one mobile beacon is used to get unknown node’s location, so the beacon must frequently communicate with unknown node. In order to obtain more accurate localization result, Munir’s method should minimize beacon messages interval as possible, but it bring more energy consumption of sensor nodes. In contrast, our method adopts two mobile beacons with different communication range for localization, so the unknown node’s location can be obtained only by one information interaction between unknown node and two beacons. Under the condition of same beacon velocity and beacon messages interval, our method and Munir’s method can get the same localization performance but our scheme effectively control energy consume of sensor nodes. In addition, our work further analyzes the impact of beacon self-localization error but Munir et al. (2007) don’t consider this factor.

Other previous localization researches using mobile sink depend on ranging-based technology or partial ranging-based technology can’t compare with our scheme due to different design ideas.