基于預測的機會式網絡編碼

劉外喜，余順爭，高鷹，胡曉

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

1 引言

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

同時，網絡編碼也是一把雙刃劍，一直以來，人們都在強調網絡編碼的優點，如提高吞吐量，傳輸可靠性，減少信息傳輸次數進而降低能耗等，但是忽視了網絡節點為了實現這些優點而付出的代價，如編碼帶來的時延、計算的復雜性，編碼本身帶來的能耗等。所以說，并不是在任何時候、任何應用場景中，網絡編碼都能夠調高吞吐量，尤其是當編碼機制試圖貪心地利用一切編碼機會的時候，反而會降低性能[6]。所以，如何從系統論的觀點綜合考慮這些利弊，使系統整體最優成為了一個新的研究熱點。機會式網絡編碼(ONC, opportunistic network coding)[7]的研究應運而生，ONC可以減少信息傳輸次數[7,8]，提高吞吐量[9]，能量利用效率[10]和傳輸可靠性[11]等，相關工作請見第2節。

本文提出了基于預測的機會式網絡編碼(ONCP,opportunistic network coding based on prediction)，它是在與現有工作不同的方向上利用不同的方法研究有關網絡編碼機會問題的。ONCP的主要思想是：利用網絡流量的自相似性，預測下一個報文的到達時間，綜合計算編碼時間，為了編碼而等待的時間，傳輸時間等要素，從而判斷出編碼是否會提高系統的整體吞吐量，從而決定是否編碼。實驗結果表明本文方法不僅可以提高系統的吞吐量，同時也可以降低網絡的能耗。

2 相關工作

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

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

從以上的分析可以看出，現有工作的一個共同點是基于無線網絡信道特有的廣播特性，各節點偷聽到信息的多少決定了編碼機會的多少。鑒于有線、無線網絡信道的根本區別，這些方法不能夠很好地應用于有線網絡，而本文討論的正是在有線網絡中如何利用流量的自相似性來發現編碼機會，并且也不需要調整速率，進而可以最大可能地提高系統吞吐量。

另一個與本文相關的研究領域是網絡編碼的優化問題[17]，它是指在給定的網絡拓撲結構上，對于某個優化目標，在保證所有節點達到理論多播速率的前提下，盡可能地降低網絡各種開銷，目前研究最多的優化目標是：最小花費多播，無向網絡的最大吞吐率，最小編碼節點、編碼邊，文獻[18]對此做了綜述。即使文獻[19]也考慮到了與本文比較接近的目標——編碼開銷——鏈路開銷的聯合優化，但該類問題與本文關注的方向不一樣。網絡優化問題關注的是如何對既定的網絡尋找最佳的設計部署方案，實際上是一個事前的規劃問題，由于計算時間較長，需要離線進行，并且當被優化的網絡在拓撲結構或節點、邊性能上變化時，都需要重新優化，這是一個宏觀規劃的問題。

而本文討論的是不針對任何特定拓撲的、實時在線地發現最佳機會的編碼方案。由于實時、在線的需要導致每個節點無法都掌握全局信息，但本文通過促使每一個節點在微觀上都做出自己最優的決定，來實現宏觀的整體最優化。

3 基于預測的機會式網絡編碼

3.1 系統模型

圖1是經典的網絡編碼的碟形，圖1(a)是同一個流內部報文之間的編碼，圖1(b)是2個流之間報文的編碼。在圖1(a)中，S是信源，T1、T2是信宿，各個邊的帶寬均為1比特/單位時間。

圖1 網絡編碼模型

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

但是，在以上的理論推導中，要實現預期的增益，隱含了一個前提假設，即假設全網是同步的，x，y會同時到達節點3，而在基于分組傳輸的實際互聯網中，由于鏈路的異構性、網絡狀況的差異性，這一假設經常不成立。也就是說x，y不一定總是會同時到達節點3，x⊕y也會隨機地到達T1、T2節點，那么為了實現編碼，就需要x和y之間的互相等待；同樣，為了實現解碼，需要x和x⊕y，以及y和x⊕y之間的互相等待，而等待就產生了延遲和分組丟失，進而降低系統吞吐量。同時，編碼也需要時間，節點3到節點4傳輸也需要時間，所以并不是任何時候的編碼都會節省時間。

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

3.2 基于流量自相似性的預測

3.2.1 網絡流量的自相似性和長相關

