張曉花，董榮勝

(桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林　541004)

?

基于OBDD的無(wú)線傳感器網(wǎng)絡(luò)可用度算法

張曉花，董榮勝

(桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林541004)

為降低傳感器節(jié)點(diǎn)的能量消耗，提高無(wú)線傳感器網(wǎng)絡(luò)可用度，構(gòu)建了可用度評(píng)估的離散概率模型，提出了一種符號(hào)A_OBDD算法。該算法利用馬爾科夫鏈描述節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移過程，實(shí)現(xiàn)了對(duì)節(jié)點(diǎn)可用度的動(dòng)態(tài)評(píng)估，引入有序二叉決策圖，有效緩解了“組合爆炸”。實(shí)驗(yàn)結(jié)果表明，WSN節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移概率對(duì)可用度有較大影響，驗(yàn)證了A_OBDD算法可以有效評(píng)估WSN可用度。

無(wú)線傳感器網(wǎng)絡(luò)；可用度；能量約束；馬爾科夫鏈；有序二叉決策圖

近年來(lái)，無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，簡(jiǎn)稱WSN)的研究大都集中在數(shù)據(jù)管理和可靠性方面，在工業(yè)應(yīng)用中對(duì)可靠性有嚴(yán)格的要求。然而，WSN可用度也是系統(tǒng)評(píng)估其完成任務(wù)能力的一個(gè)重要參數(shù)。數(shù)據(jù)的成功傳輸不僅依賴網(wǎng)絡(luò)的連通性，也依賴節(jié)點(diǎn)所處的狀態(tài)。只有能夠完成傳輸任務(wù)的路徑才是可用路徑。廉價(jià)的傳感器節(jié)點(diǎn)由低電壓電池提供能量，電池能量的有限性限制了其壽命。為了減少傳感器節(jié)點(diǎn)能量的消耗，節(jié)點(diǎn)必須在活動(dòng)和睡眠狀態(tài)之間切換。

WSN可靠度計(jì)算是一個(gè)#P-hard問題[1-2]。傳統(tǒng)的方法很難對(duì)大規(guī)模WSN可靠性進(jìn)行有效評(píng)估。Chang等[3]以網(wǎng)絡(luò)連通性作為網(wǎng)絡(luò)正常工作與否的標(biāo)準(zhǔn)，通過使用有序二叉決策圖(ordered binary decision diagrams，簡(jiǎn)稱OBDD)表示網(wǎng)絡(luò)狀態(tài)、計(jì)算網(wǎng)絡(luò)可靠性。文獻(xiàn)[4-5]考慮邊的容量約束，充分利用了代數(shù)決策圖(algebraic decision diagrams，簡(jiǎn)稱ADD)具有較高存儲(chǔ)效率以及能夠緩解實(shí)際應(yīng)用中存在的狀態(tài)空間“組合爆炸”等特性，提出一種基于ADD求解網(wǎng)絡(luò)最大流的算法。針對(duì)WSN節(jié)點(diǎn)的特性，文獻(xiàn)[6-7]基于OBDD提出COBDD算法，分析了共因失效情況下WSN可靠性，通過節(jié)點(diǎn)擴(kuò)張的方法構(gòu)建WSN的OBDD，然后遍歷OBDD計(jì)算WSN可靠度。針對(duì)WSN能量約束的特點(diǎn)，BRUNE等[8]基于傳感器節(jié)點(diǎn)的2種狀態(tài)(睡眠和活動(dòng))消耗能量的不同，對(duì)星形網(wǎng)絡(luò)可用性進(jìn)行了評(píng)估。Chiasserini等[9]基于網(wǎng)絡(luò)節(jié)點(diǎn)有限能量的限制，利用連續(xù)時(shí)間馬爾可夫鏈(continuous time Markov chain，簡(jiǎn)稱CTMC)描述傳感器節(jié)點(diǎn)的行為變化，對(duì)無(wú)線傳感器網(wǎng)絡(luò)的性能(如能量消耗、網(wǎng)絡(luò)容量和數(shù)據(jù)傳輸時(shí)延)進(jìn)行了建模。Liu等[10]在Chiasserini的基礎(chǔ)上，提出了傳感器節(jié)點(diǎn)的排隊(duì)模型和整個(gè)傳感器網(wǎng)絡(luò)的性能模型。

