應用網絡編碼的動態連續協作重傳改進算法

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

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

E-mail:332459950@qq.com

1 引言

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

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

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

2 系統模型

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

圖1 網絡模型圖Fig.1 Wireless network model

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

表1 加權接收狀態矩陣ΦTable 1 Packet receiving state matrix

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

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

3 IDCCR算法

3.1 最佳協作節點選擇機制

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

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

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

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

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

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

3.2 動態連續NC-ARQ策略

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

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

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

3.3 丟失數據包選擇調度算法

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

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

圖2 動態連續NC-ARQ策略Fig.2 Illustration of dynamic continuous NC-ARQ strategy

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

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

步驟

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

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

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

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

步驟5.重復執行步驟3和步驟4，直至全部目的節點成功接收到所有原始數據包.

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

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

3.4 IDCCR算法的工作流程

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

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

4 性能分析

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

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

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

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

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

則TN個原始包的總重傳次數為:

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

5 仿真驗證及結果分析

5.1 仿真環境及參數設置

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

5.2 仿真結果分析

5.2.1 平均重傳次數的仿真及分析

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

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

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

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

圖5 目的節點數VS重傳性能Fig.5 Retransmission efficiency against number of receivers

5.2.2 發送緩存及原始包數對重傳性能影響的仿真及分析

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

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

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

圖6 重傳性能VS發送數據緩存大小Fig.6 Retransmission efficiency against the size of transfer buffer

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

6 結論

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