基于AGNES聚類的能耗均衡WSNs優化路由算法*

茍平章，張 芬，毛 剛，賈向東

(西北師范大學計算機科學與工程學院,甘肅 蘭州 730070)

1 引言

無線傳感器網絡WSNs(Wireless Sensor Networks)是由隨機部署在監測區域內或附近具有通信能力、計算能力和數據處理能力的大量傳感器節點組成，通過節點多跳傳輸數據與基站進行通信的自組織方式網絡[1]。由于WSNs中節點一般通過電池供電，自身攜帶能量有限，并且電池不便更換，因此提高能量使用效率，降低網絡能量消耗，延長網絡生命周期成為WSNs研究的重要課題。

WSNs分簇路由協議中，最典型的是LEACH(Low Energy Adaptive Clustering Hierarchy)協議[2]，該協議以隨機選舉簇頭的方式將網絡分成若干簇，按輪的形式周期性選舉簇頭，以達到網絡中能耗均衡的目的。但是，該協議存在簇頭個數隨機，簇頭有可能分布于稀疏節點位置或者網絡邊緣位置的問題，簇頭與基站間采用直接單跳通信，會導致簇頭能耗過高，加速網絡死亡。LEACH-C協議[3]采用集中式控制，由基站決定簇頭個數，采用模擬退火算法選舉出最優簇頭，但未考慮簇的分布位置問題。LEACH-GA(Genetic Algorithm based on LEACH)協議[4]基于遺傳算法優化簇頭選舉，但數據傳輸階段與LEACH協議相同。通過對LEACH、LEACH-C和LEACH-GA協議的性能對比分析[5]可知，LEACH-C和LEACH-GA協議相對于LEACH協議在能耗方面得到了提升。LEACH-improved路由算法[6]通過加入間距因子、剩余能量因子和節點密度因子來改進LEACH協議的簇頭選舉公式，使簇頭的選舉更加合理，但簇分布不均勻。KBECRA(Balanced Energy Consumption Routing Algorithm based on K-means)路由算法[7]采用K-means聚類算法使成簇更加合理，并且通過選舉主、副簇頭，節省了能耗，但是K-means算法隨機選擇聚類中心會導致局部最優的問題。KUCR(Uniform Clustering Routing based on K-means)路由算法[8]簇內根據節點剩余能量和距離選舉簇頭，但未考慮能量和距離對簇頭選舉的影響因子不同，導致簇頭選舉不合理的問題。UCPO(Uneven Clustering and Path Optimization)路由算法[9]根據最佳簇頭個數劃分區域，在數據傳輸階段使用Dijkstra算法，降低了數據傳輸能耗，但在路徑選擇上未考慮中間節點的剩余能量和與基站的距離因素。基于粒子群優化算法的分簇路由協議[10]優化了分簇，但在數據傳輸時仍然采用單跳通信方式，增加了數據傳輸能耗。KAF(K-means And FAH)分簇算法[11]基于K-means和模糊綜合評價方法，有效減少了能耗。IFCEER(Energy Efficient Routing based on Improved Firefly Clustering)路由算法[12]采用改進螢火蟲聚類算法進行分簇，使分簇合理，但數據傳輸路徑未優化。UCR(Unequal Cluster-based Routing)協議[13]采用競爭半徑實現非均勻分簇，使用貪婪算法優化路由選擇，但該算法只考慮當前節點到達基站的代價，忽略當前已花費的代價，所以找到的傳輸路徑并非最優路徑。基于能量約束的簇首多跳算法[14]，在數據傳輸階段采用Prim最小生成樹算法，考慮節點剩余能量，使簇頭之間形成一條多跳的最優路徑，但未考慮距離對中間節點的影響。基于距離的二層中繼節點選擇閾值算法[15]實現了一種在二層網絡中根據與基站最近距離選擇中繼節點的新技術，但僅考慮了距離因素。LECP-FC(Low Energy Cluster Protocol-Fuzzy Control)協議[16]通過考慮影響因子修改LEACH中簇頭選舉公式來降低網絡能耗。文獻[17]通過分析不同維數觀測矩陣對Hybrid-CS發送數據影響，求出較優化的觀測矩陣維數，從而降低網絡能耗。文獻[18]提出I_AOMDV(Improved Ad-hoc On-demand Multipath Distance Vector)協議，在路由發現階段不再使用發生擁塞和低能量的節點，以均衡能耗，在路由維護階段使用HELLO信息交換鄰居節點的“剩余能量”和“隊列長度”，從而使I_AOMDV協議更適應靜態WSNs的數據傳輸。文獻[19]提出一種聚類算法減少無線傳感器網絡的能耗，創建一種cluster-tree分簇路由結構的傳感器網絡，實現了均衡能耗、延長網絡生命周期的目標。

