Modified Scan Algorithm for Mobile Anchor Based Localization in Wireles Sensor Network: A Brief Review

Modified Scan Algorithm for Mobile Anchor Based Localization in Wireles Sensor Network: A Brief Review

Mr. Santosh P. Salgar Prof. U. A. Patil Mr. Rushikesh S. Vathare

Electronics Engineering Dept Electronics Engineering Dept Electronics Engineering Dept

DKTEs TEI, Ichalkaranji DKTEs TEI, Ichalkaranji DKTEs TEI, Ichalkaranji

Abstract- Localization of sensor node with least error is one of the major concern in wireless sensor network as some of the application require sensor node to know their location with high degree of precision. For mobile anchor based localization many of the path planning schemes already developed which includes scan, double scan, Circles & S- Curves. These path planning schemes have some limitations like localization error, Number of sensor nodes covered in the network, Trajectory length of mobile anchor node. This paper represents an overview of modified scan algorithm. This algorithm ensures trajectory of mobile anchor node will minimize localization error and also will cover majority of sensor node in the environment.

KeywordsLocalization; Mobile anchor node; Wireless sensor network; Modified Scan algorithm

1. INTRODUCTION

   A WIRELESS Sensor Network (WSN) consist of hundreds or thousands of sensor nodes and a small number of data collection devices [1]. The sensor nodes are designed to carry out sensing applications including environmental monitoring, military surveillance, fire detection, animal tracking, and so on. The sensor nodes gather the information of interest locally and then forward the sensed information over a wireless medium to a remote data collection device (sink),where it is fused and analyzed in order to determine the global status of the sensed area.

   In some WSN applications, the sensor nodes are required to know their locations with a high degree of precision, such as tracking of goods, forest fire detection, and etc. Many localization methods have been proposed for WSNs. Here we are going to deal with mobile anchor based localization scheme which belongs to Range free localization category. In this scheme the GPS-enabled mobile anchor node navigate in sensing field and helps other sensor node to find their locations. Again different localization algorithms are there under mobile anchor based localization. Several anchor movement strategies have been proposed for all these algorithm. As the anchor movement strategy is developed considering specific localization algorithm, their compatibility with other algorithm is not guaranteed. In specific we are

   going to deal with mobile anchor based localization scheme which is based on conjecture geometry. So straight away we cant use existing path planning strategies which are already developed for other localization scheme as they provide certain limitations.

   Accordingly this paper presents overview of path planning algorithm which is compatible with Mobile anchor based localization which is based on conjecture geometry [2]. The proposed path planning algorithm is modified form of existing Scan algorithm which was there for some other localization scheme. The modifications are made considering the methodology of localization.

2. LOCALIZATION SCHEME

   In the localization scheme [3], a single mobile anchor node moves randomly through the sensing field broadcasting periodic beacon messages containing its current coordinates. The locations of the individual sensor nodes are determined by exploiting the fact that the perpendicular bisector of a chord of a circle passes through the center of the circle. It is assumed that the communication range over which a sensor node can detect broadcasts from the mobile anchor node is bounded by a circle and the sensor node is located at the center of this circle. As the anchor node moves through the sensing field, it broadcasts its coordinates periodically, and each sensor node chooses appropriate locations of the anchor node (called beacon points) to form chords of its communication circle. Once three beacon points (i.e. two chords) have been constructed, the sensor node determines it location by calculating the intersection point of the two perpendicular bisectors of the chords (see Fig. 1).

   Fig.1 Beacon Points and Chord Construction

   This method provides a computationally straightforward means of determining the sensor locations.

   However, the accuracy of the localization results is dependent on the length of the chords. In realistic environments, the selected beacon points may not be exact on the communication circle. Based on the authors observation, when the length of the chord is too short, the probability of unsuccessful localization will increase rapidly. Thus, the authors suggested that the length of each chord should exceed a certain threshold in order to minimize the localization error.

   However, in these scheme the mobile anchor moves randomly through the sensing field (i.e., in accordance with the Random Waypoint model), and thus it is possible that some of the sensor nodes cannot be localized. Therefore, the modified scan algorithm proposed in this study is specifically designed to both minimize the localization error of the individual sensor nodes and to maximize the number of sensor nodes which can determine their locations.

