能量高效的WSNs分簇路由協議

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

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

0 引 言

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

本文將遺傳算法(GA)優化的K-Medoids聚類用于WSNs，提出了能量高效的均勻分簇路由協議—GAKMDCR協議，通過選舉高質量簇首、改善通信機制的方式，在均衡網絡能耗的同時，提高了網絡吞吐量。

1 網絡模型

1.1 網絡模型

假設所研究的WSNs具有以下性質：

(1)監測區域內的N個節點同構且固定，基站位于無線傳感網內部；

(2)所有節點均具備身份標識(ID)，且各不相同；

(3)任意節點能夠根據接收到的信號強度計算與發送端的距離，能夠感知自身剩余能量、計算自成為簇首的輪數；

(4)任意節點能夠直接與基站通信，能夠進行數據去冗處理，具備擔任簇首的能力；

(5)網絡部署完成后，再無人為干涉。

1.2 能耗模型

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

(1)

(2)

圖1 數據傳輸過程與能量消耗

節點接收數據所需能量的數學表達式為

ERX=k×Eelec

(3)

其中，d為無線電的傳輸距離，k是傳輸的比特數，Eelec是無線通信的發送端/接收端每發送/接收1比特數據所需要的能量。εfs和εmp為兩種信道模型中功率放大電路的能量耗散系數。

2 GAKMDCR算法

GAKMDCR算法中，網絡按輪運行。網絡初始化時期，基站根據節點的地理位置，采用遺傳算法優化的K-Medoids迭代計算，形成h個固定的分簇。首輪簇首由簇內中心點擔任。此后每輪，由當前簇首綜合考慮簇內節點狀態決定是否更換簇首，如需更換，指定條件最優的節點成為下輪簇首。這樣就避免了因頻繁更換簇首帶來的能量消耗，有效延長了網絡生命周期。

2.1 簇的構建

2.1.1 最優簇數

K-Medoids需要指定分簇數目，基于上述網絡型和能耗模型，網絡運行一輪消耗的能量為[18-20]

(4)

其中，DtoBS為節點到基站的距離，EDA為簇首融合1 bit冗余數據帶來的能耗。

對聚類數h求偏導，令偏導數為零，可求得使網絡能耗最低的h。求得的最優簇數為

(5)

2.1.2 K-Medoids聚類算法

K-Medoids聚類算法是一種基于代表對象的劃分方法，用絕對誤差標準來定義一個類簇的緊湊程度[21]。每次迭代后選取簇內的實際樣本點作為聚類中心，解決了K-Means算法對“噪聲”敏感的問題。絕對誤差公式為

(6)

其中，p為ci簇中的樣本點，oi為ci簇的中心點。基于K-Medoids的成簇步驟見表1。

2.1.3 遺傳算法優化K-Medoids初始中心點

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

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

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

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

(3)對個體進行K-Medoids迭代計算并評價適應度；

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

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

其中，適應度函數設計為

(7)

(8)

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

2.2 簇首選舉

成簇之后，首輪簇首由簇內中心點擔任。從第二輪開始，當前簇首基于節點剩余能量、到基站的距離、與簇內其余節點的緊湊程度、擔任過簇首的輪次4個因素決定是否需要更新簇首，若需要，則指定條件最優的節點擔任下輪簇首。

節點的剩余能量因素設計為

(9)

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

網絡節點與基站的位置關系因素設計為

(10)

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

與簇內其余節點的緊湊程度因素設計為

(11)

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

擔任過簇首節點的輪次因素設計為

(12)

其中，rtotal表示網絡運行過的輪數，rCH(i)表示節點i擔任簇首的輪數。擔任簇首次數越多，比值f4(i)越小，則節點i再次當選簇首的概率相對較小。這樣很好的將網絡能耗分攤到每一個節點

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

(13)

