王宗山，丁洪偉+，李 波，李 浩，李艾珊

(1.云南大學(xué) 信息學(xué)院，云南 昆明 650500；2.復(fù)旦大學(xué) 電子信息科學(xué)與技術(shù)，上海 200433)

0 引 言

隨著無(wú)線通信技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)得到了越來(lái)越廣泛的關(guān)注，WSNs通常用于監(jiān)測(cè)指定區(qū)域的環(huán)境[1]，但傳感器節(jié)點(diǎn)能量有限且無(wú)法更換電池。因此，設(shè)計(jì)一種高效節(jié)能的路由算法尤為重要[2-4]。Heinzelman W等提出的經(jīng)典分簇路由協(xié)議LEACH[5]，通過(guò)周期性輪換簇首平衡網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)性能。但LEACH隨機(jī)選取簇首導(dǎo)致分簇不理想，縮短了網(wǎng)絡(luò)生命周期。文獻(xiàn)[6]對(duì)LEACH進(jìn)行改進(jìn)，提出QABC算法，算法考慮節(jié)點(diǎn)的能量與地理位置提出適應(yīng)度函數(shù)，采用量子人工蜂群算法確定最優(yōu)解作為簇首，從而形成網(wǎng)絡(luò)分簇。QABC算法使簇首分布更均勻，成簇更合理，進(jìn)一步提升了網(wǎng)絡(luò)性能。文獻(xiàn)[7]提出HEED算法。依據(jù)節(jié)點(diǎn)的剩余能量，迭代選取能量較高的節(jié)點(diǎn)作為簇首，保證簇首分布均勻。文獻(xiàn)[8]提出PROPOSED協(xié)議，采用“先聚類分簇，后選舉簇首”的方式，首先采用粒子群算法分割網(wǎng)絡(luò)區(qū)域，然后在每個(gè)區(qū)域內(nèi)選舉簇首。文獻(xiàn)[9]在非均勻聚類的基礎(chǔ)上引入多跳，通過(guò)合理的方式選擇中繼節(jié)點(diǎn)，有效均衡了網(wǎng)絡(luò)能耗。文獻(xiàn)[10]引入模糊規(guī)則，結(jié)合節(jié)點(diǎn)的剩余能量和位置信息提出FLECR算法。文獻(xiàn)[11]引入“網(wǎng)格”概念，并考慮節(jié)點(diǎn)剩余能量完成簇首選舉，顯著提升了網(wǎng)絡(luò)生存期。文獻(xiàn)[12]引入蟻群算法，結(jié)合節(jié)點(diǎn)的地理位置和剩余能量，提出一種基于蟻群的新路由算法。文獻(xiàn)[13]提出基于K-Means的均勻分簇路由(KUCR)算法，在網(wǎng)絡(luò)初始化時(shí)期利用K-Means分簇，在每個(gè)簇內(nèi)考慮節(jié)點(diǎn)位置坐標(biāo)和剩余能量選舉簇首。文獻(xiàn)[14]提出基于Fuzzy C-Means的改進(jìn)LEACH協(xié)議，初始階段利用Fuzzy C-Means對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)聚類分簇，在每個(gè)簇內(nèi)利用考慮節(jié)點(diǎn)剩余能量的LEACH算法完成簇首選舉和數(shù)據(jù)傳輸。

本文將遺傳算法(GA)優(yōu)化的K-Medoids聚類用于WSNs，提出了能量高效的均勻分簇路由協(xié)議—GAKMDCR協(xié)議，通過(guò)選舉高質(zhì)量簇首、改善通信機(jī)制的方式，在均衡網(wǎng)絡(luò)能耗的同時(shí)，提高了網(wǎng)絡(luò)吞吐量。

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

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

假設(shè)所研究的WSNs具有以下性質(zhì)：

(1)監(jiān)測(cè)區(qū)域內(nèi)的N個(gè)節(jié)點(diǎn)同構(gòu)且固定，基站位于無(wú)線傳感網(wǎng)內(nèi)部；

