無線傳感器網(wǎng)絡(luò)分簇拓?fù)淇刂扑惴?

龍昭華， 陳丹丹， 蔣貴全

(重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065)

0 引 言

1 HEED與EEUC拓?fù)淇刂扑惴?/h2>

HEED[5](hybrid energy-efficient distributed)算法是一種使用固定簇半徑的分簇協(xié)議[6]，該協(xié)議中給出了無線傳感器網(wǎng)絡(luò)中的3個(gè)最重要的需求：延長(zhǎng)生命周期、可擴(kuò)展性和負(fù)載均衡，并通過將能量消耗均勻分布到整個(gè)網(wǎng)絡(luò)中來達(dá)到延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。HEED協(xié)議中簇首選舉主要依據(jù)主、次2個(gè)參數(shù)。主參數(shù)依賴于剩余能量，用于隨機(jī)選取初始簇首節(jié)點(diǎn)集合，擁有較多剩余能量的節(jié)點(diǎn)將有較大的概率暫時(shí)成為簇首節(jié)點(diǎn)，而最終該節(jié)點(diǎn)能否成為簇首取決于剩余能量是否比周期內(nèi)其他節(jié)點(diǎn)的能量多，即迭代過程是否比周圍節(jié)點(diǎn)收斂的快。次參數(shù)依賴于簇內(nèi)通信代價(jià)，用來確定落在多個(gè)簇范圍內(nèi)的節(jié)點(diǎn)最終選擇哪個(gè)簇首加入，以及平衡簇首之間的負(fù)載[7]。

EEUC[8]算法是一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議，它采用多跳通信方式防止離基站遠(yuǎn)的簇首節(jié)點(diǎn)過早死亡，并且以主動(dòng)方式均衡節(jié)點(diǎn)能耗[9]，該協(xié)議會(huì)預(yù)先設(shè)置一個(gè)是否成為候選簇首的閾值T，普通節(jié)點(diǎn)根據(jù)此閾值決定自身是否成為候選簇首。未參與競(jìng)選的節(jié)點(diǎn)則進(jìn)入休眠模式，直到簇首競(jìng)選過程結(jié)束。令Si為任意的一個(gè)候選簇首節(jié)點(diǎn)，Si根據(jù)自身到基站的距離信息來計(jì)算其自身競(jìng)爭(zhēng)區(qū)域的大小，區(qū)域半徑記為Ri。候選簇首節(jié)點(diǎn)之間按照規(guī)則1進(jìn)行競(jìng)爭(zhēng)簇首。

規(guī)則1：在競(jìng)選簇首節(jié)點(diǎn)過程中，如果候選簇首Si宣告其競(jìng)選成功，那么，在其競(jìng)爭(zhēng)半徑Ri之內(nèi)的所有候選簇首節(jié)點(diǎn)需退出競(jìng)選過程。

2 雙簇首能量均衡算法

通過對(duì)經(jīng)典的分簇算法進(jìn)行研究與分析，盡量避免其不足之處，提出了一種基于雙簇首能量均衡(DCHEB)的無線傳感器網(wǎng)絡(luò)分簇拓?fù)淇刂扑惴?，本算法引進(jìn)了雙簇首的思想，每個(gè)簇有主簇首節(jié)點(diǎn)(MCH)和副簇首節(jié)點(diǎn)(VCH)。主簇首負(fù)責(zé)簇內(nèi)的數(shù)據(jù)采集，副簇首節(jié)點(diǎn)負(fù)責(zé)簇間的數(shù)據(jù)傳輸。這樣一來就使得原來單個(gè)簇首節(jié)點(diǎn)的簇內(nèi)數(shù)據(jù)采集和簇間數(shù)據(jù)傳輸?shù)?個(gè)任務(wù)分給現(xiàn)在的主副簇首節(jié)點(diǎn)去完成，這大大降低了簇首的能量消耗，可以達(dá)到延緩簇的重組的目的。

2.1 基本思想

