浅谈无线网络编码入门详解.pdf

1 无线中继广播中的时序控制和网络编码：最优解 和启发式算法 Linyu Huang, Student Member, IEEE, and Chi Wan Sung, Member, IEEE Abstract 本文讨论了如何减小中继无线广播网络的广播完成时间，以及如何降低解码的复杂度。文章同时考虑了 网络编码问题和时序控制问题。文章提出了一种确定性的网络编码算法来产生创新的编码向量。该方法可 以同时应用于基站和中继节点。通过提高所产生编码向量的稀疏度，该算法可以大大地降低解码的计算复 杂度。结合所提出的网络编码算法，文章提出了一种基于动态规划的时序控制方案，并证明了该方案能在 减少广播完成时间方面提供最优解。考虑到动态规划问题的状态空间规模和计算复杂度，文章同时提出来 一种基于贪婪算法的时序控制算法以用于实际工程应用。仿真结果显示，文章所提出的网络编码算法和时 序控制方案在减少广播完成时间和降低解码复杂度方面都变现很好。 【译者注】由于时间关系，本人仅仅翻译了引言和结论部分，以供大家对该文章有一个大概的了 解。详细的内容请参考原文： L. Huang and C. W. Sung, ”Scheduling and network coding for relay-aided wireless broadcast: optimality and heuristic,” in IEEE Transactions on Vehicular Technology, 2013. I. 引言 在无线广播网络中，源节点希望将一份由N个数据包组成的信息发送给该网络中的所有用户。这 样的无线广播网络被广泛地应用于许多场合，比如卫星通信，传感器网络和网络电视。在某些应用 中，信息需要可靠的发送给所有的用户。然而，由于干扰、路径损耗和衰减等原因，并非所有的广 播包都能成功地被所有的用户接收，这样的信道在通信结构的上层可以模拟为包删除信道。在这样 的情况下，链路信号最差的用户就成为了广播网络中的瓶颈。我们的设计目标就是最大限度的减少 This work was partially supported by a grant from the University Grants Committee of the Hong Kong Special Administrative Region, China (Project No. AoE/E-02/08). The authors are with the Department of Electronic Engineering, City University of Hong Kong, Kowloon, Hong Kong (e-mail: l.huang@my.cityu.edu.hk, albert.sung@cityu.edu.hk). 2 完成时间，即完成广播的总时间。在这篇论文中，我们考虑使用网络编码技术对不同用户的信息流 进行编码来提高传输效率，和使用中继节点来协助小区边缘用户的信息传递。 线性网络编码技术已经被广泛的用于提高频带利用率和改善网络的可靠性 [1], [2]。通过对原始 数据包进行线性组合来产生编码数据包，其中线性组合所使用的系数都取自于某一个有限域。把这 些对应于每一个原始数据包的编码系数放到一起，形成一个向量，被称作编码向量。源节点将编码 包和对应的编码向量同时发送给所有的用户。对于一个用户而言，如果一个编码向量不在该用户之 前所收到的编码向量扩张形成的向量空间里面，那么我们称该编码向量对该用户是创新的。如果一 个编码向量对所有的用户都是创新的，那么我们称该编码向量是创新的。为了最小化完成时间，源 节点需要发送尽量对最多数量用户创新的编码向量。文献 [3]证明了当有限域的阶大于或者等于网 络中用户的总数的时候，创新的编码向量一定存在。在该论