基于網(wǎng)絡(luò)編碼的傳感網(wǎng)多徑路由模型分析

趙 煒，唐振民，紀(jì)淑標(biāo)，古 力，楊余旺

（南京理工大學(xué) 計算機學(xué)院，江蘇 南京210094）

0 引 言

由于無線傳感器網(wǎng)絡(luò) （WSN）節(jié)點多且網(wǎng)絡(luò)具有不穩(wěn)定性，傳統(tǒng)的單徑傳輸很難滿足網(wǎng)絡(luò)傳輸?shù)囊?。多徑路由可在一次路由發(fā)現(xiàn)過程中找到多條路徑［1－5］，從而減少路由發(fā)現(xiàn)的次數(shù)，同時利用多條鏈路的冗余特性，提高整個網(wǎng)絡(luò)成功交付率，降低控制開銷與端到端延遲。多徑路由的穩(wěn)定性和提資源利用率高的特點，使其更適合QoS路由要求。多路徑可以分為兩類：一類是不相交多徑路由 （disjoint multipath routing，DMR），每條路徑都不相交，每個節(jié)點只能在一條路徑中出現(xiàn)；另一類是相交多徑路由（braided multipath routing，BMR），一個節(jié)點可以在多條路徑中出現(xiàn)。但在WSN中應(yīng)用多徑路由技術(shù)也面臨一些新的挑戰(zhàn)：一方面，由于多徑路由技術(shù)采用并行方式傳輸數(shù)據(jù)報文，各路徑的帶寬、跳數(shù)以及節(jié)點處理能力的差異導(dǎo)致報文傳輸延時差別較大，在目的端會出現(xiàn)報文亂序現(xiàn)象；另一方面，WSN拓撲變化和鏈路差錯引起的路徑中斷會導(dǎo)致某些路徑擁塞，從而產(chǎn)生報文丟失現(xiàn)象。當(dāng)網(wǎng)絡(luò)規(guī)模較大時，采用傳統(tǒng)的解決方案如報文重排序和報文重傳機制將極大地增加網(wǎng)絡(luò)傳輸代價，因此，多徑路由應(yīng)用在WSN中也有一定的局限性。

網(wǎng)絡(luò)編碼理論［6－9］論證了中間節(jié)點對信息的數(shù)學(xué)運算可以提高網(wǎng)絡(luò)吞吐率，同時可以使網(wǎng)絡(luò)容量逼近網(wǎng)絡(luò)最大流。文獻 ［10］研究網(wǎng)絡(luò)編碼在纏繞多徑路由中應(yīng)用，證明使用網(wǎng)絡(luò)編碼能夠提高網(wǎng)絡(luò)的穩(wěn)定性和可靠性。文獻 ［11－15］系統(tǒng)地討論了網(wǎng)絡(luò)編碼技術(shù)在傳感器網(wǎng)絡(luò)中的理論研究和應(yīng)用，采用了一系列的評價指標(biāo)評估了網(wǎng)絡(luò)編碼技術(shù)與多徑路由的性能。本文主要分析討網(wǎng)絡(luò)編碼在不相交多路徑和纏繞多路徑兩種網(wǎng)絡(luò)環(huán)境中的性能，進一步討論采用網(wǎng)絡(luò)編碼技術(shù)后的成功交付率和網(wǎng)絡(luò)冗余度。通過計算仿真，發(fā)現(xiàn)相對于傳統(tǒng)多徑路由，采用該方法能夠在一定的報文丟失范圍內(nèi)有效提升多徑路由的容錯能力，提高網(wǎng)絡(luò)成功交付率，并降低網(wǎng)絡(luò)冗余度。

1 基于網(wǎng)絡(luò)編碼的多徑路由傳感器網(wǎng)絡(luò)模型

1.1 應(yīng)用網(wǎng)絡(luò)編碼的不相交多路徑傳感器網(wǎng)絡(luò)模型

本節(jié)采用經(jīng)典的多徑網(wǎng)絡(luò)模型，網(wǎng)絡(luò)拓撲如圖1所示。N條不相交的路徑分別記為第1到N條，其中每條路徑除發(fā)送端，包含的節(jié)點個數(shù)記為ni，i＝1，2，…，N，接收端為第ni個節(jié)點。

