学位论文 > 优秀研究生学位论文题录展示

面向无线网络的高效网络编码方法研究

作　者: 唐斌
导　师: 陆桑璐; 陈道蓄
学　校: 南京大学
专　业: 计算机软件与理论
关键词: 确定网络编码随机线性网络编码协议设计性能分析与优化
分类号: TN92
类　型: 博士论文
年　份: 2014年
下　载: 105次
引　用: 0次
阅　读: 论文下载

内容摘要

在无线网络中,无线传输的广播特性以及网络拓扑的多跳性,使得无线网络中存在大量冗余报文,直接影响着无线网络的传输性能。近年来的研究表明,网络编码技术能够通过有效利用无线网络中的冗余报文,提升网络性能。然而,网络编码增加了额外计算开销,其性能增益通常受限于无线信道广播速率及无线节点的计算能力,同时还会受到无线节点移动性的影响。如何面向这些无线网络的关键特征,设计合理高效的网络编码方法是无线网络性能优化中的重要问题。针对上述问题,本文从适应无线信道广播速率限制的角度研究了多信道环境中网络编码方法,并从适应无线节点计算能力与移动性的角度分别对面向数据传送及面向数据广播的网络编码方法开展了研究。论文主要贡献包括以下三个方面：(1)针对多信道无线网络吞吐率性能优化,以OFDMA中继网络为应用背景,对适应无线信道广播速率的网络编码方法进行了探讨。首先以优化性能与负载为切入点,提出了用于支持编码感知的信道调度策略的全局方法和局部方法。进一步地,针对全局方法下的网络编码感知的信道调度问题,证明了该问题是NP难的且不存在多项式时间近似方案(polynomial time approximation scheme),并提出了一种具有低时间复杂度的启发式算法。针对局部方法下的网络编码感知的信道调度问题,证明了该问题是NP难的,并提出了一种多项式时间近似方案及一种具有1／2近似率的贪婪算法。仿真实验结果表明所提算法相比于无网络编码的机制,能够极大地提高网络吞吐率。(2)针对无线移动网络中数据传送性能优化,对具有常数复杂度的分块随机线性网络编码(简称分块码)方法进行了研究。首先证明了预编码(precoding)在分块码达到正码率中的不可或缺性。在预编码的前提下,对无重叠分块码的可达码率进行了紧(tight)的分析,并进一步地提出了采用扩展图(expander graph)生成重叠报文块的扩展分块码。通过基于树的分析以及扩展论证刻画了扩展分块码的可达码率,从而明确了扩展分块码是第一类具有非平凡性能保证的重叠分块码。数值分析结果显示扩展分块码性能接近最优,其可达码率极大地超出了无重叠分块码。此外,仿真实验结果表明,当输入报文个数有限时,扩展分块码相比于其他重叠分块码具有低得多的传输负载和解码错误概率。(3)针对无线移动网络中数据广播性能优化,提出了一种新颖的基于随机线性网络编码的广播协议。该协议将需要广播的消息分割成多个子消息,并将子消息以随机线性网络编码的方式进行传输。随机线性网络编码的应用使得无线节点易于收集有效信息,从而减轻了因一个或多个节点过晚接收到消息所致的时延瓶颈。与此同时,节点传输采用了随机调度机制,即每一个网络节点随机独立地使用无线信道。随机调度的使用能够在利用无线媒介广播特性的同时,有效应对并发传输所致的冲突问题。理论分析表明,该协议在任意的节点移动速度下,均能够达到渐进最优的广播时延。相反地,纯粹的随机调度策略在节点快速移动时不足以达到最优性。

全文目录

摘要  5-6
英文摘要  6-13
第1章绪论  13-21
  1.1 研究背景  13-16
    1.1.1 网络编码  13-14
    1.1.2 无线网络中网络编码方法  14-16
  1.2 面向无线网络的高效网络编码方法研究  16-18
    1.2.1 问题的产生、描述与意义  16-17
    1.2.2 研究内容与挑战  17-18
  1.3 论文工作  18-21
    1.3.1 论文主要贡献  18-19
    1.3.2 本文的组织安排  19-21
