基于非均勻分簇與路徑優化的 WSN路由協議*

劉國繁，許 多

（1.湖南工程學院電氣信息學院，湖南 湘潭 411104；2.湘潭大學信息工程學院，湖南 湘潭 411105）

基于非均勻分簇與路徑優化的 WSN路由協議*

劉國繁1，許 多2

（1.湖南工程學院電氣信息學院，湖南 湘潭 411104；2.湘潭大學信息工程學院，湖南 湘潭 411105）

在無線傳感網絡中，傳感節點的能量有限性，使得能量有效利用成為其“熱點”問題。針對LEACH協議簇頭的隨機選擇，導致成簇不合理或簇頭節點加速死亡，簇首與基站直接通信能量消耗大的問題。提出了一種高能效路由協議 UCPO。該協議根據最佳簇頭個數劃分區域，綜合考慮簇內能量消耗和節點剩余能量選擇簇頭，以多跳方式完成數據的發送。仿真表明，改進協議顯著減少整個網絡能量消耗，延長了網絡的生存周期。

LEACH；非均勻分簇；路徑優化；最佳簇頭數；Dijkstra算法

1 引言

無線傳感網絡WSN（Wireless Sensor Network）是當今的一個熱門領域，它集成了分布式算法、信號處理、網絡與協議、數據庫和信息管理技術、嵌入式系統［1］。網絡中的傳感節點能夠自組網絡［2］，將監測數據從偏遠或危險區域匯集給用戶。由于節點能量一般無法補充，為了盡量延長網絡生存時間，如何使用網絡節點能量成為該領域研究的一個重要內 容［3，4］。WSN中 的能 量 消耗［5］主 要 包括通信能耗、計算存儲能耗、數據采集能耗，其中通信能量消耗所占比重最大，因此如何減少通信的能耗成為關鍵問題。

LEACH（Low Energy Adaptive Clustering Hierarchy）協議［6］是較早提出來的無線傳感器網絡自適應集簇分層路由協議。近年來，很多研究學者對LEACH協議進行了改進，主要有以下三類：改 進閾 值 公式［7］、簇 內 優 化［8］和 通 信路 徑 優化［9～11］。這些改進協議 從不同 方 面減 少 了無 線傳感網絡節點能量消耗。

大量研究表明，通信過程中簇頭的選擇方式及位置、簇頭與基站的通信路徑能夠減少節點能量消耗。本文從能耗角度分析LEACH協議和LEACH-MC［12］協議，針對LEACH協議簇頭的隨機選擇可能導致簇頭剩余能量不足、簇頭數波動和分布不合理，以及簇頭與基站直接通信導致簇頭能耗較大，提出了一種基于非均勻分簇與路徑優化UCPO（Uneven Clustering and Path Optimizing）的無線傳感網絡路由協議，該協議能有效提高WSN的生存時間。與其他改進協議一樣，本協議不考慮網絡的時延和丟包。

2 非均勻分簇與路徑優化

2.1 非均勻分簇

2.1.1 最優簇頭數

對于LEACH協議，簇頭數目不同，整個網絡的能耗也不同，且總能耗差距比較明顯。因此，尋找總能耗最小的最佳簇頭數很有意義。為了便于分析，我們假設每輪所選簇頭個數為k，監測區域大小為M*M，分布的節點總數為N，于是，平均每個簇的節點個數為N/k，每個簇中有1個簇頭和（N/k）—1個成員節點。每個簇頭從成員節點接收采集的數據，經過融合后發送到基站。假定簇頭向基站傳輸的能耗模型是多路徑損耗模式［6］，則簇的能量消耗ECH如下：

其中，l表示每次傳輸數 據的比特 數，dto-BS表示簇頭與基站之間的距離，Eelec是 發送 或接 收一 個字節所消耗的能量，EDA為數 據融 合 率，εamp為 功率 放大器的放大倍數。

對于成員節點，采集完數據，進行融合處理并發送給簇頭，每個成員節點一次向簇頭發送一幀數據。成員節點與簇頭的距離在同一簇內一般較近，不會超出一階無線電模式的自由空間能耗閾值d0，所以普通節點向簇頭發送數據的能量消耗Enon-CH如下：

