基于可靠重傳機(jī)制的無(wú)線網(wǎng)絡(luò)數(shù)據(jù)廣播算法

張莉華，魏長(zhǎng)寶

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

基于可靠重傳機(jī)制的無(wú)線網(wǎng)絡(luò)數(shù)據(jù)廣播算法

張莉華，魏長(zhǎng)寶

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

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

異或編碼；無(wú)線廣播；數(shù)據(jù)重傳；高斯消元

0 引 言

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

1 網(wǎng)絡(luò)編碼重傳機(jī)制

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

以節(jié)點(diǎn)R1為例，通過(guò)P1⊕P2⊕P3⊕P4，可以得到丟失的P4。類似地，節(jié)點(diǎn)R2、R3、R4也可以單獨(dú)恢復(fù)出各自丟失的數(shù)據(jù)包。然而，Nguyen D等沒有考慮對(duì)于任意給定的反饋矩陣表T，如何確定其最優(yōu)異或編碼集合。

圖1 反饋矩陣

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

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

為減少重傳階段數(shù)據(jù)包發(fā)送次數(shù)、降低重傳帶來(lái)的網(wǎng)絡(luò)開銷，本文提出了基于可靠重傳機(jī)制的無(wú)線網(wǎng)絡(luò)數(shù)據(jù)廣播算法（WDRRM)。本文設(shè)計(jì)了可靠數(shù)據(jù)重傳機(jī)制，避免了數(shù)據(jù)包分布丟失，其數(shù)據(jù)包重傳次數(shù)由丟失數(shù)據(jù)包最多的接收節(jié)點(diǎn)決定，從而有效降低丟失數(shù)據(jù)包傳輸次數(shù)，達(dá)到改善無(wú)線網(wǎng)絡(luò)數(shù)據(jù)傳輸效率目的，并測(cè)試了本文無(wú)線廣播重傳方案的可靠性能。

2 基于可靠重傳機(jī)制的無(wú)線網(wǎng)絡(luò)數(shù)據(jù)廣播算法設(shè)計(jì)

2.1 系統(tǒng)模型

本文的無(wú)線網(wǎng)絡(luò)廣播傳輸模型如圖2所示。

1)系統(tǒng)模型由1個(gè)源節(jié)點(diǎn)和K個(gè)（K＞2)接收節(jié)點(diǎn)組成，一組數(shù)據(jù)包需要廣播給K個(gè)接收節(jié)點(diǎn)。本文假設(shè)源節(jié)點(diǎn)在固定的時(shí)間段Δt內(nèi)廣播數(shù)據(jù)包。

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

圖2 系統(tǒng)模型

3)簡(jiǎn)便起見，本文假設(shè)所有的控制消息ACK或NAK均瞬間發(fā)送且不會(huì)丟失。

4)節(jié)點(diǎn)Ri數(shù)據(jù)包丟失率服從參數(shù)為pi（i=1，2，…，K)的伯努利分布。

2.2 隨機(jī)線性網(wǎng)絡(luò)編碼

本文考慮網(wǎng)絡(luò)中存在大小相同的n個(gè)數(shù)據(jù)包需要傳輸，數(shù)據(jù)包用X1，X2，…，Xn表示。源節(jié)點(diǎn)利用隨機(jī)線性異或編碼接收節(jié)點(diǎn)丟失的數(shù)據(jù)包，新的數(shù)據(jù)包Yi表示如下：

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

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

2.3 WDRRM算法設(shè)計(jì)

本文提出的WDRRM算法分為數(shù)據(jù)廣播階段和重傳階段，詳細(xì)步驟如下：

1)源節(jié)點(diǎn)向K個(gè)接收節(jié)點(diǎn)廣播N個(gè)數(shù)據(jù)包，每個(gè)數(shù)據(jù)包在固定的時(shí)間間隔發(fā)送出去，源節(jié)點(diǎn)通過(guò)收到的ACK或NAK反饋信息建立反饋矩陣T，并維護(hù)更新。

2)源節(jié)點(diǎn)廣播N個(gè)數(shù)據(jù)包后，經(jīng)過(guò)MΔt時(shí)間進(jìn)入重傳階段。所有丟失數(shù)據(jù)包構(gòu)成集合D={X1，X2，X3，…，Xn)，系數(shù)矢量gi={gi1，gi2，gi3，…，gin}（1≤i≤Mmax)中最大系數(shù)Mmax（從限定域Fq中隨機(jī)選取)用來(lái)編碼所有丟失的數(shù)據(jù)包，生成Mmax個(gè)編碼包。Mmax為所有接收節(jié)點(diǎn)中丟失數(shù)據(jù)包最大數(shù)，由下式?jīng)Q定：

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

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

