近年来，无线网络的发展方兴未艾，蜂窝移动通信网络、Wi-Fi、蓝牙等网络类型都快速发展。同时，人们对于网络所能提供的服务类型需求也日趋差异化和精细化。特别是各种实时业务，对无线网络所能提供的服务质量提出了更高的要求，因此，对如何在无线接入网络中解决确定性时延保障问题的研究也越来越得到人们的重视。

目前的无线网络中时延问题的研究按照所关注的业务类型大致可以分为2类，分别为只考虑了单业务类型的研究工作^[1-3]和考虑了多业务类型的研究工作^[4-12]。而在研究多业务类型的方案中还可进一步细分为两大类工作，即“基于流”的机制^[4-7]和“基于类”的机制^[8-12]。

只考虑单业务类型的研究主要通过改善系统总吞吐量、调度策略、排队策略等方式来提升对时延敏感类业务的服务质量，但这些策略并不能提供确定性的时延保障。文献[1]中的方案，只针对视频流业务。文献[2]中的方案能在减少整体网络延迟和提高速率之间提供良好的折衷。文献[3]通过缩小聚合级别的候选范围，可以更快地搜索到最优聚合级别来改善时延。在目前复杂的网络需求中，这些只考虑了单类型业务研究工作很难满足现实网络中各类业务的不同需求，因此具有一定的局限性。

为了满足现有网络各种业务个性化的需求，近年来有不少研究工作考虑了多业务共存的情况，这些研究中有2类主要的解决方法，“基于流”的机制和“基于类”的机制。其中，“基于流”的机制是一种面向业务流提供资源预约服务的服务质量保障机制，其核心思想是在连接业务流源端和目的端的端到端路径所经过的所有转发节点中预留一定量的资源，以满足相应业务流的资源需求，这种机制具有较好的服务质量性能。文献[4-5]中都使用了TDMA的方式来保障时延，为相应的优先级业务流节点预留了资源。其中为了减少预留资源的浪费，文献[4]提出在轮询前先进行一轮RTS发送，来确定相应的节点是否有数据需要发送。文献[5]则使用了将TDMA的协调层和底层业务分离的思想，将非实时业务穿插在实时业务流的间隙进行发送。另外，文献[6-7]使用预约的方式来保障业务流的传输。文献[6]提出了一种多步预约的方式，提高预约信息的可靠性。为了处理预测不准确的情况，文献[7]中提出灵活预约的思想来调整预约的资源。毫无疑问，“基于流”机制是对“电路交换”机制的一种模拟，能有效保障相应的业务流服务质量。然而，使用“基于流”机制的问题在于预约的资源容易被浪费，且需要网络接入控制节点为相应的每个业务流维持状态信息，导致了可扩展性差的问题。

多业务类型研究中的另一类，即“基于类”的机制，可以在一定程度上解决“基于流”的机制所存在的资源浪费和可扩展性差的问题。“基于类”的机制是一种面向不同分组类型提供差异化服务的服务质量保障机制，其基本思想是将网络中的业务流分组划分为若干类，并在网络的中转节点中为不同类型的分组提供差异化服务。文献[8-11]是通过对相应的业务流赋予不同的优先级来改善实时业务的时延性能。文献[8]明确将业务分为3类，最高的优先级可以无需退避直接抢占信道，次一级的有较少的退避等待时间，来保证其优先于最低优先级。文献[9]中设计了一种定价机制来保证所有的网关如实报告实际优先级。文献[10]设定了周期性接入节点优先级(周期越长的优先级越高)，提出了一种新的半持久调度算法，以保证满足周期性实时通信的延迟要求，并使用最少的频谱资源。文献[11]也使用了赋予优先级的方式。另外，文献[12]中使用了软件定义网络，可以根据队列的可用带宽动态地为业务流分配队列。但由于“基于类”的机制仅将业务流分组划分为为数不多的几类，故存在着服务质量保障粒度过大问题。而且随着目前不同网络业务需求种类的不断增加，现有的类型划分会无法满足不同业务个性化的服务质量保障。若需要设计和添加新的业务类型，将势必更难平衡与原有各类型之间的“公平性”，这势必导致了其可扩展性差的问题。总之，“基于类”机制的问题在于服务质量保障的粒度大且可扩展性仍然不高。

