基于網絡編碼的多跳無線網絡可靠組播

文瑞涵 馮 鋼

(電子科技大學通信與抗干擾國家重點實驗室 成都 610054)

1 引言

在多跳無線網絡中的許多重要應用，如文件分發、實時信息發布，電子文檔分發、股票報價、視頻會議等都需要網絡提供一點同時對多點的(組)通信服務。利用組播(multicast)方式來支持組播通信的應用，可以大大提高資源利用率。特別在資源受限的多跳無線網絡中，鏈路帶寬受限且傳輸錯誤率較高，在這種情況下，組播網絡利用率高、能節省發送者自身的資源、可擴展性較強的優點尤為凸顯。因此，多跳無線網絡中組播一直是國際上無線網絡研究領域中的一個熱點研究課題[1-3]。大多數的組播應用屬于數據組播應用，要求恢復組播報文差錯、所有組播接收者收到的報文數量一致、順序一致、并具有一定實時性等，也即是說這些數據組播應用都需要可靠組播(reliable multicast)服務。如有接受者檢測到有傳輸錯誤或數據丟失，需要某種機制來恢復這些錯誤或丟失。

根據丟失恢復機制，現有的協議可以分為兩類：基于自動重播請求(ARQ)和基于前向糾錯法(Forward Error Correction, FEC)的協議?；贏RQ協議中，丟失分組由源節點根據 ACK(ACKnowledgement)或NACK反饋請求進行重傳，直到所有接收者都正確收到分組，使用 ACK反饋機制所有接受者必須發送 ACK到源節點，這加重了源節點負擔，還可能造成“應答閉塞”(Feedback implosion)，因此在組播網絡多采用NACK反饋機制，如PGM協議[4]和NORM[5]。RFC3208[4]中提出的PGM(Pragmatic General Multicast)協議是適用于有線網絡的采用 NACK反饋機制的可靠組播協議，組播組成員檢測到丟包后單播NACK。網元(路由器等中間系統)將 NACK沿組播路由反向地向上游轉發，直到到達發送節點，并在收到NACK的節點上組播 NACK 確認信息(NCF)，防止重復的NACK請求?；贔EC的可靠組播協議在每個分組中嵌入冗余數據，丟失的分組用 FEC 重建。在以往的研究中，我們已經對基于層疊網絡的可靠組播[6]、可靠組播網中丟包恢復對擁塞控制的影響[7]、以及可靠組播網絡本地恢復的多會話緩存分割[8]等相關問題進行了研究。最近，文獻[9]提出一種無線網絡中可靠組播協同丟失恢復算法 CoreRM，基于樹型路由(如MAODV)、NACK確認丟失，通過整個網絡中的所有節點間相互協同提供丟失恢復，使得丟包在最小的范圍內得到恢復。

利用網絡編碼來實現可靠組播是近年來提出的新思路。隨著Katti等人[10]提出COPE這種實用的XOR網絡編碼策略用于減少多跳單播無線網絡的傳輸次數之后，近年來出現很多基于COPE的網絡編碼重傳策略。ER重傳策略[11]使用XOR網絡編碼的重傳機制代替COPE的MAC層重傳，但ER采用遍歷的方法構建編碼樹，計算復雜度高，只能用于理論分析。文獻[12]中提出使用最小簇分割策略的網絡編碼重傳方法，并在節點處存儲需要重傳的包，同時也考慮了重傳包的再次丟失。但是，現有方案基本上是在有限域GF(2)中進行 XOR編碼[10-12]，這種XOR編碼機制有兩個限制條件：(1)只能允許將不同的接收方的丟包編碼到一起，但若采用隨機線性網絡編碼，屬于同一個接收方的丟包也可以進行編碼；(2)尋找最優編碼策略包是 NP困難的問題[13]，而使用隨機線性網絡編碼(Random Linear Network Coding, RLNC)卻沒有這些限制。Chi等人[14,15]在文獻中提出一種基于隨機線性網絡編碼靜態重傳策略，算法的計算復雜度為O(M3)，其中M為接收節點的數量。但Chi等人關注的是線性無關編碼向量的選擇過程，并未將 NACK機制與劃分“代”的恢復機制有效結合起來。

