趙 濤

(安徽財(cái)經(jīng)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，安徽 蚌埠233000)

0 引 言

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

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

1 系統(tǒng)模型

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

1.1 網(wǎng)絡(luò)拓?fù)淠Ｐ?/h3>

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

1.2 報(bào)文丟失模型

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

2 推測(cè)算法

2.1 Gibbs 抽樣推測(cè)報(bào)文丟失率算法

在數(shù)據(jù)收集結(jié)束后，根據(jù)統(tǒng)計(jì)測(cè)量結(jié)果Xk推測(cè)鏈路的參數(shù)對(duì)(pk，qk)的數(shù)值。一般來說，在網(wǎng)絡(luò)邏輯拓?fù)浜蛨?bào)文丟失模型已知的情況下，可利用測(cè)量結(jié)果推導(dǎo)出導(dǎo)致該結(jié)果的聯(lián)合概率p(Θ|X)，利用Bayesian 推測(cè)方法推測(cè)出參數(shù)值，使后驗(yàn)概率p(Θ|X)取得最大值。

Beta 分布經(jīng)常作為報(bào)文丟失的先驗(yàn)概率分布，假設(shè)鏈路報(bào)文丟失的先驗(yàn)概率符合Beta 分布

圖1 描述了使用Gibbs 抽樣方法計(jì)算鏈路報(bào)文丟失率，再將此方法擴(kuò)展至一般網(wǎng)絡(luò)。

圖1 簡(jiǎn)單的數(shù)據(jù)匯聚樹Fig 1 A simple data aggregation tree

圖1 三條鏈路對(duì)應(yīng)的報(bào)文丟失率分別為θ1=(p1，q1)，θ2=(p2，q2)，θ3=(p3，q3)。算法用測(cè)量值Xk去推測(cè)Θ={(p1，q1)，(p2，q2)，(p3，q3)}。用表示在第m－1 輪節(jié)點(diǎn)j 成功接收到節(jié)點(diǎn)i 報(bào)文的情況下，第m 輪節(jié)點(diǎn)j 接收節(jié)點(diǎn)i 報(bào)文的情況;用表示在第m－1 輪節(jié)點(diǎn)j 沒有接收到節(jié)點(diǎn)i 報(bào)文的情況下，第m 輪節(jié)點(diǎn)j 接收節(jié)點(diǎn)i 報(bào)文的情況。令P=［p1，p2，p3］，Q=［q1，q2，q3］，先以計(jì)算P=［p1，p2，p3］為例，根據(jù)圖1 所示拓?fù)渲墟溌分g的關(guān)系可以推導(dǎo)出下面公式(2)

其中

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

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

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

同理，可以完成對(duì){q1，q2，q3}的計(jì)算。

2.2 算法描述

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

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 仿真實(shí)驗(yàn)

用NS2［7］模擬傳感器網(wǎng)絡(luò)數(shù)據(jù)匯聚過程，鏈路報(bào)文丟失率(p，q)預(yù)先設(shè)定。仿真中采用兩種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，9 節(jié)點(diǎn)網(wǎng)絡(luò)現(xiàn)150 節(jié)點(diǎn)網(wǎng)絡(luò)，分別驗(yàn)證算法準(zhǔn)確性和可擴(kuò)展性。每種拓?fù)浣Y(jié)構(gòu)下分別模擬兩種場(chǎng)景下的報(bào)文丟失情況:無丟失嚴(yán)重鏈路和有丟失嚴(yán)重鏈路。正常鏈路丟失率設(shè)置為(10%，85%)，丟失嚴(yán)重鏈路為(15%，80%)。

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

圖2 無丟失嚴(yán)重鏈路:預(yù)先設(shè)置參數(shù)p 與推測(cè)值p 的比較Fig 2 No heavy loss link scenarios:ture loss rate p vs inferred loss rate p

圖3 無丟失嚴(yán)重鏈路:預(yù)先設(shè)置參數(shù)q 與推測(cè)值q 的比較Fig 3 No heavy loss link scenarios:ture loss rate q vs inferred loss rate q

圖4 有丟失嚴(yán)重鏈路:預(yù)先設(shè)置參數(shù)p 與推測(cè)值p 的比較Fig 4 Heavy loss link scenarios:ture loss rate p vs inferred loss rate p

圖5 有丟失嚴(yán)重鏈路:預(yù)先設(shè)置參數(shù)q 與推測(cè)值q 的比較Fig 5 Heavy loss link scenarios:ture loss rate q vs inferred loss rate q

表1 是150 節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)涞姆抡娼Y(jié)果，從表中可以看出:隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，推測(cè)誤差并沒有呈幾何級(jí)數(shù)增加，推測(cè)值依然很接近預(yù)設(shè)值。在仿真過程中，誤差的最大值仍然小于1%。說明算法的可伸縮性較好，推測(cè)值的誤差值不會(huì)隨著網(wǎng)絡(luò)規(guī)模的增加而變大。

4 結(jié) 論

本文提出一種傳感器網(wǎng)絡(luò)鏈路時(shí)間相關(guān)丟失率推測(cè)算法，將傳感器網(wǎng)絡(luò)邏輯鏈路報(bào)文丟失推測(cè)問題形式化為Bayesian 推測(cè)問題，并采用Gibbs 抽樣方法來解決。采用NS2 仿真工具進(jìn)行算法的有效性和可伸縮性驗(yàn)證，結(jié)果表明:算法可較準(zhǔn)確地推測(cè)出鏈路報(bào)文丟失率，且伸縮性較好。

表1 150 節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)涞姆抡娼Y(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，F(xiàn)lorida，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，F(xiàn)L，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/.