趙小強(qiáng), 張 琳

(1. 西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121； 2. 陜西省信息通信網(wǎng)絡(luò)及安全重點(diǎn)實(shí)驗(yàn)室， 陜西 西安 710121)

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)由大量小型、廉價(jià)、低功耗的傳感器節(jié)點(diǎn)組成，這些傳感器的能量主要由電池供給，故其能量有限，且更換電池困難[1-2]。布設(shè)WSN的主要挑戰(zhàn)是平衡網(wǎng)絡(luò)負(fù)載及降低傳感器節(jié)點(diǎn)的能量消耗，從而延長(zhǎng)網(wǎng)絡(luò)的生命周期[3-4]。

分簇路由協(xié)議能有效均衡節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間[5-6]，其簇首的產(chǎn)生有基于隨機(jī)選舉及基于節(jié)點(diǎn)能量選舉兩種方式[7]。低功耗自適應(yīng)分簇(low energy adaptive clustering hierarchy, LEACH)[8]是在WSN中被最早提出的基于隨機(jī)選舉簇首的分簇路由協(xié)議，但其在選取簇首時(shí)未能考慮節(jié)點(diǎn)的剩余能量，易導(dǎo)致簇首能耗不均，影響網(wǎng)絡(luò)的生命周期。穩(wěn)定選舉協(xié)議(stable election protocol,SEP)[9]考慮了節(jié)點(diǎn)的能量異構(gòu)性，優(yōu)化了簇首的選擇方法，但簇首在網(wǎng)絡(luò)空間中仍存在分布不均的現(xiàn)象?；谶m應(yīng)值的改進(jìn)灰狼優(yōu)化器(fitness value-based improved grey wolf optimizer, FIGWO)[10]引入節(jié)點(diǎn)距基站的距離信息及節(jié)點(diǎn)的剩余能量信息改進(jìn)灰狼優(yōu)化器，再進(jìn)行簇首選取，但卻忽略了空間方向信息，無(wú)法使初始簇首在網(wǎng)絡(luò)的每個(gè)方向均勻分布。

本文將針對(duì)WSN分簇路由協(xié)議，給出一種基于角度聚類(lèi)及灰狼優(yōu)化器(angle-based clustering and grey wolf optimizer,AC_GWO)算法。先根據(jù)節(jié)點(diǎn)與基站間的角度計(jì)算各節(jié)點(diǎn)的角度信息，用以改進(jìn)模糊C均值聚類(lèi)算法中的初始隸屬度矩陣，從而選取初始簇首，形成初始簇，再利用灰狼優(yōu)化器在各初始簇中迭代選取最終簇首并形成最終簇，完成數(shù)據(jù)傳輸。

1 基于角度聚類(lèi)的分簇路由算法

1.1 節(jié)點(diǎn)角度信息

將整體區(qū)域按方向劃分為C個(gè)區(qū)域，第j(j=1,2,…,C)個(gè)區(qū)域的角度范圍定義為W(j)，滿足

將節(jié)點(diǎn)i與基站間的角度定義為

其中，(xi,yi)表示第i個(gè)節(jié)點(diǎn)的位置,(x0,y0)表示基站的位置。

1.2 初始簇首選取

以節(jié)點(diǎn)角度信息作為特征，通過(guò)對(duì)模糊C均值聚類(lèi)(fuzzy c-means,FCM)算法[11]初始隸屬度矩陣的重新定義，得出隸屬度矩陣的改進(jìn)方法。

初始化節(jié)點(diǎn)i相對(duì)于區(qū)域j的初始隸屬度值，即

C=floor [(N+9)/10],

floor為向下取整函數(shù)。

計(jì)算各類(lèi)的聚類(lèi)中心

其中，m是參數(shù)，通常值為2；xi為節(jié)點(diǎn)i的值。

計(jì)算出聚類(lèi)中心cj后，更新隸屬度矩陣,即取

計(jì)算新的目標(biāo)函數(shù)值

對(duì)聚類(lèi)中心及隸屬度矩陣進(jìn)行迭代更新,直至滿足

|Ft-Ft-1|<ε。

其中，t指當(dāng)前迭代輪次，ε是迭代終止閾值[12]。

迭代終止時(shí)，輸出當(dāng)前聚類(lèi)中心。由此可得C個(gè)聚類(lèi)中心{cj:j=1,2,…,C}。然后，選擇距離每個(gè)聚類(lèi)中心最近的節(jié)點(diǎn)作為初始簇首，從而得到C個(gè)初始簇首{Hj:j=1,2,…,C}。

1.3 最終簇的形成

計(jì)算各節(jié)點(diǎn)與每個(gè)初始簇首Hj(j=1,2,…,C)間的歐氏距離，各節(jié)點(diǎn)加入距離最近的簇首形成C個(gè)初始簇。

以節(jié)點(diǎn)剩余能量及其與基站之間的距離為特征，使用灰狼算法在簇內(nèi)選取實(shí)際簇首[10]。對(duì)于同一簇內(nèi)的所有節(jié)點(diǎn)，按照特征值的大小進(jìn)行排序，選取前3個(gè)節(jié)點(diǎn)作為α、β及δ狼，根據(jù)灰狼算法中的捕獵行為[13]，選取最終簇首并形成最終簇。

1.4 網(wǎng)絡(luò)能耗

網(wǎng)絡(luò)能耗主要發(fā)生在數(shù)據(jù)發(fā)送及數(shù)據(jù)接收時(shí)段[14]。當(dāng)節(jié)點(diǎn)傳輸k比特?cái)?shù)據(jù)時(shí)，發(fā)送數(shù)據(jù)的能耗為

