摘要
物联网技术领域中的无线传感器网络(Wireless Sensor Networks, WSN)是当今研究的热点问题之一,无线传感器网络是物联网技术领域的核心技术。
WSN集成了传感器技术、无线通信技术、微电子技术、嵌入式以及分布式处理技术等,WSN在军事、环境科学、医疗健康、安全监视、生态环境监测、智能家居和其他商业领域都有着广阔的应用前景。其价值已经引起了各国政府、军事部门、研究机构和公司企业的高度重视。
本文主要研究了WSN的覆盖与连通问题。在研究覆盖与连通问题之前,首先介绍了WSN的组成结构和网络特点；然后对WSN的应用领域进行了叙述,对国内外WSN的研究现状进行了概括；最后就WSN的覆盖与连通的研究意义进行了阐述。随之介绍了无线传感器节点及其结构、功能和特点,对网络的各种覆盖进行了分类。详细描述了点线面三种覆盖,并且介绍了覆盖性能指标和覆盖的某些理论。
WSN一般由大量自供电的传感器节点组成,传感器节点一般依靠电池供电。电池电源是有限的,并且传感器节点一旦部置后,由于其工作环境等因素的限制就很难对电池进行充电或更换电池,这就使得WSN的寿命受到影响,从而不能长时间地使用。通过对WSN覆盖与连通问题的研究可以优化网络结构、延长网络寿命。
为了延长网络的生存时间,本文以图论的知识体系为支撑介绍WSN的连通性,随之讲述了选路算法,根据网络节点的多跳传输特点,通过多跳矩阵的更新来进行相应的路由选择。然后把CPN选路算法与DSBR选路算法进行了比较分析,得出CPN选路算法较好。接下来在圆域覆盖的基础上研究了可化为蜂窝型的节点部署区域覆盖。最后在基于Voronoi图理论的基础上,就MCCS问题提出了自己的算法——一种近似最优连通覆盖集。通过基于Voronoi图的CVT算法可以求出目标区域的近似最优连通覆盖集,从而得出基于Voronoi图的覆盖网络的鲁棒性和抗毁性优于蜂窝型的覆盖网络。同时,在保证WSN正常工作的同时,节省网络的开销并且延长网络的存活时间。
Wireless sensor networks (WSN) is one of the hot issues of current research in the Internet of things technology. It is the core technology in the field of the Internet of things technology.
WSN includes sensor technology, wireless communication technology, micro-electronics embedded and distributed processing technology and so on. WSN has a wide application prospect in the military, environmental health science, safety monitoring, environment monitoring, smart homes and other commercial areas. Many governments, military departments, research institutions and companies have paid more attention to its value.
This paper mainly studies the coverage and connectivity problems of the WSN. As to this question, this article begins with a brief introduction to architecture and network characteristics of WSN and also make an explanation to its application field. The current research of WSN in domestic and overseas is summarized and the significant of coverage and connectivity in the WSN is stated to finally. This paper introduced Wireless sensor nodes along with its structure, function and features and classified the variety of the network coverage. A detail description of the point, line and area coverage is also made and the coverage of performance indicators and some theories of coverage is introduced.
WSN generally consists of a large amount of self-powered sensor nodes, which generally rely on batteries. Battery power is limited. Once the sensor nodes are set, due to the factors such as their limitation of working environment, it is difficult to charge or replace the battery, which affects the life of WSN, and thus cannot use for a long time. Researching on cover and connectivity issues of WSN can optimize network structure and prolong the network life.
In order to extend the network lifetime, this paper introduced the connectivity of WSN with the support of the graph theory and routing algorithm. According to the network node's characteristics with multiple hops transmission, the routing can be chosen by updating the multiple hops matrix. Then we compare CPN routing algorithm with DSBR algorithm, and the conclusion is that CPN routing algorithm is better. After research on the Circular domain coverage, making a coverage which can be translated into the regional coverage of cellular type. The advantage of cellular coverage is that it can maximize the coverage, but the robustness and anti-destroying ability of WSN is poor. Finally, after studying on Voronoi diagram, this paper put forward my own idea—a kind of approximate optimal connecting cover sets. It can be worked out by CVT algorithm of Voronoi.Robustness and anti-destroying in WSN is better than that of regional coverage of cellular type. Meanwhile, it can reduce energy consumption and prolong the life time of WSN to ensure the normal work of WSN.
引文
[1]孙利民,李建中,陈渝,朱红松.无线传感器网络[M].北京：清华大学出版社,2005,4-22
[2]马祖长,孙怡宁,梅涛.无线传感器网络综述[J].通信学报,2004,25(4)：114-124
[3]Akyildig I F, Su W, Sankara subramaniam Y, etal. A Survey on Sensor Networks[J]. IEEE Communications Magazine,2004,29(8):721-734
[4]C.Y. Chong, S.P. Kumar, "Sensor Networks:Evolution, Opportunities and Challenges" [J],Proceedings of the IEEE,2003,91(88):1247-1256
[5]Chien-Chung Shen. Chavalit Srisathapornphat. CLTC:A Cluster-Based Topology Control Frame work for Ad-Hoc Networks, IEEE Transaction On Mobile Computing[C],2004,3(1):18-32
[6]崔莉,鞠海玲,苗勇等.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1)：163-174
[7]任丰原,黄海宁,林闯.无线传感器网络.软件学报[J],2003,14(7)：1282-1291
[8]于海斌,曾鹏,梁麟.智能无线传感器网络系统[M].北京：科学出版社,2006
[9]宋文,王兵等.无线传感器网络技术与应用[M].北京：电子工业出版社,2007.
[10]LF. Akyildiz, W. Su,Y. Sankarasubramaniam, E. Cayirci, "A Survey on Sensor Networks, "IEEE Communications Magazine[J],2002,40(8):103-115
[11]A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J.Anderson,"Wireless Sensor Networks for Habitat Monitoring" [J], Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications(WSNA),2002:88-97
[12]孟庆斌.无线传感器网络应用研究[D].天津：天津大学学位论文,2009,1
[13]孙雨耕,张静,孙永进,房朝晖.无线自组传感器网络[J].传感技术学报,2004,17(2)：331-335
[14]代宏阳,唐宏,胡锡鹏.无线传感器网络在军事中的应用研究[J].电脑知识与技术,2010,16(6)：4408-4419
[15]Schurgets. C, Tsiatsis. V, Srivastava. MB. STEM:Topology management for energy efficient sensor networks[C]. IEEE Aerspace Conference,2002:1099-1108
[16]熊炜,李清泉.高速公路场景中车用自组织网络的节点度.电子与信息学报[J].2010,32(9)：2033-2042
[17]Anastasi G, Conti M, Prancesco M D, and PassareIla A. Energy conservation in wireless sensor networks:A survey[J]. Ad-hoc Networks.2009,7(3):537-568
[18]Vieira M A M, Coelho C N. Survey on wireless sensor network devices[J]. Emerging Technologies and Factory Automation.2003,16-21(1):537-544
[19]Li M, Liu Y, Chen L. Non-threshold based event detection for 3D environment monitoring in sensor networks[J]. In:Proc of IEEE ICDCS. Canada,2007(6):9-14
[20]李雪.无线传感器网络在三维空间中的覆盖和连通[D].西安：西安电子科技大学硕士论文,2009,2
[21]Li M, Liu Y Underground structure monitoring with wireless sensor networks[J]. In: Proc. of ACM/IEEE IPSN. Cambridge, Massachusetts, USA,2007(4):69-78
[22]Yang Z, Li M, Liu Y Sea depth measurement with restricted floating Sensors[J]. In: Proc. IEEE RTSS. Tucson, Arizona, USA,2007,10:469-478
[23]Pottle G. Kaiser W. Wireless integrated network sensors[J]. Communication of the ACM,2006,43(5):51-58
[24]魏宁.无线传感器网络的三维空间覆盖与目标定位问题研究[D].西安：西安电子科技大学硕士论文,2009
[25]C. Hunag and Y. Tseng. The coverage Problem in a Wireless Sensor Network[J]. Proceedings of the IEEE,2003,19(4):115-121
[26]D. Tian and N. D. Georganas. A coverage—preserving node scheduling scheme for large wireless sensor networks[J]. First ACM International Workshop on Wireless Sensor Networks and Applications, Georgia, GA,2002.
[27]S. Meguerdichian, F. Koushanfar, M. Potkonjak, M. Srivastava. Coverage Problems in Wireless Ad-Hoc Sensor Networks[J]. IEEE INFOCOM,2007(4):384-412
[28]Sami Habib etal. Sensitivity Study of Sensors'Coverage within Wireless Sensor Networks[J], IEEE,2007:796-868
[29]屈巍.无线传感器网络中一种分布式冗余检测算法[J].小型微型计算机系统,2010,6(4)：156-171
[30]曾映兰.基于遗传算法的WSN覆盖优化方法[J].计算机工程与应用.2009,8(11)：115-130
[31]杨白薇.一种基于协作的最优无线传感器节点密度控制算法[J].计算机应用,2007,10(6)：115-130
[32]俞靓.保障覆盖连通质量的节点部署机制[D].浙江：浙江大学信息学部,2009.
[33]Abrams Z, Goel A, Plotkin S. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks[M]. In:Ramchandran K, Sztipanovits J, eds. Proc. of the 3rd Int'l Conf on Information Processing in Sensor Networks. Berkeley:ACM Press,2004: 424-432
[34]You-ChiunWang, Chun-Chi Hu, Yu-Chee Tseng. Efficient Deployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks[C]. Communication of the ACM,2005,10(8):84-88.
[35]X. Wang, G Xlng, Y Zhang, C. Lu, R. Pless, and C. Gill, Lntegrated coverage and connectivity configuration In wireless sensor networks [J], ACM Conference on Embedded Networked Sensor Systems,2008,4(15):164-182
[36]Xiaorui Wang, Guoliang Xing, Yuanfang Zhang, etal. Integrated Coverage and Connectivity Configuration in Wireless Sensor networks[J]. First ACM Conference on Embedded Networked Sensor Systems, Los Angeles, CA,2003,10
[37]Iyer R Kleinrock L. QoS control for sensor communication network protocols in deep space[C]. In Proc. of the IEEE International Conference on Communications,2003, 1:517-521
[38]S. H. L. Liang, V. Tao, A. Croitoru. The Design and Prototype of a Distributed Geospatial Infrastructure for Smart Sensor Web[M]. Proceedings of the 6th AGILE Conference on Geographic Information Science.2003
[39]A. Cerpa, J. Elson, M. Hamilton, and 1. Zhao, Habitat Monitoring:Application Driver for Wireless Communications Technology[R]. First ACM SIGCOMM Workshop on Data Communication in Latin America and the Caribbean,2001,4
[40]J. R. Polastre, D. Culler. Design and Implementation of Wireless Sensor Networks for Habitat Monitoring[C], University of California at Berkeley Press,2003
[41]孙雨耕,张静,孙永进.无线自组传感器网络.传感技术学报[J],2004(6)：331-348
[42]Alan Mainwaring, Joseph Polastre, Robert Szewczyk, et al, Wireless Sensor Networks for habitat Monitoring[C], IEEE INFOCOM,2002,9
[43]NouryN, Herve T, Riale V, et al. Moitoring behavior in home using a smart fail sensor[C]. In:IEEE2EMBS Special Topic Conference on MicrotechnolOgies in Medicine and Biology,2006,10:607-610
[44]A. Cerpa and D. Estrin. ASCENT:Adaptive Self-Connguring Sensor Networks Topologies [J]. IEEE Transactions on Mobile Computing,2006,3(3):272-285
[45]黄铮.无线传感器网络连通与覆盖的研究[D].武汉理工大学硕士论文,2006
[46]林蔚,杨永田.自组网负载平衡路由协议[J],哈尔滨工程大学学报.2007,10(4)：553-558
[47]ALZOUBI K M. Distributed Algorithms for Connected Dominating Set in Wireless Ad Hoc Networks[D]. Illinois Institute of Tecnology,2002:561-587
[48]DAS BIJOY, BHARGAVAN V. Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets [C]//ICC'97(C). New-York:IEEE Press.1997:123-135
[49]Y. Xu, J. Heidemann, and D. Estrin. Geography-informed Energy Conservation for Ad Hoc Routing[J]. ACM/IEEE International Conference on Mobile Computing and Networking, Rome, Italy,2005,7:70-84
[50]汪学清,杨永田等.无线传感器网络中基于网格的覆盖问题研究[J].计算机科学,2006,33(7)：36-39
[51]Tian D, Georganas N. A coverage-preserving node scheduling scheme for large wireless sensor networks[M]. In:Raghavendra CS,Sivalingam KM, eds. Proc. of the 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications. Atlanta:ACM Press,2002:32-41
[52]Chen H, Wu H, Tzeng N. Grid-Based approach for working node selection in wireless sensor networks[M]. In:Viginier P, ed. Proc. Of the Int'l Conf. on Communications. Paris:IEEE Press,2004(5):3673-3678
[53]Carbunar B, Grama A, Vitek J, Carbunar O. Coverage preserving redundancy elimination in sensor networks[J]. In:Znati T, Raghavendra CS, eds. Proc. of the 1st IEEE Conf. on Sensor and Ad Hoc Communications and Networks. Santa Clara:IEEE Press,2004:377-386
[54]Yan T, He T, Stankovic J. Differentiated surveillance service for sensor networks[J]. In: Akyildiz IF, Estion D, eds. Proc. of the 1st Int'l Conf. on Embedded Networked Sensor Systems. Los Angels:ACM Press,2003:51-63
[55]沈昊为.传感器网络中基于Voronoi网格的快速覆盖判定算法研究[D].湖南：湖南大学硕士论文,2009
[56]张西红,妙文亮,高彦彦.无线传感器网络的覆盖问题研究[J].计算机工程, 2009,6(7)：79-112
[57]王殊,阎毓杰等.无线传感器网络的理论及应用[M].北京：北京航空航天大学出版社,2007.
[58]Elson J, Estrin D. Sensor Networks:A Bridge to the Physical World[J]. Norwell: Kluwer Academic Publishers,2004(6):3-20
[59]Ren FY, Huang HN, Lin C. Wireless sensor networks[J]. Journal of Software, 2006,14(7):1284-1292
[60]崔莉,鞠海玲,苗勇,李天璞,刘巍,赵泽.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1)：162-175
[61]Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks[J]. In:Proc. of the Int'l Conf. on Communications. Helsinki:IEEE Communication Society,2001:472-476
[62]Cui L, Ju HL, Miao Y, Li TP, Liu W, Zhao Z. Overview of wireless sensor networks[J]. Journal of Computer Research and Development,2008,42(1):165-173
[63]Ye F, Zhong G, Lu S, Zhang L. Peas:A robust energy conserving protocol for long-lived sensor networks[J]. In:McKinley PK, Shatzs, eds. Proc. of the 23rd Int'l Conf. on Distributed Computing Systems. Providence:IEEE Press,2003:28-37
[64]Gupta H, Das SR, GU Q. Connected sensor cover:Self-Organization of sensor networks for efficient query execution[M]. In:Gerla Mad. Proc. of the ACM MobiHoc 2005. Annapolis:ACM Press,2005:189-200
[65]David Marsh et al.The Effects of Deployment Irregularity on Coverage in Wireless Sensor Networks[J]. ISSNIP,2005,8(5):14-18
[66]Stanislava Soro,Wendi B.Heinzelman. Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering[J].Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium,IEEE,2005:94-125
[67]Okabe A, Boots B, Sugihara K, Chiu S. Spatial Tessellations[M].Concepts and Applications of Voronoi Diagram.2nd ed. New York:John Wiley & Sons,2006.
[68]Hochbaum DS. Approximation Algorithms for NP-Hard Problems[C]. Communication of the ACM,2006,10(6):78-92