盧冀，吳成柯，肖嵩，張冉

(1. 中國(guó)電科集團(tuán)第54研究所，河北 石家莊 050081；

2. 通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050081；

3. 西安電子科技大學(xué) ISN重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；

4. 中國(guó)電科集團(tuán)第27研究所，河南 鄭州 450005)

1 引言

機(jī)會(huì)式網(wǎng)絡(luò)編碼(ONC, opportunistic network coding)[1]是應(yīng)用于無(wú)線網(wǎng)絡(luò)的一種隨機(jī)線性網(wǎng)絡(luò)編碼[2,3]方法。ONC因在提高無(wú)線信息傳輸效率[4]和吞吐量[5]方面具有明顯的優(yōu)越性而得到廣大研究人員的青睞。

在無(wú)線廣播網(wǎng)絡(luò)中，信道擁塞和衰落等因素造成的數(shù)據(jù)分組丟失會(huì)導(dǎo)致廣播傳輸性能的下降，通常采用自動(dòng)重傳請(qǐng)求(ARQ)方法或前向糾錯(cuò)(FEC)的傳統(tǒng)方法提高廣播傳輸?shù)男阅?。ONC為提高廣播傳輸性能提供了新思路，Nguyen等[6]在理論上證明了基于ONC傳輸方式的廣播傳輸效率明顯優(yōu)于傳統(tǒng)方法，因此如何構(gòu)造高效的編碼算法成為關(guān)鍵問(wèn)題。已有的方法可以分為3類(lèi)：第1類(lèi)是針對(duì)如何對(duì)分組丟失進(jìn)行編碼的方法，此類(lèi)方法因沒(méi)有考慮實(shí)際傳輸中編碼分組丟失的問(wèn)題而不實(shí)用，例如以最小重傳次數(shù)為約束條件的WBR編碼方法[7]；第2類(lèi)是編碼和 ARQ相結(jié)合的方法，此類(lèi)方法會(huì)因ARQ重傳次數(shù)的增多使傳輸效率大幅降低，例如用于WiMAX網(wǎng)絡(luò)的傳輸算法[8]和利用反饋信息依次組合每個(gè)終端的分組丟失的算法[9]；第3類(lèi)為選擇分組丟失進(jìn)行編碼的方法，如何選擇分組丟失是此類(lèi)算法設(shè)計(jì)的關(guān)鍵。如Fan等[10]提出的采用搜索的方法選擇數(shù)據(jù)分組生成重傳分組的算法，復(fù)雜度較高，并且沒(méi)有動(dòng)態(tài)的組合重傳中的分組丟失而性能不佳，BENEFIT算法[11]考慮終端從多個(gè)重傳分組中獲取數(shù)據(jù)分組的情況，以解碼終端數(shù)、重傳分組有效性和組合分組數(shù)為條件選擇分組丟失進(jìn)行編碼，有效地提高了分組丟失重傳效率，但因選擇分組丟失判斷條件復(fù)雜而不易實(shí)現(xiàn)。

綜上所述，為了提高無(wú)線網(wǎng)絡(luò)廣播傳輸效率，基于 ONC傳輸方法的研究目的是如何實(shí)現(xiàn)實(shí)用且性能更優(yōu)的數(shù)據(jù)分組編碼算法，即第2類(lèi)方法中設(shè)計(jì)分組丟失選擇簡(jiǎn)單實(shí)用且 ARQ重傳次數(shù)少的方法，第3類(lèi)方法中如何設(shè)計(jì)高效的數(shù)據(jù)分組組合策略在降低選擇分組丟失復(fù)雜度的同時(shí)提高重傳性能；針對(duì)上述2個(gè)問(wèn)題，本文分別提出了基于ONC的多組合分組廣播傳輸(ONCMB, ONC based multiple combination packets broadcast transmission)算法和基于 ONC的單組合分組廣播傳輸(ONCSB,ONC based solo combination packet broadcast transmission)算法。ONCSB和ONCMB分別采用散列搜索的方法和組合每個(gè)終端分組丟失的方法生成重傳分組，有效地降低了此類(lèi)方法數(shù)據(jù)分組組合策略的復(fù)雜度，并提高分組丟失重傳效率。理論分析和仿真實(shí)驗(yàn)都說(shuō)明了ONCSB和ONCMB的可行性和有效性。新算法適用于單跳無(wú)線廣播網(wǎng)絡(luò)重傳方法的設(shè)計(jì)，例如Wi-Fi，WiMAX或LTE網(wǎng)絡(luò)，并且可用于設(shè)計(jì)HARQ算法[12]。

