一種基于網(wǎng)絡(luò)編碼的組播共享樹算法?

梁建華，張振宇，楊文忠

(1.新疆大學(xué)軟件學(xué)院，新疆烏魯木齊830008;2.新疆大學(xué)信息科學(xué)與工程學(xué)院，新疆烏魯木齊830046)

0 引言

無線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測區(qū)域內(nèi)大量廉價的微型傳感器節(jié)點通過無線通信形成一個多跳的相互協(xié)助工作的分布式自組織網(wǎng)絡(luò)，節(jié)點所獲得的信息通過中間節(jié)點整合發(fā)送給數(shù)據(jù)接收中心[1]．網(wǎng)絡(luò)的生存時間是無線傳感器網(wǎng)絡(luò)的一個重要性能指標(biāo)，因此降低網(wǎng)絡(luò)消耗是關(guān)鍵性的性能需求．此外，無線帶寬利用、均衡網(wǎng)絡(luò)負載和服務(wù)質(zhì)量等方面逐漸成為無線傳感器網(wǎng)絡(luò)研究的重點．

組播[2]是一種允許一個或者多個發(fā)送節(jié)點發(fā)送單一的數(shù)據(jù)包到多個接收節(jié)點的技術(shù)．由于發(fā)送節(jié)點不必向每一個接收節(jié)點發(fā)送數(shù)據(jù)，從而減少了數(shù)據(jù)的復(fù)制和傳輸，在能量節(jié)約、帶寬利用方面提高了網(wǎng)絡(luò)性能．組播路由根據(jù)具體的應(yīng)用場景和不同的路由思想等可分3類：基于拓撲結(jié)構(gòu)的組播路由[3?6]、基于空間地理位置的組播路由[7?9]和基于節(jié)能的組播路由[10?12]．基于拓撲結(jié)構(gòu)的組播路由將網(wǎng)絡(luò)中的節(jié)點根據(jù)不同的啟發(fā)式算法，建立滿足需求的steiner樹和分層的樹型結(jié)構(gòu)．?dāng)?shù)據(jù)從源節(jié)點沿著組播樹中的最短路徑發(fā)送到網(wǎng)絡(luò)中的其他節(jié)點．雖然根據(jù)組播樹中的最優(yōu)路徑可以把信息快速準(zhǔn)確的發(fā)送給網(wǎng)絡(luò)中的節(jié)點，但是維護組播樹和節(jié)點的狀態(tài)需要消耗大量的能量．基于空間地理位置的組播路由算法中，網(wǎng)絡(luò)中的每一個節(jié)點不必知道全局的拓撲結(jié)構(gòu)，只要知道組播節(jié)點的位置和自己當(dāng)前所在的位置，利用位置算法計算離組播區(qū)域更近的下一跳節(jié)點，雖然減少了路由的開銷，但降低了網(wǎng)絡(luò)帶寬利用率，增加了網(wǎng)絡(luò)傳輸時延．基于節(jié)能的組播路由協(xié)議節(jié)能效果較好，旨在考慮傳感器節(jié)點的能量消耗，但較少考慮網(wǎng)絡(luò)的吞吐量、帶寬利用和可靠性．由于地理環(huán)境和屏蔽效應(yīng)，鏈路的質(zhì)量通常比較低，進而導(dǎo)致網(wǎng)絡(luò)資源消耗過快和較低的吞吐量．

為了提高網(wǎng)絡(luò)能耗效率、帶寬利用率和可靠性，本文提出了一種基于網(wǎng)絡(luò)編碼的組播算法（MABNC），該算法在組播中建了兩條冗余路徑．利用網(wǎng)絡(luò)編碼，鏈路輸入端將數(shù)據(jù)編碼整合，從而在鏈路輸出端得到多條數(shù)據(jù)流，提高了帶寬利用率，有效減少了網(wǎng)絡(luò)資源消耗和網(wǎng)絡(luò)時延．

1 網(wǎng)絡(luò)編碼

網(wǎng)絡(luò)編碼[13]是一種融合編碼和路由的信息交換技術(shù)，極大地提高網(wǎng)絡(luò)的吞吐量和可靠性．在傳統(tǒng)存儲轉(zhuǎn)發(fā)的路由方法基礎(chǔ)上，通過允許對接收的多個數(shù)據(jù)包進行編碼信息融合，增加單次傳輸?shù)男畔⒘?，提高網(wǎng)絡(luò)整體性能．

1.1 編碼

源節(jié)點將數(shù)據(jù)包分為M1，M2···Mn塊，線性網(wǎng)絡(luò)編碼將數(shù)據(jù)塊賦予系數(shù)gi，在有限域里每個數(shù)據(jù)包乘以系數(shù)得到編碼后的數(shù)據(jù)包，其中g(shù)=(gi···gn)是編碼向量，X是數(shù)據(jù)矢量，編碼向量和數(shù)據(jù)矢量必須與編碼數(shù)據(jù)包發(fā)送到下一個節(jié)點．

