基于可靠重傳機制的無線網絡數據廣播算法

張莉華，魏長寶

（黃淮學院信息工程學院，河南 駐馬店 463000）

基于可靠重傳機制的無線網絡數據廣播算法

張莉華，魏長寶

（黃淮學院信息工程學院，河南 駐馬店 463000）

為降低無線網絡中數據重傳時最優異或編碼集合的復雜性，并減少數據傳輸次數、提高算法穩定性，提出一種新的基于可靠重傳機制的無線網絡數據廣播算法 （wireless network broadcast data algorithm based on reliable retransmission mechanism，WDRRM)?；陔S機線性編碼理論，將網絡中丟失的數據包進行線性異或編碼，以生成新的數據包，并設計可靠的數據重傳機制，對其進行重傳；引入高斯消元法，在接收節點收到足夠數目的編碼包后，對其進行解碼，獲取原始數據包。理論分析與仿真結果顯示：WDRRM算法的數據包平均重傳次數以及控制開銷低于其他對比編碼算法。該文算法在一定程度上能夠有效降低網絡編碼復雜性，提高網絡性能。

異或編碼；無線廣播；數據重傳；高斯消元

0 引 言

在無線網絡中，廣播是一種向多個接收節點傳輸相同數據包的重要機制，廣泛應用于IPTV、視頻點播（video on demand，VoD)及設備配置等領域[1]?？煽康膹V播意味著每個接收節點都可以正確收到源節點發送的數據包。在無線廣播中，雖然自動重傳請求（automatic repeat quest，ARQ)可使通信變得可靠，但是效率不高。在源節點傳輸數據包時，如存在至少一個節點沒有正確收到數據包，則源節點利用該算法進行重傳，會產生大量的控制包，如確認包（acknowledgement，ACK)或非確認包（negative acknowledgment，NAK)等，造成網絡吞吐量下降。文獻[2]首次提出網絡編碼，被認為是改善無線網絡吞吐量的有效算法，不同于傳統的“存儲-攜帶-轉發”機制，網絡編碼的核心思想是允許轉發節點在轉發消息前對數據包編碼。為此國內外學者進行了大量研究，如呂政等[3]針對無線網絡中源節點與中繼節點或目的節點間鏈路不可靠的問題進行研究，提出協作通信聯合信道網絡編碼資源分配機制；Prashanthi V等[4]分析了網絡編碼在無線網絡中的應用，論述了如何降低網絡負載；Kamal A E等[5]強調了在數據包廣播重傳過程中網絡編碼的安全性問題并提出了相關機制。

1 網絡編碼重傳機制

近些年，Nguyen D等[6]提出了異或網絡編碼重傳機制，其源節點維護用于記錄每個數據包被其他節點正確接收的反饋矩陣表，在數據重傳階段，源節點將其他節點沒有正確接收的數據包集合進行異或編碼，生成新的數據包用于重傳，通過一次重傳，其他節點收到經過異或后的數據包，并恢復丟失的數據包，有效降低了數據包重傳次數，提高了帶寬利用率。其算法可以描述如下：源節點維護一個反饋矩陣表T，記為T=（K，M)，每個元素T（i，j)表示接收節點Ri是否正確收到數據包Pj，即若T（i，j)=1表示節點Ri正確收到數據包Pj，若T（i，j)=0則表示節點Ri丟失數據包Pj，其中，1≤i≤K，1≤j≤M。如圖1（a)所示，源節點發送4個數據包，其余接收節點接收數據包，可以得到反饋矩陣T。節點R1成功接收到數據包P1、P2、P3，而沒有收到數據包P4。根據傳統的傳輸機制，源節點需要單獨地重傳數據包P1、P2、P3、P4，直到所有的接收節點成功地收到數據包。但是，利用基于異或的網絡編碼算法，源節點僅需要將P1、P2、P3、P4進行異或，生成新的數據包P=P1⊕P2⊕P3⊕P4，并進行重傳操作。其他節點收到廣播包P后，可以恢復出丟失的數據包。

以節點R1為例，通過P1⊕P2⊕P3⊕P4，可以得到丟失的P4。類似地，節點R2、R3、R4也可以單獨恢復出各自丟失的數據包。然而，Nguyen D等沒有考慮對于任意給定的反饋矩陣表T，如何確定其最優異或編碼集合。

圖1 反饋矩陣

