基于角度聚類的無線傳感器網(wǎng)絡(luò)分簇路由算法

趙小強, 張 琳

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

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

分簇路由協(xié)議能有效均衡節(jié)點能耗，延長網(wǎng)絡(luò)生存時間[5-6]，其簇首的產(chǎn)生有基于隨機(jī)選舉及基于節(jié)點能量選舉兩種方式[7]。低功耗自適應(yīng)分簇(low energy adaptive clustering hierarchy, LEACH)[8]是在WSN中被最早提出的基于隨機(jī)選舉簇首的分簇路由協(xié)議，但其在選取簇首時未能考慮節(jié)點的剩余能量，易導(dǎo)致簇首能耗不均，影響網(wǎng)絡(luò)的生命周期。穩(wěn)定選舉協(xié)議(stable election protocol,SEP)[9]考慮了節(jié)點的能量異構(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é)點距基站的距離信息及節(jié)點的剩余能量信息改進(jìn)灰狼優(yōu)化器，再進(jìn)行簇首選取，但卻忽略了空間方向信息，無法使初始簇首在網(wǎng)絡(luò)的每個方向均勻分布。

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

1 基于角度聚類的分簇路由算法

1.1 節(jié)點角度信息

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

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

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

1.2 初始簇首選取

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

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

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

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

計算各類的聚類中心

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

計算出聚類中心cj后，更新隸屬度矩陣,即取

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

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

|Ft-Ft-1|<ε。

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

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

1.3 最終簇的形成

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

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

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

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

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

ER(k)=kE1。

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

2 實驗與分析

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

表1 仿真參數(shù)

2.1 剩余能量分布圖

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

圖1 第800輪時的能量分布

圖2 第1 300輪時的能量分布

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

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

圖3 平均剩余能量

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

圖4 平均能量差

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

各算法運行過程中節(jié)點的死亡情況如圖5所示。從中可見，AC_GWO算法首個節(jié)點的死亡時間及最后一個節(jié)點的死亡時間均晚于其他算法。

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

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

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

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

3 結(jié)語

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