1)在網(wǎng)絡(luò)初始化的時(shí)候建立一個(gè)圓形的網(wǎng)絡(luò)，基站位于其中心[10]；然后以基站為中心按照本文算法提供的方案進(jìn)行層次的劃分并計(jì)算出每層的簇的個(gè)數(shù)和層間距，傳感器節(jié)點(diǎn)均勻地分布在整個(gè)網(wǎng)絡(luò)中，節(jié)點(diǎn)根據(jù)自身的坐標(biāo)、剩余能量以及所在的層次來確定該層的主副簇首節(jié)點(diǎn)。這樣可以確保每個(gè)簇的節(jié)點(diǎn)個(gè)數(shù)相對(duì)平均，主簇首節(jié)點(diǎn)位于合適的位置上，從而可以在一定程度上均衡簇內(nèi)和簇間的能量消耗，進(jìn)而可以延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期。

2) 進(jìn)行主副簇首節(jié)點(diǎn)選舉時(shí)，首先基站廣播簇首選擇消息，各節(jié)點(diǎn)會(huì)把自身的相關(guān)信息(坐標(biāo)、剩余能量)發(fā)送給基站，基站根據(jù)節(jié)點(diǎn)的信息和已劃分好的層次通過集中式的策略來進(jìn)行主副簇首節(jié)點(diǎn)的選舉[11]。通過這種方式可以使主簇首節(jié)點(diǎn)位于較為合適的位置上，從而達(dá)到簇內(nèi)的各節(jié)點(diǎn)的能量消耗相對(duì)均衡。

2.2 DCHEB算法通信模型簡(jiǎn)介

設(shè)r為傳感器節(jié)點(diǎn)單跳通信的最大距離，本文采用的通信模型分2種情況：當(dāng)傳輸距離小于r時(shí)，發(fā)送節(jié)點(diǎn)的能耗與傳輸距離的平方呈正比；大于r時(shí)，則與傳輸距離的四次方呈正比。這2種情況分別為：自由空間傳輸模型和多路衰減模型。所以，根據(jù)傳輸距離的大小，發(fā)送節(jié)點(diǎn)傳輸kbit的信息所消耗的發(fā)送能量如式(1)[12]所示，接收kbit的信息所消耗的能量由式(2)所示

由表2可以看出，該數(shù)據(jù)為平衡面板數(shù)據(jù)，截面數(shù)為31，跨期為11，屬于短面板。被解釋變量中，人均教育支出均等化指數(shù)均值為0.972，人均醫(yī)療衛(wèi)生和人均社會(huì)保障與就業(yè)均等化指數(shù)均值都為0.999，接近于1，說明教育、醫(yī)療衛(wèi)生和社會(huì)保障與就業(yè)基本公共服務(wù)均等化供給程度相對(duì)較高。

(1)

ERx(k)=Eelec·k,

(2)

式中Eelec為射頻電路和接收電路每發(fā)送或接收單位數(shù)據(jù)所消耗的能量，J/bit；εfs為自由空間傳輸參數(shù)，εamp為多路衰減傳輸參數(shù)，它們的單位是J/(bit·m2)。

r為一個(gè)門限距離，亦即接收電路和發(fā)送電路之間距離的臨界值，當(dāng)兩者間的距離小于r時(shí)，使用自由空間模型；當(dāng)兩者間的距離大于r時(shí)，使用多路徑衰減模型。本文的通信模型將統(tǒng)一采用自由空間模型，假定每個(gè)簇首的節(jié)點(diǎn)通信范圍都能包含所劃分好的簇，使得網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都至少有一個(gè)簇加入。

2.3 簇的劃分方案

本文提出了一種新的簇的劃分方案，此方案有利于使得主副簇首節(jié)點(diǎn)位于合適的位置，而且使得每個(gè)簇的節(jié)點(diǎn)個(gè)數(shù)相對(duì)平均，這樣會(huì)使得簇間和簇內(nèi)的節(jié)點(diǎn)的能量消耗相對(duì)均勻和延長(zhǎng)邊緣節(jié)點(diǎn)的死亡時(shí)間，可以有助于延長(zhǎng)網(wǎng)絡(luò)的生存周期。

1)算出網(wǎng)絡(luò)中的最佳簇首個(gè)數(shù)，計(jì)算公式如下

(3)

2)將網(wǎng)絡(luò)區(qū)域平均分為K個(gè)簇域，簇域采用扇形區(qū)域，第n層簇的個(gè)數(shù)設(shè)為Pn，如圖1所示，可以得到下面等式

(4)

圖1 層間距Rn與層簇?cái)?shù)Pn示意圖

