基于網絡編碼的延遲容忍移動傳感器網絡低時延廣播傳輸機制

楊奎武 郭淵博 馬 駿 鄭康鋒

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

②(北京郵電大學網絡與交換國家重點實驗室信息安全中心 北京 100876)

1 引言

近年來，延遲容忍移動傳感器網絡(DTMSN)[1]由于其廣泛的適用性和廣闊的應用前景而備受關注。在DTMSN網絡中，由于傳感器節點的移動或休眠等原因，使得網絡具有間歇連通的特點，即網絡中傳感器節點之間大多不存在穩定連通路徑。因此，節點間的數據傳輸主要依靠傳感器節點移動過程中的機會性連接來實現。同樣，廣播作為一種重要的網絡數據傳輸方式，在DTMSN中，也必須通過節點間的機會連接來完成，這就使得傳統的基于簇[2]、協商[3]、多點中繼[4]的廣播機制無法適用于DTMSN網絡。

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

DT是DTMSN中最基本的數據傳輸策略，其基本思想是節點在運動過程中只與 BS進行通信。DT可以用來實現廣播數據的傳輸，但其實際上是利用多次單播來實現廣播的目的。由于DT機制中節點只接收 BS的廣播數據，因此節點通信開銷非常小，但廣播時延卻很高。

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

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

網絡編碼[10]作為一種提高網絡吞吐量、降低網絡開銷的重要手段近年來受到廣泛重視。基于網絡編碼的廣播機制的研究也取得了較多的研究成果[11,12]，但目前這些成果基本上都是以靜態網絡為研究對象，而將網絡編碼應用于動態的DTMSN廣播數據傳輸的相關研究則沒有。

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

2 網絡模型及知識基礎

2.1 網絡模型

如圖1所示，假設DTMSN初始部署時，M個傳感器節點隨機分布在一個l×l的正方形區域A內(虛線代表節點通信半徑)，基站BS位于區域中心，靜止不動。節點通信半徑為r，所有節點的移動都遵循Random WayPoint (RWP)[13]運動模型。

圖1 DTMSN網絡模型

2.2 知識基礎

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

當目的節點接收到任意l個編碼包組成的集合C={C1,C2,…,Cl}后，若其對應的編碼矩陣G={g1,g2,…,gl}各編碼向量線性無關(滿秩)，則可根據式(2)進行譯碼并恢復出原始數據集合P。

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

2.2.2節點數據相關度

定義 任意兩節點i,j的數據相關度是指i,j具有的相同數據包的數量與他們全部數據包(不包括重復)數量的比，我們用ρij表示。

圖2 編碼矩陣滿秩概率

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

3 NBT廣播傳輸機制

3.1 NBT基本原理

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

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

3.2 原始數據編碼

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

圖3 非編碼廣播和編碼廣播機制比較圖

圖4 編碼廣播數據包格式

3.3 節點間廣播數據交互

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

向量SV格式及任意兩節點間通信過程如圖5(a)和5(b)所示。其中BATCH_NUM表示節點自身具有批次的數量，SV_LEN給出了該 SV的長度，BATCH_NO是批次的編號，其后的 CPACK_NUM 表示節點具有該批次編碼消息的數量，而CPACK_NO則給出節點具體有該批次的哪些編碼包。當傳感器節點與基站BS相遇時，BS也需要根據節點提供的SV來進行廣播數據的傳輸。

3.4 節點譯碼

由于節點的移動性，DTMSN中節點間保持連接的時間通常較短，為了在有限的時間內盡量多地進行數據傳輸，在NBT機制中節點并不是每接收到一個新的編碼數據包后就試圖解碼，而是在獲取足夠多的編碼數據包后才進行解碼操作，具體為：節點接收到一個新的編碼數據包后，首先判斷該批次中自身已有的編碼包數量是否達到l，如果編碼包數量達到l，則提取l個編碼向量并利用高斯消去法判斷編碼矩陣是否滿秩，滿秩則進行解碼；否則將冗余向量對應的編碼數據包刪除，重新向對方請求序號為其它值的本批次編碼包。

由于 NBT中序號不同的編碼包采用的編碼向量是不同的，因此節點只要接收到l個序號不同的編碼包就能以很高的概率進行譯碼，這種對編碼包添加序號的方法能夠大大節省傳感器節點的計算開銷和時間，從而保證在較短的連接時間內盡量完成數據傳輸。我們在TI公司CC2430片上系統上設計實現了8

GF(2)上的8個數據包的編解碼算法，實驗得出平均編碼時間為 10.8 ms，解碼時間為 70.08 ms，因此可以看出 NBT完全可以用于資源受限的DTMSN當中。

圖5 索引向量SV格式及通信過程

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

表1 譯碼算法偽碼

表2 模擬實驗參數

4 仿真實驗及性能分析

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

仿真實驗中，傳感器節點運行區域A為100 m× 1 00 m的正方形區域， BS位于區域中心。由于DTMSN通常部署在信道條件比較惡劣的環境當中，因此數據通信過程中，設定節點間的數據傳輸成功率為0.5~0.75之間的隨機值，廣播重傳次數為1。其他具體實驗參數參見表2。所有實驗結果均為100次獨立運行結果的均值。

4.1 節點數據相關度

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

圖6 3種廣播機制節點相關度

4.2 數據完全接收條件下節點平均連接數

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

表3 節點平均連接數

4.3 3種機制性能比較分析

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

4.4 節點密度對性能的影響

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

表4 默認參數下仿真性能

4.5 節點速度對性能的影響

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

4.6 節點通信半徑對性能的影響

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

4.7 參數l對性能的影響

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

圖7 節點數量變化對廣播時延和廣播數據量的影響

圖8 節點速度變化對廣播時延和廣播數據量的影響

圖9 通信半徑變化對廣播時延和廣播數據量的影響

圖10 參數l變化對廣播時延和廣播數據量的影響

5 結束語

本文提出的基于網絡編碼的低時延廣播傳輸機制NBT，能夠較好的完成DTMSN數據的廣播傳輸功能。其主要貢獻有：(1)首次將隨機網絡編碼引入到DTMSN廣播通信當中，使得在拓撲結構時變的網絡中也能應用網絡編碼技術，拓展了網絡編碼的應用領域。(2)通過BS對相同原始數據包的多次隨機編碼來降低廣播數據相關度，從而降低了數據廣播過程中所需要的平均連接次數，提高了廣播時延性能。(3)在廣播通信開銷基本相同的前提下，找到一種比泛洪機制具有更好時延性能的廣播傳輸機制。

雖然NBT機制有著較好的廣播時延性能，但該機制也存在著廣播開銷較大的缺點，這也是我們下一步研究過程中將著重解決的問題。

[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.