應用網(wǎng)絡編碼的動態(tài)連續(xù)協(xié)作重傳改進算法

姚玉坤，張云霞，宋威威，濮 浩，李 威

(重慶郵電大學通信與信息工程學院，重慶400065)

E-mail:332459950@qq.com

1 引言

多跳無線網(wǎng)絡中，由于無線鏈路的不可靠傳輸，總是存在數(shù)據(jù)包發(fā)生丟失或出錯，而重傳方法作為一種有效途徑用于解決上述問題.2003年提出的網(wǎng)絡編碼［1］(Network Coding，NC)，允許中間節(jié)點對多個原始包進行編碼后傳輸，目的節(jié)點再解碼，進一步提高了無線網(wǎng)絡的性能、網(wǎng)絡吞吐量.文獻［2］提出了機會網(wǎng)絡編碼(Opportunity Network Coding，ONC)，且給出了具體的編解碼方式.由于ONC簡單且易于實現(xiàn)，因此成為近些年重傳策略研究的重點，且取得了許多研究成果［3，4］.

文獻［5，6］中將ONC與ARQ相結合的重傳策略在重傳速率及重傳次數(shù)上明顯優(yōu)于傳統(tǒng)的ARQ機制.肖瀟［7］等人提出了能相對減少平均傳輸次數(shù)的網(wǎng)絡編碼廣播重傳策略(Network coding wireless broadcasting retransmission，NCWBR)，但該算法存在有些編碼包無法完全解碼的問題.針對NCWBR不可解碼問題，孫偉，張更新［8］等人提出一種改進的編碼重傳策略(Improved network coding based broadcasting retransmission，INCBR).文獻［9］提出了加權廣播重傳算法(Weighted opportunistic network coding retransm-ission，WONCR)，該算法將減少重傳次數(shù)的問題轉化為了鏈路質量加權的最大增益問題.文獻［10，11］提出應用漢明重量的丟包選擇的重傳方法.文獻［12-16］中，通過結合協(xié)作通信和網(wǎng)絡編碼技術以快速恢復丟包.上述重傳算法均是分批進行數(shù)據(jù)傳輸，且在不同批間無法進行丟包的編碼重傳，因此可稱為塊內編碼重傳(Intra-Buffer Network Coding based ARQ，INCARQ).對此，文獻［17］提出了一種基于哈希搜索和網(wǎng)絡編碼的連續(xù)重傳算法(Hash Searching and Network Coding Based Continuous Retransmission，HSNCR)，該算法將固定大小的原始包傳輸替換為逐包的連續(xù)傳輸，且優(yōu)先重傳最優(yōu)丟包組合以最大化每一次重傳的效率，充分利用了塊間編碼機會，最大化每次的重傳增益，減少了重傳次數(shù).但該算法存在著重傳性能并非最優(yōu)和發(fā)送緩存浪費的問題，且該算法并未考慮鏈路丟失率不同的情況.

在各接收節(jié)點處鏈路丟失率不同的情況下，為了更有效的減少重傳次數(shù)，并保證每次重傳編碼包增益最大，在上述理論成果的基礎上提出了一種改進的應用網(wǎng)絡編碼的動態(tài)連續(xù)協(xié)作重傳(Improved Dynamic Continuous Cooperative Retransmission，IDCCR)算法.該算法的基本思想是在完成首次數(shù)據(jù)發(fā)送緩存區(qū)的包傳輸之后，動態(tài)選擇一個最佳協(xié)作節(jié)點，由該節(jié)點恢復目的節(jié)點的丟包，且在第一次重傳完成后，源節(jié)點更新數(shù)據(jù)發(fā)送緩存區(qū)，并采用不固定大小的連續(xù)策略傳輸原始包.在重傳過程中，優(yōu)先重傳編碼增益最大的編碼包.

2 系統(tǒng)模型

如圖1所示，該網(wǎng)絡模型為單源多目的的多跳無線網(wǎng)絡模型，源節(jié)點S發(fā)送原始數(shù)據(jù)包P={P1，P2，…，PM}給N個目的節(jié)點R={R1，R2，…，RN}，在該原始數(shù)據(jù)發(fā)送的過程中由中繼節(jié)點F1轉發(fā)數(shù)據(jù)包給多個目的節(jié)點.

圖1 網(wǎng)絡模型圖Fig.1 Wireless network model

