CN105163354B - 一种利用成对流间网络编码机会的数据流时延保障策略 - Google Patents

Abstract

本发明公开了一种利用成对流间网络编码机会的数据流时延保障策略，包括以下步骤：分组缓存，在IP层与MAC层之间实现中间层协议，缓存IP层到达的分组，为每条数据流建立虚拟队列，发掘数据流间成对编码机会。统计队列信息，在每个调度时长开始时统计每个队列中数据包个数、权重、时延以及数据流成对编码关系。分组调度，利用整数线性规划方法计算分组的最优发送次序和个数。编码发送，对需要编码的分组进行编码，加上编码头部后，发往MAC层接口处。结束本轮调度，当本轮调度时间到期后返回步骤1，继续调度本轮调度期间到达的数据分组。

Description

一种利用成对流间网络编码机会的数据流时延保障策略

技术领域

本发明涉及一种利用成对流间网络编码机会的数据流时延保障策略，属于通信领域协议设计领域。当数据流间存在成对流间编码能力时，采用本方法，能够在保证数据流差异性时延约束的情况下，尽可能的提高网络吞吐量。

技术背景

无线网状网(WMN)技术由于其无需基础架构的特点，能够提供低价、广覆盖的网络，被越来越多的用于学校、商场、步行街等室内外应用场景中。然而无线网络的抗干扰性差、链路不稳定的缺点，又使得其难以支持对服务质量要求较高的应用。如今多媒体应用与无线网络的结合越来越紧密，他们对无线通信服务质量要求高,通常有差异性的时延、优先级的需求。网络编码技术，能够很好地结合无线网天然的广播特性，利用网络的大量冗余信息，对数据包编码后集中发送。这一技术被证明能够有效地减少数据流转发次数，提高网络的吞吐量。是保障无线网络中多媒体应用通信质量有效解决方案。其中流间网络编码还具有编码开销小，解码时延短等优点。本文将主要研究流间网络编码，讨论有效降低数据流时延的调度策略。流间编码的基本原理是中间节点对多个来自不同数据流的分组进行编码并一次转发。编码机会依赖于数据流之间的拓扑关系。

本发明主要讨论无线网络中可编码数据流的调度问题，当多条业务流存在不同的时延要求时，如何在保证这些时延要求的情况下提高吞吐量。已有的工作或给出了启发式算法，研究了编码数据流端到端时延，或只研究成对编码，没有考虑到数据流差异性的时延要求。而我们的研究考虑的数据流条件多，编码结构全，提供的解决方案也更完善。

发明内容

本发明的目的是：讨论无线网络中可编码数据流的调度问题，当多条业务流存在不同的时延要求时，如何在保证这些时延要求的情况下提高吞吐量。

为了实现上述目的，本发明的技术方案是：

一种利用成对流间网络编码机会的数据流时延调度方法，其特征是包括以下步骤：

1)建数据流队列缓存IP层到达分组；分组缓存，在IP层与MAC层之间实现中间层协议，缓存IP层到达的分组，为每条数据流建立虚拟队列，发掘数据流间成对编码机会。

2)统计队列信息，在每个调度时长(区间)开始时统计数据流信息，包括每个队列中数据包个数、权重、时延以及数据流成对编码关系。

3)分组调度，利用整数线性规划方法计算分组的最优发送次序。

4)编码发送，对需要编码的数据包分组进行编码，加上编码头部后，将数据包按序发往MAC层接口处；

5)结束本轮调度，当本轮调度时间到期后返回步骤1)，继续调度本轮缓存的数据分组。

上述步骤1)利用节点的两跳邻居信息来发现成对编码机会。利用较小的计算成本，发现较多的编码机会。

上述步骤3)将最大化时延到达之前发送数据分组权重和问题规约为整数线性规划问题，并证明可以求出最优发送次序。

上述步骤5)划定的调度时间段长度根据网络平均时延决定。

数据流时延调度方法具体分为3个阶段：编码机会发现，分组调度和分组编码；

