低延遲高效率的機會網絡編碼擴展算法

郝 兵，曹海英

(1.河套學院 數學與計算機系，內蒙古 巴彥淖爾 015000； 2.內蒙古師范大學 計算機系，內蒙古 呼和浩特 010000)

0 引 言

網絡編碼[1]可提高單源通信的容量，在組播網絡中實現最大數據傳輸率，利用共享無線介質的廣播特性，提高帶寬、降低延遲，改善傳輸功率的性能[2]。在組播場景中，網絡編碼一般實施在應用層[3]，同時在物理層中部署二階段網絡編碼以增加頻譜效率。本文重點研究無線傳感器網絡(wireless sensor network，WSN)中的機會網絡編碼。

機會網絡編碼[4]的“機會”表示編碼的伺機性，僅當機會出現時才對分組進行編碼，且不存在增加編碼機會數量的機制。開發機會網絡編碼方案時，需要對路由路徑選擇、流量負荷平衡，以及網絡編碼決策[5]等問題進行解決。同時，為緩解高負荷節點超限造成的分組丟失問題，需要考慮負荷平衡[6]，向節點提供可在接收節點處解碼的編碼分組。

將機會網絡編碼程序完美集成到當前網絡架構很困難。其實施會影響到當前網絡協議棧的功能組件，如調度、路由和擁塞控制[6,7]。所有這些組件的交互會增加實施難度和計算復雜度，如基于機會判定規則的網絡編碼[8]、面向傳輸優化的機會網絡編碼(opportunistic network coding-transmission optimization，ONC-TO)[9]和基于聚類的網絡編碼方法(clustering network coding，CNC)[10]都依賴于在網絡層中收集到的信息。基于機會判定規則的網絡編碼還依賴鏈路層的調度信息。其它機會網絡編碼在很多方面實現了性能提升，但增加了復雜度，以及一些額外網絡開銷。

為提高網絡編碼性能，必須保持低網絡開銷。相關研究表明[11,12]，可通過增加編碼機會來平衡額外的開銷，雖然承載機會網絡編碼[13](BON)程序帶來的開銷很小，但由于采用固定設置，其無法很好地應對流量和拓撲變化。因此，本文對BON編碼進行擴展，利用自適應處理進行升級，以使其具有自我維持能力，實驗結果驗證了所提方法的優越性。

1 提出的機會網絡編碼擴展方法

提出的編碼程序位于網絡與鏈路層之間，其核心為編碼算法，發現編碼機會，通過在單次傳輸中轉發多個分組來提高系統性能。本文假定每個節點知道其所有鄰近節點的位置，且節點位置固定。算法僅根據分組上一條和下一條節點位置的相關信息做出編碼決策。因此，其獨立于所有其它通信層，且與協議完全無關[14]。

所提網絡編碼方法的主要模塊與流程如圖1所示。其中，從網絡層到達節點上的所有傳出分組均被分配到3個傳輸隊列中(根據優先級排序)，即確認分組，重傳(本地)分組，以及普通傳出(本地)分組。在分組編碼模塊中，編碼算法搜索編碼機會，并尋找將消息附加到傳出分組的機會。自適應處理觀察編碼過程，并在編碼成功的基礎上采用與編碼相關的參數。在接收端，使用收到的確認消息來取消計劃中的分組重傳。如有可能，則對編碼分組進行解碼；若不能解碼，則銷毀分組。所有本地分組均保存在分組池中以進行解碼，并發送至網絡層做進一步處理。

圖1 所提網絡編碼方法的主要模塊與流程

1.1 編碼算法

根據節點上的可用信息或需要收集的信息，制定將哪些分組編碼在一起的決策。這種解決方案不會為網絡帶來新的額外開銷，但其缺點在于，編碼程序要實施的層必須包含可用的路由信息。但當前商用通信組件并不總能滿足這一條件。通過周期性的計劃測量(例如，路由鏈路投遞概率測量)來采集信息，會引入額外的開銷，由此造成網絡實際吞吐量降低。

編碼處理以分組的局部方位為基礎，該方位在中繼節點上定義，由分組上一跳和下一跳的位置決定，其圖形表示如圖2所示。沒有經過至少一次躍程的分組是不可編碼的，也不用定義其方位。以圖2(a)為例，來解釋方位的定義。

圖2 圖形表示

(1)

并將其轉換到三維空間內，其中還考慮到節點評估(Z)

(2)

