能量優化的非均勻分簇路由的改進算法*

黃 鵬，封志宏，童宇行

0 引 言

無線傳感器網絡通常是由大量隨機部署在復雜環境中的傳感器節點和用于收集數據的基站（Sink）節點組成，并通過自組網的方式采集數據。傳感器節點能量采取電池供電的方式，在復雜環境中充電或者更換電池無法實現，因此研究熱門之一就是設計出一種能量高效的WSN路由算法[1-2]。

最早提出的LEACH[3]路由采用分簇協議，有效延長了整個網絡的存活時間。但是，由于簇頭節點到基站的通信采用單跳的方式進行，會使距離Sink節點較遠的簇頭消耗過多的能量。從一些仿真結果中可以看出，通過多跳方式完成簇頭到Sink節點間的數據傳輸更能節省能耗[4]。然而，近基站的簇頭需要中轉其他簇的數據，會造成近Sink節點的簇消耗過多能量，致使能耗不均衡。同時，在推選簇頭的過程中，沒有考慮有些節點當前能量不足而再次當選為簇頭的情況，從而加快了部分節點的失效，使鄰居節點的能耗加快，呈現出大片節點失效的問題。文獻[5]提出了一種能量高效的算法UCPO，解決了LEACH算法中隨機得到簇頭節點以及簇頭節點直接與Sink節點通信的問題，有效降低了網絡能耗。文獻[6]提出了分布式分簇路由算法DEEC，采用時間廣播機制選舉簇頭節點，采用權值函數完成多跳路徑選擇，最終均衡了網絡能耗。文獻[7]提出了EBFA協議，應用社會福利函數完成預估，某種程度上減少了WSN中的“熱區”。文獻[8]提出了LEACH-GPF算法，通過應用遺傳算法并對結合概率準則，更好地平衡了網絡能耗。文獻[9]提出的EEUC算法通過非均勻分簇的方式，有效均衡了WSN網絡的消耗，但其簇頭選擇過程中應用隨機函數與門限值確定，所選簇頭并不一定最佳。文獻[10]則在簇頭路由中引入蟻群算法，能夠延長WSN的生命周期，但蟻群算法只能保證部分路由路徑的效果最優。文獻[11]通過構建最小生成樹完成多跳路由，但構建過程中只考慮了多跳消耗和簇頭的當前能量值。

分析分簇協議中可能出現的問題，提出了能耗優化的WSN分簇算法。算法將WSN劃分為不均勻的簇，簇頭選擇階段引入簇首等待時間，計算過程中考慮節點當前的能量、節點到Sink節點的距離、鄰居表中的數目等因素，通過單跳的方式完成簇內數據的收集；在簇間多跳路由選擇階段，利用簇頭剩余能量、距離、簇內剩余能量均值等影響因子選擇中繼節點，構建數據傳輸路由樹，從而進行數據轉發。該協議能夠有效均衡節點能耗，延長WSN網絡的生命周期。

1 相關模型

1.1 網絡模型

首先，假設WSN具有以下性質：

①檢測區域內隨機部署了N個節點，之后這些節點在網絡中的相對位置不會變化，Sink節點能量變化忽略不計且其在網絡中的相對位置不再變化；

②每個節點的起始能量一定并配有唯一的身份編號ID，發射功率可根據網絡要求進行變化；

③通過收到的信號強弱RSSI來估算發送節點到接收節點的距離；

④Sink節點可以覆蓋其余所有節點，鏈路對稱，節點可以知道當前的能量，并具有一定的數據融合能力。

1.2 能耗模型

該能耗優化的非均勻分簇路由協議采用如圖1所示的無線通信能耗模型[12]。

圖1 本路由協議的無線通信能耗模型

該模型發送數據時的能耗公式如下：