本文提出一種基于 G F(28)的 RLNC的可靠組播方案(NCRM)，將劃分“代”的機制和NACK機制結合起來，只要節點收到的編碼系數矩陣滿秩，就可以解出編碼包。在文獻[16]中證明， 這種選取原則可以使得線性編碼組合出現線性無相關的概率極大(約為0.99608)，完全具備有效性。本文的主要貢獻是：提出一種新的高效多跳無線網絡組播恢復機制，將劃分“代”的數據包發送機制與NACK抑制機制結合起來，并對算法進行了數學建模分析，驗證了模型的有效性。此外，我們還考慮了恢復節點也發生丟包的情況，恢復節點在第 1次收到NACK以后，用已知鄰居數量計算出NACK退避時延，按照重傳下限發送編碼包，同時，恢復節點將不能幫助恢復的包序號攜帶在 m-NACK的比特向量中，立即向上游節點請求恢復，經過鄰居恢復、多跳恢復和源端恢復，完成可靠組播過程。

本文在第 2節中給出 NCRM 的細節，在第 3節建立了節點恢復的齊次馬爾科夫鏈數學模型，在第4節給出使用此模型進行數值計算和仿真結果。

2 基于網絡編碼的多跳無線網絡可靠組播算法(NCRM)

2.1 算法概述

NCRM是依靠MAODV路由協議建立組播樹，將劃分“代”的機制和NACK抑制機制結合起來的算法。NCRM算法采用兩種NACK：一種是組播組成員發送的頭部攜帶原始丟包比特向量的NACK；另一種是組播樹成員轉發的m-NACK，由于存在恢復節點不能幫助請求節點恢復所有包的情況，恢復節點會篩選出 NACK的原始比特向量中能夠恢復的數據包比特位，保留剩余不能恢復的比特位，生成新的丟包比特向量攜帶在m-NACK頭部，發送給上游節點。節點只要位于請求節點的通信范圍內，就可以成為恢復節點幫助完成數據包的恢復。在NCRM算法中所有節點都存儲收到的數據包，恢復節點可以充分利用鄰居節點緩存的數據包信息，幫助丟包節點用最少的跳數和 NACK完成數據包的恢復。

如圖1所示，NCRM算法的重傳恢復過程主要包括3個可能的丟失恢復階段。(1)鄰居恢復階段。節點檢測出來待恢復的“代”的比特向量不全為1，表明此“代”發生丟包，將此“代”的狀態標識為Gen_Repairing，然后向鄰居節點廣播發送攜帶丟包比特向量的NACK。收到NACK的鄰居節點幫助恢復這個接收節點恢復丟包。(2)多跳恢復階段。收到NACK的鄰居節點不能幫助恢復所有的丟包，則需要進入多跳恢復階段?；謴凸濣c將已經幫助恢復的那些包對應的比特位置為 0，若恢復節點的身份是組播樹成員，則將剩余的向量復制到m-NACK的比特向量字段，立即發送給上游節點。中間節點不斷重復此過程，直至到達某節點能夠幫助恢復丟包比特向量中所有比特位為1的包。(3)源端恢復階段。中間節點不能幫助恢復數據包，最終m-NACK會到達源端，表明從請求重傳節點到源節點途經的所有節點都丟失m-NACK的丟包比特向量中比特位為1的數據包。發送節點需要重新組播這些丟包，完成源端恢復。

圖1 NCRM算法的重傳恢復過程

2.2 數據包存儲和“代”狀態轉換策略

組播樹成員或非組播樹成員都對收到的不重復的數據包進行存儲，假設所有節點都擁有無限大存儲數據空間。每一個數據包具有全局唯一的包序號(pid)和“代”序號。發送節點在發送某一序號的數據包時，“代”序號等于 pid ModG,G為“代”的大小。每一個節點維護一張GenID列表，存儲各個“代”對應的狀態和接收比特向量。當組播組成員收到一個數據包，需要提取數據包中的“代”序號，并更新此序號對應的“代”的狀態和接收比特向量。

