基于網格的動態(tài)能量閾值的簇頭選擇算法*

梁 潘,賀 偉

(1.成都航空職業(yè)技術學院機電工程學院,成都 610100;2.阿壩師范學院物理與電子科學系,四川 汶川 623002)

項目來源:國家自然科學基金項目(61373163)；四川省教育廳重點項目(17ZA0020)

2017-02-28修改日期2017-07-03

基于網格的動態(tài)能量閾值的簇頭選擇算法*

梁 潘1,賀 偉2*

(1.成都航空職業(yè)技術學院機電工程學院,成都 610100;2.阿壩師范學院物理與電子科學系,四川 汶川 623002)

有效地使用傳感節(jié)點的能量進而延長網絡壽命成為設計無線傳感網路由協議的一項挑戰(zhàn)性的工作。而動態(tài)簇被認為提高能量利用率的有效技術之一。然而,簇頭分布不均勻加速了網絡能量的消耗,降低了網絡壽命。為此,提出基于網格的動態(tài)能量閾值的簇頭選擇算法GDET-CH(Grid Dynamic Energy Threshold-based Cluster Header),平衡簇頭分布。GDET-CH算法先將網絡區(qū)域劃分多個網格,并每個網格產生一個簇頭。然后,利用節(jié)點離網格中心距離和節(jié)點剩余能量選擇簇頭。最后,引用動態(tài)能量閾值機制,只有當節(jié)點剩余能量大于能量閾值才可能成為簇頭,進而平衡網絡能耗。實驗數據表明,與DDEEC和EDDDEC算法相比,GDET-CH算法的網絡壽命分別提高了近24.5%和36%。

無線傳感網;簇頭;能量;網格;閾值

無線傳感網絡WSNs(Wireless Sensor Networks)已廣泛應用于各類領域[1-4],如環(huán)境監(jiān)測、健康醫(yī)療、戰(zhàn)場勘察。WSNs通過傳感節(jié)點實時感測環(huán)境數據,實現對應用環(huán)境的監(jiān)測。然而,由于傳感節(jié)點的資源受限,如存儲容量、數據處理能力以及能量受限,尤其是能量受限。此外,WSNs常部署于野外惡劣環(huán)境,給傳感節(jié)點補給能量或更換電池都有巨大挑戰(zhàn)[5-6]。因此,降低節(jié)點能耗,提高節(jié)點的能量使用率,進而延長網絡壽命成為WSNs的研究重點。

為了提高WSNs的可擴展性和能量效率,常采用簇拓撲結構,即將整個網絡虛擬地劃分不同的群(簇),如圖1所示。通過簇結構,平衡能耗,提高網絡連通率[7]。通常,WSNs中的簇頭需完成多項特殊任務,如傳感節(jié)點間的協調、數據融合(基站)、與鄰近簇頭的通信,這加大了簇頭的能耗。因此,如何選擇簇頭成為WSNs研究的熱點。

圖1 基于簇結構的WSNs

常利用節(jié)點剩余能量和距離信息選擇簇頭。典型的有低功耗自適應簇LEACH[8]協議。LEACH協議利用閾值概率選擇簇頭,但它并沒有從平衡能耗角度選擇簇頭,導致某些低能量的節(jié)點誤選為簇頭,這加劇了這類簇頭因能量耗盡而失效的速度,并且它也只適用同構網絡。

針對異構網絡,文獻[9-10]分別提出基于分布式能效簇DEEC(Distributed Energy-Efficient Clustering)算法、DEEC的改進DDEEC(Developed DEEC)算法。DEEC和DDEEC算法均采用二級能量結構,即依據節(jié)點能量將傳感節(jié)點劃分為普通節(jié)點和超級節(jié)點。而文獻[11]提出EDEEC算法,其是采用三級能量結構,將傳感節(jié)點劃分為普通節(jié)點、超級節(jié)點和特超節(jié)點。然而,EDEEC算法并沒有實時依據網絡能量調整簇頭的選擇概率,最終導致某些節(jié)點因能量過早消耗殆盡而失效,節(jié)點一旦失效,就形成覆蓋空洞,這影響了傳感網絡的應用性能