在初始傳輸時，源節(jié)點S廣播發(fā)送數(shù)據(jù)包，中繼節(jié)點將接收到的包轉發(fā)給目的節(jié)點.目的節(jié)點接收到數(shù)據(jù)包后反饋發(fā)送ACK/NACK(接收/丟失)確認消息.假設反饋信道是可靠的，反饋確認消息不會發(fā)生丟失.源節(jié)點根據(jù)接收到的確認消息創(chuàng)建數(shù)據(jù)包加權接收狀態(tài)矩陣Φ，該矩陣為一個N×M的矩陣，N為目的節(jié)點數(shù)，M為原始包數(shù)，矩陣元素用ωij表示，ωij=0表示目的節(jié)點Ri成功接收到數(shù)據(jù)包Pj;0＜ωij＜1表示目的節(jié)點Ri未成功接收到數(shù)據(jù)包Pj，且在目的節(jié)點Ri處數(shù)據(jù)包傳輸成功率為1－pi，pi為目的節(jié)點Ri處的包丟失率.如表1所示，加權接收狀態(tài)矩陣Φ中有3個目的節(jié)點丟失10個數(shù)據(jù)包.

表1 加權接收狀態(tài)矩陣ΦTable 1 Packet receiving state matrix

在丟包重傳階段，采用哈希漢明搜索選擇多個丟包生成編碼包，并重傳以恢復目的節(jié)點丟包.重復上述過程，直到所有的數(shù)據(jù)包被全部目的節(jié)點正確接收.

當全部目的節(jié)點均正確接收到數(shù)據(jù)包Pi時，認為數(shù)據(jù)包Pi正確接收.當存在至少一個目的節(jié)點沒有接收到數(shù)據(jù)包Pi時，則認為數(shù)據(jù)包Pi未被正確接收.根據(jù)加權接收狀態(tài)矩陣Φ，協(xié)作節(jié)點對丟包進行編碼操作并發(fā)送給目的節(jié)點.編解碼操作采用異或(XOR)編碼.

3 IDCCR算法

3.1 最佳協(xié)作節(jié)點選擇機制

在選擇最佳協(xié)作節(jié)點的過程中綜合考慮節(jié)點與下一跳節(jié)點之間的鏈路質量和與上一跳節(jié)點之間的鏈路質量，能夠減小傳輸時延且使傳輸成功率更高.假設協(xié)作節(jié)點為 Ci，D(F1)表示節(jié)點F1的鄰居節(jié)點集;L(n)表示節(jié)點F1的上一跳節(jié)點的鄰居節(jié)點集;N(n)表示節(jié)點F1的下一跳節(jié)點的鄰居節(jié)點集;PS，Ci表示源節(jié)點與節(jié)點Ci之間的鏈路丟包率;PCi，Ri表示節(jié)點Ci與目的節(jié)點Ri之間的鏈路丟包率.則節(jié)點Ci為最佳協(xié)作節(jié)點的條件如下所示:

1)Ci∈L(n)且 Ci∈N(n)，且有 Ci∈D(F1)，即該節(jié)點既在上一跳節(jié)點的一跳范圍內，又在下一跳節(jié)點的一跳范圍內;

2)Ci=arg min(PS，Ci)且 Ci=arg min(PCi，Ri)，即該節(jié)點與源節(jié)點之間和目的節(jié)點之間的鏈路質量均是最佳的.

證明:假定上述條件1)和條件2)均成立.即節(jié)點Ci既是源節(jié)點的鄰居又是目的節(jié)點的鄰居，且節(jié)點Ci與S以及Ri之間的鏈路丟失率均為最小，則節(jié)點Ci可以偵聽到越多的信息，從而有利于充當協(xié)作節(jié)點，充分性得證.

假設節(jié)點Ci為協(xié)作節(jié)點，則該節(jié)點既是源節(jié)點S的鄰居又是目的節(jié)點Ri的鄰居，滿足條件1).且Ci接收到最多的原始包和確認信息，即該節(jié)點與S和Ri的鏈路質量均為最好，鏈路丟失率最小，從而滿足條件2)，必要性得證.

當存在唯一節(jié)點滿足上述條件時，選擇該節(jié)點作為協(xié)作節(jié)點;當存在兩個及以上節(jié)點滿足上述條件時，選擇多個鄰居節(jié)點中擁有最多目的節(jié)點丟包的節(jié)點作為協(xié)作節(jié)點.

3.2 動態(tài)連續(xù)NC-ARQ策略

定義1.最優(yōu)重傳組合(Optimized Retransmission Combination，ORC)，可以使得所有目的節(jié)點至少恢復一個丟包的編碼包.

定義2.最大重傳組合(Maximum Retransmission Combination，MRC)，可以使得最多目的節(jié)點至少恢復一個丟包的編碼包.

