基于機(jī)會(huì)式網(wǎng)絡(luò)編碼改進(jìn)的加權(quán)廣播重傳方法

，

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

基于機(jī)會(huì)式網(wǎng)絡(luò)編碼改進(jìn)的加權(quán)廣播重傳方法

孟利民，單劍輝

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

針對(duì)在無線廣播網(wǎng)絡(luò)鏈路狀態(tài)不同和丟包率較高的情況下，WONCR(Weighted opportunistic network coding retransmission)等重傳方法存在計(jì)算復(fù)雜度高的問題，提出了一種經(jīng)過改進(jìn)的基于機(jī)會(huì)網(wǎng)絡(luò)編碼的加權(quán)廣播重傳方法.該方法先根據(jù)接收端的反饋信息構(gòu)建加權(quán)數(shù)據(jù)包狀態(tài)矩陣，然后根據(jù)狀態(tài)矩陣創(chuàng)建丟包的Hash表，最后通過Hash鄰域最大值搜索和接收端緩存優(yōu)化快速選擇滿足一定編碼條件的丟包組合通過異或生成編碼包進(jìn)行重傳，從而在保持較高重傳性能的同時(shí)，有效降低了重傳方法的時(shí)間復(fù)雜度和接收端所需的緩存容量.仿真結(jié)果表明相比已有算法有較低的時(shí)間復(fù)雜度，能有效地減少計(jì)算開銷和接收端的緩存壓力，大大提高實(shí)用性.

無線廣播網(wǎng)絡(luò)；機(jī)會(huì)式網(wǎng)絡(luò)編碼；重傳；優(yōu)化方案

網(wǎng)絡(luò)編碼(Network coding，NC)概念于2000年首次提出[1]，中轉(zhuǎn)節(jié)點(diǎn)通過對(duì)多條有關(guān)鏈路的數(shù)據(jù)流進(jìn)行編碼形成一個(gè)單獨(dú)的編碼數(shù)據(jù)流，接收節(jié)點(diǎn)可利用數(shù)據(jù)流之間的相關(guān)性來解碼.與傳統(tǒng)節(jié)點(diǎn)對(duì)數(shù)據(jù)包僅進(jìn)行“存儲(chǔ)轉(zhuǎn)發(fā)”的方式不同，它可以提升網(wǎng)絡(luò)的傳輸性能，使網(wǎng)絡(luò)多播信息流達(dá)到最大流最小割定理(Max-flow min cut theorem)所述的理論值上界.無線網(wǎng)絡(luò)隨著它的普及得到了業(yè)內(nèi)越來越多的關(guān)注，近些年以來有許多基于無線網(wǎng)絡(luò)的研究出現(xiàn)[2-4].其中，無線網(wǎng)絡(luò)具有有線網(wǎng)絡(luò)所不具備的天然的廣播特性，也正是由于該特性為網(wǎng)絡(luò)編碼理論的應(yīng)用提供了比較有利的條件，因此國內(nèi)外有越來越多的研究者開始將無線網(wǎng)絡(luò)和網(wǎng)絡(luò)編碼兩者結(jié)合起來進(jìn)行研究并得到了許多研究結(jié)果.而在這些研究結(jié)果當(dāng)中，機(jī)會(huì)式網(wǎng)絡(luò)編碼(Opportunistic network coding，ONC)方案[5]由于只需要進(jìn)行異或操作就可以完成編解碼，具有復(fù)雜度低、高效率的特點(diǎn)，逐漸成為了主流，取得了許多研究成果[6-8].文獻(xiàn)[9]提出了將ONC與自動(dòng)重傳請(qǐng)求(Automatic repeat request，ARQ)相結(jié)合的重傳策略.文獻(xiàn)[10]提出了一種基于網(wǎng)絡(luò)編碼的廣播重傳(Network coding wireless broadcasting retransmission，NCWBR)方法，該方法相比于傳統(tǒng)的ARQ能相對(duì)減少所需的平均傳輸次數(shù)并提高傳輸性能，但其存在著重傳編碼包無法每次都被所有接收節(jié)點(diǎn)解碼和丟失成塊數(shù)據(jù)包時(shí)傳輸性能惡化的問題.針對(duì)NCWBR的不可解碼問題，文獻(xiàn)[11]提出了一種改進(jìn)的重傳策略(Improved network-coding-based broadcasting retransmission，INCBR)，但該方法雖解決了不可解的問題，卻并未對(duì)丟失數(shù)據(jù)包的選擇進(jìn)行優(yōu)化.文獻(xiàn)[12]從多發(fā)送端多接收端的角度出發(fā)，提出了一種應(yīng)用于多發(fā)-多收網(wǎng)絡(luò)的重傳方案(Network coding wireless retransmission mechanism，NCWRM)，在該算法中每個(gè)節(jié)點(diǎn)既可以是發(fā)送者也可以是接收者，因此該方案的情況更一般化，但該方案的缺陷是會(huì)使中心度較高的節(jié)點(diǎn)能耗較大.文獻(xiàn)[13]從改善選包策略的角度提出(Hash lookup assisted retransmission，HLAR)，該方法利用散列組合進(jìn)行選包，能更快地尋找到合適的丟失分組進(jìn)行編碼并降低平均傳輸次數(shù)，但其將編碼包的重傳過程理想化了，未考慮重傳編碼包在重傳過程中出現(xiàn)的再丟失問題.文獻(xiàn)[14]在HLAR的基礎(chǔ)上提出了一種改進(jìn)的基于機(jī)會(huì)網(wǎng)絡(luò)編碼的重傳(Improved opportunistic network coding retransmission，IONCR)方法，其在保持較低算法復(fù)雜度的情況下挖掘了丟失數(shù)據(jù)包更多的編碼機(jī)會(huì)，提高了丟失包的編碼率，但該方案需要接收節(jié)點(diǎn)緩存額外的重傳編碼包，對(duì)接收節(jié)點(diǎn)的存儲(chǔ)資源不夠友好，無法適用于一些設(shè)備存儲(chǔ)資源比較有限的場(chǎng)景.不同于文獻(xiàn)[10-14]，茍亮等[15]從每個(gè)節(jié)點(diǎn)接收鏈路數(shù)據(jù)丟失率不同的角度出發(fā)，提出了一種基于機(jī)會(huì)網(wǎng)絡(luò)編碼的加權(quán)廣播重傳算法(Weighted opportunistic network coding retransmission，WONCR)，該方法對(duì)減少重傳次數(shù)的問題進(jìn)行了轉(zhuǎn)化，將其變?yōu)榛诩訖?quán)的接收節(jié)點(diǎn)的最大增益問題，即讓每次重傳都能使盡可能多的接收節(jié)點(diǎn)受益，但該方案的加權(quán)數(shù)據(jù)包調(diào)度算法采用逐行逐列尋找，其時(shí)間復(fù)雜度較高，而且也未對(duì)接收端的緩存容量進(jìn)行優(yōu)化，因此在現(xiàn)實(shí)場(chǎng)景當(dāng)中應(yīng)用有較大限制.

