趙 濤

(安徽財經大學 計算機科學與技術系，安徽 蚌埠233000)

0 引 言

在現有傳感器網絡鏈路丟失率推測算法中［1～4］，一般都存在鏈路報文丟失時間無關假設，即認為上一個通過該鏈路的報文丟失不會對下一報文丟失概率產生影響。但在實際的傳感器網絡中，報文丟失的主要原因有緩沖區(qū)溢出、干擾等，鏈路發(fā)生報文丟失事件，意味著該鏈路出現擁塞，干擾或節(jié)點失效，這就使得下一個通過此鏈路的報文丟失概率增大。因此，報文丟失在時間上具有較強相關性。

Gilbert 概率模型是一個兩狀態(tài)的馬爾科夫模型，描述兩個不同時間發(fā)生的依賴關系。為解決報文丟失時間相關性問題，本文用Gilbert 概率模型來描述鏈路報文丟失過程，將Gilbert 模型下的鏈路報文丟失率推測形式化為Bayesian 概率問題，并用Gibbs 抽樣算法來獲得鏈路丟失率的推測值。

1 系統(tǒng)模型

傳感器網絡受能量和帶寬限制，常使用數據匯聚方法收集數據［5，6］，節(jié)點在收集所有子節(jié)點數據后，將數據發(fā)送至下一跳節(jié)點(父節(jié)點)，直至最后匯聚到Sink 節(jié)點。這種匯聚方法通過一個倒立的匯聚樹將數據傳送到Sink 節(jié)點，已經成為延長傳感器網絡生命能量周期普遍使用的方法。

1.1 網絡拓撲模型

用T=(V，L)描述匯聚過程的倒立匯聚樹，V 為匯聚過程中所參與傳感器節(jié)點集合，L 為節(jié)點間的鏈路集合。n為匯聚過程中節(jié)點個數，用s 表示匯聚樹的根節(jié)點，即傳感器網絡的Sink 節(jié)點。用節(jié)點對(i，j)∈V×V 表示匯聚樹中的鏈路(數據從節(jié)點i 發(fā)送至節(jié)點j)，節(jié)點j 是節(jié)點i 的父節(jié)點，用f(i)表示，子節(jié)點集合用c(i)表示，d(i)表示子孫節(jié)點集合。

1.2 報文丟失模型

用隨機過程Z=(zi，j)，i∈d(j)，j∈V 表示匯聚樹的數據流，用參數對(pi，qi)表示鏈路l∈L 的時間相關丟失率參數，其中，p 為當前報文通過，下一報文丟失概率;q 為當前報文丟失，下一個報文通過概率。假設傳感器網絡中所有節(jié)點每一輪都發(fā)送數據到Sink節(jié)點，在每輪數據發(fā)送結束后，在Sink 節(jié)點可獲得各節(jié)點發(fā)送數據成功或失敗信息，用向量表示，其中表示節(jié)點k 的數據在第m 輪數據匯聚中是否到達Sink 節(jié)點。用向量Xk=表示在N 輪數據匯聚過程中，節(jié)點k 每輪數據成功發(fā)送情況。0 表示丟失，1 表示成功到達。

2 推測算法

2.1 Gibbs 抽樣推測報文丟失率算法

在數據收集結束后，根據統(tǒng)計測量結果Xk推測鏈路的參數對(pk，qk)的數值。一般來說，在網絡邏輯拓撲和報文丟失模型已知的情況下，可利用測量結果推導出導致該結果的聯合概率p(Θ|X)，利用Bayesian 推測方法推測出參數值，使后驗概率p(Θ|X)取得最大值。

Beta 分布經常作為報文丟失的先驗概率分布，假設鏈路報文丟失的先驗概率符合Beta 分布

圖1 描述了使用Gibbs 抽樣方法計算鏈路報文丟失率，再將此方法擴展至一般網絡。

圖1 簡單的數據匯聚樹Fig 1 A simple data aggregation tree

圖1 三條鏈路對應的報文丟失率分別為θ1=(p1，q1)，θ2=(p2，q2)，θ3=(p3，q3)。算法用測量值Xk去推測Θ={(p1，q1)，(p2，q2)，(p3，q3)}。用表示在第m－1 輪節(jié)點j 成功接收到節(jié)點i 報文的情況下，第m 輪節(jié)點j 接收節(jié)點i 報文的情況;用表示在第m－1 輪節(jié)點j 沒有接收到節(jié)點i 報文的情況下，第m 輪節(jié)點j 接收節(jié)點i 報文的情況。令P=［p1，p2，p3］，Q=［q1，q2，q3］，先以計算P=［p1，p2，p3］為例，根據圖1 所示拓撲中鏈路之間的關系可以推導出下面公式(2)

其中

將式(1)、式(3)和式(4)代入式(2)中，可得式(5)

根據公式(5)，可以看出邏輯鏈路的后驗報文丟失P=［p1，p2，p3］的概率分布仍然是Beta 分布，每條邏輯鏈路報文丟失率對應的Beta 分布分別為

