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

洪孙焱，申时凯，3，阿 圆

（1.昆明学院信息技术学院，云南昆明650214；2.昆明市物联网及泛在工程技术中心，云南昆明650214；3.函馆未来大学，日本）

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

洪孙焱1，2，申时凯1，2，3，阿 圆1，2

（1.昆明学院信息技术学院，云南昆明650214；2.昆明市物联网及泛在工程技术中心，云南昆明650214；3.函馆未来大学，日本）

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

无线传感器网络；网络流；负载均衡问题；近似算法

无线传感器网络在紧急救援、救灾抢险、军事网络等动态通讯设施中扮演着越来越重要的角色.负载均衡问题是无线传感器网络的关键问题之一［1］.Heinzelman等［2］研究了无线传感器网络中通讯协议，姬宁等［3］改进了LEACH算法，但是张学等［4］的研究表明LEACH在实际环境中表现很差.Low等［5-6］首次提出了无线传感网络中的负载均衡问题，并给出了近似度为3／2的算法.我们经过研究发现Low的算法不可能是3／2近似度的，本文给出了反例及一种基于网络流［7］的算法.

无线传感器网络的负载均衡问题，可以这样抽象描述：给定一定数量的普通节点和网关，节点如何在一个可选的网关集中选择一个合适的网关，使得整个网络的网关最大负载最小.

无线传感器网络的负载均衡问题（load-balanced clustering problem，LBCP），形式化描述如下：

di表示传感节点ti的流量，i＝1，…，n；

Ci表示传感节点ti可选的网关集合，ti∈T，Ci⊆C；

cj表示网关节点，j＝1，…，｜Ci｜；

xij表示传感节点和网关的关系，如果cj在节点ti的可选网关集合中则其值为1，否则为0；

α：表示网关的最大负载.

则LBCP可表达为整数线性规划形式：

LBCP可以一般化为同型机最小makespan调度问题，这是一个强NP-难问题并且存在PTAS.LBCP也是不相关机最小makespan调度问题的一个特例.不相关机最小makespan调度问题只能有近似度为2的近似算法，这与Low等人设计出近似度为3／2-ε（∀ε＞0）的算法［5-6］是矛盾的.

1 反例

我们给出一个反例证明Low等给出的贪婪算法不能够达到3／2的近似度.

如文献［5-6］一样，可以简化LBCP为一个二部图G＝（T∪C，E），其中E为T中结点连接C中节点的边.文献［5-6］给出的贪婪算法如下：首先按流量把普通传感节点降序排列，即T＝｛t1，t2，…，tn｝，d1≥d2≥…≥dn.然后以这个顺序分配节点给网关.对于每一个节点ti，如果存在ti到未使用网关的增广路P，重新分配P上的节点，这样可以用到更多的网关，否则分配这个节点给负载最小的网关.详见文献［5-6］.

考虑一个由8个普通节点和4个网关组成网络的情况，T＝｛t1，t2，…，t8｝，C＝｛c1，c2，…，c4｝，c1覆盖的节点集合是｛t1，t2｝，c2覆盖的节点集合是｛t2，t3，t4｝，c3覆盖的节点集合是｛t3，t5，t6，t7｝，c4覆盖的节点集合是｛t4，t5，t6，t7，t8｝，节点的流量如图1所示.根据文献［5-6］的贪婪算法，对于节点ti（i＝1，2，3，4），都有一个增广路连接到ci（i＝1，2，3，4），因此分配给ci.对于节点ti（i＝5，6，7，8），存在增广路，因此分配给最小负载的网关.最后的结果如图1中的粗线所示.这样得到的可行解是4-2／m.从图1可以很容易得到最优解是2＋6／m.当m是无穷大时，近似度是2.贪婪算法是启发式算法，不能保证达到最优解，所以Low等给出的贪婪算法的近似度高于2，不能够达到文献［5-6］中所称的3／2近似度.

2 LBCP新算法

在本节，我们给出LBCP问题一种新的近似度为2的算法.分为2步来考虑：①构造LBCP松弛问题：假设节点的流量可以分割，从而一个节点可以连接多个网关.把LBCP问题转化为网络流问题［7］，利用网络流思想设计组合算法可以得到LBCP的松弛问题最优解；②从LBCP的松弛问题最优解得到原始LBCP的可行解.

2.1 LBCP松弛问题

假设LBCP中，每个节点的流量可以分割，从而1个节点可以连接多个网关.

定理1 LBCP松弛问题有多项式时间算法.

证明 给出算法以证明.

构造网络：

其中s是源，t是目标，对于每条边（s，cj）（j＝1，2，…，m），容量为B（B是一个参数，它的最终值是LBCP松弛问题最优解）.

对于每条边（ti，t）（i＝1，2，…，n），容量为di，即满足每个传感节点si的流量要求.我们给出网络构造的实例：2个网关、4个传感节点的LBCP二部图如图2（a）所示，构造的网络流图如图2（b）.

2.2 去圈技术

给出一个实例，2个网关、4个传感节点的网络，节点的流量为4，6，5，5，网络二部图与图2一样.使用二分法和网络流算法，得到最优解的值是10，如图3（a）.这个算法结果中节点t1和t4流量被整体分配给某个网关，而t2和t3流量分散给2个网关.我们称t2和t3这样的节点为分流节点，分流节点指的是流量分散给了至少2个网关的节点.