(2)所有節(jié)點(diǎn)均具備身份標(biāo)識(shí)(ID)，且各不相同；

(3)任意節(jié)點(diǎn)能夠根據(jù)接收到的信號(hào)強(qiáng)度計(jì)算與發(fā)送端的距離，能夠感知自身剩余能量、計(jì)算自成為簇首的輪數(shù)；

(4)任意節(jié)點(diǎn)能夠直接與基站通信，能夠進(jìn)行數(shù)據(jù)去冗處理，具備擔(dān)任簇首的能力；

(5)網(wǎng)絡(luò)部署完成后，再無(wú)人為干涉。

1.2 能耗模型

本文采用的無(wú)線電能量模型與Heinzelman等討論的模型相同[15]。圖1是該模型傳輸數(shù)據(jù)的基本流程。如圖1所示，根據(jù)發(fā)射端到接收端的距離與閾值dinit的大小關(guān)系，選擇性使用自由空間信道模型和多路徑衰減模型。節(jié)點(diǎn)發(fā)送數(shù)據(jù)所需能量的數(shù)學(xué)表達(dá)式為[16,17]

(1)

(2)

圖1 數(shù)據(jù)傳輸過(guò)程與能量消耗

節(jié)點(diǎn)接收數(shù)據(jù)所需能量的數(shù)學(xué)表達(dá)式為

ERX=k×Eelec

(3)

其中，d為無(wú)線電的傳輸距離，k是傳輸?shù)谋忍財(cái)?shù)，Eelec是無(wú)線通信的發(fā)送端/接收端每發(fā)送/接收1比特?cái)?shù)據(jù)所需要的能量。εfs和εmp為兩種信道模型中功率放大電路的能量耗散系數(shù)。

2 GAKMDCR算法

GAKMDCR算法中，網(wǎng)絡(luò)按輪運(yùn)行。網(wǎng)絡(luò)初始化時(shí)期，基站根據(jù)節(jié)點(diǎn)的地理位置，采用遺傳算法優(yōu)化的K-Medoids迭代計(jì)算，形成h個(gè)固定的分簇。首輪簇首由簇內(nèi)中心點(diǎn)擔(dān)任。此后每輪，由當(dāng)前簇首綜合考慮簇內(nèi)節(jié)點(diǎn)狀態(tài)決定是否更換簇首，如需更換，指定條件最優(yōu)的節(jié)點(diǎn)成為下輪簇首。這樣就避免了因頻繁更換簇首帶來(lái)的能量消耗，有效延長(zhǎng)了網(wǎng)絡(luò)生命周期。

2.1 簇的構(gòu)建

2.1.1 最優(yōu)簇?cái)?shù)

K-Medoids需要指定分簇?cái)?shù)目，基于上述網(wǎng)絡(luò)型和能耗模型，網(wǎng)絡(luò)運(yùn)行一輪消耗的能量為[18-20]

(4)

其中，DtoBS為節(jié)點(diǎn)到基站的距離，EDA為簇首融合1 bit冗余數(shù)據(jù)帶來(lái)的能耗。

對(duì)聚類數(shù)h求偏導(dǎo)，令偏導(dǎo)數(shù)為零，可求得使網(wǎng)絡(luò)能耗最低的h。求得的最優(yōu)簇?cái)?shù)為

(5)

2.1.2 K-Medoids聚類算法

K-Medoids聚類算法是一種基于代表對(duì)象的劃分方法，用絕對(duì)誤差標(biāo)準(zhǔn)來(lái)定義一個(gè)類簇的緊湊程度[21]。每次迭代后選取簇內(nèi)的實(shí)際樣本點(diǎn)作為聚類中心，解決了K-Means算法對(duì)“噪聲”敏感的問(wèn)題。絕對(duì)誤差公式為

(6)

其中，p為ci簇中的樣本點(diǎn)，oi為ci簇的中心點(diǎn)。基于K-Medoids的成簇步驟見(jiàn)表1。

