基于机会式网络编码的高效广播传输算法

卢冀，吴成柯，肖嵩，张冉

(1. 中国电科集团第54研究所，河北 石家庄 050081；

2. 通信网信息传输与分发技术重点实验室，河北 石家庄 050081；

3. 西安电子科技大学 ISN重点实验室，陕西 西安 710071；

4. 中国电科集团第27研究所，河南 郑州 450005)

1 引言

机会式网络编码(ONC, opportunistic network coding)[1]是应用于无线网络的一种随机线性网络编码[2,3]方法。ONC因在提高无线信息传输效率[4]和吞吐量[5]方面具有明显的优越性而得到广大研究人员的青睐。

在无线广播网络中，信道拥塞和衰落等因素造成的数据分组丢失会导致广播传输性能的下降，通常采用自动重传请求(ARQ)方法或前向纠错(FEC)的传统方法提高广播传输的性能。ONC为提高广播传输性能提供了新思路，Nguyen等[6]在理论上证明了基于ONC传输方式的广播传输效率明显优于传统方法，因此如何构造高效的编码算法成为关键问题。已有的方法可以分为3类：第1类是针对如何对分组丢失进行编码的方法，此类方法因没有考虑实际传输中编码分组丢失的问题而不实用，例如以最小重传次数为约束条件的WBR编码方法[7]；第2类是编码和 ARQ相结合的方法，此类方法会因ARQ重传次数的增多使传输效率大幅降低，例如用于WiMAX网络的传输算法[8]和利用反馈信息依次组合每个终端的分组丢失的算法[9]；第3类为选择分组丢失进行编码的方法，如何选择分组丢失是此类算法设计的关键。如Fan等[10]提出的采用搜索的方法选择数据分组生成重传分组的算法，复杂度较高，并且没有动态的组合重传中的分组丢失而性能不佳，BENEFIT算法[11]考虑终端从多个重传分组中获取数据分组的情况，以解码终端数、重传分组有效性和组合分组数为条件选择分组丢失进行编码，有效地提高了分组丢失重传效率，但因选择分组丢失判断条件复杂而不易实现。

综上所述，为了提高无线网络广播传输效率，基于 ONC传输方法的研究目的是如何实现实用且性能更优的数据分组编码算法，即第2类方法中设计分组丢失选择简单实用且 ARQ重传次数少的方法，第3类方法中如何设计高效的数据分组组合策略在降低选择分组丢失复杂度的同时提高重传性能；针对上述2个问题，本文分别提出了基于ONC的多组合分组广播传输(ONCMB, ONC based multiple combination packets broadcast transmission)算法和基于 ONC的单组合分组广播传输(ONCSB,ONC based solo combination packet broadcast transmission)算法。ONCSB和ONCMB分别采用散列搜索的方法和组合每个终端分组丢失的方法生成重传分组，有效地降低了此类方法数据分组组合策略的复杂度，并提高分组丢失重传效率。理论分析和仿真实验都说明了ONCSB和ONCMB的可行性和有效性。新算法适用于单跳无线广播网络重传方法的设计，例如Wi-Fi，WiMAX或LTE网络，并且可用于设计HARQ算法[12]。

2 基于ONC传输方法的思想

基于 ONC的广播传输方法在源节点采用机会式编码(OC, opportunistic coding)技术生成重传分组，不同终端可从一个重传分组中恢复其分组丢失，因此该方法可以减少广播传输的次数。OC将多个数据分组通过异或(⊕)运算编码成组合重传分组，假设Pi(1≤i≤N)为第i个数据分组，R为组合重传分组，则 Pi和 R可以分别由二进制序列{ pi, pi, … , pi}和{r,r,…,r}表示，其中，L表示长

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

其中，λi=1表示Pi编码于R中。

基于 ONC的传输方法可以减少广播传输的次数。如图 1所示，S发送 P1、P2和 P3后，T1、T2和 T3分别丢失 P1、P2和 P3，Rk(k=1,2,…)表示第 k个重传分组。举 2个例子：传输方法 A：重传R1=P1⊕ P2⊕P3时，T1通过 R1⊕ (P2⊕P3)=P1恢复P1，T2和T3同理从R1中得到P2和P3，A只需1次重传；传输方法B：当R1=P1⊕P2时，类似的，T1可以恢复P1，T2可以恢复P2，但是需要传输R2=P3使T3恢复P3，B共需2次重传；传统ARQ方法需要分别重传R1=P1，R2=P2和R3=P3，共需3次重传。因此基于 ONC的传输方法可以减少分组丢失重传的次数，此外，数据分组的组合方式决定了基于ONC传输方法的性能。

图1 基于机会式网络编码重传方法示例

3 基于ONC的广播传输算法

3.1 广播单跳传输模型