自從文獻[20,21]發現局域網和廣域網中的流量具有自相似（self-similarity）的性質以來，各種類型網絡中在各個網絡協議層次的流量都被研究發現有自相似性，現在人們已經普遍認為自相似性是分組網絡中流量的固有性質[22]。

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

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

這說明：一個隨機過程{X(t),-∞＜t＜∞}在時間上進行壓縮或擴展時，其統計特性不變。自相似過程是在統計意義上具有尺度不變性的一類隨機過程，從這一點上來說，自相似過程實際上是在隨機過程中引入了分形的概念。

長相關（LRD, long range dependent）是自相似特性的一個明顯特征。設X(t)是連續隨機過程，R(t)是該隨機過程的相關函數，如果 ∫∞ R( t) =∞，則稱X(t)是長相關過程。

也就是說，X(t)的當前值與它的所有歷史有關，或者更進一步地講，利用當前和過去的值可以預測未來值。

3.2.2 自相似網絡流量預測

網絡流量的預測對網絡的規劃設計、流量工程、QoS保證具有重要意義，預測也是本文的機會式網絡編碼的基礎，而正是因為流量具有自相似性和長相關性，使得預測成為了可能。

目前主要有以下方法進行預測：①線性預測，最著名的應當是以自回歸AR模型、滑動平均MA模型和 ARMA模型為代表的回歸類模型，還包括分數自回歸滑動平均（FARIMA）模型[23]等；②非線性預測，以神經網絡(ANN)為代表的，具有不依賴先驗知識或規則為前提的自適應學習能力。

近年來，又提出了將具有自相似性的流量數據轉化為短相關數據，再利用短相關模型加以建模和預測的方法，這樣可以有效地減小計算復雜度。

出于對算法復雜度、計算開銷、存儲開銷、預測精度的綜合折中考慮，本文使用一種基于 EMD(empirical mode decomposition)[24]的 ARMA（自回歸滑動平均）模型預測自相似網絡流量的方法[25]，其主要步驟如下。

1) 利用EMD方法將自相似網絡流量分解為若干個短相關序列——IMF (intrinsic mode functions，固有模式函數），從而將長相關序列建模預測問題轉化為對若干個短相關序列的建模和預測，可有效地降低模型的復雜度，減少計算開銷。

2) 利用ARMA模型優秀的短相關預測能力，對分解后的各個IMF序列進行預測。

3) 將分別預測到的各 IMF序列進行合成，就得到原始信號的預測信號。

本文基于EMD的ARMA的預測系統框如圖2所示，主體包括EMD分解和ARMA模型建立以及預測3個模塊。由于網絡流量的自相似性質，將歷史數據作為訓練數據來確定 ARMA模型參數并不會影響參數的正確性，然后利用這一模型參數去幫助在線的實時預測。互聯網的原始數據經過簡單的預處理后進入到EMD進行IMF分量的分解，然后根據模型參數對各IMF進行預測。同時，設立一個定時器（timer），定期地用實時數據更新訓練數據，保持模型參數的時效性。

圖2 預測系統框圖

限于篇幅，這里只對其中起到關鍵作用的EMD做介紹。EMD算法假設任何信號都是由若干個IMF組成的，這些IMF需要滿足以下條件。

1) 整個信號上，極值點的個數和過零點的個數相差不大于1。

2) 在任意點處，上下包絡的均值為0。

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

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

3.3 基于預測的機會式網絡編碼的理論分析

經過上文的分析發現，如果能夠預測下一個報文的到達，就可知道需要等待的時間，那么就判斷在什么情況下的編碼可以提高性能，下面以如圖1(b)所示的Inter-session網絡編碼的模型為例進行理論分析，Intra-session網絡編碼也可以按照同樣思路分析，限于篇幅，在此不再贅述。

3.3.1 網絡編碼實現正增益的條件

x、y分別處于不同的session，設節點3的編碼時間為c (包括讀內存、編碼的計算等因編碼而需額外增加的時間)，S1→3和 S2→3鏈路上2個session的報文在節點3互相等待的時間為w，關于w更加詳細的含義請見3.3.2節，節點3到節點4的傳輸時間為t。在節點3進行ONCP的情況下，設報文從進入節點3到進入節點4的時間為T1；在節點3未編碼情況下，設報文從進入節點3到進入節點4的時間為T2。那么分析后可發現下式成立：

顯然，只有T1＜T2 的時候，編碼才能夠節省時間，同時帶來吞吐量正增益。設因編碼而節省的時間為A=T2-T1，那么

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

