基于LEACH協(xié)議簇頭定位算法研究

丁俊美 ，范生海

(1.合肥財(cái)經(jīng)職業(yè)學(xué)院 人工智能學(xué)院， 安徽 合肥 230601；2.鹽城工學(xué)院 材料科學(xué)與工程學(xué)院， 江蘇 鹽城 224051)

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

本文在深入分析LEACH算法及其改進(jìn)算法的基礎(chǔ)上，綜合考慮網(wǎng)絡(luò)簇頭邊緣化、分布不均的情況，提出一種簇頭定位控制的路由算法。

1 LEACH協(xié)議剖析

LEACH算法是一個(gè)比較經(jīng)典的單跳分簇協(xié)議［8］，該算法使每輪成簇過程中各個(gè)傳感器節(jié)點(diǎn)成為簇頭的機(jī)會(huì)相等，并循環(huán)下去。每輪成簇都可分為兩個(gè)階段，分別是簇的建立和穩(wěn)定階段。

在簇的建立過程中，簇頭的選取最為關(guān)鍵。節(jié)點(diǎn)成為簇頭的條件是第n個(gè)傳感器節(jié)點(diǎn)的隨機(jī)數(shù)T(n)大于該傳感器節(jié)點(diǎn)自動(dòng)生成的隨機(jī)數(shù)，此隨機(jī)數(shù)為0～1。當(dāng)某個(gè)節(jié)點(diǎn)成為簇頭后，需要廣播自己成為簇頭節(jié)點(diǎn)的消息［9］。

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

式中：T(n)表示第n個(gè)傳感器節(jié)點(diǎn)的隨機(jī)數(shù)；P表示簇頭節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)的百分比；r為當(dāng)前循環(huán)輪數(shù)，輪；n表示第n個(gè)傳感器節(jié)點(diǎn)；G表示過去1/P輪中仍未當(dāng)選簇頭的節(jié)點(diǎn)集合。

顯然，如果簇頭數(shù)固定，隨著r的減小、T(n)的增大，所有節(jié)點(diǎn)最后都有機(jī)會(huì)成為簇頭［10］。

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

（1）未將節(jié)點(diǎn)剩余能量考慮進(jìn)LEACH算法。因?yàn)楣?jié)點(diǎn)的類型和距離不同，其能耗也不相同。

（2）LEACH協(xié)議簇頭選取具有隨機(jī)性。如果簇頭選在網(wǎng)絡(luò)的邊緣，簇頭的覆蓋面積會(huì)變小，傳輸數(shù)據(jù)的能耗就會(huì)過大［12］。

（3）LEACH協(xié)議沒有對簇頭選取區(qū)域進(jìn)行限制，造成簇頭密度不均，大部分簇頭與基站間距較遠(yuǎn)，能量消耗過大。

2 LEACH協(xié)議能量模型

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

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

當(dāng)兩節(jié)點(diǎn)的距離為dm，發(fā)送數(shù)據(jù)總量為lbit時(shí)，發(fā)送過程與接收過程的能量消耗ETX(l，d)、ERX(l)計(jì)算公式分別如式（2）、式（3）所示［14］。

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

3 LEACH協(xié)議改進(jìn)

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

式中：Er、Ei分別為節(jié)點(diǎn)的當(dāng)前能量和初始能量，J。

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

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

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

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

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

式中：L為簇頭間距的最小門限值，m；N為傳感器節(jié)點(diǎn)總數(shù)［18］。

4 模擬仿真及結(jié)果分析

4.1 仿真準(zhǔn)備

在模擬仿真實(shí)驗(yàn)中，將改進(jìn)后綜合考慮了簇頭剩余能量、簇頭邊緣化、簇頭密度算法的LEACH協(xié)議命名為LEACH-NEW協(xié)議，將僅考慮簇頭剩余能量、減小簇頭邊緣化、簇頭密度均勻化算法的LEACH協(xié)議分別命名為LEACH-EN協(xié)議、LEACH-MA協(xié)議、LEACH-DE協(xié)議。仿真實(shí)驗(yàn)前需要確定最優(yōu)簇頭個(gè)數(shù)K和μ值。對于一定區(qū)域內(nèi)的傳感器網(wǎng)絡(luò)，最優(yōu)簇頭個(gè)數(shù)K由傳感器節(jié)點(diǎn)的總個(gè)數(shù)N和簇頭到基站距離共同決定［19］。

優(yōu)化后的最優(yōu)簇頭數(shù)計(jì)算公式如下：

