面向微電網的WSN分簇算法

施 義，劉振興，蔡 彬，謝祥中

(1.武漢科技大學 信息科學與工程學院，湖北 武漢 430081；2.倫敦大學學院 UCL動力工程系，倫敦 英國 WC1E 7JE)

0 引 言

作為智能電網領域的重要組成部分，微電網中存在各類分布式電源，網絡中使用大量的監測設備來滿足其雙向、實時、高效的通信要求[1,2]。針對微電網就地控制層中采集節點多、節點位置分散等復雜的網絡情況[3,4]，利用無線傳感器網絡(wireless sensor networks，WSN)技術來構建該層的數據監控網絡是保證電網安全穩定運行的重要手段。

考慮微電網的實際特點，監控網絡選擇具有能量效率高、可擴展性強的分簇結構[5]。傳統的分簇算法如LEACH算法采用均勻分簇，由于簇間路由是單跳的方式，存在遠離匯聚點的簇頭節點因通信代價高而過早死亡的問題[6]。EEUC算法引入非均勻分簇概念，在簇頭選擇階段，其通信代價大，簇頭選擇和成簇等階段缺乏節點剩余能量的考慮，導致靠近匯聚點的簇頭節點沒有足夠多的能量完成大量數據的轉發而提前死亡[7,8]，影響了網絡整體的生命周期。

針對LEACH算法和EEUC算法的不足，結合微電網中分布式電源的分布情況，本文提出了一種基于節點實時能量的無線傳感器網絡非均勻分簇算法(node real-time energy based uneven clustering algorithm for WSN in micro-grid，NREUC)。NREUC算法在簇頭競爭半徑中引入節點實時能量作為部分權重，在成簇階段，普通節點依據成簇判斷因子來選擇要加入的簇，達到非均勻分簇的目的。實驗結果表明，與LEACH算法和EEUC算法相比，NREUC算法顯著延長了網絡中第一個節點死亡時間，死亡節點的分布是均勻分布，避免了監控盲區的出現，提高了網絡的監控質量。

1 微電網監控網絡

微電網的運行控制中，分布式電源的監控網絡如圖1所示。其中通信系統可以分為控制中心層、集中控制層和就地控制層[9]。終端電源單元將自身的狀態信息通過無線傳感器網絡發送給數據匯聚層的監控單元，再由數據匯聚層統一通過光纖傳遞的方式傳遞給控制中心層進行調控[10]。本文中，假設網絡里所有的監控節點和區域匯聚點位置是固定的，每個監控節點是同構的，都可以成為簇頭、候選簇頭或普通節點。同時，網絡中鏈路是對稱的，已知對方發射功率時，節點能夠根據接收信號強度計算距離[11]。

圖1 微電網中分布式電源模塊監控網絡

根據圖1可得圖2監控網絡的仿真場景，其中小圓圈是監控節點，五角星是匯聚點。微電網中分布式電源模塊監控網絡中簇規模的整體趨勢是靠近匯聚節點的簇規模小數量多，遠離匯聚節點的簇規模大數量小，這樣讓靠近匯聚節點的簇頭有更多的能量轉發消息，不至于過早死亡形成“熱區”。

圖2 監控網絡仿真場景

2 分簇算法

2.1 簇頭選舉

無線傳感器網絡在進行分簇時，首先是簇頭選舉的過程。在簇頭選舉中，NREUC算法利用簇頭競爭半徑來實現簇頭節點的非均勻分布，在競爭半徑Ri計算公式中引入距離和能量兩個因素

(1)

式中：dmax、dmin——網絡中節點到匯聚節點的最大與最小距離，d(si,s0)是節點i與匯聚節點的距離，R0是簇頭競爭半徑的最大值，Ep是網絡中存活節點的平均能量與節點i的實時能量的比值，c是用于控制取值范圍的參數。