接收數(shù)據(jù)的能耗為

ER(k)=kE1。

所給AC_GWO分簇路由算法將在此種能耗模式下持續(xù)工作直至節(jié)點(diǎn)能量全部耗盡。

2 實(shí)驗(yàn)與分析

驗(yàn)證AC_GWO算法的有效性，使用MATLAB將其與LEACH、SEP及FIGWO進(jìn)行仿真比較。仿真參數(shù)如表1所示[15]。

表1 仿真參數(shù)

2.1 剩余能量分布圖

比較LEACH、SEP、FIGWO和AC_GWO算法運(yùn)行至第800輪和第1 300輪節(jié)點(diǎn)的剩余能量分布情況，實(shí)驗(yàn)結(jié)果如圖1和圖2所示。其中節(jié)點(diǎn)附近的數(shù)字表示節(jié)點(diǎn)剩余能量的百分比。從圖1可見(jiàn)，AC_GWO算法各節(jié)點(diǎn)的剩余能量明顯大于其余算法，且能量消耗相對(duì)均衡。從圖2可見(jiàn)，LEACH和SEP算法的大部分節(jié)點(diǎn)能量已經(jīng)消耗殆盡，F(xiàn)IGWO算法已經(jīng)開(kāi)始有節(jié)點(diǎn)死亡，而AC_GWO算法還沒(méi)有節(jié)點(diǎn)死亡。因此，AC_GWO算法可以使節(jié)點(diǎn)的能耗更加均衡，確保不加速消耗某節(jié)點(diǎn)的能量。

圖1 第800輪時(shí)的能量分布

圖2 第1 300輪時(shí)的能量分布

2.2 網(wǎng)絡(luò)總能耗及節(jié)點(diǎn)剩余能量差

對(duì)網(wǎng)絡(luò)總能耗進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如圖3所示。從中可見(jiàn)，AC_GWO算法的總體能量較其余算法消耗速度較慢，表明該算法在相同初始能量下，可運(yùn)行更長(zhǎng)的時(shí)間，即AC_GWO算法可以有效降低網(wǎng)絡(luò)的整體能耗，是一種有效的分簇路由算法。

圖3 平均剩余能量

為了進(jìn)一步分析節(jié)點(diǎn)能量的變化，對(duì)所有節(jié)點(diǎn)的能量差進(jìn)行計(jì)算，以判斷算法在運(yùn)行過(guò)程中各節(jié)點(diǎn)的能量消耗是否均衡。實(shí)驗(yàn)結(jié)果如圖4所示。從中可見(jiàn)，所有算法的節(jié)點(diǎn)能量差先增大后減小，峰值出現(xiàn)在首個(gè)節(jié)點(diǎn)死亡之時(shí)。與其他算法相比，AC_GWO算法具有最低的峰值及低增長(zhǎng)率。這表明所給算法節(jié)點(diǎn)間的能量差相對(duì)較小，進(jìn)而證明了其能耗更均衡。

圖4 平均能量差

2.3 網(wǎng)絡(luò)穩(wěn)定傳輸期

各算法運(yùn)行過(guò)程中節(jié)點(diǎn)的死亡情況如圖5所示。從中可見(jiàn)，AC_GWO算法首個(gè)節(jié)點(diǎn)的死亡時(shí)間及最后一個(gè)節(jié)點(diǎn)的死亡時(shí)間均晚于其他算法。

關(guān)鍵節(jié)點(diǎn)死亡時(shí)間統(tǒng)計(jì)結(jié)果如表2所示。從中可見(jiàn)，AC_GWO算法保障了1%的節(jié)點(diǎn)、50%的節(jié)點(diǎn)及100%的節(jié)點(diǎn)的死亡時(shí)間均晚于其他算法，且使網(wǎng)絡(luò)穩(wěn)定傳輸期較其他算法都有明顯改善。這表明所給算法的網(wǎng)絡(luò)生命周期比其他算法更長(zhǎng)。

圖5 網(wǎng)絡(luò)穩(wěn)定傳輸期

表2 關(guān)鍵節(jié)點(diǎn)死亡時(shí)間

算法死亡輪次1%節(jié)點(diǎn)50%節(jié)點(diǎn)100%節(jié)點(diǎn)穩(wěn)定傳輸期增長(zhǎng)率AC_GWO1 2961 6422 057-FIGWO1 1941 5441 92763.4%SEP9601 3121 69335.0%LEACH7931 2001 4238.6%

3 結(jié)語(yǔ)

在分簇路由協(xié)議中，均勻選取簇首是一大挑戰(zhàn)。若將網(wǎng)絡(luò)視為整體，則可通過(guò)在網(wǎng)絡(luò)各方向上選擇簇首來(lái)優(yōu)化能耗。所給基于模糊C均值聚類(lèi)和灰狼優(yōu)化器的混合路由協(xié)議，使用節(jié)點(diǎn)和基站間的角度信息來(lái)構(gòu)造初始隸屬度矩陣，保障了簇首的均勻分布。仿真結(jié)果表明，與LEACH、SEP、FIGWO相比，所給算法在穩(wěn)定傳輸期和節(jié)點(diǎn)能耗方面有顯著改善，網(wǎng)絡(luò)穩(wěn)定傳輸期分別增加了63.4%，35.0%和8.6%，而節(jié)點(diǎn)剩余能量分別增加了50.0%，47.2%和8.0%。所給算法可有效均衡節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。