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

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

1 引言

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

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

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

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型假設(shè)如下：

假設(shè)1 實驗區(qū)域范圍為M×M，N個傳感器節(jié)點隨機(jī)分布在該區(qū)域內(nèi)。

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

假設(shè)3 所有傳感器節(jié)點有自己的ID，可以知道自身的剩余能量和位置，可對接收到的數(shù)據(jù)進(jìn)行融合。

假設(shè)4 所有節(jié)點不可移動，隨機(jī)分布后無人為干預(yù)。

假設(shè)5 鏈路對稱，節(jié)點可以根據(jù)接收到的信號強(qiáng)度估算兩者之間的距離，節(jié)點的發(fā)射功率和通信半徑可以自行調(diào)控。

假設(shè)6 節(jié)點以固定速率監(jiān)測環(huán)境，定期傳輸收集到的數(shù)據(jù)。

2.2 能耗模型

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

Figure 1 Energy consumption model圖1 能耗模型

傳感器節(jié)點發(fā)送kbit數(shù)據(jù)消耗的能量ETx(k,d)為：

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

(1)

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

(2)

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

ERx(k)=k×Eelec

(3)

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

EMx(k)=k×Eda

(4)

其中，Eda為數(shù)據(jù)融合率。為了求出最優(yōu)簇頭個數(shù)，假定簇頭向基站傳輸?shù)哪芎哪Ｐ褪嵌鄰剿ヂ湫诺滥Ｐ停貎?nèi)普通節(jié)點向簇頭傳輸?shù)哪芎哪Ｐ褪亲杂煽臻g信道模型，監(jiān)測區(qū)域大小為M×M，分布節(jié)點總數(shù)為N，則根據(jù)式(1)～式(4)和文獻(xiàn)[5]，計算出最優(yōu)簇頭個數(shù)kopt的值，如式(5)所示：

(5)

3 EBRAA算法

3.1 網(wǎng)絡(luò)初始階段

在網(wǎng)絡(luò)初始階段，EBRAA算法采用確定簇數(shù)的AGNES 算法對節(jié)點進(jìn)行分簇。開始時將每個對象作為1個初始聚類簇，即將監(jiān)測區(qū)域的N個節(jié)點看做N個簇，然后在算法運(yùn)行的每一步中根據(jù)簇間相似度將這些簇一步步地合并直至達(dá)到設(shè)定簇數(shù)。

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

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

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

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

Step 1 將每個節(jié)點當(dāng)成1個初始聚類簇Cj,j=1,2,…,N。

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

(6)

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

Figure 4 Protocol run rounds圖4 協(xié)議運(yùn)行輪次

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

Step 4 重復(fù)Step 2和Step 3，直到簇的個數(shù)滿足最優(yōu)簇頭個數(shù)kopt,表示完成均勻分簇，網(wǎng)絡(luò)初始階段結(jié)束。

3.2 分布式簇頭選舉階段

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

(7)

其中，Eres為節(jié)點剩余能量，Dto-BS為節(jié)點到基站的距離，w1為簇內(nèi)節(jié)點剩余能量的權(quán)重因子，w2為簇內(nèi)節(jié)點到基站距離的權(quán)重因子。

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

(8)

其中，Di為簇內(nèi)節(jié)點i與基站距離。

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

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

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

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

3.3 數(shù)據(jù)傳輸階段

數(shù)據(jù)傳輸階段使用改進(jìn)的Dijkstra算法，考慮節(jié)點剩余能量和與基站距離因素，計算出最短路徑后，簇頭間采用多跳路由對數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)。

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

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

(9)

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

Eres≥Elim∧ds-BS≥d0

(10)

改進(jìn)的Dijkstra算法具體步驟如下所示：

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

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

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

Step 4 重復(fù)Step3，直到所有簇頭節(jié)點都加入到節(jié)點集合node_id中，即|node_id|=kopt+1，此時，BS到網(wǎng)絡(luò)中所有簇頭節(jié)點的最短路徑已經(jīng)求出；

Step 5 求出BS到簇內(nèi)所有簇頭節(jié)點最短路徑后，簇頭按照此最短路徑多跳傳輸數(shù)據(jù)至BS。

改進(jìn)的Dijkstra算法過程如圖5所示。

Figure 5 Improved Dijkstra algorithm圖5 改進(jìn)的Dijkstra算法

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

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

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

計算出最短路徑后，各節(jié)點反向傳送數(shù)據(jù)到BS，其路徑分別為A→BS，B→D→BS，C→B→D→BS，D→BS，E→BS，F(xiàn)→BS，G→BS。

4 仿真及性能分析

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

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

圖6為分簇后簇頭分布圖。可以看出，LEACH算法的簇頭個數(shù)隨著輪數(shù)隨機(jī)取值，且分布位置不均勻，會出現(xiàn)簇頭集中分布和分布在網(wǎng)絡(luò)邊緣的情況；而EBRAA和KBECRA算法的簇頭分布更加均勻，簇結(jié)構(gòu)更合理，且簇頭個數(shù)為設(shè)定的最佳簇頭數(shù)kopt，使得簇頭個數(shù)穩(wěn)定。

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

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

Figure 7 Number of surviving nodes圖7 存活節(jié)點數(shù)

圖8為網(wǎng)絡(luò)運(yùn)行中死亡節(jié)點數(shù)隨著輪數(shù)的增加而變化的趨勢圖。從圖8中可以看出，LEACH算法第1個節(jié)點死亡發(fā)生在300輪左右，50%節(jié)點死亡發(fā)生在650輪左右，全部節(jié)點死亡發(fā)生在1 050輪左右；KBECRA算法第1個節(jié)點死亡發(fā)生在500輪左右，50%節(jié)點死亡發(fā)生在823輪左右，全部節(jié)點死亡發(fā)生在1 162輪左右；EBRAA算法第1個節(jié)點死亡發(fā)生在500輪左右，50%節(jié)點死亡發(fā)生在890輪左右，全部節(jié)點死亡發(fā)生在1 250輪左右。

Figure 8 Number of dead nodes圖8 死亡節(jié)點數(shù)

圖9為網(wǎng)絡(luò)運(yùn)行中節(jié)點總能耗隨著輪數(shù)增加而變化的趨勢圖。從圖9中可以看出，LEACH、KBECRA和EBRAA算法能耗為50%時分別發(fā)生在295輪，392輪和440輪左右，能耗為100%時分別發(fā)生在1 030輪，1 159輪和1 230輪左右。

Figure 9 Total energy consumption of nodes圖9 節(jié)點總能耗

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

5 結(jié)束語

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