考慮到節點的通信能耗，在NREUC算法的簇頭競爭半徑計算中，節點與匯聚節點間距離仍是主要因素，距離匯聚節點越遠，競爭半徑越大。節點自身實時能量是次要因素，對簇頭競爭半徑起到微調的作用，能量大的節點的競爭半徑偏大，但不會影響網絡中簇規模分布的整體結構。

2.2 成簇階段

簇頭節點確定后，進入成簇階段。在本文NREUC算法中，普通節點根據成簇判斷因子決定要加入的簇

(2)

式中：C(i,j,k)是第k輪，節點j到簇頭i的成簇判斷因子，Re(i,k)為簇頭i的實時能量，Ek是當前網絡中節點的平均能量，d(si,sj)為節點j到簇頭i的距離。這樣在考慮就近成簇減少通信代價的同時，讓剩余能量大的簇頭能夠接收更多的節點，達到能量均衡的目的。

2.3 NREUC算法

圖3 NREUC算法

初始化網絡時，匯聚節點會向所有節點廣播消息，以便讓所有節點計算出與匯聚節點間的距離，用于后面的非均勻分簇以及節點向基站傳輸信息時發送功率的選擇。NREUC算法采用循環機制，每輪中包括簇頭的選舉及簇的形成、簇間路由建立和數據的傳輸。網絡中的節點有4種狀態：普通節點狀態，候選簇頭狀態，簇頭狀態和死亡狀態。每個節點設有簇頭標志位G，標志位G初始態置0，在節點當選簇頭后，標志位G會置1。節點的狀態每輪會動態變化，簇頭在候選簇頭中產生，其中候選簇頭節點的簇頭競爭半徑為Ri，由式(1)得到。大小不同的競爭半徑形成規模不等的簇。

NREUC算法的具體實現步驟如下(如圖3所示)：

步驟1 標志位G的初始化

對所有節點的簇頭標志位G置0。

步驟2 候選簇頭選舉

先判斷簇頭標志位G，允許標志位為0的節點進行候選簇頭的選舉，否則節點休眠直至簇頭競選結束。再按概率選出部分節點成為候選簇頭，其它落選節點休眠直至簇頭競選結束。

步驟3 簇頭選舉

依據式(1)求出的簇頭競爭半徑來實現簇頭的選舉。每輪簇頭競選中，候選簇頭節點i有一張該節點的鄰候選簇頭信息表，表內的任意節點j都滿足節點j與節點i間的距離小于這兩個節點的競爭半徑的最大值的條件。實時能量最大的候選簇頭最先被選出擔任簇頭，同時它的鄰候選簇頭信息表中的候選簇頭都退選成為普通節點。然后再在剩余的候選簇頭中，選出實時能量最大的節點成為簇頭，它的鄰候選簇頭信息表中的候選簇頭也都退選成為普通節點，依次循環至沒有候選簇頭。在節點出任簇頭后，該節點標志位G置1。

步驟4 成簇階段

網絡中的普通節點依據成簇判斷因子的式(2)來選擇簇頭，形成規模大小不等的簇。

步驟5 信息傳輸階段

本網絡中采用簇內單跳，簇首間多跳的方式進行信息的傳輸。

步驟6 簇頭標志G的再判斷

信息傳輸完成后，計算各節點在本輪結束時的剩余能量，將剩余能量大于或等于平均剩余能量的簇頭節點的標志位G置0，讓其可以繼續參與到后面的簇頭競選中。

步驟7 死亡節點個數判斷

若網絡中的節點死亡數超過預設最大值，則網絡宣告死亡，否則進入新一輪的網絡分簇、信息傳遞中。

3 算法仿真

3.1 仿真參數設置

本文在MATLAB中分別編碼LEACH算法、EEUC算法和NREUC算法，并進行仿真性能分析。實驗中，在邊長200 m的方形區域內隨機分布400個節點，網絡中消耗的能量主要由發射電路能耗和功率放大電路的能耗組成。當節點發射比特數為k比特的數據到相聚d距離的位置時，通信能耗計算為

