無線傳感器網絡的可靠性計算

（中國科學院 研究生院 a.數學科學學院; b.工程教育學院，北京 100049)



摘要：

主要研究無線傳感器網絡的傳輸可靠性計算問題。針對傳感器網絡的特性，對無線傳感器的節點和鏈路都有失敗概率的情況，提出一種計算網絡傳輸可靠性的分解算法，分析了算法的計算復雜性，并通過算例演示了算法的可行性。

關鍵詞：無線傳感器網絡； 可靠性； 分簇

中圖分類號：TP802文獻標志碼：A

文章編號：10013695(2009)03098704



Computing reliability of wireless sensor network



XU Rana，b， GAO Suixianga， DONG Pinga， HUANG Feia



(a.College of Mathematical Sciences，b. College of Engineering， Graduate School， Chinese Academy of Sciences， Beijing 100049，China)



Abstract:

This paper mainly researched the transmission reliability of wireless sensor network. Aiming at the wireless sensor network， presented a factorability algorithm to compute reliability accounting for unreliable sensors and edges. Besides， analyzed the complexity of algorithm and the algorithm was feasible by demonstrating an example.

Key words：wireless sensor network; reliability; cluster;



無線傳感器網絡(wireless sensor networks)是近幾年出現的一種新的無線通信網絡技術，它由部署在監測區域內大量的廉價微型傳感器節點組成，通過無線通信方式形成一個多跳的自組織網絡系統。其目的是協作地感知、采集和處理網絡覆蓋區域中感知對象的信息，并發送給觀察者。它的應用前景十分廣闊，如交通監控、城市管理、環境監測、搶險救災、危險區域遠程控制、戰場信息收集等領域都可用到傳感器網絡。

目前國內外對無線傳感器網絡的研究主要集中在路由協議的設計、數據融合的應用、MAC層設計、拓撲控制算法和時間同步機制等方面，以及一些硬件平臺的設計與操作系統的研究[1]。與這些研究相比，本文更注重于一個網絡運行的穩定性及傳輸數據的準確性和完整性，這集中體現為無線傳感器網絡的可靠性，它是大規模無線傳感器網絡走向實際應用所需解決的關鍵問題之一。目前對無線傳感器網絡可靠性的研究還不是很多。文獻[2]提出基于事件到sink節點的傳感器網絡可靠性，并據此給出了一種可靠的傳輸協議ESRT；文獻[3]研究了使用多路徑的轉發協議來提高網絡的可靠性；文獻[4]研究在邊不可靠的情況下，使用分解算法求解一般網絡可靠性的問題；文獻[5]考慮節點不可靠情況下，使用分解算法求解一般網絡的可靠性，它假設一條邊的兩個端點至少有一個是可靠的。但在實際的傳感器網絡中，所有的節點均不可靠。本文考慮傳感器節點以及節點間的鏈路都以一定的概率正常工作時網絡的可靠性問題，提出求解傳感器網絡可靠性的一種改進的分解算法。

1術語與符號

按照網絡中節點的運行功能不同，本文將傳感器網絡的節點分為三類：a）sink節點，是無線傳感器網絡與外界聯系的橋梁，負責收集其他節點傳來的數據信息；b)中轉節點，主要負責數據的多跳轉發，也可以采集數據；c)采集節點，只負責采集數據并將自身采集的數據轉發給下一跳的中轉節點或者sink點。

假設無線傳感器網絡只有一個sink節點，地理位置接近的采集節點形成簇，簇中所有的節點均無區別，采集到的數據內容相同，且其節點擁有相同的ID。簇中的每個節點都將采集到的數據轉發給下一跳的中轉節點或sink節點；位于不同簇的采集節點可以使用同一個中轉節點。簇與簇之間無數據交換，整個網絡以及鏈路（節點與邊）的工作狀態是統計獨立的。傳感器網絡中節點的能量有限，節點不完全可靠，而是以一定的概率正常工作。節點間的無線鏈路受到環境因素、信道誤差等因素的影響，也以一定的概率正常工作。為了后續敘述方便，介紹如下術語和記號：

a)G（V，E），由傳感器網絡的路由拓撲形成的路由網絡。其中傳感器節點集合為 V，V={t1，t2，…，tn}；節點之間的邊集合為 E，E={e1，e2，…，em}。以下將G(V，E)稱為傳感器網絡，簡記為G。

b)Rel(G)，傳感器網絡G的可靠性。

c）G-e，圖G的邊e被刪除，保留e的兩個端點。

d)G*e，圖G的邊e被收縮，指從圖 G中刪除邊e，并將邊e的兩個端點粘合在一起，使得兩個端點重合為一個端點。

