基于預(yù)測(cè)的機(jī)會(huì)式網(wǎng)絡(luò)編碼

劉外喜，余順爭(zhēng)，高鷹，胡曉

(1. 廣州大學(xué) 電子信息工程系，廣東 廣州 510006；2. 中山大學(xué) 電子通信工程系，廣東 廣州 510006)

1 引言

自2000年R Ahlswede、蔡寧等人提出網(wǎng)絡(luò)編碼[1,2]（network coding）的概念以來(lái)，網(wǎng)絡(luò)編碼就一直是一個(gè)研究熱點(diǎn)，并在實(shí)際中得到了應(yīng)用。引入網(wǎng)絡(luò)編碼最初是為了解決多播中的最大流最小割問(wèn)題，但隨著研究的進(jìn)一步深入，發(fā)現(xiàn)網(wǎng)絡(luò)編碼在提高網(wǎng)絡(luò)吞吐量，改善負(fù)載均衡，減小傳輸延遲，節(jié)省節(jié)點(diǎn)能耗，增強(qiáng)網(wǎng)絡(luò)頑健性等方面均顯示出優(yōu)勢(shì)，可廣泛應(yīng)用于ad hoc網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)、P2P[3]內(nèi)容分發(fā)和網(wǎng)絡(luò)安全[4]等領(lǐng)域，關(guān)于網(wǎng)絡(luò)編碼更多的信息可參考文獻(xiàn)[5]。毋庸置疑，網(wǎng)絡(luò)編碼展現(xiàn)了巧妙的思想和生機(jī)勃勃的應(yīng)用前景。

同時(shí)，網(wǎng)絡(luò)編碼也是一把雙刃劍，一直以來(lái)，人們都在強(qiáng)調(diào)網(wǎng)絡(luò)編碼的優(yōu)點(diǎn)，如提高吞吐量，傳輸可靠性，減少信息傳輸次數(shù)進(jìn)而降低能耗等，但是忽視了網(wǎng)絡(luò)節(jié)點(diǎn)為了實(shí)現(xiàn)這些優(yōu)點(diǎn)而付出的代價(jià)，如編碼帶來(lái)的時(shí)延、計(jì)算的復(fù)雜性，編碼本身帶來(lái)的能耗等。所以說(shuō)，并不是在任何時(shí)候、任何應(yīng)用場(chǎng)景中，網(wǎng)絡(luò)編碼都能夠調(diào)高吞吐量，尤其是當(dāng)編碼機(jī)制試圖貪心地利用一切編碼機(jī)會(huì)的時(shí)候，反而會(huì)降低性能[6]。所以，如何從系統(tǒng)論的觀點(diǎn)綜合考慮這些利弊，使系統(tǒng)整體最優(yōu)成為了一個(gè)新的研究熱點(diǎn)。機(jī)會(huì)式網(wǎng)絡(luò)編碼(ONC, opportunistic network coding)[7]的研究應(yīng)運(yùn)而生，ONC可以減少信息傳輸次數(shù)[7,8]，提高吞吐量[9]，能量利用效率[10]和傳輸可靠性[11]等，相關(guān)工作請(qǐng)見(jiàn)第2節(jié)。

本文提出了基于預(yù)測(cè)的機(jī)會(huì)式網(wǎng)絡(luò)編碼(ONCP,opportunistic network coding based on prediction)，它是在與現(xiàn)有工作不同的方向上利用不同的方法研究有關(guān)網(wǎng)絡(luò)編碼機(jī)會(huì)問(wèn)題的。ONCP的主要思想是：利用網(wǎng)絡(luò)流量的自相似性，預(yù)測(cè)下一個(gè)報(bào)文的到達(dá)時(shí)間，綜合計(jì)算編碼時(shí)間，為了編碼而等待的時(shí)間，傳輸時(shí)間等要素，從而判斷出編碼是否會(huì)提高系統(tǒng)的整體吞吐量，從而決定是否編碼。實(shí)驗(yàn)結(jié)果表明本文方法不僅可以提高系統(tǒng)的吞吐量，同時(shí)也可以降低網(wǎng)絡(luò)的能耗。

2 相關(guān)工作

Katti等人[7]提出了適用于無(wú)線網(wǎng)絡(luò)的實(shí)用化網(wǎng)絡(luò)編碼的架構(gòu)——COPE，其主要思想是：利用無(wú)線網(wǎng)絡(luò)中信道的廣播特性，各節(jié)點(diǎn)將其偷聽(tīng)到的所有信息存儲(chǔ)起來(lái)，并且節(jié)點(diǎn)之間互相交換各自存儲(chǔ)的信息；然后，節(jié)點(diǎn)分析自己和鄰居節(jié)點(diǎn)所掌握的信息情況以及鄰居節(jié)點(diǎn)的需求，尋找一個(gè)最佳的編碼方案，使鄰居節(jié)點(diǎn)都能獲得自己所需要的信息，以期獲得最大的系統(tǒng)吞吐量增益。可以看出，偷聽(tīng)到的信息是這種方法判斷編碼機(jī)會(huì)的基礎(chǔ)，所以不可靠，具有隨機(jī)的波動(dòng)性，并且編碼機(jī)會(huì)是被動(dòng)的,在其應(yīng)用過(guò)程中，如果所有路由節(jié)點(diǎn)都沒(méi)有編碼機(jī)會(huì)，那么網(wǎng)絡(luò)吞吐量將不會(huì)有任何的提高。針對(duì)COPE被動(dòng)的缺點(diǎn)，SENGUPTA S[12]、楊林等人[13]提出利用路由協(xié)議來(lái)主動(dòng)地尋找編碼機(jī)會(huì)。

在無(wú)線網(wǎng)絡(luò)環(huán)境下，在實(shí)現(xiàn)交互會(huì)話(inter-session)網(wǎng)絡(luò)編碼時(shí)，各個(gè)會(huì)話(session)之間的速度匹配與否決定了節(jié)點(diǎn)所能夠偷聽(tīng)到信息的數(shù)量，而偷聽(tīng)到的信息數(shù)量又決定了編碼機(jī)會(huì)的多少，而機(jī)會(huì)的多少又決定了系統(tǒng)吞吐量的增益大小。為此，Yuchul Kim[11]提出了利用速率自適應(yīng)的方法來(lái)提高Inter-session網(wǎng)絡(luò)編碼中的吞吐量增益，Tae-Suk Kim[14]、Raju Kumar等[15]也提出了類似的思想。這類思想為了實(shí)現(xiàn)速率匹配，有的時(shí)候需要降低局部節(jié)點(diǎn)的速率，這樣做顯然導(dǎo)致整個(gè)系統(tǒng)無(wú)法發(fā)揮最大的性能。文獻(xiàn)[16]試圖從系統(tǒng)論的觀點(diǎn)出發(fā)，在基于網(wǎng)絡(luò)編碼的無(wú)線網(wǎng)絡(luò)中找出時(shí)延、分組丟失率、能源消耗之間最佳的平衡點(diǎn)，實(shí)際上也就是找出最佳的編碼機(jī)會(huì)，使系統(tǒng)整體最優(yōu)。