2.1.3 遺傳算法優(yōu)化K-Medoids初始中心點(diǎn)

K-Medoids雖然解決了K-Means算法對(duì)噪聲數(shù)據(jù)和孤立點(diǎn)敏感的問(wèn)題，但其性能仍受初始中心點(diǎn)的影響，易陷入局部最優(yōu)解。為解決這一問(wèn)題，用遺傳算法改善K-Me-doids的初始中心點(diǎn)，提高聚類質(zhì)量。遺傳算法優(yōu)化K-Me-doids的步驟[22,23]為：

表1 基于K-Medoids的成簇步驟

(1)初始化參數(shù)(種群數(shù)目p、聚類數(shù)目h、交叉概率pc、變異概率pm、最大迭代次數(shù))；

(2)初始化種群，每個(gè)個(gè)體編碼代表一種聚類結(jié)果；

(3)對(duì)個(gè)體進(jìn)行K-Medoids迭代計(jì)算并評(píng)價(jià)適應(yīng)度；

(4)進(jìn)行遺傳算法中的相應(yīng)操作，產(chǎn)生新一代種群，判斷是否可以終止迭代；

(5)如果可以終止迭代，輸出K-Medoids的初始中心點(diǎn)。否則，轉(zhuǎn)至步驟(3)。

其中，適應(yīng)度函數(shù)設(shè)計(jì)為

(7)

(8)

其中，Jc為類內(nèi)距離，zij為第i條染色體所表示的第j個(gè)聚類cj的中心點(diǎn)，p為cj中的其余點(diǎn)。從式(7)可以看出，類內(nèi)緊湊程度越大，類內(nèi)距離Jc的值就越小，適應(yīng)度也越大。這樣保證了一個(gè)聚類結(jié)果的適應(yīng)度越大，聚類效果越理想。編碼方式與文獻(xiàn)[24]相同，從{1,2,…h(huán)…,n-1,n}中隨機(jī)選取一組值α={α1,…αi…αq}代表一條染色體，αi代表一個(gè)聚類中心點(diǎn)，α中元素的個(gè)數(shù)代表聚類數(shù)目。

2.2 簇首選舉

成簇之后，首輪簇首由簇內(nèi)中心點(diǎn)擔(dān)任。從第二輪開(kāi)始，當(dāng)前簇首基于節(jié)點(diǎn)剩余能量、到基站的距離、與簇內(nèi)其余節(jié)點(diǎn)的緊湊程度、擔(dān)任過(guò)簇首的輪次4個(gè)因素決定是否需要更新簇首，若需要，則指定條件最優(yōu)的節(jié)點(diǎn)擔(dān)任下輪簇首。

節(jié)點(diǎn)的剩余能量因素設(shè)計(jì)為

(9)

式中：f1(i)表示在當(dāng)前輪次，節(jié)點(diǎn)i的能量值比上該節(jié)點(diǎn)所在第j簇的平均能量值。f1(i)與節(jié)點(diǎn)i的當(dāng)前能量值成正比，f1(i)越大，表示節(jié)點(diǎn)i在當(dāng)前輪次的能量值越高。

網(wǎng)絡(luò)節(jié)點(diǎn)與基站的位置關(guān)系因素設(shè)計(jì)為

(10)

其中，dtoBS(i)為節(jié)點(diǎn)i到基站的距離，dtoBS(max)為節(jié)點(diǎn)i所在簇內(nèi)，任意節(jié)點(diǎn)到基站距離的最大值。比值f2(i)越大，表示節(jié)點(diǎn)i距離基站越近，與基站通信時(shí)的能量消耗越小。

與簇內(nèi)其余節(jié)點(diǎn)的緊湊程度因素設(shè)計(jì)為

(11)