阶段一：编码机会发现策略，PTCS的首要模块是编码机会发现机制，能够利用节点的一跳邻居信息和两跳邻居信息来挖掘数据流间的成对编码关系；对于先应式路由协议，每个节点能够很容易的知道自己的一跳和两跳邻居；对于反应式路由协议，让每个节点利用Hello报文广播自己的一跳邻居信息给邻居；收到邻居的Hello报文后，节点就更新自己的一跳邻居表和两跳邻居表；

利用数据流的上下游节点信息以及中间节点的一跳和两跳邻居信息来判断一对数据流是否存在编码关系；

将中间节点R收到的数据包，分别缓存到为每个数据流建立的队列中；每条队列都要记录下对应数据流的源节点、目的节点、下一跳地址、权重大小、时延要求、数据包个数信息，还要保存指向数据包列表的指针；每当一个数据包进入节点R时，首先检查这个数据流的队列是否存在，若队列存在，直接将该数据包加入队列中的数据包列表，同时队列信息中数据包个数记录加1；若不存在，则为这个数据流新建一个队列，同时利用队列信息以及编码判断条件来检查这条数据流和已入队的数据流是否存在编码关系；

阶段二：分组调度；能根据数据流的编码关系、权重、时延、队列长度信息给出一个最优数据包发送顺序；先定义一个调度区间为T个发送时隙，即在这段时间内能发送出去T个数据包；在每个调度区间的开始，统计队列中记录的数据流信息，编码关系、权重、时延、队列长度，对最大化在时延到达之前发送数据包的权重和问题进行形式化；

将经过中间结点的数据流分为两个集合，集合P_S中数据流没有编码关系，为单流，集合P_C中都是有编码关系的编码对；个数为S_k,对于有编码关系的编码有序对(i,j),且满足i<j,被成功转发的编码数据包个数定义为D_i，f_i和f_j中未被编码就转发的数据包叫做余包，其个数分别定义为R_i和R_j.有R_i·R_j＝0的性质，即两者中至少有一个为0，否则两个数据流仍能继续编码；

通过线性规划方法给出每个数据流发送的分组个数，按照时延从小到大的顺序，将单个数据包或是编码数据包移动到中间节点R的发送队列中，让数据包等待MAC层的发送机会；同时清理原来的缓存数据队列，等待新数据包的到达；每当中间节点取得一个发送机会，就从发送队列的最前端取一个数据包发送；在调度区间内到达节点的数据包，经过IP层的路由后，就被缓存在新的队列里，在本轮调度结束后，参与下一轮的调度；

阶段三：分组编码，PTCS分组调度模块输出的发送顺序是一系列的数据流中被调度的数据包个数，这些数据流是单流或编码流；中间节点按照这个发送顺序，从每个数据流队列的最前端取出相应个数的数据包发送；如果遇到编码数据流，则要从一对编码流中分别取出数据包进行编码；称这两个数据一个为主编码包，另一个为从属编码包；IP头部中保存的是主编码包的源节点、目的节点、时延信息、权重信息、发送时间；需要给每个数据包加上一个编码头部用于记录从属编码包的信息，称之为CodeHead，放在IP头部和MAC头部之间；CodeHead的结构中，编码标识位显示此数据包是否为编码包，以及从属编码包的源节点、目的节点、下一跳地址、时延信息、权重信息、发送时间信息；编码后的数据包和其他单包一样按序加入节点的发送端口处，交由MAC层发送；为了接收到编码数据包，节点需要打开混杂模式，也就是无线节点利用信道的广播特性，接受一切能听到的数据包，包括不是发送给它自己的；MAC层收到单播数据包，就将数据包移交PTCS层；PTCS层判断数据包是否编码，并对编码的数据包进行解码，最后将解码后的单包提交IP层进行路由或是交付。

