基于網(wǎng)絡(luò)編碼的延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)低時(shí)延廣播傳輸機(jī)制

楊奎武 郭淵博 馬 駿 鄭康鋒

①(解放軍信息工程大學(xué)電子技術(shù)學(xué)院 鄭州 450004)

②(北京郵電大學(xué)網(wǎng)絡(luò)與交換國(guó)家重點(diǎn)實(shí)驗(yàn)室信息安全中心 北京 100876)

1 引言

近年來(lái)，延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)(DTMSN)[1]由于其廣泛的適用性和廣闊的應(yīng)用前景而備受關(guān)注。在DTMSN網(wǎng)絡(luò)中，由于傳感器節(jié)點(diǎn)的移動(dòng)或休眠等原因，使得網(wǎng)絡(luò)具有間歇連通的特點(diǎn)，即網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)之間大多不存在穩(wěn)定連通路徑。因此，節(jié)點(diǎn)間的數(shù)據(jù)傳輸主要依靠傳感器節(jié)點(diǎn)移動(dòng)過(guò)程中的機(jī)會(huì)性連接來(lái)實(shí)現(xiàn)。同樣，廣播作為一種重要的網(wǎng)絡(luò)數(shù)據(jù)傳輸方式，在DTMSN中，也必須通過(guò)節(jié)點(diǎn)間的機(jī)會(huì)連接來(lái)完成，這就使得傳統(tǒng)的基于簇[2]、協(xié)商[3]、多點(diǎn)中繼[4]的廣播機(jī)制無(wú)法適用于DTMSN網(wǎng)絡(luò)。

當(dāng)前，針對(duì)DTMSN的研究主要集中在路由領(lǐng)域，并取得了較多研究成果[5-7]，而關(guān)于 DTMSN廣播機(jī)制的研究則非常少，主要有直接傳輸(DT)、泛洪(flood)、k-鄰居(k-neighbor)等機(jī)制。

DT是DTMSN中最基本的數(shù)據(jù)傳輸策略，其基本思想是節(jié)點(diǎn)在運(yùn)動(dòng)過(guò)程中只與 BS進(jìn)行通信。DT可以用來(lái)實(shí)現(xiàn)廣播數(shù)據(jù)的傳輸，但其實(shí)際上是利用多次單播來(lái)實(shí)現(xiàn)廣播的目的。由于DT機(jī)制中節(jié)點(diǎn)只接收 BS的廣播數(shù)據(jù)，因此節(jié)點(diǎn)通信開(kāi)銷(xiāo)非常小，但廣播時(shí)延卻很高。

泛洪也是一種基本的數(shù)據(jù)傳輸策略，與DT相反，泛洪機(jī)制中傳感器節(jié)點(diǎn)會(huì)把自身存儲(chǔ)的廣播數(shù)據(jù)轉(zhuǎn)發(fā)給所有能夠與其通信的其他節(jié)點(diǎn)，從而達(dá)到有效降低廣播延遲的目的，但由此也導(dǎo)致廣播通信開(kāi)銷(xiāo)較大。為了降低通信開(kāi)銷(xiāo)，傳染路由(epidemic)[8]等機(jī)制相繼被提出，雖然這些機(jī)制能夠在一定程度上降低通信開(kāi)銷(xiāo)，但也增加了廣播延遲。

為了降低廣播過(guò)程中的通信開(kāi)銷(xiāo)，文獻(xiàn)[9]提出了k-鄰居(k-neighbors)機(jī)制，該機(jī)制的基本思想是在只有在節(jié)點(diǎn)最少存在k個(gè)鄰居的情況下才進(jìn)行廣播數(shù)據(jù)傳輸，從而避免了泛洪機(jī)制中向每個(gè)節(jié)點(diǎn)都進(jìn)行數(shù)據(jù)傳輸所帶來(lái)的通信開(kāi)銷(xiāo)，充分利用了無(wú)線(xiàn)信道的廣播特性。k越大，通信開(kāi)銷(xiāo)越小。但由于需要有k個(gè)以上鄰居節(jié)點(diǎn)才能進(jìn)行數(shù)據(jù)的廣播傳輸，因此廣播延遲較高。