式中：k表示收發數據的長度，單位bit；Eelec為節點發送/接收每比特數據消耗的能量，d為該數據傳輸的距離；εamp為多徑衰落模式下傳遞每比特數據消耗的能量；εfs為自由空間模式下傳遞每比特數據消耗的能量；d0的計算公式為是劃分空間模型的臨界值；當發送者與接收者的距離d小于d0時，采用自由空間的計算公式；當發送者與接收者的距離d大于等于d0時，采用多徑衰落的計算公式。

接收m bit數據節點消耗的能量為：

所以，簇頭的能耗為接收簇內其余節點采集的數據能耗、將采集到的數據融合后發出去的能耗以及做為其他簇的中繼節點的能耗。綜合式（1）、式（2）可以得到：

由式（3）可知，簇頭的能量消耗是通過簇內其余節點的數量、收集到的數據以及下一跳距離d決定的，所以選擇更優的簇頭和選擇最佳的傳輸路由可以減少能耗，均衡網絡負載。

2 能耗優化的非均勻分簇路由算法

本算法采用LEACH協議中“輪”的方式進行。每“輪”根據簇內節點間距離、簇首的鄰居數目以及節點的當前能量計算非均勻成簇的競爭半徑，簇首的選取利用時間等待機制，簇中采用TDMA的方式傳遞，簇間的路由根據構造的路由樹傳輸到基站節點。

2.1 簇首選擇算法

2.1.1 非均勻競爭半徑的計算

定義1 在改進的算法中給定除Sink節點外其余節點的最大通信半徑Rmax，對于WSN中的節點i，其鄰居節點定義如下：

i的鄰居節點的數目為：

EEUC算法中，在構建節點競爭半徑時只考慮了本簇首到Sink節點的距離，如式（6）所示。改進算法通過文獻[13]中對非均勻競爭半徑的計算進行完善，構建的競爭半徑考慮了簇首到Sink節點的d、鄰居表中的數目、每輪能耗的平均值以及節點當前的能量等因素。鄰居節點的數目已經由上述定義給出，每輪能耗的平均值由式（7）給出，所以非均勻成簇的競爭半徑計算公式由式（8）得到。

其 中 u1、u2、u3、u4為 參 數 控 制 因 子， 且u1+u2+u3+u4=1；dmin表示候選的簇首節點到Sink節點的最小d；dmax表示候選的簇首節點到Sink節點的最大d，r表示當前的輪數，Nnbc為候選簇首的鄰居個數。可見，成簇規模與候選簇首的鄰居個數、每輪平均能耗成反比，與該簇首當前能量、該簇首到鄰居節點的d成正比例。u3、u4兩個參數可以對剩余能量過多而消耗速率快的情況進行權衡，以決定最終的成簇大小。

2.1.2 簇首的競選

為后續流程的描述，對算法的概念說明如下：

①競選半徑。節點競選非均勻成簇的半徑，具體如式（8）所示。

②鄰居表。鄰居節點根據定義1得到每個節點的鄰居表來保存節點信息，具體如表1所示。

表1 節點鄰居表的內容

③剩余能量比PEi。PEi表示節點si的所有鄰居節點的當前平均當前能量與該節點的當前能量的比。PEi越小，說明節點si的當前的能量相比鄰居節點的當前能量更多。

④平均距離davg。依據鄰居表中的內容得到候選簇頭到其鄰居節點的距離的平均值。

⑤簇首競爭等待時間t。從節點收到Sink節點通知簇首競爭到本節點發出簇首競爭消息的時間。

其中：α為[0.9，1]中的任意值，T為指定的簇首競爭時間，β、γ為距離調節因子。因此可知，節點剩余能量低、距離基站遠和平均距離增大，都會使簇首競爭的持續時間變長。

2.1.3 簇首的競選流程

在WSN分簇路由協議算法中，簇首的能量和能耗影響著整個網絡的性能。當采用簇間多跳路由時，簇首不僅要對其所在簇的數據進行接收和融合，還要做為中繼節點參與其他簇的信息傳遞。本文以非均勻分簇算法為基礎，改進簇頭選舉公式。每輪開始時，WSN中所有的節點都參與到簇頭選舉的競爭中，之后應用時序的方式完成最終簇首的確定。

