鄭歡歡，白魚秀

（榆林學院信息工程學院，陜西榆林，719000）

0 引言

近年來礦井安全事故頻發(fā)，因此建立較為完善的煤礦井下安全監(jiān)測系統(tǒng)尤為重要。由于井下環(huán)境復雜、惡劣，如果采用有線設備建設安全監(jiān)測系統(tǒng)，不僅費時費力、成本較高，而且一旦有線設備受損也容易造成系統(tǒng)的功能受限[1]。

無線傳感器網(wǎng)絡由于強大的移動性和自組織性更適合應用于煤礦井下的特殊環(huán)境。將無線傳感器網(wǎng)絡應用于煤礦井下環(huán)境還有兩個問題要解決：傳感器節(jié)點受限于能量有限，無線傳感器網(wǎng)絡中節(jié)點能耗不均會導致節(jié)點過快死亡，影響網(wǎng)絡的生存時間和整體性能；煤礦井下長距離帶狀環(huán)境，容易造成“熱區(qū)”問題，導致節(jié)點能耗不均[2]。因此需要為WSN建立合理的網(wǎng)絡拓撲結構，以降低網(wǎng)絡的整體能耗、延長網(wǎng)絡的生存周期、提高網(wǎng)絡性能和擴展性等。

本文采用k-medoids聚類算法對無線傳感器網(wǎng)絡的拓撲結構進行簇類劃分，并在初始化簇頭節(jié)點時舍棄傳統(tǒng)算法中的隨機選擇，采用領域自適應半徑的方法進行簇頭節(jié)點選擇，綜合考慮了簇頭節(jié)點的剩余能量因子和用鄰居節(jié)點數(shù)計算出的近似密度因子；替換新簇頭節(jié)點時考慮節(jié)點剩余能量，較好的均衡了無線傳感器網(wǎng)絡節(jié)點的能量，延長了網(wǎng)絡的生存周期。

1 傳統(tǒng)k-medoids算法

k-medoids算法是一種優(yōu)化的劃分式聚類方法，對包含異常點的數(shù)據(jù)集能夠實現(xiàn)較好的聚類劃分，具有較好的健壯性和魯棒性[3]。

k-medoids算法常用的劃分方法是選取實際節(jié)點作為簇頭節(jié)點，普通節(jié)點根據(jù)與簇頭節(jié)點的相似性度量加入相應的簇中。其算法的核心思想是：從n個節(jié)點中隨機選擇k個節(jié)點作為簇頭節(jié)點，其余節(jié)點按照就近原則分配到k個簇中；通過反復迭代使用非簇頭節(jié)點代替簇頭節(jié)點，從而得到最佳分簇效果。

雖然k-medoids算法比起其他聚類算法能夠得到較均勻的分簇結構，有效改善孤立點的簇類劃分，一定程度上改善了節(jié)點之間的能耗問題。但也存在不少缺點：（1）在初始化簇頭節(jié)點時采用隨機選擇的方法，導致不同環(huán)境中分簇效果不穩(wěn)定；（2）更新簇頭節(jié)點為參考當前能量值等其他標準，導致迭代計算工作量較大。因此本文分析研究傳統(tǒng)k-medoids算法的基礎上，提出了基于能耗均衡的k-medoids算法。

2 基于能耗均衡的k-medoids算法

■2.1 網(wǎng)絡模型

假設本文采用的網(wǎng)絡模型如下：

（1）在一個大小為L×W的實驗區(qū)域內有n個傳感器節(jié)點和1個匯聚節(jié)點，其中匯聚節(jié)點位于網(wǎng)絡的一端。

（2）網(wǎng)絡中的匯聚節(jié)點能量不受限制，其余傳感器節(jié)點有唯一的標識ID，具有相同的功能屬性。

（3）節(jié)點可以根據(jù)接收信號強度計算節(jié)點間距離，并根據(jù)環(huán)境調節(jié)自身發(fā)射功率。

■2.2 能耗模型

