Review on Different Localization Schemes in Wireless Sensor Networks

Review on Different Localization Schemes in Wireless Sensor Networks

Sachin Gopal.V

Electronic and Communication Engineering NSS College of Engineering Palakkad,Kerala,India

Dr. Binu G. S

Assistant Professor

Electronics and Communication Engineering NSS College of Engineering

Palakkad,Kerala,India

AbstractWireless sensors are used for sensing physical quantities from the environment. Usually sensors are scattered in the sensing field. These sensors collect data from the environment and send it to the data collecting device. In many applications like home, military, health sensor location is essential. There are different approaches to locate sensors in the field. Comparison of different localization schemes are studied in this paper. Fixed anchor, mobile anchor, range based, range free are some localization schemes being used.

Keywords Range free, range based, fixed anchor, mobile anchor

INTRODUCTION

Application like habitat monitoring or health monitoring need information about current location. In the case of habitat monitoring sensors are fixed on some animals. Since they have highly random movement manual localization is difficult. So different methods are adopted for the localization[1-5]. One commonly used method is to find the location by using GPS enabled sensor devices. Large number of sensors are deployed for many applications. Installing a GPS receiver will increase the total cost. Power consumption is also higher which adversely affects the life of sensors. Fixing bulky devices like GPS on animals or any other remote place becomes difficult. Distributed location method without using GPS for the sensors are used [6-14]. In this method sensors have GPS unit[15]. These sensors transmit their position to all other sensors for localization. Use of mobile landmark or mobile anchor for localization is one method. The mobile device may be a robot or human. So the size of the device is much more than other sensor. There are different localization schemes to locate the sensors[14-16]. The localization can be done with static or mobile node and static or mobile or landmark. Each scheme can be classified into range free and range based. Range based scheme is a static path planning scheme which gives the angular or distance information between the neighbouring nodes. The information is obtained by TDOA, TOA, RSSI and AOA [17] method. In order to get the range information additional equipments are needed. Thus the system become bulky and complex[18]. In RSSI, according to the received signal strength, the distance between neighbouring nodes is calculated and location is estimated by triangulation [19-20]. Similarly in TOA and TDOA time of arrival and difference of arrival of signal are calculated. In AOA, angle of signal arrival is calculated and from this information, location of the sensors are determined. This method become expensive and complex due to the presence of equipments which are capable of finding these information. Range free scheme is the simplest algorithm widely used in WSN applications. In this scheme there is no

need of distance or angular information. So the system is inexpensive and widely used. Locations are calculated by using some algorithms [21-23]. Centroid scheme uses a centroid algorithm, DV-Hop method uses hop count from each reference point and locations are calculated. There are other range free schemes but the accuracy is much less than range based scheme. Timebased positioning scheme (TPS)[10] is another method used for calculating the location. The range information from three base stations is used for localization.

Fig. 1. Different localization scheme

1. LOCALIZATION SCHEME

   1. Static node and landmark)

      In this category both sensors and reference point or landmarks are static. Both range based and range free schemes are included in this category. APS[6],[24] TPS, TDoA, DV-Hop, are some of the methods. The range information from three or more static nodes or land marks are used for the distance calculation. By using triangulation, trilateration, multilateration [25] method, locations are estimated. AFL is another method which performs the localization without using GPS equipped device.

   2. Mobile nodes and static landmarks

      In this category the nodes have mobility and some reference points or fixed land marks are placed in a pre-defined location. This method is suitable for indoor localization in order to locate mobile nodes in a building like in a hospital or in a factory. These schemes have two phases. Offline and online localization phase. In offline phase a database is prepared. The database consists of signal strength at different points. In the second phase the mobile node compares its current signal strength with signal strength stored in the database and gives an estimate of the location. This system uses RADAR, CRICKET location etc.

   3. Static nodes and mobile landmarks

   In this category one or two mobile landmarks are used. This method is used to reduce the number of expensive GPS nodes. Mobile landmark can be of a robot or a man. This mobile landmark or mobile anchor moves through a particular sensing area and periodically sends its coordinate as beacon messages. This beacon message is used for location calculation. There are different path planning schemes of the mobile anchor movement. SCAN, DOUBLE SCAN, HILBERT in [3], S-

   CURVE, CIRCLES in [5] are some of the path planning schemes. According to this algorithm the mobile anchor moves through the sensing field.

