无线传感器网络节能问题及相关的图论问题

论文摘要

由于半导体技术在最近30年间里成指数式发展,研究人员们有能力利用这个半导体生产技术制造小型化的天线和能够感应物理世界的传感器元件。因此由这些传感器组成的网络开启了一个新的研究领域,这个领域覆盖军事,环境,机械,生物,家庭,太空以及物体追踪等等。一个无线传感器网络有很多的传感器节点组成,并且每个节点有能力传感其周围物理空间的一些属性,比如光线,温度,或者震动等等。无线传感器网络的目的就是要处理这些传感需求以及将传感的数据汇报给用户。但是,由于无线传感器网络在其部署完成后必须是自组织,自调节和自管理的,所以这个领域带来了很多新的挑战。传感器节点中的传感器,处理器和天线的能源通常都是由电池提供的,所以在传感器网络运行中是无法进行充电的。节能以延长网络寿命是无线传感器网络的一个主要设计目标。另外一个设计目标是保证无线传感器网络提供给应用的服务质量（QOS）。一般来说,服务质量都是通过无线传感器网络获得信息的准确性和及时性来进行评价的。在这篇论文中,我们将分别研究无线传感器网络在保证两个服务质量（即覆盖和有效路由）的情况下节能的问题。第一章介绍了无线传感器网络的来历及其与传统网络和无线网络相比较出现的新的特征。我们在这篇论文中主要考虑三个方面的问题,即节能,覆盖和有效路由问题。由于无线传感器网络中节点能源的有限性,节能是最重要的问题。另外两个问题都是伴随节能问题的。覆盖需求的目标就是使目标在至少一个传感器节点的传感范围内。而有效路由的目标是将收集到的数据通过有效的方式传输给用户。我们将介绍关于这些方面相关的工作以及根据这些工作的特征进行总结。另外,我们将阐述我们的工作与其它工作载这些特征上的不同点。最后,我们将介绍一些我们在这篇论文中经常使用的有关图论的基本定义和符号。第二章到第四章将研究有关覆盖节能的问题。第二章将研究有关在异构无线传感器网络中一组传感器节点监控一组位置明确的目标节点的问题。我们提出一种有效的方式来延长网络寿命,这种方式将传感器节点以最大程度分成不相交的集合,每个集合中的传感器节点轮流启动监视目标节点。启动的节点将负责监视所有的目标节点同时保证数据传输到网关节点。在这一章节中我们将介绍保证覆盖和连同的最大化不相交节点结合问题（MDS-MCC）,同时我们证明这个问题是NP完全的。我们为解决此问题提出了一个有效的算法,并且实现了这个算法中相关的启发式函数。另外,理论分析和试验表明了此算法的有效性。第三章继续研究在特殊情况下的MDS-MCC问题。我们考虑无线传感器网络中每个节点只能够监视一个目标或者只用于传输数据的情况。我们假设无线传感器网络有l个目标,每个目标被恰好k个节点监视。当k=2并且网络所对应的图G是（l+max{1,1-4}）连通的,或者当k≥3并且G是（l（k-1）+1）连通时,我们能够肯定找到k个不相交的节点集合,每个集合中的节点能够完全覆盖所有的目标,并且与网关节点连通。在第四章中,我们扩展第三章中的工作继续定义每个节点有且仅有d个单位的工作时间。我们提出了一个有效的方法组织这些节点分为不同的集合,每个集合的节点能够完全覆盖所有的目标,并且与网关节点连通。我们证明了要找到最多的这样子的集合也是NP完全的。即使在保证特定连通度的情况下,这个问题也是NP完全问题。我们设计了一个算法,并且从理论和试验的角度证明了这个算法的可行性。在最后的一个章节中,我们将介绍移动物体追踪无线传感器网络的路由问题。我们将同时解决路由中网络寿命最大化（即节能）和延时最小化的问题。为了使问题可解,我们假定每个节点在开启后将一直保持工作状态。由此,我们把网络寿命最大化抽象为求最大的为被开启的节点数目,以及把延时最小化抽象为求最小的路由路径长度。我们证明了这个问题不仅是NP完全的同时也是APX完全的,因此我们提出了三种启发式算法解决此问题。我们进行了多项试验来说明这三种算法在三种不同部署拓扑结构（随机结构,网格结构以及超立方结构）上网络寿命和延时性能上的优缺点。此外,我们针对这三种集中式的算法实现了其对应的分布式算法。

论文目录

• 摘要
• Abstract
• 第一章 引言
• §1.1 无线传感器网络
• §1.2 节能
• §1.2.1 节点层节能
• §1.2.2 MAC层节能
• §1.2.3 网络层节能
• §1.3 覆盖
• §1.4 路由
• §1.5 图论中的基本定义和符号
• 第二章 保证覆盖和连通的节能无线传感器网络
• §2.1 相关工作
• §2.2 问题定义
• §2.2.1 保证覆盖和连通的最大不相交集合问题（MDS-MCC）
• §2.2.2 网络模型
• §2.2.3 收敛的图
• §2.2.4 NP完全性
• §2.3 算法
• §2.4 分析以及模拟
• §2.4.1 理论分析
• §2.4.2 解决MDS-MCC问题的模拟退火算法
• §2.4.3 性能评估
• 第三章 MDS-MCC问题中的一类特殊问题以及其解的界
• §3.1 问题的形式化
• §3.2 定理证明
• §3.3 相关算法
• 第四章 考虑传感器节点工作时间的节能覆盖问题
• §4.1 NP完全性
• §4.2 相关算法
• §4.3 性能分析
• §4.3.1 理论分析
• §4.3.2 性能评价
• 第五章 实现无线传感器网络中的移动物体追踪需求
• §5.1 问题形式化
• §5.1.1 假设条件
• §5.1.2 符号及其定义
• §5.1.3 NP完全性
• §5.2 算法
• §5.2.1 最短路径选择算法
• §5.2.2 二重最短路径选择算法
• §5.2.3 带权最短路径选择算法
• §5.3 性能评价
• §5.3.1 模拟配置
• §5.3.2 指标
• §5.3.3 随机图
• §5.3.3.1 图的大小
• §5.3.3.2 能量容量
• §5.3.3.3 连通度
• §5.3.4 二维网状栅格vs.超立方
• §5.4 分布式实现
• 参考文献
• 在学期间完成的学术论文
• 研究展望
• 致谢