如在數(shù)據(jù)重傳階段接收節(jié)點(diǎn)Ri收到Mmax個(gè)編碼包，則Ni為0。如節(jié)點(diǎn)Ri丟失2個(gè)編碼包，則Ni=2。

為使接收節(jié)點(diǎn)向源節(jié)點(diǎn)反饋所需編碼包個(gè)數(shù)Ni，本文在反饋包中添加一個(gè)新的域，用來(lái)記錄需要編碼包的個(gè)數(shù)Ni值，Ni普遍使用值不會(huì)大于255，所以1個(gè)字節(jié)的空間即滿足Ni使用。

4)源節(jié)點(diǎn)根據(jù)每個(gè)接收節(jié)點(diǎn)反饋的Ni值更新Mmax，并在新的重傳階段生成Mmax個(gè)編碼包，Mmax算法見式（4)。

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

可見，本文提出的WDRRM與NCWBR算法的區(qū)別主要表現(xiàn)在以下方面：

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

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

3)WDRRM算法降低了在重傳階段反饋信息帶來(lái)的開銷。如使用NCWBR算法接收節(jié)點(diǎn)在接收到每個(gè)異或包后，需要反饋ACK或NAK控制包，以便源節(jié)點(diǎn)更新矩陣T。當(dāng)廣播系統(tǒng)中存在大量使用者時(shí)，會(huì)造成大量反饋信息開銷。使用WDRRM算法所有接收節(jié)點(diǎn)僅在Mmax個(gè)編碼包重傳后才反饋信息，無(wú)需頻繁地向源節(jié)點(diǎn)發(fā)送反饋信息，在一定程度上降低了控制開銷。WDRRM算法的具體流程如圖3所示。

圖3 WDRRM算法流程

2.4 數(shù)學(xué)分析

本文限定平均每個(gè)數(shù)據(jù)包傳輸次數(shù)作為分析參數(shù)，令L1表示傳統(tǒng)傳輸算法的平均傳輸次數(shù)。參考文獻(xiàn)[2]給出了傳統(tǒng)傳輸算法的平均傳輸次數(shù)L1計(jì)算算法：

式中K表示接收節(jié)點(diǎn)個(gè)數(shù)。

為了計(jì)算本文提出的WDRRM算法平均傳輸次數(shù)L2，給出如下假設(shè)：

WDRRM算法平均傳輸次數(shù)計(jì)算如下：

其中PX=max{P1，P2，…，PK}；P1，P2，…，PK表示待重傳數(shù)據(jù)包；K表示接收節(jié)點(diǎn)個(gè)數(shù)。

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

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

3 仿真和性能分析

為體現(xiàn)WDRRM算法的優(yōu)越性，將NCWBR算法和傳統(tǒng)ARQ機(jī)制視為對(duì)照組。采用OPNET[13]仿真工具對(duì)這3種算法進(jìn)行測(cè)試。具體仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)表

3.1 仿真統(tǒng)計(jì)量

本文采用的評(píng)估指標(biāo)為：1)在一次廣播中不同丟包率和不同接收節(jié)點(diǎn)數(shù)對(duì)每個(gè)數(shù)據(jù)包平均重傳次數(shù)的影響；2)歸一化控制開銷。

1)平均傳輸次數(shù)。平均傳輸次數(shù)是指在仿真時(shí)間內(nèi)數(shù)據(jù)包（包括原始數(shù)據(jù)包和編碼數(shù)據(jù)包)發(fā)送的總次數(shù)與網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的比值[15]，其計(jì)算式為

式中：TA——數(shù)據(jù)包平均傳輸次數(shù)；

Ttotal——數(shù)據(jù)包總傳輸次數(shù)；

N——網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)。

2)歸一化控制開銷。歸一化控制開銷是指所有節(jié)點(diǎn)發(fā)送和轉(zhuǎn)發(fā)的數(shù)據(jù)包所含的比特?cái)?shù)與到達(dá)目的節(jié)點(diǎn)數(shù)據(jù)包所含的比特?cái)?shù)的比值[16]。其計(jì)算模型為

式中：PC——整個(gè)網(wǎng)絡(luò)輸送的數(shù)據(jù)包含的比特?cái)?shù)；

PD——到達(dá)目的節(jié)點(diǎn)數(shù)據(jù)包的總比特?cái)?shù)。

3.2 仿真結(jié)果分析