假設(shè)WSN節(jié)點(diǎn)可靠而邊不可靠，對(duì)于節(jié)點(diǎn)能量受限的WSN網(wǎng)絡(luò)，基于OBDD的可靠性計(jì)算方法不能直接應(yīng)用于WSN可用度計(jì)算。而在使用數(shù)學(xué)方法計(jì)算可用度的過程中，存在狀態(tài)空間爆炸，很難解決大規(guī)模WSN的可用度問題。

針對(duì)以上問題，利用OBDD結(jié)構(gòu)，基于馬爾科夫鏈考慮節(jié)點(diǎn)能量約束，提出基于馬爾科夫鏈的WSN可用度符號(hào)算法——A_OBDD算法。該算法緩解了組合爆炸，降低了算法的時(shí)間復(fù)雜度，提高網(wǎng)絡(luò)的可用性。

1　馬爾科夫鏈下WSN可用度模型

1.1形式化模型

無(wú)線傳感器網(wǎng)絡(luò)的關(guān)鍵問題是傳感器節(jié)點(diǎn)可用能量的限制，因此，必須充分利用能量、提高網(wǎng)絡(luò)壽命。一個(gè)廣泛采用的保存能量的技術(shù)就是使節(jié)點(diǎn)處于睡眠模式。傳感器節(jié)點(diǎn)包含睡眠和活動(dòng)2種狀態(tài)。使用馬爾科夫鏈描述節(jié)點(diǎn)行為的變化，如圖1所示。

圖1　無(wú)線傳感器節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移Fig.1　The state transition of sensor nodes

對(duì)節(jié)點(diǎn)能量約束下的WSN進(jìn)行建模，其形式化模型為

1)G為由n個(gè)節(jié)點(diǎn)和m條邊組成的網(wǎng)絡(luò)結(jié)構(gòu)圖。G=(V,E)。其中：V=(v1,v2,…,vn)為n個(gè)節(jié)點(diǎn)的集合；E=(e1,e2,…,em)為m條邊的集合，滿足E?V×V。

2)S為無(wú)線傳感器網(wǎng)絡(luò)的源節(jié)點(diǎn)。

3)T為無(wú)線傳感器網(wǎng)絡(luò)的目標(biāo)節(jié)點(diǎn)。

4)E為傳感器節(jié)點(diǎn)的能量初始值設(shè)定，E={Emax,Erest(t),Emin}。其中：Emax為傳感器節(jié)點(diǎn)自身帶有的能量；Emin為使傳感器節(jié)點(diǎn)正常工作的門限值；Erest(t)為傳感器節(jié)點(diǎn)在t時(shí)刻的剩余能量。

5)P(λ,μ)為傳感器節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移的概率。其中：λ為節(jié)點(diǎn)由活動(dòng)狀態(tài)轉(zhuǎn)到睡眠狀態(tài)的概率，0≤λ；μ為節(jié)點(diǎn)由睡眠狀態(tài)轉(zhuǎn)到活動(dòng)狀態(tài)的概率，μ≤1。

1.2可用度定義

WSN節(jié)點(diǎn)具有能量約束的特點(diǎn)，為了充分利用能量，傳感器節(jié)點(diǎn)必須在活動(dòng)和睡眠狀態(tài)之間切換。在時(shí)刻t數(shù)據(jù)的成功傳輸不僅依賴于源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的連通性，也依賴于傳感器節(jié)點(diǎn)在時(shí)刻t所處的狀態(tài)。只有能夠完成傳輸任務(wù)的路徑才是可用路徑。以4個(gè)假設(shè)為前提：

1)WSN網(wǎng)絡(luò)的邊可靠；

2)傳感器節(jié)點(diǎn)開始時(shí)，能量存儲(chǔ)量都相同；

3)傳感器節(jié)點(diǎn)進(jìn)行狀態(tài)轉(zhuǎn)移的概率不變；

4)容錯(cuò)分簇協(xié)議保持WSN拓?fù)洳蛔儭?/p>

系統(tǒng)在時(shí)刻t的可用度是系統(tǒng)在時(shí)刻t完成任務(wù)的能力。在工作時(shí)間內(nèi)，若傳感器節(jié)點(diǎn)處于睡眠狀態(tài)，則不能發(fā)送/接受數(shù)據(jù)，此時(shí)也不能與源節(jié)點(diǎn)通信。從源節(jié)點(diǎn)的角度看，睡眠節(jié)點(diǎn)不能完成任務(wù)。因此，可以定義傳感器節(jié)點(diǎn)的可用度。

