洪孫焱，申時(shí)凱，3，阿 圓

（1.昆明學(xué)院信息技術(shù)學(xué)院，云南昆明650214；2.昆明市物聯(lián)網(wǎng)及泛在工程技術(shù)中心，云南昆明650214；3.函館未來(lái)大學(xué)，日本）

基于網(wǎng)絡(luò)流的無(wú)線傳感網(wǎng)負(fù)載均衡問(wèn)題算法

洪孫焱1，2，申時(shí)凱1，2，3，阿 圓1，2

（1.昆明學(xué)院信息技術(shù)學(xué)院，云南昆明650214；2.昆明市物聯(lián)網(wǎng)及泛在工程技術(shù)中心，云南昆明650214；3.函館未來(lái)大學(xué)，日本）

在大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)中，普通節(jié)點(diǎn)與有較大能源和計(jì)算能力的網(wǎng)關(guān)節(jié)點(diǎn)相連，由網(wǎng)關(guān)融合成員節(jié)點(diǎn)的數(shù)據(jù)并實(shí)現(xiàn)數(shù)據(jù)的長(zhǎng)距離路由轉(zhuǎn)發(fā).網(wǎng)關(guān)節(jié)點(diǎn)負(fù)載均衡問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)路由中的關(guān)鍵問(wèn)題，Low給出了負(fù)載均衡問(wèn)題一個(gè)近似度為3／2的算法，我們舉出反例證明此算法的近似度不可能為3／2，并設(shè)計(jì)了一種新的近似度為2的基于網(wǎng)絡(luò)流的算法.實(shí)驗(yàn)仿真表明，在節(jié)點(diǎn)數(shù)較多的大規(guī)模傳感網(wǎng)絡(luò)中，新算法的近似度更低.

無(wú)線傳感器網(wǎng)絡(luò)；網(wǎng)絡(luò)流；負(fù)載均衡問(wèn)題；近似算法

無(wú)線傳感器網(wǎng)絡(luò)在緊急救援、救災(zāi)搶險(xiǎn)、軍事網(wǎng)絡(luò)等動(dòng)態(tài)通訊設(shè)施中扮演著越來(lái)越重要的角色.負(fù)載均衡問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)的關(guān)鍵問(wèn)題之一［1］.Heinzelman等［2］研究了無(wú)線傳感器網(wǎng)絡(luò)中通訊協(xié)議，姬寧等［3］改進(jìn)了LEACH算法，但是張學(xué)等［4］的研究表明LEACH在實(shí)際環(huán)境中表現(xiàn)很差.Low等［5-6］首次提出了無(wú)線傳感網(wǎng)絡(luò)中的負(fù)載均衡問(wèn)題，并給出了近似度為3／2的算法.我們經(jīng)過(guò)研究發(fā)現(xiàn)Low的算法不可能是3／2近似度的，本文給出了反例及一種基于網(wǎng)絡(luò)流［7］的算法.

無(wú)線傳感器網(wǎng)絡(luò)的負(fù)載均衡問(wèn)題，可以這樣抽象描述：給定一定數(shù)量的普通節(jié)點(diǎn)和網(wǎng)關(guān)，節(jié)點(diǎn)如何在一個(gè)可選的網(wǎng)關(guān)集中選擇一個(gè)合適的網(wǎng)關(guān)，使得整個(gè)網(wǎng)絡(luò)的網(wǎng)關(guān)最大負(fù)載最小.

無(wú)線傳感器網(wǎng)絡(luò)的負(fù)載均衡問(wèn)題（load-balanced clustering problem，LBCP），形式化描述如下：

di表示傳感節(jié)點(diǎn)ti的流量，i＝1，…，n；

Ci表示傳感節(jié)點(diǎn)ti可選的網(wǎng)關(guān)集合，ti∈T，Ci?C；

cj表示網(wǎng)關(guān)節(jié)點(diǎn)，j＝1，…，｜Ci｜；

xij表示傳感節(jié)點(diǎn)和網(wǎng)關(guān)的關(guān)系，如果cj在節(jié)點(diǎn)ti的可選網(wǎng)關(guān)集合中則其值為1，否則為0；

α：表示網(wǎng)關(guān)的最大負(fù)載.

