基于雙簇頭及數據融合的改進LEACH算法的網絡拓撲控制研究

宋錦波 徐海芹 宮曉慧 劉洋

摘要：針對LEACH算法固有的能量損耗問題，對其數據融合率以及簇頭的選舉進行重新規劃。在數據融合階段，采用模糊理論定義各節點的信任度，實現最優形式進行數據融合。利用最優簇頭率求解最佳簇頭數目，引入主副簇頭概念，有效保證了數據安全性，且以特有雙簇頭輪換模式減少了能量的損耗。研究結果表明，該算法可以有效減少簇頭競選次數，避免不必要能量損耗，延長網絡生存周期。

關鍵詞：數據融合率;最優簇頭數;雙簇頭;網絡生存周期

中圖分類號：TP393

文獻標志碼：A

文章編號：1006-1037（2021）03-0022-06

隨著無線傳感器網絡的不斷發展，應用范圍也隨之不斷地擴大，現已被廣泛的應用在數據采集、軍事偵察、環境檢測等方面，網絡內的節點可以感知周圍環境[1]，對數據進行接收、處理和轉發。在無線傳感器網絡中，從路由結構要素出發可以分為平面路由協議和分簇路由協議[2-3]。前者設計較為簡單，適用于小型網絡環境中;后者的健壯性較好，擴展性佳，相對于平面路由協議有著較為明顯的優勢。LEACH協議作為一種比較經典的分簇路由協議，基于傳統分簇協議，將感知到的數據發送到無線傳感器網絡（Wireless Sensor Network，后簡稱WSN）選取的簇頭（Cluster Header，后簡稱CH）上，簇頭節點將接收到的數據轉發送至基站處，數據的接收與轉發是一個消耗能量的過程[4]，而數據的接收與轉發又分為簇內集群信息的傳遞以及簇間信息的傳遞[5]，傳輸的數據量在能量損耗中占了一定的比重。LEACH不僅在選取簇頭時具有很大的隨機性，在冗余數據上也沒有做過多的處理，但網絡的生存周期與分簇的結果和數據量的發送息息相關，為了優化能量消耗并延長網絡的周期[6]，現對網絡的簇頭的選取進行重新規劃，首先計算出當前網絡環境的最優簇頭數目[7-9]并對此進行合理劃分區域[10]，同時引入雙簇頭概念[11]，簇頭的選舉會考慮通信代價[12]，對于數據傳輸中的冗余數據計算出最優融合率[13]，以達到有效地延長網絡的生命周期[14]。

1 LEACH算法介紹

LEACH（Low Energy Adaptive Clustering Hierarchy）算法是Heinzelman提出的一種低能耗自適應聚簇分層型協議算法，是一種以輪的形式進行迭代的算法，每個輪分為初始化和穩定通信兩個階段。初始化時每一輪會隨機選舉簇頭，給予每個節點一個隨機值，并與閾值T（n）進行比較。當小于閾值T（n）時，則當前節點被選舉成為簇頭節點;穩定通信時，節點向簇頭傳送數據，簇頭接收簇內節點數據并轉發到基站。

1.1 LEACH算法的簇頭選舉階段和簇的形成

LEACH算法在每一輪都會重新構建簇的集群，首先網絡內的各節點會隨機生成一個[0，1]之間的數值rand，然后將這個節點的rand值與T（n）比較，當前節點rand值小于當前的閾值時，則該節點被標記成為該輪次的簇頭節點，否則該節點為普通節點。T（n）的計算公式

其中，p是簇頭在網絡中的節點所占的比例，r是當前選舉的輪數，n是網絡的節點數，S是r輪后還未當選過簇頭的節點的集合。

當每一輪選舉出簇頭后，簇頭節點會發布廣播信息告知自己可達跳數范圍內的節點自己當選簇頭的信息，節點會根據各自接收到的節點的信息強度進行判斷自己屬于哪個簇頭節點構建的集群（就近原則），然后簇內節點會發送自己的節點id和位置信息到簇頭處，簇頭構建簇群內節點信息表進行保存，同時簇頭按照時分復用（Time Division Multiple Access，后簡稱TDMA）為每一個節點劃分時隙用以發送數據或停止工作進入睡眠狀態，簇內節點會根據TDMA原則采集數據和發送數據到簇頭處，同時在自己的休眠時間點不再工作，進入睡眠狀態后直到下一次被喚醒。當簇內節點信息發送完畢后，簇頭將接受該數據并與其自身的數據進行一定的融合，融合后的數據將被發送至基站處，基站會接收所有簇頭節點的信息然后統一將節點信息發送到用戶處，如此反復進行，每一輪都需要重新選舉簇頭節點。