定義1節(jié)點(diǎn)可用度Anode(t)：傳感器節(jié)點(diǎn)在t時(shí)刻能夠與源節(jié)點(diǎn)保持通信的能力，即節(jié)點(diǎn)在時(shí)刻t處于活動(dòng)狀態(tài)的概率。形式化定義為

Anode(t)={λ,μ,t,l}。

定義2對(duì)于給定的無(wú)線傳感器網(wǎng)絡(luò)WSN，可用度的形式化定義為

其中：vs為WSN網(wǎng)絡(luò)的源節(jié)點(diǎn)，vs∈V；vt為WSN網(wǎng)絡(luò)的目標(biāo)節(jié)點(diǎn)；?R(vs→vt)為WSN網(wǎng)絡(luò)存在一條由vs到vt的有效數(shù)據(jù)傳輸鏈路；p(?R(vs→vt))為WSN網(wǎng)絡(luò)至少存在一條由vs到vt的有效數(shù)據(jù)傳輸鏈路的概率，表示W(wǎng)SN模型的可用度Awsn(vs,vt)。

1.3WSN節(jié)點(diǎn)可用度的計(jì)算

1.3.1節(jié)點(diǎn)可用度Anode(t)的計(jì)算

對(duì)于圖1的無(wú)線傳感器節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移圖，假設(shè)節(jié)點(diǎn)初始時(shí)刻為活動(dòng)狀態(tài)，節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移方程為：

(1)

式(1)可變形為：

(2)

根據(jù)拉普拉斯變換和初始條件p0(0)=1和p0(1)=0，得到式(2)的解：

(3)

解式(3)得

(4)

利用部分分式法，得

(5)

對(duì)式(5)進(jìn)行逆變換得

(6)

即得節(jié)點(diǎn)可用度為

(7)

1.3.2穩(wěn)態(tài)可用度l的計(jì)算

(8)

(9)

根據(jù)馬爾科夫鏈的遍歷性：

(10)

且有式(11)成立：

(11)

于是得

(12)

2　WSN可用度分析的A_OBDD算法

對(duì)于給定無(wú)線傳感器網(wǎng)絡(luò)N=〈G,S,T,E,P(λ,μ)〉，評(píng)估可用度的A_OBDD算法分為4步：第1步利用BFS方法確定OBDD變量順序；第2步構(gòu)建源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路徑的OBDD[11]；第3步計(jì)算隨時(shí)間變化的節(jié)點(diǎn)可用度分布；第4步遍歷OBDD，計(jì)算節(jié)點(diǎn)的動(dòng)態(tài)可用度。

第1步：利用BFS方法確定OBDD變量順序。

1)對(duì)于給定的WSN網(wǎng)絡(luò)圖，利用廣度優(yōu)先搜索法，存儲(chǔ)層次節(jié)點(diǎn)和層次邊，將搜索到的節(jié)點(diǎn)vi放到集合V[x]中，將搜索到的邊ei存儲(chǔ)到OBDD變量U[x]中，當(dāng)i=0時(shí)，vi為源節(jié)點(diǎn)vs，對(duì)其進(jìn)行編序。

2)當(dāng)i>0時(shí)，若與搜索到的起始節(jié)點(diǎn)相連的節(jié)點(diǎn)只有一個(gè)，則執(zhí)行4)。

3)當(dāng)i>0時(shí)，若與搜索到的起始節(jié)點(diǎn)相連的節(jié)點(diǎn)有多個(gè)，則用優(yōu)先函數(shù)式選擇下一層節(jié)點(diǎn)，并對(duì)節(jié)點(diǎn)進(jìn)行編序。

4)返回WSN的節(jié)點(diǎn)變量序。使用相對(duì)距離函數(shù)作為優(yōu)先函數(shù)：

(13)

(14)

第2步：構(gòu)建源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路徑的OBDD。

1)根據(jù)第1步得到的變量序，若網(wǎng)絡(luò)源節(jié)點(diǎn)vs等于目標(biāo)節(jié)點(diǎn)vt，則結(jié)束遞歸，并返回vs，否則繼續(xù)執(zhí)行2)；

2)求出與源節(jié)點(diǎn)vs相連且沒有被訪問過的節(jié)點(diǎn)集V[x]；

3)vs=vn，進(jìn)入下一次遞歸，遞歸返回值賦給R[i+1]；

4)節(jié)點(diǎn)vn的OBDD和R[i+1]進(jìn)行And布爾操作，并將其值賦給R[i]；

5)將已構(gòu)造的OBDD和R[i]進(jìn)行Or布爾操作，并將其值賦給AWSN；