網(wǎng)絡(luò)編碼[10]作為一種提高網(wǎng)絡(luò)吞吐量、降低網(wǎng)絡(luò)開(kāi)銷(xiāo)的重要手段近年來(lái)受到廣泛重視?；诰W(wǎng)絡(luò)編碼的廣播機(jī)制的研究也取得了較多的研究成果[11,12]，但目前這些成果基本上都是以靜態(tài)網(wǎng)絡(luò)為研究對(duì)象，而將網(wǎng)絡(luò)編碼應(yīng)用于動(dòng)態(tài)的DTMSN廣播數(shù)據(jù)傳輸?shù)南嚓P(guān)研究則沒(méi)有。

針對(duì)當(dāng)前DTMSN廣播數(shù)據(jù)傳輸延遲較大的問(wèn)題，本文提出一種基于隨機(jī)網(wǎng)絡(luò)編碼的低延遲廣播傳輸(NBT)機(jī)制。該機(jī)制中，原始數(shù)據(jù)被分為多個(gè)批次，BS以單播的方式向每一個(gè)移動(dòng)到其通信范圍內(nèi)的傳感器節(jié)點(diǎn)發(fā)送需要廣播的編碼數(shù)據(jù)，且保證不同傳感器節(jié)點(diǎn)接收到的同一批次的任意兩個(gè)編碼數(shù)據(jù)所采用的編碼向量互不相關(guān)；而傳感器節(jié)點(diǎn)之間則利用泛洪機(jī)制進(jìn)行編碼廣播數(shù)據(jù)的交互。當(dāng)傳感器節(jié)點(diǎn)接收到足夠多的同一批次的編碼數(shù)據(jù)后便可以通過(guò)解碼獲得原始數(shù)據(jù)。仿真結(jié)果表明，NBT與現(xiàn)有的泛洪(flood)機(jī)制、k-鄰居(k-neighbors)機(jī)制相比有著更好的廣播延遲性能。

2 網(wǎng)絡(luò)模型及知識(shí)基礎(chǔ)

2.1 網(wǎng)絡(luò)模型

如圖1所示，假設(shè)DTMSN初始部署時(shí)，M個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在一個(gè)l×l的正方形區(qū)域A內(nèi)(虛線(xiàn)代表節(jié)點(diǎn)通信半徑)，基站BS位于區(qū)域中心，靜止不動(dòng)。節(jié)點(diǎn)通信半徑為r，所有節(jié)點(diǎn)的移動(dòng)都遵循Random WayPoint (RWP)[13]運(yùn)動(dòng)模型。

圖1 DTMSN網(wǎng)絡(luò)模型

2.2 知識(shí)基礎(chǔ)

2.2.1隨機(jī)網(wǎng)絡(luò)編碼[14]假設(shè)集合P={p1,p2,…,pl}中含有l(wèi)個(gè)長(zhǎng)度相等的待發(fā)送原始數(shù)據(jù)包，在對(duì)原始數(shù)據(jù)包進(jìn)行廣播發(fā)送之前，源節(jié)點(diǎn)每次隨機(jī)選擇不同的編碼向量gi=(gi1,gi2,…,gil)(gij∈GF(2N),j≤l)對(duì)l個(gè)原始數(shù)據(jù)包進(jìn)行編碼，如式(1)所示。

當(dāng)目的節(jié)點(diǎn)接收到任意l個(gè)編碼包組成的集合C={C1,C2,…,Cl}后，若其對(duì)應(yīng)的編碼矩陣G={g1,g2,…,gl}各編碼向量線(xiàn)性無(wú)關(guān)(滿(mǎn)秩)，則可根據(jù)式(2)進(jìn)行譯碼并恢復(fù)出原始數(shù)據(jù)集合P。

圖2給出了在N,l取不同值的情況下，隨機(jī)編碼矩陣G滿(mǎn)秩的概率。從圖中可以看出，隨著N,l的增大，編碼矩陣G滿(mǎn)秩的概率也隨機(jī)增大，當(dāng)取N＞5 時(shí)，目的節(jié)點(diǎn)在接收到l個(gè)編碼包后基本上能夠以接近1的概率進(jìn)行譯碼。同樣，Ho等人[15]也相應(yīng)地證明，在N等于16的網(wǎng)絡(luò)中采用隨機(jī)網(wǎng)絡(luò)編碼時(shí)，目的節(jié)點(diǎn)可以最低以 99.6%的概率進(jìn)行譯碼，實(shí)際應(yīng)用中取N=8即可。

2.2.2節(jié)點(diǎn)數(shù)據(jù)相關(guān)度

