基于冲突图的毫米波无线个域网并行调度方案

王一兵，牛勇，丁玮光，吴昊

（北京交通大学电子信息工程学院，北京 100044）

1 引言

随着移动数据业务需求的急剧增长，位于30～300 GHz的毫米波频段在第五代（5G）移动通信系统中逐渐受到了广泛的关注。其中，60 GHz毫米波（以下简称毫米波）频段是研究中使用较多的一个频段。一方面，毫米波较大的带宽和较高的发射功率，为高清视频、即时音乐、高清图像传输等无线个域网（WPAN, wireless personal area network）中带宽密集型多媒体服务的实现提供了可能[1-2]。另一方面，对于毫米波的高传播损耗，实际中一般采用定向天线和波束赋形技术加以克服。将发射机和接收机的波束相互对准[3]，这种定向通信使不同链路之间的干扰大大减小，因此，通过合适的调度算法，可以充分利用空分复用技术来进行并行传输[4]，进而提高整个网络的性能。

2 相关工作

在之前针对毫米波无线网络调度问题的研究中，许多基于时分复用（TDMA, time division multiple access）的方案被用于传输调度[5-6]。后来由于定向天线和波束赋形技术的发展，传播损耗对系统的影响得以改善[7-8]。并且定向通信可以减少链路之间的干扰，因此采用并行传输的方式可以提高系统吞吐量[9]。在现有的相关工作中，文献[5-6]的方案都是基于TDMA提出的，其目的是提高系统的传输速率和整个网络的吞吐量，尽管这2种方案在一定程度上提高了网络性能，但与并行传输所能达到的传输速率和网络吞吐量相比，还是远远不够的。文献[10]提出了一种在速率自适应无线网络中的双重更新并行调度算法，但并未考虑毫米波的特性所带来的影响。文献[4]在毫米波条件下提出了基于最大QoS独立集的并行调度算法，但是该算法是在小小区回传网络的场景下得出的。文献[11]提出了一种基于独占区的调度算法，确保了毫米波无线个域网内的并行传输总是比顺序的时分复用算法性能更佳。文献[12]提出了一种在考虑了流的吞吐量需求的前提下，以最大化网络中总流数为目标的翻转性算法，但是并未考虑网络中关于流之间冲突干扰的全局性信息。文献[13]提出了一种分布式传输功率控制解决方案，用于设备到设备（D2D, device-to-device）链路之间的并行传输调度，增大同时调度流的速率和并进一步提高网络吞吐量，但并没有考虑传输效率问题，无法实现对资源的充分有效利用。文献[14]提出了一种用于毫米波网络的能量有效调度方案，该方案利用并行传输来实现更高的能量效率，但没有对网络中的冲突干扰做出应对。因此，在60 GHz的无线个域网场景中，如何在时隙资源有限的情况下实现对资源的充分有效利用，以实现网络性能的全局最优，仍然存在一定的挑战。

本文提出了一种基于冲突图的空时分多址接入调度算法（CB-STDMA, contention graph based spatial-time division multiple access）。该算法对相同级别的流进行调度，一方面让所用时隙数较少的流优先被调度，从而节省出宝贵的时隙资源来调度更多的流；另一方面，只有被调度的流之间没有冲突，即不是相邻链路且相互干扰小于某个门限值时才能被同时调度，使被调度的流保持较高的速率，从而进一步增加了网络中满足吞吐量需求的流数以及网络的总吞吐量。本文中将最低吞吐量需求称为服务质量（QoS, quality of service）需求。

3 系统模型

本文考虑基于IEEE 802.15.3c协议的60 GHz室内无线个域网场景。场景中包括一个微微网控制（PNC, piconet controller）和几个无线节点（WN,wireless node）。无线节点之间可能有数据流需要进行传输，每条流都有自己的最低吞吐量需求，即QoS需求。PNC可以对网络中的数据传输进行同步和协调[15]，并且可以获得每条流的QoS需求以及各个无线节点的位置。每个无线节点都装有电子导向定向天线，从而使收发器之间可以进行定向传输来提高天线增益[16]。另外，假设各无线节点之间进行视距（LOS, line of sight）传输，从而尽量降低路径损耗。对于无线节点的发射机和接收机，则都假设是半双工的，即同一时刻只允许一条流进行传输（发送或接收）。

3.1 MAC层帧结构