其中，dtoCH(i)為節(jié)點(diǎn)i到簇首的距離，dtoCH(ave)為節(jié)點(diǎn)i所在簇內(nèi)所有節(jié)點(diǎn)到簇首的平均距離。當(dāng)前簇首的dtoCH取值為dtoCH(ave)。這樣設(shè)計(jì)的好處是：當(dāng)前簇首由上輪簇首綜合考慮后選定，這就意味著當(dāng)前簇首與簇內(nèi)其余節(jié)點(diǎn)的緊湊程度比較理想。利用到當(dāng)前簇首的距離作為評(píng)判標(biāo)準(zhǔn)，可以有效衡量各節(jié)點(diǎn)與簇內(nèi)其余節(jié)點(diǎn)的緊湊程度。比值f3(i)越大，節(jié)點(diǎn)i與簇內(nèi)其余節(jié)點(diǎn)相對(duì)更緊湊。

擔(dān)任過(guò)簇首節(jié)點(diǎn)的輪次因素設(shè)計(jì)為

(12)

其中，rtotal表示網(wǎng)絡(luò)運(yùn)行過(guò)的輪數(shù)，rCH(i)表示節(jié)點(diǎn)i擔(dān)任簇首的輪數(shù)。擔(dān)任簇首次數(shù)越多，比值f4(i)越小，則節(jié)點(diǎn)i再次當(dāng)選簇首的概率相對(duì)較小。這樣很好的將網(wǎng)絡(luò)能耗分?jǐn)偟矫恳粋€(gè)節(jié)點(diǎn)

f=αf1+βf2+λf3+μf4

(13)

其中，α、β、λ、μ為權(quán)重參數(shù)，用于調(diào)整4個(gè)因素的重要程度，且滿足和為1。隨著網(wǎng)絡(luò)的運(yùn)行，根據(jù)4個(gè)因素對(duì)網(wǎng)絡(luò)影響力的改變動(dòng)態(tài)調(diào)整權(quán)重參數(shù)，以選出最優(yōu)簇首。權(quán)重參數(shù)的更新公式設(shè)計(jì)為

α=(Emax-Emin)/(Eres(i))

(14)

β=λ=μ=(1-α)/3

(15)

其中，Eres(i)為節(jié)點(diǎn)i的剩余能量，Emax和Emin分別為節(jié)點(diǎn)i所在簇內(nèi)任意節(jié)點(diǎn)剩余能量的最大和最小值。這樣設(shè)計(jì)的好處是：網(wǎng)絡(luò)不斷運(yùn)行，節(jié)點(diǎn)剩余能量因素愈加重要，節(jié)點(diǎn)的剩余能量不斷減少，得到的α值動(dòng)態(tài)增大，即能量因素越來(lái)越重要。同時(shí)，簇內(nèi)節(jié)點(diǎn)的剩余能量?jī)蓸O分化越嚴(yán)重，對(duì)應(yīng)式(14)中的分子越大，該簇節(jié)點(diǎn)得到的α值也越大，能量因素在該簇的簇首選舉中所占比重更大。這樣就避免了能量消耗集中于部分節(jié)點(diǎn)使網(wǎng)絡(luò)生存期減短。

每輪的最后階段，簇首根據(jù)節(jié)點(diǎn)發(fā)來(lái)的位置坐標(biāo)、剩余能量和擔(dān)任簇首的輪數(shù)，按式(13)計(jì)算其參量值f，并選出f值最大的節(jié)點(diǎn)i，乘以網(wǎng)絡(luò)系數(shù)θ后與自身參量值作比較

fCH≤θf(wàn)max(i),θ∈(0,1]

(16)

若式(16)成立，簇首指定節(jié)點(diǎn)i成為下輪簇首，否則，不更新簇首。相比于每輪更新簇首，這種方式避免了頻繁更新簇首帶來(lái)的能耗，延長(zhǎng)了網(wǎng)絡(luò)生存期。網(wǎng)絡(luò)系數(shù)θ影響簇首更新的速度。θ取值過(guò)大則簇首更換頻繁，加大了網(wǎng)絡(luò)能耗。θ取值過(guò)小則簇首更新慢，導(dǎo)致小部分節(jié)點(diǎn)因長(zhǎng)期擔(dān)任簇首過(guò)早死亡。

