摘 要： 針對現(xiàn)存骨干結(jié)構(gòu)算法在轉(zhuǎn)換重要節(jié)點(diǎn)時不能形成完整骨干結(jié)構(gòu)的問題，提出一種帶寬有效聚類結(jié)合隨機(jī)虛擬骨干樹（BC?RVBT）的WSN故障容錯路由算法。帶寬聚類提供更好的骨干樹構(gòu)建條件，在構(gòu)建骨干的過程中選取樹節(jié)點(diǎn)和非樹節(jié)點(diǎn)，每個節(jié)點(diǎn)至少與一個樹節(jié)點(diǎn)密切相關(guān)，根據(jù)樹節(jié)點(diǎn)的適合度值將非樹節(jié)點(diǎn)隨機(jī)地重新分布到所有合格的樹節(jié)點(diǎn)中，提高虛擬骨干樹的性能。在NS2仿真器上的實(shí)驗(yàn)結(jié)果顯示，相比其他幾種容錯算法，該文算法在傳輸數(shù)據(jù)時總能耗最低；平均路由路徑長度和家屬節(jié)點(diǎn)方差均為最低，分別為3.14和37.36。存在故障節(jié)點(diǎn)時，恢復(fù)延遲也表現(xiàn)優(yōu)秀，有效提高了WSN的使用壽命。

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)； 虛擬骨干樹； 帶寬聚類； 故障容錯路由算法

中圖分類號： TN926?34； TP393 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2016）12?0026?06

Abstract： As the existing backbone algorithms cannot form a complete backbone structure when transforming important nodes， a new fault?tolerant routing algorithm for wireless sensor network （WSN） is proposed， which is based on bandwidth?efficient clustering and random virtual backbone tree （BC?RVBT）. Bandwidth?efficient clustering can provide a better condition for the construction of virtual backbone tree. In the process of building the backbone tree， the tree node and non?tree nodes are selected. Each node is closely associated with at least one tree node. According to the value of the tree node， non?tree nodes are randomly re?distributed into all qualified tree node so as to improve the performance of RVBT. The results from the experiment on NS2 simulator show that the total energy consumption of the proposed algorithm is less than several other advanced fault?tolerant algorithms in data transmission， whose average length of routing paths is shortest （3.14） and the variance of family nodes is lowest （37.36） among all the algorithms. The recovery delay of proposed algorithm is also outstanding in case of existing faulty nodes， which indicates it has effectively improved the lifetime of WSN.

Keywords： wireless sensor network； virtual backbone tree； bandwidth clustering； fault?tolerant routing algorithm

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）[1?2]已在環(huán)境監(jiān)控、工業(yè)控制、醫(yī)療保健、軍事用途、區(qū)域監(jiān)控等領(lǐng)域得到廣泛應(yīng)用[3]。傳感器節(jié)點(diǎn)在傳感、計算和通信過程中會消耗能量，影響傳感器網(wǎng)絡(luò)系統(tǒng)的壽命[4?5]。因此，有效降低通信過程的開銷和整體能量消耗非常重要。