针对目前时延保障机制所存在的主要问题，本文提出了粒子化接入的思想和方法，将业务流建模为信息粒子群。并且给出了满足给定信息粒子群中所有信息粒子时延需求的最小可达接入带宽的计算方式以及相应的接入传输方法。基于粒子化思想，提出了一种在无线网络接入动态环境下的细粒度延迟保障机制。该接入机制可以在信息粒子的细粒度上，保障各业务流差异化的时延性能需求，且可同时做到对频谱资源最为充分的利用。

1 粒子化接入基本思想

如图 1所示，本节从基础模型到接入算法描述了粒子化接入的基本思想。首先说明了基于信息粒子的业务流模型，然后说明了所提出的业务流模型静态情况下最小可达接入带宽和相应的接入传输方法，最后说明了实际情况下业务流动态到达时所采用的粒子化接入时延保障机制的基本思想。

1) 基于信息粒子的业务流模型

保障网络的端到端业务流服务质量的4个主要性能指标是：带宽、时延、时延抖动、分组丢弃率。其中，时延指标尤为关键^[13]。因此，本文所提出的基于信息粒子的业务流模型，将围绕时延指标展开。所提出的业务流模型，将聚焦于粒度更细的级别。模型将基于以下几点假设：

(1) 一个端到端业务流可以被划分为若干个具有一定大小(即信息承载量I，单位为bit)的信息块；

(2) 每个信息块均明确对应着属于自己的端到端时延容忍值(即该信息块截止时刻T，单位为s)；

(3) 对于一个承载量为I且截止时刻为T的信息块，如果网络能在T时刻前将其所承载的所有信息比特成功地传送至接收端，则认为对该信息块的传输是有效的。

本文中，将具有承载量属性和截止时刻属性的信息块称为一个信息粒子，而端到端业务流便被建模为由信息粒子构成的信息粒子流。

2) 信息粒子群的最小可达接入带宽的计算及相应的接入传输策略

在粒子化接入机制中，网络中的路由节点需要处理由大量信息粒子所构成的信息粒子群的接入问题。针对这个问题，核心思想是在给定信息粒子群(其包含的所有粒子的属性均为已知)的情况下，找到可以使其中所有信息粒子传输都为有效的最小可达接入带宽。在后续的分析中发现至少存在EDF传输策略可在最小可达接入带宽的约束下，实现对所有信息粒子的有效传输。

3) 动态业务流的接入机制

由于在实际应用场景下，每个节点会将队列中的信息粒子不断地发送出去，并且不断有新的信息粒子到达该节点。因此，本文提出的接入机制中，将在每个信息粒子到达发送队列的时候，计算相应的信息粒子群最小可达接入带宽。如果该计算所得到的最小可达接入带宽大于给定的信道带宽，则说明当前新到达的信息粒子将无法被有效发送，反之则将该信息粒子加入到队列中。队列中的信息粒子均可以通过EDF传输策略进行发送，且可以证明此传输策略满足队列中所有信息粒子的时延要求。

2 粒子群的最小可达接入带宽分析

本小节给出了信息粒子及其属性的定义和信息粒子群及其属性的定义。定义了对信息粒子群中粒子的排序操作。定义了信息粒子群的可达接入带宽、最小可达接入带宽和平均接入带宽需求等。证明了EDF是可以达到最小可达接入带宽的接入传输策略。最后，给出了在给定信息粒子群的情况下，计算最小可达接入带宽的方法(注：更为完整的分析请参见文献[14])。

定义1   信息粒子

具有特定基本属性(包括: 承载量I_i∈R⁺、初始时刻t_{b, i}∈R、截止时刻t_{e, i}∈R⁺等)的待传输信息块被称为信息粒子, 用n_i来标识。以下为其主要属性: 有效生存区间为(本文仅考虑已到达的粒子, 即t_{b, i}=0), D_i所覆盖的时间长度为此粒子的有效生存跨度T_Di∈R⁺, 即。信息粒子i在时刻t的瞬时传输速率记为r_i(t), 若n_i在D_i时间区间内被发送, 则称为有效发送。

