3 拓?fù)渚S護研究現(xiàn)狀
目前專門的拓?fù)渚S護技術(shù)研究還比較少,但相關(guān)研究結(jié)果表明優(yōu)化的拓?fù)渚S護能有效地節(jié)省能量并延長網(wǎng)絡(luò)生命周期,同時保持網(wǎng)絡(luò)的基本屬性覆蓋或連通。本節(jié)中,根據(jù)拓?fù)渚S護決策器所選維護策略將現(xiàn)有的拓?fù)渚S護技術(shù)分為基于角色輪換、基于拓?fù)渲貥?gòu)和混合的拓?fù)渚S護。
3.1 基于角色輪換的拓?fù)渚S護
基于角色轉(zhuǎn)換的拓?fù)渚S護技術(shù),通過輪換節(jié)點的角色來對拓?fù)溥M行維護。節(jié)點的角色可以從多方面描述,如睡眠/工作、簇頭/非簇頭、協(xié)調(diào)器/非協(xié)調(diào)器等,且節(jié)點的角色可以相互轉(zhuǎn)換。目前研究中,輪換的節(jié)點角色主要有兩種,一種是簇頭/非簇頭。它通過輪換簇內(nèi)簇頭節(jié)點來均衡簇內(nèi)能量消耗,優(yōu)化局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。LEACH是一種典型的角色輪換拓?fù)渚S護算法,通過概率隨機輪換簇頭,使網(wǎng)絡(luò)中節(jié)點等概率擔(dān)任簇頭,有效地節(jié)省節(jié)點能量。
另一種節(jié)點角色輪換為睡眠/工作,它通過調(diào)度那些未參與通信的網(wǎng)絡(luò)節(jié)點進入睡眠狀態(tài)來節(jié)約能量,實現(xiàn)延長網(wǎng)絡(luò)生命周期的目的。如SPAN通過維護組成骨干基礎(chǔ)架構(gòu)的節(jié)點來保持網(wǎng)絡(luò)的連通和轉(zhuǎn)發(fā)能力。MESH-CDS中,最大獨立集中節(jié)點故障時,通過轉(zhuǎn)換節(jié)點角色來修復(fù)最大獨立集并維護一個連通的骨干網(wǎng)絡(luò)。此外,CCP通過對節(jié)點角色的輪換維護網(wǎng)絡(luò)拓?fù)涞母采w和連通,它是一種典型和有重要影響的基于角色轉(zhuǎn)換的拓?fù)渚S護協(xié)議。其基本思想主要是通過保持一個足夠大的工作節(jié)點子集來維護網(wǎng)絡(luò)k-覆蓋。
在該算法中,每個節(jié)點扮演兩個角色,即睡眠節(jié)點或工作節(jié)點。每個節(jié)點利用ks-覆蓋規(guī)則和接收其鄰居節(jié)點的HELLO報文信息來進行本地決策以確定是否需要進行角色輪換。
CCP能夠?qū)⒕W(wǎng)絡(luò)配置到指定的覆蓋度與連通度,并通過角色輪換來維護網(wǎng)絡(luò)的覆蓋和連通,其可靈活地應(yīng)用于不同的網(wǎng)絡(luò)環(huán)境。但是,CCP 需要較為精確的位置信息,并且當(dāng)發(fā)射半徑小于感知半徑的2倍時,不能保證網(wǎng)絡(luò)的連通性。
由上可見,基于角色輪換的技術(shù)通過調(diào)度那些未參與通信的網(wǎng)絡(luò)節(jié)點進入睡眠狀態(tài)或選擇剩余能量多的節(jié)點擔(dān)任簇頭來維護網(wǎng)絡(luò)連通和覆蓋。睡眠節(jié)點或非簇頭節(jié)點消耗的能量很小,且它們比工作節(jié)點或簇頭節(jié)點的數(shù)量大得多,所以網(wǎng)絡(luò)的能量消耗性能十分優(yōu)越。而且,通常算法僅需要局部信息,通過本地進行決策,計算復(fù)雜度低。然而,基于角色輪換的拓?fù)渚S護技術(shù)僅從局部對網(wǎng)絡(luò)進行維護,不能從網(wǎng)絡(luò)的整體出發(fā),導(dǎo)致整個網(wǎng)絡(luò)拓?fù)浞亲顑?yōu)甚至不連通。
3.2 基于拓?fù)渲貥?gòu)的拓?fù)渚S護
基于拓?fù)錁?gòu)建的拓?fù)渚S護技術(shù)通常周期性調(diào)用拓?fù)錁?gòu)建過程或?qū)S玫木S護算法來重構(gòu)網(wǎng)絡(luò)的拓?fù)。如DKM協(xié)議,當(dāng)節(jié)點密度| SNS | k 時運行拓?fù)渚S護過程,有效地恢復(fù)和維護網(wǎng)絡(luò)的k -連通。SMSS算法中,當(dāng)節(jié)點u 發(fā)現(xiàn)某個節(jié)點m 失效時,它將檢查m 是否為它確定的鄰節(jié)點,如果是,重新運行拓?fù)淇刂扑惴▉砭S護網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。
EETMS算法中,一旦網(wǎng)絡(luò)發(fā)現(xiàn)故障節(jié)點,觸發(fā)拓?fù)渚S護過程,并最終構(gòu)建一個能量有效的局部拓?fù),且其鏈路長度之和最小。EETMS 是一種典型的專門用于拓?fù)渚S護的基于拓?fù)渲貥?gòu)的技術(shù)。其思想是僅利用直接的鄰居節(jié)點來響應(yīng)拓?fù)渚S護過程,且節(jié)點將大部分能量花在用來估量網(wǎng)絡(luò)連通和尋找最小能量拓?fù)洌皇怯糜谵D(zhuǎn)發(fā)數(shù)據(jù)。
EETMS 算法首先提出了一個判斷網(wǎng)絡(luò)連通的標(biāo)準(zhǔn)。在一個二維的歐幾里得空間里,網(wǎng)絡(luò)拓?fù)溆靡粋圖G(V, E) 表示,其中V 為節(jié)點集,節(jié)點個數(shù)為n .E 為所有邊e(i, j)的集合,其中e(i, j) 表示節(jié)點i 和j 彼此互為鄰居。則網(wǎng)絡(luò)拓?fù)淇捎脠DG 的鄰接矩陣A 表示,且矩陣的每個元素ai, j可表示為:
接下來,令,如果對于任意的i, j s 有, 0 i j s ,則圖G(V, E) 連通。因此,維護算法通過計算si, j 來構(gòu)建一個連通的拓?fù)洹.?dāng)網(wǎng)絡(luò)運行中發(fā)現(xiàn)故障節(jié)點u ,觸發(fā)拓?fù)渚S護過程。此時故障節(jié)點u 的鄰居集為u ,節(jié)點數(shù)u m .EETMS能夠維護網(wǎng)絡(luò)的連通,并確保鏈路長度之和最小。但算法中需要構(gòu)建故障節(jié)點的鄰接矩陣,并根據(jù)該矩陣來計算網(wǎng)絡(luò)的連通。在高密度網(wǎng)絡(luò)中,需要大量的存儲空間和高的計算復(fù)雜度。此外,算法中并沒有描述故障節(jié)點檢測機制,無法知道拓?fù)渚S護算法的觸發(fā)頻率。
總之,基于拓?fù)渲貥?gòu)的拓?fù)渚S護技術(shù)可能需要多次動態(tài)運行拓?fù)錁?gòu)建或維護算法,通常需要更多的時間和能量消耗。然而,拓?fù)錁?gòu)建過程在它每次運行時通常選擇最優(yōu)或接近最優(yōu)拓?fù),從而?dǎo)致生成比基于角色轉(zhuǎn)換拓?fù)渚S護技術(shù)更好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。
3.3 混合的拓?fù)渚S護
混合的拓?fù)渚S護技術(shù)結(jié)合了基于角色輪換和拓?fù)渲貥?gòu)的拓?fù)渚S護。該類拓?fù)渚S護技術(shù)周期性地采用節(jié)點角色轉(zhuǎn)換和拓?fù)渲貥?gòu)策略。首先,混合的方法采用角色轉(zhuǎn)換的維護方法對網(wǎng)絡(luò)的局部拓?fù)溥M行維護,實現(xiàn)網(wǎng)絡(luò)一部分(如一個簇)的優(yōu)化。隨著網(wǎng)絡(luò)的運行,作為數(shù)據(jù)轉(zhuǎn)發(fā)的骨干網(wǎng)絡(luò)能量消耗較快,造成網(wǎng)絡(luò)內(nèi)的能量消耗不均衡,于是混合技術(shù)采用拓?fù)渲貥?gòu)的維護技術(shù)來重構(gòu)整個網(wǎng)絡(luò)的拓?fù),兩種方法周期性地交替運行,有效地均衡網(wǎng)絡(luò)能量消耗。DFTM采用角色輪換的方法對局部拓?fù)溥M行維護,而采用拓?fù)渲貥?gòu)的方法來對整個網(wǎng)絡(luò)拓?fù)溥M行維護。
可見,混合的拓?fù)渚S護技術(shù)可以使用基于節(jié)點角色輪換無法使用的資源,而且網(wǎng)絡(luò)持續(xù)的時間比基于拓?fù)渲貥?gòu)方法要長,因為輪轉(zhuǎn)過程比一個完整的新構(gòu)建過程消耗的能量少。但是,混合技術(shù)由于觸發(fā)條件的選擇,一個性能嚴(yán)重下降的拓?fù)淇赡艹掷m(xù)很長一段時間,在它到達拓?fù)渲貥?gòu)恢復(fù)點前,這將影響連通和覆蓋的服務(wù)水平。
3.4 拓?fù)渚S護算法分類
拓?fù)渚S護算法分類可以從許多方面來進行,如可以根據(jù)設(shè)計目標(biāo)將拓?fù)渚S護分為確保覆蓋、連通的拓?fù)渚S護,故障容忍和安全的拓?fù)渚S護,能量消耗均衡的拓?fù)渚S護等。此外,很難將目前研究的設(shè)計目標(biāo)和設(shè)計要素分開,導(dǎo)致分類可能并沒有精確地反映設(shè)計者的最初意圖。為了盡量避免該問題,本文根據(jù)第2 節(jié)設(shè)計的拓?fù)渚S護模型對現(xiàn)有的拓?fù)渚S護算法進行分類,如表1 所示。
4 存在的問題和發(fā)展趨勢
從以上可見,無線傳感器網(wǎng)路拓?fù)渚S護研究取得了一些成果,但其仍然存在一些問題。此外,隨著無線傳感器網(wǎng)絡(luò)的實際應(yīng)用,如何確保拓?fù)渚S護的安全性以及如何有機地與其它層互相融合將是拓?fù)渚S護算法的主要發(fā)展方向。
(1)缺乏實際的拓?fù)渚S護實施
盡管許多研究機構(gòu)致力于本文提到的拓?fù)渚S護技術(shù)研究,且許多的理論和基于仿真的證據(jù)表明拓?fù)渚S護算法或協(xié)議能有效減小網(wǎng)絡(luò)的能量消耗從而延長網(wǎng)絡(luò)的生命周期,但是迄今為止,很少有實際的網(wǎng)絡(luò)實施來證明拓?fù)渚S護事實上能被用于實現(xiàn)這些目標(biāo)。
(2)未能量化拓?fù)渚S護頻率
拓?fù)渚S護算法要考慮拓?fù)渲貥?gòu)產(chǎn)生的報文開銷和優(yōu)化拓?fù)涞馁|(zhì)量之間的權(quán)衡,一般情況下,產(chǎn)生一個高質(zhì)量的優(yōu)化拓?fù)洌托枰l繁執(zhí)行拓?fù)渚S護協(xié)議。另一方面,每一次執(zhí)行拓?fù)渚S護協(xié)議將導(dǎo)致相當(dāng)數(shù)量的報文開銷。目前,很少有研究仔細考慮兩者之間的權(quán)衡關(guān)系。
(3)安全的拓?fù)渚S護
目前的大部分拓?fù)渚S護協(xié)議通常假設(shè)傳感器部署在一個可信的、非敵對的環(huán)境中,并沒有考慮到節(jié)點內(nèi)部或外部攻擊的影響。而無線傳感器的實際應(yīng)用尤其是商業(yè)和軍事應(yīng)用,存在各種類型的惡意行為和攻擊,對手可以利用使用的拓?fù)渚S護算法來對網(wǎng)絡(luò)發(fā)起攻擊。因此,必須采取相應(yīng)的安全策略,提高拓?fù)渚S護算法的魯棒性,使其能防御各類攻擊。
(4)跨層的拓?fù)渚S護
無線傳感器網(wǎng)絡(luò)的生命期優(yōu)化目標(biāo)涉及從底層硬件到上層應(yīng)用的所有環(huán)節(jié), 因此僅通過拓?fù)錁?gòu)建甚至拓?fù)渚S護往往難以達到最理想效果,需要拓?fù)淇刂疲?gòu)建與維護)與其它上下層協(xié)議緊密耦合協(xié)同。因此,拓?fù)渚S護的設(shè)計也必須兼顧各層協(xié)議的特點,以便在無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)中扮演好承上啟下的重要角色。
5 結(jié)論
本文對無線傳感器網(wǎng)絡(luò)拓?fù)渚S護研究現(xiàn)狀進行了綜述,并對當(dāng)前研究中存在的普遍問題進行了分析和概括。從目前的研究現(xiàn)狀來看,拓?fù)渚S護研究主要以基于角色輪換和拓?fù)渲貥?gòu)為主,已經(jīng)提出了CCP、EETMS等算法。但目前的研究還存在模型理想化、缺乏實際的拓?fù)渚S護實施以及未能量化拓?fù)渚S護運行頻率和缺乏算法性能有效度量等問題。
總之,拓?fù)渚S護算法已經(jīng)取得了初步的研究成果,但專門面向拓?fù)渚S護的研究還太少。而且,目前的研究未能考慮實際應(yīng)用所面對的如環(huán)境地形、噪音干擾、惡意攻擊等諸多因素。可見,拓?fù)渚S護還有許多問題需要進一步研究,特別是需要探索面向?qū)嶋H應(yīng)用的安全和跨層的拓?fù)渚S護技術(shù)
來源:電子愛好者博客