無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的研究改進

劉闖，陳桂芬，馬威風(fēng)

（長春理工大學(xué) 電子信息工程學(xué)院，長春 130022）

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是一個整體。WSN（無線傳感器）主要工作方式：在需要監(jiān)測區(qū)域安放大量的傳感器節(jié)點，傳感器節(jié)點能夠自動采集所需要信息，傳感器網(wǎng)絡(luò)根據(jù)采集到信息做出決策，最終為用戶提供服務(wù)。無線傳感器網(wǎng)絡(luò)是一種新的數(shù)據(jù)獲取的方式，因此對于傳感器的研究備受矚目［1］。但由于WSN節(jié)點成本較高，能量受限后難以后期維護，因此WSN路由協(xié)議的一個重要目的就是高效地使用節(jié)點能量，最大限度延長網(wǎng)絡(luò)的生存時間［2，3］。

分簇具有降低網(wǎng)絡(luò)能耗，拓?fù)涔芾矸浅７奖?，能量利用率高等點。除以上優(yōu)點之外，其在數(shù)據(jù)融合方面也有巨大優(yōu)勢［4］。LEACH［5］首先提出基于多簇結(jié)構(gòu)，部分基于分簇路由算法，例如LEACH-C［6］、EEE-LEACH［7］、EMODLEACH［8］等 都 是 借 鑒LEACH分簇思想發(fā)展而來的。簇頭的隨機選擇雖然具有易實現(xiàn)、操作性靈活等優(yōu)點，但無法合理地確定簇頭數(shù)目和區(qū)域的分布，這樣會導(dǎo)致節(jié)點能量消耗不均衡，造成整個網(wǎng)絡(luò)性能變差。研究表明，多跳在數(shù)據(jù)轉(zhuǎn)發(fā)過程中更有利于能量的節(jié)約。HEED［9］協(xié)議在簇頭和BS之間采用多跳的通信方式能更好地節(jié)約能量，但容易導(dǎo)致靠近BS的簇頭由于需要轉(zhuǎn)發(fā)消息到其他簇而消耗更多能量，致整個網(wǎng)絡(luò)中的各個區(qū)域之間能量的不平衡。對于其存在的問題，EEUC［10］算法使用非均勻分簇的方法成簇，根據(jù)距離這一變量劃分簇，網(wǎng)絡(luò)被劃分為不同的簇，離BS近的簇的規(guī)模小，簇頭收到成員節(jié)點數(shù)據(jù)后選擇剩余能量多且距離自己最近的簇頭多跳傳輸數(shù)據(jù)，能夠平衡整個網(wǎng)絡(luò)的能量消耗，延長網(wǎng)絡(luò)使用時間。簇的規(guī)模不同，簇間的成員節(jié)點數(shù)也有所差別，在數(shù)據(jù)傳輸階段離BS較近的簇頭，在單位時間內(nèi)向BS發(fā)送數(shù)據(jù)次數(shù)較多，導(dǎo)致全網(wǎng)節(jié)點數(shù)據(jù)難以同步。

綜合考慮上述問題。對于算法改進基本思想：一是在簇頭選舉時考慮節(jié)點上一輪的能量消耗和到節(jié)點到BS的距離；二在形成簇時，節(jié)點選擇考慮了簇頭規(guī)模、能量、簇頭與BS距離，構(gòu)建大小不同規(guī)模的簇來均衡區(qū)域間的能耗，同時為了解決非均勻分簇簇規(guī)模大小不一存在的步調(diào)不一致問題，采用不定長幀的結(jié)構(gòu)方式，簇的成員較少的簇的幀時間間隔較大，簇的成員較多的簇的幀時間間隔較小，以此來保證單位時間內(nèi)不同簇的節(jié)點傳輸?shù)臄?shù)據(jù)次數(shù)相同；三是當(dāng)簇頭間距離大于設(shè)定值時，簇的內(nèi)部選擇中繼節(jié)點協(xié)助傳輸數(shù)據(jù)，數(shù)據(jù)通過中繼節(jié)點和相鄰簇頭多跳傳輸?shù)紹S，進一步延長了網(wǎng)絡(luò)的生存時間。

1 相關(guān)模型

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