圖1 不相交多經(jīng)路由網(wǎng)絡(luò)拓撲

模型采用分包傳輸思想，應(yīng)用隨機線性編碼方案作為編碼方法。先是把數(shù)據(jù)包 （長度L）分成N個大小相等的數(shù)據(jù)包，然后對分割后的包再拆分成K個數(shù)據(jù)包，采用隨機線性編碼將K個包編碼生成K′個數(shù)據(jù)包 （K′≥K）。編碼后包長度為：L′＝L∕NK＋K，編碼后包每次轉(zhuǎn)發(fā)正確的概率為：p＝ （1－pb）L′，其中，pb為每字節(jié)傳輸誤碼率，根據(jù)隨機網(wǎng)絡(luò)編碼理論，每次傳輸時接收端只要正確接收K個線性不相關(guān)數(shù)據(jù)包就可還原出正確的原始數(shù)據(jù)包，所以每次正確接收K個或者多于K個數(shù)據(jù)包的概率可以由式 （1）表示

每條路徑需要發(fā)送ni次，計算出每條路徑正確接收率為qi＝qni。成功交付率 （successful delivery ratio，SDR），指由發(fā)送端發(fā)送的數(shù)據(jù)包成功正確地到達接收端的概率，因此成功交付率可由式 （2）給出

每條路徑轉(zhuǎn)發(fā)數(shù)據(jù)包總量可以由式 （3）給出

標(biāo)準(zhǔn)化冗余度 （normalized redundancy，NR），指成功交付一個數(shù)據(jù)包所平均需要在網(wǎng)絡(luò)中傳遞的數(shù)據(jù)包的總數(shù)。根據(jù)標(biāo)準(zhǔn)化冗余度的定義，可以得到該模型的標(biāo)準(zhǔn)化冗余度如下所示

1.2 應(yīng)用網(wǎng)絡(luò)編碼的相交多路徑傳感器網(wǎng)絡(luò)模型

建立基于簇的相交多路徑路由模型［1］，網(wǎng)絡(luò)拓撲如圖2所示。網(wǎng)絡(luò)中節(jié)點分為N個簇，分別記為第1到N簇。其中每個簇里面包含的節(jié)點個數(shù)記為ni，其中i＝1，2，…，N，接收端在第N個簇中。

圖2 相交多經(jīng)路由網(wǎng)絡(luò)拓撲

應(yīng)用隨機線性編碼方案作為編碼方法，發(fā)送端把報文拆分成K個數(shù)據(jù)包，編碼后生成的數(shù)據(jù)包個數(shù)K′（K′≥K），假定被編碼成K′＝K＋2個數(shù)據(jù)包。ai，k表示第i個節(jié)點集合里的任意一個節(jié)點正確收到k個數(shù)據(jù)包的概率，其中1≤i≤N，0≤k≤K。對于第一簇中的節(jié)點，由于無線信道出錯事件是相互獨立的，于是其收到k個數(shù)據(jù)包的概率服從參數(shù)為K′和p的貝努利事件，故a1，k可以由式 （5）計算出來

由于中間節(jié)點會對收到的所有數(shù)據(jù)包重新進行編碼，并且對編碼后的數(shù)據(jù)包進行轉(zhuǎn)發(fā)，所以，在任意簇中的節(jié)點向下一簇廣播數(shù)據(jù)包時，數(shù)據(jù)包可能會有差錯。每個數(shù)據(jù)包出錯的事件是相互獨立的，記m為當(dāng)前節(jié)點將要向下一簇轉(zhuǎn)發(fā)的數(shù)據(jù)包個數(shù)，傳輸多個數(shù)據(jù)包時有k個數(shù)據(jù)包正確地被下一簇中的節(jié)點接收的概率服從貝努利分布，把第i個簇中的節(jié)點從1到ni編號，用bi，j，k表示第i個簇中的任意一個節(jié)點正確接收到來自上一個簇中第j個節(jié)點恰好k個數(shù)據(jù)包的概率。在本模型中，為了降低網(wǎng)絡(luò)冗余度，中間節(jié)點在轉(zhuǎn)發(fā)的過程中，對于同一組的不同的數(shù)據(jù)包，最多只轉(zhuǎn)發(fā)K個，于是對于i≥2，1≤j≤ni，1≤k≤K的情況，bi，j，k由式 （6）所示