結論 1 在基于編碼的系統中，當 w＜t-c，并且等待時間為w，編碼才能夠帶來吞吐量的正增益，此時，節省的時間是

結論1實際上表明：編碼節點上報文互相等待最長的時間是 t-c，超過這個上界等來的編碼對吞吐量不會改善反而會降低。

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

圖3 EMD算法流程圖

在考慮了預測誤差的因素后，得到結論2。

結論2 在基于編碼的系統中，在第n次預測中，設報文之間互相等待時間的預測值為w，預測值和實際值之間的預測誤差為 v，那么只有當w＜t-c-v，并且等待時間為 w-v，才會獲得吞吐量的正增益。

當v=0，結論2等價于結論1，這進一步說明了結論2是結論1在實際系統中的推廣。通過結論2來判斷是否編碼，就可以避免如上所述由于結論1所帶來的“錯失編碼機會”和“無效等待”問題。

在本文中，第n次預測的誤差v是通過以下方法得到的：前n-1次預測值的標準誤差（記作nv）。通過這樣一種基于歷史數據的在線訓練的計算方法可以提高v的精確度，進而可以提高系統的性能，其計算公式如下

在式(6)中，wi表示第i次預測時報文之間互相等待時間的預測值，wi'表示第i次預測時報文之間互相等待時間的實際值。

結論2的證明如下。

設預測值為w，實際值為w’，t-c如前文所述，那么w與t-c、w與w’、w’與t-c這3對變量的關系可以有8種組合，如表1所示。表1中的case4和case6由于條件之間的互相矛盾導致不會出現。

同理，由case2可得到

同理，由case3可得到

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

同理，由case5可得到

同理，由case7可得到

當等待時間為0 (12)

同理，由case8可得到

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

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

因此，結論2得證。

3.3.2 報文之間互相等待的時間w的含義

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

表1 w、w' 和t-c的關系

圖4 報文到達過程的2種情況

第1種情況：理想情況，節點3沒有背景流量（即沒有其他的單播和多播流量），只有X序列和Y序列，并且不需要排隊。那么，w就是Xi和Yj之間到達過程中的等待時間，如圖4所示。

第2種情況：在實際網絡中，S1→3和S2→3鏈路上除了有X和Y序列的報文以外，還有很多的背景流量，并且節點3并不能保證對所有的session都可以線速轉發，因此節點 3需要為來自不同源而去往同一目的地的報文設置隊列。假設節點3為所有來自S1→3鏈路的報文設置隊列p13；為所有來自S2→3鏈路的報文設置隊列p23，那么，此時的p13中不僅包含X序列的報文，還有其他session的報文在排隊；p23也是同樣的情況。那么此時，w就不能夠僅僅是Xi和Yj之間到達過程中的等待時間，還需要考慮各自在隊列中的排隊時間，也就是說w有了新的含義。

設Xi進入到p13隊列，距離發送還需時間q1，而預測Yj還需要時間m才能夠到達，而假設 Yj在p23隊列中的排隊時間是q2，w的含義就如下式所示

其中，q1、q2是節點3容易獲得的2個常量，本文利用3.2.2節的方法需要預測的僅僅是m的值。

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

為了解決上述循環問題，在本文中，為每一個會話增加一個專門的編碼緩存區，不管Xi或Yj哪一個先到達發送時刻，只要通過結論2判斷有編碼的價值，那么就轉移到各自的編碼緩存區中，進一步等待編碼，因緩沖區中的內容較少，所以不存在排隊的問題，也就不存在上述的循環問題，具體算法如圖5所示。

3.3.3 實現基于預測的機會式網絡編碼的算法

利用結論2來判斷是否編碼，節點3執行的基于預測的機會式網絡編碼的算法主體如圖5所示，而利用結論1來判斷是否編碼的算法與此類似，限于篇幅，在此不再贅述。

圖5 基于預測的機會式編碼算法的主體

4 仿真實驗分析

本文使用NS2[27]進行仿真，拓撲如圖1(b)所示，網絡環境為實際網絡（即節點3有背景流量，并設置了排隊隊列）。本文用NS2自帶的符合Pareto 分布的 trace流量模擬實際網絡中自相似流量。為了模擬實際網絡中全網不同步、鏈路的異構性，在S1和 S2節點的 S1→3、S2→3鏈路上分別產生參數不一樣的Pareto流量使X、Y序列到達節點3時各個報文的到達時間不一致。通過改變Pareto分布的形狀（shape）參數來實現X、Y序列的不同到達過程，進而來模擬網絡不同步的程度。

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

