摘要
无线传感器网络(Wireless Sensor Network，WSN)是由大量计算、通信及存储能力有限的传感器节点组成的特殊Ad hoc网络，可感知、采集和实时传递监测对象的各种参数，在军事、工业及民用等领域应用广泛，是目前一个非常活跃的研究领域。覆盖问题是无线传感器网络研究中的关键问题之一，它反映了传感器网络所提供的“感知”服务质量，可以使无线传感器网络的空间资源得到优化分配。论文针对无线传感器网络的栅栏覆盖问题，从监控方(传感器网络)和反监控方(移动目标)两个角度展开了深入研究。前者是解决无线传感器网络如何探测到目标的问题，而后者则关注如何在已有覆盖的基础上提高网络覆盖性能。本文主要工作包括以下几个方面：
(1)首先，本文从被监测的移动目标即反监控方的角度出发，研究了受时间约束的目标如何安全穿越传感器网络的问题。当智能目标穿越敌方无线传感器网络的穿行时间受限时，现有基于广度优先搜索的穿越算法不能保证路径满足约束条件。为此，论文建立了一种穿越模型，并提出一种启发式的近似数值优化算法(kSP-LAHTP)。算法利用Voronoi图将连续路径问题域离散化，计算Voronoi边的两个衡量指标：暴露度和穿行时间，结合线性聚合的启发式路由机制，使目标实现满足时间约束值的最佳穿越。分析和试验结果表明算法解决了目标穿越时间受限情况下的穿越问题，且随系数k的增加，算法搜索路径更接近实际最佳。
(2)研究了轨迹长度受约束的目标穿越问题。在实际应用中，可能由于一些不可抗拒因素的原因(如：能耗)，目标必须兼顾穿行轨迹的长度，过长的轨迹无疑要消耗更多的能源。尽管当目标以匀速运动前进时，路程的消耗可转换成对时间的消耗，但若目标以变速前进时，路程和目标穿行时间难以进行有效转换。为此，本文采用网格技术，并结合标签设定路由机制，提出一种轨迹长度受约束的目标穿越轨迹算法。该算法可使智能目标在起点至终点的轨迹长度不大于约束阈值的前提下实现近似最优穿越。分析和试验结果表明，算法能有效搜索到满足约束条件的近似最佳轨迹，同时可以通过增加网格阶数来提高轨迹精确度。
(3)研究了基于有向感知模型的弱栅栏覆盖问题。目前，关于弱栅栏覆盖控制方面的研究一般是针对满足全向性感知模型的传感器网络展开。然而，传感器网络构造栅栏时，仅需用到传感器节点的部分感知区域即扇形区域，显然采用全向感知模型将导致节点能源的浪费。为此，本文采用有向感知模型来展开弱栅栏覆盖问题的研究，分析了传感器网络构造弱栅栏覆盖的概率以及间隙长度(即覆盖缺口)小于目标大小的概率，并提出一种弱栅栏覆盖启发式构造算法。该算法通过计算节点覆盖区域在区域边界的投影，将弱栅栏覆盖问题转化为一维线覆盖问题，且算法可依据目标的大小来调控间隙距离，从而使网络探测到目标的同时最小化节点数。实验结果表明，采用有向感知模型的方案为构造栅栏所需激活节点数少于基于全向感知模型的方案，且构建弱栅栏覆盖所需节点数随着目标大小的增加而减少。
(4)研究了基于数据融合的强栅栏覆盖问题。对于沿任意路径穿越带状区域的移动目标，分布于区域的无线传感器网络通常构造强栅栏覆盖以检测穿越目标，并利用节点睡眠调度策略有效缓解节点能量受限问题。然而，现有研究一般基于圆盘感知模型且未考虑节点间的协作，容易导致传感器节点的浪费。针对此问题,本文采用概率性感知模型，并利用数据融合技术构造虚拟节点来增加节点覆盖区域。在此基础上，提出一种栅栏覆盖控制算法。算法借助分治法构造栅栏，以减少节点间通信开销；并调度传感器使冗余节点睡眠，达到减少网络能耗和延长网络寿命的目的。实验结果表明，算法在栅栏数、网络寿命等性能上均优于基于节点监测数据未融合的栅栏覆盖控制算法。
(5)最后，研究了基于概率性模型的k-连通栅栏覆盖问题。覆盖和连通是传感器网络的两个重要属性，在网络设计中扮演着重要角色。然而，目前大部分相关工作仅考虑其中一类问题，而未将覆盖和连通结合研究分析。而且，研究成果大部分是基于圆盘模型，该模型并不能有效利用节点的感知和通信能力。为此，本章基于概率性模型分析了栅栏覆盖与s-t连通之间的关系，并提出一种分布式k-连通栅栏覆盖维持协议。该协议可同时实现栅栏覆盖和s-t连通，且比其它基于圆盘模型的协议更适合真实环境。实验结果表明，协议可通过对探测率阈值，误警率阈值以及包传递率阈值的设置来提供质量可控的连通栅栏覆盖和调节激活节点数。
综上所述，本文以改善覆盖能力和提高覆盖质量为目标，分别从反监控方和监控方两个角度研究了栅栏覆盖问题，对于推进无线传感器网络栅栏覆盖控制的研究和实用化具有广泛的理论意义和应用价值。
Wireless sensor network (WSN) is a special self-organized ad-hoc networkconsisting of a number of tiny sensor devices with low processing power, lowcommunication capacity, and limited buffer capacity. Each device has sensing,processing and wireless communication capabilities, which enable it to gather usefulinformation about the environment, to generate report messages and deliver messagesto the base station. Wireless sensor networks widely used in military, industrial, civil,etc. is currently an active research area. Sensing coverage is one of the fundamentalproblems in wireless sensor networks, which reflects the quality of service (QoS) ofmonitoring provided by the entire sensor network. Space resources of wireless sensornetwork can be optimized allocation by coverage. This dissertation focuses on thebarrier coverage based on monitoring (wireless sensor network) and anti-monitoring(moving target) in wireless sensor network. The former is to address how to cover themoving target, while the latter is to consider how to provide better QoS of monitoring.The major contributions of the dissertation are as follows:
(1) Firstly, based on anti-monitoring, the moving target subjected to traversal timeconstraint how to across enemy sensor networks field was studied. The most existingtraversal algorithms based on breadth-first-search are difficulty to satisfy apre-determined time constraint value. Motivated by this reason, a traversal model isconstructed and a heuristic approximately optimization algorithm (kSP-LAHTP) isproposed in this dissertation. The algorithm makes the continuous path problemdomain to a discrete one by Voronoi diagram. By using exposure and traversal time asthe path (trajectory) performance metric, the algorithm combines the linear aggregatedrouting mechanism to find the optimal path. It makes the moving target can traversethe enemy sensor networks field. And the traversal time from the source to thedestination is less a given threshold. Theoretically and experimentally, it is concludedthat the proposed algorithm is able to solve the traversal path problem with timeconstraint. The proposed algorithm (kSP-LAHTP) is able to find a traversal path closerto the optimum with parameter k increasing.
(2) Secondly, the moving target subjected to trajectory length constraint how toacross the enemy sensor networks field was studied. In practical applications, due tosome majeure reasons (such as: energy consumption), the target must take into account the length of the trajectory, because long trajectory will undoubtedly consume moreresources. When target move forward with uniform speed, the trajectory length cantranslate into time. When target move forward with uneven speed, the trajectory lengthcan’t translate into time. Thus we can’t search the trajectory with length constraint bythe kSP-LAHTP algorithm. For the reason, utilizing grid and label setting routingmechanism, an approximate optimization approach was proposed for finding traversaltrajectory of target. The algorithm can calculate the approximate optimal trajectory ofintelligent target with a constraint on the trajectory length, where the trajectory lengthfrom start to destination is less than special threshold. Theoretical analysis andextensive experiments results show that the proposed scheme is able to find theapproximate minimal exposure trajectory with constraints and improve accuracy of thetrajectory by increase order of grid.
(3) The issue on how to achieve weak barrier coverage based on directionalsensing model was studied in the dissertation. At present, most of the existing weakbarrier coverage schemes are based on omni-directional sensing model. However, itcan be known that only a sector of sensing region is required to construct barrier.Therefore, omni-directional sensing model will result in waste of energy formaintaining the sensing capability over the remainder of the sensing region. Motivatedby the reason, based on directional sensing model, we analysis the probability of thesensor network successfully accomplished weak barrier coverage and the probability ofthe gap is less than size of the target. And we propose a weak barrier coverage heuristicalgorithm. The algorithm translate the weak barrier coverage problem into linecoverage problem by projecting sensors’ coverage regions on boundary of region,while the barrier can exist the gaps which smaller than a given size. The performanceof the proposed scheme was evaluated and compared with that of the omni-directionalsensing scheme. The results show that the proposed directional sensing schemeachieved weak barrier coverage is better than the omni-directional sensing scheme, andthe number of activated node will decrease with size of target increasing.
(4) The issue on the (strong) barrier coverage based on data fusion was studied.Wireless sensor networks usually construct barrier coverage for detecting travel targetwhen sensor random development in a belt region. And sensors scheduling algorithm isused to alleviate the energy limitation problem of sensor in sensor networks. However,most of current researches are based on disk sensing model, and don’t consider thecollaboration between sensor nodes, which will result in waste of sensor nodes.Therefore, in this paper, based on probabilistic sensing model, we construct virtual sensor by information fusion scheme that fuse sensing measurements of two sensors,which can significantly improve coverage region. Based on the theories, a barriercoverage preserving configuration algorithm is proposed. The algorithm providescontinuous barrier coverage for the whole region by divide-and-conquer approach,which can reduce the communication overhead. Moreover, the redundancy nodes arescheduled to sleep for reducing energy consumption and prolonging the networklifetime. Analysis and experiment results show that the algorithm outperforms thebarrier coverage preserving configuration scheme based on information non-fusionsensor, on the number of barrier and network lifetime, etc.
(5) Finally, the issue on k-connected barrier coverage based on probability modelwas studied. Barrier coverage and network connectivity are two important properties ofwireless sensor networks deployed in belt region. However, most of the previousworks addressed only one kind of the two issues: coverage or connectivity alone.Moreover, many previous works on coverage and connectivity are based on the diskmodel, which can’t fully utilize the sensing and communication capacity of sensors.For these reasons, we analysis the relationship between barrier coverage and s-tconnectivity and proposed a distributed algorithm (k-CBC) for maintaining bothk-barrier coverage and s-t connectivity (refer to as k-connected barrier coverage) underprobabilistic model. The proposed algorithm is more suitable for real environmentsthan other protocols that assume sensing and communication regions (ranges) are diskswith a fixed radius around sensors. The performance of the proposed scheme wasevaluated and compared with other schemes. Compared with other algorithm based ondisk model, our scheme can provide the controllable quality of k-connected barriercoverage and the number of active nodes by detection probability threshold, falsealarm probability threshold, and packet deliver rate threshold.
In summary, our goal is improve the barrier coverage performance and enhancingthe quality of barrier coverage. This dissertation studies the barrier coverage based onanti-monitoring and monitoring respectively, which has practical value and theoreticalsignificance for advancing the research and practicability of barrier coverage.
引文
[1] Akyildiz I F, Su W, Sankarasubramaniam Y, et al. Wireless sensor networks: asurvey. Computer Networks,2002,38(4):393-422
[2]孙利民,李建中,陈渝等.无线传感器网络.北京:清华大学出版社,2005,1-26
[3] Akyildiz I F, Melodia T, Chowdhury K. A survey on wireless multimedia sensornetworks. Computer Networks,2007,5l (4):921-960
[4]程卫芳.无线传感器网络覆盖控制技术研究:[国防科技大学博士学位论文].长沙:国防科技大学,2008,1-34
[5]任丰原,黄海宁,林闯.无线传感器网络.软件学报,2003,14(7):1282-1291
[6] Akyildiz I F, Su W, Sankarasubramaniam Y. A survey on sensor networks. IEEECommunications Magazine,2002,40(8):102-114
[7] Bharathidasan A, Ponduru V A S. Sensor networks: an overview. IEEE Journalon Potentials,2003,22(2):20–23
[8] Akyildiz I F, Kasimoglu I H. Wireless sensor and actorq networks: researchchallenges. Ad hoc Networks,2004,2(4):351-367
[9] Perkins C E. Ad Hoc Networking. Boston: Addison-Wesley,2001
[10] Chong C Y, Kumar S P. Sensor networks: evolution, opportunities, andchallenges. Jounal Proceedings of the IEEE,2003,91(8):1247–1256
[11]张鼎兴.无线传感器网络点覆盖技术研究:[国防科技大学博士学位论文].长沙:国防科技大学,2008,1-17
[12] Hill J, Szewczyk R, Woo A, et al. System architecture directions for networkedsensors. In: Proc. of the9th International Conference on Architectural Supportfor Programming Languages and Operating Systems. Cambridge, Massachusetts,USA,2000,93-104
[13]秦宁宁.无线传感器网络栅栏覆盖的研究:[江南大学博士学位论文].无锡:江南大学,2008,1-40
[14]刘丽萍.无线传感器网络节能覆盖:[浙江大学博士学位论文].杭州:浙江大学,2006,1-31
[15]蒋杰.无线传感器网络覆盖控制研究:[国防科技大学博士学位论文].长沙:国防科技大学,2005,1-26
[16] Simon O, Maroti M, Ledeczi A, et al. Sensor network-based countersnipersystem. In: Proc. of the2nd intemational conference on Embedded networkedsensor systems. Baltimore, MD, USA,2004,1-12
[17] ALERT Systems Organization. ALERT-2Protocol Development. http://www.alertsystem.org,2011-6-19
[18] Polastre J R. Design and implementation of wireless sensor networks for habitatmonitoring:[thesis]. Berkeley: University of Califomia,2003,4-10
[19] Cerpa A, Elson J, Estrin D, et a1. Habitat monitoring: application driver forwireless communications technology. In: Proc. of the2001ACM SIGCOMMWorkshop on Data Communications in Latin America and the Caribbean. CostaRica,2001,20-41
[20] Mainwaring A, Polastre J, Szewczyk R, et a1. Wireless sensor networks forhabitat monitoring. In: Proc. of the1st ACM international workshop on Wirelesssensor networks and applications. Atlanta, Georgia, USA,2002,88-97
[21] Steere D C, Baptista A, Mcnamee D, et a1. Research challenges in environmentalobservation and forecasting systems. In:Proc. of the6th Annual InternationalConference on Mobile Computing and Networking. Boston, Massachusetts, USA,2000,292-299
[22] Bonnet P, Gehrke J, Seshadri P. Querying the physical world. IEEE PersonalCommunications,2000,7(5):10-15
[23] Petriu E M, Georganas N D, Petriu D C, et al. Sensor-based informationappliances. IEEE Instrumentation and Measurement Magazine,2000,3(4):3l-35
[24] Noury N, Herve T, Rialle V, et al. Monitoring behavior in home using a smartfall sensor and position sensors. In: the1st Annual International Conference onon Microtechnologies in Medicine and Biology. Lyon, France,2000,607-610
[25] Schwiebert L, Gupta S K S, Weinmann J. Research challenges in wirelessnetworks of biomedical sensors. In: Proc. of the7th annual internationalconference on Mobile Computing and Networking. Rome, Italy,2001,151-165
[26] Nam Y H, Halm Z, Chee Y J, et a1. Development of remote diagnosis systemintegrating digital telemetry for medicine. In: Proc. of the20th Annual IEEEInternational Conference on Engineering in Medicine and Biology Society. HongKong, China,1998,1170-1173
[27] Sibbald B. Use computerized systems to cut adverse drug events: report. CMAJLCanadian Medical Association Journal,2001,164(13):1878
[28] Ogawa M, Tamura T, Togawa T. Fully automated biosignal acquisition in dailyroutine through1month. In: Proc. of the20th Annual International Conferenceon Engineering in Medicine and Biology Society. Hong Kong, China,1998,1947-1950
[29] Lin F, Wang Y, Wu H Y. Testbed implementation of delay/fault-tolerant mobilesensor network. In:Proc. of the fourth Annual IEEE International Conference onPervasive Computing and Communications workshops. Pisa, Italy,2006,322-327
[30] Rabaey J, Ammer J, da Silva Jr J L, et al. PicoRadio supports ad hoc ultra-lowpower wireless networking. IEEE Computer Magazine,2000,33(7):42-48
[31] Shih E, Cho S H, Ickes N, et al. Physical layer driven protocol and algorithmdesign for energy-eficient wireless sensor networks. In: Proc. of the7th annualInternational Conference on Mobile Computing and Networking(MobiCom'01).Rome, Italy,2001,272-286
[32] Jiang H F, Qian J S, Wei P. Energy efficient sensor placement for tunnel wirelesssensor network in underground mine. In: Proc. of the2nd InternationalConference on Power Electronics and Intelligent Transportation System. Shenzhen, China,2009,219-222
[33] Li R. A study of the security monitoring system in coal mine underground basedon WSN. In: Proc. of the IEEE3rd International Conference on CommunicationSoftware and Networks. Xi’an, China,91-93
[34] Priyantha N B, Chakraborty A, Balakrishnan H. The cricket location-supportsystem. In: Proc. of the6th ACM International Conference on Mobile Computingand Networking. Boston, Massachusetts, USA,2000,32-43
[35] Pottie G J, Kaiser W J. Wireless integrated network sensors. Communication ofthe ACM,2000,43(5):51-58
[36] Li M, Liu Y,Chen L. Non-threshold based event detection for3D environmentmonitoring in sensor networks. IEEE Transactions on Knowledge and DataEngineering.2008,20(12):1699-1711
[37] Li M，Liu Y. Underground structure monitoring with wireless sensor networks. In:Proc.of the6th International Conference on Information Processing in SensorNetworks (IPSN’07). Cambridge, Massachusetts, USA,2007,69-78
[38] Yang Z, Li M, Liu Y. Sea depth measurement with restricted floating Sensors. In:Proc. of the28th IEEE International Real-Time Systems Sympsium (RTSS’07).Tucson, Arizona, USA,2007,469-478
[39]蒋承东.稠密传感器网络中的双障碍覆盖和SParseDT拓扑控制协议:[中国科技大学博士学位论文].安徽:中国科技大学,2007,1-18
[40]柳立峰.无线传感器网络节能机制与算法的研究:[北京邮电大学博士学位论文].北京:北京邮电大学,2005,9-21
[41]赵从欢.无线传感器网络覆盖算法研究与设计:[哈尔滨工程大学硕士学位论文].哈尔滨:哈尔滨工程大学,2009,1-13
[42] Simeone O, Spagnolini U. Distributed time synchronization in wireless sensornetworks with coupled discrete-time oscillators. EURASIP Journal on WirelessCommunications and Networking,2007,2007:1-13
[43] Sivrikaya F, Yener B. Time synchronization in sensor networks: a survey. IEEENetwork,2004,18(4):45–50
[44] Elson J. Time synchronization in wireless sensor networks:[dissertation]. LosAngeles: University of Califoronia,2001
[45] Yuan W, Krishnamurthy S V, Tripathi S K. Synchronization of multiple levels ofdata fusion in wireless sensor networks. In: Proc. of the23th IEEE InternationalConference on Global telecommunications (Globecom’03). San Francisco,USA,2003,221-225
[46] Elson J, Girod L, Estrin D. Fine-grained network time synchronization usingreference broadcasts.In:Proc.of the5th Symposium on Operating systems designand implementation. Boston, MA, USA,2002,147-163
[47] Palchaudhuri S, Saha A K, Jolmsin D B. Adaptive clock synchronization insensor networks. In: Proc. of the3rd Inrernational Symposium on InformationProcessing in sensor networks (IPSN’04). Berkeley, California, USA,2004,340-348
[48] Lasassmeh S M, Conrad J M. Time synchronization in wireless sensor networks:a survey. In: Proc. of IEEE SoutheastCon. Concord, NC, USA,2010,242-245
[49] Zheng G, Liu Q. A Survey on topology control in wireless sensor network. In:Proc. of the2nd International Conference on Future Networks, Sanya, Hainan,China,2010,376-380
[50] He Y X, Zeng Y Y. Interference-aware topology control problem in wirelesssensor networks. In: Proc. of the6th International Conference on ITSTelecommunications. Chengdu, China,2006,969-972
[51] Yin B L, Shi H C, Shang Y. A two-level strategy for topology control in wirelesssensor networks. In: Proc. of the1lth International Conference on Parallel andDistributed Systems. Fukuoka, Japan,2005,358-362
[52] Wightman P M, Labrador M A. Topology maintenance: extending the lifetime ofwireless sensor networks. In: Proc. of the IEEE Latin-American Conference onCommunications (LATINCOM '09). Medellin, Colombia,2009,1-6
[53]唐勇,周明天,张欣.无线传感器网络路由协议研究进展.软件学报,2006,17(3):410-421
[54] Dulman S, Nieberg T, Wu J, et al.Trade-off between traffic overhead andreliability in the mulitpath routing for wireless sensor networks. In: Proc. ofIEEE Wireless Communications and Networking (WCNC’03). New Oeleans, LA,USA,2003,1918-1922
[55]任彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法.软件学报,2006,17(3):422-433
[56]王燕莉,安世全.无线传感器网络的覆盖问题研究.传感技术学报,2005,18(2):307-312
[57] Mulligan R. Coverage in wireless sensor networks: a survey. Netwrok Protocolsand Algorithms,2010,2(2):27-53
[58] Nakatsuka K, Nakamura K, Hirata Y, et al. A Proposal of the Co-existence MACof IEEE802.11b/g and802.15.4used for The Wireless Sensor Network. In:Proc.of the5th IEEE Conference on Sensors, Daegu, Korea,2006,722-725
[59] Perez J J, Pelegri J, Menendez A. Preamble sampling mac protocol for low powerwireless sensor networks with ieee802.15.4transceivers. In: Proc. of the IEEEConference on Instrumentation and Measurement Technology. Sorrento, Italy,2006,1543-1546
[60] Salman N, Rasool I, Kemp A H. Overview of the ieee802.15.4standards familyfor low rate wireless personal area networks. In: Proc. of the7th InternationalSymposium on Wireless Communication Systems (ISWCS’10). York, Canada,2010,701-705
[61]李平,林亚平,曾玮妮.传感器网络安全研究.软件学报,2006,17(12):2577-2588
[62] Hu Y C, Perrig A, Johnson D B. Packet leashes: a defense agaist wormhole attackin wireless networks. In: Proc. of the22nd annual Joint Conference of the IEEEComputer and Communications (INFOCOM’03). San Francisco, USA,2003,1976-1986
[63] Hu Y C, Perrig A, Johnson D B. Wormhole attacks in wireless networks. IEEEJournal on Selected Areas in Communications,2006,24(2):370-380
[64] Galstyan A, Krishnamachari B, Lerman K, et al. Distributed online localizationin sensor networks using a moving target. In Proc. of the3rd intl symposium onInformation processing in sensor networks (IPSN’04). Berkeley, California, USA,2004,61-70
[65] Patwari N, Ash J, Kyperountas S, et al. Locating the nodes: cooperativelocalization in wireless sensor networks. IEEE Signal Processing Magazine,2005,22(4),54-69
[66] Baggio A, Langendoen K. Monte-carlo localization for mobile wireless sensornetworks. Ad hoc Networks,2008,6(5):718-733
[67] Luo H, Luo J, Liu Y,et al. Adaptive Data Fusion for Energy Efficient Routing inWireless Sensor Networks. IEEE Transactions on Computers,2006,55(10),1286-1299
[68] Li L; Bai F. Analysis of data fusion in wireless sensor networks. In: Proc. of theInternational Conference on Electronics, Communications and Control. Ningbo,China,2011,2547-2549
[69]李燕君,王智,孙优贤.资源受限的无线传感器网络基于衰减信道的决策融合.软件学报,2007,18(5):1130-1137
[70]李建中,李金宝,石胜飞.传感器网络及其数据管理的概念、问题与进展.软件学报,2003,l4(l0):1717-1727
[71] Moon Y B, Choi Y J, Hong S K, et al. Sensor data management system in sensornetwork for low power. In: Proc. of10th International Conference on AdvancedCommunication Technology. Gangwon-Do,2008,504-507
[72] Tian D, Georganas N D. Connectivity maintenance and coverage preservation inwireless sensor networks. Ad Hoc Networks,2005,3(6):744–761
[73] Watfa. Coverage issues in wireless sensor networks:[dissertation]. Norman:University of Oklahoma graduate college,2006
[74] Ahmed N, Kanhere S S, Jha S. The holes problem in wireless sensor networks:asurvey. Sigmobile Mobile Computing and Communications Review,2006,9(2):4-18
[75] Gage D W. Command Control for Many-Robot Systems. In: Proc. of theNineteenth Annual AUVS Technical Symposium. Hunstville, Alabama, USA,1992,22-24
[76] Chakrabarty K, Iyengar S S, Qi H, et al. Grid coverage for surveillance and targetlocation in distributed sensor networks. IEEE Transactions on Computers,2002,51(12):1448-1453
[77] Shen X, Chen J, Sun Y, et al. Grid Scan: A simple and effective approach forcoverage issue in wireless sensor networks. In: Proc. of IEEE InternationalConference on Communications. Istanbul, Turkey,2006,3480-3484
[78] Shakkottai S, Srikant R, Shroff N. Unreliable sensor grids: coverage,connectivity and diameter. In: Proc. of the22nd annual Joint Conference of theIEEE Computer and Communications (INFOCOM’03). San Francisco, USA,2003,1073-1083
[79] Du X, Lin F. Maintaining differentiated coverage in heterogeneous sensornetworks. EURASIP Journal on Wireless Communications and Networking,2005,2005(4):565–572
[80] Lin F Y S, Chiu P L. A near-optimal sensor placement algorithm to achievecomplete coverage/discrimination in sensor networks. IEEE CommunicationsLetters,2005,9(1):43–45
[81] Bai X, Kumar S, Xuan D, et al. Deploying wireless sensors to achieve bothcoverage and connectivity. In Proc. of the7th ACM international symposium onMobile ad hoc networking and computing (MobiHoc’06). Florence, Italy,2006,131-142
[82] Bai X, Xuan D, Yun Z, et al. Complete optimal deployment patterns forfull-coverage and k-connectivity (k≤6) wireless sensor networks. In: Proc. ofthe9th ACM international symposium on Mobile ad hoc networking andcomputing(MobiHoc’08). Hong Kong, China,2008,401–410
[83] Bai X, Zhang C, Xuan D, et al. Low-connectivity and full-coverage threedimensional wireless sensor networks. In: Proc. of the10th ACM internationalsymposium on Mobile ad hoc networking and computing (MobiHoc’09). NewOrleans, Louisiana, USA,2009,145-154
[84] Bai X, Yun Z, Xuan D, et al. Deploying four-connectivity and full-coveragewireless sensor networks. In: Proc. of The27th Conference on Computer andCommunications (NFOCOM’08). Phoenix, AZ, USA,2008,296-300
[85] Wang Y C, Hu C C, Tseng Y C. Efficient deployment algorithms for ensuringcoverage and connectivity of wireless sensor networks. In: Proc. ot the1stInternational Conference on Wireless Internet (WICON’05). Budapest, Hungary,2005,114–121
[86] Wang B, Wang W, Srinivasan V, et al. Information coverage for wireless sensornetworks. IEEE Communications Letters,2005,9(11):967–969
[87] Wang X, Xing G, Zhang Y,et al. Integrated coverage and connectivityconfiguration in wireless sensor networks. In: Proc. of the1st internationalConference on embedded Networked Sensor Systems (SenSys’03). Los Angeles,California, USA,2003,28-39
[88] Huang C, Tseng Y. The coverage problem in a wireless sensor network. MobileNetworks and Applications,2005,10(4):519-528
[89]毛莺池,刘明,陈力军等.DELIC:一种高效节能的节点位置无关的传感器网络覆盖协议.计算机研究与发展,2006,43(2):187-195
[90] Tian D, Georganas N. A coverage-preserving node scheduling scheme for largewireless sensor networks. In: Proc. of1st ACM International workshop onWireless Sensor Networks and Applications (WSNA’02). Atlanta, Georgia, USA,2002,32–41
[91] Zhou Z, Das S, Gupta H. Connected k-coverage problem in sensor networks. In:Proc. of the13th International Conference on Computer Communications andNetworks (ICCCN’04). Chicago, IL, USA,2004,373-378
[92] Zhang H, Hou J C. Maintaining sensing coverage and connectivity in large sensornetworks. Ad Hoc&Sensor Wireless Network.2005,1(2),89–124
[93] Wang W, Srinivasan V, Chua K C, et al. Energy-efficient coverage for targetdetection in wireless sensor networks. In: Proc. of the6th internationalconference on Information processing in sensor networks (IPSN’07). Cambridge,Massachusetts, USA,2007,313-322
[94] Wang B, Chua K C, Srinivasan V, et al. Sensor density for complete informationcoverage in wireless sensor networks. In: Proc. of the3rd European conferenceon Wireless Sensor Networks (EWSN’06). Zurich, Switzerland,2006,69-82
[95] Ahmed N, Kanhere S, Jha S. Probabilistic coverage in wireless sensor networks.In: Proc. of the IEEE Conference on Local Computer Networks (LCN’05),Sydney, Australia,2005,672–681
[96] Wang B, Chua K C, Srinivasan V. Connected sensor cover for area informationcoverage in wireless sensor networks. International Journal of CommunicationSystems,2008,21(11):1181-1203
[97] Wang B, Chua K C, Srinivasan V, et al. Information coverage in randomlydeployed wireless sensor networks. IEEE Transactions on WirelessCommunications,2007,6(8):2994-3004
[98] Lu J, Bao L, Suda T. Probabilistic self-scheduling for coverage configuration inwireless ad-hoc sensor networks. International Journal of Pervasive Computingand Communications,2008,4(1):26-39
[99] Wang D, Liu J, Zhang Q. Probabilistic field coverage using a hybrid network ofstatic and mobile sensors. In: Proc. of the15th IEEE international workshop onQuality of Service. Evanston, TL, USA,2007,56-64
[100] Poduri S, Sukhatme G S. Constrained coverage for mobile sensor networks. In:Proc. of the IEEE International Conference on Robotics and Automation. NewOrleans, LA, USA,2004,165–172
[101] Jiang Z, Wu J, Kline R, et al. Mobility control for complete coverage in wirelesssensor networks. In: Proc. of the28th International Conference on DistributedComputing Systems Workshops (ICDCS’08). Beijing,China,2008,291–296
[102] Chellappan S, Gu W J, Bai X L, et al. Deploying wireless sensor networks underlimited mobility constraints. IEEE Transactions on Mobile Computing,2007,6(10):1142–1157
[103] Wang Y C, Tseng Y C. Distributed deployment schemes for mobile wirelesssensor networks to ensure multi-level coverage. IEEE Transactions on Paralleland Distributed Systems,2008,19(9):1280-1294
[104] Wang B, Lim H B and Ma D. A survey of movement strategies for improvingnetwork coverage in wireless sensor networks. Computer Communications,2009,32(13):1427-1436
[105] Cortes J, Martinez S, Karatas T, et al. Coverage control for mobile sensingnetworks. IEEE Transactions on Robotics and Automation,2004,20(2):243-255
[106] Han X, Cao X, Lloyd E L,et al. Deploying directional sensor networks withguaranteed connectivity and coverage. In: Proc. of the5th Annual IEEECommunications Society Conference on Sensor, Mesh and Ad HocCommunications and Networks (SECON’08). San Francisco, CA, USA,2008,153-160
[107] Cardei M, Thai M T, Li Y, et al. Energy-efficient target coverage in wirelesssensor networks. In: Proc. of the24th Annual Joint Conference of the IEEEComputer and Communications Societies (INFOCOM’05). Miami,FL,USA,2005,1976–1984
[108] Cardei I. Energy-efficient target coverage in heterogeneous wireless sensornetworks. In: Proc. of IEEE international conference on Mobile adhoc and SensorSystems(MASS’06). Vancouver, BC, Canada,2006,397-406
[109] Yang S, Dai F, Cardei M, et al. On connected multiple point coverage in wirelesssensor networks. International Journal of Wirelesss information networks,2006,13(4):289-301
[110] Shih K P, Chen H C, Chou C M, et al. On target coverage in wirelessheterogeneous sensor networks with multiple sensing units. Journal of Networkand Computer applications,2009,32(4):866-877
[111] Yang S, Dai F, Cardei M, et al. On multiple point coverage in wireless sensornetworks. In: Proc. of IEEE International Conference on Mobile Ad-hoc andSensor Systems (MASS’05).Washington, DC, USA,2005,757–764
[112] Wang J, Niu C, Shen R. Priority-based target coverage in directional sensornetworks using a genetic algorithm. Computers and Mathematics withApplications.2009,57(11):1915-1922
[113] Wang B, Chua K C, Srinivasan V, et al. Scheduling sensor activity forinformation coverage of discrete targets in sensor networks. WirelessCommunications and Mobile Computing,2009,9(6):745-757
[114] Wang B, Chua K C, Srinivasan V, et al. Scheduling sensor activity for pointinformation coverage in wireless sensor networks. In: Proc. of the4thInternational Symposium on Modeling and Optimization in Mobile, Ad Hoc, andWireless Networks (WiOpt’06). Boston, Massachusetts, USA,2006,353-360
[115] Cai Y, Lou W, Li M. Target-oriented scheduling in directional sensor networks.In: Proc. of the26th IEEE Conference on Computer Communications(INFOCOM’07), Anchorage, Alaska, USA,2007,1550-1558
[116] Wang J, Zhong N. Efficient point coverage in wireless sensor networks. Journalof Combinatorial Optimization,2006,11(3):291–304
[117] Kong L, Liu X, Li Z, et al. Automatic Barrier coverage formation with mobilesensor networks. In: Proc. of the IEEE international conference onCommunications (ICC’10). Cape Town, South Africa,2010,1-5
[118] Kumar S, Lai T H, Arora A. Barrier coverage with wireless sensors. In: Proc. ofthe11th annual international conference on Mobile computing and networking(Mobicom’05). Cologne, Germany,2005,284-298
[119] Chen A, Kumar S, Lai T H. Designing localized algorithms for barrier coverage.In: Proc. of the13th annual ACM international conference on Mobile computingand networking (MobiCom’07). Montreal, QC, Canada,2007,63-74
[120] Saipulla A, Westphal C, Liu B, et al. Barrier coverage of line-based deployedwireless sensor networks. In: Proc. of the28th IEEE International conference onComputer communications (INFOCOM’09). Rio de Janeiro, Brazil,2009,127-135
[121] Jiang C D, Chen G L. Double barrier coverage in dense sensor networks. Journalof Computer Science and Technology,2008,23(1):154-166
[122] Ssu K F, Wang W T, Wu F K, et al. k-barrier coverage with a directional sensingmodel. International Journal on Smart sensing and Intelligent systems,2009,2(1):75-93
[123] Li L, Zhang B, Shen X, et al. A study on the weak barrier coverage problem inwireless sensor networks. Computer Networks,2010,55(3):711-721
[124] Zhang L, Tang J, Zhang W. Strong barrier coverage with directional sensors. In:Proc. of the28th IEEE International Conference on Global telecommunications(Globecom’09). Honolulu, Hawaii, USA,2009,1816-1821
[125] Liu B, Dousse O, Wang J, et al. Strong barrier coverage of wireless sensornetworks. In: Proc. of the9th ACM international symposium on Mobile ad hocnetworking and computering (MobiHoc’08). Hong Kong, China,2008,411–419
[126] Meguerdichian S, Slijepcevic S, Karayan V, et al. Localized algorithms inwireless ad-hoc networks: location discovery and sensor exposure. In: Proc. ofthe2nd ACM international symposium on Mobile ad hoc networking andcomputering (Mobihoc’01). Long Beach, California, USA,2001,106-116
[127] Meguerdichian S, Koushanfar F, Qu G, et al. Exposure in wireless ad-hoc sensornetworks. In: Proc. of the7th annual International Conference on MobileComputing and Networking (Mobicom’01). Rome, Italy,2001,139–150
[128] Yang G Q, Qiao D J. Barrier Information Coverage with Wireless Sensors. In:Proc. of the28th IEEE International Conference on Computer Communications(INFOCOM’09). Rio de Janeiro, Brazil,2009,918-926
[129] Meguerdichian S, Koushanfar F, Potkonjak M, et al. Worst and best-casecoverage in sensor networks. IEEE Transactions on Mobile Computing,2005,4(1):84-92
[130] Meguerdichian S, Koushanfar F, Potkonjak M, et al. Coverage problems inwireless ad-hoc sensor networks. In: Proc. of the20th IEEE InternationalConference on Computer Communications (INFOCOM’01). Anchorage, Alaska,USA,2001,1380-1387
[131] Li X Y, Wan P, Frieder O. Coverage in wireless ad-hoc sensor networks. IEEETransactionson on Computers,2003,52(6):753–763
[132] Veltri G, Huang Q, Qu G, et al. Minimal and maximal exposure path algorithmsfor wireless embedded sensor networks. In: Proc. of the1st internationalconference on Embedded networked sensor system (SenSys’03), Los Angeles,California, USA,2003,40-50
[133] Veradej P, Ramanathan P. Vulnerability of sensor networks to unauthorizedtraversal and monitoring. IEEE Transactionson on Computers,2004,53(3):364-369
[134]张文哲,李明禄,伍民友.一种基于局部Voronoi图的目标穿越算法.软件学报,2007,18(5):1246-1253
[135]陈喆,王雷.传感环境下一种启发式反监控路径搜索算法.计算机应用,2008,28(11):2767-2770
[136] Liu B, Towsley D. On the Coverage and Detectability of Large-scale WirelessSensor Networks. In: Proc. of the1st International Symposium on Modeling andOptimization in Mobile, Ad Hoc, and Wireless Networks(WiOpt'03). INRIASophia-Antipolis, France,2003
[137] Liu B, Towsley D. A study of the coverage of large-scale sensor networks. In:Proc. of IEEE International conference on Mobile ad hoc and Sensor Systems(MASS’04). Fort Lauderdale, Florida, USA,2004,475-483
[138] Adlakha S, Srivastava M. Critical Density Thresholds for Coverage in WirelessSensor Networks. In: Proc. of IEEE International conference on WirelessCommunications and Networking (WCNC'03). New Orleans, Louisiana, USA,2003,1615-1620
[139]申兴发,陈积明,王智等.面向移动目标的传感器网络覆盖质量度量与优化.通信学报,2008,29(11):246-252
[140] Zhou S, Wu M Y, Shu W. Blocking vulnerable paths of wireless sensor networks.In: Proc. of the25th IEEE International conference on Global telecommunica-tions (Globecom’06). San Francisco, California, USA,2006,1-5
[141] Balister P, Bollobas B, Sarkar A, et al. Reliable density estimates for coverageand connectivity in thin strips of finite length. In: Proc. of the13th annual ACMInternational conference on Mobile computing and networking (MobiCom’07).Montreal, QC, Canada,2007,75-86
[142] Kumar S, Lai T H, Posner M E, et al. Optimal sleep wakeup algorithms forbarriers of wireless sensors. In: Proc. of the4th International conference onBroadband communications, networks, systems (Broadnets’07). North Carolina,USA,2007,327-336
[143]臧传治,于海斌,梁桦,白洁音.无线传感器网络覆盖问题中的目标最优运动模式.控制与决策,2006,21(10):1119-1123
[144] Harada J, Shioda S, Saito H. Path coverage property of randomly deployedsensor networks with finite data-communication ranges. Computer Networks.2009,53(7):1014-1026
[145] Zabarankin M, Uryasev S, Pardalos P. Optimal risk path algorithms. CooperativeControl and Optimization,2002,66:273-298
[146] Chin T L, Ramanathan P, K Saluja K K,et al. Exposure for collaborativedetection using mobile sensor networks. In: Proc. of the2nd IEEE Internationalconference on Mobile Ad hoc and sensor systems (MASS’05). Washington, DC,USA,2005,743-750
[147] Okabe A, Boots B, Sugihara K, et al. Spatial tessellations: concepts andapplications of voronoi diagram,2nd ed. New York: John Wiley＆Sons,1999
[148] Kuipers F A, Van Mieghem P, Korkmaz T, et al. An overview of constraint-based path selection algorithms for QoS routing. IEEE CommunicationsMagazine,2002,40(12):50-55
[149] Juttner A, Szviatovszki B, Mecs I, et al. Lagrange relaxation based method forthe qos routing problem. In: Proc. of the20th IEEE International Conference onComputer Communications (INFOCOM’01). Anchorage, Alaska, USA,2001,2:859-868
[150] Jia Z F, Varaiya P. Heuristic methods for delay constrained least cost routingusing k-Shortest-Paths. IEEE Transactions on Automatic control,2006,51(4):707-712
[151] Eppstein D. Finding the k shortest paths. SIAM Journal on Computing,1999,28(2):652-673
[152] Zhang W Z, Li M L, Shu W, et al. Smart path-finding with local information in asensory field. In Proc. of the2nd International Conference on Mobile Ad-hoc andSensor Networks (MSN’06). Hong Kong, China,2006,119-130
[153] Mehlhorn K, Ziegelmann M. Resource constraint shortest paths. In: Proc. of the8th Annual European Symposium on Algorithms (ESA’00). Saarbrucken,Germany,2000,326-337
[154] Dumitrescu I. Constrained path and cycle problems:[dissertation]. Melbourne:The University of Melbourne,2002
[155] Gellermann T, Sellmann M. Wright R. Shorter path constraints for the resourceconstrained shortest path problem. In: Proc. of the2nd International Conferenceon the Integration of AI and OR Techniques in Constraint programming forCombinatorial optimization problems (CPAIOR’05). Prague, Czech Republic,2005,201-216
[156] Dumitrescu I, Boland N. Improving preprocessing, labeling and scalingalgorithms for the weight constrained shortest path problem. Networks,2003,42(3):135-153
[157] Buragohain C, Agrawal D, Suri S. Distributed navigation algorithms for sensornetworks. In: Proc. of the25th IEEE International Conference on ComputerCommunications (INFOCOM’06). Barcelona, Spain,2006,1-10
[158] Ma H D, Liu Y H. On coverage problems of directional sensor networks. In: Proc.of the1st International Conference on Mobile Ad-hoc and Sensor Networks(MSN’05).2005,721-731
[159] Ma H D, Zhang X, Ming A L. A coverage-enhancing method for3D directionalsensor networks. In: Proc. of the28th IEEE International Conference onComputer communications (INFOCOM’09). Rio de Janeiro, Brazil,2009,2791-2795
[160]陶丹,马华东,刘亮.基于虚拟势场的有向传感器网络覆盖增强算法.软件学报.2007,18(5):1152-1163．
[161] Ai J, Abouzeid A A. Coverage by directional sensors in randomly deployedwireless sensor networks. Journal of Combinatorial Optimization,2006,l1(1):21-41
[162]温俊,蒋杰,窦文华.公平的有向传感器网络方向优化和节点调度算法.软件学报,2009,20(3): l644-659
[163] Tezean N, Wang W Y. Self-orienting wireless multimedia sensor networks formaximizing multimedia coverage. In: Proc. of the IEEE International Conferenceon Communications (ICC’08). Beijing, China,2008:2206-2210
[164]程卫芳,廖湘科,沈昌祥.有向传感器网络最大覆盖调度算法.软件学报,2009,20(4):975-984
[165] Ram S S,Manjunath D,Iyer S K, et al. On the path coverage properties of randomsensor networks. IEEE Transactions on Mobile Computing,2007,6(5):494-506
[166] Manohar P, Ram S S, Manjunath D. Path coverage by a sensor field: thenonhomogeneous case. ACM Transactions on Sensor Networks,2009,5(2):1-26.
[167] Harada J, Shioda S, Saito H. Path coverage property of randomly deployedsensor networks with finite communication ranges. In: Proc. of the IEEEInternational Conference on Communications (ICC’08). Beijing, China,2008,2221-2227
[168]李磊,张宝贤,黄河清等.无线传感器网络路径覆盖问题研究.电子与信息学报,2010,32(10):1752-1757
[169] Noori M, Movaghati S, Ardakani M. Characterizing the path coverage of randomwireless sensor networks. EURASIP Journal on Wireless Communi-cations andNetworking,2010,2010(14):1-11
[170]陶丹,马华东,刘亮.视频传感器网络中路径覆盖增强算法研究.电子学报,2008,36(7)：1291-1296
[171]肖甫,王汝传,叶晓国,孙力娟.基于改进势场的有向传感器网络路径覆盖增强算法.计算机研究与发展,2009,46(12):2126-2133
[172] Adriaens J, Megerian S, Potkonjak M. Optimal worst-case coverage ofdirectional field-of-view sensor networks. In: Proc. of the3rd Annual IEEECommunications Society on Sensor, Mesh and Ad hoc Communications andNetworks (SECON’06). Reston, VA, USA,2006,336-345
[173] Ma H D, Liu Y H. Some problems of directional sensor networks. InternationalJournal of Sensor Networks,2007,2(1):44-52
[174] Saipulla A, Liu B Y, Xing G L, et al. Barrier coverage with sensors of limitedmobility. In: Proc. of the11th ACM international symposium on Mobile ad hocnetworking and computing (MobiHoc’10).Chiagao, Lllinois,USA,2010,201-210
[175] Chen A, Li Z Z, Lai T H, et al. One-way barrier coverage with wireless sensors.In: Proc. of the30th IEEE International Conference on ComputerCommunications (INFOCOM’11), Shanghai, China,2011:626-630
[176] Saipulla A, Liu B Y, Wang J. Finding and mending barrier gaps in wirelesssensor networks. In: Proc. of the30th IEEE International conference on Globaltelecommunications (Globecom’10). Miami, FL, USA,2010,1-5
[177] Yang G Q, Qiao D J. Multi-round sensor deployment for guaranteed barriercoverage. In: Proc. of the29th IEEE International Conference on ComputerCommunications (INFOCOM’10). San Diego, CA, USA,2010,1-9
[178] Hefeeda M, Ahmadi H. Energy-efficient protocol for deterministic andprobabilistic coverage in sensor networks. IEEE Transactions on Parallel andDistributed Systems,2010,21(5):579-593
[179] Xing G L, Tan R, Liu B Y, et al. Data fusion improves the coverage of wirelesssensor networks. In: Proc. of the15th Annual International Conference onMobile computing and networking (Mobicom’09). Beijing,China,2009,157-168
[180] Dousse O. Asymptotic properties of wireless multi-hop networks:[dissertation].Lausanne: Seiss Federal Institute of Technology.2005,81-100
[181] Hefeeda M, Ahmadi H. A probabilistic coverage protocol for wireless sensornetworks. in: Proc. of the IEEE International Conference on Network Protocols(ICNP’07), Beijing, China,2007,41-50
[182] Xu Y, Heidemann J, Estrin D. Geography-informed energy conservation for adhoc routing. In: Proc. of the7th Annual International Conference on MobileComputing and Networking (MobiCom’01). Rome, Italy,2001,70–84
[183] Chen B, Jamieson K, Balakrishnana H, et al. Span: an energy-efficientcoordination algorithm for topology maintenance in ad hoc wireless networks. In:Proc. of the7th Annual International Conference on Mobile Computing andNetworking (Mobicom’01). Rome,Italy,2001,85–96
[184] Cerpa A, Estrin D. ASCENT: Adaptive self-configuring sensor networkstopologies. IEEE Transactions on Mobile Computing,2004,3(3):272–285
[185] Xu Y, Heidemann J, Estrin D. Adaptive energy-conserving routing for multihopad hoc networks. http://www.isi.edu/~johnh/PAPERS/Xu00a.html,2010-9-16
[186] Hekmat R, Van Mieghem P. Connectivity in wireless ad-hoc networks with alog-normal radio model. Mobile Networks and Applications,2006,11(3):351–360
[187] Bettstetter C, Hartmann C. Connectivity of wireless multihop networks in ashadow fading environment. In: Proc. of the6th ACM International workshop onModeling analysis and simulation of wireless and mobile systems (MSWIM’03).San Diego, CA, USA,2003,28–32
[188] Miorandi D, Altman E. Coverage and connectivity of ad hoc networks inpresence of channel randomness. In: Proc. of the24th IEEE InternationalConference on Computer Communications (INFOCOM’05). Miami, FL, USA,2005,491–502
[189] Dousse O, Baccelli F, Thiran P. Impact of interferences on connectivity in ad-hocnetworks. IEEE/ACM Transactions on Networking,2005,13(2):425–436
[190] Xing G L, Wang X R, Zhang Y F, et al. Integrated coverage and connectivityconfiguration for energy conservation in sensor networks. ACM Transactions onSensor Networks,2005,1(1):36–72
[191] Gupta H, Zhou Z H, Das S R. Connected sensor cover:self-organization of sensornetworks for efficient query execution. ACM/IEEE Transactions on Networking,2006,14(1):55-67
[192]蒋杰,方力,张鹤颖,窦文华.无线传感器网络最小连通覆盖集问题求解算法.软件学报,2006,17(2):175-184
[193] Hefeeda M, Ahmadi H. An integrated protocol for maintaining connectivity andcoverage under probabilistic models for wireless sensor networks. Ad Hoc&Sensor Wireless Networks,2009,7(3):295–323