簇頭選舉的算法流程：

（1）WSN中的所有的節點以Rmax為半徑傳遞Ne_MSG消息，接收到該內容的其他節點加入到此節點的鄰居節點表中。

（2）Sink節點向全網廣播一個分簇信號Par_CLU，通過收到的信號強弱RSSI，每個節點估算Sink節點到節點的距離，并根據此時鄰居節點表中的信息，結合式（8）計算各自的競選半徑。

（3）各節點在其半徑Rc/2的范圍內發送競選的消息，其內容主要有節點的ID和當前的能量。

（4）各節點收到來自其他節點的競選消息，根據收到的信號強度RSSI計算節點間的距離，并更新此時的鄰居節點表。

（5）各節點根據此時鄰居節點表中的信息，結合式（9）、式（10）計算PEi、davg，從而得到式（11）的各自簇首競爭等待的時間。

（6）Sink節點發出同步信號Tim_MSG，以同步各個節點的時間。

（7）各個節點收到時間同步信號后，開始計時并監聽其他節點的信息。

（8）如果節點在自身簇首競爭等待時間t到達前并沒有收到其余節點的簇首競爭成功的消息Succ_MSG，則該節點發送Succ_MSG消息，并成為成為簇頭。

（9）如果節點在自身簇首競爭等待時間t到達前收到了其余節點的競選成功消息Succ_MSG，則此節點廣播Fail_MSG，退出簇頭的競選。

（10）當節點收到其余節點的Fail_MSG后，就把這個節點從鄰居節點表中刪除。

（11）選舉流程結束后，沒有成為簇頭的節點依據節點表中的信息，選擇最近的簇頭并加入其中。

（12）分簇結束后，各個簇頭以Rmax為半徑廣播消息，消息包括簇頭ID、剩余能量、到基站的距離以及簇內剩余能量均值，并收集其他簇頭的消息。

算法完成后，依據鄰居表中的信息，整個網絡被劃分為大小不等的簇，有利于能耗均衡；在得到簇頭競爭時間的過程中，通過平衡當前能量、節點到Sink節點的距離以及簇內節點的平均距離等因素得到其值，最終得到綜合性能最優的簇頭。

2.2 簇間路由的選擇與數據傳輸

首先，簇頭節點根據之前的RSSI得到其與Sink節點的距離d，如果d，則通過單跳的方式，該簇頭直接與Sink節點進行通信。如果d ＞則此時采用多跳的方式。

中繼節點的選擇如下。在成簇階段，簇頭存儲其通信范圍內其余簇的簇頭ID、當前能量、到Sink節點的距離和簇內當前能量均值。根據貪婪算法，簇頭節點在其鄰居簇頭節點集合中。然后，根據最小代價函數得到下一跳的中繼節點RN。參考文獻[14]中代價函數的定義為：

式中，Eave表示簇頭節點si所有鄰居簇頭節點的剩余能量均值；Ere表示簇頭節點si當前剩余的能量；Nnbc( j )表示簇頭sj中成員節點的數目；Nnei(i)表示簇頭si的鄰居簇頭其簇內節點的均值；表示兩節點間的距離；表示節點s距離jSink節點的距離；表示節點s距離Sink節點i的距離；α、β、γ表示加權因子，且α+β+γ=1。因此，cost(RN)=min{cost(i, j)}。當所有簇頭節點完成中繼節點RN的選擇后，開始簇間路由的傳輸。

當路由規則確定后，節點就可以傳輸數據。首先，簇內的非簇頭節點按照時分多路復用即TDMA方式，把數據傳遞給簇首節點；簇內節點都在其分配的時隙內工作，其余時間處于休眠狀態，以降低能耗；簇頭節點接收來自簇內所有節點采集的信息，并對接收信息進行數據融合，然后再選擇簇間中繼節點將融合后的信息以多跳、單跳相結合的路由方式傳遞給Sink節點。改進的路由協議采用分布式策略，目的是找到一條最優路徑，以減少簇間數據傳輸所消耗的能量，最終達到均衡網絡能耗、延長生命周期的目的。