定義 任意兩節(jié)點(diǎn)i,j的數(shù)據(jù)相關(guān)度是指i,j具有的相同數(shù)據(jù)包的數(shù)量與他們?nèi)繑?shù)據(jù)包(不包括重復(fù))數(shù)量的比，我們用ρij表示。

圖2 編碼矩陣滿(mǎn)秩概率

例如，節(jié)點(diǎn)i有8個(gè)數(shù)據(jù)包，j有10個(gè)數(shù)據(jù)包，其中相同的數(shù)據(jù)包數(shù)量為6，則節(jié)點(diǎn)i,j的數(shù)據(jù)相關(guān)度為ρij=6 /(8 + 1 0 - 6)=0 .5。ρij越大，表示節(jié)點(diǎn)具有相同數(shù)據(jù)包的比例越高，因此能夠相互交換的數(shù)據(jù)也就越少。

3 NBT廣播傳輸機(jī)制

3.1 NBT基本原理

非編碼廣播機(jī)制如圖3(a)所示，假設(shè)BS有a～h共8個(gè)數(shù)據(jù)需要廣播，節(jié)點(diǎn)A,B,C在各自運(yùn)動(dòng)過(guò)程中由于信道等原因僅從BS分別獲得了4,6,4個(gè)廣播數(shù)據(jù)，即節(jié)點(diǎn)A攜有數(shù)據(jù)a,b,c,d，節(jié)點(diǎn)B攜有數(shù)據(jù)a,b,c,e,f,g，節(jié)點(diǎn)C攜有數(shù)據(jù)e,f,g,h。由于網(wǎng)絡(luò)中節(jié)點(diǎn)是動(dòng)態(tài)的，在節(jié)點(diǎn)A沿圖中虛線(xiàn)繼續(xù)運(yùn)動(dòng)過(guò)程中，當(dāng)A與B發(fā)生連接時(shí)，節(jié)點(diǎn)A,B都無(wú)法從對(duì)方處獲得全部自身需要廣播數(shù)據(jù)包，即A,B發(fā)生連接后A,B節(jié)點(diǎn)都因缺少數(shù)據(jù)h而無(wú)法獲得全部廣播數(shù)據(jù)；只有在節(jié)點(diǎn)A與C發(fā)生連接后，A才能將廣播數(shù)據(jù)獲取完整。因此在A沿虛線(xiàn)運(yùn)動(dòng)這一時(shí)段內(nèi)，僅有A,C獲取了全部廣播數(shù)據(jù)。

采用編碼廣播機(jī)制時(shí)(如圖3(b)),BS利用隨機(jī)選取的不相關(guān)的編碼向量將8個(gè)廣播數(shù)據(jù)編碼后發(fā)送。同樣，我們假設(shè)A,B,C在各自運(yùn)動(dòng)過(guò)程中分別獲得了4,6,4個(gè)廣播數(shù)據(jù)，即節(jié)點(diǎn)A攜有編碼數(shù)據(jù)1,2,3,4，節(jié)點(diǎn)B攜有編碼數(shù)據(jù)5,6,7,8,9,10，節(jié)點(diǎn)C攜有編碼數(shù)據(jù)11,12,13,14。當(dāng)節(jié)點(diǎn)A沿虛線(xiàn)繼續(xù)運(yùn)動(dòng)過(guò)程中，當(dāng)A與B發(fā)生連接時(shí)，節(jié)點(diǎn)A,B都能夠從對(duì)方獲取到自身沒(méi)有的編碼數(shù)據(jù)并以非常高的成功率進(jìn)行譯碼(參見(jiàn)2.2.1節(jié))，從而獲得全部廣播數(shù)據(jù)。在A與C發(fā)生連接后，同樣C節(jié)點(diǎn)也能夠成功譯碼。因此在A沿虛線(xiàn)運(yùn)動(dòng)這一時(shí)間內(nèi)，A,B,C都能夠以較高的概率獲取全部廣播數(shù)據(jù)，相比非編碼機(jī)制降低了廣播的延遲。

3.2 原始數(shù)據(jù)編碼

