肖宜龍， 蔣海波

(1. 中煤平朔集團(tuán)有限公司，山西 朔州 036006； 2. 中國(guó)科學(xué)院 成都生物研究所，四川 成都 610041; 3. 中國(guó)科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所，四川 成都 610041)

無(wú)人值守傳感器網(wǎng)絡(luò)[1-2]通常部署在惡劣環(huán)境中，數(shù)據(jù)收集節(jié)點(diǎn)Sink不固定在網(wǎng)絡(luò)中，而是每隔一段時(shí)間后在網(wǎng)絡(luò)中出現(xiàn)，收集各數(shù)據(jù)節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)包．在Sink節(jié)點(diǎn)出現(xiàn)之前，為避免數(shù)據(jù)包因節(jié)點(diǎn)損壞或是能量耗盡而丟失，各數(shù)據(jù)包通常分布式地存儲(chǔ)在整個(gè)網(wǎng)絡(luò)中．

筆者針對(duì)無(wú)人值守傳感器網(wǎng)絡(luò)的分布式存儲(chǔ)算法[3-5]進(jìn)行研究．基本假設(shè)[6]為網(wǎng)絡(luò)由均勻分布的n個(gè)傳感器節(jié)點(diǎn)構(gòu)成，其中k個(gè)為數(shù)據(jù)節(jié)點(diǎn) (n>k)，每個(gè)數(shù)據(jù)節(jié)點(diǎn)用來(lái)感知物理量并產(chǎn)生一個(gè)大小固定的數(shù)據(jù)包，稱為源數(shù)據(jù)包，其余的所有非數(shù)據(jù)節(jié)點(diǎn)只用來(lái)存儲(chǔ)數(shù)據(jù)．每個(gè)節(jié)點(diǎn)有相同的通信半徑，距離小于通信半徑的兩個(gè)節(jié)點(diǎn)互稱為鄰居節(jié)點(diǎn)，可以直接通信；處于通信半徑之外的節(jié)點(diǎn)通過(guò)多跳機(jī)制間接通信．網(wǎng)絡(luò)是連通的，但網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)都沒(méi)有路由表記錄如何與其通信半徑之外的節(jié)點(diǎn)間接通信，因此，兩個(gè)節(jié)點(diǎn)之間的間接通信是通過(guò)隨機(jī)選擇中間節(jié)點(diǎn)來(lái)完成的．

針對(duì)無(wú)人值守傳感器網(wǎng)絡(luò)設(shè)計(jì)的最新且最具代表性的分布式存儲(chǔ)算法是文獻(xiàn)[6]中提出的基于LT碼的算法．存儲(chǔ)過(guò)程中該算法采用簡(jiǎn)單隨機(jī)游走規(guī)則將k個(gè)源數(shù)據(jù)包傳遞到網(wǎng)絡(luò)中的n個(gè)節(jié)點(diǎn)；每個(gè)節(jié)點(diǎn)按照LT碼的度分度函數(shù)接收一定數(shù)量的源數(shù)據(jù)包，并計(jì)算得到一個(gè)存儲(chǔ)數(shù)據(jù)包存儲(chǔ)起來(lái)．Sink節(jié)點(diǎn)出現(xiàn)后，通過(guò)訪問(wèn)這些存儲(chǔ)數(shù)據(jù)包恢復(fù)出原來(lái)的源數(shù)據(jù)包．該方法主要有兩方面的缺點(diǎn)：一是簡(jiǎn)單隨機(jī)游走的低效率以及算法本身的需求，導(dǎo)致每個(gè)源數(shù)據(jù)包為了遍歷網(wǎng)絡(luò)中所有的節(jié)點(diǎn)，在實(shí)際過(guò)程中至少需要傳遞 3nlnn次．因此，這增加了網(wǎng)絡(luò)的通信成本．二是Sink節(jié)點(diǎn)為了恢復(fù)出所有的k個(gè)源數(shù)據(jù)包，需要訪問(wèn)k+kλ個(gè)存儲(chǔ)數(shù)據(jù)包 (λ> 0，與k的取值有關(guān))．文獻(xiàn)[6]的實(shí)驗(yàn)表明k的數(shù)量級(jí)大于等于102時(shí)，kλ的值大于100．因此，這導(dǎo)致了Sink節(jié)點(diǎn)的訪問(wèn)成本較高．針對(duì)LT碼算法的上述不足，尤其是考慮到如何降低網(wǎng)絡(luò)的通信成本(有利于傳感器網(wǎng)絡(luò)節(jié)能)，筆者提出了一種基于源數(shù)據(jù)包傳遞過(guò)程中并行定向隨機(jī)游走規(guī)則和網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)對(duì)源數(shù)據(jù)包獨(dú)立處理機(jī)制的分布式數(shù)據(jù)存儲(chǔ)算法．