為此,本文提出基于網格的動態(tài)能量閾值的簇頭選擇算法GDET-CH平衡網絡能耗。GDET-CH算法先將網絡劃分為同等大小的網格,在每個網格內產生一個簇頭。然后,計算非簇頭節(jié)點就選擇自己最近的離簇頭加入,進而形成簇。實驗數據表明,提出的GDET-CH算法能夠有效地適用于同構網絡和異構網絡,并提高了網絡壽命。

1 系統模型

考慮n個節(jié)點隨機分布于A×B的感測區(qū)域的多跳傳感網絡。在部署初期,每個傳感節(jié)點具有一定的數據處理和通信能力。假定S為網絡內所有傳感節(jié)點集,如式(1)所示:

S={S1,S2,…,Si}

(1)

式中:Si表示第i個傳感節(jié)點。

同時,將整個網絡劃分為無不重疊唯一的網格ac×bc。假定Q表示網絡內所有網格集,如式(2):

Q={Qj|j=1,2,…,q}

(2)

式中:q表示網絡的網格數。并且每個網格內有pj個節(jié)點數。而在每個網格內的傳感節(jié)點數集可表示為{Si|i=1,2,…,pj}。因此,網絡內的節(jié)點數可表示為:

(3)

此外,假定第j個網格內的傳感節(jié)點集為Qj,其定義如式(4)所示:

(4)

在每個網格內選擇一個節(jié)點作為簇頭,網格內的其他節(jié)點稱為成員節(jié)點,并由簇頭與成員節(jié)點進行協調。簇頭先接收來自成員節(jié)點的數據,然后,再進行數據融合,并轉發(fā)至數據中心。GDET-CH算法從能量角度,有效地選擇簇頭,進而能有效地適應網絡拓撲的動態(tài)變化。

此外,假定nt個數據傳輸節(jié)點所傳輸的數據矢量為x:

x=[x1,x2,…,xnt]T

(5)

數據融合中心的接收信號矢量可表述為y:

y=Hx+n

(6)

式中:y為nr×1維的接收信號矢量。H為瑞利衰落信道矩陣,且尺寸為nr×nt。而n為nr×1維的噪聲矢量,其中n為零均值的加性高斯白噪聲,且方差為σ2。

瑞利衰落信道矩陣H定義如式(7):

(7)

式中:hj,i表示從第i個發(fā)射節(jié)點到數據中心的第j個接收天線的信道協方差系數。

圖2 GDET-CH算法的時間模型

1.1 時間模型

提出的GDET-CH算法將運行時間劃分等間隔輪r(round),并規(guī)定從簇頭產生至數據傳輸至融合中心稱為一輪,如圖2所示。即在每輪內產生簇頭,并傳輸數據。此外,本文引用輪數衡量網絡壽命。網絡經歷的輪數越多,說明網絡運行的時間越長,即網絡壽命越大。

2 GDET-CH 算法

GDET-CH算法主要從距離和能量兩個角度選擇簇頭。先計算節(jié)點離所有網格的距離,并進行排序。然后設置能量閾值。當節(jié)點的剩余能量大于閾值,才有可能作為簇頭候選節(jié)點,再從這些簇頭候選集內選擇離網格最近的節(jié)點作為該網格的簇頭。

2.1 距離因子

(8)

當所有節(jié)點部署后,它們就計算離他們各自的網格中心的距離,其定義如式(9)所示:

d1=Γ(cx,cy,sx,sy)

(9)

據此,可定義矩陣Q,其定義如式(10)所示:

(10)

矩陣Q內的第1行表示每個網格內所有的節(jié)點數。盡管每個網格內所擁有的節(jié)點數不同,但仍用矩陣Q表示。利用S(j,i)的值,表示此位置是否存在一個節(jié)點。此值為1,表示存在傳感節(jié)點,-1表示不存在傳感節(jié)點。

