李 龍,劉建明,李宏周,彭智勇
(1.桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院,廣西桂林541004;2.桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣西桂林541004)
無(wú)線傳感器網(wǎng)絡(luò)[1]是由大量隨機(jī)部署的傳感器節(jié)點(diǎn)通過(guò)無(wú)線電通信構(gòu)成的自組織網(wǎng)絡(luò),目的是感知、監(jiān)測(cè)、采集和處理網(wǎng)絡(luò)覆蓋圍內(nèi)的相關(guān)環(huán)境參數(shù),并最終傳遞給觀察者。網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)擁有的能量十分有限,因此,在不影響網(wǎng)絡(luò)整體功能的前提下,盡可能高效地利用節(jié)點(diǎn)的能量以最大限度延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間成為無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)中的核心問(wèn)題。為此,Wendi Rabiner Heinzelman等人在網(wǎng)絡(luò)路由層面提出了LEACH(low energy adaptive clustering hierarchy)算法[3,4]。
LEACH協(xié)議將整個(gè)網(wǎng)絡(luò)劃分為邏輯上的層次結(jié)構(gòu),按功能將網(wǎng)絡(luò)中的節(jié)點(diǎn)區(qū)分為簇頭節(jié)點(diǎn)和普通節(jié)點(diǎn)。其基本思想是周期性地隨機(jī)選擇部分節(jié)點(diǎn)成為簇頭節(jié)點(diǎn),負(fù)責(zé)收集其他節(jié)點(diǎn)發(fā)送的數(shù)據(jù)并與基站通信;其他普通節(jié)點(diǎn)按照通信距離的遠(yuǎn)近選擇較近的簇頭節(jié)點(diǎn)入簇,并在自己所屬的時(shí)間片內(nèi)將收集到的數(shù)據(jù)直接發(fā)送給本簇的簇頭。由于簇頭節(jié)點(diǎn)需要收集本簇內(nèi)所有節(jié)點(diǎn)的數(shù)據(jù),并進(jìn)行數(shù)據(jù)融合以及發(fā)送給基站,使得此類(lèi)節(jié)點(diǎn)的能耗較大、更容易死亡,因此在具體選擇簇頭的過(guò)程中應(yīng)該充分考慮這一現(xiàn)象,力求將整個(gè)網(wǎng)絡(luò)的能量消耗盡可能平均地分配到每個(gè)傳感器節(jié)點(diǎn),從而達(dá)到降低網(wǎng)絡(luò)能源消耗、提高網(wǎng)絡(luò)整體生存時(shí)間的目的。本文以LEACH協(xié)議為基礎(chǔ),提出了一種新的簇頭選擇算法,該算法在選舉簇頭的過(guò)程中考慮所有節(jié)點(diǎn)的剩余能量分布情況,并根據(jù)節(jié)點(diǎn)自身剩余能量將節(jié)點(diǎn)歸類(lèi),不同類(lèi)別的節(jié)點(diǎn)擁有不同的閾值T(n),即當(dāng)選為本輪簇頭節(jié)點(diǎn)的概率不同,最終使得網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能耗更加均衡?;贜S2的仿真結(jié)果表明,該算法可以更好平衡網(wǎng)絡(luò)中各節(jié)點(diǎn)的能量消耗,在延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間、提高網(wǎng)絡(luò)數(shù)據(jù)吞吐量等方面都有比較好的表現(xiàn)。
按照節(jié)點(diǎn)的功能不同,LEACH協(xié)議將構(gòu)成整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)分為3類(lèi):簇頭節(jié)點(diǎn)、簇內(nèi)節(jié)點(diǎn)、基站節(jié)點(diǎn)。其網(wǎng)絡(luò)模型如圖1所示,其中各種節(jié)點(diǎn)的詳細(xì)屬性設(shè)定如下[4,6]:
(1)基站節(jié)點(diǎn)的位置固定,原理監(jiān)測(cè)區(qū)域,并且具有充足的能量供應(yīng),即研究中不考慮基站的能量消耗;
(2)除基站節(jié)點(diǎn)外,其他節(jié)點(diǎn)具有完全相同的物理結(jié)構(gòu)、初始能量,并且能量供應(yīng)有限;
(3)所有節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)域內(nèi),并且節(jié)點(diǎn)是靜止的;
(4)節(jié)點(diǎn)可感知自身的剩余能量;
(5)節(jié)點(diǎn)總是有數(shù)據(jù)要發(fā)送;
(6)相鄰節(jié)點(diǎn)收集到的數(shù)據(jù)具有相似性,可以通過(guò)數(shù)據(jù)融合減少通信量;
(7)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)可以相互通信,且都使用單跳通信。
本文中在計(jì)算節(jié)點(diǎn)能耗的時(shí)候,使用的是文獻(xiàn)[4]中提供的無(wú)線通信能耗模型,即一階無(wú)線電模型,如圖2所示。
圖1 LEACH協(xié)議網(wǎng)絡(luò)模型
圖2 一階無(wú)線電模型
該模型中,數(shù)據(jù)發(fā)送端節(jié)點(diǎn)的能耗包含發(fā)送電路能耗、放大電路能耗,數(shù)據(jù)接收端節(jié)點(diǎn)的能耗只包含接收電路能耗。
本文中設(shè)定發(fā)送電路以及接收電路的能耗為Eelec=50nJ/bit,放大電路的能耗為εamp=100pJ/bit/m2。
據(jù)此便可求得數(shù)據(jù)發(fā)送端節(jié)點(diǎn)的能耗為ETx(k,d)=Eelec*k+εamp*k*d2;數(shù)據(jù)接收端節(jié)點(diǎn)的能耗為ERx(k)=Eelec*k。
其中,k為節(jié)點(diǎn)間傳送的數(shù)據(jù)量,單位為bit;d為節(jié)點(diǎn)間通信距離。相較于數(shù)據(jù)發(fā)送、接收時(shí)的能耗,節(jié)點(diǎn)在閑置、休眠時(shí)的能耗可以忽略不計(jì)。
LEACH協(xié)議定義了“輪(round)”的概念來(lái)細(xì)化網(wǎng)絡(luò)的工作流程,如圖3所示,一輪包括簇的生成和數(shù)據(jù)傳輸兩個(gè)階段[4]。
在簇的生成階段,每個(gè)節(jié)點(diǎn)自主選擇是否成為當(dāng)前輪的簇頭,若成為簇頭則通過(guò)CSMA MAC協(xié)議以相同的傳輸能量向整個(gè)網(wǎng)絡(luò)廣播自己成為簇頭的消息;其他非簇頭節(jié)點(diǎn)根據(jù)接收到的多個(gè)廣播消息的強(qiáng)度來(lái)決定加入哪個(gè)簇,并通過(guò)CSMA MAC協(xié)議將自己加入該簇的信息報(bào)告給相應(yīng)的簇頭;簇頭節(jié)點(diǎn)收到所有的非簇頭節(jié)點(diǎn)想要加入該簇的信息后,基于本簇內(nèi)加入的節(jié)點(diǎn)數(shù)目創(chuàng)建TDMA調(diào)度,并通知簇內(nèi)節(jié)點(diǎn)。在數(shù)據(jù)傳輸階段,簇內(nèi)節(jié)點(diǎn)在分配好的時(shí)隙內(nèi)把采集到的數(shù)據(jù)發(fā)送給簇頭,簇頭對(duì)收集到的數(shù)據(jù)進(jìn)行融合、壓縮后轉(zhuǎn)發(fā)至基站節(jié)點(diǎn)。
圖3 LEACH協(xié)議的工作流程
為提高能量的利用效率,減少頻繁分簇帶來(lái)的能量消耗以及信息傳遞的延時(shí),每一輪中的數(shù)據(jù)傳輸階段要遠(yuǎn)遠(yuǎn)長(zhǎng)于簇的生成階段。
從LEACH協(xié)議的工作流程我們也可以看出,在每一輪中,只有在簇的生成階段選擇合適的簇頭,并以簇為單位對(duì)網(wǎng)絡(luò)進(jìn)行合理的分割,才能在接下來(lái)的數(shù)據(jù)傳輸階段提高網(wǎng)絡(luò)的整體效率,并最終延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。
在LEACH協(xié)議中提供了一種簇頭節(jié)點(diǎn)的選取原則:在簇的生成階段,每個(gè)節(jié)點(diǎn)都擁有閾值T(n),同時(shí)會(huì)生成一個(gè)(0,1)之間的隨機(jī)數(shù),如果該隨機(jī)數(shù)小于閾值T(n),則該節(jié)點(diǎn)當(dāng)選為本輪中的簇頭。節(jié)點(diǎn)閾值T(n)的計(jì)算公式如下
其中,p是期望的簇頭數(shù)在所有節(jié)點(diǎn)中占的百分比,r是輪數(shù),G是最近1/p輪中未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)集合。
關(guān)于LEACH協(xié)議中的簇頭選擇算法,科研人員已經(jīng)進(jìn)行了許多探索,在文獻(xiàn)[5]中提出了一種基于節(jié)點(diǎn)剩余能量的簇頭選擇算法,該算法更改了簇頭選擇過(guò)程中的節(jié)點(diǎn)閾值T(n)的計(jì)算方法,添加了乘性因子E_current/E_max,得出新的計(jì)算公式
其中,E_current是當(dāng)前節(jié)點(diǎn)的剩余能量,E_max是當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量的最大值,p、r、G的含義與前面相同。
顯而易見(jiàn),上述式(2)中之所以添加乘性因子E_current/E_max,是將所有節(jié)點(diǎn)的剩余能量默認(rèn)為服從線性分布,目的是使得剩余能量大的節(jié)點(diǎn),有更大的概率當(dāng)選為本輪簇頭。但是通過(guò)仿真可以發(fā)現(xiàn),某一時(shí)刻網(wǎng)絡(luò)中所有節(jié)點(diǎn)的剩余能量之間沒(méi)有必然的規(guī)律(如圖4所示),可視為隨機(jī)分布,在這種情況下,若求取閾值的過(guò)程中只考慮兩個(gè)節(jié)點(diǎn)的剩余能量E_current、E_max不足以體現(xiàn)整個(gè)網(wǎng)絡(luò)的能耗情況,節(jié)點(diǎn)間能量消耗的均衡性不夠理想。
圖4 節(jié)點(diǎn)剩余能量分布
為更好的解決上面提到的問(wèn)題,使得節(jié)點(diǎn)間的能量消耗更加均衡,本文在充分考慮節(jié)點(diǎn)剩余能量的分布的情況下,結(jié)合節(jié)點(diǎn)自身的剩余能量情況,提出基于節(jié)點(diǎn)剩余能量分布的簇頭選擇算法。
網(wǎng)絡(luò)運(yùn)行過(guò)程中,LEACH協(xié)議會(huì)周期性地、不間斷地進(jìn)行簇頭的選擇,同樣的,新算法也會(huì)周期性地要求基站進(jìn)行以下工作:收集網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的剩余能量信息、求取剩余能量平均值E_average,并統(tǒng)計(jì)剩余能量高于該平均值的節(jié)點(diǎn)的數(shù)量num_HaveMoreEnergy,此類(lèi)節(jié)點(diǎn)被視為高能量節(jié)點(diǎn),反之視為低能量節(jié)點(diǎn);在統(tǒng)計(jì)完成后,基站會(huì)將統(tǒng)計(jì)結(jié)果面向全網(wǎng)廣播,其中統(tǒng)計(jì)信息中含有以下數(shù)據(jù):所有節(jié)點(diǎn)的平均剩余能量、高能量節(jié)點(diǎn)數(shù)、理想簇頭數(shù)等。
新算法的核心思想就是基站周期性地收集網(wǎng)絡(luò)的剩余能量情況并獲得統(tǒng)計(jì)信息,若統(tǒng)計(jì)信息中高能量節(jié)點(diǎn)的數(shù)量大于理想簇頭節(jié)點(diǎn)數(shù)num_clusters,則簇頭節(jié)點(diǎn)全部從高能量節(jié)點(diǎn)中選出,否則,num_HaveMoreEnergy個(gè)高能量節(jié)點(diǎn)全部擔(dān)任簇頭,有(num_clusters-num_HaveMoreEnergy)個(gè)簇頭節(jié)點(diǎn)按照某一特定概率從低能量節(jié)點(diǎn)中選出。
對(duì)于每一個(gè)節(jié)點(diǎn)來(lái)說(shuō),該節(jié)點(diǎn)接收來(lái)自基站的數(shù)據(jù)廣播,判斷網(wǎng)絡(luò)整體能耗情況并結(jié)合自身剩余能量情況生成閾值T(n),然后與隨機(jī)數(shù)RandomRange{0 1}相比較,判定自身是否擔(dān)任本輪中的簇頭,圖5為該簇頭選擇算法的具體流程圖。
圖5中T(n)_式(1)的具體公式為
圖5中T(n)_式(2)的具體公式為
圖5 流程
為了評(píng)估本文中提出的簇頭選擇算法的合理性以及有效性,并在節(jié)點(diǎn)能量消耗、網(wǎng)絡(luò)數(shù)據(jù)吞吐量以及網(wǎng)絡(luò)存活時(shí)間等方面與其他研究人員提出的簇頭選擇算法相比較,本文以NS2為仿真平臺(tái)分別對(duì)LEACH中的簇頭選擇算法、文獻(xiàn)[5]中提出的簇頭選擇算法、本文中提出的基于節(jié)點(diǎn)剩余能量分布的簇頭選擇算法進(jìn)行數(shù)十次仿真,并對(duì)仿真結(jié)果進(jìn)行分析比較。仿真場(chǎng)景中詳細(xì)的參數(shù)設(shè)置見(jiàn)表1。
表1 仿真參數(shù)設(shè)置
本文基于相同的仿真場(chǎng)景,分別對(duì)前文中提到的3種簇頭選擇算法進(jìn)行了仿真。仿真主要對(duì)比了將不同的簇頭選擇算法應(yīng)用到WSN時(shí),網(wǎng)絡(luò)在生存時(shí)間、數(shù)據(jù)吞吐量、節(jié)點(diǎn)生存時(shí)間、節(jié)點(diǎn)平均能耗等多個(gè)方面的表現(xiàn)。
4.2.1 網(wǎng)絡(luò)生存時(shí)間
由于節(jié)點(diǎn)能量受限,網(wǎng)絡(luò)生存時(shí)間成為衡量該網(wǎng)絡(luò)性能的指標(biāo)之一。為此,本文分別對(duì)應(yīng)用不用簇頭選擇算法的網(wǎng)絡(luò)進(jìn)行10次仿真,并對(duì)仿真數(shù)據(jù)進(jìn)行綜合分析,得出圖6中的仿真結(jié)果對(duì)比圖。
在仿真的過(guò)程中,如果存活節(jié)點(diǎn)的數(shù)量小于理想簇頭節(jié)點(diǎn)數(shù),即認(rèn)為網(wǎng)絡(luò)死亡,仿真結(jié)束。當(dāng)網(wǎng)絡(luò)中分別應(yīng)用LEACH協(xié)議中的簇頭選擇算法(式(1))、文獻(xiàn)[5]中介紹的簇頭選擇算法(式(2))、本文中提出的基于節(jié)點(diǎn)剩余能量分布的簇頭選擇算法時(shí)(圖5),網(wǎng)絡(luò)生存時(shí)間的平均值分別為551s、608s、653s,可見(jiàn)本文中提出的新算法在提高網(wǎng)絡(luò)的生存時(shí)間方面有比較大的優(yōu)勢(shì)。
4.2.2 存活節(jié)點(diǎn)數(shù)
圖7中繪制的是10次仿真過(guò)程中首個(gè)死亡節(jié)點(diǎn)的出現(xiàn)時(shí)間對(duì)比圖。圖8為10次仿真過(guò)程中節(jié)點(diǎn)平均存活數(shù)。從圖7中的仿真結(jié)果得出,分別將3種不同的簇頭選擇算法(排序同上)應(yīng)用到網(wǎng)絡(luò)中的時(shí)候,首個(gè)死亡節(jié)點(diǎn)出現(xiàn)時(shí)間的平均值分別為370s,400s,410s。從圖8可以看出,若網(wǎng)絡(luò)在簇頭選擇過(guò)程中使用本文中提出的新算法,其存活節(jié)點(diǎn)數(shù)在整個(gè)網(wǎng)絡(luò)的生存時(shí)間內(nèi)都明顯高于應(yīng)用其他簇頭選擇算法的網(wǎng)絡(luò)。
4.2.3 節(jié)點(diǎn)的平均能耗
隨著仿真過(guò)程的進(jìn)行,節(jié)點(diǎn)的能耗不斷增加,若能耗大魚(yú)2J,則節(jié)點(diǎn)死亡。圖9中繪制的是整個(gè)仿真過(guò)程中,隨著網(wǎng)絡(luò)運(yùn)行時(shí)間不斷加長(zhǎng),所有節(jié)點(diǎn)的平均能耗情況。從圖中可見(jiàn),由于應(yīng)用了新的簇頭選擇算法,網(wǎng)絡(luò)中節(jié)點(diǎn)的平均能耗明顯降低,能量利用更加均衡合理,相應(yīng)地延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。
4.2.4 網(wǎng)絡(luò)數(shù)據(jù)吞吐量
本文不僅在網(wǎng)絡(luò)生存時(shí)間、節(jié)點(diǎn)能耗方面對(duì)新的簇頭選擇算法進(jìn)行了分析,還對(duì)比了在應(yīng)用不同分簇算法時(shí)網(wǎng)絡(luò)的數(shù)據(jù)吞吐量,如圖10所示。本文中統(tǒng)計(jì)的數(shù)據(jù)吞吐量是在網(wǎng)絡(luò)死亡后,基站節(jié)點(diǎn)所成功接收到的全部數(shù)據(jù)量。分別對(duì)應(yīng)用不同簇頭選擇算法(排序同上)的網(wǎng)絡(luò)進(jìn)行10次仿真,得出網(wǎng)絡(luò)數(shù)據(jù)吞吐量的平均值分別為44720bit、45960bit、47420bit。顯而易見(jiàn),本文中提出的簇頭選擇算法在提高網(wǎng)絡(luò)的數(shù)據(jù)吞吐量方面表現(xiàn)尤為突出。
圖7 首個(gè)死亡節(jié)點(diǎn)的出現(xiàn)時(shí)間
圖8 存活節(jié)點(diǎn)數(shù)
圖9 所有節(jié)點(diǎn)的平均能耗
圖10 網(wǎng)絡(luò)數(shù)據(jù)吞吐量
綜合以上仿真結(jié)果可見(jiàn),相比于其他的簇頭選擇算法,本文中提出的基于節(jié)點(diǎn)剩余能量分布的簇頭選擇算法在平衡節(jié)點(diǎn)能耗、延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間、提高網(wǎng)絡(luò)數(shù)據(jù)吞吐量多個(gè)方面都有比較大優(yōu)勢(shì)。
本文中提出了一種基于節(jié)點(diǎn)剩余能量分布的簇頭選擇算法,并使用NS2仿真軟件對(duì)該算法進(jìn)行了驗(yàn)證,通過(guò)仿真數(shù)據(jù)可以發(fā)現(xiàn),相比于其他簇頭選擇算法,該算法可以更好平衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗,在延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間、提高網(wǎng)絡(luò)數(shù)據(jù)吞吐量等方面都有比較好的表現(xiàn),與仿真前的設(shè)想一致。
不可忽略的是,該算法的實(shí)現(xiàn)需要節(jié)點(diǎn)周期性地獲取自身的剩余能量并上傳到基站,基站統(tǒng)計(jì)分析全局的能量信息之后再?gòu)V播給所有節(jié)點(diǎn),這會(huì)增加網(wǎng)絡(luò)中控制信息的發(fā)送量,給數(shù)據(jù)的傳遞帶來(lái)延時(shí),這是接下來(lái)需要進(jìn)一步改進(jìn)的地方。除此之外,LEACH協(xié)議在其他方面還需進(jìn)一步研究,例如,簇頭的分布位置不合理、簇的規(guī)模不均勻等。
[1]Liu X.A survey on clustering routing protocols in wireless sensor networks[J].Sensors,2012(12):11113-11153.
[2]Meenakshi Sharma,Kalpana Sharma.An energy efficient extended LEACH(EEELEACH)[C]//International Conference on Communication Systems and Network Technologies,2012:377-382.
[3]ZHANG Yabin.Research on layered-clustering routing and simulation platform for underwater sensor network[D].Guilin:Guilin University of Electronic Technology,2012(in Chinese).[張亞斌.水下傳感器網(wǎng)絡(luò)分層-分簇路由與仿真平臺(tái)研究[D].桂林:桂林電子科技大學(xué),2012.]
[4]DAI Sisi,TANG Junhua,ZHANG Aixin.Gossiping-based directed diffusion for wireless sensor network[J].China Infor-mation Security,2010(4):45-49(in Chinese).[戴思思,唐俊華,張愛(ài)新.基于Gossip算法的定向擴(kuò)散協(xié)議研究[J].信息安全與通信保密,2010(4):45-49.]
[5]HUANG Jiayi,CHENG Lianglun.Balanced energy clustering algorithm of WSN which cluster region were adjusted adaptively[J].Application Research of Computers,2012(29):4276-4279(in Chinese).[黃加異,程良倫.一種聚類(lèi)區(qū)域自適應(yīng)調(diào)整的WSN能耗均衡分簇算法[J].計(jì)算機(jī)應(yīng)用研究,2012(29):4276-4279.]
[6]Hyunsook Kim.Cluster head selection scheme for minimizing the changes of the cluster members considering mobility in mobile wireless sensor networks[C]//ICACT,2013.
[7]Deng S,Li J,Shen L.Mobility-based clustering protocol for wireless sensor networks with mobile nodes[J].Wireless Sensor Systems,2011(1):39-47.
[8]Andrey K,Ahmed S.Prediction-based clustering algorithm for mobile wireless sensor networks[C]//International Conference on Advanced Communication Technology.Phoenix Park,2012:1209-1215.
[9]YANG Ming,XU Ruichen,JIANG Ting.A cluster head selection mechanism based on historical information[J].Communications Technology,2011,44(11):97-99(in Chinese).[楊明,許瑞琛,蔣挺.一種基于歷史信息的簇頭選取機(jī)制[J].通信技術(shù),2011,44(11):97-99.]
[10]HUANG Tao,YANG Ning,ZHANG Zhijiang,et al.Analysis and simulation of LEACH and its evolution routing protocols[J].Radio Communications Technology,2009(35):4-7(in Chinese).[黃韜,楊寧,張智江,等.LEACH及其演進(jìn)路由協(xié)議分析與仿真[J].無(wú)線電通信技術(shù),2009(35):4-7.]
[11]Asaduzzaman,Hyung Yun Kong.Energy efficient cooperative LEACH protocol for wireless sensor networks[J].Journal of Communications and Networks,2012,12(4):358-365.
[12]TIAN Wei,YANG Zhen.Research on WSN geographic routing algorithm[J].China Communications,2010,7(3):153-157(in Chinese).[田煒,楊震.WSN地理位置路由算法研究[J].中國(guó)通信,2010,7(3):153-157.]