為了更好的在各節(jié)點(diǎn)接收鏈路分組丟失率不同的情況下保持較高重傳方法性能，降低其數(shù)據(jù)包調(diào)度算法的時(shí)間復(fù)雜度，并且保證在每次重傳收益最大的情況下使接收端平均所需緩存容量最小，在WONCR等方法的基礎(chǔ)上，提出了一種基于機(jī)會(huì)網(wǎng)絡(luò)編碼改進(jìn)的加權(quán)廣播重傳(Improved-WONCR，IWONCR)方法.其基本思想是在WONCR的基礎(chǔ)上采用Hash鄰域最大值搜索和接收端緩存容量優(yōu)化來快速選擇丟失數(shù)據(jù)包組合進(jìn)行編碼重傳從而降低加權(quán)數(shù)據(jù)包調(diào)度算法的復(fù)雜度和優(yōu)化接收端平均所需緩存容量.

1 系統(tǒng)模型及基本原理

該系統(tǒng)模型包含一個(gè)發(fā)送數(shù)據(jù)的源節(jié)點(diǎn)S和N個(gè)接收數(shù)據(jù)的接收節(jié)點(diǎn)R={R1,R2,…,RN}，假設(shè)源節(jié)點(diǎn)廣播M個(gè)原始數(shù)據(jù)包P={P1,P2,…,PM}給N個(gè)接收節(jié)點(diǎn).整個(gè)數(shù)據(jù)廣播過程分為兩個(gè)階段：原始數(shù)據(jù)發(fā)送階段和丟包重傳階段.

在第一階段，也就是原始數(shù)據(jù)發(fā)送階段，源節(jié)點(diǎn)先將M個(gè)原始數(shù)據(jù)包進(jìn)行廣播，所有接收節(jié)點(diǎn)對(duì)每個(gè)數(shù)據(jù)包的狀態(tài)通過ACK/NCK反饋給源節(jié)點(diǎn)S.這里假設(shè)接收節(jié)點(diǎn)Ri可以在源節(jié)點(diǎn)S廣播數(shù)據(jù)包之后，通過接收信號(hào)的信噪比來得到鏈路的信道狀態(tài)，而且狀態(tài)信息反饋不會(huì)發(fā)生丟失.另外，假設(shè)每個(gè)接受節(jié)點(diǎn)和源節(jié)點(diǎn)之間的信道是相互獨(dú)立的，而且各鏈路丟包率在發(fā)送一個(gè)數(shù)據(jù)包的時(shí)隙內(nèi)不會(huì)發(fā)生改變.

