论文题目: 无线传感器网络广播与节点休眠算法中的节能覆盖问题研究
论文类型: 博士论文
论文专业: 信息与通信工程
作者: 赵大胜
导师: 杨宗凯
关键词: 广播,休眠,最小覆盖,连通支配集,圆周覆盖
文献来源: 华中科技大学
发表年度: 2005
论文摘要: 无线传感器网络在军民用领域有着广阔的应用前景,是目前学术界研究的热点之一。由于无线传感器网络中节点电池能量有限,节能问题受到了广泛的关注。降低节点射频通信部分的能耗是节能的关键,由于射频部分在发送状态功耗最高、休眠状态功耗最低,因此减少冗余通信量和使冗余节点休眠有助于节能。广播在传感器网络中被频繁应用于数据查询、路由发现、时钟同步等操作,广播流量是网络通信流量的重要组成部分。由于传感器网络通常采用高密度布撒,实际只需少量节点参与广播即可覆盖全网节点,广播中存在着大量的冗余。同样,对于目标区域的覆盖也只需少量节点处于活动状态即可完成,也存在着大量的冗余节点。降低冗余广播通信量和使冗余节点休眠有助于节能。如何削减冗余广播和发现可休眠的冗余节点,可归结为对节能覆盖问题的研究,具体包括以下两个问题。1. 广播中的节能覆盖问题:如何用尽量少的节点覆盖网内全部节点,使得只需这些节点参与广播,网内节点都可以收到广播包。这是一个最小点集合覆盖问题,即对一个点集合而言,如何找出其最小连通支配集。2. 休眠机制中的节能覆盖问题:如何使用尽量少的节点覆盖全部的探测区域,使得不出现覆盖盲点、不破坏网络的连通性,这可归结为一个最小区域覆盖问题,其关键是覆盖度和连通性。研究表明,这两个最小覆盖问题都是NP-HARD 问题,只能采用启发式算法求次优解。基于此上考虑,本文主要研究连通支配集的启发式构造算法和冗余节点判定的启发式算法,并将之应用于广播和节点休眠机制中。这些工作得到国家自然科学基金“基于媒体传输特性的无线多媒体技术的研究”(No.60202005)的资助。本文的主要创新点如下所示: 1. 提出了一种基于多点覆盖的连通支配集并行构造算法并将之应用于广播中:相比于同类算法,将计算复杂度从ο( ?3)降为ο( ?2),?代表网内节点的最大度,并降低了连通支配集的尺寸; 降低了冗余广播通信量。
论文目录:
摘要
ABSTRACT
1 绪论
1.1 选题背景与课题意义
1.2 论文的研究内容及组织结构
1.3 论文的创新之处
2 广播和休眠机制中的最小覆盖问题研究与相关理论
2.1 无线传感器网络拓扑模型和感测模型
2.2 广播中的最小集合覆盖问题研究
2.3 节点休眠中的最小区域覆盖问题研究
2.4 本章小结
3 基于多点覆盖的连通支配集构造算法及其广播应用
3.1 引言
3.2 现有算法及其优缺点
3.3 基于多点覆盖的连通支配集构造算法----DRN 算法
3.4 极限情况下的DRN 算法性能
3.5 基于DRN 算法的广播机制设计
3.6 本章小结
4 基于串行最大独立集的连通支配集构造算法及其广播应用
4.1 引言
4.2 最大独立集定义及相关性质
4.3 现有算法及优缺点
4.4 基于权重和时序的连通支配集构造算法
4.5 仿真与结果
4.6 SMCDS 算法在广播中的应用研究
4.7 本章小结
5 基于局部圆周覆盖的节点休眠机制研究
5.1 引言
5.2 连通覆盖问题及相关研究工作
5.3 基于局部圆周覆盖的节点休眠机制研究
5.4 仿真与结果
5.5 小结
6 总结与展望
6.1 论文总结
6.2 后续工作
致谢
参考文献
附录1:攻读博士论文期间发表的论文列表
发布时间: 2006-04-05