无线传感器网络点覆盖技术研究
|
摘要
无线传感器网络是由具备感知、数据处理、存储和数据传输的传感器节点自组织而形成的无线网络,在军用和民用领域有着广泛的应用前景。覆盖问题是无线传感器网络的重要问题之一,它是反映无线传感器网络服务质量的一项重要性能指标。由于受到能量的约束,覆盖问题的主要任务是找出较小的覆盖集,并使这些集合能独立完成所需要的任务,而其它节点则处于低功耗的休眠状态。
目前,点覆盖问题研究一般着重于设计集中式优化算法,这些算法对无线传感器网络的实际应用存在一定的局限性。本文以布尔感知模型为基础,通过发掘点覆盖问题中应用场景,研究分布式、集中式以及集中式算法的局部化处理算法。针对点覆盖问题中目标点分布对覆盖集连通性的制约,本文也系统地研究了覆盖连通问题,并提出了相应的连通算法。
本文首先讨论了无线传感器网络节点冗余覆盖调度机制,进而提出了一种分布式算法SRCA。该算法通过检测网络中的覆盖冗余节点,让部分冗余节点休眠,从而降低网络的冗余覆盖程度。SRCA算法在保证网络初始覆盖的同时,能够有效地降低系统能量消耗,延长网络的生存时间。
面向无线传感器网络的一种应用场景,本文提出了一种基于遗传算法的传感器节点调度的一种集中式近似算法—NSAGA算法。该算法期望利用遗传算法的种群特性,求解无线传感器网络覆盖子集。该算法每次迭代可以同时产生多个满足条件的覆盖子集,还可以根据覆盖要求改变约束条件,满足不同的应用场景。
针对目前点覆盖调度的算法一般都将覆盖问题转化为数学规划模型,然后采用集中式算法近似算法求解。虽然这种求解方式比分布式算法的精度高,但不适合大规模无线传感器网络。为此,本文提出了一种将集中式算法进行局部化的思想,并提出了一种分布式LCACA算法。该算法首先选举局部中心节点将整个网络划分成多个规模较小的网络。然后在每个划分的网络中再运行集中式算法,完成传感器节点的调度。而且,该算法还可以根据不同子区域的目标的覆盖要求,通过划分网络后,在每个划分的网络上运行不同的调度算法。
一般点覆盖算法大多假设覆盖与连通是一致的,并没有考虑被监测的目标分布情况对网络连通性的影响。为此本文讨论了点覆盖与连通性的关系,提出了一种基于Steiner树集中式连通算法—CCAST算法。该算法首先将所有连通簇看成一个虚拟节点,然后构建加权通信图并调用已有构造Steiner树的算法挑选出Steiner点,使得所有的覆盖节点保持连通。接着,本文又进一步提出了一种分布式连通算法DCAVIS。该算法首先构造虚拟独立集,然后寻找使覆盖集成为连通集的中继节点。DCAVIS算法为解决点覆盖连通问题可提供了一种分布式近似求解算法,同时可以有效延长无线传感器网络的生存时间。
综上所述,本文以无线传感器网络点覆盖问题为主要目标,从分布式、集中式以及集中式算法的局部化三方面研究了点覆盖算法,其中,集中式算法的局部化还可做为以后的工作进一步研究。
Wireless sensor networks are such kind of integrated wireless networks which perform sensoring, data processing, storage and delivering. There are wide applications for the networks in both military and civil affairs. The coverage problem is one of the important issues in wireless sensor networks and reflects the quality of service. With the energy constraint, one main requirement of the coverage problem is to find a small subset of sensor nodes such that this subset can independently perform the required tasks while other redundant nodes enter into the low energy sleep status.
At present, researchers stress the central optimize algorithm which restrict practicality use to solve the point coverage problems. By exploring new application scenario in the point coverage issues, this dissertation aims to the point coverage problems to research the relevant algorithms based on Boolean sensoring model. Considering the restriction of the object distribution to the connectivity, this dissertation also studies the connected coverage problems to put forward a relevant algorithm.
This dissertation first discusses the redundant nodes scheduling mechanism for wireless sensor networks. Furthermore, a distributed algorithm SRCA is put forward in the dissertation. This algorithm checks the redundant nodes in the network to make the redundant nodes sleep such that the redundant nodes are reduced obviously in the network. SRCA can effectively reduce the energy expense so to prolong the network lifetime.
Toward an application scenario, this dissertation proposed a sensor node approximately scheduling algorithm NSAGA based on genetic algorithm. This algorithm utilizes the population characteristic to solve the coverage subset. NSAGA can not only produce a few of coverage subsets to satisfy the coverage requirements in an iterative but also suit to diverse application scenarios by changing the restriction according to the coverage requirement.
Nowadays, the algorithms translate the point coverage problems into mathematic programming models, and then solve the mathematic programming by the central approximate algorithm. Although the method is of better precision, it is unsuitable for the large wireless sensor network. Therefore, this dissertation proposed a method to localize central algorithms, then a distributed algorithm LCACA is put forward. LCACA first elects the local central nodes to divide the network into a few of small scale subnets. Then, the central algorithm can be performed in these subnets. The algorithm can perform different scheduling algorithms in wireless sensor networks according to the sub-area coverage requirement.
Since current point coverage algorithms which are proposed in case of coinciding the coverage with connectivity ignore the influence of the object distribution over connectivity. A central algorithm CCAST based on Steiner tree is proposed. CCAST first translates a connected cluster into a virtual node. Then, it constructs a weighted graph and calls current algorithm to pick out nodes which connect the network. Furthermore, a distributed algorithm DCAVIS is proposed. The algorithm first constructs a virtual independent set, and then finds out relay nodes.
In summary, aiming at the point coverage issues, this dissertation discussed the point coverage problem in the distributed algorithm, central algorithm and the method to localize the central algorithm. The method to localize the central algorithm can be further exploited for future research.
目前,点覆盖问题研究一般着重于设计集中式优化算法,这些算法对无线传感器网络的实际应用存在一定的局限性。本文以布尔感知模型为基础,通过发掘点覆盖问题中应用场景,研究分布式、集中式以及集中式算法的局部化处理算法。针对点覆盖问题中目标点分布对覆盖集连通性的制约,本文也系统地研究了覆盖连通问题,并提出了相应的连通算法。
本文首先讨论了无线传感器网络节点冗余覆盖调度机制,进而提出了一种分布式算法SRCA。该算法通过检测网络中的覆盖冗余节点,让部分冗余节点休眠,从而降低网络的冗余覆盖程度。SRCA算法在保证网络初始覆盖的同时,能够有效地降低系统能量消耗,延长网络的生存时间。
面向无线传感器网络的一种应用场景,本文提出了一种基于遗传算法的传感器节点调度的一种集中式近似算法—NSAGA算法。该算法期望利用遗传算法的种群特性,求解无线传感器网络覆盖子集。该算法每次迭代可以同时产生多个满足条件的覆盖子集,还可以根据覆盖要求改变约束条件,满足不同的应用场景。
针对目前点覆盖调度的算法一般都将覆盖问题转化为数学规划模型,然后采用集中式算法近似算法求解。虽然这种求解方式比分布式算法的精度高,但不适合大规模无线传感器网络。为此,本文提出了一种将集中式算法进行局部化的思想,并提出了一种分布式LCACA算法。该算法首先选举局部中心节点将整个网络划分成多个规模较小的网络。然后在每个划分的网络中再运行集中式算法,完成传感器节点的调度。而且,该算法还可以根据不同子区域的目标的覆盖要求,通过划分网络后,在每个划分的网络上运行不同的调度算法。
一般点覆盖算法大多假设覆盖与连通是一致的,并没有考虑被监测的目标分布情况对网络连通性的影响。为此本文讨论了点覆盖与连通性的关系,提出了一种基于Steiner树集中式连通算法—CCAST算法。该算法首先将所有连通簇看成一个虚拟节点,然后构建加权通信图并调用已有构造Steiner树的算法挑选出Steiner点,使得所有的覆盖节点保持连通。接着,本文又进一步提出了一种分布式连通算法DCAVIS。该算法首先构造虚拟独立集,然后寻找使覆盖集成为连通集的中继节点。DCAVIS算法为解决点覆盖连通问题可提供了一种分布式近似求解算法,同时可以有效延长无线传感器网络的生存时间。
综上所述,本文以无线传感器网络点覆盖问题为主要目标,从分布式、集中式以及集中式算法的局部化三方面研究了点覆盖算法,其中,集中式算法的局部化还可做为以后的工作进一步研究。
Wireless sensor networks are such kind of integrated wireless networks which perform sensoring, data processing, storage and delivering. There are wide applications for the networks in both military and civil affairs. The coverage problem is one of the important issues in wireless sensor networks and reflects the quality of service. With the energy constraint, one main requirement of the coverage problem is to find a small subset of sensor nodes such that this subset can independently perform the required tasks while other redundant nodes enter into the low energy sleep status.
At present, researchers stress the central optimize algorithm which restrict practicality use to solve the point coverage problems. By exploring new application scenario in the point coverage issues, this dissertation aims to the point coverage problems to research the relevant algorithms based on Boolean sensoring model. Considering the restriction of the object distribution to the connectivity, this dissertation also studies the connected coverage problems to put forward a relevant algorithm.
This dissertation first discusses the redundant nodes scheduling mechanism for wireless sensor networks. Furthermore, a distributed algorithm SRCA is put forward in the dissertation. This algorithm checks the redundant nodes in the network to make the redundant nodes sleep such that the redundant nodes are reduced obviously in the network. SRCA can effectively reduce the energy expense so to prolong the network lifetime.
Toward an application scenario, this dissertation proposed a sensor node approximately scheduling algorithm NSAGA based on genetic algorithm. This algorithm utilizes the population characteristic to solve the coverage subset. NSAGA can not only produce a few of coverage subsets to satisfy the coverage requirements in an iterative but also suit to diverse application scenarios by changing the restriction according to the coverage requirement.
Nowadays, the algorithms translate the point coverage problems into mathematic programming models, and then solve the mathematic programming by the central approximate algorithm. Although the method is of better precision, it is unsuitable for the large wireless sensor network. Therefore, this dissertation proposed a method to localize central algorithms, then a distributed algorithm LCACA is put forward. LCACA first elects the local central nodes to divide the network into a few of small scale subnets. Then, the central algorithm can be performed in these subnets. The algorithm can perform different scheduling algorithms in wireless sensor networks according to the sub-area coverage requirement.
Since current point coverage algorithms which are proposed in case of coinciding the coverage with connectivity ignore the influence of the object distribution over connectivity. A central algorithm CCAST based on Steiner tree is proposed. CCAST first translates a connected cluster into a virtual node. Then, it constructs a weighted graph and calls current algorithm to pick out nodes which connect the network. Furthermore, a distributed algorithm DCAVIS is proposed. The algorithm first constructs a virtual independent set, and then finds out relay nodes.
In summary, aiming at the point coverage issues, this dissertation discussed the point coverage problem in the distributed algorithm, central algorithm and the method to localize the central algorithm. The method to localize the central algorithm can be further exploited for future research.
引文
[1] 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.
[2] Bettstetter C, Hartmann C. Connectivity of wireless multihop networks in a shadow fading environment [C] .The 8th International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems. San Diego: MSWiM, 2003:28-32.
[3] M. Roussopoulos, M. Baker. Controlled Update Propagation in Peer-to-Peer Networks. Proceedings of USENIX Annual Technical Conference. 2003.
[4] S.H.L.Liang, V.Tao, A.Croitoru. The Design and Prototype of a Distributed Geospatial Infrastructure for Smart Sensor Web. Proceedings of the 6th AGILE Conference on Geographic Information Science.2003
[5] A. Cerpa, J. Elson, M. Hamilton, and 1. Zhao, Habitat Monitoring: Application Driver for Wireless Communications Technology. First ACM SIGCOMM Workshop on Data Communication in Latin America and the Caribbean, April 2001.
[6] J.R. Polastre, D. Culler. Design and Implementation of Wireless Sensor Networks for Habitat Monitoring, University of California at Berkeley, 2003.
[7] P.Bonnet, J.Gehrke, P.Seshadri. Querying the Physical World. IEEE Personal Communications, 2000, 7.
[8] Rabaey J M, Ammer M J, da Silva J L Jr. Patel D, Roundy S. PicoRadio supports ad hoc ultra-low power wireless networking[J]. IEEE Computer Magazine 2000:42-48
[9] D. Estrin, R. Govindan, J. Heidemann, et al.. Next century challenges :scalable coordination in sensor networks. ACM MOBICOM, Seattle, WA, August 1999.
[10] N. Bulusu, D. Estrin, L. Girod, J. Heidemann, Scalable coordination for wireless sensor networks: self-configuring localization systems, International Symposium on Communication Theory and Applications (ISCTA 2001), Ambleside, UK, July 2001.
[11] P. Bauer, M. Sichitiu, R. Istepanian and K. Premaratne. The Mobile Patient: Wireless Distributed Sensor Networks for patient monitoring and Care. In Proc. IEEE EMBS International Conference on Information Technology Applications in Biomedicine, Arlington, pp. 17-21,2000.
[12] http://www.agingtech.org.
[13] http://www.rfidjournal.com/article/view/3625/.
[14] I.F.Akyildiz,W.Su, Y.Sankarasubramaniam, E.Cayirci. A Survey on Sensor Networks. IEEE Communications Magazine, 2002,40(8): 102-114.
[15] Conrad J G.CEC:Sensor Netting with Integrated Fire Control[J].Johns Hopkins APL Technical Digest,2002,23(2):2-3.
[16]http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/MICA.pdf
[17]http://bwrc.eecs.berkeley.edu
[18]UCLA.Medusa MK-2 Programming Resource[EB/OL].http://nesl.ee.ucla.edu/projects/ahlos/mk2/,2003-10.
[19]http://www.intel.com/research/exploratory/motes.htm.
[20]UC Berkeley.TinyOS:An Open-source Operating System Designed for Wireless Embedded Sensor Networks[EB/OL].http://www.tinyos.net/,2003-10.
[21]http://mantis.cs.colorado.edu/index.php/tiki-index.php.
[22]http://nesl.ee.ucla.edu/proj cots/sos/.
[23]http://www.cast.cse.ohio-state.edu/exscal/.
[24]http://projects.cerias.urdue.edu/esp/.
[25]http://www.eng.yale.edu/enalab
[26]http://www.eecs.harvard.edu/～mdw/proj/codeblue/.
[27]http://wings.cs.sunysb.edu.
[28]http://www robotics.usc.edu/embedded/.
[29]http://www.isi.edu/scadds/.
[30]http://www.ece.gatech.edu/researchAabs/bwn/index.html.
[31]http://www.zurich.ibm.com/sys/communication/sensors.html.
[32]http://www.intel.com/research/exploratory/wireless_sensors.htm.
[33]http://research.microsoft.com/nec/.
[34]P.Berman,G.Calinescu,C.Shah and A.Zelikovsky.Power Efficient Monitoring Management in Sensor Networks,Proceedings of WCNC'04,March 2004.
[35]S.Slijepcevic and M.Potkonjak.Power Efficient Organization of Wireless Sensor Networks,IEEE International Conference on Communications,June 2001.
[36]J.Jiang and W.Dou.A Coverage-Preserving Density Control Algorithm for Wireless Sensor Networks.In International Conference on AD-HOC Networks &Wireless(ADHOC-NOW),pp.42-55,July 2004.
[37]Dhillon S S,Chakrabarty K,Iyengar S S.Sensor placement for grid coverage under imprecise detections[C].Proceeding of International Conference on Information Fusion,2002:158 -1587.
[38]Dhillon S S,Chakrabarty K.Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks[C].Proceeding of IEEE WCNC 2003.New Orleans,Louisiana,USA,2003:1609-1614.
[39]Zou Y,Chakrabarty K.Sensor deployment and target localization in distributed sensor networks.ACM Trans.on Embedded Computing Systems,2004,3(1):61-91.
[40]J.Lu,et al..Coverage-aware Self-scheduling in Sensor Networks.In Proc.of CCW 2003,Oct.2003,pp.117-123.
[41]Nadeem Ahmed,Salil S.Kanhere,Sanjay Jha.Probabilistic Coverage in Wireless Sensor Networks.Fifth International IEEE Workshop on Wireless Local Networks(WLN 2005), pp. 672-681,2005.
[42] T. S. Rappaport, Wireless communications,Principles and Practice, Prentice Hall, New Jersey, 1996.
[43] H.Ma,Y.Liu. On coverage problems of directional sensor networks.Proceedings of the International Conference on Mobile Ad-Hoc and Sensor Networks.2005.
[44] Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks. In: Glisic S, ed. Proc. of the IEEE Int'l Conf. on Communications (ICC). Helsinki: IEEE Press, 2001, 472-476.
[45] P. Berman, G. Calinescu,C.Shah, et.al.. Power Efficient Monitoring Management in wireless sensor networks. Proceedings of IEEE Wireless Communication and Networking Conference(WCNC04), Allanta, USA, 2004.
[46] Abrams Z, Goel A, Plotkin S. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. 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.
[47] F. Ye, G. Zhong, S. Lu, and L. Zhang, Energy. Efficient Robust Sensing Coverage in Large Sensor Networks. Technical Report UCLA (2002).
[48] Ye F, Zhong G, Lu S, Zhang L. PEAS: A robust energy conserving protocol for long-lived sensor networks. In: Stankovic J, Zhao W, eds. Proc. of the Int'l Conf. on Distributed Computing Systems (ICDCS). Providence: IEEE Press, 2003. 28-37.
[49] Tian D, Georganas N. A coverage-preserving node scheduling scheme for large wireless sensor networks. In: Raghavendra CS, Sivalingam K, eds. Proc. of the 1st Int'l Workshop on Wireless Sensor Networks and Applications (WSNA 2002). Atlanta: ACM Press, 2002, 32-41.
[50] Tian, D., and Georganas, N. D. A node scheduling scheme for energy conservation in large sensor networks. Journal of Wireless Communications and Mobile Computing 3 (2003), 271(290. Special issue on Algorithmic, Geometric, Graph, Combinatorial, and Vector Aspects of Wireless Networks and Mobile Computing.
[51] Yah T, He T, Stankovic J. Differentiated surveillance service for sensor networks. 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.
[52] Howard A,Mataric M J, Sukhatme G S. Mobile Sensor Network Deployment using Potential Fields: a distributed, Scalable Solution to the Area Coverage Problem[C]. In: Proceeding of International Conference on Distributed Autonomous Robotic Systems,2002:299-308
[53] Zou Y, Chakrabarty K.Sensor Deployment and Target Localization based on Virtual Forces[C]. In: Proceeding of IEEE INFOCOM, 2003:1293-1303
[54] Heo N, Varshney P K. An Intelligent Deployment and Clustering Algorithm for a Distributed Mobile Sensor Network[C]. In Proceeding of IEEE International Conference on Systems, Man and Cybernetics, 2003: 4576- 4581
[55] G.Wang, G.Cao, T.La Porta. A Bidding Protocol for Deploying Mobile Sensors. Proceedings of the 11th IEEE International Conference on Network Protocols(ICNP'03),2003
[56] G.Wang, G.Cao, T.La Porta, Movement-Assisted Sensor Deployment, Proceedings of IEEE INFOCOM'04, HongKong, 2004
[57] G.Wang, G.Cao, T.La Porta, Proxy-based Sensor Deployment for Mobile Sensor Networks, Proceedings of the 1 st IEEE International Conference on Mobile Ad-hoc and Sensor Systems(MASS'04),Fort Lauderdale, Florida, 2004
[58] G.Wang, G.Cao, T.Porta, W.Zhang. Sensor Relocation in Mobile Sensor Networks. Proceedings of IEEE INFOCOM'05, Miami, Florida,2005
[59] J.Wang, D.Du, E.Kusmierek. Energy Efficient Oragnization of Mobile Sensor Networks, Proceedings of the 2004 International Conference on Parallel Processing Workshops(ICPPW'04),Montreal,Quebec,Canada,2004
[60] Basagni S. Distributed Clustering for Adoc hoc Networks[C]. In: Proceeding of IEEE International symposium on Parallel Architectures, Algorithms, and Networks, 1999:310-315
[61] B.Liu,P.Brass,O.Dousse,P.Nain,D.Towsley.Mobility Improves Coverage of Sensor Network,Proceedings of ACM Mobihoc'05, Urbana-Champaign,IL,2005
[62] Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava MB. Coverage problems in wireless ad-hoc sensor network. In: Sengupta B, ed. Proc. of the IEEE INFOCOM. Anchorage: IEEE Press, 2001. 1380-1387.
[63] Xiang-Yang Li, Peng-Jun Wan, Ophir Frieder. Coverage in Wireless Ad-Hoc Sensor Networks. Proc. IEEE Trans. Computers, 2003, vol.52(6): 753-763.
[64] Meguerdichian S, Koushanfar F, Qu G, Potkonjak M. Exposure in wireless ad-hoc sensor networks. In: Rose C, ed. Proc. of the ACM Int'l Conf. on Mobile Computing and Networking (MobiCom). New York: ACM Press, 2001. 139-150.
[65] Cheng M X,Ruan L,Wu W.Achieving Minimum Coverage Breach Under Bandwidth Constraints in Wireless Sensor Networks[C].Proc of the 24th Conf of the IEEE Communications Society, 2005.
[66] Adlakha S, Srivastava M. Critical density thresholds for coverage in wireless sensor networks. In: Tachikawa K, ed. Proc. of the IEEE Wireless Communications and Networking (WCNC). New Orleans: IEEE Press, 2003. 1615-1620.
[67] B. Liu, D. Towaley. On the Coverage and Detectability of Large-scale. Wireless Sensor Networks. Proc. of the Modeling and Optimization in Mobile, Ad hoc and Wireless Networks, INRIA Sophia-Antipolis, France, 2003
[68] R. Meester and R. Roy. Continuum percolation, Cambridge University Press, Cambridge, 1996.21.
[69] Liu B, Towsley D. A study of the coverage of large-scale sensor networks. In: Proc. of the ACM Mobile Ad-Hoc and Sensor Systems (MASS'04). New York: ACM Press, 2004. 475-483
[70] Cardei M, Du DZ. Improving wireless sensor network lifetime through power aware organization. Wireless Networks, 2005,11(3): 333-340.
[71] Cardei M, Thai MT, Li Y. Energy-Efficient target coverage in wireless sensor networks. In: Raton B, ed. Proc. of the IEEE INFOCOM. Miami: IEEE Computer Society, 2005. 1976-1984.
[72] Chang JH, Tassiulas L. Maximum lifetime routing in wireless sensor networks. IEEE/ACM Trans. on Networking, 2004,12(4): 609-619.
[73] M. Lu, J. Wu, M. Cardei and M. Li. Energy-efficient connected coverage of discrete targets in wireless sensor netorks. IEEE International Conference on Volume , Issue ,19-21 June 2006 Page(s): 94-101
[74] Kar K, Banerjee S. Node placement for connected coverage in sensor networks. In: Crowcroft J, ed. Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. Sophia-Antipolis: IEEE Press, 2003. 50-52.
[75] S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In: IEEE International Conference on Communications,Helsinki, Finland June 2001.
[76] D. Tian and N. D. Georganas. A coverage-preserving node scheduling scheme for large wireless sensor network, in Proceeding of 1 st ACM Workshop on Wireless Sensor Networks and Applications (WSNA 02), Atlanta, Geogia, 2002.
[77] Ye F, Zhong G, Lu S, Zhang L. Gradient broadcast: A Robust Data Delivery Protocol for Large Scale Sensor Networks. ACM Wireless Networks, 2005, ll(3):285-298.
[78] M. Cardei, J. Wu, M. Lu, and M. O. Pervaiz. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. Proc. of IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob) (2005)
[79] F. Dai and J. Wu. On constructing k-connected k-dominating set in wireless networks. Proc. of IPDPS (2005)
[80] Abrams Z, Goel A, Plotkin S. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. 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
[81] K. Chakrabarty, S. S. Iyengar, H. Qi, and E. Cho. Grid coverage for surveillance and target location in distributed sensor networks. IEEE Trans. on Comput, 51(12)(2002): 1448-1453
[82] M. Cardei, D.Z. Du. Improving wireless sensor network lifetime through power aware organization.ACM Wireless Networks(2005),11(3)
[83]Cardei M,Thai MT,Li Y,Wu W.Energy-efficient target coverage in wireless sensor networks.In:Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM),Vol.3(2005) 1976-1984
[84]Steuer,R.E.Multiple criteria optimization:Theory,computation,and application.New York:Wiley(1986)
[85]K.Deb,S.Agrawal,A.Pratap,and T.Meyarivan:A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization:NSGA-Ⅱ.In:Proceedings of Parallel Problem Solving from Nature -PPSN Ⅵ.Springer(2000) 849-858
[86]Kalyanmoy Deb and R.B.Agarwal.Simulated Binary Crossover for Continuous Search Space.Complex Systems(1995)(9)115-148
[87]Bulusu N,Heidemann J,Estrin D.GPS-Less low cost outdoor localization for very small devices.IEEE Personal Communications Magazine,2000.7(5):28-34.
[88]He H,Huang C,Blum BM,Stankovic JA,Abdelzaher TF.Range-Free localization schemes in large scale sensor networks.In:Johnson DB,ed.Proc.of the ACM MobiCom 2003.San Diego:ACM Press,2003.81-95.
[89]Romer K,Zurich E.The lighthouse location system for smart dust.In:Siewiorek D,ed.Proc.of the 1st Int'l Conf.on Mobile Systems,Applications,and Services.San Francisco:ACM Press,2004.15-30.
[90]S.Singh and C.Raghavendra.PAMAS:Power Aware Multi-Access protocol with Signalling for Ad Hoc Networks.ACM Computer Communication Review,vol.28,no.3,pp.5-26,July 1998.
[91]K.Sohrabi,J.Gao,V.Ailawadhi,and G.J.Pottie.Protocols for Self-Organization of a Wireless Sensor Network.IEEE Personal Comm.Mag.,vol.7,no.5,Oct.2000.
[92]Z.Haas and S.Tabrizi.On Some Challenges and Design Choices in Ad-Hoc Communications.In:IEEE MILCOM'98,October 1998.
[93]W.Ye,J.Heidenmann,and D.Estrin.An Energy-Efficient MAC Protocol for Wireless Sensor Networks.In:Proceedings of IEEE INFOCOM,New York,NY,June 2002.
[94]V.Kawadia and P.R.Kumar.Power Control and Clustering in Ad Hoc Networks.In:Proceedings of IEEE INFOCOM,April 2003.
[95]S.Narayanaswamy,V.Kawadia,R.S.Sreenivas,and P.R.Kumar.Power Control in Ad-Hoc Networks:Theory,Architecture,Algorithm and Implementation of the COMPOWprotocol.In:Proceedings of European Wireless 2002.Next Generation Wireless Networks:Technologies,Protocols,Services and Applications,February 2002,pp.156-162.
[96]C.Intanagonwiwat,R.Govindan,and D.Estrin.Directed Diffusion:A Scalable and Robust Communication Paradigm for Sensor Networks.In:Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), 2000.
[97] J. Kulik, W. R. Heinzelman, and H. Balakrishnan. Negotiation-Based Protocols for Disseminating Information in Wireless Sensor Networks. ACM Wireless Networks, vol. 8, no. 2-3, pp. 169-185,2002.
[98] J.-H. Chang and L. Tassiulas.Energy conserving routing in wireless ad-hoc networks. In: Proceedings of IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000.
[99] W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. An Application-Specific Protocol Architecture for Wireless Microsensor Networks. IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660-670, October 2002.
[100] A. Cerpa and D. Estrin. ASCENT: Adaptive Self-Configuring Sensor Networks Topologies. In: Proceedings of IEEE INFOCOM, New York, NY, June 2002.
[101] Y. Xu, J. Heidemann, and D. Estrin. Geography-Informed Energy Conservation for Ad Hoc Routing. In: Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Rome, Italy, July 2001, pp. 70-84.
[102] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris. Span: an Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks. ACM Wireless Networks, vol. 8, no. 5, September 2002.
[103] J.Wang, Ning Zhong.Efficient point coverage in wireless sensor networks[J]. Journal of Combinatorial Optimization, 2006,Volume 11, Number 3, 291-304.
[104] Cardei M, Thai MT, Li Y. Energy-Efficient target coverage in wireless sensor networks. In: Raton B, ed. Proc. of the IEEE INFOCOM. Miami: IEEE Computer Society, 2005. 1976-1984.
[105] Cheng M X,Ruan L,Wu W.Achieving Minimum Coverage Breach Under Bandwidth Constraints in Wireless Sensor Networks[C].Proc of the 24th Conf of the IEEE Communications Society,2005.
[106] Chen Wang, My T. Thai, et al.. Minimum Coverage Breach and Maximum Network Lifetime in Wireless Sensor Networks, IEEE GLOBECOM 2007, Washington, DC, November 26-30,2007.
[107] Deng J, Han YS, Heinzelman WB, Varshney PK. Scheduling sleeping nodes in high density networks. ACM/Kluwer Mobile Networks and Applications (MONET), 2005, 10(6): 825-835.
[108] W. Heinzelman, A. Chandrakasan and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In: Proc. of the 33rd Annual Hawaii International Conference on System Sciences (HICSS), Maui, HI, Jan. 2000, pp. 3005-3014.
[109] W. Heinzelman, A. Chandrakasan and H. Balakrishnan. An application-specific protocol architecture for wireless microsensor networks [J] . IEEE Transactions on Wireless Communications, 2002, l(4):660-670.
[110] Younis 0, fahmy S. HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Trans. on Mobile Computing, 2004, 3(4): 660-669.
[111] Gupta I, Riordan D, Sampalli S. Cluster-Head election using fuzzy logic for wireless sensor networks. In: Proc. of the 3rd Annual Communication Networks and Services Research Conf. Halifax: IEEE Computer Society, 2005. 255-260.
[112] Manjeshwar A, Grawal DP. TEEN: A protocol for enhanced efficiency in wireless sensor networks. In: Proc. of the 15th Parallel and Distributed Processing Symp. San Francisco: IEEE Computer Society, 2001. 2009-2015.
[113] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences, 2000, pp. 1-10.
[114] Kubisch M, Karl H, Wolisz A, Zhong LC, Rabaey J. Distributed algorithms for transmission power control in wireless sensor networks. In: Taga T, ed. Proc. of the IEEE Wireless Communications and Networking Conf. (WCNC). New Orleans: IEEE Press, 2003. 558-563.
[115] Qayyum A, Viennot L, Laouiti L. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. Technical Report, 3898, INRIA-Rapport de Recherche, 2000.
[116] Wan PJ, Alzoubi KM, Frieder O. Distributed construction of connected dominating set in wireless ad hoc networks. In: Kermani P, ed. Proc. of the IEEE Infocom. New York: IEEE Press, 2002. 1597-1604.
[117] Das B, Sivakumar R, Bhargavan V. Routing in ad hoc networks using a spine. In: Makki K, ed. Proc. of the Int'l Conf. on Computer Communications and Networks (ICCCN). Los Alamitos: IEEE Press, 1997. 34-41.
[118] Alzoubi KM, Wan PJ, Frieder O. Message-Optimal connected dominating sets in mobile ad hoc networks. In: Hubaux JP, ed. Proc. of the ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc). New York: ACM Press, 2002. 157-164.
[119] Chen Y, Liestman A. Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks. In: Hubaux JP, ed. Proc. of the ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc). New York: ACM Press, 2002. 165-172.
[120] Wu J, Dai F. Broadcasting in ad hoc networks based on self-pruning. In: Bauer F, ed. Proc. of the IEEE Infocom. San Fransisco: IEEE Press, 2003. 2240-2250.
[121] Dai F, Wu J. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans, on Parallel and Distributed Systems, 2004,15(10):908-920.
[122] Zhang H, Hou JC. Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc & Wireless Networks, 2005,1(1): 89-124.
[123] Wang X, Xing G, Zhang Y, Lu C, Pless R, Gill C. Integrated coverage and connectivity configuration in wireless sensor networks. In: Akyildiz IF, Estion D, eds. Proc. of the ACM Int'l Conf. on Embedded Networked Sensor Systems (SenSys). New York: ACM Press, 2003. 28-39.
[124] Chen B, Jamieson K, Balakrishnan H, Morris R. SPAN: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. In: Rose C, ed. Proc. of the 7th ACM Int'l Conf. on Mobile Computing and Networking (MobiCom). New York: ACM Press, 2001. 85-96.
[125] Carle J, Gallais A, Simplot-Ryl D. Preserving area coverage in wireless sensor networks by using surface coverage relay dominating sets. In: Ammar R, Saracco R, eds. Proc. of the 10th IEEE Symp. on Computers and Communications (ISCC). Cartagena: IEEE Press, 2005. 347-352.
[126] Gupta H, Das SR, Gu Q. Connected sensor cover: Self-Organization of sensor networks for efficient query execution. In: Gerla M, ed. Proc. of the ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc). New York: ACM Press, 2003. 189-200.
[127] Zhou Z, Das SR, Gupta H. Fault tolerant connected sensor cover with variable sensing and transmission ranges. In: Garcia-Luna-Aceves J, ed. Proc. of the 2nd Annual IEEE Communications Society Conf. on Sensor and Ad Hoc Communications and Networks (SECON). Santa Clara: IEEE Press, 2005. 594-604.
[128] Narayanswamy S, Kawadia V, Sreenivas RS, Kumar PR. Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol. In: Lenzini L, ed. Proc. of the European Wireless Conf.—Next Generation Wireless Networks: Technologies, Protocols, Services and Applications. Pisa: IEEE Press, 2002. 156-162.
[129] Ramanathan R, Rosales-Hain R. Topology control of multihop wireless networks using transmit power adjustments. In: Sidi M, ed. Proc. of the IEEE INFOCOM. Tel Aviv: IEEE Press, 2000. 404-413.
[130] Li N, Hou JC. Toplogy control in heterogeneous wireless networks: Problems and solutions. In: Li VOK, ed. Proc. of the IEEE INFOCOM. Hong Kong: IEEE Press, 2004. 232-243.
[131] Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, eds. Proc. of the Complexity of Computer Computations. New York: Plenum Press, 1972. 85-103.
[132] Garey MR, Graham RL, Johnson DS. The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics, 1977, 32(4):835-859.
[133] Garey M R and Johnson D S. Computers and intractability: A guide to New York: Freeman, 1979.
[134] Boyce W M. An improved program for the full Steiner tree problem. ACM Transactions on Mathematical Software,1997,3:359-385.
[135]Gilbert E N and Pollak H O.Steiner minimal trees.SIAM Journal on Applied Mathematics,1996,16:1-29.
[136]P.Berman and V.Ramaiyer.Improved approximations for the Steiner tree problem.In:Proceedings of the Third Symposium on Discrete Algorithms,pages 325-334,1992.
[137]P.Berman and V.Ramaiyer.Improved approximations for the Steiner tree problem.Journal of Algorithms,17:381-408,1994.
[138]S.Ganeriwal,R.Kumar,and M.Srivastava.Timing-Sync Protocol for Sensor Networks.In:Proceedings of the 1st International Conference on Embedded Networked Sensor Systems,pp.138-149,November 2003.
[139]M.Maroti,B.Kusy,G.Simon,and A.Ledeczi.The Flooding Time Synchronization Protocol.In:Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems,pp.39-49,November 2004.]
[140]J.V.Greunen and J.Rabaey.Lightweight Time Synchronization for Sensor Networks.In:Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications,pp.11-19,September 2003.
[141]Q.Li and D.Rus,Global Clock Synchronization in Sensor Networks,INFOCOM'04,March 2004.
[142]G.Robins and A.Zelikovsky.Improved Steiner tree approximation in graphs.In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms,pages 770-779,2000.
[2] Bettstetter C, Hartmann C. Connectivity of wireless multihop networks in a shadow fading environment [C] .The 8th International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems. San Diego: MSWiM, 2003:28-32.
[3] M. Roussopoulos, M. Baker. Controlled Update Propagation in Peer-to-Peer Networks. Proceedings of USENIX Annual Technical Conference. 2003.
[4] S.H.L.Liang, V.Tao, A.Croitoru. The Design and Prototype of a Distributed Geospatial Infrastructure for Smart Sensor Web. Proceedings of the 6th AGILE Conference on Geographic Information Science.2003
[5] A. Cerpa, J. Elson, M. Hamilton, and 1. Zhao, Habitat Monitoring: Application Driver for Wireless Communications Technology. First ACM SIGCOMM Workshop on Data Communication in Latin America and the Caribbean, April 2001.
[6] J.R. Polastre, D. Culler. Design and Implementation of Wireless Sensor Networks for Habitat Monitoring, University of California at Berkeley, 2003.
[7] P.Bonnet, J.Gehrke, P.Seshadri. Querying the Physical World. IEEE Personal Communications, 2000, 7.
[8] Rabaey J M, Ammer M J, da Silva J L Jr. Patel D, Roundy S. PicoRadio supports ad hoc ultra-low power wireless networking[J]. IEEE Computer Magazine 2000:42-48
[9] D. Estrin, R. Govindan, J. Heidemann, et al.. Next century challenges :scalable coordination in sensor networks. ACM MOBICOM, Seattle, WA, August 1999.
[10] N. Bulusu, D. Estrin, L. Girod, J. Heidemann, Scalable coordination for wireless sensor networks: self-configuring localization systems, International Symposium on Communication Theory and Applications (ISCTA 2001), Ambleside, UK, July 2001.
[11] P. Bauer, M. Sichitiu, R. Istepanian and K. Premaratne. The Mobile Patient: Wireless Distributed Sensor Networks for patient monitoring and Care. In Proc. IEEE EMBS International Conference on Information Technology Applications in Biomedicine, Arlington, pp. 17-21,2000.
[12] http://www.agingtech.org.
[13] http://www.rfidjournal.com/article/view/3625/.
[14] I.F.Akyildiz,W.Su, Y.Sankarasubramaniam, E.Cayirci. A Survey on Sensor Networks. IEEE Communications Magazine, 2002,40(8): 102-114.
[15] Conrad J G.CEC:Sensor Netting with Integrated Fire Control[J].Johns Hopkins APL Technical Digest,2002,23(2):2-3.
[16]http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/MICA.pdf
[17]http://bwrc.eecs.berkeley.edu
[18]UCLA.Medusa MK-2 Programming Resource[EB/OL].http://nesl.ee.ucla.edu/projects/ahlos/mk2/,2003-10.
[19]http://www.intel.com/research/exploratory/motes.htm.
[20]UC Berkeley.TinyOS:An Open-source Operating System Designed for Wireless Embedded Sensor Networks[EB/OL].http://www.tinyos.net/,2003-10.
[21]http://mantis.cs.colorado.edu/index.php/tiki-index.php.
[22]http://nesl.ee.ucla.edu/proj cots/sos/.
[23]http://www.cast.cse.ohio-state.edu/exscal/.
[24]http://projects.cerias.urdue.edu/esp/.
[25]http://www.eng.yale.edu/enalab
[26]http://www.eecs.harvard.edu/～mdw/proj/codeblue/.
[27]http://wings.cs.sunysb.edu.
[28]http://www robotics.usc.edu/embedded/.
[29]http://www.isi.edu/scadds/.
[30]http://www.ece.gatech.edu/researchAabs/bwn/index.html.
[31]http://www.zurich.ibm.com/sys/communication/sensors.html.
[32]http://www.intel.com/research/exploratory/wireless_sensors.htm.
[33]http://research.microsoft.com/nec/.
[34]P.Berman,G.Calinescu,C.Shah and A.Zelikovsky.Power Efficient Monitoring Management in Sensor Networks,Proceedings of WCNC'04,March 2004.
[35]S.Slijepcevic and M.Potkonjak.Power Efficient Organization of Wireless Sensor Networks,IEEE International Conference on Communications,June 2001.
[36]J.Jiang and W.Dou.A Coverage-Preserving Density Control Algorithm for Wireless Sensor Networks.In International Conference on AD-HOC Networks &Wireless(ADHOC-NOW),pp.42-55,July 2004.
[37]Dhillon S S,Chakrabarty K,Iyengar S S.Sensor placement for grid coverage under imprecise detections[C].Proceeding of International Conference on Information Fusion,2002:158 -1587.
[38]Dhillon S S,Chakrabarty K.Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks[C].Proceeding of IEEE WCNC 2003.New Orleans,Louisiana,USA,2003:1609-1614.
[39]Zou Y,Chakrabarty K.Sensor deployment and target localization in distributed sensor networks.ACM Trans.on Embedded Computing Systems,2004,3(1):61-91.
[40]J.Lu,et al..Coverage-aware Self-scheduling in Sensor Networks.In Proc.of CCW 2003,Oct.2003,pp.117-123.
[41]Nadeem Ahmed,Salil S.Kanhere,Sanjay Jha.Probabilistic Coverage in Wireless Sensor Networks.Fifth International IEEE Workshop on Wireless Local Networks(WLN 2005), pp. 672-681,2005.
[42] T. S. Rappaport, Wireless communications,Principles and Practice, Prentice Hall, New Jersey, 1996.
[43] H.Ma,Y.Liu. On coverage problems of directional sensor networks.Proceedings of the International Conference on Mobile Ad-Hoc and Sensor Networks.2005.
[44] Slijepcevic S, Potkonjak M. Power efficient organization of wireless sensor networks. In: Glisic S, ed. Proc. of the IEEE Int'l Conf. on Communications (ICC). Helsinki: IEEE Press, 2001, 472-476.
[45] P. Berman, G. Calinescu,C.Shah, et.al.. Power Efficient Monitoring Management in wireless sensor networks. Proceedings of IEEE Wireless Communication and Networking Conference(WCNC04), Allanta, USA, 2004.
[46] Abrams Z, Goel A, Plotkin S. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. 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.
[47] F. Ye, G. Zhong, S. Lu, and L. Zhang, Energy. Efficient Robust Sensing Coverage in Large Sensor Networks. Technical Report UCLA (2002).
[48] Ye F, Zhong G, Lu S, Zhang L. PEAS: A robust energy conserving protocol for long-lived sensor networks. In: Stankovic J, Zhao W, eds. Proc. of the Int'l Conf. on Distributed Computing Systems (ICDCS). Providence: IEEE Press, 2003. 28-37.
[49] Tian D, Georganas N. A coverage-preserving node scheduling scheme for large wireless sensor networks. In: Raghavendra CS, Sivalingam K, eds. Proc. of the 1st Int'l Workshop on Wireless Sensor Networks and Applications (WSNA 2002). Atlanta: ACM Press, 2002, 32-41.
[50] Tian, D., and Georganas, N. D. A node scheduling scheme for energy conservation in large sensor networks. Journal of Wireless Communications and Mobile Computing 3 (2003), 271(290. Special issue on Algorithmic, Geometric, Graph, Combinatorial, and Vector Aspects of Wireless Networks and Mobile Computing.
[51] Yah T, He T, Stankovic J. Differentiated surveillance service for sensor networks. 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.
[52] Howard A,Mataric M J, Sukhatme G S. Mobile Sensor Network Deployment using Potential Fields: a distributed, Scalable Solution to the Area Coverage Problem[C]. In: Proceeding of International Conference on Distributed Autonomous Robotic Systems,2002:299-308
[53] Zou Y, Chakrabarty K.Sensor Deployment and Target Localization based on Virtual Forces[C]. In: Proceeding of IEEE INFOCOM, 2003:1293-1303
[54] Heo N, Varshney P K. An Intelligent Deployment and Clustering Algorithm for a Distributed Mobile Sensor Network[C]. In Proceeding of IEEE International Conference on Systems, Man and Cybernetics, 2003: 4576- 4581
[55] G.Wang, G.Cao, T.La Porta. A Bidding Protocol for Deploying Mobile Sensors. Proceedings of the 11th IEEE International Conference on Network Protocols(ICNP'03),2003
[56] G.Wang, G.Cao, T.La Porta, Movement-Assisted Sensor Deployment, Proceedings of IEEE INFOCOM'04, HongKong, 2004
[57] G.Wang, G.Cao, T.La Porta, Proxy-based Sensor Deployment for Mobile Sensor Networks, Proceedings of the 1 st IEEE International Conference on Mobile Ad-hoc and Sensor Systems(MASS'04),Fort Lauderdale, Florida, 2004
[58] G.Wang, G.Cao, T.Porta, W.Zhang. Sensor Relocation in Mobile Sensor Networks. Proceedings of IEEE INFOCOM'05, Miami, Florida,2005
[59] J.Wang, D.Du, E.Kusmierek. Energy Efficient Oragnization of Mobile Sensor Networks, Proceedings of the 2004 International Conference on Parallel Processing Workshops(ICPPW'04),Montreal,Quebec,Canada,2004
[60] Basagni S. Distributed Clustering for Adoc hoc Networks[C]. In: Proceeding of IEEE International symposium on Parallel Architectures, Algorithms, and Networks, 1999:310-315
[61] B.Liu,P.Brass,O.Dousse,P.Nain,D.Towsley.Mobility Improves Coverage of Sensor Network,Proceedings of ACM Mobihoc'05, Urbana-Champaign,IL,2005
[62] Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava MB. Coverage problems in wireless ad-hoc sensor network. In: Sengupta B, ed. Proc. of the IEEE INFOCOM. Anchorage: IEEE Press, 2001. 1380-1387.
[63] Xiang-Yang Li, Peng-Jun Wan, Ophir Frieder. Coverage in Wireless Ad-Hoc Sensor Networks. Proc. IEEE Trans. Computers, 2003, vol.52(6): 753-763.
[64] Meguerdichian S, Koushanfar F, Qu G, Potkonjak M. Exposure in wireless ad-hoc sensor networks. In: Rose C, ed. Proc. of the ACM Int'l Conf. on Mobile Computing and Networking (MobiCom). New York: ACM Press, 2001. 139-150.
[65] Cheng M X,Ruan L,Wu W.Achieving Minimum Coverage Breach Under Bandwidth Constraints in Wireless Sensor Networks[C].Proc of the 24th Conf of the IEEE Communications Society, 2005.
[66] Adlakha S, Srivastava M. Critical density thresholds for coverage in wireless sensor networks. In: Tachikawa K, ed. Proc. of the IEEE Wireless Communications and Networking (WCNC). New Orleans: IEEE Press, 2003. 1615-1620.
[67] B. Liu, D. Towaley. On the Coverage and Detectability of Large-scale. Wireless Sensor Networks. Proc. of the Modeling and Optimization in Mobile, Ad hoc and Wireless Networks, INRIA Sophia-Antipolis, France, 2003
[68] R. Meester and R. Roy. Continuum percolation, Cambridge University Press, Cambridge, 1996.21.
[69] Liu B, Towsley D. A study of the coverage of large-scale sensor networks. In: Proc. of the ACM Mobile Ad-Hoc and Sensor Systems (MASS'04). New York: ACM Press, 2004. 475-483
[70] Cardei M, Du DZ. Improving wireless sensor network lifetime through power aware organization. Wireless Networks, 2005,11(3): 333-340.
[71] Cardei M, Thai MT, Li Y. Energy-Efficient target coverage in wireless sensor networks. In: Raton B, ed. Proc. of the IEEE INFOCOM. Miami: IEEE Computer Society, 2005. 1976-1984.
[72] Chang JH, Tassiulas L. Maximum lifetime routing in wireless sensor networks. IEEE/ACM Trans. on Networking, 2004,12(4): 609-619.
[73] M. Lu, J. Wu, M. Cardei and M. Li. Energy-efficient connected coverage of discrete targets in wireless sensor netorks. IEEE International Conference on Volume , Issue ,19-21 June 2006 Page(s): 94-101
[74] Kar K, Banerjee S. Node placement for connected coverage in sensor networks. In: Crowcroft J, ed. Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. Sophia-Antipolis: IEEE Press, 2003. 50-52.
[75] S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In: IEEE International Conference on Communications,Helsinki, Finland June 2001.
[76] D. Tian and N. D. Georganas. A coverage-preserving node scheduling scheme for large wireless sensor network, in Proceeding of 1 st ACM Workshop on Wireless Sensor Networks and Applications (WSNA 02), Atlanta, Geogia, 2002.
[77] Ye F, Zhong G, Lu S, Zhang L. Gradient broadcast: A Robust Data Delivery Protocol for Large Scale Sensor Networks. ACM Wireless Networks, 2005, ll(3):285-298.
[78] M. Cardei, J. Wu, M. Lu, and M. O. Pervaiz. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. Proc. of IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob) (2005)
[79] F. Dai and J. Wu. On constructing k-connected k-dominating set in wireless networks. Proc. of IPDPS (2005)
[80] Abrams Z, Goel A, Plotkin S. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. 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
[81] K. Chakrabarty, S. S. Iyengar, H. Qi, and E. Cho. Grid coverage for surveillance and target location in distributed sensor networks. IEEE Trans. on Comput, 51(12)(2002): 1448-1453
[82] M. Cardei, D.Z. Du. Improving wireless sensor network lifetime through power aware organization.ACM Wireless Networks(2005),11(3)
[83]Cardei M,Thai MT,Li Y,Wu W.Energy-efficient target coverage in wireless sensor networks.In:Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM),Vol.3(2005) 1976-1984
[84]Steuer,R.E.Multiple criteria optimization:Theory,computation,and application.New York:Wiley(1986)
[85]K.Deb,S.Agrawal,A.Pratap,and T.Meyarivan:A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization:NSGA-Ⅱ.In:Proceedings of Parallel Problem Solving from Nature -PPSN Ⅵ.Springer(2000) 849-858
[86]Kalyanmoy Deb and R.B.Agarwal.Simulated Binary Crossover for Continuous Search Space.Complex Systems(1995)(9)115-148
[87]Bulusu N,Heidemann J,Estrin D.GPS-Less low cost outdoor localization for very small devices.IEEE Personal Communications Magazine,2000.7(5):28-34.
[88]He H,Huang C,Blum BM,Stankovic JA,Abdelzaher TF.Range-Free localization schemes in large scale sensor networks.In:Johnson DB,ed.Proc.of the ACM MobiCom 2003.San Diego:ACM Press,2003.81-95.
[89]Romer K,Zurich E.The lighthouse location system for smart dust.In:Siewiorek D,ed.Proc.of the 1st Int'l Conf.on Mobile Systems,Applications,and Services.San Francisco:ACM Press,2004.15-30.
[90]S.Singh and C.Raghavendra.PAMAS:Power Aware Multi-Access protocol with Signalling for Ad Hoc Networks.ACM Computer Communication Review,vol.28,no.3,pp.5-26,July 1998.
[91]K.Sohrabi,J.Gao,V.Ailawadhi,and G.J.Pottie.Protocols for Self-Organization of a Wireless Sensor Network.IEEE Personal Comm.Mag.,vol.7,no.5,Oct.2000.
[92]Z.Haas and S.Tabrizi.On Some Challenges and Design Choices in Ad-Hoc Communications.In:IEEE MILCOM'98,October 1998.
[93]W.Ye,J.Heidenmann,and D.Estrin.An Energy-Efficient MAC Protocol for Wireless Sensor Networks.In:Proceedings of IEEE INFOCOM,New York,NY,June 2002.
[94]V.Kawadia and P.R.Kumar.Power Control and Clustering in Ad Hoc Networks.In:Proceedings of IEEE INFOCOM,April 2003.
[95]S.Narayanaswamy,V.Kawadia,R.S.Sreenivas,and P.R.Kumar.Power Control in Ad-Hoc Networks:Theory,Architecture,Algorithm and Implementation of the COMPOWprotocol.In:Proceedings of European Wireless 2002.Next Generation Wireless Networks:Technologies,Protocols,Services and Applications,February 2002,pp.156-162.
[96]C.Intanagonwiwat,R.Govindan,and D.Estrin.Directed Diffusion:A Scalable and Robust Communication Paradigm for Sensor Networks.In:Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), 2000.
[97] J. Kulik, W. R. Heinzelman, and H. Balakrishnan. Negotiation-Based Protocols for Disseminating Information in Wireless Sensor Networks. ACM Wireless Networks, vol. 8, no. 2-3, pp. 169-185,2002.
[98] J.-H. Chang and L. Tassiulas.Energy conserving routing in wireless ad-hoc networks. In: Proceedings of IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000.
[99] W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. An Application-Specific Protocol Architecture for Wireless Microsensor Networks. IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660-670, October 2002.
[100] A. Cerpa and D. Estrin. ASCENT: Adaptive Self-Configuring Sensor Networks Topologies. In: Proceedings of IEEE INFOCOM, New York, NY, June 2002.
[101] Y. Xu, J. Heidemann, and D. Estrin. Geography-Informed Energy Conservation for Ad Hoc Routing. In: Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Rome, Italy, July 2001, pp. 70-84.
[102] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris. Span: an Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks. ACM Wireless Networks, vol. 8, no. 5, September 2002.
[103] J.Wang, Ning Zhong.Efficient point coverage in wireless sensor networks[J]. Journal of Combinatorial Optimization, 2006,Volume 11, Number 3, 291-304.
[104] Cardei M, Thai MT, Li Y. Energy-Efficient target coverage in wireless sensor networks. In: Raton B, ed. Proc. of the IEEE INFOCOM. Miami: IEEE Computer Society, 2005. 1976-1984.
[105] Cheng M X,Ruan L,Wu W.Achieving Minimum Coverage Breach Under Bandwidth Constraints in Wireless Sensor Networks[C].Proc of the 24th Conf of the IEEE Communications Society,2005.
[106] Chen Wang, My T. Thai, et al.. Minimum Coverage Breach and Maximum Network Lifetime in Wireless Sensor Networks, IEEE GLOBECOM 2007, Washington, DC, November 26-30,2007.
[107] Deng J, Han YS, Heinzelman WB, Varshney PK. Scheduling sleeping nodes in high density networks. ACM/Kluwer Mobile Networks and Applications (MONET), 2005, 10(6): 825-835.
[108] W. Heinzelman, A. Chandrakasan and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In: Proc. of the 33rd Annual Hawaii International Conference on System Sciences (HICSS), Maui, HI, Jan. 2000, pp. 3005-3014.
[109] W. Heinzelman, A. Chandrakasan and H. Balakrishnan. An application-specific protocol architecture for wireless microsensor networks [J] . IEEE Transactions on Wireless Communications, 2002, l(4):660-670.
[110] Younis 0, fahmy S. HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Trans. on Mobile Computing, 2004, 3(4): 660-669.
[111] Gupta I, Riordan D, Sampalli S. Cluster-Head election using fuzzy logic for wireless sensor networks. In: Proc. of the 3rd Annual Communication Networks and Services Research Conf. Halifax: IEEE Computer Society, 2005. 255-260.
[112] Manjeshwar A, Grawal DP. TEEN: A protocol for enhanced efficiency in wireless sensor networks. In: Proc. of the 15th Parallel and Distributed Processing Symp. San Francisco: IEEE Computer Society, 2001. 2009-2015.
[113] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences, 2000, pp. 1-10.
[114] Kubisch M, Karl H, Wolisz A, Zhong LC, Rabaey J. Distributed algorithms for transmission power control in wireless sensor networks. In: Taga T, ed. Proc. of the IEEE Wireless Communications and Networking Conf. (WCNC). New Orleans: IEEE Press, 2003. 558-563.
[115] Qayyum A, Viennot L, Laouiti L. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. Technical Report, 3898, INRIA-Rapport de Recherche, 2000.
[116] Wan PJ, Alzoubi KM, Frieder O. Distributed construction of connected dominating set in wireless ad hoc networks. In: Kermani P, ed. Proc. of the IEEE Infocom. New York: IEEE Press, 2002. 1597-1604.
[117] Das B, Sivakumar R, Bhargavan V. Routing in ad hoc networks using a spine. In: Makki K, ed. Proc. of the Int'l Conf. on Computer Communications and Networks (ICCCN). Los Alamitos: IEEE Press, 1997. 34-41.
[118] Alzoubi KM, Wan PJ, Frieder O. Message-Optimal connected dominating sets in mobile ad hoc networks. In: Hubaux JP, ed. Proc. of the ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc). New York: ACM Press, 2002. 157-164.
[119] Chen Y, Liestman A. Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks. In: Hubaux JP, ed. Proc. of the ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc). New York: ACM Press, 2002. 165-172.
[120] Wu J, Dai F. Broadcasting in ad hoc networks based on self-pruning. In: Bauer F, ed. Proc. of the IEEE Infocom. San Fransisco: IEEE Press, 2003. 2240-2250.
[121] Dai F, Wu J. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans, on Parallel and Distributed Systems, 2004,15(10):908-920.
[122] Zhang H, Hou JC. Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc & Wireless Networks, 2005,1(1): 89-124.
[123] Wang X, Xing G, Zhang Y, Lu C, Pless R, Gill C. Integrated coverage and connectivity configuration in wireless sensor networks. In: Akyildiz IF, Estion D, eds. Proc. of the ACM Int'l Conf. on Embedded Networked Sensor Systems (SenSys). New York: ACM Press, 2003. 28-39.
[124] Chen B, Jamieson K, Balakrishnan H, Morris R. SPAN: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. In: Rose C, ed. Proc. of the 7th ACM Int'l Conf. on Mobile Computing and Networking (MobiCom). New York: ACM Press, 2001. 85-96.
[125] Carle J, Gallais A, Simplot-Ryl D. Preserving area coverage in wireless sensor networks by using surface coverage relay dominating sets. In: Ammar R, Saracco R, eds. Proc. of the 10th IEEE Symp. on Computers and Communications (ISCC). Cartagena: IEEE Press, 2005. 347-352.
[126] Gupta H, Das SR, Gu Q. Connected sensor cover: Self-Organization of sensor networks for efficient query execution. In: Gerla M, ed. Proc. of the ACM Int'l Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc). New York: ACM Press, 2003. 189-200.
[127] Zhou Z, Das SR, Gupta H. Fault tolerant connected sensor cover with variable sensing and transmission ranges. In: Garcia-Luna-Aceves J, ed. Proc. of the 2nd Annual IEEE Communications Society Conf. on Sensor and Ad Hoc Communications and Networks (SECON). Santa Clara: IEEE Press, 2005. 594-604.
[128] Narayanswamy S, Kawadia V, Sreenivas RS, Kumar PR. Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol. In: Lenzini L, ed. Proc. of the European Wireless Conf.—Next Generation Wireless Networks: Technologies, Protocols, Services and Applications. Pisa: IEEE Press, 2002. 156-162.
[129] Ramanathan R, Rosales-Hain R. Topology control of multihop wireless networks using transmit power adjustments. In: Sidi M, ed. Proc. of the IEEE INFOCOM. Tel Aviv: IEEE Press, 2000. 404-413.
[130] Li N, Hou JC. Toplogy control in heterogeneous wireless networks: Problems and solutions. In: Li VOK, ed. Proc. of the IEEE INFOCOM. Hong Kong: IEEE Press, 2004. 232-243.
[131] Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, eds. Proc. of the Complexity of Computer Computations. New York: Plenum Press, 1972. 85-103.
[132] Garey MR, Graham RL, Johnson DS. The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics, 1977, 32(4):835-859.
[133] Garey M R and Johnson D S. Computers and intractability: A guide to New York: Freeman, 1979.
[134] Boyce W M. An improved program for the full Steiner tree problem. ACM Transactions on Mathematical Software,1997,3:359-385.
[135]Gilbert E N and Pollak H O.Steiner minimal trees.SIAM Journal on Applied Mathematics,1996,16:1-29.
[136]P.Berman and V.Ramaiyer.Improved approximations for the Steiner tree problem.In:Proceedings of the Third Symposium on Discrete Algorithms,pages 325-334,1992.
[137]P.Berman and V.Ramaiyer.Improved approximations for the Steiner tree problem.Journal of Algorithms,17:381-408,1994.
[138]S.Ganeriwal,R.Kumar,and M.Srivastava.Timing-Sync Protocol for Sensor Networks.In:Proceedings of the 1st International Conference on Embedded Networked Sensor Systems,pp.138-149,November 2003.
[139]M.Maroti,B.Kusy,G.Simon,and A.Ledeczi.The Flooding Time Synchronization Protocol.In:Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems,pp.39-49,November 2004.]
[140]J.V.Greunen and J.Rabaey.Lightweight Time Synchronization for Sensor Networks.In:Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications,pp.11-19,September 2003.
[141]Q.Li and D.Rus,Global Clock Synchronization in Sensor Networks,INFOCOM'04,March 2004.
[142]G.Robins and A.Zelikovsky.Improved Steiner tree approximation in graphs.In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms,pages 770-779,2000.