无线传感器网络优化部署及仿真研究
摘要
无线传感器网络是近年来研究的热点领域之一,被评为21世纪最重要、最有发展前景的技术之一,将会对人类生活产生非常重要的影响。无线传感器网络技术综合了传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术等众多技术领域,结合了各个交叉学科的前沿技术,具有广阔的研究空间,吸引了大批学者。
合理地进行网络节点部署,可以改善传感器网络监测的覆盖范围,提高感知数据的精确度,大幅度降低节点能耗。本文旨在研究无线传感器网络优化部署及覆盖问题,即在传感区域内如何优化布置节点以达到增加网络覆盖度的目的。
本文主要的研究内容包括两个方面:(1)无线传感器网络的优化部署。介绍了当前的网络部署研究现状和现有的传感器优化部署算法。并对其中的一种算法进行详细介绍,编写程序仿真,对仿真结果分析比较。针对该算法的不足对其做了一定的改进,结果表明改进算法增加了节点传感区域的覆盖度和覆盖率,限制了节点的移动距离,节省了节点重新部署消耗的能量,达到延长节点生存期的效果。(2)异构无线传感器网络中超级节点的位置部署。异构网络部署,即在传感区域内增加一些具有足够能量的有线或者无线传输方式的超级节点,作为邻近节点的汇聚节点收集数据,直接和汇聚节点通信,极大地减少网络传感数据的平均传输路径,从而节省能耗、提高网络生命期。文中通过二维网格建立一个数学模型,使用基于整数目标规划的遗传算法求模型的最优解,得到超级节点的部署位置,并对结果进行分析。
Wireless sensor networks are a hot area of research in recent years, which was rated as the most important technology in 21st century, and one of the best prospects for development of technology, will have a very significant impact on human life. Wireless sensor network technology integrates sensor technology, embedded computing technology, distributed information processing and communication technology and other technical fields, has broad research space, and attracts a large number of scholars.
Reasonable deployment of sensors can improve the coverage of monitoring sensor networks, the accuracy of data and greatly reduce sensor’s energy consumption. This paper aims to evaluate the optimal deployment of wireless sensor network coverage, and how to optimize the layout of Sensors in the sensor region for the sake of increasing the network coverage.
This paper covers two sides content: (1) Optimal deployment of wireless sensor networks. Summarize current optimization deployment algorithms of sensor network. Introduce the virtual force algorithm in details, simulate, analyze and compare the simulation results. In view of the algorithm's disadvantage, this paper improves it. Results show that improved algorithm can increase the coverage, reduce re-deployment energy consumption, prolong life cycle of nodes. (2) Heterogeneous wireless sensor networks deployment with super-nodes. Heterogeneous network deployment means that some super-nodes added into sensor region with sufficient energy and wired or wireless transmission. Super-nodes can collect sensing data from nodes around it, and directly communication with cluster-node. They can greatly reduce network transmission path, thereby saving energy, and improve network life cycle.
合理地进行网络节点部署,可以改善传感器网络监测的覆盖范围,提高感知数据的精确度,大幅度降低节点能耗。本文旨在研究无线传感器网络优化部署及覆盖问题,即在传感区域内如何优化布置节点以达到增加网络覆盖度的目的。
本文主要的研究内容包括两个方面:(1)无线传感器网络的优化部署。介绍了当前的网络部署研究现状和现有的传感器优化部署算法。并对其中的一种算法进行详细介绍,编写程序仿真,对仿真结果分析比较。针对该算法的不足对其做了一定的改进,结果表明改进算法增加了节点传感区域的覆盖度和覆盖率,限制了节点的移动距离,节省了节点重新部署消耗的能量,达到延长节点生存期的效果。(2)异构无线传感器网络中超级节点的位置部署。异构网络部署,即在传感区域内增加一些具有足够能量的有线或者无线传输方式的超级节点,作为邻近节点的汇聚节点收集数据,直接和汇聚节点通信,极大地减少网络传感数据的平均传输路径,从而节省能耗、提高网络生命期。文中通过二维网格建立一个数学模型,使用基于整数目标规划的遗传算法求模型的最优解,得到超级节点的部署位置,并对结果进行分析。
Wireless sensor networks are a hot area of research in recent years, which was rated as the most important technology in 21st century, and one of the best prospects for development of technology, will have a very significant impact on human life. Wireless sensor network technology integrates sensor technology, embedded computing technology, distributed information processing and communication technology and other technical fields, has broad research space, and attracts a large number of scholars.
Reasonable deployment of sensors can improve the coverage of monitoring sensor networks, the accuracy of data and greatly reduce sensor’s energy consumption. This paper aims to evaluate the optimal deployment of wireless sensor network coverage, and how to optimize the layout of Sensors in the sensor region for the sake of increasing the network coverage.
This paper covers two sides content: (1) Optimal deployment of wireless sensor networks. Summarize current optimization deployment algorithms of sensor network. Introduce the virtual force algorithm in details, simulate, analyze and compare the simulation results. In view of the algorithm's disadvantage, this paper improves it. Results show that improved algorithm can increase the coverage, reduce re-deployment energy consumption, prolong life cycle of nodes. (2) Heterogeneous wireless sensor networks deployment with super-nodes. Heterogeneous network deployment means that some super-nodes added into sensor region with sufficient energy and wired or wireless transmission. Super-nodes can collect sensing data from nodes around it, and directly communication with cluster-node. They can greatly reduce network transmission path, thereby saving energy, and improve network life cycle.
引文
[1]任丰原,黄海宁,林闯.无线传感器网络.软件学报, 2003, 14(7) : 1282～1291
[2] Vardhan S, Wilczynski M, Portie G.J et al. Wireless integrated network sensors (WINS) : distributed in situ sensing for mission and flight systems. Aerospace Conference Proceedings 2000 IEEE. 2000: 459～463
[3] Kahn M, Katz RH, Pister KSJ. Next Century Challenges: Mobile Networking for "Smart Dust ". J of Common and Networks, 2000, 2(3)
[4] Intanagonwiwat C, Govindan R, Estrin D et al. Directed Diffusion for Wireless Sensor Networking. IEEE/ACM Transactions on Networking, 2003, 11(1) : 2～16
[5] Manjeshwar A, Agrawal D.P. TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. Parallel and Distributed Processing Symposium. 2001: 2009～2015
[6] Lindsey S, Raghavendra C.S. PEGASIS: Power-Efficient Gathering in Sensor Information Systems. Aerospace Conference Proceedings of IEEE. 2002: 1125～1130
[7]孙利民,李建中,陈渝等.无线传感器网络.北京:清华大学出版社, 2005
[8]王金龙,王呈贵,吴启晖等. Ad Hoc移动无线网络.北京:国防工业出版社, 2004
[9]李志刚,周兴社.传感器网络.计算机应用研究, 2004(12) : 9～12
[10]王鸿彦.基于有限能量的无线传感器网络协议研究:硕士学位论文.南京:河海大学, 2005
[11]叶驰,孙利民,廖勇.传感器网络的能量管理.计算机工程与应用, 2004(8) : 196～198
[12] Saltzer, Reed D, Clark D. End-to-End arguments in system design. ACM Transactions on Computer System, 1984, 2(4) : 195～206
[13]马祖长,孙怡宁,梅涛.无线传感器网络综述.通信学报, 2004, 25(4) : 114～124
[14] CrossBow. XBOW_Smart_Dust_ProductInfoGuide. 2005
[15]中科院计算所信息网络室. GAINS节点产品白皮书. 2005
[16] Polastre JR. Design and Implementation of Wireless Sensor Networks for Habitat Monitoring. 2003
[17]沈东方.无线传感器网络的节能研究.大众科技, 2006(5) : 87～88
[18]刘丽萍,王智,孙优闲.无线传感器网络部署及其覆盖问题研究.电子与信息学报, 2006, 28(9) : 1752～1757
[19]任彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法.软件学报, 2006, 17(3) : 422～433
[20] Qi H, Iyengar SS, Chakrabarty K. Multi-resolution data integration using mobile agents in distributed sensor networks. Man and Cybernetics (Part C) , 2001, 31: 383～391
[21] Musman SA, Lehner PE, Elsaesser C. Sensor Planning for Elusive Targets. Journal of Computer & Mathematical Modeling, 1997, 25(3) : 103～115
[22] Howard A, MJ Matari'c, Sukhatme GS. Mobile Sensor Network Deployment Using Potential Field: a distributed scalable solution to the area coverage problem. International Conference on Distributed Autonomous Robotic Systems, 2002
[23] Meguerdichian S, Slijepcevic S, Karayan V et al. coverage problems in wireless ad-hoc sensor networks. IEEE Infocom, 2001, 3: 1380～1387
[24] Priyantha NB, Chakraborty A, Balakrishnan H. The cricket location support system. 2000: 32～43
[25] Chakrabarty K, Iyengar SS, Qi H et al. Grid coverage for surveillance and target location in distributed sensor networks. IEEE Transactions on Computers, 2002, 51: 1448～1458
[26] Chakrabarty K, Iyengar SS, Qi H et al. Coding Theory Framework for Target Location in Distributed Sensor Networks. Coding and Computing, 2001: 130～134
[27] Liu L P, Xia F, Wang Z. Deployment issues in wireless sensor networks. Proceedings of the First International Conference on Mobile Ad-Hoc and SensorNetworks. 2005: 239～248
[28]汪学清,杨永田.一种基于虚拟菱形网格的传感器节点布置算法.计算机应用, 2006, 26(7) : 1554～1556
[29]刘丽萍,曹峰,王智等.基于嵌套网格的无线传感器网络节能部署算法.信息与控制, 2006, 35(2) : 154～160
[30] Zou Y, Chakrabarty K. Sensor Deployment and Target Localization Based on Virtual Forces. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. New York USA, 2003: 1293～1303
[31] Chitradurga R, Helmy A. Analysis of Wired Short Cuts in Wireless Sensor Networks. The IEEE/ACS International Conference on Pervasive Services (ICPS'04) . 2004: 167～176
[32] Mhatte V, Rosenberg C, Kofman D et al. A minimum cost heterogeneous sensor network with a lifetime constraint. IEEE Trans on Mobile Computing, 2005: 1～4
[33] Yarvis M, Kushalnagar N, Singh H et al. Exploiting Heterogeneity in Sensor Networks. The IEEE International Conference on Computer Communiation. 2005: 878～890
[34]黄刘生,张波,徐宏力等.无线传感器网络节点随机配置的覆盖和连通研究.计算机应用, 2006, 26(11) : 22～24
[35]宋光明,庄伟,魏志刚等.用于未知环境的移动传感器网络自部署算法.华南理工大学学报, 2006, 34(9) : 26～30
[36] Howard A, MJMatari'c, Sukhatme GS. Mobile Sensor Network Deployment Using Potential Field: a distributed scalable solution to the area coverage problem. International Conference on Distributed Autonomous Robotic Systems, 2002
[37] Locateli M, Raber U. Packing equal circles in a square: a deterministic global optimization approach. Discrete Applied Mathematics, 2002, 122: 139～166
[38]周正.无线传感器网络的节点自定位技术.中兴通讯技术, 2005, 11(4) : 51～56
[39] Jain R, Puri A, Sengupta R. Geographical routing using partial information for wireless Ad Hoc networks. IEEE Personal Communications, 2001: 48～57.
[40]王小平,曹立明.遗传算法--理论、应用与软件实现.西安:西安交大出版社,2002: 1～15.
[41]飞思科技产品研发中心. Matlab 6. 5应用接口编程.北京:电子工业出版社,2002
[42]崔莉,鞠海玲,苗勇等.无线传感器网络研究进展.计算机研究与发展, 2005, 42(1) : 163～174
[43] Sharma G, Mazumdar R. Hybrid sensor networks: a small world. Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, 2005
[44] Zhang H, Hou J C. Maintaining Sensing Coverage and Connectivity in Large Sensor Networks. University of Illinois at Urbana Cham paign UIUC Computer Science Technical Report, 2004
[45] Wang G, Cao G, La Porta T. Movement-Assisted Sensor Deployment. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies. 2004: 2469～2479
[46]曹峰,刘丽萍,王智.能量有效的无线传感器网络部署.信息与控制,2006, 35(2) : 148～153
[2] Vardhan S, Wilczynski M, Portie G.J et al. Wireless integrated network sensors (WINS) : distributed in situ sensing for mission and flight systems. Aerospace Conference Proceedings 2000 IEEE. 2000: 459～463
[3] Kahn M, Katz RH, Pister KSJ. Next Century Challenges: Mobile Networking for "Smart Dust ". J of Common and Networks, 2000, 2(3)
[4] Intanagonwiwat C, Govindan R, Estrin D et al. Directed Diffusion for Wireless Sensor Networking. IEEE/ACM Transactions on Networking, 2003, 11(1) : 2～16
[5] Manjeshwar A, Agrawal D.P. TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. Parallel and Distributed Processing Symposium. 2001: 2009～2015
[6] Lindsey S, Raghavendra C.S. PEGASIS: Power-Efficient Gathering in Sensor Information Systems. Aerospace Conference Proceedings of IEEE. 2002: 1125～1130
[7]孙利民,李建中,陈渝等.无线传感器网络.北京:清华大学出版社, 2005
[8]王金龙,王呈贵,吴启晖等. Ad Hoc移动无线网络.北京:国防工业出版社, 2004
[9]李志刚,周兴社.传感器网络.计算机应用研究, 2004(12) : 9～12
[10]王鸿彦.基于有限能量的无线传感器网络协议研究:硕士学位论文.南京:河海大学, 2005
[11]叶驰,孙利民,廖勇.传感器网络的能量管理.计算机工程与应用, 2004(8) : 196～198
[12] Saltzer, Reed D, Clark D. End-to-End arguments in system design. ACM Transactions on Computer System, 1984, 2(4) : 195～206
[13]马祖长,孙怡宁,梅涛.无线传感器网络综述.通信学报, 2004, 25(4) : 114～124
[14] CrossBow. XBOW_Smart_Dust_ProductInfoGuide. 2005
[15]中科院计算所信息网络室. GAINS节点产品白皮书. 2005
[16] Polastre JR. Design and Implementation of Wireless Sensor Networks for Habitat Monitoring. 2003
[17]沈东方.无线传感器网络的节能研究.大众科技, 2006(5) : 87～88
[18]刘丽萍,王智,孙优闲.无线传感器网络部署及其覆盖问题研究.电子与信息学报, 2006, 28(9) : 1752～1757
[19]任彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法.软件学报, 2006, 17(3) : 422～433
[20] Qi H, Iyengar SS, Chakrabarty K. Multi-resolution data integration using mobile agents in distributed sensor networks. Man and Cybernetics (Part C) , 2001, 31: 383～391
[21] Musman SA, Lehner PE, Elsaesser C. Sensor Planning for Elusive Targets. Journal of Computer & Mathematical Modeling, 1997, 25(3) : 103～115
[22] Howard A, MJ Matari'c, Sukhatme GS. Mobile Sensor Network Deployment Using Potential Field: a distributed scalable solution to the area coverage problem. International Conference on Distributed Autonomous Robotic Systems, 2002
[23] Meguerdichian S, Slijepcevic S, Karayan V et al. coverage problems in wireless ad-hoc sensor networks. IEEE Infocom, 2001, 3: 1380～1387
[24] Priyantha NB, Chakraborty A, Balakrishnan H. The cricket location support system. 2000: 32～43
[25] Chakrabarty K, Iyengar SS, Qi H et al. Grid coverage for surveillance and target location in distributed sensor networks. IEEE Transactions on Computers, 2002, 51: 1448～1458
[26] Chakrabarty K, Iyengar SS, Qi H et al. Coding Theory Framework for Target Location in Distributed Sensor Networks. Coding and Computing, 2001: 130～134
[27] Liu L P, Xia F, Wang Z. Deployment issues in wireless sensor networks. Proceedings of the First International Conference on Mobile Ad-Hoc and SensorNetworks. 2005: 239～248
[28]汪学清,杨永田.一种基于虚拟菱形网格的传感器节点布置算法.计算机应用, 2006, 26(7) : 1554～1556
[29]刘丽萍,曹峰,王智等.基于嵌套网格的无线传感器网络节能部署算法.信息与控制, 2006, 35(2) : 154～160
[30] Zou Y, Chakrabarty K. Sensor Deployment and Target Localization Based on Virtual Forces. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. New York USA, 2003: 1293～1303
[31] Chitradurga R, Helmy A. Analysis of Wired Short Cuts in Wireless Sensor Networks. The IEEE/ACS International Conference on Pervasive Services (ICPS'04) . 2004: 167～176
[32] Mhatte V, Rosenberg C, Kofman D et al. A minimum cost heterogeneous sensor network with a lifetime constraint. IEEE Trans on Mobile Computing, 2005: 1～4
[33] Yarvis M, Kushalnagar N, Singh H et al. Exploiting Heterogeneity in Sensor Networks. The IEEE International Conference on Computer Communiation. 2005: 878～890
[34]黄刘生,张波,徐宏力等.无线传感器网络节点随机配置的覆盖和连通研究.计算机应用, 2006, 26(11) : 22～24
[35]宋光明,庄伟,魏志刚等.用于未知环境的移动传感器网络自部署算法.华南理工大学学报, 2006, 34(9) : 26～30
[36] Howard A, MJMatari'c, Sukhatme GS. Mobile Sensor Network Deployment Using Potential Field: a distributed scalable solution to the area coverage problem. International Conference on Distributed Autonomous Robotic Systems, 2002
[37] Locateli M, Raber U. Packing equal circles in a square: a deterministic global optimization approach. Discrete Applied Mathematics, 2002, 122: 139～166
[38]周正.无线传感器网络的节点自定位技术.中兴通讯技术, 2005, 11(4) : 51～56
[39] Jain R, Puri A, Sengupta R. Geographical routing using partial information for wireless Ad Hoc networks. IEEE Personal Communications, 2001: 48～57.
[40]王小平,曹立明.遗传算法--理论、应用与软件实现.西安:西安交大出版社,2002: 1～15.
[41]飞思科技产品研发中心. Matlab 6. 5应用接口编程.北京:电子工业出版社,2002
[42]崔莉,鞠海玲,苗勇等.无线传感器网络研究进展.计算机研究与发展, 2005, 42(1) : 163～174
[43] Sharma G, Mazumdar R. Hybrid sensor networks: a small world. Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, 2005
[44] Zhang H, Hou J C. Maintaining Sensing Coverage and Connectivity in Large Sensor Networks. University of Illinois at Urbana Cham paign UIUC Computer Science Technical Report, 2004
[45] Wang G, Cao G, La Porta T. Movement-Assisted Sensor Deployment. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies. 2004: 2469～2479
[46]曹峰,刘丽萍,王智.能量有效的无线传感器网络部署.信息与控制,2006, 35(2) : 148～153