[王瑞]
?
基于睡眠機制的WSN簇維護算法改進
[王瑞]
摘要
局域按需簇維護方法(LDMC)能夠明顯延長網(wǎng)絡(luò)的生命周期,但是網(wǎng)絡(luò)中仍存在大量的冗余節(jié)點,在成簇階段也沒有考慮剩余能量和節(jié)點密度對簇頭的影響,提出了一種改進的無線傳感網(wǎng)簇維護算法。該算法在簇頭的選舉階段引入了節(jié)點剩余能量和密度因子,避免能量過低的節(jié)點擔任簇頭;同時針對網(wǎng)絡(luò)中存在的大量的冗余節(jié)點提出部分冗余節(jié)點睡眠機制,使網(wǎng)絡(luò)的整體生命周期得以進一步延長。NS2仿真結(jié)果表明,與原局域按需簇維護算法相比,該改進優(yōu)化算法可減少業(yè)務(wù)中斷時長、增加發(fā)送的數(shù)據(jù)包總量;仿真條件下網(wǎng)絡(luò)的生命周期相較于LDMC方法最多可延長16.3%;網(wǎng)絡(luò)規(guī)模越大,運用該算法的優(yōu)勢越明顯。
關(guān)鍵詞:簇維護 睡眠機制 剩余能量 密度因子 生命周期
王瑞
重慶郵電大學信息與通信工程學院,碩士研究生,主要研究方向為物聯(lián)網(wǎng)理論與技術(shù)。
無線傳感網(wǎng)由計算、通信、能量等資源均受限的大量傳感器節(jié)點以多跳、自組織的方式組成,是物聯(lián)網(wǎng)感知層的核心支撐[1]。無線傳感網(wǎng)自二十世紀九十年代提出以來,引發(fā)了世界范圍內(nèi)的廣泛關(guān)注,特別是美國、日本、歐洲等發(fā)達
國家或地區(qū)陸續(xù)開展了無線傳感網(wǎng)方面的探索性研究[2]。傳感器節(jié)點一般通過電池供電,并且工作于無人值守的環(huán)境中,能量補給困難,甚至是一次性的,因此如何節(jié)省能量,延長網(wǎng)絡(luò)的生命周期顯得十分重要[3,4]。
基于簇的層次式拓撲結(jié)構(gòu)是無線傳感網(wǎng)最流行的組網(wǎng)模式,具有管理方便、能量利用高效、數(shù)據(jù)融合簡單等優(yōu)點[5-7]。目前,普遍采用全網(wǎng)周期性重新成簇的簇維護模式,導致超范圍過度維護,存在維護成本高、能量浪費嚴重、周期性服務(wù)中斷、響應不及時等缺點。因此,如何優(yōu)化管理與維護網(wǎng)絡(luò)拓撲、最大限度地均衡網(wǎng)絡(luò)內(nèi)節(jié)點的能量消耗以延長整個網(wǎng)絡(luò)的生命周期一直是無線傳感網(wǎng)的研究熱點。
一些研究者針對傳統(tǒng)全網(wǎng)周期性成簇存在的維護成本高、能量消耗大、針對性差、周期難確定等問題進行了改進:文獻[8]通過在簇頭形成過程中引入節(jié)點剩余能量,是對LEACH改進的一種雙輪成簇協(xié)議,形成混合型網(wǎng)絡(luò)拓撲結(jié)構(gòu);文獻[9]提出由匯聚(Sink)節(jié)點采用集中式算法產(chǎn)生簇頭,不需要每輪都選舉簇頭,簇頭是否輪換取決于簇的能量消耗;文獻[10]提出了兩種集中式簇頭產(chǎn)生算法:LEACH-C由基站負責完成簇頭選取工作,只有能量高于網(wǎng)絡(luò)平均剩余能量的節(jié)點才有可能成為簇頭;LEACH-F要求一旦簇被形成,簇的結(jié)構(gòu)就不再改變,簇內(nèi)節(jié)點無需每輪循環(huán)都構(gòu)造簇,減少了構(gòu)造簇的開銷;文獻[11]創(chuàng)造性地提出并構(gòu)建了基于事件驅(qū)動的“局域”、“按需”簇維護算法(LDMC),一旦網(wǎng)絡(luò)中出現(xiàn)需要維護的事件,能夠快速及時地在簇受損的局部范圍內(nèi)進行維護,明顯提高能量利用率、延長網(wǎng)絡(luò)生命周期;文獻[12]進一步從系統(tǒng)實現(xiàn)的角度進行了完善和仿真測試;在此基礎(chǔ)上,文獻[13]針對不同的簇受損情形建立了一種可以滿足不同簇維護需要的多模簇維護機制(M2CM),以自適應局域按需簇維護的需要。
局域按需簇維護方法的提出和多模簇維護機制的構(gòu)建,克服了傳統(tǒng)簇維護方法存在的弊端,能夠明顯減少簇維護的能量消耗、延長網(wǎng)絡(luò)生存時間,并增加傳輸數(shù)據(jù)包的總量。但這種方法在成簇階段時采用了LEACH算法,沒有考慮到節(jié)點剩余能量和節(jié)點的鄰居節(jié)點數(shù)對簇頭選取的影響;傳感器網(wǎng)絡(luò)中節(jié)點稠密撒布、節(jié)點間的有效探測范圍相互重疊,使得同一時刻不同節(jié)點采集來的數(shù)據(jù)存在大量的冗余,造成不必要的能量浪費。為進一步完善LDMC算法,本文提出IACM算法。該算法在簇頭選取階段,引入剩余能量因子和節(jié)點密度因子,對LDMC算法的簇頭選取閾值進行改進,使得簇頭的分布更加合理,避免了剩余能量小的節(jié)點或者孤立節(jié)點成為簇頭;同時引入節(jié)點睡眠機制,使得剩余能量小的部分冗余節(jié)點進入睡眠狀態(tài),不進行數(shù)據(jù)監(jiān)測,節(jié)省了節(jié)點能量,進一步延長了網(wǎng)絡(luò)生命周期、提高了數(shù)據(jù)包發(fā)送量。通過對T (n)的改進以及冗余節(jié)點睡眠機制來最大限度地減少簇維護的能量消耗和服務(wù)中斷次數(shù),延長網(wǎng)絡(luò)生命周期。
在物聯(lián)網(wǎng)感知層中,節(jié)點一般分為Sink節(jié)點和普通節(jié)點。本文假設(shè):
(1)網(wǎng)絡(luò)中有一個Sink節(jié)點和多個普通節(jié)點,且位置都是固定不變的;
(2)Sink節(jié)點的能量是可補充的,但普通節(jié)點的能量是受限的;Sink節(jié)點留存整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息;
(3)普通節(jié)點具有相同的初始屬性(如無線電發(fā)射功率、通信半徑、能量等);
(4)普通節(jié)點將收集的數(shù)據(jù)發(fā)送給簇頭,簇頭負責將收集的數(shù)據(jù)進行融合,然后以單跳或者多跳的方式傳送給Sink節(jié)點。
本文采用的無線通信能量消耗模型如圖1所示。
圖1 傳感器網(wǎng)絡(luò)能量消耗模型
傳感器節(jié)點發(fā)送l bit的信息,傳輸距離為d,則發(fā)送端消耗的能量可表示為:
式中,Eelec為無線收發(fā)電路的能量消耗,和分別為自由空間模型和多徑衰減模型中功率放大器的能量消耗;d0為傳輸距離門限,可用式(2)表示:
傳感器節(jié)點接收l bit消息的能耗為:
原簇維護算法根據(jù)不同的場景,設(shè)置了相應的維護動作,分別為有(無)簇頭重選、并入鄰簇、簇分裂、時隙再分配、簇合并以及多簇重新成簇等簇維護策略,有效地延長了網(wǎng)絡(luò)的生存時間。但是該算法在網(wǎng)絡(luò)初始化時,采用了LEACH算法進行分簇,沒有考慮節(jié)點密度對簇頭的影響;由于無線傳感網(wǎng)節(jié)點密度大,大量的冗余節(jié)點造成了不必要的能量消耗。
針對LDMC算法的不足,考慮到簇頭節(jié)點擔負著融合簇內(nèi)信息,并且發(fā)送至Sink節(jié)點的任務(wù),簇頭節(jié)點的壽命在很大程度上影響了整個網(wǎng)絡(luò)的生存時間。這里提出了兩點改進方法:、
(1)在簇頭選擇時,求出網(wǎng)絡(luò)的最優(yōu)簇頭數(shù),同時考慮節(jié)點剩余能量和密度,避免能量低或者鄰居節(jié)點少的節(jié)點被選為簇頭;
(2)根據(jù)節(jié)點監(jiān)測到的數(shù)據(jù)的相似度,使一部分節(jié)點進入睡眠狀態(tài),減少能量消耗。
3.1 簇頭選舉階段
原LDMC算法在成簇階段,采用LEACH算法進行簇的生成,沒有考慮能量和節(jié)點密度對簇頭選舉的影響。本文提出的改進算法,充分考慮了節(jié)點剩余能量和節(jié)點密度對簇頭選舉的影響,在簇頭選舉時,對閾值T(n)進行重新設(shè)定,使簇頭的分布更加合理。
在網(wǎng)絡(luò)其他條件一定時,當簇頭數(shù)在某一值時,網(wǎng)絡(luò)所消耗的能量最少,我們稱該值為最優(yōu)簇頭數(shù)。我們以單跳LEACH網(wǎng)絡(luò)求解最優(yōu)簇頭數(shù)。假定在的區(qū)域內(nèi)分布了N 個節(jié)點,簇頭數(shù)為k 個,EDA表示數(shù)據(jù)融合消耗的能量,計算最優(yōu)簇頭數(shù)Kopt。簇頭的能量主要消耗在接收簇內(nèi)節(jié)點的數(shù)據(jù)、數(shù)據(jù)融合以及把數(shù)據(jù)傳輸給Sink節(jié)點。每個簇頭節(jié)點的能耗為:
簇內(nèi)采用自由空間傳輸模型,假設(shè)簇內(nèi)成員節(jié)點每次發(fā)送l 比特的數(shù)據(jù)包,dCH表示到簇頭的距離,則一個簇內(nèi)成員節(jié)點的能量消耗為:
整個網(wǎng)絡(luò)是分布在M′ M 的區(qū)域內(nèi),有k個簇,則每個簇所占的區(qū)域平均是M2/ k ,假設(shè)這是一個圓形區(qū)域,則半徑,設(shè)區(qū)域內(nèi)節(jié)點的分布概率為,則簇內(nèi)成員節(jié)點到簇頭的距離的平方的數(shù)學期望是:
把式(7)帶入式(5)可以得到簇內(nèi)一個成員節(jié)點的能量消耗為:
因此一個簇在這一輪消耗的能量為:
則k 個簇消耗的能量E 可表示為:
等式兩邊對k 進行求導,得出最優(yōu)簇頭數(shù)kopt為:
在簇頭選取時考慮節(jié)點當前的剩余能量,增加剩余能量大的節(jié)點的當選概率,引入剩余能量因子:
節(jié)點周圍鄰居節(jié)點的多少,對簇頭的選取也有重要影響,在剩余能量相等的情況下,節(jié)點的密度越大,當選簇頭的概率越大。節(jié)點的密度因子可表示為:
其中Ntotal( i )為節(jié)點i的有效通信區(qū)域內(nèi)的節(jié)點總數(shù);Nalive為網(wǎng)絡(luò)中存活的節(jié)點總數(shù)。
通過引入節(jié)點剩余能量因子和密度因子,可以使簇頭的選擇更加合理,有助于節(jié)省能量,延長網(wǎng)絡(luò)的生命周期。改進的閾值為:
式中,k+ k = 1,p'= k/ n 。當簇頭選舉完
12opt成后,各個節(jié)點根據(jù)接收到的廣播信息的信號強度,選擇信號最強的簇頭加入。當所有節(jié)點都加入簇后,進入穩(wěn)定的數(shù)據(jù)傳輸階段。
在網(wǎng)絡(luò)初始化成簇以及執(zhí)行重新成簇的維護動作進行簇頭選取時,改進的閾值可以使簇頭位置更加合理,延長簇頭的壽命,減少重新選擇簇頭造成的網(wǎng)絡(luò)中斷,進而延長網(wǎng)絡(luò)生存時間。
3.2 簇維護階段
傳感器網(wǎng)絡(luò)中節(jié)點稠密撒布、節(jié)點間的有效探測范圍相互重疊。這使得在網(wǎng)絡(luò)數(shù)據(jù)收集應用中,同一時刻不同節(jié)點采集的數(shù)據(jù)間存在空間相關(guān)性,造成觀測信息間存在較高空間冗余度,使得網(wǎng)絡(luò)產(chǎn)生不必要的能量消耗。本文根據(jù)兩個節(jié)點監(jiān)測到的數(shù)據(jù)的時空相關(guān)性[14],使一部分節(jié)點進入睡眠狀態(tài),不進行信息監(jiān)測,直到將其喚醒,并在本簇內(nèi)進行廣播睡眠節(jié)點的ID。
分簇完成后,當簇頭接收一輪數(shù)據(jù)之后,若是有兩個節(jié)點監(jiān)測的數(shù)據(jù)的相似度達到一定值時,簇頭使得兩個節(jié)點中能量較小的進入睡眠狀態(tài),不再進行數(shù)據(jù)監(jiān)測,直到將其喚醒。
隨著網(wǎng)絡(luò)的運行,當網(wǎng)絡(luò)中出現(xiàn)了需要維護的事件時,立即對網(wǎng)絡(luò)進行維護,具體的維護機制如下:
(1)有簇頭重選
當進行有簇頭重選時,首先簇頭喚醒本簇內(nèi)的睡眠節(jié)點,然后簇頭在簇內(nèi)廣播cluster_rebuild消息,收到消息的簇內(nèi)節(jié)點把自己的剩余能量和ID發(fā)送給簇頭,簇頭選擇其中剩余能量最大的節(jié)點作為簇頭,并向簇內(nèi)其他節(jié)點和鄰近的簇頭廣播簇頭更換消息。當新簇頭接收一輪簇內(nèi)成員節(jié)點發(fā)送的數(shù)據(jù)后,根據(jù)兩個節(jié)點發(fā)送的數(shù)據(jù)的相似度使能量小的節(jié)點進入睡眠狀態(tài),不再進行數(shù)據(jù)監(jiān)測,同時在本簇內(nèi)廣播睡眠節(jié)點的ID。
(2)無簇頭重選
由最先發(fā)現(xiàn)簇頭失效的節(jié)點喚醒本簇內(nèi)的睡眠節(jié)點,然后進行無簇頭重選。當新簇頭接收一輪數(shù)據(jù)之后,根據(jù)數(shù)據(jù)的相似程度使剩余能量小的部分節(jié)點進入睡眠狀態(tài),不再進行數(shù)據(jù)監(jiān)測,同時在簇內(nèi)廣播睡眠節(jié)點的ID。
(3)并入鄰簇
當需要執(zhí)行并入相鄰簇的維護動作時,由需要加入鄰簇的簇頭喚醒本簇內(nèi)的睡眠節(jié)點。動作完成后,新簇頭根據(jù)接收到的數(shù)據(jù)的相似程度剩余能量小的部分節(jié)點進入睡眠狀態(tài),并在簇內(nèi)廣播睡眠節(jié)點的ID。
(4)簇分裂
當執(zhí)行簇分裂的維護動作時,首先由需要分裂的簇的簇頭喚醒本簇內(nèi)睡眠節(jié)點,然后執(zhí)行簇分裂。當維護動作完成后,新簇頭在接收一輪數(shù)據(jù)后,根據(jù)數(shù)據(jù)的相似程度使剩余能量小的部分節(jié)點進入睡眠狀態(tài),并在簇內(nèi)廣播睡眠節(jié)點ID。
(5)簇合并
需要進行合并的簇的簇頭將各自簇內(nèi)睡眠節(jié)點喚醒,然后執(zhí)行簇合并動作。合并完成后,當新簇頭接收一輪數(shù)據(jù)之后,如果兩個節(jié)點的監(jiān)測數(shù)據(jù)相似度達到一定程度,簇頭使得能量小的那個節(jié)點進入睡眠狀態(tài),并在簇內(nèi)廣播睡眠節(jié)點的ID。
(6)多簇重新成簇
需要執(zhí)行重新成簇的各個簇頭喚醒本簇內(nèi)的睡眠節(jié)點,然后執(zhí)行多簇重新成簇的維護動作。當新簇頭產(chǎn)生后,簇頭根據(jù)接收到的數(shù)據(jù)的相似度使一部分節(jié)點進入睡眠狀態(tài),并在本簇內(nèi)廣播睡眠節(jié)點的ID。
當維護完成后,繼續(xù)進入穩(wěn)定的數(shù)據(jù)傳輸階段。隨著網(wǎng)絡(luò)的運行,當網(wǎng)絡(luò)中發(fā)生需要維護的事件時,網(wǎng)絡(luò)會在受損的局域范圍內(nèi)進行維護,執(zhí)行相應的改進后的維護動作,如此循環(huán)。
4.1 仿真場景設(shè)置
本文采用網(wǎng)絡(luò)仿真軟件NS-2.34,仿真區(qū)域為100m×100 m,在其中隨機分布100個和200個傳感器節(jié)點,基站位于場景上方。具體的節(jié)點仿真參數(shù)配置如表1所示。
表1 仿真參數(shù)配置
4.2 仿真結(jié)果分析
圖2為在網(wǎng)絡(luò)運行過程中當出現(xiàn)了受損簇時分別采用LDMC和改進算法的簇維護方法所對應的網(wǎng)絡(luò)中斷時長對比圖。由圖2可見,當網(wǎng)絡(luò)中出現(xiàn)了受損簇時,采用改進算法比LDMC簇維護方法更能減少網(wǎng)絡(luò)中斷時長,約減少了11.48%,同時也減少了業(yè)務(wù)中斷次數(shù),更加有利于簇結(jié)構(gòu)穩(wěn)定。這是因為在簇頭選舉時,考慮了剩余能量因子和密度因子的影響,重新設(shè)置閾值,使得節(jié)點剩余能量大、鄰居節(jié)點多的節(jié)點當選簇頭的概率增大,避免了節(jié)點剩余能量小的節(jié)點當選簇頭造成的頻繁的網(wǎng)絡(luò)中斷;同時,在網(wǎng)絡(luò)中引入節(jié)點睡眠機制,使網(wǎng)絡(luò)中剩余能量小的部分冗余節(jié)點進入睡眠狀態(tài),不進行數(shù)據(jù)監(jiān)測,節(jié)省了能量,同時也減輕了簇頭的負擔,節(jié)省了能量,使網(wǎng)絡(luò)運行更加穩(wěn)定,也即減少了網(wǎng)絡(luò)的中斷時長和中斷次數(shù)。
圖2 LDMC與改進算法中斷時長對比
由圖3可知,當網(wǎng)絡(luò)中有100個節(jié)點時,LDMC算法的網(wǎng)絡(luò)存活時間是744s,LEACH協(xié)議的網(wǎng)絡(luò)存活時間為521s,改進算法的網(wǎng)絡(luò)存活時間為835s,較LDMC算法延長了約12.2%,相比于LEACH協(xié)議延長了約60.3%。這是因為該改進算法使得簇頭分布更加合理,引入睡眠機制,減少了節(jié)點冗余和中斷次數(shù),節(jié)省了能量消耗,從而延長網(wǎng)絡(luò)存活時間。
圖3 兩種算法的網(wǎng)絡(luò)存活時間對比
由圖4可知,LDMC算法接收了78235比特的數(shù)據(jù)量,改進算法接收了89189比特的數(shù)據(jù)量,提高約14.0%;LEACH協(xié)議中基站接收了52374比特的數(shù)據(jù),改進算法較之提高了約70.3%。由此可見:改進算法在延長網(wǎng)絡(luò)存活時間的同時,增加了基站接收到的數(shù)據(jù)包數(shù)量。
圖4 數(shù)據(jù)傳輸量對比
本文在相對于傳統(tǒng)全網(wǎng)周期性重新成簇具有較大優(yōu)勢的局域按需簇維護算法基礎(chǔ)上,提出一種改進優(yōu)化算法。首先引入剩余能量因子和節(jié)點密度因子對選舉閾值進行改進,使得剩余能量大、鄰居節(jié)點多的節(jié)點稱為簇頭的幾率增大;然后根據(jù)節(jié)點監(jiān)測數(shù)據(jù)的相似度使一部分能量低的節(jié)點進入睡眠狀態(tài),減少了數(shù)據(jù)冗余度,節(jié)省了節(jié)點的能量消耗,延長了簇頭的存活時間,進而使得網(wǎng)絡(luò)的生命周期得以延長。仿真測試結(jié)果表明:相比于原局域按需簇維護算法,改進算法有助于減少業(yè)務(wù)中斷次數(shù)和中斷時長,降低用于簇維護的能量消耗,增加傳輸數(shù)據(jù)包總量,網(wǎng)絡(luò)生命周期最多延長了12.2%;網(wǎng)絡(luò)規(guī)模越大,運用該優(yōu)化算法的優(yōu)勢越明。
參考文獻
1Li Shancang, Xu Lida, Zhao Shanshan. The internet of things: a survey[J], Information Systems Frontiers, 2015, 17(2):243-259
2Iyengar R, Kar K, Banerjee S. Low- coordination topologies for redundancy in sensor networks [C]// Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Chicago, USA: ACM,2005: 332-342
3錢志鴻,王義軍. 面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述[J]. 電子與信息學報,2013, 35(1):215-225
4孫波,高隨祥. 無線傳感器網(wǎng)絡(luò)中最大化簇壽命的優(yōu)化模型[J].計算機仿真,2008, 25(2):116-120
5HEINZELMAN W R, CHANDRAKA- SAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless micro sensor networks[C] // Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Hawaii: IEEE Computer Society, 2000: 10-15
6Handy MJ, Haase M, Timmermann D. Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]// Proceedings of the 4th IEEE Conf. on Mobile and Wireless Communications Networks, 2002: 368-372
7YOUNIS O, FAHMY S. HEED: A hybrid energy- efficient distributed clustering approach for Ad hoc sensor networks [J]. IEEE Transaction on Mobile Computing, 2004, 3(4): 366-379
8Chan H, Perrig A. ACE: An emergent algorithm for highly uniform cluster formation[C]// Proceedings of the 1st European Workshop on Wireless Sensor Networks. LNCS 2920, Berlin: Springer Verlag, 2004: 154-171
9Tillapart P, Thumthawatworn T, Pakdeepinit P. Method for cluster heads selection in wireless sensor networks[C]// Proceedings of the 2004 IEEE Aerospace Conf. Chiang Mai: IEEE Press, 2004: 3615-3620
10Gao J J, Liu Y H, Zhu L Q, et al. The LEACH-DCHS protocol cluster maintenance algorithm based on WSN[J]. Computer engineering and applications, 2009, 45(30): 95-97
11廖明華, 張華, 王東. 基于LEACH 協(xié)議的簇頭選舉改進算法[J]. 計算機工程, 2011, 37(7): 112-114
12胡向東,徐慧芬,張力. 物聯(lián)網(wǎng)感知層局域按需簇維護模型與算法[J]. 軟件學報, 2015,26(8):2020-2040
13胡向東,徐慧芬,王愷. 無線傳感網(wǎng)多模簇維護機制與算法[J].系統(tǒng)工程與電子技術(shù),2015,37(10): 2376-2382
14王軍,王正路,程勇. 基于時間序列預測模型的簇型數(shù)據(jù)收集機制[J]. 計算機應用,2014,34(10):2766-2770
DOI:10.3969/j.issn.1006-6403.2016.02.012
收稿日期:(2016-01-12)