這個模型中，并不區(qū)分每一簇中的任意兩個節(jié)點，所以對于第i個簇來說，它從第i－1個簇中的任意一個節(jié)點收到k個數(shù)據(jù)包的概率實際上是相同的。而當(dāng)i≥2時的ai，k便等于第i個簇中的任意節(jié)點從第i－1個簇中的每一個節(jié)點收到的數(shù)據(jù)包之總數(shù)為k的所有節(jié)點組合的概率之和。對于2≤i≤N，1≤j≤ni，0≤k≤K，ai，k由式 （7）所示

式 （5）與式 （7）計算了每一個節(jié)點正確收到數(shù)據(jù)包從0到K－1個的概率。只要編碼系數(shù)的有窮域容量足夠大，目的節(jié)點收到的數(shù)據(jù)包個數(shù)大于或者等于K，就可以解碼出原始數(shù)據(jù)包。因此成功交付率即目的節(jié)點收到的數(shù)據(jù)包個數(shù)大于或者等于K個的概率，由式 （8）計算

源節(jié)點發(fā)送了K′個數(shù)據(jù)包給第1個節(jié)點集，而從第2個節(jié)點集開始，每一簇的節(jié)點也是采用廣播的方式向下一簇節(jié)點傳遞數(shù)據(jù)包，并且每一個中間節(jié)點在正確收到K個或者多余K個數(shù)據(jù)包的情況下也僅僅是轉(zhuǎn)發(fā)K個數(shù)據(jù)包。于是，整個系統(tǒng)中所傳遞過的數(shù)據(jù)包總數(shù)可以通過累加得到，所以該系統(tǒng)的標(biāo)準(zhǔn)化冗余度由式 （9）表示

2 性能分析比較

為了更好地比較兩種模型性能，本文對圖1、圖2兩種模型拓撲進行了統(tǒng)一，因此，不相交多徑路由模型修改簡化為基于簇的模型，拓撲圖如圖3所示，模型每條路徑長度為N，路徑跳數(shù)為ni，且n1＝n2＝…＝ni。

圖3 簡化后的不相交多路徑網(wǎng)絡(luò)拓撲

2.1 使用網(wǎng)絡(luò)編碼前后性能分析

根據(jù)式 （2）、式 （4）、式 （8）、式 （9）可以得出圖4所示的使用網(wǎng)絡(luò)編碼前后性能比較圖，圖中分別給出不相交多徑路由模型和相交多徑路由模型的成功交付率與標(biāo)準(zhǔn)化冗余度隨誤碼率變化曲線。分析計算所使用的參數(shù)為：簇數(shù)5、每簇節(jié)點個數(shù)2、傳輸數(shù)據(jù)512個字節(jié)、每組數(shù)據(jù)包個數(shù)3。

圖4 使用網(wǎng)絡(luò)編碼前后性能比較

由圖4可以看出，對于不相交多徑路由，雖然使用網(wǎng)絡(luò)編碼會帶來一定的冗余，但是成功交付率的提升幅度更大，因此標(biāo)準(zhǔn)化冗余度比未使用網(wǎng)絡(luò)編碼模型有大幅度降低；而對于相交多徑路由，由于網(wǎng)絡(luò)成功交付率在使用了網(wǎng)絡(luò)編碼后提升幅度較小，不能抵掉數(shù)據(jù)冗余度增加的幅度，因此使用網(wǎng)絡(luò)編碼后標(biāo)準(zhǔn)化冗余度略微變大。

通過上面分析計算，可以發(fā)現(xiàn)，網(wǎng)絡(luò)編碼技術(shù)在多徑傳感器網(wǎng)絡(luò)中能獲得較好的效果，在保證系統(tǒng)冗余度偏低的同時提高了網(wǎng)絡(luò)了成功交付率。

2.2 兩種基于網(wǎng)絡(luò)編碼技術(shù)多路徑模型比較