通過增加容限角，可以覆蓋更大區域，由此提高分組滿足條件的概率[15]。但加大容限角參數，接收節點不能對分組解碼的概率也隨之上升。降低參數ε的數值將減少編碼機會，但接收節點成功完成分組解碼的概率則會增加。

對方位機會網絡編碼程序進行擴展，可支持多個分組的編碼。當所有分組對及其相應節點均在鄰近區域內，可以將多個分組編碼到一個分組中。ε的數值越大，可編碼多個分組的概率越高；另一方面，若至少一個ε=0， 則僅可對兩個分組進行編碼。提出的編碼程序中，通過參數ε實現編碼機會和分組成功解碼之間的平衡，而參數ε在每個節點上自動調整。

1.2 容限角的自適應

在決策制定過程中，根據定義2，容限角ε必須為已知。若將參數ε設為過低的數值，算法可能無法發現所有可能的編碼機會，從而導致網絡性能下降。若參數ε的數值過大，則接收節點很可能將無法對分組內容進行解碼，需要重傳分組，同樣會導致性能下降。此外，由于無線網絡中鏈路質量的變化，算法必須能夠快速自動調整參數ε。

根據重傳比(RR)參數來調整容限角ε，RR反映了分組編碼成功率，節點Vi的RR計算為

(3)

式中：KCVi>0為編碼分組一部分的本地分組數量，即節點上的編碼分組；KPVi>0為從網絡層傳遞到網絡編碼層的分組數量。KRVi為節點上網絡編碼層重傳分組的數量。RR值較高意味著分組重傳比率較大，重傳原因是分組解碼不成功或分組投遞失敗。這種情況下，說明網絡條件可能比較差，需要考慮保守的編碼條件，即較小的ε值。

當KRVi/KCVi較小，或KPVi較大(足以補償較高的KRVi/KCVi比)時，將得到較小的RR值。第1種情況意味著較好的編碼條件，因為與編碼分組數量相比，重傳次數較少，因此可考慮寬松的編碼條件，即增加ε。第2種情況下，若實際上進行的編碼數量很少，且節點正在處理大量分組時，KPVi數值可能會較大。一般來說，可利用這種情況對介質進行測試，由此希望放寬編碼條件。

容限角參數ε的更新過程如圖3所示，首先，給出ε的初始值。在更新周期TεU中統計KR、KC和KP。其后，計算更新周期的重傳比RR值。接著，將得出的數值與最大閾值RRmax和最小閾值RRmin相比較。根據比較結果，給出參數ε增加、減少或保持不變的決策。在更新過程結束時，重置KR、KC和KP的記數器。若網絡條件適合編碼，重傳次數很少，則增加ε。由此可發現更多的編碼機會。若決策不正確，分組重傳次數會增加，那么在自適應的下一次迭代中會降低ε。需要對ε進行連續調整，因為需要使用普通傳出分組對介質進行測試，以發現新的機會。

圖3 容限角的自適應更新流程

在更新的過程中，RR是一個非常重要的參數，其定義如下

(4)

式中：m={1,2,3,…}， 在時間間隔 [(m-1)TεU,mTεU) 中對KRmVi、KCmVi和KPmVi進行測量。

以下算法給出了更新參數ε的詳情。在解釋基本程序之外，本文還考慮到本地分組處理數量KP，KP應該大于KPMIN以應對各種不同情況的變更。若較長周期內未發現編碼機會，則增加參數ε。即，滿足未編碼閾值條件時，則增加ε值。參數ε的數值設定過低可能會造成節點上無編碼機會。因此，通過提高ε值，可以提升編碼算法的分組編碼概率。

此外，還需要考慮KR、KC和KP的采樣周期，因為修改參數ε導致的重傳會在重傳調度時間Tretrans后首次出現。至t+Tretrans之前的采樣周期將記錄參數ε之前狀態。如前文定義，參數ε必須大于等于0。此外，參數ε不應大于εmax。函數Increase_Epsilon(ε,Δε,εmax) 和Decrease_Epsilon(ε,Δε) 在增加或減少ε(Δε為步長)時考慮到了這一點。函數Sche-dule_Update(T)在時間T調度啟動ε更新程序的事件。

算法： 更新容限角ε算法

(1)if(KP>KPMIN)do

(2)if(KC>0)do

(3)if(在上一次更新中增加了ε)do

(4)CounterTrunsWithoutCoding=0；//無編碼記錄的時長

