鄭歡歡，白魚(yú)秀

（榆林學(xué)院信息工程學(xué)院，陜西榆林，719000）

0 引言

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

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

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

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

k-medoids 算法是一種優(yōu)化的劃分式聚類(lèi)方法，對(duì)包含異常點(diǎn)的數(shù)據(jù)集能夠?qū)崿F(xiàn)較好的聚類(lèi)劃分，具有較好的健壯性和魯棒性[3]。

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

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

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

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

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

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

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

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

■2.2 能耗模型

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

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

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

■2.3 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

替換流程如下：

a.隨機(jī)選擇一個(gè)普通節(jié)點(diǎn)作為備用簇頭節(jié)點(diǎn)準(zhǔn)備替換原簇頭節(jié)點(diǎn)。

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

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

3 實(shí)驗(yàn)仿真及分析

■3.1 實(shí)驗(yàn)環(huán)境

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

表1 實(shí)驗(yàn)參數(shù)

■3.2 實(shí)驗(yàn)結(jié)果對(duì)比

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

圖1 節(jié)點(diǎn)死亡數(shù)目對(duì)比

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

圖2 節(jié)點(diǎn)平均剩余能量對(duì)比

4 結(jié)束語(yǔ)

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