一種基于能量和密度的低功耗自適應集簇分層協議的優化

何朝聰 劉培培 嚴春飛 王慕歡 林軍

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

關鍵詞： 無線傳感網（WSN）; 低功耗自適應集簇分層（LEACH）算法; 網絡壽命; 簇首節點選取

中圖分類號： TN929.5文獻標志碼： 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 引 言

無線傳感器網絡（WSN）是一種將傳感測控技術、通信技術、嵌入式技術有機整合形成的一個新式協同系統[1].它由大量的傳感器節點組成，通常用來檢測一個區域的環境參數，并將收集到的數據發送給基站.由于其功耗低、無線傳輸、無線傳感等特點，常常被應用于目標跟蹤、環境檢測等領域[2].但WSN電池能量有限且不易補充，有生存時間較短的問題，限制了其推廣應用[3].

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

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

1 LEACH算法

1.1 簇的建立

LEACH算法工作過程分為初始化階段和穩定階段.為了節省資源開銷，穩定階段的持續時間大于初始化階段的持續時間.簇的建立過程可分成4個階段：簇首節點的選擇、廣播、建立，和調度機制的生成.

1.1.1 初始化階段

在簇首節點選取準備階段開始時，每個節點產生一個值為0～1之間的隨機數，并與閾值T（n） 進行比較，若隨機值小于閾值則該節點當選為簇首節點，T（n）的計算公式如下：

其中，p為成為簇首節點的期望百分比，r為輪數，G為1p輪還沒有當選簇首節點的節點集合，·為向下取整運算.

節點成為簇首節點后，向網絡中廣播自己成為簇首節點的消息，非簇首節點根據收到信號的強弱程度決定是否加入該簇，并向加入簇的簇首節點發送申請信息.當簇首節點收到申請加入信息后，通過時分多址（TDMA）建立通信時間表，并向簇內廣播，至此，初始化階段完成.

1.1.2 穩定階段

簇內非簇首節點按照之前分配好的通信時間表，將采集到的數據發給簇首節點，隨后進入休眠狀態.簇首節點將接收到的數據進行融合后，轉發給基站.穩定階段的時間遠遠大于初始化階段的時間.

1.2 LEACH算法的不足

LEACH 算法中，簇首節點的選舉完全是隨機的，易出現簇首節點分布不均的問題.而在智能家居應用中，傳感器節點往往分布在由許多小區域組成的空間里，造成有的區域里有多個簇首節點，而有的區域里沒有簇首節點，嚴重影響整個網絡的壽命.此外，由于沒有考慮到節點剩余能量因素，可能出現剩余能量低的節點重復當選簇首節點的問題，加速該節點的死亡速度，影響網絡的壽命.

2 LEACH-ED算法

2.1 網絡模型的假設

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

2.2 無線通信能量消耗模型

2.3 LEACH-ED算法描述

利用加權思想對LEACH算法進行改進，使節點產生一個基于能量和密度的權值，通過這個權值概率閾值選擇簇首節點，進而生成整個簇.該權值綜合考慮了節點所處的網絡環境和本身狀態，節點的鄰居節點越多，成為簇首節點的概率就越大，成為簇首節點的概率越大.

改進后的閾值其中，Eres為節點的剩余能量，E0為節點的初始能量，nneb為鄰居節點數量，Ncnum為簇內成員數量，γ1與γ2分別為權值影響因子，且γ1+γ2=1.

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

3 仿真結果與分析

3.1 仿真環境以及模型配置

實驗設置網絡中有100個節點隨機地分布在長寬為100 m×100 m的仿真場景內，基站位于坐標（50，50）處，網絡拓撲圖如圖2所示.每幀數據為500 B，并假定各節點總有數據向基站發送[11].每個節點的初始能量設為0.02 J，Eda為0.02 nJ·bit-1·m-2，控制信息大小CM為32 bit，數據信息大小DM為 4000 bit，權值影響因子為0.55，網絡中簇首節點個數所占比例p=0.1，Eelec=10 nJ·bit-1[12].

3.2 仿真波形及分析

通過Matlab仿真軟件對傳統LEACH算法以及LEACH-ED算法進行仿真，輪數-節點死亡數關系曲線如圖3所示.由圖3可知，隨著輪數的不斷上升，LEACH-ED算法的優勢逐漸體現出來，與傳統LEACH算法相比，提高了網絡的生命周期.

4 結 論

在傳統LEACH算法的基礎上，考慮了節點的能量以及密度因素，提出改進的LEACH-ED算法，根據節點的剩余能量選取簇首節點，避免能量較低的節點再次當選簇首節點的情況，使網絡中節點的剩余能量趨于平均.仿真實驗結果表明：與LEACH算法相比，LEACH-ED算法延長了網絡的生命壽命，降低了網絡的平均能耗.但是該算法未考慮穩定階段的傳輸問題，有待后續開展進一步的研究工作.

參考文獻：

[1] 梁度，劉夢璐，章成駒.一種LEACH的分簇優化策略 [J].北京聯合大學學報，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協議的無線傳感網能效分簇算法 [J].吉林大學學報（信息科學版），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協議分析與仿真 [J].電子測量技術，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中基于權值的LEACH協議的研究與改進 [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] 柴寶杰，馬寶英，范書平，等.無線傳感器網絡中改進的EEUC路由算法 [J].微計算機信息，2012（9）：366-368.

CHAI B J，MA B Y，FAN S P，et al.Improved EEUC routing algorithms in wireless sensor networks [J].Microcomputer Information，2012（9）：366-368.

[8] 馮永亮，雷偉軍.無線傳感器網絡LEACH協議的研究與改進 [J].信息技術，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] 鄧亞平，鄧利軍.無線傳感器網絡的能量有效加權分簇算法 [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].計算機應用，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.

（責任編輯：包震宇，顧浩然）