其中，α、β、λ、μ為權重參數，用于調整4個因素的重要程度，且滿足和為1。隨著網絡的運行，根據4個因素對網絡影響力的改變動態調整權重參數，以選出最優簇首。權重參數的更新公式設計為

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

(14)

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

(15)

其中，Eres(i)為節點i的剩余能量，Emax和Emin分別為節點i所在簇內任意節點剩余能量的最大和最小值。這樣設計的好處是：網絡不斷運行，節點剩余能量因素愈加重要，節點的剩余能量不斷減少，得到的α值動態增大，即能量因素越來越重要。同時，簇內節點的剩余能量兩極分化越嚴重，對應式(14)中的分子越大，該簇節點得到的α值也越大，能量因素在該簇的簇首選舉中所占比重更大。這樣就避免了能量消耗集中于部分節點使網絡生存期減短。

每輪的最后階段，簇首根據節點發來的位置坐標、剩余能量和擔任簇首的輪數，按式(13)計算其參量值f，并選出f值最大的節點i，乘以網絡系數θ后與自身參量值作比較

fCH≤θfmax(i),θ∈(0,1]

(16)

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

2.3 數據傳輸

2.3.1 選擇通信對象

簇首更新之后，新簇首根據簇內成員節點的位置坐標計算其到基站的距離dtoBS和到簇首的距離dtoCH，并按式(17)進行比較

dtoBS(i)

(17)

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

2.3.2 通信機制

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

GAKMDCR算法流程如圖2所示。

圖2 GAKMDCR算法流程

3 算法仿真及性能分析

3.1 仿真環境

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

3.2 仿真實驗一

LEACH算法、改進的LEACH算法、KUCR算法和本文算法的成簇對比如圖3所示。傳統的LEACH算法隨機選舉簇首成簇，簇的大小和簇首分布不均勻。KUCR采用K-Means形成網絡分簇，簇首分布較為均勻，但K-Means性能受初始聚類中心影響，導致簇的大小不均勻。改進的LEACH算法采用FCM對監測區域進行分割，每個區域內的節點即為一簇，但FCM同樣受初始聚類中心選取的影響，簇的大小也不均勻。本文算法用K-Medoids對網絡節點聚類分簇，并采用遺傳算法優化初始中心點。通過圖3可以看出，本文算法簇首分布合理，簇的大小均勻，成簇效果理想。

表2 仿真參數

圖3 成簇結果對比

3.3 仿真實驗二

LEACH算法、改進的LEACH算法、KUCR算法和本文算法生命周期的比較。表3統計了不同個數的節點死亡出現的輪數，圖4是4種算法生命周期的對比，圖5統計了死亡不同比例節點對應的輪數。可以看出，從網絡初期到最后，本文算法的存活節點數始終多余其它3種算法，這得益于本文算法成簇效果理想，簇首更換機制合理，有效延長了網絡生存期。

表3 不同死亡節點占比出現的輪數

3.4 仿真實驗三

LEACH算法、改進的LEACH算法、KUCR算法和本文算法網絡能耗的對比。圖6橫坐標為網絡運行的輪數，縱坐標為網絡剩余能量，可以看出，本文算法的網絡剩余能量始終高于其它3種算法，這得益于本文算法分簇理想，網絡能耗均衡。

3.5 仿真實驗四

LEACH算法、改進的LEACH算法、KUCR算法和本文算法吞吐量的對比。圖7橫坐標為網絡運行的輪數，縱坐標為基站接收到的數據包個數，可以看出，由于本文算法的生命周期更長，基站最終成功接收到的數據遠多于其它3種算法。在網絡初期，本文算法的吞吐量也有很大優勢，這得益于簇內通信階段，本文算法用輪詢機制替換了其余3種算法的TDMA機制，有效解決了時隙利用不充分的問題。

圖4 生命周期對比

圖5 死亡節點數對比

圖6 網絡剩余能量對比

圖7 網絡吞吐量對比

4 結束語

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