在跳數(shù)分別為2、5、10、20、40、60時，兩種模型成功交付率如圖5所示，可以看出：基于網(wǎng)絡(luò)編碼的相交多徑路由 （NC－BMR）受簇數(shù)影響較小，當(dāng)跳數(shù)大于5時成功交付率基本不再發(fā)生變化；而基于網(wǎng)絡(luò)編碼的不相交多徑路由 （NC－DMR）模型隨跳數(shù)變化較大并且隨著跳數(shù)增加而降低；當(dāng)跳數(shù)較小時NC－DMR模型成功交付率要比NC－BMR絡(luò)模型高，隨著跳數(shù)增加，NC－DMR模型成功交付率逐漸下降，在跳數(shù)大于40后，成功交付率要比NCBMR模型低；跳數(shù)分別為10、20、40、60時，其變化基本與成功交付率一致。

當(dāng)層數(shù)為5，簇中節(jié)點個數(shù)分別為2、3、5、8時，計算分析結(jié)果如圖6所示，可以看出：隨著節(jié)點增多，兩種模型的成功交付率都隨之提高，且BMR模型提高的幅度要比NC－DMR模型大。當(dāng)節(jié)點較少時，相交網(wǎng)絡(luò)編碼模型成功交付率比不相交模型的低，隨著節(jié)點個數(shù)變多，相交網(wǎng)絡(luò)編碼模型成功交付率逐漸超過不相交網(wǎng)絡(luò)編碼模型。

由圖6可知，NC－BMR模型隨著簇中節(jié)點個數(shù)的增加成功交付率很穩(wěn)定，標(biāo)準(zhǔn)化冗余度逐漸變得穩(wěn)定，但是誤碼率較低的時候標(biāo)準(zhǔn)化冗余度隨著節(jié)點個數(shù)變大而變高，主要是因為節(jié)點增多后，路徑增多，冗余增加；而NC－DMR模型由于采用了分包傳輸，雖然路徑增多，但是每條路徑上傳輸?shù)臄?shù)據(jù)減少，因此標(biāo)準(zhǔn)化冗余度隨節(jié)點個數(shù)變化不大。

通過本節(jié)分析可以看出，兩種基于網(wǎng)絡(luò)編碼的多路徑傳感器網(wǎng)絡(luò)適用的網(wǎng)絡(luò)不同：NC－DMR模型適用于網(wǎng)絡(luò)規(guī)模較小的網(wǎng)絡(luò) （簇數(shù)較小，簇中的節(jié)點較少），而NC－BMR模型則適用于網(wǎng)絡(luò)規(guī)模較大的網(wǎng)絡(luò)，且對正確交付率和標(biāo)準(zhǔn)化冗余度的影響基本保持一致。

在實際應(yīng)用中，可以根據(jù)網(wǎng)絡(luò)規(guī)模來選擇不同的模型，使得網(wǎng)絡(luò)達到最優(yōu)。只把網(wǎng)絡(luò)的成功交付率作為選擇路由的評判標(biāo)準(zhǔn)，便可以計算兩種模型的正確交付率，選擇成功交付率高的路由模型來組建網(wǎng)絡(luò)。

3 仿真實驗

為了驗證理論分析的正確性，本文使用omnet＋＋仿真工具對使用網(wǎng)絡(luò)編碼后的不相交多路徑傳感器網(wǎng)絡(luò)模型和相交多路徑傳感器網(wǎng)絡(luò)模型進行了仿真實驗。為了跟理論分析計算結(jié)果進行比較，仿真參數(shù)與2.1節(jié)中的參數(shù)一致，仿真結(jié)果如圖7所示，從圖7可以看出，仿真實驗結(jié)果和理論計算結(jié)果基本吻合。在仿真的過程中數(shù)據(jù)包添加了數(shù)據(jù)包頭，因此性能比理論略為降低。

4 結(jié)束語

本文將網(wǎng)絡(luò)編碼應(yīng)用到傳感器網(wǎng)絡(luò)多徑路由中，通過在源節(jié)點和中繼節(jié)點使用隨機網(wǎng)絡(luò)編碼，在接收節(jié)點進行解碼，可以在部分報文丟失和順序變化的情況下恢復(fù)出源數(shù)據(jù)包，使網(wǎng)絡(luò)可靠性得到提高。通過仿真計算證明，使用網(wǎng)絡(luò)編碼后，多徑路由的成功交付率和標(biāo)準(zhǔn)化冗余度都得到了很好的改善，提高了傳感器網(wǎng)絡(luò)的整體性能。通過對兩種基于網(wǎng)絡(luò)編碼模型的性能比較，NC－DMR模型適用于網(wǎng)絡(luò)規(guī)模較小的網(wǎng)絡(luò)，而NC－BMR模型則適用于網(wǎng)絡(luò)規(guī)模較大的網(wǎng)絡(luò)。下一步工作計劃是在移動傳感器網(wǎng)絡(luò)中，結(jié)合動態(tài)網(wǎng)絡(luò)編碼對多徑路由協(xié)議進行更加深入的研究。