3. EXISTING PATH PLANNING STRATEGIES

   1. SCAN

      In SCAN, the mobile anchor node travels along a single dimension (e.g. the x-axis or y-axis direction), and the distance between two neighboring segments of the node trajectory defines the resolution of the trajectory [4]. SCAN is simple and provides uniform coverage to the entire network. However, the collinearity of the beacons degrades the accuracy of the localization results. SCAN cannot guarantee that the length of each chord exceeds a certain threshold.

   2. DOUBLE SCAN

      In DOUBLE SCAN, the collinearity problem is resolved by driving the anchor in both the x- and the y- directions [4]. However, whilst this strategy improves the localization performance of the sensor nodes, the path length is doubled compared to that of SCAN, and thus the energy overhead increases accordingly. DOUBLE SCAN increases the beacon overhead due to the generation of redundant beacon points.

   3. HILBERT

      In HILBERT, the mobile anchor node is driven along a curved trajectory such that the sensor nodes can construct non-collinear beacon points and the total path length is reduced [4]. The results presented showed that through an appropriate setting of the curved trajectory parameters, a significant reduction in the localization error could be obtained compared to the case in which the anchor node simply moved randomly through the sensing field. HILBERT cannot guarantee that every sensor node will obtain the three or more beacon points required to construct two chords of the communication circle.

   4. CIRCLE

      In CIRCLES, the mobile anchor follows a sequence of concentric circular trajectories centered at the center point of

      the deployment area [5]. CIRCLES can only guarantee that the four corners of the sensing field are covered by expanding the diameter of the concentric circles. As a result, the path length is extended, and the energy consumption is increased.

   5. S-CURVES

   In S-CURVES, the anchor follows an S-shaped curve rather than a simple straight line as in the SCAN method [5]. The results showed that given a trajectory resolution much larger than the radio range, both CIRCLE and S-CURVE schemes cope effectively with the collinearity problem and provide a significantly better localization accuracy andcoverage than previous solutions.

   In S-CURVES, the trajectory of the mobile anchor cannot guarantee that each sensor node can construct two valid chords.

4. MODIFIED SCAN ALGORITHM

   In order to get at least three beacon points on the communication circle of sensor node to form two chords it is necessary that anchor node must through circle area at least two times. In the modified Scan algorithm proposed in this study, the distance between two successive vertical segments of the anchor trajectory (i.e. the resolution of the anchor trajectory) is specified as RX, where R is the communication radius of the mobile anchor node and X is set in the range 0 < X R/3. This is because if X is bigger than R/3, R X will be smaller than 2R/3 . Hence, the distance between four successive vertical segments is less than the diameter of the communication circle (i.e. 2R). As a result, the mobile anchor node will pass through the circle more than three times. In other words, increasing the value of X may incur redundant beacon points. Conversely, decreasing the value of X may cause the chord length to fall below the minimum threshold value. Thus, in practice, a careful choice of X is required. To determine the positions of the sensor nodes close to the boundary of the sensing field, the dimensions of the field are virtually extended by a distance of R on each side, as shown in Fig.2. By extending the sensing field, and choosing an appropriate value of X, the proposed path planning scheme ensures that the mobile anchor node passes through the circle of each sensor node either two or three times.

   Fig.2 Modified Scan Algorithm

   As shown in Fig. 2, the total path length D is given as

   = + 2 +2 + 1 + +2

   Figure 4 illustrates the localization error of the proposed scheme for various values of X in the range 0.05 to

   0.3 R. It can be seen that the localization error maintains a

   The total path length consists of two components i.e. Vertical path and Horizontal path. The vertical path comprises

   +2 + 1 segments of length + 2 and horizontal path

   constant value of just 0.3 0.45 m as the value of X is increased. The low value of the localization error arises because the modified scan algorithm guarantees that the length

   +2

   of all the chords constructed by the sensor nodes exceeds 2R/3

   comprises segments of length .

   This modified scan algorithms for mobile anchor based

   localization guarantees following conditions

   1. The chord length exceeds 2R/3

   2. All sensor nodes can determine their location

5. OBSTACLE RESISTANCE TRAJECTORY In a realistic environment, obstacles may appear in

   the sensing field and thus obstruct the radio connectivity between the anchor node and the sensor nodes. The obstacle- resistant trajectory of the anchor node is introduced in Fig. 3.

   Fig. 3 Obstacle Resistance Trajectory

   When the anchor node moving along the proposed trajectory discovers an obstacle, the anchor node detours around the obstacle toward the right-hand direction. After detouring, the anchor node returns to the original proposed trajectory. However, the obstacle-resistant trajectory may cause that sensor nodes obtain beacon points which are not on the circle. The localization performance will be degraded due to incorrect beacon points.

