基于网络流的无线传感网负载均衡问题算法

A new algorithm based on network flow for LBCP of wireless sensor networks

在大规模无线传感器网络中,普通节点与有较大能源和计算能力的网关节点相连,由网关融合成员节点的数据并实现数据的长距离路由转发.网关节点负载均衡问题是无线传感器网络路由中的关键问题,Low给出了负载均衡问题一个近似度为3/2的算法,我们举出反例证明此算法的近似度不可能为3/2,并设计了一种新的近似度为2的基于网络流的算法.实验仿真表明,在节点数较多的大规模传感网络中,新算法的近似度更低.

The load -balanced clustering problem （LBCP） for wireless sensor networks is related to the grouping of the sensor nodes into clusters to enhance the overall scalability of the network. A selected set of nodes, known as gateway nodes, will act as cluster-heads for each cluster and the objective is to balance the load among these gateways. C. P. Low has proposed a 3/2 approximation algorithm for this problem. This paper has proved that the main lemmas are wrong. It also designs a novel 2 - approximation algorithm based on network flow for this problem. It has proved that this algorithm can get better solutions than C. P. Low＇ s algorithm in large wireless sensor net- works.