在第二階段，也就是丟包重傳階段，源節(jié)點(diǎn)根據(jù)接收節(jié)點(diǎn)反饋的丟包信息，通過某種調(diào)度算法來選擇不同接收節(jié)點(diǎn)的丟包進(jìn)行異或編碼，然后將編碼包再次發(fā)送出去.接收節(jié)點(diǎn)收到重傳的編碼包之后，通過異或運(yùn)算從該編碼包和已接收的數(shù)據(jù)包中恢復(fù)出所需的丟失數(shù)據(jù)包信息.然后不斷重復(fù)此過程，直到接收節(jié)點(diǎn)都收到了所有數(shù)據(jù)包.這里假設(shè)接收節(jié)點(diǎn)系統(tǒng)只有在底層緩存的數(shù)據(jù)包可用的情況下才會(huì)將數(shù)據(jù)包從底層緩存中移至應(yīng)用層中，即當(dāng)?shù)趉個(gè)數(shù)據(jù)包到達(dá)時(shí)，只有當(dāng)數(shù)據(jù)包Pi(i∈{1,2,…,k-1})都正確接收到且不會(huì)再用于重傳包解碼的情況下，Pk才會(huì)被系統(tǒng)從底層緩存中移至應(yīng)用層當(dāng)中，如果前面存在丟包，則這個(gè)包也只能暫時(shí)保存在底層緩存當(dāng)中.

假設(shè)被選擇的丟失數(shù)據(jù)包為X1,X2,…,Xt，其中Xi(1≤i≤t)長度為l，y表示一個(gè)編碼組合，分別用二進(jìn)制序列表示為[xi1,…,xij,…,xil]和[y1,…,yj,…,yl]，從而采用ONC生成的廣播重傳分組序列的某一數(shù)據(jù)包可以描述為

(1)

式中αi為數(shù)據(jù)包Xi編碼與否的控制因子.當(dāng)αi=0時(shí)，數(shù)據(jù)包Xi不參與編碼，否則，Xi獲得參與編碼的機(jī)會(huì).

由于單個(gè)重傳編碼包中包含一個(gè)或多個(gè)原始丟失數(shù)據(jù)包，多個(gè)接收節(jié)點(diǎn)可以從該重傳數(shù)據(jù)包中通過異或解碼恢復(fù)得到各自的丟失數(shù)據(jù)包.因此可以得出：基于ONC的廣播重傳方法相對(duì)于傳統(tǒng)的ARQ方法能有效減少重傳次數(shù).在每條鏈路損耗都不同的情況下，尋找丟失數(shù)據(jù)包組合的算法以及編

解碼策略的設(shè)計(jì)是基于ONC的加權(quán)廣播重傳的關(guān)鍵所在，盡可能在每次重傳過程中都能使更多接收節(jié)點(diǎn)受益的情況下來降低算法時(shí)間復(fù)雜度，而且又能使重傳次數(shù)減到最少.

IWONCR是基于WONCR的廣播重傳，其核心思想是在保持每次重傳都能讓最多的接收節(jié)點(diǎn)受益以及盡可能減少平均重傳次數(shù)的情況下，進(jìn)一步降低算法的時(shí)間復(fù)雜度，并減少接收端的緩存壓力.

2 算法描述

WPDM是指在原始數(shù)據(jù)傳輸之后，源節(jié)點(diǎn)通過ACK/NCK的方式收集各接收節(jié)點(diǎn)反饋的數(shù)據(jù)包狀態(tài)信息和鏈路狀態(tài)信息所形成的列表[15].該列表是一個(gè)N×M的矩陣，行系數(shù)和列系數(shù)分別代表各個(gè)接收節(jié)點(diǎn)和數(shù)據(jù)包，數(shù)據(jù)包元素在矩陣中用wi,j(0≤wi,j≤1;i=1,2,…,N;j=1,2,…,M)來進(jìn)行表示.假設(shè)wi,j=1-pi>0，則代表接收節(jié)點(diǎn)Ri沒有成功接收到數(shù)據(jù)包Pj，且接收節(jié)點(diǎn)Ri和源節(jié)點(diǎn)S之間的通信鏈路成功傳輸概率為1-pi，其中pi為接收節(jié)點(diǎn)Ri和源節(jié)點(diǎn)S之間通信鏈路的丟包率；如果wi,j=0，則說明Ri已經(jīng)成功接收到數(shù)據(jù)包Pj.表1給出了一個(gè)3個(gè)接收節(jié)點(diǎn)和10個(gè)原始數(shù)據(jù)包的WPDM示例.

表1 加權(quán)數(shù)據(jù)包分布矩陣(WPDM)Table 1 The weighted packet distribution matrix

圖1給出了IWONCR重傳方法的實(shí)現(xiàn)流程，一共分為6個(gè)步驟，具體步驟描述如下：