對此，Xiao X等[7]提出一種基于網絡編碼的無線網絡廣播重傳策略（NCWBR)，以解決該問題。該算法尋找T中每行第1個為0的元素結合相應的數據包進行異或。接收節點收到經過異或的數據包后，將試圖恢復丟失的包，如果恢復成功，則源節點將反饋矩陣T中相應元素置1，否則仍為0。源節點根據接收節點反饋的信息更新矩陣T中元素，之后繼續編碼并重傳，直到所有元素均為1。以圖1（b)為例，NCWBR首先異或包P1、P2、P3，僅R2可以恢復丟失的數據包P3。源節點根據R2回復的信息，更新T（2，3)元素為1。但是，其他接收節點無法解碼出其丟失的數據包，則T中相應元素T（1，1)、T（1，2)仍為0，源節點繼續編碼新的數據包并重傳。

但是，NCWBR也存在一定的缺點。首先，尋找最優算法確定編碼包被證明是復雜的NP問題[8-9]。此外，源節點在廣播每個數據包后，需要更新反饋矩陣，會產生大量的控制開銷。其次，該算法受限于丟失包的分布情況，導致性能不穩定。以圖1（a)為例，源節點需要重傳1個數據包，即P=P1⊕P2⊕P3⊕P4。在圖1（b)中，源節點需要按順序重傳異或包P1⊕P2⊕P3、P1⊕P2⊕P4、P1⊕P2、P1⊕P3、P1⊕P2⊕P4、P1⊕P2、P1⊕P4、P2、P3，相比傳統的ARQ機制重傳次數更多。

為減少重傳階段數據包發送次數、降低重傳帶來的網絡開銷，本文提出了基于可靠重傳機制的無線網絡數據廣播算法（WDRRM)。本文設計了可靠數據重傳機制，避免了數據包分布丟失，其數據包重傳次數由丟失數據包最多的接收節點決定，從而有效降低丟失數據包傳輸次數，達到改善無線網絡數據傳輸效率目的，并測試了本文無線廣播重傳方案的可靠性能。

2 基于可靠重傳機制的無線網絡數據廣播算法設計

2.1 系統模型

本文的無線網絡廣播傳輸模型如圖2所示。

1)系統模型由1個源節點和K個（K＞2)接收節點組成，一組數據包需要廣播給K個接收節點。本文假設源節點在固定的時間段Δt內廣播數據包。

2)接收節點向源節點發送ACK或NAK信息，源節點接收并維護一個反饋矩陣表T，記為T=（K，N)，矩陣中元素T（i，j)表示接收節點Ri是否正確接收到數據包Pj，其中，1≤i≤K，1≤j≤N。

圖2 系統模型

3)簡便起見，本文假設所有的控制消息ACK或NAK均瞬間發送且不會丟失。

4)節點Ri數據包丟失率服從參數為pi（i=1，2，…，K)的伯努利分布。

2.2 隨機線性網絡編碼

本文考慮網絡中存在大小相同的n個數據包需要傳輸，數據包用X1，X2，…，Xn表示。源節點利用隨機線性異或編碼接收節點丟失的數據包，新的數據包Yi表示如下：

編碼系數gij（1≤j≤n)為從限定域Fq中隨機選取的值。每個接收節點收到n個編碼包后，可以通過下面線性方程，解碼出原始包：

系數矩陣由n個系數矢量G={gi1，gi2，gi3，…，gin}構成。根據Ho T和Li Y R等[10-11]提出的線性編碼理論，對于接收節點，式（2)具有可解性的條件是：系數矢量矩陣G中的元素個數要與未知原始包數相同，即矩陣G中n個系數相互獨立。根據文獻[12]，當限定域Fq足夠大，如Fq=29，編碼成功率超過99.6%，編碼失敗主要是因為矩陣G中系數非獨立，在滿足網絡性能條件下可以忽略不計。假設網絡在廣播數據時，存在1個源節點K個（K＞2)接收節點，節點Ri丟包率最大，N個原始數據包丟失D個，文獻[10]已經證明在數據重傳階段，廣播D個線性網絡編碼包，所有接收節點可以恢復出其丟失的數據包。這樣，節點Ri需要D個編碼包才能使其矢量矩陣達到滿排列并解碼出丟失的原始包，而其他接收節點Rj（1≤j≤K，j≠i)已經使其矢量矩陣達到滿排列，因為丟失的數據包少于D個。這就是說，所有接收節點滿足式（2)的可解性。

2.3 WDRRM算法設計

本文提出的WDRRM算法分為數據廣播階段和重傳階段，詳細步驟如下：

