多級能量異構(gòu)自適應(yīng)傳感器網(wǎng)絡(luò)成簇算法*

關(guān)志艷

(山西大學(xué)商務(wù)學(xué)院 信息學(xué)院，山西 太原 030031)

多級能量異構(gòu)自適應(yīng)傳感器網(wǎng)絡(luò)成簇算法*

關(guān)志艷

(山西大學(xué)商務(wù)學(xué)院 信息學(xué)院，山西 太原 030031)

在經(jīng)典LEACH算法的基礎(chǔ)上，綜合考慮簇首選擇概率、節(jié)點(diǎn)剩余能量及與基站距離等因素，本文提出了多級能量異構(gòu)自適應(yīng)傳感網(wǎng)絡(luò)成簇算法，對簇首選擇閾值進(jìn)行改進(jìn)，將高能量近距離的節(jié)點(diǎn)優(yōu)先選為簇首。在簇首將數(shù)據(jù)傳輸?shù)交镜倪^程中，考慮中繼簇首的選擇，從而減少路由中繼次數(shù)，最大限度節(jié)約能耗。仿真實驗表明，本文算法在異構(gòu)能量網(wǎng)絡(luò)環(huán)境下有更長的網(wǎng)絡(luò)穩(wěn)定期。

能量異構(gòu)；簇首；剩余能量

無線傳感器網(wǎng)絡(luò)是物聯(lián)網(wǎng)的重要分支，在地形復(fù)雜區(qū)域往往不能人為部署節(jié)點(diǎn)，需要利用直升機(jī)等設(shè)備隨機(jī)部署在監(jiān)測區(qū)域內(nèi)，此時能耗與通信就顯得尤為突出。在網(wǎng)絡(luò)運(yùn)行過程中各節(jié)點(diǎn)能量出現(xiàn)異構(gòu)，將不同能量級別的節(jié)點(diǎn)組織簇，將剩余能量高的節(jié)點(diǎn)選為簇首，負(fù)責(zé)收集、融合、壓縮及發(fā)送來自簇成員節(jié)點(diǎn)采集的信息。

經(jīng)典LEACH[1]是每個節(jié)點(diǎn)等概率隨機(jī)產(chǎn)生于[0,1]，選擇小于閾值的節(jié)點(diǎn)為簇首，廣播簇首信息，每個節(jié)點(diǎn)據(jù)收到信號強(qiáng)弱來判斷距離遠(yuǎn)近是否適合加入簇，該協(xié)議主要應(yīng)用于同構(gòu)。Younis[2]提出HEED協(xié)議，設(shè)定主次參數(shù)，主參數(shù)依賴于迭代過程是否比周圍節(jié)點(diǎn)收斂快，次參數(shù)依賴于簇內(nèi)通信代價，以平衡簇首間負(fù)載。

鄧亞平[3]提出了多級能量異構(gòu)傳感器網(wǎng)絡(luò)能量有效的路由算法，其針對TDEEC、SEP算法的平均網(wǎng)絡(luò)能量進(jìn)行改進(jìn)，保證相對剩余能量較高的節(jié)點(diǎn)更有可能成為簇首，簇間采用多跳路由協(xié)議。劉唐[4]提出了基于相對距離的多級能量傳感網(wǎng)絡(luò)成簇算法，考慮到節(jié)點(diǎn)與基站的距離，節(jié)點(diǎn)等概率輪流成為簇首。張穎[5]提出了一種基于能量與距離的多級能量異構(gòu)傳感網(wǎng)絡(luò)路由算法，其針對CDEE簇首選擇機(jī)制進(jìn)行改進(jìn)，在簇首間形成一個多跳路由路徑通向基站，但實現(xiàn)較難，無形中增加了網(wǎng)絡(luò)計算能耗。

