2021卫星通信调度问题

卫星通信调度问题 卫星通信调度问题 摘 要 卫星通信系统通过SS-TDMA 技术使得卫星可以为每个地面站传输数据，而卫星上的转发器，允许在n 个发射器和n 个接收器之间进行任意的排列组合，因此我们需要找到一个最短传输时间的优化方案。

针对问题一，对此我们根据SS-TDMA 工作原理，提出算法，利用“拆分法”将待传输的数据矩阵进行拆分，分次发送，并使总的传输时间所用最小。因为一个工作模式的长度即其中最长的数据包的长度，为此我们对矩阵TRAF 进行优化处理，使得每组传输模式的数据量尽可能相等，这样进行下去，传输时间必定最小。因此我们选择矩阵TRAF 中colr 值或rowt 值等于LB 值（colr 值和rowt 值中最大的一组数组）所在的行或者列，确定该行或者列数组中的最大元素。当确定最大元素 ij a 后，将该元素所在位置处赋值为s （本文中s 取1），并令第i 行j 列中其他元 素为0，产生一个新的矩阵。然后再从该矩阵找到剩余元素中的最大元素＇＇j i a ，重复上述步骤，找到每行每列中至多有一个非零数s 的模式矩阵B 。再用A 减去B ，得到新的矩阵 n A ，循环上述步骤，找到所有的工作模式矩阵 n B 。用MATLAB 对该 过程进行编程求解，得到最优方案，并对模型进行检验。

针对问题二要求的一般情况，我们将数据发送站点数目取m ，数据接收点数目取为n ，这样我们得到一个m 行n 列的一般矩阵。这样我们只需要在问题一中算法中将TRAF 矩阵改成一般矩阵使用MATLAB 进行求解即可得到一般情况下的最优方案。

对于问题三的问题，传输过程中存在数据丢失，且每个数据包中的数据丢失量服从正态分布的概率形式，因此，我们通过求所用时间的期望值来考虑这种概率影响，首先针对一个工作模式矩阵，在确认了其非零行的数目以后，从第一个数据包开始，先求出每个数据包丢失数据量的期望值，且丢失的数据要重新发送，而传输成功的数据就不用再发，因此，在求得每个数据包丢失数据量中，找出其最大值，就是在这种工作模式矩阵正常发送时间基础上需要多计算的那部分额外时间。最后，求出每个工作模式矩阵的这个额外时间后，进行累加，这也是一个期望值，表示的意义就是在发送数据时若发生数据丢失，考虑数据丢失的概率因素对于发送时间的增量。

关键词：卫星通信调度，拆分法，微分思想，MATLAB,数据传输概率 一、问题重述 卫星数字通信系统由一颗卫星和一组地面站组成。地面站即扮演与地基通信网络之间的接口角色。通过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 1 3 9 45 3 17 12 6 10 45 4 6 13 1 5 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 17 0 0 0 3到1 17 4 0 13 0 0 4到2 13 col 38 40 45 38 LB=45 正确的传输调度方案为星载转发器定义了一系列传输排列组合方式，以为矩阵TRAF中的通信量设计路由。也就是说，需要将TRAF分解为一系列的工作模式矩阵。可以将TRAF中的元素拆解开，例如在表2所示的模式中只传输了TRAF31 的部分内容。一个被分解的元素将分布于多个数据包和多个传输模式中进行发送。一个工作模式的长度即其中最长的数据包的长度。那么：
1. 请找出此问题的具有最短传输时间的调度方案；

2. 给出一个一般情况下的具有最短传输时间调度方案或者求解具有最短传输时间的调度方案的一般方法（或算法）；

3. 如果传输时会以概率发生错误，此时传输的数据包中的数据有丢失（即没有传输完），且传输的丢失量服从中心为5，标准差为1的正态分布，则情况如何。

二、模型假设 1.在发送站与接收站之间传输的数据量为非负整数；
所有线路的传输速率都相同，因此数据量以单位为秒的传输时间计；

2.同一时刻，不能有两个或两个以上的脉冲信号传送到同一个转发器，即假设工作模式矩阵的每一行每一列至多有一个非零数；

3.假设在两种工作模式之间不需要处理时间，则数据传输矩阵TRAF的传输时 间只等于其所对应的所有工作模式的传输时间之和。

5、若发生数据丢失，假设分成两个步骤，第一步，数据发送站在第i个工作模式正常发送时间段错误！未找到引用源。内等待确认信息，第二步，若收到确认信息，则数据没有丢失，若没有收到信息，则将丢失部分数据进行重新发送，且假设第二步发送丢失数据时，不再有数据损失，可一次性完成；