第2章相关工作  21-28
  2.1 网络编码理论相关工作  21-22
  2.2 确定网络编码方法研究  22-23
  2.3 随机线性网络编码方法研究  23-26
    2.3.1 有线网络中随机线性网络编码应用  23-24
    2.3.2 无线网络中随机网络编码应用  24-26
  2.4 小结  26-28
第3章面向多信道无线网络的网络编码方法研究  28-59
  3.1 引言  28-30
  3.2 相关工作  30-31
  3.3 系统建模  31-33
    3.3.1 网络模型  31-32
    3.3.2 调度方法  32-33
  3.4 全局方法下网络编码感知的信道调度  33-37
    3.4.1 形式化描述  33-34
    3.4.2 难度分析  34-35
    3.4.3 启发式算法  35-37
  3.5 局部方法下网络编码感知的信道调度  37-52
    3.5.1 形式化描述  37-38
    3.5.2 难度分析  38-39
    3.5.3 PTAS解法  39-48
    3.5.4 1/2-近似算法  48-52
  3.6 性能评估  52-58
    3.6.1 评估方法  52-53
    3.6.2 仿真设定  53
    3.6.3 仿真结果  53-58
  3.7 本章小结  58-59
第4章面向无线移动网络数据传送的网络编码方法研究  59-81
  4.1 问题建模  61-63
    4.1.1 编码与解码  61-62
    4.1.2 性能分析模型  62-63
  4.2 预编码的重要性  63-66
  4.3 无重叠分块码的可达速率  66-69
  4.4 扩展分块码  69-72
    4.4.1 方法描述  69-70
    4.4.2 可达码率  70-72
  4.5 扩展分块码分析  72-78
    4.5.1 基于树的分析  73-77
    4.5.2 扩展图论证  77-78
    4.5.3 定理4.8的证明  78
  4.6 性能评估  78-80
  4.7 本章小结  80-81
第5章面向无线移动网络数据广播的网络编码方法研究  81-100
  5.1 引言  81-82
  5.2 相关工作  82-83
  5.3 系统建模  83-85
    5.3.1 移动模型  83-84
    5.3.2 通信模型  84-85
    5.3.3 时延下界  85
  5.4 协议与结论  85-89
    5.4.1 纯粹随机调度协议  85-86
    5.4.2 R~2广播协议  86-87
    5.4.3 R~2协议与性能  87-89
  5.5 预备知识与下界  89-91
    5.5.1 网络区域划分  89-90
    5.5.2 投影分析  90
    5.5.3 引理5.1的证明  90-91
  5.6 PRS协议的次优性  91-93
  5.7 R~2协议的最优性  93-99
    5.7.1 R~2的基本性质  93-94
    5.7.2 慢速移动  94-95
    5.7.3 高速移动  95-99
  5.8 本章小结  99-100
第6章总结与展望  100-102
  6.1 论文总结  100-101
  6.2 进一步的研究工作  101-102
致谢  102-104
攻读博士期间发表的论文  104-106
参考文献  106-115

相似论文

基于SCTP的多终端间业务移动控制,TN929.5
一个基于UDP协议的P2P即时通讯软件的设计与实现,TP393.02
确定网络编码的安全特性研究,TN915.01
基于网络编码的网络视频通信差错控制研究,TN919.8
一种基于网络编码的改进型BitTorrent内容分发系统研究,TP393.093
基于网络编码的P2P内容分发机制研究,TP393.02
高压水射流切割特性影响因素分析及系统设计,TG48
分体式燃气轮机性能优化研究,TK472
Gbps无线传输系统MAC协议设计与实现,TN929.5
基于ACE的数据传输系统设计与实现,TP311.52
基于网络的焊接机器人信息传输方法研究,TG409
CDN中一种资源控制器的设计与实现,TP393.05
短波测评与通信软件设计与实现,TN925
无线协作传输系统中多天线终端的伙伴选择方法,TN929.5
密集型窄缝矩形通道液冷冷板性能分析与结构优化,TK124
偏心齿轮分插机构运动学和动力学分析及参数优化,S223.91
匿名认证体系的优化设计与验证,TP393.08
网络编码在P2P中的应用,TP393.02
AIX系统的运行性能优化及应用研究,TP316.81
基于AODV协议的Ad Hoc网络路由安全设计与实现研究,TN929.5
无线通信中协作分集技术的研究,TN92