式中S為傳感器網(wǎng)絡(luò)區(qū)域面積；K為最優(yōu)簇首數(shù)目；Pn為第n層簇的數(shù)目；Ri為第i層的間距。

綜上,可以得出Rn的解為

(5)

2.4 主副簇首的選舉

在對(duì)簇首節(jié)點(diǎn)選舉策略的選擇時(shí)，則應(yīng)考慮以下幾個(gè)方面：

1)簇首選舉策略應(yīng)該盡量采取分布式的方案[13],網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)都可以根據(jù)本地地信息進(jìn)行自主選擇簇首節(jié)點(diǎn)，并且簇首節(jié)點(diǎn)的選舉算法應(yīng)該盡量簡(jiǎn)單，以節(jié)約能量消耗。

2)盡量使被選擇擔(dān)當(dāng)簇首的節(jié)點(diǎn)均勻地分布在整個(gè)網(wǎng)絡(luò)中，并且可以監(jiān)測(cè)整個(gè)網(wǎng)絡(luò)的運(yùn)行情況。

3)網(wǎng)絡(luò)中被選舉出擔(dān)當(dāng)簇首的節(jié)點(diǎn)數(shù)目應(yīng)該盡可能接近于最佳簇首個(gè)數(shù)。

4)簇首選舉過程中應(yīng)使能量消耗盡可能的少。

主副簇首選舉的流程如圖2所示。

圖2 主副簇首節(jié)點(diǎn)選舉流程圖

通過此階段的選舉，可以確保被選舉成為簇首節(jié)點(diǎn)的節(jié)點(diǎn)比較均勻地分布在整個(gè)網(wǎng)絡(luò)中，并且能夠監(jiān)測(cè)整個(gè)網(wǎng)絡(luò)的運(yùn)行情況。在此階段之后，被選舉出的主簇首節(jié)點(diǎn)會(huì)發(fā)送廣播消息來組建自己的簇。簇一旦建立完成后，這種簇結(jié)構(gòu)就不會(huì)再發(fā)生改變。當(dāng)簇首發(fā)生異常，不再適合繼續(xù)擔(dān)當(dāng)簇首節(jié)點(diǎn)時(shí)(包括主、副簇首節(jié)點(diǎn))，不需要再通過基站在全網(wǎng)中進(jìn)行選舉了，而是在自己所在簇的周圍(也包括簇內(nèi))，即在小范圍內(nèi)按照一定的方式選舉出新任的簇首節(jié)點(diǎn)，亦即網(wǎng)絡(luò)運(yùn)行階段中的簇首選舉[14]。

3 仿 真

本文設(shè)置的仿真環(huán)境：以基站為中心，坐標(biāo)為原點(diǎn)(0，0)m，把300個(gè)傳感器節(jié)點(diǎn)均勻分布到半徑為200 m的圓形感知區(qū)域的4個(gè)象限中。

在上面仿真環(huán)境中全部的普通節(jié)點(diǎn)負(fù)責(zé)收集信息，并且按照固定的周期進(jìn)行數(shù)據(jù)傳輸，每個(gè)數(shù)據(jù)包均設(shè)置為2 000 bit，全部節(jié)點(diǎn)的原始能量都設(shè)置為0.5 J。其他參數(shù)設(shè)置為εelec=50 nJ/bit，εfs=10 pJ/bit/m2，εmp=0.001 3 pJ/bit/m4。

3.1 網(wǎng)絡(luò)生存時(shí)間對(duì)比

HEED協(xié)議在接近20 s的時(shí)候網(wǎng)絡(luò)中的全部節(jié)點(diǎn)死亡，EEUC協(xié)議在接近100 s的時(shí)候網(wǎng)絡(luò)中的全部節(jié)點(diǎn)死亡，而DCHEB在接近160 s的時(shí)候網(wǎng)絡(luò)中的全部節(jié)點(diǎn)才會(huì)死亡,如圖3。

圖3 網(wǎng)絡(luò)的生存時(shí)間對(duì)比圖

3.2 網(wǎng)絡(luò)能耗的對(duì)比

HEED協(xié)議在接近20 s的時(shí)候整個(gè)網(wǎng)絡(luò)的能量消耗完，EEUC協(xié)議在接近100 s的時(shí)候整個(gè)網(wǎng)絡(luò)的能量消耗完，而DCHEB協(xié)議在將近160 s的時(shí)候整個(gè)網(wǎng)絡(luò)的能量才消耗完，如圖4。