1.2 LEACH算法的能量消耗

LEACH的能量損耗主要在于節點發送數據和接收數據兩方面，其中普通節點發送數據和接收數據的能量損耗為

其中，Eelec為無線電接收和發送單位比特數據的能耗系數，參數εfs和εmp代表的是自由空間模型的能耗系數和多徑衰落能耗中的系數，d0= εfs/εmp，d0決定了LEACH使用什么樣的模型，d是目標節點到源節點的距離，當節點距離小于等于d0時，傳輸模型采用自由空間模型，反之則使用多徑衰落模型。

節點接收L位數據的能量損耗為

2 TLE-LEACH算法

針對傳統LEACH算法的不足，本文提出基于融合率和計算簇頭節點最低能耗的改進TLE-LEACH（The Least Energy- Low Energy Adaptive Clustering Hierarchy）算法。引入數據融合率，首先利用信任度函數計算綜合信任度，搭建信任矩陣，在簇頭處對傳感器節點所測得數據進行一定的融合，發送給基站;再根據能量損耗最低的原則進行簇頭選取，分別計算簇內各節點和簇頭節點所需的能量損耗，考慮節點的信任度，計算求得最佳簇頭C1和C2，C2作為備選簇頭，當C1的能量低于簇內節點的平均能量時，備選簇頭C2則代替C1進行數據傳輸，二者不斷輪換當選簇頭，直到C1、C2能量均低于簇內平均能量時，簇內開始重新選舉簇頭。當網絡內70%節點死亡后，節點采用單步傳輸數據到基站，直到90%節點死亡，網絡癱瘓。

2.1 簇的形成階段

在節點比較密集的地方，不可避免地會出現節點收集到的信息是重復的，傳輸這些數據對于簇頭的能量損耗是比較大的，所以需要在簇頭節點處對冗余數據進行一定的融合，引入數據融合率的概念，以減少數據的冗余。

由文獻[15]可知，數據融合率算方法如下：初始化網絡迭代的輪數，節點需要計算集群內各節點對于自己的信任度并采用模糊理論對數據之間的接近程度進行處理，利用其構建信任矩陣w，計算數據融合率并利用矩陣存儲相應的信息。

信任度函數構建如下：N個傳感器節點對于同一數據進行監測，Xi和Xj為第i個節點和第j個節點測得的數據，且都服從高斯分布，pi（x） 和pj（x）是傳感器的特性函數，Xi和Xj的一次觀測值用xi，xj表示，二者之間的偏差用置信距離測度反映。

2.2 最優簇頭數的計算

在一個網絡中，節點當選簇頭后需要承擔發送數據到基站并接收節點信息的任務，同時告知節點自己成為簇頭信息等。但這些過程都需要消耗能量，簇頭數目過多時，簇頭節點與基站直接進行信息傳輸，會增加網絡節點的能耗，簇頭數目較少時，會加大簇頭的能量損耗，加重簇頭負擔，以至于簇頭過快死亡影響整個網絡的運行[8]。當選舉出來的簇頭節點的位置距離基站較遠時，簇頭到基站的數據傳輸壓力就會加大，嚴重影響了簇頭的存活性，因而簇頭數目的多少和分布關乎到整個網絡的生存周期。

由此可見網絡的區域劃分即簇頭的數目對于網絡整體生存周期的延長十分重要，而原有的LEACH算法生成的簇頭數具有隨機性，對于傳感器節點賦予的隨機數的大小依賴十分巨大，在LEACH初步分區的基礎上根據當前能量的損耗計算出當前網絡中的最佳簇頭數k并根據簇頭的數目進行區域的劃分。

假設此時網絡中的節點數為N，簇頭節點的能量損耗主要在于接收節點的數據所造成的能量損耗ERN，轉發數據到基站所造成的能量損耗EHB以及對節點傳送過來的數據進行融合所造成的能量損耗EDA。簇頭節點接收集群內節點的數據造成的能量損耗為[19]