本研究綜合考慮簇首選擇概率、節(jié)點(diǎn)剩余能量及與基站距離三個因素，對簇首選擇閾值進(jìn)行改進(jìn)，提出了多級能量異構(gòu)自適應(yīng)傳感網(wǎng)絡(luò)成簇算法，在簇首將數(shù)據(jù)傳輸?shù)交镜倪^程中，設(shè)定通信閾值以選擇中繼簇首。仿真實驗表明，本算法可以延長節(jié)點(diǎn)死亡時間，有效節(jié)約能量。

1 系統(tǒng)模型

1.1 同構(gòu)能量網(wǎng)絡(luò)成簇模型

在M×M的矩形監(jiān)測區(qū)域內(nèi)隨機(jī)分布N個節(jié)點(diǎn)，所有節(jié)點(diǎn)初始能量相同，并在其中選出Kopt個簇首節(jié)點(diǎn)，Popt為優(yōu)化簇首比例，簇首對本簇成員節(jié)點(diǎn)感知的數(shù)據(jù)信息進(jìn)行收集并融合，再傳輸給基站。所有節(jié)點(diǎn)不具備移動性，節(jié)點(diǎn)依據(jù)接受信號強(qiáng)弱來判斷與簇首距離，以確定是否加入該簇。

1.2 多級能量異構(gòu)網(wǎng)絡(luò)成簇模型

在上述同構(gòu)能量網(wǎng)絡(luò)模型的基礎(chǔ)上，所有節(jié)點(diǎn)初始能量不再是相同的，而是隨機(jī)分布于[E0,E0(1+ai)]內(nèi)，ai是比E0多出的能量倍數(shù)。節(jié)點(diǎn)能量消耗主要考慮無線收發(fā)通信消耗，據(jù)收發(fā)節(jié)點(diǎn)間距離的不同，可采用自由空間模型和多路衰減模型。當(dāng)發(fā)送端將1 bit數(shù)據(jù)傳輸?shù)骄嚯x為d的接收端時，發(fā)送能耗為式(1)，接受能耗為式(2)，數(shù)據(jù)融合能耗為式(3)。

圖1 100個節(jié)點(diǎn)隨機(jī)分布

圖2 LEACH 形成的分簇

(1)

ER(L,d)=L·Eelec.

(2)

EF(L)=L·EDA.

(3)

σ∈[1,6]為距離能量梯度系數(shù)，由物理環(huán)境而定，λ∈[1,2]為常數(shù)。

2 算法設(shè)計

2.1 簇首選擇

在網(wǎng)絡(luò)運(yùn)行過程中，將時間分成許多間隙，稱為輪。每輪節(jié)點(diǎn)是否成為簇首主要受節(jié)點(diǎn)與基站的距離、節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)選擇成簇概率三方面決定。節(jié)點(diǎn)的選擇成簇概率決定了優(yōu)化簇首比例，文獻(xiàn)[5]詳細(xì)闡述了簇首個數(shù)的計算。

(6)

同時考慮到簇首要將收集到的信息融合發(fā)送給基站，式(1)(2)可知，離基站越近成為簇首的可能性越大，節(jié)點(diǎn)i按距離基站遠(yuǎn)近成為簇首的加權(quán)概率為：

(7)

經(jīng)過每輪的選擇、廣播通信等能耗，下一輪簇首應(yīng)選擇剩余能量更多的節(jié)點(diǎn)，假設(shè)Ei(r)為節(jié)點(diǎn)i第r輪的剩余能量，Ei(r)=Ei(r-1)-ET(L,d)-ER(L,d)-EF(L)，Eave(r)為第r輪所有節(jié)點(diǎn)剩余能量平均值，在式(6)(7)的基礎(chǔ)上，節(jié)點(diǎn)i再按初始能量不同、距離基站遠(yuǎn)近、剩余能量多少三方面影響成為簇首的加權(quán)概率為：

(8)