［1］Mahesh K，Marina，Samir R Das.Ad HoC on－demand multipath distance vector routing：research articles ［J］.Wireless Communications ＆ Mobile Computing，2006，6 （7）：969－988.

［2］Reddeppa Reddy L，Raghavan PS V.SMORT：Scalable multipath on－demand routing for mobile Ad HoC networks ［J］.Ad HoC Networks，2007，5 （2）：162－188.

［3］Ammar Zahary，Aladdin Ayesh.An analytical review for multipath routing in mobile Ad HoC networks ［J］.International Journal of Ad HoC and Ubiquitous Computing，2010，5 （2）：69－85.

［4］Eliana Stavrou，Andreas Pitsillides.A survey on secure multipath routing protocols in WSNs ［J］.Computer Networks the International Journal of Computer and Telecommunications Networking，2010，54 （13）：2215－2238.

［5］Mohammed Tarique，Kemal E Tepe，Sasan Adibi，et al.Review survey of multipath routing protocols for mobile Ad HoC networks ［J］.Journal of Network and Computer Applications，2009，32 （6）：1125－1143.

［6］WANG Chihchun.Pruning network coding traffic by network coding：a new class of max－flow algorithms ［J］.IEEE Transactions on Information Theory，2010，56 （4）：1909－1929.

［7］Parimal Parag，Chamberland Jean Francois.Queueing analysis of a butterfly network for comparing network coding to classical routing ［J］.IEEE Transactions on Information Theory，2010，56 （4）：1890－1908.

［8］Makesh Pravin Wilson，Krishna Narayanan，Henry D Pfister，et al.Joint physical layer coding and network coding for bidirectional relaying ［J］.IEEE Transactions on Information Theory，2010，56 （11）：5641－5654.

［9］Emina Soljanin，Piyush Gupta，Gerhard Kramer.Network coding for efficient network multicast ［J］.Bell Labs Technical Journal，2009，14 （3）：157－166.

［10］YANG Yuwang，ZHONG Chunshan，SUN Yamin，et al.Network coding based reliable disjoint and braided multipath routing for sensor networks ［J］.Journal of Network and Computer Applications，2010，33 （4）：422－432.

［11］GUO Zheng，WANG Bing，XIE Peng，et al.Efficient error recovery with network coding in underwater sensor networks［J］.Ad HoC Networks，2009，7 （4）：791－802.

［12］Fragouli C， Widmer J，LE Boudec J Y.Efficient broadcasting using network coding ［J］.IEEE／ACM Transactions on Networking，2008，16 （2）：450－463.

［13］YANG Yuwang，GU Li，JU Yutao，et al.Reliable braided multipath routing with network coding for underwater sensor networks［J］.China Ocean Engineering，2010，24 （3）：565－574.

［14］YU Jiming，LU Xianling，YANG Yuwang，et al.Overview of multipath routing protocols in wireless sensor networks［J］.Application Research of Computers，2007，24 （6）：1－3（in Chinese）.［于繼明，盧先領(lǐng)，楊余旺，等.無線傳感器網(wǎng)絡(luò)多路徑路由協(xié)議研究進展 ［J］.計算機應(yīng)用研究，2007，24 （6）：1－3.］

［15］LU Liping，HUANG Fei，ZHANG Hong，et al.Energy analysis of network coding based multipath routing model for sensor networks ［J］.Journal of Nanjing University of Science and Technology，2010，34 （4）：436－440 （in Chinese）.［盧莉萍，黃飛，張宏，等.基于網(wǎng)絡(luò)編碼的傳感器網(wǎng)絡(luò)多徑路由模型能量分析 ［J］.南京理工大學(xué)學(xué)報，2010，34 （4）：436－440.］