BS在廣播原始數(shù)據(jù)前，首先需要根據(jù)原始數(shù)據(jù)的大小將其分為若干個(gè)批次，每個(gè)批次包含長(zhǎng)度相等的l個(gè)原始數(shù)據(jù)包。當(dāng)有傳感器節(jié)點(diǎn)移動(dòng)到BS通信范圍內(nèi)時(shí)，BS針對(duì)每一批次的原始數(shù)據(jù)包隨機(jī)選擇編碼向量對(duì)其進(jìn)行編碼，并將編碼后的編碼包以單播形式發(fā)送給傳感器節(jié)點(diǎn)。BS對(duì)同一批次的數(shù)據(jù)包每進(jìn)行一次編碼都需要將編碼包的序號(hào)加 1。需要指出的是，為了提高節(jié)點(diǎn)編碼包的不相關(guān)度，任意兩個(gè)不同序號(hào)的編碼包使用的編碼向量是不相關(guān)的，BS可以將選擇的編碼向量同歷史編碼向量相比較來(lái)實(shí)現(xiàn)這一目的。同樣，BS以單播形式對(duì)編碼數(shù)據(jù)進(jìn)行傳輸也是為了降低節(jié)點(diǎn)間編碼包的不相關(guān)度。廣播包的格式及所在層次如圖4所示，可以看出廣播包的包頭處于 MAC層之上，其中 PACK_TYPE代表報(bào)文類(lèi)型(這里為廣播數(shù)據(jù)包)，B_ID為本次廣播的標(biāo)識(shí)，BATCH_NUM 代表本次廣播包含批次的數(shù)量，BATCH_NO為廣播數(shù)據(jù)的批次號(hào)，CPACK_NO是編碼包的序號(hào)，CODE_VECTOR為編碼向量。

圖3 非編碼廣播和編碼廣播機(jī)制比較圖

圖4 編碼廣播數(shù)據(jù)包格式

3.3 節(jié)點(diǎn)間廣播數(shù)據(jù)交互

為了降低廣播延遲，傳感器節(jié)點(diǎn)之間在彼此進(jìn)行編碼廣播數(shù)據(jù)傳輸時(shí)采用泛洪的機(jī)制。當(dāng)任意兩個(gè)傳感器節(jié)點(diǎn)進(jìn)入彼此通信范圍內(nèi)時(shí)，節(jié)點(diǎn)間首先通過(guò)交換各自的消息索引向量SV(Summary Vector)來(lái)確定自身能夠提供給對(duì)方的編碼數(shù)據(jù)包及其數(shù)量，然后將編碼數(shù)據(jù)包發(fā)送給對(duì)方。假設(shè)a為節(jié)點(diǎn)i某批次所缺少編碼包數(shù)量，而b為鄰居節(jié)點(diǎn)j能夠提供的該批次不同序號(hào)編碼包的數(shù)量，則節(jié)點(diǎn)j向i傳輸編碼包的數(shù)量為min(a,b)。實(shí)際傳輸中由于受到信道不確定性的影響，對(duì)丟失的廣播數(shù)據(jù)包需要進(jìn)行重傳，NBT采用簡(jiǎn)單自動(dòng)請(qǐng)求重傳機(jī)制，最高重傳次數(shù)設(shè)定為m。

向量SV格式及任意兩節(jié)點(diǎn)間通信過(guò)程如圖5(a)和5(b)所示。其中BATCH_NUM表示節(jié)點(diǎn)自身具有批次的數(shù)量，SV_LEN給出了該 SV的長(zhǎng)度，BATCH_NO是批次的編號(hào)，其后的 CPACK_NUM 表示節(jié)點(diǎn)具有該批次編碼消息的數(shù)量，而CPACK_NO則給出節(jié)點(diǎn)具體有該批次的哪些編碼包。當(dāng)傳感器節(jié)點(diǎn)與基站BS相遇時(shí)，BS也需要根據(jù)節(jié)點(diǎn)提供的SV來(lái)進(jìn)行廣播數(shù)據(jù)的傳輸。

3.4 節(jié)點(diǎn)譯碼

由于節(jié)點(diǎn)的移動(dòng)性，DTMSN中節(jié)點(diǎn)間保持連接的時(shí)間通常較短，為了在有限的時(shí)間內(nèi)盡量多地進(jìn)行數(shù)據(jù)傳輸，在NBT機(jī)制中節(jié)點(diǎn)并不是每接收到一個(gè)新的編碼數(shù)據(jù)包后就試圖解碼，而是在獲取足夠多的編碼數(shù)據(jù)包后才進(jìn)行解碼操作，具體為：節(jié)點(diǎn)接收到一個(gè)新的編碼數(shù)據(jù)包后，首先判斷該批次中自身已有的編碼包數(shù)量是否達(dá)到l，如果編碼包數(shù)量達(dá)到l，則提取l個(gè)編碼向量并利用高斯消去法判斷編碼矩陣是否滿(mǎn)秩，滿(mǎn)秩則進(jìn)行解碼；否則將冗余向量對(duì)應(yīng)的編碼數(shù)據(jù)包刪除，重新向?qū)Ψ秸?qǐng)求序號(hào)為其它值的本批次編碼包。