依據(jù)LEACH協(xié)議，每個節(jié)點(diǎn)在簇首選擇過程中，產(chǎn)生[0,1]隨機(jī)數(shù)，小于閾值選擇為簇首，為了使具有更多剩余能量且離基站更近的節(jié)點(diǎn)成為簇首，閾值設(shè)計為：

(9)

其中:r為選擇簇首輪數(shù)，G為本輪還未當(dāng)簇首的節(jié)點(diǎn)集合，η1為對應(yīng)的能量調(diào)節(jié)因子，η2為距離調(diào)節(jié)因子，η1+η2=1 且η1≥0,η2≥0。

2.2 數(shù)據(jù)傳輸

簇首收集簇成員信息，并采用單跳或多跳相結(jié)合的傳輸形式。在多跳傳輸時，假設(shè)中繼簇首只是轉(zhuǎn)發(fā)其他簇首數(shù)據(jù)，不進(jìn)行簇首間數(shù)據(jù)融合，則將數(shù)據(jù)發(fā)送到基站的關(guān)鍵因素在于中繼路由次數(shù)。為了選取合適的中繼簇首，設(shè)定距離閾值dth，若di-BS(r)>dth，則需尋求中繼簇首。

構(gòu)建路由表時，需要尋求中繼簇首的簇首，向所有簇首廣播信息(包括剩余能量和基站距離)，其余簇首據(jù)接收信號強(qiáng)度估算與該簇首的相對距離，據(jù)文獻(xiàn)[6]，符合式(10)的簇首可作為中繼簇首。

(10)

2.3 算法流程

多級能量異構(gòu)自適應(yīng)傳感網(wǎng)絡(luò)成簇算法按輪進(jìn)行，流程如圖3所示，在簇首選擇階段，會根據(jù)節(jié)點(diǎn)與基站的距離、節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)選擇成簇概率來確定節(jié)點(diǎn)成為簇首的閾值，再進(jìn)行簇首間數(shù)據(jù)傳輸。

3 仿真結(jié)果及性能分析

3.1 仿真環(huán)境

將本文所提算法與經(jīng)典LEACH算法和異構(gòu)SEP算法進(jìn)行對比，主要從網(wǎng)絡(luò)穩(wěn)定期和網(wǎng)絡(luò)能量消耗量方面來測試該算法的節(jié)能有效性。在100×100的監(jiān)測區(qū)域，隨機(jī)分布100個節(jié)點(diǎn)，基站在監(jiān)測區(qū)域外位置為(50,150)，所有節(jié)點(diǎn)與基站位置固定不具備移動性，初始能量分布于1～3J,算法所需實驗參數(shù)在介紹各個公式時已說明，簇首傳輸數(shù)據(jù)量為4 000 bit,可計算出優(yōu)化簇首個數(shù)，Kopt=9、η1、η2取值參考文獻(xiàn)[6],當(dāng)(η1,η2)為(0.5,0.5)時，節(jié)點(diǎn)的第一個死亡時間最晚，可最大限度延緩所有節(jié)點(diǎn)的整體死亡時間，從而有效均衡負(fù)載。LEACH算法、SEP算法與本算法相同參數(shù)上取值相同，在數(shù)據(jù)傳輸階段，假設(shè)數(shù)據(jù)在傳輸過程中無丟失，并忽略信道干擾等隨機(jī)因素。

圖3 算法流程圖

3.2 結(jié)果與分析

初始能量倍數(shù)ai對網(wǎng)絡(luò)的穩(wěn)定期影響如圖4所示，從LEACH、SEP算法來看，隨著ai的增長，并沒有出現(xiàn)增長網(wǎng)絡(luò)穩(wěn)定期的效果，整體趨向呈現(xiàn)隨著ai增長，縮短網(wǎng)絡(luò)穩(wěn)定期的現(xiàn)象。但本文算法隨著ai增長，節(jié)點(diǎn)死亡時間延遲，有效延長網(wǎng)絡(luò)穩(wěn)定期，下面的實驗結(jié)果是以ai=2作為能量倍數(shù)。