2 基于ONC傳輸方法的思想

基于 ONC的廣播傳輸方法在源節(jié)點(diǎn)采用機(jī)會(huì)式編碼(OC, opportunistic coding)技術(shù)生成重傳分組，不同終端可從一個(gè)重傳分組中恢復(fù)其分組丟失，因此該方法可以減少?gòu)V播傳輸?shù)拇螖?shù)。OC將多個(gè)數(shù)據(jù)分組通過(guò)異或(⊕)運(yùn)算編碼成組合重傳分組，假設(shè)Pi(1≤i≤N)為第i個(gè)數(shù)據(jù)分組，R為組合重傳分組，則 Pi和 R可以分別由二進(jìn)制序列{ pi, pi, … , pi}和{r,r,…,r}表示，其中，L表示長(zhǎng)

1 2L12L度，那么OC生成R中 rl(1≤l≤L)的方法為

其中，λi=1表示Pi編碼于R中。

基于 ONC的傳輸方法可以減少?gòu)V播傳輸?shù)拇螖?shù)。如圖 1所示，S發(fā)送 P1、P2和 P3后，T1、T2和 T3分別丟失 P1、P2和 P3，Rk(k=1,2,…)表示第 k個(gè)重傳分組。舉 2個(gè)例子：傳輸方法 A：重傳R1=P1⊕ P2⊕P3時(shí)，T1通過(guò) R1⊕ (P2⊕P3)=P1恢復(fù)P1，T2和T3同理從R1中得到P2和P3，A只需1次重傳；傳輸方法B：當(dāng)R1=P1⊕P2時(shí)，類(lèi)似的，T1可以恢復(fù)P1，T2可以恢復(fù)P2，但是需要傳輸R2=P3使T3恢復(fù)P3，B共需2次重傳；傳統(tǒng)ARQ方法需要分別重傳R1=P1，R2=P2和R3=P3，共需3次重傳。因此基于 ONC的傳輸方法可以減少分組丟失重傳的次數(shù)，此外，數(shù)據(jù)分組的組合方式?jīng)Q定了基于ONC傳輸方法的性能。

圖1 基于機(jī)會(huì)式網(wǎng)絡(luò)編碼重傳方法示例

3 基于ONC的廣播傳輸算法

3.1 廣播單跳傳輸模型

在實(shí)際的廣播無(wú)線網(wǎng)絡(luò)中，數(shù)據(jù)分組一般通過(guò)基站(BS)或無(wú)線訪問(wèn)節(jié)點(diǎn)(AP)廣播發(fā) Pi(1≤i≤N),Tj是否丟失Pi服從參數(shù)為qj的貝努力實(shí)驗(yàn)，其中，qj表示Tj的分組丟失率。每個(gè)時(shí)隙S廣播發(fā)送一個(gè)數(shù)據(jù)分組，全部終端通過(guò)可靠信道反饋ACK/NAK信號(hào)說(shuō)明其是否收到該時(shí)隙傳輸?shù)臄?shù)據(jù)分組。當(dāng)發(fā)送完數(shù)據(jù)分組后，源節(jié)點(diǎn)能獲得終端分組丟失的信息。

定義1 用?來(lái)表示S獲得的終端丟失數(shù)據(jù)分組的信息，其可以表示為一個(gè)M行N列的矩陣，且M＞1。?中元素ωji∈{0,1}表示Tj是否成功收到Pi，ωji=0表示Pi成功發(fā)送，反之表示Pi丟失。圖2給出了?的示例。

圖2 ?示例

定義2 傳輸帶寬B可以用來(lái)描述傳輸算法的性能[6]，其表示為

其中，K表示數(shù)據(jù)分組重傳的次數(shù)。B反映了成功傳輸一個(gè)數(shù)據(jù)分組需要的平均傳輸次數(shù)。

3.2 ONCSB算法

如何選擇分組丟失決定了此類(lèi)算法的復(fù)雜度和性能，此外，散列搜索算法具有較低的復(fù)雜度和較高的性能，因此ONCSB采用散列搜索的方法降低數(shù)據(jù)分組選擇的復(fù)雜度并提高重傳性能。