由于 NBT中序號(hào)不同的編碼包采用的編碼向量是不同的，因此節(jié)點(diǎn)只要接收到l個(gè)序號(hào)不同的編碼包就能以很高的概率進(jìn)行譯碼，這種對(duì)編碼包添加序號(hào)的方法能夠大大節(jié)省傳感器節(jié)點(diǎn)的計(jì)算開(kāi)銷(xiāo)和時(shí)間，從而保證在較短的連接時(shí)間內(nèi)盡量完成數(shù)據(jù)傳輸。我們?cè)赥I公司CC2430片上系統(tǒng)上設(shè)計(jì)實(shí)現(xiàn)了8

GF(2)上的8個(gè)數(shù)據(jù)包的編解碼算法，實(shí)驗(yàn)得出平均編碼時(shí)間為 10.8 ms，解碼時(shí)間為 70.08 ms，因此可以看出 NBT完全可以用于資源受限的DTMSN當(dāng)中。

圖5 索引向量SV格式及通信過(guò)程

不失一般性地，我們假定Γ={(i,n)|i＞0,n＞0}為傳感器節(jié)點(diǎn)內(nèi)編碼數(shù)據(jù)包所對(duì)應(yīng)的批次號(hào)和編碼序號(hào)二元組的集合，其中i為批次號(hào)，n為序號(hào)。代表傳感器節(jié)點(diǎn)所包含的批次為i的各編碼數(shù)據(jù)包所對(duì)應(yīng)的編碼向量的集合，為編碼包的編碼向量，C(φ)表示集合φ中元素的個(gè)數(shù)。則傳感器節(jié)點(diǎn)在接收到某一編碼向量為的編碼包后譯碼算法如表1所示。

表1 譯碼算法偽碼

表2 模擬實(shí)驗(yàn)參數(shù)

4 仿真實(shí)驗(yàn)及性能分析

根據(jù)表2的實(shí)驗(yàn)參數(shù)，本文使用 ONE(Opportunistic Networking Environment)模擬器，在RWP移動(dòng)策略下，通過(guò)修改EpidemicRouter路由包仿真實(shí)現(xiàn)了泛洪、k-鄰居(k=2),NBT 3種廣播傳輸機(jī)制，并在網(wǎng)絡(luò)中90%的節(jié)點(diǎn)收到全部廣播數(shù)據(jù)包情況下，從廣播數(shù)據(jù)包總量、數(shù)據(jù)包傳輸延時(shí)兩方面對(duì)以上機(jī)制進(jìn)行了比較，同時(shí)分析了不同實(shí)驗(yàn)參數(shù)對(duì)各種傳輸機(jī)制造成的影響。

仿真實(shí)驗(yàn)中，傳感器節(jié)點(diǎn)運(yùn)行區(qū)域A為100 m× 1 00 m的正方形區(qū)域， BS位于區(qū)域中心。由于DTMSN通常部署在信道條件比較惡劣的環(huán)境當(dāng)中，因此數(shù)據(jù)通信過(guò)程中，設(shè)定節(jié)點(diǎn)間的數(shù)據(jù)傳輸成功率為0.5~0.75之間的隨機(jī)值，廣播重傳次數(shù)為1。其他具體實(shí)驗(yàn)參數(shù)參見(jiàn)表2。所有實(shí)驗(yàn)結(jié)果均為100次獨(dú)立運(yùn)行結(jié)果的均值。

4.1 節(jié)點(diǎn)數(shù)據(jù)相關(guān)度

