一種新的基于多節點網絡編碼的無線廣播重傳算法

摘 要：提出了一種基于網絡編碼的無線網絡廣播重傳算法。該算法按照包丟失分布概率的特點生成新的重傳序列，采用多節點的網絡編碼方法進行丟失包組合實現重傳。通過數學分析和仿真證明，該算法能保證接收節點的編碼可解性，同時重傳次數可達到局部最優性；與傳統重傳方法相比，該算法可以有效地減少信息包的平均傳輸次數，從而提高傳輸效率。

關鍵詞：無線網絡; 網絡編碼; 廣播重傳機制; 廣播重傳算法

中圖分類號：TN911-34 文獻標識碼：A

文章編號：1004-373X(2011)17-0051-03

New Wireless Broadcasting Retransmission Algorithm Based on Multiple Nodes Network Coding

WANG Xing-liang， LU Xuan-min， FENG Sha， LIU Ya-liang

(School of Electronics and Information， Northwestern Polytechnical University， Xi’an 710129， China)

Abstract： A wireless network broadcasting retransmission algorithm based on network coding is put forward in this paper. In accordance with the characteristic of packet loss distribution probability， it generates the new retransmission sequences， accomplishes the combination of lost packages， and then realizes the wireless network broadcasting retransmission by means of the multi-node network coding method. The mathematics analysis and simulation results prove that the algorithm can ensure the solvability of the codes at receiving nodes， meanwhile the retransmission frequency can reach the local optimality. Compared with the traditional retransmission method， this algorithm can reduce the average transmission number of message packages more effectively. Therefore， the transmission efficiency was improved.

Keywords： wireless network; network coding; broadcasting retransmission mechanism; broadcasting retransmission algorithm

0 引 言

無線廣播技術在蜂窩移動通信系統網中起著重要的作用，目前無線網絡具有較高的傳輸錯誤率，需要應用丟失包重傳技術 ［1-4］。傳統的重傳機制中，只要在一個現時時間槽有包丟失，接收節點就立刻發送NAK，信源重傳這個包，因此需要很大的重傳次數；在一種改進的機制中，僅當在現時時間槽內有數據包的丟失，并且這個包沒有在以前的時間槽內被正確接收時，才會進行重傳，即使是這樣，帶寬利用率仍然很低［5-6］。

網絡編碼理論是從2000年左右發展起來的一門新興理論，其基本原理就是傳輸鏈路上的節點對接收到的信息進行相應的操作處理后再進行轉發，而目的節點最終能夠恢復這些被處理的信息，網絡編碼已經被證實可以增強網絡性能，實現網絡最大流傳輸［7-10］。

因此，本文提出了一種新的基于網絡編碼廣播重傳機制，該機制按照包丟失分布概率特點生成新的重傳序列，采用基于多節點的網絡編碼方法進行丟失包組合實現重傳，從而極大地減少了重傳次數，提高了重傳效率。

1 基于多節點網絡編碼的無線廣播重傳算法

1.1 算法描述

首先假設一個理想的無線廣播網絡模型：

假設1:具有一個廣播源節點和M(M>2)個接收節點的無線廣播網絡，廣播源以固定間隔時間(Δt)廣播信息包。

假設2:廣播源節點能獲取接收節點丟失情況，即信息包是否丟失；丟失信息包序列號和丟失節點序列號。

假設3:假定M個接收節點的丟包率彼此互不相關，接收節點i(1≤i≤M)丟包率為Pi。令R(m，Pi)表示接收節點數目為m(m≤M)，節點丟包率為Pi(1≤i≤m)時，單位信息包重傳平均發送次數。

假設4:丟失情況記錄在緩存信息包矩陣T中。

定義1 緩存信息包矩陣T，是指廣播發送中ACK/NACKs反饋生成的信息包接收情況矩陣。該矩陣中行表示接收節點接收情況，列表示信息包接收情況。若某個信息包在某個接收節點成功接收，相應位置賦值為0；若丟失賦值為1。

定義2 緩存信息包子矩陣T(S)，是指其中S個信息包的接收情況矩陣。

具體的算法描述如下：

步驟1:依次在緩存信息包矩陣T的每一行搜尋第一個為1的位置；

步驟2:檢測步驟1找出的數據包，如果對它們編碼，在接收節點是否具有編碼可解性；

步驟3:如果步驟2檢測出接收節點無法解碼，則將無法解碼的數據包中存在丟失最多的數據包直接廣播發送出去，同時將矩陣T中對應的位置賦值0，然后返回步驟1；如果步驟2檢測出所有接收節點都可以解碼，則將所尋位置信息包取出放入編碼序列，同時將原位置賦值0；

步驟4:將編碼序列中的信息包進行網絡編碼組合后廣播發送出去，然后回到步驟1。

圖1給出了應用網絡編碼中廣播重傳算法的發送情況描述。圖1(a)為一個M=5，r=10的緩存信息包矩陣例子;圖1(b)為使用該算法時系統的運行情況。