傳感器節(jié)點絕大部分能量都消耗在節(jié)點間的數(shù)據(jù)接收和轉發(fā)，所以能量的消耗模型采用傳統(tǒng)的無線通信模型，網(wǎng)絡節(jié)點發(fā)送l bit數(shù)據(jù)傳輸d m距離消耗的能量Etx為：

網(wǎng)絡節(jié)點接收l bit數(shù)據(jù)傳輸d m距離消耗的能量Erx為：

上式中，Eelec、εfs和εamp都是常數(shù)，分別表示信號處理時的能量消耗、自由空間模型下放大器功耗和多徑衰減模型下放大器功耗。

■2.3 算法描述

本算法主要分為3個步驟，首先是在無線傳感器網(wǎng)絡內選擇初始化簇頭節(jié)點；然后剩余節(jié)點根據(jù)就近原則選擇加入相似度最高的簇中；為了最大程度的優(yōu)化分簇結果，因此要按照替換準則選擇其余節(jié)點優(yōu)化分簇結果，如果分簇結果改變就需要重新回到第二步繼續(xù)迭代優(yōu)化，直到分簇結果不發(fā)生改變，則說明分簇結果已達到最優(yōu)。以下詳細描述初始化簇頭節(jié)點和更新簇頭節(jié)點算法詳情。

（1）初始化簇頭節(jié)點

由于傳統(tǒng)k-medoids算法隨機選取k個節(jié)點作為簇頭節(jié)點，再通過不斷地迭代優(yōu)化聚類，不僅浪費大量迭代時間，而且由于簇頭節(jié)點選擇的隨機性，容易是聚類陷入局部最優(yōu)。因此本算法采用領域自適應半徑的方法[4]選取初始簇頭節(jié)點，綜合考慮了簇頭節(jié)點的剩余能量因子和用鄰居節(jié)點數(shù)計算出的近似密度因子，可以縮短選擇初始化簇頭節(jié)點的時間[5]。

首先根據(jù)能量消耗模型計算網(wǎng)絡傳輸一次數(shù)據(jù)的能耗得出最優(yōu)簇頭節(jié)點數(shù)目[6]為：

根據(jù)煤礦井下巷道的長距離帶狀環(huán)境，設置傳感器的領域半徑Rch計算方法見式（4）。

為了更好地均衡能耗，本文采用領域自適應半徑，因此在計算中綜合考慮了傳感器節(jié)點的剩余能量和鄰居節(jié)點數(shù)。故根據(jù)下式計算得出：

其中，Ec是傳感器節(jié)點的當前剩余能量，Eavg表示當前網(wǎng)絡的平均能量。Nbrn是本節(jié)點在網(wǎng)絡中相鄰節(jié)點的數(shù)目。α和β為控制權重參數(shù)，且相加之和為1。

最后，設置假設所有節(jié)點的中心位置為O，將以O為中心，以Rc為半徑確定中心圓。k-medoids選取的初始化簇頭節(jié)點是實際節(jié)點，因此在中心園上均勻的選擇k個節(jié)點作為初始簇頭節(jié)點。

通過式（5）計算得到的自適應半徑，用節(jié)點的剩余能量和初始能量比例作為能量因子可以計算出節(jié)點消耗能量的速率，而通過本節(jié)點的鄰居節(jié)點和所有節(jié)點的比例可以近似得到本節(jié)點周圍的節(jié)點密度因子，因此可知如果節(jié)點耗能越少、節(jié)點密度越稀疏會得到較大的領域半徑。這樣在自適應半徑圓上選取的初始化簇頭節(jié)點大大降低了算法的迭代時間，更加高效。

（2）更新簇頭節(jié)點

分簇完成后，需要通過迭代優(yōu)化分簇，更新簇頭節(jié)點實現(xiàn)普通節(jié)點和簇頭節(jié)點之間的距離最小化。更新簇頭節(jié)點的替換準則應滿足[7]下式：

其中x是簇Ci中的普通節(jié)點，mi表示Ci中的簇頭節(jié)點。