圖4 網(wǎng)絡(luò)的能量消耗對(duì)比圖

本節(jié)采用Matlab仿真工具對(duì)HEED,EEUC和DCHEB 3種算法，分別從整個(gè)網(wǎng)絡(luò)的生存時(shí)間、整個(gè)網(wǎng)絡(luò)的能量消耗2個(gè)方面進(jìn)行仿真分析。分析表明:DCHEB協(xié)議的性能總體上要優(yōu)越于HEED,EEUC。

4 結(jié)束語

本文引入了雙簇首的思想，由于每個(gè)簇內(nèi)有主副簇首2個(gè)簇首節(jié)點(diǎn)，則可以使簇首節(jié)點(diǎn)的數(shù)據(jù)采集和轉(zhuǎn)發(fā)數(shù)據(jù)2項(xiàng)工作平均分配到主副簇首節(jié)點(diǎn)上去，從而使主副簇首節(jié)點(diǎn)的能量消耗要比一個(gè)簇首節(jié)點(diǎn)時(shí)慢很多，從而可以延緩簇首重構(gòu)的時(shí)間，減少簇首重構(gòu)的次數(shù)，達(dá)到節(jié)約網(wǎng)絡(luò)

能量，延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間的作用。但是DCHEB算法仍然存在一些不足之處，比如：會(huì)導(dǎo)致距離基站較近的節(jié)點(diǎn)也會(huì)因?yàn)橐D(zhuǎn)發(fā)相對(duì)較多的數(shù)據(jù)量而消耗大量的能量，導(dǎo)致整個(gè)網(wǎng)絡(luò)中能量消耗不均勻，出現(xiàn)比距離基站較遠(yuǎn)節(jié)點(diǎn)提前死亡的情況，這也是以后研究中需要考慮的主要方面之一。

參考文獻(xiàn):

[1] Xie X,Zhang H.Topology algorithm research based on energy and power control for topdisc algorithm[C]∥Second International Conference on Computer Modeling and Simulation,2010:37-40.

[2] Shirali M,Meybodi M R,Tarigh H D.Topology control scheduling:Based on the distributed learning automata[C]∥2010 IEEE 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM),2010:1-4.

[3] Hu X,Ren D R,Wang H,et al.Adaptive clustering algorithm based on energy restriction[C]∥2011 IEEE International Conference on Intelligent Computation Technology and Automation(ICICTA),2011:949-951.

[4] 胡 靜，沈連豐.基于博弈論的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].東南大學(xué)學(xué)報(bào):自然科學(xué)版,2010,40(3):441-445.

[5] Younis Ossama,Fahmy Sonia.HEED,A hybrid,energy-efficient,distributed clustering approach for Ad Hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):336-379.

[6] 崔 英.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議的研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué),2012.

[7] 呂 濤，朱清新，朱玉玉.一種能耗均衡的無線傳感器網(wǎng)絡(luò)分簇算法[J].計(jì)算機(jī)應(yīng)用,2012,32(11):3107-3111.

[8] 李成法，陳貴海，吳 杰.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào)，2007,30(1):27-35.

[9] 柴寶杰,馬寶英,范書平,等.無線傳感器網(wǎng)絡(luò)中改進(jìn)的 EEUC 路由算法[J].微計(jì)算機(jī)信息,2012(9):149.

[10] 戴世瑾，李樂民.高能量有效的基于分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議倡[J].計(jì)算機(jī)應(yīng)用研究,2010,27(6):2201-2203.

[11] 楊 軍，張德運(yùn)，張?jiān)埔?，?基于分簇的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)匯聚傳送協(xié)議[J].軟件學(xué)報(bào),2010,21(5):1127-1137.

[12] 徐小良，裘君娜.異構(gòu)傳感器網(wǎng)絡(luò)中一種能量有效的簇頭選擇算法[J].傳感技術(shù)學(xué)報(bào),2009，22(3):395-400.

[13] 何永剛，徐汀榮，彭 俊.無線傳感器網(wǎng)絡(luò)分簇方法的優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2011,47(1):92-95.

[14] 唐一梅，李志軍，胡 江，等.一種低能耗層次型傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴╗J].自動(dòng)化學(xué)報(bào)，2010,36(4):543-549.