2. DIFFERENT LOCATION ESTIMATION TECHNIQUES

   1. RADAR

      This method is used for continuous tracking of an object. It consists of two sections ie of tracking a user and locating the user[26-27]. RADAR can be used to locate the user with few meters from the actual location[28]. RADAR is based on radio frequency. Signal strength at specific location is calculated and processed. Nearest neighbours in signal space are used to find the best match location[29]. IR wireless networks are also used for location tracking.

   2. Distance vector-hop method

      One of the simplest schemes is the distance vector hop mechanism method which consists of different stages [30]. In the first stage, distance is calculated according to hop count. Nodes maintain a table with its position and hop count. This table is exchanged with the other neighbouring nodes. During the next stage, each landmark calculates the distance between other landmarks. The size of each hop is estimated and a correction in location is calculated and passed to all other nodes. Forward correction mechanism is used which ensures that all nodes get only one correction from the nearest landmarks. DV-distance method is another method closely related to the DV-hop method. Instead of measuring the hop count between the nodes it measures the distance in meters using signal strength.

   3. Ad hoc positioning system (APS)

      In the case of a wireless sensor, each node can communicate with its neighbouring node with in the coverage area[6],[31]. Ideally coverage area is considered as a circle. In APS both node and landmarks are static. The landmarks have the knowledge about their position by human input or GPS receiver. Angle of arrival capability is utilized for the calculation of range information. This is done by using array antennas.[7],[24].

      Fig.2 shows the location calculation from the angle and range information. If position of each vertice and the angle towards an interior points are known then that point can be located. This method is called triangulation. Here , B, C are landmarks or anchors. The distance between each landmark and sensor, the angle from each landmark ADC, BDA and

      CDB are known. Then the location can be easily found out.

      In wireless networks, the node can only communicate with its neighbouring nodes since they are low powered devices. More power used for signal transmission will lead to reduction in life of the node. Multi hop mechanism is used to increase the life of the network. In order to achieve this APS [7] distance vector routing and GPS positioning are used. The information from one node is passed to the next in hop by hop fashion. Based on the base station reading each node locates itself. Another method is also included in the APS system. If the nodes are not oriented with respect to the landmark forward bearing is used. This method consists of two algorithms, DV bearing, which allows to get orientation from node to landmarks, and DV radial, which gives the radial information. This method has an advantage of giving exact location and orientation. Error control mechanism in[32-33] is used to correct the position estimate from the reference node.

   4. Anchor free location (AFL)

      Sensor networks have a self configuring capability. This method use a decentralized algorithm[37]. All sensor nodes start from a random initial location. In outdoor environment, the location information is found by using a GPS receiver[34]. From a set of nodes whose positions are unknown, and a mechanism can be used to determine the location. AFL algorithm consist of two phases. In the first phase a free fold graph similar to the original graph is created and in the next phase an optimization method is used to correct the errors. Anchor based algorithm is proposed in [35]. This algorithm consists of small number of anchors which are aware their locations.

   5. Time based positioning schemes (TPS)

      This technique is one of the efficient localization methods in outdoor networks. Most location measuring methods have two phase: range or angle measurement and position estimation. Range estimation can be done with TOA, TDoA, AoA, RSSI etc. Time of arrival and time difference of arrival uses the time taken by a signal to reach the destination and tie time difference of arrival. In AoA the angle at which the signal arrive is calculated. Location is computed from the range or angle information. The techniques used for the calculation are trilateration, multilateration[36] or triangulation[15],[18] as shown in Fig.3(i) If the angle of arrival of signals from two base station 1 and 2 is known, then location is where line from Base Stations intersects. Fig.3(ii) shows the trilateration. The common intersection point from each land mark gives the location of the sensor. In this case if there is no common intersection, location result becomes incorrect. Multilateration in Fig.3(iii) uses a function to minimize the error in localization. This technique has higher accuracy and computational overhead. Fig. 4 shows TPS which uses TDoA and trilateration. This method consists of two steps. In the first method, the difference in time of arrival of signal from different Base Stations is noted, basically from three Base Stations. Thus range difference information is obtained, further by using trilateration the coordinates are obtained [10].

      Fig. 3. Combining technique

      Fig. 4. Time based positioning scheme

   6. Distributed position estimation algorithm

      Consider some static nodes and more than one anchor node [37]. The anchor sends beacon packets. These packets are used for position estimation. Distance can be measured by measuring propagation delay of ultrasonic signals. The beacon packet contains id of the node, power level at the time of transmission and current position. In this case one node can assist other nodes in estimating the location, ie if one node has an idea about its location it can help other nodes in localization. Position estimate of all node in the area are initialized. Only beacon packet transfer takes place. From these beacon packets certain constraints about location is made. The current estimate and new the constraint are compared and new location is noted and broadcast to all other sensors. This method ensure that every node receives one beacon message from each anchor.

   7. Different mobile anchor movenment

      In the case, of static sensor and mobile landmarks, the anchor moves through the sensing field [38]. The anchor follows different algorithms, and it periodically broadcast its coordinates as beacon message. These beacon messages is further used to calculate the location. Location is calculated by the perpendicular bisector of a chord pass through the center. In

      order to construct two valid non parallel chords three beacon points are needed so that the mobile node must pass through the sensor at least two times. In [3],[5],[39] different path planning schemes are proposed for mobile sensors which are SCAN, HILBERT, DOUBLE SCAN, CIRCLES, S-CURVES.

      1. SCAN and DOUBLE SCAN: In this method, mobile node moves in only one direction either x or y direction. Resolution of SCAN method can be defined by the distance between the two adjacent vertical segments. SCAN method has a disadvantage of collinearity of beacon points, ie sensor gets beacons from a single vertical segment. If resolution is properly chosen then the collinearity problem can be avoided [4]. Consider sensors are located at all corners of the sensing field. SCAN doesnt scan the corners of the field. So virtually the sensing field has to extended so that the sensors at the corners get beacon messages. Consider the communication range of a sensor is R and maximum resolution 2R, if L is the length of square. In [4] a modified SCAN method is proposed which, virtually extends the field by a distance of R. So all sensors get localized. Obstacles are also included in the sensing area[40-44], So obstacle resistant mechanism and virtual beacon selection are used in [4]. In order to avoid collinearity DOUBLE SCAN is used. The mobile node covers both x and y directions. In DOUBLE SCAN the mobile anchor first moves along the y axis, like SCAN then it step towards the x axis. So the path length of DOUBLE SCAN is two times that of SCAN and the execution time also increases.

      2. HILBERT: It is a space filling curve. It consists of many turns. So collinearity problem is solved and path length is also lesser than SCAN. The complexity of HILBERT curve depends on the level chosen. For an n level HILBERT curve the entire square plot is divided into 4n square cells. Center of each square is connected using 4n line

      3. CIRCLES and S-Curves: Other methods are introduced by Huang and Zaruba [5] to avoid the collinearity problem introduced in SCAN. In CIRCLES the mobile anchor moves according to concentric circles with resolution R. In order to travel along the corners of the field the path should be increased. S-Curves are similar to SCAN. The mobile anchor moves like S curve in one direction. In this method since more turns are used collinearity can be avoided