其中，dto-CH表示該成 員節 點到 本 簇簇 頭 的距 離，εfs為功率放大器倍數。

假設把監測區域均勻劃分，那么所劃分的每個虛擬小區域的面積是M2/k。設隨機布放的一個節點坐標為ρ（x，y），則簇內節點到簇頭的距離平方期望值如下：

為了便于計算分析，用一個與虛擬小區域面積相同的圓作等價變換，這個圓的面積為M2/k，則由圓面積公式可得該圓的半徑是：

把上式所得的R代入到式（3），經過化簡、計算可得：

如果區域內節點分布密度是均勻的，可以得到：

將上面所得的ρ代入式（5）得：

將得到的dto-CH平方期望值代入到式（2）得：

一個簇內的能量消耗由簇頭能耗和成員節點能耗兩部分組成，因此，一個 簇的能量 消耗Ecluster如下：

整個監測區域是由k個簇組成，那么整個區域的能耗Etotal如下：

將每個簇的能耗代入式（10），可得：

根據式（11），可以求出整個監測區域能耗最小時的k值，它就是最佳簇頭數kopt，如下式：

2.1.2 區域劃分

根據上面的計算，UCPO協議將監測區域劃分為若干虛擬小區，每個虛擬小區選擇一個節點作為簇頭，虛擬小區的個數為式（12）確定的最佳簇頭數。UCPO協議采用非均勻分簇，即各虛擬小區面積不等，簇的大小也不同。距離基站較近的虛擬小區，面積相對減小，簇也相應較小；距離基站較遠的虛擬小區，面積相對增大，簇也相應較大。

假設在一個100×100的正方形區域，隨機分布100個無線傳感器節點，基站位置在 （50，220），由式（12）可得，最佳簇頭數為5，于是，將整個監測區域劃分成5個虛擬子區域，對每個虛擬區域中的節點都作標記node_area。如果節點在子區域i（i=1～5），則該節點的node_area=i。采用非均勻分簇，以整個區域上下方向的中線為分割線，將整個區域分成上下兩個部分，再將靠近基站的上部分分成三個大小相等的子區域，下部分分成兩個大小相同的子區域，具體劃分如圖1所示。

Figure 1 Areas division圖1 區域的劃分

2.1.3 簇頭選擇

在上述虛擬區域中，設某個區域有j個節點，其中任一個節點i的坐標為 （xi，yi），可以求出該區域j個節點的“中心”Center的坐標如下：

所得“中心”位于虛擬區域的中心，選擇距離“中心”位置最近的節點作為該區域的候選簇頭，檢查該節點的剩余能量是否超過了該區域節點剩余能量平均值Eaver：

如果該節點的剩余能量大于Eaver，則當選為簇頭；否則，選擇距離“中心”位置次近的節點作為候選簇頭，如此循環直至在該區域找到簇頭。

選出簇頭后，UCPO協議本“輪”的后續運行

接收節點收到l比特數據需要消耗的能量ERX如下：

式（15）、式（16）中，Eelec表示節點發送或接收l比特數據所需要消耗的能量，εfs、εamp分別表示自由空間模型和多徑衰減模型下功率放大器倍數。

UCPO協議的多跳方式采用了Dijkstra算法思想。Dijkstra算法原理如下：

（1）N為每輪選出的簇頭總數，V為除路徑起始簇頭O外的其他簇頭集，S為已求出最短路徑的簇頭集，E（i）表示簇頭到基站的能量消耗，E（i，j）表示從簇頭i到簇頭j的能量消耗，node_id保存最佳路徑簇頭的id，node_id的初始值為簇頭O的id。

（2）在V中找出簇頭j，使之符合E（O，j）= Min｛E|vj∈V｝，則簇頭j就是簇頭O最小能量消耗的下一跳簇頭，路徑就是E（O，j），將簇頭j并入集合S：S=S∪｛j｝。