ONCSB選擇分組丟失的過(guò)程分為4個(gè)階段：1) 根據(jù)散列函數(shù)計(jì)算分組丟失的散列值；2) 根據(jù)得到的散列值創(chuàng)建分組丟失的散列列表；3)從散列列表表中選擇滿足條件的分組丟失組合成重傳分組；4)根據(jù)終端是否從重傳分組中恢復(fù)數(shù)據(jù)分組的情況，更新散列列表。

階段1：計(jì)算分組丟失的散列值。根據(jù)?第i列的元素值計(jì)算Pi的散列值，計(jì)算該散列值的散列函數(shù)F為

分組丟失對(duì)應(yīng)的散列值跟該終端分組丟失信息對(duì)應(yīng)。由式(3)得到Pi對(duì)應(yīng)的散列值hi滿足0≤hi≤2M-1。

階段 2：創(chuàng)建分組丟失的散列列表。根據(jù)分組丟失散列值由大到小得順序建立分組丟失的散列列表，圖3給出了圖2所示分組丟失的散列列表，該列表第1行是由式(3)計(jì)算得到的散列值H，第2行和第3行表示散列值為H的數(shù)據(jù)分組數(shù)和數(shù)據(jù)分組。

圖3 散列表

階段 3：選擇滿足編碼條件的分組丟失生成重傳分組。具體過(guò)程是：A 在散列列表中，選擇最大散列值h1；B從已選擇的散列值的鄰域中選擇最大的散列值，直到該鄰域?yàn)榭?；C把所選散列值對(duì)應(yīng)的數(shù)據(jù)分組組合成一個(gè)重傳分組。定義U表示散列值h1,h2,…,hn(n∈{1, 2, …, N})鄰域，U的計(jì)算式為

其中， bij(1≤i≤n)表示 hi的第 j比特。如圖 3所示，首選選擇最大的散列值20，從其鄰域中選擇散列值8，再?gòu)?0和8的鄰域中選擇2，最后從20、8和2的鄰域中選擇1，之后鄰域?yàn)榭?，搜索完成，將散列?0、8、2和1對(duì)應(yīng)的數(shù)據(jù)分組P5、P4、P2和P1編碼組合成一個(gè)重傳分組。

階段4：傳輸?shù)?階段生成的數(shù)據(jù)分組，在一個(gè)傳輸時(shí)隙內(nèi)，終端通過(guò)ACK/NAK信號(hào)反饋其是否收到該數(shù)據(jù)分組。當(dāng)一個(gè)終端未收到該數(shù)據(jù)分組時(shí)，重新計(jì)算該終端分組丟失的散列值，計(jì)算公式為

其中，τj=1表示Tj沒(méi)有從該重傳分組中恢復(fù)其分組丟失，并根據(jù)上式計(jì)算的散列值將分組丟失更新到散列列表中。如果散列列表中存在分組丟失，至階段3，否則結(jié)束。

3.3 ONCMB算法

ONCMB算法在源節(jié)點(diǎn)依次選擇每個(gè)終端的分組丟失組成重傳分組，使每個(gè)終端的分組丟失依次編碼于重傳分組中，終端從收到的重傳分組中解碼其分組丟失，若該重傳分組只包含終端一個(gè)分組丟失，該終端可以解碼得到其分組丟失，否則，終端可以從多個(gè)重傳分組解碼得到多個(gè)分組丟失。與文獻(xiàn)[9]方法相比，ONCMB編碼生成單個(gè)重傳分組的不同分組丟失數(shù)較多，因此有效地提高了終端恢復(fù)分組丟失的效率，提高了傳輸性能。

ONCMB算法生成重傳分組的過(guò)程可分為以下2個(gè)階段。