在本文的仿真中，區分了4種不同的編碼策略：1) 不進行網絡編碼，即傳統的存儲轉發，簡稱(NNC,not network coding)；2) 總是網絡編碼，即在節點3，不管什么情況，先到的報文總是等待下一個報文進行編碼，簡稱 ANC（always network coding）；3) 基于預測的機會式網絡編碼，以結論1作為判斷依據，簡稱 ONCP1；4) 基于預測的機會式網絡編碼，以結論2作為判斷依據，簡稱ONCP2。

4.1 預測系統的性能

本節對如圖2所示的預測系統的性能進行介紹，包括計算速度和預測精度等。本文對包含40 000個報文的實際數據序列進行預測，式(2)中的Э=0.15。預測系統中各模塊的性能表現如表2所示，第2行是計算時間開銷；如果設每個報文大小為1 500byte，第3行是根據計算時間轉換而來的計算速度。ARMA建模和預測模塊的速度都超過1 000Mbit/s，最慢的EMD也有47.041 8Mbit/s，即使將EMD分解和ARMA建模合并在一起計算，其速度也可達到45.163 7Mbit/s。

表2 預測系統的性能

表2數據是在2.8GHz的CPU（Intel Pentium 4）和2G內存的PC機上測量得到的，實際上，利用路由器中的專門硬件，系統可以運行的更快，完全可以實現在線地實時預測。

在本文中，用歸一化均方誤差NMSE來評判預測精度，NMSE定義如下

式(17)中的n表示網絡流量數據的個數，y?(i )表示第i個網絡流量數據的?預測值，y(i)表示第i個網絡流量數據的實際值， δ2是預測值的方差。

ARMA預測各IMF分量的NMSE結果如圖6所示。可以看到，各IMF的預測精度都比較高，并且隨著IMF階數的增加，預測精度以指數的速度提高。

從上文可以看到，整個預測系統可以滿足普通速率網絡在線實時預測的要求，但EMD模塊是阻礙預測系統運行于高速骨干網的性能瓶頸，可以通過以下3種方法提高EMD的速度。

1) 減少IMF的數量，將多個IMF分量加在一起，作為一個整體進行預測。由于隨著IMF階數的增加，IMF信號的隨機性、突發性逐漸減弱，IMF信號逐漸表現為類似正弦信號的震蕩模式，并且如圖6所示，隨著IMF階數的增加，預測精度以指數的速度提高，因此可以對IMF1以外的IMF進行合并，即對信號可以只分解為2個IMF：IMF1和剩余IMF，剩余IMF放在一起預測[25]，實驗證明這樣做也不會降低預測精度，NMSE可達到0.001 09，這樣減少了IMF個數，可提高效率。經過改良后，EMD的速度提高到90.798Mbit/s。

圖6 ARMA預測各IMF分量的NMSE值

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

3) 剝離出系統的一部分作為離線運行，以減少系統的開銷，圖2所示的虛線部分就可以離線運行。相信依靠EMD算法的進一步優化以及硬件的加速作用，本文的系統完全可以滿足高速骨干網在線實時預測的要求。

4.2 ONCP對吞吐量的改善

吞吐量的仿真結果如圖 7所示，即 2個基于Pareto分布的流量的shape參數的比值，它反映了2個流量報文到達過程的差異程度，相對形狀參數越大，2個流的報文到達過程差異越大。關于ANC，從圖中觀察到以下現象。

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

2) 隨著相對形狀參數的增大，ANC的吞吐量總體呈下降趨勢，這主要是因為當2個流到達過程差異越大，系統需要將更多的時間花費在報文的相互等待過程上面，所以 ANC的吞吐量會為此而降低，而ONCP1和ONCP2在報文到達過程差異程度不同的情況下都可以保持相對的平穩。

3) ANC并不是一直呈直線下降的，在下降的過程中偶爾有一些改善的區間，這是因為在這些區間，雖然相對形狀參數較大，但也并不排除2個流量中一些報文的到達時間比較接近的可能性，如果此時報文需要等待的時間滿足結論 1，那么就可以提高吞吐量，如果這種報文在流量中的比例很高，就會導致相對形狀參數大的時候比相對形狀參數小的時候的吞吐量還高。