從以上的分析可以看出，現(xiàn)有工作的一個(gè)共同點(diǎn)是基于無(wú)線網(wǎng)絡(luò)信道特有的廣播特性，各節(jié)點(diǎn)偷聽(tīng)到信息的多少?zèng)Q定了編碼機(jī)會(huì)的多少。鑒于有線、無(wú)線網(wǎng)絡(luò)信道的根本區(qū)別，這些方法不能夠很好地應(yīng)用于有線網(wǎng)絡(luò)，而本文討論的正是在有線網(wǎng)絡(luò)中如何利用流量的自相似性來(lái)發(fā)現(xiàn)編碼機(jī)會(huì)，并且也不需要調(diào)整速率，進(jìn)而可以最大可能地提高系統(tǒng)吞吐量。

另一個(gè)與本文相關(guān)的研究領(lǐng)域是網(wǎng)絡(luò)編碼的優(yōu)化問(wèn)題[17]，它是指在給定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上，對(duì)于某個(gè)優(yōu)化目標(biāo)，在保證所有節(jié)點(diǎn)達(dá)到理論多播速率的前提下，盡可能地降低網(wǎng)絡(luò)各種開(kāi)銷，目前研究最多的優(yōu)化目標(biāo)是：最小花費(fèi)多播，無(wú)向網(wǎng)絡(luò)的最大吞吐率，最小編碼節(jié)點(diǎn)、編碼邊，文獻(xiàn)[18]對(duì)此做了綜述。即使文獻(xiàn)[19]也考慮到了與本文比較接近的目標(biāo)——編碼開(kāi)銷——鏈路開(kāi)銷的聯(lián)合優(yōu)化，但該類問(wèn)題與本文關(guān)注的方向不一樣。網(wǎng)絡(luò)優(yōu)化問(wèn)題關(guān)注的是如何對(duì)既定的網(wǎng)絡(luò)尋找最佳的設(shè)計(jì)部署方案，實(shí)際上是一個(gè)事前的規(guī)劃問(wèn)題，由于計(jì)算時(shí)間較長(zhǎng)，需要離線進(jìn)行，并且當(dāng)被優(yōu)化的網(wǎng)絡(luò)在拓?fù)浣Y(jié)構(gòu)或節(jié)點(diǎn)、邊性能上變化時(shí)，都需要重新優(yōu)化，這是一個(gè)宏觀規(guī)劃的問(wèn)題。

而本文討論的是不針對(duì)任何特定拓?fù)涞?、?shí)時(shí)在線地發(fā)現(xiàn)最佳機(jī)會(huì)的編碼方案。由于實(shí)時(shí)、在線的需要導(dǎo)致每個(gè)節(jié)點(diǎn)無(wú)法都掌握全局信息，但本文通過(guò)促使每一個(gè)節(jié)點(diǎn)在微觀上都做出自己最優(yōu)的決定，來(lái)實(shí)現(xiàn)宏觀的整體最優(yōu)化。

3 基于預(yù)測(cè)的機(jī)會(huì)式網(wǎng)絡(luò)編碼

3.1 系統(tǒng)模型

圖1是經(jīng)典的網(wǎng)絡(luò)編碼的碟形，圖1(a)是同一個(gè)流內(nèi)部報(bào)文之間的編碼，圖1(b)是2個(gè)流之間報(bào)文的編碼。在圖1(a)中，S是信源，T1、T2是信宿，各個(gè)邊的帶寬均為1比特/單位時(shí)間。

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

現(xiàn)要將2bit數(shù)據(jù)x, y 同時(shí)從S傳到T1, T2。易知，S與T1 , T2之間都分別存在2條獨(dú)立路徑，若采用傳統(tǒng)路由方法，由于兩組路徑間存在共有鏈路3→4, x, y不能同時(shí)在鏈路3→4上傳輸，則S到T1、T2的最大信息流速率為1.5比特/單位時(shí)間；若采用網(wǎng)絡(luò)編碼方法，在節(jié)點(diǎn)3上對(duì)x, y執(zhí)行異或運(yùn)算后轉(zhuǎn)發(fā)，則節(jié)點(diǎn)T1可以通過(guò)計(jì)算x⊕x⊕y解出y，同理，T2也可以解出x , 從而使S到T1, T2的信息流速率達(dá)到2比特/單位時(shí)間，帶寬利用率提高33%。而在圖 1(b)中，S1需要將x發(fā)送到 T1、T2，S2需要將y發(fā)送到T1、T2，其他條件和圖1(a)的相同，如上分析，通過(guò)網(wǎng)絡(luò)編碼同樣可以實(shí)現(xiàn)帶寬利用率的提高。

但是，在以上的理論推導(dǎo)中，要實(shí)現(xiàn)預(yù)期的增益，隱含了一個(gè)前提假設(shè)，即假設(shè)全網(wǎng)是同步的，x，y會(huì)同時(shí)到達(dá)節(jié)點(diǎn)3，而在基于分組傳輸?shù)膶?shí)際互聯(lián)網(wǎng)中，由于鏈路的異構(gòu)性、網(wǎng)絡(luò)狀況的差異性，這一假設(shè)經(jīng)常不成立。也就是說(shuō)x，y不一定總是會(huì)同時(shí)到達(dá)節(jié)點(diǎn)3，x⊕y也會(huì)隨機(jī)地到達(dá)T1、T2節(jié)點(diǎn)，那么為了實(shí)現(xiàn)編碼，就需要x和y之間的互相等待；同樣，為了實(shí)現(xiàn)解碼，需要x和x⊕y，以及y和x⊕y之間的互相等待，而等待就產(chǎn)生了延遲和分組丟失，進(jìn)而降低系統(tǒng)吞吐量。同時(shí)，編碼也需要時(shí)間，節(jié)點(diǎn)3到節(jié)點(diǎn)4傳輸也需要時(shí)間，所以并不是任何時(shí)候的編碼都會(huì)節(jié)省時(shí)間。

那么，編碼時(shí)間、等待時(shí)間以及傳輸時(shí)間之間到底要滿足什么樣的條件編碼才有意義，即怎樣才會(huì)帶來(lái)吞吐量的提升？

3.2 基于流量自相似性的預(yù)測(cè)

3.2.1 網(wǎng)絡(luò)流量的自相似性和長(zhǎng)相關(guān)

自從文獻(xiàn)[20,21]發(fā)現(xiàn)局域網(wǎng)和廣域網(wǎng)中的流量具有自相似（self-similarity）的性質(zhì)以來(lái)，各種類型網(wǎng)絡(luò)中在各個(gè)網(wǎng)絡(luò)協(xié)議層次的流量都被研究發(fā)現(xiàn)有自相似性，現(xiàn)在人們已經(jīng)普遍認(rèn)為自相似性是分組網(wǎng)絡(luò)中流量的固有性質(zhì)[22]。

對(duì)于隨機(jī)過(guò)程X(t)，如果對(duì)于a＞0，t≥0，存在H值使得下式成立

dis則稱X(t)具有嚴(yán)格自相似性，這里的=表示有限維分布意義上相等，H是衡量自相似性程度的參數(shù)（即Hurst參數(shù)），H∈(0,1)，如果H＞0.5，說(shuō)明X(t)有自相似性，H值越大，自相似性越強(qiáng)。

這說(shuō)明：一個(gè)隨機(jī)過(guò)程{X(t),-∞＜t＜∞}在時(shí)間上進(jìn)行壓縮或擴(kuò)展時(shí)，其統(tǒng)計(jì)特性不變。自相似過(guò)程是在統(tǒng)計(jì)意義上具有尺度不變性的一類隨機(jī)過(guò)程，從這一點(diǎn)上來(lái)說(shuō)，自相似過(guò)程實(shí)際上是在隨機(jī)過(guò)程中引入了分形的概念。