階段 1：每次傳輸，S重傳由每個(gè)終端的一個(gè)分組丟失編碼組合成的重傳分組，而后終端反饋ACK/NAKs信號(hào)說(shuō)明其是否收到該時(shí)隙傳輸?shù)臄?shù)據(jù)分組。同理，S生成并發(fā)送重傳分組，再接收反饋得知未恢復(fù)的數(shù)據(jù)分組，依次類(lèi)推，直到全部數(shù)據(jù)分組都成功發(fā)送。終端從收到的重傳分組中恢復(fù)分組丟失，當(dāng)重傳分組中包含某終端一個(gè)分組丟失時(shí)，該終端立即恢復(fù)這個(gè)分組丟失，當(dāng)重傳分組中包含某終端多個(gè)分組丟失時(shí)，該終端可以從后續(xù)重傳分組中恢復(fù)分組丟失后再恢復(fù)這個(gè)重傳分組中包含的最后一個(gè)分組丟失。

具體的做法是：從?每行中選擇第一個(gè)值為1的數(shù)據(jù)分組編碼得到重傳分組 R1，傳輸 R1后，若Tj(1≤j≤M)未收到R1，則?中第j行所選擇數(shù)據(jù)分組對(duì)應(yīng)的元素值不變，否則，該元素值為零；繼續(xù)生成 R2，直到 ? 為零矩陣。圖 2中，R1=P1⊕P2⊕P3⊕P4⊕P5，假設(shè)只有T2未收到R1，則R2=P3⊕P2⊕P5⊕P6⊕P7，若所有終端收到 R2，T1，T4和T5通過(guò)R1和R2恢復(fù)各自的2個(gè)分組丟失。

階段2：ONCMB使終端從多個(gè)重傳分組中恢復(fù)其分組丟失，因把某終端的多個(gè)分組丟失組合到一個(gè)重傳分組中，可能會(huì)導(dǎo)致該終端不能從收到的多個(gè)重傳分組中恢復(fù)分組丟失[13,14]，因此ONCMB依次傳輸這些終端所需的數(shù)據(jù)分組完成重傳。此時(shí)，根據(jù)組合分組信息在發(fā)送端找出終端不能恢復(fù)的ε(ε≥2)個(gè)數(shù)據(jù)分組，首先傳輸ε-1個(gè)不可恢復(fù)的數(shù)據(jù)分組，再解碼獲取最后一個(gè)分組丟失。

令 Ei(n)=1(1≤i≤k, 1≤n≤N)表示數(shù)據(jù)分組 Pn編碼于Ri，反之Pn未編碼于Ri，其中，k表示階段1生成的重傳分組數(shù)。令N維行向量ψ=[φ1, φ2, …,φn, …, φN]，其中，φn表示Pn編碼在哪些重傳分組中的信息，則ψ表示所有數(shù)據(jù)分組是否編碼于重傳分組中的信息。對(duì)于終端Tj(1≤j≤M)，φn的計(jì)算公式為

通過(guò)式(6)可得到ψ，從ψ中選擇相等的非零元素即可推出Tj未恢復(fù)的分組丟失。如圖2中T3不能從重傳分組R1和R2中恢復(fù)其分組丟失P3和P5，因由式(6)計(jì)算可得 ψ=[0,0,15,0,15,0, 0]，得到φ3=φ5≠0。

4 平均傳輸帶寬分析

當(dāng)N足夠大時(shí)，文獻(xiàn)[6]給出了最優(yōu)的平均傳輸帶寬Bopt，其表示式為

其中，qmax=max{q1,q2,…,qM}，qj(1≤j≤M)表示終端Tj的分組丟失率。

令Rs和Bs分別表示ONCSB算法傳輸?shù)钠骄鶖?shù)據(jù)分組數(shù)和平均傳輸帶寬。當(dāng)N足夠大時(shí)，ONCSB的重傳分組中最多包含任一終端的一個(gè)分組丟失，因此其生成的平均重傳分組數(shù)由分組丟失率最大終端的分組丟失數(shù)決定，于是ONCSB生成的平均重傳分組數(shù)r1為

此外，傳輸r1的過(guò)程仍然會(huì)有分組丟失，由上述分析可知，其平均分組丟失數(shù)r2為

依此類(lèi)推，傳輸 ri-1個(gè)分組丟失產(chǎn)生的平均分組丟失數(shù)ri可以表示為

因此，ONCSB傳輸?shù)钠骄鶖?shù)據(jù)分組數(shù)為

代入式(2)，可得

令RM和BM分別表示ONCMB算法傳輸?shù)钠骄鶖?shù)據(jù)分組數(shù)和平均傳輸帶寬。在第1階段，ONCMB的重傳分組中包含每個(gè)終端的分組丟失，平均重傳分組數(shù)由分組丟失率最大終端的分組丟失數(shù)決定，由式(10)知，第1階段的平均重傳分組數(shù)r1為

