文瑞涵 馮 鋼

(電子科技大學(xué)通信與抗干擾國家重點(diǎn)實(shí)驗(yàn)室 成都 610054)

1 引言

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

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

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

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

本文在第 2節(jié)中給出 NCRM 的細(xì)節(jié)，在第 3節(jié)建立了節(jié)點(diǎn)恢復(fù)的齊次馬爾科夫鏈數(shù)學(xué)模型，在第4節(jié)給出使用此模型進(jìn)行數(shù)值計(jì)算和仿真結(jié)果。

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

2.1 算法概述

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

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

圖1 NCRM算法的重傳恢復(fù)過程

2.2 數(shù)據(jù)包存儲和“代”狀態(tài)轉(zhuǎn)換策略

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

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

圖2 “代”狀態(tài)轉(zhuǎn)換圖

需要指出的是，所有節(jié)點(diǎn)都維護(hù)GenID列表，但只有組播組成員才會因收到新“代”的包而觸發(fā)NACK的發(fā)送。

2.3 NACK抑制策略

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

NACK包頭主要包括：數(shù)據(jù)包的“代”序號(nack_gen)，丟包比特向量(lost_bitvec)，原始發(fā)起NACK 的節(jié)點(diǎn)標(biāo)識(initiator)和組播組的 IP地址(nack_maddr)。

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

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

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

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

本節(jié)對NCRM算法進(jìn)行建模與性能分析?？紤]一個(gè)發(fā)送節(jié)點(diǎn)和多個(gè)接收節(jié)點(diǎn)的組播模型。需要用到的術(shù)語見表1。設(shè)隨機(jī)生成的網(wǎng)絡(luò)拓?fù)錇镚(V,E)，其中V是網(wǎng)絡(luò)中所有節(jié)點(diǎn)構(gòu)成的集合，E是由網(wǎng)絡(luò)中能夠相互通信的節(jié)點(diǎn)構(gòu)成的邊集。

表1 術(shù)語

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

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

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

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

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

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

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

取G=2，則狀態(tài)空間為Ω={00,01,10,11}，鄰居幫助恢復(fù)的一跳轉(zhuǎn)移矩陣P為

得到的P是一個(gè)下三角矩陣。顯然，可以找到一個(gè)概率分布π={1,0,0,0}，使得π=πP,π={1,0,0,0}為齊次馬爾科夫鏈的平穩(wěn)分布，說明Ti節(jié)點(diǎn)最終會停留在{00}狀態(tài)，即成功恢復(fù)的平穩(wěn)狀態(tài)。

在n時(shí)刻，節(jié)點(diǎn)Ti的絕對概率為π(n)=(p2,p(1-p),p(1-p),(1-p)2)。經(jīng)過鄰居j跳恢復(fù)以后的概率分布為π(n+j)=π(n)Pj。

經(jīng)過j跳鄰居恢復(fù)成功的概率為

NCRM算法的包投遞率為

平均恢復(fù)跳數(shù)為

平均恢復(fù)時(shí)延為

在第4節(jié)中，我們將使用本節(jié)提出的模型進(jìn)行數(shù)值計(jì)算和計(jì)算機(jī)仿真，分析影響系統(tǒng)性能的因素，并驗(yàn)證模型的有效性。

4 NCRM算法的數(shù)值結(jié)果與仿真

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

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

圖3 理論和仿真平均恢復(fù)時(shí)延、平均恢復(fù)跳數(shù)

圖4 不同 DNACK 的平均恢復(fù)時(shí)延和包投遞率

圖5 不同G的平均恢復(fù)時(shí)延和包投遞率

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

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

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

圖6 發(fā)生丟包情況下的包投遞率

圖7 發(fā)生丟包情況下的吞吐量

圖8 發(fā)生丟包情況下的平均恢復(fù)時(shí)延

5 結(jié)束語

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

[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網(wǎng)絡(luò)中基于層疊網(wǎng)絡(luò)的可靠組播協(xié)議[J]. 通信學(xué)報(bào), 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網(wǎng)絡(luò)基于協(xié)同的可靠組播丟失恢復(fù)算法設(shè)計(jì)[J]. 電子與信息學(xué)報(bào), 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.