圖4 隨ai變化的網(wǎng)絡(luò)穩(wěn)定期

網(wǎng)絡(luò)能耗主要是在節(jié)點(diǎn)的數(shù)據(jù)傳輸、廣播、融合等方面。從圖5中可以看出，LEACH算法能耗高于SEP算法和本文算法，本算法在前期能耗較低，但是到了后期能耗較大，這是因為SEP算法和LEACH算法在前期的死亡節(jié)點(diǎn)多，到了后期存活節(jié)點(diǎn)數(shù)量少，而本算法后期存活節(jié)點(diǎn)較多，消耗相對來說就高些。

圖5 網(wǎng)絡(luò)能耗

4 結(jié)束語

本文在LEACH算法和SEP算法的基礎(chǔ)上，對簇首選擇的閾值進(jìn)行了改進(jìn)，充分考慮了節(jié)點(diǎn)的剩余能量和基站距離的因素。在數(shù)據(jù)傳輸方面，當(dāng)簇首與基站距離大于通信閾值時，需尋求中繼簇首，從而整體上延長網(wǎng)絡(luò)穩(wěn)定期。仿真結(jié)果表明，本文算法可以有效均衡網(wǎng)絡(luò)負(fù)載。

[1] Heinzelman W R,Chandralcasan A, Balalcrishnan

H.Energy-efficient Communication Protocol for Wireless Sensor Networks[C].Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Washigton,DC:IEEEComputer Society,2000,2:1-10.

[2] Younis O,Fahmy S,HEED: A Hybrid,Enengy-Efficient,Distributed Clustering Approach fo Ad Hoc Sensor Networks[J].IEEE Fras on Mobile computing,2004,3(4):660-669.

[3] 鄧亞平,藺換換.多級能量異構(gòu)傳感器網(wǎng)絡(luò)能量有效的路由算法[J].計算機(jī)應(yīng)用,2011,31(1):4-7.

[4] 劉唐,汪小芬.楊進(jìn).基于相對距離的多級能量傳感網(wǎng)絡(luò)成簇算法[J].計算機(jī)科學(xué),2012,39(8):119-203.

[5] 張穎,季常剛.李俊甫.一種基于能量與距離的多級能量異構(gòu)傳感網(wǎng)絡(luò)路由算法[J].上海交通大學(xué),2014,48(7):953-958.

[6] 吳保強(qiáng),張霓,鄒濤,等.多級異構(gòu)傳感器網(wǎng)絡(luò)距離和能量有效分簇算法[J].機(jī)電工程,2010,27(7):57-60.

A Clustering Algorithm for Multilevel Energy Heterogeneous Self-adaption Sensor Networks

Guan Zhiyan

(InformationInstitute,BusinessCollegeofShanxiUniversity,TaiyuanShanxi030001,China)

Based on the classical LEACH algorithm，considering the cluster head selection probability, the node residual energy and distance of base station ,this paper proposes a clustering algorithm for multilevel energy heterogeneous self-adaption sensor networks which improves the cluster head selection threshold, and the high energy and close distance nodes is selected as cluster head preferentially. In the process of data transmitting to the base station, the relay cluster head is selected so as to reduce the number of routing relays and save the energy. Simulation results show that the algorithm is more stable in the heterogeneous network environment.

energy heterogeneous; cluster head; residual energy

2017-03-31

山西大學(xué)商務(wù)學(xué)院教學(xué)改革基金項目(2015012)； 2016教育部人文社會科學(xué)研究規(guī)劃基金項目(16YJAZH040)；山西省“十三五”高等院校規(guī)劃課題(GH—16182)

關(guān)志艷(1983- )，女，山西太原人，講師，碩士研究生，研究方向為無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋研究。

1674- 4578(2017)03- 0051- 04

TP301.6

A