6)返回可用度AWSN。

第3步：計(jì)算隨時(shí)間變化的節(jié)點(diǎn)可用度分布。

1)給定傳感器節(jié)點(diǎn)狀態(tài)之間轉(zhuǎn)移的概率；

2)計(jì)算節(jié)點(diǎn)的瞬時(shí)可用度；

3)根據(jù)馬爾科夫鏈的遍歷性計(jì)算節(jié)點(diǎn)的穩(wěn)態(tài)可用度。

第4步：遍歷OBDD，計(jì)算節(jié)點(diǎn)動(dòng)態(tài)可用度。

1)從根節(jié)點(diǎn)開始，訪問構(gòu)造得到的OBDD，根節(jié)點(diǎn)概率值初始化為1，即P(vs)=1，將節(jié)點(diǎn)插入到給定隊(duì)列中，該隊(duì)列用來(lái)保存已訪問過的節(jié)點(diǎn)；

2)若隊(duì)列為空，算法結(jié)束，得到的A值即為所求可用度；

3)取隊(duì)列首節(jié)點(diǎn)vi，vi的0邊為F0，若F0為1葉子節(jié)點(diǎn)，則可用度AWSN+=(1-p)×P(vi)，否則，節(jié)點(diǎn)概率值P(F0)+= (1-p)×P(vi)，將F0插入隊(duì)列中；

4)vi的1邊為F1，若F1為1葉子節(jié)點(diǎn)，則可用度AWSN+=p×P(vi)，否則，節(jié)點(diǎn)概率值P(F1)+=p×P(vi)，將F1插入隊(duì)列中，跳轉(zhuǎn)到步驟2)；

5)返回可用度值A(chǔ)WSN。

采用寬度優(yōu)先搜索的方法遍歷OBDD，計(jì)算WSN的網(wǎng)絡(luò)可用度。概率從根節(jié)點(diǎn)開始計(jì)算，將父節(jié)點(diǎn)的概率值乘以本身節(jié)點(diǎn)的概率，然后將求得的概率值分配到子節(jié)點(diǎn)(計(jì)算時(shí)根節(jié)點(diǎn)的父節(jié)點(diǎn)概率值為0，根節(jié)點(diǎn)自身概率值為1)，最后計(jì)算出1葉子節(jié)點(diǎn)的概率。利用下式完成此操作：

其中：p為節(jié)點(diǎn)處于活動(dòng)狀態(tài)的概率；P(vi)為節(jié)點(diǎn)vi具有的概率值。由式(15)可以看出，計(jì)算WSN可用度只與構(gòu)造的OBDD節(jié)點(diǎn)數(shù)目有關(guān)，只需遍歷一次OBDD就可以計(jì)算出可用度，算法的時(shí)間復(fù)雜度為O(n)，n為構(gòu)造的OBDD的節(jié)點(diǎn)數(shù)目。

3　實(shí)例分析

以圖2所示的網(wǎng)絡(luò)圖為例，構(gòu)建OBDD，并利用式(15)計(jì)算可用度。實(shí)例中源節(jié)點(diǎn)為1，目標(biāo)節(jié)點(diǎn)為6，假設(shè)每個(gè)節(jié)點(diǎn)的能量為1800nJ，節(jié)點(diǎn)在活動(dòng)狀態(tài)時(shí)能耗為150nJ/h。

圖2　測(cè)試網(wǎng)絡(luò)Fig.2　Test network

為檢驗(yàn)A_OBDD算法性能，采用Colorado大學(xué)的CUDD軟件包[12]，在運(yùn)行平臺(tái)Windows7，IntelCorei3CPU3.07GHz，2GB的內(nèi)存環(huán)境下，計(jì)算圖2中基準(zhǔn)網(wǎng)絡(luò)在任意時(shí)刻t的可用度。分析節(jié)點(diǎn)活動(dòng)-睡眠狀態(tài)轉(zhuǎn)移概率對(duì)節(jié)點(diǎn)以及WSN可用度的影響。實(shí)驗(yàn)分析步驟為4步：

