煤礦井下無線傳感網絡路由協議研究

鄭歡歡，白魚秀

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

0 引言

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

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

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

1 傳統k-medoids算法

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

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

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

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

■2.1 網絡模型

假設本文采用的網絡模型如下：

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

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

（3）節點可以根據接收信號強度計算節點間距離，并根據環境調節自身發射功率。

■2.2 能耗模型

傳感器節點絕大部分能量都消耗在節點間的數據接收和轉發，所以能量的消耗模型采用傳統的無線通信模型，網絡節點發送l bit數據傳輸d m距離消耗的能量Etx為：

網絡節點接收l bit數據傳輸d m距離消耗的能量Erx為：

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

■2.3 算法描述

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

（1）初始化簇頭節點

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

首先根據能量消耗模型計算網絡傳輸一次數據的能耗得出最優簇頭節點數目[6]為：

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

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

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

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

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

（2）更新簇頭節點

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

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

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

替換流程如下：

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

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

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

3 實驗仿真及分析

■3.1 實驗環境

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

表1 實驗參數

■3.2 實驗結果對比

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

圖1 節點死亡數目對比

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

圖2 節點平均剩余能量對比

4 結束語

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