步驟1在初始階段，源節(jié)點(diǎn)將原始數(shù)據(jù)包廣播發(fā)送給所有接收節(jié)點(diǎn).

步驟2在初始傳輸階段或某次重傳結(jié)束之后，通過ACK/NCK更新接收狀態(tài)表，根據(jù)WPDM矩陣是否為全“0”矩陣來判斷是否所有數(shù)據(jù)分組都被節(jié)點(diǎn)正確接收，如果是，則表示所有數(shù)據(jù)分組都被各接收節(jié)點(diǎn)正確接收，不需要再進(jìn)行重傳，直接進(jìn)入步驟6；否則進(jìn)入步驟3繼續(xù)執(zhí)行.

步驟3根據(jù)WPDM計(jì)算所有丟失數(shù)據(jù)包的Hash值，并生成丟失數(shù)據(jù)包的Hash列表(Hash table).然后利用Hash值通過Hash鄰域最大值搜索來快速尋找合適的第i次重傳的丟失數(shù)據(jù)包組合.判斷第i次的Hash最大值的數(shù)據(jù)包組合是否唯一，若是，則轉(zhuǎn)到步驟5繼續(xù)執(zhí)行；如果不是，則進(jìn)入步驟4進(jìn)行接收端緩存容量優(yōu)化環(huán)節(jié).

步驟4使用接收端緩存容量優(yōu)化選擇合適的編碼包，即在多個(gè)Hash最大值相同的組合當(dāng)中根據(jù)原始包的先后順序選出總順序和最小的數(shù)據(jù)包分組，進(jìn)入步驟5.

步驟5根據(jù)所選的數(shù)據(jù)包組合進(jìn)行異或編碼，然后廣播給所有接收端，接收端對(duì)其進(jìn)行解碼.然后繼續(xù)重復(fù)步驟2.

步驟6當(dāng)所有接收端都接收到所需的數(shù)據(jù)包，源節(jié)點(diǎn)如果接下去還需要發(fā)送更多信息，則系統(tǒng)重新從步驟1開始新一輪的傳輸流程，否則整個(gè)傳輸流程結(jié)束.

圖1 IWONCR方法流程Fig.1 IWONCR algorithm flow

2.1 根據(jù)WPDM生成丟失分組的Hash表

WPDM里的第i列表示數(shù)據(jù)分組Pj(1≤i≤M)在N個(gè)節(jié)點(diǎn)接收丟失分組的情況.為了在搜索階段能夠快速通過鄰域來搜索，需要保證當(dāng)接收節(jié)點(diǎn)在丟失數(shù)據(jù)包Pj的情況不一樣時(shí)其對(duì)應(yīng)Hash值大小也不一樣，否則其對(duì)應(yīng)的Hash值大小相同，IWONCR采用Hash函數(shù)h計(jì)算每一個(gè)丟失數(shù)據(jù)包的Hash值，h表示為

(2)

由式(2)算出每個(gè)丟失包的Hash值之后，按Hash值從大到小的順序創(chuàng)建丟失分組的Hash表，為方便后續(xù)操作，這里將Hash值作為列的索引下標(biāo).表2給出了表1所示W(wǎng)PDM的Hash表，其中Nhi代表索引下標(biāo)為i的Hash值的丟失分組數(shù)量.

表2 丟失數(shù)據(jù)包的Hash表Table 2 The Hash Table of missing packet

2.2Hash鄰域最大值搜索

根據(jù)丟失分組的Hash表，IWONCR在鄰域范圍通過最大值搜索符合條件的丟失數(shù)據(jù)包組合，如果組合唯一則進(jìn)行編碼重傳，否則需要進(jìn)行接收端緩存容量優(yōu)化選擇來選出進(jìn)行重傳的編碼包組合.當(dāng)所有的丟失數(shù)據(jù)包都被搜索完成之后，此步驟完成.鄰域搜索相對(duì)于一般的逐行逐列的掃描判斷，極大地縮小了搜索的范圍，大大降低了搜索過程所需的時(shí)間，提高了搜索效率.同時(shí)，IWONCR優(yōu)先重傳能讓更多節(jié)點(diǎn)恢復(fù)其丟失數(shù)據(jù)包的編碼組合，也就是讓每次的重傳收益最大化.

根據(jù)文獻(xiàn)[12]，當(dāng)數(shù)據(jù)分組為P1,P2,…,Pn(n∈{1,2,…,M})，對(duì)應(yīng)的Hash值分別為h1,h2,…,hn，當(dāng)滿足

Fi(h1,h2,…,hn)≤1i=1,2,…,N

(3)

由P1,P2,…,Pn編碼組合而成的數(shù)據(jù)分組對(duì)所有接收節(jié)點(diǎn)可解，其中Fi表示全部hj(1≤j≤n)用二進(jìn)制表示下其第i比特之和.特別的，當(dāng)滿足