Yossef等[13]在理論上證明了采用二進(jìn)制碼對(duì)分組丟失信息進(jìn)行編碼可使重傳次數(shù)以很大的概率達(dá)到最優(yōu)，本文基于機(jī)會(huì)式編碼的重傳方法采用二進(jìn)制碼(如式(1)所示)進(jìn)行編碼，滿足上述結(jié)論，該方法可使終端以很大概率從最少的重傳分組(r1)中恢復(fù)全部分組丟失，即r2以很大概率為零。因此，當(dāng)N足夠大時(shí)，第2階段平均發(fā)送的數(shù)據(jù)分組數(shù)r2近似為分組丟失率最大終端平均分組丟失數(shù)的無(wú)窮小量，則r2為

由式(13)和式(14)可得，ONCMB平均發(fā)送的數(shù)據(jù)分組數(shù)RM為

代入式(2)，可得

由式(12)和式(16)可知，在一定條件下，本文提出的ONCSB和ONCMB方法可以使網(wǎng)絡(luò)平均傳輸帶寬接近最優(yōu)值。

5 仿真實(shí)驗(yàn)及分析

實(shí)驗(yàn)采用圖1所示傳統(tǒng)的多播網(wǎng)絡(luò)，S每次通過(guò)廣播方式發(fā)送一個(gè)數(shù)據(jù)分組，數(shù)據(jù)分組的長(zhǎng)度和發(fā)送時(shí)間間隔相同。在相同的分組丟失信息?條件下，仿真得出了不同算法成功發(fā)送全部分組丟失所需的傳輸次數(shù)，再由式(2)得到傳輸帶寬，多次實(shí)驗(yàn)后得到平均傳輸帶寬。由式(1)知，平均傳輸帶寬越小算法的性能越好。

為了驗(yàn)證算法的有效性和可行性，并有效反映算法在真實(shí)網(wǎng)絡(luò)環(huán)境下的性能，仿真采用不同類(lèi)型的分組丟失模型來(lái)模擬實(shí)際無(wú)線信道的狀態(tài)，分組丟失模型分為：1) 隨機(jī)分組丟失模型；2) 連續(xù)分組丟失模型[6]。仿真實(shí)驗(yàn)采用上述分組丟失率模型得到分組丟失信息?，并統(tǒng)計(jì)了不同算法針對(duì)相同?得到的平均傳輸帶寬。

仿真中比較了下述算法：1)傳統(tǒng)的基于ARQ機(jī)制的傳輸算法，記為SF；2)一種適用于WiMAX的傳輸算法[8]，記為T(mén)NC；3)文獻(xiàn)[9]的傳輸算法NCWBR；4)文獻(xiàn)[10]的傳輸算法，記為 DNC；5)文獻(xiàn)[11]的BENEFIT算法；6)本文提出的基于ONC的單組合分組廣播傳輸算法，記為ONCSB；7)本文提出基于ONC的多組合分組廣播傳輸算法，記為ONCMB。

5.1 隨機(jī)分組丟失模型

分組丟失率q的范圍是[0.01, 0.2]，步長(zhǎng)為0.01，數(shù)據(jù)分組數(shù)N={10,100},終端數(shù)M=5。當(dāng)終端分組丟失率相等，即q1=q2=…=qM=q時(shí)，圖4給出了分組丟失率變化對(duì)算法傳輸帶寬性能的影響?；贠NC的傳輸算法的性能明顯優(yōu)于傳統(tǒng)重傳算法。隨著分組丟失率的增加，ONCSB和ONCMB算法的性能較其他算法更好。在一定分組丟失率的條件下，分組丟失數(shù)隨 N值增大而增加，ONCSB和ONCMB選擇分組丟失的編碼策略較好，因此它們的平均傳輸帶寬較小，而 SF算法不對(duì)數(shù)據(jù)分組進(jìn)行編碼，其性能最差。ONCSB的性能略好于ONCMB的性能，原因在于前者從所有分組丟失中選擇可以組合的分組丟失，而后者是連續(xù)的選擇終端的分組丟失，因此ONCMB的重傳分組可能出現(xiàn)不能使終端恢復(fù)分組丟失的情況，需要重傳分組丟失保證該終端可恢復(fù)其分組丟失，導(dǎo)致ONCMB的傳輸帶寬增加。