接下來,定義q×p維的矩陣D1,其表示所有節(jié)點到每個網格中心的距離,如式(11)所示:

(11)

從式(11)可知,矩陣D1的第1行表示傳感節(jié)點所有節(jié)點至第1個網格中心的距離。為此,利用d1(k)表示所有節(jié)點至第kth個網格中心的距離,即d1(k)={d1(k,1),d1(k,2),…,d1(k,p)},且k=1,2,…,q。

ξk=min[abs(d1(k))]

(12)

2.2 動態(tài)能量閾值

GDET-CH算法在選擇簇頭時,充分考慮了節(jié)點剩余能量。當節(jié)點剩余能量Ere大于預定Eth值,才可能成為簇頭。將Eth稱為能量閾值。

而如何設定閾值Eth對簇頭選擇起到關鍵作用。傳統的簇頭選擇算法常引用固定閾值,這不利用網絡能耗的平衡。具體而言,最初節(jié)點能量較高,可以設置較大的閾值,但隨著網絡的運行,節(jié)點能量下降,這時需要降低閾值。為此,采用自適應的閾值機制。

首先,引用ψ={ψ1,ψ2,…,ψm}表示節(jié)點能量的范圍,且ψ∈[0,1]。隨著,網絡的運行,節(jié)點能量肯定逐步下降。換而言之,最初,閾值Eth可以較高,因為多數節(jié)點的能量較為充足。但是,經過一段時間后,節(jié)點能量肯定下降,如果節(jié)點閾值Eth過高,或者不隨進行改變,那多數節(jié)點的能量肯定低于閾值Eth。

(13)

2.3 簇頭產生過程

簇頭產生過程的偽代碼如圖3所示。先將矩陣D1、P1和Qs初始化,并將矢量d1、p1也初始化。其中Qs為節(jié)點狀態(tài)矩陣,維數為q×p。如果節(jié)點為簇頭,則其元素值就為1,否則就為零,即節(jié)點為普通節(jié)點。

然后,從第1個網格開始,再依據式(9),每個節(jié)點計算離此網格中心的距離,即形成d1(1),再進行排序。然后再從第2個網格開始,重復上述過程,直至所有傳感網絡均計算了離各自網格中心的距離。

圖3 產生簇頭算法的偽代碼

2.4 簇形成過程

產生簇頭后,就形成簇頭集Qch,其定義如式(14)所示:

(14)

非簇頭節(jié)點(普通節(jié)點)需要加入至一個簇,加入的原則就是,選擇離自己最近的簇。為此,定義n×q維的矩陣D2,其表示所有普通節(jié)點離q個簇頭的距離,如式(15)所示:

(15)

而d2表示普通節(jié)點離簇頭的距離,可由式(8)計算,如式(16)所示:

(16)

引用d2(i)表示矩陣D2的第i行,其元素值等于普通節(jié)點(第i個普通節(jié)點)至離q個簇頭的距離。該普通節(jié)點就選擇離自己最近的簇頭加入,即min{d2(i)}。簇形成算法的偽代碼如圖4所示。

圖4 簇形成過程的偽代碼

3 性能仿真

3.1 仿真參數及性能指標

為了更好地評估GDET-CH算法性能,通過MATLAB軟件建立仿真平臺。選擇100 m×100 m的感測區(qū)域,且傳感節(jié)點數為100。每個節(jié)點的初始能量E0=1 J。假定融合中心位于100 m×100 m區(qū)域的中心。

此外,為了更好地考查傳感節(jié)點的同構或異構性對GDET-CH算法的性能影響,建立兩個實驗:同構網絡實驗;異構網絡實驗。本文所指的同構網絡是指網絡內所有節(jié)點的初始相同,而異構網絡是指節(jié)點能量初始不相同。

3.2 同構網絡實驗