研究整個網(wǎng)絡(luò)分布在一個正方形區(qū)域內(nèi)，隨機分布N傳感器節(jié)點，可以周期性的收集區(qū)域內(nèi)數(shù)據(jù)，假設(shè)：①BS檢測區(qū)域外圍，傳感器節(jié)點和BS在安放后均不再發(fā)生位置移動；②全部節(jié)點同構(gòu)并且能量有限，可以獲得本身的剩余能量，每個標(biāo)識ID對應(yīng)一個節(jié)點；③全部節(jié)點都能夠一跳到達(dá)BS，BS能夠與全部節(jié)點通信；④數(shù)據(jù)融合能夠減少數(shù)據(jù)量傳輸，簇頭融合單位數(shù)據(jù)消耗的能量相同；⑤節(jié)點可以通過接收到的信號強度RSSI計算信號發(fā)出者到自己的距離，同時節(jié)點不具有位置感知能力；⑥忽略外界因素對通信質(zhì)量的影響，節(jié)點能夠可靠地進行周期性數(shù)據(jù)采集任務(wù)并始終有數(shù)據(jù)傳輸?shù)紹S。

1.2 能量模型

采用文獻［6］中的無線通信能耗模型，節(jié)點發(fā)送kbit的數(shù)據(jù)包到達(dá)距離為d的另一個節(jié)點，無線信號收發(fā)部分和功率放大部分是主要的能量消耗部分。其中，功率放大器的能量消耗與傳輸環(huán)境和距離密不可分，其可由自由空間和多徑傳輸兩種模式組成。發(fā)射機傳輸k比特數(shù)據(jù)所消耗能量計算公式如下式（1）所示：

其中，Eelec為能量消耗，d0為傳輸距離常數(shù)。當(dāng)傳輸距離d＜d0，則采用自由空間衰落模型εfsd2；若傳輸距離d≥d0，則采用多徑衰落模型εmpd4。式（1）中的 d0=，εfs和εmp分別為射頻參數(shù)，其值中功率放大器決定。接收器件消耗的能量如式（2）：

2 LEACH-LOMUC協(xié)議

提出的LEACH-LOMUC協(xié)議采用“輪”循環(huán)工作方式，主要由簇頭選擇、簇的形成、簇間多跳路徑的構(gòu)建三部分組成。準(zhǔn)備階段中，BS向全網(wǎng)廣播初始化消息（包含最優(yōu)數(shù)目mopt和最優(yōu)通信半徑ropt），節(jié)點根據(jù)信號強度估算與BS的距離ditoBS。簇的形成階段產(chǎn)生不同規(guī)模的簇，由分簇結(jié)果建立簇頭間的多跳路徑，最后網(wǎng)絡(luò)便進入穩(wěn)定的數(shù)據(jù)傳輸階段。圖1是協(xié)議的基本原理圖，簇頭與下一跳簇頭距離大于傳輸距離閾值d0時，選擇中繼節(jié)點輔助數(shù)據(jù)傳輸，圖中的節(jié)點連線代表簇間多跳傳輸路徑。

圖1LOMUC協(xié)議基本原理

2.1 相關(guān)工作準(zhǔn)備階段

BS根據(jù)監(jiān)測區(qū)域面積和全網(wǎng)節(jié)點數(shù)計算最優(yōu)簇的數(shù)目mopt，采用文獻［6］中的方法，假設(shè)在M×M的區(qū)域內(nèi)均勻部署N傳感器節(jié)點，運行結(jié)束后產(chǎn)生了m簇，m簇的整體能量消耗為ETotal，如式（3）。

對式（3）中的m求導(dǎo)并令導(dǎo)數(shù)等于0，求出mopt，然后得到最優(yōu)通信半徑ropt：

2.2 LEACH-LOMUD簇頭選擇

針對LEACH協(xié)議閾值T(n)的不足，把能量和距離因素考慮進來，對公式Topt(n)進行改進，在此階段，對于每個傳感器點，使其產(chǎn)生一個0～1之間的隨機數(shù)，對于這個隨機數(shù)值小于閾值Topt(n)，此節(jié)點就成為候選簇頭。

其中，，p表示簇頭所占比例，r為已完成輪數(shù)，G是最近1p輪中未被選為過簇頭的集合，Erest、Eused、Eavg為上一輪剩余能量、節(jié)點在上一輪消耗的能量、簇內(nèi)節(jié)點上一輪平均剩余能量。

2.3 簇的形成

候選簇頭產(chǎn)生后，各候選簇頭以距離常數(shù)d0廣播最終簇頭競選消息（其中包含剩余能量、到BS距離和一跳鄰居節(jié)點數(shù)）。在d0范圍內(nèi)不包含有其他候選簇頭，則該節(jié)點為最終簇頭；反之，則根據(jù)公式（7）進行代價值計算并交換比較，代價值小的候選簇頭競選獲勝并廣播獲勝消息；反之，退出簇頭競選成為普通節(jié)點。普通節(jié)點依由文獻［11］改進的公式（8）選擇簇頭發(fā)送加入請求（含有剩余能量），簇頭接收到所有節(jié)點消息后，計算出簇間的平均剩余能量并采用TDMA方式向簇的成員節(jié)點發(fā)送時隙表，隨著簇頭向簇內(nèi)所有成員節(jié)點廣播平均剩余能量和調(diào)度時隙表，簇的形成階段完成。