如果节点ti不是分流节点，直接分配ti给cj，边的流量为f（cj，ti）＞0.因此仅考虑分流节点即可.设TS为分流节点集，GS＝（CS∪TS，ES）是最优解解二部图的导出子图，其中CS＝f（cj，ti）＞0，ti是分流节点｝，ES＝｛（cj，ti）｜f（cj，ti）＞0，ti是分流节点｝.我们称GS＝（CS∪TS，ES）为分流图.图3（b）就是所举实例的分流图.

二部图没有奇圈，如果在二部图中找到一个圈，它必定有偶数边.这个圈可以分成2个匹配：M1和M2.例如图3（b）中圈C＝（c1，t2，c2，t3）包含2个匹配：

对于任何分流图在有限步（至多nm）之后，都可以得到森林.

显然，给定一个LCBP松弛问题的最优解，利用去圈技术得到的是另一个最优解，其中的分流节点更少且相关的分流图是森林.

然后可以得到可行解：如果ti没有被分流，直接把全部流量f（cj，ti）＞0分配给网关cj.在分流图中，每个传感节点都是分流节点，度数至少为2.根据取整定理［1］，对于森林中的每个树，把某个传感节点当做根节点，可匹配这个节点给任何一个子节点即网关（每个传感节点有至少一个子节点，因为每个网关有至多一个父节点，所以没有网关匹配一个以上传感节点）.实例的可行解如图4（b）.

2.3 算法时间复杂度

定理2 对于每个网关cj，最终负载至多是OPTf＋｛di｝-1，小于2OPT.其中OPT表示LBCP问题的最优解（见公式（1）），OPTf表述LBCP松弛问题最优解.

证明 很明显在取整分流节点过程中网关的负载不会改变.我们取整的时候至多一整个节点分给某一网关，所以任一网关的负载至多是OPTf＋x｛ di｝-1.

因为OPTf和 ｝是OPT的下界，所以我们的算法可以达到近似因子为2.

3 仿真

用Lingo计算最优解，用Java构造出传感网络模拟环境，得出的可行解与最优解与Low算法解之比.模拟环境中，选出不同数量传感节点和20个网关随机分布在一个2 000 m×2 000 m的平面上，节点的负载是100 kb／s到500 kb／s，节点的有效传输距离为500m（这些参数是根据无线传感网实际情况设定的）.

每个算法在节点数为50、100、150、200的情况下分别做100次实验.由实验结果与Lingo计算的最优解之比得到近似因子.实验结果如图5所示.其中Low算法在节点数为100的实验中出现了1.57的近似比，这也证明Low算法不是3／2近似度的.实验结果表明在节点数为50、150和200的时候均有计算到最优解，本文算法的近似度随着节点数的增多而减低，如图6所示在节点数为500到1 000的大规模网络中本文算法比Low算法好.

4 结语

负载均衡问题LBCP是传感器网络中的重要问题，本文对LBCP进行研究，指出了Low算法的近似度至少为2，而不是作者申称的3／2近似度.我们给出LBCP的网络流算法，对算法进行模拟，结果表明在节点数超过100的情况下能得到比Low算法更优的解.

［1］钱志鸿，王义君.面向物联网的无线传感器网络综述［J］.电子与信息学报，2013，35（1）：215-227.

［2］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks［C］／／System Sciences，2000.Proceedings of the 33rd Annual Hawaii International Conference on.IEEE，2000（2）：10.

［3］姬宁，崔晓燕.一种基于负载均衡无线传感器网络节能分簇算法［J］.传感器世界，2007，13（12）：40-43.

［4］张学，陆桑璐，陈贵海，等.无线传感器网络的拓扑控制［J］.软件学报，2007，18（4）：943-954.

［5］LOW C P，NG JM，ANG Y H.An approximation algorithm for the load-balanced clustering problem in wireless sensor networks［C］／／Proceedings 15th International Conference on Computer Communications and Networks，ICCCN 2006.IEEE，2006：143-148.

［6］LOW C P，FANG C，MEE J，et al.Load-balanced clustering algorithms for wireless sensor networks［C］／／IEEE International Conference on Communications，2007，ICC′07.IEEE，2007：3485-3490.

［7］AHUJA R K，MAGNANTI T L，ORLIN J B.Network flows：Theory，algorithms，and applications［J］.Journal of the Operational Research Society，1994，45（11）：1340-1340.

［8］LENSTRA JK，SHMOYSD B，TARDOSÉ.Approximation algorithms for scheduling unrelated parallel machines［J］.Mathematical programming，1990，46（1／2／3）：259-271.

（责任编辑 庄红林）

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

HONG Sun-yan1，2，SHEN Shi-kai1，2，3，A Yuan1，2
（1.School of Information Technology，Kunming University，Kunming 650214，China；2.Kunming IOT and Ubiquitous Engineering Center，Kunming 650214，China；3.Future University-Hakodate，Japan）

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 novel2-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 networks.

wireless sensor networks；network flow；LBCP；approximation algorithm

TP301.6

：A

：1672-8513（2014）01-0011-04

2013-09-17.

云南省应用基础研究计划项目（2011FZ176）；昆明学院科研项目（2010JS02）.

洪孙焱（1982-），男，硕士，讲师.主要研究方向：网络安全与物联网技术.

申时凯（1964-），男，教授.主要研究方向：数据融合与物联网技术.