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

面向多包接收的无线网络调度研究

作　者: 吕绍和
导　师: 周兴铭
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 无线网络多包接收相继干扰消除链路调度网络容量近似算法
分类号: TN929.5
类　型: 博士论文
年　份: 2011年
下　载: 74次
引　用: 0次
阅　读: 论文下载

内容摘要

无线网络在军情侦察、战场通信等军事领域及家庭生活、医疗看护与环境监测等民用领域,有着广阔的应用前景。未来的无线网络呈现出规模与密度不断增大、通信质量要求不断提高等趋势。现有无线网络技术,在性能与可扩展性等方面难以满足未来的应用需求。现有的无线通信网络借鉴了有线网络的许多设计思想。它将无线信道抽象为基于单包接收的点对点信道:接收节点每次仅考虑单个信号的解码;当信道上存在并发的多路传输时,这些传输信号相互干扰。当无线网络的规模较大或部署密度较高时,干扰是制约网络性能的关键因素。无线信道以大气为传播媒介,具有开放性、共享性与脆弱性等特征。点对点抽象,不能充分发挥无线通信的效率。随着无线网络的不断发展,如何摆脱现有思路,设计与无线信道相适应的技术,成为提高无线网络性能的一个突破口。多包接收技术是物理层信号接收技术的重大发展。当信号传输发生冲突时,现有方法简单地将冲突信号抛弃。多包接收技术则试图分离冲突中的信号并完成多份信号的解码。多包接收技术将无线网络从排斥共享、避免干扰转移到允许共享、促进并发的思路上,跳出了传统设计的局限性。此时,无线信道的开放性与共享性不再是造成干扰的有害因素,而是允许并发的有利条件。由于多包接收技术在提高无线网络性能上的巨大潜力,它将在未来得到广泛应用。当物理层具备多包接收能力时,如何协调链路传输以充分发挥多包接收的效能,是网络协议设计的重要任务。只有当冲突中的多路信号满足给定的条件时,多包接收才能成功。在多包接收过程中,冲突的信号之间,不再是简单的相互干扰,而是解码过程中彼此依赖、紧密相关。现有网络协议主要面向单包接收,未考虑这些特征,不能适用于支持多包接收的无线网络。相继干扰消除(SIC)是一种基础性的多包接收技术,链路调度是网络协议设计的核心技术之一。本文系统研究支持SIC的无线网络中基于TDMA(时分多路复用)的链路调度。SIC具有功能强大、实现简单等优点,有望在下一代无线网络(4G)中得到应用。支持SIC的接收节点使用顺序检测方式检测多路传输信号。在每一次迭代中,信号强度最强的信号被解码,而其他信号被视为干扰。如果信号干扰噪声比不低于给定阈值,则该信号被成功解码。然后,将被解码的信号从冲突信号中移除,以降低后续解码的干扰。在随后的迭代检测中,下一个最强的信号被解码。这个迭代过程持续到所有的信号均被解码或者出现解码失败。链路调度是无线网络领域的热点问题,它主要研究信道资源在不同链路之间的分配与使用。调度算法力图达到系统整体的高效与链路通信质量的最佳,是无线网络不可缺少的重要功能。在调度的研究中,主要有非累积与累积两类干扰模型。前者仅考虑链路两两之间的关系,后者则考虑了干扰的累积效应。累积效应是指,当多份干扰信号并存时,总干扰为它们的累加。论文的主要研究内容与研究成果如下。第一研究支持SIC的无线网络中基于非累积干扰模型的链路调度。首先,提出一种新的网络模型—并发图(SG),以刻画SIC的顺序检测特性与链路之间的相关性。其次,定义干扰数以衡量链路的干扰并证明基于SG的链路调度为NP-hard问题。然后,给出两类极大贪婪链路调度算法并证明网络的最大干扰数是它们的性能上界。最后,在仿真实验与基于USPR的原型网络实验中,与IEEE 802.11等经典协议相比,新调度算法的吞吐量,平均提高40%,最高可达120%。与面向单包接收的网络模型(例如,冲突图)相比,并发图的复杂度仅提高O(log2n)倍,其中n为网络中链路的数目。第二研究支持SIC的无线网络中基于累积干扰模型的链路调度。累积效应与SIC顺序检测特性的并存,给描述链路干扰、设计调度算法带来严峻挑战。首先,讨论一种新的网络图模型—加权并发图(WSG)。它是并发图的扩展,通过加权方式描述干扰的累积效应。其次,证明基于WSG的链路调度为NP-hard问题。针对现有算法在利用干扰信息上的不足,提出周边信号感知(context- aware)的新理念。然后,提出容忍度以衡量时间槽接纳新链路的能力并据此设计了两类新的调度算法。在仿真实验中,与现用算法相比,新算法的吞吐量可提高20%到60%。第三研究支持SIC的无线网络中基于累积干扰模型的最大并发集问题。最大并发集是网络中最大的可并发链路集,它直接揭示了网络的并发能力。寻找最大并发集的问题也可视为链路调度的子问题。首先,给出该问题基于数学规划的精确定义并证明在网络支持SIC时求取最大并发集为NP-hard。然后,提出传输代价以衡量链路集的干扰并据此设计新的近似算法。新算法的近似比,上界是它所构建的链路集的传输代价。该算法时间复杂度为O(n4)。仿真实验表明,新算法所得到的集合,其链路数目不低于优化解的70%。第四研究支持SIC的无线网络的调度性能与网络容量。虽然SIC能显著提高网络性能,但在许多实验中,这种提高的程度要低于已有的理论分析结果。为揭示这种矛盾背后的规律,分析了支持SIC的无线网络的调度性能与网络容量。主要结论包括:设A是在设计阶段不考虑SIC特征的调度算法。在不支持SIC时,与最优调度相比,A的近似比记为α1。而当网络支持SIC时,与此时的最优调度相比,A的近似比记为α2。则α2与α1,仅相差常数倍。在非累积模型下,网络容量为O( n )。在非累积模型下,若允许任意的传输功率,网络容量可达O(n);否则,网络容量为O(n(η-1/η))。与单包接收的情况相比,若允许任意的传输功率,SIC使网络容量产生数量级的提高;否则,网络容量仅提高常数倍。在链式网络与蜂窝型网络等场景中,SIC可提高吞吐量20%到200%。然而,只有当SIC的特征被准确描述时, SIC提供的传输机会才能被充分利用。传统算法复杂性理论中的近似比,未考虑调度算法对SIC能力的利用程度,不足以全面衡量支持SIC的无线网络中的调度性能。总之,本文系统研究了支持SIC的无线网络中的链路调度,提出了多个具有合理开销、高性能等优点的调度算法,揭示了支持SIC的无线网络在调度性能、网络容量等方面的规律。研究成果具有很好的理论与实际意义。论文成果深化了对支持SIC时无线网络的本质规律的认识,有助于推动多包接收技术的实际应用。论文所提出的系统模型与技术方案,对面向其它多包接收技术的协议设计,也有很好的参考与借鉴作用。

