基于网络编码的无线网络可靠多播机制研究

《基于网络编码的无线网络可靠多播机制研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学博士学位论文基于网络编码的无线网络可靠多播机制研究姓名：詹成申请学位级别：博士专业：计算机软件与理论指导教师：许胤龙2011-05-02摘要摘要通信技术的发展促进了多种无线传输网络建设与应用，如蜂窝网络，无线自组织(Adhoc)网络等。近年来，移动主机和掌上电脑不断普及，使得许多应用得以在各种无线网络上进行开发。由于无线网络中信道质量差和节点的移动性，数据包丢失在无线网络传输中很常见。而绝大多数应用都需要数据在无线网络中进行可靠传输。因此，无线网络中数据包的可靠传输是一个非常重要的问题。在无线网络中，根据接收节点的反馈信息，源节点可以知道接收节点已经接收到的数据包和丢失的数据包

2、。本文利用网络编码研究了如何编码重传丢失的数据包以保证接收节点能够正确地接收到所有的数据包。针对不同的应用场景，本文研究了不同的编码方案以及传输调度方案来优化网络的性能，优化目标包括最小化发送节点重传的总次数，最小化超过延迟约束数据包的数目等。本文的主要研究内容与贡献如下：(1)基于网络编码的可靠重传算法本文研究了无线网络中基于网络编码的可靠组播，目标在于最小化发送节点重传数据包的总数。本文提出了一个图模型来刻画基于网络编码的重传问题，并将发送节点的重传策略模型化为图中的最小团划分。为了有效的解决编码重传问题，本文提出了一个时间复杂度为O(

3、E

4、)的近似最小团划分算法并证明了其正确性，其中

5、E

6、

7、为图中边的数目。针对不同丢包率的无线网络，实验比较了基于网络编码的重传策略和传统重传策略所需重传数据包的总数。模拟实验结果表明，基于网络编码的重传策略需要的重传数据包数明显少于传统的重传策略。(2)基于网络编码的可靠多播模型在上述工作的基础上，我们提出了两个可靠多播模型，动态多播重传编码模型(DynamicMulticastRetransmissionEncoding,DMRE)和基于缓存的多播重传编码模型(Cache-basedMulticastRetransmissionEncoding,CMRE)以及相应的启发式算法来进一步减少重传次数。DMRE是无记忆模型，假定接收节点不会缓存重传的

8、编码数据包，但DMRE模型通过持续更新多播组中每个接收节点当前已经收到的数据包来进一步减少重传次数，在这种模型下，每次重传都基于接收节点最新需要的数据包。CMRE模型假设接收节点能缓存所收到的所有重I摘要传包并当有足够的信息后才进行解码。模拟实验结果表明，采用DMRE模型的重传策略优于基于团划分的重传策略，而CMRE模型则更优于DMRE模型。(3)基于网络编码的延迟约束广播调度考虑到对数据包延迟等服务质量要求比较高的流媒体应用，本文研究了无线网络中数据包有延迟约束的基于网络编码的广播调度问题，目标在于最小化超过延迟约束数据包的数目。本文提出一个加权图模型来描述这个问题并证明了无线网络中基于网络

9、编码的延迟约束广播调度问题是NP难的。提出了一个整数线性规划数学模型来求解该问题，但由于该问题是NP难解的，所提出的整数线性规划只能求解小规模的网络。通过将图中顶点的权值设置为关于数据包延迟约束的减函数，并进一步提出了一种在图中寻找最大加权团的近似算法来进行编码调度的算法，可以显著的减少超过延迟约束数据包的数目。针对不同的应用需求，还详细分析了顶点的权值函数应该如何设置，为以后针对QoS需求的网络编码问题提供了参考。关键词：无线网络，网络编码，可靠多播，图模型，服务质量IIAbstractAbstractVarietiesofwirelessnetworkshavebecomepopulara

10、longwiththedevelopmentofcommunicationstechnology,suchascellularnetwork,wirelessadhocnetwork,etc.Recentlythemobilehostandhandheldcomputersarebecomingmorepopularandmanynetworkapplicationsarepromotedinwirelessnetworks.Duetothepoorqualityofwirelesschannelandnodemobilityinwirelessnetworks,datapacketsareo

11、ftenlost.However,mostapplicationsrequirereliabledatatransmissioninwirelessnetworks.Therefore,thereliabletransmissionofdatapacketsinwirelessnetworksisveryimportant.Inwirelessnetworks,accordingtothefeed