数学建模卫星通信

卫星通信调度问题

摘要

这是一个卫星通信具有最短传输时间方案的制定问题。采用拆分法，即将时

间传输矩阵写成若干个矩阵的和，然后对这些矩阵最优化处理，最终得到最短传

0400输时间的方案：

0300 、

004040000004300000030030 ……在此方案下，最短传输时间

为：45s。

在此基础上，得到一般情况下具有最短传输时间的方案。先将矩阵补充成每行每列的和均为原矩阵最大行和列和的矩阵，同样运用拆分法， 每次从矩阵的最大值中拆分1组成每行每列最多只有1个1的若干矩阵的和，从而得到最短传输时间方案，此方案的最短传输时间就是拆分的矩阵的个数。

考虑在数据传输时以概率p发生错误，数据的丢失量X服从N(5,12)的正态

分布,传输量Y服从N(4,12)，传输量的分布函数：

Fyy21y42dt

所以，每个拆分后的传输矩阵的传输时间的分布函数为：

FmaxF(y1)*F(y2)*F(y3)*F(y4)F(y)

4则其密度函数为l(y)就是对上式求导，再对l(y)积分就可以得到最短传输时间的方案。

一、问题重述

卫星数字通信系统由一颗卫星和一组地面站组成。地面站扮演与地基通信网

之间的接口的角色。通过SS-TDMA技术，卫星可以为每个地面站发配连接时间。考虑这样的问题，在A地有4个发射站，在B地有4个接收站，表1给出了一个

44的数据传输矩阵，TRAFM是在发射站i和接收站j之间传输的数据量，由于

所有线路的传输速率都相同，因此数据量可以以单位为秒的传输时间计。

TRAF 1 2 3 4 colr 1 0 15 17 6 38 2 7 8 12 13 40 3 11 13 6 15 45 4 15 9 10 4 38 rowt 33 45 45 38 LB=45 表1. 数据传输矩阵TRAF及传输时间的下界

在此卫星上有一个转发器，允许在四个发射器和四个接收器之间进行任意的排列组合。这些连接即对数据传输矩阵中某个元素的一部分进行路由安排，称为一个工作模式。在一个模式中传输矩阵中某个元素的一部分就称为一个数据包。 工作模式也是一个44的矩阵M，其中每一行每一列都至多有一个非零的数据包。

正确的传输调度方案为星载转发器定义了一系列传输排列组合方式，以为矩阵TRAF中的通信量设计路由。也就是说，需要将TRAF分解为一系列的工作模式矩阵。可以将TRAF中的元素拆解开，一个被分解的元素将分布于多个数据包和多个传输模式中进行发送。一个工作模式的长度即为其中最长的数据包的长度。 （1）根据上述条件，确定此问题具有最短传输时间的方案。

（2）在（1）的基础上，要求给出一般情况下的具有最短传输时间的调度方案。 （3）若考虑传输过程中的以概率p发生错误，此时传输的数据包中的数据有丢失（即没有传输完），且传输的丢失量服从N(5,12)的正态分布，求解此时具有最短传输时间的方案。

二、 模型假设

1、 假设每次只能是一个接受站和一个发射站进行数据传输。

2、 假设所有线路的传输速率都相等。

3、假设问题1和问题2的数据在传输过程中没有数据丢失。 4、假设数据的传输不受天气和地理位置等自然条件的影响。

三、 符号说明

符号 说明 时间传输矩阵 TRAFMTRAF i时间传输矩阵的分解矩阵 （其中i是正整数） T 传输时间 X Y F f 传输过程中的数据丢失量 传输过程中的数据准确传输量 分布函数 概率密度函数 F max工作模式的长度的分布函数 lx

工作模式的长度的概率密度 四、 问题分析