定义2   信息粒子群

包含N≥1个有意义的信息粒子的非空集合, 记为Q。其承载量为所包含的所有信息粒子承载量之和, 即, 其有效生存空间D_Q为所有信息粒子的有效生存区间的并区间, 即, 所涵盖的总时间长度为其有效生存跨度T_DQ。

定义3   对信息粒子群Q执行的升序排序操作O_Inc(Q)

给定信息粒子群Q, 设其由N≥1个信息粒子组成。如果按照各信息粒子截止时刻由小到大进行排序, 并赋予排在第1位的信息粒子的序号为“1”(其截止时刻为t_{e, 1}), 赋予排在第2位的信息粒子的序号为“2”(其截止时刻为t_{e, 2}≥t_{e, 1}), …, 赋予排在第N位的信息粒子的序号为“N”(其截止时刻为t_{e, N}≥t_{e, N-1}), 称这样的针对Q所包含的信息粒子进行的排序操作为升序排序操作, 记为O_Inc(Q)。

定义4   信息粒子群Q的可达接入带宽B_{re, Q}，单位: bit/s

如存在一种传输策略能使得在Q中的所有信息粒子都有效传输, 且总的瞬时传输速率≤B_{re, Q}(B_{re, Q}>0, t∈D_Q), 则称接入带宽B_{re, Q}对Q来说是可达的。

定义5   信息粒子群Q的最小可达接入带宽B_{re, Q}^min∈R⁺，单位: bit/s

信息粒子群Q在其有效生存区间D_Q内的所有可达接入带宽中的最小值。

定义6   信息粒子群的平均接入带宽需求B_{av, Q}∈R⁺，单位: bit/s

针对信息粒子群Q, 定义为其平均接入带宽需求。平均接入带宽的实际物理含义为该粒子群中的所有粒子以恒定速率进行传输, 且恰好在最大截止时间时完成对所有粒子传输的恒定速率, 若这个恒定速率能使得该粒子群中的所有粒子有效发送, 则其必为该粒子群的最小接入带宽。

定理1   给定信息粒子群Q, 设其最小可达接入带宽为B_{re, Q}^min。对这个粒子群Q使用EDF策略可以在最小带宽下有效发送。

证明   首先, 一个有效的发送方案需要满足的最基础条件为: 在t_{e, i}前完成对n_i的发送(参见定义1中粒子有效发送)。那么对Q实施递增排序操作O_Inc(Q)后, 用Q_i(Q_i⊆Q)表示信息粒子群Q中序号不大于i(1≤i≤N)的所有信息粒子组成的信息粒子子群。

条件1   在t_{e, 1}时刻前的有效方案的最低要求为完成Q₁(即n₁)的发送, 即:

(1)

根据平均接入带宽的定义(定义6), 等价于

(2)

条件2   在t_{e, 2}前的最低要求为完成Q₂(即n₁, n₂)的发送, 且满足条件1, 即

(3)

等价于

(4)

以此类推:

条件N   在t_{e, N}前的最低要求为完成Q_N的发送, 且满足条件N-1, 即

(5)

若max{B_{av, Q1}, B_{av, Q2}, …, B_{av, QN-1}, B_{av, QN}}=B_{av, Qk}, 则(5)式取等号的条件为

(6)

表示发送前k个信息粒子时完全利用了带宽为B_{re, Q}^min的资源, 且正好在t_{e, k}时刻完成了传输。

所以

(7)

而使用EDF传输策略以瞬时速率B_{re, Q}^min进行传输, 则均可以对应每个条件, 即使得每个粒子在其截止时间前完成发送, 所以EDF是有效的。

证毕。

此定理给出了将整个粒子群有效发送的最低要求, 且EDF方法正好满足所有的条件, 即证明了EDF方法可以使用最小可达接入带宽有效发送整个粒子群。