三、符号说明 表3 符号说明表 符号表示的意义 TRAF 数据传输矩阵 a发射站i和接收站j之间传输的数据量 ij LB信号传输完成所需的最短时间 A传输矩阵（n=1的时候，A矩阵即是TRAF矩阵）
n B数据传输过程中，每次传输的模式矩阵 n P发生数据丢失的概率 E每个工作模式传输数据量的期望值 i add传输发生错误时丢失的数据量 四、问题分析及模型建立 （一）问题一的分析和模型建立求解：
（1）问题一的分析：
该问题要求我们对于已经给定的数据传输矩阵，设计一种数据传输转换方法，使在满足要求的情况下使传输时间最少。我们利用“拆分法”将待传输的数据矩阵进行拆分，分次发送，并使总的传输时间所用最小。

一个工作模式的长度即其中最长的数据包的长度，为此我们对矩阵TRAF 进行优化处理，从中取出的状态矩阵的各个元素尽可能相等，这样进行下去，传输时间必定最小。

（2）问题一的模型建立和求解：
第一步：我们找到矩阵TRAF=??? ?? ???????91515610612179138151711107中colr 值或rowt 值等于 LB 值的行或者列（在问题一中我们选择在colr 值为45的第3列）确定该行或者列数组中的最大元素。

第二步：当确定最大元素 ij a 后，将该元素所在位置处赋值 为1，并令第i 行j 列中其他元素为0，产生一个新的矩阵。

我们在第三列中找到最大元素为15，于是令其所在的第4行第3列的其他元 素都为0，而15所在处改为1，得到???? ? ???? ???0100100121790815170107。

第三步：再从得到的新矩阵找到剩余元素中的最大元素＇＇j i a ，比如在 ????? ? ??????0100100121790815170107中找到最大元素17，有两组可能，我们选择第一组，即第一列中的最大元素17。

s 工作模式长度 第四步：循环上述步骤，得到???? ????? ???010000019080170100.....最后得到模式矩阵1B =? ? ??? ???? ???0100 000100101000，即第一波数据传输的模式。然后用A 矩阵减去1 B ，得到剩余矩 阵2A =???? ? ???????4141361061216913715141170，2A 代替A 参与循环，得到模式矩阵2 B ,3B ,...,45B （具体模式矩阵即传输方案见附录），传输时间T=1+1+1+...+1=45,即得到一种满足最短传输时间要求的调度方案。

（二）问题二的分析和模型建立求解：
图1 问题一MATLAB 程序部分运算结果 根据“拆分法”模型分析可得，对任意一个矩阵TRAF={}ij n n a ?， 我们从矩阵 中colr 值或rowt 值等于LB 值（colr 值和rowt 值中最大的一组数组）所在的行或者列开始取，确定该行或者列数组中的最大元素。对于比较庞大的矩阵我们可以通过EXCEL 软件很快找到矩阵最大元素的位置。当确定最大元素 ij a 后，将该元 素所在位置处赋值为1，并令第i 行j 列中其他元素为0，产生一个新的矩阵。然后再从该矩阵找到剩余元素中的最大元素＇＇j i a ，重复上述步骤，找到每行每列中至多有一个非零数1的模式矩阵B 。再用A 减去B ，得到新的矩阵n A 。如此再循环，我 们便可找到所有的工作模式矩阵 n B 。最后用MATLAB 对该过程进行编程求解，就能 得到一般情况下的最优方案，使得问题一模型得以推广，也可对模型进行检验。

所有模式矩阵n B 满足如下关系：n B B B B A ++++= 321。

为方便演示推广，我们取一55?的TRAF 矩阵????? ?? ?????????=1233243213232131124213120A 对其进行推广。

表4. 数据传输矩阵TRAF 及传输时间的下界 TRAF 1 2 3 4 5 rowt 1 0 2 1 3 1 7 2 2 4 2 1 1 10 3 3 1 2 3 2 11 4 3 1 2 3 4 13 5 2 3 3 2 1 11 colr 10 11 11 12 9 LB=13 使该传输矩阵进入问题一所建模型MATLAB 的程序算法，计算结果见附录，我们截取部分结果如下图：
从该推广例子我们可以看到，对于问题一所建立的拆分模型我们可以在模型二 中进行推广。当任给一个TRAF 传输矩阵，我们只需要将该矩阵编写入问题一原有MATLAB 算法程序，并将矩阵中colr 值或rowt 值等于LB 值所在的行或者列在相应的位置更改后，运行程序，即可得到一种满足最短时间要求的传输方案。