本题首先要从题目中给出的具体情况求出其最短传输时间的调度方案，进而讨论一般情况下的方案，最后，若考虑传输过程中数据的丢失，讨论最短传输时间方案。根据题目中的要求，可以将时间传输矩阵中的元素拆解开，一个被分解的元素将分布于多个数据包和多个传输模式中进行发送，从而求出其最短传输时间的调度方案。

问题1

该问题只需讨论本题给出的具体情况，由上述分析可知，将题目中给出的时间传输矩阵分解为一系列矩阵的和，并对这些矩阵进行最优化即可得到最短传输时间。因此，我们将这些矩阵优化为每一行每一列都至多有一个同样的非零元素，这样就可以求得最短传输时间。因为拆分的矩阵每一行每一列都至多有一个非零元素，所以，同一行的元素必然在不同的矩阵中，将元素拆分后的传输时间大于等于同一行元素的和的最大值，即45s。

问题2

该问题既是在问题1的基础上，找出一般情况的求法。同样按照问题1的方法，我们将时间传输矩阵拆分成若干个矩阵的和，而这些矩阵正是由0和1组成的且满足每一行每一列至少有一个非零元素，这样的矩阵的个数就是传输所需的最短的时间，这样的传输方案就是我们所要求的传输方案。

问题3

若考虑传输过程中数据的丢失，那么我们同样按照前面两问的方法，将时间传输矩阵分成一系列由0和1组成的每行每列至多有一个非零元素组成的矩阵的和，但是，我们要考虑在传输过程中数据的丢失对传输时间的影响。根据《概率论与数理统计》的知识，已知丢失量的分布和出错率，我们可以求出工作模式的长度的分布情况，便可求出在这种情况下的数据传输的时间所满足的函数。

五、 模型建立与求解

模型一

071115 根据模型假设1和2，我们可以将矩阵 158139 拆分成下列

1712610613154矩阵之和，即

0711150400030015813900403000 = + 171261040000003613154000400300006+ 0070 + 0040 + 06000060600000057000000707000004400004000002 0002 + + 50000500005000000020200002000000 + 020020000020 + 000550000050 + 007007000000 据上述可得，

T=4+3+6+7+4+5+2+2+5+7=45(s)

因此，传输时间最短为45s的传输方案就是按照上述各矩阵传输数据。

模型二

在模型一的基础上，我们得出更一般的方法：先将矩阵补充成每行每

列的和均为原矩阵最大行和列和的矩阵，同样运用拆分法， 每次从矩阵的

最大值中拆分1组成每行每列最多只有1个1，其余全为0的若干矩阵的和， 算法思路如下：例如题中所给矩阵，先将其补充成每行每列和相等的矩阵：

7121115158139（每行每列和均为45），令最大值17处为1，并且令其所在

171261061315110121115的行与列中的数值全部为0， 得矩阵 018013090 ，再令此矩阵中的最

0131511大值15（如果最大值不止一个，则按从左往右，从上到下的顺序找到第一个）

0

处为1，继而得到 08

0

01000101

1300800 ，然后得 ，最终可以得00100001315000100001010010000010出第一次拆分出来的矩阵 。然后用原矩阵减去拆分出来的

7121114157139矩阵，得到差矩阵 ，继续拆分直至结束。

16126106131411从而得到最短传输时间方案，此方案的最短传输时间就是拆分的矩阵的个数。编程得到结果为：

. .

.

因此，最短时间传输方案就是按照上述的0、1矩阵进行传输的方案，此方案下的最短传输时间是45s。

模型三

考虑传输过程中的数据丢失，由题知X~N(5,12),则Y=1-X~N(4,12)：

1 fy2y42

则 Fyftdt

y FmaxFy

4' lyFmax

用Matlab计算的结果为：最短时间的期望为E=43s。

六、 模型评价

以上所有的模型都做出了一些理想化的假设，即不考虑不同数据线传输速度的差异、自然因素等问题。

优点：这些假设使得我们既可以用数学建模的方法来解决实际生活中的问

题，又在一定程度上反映了卫星传输数据的实际情况。