Fi(h1,h2,…,hn)=1i=1,2,…,N

(4)

P1,P2,…,Pn滿足異或編碼組合的全局最大值條件，也可稱之為滿秩條件，即每個(gè)接收節(jié)點(diǎn)都可以從單個(gè)重傳編碼包中恢復(fù)出各自所需的丟失數(shù)據(jù)包，達(dá)到重傳收益的最大值.

集合U表示Hash值h1,h2,…,hn(n∈{1,2,…,M})的鄰域，U表示為

(5)

2.3 接收端緩存容量優(yōu)化

IWONCR根據(jù)數(shù)據(jù)包的影響范圍來確定數(shù)據(jù)包的重要性.IWONCR認(rèn)為，在傳輸中，如果某個(gè)數(shù)據(jù)包被越少的接收端成功接收到，則該數(shù)據(jù)包在重傳階段所帶來的重傳影響也就越大，因此在重傳過程中也應(yīng)該最優(yōu)先發(fā)送.而當(dāng)在Hash鄰域最大值搜索階段出現(xiàn)多個(gè)數(shù)據(jù)包或數(shù)據(jù)包組合具有相同重傳影響時(shí)，考慮到一般接收節(jié)點(diǎn)系統(tǒng)底層緩存容量的局限性，為了減少對(duì)接收節(jié)點(diǎn)的系統(tǒng)底層緩存壓力，使重傳數(shù)據(jù)包能盡早從底層緩存轉(zhuǎn)移到應(yīng)用層當(dāng)中，應(yīng)該讓發(fā)包順序靠前的數(shù)據(jù)包優(yōu)先得到編碼重傳的機(jī)會(huì)，以此來對(duì)接收端系統(tǒng)緩存容量進(jìn)行優(yōu)化，減輕接收端系統(tǒng)緩存的壓力.

每一次搜索中，在丟失包的Hash表中IWONCR優(yōu)先尋找滿足式(4)Hash值或Hash值組合(所有接收端都可從編碼中收益)，當(dāng)找不到滿秩條件的Hash組合時(shí)再尋找滿足式(3)條件下的最大值組合，使重傳收益最大化.當(dāng)出現(xiàn)多個(gè)Hash值或Hash值組合最大值相同的數(shù)據(jù)包或數(shù)據(jù)包組合時(shí)，就根據(jù)接收端緩存容量優(yōu)化的原則選擇數(shù)據(jù)包索引之和更小的.由于在鄰域范圍中搜索Hash值，可以大幅度排除不符合條件的丟失數(shù)據(jù)包，縮小數(shù)據(jù)包搜索的范圍，從而提高了數(shù)據(jù)包組合的搜索效率.在選擇了一組Hash值之后，將對(duì)應(yīng)的數(shù)據(jù)包進(jìn)行編碼組合成重傳編碼包.以表2所示的Hash表為例，P8為所有接收端都成功接收的數(shù)據(jù)包，因此無需重傳.IWONCR首先選最大的Hash值7，對(duì)應(yīng)的數(shù)據(jù)包P1直接符合滿秩條件，因此進(jìn)行單獨(dú)傳輸.接著，搜索找到P5和P7，P2和P3，P4和P6三個(gè)組合包也符合滿秩條件，因?yàn)樽畲笾挡晃ㄒ?，因此進(jìn)行接收端緩存優(yōu)化處理，因此重傳的順序是P2和P3，P4和P6，P5和P7.最后將剩余不滿足滿秩條件的丟失包按照滿足式(3)條件下的Hash值或Hash值組合從大到小進(jìn)行編碼重傳，也就是單獨(dú)重傳P9和P10.

3 性能分析

3.1 重傳性能

(6)

3.2 算法復(fù)雜度

本小節(jié)還是假設(shè)丟失包的個(gè)數(shù)為M個(gè)，為作比較，將傳統(tǒng)的存儲(chǔ)轉(zhuǎn)發(fā)方法加入討論，記為SF，由于其每次都直接對(duì)丟失包進(jìn)行單獨(dú)重傳，單獨(dú)重傳一個(gè)編碼包的復(fù)雜度為O(1)，因此其時(shí)間復(fù)雜度為M·O(1)=O(M)級(jí)別.WONCR調(diào)度算法將在重傳階段尋找所有的M2個(gè)包的組合，因此該算法的時(shí)間復(fù)雜度為O(M2)級(jí)別.IWONCR調(diào)度算法的過程：1) 計(jì)算一個(gè)數(shù)據(jù)包Hash值的復(fù)雜度O(1)，因此構(gòu)建Hash表的時(shí)間復(fù)雜度為M·O(1)=O(M)；2) 在Hash表當(dāng)中根據(jù)不同的Hash值來搜索一個(gè)數(shù)據(jù)包的時(shí)間復(fù)雜度為常數(shù)級(jí)別O(1)，因此從M個(gè)數(shù)據(jù)包中搜索選取所有丟失數(shù)據(jù)包的組合的時(shí)間復(fù)雜度為O(M).由此可以得出：IWONCR算法總的時(shí)間復(fù)雜度為O(M)+O(M)=O(M)級(jí)別，具體如表3所示.

