一种基于时间限制的通信调度模拟方法

摘要

本发明的目的在于提供一种基于时间限制的通信调度模拟方法。该方法在拓扑网络中使用随机数生成模拟网络结点通信，突出模拟网络通信的随机性，同时在保证在最迟开始时间开始通信的基础上以最快完成任务为原则安排给通信结点的通信端口，提高通信仿真的效率。

主权项

一种基于时间限制的通信调度模拟方法，其特征在于：本发明的目的是这样实现的：设网络拓扑中从M结点出发，将与其他网络结点进行通信，通信数量为L；设结点M共有P个通信端口记为Port₁,Port₂,…,Port_m，使用数据格式Port_i{Q₁,R₁,S₁]，[Q_i,R_i,S_i]..：TOTAL_i}来表示结点通过端口Port_i依次需要向网络结点Q₁，Q₂…串行发送数据，[Q_i,R_i,S_i]表示结点M向网络结点Q_i发送数据最迟在S_i时刻开始，需要的数据传输时间为R_i,TOTAL_i表示通信端口Port_i完成所有发送任务所需要的总时间；生成L组不同的三元随机数{Q₁,R₁,S₁}…{Q_k,R_k,S_k}…{Q_l,R_l,S_l}来表示通信任务，其中Q_k≠M；为保证通信任务都能在最迟开始之前进行，并且保证所有通信任务以最快的速度完成，使用以下方式进行通信：首先将通信任务按照最迟开始时间的大小进行升序排序，这样形成了L个有序的发送任务列表，然后将前P个通信任务分发给P个通信端口，保证前P个发送任务并发执行，形成任务列表PortList：Port₁{[Q₁,R₁,0]:TOTAL₁}，…，Port_p{[Q_p,R_p,0]:TOTAL_p}；TOTAL_i＝R_i；使用如下方法保证后面L‑P个任务在最短时间内完成：取通信任务{Qk,Rk,Sk}，k>P，如果TOTAL₁早于S_k，则令TOTAL₁+R_k，将发送任务{Q_k,R_k,S_k}直接放入Port₁中形成新的任务列表，否则，从Port₁开始，依次查看其它端口任务列表中的每个通信任务；如果在端口Port_i中已安排好的第N个任务前插入{Q_k,R_k,S_k}，可以保证Port_i中前N‑1个任务的完成时间小于S_k，并且{Q_k,R_k,S_k}的任务插入不会导致端口Port_i中第N个到最后一个任务的开始时间大于其最迟开始时间，则将任务{Q_k,R_k,S_k}插入到Port_i中的第N个位置，并将任务列表按照TOTAL_i的大小重新升序排序为Port₁，Port₂…；如果在其它端口的任务列表未找到合适的位置，则舍弃该通信任务；依次完成L个发送任务的安排，便形成了完整的发送任务链表PortList；结点M的各端口仅需要根据PortList的记录进行数据发送便可摸拟基于时间限制的通信调度模拟方法；具体步骤为：(1)生成随机数M，L，表示网络结点M将与其它网络结点进行L次通信，初始化RList、PortList为空；(2)随机生成网络结点M的通信端口数P，端口编号num＝1,2…P；(3)设置i＝1；(4)生成随机数{Q_i,R_i,S_i}；(5)如果满足条件Q_i<P,则执行步骤(6)；否则执行步骤(4)；(6)初始化j＝1；(7)如果i>1执行步骤(8)，否则执行步骤(11)；(8)从RList中取出Qj，如果Qi＝Qj执行步骤(9)，否则执行步骤(10)；(9)如果S_i＝S_j，执行步骤(4)，否则执行步骤(10)；(10)j+1；如果j＝i；执行步骤(11)，否则执行步骤(8)；(11)将{Q_i,R_i,S_i}加入RList，i+1；(12)如果i>L执行步骤(13)；否则执行步骤(4)；(13)将RList中的任务根据最迟开始时间升序排序；(14)设置i＝1；(15)如果i<＝P执行步骤16，否则执行步骤17；(16)从RList中取出一个元素{Q_i,R_i,S_i}，令TOTAL_i＝R_i形成任务Port_i{[Q_i,R_i,S_i]:TOTAL_i}并加入数据列表PortList，执行步骤29；(17)将PortList中元素根据端口TOTAL值重新升序排序；(18)从RList中取出一个元素{Q_i,R_i,S_i}，如果TOTAL₁<＝S_i执行步骤19，否则执行步骤20；(19)将{Q_i,R_i,S_i}形成通信任务交给端口Port₁，设置TOTAL₁＝TOTAL₁+R_i；更新任务列表为Port1{[Q₁,R₁,S₁]…[Q_i,R_i,S_i]:TOTAL₁}，执行步骤29；(20)初始化s＝1；(21)初始化m为Port_s中已安排任务的个数；(22)如果Port_s中前m‑1个任务的完成时间和小于S_i则执行步骤23，否则执行步骤27；(23)初始化n＝m；(24)如果前n‑1个任务的完成时间和加上R_i小于S_n，执行步骤25，否则执行步骤28；(25)N的值加1,如果n大于Port_s中任务的个数，执行步骤26，否则执行步骤24；(26)从RList中取出一个元素{Q_i,R_i,S_i}，形成通信任务插入端口Port_s的第m个位置，设置TOTAL_s＝TOTAL_s+R_i；执行步骤29；(27)m的值减1，如果m>0，执行步骤22，否则执行步骤28；(28)s的值加1,如果s<＝P，执行步骤21；否则舍弃该任务，执行步骤29；(29)i的值加1，如果i<＝L执行步骤15，否则程序结束；