4) ANC的波動是最大的，這主要是因為：當2個流量報文的到達時間比較接近的時候，ANC工作的較好，吞吐量改善明顯；而當2個流量報文的到達時間相差較大的時候，ANC由于等待時間過長而會明顯地降低吞吐量，因此急升急降導致波動大。

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

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

4.3 ONCP對能量的節省

網絡編碼可以減少數據的發送次數，不僅實現了吞吐量的提高，也節省了能量，這種能量的節省對無線網絡、傳感網絡等節點能量受限的網絡顯得尤其重要。理論上來講，編碼的次數越多，那么發送數據的次數減少的越多，就意味著節省的能量越多。

如圖8所示，ONCP在取得較高吞吐量增益的前提下，能量的節省也不錯。其中橫坐標依然是相對形狀參數，縱坐標是經過ONCP編碼的報文占所有發送報文的比例，能夠相對地反映能量節省的程度，比例越高，節省的能量越多，ONCP1平均達到了 20.85%左右。這個數字看起來不大，沒有 ANC的100%那么高，但因為進行ONCP1編碼的前提是滿足結論1，即可以提高吞吐量，所以這里的20.85%是指在提高吞吐量的基礎上帶來的能量節省，而ANC的能量節省卻是以犧牲吞吐量為代價的。

經過改良后的ONCP2可以避免ONCP1帶來的“錯失編碼機會”和“無效等待”問題。如圖8所示，ONCP2編碼的比例平均達到了21.73%左右，相對于ONCP1有 4.22%的改善。此值小于5.55%(ONCP2相對于ONCP1在吞吐量上的改善平均值)，也就是說編碼數量的提高和吞吐量的改善不是完全同步的，這主要是由于ONCP2不僅會因為避免“錯失編碼機會”而增加編碼次數，而且也會因為需要避免“無效等待”而導致編碼機會的減少。

5 討論

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

圖8 ONCP編碼次數的比例

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

因此，需要討論是在一個隊列非空，另一個隊列是空時的情況。例如，設Y隊列是空的，X隊列是非空的，依次有Xi-n, Xi-n+1, …, Xi在其中排隊，Xi在隊列的尾部，在這種情況下，任何時候Y隊列有一個報文到達，都可以與X隊列頭部的報文進行網絡編碼，以獲得最大的增益。所以，當X隊列有多個報文排隊時，排在隊首的報文完全不用等待就可以立即發送，因為隊列中還有后續的報文可與即將到來的Yj報文進行編碼。

因此，只有當X隊列僅有一個報文Xi時，才需要考慮是否等待。設Xi已經排隊等待了qi的時間，這時到達了X隊列的頭部，且Xi后面沒有其他報文在排隊；Y隊列下一個要到達的報文是Yj，且預測 Yj還需要時間 m才能夠到達。如果qi+m+v＜t-c，則令Xi再等待m+v的時間；否則把Xi立即發送出去。如果在Xi等待期間，有一個新的報文Xi+1進入X隊列排隊，這時應該把Xi立即發送出去，然后讓Xi+1代替Xi等待剩余的時間，此時的w=qi+m。

6 結束語

理論網絡編碼在實際應用過程中存在缺陷，同時，現有機會式網絡編碼必須完全依賴于無線信道的廣播特性進行偷聽；而網絡編碼的優化問題關注的是如何對既定的網絡尋找事前的最佳規劃設計、部署方案，本文克服以上方法的不足，提出基于預測的機會式網絡編碼，即預測未來，有機會就編碼，沒有機會就不編碼。

本文利用EMD將自相似的長相關流量模型用相對簡單的短相關模型來替代，然后再利用成熟的ARMA進行預測，可有效地降低預測模型的復雜度，將預測的計算開銷控制在合理的水平，實現了在線的實時預測。本文的方法既可以應用于無線網絡也可應用于有線網絡中的Inter-session網絡編碼，并且也不需要調節傳輸速率。

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

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

[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] 劉外喜，余順爭，蔡君. 安全的網絡編碼所面臨的挑戰和對策[J].計算機科學, 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] 楊林，鄭剛. 無線多跳網中具有網絡編碼意識的機會路由協議[J].清華大學學報∶ 自然科學版, 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] 黃政，王新. 網絡編碼中的優化問題研究[J]. 軟件學報. 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].計算機研究與發展, 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 的自相似網絡流量預測[J]. 通信學報, 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 算法研究及其在信號去噪中的應用[D]. 哈爾濱∶ 哈爾濱工業大學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.