基于LEACH協議簇頭定位算法研究

丁俊美 ，范生海

(1.合肥財經職業學院 人工智能學院， 安徽 合肥 230601；2.鹽城工學院 材料科學與工程學院， 江蘇 鹽城 224051)

無線傳感器網絡WSN是一種可以對被感知對象的信息進行發送、采集、處理、融合等系列操作的自組織無線網絡［1］。網絡中大量傳感器節點通常布設在較為惡劣的環境中，許多學者一直在尋求一種既能均衡能耗、又能延長網絡壽命的路由算法，其中最早、最為經典的是由Heinzelman等［2］于2000年提出的分簇路由協議LEACH，該協議將網絡劃分成多個簇，大大降低了網絡能耗。2002年，Heinzelman等［3］對此協議進行了改進，提出了LEACH-C協議，其節點可以將自身的坐標信息和剩余能量信息傳輸給基站，優化了簇頭選擇，很好地節省了普通節點的能耗；2017年，黃利曉等［4］提出了LEACH-improved節能算法，通過加入間距因子、剩余能量因子和節點密度因子來改進閾值計算公式，再綜合考慮節點剩余能量和地理位置選擇簇首；2019年，常鐵原等［5］提出了OLEACH算法，在成簇過程中加入簇頭節點的能量和節點距各簇頭的距離等參考量對成簇過程進行優化；2021年，Maheshwari等［6］提出使用蝴蝶優化算法選取最佳簇首，有效地延長了網絡的壽命；同年，馬澤等［7］提出LEACH-HD算法，通過推導一階無線能量模型，得到最佳簇首數目，再通過加入節點的剩余能量因子和節點與主機節點的平均距離因子，改進了簇首節點的選擇方式。

本文在深入分析LEACH算法及其改進算法的基礎上，綜合考慮網絡簇頭邊緣化、分布不均的情況，提出一種簇頭定位控制的路由算法。

1 LEACH協議剖析

LEACH算法是一個比較經典的單跳分簇協議［8］，該算法使每輪成簇過程中各個傳感器節點成為簇頭的機會相等，并循環下去。每輪成簇都可分為兩個階段，分別是簇的建立和穩定階段。

在簇的建立過程中，簇頭的選取最為關鍵。節點成為簇頭的條件是第n個傳感器節點的隨機數T(n)大于該傳感器節點自動生成的隨機數，此隨機數為0～1。當某個節點成為簇頭后，需要廣播自己成為簇頭節點的消息［9］。

T(n)的計算公式如式（1）所示。

式中：T(n)表示第n個傳感器節點的隨機數；P表示簇頭節點占總節點數的百分比；r為當前循環輪數，輪；n表示第n個傳感器節點；G表示過去1/P輪中仍未當選簇頭的節點集合。

顯然，如果簇頭數固定，隨著r的減小、T(n)的增大，所有節點最后都有機會成為簇頭［10］。

LEACH協議僅僅在概率的角度上體現節點成為簇頭的公平性，而沒有把節點的能耗、邊緣化以及簇頭密度等作為簇形成的重要影響因素［11］。LEACH協議的不足之處如下：

（1）未將節點剩余能量考慮進LEACH算法。因為節點的類型和距離不同，其能耗也不相同。

（2）LEACH協議簇頭選取具有隨機性。如果簇頭選在網絡的邊緣，簇頭的覆蓋面積會變小，傳輸數據的能耗就會過大［12］。

（3）LEACH協議沒有對簇頭選取區域進行限制，造成簇頭密度不均，大部分簇頭與基站間距較遠，能量消耗過大。

2 LEACH協議能量模型

LEACH協議采用一階無線通信模式［13］，如圖1所示。該模式中，能量的消耗主要發生在數據接收和發送過程中。

圖1 無線通信模型Fig.1 Wireless communication model

當兩節點的距離為dm，發送數據總量為lbit時，發送過程與接收過程的能量消耗ETX(l，d)、ERX(l)計算公式分別如式（2）、式（3）所示［14］。