（3）找出下一跳簇頭節點j后，從簇頭j出發繼續尋找下一跳簇頭n，使簇頭n發送數據到簇頭節點j能耗最小。

（4）重復步驟（2）、（3）直至到達基站為止。

按UCPO協議，其簇頭總數由式（12）確定，從距離基站最遠的簇頭到基站的數據傳輸不需要經過太多中繼簇頭，因此我們對Dijkstra算法進行了適當改進。改進的Dijkstra算法如下：

假設某條路徑的起始簇頭節點仍為O節點，中繼節點為r節點，E（O，j）表示從起始簇頭到中繼簇頭的能量消耗，E（O）表示從簇頭O到基站的能耗，D是最佳路徑的節點標號集。

（1）初始化：將較遠子區域的簇頭節點O標號與LEACH協議相同。在下一“輪”簇頭選擇時，再按上述簇頭選擇的方法選擇新一“輪”簇頭運行，直至網絡失效。

2.2 路徑優化

UCPO協議從簇頭到基站的數據傳輸采用多跳傳送。設通信的兩簇頭節點距離為d，如果距離d＜d0，則發送節點的能耗模型是自由空間損耗模型；若d≥d0，則發送節點的能耗模型是多路徑衰減模型。因此，發送節點和接收節點間的距離為d時，發 送 和 接 收l比 特 數 據，發送節點的 能 耗［6］ETX如下：放入D中，較近子區域的簇頭直接與基站通信。

（2）計算其它簇頭r到簇頭O的能量消耗值，存入E（O，r）中，再計算中繼簇頭r到基站的能量消耗，存入E（r）中。

（3）選擇能耗E（O，r）+E（r）最小的路徑進行傳輸。

（4）如此循環進行，直至所有簇頭的數據向基站發送完成。然后，進入下一輪的運行。

與Dijkstra算法相比，改進算法能避免所有的數據都通過距離基站最近的簇頭轉發，防止距離基站最近的簇頭過早死亡。如圖2所示，五角星代表基站，如果按照Dijkstra算法傳輸，簇頭A向基站發送數據，簇頭A首先選擇距離最近的簇頭B作為下一跳簇頭，簇頭B則選擇最近的簇頭C為下一跳簇頭，簇頭C直接向基站發送數據，則傳輸路徑是A→B→C→基站。而采用改進算法，簇頭A則會選擇B或者C作為下一跳的簇頭，再由下一跳簇頭向基站傳輸數據，如果A→B→基站這條路徑的能耗小于A→C→基站，則選擇A→B→基站這條路徑傳輸數據。

Figure 2 Data transmission path of the improved Dijkstra algorithm圖2 Dijkstra改進算法的數據傳輸路徑

3 仿真結果和分析

我們采用Matlab仿真軟件對LEACH、LEACH-MC和UCPO協議進行比較分析。對比了LEACH協議簇頭數目和改進協議簇頭數目的

穩定 性、分 布 位 置 的 均勻性，計 算 LEACH、LEACH-MC和UCPO三種協議的簇頭存活數，分析它 們 的能 量 效率，證 明 UCPO協 議 優 于LEACH協議和LEACH-MC協議。實驗中所用的環境參數如表1所示，其能耗模型的相關參數取自文獻［13］。

Table 1 Experiment parameters表1 實驗參數

Figure 3 Cluster heads'number of the LEACH rounds圖3 LEACH協議各輪簇頭個數

由圖3可知，LEACH協議的簇頭產生的波動性較大，簇頭數目最少是2，最多可達8。UCPO協議根據公式（12）確定最優簇頭數為5，這種方法不存在簇頭數目的波動問題。由前面的分析計算可知，簇頭個數為最優簇頭數，能夠使整個網絡的能量消耗始終保持在較低水平。

Figure 4 Cluster heads distribution of a LEACH round圖4 LEACH協議某輪簇頭分布