表3 3種調(diào)度方案的時(shí)間復(fù)雜度Table 3 Time complexity of three scheduling schemes

3.3 接收端平均所需緩存容量

假設(shè)系統(tǒng)能實(shí)時(shí)地將底層緩存當(dāng)中正確接收的滿足轉(zhuǎn)移要求的數(shù)據(jù)包移到應(yīng)用層中，而且只考慮單一源節(jié)點(diǎn)發(fā)送數(shù)據(jù)的情況.在原始數(shù)據(jù)包傳輸階段傳輸了M個(gè)數(shù)據(jù)包之后，各接收端分別有Mpi個(gè)數(shù)據(jù)包未成功接收到.當(dāng)所有的丟包都連續(xù)出現(xiàn)在數(shù)據(jù)包序列的最后部分時(shí)達(dá)到理想情況下的最小所需緩存容量為Mpmax，同樣假設(shè)每一次重傳都能使每個(gè)接收端都能恢復(fù)出一個(gè)丟失數(shù)據(jù)包，因此可得理想情況下最小的接收端平均所需緩存容量(Average required cache size，ARCS)為

(7)

4 仿真結(jié)果

為了驗(yàn)證筆者提出的IWONCR方案的有效性，本節(jié)對(duì)SF，WONCR，IWONCR 3個(gè)方案的平均重傳次數(shù)和時(shí)間復(fù)雜度進(jìn)行了仿真實(shí)驗(yàn).假設(shè)通信鏈路的平均丟包率為μ，各接收節(jié)點(diǎn)與源節(jié)點(diǎn)與之間的鏈路丟包率均勻分布在[μ-0.1,μ+0.1]范圍內(nèi).經(jīng)過500次的仿真，得出了3種方案的平均重傳次數(shù)和計(jì)算開銷，并對(duì)它們進(jìn)行了比較.

4.1 平均重傳次數(shù)

當(dāng)接收節(jié)點(diǎn)個(gè)數(shù)N=5，鏈路平均丟包率μ=0.3時(shí)，圖2(a)給出了各方案的平均重傳次數(shù)隨數(shù)據(jù)包數(shù)量變化的關(guān)系.WONCR，IWONCR兩個(gè)方案的平均重傳次數(shù)都要遠(yuǎn)小于傳統(tǒng)的SF方案；隨著數(shù)據(jù)包數(shù)量的增加，SF，WONCR，IWONCR 3個(gè)方案的平均重傳次數(shù)都大致呈線性的增加，而且WONCR，IWONCR的增長幅度要明顯小于SF方案，這是因?yàn)殡S著數(shù)據(jù)包的增加丟失數(shù)據(jù)包滿足式(4)的編碼組合也開始變多；WONCR，IWONCR方案的平均重傳次數(shù)都比較接近于理論上的最少重傳次數(shù).當(dāng)數(shù)據(jù)包數(shù)量M=100，接收節(jié)點(diǎn)個(gè)數(shù)N=5時(shí)，圖2(b)給出了各方案的平均重傳次數(shù)隨丟包率變化的關(guān)系.這里可以看出：3個(gè)方案的平均重傳次數(shù)都隨著丟包率的增加而快速增加；WONCR，IWONCR方案的性能要好于SF方案，更接近于理論上的最小重傳次數(shù)，但隨著平均丟包率的增加，WONCR，IWONCR的曲線都逐漸向SF靠攏，這是因?yàn)楫?dāng)鏈路的平均丟包率μ接近1時(shí)，也就是當(dāng)信道完全不可用的時(shí)候，不管SF，WONCR還是IWONCR的平均重傳次數(shù)都趨向無窮大.

圖2 各情況下的重傳次數(shù)比較Fig.2 The number of retransmissions in each case

4.2 計(jì)算開銷

本節(jié)對(duì)SF，WONCR，IWONCR 3種方案的運(yùn)算時(shí)間進(jìn)行了仿真驗(yàn)證，使用的仿真計(jì)算機(jī)的CPU為Intel(R) Core(TM)i3 M380 2.53 GHz，內(nèi)存為6 GB，仿真實(shí)驗(yàn)軟件為Matlab R2012a.