假設S={S1, S2,…,Sj,…Sk-1,Sk},S表示無線傳感器網(wǎng)絡中所有簇頭節(jié)點的集合。從網(wǎng)絡中隨機選擇一個普通節(jié)點Sr作為備用簇頭節(jié)點準備替換原簇頭節(jié)點Sj,。根據(jù)式（6）給出的替換準則計算備用簇頭節(jié)點的替換準則，如果該值小于原簇頭節(jié)點的替換準則值且備用簇頭節(jié)點的剩余能量大于此時網(wǎng)絡中所有節(jié)點的平均剩余能量值時，那么就用該備用簇頭節(jié)點替換原簇頭節(jié)點，即簇頭節(jié)點集合變?yōu)镾={S1, S2,…,Sr,…Sk-1,Sk}。

替換流程如下：

a.隨機選擇一個普通節(jié)點作為備用簇頭節(jié)點準備替換原簇頭節(jié)點。

b.計算該備用簇頭節(jié)點的替換準則，如果該節(jié)點的替換準則小于原簇頭節(jié)點的替換準則，且備用簇頭節(jié)點剩余能量小于網(wǎng)絡中所有節(jié)點的平均剩余能量，那么就用備用簇頭節(jié)點替換原簇頭節(jié)點，否則就釋放掉備用簇頭節(jié)點。

c.如果原簇頭節(jié)點都沒有替換，則表示已得到最優(yōu)化分簇；否則根據(jù)替換的新簇頭節(jié)點重新劃分簇，返回a迭代尋找最佳劃分簇。

3 實驗仿真及分析

■3.1 實驗環(huán)境

根據(jù)理論分析，通過matlab搭建實驗仿真環(huán)境，對本文協(xié)議進行仿真，并參照LEACH、EEUC協(xié)議進行對比。實驗參數(shù)設置如表1所示。

表1 實驗參數(shù)

■3.2 實驗結果對比

圖1表示三種算法在節(jié)點死亡數(shù)目的對比，LEACH在500輪后開始出現(xiàn)死亡節(jié)點，EEUC和本文算法在1100輪后開始出現(xiàn)死亡節(jié)點，而之后EEUC死亡節(jié)點數(shù)目劇增，本文算法死亡節(jié)點數(shù)目變化緩慢，直到2000輪左右，本文算法的死亡節(jié)點數(shù)目都是最少。說明改進的協(xié)議能夠有效的均衡網(wǎng)絡節(jié)點的能量消耗，最大程度保障網(wǎng)絡性能，延長網(wǎng)絡生命周期。

圖1 節(jié)點死亡數(shù)目對比

圖2從節(jié)點平均剩余能量方面做對比，節(jié)點平均剩余能量是循環(huán)工作一定輪次后取節(jié)點的剩余能量平均值，可以看出本文改進協(xié)議的節(jié)點平均剩余能量高于其他對比協(xié)議，說明該協(xié)議能較好的均衡節(jié)點能耗。

圖2 節(jié)點平均剩余能量對比

4 結束語

本文提出了基于k-medoids算法應用于礦井巷道環(huán)境下的能夠均衡網(wǎng)絡能耗的路由協(xié)議。改進協(xié)議在初始化簇頭節(jié)點時采用領域自適應半徑的方法，綜合考慮了簇頭節(jié)點的剩余能量因子和用鄰居節(jié)點數(shù)計算出的近似密度因子，可以縮短選擇初始化簇頭節(jié)點的時間；更新簇頭節(jié)點時把剩余能量也作為更新條件，從而達到均衡網(wǎng)絡節(jié)點能耗的目的。實驗仿真結果表明，改進協(xié)議在應用于長距離帶狀環(huán)境下，在節(jié)點死亡個數(shù)和平均剩余能量方面的性能優(yōu)于LEACH和EEUC協(xié)議，有效均衡了網(wǎng)絡能量消耗，延長了網(wǎng)絡生命周期。