一種基于能量和密度的低功耗自適應(yīng)集簇分層協(xié)議的優(yōu)化

何朝聰 劉培培 嚴(yán)春飛 王慕歡 林軍

摘 要： 根據(jù)經(jīng)典的低功耗自適應(yīng)集簇分層（LEACH）協(xié)議，提出了一種新型的簇首節(jié)點(diǎn)選擇機(jī)制，通過加權(quán)思想綜合考慮了節(jié)點(diǎn)的剩余能量和密度參數(shù)來優(yōu)化簇首節(jié)點(diǎn)的選擇，權(quán)衡簇首節(jié)點(diǎn)負(fù)載均衡和網(wǎng)絡(luò)生存時間之間的關(guān)系，以得到較為理想的加權(quán)因子.仿真結(jié)果表明：在仿真區(qū)域面積為100 m×100 m、節(jié)點(diǎn)數(shù)目為100的條件下，相比于LEACH算法，該算法將第一個節(jié)點(diǎn)的死亡時間延長了19.6%，并且500輪后，網(wǎng)絡(luò)中的剩余節(jié)點(diǎn)數(shù)是LEACH算法的5倍多，改善了節(jié)點(diǎn)能耗，有效提高了整個網(wǎng)絡(luò)的生命周期.

關(guān)鍵詞： 無線傳感網(wǎng)（WSN）; 低功耗自適應(yīng)集簇分層（LEACH）算法; 網(wǎng)絡(luò)壽命; 簇首節(jié)點(diǎn)選取

中圖分類號： TN929.5文獻(xiàn)標(biāo)志碼： A文章編號： 1000-5137（2019）01-0001-06

Abstract： A new cluster head selection mechanism was proposed according to the classical low energy adaptive clustering hierarchy（LEACH） protocol.In the new algorithm，the cluster head selection was optimized by considering residual energy of nodes and density parameters of nodes comprehensively.Meanwhile，the relationship between cluster head load balancing and network lifetime was weighed to get an optimum weighting factor.The simulation results showed that，compared with LEACH algorithm，the proposed algorithm prolonged the death time of the first node by 19.6% when the simulation area was 100 m×100 m and the number of nodes was 100.The number of remaining nodes in the network after 500 rounds was more than 5 times that of LEACH algorithm，which improved the energy consumption of nodes and the whole network lifetime effectively.

0 引 言

無線傳感器網(wǎng)絡(luò)（WSN）是一種將傳感測控技術(shù)、通信技術(shù)、嵌入式技術(shù)有機(jī)整合形成的一個新式協(xié)同系統(tǒng)[1].它由大量的傳感器節(jié)點(diǎn)組成，通常用來檢測一個區(qū)域的環(huán)境參數(shù)，并將收集到的數(shù)據(jù)發(fā)送給基站.由于其功耗低、無線傳輸、無線傳感等特點(diǎn)，常常被應(yīng)用于目標(biāo)跟蹤、環(huán)境檢測等領(lǐng)域[2].但WSN電池能量有限且不易補(bǔ)充，有生存時間較短的問題，限制了其推廣應(yīng)用[3].

低功耗自適應(yīng)集簇分層（LEACH）算法[4]是為了延長網(wǎng)絡(luò)的生命周期而提出的一種分簇算法，分簇的基礎(chǔ)是在網(wǎng)絡(luò)中，將所有的節(jié)點(diǎn)劃分為多個簇，每個簇中均有一個簇首節(jié)點(diǎn)，簇中的其他節(jié)點(diǎn)稱為簇成員，簇首節(jié)點(diǎn)接收簇成員送來的采集信息，進(jìn)行數(shù)據(jù)融合，并送到基站節(jié)點(diǎn).由于LEACH算法在選取簇首節(jié)點(diǎn)時存在隨機(jī)性，使得分簇不均，造成節(jié)點(diǎn)能量分布不均，影響網(wǎng)絡(luò)壽命.杜超[5]提出低功耗自適應(yīng)集中分層型（LEACH-C）算法，在選擇簇首節(jié)點(diǎn)時，考慮了節(jié)點(diǎn)間的通信距離以及節(jié)點(diǎn)的剩余能量，解決了LEACH算法中通信方式和簇首節(jié)點(diǎn)選擇的隨機(jī)性.但是，LEACH-C算法過于依賴基站，增加了基站的能量消耗，降低了網(wǎng)絡(luò)的穩(wěn)定性.張輝等[6]提出了一種基于權(quán)值的LEACH改進(jìn)算法，以權(quán)值作為選取簇首節(jié)點(diǎn)的一種數(shù)學(xué)度量，考慮了節(jié)點(diǎn)的能量、地理位置以及鄰居節(jié)點(diǎn)數(shù).該算法有效地提高了網(wǎng)絡(luò)的生存時間，但簇首節(jié)點(diǎn)與基站之間的通信能耗過大.柴寶杰等[7]在非均勻分簇（EEUC）算法的基礎(chǔ)上針對“空洞”節(jié)點(diǎn)（即某些節(jié)點(diǎn)并未加入任何一個簇）進(jìn)行改進(jìn)，但未考慮基站最優(yōu)位置，影響節(jié)點(diǎn)的傳輸距離和消耗的能量.