長(zhǎng)相關(guān)（LRD, long range dependent）是自相似特性的一個(gè)明顯特征。設(shè)X(t)是連續(xù)隨機(jī)過(guò)程，R(t)是該隨機(jī)過(guò)程的相關(guān)函數(shù)，如果 ∫∞ R( t) =∞，則稱X(t)是長(zhǎng)相關(guān)過(guò)程。

也就是說(shuō)，X(t)的當(dāng)前值與它的所有歷史有關(guān)，或者更進(jìn)一步地講，利用當(dāng)前和過(guò)去的值可以預(yù)測(cè)未來(lái)值。

3.2.2 自相似網(wǎng)絡(luò)流量預(yù)測(cè)

網(wǎng)絡(luò)流量的預(yù)測(cè)對(duì)網(wǎng)絡(luò)的規(guī)劃設(shè)計(jì)、流量工程、QoS保證具有重要意義，預(yù)測(cè)也是本文的機(jī)會(huì)式網(wǎng)絡(luò)編碼的基礎(chǔ)，而正是因?yàn)榱髁烤哂凶韵嗨菩院烷L(zhǎng)相關(guān)性，使得預(yù)測(cè)成為了可能。

目前主要有以下方法進(jìn)行預(yù)測(cè)：①線性預(yù)測(cè)，最著名的應(yīng)當(dāng)是以自回歸AR模型、滑動(dòng)平均MA模型和 ARMA模型為代表的回歸類模型，還包括分?jǐn)?shù)自回歸滑動(dòng)平均（FARIMA）模型[23]等；②非線性預(yù)測(cè)，以神經(jīng)網(wǎng)絡(luò)(ANN)為代表的，具有不依賴先驗(yàn)知識(shí)或規(guī)則為前提的自適應(yīng)學(xué)習(xí)能力。

近年來(lái)，又提出了將具有自相似性的流量數(shù)據(jù)轉(zhuǎn)化為短相關(guān)數(shù)據(jù)，再利用短相關(guān)模型加以建模和預(yù)測(cè)的方法，這樣可以有效地減小計(jì)算復(fù)雜度。

出于對(duì)算法復(fù)雜度、計(jì)算開(kāi)銷、存儲(chǔ)開(kāi)銷、預(yù)測(cè)精度的綜合折中考慮，本文使用一種基于 EMD(empirical mode decomposition)[24]的 ARMA（自回歸滑動(dòng)平均）模型預(yù)測(cè)自相似網(wǎng)絡(luò)流量的方法[25]，其主要步驟如下。

1) 利用EMD方法將自相似網(wǎng)絡(luò)流量分解為若干個(gè)短相關(guān)序列——IMF (intrinsic mode functions，固有模式函數(shù)），從而將長(zhǎng)相關(guān)序列建模預(yù)測(cè)問(wèn)題轉(zhuǎn)化為對(duì)若干個(gè)短相關(guān)序列的建模和預(yù)測(cè)，可有效地降低模型的復(fù)雜度，減少計(jì)算開(kāi)銷。

2) 利用ARMA模型優(yōu)秀的短相關(guān)預(yù)測(cè)能力，對(duì)分解后的各個(gè)IMF序列進(jìn)行預(yù)測(cè)。

3) 將分別預(yù)測(cè)到的各 IMF序列進(jìn)行合成，就得到原始信號(hào)的預(yù)測(cè)信號(hào)。

本文基于EMD的ARMA的預(yù)測(cè)系統(tǒng)框如圖2所示，主體包括EMD分解和ARMA模型建立以及預(yù)測(cè)3個(gè)模塊。由于網(wǎng)絡(luò)流量的自相似性質(zhì)，將歷史數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)來(lái)確定 ARMA模型參數(shù)并不會(huì)影響參數(shù)的正確性，然后利用這一模型參數(shù)去幫助在線的實(shí)時(shí)預(yù)測(cè)?；ヂ?lián)網(wǎng)的原始數(shù)據(jù)經(jīng)過(guò)簡(jiǎn)單的預(yù)處理后進(jìn)入到EMD進(jìn)行IMF分量的分解，然后根據(jù)模型參數(shù)對(duì)各IMF進(jìn)行預(yù)測(cè)。同時(shí)，設(shè)立一個(gè)定時(shí)器（timer），定期地用實(shí)時(shí)數(shù)據(jù)更新訓(xùn)練數(shù)據(jù)，保持模型參數(shù)的時(shí)效性。

圖2 預(yù)測(cè)系統(tǒng)框圖

限于篇幅，這里只對(duì)其中起到關(guān)鍵作用的EMD做介紹。EMD算法假設(shè)任何信號(hào)都是由若干個(gè)IMF組成的，這些IMF需要滿足以下條件。

1) 整個(gè)信號(hào)上，極值點(diǎn)的個(gè)數(shù)和過(guò)零點(diǎn)的個(gè)數(shù)相差不大于1。

2) 在任意點(diǎn)處，上下包絡(luò)的均值為0。

每一個(gè)IMF可通過(guò)如圖3所示的算法得到，圖3中的SD＜Э，具體表示為式（2）。

經(jīng)過(guò) k次迭代后，式(2)判斷 hk(t)是否為 IMF分量的條件：hk(t)與前一次迭代結(jié)果 hk-1(t)之間的均方根差值如果小于某一預(yù)定數(shù)值，則可將hk(t)視為滿足條件的第i個(gè)IMF分量。Э值越小，最終得到的滿足式（2）的hk(t)越接近真實(shí)的IMF分量[25]，本文中，將此閾值設(shè)定為0.15。最終結(jié)束后，原始信號(hào)x(t)可由n個(gè)IMF分量和一個(gè)殘余量的和組成，可表示為：，其中，ci(t)是 IMF分量，rk+1(t)是殘余分量[26]。

3.3 基于預(yù)測(cè)的機(jī)會(huì)式網(wǎng)絡(luò)編碼的理論分析

經(jīng)過(guò)上文的分析發(fā)現(xiàn)，如果能夠預(yù)測(cè)下一個(gè)報(bào)文的到達(dá)，就可知道需要等待的時(shí)間，那么就判斷在什么情況下的編碼可以提高性能，下面以如圖1(b)所示的Inter-session網(wǎng)絡(luò)編碼的模型為例進(jìn)行理論分析，Intra-session網(wǎng)絡(luò)編碼也可以按照同樣思路分析，限于篇幅，在此不再贅述。

3.3.1 網(wǎng)絡(luò)編碼實(shí)現(xiàn)正增益的條件

x、y分別處于不同的session，設(shè)節(jié)點(diǎn)3的編碼時(shí)間為c (包括讀內(nèi)存、編碼的計(jì)算等因編碼而需額外增加的時(shí)間)，S1→3和 S2→3鏈路上2個(gè)session的報(bào)文在節(jié)點(diǎn)3互相等待的時(shí)間為w，關(guān)于w更加詳細(xì)的含義請(qǐng)見(jiàn)3.3.2節(jié)，節(jié)點(diǎn)3到節(jié)點(diǎn)4的傳輸時(shí)間為t。在節(jié)點(diǎn)3進(jìn)行ONCP的情況下，設(shè)報(bào)文從進(jìn)入節(jié)點(diǎn)3到進(jìn)入節(jié)點(diǎn)4的時(shí)間為T(mén)1；在節(jié)點(diǎn)3未編碼情況下，設(shè)報(bào)文從進(jìn)入節(jié)點(diǎn)3到進(jìn)入節(jié)點(diǎn)4的時(shí)間為T(mén)2。那么分析后可發(fā)現(xiàn)下式成立：