缺点： 这些假设的存在，弱化了这些模型的实际意义。并且，一些参数

的理想化也有缺点。例如，在模型三中，我们假设数据传输过程中数据以概率p发生错误，且传输的丢失量服从正态分布，这些在现实生活中都是不存在的。

七、 模型推广

此模型是建立在简单的一对一的传输情况，它也可以推广到多对多的传输情况。运用同样的拆分法求解问题，既然是多对多数据传输，那么拆分成的工作模式的矩阵每行每列的的元素个数就没有条件，我们任然按照一般情况下的模型求解，利用穷举法编程即可实现。

八、 参考书目

[1] 苏小红 陈惠鹏 孙志岗 《C语言》 ISBN 978-7-121-03782-5

[2] 陈慧南 《数据结构——使用C++语言描述》 ISBN 978-7-115-18402-3 [3] 谢金星 叶俊 《数学模型》 ISBN 978-7-04-011944-2

[4] 盛骤 谢式千 潘承毅 《概率论与数理统计》 ISBN 978-7-04-0236-9

九、 附 录

模型二：

程序：

#include using namespace std; int n;

int **matrix; int **example; int **acopy; int fuck=0; //构建矩阵

void inicial() {

int i;

matrix=new int* [n]; for(i=0;imatrix[i]=new int [n]; example=new int* [n]; for(i=0;iexample[i]=new int [n]; acopy=new int* [n]; for(i=0;iacopy[i]=new int [n]; }

//判断是否继续拆分 bool go_on(int **a) {

int i,j;

for(i=0;iif(a[i][j]>0) return true; return false; }

void deletes(int **c,int **a,int **b) {

int i,j;

for(i=0;ic[i][j]=a[i][j]-b[i][j]; }

//释放指针空间

void clear(int **a) {

int i,j;

for(i=0;i//将a矩阵复制b矩阵，此程序中是将每次的差矩阵作为下一步拆分时的原矩阵 void xcopy(int **a,int **b) {

int i,j;

for(i=0;i//拆分成每行每列最多有一个1的矩阵，其余项均为0，并将拆分所得矩阵与差//矩阵分别输出 void findmax() {

int k=n; int i,j;

int row,col,maxi; xcopy(acopy,matrix); clear(example); while(k--) {

row=col=maxi=0; for(i=0;iif(matrix[i][j]>maxi) {

row=i; col=j;

maxi=matrix[i][j]; } if(maxi>0) {

example[row][col]=1;

for(i=0;imatrix[row][i]=matrix[i][col]=0; } else

break; }

deletes(matrix,acopy,example); cout<<++fuck<for(j=0;jcout<cout<<\" \"; for(j=0;jcout<cout<//主函数，主要通过一个循环，将每次的拆分所得矩阵与差矩阵分别输出，并输//出拆分矩阵的个数 int main() {

system(\"color F0\"); cin>>n; inicial();

int i,j,answer; for(i=0;icin>>matrix[i][j];

for(answer=0;go_on(matrix);answer++) {

findmax(); }

cout<模型三

>> clear >> syms x

>> int(exp(-power(x+4,2)/2)) ans =

1/2*pi^(1/2)*2^(1/2)*erf(1/2*2^(1/2)*x+2*2^(1/2))

>> power(ans,4) ans =

1/4*pi^2*erf(1/2*2^(1/2)*x+2*2^(1/2))^4

>> diff(ans) ans =

pi^(3/2)*erf(1/2*2^(1/2)*x+2*2^(1/2))^3*exp(-(1/2*2^(1/2)*x+2*2^(1/2))^2)*2^(1/2)

>> int(x*ans,x,0,inf) ans =

int(x*pi^(3/2)*erf(1/2*2^(1/2)*x+2*2^(1/2))^3*exp(-(1/2*2^(1/2)*x+2*2^(1/2))^2)*2^(1/2),x = 0 .. Inf)