在实际的广播无线网络中，数据分组一般通过基站(BS)或无线访问节点(AP)广播发 Pi(1≤i≤N),Tj是否丢失Pi服从参数为qj的贝努力实验，其中，qj表示Tj的分组丢失率。每个时隙S广播发送一个数据分组，全部终端通过可靠信道反馈ACK/NAK信号说明其是否收到该时隙传输的数据分组。当发送完数据分组后，源节点能获得终端分组丢失的信息。

定义1 用Ω来表示S获得的终端丢失数据分组的信息，其可以表示为一个M行N列的矩阵，且M＞1。Ω中元素ωji∈{0,1}表示Tj是否成功收到Pi，ωji=0表示Pi成功发送，反之表示Pi丢失。图2给出了Ω的示例。

图2 Ω示例

定义2 传输带宽B可以用来描述传输算法的性能[6]，其表示为

其中，K表示数据分组重传的次数。B反映了成功传输一个数据分组需要的平均传输次数。

3.2 ONCSB算法

如何选择分组丢失决定了此类算法的复杂度和性能，此外，散列搜索算法具有较低的复杂度和较高的性能，因此ONCSB采用散列搜索的方法降低数据分组选择的复杂度并提高重传性能。

ONCSB选择分组丢失的过程分为4个阶段：1) 根据散列函数计算分组丢失的散列值；2) 根据得到的散列值创建分组丢失的散列列表；3)从散列列表表中选择满足条件的分组丢失组合成重传分组；4)根据终端是否从重传分组中恢复数据分组的情况，更新散列列表。

阶段1：计算分组丢失的散列值。根据Ω第i列的元素值计算Pi的散列值，计算该散列值的散列函数F为

分组丢失对应的散列值跟该终端分组丢失信息对应。由式(3)得到Pi对应的散列值hi满足0≤hi≤2M-1。

阶段 2：创建分组丢失的散列列表。根据分组丢失散列值由大到小得顺序建立分组丢失的散列列表，图3给出了图2所示分组丢失的散列列表，该列表第1行是由式(3)计算得到的散列值H，第2行和第3行表示散列值为H的数据分组数和数据分组。

图3 散列表

阶段 3：选择满足编码条件的分组丢失生成重传分组。具体过程是：A 在散列列表中，选择最大散列值h1；B从已选择的散列值的邻域中选择最大的散列值，直到该邻域为空；C把所选散列值对应的数据分组组合成一个重传分组。定义U表示散列值h1,h2,…,hn(n∈{1, 2, …, N})邻域，U的计算式为

其中， bij(1≤i≤n)表示 hi的第 j比特。如图 3所示，首选选择最大的散列值20，从其邻域中选择散列值8，再从20和8的邻域中选择2，最后从20、8和2的邻域中选择1，之后邻域为空，搜索完成，将散列值20、8、2和1对应的数据分组P5、P4、P2和P1编码组合成一个重传分组。

阶段4：传输第3阶段生成的数据分组，在一个传输时隙内，终端通过ACK/NAK信号反馈其是否收到该数据分组。当一个终端未收到该数据分组时，重新计算该终端分组丢失的散列值，计算公式为

其中，τj=1表示Tj没有从该重传分组中恢复其分组丢失，并根据上式计算的散列值将分组丢失更新到散列列表中。如果散列列表中存在分组丢失，至阶段3，否则结束。

3.3 ONCMB算法

ONCMB算法在源节点依次选择每个终端的分组丢失组成重传分组，使每个终端的分组丢失依次编码于重传分组中，终端从收到的重传分组中解码其分组丢失，若该重传分组只包含终端一个分组丢失，该终端可以解码得到其分组丢失，否则，终端可以从多个重传分组解码得到多个分组丢失。与文献[9]方法相比，ONCMB编码生成单个重传分组的不同分组丢失数较多，因此有效地提高了终端恢复分组丢失的效率，提高了传输性能。

ONCMB算法生成重传分组的过程可分为以下2个阶段。

阶段 1：每次传输，S重传由每个终端的一个分组丢失编码组合成的重传分组，而后终端反馈ACK/NAKs信号说明其是否收到该时隙传输的数据分组。同理，S生成并发送重传分组，再接收反馈得知未恢复的数据分组，依次类推，直到全部数据分组都成功发送。终端从收到的重传分组中恢复分组丢失，当重传分组中包含某终端一个分组丢失时，该终端立即恢复这个分组丢失，当重传分组中包含某终端多个分组丢失时，该终端可以从后续重传分组中恢复分组丢失后再恢复这个重传分组中包含的最后一个分组丢失。