節點首次收到k號“代”的數據包，查找GenID列表，發現k號“代”對應狀態是“不存在”，則將狀態更改成“待恢復”，同時將本次收到的包序號對應的比特向量位置1。節點持續接收屬于k號“代”的數據包，則其狀態停留在“待恢復”，直到首次接收到屬于k+1號“代”的數據包，將k號“代”狀態更新為“正在恢復”，此時存在兩種可能：(1)k號“代”的數據包未發生丟失，則將k號“代”的狀態轉換為“恢復成功”，節點繼續等待接收k+1號“代”的數據包，一直到接收k+2號“代”的數據包以后再進入k+1號“代”的恢復過程。(2)k號“代”發生丟失，若通過NCRM算法完全恢復了k號“代”的數據包后，則將k號“代”的狀態更新為“恢復成功”，表示成功接收；否則k號“代”的狀態仍為“正在恢復”。

圖2 “代”狀態轉換圖

需要指出的是，所有節點都維護GenID列表，但只有組播組成員才會因收到新“代”的包而觸發NACK的發送。

2.3 NACK抑制策略

當組播網絡中有多個組播成員丟失數據包，它們同時發送NACK請求，可能導致NACK風暴。NACK風暴會導致網絡的瓶頸鏈路發生擁塞，甚至造成整個網絡的癱瘓。因此，NCRM算法將NACK抑制與劃分“代”的機制結合起來，以避免NACK風暴。MAODV協議本身沒有NACK/ACK確認機制，NCRM算法需要使用MAODV路由協議鄰居列表中鄰居數量信息，因此將NACK作為MAODV路由協議包的一種在網絡層進行處理。

NACK包頭主要包括：數據包的“代”序號(nack_gen)，丟包比特向量(lost_bitvec)，原始發起NACK 的節點標識(initiator)和組播組的 IP地址(nack_maddr)。

網絡中存在兩種類型的NACK包：(1)組播組成員始發的NACK包。節點收到k+1號“代”的數據包以后，檢查k號“代”的接收比特向量的比特位不全為1(表示k號“代”發生丟包)，而節點又是組播組成員，則向鄰居節點廣播initiator字段為本節點的地址的 NACK, nack_maddr為組播組的IP地址。(2)組播樹成員轉發的m-NACK包?；謴凸濣c收到鄰居組播組成員發送的NACK以后，考慮到可能存在恢復節點不能幫助鄰居恢復所有包的情況(表明本節點也丟失其中的數據包，這種可能性隨G的增加而增加)，則需要轉發 m-NACK，將原來的NACK中已經成功恢復的向量比特位置0，再將剩余的丟包比特向量復制到 m-NACK的 lost_bitvec字段，進入多跳恢復過程。最壞的情況是NACK最終返回到組播組源節點，源節點重新在組播組廣播丟失的數據包，完成源端恢復。

不同類型的節點在收到 NACK后會做出不同反應：(1)組播樹成員：轉發 m-NACK和盡可能地幫助恢復數據包。若首次收到某一序號“代”的NACK，則退避等待一段時間，等收到多個鄰居發來的同一“代”的NACK以后，按照定理1的策略發送重傳編碼包。(2)非組播樹成員：既不發送NACK，又不發送m-NACK，只是盡可能幫助發送重傳編碼包。它并沒有鄰居信息，收到NACK后不會退避等待，而是直接發送重傳編碼包。非組播樹成員可能偷聽到組播樹成員轉發的數據包，充分利用這些節點可以增大恢復重傳包的可能性。

證明NCRM 方法選取的原則，是通過比較NACK比特向量中丟包比特位為1的個數Li，得到最大的丟包數Lj，恢復節點發送Lj個隨機線性編碼包。在M個鄰居節點的編碼向量矩陣中，Nj的未知變量個數最多，因此需要的用于增加編碼向量矩陣秩的線性組合數目也是最多的。在文獻[17]對隨機線性網絡編碼的分析中，滿足線性無關性的隨機線性網絡編碼包，能使編碼向量矩陣的秩增加 1，即丟包最多的接收節點Nj在接收到的編碼包后，能夠使得編碼向量矩陣滿秩，滿足可解性條件。而在其他接收節點Ni(1≤i≤M,i≠j)，均能夠獲得大于未知變量個數的線性編碼組合，同樣滿足使編碼向量矩陣滿秩的條件。因此，根據最大丟包數Lj發送隨機線性網絡編碼包，可以達到重傳目的。 證畢

