无线传感器网络生存时间优化问题研究
|
摘要
无线传感器网络是当今网络技术的一个研究热点。传感器节点集成了微传感器、微控制器和无线通信模块,具有体积小、功耗低、价格低廉和无线通信等优势。传感器节点可以随机部署、自组成网,完成对环境数据的自动化采集、处理和传输。无线传感器网络连接了信息世界和现实世界,提高了人们对物理世界的认识能力,有广阔的发展前景。
能源受限是无线传感器网络的一个突出特点。针对无线传感器网络的研究必须充分考虑节能性。节能的目标是延长网络的生存时间。由于通信能耗占传感器节点总能耗的绝大部分,设计节能的通信协议是延长无线传感器网络生存时间的一个重要途径。生存时间优化和休眠调度分别从不同角度对通信能耗进行了优化。其中,生存时间优化解决的是网络中有数据传输时如何均衡各节点能耗的问题,而休眠调度解决的是如何安排没有数据采集和传输任务的节点休眠以降低空闲能耗的问题。两者可以联合使用以提高网络的生存时间。
无线传感器网络中的主要流量是传感器节点到sink节点的数据汇集流。而且中间节点可能在传输过程中进行数据聚合,这和传统网络有很大不同。流量的汇集性特点为通信协议的设计提出了新的要求,同时也为生存时间的全局优化提供了机会。
生存时间优化就是在给定节点的初始能量、数据产生速度和链路传输代价等约束的情况下,寻求流量或流速在网络上的最佳分配方案以使网络生存时间最大化。根据是否考虑数据聚合、节点是否具有发射功率控制能力、是否考虑接收功耗、是否考虑多种物流、路由结构是否动态可变,以及所针对的通信类型和所采用的生存时间定义,生存时间优化有多种不同的问题模型和不同的求解难度。
本文首先针对发射功率不可控的单物流传感器网络上的单播生存时间优化问题从网络流的角度进行建模。把多到一或多到多的单物流无线传感器网络中,数据汇集流所引发的生存时间优化问题转化为点弧权网络上单源单汇的最大流问题。在对这一问题进行分析的基础上,给出两个复杂度不同的集中式算法VABA和FAT,以及一个分布式算法ADALM。它们都属于判定性算法,能够在多项式时间内判断一个传感器网络的最大生存时间能否达到给定的数值。使用判定性算法结合生存时间上限通过折半查找能够以所需精度逼近最大生存时间和最佳传输方案。
在此基础上把网络流模型扩展到发射功率可控的无线传感器网络上。将VABA扩展为I-VABA算法,并提出以圈流调整将不可增广的阻塞流转化为同等流量下的理想流以便进一步增广。据此提出基于圈流调整的启发式网络流算法AOC。比较其它启发式算法,AOC的近似度更高或基本持平,但运算时间却大大降低,对网络规模的扩展性更强。
接着考虑更为复杂的情况——研究带有功率控制、数据聚合和QoS要求的多约束条件下的生存时间优化问题。首先使用非线性规划对问题进行描述,然后给出一个遗传算法GAMSN。GAMSN算法以携带单位流速的源目的路径作为基因,以一组源自相同节点的基因组成染色体,并进而构成个体。染色体所含的基因数由对应源节点的数据产生速度决定,个体所含的染色体数由源节点数决定。染色体的长度决定了一个源节点所能用来进行流速均衡的单位路径数量,从而限制了算法所能达到的精度。因此设置参数PREC与源节点数据产生速度共同控制染色体的长度和算法求解的精度。GAMSN通过流速编码避免了个体突破能量约束的情况,可以实现精度可控的求解,并在实验中表现出了良好的性能。
然而基本的GAMSN算法在实际应用中存在个体多样性随精度提高而快速增大,导致随机产生的初始群体平均适应度下降,进而影响群体进化速度的问题。针对这一问题提出改进算法DCGA,即多样性可控的遗传算法。DCGA通过控制染色体所含的基因数量和基因种类实现多样性可控的递进求解。对比GAMSN,改进算法DCGA所能达到的求解精度明显提高。
和一类直接对规划问题进行近似求解的算法相比,DCGA算法的优势在于同样可以达到较高的近似度,但复杂度更低。和普通启发式算法相比,DCGA算法以较小的复杂度增幅换取了较大的近似度改进。更重要的是现有算法尚不能处理功率可控、延迟和吞吐率受限的多传感器网络上无穷或比例聚合条件下的数据汇集流生存时间优化问题,而DCGA算法则能较好地解决该问题。
在上述对生存时间优化问题研究的基础上,提出当无线传感器网络中的数据传输总量较小的时候,应该使用同步休眠调度作为生存时间优化的补充,以进一步提高网络的生存时间。特别地,针对带有数据聚合的无线传感器网络,生存时间优化只解决了流量或流速在链路上的分配问题,而没有解决流量的调度问题。而不佳的流量调度会影响系统的可休眠时间。我们对流量调度问题进行了建模,提出了一个基于关键路径的启发式算法PYTMS。实验表明PYTMS算法显著缩短了系统所需的活跃周期长度,从而降低了相应的空闲能耗,有利于延长网络的生存时间。
Wireless sensor network is considered a promising infrastructure to change the physical environment, and hence our life in this environment. It has been an active research area in the past few years. Wireless sensor networks are presumed to be deployed using battery-powered stationary sensor nodes equipped with sensing, computing and wireless communicating modules. In a broad range of potential applications, inexpensive sensors can be embedded into buildings or scattered into spaces to collect, process and send out relevant information for various civilian or military purposes.
Since sensors have significant power constraints, and the radio transceiver typically consumes more energy than any other hardware component onboard a sensor node, design of energy efficient communication algorithms is of great importance. For prolonging system lifetime by reducing the energy consumed by communications, various algorithms have been proposed. They can be categorized into two families: lifetime maximization and sleeping scheduling. Lifetime maximization problem focuses on how to balance the energy consumption of data transmission so that the system lifetime that the first“die-out”node lives could be prolonged as much as possible. However, sleeping scheduling focuses on how to force as many as possible nodes to go to sleep so that the energy consumed by idle listening could be conserved. A promising perspective on combining lifetime maximization and sleeping scheduling should be taken to prolong system lifetime.
The data flow in a sensor network is very different from data flow in an ordinary network, and therefore the common protocols used in the Internet or Manet paradigm are inadequate to handle. Such special data flow poses novel challenges and also chances in designing efficient routing algorithms in sensor networks. That is to perform global optimization in traffic planning to prolong system lifetime as much as possible.
We abstract a kind of multi-source-to-multi-sink communication lifetime maximization problem of non-power-controllable sensor networks into a kind of one-source-to-one-sink single-commodity flow maximization problem on a directed graph with arc and vertex capacities. Based on this model, three polynomial-time algorithms VABA, FAT and ADALM are presented to estimate whether a sensor network can live a given lifetime or not. Through binary search, these algorithms can find out the maximum lifetime and the best traffic planning under a given precision.
Precious sensor node battery power can be saved by power control measures that can dynamically adjust the radio transmission range of a sensor node. Therefore we extend VABA to I-VABA in order to handle the lifetime maximization problem of power-controllable sensor networks. In particular, a heuristic algorithm AOC is presented to perform circle flow adjustment when I-VABA is blocked so that additional flow augmentations could be achieved. Compared with other heuristic algorithms, AOC achieves a higher or a similar approximation ratio but uses a much fewer run time.
In sensor networks, the communication cost is often several orders of magnitude higher than the computation cost. So in-network data aggregation is considered an effective technique for energy conservation. In addition, QoS constraints are also important for providing congestion-free and latency-bounded data transmission service. We formulize such kind of lifetime maximization problem with considering data aggregation and QoS constraints as non-linear programming and propose a genetic algorithm GAMSN to solve it. GAMSN takes unit-flow-rate paths as genes and constructs a chromosome for each source node by a set of unit paths that originated from it. In particular, a parameter named“PREC”is set to serve the purpose of control the number of genes of a chromosome and hence the precision in which GAMSN could approximate the maximum lifetime. This approach has a reasonable time complexity and performs well in experiments.
However, a major drawback of GAMSN is the additional individual diversity overhead resulted from increased PREC. With the increase of individual diversity, much greater population size is needed to ensure that there are some good individuals in a randomly generated initial population. Therefore, the increase of individual diversity will adversely impact the algorithm effectiveness. We propose a diversity-controllable genetic algorithm DCGA as an improvement of GAMSN to address this problem. DCGA uses two methods to control the individual diversity. The first is to control the number of genes in a chromosome through parameter PREC. The second is to control the type of genes by limiting the hop counts of randomly generated unit paths. DCGA gains remarkable performance improvement under high PREC by diversity control.
Compared with a kind of algorithms which use multi-commodity approximate methods to solve programming problems, DCGA can also achieve a high approximation ratio but has lower time complexity. Compared with a kind of heuristic algorithms, DCGA achieves a higher approximation ratio with a little increased order of computations. To the best of our knowledge, GAMSN and it diversity-controllable improvement DCGA are the first algorithms that can solve multi-commodity lifetime maximization problems of power-controllable sensor networks with data aggregation and QoS constraints.
Synchronized periodic duty cycling of the sensor nodes is suggested to minimize the energy consumption of idle listening. Each node follows a periodic cycle of active/sleep radio states. During the sleep period, the radio is completely turned off, and during the active period, the radio is turned on and all generated data is send to the sink. So the important problem is to reduce the length of active period as much as possible. In sensor networks with data aggregation, an intermediate node must to wait for all incoming data to arrive before it can perform data aggregation and send the aggregated data to the downstream nodes. If an upstream node decides to send it outgoing data to another node firstly, the current node has to wait for it and put off its data aggregation and out sending. Consequently, all nodes that wait for incoming data from the current node have to put off their process as the same. Such kind of wait results in significant delay and prolong the time that is needed to send all data generated in a periodic of active/sleep cycle to the sink. Therefore it is very important to schedule the transmission order on each node to reduce the wait time and consequently the length of active period. We call this traffic scheduling and propose a heuristic algorithm named PYTMS based on the adjustments on critical paths. It can reduce the active period remarkably.
能源受限是无线传感器网络的一个突出特点。针对无线传感器网络的研究必须充分考虑节能性。节能的目标是延长网络的生存时间。由于通信能耗占传感器节点总能耗的绝大部分,设计节能的通信协议是延长无线传感器网络生存时间的一个重要途径。生存时间优化和休眠调度分别从不同角度对通信能耗进行了优化。其中,生存时间优化解决的是网络中有数据传输时如何均衡各节点能耗的问题,而休眠调度解决的是如何安排没有数据采集和传输任务的节点休眠以降低空闲能耗的问题。两者可以联合使用以提高网络的生存时间。
无线传感器网络中的主要流量是传感器节点到sink节点的数据汇集流。而且中间节点可能在传输过程中进行数据聚合,这和传统网络有很大不同。流量的汇集性特点为通信协议的设计提出了新的要求,同时也为生存时间的全局优化提供了机会。
生存时间优化就是在给定节点的初始能量、数据产生速度和链路传输代价等约束的情况下,寻求流量或流速在网络上的最佳分配方案以使网络生存时间最大化。根据是否考虑数据聚合、节点是否具有发射功率控制能力、是否考虑接收功耗、是否考虑多种物流、路由结构是否动态可变,以及所针对的通信类型和所采用的生存时间定义,生存时间优化有多种不同的问题模型和不同的求解难度。
本文首先针对发射功率不可控的单物流传感器网络上的单播生存时间优化问题从网络流的角度进行建模。把多到一或多到多的单物流无线传感器网络中,数据汇集流所引发的生存时间优化问题转化为点弧权网络上单源单汇的最大流问题。在对这一问题进行分析的基础上,给出两个复杂度不同的集中式算法VABA和FAT,以及一个分布式算法ADALM。它们都属于判定性算法,能够在多项式时间内判断一个传感器网络的最大生存时间能否达到给定的数值。使用判定性算法结合生存时间上限通过折半查找能够以所需精度逼近最大生存时间和最佳传输方案。
在此基础上把网络流模型扩展到发射功率可控的无线传感器网络上。将VABA扩展为I-VABA算法,并提出以圈流调整将不可增广的阻塞流转化为同等流量下的理想流以便进一步增广。据此提出基于圈流调整的启发式网络流算法AOC。比较其它启发式算法,AOC的近似度更高或基本持平,但运算时间却大大降低,对网络规模的扩展性更强。
接着考虑更为复杂的情况——研究带有功率控制、数据聚合和QoS要求的多约束条件下的生存时间优化问题。首先使用非线性规划对问题进行描述,然后给出一个遗传算法GAMSN。GAMSN算法以携带单位流速的源目的路径作为基因,以一组源自相同节点的基因组成染色体,并进而构成个体。染色体所含的基因数由对应源节点的数据产生速度决定,个体所含的染色体数由源节点数决定。染色体的长度决定了一个源节点所能用来进行流速均衡的单位路径数量,从而限制了算法所能达到的精度。因此设置参数PREC与源节点数据产生速度共同控制染色体的长度和算法求解的精度。GAMSN通过流速编码避免了个体突破能量约束的情况,可以实现精度可控的求解,并在实验中表现出了良好的性能。
然而基本的GAMSN算法在实际应用中存在个体多样性随精度提高而快速增大,导致随机产生的初始群体平均适应度下降,进而影响群体进化速度的问题。针对这一问题提出改进算法DCGA,即多样性可控的遗传算法。DCGA通过控制染色体所含的基因数量和基因种类实现多样性可控的递进求解。对比GAMSN,改进算法DCGA所能达到的求解精度明显提高。
和一类直接对规划问题进行近似求解的算法相比,DCGA算法的优势在于同样可以达到较高的近似度,但复杂度更低。和普通启发式算法相比,DCGA算法以较小的复杂度增幅换取了较大的近似度改进。更重要的是现有算法尚不能处理功率可控、延迟和吞吐率受限的多传感器网络上无穷或比例聚合条件下的数据汇集流生存时间优化问题,而DCGA算法则能较好地解决该问题。
在上述对生存时间优化问题研究的基础上,提出当无线传感器网络中的数据传输总量较小的时候,应该使用同步休眠调度作为生存时间优化的补充,以进一步提高网络的生存时间。特别地,针对带有数据聚合的无线传感器网络,生存时间优化只解决了流量或流速在链路上的分配问题,而没有解决流量的调度问题。而不佳的流量调度会影响系统的可休眠时间。我们对流量调度问题进行了建模,提出了一个基于关键路径的启发式算法PYTMS。实验表明PYTMS算法显著缩短了系统所需的活跃周期长度,从而降低了相应的空闲能耗,有利于延长网络的生存时间。
Wireless sensor network is considered a promising infrastructure to change the physical environment, and hence our life in this environment. It has been an active research area in the past few years. Wireless sensor networks are presumed to be deployed using battery-powered stationary sensor nodes equipped with sensing, computing and wireless communicating modules. In a broad range of potential applications, inexpensive sensors can be embedded into buildings or scattered into spaces to collect, process and send out relevant information for various civilian or military purposes.
Since sensors have significant power constraints, and the radio transceiver typically consumes more energy than any other hardware component onboard a sensor node, design of energy efficient communication algorithms is of great importance. For prolonging system lifetime by reducing the energy consumed by communications, various algorithms have been proposed. They can be categorized into two families: lifetime maximization and sleeping scheduling. Lifetime maximization problem focuses on how to balance the energy consumption of data transmission so that the system lifetime that the first“die-out”node lives could be prolonged as much as possible. However, sleeping scheduling focuses on how to force as many as possible nodes to go to sleep so that the energy consumed by idle listening could be conserved. A promising perspective on combining lifetime maximization and sleeping scheduling should be taken to prolong system lifetime.
The data flow in a sensor network is very different from data flow in an ordinary network, and therefore the common protocols used in the Internet or Manet paradigm are inadequate to handle. Such special data flow poses novel challenges and also chances in designing efficient routing algorithms in sensor networks. That is to perform global optimization in traffic planning to prolong system lifetime as much as possible.
We abstract a kind of multi-source-to-multi-sink communication lifetime maximization problem of non-power-controllable sensor networks into a kind of one-source-to-one-sink single-commodity flow maximization problem on a directed graph with arc and vertex capacities. Based on this model, three polynomial-time algorithms VABA, FAT and ADALM are presented to estimate whether a sensor network can live a given lifetime or not. Through binary search, these algorithms can find out the maximum lifetime and the best traffic planning under a given precision.
Precious sensor node battery power can be saved by power control measures that can dynamically adjust the radio transmission range of a sensor node. Therefore we extend VABA to I-VABA in order to handle the lifetime maximization problem of power-controllable sensor networks. In particular, a heuristic algorithm AOC is presented to perform circle flow adjustment when I-VABA is blocked so that additional flow augmentations could be achieved. Compared with other heuristic algorithms, AOC achieves a higher or a similar approximation ratio but uses a much fewer run time.
In sensor networks, the communication cost is often several orders of magnitude higher than the computation cost. So in-network data aggregation is considered an effective technique for energy conservation. In addition, QoS constraints are also important for providing congestion-free and latency-bounded data transmission service. We formulize such kind of lifetime maximization problem with considering data aggregation and QoS constraints as non-linear programming and propose a genetic algorithm GAMSN to solve it. GAMSN takes unit-flow-rate paths as genes and constructs a chromosome for each source node by a set of unit paths that originated from it. In particular, a parameter named“PREC”is set to serve the purpose of control the number of genes of a chromosome and hence the precision in which GAMSN could approximate the maximum lifetime. This approach has a reasonable time complexity and performs well in experiments.
However, a major drawback of GAMSN is the additional individual diversity overhead resulted from increased PREC. With the increase of individual diversity, much greater population size is needed to ensure that there are some good individuals in a randomly generated initial population. Therefore, the increase of individual diversity will adversely impact the algorithm effectiveness. We propose a diversity-controllable genetic algorithm DCGA as an improvement of GAMSN to address this problem. DCGA uses two methods to control the individual diversity. The first is to control the number of genes in a chromosome through parameter PREC. The second is to control the type of genes by limiting the hop counts of randomly generated unit paths. DCGA gains remarkable performance improvement under high PREC by diversity control.
Compared with a kind of algorithms which use multi-commodity approximate methods to solve programming problems, DCGA can also achieve a high approximation ratio but has lower time complexity. Compared with a kind of heuristic algorithms, DCGA achieves a higher approximation ratio with a little increased order of computations. To the best of our knowledge, GAMSN and it diversity-controllable improvement DCGA are the first algorithms that can solve multi-commodity lifetime maximization problems of power-controllable sensor networks with data aggregation and QoS constraints.
Synchronized periodic duty cycling of the sensor nodes is suggested to minimize the energy consumption of idle listening. Each node follows a periodic cycle of active/sleep radio states. During the sleep period, the radio is completely turned off, and during the active period, the radio is turned on and all generated data is send to the sink. So the important problem is to reduce the length of active period as much as possible. In sensor networks with data aggregation, an intermediate node must to wait for all incoming data to arrive before it can perform data aggregation and send the aggregated data to the downstream nodes. If an upstream node decides to send it outgoing data to another node firstly, the current node has to wait for it and put off its data aggregation and out sending. Consequently, all nodes that wait for incoming data from the current node have to put off their process as the same. Such kind of wait results in significant delay and prolong the time that is needed to send all data generated in a periodic of active/sleep cycle to the sink. Therefore it is very important to schedule the transmission order on each node to reduce the wait time and consequently the length of active period. We call this traffic scheduling and propose a heuristic algorithm named PYTMS based on the adjustments on critical paths. It can reduce the active period remarkably.
引文
[1] Liang S H L, Tao V, Croitoru A. The Design and Prototype of a Distributed Geospatial Infrastructure for Smart Sensor Webs [C]. in The 6th AGILE Conference on Geographic Information Science. Lyon, France, April 2003.
[2] Ouellette J. Electronic Noses Sniff Out New Markets [J]. The Indusrial Physicist, February1999: 26-29.
[3] Bonnet P, Gehrke J, Seshadri P. Querying the physical world [J]. IEEE Personal Communications, 2000, vol. 7(5): 10-15.
[4] Polastre J R, Culler D. Design and Implementation of Wireless Sensor Networks for Habitat Monitoring [D]: University of California at Berkeley, 2003.
[5] Berkowitz B. Technology catches up to runners [N]. Washington Post, April 20, 2001(E: 1).
[6] Schoeneman J L. Authenticated tracking and monitoring system (ATMS) tracking shipments from an Australian uranium mine [R]. Springfield, VA: National Technical Information Service, DE98007251, 1998.
[7] Chien S, Cichy B, Davies A, et al. An Autonomous Earth-Observing Sensorweb [C]. in IEEE Conference on Systems Man and Cybernetics. Big Island, HI, October 2005.
[8] http://research.cens.ucla.edu/.
[9] http://www.janet.ucla.edu/WINS/.
[10] http://bwrc.eecs.berkeley.edu.
[11] http://webs.cs.berkeley.edu/.
[12] http://www.robotics.usc.edu/?embedded/.
[13] http://www.isi.edu/scadds/.
[14] http://www.ece.gatech.edu/research/labs/bwn/index.html.
[15] http://www.cast.cse.ohio-state.edu/exscal/.
[16] http://www.wings.cs.sunysb.edu/.
[17] http://www.eecs.harvard.edu/?mdw/proj/codeblue/.
[18] http://mantis.cs.colorado.edu/index.php/tiki-index.php.
[19] http://www.eng.yale.edu/enalab/.
[20] http://nms.csail.mit.edu/.
[21] http://www-mtl.mit.edu/researchgroups/icsystems/uamps/.
[22] http://lion.cs.uiuc.edu/.
[23] http://projects.cerias.purdue.edu/esp/.
[24] http://www.zurich.ibm.com/sys/communication/sensors.html.
[25] http://www.intel.com/research/exploratory/wireless_sensors.htm.
[26] http://research.microsoft.com/nec/.
[27] http://www.xbow.com/Products/Wireless_Sensor_Networks.htm.
[28] http://bwrc.eecs.berkeley.edu/Research/Pico_Radio/Default.htm.
[29] http://nesl.ee.ucla.edu/projects/ahlos/.
[30] http://www.intel.com/research/exploratory/motes.htm.
[31] http://www.tinyos.net/.
[32] http://nesl.ee.ucla.edu/projects/sos/.
[33] 李建中, 李金宝, 石胜飞. 传感器网络及其数据管理的概念、问题与进展 [J]. 软件学报, 2003, vol. 14(10): 1717-1727.
[34] 任丰原, 黄海宁, 闯 林. 无线传感器网络 [J]. 软件学报, 2003, vol. 14(7): 1282-1291.
[35] 林亚平, 王雷, 陈宇 等. 传感器网络中一种分布式数据汇聚层次路由算法 [J]. 电子学报, 2004, vol. 32(11): 1801-1805.
[36] 张卿, 谢志鹏, 凌波 等. 一种传感器网络最大化生命周期数据收集算法 [J]. 软件学报, 2005, vol. 16(11): 1946-1957.
[37] 刘明, 龚海刚, 毛莺池 等. 高效节能的传感器网络数据收集和聚合协议 [J]. 软件学报, 2005, vol. 16(12): 2106-2116.
[38] 彭伟, 卢锡城. 一个新的分布式最小连通支配集近似算法 [J]. 计算机学报, 2001, vol. 24(3): 254-258.
[39] Peng W, Lu X. An Approach to Support IP Multicasting in Networks with Mobile Hosts [J]. Journal of Computer Science and Technology, November 1999, vol. 14(6): 529-538.
[40] Peng W, Lu X. AHBP: An Efficient Broadcast Protocol for Mobile Ad Hoc Networks [J]. Journal of Computer Science and Technology, March 2001, vol. 16(2): 114-125.
[41] Peng W, Lu X. Efficient Broadcast in Mobile Ad Hoc Networks Using Connected Dominating Sets [J]. Journal of Software, April 2001, vol. 12(4): 529-536.
[42] Peng W, Lu X. On the Reduction of Broadcast Redundancy in Mobile Ad Hoc Networks [C]. in MOBIHOC. Boston, Massachusetts, August 2000.
[43] 蒋杰, 方力, 张鹤颖 等. 无线传感器网络最小连通覆盖集问题求解算法 [J]. 软件学报, 2006, vol. 17(2): 175-184.
[44] 卿利, 朱清新, 王明文. 异构传感器网络的分布式能量有效成簇算法 [J]. 软件学报, 2006,3, vol. 17(3): 481-489.
[45] Kahn J M, Katz R H, Pister K S J. Next century challenges: Mobile networking for “smart dust” [C]. in MOBICOM. Seattle, Washington, USA, August 1999: 271-278.
[46] Pottie G J, Kaiser W J. Wireless Integrated Network Sensors [J]. Communications of the ACM, May 2000, vol. 43(5): 51-58
[47] Cardei M, Thai M T, Li Y, et al. Energy-Efficient Target Coverage in Wireless Sensor Networks [C]. in INFOCOM. Miami, USA, March 2005.
[48] Raghunathan V, Schurgers C, Park S, et al. Energy-aware Wireless Microsensor Networks [J]. IEEE Signal Processing Magazine, 2002(19): 40-50.
[49] Kalpakis K. Efficient Algorithms for Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks [J]. Computer Networks: The International Journal of Computer and Telecommunications Networking, August 2003, vol. 42(6): 697-716.
[50] Singh S, Woo M, Raghavendra C S. Power-Aware Routing in Mobile Ad Hoc Networks [C]. in Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking. Dallas, Texas, United States: ACM Press, 1998.
[51] Ramanathan R, Rosales-Hain R. Topology Control of Multihop Wireless Networks using Transmit Power Adjustment [C]. in INFOCOM. Tel Aviv, Israel: IEEE, March 2000: 404-413.
[52] Wieselthier J E, Nguyen G D, Ephremides A. On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks [C]. in INFOCOM. Tel Aviv, Israel: IEEE, March 2000: 585-594.
[53] Chen B, Jamieson K, Balakrishnan H, et al. Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks [C]. in MOBICOM. Rome, Italy, 2001: 85-96.
[54] Clementi A E F, Crescenzi P, Penna P, et al. On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs [C]. in STACS, 2001: 121-131.
[55] Wan P-J, Calinescu G, Li X, et al. Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks [C]. in INFOCOM. Anchorage, AK, April 2001: 1162-1171.
[56] Xu Y, Heidemann J S, Estrin D. Geography-informed Energy Conservation for Ad Hoc Routing [C]. in MOBICOM. Rome, Italy, 2001: 70-84.
[57] Calinescu G, Mandoiu I I, Zelikovsky A. Symmetric Connectivity With Minimum Power Consumption in Radio Networks [C]. in TCS, August 2002: 119-130.
[58] Liang W. Constructing Minimum-Energy Broadcast Trees in Wireless Ad Hoc Networks [C]. in MobiHoc. Lausanne, Switzerland: ACM Press, June 2002: 112--122.
[59] Lloyd E L, Liu R, Marathe M V, et al. Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks [C]. in MobiHoc Lausanne, Switzerland: ACM Press, June 2002: 123-134.
[60] Das A K. Minimum power broadcast trees for wireless networks: Integer programming formulations [C]. in INFOCOM. San Franciso, CA, USA: IEEE,April 2003: 1001-1010
[61] Cartigny J, Simplot D, Stojmenovi′c I. Localized minimum-energy broadcasting in ad-hoc networks [C]. in INFOCOM. San Franciso,CA,USA: IEEE, April 2003: 2210-2217.
[62] Chang J-H, Tassiulas L. Energy Conserving Routing in Wireless Ad Hoc Networks [C]. in INFOCOM. Tel Aviv, Israel: IEEE, March 2000: 22-31.
[63] Chang J-H, Tassiulas L. Fast approximate algorithms for maximum lifetime routing in wireless ad-hoc networks [C]. in NETWORKING: Springer-Verlag, 2000: 702-713.
[64] Chang J-H, L.Tassiulas. Routing for Maximum System Lifetime in Wireless Ad-hoc Networks [C]. in 37th Annual Allerton Conference on Communication, Control, and Computing. Monticello, IL, September 1999.
[65] Das A K, Marks R J, El-Sharkawi M, et al. Mdlt: A Polynomial Time Optimal Algorithm for Maximization of Time To-First-Failure in Energy Constrained Wireless Broadcast Networks [C]. in GLOBECOM. San Francisco,California,USA: IEEE, December 2003: 362-366.
[66] Kang I, Poovendran R. Maximizing Static Network Lifetime of Wireless Broadcast Adhoc Networks [C]. in ICC. Alska: IEEE, May 2003: 2256-2261.
[67] Das A K, El-Sharkawi M, Marks R J, et al. Maximization of time-to-first-failure for multicasting in wireless networks: Optimal solution [C]. in MILCOM. Seattle: IEEE, October 2004: 1358-1363.
[68] Floréen P, Kaski P, Kohonen J, et al. Lifetime Maximization for Multicasting in Energy-Constrained Wireless Networks [J]. IEEE Journal on Selected Areas in Communications, January 2005, vol. 23(1): 117-126.
[69] Santi P, Blough D M, Vainstein F. A probabilistic analysis for the range assignment problem in ad hoc networks [C]. in MobiHoc. Long Beach, California, USA, October 2001: 212-220.
[70] Ephremides A. Energy concerns in wireless networks [J]. IEEE Wireless Communications, Augest 2002, vol. 9(4): 48-59.
[71] Wattenhofer R, Li L, Bahl P, et al. Distributed topology control for wireless multihop ad hoc networks [C]. in INFOCOM. Anchorage, AK: IEEE, April 2001: 1388-1397.
[72] Wieselthier J E, Nguyen G D, Ephremides A. Resource management in energy-limited, bandwidth-limited, transceiver-limited wireless networks for session-based multicasting [J]. Computer Networks, June 2002, vol. 39(2): 113-131.
[73] Toh C-K. Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks [J]. IEEE Communications Magazine, June 2001: 138-147.
[74] Brown T X, Gabow H N, Zhang Q. Maximum Flow-Life Curve for a Wireless Ad Hoc Network [C]. in MobiHoc. Long Beach, California, USA, 2001: 128-136.
[75] Bhardwaj M, Garnett T, Chandrakasan A P. Upper Bounds on the Lifetime of Sensor Networks [C]. in ICC. Helsinki, Finland, June 2001: 785-790.
[76] Guo S, Leung V, Yang O. A scalable distributed multicast algorithm for lifetime maximization in large-scale resource-limited multihop wireless networks [C]. in Proceeding of the 2006 international conference on Communications and mobile computing. Vancouver, British Columbia, Canada: ACM Press, July 2006: 419-424.
[77] Guo S, Yang O. Performance of distributed algorithms for maximizing multicast lifetime in mobile ad hoc networks [C]. in Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks. Montreal, Quebec, Canada: ACM Press, 2005: 152-159.
[78] Wang B, Gupta S K S. On Maximizing Lifetime of Multicast Trees in Wireless Ad hoc Networks [C]. in ICPP, 2003: 333-340.
[79] Cagalj M, Hubaux J, Enz C. Minimum-Energy Broadcast in All Wireless Networks: Np-Completeness and Distribution Issues [C]. in MobiCOM. Atlanta, Georgia: ACM Press, September 2002: 172-182
[80] Guo X. Broadcasting for Network Lifetime Maximization in Wireless Sensor Networks [C]. in SECON. Santa Clara, CA: IEEE, October 2004.
[81] Kang I, Poovendran R. Maximizing Network Lifetime of Broadcasting Over Wireless Stationary Ad Hoc Networks [J]. ACM MONET, 2005, vol. 10(6): 879-896.
[82] Chang J, Tassiulas L. Maximum Lifetime Routing In Wireless Sensor Networks [J]. IEEE/ACM Transactions on Networking August 2004, vol. 12(4): 609-619.
[83] Sankar A, Liu Z. Maximum Lifetime Routing in Wireless Ad-hoc Networks [C]. in INFOCOM. Hong Kong: IEEE, March 2004: 1089-1097.
[84] XUE Y, CUI Y, NAHRSTEDT K. Maximizing Lifetime for Data Aggregation in Wireless Sensor Networks [J]. ACM/Kluwer Mobile Networks and Applications, 2005, vol. 10(6): 853-864.
[85] Kalpakis K, Dasgupta K, Namjoshi P. Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks [R]. Baltimore, Maryland: University of Maryland Baltimore County, TR CS-02-12, August 2002.
[86] Hua C, Yum T-S P. Optimal Routing for Maximizing Lifetime of Wireless Sensor Networks [C]. in INFOCOM. Miami, USA: IEEE, March 2005.
[87] Alonso J, Dunkels A, Voigt T. Bounds on the energy consumption of routings in wireless sensor networks [C]. in the 2nd WiOpt, Modeling and Optimization in Mobile, Ad Hoc and Wireless Network. Cambridge, UK, March 2004.
[88] Giridhar A, Kumar P R. Maximizing the Functional Lifetime of Sensor Networks [C]. in IPSN. Los Angeles, California IEEE, 2005: 5-12.
[89] Dasgupta K, Kukreja M, Kalpakis K. Topology-Aware Placement and Role Assignment for Energy-Efficient Information Gathering in Sensor Networks [C]. in IEEE Symposium on Computers and Communications (ISCC'03).Kiris-Kemer, Turkey: IEEE, June 2003: 341-348.
[90] Dong Q. Maximizing system lifetime in wireless sensor networks [C]. in IPSN. Los Angeles, California IEEE, 2005: 13-19.
[91] Heinzelman W. Application-Specific Protocol Architectures for Wireless Networks [D]: Massachusetts Institute of Technology, 2000.
[92] Wang A, Heinzelman W, Chandrakasan A. Energy-scalable protocols for battery-operated microsensor networks [C]. in IEEE Workshop on Signal Processing Systems: IEEE, 1999: 483-492.
[93] Cristescu R a, Beferull-Lozano B, Vetterli M. On Network Correlated Data Gathering [C]. in INFOCOM. Hong Kong: IEEE, March 2004: 218-224.
[94] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks [C]. in the 33rd Hawaii International Conference on System Sciences, January 2000: 10.
[95] Heinzelman W R, Chandrakasan A, Balakrishnan H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks [J]. IEEE Transactions on Wireless Communications, October 2002, vol. 1(4): 660-670.
[96] Lindsey S, Raghavendra C. PEGASIS: Power-efficient gathering in sensor information systems [C]. in IEEE Aerospace Conference: IEEE, March 2002: 1125-1130.
[97] Wong J, Jafari R, Potkonjak M. Gateway placement for latency and energy efficient data aggregation [C]. in the 29th Annual IEEE International Conference on Local Computer Networks: IEEE, November 2004: 490-497.
[98] Zhang W, Cao G. DCTC: Dynamic Convoy Tree-based Collaboration for Target Tracking in Sensor Networks [J]. IEEE Transactions on Wireless Communications, September 2004, vol. 3: 1689-1701.
[99] Zhang W, Cao G. Optimizing Tree Reconfiguration for Mobile Target Tracking in Sensor Networks [C]. in INFOCOM. Hong Kong: IEEE, March 2004.
[100] Intanagonwiwat C, Estrin D, Goviindan R. Impact of Network Density on Data Aggregation in Wireless Sensor Networks [R]: University of Southern California, November 2001.
[101] Zhao Q, Mohan G. Topology knowledge range control for lifetime maximization in sensor networks with data aggregation [C]. in the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks. Montreal, Quebec, Canada: ACM Press, 2005: 84-91.
[102] Dasgupta K, Kalpakis K, Namjoshi P. An Efficient Clustering-based Heuristic for Data Gathering and Aggregation in Sensor Networks [C]. in WCNC. New Orleans, Louisiana: IEEE, March 2003: 16-20
[103] Garg N, Konemann J. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems [C]. in IEEE Symposium on Found. of Comp. Science, 1998: 300-309.
[104] Awerbuch B, Leighton F T. A simple local-control approximation algorithm for multicommodity flow [C]. in IEEE Symposium on Foundations of ComputerScience, 1993: 459-468.
[105] Awerbuch B, Leighton F T. Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks [C]. in ACM Symposium on Theory of Computing, 1994: 487-496.
[106] Perillo M, Cheng Z, Heinzelman W. On the Problem of Unbalanced Load Distribution in Wireless Sensor Networks [C]. in GLOBECOM: IEEE, November 2004: 74-79.
[107] Olariu S, Stojmenovi′c I. Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting [C]. in INFOCOM. Barcelona Spain: IEEE, 2006: 1587-1596.
[108] Madan R, Lall S. Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Networks [C]. in Globecom. Dallas: IEEE, November 2004: 748-753.
[109] Shor N Z. Minimization Methods for Non-differentiable Functions [M]: Springer-Verlag, 1985.
[110] Bhardwaj M, Chandrakasan A P. Bounding the Lifetime of Sensor Networks Via Optimal Role Assignments [C]. in INFOCOM. New York, USA: IEEE, 2002.
[111] Rai V, Mahapatra R N. Lifetime Modeling of a Sensor Network [C]. in Design, Automation and Test in Europe (DATA'05). Munich, Germany: IEEE Computer Society, March 2005: 202-203.
[112] Duarte-Melo E J, Liu M, Misra A. A Modeling Framework for Computing Lifetime and Information Capacity in Wireless Sensor Networks [C]. in Ad Hoc and Wireless Networks. Cambridge, UK, March 2004.
[113] Guo S, Yang O. A Dynamic Multicast Tree Reconstruction Algorithm for Minimum-Energy Multicasting in Wireless Ad Hoc Networks [C]. in IPCCC. Phoenix, USA: IEEE, April 2004: 637-642.
[114] Li F, Nikolaidis I. On minimum-energy broadcasting in all-wireless networks [C]. in LCN. Tampa: IEEE, November 2001: 14-16.
[115] Wieselthier J E, Nguyen G D, Ephremides A. Algorithms for energy-efficient multicasting in static ad hoc wireless networks [J]. ACM MONET, June 2001, vol. 6(3): 251-263.
[116] Cagalj M, Hubaux J-P, Enz C. Minimum-energy broadcast in all-wireless networks: NP completeness and distribution issues [C]. in Mobicom. Atlanta, Georgia, USA: ACM Press, 2002: 172-182.
[117] Cheng M X, Sun J. Energy-efficient Broadcast and Multicast Routing in Ad Hoc Wireless Networks [C]. in IPCCC. Phoenix, Arizona: IEEE, April 2003: 87-94.
[118] Floréen B, Kaski P. Multicast time maximization in energy constrained wireless networks [C]. in Workshop on Foundations of Mobile Computing. New York, NY, 2003: 50-58.
[119] Guo S, Yang O. Multicast Lifetime Maximization for Energy-Constrained Wireless Ad-hoc Networks with Directional Antennas [C]. in Globecom. Dallas,USA: IEEE, December 2004: 4120-4124.
[120] II R J M, Das A K, El-Sharkawi M. Maximizing Lifetime in an Energy Constrained Wireless Sensor Array Using Team Optimization of Cooperating Systems [C]. in Proceedings of the World Congress on Computational Intelligence. Honolulu, Hawaii: IEEE, 2002.
[121] 卢开澄, 卢华明. 图论及其应用 [M]. 北京: 清华大学社出版社, 1995.
[122] Malhotra V M, Kumar M P, Maheshwari S N. An O(|V|3) algorithm for find-ing maximum flows in networks [J]. Information Processing Letters, 1978(7): 277-278.
[123] Goldberg A V, Tarjan R E. A new approach to the maximum-flow problem [J]. Journal of ACM, 1988, vol. 35(4): 921-940.
[124] Pham T L, Bui M, Lavallae I, et al. A Distributed Preflow-Push for the Maximum Flow Problem [C]. in 5th International Workshop. Paris, France, June, 2005.
[125] 刘家壮, 徐源. 网络最优化 [M]. 北京: 高等教育出版社, 1991.8.
[126] Mainwaring A, Polastre J, Szewczyk R, et al. Wireless Sensor Networks for Habitat Monitoring [C]. in ACM International Workshop on Wireless Sensor Networks and Applications, 2002.
[127] 王凌. 智能优化算法及其应用 [M]. 北京: 清华大学出版社, 2001.10. 230p.
[2] Ouellette J. Electronic Noses Sniff Out New Markets [J]. The Indusrial Physicist, February1999: 26-29.
[3] Bonnet P, Gehrke J, Seshadri P. Querying the physical world [J]. IEEE Personal Communications, 2000, vol. 7(5): 10-15.
[4] Polastre J R, Culler D. Design and Implementation of Wireless Sensor Networks for Habitat Monitoring [D]: University of California at Berkeley, 2003.
[5] Berkowitz B. Technology catches up to runners [N]. Washington Post, April 20, 2001(E: 1).
[6] Schoeneman J L. Authenticated tracking and monitoring system (ATMS) tracking shipments from an Australian uranium mine [R]. Springfield, VA: National Technical Information Service, DE98007251, 1998.
[7] Chien S, Cichy B, Davies A, et al. An Autonomous Earth-Observing Sensorweb [C]. in IEEE Conference on Systems Man and Cybernetics. Big Island, HI, October 2005.
[8] http://research.cens.ucla.edu/.
[9] http://www.janet.ucla.edu/WINS/.
[10] http://bwrc.eecs.berkeley.edu.
[11] http://webs.cs.berkeley.edu/.
[12] http://www.robotics.usc.edu/?embedded/.
[13] http://www.isi.edu/scadds/.
[14] http://www.ece.gatech.edu/research/labs/bwn/index.html.
[15] http://www.cast.cse.ohio-state.edu/exscal/.
[16] http://www.wings.cs.sunysb.edu/.
[17] http://www.eecs.harvard.edu/?mdw/proj/codeblue/.
[18] http://mantis.cs.colorado.edu/index.php/tiki-index.php.
[19] http://www.eng.yale.edu/enalab/.
[20] http://nms.csail.mit.edu/.
[21] http://www-mtl.mit.edu/researchgroups/icsystems/uamps/.
[22] http://lion.cs.uiuc.edu/.
[23] http://projects.cerias.purdue.edu/esp/.
[24] http://www.zurich.ibm.com/sys/communication/sensors.html.
[25] http://www.intel.com/research/exploratory/wireless_sensors.htm.
[26] http://research.microsoft.com/nec/.
[27] http://www.xbow.com/Products/Wireless_Sensor_Networks.htm.
[28] http://bwrc.eecs.berkeley.edu/Research/Pico_Radio/Default.htm.
[29] http://nesl.ee.ucla.edu/projects/ahlos/.
[30] http://www.intel.com/research/exploratory/motes.htm.
[31] http://www.tinyos.net/.
[32] http://nesl.ee.ucla.edu/projects/sos/.
[33] 李建中, 李金宝, 石胜飞. 传感器网络及其数据管理的概念、问题与进展 [J]. 软件学报, 2003, vol. 14(10): 1717-1727.
[34] 任丰原, 黄海宁, 闯 林. 无线传感器网络 [J]. 软件学报, 2003, vol. 14(7): 1282-1291.
[35] 林亚平, 王雷, 陈宇 等. 传感器网络中一种分布式数据汇聚层次路由算法 [J]. 电子学报, 2004, vol. 32(11): 1801-1805.
[36] 张卿, 谢志鹏, 凌波 等. 一种传感器网络最大化生命周期数据收集算法 [J]. 软件学报, 2005, vol. 16(11): 1946-1957.
[37] 刘明, 龚海刚, 毛莺池 等. 高效节能的传感器网络数据收集和聚合协议 [J]. 软件学报, 2005, vol. 16(12): 2106-2116.
[38] 彭伟, 卢锡城. 一个新的分布式最小连通支配集近似算法 [J]. 计算机学报, 2001, vol. 24(3): 254-258.
[39] Peng W, Lu X. An Approach to Support IP Multicasting in Networks with Mobile Hosts [J]. Journal of Computer Science and Technology, November 1999, vol. 14(6): 529-538.
[40] Peng W, Lu X. AHBP: An Efficient Broadcast Protocol for Mobile Ad Hoc Networks [J]. Journal of Computer Science and Technology, March 2001, vol. 16(2): 114-125.
[41] Peng W, Lu X. Efficient Broadcast in Mobile Ad Hoc Networks Using Connected Dominating Sets [J]. Journal of Software, April 2001, vol. 12(4): 529-536.
[42] Peng W, Lu X. On the Reduction of Broadcast Redundancy in Mobile Ad Hoc Networks [C]. in MOBIHOC. Boston, Massachusetts, August 2000.
[43] 蒋杰, 方力, 张鹤颖 等. 无线传感器网络最小连通覆盖集问题求解算法 [J]. 软件学报, 2006, vol. 17(2): 175-184.
[44] 卿利, 朱清新, 王明文. 异构传感器网络的分布式能量有效成簇算法 [J]. 软件学报, 2006,3, vol. 17(3): 481-489.
[45] Kahn J M, Katz R H, Pister K S J. Next century challenges: Mobile networking for “smart dust” [C]. in MOBICOM. Seattle, Washington, USA, August 1999: 271-278.
[46] Pottie G J, Kaiser W J. Wireless Integrated Network Sensors [J]. Communications of the ACM, May 2000, vol. 43(5): 51-58
[47] Cardei M, Thai M T, Li Y, et al. Energy-Efficient Target Coverage in Wireless Sensor Networks [C]. in INFOCOM. Miami, USA, March 2005.
[48] Raghunathan V, Schurgers C, Park S, et al. Energy-aware Wireless Microsensor Networks [J]. IEEE Signal Processing Magazine, 2002(19): 40-50.
[49] Kalpakis K. Efficient Algorithms for Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks [J]. Computer Networks: The International Journal of Computer and Telecommunications Networking, August 2003, vol. 42(6): 697-716.
[50] Singh S, Woo M, Raghavendra C S. Power-Aware Routing in Mobile Ad Hoc Networks [C]. in Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking. Dallas, Texas, United States: ACM Press, 1998.
[51] Ramanathan R, Rosales-Hain R. Topology Control of Multihop Wireless Networks using Transmit Power Adjustment [C]. in INFOCOM. Tel Aviv, Israel: IEEE, March 2000: 404-413.
[52] Wieselthier J E, Nguyen G D, Ephremides A. On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks [C]. in INFOCOM. Tel Aviv, Israel: IEEE, March 2000: 585-594.
[53] Chen B, Jamieson K, Balakrishnan H, et al. Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks [C]. in MOBICOM. Rome, Italy, 2001: 85-96.
[54] Clementi A E F, Crescenzi P, Penna P, et al. On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs [C]. in STACS, 2001: 121-131.
[55] Wan P-J, Calinescu G, Li X, et al. Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks [C]. in INFOCOM. Anchorage, AK, April 2001: 1162-1171.
[56] Xu Y, Heidemann J S, Estrin D. Geography-informed Energy Conservation for Ad Hoc Routing [C]. in MOBICOM. Rome, Italy, 2001: 70-84.
[57] Calinescu G, Mandoiu I I, Zelikovsky A. Symmetric Connectivity With Minimum Power Consumption in Radio Networks [C]. in TCS, August 2002: 119-130.
[58] Liang W. Constructing Minimum-Energy Broadcast Trees in Wireless Ad Hoc Networks [C]. in MobiHoc. Lausanne, Switzerland: ACM Press, June 2002: 112--122.
[59] Lloyd E L, Liu R, Marathe M V, et al. Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks [C]. in MobiHoc Lausanne, Switzerland: ACM Press, June 2002: 123-134.
[60] Das A K. Minimum power broadcast trees for wireless networks: Integer programming formulations [C]. in INFOCOM. San Franciso, CA, USA: IEEE,April 2003: 1001-1010
[61] Cartigny J, Simplot D, Stojmenovi′c I. Localized minimum-energy broadcasting in ad-hoc networks [C]. in INFOCOM. San Franciso,CA,USA: IEEE, April 2003: 2210-2217.
[62] Chang J-H, Tassiulas L. Energy Conserving Routing in Wireless Ad Hoc Networks [C]. in INFOCOM. Tel Aviv, Israel: IEEE, March 2000: 22-31.
[63] Chang J-H, Tassiulas L. Fast approximate algorithms for maximum lifetime routing in wireless ad-hoc networks [C]. in NETWORKING: Springer-Verlag, 2000: 702-713.
[64] Chang J-H, L.Tassiulas. Routing for Maximum System Lifetime in Wireless Ad-hoc Networks [C]. in 37th Annual Allerton Conference on Communication, Control, and Computing. Monticello, IL, September 1999.
[65] Das A K, Marks R J, El-Sharkawi M, et al. Mdlt: A Polynomial Time Optimal Algorithm for Maximization of Time To-First-Failure in Energy Constrained Wireless Broadcast Networks [C]. in GLOBECOM. San Francisco,California,USA: IEEE, December 2003: 362-366.
[66] Kang I, Poovendran R. Maximizing Static Network Lifetime of Wireless Broadcast Adhoc Networks [C]. in ICC. Alska: IEEE, May 2003: 2256-2261.
[67] Das A K, El-Sharkawi M, Marks R J, et al. Maximization of time-to-first-failure for multicasting in wireless networks: Optimal solution [C]. in MILCOM. Seattle: IEEE, October 2004: 1358-1363.
[68] Floréen P, Kaski P, Kohonen J, et al. Lifetime Maximization for Multicasting in Energy-Constrained Wireless Networks [J]. IEEE Journal on Selected Areas in Communications, January 2005, vol. 23(1): 117-126.
[69] Santi P, Blough D M, Vainstein F. A probabilistic analysis for the range assignment problem in ad hoc networks [C]. in MobiHoc. Long Beach, California, USA, October 2001: 212-220.
[70] Ephremides A. Energy concerns in wireless networks [J]. IEEE Wireless Communications, Augest 2002, vol. 9(4): 48-59.
[71] Wattenhofer R, Li L, Bahl P, et al. Distributed topology control for wireless multihop ad hoc networks [C]. in INFOCOM. Anchorage, AK: IEEE, April 2001: 1388-1397.
[72] Wieselthier J E, Nguyen G D, Ephremides A. Resource management in energy-limited, bandwidth-limited, transceiver-limited wireless networks for session-based multicasting [J]. Computer Networks, June 2002, vol. 39(2): 113-131.
[73] Toh C-K. Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks [J]. IEEE Communications Magazine, June 2001: 138-147.
[74] Brown T X, Gabow H N, Zhang Q. Maximum Flow-Life Curve for a Wireless Ad Hoc Network [C]. in MobiHoc. Long Beach, California, USA, 2001: 128-136.
[75] Bhardwaj M, Garnett T, Chandrakasan A P. Upper Bounds on the Lifetime of Sensor Networks [C]. in ICC. Helsinki, Finland, June 2001: 785-790.
[76] Guo S, Leung V, Yang O. A scalable distributed multicast algorithm for lifetime maximization in large-scale resource-limited multihop wireless networks [C]. in Proceeding of the 2006 international conference on Communications and mobile computing. Vancouver, British Columbia, Canada: ACM Press, July 2006: 419-424.
[77] Guo S, Yang O. Performance of distributed algorithms for maximizing multicast lifetime in mobile ad hoc networks [C]. in Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks. Montreal, Quebec, Canada: ACM Press, 2005: 152-159.
[78] Wang B, Gupta S K S. On Maximizing Lifetime of Multicast Trees in Wireless Ad hoc Networks [C]. in ICPP, 2003: 333-340.
[79] Cagalj M, Hubaux J, Enz C. Minimum-Energy Broadcast in All Wireless Networks: Np-Completeness and Distribution Issues [C]. in MobiCOM. Atlanta, Georgia: ACM Press, September 2002: 172-182
[80] Guo X. Broadcasting for Network Lifetime Maximization in Wireless Sensor Networks [C]. in SECON. Santa Clara, CA: IEEE, October 2004.
[81] Kang I, Poovendran R. Maximizing Network Lifetime of Broadcasting Over Wireless Stationary Ad Hoc Networks [J]. ACM MONET, 2005, vol. 10(6): 879-896.
[82] Chang J, Tassiulas L. Maximum Lifetime Routing In Wireless Sensor Networks [J]. IEEE/ACM Transactions on Networking August 2004, vol. 12(4): 609-619.
[83] Sankar A, Liu Z. Maximum Lifetime Routing in Wireless Ad-hoc Networks [C]. in INFOCOM. Hong Kong: IEEE, March 2004: 1089-1097.
[84] XUE Y, CUI Y, NAHRSTEDT K. Maximizing Lifetime for Data Aggregation in Wireless Sensor Networks [J]. ACM/Kluwer Mobile Networks and Applications, 2005, vol. 10(6): 853-864.
[85] Kalpakis K, Dasgupta K, Namjoshi P. Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks [R]. Baltimore, Maryland: University of Maryland Baltimore County, TR CS-02-12, August 2002.
[86] Hua C, Yum T-S P. Optimal Routing for Maximizing Lifetime of Wireless Sensor Networks [C]. in INFOCOM. Miami, USA: IEEE, March 2005.
[87] Alonso J, Dunkels A, Voigt T. Bounds on the energy consumption of routings in wireless sensor networks [C]. in the 2nd WiOpt, Modeling and Optimization in Mobile, Ad Hoc and Wireless Network. Cambridge, UK, March 2004.
[88] Giridhar A, Kumar P R. Maximizing the Functional Lifetime of Sensor Networks [C]. in IPSN. Los Angeles, California IEEE, 2005: 5-12.
[89] Dasgupta K, Kukreja M, Kalpakis K. Topology-Aware Placement and Role Assignment for Energy-Efficient Information Gathering in Sensor Networks [C]. in IEEE Symposium on Computers and Communications (ISCC'03).Kiris-Kemer, Turkey: IEEE, June 2003: 341-348.
[90] Dong Q. Maximizing system lifetime in wireless sensor networks [C]. in IPSN. Los Angeles, California IEEE, 2005: 13-19.
[91] Heinzelman W. Application-Specific Protocol Architectures for Wireless Networks [D]: Massachusetts Institute of Technology, 2000.
[92] Wang A, Heinzelman W, Chandrakasan A. Energy-scalable protocols for battery-operated microsensor networks [C]. in IEEE Workshop on Signal Processing Systems: IEEE, 1999: 483-492.
[93] Cristescu R a, Beferull-Lozano B, Vetterli M. On Network Correlated Data Gathering [C]. in INFOCOM. Hong Kong: IEEE, March 2004: 218-224.
[94] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks [C]. in the 33rd Hawaii International Conference on System Sciences, January 2000: 10.
[95] Heinzelman W R, Chandrakasan A, Balakrishnan H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks [J]. IEEE Transactions on Wireless Communications, October 2002, vol. 1(4): 660-670.
[96] Lindsey S, Raghavendra C. PEGASIS: Power-efficient gathering in sensor information systems [C]. in IEEE Aerospace Conference: IEEE, March 2002: 1125-1130.
[97] Wong J, Jafari R, Potkonjak M. Gateway placement for latency and energy efficient data aggregation [C]. in the 29th Annual IEEE International Conference on Local Computer Networks: IEEE, November 2004: 490-497.
[98] Zhang W, Cao G. DCTC: Dynamic Convoy Tree-based Collaboration for Target Tracking in Sensor Networks [J]. IEEE Transactions on Wireless Communications, September 2004, vol. 3: 1689-1701.
[99] Zhang W, Cao G. Optimizing Tree Reconfiguration for Mobile Target Tracking in Sensor Networks [C]. in INFOCOM. Hong Kong: IEEE, March 2004.
[100] Intanagonwiwat C, Estrin D, Goviindan R. Impact of Network Density on Data Aggregation in Wireless Sensor Networks [R]: University of Southern California, November 2001.
[101] Zhao Q, Mohan G. Topology knowledge range control for lifetime maximization in sensor networks with data aggregation [C]. in the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks. Montreal, Quebec, Canada: ACM Press, 2005: 84-91.
[102] Dasgupta K, Kalpakis K, Namjoshi P. An Efficient Clustering-based Heuristic for Data Gathering and Aggregation in Sensor Networks [C]. in WCNC. New Orleans, Louisiana: IEEE, March 2003: 16-20
[103] Garg N, Konemann J. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems [C]. in IEEE Symposium on Found. of Comp. Science, 1998: 300-309.
[104] Awerbuch B, Leighton F T. A simple local-control approximation algorithm for multicommodity flow [C]. in IEEE Symposium on Foundations of ComputerScience, 1993: 459-468.
[105] Awerbuch B, Leighton F T. Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks [C]. in ACM Symposium on Theory of Computing, 1994: 487-496.
[106] Perillo M, Cheng Z, Heinzelman W. On the Problem of Unbalanced Load Distribution in Wireless Sensor Networks [C]. in GLOBECOM: IEEE, November 2004: 74-79.
[107] Olariu S, Stojmenovi′c I. Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting [C]. in INFOCOM. Barcelona Spain: IEEE, 2006: 1587-1596.
[108] Madan R, Lall S. Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Networks [C]. in Globecom. Dallas: IEEE, November 2004: 748-753.
[109] Shor N Z. Minimization Methods for Non-differentiable Functions [M]: Springer-Verlag, 1985.
[110] Bhardwaj M, Chandrakasan A P. Bounding the Lifetime of Sensor Networks Via Optimal Role Assignments [C]. in INFOCOM. New York, USA: IEEE, 2002.
[111] Rai V, Mahapatra R N. Lifetime Modeling of a Sensor Network [C]. in Design, Automation and Test in Europe (DATA'05). Munich, Germany: IEEE Computer Society, March 2005: 202-203.
[112] Duarte-Melo E J, Liu M, Misra A. A Modeling Framework for Computing Lifetime and Information Capacity in Wireless Sensor Networks [C]. in Ad Hoc and Wireless Networks. Cambridge, UK, March 2004.
[113] Guo S, Yang O. A Dynamic Multicast Tree Reconstruction Algorithm for Minimum-Energy Multicasting in Wireless Ad Hoc Networks [C]. in IPCCC. Phoenix, USA: IEEE, April 2004: 637-642.
[114] Li F, Nikolaidis I. On minimum-energy broadcasting in all-wireless networks [C]. in LCN. Tampa: IEEE, November 2001: 14-16.
[115] Wieselthier J E, Nguyen G D, Ephremides A. Algorithms for energy-efficient multicasting in static ad hoc wireless networks [J]. ACM MONET, June 2001, vol. 6(3): 251-263.
[116] Cagalj M, Hubaux J-P, Enz C. Minimum-energy broadcast in all-wireless networks: NP completeness and distribution issues [C]. in Mobicom. Atlanta, Georgia, USA: ACM Press, 2002: 172-182.
[117] Cheng M X, Sun J. Energy-efficient Broadcast and Multicast Routing in Ad Hoc Wireless Networks [C]. in IPCCC. Phoenix, Arizona: IEEE, April 2003: 87-94.
[118] Floréen B, Kaski P. Multicast time maximization in energy constrained wireless networks [C]. in Workshop on Foundations of Mobile Computing. New York, NY, 2003: 50-58.
[119] Guo S, Yang O. Multicast Lifetime Maximization for Energy-Constrained Wireless Ad-hoc Networks with Directional Antennas [C]. in Globecom. Dallas,USA: IEEE, December 2004: 4120-4124.
[120] II R J M, Das A K, El-Sharkawi M. Maximizing Lifetime in an Energy Constrained Wireless Sensor Array Using Team Optimization of Cooperating Systems [C]. in Proceedings of the World Congress on Computational Intelligence. Honolulu, Hawaii: IEEE, 2002.
[121] 卢开澄, 卢华明. 图论及其应用 [M]. 北京: 清华大学社出版社, 1995.
[122] Malhotra V M, Kumar M P, Maheshwari S N. An O(|V|3) algorithm for find-ing maximum flows in networks [J]. Information Processing Letters, 1978(7): 277-278.
[123] Goldberg A V, Tarjan R E. A new approach to the maximum-flow problem [J]. Journal of ACM, 1988, vol. 35(4): 921-940.
[124] Pham T L, Bui M, Lavallae I, et al. A Distributed Preflow-Push for the Maximum Flow Problem [C]. in 5th International Workshop. Paris, France, June, 2005.
[125] 刘家壮, 徐源. 网络最优化 [M]. 北京: 高等教育出版社, 1991.8.
[126] Mainwaring A, Polastre J, Szewczyk R, et al. Wireless Sensor Networks for Habitat Monitoring [C]. in ACM International Workshop on Wireless Sensor Networks and Applications, 2002.
[127] 王凌. 智能优化算法及其应用 [M]. 北京: 清华大学出版社, 2001.10. 230p.