Abstract: Localization has been regarded as one of the fundamental and supporting technology for many applications of wireless sensor networks. This study presented an overview of localization techniques and surveyed the currently available algorithms for localization. In this survey, we proposed different classification methods, reviewed important localization algorithms, summarized their advantages and disadvantages for wireless sensor networks and finally, discussed some possible directions of future research.
INTRODUCTION
With ever increasing advancement in the manufacturing industry and extensive application of sensor network, Wireless Sensor Networks (WSN) have attracted unprecedented attention (Ruifang et al., 2009). Localization is critical for many applications in wireless sensor networks, such as clustering, topology control, location-based information querying and geographical routing (Li et al., 2009a). Without the 1ocation of sensor nodes, collected information is valueless (Ye-Hua et al., 2008). Hence, Localization has become the hot research spot of wireless sensor network.
The GPS has been widely applied in automobile and so on. However, its implementation is too heavy-weight to be supported by sensor nodes. Moreover, it is too expensive to attach on cheap node (Li et al., 2009a). Self-organized, robustness, efficient energy is necessary for localization algorithm in wireless sensor network.
Thus far, a number of localization algorithms have been reported. Different researchers have different strategies to categorize them with various criteria. In general, those strategies can be divided into centralized localization methods and distributed localization methods, range-based localization methods and range-free localization methods, absolute localization methods and relative localization methods.
Our contribution in this study is to survey the state of the art of localization algorithms in wireless sensor networks. We also compared localization protocols from different perspectives in order to discuss directions of future research on this problem.
LOCALIZATION METHOD CLASSIFICATION
Centralized localization method: Centralized localization algorithms require base station to gather network-wide environment information and with plenty of computational power. Base station determines the location of each node by collected data and transport them back into network. The collection of information performed by message exchange between nodes, hence, with the number of nodes increased in network, centralized localization algorithms become lower energy-efficiency, longer delay and larger network communication traffic. In another hand, it will obtain relative high precise location. Common node has light calculation burden. In general, it was suitable for static small networks.
The MDS-MAP and Semi-Definite Programming (SDP) are classic protocols of centralized localization method. MDS-MAP obtains node location information by using a technique from data analysis in statistics called multidimensional scaling (MDS) and transforming the node related information into the space coordinates (Xin et al., 2008). Semi-definite programming approach (Doherty et al., 2001) is an extension of linear programming. It used convex optimization to estimate positions based on connectivity constraints given some nodes with known positions. Ye-Hua et al. (2009a) presented a semi-centralized localization algorithm based on support vector regression (SCBSVR). It can avoid collecting global network information and reduce the accumulation of ranging errors.
Distributed localization method: In the process of distributed localization, each node independently determined its location with only limited communication with one-hop or multi-hops neighbor nodes. It has the characteristics of small traffic, equal calculation burden of each node, little storage requirements, good scalability. However, due to the lack of global information, location accuracy is susceptible to the number of beacon nodes and the distribution of nodes.
Diffusion and approximate point in triangulation test (APIT) are classic protocols of centralized localization method. Bulusu et al. (2000) localized unknown node by centroid model: the position of unknown node is at the centroid of its neighbors’ position. This method has low computational complexity and poor localization precision. It is quite useful in dense networks where node just need coarse accuracy. Approximate point in triangulation test used point-in-triangulation test (PIT) to narrow down the possible area in which an unknown node resides and then compute the centroid of polygons (He et al., 2003). Ye-Hua et al. (2009a) presented a distributed localization algorithm based on hybrid taboo search (DBHTS). Its optimization procedure was performed by using a hybrid of taboo search and simulated annealing (Ye-Hua et al., 2009b). General speaking, all of them use a subset of information (local information) to localize unknown node.
Range-based localization method: Range-based localization methods depended on distance or angle between nodes to obtain unknown node’s location. The first step is distance estimates and angle estimates. A number of approaches, such as time of arrival, time difference of arrival, angle of arrival, received signal strength, have been presented (Srinivasan and Wu, 2007). The second step is location calculations. trilateration, triangulation and maximum likelihood estimation are typical methods (Srinivasan and Wu, 2007). Range-based localization methods have the advantage of fine resolution. However, extra hardware and additional energy consumption restricted the application of range-based methods.
Range-free localization method: Range-free localization methods use the information of topology and connectivity for location estimation. Range-free methods have some advanced characteristics, such as low cost, small communication traffic, no extra hardware and flexible localization precision. Because of these special characteristics of range-free methods, they were been regard as a promising solution for the localization problem in WSN.
Centroid localization, DV-Hop localization, amorphous localization and APIT are typical algorithms. In DV-Hop, nodes calculate their position based on anchor locations, the hops from anchor and the average distance per hop (Srinivasan and Wu, 2007). Amorphous positioning algorithm uses offline hop-distance estimations, improving location estimates through a neighbor-information exchange (He et al., 2005).
Absolute localization method: Most of absolute localization is GPS-based localization. GPS-based localization requires sensor equipped with GPS receiver (Srinivasan and Wu, 2007). As mentioned before on this paper, only a small subset of nodes will equip with GPS receiver act as beacon nodes for reference. An absolute coordinate system will define by these reference nodes. In addition, coordinates in absolute coordinate system can be obtained from those in relative coordinate system by a simple linear transformation and some reference nodes. In short, the result of absolute localization is easy to be understood and used by users.
Relative localization method: The aim of relative localization was to obtain the relationship of distance or angle between nodes. Its distance is relative, not absolute, the same to angle. A relative coordinate system will define by manual configuration or some reference nodes. This approach effectively reduces overhead introduced by GPS receiver. The reason of relative localization became research hotspot: (a) relative localization can meet part users’ needs and (b) it is a preparation for absolute localization.
LOCALIZATION ALGORITHMS COMPARISON
First, we describe additional criteria which are used in this comparison and then we present our comparison.
Additional criteria
Self-organized: Because of the lack of localization infrastructure
in wireless sensor network, the self-organization of localization algorithm
is necessary.
Robustness: Localization algorithm is immune to node failure and distance estimation error.
Efficient energy: Message exchange is an indicator of energy consumption. How much communication overhead is required?
Distributed calculation: Does localization algorithm only uses localized information?
| Table 1: | Characteristics of localization techniques |
Scalability: Is a localization algorithm scalable to the number of nodes in network?
Comparison: Table 1 presents different localization algorithms’ advantages and disadvantages. Hence, we need to choose a suitable location algorithm for different applications of wireless sensor networks.
DIRECTIONS OF FUTURE RESEARCH
It has been shown that there are a number of location algorithms in wireless sensor networks. However, there still exist some interesting problems that need to be addressed in the future research.
| • | Thought energy efficiency and accuracy have been researched extensively, the security metric has drawn the attention of researchers only recently and as such has not been addressed adequately (Srinivasan and Wu, 2007) |
| • | Low-cost GPS-based location: With ever increasing advancement in MEME(Micro-Electro-Mechanical System) and manufacturing industry, inexpensive and low energy-consumption GPS location hardware will be widely used |
| • | Location relay on some sort of message exchange between nodes, the same to time synchronization and routing. Therefore, cross-layer scheme may be proposed by exploiting the ability of message exchange between nodes. Range-based clock synchronization (Li et al., 2009b) is a typical example. |
CONCLUSION
Location in wireless sensor network is a hot area of research. In this article, we presented a comprehensive survey of location techniques.
Overall, the location techniques can be classified into centralized method, distributed method, range-based method, range-free method, absolute localization method, relative localization method. We highlight the design of different kind of methods, as well as the advantages and disadvantages of each algorithm. Although many of location algorithms look promising, there are still many challenges that need to be solved. We pinpoint future research directions in this survey.
ACKNOWLEDGMENTS
This research is supported by Natural Science Research Fund of Hunan Provincial Education Department: Cross-layer research on time synchronization in multimedia wireless sensor network.