3 NCRM算法的性能建模與分析

本節對NCRM算法進行建模與性能分析?？紤]一個發送節點和多個接收節點的組播模型。需要用到的術語見表1。設隨機生成的網絡拓撲為G(V,E)，其中V是網絡中所有節點構成的集合，E是由網絡中能夠相互通信的節點構成的邊集。

表1 術語

由于NCRM算法包括3個恢復階段：鄰居恢復，多跳恢復，源端恢復，不同階段經歷的時延也不相同。只要節點在某個階段恢復失敗，就會進入下一個階段的恢復過程。節點接收新的數據包后，更新長度為G的接收比特向量，其中0代表丟包，1代表成功接收。節點發送的NACK中攜帶的丟包比特向量長度也為G，其中1代表丟包，0代表未丟包。

定理2每個比特位{bi,i=1,2,3,…,G}都是取值空間為A={0,1}的隨機變量，則由Gbit構成的接收比特向量序列{XG,G=1,2,3,…} 是齊次馬爾科夫鏈。

證明接收比特向量序列是由G個比特構成的序列，而每個比特bi是取值空間為A={0,1}的隨機變量，其中1代表成功接收，概率為p, 0代表丟包，概率為1-p。用xi表示bi1bi2bi3…biG-1biG比特向量序列，xi的取值空間Ω有2G種可數狀態。發生丟包是相互獨立同分布的，因此每一個比特的取值是相互獨立同分布的，且他們構成的比特向量序列也是獨立同分布的。

n時刻的接收比特向量轉變成n+1時刻的接收比特向量只與n時刻的接收比特向量的取值有關，因此有對任意正整數G與取值?x1,x2,…,xn,xn+1∈Ω，有

由此得證接收比特向量序列{XG,G=1,2,3,…}是齊次馬爾科夫鏈。

同理可證，丟包比特向量序列{XG,G=1,2,3,…}也是齊次馬爾科夫鏈。 證畢

下面計算NCRM算法經歷 3個恢復階段的概率，設組播組成員Ri發生丟包，向鄰居節點請求重傳，則丟包向量比特的狀態空間Ω有 2G種可數狀態。由于丟包比特向量和接收比特向量都是齊次馬爾科夫鏈，任意時刻m的狀態都可以用n時刻的絕對概率與狀態轉移矩陣Pk相乘得到，其中k=m-n。

取G=2，則狀態空間為Ω={00,01,10,11}，鄰居幫助恢復的一跳轉移矩陣P為

得到的P是一個下三角矩陣。顯然，可以找到一個概率分布π={1,0,0,0}，使得π=πP,π={1,0,0,0}為齊次馬爾科夫鏈的平穩分布，說明Ti節點最終會停留在{00}狀態，即成功恢復的平穩狀態。

在n時刻，節點Ti的絕對概率為π(n)=(p2,p(1-p),p(1-p),(1-p)2)。經過鄰居j跳恢復以后的概率分布為π(n+j)=π(n)Pj。

經過j跳鄰居恢復成功的概率為

NCRM算法的包投遞率為

平均恢復跳數為

平均恢復時延為

在第4節中，我們將使用本節提出的模型進行數值計算和計算機仿真，分析影響系統性能的因素，并驗證模型的有效性。

4 NCRM算法的數值結果與仿真

本節利用仿真實驗驗證我們的分析模型并估計NCRM性能。仿真平臺是 2.30版本 NS2。仿真場景隨機分布16個節點在670 m×670 m的范圍內，任意選取一個作為發送節點，通過固定碼率流量生成器產生整個網絡仿真的數據，數據包長為 210 Byte，發送速率為 12 kbps。仿真中使用MAODV組播路由協議作為路由層協議，802.11作為 MAC層協議。本文采用性能指標主要有包投遞率、網絡的吞吐量和平均丟失恢復時延。包投遞率是指節點成功接收的包數占發送節點發送包數的百分比。平均吞吐量是指每個節點每秒接收的比特量。平均丟失恢復時延是指數據包發生丟失到數據包成功恢復的時延。