針對(duì)泛洪、k-鄰居(k=2),NBT 3種廣播機(jī)制，當(dāng)30%,50%,70%,90%的傳感器節(jié)點(diǎn)接收到全部廣播數(shù)據(jù)包時(shí)，接收到廣播數(shù)據(jù)包的節(jié)點(diǎn)之間平均數(shù)據(jù)相關(guān)度仿真結(jié)果如圖6所示。從圖中可以看出，隨著接收到全部廣播數(shù)據(jù)包的節(jié)點(diǎn)比例的提高，3種機(jī)制的數(shù)據(jù)相關(guān)度都呈增長(zhǎng)趨勢(shì)，其主要原因是越來(lái)越多的節(jié)點(diǎn)收到了所有的廣播數(shù)據(jù)，因此相關(guān)度越來(lái)越高。而3種機(jī)制中，NBT機(jī)制的相關(guān)度最低，而其他兩種方法的相關(guān)度則比較接近，這主要是由于NBT機(jī)制中BS每次都將不同的編碼數(shù)據(jù)包發(fā)送給傳感器節(jié)點(diǎn)，由此降低了節(jié)點(diǎn)彼此之間的數(shù)據(jù)相關(guān)度。

圖6 3種廣播機(jī)制節(jié)點(diǎn)相關(guān)度

4.2 數(shù)據(jù)完全接收條件下節(jié)點(diǎn)平均連接數(shù)

節(jié)點(diǎn)間數(shù)據(jù)相關(guān)度小，說(shuō)明節(jié)點(diǎn)之間能夠進(jìn)行交換的數(shù)據(jù)數(shù)量較大，因此節(jié)點(diǎn)便可以經(jīng)過(guò)較少的連接就接收到所有廣播數(shù)據(jù)包。在表2參數(shù)條件下，通過(guò)仿真，我們給出了在完全接收到廣播數(shù)據(jù)時(shí)，3種機(jī)制中每個(gè)節(jié)點(diǎn)所經(jīng)歷的平均連接數(shù)(如表3所示)。從表3我們可以看出k-鄰居機(jī)制由于需要在鄰居數(shù)大于2的情況下才能進(jìn)行數(shù)據(jù)傳輸，因此連接次數(shù)最多，而NBT機(jī)制所需要的連接則最少。

表3 節(jié)點(diǎn)平均連接數(shù)

4.3 3種機(jī)制性能比較分析

在表2給定的默認(rèn)參數(shù)條件下，當(dāng)90%節(jié)點(diǎn)收到全部廣播數(shù)據(jù)包時(shí)，3種廣播機(jī)制的具體性能見(jiàn)表4。從表中可以看出NBT機(jī)制的傳輸時(shí)延最低，只有72.1 s，其次是泛洪機(jī)制，為79.2 s，廣播延遲降低接近 10%；由于k-鄰居(k.=2)機(jī)制只有在節(jié)點(diǎn)有2個(gè)以上鄰居的情況下才能進(jìn)行數(shù)據(jù)傳輸，因此傳輸時(shí)延較長(zhǎng)。NBT廣播時(shí)延較低的主要原因是節(jié)點(diǎn)中編碼數(shù)據(jù)的相關(guān)度較低，節(jié)點(diǎn)可以用更少的連接次數(shù)便可獲取全部廣播數(shù)據(jù)。另外，從通信開(kāi)銷(xiāo)的角度來(lái)看，NBT和泛洪機(jī)制的廣播數(shù)據(jù)包總量基本相同，開(kāi)銷(xiāo)較大，其主要原因在于二者都采用泛洪機(jī)制進(jìn)行數(shù)據(jù)傳輸；而k-鄰居機(jī)制利用信道的廣播特性節(jié)省了開(kāi)銷(xiāo)。這里需要指出的是在k-鄰居機(jī)制中，當(dāng)k=1時(shí)，該機(jī)制同泛洪機(jī)制相同，k越大廣播延遲越高。

4.4 節(jié)點(diǎn)密度對(duì)性能的影響

圖7(a),7(b)分別給出了在節(jié)點(diǎn)密度變化條件下，3種機(jī)制的廣播時(shí)延和廣播數(shù)據(jù)量的仿真結(jié)果。從圖7(a)中我們可以看出，隨著節(jié)點(diǎn)數(shù)量的增多，節(jié)點(diǎn)間連接發(fā)生的時(shí)間間隔也隨之降低，因此3種機(jī)制的廣播時(shí)延都呈下降趨勢(shì)，其中NBT機(jī)制時(shí)延最小，k-鄰居(k=2)機(jī)制時(shí)延最大。而由于節(jié)點(diǎn)數(shù)量的增多，需要傳輸?shù)膹V播數(shù)據(jù)包的數(shù)量也相應(yīng)增加，因此從圖7(b)中可以看出，廣播數(shù)據(jù)量與節(jié)點(diǎn)數(shù)量基本呈線(xiàn)性增長(zhǎng)的關(guān)系，其中k-鄰居機(jī)制的通信開(kāi)銷(xiāo)最小，NBT機(jī)制小于泛洪機(jī)制，開(kāi)銷(xiāo)較大。