在 IEEE802.15.3c协议中，网络时间被划分成一系列的超帧[17]，其介质访问控制层（MAC，media access control）帧结构如图1所示。每一个超帧由3部分组成：信标周期（BP, beacon period）、竞争访问周期（CAP, contention access period）、信道时间分配周期（CTAP, channel time allocation period）。在BP中，主要对来自PNC的网络同步和控制信息进行广播，如将对各流的调度决策广播给网络中所有的无线节点。在 CAP中，设备通过载波监听多点接入/冲突避免（CSMA/CA, carrier sense multiple access with collision avoidance）技术将自己的传输请求发送给PNC。在CTAP中，划分出许多时隙（TS,time slot），在每一个时隙，无线节点之间可以根据BP周期中接收到的调度命令进行有效的数据传送。在本文提出的方案中，因为毫米波的定向传输特性，每个时隙可以选择对多个流进行并行调度，即空时分多址接入（STDMA, spatial-time division multiple access）[18]。

图1 IEEE802.15.3c的MAC层帧结构

3.2 路径损耗模型

对于毫米波WPAN来说，本文假设节点之间可以进行视距传输，采用文献[14]中的路径损耗模型。流i的接收机ir接收到的来自对应发射机si的信号功率可以表示为

其中，k是与成正比的常数因子，P代表发t射机的发射功率，代表发送天线增益，代表接收天线增益，dii代表流i的发射机与接收机之间的距离，n为路径损耗指数。

类似地，流j的发射机对流i的接收机造成的干扰则可以表示为

其中，m是与不同用户信号间的互相关有联系的多用户干扰因子（MUI, multi-user interference）。

3.3 数据传输速率

在高斯加性白噪声（AWGN, additive white Gaussian noise）信道中，流i可达的数据传输速率可以根据香农公式得到，如式（3）所示。

其中，η是描述收发机设计效率的因子，取值范围为（0,1）；W为信道带宽；N0为高斯白噪声的单边功率谱密度。

4 问题建立与分析

假设网络中PNC一共收到F条流的传输请求，每条流i都有自己的QoS需求qi。每个超帧的CTAP中包含S个时隙，每个时隙可以同时对多个流并行调度。在第s个时隙中，用一个调度向量Hs来表示在该时隙有哪些流被调度。全部时隙共S个调度向量构成调度矩阵HF×S，若该矩阵中与流i对应的元素则代表流i在第s个时隙中被调度；若则代表流i在第s个时隙中未被调度。

因为用户之间的相互干扰，只有当调度向量确定以后，流i的实际传输速率才能被确定。因此，根据式（3）在第s个时隙中流i的实际传输速率可以表示为

经过T个时隙后，流i已经达到的吞吐量可以表示为

其中，Δt代表CTAP中时隙的时长，TBP代表信标周期的时长，TCAP则代表竞争访问周期的时长。

出于公平与效率的折中考虑，并且考虑到 5G场景中各种带宽密集型应用对服务质量的要求，本文以最大化网络中满足QoS需求的流数为目标。满足QoS需求是指，通过调度满足了该流的最低吞吐量需求。只有满足了数据流的QoS需求，才能保证各种带宽密集型应用的服务质量。二进制变量iF表示流i的 QoS需求是否被满足。Fi= 1表示流i的QoS需求已经被满足，Fi= 0则表示尚未满足。据此，最优调度问题可以被定式化为问题 P，如式（6）～式（9）所示。

约束条件为

式（8）表示该流的QoS需求必须在CTAP中给定的时隙数之内能够满足。如果该流在所有的时隙中都被调度，但其QoS需求仍无法满足，则不予调度。式（9）表示由于发射机和接收机节点的半双工特性，同一节点在同一时刻只能对一条流进行传输（发射或接收）。当流i和流j有共享节点（即si=sj或si=rj或ri=sj或ri=rj）时，定义流i和流j是相邻的。相邻的流不能被同时调度。

问题 P是一个整数非线性规划问题，它是NP-hard问题[4]。每条流在每个时隙都可以被调度或者不被调度，如果使用穷举法来计算它的解，当流数为F且时隙数为S时，计算的复杂度为2F×S。当流数较多时，采用穷举法是非常耗时的。因此，本文提出了一种基于冲突图的并行调度算法来解决这个问题，以降低它的复杂度。

5 基于冲突图的STDMA并行调度算法

本节提出了一种基于冲突图的 STDMA调度算法，即CB-STDMA算法，用来提高被调度的流的数量。首先定义了相对干扰、冲突图、预调度集和调度集的概念。

5.1 相对干扰

为了最大化被调度流的数量，尽可能地使被调度的数据流保持一个较高的速率，从而使调度更加有效，在对流i进行调度决策时，如果已经决定要调度的流中存在流j对流i的干扰大于给定的门限σ,则对流i不予调度。2条流之间的相对干扰RIji可以定义为

