基于LEACH—C協(xié)議的研究與改進(jìn)

摘要：無線傳感器網(wǎng)絡(luò)（WSN）路由協(xié)議中的LEACH-C協(xié)議是一種集中式的簇頭選擇協(xié)議，不同于LEACH分布式隨機(jī)選擇簇頭的方式。針對LEACH-C只考慮節(jié)點剩余能量和過度依賴基站等問題，在LEACH-C成簇基礎(chǔ)上進(jìn)行改進(jìn)，主簇頭和路由簇頭的選擇既考慮了節(jié)點的覆蓋率也兼顧節(jié)點的能量剩余和距離，減少頻繁分簇而導(dǎo)致的能量消耗，路由采取雙路徑路由通信方案，提高網(wǎng)絡(luò)的健壯性。通過Matlab仿真實驗平臺驗證了改進(jìn)協(xié)議比LEACH-C更能延長網(wǎng)絡(luò)壽命。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；LEACH-C協(xié)議；剩余能量；覆蓋率；雙路徑路由通信

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼： 文章編號：1009-3044（2016）08-0036-03

1 概述

無線傳感器網(wǎng)絡(luò)（WSN）[1]已廣泛用于監(jiān)測環(huán)境、軍事活動和現(xiàn)代農(nóng)業(yè)等方面，具有重要研究意義和價值。傳感器節(jié)點的能量是有限的，所以高效地利用有限的能量以獲得最大的生命周期是無線傳感器網(wǎng)絡(luò)研究的重要問題之一[2]。

低功耗自適應(yīng)聚類路由協(xié)議（LEACH） [3]是WSN中經(jīng)典的分簇路由協(xié)議，其協(xié)議通過循環(huán)隨機(jī)地選舉簇頭節(jié)點來提高網(wǎng)絡(luò)的能量利用效率和延長整個系統(tǒng)的生命周期。LEACH-C[4]采用集中式的簇頭產(chǎn)生協(xié)議。當(dāng)每輪開始時，每個節(jié)點向基站報告自己的剩余能量和位置，基站計算所有節(jié)點的平均能量，剩余能量高于平均能量的節(jié)點作為候選節(jié)點并從中最優(yōu)的作為簇頭。LEACH-C的不足是每一輪結(jié)束后所有網(wǎng)絡(luò)節(jié)點都要給基站發(fā)送自己的狀態(tài)消息，而且簇頭節(jié)點也是以單跳的形式直接和基站通信[5]。文獻(xiàn)[6]提出了基于粒子群優(yōu)化的LEACH-C算法的改進(jìn)。文獻(xiàn)[7]提出了基于Dijkstra路由策略的LEACH-C改進(jìn)算法，但未考慮中間節(jié)點的能耗問題。

在綜合考慮節(jié)點的剩余能量、節(jié)點覆蓋率以及半徑內(nèi)節(jié)點通信代價因素提出了一種改進(jìn)的LEACH-C成簇算法，引入路由節(jié)點代替簇頭路由的方式來提高簇的生存能力。在路由機(jī)制中采用雙路徑通信方案，提高網(wǎng)絡(luò)健壯性。仿真結(jié)果表明該算法在確保檢測區(qū)域有較好的覆蓋性條件下延長了網(wǎng)絡(luò)壽命。

2 相關(guān)參數(shù)的定義與計算方式

2.1 能量因子定義

在基站選擇簇頭時，需要考慮節(jié)點的剩余能量，因而能量因子是描述節(jié)點剩余能量與網(wǎng)絡(luò)平均能量的一個參數(shù)，能量因子越大的節(jié)點表示節(jié)點剩余能量越多，當(dāng)選簇頭的概率應(yīng)該越大。能量因子的確定：

其中，Eir為i節(jié)點的當(dāng)前剩余能量，Ei為能量比值。當(dāng)節(jié)點剩余能量大于平均能量時Ei大于1。

2.2 覆蓋率因子定義

節(jié)點的被覆蓋因子Ci：傳感器節(jié)點i的覆蓋面積內(nèi)，被其他傳感器節(jié)點覆蓋的面積與本節(jié)點覆蓋區(qū)域面積的比值。假設(shè)有N個鄰居節(jié)點對i節(jié)點的監(jiān)測范圍有重合，若這N個節(jié)點在去除該區(qū)域的相互重疊面積后總覆蓋面積為Ai，A為i節(jié)點的監(jiān)測范圍。則節(jié)點i的被覆蓋率Ci的計算如下：