1)獲取節(jié)點(diǎn)變量序。首先存儲(chǔ)每層的節(jié)點(diǎn)集和邊集，節(jié)點(diǎn)集為：V[0]={1},V[1]={5,4},V[2]={2,3},V[3]={6},邊集為：U[0]={e1,e2}，U[1]={e3,e4,e5}，U[2]={e6,e7}。從節(jié)點(diǎn)1開始獲得邊集{e1,e2}，使用優(yōu)先函數(shù)選擇邊e2并獲得優(yōu)先節(jié)點(diǎn)4，于是給節(jié)點(diǎn)4編序2，使用同樣的方式給節(jié)點(diǎn)5編序3，所有與1相連的節(jié)點(diǎn)編序完成，本次循環(huán)結(jié)束。進(jìn)入下一次循環(huán)，為下一層節(jié)點(diǎn)編序，直到獲得變量序。最終獲得的變量序?yàn)棣?v1

2)構(gòu)造從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的OBDD。根據(jù)獲得的節(jié)點(diǎn)變量序遍歷網(wǎng)絡(luò)圖。從節(jié)點(diǎn)1開始，接下來(lái)是節(jié)點(diǎn)4和節(jié)點(diǎn)3，最后是目標(biāo)節(jié)點(diǎn)6。對(duì)于同一條路徑上的節(jié)點(diǎn)(1→4→3→6)進(jìn)行OBDD的與布爾操作，對(duì)于不同路徑上的節(jié)點(diǎn)(1→5→3→6,1→5→2→6)進(jìn)行OBDD的或布爾操作，直至構(gòu)造出整個(gè)WSN可用度函數(shù)的OBDD。最終得到測(cè)試網(wǎng)絡(luò)的OBDD如圖3所示。

圖3　測(cè)試網(wǎng)絡(luò)的OBDDFig.3　OBDD of test network

3)計(jì)算隨時(shí)間變化的節(jié)點(diǎn)可用度分布。為分析節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移概率對(duì)節(jié)點(diǎn)以及WSN可用度的影響，設(shè)λ=1.0，μ在[0.1,1.0]范圍內(nèi)變化，如表1所示，得到節(jié)點(diǎn)可用度Anode(t)函數(shù)如圖4所示。

表1　節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移概率

圖4　節(jié)點(diǎn)可用度Fig.4　Availability of sensor node

4)計(jì)算WSN的動(dòng)態(tài)可用度。WSN網(wǎng)絡(luò)可用的條件是至少存在一條由源節(jié)點(diǎn)vs到目標(biāo)節(jié)點(diǎn)vt的有效數(shù)據(jù)傳輸鏈路，使得數(shù)據(jù)成功傳輸。求解的WSN可用度為1葉子節(jié)點(diǎn)的概率值，該算法能夠精確地計(jì)算WSN的可用度，如圖5所示。

圖5　WSN可用度Fig.5　Availability of WSN

由此可以看出，A_OBDD算法可以計(jì)算WSN可用度，從而評(píng)估WSN網(wǎng)絡(luò)完成數(shù)據(jù)傳輸任務(wù)的能力。

另外，對(duì)同一個(gè)WSN測(cè)試網(wǎng)絡(luò)，給出5組不同的節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移概率，分別對(duì)WSN可用度進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果表明，WSN的可用度隨節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移概率的不同而改變，節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移對(duì)WSN可用度影響較大。對(duì)節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移概率的權(quán)衡，有助于設(shè)計(jì)者對(duì)傳感器節(jié)點(diǎn)進(jìn)行優(yōu)化。

4　結(jié)束語(yǔ)

WSN可用度問題是WSN網(wǎng)絡(luò)設(shè)計(jì)、部署、驗(yàn)證和維護(hù)階段的核心問題。傳感器節(jié)點(diǎn)是能量有效、資源有限的節(jié)點(diǎn)，為了節(jié)省能量，采用“活動(dòng)/睡眠”策略，使用馬爾科夫鏈描述節(jié)點(diǎn)行為的變化，并計(jì)算了不同的“活動(dòng)/睡眠”轉(zhuǎn)移概率對(duì)節(jié)點(diǎn)性能的影響。這對(duì)設(shè)計(jì)者設(shè)計(jì)網(wǎng)絡(luò)節(jié)點(diǎn)，提高WSN網(wǎng)絡(luò)壽命具有一定的指導(dǎo)作用。對(duì)馬爾科夫鏈下的WSN可用度進(jìn)行分析，并給出了A_OBDD算法。該算法利用廣度優(yōu)先搜索法遍歷網(wǎng)絡(luò)圖給出變量序，結(jié)合利用OBDD的“與”布爾操作和“或”布爾操作構(gòu)建WSN可用度函數(shù)OBDD，計(jì)算隨時(shí)間變化的節(jié)點(diǎn)可用度分布，通過遍歷OBDD計(jì)算出WSN動(dòng)態(tài)可用度。