首先分析δ,DNACK和G對包投遞率和平均恢復時延的影響。圖3(a)和3(b)分別為式(5)計算出的理論與實際仿真平均恢復時延的比較結果和式(6)計算出的理論與實際仿真平均恢復跳數的比較結果?？梢钥闯隼碚摵头抡鏁r延結果符合很好。圖4(a)和 4(b)分別為不同DNACK的平均恢復時延和包投遞率，DNACK使每個節點退避等待NACK的時間增加，總時延也增加，但是適當延長DNACK得到的好處是：恢復節點能在等待時間內收到更多的NACK，每次能幫助更多鄰居恢復數據包，有效減少重傳包的發送個數，避免網絡擁塞。圖5(a)和5(b)分別為取不同G的平均恢復時延和包投遞率。NCRM算法將數據包劃分成大小為G的“代”逐一進行恢復，因此G的選取直接影響 NCRM 算法的平均恢復時延。與DNACK的選取類似，G越大，節點每次幫助恢復的數據包越多，可以減少NACK和重傳數據包的數量，從而增加包投遞率。

圖3 理論和仿真平均恢復時延、平均恢復跳數

圖4 不同 DNACK 的平均恢復時延和包投遞率

圖5 不同G的平均恢復時延和包投遞率

從以上分析可以看出DNACK和G都對包投遞率和平均恢復時延有影響，DNACK和G的選取其實是對包投遞率和平均恢復時延的折中。

圖 6，圖 7和圖 8所示為發生丟包時 PGM、CoreRM和NCRM算法的性能對比。原有的PGM算法是NACK反饋機制的有線網絡可靠組播協議，我們修改了 PGM 的有線部分，使它可以用于無線網絡?？梢钥闯?，隨丟包率的增加，3種算法的投遞率和平均吞吐量都降低，NCRM算法的包投遞率和吞吐量都是最高的。圖8中NCRM算法的平均恢復時延遠遠小于CoreRM和PGM算法。主要有3個原因：(1)NCRM算法采用隨機線性網絡編碼，在GF(28)域選取編碼系數，比在GF(2)域編碼更能利用潛在的編碼機會。(2)NCRM 算法采用的 NACK機制不同，CoreRM和PGM算法的NACK是單個包的確認機制，而NCRM算法是對一個“代”的包的確認機制。劃分“代”的機制降低了網絡中NACK的數量，進一步減少網絡擁塞。(3)NCRM算法沒有CoreRM的單播恢復的過程，因為廣播NACK可以充分利用不在組播樹上的節點所擁有的有效包信息，而單播對網絡鏈路的依賴性很大，如果單播恢復發生再次丟失，會導致恢復過程經歷更大的時延。另外，不在組播樹上的節點只參與重傳編碼包的過程，并不再次廣播NACK包，以防止NACK風暴。

因此，NCRM算法能充分利用鄰居節點存儲的信息，在發生丟包的情況下仍然具有很高的包投遞率(大于 92%)和網絡吞吐量，同時保持很低的重傳恢復時延。

圖6 發生丟包情況下的包投遞率

圖7 發生丟包情況下的吞吐量

圖8 發生丟包情況下的平均恢復時延

5 結束語

本文提出了一個適用無線組播網絡的可靠組播丟失恢復算法 NCRM。NCRM 是基于隨機線性網絡編碼和NACK機制，將數據包劃分為“代”進行丟失重傳的算法。 NCRM算法將NACK抑制策略和劃分“代”的方式結合起來，有效避免了NACK風暴。算法的設計主要目的是充分利用鄰居信息，用最少的跳數和最短的時延完成丟包恢復。本文還建立了NCRM算法的數學模型，分析了模型中影響性能的主要因素。通過仿真無線多跳組播網絡環境，對比另外兩種組播傳輸協議算法的性能，發現NCRM 算法的性能在相同仿真環境中可靠性要高于使用 XOR編碼的恢復算法。我們計劃考慮多個發送節點和不同數據發送速率的情況，設計出適合不同應用場景的算法。

