对于卫星通信调度问题的分析.doc

创新实验论文 论文题目：对于卫星通信调度问题的分析 对于卫星通信调度问题的分析 1）摘要 本文所讨论的问题总的来说是，求最小量的问题，但是这又不同于线性规划和非线性规划。若用（非）线性规划的语言来描述，就是：目标函数，所有的工作模式的传输时间最短；约束条件就是所有工作模式合起来就是一个传输矩阵TRAF。根据工作模式的定义，可以得到，可以由数据传输矩阵分出许多的工作模式，而且数量非常巨大，所以思考工作模式的时候，这是一个障碍。由上所述这个问题可以看作非规划问题，而可以用总结的算法来解决这个问题。 但是如果我们确定选定的工作模式的话，可以成功地将传输矩阵TRAF分为许多的工作模式。所以此问题的关键就是如何确定分出的矩阵最小。 自己写的算法——“逐一消除法”可以保证分出的工作模式与传输矩阵的耗时最小。 关键词： 非规划问题、 工作模式、 逐一消除法 2）问题的重述 卫星数字通信系统由一颗卫星和一组地面站组成。地面站即扮演与地基通信网络之间的接口角色。通过SS-TDMA（卫星转发，时分复用）技术，卫星可以为每个地面站发配连接时间。考虑这样的例子，在A地有4个发射站，在B地有4个接收站，表1给出了一个的数据传输矩阵。TRAFij是在发射站i和接收站j之间传输的数据量。由于所有线路的传输速率都相同，因此数据量可以以单位为秒的传输时间计。 表1. 数据传输矩阵TRAF及传输时间的下界 TRAF 1 2 3 4 rowt 1 0 7 11 15 33 2 15 8 13 9 45 3 17 12 6 10 45 4 6 13 15 4 38 colr 38 40 45 38 LB=45  在此卫星上有一个转发器，允许在四个发射器和四个接收器之间进行任意的排列组合。表2给出了一种排列组合方式，将发射站1到4分别连接到接收站3，4，1，2。这些连接即对数据传输矩阵中某个元素的一部分进行路由安排，称为一个工作模式。在一个模式中传输矩阵中某个元素的一部分就称为一个数据包。 工作模式也是一个的矩阵M，其中每一行每一列都至多有一个非零的数据包。 表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 正确的传输调度方案为星载转发器定义了一系列传输排列组合方式，以为矩阵TRAF中的通信量设计路由。也就是说，需要将TRAF分解为一系列的工作模式矩阵。可以将TRAF中的元素拆解开，例如在表2所示的模式中只传输了TRAF31的部分内容。一个被分解的元素将分布于多个数据包和多个传输模式中进行发送。一个工作模式的长度即其中最长的数据包的长度。那么： 1. 请找出此问题的具有最短传输时间的调度方案； 2. 给出一个一般情况下的具有最短传输时间调度方案或者求解具有最短传输时间的调度方案的一般方法（或算法）； 3. 如果传输时会以概率发生错误，此时传输的数据包中的数据有丢失（即没有传输完），且传输的丢失量服从中心为5，标准差为1的正态分布，则情况如何。 3）模型假设及符号说明 假设：每个数据的传输为整数传输，即每个工作模式包含的数据包都是整数。这可以有效地减轻算法的负担。 4）问题的分析及模型的设计 首先着手于传输矩阵TRAF，如果我们要求所有分离出来的工作模式总时最小的话，我们可以逐步来分解出工作模式。根据假设，每个工作模式的数据包都为整数，所以我们可以用最小量来分解传输矩阵TRAF，即逐一分离出工作模式，消去原传输矩阵TRAF，得到新的传输矩阵。重复消去传输矩阵TRAF，使之成为一个工作模式。 所有由最小量——1来组成的工作模式和被多次消去后传输矩阵TRAF变成的工作模式最终可以结合成新的不会相互重叠的工作模式。 5）求解方法、结果的分析和检验 “逐一消除法”算法： 叙述：逐一消除法的算法核心是求出最小量构成的工作模式。所以核心算法是在求出每个工作模式中的1，在什么位置。因为要求最小，所以应该保证，选取的最小量位置应该在传输矩阵TRAF中最大数据包的位置。 对传输矩阵TRAF进行排序，查看最大值是否又重复，若有重复，这比较这些元素位置的横竖方向上的元素大小，选取数值比较小的（因为可以在选取数值比较小的情况下，较大的数的位置可以被选进工作模式中，减小后面计算中可能导致的不完全消除传输矩阵TRAF）。 可以用同样的方法选取1的第二、第三个位置，自然可以确定第四个位置。 新建一个零矩阵，把以上选出的位置上的零置1。有原来的传输矩阵减去这个新建的矩阵。 判断之后的传输矩阵是否为零（即全部被工作模式消去。） 结果： workMode： val(:,:,1) = 0 0