圖4顯示了不同算法在不同丟包率情況下，對(duì)平均傳輸次數(shù)的影響，網(wǎng)絡(luò)中有4個(gè)接收節(jié)點(diǎn)和20個(gè)數(shù)據(jù)包需要廣播。由圖可知，WDRRM算法的數(shù)據(jù)包平均傳輸次數(shù)最低。另外，當(dāng)丟包率相當(dāng)小時(shí)，NCWBR算法與WDRRM算法的數(shù)據(jù)包平均重傳次數(shù)很接近。隨著丟包率增加到0.3后，WDRRM算法性能要明顯優(yōu)于NCWBR算法和傳統(tǒng)ARQ機(jī)制，主要因?yàn)閃DRRM算法將需要重傳的數(shù)據(jù)包進(jìn)行組合，代替?zhèn)鹘y(tǒng)ARQ機(jī)制單個(gè)數(shù)據(jù)包重傳的操作，與NCWBR算法相比，WDRRM算法編碼包數(shù)由丟失率最高的接收節(jié)點(diǎn)決定，不受數(shù)據(jù)包丟失分布的影響，而NCWBR算法則性能不穩(wěn)定。

圖4 丟包率對(duì)平均傳輸次數(shù)的影響

圖5顯示了不同算法在不同接收節(jié)點(diǎn)個(gè)數(shù)情況下，對(duì)平均傳輸次數(shù)的影響，網(wǎng)絡(luò)中接收節(jié)點(diǎn)丟包率為0.2，有20個(gè)數(shù)據(jù)包需要廣播。當(dāng)僅有兩個(gè)廣播接收節(jié)點(diǎn)時(shí)，WDRRM算法與其他對(duì)比算法在性能上沒有大的差別。隨著接收節(jié)點(diǎn)數(shù)K的增加，與其他兩個(gè)算法相比，WDRRM算法的數(shù)據(jù)包平均傳輸次數(shù)低于其他兩種機(jī)制，這是因?yàn)閃DRRM算法數(shù)據(jù)包傳輸次數(shù)主要由丟包率最大的節(jié)點(diǎn)決定，在丟包率不變的情況下不會(huì)引起傳輸次數(shù)的明顯增加。而相比于WDRRM算法，NCWBR算法丟包分布情況變得復(fù)雜，接收節(jié)點(diǎn)通過(guò)接收到的異或包解碼出丟失包的概率降低，造成平均傳輸次數(shù)增加。

圖5 接收節(jié)點(diǎn)個(gè)數(shù)對(duì)平均傳輸次數(shù)的影響

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

圖6 不同丟包率對(duì)平均傳輸次數(shù)的影響

圖7顯示了不同算法在不同丟包率情況下，對(duì)網(wǎng)絡(luò)歸一化控制開銷的影響。依圖可知，本文提出的WDRRM算法的歸一化控制開銷要低于對(duì)照組機(jī)制，這是因?yàn)閃DRRM算法計(jì)算復(fù)雜度低，不受丟失數(shù)據(jù)包分布的影響，主要由丟失數(shù)據(jù)包最多的接收節(jié)點(diǎn)決定編碼包數(shù)，在一定程度上降低了數(shù)據(jù)包重傳次數(shù)；且目的節(jié)點(diǎn)無(wú)需將控制信息反饋給源節(jié)點(diǎn)，而對(duì)比機(jī)制具有較高的復(fù)雜度，且其選取編碼包的效率較低，導(dǎo)致歸一化控制開銷比較高。

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

4 結(jié)束語(yǔ)

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

[1]后學(xué)知，張大方，何施茗.無(wú)線廣播中基于網(wǎng)絡(luò)編碼的隱藏終端解決機(jī)制[J].小型微型計(jì)算機(jī)系統(tǒng)，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]呂政，余志軍，劉海濤.協(xié)作通信中聯(lián)合信道-網(wǎng)絡(luò)編碼的性能分析與資源分配[J].西安交通大學(xué)學(xué)報(bào)，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]盧冀，肖嵩，吳成柯.無(wú)線網(wǎng)絡(luò)中應(yīng)用機(jī)會(huì)式網(wǎng)絡(luò)編碼的廣播重傳方法[J].西安交通大學(xué)學(xué)報(bào)，2011，45（2)：68-72.

[16]任智，徐中浩，曹建玲，等.基于跨層設(shè)計(jì)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能雙向梯度路由算法[J].電子與信息學(xué)報(bào)，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

河南省科技攻關(guān)計(jì)劃項(xiàng)目（122102210430)河南省教育廳重點(diǎn)科技攻關(guān)項(xiàng)目（13A520786)

張莉華（1978-)，女，河南駐馬店市人，副教授，碩士，研究方向?yàn)橥ㄐ艆f(xié)議、網(wǎng)絡(luò)信息安全。