JIANG Zidong，FENG Hui，YANG Tao，HU Bo

(Department of Electronic Engineering，Fudan University，Shanghai 200433，China)

Joint Optimization of Battery Allocation and Routing for Maximum Lifetime in Wireless Sensor Networks*

JIANG Zidong，FENG Hui，YANG Tao，HU Bo*

(Department of Electronic Engineering，Fudan University，Shanghai 200433，China)

In order to prolong the lifetime of wireless sensor networks(WSN)，we jointly optimize the routing and battery allocation policy.The joint optimization problem is modeled with continuous and discrete battery levels respectively.In the case of continuous battery allocation，a linear programming problem is established，which obtains the optimal routing and battery allocation simultaneously.In the case of discrete battery allocation，a suboptimal but efficient method is proposed，which slacks a combinational optimization problem to a continuous form，and discretizes the battery levels in an optimal way.The simulation results show that our methods can substantially prolong the network lifetime and perform better than others.

wireless sensor networks;network lifetime;battery allocation;routing;linear programming

无线传感器网络(WSN)通常会在目标区域中放置大量的廉价传感器节点来完成数据的采集，传输与处理。由于其成本低，覆盖率高的特性，在很多领域都引起了广泛关注［1－2］，比如环境数据监测，灾难预警，目标跟踪等。在大多数的场景中，节点由电池供能，且更换电池所需要的成本很高，例如当网络布置在偏远区域中时。因此，在无线传感器网络的应用中，如何在有限的电量下延长网络的工作时间，是一项重要的工作和挑战。

无线传感器网络的寿命主要取决于节点的能耗能否平衡。在有数据汇聚节点(通常称为Sink节点)的多跳WSN中，Sink节点周围的节点由于需要转发大量数据而容易出现电量耗尽的情况，导致外部节点虽然有剩余电量，整个网络却无法继续工作。这种现象被称为能量空洞(Energy Hole)［3－5］。一些方法可以减轻这种现象，比如合理规划节点的放置策略和放置密度［6－7］，或者引入可移动的Sink节点［8－10］来平衡全网能耗。但是很多应用场景中，节点的位置是预先确定不可更改的。比如在气象数据监测网络中，节点的放置有严格的规定，这关系到测量数据的准确性。在这些场景中，节点电池电量分配［11－13］就是一个缓解能量空洞现象的有效方式。文献［11］首先提出了对节点分配不同电量的电池可以有效的延长网络寿命的观点。其多层分配方法MTA(Multiple Tiers Allocation Method)根据节点到Sink节点的跳数，将节点划分到不同的层级，同一层级采用同一种电量的电池。但是MTA的方法需要假设WSN有均匀的节点分布密度，有一定局限性，而且它的推导和分析都是基于最小跳数路由策略。……