3. CONCLUSIONS

In this paper different localization schemes used for locating wireless sensors are discussed. Sensors in different scenarios are also considered. In [4] a modified path planning scheme is proposed for localization. The mobile anchor moves in one direction and periodically broadcasts a beacon message. Modified SCAN in [4] ensures the localization of all the sensors in the field. RADAR method is one of the simplest and oldest methods to determine the location information. Localization also uses with or without anchors. Using small number of GPS enabled devices anchor localization can be achieved.

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, Aug. 2002.

2. K. F. Ssu, C. H. Ou, and H. C. Jiau, Localozation with mobile anchor points in wireless sensornetworks, IEEE Trans. Veh. Technol., vol. 54, no.3,pp 1187-1197, May 2005

3. D. Koutsonikolas, S. M. Das, and Y. C. Hu,Path planning of mobile landmarks for localization in wireless sensor networks, Comput. Commun., vol. 30, no. 13, pp. 2577-2592, Sep.2007.

4. Chia-Ho Ou, Wei-Lun He Path planning allgorith for mobile anchor based localization in wireless sensor networks, IEEE sensor journal,

   Vol. 13, no. 2, Feb 2013

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. 323-330.

6. D. Niculescu and B. Nath, Ad hoc positioning system (APS), Technical Report DCS-TR-435, Department of Computer Science, Rutgers University (2001).