3 實驗仿真

本文通過仿真對改進算法、EEUC協議以及LEACH協議進行比較和模擬。實驗參數如表2所示，傳感器節點隨機分布在檢測區域內，忽略簇頭節點融合數據的能量，協議中其他參數的取值都是通過多次運行模擬得到的最優值。

表2 實驗仿真參數設置

3.1 簇首能耗均衡的分析

簇首能量的消耗是無線傳感器網絡中能量消耗的最主要部分。隨機選取20輪，3種協議的簇首數目相同，對比統計3種協議簇首消耗的能量，結果如圖2所示。

實驗對比結果顯示，本文的路由算法簇頭能耗較為均衡、消耗的能量最低，LEACH協議簇頭能量消耗波動最大，EEUC協議能耗明顯高于改進的協議。究其原因，在于改進的路由協議在簇首選舉過程中綜合考慮了剩余能量、節點到基站的距離以及簇內節點的平均距離等因素，最大程度地保證了選出的簇首節點最優。同時，在不均勻簇劃分過程中綜合考慮了簇首到匯聚節點的距離、鄰居節點的數目、每輪消耗的平均能量以及節點當前的剩余能量等因素，保證了簇首節點能耗的減少。實驗結果表明，改進的路由協議能耗波動最小，有效解決了“熱區”問題，降低了簇首負載，簇首能耗更均衡。

3.2 網絡生命周期的分析

存活節點的變化情況如圖3所示。

圖2 簇首節點能耗的均衡性

圖3 存活節點變化情況

圖3 顯示了3種不同的路由協議隨著仿真時間的增加，網絡中節點存活數量隨輪數增長的變化情況。可以看出，由于節點能耗不均，LEACH協議早早出現了死亡節點，且其第一個死亡的節點與最后一個死亡的節點的時間跨度遠遠大于EEUC和改進協議；EEUC協議優于LEACH協議，但其時間跨度也大于改進的路由協議。時間跨度的大小，表明了整個網絡的均衡程度。可見，改進的路由算法有效均衡了網絡能耗，解決了“熱區”問題，同時改進了WSN內節點的能耗，均衡了簇內網絡能耗，其第一個死亡節點和最后一個死亡節點相對于其他兩個協議都有所延長，延長了整個網絡的壽命。

4 結 語

本文針對“熱區”影響網絡均衡、降低網絡壽命的問題，提出了一種改進的路由協議。改進的路由協議在非均勻分簇半徑的選取中，綜合考慮了簇首到匯聚節點的距離、鄰居節點的數目、每輪消耗的平均能量以及節點當前的剩余能量等因素，更好地控制了簇規模的大小；在簇首選舉過程中，引入時間競爭機制，使競爭時間的大小依據剩余能量、節點到基站的距離以及簇內節點的平均距離等因素來確定，使簇頭選舉過程更加合理，簇頭分布更加均勻，更加均衡了整個簇內的能耗；在簇間路由選擇階段，運用單跳、多跳相結合的方式，其中多跳依據代價函數選擇下一跳節點；同時，引入閾值控制，保證了能量少的節點不會當選中繼節點。仿真結果表明，本文的路由算法很好地解決了網絡“熱區”問題，均衡了網絡能耗，延長了WSN的壽命。

[1] 李亞男,徐夫田,陳學鑫.基于LEACH的WSNs分簇路由優化策略[J].傳感技術學報,2014,27(05):670-674.LI Ya-nan,CHEN Fu-tian,CHEN Xue-xin.WSNs Cluster Routing Optimization Strategy Based on LEACH’s[J].Chinese Journal of Sensors and Actuators,2014,27(05):670-674.

[2] 李建洲,王海濤,陶安.一種能耗均衡的WSN分簇路由協議[J].傳感技術軟件學報,2013,26(03):396-401.LI Jian-zhou,WANG Hai-tao,TAO An.A WSN Clustering Routing Protocol for Energy Consumption Equilibrium[J].Journal of Sensors and Software,2013,26(03):396-401.