綜合以上研究，本文提出基于AGNES聚類的能耗均衡WSNs優化路由算法EBRAA(Energy-Balanced Routing Algorithm based on AGNES clustering)。在網絡初始階段，將最優簇頭個數作為AGNES算法的終止條件，完成網絡的均勻分簇；集中分簇后，在簇頭選舉階段，采取簇內分布式選舉簇頭策略，各簇內根據節點剩余能量、與基站距離及兩者的權重因子優化選舉簇頭；在數據傳輸階段，采用優化后的Dijkstra算法，并加入能量閾值公式和距離閾值公式，以基站為源節點，將滿足閾值公式的簇頭節點放入節點集合后，計算基站到其他簇頭節點的最短路徑，優化了簇頭間多跳傳輸數據的路徑。EBRAA算法使簇的分布更加均勻，簇頭選舉更加合理，減少路徑傳輸能耗，均衡網絡能耗，達到延長網絡生命周期的目標。

2 系統模型

2.1 網絡模型

網絡模型假設如下：

假設1 實驗區域范圍為M×M，N個傳感器節點隨機分布在該區域內。

假設2 所有傳感器節點具有相同的初始能量、處理能力和通信能力。

假設3 所有傳感器節點有自己的ID，可以知道自身的剩余能量和位置，可對接收到的數據進行融合。

假設4 所有節點不可移動，隨機分布后無人為干預。

假設5 鏈路對稱，節點可以根據接收到的信號強度估算兩者之間的距離，節點的發射功率和通信半徑可以自行調控。

假設6 節點以固定速率監測環境，定期傳輸收集到的數據。

2.2 能耗模型

能耗模型采用和LEACH協議相同的1階無線電通信能耗模型，該模型如圖1所示。

Figure 1 Energy consumption model圖1 能耗模型

傳感器節點發送kbit數據消耗的能量ETx(k,d)為：

ETx(k,d)=ETx-elec(k)+ETx-amp(k,d)=

(1)

其中，ETx-elec為發射電路消耗的能量，ETx-amp為發射功率放大器消耗的能量，k為發送數據的比特數，d為數據傳輸的距離，Eelec為發射電路處理1 bit數據所消耗的能量，εfs為自由空間信道模型下發送功率放大器向單位面積發射1 bit數據消耗的能量，εamp為多徑衰落信道模型下發送功率放大器向單位面積發射1bit數據消耗的能量。通過式(1)計算出d0的臨界值：

(2)

節點接收kbit數據需要消耗的能量ERx(k)為：

ERx(k)=k×Eelec

(3)

簇頭對kbit數據進行融合需要消耗的能量EMx(k)為：

EMx(k)=k×Eda

(4)

其中，Eda為數據融合率。為了求出最優簇頭個數，假定簇頭向基站傳輸的能耗模型是多徑衰落信道模型，簇內普通節點向簇頭傳輸的能耗模型是自由空間信道模型，監測區域大小為M×M，分布節點總數為N，則根據式(1)～式(4)和文獻[5]，計算出最優簇頭個數kopt的值，如式(5)所示：

(5)

3 EBRAA算法

3.1 網絡初始階段

在網絡初始階段，EBRAA算法采用確定簇數的AGNES 算法對節點進行分簇。開始時將每個對象作為1個初始聚類簇，即將監測區域的N個節點看做N個簇，然后在算法運行的每一步中根據簇間相似度將這些簇一步步地合并直至達到設定簇數。

2個簇間的相似度(也稱為簇間距離)有多種不同的計算方法。其中，單鏈度量(最小距離)是計算2個不同簇之間任意2點的最短距離；完全鏈度量(最大距離)是計算2個不同簇之間任意2點之間的最長距離；組平均度量(平均距離)是計算2個簇之間任意2點的平均距離。因為單鏈度量和完全鏈度量代表了簇間相似度的2個極端，所以本文采用組平均度量davg作為相似度計算方法。相似度計算方法如圖2所示，圖2a為單鏈度量，圖2b為完全鏈度量，圖2c為組平均度量。

Figure 2 Similarity calculation method圖2 相似度計算方法

采用圖2c的度量方法分簇過程為，找出距離最近的2個聚類簇Ci和Cj進行合并，合并過程一直迭代進行，直到對象個數滿足簇數目kopt，則完成分簇。簇數目為kopt的AGNES 算法具體步驟如下所示：

輸入：包含N個節點的數據集，初始節點之間的距離度量dini，終止條件的簇個數為根據式(5)計算出的kopt。

Step 1 將每個節點當成1個初始聚類簇Cj,j=1,2,…,N。

Step 2 計算任意2個簇的平均距離davg，即Ci、Cj中所有節點的平均距離，求出節點之間距離的相似矩陣。計算公式如式(6)所示：

(6)