顯然，只有T1＜T2 的時(shí)候，編碼才能夠節(jié)省時(shí)間，同時(shí)帶來(lái)吞吐量正增益。設(shè)因編碼而節(jié)省的時(shí)間為A=T2-T1，那么

顯然，只有 A＞0，編碼才意義。由于 c、w、t都是正實(shí)數(shù)，很容易證明如下結(jié)論。

結(jié)論 1 在基于編碼的系統(tǒng)中，當(dāng) w＜t-c，并且等待時(shí)間為w，編碼才能夠帶來(lái)吞吐量的正增益，此時(shí)，節(jié)省的時(shí)間是

結(jié)論1實(shí)際上表明：編碼節(jié)點(diǎn)上報(bào)文互相等待最長(zhǎng)的時(shí)間是 t-c，超過(guò)這個(gè)上界等來(lái)的編碼對(duì)吞吐量不會(huì)改善反而會(huì)降低。

由于任何預(yù)測(cè)方法都有誤差，因此當(dāng)用理論推導(dǎo)出來(lái)的結(jié)論1來(lái)判斷是否編碼時(shí)，實(shí)際上并不能夠達(dá)到最優(yōu)。例如，假設(shè)預(yù)測(cè)值是 w＞t-c，而實(shí)際值 w’＜w，并滿足 w’＜t-c，那么此時(shí)將會(huì)帶來(lái)“錯(cuò)失編碼機(jī)會(huì)”的問(wèn)題；而另外一種情況是：假設(shè)預(yù)測(cè)值是 w＜t-c，而實(shí)際值 w’＞w，并且 w’＞t-c，那么此時(shí)如果等待w將會(huì)浪費(fèi)時(shí)間w而不會(huì)得到編碼機(jī)會(huì)，而如果等待w’則等到了編碼機(jī)會(huì)，但由于違背了結(jié)論1而致使系統(tǒng)的吞吐量下降，不管哪種情況都是“無(wú)效等待”，所以在實(shí)際設(shè)計(jì)中需要進(jìn)一步考慮預(yù)測(cè)誤差的存在。

圖3 EMD算法流程圖

在考慮了預(yù)測(cè)誤差的因素后，得到結(jié)論2。

結(jié)論2 在基于編碼的系統(tǒng)中，在第n次預(yù)測(cè)中，設(shè)報(bào)文之間互相等待時(shí)間的預(yù)測(cè)值為w，預(yù)測(cè)值和實(shí)際值之間的預(yù)測(cè)誤差為 v，那么只有當(dāng)w＜t-c-v，并且等待時(shí)間為 w-v，才會(huì)獲得吞吐量的正增益。

當(dāng)v=0，結(jié)論2等價(jià)于結(jié)論1，這進(jìn)一步說(shuō)明了結(jié)論2是結(jié)論1在實(shí)際系統(tǒng)中的推廣。通過(guò)結(jié)論2來(lái)判斷是否編碼，就可以避免如上所述由于結(jié)論1所帶來(lái)的“錯(cuò)失編碼機(jī)會(huì)”和“無(wú)效等待”問(wèn)題。

在本文中，第n次預(yù)測(cè)的誤差v是通過(guò)以下方法得到的：前n-1次預(yù)測(cè)值的標(biāo)準(zhǔn)誤差（記作nv）。通過(guò)這樣一種基于歷史數(shù)據(jù)的在線訓(xùn)練的計(jì)算方法可以提高v的精確度，進(jìn)而可以提高系統(tǒng)的性能，其計(jì)算公式如下

在式(6)中，wi表示第i次預(yù)測(cè)時(shí)報(bào)文之間互相等待時(shí)間的預(yù)測(cè)值，wi'表示第i次預(yù)測(cè)時(shí)報(bào)文之間互相等待時(shí)間的實(shí)際值。

結(jié)論2的證明如下。

設(shè)預(yù)測(cè)值為w，實(shí)際值為w’，t-c如前文所述，那么w與t-c、w與w’、w’與t-c這3對(duì)變量的關(guān)系可以有8種組合，如表1所示。表1中的case4和case6由于條件之間的互相矛盾導(dǎo)致不會(huì)出現(xiàn)。

同理，由case2可得到

同理，由case3可得到

那么由式（7）～式（9）可得到

同理，由case5可得到

同理，由case7可得到

當(dāng)?shù)却龝r(shí)間為0 (12)

同理，由case8可得到

那么由式（11）～式（13）可得到

那么由式（10）和式（12）可得到

因此，結(jié)論2得證。

3.3.2 報(bào)文之間互相等待的時(shí)間w的含義

如前文所述，w是判斷是否編碼的重要依據(jù)，而在不同的情況下它有不同的含義，下面說(shuō)明本文中w的含義。

表1 w、w' 和t-c的關(guān)系

圖4 報(bào)文到達(dá)過(guò)程的2種情況

第1種情況：理想情況，節(jié)點(diǎn)3沒(méi)有背景流量（即沒(méi)有其他的單播和多播流量），只有X序列和Y序列，并且不需要排隊(duì)。那么，w就是Xi和Yj之間到達(dá)過(guò)程中的等待時(shí)間，如圖4所示。

第2種情況：在實(shí)際網(wǎng)絡(luò)中，S1→3和S2→3鏈路上除了有X和Y序列的報(bào)文以外，還有很多的背景流量，并且節(jié)點(diǎn)3并不能保證對(duì)所有的session都可以線速轉(zhuǎn)發(fā)，因此節(jié)點(diǎn) 3需要為來(lái)自不同源而去往同一目的地的報(bào)文設(shè)置隊(duì)列。假設(shè)節(jié)點(diǎn)3為所有來(lái)自S1→3鏈路的報(bào)文設(shè)置隊(duì)列p13；為所有來(lái)自S2→3鏈路的報(bào)文設(shè)置隊(duì)列p23，那么，此時(shí)的p13中不僅包含X序列的報(bào)文，還有其他session的報(bào)文在排隊(duì)；p23也是同樣的情況。那么此時(shí)，w就不能夠僅僅是Xi和Yj之間到達(dá)過(guò)程中的等待時(shí)間，還需要考慮各自在隊(duì)列中的排隊(duì)時(shí)間，也就是說(shuō)w有了新的含義。

設(shè)Xi進(jìn)入到p13隊(duì)列，距離發(fā)送還需時(shí)間q1，而預(yù)測(cè)Yj還需要時(shí)間m才能夠到達(dá)，而假設(shè) Yj在p23隊(duì)列中的排隊(duì)時(shí)間是q2，w的含義就如下式所示

其中，q1、q2是節(jié)點(diǎn)3容易獲得的2個(gè)常量，本文利用3.2.2節(jié)的方法需要預(yù)測(cè)的僅僅是m的值。