（三）问题三的分析和模型建立求解：
（1）问题三的分析：
由问题三可知，数据包可能以概率发生数据丢失，且丢失量服从中心为5，标准差为1的正态分布。由于数据的丢失是以概率发生的，且最多数据包会丢失完，即数据的丢失的最大量是数据包的量。同时可知，当数据发生丢失时，发射站会重新发送丢失的那部分数据，且这次传输不再考虑数据丢失。借此思路，可以给出一种算法，即在不发生数据丢失的最优传输方案下，考虑发生丢失数据的情况，并利用该算法求出数据传输总时间（也就是传输的数据量）的期望值i E 。

图2. 问题二推广模型部分运算结果截图 （2）问题三的模型建立：
假设数据包丢失概率为P ,则每个工作模式下数据包传输成功的概率是 n P )-1（，其中n 指的是每个工作模式矩阵中非零元素的个数。而数据包丢失的概 率则是：))1(1n P --（，那么每个工作模式下数据传输时间（也就是传输的数据量）
的期望值i E = 1*)1()1)()-1-1n P add P n -++（（，其中2 )5(2 21 -- =s e add π 。

于是，整个数据包传输完成所需时间的期望值为 ∑=45 1 i i E 。

（3）问题三的模型检验：
针对上述模型，我们可以知道，如果0=P ,即数据传输没有数据丢失，那么 45 =i E ，或者接近于45。于是我们通过MATLAB 对该模型进行编程求解，进行检 验。截取部分结果如下：
B = 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 sumE = 45.0019 t = 45 A = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 通过MATLAB验算，我们可以看到sumE = 45.0019，与LB=45接近，模型正确！ 五、模型的评价 5.1模型的优点 该模型对于传输矩阵的要求不高，不需要传数矩阵必须是方阵，任何一个n m 的矩阵都可以在该模型中进行推广求解，具有广泛的适用性。另外，该模型中模式矩阵长度s可以是1，也可是是0.1，充分运用了微分思想，使得该模型准确性更高。

5.2模型的缺点 本文所建模型，工作模式长度s较小为1，在提高准确性的同时，却使得工作模式更为繁杂，共有45种工作模式。另外，通过调查资料我们还发现，在现实生活中，关于卫星在基于TCP协议下是如何进行数据的传输与分配还相当复杂，数据的丢失处理也要考虑更多更复杂的因素，因此，本文中所建立的模型考虑因素不全面，模型比较简单。

六、模型的改进与推广 我们建立的模型可以容易地解决优化调度类或者数据传输类的问题，因此可以推广到很多有关调度或者网络数据传输过程中进行求解最优方案。但由于本文没有考虑工作模式之间的时间间隙，所以与实际情况有较小的出入。因此，只有针对实际情况，提出更合理的约束条件，才能建立出更符合实际的数学模型加以解决。

参考文献：
[1] 方炎申，邹凯，陈英武，陈邓安. 卫星通信系统星上处理中的调度问题及其算法 ,计算机仿真第22卷第5期 35-37页 2021,5 附录：
A=[ 0 7 11 15;15 8 13 9;17 12 6 10;6 13 15 4]; s=1; %确定工作模式长度为1 t=0; %t为模式个数 p=0.1; %假设传输错误概率为0.1 sumE=0; %期望为sumE while rank(A)~=0 B=zeros(size(A));a=A; [x0,y0]=find(a(3,:)==max(a(3,:)));%k0=find(max(a(3,:))); %找到A第三行中最大元的坐标 x0=3;y0=y0(1); %可能有多组值，任意取一组坐标，我们取的第三行第一组 B(x0,y0)=1; %将B中与A最大元坐标一致处赋值为1 a(x0,:)=0;a(:,y0)=0; %将A第三行最大元对应的行和列赋值为0（相当于叉掉最大元的行列）while rank(a)~=0 [x1,y1]=find(a==max(max(a))); %找到不在A第三行最大元的行和列的最大元的坐标 x1=x1(1);y1=y1(1); %可能有多组值，任意取一组坐标，我们取的第一组 k1=a(x1,y1); if k1>0 B(x1,y1)=1; %若a最大元非零将B中与最大元坐标一致处赋值为1 else B(x1,y1)=0; %若a最大元为零将B中与最大元坐标一致处赋值为0 end a(x1,:)=0;a(:,y1)=0; %将上面最大元对应的行和列赋值为0（相当于叉掉最大元的行列）end B(B==1)=s %将B中为1的元全部替换为s，即得到一个数据包 n=max(size(B(B~=0))); add=(1/sqrt(2*pi))*exp(-(s-5)^2/2); % 每个模式下传输错误的数据丢失量 E=1*(1-p)^n+(1+add)*(1-(1-p)^n); sumE=sumE+E t=t+1 A=A-B end