實(shí)驗(yàn)結(jié)果表明，不同節(jié)點(diǎn)轉(zhuǎn)移概率對(duì)WSN可用度影響較大，符號(hào)A_OBDD算法可有效評(píng)估WSN可用度，降低了WSN可用度分析的復(fù)雜性，并且有助于設(shè)計(jì)者對(duì)WSN網(wǎng)絡(luò)進(jìn)行設(shè)計(jì)、優(yōu)化和維護(hù)。

為了更好地節(jié)省能量，WSN還可以采用睡眠、傳遞、等待、接收、閑置5種狀態(tài)轉(zhuǎn)化策略，該策略下WSN可靠性及可用度分析是未來(lái)的一個(gè)研究方向。

[1]ABOELFOTOHHMF,HOSAMMF,IYENGARSS,etal.Computingreliabilityandmessagedelayforcooperativewirelessdistributedsensornetworkssubjecttorandomfailures[J].IEEETransactionsonReliability,2005,54(1):145-155.

[2]閆宗帥,董榮勝.一種基于OBDD的WSN可靠性評(píng)估方法[J].桂林電子科技大學(xué)學(xué)報(bào),2014,34(5):411-416.

[3]CHANGYR,AMARISV,KUOSY.ComputingsystemfailurefrequenciesandreliabilityimportancemeasuresusingOBDD[J].IEEETransactionsonComputers,2004,53(1):54-68.

[4]GUTianlong,XUZhoubo.Thesymbolicalgorithmsformaximumflowinnetworks[J].ComputersandOperationsResearch,2007,34(3):799-816.

[5]徐周波,古天龍,趙嶺忠.網(wǎng)絡(luò)最大流問題的一種新的符號(hào)ADD求解算法[J].通信學(xué)報(bào),2005,26(2):1-8.

[6]XIAOYufeng,LIXin,LIYuhong,etal.EvaluateReliabilityofwirelesssensornetworkswithOBDD[C]//IEEEInternationalConferenceonCommunications,2009:1-5.

[7]董榮勝,馬爭(zhēng)先,郭云川,等.一種基于馬爾可夫博弈的能量均衡路由算法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(7):1500-1508.

[8]BRUNED,PULIAFITOA,SCARPAM.Dependabilityanalysisofwirelesssensornetworkswithactive-sleepcyclesandredundantnodes[C]//ProceedingsoftheFirstWorkshoponDynamicAspectsinDependabilityModelsforFault-tolerantSystems,2010:25-30.

[9]CHIASSERINICF,GARETTM.Modelingtheperformanceofwirelesssensornetworks[J].ProceedingsIEEEINFOCOM,2004(1):220-231.

[10]LIUJianming,TONGL.Aframeworkforperformancemodelingofwirelesssensornetworks[C]//IEEEInternationalConferenceonCommunications,2005:1075-1081.

[11]古天龍.有序二叉決策圖及應(yīng)用[M].北京:科學(xué)出版社,2009:22-111.

[12]SOMENZIF.CUDD:CUdecisiondiagrampackagerelease2.4.1[J].PCWorld,2005,67(4):595-599.

編輯：梁王歡

An OBDD-based method for availability evaluation of WSN

ZHANG Xiaohua, DONG Rongsheng

(School of Computer and Information Security, Guilin University of Electronic Technology, Guilin 541004, China)

To reduce the energy consumption of sensor nodes and increase availability of wireless sensor networks, the discrete probability model of availability assessment is proposed, based on this model, a symbolic algorithm A_OBDD is given. To realize the dynamic assessment of the availability of nodes, Markov chain is used to describe process of state transition. The ordered binary decision diagrams are introduced to effectively relieve the combination explosion. The experimental results show that WSN availability is greatly influenced by node state transition probability and can be evaluated effectively by A_OBDD algorithm.

wireless sensor networks; availability; energy constrain; Markov chain; ordered binary decision diagrams

2015-12-29

國(guó)家自然科學(xué)基金(61363070)

董榮勝(1965-)，男，湖北黃岡人，教授，研究方向?yàn)橛?jì)算思維、網(wǎng)絡(luò)可靠性、形式化技術(shù)。E-mail:ccrsdong@guet.edu.cn

TP302.7

A

1673-808X(2016)03-0210-05

引文格式： 張曉花，董榮勝.基于OBDD的無(wú)線傳感器網(wǎng)絡(luò)可用度算法[J].桂林電子科技大學(xué)學(xué)報(bào)，2016,36(3)：210-214.