《卫星通信调度问地的题目》由会员分享，可在线阅读，更多相关《卫星通信调度问地的题目（23页珍藏版）》请在金锄头文库上搜索。
1、word卫星通信调度问题某某学院年级专业学号联系相关学科成绩高等数学线性代数概率统计数学模型数学实验英语四级英语六级朱春春土木学院07测绘工程20076383979593未学良557486程睿木学学院07土木工程建筑工程 200759709983 100未学未学 610493唐雷计算机学院08计算机科学与技术2008552671 80 未学未学未学 531459卫星通信调度问题摘要：本文主要是研究在卫星通信过程中，利用SS-TDMA工作原理，提出算法，将待传输的数据矩阵进展拆分，分次发送，并使总的传输时间所用最小。合理的假设与正确的分析出约束条件是很重要的。我们选择了有约束的优化模型整数规划模
2、型。通过资料学习，提出算法，并通过对几种不同的数据矩阵进展拆分比照，提出模型改良。通过MATLAB编程，对该优化模型进展求解。对于问题一，我们对于题目给出的44数据矩阵分析可以得出，第一问所求最优方案，最短的时间即为LB，因此求最优路由方案转化为将原始矩阵各个元素拆分后组成假如干个工作模式矩阵，每个工作模式矩阵中每行每列至多有一个非零元素，取每个工作模式矩阵中的最大元素作为这个矩阵的传输时间，再将每个传输时间相加，之和为LB，如此满足题意，因此建立整数规划模型进展求解。采用了添加虚拟值算法，使每行每列元素之和均为LB，再按每行每列至多有一个非零元素的原如此从最小非零元素开始，得到假如干个模式矩
3、阵，最后在模式矩阵中对应添加虚拟值的位置将虚拟值减去，如此为最后的工作模式矩阵。问题二要我们针对一般情况进展讨论，因此我们将数据发送站点数目取m，数据接收点数目取为n，这样原始数据矩阵即为一个m行n列队一般矩阵。为了还能够继续使用第一问的算法，我们将这个m行n列矩阵，通过添加0元素，变成N阶方阵N=maxm,n，这样就可以利用问题一的结论，采用改良的算法进展求解，并且使用MATLAB进展编程求解，得到更一般最优方案的解算程序，具体程序参见附录一； 对于问题三的问题，由于存在数据丢失，且每个数据包中的数据丢失量服从正态分布的概率形式，因此，我们通过求所用时间的期望值来考虑这种概率影响，首先针对于
4、一个工作模式矩阵，在确认了其非零行的数目以后，从第一个数据包开始，先求出每个数据包丢失数据量的期望值，且丢失的数据要重新发送，而传输成功的数据就不用再发，因此，在求得每个数据包丢失数据量中，找出其最大值，就是在这种工作模式矩阵正常发送时间根底上需要多计算的那局部额外时间。最后，求出每个工作模式矩阵的这个额外时间后，进展累加，这也是一个期望值，表示的意义就是在发送数据时假如发生数据丢失，考虑数据丢失的概率因素对于发送时间的增量。 关键字：优化模型 MATLAB编程 约束条件 工作模式矩阵 数据丢失 概率密度函数 期望值一、问题的重述第一个问题要求设计一种传输方案，针对于题目所给出的数据传输矩阵，
5、合理地选择工作模式，使得传输所用时间最小；第二个问题要求我们将问题推广至一般情况，即对于任意的m个数据发送点与n个数据承受点，如何选择工作模式，才能使传输所有数据所需要的时间最短；第三个问题要求我们考虑在发生数据损失时，且丢失数据的概率以与丢失量的概率分布，如何对一种既定的最优工作模式估计其实际的传输时间。二、模型的根本假设1、假设一个工作模式下，发射站和接收站是一对一的关系，即假设工作模式矩阵的每一行每一列至多有一个非零数；2、在发送站与接收站之间传输的数据量为非负整数； 所有线路的传输速率都一样，因此数据量以单位为秒的传输时间计；3、卫星在某段时间内只能处理一种工作模式，下一工作模式必须待
6、上一步工作模式全部处理完毕后才可进入卫星转发器； 4、假设在两种工作模式之间不需要处理时间，如此数据传输矩阵TRAF的传输时间只等于其所对应的所有工作模式的传输时间之和。5、假如发生数据丢失，假设分成两个步骤，第一步，数据发送站在第i个工作模式正常发送时间段内等待确认信息，第二步，假如收到确认信息，如此数据没有丢失，假如没有收到信息，如此将丢失局部数据进展重新发送，且假设第二步发送丢失数据时，不再有数据损失，可一次性完成；6、在数据丢失时，如果丢失的数据介于n-1到n之间，如此统统进一位，发送丢失数据时，发送数据量为n，与丢失的数据量为整数，如数据丢失了1.1秒如此重发送2秒；三、符号说明1、
7、发射站个数为m;接收站个数为n;2、将数据传输矩阵TRAF矩阵用D表示，其中的每一个元素记作(a=1,2,m；b=1,2,n)；3、D的虚拟矩阵记作DD；4、传输所有数据所需的总时间记作T，而将每个工作模式所需的时间记作5、记一个工作模式为矩阵(i=1,2,k)，其中的每个元素记作( i=1,2,k; a=1,2,m; b=1,2,n)；6、k为一次总数据传输过程中工作模式的个数；7、m为地面数据发送点个数，n为地面数据接收点个数；8、记一个模式矩阵为，其中每个元素记作，并记=max，即表示的是第 k 个模式矩阵中的最大元素值； 9、传输时间下限记作LB；10、r为中非零行的数目；11、j为中
8、发生数据丢失的数据包的个数；12、p表示数据丢失的量；13、q表示有j个数据包发生丢失时，第q种发生丢失的数据包的组合；14、q=1,2,3表示当有j个数据包发生丢失时，第q种发生丢失的数据包组合的最大值。15、数据传输总时间的期望值为ELB。四、问题的分析与其模型的建立求解一问题一的分析和模型建立求解：1问题一的分析：该问题要求我们对于已经给定的数据传输矩阵，设计一种数据传输转换方法，使在满足要求的情况下使传输时间最少。根据题意，记TRAF矩阵为D，D矩阵中，每一个元素表示从i号发射站至j号接收站共需传送的数据量，因为传输的数据量可以用单位为秒的传输时间记，因此也就是从i号发射站至j号接收站
9、传输数据所需要的时间。题目表1中，列自上而下的数据代表的是i(i=1,2,3,4)号发射站向所有的接收站所发送的总数据量，也即是发送完所有数据所需总时间；而从左至右代表的是j(j=1,2,3,4)号接收站从所有发射站接收数据量，也即是承受完这些所有数据所需的总时间。并且由题意，可以将拆分为非负整数的组合，将一次的总数据传输分成假如干个工作模式进展数据传输。因此，就存在这样的拆分方式，使得传输总数据所用的时间最少，第一问正是要我们求出这样的最优拆分方式。由假设4可知，总时间T 即为：，其中，为每个工作模式所需的时间，也即是每个工作模式中的最长数据包的长度。并且在D中我们可以看到，时间下限LB=4
10、5。假设某种分配方式，使得被拆开的元素在其所在的工作模式中均为最大的，如此加在一起后就是LB；而对于其他情况，假如这些被拆开的元素至少有一个不是所在工作模式矩阵的最大元素，那么其他元素与这个工作模式矩阵中的最大值相加后就会大于LB。 由此分析可知，任何一种分配方案，最终所得到的总传输时间一定是大于或等于LB的。因此，问题一又可描述为找到一种工作模式矩阵的组合，既满足数据的需求，同时传输数据所用的总时间就是传输时间下限值LB。2问题一的模型建立和求解：由上述分析可知，此题其实对应的就是带有一定约束条件的优化模型。可建立优化模型整数规划模型如下：目标函数：i=1,2，kT=LB工作模式矩阵约束条件
11、：；当，如此，且均为非负整数；针对此问题，考虑到问题一中，m=n=4，现提出一种优化算法如下：第一步：记 LB = max，；第二步： 在D 中添加虚拟值，使得 D 每行每列之和均为LB，并记为D的虚拟矩阵DD：第三步：令 u = 0 , C = 0；第四步：如果 DD 0，转第五步；否如此转第六步；第五步：令 u = u + 1 , 在 DD 中找出具有最小非零元素的模式矩阵 ，计算其工作模式的长度，令DD=DD，C=C+。转第四步；第六步：将 u 个工作模式矩阵中的虚拟值都去掉，即可得到一种最优的工作模式的集合；第七步：算法完毕，C值即是最短传输时间，也就是等于LB。不难发现，在以上优化算
12、法中，第二步和第六步的具体操作有多种方法，即满足最优要求的工作模式的集合可能求解出很多种。由于数据量不大，采用上述优化调度算法，即可手算解得多种具有最短传输时间的调度方案。下面给出其中两种最优方案：数据传输矩阵：D = 第一种方案：采用矩阵形式表示添加虚拟值，构造虚拟矩阵DD =按上述优化算法进展计算，得出各个模式矩阵如下：第一种模式矩阵 第二种模式矩阵第三种模式矩阵 第四种模式矩阵第五种模式矩阵 第六种模式矩阵第七种模式矩阵 第八种模式矩阵第九种模式矩阵将模式矩阵中相应位置的虚拟值减去，即可以得到对应于每种模式矩阵的工作模式。工作模式矩阵如下：第一种工作模式 第二种工作模式 第三种工作模式 第四种工作模式第五种工
