网络通信的调度问题.pdf

《网络通信的调度问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的

2、话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：网络通信的调度问题模型摘要随着经济的飞速发展，使得更多的人使用计算机来与世界交流，由此可见网络通信已经越来越深入人心，影响着我们的生活和学习，所以在网络通信中我们合理安排文件的传输顺序，既要保证文

3、件在传输过程中不至于发生碰撞，而且还要使文件的传输时间不要最短，文章介绍了网络通信是在受传输时间和计算机容量等因素的限制下，研究在一个网络中如何安排一些文件的传输，使得完成全部文件传输的基础上，所消耗的时间最短。问题一所描述的情形中的网络转换为树状结构的赋权无向图，定义同时传输不互斥文件的数量最大称为最大匹配，每次传输时都寻找最大匹配进行传输，通过使每次传输不互斥文件的数量最大，使传输所有文件的总时间最短。问题二所描述的情形属于一般网，每台计算机的容量不尽相同，各文件的传输时间也不一样，所以文件的传输存在优先权问题，定义计算机的负荷为其完成与其相关的全部文件传输的最短时

4、间,根据计算机的负荷的差异，采用计算机负荷大的优先考虑其传输，同时文件传输时间小的优先传输，以此来减少计算机的等待时间，再通过回溯的方法逐步改变优先权次序，在合理的时间寻求不同可能的传输方案。关键字:计算机负荷最大匹配贪婪算法回溯法1.问题重述在科技飞速发展的现今，越来越多的人依赖计算机来完成各种信息的传输，虽然这种信息交流方式给大家带来很多方便，但随之而来的也有亟需解决的问题，即在计算机最大负荷的情况下让文件传输所消耗的时间最短，本题讲述就是这样一个问题：在一个由多个部门组成且各部门之间往往需要共享信息，协同工作的公司用若干台计算机组建一个通信网络，由一台计算机向另一

5、台计算机传输文件（数据）。如果该公司有28个部门，每个部门有一台计算机，每天必须传输27个文件。可以用下图表示：其中，顶点表示计算机，边表示要传输的文件。如果用表示计算机能够同时传输文件的容量（比如表示计算机一次只能传输一个文件），表示传输文件所需要的时间（文件的传输必须占用两台计算机为传输该文件所需的全部时间）。通过以上网络图，我们需要解决以下问题：(1)所有的，，，安排一个最优方式来安排传输，使得传输所有文件所用总时间最少。(2)如果公司的计算机经过升级换代，每次能够传输的文件不止一个，如表1所示。表1计算机容量i1234567C(Vi)2211111i111213

6、14151617C(Vi)1122121i21222324252627C(Vi)1211121同时，传输文件所需时间也发生了变化，如表2所示。表2文件传输时间j12345678910T(ej)3.04.14.07.01.08.03.22.45.08.0j11121314151617181920T(ej)1.04.49.03.22.18.03.64.57.07.0j21222324252627T(ej)9.04.24.45.07.09.01.2在此情况下，安排最优传输方式，使得传输所有文件的总时间最少。并说明安排此传输方式的方法是否具有一般性？2.问题分析在题中的传输网络

7、中，将承担作用的计算机看作是一个点，记为，如果两台计算机可以传输文件，在代表两台计算机的点之间连一条边，记为,文件传输时间为该边上的权，一台计算机可以传输的文件数量称为对应点的容量，从而将传输网络转化为图，由于文件的传输由两台计算机同时进行的，则传输网络图是一个赋权无向图，传输网络构成的一个具有28个点，27条边的一个图总等待时间最短。2.1问题一：联系28个部门，需要传输27个文件的传输网络，是含28个结点、27条边的一个图，通过对图中边和结点的分析，希望找到一种最优传输方式，使所有文件在指定的计算机上总传输时间最短，题中给出对于所有的