1.2 解碼

當(dāng)目的節(jié)點完全接收到(g1,X1),···,(gm,Xm)以后，根據(jù)公式1只需要解碼一組方程來恢復(fù)原始數(shù)據(jù)包M1,···,Mn．其過程是一個解逆矩陣．

其中，如果m≥n，編碼向量g就是線性獨立，因此目的節(jié)點根據(jù)線性無關(guān)可以恢復(fù)n個原始數(shù)據(jù)(M1,···,Mn)．由于有些組合線性也許不是線性無關(guān)，則條件是不夠的．選擇線性相關(guān)組合的概率取決于網(wǎng)絡(luò)規(guī)模的大?。贔ragouli[14]的實驗仿真展示了甚至是較小的場地線性相關(guān)組合的概率可以被忽略．因此一個節(jié)點收到足夠的數(shù)據(jù)向量可以很容易完成解碼恢復(fù)原來的數(shù)據(jù)包．

2 基于網(wǎng)絡(luò)編碼的組播共享樹算法

2.1 冗余路徑

基于樹型結(jié)構(gòu)的組播路由，其中目的節(jié)點到源節(jié)點只有一條傳輸路徑．基于網(wǎng)絡(luò)編碼的共享樹路由在組播中建了兩條冗余路徑，多個目的節(jié)點共享一個源節(jié)點．如圖1所示，目標(biāo)節(jié)點T1到源節(jié)點的兩條不相交的路徑（黑色的鏈接是T1的第一條道路，左邊第二個路徑是白色）．沒有網(wǎng)絡(luò)編碼，兩個目標(biāo)節(jié)點不能同時得到信息流a和b．處在“瓶頸”鏈路的中間節(jié)點U3上應(yīng)用網(wǎng)絡(luò)編碼，目標(biāo)節(jié)點T1可以從源節(jié)點接收a和（a+b）信息流．同樣，目標(biāo)節(jié)點T2可以接收b和（a+b）信息流．節(jié)點T1和T2通過簡單的模加法運算可以恢復(fù)原始數(shù)據(jù)a和b．

2.2 組播路徑

組播路徑的建立過程如圖2所示．為便于解釋，只取一個源節(jié)點的情況．開始只有一個源節(jié)點，沒有目的節(jié)點，如圖2（a）所示．如果一個目的節(jié)點要加入到組播，源節(jié)點將要建立兩條不相交的路徑，一條路徑的帶寬最大，一條路徑的時延最?。绻粋€目的節(jié)點加入到組播，那么這條路徑成本和延遲是1/(1+λk)，其中λ是一個變量，k是不屬于組播里的t節(jié)點的鄰居節(jié)點數(shù)量．如圖2（b）所示要求最短延遲，對于目標(biāo)節(jié)點U10，到源節(jié)點有兩條路徑r1：S-U1-U5-U10和r2：S-U2-U6-U10．目的節(jié)點不僅可以與中間節(jié)點進行通信，還可以與其他目的節(jié)點進行通信．如圖2（c）所示，U11則可以把U10當(dāng)作中間節(jié)點，經(jīng)過U10到源節(jié)點建立一條路徑．當(dāng)所有目的節(jié)點到源節(jié)點都建立了兩條冗余路徑，則組播路徑建立完成．圖2（d）展示了在建立組播路徑時如何實現(xiàn)網(wǎng)絡(luò)編碼．由于目的節(jié)點到源節(jié)點有幾條不同的路徑，所以目的節(jié)點可以共享路徑，稱為瓶頸路徑，例如（S,U1）和（U6，U10），并通過網(wǎng)絡(luò)編碼處理．

圖1 網(wǎng)絡(luò)編碼冗余路徑

圖2 組播路徑

2.3 基于網(wǎng)絡(luò)編碼的組播共享樹算法

基于網(wǎng)絡(luò)編碼的組播共享樹算法首先選取源節(jié)點作為樹的根節(jié)點，建立組播路徑到共享樹里，然后從目的節(jié)點搜索組播路徑添加到共享樹．基于網(wǎng)絡(luò)編碼的組播共享樹算法有多個節(jié)點為編碼節(jié)點，其主要建立步驟：1）根據(jù)編碼節(jié)點算法選取編碼節(jié)點；2）把有編碼節(jié)點的組播路徑添加到共享樹中；3）在組播路徑之上建立源節(jié)點到目的節(jié)點的冗余路徑，經(jīng)過編碼節(jié)點傳輸數(shù)據(jù)．