本发明的有益效果：本发明针对无线网络中可编码数据流的调度问题，当多条业务流存在不同的时延要求时，保证这些时延要求的情况下提高吞吐量。尤其是考虑的数据流条件多，编码结构全，提供的解决方案也更完善。尤其是当多条业务流存在不同的时延要求时，保证这些时延要求的情况下提高吞吐量。

现有技术或给出了启发式算法，研究了编码数据流端到端时延，或只研究单跳网络，没有考虑到数据流差异性的时延要求。而本发明考虑的数据流条件多，网络拓扑灵活，提供的解决方案也更完善。能够利用网络中大量存在的成对流间编码机会，有效的降低多组单播数据流的时延，提高网络的吞吐量。可以为无线自组织网中对服务质量有较高要求的应用提供高效、有保证的支持。

附图说明

图1：hello数据格式；

图2：编码头部格式；

图3：21个节点拓扑图；

图4：吞吐量变化曲线；其中图4(a)为三种协议在网络总流量的变化下，所有被目的节点接收的数据包吞吐量。图4(b)为三种协议在网络总流量的变化下，所有被目的节点及时接收的数据吞吐量。

图5显示了三种协议的效用性能曲线。其中图5(a)为三种协议在网络总流量的变化下，所有被目的节点接收的数据包权重和。图5(b)为三种协议在网络总流量的变化下，所有被目的节点及时接收的数据包权重和。

图6显示了三种协议的时延性能曲线。其中图6(a)为三种协议在网络总流量的变化下，所有被目的节点接收的数据包平均时延。图6(b)为三种协议在网络总流量的变化下，目的节点接收到的超时数据包的平均时延。

具体实施方法

本发明为IP与MAC中间层协议，命名为PTCS(Pairwise-coding Time ConstraintScheduling)。PTCS可分为3个阶段：编码机会发现，分组调度和分组编码。我们采用一种有效的编码路由发现策略，能够利用数据流的两跳路由信息来获取编码机会，同时保持较低的计算开销。我们建立两跳路由表发现编码机会，用一个编码关系表将结果保存下来。我们为中间节点上缓存的每条数据流都建立一条队列。这个队列记录下每条数据流中数据包的信息，包括数据包权重，数据包到达时间，数据流时延约束和队列长度。编码关系表和队列信息将成为协议中调度策略的输入，而调度策略最终输出当前缓存数据包的发送顺序，最后由中间节点按顺序逐次发送数据包，如果数据包需要编码，则由编码模块对数据包进行编码后发送。

阶段一：编码机会发现策略

PTCS的首要模块是编码机会发现机制，它能够利用节点的一跳邻居信息和两跳邻居信息来挖掘数据流间的成对编码关系。对于先应式路由协议，如DSDV和OSLR，由于邻居表已知，所以每个节点能够很容易的知道自己的一跳和两跳邻居。对于反应式路由协议，如AODV，我们采用董超等人提出的方法，让每个节点利用Hello报文广播自己的一跳邻居信息给邻居。这种方法的优点是局部的邻居和拓扑信息不扩散到全网中，在不增加过多计算开销和网络开销的情况下，每个节点就能获取到两跳邻居信息。其Hello报文的设计如图1所示，灰色保留字段中保存发送节点的一跳邻居个数，Hello报文的末尾则添加了每个一跳邻居的地址，和经过该邻居能到达的目的节点地址。每个节点都有一个一跳邻居表，其中每个一跳邻居又有一个指向自己邻居表指针，即该节点的两跳邻居表。收到邻居的Hello报文后，节点就更新自己的一跳邻居表和两跳邻居表。如图1示。

我们将利用数据流的上下游节点信息以及中间节点的一跳和两跳邻居信息来判断一对数据流是否存在编码关系。对于中间节点R处的两条数据流f₁和f₂，他们的编码关系判断过程如下。我们令符号PH_(1,1)表示数据流f₁关于R的上一跳节点，PH_(1,2)表示数据流f₁关于R的上两跳节点，NH_(1,1)表示数据流f₁关于R的下一跳节点。相对的，我们有PH_(2,1)表示数据流f₂关于R的上一跳节点，PH_(2,2)表示数据流f₂关于R的上两跳节点，NH_(2,1)表示数据流f₂关于R的下一跳节点。同时，我们还令符号N(node)表示节点node的邻居节点，若有node₁∈N(node₂)，就表示节点node₁是节点node₂的邻居节点。