1 并行定向隨機(jī)游走

為了用數(shù)值實(shí)驗(yàn)?zāi)M和驗(yàn)證文中算法的有效性，將無(wú)人值守傳感器網(wǎng)絡(luò)抽象為一個(gè)連通的二維隨機(jī)圖[7]．各傳感器節(jié)點(diǎn)用圖中的各頂點(diǎn)表示．若兩個(gè)傳感器節(jié)點(diǎn)互為鄰居節(jié)點(diǎn)，則用一條邊連接圖中對(duì)應(yīng)的頂點(diǎn)；一個(gè)傳感器節(jié)點(diǎn)的數(shù)據(jù)包傳遞到另一個(gè)節(jié)點(diǎn)的過(guò)程用隨機(jī)幾何圖上一次隨機(jī)游走表示．

二維隨機(jī)圖上的隨機(jī)游走定義為按某一隨機(jī)序列訪問(wèn)圖中頂點(diǎn)的過(guò)程．一次隨機(jī)游走開始于圖中某一頂點(diǎn)，并且下一步要訪問(wèn)頂點(diǎn)是從當(dāng)前訪問(wèn)頂點(diǎn)的鄰居頂點(diǎn)中選取的;如果下一步要訪問(wèn)的頂點(diǎn)是從當(dāng)前訪問(wèn)頂點(diǎn)的所有鄰居頂點(diǎn)中等概率隨機(jī)選取的，那么這樣的隨機(jī)游走稱為簡(jiǎn)單隨機(jī)游走．

與文獻(xiàn)[6]中采用的簡(jiǎn)單隨機(jī)游走規(guī)則不同，文中算法采用效率更高的并行定向隨機(jī)游走規(guī)則[8]在網(wǎng)絡(luò)中傳遞每個(gè)源數(shù)據(jù)包．下面先介紹(串行的)定向隨機(jī)游走規(guī)則，再介紹其并行化方式．

1.1 定向隨機(jī)游走規(guī)則

按照定向隨機(jī)游走規(guī)則，每當(dāng)源數(shù)據(jù)包到達(dá)了當(dāng)前訪問(wèn)的傳感器節(jié)點(diǎn)v后，要從v的所有鄰居節(jié)點(diǎn)中選出一個(gè)作為下一步要訪問(wèn)的節(jié)點(diǎn)u．

如果用N(o)表示任意一個(gè)節(jié)點(diǎn)o的鄰居節(jié)點(diǎn)集合，δ(o)表示節(jié)點(diǎn)o的鄰居節(jié)點(diǎn)個(gè)數(shù)，c(o)表示定向隨機(jī)游走目前已訪問(wèn)節(jié)點(diǎn)o的次數(shù)，那么，下一步將要訪問(wèn)的節(jié)點(diǎn)u的選取過(guò)程分為如下兩步:

步驟1 從當(dāng)前訪問(wèn)節(jié)點(diǎn)v的鄰居集合N(v)中隨機(jī)均勻地選擇2個(gè)節(jié)點(diǎn)作為備選節(jié)點(diǎn)．

步驟2 從2個(gè)備選節(jié)點(diǎn)(用集合N′表示)中選擇滿足下式的節(jié)點(diǎn)u作為下一步將要訪問(wèn)的節(jié)點(diǎn)．

1.2 并行定向隨機(jī)游走規(guī)則