根據后驗概率分布式(6)～式(8)，用Gibbs 抽樣方法連續(xù)抽樣，就可得到{p1，p2，p3}和{z2，1，z3，1，z4，1}的抽樣數據，就可以利用式(9)計算{p1，p2，p3}的估計值

同理，可以完成對{q1，q2，q3}的計算。

2.2 算法描述

將算法擴展到一般網絡中，數據共采集J=J0+J1次，J0是到達穩(wěn)態(tài)所需數據收集次數。算法首先依據先驗概率分布抽取Θ(0)和Z(0)，然后利用測量值抽取Θ 和Z 并計算詳細描述如下:

Initialization:Draw random samplesΘ(0)and Y(0)from theirprior.

Sample:for j=1，2，…，J do

·GivenΘ(j)，for k∈V{s}，for m=1，2，…，N，draw a sample

3 仿真實驗

用NS2［7］模擬傳感器網絡數據匯聚過程，鏈路報文丟失率(p，q)預先設定。仿真中采用兩種網絡拓撲結構，9 節(jié)點網絡現150 節(jié)點網絡，分別驗證算法準確性和可擴展性。每種拓撲結構下分別模擬兩種場景下的報文丟失情況:無丟失嚴重鏈路和有丟失嚴重鏈路。正常鏈路丟失率設置為(10%，85%)，丟失嚴重鏈路為(15%，80%)。

9 節(jié)點網絡仿真結果如圖2～圖5 所示，從圖2，圖3 中可以看出:無丟失嚴重鏈路場景中，丟失率推測值和預設值非常接近;在有丟失鏈路場景中，預設值和推測值同樣較為吻合，但靠近葉子節(jié)點的推測值誤差稍大，其主要原因是將在父節(jié)點丟失的報文歸結于子節(jié)點發(fā)送丟失?？傮w來說，其推測誤差都在1%內，說明算法可以較好地完成鏈路丟失率推測。

圖2 無丟失嚴重鏈路:預先設置參數p 與推測值p 的比較Fig 2 No heavy loss link scenarios:ture loss rate p vs inferred loss rate p

圖3 無丟失嚴重鏈路:預先設置參數q 與推測值q 的比較Fig 3 No heavy loss link scenarios:ture loss rate q vs inferred loss rate q

圖4 有丟失嚴重鏈路:預先設置參數p 與推測值p 的比較Fig 4 Heavy loss link scenarios:ture loss rate p vs inferred loss rate p

圖5 有丟失嚴重鏈路:預先設置參數q 與推測值q 的比較Fig 5 Heavy loss link scenarios:ture loss rate q vs inferred loss rate q

表1 是150 節(jié)點網絡拓撲的仿真結果，從表中可以看出:隨著網絡規(guī)模的擴大，推測誤差并沒有呈幾何級數增加，推測值依然很接近預設值。在仿真過程中，誤差的最大值仍然小于1%。說明算法的可伸縮性較好，推測值的誤差值不會隨著網絡規(guī)模的增加而變大。

4 結 論

本文提出一種傳感器網絡鏈路時間相關丟失率推測算法，將傳感器網絡邏輯鏈路報文丟失推測問題形式化為Bayesian 推測問題，并采用Gibbs 抽樣方法來解決。采用NS2 仿真工具進行算法的有效性和可伸縮性驗證，結果表明:算法可較準確地推測出鏈路報文丟失率，且伸縮性較好。

表1 150 節(jié)點網絡拓撲的仿真結果Tab 1 Simulation result of 150-node network topology

［1］ Shah－Mansouri V，Wong S.Link loss inference in wireless sensor networks with randomized network coding［C］∥Global Telecommunications Conference(GLOBECOM 2010)，Miami，Florida，USA:IEEE，2010:1－6.

［2］ Yu Yang，Xu Yongjun，Li Xiaowei，et al.A loss inference algorithm for wireless sensor networks to improve data reliability of digital ecosystems［J］.IEEE Transactions on Industrial Electronics，2011，58(6):2126－2137.

［3］ J Wenli，G Teng，J Meiyin，et al.Researching topology inference based on end－to－end date in wireless sensor networks［C］∥2011 International Conference o Intelligent Computation Technology and Automation(ICICTA)，Changsha，China:IEEE，2011:683－686.

［4］ Y Xunqi，W Modestino，T Xusheng.The accuracy of Gilbert models in predicting packet－loss statistics for a single－multiplexer network model［C］∥INFOCOM 24th Annual Joint Conference of the IEEE Computer and Communications Societies，Miami，FL，USA:IEEE，2005:2602－2612.

［5］ Hartl G，Li Baochun.Loss inference in wireless sensor networks based on data aggregation［C］∥Third International Symposium on Information Processing in Sensor Networks，Berkeley，California，USA:IEEE，2005:396－404.

［6］ Yu Yang，Xu Yongjun，Li Xiaowei.Topology tomography in wireless sensor networks based on data aggregation［C］∥International Conference on Communications and Mobile Computing，Leipzig，Germany:IEEE，2009:37－41.

［7］ The network simulator NS－2［DB/OL］.［2011—11—05］.http:∥www.isi.edu/nsnam/ns/.