基于機會式網絡編碼改進的加權廣播重傳方法

，

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

基于機會式網絡編碼改進的加權廣播重傳方法

孟利民，單劍輝

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

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

無線廣播網絡；機會式網絡編碼；重傳；優化方案

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

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

1 系統模型及基本原理

該系統模型包含一個發送數據的源節點S和N個接收數據的接收節點R={R1,R2,…,RN}，假設源節點廣播M個原始數據包P={P1,P2,…,PM}給N個接收節點.整個數據廣播過程分為兩個階段：原始數據發送階段和丟包重傳階段.

在第一階段，也就是原始數據發送階段，源節點先將M個原始數據包進行廣播，所有接收節點對每個數據包的狀態通過ACK/NCK反饋給源節點S.這里假設接收節點Ri可以在源節點S廣播數據包之后，通過接收信號的信噪比來得到鏈路的信道狀態，而且狀態信息反饋不會發生丟失.另外，假設每個接受節點和源節點之間的信道是相互獨立的，而且各鏈路丟包率在發送一個數據包的時隙內不會發生改變.

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

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

(1)

式中αi為數據包Xi編碼與否的控制因子.當αi=0時，數據包Xi不參與編碼，否則，Xi獲得參與編碼的機會.

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

解碼策略的設計是基于ONC的加權廣播重傳的關鍵所在，盡可能在每次重傳過程中都能使更多接收節點受益的情況下來降低算法時間復雜度，而且又能使重傳次數減到最少.

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

2 算法描述

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

表1 加權數據包分布矩陣(WPDM)Table 1 The weighted packet distribution matrix

圖1給出了IWONCR重傳方法的實現流程，一共分為6個步驟，具體步驟描述如下：

步驟1在初始階段，源節點將原始數據包廣播發送給所有接收節點.

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

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

步驟4使用接收端緩存容量優化選擇合適的編碼包，即在多個Hash最大值相同的組合當中根據原始包的先后順序選出總順序和最小的數據包分組，進入步驟5.

步驟5根據所選的數據包組合進行異或編碼，然后廣播給所有接收端，接收端對其進行解碼.然后繼續重復步驟2.

步驟6當所有接收端都接收到所需的數據包，源節點如果接下去還需要發送更多信息，則系統重新從步驟1開始新一輪的傳輸流程，否則整個傳輸流程結束.

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

2.1 根據WPDM生成丟失分組的Hash表

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

(2)

由式(2)算出每個丟失包的Hash值之后，按Hash值從大到小的順序創建丟失分組的Hash表，為方便后續操作，這里將Hash值作為列的索引下標.表2給出了表1所示WPDM的Hash表，其中Nhi代表索引下標為i的Hash值的丟失分組數量.

表2 丟失數據包的Hash表Table 2 The Hash Table of missing packet

2.2Hash鄰域最大值搜索

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

根據文獻[12]，當數據分組為P1,P2,…,Pn(n∈{1,2,…,M})，對應的Hash值分別為h1,h2,…,hn，當滿足

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

(3)

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

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

(4)

P1,P2,…,Pn滿足異或編碼組合的全局最大值條件，也可稱之為滿秩條件，即每個接收節點都可以從單個重傳編碼包中恢復出各自所需的丟失數據包，達到重傳收益的最大值.

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

(5)

2.3 接收端緩存容量優化

IWONCR根據數據包的影響范圍來確定數據包的重要性.IWONCR認為，在傳輸中，如果某個數據包被越少的接收端成功接收到，則該數據包在重傳階段所帶來的重傳影響也就越大，因此在重傳過程中也應該最優先發送.而當在Hash鄰域最大值搜索階段出現多個數據包或數據包組合具有相同重傳影響時，考慮到一般接收節點系統底層緩存容量的局限性，為了減少對接收節點的系統底層緩存壓力，使重傳數據包能盡早從底層緩存轉移到應用層當中，應該讓發包順序靠前的數據包優先得到編碼重傳的機會，以此來對接收端系統緩存容量進行優化，減輕接收端系統緩存的壓力.

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

3 性能分析

3.1 重傳性能

(6)

3.2 算法復雜度

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

表3 3種調度方案的時間復雜度Table 3 Time complexity of three scheduling schemes

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

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

(7)

4 仿真結果

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

4.1 平均重傳次數

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

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

4.2 計算開銷

本節對SF，WONCR，IWONCR 3種方案的運算時間進行了仿真驗證，使用的仿真計算機的CPU為Intel(R) Core(TM)i3 M380 2.53 GHz，內存為6 GB，仿真實驗軟件為Matlab R2012a.

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

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

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

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

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

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

5 結 論

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

[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] 龍勝春,龍軍.一種應用于無線傳感器網絡的數據壓縮方法[J].浙江工業大學學報,2014,42(2):210-213.

[3] 周曉,朱仁烽,趙鋒,等.基于人工蜂群算法的無線傳感器網絡路由協議[J].浙江工業大學學報,2014,42(5):577-580.

[4] 彭宏,荊晶.無線自組織量子通信網絡的Grover路由算法研究[J].浙江工業大學學報,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] 肖瀟,王偉平,楊路明,等.基于網絡編碼的無線網絡廣播重傳方法[J].通信學報,2009(9):69-75.

[11] 孫偉,張更新,邊東明,等.衛星通信中基于網絡編碼改進的廣播重傳策略[J].宇航學報,2013,34(2):231-236.

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

[13] 盧冀,肖嵩,吳成柯.一種基于機會式網絡編碼的高效廣播重

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

[14] 邵鵬飛,趙燕偉,吳耀輝,等.多播網絡中基于機會網絡編碼改進的重傳方法[J].電信科學,2015,31(4):99-106.

[15] 茍亮,張更新,孫偉,等.無線網絡中基于機會網絡編碼的加權廣播重傳[J].電子與信息學報,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

國家自然科學基金資助項目(61372087)；浙江省科技廳公益社發項目(2016C33166)

孟利民(1963—)，女，浙江金華人，教授，研究方向為無線通信與網絡多媒體數字通信，E-mail：mlm@zjut.edu.cn.

TP393

A

1006-4303(2017)06-0621-07

(責任編輯：陳石平)