每個(gè)數(shù)據(jù)節(jié)點(diǎn)將其源數(shù)據(jù)包并行地向外發(fā)出m個(gè)副本(0

對(duì)于一個(gè)連通的二維隨機(jī)圖，用t表示隨機(jī)游走的步數(shù)，那么該隨機(jī)游走對(duì)圖的覆蓋率(也就是訪問(wèn)到的不同頂點(diǎn)數(shù)占圖中總的頂點(diǎn)數(shù)的比例)，其理論值可以近似地表示[9]為 1-exp(-t/n)．因此，對(duì)于無(wú)人值守傳感器網(wǎng)絡(luò)，當(dāng)采用隨機(jī)游走機(jī)制(串行或并行[10])傳遞每個(gè)源數(shù)據(jù)包時(shí)，理論上傳遞次數(shù)達(dá)到O(nlnn) 時(shí)，才能使得每個(gè)源數(shù)據(jù)包訪問(wèn)到網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)．

2 高性能分布式數(shù)據(jù)存儲(chǔ)算法

文獻(xiàn)[6]提出的基于LT碼的方法，為使每個(gè)源數(shù)據(jù)包遍歷網(wǎng)絡(luò)中所有n個(gè)節(jié)點(diǎn)，每個(gè)源數(shù)據(jù)包的傳遞次數(shù)(文中將其看做網(wǎng)絡(luò)通信成本開銷)必須達(dá)到O(nlnn)．為降低這一開銷，筆者提出了一種基于并行隨機(jī)游走機(jī)制的高性能分布式存儲(chǔ)算法，該算法只要求每個(gè)源數(shù)據(jù)包的傳遞次數(shù)達(dá)到O(n)即可．

2.1 算法流程

文中算法的具體實(shí)現(xiàn)流程用代偽碼表示如下(命名為算法1):

算法1 無(wú)人值守傳感器網(wǎng)絡(luò)的高性能分布式存儲(chǔ)算法

輸入:k個(gè)源數(shù)據(jù)包Xv，v=1，…，k．

輸出:n個(gè)存儲(chǔ)數(shù)據(jù)包Yu，u=1，…，n．

/*初始化階段*/

1: For 每個(gè)數(shù)據(jù)節(jié)點(diǎn)v=1 tok

2: 為源數(shù)據(jù)包Xv添加頭信息: IDv號(hào)及定向隨機(jī)游走步數(shù)計(jì)數(shù)器N=0;

3: For 每個(gè)節(jié)點(diǎn)u=1 ton

4: 初始化每個(gè)存儲(chǔ)數(shù)據(jù)包的值:Yu=0;

5: 初始化每個(gè)源數(shù)據(jù)包Xv已訪問(wèn)節(jié)點(diǎn)u的當(dāng)前次數(shù):cv(u)=1，v=1，…，k;/*分布式存儲(chǔ)階段*/

6: For 每個(gè)數(shù)據(jù)節(jié)點(diǎn)v=1 tok

7: 按照概率alnk/k接收Xv，并且更新自己的存儲(chǔ)數(shù)據(jù)包:Yv=Yv?Xv;

8: 按照定向隨機(jī)游走規(guī)則將源數(shù)據(jù)包Xv的m個(gè)副本分別傳遞出去;

9:cv(v)=cv(v)+1;

10: For 每個(gè)節(jié)點(diǎn)u=1 ton

11: For 每個(gè)到達(dá)節(jié)點(diǎn)u的源數(shù)據(jù)包Xj

12: IfXj是第一次訪問(wèn)節(jié)點(diǎn)u

13: 節(jié)點(diǎn)u按照概率alnk/k接收Xj，并且更新自己的存儲(chǔ)數(shù)據(jù)包:Yu=Yu?Xj;

14:cj(u)=cj(u)+1;

15: 源數(shù)據(jù)包Xj更新頭信息:N=N+1;

16: IfN

17: 節(jié)點(diǎn)u按照定向隨機(jī)游走規(guī)則將源數(shù)據(jù)包Xj傳遞到它的一個(gè)鄰居節(jié)點(diǎn);

18: Else

19: 節(jié)點(diǎn)u丟棄Xj;

算法結(jié)束．