我们将编码关系判断过程抽象成两个条件：

条件一：检查f₁的上游路径与f₂的下游路径是否有交汇。我们有三个等式：

PH_(1,1)＝NH_(2,1)；PH_(1,1)∈N(NH_(2,1))；PH_(1,2)∈N(NH_(2,1)).

若满足三个等式中的一个，我们认为条件一被满足。

条件二：

检查f₂的上游路径与f₁的下游路径是否有交汇。我们也有三个等式：

PH_(2,1)＝NH_(1,1)；PH_(2,1)∈NH_(1,1)；PH_{2,2}∈N(NH_(1,1)).

若满足三个等式中的一个，我们认为条件二被满足。

当两个条件都被满足时，我们认为数据流f₁和f₂之间存在编码关系。

我们将中间节点R收到的数据包，分别缓存到我们为每个数据流建立的队列中。每条队列都要记录下对应数据流的源节点、目的节点、下一跳地址、权重大小、时延要求、数据包个数等信息，还要保存指向数据包列表的指针。每当一个数据包进入节点R时，我们首先检查这个数据流的队列是否存在。若队列存在，直接将该数据包加入队列中的数据包列表，同时队列信息中数据包个数记录加1。若不存在，则为这个数据流新建一个队列，同时利用队列信息以及编码判断条件来检查这条数据流和已入队的数据流是否存在编码关系。

阶段二：分组调度

PTCS的第二大模块是分组的调度，它能根据数据流的编码关系、权重、时延、队列长度等信息给出一个最优数据包发送顺序。我们定义一个调度区间为T个发送时隙，即在这段时间内我们可以发送出去T个数据包。在每个调度区间的开始，我们统计队列中记录的数据流信息，如编码关系、权重、时延、队列长度，对最大化在时延到达之前发送数据包的权重和问题进行形式化。

我们将经过中间结点的数据流分为两个集合，集合P_S中数据流没有编码关系，为单流，集合P_C中都是有编码关系的编码对。以图2中的模型为例，P_S＝{1，6，7},P_C＝{(2，3),(4，5)}.对于一条单流f_k，能被成功转发的数据包为单包，个数为S_k,对于有编码关系的编码有序对(i,j),且满足i<j,被成功转发的编码数据包个数定义为D_i，f_i和f_j中未被编码就转发的数据包叫做余包，其个数分别定义为R_i和R_j.在我们的问题模型中，有R_i·R_j＝0的性质，即两者中至少有一个为0，否则两个数据流仍可以继续编码。为了更容易的说明问题的形式化过程，我们首先定义问题的标准解形式。

定义一：问题的标准解形式是指时间段内的数据包按照他们的时延从小到大排序的队列。同一条数据流中的数据包在队列中相邻。这样的队列也可以被看作是由连续的D,R,S数据块排列而成的，我们认为编码数据包D的时延对应于编码对中序号较小的数据流的时延。

定理一：给定调度时间段内任意的一个可行解，我们都能将它转换成一个等价的标准解形式。

证明：对于任意可行调度，我们首先观察其中相邻的两个数据包，如果他们来自不同的数据流，那么我们总是可以时延较短的数据包移到前面，同时保证两个数据包的时延约束都不被破坏。重复这一交换过程就可以将任意可行解调整为标准解形式。证明完毕。

我们可以根据D,R,S的有关定义来对我们的问题进行形式化，将其规约为一个整数线性规划问题

s.t

D_i,R_i,S_i∈{0,1,2,3,...}. (4)