式中：K為最優(yōu)簇頭個(gè)數(shù)；M為監(jiān)測區(qū)域邊長，m；dtoBS為簇頭到基站的距離，m。

仿真前，確定網(wǎng)絡(luò)節(jié)點(diǎn)布設(shè)圖如圖2所示，仿真參數(shù)如表1所示。圖2中，黑色正三角形為基站（Sink節(jié)點(diǎn)），位于中心點(diǎn)，坐標(biāo)為（50，50）m；實(shí)心正圓為新一輪簇形成后的簇頭；空心正圓為普通節(jié)點(diǎn)。當(dāng)簇頭位于圖2監(jiān)測區(qū)域的中心點(diǎn)時(shí)，簇頭到基站距離dtoBS最短，為0；當(dāng)簇頭在4個(gè)角時(shí)，距離dtoBS最大，為71 m，因此，本仿真實(shí)驗(yàn)中dtoBS取值為0～71 m。

表1 實(shí)驗(yàn)仿真參數(shù)Table 1 Experimental simulation parameters

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)布設(shè)圖Fig.2 Layout diagram of network nodes

將dtoBS值及表1中參數(shù)代入公式（7），得到最優(yōu)簇頭數(shù)K為4～5個(gè)，由P=K/N得出簇頭節(jié)點(diǎn)與總節(jié)點(diǎn)數(shù)百分比P的最優(yōu)值為4%～5%。本實(shí)驗(yàn)簇頭數(shù)K選擇5個(gè)，P取5%。

仿真時(shí)需要對各種算法進(jìn)行性能比較，而μ值對新算法LEACH-NEW的影響較大，因此仿真前必須確定μ值。為此，需要在LEACH-NEW算法下，對網(wǎng)絡(luò)死亡時(shí)間及發(fā)送數(shù)據(jù)量進(jìn)行綜合比較，從而固定μ值。

設(shè)網(wǎng)絡(luò)第一個(gè)節(jié)點(diǎn)死亡時(shí)間為T1，所有節(jié)點(diǎn)死亡的時(shí)間為Ts，網(wǎng)絡(luò)存活期內(nèi)節(jié)點(diǎn)給基站發(fā)送的總數(shù)據(jù)量為D，根據(jù)表1的仿真參數(shù)，經(jīng)過多輪仿真，得到結(jié)果如表2所示。

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

由表2可知，當(dāng)μ=0.6時(shí)，網(wǎng)絡(luò)第一個(gè)節(jié)點(diǎn)死亡時(shí)間T1約為470 s，網(wǎng)絡(luò)整體死亡時(shí)間Ts約為790 s，數(shù)據(jù)接收總量為2141 603 B，均優(yōu)于其它μ值時(shí)的網(wǎng)絡(luò)性能。因此，取μ=0.6，此時(shí)T1、Ts、數(shù)據(jù)傳輸總量均最大，網(wǎng)絡(luò)整體性能最佳。

4.2 模擬仿真

根據(jù)上面確定的最優(yōu)簇頭數(shù)K=5、P=5%、μ=0.6，以及表1的仿真參數(shù)，采用MATLAB對以上含LEACH算法的5種算法下Sink節(jié)點(diǎn)數(shù)據(jù)接收量、節(jié)點(diǎn)存活時(shí)間、能量消耗3個(gè)方面進(jìn)行仿真［20］，結(jié)果如圖3～圖5及表3所示。

表3 網(wǎng)絡(luò)性能對比表Table 3 Comparison table of network performance

圖3 接收數(shù)據(jù)量仿真結(jié)果曲線圖Fig.3 Simulation result curve of received data volume

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

圖4 存活節(jié)點(diǎn)仿真結(jié)果曲線圖Fig.4 Simulation result curve of living node

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

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

5 總結(jié)

本文在傳統(tǒng)LEACH算法基礎(chǔ)上進(jìn)行了改進(jìn)，綜合考慮了無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)到基站中心區(qū)域的面積約束條件、簇頭節(jié)點(diǎn)密度的優(yōu)化，保證了網(wǎng)絡(luò)簇頭節(jié)點(diǎn)覆蓋面積最大化和密度均勻化。通過對改進(jìn)前后的算法進(jìn)行大量的仿真試驗(yàn)及結(jié)果分析，可以看出改進(jìn)后的LEACH-NEW算法在網(wǎng)絡(luò)節(jié)點(diǎn)存活時(shí)間、能量消耗及發(fā)送數(shù)據(jù)總量的優(yōu)越性，表明該算法是一種有效的分簇算法。