從式(16)可以看出，當(dāng) q1＜q2+m時(shí)，Xi會(huì)先到達(dá)發(fā)送時(shí)刻，如果此時(shí)又滿足結(jié)論 2，即有編碼機(jī)會(huì)和價(jià)值，那么此時(shí) Xi就應(yīng)該等待，但應(yīng)該將 Xi放到隊(duì)列中的哪個(gè)位置來(lái)等待比較合適？如果此時(shí)再次將 Xi，放到原來(lái)的排隊(duì)隊(duì)列中，那么此時(shí)又會(huì)產(chǎn)生新的q1，隨后，那么又必將進(jìn)入到從式（16）開(kāi)始的如上所述的一系列判斷循環(huán)中；當(dāng)q1＜ q2+m時(shí)，也存在同樣問(wèn)題。

為了解決上述循環(huán)問(wèn)題，在本文中，為每一個(gè)會(huì)話增加一個(gè)專門(mén)的編碼緩存區(qū)，不管Xi或Yj哪一個(gè)先到達(dá)發(fā)送時(shí)刻，只要通過(guò)結(jié)論2判斷有編碼的價(jià)值，那么就轉(zhuǎn)移到各自的編碼緩存區(qū)中，進(jìn)一步等待編碼，因緩沖區(qū)中的內(nèi)容較少，所以不存在排隊(duì)的問(wèn)題，也就不存在上述的循環(huán)問(wèn)題，具體算法如圖5所示。

3.3.3 實(shí)現(xiàn)基于預(yù)測(cè)的機(jī)會(huì)式網(wǎng)絡(luò)編碼的算法

利用結(jié)論2來(lái)判斷是否編碼，節(jié)點(diǎn)3執(zhí)行的基于預(yù)測(cè)的機(jī)會(huì)式網(wǎng)絡(luò)編碼的算法主體如圖5所示，而利用結(jié)論1來(lái)判斷是否編碼的算法與此類似，限于篇幅，在此不再贅述。

圖5 基于預(yù)測(cè)的機(jī)會(huì)式編碼算法的主體

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

本文使用NS2[27]進(jìn)行仿真，拓?fù)淙鐖D1(b)所示，網(wǎng)絡(luò)環(huán)境為實(shí)際網(wǎng)絡(luò)（即節(jié)點(diǎn)3有背景流量，并設(shè)置了排隊(duì)隊(duì)列）。本文用NS2自帶的符合Pareto 分布的 trace流量模擬實(shí)際網(wǎng)絡(luò)中自相似流量。為了模擬實(shí)際網(wǎng)絡(luò)中全網(wǎng)不同步、鏈路的異構(gòu)性，在S1和 S2節(jié)點(diǎn)的 S1→3、S2→3鏈路上分別產(chǎn)生參數(shù)不一樣的Pareto流量使X、Y序列到達(dá)節(jié)點(diǎn)3時(shí)各個(gè)報(bào)文的到達(dá)時(shí)間不一致。通過(guò)改變Pareto分布的形狀（shape）參數(shù)來(lái)實(shí)現(xiàn)X、Y序列的不同到達(dá)過(guò)程，進(jìn)而來(lái)模擬網(wǎng)絡(luò)不同步的程度。

在仿真中，Pareto 分布 trace流量持續(xù)時(shí)間都是 60s，分組大小都是 500byte, 做完一次后改變Pareto分布的形狀（shape）參數(shù)，再重復(fù)。

在本文的仿真中，區(qū)分了4種不同的編碼策略：1) 不進(jìn)行網(wǎng)絡(luò)編碼，即傳統(tǒng)的存儲(chǔ)轉(zhuǎn)發(fā)，簡(jiǎn)稱(NNC,not network coding)；2) 總是網(wǎng)絡(luò)編碼，即在節(jié)點(diǎn)3，不管什么情況，先到的報(bào)文總是等待下一個(gè)報(bào)文進(jìn)行編碼，簡(jiǎn)稱 ANC（always network coding）；3) 基于預(yù)測(cè)的機(jī)會(huì)式網(wǎng)絡(luò)編碼，以結(jié)論1作為判斷依據(jù)，簡(jiǎn)稱 ONCP1；4) 基于預(yù)測(cè)的機(jī)會(huì)式網(wǎng)絡(luò)編碼，以結(jié)論2作為判斷依據(jù)，簡(jiǎn)稱ONCP2。

4.1 預(yù)測(cè)系統(tǒng)的性能

本節(jié)對(duì)如圖2所示的預(yù)測(cè)系統(tǒng)的性能進(jìn)行介紹，包括計(jì)算速度和預(yù)測(cè)精度等。本文對(duì)包含40 000個(gè)報(bào)文的實(shí)際數(shù)據(jù)序列進(jìn)行預(yù)測(cè)，式(2)中的Э=0.15。預(yù)測(cè)系統(tǒng)中各模塊的性能表現(xiàn)如表2所示，第2行是計(jì)算時(shí)間開(kāi)銷；如果設(shè)每個(gè)報(bào)文大小為1 500byte，第3行是根據(jù)計(jì)算時(shí)間轉(zhuǎn)換而來(lái)的計(jì)算速度。ARMA建模和預(yù)測(cè)模塊的速度都超過(guò)1 000Mbit/s，最慢的EMD也有47.041 8Mbit/s，即使將EMD分解和ARMA建模合并在一起計(jì)算，其速度也可達(dá)到45.163 7Mbit/s。

表2 預(yù)測(cè)系統(tǒng)的性能

表2數(shù)據(jù)是在2.8GHz的CPU（Intel Pentium 4）和2G內(nèi)存的PC機(jī)上測(cè)量得到的，實(shí)際上，利用路由器中的專門(mén)硬件，系統(tǒng)可以運(yùn)行的更快，完全可以實(shí)現(xiàn)在線地實(shí)時(shí)預(yù)測(cè)。

在本文中，用歸一化均方誤差NMSE來(lái)評(píng)判預(yù)測(cè)精度，NMSE定義如下

式(17)中的n表示網(wǎng)絡(luò)流量數(shù)據(jù)的個(gè)數(shù)，y?(i )表示第i個(gè)網(wǎng)絡(luò)流量數(shù)據(jù)的?預(yù)測(cè)值，y(i)表示第i個(gè)網(wǎng)絡(luò)流量數(shù)據(jù)的實(shí)際值， δ2是預(yù)測(cè)值的方差。

ARMA預(yù)測(cè)各IMF分量的NMSE結(jié)果如圖6所示?？梢钥吹?，各IMF的預(yù)測(cè)精度都比較高，并且隨著IMF階數(shù)的增加，預(yù)測(cè)精度以指數(shù)的速度提高。

從上文可以看到，整個(gè)預(yù)測(cè)系統(tǒng)可以滿足普通速率網(wǎng)絡(luò)在線實(shí)時(shí)預(yù)測(cè)的要求，但EMD模塊是阻礙預(yù)測(cè)系統(tǒng)運(yùn)行于高速骨干網(wǎng)的性能瓶頸，可以通過(guò)以下3種方法提高EMD的速度。