本文提出了動態(tài)連續(xù)NC-ARQ策略，其基本思想是在首次完成前M個原始包的初始傳輸后，包傳輸采用數(shù)目動態(tài)的連續(xù)傳輸方式來代替數(shù)目固定的塊傳輸方式.如圖2所示為動態(tài)連續(xù)NC-ARQ策略描述圖，假設原始數(shù)據(jù)發(fā)送緩存空間為M，首先，源節(jié)點發(fā)送數(shù)據(jù)發(fā)送緩存中的原始包給目的節(jié)點，目的節(jié)點接收數(shù)據(jù)包并反饋發(fā)送ACK/NACK;其次，協(xié)作節(jié)點搜索并重傳ORC或者滿足特定條件的MRC組合，目的節(jié)點接收編碼包后解碼并反饋發(fā)送ACK/NACK;然后，源節(jié)點更新數(shù)據(jù)發(fā)送緩存，并計算第1次數(shù)據(jù)傳輸過程中發(fā)送緩存中目的成功接受到的原始包數(shù)Li;最后，源節(jié)點繼續(xù)發(fā)送Li個原始數(shù)據(jù)包，目的反饋確認信息，然后重復上述過程直到所有原始數(shù)據(jù)包被全部目的節(jié)點成功接收.

3.3 丟失數(shù)據(jù)包選擇調度算法

在IDCCR中，原始丟失數(shù)據(jù)包的選擇調度采用哈希漢明搜索.用表示丟失數(shù)據(jù)包Pj的漢明重量，該值為加權接收狀態(tài)矩陣Φ中對應Pj所在列的元素取整之和，該值越大，Pj發(fā)生丟失越多，需要該包的目的節(jié)點越多，則該包對編碼的影響越大.記加權接收狀態(tài)矩陣Φ的列向量為WP1，WP2，…，WPM，若數(shù)據(jù)包 P1，P2，…Pn同時滿足下述兩式:

式中＆表示元素進行“與”運算，則數(shù)據(jù)包P1，P2，…Pn是一組可解的編碼組合.公式(1)為編碼包的解碼條件，即允許目的節(jié)點在該編碼組合中沒有或僅有一個丟包;公式(2)為編碼性能判斷條件，值越大則越多的目的節(jié)點需要該編碼組合，編碼效率越高.

圖2 動態(tài)連續(xù)NC-ARQ策略Fig.2 Illustration of dynamic continuous NC-ARQ strategy

定義3.若數(shù)據(jù)包P1，P2，…，Pn的漢明重量分別為 W1，W2，…，Wn，則 W1，W2，…，Wn的漢明鄰域可用集合 Uw表示:

根據(jù)漢明思想的定義，哈希漢明搜索的操作步驟如下所示:

步驟

1.計算加權接收狀態(tài)矩陣Φ中所有丟包的漢明重量;

步驟2.根據(jù)漢明重量從大到小的順序建立丟包的哈希漢明列表，列表中第二行為相同漢明重量的丟包個數(shù);

步驟3.在每次搜索中總是搜索漢明重量最大的丟包.首先從哈希漢明列表中選擇漢明重量最大的丟包，然后計算該值的漢明鄰域，并按大小順序從中找到下一個可組合的丟包;再根據(jù)這兩個丟包的漢明重量和計算其漢明鄰域，并按從大到小從中找到下一個可組合的丟包.不斷重復該過程，直至當前搜索到的丟包組合的漢明重量和已經(jīng)達到N或哈希表已被搜索完畢，最后把本次搜索的結果進行編碼重傳;

步驟4.根據(jù)目的節(jié)點的重傳反饋信息，源節(jié)點即時更新加權狀態(tài)矩陣，同時更新丟包哈希漢明列表;

步驟5.重復執(zhí)行步驟3和步驟4，直至全部目的節(jié)點成功接收到所有原始數(shù)據(jù)包.

IDCCR采用哈希漢明搜索方式選擇ORC和MRC組合，如果哈希漢明列表已被全部遍歷但所選的丟包組合漢明重量和沒達到N，那么本次搜索到編碼組合為MRC組合;否則是ORC組合.如表2所示為表1中矩陣Φ對應的哈希漢明列表，編碼包 P1P3、P4P5、P2P6和 P7P10均可恢復所有目的的其中一個丟包，則這些丟包組合為ORC組合.

表2 哈希漢明列表Table 2 Hash hamming list

3.4 IDCCR算法的工作流程

IDCCR算法采用不固定大小的動態(tài)重傳策略代替固定大小的重傳機制，不僅能夠在塊內進行編碼操作，而且與現(xiàn)有基于網(wǎng)絡編碼的重傳策略相比傳輸效率更優(yōu).此外，為了更加快速有效的搜索原始丟失數(shù)據(jù)包組合，采用哈希漢明搜索方式搜索原始丟包.IDCCR算法流程圖如圖3所示.