其中，Nalive指的是當前網絡中的節點存活數量，根據kopt對網絡內的節點進行區域的劃分，令kopt=k，分區完成后會根據每一輪的節點存活數目重新計算出最優的簇頭數并以此重新進行區域劃分，傳統的區域劃分是k個區域內定義k個簇頭，簇頭承擔起簇內集群內節點的數據轉發和融合，但由于考慮傳感器節點傳輸數據安全性以及在競選簇頭階段減少能量損耗的需要，現提出主副簇頭的概念，在k個區域內現引入副簇頭，區域內簇頭節點依據每個簇頭節點能量損耗最少的原則進行競聘，網絡能耗最少的當選主簇頭C1（Cluster1），能量消耗其次的，并引入主簇頭和基站的距離因子考慮C2（Cluster2）副簇頭。副簇頭用于接收主簇頭傳遞過來的數據，保證了數據的安全性，防止主簇頭突然死亡引起的數據丟失;另一方面，當主簇頭的能量低于簇內節點平均能量時，會比較副簇頭與簇內平均能量的大小，若高于簇內平均能量，則副簇頭當選為主簇頭，主簇頭為副簇頭，直到主副簇頭的能量均低于簇內能量或副簇頭能量低于總能量的10%時，進行下一輪簇頭選舉，極大的減少了由簇頭的選舉而帶來的能量損耗。

3 實驗結果分析

在300×300的區間內隨機分布了200個傳感器節點，各節點通信能力相同，初始能量均相同，基站位于中心位置。仿真環境是Matlab2017b，電腦為聯想拯救y7000，處理器為Intel（R） Core（TM） i7-9750H。

3.1 死亡節點數

整個傳感器網絡的性能好壞與傳感器網絡的生存時間息息相關，現通過各時間的節點死亡數目來進行衡量。圖1是協議改進前后死亡節點數隨時間變化的曲線，可以看出LEACH算法在2 000輪左右時，90%節點已經全部死亡，網絡自此進入癱瘓不再感知和傳送數據。TLE-LEACH算法在前期節點死亡較多是因為前期簇頭C1和C2承擔的簇內節點數據的接收，距離較遠的容易較先死亡，在網絡的500輪后，TLE-LEACH算法節點死亡速率較為平緩，網絡生命周期持續到了15 000輪左右，相對于LEACH的2 000輪，網絡的生命周期有了較好的改善。

3.2 網絡能耗圖

網絡的總能量消耗可以衡量一個系統性能上的好壞，節點的能量損耗在傳感器網絡中占據了較為重要的部分，圖2是協議改進前后網絡能量隨著時間變化的曲線，如圖所示LEACH在2 000輪左右能量消耗殆盡，而TLE-LEACH在后續的競選中簇頭C1、C2競選次數越來越少，使得能量的損耗大為減少，直到15 000輪左右時能量幾乎耗盡，有效的延長了網絡生存周期。

3.3 基站接收數據

圖3是協議改進前后基站數據的接收量隨著時間的變化的曲線圖，可以看出TLE-LEACH算法在數據的轉發量上有了較大的改進，原有的LEACH算法由于每輪選舉簇頭導致能量消耗較快，生命周期較短，發送數據量少，Sink節點接收的數據量就少，而TLE-LEACH算法的數據融合、最優簇頭和雙簇頭機制有效的加長了網絡的生存周期，增加了數據的發送量和基站接收的數據量，相對于LEACH算法，數據量的接收提升較大。

4 結論