1) 減少I(mǎi)MF的數(shù)量，將多個(gè)IMF分量加在一起，作為一個(gè)整體進(jìn)行預(yù)測(cè)。由于隨著IMF階數(shù)的增加，IMF信號(hào)的隨機(jī)性、突發(fā)性逐漸減弱，IMF信號(hào)逐漸表現(xiàn)為類似正弦信號(hào)的震蕩模式，并且如圖6所示，隨著IMF階數(shù)的增加，預(yù)測(cè)精度以指數(shù)的速度提高，因此可以對(duì)IMF1以外的IMF進(jìn)行合并，即對(duì)信號(hào)可以只分解為2個(gè)IMF：IMF1和剩余IMF，剩余IMF放在一起預(yù)測(cè)[25]，實(shí)驗(yàn)證明這樣做也不會(huì)降低預(yù)測(cè)精度，NMSE可達(dá)到0.001 09，這樣減少了IMF個(gè)數(shù)，可提高效率。經(jīng)過(guò)改良后，EMD的速度提高到90.798Mbit/s。

圖6 ARMA預(yù)測(cè)各IMF分量的NMSE值

2) 增大式(2)中的Э，減少計(jì)算時(shí)間開(kāi)銷。Э值越小，最終滿足式(2)得到的 hk(t)越接近真實(shí)的IMF分量，那么預(yù)測(cè)精度就越高，那么滿足結(jié)論2并獲得性能正增益的概率也越大，但計(jì)算時(shí)間開(kāi)銷也越大。同時(shí)，實(shí)驗(yàn)也證明，預(yù)測(cè)精度對(duì)增大Э的敏感度比計(jì)算時(shí)間開(kāi)銷對(duì)增大Э的敏感度要小，限于篇幅，在此就不再贅述。所以在實(shí)際應(yīng)用中，可以綜合考慮計(jì)算時(shí)間開(kāi)銷與期望獲得的性能正增益來(lái)選擇Э的值，使預(yù)測(cè)系統(tǒng)整體上達(dá)到最優(yōu)。

3) 剝離出系統(tǒng)的一部分作為離線運(yùn)行，以減少系統(tǒng)的開(kāi)銷，圖2所示的虛線部分就可以離線運(yùn)行。相信依靠EMD算法的進(jìn)一步優(yōu)化以及硬件的加速作用，本文的系統(tǒng)完全可以滿足高速骨干網(wǎng)在線實(shí)時(shí)預(yù)測(cè)的要求。

4.2 ONCP對(duì)吞吐量的改善

吞吐量的仿真結(jié)果如圖 7所示，即 2個(gè)基于Pareto分布的流量的shape參數(shù)的比值，它反映了2個(gè)流量報(bào)文到達(dá)過(guò)程的差異程度，相對(duì)形狀參數(shù)越大，2個(gè)流的報(bào)文到達(dá)過(guò)程差異越大。關(guān)于ANC，從圖中觀察到以下現(xiàn)象。

1) ANC的吞吐量并不總是比NNC高，甚至在大多數(shù)的時(shí)候，ANC比NNC性能要差，這主要是由于每次因編碼而節(jié)省的時(shí)間并不總會(huì)大于等待所花費(fèi)的時(shí)間，即并不總是都會(huì)滿足結(jié)論 2，所以編碼次數(shù)越多性能越差。

2) 隨著相對(duì)形狀參數(shù)的增大，ANC的吞吐量總體呈下降趨勢(shì)，這主要是因?yàn)楫?dāng)2個(gè)流到達(dá)過(guò)程差異越大，系統(tǒng)需要將更多的時(shí)間花費(fèi)在報(bào)文的相互等待過(guò)程上面，所以 ANC的吞吐量會(huì)為此而降低，而ONCP1和ONCP2在報(bào)文到達(dá)過(guò)程差異程度不同的情況下都可以保持相對(duì)的平穩(wěn)。

3) ANC并不是一直呈直線下降的，在下降的過(guò)程中偶爾有一些改善的區(qū)間，這是因?yàn)樵谶@些區(qū)間，雖然相對(duì)形狀參數(shù)較大，但也并不排除2個(gè)流量中一些報(bào)文的到達(dá)時(shí)間比較接近的可能性，如果此時(shí)報(bào)文需要等待的時(shí)間滿足結(jié)論 1，那么就可以提高吞吐量，如果這種報(bào)文在流量中的比例很高，就會(huì)導(dǎo)致相對(duì)形狀參數(shù)大的時(shí)候比相對(duì)形狀參數(shù)小的時(shí)候的吞吐量還高。

4) ANC的波動(dòng)是最大的，這主要是因?yàn)椋寒?dāng)2個(gè)流量報(bào)文的到達(dá)時(shí)間比較接近的時(shí)候，ANC工作的較好，吞吐量改善明顯；而當(dāng)2個(gè)流量報(bào)文的到達(dá)時(shí)間相差較大的時(shí)候，ANC由于等待時(shí)間過(guò)長(zhǎng)而會(huì)明顯地降低吞吐量，因此急升急降導(dǎo)致波動(dòng)大。

在吞吐量的改善上，其中，ONCP1相對(duì)于ANC有4.01%～26.56%的提高；ONCP1相對(duì)于NNC大約有8.5%～12.38%的提高，ONCP1相對(duì)于NNC平均提高10%左右。

經(jīng)過(guò)算法改良后的ONCP2的性能進(jìn)一步提高，ONCP2的吞吐量總是高于ANC、NNC、ONCP1，并且波動(dòng)較小，ONCP2相對(duì)于 ANC大約有11.05%～32.26%的提高；ONCP2相對(duì)于NNC大約有14.82%～17.75%的提高，ONCP2相對(duì)于NNC平均提高15.89%左右；而ONCP2相對(duì)于ONCP1有了3.9%～7.07%的提高，平均改善5.55%左右。

4.3 ONCP對(duì)能量的節(jié)省

網(wǎng)絡(luò)編碼可以減少數(shù)據(jù)的發(fā)送次數(shù)，不僅實(shí)現(xiàn)了吞吐量的提高，也節(jié)省了能量，這種能量的節(jié)省對(duì)無(wú)線網(wǎng)絡(luò)、傳感網(wǎng)絡(luò)等節(jié)點(diǎn)能量受限的網(wǎng)絡(luò)顯得尤其重要。理論上來(lái)講，編碼的次數(shù)越多，那么發(fā)送數(shù)據(jù)的次數(shù)減少的越多，就意味著節(jié)省的能量越多。

如圖8所示，ONCP在取得較高吞吐量增益的前提下，能量的節(jié)省也不錯(cuò)。其中橫坐標(biāo)依然是相對(duì)形狀參數(shù)，縱坐標(biāo)是經(jīng)過(guò)ONCP編碼的報(bào)文占所有發(fā)送報(bào)文的比例，能夠相對(duì)地反映能量節(jié)省的程度，比例越高，節(jié)省的能量越多，ONCP1平均達(dá)到了 20.85%左右。這個(gè)數(shù)字看起來(lái)不大，沒(méi)有 ANC的100%那么高，但因?yàn)檫M(jìn)行ONCP1編碼的前提是滿足結(jié)論1，即可以提高吞吐量，所以這里的20.85%是指在提高吞吐量的基礎(chǔ)上帶來(lái)的能量節(jié)省，而ANC的能量節(jié)省卻是以犧牲吞吐量為代價(jià)的。

