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

无线网络中保证覆盖连通的节点部署问题研究

作　者: 廖卓凡
导　师: 王建新
学　校: 中南大学
专　业: 计算机科学与技术
关键词: 无线传感器网络 WiMAX网络节点移动性覆盖连通
分类号: TP212.9
类　型: 博士论文
年　份: 2012年
下　载: 100次
引　用: 0次
阅　读: 论文下载

内容摘要

无线网络是当前信息领域中的新研究热点,具有广泛的应用前景。在较受关注的无线网络中,无线传感器网络作为21世纪最具影响力的技术之一,由大量传感器节点组成,通过节点收集、处理和传输来自物理世界的数据,为促进人类生产、改善生活质量提供服务。在无线移动互联网中,WiMAX作为宽带无线接入的新兴技术,使用大量中继节点来覆盖用户并中转信号,为用户提供随时随地高速接入互联网的服务,具有加强信号功率、减少信号衰减的作用,改善了用户所收到的信号质量。节点作为这些无线网络的基本组成部分,其部署方式决定了网络的服务质量。本文旨在设计优化的节点部署方案,提高网络服务质量、降低网络构建成本。主要研究工作包括：(1)在无线传感器网络中,任务区域边界的存在导致“边界效应”,影响网络的覆盖和连通性能。针对此问题,本文首先分析研究边界附近节点的位置关系,然后基于此位置关系提出无边界效应部署算法GRLD,使用较少节点实现对任务区域的完全覆盖和网络连通。理论分析和仿真结果表明,算法GRLD部署的网络能覆盖任意形状区域,满足常用连通覆盖半径比值(rc/rs≥0.54)下的网络连通性。相对于已有的典型确定性部署算法,GRLD能保证对区域的无边界覆盖和网络连通,具有较好的部署效率。(2)在能量受限的传感器网络中,节点的移动能耗约为感知和传输数据能耗的10至100倍。节点的移动将导致节点能耗过大,导致其过快“死亡”,缩短网络生命周期。针对此问题,本文设计移动节点部署算法,在保证目标覆盖和网络连通的同时,降低节点的移动能耗。通过定义最小移动代价的节点部署问题,证明问题难度。接着分别针对特殊场景和一般场景,设计了基于分配问题的扩展匈牙利算法、基于团划分的Basic算法和基于目标Voronoi图的TV-Greedy算法解决覆盖问题。基于最小欧几里得树提出ECST-H算法,解决连通问题。理论分析和模拟结果表明,算法能以较低的时间和空间复杂度,用较少的节点移动代价实现对目标的覆盖和全网连通。(3)在WiMAX网络中,当发送功率和信道数目一定时,用户接入链路的传输速率直接取决于用户到中继的距离。本文研究如何部署较少中继,满足用户到中继距离的要求,从而保证用户的数据速率。通过将该其转化为最少团划分问题,基于用户邻居信息提出启发式算法MAXDCP,接着考虑用户地理位置信息,设计算法GEOCP。理论分析和模拟结果表明,相对于已有算法,算法MAXDCP和GEOCP的时间复杂度低,能使用更少中继保证用户的数据速率要求。(4)在移动WiMAX网络中,用户在固定中继的覆盖区域之间移动,加重了沿途中继站的负载,影响信号中转质量。针对此问题,本文提出最少移动中继部署问题MMRP,使用移动中继作为临时中继,对固定中继进行巡逻,减少固定中继在繁忙时期的负载。通过将MMRP转化为点不相交的最少路径覆盖问题,分别基于图的遍历、最大匹配和最大流思想设计算法。理论分析和模拟结果表明,所提出的算法具有低复杂度,能够以较少移动中继满足对固定中继巡逻的要求,有效缓解WiMAX网络中固定中继的负担。综上所述,本文针对无线网络中节点的部署问题提出了相应的解决方案,对于推进无线网络的研究和实用化具有一定的理论意义和应用价值。

全文目录

