谈谈通信网络调度问题的建模与算法
通信网络作为计算机间的信息传输，笔者主要研究如何以最优的方式安排信息的传输，使传输完所有的信息所用的总通信时间最少，这个时间被称为完工时间。
摘要：阐述了通信网络调度问题数学建模，探讨了通信网络调度问题，进行了通信网络应用实例与结果分析，研究在一个网络中如何安排一些文件的传输，使得完成全部文件传输的工作时间为最短。
关键词：传输时间;计算机容量;时间表问题;完工时间;最大基数匹配算法
随着知识和网络的发展，越来越多的人使用计算机来实现与世界的交流，网络通信已经占领了通信系统中的主导地位，所以技术人员要合理地安排信息的传输，使得信息在传输过程中不会发生碰撞，而且还要使传输时间不能过于长。上述的这个过程属于时间表问题。就复杂性分类，大部分的时间表问题属于NP-困难问题，不同类型的时间表问题在算法上有很大的差别。因此，大多数时间表问题当其规模相当大时，最优解的寻求是困难的。对于一个属于NP-困难的规模较大的时间表问题，为了很快地计算出最优解，常使用一些多项式时间的近似方法，且要求近似方法求得的近似解能比较好地接近问题的最优解[1]。笔者研究的通信网络的3种情况(情况A，情况B，情况C)都是规模比较小的问题，与其他离散最优化问题一样，规模较小的时间表问题可以使用“穷举方法”来求得其最优解。针对同一问题可以设计不同的穷举方法，较简单的穷举方法比繁琐的穷举方法可显著地提高计算效率。但是NP-困难问题的任何穷举方法只能是指数性质的，它的计算时间随着问题的规模的增大而呈指数的增长。笔者利用图论和最大基数匹配算法解决了3种情况下的通信问题，并且证明了根据3种情况所计算出的结果都是最优的。
1 通信网络调度问题数学建模
通信网络作为计算机间的信息传输，笔者主要研究如何以最优的方式安排信息的传输，使传输完所有的信息所用的总通信时间最少，这个时间被称为完工时间[2]。为了方便研究一般把通信网络转换成赋权网络来研究，这样研究通信网络的'合理调度问题就转换为求赋权网络的最少的最大基数匹配的个数问题。
设N=(V，E，C(Vi)，T(Ej))为一个通信网络，其中V={V1，V2，V3，…，Vn}为顶点集(表示计算机)，E=(e1，e2，e3，…，em)为边集(表示两台计算机之间传输信息的线路)，C(vi)为顶点的权值(表示计算机vi可同时传输多少个信息的容量)，T(ej)为边的权值(表示传输信息ej所需的时间)。笔者把网络N分为以下3种情况。
情况A：|V|=n，|E|=m，C(vi)=1(i=1，2，3，…，m)，T(ej)=1(j=1，2，3，…，m)。
情况B：|V|=n，|E|=m，C(vi)=1(i=1，2，3，…，m)，T(ej)≥1(j=1，2，3，…，m)。
情况C：|V|=n，|E|=m，C(vi)≥1(i=1，2，3，…，m)，T(ej)≥1(j=1，2，3，…，m)。
通过对上述3种情况的深入分析，总结出其最大基数匹配算法实现。
2 通信网络调度问题的算法
2.1最大基数匹配算法
最大基数匹配算法的实现步骤如下。
步骤1：判断计算机的传输容量C(vi)=1，则直接执行E=步骤2;若C(vi)≥1，则先执行对网络进行完伪顶点变换，变换后的节点个数V´。
步骤2：赋予传输文件的所需的时间T(ej)，从传输文件集合E中随机抽取一个文件，让其传输。
步骤3：再从集合E中寻找与上一步骤抽取文件不互斥的文件，让其传输。
步骤4：不断重复上一步骤，直到得到与步骤1所抽取文件不互斥文件的最大匹配，记为信息集合E1，信息传输时间为MAX1{T(ej)}。
步骤5：若E1中的MIN{T(ej)}传输完，则从集合E-E1中随机抽取一个文件，让其传输。
步骤6：再从集合E-E1中寻找与上一步骤抽取文件不互斥的文件，让其传输。
步骤7：不断重复上一步骤，直到得到与步骤5抽取文件不互斥文件的最大匹配，记为集合E2，信息传输时间为MAX2{T(ej)}。
步骤8：按照上述过程，依次得到E1，E2，E3，…，En，则通信网络传输的最短时间就等于MAX1{T(ej)}+MAX2{T(ej)}+MAXn{T(ej)}[3]。
3 通信网络应用实例与结果分析
该通信网络的3个实例都是规模较小的问题，对于规模较小的时间表问题使用“穷举方法”求得最优解，那么就需要对此方法做出证明，证明其是最优的。
实例1：给出由10个顶点，9条边组成的通信网络实例，见图1。
对于实例1，最短完工时间3min，在第1min内传输4个文件，第2min传输3个文件，第3min传输2个文件。这个答案的证明可以用最大基数匹配算法和边色数的重要定理：二分图的边色数等于顶点的最大次。而实例1中所有顶点的最大次是3。这就构成了图的一个“正常的三边染色”(即相邻的边得染色不同)，证明了计算结果的最优性[4]。
实例2：选择10个节点，9条边作为通信网络的实例，其模型的结构图和实例1一样，只是传输文件的时间不同。
对于实例2，最短完工时间为9min，考虑子网络(V3，V4，V5，V6;e3，e4，e5)见图2。其中结点V4称为“瓶颈结点”，则文件e4，e5，e6不能同时传输，由此可见实例2最短完工时间是3+2+4=9min。
实例3：由8个顶点，11条边组成的通信网络实例见图3。
计算机的编号为1，2，3，4，5，6，7，8。计算机的容量为：1，2，1，2，1，1，3，1。由于在这种情况下计算机的容量不为1，这就引进了伪节点的概念，可以使原有的容量不为1的计算机转换为容量为1，就可以使用一般图的最大基数匹配算法来实现。根据计算机的容量表对实例3给出的通信网络图进行等价转换见图4。
对于实例3：最短完工时间是9min，考虑子网络(V1，V2，V3，V4，V5;e1，e2，e3，e9)见图5。其中结点V3为“瓶颈结点”，文件的传输时间为T(e1)=2，T(e2)=1，T(e3)=3，T(e9)=3，而文件e1，e2，e3，e9不可以同时传送，由此可见实例的最短完工时间是2+1+3+3=9min。
4 结束语
笔者所研究的最大技术匹配算法在一定情况下是最优的。但是通过对实例中3种情况的分析可以发现，影响最优完工时间的主要因素是计算机的通信容量。显然增大一些计算机容量有可能缩短完工时间，如增大那些传输量很大的计算机容量，对完工时间的有明显影响。比如实例2中的V4和实例3中的V3，这些被称为瓶颈的结点，如果增大它们的容量，就会大大缩短整个网络的完工时间。
另外，笔者所论述的信息都是在理想的状态下完成传输的，但实际情况中影响信息传输的因素还很多。比如，网络中所有的文件再开始时都已准备好，随时可以传输，但实际上文件有可能没有准备就绪，其次文件传输是相互无关的，实际中有时文件是有相关顺序的，或者文件的优先权问题，笔者没有涉及，最后如果有紧急情况，一些被传输的文件就会被中断，这就涉及文件的抢占等。
参考文献：
[1]时凌,陶勇.有序流水作业时间表问题是NP-困难[J].湖北民族学院学报:自然科学版,2000(10):34-35.
[2]刘念,关守平.网络控制系统调度问题的研究与进展[J].机械设计与制造,2009(9):45-46.
[3]赵红梅.算法设计与分析综述[J].科技信息,2010(23-25).
[4]段志生.图论与复杂网络[J].力学进展,2008(5):78-79.