Theory and Algorithms on Localization in Wireless Sensor Networks

As a basis of many network protocols and applications, localization is one of the major supportive technologies for wireless sensor networks, making it an indispensable part in the design of wireless sensor networks. In this paper, we comprehensively survey the recent advancements of the theory and algorithms on localization. We completely summarize the following aspects on localization theory. Firstly, we describe the formal definition of localization problem. Then, we analyze the computational complexity of the localization problem under various configurations. Next, we introduce the localization theory, which is developed from the rigidity theory. Finally, we present a special kind of location computable network: sequentially localizable network. In a global view, the study of localization theory is the basis of all the achievements, which not only shows great insights on the localization problem, but also further solves many fundamental problems of localization, especially in two-dimensional case. By localization theory, a lot of new localization algorithms are proposed. We also conclude the typical localization algorithms related to localization theory. We place special emphasis on their design ideas, as well as the application scope and disadvantage, for each localization algorithm. Finally, we point out the possible directions in both localization theory and localization algorithm for further research.