表4 默認(rèn)參數(shù)下仿真性能

4.5 節(jié)點(diǎn)速度對(duì)性能的影響

圖8(a),8(b)分別給出了在RWP模型中節(jié)點(diǎn)最大運(yùn)行速度變化條件下，3種機(jī)制的廣播時(shí)延和廣播數(shù)據(jù)量的仿真結(jié)果。由于在節(jié)點(diǎn)密度不變的條件下，節(jié)點(diǎn)移動(dòng)速度越快，同等時(shí)間內(nèi)節(jié)點(diǎn)移動(dòng)所覆蓋的區(qū)域越大，也就能夠與更多節(jié)點(diǎn)產(chǎn)生連接，從而降低了廣播時(shí)延。因此從圖8(a)中可以看出，3種機(jī)制隨著速度的增大，廣播時(shí)延是逐漸降低的，其中NBT機(jī)制的時(shí)延最小。而由于節(jié)點(diǎn)數(shù)量基本不變，因此需要廣播的數(shù)據(jù)包總量也不變，因此3種機(jī)制廣播數(shù)據(jù)量在節(jié)點(diǎn)速度變化的情況基本平穩(wěn)，起伏不大，如圖8(b)所示。

4.6 節(jié)點(diǎn)通信半徑對(duì)性能的影響

圖9(a),9(b)分別給出了在節(jié)點(diǎn)通信半徑變化條件下，3種機(jī)制的廣播時(shí)延和廣播數(shù)據(jù)量的仿真結(jié)果。由于節(jié)點(diǎn)通信半徑的增加，節(jié)點(diǎn)通信半徑覆蓋范圍內(nèi)其他節(jié)點(diǎn)出現(xiàn)的概率也將隨之增加，因此節(jié)點(diǎn)間能夠進(jìn)行數(shù)據(jù)交換的機(jī)會(huì)也將變大，從而降低了廣播時(shí)延。因此圖9(a)中3種機(jī)制的廣播時(shí)延隨著通信半徑的增加都呈下降趨勢(shì)，其中k-鄰居 (k=2)廣播時(shí)延下降最快，而NBT時(shí)延最小。由于泛洪、NBT機(jī)制采用泛洪進(jìn)行數(shù)據(jù)通信，因此節(jié)點(diǎn)數(shù)量不變的情況下廣播數(shù)據(jù)量也基本不變；而k-鄰居機(jī)制由于通信半徑的增加提高廣播機(jī)會(huì)，通信量呈下降趨勢(shì)，具體如圖9(b)所示。

4.7 參數(shù)l對(duì)性能的影響

NBT機(jī)制中參數(shù)l代表每一批次當(dāng)中包含的原始數(shù)據(jù)包數(shù)量，也就是每次參與編碼的原始數(shù)據(jù)包數(shù)量。在表2實(shí)驗(yàn)參數(shù)條件下，l也代表需要廣播的原始數(shù)據(jù)包的數(shù)量。從圖10(a)中可以看出，隨著l的增大，3種機(jī)制的廣播時(shí)延呈現(xiàn)緩慢上升趨勢(shì)，升幅不大，說(shuō)明在廣播數(shù)量較小，通信帶寬足夠的情況下，3種機(jī)制的廣播時(shí)延主要取決于節(jié)點(diǎn)間連接發(fā)生的時(shí)間間隔。從圖10(b)中可以看出，隨著l的增大，也即需要廣播的原始數(shù)據(jù)的增加，廣播數(shù)據(jù)量也基本呈線(xiàn)性增長(zhǎng)的趨勢(shì)，符合實(shí)際情況。

圖7 節(jié)點(diǎn)數(shù)量變化對(duì)廣播時(shí)延和廣播數(shù)據(jù)量的影響

圖8 節(jié)點(diǎn)速度變化對(duì)廣播時(shí)延和廣播數(shù)據(jù)量的影響

圖9 通信半徑變化對(duì)廣播時(shí)延和廣播數(shù)據(jù)量的影響

圖10 參數(shù)l變化對(duì)廣播時(shí)延和廣播數(shù)據(jù)量的影響

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

