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

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

作　　者：洪孙焱[1,2] 申时凯[1,2,3] 阿圆[1,2] 

机构地区：[1]昆明学院信息技术学院,云南昆明650214 [2]昆明市物联网及泛在工程技术中心,云南昆明650214 [3]函馆未来大学

出　　处：《云南民族大学学报（自然科学版）》2014年第1期11-14,共4页Journal of Yunnan Minzu University:Natural Sciences Edition

基　　金：云南省应用基础研究计划项目(2011FZ176);昆明学院科研项目(2010JS02)

摘　　要：在大规模无线传感器网络中,普通节点与有较大能源和计算能力的网关节点相连,由网关融合成员节点的数据并实现数据的长距离路由转发.网关节点负载均衡问题是无线传感器网络路由中的关键问题,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.

关 键 词：无线传感器网络 网络流 负载均衡问题 近似算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]