(5) Schedule_Update(t+Tretrans)；

//計劃更新

(6)elsedo

(7) Schedule_Update(t+TεU)；

(8)if(RR≤RRmin)do

(9)ε=Increase_Epsilon(ε,Δε,εmax)；

//增加ε

(10)elseif(RR≥RRmax)do

(11)ε=Decrease_Epsilon(ε,Δε)；

//降低ε

(12)endif

(13)endif

(14)elsedo

(15) Schedule_Update(t+TεU)；

(16)if(CounterTrunsWithoutCoding>No_Coding_Threshold)do

//若無編碼記錄的時長超過無編碼機會閾值

(17)ε=Increase_Epsilon(ε,Δε,εmax)；

(18)elsedo

(19)CounterTrunsWithoutCoding++；

//增加無編碼記錄的時長

(20)endif

(21)endif

(22)elsedo

(23) Schedule_Update(t+TεU)

(24)endif

2 仿真實驗與分析

2.1 評價指標

本文利用OPNET Modeler 17.1[16]開發仿真模型。通過性能評價，分析機會網絡編碼的兩個方面：首先，評估提出的編碼程序性能；其次，通過分析服務質量(quality of service，QoS)參數和公平性，評估編碼方法的用戶感受。

網絡實際吞吐量(g)是反映服務質量的基本度量，表示單位時間內網絡向特定目的地傳輸的有效信息比特數。本文將實際吞吐量定義為第i次仿真中特定網絡負荷下所有網絡節點上所有實際吞吐量之和，即g(i)。此外，將第i次仿真中的增益G(i)定義為與使用網絡編碼后實現的實際吞吐量增長

(5)

式中：gcoding(i) 表示第i次仿真中，使用網絡編碼后的網絡吞吐量；gnocoding(i) 表示第i次仿真中，不使用網絡編碼后的網絡吞吐量。

現在，分析網絡編碼對QoS的影響。本文測量了應用層的端到端延遲，以捕捉在多個節點上傳輸，并分析在傳輸路徑上可能被多次編碼的分組影響。所有通信層都會增加應用程序延遲。在分析網絡編碼對總體延遲的影響時，可以與不使用編碼方法作比較，因為其它網絡層是相同的。端到端延遲可計算為

(6)

式中：dn為第n個分組的端到端延遲；Ka(i)為應用層接收到的分組數量。

2.2 參數設置

評價中，本文對提出的機會網絡編碼方法與文獻[9]提出的面向傳輸優化的機會網絡編碼(ONC-TO)、文獻[10]提出的一種基于聚類的網絡編碼方法(CNC)，以及不使用網絡編碼的參考場景進行比較。ONC-TO[9]與本文編碼程序的操作較為相似，但存在兩個主要差異：分組編碼算法完全不同。此外，在ONC-TO中，節點使用報告消息來更新其鄰近節點的接收分組狀態，編碼過程依賴于節點通過廣播偵聽所獲取的鄰接節點上的分組信息。雖然編碼過程簡單直接，解碼處理的成功率較高，但通過特定消息和偵聽所有廣播消息獲得的信息僅能提供很少的編碼機會。當特定鄰近節點上的分組信息不可用時，編碼程序需要做出猜測。基于預期傳遞次數的路由協議通過投遞概率完成猜測。通過觀察分組的上一跳與節點N之間的鏈路的投遞概率，得到節點N持有分組p的節點估計概率。

每輪仿真中，采集第90 s和第150 s之間的結果，以觀察穩態條件。每個場景使用30種不同的網絡負荷進行評估。針對每種網絡負荷運行4次仿真。兩種編碼程序中，在首次接收分組之后，均將分組保存在分組池30 s。每隔0.5 s，至少發送一次累積確認消息。初始分組傳輸0.6 s后，發起網絡編碼層分組重傳。若在網絡中發現機會，則將累積確認消息附加到普通傳出分組上。ONC-TO至少每0.5 s發送一次報告。在可能的情況下，將報告信息附加到普通傳出分組或累積確認消息上。表1給出了本文編碼方法的自適應參數。在原始節點中生成類UDP流量。通過分組到達間隔時間調整流量密度，分組長度的變換范圍在360比特和12 000比特之間[17]。

表1 所提編碼方法的參數設置

2.3 結果分析