為了更好地分析GDET-CH算法性能,選擇同類動態(tài)簇算法LEACH作為參照。假定所有傳感節(jié)點是同構的,并且由簇頭負責將數據轉發(fā)至融合中心。

圖5 同構網絡壽命

圖5顯示了GDET-CH和LEACH算法的活動節(jié)點數NA隨輪數的變化情況。從圖5可知,GDET-CH算法的第1個失效節(jié)點FND(First Node Died)發(fā)生在1 370輪,而LEACH算法的FND發(fā)生于903輪。此外,當LEACH算法運行至1 198輪時,就有一半的節(jié)點失效HND(Half Nodes Died),而GDET-CH算法直到2 334輪才出現這種情況。觀察圖5可發(fā)現,GDET-CH算法的最后一個失效節(jié)點LND(Last Node Died)發(fā)生于3 415輪,而LEACH算法在1 862輪就出現這種情況。從這些數據可知,GDET-CH算法分別通過100%、50%、1%的活動節(jié)點提高的51%、94%、83%的網絡壽命。這里的網絡壽命是通過輪數表征。運行的輪數越多,網絡壽命也就越長。

3.3 異構網絡實驗

本次實驗是基于異構網絡,并且考慮二級、三級的異構網絡。在二級異構網絡中,通過節(jié)點的初始能量的不同,將網絡內傳感節(jié)點劃分為普通節(jié)點、超級節(jié)點。且普通節(jié)點數為n×(1-m)、超級節(jié)點數為n×m。

而在三級異構網絡中,將傳感節(jié)點劃分為普通節(jié)點、超級節(jié)點和特超節(jié)點,它們的節(jié)點數分別為n×(1-m)、n×m×(1-m0)和n×m×m0。其中n=100、m、m0分別設置為0.3。而超級節(jié)點和特超節(jié)點的初始能量分別為(1+α)E0、(1+b)E0,其中a、b分別為2、3.5。

圖6顯示了GDET-CH算法和DDEEC和DEEC在二級異構網絡內的活動節(jié)點數。從圖6可知,GDET-CH算法的FND、HND和LND分別發(fā)生于2 151、2 777和4 351輪。而DEEC和DDEEC算法的FND分別發(fā)生于936和2 013輪,而HND分別發(fā)生于2 145和2 232輪,LND發(fā)生于3 531和3 770輪。因此,相比于DEEC和DDEEC,GDET-CH算法的網絡壽命提高了近23.2%和15.4%。

圖6 異構網絡壽命(二級)

圖7 異構網絡壽命(三級能量)

圖7顯示了三級異構網絡的實驗數據,也選擇同類的EDEEC和EDDEEC[12]與GDET-CH算法進行參照。從圖7可知,GDET-CH算法的FND、HND和LND分別發(fā)生于2 158、3 391和4 635輪,而EDEEC和EDDEEC的FND分別發(fā)生于2 401輪和2 492輪。相應地,LND發(fā)生于4 157和4 520輪。這些數據表明,在三級異構網絡中,GDET-CH算法的網絡壽命比EDEEC和EDDEEC分別提高了11.25%和2.6%。

4 總結

本文針對無線傳感網絡的簇頭選擇問題,提出了基于網格的動態(tài)能量閾值的簇頭選擇算法GDET-CH。GDET-CH算法充分考慮了簇頭分布的均勻性對網絡壽命的影響。在選擇簇頭時,融合了距離和節(jié)點剩余能量信息,并且考慮了動態(tài)的能量閾值,而不是單一的能量閾值。實驗數據表明,提出的GDET-CH算法能夠有效地提高網絡壽命。

[1] Muruganathan S D,Ma D C,Bhasin R I. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks[J]. IEEE Radio Communications,2011,43(3):8-13.

[2] 歸奕紅. 無線傳感器網絡HEDSA數據聚合研究[J]. 計算機工程,2011,37(7):160-164.

[3] 沈艷霞,薛小松. 無線傳感網絡移動信標節(jié)點路徑優(yōu)化策略[J]. 傳感器與微系統,2012,31(12):42-46.