圖4是LEACH協議某輪的簇頭（用實心圓表示）分布圖，圖5是UCPO協議的某輪簇頭（用實心圓表示）分布圖。通過對比可看出，LEACH協議的簇頭數為3，簇頭偏離了最佳簇頭數，且分布在整個監測區域的右側，左邊的區域完全沒有簇頭，分布很不合理。UCPO協議簇頭的數目一直保持最優，簇頭分布比較均勻，簇頭與簇頭之間的距離合適，能夠改善簇頭能耗，從而有效降低整個網絡的能量消耗，延長網絡生存時間。

Figure 5 Cluster heads distribution of a UCPO round圖5 UCPO協議某輪簇頭分布

三種協議存活節點數對比如圖6所示。由圖6可知，LEACH-MC優于LEACH協議，UCPO協議優于前兩者。一是因為簇頭數大部分時間保持為最佳簇頭數，使整個網絡的能耗大部分階段處在較低水平；二是因為簇頭靠近簇“中心”位置，對成簇有利，簇內數據傳輸的能量消耗與簇頭位于其他位置相比，能耗要小很多；三是因為簇頭與基站的通信改用了多跳通信，減小了簇頭的能量消耗。

Figure 6 Survival node number of the three protocols圖6 三種協議的存活節點數

LEACH、LEACH-MC和UCPO協議死亡相同數目節點的運行輪數對比如圖7所示。由圖7可知，三個協議的第一個死亡節點分別發生在395輪、595輪和855輪，死亡一半節點分別發生在490輪、789輪和1 023輪，網絡節點完全死亡分別發生在701輪、1 012輪和1 103輪。UCPO協議與LEACH協議相比，在各個階段分別提升了460輪、533輪和402輪，與LEACH-MC比較各個階段分別提升了260輪、234輪和91輪。可以看出，UCPO協議的網絡生存時間，比LEACH協議和LEACH-MC協議的網絡生存時間，都有較明顯的提高。

Figure 7 Comparison in the amount of operation rounds with the same number of dead nodes圖7 死亡相同數目節點的運行輪數對比

4 結束語

本文提出了一種基于非均勻分簇和路徑優化的無線傳感器網絡路由協議，其核心思想是根據最佳簇頭數，將整個網絡劃分成與之個數相等的虛擬子區域，并適當減小靠近基站的子區域面積，增加較遠子區域面積。在子區域中，每個區域選擇剩余能量高于該區域剩余能量平均值且靠近區域“中心”位置的節點擔任簇頭，簇頭與基站的多跳路徑依據改進的Dijkstra算法，選擇總能耗最小的路徑傳輸數據。仿真實驗表明，UCPO協議優化了整個網絡的能量消耗，特別是減少了簇內的能耗，與

LEACH協議及LEACH-MC協議相比，有效延長了網絡的存活時間。下一步的工作是對非均勻分簇進行動態研究，路徑選擇考慮采用更加節能的方法。

［1］ Kumar N，Kaur J.Improved LEACH protocol for wireless sensor networks［C］∥Proc of the 7th International Conference on Wireless Communications，Networking and Mobile Computing（WiCOM），2011：1.

［2］ Li Bin，Wang Wen-jie，Yin Qin-ye，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.

［3］ Vural S，Ekici E.On multihop distances in wireless sensor networks with random node locations［J］.IEEE Transactions on Mobile Computing，2010，4（9）：540-552.

［4］ Lin Zhang-xiao，Wei Liang，Yu Hai-bin，et al.Survey of transmission scheduling methods in wireless sensor networks ［J］.Journal on Communications，2012，33（5）：143-157.

［5］ Li Cheng-fa，Chen Gui-hai，Ye Mao，et al.An uneven cluster-based routing protocol for wireless sensor networks［J］. Chinese Journal of Computers，2007，30（1）：27-36.（in Chi-nese）

［6］ Heinzelman W B，Chandrakasan A，Balakrishnan H.Energyefficient communication protocol for wireless microsensor networks［C］∥Proc of the 33rd Annual Hawaii International Conference on System Sciences，2000：1.