則LBCP可表達(dá)為整數(shù)線性規(guī)劃形式：

LBCP可以一般化為同型機(jī)最小makespan調(diào)度問(wèn)題，這是一個(gè)強(qiáng)NP-難問(wèn)題并且存在PTAS.LBCP也是不相關(guān)機(jī)最小makespan調(diào)度問(wèn)題的一個(gè)特例.不相關(guān)機(jī)最小makespan調(diào)度問(wèn)題只能有近似度為2的近似算法，這與Low等人設(shè)計(jì)出近似度為3／2-ε（?ε＞0）的算法［5-6］是矛盾的.

1 反例

我們給出一個(gè)反例證明Low等給出的貪婪算法不能夠達(dá)到3／2的近似度.

如文獻(xiàn)［5-6］一樣，可以簡(jiǎn)化LBCP為一個(gè)二部圖G＝（T∪C，E），其中E為T(mén)中結(jié)點(diǎn)連接C中節(jié)點(diǎn)的邊.文獻(xiàn)［5-6］給出的貪婪算法如下：首先按流量把普通傳感節(jié)點(diǎn)降序排列，即T＝｛t1，t2，…，tn｝，d1≥d2≥…≥dn.然后以這個(gè)順序分配節(jié)點(diǎn)給網(wǎng)關(guān).對(duì)于每一個(gè)節(jié)點(diǎn)ti，如果存在ti到未使用網(wǎng)關(guān)的增廣路P，重新分配P上的節(jié)點(diǎn)，這樣可以用到更多的網(wǎng)關(guān)，否則分配這個(gè)節(jié)點(diǎn)給負(fù)載最小的網(wǎng)關(guān).詳見(jiàn)文獻(xiàn)［5-6］.

考慮一個(gè)由8個(gè)普通節(jié)點(diǎn)和4個(gè)網(wǎng)關(guān)組成網(wǎng)絡(luò)的情況，T＝｛t1，t2，…，t8｝，C＝｛c1，c2，…，c4｝，c1覆蓋的節(jié)點(diǎn)集合是｛t1，t2｝，c2覆蓋的節(jié)點(diǎn)集合是｛t2，t3，t4｝，c3覆蓋的節(jié)點(diǎn)集合是｛t3，t5，t6，t7｝，c4覆蓋的節(jié)點(diǎn)集合是｛t4，t5，t6，t7，t8｝，節(jié)點(diǎn)的流量如圖1所示.根據(jù)文獻(xiàn)［5-6］的貪婪算法，對(duì)于節(jié)點(diǎn)ti（i＝1，2，3，4），都有一個(gè)增廣路連接到ci（i＝1，2，3，4），因此分配給ci.對(duì)于節(jié)點(diǎn)ti（i＝5，6，7，8），存在增廣路，因此分配給最小負(fù)載的網(wǎng)關(guān).最后的結(jié)果如圖1中的粗線所示.這樣得到的可行解是4-2／m.從圖1可以很容易得到最優(yōu)解是2＋6／m.當(dāng)m是無(wú)窮大時(shí)，近似度是2.貪婪算法是啟發(fā)式算法，不能保證達(dá)到最優(yōu)解，所以Low等給出的貪婪算法的近似度高于2，不能夠達(dá)到文獻(xiàn)［5-6］中所稱(chēng)的3／2近似度.

2 LBCP新算法

在本節(jié)，我們給出LBCP問(wèn)題一種新的近似度為2的算法.分為2步來(lái)考慮：①構(gòu)造LBCP松弛問(wèn)題：假設(shè)節(jié)點(diǎn)的流量可以分割，從而一個(gè)節(jié)點(diǎn)可以連接多個(gè)網(wǎng)關(guān).把LBCP問(wèn)題轉(zhuǎn)化為網(wǎng)絡(luò)流問(wèn)題［7］，利用網(wǎng)絡(luò)流思想設(shè)計(jì)組合算法可以得到LBCP的松弛問(wèn)題最優(yōu)解；②從LBCP的松弛問(wèn)題最優(yōu)解得到原始LBCP的可行解.

2.1 LBCP松弛問(wèn)題

假設(shè)LBCP中，每個(gè)節(jié)點(diǎn)的流量可以分割，從而1個(gè)節(jié)點(diǎn)可以連接多個(gè)網(wǎng)關(guān).