若節(jié)點Ci為1時，則稱為完全覆蓋，該節(jié)點的死亡不會影響整個網(wǎng)絡(luò)的覆蓋范圍和覆蓋率。若節(jié)點Ci不為1時，則稱非完全覆蓋或無覆蓋。

2.3 節(jié)點半徑內(nèi)通信代價因子

選擇出來的簇頭不應(yīng)該偏離簇內(nèi)大部分成員太遠(yuǎn)，如果位于整個簇的幾何中心位置附近，有利于降低簇內(nèi)成員與簇頭的通信，因為簇頭要擔(dān)任與基站的路由通信功能，所以還要考慮簇頭與基站距離的因素。所以通信代價因子的定義為：

其中，ri為節(jié)點i為未當(dāng)選簇頭的輪數(shù)，一旦當(dāng)選簇頭或副簇頭則重置為0。r為系統(tǒng)當(dāng)前運(yùn)行的輪數(shù)。輪是以基站規(guī)定的時間段為標(biāo)準(zhǔn)，在這時間段內(nèi)所有節(jié)點都至少能向基站傳送一次數(shù)據(jù)。由公式可知在開始的階段簇頭的選擇主要依靠覆蓋率、剩余能量以及通信代價，在多輪以后逐步以剩余能量和通信代價為主要選擇依據(jù)，這樣也增強(qiáng)了簇頭選擇的合理性。

3 算法設(shè)計

主要剩余能量、節(jié)點覆蓋率以及半徑內(nèi)節(jié)點通信代價因素來進(jìn)行網(wǎng)絡(luò)分簇，提高能量利用效率。首先描述簇頭選擇公式，然后根據(jù)公式提出具體選擇協(xié)議。

3.1 簇頭的選擇

步驟一：首輪所有節(jié)點發(fā)送自己的能量以及位置信息，距離遠(yuǎn)的節(jié)點以多跳方式發(fā)送給基站，以后節(jié)點以信息捎帶的方式發(fā)送剩余能量即可。BS根據(jù)所有節(jié)點的信息計算網(wǎng)絡(luò)平均能量，各個節(jié)點覆蓋率以及通信代價因子。

步驟二：判斷節(jié)點的剩余能量是否大于平均能量，如果大于平均能量則有機(jī)會競爭簇頭。

步驟三：BS在選擇簇頭時盡量選擇Ci為1的節(jié)點。如果一個簇范圍內(nèi)有多個符合條件的節(jié)點，則根據(jù)S因子選擇主簇頭。其他符合條件的節(jié)點BS可根據(jù)需要讓其睡眠。若某區(qū)域內(nèi)沒有Ci為1的節(jié)點，則根據(jù)S因子利用擬退火算法選擇出主簇首。

步驟四：BS把簇首信息廣播給相應(yīng)的簇節(jié)點，節(jié)點接收廣播信息確定自己是否當(dāng)選為簇頭節(jié)點，是則根據(jù)廣播半徑廣播自己的簇頭消息，不是則根據(jù)接收到的簇頭消息加入離自己最近的簇中，完成簇的建立。

3.2 路由節(jié)點的選擇和成簇通信方式

在路由點選擇中，BS可根據(jù)簇的分布情況，在網(wǎng)絡(luò)中選擇出多個節(jié)點擔(dān)任路由節(jié)點，負(fù)責(zé)整個網(wǎng)絡(luò)中信息的專遞工作。這樣通過簇的管理節(jié)點與路由傳送節(jié)點的分離，降低簇頭節(jié)點的能量消耗，延長簇頭的壽命。路由節(jié)點的選擇方式是根據(jù)能量因子以及與基站的距離因素利用擬退火算法來選擇。在穩(wěn)定階段，簇內(nèi)的所有普通節(jié)點都按照時分復(fù)用（Time Division Multiple Access，TDMA）時隙將采集到的信息傳送到簇頭節(jié)點。所有簇頭在收集數(shù)據(jù)時都進(jìn)行數(shù)據(jù)融合才向路由節(jié)點或基站發(fā)送，減少通信量。

3.3 簇間路由選擇