定理1之推论1:给定包含有限个(即N≥1)信息粒子的信息粒子群Q, 对其执行递增排序操作O_Inc(Q)。令B_{av, Qi}表示信息粒子群Q中序号不大于i(1≤i≤N)的所有信息粒子组成的信息粒子子群Q_i(Q_i⊆Q)的平均接入带宽需求, 则有

证明   由定理1可知, 在对Q实施递增排序操作O_Inc(Q)的前提下, 成立。

证毕。

此推论给出了对于已到达粒子所组成的粒子群, 计算最小可达接入带宽的公式。

3 基于粒子化接入思想的细粒度延迟保障机制

本节首先基于粒子化接入思想, 提出了一个基础性的细粒度延迟保障机制。进一步, 为了改善网络重业务负荷情况下信息粒子间接入的公平性, 提出了一种改进算法。

3.1 粒子化接入基础算法

如图 2所示, 不同种类的业务流信息粒子从上层到达后, 都将与当前节点待发送队列中的信息粒子组成信息粒子群, 然后进行准入判断, 即计算最小可达接入带宽(参见定理1之引理1), 若最小可达接入带宽小于信道带宽, 即认为该信息粒子能被有效发送, 将其加入到队列中, 反之则将其丢弃。队列中的信息粒子将等待EDF调度, 即剩余时间越少的将越先被发送, 且队列中的所有信息粒子都可以被有效发送(参见定理1)。以下为粒子化接入基础算法。

算法1   粒子化接入基础算法

输入   到达的信息粒子

当前节点的待发送队列

输出   被发送的信息粒子

1   当一个信息粒子到达, 计算其剩余时间

2   计算队列中粒子群以及到达粒子组成集合的最小可达接入带宽(参见定理1之引理1)

3   IF (最小可达接入带宽>信道带宽)

4     将到达信息粒子丢弃

5   ELSE

6     将到达信息粒子加入节点EDF队列

7   END IF

8   WHILE (发送队列信息粒子群不为空)

9     选择发送队列中执行O_Inc(Q)后排序第一的粒子(参见定义3)

10 END WHILE

3.2 粒子化接入公平算法

根据粒子化接入最小可达带宽的计算公式可以得到, 新加入的粒子的截止时间越小则计算得到的最小可达接入带宽越大, 因此, 在网络负载较重时, 低时延的信息粒子会更难进入队列。为了平衡业务流之间的公平性, 对算法1进行了改进并提出了粒子化接入公平算法, 如图 3所示, 不同种类的业务流的信息粒子从上层到达时, 首先根据前一段时间已经到达的信息粒子剩余时间的中值, 将其分类为“紧急”或“一般”, 然后再进行准入判断(同算法1)。对通过准入判断的信息粒子增加一个随机丢包的环节。随机丢包阶段的目的是在高业务负载的状态下, 保障2类信息粒子间的公平性。正常情况下“一般”类型的信息粒子时延容忍更高, 因此其所需的最小可达接入带宽更小, 更容易进入队列并获取到接入资源。为公平性起见, 需要控制“一般”类型信息粒子的接入成功率。具体做法是, 在“一般”类型信息粒子通过准入判断后, 依旧会存在一定概率被随机丢弃, 这样可以使得队列腾出资源给“紧急”类型的信息粒子。首先定义平衡阈值和固定丢包率, 平衡阈值为“紧急”类型的业务占比目标。固定丢包率为当实际发送“紧急”类型业务占比偏移于平衡阈值时, 调整“一般”类型丢包率的单次调整量, 具体的调整过程如下: 统计一定时间内, 丢弃的信息粒子类型, 若“一般”类型的丢弃占比超过平衡阈值则降低固定丢包概率, 若“紧急”类型的丢弃占比超过平衡阈值则增加固定丢包概率。这种反馈机制和重新分类的方法可以改善不同类型信息粒子接入的公平性。最后在进入队列中的信息粒子将等待EDF调度和发送。以下为改进算法的具体描述:

算法2   粒子化接入公平算法

输入   到达的信息粒子

当前节点的待发送队列

输出   被发送的信息粒子

1   当一个信息粒子到达, 计算其剩余时间

2   IF (剩余时间 < 统计的剩余时间中值)