經(jīng)過(guò)改良后的ONCP2可以避免ONCP1帶來(lái)的“錯(cuò)失編碼機(jī)會(huì)”和“無(wú)效等待”問(wèn)題。如圖8所示，ONCP2編碼的比例平均達(dá)到了21.73%左右，相對(duì)于ONCP1有 4.22%的改善。此值小于5.55%(ONCP2相對(duì)于ONCP1在吞吐量上的改善平均值)，也就是說(shuō)編碼數(shù)量的提高和吞吐量的改善不是完全同步的，這主要是由于ONCP2不僅會(huì)因?yàn)楸苊狻板e(cuò)失編碼機(jī)會(huì)”而增加編碼次數(shù)，而且也會(huì)因?yàn)樾枰苊狻盁o(wú)效等待”而導(dǎo)致編碼機(jī)會(huì)的減少。

5 討論

圖7 幾種編碼方式的吞吐量

圖8 ONCP編碼次數(shù)的比例

在前文中討論了2種情況下w的含義，實(shí)際上還有一種情況需要討論，那就是在節(jié)點(diǎn)3沒(méi)有背景流，但由于S1→3和S2→3鏈路到達(dá)的報(bào)文較快，在節(jié)點(diǎn)3需要排隊(duì)，節(jié)點(diǎn)3分別為S1→3和S2→3鏈路的報(bào)文設(shè)置X隊(duì)列、Y隊(duì)列。在這種情況下，如果X隊(duì)列、Y隊(duì)列都為非空，那顯然，對(duì)于同時(shí)處于隊(duì)列中的任意 Xi和 Yj進(jìn)行網(wǎng)絡(luò)編碼都可以帶來(lái)正增益，并且，對(duì)同時(shí)處于X隊(duì)列和 Y隊(duì)列首部的 Xi和 Yj進(jìn)行網(wǎng)絡(luò)編碼帶來(lái)的正增益最大。

因此，需要討論是在一個(gè)隊(duì)列非空，另一個(gè)隊(duì)列是空時(shí)的情況。例如，設(shè)Y隊(duì)列是空的，X隊(duì)列是非空的，依次有Xi-n, Xi-n+1, …, Xi在其中排隊(duì)，Xi在隊(duì)列的尾部，在這種情況下，任何時(shí)候Y隊(duì)列有一個(gè)報(bào)文到達(dá)，都可以與X隊(duì)列頭部的報(bào)文進(jìn)行網(wǎng)絡(luò)編碼，以獲得最大的增益。所以，當(dāng)X隊(duì)列有多個(gè)報(bào)文排隊(duì)時(shí)，排在隊(duì)首的報(bào)文完全不用等待就可以立即發(fā)送，因?yàn)殛?duì)列中還有后續(xù)的報(bào)文可與即將到來(lái)的Yj報(bào)文進(jìn)行編碼。

因此，只有當(dāng)X隊(duì)列僅有一個(gè)報(bào)文Xi時(shí)，才需要考慮是否等待。設(shè)Xi已經(jīng)排隊(duì)等待了qi的時(shí)間，這時(shí)到達(dá)了X隊(duì)列的頭部，且Xi后面沒(méi)有其他報(bào)文在排隊(duì)；Y隊(duì)列下一個(gè)要到達(dá)的報(bào)文是Yj，且預(yù)測(cè) Yj還需要時(shí)間 m才能夠到達(dá)。如果qi+m+v＜t-c，則令Xi再等待m+v的時(shí)間；否則把Xi立即發(fā)送出去。如果在Xi等待期間，有一個(gè)新的報(bào)文Xi+1進(jìn)入X隊(duì)列排隊(duì)，這時(shí)應(yīng)該把Xi立即發(fā)送出去，然后讓Xi+1代替Xi等待剩余的時(shí)間，此時(shí)的w=qi+m。

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

理論網(wǎng)絡(luò)編碼在實(shí)際應(yīng)用過(guò)程中存在缺陷，同時(shí)，現(xiàn)有機(jī)會(huì)式網(wǎng)絡(luò)編碼必須完全依賴于無(wú)線信道的廣播特性進(jìn)行偷聽(tīng)；而網(wǎng)絡(luò)編碼的優(yōu)化問(wèn)題關(guān)注的是如何對(duì)既定的網(wǎng)絡(luò)尋找事前的最佳規(guī)劃設(shè)計(jì)、部署方案，本文克服以上方法的不足，提出基于預(yù)測(cè)的機(jī)會(huì)式網(wǎng)絡(luò)編碼，即預(yù)測(cè)未來(lái)，有機(jī)會(huì)就編碼，沒(méi)有機(jī)會(huì)就不編碼。

本文利用EMD將自相似的長(zhǎng)相關(guān)流量模型用相對(duì)簡(jiǎn)單的短相關(guān)模型來(lái)替代，然后再利用成熟的ARMA進(jìn)行預(yù)測(cè)，可有效地降低預(yù)測(cè)模型的復(fù)雜度，將預(yù)測(cè)的計(jì)算開(kāi)銷控制在合理的水平，實(shí)現(xiàn)了在線的實(shí)時(shí)預(yù)測(cè)。本文的方法既可以應(yīng)用于無(wú)線網(wǎng)絡(luò)也可應(yīng)用于有線網(wǎng)絡(luò)中的Inter-session網(wǎng)絡(luò)編碼，并且也不需要調(diào)節(jié)傳輸速率。

同時(shí)，本文證明了獲得吞吐量正增益可以等待的時(shí)間的理論上界。仿真實(shí)驗(yàn)顯示，如果以結(jié)論 2作為判斷條件，ONCP的吞吐量總是高于 ANC、NNC，ONCP相對(duì)于ANC有11.05%～32.26%的提高，ONCP相對(duì)于NNC提高14.82%～17.75%，平均提高15.89%左右。在提高吞吐量的基礎(chǔ)上，ONCP也可有效地降低能量消耗。

延續(xù)本文的思想，未來(lái)還有很多工作可以做。自互聯(lián)網(wǎng)被發(fā)明幾十年以來(lái)，網(wǎng)絡(luò)流量日益龐大，網(wǎng)絡(luò)應(yīng)用也呈現(xiàn)多樣化，網(wǎng)絡(luò)的主要應(yīng)用從最初的Web到現(xiàn)在的P2P，但網(wǎng)絡(luò)流量一直保持著自相似性[28]，甚至下一代的 IPv6網(wǎng)絡(luò)也依然展現(xiàn)了自相似性[29～31]。同時(shí)，本文是從研究Inter-session網(wǎng)絡(luò)編碼出發(fā)提出了 ONCP，但 Intra-session網(wǎng)絡(luò)編碼的等待問(wèn)題也類似，即使是目前在實(shí)際應(yīng)用中普遍采用的隨機(jī)線性網(wǎng)絡(luò)編碼方案也同樣存在等待問(wèn)題。所以，這一基于預(yù)測(cè)的思想有著廣泛的應(yīng)用場(chǎng)合，也可應(yīng)用于實(shí)際網(wǎng)絡(luò)和IPv6網(wǎng)絡(luò)，筆者在未來(lái)的工作中將驗(yàn)證這些設(shè)想。

[1] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J].IEEE Transactions on Information Theory, 2000, 46(4)∶ 1204-1216.

[2] LI S Y R, YEUNG R W, CAI N. Linear network coding[J]. IEEE Transactions on Information Theory, 2003, 49(2)∶ 371-381.

[3] CHU X, JIANG Y. Random linear network coding for peer-to-peer applications[J]. Network, IEEE, 2010, 24(4)∶ 35-39.