其中，α表示權(quán)重，P1=Eres(CHj)ditoCHj，，Eres(CHj)表示簇頭j的剩余能量，ditoCHj表示節(jié)點i簇頭j的距離，dCHjtoBS表示簇頭j到BS的距離，N(CHj)表示簇頭j的一跳鄰居節(jié)點數(shù)。

2.4 簇頭間通信

在簇形成后，與BS距離小于d0的簇頭直接將數(shù)據(jù)傳送至，距離大于d0的簇頭則使用多跳方式傳送數(shù)據(jù)，根據(jù)公式（9）計算代價函數(shù)Cost(CHi,CHj)值，選擇代價值最小的簇頭作為下一跳簇頭。其中，dCHitoCHj為簇頭i與j之間距離，dCHjtoBS為簇頭j與BS之間距離，Eres(CHj)為簇頭j當(dāng)前剩余能量。

如果下一跳節(jié)點的簇頭已確定，若簇頭之間距離超過d0，便在距離該下一跳簇頭直線距離的中點附近選擇一個本簇內(nèi)能量高且距離下一跳簇頭最近的中繼節(jié)點用于兩簇頭之間的多跳傳輸數(shù)據(jù)。中繼節(jié)點選舉公式如下式（10）。其中，dreltoCHi為中繼節(jié)點與所在簇的簇頭距離，dreltoCHj為中繼節(jié)點到下一跳簇頭的距離，Erel為中繼節(jié)點的剩余能量。

3 仿真實驗與分析

3.1 仿真實驗

對于算法驗證，通過對MATLAB建立仿真模型，對于LEACH、HEED、EB-LEACH［12］和EEUC與本LEACH-LOMUD算法進行對比。對比方式主要是網(wǎng)絡(luò)整體能量、網(wǎng)絡(luò)運行輪數(shù)、存活節(jié)點數(shù)等多項性能進行仿真分析，仿真參數(shù)見表1。

3.2 仿真實驗結(jié)果分析

算法中簇權(quán)值α值的選擇十分重要，因為α是控制普通節(jié)點加入簇，簇的區(qū)域規(guī)模大小的變量，參數(shù)選擇0.1～1進行試驗，結(jié)果如下圖2所示。可以看出，當(dāng)α=0.5或α=0.6時效果最好，因此選擇α=0.6。

表1 網(wǎng)絡(luò)環(huán)境與參數(shù)

圖2 權(quán)值α與輪數(shù)的關(guān)系

圖3 五個協(xié)議的兩個參數(shù)（FND和HND）

由上圖3可知（死亡節(jié)點出現(xiàn)的輪數(shù)），能夠看出整個網(wǎng)絡(luò)情況，對于論數(shù)時間比較長的，說明其能量利用率高，比較小的，說明其能量利用率較低，整個網(wǎng)絡(luò)較差。對于那些輪數(shù)較長時間出現(xiàn)的，其即能量利用率就越高。圖3參數(shù)FND（第一個節(jié)點死亡參數(shù)）和HND（一半節(jié)點死亡參數(shù)）相互比較，LEACH算法的死亡節(jié)點出現(xiàn)在683輪后開始出現(xiàn)，而LEACH-LOMUC在1323輪后；1287輪之后，LEACH算法節(jié)點死亡一半，而LEACH-LOMUC在1672輪才出現(xiàn)這種情況。由此可見，改進算法LEACH-LOMUC不僅顯著地延長了網(wǎng)絡(luò)生存周期，而且死亡節(jié)點出現(xiàn)也晚于其他算法，這種現(xiàn)象表明LEACH-LOMUC能夠均衡網(wǎng)絡(luò)中節(jié)點的能耗。

圖4 生命周期對比

圖5 剩余總能量對比

圖4與圖5是五種算法網(wǎng)絡(luò)生命周期和剩余總能量的比較，從圖中可以看出，LEACH-LOMUC的生命周期最長且剩余能量最多，EEUC第二，LEACH最差。在生命周期方面，LEACH-LOMUC比LEACH延長一半，相較于EEUC，其生命周期延長了約13%，HEED和EB-LEACH的生命周期分別延長了約50%和40%；網(wǎng)絡(luò)剩余總能量方面，LEACH-LOMUC明顯優(yōu)于LEACH、HEED、EB-LEACH和EEUC。

