卫星通信调度问题.docVIP

卫星通信调度问题 姓名 学院 年级专业 学号 联系电话 相关学科成绩 高等 数学 线性 代数 概率 统计 数学 模型 数学 实验 英语四级 英语六级 朱春春 土木学院 07测绘工程 97 95 93 未学 良 557 486 程 睿 木学学院 07土木工程建筑工程 99 83 100 未学 未学 610 493 唐 雷 计算机学院 08计算机科学与技术 71 80 未学 未学 未学 531 459 卫星通信调度问题 本文主要是研究在卫星通信过程中，利用SS-TDMA工作原理，提出算法，将待传输的数据矩阵进行拆分，分次发送，并使总的传输时间所用最小。合理的假设及正确的分析出约束条件是很重要的。我们选择了有约束的优化模型（整数规划模型）。通过资料学习，提出算法，并通过对几种不同的数据矩阵进行拆分对比，提出模型改进。通过MATLAB编程，对该优化模型进行求解。 对于问题一，我们对于题目给出的44数据矩阵分析可以得出，第一问所求最优方案，最短的时间即为LB，因此求最优路由方案转化为将原始矩阵各个元素拆分后组成若干个工作模式矩阵，每个工作模式矩阵中每行每列至多有一个非零元素，取每个工作模式矩阵中的最大元素作为这个矩阵的传输时间，再将每个传输时间相加，之和为LB，则满足题意，因此建立整数规划模型进行求解。采用了添加虚拟值算法，使每行每列元素之和均为LB，再按每行每列至多有一个非零元素的原则从最小非零元素开始，得到若干个模式矩阵，最后在模式矩阵中对应添加虚拟值的位置将虚拟值减去，则为最后的工作模式矩阵。 问题二要我们针对一般情况进行讨论，因此我们将数据发送站点数目取m，数据接收点数目取为n，这样原始数据矩阵即为一个m行n列队一般矩阵。为了还能够继续使用第一问的算法，我们将这个m行n列矩阵，通过添加0元素，变成N阶方阵（N=max{m,n}），这样就可以利用问题一的结论，采用改进的算法进行求解，并且使用MATLAB进行编程求解，得到更一般最优方案的解算程序，具体程序参见附录一； 对于问题三的问题，由于存在数据丢失，且每个数据包中的数据丢失量服从正态分布的概率形式，因此，我们通过求所用时间的期望值来考虑这种概率影响，首先针对于一个工作模式矩阵，在确认了其非零行的数目以后，从第一个数据包开始，先求出每个数据包丢失数据量的期望值，且丢失的数据要重新发送，而传输成功的数据就不用再发，因此，在求得每个数据包丢失数据量中，找出其最大值，就是在这种工作模式矩阵正常发送时间基础上需要多计算的那部分额外时间。最后，求出每个工作模式矩阵的这个额外时间后，进行累加，这也是一个期望值，表示的意义就是在发送数据时若发生数据丢失，考虑数据丢失的概率因素对于发送时间的增量。 关键字：优化模型 MATLAB编程 约束条件 工作模式矩阵 数据丢失 概率密度函数 期望值 一、问题的重述 第一个问题要求设计一种传输方案，针对于题目所给出的数据传输矩阵，合理地选择工作模式，使得传输所用时间最小； 第二个问题要求我们将问题推广至一般情况，即对于任意的m个数据发送点及n个数据接受点，如何选择工作模式，才能使传输所有数据所需要的时间最短； 第三个问题要求我们考虑在发生数据损失时，且已知丢失数据的概率以及丢失量的概率分布，如何对一种既定的最优工作模式估计其实际的传输时间。 二、模型的基本假设 1、假设一个工作模式下，发射站和接收站是一对一的关系，即假设工作模式矩阵的每一行每一列至多有一个非零数； 2、在发送站与接收站之间传输的数据量为非负整数； 所有线路的传输速率都相同，因此数据量以单位为秒的传输时间计 3、卫星在某段时间内只能处理一种工作模式，下一工作模式必须待上一步工作模式全部处理完毕后才可进入卫星转发器； 4、假设在两种工作模式之间不需要处理时间，则数据传输矩阵TRAF的传输时间只等于其所对应的所有工作模式的传输时间之和。 5、若发生数据丢失，假设分成两个步骤，第一步，数据发送站在第i个工作模式正常发送时间段内等待确认信息，第二步，若收到确认信息，则数据没有丢失，若没有收到信息，则将丢失部分数据进行重新发送，且假设第二步发送丢失数据时，不再有数据损失，可一次性完成； 6、在数据丢失时，如果丢失的数据介于n-1到n之间，则统统进一位，发送丢失数据时，发送数据量为n，及丢失的数据量为整数，如数据丢失了1.1秒则重发送2秒； 三、符号说明 1、发射站个数为m;接收站个数为n; 2、将数据传输矩阵TRAF矩阵用D表示，其中的每一个元素记作(a=1,2,…,m；b=1,2,…,