约束(1)表示单流发送的数据包个数不能超其缓存的数据包个数，约束(2)表示编码数据包的长度约束，约束(3)表示数据包的发送不能超过其时延约束，约束(4)要求发送的数据包个数必须是正整数。目标是最大化在时延到达之前被发送的数据分组的权重和。

通过线性规划方法可以给出每个数据流发送的分组个数，我们按照时延从小到大的顺序，将单个数据包或是编码数据包移动到中间节点R的发送队列中，让数据包等待MAC层的发送机会。同时我们清理原来的缓存数据队列，等待新数据包的到达。每当中间节点取得一个发送机会，就从发送队列的最前端取一个数据包发送。在调度区间内到达节点的数据包，经过IP层的路由后，就被缓存在新的队列里，在本轮调度结束后，参与下一轮的调度。

我们的协议有良好的可移植性。这个协议能够用于基于时隙划分的MAC协议，每个节点有固定的发送时间，如TDMA。也能用于基于信道竞争的802.11协议。虽然802.11会引入额外的信道竞争时延，无发保证数据包在设定的时隙发送。但我们不需要知道每个数据包具体发送时间，就能够提供最优的发送顺序，即使有信道竞争时延存在，我们相信调整后的数据包发送顺序一定能为网络性能带来提升。

阶段三：分组编码

PTCS分组调度模块输出的发送顺序是一系列的数据流中被调度的数据包个数，这些数据流可能是单流，也可能是编码流。中间节点按照这个发送顺序，从每个数据流队列的最前端取出相应个数的数据包发送。如果遇到编码数据流，则要从一对编码流中分别取出数据包进行编码。我们称这两个数据一个为主编码包，另一个为从属编码包。IP头部中保存的是主编码包的源节点、目的节点、时延信息、权重信息、发送时间等信息。我们还需要给每个数据包加上一个编码头部用于记录从属编码包的信息，我们称之为CodeHead，放在IP头部和MAC头部之间。CodeHead的结构如图2所示，其中编码标识位显示此数据包是否为编码包，以及从属编码包的源节点、目的节点、下一跳地址、时延信息、权重信息、发送时间等信息。编码后的数据包和其他单包一样按序加入节点的发送端口处，交由MAC层发送。为了接收到编码数据包，节点需要打开混杂模式。也就是无线节点利用信道的广播特性，接受一切可以听到的数据包，包括不是发送给它自己的。MAC层收到单播数据包，就将数据包移交PTCS层。PTCS层判断数据包是否编码，并对编码的数据包进行解码，最后将解码后的单包提交IP层进行路由或是交付。

将PTCS协议与两个著名的协议，802.11和COPE，进行实验对比，发现PTCS不仅能够利用网络编码的优点提升吞吐量，还能够通过有效的调度策略降低数据流平均时延，提高满足时延需求的数据包的权重和。对于较大规模较高流量的无线自组织网络有良好的适应能力。

本发明的实验平台是QualNet仿真器。QualNet是一种应用于无线、有线以及混合动态网络的快速而且精确的开发、仿真系统。在QualNet中，仿真协议的移植性很强。仿真协议与真实设备上的协议相似，只需要作简单的修改就可以下载到设备中去使用，并且与CPU无关。甚至可以作为真实网络的一部分，参与到网络的测试中。我们基于802.11协议实现我们的中间层协议，将其命名为802.11-pcs(Pairwise Coding Scheduling)。同时我们还在802.11上实现了编码协议COPE，能够对数据包成对编码，对数据包的调度遵循先进先出的原则，我们将这个协议命名为802.11-pc(Pairwise Coding)。我们还与没有编码功能的802.11比较，检验成对编码对性能带来的增益。

如图3所示，我们有21个节点布置在1000m*600m范围内，节点的通信距离为250m，有效链路都在图中标记出来。数据流的源节点和目的节点随机选出，网络中总共存在16条CBR数据流，数据包的大小为1000Byte。我们调整网络中总吞吐量，从3Mbps逐步增长到7Mbps,观察三种协议下吞吐量和时延的性能。