算法1完成之后，每個(gè)節(jié)點(diǎn)存儲(chǔ)了一個(gè)存儲(chǔ)數(shù)據(jù)包，源數(shù)據(jù)包不再存儲(chǔ)．算法有兩個(gè)重要參數(shù): 一個(gè)是定向隨機(jī)游走步數(shù)，即每個(gè)源數(shù)據(jù)包副本的傳遞次數(shù)，設(shè)置為cn/m，用變量N來(lái)計(jì)數(shù)；副本每傳遞一次N的值加1，當(dāng)N>cn/m時(shí)，副本被丟棄，不再傳遞．另一個(gè)參數(shù)是每個(gè)節(jié)點(diǎn)接收一個(gè)新到達(dá)的源數(shù)據(jù)包副本的概率，算法中設(shè)置為alnk/k．算法性能主要由這兩個(gè)參數(shù)決定．下面做具體分析．

2.2 算法性能分析

當(dāng)算法1執(zhí)行完成之后，k個(gè)源數(shù)據(jù)包被分布式地存儲(chǔ)到網(wǎng)絡(luò)的n個(gè)節(jié)點(diǎn)中，每個(gè)節(jié)點(diǎn)存儲(chǔ)的存儲(chǔ)數(shù)據(jù)包都是若干個(gè)源數(shù)據(jù)包的異或和(每個(gè)源數(shù)據(jù)包和存儲(chǔ)數(shù)據(jù)包都看做是二元域上的比特向量)．下文將分析Sink節(jié)點(diǎn)收集到多少個(gè)存儲(chǔ)數(shù)據(jù)包之后可以恢復(fù)原來(lái)的k個(gè)源數(shù)據(jù)包．

假定Sink節(jié)點(diǎn)出現(xiàn)后，隨機(jī)地從k+ε個(gè)未損壞節(jié)點(diǎn)中收集了k+ε個(gè)存儲(chǔ)數(shù)據(jù)包．為便于描述，這k+ε個(gè)存儲(chǔ)數(shù)據(jù)包表示為Yi，i=1， 2， …，k+ε．每個(gè)存儲(chǔ)數(shù)據(jù)包都是源數(shù)據(jù)包的線性組合，因此，任意一個(gè)Yi，i=1， 2， …，k+ε，都可以表示為下式(式中的乘法為二元域上的元素與二元域上的向量之間的數(shù)乘):

Yi=gi·[X1，X2，…，Xk]T,

(1)

其中，X1， …，Xk表示k個(gè)未知的源數(shù)據(jù)包，gi是一個(gè)獨(dú)立的且取值在二元域上的隨機(jī)行向量，稱為存儲(chǔ)數(shù)據(jù)包Yi的生成行向量．當(dāng)gi的某個(gè)元素gij取值為1時(shí)表示對(duì)應(yīng)的源數(shù)據(jù)包Xi被接收．假定步數(shù)為t=cn的并行定向隨機(jī)游走覆蓋的各節(jié)點(diǎn)均勻地分布在網(wǎng)絡(luò)中，那么，由算法1可知：gi中每個(gè)元素gij，j=1，…，k，都是獨(dú)立取值的，且都服從式(2)定義的分布．

(2)

這k+ε個(gè)存儲(chǔ)數(shù)據(jù)包的生成行向量構(gòu)成了一個(gè)(k+ε)×k階矩陣G(k+ε)×k，稱為這k+ε個(gè)存儲(chǔ)數(shù)據(jù)包的生成矩陣，即G(k+ε)×k= [g1，g2， …，gk+ε]T．借助生成矩陣，這k+ε個(gè)存儲(chǔ)數(shù)據(jù)包可以表示為

[Y1，Y2，…，Yk+ε]T=G(k+ε)×k·[X1，…，Xk]T．

(3)

若生成矩陣G(k+ε)×k存在一個(gè)可逆k×k階子矩陣，也就是G列滿秩，則式(3)定義的方程組存在惟一一組解，解方程組后可求得k個(gè)未知的源數(shù)據(jù)包X1， …，Xk．因此，Sink節(jié)點(diǎn)可由任意k+ε個(gè)存儲(chǔ)數(shù)據(jù)包計(jì)算得到k個(gè)未知源數(shù)據(jù)包的概率等于這k+ε個(gè)存儲(chǔ)數(shù)據(jù)包的生成矩陣G(k+ε)×k列滿秩的概率．如果用Pfailure表示二元域上的生成矩陣G(k+ε)×k列不滿秩的概率，當(dāng)式(2)成立時(shí)，得到如下結(jié)論:

引理1 當(dāng)G(k+ε)×k的每個(gè)元素的取值服從式(2)定義的分布時(shí)，Pfailure的上界為

(4)

證明 若G(k+ε)×k的各列線性相關(guān)，則G(k+ε)×k列不滿秩，因此

(5)

令R表示G(k+ε)×k的任意一個(gè)行向量，用w表示向量x中1的個(gè)數(shù)，因?yàn)樾邢蛄縍的每一個(gè)元素取值獨(dú)立，且取值為1的概率由式(2)定義，因此

(6)

因?yàn)榫仃嘒(k+ε)×k的每一個(gè)行向量獨(dú)立，因此，G(k+ε)×kxT=0的概率為

(7)

當(dāng)向量x取所有不同的值時(shí)，根據(jù)式(5)可得到引理1中的結(jié)論．

綜合上述分析，可用如下定理1描述算法1的性能．

定理1 采用算法1，Sink節(jié)點(diǎn)可由隨機(jī)選取的k+ε個(gè)存儲(chǔ)數(shù)據(jù)包計(jì)算得到原來(lái)的k個(gè)源數(shù)據(jù)包的概率Psuccess滿足:

(8)

另外，通過(guò)數(shù)值實(shí)驗(yàn)發(fā)現(xiàn)(鑒于篇幅關(guān)系，這里不再列出相關(guān)實(shí)驗(yàn)結(jié)果)，當(dāng)式(8)中的參數(shù)(1-exp(-c))a≥2 時(shí)，Psuccess的下界主要由ε的值決定，可以用簡(jiǎn)化表達(dá)式 1-(1/2)ε近似表示Psuccess的下界．

3 數(shù)值實(shí)驗(yàn)

算法的數(shù)值實(shí)驗(yàn)在MATLAB環(huán)境下進(jìn)行．用隨機(jī)生成的二維隨機(jī)圖模擬網(wǎng)絡(luò)，在L×L= 100×100的正方形區(qū)域隨機(jī)均勻地分布n個(gè)點(diǎn)模擬傳感器網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)，其中數(shù)據(jù)節(jié)點(diǎn)的比例設(shè)置為40%，即k=0.4n，每個(gè)節(jié)點(diǎn)的通信半徑R滿足R2= (2 lnn/(πn))L2(按照隨機(jī)幾何圖的理論，這一條件保證了網(wǎng)絡(luò)極大的連通概率)．實(shí)驗(yàn)分為兩組，第1組測(cè)試網(wǎng)絡(luò)的通信成本，即存儲(chǔ)過(guò)程中每個(gè)源數(shù)據(jù)包在達(dá)到一定的網(wǎng)絡(luò)覆蓋率前提下需要在網(wǎng)絡(luò)中的傳遞次數(shù)．通信成本越低，越有利于節(jié)約網(wǎng)絡(luò)中各節(jié)點(diǎn)的通信能耗．第2組測(cè)試讀取源數(shù)據(jù)包時(shí)的訪問(wèn)成本，即存儲(chǔ)完成之后，Sink節(jié)點(diǎn)需要訪問(wèn)多少個(gè)存儲(chǔ)數(shù)據(jù)包才能恢復(fù)出原來(lái)的k個(gè)源數(shù)據(jù)包．訪問(wèn)成本越低，允許損壞的傳感器節(jié)點(diǎn)就越多，網(wǎng)絡(luò)的可靠性就越高．

3.1 存儲(chǔ)源數(shù)據(jù)包的通信成本實(shí)驗(yàn)

每個(gè)源數(shù)據(jù)包都按照并行隨機(jī)游走機(jī)制在網(wǎng)絡(luò)中傳遞，每個(gè)源數(shù)據(jù)包并行傳遞的副本數(shù)設(shè)為m=2，當(dāng)m個(gè)副本總的傳遞次數(shù)，即隨機(jī)游走的總步數(shù)為t時(shí)，網(wǎng)絡(luò)覆蓋率的理論值[9]近似為 1-exp(-t/n)．實(shí)驗(yàn)中將并行定向隨機(jī)游走的總步數(shù)設(shè)為t=cn時(shí)，單個(gè)副本的傳遞次數(shù)設(shè)置為cn/m．實(shí)驗(yàn)測(cè)試了k個(gè)源數(shù)據(jù)包對(duì)網(wǎng)絡(luò)各節(jié)點(diǎn)的平均覆蓋率與系數(shù)c之間的關(guān)系．作為對(duì)比，也測(cè)試了采用簡(jiǎn)單隨機(jī)游走機(jī)制時(shí)的相關(guān)性能．圖1、圖2所示為n，k，c取不同值時(shí)的實(shí)驗(yàn)結(jié)果．

