卫星通信调度问题建模论文 17页

《卫星通信调度问题建模论文 17页》由会员分享，可在线阅读，更多相关《卫星通信调度问题建模论文 17页（17页珍藏版）》请在金锄头文库上搜索。

1、- 1 -卫星通信调度问题摘要卫星数字通信系统由一颗卫星和一组地面站组成，正确的传输调度方案为 星载转发器定义了一系列传输排列组合方式，以为矩阵 TRAF 中的通信量设计路 由。本文针对卫星通信数据传输时间进行了调度，建立模型，解决了一般情况 下的最短传输时间的算法。对于问题一中的数据传输矩阵，我们建立了最短传输时间模型，详尽44 地写出了具体的算法，画出了对应的流程图。通过采用添加虚拟值的方法，使 得每行每列之和都为 LB，然后对数据传输矩阵进行合理的拆分，并对每个工作模式的传输时间求和，即为最短传输时间。tL问题二即为问题一的推广，对于更为普遍的型的数据传输矩阵，我们nm 在问题一中的算法

2、中添加了判断 m 和 n 的大小关系并将原数据传输矩阵构造成 为 N 阶方阵这一步，结合问题一中的算法，从而得到了一般情况下最短传输时 间调度方案。问题三中，我们在对样本进行假设检验之后，求出了在传输过程中数据包 发生丢失的情况下传输时间的数学期望。我们假设系统会在一个工作模式完成 之后，检测数据是否有丢失，如果有丢失将要进行重新传输。在这次重新传输 过程中我们认为进行的是将整个工作模式再次进行传输，并且在重新传输过程 中不再发生错误，接着根据概率统计知识进行相关求解。模型改进时考虑了卫星在传输数据量的过程中，存在一种自动纠错功能， 即传输数据包时，数据丢失量在某一范围内，卫星中继站会自己分析

3、补足该数 据包，这样缩短了数据传输时间，增强了模型的适用性。关键字关键字 卫星通信调度 虚拟添加值 传输数据错误 最短传输时间- 2 -1. 问题重述卫星数字通信系统由一颗卫星和一组地面站组成。地面站即扮演与地基通 信网络之间的接口角色。通过 SS-TDMA（卫星转发，时分复用）技术，卫星可 以为每个地面站发配连接时间。考虑这样的例子，在 A 地有 4 个发射站，在 B 地有 4 个接收站，表 1 给出了一个的数据传输矩阵。TRAFij 是在发射站 i 和接 收站 j 之间传输的数据量。由于所有线路的传输速率都相同，因此数据量可以 以单位为秒的传输时间计。表 1 数据传输矩阵 TRAF 及传输

4、时间的下界TRAF1234rowi1071115332158139453171261045461315438colj38404538LB=45在此卫星上有一个转发器，允许在四个发射器和四个接收器之间进行任意 的排列组合。表 2 给出了一种排列组合方式，将发射站 1 到 4 分别连接到接收 站 3，4，1，2。这些连接即对数据传输矩阵中某个元素的一部分进行路由安排， 称为一个工作模式。在一个模式中传输矩阵中某个元素的一部分就称为一个数 据包。工作模式也是一个 4*4 的矩阵 M，其中每一行每一列都至多有一个非零的 数据包。表 2 工作模式实例与对应调度方案1234站点 数据包1001101到 3

5、11200092到 493150003到 1154013004到 213- 3 -colr38404538LB=45正确的传输调度方案为星载转发器定义了一系列传输排列组合方式，以为 矩阵 TRAF 中的通信量设计路由。也就是说，需要将 TRAF 分解为一系列的工作 模式矩阵。可以将 TRAF 中的元素拆解开，例如在表 2 所示的模式中只传输了 TRAF31 的部分内容。一个被分解的元素将分布于多个数据包和多个传输模式中 进行发送。一个工作模式的长度即其中最长的数据包的长度。那么：1. 请找出此问题的具有最短传输时间的调度方案；2. 给出一个一般情况下的具有最短传输时间调度方案或者求解具有最短传