摘要  4-6
ABSTRACT  6-12
第1章绪论  12-27
  1.1 研究背景和意义  12-21
    1.1.1 无线传感器网络概述  12-16
    1.1.2 WiMAX网络概述  16-20
    1.1.3 节点部署的研究意义  20-21
  1.2 待解决问题  21-22
  1.3 研究目标和研究内容  22-25
  1.4 论文的结构  25-27
第2章相关研究  27-35
  2.1 无线传感器网络中的节点部署  27-32
    2.1.1 静态节点部署  27-28
    2.1.2 移动节点部署  28-32
  2.2 WiMAX网络中的中继部署  32-34
  2.3 本章小结  34-35
第3章无边界效应的传感器确定性部署算法  35-55
  3.1 概述  35-37
  3.2 网络模型和问题描述  37-41
    3.2.1 网络模型和假设  37-38
    3.2.2 边界节点部署分析  38-41
  3.3 算法GRLD的设计  41-47
    3.3.1 相关定义  41-42
    3.3.2 算法基本思想  42
    3.3.3 算法描述  42-47
  3.4 算法性能分析  47-49
    3.4.1 关于算法保证覆盖与连通的证明  47-49
    3.4.2 GRLD中节点的密度计算  49
  3.5 仿真实验与分析  49-53
    3.5.1 GRLD所需节点数目  49-51
    3.5.2 部署节点数目对比  51-53
  3.6 讨论  53-54
  3.7 本章小结  54-55
第4章保证目标覆盖的最小移动代价部署算法  55-80
  4.1 概述  55-56
  4.2 网络模型和问题描述  56-59
    4.2.1 网络模型  56-57
    4.2.2 问题定义  57-59
    4.2.3 问题难度  59
  4.3 针对TCOV问题的算法设计  59-67
    4.3.1 特殊场景下的TCOV问题解决方案  60-61
    4.3.2 一般场景下的TCOV问题解决  61-67
  4.4 针对NCON问题的算法设计  67-69
  4.5 算法性能分析  69-72
    4.5.1 算法的时间和空间复杂度分析  69-71
    4.5.2 算法的鲁棒性分析  71-72
  4.6 仿真实验与分析  72-78
    4.6.1 算法部署方案展示  72-75
    4.6.2 仿真数据分析  75-77
    4.6.3 网络参数对算法性能的影响  77-78
  4.7 本章小结  78-80
第5章 WiMAX网络中基于团划分的中继部署算法  80-96
  5.1 概述  80-81
  5.2 网络模型和问题描述  81-84
    5.2.1 网络模型  82-83
    5.2.2 相关定义  83
    5.2.3 问题描述  83-84
  5.3 针对LORC问题的团划分算法  84-92
    5.3.1 算法MAXDCP描述  86-88
    5.3.2 算法GEOCP描述  88-90
    5.3.3 算法时间复杂度分析  90-92
  5.4 仿真实验与分析  92-95
    5.4.1 网络拓扑  92-93
    5.4.2 部署中继个数比较  93-95
  5.5 本章小结  95-96
第6章 WiMAX网络中移动中继的部署算法  96-111
  6.1 概述  96-98
  6.2 网络模型和问题描述  98-101
    6.2.1 网络模型  98-99
    6.2.2 相关定义  99-100
    6.2.3 问题描述  100-101
  6.3 针对MMRP问题的算法设计  101-106
    6.3.1 忙期图分析  102-103
    6.3.2 针对不加权有向无环忙期图的最大匹配算法  103
    6.3.3 针对加权有环忙期图的最大流算法  103-105
    6.3.4 算法复杂度分析  105-106
  6.4 仿真实验与分析  106-110
    6.4.1 路径数目  106-108
    6.4.2 忙期覆盖收益  108
    6.4.3 网络开销  108-110
  6.5 本章小结  110-111
第7章结束语  111-115
  7.1 工作总结  111-113
  7.2 研究展望  113-115
参考文献  115-129
致谢  129-131
攻读学位期间主要的研究成果  131-132

无线网络中保证覆盖连通的节点部署问题研究

内容摘要

全文目录

相似论文