7. D. Niculescu, B. Nath, Ad hoc positioning system (APS), in:Proceedings of Globecom, November 2001.

8. N. Bulusu, J. Heidemann, D. Estrin, GPS-less low cost outdoor localization for very small devices, IEEE Personal Commun. Mag. 7(5) (2000) 28-34.

9. X. Ji, H. Zha, Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling, in: Proceedings of IEEE INFOCOM, March 2004.

10. X. Cheng, D.C. Andrew Thaeler, Guoliang Xue, TPS: a timebased positioning scheme for outdoor wireless sensor networks, in: Proceedings of IEEE INFOCOM, March 2004.

11. L. Hu, D. Evans, Localization for mobile sensor networks, in:Proceedings of ACM MobiCom, September 2004.

12. N.B. Priyantha, A. Chakraborty, H. Balakrishnan, The cricket location- support system, in: Proceedings of MobiCom, September 2000.

13. A. Savvides, C.-C. Han, M.B. Strivastava, Dynamic finegrained localization in ad-hoc networks of sensors, in: Proceedings of ACM MobiCom, July 2001.

14. M. L. Sichitiu and V. Ramadurai, Localization of Wireless Sensor Networks with a Mobile Beacon, in Proc. of the First IEEE Conference on Mobile Ad-hoc and Sensor Systems ( MASS 2004), pp. 174-183, Fort Lauderdale, FL, October 2004.

15. B. Parkinson and J. Spilker, Global Positioning System: Theory and Application. American Institute of Astronautics and Aeronautics, 1996.

16. K.-F. Ssu, C.-H. Ou, and H.C. Jiau, Localization with Mobile Anchor Points in Wireless Sensor Networks, IEEE Transactions on Vehicular Technology, vol. 54, no. 3, pp. 1187-1197, May 2005.

17. A. Nasipuri and K. Li, A directionality based location discovery scheme for wireless sensor networks, in Proc. ACM Int. Workshop Wireless Sensor Netw. Appl., Sep. 2002, pp. 105-111.

18. T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, Range-free localization schemes for large scale sensor networks, in Proc. ACM Int. Conf. Mobile Comput. Netw., Sep. 2003, pp. 81-95.

19. J. Hightower,G. Boriello, and R.Want,SpotON: An indoor 3 D location sensing technology based on RF signal strength, Univ. of Washington, Tech. Rep. UW CSE 00-02-02, Feb. 2000.

20. P. Bahl and V. N. Padmanabhan, RADAR: an in-building RFbased user location and tracking system, in Proc. IEEE Joint Conf. IEEE Computer Communications Societies ( INFOCOM), Tel Aviv, Israel, Mar. 2000, pp. 775-784.

21. N. Bulusu, J. Heidemann, and D. Estrin, GPS-less low cost outdoor localization for very small devices, IEEE Personal Commun., vol. 7, pp. 28-34, Oct. 2000.

22. D. Niculescu and B. Nath, DV based positioning in ad hoc networks,

    Kluwer J. Telecommun. Syst., vol. 22, no. 1, pp. 267280, Jan. 2003.

23. C. T. Chang, C. Y. Chang, and C. Y. Lin,Anchor-guiding mechanism for beacon-assisted localization in wireless sensor networks, IEEE Sensors J., vol. 12, no. 5, pp. 1098-1111, May 2012.

24. D. Niculescu, B. Nath, Error characteristics of ad hoc positioning systems (APS), in: Proceedings of MobiHoc, May 2004.

25. A. Savvides, H. Park, and M. Srivastava, The bits and flops of the Nhop multilateration primitive for node localization problems, in Proc. ACM Int. Workshop Wireless Sensor Netw. Appl., Sep. 2002, pp. 112-121.

26. P. Bahl and V. N. Padmanabhan, RADAR: An in-building RFbased user location and tracking system, in Proc. IEEE Joint Conf. IEEE Comput. Commun. Soc., Mar. 2000, pp. 775-784.