文獻(xiàn)[6]提出了一種故障節(jié)點(diǎn)容錯算法（VitaMin算法），通過對數(shù)據(jù)包的跟蹤為每個樹節(jié)點(diǎn)找到到達(dá)匯聚節(jié)點(diǎn)的最短路徑，利用一個集中和動態(tài)策略控制匯聚節(jié)點(diǎn)的移動性，增加網(wǎng)絡(luò)的壽命。然而，在重要節(jié)點(diǎn)轉(zhuǎn)換時，該算法不能形成完整骨干結(jié)構(gòu)。文獻(xiàn)[7]提出一種能量感知的虛擬骨干樹（Energy Virtual Backbone Tree，EVBT），EVBT將一個廣播請求數(shù)據(jù)包發(fā)送給其傳感范圍內(nèi)的所有節(jié)點(diǎn)，接收到這個數(shù)據(jù)包的節(jié)點(diǎn)計算出這個數(shù)據(jù)包的適應(yīng)度因子和時間延遲[td]，這個節(jié)點(diǎn)開始等待直到[td]到期。這個過程并不需要進(jìn)行大量的計算，算法主要目的是減少能量消耗并增強(qiáng)網(wǎng)絡(luò)的持久性，但是到達(dá)匯聚節(jié)點(diǎn)路由線路經(jīng)常并不是最近的。文獻(xiàn)[8]提出了改進(jìn)的EVBT（m?EVBT）通過利用節(jié)點(diǎn)間的距離和能量消耗信息減少總的能量消耗，能量消耗信息用于識別上游的關(guān)系，而能量消耗信息是通過一個EVBT結(jié)構(gòu)請求數(shù)據(jù)包進(jìn)行傳輸，只有當(dāng)節(jié)點(diǎn)所含有的能量大于閾值時，才考慮是否將其作為樹節(jié)點(diǎn)，m?EVBT利用一個集中和動態(tài)策略可以控制匯聚節(jié)點(diǎn)的移動性，增加網(wǎng)絡(luò)的壽命。文獻(xiàn)[9]提出了一種節(jié)能數(shù)據(jù)聚集協(xié)議（EDGA），該協(xié)議通過將節(jié)點(diǎn)的剩余能量作為計算度量以達(dá)到減少能量消耗的目的，然而，在網(wǎng)絡(luò)穩(wěn)定性方面存在不足。

本文提出了一種基于帶寬有效聚類結(jié)合隨機(jī)虛擬骨干樹的WSN容錯模型（Bandwidth?Efficient Clustering and Random Virtual Backbone tree，BC?RVBT），采用移動匯聚節(jié)點(diǎn)選取樹節(jié)點(diǎn)。根據(jù)樹節(jié)點(diǎn)的適合度值將非樹節(jié)點(diǎn)隨機(jī)重新分布到所有合格的樹節(jié)點(diǎn)中，有效解決了傳統(tǒng)骨干樹算法的問題，降低了總能耗，提高了WSN的使用壽命，具有較好的適應(yīng)性。

1 帶寬有效聚類

帶寬聚類和RVBT樹構(gòu)建的共同目標(biāo)都是減少總能耗和通信成本，帶寬聚類減少了數(shù)據(jù)包總量，有利于構(gòu)建骨干樹。

網(wǎng)絡(luò)模型是WSN中不同簇類[{C1，C2，…，Cn}]間的一個連接圖[G（V，E）]，含有異構(gòu)節(jié)點(diǎn)和移動匯聚點(diǎn)[10]。模型如圖1所示，每個區(qū)域中的簇頭CH和多個節(jié)點(diǎn)用頂點(diǎn)集合‘V’和無線連接邊‘E’表示。網(wǎng)絡(luò)中的‘V’節(jié)點(diǎn)是隨機(jī)分布的，利用多跳聚類算法將這些節(jié)點(diǎn)分配到‘n’簇類中。少量的節(jié)點(diǎn)‘h’（30～40 J）配置比一般節(jié)點(diǎn)‘u’（20 J）更高的能量。每個簇類中含有‘N’個節(jié)點(diǎn)，將[?u，h∈N]節(jié)點(diǎn)作為簇類成員，利用這些成員生成固定尺寸的可變數(shù)據(jù)包。為了生成數(shù)據(jù)包，在CH上定義一個適當(dāng)?shù)膲嚎s聚合函數(shù)[10]。

[f（CA）=i=1K（Xi）+1Mj=1M（Yj）] （1）

式中：[Xi]和[Yj]分別表示簇類中‘u’和‘h’節(jié)點(diǎn)生成數(shù)據(jù)包個數(shù)。函數(shù)所示為每個節(jié)點(diǎn)生成數(shù)據(jù)包的相關(guān)性，使用聚合函數(shù)的目的是：增加帶寬利用率（簇類內(nèi)部聚合），減少通信開銷（成本）和最小化網(wǎng)絡(luò)中的能量消耗率。

帶寬聚類分為三個階段：第一階段，將隨機(jī)分布的異構(gòu)節(jié)點(diǎn)編入簇類的編號中，表示每平方區(qū)域中用于簇類內(nèi)部和簇類之間聚合的CH；第二階段，用CH對可變簇類成員生成的數(shù)據(jù)包進(jìn)行聚合，生成的數(shù)據(jù)包的尺寸是固定的；第三階段，每個CH作為一個獨(dú)立節(jié)點(diǎn)進(jìn)行簇類間的聚類操作，最后，匯聚節(jié)點(diǎn)通過減少數(shù)據(jù)包總量的方式對數(shù)據(jù)包進(jìn)行聚合，從而減少通信成本。

2 虛擬骨干樹模型構(gòu)建

2.1 骨干樹構(gòu)建

帶寬聚類后，簇類已經(jīng)進(jìn)行了聚類操作，在減少能耗和通信成本的同時，也為骨干的構(gòu)建創(chuàng)造了更好的條件。圖2為本文的骨干樹系統(tǒng)，包含一個匯聚節(jié)點(diǎn)和傳感器節(jié)點(diǎn)，將傳感器節(jié)點(diǎn)劃分為樹節(jié)點(diǎn)和非樹節(jié)點(diǎn)。樹節(jié)點(diǎn)主要用于數(shù)據(jù)的感知、發(fā)送和接收，為了延長網(wǎng)絡(luò)的壽命，利用最小的能量代價和最小的距離將非樹節(jié)點(diǎn)發(fā)出的所有數(shù)據(jù)發(fā)送到匯聚節(jié)點(diǎn)。實(shí)驗(yàn)證明這樣的骨干樹可以減少數(shù)據(jù)包的能量消耗、增加網(wǎng)絡(luò)壽命、沒有快速的耗盡任何特定節(jié)點(diǎn)并維護(hù)了節(jié)點(diǎn)間的壽命。

傳感器網(wǎng)絡(luò)中的每個節(jié)點(diǎn)都含有一個可變能量級[11?12]。最初，所有能量級大于閾值（Th）的節(jié)點(diǎn)被暫時定為樹節(jié)點(diǎn)。從匯聚節(jié)點(diǎn)開始通過連接所有合格的節(jié)點(diǎn)構(gòu)成一棵樹。如果一個樹節(jié)點(diǎn)的能量逼近其閾值或擁有許多關(guān)聯(lián)，那么這個節(jié)點(diǎn)會變成一個熱點(diǎn)，由于熱點(diǎn)要傳輸許多數(shù)據(jù)包，因此會很快耗盡能量。直接利用家屬子樹節(jié)點(diǎn)和相關(guān)的非樹節(jié)點(diǎn)尋找一個新的父母樹節(jié)點(diǎn)。一個節(jié)點(diǎn)只要擁有父親節(jié)點(diǎn)，就不必去尋找一個新的父親節(jié)點(diǎn)。算法1說明了每個樹節(jié)點(diǎn)是如何找到可達(dá)樹節(jié)點(diǎn)。

算法1：虛擬骨干樹結(jié)構(gòu)初始化

Ni

If [Ni].Energy >t then

[Ni][←]TN

[?Ni] RTN[][←][Nj]==NT dist（i，j）

[?RTN]

Sum+ = RTN[→]No. of dependents

Avg=Sum/n

If RTN[→]No. of dependents[≥]2×Avg or [Ni.Energy→t+ε]

then

Find a suitable parent

End

End

本文算法所用符號說明如下：[Ni]為節(jié)點(diǎn)i；TN為樹節(jié)點(diǎn)；NTN為非樹節(jié)點(diǎn)；RTN為可達(dá)樹節(jié)點(diǎn)；[Si]為節(jié)點(diǎn)i的感知范圍；Dependents為將一個節(jié)點(diǎn)的子樹節(jié)點(diǎn)和相關(guān)的非樹節(jié)點(diǎn)作為其家屬；Th為一個樹節(jié)點(diǎn)所需的最小能量或能量閾值。

2.1.1 為子樹節(jié)點(diǎn)找到合適的父親節(jié)點(diǎn)

當(dāng)一個樹節(jié)點(diǎn)希望重新分布其家屬時，這個樹節(jié)點(diǎn)指導(dǎo)其子節(jié)點(diǎn)去尋找一個新的父親節(jié)點(diǎn)。子樹節(jié)點(diǎn)對這個行為進(jìn)行初始化如算法2所示。一個子樹節(jié)點(diǎn)在其感知范圍內(nèi)掃描并找到了可達(dá)樹節(jié)點(diǎn)的名單，如果在其范圍內(nèi)僅找到了一個節(jié)點(diǎn)，那么選取這個節(jié)點(diǎn)作為父親節(jié)點(diǎn)；如果在其范圍內(nèi)找到了多個可作為父母的樹節(jié)點(diǎn)，那么選取擁有最高適應(yīng)度因子的節(jié)點(diǎn)作為父親節(jié)點(diǎn)；如果沒能發(fā)現(xiàn)一個合適的節(jié)點(diǎn)，那么這個子樹節(jié)點(diǎn)仍然作為其先前父親節(jié)點(diǎn)的子節(jié)點(diǎn)以維護(hù)網(wǎng)絡(luò)正常運(yùn)行。

算法2：一個子樹節(jié)點(diǎn)選取新的父親節(jié)點(diǎn)

[?] child tree node j

RTN[][←]（[Nk][?]parent（[Nk]）[≠]Ni） [?]dist（k，j）<[Sk]

If k == 1 then

parent[j] [←]RTN else if k>1

max[←]-1，index[←]undefined

[?] RTN t then

If fitness factor（j，t）> max then

[max←]fitness factor（j，t）， index[←]t

parent[j] [←]index

If max == -1 then

If [（]parent Parent[sibling（j）][≠]NULL

Sibling（j）.is Reachable（） == TRUE then

parent[j] = sibling[j]

flag[←]-1

[?] child tree node j

If Parent[j] ==NULL || Parent[j] ==Ni then

[Ni←TN]

flag[←]0； break

End

End

End

End

End

2.1.2 為相關(guān)的非樹節(jié)點(diǎn)找到一個父親節(jié)點(diǎn)

對于每個非樹子節(jié)點(diǎn)，找到的可達(dá)樹節(jié)點(diǎn)都位于其感知范圍內(nèi)。在這些可達(dá)樹節(jié)點(diǎn)中，選取最短上游距離的節(jié)點(diǎn)作為父親節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)[Ni]沒有家屬時，其變成一個非樹節(jié)點(diǎn)，根據(jù)最小適應(yīng)度值選取子樹節(jié)點(diǎn)的父母，根據(jù)最小上游距離選取子非樹節(jié)點(diǎn)的父母，如算法3所示。

算法3：非樹節(jié)點(diǎn)選取新的父親節(jié)點(diǎn)

[?] associated non-tree node j

RTN[←]NK==TN[?]parent（NK）[≠][Ni] [?]dist（k，j）

k[←]（sizeof（RTN）/sizeof（RTN[0]））

If k == 1 then

parent[j][←]RTN

else if min[←]INFINITY index[←]NULL

[?]RTN t then

If upstream（t） + distance（j，t） < min then

min[←]upstream（t） + distance（j，t）

index[←]t

parent[j] [←]index

[?]associated non-tree node j

If Parent[j] ==NULL||parent[j] ==[Ni]then

[Ni][←]TN

flag[←]0

If if flag == 1 then

[Ni][←]NTN

End

End

End

End

2.2 骨干重構(gòu)

當(dāng)硬件發(fā)生錯誤或節(jié)點(diǎn)的能量完全耗盡時這個節(jié)點(diǎn)可能發(fā)生錯誤[12]。算法4對重構(gòu)機(jī)制進(jìn)行了介紹，樹節(jié)點(diǎn)定期檢查其能量是否低于Th，如果樹節(jié)點(diǎn)的能量低于Th，那么這個樹節(jié)點(diǎn)就變成一個非樹節(jié)點(diǎn)。如果t表示一個失效的樹節(jié)點(diǎn)，那么t的所有子樹節(jié)點(diǎn)被分配給其他節(jié)點(diǎn)。一個子樹節(jié)點(diǎn)在其感知范圍內(nèi)搜尋所有的樹節(jié)點(diǎn)，選取其中擁有最高適應(yīng)度因子的樹節(jié)點(diǎn)作為其父母。如果這個子樹節(jié)點(diǎn)感知范圍內(nèi)沒有其他樹節(jié)點(diǎn)，那么這個子樹節(jié)點(diǎn)在其感知范圍內(nèi)檢測所有非樹節(jié)點(diǎn)。

算法4：重構(gòu)骨干

iEnergy = Node[→]energy（）

If iEnergy < Th || Node.s Exist（） == FALSE then

[?]（t=parent（[Nc]）[?][Nc] = TN）

NN[][←][Nj][?]dist（c，j） < [Sc][?][Nj]= TN

k=sizeof（NN）/sizeof（NN[0]）

If k == 1 then

Parent[[Nc]][←]NN

else if k > 1 then

End

End

3 隨機(jī)虛擬骨干樹

隨機(jī)虛擬骨干樹（RVBT）與虛擬骨干樹很多部分都相同，如骨干構(gòu)建與重構(gòu)，不同的是虛擬骨干樹僅選取含有最大適應(yīng)度因子的樹節(jié)點(diǎn)作為父親節(jié)點(diǎn)[12]，而本文根據(jù)適應(yīng)度因子選取所有的樹節(jié)點(diǎn)作為父親節(jié)點(diǎn)。選取一個隨機(jī)父母，根據(jù)權(quán)重函數(shù)，為發(fā)送到匯聚節(jié)點(diǎn)的數(shù)據(jù)包隨機(jī)選取父母樹節(jié)點(diǎn)，最初，利用式（2）計算匯聚點(diǎn)可達(dá)的所有樹節(jié)點(diǎn)的適應(yīng)度因子之和：

[sum=tfitnessfactor（i，t）] （2）

一開始對前者的樹節(jié)點(diǎn)進(jìn)行排序，在區(qū)間[[0，sum]]中隨機(jī)生成一個數(shù)值，如果這個值位于區(qū)間[[0，fitnessfactor（i，0）]]內(nèi)，那么選取樹節(jié)點(diǎn)[t0]作為父母；如果生成的值位于區(qū)間[[fitnessfactor（i，0），][fitnessfactor（i，0）+finessfactor（i，1）]]內(nèi)，那么選取樹節(jié)點(diǎn)[t1]作為父母。計算節(jié)點(diǎn)[t]被選為一個樹節(jié)點(diǎn)父母的概率如下：

[P（t==parent）=fitnessfactor（i，t）sum] （3）

利用式（3）計算的距離可以完成選取過程。對于一個指定的非樹節(jié)點(diǎn)[j]，有：

[sum=t1upstream+distance（j，t）] （4）

利用式（5）計算選取節(jié)點(diǎn)[t]作為一個非樹節(jié)點(diǎn)父母的概率為：

[P（t==parent）=1upstream+distance（j，t）×sum] （5）

本文一開始對節(jié)點(diǎn)進(jìn)行部署時，大多數(shù)節(jié)點(diǎn)含有的能量大于能量閾值。用[path（n）]表示匯聚節(jié)點(diǎn)到節(jié)點(diǎn)[n]的路徑，通過樹節(jié)點(diǎn)對所有節(jié)點(diǎn)‘n’的路徑進(jìn)行定義。當(dāng)節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)很遠(yuǎn)時，利用單個虛擬骨干可能不足以進(jìn)行覆蓋。因此，在初始化構(gòu)建虛擬化骨干后，一些匯聚節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)其路徑[path（n）]為無窮大。根節(jié)點(diǎn)構(gòu)造一個‘n’節(jié)點(diǎn)并再次建立一個虛擬骨干，于是形成了一些離散度虛擬骨干，在重建過程中，將一些非樹節(jié)點(diǎn)轉(zhuǎn)化為樹節(jié)點(diǎn)，必要時可以將所有非樹節(jié)點(diǎn)進(jìn)行轉(zhuǎn)化。如果設(shè)置的一個節(jié)點(diǎn)N的開銷cost（N）過高，匯聚節(jié)點(diǎn)通過自身的更新采用其他的根節(jié)點(diǎn)和虛擬骨干，這樣匯聚節(jié)點(diǎn)就能定期的訪問節(jié)點(diǎn)N。當(dāng)節(jié)點(diǎn)失效后，如果選取了許多新的根節(jié)點(diǎn)，那么相應(yīng)形成新的離散結(jié)構(gòu)，匯聚節(jié)點(diǎn)將定期訪問這些根節(jié)點(diǎn)[13?14]。如果匯聚節(jié)點(diǎn)覆蓋范圍內(nèi)存在多個破損，那么形成‘n’個非重疊組。因此對于匯聚節(jié)點(diǎn)來說至少存在‘n’個根節(jié)點(diǎn)為其收集數(shù)據(jù)，每個組中至少含有一個。根據(jù)N?of?N壽命概念[15]，如果在部署區(qū)域中僅剩下很少的節(jié)點(diǎn)，那么網(wǎng)絡(luò)中必須形成骨干。只要活躍節(jié)點(diǎn)的個數(shù)不為零，匯聚節(jié)點(diǎn)就持續(xù)收集數(shù)據(jù)并維護(hù)N?of?N壽命。

4 仿真實(shí)驗(yàn)與分析

在結(jié)合Mac/802.15.4的NS2仿真器[16]平臺上對本文算法進(jìn)行仿真，其目標(biāo)是既能形成一個低數(shù)據(jù)率、低能耗和低成本的無線網(wǎng)絡(luò)，又可以在設(shè)備層級上實(shí)現(xiàn)無線聯(lián)通。

仿真實(shí)驗(yàn)在200×150平方單元的矩形區(qū)域內(nèi)分別放置了100和200個節(jié)點(diǎn)（在某些對比實(shí)驗(yàn)中，放置更多）。如果一個樹節(jié)點(diǎn)的家屬數(shù)量過多，此時這個樹節(jié)點(diǎn)的能量將會迅速耗盡，因此樹節(jié)點(diǎn)的家屬個數(shù)對樹節(jié)點(diǎn)具有很大的影響，能量耗盡的樹節(jié)點(diǎn)變成非樹節(jié)點(diǎn)。為了避免這個問題的發(fā)生，樹節(jié)點(diǎn)的家屬個數(shù)必須保持最小。在BC?RVBT中，對每個樹節(jié)點(diǎn)家屬的個數(shù)進(jìn)行隱式檢查。

4.1 傳輸能量消耗比較

網(wǎng)絡(luò)傳輸能量消耗是網(wǎng)絡(luò)容錯算法的重要評價標(biāo)準(zhǔn)。在每個節(jié)點(diǎn)上運(yùn)行BC?RVBT中的所有模塊，每個節(jié)點(diǎn)根據(jù)本文提出的算法將其狀態(tài)從樹節(jié)點(diǎn)變?yōu)榉菢涔?jié)點(diǎn)。

在NS2中通過修改cc文件可以獲取每個節(jié)點(diǎn)的能量耗損，當(dāng)執(zhí)行tcl文件時獲取每個節(jié)點(diǎn)的能量耗損。通過網(wǎng)絡(luò)仿真工具可以生成圖形表示，仿真事件序列存儲在跟蹤文件內(nèi)。當(dāng)一個節(jié)點(diǎn)的能量低于能量閾值時，只能永遠(yuǎn)作為一個非樹節(jié)點(diǎn)。在節(jié)點(diǎn)個數(shù)為100和200時，利用VitaMin[6]，m?EVBT[8]，EVBT CDS[12]和本文算法傳送數(shù)據(jù)，對傳送數(shù)據(jù)時總能量，消耗進(jìn)行仿真，圖3和圖4給出了仿真實(shí)驗(yàn)結(jié)果。對于一級能量模型最優(yōu)的傳送范圍為39 m左右，因此傳送范圍超過40 m后傳感器節(jié)點(diǎn)的能量消耗將會增加，但是，增加傳輸范圍將會消耗更多的電池電量。同時也可以看出，本文算法BC?RVBT總能耗最低。

4.2 恢復(fù)延遲比較

恢復(fù)延遲即故障恢復(fù)需要的平均時間是網(wǎng)絡(luò)容錯算法的重要標(biāo)志，其定義如下：

[故障恢復(fù)延遲=j=1j=k（dh+di）j] （6）

式（6）中：[dh]為切換機(jī)制的平均延遲；[di]為動態(tài)干擾抑制時間延遲；k為鄰居節(jié)點(diǎn)數(shù)量。

圖5和圖6分別為100個節(jié)點(diǎn)和200個節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)下幾種算法的恢復(fù)延遲。隨著故障節(jié)點(diǎn)數(shù)的增加，延遲也逐漸增加。由于可能存在距離超過3跳的故障節(jié)點(diǎn)導(dǎo)致同步故障恢復(fù)，因此降低了故障恢復(fù)延遲。同時延遲的增加與故障節(jié)點(diǎn)數(shù)目也相關(guān)，因?yàn)猷従庸?jié)點(diǎn)變成故障節(jié)點(diǎn)的恢復(fù)機(jī)制以順序方式執(zhí)行。從圖5和圖6可以看出本文算法BC?RVBT平均增長斜率最小，即恢復(fù)延遲所需的時間最少。

隨著節(jié)點(diǎn)數(shù)從100增加到200，延遲時間也隨之增加。這是因?yàn)楫?dāng)節(jié)點(diǎn)數(shù)量增加時，故障節(jié)點(diǎn)的鄰居節(jié)點(diǎn)也增加且恢復(fù)這些節(jié)點(diǎn)的時間也增加。然而，隨著網(wǎng)絡(luò)節(jié)點(diǎn)逐漸增加，本文算法故障恢復(fù)延遲達(dá)到一個常量。如圖7所示，隨著節(jié)點(diǎn)數(shù)增加，故障恢復(fù)延遲也增加，之后保持常量。隨著節(jié)點(diǎn)密度的增加，故障恢復(fù)時間變?yōu)槌Ａ?，因?yàn)楣收瞎?jié)點(diǎn)可能存在更多的鄰居節(jié)點(diǎn)且由于同步恢復(fù)使得延遲保持為常量；所以本文算法在恢復(fù)延遲方面具有更好的效果。

4.3 平均路由路徑長度與家屬節(jié)點(diǎn)方差比較

基于CDS的虛擬骨干通過計算跳的數(shù)量獲取最短的平均路由路徑長度。然而，家屬節(jié)點(diǎn)的數(shù)量是一個非常重要的變量，能夠?qū)е聵涔?jié)點(diǎn)的失效并影響網(wǎng)絡(luò)壽命。負(fù)載均衡虛擬骨干在所有樹節(jié)點(diǎn)的家屬數(shù)量中最小，但是獲取的平均路由路徑長度太大。本文提出的算法利用一個比負(fù)載均衡虛擬骨干短的路由路徑長度，負(fù)載均衡骨干在某種程度上最小化了家屬的個數(shù)。當(dāng)發(fā)送一個信息時隨機(jī)選取父親節(jié)點(diǎn)，這使得家屬分布更加合理。表1為基于能量、負(fù)載和距離的父親節(jié)點(diǎn)請求式隨機(jī)選取結(jié)果，這種機(jī)制有助于提高網(wǎng)絡(luò)的壽命。

表1 虛擬骨干樹算法之間的比較

表1給出了平均路由路徑長度和家屬節(jié)點(diǎn)方差方面的比較，可以看出本文算法BC?RVBT路由路徑最短，家屬節(jié)點(diǎn)的方差最小。因此，本文根據(jù)隨機(jī)化的權(quán)重函數(shù)給予所有的樹節(jié)點(diǎn)相同的似然性，隨機(jī)化權(quán)重函數(shù)在維持相同級別的能量消耗的情況下最小化重新分布，避免了含有較高適應(yīng)度因子和能量間的頻繁再分布。