圖1 源數(shù)據(jù)包通信成本測(cè)試1(隨機(jī)游走步數(shù)t=cn, n=500, k=200)圖2 源數(shù)據(jù)包通信成本測(cè)試2(隨機(jī)游走步數(shù)t=cn, n=1000, k=400)

從圖1和圖2中可以看出，采用并行定向隨機(jī)游走機(jī)制，k個(gè)源數(shù)據(jù)包對(duì)網(wǎng)絡(luò)覆蓋率平均值的實(shí)驗(yàn)值與理論值 1-exp(-t/n) 是近似相等的．當(dāng)t=n時(shí)，實(shí)驗(yàn)值接近60%，當(dāng)t=3n時(shí)，基本上每個(gè)源數(shù)據(jù)包都能覆蓋網(wǎng)絡(luò)中超過(guò)95%的節(jié)點(diǎn)．而采用簡(jiǎn)單隨機(jī)游走規(guī)則，實(shí)驗(yàn)值明顯小于理論值，比并行隨機(jī)游走機(jī)制的網(wǎng)絡(luò)覆蓋率平均低約20%．因此，采用定向隨機(jī)游走機(jī)制能有效降低網(wǎng)絡(luò)的通信成本．同時(shí)，采用并行定向隨機(jī)游走機(jī)制時(shí)，網(wǎng)絡(luò)中每一時(shí)刻平均有mk個(gè)源數(shù)據(jù)包被同時(shí)處理，提高了網(wǎng)絡(luò)的吞吐率，節(jié)省了整個(gè)存儲(chǔ)過(guò)程的耗時(shí)；而采用簡(jiǎn)單隨機(jī)游走機(jī)制時(shí)，網(wǎng)絡(luò)中每一時(shí)刻只有k個(gè)源數(shù)據(jù)包處理．

需要說(shuō)明的是，當(dāng)每個(gè)源數(shù)據(jù)包并行傳遞的副本數(shù)m小于lnn值時(shí)，實(shí)驗(yàn)結(jié)果與圖1和圖2所示類似；而當(dāng)m大于 lnn值時(shí)，網(wǎng)絡(luò)覆蓋率隨m的增大而減?。?/p>

3.2 讀取源數(shù)據(jù)包的訪問(wèn)成本實(shí)驗(yàn)

測(cè)試存儲(chǔ)過(guò)程完成之后，Sink節(jié)點(diǎn)為得到k個(gè)源數(shù)據(jù)包而訪問(wèn)的存儲(chǔ)數(shù)據(jù)包的個(gè)數(shù)．實(shí)驗(yàn)結(jié)果用如下兩個(gè)變量之間的關(guān)系描述：源數(shù)據(jù)包恢復(fù)開銷η，即Sink節(jié)點(diǎn)訪問(wèn)到的存儲(chǔ)數(shù)據(jù)包個(gè)數(shù)h與源數(shù)據(jù)包個(gè)數(shù)k之差；源數(shù)據(jù)包恢復(fù)成功率S，即Sink節(jié)點(diǎn)能從h個(gè)存儲(chǔ)數(shù)據(jù)包計(jì)算出k個(gè)源數(shù)據(jù)包的概率．

實(shí)驗(yàn)中主要調(diào)節(jié)參數(shù)為每個(gè)源數(shù)據(jù)包的并行定向隨機(jī)游走的總步數(shù)cn的系數(shù)c以及每個(gè)傳感器節(jié)點(diǎn)接收一個(gè)新到達(dá)的源數(shù)據(jù)包的概率alnk/k的系數(shù)a．圖3至圖6所示為不同網(wǎng)絡(luò)規(guī)模下，c和a的取值不同時(shí)，S與η之間的關(guān)系(圖中S的每個(gè)值都是 1 000 次實(shí)驗(yàn)的平均值)．