[4] Tyagi S,Kumar N. A Systematic Review on Clustering and Routing Techniques Based Upon LEACH Protocol for Wireless Sensor Networks[J]. Journal of Network and Computer Applications,2013,36(2):623-645.

[5] 陳東海,李長庚. 基于簇頭功能分化的無線傳感器網絡成簇算法[J]. 傳感技術學報,2015,28(2):244-248.

[6] 門順治,孫順遠,徐保國. 基于PSO的非均勻分簇雙簇頭路由算法[J]. 傳感技術學報,2014,27(9):1281-1286.

[7] Chidean M I,Morgado E,del Arco E,et al. Scalable Data-Coupled Clustering for Large Scale WSN[J]. IEEE Transactions on Wireless Communications,2015,14(9):4681-4694.

[8] Yan J F,Liu Y L. Improved LEACH Routing Protocol for Large Scale Wireless Sensor Networks Routing[C]//In International Conference on Electronics,Communications and Control. Ningbo,China,September,2011:35-42.

[9] Qing L,Zhu Q,Wang M. Design of a Distributed Energy-Efficient Clustering Algorithm for Heterogeneous Wireless Sensor Network[J]. ELSEVIER,Comput. Commun,2006,29:2230-2237.

[10] Elbhiri B,Saadane R,El-Fkihi S,et al. Developed Distributed Energy-Efficient Clustering(DDEEC)for Heterogeneous Wireless Sensor Networks[C]//In 5th International Symposium on I/V Communications and Mobile Network,2010:32-42.

[11] Saini A P,Sharma K. Distributed and Grid Computing(PDGC-2010). E-DEEC-Enhanced Distributed Energy Efficient Clustering Scheme for Heterogeneous WSN[C]//In 2010 1st International Conference on Parallel,2011:3-9.

[12] Javaid N,Qureshi T,Khan A,et al. EDDEEC:Enhanced Developed Distributed Energy-Efficient Clustering for Heterogeneous Wireless Sensor Networks[J]. Procedia Computer Science,2013,19(2):914-919.

GridDynamicEnergyThreshold-BasedClusterHeaderAlgorithminWirelessSensorNetwork*

LIANGPan1,HEWei2*

(1.Department of Electro-Mechanic Engineering,Cheng Du Aeronautic Polytechnic,Chengdu 610100,China; 2.Department of Electronic Information,ABA Teahers University,Wenchuan Sichuan 423002,China)

Using the energy of sensor nodes efficiently to prolong the network lifetime is a chief challenge for designing routing protocols. Dynamic clustering is generally considered as one of the energy conservation techniques,but unbalanced distribution of cluster heads in clusters tend to drain out the network energy quickly resulting premature decrease in network lifetime. Grid dynamic energy threshold-based Cluster header(GDET-CH)algorithm is proposed in this paper,which balanced the distribution of cluster heads. In GDET-CH,Firstly,the whole network is divided into non-overlapping uniform grids,and each grid has a cluster head. Then,Distance from the center of grid and residual energy of node are both considered into selecting cluster head. Finally,GDET-CH introduces the dynamic energy threshold to balance the energy consumption,Only residual energy is more than threshold,the node may to be a cluster head. From simulation results,it is observed that the proposed clustering scheme enhances network lifetime by 24.5% and 36% as compared to existing schemes e.g. DDEEC and EDDEEC respectively.

wireless sensor network;cluster header;energy;grid;threshold

TPT393

A

1004-1699(2017)10-1583-06

10.3969/j.issn.1004-1699.2017.10.022

ξk表示離第kth個網格中心的距離最小的節(jié)點信息,其定義如式(12)所示:

梁潘(1978-),男,四川廣漢人,副教授,碩士,研究方向為人工智能與網絡安全;

賀偉(1980-),男,四川郫縣人,副教授,碩士,研究方向為人工智能與網絡安全。