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

无线传感器网络上的数据聚集调度算法

作　者: 于博
导　师: 李建中
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: 传感器网络数据聚集调度
分类号: TP212.9
类　型: 硕士论文
年　份: 2008年
下　载: 94次
引　用: 0次
阅　读: 论文下载

内容摘要

随着微电子技术、计算技术以及无线通信技术的进步,低功耗多功能的传感器得到了快速的发展,而且无线传感器网络已经被广泛地应用。数据聚集是无线传感器网络应用中一项重要的操作。本文主要研究传感器网络上的数据聚集调度问题。本文基于极大独立集提出了一种分布式聚集调度算法,为无线传感器网络中的数据聚集产生一个无冲突的调度。该分布式数据聚集调度算法可以分为两个阶段。第一个阶段是分布式聚集树构造算法,第二个阶段是分布式调度生成算法。我们在本文中详细地介绍了该聚集调度算法的细节实现,该算法通过贪心的方法对生成调度的时间延迟进行了优化。据我们所知,本文是第一篇分布式聚集调度算法。接下来我们给出了算法的理论分析。首先我们给出算法生成的调度的时间延迟上界为12 D+ 6Δ+ 16,其中D是网络的直径,Δ是网络图中的最大顶点度。在此之前具有最小时间延迟的数据聚集算法的时间延迟上界为(Δ- 1)R,其中R是网络的半径。然后我们以一个定理的形式给出了算法的通信复杂度和时间复杂度。我们还做了全面的模拟实验来考察该调度算法的性能。理论分析和实验结果均表明本文提出的调度算法优于先前的其他聚集调度算法。本文还提出了在传感器网络中有节点加入或失效的情况下的一种自适应的调度策略。和前面提出的调度算法类似,该自适应调度策略也分为两个阶段。第一阶段是自适应聚集树的维护算法,第二阶段为自适应的调度维护算法。我们对此策略进行了一定的理论分析和模拟实验,从中可以看到,该自适应调度算法能够以很少的通信开销有效地维护网络的调度。

全文目录

摘要  4-5
Abstract  5-9
第1章绪论  9-17
  1.1 研究背景  9-13
    1.1.1 无线传感器网络概述  9-11
    1.1.2 传感器网络的特点与挑战  11-12
    1.1.3 数据聚集概述  12-13
  1.2 国内外的研究现状  13-15
    1.2.1 无线传感器网络的研究现状  13-14
    1.2.2 无线传感器网络上数据聚集问题的研究现状  14
    1.2.3 无线传感器网络上的数据聚集调度问题的研究现状  14-15
  1.3 本文的贡献  15-16
  1.4 本文的结构  16-17
第2章预备知识  17-25
  2.1 无线传感器网络中的数据聚集  17-20
    2.1.1 树型聚集  17-18
    2.1.2 环形聚集  18-19
    2.1.3 簇型聚集  19-20
  2.2 数据聚集调度问题的定义  20-21
  2.3 关于[31]中算法的分析  21-23
    2.3.1 算法的简要描述  21-22
    2.3.2 算法中的错误  22-23
  2.4 本章小结  23-25
第3章无线传感器网络中分布式数据聚集调度算法  25-53
  3.1 引言  25-26
  3.2 基础知识  26-28
    3.2.1 连通支配集相关知识  26-27
    3.2.2 冲突（Collision）的相关知识  27-28
  3.3 分布式聚集调度算法  28-42
    3.3.1 分布式聚集树构造算法  28-32
    3.3.2 分布式调度生成算法  32-42
  3.4 算法的理论分析与证明  42-48
    3.4.1 算法正确性证明  42-43
    3.4.2 时间延迟的分析  43-48
    3.4.3 通信复杂性与时间复杂性  48
  3.5 实验评价  48-52
  3.6 本章小结  52-53
第4章传感器网络中数据聚集的自适应调度策略  53-61
  4.1 数据聚集树的动态维护  53-55
  4.2 网络中节点调度计划的动态维护  55-56
  4.3 自适应调度策略的理论分析  56-57
  4.4 实验评价  57-60
  4.5 本章小结  60-61
结论  61-63
参考文献  63-66
攻读学位期间发表的学术论文  66-68
致谢  68

无线传感器网络上的数据聚集调度算法

内容摘要

全文目录

相似论文