(3)

式中：Eelec——發射電路消耗的能量，εfs、εmp——兩類信道模型中功率放大電路的最大消耗能量。相關仿真場景參數見表1。

表1 仿真場景參數

在式(1)簇頭競爭半徑Ri的計算中，系數c和最大競爭半徑R0的值是需要預先設定的。其中，為方便與EEUC算法比較，系數c的值沿用原EEUC的值0.5。對于候選簇頭的最大競爭半徑R0，它影響最后簇的生成個數，最大競爭半徑大時，則生成的簇個數少，從而影響最終網絡中簇分布情況。這里采用實驗方法得出本仿真環境下最大競爭半徑的最適值為90 m。

3.2 仿真結果分析

網絡仿真中，本文主要在網絡生命周期及網絡的死亡節點分布上進行比較分析。網絡生命周期越長，特別是網絡中第一個節點的死亡時間越長，則表明網絡中能量越均衡，節點不會過早死亡。網絡的死亡節點分布影響著整個網絡的監控質量，死亡節點分布越均勻，監控質量越好。

3.2.1 網絡生命周期

針對采集信息精確度要求較高的網絡，節點的初始死亡時間決定著網絡整體的生命周期。如微電網中，單元級別的設備狀態數據采集需要達到全覆蓋和高精度的要求，盲區的出現會影響整個網絡的運行安全。

圖4中比較了3種分簇算法的網絡生命周期，NREUC算法相比于LEACH算法和EEUC算法，網絡中第一個節點的死亡時間得到了很大的延長，網絡整體的存活時間也得到了增加。NREUC算法中，簇間多跳路由的方式解決了LEACH算法中遠離匯聚點的簇頭節點因通信消耗大而過早死亡的問題。在候選簇頭的選擇上，NREUC算法加入簇頭標志位的判斷，讓上輪中擔任過簇頭的這類能量消耗大的節點不參與之后的簇頭競選，提高候選簇頭質量，避免不必要的能量消耗，緩解了EEUC算法中簇頭選擇能量開銷大的問題。在NREUC算法簇頭競爭半徑計算中，考慮節點自身能量和其與匯聚節點間距離兩個因素，使分簇的規模較EEUC算法更加合理。根據圖4中NREUC算法曲線的衰減走勢可以看出，NREUC算法在同等的能耗條件下提高了網絡中的能量均衡程度，在網絡生存周期后段，每輪中的存活節點占有率都要比LEACH算法和EEUC算法高。

圖4 3種分簇算法的網絡生命周期

3.2.2 網路死亡節點分布

根據圖5和圖6中網絡的死亡節點分布可以看出，圖5中EEUC算法中死亡節點大多集中在靠近匯聚節點的區域，圖6中NREUC算法中死亡節點分布均勻。

圖5 EEUC算法的死亡節點分布

圖6 NREUC算法的死亡節點分布

NREUC算法在每輪的簇頭選舉階段都會考慮各個節點的剩余能量問題，減少低能量節點成為簇頭的可能性，在簇頭競爭半徑計算中加入簇頭自身能量的考慮因素，利用大小不等的簇頭競爭半徑達到網絡中簇頭節點非均勻分布的目的。同時在成簇時，NREUC算法將簇頭能量考慮進去，普通節點在選擇簇頭時不再是單純的就近選擇，而是根據節點與簇頭間距離及簇頭剩余能量兩個因素進行判斷，最終使得網絡中最后的死亡節點分布是均勻的，解決了EEUC算法中靠近匯聚點的簇頭節點因轉發過多數據而提前死亡的問題，達到提高網絡監控質量的目的。

4 結束語