圖3 IDCCR算法流程圖Fig.3 Flow chart of IDCCR algorithm

4 性能分析

在HSNCR算法中，除初次的M個原始數(shù)據(jù)傳輸外，每發(fā)送一個原始包且該包在目的節(jié)點處存在丟失時，將立刻進入重傳過程，且僅重傳符合條件的最優(yōu)分組組合或最大分組組合.因此，在HSNCR中，總的重傳包數(shù)(T2)為:

當采用INC-ARQ機制時，重傳中編碼包的個數(shù)等于某接收節(jié)點處的最大丟包數(shù).假定源節(jié)點處原始數(shù)據(jù)發(fā)送緩存大小為M，需要傳輸?shù)脑紨?shù)據(jù)包總數(shù)為TN，Nij表示目的節(jié)點Ri在第j個緩存數(shù)據(jù)傳輸過程中的丟包數(shù)，則總的重傳包數(shù)(T1)為:

采用IDCCR機制時，除首次固定發(fā)送M個原始數(shù)據(jù)包外，每傳送Li(1≤Li≤M)個原始包時即開始重傳，且只重傳ORC或滿足條件的MRC.當目的節(jié)點Ri有ni個原始丟包時，接收到ni個重傳編碼包時就可以恢復其全部ni個丟包.因此，重傳包數(shù)等于某個目的節(jié)點處的最大丟包數(shù).則總的重傳包數(shù)(T3)為:

由公式(4)、公式(5)和公式(6)可以看出，T1總是大于等于T2和T3，因此與傳統(tǒng)的NC-ARQ機制相比，IDCCR算法與HSNCR算法的總重傳次數(shù)相對較少，且從公式(7)可以看出，IDCCR算法的總重傳次數(shù)相比HSNCR算法更少，則IDCCR算法性能更優(yōu).

在實際中，接收節(jié)點處的鏈路丟包率決定了原始丟包的平均數(shù)量.因此，當原始數(shù)據(jù)包數(shù)足夠多時，丟包率最大的節(jié)點決定了網(wǎng)絡的重傳性能.目的節(jié)點數(shù)為N，總的原始包數(shù)為TN，目的節(jié)點Ri處的丟包率為pi.則總的數(shù)據(jù)包傳輸次數(shù)(記為TTN)可表示為:

則TN個原始包的總重傳次數(shù)為:

假設目的節(jié)點處的丟包率均相同，即p1=p2，…，=p.則每一個原始數(shù)據(jù)包的平均重傳次數(shù)(記為ANR):

5 仿真驗證及結果分析

5.1 仿真環(huán)境及參數(shù)設置

本文利用OPNET Modeler 14.5的仿真工具對IDCCR算法進行仿真實驗，網(wǎng)絡模型設計為設計400m×400m的平面區(qū)域內，無線網(wǎng)絡模型包括一個源節(jié)點、一個中繼節(jié)點和N各目的節(jié)點.MAC層協(xié)議采用IEEE 802.11.b標準，數(shù)據(jù)傳輸速率最高為11Mb/s.原始數(shù)據(jù)包初始傳輸階段和丟包編碼重傳階段，原始數(shù)據(jù)包發(fā)送間隔為1s，發(fā)送的原始數(shù)據(jù)包總數(shù)用TN表示.

5.2 仿真結果分析

5.2.1 平均重傳次數(shù)的仿真及分析

為了驗證IDCCR算法的有效性，本節(jié)對未編碼的ARQ、EONCR、HSNCR和IDCCR四種算法的平均重傳次數(shù)分別在鏈路丟失率、目的節(jié)點數(shù)不同取值的情況下進行仿真實驗，固定原始數(shù)據(jù)包總數(shù)TN為5×105個.

當M=50，N=5，鏈路丟包率p以步長0.05的規(guī)律從0.2遞增到0.7，由圖4可知，當p逐漸增大的時候，四種算法的重傳性能均有所提升.其主要原因是當丟包率逐漸增大的時候，目的節(jié)點接收數(shù)據(jù)成功率均有所降低.從圖4中可看出IDCCR算法的重傳次數(shù)相比HSNCR算法略好一點.其主要原因是IDCCR算法的連續(xù)重傳機制優(yōu)于HSNCR算法的連續(xù)重傳機制，IDCCR算法在完成原始數(shù)據(jù)包的首次傳輸后，用動態(tài)數(shù)目的原始包傳輸來替代固定數(shù)目的原始包傳輸源，且在重傳時優(yōu)先重傳ORC和滿足條件的MRC，從而提升了重傳性能.