2.3 數(shù)據(jù)傳輸

2.3.1 選擇通信對(duì)象

簇首更新之后，新簇首根據(jù)簇內(nèi)成員節(jié)點(diǎn)的位置坐標(biāo)計(jì)算其到基站的距離dtoBS和到簇首的距離dtoCH，并按式(17)進(jìn)行比較

dtoBS(i)

(17)

若式(17)成立，則節(jié)點(diǎn)i在當(dāng)前輪次直接與基站通信，簇首將節(jié)點(diǎn)i從輪詢表中刪除(本文算法的簇內(nèi)通信采用輪詢機(jī)制)，后面節(jié)點(diǎn)的輪詢順序依次前移。這樣通過(guò)縮短通信距離有效減少了數(shù)據(jù)傳輸帶來(lái)的能耗。

2.3.2 通信機(jī)制

大多數(shù)WSNs分簇路由協(xié)議中，簇內(nèi)節(jié)點(diǎn)采集信息后，采用時(shí)分多址(TDMA)機(jī)制將信息發(fā)送給本簇簇首[25]。節(jié)點(diǎn)根據(jù)簇首建立的TDMA時(shí)隙表工作或休眠。簇內(nèi)成員節(jié)點(diǎn)在自己的時(shí)隙被喚醒，打開(kāi)發(fā)射器，與簇首通信。如果有節(jié)點(diǎn)在一段時(shí)間內(nèi)沒(méi)有采集到有效數(shù)據(jù)，那么簇首節(jié)點(diǎn)分配給該節(jié)點(diǎn)的時(shí)隙被浪費(fèi)，并且?guī)?lái)不必要的能量消耗。針對(duì)這一問(wèn)題，本文算法的簇內(nèi)通信機(jī)制采用輪詢機(jī)制[26,27]。每輪由簇首根據(jù)簇內(nèi)節(jié)點(diǎn)信息建立輪詢表，節(jié)點(diǎn)輪流接受服務(wù)。當(dāng)節(jié)點(diǎn)能量耗盡、直接與基站通信或處于休眠狀態(tài)時(shí)，簇首將其從輪詢表中刪除，后面節(jié)點(diǎn)的輪詢順序依次前移。一個(gè)輪詢周期結(jié)束后，簇首對(duì)采集到的數(shù)據(jù)進(jìn)行去冗，并單跳發(fā)至基站。這樣就解決了時(shí)隙被浪費(fèi)的問(wèn)題，并且有效避免了簇內(nèi)節(jié)點(diǎn)被不必要地喚醒，從而減少了網(wǎng)絡(luò)能耗，并顯著提高了網(wǎng)絡(luò)吞吐量。

GAKMDCR算法流程如圖2所示。

圖2 GAKMDCR算法流程

3 算法仿真及性能分析

3.1 仿真環(huán)境

本文在MATLAB R2014b上對(duì)LEACH算法、KUCR算法(參考文獻(xiàn)[13]算法)、基于Fuzzy C-Means聚類的改進(jìn)LEACH算法(參考文獻(xiàn)[14]算法，下文稱改進(jìn)的LEACH算法)、GAKMDCR算法進(jìn)行仿真實(shí)驗(yàn)，并對(duì)4種算法的成簇效果、能量均衡性、網(wǎng)絡(luò)生命周期和網(wǎng)絡(luò)吞吐量進(jìn)行了對(duì)比。仿真參數(shù)[28]見(jiàn)表2。其中，遺傳算法參數(shù)設(shè)計(jì)為[29]：種群大小為50，交叉概率pc=0.25，變異概率pm=0.05，最大迭代次數(shù)T=110。

3.2 仿真實(shí)驗(yàn)一

