卫星通信调度问题建模论文［精荐］.doc

PAGE \* MERGEFORMAT PAGE \* MERGEFORMAT - 1 - 卫星通信调度问题 摘要 卫星数字通信系统由一颗卫星和一组地面站组成，正确的传输调度方案为星载转发器定义了一系列传输排列组合方式，以为矩阵TRAF中的通信量设计路由。本文针对卫星通信数据传输时间进行了调度，建立模型，解决了一般情况下的最短传输时间的算法。 对于问题一中的数据传输矩阵，我们建立了最短传输时间模型，详尽地写出了具体的算法，画出了对应的流程图。通过采用添加虚拟值的方法，使得每行每列之和都为LB，然后对数据传输矩阵进行合理的拆分，并对每个工作模式的传输时间求和，即为最短传输时间。 问题二即为问题一的推广，对于更为普遍的型的数据传输矩阵，我们在问题一中的算法中添加了判断m和n的大小关系并将原数据传输矩阵构造成为N阶方阵这一步，结合问题一中的算法，从而得到了一般情况下最短传输时间调度方案。 问题三中，我们在对样本进行假设检验之后，求出了在传输过程中数据包发生丢失的情况下传输时间的数学期望。我们假设系统会在一个工作模式完成之后，检测数据是否有丢失，如果有丢失将要进行重新传输。在这次重新传输过程中我们认为进行的是将整个工作模式再次进行传输，并且在重新传输过程中不再发生错误，接着根据概率统计知识进行相关求解。 模型改进时考虑了卫星在传输数据量的过程中，存在一种自动纠错功能，即传输数据包时，数据丢失量在某一范围内，卫星中继站会自己分析补足该数据包，这样缩短了数据传输时间，增强了模型的适用性。 关键字 卫星通信调度 虚拟添加值 传输数据错误 最短传输时间 问题重述 卫星数字通信系统由一颗卫星和一组地面站组成。地面站即扮演与地基通信网络之间的接口角色。通过SS-TDMA（卫星转发，时分复用）技术，卫星可以为每个地面站发配连接时间。考虑这样的例子，在A地有4个发射站，在B地有4个接收站， REF 表 \h \* MERGEFORMAT 表 1给出了一个的数据传输矩阵。TRAFij是在发射站i和接收站j之间传输的数据量。由于所有线路的传输速率都相同，因此数据量可以以单位为秒的传输时间计。 表 SEQ 表 \* ARABIC 1 数据传输矩阵TRAF及传输时间的下界 TRAF 1 2 3 4 rowi 1 0 7 11 15 33 2 15 8 13 9 45 3 17 12 6 10 45 4 6 13 15 4 38 colj 38 40 45 38 LB=45 在此卫星上有一个转发器，允许在四个发射器和四个接收器之间进行任意的排列组合。表2给出了一种排列组合方式，将发射站1到4分别连接到接收站3，4，1，2。这些连接即对数据传输矩阵中某个元素的一部分进行路由安排，称为一个工作模式。在一个模式中传输矩阵中某个元素的一部分就称为一个数据包。 工作模式也是一个4*4的矩阵M，其中每一行每一列都至多有一个非零的数据包。 表 SEQ 表 \* ARABIC 2 工作模式实例与对应调度方案 1 2 3 4 站点 数据包 1 0 0 11 0 1到3 11 2 0 0 0 9 2到4 9 3 15 0 0 0 3到1 15 4 0 13 0 0 4到2 13 colr 38 40 45 38 LB=45 正确的传输调度方案为星载转发器定义了一系列传输排列组合方式，以为矩阵TRAF中的通信量设计路由。也就是说，需要将TRAF分解为一系列的工作模式矩阵。可以将TRAF中的元素拆解开，例如在表2所示的模式中只传输了TRAF31的部分内容。一个被分解的元素将分布于多个数据包和多个传输模式中进行发送。一个工作模式的长度即其中最长的数据包的长度。那么： 1. 请找出此问题的具有最短传输时间的调度方案； 2. 给出一个一般情况下的具有最短传输时间调度方案或者求解具有最短传输时间的调度方案的一般方法（或算法）； 3. 如果传输时会以概率发生错误，此时传输的数据包中的数据有丢失（即没有传输完），且传输的丢失量服从中心为5，标准差为1的正态分布，则情况如何。 问题分析 对于问题一，题目给出了4个发射站与4个接收站数据传输矩阵TRAF和传输时间的下界，以及一个工作模式的传输排列组合方式实例，问题需要将数据传输矩阵TRAF分解成多个工作模式，并求出具有最短传输时间LB的调度方案，最短传输时间即为各个模式的最短传输时间之和，即要求多个工作模式的数据量之和最大，该问题核心就是将D分解成个工作模式，使得总时间最小，可以考虑采用优化调度算法，在矩阵中添加虚拟值，得到各工作模式对应的通信链接，最后再算出最大传输数据量，转换为最短传输时间。 对于问题二，题目要求一般情况下的通信调度算法，此模型可以作为模型一的推广，此时的矩阵不再是方阵，所以可以尝试将一般矩阵转化为