1)源節點向K個接收節點廣播N個數據包，每個數據包在固定的時間間隔發送出去，源節點通過收到的ACK或NAK反饋信息建立反饋矩陣T，并維護更新。

2)源節點廣播N個數據包后，經過MΔt時間進入重傳階段。所有丟失數據包構成集合D={X1，X2，X3，…，Xn)，系數矢量gi={gi1，gi2，gi3，…，gin}（1≤i≤Mmax)中最大系數Mmax（從限定域Fq中隨機選取)用來編碼所有丟失的數據包，生成Mmax個編碼包。Mmax為所有接收節點中丟失數據包最大數，由下式決定：

3)重傳Mmax個編碼包后，每個接收節點估算自身的編碼矢量矩陣G的排列，并用ri表示。若ri≠N，對節點Ri意味著G沒有達到滿排列，之后節點Ri將通知源節點需要重傳多少個編碼包，才可以使G達到滿排列，本文通過Ni表示需要的編碼包，具體情況如下式所示：

式中i=1，2，…，K。

如在數據重傳階段接收節點Ri收到Mmax個編碼包，則Ni為0。如節點Ri丟失2個編碼包，則Ni=2。

為使接收節點向源節點反饋所需編碼包個數Ni，本文在反饋包中添加一個新的域，用來記錄需要編碼包的個數Ni值，Ni普遍使用值不會大于255，所以1個字節的空間即滿足Ni使用。

4)源節點根據每個接收節點反饋的Ni值更新Mmax，并在新的重傳階段生成Mmax個編碼包，Mmax算法見式（4)。

5)重復3)和4)，直到所有接收節點矢量矩陣排列等于N，即Mmax=0，無丟失數據包，接收節點利用高斯消元法可以解碼出原始數據包。

可見，本文提出的WDRRM與NCWBR算法的區別主要表現在以下方面：

1)WDRRM算法在組合丟失數據包時具有低復雜度。NCWBR算法需要更新反饋矩陣以及決定異或哪一個數據包，而WDRRM算法僅組合所有丟失數據包進行重傳，而且編碼包的個數由Mmax決定。

2)WDRRM算法不受丟失數據包分布的影響，主要由丟失數據包最多的接收節點決定編碼包數。以圖1（b)為例，利用NCWBR算法源節點需要重傳9個數據包，比傳統的ARQ機制的重傳個數還多；利用WDRRM算法僅需要3個編碼包：Y1=g11P1+g12P2+g13P3+g14P4、Y2=g21P1+g22P2+g23P3+g24P4、Y3=g31P1+g32P2+g33P3+g34P4，即可以使接收節點解碼出所有丟失數據包。

3)WDRRM算法降低了在重傳階段反饋信息帶來的開銷。如使用NCWBR算法接收節點在接收到每個異或包后，需要反饋ACK或NAK控制包，以便源節點更新矩陣T。當廣播系統中存在大量使用者時，會造成大量反饋信息開銷。使用WDRRM算法所有接收節點僅在Mmax個編碼包重傳后才反饋信息，無需頻繁地向源節點發送反饋信息，在一定程度上降低了控制開銷。WDRRM算法的具體流程如圖3所示。

圖3 WDRRM算法流程

2.4 數學分析

本文限定平均每個數據包傳輸次數作為分析參數，令L1表示傳統傳輸算法的平均傳輸次數。參考文獻[2]給出了傳統傳輸算法的平均傳輸次數L1計算算法：

式中K表示接收節點個數。

為了計算本文提出的WDRRM算法平均傳輸次數L2，給出如下假設：

WDRRM算法平均傳輸次數計算如下：

其中PX=max{P1，P2，…，PK}；P1，P2，…，PK表示待重傳數據包；K表示接收節點個數。

證明：假設節點j具有最大丟包率，則有Pj=max {P1，P2，…，PK}，根據WDRRM算法重新廣播數據包數由具有最大丟包率的接收節點決定，并且只有節點j的編碼矢量矩陣G的排列為滿置時，源節點才結束重傳操作。也就是說，節點j至少成功接收M個數據包（包括原始數據包和編碼包)。這意味著WDRRM算法傳輸階段等價于源節點向節點j傳輸M個數據包。這樣，可以得出總的傳輸數據包數如下：

則可以得出WDRRM算法的平均傳輸次數L2如式（6)所示。

3 仿真和性能分析