e)Ci，采集節點組成的第i個簇。

f)Gi，簇Gi中的節點，以及這些節點使用的中轉節點和sink點組成的網絡。

g)Rel(Gi)，網絡中第i個簇的可靠性。

h)Pti，表示節點 ti的正常工作概率。

i)Pei，表示邊ei的正常工作概率。

j)子網絡，由一個網絡G通過刪除邊操作或者收縮邊操作得到的網絡。

2問題闡述與算法

2.1問題描述

根據不同的分簇算法，將傳感器網絡中的節點分組，每一組稱為一個簇。在分簇結構下的傳感器網絡的某些應用中，監測的可靠性依賴于目標簇中所有節點共同采集的數據[6]，而不是個別節點的數據，所以個別節點的失效可能不會對網絡的監測結果造成影響。本文定義簇Ci的可靠性為：簇Ci中至少有一個節點到匯聚節點（sink節點）有路的概率。其中“有路”是指簇中一個節點的數據經過一跳或者多跳能夠到達sink點。假設任兩個簇不相交且簇與簇之間的節點不進行數據交換，因此整個網絡的傳輸可靠性定義為所有簇的可靠性之積，即Rel(G)=Πki=1Rel(Gi)?？梢娬麄€網絡的傳輸可靠性問題可歸結為求每個簇的可靠性。本文所要考慮的問題可確切地描述如下：在一個具有中轉節點的簇狀采集網絡中，設已知各個節點的正常工作概率和每條鏈路的正常工作概率，求整個網絡G（V，E）的傳輸可靠性。

網絡的“分解”是指對網絡的一條邊進行收縮和刪除運算獲得兩個子網絡的過程。例如，對于圖1（a）所示的網絡G，收縮邊a得到圖G*a(圖1(b))，刪除邊a得到圖G-a（圖1（c））。

對網絡G進行一次分解后，其可靠性可化為子網絡的可靠性[7]:

Rel(G)=PeRel(G*e)+(1-Pe)Rel(G-e)(1)

每次分解都會將網絡一分為二，得到子網絡G*e和G-e；再分別對兩個子網絡遞歸地進行分解，直到子網絡的可靠度為1或者0時，停止分解。此時按式(1)遞推，便可求出網絡G的可靠性。

對于無線傳感器網絡，不能直接使用式（1）計算可靠性，因為這個公式只考慮邊的可靠性而未考慮節點的可靠性。而在傳感器網絡中傳感器節點和鏈路均不可靠，因此需要建立新的分解公式。

在傳感器網絡中，只有當節點與其傳輸鏈路（邊）都處于正常工作的狀態時，數據才能被成功轉發。對節點u及其出邊e=(u，v)，數據被成功轉發的概率為PuPe，它對應于邊e的收縮，表示點u通過邊e可以將數據成功轉發；如果節點u或者鏈路e有一者失效，則數據不能被成功轉發，其概率為1-PuPe，它對應于邊e的刪除，表示數據不能從u成功轉發。因此網絡的傳輸可靠性應為

Rel(G)=PuPeRel(G*e)+(1-PuPe)Rel(G-e)(2)

這里可以從另一個角度來分析式（2）的正確性：原來的分解式（1）每條邊的概率與式（2）中點的概率和邊的概率之積相對應，而這種對應是一對一的，即一般圖的邊概率Pe一一對應于傳感器網絡的點邊概率PuPe，所以可以把傳感器網絡中點的概率與邊的概率的乘積看成一個新網絡的邊的概率，對這個新的網絡使用式(1)，便得到式(2)。

2.2算法思想

給定無線傳感器網絡G（V，E），設 G有m個簇，分別為C1，C2，…，Cm。簇 Ci中的節點以及這些節點使用的中轉節點、sink點組成的網絡記為Gi，每個簇的可靠性就是指圖Gi的傳輸可靠性。對簇Gi對應的網絡Gi進行遞推分解，每次分解都將網絡一分為二。分解方法為任選Gi的一條邊e，對邊e分別進行收縮和刪除操作，得到兩個子網絡Gi*e和Gi-e；然后依次序先對Gi*e進一步分解，將Gi*e分解結束后，再考慮對Gi-e進行分解。每個子網絡使用式(2)遞推分解到出現下列情況之一時結束：a）簇中某一個采集節點與sink點重合，此時表明采集節點到sink點有路，得到的子網絡的可靠性為1；b）簇中所有的采集節點與sink點都不連通，此時得到的子網絡的可靠性為0。每次分解都使用式（2）計算可靠性，因此網絡Gi分解的過程給出了式（2）遞推迭代的計算過程。在反復對邊進行刪除和收縮運算時，網絡中可能會出現并行邊，即兩個節點之間有兩條邊連接，此時進行如下處理[8]：若ei=(u，v)，ej=(u，v)為兩條并行邊，則用一條邊ek代替ei與ej，ek=(u，v)，且Pek=1-PeiPej，用1-P2u×Pei×Pej代替式(1)中的Pe，得到的新圖G′，并且Rel(G)=Rel(G)。

