無線傳感器網(wǎng)絡(luò)由于具有低功耗、低成本以及分布式和自組織等特點已被廣泛應(yīng)用于軍事國防、工農(nóng)業(yè)控制、環(huán)境監(jiān)測、生物醫(yī)療和搶險救災(zāi)等領(lǐng)域。通常,一個無線傳感器網(wǎng)絡(luò)由成百上千傳感器節(jié)點組成,每個節(jié)點具有感知當(dāng)前環(huán)境、通過廣播與鄰近節(jié)點進(jìn)行通信以及對收集的信息執(zhí)行本地計算的能力。但是,這些能力對每個節(jié)點來說都很有限,尤其是節(jié)點的能量受限嚴(yán)重限制了網(wǎng)絡(luò)的生命周期,從而影響了網(wǎng)絡(luò)的服務(wù)質(zhì)量和進(jìn)一步應(yīng)用。因此,近幾年來,許多研究人員對無線傳感器網(wǎng)絡(luò)的節(jié)能方面進(jìn)行了大量的研究,從擁塞控制[2]到數(shù)據(jù)壓縮,從睡眠調(diào)度到拓?fù)淇刂。目的是盡可能多的節(jié)省能量,最大化網(wǎng)絡(luò)生命周期。
拓?fù)淇刂谱鳛闊o線傳感器網(wǎng)絡(luò)的一種關(guān)鍵節(jié)能技術(shù),通常在保持網(wǎng)絡(luò)重要特性如連通和覆蓋的前提下改變、簡化或優(yōu)化網(wǎng)絡(luò)的拓?fù)鋪砉?jié)省能量。而且,拓?fù)淇刂菩纬傻牧己镁W(wǎng)絡(luò)拓?fù)淠軌蛱岣呗酚蓞f(xié)議和MAC 協(xié)議的效率[5].然而,拓?fù)淇刂仆ǔ1灰暈橐粋單一過程,它并未包括對網(wǎng)絡(luò)拓?fù)涞木S護(hù),這影響拓?fù)淇刂扑惴ǖ姆诸悺D壳暗姆诸惗季窒抻谌绾螛?gòu)建網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),而忽略拓?fù)淇刂浦械耐負(fù)渚S護(hù)。如文獻(xiàn)[6]提出的分類只注重拓?fù)錁?gòu)建算法,這些算法通過改變節(jié)點的傳輸范圍來構(gòu)建和優(yōu)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。文獻(xiàn)[5][7]中提出一個更廣泛的拓?fù)錁?gòu)建算法分類,主要考慮分層和混合算法。文獻(xiàn)[8]提出了拓?fù)淇刂朴赏負(fù)錁?gòu)建和拓?fù)渚S護(hù)兩個階段組成,并對拓?fù)渚S護(hù)進(jìn)行了簡單定義和分類。
雖然文獻(xiàn)[8]中對拓?fù)渚S護(hù)進(jìn)行了簡單定義,并根據(jù)目標(biāo)優(yōu)化拓?fù)錁?gòu)建的時間將拓?fù)渚S護(hù)技術(shù)分為靜態(tài)、動態(tài)和混合拓?fù)渚S護(hù)。但文中并未對拓?fù)渚S護(hù)進(jìn)行系統(tǒng)闡述,而對拓?fù)渚S護(hù)的定義又不嚴(yán)謹(jǐn),對拓?fù)渚S護(hù)技術(shù)的分類也與當(dāng)前研究現(xiàn)狀不符,因為現(xiàn)有研究中基本上沒有文中所提到的靜態(tài)和混合拓?fù)渚S護(hù)算法或協(xié)議。因此,為了更深入的對無線傳感器網(wǎng)絡(luò)中的拓?fù)渚S護(hù)技術(shù)進(jìn)行研究,本文從拓?fù)渚S護(hù)定義及模型,拓?fù)渚S護(hù)設(shè)計目標(biāo),以及當(dāng)前的研究現(xiàn)狀和存在的問題與發(fā)展方向等方面對拓?fù)渚S護(hù)進(jìn)行了闡述。第1 節(jié)描述了無線傳感器網(wǎng)絡(luò)拓?fù)渚S護(hù)基礎(chǔ),主要給出了拓?fù)渚S護(hù)全新的定義,并指出拓?fù)渚S護(hù)設(shè)計目標(biāo)。第2 節(jié)設(shè)計了一個拓?fù)渚S護(hù)通用模型,并對模型中的觸發(fā)標(biāo)準(zhǔn)和維護(hù)策略進(jìn)行了詳細(xì)描述。第3 節(jié)總結(jié)了目前有關(guān)拓?fù)渚S護(hù)研究工作,并進(jìn)行了比較分析。第4 節(jié)分析了當(dāng)前研究中的不足,并指出拓?fù)渚S護(hù)技術(shù)的發(fā)展方向。最后對全文進(jìn)行了總結(jié)。
1 拓?fù)渚S護(hù)基礎(chǔ)
無線傳感器網(wǎng)絡(luò)拓?fù)淇刂朴蓛刹糠纸M成,即拓?fù)錁?gòu)建和拓?fù)渚S護(hù)。一旦建立起最初的網(wǎng)絡(luò)優(yōu)化拓?fù),網(wǎng)絡(luò)開始執(zhí)行它所指定的任務(wù)。由于網(wǎng)絡(luò)任務(wù)所包含的每一個行為如感測、數(shù)據(jù)處理和傳輸?shù)榷夹枰哪芰浚虼穗S著時間的推移,當(dāng)前的網(wǎng)絡(luò)拓?fù)洳辉偬幱谧顑?yōu)運行狀態(tài),因此需要對其進(jìn)行維護(hù)使其重新保持最優(yōu)或接近最優(yōu)狀態(tài)。
1.1 拓?fù)渚S護(hù)定義
無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂瓶梢钥醋饕粋重復(fù)的過程,如圖1 所示。首先,對所有無線傳感器網(wǎng)絡(luò)都有一個拓?fù)涑跏蓟A段。在該階段,每個節(jié)點用其最大發(fā)射功率發(fā)射來建立初始拓?fù)洹T诔跏蓟A段后,通過運行不同的算法或協(xié)議來對初始拓?fù)溥M(jìn)行優(yōu)化,并最終構(gòu)建一個優(yōu)化拓?fù),該階段稱之為拓?fù)錁?gòu)建。一旦拓?fù)錁?gòu)建階段建立起優(yōu)化網(wǎng)絡(luò)拓?fù)洌負(fù)渚S護(hù)階段必須開始工作。
在拓?fù)渚S護(hù)階段,實時監(jiān)測當(dāng)前拓?fù)錉顟B(tài),并在適當(dāng)?shù)臅r候觸發(fā)拓?fù)浠謴?fù)或重構(gòu)過程。從圖1 中可見,在網(wǎng)絡(luò)的生命周期內(nèi),拓?fù)渚S護(hù)周期運行,直到網(wǎng)絡(luò)死亡。目前,對拓?fù)渚S護(hù)進(jìn)行定義的文獻(xiàn)很少,文獻(xiàn)[8]對拓?fù)渚S護(hù)進(jìn)行了簡單定義,指出“拓?fù)渚S護(hù)是指當(dāng)網(wǎng)絡(luò)當(dāng)前工作的拓?fù)浣Y(jié)構(gòu)不是最優(yōu)化的拓?fù)浣Y(jié)構(gòu)時,及時通過修復(fù)、切換或重構(gòu)新的網(wǎng)絡(luò)拓?fù),使網(wǎng)絡(luò)達(dá)到預(yù)先設(shè)定的性質(zhì),延長網(wǎng)絡(luò)的生命期”.
該定義沒有指出拓?fù)渚S護(hù)運行的時間、所采取的維護(hù)方式,特別是定義中提到使拓?fù)溥_(dá)到或接近最優(yōu)以及達(dá)到預(yù)先設(shè)定的性質(zhì),卻沒有指出是哪個具體階段的最優(yōu)或性質(zhì),因為隨著網(wǎng)絡(luò)的運行,網(wǎng)絡(luò)的最優(yōu)狀態(tài)和性質(zhì)也在發(fā)生變化。所以,本文對拓?fù)渚S護(hù)進(jìn)行了比較嚴(yán)謹(jǐn)?shù)亩x,即拓?fù)渚S護(hù)是一個周期性的過程,在每個周期中它由不同的觸發(fā)標(biāo)準(zhǔn)(如時間,能量,節(jié)點故障等)觸發(fā),通過盡可能多地輪換節(jié)點角色或重新運行拓?fù)錁?gòu)建過程或調(diào)用專用維護(hù)算法來修復(fù)或重構(gòu)網(wǎng)絡(luò)拓?fù),均衡網(wǎng)絡(luò)能量消耗,使新的拓?fù)涑蔀楫?dāng)前最優(yōu)或接近當(dāng)前最優(yōu)狀態(tài),并最終延長網(wǎng)絡(luò)的生命周期。
1.2 設(shè)計目標(biāo)
拓?fù)渚S護(hù)和其它傳感器網(wǎng)絡(luò)技術(shù)一樣,其主要目的是延長網(wǎng)絡(luò)的生命周期。此外,傳感器網(wǎng)絡(luò)被構(gòu)建用來實現(xiàn)某些任務(wù),如執(zhí)行傳感和傳輸傳感數(shù)據(jù),因此一個或多個服務(wù)質(zhì)量目標(biāo)如保持傳感覆蓋以及保持網(wǎng)絡(luò)連通等也通常被考慮。
而且,無線傳感器網(wǎng)絡(luò)的應(yīng)用不同則導(dǎo)致其底層網(wǎng)絡(luò)的拓?fù)渚S護(hù)設(shè)計目標(biāo)不同或目標(biāo)優(yōu)先次序不同。因此,本文接下來只介紹拓?fù)渚S護(hù)主要考慮的設(shè)計目標(biāo)。
(1)網(wǎng)絡(luò)生命周期
網(wǎng)絡(luò)生命周期已經(jīng)以不同方式被定義,如基于節(jié)點數(shù)、基于傳感覆蓋以及網(wǎng)絡(luò)連通以及可擴(kuò)展的網(wǎng)絡(luò)生命周期。
拓?fù)渚S護(hù)是延長網(wǎng)絡(luò)生命周期十分有效的技術(shù),如拓?fù)渚S護(hù)協(xié)議SPAN和CCP 通過關(guān)閉冗余節(jié)點并維持一個節(jié)點子集處于工作狀態(tài)來提高無線傳感器網(wǎng)絡(luò)的生命周期。然而,最大化網(wǎng)絡(luò)生命周期是一個十分復(fù)雜的問題,它一直是拓?fù)渚S護(hù)研究的主要目標(biāo)。
(2)覆蓋和連通
覆蓋和連通是無線傳感器網(wǎng)絡(luò)拓?fù)渚S護(hù)的基本問題,拓?fù)渚S護(hù)在對原有的優(yōu)化拓?fù)溥M(jìn)行恢復(fù)、切換或重構(gòu)的過程中,必須保持原有拓?fù)涞母采w或連通。
(3)安全和故障容忍
拓?fù)渚S護(hù)過程中,一些傳感器節(jié)點由于能量耗盡、物理損壞或環(huán)境干擾可能會失靈或發(fā)生故障,而這些傳感器節(jié)點的失效并不影響拓?fù)渚S護(hù)的整體任務(wù)。如文獻(xiàn)[12]中提出一個故障容忍的自組織方法來維護(hù)一個覆蓋和連通的骨干網(wǎng)絡(luò)。此外,無線傳感器的實際應(yīng)用中存在各種類型的惡意行為和攻擊[13],因此,安全也是拓?fù)渚S護(hù)的一個重要目標(biāo)。
(4)能量效率和收斂時間
與無線傳感器網(wǎng)絡(luò)其它功能一樣,拓?fù)渚S護(hù)算法必須是能量有效的。也就是說拓?fù)渚S護(hù)算法應(yīng)該具有低的計算復(fù)雜度和低的報文開銷。此外,在拓?fù)渚S護(hù)過程中,當(dāng)前的拓?fù)鋵⒈灰粋新的拓?fù)淙〈,因此在新拓(fù)浔患せ钪g有一個轉(zhuǎn)換時間,該時間應(yīng)該盡可能小。
(5)能量均衡和可擴(kuò)展性
拓?fù)渚S護(hù)技術(shù)應(yīng)該盡量在網(wǎng)絡(luò)的所有節(jié)點間均衡地分布能量消耗。另外,部署在興趣或目標(biāo)區(qū)域的傳感器節(jié)點可能成百上千甚至上萬。拓?fù)渚S護(hù)協(xié)議或算法應(yīng)該能在不同數(shù)量級節(jié)點的網(wǎng)絡(luò)中運行。
2 拓?fù)渚S護(hù)模型
目前,并沒有文獻(xiàn)對拓?fù)渚S護(hù)模型進(jìn)行描述。為了更好的理解拓?fù)渚S護(hù)的運行過程及其特點,本文設(shè)計了一個通用的拓?fù)渚S護(hù)模型,如圖2 所示。從圖中可見,拓?fù)渚S護(hù)是一個周期的過程,每個周期中從網(wǎng)絡(luò)的當(dāng)前拓?fù)溟_始,經(jīng)過拓?fù)渚S護(hù)過程生成一個優(yōu)化的拓?fù)洌芷谶\行,直到網(wǎng)絡(luò)死亡。
從上圖可見,每個拓?fù)渚S護(hù)周期,經(jīng)由觸發(fā)器和決策器。
其中觸發(fā)器主要根據(jù)設(shè)計的觸發(fā)標(biāo)準(zhǔn)如時間、能量或節(jié)點故障等來觸發(fā)拓?fù)渚S護(hù)過程。決策器用來選擇拓?fù)渚S護(hù)策略。
接下來對該模型進(jìn)行詳細(xì)描述。
(1)觸發(fā)器
觸發(fā)器負(fù)責(zé)周期地觸發(fā)當(dāng)前網(wǎng)絡(luò)拓?fù)涞木S護(hù)過程,其對拓?fù)渚S護(hù)的性能具有重要的影響。因為如果提前觸發(fā),則由于頻繁運行拓?fù)渚S護(hù)協(xié)議或算法而消耗不必要的能量,而滯后觸發(fā),則將導(dǎo)致網(wǎng)絡(luò)可能以次優(yōu)甚至不連通狀態(tài)運行,降低甚至無法實現(xiàn)網(wǎng)絡(luò)的服務(wù)質(zhì)量。常見的觸發(fā)標(biāo)準(zhǔn)有:
時間:網(wǎng)絡(luò)運行一段時間后觸發(fā)拓?fù)渚S護(hù),該時間的大小通常是固定且預(yù)先定義,通常由一個定時器來完成。
SPAN基于時間來觸發(fā)網(wǎng)絡(luò)中協(xié)調(diào)器節(jié)點的更新過程,從而實現(xiàn)骨干網(wǎng)絡(luò)的拓?fù)渚S護(hù)。
能量:鑒于無線傳感器設(shè)備的能量限制,當(dāng)節(jié)點的能量級別低于某個閾值時觸發(fā)拓?fù)渚S護(hù)是很有必要的。LPH算法中,當(dāng)節(jié)點的剩余能量E(i)低于平均剩余能量Eavr 時,觸發(fā)簇內(nèi)拓?fù)渚S護(hù)過程。CLTC算法中,當(dāng)簇頭節(jié)點的能量降到門限值M 時,觸發(fā)簇內(nèi)拓?fù)渚S護(hù)過程。而Poly算法中,當(dāng)網(wǎng)絡(luò)的整體能量降低10%時觸發(fā)拓?fù)渚S護(hù)過程。
節(jié)點故障:當(dāng)網(wǎng)絡(luò)中一個或一些節(jié)點故障時,觸發(fā)拓?fù)渚S護(hù)。如SMSS算法中,當(dāng)節(jié)點u 發(fā)現(xiàn)某個節(jié)點m 故障時,它將檢查m 是否為其確定的鄰節(jié)點,如果是則重新運行拓?fù)錁?gòu)建算法來維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。EETMS算法中,一旦網(wǎng)絡(luò)發(fā)現(xiàn)故障節(jié)點,觸發(fā)局部拓?fù)渚S護(hù)過程。
網(wǎng)絡(luò)密度:采用網(wǎng)絡(luò)的節(jié)點度或者一些重要節(jié)點的節(jié)點度來觸發(fā)拓?fù)渚S護(hù)過程。AFECA提出的自適應(yīng)精度節(jié)能算法使用鄰居密度來觸發(fā)拓?fù)渚S護(hù)過程。
此外,這些觸發(fā)條件也可任意組合用來觸發(fā)拓?fù)渚S護(hù)過程,如基于能量和節(jié)點故障,或者時間和能量等。此外,其它的網(wǎng)絡(luò)參數(shù)也可作為觸發(fā)標(biāo)準(zhǔn),如鏈路失效、頻繁丟包以及擁塞和長路由路徑等。
(2)決策器
決策器主要確定采用何種策略來維護(hù)當(dāng)前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),它是拓?fù)渚S護(hù)的核心。拓?fù)渚S護(hù)策略可以分為兩種,一種是基于角色輪換的拓?fù)渚S護(hù)策略,也就是說通過對網(wǎng)絡(luò)中節(jié)點的角色-如睡眠/工作、簇頭/非簇頭等進(jìn)行切換來節(jié)約能量,實現(xiàn)延長網(wǎng)絡(luò)生命周期的目的。另一種是基于拓?fù)渲貥?gòu)的拓?fù)渚S護(hù)策略,其實質(zhì)是運行拓?fù)錁?gòu)建階段的算法或?qū)iT的拓?fù)渚S護(hù)算法與協(xié)議來維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。
在基于角色輪換的拓?fù)渚S護(hù)策略中,首先要明確網(wǎng)絡(luò)中每個節(jié)點所能扮演的角色。每個節(jié)點的角色遷移與拓?fù)渚S護(hù)協(xié)議或算法特點和設(shè)計密切相關(guān),確定節(jié)點所處角色的因素包括節(jié)點密度、位置、通信流量、丟包率、時間以及外部環(huán)境條件等。如節(jié)點當(dāng)前為角色1,當(dāng)某個事件發(fā)生,則節(jié)點進(jìn)行相應(yīng)測試以決定是否進(jìn)入角色2還是繼續(xù)處于角色1.
而基于拓?fù)渲貥?gòu)的拓?fù)渚S護(hù)策略中,主要是重新調(diào)用拓?fù)錁?gòu)建階段的算法或?qū)iT的拓?fù)渚S護(hù)算法。因此,調(diào)用算法的頻率是關(guān)鍵。一旦觸發(fā)器觸發(fā)拓?fù)渚S護(hù)過程,拓?fù)渚S護(hù)策略則應(yīng)該綜合考慮網(wǎng)絡(luò)的相關(guān)性能,決定是否調(diào)用相關(guān)算法或協(xié)議,以均衡網(wǎng)絡(luò)能量消耗并最終延長網(wǎng)絡(luò)生命周期。
此外,決策器還可根據(jù)網(wǎng)絡(luò)運行情況在不同的階段采用不同的維護(hù)策略來維護(hù)當(dāng)前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。無論是基于角色轉(zhuǎn)換還是基于拓?fù)渲貥?gòu)的拓?fù)渚S護(hù)技術(shù),決策器還負(fù)責(zé)對生命周期的監(jiān)測。也就是說,在網(wǎng)絡(luò)的生命周期內(nèi),決策器根據(jù)維護(hù)策略周期性地對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行維護(hù),而一旦網(wǎng)絡(luò)的生命周期結(jié)束,決策器停止維護(hù)過程,并宣告網(wǎng)絡(luò)死亡
來源:電子愛好者博客