基站在選擇完路由節(jié)點以后，為每個路由節(jié)點在通往基站的方向上利用Dijkstra算法選擇出兩條最短路徑，但一次只使用一條路徑，另一條作為備用路徑保存。每個路由節(jié)點無需保存路徑的全部節(jié)點信息，只需保持路由節(jié)點的下一跳的兩個后繼節(jié)點（每一個后繼節(jié)點代表一條路徑）和需要通過本路由節(jié)點向基站傳遞消息的所有前驅(qū)節(jié)點（代表有多少簇頭節(jié)點需要通過本節(jié)點給基站傳遞消息），這樣就可以實現(xiàn)較遠(yuǎn)的路由節(jié)點以多跳的方式傳送數(shù)據(jù)給基站。每個路由節(jié)點收到消息后都進(jìn)行數(shù)據(jù)融合以減少不必要的能量消耗。為每個路由節(jié)點設(shè)置一個通信閾值，如果通信量超過這個閾值，便可通知自己的部分前驅(qū)節(jié)點選擇第二條路徑傳送數(shù)據(jù)，從而達(dá)到減少某個路由節(jié)點能量過度消耗而提前死亡的危險，增強(qiáng)網(wǎng)絡(luò)的健壯性。

4 仿真實現(xiàn)

4.1 模擬實驗環(huán)境設(shè)置和參數(shù)

用Matlab作為仿真實驗平臺，仿真環(huán)境是在200m*200m的正方形區(qū)域內(nèi)隨機(jī)的部署200個傳感器節(jié)點，初始能量為E=1J，基站處于正方形的左下角（0，0）m位置，并使用與文獻(xiàn)[8]相同的無線通信能量消耗模型。發(fā)送數(shù)據(jù)和接收數(shù)據(jù)的無線通信模型分別為：

Leach協(xié)議在100輪時出現(xiàn)死亡節(jié)點，Leach-c協(xié)議在127輪出現(xiàn)第一個死亡節(jié)點，而本協(xié)議在將近250輪才出現(xiàn)，有效延長了第一個節(jié)點死亡時間。不過本協(xié)議在出現(xiàn)第一個死亡節(jié)點以后網(wǎng)絡(luò)的節(jié)點死亡速度很快，在后面的六十輪中死亡節(jié)點數(shù)目急劇上升，幾乎全部死亡。通過三種協(xié)議的比較，顯示了改進(jìn)協(xié)議在確保網(wǎng)絡(luò)有較好覆蓋率條件下延長了網(wǎng)絡(luò)。

5 結(jié)束語

通過對Leach協(xié)議和Leach-c協(xié)議的分析研究，綜合考慮了兩個協(xié)議的優(yōu)缺點，提出一種基于節(jié)點覆蓋率、剩余能量和位置信息的Leach-c協(xié)議的改進(jìn)協(xié)議。協(xié)議在Leach-c的基礎(chǔ)上改進(jìn)了簇頭選擇條件，加入路由節(jié)點改進(jìn)簇首節(jié)點路由方式，采取了雙路徑方式，不僅保證了簇消息的發(fā)送成功概率，又優(yōu)化了簇首節(jié)點的能耗過快問題，保證了網(wǎng)絡(luò)在有較好的覆蓋性條件下延長了整個網(wǎng)絡(luò)的壽命。實驗表明在確保網(wǎng)絡(luò)覆蓋率的條件下很好的延長了網(wǎng)絡(luò)的生存壽命，但還有些可以改進(jìn)的地方，如中繼簇頭能耗較大問題，對基站的依賴程度還比較大，不夠獨(dú)立等。

參考文獻(xiàn)：

[1] 廖明華，張華，王東.基于LEACH協(xié)議的簇頭選舉改進(jìn)算法[J].計算機(jī)工程，2011，37（7）：112-114.

[2] 底欣，張百海.一種改進(jìn)的WSN成簇算法[J].計算機(jī)工程，2011，37（1）：110-112.

[3] Heinzelman W， Chandrakasan A， Balakrishnan H. Energy-efficient Communication Protocol for Wireless Microsensor Networks[C]// Proc. of the 33rd Annual Hawaii Intl Conf. on System Sciences. [S.l.]： IEEE Computer Society， 2000.

[4] Siva DMG， Ma DCF. A Centralized Energy efficient Routing Protocol for Wireless Sensor Networks[J]. IEEE Radio Communications， 2005， 43（3）： 8-13.

[5] 何傳波.無線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)的研究[D].廣西大學(xué)，2014.

[6] 閆效鶯，程國建.基于改進(jìn)粒子群優(yōu)化的WSN均衡能量消耗路由算法[J].計算機(jī)工程與設(shè)計，2012， 10（33）：3692-3696.

[7] 蔣華，劉偉強(qiáng)，王鑫.無線傳感器網(wǎng)絡(luò)中Leach-c路由協(xié)議的研究與改進(jìn)[J].微電子學(xué)與計算機(jī)，2014，12（31）：43-47.

[8] 蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學(xué)報，2012， 23（5）：1222-1233.