5.2 冲突图

以图2为例，图中4个节点代表4条流，流1与流2之间有边，代表流1与流2之间存在冲突，可能是由于2条流之间有共享节点或2条流之间干扰超过门限值导致的，所以流1与流2不能同时调度。流1与流4同理。而流1与流3之间没有边，说明不存在共享节点和干扰等问题，可以同时调度。此时对应冲突图的邻接矩阵A中对应元素a12、和a14均为1，其余元素为0。

图2 冲突图实例

5.3 预调度集与调度集

在本文的算法中，并不是所有请求传输的流都可以被调度。为了解决式（6）中的最优调度问题，使大多数流的QoS需求得以满足，提高整个网络传输效率，会有很小一部分流被舍弃不参与调度。因为CTAP中时隙的个数是有限的，如果该流在所有的时隙中都被调度时，仍然不能满足它的QoS需求，则对该流的调度实际上是一种对时隙资源的浪费。因此，对这部分流不予调度，从而把时隙用于对其他流进行有效的调度。为了增加调度的流数，在剩余的流中应当优先对所用时隙数少的流进行调度。当某条流的QoS需求被满足后，就认为它的服务质量已经得到保证，继续调度该流，对服务质量的增加也不明显。因此，需求被满足的流在以后的时隙中都不会再被调度，从而把时隙资源供给更多的流使用。然后，将那些可以在给定的S个时隙内满足其 QoS需求的流按照传输所用时隙数的从小到大进行排序，这样得到的可以被调度的流的集合称为预调度集（PSS, pre-schedule set），即准备调度的流的集合。具体地，流i传输所用的时隙数可以按照式（12）进行计算。

需要注意的是，式（12）中Ri是在没有其他流干扰情况下得到的自身传输速率，即式（3）中去掉项得到的速率；Δt代表每个时隙的时长。

此外，把第s个时隙中被调度的流的集合叫作第s个时隙的调度集（SS, schedule set），即调度向量Hs中等于 1的元素对应的流所组成的集合。CB-STDMA 算法对于第s个时隙调度的流的数量没有明确的限制，只要满足可以同时传输的条件，便可以同时使用第s个时隙传输。

事实上，根据5.2节中的冲突图来确定单个时隙调度的流，虽然没有确定的条数限制，但相对干扰的门限值会对流的数量进行制约，同一时隙调度的流的条数不会太多。因为同时调度数量过多时，必然无法满足相对干扰低于门限值的条件。所以单个时隙调度的流的个数无法确定，要由本文提出的算法根据实际情况来计算。

5.4 调度算法设计

下面对 60 GHz无线个域网中的 CB-STDMA算法进行详细描述。该调度算法的伪代码见算法1，其中第1）行～第8）行是初始化工作，第9）行～第23）行是算法的主要部分。

首先，在某一超帧的 CAP中，各个无线节点将自己的位置以及数据流的传输请求发送给PNC，每条流都有自己的QoS需求qi。PNC收到各条流的传输请求后，计算各条流传输所用的时隙数iξ，将iξ大于CTAP中最大时隙数S的流舍弃，剩下的流按照iξ从小到大的顺序排序，作为预调度集。然后，判断可进行同时调度的流。上述过程如算法 1中的 1）～8）行所示。

CB-STDMA算法判断可同时调度的流是由PNC根据5.2节所描述的方法，生成包含预调度集中所有流的冲突图即生成预调度集的对应冲突图的邻接矩阵，根据式（10）计算流之间的相对干扰，然后考虑流之间是否存在共享节点和相对干扰是否超过门限值，来判断能否同时调度，确定矩阵中各个元素的值。

本文调度算法为了实现式（6）中的优化目标，即尽可能提高满足QoS需求被调度流的个数，除了选择并行传输的传输方式本身就可以提高性能外，算法中选择了不间断的数据流调度方案也是实现优化的关键。在每一个时隙结束时，都要检查是否有某些流的QoS需求已经被满足。当一个流的QoS需求已经被满足时，就将调度向量Hs中对应的元素设为-1，表示该流在以后的时隙中都不能被调度，并在下一时隙选择满足条件的新的流加入调度集合。对于没有完成其QoS需求的流，下一时隙中则继续调度。这一过程如算法1中 20）行～22）行所示。算法中调度向量Hs中值为-1的元素越多，表示有越多的被调度流已经满足QoS需求，越能体现出算法的优越性。

