Localization in Wireless Sensor Networks: Solvability Improvement Technique Using Priori Information from Sensing Data and Network Properties in Unit Disk Graph Model

Abstract:

From the theoretical point of view, network localization can be viewed as finding a unique solution from distances constraint among points. The one of the difficulties is that even if the network is uniquely localizable, it is proven to be an NP-Hard [1]. It is also true that the network graph has to be sufficiently dense [2]. This poses even more challenges to the original problem as we often work on sparse networks. To cope with this, in [3], we introduce priori knowledge to assist the process of finding the unique localization solution. It helps to speed up the searching algorithm; however, the ambiguity still exists among sparse networks. In this paper we try to bring as much priori knowledge as possible to assist or to be used as constraints. Hopefully this will reduce search space and reach the unique solution quickly. In clean environment, this extra info will, by some magnitude, bring the graph closer to the unique answer. We start from integer-coordinate noise-free position and then add sources of priori knowledge. Then we examine the case where assisted data can be noisy. A search is used within the noisy but useful constraint. The justification of using the assisted knowledge is from the practical uses of some networks, e.g. sensor network, where other measurements are available and they are often correlated and can be helpful in determining the positions.

• Periodical: Advanced Materials Research (Volumes 931-932)
• Pages: 999-1003
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.931-932.999
• Online since: May 2014
• Authors: Phisan Kaewprapha*
• Keywords: Constraint Search, Localization, Non-Linear Optimization, Random Network, Wireless Sensor Network (WSN)

References

[1] Heinz Breu, David G. Kirkpatrick, Unit disk graph recognition is NP-hard, Computational Geometry, Volume 9, Issues 1–2, January (1998).

DOI: 10.1016/s0925-7721(97)00014-x

[2] Aspnes, J.; Eren, T.; Goldenberg, D.K.; Morse, A.S.; Whiteley, W.; Yang, Y.R.; Anderson, B. D O; Belhumeur, P.N., A Theory of Network Localization, Mobile Computing, IEEE Transactions on , vol. 5, no. 12, p.1663, 1678, Dec. (2006).

DOI: 10.1109/tmc.2006.174

[3] Kaewprapha, P.; Jing Li; Puttarak, N., Multi-hop network localization in multi-radius unit disk graph model, Wireless Communications & Signal Processing (WCSP), 2012 International Conference on , vol., no., p.1, 6, 25-27 Oct. (2012).

DOI: 10.1109/wcsp.2012.6542944

[4] Zhen Hu; Dongbing Gu; Zhengxun Song; Hongzuo Li, Localization in wireless sensor networks using a mobile anchor node, Advanced Intelligent Mechatronics, 2008. AIM 2008. IEEE/ASME International Conference on , vol., no., p.602, 607, 2-5 July (2008).

DOI: 10.1109/aim.2008.4601728

[5] A Pal, Localization algorithms in wireless sensor networks: Current approaches and future challenges, Network Protocols and Algorithms, Vol. 2, No. 1.

DOI: 10.5296/npa.v2i1.279

[6] S. Lee, H. Woo, and C Lee, Wireless sensor network localization with connectivity-based refinement using mass spring and Kalman filtering, EURASIP J Wireless Commun. and Networking, pp.1-11, (2012).

DOI: 10.1186/1687-1499-2012-152

[7] Biswas, P. and Ye, Y. Semidefinite programming for ad hoc wireless sensor network localization, 3rd Intl. Symp. Inf. Processing in Sensor Net. pp.46-54, (2004).

DOI: 10.1145/984622.984630

[8] Guoqiang Mao, Barış Fidan, Brian D.O. Anderson, Wireless sensor network localization techniques, Computer Networks, Volume 51, Issue 10, 11 July (2007).

DOI: 10.1016/j.comnet.2006.11.018

[9] Zhong Zhou; Zheng Peng; Jun-Hong Cui; Zhijie Shi; Bagtzoglou, A.C., Scalable Localization with Mobility Prediction for Underwater Sensor Networks, Mobile Computing, IEEE Transactions on , vol. 10, no. 3, p.335, 348, March (2011).

DOI: 10.1109/tmc.2010.158