6、 输时间的调度方案的一般方法（或算法）；3. 如果传输时会以概率发生错误，此时传输的数据包中的数据有丢失（即 没有传输完），且传输的丢失量服从中心为 5，标准差为 1 的正态分布，则情 况如何。2. 问题分析对于问题一，题目给出了 4 个发射站与 4 个接收站数据传输矩阵 TRAF 和 传输时间的下界，以及一个工作模式的传输排列组合方式实例，问题需要将数 据传输矩阵 TRAF 分解成多个工作模式，并求出具有最短传输时间 LB 的调度 方案，最短传输时间即为各个模式的最短传输时间之和，即要求多个工作模式 的数据量之和最大，该问题核心就是将 D 分解成个工作模式，使得总时间u最小，可以考虑采用优化

7、调度算法，在矩阵中添加虚拟值，得到各工作模式tL对应的通信链接，最后再算出最大传输数据量，转换为最短传输时间。对于问题二，题目要求一般情况下的通信调度算法，此模型可以作为模型 一的推广，此时的矩阵不再是方阵，所以可以尝试将一般矩阵转化为方阵后按照模型一的算法再次求解，此时数据传输矩阵可以记为，表示nmijdD)(ijd第 i 个地面发射站到第 j 个接受站所用的时间，要解决的问题就是要将的nm 矩阵转化为方阵，然后再进行元素的拆分。另外由 mn 传输矩阵最后得到的一 些工作模式矩阵都应当删除对应扩展的行或者列，使其与传输矩阵 D 具有同样 的行和列。问题三已知在传输过程中数据包会以概率 发生错

8、误，这时候传输的数据 包中的数据有丢失，且传输的丢失量服从中心为 5，标准差为 1 的正态分布。 系统会在一个工作模式之后，检测数据是否有丢失，如果有丢失将要进行重新 传输。在这次重新传输过程中我们认为进行的是将整个工作模式再次进行传输， 并且在重新传输过程中不再发生错误，根据概率统计知识进行相关求解。- 4 -3. 符号说明4. 模型的假设影响卫 星通信调 度问题的 因素很多， 需要简化 模型，为此， 我们做以 下假设：（1）假设一个工作模式结束后，下一个工作模式立即开始，即转换模式为零延 迟；（2）假设所有线路的传输速率都相同，因此数据量可以以单位为秒的传输时间 计；（3）假设每一个传输模

9、式矩阵的每一行每一列都至多有一个非零的数据包；（4）假设各个工作模式下，每个发射站只能向一个接收站传输数据，每个接收 站也只能接收一个发射站的数据；（5）假设系统会在一个工作模式之后，检测数据是否有丢失；5. 问题一：最短传输时间模型5.1.模型的建立卫星通信的数据传输矩阵记为nnijdD)(ijd第 i 个地面发射站到第 j 个接受站所用的时间k ijp第 k 个工作模式中第 i 个发射站向第 j 个接收 站传输数据所用的时间k每一个被分解后的工作模式的最大传输数据量， 即最短传输时间D卫星通信数据传输矩阵tL各工作模式时间之和u数据传输矩阵被拆分的工作模式数量LB各传输模式的时间之和ix添

10、加的虚拟值- 5 -其中，表示第 i 个地面发射站到第 j 个接受站所用的时间。ijd数据传输时间记为，；ijijdLBijijiijjdrowdcol , 用表示传输矩阵 D 中非零元素的数目。第个工作模式记为：kmmk ijkpp)(其中表示第个工作模式中，从第 i 个发射站向第 j 个接收站传输数据k ijpk所用的时间。由于 TRAF 被分解为一系列的工作模式矩阵，所以有以下关系：mjmidpijk ij, 2 , 1 ;, 2 , 1 , LL记，表示每一个被分解后的工作模式的最大传输数据量，即 k ijjikp ,max最短传输时间，各工作模式的总时间。卫星通信调度的核心就是将 D

11、 ukktL1分解成个工作模式，使得总时间 LB 最小，于是问题一的调度问题可描述如下：u ukktL1minmin ukkpD15.2.模型的求解算法记，对于问题一，。同时为了最大程 nji niimTcolrowBLL , 1, 1,max,maxmaxnm 度的利用资源，每个传输矩阵的脉冲信号量是相等的。由此设计算法流程图如图 1- 6 -令u=0，Lt=0计算B值在D中添加虚拟值，使得D中各 行各列元素之和等于B判断D是否等于0令 ，在D中找出具有最小非零元 素的模式矩阵 。计算 ，令 ，将u个模式矩阵中 的虚拟值去掉1uuuuDDpttuLLup开始结束NY图 1 调度算法流程图在传

12、输矩阵 D 中，每行每列之和的最大值为 45，所以传输时间应该满足 45T。在 D 中添加虚拟值，得到虚拟矩阵D，使得每行每列元素之和都等于 45。因为除设11d、12d、14d、41d、42d、44d以外其他元素已经满足行及列的和为45，所以只需要分别给11d、12d、14d、41d、42d、44d分别加入虚拟值X1、X2、X3、X4、X5、X6017211 153 158139 1712610 641351546XXXXXX ，使加入的虚拟值为整数，- 7 -列出方程组763552741765412321XXXXXXXXXXXX即为 76355274112321XXXXXXXXX，取一组虚

13、拟值为：X1=7、X2=5、X3=0、X4=0、X5=0、X6=7得到的虚拟矩阵为111513610612179138151511127按照流程图，求解得到其中一种方案的 8 个工作模式虚拟矩阵以及对应的数据 传输线路如下：工作模式虚拟矩阵 1 0006060060000060工作模式虚拟矩阵 2 0300003030000003工作模式虚拟矩阵 3 0400400000400004123412341234123412341234- 8 -工作模式虚拟矩阵 4 4000000400400400工作模式虚拟矩阵 5 0600600000060060工作模式虚拟矩阵 6 0013000013013

14、0013000工作模式虚拟矩阵 7 7000007000070700工作模式虚拟矩阵 8 0200002000022000最后去掉虚拟值，得到传输数据的最短传输时间调度结果如表 3，括号内 的数字表示数据传输时间。1234123412341234123412341234123412341234- 9 -表 3 最短传输时间调度方案工作模式123456781到2（6 ）1(0)idle1(0)idle3(4)2(1)idle4(2)3(7)4(13)2到4（6 ）4（3）2(4)2(4)1(6)1(2)1(7)3(13)3到3（6 ）2（3）4(4)1(4)4(6)2(2)2(7)1(13)4到

15、1（6 ）3（3)3(4)4(4)3(6)3(2)4(0)2(13)5.3.模型结论及分析将每个工作模式所用时间最大值相加，即为所求的最短传输时间，即=6+3+4+4+6+2+7+13=45。结合前面的分析，又有45，所以本方案求得mintLtL的最小值是理想的，即本方案可行。另外，在调度算法流程中，矩阵 D 添加虚拟值的方法有很多种，所以最短 传输时间的调度方式也有很多种，这里没有一一列出，采用 MATLAB 编程可 以求解。有了最短传输时间的调度方案，就可以根据此方案进行数据的传输， 最大程度的节约时间，这是卫星通信过程现在也是今后的一个研究方向。6. 问题二：最短传输时间的一般算法6.1.模型的建立我们假设有 m 个发射站，n 个接收站，构成一个 m 行 n 列的传输矩阵 D，求 解具有最短传输时间的调度方案的一般算法。问题一中即为 m=n 的特殊情形， 对于mn的一般情形，我们需要将其扩展成为方阵（当mn时，可以增加列 数，当mn，增加行数，增加