本文作者結(jié)合了LEACH-C算法的優(yōu)勢，針對LEACH算法對簇首節(jié)點(diǎn)選擇的隨機(jī)性，提出了一種基于能量和密度的LEACH（LEACH-ED）改進(jìn)算法.其基本思想是在簇首節(jié)點(diǎn)的選取中引入權(quán)值，綜合考慮候選簇首節(jié)點(diǎn)的能量及位置信息，保證每輪都選取最佳節(jié)點(diǎn)做為簇首節(jié)點(diǎn)，同時根據(jù)節(jié)點(diǎn)的剩余能量確定進(jìn)入下一輪大循環(huán)周期的條件，以期有效提高節(jié)點(diǎn)的生存時間，延長網(wǎng)絡(luò)的生命周期.

1 LEACH算法

1.1 簇的建立

LEACH算法工作過程分為初始化階段和穩(wěn)定階段.為了節(jié)省資源開銷，穩(wěn)定階段的持續(xù)時間大于初始化階段的持續(xù)時間.簇的建立過程可分成4個階段：簇首節(jié)點(diǎn)的選擇、廣播、建立，和調(diào)度機(jī)制的生成.

1.1.1 初始化階段

在簇首節(jié)點(diǎn)選取準(zhǔn)備階段開始時，每個節(jié)點(diǎn)產(chǎn)生一個值為0～1之間的隨機(jī)數(shù)，并與閾值T（n） 進(jìn)行比較，若隨機(jī)值小于閾值則該節(jié)點(diǎn)當(dāng)選為簇首節(jié)點(diǎn)，T（n）的計(jì)算公式如下：

其中，p為成為簇首節(jié)點(diǎn)的期望百分比，r為輪數(shù)，G為1p輪還沒有當(dāng)選簇首節(jié)點(diǎn)的節(jié)點(diǎn)集合，·為向下取整運(yùn)算.

節(jié)點(diǎn)成為簇首節(jié)點(diǎn)后，向網(wǎng)絡(luò)中廣播自己成為簇首節(jié)點(diǎn)的消息，非簇首節(jié)點(diǎn)根據(jù)收到信號的強(qiáng)弱程度決定是否加入該簇，并向加入簇的簇首節(jié)點(diǎn)發(fā)送申請信息.當(dāng)簇首節(jié)點(diǎn)收到申請加入信息后，通過時分多址（TDMA）建立通信時間表，并向簇內(nèi)廣播，至此，初始化階段完成.

1.1.2 穩(wěn)定階段

簇內(nèi)非簇首節(jié)點(diǎn)按照之前分配好的通信時間表，將采集到的數(shù)據(jù)發(fā)給簇首節(jié)點(diǎn)，隨后進(jìn)入休眠狀態(tài).簇首節(jié)點(diǎn)將接收到的數(shù)據(jù)進(jìn)行融合后，轉(zhuǎn)發(fā)給基站.穩(wěn)定階段的時間遠(yuǎn)遠(yuǎn)大于初始化階段的時間.

1.2 LEACH算法的不足

LEACH 算法中，簇首節(jié)點(diǎn)的選舉完全是隨機(jī)的，易出現(xiàn)簇首節(jié)點(diǎn)分布不均的問題.而在智能家居應(yīng)用中，傳感器節(jié)點(diǎn)往往分布在由許多小區(qū)域組成的空間里，造成有的區(qū)域里有多個簇首節(jié)點(diǎn)，而有的區(qū)域里沒有簇首節(jié)點(diǎn)，嚴(yán)重影響整個網(wǎng)絡(luò)的壽命.此外，由于沒有考慮到節(jié)點(diǎn)剩余能量因素，可能出現(xiàn)剩余能量低的節(jié)點(diǎn)重復(fù)當(dāng)選簇首節(jié)點(diǎn)的問題，加速該節(jié)點(diǎn)的死亡速度，影響網(wǎng)絡(luò)的壽命.