式中：ETX(l，d)表示發送數據lbit到距離為dm的另一個節點需要耗費的總能量，J；Eelec為發送和接收單位數據的能量消耗，為50 nJ/bit，包括電磁數據編碼、發送、接收和調制解調等消耗的能量；ETX-mp(l，d)為發送數據信號放大電路的能量消耗，J；εmp、εfs為放大器的增益，均為常數，在一階無線通信模式中，當d≥d0(d0=時，εmp為多路衰減信道模型下的功率放大系數，為0.0013 pJ/(bit·m4)，當d＜d0時，εfs為自由空間信道模型下的功率放大系數，為10 pJ/(bit·m2)；ERX(l)為接受lbit的數據需要消耗的能量，J。

3 LEACH協議改進

在網絡建設的初始階段，各節點能量相同，隨著時間的推移，因傳感器類型、節點與簇頭距離的不同，導致各節點剩余能量發生較大變化。為盡量不將能量較低的節點選為簇頭，導致網絡過早死亡。在簇頭選取時，要加入能量比例，優先選擇剩余能量多的節點成為簇頭［15］。改進后的T(n)計算公式如式（4）所示。

式中：Er、Ei分別為節點的當前能量和初始能量，J。

為避免將網絡邊緣區域節點選為簇頭，可以在式（4）中加入節點距離中心基站的面積比例，在滿足所有節點覆蓋情況下，縮短節點至簇頭、簇頭至基站的傳輸距離［16］，使所選的簇頭盡量靠近中心基站，簇頭節點的覆蓋面積盡量最大。

改進后的T(n)計算公式如式（5）所示。

式中：μ為常量，表示節點的能耗比例和面積比例在T(n)中所占的比重；S為節點到中心基站的距離R形成的圓形區域面積，即S=πR2；Smax為最遠節點至中心基站的距離Rmax形成的網絡面積，Smax=。

除了考慮簇頭剩余能量和邊緣化之外，簇頭的密度對網絡影響也比較大。在LEACH協議中，為了防止簇頭位置在某區域過于密集，在選取簇頭時，可對簇頭之間的距離進行限制［17］，使得簇頭分布較為均勻。

簇頭之間最小距離公式如式（6）所示。

式中：L為簇頭間距的最小門限值，m；N為傳感器節點總數［18］。

4 模擬仿真及結果分析

4.1 仿真準備

在模擬仿真實驗中，將改進后綜合考慮了簇頭剩余能量、簇頭邊緣化、簇頭密度算法的LEACH協議命名為LEACH-NEW協議，將僅考慮簇頭剩余能量、減小簇頭邊緣化、簇頭密度均勻化算法的LEACH協議分別命名為LEACH-EN協議、LEACH-MA協議、LEACH-DE協議。仿真實驗前需要確定最優簇頭個數K和μ值。對于一定區域內的傳感器網絡，最優簇頭個數K由傳感器節點的總個數N和簇頭到基站距離共同決定［19］。

優化后的最優簇頭數計算公式如下：

式中：K為最優簇頭個數；M為監測區域邊長，m；dtoBS為簇頭到基站的距離，m。

仿真前，確定網絡節點布設圖如圖2所示，仿真參數如表1所示。圖2中，黑色正三角形為基站（Sink節點），位于中心點，坐標為（50，50）m；實心正圓為新一輪簇形成后的簇頭；空心正圓為普通節點。當簇頭位于圖2監測區域的中心點時，簇頭到基站距離dtoBS最短，為0；當簇頭在4個角時，距離dtoBS最大，為71 m，因此，本仿真實驗中dtoBS取值為0～71 m。

表1 實驗仿真參數Table 1 Experimental simulation parameters

圖2 網絡節點布設圖Fig.2 Layout diagram of network nodes

將dtoBS值及表1中參數代入公式（7），得到最優簇頭數K為4～5個，由P=K/N得出簇頭節點與總節點數百分比P的最優值為4%～5%。本實驗簇頭數K選擇5個，P取5%。

仿真時需要對各種算法進行性能比較，而μ值對新算法LEACH-NEW的影響較大，因此仿真前必須確定μ值。為此，需要在LEACH-NEW算法下，對網絡死亡時間及發送數據量進行綜合比較，從而固定μ值。

設網絡第一個節點死亡時間為T1，所有節點死亡的時間為Ts，網絡存活期內節點給基站發送的總數據量為D，根據表1的仿真參數，經過多輪仿真，得到結果如表2所示。

表2 不同μ值性能參數對比Table 2 Comparison of performance parameters of different μ values

由表2可知，當μ=0.6時，網絡第一個節點死亡時間T1約為470 s，網絡整體死亡時間Ts約為790 s，數據接收總量為2141 603 B，均優于其它μ值時的網絡性能。因此，取μ=0.6，此時T1、Ts、數據傳輸總量均最大，網絡整體性能最佳。

4.2 模擬仿真

根據上面確定的最優簇頭數K=5、P=5%、μ=0.6，以及表1的仿真參數，采用MATLAB對以上含LEACH算法的5種算法下Sink節點數據接收量、節點存活時間、能量消耗3個方面進行仿真［20］，結果如圖3～圖5及表3所示。

表3 網絡性能對比表Table 3 Comparison table of network performance

圖3 接收數據量仿真結果曲線圖Fig.3 Simulation result curve of received data volume

由圖3、圖4及表3可知，在運行前期，5種協議的數據量基本相同，但LEACH協議的數據接收量約在410 s出現拐點，并首先出現節點死亡，約在690 s節點全部死亡，接收的數據總量為1543 675 B；基于簇頭密度均勻化的LEACH-DE協議約在420 s出現節點死亡，約在720 s節點全部死亡，接收的數據總量為1702 541 B；基于減小簇頭邊緣化的LEACH-MA協議約在440 s出現節點死亡，約在740 s節點全部死亡，接收的數據總量為1877 492 B；基于剩余能量的LEACH-EN協議約在450 s出現節點死亡，約在760 s節點全部死亡，接收的數據總量為1982 474 B；LEACHNEW協議約在470 s出現節點死亡，約在790 s節點全部死亡，接收的數據總量為2141 603 B。因此改進后的LEACH-NEW協議不僅在數據接收總量方面均優于其他4種協議，也有效地延長了網絡的整體壽命。

圖4 存活節點仿真結果曲線圖Fig.4 Simulation result curve of living node

由圖5的整個網絡能耗與網絡存活周期之間關系曲線可以看出，所有協議在前期階段能量消耗較快，在后期階段逐漸放緩，主要因為節點死亡速度逐漸加快。LEACH協議網絡總能量在690 s左右消耗完畢；LEACH-DE協議在720 s左右總能量消耗結束；LEACH-MA協議在740 s左右總能量消耗結束；LEACH-EN協議在760 s左右總能量消耗結束；LEACH-NEW協議在790 s左右總能量消耗結束，且能耗曲線相對其他協議更加平緩，即LEACH-NEW協議能耗均衡性更好，原因在于LEACH-NEW協議的簇頭選取算法比其他協議的有效性更好，在每一輪簇頭選取過程都節省了節點的能量，從而降低了網絡的總體能耗。

圖5 能量消耗仿真結果曲線圖Fig.5 Simulation result curve of energy consumption

5 總結

本文在傳統LEACH算法基礎上進行了改進，綜合考慮了無線傳感器網絡節點的剩余能量、節點到基站中心區域的面積約束條件、簇頭節點密度的優化，保證了網絡簇頭節點覆蓋面積最大化和密度均勻化。通過對改進前后的算法進行大量的仿真試驗及結果分析，可以看出改進后的LEACH-NEW算法在網絡節點存活時間、能量消耗及發送數據總量的優越性，表明該算法是一種有效的分簇算法。