2.3.1 編碼節(jié)點

如圖3所示，s1和s2是源節(jié)點，d1，d2和d3是目標(biāo)節(jié)點集合，其他節(jié)點是具有編碼功能的中間節(jié)點．邊上的值表示每條鏈路的代價，那么根據(jù)上面的算法Smin(A)=2，Smin(B)=3，Smin(C)=4，Smin(D)=3···，Smin(A)最小，因此選擇A節(jié)點作為編碼節(jié)點．A節(jié)點接收來至所有的源節(jié)點的數(shù)據(jù)并且編碼．

2.3.2 共享組播樹

根據(jù)編碼節(jié)點的選擇算法，基于網(wǎng)絡(luò)編碼的組播共享樹的建立過程如下：

1）首先從源節(jié)點到中間節(jié)點建立組播路徑，然后將目的節(jié)點加入到組播路徑中；

2）利用編碼節(jié)點選擇策略在組播路徑中選擇編碼節(jié)點；

3）在網(wǎng)絡(luò)中計算編碼節(jié)點到每個目的節(jié)點沒有共享的路徑數(shù)量，如果大于2，則反復(fù)用Dijkstra算法在部分網(wǎng)絡(luò)或者整個網(wǎng)絡(luò)中篩選出2條從編碼節(jié)點到每個目的節(jié)點的最短非共享路徑；

4）重復(fù)步驟2直到每個目的節(jié)點找到兩條冗余路徑，組成組播共享樹；

5）平均分配數(shù)據(jù)到編碼節(jié)點，再把編碼數(shù)據(jù)傳輸?shù)侥康墓?jié)點．

如圖4所示：編碼節(jié)點A作為源節(jié)點，A到其他中間節(jié)點可以獲得最短路徑，例如A-B，A-C，A-H，AB-D，A-C-F，A-H-I，A-D-E和A-C-F-G．然后通過Dijkstra算法獲取各接收節(jié)點的非共享路徑．節(jié)點D1的兩條非共享路徑是A-B-D-D1和A-B-E-D1，節(jié)點D2的兩條非共享路徑是A-B-D2和A-C-D2，節(jié)點D3的兩條非共享路徑是A-H-G-D3和A-C-F-D3，最后將這些路徑添加到共享樹．

圖3 局部網(wǎng)絡(luò)拓撲

圖4 組播共享樹

3 仿真結(jié)果分析

為驗證算法的有效性，將MABNC算法與基于樹組播算法（Multicast based tree）[6]進行了比較．仿真利用了NS平臺，假設(shè)網(wǎng)絡(luò)中有500個節(jié)點隨機分布在一個100m*100m的矩形監(jiān)測區(qū)域內(nèi)，其中50個接收節(jié)點，匯聚節(jié)點位于網(wǎng)絡(luò)的中心位置．節(jié)點通信半徑R=20m，節(jié)點初始能量ε=200J，傳輸消息能耗為0.5J/KB，每個數(shù)據(jù)包大小為512byte．仿真時間為240s．仿真中信號碰撞、信號干擾等因素忽略不計．

3.1 平均能耗

根據(jù)文獻[15]，在傳感器網(wǎng)絡(luò)中能耗體現(xiàn)在數(shù)據(jù)的傳輸．每隔10s采集一次數(shù)據(jù)，開始30s左右構(gòu)建組播拓撲結(jié)構(gòu)，節(jié)點平均能耗有所上升，隨后的過程是數(shù)據(jù)的傳輸．如圖5所示，仿真表明基于網(wǎng)絡(luò)編碼的組播共享樹算法初始的能耗開銷比基于樹的組播算法能耗增加的速率快．然而，在數(shù)據(jù)傳輸時，利用網(wǎng)絡(luò)編碼機制有效減少了平均能量消耗．利用網(wǎng)絡(luò)編碼可以減少傳輸節(jié)點，讓數(shù)據(jù)傳輸更加有效．

圖5 節(jié)點平均能耗

圖6 網(wǎng)絡(luò)吞吐量

3.2 吞吐量

網(wǎng)絡(luò)帶寬的大小跟目標(biāo)接收節(jié)點的數(shù)量有關(guān)，仿真中500個節(jié)點有50個接收節(jié)點，目標(biāo)接收節(jié)點比率10%．圖6表明基于網(wǎng)絡(luò)編碼的組播共享樹的吞吐量接近組播樹的兩倍．有向組播網(wǎng)絡(luò)采用線性網(wǎng)絡(luò)編碼即可達到最大組播速率[16]．網(wǎng)絡(luò)中數(shù)據(jù)傳輸率的提高，在單位時間內(nèi)網(wǎng)絡(luò)吞吐量明顯增大．與基于樹的組播路由算法相比，基于網(wǎng)絡(luò)編碼的組播共享樹算法可以達到良好的組播最大流．

