基于动态规划的多跳网络在线调度算法研究与分析.doc

摘要：随着车联网、云计算及SDN等诸多新型网络技术的不断兴起，为了在多跳网络中及时传输海量的实时数据，有效的在线控制策略和节点调度算法已成为下一代通信系统的主要特征和挑战。当今社会，现有的节点调度算法都是从网络覆盖的角度来考虑计算的。然而，按照这种情况计算的话，会引起节点的状态发生改变，影响到其他的方面。合理利用动态规划算法，进而来优化改善现有的调度算法，来达到优化系统的传输是现在人们都会考虑到的方面。

传统的调度算法一般有静态调度和动态调度，但是传统的调度方法存在这一些不足，比如不能及时反应问题，没有一定的任务优先级，不能够合理的分配一个系统中的资源，在此基础上研究学者不断的改进，比如动态逼近法（SBFA）算法，拉格朗日乘子法（QP）算法等等，这些算法比如像SBFA算法能够合理分配资源，QP算法能够在环境资源比较少的情况下还能够做出比较好的调度，相对于传统的动态静态调度算法，在优化资源利用，节点处理能理上面有提高。

本文主要阐述了动态规划算法与任务调度算法，并且研究了将动态规划与现有的调度算法相结合，最终目的是希望能够使得在多跳网络中的调度算法得到一个最优化的调节，能够保证各类服务之间的公平性，动态适应网络链路变化，提高系统吞吐量和网络信道利用率，实现服务质量的平滑过渡和降低系统复杂度，以达到在资源相对较少的环境下，优化资源的利用，提高节点处理任务的能力，从而使系统的性能得到提高，达到提高节点任务调度的应用性能的目的。利用MATLAB仿真软件来进行算法性能的测试，测试QP算法的性能相比较于一般的算法具有那些优势或者不足之处。

关键词：动态规划 多跳网络  调度算法

目录

摘要

ABSTRACT

第一章  绪论-1

1.1研究背景-1

1.2研究现状-2

1.2.1动态规划-2

1.2.2在线调度算法-3

1.3研究内容-4

第二章  调度算法-6

2.1独立型任务调度算法-6

2.2构建模型-6

2.2.1收集数据任务模型-6

2.2.2独立型任务调度算法-6

2.3仿真分析-7

2.3.1仿真-7

2.3.2算法性能分析-9

2.5本章小结-10

第三章  动态规划-11

3.1最优性原理-11

3.2离散系统的动态规划-12

3.3多优先级列表动态规划-13

3.3.1相关概念-13

3.3.2任务优先权系数-13

3.4本章小结-13

第四章  基于动态规划调度-15

4.1动态规划与任务调度相结合-15

4.2规划调度-15

4.3本章小结-16

第五章  总结与展望-18

5.1总结-18

5.2展望-18

致  谢-19

参考文献-20