首先使用增益度量，對兩種編碼程序與無編碼案例進行比較，不同網絡負荷下的增益(G)變化情況如圖4所示，可以看出，與無編碼案例相比，ONC-TO、CNC和本文編碼程序均大幅提高了網絡實際吞吐量，該結果與預期相符。從圖4可發現，本文程序可以向指定目的節點傳遞最大數量的分組。當網絡負荷較小時，兩種編碼程序均不會造成網絡性能退化。低負荷狀態下，編碼機會較為稀疏；節點隊列中分組很少，因此編碼機會也非常少。此外，在無編碼案例中，系統能夠將整個負荷傳遞至目的地，且與編碼場景的性能差異可忽略不計。隨著負荷增加，編碼機會也會增多。通過使用多個編碼分組，減少了將相同的通信量傳遞至目的地所需的傳輸次數。由此減少了擁塞以及分組沖突概率，提升網絡性能。

圖4 不同網絡負荷下的增益(G)變化情況

網絡端到端延遲(ETE)變化情況如圖5所示。由圖5可知，與無編碼案例相比，兩種編碼程序不但增加了實際吞吐量，而且降低了平均ETE延遲。當網絡負荷較低時，本文方法、ONC-TO、CNC和無編碼方法的延遲大致相同。隨著負荷增加，差異開始出現。無編碼案例中的ETE延遲增加最快，且所有負荷的ETE延遲均為最高。本文編碼方法的實際吞吐量大于ONC-TO和CNC，且依然能夠保持延遲低于ONC-TO和CNC。仿真中，通過網絡編碼的參數設置來優化網絡實際吞吐量。利用網絡編碼將平均延遲保持在較低水平，雖然編碼分組在傳輸路徑中至少有一次解碼不成功，但達到目的地的延遲依然遠低于平均值。

圖5 網絡端到端延遲變化情況

本文方法的實際吞吐量和延遲方面的性能均優于ONC-TO和CNC，為深入比較，網絡編碼層內的分組重傳結果如圖6所示。從中可發現，與ONC-TO和CNC相比，本文編碼方法能夠更好地發現合適的編碼機會，從而減少分組重傳次數。編碼程序中更好的決策制定得益于自適應處理。ONC-TO中，根據分組解碼概率是否大于閾值來確定編碼決策，該閾值是固定的。CNC根據分組的聚類決策。而在本文編碼方法中，在每個節點上分別計算出容限角ε， 其中考慮到當前和過去的本地流量和鏈路條件。這意味著網絡瓶頸，并執行大部分編碼工作的節點的ε值較低。在大量編碼機會中，算法會選擇解碼可能性較大的機會。由此，減少了不正確的編碼決策和重傳次數。對于執行編碼作業較少的節點(例如位于網絡邊緣的節點)，將ε設為較大數值，以更投機的方式對分組編碼。由此，不正確的編碼決策造成重傳的情況在這些節點上更可能發生。通過較低的ε值和用于重傳的分組隊列，確保了較好的分組投遞率。

圖6 網絡編碼層內分組重傳次數

2.4 關于容限角對編碼性能的影響

容限角設置不正確，會造成服務退化，甚至會造成整個數據流的丟失。應根據當前拓撲配置和流量分布設定最優容限角。下面討論容限角的設置對本文編碼方法的性能影響。本文使用恒定分組大小(10 KB)，以排除不理想編碼的影響。在每輪仿真中保持容限角ε數值不變，并將結果與使用自適應容限角的結果相比較。圖7給出3次最大增益(MaxGain)的均值結果。結果表明，ε值的設置會對性能產生較大影響。從結果中可發現，對于給定的流量分布和拓撲，最高的MaxGain值為25.7%，其中容限角ε=35°。 使用自適應方法時MaxGain為25.1%，稍低于最優固定值設置，但自適應算法大幅提高了可用性。

圖7 容限角對本文方法的性能影響

3 結束語

本文提出一種機會網絡編碼方法，具有自適應性和通用性，適用于靜態多跳無線網絡，例如城域Wi-Fi網絡或無線傳感器網絡，作為獨立層，對上層和下層均具有透明性。且提出的編碼程序與路由無關，向網絡引入的額外開銷非常小，由此使用的無線電資源也更少。對于無編碼機會的節點，或者在整個網絡負荷較低的情況下，網絡開銷與不使用編碼程序時相同。結果表明與CNC、ONC-TO和不使用網絡編碼相比，提出的編碼程序能夠提升網絡有效吞吐量，減少延遲。