其中，Ci、Cj為2個簇；|Ci|、|Cj|為2個簇中節點個數；p為Ci簇中節點；q為Cj簇中節點。根據式(6)計算出所有聚類簇的平均距離davg后得到節點之間距離的相似矩陣。

Figure 4 Protocol run rounds圖4 協議運行輪次

Step 3 使用相似矩陣查找平均距離最小的2個簇(即最相似的2個簇)Ci和Cj，合并2個簇為1個簇，即Cij=Ci∪Cj，生成新的簇集合Cij，將聚類簇Cj重編號為Cj-1，簇的個數通過合并更新，通過式(6)重新計算新創建的簇Cij到其他所有簇Cr(r≠i∨r≠j)的距離，從而更新簇間距離的相似矩陣。

Step 4 重復Step 2和Step 3，直到簇的個數滿足最優簇頭個數kopt,表示完成均勻分簇，網絡初始階段結束。

3.2 分布式簇頭選舉階段

在選舉簇頭階段，分簇后產生的kopt個簇在簇內進行分布式簇頭選舉，因為節點位置固定且無人為干預，所以每一輪結束后，簇內普通節點將自己剩余能量信息告知簇頭節點，簇頭計算每個節點的競爭值W，計算公式如式(7)所示：

(7)

其中，Eres為節點剩余能量，Dto-BS為節點到基站的距離，w1為簇內節點剩余能量的權重因子，w2為簇內節點到基站距離的權重因子。

所有節點距基站的平均距離Davg的計算如下所示：

(8)

其中，Di為簇內節點i與基站距離。

通過比較Dto-BS和Davg的大小來確定w1和w2的值。經過實驗驗證，當Dto-BS>Davg時，w1=4/5，w2=1/5，此時節點剩余能量因素對簇頭選舉影響較大；當Dto-BS≤Davg時,w1=2/5，w2=3/5，此時節點與基站距離因素對簇頭選舉影響較大。加入權重因子可以增加離基站較遠的節點成為簇頭節點的概率，減少離基站較近的節點過早死亡的現象，均衡整個網絡的能耗。

將簇頭節點的競爭值Wch與簇內其他普通節點的競爭值Wi相比較，Wch和Wi的值按照式(7)計算，如果Wch

Figure 3 Distributed cluster head contention圖3 分布式簇頭競爭

由于分布式簇頭選舉不同于LEACH協議中每輪都需要更換簇頭節點，所以更加節省能量，使能量效率提高。協議運行輪次如圖4所示。

3.3 數據傳輸階段

數據傳輸階段使用改進的Dijkstra算法，考慮節點剩余能量和與基站距離因素，計算出最短路徑后，簇頭間采用多跳路由對數據進行轉發。

Dijkstra算法將網絡作為1個帶權圖G=(V,E)，BS和簇頭節點為圖中的頂點集合，頂點之間距離為權值。將BS作為源節點，創建node_id和T2個節點集合，開始時，node_id節點集合只包含BS源節點，其他簇頭節點ID存放在T節點集合中；將距離BS最近的T節點集合中的節點ID，即權值最小的節點加入node_id節點集合，其他節點ID繼續存在T集合中；迭代求權值最小節點的ID，并將其放入node_id節點集合中；最終求得源節點BS到帶權圖G中其他簇頭節點的最小權值之和的路徑，得到多跳最小能耗路由。

在改進的Dijkstra算法中，設置1個能量閾值Elim，計算公式如式(9)所示：

(9)

其中，Ei是節點i的剩余能量，w3是調整因子。隨著輪數的增加，網絡平均能量降低，適當減小調整因子w3，使Elim得到調整，防止路由多跳中間節點數量過少導致跳距過大的問題。Dijkstra在選擇下一跳中間簇頭節點時，考慮中間節點s的剩余能量Eres和與基站的距離ds-BS，如式(10) 所示：

Eres≥Elim∧ds-BS≥d0

(10)

改進的Dijkstra算法具體步驟如下所示：

Step 1 初始化節點集合。設置2個節點集合T和node_id，節點集合node_id中存放已經找到最短路徑的節點ID，節點集合T中存放當前還未找到最短路徑的節點ID，即為kopt個節點數量，kopt為每輪選舉的簇頭總數；

Step 2 開始時，節點集合node_id中只有1個節點，即基站BS作為源點v0。設置1個二維數組distance[i][j]表示節點i和節點j之間的距離，一維數組dist[i]表示從源節點v0到節點i的最短特殊路徑長度；

Step 3 在節點集合T中選舉當前長度最短的1條路徑(v0,…,vi)，如果節點vi滿足式(10)，則將節點vi加入到節點集合node_id中，即node_id=node_id∪{vi}，并修改源節點v0到T中各節點的最短特殊路徑長度，即dist[i]，此時并非全部節點的最短路徑，繼續下列步驟；