為體現WDRRM算法的優越性，將NCWBR算法和傳統ARQ機制視為對照組。采用OPNET[13]仿真工具對這3種算法進行測試。具體仿真參數設置如表1所示。

表1 仿真參數表

3.1 仿真統計量

本文采用的評估指標為：1)在一次廣播中不同丟包率和不同接收節點數對每個數據包平均重傳次數的影響；2)歸一化控制開銷。

1)平均傳輸次數。平均傳輸次數是指在仿真時間內數據包（包括原始數據包和編碼數據包)發送的總次數與網絡中節點數的比值[15]，其計算式為

式中：TA——數據包平均傳輸次數；

Ttotal——數據包總傳輸次數；

N——網絡中節點數。

2)歸一化控制開銷。歸一化控制開銷是指所有節點發送和轉發的數據包所含的比特數與到達目的節點數據包所含的比特數的比值[16]。其計算模型為

式中：PC——整個網絡輸送的數據包含的比特數；

PD——到達目的節點數據包的總比特數。

3.2 仿真結果分析

圖4顯示了不同算法在不同丟包率情況下，對平均傳輸次數的影響，網絡中有4個接收節點和20個數據包需要廣播。由圖可知，WDRRM算法的數據包平均傳輸次數最低。另外，當丟包率相當小時，NCWBR算法與WDRRM算法的數據包平均重傳次數很接近。隨著丟包率增加到0.3后，WDRRM算法性能要明顯優于NCWBR算法和傳統ARQ機制，主要因為WDRRM算法將需要重傳的數據包進行組合，代替傳統ARQ機制單個數據包重傳的操作，與NCWBR算法相比，WDRRM算法編碼包數由丟失率最高的接收節點決定，不受數據包丟失分布的影響，而NCWBR算法則性能不穩定。

圖4 丟包率對平均傳輸次數的影響

圖5顯示了不同算法在不同接收節點個數情況下，對平均傳輸次數的影響，網絡中接收節點丟包率為0.2，有20個數據包需要廣播。當僅有兩個廣播接收節點時，WDRRM算法與其他對比算法在性能上沒有大的差別。隨著接收節點數K的增加，與其他兩個算法相比，WDRRM算法的數據包平均傳輸次數低于其他兩種機制，這是因為WDRRM算法數據包傳輸次數主要由丟包率最大的節點決定，在丟包率不變的情況下不會引起傳輸次數的明顯增加。而相比于WDRRM算法，NCWBR算法丟包分布情況變得復雜，接收節點通過接收到的異或包解碼出丟失包的概率降低，造成平均傳輸次數增加。

圖5 接收節點個數對平均傳輸次數的影響

圖6顯示了在一次廣播中，4個接收節點在不同丟包數量情況下，每個數據包平均傳輸次數的仿真結果。從圖中可知，隨著廣播過程中丟失數據包數量的增加，兩種算法的平均傳輸次數均減少，而WDRRM算法更加明顯。在丟包數量較少情況下（見圖6（a))，WDRRM算法較NCWBR算法性能改善不明顯；在丟包數量較大的情況下（見圖6（b))，WDRRM算法要明顯優于NCWBR算法。這主要是因為丟包率較小時，僅有少數數據包需要重傳，通過異或組合數據包的概率不高；當丟包數量增加時，數據包丟失分布變得不均，導致接收節點通過異或包解碼出丟失包的概率降低，而平均傳輸次數相應變大。而對比算法NCWBR沒有有效地對丟失數據包進行編碼且編碼復雜度較高，所以數據包平均傳輸次數高些。

圖6 不同丟包率對平均傳輸次數的影響

圖7顯示了不同算法在不同丟包率情況下，對網絡歸一化控制開銷的影響。依圖可知，本文提出的WDRRM算法的歸一化控制開銷要低于對照組機制，這是因為WDRRM算法計算復雜度低，不受丟失數據包分布的影響，主要由丟失數據包最多的接收節點決定編碼包數，在一定程度上降低了數據包重傳次數；且目的節點無需將控制信息反饋給源節點，而對比機制具有較高的復雜度，且其選取編碼包的效率較低，導致歸一化控制開銷比較高。

圖7 丟包率對歸一化控制開銷的影響

4 結束語

本文提出了一種新穎的基于可靠重傳機制的無線網絡數據廣播算法WDRRM，有效降低了數據包平均重傳次數，通過在不同情況下進行大量仿真，驗證WDRRM算法的性能。仿真結果顯示，與現有基于異或的網絡編碼算法（如NCWBR算法)相比，本文提出的WDRRM算法的傳輸效率更高，在具有大量接收節點的情況下更為突出。