图4显示了三种协议的吞吐量性能。图4(a)为三种协议在网络总流量的变化下，所有被目的节点接收的数据包吞吐量。802.11-pcs和802.11-pc的吞吐量接近，但都远高于802.11的吞吐量，说明网络编码能有效的提高网络吞吐量性能。当网络流量增加时，802.11-pcs和802.11-pc都能趋近线性增长。而802.11有时性能会不稳定，可能与网络中数据流的走向有关，若某些节点中的数据包严重拥塞，会造成大量数据包丢弃，大大降低吞吐量。如图4(a)中流量为5Mbps处，802.11吞吐量降至最低，而802.11-pcs和802.11-pc只有小幅度下降。图4(b)为三种协议在网络总流量的变化下，所有被目的节点及时接收的数据吞吐量。可以看到802.11-pcs的及时吞吐量始终优于802.11-pc和802.11。由于编码带来的增益，当网络交通量增长时，802.11-pcs和802.11-pc的有效吞吐量都能稳步提升。因为编码减少了网络的转发次数，降低了数据包的排队时间。而802.11则对网络流量的增加和数据流的路由结构更为敏感，有效吞吐量增幅不大，并且会产生性能很低的情况。由于802.11-pcs有数据流调度的功能，其及时吞吐量比802.11-pc可高出18.2％。

图5显示了三种协议的效用性能。图5(a)为三种协议在网络总流量的变化下，所有被目的节点接收的数据包权重和。图5(b)为三种协议在网络总流量的变化下，所有被目的节点及时接收的数据包权重和。可以发现三种协议的效用性能走向与吞吐量性能走向类似，有较强的相关性。802.11-pcs总效用曲线与802.11-pc基本重合，但及时效用比802.11高出达18.8％。这两者的效用都远高于802.11。这一组数据再次验证，我们的调度策略能够在数据包编码技术之上进一步提高网络的有效增益。

图6显示了三种协议的时延性能。图6(a)为三种协议在网络总流量的变化下，所有被目的节点接收的数据包平均时延。802.11-pcs的平均时延始终最低，即使网络流量增加，时延也没有过多的提高，说明802.11-pcs对大规模大流量网络的适应性较好。802.11-pc与802.11的时延性能都有一定起伏，其中802.11-pc的时延比802.11-pcs高出约22.3％，802.11的时延比802.11-pcs高出约24.6％。图6(b)为三种协议在网络总流量的变化下，目的节点接收到的超时数据包的平均时延。这一组数据的起伏都比较大，有较大的随机性，因为超时的数据包其发送时间长，说明其受网络交通和节点拥塞程度的影响较大。802.11的起伏最大,802.11-pcs与802.11-pc的曲线较接近。

Claims (1)

1.一种利用成对流间网络编码机会的数据流时延调度方法，其特征是包括以下步骤：

步骤1)建数据流队列缓存IP层到达分组；分组缓存，在IP层与MAC层之间实现中间层协议，缓存IP层到达的分组，为每条数据流建立虚拟队列，发掘数据流间成对编码机会；

步骤2)统计队列信息，在每个调度时长开始时统计数据流信息，包括每个队列中数据包个数、权重、时延以及数据流成对编码关系；

步骤3)分组调度，利用整数线性规划方法计算分组的最优发送次序；

步骤4)编码发送，对需要编码的数据包分组进行编码，加上编码头部后，将数据包按序发往MAC层接口处；

步骤5)结束本轮调度，当本轮调度时间到期后返回步骤1)，继续调度本轮缓存的数据分组；

步骤1)利用节点的两跳邻居信息来发现成对编码机会；利用小的计算成本，发现多的编码机会；

步骤3)将最大化时延到达之前发送数据分组权重和问题规约为整数线性规划问题，并证明能求出最优发送次序；

步骤5)划定的调度时间段长度由网络平均时延决定；