圖4 隨機(jī)分組丟失模型下平均傳輸帶寬比較

為了說(shuō)明終端數(shù)同平均傳輸帶寬的關(guān)系，圖 5給出了終端數(shù)M不同時(shí)對(duì)應(yīng)的平均傳輸帶寬，圖中q1=q2=…=qM= 0.1且N=50。由圖可知，當(dāng)M值不同時(shí)，ONCSB和ONCMB的性能較好，并且隨著M的增加，其平均傳輸帶寬較其他幾種算法收益增加。在一定分組丟失率的條件下，隨著M的增加，丟失同一個(gè)數(shù)據(jù)分組的終端數(shù)增多，廣播重傳單個(gè)數(shù)據(jù)分組的效率增加，基于 ONC的傳輸方法的性能接近于SF方法的性能[15]。

5.2 連續(xù)分組丟失模型

為了比較信道發(fā)生連續(xù)分組丟失時(shí)算法的性能，定義二狀態(tài)馬爾可夫過(guò)程的2個(gè)狀態(tài)為好信道狀態(tài)Sg和壞信道狀態(tài)Sb。Pα和Pβ分別表示Sg到Sb和Sb到Sg的轉(zhuǎn)移概率，信道處于狀態(tài)Sg和 Sb的概率分別為 Pβ/(Pα+Pβ)和 Pα/(Pα+Pβ)。終端分組丟失率之間相互獨(dú)立，Pα的范圍是[0,0.2]，變化步長(zhǎng)為 0.02，Pβ為固定值 0.4，Sg和Sb對(duì)應(yīng)的分組丟失率分別為 0.01和 0.5，N={10,100}, M=5。

圖5 終端數(shù)不同時(shí)平均傳輸帶寬比較

圖6 給出了算法的平均傳輸帶寬，Pα=0時(shí)，信道處于好狀態(tài)，終端分組丟失率較低(0.01)，所以全部傳輸算法的性能幾乎相同，隨著 Pα的增加，信道處于壞狀態(tài)的概率增加，分組丟失增多，并且N的增大有利于基于ONC的傳輸算法的重傳分組中組合更多的分組丟失，因此隨著Pα和N的增大，它們的性能比SF算法的性能更好，其中，ONCSB和ONCMB算法的性能略?xún)?yōu)于BENEFIT算法，并明顯好于其他傳輸算法的性能。隨著Pα的增加，出現(xiàn)數(shù)據(jù)分組連續(xù)丟失的情況增多，在這種情況下，同本文算法一樣，BENEFIT算法能使每個(gè)終端的分組丟失組合于單個(gè)重傳分組使重傳數(shù)量減少，因此其同本文算法性能接近；DNC算法因沒(méi)有動(dòng)態(tài)的處理重傳過(guò)程的分組丟失導(dǎo)致其重傳次數(shù)增加，因此平均傳輸帶寬在所有基于ONC的傳輸方法中最差。

圖6 連續(xù)分組丟失模型下平均傳輸帶寬比較

5.3 算法時(shí)間比較

表1給出了不同算法的時(shí)間復(fù)雜度。采用隨機(jī)分組丟失模型，終端分組丟失率均為0.1，M設(shè)為10，實(shí)驗(yàn)得出了不同算法的平均執(zhí)行時(shí)間，如圖7所示。由比較知，ONCSB由于采用了效率較高的散列搜索方法選擇分組丟失，保證傳輸帶寬性能最優(yōu)的條件下，維持了較低的運(yùn)行時(shí)間。ONCMB搜索終端不可恢復(fù)分組丟失的過(guò)程增加了執(zhí)行時(shí)間，但與復(fù)雜度相同的NCWBR和DNC相比，其傳輸效率最好，其平均執(zhí)行時(shí)間隨著數(shù)據(jù)分組數(shù)的增加明顯優(yōu)于DNC算法，ONCMB性能略好于BENEFIT算法，但前者運(yùn)行時(shí)間和復(fù)雜度性能明顯優(yōu)于后者。

表1 算法時(shí)間復(fù)雜度

圖7 平均執(zhí)行時(shí)間比較

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

