Wireless Sensor Network Node Localization  Based on Differential Evolution

doi:10.3969/j.issn.1000-3428.2013.11.017

Abstract

Abstract: This paper proposes a node localization algorithm for Wireless Sensor Network(WSN) based on Differential Evolution(DE). The proposed algorithm constructs objective function according to the error of estimated distance from measured distance between neighboring nodes, and uses DE algorithm to find optimal solutions to the objective function. When the algorithm finds optimal solutions, it gets the estimated coordinates of unknown nodes. Experimental result shows that the localization accuracy of the proposed algorithm is less than 5% when the percentage of anchor nodes is 10% and the transmission range R of nodes is 1.8r, and the proposed algorithm can achieve higher localization accuracy than Semi-definite Programming(SDP) with gradient search localization algorithm.

Key words: Wireless Sensor Network(WSN), Differential Evolution(DE), node localization, range-based, localization accuracy, Semi- definite Programming(SDP)

摘要： 针对无线传感器网络(WSN)节点的定位问题，提出一种基于差分演化的WSN节点定位算法。根据相邻节点间估计距离和测量距离之间的偏差构造目标函数，利用差分演化算法求出函数的最优解，达到最优解时的节点坐标即为未知节点的估计坐标。实验结果表明，该算法在锚节点比例为10%，节点无线通信半径R为1.8r的情况下，平均定位误差不超过5%，与带梯度搜索的半定规划定位算法相比，其定位精度更高。

关键词: 无线传感器网络, 差分演化, 节点定位, 基于测距, 定位精度, 半定规划

CLC Number:

TP393

ZHANG Qing-guo, WANG Jing-hua, ZHANG Wei. Wireless Sensor Network Node Localization Based on Differential Evolution[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2013.11.017.

张清国，王敬华，张维. 基于差分演化的无线传感器网络节点定位[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2013.11.017.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2013.11.017

http://www.ecice06.com/EN/Y2013/V39/I11/78

References

参考文献 [1] 王福豹, 史龙, 任丰原. 无线传感器网络中的自身定位系统和算法[J]. 软件学报, 2005, 16(5): 857-868. [2] Nicolescu D, Nath B. Ad-Hoc Positioning Systems(APS)[C]// Proc. of Global Telecommunications Conference. San Antonio, USA: [s. n.], 2001. [3] Avvides A, Park H, Srivastava M B. The Bits and Flops of the N-hop Multilateration Primitive for Node Localization Problems[C]//Proc. of the 1st ACM Int’l Workshop on Wireless Sensor Networks and Applications. Atlanta, USA: ACM Press, 2002. [4] Doherty L, Pister K S J, Ghaoui L E. Convex Position Estimation in Wireless Sensor Networks[C]//Proc. of IEEE INFOCOM’01. [S. l.]: IEEE Press, 2001. [5] Shang Yi, Ruml W, Zhang Ying, et al. Localization from Mere Connectivity[C]//Proc. of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing. Annapolis, USA: ACM Press, 2003. [6] Bulusu N, Heidemann J, Estrin D. GPS-less Low Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications Magazine, 2000, 7(5): 28-34. [7] Bergamo P, Mazzini G. Localization in Sensor Networks with Fading and Mobility[C]//Proc. of the 13th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications. Lisbon, Portugal: IEEE Communications Society, 2002. [8] Cheng K, Tam V, Lui K. Improving APS with Anchor Selection in Anisotropic Networks[C]//Proc. of the International Conference on Networking and Services. Los Alamitos, USA: [s. n.], 2005. [9] Savarese C, Rabay J, Langendoen K. Robust Positioning Algorithms for Distributed Ad-hoc Wireless Sensor Networks[C]//Proc. of the General Track of the Annual Conference on USENIX Annual Technical Conference. Monterey, USA: USENIX Press, 2002. [10] Savarese C, Rabaey J M, Beutel J. Locationing in Distributed Ad-hoc Wireless Sensor Network[C]//Proc. of ICASSP’01. Salt Lake City, USA: [s. n.], 2001. [11] Biswas P, Lian Tzn-Chen, Wang Ta-Chung, et al. Semide?nite Programming Based Algorithms for Sensor Network Localization[J]. ACM Transactions on Sensor Networks, 2006, 2(2): 188-220. [12] Gotsman C, Koren Y. Distributed Graph Layout for Sensor Networks[J]. Journal of Graph Algorithms and Applications, 2005, 9(3): 327-346. [13] Nawaz S, Jha S. A Graph Drawing Approach to Sensor Network Localization[C]//Proc. of the 4th IEEE Conference on Mobile Adhoc and Sensor Systems. Pisa, Italy: [s. n.], 2007. [14] Bertsekas D P. Nonlinear Programming[M]. 2nd ed. [S. l.]: Athena Scientific, 1999. [15] Zhang Qingguo, Wang Jinghua, Jin Cong, et al. Genetic Algorithm Based Wireless Sensor Network Locali- zation[C]//Proc of the 4th International Conference on Natural Computation. Jinan, China: [s. n.], 2008. [16] Kannan A A, Mao Guoqiang, Vucetic B. Simulated Annealing Based Localization in Wireless Sensor Network Localization with Flip Ambiguity Mitigation[C]//Proc. of the 63rd IEEE Vehicular Technology Conference. Melbourne, Australia: IEEE Press, 2006. [17] 蔡绍滨, 高振国, 潘海为, 等. 带有罚函数的无线传感器网络粒子群定位算法[J]. 计算机研究与发展, 2012, 49(6): 1228-1234. [18] Storn R, Price K. Differential Evolution——A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces[J]. Journal of Global Optimization, 1997, 11(4): 341- 359. [19] Nissanka B P, Chakraborty A, Balakrishnan H. The Cricket Location-support System[C]//Proc. of the 6th Annual International Conference on Mobile Computing and Networking. New York, USA: ACM Press, 2000. [20] Noman N, Iba H. Enhancing Differential Evolution Per- formance with Local Search for High Dimensional Function Optimization[C]//Proc. of GECCO’05. New York, USA: ACM Press, 2005. 编辑任吉慧

Please choose a citation manager

Content to export