27. P. Bahl, V.N. Padmanabhan, RADAR: an in-building RFbased user location and tracking system, in: Proceedings of IEEE INFOCOM, March 2000.

28. Paramvir Bahl and Venkata N. Padmanabhan, RADAR: An In-Building RF-based User Location and Tracking System, Microsoft Research,

29. A. Harter and A. Hopper,A Distributed Location System for the Active Office, IEEE Network, January 1994

30. Drago S Niculescu and Badri nath DV Based Positioning in Ad

    Hoc Networks Telecommunication Systems 22:1-4, 267-280, 2003

31. D. Niculescu, B. Nath, Ad hoc positioning system (APS) using AOA,

    in: Proceedings of IEEE INFOCOM, March 2003.

32. M. Betke and L. Gurvitis, Mobile robot localization using landmarks, in IEEE International Conference on Robotics and Automation, vol. 2, May 1994, pp. 135-142.

33. D. Niculescu and B. Nath, DV based positioning in ad hoc networks,

    Telecommunication Systems, Baltzer, vol. 1, 2003, to appear.

34. HOFFMANN-WELLENHOF, B., LICHTENEGGER, H., AND COLLINS, J. Global Positioning System: Theory and Practice, Fourth Edition. Springer-Verlag, 1997.

35. SAVARESE, C., RABAEY, J., AND BEUTEL, J.Locationing in Distributed Ad-Hoc Wireless Sensor Networks. In Proc. of ICASSP (Salt Lake City, UT, May 2001), pp. 2037-2040.

36. SAVVIDES, A., HAN, C., AND SRIVASTAVA, M. Dynamic Fine- Grained Localization in Ad-Hoc Networks of Sensors. In Proc. 7th ACM MOBICOM Conf. (July 2001), pp. 166-179.

37. M.L. Sichitiu, V. Ramadurai, P. Peddabachagari, Simple algorithm for outdoor localization of wireless sensor networks with inaccurate range measurements, in: Proceedings of ICWN, June 2003.

38. C. T. Chang, C. Y. Chang, and C. Y. Lin, Anchor-guiding mechanism for beacon-assisted localization in wireless sensor networks, IEEE Sensors J., vol. 12, no. 5, pp. 1098-1111, May 2012.

39. M. L. Sichitiu and V. Ramadurai, in Proc.Localization of wireless sensor networks with a mobile beacon, IEEE Int. Conf. Mobile Ad-Hoc Sensor Syst., Oct. 2004, pp. 174-183.

40. C. Y. Chang, C. T. Chang, Y. C. Chen, and H. R. Chang,

    Obstacleresistant deployment algorithms for wireless sensor networks,

    IEEE Trans. Veh. Technol., vol. 58, no. 6, pp. 2925-2941 , Jul. 2009.

41. C. Y. Chang, J. P. Sheu, and Y. C. Chen, An obstaclefree and powerefficient deployment algorithm for wireless sensor networks, IEEE Trans. Syst., Man, Cybern., A, Syst. Humans, vol. 39, no. 4, pp. 795-806, Jul. 2009.

42. C. Y. Chang, C. T. Chang, Y. C. Chen, and S. C. Lee,Active route guiding protocols for resisting obstacles in wireless sensor networks, IEEE Trans. Veh. Technol., vol. 59, no. 9, pp. 44254442, Nov. 2010.

43. G. N. DeSouza and A. C. Kak, Vision for mobile robot navigation: A survey, IEEE Trans. Pattern Anal. Mach. Intell., vol. 24, no. 2, pp. 237- 267, Feb. 2002.

44. Y. Wang, S. Fang, Y. Cao, and H. Sun, Image-based exploration obstacle avoidance for mobile robot, in Proc. IEEE Chin. Control Decision Conf., Jun. 2009, pp. 3019-3023. [45] N.B. Priyantha, H. Balakrishnan, E. Demaine, S. Teller, Anchor-free distributed localization in sensor networks, in: Proceedings of SenSys, November 2003

45. G. Han, H. Xu, J. Jiang, L. Shu, Y. Hara, and S. Nishio, Path planning using a mobile anchor node based on trilateration in wireless sensor networks, Wireless Commun. Mobile Comput., 2011, to be published.