卫星通信调度问题建模

卫星通信调度问题摘要卫星数字通信系统由一颗卫星和一组地面站组成,正确的传输调度方案为星载转发器定义了一系列传输排列组合方式，以为矩阵RA中的通信量设计路由.本文针对卫星通信数据传输时间进行了调度，建立模型，解决了一般情况下的最短传输时间的算法.对于问题一中的数据传输矩阵，我们建立了最短传输时间模型，详尽地写出了具体的算法,画出了对应的流程图。通过采用添加虚拟值的方法，使得每行每列之和都为LB,然后对数据传输矩阵进行合理的拆分，并对每个工作模式的传输时间求和，即为最短传输时间。问题二即为问题一的推广，对于更为普遍的型的数据传输矩阵,我们在问题一中的算法中添加了判断和n的大小关系并将原数据传输矩阵构造成为N阶方阵这一步，结合问题一中的算法，从而得到了一般情况下最短传输时间调度方案。问题三中，我们在对样本进行假设检验之后,求出了在传输过程中数据包发生丢失的情况下传输时间的数学期望.我们假设系统会在一个工作模式完成之后，检测数据是否有丢失，如果有丢失将要进行重新传输.在这次重新传输过程中我们认为进行的是将整个工作模式再次进行传输,并且在重新传输过程中不再发生错误,接着根据概率统计知识进行相关求解。模型改进时考虑了卫星在传输数据量的过程中,存在一种自动纠错功能，即传输数据包时，数据丢失量在某一范围内，卫星中继站会自己分析补足该数据包,这样缩短了数据传输时间，增强了模型的适用性。关键字 卫星通信调度 虚拟添加值 传输数据错误 最短传输时间1. 问题重述卫星数字通信系统由一颗卫星和一组地面站组成.地面站即扮演与地基通信网络之间的接口角色。通过-TDMA(卫星转发，时分复用）技术，卫星可以为每个地面站发配连接时间。考虑这样的例子,在A地有4个发射站，在地有4个接收站，表 Error! Bookmark not defined.给出了一个的数据传输矩阵。TRAFi是在发射站i和接收站j之间传输的数据量。由于所有线路的传输速率都相同,因此数据量可以以单位为秒的传输时间计.表 Error! Bookmark not defined. 数据传输矩阵TRA及传输时间的下界TRAF1234rowi10711533258139453112104546131543olj8404538B=4在此卫星上有一个转发器,允许在四个发射器和四个接收器之间进行任意的排列组合。表2给出了一种排列组合方式，将发射站到4分别连接到接收站,，2。这些连接即对数据传输矩阵中某个元素的一部分进行路由安排,称为一个工作模式。在一个模式中传输矩阵中某个元素的一部分就称为一个数据包。工作模式也是一个44的矩阵M，其中每一行每一列都至多有一个非零的数据包。表 Error! Bookmark not defined. 工作模式实例与对应调度方案123站点数据包1001101到1120009到4350003到154013004到213colr38404538LB45正确的传输调度方案为星载转发器定义了一系列传输排列组合方式,以为矩阵TRAF中的通信量设计路由。也就是说，需要将TRAF分解为一系列的工作模式矩阵。可以将TR中的元素拆解开，例如在表2所示的模式中只传输了TAF1的部分内容。一个被分解的元素将分布于多个数据包和多个传输模式中进行发送.一个工作模式的长度即其中最长的数据包的长度。那么：1。 请找出此问题的具有最短传输时间的调度方案;2。 给出一个一般情况下的具有最短传输时间调度方案或者求解具有最短传输时间的调度方案的一般方法(或算法)；3。 如果传输时会以概率发生错误,此时传输的数据包中的数据有丢失(即没有传输完)，且传输的丢失量服从中心为5，标准差为的正态分布,则情况如何。2. 问题分析对于问题一，题目给出了4个发射站与4个接收站数据传输矩阵TRAF和传输时间的下界，以及一个工作模式的传输排列组合方式实例,问题需要将数据传输矩阵RF分解成多个工作模式,并求出具有最短传输时间LB的调度方案,最短传输时间即为各个模式的最短传输时间之和,即要求多个工作模式的数据量之和最大,该问题核心就是将D分解成个工作模式，使得总时间最小，可以考虑采用优化调度算法，在矩阵中添加虚拟值，得到各工作模式对应的通信链接，最后再算出最大传输数据量，转换为最短传输时间。对于问题二，题目要求一般情况下的通信调度算法，此模型可以作为模型一的推广，此时的矩阵不再是方阵,所以可以尝试将一般矩阵转化为方阵后按照模型一的算法再次求解,，此时数据传输矩阵可以记为，表示第i个地面发射站到第j个接受站所用的时间，要解决的问题就是要将的矩阵转化为方阵，然后再进行元素的拆分.另外由n传输矩阵最后得到的一些工作模式矩阵都应当删除对应扩展的行或者列，使其与传输矩阵D具有同样的行和列.问题三已知在传输过程中数据包会以概率发生错误，这时候传输的数据包中的数据有丢失，且传输的丢失量服从中心为5，标准差为1的正态分布.系统会在一个工作模式之后，检测数据是否有丢失，如果有丢失将要进行重新传输。在这次重新传输过程中我们认为进行的是将整个工作模式再次进行传输，并且在重新传输过程中不再发生错误,根据概率统计知识进行相关求解.3. 符号说明第i个地面发射站到第j个接受站所用的时间第k个工作模式中第i个发射站向第j个接收站传输数据所用的时间每一个被分解后的工作模式的最大传输数据量，即最短传输时间卫星通信数据传输矩阵各工作模式时间之和数据传输矩阵被拆分的工作模式数量各传输模式的时间之和添加的虚拟值4. 模型的假设影响卫星通信调度问题的因素很多，需要简化模型，为此，我们做以下假设:(）假设一个工作模式结束后，下一个工作模式立即开始,即转换模式为零延迟;（2）假设所有线路的传输速率都相同，因此数据量可以以单位为秒的传输时间计；(3）假设每一个传输模式矩阵的每一行每一列都至多有一个非零的数据包；（4）假设各个工作模式下，每个发射站只能向一个接收站传输数据，每个接收站也只能接收一个发射站的数据；（5）假设系统会在一个工作模式之后，检测数据是否有丢失；5. 问题一：最短传输时间模型5.1. 模型的建立卫星通信的数据传输矩阵记为其中,表示第i个地面发射站到第j个接受站所用的时间。数据传输时间记为，;用表示传输矩阵D中非零元素的数目.第个工作模式记为：其中表示第个工作模式中，从第i个发射站向第j个接收站传输数据所用的时间.由于TAF被分解为一系列的工作模式矩阵，所以有以下关系:记，表示每一个被分解后的工作模式的最大传输数据量,即最短传输时间,各工作模式的总时间。卫星通信调度的核心就是将D分解成个工作模式，使得总时间L最小，于是问题一的调度问题可描述如下：5.2. 模型的求解算法记，对于问题一,。同时为了最大程度的利用资源,每个传输矩阵的脉冲信号量是相等的。由此设计算法流程图如图图 1调度算法流程图在传输矩阵中，每行每列之和的最大值为45,所以传输时间应该满足。在中添加虚拟值,得到虚拟矩阵，使得每行每列元素之和都等于4。因为除设、以外其他元素已经满足行及列的和为4，所以只需要分别给、分别加入虚拟值X1、X2、X3、X4、X5、X6,使加入的虚拟值为整数，列出方程组即为，取一组虚拟值为:1=、X2=5、X3=0、X4=0、X5=、X67得到的虚拟矩阵为按照流程图,求解得到其中一种方案的8个工作模式虚拟矩阵以及对应的数据传输线路如下：工作模式虚拟矩阵1 工作模式虚拟矩阵2 工作模式虚拟矩阵3 工作模式虚拟矩阵 工作模式虚拟矩阵 5 工作模式虚拟矩阵6 工作模式虚拟矩阵7 工作模式虚拟矩阵8 最后去掉虚拟值,得到传输数据的最短传输时间调度结果如Error! Reference source not found.,括号内的数字表示数据传输时间。表Error! Bookmark not defined. 最短传输时间调度方案工作模式134581到(6)1（0）ide1(0）idle（4）（1)dle4(）3（）4(13）2到(6)4（3）2（4）2(）（6)1(）（7)3(13）3到3（6）2（3）(）1(4）4（6）2（2）2(7）（3）4到1（6)3（3）3（）4（4)（6)(2)4（)2（13)5.3. 模型结论及分析将每个工作模式所用时间最大值相加,即为所求的最短传输时间，即=+3+4+4+6+2+7+13=.结合前面的分析，又有，所以本方案求得的最小值是理想的，即本方案可行。另外，在调度算法流程中,矩阵D添加虚拟值的方法有很多种,所以最短传输时间的调度方式也有很多种，这里没有一一列出，采用MATL编程可以求解。有了最短传输时间的调度方案，就可以根据此方案进行数据的传输，最大程度的节约时间,这是卫星通信过程现在也是今后的一个研究方向。6. 问题二：最短传输时间的一般算法6.1. 模型的建立我们假设有m个发射站,个接收站，构成一个行n列的传输矩阵D,求解具有最短传输时间的调度方案的一般算法。问题一中即为m=的特殊情形，对于的一般情形,我们需要将其扩展成为方阵（当时，可以增加列数，当,增加行数，增加的元素均为0,方阵仍旧计为）,此时数据传输矩阵可以记为，表示第i个地面发射站到第j个接受站所用的时间,此问题的关键是要将的矩阵转化为方阵，使其成为行列相等的特殊情形，然后便可运用问题一中的方法进行求解。6.2. 模型理论算法此时的算法需要在问题一的算法基础上，进行方阵的转换，具体算法如下：输入：传输矩阵D输出：最短传输时间tp 1:判断m和n的大小关系,若，转下一步；否则当时，构造的方阵,当时,构造Nn的方阵.Step:计算LB值,即Step ：在D中添加虚拟值,使得D中各行各列元素之和都等于LB。Step 4：令u，C=。Step 5:如果D0，,转t6，否则转Step7。tep：令u=u+1，在D中找出具有最小非零元素的模式矩阵。计算，令D=D-，=C+。转tep .Stp 7:将个工作模式矩阵中的虚拟值都去掉.Step 8:若mn,转下一步，若mn，删除每个模式矩阵对应于虚拟矩阵中扩展的行和列。Sp :输出C以及个工作模式矩阵。ep 0:算法停止。个工作模式即为一种最优方案,C即为最短传输时间。6.3. 模型求解根据上面的算法,我们可以运用MLAB进行编程，运行该程序可以解出一种满足要求的最优方案。对于的情形如，运行程序得以上求出的工作模式的总传输时间C为4数据传输矩阵D的传输时间下界为45可得CL，程序运行成功，所求方案为一种最优方案.对于的情形如，运行程序得以上求出的工作模式的总传输时间为45数据传输矩阵的传输时间下界L为45可得C=LB,程序运行成功，所求方案为一种最优方案。对于的情形如,运行程序得以上求出的工作模式的总传输时间为5数据传输矩阵的传输时间下界LB为45可得C=，程序运行成功,所求方案为一种最优方案.7. 问题三：传输数据错误的调度模型7.1. 样本的假设检验问题三已知了在传输过程中数据包会以概率发生错误，这时候传输的数据包中的数据有丢失，且传输的丢失量服从中心为5，标准差为的正态分布。由于做出决策的依据是一个样本,我们提出两个相互对立的假设和当实际上为真时仍可能做出拒绝的决策,且这种可能性是无法消除的，因此自然希望将犯这类错误的概率控制在一定限度之内，即给出一个较小的数，使犯这类错误的概率不超过，即使得为了确定常数，我们考虑统计量，由于只允许犯这类错误的概率最大为,令由于当为真时,由标准正态分布分位点的定义得因而,若的观测值满足,则拒绝，即表示卫星中继站可能存在某些问题，导致数据的丢失量变得更大。此时我们可以采用作为传输数据丢失量的样本均值来估计需要传输数据的长度。7.2. 模型的建立与求解假设系统会在一个工作模式之后,检测数据是否有丢失，如果有丢失将要重新传输。在这次重新传输过程中我们认为进行的是将整个工作模式再次进行传输，并且在重新传输过程中不再发生错误.因为丢失量,所以可以得到数据传输的丢失量的概率密度函数为 则不发生丢失的概率(既x0的概率）为，记为；设总共有个工作模式，每个工作模式中个数据包，每个工作模式的工作长度用表示。则在一个工作模式中发生错误且丢失的概率是。一个工作模式的长度的数学期望为。由于每个工作模式相互独立，那么整体传输的长度的数学期望即每个工作模式长度的数学期望之和。由此可以得到在整个传输过程中的传输长度的数学期望为:7.3. 模型的改进由于上述模型假设的是重新传输过程中进行的是将整个工作模式再次进行传输，这必然会浪费资源,通过查阅资料得知，卫星在传输数据量的过程中，存在一种自动纠错功能，即传输数据包时,数据丢失量在某一范围内,会自己分析补足该数据包,这是因为数据之间具有很强的相关性，这种情况下，该数据包就可默认为传输成功，不需要重新发送。而丢失量超过某一个范围无法纠正时，接收器就需反馈信息，要求相应的发射器对该数据包进行重发。我们设定数据量丢失范围在0,0的区间内,卫星可以纠正补足该数据包。传输数据丢失数据包Y的期望值为由于我们设定数据量丢失范围在0，20%，而丢失数据包Y的最大期望值最大为5。因此当数据包超过2个值时，我们认为丢失的数据包都能经过微型自动纠错功能纠正补足数据，所以只需要考虑数据包的传输范围，且服从均匀分布。根据丢失数据的期望值与标准差，满足的正态分布，求出丢失数据需要重新传输的概率如下:于是求得整体需要传输的概率为.624；那么根据传输长度以及出错的概率可以得到整个传输过程中的传输长度的数学期望为：7.4. 结论及分析在进行传输长度的估计之前，假设检验是有必要的,这样可以从一定程度上节省传输数据时间.当重新传输过程中进行的是将整个工作模式的再次传输时，得到了整个传输过程中的传输长度的数学期望为:在模型的改进中，考虑了卫星通信的自动纠错功能，这样又一次减少了整个传输过程的传输时间,求得了这样情况下的传输长度时间数学期望，应该是较佳的调度方案。8. 模型的优缺点及展望8.1. 模型一和模型二的优缺点优点：采用添加虚拟值构造虚拟矩阵的方法不仅具有实用性,而且操作起来简单, 易于实现； 第一和第二个问题的算法步骤简单，可以使得读者一目了然，且能对不同 的传输矩阵求解，具有广泛性.缺点:对于第一和第二个问题中所添加的虚拟值构成的方程组,我们只是任意取 了一组解，没有详尽所有可能的虚拟值的解,所以不能求出所有可能的方 案种数。8.2. 模型三的优缺点优点：在求解之前考虑了题目所给样本数据的假设检验,并对模型进行了改进， 考虑了卫星在传输数据量的过程中，存在一种自动纠错功能。缺点：没有考虑工作模式的交换时间。8.3. 模型的展望卫星通信的调度问题是卫星通信的发展方向。本文建立的模型可以解决卫星通信系统星上处理中的调度问题.其次,错误概率的计算考虑了现实意义，其思路与方法具有一定的借鉴意义.该模型可用于某些时间约束下的多目标运输问题，在实际应用时还需注意编写具体的程序。9. 参考文献1 方炎申，周凯，陈英武，陈邓安卫星通信系统星上的调度问题及其算法M。长沙：国防科技大学出版社.2005;2 吕洪生，杨新德实用通信卫星工程M.成都：电子科技大学出版社，1994；3贺仁杰.成像侦察卫星调度问题研究D。长沙：国防科技大学博士学位论文，24;文中如有不足，请您指教！- 17 - / 17