圖3(a)給出了當(dāng)接收節(jié)點(diǎn)個(gè)數(shù)N=5，鏈路平均丟包率μ=0.3時(shí)，3種方案的運(yùn)算時(shí)間隨數(shù)據(jù)包數(shù)目變化的比較曲線.由于SF方案不需要編碼包的選取，直接重傳的時(shí)間消耗非常小，導(dǎo)致該方案在數(shù)據(jù)包數(shù)量變化和丟包率變化下的影響可忽略不計(jì)，因此在這里我們主要比較WONCR，IWONCR這2種方案.從圖3(a)里可以看出：2種方案的運(yùn)算時(shí)間均隨著數(shù)據(jù)包數(shù)目及丟包率的增大而增大.但WONCR方案的運(yùn)算時(shí)間增長速度隨數(shù)據(jù)包的增加變得越來越快，基本與數(shù)據(jù)包的增加呈平方關(guān)系，而IWONCR方案的運(yùn)算時(shí)間要遠(yuǎn)遠(yuǎn)低于WONCR方案，且大致與數(shù)據(jù)包數(shù)目呈線性關(guān)系，這也與第3節(jié)當(dāng)中對(duì)時(shí)間復(fù)雜度的理論分析相吻合.圖3(b)給出了當(dāng)數(shù)據(jù)包數(shù)量M=100，接收節(jié)點(diǎn)個(gè)數(shù)N=5時(shí)，3種方案的運(yùn)算時(shí)間隨平均丟包率變化的比較曲線.從圖3(b)可以看出：在丟包率變大的情況下，IWONCR，WONCR的運(yùn)算時(shí)間都隨之增長，但是IWONCR方案的運(yùn)算時(shí)間和增長幅度都要比WONCR方案小的多.

圖3 各情況下的計(jì)算開銷比較Fig.3 The computational cost in each case

4.3 接收端平均所需緩存容量

圖4(a)給出了當(dāng)接收節(jié)點(diǎn)個(gè)數(shù)N=5，鏈路平均丟包率μ=0.3時(shí)，3種方案的接收端平均所需緩存容量隨數(shù)據(jù)包數(shù)目變化的比較關(guān)系.由于SF采用丟一個(gè)重傳一個(gè)的策略，因此該方案不受數(shù)據(jù)包數(shù)量和平均丟包率變化的影響始終為1個(gè)數(shù)據(jù)包的緩存容量.從圖4(a)可以看出：WONCR，IWONCR方案的平均所需緩存容量都隨著數(shù)據(jù)包數(shù)目的增加而增加，但由于IWONCR在選包過程中針對(duì)緩存容量進(jìn)行了優(yōu)化，因此平均所需容量要比WONCR小.圖4(b)給出了當(dāng)數(shù)據(jù)包數(shù)量M=100，接收節(jié)點(diǎn)個(gè)數(shù)N=5時(shí)，3種方案隨著平均丟包率變化的比較關(guān)系.可以看出：WONCR，IWONCR都隨著平均丟包率的增大而增大；在所有情況下，IWONCR都比WONCR的接收端平均所需緩存容量要小.

圖4 各情況下的平均所需緩存容量比較Fig.4 The average cache capacity in each case

由以上仿真可以看出：WONCR方案的傳輸效率相較于傳統(tǒng)SF方案要高許多，但計(jì)算復(fù)雜度較高，且在選包策略上并未針對(duì)接收端緩存容量進(jìn)行優(yōu)化，因此在一些計(jì)算資源和系統(tǒng)底層緩存資源受限制的系統(tǒng)上實(shí)用性不強(qiáng)；經(jīng)過改進(jìn)的IWONCR方案在傳輸效率上與WONCR方案基本保持一致，但其計(jì)算開銷和接收端平均所需緩存容量都要低于WONCR方案，因此具有更高的使用價(jià)值.

5 結(jié) 論

該方案在WONCR方案的基礎(chǔ)上通過使用WPDM矩陣，利用Hash表和接收端緩存容量優(yōu)化進(jìn)行重傳編碼包的調(diào)度，以此提高計(jì)算效率和減輕對(duì)接收端的底層緩存壓力.通過理論分析和仿真表明：改進(jìn)之后的方案可以在保證與WONCR方案相同傳輸效率的同時(shí)降低計(jì)算時(shí)間復(fù)雜度和減少接收端平均所需緩存容量，減小接收節(jié)點(diǎn)的處理負(fù)荷和緩存壓力，使在各鏈路丟包率不同的情況下基于機(jī)會(huì)式網(wǎng)絡(luò)編碼的無線廣播重傳算法性能得到了比較大的提升，使其能夠應(yīng)用到一些接收節(jié)點(diǎn)性能和資源受限的場(chǎng)景當(dāng)中，譬如，衛(wèi)星廣播網(wǎng)、無線傳感器網(wǎng)絡(luò)等系統(tǒng)，具有較高的應(yīng)用價(jià)值.

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

[2] 龍勝春,龍軍.一種應(yīng)用于無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)壓縮方法[J].浙江工業(yè)大學(xué)學(xué)報(bào),2014,42(2):210-213.