全文目录

摘要  11-14
Abstract  14-18
第一章绪论  18-32
  1.1 无线网络概述  18-20
    1.1.1 应用的现状与需求  18-20
    1.1.2 无线通信的主要特点  20
  1.2 干扰处理与多包接收  20-24
    1.2.1 资源复用  20-21
    1.2.2 基于单包接收的干扰处理  21-23
    1.2.3 多包接收  23-24
  1.3 链路调度  24-27
    1.3.1 资源调度问题  24-25
    1.3.2 无线网络的链路调度  25-26
    1.3.3 多包接收带来的挑战  26-27
  1.4 国内外的研究现状  27-29
  1.5 研究问题与研究内容  29-31
  1.6 论文组织  31-32
第二章相关研究综述  32-46
  2.1 多包接收技术  32-38
    2.1.1 基础知识  32-33
    2.1.2 多用户检测  33-35
    2.1.3 干扰消除  35-36
    2.1.4 模拟网络编码与Zigzag  36-38
    2.1.5 发展趋势与小结  38
  2.2 面向单包接收的链路调度  38-42
    2.2.1 调度算法的分类  38-40
    2.2.2 图着色与调度  40-41
    2.2.3 其它调度方法  41-42
    2.2.4 小结  42
  2.3 面向多包接收的分析与设计  42-45
    2.3.1 多包接收的建模  42-44
    2.3.2 网络性能分析  44
    2.3.3 网络协议设计  44-45
    2.3.4 小结  45
  2.4 小结  45-46