Step 4 重復Step3，直到所有簇頭節點都加入到節點集合node_id中，即|node_id|=kopt+1，此時，BS到網絡中所有簇頭節點的最短路徑已經求出；

Step 5 求出BS到簇內所有簇頭節點最短路徑后，簇頭按照此最短路徑多跳傳輸數據至BS。

改進的Dijkstra算法過程如圖5所示。

Figure 5 Improved Dijkstra algorithm圖5 改進的Dijkstra算法

圖5中，A、B、C、D、E、F、G均為簇頭節點。假設E、F和G節點到BS的距離d1、d2和d3均小于式(2)的d0，不滿足式(10),所以E、F和G節點不需要參與Dijkstra算法，選擇與BS直接通信。其余節點A、B、C、D與BS通過改進的Dijkstra算法計算出最短路徑后，多跳地傳輸數據，假設A、B、C、D節點均滿足式(10)，其過程如表1所示。

Table 1 Shortest path iteration表1 最短路徑迭代過程

由表1可得，BS到A節點最短路徑為BS→A，BS到B節點最短路徑為BS→D→B，BS到C節點最短路徑為BS→D→B→C，BS到D節點最短路徑為BS→D。

計算出最短路徑后，各節點反向傳送數據到BS，其路徑分別為A→BS，B→D→BS，C→B→D→BS，D→BS，E→BS，F→BS，G→BS。

4 仿真及性能分析

本文利用Matlab從簇頭分布位置、節點的存活數、節點的死亡數和節點總能耗等方面，對基于LEACH協議的算法(簡稱LEACH算法)、KBECRA和EBRAA算法進行仿真比較，仿真參數設置如表2所示。

Table 2 Experiment parameters表2 實驗參數

圖6為分簇后簇頭分布圖。可以看出，LEACH算法的簇頭個數隨著輪數隨機取值，且分布位置不均勻，會出現簇頭集中分布和分布在網絡邊緣的情況；而EBRAA和KBECRA算法的簇頭分布更加均勻，簇結構更合理，且簇頭個數為設定的最佳簇頭數kopt，使得簇頭個數穩定。

Figure 6 Cluster head distribution map圖6 簇頭分布圖

圖7為網絡運行中節點的存活數隨著輪數的增加而變化的趨勢圖。從圖7中可以看出，LEACH算法在300輪左右時存活節點數開始減少，在655輪左右時剩余50%存活節點，在1 047輪左右時存活節點為0；KBECRA算法在500輪左右時存活節點數開始減少，在824輪左右時剩余50%存活節點，在1 160輪左右時存活節點數為0；EBRAA算法在500輪左右時存活節點數開始減少，在885輪左右時剩余50%存活節點，在1 255輪左右時存活節點數為0。

Figure 7 Number of surviving nodes圖7 存活節點數

圖8為網絡運行中死亡節點數隨著輪數的增加而變化的趨勢圖。從圖8中可以看出，LEACH算法第1個節點死亡發生在300輪左右，50%節點死亡發生在650輪左右，全部節點死亡發生在1 050輪左右；KBECRA算法第1個節點死亡發生在500輪左右，50%節點死亡發生在823輪左右，全部節點死亡發生在1 162輪左右；EBRAA算法第1個節點死亡發生在500輪左右，50%節點死亡發生在890輪左右，全部節點死亡發生在1 250輪左右。

Figure 8 Number of dead nodes圖8 死亡節點數

圖9為網絡運行中節點總能耗隨著輪數增加而變化的趨勢圖。從圖9中可以看出，LEACH、KBECRA和EBRAA算法能耗為50%時分別發生在295輪，392輪和440輪左右，能耗為100%時分別發生在1 030輪，1 159輪和1 230輪左右。

Figure 9 Total energy consumption of nodes圖9 節點總能耗

綜上所述，EBRAA算法簇頭分布更加合理，網絡生命周期比LEACH和KBECRA算法的長。

5 結束語

本文在分析研究分簇路由算法LEACH和基于K-means聚類路由算法KBECRA基礎上，針對其分簇不合理、簇頭選舉隨機和單跳傳輸路由造成網絡能耗不均的問題，提出一種基于AGNES聚類的能耗均衡WSNs優化路由算法(EBRAA)。通過確定簇數的AGNES聚類算法使簇的分布更加均勻，穩定了簇頭個數，避免了簇頭分布過于集中或者分布在網絡邊緣位置的情況。在簇內考慮能量和距離因素，以分布式方式選舉和更換簇頭，減少了每輪都需要選舉簇頭的能量消耗。采用改進后的Dijkstra算法產生簇頭間多跳的最短傳輸路徑，路徑得到優化，最終提高了節點能量的利用率，均衡了網絡能耗，延長了網絡的生命周期。仿真結果表明，EBRAA算法相較于LEACH和基于K-means分簇路由算法KBECRA，延長了網絡生命周期，提升了網絡能量利用率。