對于產(chǎn)生上述現(xiàn)象的主要原因如下，LEACH協(xié)議簇與匯聚節(jié)點之間以單跳方式直接通信，生命周期短并且能量消耗最大；HEED算法與LEACH不同（在競爭機制），對于簇頭選擇參考剩余能量，能夠選出更好的網(wǎng)絡(luò)分布。但是與EB-LEACH相比，其多次迭代生成的簇消耗過多能量。EB-LEACH算法對于簇頭選擇加入了能量閾值約束條件，性能較LEACH和HEED有所優(yōu)勢，但缺點也十分明顯，其僅僅能均衡簇頭區(qū)域的能量分布，不能使得整個網(wǎng)絡(luò)能量消耗平衡。EEUC采用非均勻分簇方法使網(wǎng)絡(luò)中形成大小不等的簇，解決了熱點問題，采用多跳方法，節(jié)省能耗，使得其網(wǎng)絡(luò)生存時間較LEACH、HEED和EB-LEACH明顯延長。

LEACH-LOMUC和EEUC一樣也采用非均勻分簇和多跳數(shù)據(jù)傳輸方式節(jié)省網(wǎng)絡(luò)中通信能量消耗。不同于EEUC的是，LEACH-LOMUC在閾值上引入了上一輪節(jié)點的能量消耗因素和距離因素，使得能量大且離BS近的節(jié)點有更大的可能成為簇頭；節(jié)點在選擇加入簇頭時考慮了簇頭的規(guī)模和負(fù)載問題，節(jié)點選擇簇內(nèi)未飽和的簇頭加入；在簇間多跳通信時，簇頭間距離大于設(shè)定值時選擇中繼節(jié)點輔助簇頭間數(shù)據(jù)傳輸，節(jié)省簇頭的能量，使得網(wǎng)絡(luò)每輪剩余能量有所增加，整個網(wǎng)絡(luò)能量平衡。所以LEACH-LOMUC的生命周期優(yōu)于其他四種算法。

4 結(jié)論

對于現(xiàn)有無線傳感器網(wǎng)絡(luò)路由算法及其存在的問題，根據(jù)非均勻分簇的思想，提出了基于LEACH路由協(xié)議的改進協(xié)議LEACH-LOMUC。改進協(xié)議基本思想是簇頭的選舉考慮了節(jié)點上一輪的能量消耗和到節(jié)點到BS的距離；成簇時，考慮簇的規(guī)模、能量、簇頭與BS之間的距離，同時在時間片中引入休眠過程來解決非均勻分簇簇規(guī)模大小不一存在的步調(diào)不一致問題；最后對于簇頭間通信距離過大時引入中繼節(jié)點輔助數(shù)據(jù)傳輸，數(shù)據(jù)通過中繼節(jié)點和相鄰簇頭傳輸?shù)紹S。通過實驗對比結(jié)果表明：與LEACH、HEED、EB-LEACH和EEUC算法相較可以發(fā)現(xiàn)，算法能量均衡，生命周期延長。

參考文獻

［1］ 黃庭輝，伊凱，王玉良.基于非均勻分簇的無線傳感器網(wǎng)絡(luò)分層路由協(xié)議［J］.計算機應(yīng)用，2017，23（13）20-24.

［2］ 石閃，施偉斌，朱蓓.一種針對無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的改進算法［J］.電子科技，2017，32（10）：100-103.

［3］ 潘峰.基于能量的無線傳感器網(wǎng)絡(luò)分簇算法研究［J］.計算機仿真，2011，28（3）：159-162.

［4］ 賈云龍.無線傳感器網(wǎng)絡(luò)的非均勻分簇路由協(xié)議研究［J］.計算機應(yīng)用，2014，24（7）：86-89.

［5］ Hzelman WR，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］.Proceedings of the 2000 IEEE International Conference on System Sciences,2000.

［6］ Heinzelman WR，Chandrakasan A，Balakrishnan H.An Application-specific ProtocolArchitecture for Wireless Microsensor Networks［J］.IEEE Transactionson WirelessCommunications，2002，1（4）：660-670.

［7］ Bharti A，Devi C，Bhatia V.Enhanced Energy EfficientLEACH （EEE-LEACH） Algorithm Using MIMO for Wireless Sensor Network［C］.IEEE International Conference on Computational Intelligence&Computing Research,2016.

［8］ 張涌逸.無線傳感器網(wǎng)絡(luò)中非線性非均勻分簇路由研究［J］.無線互聯(lián)科技，2017，（4）：54-57.

［9］ 從立剛，楊華民，王楊惠，等.一種DTN網(wǎng)絡(luò)擺渡點存儲分配方案研究［J］.長春理工大學(xué)學(xué)報：自然科學(xué)版，2017，40（3）：117-122.

［10］ 孫超，彭力，唐波等.基于環(huán)的能耗均衡分簇路由算法［J］.計算機應(yīng)用研究，2017，15（1）：27-36.

［11］ 江禹生，李萍，馬超.一種能量高效的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ǎ跩］.傳感器與微系統(tǒng)，2014，33（2）：146-149.