無線傳感器網(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é)省能量并延長網(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ù)，通過輪換節(jié)點(diǎn)的角色來對拓?fù)溥M(jìn)行維護(hù)。節(jié)點(diǎn)的角色可以從多方面描述，如睡眠/工作、簇頭/非簇頭、協(xié)調(diào)器/非協(xié)調(diào)器等，且節(jié)點(diǎn)的角色可以相互轉(zhuǎn)換。目前研究中，輪換的節(jié)點(diǎn)角色主要有兩種，一種是簇頭/非簇頭。它通過輪換簇內(nèi)簇頭節(jié)點(diǎn)來均衡簇內(nèi)能量消耗，優(yōu)化局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。LEACH是一種典型的角色輪換拓?fù)渚S護(hù)算法，通過概率隨機(jī)輪換簇頭，使網(wǎng)絡(luò)中節(jié)點(diǎn)等概率擔(dān)任簇頭，有效地節(jié)省節(jié)點(diǎn)能量。

　　另一種節(jié)點(diǎn)角色輪換為睡眠/工作，它通過調(diào)度那些未參與通信的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)來節(jié)約能量，實(shí)現(xiàn)延長網(wǎng)絡(luò)生命周期的目的。如SPAN通過維護(hù)組成骨干基礎(chǔ)架構(gòu)的節(jié)點(diǎn)來保持網(wǎng)絡(luò)的連通和轉(zhuǎn)發(fā)能力。MESH-CDS中，最大獨(dú)立集中節(jié)點(diǎn)故障時(shí)，通過轉(zhuǎn)換節(jié)點(diǎn)角色來修復(fù)最大獨(dú)立集并維護(hù)一個(gè)連通的骨干網(wǎng)絡(luò)。此外，CCP通過對節(jié)點(diǎn)角色的輪換維護(hù)網(wǎng)絡(luò)拓?fù)涞母采w和連通，它是一種典型和有重要影響的基于角色轉(zhuǎn)換的拓?fù)渚S護(hù)協(xié)議。其基本思想主要是通過保持一個(gè)足夠大的工作節(jié)點(diǎn)子集來維護(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)文信息來進(jìn)行本地決策以確定是否需要進(jìn)行角色輪換。

　　CCP能夠?qū)⒕W(wǎng)絡(luò)配置到指定的覆蓋度與連通度，并通過角色輪換來維護(hù)網(wǎng)絡(luò)的覆蓋和連通，其可靈活地應(yīng)用于不同的網(wǎng)絡(luò)環(huán)境。但是，CCP 需要較為精確的位置信息，并且當(dāng)發(fā)射半徑小于感知半徑的2倍時(shí)，不能保證網(wǎng)絡(luò)的連通性。

　　由上可見，基于角色輪換的技術(shù)通過調(diào)度那些未參與通信的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)或選擇剩余能量多的節(jié)點(diǎn)擔(dān)任簇頭來維護(hù)網(wǎng)絡(luò)連通和覆蓋。睡眠節(jié)點(diǎn)或非簇頭節(jié)點(diǎn)消耗的能量很小，且它們比工作節(jié)點(diǎn)或簇頭節(jié)點(diǎn)的數(shù)量大得多，所以網(wǎng)絡(luò)的能量消耗性能十分優(yōu)越。而且，通常算法僅需要局部信息，通過本地進(jìn)行決策，計(jì)算復(fù)雜度低。然而，基于角色輪換的拓?fù)渚S護(hù)技術(shù)僅從局部對網(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)建過程或?qū)Ｓ玫木S護(hù)算法來重構(gòu)網(wǎng)絡(luò)的拓?fù)?。如DKM協(xié)議，當(dāng)節(jié)點(diǎn)密度| SNS | k 時(shí)運(yùn)行拓?fù)渚S護(hù)過程，有效地恢復(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ù)淇刂扑惴▉砭S護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

　　EETMS算法中，一旦網(wǎng)絡(luò)發(fā)現(xiàn)故障節(jié)點(diǎn)，觸發(fā)拓?fù)渚S護(hù)過程，并最終構(gòu)建一個(gè)能量有效的局部拓?fù)洌移滏溌烽L度之和最小。EETMS 是一種典型的專門用于拓?fù)渚S護(hù)的基于拓?fù)渲貥?gòu)的技術(shù)。其思想是僅利用直接的鄰居節(jié)點(diǎn)來響應(yīng)拓?fù)渚S護(hù)過程，且節(jié)點(diǎn)將大部分能量花在用來估量網(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可表示為：

　　接下來，令，如果對于任意的i， j s 有， 0 i j s ，則圖G（V， E） 連通。因此，維護(hù)算法通過計(jì)算si， j 來構(gòu)建一個(gè)連通的拓?fù)洹．?dāng)網(wǎng)絡(luò)運(yùn)行中發(fā)現(xiàn)故障節(jié)點(diǎn)u ，觸發(fā)拓?fù)渚S護(hù)過程。此時(shí)故障節(jié)點(diǎn)u 的鄰居集為u ，節(jié)