无线传感器网络可分负载调度研究

论文摘要

无线传感器网络的发展以及对其应用需求的持续增长,不断给调度问题赋予新的内涵并且提出新的挑战,任务调度一直是无线传感器网络研究的热点问题。无线传感器网络节点能量有限,所以其任务调度算法应保证任务在最短的时间内完成,以便用户能够根据采集的数据对监控区域做出及时有效的判断及响应,同时应该减少节点能耗,延长网络寿命。用于无线传感器网络任务调度应用建模的工具通常是有向无环图(DAG)和独立任务集。在一般情况下,基于这两类模型的调度问题都是NP完全的。可分负载理论在无线传感器网络上的应用为其任务调度提供了一个有效的解决方案。与其它无线传感器网络任务调度问题的启发式解决方案不同,该技术不仅可以得到最优解,而且可以得到解析解,从而保证了调度结果的一致性。本文研究了可分负载理论在无线传感器网络中的应用技术,具体研究成果如下:1.研究了异构无线传感器网络在分群结构下的任务调度问题。现有的基于可分负载理论的无线传感器网络任务调度模型都是在单层树状拓扑,或者同构的分群结构这些特殊的网络环境下进行研究的。这些对网络的假设条件并不适合于无线传感器网络的研究发展。本文分别在单信道、多信道以及有协处理器三种条件下,分析了分群结构异构无线传感器网络的任务调度问题。给出了异构网络环境下最短的总任务完成时间和最优任务调度方案的解析解,分析了任务调度的极限情况。并针对群首存储资源有限的情况,给出了任务调度的线性规划模型,分析其最优解的情况。2.研究了无线传感器网络多轮任务调度问题。可分负载调度算法分为单轮调度算法和多轮调度算法两大类。单轮调度算法较为简单,但其计算和通信的重叠性比较差,额外的开销相对较大。多轮调度算法具有较好的计算和通信重叠性,从而降低整个应用的响应时间,降低了调度的额外开销。但由于比较难以分析等原因,使得对多轮调度算法的研究成果相对较少,已有的可分负载多轮调度算法大多数是基于同构集群计算环境设计的,并且忽略处理结果的返回问题。本文提出了分群结构下,基于可分负载理论的无线传感器网络多轮任务调度算法。算法根据各个群的任务处理速率按多轮方案将总任务从SINK节点下发给各个群。为了去除由节点间通信干扰导致的性能下降, SINK节点相继向各个群首发送每一轮的负载。每一轮各个群执行完数据采集任务并把数据融合后,也由群首将该轮数据相继向SINK节点报告,使得任务执行和通信更好地重叠,最终减少了整个应用的响应时间且提高了网络资源利用率。3.研究了无线传感器网络任务调度的博弈算法。在一个大规模的无线传感器网络中,组成系统的各个节点可以是属于不同公司、研究机构甚至是个人的传感器网络或单个传感器。因此每个节点都希望能够最大化他们自己的利益。也就是说,每个传感节点都是理性且自私的。传感器节点可能因为能量限制而拒绝尽力地协作完成任务,针对于传感器节点存在这种潜在的自私行为,提出了一种无线传感器网络任务调度的非合作博弈算法。通过对传感器节点的自私行为引入惩戒机制,从而降低了节点背离协作的可能性。设计了一个与总任务完成时间和节点所分配任务大小有关的效用函数,证明了纳什均衡的存在性。4.提出了多SINK架构的无线传感器任务调度算法。多SINK的无线传感器网络比传统架构具有更好的稳定性和有效性,是当前一个研究热点。算法将总任务从多个SINK节点下发至网络中。群内节点在收到各个SINK的子任务后,同时开始采集数据,然后将结果相继向群首报告。群首将群内节点报告的数据融合后,相继向各个SINK传送结果,使得任务执行和通信能够更好的重叠,从而提高资源利用率和减少总任务完成时间。5.提出了与可分负载调度算法等效的连续时间马尔科夫链模型,用马尔科夫链模型对任务调度问题进行分析,其中状态空间由各个节点所应获得的最优负载比例组成。得出可分负载理论与马尔科夫链模型有一定的对等性的结论,通过马尔科夫链内相邻状态的局部平衡等式,可以得到和可分负载理论同样的任务调度结果。新的模型将可分负载调度的分配关系抽象成一种简单紧致的马尔科夫链模型,这样更容易分析大规模的无线传感器网络。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 无线传感器网络简介
• 1.1.1 主要特征
• 1.1.2 体系结构
• 1.1.3 研究内容
• 1.1.4 应用领域
• 1.2 选题背景与课题研究意义
• 1.3 无线传感器网络任务调度的研究意义及要求
• 1.3.1 无线传感器网络任务调度的研究意义
• 1.3.2 传感器网络对任务调度提出的新要求
• 1.4 国内外研究现状
• 1.5 本论文的主要研究内容
• 1.5.1 论文研究内容
• 1.5.2 论文章节安排
• 第二章 可分负载理论基本模型及在无线传感器网络中的应用
• 2.1 引言
• 2.2 可分负载理论基础
• 2.2.1 可分负载理论及其特点
• 2.2.2 可分负载模型及需要解决的问题
• 2.2.3 可分负载理论扩展模型
• 2.2.4 可分负载理论的应用研究
• 2.2.5 国内关于可分负载理论的研究现状
• 2.3 可分负载理论在无线传感器网络中的应用
• 2.4 本章小结
• 第三章 基于可分负载理论的无线传感器网络任务调度分析
• 3.1 引言
• 3.2 相关工作
• 3.3 问题描述
• 3.4 调度策略
• 3.4.1 同时开始采集数据，相继报告数据
• 3.4.2 同时开始采集数据，同时完成报告数据
• 3.4.3 带协处理器的传感节点
• 3.4.4 多SINK 模型
• 3.5 马尔科夫模型分析
• 3.6 能量消耗模型
• 3.7 仿真分析
• 3.7.1 同时开始采集数据，相继报告数据
• 3.7.2 同时开始采集数据，同时完成数据报告
• 3.7.3 带协处理器节点同时开始采集数据，同时完成报告数据
• 3.7.4 三种采集模式的耗时耗能对比
• 3.7.5 多SINK 模型
• 3.8 本章小结
• 第四章 无线传感器网络多轮任务调度
• 4.1 引言
• 4.2 问题描述
• 4.3 调度策略
• 4.4 仿真分析
• 4.5 本章小结
• 第五章 无线传感器网络任务调度的非合作博弈算法
• 5.1 引言
• 5.2 传感器网络中的自私问题
• 5.3 博弈论在无线传感器网络中的应用
• 5.3.1 博弈论概述
• 5.3.2 博弈论基本概念及相关定义
• 5.3.3 纳什均衡
• 5.3.4 博弈论在无线传感器网络中的应用
• 5.4 网络中节点协作的非合作博弈模型描述
• 5.4.1 “支付-补偿”机制描述
• 5.4.2 机制设计基本原理
• 5.5 机制设计
• 5.6 仿真分析
• 5.7 本章小结
• 第六章 总结与展望
• 6.1 内容总结
• 6.2 工作展望
• 致谢
• 参考文献
• 攻读博士学位期间完成的研究成果