2.3算法步驟

根據上述算法思想的描述，本文用偽代碼方式寫出算法具體的步驟：

Rel(G)

input：無線傳感網絡G，G的每個頂點的正常工作概率與每條邊的正常工作概率；

output：圖 G的可靠性Rel(G);

begin

{圖G有n個簇，記為Gi，Rel(G)=1;

for(i=1，2，…，n)

Rel(Gt);

Rel(G)=Rel(G1)*Rel(G)

return Rel(G);

}

Rel(G)

{ begin：{分解}

從圖G中任選條邊e，e=(u，v)，然后刪去此邊；

if該邊使得所有采集節點與sink節點都不連通

則P1=0；

else

P1=Rel(G-e)；

收縮邊 e；G←G*e；

if收縮該邊使得采集節點與sink節點重合

則 P2=1；

else

P2=Rel(G)；

在圖G中進行并行邊收縮；

L1=(1-PuPe)，L2=PuPe；

return(L1*P1+L2*P2)；

end{分解}

end

2.4復雜性分析

算法的執行過程[9]是二叉樹的遞歸搜索過程，可以把每個Gi的分解過程看成：樹的根節點為Gi，其左右孩子為Gi*e和Gi-e，其中e=(u，v)；父節點與左右孩子節點之間邊的賦權為PuPe和1-PuPe。這樣遞歸生成一棵二叉樹，設其節點數為N(Gi)，且N(Gi)=2|Ei|+1。其中|Ei|為Gi的邊數，葉子節點數為L(Gi)=(N(Gi)+1)/2，生成的該樹層數最多為|Ei|。使用式(2)得到的最終的展開式中，一共有2|Ei|項相加，每一項最多要做|Ei|次乘法，所以展開式中乘法次數最多為2|Ei||Ei|，加法次數為2|Ei|-1。設Gi一次刪除邊操作或一次收縮邊操作需要一次運算量，Gi的總的刪除和收縮操作運算量等于二叉樹節點個數N(Gi)，所以需要2|Ei|+1次運算，且每個簇的運算量為2|Ei||Ei|+2|Ei|-1+2|Ei|+1=2|Ei|(|Ei|+2)。所以計算每個簇的時間復雜度至多為O(2|Ei||Ei|)，i=1，2，…，M；用分解算法得到整個網絡的復雜度至多為O(M#8226;2|Ei||Em|)。其中：M是簇的個數；m是指邊數最多的那個簇的下標。

3算例演示

不妨設網絡只有一個簇C，簇中的點為{1，2，3}，它們與中轉節點、sink節點構成的路由網絡結構G如圖1（a）所示。圖1中兩個圓圈的重疊表示兩個節點的重合，根據本文的算法求其可靠性，步驟如下：

任選圖G的一條邊，如選邊a，進行收縮和刪除運算，結果得到G*a和G-a，見圖1（b）(c)。

Rel(G)=p1paRel(G*a)+(1-p1pa)Rel(G-a)(3)

再對網絡G*a進行分解。任選其一條邊f，進行收縮和刪除運算，得到兩個網絡G*a*f和G*a-f。由于收縮邊f使得簇中節點1與s重合，故Rel(G*a*f)=1。由分解公式得

Rel(G*a)=P4PfRel(G*a*f)+(1-P4Pf)Rel(G*a-f)=

P4Pf+(1-P4Pf)Rel(G*a-f)(4)

繼續對式(4)中的圖G*a-f進行分解，如圖2所示。選邊b，按公式分解得到

Rel(G*a-f)=P1PbRel((G*a-f)*b)+(1-P1Pb)Rel((G*a-f)-b)(5)

對式(5)中圖(G*a-f)*b任選邊g進行分解，得到(G*a-f)*b*g和(G*a-f)*b-g，見圖2（c）（d）。因收縮邊g后，節點1和s重合，所以Rel((G*a-f)*b*g)=1，而

Rel((G*a-f)*b)=P5PgRel((G*a-f)*b*g)+(1-P5Pg)Rel((G*a-f)*b-g)=P5Pg+(1-P5Pg)Rel((G*a-f)*b-g)(6)

對式(6)中的圖(G*a-f)*b-g進行分解，如圖3所示。任選邊d，按照分解公式有

Rel((G*a-f)*b-g)=P2PdRel(((G*a-f)*b-g)*d)+(1-P2Pd)Rel(((G*a-f)*b-g)-d)(7)

對式(7)中的圖((G*a-f)*b-g)*d選邊h進行收縮和刪除，按分解公式有

Rel(((G*a-f)*b-g)*d)=P6PhRel(((G*a-f)*b-g)*d*h)+(1-P6Ph)Rel(((G*a-f)*b-g)*d-h)（8）

因為收縮邊h使得簇中節點2與s重合，刪除邊h使得簇中所有的節點與點s斷開，故Rel(((G*a-f)*b-g)*d*h)=1，Rel(((G*a-f)*b-g)*d-h)=0。將此兩式代入式(8)得

Rel((G*a-f)*b-g)*d=P6Ph(9)

下面返回到式(7)，求網絡(((G*a-f)*b-g)-d的可靠性。任選邊e進行收縮和刪除操作后，得到兩個子網絡，如圖4所示，按分解公式，有

Rel(((G*a-f)*b)-g-d)=P3PeRel(((G*a-f)*b-g-d)*e)+(1-P3Pe)Rel(((G*a-f)*b-g-d)-e)(10)

對式(10)中圖((G*a-f)*b-g-d)*e分解。任選邊h，按公式有

Rel(((G*a-f)*b-g-d)*e)=P6PhRel(((G*a-f)*b-g-d)*e*h)+(1-P6Ph)Rel(((G*a-f)*b-g-d)*e-h)（11）

因收縮邊h使得簇中節點3與s重合，刪除邊h使得簇中所有節點與s都斷開，所以Rel(((G*a-f)*b-g-d)*e*h)=1，Rel(((G*a-f)*b-g-d)*e-h)=0。將此兩式代入到式（11）中，得：

Rel(((G*a-f)*b-g-d)*e)=P6Ph

對式（10）中的網絡(G*a-f)*b-g-d-e而言，刪除邊e使得簇中所有節點都與點s斷開，故

Rel(((G*a-f)*b-g-d)-e)=0(12)

將式(12)(13)代入到式(9)中有

Rel((G*a-f)*b-g-d)=P3PeP6Ph(13)

再將式(9)(13)代入到式(7)中，得

Rel((G*a-f)*b-g)=P2PdP6Ph+(1-P2Pd)P3PeP6Ph（14）

將式(14)代入到式(6)中得

Rel((G*a-f)*b=P5Pg+(1-P5Pg)[P2PdP6Ph+(1-P2Pd)P3PeP6Ph]（15）

下面返回到式(5)，求其中G*a-f-b的可靠性。任選網絡G*a-f-b的邊c進行分解，按分解公式有

Rel(G*a-f-b)=P2PcRel((G*a-f-b)*c)+(1-P2Pc)Rel((G*a-f-b)-c)（16）

接著對式(16)中(G*a-f-b)*c進行分解，如圖5所示。任選邊g，因收縮邊g使得簇中節點2與s重合，所以Rel((G*a-f-b)*c*g=1，從而

Rel((G*a-f-b)*ci)=P5PgRel((G*a-f-b)*c*g)+(1-P5Pg)Rel((G*a-f-b)*c-g)=P5Pg+(1-P5Pg)Rel((G*a-f-b)*c-g)（17）

繼續對式(17)中的(G*a-f-b)*c-g進行分解，如圖6所示。選邊d，按分解公式得到

Rel((G*a-f-b)*c-g)=P2PdRel(((G*a-f-b)*c-g)*d)+(1-P2Pd)Rel((G*a-f-b)*c-g)-d)（18）

對式(18)中網絡((G*a-f-b)*c-g)*d，任選邊h進行分解，按分解公式有

Rel(((G*a-f-b)*c-g)*d)=P6PhRel(((G*a-f-b)*c-g)*d*h)+(1-P6Ph)Rel(((G*a-f-b)*c-g)*d-h)(19)

因為收縮邊h使得簇中節點2與s重合，而刪除邊h使得簇中所有節點與s斷開，所以Rel(((G*a-f-b)*c-g)*d*h)=1，Rel(((G*a-f-b)*c-g)*d-h)=0。將此兩式代回到式（19）得

Rel(((G*a-f-b)*c-g)*d)=P6Ph（20）

下面返回式(18)，考慮其中網絡((G*a-f-b)*c-g)-d，如圖7所示。任選邊e進行分解有

Rel(((G*a-f-b)*c-g)-d)=P3PeRel((((G*a-f-b)*c-g)-d)*e)+(1-P3Pe)Rel((((G*a-f-b)*c-g)-d)-e)（21）

對式(21)中的網絡(((G*a-f-b)*c-g)-d)*e，任選邊h進行分解，得

Rel((((G*a-f-b)*c-g)-d)*e)=P6PhRel((((G*a-f-b)*c-g)-d)*e*h)+(1-P6Ph)Rel((((G*a-f-b)*c-g)-d)*e-h)（22）

由于收縮邊h使得簇中節點3與s重合，刪除邊h使得該簇中所有節點與s斷開，因此Rel((((G*a-f-b)*c-g)-d)*e*h)=1，Rel((((G*a-f-b)*c-g)-d)*e-h)=0。將此兩式代入式(22)中得

Rel((((G*a-f-b)*c-g)-d)*e)=P6Ph（23）

返回式(21)中求網絡(((G*a-f-b)*c-g)-d)-e的可靠性。由于刪除e使得所有節點與s斷開，則有

Rel((((G*a-f-b)*c-g)-d)-e)=0(24)

式(23)(24)代回到式(21)中得

Rel((G*a-f-b)*c-g-d)=P6PhP3Pe（25）

式(20)(25)代到式(17)中得Rel((G*a-f-b)*c-g)=[P2PdP6Ph+(1-P2Pd)P3PeP6Ph]；將此式代入到式(17)中，得到

Rel((G*a-f-b)*c)=P5Pg+(1-P5Pg)[P2PdP6Ph+(1-P2Pd)P3PeP6Ph]（26）

現在返回式(16)，求網絡(G*a-f-b)-c的可靠性。任選邊d對網絡進行分解，有

Rel((G*a-f-b)-c)=P2PdRel(((G*a-f-b)-c）*d)+(1-P2Pd)Rel(((G*a-f-b)-c)-d)（27）

繼續對式(27)中的((G*a-f-b)-c)*d進行分解，如圖8所示。任選邊h，按照分解公式，有

Rel(((G*a-f-b)-c)*d=P6PhRel(((G*a-f-b)-c)*d*h)+(1-P6Ph)Re(((G*a-f-b)-c)*d-h)（28）

因收縮邊h使得簇中節點2與s重合，刪除邊h使得簇中所有節點與s斷開，所以Rel(((G*a-f-b)-c)*d*h)=1，Rel(((G*a-f-b)-c)*d-h)=0。將此兩式代入式（28）中，得

Rel((((G*a-f-b)-c)*d)=P6Ph(29)

現返回式(27)對網絡((G*a-f-b)-c-d)進行分解，如圖9所示。任選邊e，因刪除邊e使得簇中節點與s斷開，故有Rel(((G*a-f-b)-c)-d-e)=0。按分解公式得

Rel(((G*a-f-b)-c)-d)=P3PeRel((((G*a-f-b)-c)-d)*e)+(1-P3Pe)Rel((((G*a-f-b)-c)-d)-e)=P3PeRel((((G*a-f-b)-c)-d)*e)(30)

對式(30)的網絡(((G*a-f-b)-c)-d)*e進行分解。任選邊h，因收縮邊h使得簇中節點3與s重合，刪除邊h使得簇中所有節點與s斷開，所以有Rel((((G*a-f-b)-c)-d)*e*h)=1，Rel((((G*a-f-b)-c)-d)*e-h)=0。故Rel((((G*a-f-b)-c)-d)*e)=P6PhRel((((G*a-f-b)-c)-d)*e*h)+(1-P6Ph)Rel((((G*a-f-b)-c)-d)*e-h)=P6Ph。將此式代入式(30)中得到

Rel(((G*a-f-b)-c)-d)=P3PeP6Ph（31）

將式(29)(31)代回到式(27)中得

Rel((G*a-f-b)-c)=P2PdP6Ph+(1-P2Pd)P3PeP6Ph(32)

再將式(26)(32)代入到式(16)中得

Rel(G*a-f-b)=P2PcP5Pg+(1-P2PcP5Pg)[P2PdP6Ph+(1-P2Pd)P3PeP6Ph](33)

將式(15)(33)代入到式(5)中得Rel(G*a-f-b)=P1Pb[P5Pg+(1-P5Pg)×X]+（1-P1Pb)[P2PcP5Pg+(1-P2PcP5Pg)×X]。其中X=[P2PdP6Ph+(1-P2Pd)P3PeP6Ph]。