[3] 周曉,朱仁烽,趙鋒,等.基于人工蜂群算法的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].浙江工業(yè)大學(xué)學(xué)報(bào),2014,42(5):577-580.

[4] 彭宏,荊晶.無線自組織量子通信網(wǎng)絡(luò)的Grover路由算法研究[J].浙江工業(yè)大學(xué)學(xué)報(bào),2014,42(6):612-615.

[5] KATTI S, RAHUL H, HU W, et al. XORs in the air: practical wireless network coding[C]//ACM SIGCOMM Computer Communication Review. Pisa: ACM,2006:243-254.

[6] WANG Y, ZHANG Q. An approach on wireless broadcasting retransmission using network coding[C]//Wireless Communications, Networking and Mobile Computing (WiCOM), 2012 8th International Conference on Wireless Commucation. Shanghai: IEEE,2012:1-4.

[7] GONG D, YANG Y, LI H. An efficient cooperative retransmission MAC protocol for IEEE 802.11 n Wireless LANs[C]//2013 IEEE 10th International Conference on Mobile Ad-Hoc and Sensor Systems. Beijing: IEEE,2013:191-199.

[8] GO K C, CHA J R, OH S K, et al. End-to-end performance analysis based on cross-layer retransmission scheme in wireless communication system[C]//The International Conference on Information Networking 2013 (ICOIN). Bangkok: IEEE,2013:141-144.

[9] NGUYEN D, TRAN T, NGUYEN T, et al. Wireless broadcast using network coding[J]. IEEE transactions on vehicular technology,2009,58(2):914-925.

[10] 肖瀟,王偉平,楊路明,等.基于網(wǎng)絡(luò)編碼的無線網(wǎng)絡(luò)廣播重傳方法[J].通信學(xué)報(bào),2009(9):69-75.

[11] 孫偉,張更新,邊東明,等.衛(wèi)星通信中基于網(wǎng)絡(luò)編碼改進(jìn)的廣播重傳策略[J].宇航學(xué)報(bào),2013,34(2):231-236.

[12] 劉期烈,吳陽陽,曹儐.無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的重傳機(jī)制[J].計(jì)算機(jī)應(yīng)用,2014,34(2):309-312.

[13] 盧冀,肖嵩,吳成柯.一種基于機(jī)會(huì)式網(wǎng)絡(luò)編碼的高效廣播重

傳方法[J].電子與信息學(xué)報(bào),2011,33(4):858-863.

[14] 邵鵬飛,趙燕偉,吳耀輝,等.多播網(wǎng)絡(luò)中基于機(jī)會(huì)網(wǎng)絡(luò)編碼改進(jìn)的重傳方法[J].電信科學(xué),2015,31(4):99-106.

[15] 茍亮,張更新,孫偉,等.無線網(wǎng)絡(luò)中基于機(jī)會(huì)網(wǎng)絡(luò)編碼的加權(quán)廣播重傳[J].電子與信息學(xué)報(bào),2014,36(3):749-753.

[16] SOROUR S, VALAEE S. Adaptive network coded retransmission scheme for wireless multicast[C]//2009 IEEE International Symposium on Information Theory. Seoul: IEEE,2009:2577-2581.

Animprovedweightedbroadcastingretransmissionmethodbasedonopportunisticnetworkcodinginwirelessnetworks

MENG Limin, SHAN Jianhui

(College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China)

The weighted opportunistic network coding retransmission (WONCR) has high computational complexity in the case of different link state and high packet loss rate of wireless broadcast networks. To solve this problem, this paper proposes an improved weighted broadcast retransmission scheme based on opportunistic network coding. The scheme first constructs a weighted packet status matrix based on the feedback information of the receivers, and then creates a lost Hash table according to the matrix. Finally, according to the Hash table, the Hash neighborhood maximum search and the receiver cache optimization are used to quickly select ta packet loss combination that satisfies certain coding conditions. Then an encoding packet generated by XOR is retransmitted. It can reduce the time complexity of the retransmission scheme and the cache capacity of the receiver while maintaining high retransmission performance. The simulation results show that this method has lower time complexity compared to the existing algorithms, and can effectively reduce the computational overhead and the cache pressure of the receiver, greatly improve the usability.

wireless broadcasting network; opportunistic network coding; retransmission; optimal scheme

2016-12-23

國家自然科學(xué)基金資助項(xiàng)目(61372087)；浙江省科技廳公益社發(fā)項(xiàng)目(2016C33166)

孟利民(1963—)，女，浙江金華人，教授，研究方向?yàn)闊o線通信與網(wǎng)絡(luò)多媒體數(shù)字通信，E-mail：mlm@zjut.edu.cn.

TP393

A

1006-4303(2017)06-0621-07

(責(zé)任編輯：陳石平)