摘 要: 拓?fù)渚S護(hù)對(duì)無(wú)線傳感器網(wǎng)絡(luò)的運(yùn)行至關(guān)重要,,它旨在通過(guò)輪換節(jié)點(diǎn)角色、調(diào)用拓?fù)錁?gòu)建或維護(hù)算法來(lái)修復(fù),、重構(gòu)當(dāng)前的拓?fù)浣Y(jié)構(gòu)以提高網(wǎng)絡(luò)的生命周期,。首先對(duì)拓?fù)渚S護(hù)進(jìn)行了定義,描述了拓?fù)渚S護(hù)的設(shè)計(jì)目標(biāo),,并設(shè)計(jì)了一個(gè)拓?fù)渚S護(hù)通用模型,。然后闡述了拓?fù)渚S護(hù)技術(shù)的研究進(jìn)展,并對(duì)其中有代表性的算法進(jìn)行了比較分析,。最后指出了目前拓?fù)渚S護(hù)研究中存在的問(wèn)題及其發(fā)展趨勢(shì)。
無(wú)線傳感器網(wǎng)絡(luò)由于具有低功耗,、低成本以及分布式和自組織等特點(diǎn)已被廣泛應(yīng)用于軍事國(guó)防、工農(nóng)業(yè)控制,、環(huán)境監(jiān)測(cè),、生物醫(yī)療和搶險(xiǎn)救災(zāi)等領(lǐng)域,。通常,,一個(gè)無(wú)線傳感器網(wǎng)絡(luò)由成百上千傳感器節(jié)點(diǎn)組成,每個(gè)節(jié)點(diǎn)具有感知當(dāng)前環(huán)境,、通過(guò)廣播與鄰近節(jié)點(diǎn)進(jìn)行通信以及對(duì)收集的信息執(zhí)行本地計(jì)算的能力。但是,,這些能力對(duì)每個(gè)節(jié)點(diǎn)來(lái)說(shuō)都很有限,,尤其是節(jié)點(diǎn)的能量受限嚴(yán)重限制了網(wǎng)絡(luò)的生命周期,,從而影響了網(wǎng)絡(luò)的服務(wù)質(zhì)量和進(jìn)一步應(yīng)用。因此,,近幾年來(lái),許多研究人員對(duì)無(wú)線傳感器網(wǎng)絡(luò)的節(jié)能方面進(jìn)行了大量的研究,,從擁塞控制到數(shù)據(jù)壓縮,從睡眠調(diào)度到拓?fù)淇刂?。目的是盡可能多的節(jié)省能量,最大化網(wǎng)絡(luò)生命周期,。
拓?fù)淇刂谱鳛闊o(wú)線傳感器網(wǎng)絡(luò)的一種關(guān)鍵節(jié)能技術(shù),,通常在保持網(wǎng)絡(luò)重要特性如連通和覆蓋的前提下改變、簡(jiǎn)化或優(yōu)化網(wǎng)絡(luò)的拓?fù)鋪?lái)節(jié)省能量,。而且,,拓?fù)淇刂菩纬傻牧己镁W(wǎng)絡(luò)拓?fù)淠軌蛱岣呗酚蓞f(xié)議和MAC 協(xié)議的效率,。然而,拓?fù)淇刂仆ǔ1灰暈橐粋€(gè)單一過(guò)程,,它并未包括對(duì)網(wǎng)絡(luò)拓?fù)涞木S護(hù),,這影響拓?fù)淇刂扑惴ǖ姆诸?。目前的分類都局限于如何?gòu)建網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),而忽略拓?fù)淇刂浦械耐負(fù)渚S護(hù),。
雖然對(duì)拓?fù)渚S護(hù)進(jìn)行了簡(jiǎn)單定義,,并根據(jù)目標(biāo)優(yōu)化拓?fù)錁?gòu)建的時(shí)間將拓?fù)渚S護(hù)技術(shù)分為靜態(tài),、動(dòng)態(tài)和混合拓?fù)渚S護(hù)。但文中并未對(duì)拓?fù)渚S護(hù)進(jìn)行系統(tǒng)闡述,,而對(duì)拓?fù)渚S護(hù)的定義又不嚴(yán)謹(jǐn),,對(duì)拓?fù)渚S護(hù)技術(shù)的分類也與當(dāng)前研究現(xiàn)狀不符,因?yàn)楝F(xiàn)有研究中基本上沒(méi)有文中所提到的靜態(tài)和混合拓?fù)渚S護(hù)算法或協(xié)議,。因此,為了更深入的對(duì)無(wú)線傳感器網(wǎng)絡(luò)中的拓?fù)渚S護(hù)技術(shù)進(jìn)行研究,,本文從拓?fù)渚S護(hù)定義及模型,,拓?fù)渚S護(hù)設(shè)計(jì)目標(biāo),以及當(dāng)前的研究現(xiàn)狀和存在的問(wèn)題與發(fā)展方向等方面對(duì)拓?fù)渚S護(hù)進(jìn)行了闡述,。第1 節(jié)描述了無(wú)線傳感器網(wǎng)絡(luò)拓?fù)渚S護(hù)基礎(chǔ),主要給出了拓?fù)渚S護(hù)全新的定義,,并指出拓?fù)渚S護(hù)設(shè)計(jì)目標(biāo),。第2 節(jié)設(shè)計(jì)了一個(gè)拓?fù)渚S護(hù)通用模型,并對(duì)模型中的觸發(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ā)展方向,。最后對(duì)全文進(jìn)行了總結(jié)。
1 拓?fù)渚S護(hù)基礎(chǔ)
無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂朴蓛刹糠纸M成,,即拓?fù)錁?gòu)建和拓?fù)渚S護(hù)。一旦建立起最初的網(wǎng)絡(luò)優(yōu)化拓?fù)?,網(wǎng)絡(luò)開(kāi)始執(zhí)行它所指定的任務(wù)。由于網(wǎng)絡(luò)任務(wù)所包含的每一個(gè)行為如感測(cè),、數(shù)據(jù)處理和傳輸?shù)榷夹枰哪芰浚虼穗S著時(shí)間的推移,,當(dāng)前的網(wǎng)絡(luò)拓?fù)洳辉偬幱谧顑?yōu)運(yùn)行狀態(tài),因此需要對(duì)其進(jìn)行維護(hù)使其重新保持最優(yōu)或接近最優(yōu)狀態(tài),。
1.1 拓?fù)渚S護(hù)定義
無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂瓶梢钥醋饕粋€(gè)重復(fù)的過(guò)程,,如圖1 所示。首先,,對(duì)所有無(wú)線傳感器網(wǎng)絡(luò)都有一個(gè)拓?fù)涑跏蓟A段,。在該階段,每個(gè)節(jié)點(diǎn)用其最大發(fā)射功率發(fā)射來(lái)建立初始拓?fù)?。在初始化階段后,通過(guò)運(yùn)行不同的算法或協(xié)議來(lái)對(duì)初始拓?fù)溥M(jìn)行優(yōu)化,,并最終構(gòu)建一個(gè)優(yōu)化拓?fù)?,該階段稱之為拓?fù)錁?gòu)建,。一旦拓?fù)錁?gòu)建階段建立起優(yōu)化網(wǎng)絡(luò)拓?fù)?,拓?fù)渚S護(hù)階段必須開(kāi)始工作。
在拓?fù)渚S護(hù)階段,,實(shí)時(shí)監(jiān)測(cè)當(dāng)前拓?fù)錉顟B(tài),,并在適當(dāng)?shù)臅r(shí)候觸發(fā)拓?fù)浠謴?fù)或重構(gòu)過(guò)程,。從圖1 中可見(jiàn),在網(wǎng)絡(luò)的生命周期內(nèi),,拓?fù)渚S護(hù)周期運(yùn)行,,直到網(wǎng)絡(luò)死亡。目前,,對(duì)拓?fù)渚S護(hù)進(jìn)行定義的文獻(xiàn)很少,,文獻(xiàn)[8]對(duì)拓?fù)渚S護(hù)進(jìn)行了簡(jiǎn)單定義,,指出“拓?fù)渚S護(hù)是指當(dāng)網(wǎng)絡(luò)當(dāng)前工作的拓?fù)浣Y(jié)構(gòu)不是最優(yōu)化的拓?fù)浣Y(jié)構(gòu)時(shí),,及時(shí)通過(guò)修復(fù),、切換或重構(gòu)新的網(wǎng)絡(luò)拓?fù)?,使網(wǎng)絡(luò)達(dá)到預(yù)先設(shè)定的性質(zhì),延長(zhǎng)網(wǎng)絡(luò)的生命期”,。
該定義沒(méi)有指出拓?fù)渚S護(hù)運(yùn)行的時(shí)間,、所采取的維護(hù)方式,,特別是定義中提到使拓?fù)溥_(dá)到或接近最優(yōu)以及達(dá)到預(yù)先設(shè)定的性質(zhì),卻沒(méi)有指出是哪個(gè)具體階段的最優(yōu)或性質(zhì),,因?yàn)殡S著網(wǎng)絡(luò)的運(yùn)行,,網(wǎng)絡(luò)的最優(yōu)狀態(tài)和性質(zhì)也在發(fā)生變化。所以,,本文對(duì)拓?fù)渚S護(hù)進(jìn)行了比較嚴(yán)謹(jǐn)?shù)亩x,,即拓?fù)渚S護(hù)是一個(gè)周期性的過(guò)程,,在每個(gè)周期中它由不同的觸發(fā)標(biāo)準(zhǔn)(如時(shí)間,能量,,節(jié)點(diǎn)故障等)觸發(fā),,通過(guò)盡可能多地輪換節(jié)點(diǎn)角色或重新運(yùn)行拓?fù)錁?gòu)建過(guò)程或調(diào)用專用維護(hù)算法來(lái)修復(fù)或重構(gòu)網(wǎng)絡(luò)拓?fù)洌饩W(wǎng)絡(luò)能量消耗,,使新的拓?fù)涑蔀楫?dāng)前最優(yōu)或接近當(dāng)前最優(yōu)狀態(tài),,并最終延長(zhǎng)網(wǎng)絡(luò)的生命周期。
1.2 設(shè)計(jì)目標(biāo)
拓?fù)渚S護(hù)和其它傳感器網(wǎng)絡(luò)技術(shù)一樣,,其主要目的是延長(zhǎng)網(wǎng)絡(luò)的生命周期,。此外,傳感器網(wǎng)絡(luò)被構(gòu)建用來(lái)實(shí)現(xiàn)某些任務(wù),,如執(zhí)行傳感和傳輸傳感數(shù)據(jù),,因此一個(gè)或多個(gè)服務(wù)質(zhì)量目標(biāo)如保持傳感覆蓋以及保持網(wǎng)絡(luò)連通等也通常被考慮。
而且,,無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用不同則導(dǎo)致其底層網(wǎng)絡(luò)的拓?fù)渚S護(hù)設(shè)計(jì)目標(biāo)不同或目標(biāo)優(yōu)先次序不同,。因此,本文接下來(lái)只介紹拓?fù)渚S護(hù)主要考慮的設(shè)計(jì)目標(biāo),。
?。?)網(wǎng)絡(luò)生命周期
網(wǎng)絡(luò)生命周期已經(jīng)以不同方式被定義,如基于節(jié)點(diǎn)數(shù),、基于傳感覆蓋以及網(wǎng)絡(luò)連通以及可擴(kuò)展的網(wǎng)絡(luò)生命周期,。
拓?fù)渚S護(hù)是延長(zhǎng)網(wǎng)絡(luò)生命周期十分有效的技術(shù),如拓?fù)渚S護(hù)協(xié)議SPAN和CCP 通過(guò)關(guān)閉冗余節(jié)點(diǎn)并維持一個(gè)節(jié)點(diǎn)子集處于工作狀態(tài)來(lái)提高無(wú)線傳感器網(wǎng)絡(luò)的生命周期,。然而,,最大化網(wǎng)絡(luò)生命周期是一個(gè)十分復(fù)雜的問(wèn)題,它一直是拓?fù)渚S護(hù)研究的主要目標(biāo),。
?。?)覆蓋和連通
覆蓋和連通是無(wú)線傳感器網(wǎng)絡(luò)拓?fù)渚S護(hù)的基本問(wèn)題,拓?fù)渚S護(hù)在對(duì)原有的優(yōu)化拓?fù)溥M(jìn)行恢復(fù),、切換或重構(gòu)的過(guò)程中,,必須保持原有拓?fù)涞母采w或連通。
?。?)安全和故障容忍
拓?fù)渚S護(hù)過(guò)程中,,一些傳感器節(jié)點(diǎn)由于能量耗盡、物理?yè)p壞或環(huán)境干擾可能會(huì)失靈或發(fā)生故障,而這些傳感器節(jié)點(diǎn)的失效并不影響拓?fù)渚S護(hù)的整體任務(wù),。如文獻(xiàn)[12]中提出一個(gè)故障容忍的自組織方法來(lái)維護(hù)一個(gè)覆蓋和連通的骨干網(wǎng)絡(luò),。此外,無(wú)線傳感器的實(shí)際應(yīng)用中存在各種類型的惡意行為和攻擊[13],,因此,,安全也是拓?fù)渚S護(hù)的一個(gè)重要目標(biāo)。
?。?)能量效率和收斂時(shí)間
與無(wú)線傳感器網(wǎng)絡(luò)其它功能一樣,,拓?fù)渚S護(hù)算法必須是能量有效的。也就是說(shuō)拓?fù)渚S護(hù)算法應(yīng)該具有低的計(jì)算復(fù)雜度和低的報(bào)文開(kāi)銷,。此外,,在拓?fù)渚S護(hù)過(guò)程中,當(dāng)前的拓?fù)鋵⒈灰粋€(gè)新的拓?fù)淙〈?,因此在新拓?fù)浔患せ钪g有一個(gè)轉(zhuǎn)換時(shí)間,,該時(shí)間應(yīng)該盡可能小。
?。?)能量均衡和可擴(kuò)展性
拓?fù)渚S護(hù)技術(shù)應(yīng)該盡量在網(wǎng)絡(luò)的所有節(jié)點(diǎn)間均衡地分布能量消耗,。另外,部署在興趣或目標(biāo)區(qū)域的傳感器節(jié)點(diǎn)可能成百上千甚至上萬(wàn),。拓?fù)渚S護(hù)協(xié)議或算法應(yīng)該能在不同數(shù)量級(jí)節(jié)點(diǎn)的網(wǎng)絡(luò)中運(yùn)行,。
2 拓?fù)渚S護(hù)模型
目前,并沒(méi)有文獻(xiàn)對(duì)拓?fù)渚S護(hù)模型進(jìn)行描述,。為了更好的理解拓?fù)渚S護(hù)的運(yùn)行過(guò)程及其特點(diǎn),,本文設(shè)計(jì)了一個(gè)通用的拓?fù)渚S護(hù)模型,如圖2 所示,。從圖中可見(jiàn),,拓?fù)渚S護(hù)是一個(gè)周期的過(guò)程,,每個(gè)周期中從網(wǎng)絡(luò)的當(dāng)前拓?fù)溟_(kāi)始,,經(jīng)過(guò)拓?fù)渚S護(hù)過(guò)程生成一個(gè)優(yōu)化的拓?fù)洌芷谶\(yùn)行,,直到網(wǎng)絡(luò)死亡,。
從上圖可見(jiàn),每個(gè)拓?fù)渚S護(hù)周期,,經(jīng)由觸發(fā)器和決策器,。
其中觸發(fā)器主要根據(jù)設(shè)計(jì)的觸發(fā)標(biāo)準(zhǔn)如時(shí)間、能量或節(jié)點(diǎn)故障等來(lái)觸發(fā)拓?fù)渚S護(hù)過(guò)程,。決策器用來(lái)選擇拓?fù)渚S護(hù)策略,。
接下來(lái)對(duì)該模型進(jìn)行詳細(xì)描述。
(1)觸發(fā)器
觸發(fā)器負(fù)責(zé)周期地觸發(fā)當(dāng)前網(wǎng)絡(luò)拓?fù)涞木S護(hù)過(guò)程,,其對(duì)拓?fù)渚S護(hù)的性能具有重要的影響,。因?yàn)槿绻崆坝|發(fā),則由于頻繁運(yùn)行拓?fù)渚S護(hù)協(xié)議或算法而消耗不必要的能量,,而滯后觸發(fā),,則將導(dǎo)致網(wǎng)絡(luò)可能以次優(yōu)甚至不連通狀態(tài)運(yùn)行,降低甚至無(wú)法實(shí)現(xiàn)網(wǎng)絡(luò)的服務(wù)質(zhì)量,。常見(jiàn)的觸發(fā)標(biāo)準(zhǔn)有:
時(shí)間:網(wǎng)絡(luò)運(yùn)行一段時(shí)間后觸發(fā)拓?fù)渚S護(hù),,該時(shí)間的大小通常是固定且預(yù)先定義,通常由一個(gè)定時(shí)器來(lái)完成,。
SPAN基于時(shí)間來(lái)觸發(fā)網(wǎng)絡(luò)中協(xié)調(diào)器節(jié)點(diǎn)的更新過(guò)程,,從而實(shí)現(xiàn)骨干網(wǎng)絡(luò)的拓?fù)渚S護(hù)。
能量:鑒于無(wú)線傳感器設(shè)備的能量限制,,當(dāng)節(jié)點(diǎn)的能量級(jí)別低于某個(gè)閾值時(shí)觸發(fā)拓?fù)渚S護(hù)是很有必要的,。LPH算法中,當(dāng)節(jié)點(diǎn)的剩余能量E(i)低于平均剩余能量Eavr 時(shí),,觸發(fā)簇內(nèi)拓?fù)渚S護(hù)過(guò)程,。CLTC算法中,當(dāng)簇頭節(jié)點(diǎn)的能量降到門限值M 時(shí),,觸發(fā)簇內(nèi)拓?fù)渚S護(hù)過(guò)程,。而Poly算法中,當(dāng)網(wǎng)絡(luò)的整體能量降低10%時(shí)觸發(fā)拓?fù)渚S護(hù)過(guò)程,。
節(jié)點(diǎn)故障:當(dāng)網(wǎng)絡(luò)中一個(gè)或一些節(jié)點(diǎn)故障時(shí),,觸發(fā)拓?fù)渚S護(hù)。如SMSS算法中,,當(dāng)節(jié)點(diǎn)u 發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)m 故障時(shí),,它將檢查m 是否為其確定的鄰節(jié)點(diǎn),如果是則重新運(yùn)行拓?fù)錁?gòu)建算法來(lái)維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),。EETMS算法中,,一旦網(wǎng)絡(luò)發(fā)現(xiàn)故障節(jié)點(diǎn),觸發(fā)局部拓?fù)渚S護(hù)過(guò)程,。
網(wǎng)絡(luò)密度:采用網(wǎng)絡(luò)的節(jié)點(diǎn)度或者一些重要節(jié)點(diǎn)的節(jié)點(diǎn)度來(lái)觸發(fā)拓?fù)渚S護(hù)過(guò)程,。AFECA提出的自適應(yīng)精度節(jié)能算法使用鄰居密度來(lái)觸發(fā)拓?fù)渚S護(hù)過(guò)程。
此外,,這些觸發(fā)條件也可任意組合用來(lái)觸發(fā)拓?fù)渚S護(hù)過(guò)程,,如基于能量和節(jié)點(diǎn)故障,或者時(shí)間和能量等,。此外,,其它的網(wǎng)絡(luò)參數(shù)也可作為觸發(fā)標(biāo)準(zhǔn),,如鏈路失效、頻繁丟包以及擁塞和長(zhǎng)路由路徑等,。
?。?)決策器
決策器主要確定采用何種策略來(lái)維護(hù)當(dāng)前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),它是拓?fù)渚S護(hù)的核心,。拓?fù)渚S護(hù)策略可以分為兩種,,一種是基于角色輪換的拓?fù)渚S護(hù)策略,也就是說(shuō)通過(guò)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的角色-如睡眠/工作,、簇頭/非簇頭等進(jìn)行切換來(lái)節(jié)約能量,,實(shí)現(xiàn)延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。另一種是基于拓?fù)渲貥?gòu)的拓?fù)渚S護(hù)策略,,其實(shí)質(zhì)是運(yùn)行拓?fù)錁?gòu)建階段的算法或?qū)iT的拓?fù)渚S護(hù)算法與協(xié)議來(lái)維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),。
在基于角色輪換的拓?fù)渚S護(hù)策略中,首先要明確網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)所能扮演的角色,。每個(gè)節(jié)點(diǎn)的角色遷移與拓?fù)渚S護(hù)協(xié)議或算法特點(diǎn)和設(shè)計(jì)密切相關(guān),,確定節(jié)點(diǎn)所處角色的因素包括節(jié)點(diǎn)密度、位置,、通信流量,、丟包率、時(shí)間以及外部環(huán)境條件等,。如節(jié)點(diǎn)當(dāng)前為角色1,,當(dāng)某個(gè)事件發(fā)生,則節(jié)點(diǎn)進(jìn)行相應(yīng)測(cè)試以決定是否進(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ù)過(guò)程,,拓?fù)渚S護(hù)策略則應(yīng)該綜合考慮網(wǎng)絡(luò)的相關(guān)性能,決定是否調(diào)用相關(guān)算法或協(xié)議,,以均衡網(wǎng)絡(luò)能量消耗并最終延長(zhǎng)網(wǎng)絡(luò)生命周期,。
此外,決策器還可根據(jù)網(wǎng)絡(luò)運(yùn)行情況在不同的階段采用不同的維護(hù)策略來(lái)維護(hù)當(dāng)前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),。無(wú)論是基于角色轉(zhuǎn)換還是基于拓?fù)渲貥?gòu)的拓?fù)渚S護(hù)技術(shù),,決策器還負(fù)責(zé)對(duì)生命周期的監(jiān)測(cè)。也就是說(shuō),,在網(wǎng)絡(luò)的生命周期內(nèi),決策器根據(jù)維護(hù)策略周期性地對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行維護(hù),,而一旦網(wǎng)絡(luò)的生命周期結(jié)束,,決策器停止維護(hù)過(guò)程,并宣告網(wǎng)絡(luò)死亡。
3 拓?fù)渚S護(hù)研究現(xiàn)狀
目前專門的拓?fù)渚S護(hù)技術(shù)研究還比較少,,但相關(guān)研究結(jié)果表明優(yōu)化的拓?fù)渚S護(hù)能有效地節(jié)省能量并延長(zhǎng)網(wǎng)絡(luò)生命周期,,同時(shí)保持網(wǎng)絡(luò)的基本屬性覆蓋或連通。本節(jié)中,,根據(jù)拓?fù)渚S護(hù)決策器所選維護(hù)策略將現(xiàn)有的拓?fù)渚S護(hù)技術(shù)分為基于角色輪換,、基于拓?fù)渲貥?gòu)和混合的拓?fù)渚S護(hù)。
3.1 基于角色輪換的拓?fù)渚S護(hù)
基于角色轉(zhuǎn)換的拓?fù)渚S護(hù)技術(shù),,通過(guò)輪換節(jié)點(diǎn)的角色來(lái)對(duì)拓?fù)溥M(jìn)行維護(hù),。節(jié)點(diǎn)的角色可以從多方面描述,如睡眠/工作,、簇頭/非簇頭,、協(xié)調(diào)器/非協(xié)調(diào)器等,且節(jié)點(diǎn)的角色可以相互轉(zhuǎn)換,。目前研究中,,輪換的節(jié)點(diǎn)角色主要有兩種,一種是簇頭/非簇頭,。它通過(guò)輪換簇內(nèi)簇頭節(jié)點(diǎn)來(lái)均衡簇內(nèi)能量消耗,,優(yōu)化局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。LEACH是一種典型的角色輪換拓?fù)渚S護(hù)算法,,通過(guò)概率隨機(jī)輪換簇頭,,使網(wǎng)絡(luò)中節(jié)點(diǎn)等概率擔(dān)任簇頭,有效地節(jié)省節(jié)點(diǎn)能量,。
另一種節(jié)點(diǎn)角色輪換為睡眠/工作,,它通過(guò)調(diào)度那些未參與通信的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)來(lái)節(jié)約能量,實(shí)現(xiàn)延長(zhǎng)網(wǎng)絡(luò)生命周期的目的,。如SPAN通過(guò)維護(hù)組成骨干基礎(chǔ)架構(gòu)的節(jié)點(diǎn)來(lái)保持網(wǎng)絡(luò)的連通和轉(zhuǎn)發(fā)能力,。MESH-CDS中,最大獨(dú)立集中節(jié)點(diǎn)故障時(shí),,通過(guò)轉(zhuǎn)換節(jié)點(diǎn)角色來(lái)修復(fù)最大獨(dú)立集并維護(hù)一個(gè)連通的骨干網(wǎng)絡(luò),。此外,CCP通過(guò)對(duì)節(jié)點(diǎn)角色的輪換維護(hù)網(wǎng)絡(luò)拓?fù)涞母采w和連通,,它是一種典型和有重要影響的基于角色轉(zhuǎn)換的拓?fù)渚S護(hù)協(xié)議,。其基本思想主要是通過(guò)保持一個(gè)足夠大的工作節(jié)點(diǎn)子集來(lái)維護(hù)網(wǎng)絡(luò)k-覆蓋。
在該算法中,,每個(gè)節(jié)點(diǎn)扮演兩個(gè)角色,,即睡眠節(jié)點(diǎn)或工作節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)利用ks-覆蓋規(guī)則和接收其鄰居節(jié)點(diǎn)的HELLO報(bào)文信息來(lái)進(jìn)行本地決策以確定是否需要進(jìn)行角色輪換,。
CCP能夠?qū)⒕W(wǎng)絡(luò)配置到指定的覆蓋度與連通度,,并通過(guò)角色輪換來(lái)維護(hù)網(wǎng)絡(luò)的覆蓋和連通,,其可靈活地應(yīng)用于不同的網(wǎng)絡(luò)環(huán)境。但是,,CCP 需要較為精確的位置信息,,并且當(dāng)發(fā)射半徑小于感知半徑的2倍時(shí),不能保證網(wǎng)絡(luò)的連通性,。
由上可見(jiàn),,基于角色輪換的技術(shù)通過(guò)調(diào)度那些未參與通信的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)或選擇剩余能量多的節(jié)點(diǎn)擔(dān)任簇頭來(lái)維護(hù)網(wǎng)絡(luò)連通和覆蓋。睡眠節(jié)點(diǎn)或非簇頭節(jié)點(diǎn)消耗的能量很小,,且它們比工作節(jié)點(diǎn)或簇頭節(jié)點(diǎn)的數(shù)量大得多,,所以網(wǎng)絡(luò)的能量消耗性能十分優(yōu)越。而且,,通常算法僅需要局部信息,,通過(guò)本地進(jìn)行決策,計(jì)算復(fù)雜度低,。然而,,基于角色輪換的拓?fù)渚S護(hù)技術(shù)僅從局部對(duì)網(wǎng)絡(luò)進(jìn)行維護(hù),不能從網(wǎng)絡(luò)的整體出發(fā),,導(dǎo)致整個(gè)網(wǎng)絡(luò)拓?fù)浞亲顑?yōu)甚至不連通,。
3.2 基于拓?fù)渲貥?gòu)的拓?fù)渚S護(hù)
基于拓?fù)錁?gòu)建的拓?fù)渚S護(hù)技術(shù)通常周期性調(diào)用拓?fù)錁?gòu)建過(guò)程或?qū)S玫木S護(hù)算法來(lái)重構(gòu)網(wǎng)絡(luò)的拓?fù)洹H鏒KM協(xié)議,,當(dāng)節(jié)點(diǎn)密度| SNS | k 時(shí)運(yùn)行拓?fù)渚S護(hù)過(guò)程,,有效地恢復(fù)和維護(hù)網(wǎng)絡(luò)的k -連通。SMSS算法中,,當(dāng)節(jié)點(diǎn)u 發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)m 失效時(shí),,它將檢查m 是否為它確定的鄰節(jié)點(diǎn),如果是,,重新運(yùn)行拓?fù)淇刂扑惴▉?lái)維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),。
EETMS算法中,一旦網(wǎng)絡(luò)發(fā)現(xiàn)故障節(jié)點(diǎn),,觸發(fā)拓?fù)渚S護(hù)過(guò)程,,并最終構(gòu)建一個(gè)能量有效的局部拓?fù)洌移滏溌烽L(zhǎng)度之和最小,。EETMS 是一種典型的專門用于拓?fù)渚S護(hù)的基于拓?fù)渲貥?gòu)的技術(shù),。其思想是僅利用直接的鄰居節(jié)點(diǎn)來(lái)響應(yīng)拓?fù)渚S護(hù)過(guò)程,且節(jié)點(diǎn)將大部分能量花在用來(lái)估量網(wǎng)絡(luò)連通和尋找最小能量拓?fù)?,而不是用于轉(zhuǎn)發(fā)數(shù)據(jù),。
EETMS 算法首先提出了一個(gè)判斷網(wǎng)絡(luò)連通的標(biāo)準(zhǔn)。在一個(gè)二維的歐幾里得空間里,,網(wǎng)絡(luò)拓?fù)溆靡粋€(gè)圖G(V,, E) 表示,,其中V 為節(jié)點(diǎn)集,,節(jié)點(diǎn)個(gè)數(shù)為n .E 為所有邊e(i,, j)的集合,其中e(i,, j) 表示節(jié)點(diǎn)i 和j 彼此互為鄰居,。則網(wǎng)絡(luò)拓?fù)淇捎脠DG 的鄰接矩陣A 表示,且矩陣的每個(gè)元素ai,, j可表示為:
接下來(lái),,令,如果對(duì)于任意的i,, j s 有,, 0 i j s ,則圖G(V,, E) 連通,。因此,維護(hù)算法通過(guò)計(jì)算si,, j 來(lái)構(gòu)建一個(gè)連通的拓?fù)?。?dāng)網(wǎng)絡(luò)運(yùn)行中發(fā)現(xiàn)故障節(jié)點(diǎn)u ,觸發(fā)拓?fù)渚S護(hù)過(guò)程,。此時(shí)故障節(jié)點(diǎn)u 的鄰居集為u ,,節(jié)點(diǎn)數(shù)u m .EETMS能夠維護(hù)網(wǎng)絡(luò)的連通,并確保鏈路長(zhǎng)度之和最小,。但算法中需要構(gòu)建故障節(jié)點(diǎn)的鄰接矩陣,,并根據(jù)該矩陣來(lái)計(jì)算網(wǎng)絡(luò)的連通。在高密度網(wǎng)絡(luò)中,,需要大量的存儲(chǔ)空間和高的計(jì)算復(fù)雜度,。此外,算法中并沒(méi)有描述故障節(jié)點(diǎn)檢測(cè)機(jī)制,,無(wú)法知道拓?fù)渚S護(hù)算法的觸發(fā)頻率,。
總之,基于拓?fù)渲貥?gòu)的拓?fù)渚S護(hù)技術(shù)可能需要多次動(dòng)態(tài)運(yùn)行拓?fù)錁?gòu)建或維護(hù)算法,,通常需要更多的時(shí)間和能量消耗,。然而,拓?fù)錁?gòu)建過(guò)程在它每次運(yùn)行時(shí)通常選擇最優(yōu)或接近最優(yōu)拓?fù)?,從而?dǎo)致生成比基于角色轉(zhuǎn)換拓?fù)渚S護(hù)技術(shù)更好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),。
3.3 混合的拓?fù)渚S護(hù)
混合的拓?fù)渚S護(hù)技術(shù)結(jié)合了基于角色輪換和拓?fù)渲貥?gòu)的拓?fù)渚S護(hù)。該類拓?fù)渚S護(hù)技術(shù)周期性地采用節(jié)點(diǎn)角色轉(zhuǎn)換和拓?fù)渲貥?gòu)策略,。首先,,混合的方法采用角色轉(zhuǎn)換的維護(hù)方法對(duì)網(wǎng)絡(luò)的局部拓?fù)溥M(jìn)行維護(hù),,實(shí)現(xiàn)網(wǎng)絡(luò)一部分(如一個(gè)簇)的優(yōu)化。隨著網(wǎng)絡(luò)的運(yùn)行,,作為數(shù)據(jù)轉(zhuǎn)發(fā)的骨干網(wǎng)絡(luò)能量消耗較快,,造成網(wǎng)絡(luò)內(nèi)的能量消耗不均衡,于是混合技術(shù)采用拓?fù)渲貥?gòu)的維護(hù)技術(shù)來(lái)重構(gòu)整個(gè)網(wǎng)絡(luò)的拓?fù)?,兩種方法周期性地交替運(yùn)行,,有效地均衡網(wǎng)絡(luò)能量消耗。DFTM采用角色輪換的方法對(duì)局部拓?fù)溥M(jìn)行維護(hù),,而采用拓?fù)渲貥?gòu)的方法來(lái)對(duì)整個(gè)網(wǎng)絡(luò)拓?fù)溥M(jìn)行維護(hù),。
可見(jiàn),混合的拓?fù)渚S護(hù)技術(shù)可以使用基于節(jié)點(diǎn)角色輪換無(wú)法使用的資源,,而且網(wǎng)絡(luò)持續(xù)的時(shí)間比基于拓?fù)渲貥?gòu)方法要長(zhǎng),,因?yàn)檩嗈D(zhuǎn)過(guò)程比一個(gè)完整的新構(gòu)建過(guò)程消耗的能量少。但是,,混合技術(shù)由于觸發(fā)條件的選擇,,一個(gè)性能嚴(yán)重下降的拓?fù)淇赡艹掷m(xù)很長(zhǎng)一段時(shí)間,在它到達(dá)拓?fù)渲貥?gòu)恢復(fù)點(diǎn)前,,這將影響連通和覆蓋的服務(wù)水平,。
3.4 拓?fù)渚S護(hù)算法分類
拓?fù)渚S護(hù)算法分類可以從許多方面來(lái)進(jìn)行,如可以根據(jù)設(shè)計(jì)目標(biāo)將拓?fù)渚S護(hù)分為確保覆蓋,、連通的拓?fù)渚S護(hù),,故障容忍和安全的拓?fù)渚S護(hù),能量消耗均衡的拓?fù)渚S護(hù)等,。此外,,很難將目前研究的設(shè)計(jì)目標(biāo)和設(shè)計(jì)要素分開(kāi),導(dǎo)致分類可能并沒(méi)有精確地反映設(shè)計(jì)者的最初意圖,。為了盡量避免該問(wèn)題,,本文根據(jù)第2 節(jié)設(shè)計(jì)的拓?fù)渚S護(hù)模型對(duì)現(xiàn)有的拓?fù)渚S護(hù)算法進(jìn)行分類,如表1 所示,。
4 存在的問(wèn)題和發(fā)展趨勢(shì)
從以上可見(jiàn),,無(wú)線傳感器網(wǎng)路拓?fù)渚S護(hù)研究取得了一些成果,但其仍然存在一些問(wèn)題,。此外,,隨著無(wú)線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用,如何確保拓?fù)渚S護(hù)的安全性以及如何有機(jī)地與其它層互相融合將是拓?fù)渚S護(hù)算法的主要發(fā)展方向,。
?。?)缺乏實(shí)際的拓?fù)渚S護(hù)實(shí)施
盡管許多研究機(jī)構(gòu)致力于本文提到的拓?fù)渚S護(hù)技術(shù)研究,且許多的理論和基于仿真的證據(jù)表明拓?fù)渚S護(hù)算法或協(xié)議能有效減小網(wǎng)絡(luò)的能量消耗從而延長(zhǎng)網(wǎng)絡(luò)的生命周期,但是迄今為止,,很少有實(shí)際的網(wǎng)絡(luò)實(shí)施來(lái)證明拓?fù)渚S護(hù)事實(shí)上能被用于實(shí)現(xiàn)這些目標(biāo),。
(2)未能量化拓?fù)渚S護(hù)頻率
拓?fù)渚S護(hù)算法要考慮拓?fù)渲貥?gòu)產(chǎn)生的報(bào)文開(kāi)銷和優(yōu)化拓?fù)涞馁|(zhì)量之間的權(quán)衡,,一般情況下,,產(chǎn)生一個(gè)高質(zhì)量的優(yōu)化拓?fù)洌托枰l繁執(zhí)行拓?fù)渚S護(hù)協(xié)議,。另一方面,,每一次執(zhí)行拓?fù)渚S護(hù)協(xié)議將導(dǎo)致相當(dāng)數(shù)量的報(bào)文開(kāi)銷,。目前,,很少有研究仔細(xì)考慮兩者之間的權(quán)衡關(guān)系。
?。?)安全的拓?fù)渚S護(hù)
目前的大部分拓?fù)渚S護(hù)協(xié)議通常假設(shè)傳感器部署在一個(gè)可信的,、非敵對(duì)的環(huán)境中,并沒(méi)有考慮到節(jié)點(diǎn)內(nèi)部或外部攻擊的影響,。而無(wú)線傳感器的實(shí)際應(yīng)用尤其是商業(yè)和軍事應(yīng)用,,存在各種類型的惡意行為和攻擊,對(duì)手可以利用使用的拓?fù)渚S護(hù)算法來(lái)對(duì)網(wǎng)絡(luò)發(fā)起攻擊,。因此,,必須采取相應(yīng)的安全策略,提高拓?fù)渚S護(hù)算法的魯棒性,,使其能防御各類攻擊,。
(4)跨層的拓?fù)渚S護(hù)
無(wú)線傳感器網(wǎng)絡(luò)的生命期優(yōu)化目標(biāo)涉及從底層硬件到上層應(yīng)用的所有環(huán)節(jié),, 因此僅通過(guò)拓?fù)錁?gòu)建甚至拓?fù)渚S護(hù)往往難以達(dá)到最理想效果,,需要拓?fù)淇刂疲?gòu)建與維護(hù))與其它上下層協(xié)議緊密耦合協(xié)同。因此,,拓?fù)渚S護(hù)的設(shè)計(jì)也必須兼顧各層協(xié)議的特點(diǎn),,以便在無(wú)線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)中扮演好承上啟下的重要角色。
5 結(jié)論
本文對(duì)無(wú)線傳感器網(wǎng)絡(luò)拓?fù)渚S護(hù)研究現(xiàn)狀進(jìn)行了綜述,,并對(duì)當(dāng)前研究中存在的普遍問(wèn)題進(jìn)行了分析和概括,。從目前的研究現(xiàn)狀來(lái)看,拓?fù)渚S護(hù)研究主要以基于角色輪換和拓?fù)渲貥?gòu)為主,,已經(jīng)提出了CCP,、EETMS等算法。但目前的研究還存在模型理想化,、缺乏實(shí)際的拓?fù)渚S護(hù)實(shí)施以及未能量化拓?fù)渚S護(hù)運(yùn)行頻率和缺乏算法性能有效度量等問(wèn)題,。
總之,拓?fù)渚S護(hù)算法已經(jīng)取得了初步的研究成果,,但專門面向拓?fù)渚S護(hù)的研究還太少,。而且,,目前的研究未能考慮實(shí)際應(yīng)用所面對(duì)的如環(huán)境地形、噪音干擾,、惡意攻擊等諸多因素,。可見(jiàn),,拓?fù)渚S護(hù)還有許多問(wèn)題需要進(jìn)一步研究,,特別是需要探索面向?qū)嶋H應(yīng)用的安全和跨層的拓?fù)渚S護(hù)技術(shù)。