[1]后學知，張大方，何施茗.無線廣播中基于網絡編碼的隱藏終端解決機制[J].小型微型計算機系統，2013，34（2)：238-242.

[2]Ahlswede R，Cai N，Li S Y R，et al.Network information flow[J].IEEE Trans on Information Theory，2000，46（4)：1204-1216.

[3]呂政，余志軍，劉海濤.協作通信中聯合信道-網絡編碼的性能分析與資源分配[J].西安交通大學學報，2012（4)：83-87.

[4]Prashanthi V，Guru R.Network coding-based communication in wireless ad-hoc networks[C]∥Proceedings of Communications and Signal Processing （ICCSP).Melmaruvathur：IEEE Press，2014：1040-1044.

[5]Kamal A E，Mohandespour M.Network coding-based protection[J].Optical Switching and Networking，2014，26（11)：189-201.

[6]Nguyen D，Tran T，Nguyen T.Wireless broadcast using network coding[J].IEEE Trans on Vehicular Technology，2009，58（2)：914-925.

[7]Xiao X，Yang L M，Wang W P.A wireless broadcasting retransmission approach based on network coding[C]∥Proc 4th IEEE Int'l Conf.Circuits and Systems for Communications.IEEE，2008：782-786.

[8]Chi K K，Jiang X H，Ye B L.Efficient network coding-based loss recovery for reliable multicast in wireless networks[J].IEICE Trans on Communication，2010，93（4)：971-981.

[9]Poonguzharselvib B，Vetrisselvi V.Survey on routing algorithms in opportunistic networks[C]∥Proceedings of 2013 International Conference on Computer Communication and Informatics（ICCCI).Coimbatore：IEEE Press，2013：1-5.

[10]Li Y R，Yetmg R W，Cai N.Linear network coding[J]. IEEE Trans on Information Theory，2003，49（2)：371-381.

[11]Ho T， Chen L，Chiang M，et al.Congestion control for multicast flows with network coding[J].Information Theory IEEE Tran，2012，58（9)：5908-5921.

[12]Wei S，Li J，Chen W.Power adaptive net work coding for a non-orthogonal multiple-access relay channel[J]. IEEE Transactions on Communications，2014，62（5)：872-887.

[13]Keller L，Atsan E，Argyraki K.SenseCode：Network coding for reliable sensor networks[J].ACM Transactions on Sensor Networks，2013，9（2)：1452-1461.

[14]Bettstetter C，Resta G，Santi P.The node distribution of the random waypoint mobility model for wireless Ad Hoc networks[J].IEEE Transactions on Mobile Computing，2003，2（3)：257-269.

[15]盧冀，肖嵩，吳成柯.無線網絡中應用機會式網絡編碼的廣播重傳方法[J].西安交通大學學報，2011，45（2)：68-72.

[16]任智，徐中浩，曹建玲，等.基于跨層設計的無線傳感器網絡節能雙向梯度路由算法[J].電子與信息學報，2013，35（1)：133-140.

A wireless network broadcast data algorithm based on reliable retransmission mechanism

ZHANG Lihua，WEI Changbao
（College of Information Engineering，Huanghuai University，Zhumadian 463000，China）

A new wirelessnetwork broadcastdata algorithm based on reliable retransmission mechanism （WDRRM）was proposed to decrease the complexity of the optimal XOR coding set and reduce the number of data retransmission as well as improve the stability of algorithm.The loss data packets in network were transformed into new data packets by XOR according to random linear coding theory.And a new reliable retransmission mechanism was designed for retransmitting these data packets.The original data packet was decoded by introducing Gaussian elimination after a sufficient number of code packages were received at the receiving node.Theoretical analysis and simulation resultsshow that，compared with othercodingalgorithms，the proposed WDRRM algorithm is superiorin average packetretransmission times and controlexpenses and can effectively reduce the network complexity ofnetwork coding and significantly improve the performances of the network.

XOR coding；wireless broadcasting；data retransmission；Gaussian elimination

A

：1674-5124（2015）10-0098-06

10.11857/j.issn.1674-5124.2015.10.022

2014-12-19；

：2015-01-11

河南省科技攻關計劃項目（122102210430)河南省教育廳重點科技攻關項目（13A520786)

張莉華（1978-)，女，河南駐馬店市人，副教授，碩士，研究方向為通信協議、網絡信息安全。