2 LEACH-ED算法

2.1 網(wǎng)絡(luò)模型的假設(shè)

提出幾點(diǎn)假設(shè)：1） 基站始終具備充足的能量，其余節(jié)點(diǎn)同構(gòu)且初始能量相同;2） 所有節(jié)點(diǎn)一旦生成，位置不變，有唯一的ID標(biāo)識;3） 接收節(jié)點(diǎn)可以根據(jù)接收到的信號強(qiáng)度計(jì)算與發(fā)射節(jié)點(diǎn)之間的距離，控制發(fā)射功率;4） 信道采取兩種不同的工作模式——自由空間傳輸模式和多路徑損耗模式.

2.2 無線通信能量消耗模型

2.3 LEACH-ED算法描述

利用加權(quán)思想對LEACH算法進(jìn)行改進(jìn)，使節(jié)點(diǎn)產(chǎn)生一個基于能量和密度的權(quán)值，通過這個權(quán)值概率閾值選擇簇首節(jié)點(diǎn)，進(jìn)而生成整個簇.該權(quán)值綜合考慮了節(jié)點(diǎn)所處的網(wǎng)絡(luò)環(huán)境和本身狀態(tài)，節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多，成為簇首節(jié)點(diǎn)的概率就越大，成為簇首節(jié)點(diǎn)的概率越大.

改進(jìn)后的閾值其中，Eres為節(jié)點(diǎn)的剩余能量，E0為節(jié)點(diǎn)的初始能量，nneb為鄰居節(jié)點(diǎn)數(shù)量，Ncnum為簇內(nèi)成員數(shù)量，γ1與γ2分別為權(quán)值影響因子，且γ1+γ2=1.

改進(jìn)后的算法流程圖如圖1所示.首先初始化節(jié)點(diǎn)，然后節(jié)點(diǎn)產(chǎn)生一個0～1之間的隨機(jī)數(shù)，并與改進(jìn)后的閾值進(jìn)行比較，若小于閾值，則當(dāng)選為簇首節(jié)點(diǎn).考慮節(jié)點(diǎn)的剩余能量及密度所選取的簇首節(jié)點(diǎn)更為均勻合理.當(dāng)節(jié)點(diǎn)的剩余能量低于網(wǎng)絡(luò)的平均能量時，再重新選取簇首節(jié)點(diǎn)，減少了選取簇首節(jié)點(diǎn)的循環(huán)次數(shù)，進(jìn)而減少了網(wǎng)絡(luò)能耗.節(jié)點(diǎn)被選為簇首節(jié)點(diǎn)后，廣播成簇消息，收到普通節(jié)點(diǎn)的加入請求后，簇首節(jié)點(diǎn)以TDMA方式為簇內(nèi)成員分配時隙，進(jìn)入穩(wěn)定階段.

3 仿真結(jié)果與分析

3.1 仿真環(huán)境以及模型配置

實(shí)驗(yàn)設(shè)置網(wǎng)絡(luò)中有100個節(jié)點(diǎn)隨機(jī)地分布在長寬為100 m×100 m的仿真場景內(nèi)，基站位于坐標(biāo)（50，50）處，網(wǎng)絡(luò)拓?fù)鋱D如圖2所示.每幀數(shù)據(jù)為500 B，并假定各節(jié)點(diǎn)總有數(shù)據(jù)向基站發(fā)送[11].每個節(jié)點(diǎn)的初始能量設(shè)為0.02 J，Eda為0.02 nJ·bit-1·m-2，控制信息大小CM為32 bit，數(shù)據(jù)信息大小DM為 4000 bit，權(quán)值影響因子為0.55，網(wǎng)絡(luò)中簇首節(jié)點(diǎn)個數(shù)所占比例p=0.1，Eelec=10 nJ·bit-1[12].

3.2 仿真波形及分析

通過Matlab仿真軟件對傳統(tǒng)LEACH算法以及LEACH-ED算法進(jìn)行仿真，輪數(shù)-節(jié)點(diǎn)死亡數(shù)關(guān)系曲線如圖3所示.由圖3可知，隨著輪數(shù)的不斷上升，LEACH-ED算法的優(yōu)勢逐漸體現(xiàn)出來，與傳統(tǒng)LEACH算法相比，提高了網(wǎng)絡(luò)的生命周期.

