Localization is a fundamental challenge of wireless sensor networks in many applications because a set of nodes must be aware of individual positions, based only on their own resources, i.e. without the aid of external agents. This problem has been tackled using different approaches that provide good solutions under specific circumstances. Nevertheless, new conditions, including massive node deployment or irregular topologies, call for further study and development.
TopIntroduction
A Wireless Sensor Network (WSN) is essentially a large number of small sensing self-powered nodes which gather information and communicate in a wireless fashion, with a common end goal. For a general review of the characteristics, applications and communication protocols in WSNs, see surveys in Akyildiz, Su, Sankarasubramaniam and Cayirci (2002) and Yick, Mukherjee and Ghosal (2008).
Wireless Sensor Networks represent an emerging technology with a wide spectrum of potential applications and, at the same time, they are also a source of challenging problems. One such challenging problem is how to accurately find the location of each sensor node. Node localization is important because it can enable new WSN applications. For example, with node localization capability, monitoring systems can determine the specific source of a critical event. Node localization capability can also be used to enhance the operation of a WSN. For example, a node can forward packets to its final destination, based solely on the position of the nodes that make up its neighborhood (Marcelín-Jiménez, 2007). This routing strategy fosters local work and limits energy consumption.
To solve the node localization problem, a global positioning system (GPS) may provide a good starting point. Nevertheless, the utilization of a GPS is strongly limited by budgetary constraints and it is not recommended for indoor systems where satellite reception can be poor.
For a small set of nodes, individual positions can be programmed manually. In some other cases, a mobile node exists which is always aware of its position and performs a comprehensive tour across the underlying network in order to inform each node about its particular location. Nevertheless, when nodes are randomly placed, the number of nodes is massive, or a mobile “supervisor” is unfeasible; an automatic procedure is required. Moreover, since node localization is a fundamental operation in WSNs, the solution to the localization problem needs to comply with several attributes including accuracy, efficiency and robustness.
A set of very fine survey papers on localization is: Mao, Fidan and Anderson (2007); Pestana-Leao and Rodríguez-Peralta (2007); Langendoen and Reijers (2003); Patwari (2005). Nevertheless, recent results have arisen which justify revisiting this subject. This chapter focuses on automatic localization procedures, where the solution is built from the information each node has about its surroundings. There is not an external entity with a complete view of the landscape that can help each node know its coordinates. Instead, nodes solve the problem by themselves.
The rest of this chapter includes the following sections: Section THE PROBLEM formally states the subject. There are two main sources of addressing localization: graph theory and optimization; we present both approaches. Throughout the remaining subsections, we will see how these complementary views may be correlated in order to tackle the difficult parts of this problem. We provide a short description of distance measurement techniques. As we will see, obtaining measurements of the distance between each couple of sensor nodes is a necessary condition to find a solution to the node localization problem. Next, we classify solutions to the localization problem into two categories: centralized and distributed. Since measurements have intrinsic noise, we will describe methods that can be used to determine the errors bounds associated to the localization problem. We end this section by reviewing the necessary conditions to find a unique solution to the localization problem. When such conditions are not satisfied, the problem turns to be NP-complete. Section ALTERNATIVES gathers the most important results and new trends on the subject. We also point out some of the emerging approaches to solve the localization problem. Finally, in CONCLUSION we summarize our findings.