[3] Heinzelman W,Chandrakasan A,Balakrishnam H.Energy-Efficient Communication Protocol for Wireless Micro-sensor Networks[C].Proc of the 33rd Conf on System Sciences.Piscataway,2000:3005-3014.

[4] Mhatre V,Rosenberg C.Design Guidelines for Wireless Sensor Networks:Communication,Clustering and Aggregation[J].Ad Hoc Networks,2004,2(01):45-63.

[5] 劉國繁,許多.基于非均勻分簇與路徑優化的WSN路由協議[J].計算機工程與科學,2015,37(08):1492-1497.LIU Guo-fan,XU Duo.WSN Routing Protocol Based on Uneven Clustering and Path Optimization[J].Computer Engineering and Science,2015,37(08):1492-1497.

[6] 魏春娟,楊俊杰,張志美.一種分布式能量有效的無線傳感器網絡協議[J].傳感技術學報,2013,26(07):1014-1018.WEI Chun-juan,YANG Jun-jie,ZHANG Zhi-mei.A Distributed Energy Efficient Wireless Sensor Network Protocol[J].Chinese Journal of Sensors and Actuato rs,2013,26(07):1014-1018.

[7] 孫彥景,林昌林,江海峰.一種能量高效的分布式非均勻分簇路由算法[J].傳感技術學報,2015,28(08):1994-1200.SUN Yan-jing,LIN Chang-lin,JIANG Hai-feng.A Distributed Uneven Clustering Routing Algorithm with High Energy Efficiency[J].Chinese Journal of Sensors and Actuators,2015,28(08):1994-1200.

[8] 陳海南,劉廣聰,吳曉鴿.一種基于遺傳算法與概率轉發的分簇協議[J].計算機科學,2015,42(03):71-73.CHEN Hai-nan,LIU Guang-cong,WU Xiao-ge.A Clustering Portocol Based on Genetic Algorithm and Probability Forwarding[J].Computer Science,2015,42(03):71-73.

[9] 李成法,陳貴海,葉懋.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報,2007,30(01):27-36.LI Cheng-fa,CHEN Gui-hai,YE Mao.A Wireless Sensor Networks Routing Protocol Based on Uneven Clustering[J].Chinese Journal of Computers,2007,30(01):27-36.

[10] 張榮博,曹建富.利用蟻群優化的非均勻分簇無線傳感器網絡路由算法[J].西安交通大學學報,2010,44(06):33-38.ZHANG Rong-bo,CAO Jian-fu.An Uneven Distributed Cluster Wireless Sensor Network Routing Algorithm Using Ant Colony Optimization[J].Journal of Xi’an Jiaotong University,2010,44(06):33-38.

[11] 陸晶,馬悅,吳曉軍.一種基于最小生成樹的非均勻分簇路由算法[J].小型微型計算機系統,2012,33(10):33-38.LU Jing,MA Yue,WU Xiao-jun.A Uneven Clustering Routing Algorithm Based on Minimum Spanning Tree[J].Journal of Chinese Mini-Micro Computer Systems,2012,33(10):33-38.

[12] Jangs,Kimhy,Kimnu,et al.Energy-Efficient Clustering Scheme with Concentric Hierarchy[C].2011 IEEE International RF and Micro wave Conference(RFM),2011:79-82.

[13] 王偉.長距離帶狀無線傳感器網絡路由協議設計[J].計算機工程,2014,40(03):132-136.WANG Wei.Routing Protocol for Long-Distance Ribbon Wireless Sensor Network[J].Computer Engineering,2014,40(03):132-136.

[14] 尚風軍.無線傳感器網絡的分布式能量有效非均勻成簇算法[J].通信學報,2009(10):34-43.SHANG Feng-jun.The Distributed Energy Efficiency Uneven Algorithm of Wireless Sensor Network[J].Journal on Communications,2009(10):34-43.