具体的做法是：从Ω每行中选择第一个值为1的数据分组编码得到重传分组 R1，传输 R1后，若Tj(1≤j≤M)未收到R1，则Ω中第j行所选择数据分组对应的元素值不变，否则，该元素值为零；继续生成 R2，直到 Ω 为零矩阵。图 2中，R1=P1⊕P2⊕P3⊕P4⊕P5，假设只有T2未收到R1，则R2=P3⊕P2⊕P5⊕P6⊕P7，若所有终端收到 R2，T1，T4和T5通过R1和R2恢复各自的2个分组丢失。

阶段2：ONCMB使终端从多个重传分组中恢复其分组丢失，因把某终端的多个分组丢失组合到一个重传分组中，可能会导致该终端不能从收到的多个重传分组中恢复分组丢失[13,14]，因此ONCMB依次传输这些终端所需的数据分组完成重传。此时，根据组合分组信息在发送端找出终端不能恢复的ε(ε≥2)个数据分组，首先传输ε-1个不可恢复的数据分组，再解码获取最后一个分组丢失。

令 Ei(n)=1(1≤i≤k, 1≤n≤N)表示数据分组 Pn编码于Ri，反之Pn未编码于Ri，其中，k表示阶段1生成的重传分组数。令N维行向量ψ=[φ1, φ2, …,φn, …, φN]，其中，φn表示Pn编码在哪些重传分组中的信息，则ψ表示所有数据分组是否编码于重传分组中的信息。对于终端Tj(1≤j≤M)，φn的计算公式为

通过式(6)可得到ψ，从ψ中选择相等的非零元素即可推出Tj未恢复的分组丢失。如图2中T3不能从重传分组R1和R2中恢复其分组丢失P3和P5，因由式(6)计算可得 ψ=[0,0,15,0,15,0, 0]，得到φ3=φ5≠0。

4 平均传输带宽分析

当N足够大时，文献[6]给出了最优的平均传输带宽Bopt，其表示式为

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

令Rs和Bs分别表示ONCSB算法传输的平均数据分组数和平均传输带宽。当N足够大时，ONCSB的重传分组中最多包含任一终端的一个分组丢失，因此其生成的平均重传分组数由分组丢失率最大终端的分组丢失数决定，于是ONCSB生成的平均重传分组数r1为

此外，传输r1的过程仍然会有分组丢失，由上述分析可知，其平均分组丢失数r2为

依此类推，传输 ri-1个分组丢失产生的平均分组丢失数ri可以表示为

因此，ONCSB传输的平均数据分组数为

代入式(2)，可得

令RM和BM分别表示ONCMB算法传输的平均数据分组数和平均传输带宽。在第1阶段，ONCMB的重传分组中包含每个终端的分组丢失，平均重传分组数由分组丢失率最大终端的分组丢失数决定，由式(10)知，第1阶段的平均重传分组数r1为

Yossef等[13]在理论上证明了采用二进制码对分组丢失信息进行编码可使重传次数以很大的概率达到最优，本文基于机会式编码的重传方法采用二进制码(如式(1)所示)进行编码，满足上述结论，该方法可使终端以很大概率从最少的重传分组(r1)中恢复全部分组丢失，即r2以很大概率为零。因此，当N足够大时，第2阶段平均发送的数据分组数r2近似为分组丢失率最大终端平均分组丢失数的无穷小量，则r2为

由式(13)和式(14)可得，ONCMB平均发送的数据分组数RM为

代入式(2)，可得

由式(12)和式(16)可知，在一定条件下，本文提出的ONCSB和ONCMB方法可以使网络平均传输带宽接近最优值。

5 仿真实验及分析

实验采用图1所示传统的多播网络，S每次通过广播方式发送一个数据分组，数据分组的长度和发送时间间隔相同。在相同的分组丢失信息Ω条件下，仿真得出了不同算法成功发送全部分组丢失所需的传输次数，再由式(2)得到传输带宽，多次实验后得到平均传输带宽。由式(1)知，平均传输带宽越小算法的性能越好。

为了验证算法的有效性和可行性，并有效反映算法在真实网络环境下的性能，仿真采用不同类型的分组丢失模型来模拟实际无线信道的状态，分组丢失模型分为：1) 随机分组丢失模型；2) 连续分组丢失模型[6]。仿真实验采用上述分组丢失率模型得到分组丢失信息Ω，并统计了不同算法针对相同Ω得到的平均传输带宽。

仿真中比较了下述算法：1)传统的基于ARQ机制的传输算法，记为SF；2)一种适用于WiMAX的传输算法[8]，记为TNC；3)文献[9]的传输算法NCWBR；4)文献[10]的传输算法，记为 DNC；5)文献[11]的BENEFIT算法；6)本文提出的基于ONC的单组合分组广播传输算法，记为ONCSB；7)本文提出基于ONC的多组合分组广播传输算法，记为ONCMB。

5.1 随机分组丢失模型

