无线传感器网络覆盖优化算法的研究
|
摘要
无线传感器网络是随着无线通信和嵌入式计算技术、传感器技术、分布式信息处理技术的进步而发展起来的一种新兴的信息获取技术,是当前在国际上备受关注的、涉及多学科高度交叉的、知识高度集成的前沿热点研究领域。它是一种全新的计算模式,是继Internet之后将对21世纪人类生活方式产生重大影响的IT热点技术,它将逻辑上的信息世界与物理世界融合在一起,将改变人与自然的交互方式。无线传感器网络的应用已经由最初的军事领域扩展到众多民用领域,如环境监测、空间探索、反恐防暴、灾难援救、医疗卫生、智能家居、经济农业、人员定位等。
网络覆盖是无线传感器网络研究和应用的关键性基础问题,是其他网络研究的基础,直接影响着网络的使用性能。网络覆盖在无线传感器网络设计中的重要性与网络连接并列,二者均是网络运行必须解决的基本问题。本文针对节点分布情况和具体应用的不同,提出了提高区域覆盖质量的节点调度算法,和提高对重点目标覆盖质量的算法。
(1)针对覆盖区域节点密集分布的情况,提出了基于K重覆盖保证的无线传感器网络节点调度机制策略,提高了睡眠冗余节点的数量。
(2)针对多数K重覆盖算法是保证区域的覆盖,提出了针对目标的覆盖优化方法,通过虚拟力的作用保证重要目标的多重覆盖。
(3)由于传感器网络的节点能力有限、数目巨大和密集分布的特点决定了必须通过多节点合作感知目标才能提高感知能力,通过这一特点,提出了目标被多个节点合作感知的思想,以提高对目标的感知和覆盖质量。
(4)通过移动节点对盲区进行监测并减少密集区冗余节点的数量,针对这一问题建立了节点移动能量消耗和网络覆盖概率平衡的数学优化模型;最后从理论上提出了一个利用节点的可移动性来改善无线传感器网络覆盖性能的方法。
Wireless sensor networks is a new kind of information access technology, which is formed with the development of wireless communication ,embedded computing technology, sensor technology, MEMS technology, and distributed information processing technology. It is currently cutting-edge and hot research area which is the concern of international arena, and involves a high degree of cross-multidisciplinary of subjects and highly integrated knowledge. It is a new computing model, and it is hot IT technology that will have a significant impact on lifestyle of mankind in the 21st century following the Internet. It will combine the logical world of information and physical world together, and will change the way of interaction between man and nature. The application of wireless sensor networks have been expanded from the original military field to a number of civilian areas, such as environmental monitoring, space exploration, anti-terrorism riot, disaster rescuing, medical care, intelligent furniture, the economical agriculture, personnel orientation.
Network coverage is critical and basic issue for research and application of wireless sensor networks. It is the basis of other network research, directly affecting the network performance. the importance of network coverage in wireless sensor network design and network connections is in the same position. Both of the network to run the basic problems must be solved. In this paper, according to the node distribution and the specific application, the node scheduling algorithm is proposed to improve the quality of the regional coverage, and the multi-covering algorithm is put forward for key objectives.
(1) For the situation that covering regional nodes are densely distributed, wireless sensor network node scheduling strategy is put forward which is based on K re-assurance mechanisms, thus increases the number of sleep redundant nodes.
(2)For the situation that majority of K re-covering algorithm are to ensure regional coverage, coverage optimization method is proposed for the target. The multiple coverage of important goal is ensured through the effect of virtual power
(3)The characteristics of the limited capacity of sensor network nodes, the large number and density decide that the perception capacity only can be improved by multi-node cooperation to perceive objectives. According to this characteristic, the thought that multiple nodes cooperate with each other to improve the perception of targets and coverage quality is formed.
(4) Through the monitoring of mobile node to the blind area, for the problem, mobile node energy consumption and mathematical optimization model for the balance of probability of network coverage are established. Finally, an approach to improve performance of the wireless sensor network coverage is put forward from theory by using the mobility of node.
网络覆盖是无线传感器网络研究和应用的关键性基础问题,是其他网络研究的基础,直接影响着网络的使用性能。网络覆盖在无线传感器网络设计中的重要性与网络连接并列,二者均是网络运行必须解决的基本问题。本文针对节点分布情况和具体应用的不同,提出了提高区域覆盖质量的节点调度算法,和提高对重点目标覆盖质量的算法。
(1)针对覆盖区域节点密集分布的情况,提出了基于K重覆盖保证的无线传感器网络节点调度机制策略,提高了睡眠冗余节点的数量。
(2)针对多数K重覆盖算法是保证区域的覆盖,提出了针对目标的覆盖优化方法,通过虚拟力的作用保证重要目标的多重覆盖。
(3)由于传感器网络的节点能力有限、数目巨大和密集分布的特点决定了必须通过多节点合作感知目标才能提高感知能力,通过这一特点,提出了目标被多个节点合作感知的思想,以提高对目标的感知和覆盖质量。
(4)通过移动节点对盲区进行监测并减少密集区冗余节点的数量,针对这一问题建立了节点移动能量消耗和网络覆盖概率平衡的数学优化模型;最后从理论上提出了一个利用节点的可移动性来改善无线传感器网络覆盖性能的方法。
Wireless sensor networks is a new kind of information access technology, which is formed with the development of wireless communication ,embedded computing technology, sensor technology, MEMS technology, and distributed information processing technology. It is currently cutting-edge and hot research area which is the concern of international arena, and involves a high degree of cross-multidisciplinary of subjects and highly integrated knowledge. It is a new computing model, and it is hot IT technology that will have a significant impact on lifestyle of mankind in the 21st century following the Internet. It will combine the logical world of information and physical world together, and will change the way of interaction between man and nature. The application of wireless sensor networks have been expanded from the original military field to a number of civilian areas, such as environmental monitoring, space exploration, anti-terrorism riot, disaster rescuing, medical care, intelligent furniture, the economical agriculture, personnel orientation.
Network coverage is critical and basic issue for research and application of wireless sensor networks. It is the basis of other network research, directly affecting the network performance. the importance of network coverage in wireless sensor network design and network connections is in the same position. Both of the network to run the basic problems must be solved. In this paper, according to the node distribution and the specific application, the node scheduling algorithm is proposed to improve the quality of the regional coverage, and the multi-covering algorithm is put forward for key objectives.
(1) For the situation that covering regional nodes are densely distributed, wireless sensor network node scheduling strategy is put forward which is based on K re-assurance mechanisms, thus increases the number of sleep redundant nodes.
(2)For the situation that majority of K re-covering algorithm are to ensure regional coverage, coverage optimization method is proposed for the target. The multiple coverage of important goal is ensured through the effect of virtual power
(3)The characteristics of the limited capacity of sensor network nodes, the large number and density decide that the perception capacity only can be improved by multi-node cooperation to perceive objectives. According to this characteristic, the thought that multiple nodes cooperate with each other to improve the perception of targets and coverage quality is formed.
(4) Through the monitoring of mobile node to the blind area, for the problem, mobile node energy consumption and mathematical optimization model for the balance of probability of network coverage are established. Finally, an approach to improve performance of the wireless sensor network coverage is put forward from theory by using the mobility of node.
引文
[1].孙利民,李建中,陈渝,朱红松等.无线传感器网络[M].北京:清华大学出版社,2005.
[2].李晓维,徐勇军,任丰原.无线传感器网络技术[M].北京:北京理工大学出版社,2007.
[3].刘丽萍.无线传感器网络节点覆盖[D].杭州:浙江大学,2006.
[4].刘丽萍,王智,孙优贤.无线传感器网络部署及其覆盖问题研究[J].电子与信息学报,2006,28(9):1752-1758.
[5]. Jason Lester Hill. System Architecture for Wireless Sensor Networks [D].California: University of California, 2003.
[6].饶大展.传感器网络覆盖算法研究[D].杭州:浙江大学,2006.
[7].王鲁鹏.无线传感器网络覆盖与连通问题研究[D].长沙:中南大学.2008.
[8]. O’Rourke J. Artgallery theorem and algorithms [D]. New York: Oxford University Press, 1987.
[9].王殊,阎毓杰,胡富平,屈晓旭.无线传感器网络的理论及应用[M].北京:北京航空航天大学出版社,2007.
[10]. Gao Jun Fan, Shi Yao jin. A simple coverage-evaluating approach for wireless sensor networks with arbitrary sensing areas [J]. Information Processing Letters, 2008, 106(7):159-161.
[11].任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003,14(7):1281—1291.
[12]. Alan Mainwaring, seph Polastre, Robert Szewczyk, etc. Wireless Sensor Networks for Habitat Monitoring[R]. Atlanta: Monitoring. Intl. Workshop on Wireless Sensor Networks and Applications (WSNA’02), 2002.
[13]. Mark Yarvis, Nandakishore Kushalnagar, Harkirat Singh, etc. Exploiting Heterogeneity in Sensor Networks[R]. Miami, FL:IEEE Info Com,2005.
[14]. Di Tian, Nicolas D. Georganas. Connectivity maintenance and coverage preservation in wireless sensor networks[J]. Ad Hoc Networks, 2005, 3(11):744–761.
[15]. Amitabha Ghosh, Sajal K. Das. Coverage and Connectivity Issues in Wireless SensorNetworks[R].A Survey online, 2006.
[16]. Zhang Hong hai, Jennifer C. Hou. Maintaining sensoring coverage and connectivity in large sensor networks[J]. Ad Hoc & Sensor Wireless Networks, 2005, 1(x):89-124.
[17].黄刘生,张波,徐宏力,张俊霞.无线传感器网络节点随机配置的覆盖和连通研究[J].计算机应用,2006,26(11):2567-2569.
[18].毛莺池,周晓峰,王志坚,陈力军.能量感知的无线传感器网络覆盖控制协议[J].微电子学与计算机,2008,25(10):27-29.
[19]. Huang Chi Fu, Tseng Yu Chee. The coverage problem in a wireless sensor network[R]. San Diego: WSNA03, 2003.
[20]. Li Jian zhong, Gao Hong. Survey on sensor network research, Computer Research and Development, v45, n1, January, 2008, p 1-15.
[21]. A Howard, M J Mataric, G S Sukhatme. Mobile sensor network deployment using potential fields : A distributed, scalable solution to the area coverage problem [R]. Japan: 1 The 6th Int’l Symp on Distributed Autonomous Robotics Systems (DARS) , 2002.
[22].于海斌,曾鹏等.智能无线传感器网络系统[M].北京:科学出版社,2006.
[23]. Li zhi Charlie Zhong, Rahul Shah, Chunlong Guo, Jan Rabaey. An Ultra-Low Power and Distributed Access Protocol for Broadband Wireless Sensor Networks [A].IEEE Broadband Wireless Summit [C]. Las Vegas, Nevada. 2001.
[24]. Poduri S, Sukhatme G S. Constrained Coverage in Mobile Sensor Networks[R]. New Orleans: LA.Proc. IEEE. Int. Conf. Robotics and Automation, 2004.
[25]. Zou Y, Chakrabarty K. Sensor deployment and target localization in distributed sensor networks[J]. ACM Trans. on Embedded Computing Systems, 2004,3(1):61?91.
[26]. Wang. X, et al. Integrated coverage and connectivity configuration in wireless sensor networks[R]. Los Argels: SenSys’03: Proceedings of the First International Conference on Embedded Networks Sensor Systems, 2003.
[27].汪学清,杨永田,孙婷,张忠林.无线传感器网络中基于网格的覆盖问题研究.计算机科学,2006,3(11):38-40.
[28]. Liu Jie, Patrick Cheung, Leonidas Guibas, etc.A Dual-space Approach to Tracking and Sensor Management in Wireless Sensor Networks[R]. Palo Alto: Palo Alto ResearchCenter Technical Report P2002-10077, 2002.
[29]. Azzedine Boukerche, Xin Fei, Regina B. Araujo. An optimal coverage-preserving scheme for wireless sensor networks based on local information exchange. Computer Communications [J]. 2007, 30(34): 2708–2720.
[30]. Mihaela Cardei, Jie Wu. Energy-efficient coverage problems in wireless ad-hoc sensor networks [J]. Computer Communications, 2006, 29(6): 413–420.
[31]. Ossama Younis, Marwan Krunz, Srinivasan Ramasubramanian. Location-unaware coverage in wireless sensor networks [J]. Ad Hoc Networks, 2008, 6(7): 1078-1097.
[32].王晟.无线传感器网络节点定位与覆盖控制理论及技术研究[D].武汉:武汉理工大学,2006.
[33].黄铮.无线传感器网路连通与覆盖问题的研究[D].武汉:武汉理工大学,2006.
[34]. J. Chou D. Petrovic, R. Kennan. A distributed and adaptive signal processing approach to reducing energy consumption in sensor networks [A]. In: IEEE INFOCOM 2003[C]. Apri1 2003:1054-1062.
[35].张颖,郭鹏,周宗仪.移动传感器网络覆盖算法研究.计算机工程与科学, 2008,30(2):81-84.
[36].周彤,洪炳鎔,朴松昊.基于虚拟力的混合感知网节点部署.计算机研究与发展,2007,44(6):965-972.
[37]. WANG Xiao-rui, XING Guo-liang, ZHANG Yuan-fang, et al. Integrated coverage and connectivity configuration in wireless sensor net-works[C]//Proc of the ACM International Conference on Embedded Networked Sensor Systems ( SenSys) . New York: ACM Press, 2003:28-39.
[38].王换招,董贝,罗韩梅,陈培军,李增智.基于k-覆盖保证的异构传感器网络节点调度策略.西安交通大学学报,2008,42(8):940-945.
[39].蒋丽萍,王良民,熊书明,詹永照.基于感知概率的无线传感器网络k重覆盖算法.计算机应用研究,2009,26(9):3484-3486.
[40]. LIU Ming, CAO Jian Nong, ZHENG Yuan, CHEN Li-Jun, XIE Li. Analysis for Multi-Coverage Problem in Wireless Sensor Networks. Journal of Software, 2007, 18(1):127?136.
[41].翟正怡.无线传感器网络中的覆盖优化算法与连通问题研究[D].上海:同济大学,2008.
[42]. Cerpa A, Estrin D, ASCENT: adaptive self-configuring sEnsor networks topologies [Al .INFOCOM 2002 Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings[C], June 2002(3):23-27 .
[43]. Okabe, B. Boots, K. Sugihara, S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagram, John Wiley and Sons, New York, 1999.
[44].王雪,王晨,马俊杰.无线传感网络布局的虚拟力导向微粒群优化策略[J].电子学报,2007,35(11):2038-2042.
[45].杨丹.无线传感器网络中维护覆盖和连通的节点调度算法[D].湖南:湖南大学,2008.
[46]. Bang Wang, Wei Wang, V. Srinivasan, and K.C. Chua, Information Coverage for Wireless Sensor Networks [J], IEEE Communications Letters, vol.9, no.11, 2005: 967-969.
[47]. YeF, Zhong G, Lu S et al. PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks [A] The 23rd International Conference on Distributed Computing Systems (ICDCS’03)[C],May 2003.
[48]. Meguerdichian S, Koushanfar F, Potorjak M, etc. Coverage problems in wireless[J]. Ad-hoc sensor networks. Infocom,2001,7(3):1380-1387.
[49].蒋杰.无线传感器网络覆盖控制研究[D].长沙:国防科学技术大学,2005.
[50]. JIN Yan, WANG Ling, YANG Xiao-zong, WEN Dong-xin. Overview of Node Scheduling Algorithm in Wireless Sensor Networks. Journal of Astronautics. 2007, 28(5): 1086-1093.
[2].李晓维,徐勇军,任丰原.无线传感器网络技术[M].北京:北京理工大学出版社,2007.
[3].刘丽萍.无线传感器网络节点覆盖[D].杭州:浙江大学,2006.
[4].刘丽萍,王智,孙优贤.无线传感器网络部署及其覆盖问题研究[J].电子与信息学报,2006,28(9):1752-1758.
[5]. Jason Lester Hill. System Architecture for Wireless Sensor Networks [D].California: University of California, 2003.
[6].饶大展.传感器网络覆盖算法研究[D].杭州:浙江大学,2006.
[7].王鲁鹏.无线传感器网络覆盖与连通问题研究[D].长沙:中南大学.2008.
[8]. O’Rourke J. Artgallery theorem and algorithms [D]. New York: Oxford University Press, 1987.
[9].王殊,阎毓杰,胡富平,屈晓旭.无线传感器网络的理论及应用[M].北京:北京航空航天大学出版社,2007.
[10]. Gao Jun Fan, Shi Yao jin. A simple coverage-evaluating approach for wireless sensor networks with arbitrary sensing areas [J]. Information Processing Letters, 2008, 106(7):159-161.
[11].任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003,14(7):1281—1291.
[12]. Alan Mainwaring, seph Polastre, Robert Szewczyk, etc. Wireless Sensor Networks for Habitat Monitoring[R]. Atlanta: Monitoring. Intl. Workshop on Wireless Sensor Networks and Applications (WSNA’02), 2002.
[13]. Mark Yarvis, Nandakishore Kushalnagar, Harkirat Singh, etc. Exploiting Heterogeneity in Sensor Networks[R]. Miami, FL:IEEE Info Com,2005.
[14]. Di Tian, Nicolas D. Georganas. Connectivity maintenance and coverage preservation in wireless sensor networks[J]. Ad Hoc Networks, 2005, 3(11):744–761.
[15]. Amitabha Ghosh, Sajal K. Das. Coverage and Connectivity Issues in Wireless SensorNetworks[R].A Survey online, 2006.
[16]. Zhang Hong hai, Jennifer C. Hou. Maintaining sensoring coverage and connectivity in large sensor networks[J]. Ad Hoc & Sensor Wireless Networks, 2005, 1(x):89-124.
[17].黄刘生,张波,徐宏力,张俊霞.无线传感器网络节点随机配置的覆盖和连通研究[J].计算机应用,2006,26(11):2567-2569.
[18].毛莺池,周晓峰,王志坚,陈力军.能量感知的无线传感器网络覆盖控制协议[J].微电子学与计算机,2008,25(10):27-29.
[19]. Huang Chi Fu, Tseng Yu Chee. The coverage problem in a wireless sensor network[R]. San Diego: WSNA03, 2003.
[20]. Li Jian zhong, Gao Hong. Survey on sensor network research, Computer Research and Development, v45, n1, January, 2008, p 1-15.
[21]. A Howard, M J Mataric, G S Sukhatme. Mobile sensor network deployment using potential fields : A distributed, scalable solution to the area coverage problem [R]. Japan: 1 The 6th Int’l Symp on Distributed Autonomous Robotics Systems (DARS) , 2002.
[22].于海斌,曾鹏等.智能无线传感器网络系统[M].北京:科学出版社,2006.
[23]. Li zhi Charlie Zhong, Rahul Shah, Chunlong Guo, Jan Rabaey. An Ultra-Low Power and Distributed Access Protocol for Broadband Wireless Sensor Networks [A].IEEE Broadband Wireless Summit [C]. Las Vegas, Nevada. 2001.
[24]. Poduri S, Sukhatme G S. Constrained Coverage in Mobile Sensor Networks[R]. New Orleans: LA.Proc. IEEE. Int. Conf. Robotics and Automation, 2004.
[25]. Zou Y, Chakrabarty K. Sensor deployment and target localization in distributed sensor networks[J]. ACM Trans. on Embedded Computing Systems, 2004,3(1):61?91.
[26]. Wang. X, et al. Integrated coverage and connectivity configuration in wireless sensor networks[R]. Los Argels: SenSys’03: Proceedings of the First International Conference on Embedded Networks Sensor Systems, 2003.
[27].汪学清,杨永田,孙婷,张忠林.无线传感器网络中基于网格的覆盖问题研究.计算机科学,2006,3(11):38-40.
[28]. Liu Jie, Patrick Cheung, Leonidas Guibas, etc.A Dual-space Approach to Tracking and Sensor Management in Wireless Sensor Networks[R]. Palo Alto: Palo Alto ResearchCenter Technical Report P2002-10077, 2002.
[29]. Azzedine Boukerche, Xin Fei, Regina B. Araujo. An optimal coverage-preserving scheme for wireless sensor networks based on local information exchange. Computer Communications [J]. 2007, 30(34): 2708–2720.
[30]. Mihaela Cardei, Jie Wu. Energy-efficient coverage problems in wireless ad-hoc sensor networks [J]. Computer Communications, 2006, 29(6): 413–420.
[31]. Ossama Younis, Marwan Krunz, Srinivasan Ramasubramanian. Location-unaware coverage in wireless sensor networks [J]. Ad Hoc Networks, 2008, 6(7): 1078-1097.
[32].王晟.无线传感器网络节点定位与覆盖控制理论及技术研究[D].武汉:武汉理工大学,2006.
[33].黄铮.无线传感器网路连通与覆盖问题的研究[D].武汉:武汉理工大学,2006.
[34]. J. Chou D. Petrovic, R. Kennan. A distributed and adaptive signal processing approach to reducing energy consumption in sensor networks [A]. In: IEEE INFOCOM 2003[C]. Apri1 2003:1054-1062.
[35].张颖,郭鹏,周宗仪.移动传感器网络覆盖算法研究.计算机工程与科学, 2008,30(2):81-84.
[36].周彤,洪炳鎔,朴松昊.基于虚拟力的混合感知网节点部署.计算机研究与发展,2007,44(6):965-972.
[37]. WANG Xiao-rui, XING Guo-liang, ZHANG Yuan-fang, et al. Integrated coverage and connectivity configuration in wireless sensor net-works[C]//Proc of the ACM International Conference on Embedded Networked Sensor Systems ( SenSys) . New York: ACM Press, 2003:28-39.
[38].王换招,董贝,罗韩梅,陈培军,李增智.基于k-覆盖保证的异构传感器网络节点调度策略.西安交通大学学报,2008,42(8):940-945.
[39].蒋丽萍,王良民,熊书明,詹永照.基于感知概率的无线传感器网络k重覆盖算法.计算机应用研究,2009,26(9):3484-3486.
[40]. LIU Ming, CAO Jian Nong, ZHENG Yuan, CHEN Li-Jun, XIE Li. Analysis for Multi-Coverage Problem in Wireless Sensor Networks. Journal of Software, 2007, 18(1):127?136.
[41].翟正怡.无线传感器网络中的覆盖优化算法与连通问题研究[D].上海:同济大学,2008.
[42]. Cerpa A, Estrin D, ASCENT: adaptive self-configuring sEnsor networks topologies [Al .INFOCOM 2002 Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings[C], June 2002(3):23-27 .
[43]. Okabe, B. Boots, K. Sugihara, S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagram, John Wiley and Sons, New York, 1999.
[44].王雪,王晨,马俊杰.无线传感网络布局的虚拟力导向微粒群优化策略[J].电子学报,2007,35(11):2038-2042.
[45].杨丹.无线传感器网络中维护覆盖和连通的节点调度算法[D].湖南:湖南大学,2008.
[46]. Bang Wang, Wei Wang, V. Srinivasan, and K.C. Chua, Information Coverage for Wireless Sensor Networks [J], IEEE Communications Letters, vol.9, no.11, 2005: 967-969.
[47]. YeF, Zhong G, Lu S et al. PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks [A] The 23rd International Conference on Distributed Computing Systems (ICDCS’03)[C],May 2003.
[48]. Meguerdichian S, Koushanfar F, Potorjak M, etc. Coverage problems in wireless[J]. Ad-hoc sensor networks. Infocom,2001,7(3):1380-1387.
[49].蒋杰.无线传感器网络覆盖控制研究[D].长沙:国防科学技术大学,2005.
[50]. JIN Yan, WANG Ling, YANG Xiao-zong, WEN Dong-xin. Overview of Node Scheduling Algorithm in Wireless Sensor Networks. Journal of Astronautics. 2007, 28(5): 1086-1093.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |