帶寬有效聚類結(jié)合RVBT的傳感器網(wǎng)絡(luò)容錯(cuò)路由算法

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

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

中圖分類號(hào)： TN926?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ú)線傳感器網(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)在傳感、計(jì)算和通信過(guò)程中會(huì)消耗能量，影響傳感器網(wǎng)絡(luò)系統(tǒng)的壽命[4?5]。因此，有效降低通信過(guò)程的開(kāi)銷(xiāo)和整體能量消耗非常重要。

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

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

1 帶寬有效聚類

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

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

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

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

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

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

2.1 骨干樹(shù)構(gòu)建

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

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

算法1：虛擬骨干樹(shù)結(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

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

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

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

算法2：一個(gè)子樹(shù)節(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)的非樹(shù)節(jié)點(diǎn)找到一個(gè)父親節(jié)點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 傳輸能量消耗比較

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

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

4.2 恢復(fù)延遲比較

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

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

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

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

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

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

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

表1 虛擬骨干樹(shù)算法之間的比較

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

5 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[1] 張希偉，戴海鵬，徐力杰，等.無(wú)線傳感器網(wǎng)絡(luò)中移動(dòng)協(xié)助的數(shù)據(jù)收集策略[J].軟件學(xué)報(bào)，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] 王艷，萬(wàn)鏹.生物啟發(fā)的無(wú)線傳感器網(wǎng)絡(luò)能量均衡方法研究[J].系統(tǒng)仿真學(xué)報(bào)，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é)報(bào)，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ú)線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學(xué)報(bào)，2012，34（5）：1222?1232.

[10] 洪榛，俞立，張貴軍.多級(jí)異構(gòu)無(wú)線傳感網(wǎng)高效動(dòng)態(tài)聚簇策略研究[J].自動(dòng)化學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)中能量?jī)?yōu)化與安全方案研究[D].北京：北京郵電大學(xué)，2013.

[14] 王軍，張宏烈.一種基于非均勻分簇的無(wú)線傳感器網(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è)計(jì)與實(shí)現(xiàn)[J].山東大學(xué)學(xué)報(bào)（理學(xué)版），2013（11）：36?43.