定理1 LBCP松弛問(wèn)題有多項(xiàng)式時(shí)間算法.

證明 給出算法以證明.

構(gòu)造網(wǎng)絡(luò)：

其中s是源，t是目標(biāo)，對(duì)于每條邊（s，cj）（j＝1，2，…，m），容量為B（B是一個(gè)參數(shù)，它的最終值是LBCP松弛問(wèn)題最優(yōu)解）.

對(duì)于每條邊（ti，t）（i＝1，2，…，n），容量為di，即滿(mǎn)足每個(gè)傳感節(jié)點(diǎn)si的流量要求.我們給出網(wǎng)絡(luò)構(gòu)造的實(shí)例：2個(gè)網(wǎng)關(guān)、4個(gè)傳感節(jié)點(diǎn)的LBCP二部圖如圖2（a）所示，構(gòu)造的網(wǎng)絡(luò)流圖如圖2（b）.

2.2 去圈技術(shù)

給出一個(gè)實(shí)例，2個(gè)網(wǎng)關(guān)、4個(gè)傳感節(jié)點(diǎn)的網(wǎng)絡(luò)，節(jié)點(diǎn)的流量為4，6，5，5，網(wǎng)絡(luò)二部圖與圖2一樣.使用二分法和網(wǎng)絡(luò)流算法，得到最優(yōu)解的值是10，如圖3（a）.這個(gè)算法結(jié)果中節(jié)點(diǎn)t1和t4流量被整體分配給某個(gè)網(wǎng)關(guān)，而t2和t3流量分散給2個(gè)網(wǎng)關(guān).我們稱(chēng)t2和t3這樣的節(jié)點(diǎn)為分流節(jié)點(diǎn)，分流節(jié)點(diǎn)指的是流量分散給了至少2個(gè)網(wǎng)關(guān)的節(jié)點(diǎn).

如果節(jié)點(diǎn)ti不是分流節(jié)點(diǎn)，直接分配ti給cj，邊的流量為f（cj，ti）＞0.因此僅考慮分流節(jié)點(diǎn)即可.設(shè)TS為分流節(jié)點(diǎn)集，GS＝（CS∪TS，ES）是最優(yōu)解解二部圖的導(dǎo)出子圖，其中CS＝f（cj，ti）＞0，ti是分流節(jié)點(diǎn)｝，ES＝｛（cj，ti）｜f（cj，ti）＞0，ti是分流節(jié)點(diǎn)｝.我們稱(chēng)GS＝（CS∪TS，ES）為分流圖.圖3（b）就是所舉實(shí)例的分流圖.

二部圖沒(méi)有奇圈，如果在二部圖中找到一個(gè)圈，它必定有偶數(shù)邊.這個(gè)圈可以分成2個(gè)匹配：M1和M2.例如圖3（b）中圈C＝（c1，t2，c2，t3）包含2個(gè)匹配：

對(duì)于任何分流圖在有限步（至多nm）之后，都可以得到森林.

顯然，給定一個(gè)LCBP松弛問(wèn)題的最優(yōu)解，利用去圈技術(shù)得到的是另一個(gè)最優(yōu)解，其中的分流節(jié)點(diǎn)更少且相關(guān)的分流圖是森林.

然后可以得到可行解：如果ti沒(méi)有被分流，直接把全部流量f（cj，ti）＞0分配給網(wǎng)關(guān)cj.在分流圖中，每個(gè)傳感節(jié)點(diǎn)都是分流節(jié)點(diǎn)，度數(shù)至少為2.根據(jù)取整定理［1］，對(duì)于森林中的每個(gè)樹(shù)，把某個(gè)傳感節(jié)點(diǎn)當(dāng)做根節(jié)點(diǎn)，可匹配這個(gè)節(jié)點(diǎn)給任何一個(gè)子節(jié)點(diǎn)即網(wǎng)關(guān)（每個(gè)傳感節(jié)點(diǎn)有至少一個(gè)子節(jié)點(diǎn)，因?yàn)槊總€(gè)網(wǎng)關(guān)有至多一個(gè)父節(jié)點(diǎn)，所以沒(méi)有網(wǎng)關(guān)匹配一個(gè)以上傳感節(jié)點(diǎn)）.實(shí)例的可行解如圖4（b）.