為了提高無(wú)線網(wǎng)絡(luò)中廣播傳輸?shù)膫鬏斝?，本文提出?種基于機(jī)會(huì)式網(wǎng)絡(luò)編碼的廣播傳輸算法，有效地解決此類(lèi)算法選擇數(shù)據(jù)分組復(fù)雜度高及性能不佳的問(wèn)題。在引入的無(wú)線單跳網(wǎng)絡(luò)廣播傳輸模型的基礎(chǔ)上,首先利用散列方法提出了一種高效的單組合分組廣播傳輸(ONCSB)算法，其次在采用從多個(gè)重傳分組中恢復(fù)分組丟失方法的基礎(chǔ)上提出了一種多組合分組廣播傳輸(ONCMB)算法。理論分析和仿真實(shí)驗(yàn)都說(shuō)明了ONCSB和ONCMB的有效性和可行性。

[1] KATTI S, RAHUL H S, HU W J, et al. XORs in the air: practical wireless network coding[J]. IEEE/ACM Transactions on Networking,2008, 16(3):497-510.

[2] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J].IEEE Transactions on Information Theory, 2000, 46(4):1204 -1216.

[3] HO T, MéDARD M, KOETTER R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory, 2006, 52(10):4413-4430.

[4] LE J L, LUI C S J, CHIU D M. DCAR: distributed coding-aware routing in wireless networks[J]. IEEE Transactions on Mobile Computing, 2010, 9(4):596-608.

[5] YOMO H, POPOVSKO P. Opportunistic scheduling for wireless network coding[A]. Proc 2007 IEEE International Conference on Communications[C]. Scotland, 2007.5610-5615.

[6] NGUYEN D, TRAN T, NGUYEN T, et al. Wireless broadcast using network coding[J]. IEEE Transactions on Vehicular Technology, 2009,58(2):914-925.

[7] 盧冀, 肖嵩, 吳成柯. 無(wú)線網(wǎng)絡(luò)中應(yīng)用機(jī)會(huì)式網(wǎng)絡(luò)編碼的廣播重傳方法[J]. 西安交通大學(xué)學(xué)報(bào), 2011, 45(2):68-72.LU J, XIAO S, WU C K. A broadcast retransmission method using opportunistic network coding in wireless networks[J]. Journal of Xi'an Jiaotong University, 2011, 45(2):68-72.

[8] CHOU C C, WEI H Y. Network coding based data distribution in WiMAX[A]. Proc International Conference on Mobile Data Management:Systems, Services and Middleware[C]. Taiwan, China, 2009. 393-394.

[9] 肖瀟, 王偉平, 楊路明等. 基于網(wǎng)絡(luò)編碼的無(wú)線網(wǎng)絡(luò)廣播重傳算法[J]. 通信學(xué)報(bào), 2009, 30(9): 69-75.XIAO X, WANG W P, YANG L M, et al. Wireless broadcasting retransmission approach based on network coding[J]. Journal on Communications, 2009, 30(9):69-75.

[10] FAN P Y, CHEN Z, CHEN W, et al. Reliable relay assisted wireless multicast using network coding[J]. IEEE Journal on Selected Areas in Communications, 2009, 27(5):749-762.

[11] JALALUDDIN Q, CHUAN H F, CAI J F. An efficient network coding based retransmission algorithm for wireless multicast[A]. Proc IEEE 20th International Symposium on Personal, Indoor and Mobile Radio Communications[C]. Japan, 2009. 691-695.

[12] TRAN T, NGUYEN T. A hybrid network coding technique for single-hop wireless networks[J]. IEEE Journal on Selected Areas in Communications, 2009, 27(5):685-697.

[13] YOSSEF Z B, BIRK Y, JAYRAM T S, et al. Index coding with side information[A]. IEEE Symposium on Foundations of Computer Science[C]. USA, 2006.197-206.

[14] ROUAYHEB S E, SPRINTSON A, GEORGHIADES C. On the index coding problem and its relation to network coding and matroid theory[J].IEEE Transactions on Information Theory, 2010, 56(7):3187 -3195.

[15] SOROUR S, VALAEE S. Adaptive network coded retransmission scheme for wireless multicast[A]. IEEE Symposium on Information Theory[C]. Korea, 2009.2577-2581.