［7］ Zhang Deng-yong，Xiong Hao-xiang，Li Feng，et al.The improvement of wireless sensor networks LEACH protocol based on the energy efficiency［J］.Journal of Changsha University of Science and Technology，2007，9（4）：79-82.（in Chinese）

［8］ Bai Feng-e，Wang Li-li，Ma Yan-yan，et al.Algorithm analysis of routing protocols LEACH for wireless sensor networks［J］.Journal of Taiyuan University of Technology，2009，40（4）：15-19.（in Chinese）

［9］ Fan Yi-ming，Chen Qing-zhang，Yu Jian-jun.New routing protocol for wireless sensor networks based on the minimum spanning tree of the cluster head［J］.Chinese Journal of Sensors and Actuators，2008，12（24）：47-50.（in Chinese）

［10］ Zhang De-gan，Li Guang，Zheng Ke，et al.An energy-balanced routing method based on forward-aware factor for wireless sensor networks［J］.IEEE Transactions on Industrial Informatics，2014，1（10）：766-773.

［11］ Lindsey S，Raghavendra C S.PEGASIS：Power-efficient gathering in sensor information systems［C］∥Proc of IEEE Aerospace Conference Proceedings，2002：1125-1130.

［12］ Luo Bing，Huang Yu-qing.An improved multistage clustering algorithm of LEACH protocol［J］.Computer Engineering，2013，39（6）：99-102.（in Chinese）

［13］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

附中文參考文獻：

［5］ 李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30（1）：27-36.

［7］ 章登勇，熊昊翔，李峰，等.基于節能的無線傳感器網絡LEACH協議改進［J］.長沙理工大學學報，2007，9（4）：79-82.

［8］ 白鳳 娥，王 莉莉，馬 艷 艷，等.無線 傳 感 器 網絡 路 由 協 議LEACH的算法分析［J］.太原理工大學學報，2009，40（4）：15-19.

［9］ 范一鳴，陳慶章，余建軍.一種基于簇首生成樹的無線傳感器網絡分層路由協議［J］.傳感技術學報，2008，12（24）：47-50.

［12］ 羅冰，黃玉清.一種LEACH協議的多級分簇改進算法［J］.計算機工程，2013，39（6）：99-102.

劉國繁（1959），男，湖南華容人，教授，研究方向為計算機應用技術。E-mail：Liugf59@foxmail.com

LIU Guo-fan，born in 1959，professor，his research interest includes computer application technology.

許多（1988 ），男，湖南衡陽人，碩士生，研究方向為無線傳感網絡。E-mail：406875627@qq.com

XU Duo，born in 1988，MS candidate，his research interest includes wireless sensor network.

A routing protocol based on uneven clustering and path optimization in wireless sensor networks

LIU Guo-fan1，XU Duo2
（1.School of Electrical Information，Hunan Institute of Engineering，Xiangtan 411104；
2.College of Information Engineering，Xiangtan University，Xiangtan 411105，China）

Due to the limited energy of sensor nodes in wireless sensor networks，how to use energy efficiently has become a hot topic.The random selection of the LEACH's cluster heads leads to unreasonable cluster composition，accelerates the death of cluster heads，and the communication between cluster heads and the base station causes huge energy consumption.To solve the problems listed above，in this paper we put forward a routing protocol with higher energy efficiency，in which the area is divided based on the number of the best cluster heads.The cluster heads are selected with comprehensive consideration of the energy consumption within cluster heads and the rest energy of the nodes，and the energy is transmitted by multi-hops.Simulation results show that the improved protocol can reduce the energy consumption of the whole network dramatically and effectively prolong the network's lifetime.

LEACH；uneven clustering；path optimization；optimal number of cluster head；Dijkstra algorithm

TP301

A

10.3969/j.issn.1007-130X.2015.08.012

1007-130X（2015）08-1492-06

2014-08-07；

2014-10-27

湖南省科技計劃資助項目（2012SK3173）

通信地址：411104湖南省湘潭市福星東路88號湖南工程學院電氣信息學院

Address：School of Electrical Information，Hunan Institute of Engineering，88 Fuxing Rd East，Xiangtan 411104，Hunan，P.R.China