從圖3至圖6可以看出， 當(dāng)參數(shù)a≥2時(shí)， 只要c的取值增大， 就能以較少的源數(shù)據(jù)包恢復(fù)開銷成功計(jì)算出原來(lái)的源數(shù)據(jù)包．進(jìn)一步地，從圖4、圖6可以看出，當(dāng)參數(shù)a=3 時(shí)，只要c≥3，Sink節(jié)點(diǎn)就能從任意收集到的k+11 個(gè)以上的存儲(chǔ)數(shù)據(jù)包以100%的概率恢復(fù)出k個(gè)源數(shù)據(jù)包．此時(shí)，式(8)中的 (1-exp(-c))a≥ (1-exp(-3)) 3≈ 2.85．按定理1的結(jié)論，當(dāng)η≥11 時(shí)，理論上Sink節(jié)點(diǎn)可由任意k+η個(gè)存儲(chǔ)數(shù)據(jù)包計(jì)算得到原來(lái)的k個(gè)源數(shù)據(jù)包的概率S近似大于 1-2-11≈ 99.95%，實(shí)驗(yàn)值基本上驗(yàn)證了理論值．

圖3 源數(shù)據(jù)包訪問(wèn)成本測(cè)試1(n=500, k=200, 參數(shù)a=2)圖4 源數(shù)據(jù)包訪問(wèn)成本測(cè)試2(n=500, k=200, 參數(shù)a=3)

圖5 源數(shù)據(jù)包訪問(wèn)成本測(cè)試3(n=1000, k=400, 參數(shù)a=2)圖6 源數(shù)據(jù)包訪問(wèn)成本測(cè)試4(n=1000, k=400, 參數(shù)a=3)

鑒于篇幅有限，參數(shù)a和c取其他值時(shí)的實(shí)驗(yàn)結(jié)果不在文中列出．不過(guò)筆者發(fā)現(xiàn)，當(dāng) (1-exp(-c))a小于2時(shí)，實(shí)驗(yàn)結(jié)果不穩(wěn)定；當(dāng) (1-exp(-c))a取值不是很大時(shí)，實(shí)驗(yàn)結(jié)果與 (1-exp(-c)) 3 時(shí)的類似；而當(dāng) (1-exp(-c))a取值較大時(shí)，反而會(huì)使得成功恢復(fù)源數(shù)據(jù)包的概率降低．因此，建議在實(shí)際應(yīng)用中，取a=3，c=3 即可，這樣既能獲得好的穩(wěn)定性，也能使網(wǎng)絡(luò)各節(jié)點(diǎn)的計(jì)算成本較低(因?yàn)閍的值越大，每個(gè)節(jié)點(diǎn)接收源數(shù)據(jù)包的概率就越大，因而計(jì)算成本就會(huì)提高)．

3.3 性能比較

文獻(xiàn)[6]提出的基于LT碼的算法中，單個(gè)源數(shù)據(jù)包在網(wǎng)絡(luò)中總的傳遞次數(shù)為O(nlnn)，并指出這一值達(dá)到 3nlnn時(shí)實(shí)驗(yàn)效果較好．而文中方法所需傳遞次數(shù)為O(n)，實(shí)驗(yàn)中將這一值設(shè)置為3n時(shí)就能得到很好的源數(shù)據(jù)包恢復(fù)性能．另外，采用基于LT碼的算法，Sink節(jié)點(diǎn)為了恢復(fù)出k個(gè)源數(shù)據(jù)包而需要訪問(wèn)的存儲(chǔ)數(shù)據(jù)包的個(gè)數(shù)與LT碼的譯碼性能有關(guān)．文獻(xiàn)[6]的實(shí)驗(yàn)表明，當(dāng)k大于100時(shí)，只有當(dāng)源數(shù)據(jù)包恢復(fù)開銷η的值較大(大于100)時(shí)，Sink節(jié)點(diǎn)才能成功恢復(fù)出源數(shù)據(jù)包．而采用文中方法，不論k的取值如何，成功恢復(fù)k個(gè)源數(shù)據(jù)包，Sink節(jié)點(diǎn)只需訪問(wèn)k+11 個(gè)存儲(chǔ)數(shù)包．對(duì)于某些實(shí)驗(yàn)參數(shù)，文中算法(源數(shù)據(jù)包傳遞次數(shù)設(shè)置為3n，參數(shù)a的值設(shè)置為3)與基于LT碼算法(源數(shù)據(jù)包傳遞次數(shù)設(shè)置為 3nlnn，譯碼時(shí)采用極大似然譯碼算法)的具體對(duì)比結(jié)果列于表1中．