本文提出了一種面向微電網的WSN非均勻分簇算法，算法的核心思想是在簇頭選擇和成簇階段均加入節點的實時能量因素進行考慮，以均衡網絡中的能量消耗，延長網絡的生存時間。針對微電網監控網絡中節點分布廣、監控精度高的特點，該算法相比于傳統的分簇算法，網絡中能量均衡的程度更高，節點初始死亡時間更晚，網絡生命期更長。

雖然本文的NREUC算法對無線傳感器網絡中能量均衡起到了較好的效果，但在分簇時需要一定的消息開銷，可能會影響網絡生存時間。下一步的工作考慮減少網絡中每輪的能量消耗，同時驗證該算法在實際微電網環境中應用的可行性。

[1]YANG Xinfa,SU Jian,LYU Zhipeng,et al.Overview on micro-grid technology[J].Proceedings of the Chinese Society of Electrical Engineering,2014,34(1):57-70(in Chinese).[楊新法,蘇劍,呂志鵬,等.微電網技術綜述[J].中國電機工程學報,2014,34(1):57-70.]

[2]Arefifar SA,Mohamed ARI,El-Fouly T.Optimized multiple microgrid-based clustering of active distribution systems consi-dering communication and control requirements[J].IEEE Transactions on Industrial Electronics,2015,62(2):711-723.[3]WU Xiong,WANG Xiuli,LIU Shimin,et al.Summary of research on microgrid energy management system[J].Electric Power Automation Equipment,2014,34(10):7-14(in Chinese).[吳雄,王秀麗,劉世民,等.微電網能量管理系統研究綜述[J].電力自動化設備,2014,34(10):7-14.]

[4]Angelo PM,Ted S.A survey of techniques used to control microgrid generation and storage during island operation[J].IEEE Transactions on Power Systems,2015,30(2):701-709.

[5]Bin LI,Wang WJ,Yin QY,et al.An energy-efficient geographic routing based on cooperative transmission in wireless sensor networks[J].Science China Information Sciences,2013,56(7):1-10.

[6]FENG Lin,RAN Xiaomin,MEI Guanlin.WSN coverage tactics based on balanced node energy consumption[J].Computer Engineering and Design,2015,36(9):2334-2339(in Chinese).[馮琳,冉曉旻,梅關林.基于節點能耗均衡的WSN覆蓋策略[J].計算機工程與設計,2015,36(9):2334-2339.]

[7]YUE Liying,DAI Yueming,WU Dinghui.Energy optimized uneven clustering routing protocol in wireless sensor networks[J].Computer Engineering and Applications,2015,51(15):80-85(in Chinese).[岳麗穎,戴月明,吳定會.一種能量優化WSNs非均勻分簇路由協議[J].計算機工程與應用,2015,51(15):80-85.]

[8]WEN Peizhi,XU Chenjiao,DENG Zhenrong,et al.Cluster-routing protocol for heterogenous multi-level wireless sensor networks[J].Computer Engineering and Design,2016,37(6):1471-1477(in Chinese).[溫佩芝,許晨蛟,鄧珍榮,等.多級異構無線傳感器網絡分簇路由協議[J].計算機工程與設計,2016,37(6):1471-1477.]

[9]ZHANG Xinchang.Solution and application of micro-grid ope-ration control[J].Power System Protection and Control,2014,42(10):141-146(in Chinese).[張新昌.微電網運行控制解決方案及應用[J].電力系統保護與控制,2014,42(10):141-146.]

[10]Tan X,Li Q,Wang H.Advances and trends of energy sto-rage technology in microgrid[J].International Journal of Electrical Power & Energy Systems,2013,44(1):179-191.

[11]JIANG Changjiang,SHI Weiren,TANG Xianlun,et al.Energy-balanced unequal clustering routing protocol for wireless sensor networks[J].Journal of Software,2012,34(5):1222-1232(in Chinese).[蔣暢江,石為人,唐賢倫,等.能量均衡的無線傳感器網絡非均勻分簇路由協議[J].軟件學報,2012,34(5):1222-1232.]