6. PERFORMANCE EVALUATION

   The performance of the modified scan algorithm is evaluated by performing a series of simulations on the ns-2 network simulator [6]. The simulation carried out for varying value of X.

   1. The localization error: the average discrepancy between the estimated sensor node location and the actual sensor node location for all the sensor nodes;

   2. The percentage of localized sensor nodes: the ratio of the number of successfully localized sensor nodes to the total number of sensor nodes;

   3. The chord length: the average chord length constructed by the sensor nodes.

   provided that the value of X is less than R/3.

   Fig. 4 Localization error Vs X

   Figure 5shows that the average chord length reduces with an increasing value of X. From inspection, the average chord length varies between 25.6 and 28.5 m, and is therefore greater than 2R/3= 13.3m.

   Fig. 5 Chord length Vs X

   Figure 6 compares the average localization errors of the six path planning schemes in each of the fifty simulation runs. It can be seen that when the presented mobile anchor based localization is implemented using modified scan algorithm, the localization error has a constant value of approximately 0.4 m and is lower than that achieved by any of the other schemes.

   Fig. 6 Localization error of all movement strategies

   Figure 7 shows the average chord length of the six path planning strategies in each of the fifty simulation runs.

   The chords constructed by the sensor nodes when using the HILBERT and S-CURVES strategies are significantly longer than those obtained when using the DOUBLE SCAN, CIRCLES and random movement schemes. The chord length obtained when using the modified scan algorithm has a constant value of around 28.5 m and is comparable to that obtained when using the HILBERT and S-CURVES methods. Of the six schemes, the CIRCLES scheme results in the shortest chord length.

   Fig 7 Chord length of all movement strategies

   Figure 8 shows the percentage of successfully localized sensor nodes in each simulation run when using the six different path planning strategies. It is observed that the movement strategy proposed in this study enables all of the sensors to determine their locations in every simulation run. It can be seen that DOUBLE SCAN also results in high localization performance (i.e., 98% 99%). The remaining movement strategies, i.e., HILBERT, S-CURVES, CIRCLES, and the original random movement strategy, result in average localization percentages of 82%, 91%, 82%, and 79%, respectively.

   Fig 8 Percentage of localized sensor node of all movement strategy

   Figure 9 depicts the average localization errors of the obstacle-free and the obstacle environments in each of the fifty simulation runs. Although the virtual beacon point generation is proposed to determine the locations of sensor nodes, the estimated position of the virtual beacon point may not be correctly located on the circle and thus incurs more errors on localization. It can be seen that the localization error of the obstacle-free environment keeps about 0.4 m and the obstacle environment has a localization error between 0.6 to 0.8 m.

   Fig 9 Localization errors of obstacle free and obstacle environment

   Figure 10 shows that the average chord length of the obstacle-free and the obstacle environments in each of the fifty simulation runs. The average chord length of the obstacle environment varies between 29.5 and 30.8 m and is larger than that of the obstacle-free environment.

   Fig 10 Chord length of obstacle free and obstacle environment

7. CONCLUSION

In this paper, we have presented overview study of a modified scan algorithm for the mobile anchor node in the localization method based on conjecture geometry. This algorithm ensures that the chords constructed by the individual sensor nodes always have a length greater than 2R/3 . Thus, the short chord problem is is resolved. Besides, the modified movement trajectory and the virtual beacon point generation scheme are presented to tolerate the obstacles in the sensing field. The performance of the modified scan algorithm is compared numerically with that of five existing path planning schemes, namely DOUBLESCAN, CIRCLES, S-CURVES, HILBERT, and

the original random movement strategy. Overall, the simulation results have shown that the modified scan algorithm outperforms existing methods in terms of both a smaller localization error and a higher percentage of successfully localized sensor nodes

<>REFERENCES

1. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Commun. Mag., vol. 40, no. 8, pp. 102-114, Auguest 2002.

2. Chia-Ho Ou, Membr, IEEE, and Wei-Lun He, "Path Planning Algorithm for Mobile Anchor-Based Localization in Wireless Sensor Networks," IEEE SENSORS JOURNAL, vol. 13, no. 2, pp. 466-475, FEBRUARY 2013.

3. C. H. Ou, and H. C. Jiau K. F. Ssu, "Localization with mobile anchor points in wireless sensor networks," IEEE Trans. Veh. Technol, vol. 54, no. 3, pp. 11871197, May 2005.

4. S. M. Das, and Y. C. Hu D. Koutsonikolas, "Path planning of mobile landmarks for localization in wireless sensor networks," Comput. Commun, vol. 30, no. 13, pp. 25772592, sept. 2007.

5. R. Huang and G. V. Zaruba, "Static path planning for mobile beacons to localize sensor networks," in Proc. IEEE Int. Conf. Pervas. Comput. Commun. Workshops, Mar. 2007, pp. 323330.

6. "The Network Simulator – ns-2," http://www.isi.edu/nsnam/ns/, (2012).