4 結(jié) 論

在傳統(tǒng)LEACH算法的基礎(chǔ)上，考慮了節(jié)點(diǎn)的能量以及密度因素，提出改進(jìn)的LEACH-ED算法，根據(jù)節(jié)點(diǎn)的剩余能量選取簇首節(jié)點(diǎn)，避免能量較低的節(jié)點(diǎn)再次當(dāng)選簇首節(jié)點(diǎn)的情況，使網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量趨于平均.仿真實(shí)驗(yàn)結(jié)果表明：與LEACH算法相比，LEACH-ED算法延長了網(wǎng)絡(luò)的生命壽命，降低了網(wǎng)絡(luò)的平均能耗.但是該算法未考慮穩(wěn)定階段的傳輸問題，有待后續(xù)開展進(jìn)一步的研究工作.

參考文獻(xiàn)：

[1] 梁度，劉夢璐，章成駒.一種LEACH的分簇優(yōu)化策略 [J].北京聯(lián)合大學(xué)學(xué)報(bào)，2017，31（1）：75-80.

LIANG D，LIU M L，ZHANG C J.A clustering optimization strategy for LEACH [J].Journal of Beijing Union University，2017，31（1）：75-80.

[2] ARUMUGAM G S，PONNUCHAMY T.EE-LEACH：development of energy-efficient LEACH protocol for data gathering in WSN [J].Eurasip Journal on Wireless Communications and Networking，2015（1）：1-9.

[3] 韓廣輝，張麗翠.基于LEACH協(xié)議的無線傳感網(wǎng)能效分簇算法 [J].吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2017，35（1）：26-31.

HAN G H，ZHANG L C.Energy efficiency clustering in wireless sensor networks based on LEACH protocol [J].Journal of Jilin University （Information Science Edition），2017，35（1）：26-31

[4] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks [J].IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

[5] 杜超.基于NS2的LEACH-C協(xié)議分析與仿真 [J].電子測量技術(shù)，2011，34（9）：121-123.

DU C.Analysis and simulation of LEACH-C protocol based on NS2 [J].Electronic Measurement Technology，2011，34（9）：121-123.

[6] 張輝，許峰.WSN中基于權(quán)值的LEACH協(xié)議的研究與改進(jìn) [J].微計(jì)算機(jī)信息，2010，26：199-201.

ZHANG H，XU F.Research and improvement of LEACH protocol for WSN based on weight value [J].Microcomputer Information，2010，26：199-201.

[7] 柴寶杰，馬寶英，范書平，等.無線傳感器網(wǎng)絡(luò)中改進(jìn)的EEUC路由算法 [J].微計(jì)算機(jī)信息，2012（9）：366-368.

CHAI B J，MA B Y，F(xiàn)AN S P，et al.Improved EEUC routing algorithms in wireless sensor networks [J].Microcomputer Information，2012（9）：366-368.

[8] 馮永亮，雷偉軍.無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的研究與改進(jìn) [J].信息技術(shù)，2016（2）：145-148.

FENG Y L，LEI W J.Research and improvement of LEACH protocol in wireless sensor networks [J].Information Technology，2016（2）：145-148.

[9] 鄧亞平，鄧?yán)?無線傳感器網(wǎng)絡(luò)的能量有效加權(quán)分簇算法 [J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（4）：1216-1219.

DENG Y P，DENG L J.Energy-efficient weighted clustering algorithm for wireless sensor networks [J].Computer Engineering and Design，2011，32（4）：1216-1219.

[10] FENG X，ZHANG J，REN C，et al.An unequal clustering algorithm concerned with time-delay for internet of things [J].IEEE Access，2018，6：33895-33909.

[11] 林啟中，張冬梅，王聰，等.基于位置信息的雙簇頭路由算法 [J].計(jì)算機(jī)應(yīng)用，2015，35（3）：606-609.

LIN Q Z，ZHANG D M，WANG C，et al.Dual cluster head routing algorithms based on location information [J].Computer Application，2015，35（3）：606-609.

[12] SONY C T，SANGEETHA C P，SURIYAKALA C D.Multi-hop LEACH protocol with modified cluster head selection and TDMA schedule for wireless sensor networks [C]//Communication Technologies.Thuckalay：IEEE，2015：539-543.

（責(zé)任編輯：包震宇，顧浩然）