数据流时延调度方法具体分为3个阶段：编码机会发现，分组调度和分组编码；

阶段一：编码机会发现策略，编码机会发现策略，能够利用节点的一跳邻居信息和两跳邻居信息来挖掘数据流间的成对编码关系；对于先应式路由协议，每个节点能够很容易的知道自己的一跳和两跳邻居；对于反应式路由协议，让每个节点利用Hello报文广播自己的一跳邻居信息给邻居；收到邻居的Hello报文后，节点就更新自己的一跳邻居表和两跳邻居表；

利用数据流的上下游节点信息以及中间节点的一跳和两跳邻居信息来判断一对数据流是否存在编码关系；

将中间节点R收到的数据包，分别缓存到为每个数据流建立的队列中；每条队列都要记录下对应数据流的源节点、目的节点、下一跳地址、权重大小、时延要求、数据包个数信息，还要保存指向数据包列表的指针；每当一个数据包进入节点R时，首先检查这个数据流的队列是否存在，若队列存在，直接将该数据包加入队列中的数据包列表，同时队列信息中数据包个数记录加1；若不存在，则为这个数据流新建一个队列，同时利用队列信息以及编码判断条件来检查这条数据流和已入队的数据流是否存在编码关系；

阶段二：分组调度；能根据数据流的编码关系、权重、时延、队列长度信息给出一个最优数据包发送顺序；先定义一个调度区间为T个发送时隙，即在这段时间内能发送出去T个数据包；在每个调度区间的开始，统计队列中记录的数据流信息，编码关系、权重、时延、队列长度，对最大化在时延到达之前发送数据包的权重和问题进行形式化；

将经过中间结点的数据流分为两个集合，集合P_S中数据流没有编码关系，为单流，集合P_C中都是有编码关系的编码对；对于一条单流f_k，能被成功转发的数据包为单包，个数为S_k,对于有编码关系的编码有序对(i,j),且满足i<j,被成功转发的编码数据包个数定义为D_i，f_i和f_j中未被编码就转发的数据包叫做余包，其个数分别定义为R_i和R_j；在本方案中，有R_i·R_j＝0的性质，即两者中至少有一个为0，否则两个数据流仍能继续编码；

通过线性规划方法给出每个数据流发送的分组个数，按照时延从小到大的顺序，将单个数据包或是编码数据包移动到中间节点R的发送队列中，让数据包等待MAC层的发送机会；同时清理原来的缓存数据队列，等待新数据包的到达；每当中间节点取得一个发送机会，就从发送队列的最前端取一个数据包发送；在调度区间内到达节点的数据包，经过IP层的路由后，就被缓存在新的队列里，在本轮调度结束后，参与下一轮的调度；

阶段三：分组编码，PTCS分组调度模块输出的发送顺序是一系列的数据流中被调度的数据包个数，这些数据流是单流或编码流，PTCS为IP与MAC中间层协议；中间节点按照这个发送顺序，从每个数据流队列的最前端取出相应个数的数据包发送；如果遇到编码数据流，则要从一对编码流中分别取出数据包进行编码；称这两个数据一个为主编码包，另一个为从属编码包；IP头部中保存的是主编码包的源节点、目的节点、时延信息、权重信息、发送时间；需要给每个数据包加上一个编码头部用于记录从属编码包的信息，称之为CodeHead，放在IP头部和MAC头部之间；CodeHead的结构中，编码标识位显示此数据包是否为编码包，以及从属编码包的源节点、目的节点、下一跳地址、时延信息、权重信息、发送时间信息；编码后的数据包和其他单包一样按序加入节点的发送端口处，交由MAC层发送；为了接收到编码数据包，节点需要打开混杂模式，也就是无线节点利用信道的广播特性，接收一切能听到的数据包，包括不是发送给它自己的数据包；MAC层收到单播数据包，就将数据包移交PTCS层；PTCS层判断数据包是否编码，并对编码的数据包进行解码，最后将解码后的单包提交IP层进行路由或是交付。