第三章基于非累积干扰模型的调度  46-68
  3.1 引言  46-47
  3.2 系统模型与挑战  47-49
  3.3 网络干扰的建模  49-53
    3.3.1 链路干扰模型  49
    3.3.2 网络干扰模型  49-51
    3.3.3 并发图：构造  51
    3.3.4 并发图：性质  51-52
    3.3.5 链路并发可行性判断  52-53
  3.4 调度算法  53-60
    3.4.1 干扰数  54-55
    3.4.2 基于独立集的调度  55-57
    3.4.3 达到更好边界的策略  57-60
  3.5 仿真实验评估  60-63
    3.5.1 均匀网络  60-61
    3.5.2 随机网络  61-63
  3.6 原型实验环境评估  63-67
    3.6.1 集中通信模式  64-66
    3.6.2 分布通信模式  66-67
  3.7 结束语  67-68
第四章基于累积干扰模型的最大并发集问题  68-84
  4.1 引言  68-69
  4.2 相关研究  69-70
  4.3 系统模型  70-71
  4.4 加权并发图  71-74
    4.4.1 构造  71-72
    4.4.2 实例  72-73
    4.4.3 判断链路集的可行性  73-74
  4.5 最大并发集的求取  74-79
    4.5.1 问题的定义与难度  74-75
    4.5.2 干扰的理解  75-76
    4.5.3 贪婪算法  76-79
  4.6 性能评价  79-83
    4.6.1 单跳网络  79-80
    4.6.2 均匀网络  80-81
    4.6.3 随机网络  81-83
  4.7 结束语  83-84
第五章基于累积干扰模型的调度  84-98
  5.1 引言  84-85
  5.2 相关研究  85-86
  5.3 系统模型  86-88
  5.4 周边信号感知的调度  88-93
    5.4.1 贪婪算法的一般过程  88-89
    5.4.2 链路集的饱和度  89-92
    5.4.3 周边信号感知的调度算法  92-93
    5.4.4 讨论与分析  93
  5.5 性能评估  93-96
    5.5.1 单跳网络  94
    5.5.2 均匀网络  94-95
    5.5.3 随机网络  95-96
  5.6 结束语  96-98
第六章调度性能的分析  98-118
  6.1 引言  98-99
  6.2 相关研究  99-100
  6.3 系统模型  100-102
    6.3.1 M-level 非累积干扰模型  100-101
    6.3.2 有序累积干扰模型  101-102
  6.4 基于有序累积干扰模型的调度  102-106
    6.4.1 链路调度问题  102
    6.4.2 近似算法  102-105
    6.4.3 性能分析  105-106
  6.5 基于M-level 非累积干扰模型的调度  106-109
    6.5.1 近似算法  106-107
    6.5.2 性能分析  107-108
    6.5.3 讨论  108-109
  6.6 实验结果  109-111
  6.7 结束语  111
  6.8 附录  111-118
第七章网络容量的分析  118-134
  7.1 引言  118-119
  7.2 相关工作  119
  7.3 系统模型  119-120
  7.4 网络容量分析  120-126
    7.4.1 M-level 非累积干扰模型  120-122
    7.4.2 有序累积干扰模型  122-125
    7.4.3 讨论  125-126
  7.5 典型场景分析  126-132
    7.5.1 链式拓扑  126-129
    7.5.2 蜂窝拓扑  129-131
    7.5.3 讨论  131-132
  7.6 结束语  132-134
第八章结论与展望  134-138
  8.1 工作总结  134-135
  8.2 工作展望  135-138
    8.2.1 分布式调度  136
    8.2.2 调度与其它问题的联合设计  136-137
    8.2.3 统一的智能调度框架  137-138
致谢  138-140
参考文献  140-150
作者在学期间取得的学术成果  150-152

面向多包接收的无线网络调度研究

内容摘要

全文目录

相似论文