2.3 算法時(shí)間復(fù)雜度

定理2 對(duì)于每個(gè)網(wǎng)關(guān)cj，最終負(fù)載至多是OPTf＋｛di｝-1，小于2OPT.其中OPT表示LBCP問(wèn)題的最優(yōu)解（見(jiàn)公式（1）），OPTf表述LBCP松弛問(wèn)題最優(yōu)解.

證明 很明顯在取整分流節(jié)點(diǎn)過(guò)程中網(wǎng)關(guān)的負(fù)載不會(huì)改變.我們?nèi)≌臅r(shí)候至多一整個(gè)節(jié)點(diǎn)分給某一網(wǎng)關(guān)，所以任一網(wǎng)關(guān)的負(fù)載至多是OPTf＋x｛ di｝-1.

因?yàn)镺PTf和 ｝是OPT的下界，所以我們的算法可以達(dá)到近似因子為2.

3 仿真

用Lingo計(jì)算最優(yōu)解，用Java構(gòu)造出傳感網(wǎng)絡(luò)模擬環(huán)境，得出的可行解與最優(yōu)解與Low算法解之比.模擬環(huán)境中，選出不同數(shù)量傳感節(jié)點(diǎn)和20個(gè)網(wǎng)關(guān)隨機(jī)分布在一個(gè)2 000 m×2 000 m的平面上，節(jié)點(diǎn)的負(fù)載是100 kb／s到500 kb／s，節(jié)點(diǎn)的有效傳輸距離為500m（這些參數(shù)是根據(jù)無(wú)線傳感網(wǎng)實(shí)際情況設(shè)定的）.

每個(gè)算法在節(jié)點(diǎn)數(shù)為50、100、150、200的情況下分別做100次實(shí)驗(yàn).由實(shí)驗(yàn)結(jié)果與Lingo計(jì)算的最優(yōu)解之比得到近似因子.實(shí)驗(yàn)結(jié)果如圖5所示.其中Low算法在節(jié)點(diǎn)數(shù)為100的實(shí)驗(yàn)中出現(xiàn)了1.57的近似比，這也證明Low算法不是3／2近似度的.實(shí)驗(yàn)結(jié)果表明在節(jié)點(diǎn)數(shù)為50、150和200的時(shí)候均有計(jì)算到最優(yōu)解，本文算法的近似度隨著節(jié)點(diǎn)數(shù)的增多而減低，如圖6所示在節(jié)點(diǎn)數(shù)為500到1 000的大規(guī)模網(wǎng)絡(luò)中本文算法比Low算法好.

4 結(jié)語(yǔ)

負(fù)載均衡問(wèn)題LBCP是傳感器網(wǎng)絡(luò)中的重要問(wèn)題，本文對(duì)LBCP進(jìn)行研究，指出了Low算法的近似度至少為2，而不是作者申稱(chēng)的3／2近似度.我們給出LBCP的網(wǎng)絡(luò)流算法，對(duì)算法進(jìn)行模擬，結(jié)果表明在節(jié)點(diǎn)數(shù)超過(guò)100的情況下能得到比Low算法更優(yōu)的解.

［1］錢(qián)志鴻，王義君.面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述［J］.電子與信息學(xué)報(bào)，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］姬寧，崔曉燕.一種基于負(fù)載均衡無(wú)線傳感器網(wǎng)絡(luò)節(jié)能分簇算法［J］.傳感器世界，2007，13（12）：40-43.

［4］張學(xué)，陸桑璐，陳貴海，等.無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂疲跩］.軟件學(xué)報(bào)，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，F(xiàn)ANG 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.

（責(zé)任編輯 莊紅林）

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.

云南省應(yīng)用基礎(chǔ)研究計(jì)劃項(xiàng)目（2011FZ176）；昆明學(xué)院科研項(xiàng)目（2010JS02）.

洪孫焱（1982-），男，碩士，講師.主要研究方向：網(wǎng)絡(luò)安全與物聯(lián)網(wǎng)技術(shù).

申時(shí)凱（1964-），男，教授.主要研究方向：數(shù)據(jù)融合與物聯(lián)網(wǎng)技術(shù).