3.3 傳輸時延

如圖7所示，由于對比單位為毫秒，基于樹的組播路由算法的傳輸時延比基于網(wǎng)絡(luò)編碼的組播較小，但隨著實際的應(yīng)用時間的延長，基于網(wǎng)絡(luò)編碼的組播共享樹路由的優(yōu)勢會增大．由于傳感器節(jié)點動態(tài)的變化，網(wǎng)絡(luò)拓撲不穩(wěn)定，路由需要維持和調(diào)整樹的結(jié)構(gòu)從而影響組播的性能．

4 結(jié)束語

針對無線傳感器網(wǎng)絡(luò)資源消耗過快和帶寬利用率不足等問題，提出了一種基于網(wǎng)絡(luò)編碼的組播共享樹路由算法，利用開銷最小鏈路選擇網(wǎng)絡(luò)編碼節(jié)點．該算法在組播中建立兩條冗余路徑，在此基礎(chǔ)上在整個網(wǎng)絡(luò)中，每個目的節(jié)點選擇兩條最優(yōu)鏈路傳輸數(shù)據(jù)，提高了網(wǎng)絡(luò)帶寬利用率，均衡了鏈路消耗．實驗仿真表明該算法可以提高網(wǎng)絡(luò)吞吐量，減少了網(wǎng)絡(luò)資源消耗和傳輸時延．

圖7 網(wǎng)絡(luò)傳輸時延

參考文獻：

[1]Akyildiz IF,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks:A urvey[J].Computer Networks,2002,38(4):393-422.

[2]田捷.組播路由算法研究[D].武漢:武漢理工大學(xué),2005.

[3]The pvilojanapong N，Tobe Y，Sezaki K．An efficient multicast routing protocol for wireless sensor networks[J]．IEIC Technical Report，2005:419-422.

[4]Sheth A，Shucker B，Han R．VLM2:A very lightweight mobile multicast system for wireless sensor networks[C].IEEE Intl Conf on Wireless Communications and Networking，New Orleans，2003:1936-1941.

[5]Zhang W,Cao G,La Porta T.Dynamic proxy tree-based data dissemination schemes for wireless sensor networks[J].Wireless Networks,2007,13(5):583-595.

[6]Wang Fangfang，Tao Jun，Shao Birui．An energy-balanced multicast routing algorithm in wireless sensor networks[C].Proc of Ninth IEEE International Conference on Grid and Cloud Computing，Nanjing,2010:361-365.

[7]KoY B，Vatda N H．Geocasting in mobile ad hoc networks:Location-based multicast algorithms[C].Proc of the Second IEEE Workshop on Mobile Computer Systems and Applications，Washington:IEEE Computer Society，1999:101-110.

[8]Sanchez A，Ruiz M．Bandwidth-efficient geographic multicast routing protocol for wireless sensor networks[J].IEEE Sensors Journal，2007，7(5):627-636.

[9]Wu Shibo，Selcuk K.GMP:Distributed geographic multicast routing in wireless sensor networks[C].Proc of the 26th IEEE International Conference on Distributed Computing Systems，Lisboa:IEEE,2006:1-9.

[10]Chen C,He Z,Sun H,et al.A grid-based energy efficient routing protocol in Wireless Sensor Networks[C]//Wireless and Pervasive Computing(ISWPC),2013 International Symposium on.IEEE,2013:1-6.

[11]Mammu A S K,Sharma A,Hernandez-Jayo U,et al.A Novel Cluster-Based Energy Efficient Routing in Wireless Sensor Networks[C]//Advanced Information Networking and Applications(AINA),2013 IEEE 27th International Conference on.IEEE,2013:41-47.

[12]Minhas A A,Sattar D,Mustaq K,et al.Energy efficient multicast routing protocols for Wireless Sensor Networks[C]//Sustainable Technologies(WCST),2011 World Congress on.IEEE,2011:178-181.

[13]AHLSWEDE R，CAI N，LI S Y，et al．Network information f l ow[J]．IEEE Transactions on Information Theory，2000，46(4):1204-1216.

[14]Fragouli C,Le Boudec J Y,Widmer J.Network coding:an instant primer[J].ACM SIGCOMM Computer Communication Review,2006,36(1):63-68.

[15]Rex Min,Anantha Chandrakasan.A Framework for Energy-Scalable Communication in High-Density Wireless Networks[C].Proceedings of the 2002 International Symposium on Low Power Electronics and Design,2002:36-41.

[16]Li S Y R,Yeung R W,Cai N.Linear network coding[J].IEEE Trans on Informat ion Theory,2003,49(2):371-381.