本文提出的基于網(wǎng)絡(luò)編碼的低時(shí)延廣播傳輸機(jī)制NBT，能夠較好的完成DTMSN數(shù)據(jù)的廣播傳輸功能。其主要貢獻(xiàn)有：(1)首次將隨機(jī)網(wǎng)絡(luò)編碼引入到DTMSN廣播通信當(dāng)中，使得在拓?fù)浣Y(jié)構(gòu)時(shí)變的網(wǎng)絡(luò)中也能應(yīng)用網(wǎng)絡(luò)編碼技術(shù)，拓展了網(wǎng)絡(luò)編碼的應(yīng)用領(lǐng)域。(2)通過(guò)BS對(duì)相同原始數(shù)據(jù)包的多次隨機(jī)編碼來(lái)降低廣播數(shù)據(jù)相關(guān)度，從而降低了數(shù)據(jù)廣播過(guò)程中所需要的平均連接次數(shù)，提高了廣播時(shí)延性能。(3)在廣播通信開(kāi)銷(xiāo)基本相同的前提下，找到一種比泛洪機(jī)制具有更好時(shí)延性能的廣播傳輸機(jī)制。

雖然NBT機(jī)制有著較好的廣播時(shí)延性能，但該機(jī)制也存在著廣播開(kāi)銷(xiāo)較大的缺點(diǎn)，這也是我們下一步研究過(guò)程中將著重解決的問(wèn)題。

[1]Leguay J,Friedman T,and Conan V.DTN routing in a mobility pattern space[C].In ACM Workshop on Delay Tolerant Networking and Related Topics (SIGCOMM 2005),New York,NY,USA,2005: 276-283.

[2]Cheng L,Das S K,Di Francesco M,et al..Scalable and energy-efficient broadcasting in multi-hop cluster-based wireless sensor network[C].The 2011 IEEE International Conference on Communications (ICC 2011),Kyoto,Japan,2011: 1-5.

[3]Huang T,Lin Y,and Tang L.Neighbor-aware gossip-based broadcasting scheme for wireless sensor networks[C].2010 International Conference on Communications and Mobile Computing,Shenzhen,China,2010: 293-297.

[4]Montolio-Aranda P,García-Alfaro J,and Megías D.Improved flooding of broadcast messages using extended multipoint relaying[J].JNetwork and Computer Applications,2011,34(2): 542-550.

[5]Wang Y and Wu H.Delay/Fault-tolerant mobile sensor network (DFT-MSN): a new paradigm for pervasive information gathering[J].IEEE Transactions on Mobile Computing,2006,6(8): 1021-1034.

[6]Xu X,Luo J,and Zhang Q.Delay tolerant event collection in sensor networks with mobile sink[C].In 2010 Proceedings IEEE INFOCOM,San Diego,California,USA,2010: 1-9.

[7]Talipov E and Cha H.Communication capacity-based message exchange mechanism for delay-tolerant networks[J].Computer Network,2011,55(15): 3408-3422.

[8]Vahdat A and Becker D.Epidemic routing for partially connected Ad hoc networks[R].Technical Report CS-200006,Duke University,Apr.2000.

[9]Goundan A,Coe E,and Raghavendra C.Efficient Broadcasting in Delay Tolerant Networks[C].Proc.GLOBECOM,New Orleans,Louisiana,USA,2008: 523-527.

[10]Ahlswede R,Cai N,Li S Y R,et al..Network information flow[J].IEEE Transactions on Information Theory,2000,46(4): 1204-1216.

[11]Fragouli C,Widmer J,and Boudec J L.Efficient broadcasting using network coding[J].Presented at IEEE/ACM Transactions on Networking,2008,16(2): 450-463.

[12]Widmer J and Boudec J L.Network coding for efficient communication in extreme networks[C].In Proceedings of the ACM SIGCOMM Workshop on Delay-Tolerant Networking,Philadelphia,PA,USA,2005: 284-291.

[13]Bettstetter C,Hartenstein H,and Prez-Costa X.Stochastic properties of Random Waypoint mobility model[J].Wireless Networks,2004,10(5): 555-567.

[14]Ho T,Koetter R,Médard M,et al..The benefits of coding over routing in a randomized setting[C].Proceedings of IEEE International Symposium on Information Theory,Yokohama,Japan,2003: 442-447.

[15]Ho T,Médard M,Shi J,et al..On randomized network coding[C].41st Annual Allerton Conference on Communication Control and Computing,Monticello,IL,USA,2003: 11-20.