[1]Shakkottai S, Liu Xin, and Srikant R. The multicast capacity of large multihop wireless networks[J].IEEE/ACM Transactions on Networking, 2010, 18(6): 1691-1700.

[2]Traskov D, Heindlmaier M, Médard M,et al.. Scheduling for network-coded multicast[J].IEEE/ACM Transactions on Networking, 2012, 20(2): 1-9.

[3]Niati R, Banihashemi A H, Kunz T,et al.. Throughput and energy optimization in wireless networks: joint MAC scheduling and network coding[J].IEEE Transactions on Vehicular Technology, 2012, 61(3): 1372-1382.

[4]RFC3208: PGM reliable transport protocol [OL]. http://www.hjp.at/doc/rfc/rfc3208.html, 2001.

[5]Internet Engineering Task Force(IETF)RFC. RFC5740-NACK-Oriented Reliable Multicast(NORM)Transport Protocol[S]. 2009.

[6]石曦, 馮鋼, 張翼德. 無線 Ad-hoc網絡中基于層疊網絡的可靠組播協議[J]. 通信學報, 2010, 31(8A): 26-31.

Shi Xi, Feng Gang, and Zhang Yi-de. Overlay reliable multicast protocol in wireless Ad-hoc network[J].Journal on Communications, 2010, 31(8A): 26-31.

[7]Xie Feng and Feng Gang. The impact of loss recovery on congestion control for reliable multicast[J].IEEE/ACM Trnsactions on Networking, 2006, 14(6): 1323-1335.

[8]Yeung K L and Feng Gang. Cache partitioning for multiple sessions in local loss recovery of reliable multicast[J].IEE Proceedings-Communications, 2005, 152(6): 866-876.

[9]黃夢潔, 馮鋼, 張翼德. Ad hoc網絡基于協同的可靠組播丟失恢復算法設計[J]. 電子與信息學報, 2010, 32(9): 2065-2071.

Huang Meng-jie, Feng Gang, and Zhang Yi-de. CoreRM:cooperative loss recovery for reliable multicast in Ad hoc networks[J].Journal of Electronics&Information Technology,2010, 32(9): 2065-2071.

[10]Katti S, Rahul H, Hu W,et al.. XORs in the air: practical wireless network coding[J].IEEE/ACM Transactions on Networking, 2008, 16(3): 497-510.

[11]Rozner E, Lyer A, Mehta Y,et al.. ER: efficient transmission scheme for wireless LANs [C]. Proceedings of CoNext'07, New York, 2007: 78-90.

[12]Zhan C, Xu Y, Wang J,et al.. Reliable multicast in wireless networks using network coding[C]. IEEE 6th International Conference on MASS, Macau, 2009: 506-515.

[13]Rouayheb S Y, Chaudhry A R, Alex S,et al.. On the minimum number of transmissions in single-hop wireless coding networks[C]. IEEE Information Theory Workshop,Tahoe City, CA, 2007: 120-125.

[14]Chi Kaikai, Jiang Xiao-hong, Ye Bao-liu,et al.. Efficient network coding-based end-to-end reliable multicast in multi-hop wireless networks[C]. Proceedings of the 15th Asia-Pacific Conference on Communications, Shanghai,2009: 32-35.

[15]Chi Kai-kai, Jiang Xiao-hong, Horiguchi S,et al.. Network coding-based reliable multicast in wireless networks[J].Computer Network, 2010, 54(11): 1823-1836.

[16]Dulman S, Nieberg T, Wu J,et al.. Trade-off between traffic overhead and reliability in multipath routing for wireless sensor networks[C]. Wireless Communications and Networking Conference(WCNC), New Orleans, Louisiana USA, 2003, 3: 1918-1922.

[17]Ho T, Médard M, Shi J,et al.. On randomized network coding[C]. 41st Annual Allerton Conference on Communication Control and Computing, Monticello, 2003, 1:11-22.