分组丢失率q的范围是[0.01, 0.2]，步长为0.01，数据分组数N={10,100},终端数M=5。当终端分组丢失率相等，即q1=q2=…=qM=q时，图4给出了分组丢失率变化对算法传输带宽性能的影响。基于ONC的传输算法的性能明显优于传统重传算法。随着分组丢失率的增加，ONCSB和ONCMB算法的性能较其他算法更好。在一定分组丢失率的条件下，分组丢失数随 N值增大而增加，ONCSB和ONCMB选择分组丢失的编码策略较好，因此它们的平均传输带宽较小，而 SF算法不对数据分组进行编码，其性能最差。ONCSB的性能略好于ONCMB的性能，原因在于前者从所有分组丢失中选择可以组合的分组丢失，而后者是连续的选择终端的分组丢失，因此ONCMB的重传分组可能出现不能使终端恢复分组丢失的情况，需要重传分组丢失保证该终端可恢复其分组丢失，导致ONCMB的传输带宽增加。

图4 随机分组丢失模型下平均传输带宽比较

为了说明终端数同平均传输带宽的关系，图 5给出了终端数M不同时对应的平均传输带宽，图中q1=q2=…=qM= 0.1且N=50。由图可知，当M值不同时，ONCSB和ONCMB的性能较好，并且随着M的增加，其平均传输带宽较其他几种算法收益增加。在一定分组丢失率的条件下，随着M的增加，丢失同一个数据分组的终端数增多，广播重传单个数据分组的效率增加，基于 ONC的传输方法的性能接近于SF方法的性能[15]。

5.2 连续分组丢失模型

为了比较信道发生连续分组丢失时算法的性能，定义二状态马尔可夫过程的2个状态为好信道状态Sg和坏信道状态Sb。Pα和Pβ分别表示Sg到Sb和Sb到Sg的转移概率，信道处于状态Sg和 Sb的概率分别为 Pβ/(Pα+Pβ)和 Pα/(Pα+Pβ)。终端分组丢失率之间相互独立，Pα的范围是[0,0.2]，变化步长为 0.02，Pβ为固定值 0.4，Sg和Sb对应的分组丢失率分别为 0.01和 0.5，N={10,100}, M=5。

图5 终端数不同时平均传输带宽比较

图6 给出了算法的平均传输带宽，Pα=0时，信道处于好状态，终端分组丢失率较低(0.01)，所以全部传输算法的性能几乎相同，随着 Pα的增加，信道处于坏状态的概率增加，分组丢失增多，并且N的增大有利于基于ONC的传输算法的重传分组中组合更多的分组丢失，因此随着Pα和N的增大，它们的性能比SF算法的性能更好，其中，ONCSB和ONCMB算法的性能略优于BENEFIT算法，并明显好于其他传输算法的性能。随着Pα的增加，出现数据分组连续丢失的情况增多，在这种情况下，同本文算法一样，BENEFIT算法能使每个终端的分组丢失组合于单个重传分组使重传数量减少，因此其同本文算法性能接近；DNC算法因没有动态的处理重传过程的分组丢失导致其重传次数增加，因此平均传输带宽在所有基于ONC的传输方法中最差。

图6 连续分组丢失模型下平均传输带宽比较

5.3 算法时间比较

表1给出了不同算法的时间复杂度。采用随机分组丢失模型，终端分组丢失率均为0.1，M设为10，实验得出了不同算法的平均执行时间，如图7所示。由比较知，ONCSB由于采用了效率较高的散列搜索方法选择分组丢失，保证传输带宽性能最优的条件下，维持了较低的运行时间。ONCMB搜索终端不可恢复分组丢失的过程增加了执行时间，但与复杂度相同的NCWBR和DNC相比，其传输效率最好，其平均执行时间随着数据分组数的增加明显优于DNC算法，ONCMB性能略好于BENEFIT算法，但前者运行时间和复杂度性能明显优于后者。

表1 算法时间复杂度

图7 平均执行时间比较

6 结束语

为了提高无线网络中广播传输的传输效率，本文提出了2种基于机会式网络编码的广播传输算法，有效地解决此类算法选择数据分组复杂度高及性能不佳的问题。在引入的无线单跳网络广播传输模型的基础上,首先利用散列方法提出了一种高效的单组合分组广播传输(ONCSB)算法，其次在采用从多个重传分组中恢复分组丢失方法的基础上提出了一种多组合分组广播传输(ONCMB)算法。理论分析和仿真实验都说明了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] 卢冀, 肖嵩, 吴成柯. 无线网络中应用机会式网络编码的广播重传方法[J]. 西安交通大学学报, 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] 肖潇, 王伟平, 杨路明等. 基于网络编码的无线网络广播重传算法[J]. 通信学报, 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.