无线传感器网络中面向数据采集的支配集算法与策略研究
|
摘要
无线传感器网络是由大量具有感知、数据处理和通信能力的传感器节点组成的网络,并且通过传感器节点之间的协作,实现对各种现象的监测。由于具有低功耗、低成本、智能化、分布式、自组织等特点,无线传感器网络在军事、环保、医疗、商业、灾害预测及救援等领域有着广阔的应用前景。
无线传感器网络是面向数据的网络,其主要任务就是进行数据处理,包括数据的感知、采集、传输、压缩、聚合等等。传感器网络节点通常密集分布在所监测的网络区域中,并且会产生大量的数据,地理位置邻近的节点产生的数据往往具有很大的相关性,这些都给无线传感器网络的数据采集算法设计带来了很大的挑战。
传感器网络节点是能量受限的,在网络中传输大量的数据必然会缩短网络的生命周期。因此,优化网络通信结构和数据冗余缩减都能显著改善网络在时延、能耗、可靠性等方面的性能。
在无线传感器网络中构造虚拟主干是优化网络通信结构的一个重要手段。支配集是在无线网络中构建虚拟主干最常用的技术,很多文献提出采用连通支配集作为无线网络的虚拟主干,并设计了一些有效的算法,但这些算法都是以通用的无线网络为研究背景,因而在构造连通支配集时没有考虑无线传感器网络的特殊性,包括数据采集、冗余缩减等。
本文主要研究适合在无线传感器网络中进行高效数据采集的支配集结构。
树形通信结构很适合在无线传感器网络中进行消息洪泛、数据采集和数据融合,因此本文先对树形的连通支配集进行研究。一般意义上的连通支配集是基于连通网络的,为了将连通支配集的概念应用到稀疏无线传感器网络中,并且在数据采集时考虑数据的相关性,本文还对支配集的概念进行了扩展,提出了虚拟支配集、全虚拟支配集和关联支配集等概念,并根据扩展的支配集概念,设计了一系列在无线传感器网络进行高效数据采集的算法。
首先,提出了一个能量高效的支配树构造算法(EEDTC)来构建一个能在传感器网络中充当虚拟主干的树形的连通支配集。EEDTC算法利用节点的κ跳邻居节点信息,具有很好的可扩展性,选取合适的κ值能实现不同的消息复杂度和时间复杂度要求,同时EEDTC算法具有很好的节能特性和能量均衡特性。在不同的网络数据采集应用背景下,该算法都表现出很好的性能；
其次,为了实现从部分连通的网络中采集数据,结合虚拟支配集的概念,提出了一个基于网格分割的移动单元调度算法(GBMES),调度一个移动单元(ME)周期性地从网络中采集数据。GBMES算法在降低移动单元的行进时延和数据采集时延等方面具有很好的性能,显著降低了由于传感器网络节点的缓存溢出而产生的数据丢失。
然后,为保证移动采集节点MC在稀疏传感器网络中进行高效数据采集,基于Voronoi图提出了两个算法：基于普通Voronoi图的移动采集节点调度算法(VDMCS)和基于加权Voronoi图的能量均衡数据采集算法(MWVDC)。两个算法都是通过迭代的虚拟散点插入过程生成一个全虚拟支配集,在给定的通信半径范围内,这个集合恰好能覆盖所有的传感器节点。在全虚拟支配集的基础上,VDMCS为MC构建一条最短的行进路径,MWVDC算法则对数据采集时延和网络能耗进行综合考虑,为MC构造一条优化的数据采集路径,同时保证整个网络能量消耗的均衡性。
最后,结合关联支配集的概念,设计了一个基于熵评判的关联支配集构造算法(EECDS),该算法首先通过评价随机变量的熵值来判断网络节点间的数据相关性,然后在网络中分布式地构造一个关联图,最后借助关联图的信息构造一个连通关联支配集。EECDS算法能有效地缩减无线传感器网络的数据冗余,同时具有很好的能量均衡特性和可扩展性。
Wireless sensor networks consist of a large number of sensor nodes, which are equipped with sensing, data processing, and communicating components. The sensor nodes collaborate together to monitor various phenomenons. Due to the low-power, low-cost, intelligent, distributed, and self-organized characteristics, wireless sensor networks have shown great potential in many fields, such as, military, environment, health, business, disaster forecast and relief.
Wireless sensor networks are data-oriented, whose main task is data processing, including sensing, data gathering, transmission, compress, aggregation, and so on. Wireless sensor networks are usually densely deployed in a network area, and generate a great deal of data. Moreover, the data sensed by neighboring nodes is high correlated. These all impose great challenges on the design of data gathering algorithms.
Since the sensor nodes are power-constrained, transferring large amounts of data definitely will shorten the lifetime of sensor networks. Therefore, the network performance on energy consumption and stability could be improved through the communication structure optimization or data redundancy removal.
A virtual backbone plays an important role for the communication structure optimization. One of the frequently used techniques for virtual backbone construction is the dominating set. Many literatures proposed to use a connected dominating set as a virtual backbone in wirless networks, and designed various efficient algorithms. But few of them take special properties of sensor networks into consideration, such as data gathering, redundancy removal, etc.
This dissertation focuses on the dominating set problems for efficient data gathering in wireless sensor networks.
Because the tree structure is more appropriate for flooding, data gathering, and data aggregation in wireless sensor networks, this work first investigate the tree-based connected dominating set problem. The ordinary connected dominating set problems are based on connected networks. To extend the concept of connected dominating set into sparse sensor networks, and considering the data correlation as well, we propose the concepts of the virtual dominating set, the completedly virtual dominating set, and the correlation dominating set. Several efficient data gathering algorithms based on the extended dominating set concept are presented in this dissertation.
Firstly, the energy-efficient dominating tree construction (EEDTC) algorithm is proposed to construct a dominating tree as a virtual backbone in wireless sensor networks. The EEDTC algorithm uses k-hop neighborhood information, and adjusting k will achieve different message complexity and time complexity for the algorithm. The EEDTC algorithm has good performance on energy consumption and energy balance of the network, and performs well under various traffic patterns in data gathering applications.
Sencondly, for the purpose of gathering data from partially-connected sensor networks, with the help of virtual dominating sets, a grid-based mobile element scheduling (GBMES) algorithm is raised to schedule a mobile element (ME) periodically gathering data from the network. The GBMES algorithm has decent performance on reducing the traveling delay and data gathering delay of ME, which minimizes data loss due to the buffer overflow of sensor nodes.
Thirdly, to efficiently gather data from spase sensor networks, two Voronoi diagram based algorithms are proposed, one is the Voronoi diagram based mobile collector scheduling algorithm (VDMCS), and the other is the multiplicatively weighted Voronoi diagram approach to energy-balancing data collection (MWVDC). Two algorithms both construct a completedly virtual dominating set using iterative virtual site insertion. The completedly virtual dominating set just covers all sensor nodes within a given transmission radius. Based on the completedly virtual dominating set, VDMCS constructs a shortest loop tour for the mobile collector (MC), while MWVDC constructs a loop tour for MC by compromising data gathering delay and energy consumption. Moreover, MWVDC is able to attain energy balance for the sensor network.
Finally, an algorithm named the entropy evaluation for correlation dominating set construction (EECDS) is presented. The EECDS algorithm exploits the concept of the correlation domining set. It first determines the correlation between sensor nodes by evaluating the entropy of random variables, and then distributively generates a correlation graph. At last, the algorithm constructs a correlation dominating set using the information of the correlation graph. The EECDS algorithm is very efficient on reducing data redundancy in wireless sensor networks, and performs well on energy balance and scalability.
无线传感器网络是面向数据的网络,其主要任务就是进行数据处理,包括数据的感知、采集、传输、压缩、聚合等等。传感器网络节点通常密集分布在所监测的网络区域中,并且会产生大量的数据,地理位置邻近的节点产生的数据往往具有很大的相关性,这些都给无线传感器网络的数据采集算法设计带来了很大的挑战。
传感器网络节点是能量受限的,在网络中传输大量的数据必然会缩短网络的生命周期。因此,优化网络通信结构和数据冗余缩减都能显著改善网络在时延、能耗、可靠性等方面的性能。
在无线传感器网络中构造虚拟主干是优化网络通信结构的一个重要手段。支配集是在无线网络中构建虚拟主干最常用的技术,很多文献提出采用连通支配集作为无线网络的虚拟主干,并设计了一些有效的算法,但这些算法都是以通用的无线网络为研究背景,因而在构造连通支配集时没有考虑无线传感器网络的特殊性,包括数据采集、冗余缩减等。
本文主要研究适合在无线传感器网络中进行高效数据采集的支配集结构。
树形通信结构很适合在无线传感器网络中进行消息洪泛、数据采集和数据融合,因此本文先对树形的连通支配集进行研究。一般意义上的连通支配集是基于连通网络的,为了将连通支配集的概念应用到稀疏无线传感器网络中,并且在数据采集时考虑数据的相关性,本文还对支配集的概念进行了扩展,提出了虚拟支配集、全虚拟支配集和关联支配集等概念,并根据扩展的支配集概念,设计了一系列在无线传感器网络进行高效数据采集的算法。
首先,提出了一个能量高效的支配树构造算法(EEDTC)来构建一个能在传感器网络中充当虚拟主干的树形的连通支配集。EEDTC算法利用节点的κ跳邻居节点信息,具有很好的可扩展性,选取合适的κ值能实现不同的消息复杂度和时间复杂度要求,同时EEDTC算法具有很好的节能特性和能量均衡特性。在不同的网络数据采集应用背景下,该算法都表现出很好的性能；
其次,为了实现从部分连通的网络中采集数据,结合虚拟支配集的概念,提出了一个基于网格分割的移动单元调度算法(GBMES),调度一个移动单元(ME)周期性地从网络中采集数据。GBMES算法在降低移动单元的行进时延和数据采集时延等方面具有很好的性能,显著降低了由于传感器网络节点的缓存溢出而产生的数据丢失。
然后,为保证移动采集节点MC在稀疏传感器网络中进行高效数据采集,基于Voronoi图提出了两个算法：基于普通Voronoi图的移动采集节点调度算法(VDMCS)和基于加权Voronoi图的能量均衡数据采集算法(MWVDC)。两个算法都是通过迭代的虚拟散点插入过程生成一个全虚拟支配集,在给定的通信半径范围内,这个集合恰好能覆盖所有的传感器节点。在全虚拟支配集的基础上,VDMCS为MC构建一条最短的行进路径,MWVDC算法则对数据采集时延和网络能耗进行综合考虑,为MC构造一条优化的数据采集路径,同时保证整个网络能量消耗的均衡性。
最后,结合关联支配集的概念,设计了一个基于熵评判的关联支配集构造算法(EECDS),该算法首先通过评价随机变量的熵值来判断网络节点间的数据相关性,然后在网络中分布式地构造一个关联图,最后借助关联图的信息构造一个连通关联支配集。EECDS算法能有效地缩减无线传感器网络的数据冗余,同时具有很好的能量均衡特性和可扩展性。
Wireless sensor networks consist of a large number of sensor nodes, which are equipped with sensing, data processing, and communicating components. The sensor nodes collaborate together to monitor various phenomenons. Due to the low-power, low-cost, intelligent, distributed, and self-organized characteristics, wireless sensor networks have shown great potential in many fields, such as, military, environment, health, business, disaster forecast and relief.
Wireless sensor networks are data-oriented, whose main task is data processing, including sensing, data gathering, transmission, compress, aggregation, and so on. Wireless sensor networks are usually densely deployed in a network area, and generate a great deal of data. Moreover, the data sensed by neighboring nodes is high correlated. These all impose great challenges on the design of data gathering algorithms.
Since the sensor nodes are power-constrained, transferring large amounts of data definitely will shorten the lifetime of sensor networks. Therefore, the network performance on energy consumption and stability could be improved through the communication structure optimization or data redundancy removal.
A virtual backbone plays an important role for the communication structure optimization. One of the frequently used techniques for virtual backbone construction is the dominating set. Many literatures proposed to use a connected dominating set as a virtual backbone in wirless networks, and designed various efficient algorithms. But few of them take special properties of sensor networks into consideration, such as data gathering, redundancy removal, etc.
This dissertation focuses on the dominating set problems for efficient data gathering in wireless sensor networks.
Because the tree structure is more appropriate for flooding, data gathering, and data aggregation in wireless sensor networks, this work first investigate the tree-based connected dominating set problem. The ordinary connected dominating set problems are based on connected networks. To extend the concept of connected dominating set into sparse sensor networks, and considering the data correlation as well, we propose the concepts of the virtual dominating set, the completedly virtual dominating set, and the correlation dominating set. Several efficient data gathering algorithms based on the extended dominating set concept are presented in this dissertation.
Firstly, the energy-efficient dominating tree construction (EEDTC) algorithm is proposed to construct a dominating tree as a virtual backbone in wireless sensor networks. The EEDTC algorithm uses k-hop neighborhood information, and adjusting k will achieve different message complexity and time complexity for the algorithm. The EEDTC algorithm has good performance on energy consumption and energy balance of the network, and performs well under various traffic patterns in data gathering applications.
Sencondly, for the purpose of gathering data from partially-connected sensor networks, with the help of virtual dominating sets, a grid-based mobile element scheduling (GBMES) algorithm is raised to schedule a mobile element (ME) periodically gathering data from the network. The GBMES algorithm has decent performance on reducing the traveling delay and data gathering delay of ME, which minimizes data loss due to the buffer overflow of sensor nodes.
Thirdly, to efficiently gather data from spase sensor networks, two Voronoi diagram based algorithms are proposed, one is the Voronoi diagram based mobile collector scheduling algorithm (VDMCS), and the other is the multiplicatively weighted Voronoi diagram approach to energy-balancing data collection (MWVDC). Two algorithms both construct a completedly virtual dominating set using iterative virtual site insertion. The completedly virtual dominating set just covers all sensor nodes within a given transmission radius. Based on the completedly virtual dominating set, VDMCS constructs a shortest loop tour for the mobile collector (MC), while MWVDC constructs a loop tour for MC by compromising data gathering delay and energy consumption. Moreover, MWVDC is able to attain energy balance for the sensor network.
Finally, an algorithm named the entropy evaluation for correlation dominating set construction (EECDS) is presented. The EECDS algorithm exploits the concept of the correlation domining set. It first determines the correlation between sensor nodes by evaluating the entropy of random variables, and then distributively generates a correlation graph. At last, the algorithm constructs a correlation dominating set using the information of the correlation graph. The EECDS algorithm is very efficient on reducing data redundancy in wireless sensor networks, and performs well on energy balance and scalability.
引文
[1]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci. Wireless sensor networks:A survey [J], Computer Networks,2002,38 (4):393-422.
[2]C. Intanagonwiwat, R. Govindan, D. Estrin. Directed diffusion:A scalable and robust communication paradigm for sensor networks [C], Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom'00), Boston, MA, USA,2000:56-67.
[3]C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, et al. Directed diffusion for wireless sensor networking [J], IEEE/ACM Transactions on Networking,2003,11 (1): 2-16.
[4]J. Agre, L. Clare. An integrated architecture for cooperative sensing networks [J], IEEE Computer,2000,33 (5):106-108.
[5]G. Simon, G. Balogh, G. Pap, M. Maroti, et al. Sensor network-based countersniper system [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004:1-12.
[6]A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, et al. Wireless sensor networks for habitat monitoring [C], Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, United States,2002:88-97.
[7]P. Zhang, C. M. Sadler, S. A. Lyon, M. Martonosi. Hardware design experiences in zebranet [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004:227-238.
[8]G. Tolle, J. Polastre, R. Szewczyk, D. Culler, et al. A macroscope in the redwoods [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[9]C. R. Baker, K. Armijo, S. Belka, M. Benhabib, et al. Wireless sensor networks for home health care [C], Proceedings of 21st International Conference on Advanced Information Networking and Applications Workshops/Symposia (AINAW'07), Niagara Falls, ON, Canada,2007:832-837.
[10]L. Schwiebert, S. K. S. Gupta, J. Weinmann. Research challenges in wireless networks of biomedical sensors [C], Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom'01), Rome,2001:151-165.
[11]P. Bonnet, J. Gehrke, P. Seshadri. Querying the physical world [J], IEEE Personal Communications,2000,7 (5):10-15.
[12]L. Krishnamurthy, R. Adler, P. Buonadonna, J. Chhabra, et al. Design and deployment of industrial sensor networks:Experiences from a semiconductor plant and the north sea [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[13]I. Johnstone, J. Nicholson, B. Shehzad, J. Slipp. Experiences from a wireless sensor network deployment in a petroleum environment [C], Proceedings of the 2007 International Wireless Communications and Mobile Computing Conference (IWCMC 2007), Honolulu, HI, United States,2007:382-387.
[14]J. Yick, B. Mukherjee, D. Ghosal. Wireless sensor network survey [J], Computer Networks,2008,52 (12):2292-2330.
[15]I. F. Akyildiz, E. P. Stuntebeck. Wireless underground sensor networks:Research challenges [J], Ad Hoc Networks,2006,4 (6):669-686.
[16]M. Li, Y. Liu. Underground structure monitoring with wireless sensor networks [C], Proceedings of the Sixth International Symposium on Information Processing in Sensor Networks (IPSN'07), Cambridge, MA, USA,2007:69-78.
[17]I. F. Akyildiz, D. Pompili, T. Melodia. Challenges for efficient communication in underwater acoustic sensor networks [J], SIGBED Rev.,2004,1 (2):3-8.
[18]J. Heidemann, W. Ye, J. Wills, A. Syed, et al. Research challenges and applications for underwater sensor networking [C], Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC'06), Las Vegas, NV, United States,2006:228-235.
[19]I. F. Akyildiz, T. Melodia, K. R. Chowdhury. A survey on wireless multimedia sensor networks [J], Computer Networks,2007,51 (4):921-960.
[20]N. Bulusu, V. Bychkovskiy, D. Estrin, J. Heidemann. Scalable, ad hoc deployable rf-based localization [C], Proceedings of the Grace Hopper Celebration of Women in Computing Conference 2002, Vancouver, Canada,2002.
[21]S. Fitzpatrick, L. Meertens. Diffusion based localization [J], Private Communication, 2004.
[22]A. Sawides, C. C. Han, M. B. Srivastava. Dynamic fine-grained localization in adhoc networks of sensors [C], Proceedings of the 7th Annual Conference on Mobile Computing and Networking, Rome, Italy,2001:166-179.
[23]D. Niculescu, B. Nath. Localized positioning in ad hoc networks [J], Ad Hoc Networks, 2003,1 (2-3):247-259.
[24]R. Nagpal, H. Shrobe, J. Bachrach. Organizing a global coordinate system from local information on an ad hoc sensor network [C], Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks (IPSN'03), Palo Alto, CA, USA,2003:333-348.
[25]D. Moore, J. Leonard, D. Rus, S, Teller. Robust distributed network localization with noisy range measurements [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004: 50-61.
[26]M. Maroti, B. Kusy, G. Balogh, P. Volgyesi, et al. Radio interferometric geolocation [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[27]R. Stoleru, T. He, J. A. Stankovic, D. Luebke, A high-accuracy, low-cost localization system for wireless sensor networks [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[28]N. B. Priyantha, H. Balakrishnan, E. D. Demaine, S. Teller. Mobile-assisted localization in wireless sensor networks [C], Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'05), Miami, FL, United States,2005:172-183.
[29]S. Ganeriwal, D. Ganesan, H. Shim, V. Tsiatsis, et al. Estimating clock uncertainty for efficient duty-cycling in sensor networks [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[30]S. Ganeriwal, R. Kumar, M. B. Srivastava. Timing-sync protocol for sensor networks [C], Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys'03), Los Angeles, CA, United States,2003:138-149.
[31]C. H. Rentel, T. Kunz. A clock-sampling mutual network time-synchronization algorithm for wireless ad hoc networks [C], Proceedings of the 2005 IEEE Wireless Communications and Networking Conference, New Orleans, LA, USA,2005:638-644.
[32]H. Dai, R. Han. Tsync:A lightweight bidirectional time synchronization service for wireless sensor networks [J], SIGMOBILE Mob. Comput. Commun. Rev.,2004,8 (1): 125-139.
[33]Q. Li, D. Rus. Global clock synchronization in sensor networks [J], IEEE Transactions on Computers,2006,55 (2):214-226.
[34]X. Wang, G. Xing, Y. Zhang, C. Lu, et al. Integrated coverage and connectivity configuration in wireless sensor networks [C], Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys'03), Los Angeles, CA, United States,2003:28-39.
[35]B. Chen, K. Jamieson, H. Balakrishnan, R. Morris. Span:An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks [C], Proceedings of the 7th annual international conference on Mobile computing and networking (MobiCom'01), Rome, Italy,2001.
[36]G. Veltri, G. Qu, Q. Huang, M. Potkonjak. Minimal and maximal exposure path algorithms for wireless embedded sensor networks [C], Proceedings of the First International Conference on Embedded Networked Sensor Systems (Sensys'03), Los Angeles, CA, United States,2003:40-50.
[37]A. Howard, M. Mataric, G. Sukhatme. Mobile sensor network deployment using potential fields:A distributed scalable solution to the area coverage problem [C], Proceedings of the 6th International Symposium on Distributed Autonomous Robotic Systems, Fukuoka, Japan,2002:299-308.
[38]S. Poduri, G. S. Sukhatme. Constrained coverage for mobile sensor networks [C], Proceedings of 2004 IEEE International Conference on Robotics and Automation New Orleans, LA, USA,2004:165-171.
[39]G. Wang, G. Cao, T. LaPorta. Movement-assisted sensor deployment [C], Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'04), Hong Kong, China,2004:2469-2479.
[40]G. Wang, G. Cao, T. LaPorta. A bidding protocol for deploying mobile sensors [C], Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP'03), Atlanta, GA, USA,2003:315-324.
[41]W. Wang, V. Srinivasan, K.-C. Chua. Trade-offs between mobility and density for coverage in wireless sensor networks [C], Proceedings of the 13th Annual International Conference on Mobile Computing and Networking (MobiCom'07), Montreal, QC, Canada,2007:39-50.
[42]S. Chellappan, W. Gu, X. Bai, D. Xuan, et al. Deploying wireless sensor networks under limited mobility constraints [J], IEEE Transactions on Mobile Computing,2007,6 (10): 1142-1157.
[43]B. Liu, P. Brass, O. Dousse, P. Nain, et al. Mobility improves coverage of sensor networks [C], Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05), Urbana-Champaign, IL, United States,2005: 300-308.
[44]N. Bisnik, A. Abouzeid, V. Isler. Stochastic event capture using mobile sensors subject to a quality metric [C], Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MobiCom'06), Los Angeles, CA, United States,2006: 98-109.
[45]C. R. Lin, M. Gerla. Adaptive clustering for mobile wireless networks [J], IEEE Journal on Selected Areas in Communications,1997,15 (7):1265-1275.
[46]I. Stojmenovic, M. Seddigh, J. Zunic. Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks [J], IEEE Transactions on Parallel and Distributed Systems,2002,13 (1):14-25.
[47]S. Basagni, A. Carosi, C. Petrioli. Sensor-dmac:Dynamic topology control for wireless sensor networks [C], Proceedings of the IEEE 60th Vehicular Technology Conference (VTC2004), Los Angeles, CA, USA,2004:2930-2935.
[48]H. Chan, A. Perrig. Ace:An emergent algorithm for highly uniform cluster formation [C], Proceedings of the First European Workshop on Wireless Sensor Networks (EWSN 2004), Berlin, Germany,2004:154-171.
[49,]J. Wu, F. Dai. A distributed formation of a virtual backbone in manets using adjustable transmission ranges [C], Proceedings of the 24th IEEE International Conference on Distributed Computing Systems (ICDCS'04), Tokyo, Japan,2004:372-379.
[50]Y. Xu, J. Heidemann, D. Estrin. Geography-informed energy conservation for ad hoc routing [C], Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom'01), Rome,2001:70-84.
[51]A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying for flooding broadcast messages in mobile wireless networks [C], Proceedings of the 35th Annual International Conference on System Sciences (HICSS'02), Big Island, HI, USA,2002:3866-3875.
[52]C. Adjih, P. Jacquet, L. Viennot. Computing connected dominated sets with multipoint relays [J], Ad Hoc and Sensor Networks,2005,1 (1):27-39.
[53]O. Liang, Y. A. Sekercioglu, N. Mani. Enhanced gateway multipoint relays for constructing a small connected dominating set in wireless ad hoc networks [C], Proceedings of the 2006 IEEE Singapore International Conference on Communication Systems (ICCS 2006), Singapore, Singapore,2006:4085677.
[54]J. Wu, H. Li. On calculating connected dominating set for efficient routing in ad hoc wireless networks [C], Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, Seattle, Washington, United States,1999.
[55]F. Dai, J. Wu. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks [J], IEEE Transactions on Parallel and Distributed Systems, 2004,.15 (10):908-920.
[56]R. Sivakumar, B. Das, V. Bharghavan. Spine routing in ad hoc networks [J], Cluster Computing,1998,1 (2):237-248.
[57]W. Peng-Jun, K. M. Alzoubi, O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks [C], Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'02), New York, NY, USA,2002:1597-1604.
[58]B. Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems [C], Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC'87), New York, NY, USA,1987:230-240.
[59]F. Dai, J. Wu. On constructing k-connected k-dominating set in wireless networks [C], Proceedings of the 19th IEEE International Symposium on Parallel and Distributed Processing, Denver, CO, USA,2005:10 pp.
[60]M. T. Thai, N. Zhang, T. Ravi, X. Xu. On approximation algorithms of k-connected m-dominating sets in disk graphs [J], Theoretical Computer Science,2007,385 (1-3): 49-59.
[61]J. Kusuma, L. Doherty, K. Ramchandran. Distributed compression for sensor networks [C], Proceedings of the 2001 International Conference on Image Processing (ICIP'01), Thessaloniki, Greece,2001:82-85.
[62]S. S. Pradhan, J. Kusuma, K. Ramchandran. Distributed compression in a dense microsensor network [J], IEEE Signal Processing Magazine,2002,19 (2):51-60.
[63]Z. Xiong, A. D. Liveris, S. Cheng. Distributed source coding for sensor networks [J], IEEE Signal Processing Magazine,2004,21 (5):80-94.
[64]D. Petrovic, R. Shah, K. Ramchandran, J. Rabaey. Data funneling:Routing with aggregation and compression for wireless sensor networks [C], Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications (SNPA 2003),, Anchorage, AK,2003:156-162.
[65]S. Nath, P. B. Gibbons, S. Seshan, Z. R. Anderson. Synopsis diffusion for robust aggregation in sensor networks [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States, 2004:250-262.
[66]N. Shrivastava, C. Buragohain, D. Agrawal, S. Suri. Medians and beyond:New aggregation techniques for sensor networks [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004:239-249.
[67]P. Von Rickenbach, R. Wattenhofer. Gathering correlated data in sensor networks [C], Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC'04), Philadelphia, PA, United States,2004:60-66.
[68]J. Chou, D. Petrovic, R. Kannan. A distributed and adaptive signal processing approach to reducing energy consumption in sensor networks [C], Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03), San Francisco, CA, USA,2003:1054-1062.
[69]R. Cristescu, B. Beferull-Lozano, M. Vetterli. On network correlated data gathering [C], Proceedings of the 23 rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'04), Hong Kong, China,2004:2571-2582.
[70]R. Cristescu, M. Vetterli. Power efficient gathering of correlated data:Optimization, np-completeness and heuristics [J], SIGMOBILE Mob. Comput. Commun. Rev.,2003,7 (3):31-32.
[71]A. Goel, D. Estrin. Simultaneous optimization for concave costs:Single sink aggregation or single source buy-at-bulk [J], Algorithmica,2005,43 (1-2):5-15.
[72]M. Enachescu, A. Goel, R. Govindan, R. Motwani. Scale free aggregation in sensor networks [C], Proceedings of the First International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors'04), Turku, Finland,2004:71-84.
[73]Y. SunHee, C. Shahabi. Exploiting spatial correlation towards an energy efficient clustered aggregation technique (cag) [C], Proceedings of the International Conference on Communications (ICC'05), Seoul, South Korea,2005:3307-3313.
[74]H. Gupta, V. Navda, S. Das, V. Chowdhary. Efficient gathering of correlated data in sensor networks [J], ACM Transactions on Sensor Networks,2008,4 (1):4.
[75]A. Wacker, M. Knoll, T. Heiber, K. Rothermel. A new approach for establishing pairwise keys for securing wireless sensor networks [C], Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems (SenSys'05), San Diego, California, USA,2005.
[76]F. Liu, J. Rivera, X. Cheng. Location-aware key establishment in wireless sensor networks [C], Proceedings of the 2006 International Wireless Communications and Mobile Computing Conference (IWCMC 2006), Vancouver, BC, Canada,2006:21-26.
[77]C. Karlof, N. Sastry, D. Wagner. Tinysec:A link layer security architecture for wireless sensor networks [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004:162-175.
[78]M. V. Marathe, H. Breu, H. B. Hunt, Ⅲ, S. S. Ravi, et al. Simple heuristics for unit disk graphs [J], Journal of Networks,1995,25 (2):59-68.
[79]M. R. Garey, D. S. Johnson. Computers and intractability-a guide to the theory of np-completeness [M], New York,1979.
[80]J. Goodman, J. O'Rourke. Handbook of discrete and computational geometry [M], Boca Raton:CRC Press, Inc.,1997.
[81]M. Gerla, T. Jack Tzu-Chieh. Multicluster, mobile, multimedia radio network [J], Wireless Networks,1995,1 (3):255-265.
[82]G. Chen, I. Stojmenovic. Clustering and routing in wireless ad hoc networks [R], Technical Report Computer Science, SITE, University of Ottawa,1999.
[83]K. M. Alzoubi, P. J. Wan,0. Frieder. Distributed heuristics for connected dominating sets in wireless ad hoc networks [J], Journal of Communications and Networks,2002,4 (1):22-29.
[84]M. Manki, F. Wang, D. Z. Du, P. M. Pardalos. A reliable virtual backbone scheme in mobile ad-hoc networks [C], Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS'04), Fort Lauderdale, FL, USA,2004:60-69.
[85]I. Cidon, O. Mokryn. Propagation and leader election in a multihop broadcast environment [C], Proceedings of the 12th International Symposium on Distributed Computing, Andros, Greece,1998:104-118.
[86]J. Wu, F. Dai, S. Yang. Iterative local solutions for connected dominating sets in ad hoc wireless networks [J], IEEE Transactions on Computers,2008,57 (5):702-715.
[87]M. Kubisch, H. Karl, A. Wolisz, L. C. Zhong, et al. Distributed algorithms for transmission power control in wireless sensor networks [C], Proceedings of the 2003 IEEE Wireless Communications and Networking Conference (WCNC'03), New Orleans, LA, USA,2003:558-563.
[88]J. Wu, M. Gao, I. Stojmenovic. On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks [C], Proceedings of the International Conference on Parallel Processing (IPPN'01), Valencia, Spain,2001:346-354.
[89]B. Kim, J. Yang, D. Zhou, M. T. Sun. Energy-aware connected dominating set construction in mobile ad hoc networks [C], Proceedings of the 14th International Conference on Computer Communications and Networks (ICCCN'05), San Diego, CA, USA,2005:229-234.
[90]J. Wu, F. Dai. Virtual backbone construction in manets using adjustable transmission ranges [J], IEEE Transactions on Mobile Computing,2006,5 (9):1188-1200.
[91]M. T. Thai, F. Wang, D. Liu, S. Zhu, et al. Connected dominating sets in wireless networks with different transmission ranges [J], IEEE Transactions on Mobile Computing, 2007,6 (7):721-730.
[92]G. Gutin, A. Punnen. The traveling salesman problem and its variations [M], Boston, USA:Kluwer Academic Publishers,2002.
[93]T. Cormen, C. Leiserson, R. Rivest. Introduction to algorithms [M]:The MIT Press, 2002.
[94]J. J. Bentley. Fast algorithms for geometric traveling salesman problems [J], ORSA Journal on Computing,1992,4 (4):387-411.
[95]G. Thompson. Hamiltonian tours and paths in rectangular lattice graphs [J], Mathematics Magazine,1977,50:147-150.
[96]Y. Gu, D. Bozdag., R. W. Brewer, E. Ekici. Data harvesting with mobile elements in wireless sensor networks [J], Computer Networks,2006,50 (17):3449-3465.
[97]A. Vahdat, D. Becker. Epidemic routing for partially connected ad hoc networks [R], Technical Report Duke University,2000.
[98]Q. Li, D. Rus. Sending messages to mobile users in disconnected ad-hoc wireless networks [C], Proceedings of the 6th annual international conference on Mobile computing and networking (MobiCom'00), Boston, MA, USA,2000:44-55.
[99]C. Okino, G. Cybenko. Modeling and analysis of active messages in volatile networks [C], Proceedings of the 37th Allerton Conference on Communication, Control, Computing,, Monticello, IL, USA,1999.
[100]R. C. Shah, S. Roy, S. Jain, W. Brunette. Data mules:Modeling and analysis of a three-tier architecture for sparse sensor networks [J], Ad Hoc Networks,2003,1 (2-3): 215-233.
[101]Z. Wenrui, M. H. Ammar. Message ferrying:Proactive routing in highly-partitioned' wireless ad hoc networks [C], Proceedings of the Ninth IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS'03), San Juan, Puerto Rico,2003:308-314.
[102]W. Zhao, M. Ammar, E. Zegura. A message ferrying approach for data delivery in sparse mobile ad hoc networks [C], Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'04), Tokyo, Japan,2004:187-198.
[103]W. Zhao, M. Ammar, E. Zegura. Controlling the mobility of multiple data transport ferries in a delay-tolerant network [C], Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'05), Miami, FL, USA, 2005:1407-1418.
[104]K. A. Harras, K. C. Almeroth. Inter-regional messenger scheduling in delay tolerant mobile networks [C], Proceedings of the 2006 International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM'06), Buffalo-Niagara Falls, NY, United States,2006:93-102.
[105]M. M. B. Tariq, M. Ammar, E. Zegura. Message ferry route design for sparse ad hoc networks with mobile nodes [C], Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc'06), Florence, Italy,2006:37-48.
[106]T. Bektas. The multiple traveling salesman problem:An overview of formulations and solution procedures [J], Omega,2006,34 (3):209-219.
[107]P. Toth, E. Vigo. The vehicle routing problem [M]:Society for Industrial and Applied Mathematics,2001.
[108]B. L. Brumitt, A. Stentz. Dynamic mission planning for multiple mobile robots [C], Proceedings of the IEEE international conference on robotics and automation, Minneapolis, MN, USA,1996:2396-2401.
[109]C. Okonjo-Adigwe. An effective method of balancing the workload amongst salesmen [J], Omega,1988,16 (2):159-163.
[110]X. Wang, A. C. Regan. Local truckload pickup and delivery with hard time window constraints [J], Transportation Research, Part B (Methodological),2002,36B (2):97-112.
[111]N. Bansal, S. Chawla, A. Blum, A. Meyerson. Approximation algorithms for deadline-tsp and vehicle routing with time-windows [C], Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing (STOC'04), Chicago, IL, United States,2004:166-174.
[112]M. M. Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints [J], Operations Research,1987,35 (2):254-265.
[113]P. Bhattacharya, M. L. Gavrilova. Voronoi diagram in optimal path planning [C], Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering, Glamorgan, UK,2007:33-42.
[114]E. Masehian, M. R. Amin-Naseri. A voronoi diagram-visibility graph-potential field compound algorithm for robot path planning [J], Journal of Robotic Systems,2004,21 (6):275-300.
[115]T. M. Cover, J. A. Thomas. Elements of information theory [M]:John Wiley and Sons, Inc.,1991.
[116]D. Slepian, J. K. Wolf. Noiseless coding of correlated information sources [J], IEEE Transactions on Information Theory,1973, IT-19 (4):471-480.
[117]D. Ganesan, R. Cristescu, B. Beferull-Lozano. Power-efficient sensor placement and transmission structure for data gathering under distortion constraints [C], Proceedings of the Third International Symposium on Information Processing in Sensor Networks (IPSN'04), Berkeley, CA, USA,2004:142-150.
[118]F. Ye, G. Zhong, J. Cheng, S. Lu, et al. Peas:A robust energy conserving protocol for long-lived sensor networks [C], Proceedings of the International Conference on Distributed Computing Systems (ICDCS'03), Providence, RI, United States,2003:28-37.
[119]A. Cerpa, D. Estrin. Ascent:Adaptive self-configuring sensor networks topologies [J], IEEE Transactions on Mobile Computing,2004,3 (3):272-285.
[2]C. Intanagonwiwat, R. Govindan, D. Estrin. Directed diffusion:A scalable and robust communication paradigm for sensor networks [C], Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom'00), Boston, MA, USA,2000:56-67.
[3]C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, et al. Directed diffusion for wireless sensor networking [J], IEEE/ACM Transactions on Networking,2003,11 (1): 2-16.
[4]J. Agre, L. Clare. An integrated architecture for cooperative sensing networks [J], IEEE Computer,2000,33 (5):106-108.
[5]G. Simon, G. Balogh, G. Pap, M. Maroti, et al. Sensor network-based countersniper system [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004:1-12.
[6]A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, et al. Wireless sensor networks for habitat monitoring [C], Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, United States,2002:88-97.
[7]P. Zhang, C. M. Sadler, S. A. Lyon, M. Martonosi. Hardware design experiences in zebranet [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004:227-238.
[8]G. Tolle, J. Polastre, R. Szewczyk, D. Culler, et al. A macroscope in the redwoods [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[9]C. R. Baker, K. Armijo, S. Belka, M. Benhabib, et al. Wireless sensor networks for home health care [C], Proceedings of 21st International Conference on Advanced Information Networking and Applications Workshops/Symposia (AINAW'07), Niagara Falls, ON, Canada,2007:832-837.
[10]L. Schwiebert, S. K. S. Gupta, J. Weinmann. Research challenges in wireless networks of biomedical sensors [C], Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom'01), Rome,2001:151-165.
[11]P. Bonnet, J. Gehrke, P. Seshadri. Querying the physical world [J], IEEE Personal Communications,2000,7 (5):10-15.
[12]L. Krishnamurthy, R. Adler, P. Buonadonna, J. Chhabra, et al. Design and deployment of industrial sensor networks:Experiences from a semiconductor plant and the north sea [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[13]I. Johnstone, J. Nicholson, B. Shehzad, J. Slipp. Experiences from a wireless sensor network deployment in a petroleum environment [C], Proceedings of the 2007 International Wireless Communications and Mobile Computing Conference (IWCMC 2007), Honolulu, HI, United States,2007:382-387.
[14]J. Yick, B. Mukherjee, D. Ghosal. Wireless sensor network survey [J], Computer Networks,2008,52 (12):2292-2330.
[15]I. F. Akyildiz, E. P. Stuntebeck. Wireless underground sensor networks:Research challenges [J], Ad Hoc Networks,2006,4 (6):669-686.
[16]M. Li, Y. Liu. Underground structure monitoring with wireless sensor networks [C], Proceedings of the Sixth International Symposium on Information Processing in Sensor Networks (IPSN'07), Cambridge, MA, USA,2007:69-78.
[17]I. F. Akyildiz, D. Pompili, T. Melodia. Challenges for efficient communication in underwater acoustic sensor networks [J], SIGBED Rev.,2004,1 (2):3-8.
[18]J. Heidemann, W. Ye, J. Wills, A. Syed, et al. Research challenges and applications for underwater sensor networking [C], Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC'06), Las Vegas, NV, United States,2006:228-235.
[19]I. F. Akyildiz, T. Melodia, K. R. Chowdhury. A survey on wireless multimedia sensor networks [J], Computer Networks,2007,51 (4):921-960.
[20]N. Bulusu, V. Bychkovskiy, D. Estrin, J. Heidemann. Scalable, ad hoc deployable rf-based localization [C], Proceedings of the Grace Hopper Celebration of Women in Computing Conference 2002, Vancouver, Canada,2002.
[21]S. Fitzpatrick, L. Meertens. Diffusion based localization [J], Private Communication, 2004.
[22]A. Sawides, C. C. Han, M. B. Srivastava. Dynamic fine-grained localization in adhoc networks of sensors [C], Proceedings of the 7th Annual Conference on Mobile Computing and Networking, Rome, Italy,2001:166-179.
[23]D. Niculescu, B. Nath. Localized positioning in ad hoc networks [J], Ad Hoc Networks, 2003,1 (2-3):247-259.
[24]R. Nagpal, H. Shrobe, J. Bachrach. Organizing a global coordinate system from local information on an ad hoc sensor network [C], Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks (IPSN'03), Palo Alto, CA, USA,2003:333-348.
[25]D. Moore, J. Leonard, D. Rus, S, Teller. Robust distributed network localization with noisy range measurements [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004: 50-61.
[26]M. Maroti, B. Kusy, G. Balogh, P. Volgyesi, et al. Radio interferometric geolocation [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[27]R. Stoleru, T. He, J. A. Stankovic, D. Luebke, A high-accuracy, low-cost localization system for wireless sensor networks [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[28]N. B. Priyantha, H. Balakrishnan, E. D. Demaine, S. Teller. Mobile-assisted localization in wireless sensor networks [C], Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'05), Miami, FL, United States,2005:172-183.
[29]S. Ganeriwal, D. Ganesan, H. Shim, V. Tsiatsis, et al. Estimating clock uncertainty for efficient duty-cycling in sensor networks [C], Proceedings of the 3rd international conference on Embedded networked sensor systems (SenSys'05), San Diego, California, USA,2005.
[30]S. Ganeriwal, R. Kumar, M. B. Srivastava. Timing-sync protocol for sensor networks [C], Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys'03), Los Angeles, CA, United States,2003:138-149.
[31]C. H. Rentel, T. Kunz. A clock-sampling mutual network time-synchronization algorithm for wireless ad hoc networks [C], Proceedings of the 2005 IEEE Wireless Communications and Networking Conference, New Orleans, LA, USA,2005:638-644.
[32]H. Dai, R. Han. Tsync:A lightweight bidirectional time synchronization service for wireless sensor networks [J], SIGMOBILE Mob. Comput. Commun. Rev.,2004,8 (1): 125-139.
[33]Q. Li, D. Rus. Global clock synchronization in sensor networks [J], IEEE Transactions on Computers,2006,55 (2):214-226.
[34]X. Wang, G. Xing, Y. Zhang, C. Lu, et al. Integrated coverage and connectivity configuration in wireless sensor networks [C], Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys'03), Los Angeles, CA, United States,2003:28-39.
[35]B. Chen, K. Jamieson, H. Balakrishnan, R. Morris. Span:An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks [C], Proceedings of the 7th annual international conference on Mobile computing and networking (MobiCom'01), Rome, Italy,2001.
[36]G. Veltri, G. Qu, Q. Huang, M. Potkonjak. Minimal and maximal exposure path algorithms for wireless embedded sensor networks [C], Proceedings of the First International Conference on Embedded Networked Sensor Systems (Sensys'03), Los Angeles, CA, United States,2003:40-50.
[37]A. Howard, M. Mataric, G. Sukhatme. Mobile sensor network deployment using potential fields:A distributed scalable solution to the area coverage problem [C], Proceedings of the 6th International Symposium on Distributed Autonomous Robotic Systems, Fukuoka, Japan,2002:299-308.
[38]S. Poduri, G. S. Sukhatme. Constrained coverage for mobile sensor networks [C], Proceedings of 2004 IEEE International Conference on Robotics and Automation New Orleans, LA, USA,2004:165-171.
[39]G. Wang, G. Cao, T. LaPorta. Movement-assisted sensor deployment [C], Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'04), Hong Kong, China,2004:2469-2479.
[40]G. Wang, G. Cao, T. LaPorta. A bidding protocol for deploying mobile sensors [C], Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP'03), Atlanta, GA, USA,2003:315-324.
[41]W. Wang, V. Srinivasan, K.-C. Chua. Trade-offs between mobility and density for coverage in wireless sensor networks [C], Proceedings of the 13th Annual International Conference on Mobile Computing and Networking (MobiCom'07), Montreal, QC, Canada,2007:39-50.
[42]S. Chellappan, W. Gu, X. Bai, D. Xuan, et al. Deploying wireless sensor networks under limited mobility constraints [J], IEEE Transactions on Mobile Computing,2007,6 (10): 1142-1157.
[43]B. Liu, P. Brass, O. Dousse, P. Nain, et al. Mobility improves coverage of sensor networks [C], Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05), Urbana-Champaign, IL, United States,2005: 300-308.
[44]N. Bisnik, A. Abouzeid, V. Isler. Stochastic event capture using mobile sensors subject to a quality metric [C], Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MobiCom'06), Los Angeles, CA, United States,2006: 98-109.
[45]C. R. Lin, M. Gerla. Adaptive clustering for mobile wireless networks [J], IEEE Journal on Selected Areas in Communications,1997,15 (7):1265-1275.
[46]I. Stojmenovic, M. Seddigh, J. Zunic. Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks [J], IEEE Transactions on Parallel and Distributed Systems,2002,13 (1):14-25.
[47]S. Basagni, A. Carosi, C. Petrioli. Sensor-dmac:Dynamic topology control for wireless sensor networks [C], Proceedings of the IEEE 60th Vehicular Technology Conference (VTC2004), Los Angeles, CA, USA,2004:2930-2935.
[48]H. Chan, A. Perrig. Ace:An emergent algorithm for highly uniform cluster formation [C], Proceedings of the First European Workshop on Wireless Sensor Networks (EWSN 2004), Berlin, Germany,2004:154-171.
[49,]J. Wu, F. Dai. A distributed formation of a virtual backbone in manets using adjustable transmission ranges [C], Proceedings of the 24th IEEE International Conference on Distributed Computing Systems (ICDCS'04), Tokyo, Japan,2004:372-379.
[50]Y. Xu, J. Heidemann, D. Estrin. Geography-informed energy conservation for ad hoc routing [C], Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom'01), Rome,2001:70-84.
[51]A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying for flooding broadcast messages in mobile wireless networks [C], Proceedings of the 35th Annual International Conference on System Sciences (HICSS'02), Big Island, HI, USA,2002:3866-3875.
[52]C. Adjih, P. Jacquet, L. Viennot. Computing connected dominated sets with multipoint relays [J], Ad Hoc and Sensor Networks,2005,1 (1):27-39.
[53]O. Liang, Y. A. Sekercioglu, N. Mani. Enhanced gateway multipoint relays for constructing a small connected dominating set in wireless ad hoc networks [C], Proceedings of the 2006 IEEE Singapore International Conference on Communication Systems (ICCS 2006), Singapore, Singapore,2006:4085677.
[54]J. Wu, H. Li. On calculating connected dominating set for efficient routing in ad hoc wireless networks [C], Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, Seattle, Washington, United States,1999.
[55]F. Dai, J. Wu. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks [J], IEEE Transactions on Parallel and Distributed Systems, 2004,.15 (10):908-920.
[56]R. Sivakumar, B. Das, V. Bharghavan. Spine routing in ad hoc networks [J], Cluster Computing,1998,1 (2):237-248.
[57]W. Peng-Jun, K. M. Alzoubi, O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks [C], Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'02), New York, NY, USA,2002:1597-1604.
[58]B. Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems [C], Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC'87), New York, NY, USA,1987:230-240.
[59]F. Dai, J. Wu. On constructing k-connected k-dominating set in wireless networks [C], Proceedings of the 19th IEEE International Symposium on Parallel and Distributed Processing, Denver, CO, USA,2005:10 pp.
[60]M. T. Thai, N. Zhang, T. Ravi, X. Xu. On approximation algorithms of k-connected m-dominating sets in disk graphs [J], Theoretical Computer Science,2007,385 (1-3): 49-59.
[61]J. Kusuma, L. Doherty, K. Ramchandran. Distributed compression for sensor networks [C], Proceedings of the 2001 International Conference on Image Processing (ICIP'01), Thessaloniki, Greece,2001:82-85.
[62]S. S. Pradhan, J. Kusuma, K. Ramchandran. Distributed compression in a dense microsensor network [J], IEEE Signal Processing Magazine,2002,19 (2):51-60.
[63]Z. Xiong, A. D. Liveris, S. Cheng. Distributed source coding for sensor networks [J], IEEE Signal Processing Magazine,2004,21 (5):80-94.
[64]D. Petrovic, R. Shah, K. Ramchandran, J. Rabaey. Data funneling:Routing with aggregation and compression for wireless sensor networks [C], Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications (SNPA 2003),, Anchorage, AK,2003:156-162.
[65]S. Nath, P. B. Gibbons, S. Seshan, Z. R. Anderson. Synopsis diffusion for robust aggregation in sensor networks [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States, 2004:250-262.
[66]N. Shrivastava, C. Buragohain, D. Agrawal, S. Suri. Medians and beyond:New aggregation techniques for sensor networks [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004:239-249.
[67]P. Von Rickenbach, R. Wattenhofer. Gathering correlated data in sensor networks [C], Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC'04), Philadelphia, PA, United States,2004:60-66.
[68]J. Chou, D. Petrovic, R. Kannan. A distributed and adaptive signal processing approach to reducing energy consumption in sensor networks [C], Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03), San Francisco, CA, USA,2003:1054-1062.
[69]R. Cristescu, B. Beferull-Lozano, M. Vetterli. On network correlated data gathering [C], Proceedings of the 23 rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'04), Hong Kong, China,2004:2571-2582.
[70]R. Cristescu, M. Vetterli. Power efficient gathering of correlated data:Optimization, np-completeness and heuristics [J], SIGMOBILE Mob. Comput. Commun. Rev.,2003,7 (3):31-32.
[71]A. Goel, D. Estrin. Simultaneous optimization for concave costs:Single sink aggregation or single source buy-at-bulk [J], Algorithmica,2005,43 (1-2):5-15.
[72]M. Enachescu, A. Goel, R. Govindan, R. Motwani. Scale free aggregation in sensor networks [C], Proceedings of the First International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors'04), Turku, Finland,2004:71-84.
[73]Y. SunHee, C. Shahabi. Exploiting spatial correlation towards an energy efficient clustered aggregation technique (cag) [C], Proceedings of the International Conference on Communications (ICC'05), Seoul, South Korea,2005:3307-3313.
[74]H. Gupta, V. Navda, S. Das, V. Chowdhary. Efficient gathering of correlated data in sensor networks [J], ACM Transactions on Sensor Networks,2008,4 (1):4.
[75]A. Wacker, M. Knoll, T. Heiber, K. Rothermel. A new approach for establishing pairwise keys for securing wireless sensor networks [C], Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems (SenSys'05), San Diego, California, USA,2005.
[76]F. Liu, J. Rivera, X. Cheng. Location-aware key establishment in wireless sensor networks [C], Proceedings of the 2006 International Wireless Communications and Mobile Computing Conference (IWCMC 2006), Vancouver, BC, Canada,2006:21-26.
[77]C. Karlof, N. Sastry, D. Wagner. Tinysec:A link layer security architecture for wireless sensor networks [C], Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys'04), Baltimore, MD, United States,2004:162-175.
[78]M. V. Marathe, H. Breu, H. B. Hunt, Ⅲ, S. S. Ravi, et al. Simple heuristics for unit disk graphs [J], Journal of Networks,1995,25 (2):59-68.
[79]M. R. Garey, D. S. Johnson. Computers and intractability-a guide to the theory of np-completeness [M], New York,1979.
[80]J. Goodman, J. O'Rourke. Handbook of discrete and computational geometry [M], Boca Raton:CRC Press, Inc.,1997.
[81]M. Gerla, T. Jack Tzu-Chieh. Multicluster, mobile, multimedia radio network [J], Wireless Networks,1995,1 (3):255-265.
[82]G. Chen, I. Stojmenovic. Clustering and routing in wireless ad hoc networks [R], Technical Report Computer Science, SITE, University of Ottawa,1999.
[83]K. M. Alzoubi, P. J. Wan,0. Frieder. Distributed heuristics for connected dominating sets in wireless ad hoc networks [J], Journal of Communications and Networks,2002,4 (1):22-29.
[84]M. Manki, F. Wang, D. Z. Du, P. M. Pardalos. A reliable virtual backbone scheme in mobile ad-hoc networks [C], Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS'04), Fort Lauderdale, FL, USA,2004:60-69.
[85]I. Cidon, O. Mokryn. Propagation and leader election in a multihop broadcast environment [C], Proceedings of the 12th International Symposium on Distributed Computing, Andros, Greece,1998:104-118.
[86]J. Wu, F. Dai, S. Yang. Iterative local solutions for connected dominating sets in ad hoc wireless networks [J], IEEE Transactions on Computers,2008,57 (5):702-715.
[87]M. Kubisch, H. Karl, A. Wolisz, L. C. Zhong, et al. Distributed algorithms for transmission power control in wireless sensor networks [C], Proceedings of the 2003 IEEE Wireless Communications and Networking Conference (WCNC'03), New Orleans, LA, USA,2003:558-563.
[88]J. Wu, M. Gao, I. Stojmenovic. On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks [C], Proceedings of the International Conference on Parallel Processing (IPPN'01), Valencia, Spain,2001:346-354.
[89]B. Kim, J. Yang, D. Zhou, M. T. Sun. Energy-aware connected dominating set construction in mobile ad hoc networks [C], Proceedings of the 14th International Conference on Computer Communications and Networks (ICCCN'05), San Diego, CA, USA,2005:229-234.
[90]J. Wu, F. Dai. Virtual backbone construction in manets using adjustable transmission ranges [J], IEEE Transactions on Mobile Computing,2006,5 (9):1188-1200.
[91]M. T. Thai, F. Wang, D. Liu, S. Zhu, et al. Connected dominating sets in wireless networks with different transmission ranges [J], IEEE Transactions on Mobile Computing, 2007,6 (7):721-730.
[92]G. Gutin, A. Punnen. The traveling salesman problem and its variations [M], Boston, USA:Kluwer Academic Publishers,2002.
[93]T. Cormen, C. Leiserson, R. Rivest. Introduction to algorithms [M]:The MIT Press, 2002.
[94]J. J. Bentley. Fast algorithms for geometric traveling salesman problems [J], ORSA Journal on Computing,1992,4 (4):387-411.
[95]G. Thompson. Hamiltonian tours and paths in rectangular lattice graphs [J], Mathematics Magazine,1977,50:147-150.
[96]Y. Gu, D. Bozdag., R. W. Brewer, E. Ekici. Data harvesting with mobile elements in wireless sensor networks [J], Computer Networks,2006,50 (17):3449-3465.
[97]A. Vahdat, D. Becker. Epidemic routing for partially connected ad hoc networks [R], Technical Report Duke University,2000.
[98]Q. Li, D. Rus. Sending messages to mobile users in disconnected ad-hoc wireless networks [C], Proceedings of the 6th annual international conference on Mobile computing and networking (MobiCom'00), Boston, MA, USA,2000:44-55.
[99]C. Okino, G. Cybenko. Modeling and analysis of active messages in volatile networks [C], Proceedings of the 37th Allerton Conference on Communication, Control, Computing,, Monticello, IL, USA,1999.
[100]R. C. Shah, S. Roy, S. Jain, W. Brunette. Data mules:Modeling and analysis of a three-tier architecture for sparse sensor networks [J], Ad Hoc Networks,2003,1 (2-3): 215-233.
[101]Z. Wenrui, M. H. Ammar. Message ferrying:Proactive routing in highly-partitioned' wireless ad hoc networks [C], Proceedings of the Ninth IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS'03), San Juan, Puerto Rico,2003:308-314.
[102]W. Zhao, M. Ammar, E. Zegura. A message ferrying approach for data delivery in sparse mobile ad hoc networks [C], Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'04), Tokyo, Japan,2004:187-198.
[103]W. Zhao, M. Ammar, E. Zegura. Controlling the mobility of multiple data transport ferries in a delay-tolerant network [C], Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'05), Miami, FL, USA, 2005:1407-1418.
[104]K. A. Harras, K. C. Almeroth. Inter-regional messenger scheduling in delay tolerant mobile networks [C], Proceedings of the 2006 International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM'06), Buffalo-Niagara Falls, NY, United States,2006:93-102.
[105]M. M. B. Tariq, M. Ammar, E. Zegura. Message ferry route design for sparse ad hoc networks with mobile nodes [C], Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc'06), Florence, Italy,2006:37-48.
[106]T. Bektas. The multiple traveling salesman problem:An overview of formulations and solution procedures [J], Omega,2006,34 (3):209-219.
[107]P. Toth, E. Vigo. The vehicle routing problem [M]:Society for Industrial and Applied Mathematics,2001.
[108]B. L. Brumitt, A. Stentz. Dynamic mission planning for multiple mobile robots [C], Proceedings of the IEEE international conference on robotics and automation, Minneapolis, MN, USA,1996:2396-2401.
[109]C. Okonjo-Adigwe. An effective method of balancing the workload amongst salesmen [J], Omega,1988,16 (2):159-163.
[110]X. Wang, A. C. Regan. Local truckload pickup and delivery with hard time window constraints [J], Transportation Research, Part B (Methodological),2002,36B (2):97-112.
[111]N. Bansal, S. Chawla, A. Blum, A. Meyerson. Approximation algorithms for deadline-tsp and vehicle routing with time-windows [C], Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing (STOC'04), Chicago, IL, United States,2004:166-174.
[112]M. M. Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints [J], Operations Research,1987,35 (2):254-265.
[113]P. Bhattacharya, M. L. Gavrilova. Voronoi diagram in optimal path planning [C], Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering, Glamorgan, UK,2007:33-42.
[114]E. Masehian, M. R. Amin-Naseri. A voronoi diagram-visibility graph-potential field compound algorithm for robot path planning [J], Journal of Robotic Systems,2004,21 (6):275-300.
[115]T. M. Cover, J. A. Thomas. Elements of information theory [M]:John Wiley and Sons, Inc.,1991.
[116]D. Slepian, J. K. Wolf. Noiseless coding of correlated information sources [J], IEEE Transactions on Information Theory,1973, IT-19 (4):471-480.
[117]D. Ganesan, R. Cristescu, B. Beferull-Lozano. Power-efficient sensor placement and transmission structure for data gathering under distortion constraints [C], Proceedings of the Third International Symposium on Information Processing in Sensor Networks (IPSN'04), Berkeley, CA, USA,2004:142-150.
[118]F. Ye, G. Zhong, J. Cheng, S. Lu, et al. Peas:A robust energy conserving protocol for long-lived sensor networks [C], Proceedings of the International Conference on Distributed Computing Systems (ICDCS'03), Providence, RI, United States,2003:28-37.
[119]A. Cerpa, D. Estrin. Ascent:Adaptive self-configuring sensor networks topologies [J], IEEE Transactions on Mobile Computing,2004,3 (3):272-285.