綜上可得出結(jié)論: 采用文中算法可以有效節(jié)約存儲(chǔ)過(guò)程中的通信成本和Sink節(jié)點(diǎn)的訪問(wèn)成本．

表1 性能比較

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

筆者研究了無(wú)人值守傳感器網(wǎng)絡(luò)的高可靠性數(shù)據(jù)存儲(chǔ)問(wèn)題，依靠源數(shù)據(jù)包傳遞過(guò)程中的并行定向隨機(jī)游走機(jī)制和網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)對(duì)源數(shù)據(jù)包的獨(dú)立處理機(jī)制，提出了一種執(zhí)行簡(jiǎn)單，性能高效的分布式數(shù)據(jù)存儲(chǔ)算法．與同類方法相比，文中方法能有效降低存儲(chǔ)過(guò)程中各節(jié)點(diǎn)的通信成本和Sink節(jié)點(diǎn)的訪問(wèn)成本．

[1] Reddy S K V L, Ruj S, Nayak A. Distributed Data Survivability Schemes in Mobile Unattended Wireless Sensor Networks [C]//Proceedings of IEEE GLOBECOM. Piscataway: IEEE, 2012: 979-984.

[2] 郭江鴻, 馬建峰, 張留美, 等. 高效的無(wú)線傳感器網(wǎng)絡(luò)加密數(shù)據(jù)匯聚方案 [J]. 西安電子科技大學(xué)學(xué)報(bào), 2013, 40(3): 95-101.

Guo Jianghong, Ma Jianfeng, Zhang Liumei, et al. Efficient Encrypted Data Aggregation Scheme for Wireless Sensor Networks [J]. Journal of Xidian University, 2013, 40(3): 95-101.

[3] Mitra S, De Sarkar A, Ray S. A Review of Fault Management System in Wireless Sensor Network [C]//Proceedings of the CUBE International Conference on Information Technology. New York: ACM, 2012: 144-148.

[4] Vitali D, Spognardi A, Mancini L V. Replication Schemes in Unattended Wireless Sensor Networks [C]//Proceedings of 4th IFIP International Conference on New Technologies, Mobility and Security. Piscataway: IEEE, 2011: 1-5.

[5] 任偉, 任毅, 張慧, 等. 無(wú)人值守?zé)o線傳感器網(wǎng)絡(luò)中一種安全高效的數(shù)據(jù)存活策略 [J]. 計(jì)算機(jī)研究與發(fā)展, 2009, 46(12): 2093-2100.

Ren Wei, Ren Yi, Zhang Hui, et al. A Secure and Efficient Data Survival Strategy in Unattended Wireless Sensor Network [J]. Journal of Computer Research and Development, 2009, 46(12): 2093-2100.

[6] Kong Z, Aly S A, Soljanin E. Decentralized Coding Algorithms for Distributed Storage in Wireless Sensor Networks [J]. IEEE Journal on Selected Areas in Communications, 2010, 28(2): 261-267.

[7] Cooper C, Frieze A. The Cover Time of Random Geometric Graphs [J]. Random Structures and Algorithms, 2011, 38(3): 324-349.

[8] Avin C, Krishnamachari B. The Power of Choice in Random Walks: An Empirical Study [J]. Computer Networks, 2008, 52(1): 44-60.

[9] Tzevelekas L, Oikonomou K, Stavrakakis I. Random Walk with Jumps in Large-scale Random Geometric Graphs [J]. Computer Communications, 2010, 33(13): 1505-1514.

[10] Cooper C, Frieze A, Radzik T. Multiple Random Walks in Random Regular Graphs [J]. SIAM Journal on Discrete Mathematics, 2009, 23(4): 1738-1761.