[4] 劉外喜，余順爭(zhēng)，蔡君. 安全的網(wǎng)絡(luò)編碼所面臨的挑戰(zhàn)和對(duì)策[J].計(jì)算機(jī)科學(xué), 2011, 38(6)∶ 20-27.LIU W X, YU S Z, CAI J. Secure network coding∶ challenges and solution[J]. Computer Science, 2011, 38(6)∶ 20-27.

[5] HO T, LUN D S. Network Coding∶ an Introduction[M]. Cambridge Univ Pr, 2008.

[6] CHAPORKAR P, PROUTIERE A. Adaptive network coding and scheduling for maximizing throughput in wireless networks[A]. Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking[C]. Montreal,QC,Canada, 2007. 135-146.

[7] KATTI S, RAHUL H, HU W, et al. XORs in the air∶ practical wireless network coding[J]. IEEE/ACM Transactions on Networking (TON),2008, 16(3)∶ 497-510.

[8] LE J, LUI J, CHIU D M. DCAR∶ Distributed coding-aware routing in wireless networks[J]. IEEE Transactions on Mobile Computing, 2010,9(4)∶596-608..

[9] YOMO H, POPOVSKI P. Opportunistic scheduling for wireless network coding[A]. Proceedings of IEEE International Conference on Communications (ICC'07)[C]. Glasgow, Scotland, 2007. 5610-5615.

[10] CUI T, CHEN L, HO T. Energy efficient opportunistic network coding for wireless networks[A]. Proceedings of the 27th Conference on Computer Communications[C]. Phoenix, AZ, USA, 2008. 361-365.

[11] KIM Y, DE VECIANA G. Is rate adaptation beneficial for inter-session network coding[J]. IEEE Journal on Selected Areas in Communications, 2009, 27(5)∶635-646.

[12] SENGUPTA S, RAYANCHU S, BANERJEE S. An analysis of wireless network coding for unicast sessions∶ the case for coding-aware routing[A]. Proceedings of 26th IEEE International Conference on Computer Communications. IEEE (INFOCOM 2007)[C]. Anchorage,Alaska, USA, 2007. 1028-1036.

[13] 楊林，鄭剛. 無(wú)線多跳網(wǎng)中具有網(wǎng)絡(luò)編碼意識(shí)的機(jī)會(huì)路由協(xié)議[J].清華大學(xué)學(xué)報(bào)∶ 自然科學(xué)版, 2011(10)∶ 1713-1717.YANG L, ZHENG G. Network coding aware opportunistic routing protocol in wireless multihop networks[J]. J Tsing hua Univ ( Sci &Tech), 2010，50(10)∶1713-1717.

[14] KIM T S, VURAL S, BROUSTIS I, et al. A framework for joint network coding and transmission rate control in wireless networks[A].Proceedings of The 29th Conference on Computer Communications.IEEE (INFOCOM 2010)[C]. San Diego, CA, USA, 2010. 1-9.

[15] KUMAR R, TATI S, DE MELLO F, et al. Network coding aware rate selection in multi-rate IEEE 802.11[A]. Proceedings of 18th IEEE International Conference on Network Protocols (ICNP 2010)[C]. Kyoto,Japan, 2010. 92-102.

[16] CHEN W, LETAIEF K B, CAO Z. Opportunistic network coding for wireless networks[A]. Proceedings of IEEE International Conference on Communications (ICC'07)[C]. Glasgow, Scotland, 2007. 4634-4639.

[17] Kim M, Médard M, O'Reilly U M, et al. An evolutionary approach to inter-session network coding[A]. Proceedings of The 28th Conference on Computer Communications. IEEE (INFOCOM 2009)[C]. Rio de Janeiro, Brazil,2009. 450-458.

[18] 黃政，王新. 網(wǎng)絡(luò)編碼中的優(yōu)化問(wèn)題研究[J]. 軟件學(xué)報(bào). 2009, 20(5)∶1349-1361.HUANG Z, WANG X. Research on the optimization problems in network coding[J]. Journal of Software, 2009,20(5)∶1349-1361.

[19] 鄧亮, 趙進(jìn), 王新. 網(wǎng)絡(luò)編碼下的編碼開(kāi)銷-鏈路開(kāi)銷聯(lián)合優(yōu)化[J].計(jì)算機(jī)研究與發(fā)展, 2010, 47(3)∶ 390-397.DENG L, ZHAO J, et al. On the joint optimization of coding cost and link cost with network coding[J]. Journal of Computer Research and Development, 2010, 47(3)∶390-397.

[20] LELAND W E, TAQQU M S, WILLINGER W, et al. On the self-similar nature of Ethernet traffic (extended version)[J].IEEE/ACM Transactions on Networking, 1994, 2(1)∶ 1-15.

[21] PAXSON V, FLOYD S. Wide area traffic∶ the failure of Poisson modeling[J]. IEEE/ACM Transactions on Networking(ToN), 1995,3(3)∶ 226-244.

[22] ABRY P, BORGNAT P, RICCIATO F, et al. Revisiting an old friend∶on the observability of the relation between long range dependence and heavy tail[J]. Telecommunication Systems. 2010, 43(3)∶ 147-165.

[23] LIU J, SHU Y, ZHANG L, et al. Traffic modeling based on FARIMA models[A]. Proceedings of the 1999 IEEE Canadian Conference on Electrical and Computer Engineering[C]. 1999. 162-167.

[24] HUANG N E, SHEN Z, LONG S R, et al. The empirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary time series analysis[J]. Proceedings of the Royal Society of London.Series A∶ Mathematical, Physical and Engineering Sciences, 1998,454(1971)∶ 903-995.

[25] 高波, 張欽宇, 梁永生等. 基于 EMD 及 ARMA 的自相似網(wǎng)絡(luò)流量預(yù)測(cè)[J]. 通信學(xué)報(bào), 2011, 32(4)∶47-56.GAO B, ZHANG Q Y, LZANG Y S, et al. Predicting self-similar networking traffic based on EMD and ARMA[J]. Journal on Communications, 2011,32(4)∶47-56.

[26] 王婷. EMD 算法研究及其在信號(hào)去噪中的應(yīng)用[D]. 哈爾濱∶ 哈爾濱工業(yè)大學(xué)2010.WANG T. Research on EMD Algorithm and Its Application in Signal denoising[D]. Harbin∶ Harbin Engineering University, 2010.

[27] http∶//www.isi.edu/nsnam/ns/ [EB/OL].

[28] BORGNAT P, DEWAELE G, FUKUDA K, et al. Seven years and one day∶ sketching the evolution of internet traffic[A]. Proceedings of The 28th Conference on Computer Communications. IEEE (INFOCOM 2009)[C]. Rio de Janeiro, Brazil, 2009. 711-719.

[29] LIU W, YAN Y. Self-similarity and heavy-tail of ICMP traffic[J].Journal of Computers. 2012, 7(12)∶2948-2954.

[30] PEZAROS D P, SIFALAKIS M, HUTCHISON D. On the long-range dependent behaviour of unidirectional packet delay of wireless traffic[A]. Global Telecommunications Conference(GLOBECOM'07).IEEE[C]. Washington, DC, USA, 2007. 2655-2660.

[31] FLANDRIN P. Wavelet analysis and synthesis of fractional Brownian motion[J]. IEEE Transactions on Information Theory, 1992, 38(2)∶910-917.