5 結(jié) 語

本文提出的BC?RVBT算法能識別熱點(diǎn)并對樹節(jié)點(diǎn)的全部家屬進(jìn)行分布，增加了虛擬骨干的持久性。由骨干選取節(jié)能路徑，增加了WSN整體的網(wǎng)絡(luò)時間。家屬的重新分布被限定在一定的范圍內(nèi)，這是為了在負(fù)載分配過程中控制總能耗。由于本文算法允許每個含有較高能量的節(jié)點(diǎn)根據(jù)其適應(yīng)度因子變成虛擬骨干的一部分。在較差情況下，即使能量遠(yuǎn)大于能量閾值的傳感器節(jié)點(diǎn)也可以轉(zhuǎn)換為樹節(jié)點(diǎn)，從而增加網(wǎng)絡(luò)的持久性。從實(shí)驗(yàn)可以看出，有故障節(jié)點(diǎn)時，其恢復(fù)延遲也表現(xiàn)優(yōu)異。

參考文獻(xiàn)

[1] 張希偉，戴海鵬，徐力杰，等.無線傳感器網(wǎng)絡(luò)中移動協(xié)助的數(shù)據(jù)收集策略[J].軟件學(xué)報，2013，27（2）：198?214.

[2] 張欣欣.基于壓縮感知的WSN數(shù)據(jù)處理方法的研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2014.

[3] RAZZAQUE M A， DOBSON S. Energy efficient sensing in wireless sensor networks using compressed sensing [J]. Sensors 2014， 14（2）： 2822?2859.

[4] 王艷，萬鏹.生物啟發(fā)的無線傳感器網(wǎng)絡(luò)能量均衡方法研究[J].系統(tǒng)仿真學(xué)報，2013，25（12）：2860?2866.

[5] DENG S， LI J， SHEN L. Mobility?based clustering protocol for wireless sensor networks with mobile nodes [J]. Iet wireless sensor systems， 2011， 1（1）： 39?47.

[6] LEE J， KIM J. ViTAMin： a virtual backbone tree algorithm for minimal energy consumption in wireless sensor network routing [C]// International Conference on Information Networking. [S.l.： s.n.]， 2012： 144?149.

[7] 劉群，白全煒，曾憲華，等.能量感知的WSN節(jié)點(diǎn)分類控制路由算法[J].傳感技術(shù)學(xué)報，2011，24（7）：1053?1059.

[8] KIM J， YOON K H， LEE S， et al. An m?EVBT algorithm for energy efficient routing in wireless sensor networks[C]// Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication. USA： ACM， 2009， 3： 586?591.

[9] 蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學(xué)報，2012，34（5）：1222?1232.

[10] 洪榛，俞立，張貴軍.多級異構(gòu)無線傳感網(wǎng)高效動態(tài)聚簇策略研究[J].自動化學(xué)報，2013，39（4）：454?460.

[11] DU H， WU W， YE Q， et al. CDS?based virtual backbone construction with guaranteed routing cost in wireless sensor networks [J]. IEEE transactions on parallel distributed systems， 2013， 24（4）： 652?661.

[12] HE J， JI S， PAN Y， et al. Load?balanced virtual backbone construction for wireless sensor networks [J]. Lecture notes in computer science， 2012， 24（2）： 1?12.

[13] 李棟.無線傳感器網(wǎng)絡(luò)中能量優(yōu)化與安全方案研究[D].北京：北京郵電大學(xué)，2013.

[14] 王軍，張宏烈.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].硅谷，2015（3）：50?51.

[15] RAHMAN M N， MATIN M A. Efficient algorithm for prolonging network lifetime of wireless sensor networks [J]. Tsinghua science technology， 2011， 16（6）： 561?568.

[16] 郭曉東，焦亮，仇一泓，等.基于Click和NS2的多路徑域間路由仿真器的設(shè)計與實(shí)現(xiàn)[J].山東大學(xué)學(xué)報（理學(xué)版），2013（11）：36?43.