摘 要：提出了一种基于网络编码的无线网络广播重传算法。该算法按照包丢失分布概率的特点生成新的重传序列，采用多节点的网络编码方法进行丢失包组合实现重传。通过数学分析和仿真证明，该算法能保证接收节点的编码可解性，同时重传次数可达到局部最优性；与传统重传方法相比，该算法可以有效地减少信息包的平均传输次数，从而提高传输效率。
关键词：无线网络; 网络编码; 广播重传机制; 广播重传算法
中图分类号：TN911-34 文献标识码：A
文章编号：1004-373X(2011)17-0051-03
New Wireless Broadcasting Retransmission Algorithm Based on Multiple Nodes Network Coding
WANG Xing-liang, LU Xuan-min, FENG Sha, LIU Ya-liang
(School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710129, China)
Abstract： A wireless network broadcasting retransmission algorithm based on network coding is put forward in this paper. In accordance with the characteristic of packet loss distribution probability, it generates the new retransmission sequences, accomplishes the combination of lost packages, and then realizes the wireless network broadcasting retransmission by means of the multi-node network coding method. The mathematics analysis and simulation results prove that the algorithm can ensure the solvability of the codes at receiving nodes, meanwhile the retransmission frequency can reach the local optimality. Compared with the traditional retransmission method, this algorithm can reduce the average transmission number of message packages more effectively. Therefore, the transmission efficiency was improved.
Keywords： wireless network; network coding; broadcasting retransmission mechanism; broadcasting retransmission algorithm
0 引 言
无线广播技术在蜂窝移动通信系统网中起着重要的作用，目前无线网络具有较高的传输错误率，需要应用丢失包重传技术 ［1-4］。传统的重传机制中，只要在一个现时时间槽有包丢失，接收节点就立刻发送NAK，信源重传这个包，因此需要很大的重传次数；在一种改进的机制中，仅当在现时时间槽内有数据包的丢失，并且这个包没有在以前的时间槽内被正确接收时，才会进行重传，即使是这样，带宽利用率仍然很低［5-6］。
网络编码理论是从2000年左右发展起来的一门新兴理论，其基本原理就是传输链路上的节点对接收到的信息进行相应的操作处理后再进行转发，而目的节点最终能够恢复这些被处理的信息，网络编码已经被证实可以增强网络性能，实现网络最大流传输［7-10］。
因此，本文提出了一种新的基于网络编码广播重传机制，该机制按照包丢失分布概率特点生成新的重传序列，采用基于多节点的网络编码方法进行丢失包组合实现重传，从而极大地减少了重传次数，提高了重传效率。
1 基于多节点网络编码的无线广播重传算法
1.1 算法描述
首先假设一个理想的无线广播网络模型：
假设1:具有一个广播源节点和M(M>2)个接收节点的无线广播网络，广播源以固定间隔时间(Δt)广播信息包。
假设2:广播源节点能获取接收节点丢失情况，即信息包是否丢失；丢失信息包序列号和丢失节点序列号。
假设3:假定M个接收节点的丢包率彼此互不相关，接收节点i(1≤i≤M)丢包率为Pi。令R(m,Pi)表示接收节点数目为m(m≤M)，节点丢包率为Pi(1≤i≤m)时，单位信息包重传平均发送次数。
假设4:丢失情况记录在缓存信息包矩阵T中。
定义1 缓存信息包矩阵T，是指广播发送中ACK/NACKs反馈生成的信息包接收情况矩阵。该矩阵中行表示接收节点接收情况，列表示信息包接收情况。若某个信息包在某个接收节点成功接收，相应位置赋值为0；若丢失赋值为1。
定义2 缓存信息包子矩阵T(S)，是指其中S个信息包的接收情况矩阵。
具体的算法描述如下：
步骤1:依次在缓存信息包矩阵T的每一行搜寻第一个为1的位置；
步骤2:检测步骤1找出的数据包，如果对它们编码，在接收节点是否具有编码可解性；
步骤3:如果步骤2检测出接收节点无法解码，则将无法解码的数据包中存在丢失最多的数据包直接广播发送出去，同时将矩阵T中对应的位置赋值0，然后返回步骤1；如果步骤2检测出所有接收节点都可以解码，则将所寻位置信息包取出放入编码序列，同时将原位置赋值0；
步骤4:将编码序列中的信息包进行网络编码组合后广播发送出去，然后回到步骤1。
图1给出了应用网络编码中广播重传算法的发送情况描述。图1(a)为一个M=5，r=10的缓存信息包矩阵例子;图1(b)为使用该算法时系统的运行情况。
首先通过循环搜索，系统一共生成了5个编码组合，且编码组合均满足编码组合定理，在接收节点均可解码出相应的数据包，实现有效的重传。需要指出的是在7⊕8⊕9组合包发送中，由于该组合中出现了8,9这两个同时在R3丢失的数据包，则会出现7⊕8⊕9组合包在节点R3处不可解的情况。此时，由于8和9两个数据包中9发生丢失的次数多一些，所以源节点会选择直接将数据包9广播发送出去，然后重新搜索矩阵T，在下次编码组合搜索中会生成7⊕8⊕10，实现将所有丢失的数据包进行重传发送。
1.2 数学分析
假设改进的传统重传算法平均传输次数为ηA；本文提出的基于网络编码的重传算法平均传输次数为ηB；依次定义两种算法为机制A和B。
首先考虑两个节点的情况，假设这两个节点的丢包率分别为P1，P2。
下面定义编码增益，即传输带宽比。机制B对于机制A的编码增益定义为：
由此可知，当Pi=P(i=1,2,…,M)时，ηA为M1－P－11－PM，ηB为11－P，M越大，P越大，则G值越大，机制B相对于机制A的编码增益越大。
2 仿真结果及分析
仿真1:接收节点数目变化。取各个接收节点丢包率P1=P2=…=PM=0.08，重传时间间隔λΔt为100Δt。当接收节点数目从2变化到8，每次递增1，测试平均传输次数变化。图2(a)给出仿真1比较曲线。
仿真2:重传时间间隔变化。取各个接收节点丢包率P1=P2=…=PM=0.08，接收节点数目M＝5。当重传时间间隔从1变化到400，测试平均传输次数变化。图2(b)给出仿真2比较曲线。
仿真3:各个接收节点丢包率相同且变化。取接收节点数目M＝5，重传时间间隔λΔt为100Δt。当节点丢包率从0.02变化到0.10，每次递增0.02，测试平均
传输次数变化。图2(c)给出仿真3比较曲线。
从图2(a)可见，基于网络编码的广播重传方法相比传统重传方法，平均传输次数有明显减少，且随着节点数目增加，减少幅度更大。从图2(b)可见，重传时间间隔足够大时，基于网络编码的广播重传方法仿真值更接近理论值。过小的重传间隔使得编码组合几率变少，当λ＝1时，基于网络编码中广播重传方法无法编码，性能与传统重传相同。由图2(c)和图2(d)可见，无论各节点丢包率是否相同，随着节点丢包率增加，基于网络编码的广播重传方法的平均传输次数均相比传统重传方法大大减少。基于网络编码的广播重传方法在各节点丢包率不同的情况下，递增趋势比各节点丢包率相同的情况下更大。
由以上结果和分析可以看出，基于网络编码的广播重传方法相比传统的逐个重传的方法有效地减少了信息包的平均传输次数，提高了重传效率。
3 结 论
本文通过将网络编码理论与无线广播技术相结合，提出了一种新的基于网络编码的低丢包率的无线广播重传算法，并且通过数学分析和仿真证明，该算法可以有效减少无线信道重传次数，从而大大提高了无线信道的利用率。
从实际应用考虑，在使用编码策略减少重传次数的同时，可能会带来重传延时。然而，对于计算延时，随着计算能力代价的增长可以忽略不计；对于等待延时，可以采用设定重传时间间隔的策略，使中心节点等待一定的时间间隔再开始重传，可以有效地降低等待延时带来的影响。
参 考 文 献
［1］THNENBAUM Andrew S.计算机网络［M］.北京:清华大学出版社,2000.
［2］TABBNAE Same.无线移动通信网络［M］.北京:电子工业出版社，2001.
［3］周听.数据通信与网络技术［M］.北京:清华大学出版社,2004.
［4］GUPTA P, KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000, 46 (2): 388-404.
［5］AHLSWEDE R. Network information flow [J]. IEEE-IT, 2000, 46: 1204-1216.
［6］LIU Q. Cross-layer combining of adaptive modulation and coding with truncated ARQ over wireless links [J]. IEEE Trans. on Wireless Communications, 2004, 3 (5): 1746-1755.
［7］KOETTER R, MEDARD M. Beyond routing: an algebraic approach to network coding [J/OL]. [2002-09-22]. .cn/qkpdf/moet/moet201117/moet20111715-1.pdf" style="color:red" target="_blank">原版全文