LEACH算法、改進(jìn)的LEACH算法、KUCR算法和本文算法的成簇對(duì)比如圖3所示。傳統(tǒng)的LEACH算法隨機(jī)選舉簇首成簇，簇的大小和簇首分布不均勻。KUCR采用K-Means形成網(wǎng)絡(luò)分簇，簇首分布較為均勻，但K-Means性能受初始聚類中心影響，導(dǎo)致簇的大小不均勻。改進(jìn)的LEACH算法采用FCM對(duì)監(jiān)測(cè)區(qū)域進(jìn)行分割，每個(gè)區(qū)域內(nèi)的節(jié)點(diǎn)即為一簇，但FCM同樣受初始聚類中心選取的影響，簇的大小也不均勻。本文算法用K-Medoids對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)聚類分簇，并采用遺傳算法優(yōu)化初始中心點(diǎn)。通過(guò)圖3可以看出，本文算法簇首分布合理，簇的大小均勻，成簇效果理想。

表2 仿真參數(shù)

圖3 成簇結(jié)果對(duì)比

3.3 仿真實(shí)驗(yàn)二

LEACH算法、改進(jìn)的LEACH算法、KUCR算法和本文算法生命周期的比較。表3統(tǒng)計(jì)了不同個(gè)數(shù)的節(jié)點(diǎn)死亡出現(xiàn)的輪數(shù)，圖4是4種算法生命周期的對(duì)比，圖5統(tǒng)計(jì)了死亡不同比例節(jié)點(diǎn)對(duì)應(yīng)的輪數(shù)?？梢钥闯?，從網(wǎng)絡(luò)初期到最后，本文算法的存活節(jié)點(diǎn)數(shù)始終多余其它3種算法，這得益于本文算法成簇效果理想，簇首更換機(jī)制合理，有效延長(zhǎng)了網(wǎng)絡(luò)生存期。

表3 不同死亡節(jié)點(diǎn)占比出現(xiàn)的輪數(shù)

3.4 仿真實(shí)驗(yàn)三

LEACH算法、改進(jìn)的LEACH算法、KUCR算法和本文算法網(wǎng)絡(luò)能耗的對(duì)比。圖6橫坐標(biāo)為網(wǎng)絡(luò)運(yùn)行的輪數(shù)，縱坐標(biāo)為網(wǎng)絡(luò)剩余能量，可以看出，本文算法的網(wǎng)絡(luò)剩余能量始終高于其它3種算法，這得益于本文算法分簇理想，網(wǎng)絡(luò)能耗均衡。

3.5 仿真實(shí)驗(yàn)四

LEACH算法、改進(jìn)的LEACH算法、KUCR算法和本文算法吞吐量的對(duì)比。圖7橫坐標(biāo)為網(wǎng)絡(luò)運(yùn)行的輪數(shù)，縱坐標(biāo)為基站接收到的數(shù)據(jù)包個(gè)數(shù)，可以看出，由于本文算法的生命周期更長(zhǎng)，基站最終成功接收到的數(shù)據(jù)遠(yuǎn)多于其它3種算法。在網(wǎng)絡(luò)初期，本文算法的吞吐量也有很大優(yōu)勢(shì)，這得益于簇內(nèi)通信階段，本文算法用輪詢機(jī)制替換了其余3種算法的TDMA機(jī)制，有效解決了時(shí)隙利用不充分的問(wèn)題。

圖4 生命周期對(duì)比

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

圖6 網(wǎng)絡(luò)剩余能量對(duì)比

圖7 網(wǎng)絡(luò)吞吐量對(duì)比

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

本文提出一種基于遺傳算法和K-Medoids聚類的分簇路由算法，初始階段利用遺傳算法優(yōu)化的K-Medoids對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)聚類分簇，綜合考慮節(jié)點(diǎn)的多種因素進(jìn)行簇首更新，數(shù)據(jù)傳輸階段，節(jié)點(diǎn)根據(jù)通信距離選擇最佳通信對(duì)象，簇內(nèi)通信引入輪詢機(jī)制。仿真結(jié)果表明，相比于LEACH、KUCR、改進(jìn)的LEACH算法，本文算法能耗均衡性更優(yōu)，顯著延長(zhǎng)了網(wǎng)絡(luò)生命周期，提高了網(wǎng)絡(luò)吞吐量。