圖4 重傳次數(shù)VS鏈路丟失率Fig.4 Retransmission efficiency against PER

當M=50，鏈路丟包率p=0.2，目的節(jié)點數(shù)N從2遞增到10.如圖5所示，當目的節(jié)點數(shù)逐漸增多的時候，IDCCR算法、EONCR算法和HSNCR算法的ANR相對比較平穩(wěn)，且IDCCR算法的ANR優(yōu)于HSNCR和EONCR算法，而未編碼的ARQ機制ANR趨于急速上升的趨勢.其主要原因是IDCCR算法中原始數(shù)據(jù)傳輸階段結束時將立刻進入重傳階段，降低了目的節(jié)點數(shù)目增多對重傳次數(shù)的影響.另外從圖5中可以看出，目的節(jié)點數(shù)越多，未采用網(wǎng)絡編碼的ARQ機制的重傳次數(shù)增速極快，而其他三種算法的上升相對比較慢，說明后三種算法性能優(yōu)于未編碼的ARQ機制.

圖5 目的節(jié)點數(shù)VS重傳性能Fig.5 Retransmission efficiency against number of receivers

5.2.2 發(fā)送緩存及原始包數(shù)對重傳性能影響的仿真及分析

本節(jié)將對編碼的ARQ、EONCR、HSNCR和IDCCR四種算法的發(fā)送緩存大小和原始數(shù)據(jù)包總數(shù)對平均重傳次數(shù)的影響進行仿真實驗.

當 N=4，p=0.2，TN=5 ×105，數(shù)據(jù)發(fā)送緩存 M 從 10 增大到400，三種算法的平均重傳次數(shù)仿真對比如圖6所示.由圖6可知，在M逐漸增大的過程中，相比其他三種算法，塊內編碼的ARQ機制的ANR明顯較低，但是塊內編碼的ARQ機制的ANR逐漸的貼近其他三種算法.當M增大到100的時候，M值對IDCCR算法的影響已經(jīng)很小，其ANR值已無線逼近理論值.對于上述四種算法，發(fā)送緩存越大，則重傳效率越高.IDCCR算法中，由于每次僅重傳 ORC或 MRC，M越大，則MRC重傳機會越小，ORC重傳機會越大，從而單次重傳效率均會提升，重傳次數(shù)減少;且由于其采用了動態(tài)連續(xù)重傳策略，新的丟包不斷的進入下一次重傳中，當M足夠大的時候，ORC的搜索要求已能夠完全滿足，即每次重傳基本都能找到ORC組合，從而使得重傳性能無線逼近理論值.明顯低于其他三種算法.這是因為相對于其他幾種機制，IDCCR具有可利用的編碼機會更多，且單次重傳效率更優(yōu).EONCR算法和應用編碼的ARQ機制僅在塊內執(zhí)行重傳過程，因此重傳效率的影響因素僅僅是每批原始數(shù)據(jù)包的數(shù)量，而不是原始數(shù)據(jù)包總數(shù).在IDCCR和HSNCR算法中，在發(fā)送緩存空間的數(shù)據(jù)首次傳輸完成之后，分別進入單個包傳輸方式和動態(tài)傳輸方式，從而其平均傳輸次數(shù)并不會受到原始包數(shù)的影響.

當 N=4，p=0.2，M=100，原始數(shù)據(jù)包總數(shù) TN 從 105個增長為106個，如圖7所示，IDCCR算法的ANR指標總體上

圖6 重傳性能VS發(fā)送數(shù)據(jù)緩存大小Fig.6 Retransmission efficiency against the size of transfer buffer

圖7 重傳性能VS原始包總數(shù)Fig.7 Retransmission efficiency against number of original packets

6 結論

本文通過分析及研究現(xiàn)有協(xié)作重傳算法，提出了一種改進的協(xié)作重傳算法，以提高傳輸效率，優(yōu)化網(wǎng)絡性能.IDCCR算法避免了INC-ARQ方案的塊隔離問題，且解決了HSNCR算法的緩存空間浪費問題并考慮了鏈路丟失率不同的情況，從而為丟失數(shù)據(jù)包提供了更多的編碼可能性.IDCCR算法是基于哈希漢明搜索的快速丟包選擇調度算法.此外，該新算法通過僅重傳ORC或MRC來最大程度地提高每一次的重傳增益.通過對不同條件下重傳性能的仿真實驗結果表明，IDCCR方案在減少重傳次數(shù)上確實優(yōu)于以往方案.在今后的工作中，我們將對多節(jié)點協(xié)作的這一方案做一些研究.