3     将该粒子分类为“紧急”

4   ELSE

5     将该粒子分类为“一般”

6   END IF

7   更新统计的时间中值

8   计算队列中粒子群以及到达粒子组成的集合的最小可达接入带宽(参见定理1之引理1)

9   IF(最小可达接入带宽>信道带宽)

10     将到达信息粒子丢弃, 更新丢包统计

11   ELSE

12     进入随机丢包阶段

13   END IF

14   IF (到达粒子为“一般”且random[0, 1)>“一般”固定丢包率

15     将到达信息粒子丢弃, 更新丢包统计

16   ELSE

17     将到达信息粒子加入发送队列中, 进行传输

18   END IF

19   更新丢包统计: 计算前100个丢包中“一般”分类包的占比

20   IF (“一般”分类占比>平衡阈值)

21     固定丢包率=固定丢包率+丢包率步长

22   ELSE IF (“紧急”分类占比>平衡阈值)

23     固定丢包率=固定丢包率-丢包率步长

24   ELSE

25     固定丢包率不变

26   END IF

27   WHILE (发送队列信息粒子群不为空)

28     选择发送队列中执行O_Inc(Q)后排序第一的粒子(参见定义3)

29   END WHILE

4 仿真验证

本文针对无线网络中的下行场景进行仿真, 如图 4所示, 中心节点(AP)需要同时传输n条第一类业务流和m条第二类业务流。每条业务流的到达强度相同且满足泊松分布，在仿真实验中，业务流的到达强度用每毫秒发送分组个数来描述。为了模拟实际情况中不同类型业务流的特征, 每类业务流中包含2种不同时延容忍分布的信息粒子。第一类业务流中, 低时延信息粒子占比较高, 但也存在少量高时延信息粒子; 第二类业务流中则恰好相反, 存在大量的高时延信息粒子和少量低时延信息粒子。为简单起见, 业务流中各类信息粒子的分布都采用均匀分布。

4.1 粒子化接入方案的仿真实验描述

如图 4所示, 本文的实验方案中, 2类业务流都将执行粒子化接入公平算法(参见算法2), 即首先对信息粒子进行准入控制, 其次对准许进入队列的信息粒子按照EDF策略依次进行传输。

4.2 对比方案的仿真实验描述

本文的对比方案是当前常用“基于类”的接入机制的简化实现版, 如图 5所示。与4.1中实验方案相同的2类业务流到达节点后, 各自进入相应的FIFO队列中进行排队等待。在信道接入环节, 首先设置队列的发送权重, 调度器将按照发送权重占比来随机调度发送不同优先级队列中的信息粒子。

4.3 仿真环境及参数设置

仿真实验中本文利用C++搭建仿真平台, 其中应用层按照设定参数和分布随机产生2类业务流, 然后数据链路层分别使用粒子化接入方案和对比方案对其进行处理, 发送和丢包数据在信道层被统计。

本文在保持其他参数不变的情况下, 逐渐增加每条泊松业务流的到达强度, 对比2种方案的有效吞吐量(指单位时间在其截止时刻内完成有效发送的信息粒子/分组的总比特数)、平均时延(指所有信息粒子/分组从其产生到完成发送的平均时间)、以及丢包率(指未有效发送的信息粒子/分组占总产生粒子/分组数的比值)。仿真的具体参数如表 1所示, 其中, 平衡阈值和固定丢包率只在算法2中被使用，详见3.2节。对照队列发送权重只在对照组中被使用, 详见4.2节。其他参数均采用WiFi环境的经典设置, 为了仿真方便, 本文仿真中采用无差错理想信道。

4.4 仿真结果及分析

如图 6所示，在业务流负载较轻的情况下，3种接入方法的性能非常接近，但随着业务到达强度的增加，对比方案由于没有进入队列的准入控制，队列中的分组出现堆积。而且已经失效的分组依然需要占用信道资源，这更加使得后续的分组无法得到有效发送，从而使对比方案的有效吞吐量急剧下降。而本文提出了粒子化接入方案由于其入队之前便可计算出到达的分组能否被有效发送，无法被有效发送的分组将被直接丢弃，这样可以节约有限的信道资源。所以，如图 6所示，2种粒子化接入方案在业务负载较高的情况下，都依然能保持较高的有效吞吐量，几乎都能完全充分地利用整个信道(仿真信道带宽40 MHz)。另外，由图可见，在业务负载逐渐增加时，粒子化接入基础算法2类业务流的有效吞吐量差距逐渐增大，但粒子化接入公平算法的2类业务的有效吞吐量依旧能保持接近，可见相比于粒子化接入基础算法，粒子化公平算法在公平性上有较好改善。

从图 7来看，对比方案大部分信息粒子发送完成后都已经失效，即超过了其截止时间(本文仿真中最大的截止时间设为600 ms)，这是其有效吞吐量急剧下降的原因。而粒子化接入方案由于具有准入控制，保证了进入队列的信息粒子的传输都是有效的，且较好地避免了信道传输资源的浪费，因此平均时延性能远优于对比方案。而在粒子化接入算法中，由图可见在粒子化基础算法中低时延占比较高的业务(第一类)不容易被发送，因此其平均时延相比公平算法也相对较高。

从图 8中可以看出，对比方案在业务流到达强度逐渐增加到饱和的情况下，丢包率会突增至80%以上，此时接入网络几乎瘫痪。而粒子化接入的丢包率则呈现较为平缓的上升趋势，在负载较重的状态下，依然能保持较低的丢包率。并且图中可以看出，粒子化基础方案中2类业务流丢包率差距明显，存在公平性问题，而粒子化公平方案有效解决了这个问题，2类业务流的丢包率一直比较接近。

综上，粒子化接入机制相比于传统的“基于类”方法，在业务流负载较轻的情况下性能相似，但在业务流负载很重的情况下，传统的“基于类”方法会由于队列中的分组堆积导致大部分分组不能得到及时发送，使得网络瘫痪。而粒子化接入策略由于在分组到达时就可以通过计算最小可达接入带宽来判断该分组是否能被有效发送，不会在队列中堆积，所以在高业务负载的状态下性能远超传统方案，且得到发送的分组都能得到相应的时延保障。进一步，从吞吐量和丢包率性能对比来看，粒子化接入公平方案有效解决了粒子化接入基础方案中不同业务流公平性较差的问题。

为了模拟业务流中2类分组占比更均衡的场景，实验将第一类业务流的高/低时延分组占比从1∶9修改为3∶7；第二类业务流的高/低时延占比从9∶1修改为7∶3。仿真结果为图 9所示，本文提出的粒子化接入算法依然明显优于对比方案。对比方案由于不关心业务流的内部情况，因此性能没有改变。而粒子化接入方案由于两类业务流总和的高/低时延粒子比例修改前后保持不变，且方案不关注信息粒子来源，因此性能没有变化。

5 结论

本文针对无线网络中多业务的时延保障问题，提出了粒子化接入的思想，并基于此提出了一种无线网络中的细粒度延迟保障机制。相比与传统的时延保障机制，本文提出的细粒度延迟保障机制所考虑的接入机制操控对象更加基础，即分组级别，并且所考虑的操控对象并不关注其来源和优先级，只考虑信息粒子的截止时间和承载信息量，因此具有更细的服务质量保障粒度和更好的可拓展性。进一步发现，在网络负载较重时，若信息粒子的截止时间很短，则在粒子化接入算法中，这个粒子将更不容易通过网络，这样的机制鼓励用户如实标记信息粒子的截止时间。在该机制下，如果网络比较拥塞，用户还可以选择在容忍范围内尽可能增大信息粒子的截止时间，来换取更高的网络通过性。可见，从根本上来讲，基于粒子化接入思想的细粒度延迟保障机制鼓励接入用户以更为诚实而高效的方式使用网络接入资源。另外，由于粒子化接入思想所具有的一般性，其还可被应用于改善包括Internet网在内的其他类型网络的服务质量保障性能。

下一步工作中，将进一步研究如何将本文所提出的接入机制拓展至更为一般的应用场景，如上行应用场景和复杂传输信道场景等。