無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)渚S護(hù)（二）

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ò)的連通性。

由上可見，基于角色輪換的技術(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護(hù)算法來(lái)重構(gòu)網(wǎng)絡(luò)的拓?fù)�。如DKM協(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ù)�，且其鏈路長(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ù)雜度。此外，算法中并沒有描述故障節(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ù)。

可見，混合的拓?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ì)要素分開，導(dǎo)致分類可能并沒有精確地反映設(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ì)

從以上可見，無(wú)線傳感器網(wǎng)路拓?fù)渚S護(hù)研究取得了一些成果，但其仍然存在一些問(wèn)題。此外，隨著無(wú)線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用，如何確保拓?fù)渚S護(hù)的安全性以及如何有機(jī)地與其它層互相融合將是拓?fù)渚S護(hù)算法的主要發(fā)展方向。

（1）缺乏實(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)文開銷和優(yōu)化拓?fù)涞馁|(zhì)量之間的權(quán)衡，一般情況下，產(chǎn)生一個(gè)高質(zhì)量的優(yōu)化拓?fù)�，就需要頻繁執(zhí)行拓?fù)渚S護(hù)協(xié)議。另一方面，每一次執(zhí)行拓?fù)渚S護(hù)協(xié)議將導(dǎo)致相當(dāng)數(shù)量的報(bào)文開銷。目前，很少有研究仔細(xì)考慮兩者之間的權(quán)衡關(guān)系。

（3）安全的拓?fù)渚S護(hù)

目前的大部分拓?fù)渚S護(hù)協(xié)議通常假設(shè)傳感器部署在一個(gè)可信的、非敵對(duì)的環(huán)境中，并沒有考慮到節(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)境地形、噪音干擾、惡意攻擊等諸多因素�？梢姡�拓?fù)渚S護(hù)還有許多問(wèn)題需要進(jìn)一步研究，特別是需要探索面向?qū)嶋H應(yīng)用的安全和跨層的拓?fù)渚S護(hù)技術(shù)

來(lái)源：電子愛好者博客