对于每一个时隙，如果是第一个时隙或者在上一个时隙中有新的流达到了其QoS需求，就开始一轮新的调度决策。对预调度集中的每一条流按顺序进行判断，如果这条流以前没有被调度过，并且与当前调度集中的流（即已经决定被调度的流）之间没有冲突，则接着对调度这条流的收益进行评估。评估的标准是，如果把它加到当前调度集中可以增加网络的总吞吐量，就把该流添加进来，否则放弃对该流的调度，继续对下一条流进行判断。这一部分如算法1中的11）行～17）行所示。直到所有时隙都做出了调度决策，从而得出了S个时隙的调度矩阵HF×S。

算法1CB-STDMA并行调度算法

1） PNC接收各个节点的位置以及带有QoS需求qi的F个流的传输请求，并初始化F×1的预调度集PSS = 1

2） 初始化调度矩阵HF×S=0

3） 计算每个流传输所用的时隙数iξ,并将PSS中的流按所用时隙数从小到大顺序排列，I= 排序后的序号

4）ifξi＞Sthen

5）F = i-1

6） 更新F×1 的 PSS 以及HF×S

7）end if

8） 构建F个流的冲突图G，初始化change = 1

9）for时隙i（1≤i≤M）

10）ifchange = 1then

11）for流f（1≤f≤F）do

12）ifSi（f） = 0且i与当前调度集中其他流没有冲突then

13）if加入流f可以增加网络总吞吐量then

14）Si（f） = 1

15）end if

16）end if

17）end for

18）end if

19） change= 0,Hs+1=Hs

20）if存在Ti≥qithen

21） change = 1,Hs+1（i） = -1

22）end if

23）end for

6 性能评估

本节对本文提出的调度算法进行了仿真，并与文献[4]提出的MQIS并行调度算法、文献[12]中提出的STDMA并行调度算法和TDMA调度算法进行了对比。在TDMA算法中，CTAP的每一个时隙中只允许一条流进行传输。

6.1 仿真参数设置

假设60 GHz 无线个域网中有10个无线节点随机分布在10 m×10 m的方形区域内，PNC位于区域的中央。每个节点所配置的定向天线产生的波束宽度为60°，并且使用文献[15]中的实际定向天线模型。每条流的源节点和目的节点都是随机选择的，节点之间的平均距离是1 m。每条流的QoS需求是在1 Gbit/s到3 Gbit/s之间均匀分布的随机变量。仿真中其他的一些主要参数如表1所示。

在不同任务数时都是影响系统性能的关键因素。而存储服务器CPU性能和磁盘性能则在不同任务数时对系统 I/O响应时间的影响都很小，属于非关键性能影响因素。上述网络RAID存储系统因素的一种有效手段，在优化系统性能时，可基于上述分析结果着重考虑改善关键性能影响因素，忽略非关键性能影响因素，以达到事半功倍的效果。

6.2 性能指标

为了验证所提出的调度方案的性能，本文主要从满足QoS需求的流数以及系统的吞吐量这2个方面进行评估。系统的吞吐量是指网络中所有流的吞吐量总和。

分别改变网络中发出传输请求的总流数、CTAP中时隙的个数以及判断相对干扰时所用的判决门限σ，观察满足QoS需求的流数和系统吞吐量的变化情况。所有仿真结果图中的每个点是100次随机仿真后的平均值。

6.3 仿真结果与分析

满足 QoS需求的流数和系统吞吐量随着网络中总流数的变化分别如图3和图4所示。此时时隙数为2 000，判决门限为10-1。

图3 不同流数下满足QoS需求的流数

图4 不同流数下的系统吞吐量

从图3和图4可以看出，当网络中流的总数增长时，本文提出的CB-STDMA算法、MQIS算法和STDMA算法满足QoS需求的流数和系统吞吐量这2个指标都随之增长，但是TDMA算法的2个指标却几乎不变。这是因为TDMA算法在每个时隙只能对一个流进行调度，所以不管流的总数如何变化，它所能满足的流数是有限的。而CB-STDMA算法、MQIS算法和STDMA算法允许多条流之间的并行传输，所以流的总数越多，进行并行调度的机会越大，能满足需求的流数和系统吞吐量也越大。但由于系统容量和时隙资源的限制，增长趋势逐渐趋于平缓。此外，CB-STDMA算法比MQIS算法和STDMA算法性能更优越。特别地，当流总数为90时，MQIS算法能成功满足 13条流，吞吐量约为 24 Gbit/s，STDMA算法能成功满足约10条流，吞吐量约为25 Gbit/s，CB-STDMA算法则可以成功满足约16条流，吞吐量达到约 30 Gbit/s。与 MQIS和STDMA相比，CB-STDMA满足QoS需求的流数分别增长了约23%和60%，吞吐量分别增长了约25%和 20%。造成这种现象的原因主要来自于以下2个方面。

