劉國繁，許 多

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

基于非均勻分簇與路徑優(yōu)化的 WSN路由協(xié)議*

劉國繁1，許 多2

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

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

LEACH；非均勻分簇；路徑優(yōu)化；最佳簇頭數(shù)；Dijkstra算法

1 引言

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

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

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

2 非均勻分簇與路徑優(yōu)化

2.1 非均勻分簇

2.1.1 最優(yōu)簇頭數(shù)

對于LEACH協(xié)議，簇頭數(shù)目不同，整個網(wǎng)絡(luò)的能耗也不同，且總能耗差距比較明顯。因此，尋找總能耗最小的最佳簇頭數(shù)很有意義。為了便于分析，我們假設(shè)每輪所選簇頭個數(shù)為k，監(jiān)測區(qū)域大小為M*M，分布的節(jié)點總數(shù)為N，于是，平均每個簇的節(jié)點個數(shù)為N/k，每個簇中有1個簇頭和（N/k）—1個成員節(jié)點。每個簇頭從成員節(jié)點接收采集的數(shù)據(jù)，經(jīng)過融合后發(fā)送到基站。假定簇頭向基站傳輸?shù)哪芎哪Ｐ褪嵌嗦窂綋p耗模式［6］，則簇的能量消耗ECH如下：

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

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

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

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

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

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

如果區(qū)域內(nèi)節(jié)點分布密度是均勻的，可以得到：

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

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

一個簇內(nèi)的能量消耗由簇頭能耗和成員節(jié)點能耗兩部分組成，因此，一個 簇的能量 消耗Ecluster如下：

整個監(jiān)測區(qū)域是由k個簇組成，那么整個區(qū)域的能耗Etotal如下：

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

根據(jù)式（11），可以求出整個監(jiān)測區(qū)域能耗最小時的k值，它就是最佳簇頭數(shù)kopt，如下式：

2.1.2 區(qū)域劃分

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

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

Figure 1 Areas division圖1 區(qū)域的劃分

2.1.3 簇頭選擇

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

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

如果該節(jié)點的剩余能量大于Eaver，則當(dāng)選為簇頭；否則，選擇距離“中心”位置次近的節(jié)點作為候選簇頭，如此循環(huán)直至在該區(qū)域找到簇頭。

選出簇頭后，UCPO協(xié)議本“輪”的后續(xù)運行

接收節(jié)點收到l比特數(shù)據(jù)需要消耗的能量ERX如下：

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

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

（1）N為每輪選出的簇頭總數(shù)，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）找出下一跳簇頭節(jié)點j后，從簇頭j出發(fā)繼續(xù)尋找下一跳簇頭n，使簇頭n發(fā)送數(shù)據(jù)到簇頭節(jié)點j能耗最小。

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

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

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

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

2.2 路徑優(yōu)化

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

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

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

（4）如此循環(huán)進行，直至所有簇頭的數(shù)據(jù)向基站發(fā)送完成。然后，進入下一輪的運行。

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

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

3 仿真結(jié)果和分析

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

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

Table 1 Experiment parameters表1 實驗參數(shù)

Figure 3 Cluster heads'number of the LEACH rounds圖3 LEACH協(xié)議各輪簇頭個數(shù)

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

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

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

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

三種協(xié)議存活節(jié)點數(shù)對比如圖6所示。由圖6可知，LEACH-MC優(yōu)于LEACH協(xié)議，UCPO協(xié)議優(yōu)于前兩者。一是因為簇頭數(shù)大部分時間保持為最佳簇頭數(shù)，使整個網(wǎng)絡(luò)的能耗大部分階段處在較低水平；二是因為簇頭靠近簇“中心”位置，對成簇有利，簇內(nèi)數(shù)據(jù)傳輸?shù)哪芰肯呐c簇頭位于其他位置相比，能耗要小很多；三是因為簇頭與基站的通信改用了多跳通信，減小了簇頭的能量消耗。

Figure 6 Survival node number of the three protocols圖6 三種協(xié)議的存活節(jié)點數(shù)

LEACH、LEACH-MC和UCPO協(xié)議死亡相同數(shù)目節(jié)點的運行輪數(shù)對比如圖7所示。由圖7可知，三個協(xié)議的第一個死亡節(jié)點分別發(fā)生在395輪、595輪和855輪，死亡一半節(jié)點分別發(fā)生在490輪、789輪和1 023輪，網(wǎng)絡(luò)節(jié)點完全死亡分別發(fā)生在701輪、1 012輪和1 103輪。UCPO協(xié)議與LEACH協(xié)議相比，在各個階段分別提升了460輪、533輪和402輪，與LEACH-MC比較各個階段分別提升了260輪、234輪和91輪?？梢钥闯觯琔CPO協(xié)議的網(wǎng)絡(luò)生存時間，比LEACH協(xié)議和LEACH-MC協(xié)議的網(wǎng)絡(luò)生存時間，都有較明顯的提高。

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

4 結(jié)束語

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

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

［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］ 李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計算機學(xué)報，2007，30（1）：27-36.

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

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

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

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

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

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

許多（1988 ），男，湖南衡陽人，碩士生，研究方向為無線傳感網(wǎng)絡(luò)。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號湖南工程學(xué)院電氣信息學(xué)院

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