首先通過循環搜索，系統一共生成了5個編碼組合，且編碼組合均滿足編碼組合定理，在接收節點均可解碼出相應的數據包，實現有效的重傳。需要指出的是在7⊕8⊕9組合包發送中，由于該組合中出現了8，9這兩個同時在R3丟失的數據包，則會出現7⊕8⊕9組合包在節點R3處不可解的情況。此時，由于8和9兩個數據包中9發生丟失的次數多一些，所以源節點會選擇直接將數據包9廣播發送出去，然后重新搜索矩陣T，在下次編碼組合搜索中會生成7⊕8⊕10，實現將所有丟失的數據包進行重傳發送。

1.2 數學分析

假設改進的傳統重傳算法平均傳輸次數為ηA；本文提出的基于網絡編碼的重傳算法平均傳輸次數為ηB；依次定義兩種算法為機制A和B。

首先考慮兩個節點的情況，假設這兩個節點的丟包率分別為P1，P2。

下面定義編碼增益，即傳輸帶寬比。機制B對于機制A的編碼增益定義為：

由此可知，當Pi=P(i=1，2，…，M)時，ηA為M1－P－11－PM，ηB為11－P，M越大，P越大，則G值越大，機制B相對于機制A的編碼增益越大。

2 仿真結果及分析

仿真1:接收節點數目變化。取各個接收節點丟包率P1=P2=…=PM=0.08，重傳時間間隔λΔt為100Δt。當接收節點數目從2變化到8，每次遞增1，測試平均傳輸次數變化。圖2(a)給出仿真1比較曲線。

仿真2:重傳時間間隔變化。取各個接收節點丟包率P1=P2=…=PM=0.08，接收節點數目M＝5。當重傳時間間隔從1變化到400，測試平均傳輸次數變化。圖2(b)給出仿真2比較曲線。

仿真3:各個接收節點丟包率相同且變化。取接收節點數目M＝5，重傳時間間隔λΔt為100Δt。當節點丟包率從0.02變化到0.10，每次遞增0.02，測試平均

傳輸次數變化。圖2(c)給出仿真3比較曲線。

從圖2(a)可見，基于網絡編碼的廣播重傳方法相比傳統重傳方法，平均傳輸次數有明顯減少，且隨著節點數目增加，減少幅度更大。從圖2(b)可見，重傳時間間隔足夠大時，基于網絡編碼的廣播重傳方法仿真值更接近理論值。過小的重傳間隔使得編碼組合幾率變少，當λ＝1時，基于網絡編碼中廣播重傳方法無法編碼，性能與傳統重傳相同。由圖2(c)和圖2(d)可見，無論各節點丟包率是否相同，隨著節點丟包率增加，基于網絡編碼的廣播重傳方法的平均傳輸次數均相比傳統重傳方法大大減少。基于網絡編碼的廣播重傳方法在各節點丟包率不同的情況下，遞增趨勢比各節點丟包率相同的情況下更大。

由以上結果和分析可以看出，基于網絡編碼的廣播重傳方法相比傳統的逐個重傳的方法有效地減少了信息包的平均傳輸次數，提高了重傳效率。

3 結 論

本文通過將網絡編碼理論與無線廣播技術相結合，提出了一種新的基于網絡編碼的低丟包率的無線廣播重傳算法，并且通過數學分析和仿真證明，該算法可以有效減少無線信道重傳次數，從而大大提高了無線信道的利用率。

從實際應用考慮，在使用編碼策略減少重傳次數的同時，可能會帶來重傳延時。然而，對于計算延時，隨著計算能力代價的增長可以忽略不計；對于等待延時，可以采用設定重傳時間間隔的策略，使中心節點等待一定的時間間隔再開始重傳，可以有效地降低等待延時帶來的影響。

參 考 文 獻

［1］THNENBAUM Andrew S.計算機網絡［M］.北京:清華大學出版社，2000.

［2］TABBNAE Same.無線移動通信網絡［M］.北京:電子工業出版社，2001.

［3］周聽.數據通信與網絡技術［M］.北京:清華大學出版社，2004.

［4］GUPTA P， KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46 (2): 388-404.

［5］AHLSWEDE R. Network information flow [J]. IEEE-IT， 2000， 46: 1204-1216.

［6］LIU Q. Cross-layer combining of adaptive modulation and coding with truncated ARQ over wireless links [J]. IEEE Trans. on Wireless Communications， 2004， 3 (5): 1746-1755.

［7］KOETTER R， MEDARD M. Beyond routing: an algebraic approach to network coding [J/OL]. [2002-09-22]. http://www. download.csdn.net.

［8］WU Y，CHOU P A， KUNG S Y. Minimum-energy multicast in mobile Ad Hoc networks using network coding [J]. IEEE Trans. on Communications， 2005， 53 (11): 1906-1918.

［9］DOUGHERTY R， FREILING C， ZEGER K. Linearity and solvability in multicast networks [J]. IEEE Transactions on Information Theory， 2004， 50 (10): 2243-2256.

［10］NGUYEN D， NGUYEN T， BOSE B. Wireless broadcas-ting using network coding， OSU-TR-2006-06 [R]. USA: Oregon State University， 2006.

作者簡介：

王興亮 男，1986年出生，碩士研究生。主要研究方向為網絡編碼技術研究。

盧選民 男，1972年出生，副教授。主要研究方向為多媒體通信與智能信息處理、寬帶無線移動網絡技術等。