1） MQIS算法中，只利用并行传输和QoS需求来判定优先级，没有舍弃部分需求过大的流，也没有考虑调度流的条数和传输效率，会造成部分资源浪费。STDMA算法中，只要将流加入调度集可以增加网络的吞吐量，就决定调度该流，没有考虑调度集中其他流对该流的干扰。而 CBSTDMA中，将网络中所有流的冲突关系都用冲突图表示出来，根据流之间的冲突关系进行调度，使得调度集中不同流间相互干扰减小，从而增加了所调度的流的传输速率。

2） 在CB-STDMA算法中，按照所需时隙数由少到多的优先级顺序对流进行选择调度，并不是所有请求传输的流都可以被调度，若CTAP中所有时隙都不够满足该流的传输需求，则直接舍弃该流不予调度，这样便能节省出时隙，供给那些可以实现其 QoS需求的流利用，使整个网络的传输效率得到明显提高。综上所述，CB-STDMA算法在优化问题，即被调度流的数量和网络总吞吐量方面有着明显的优势。

满足QoS需求的流数和系统吞吐量随着CTAP中时隙数目的变化如图4和图5所示。此时网络中的总流数为90，门限值仍取10-1。

图5 不同时隙数下满足QoS需求的流数

图6 不同时隙数下的系统吞吐量

从图5和图6中可以看出，CB-STDMA算法的2种指标仍然都优于MQIS算法、STDMA算法和TDMA算法。特别地，在时隙数为5 000时，CB-STDMA与MQIS相比，成功满足的流数增加了超过 23%，系统吞吐量增加了约 25%；而CB-STDMA比 STDMA成功满足的流数增加了超过60%，系统吞吐量增加了约20%。但是，这4种算法都只在时隙数为500到2 000时性能有增长趋势，当时隙数超过2 000时，性能几乎没有变化。这是因为在时隙资源较少时，时隙数是影响网络性能的主要限制因素，有限的资源无法满足较多流的QoS需求，因此增加时隙数使更多的流成功调度并且增加网络的吞吐量。而时隙数目继续增加时，由式（5）可知，吞吐量与时隙数的关系不大，因此总吞吐量并没有太大变化，满足最小吞吐量需求的流数也没有太大变化。所以，想要达到理想的优化目标，获得更多被调度的流，并且保证资源的充分利用，必须选择合适的时隙数目。在本文其他仿真中，只要选择时隙数在2 000时就足够得到接近最优的性能。

改变冲突图中的干扰判决门限σ，相应的指标变化如图7和图8所示。图中的横坐标是将门限值以10为底取对数的值（如门限值为10-1时，则横坐标为-1）。此时流的总数取90，时隙数取2 000。

图7 不同门限值下满足QoS需求的流数

图8 不同门限值下的系统吞吐量

从图7和图8中可以看出，TDMA与STDMA因为不涉及冲突图中的干扰判断门限，因此网络性能并不随着门限值变化。而对于 CB-STDMA和MQIS，若门限设置过小，则2条流之间有很小干扰时就认为它们之间有冲突，不利于对流进行充分的调度。此时，门限值是限制网络性能的主要因素，增大门限值有利于增加满足 QoS需求的流数和网络的总吞吐量，因此曲线在门限值为10-4～10-1时呈上升趋势。当门限值继续增大时，即使各条流之间有较大的干扰，也认为它们之间不存在冲突，这时将受到干扰较大的流加入调度集中，对于增加网络的性能是不利的，因此门限值为10-1～1时，曲线出现下降。在门限值10-1时，本文提出的CB-STDMA算法性能最优，这也是在之前仿真中将门限值设为 10-1的原因。门限值大于10时，由于流之间的相对干扰根本达不到这么大，门限值失去了它的约束作用，因此CB-STDMA的相应指标曲线也变得平坦。

7 结束语

本文为毫米波无线个域网场景设计了一种基于冲突图的并行调度算法。在进行调度决策时，考虑了网络全局的冲突条件，包括流之间的互干扰条件和半双工限制条件，并优先调度容易满足QoS需求的流，从而最大化满足QoS需求的流数和网络吞吐量。仿真结果表明，本文提出的CB-STDMA算法与STDMA算法和TDMA算法相比，在满足QoS需求的流数和网络吞吐量方面均有大幅提升。此外，通过仿真还发现，通过优化冲突判决时的门限值可提升算法的性能。