無線傳感器網絡內的節點自身能量受限，且在一些惡劣的環境中，節點不易被替換，故需要盡量減少網絡能耗，盡可能的延長網絡生命周期。本文首先分析了LEACH協議，針對傳統的LEACH算法，TLE-LEACH算法首先在簇頭節點的選擇上考慮了對冗余數據的融合以及最優簇頭率，其次在LEACH的基礎上引入了雙簇頭的概念，一方面加強了數據傳輸的安全性，另一方面由于減少了簇頭的輪換進而減少了能量損耗以達到延長網絡生存時間，傳輸更多數據的目的。仿真實驗結果表明，本文提出的TLE-LEACH算法可以有效地延長網絡生存時間，降低能耗，提升基站接收到的數據量，進而提升了網絡整體的性能。本文依舊存在不足，在副簇頭的選取時由于LEACH算法的隨機性過大，網絡節點內分區的數目會隨之改變，主副簇頭的選取也會隨之改變，能量損耗與主副簇頭的選取個數以及位置有關。簇內節點到簇頭的數據傳輸以及簇頭到基站的數據也是單跳形式進行傳輸，造成的能量損耗較大。在后續的工作中，可以考慮對LEACH算法的簇頭選取進行一定的約束，同時在簇內和簇間數據傳輸時引入不同的路徑規劃算法，減少傳感器網絡的能量損耗來更好的延長網絡生命周期。

參考文獻

[1]YANG L， LU Y， LIU S， et al. A Dynamic behavior monitoring game based trust evaluation scheme for clustering in wireless sensor networks[J]. IEEE Access， 2018， （99）： 71404-71412.

[2]李蘭鳳，馬佳榮.無線傳感器網絡路由協議分析[J].網絡安全技術與應用，2019（5）：64-66.

[3]劉偉，杜佳鴻，賈素玲，等.能量有效的無線傳感器網絡分簇路由協議[J].北京航空航天大學學報，2019，45（1）：50-56.

[4]徐晶晶，張欣慧，許必宵，等.無線傳感器網絡分簇算法綜述[J].計算機科學，2017，44（2）：31-37.

[5]CHEN D R， CHEN L C， CHEN M Y， et al. A coverage-aware and energy-efficient protocol for the distributed wireless sensor networks. 2019， 137：15-31.

[6]KHALIL E A， ATTEA B A， et al. Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks [J]. Swarm and Evolutionary Computation， 2011， 1（4）：195-203.

[7]李雪，南建國.基于IK-means聚類的分簇路由算法[J/OL].計算機應用研究：1-7[2021-01-29].https：//doi.org/10.19734/j.issn.1001-3695.2020.04.0104.

[8]章春華，陳宏偉.LEACH協議簇頭選擇算法的改進與研究[J].湖北工業大學學報，2012，27（2）：19-22.

[9]郭前崗，周德祥，周西峰.LEACH路由協議最優簇頭數計算方法[J].微型機與應用，2013，32（3）：61-63+66.

[10] 蔣勇，趙作鵬.低能耗的無線傳感網絡分層聚類與節點管理機制[J].計算機工程與設計，2019，40（3）：638-643.

[11] 張頂，張琳.基于K-Means的WSN動態信任度雙簇頭選取算法[J].南京郵電大學學報（自然科學版），2020，40（2）：108-114.

[12] 李蕾，方明科.基于證據理論加權融合的無線傳感器網絡路由算法[J].吉林大學學報（理學版），2020，58（5）：1223-1228.

[13] 孔玉靜，侯鑫，華爾天，等.基于BP神經網絡的無線傳感器網絡路由協議的研究[J].傳感技術學報，2013，26（2）：246-251.

[14] 石蔚，賈小珠. 一種Ad Hoc網絡混合式分簇路由算法[J].青島大學學報（自然科學版），2009，22（4）：62-66.

[15] 張秋，梁小凡，孫順遠，等.基于數據融合率的WSN節能策略[J].計算機測量與控制，2013，21（2）：454-457.

[16] DANIEL C. On the solution of linear differential equations with singular coefficients[J]. Journal of Differential Equations， 1982， 46（2）： 310-323.

[17] MADAN R， LALL S. Distributed algorithms for maximum lifetime routing in wireless sensor networks[J]. IEEE Trans on Wireless Communications， 2006， 5（8）： 2185-2193.

[18] 王勇，楊杰.基于無線傳感網絡定位的網關功能模塊的實現[J]. 青島大學學報（自然科學版），2016，29（1）：80-84.

[19] 章春華，陳宏偉.LEACH協議簇頭選擇算法的改進與研究[J].湖北工業大學學報，2012，27（2）：19-22.

[20] SOURABH P， AVINASH K. An application and architecture of low energy adaptive clustering hierarchy protocol in wireless microsensor network[J].Intematioual Journal of Engineering，Science and Mathematic， 2018， 7（3）：314-326.