分布式WLAN 全双工链路加权调度算法

官 铮，胡 扬，杨志军，何 敏

1.云南大学 信息学院，昆明650500

2.云南省教育厅 教育科学研究院，昆明650223

当今时代，随着新一代信息技术的发展和无线接入设备的普及，移动终端的数量和数据都呈现出一个爆炸式增长趋势，给无线通信网络带来了不小的压力。当前无线局域网络大多采用的是半双工（half-duplex，HD）模式，限制了网络性能的同时也造成了无线频谱资源的浪费。无线网络带内全双工（in-band full-duplex，IBFD）技术理论上可实现通信系统信道容量的倍增，近年来随着自干扰消除（selfinterference cancellation，SIC）等物理层技术的日渐成熟，通过自干扰抑制和消除技术，使网络中单节点的同时同频全双工（co-frequency co-time full duplex，CCFD）得以实现。

然而若要进一步实现多节点之间的带内全双工无线通信，一方面，需要抑制节点间互干扰；另一方面，还需要网络层面带内全双工无线通信MAC 协议及调度机制的支持。

集中式网络架构WLAN 中，位于基站的接入点（access point，AP）集合了802.11 标准定义的所有功能,无线资源都通过AP 在全网进行动态协调。现有大部分IBFD MAC 协议均针对集中式网络架构，即数据仅在节点和AP 之间传输，节点间的数据交换需经由AP 转发。针对节点间的数据传输会在AP 产生碰撞的问题，文献[5]设计出一种全双工MAC 协议，发生碰撞的隐藏节点通过冲突解码和报告（collision decoding and reporting，CDR）汇总给AP，根据报告信息再由AP 选择节点对链路进行调度以规避冲突来提升网络吞吐量。文献[6]在IEEE802.11 点协调（point coordination function，PCF）机制的基础上提出一种用于AP 和站点传输的混合服务双向轮询访问控制机制。以Janus 为代表的预约式全双工MAC 协议通过AP 汇聚节点信息、维护上下行调度顺序，节点在AP 控制下建立全双工链路。

传统通信能力的增长严重依赖基础设施和资源投入，如从2G到5G，通信效率提升亟待开拓新维度。随着移动通信从3G 频段提升至高频毫米波频段可有效提升带宽，受高频信号传播范围小的约束，对等用户之间的直接通信，将更利于短距离通信。此外，用户在访问硬件资源时无需借助于其他中间实体，也可有效提升硬件的访问速度。

随着网络架构逐渐以基站为中心被调整为以用户为中心，设计分布式IBFD MAC 协议成为实现无中心控制下多节点同时同频接入的关键。

目前的分布式无线网络中应用同时同频全双工的协议大多是基于IEEE 802.11 协议中的CSMA/CA机制。混合双工媒体接入控制协议（hybrid-duplex MAC，HYD-MAC）根据链路调度时网络节点状态和全双工能力自适应选择传输模式。文献[14]提出一种将TDMA 和CCFD 相结合的MAC 协议，通过建立二级链路来增加同一时隙中的共存的传输链路数以改善重负载时网络的时延和吞吐量。赵阳提出一种基于预约的分布式多信道链路调度算法（based on reservation-distributed multi-channel，BR-DMC），通过预约的方式分配节点不同信道上的时隙资源，能够无冲突地进行链路调度，动态地适应业务变化，实现了移动自组织网络下的分布式独立多信道链路调度。但是上述链路调度算法主要是针对网络吞吐量和时延进行优化，未考虑节点公平性和协议的后向兼容性问题。

传统的分布式网络在进行链路调度的节点选取时大多采用随机接入的方式，这就有可能导致某些数据量大的节点接入网络的等待时间较长，而其他节点过于频繁的工作使得系统在时间和空间资源利用上不公平。Ad Hoc 网络节点间组成的网络具有临时性，彼此通信通常要经过多跳才能实现。对于某些没有基础通信设施环境，如部队的协同作战、野外考察、灾后营救等场合，Ad Hoc 网络以其灵活的组网方式备受关注。在这些场合下，除了对网络的传统数据传输的指标进行要求外，每个节点的反应应更加迅速，节点间的数据传输应更加及时，因此需要考虑分布式场景下节点的公平性需求。此外，在工业物联网等超可靠、高时效性网络中，除考虑节点发送时延平均性能外，还应关注其尾部特性。

本文提出一种基于节点调度权重的全双工链路调度算法（full-duplex link scheduling algorithm based on nodal scheduling weights，W-FD），能够综合考虑节点的数据收发能力和链路结构对网络中的节点和调度过程进行动态调整，在提高吞吐量和降低时延的同时有效保障了节点的公平性需求。

1 系统模型

系统采用分布式网络架构，无中心控制节点，数据在节点间转发，即每个节点在网络中均可充当发送者、接收者和中继。控制策略模型如图1 所示。图中，、为由与节点发送和接收相关的业务队列、缓冲区大小和拓扑结构等构成的函数；为节点的调度权重；为节点的全双工阈值，用于判定优先节点在链路中的双工模式；为节点的工作状态；为传输链路中的节点的工作模式；e、e为节点的权重修正参数。

图1 控制策略模型Fig.1 Model of control strategy

假设网络中所有节点均有数据待发送，在调度过程开始前节点根据自身的业务队列、缓冲区大小和拓扑结构等计算出自身的调度权重(=e f+e f)，通过节点以及其邻居节点组成的邻域内调度权重的对比，选取权值最大(Argmax())的节点作为优先节点并建立数据传输链路，为了避免产生碰撞，邻域内不参与链路传输的节点应根据其与链路的关系对自身状态重新定义(,)，并将修正参数反馈给节点(e,e)，对自身的调度权重进行修正。对于未参与链路建立的节点，其调度权重会随着时间增加；而对于参与链路建立的节点，在下一次调度开始前，该节点会根据自身工作模式将调度权重置0 并重新计算。

1.1 全双工链路前提条件

（1）全连通分布式网络：网络中所有节点与其他任意节点均有路径可达，每个节点至少有两个邻居节点。

（2）同时同频全双工技术：允许节点在同一频段上发送数据的同时也能够接收数据。

如图2（a）中、构成双向链路，（b）中、、构成二级链路。

图2 全双工链路示意图Fig.2 Full-duplex links in network

图2 表示为分布式结构网络中的两种全双工链路。图2（a）中节点和同时处于发送和接收状态，且互为发送的源节点和接收的目的节点，因此和构建双向链路；图2（b）中节点处于发送状态，处于发送和接收状态，处于接收状态，既是的目的节点又是发送数据至的源节点，因此、和三个节点构成二级链路。

1.2 节点状态描述

在基于802.11 协议的基础上，本文对分布式网络中的任一节点的状态定义如下：

其中，S=00 表示节点为自由状态，允许接收和发送数据；S=01 表示节点为接收禁止状态；S=10表示节点为发送禁止状态；S=11 表示节点为静默状态，不允许发送和接收数据。

对于已经建立数据传输链路的节点，对工作模式的定义如下：

其中，SL=00 表示节点处于全双工模式；SL=01表示节点处于半双工中的发送模式；SL=10 表示节点处于半双工中的接收模式。

对于链路中节点的链路外邻居节点，为了消除对数据传输链路的干扰，其节点状态会受到链路影响。对不同工作模式下的节点，其链路外的邻居节点状态如图3 所示。

图3 链路外的邻居节点状态Fig.3 Status of neighbor node outside transmission link

图3 所示为链路外邻居节点，（a）中节点处于发送状态，为了避免受到来自节点发送数据的干扰，节点应为禁止接收状态；同理，（b）中节点处于接收状态，为了确保成功接收，节点应为禁止发送状态；（c）中同时处于发送和接收状态，此时只能处于静默状态。

2 加权式全双工链路调度算法

为了在优化节点吞吐量和降低时延的同时提高节点的公平性，本文提出一种基于节点调度权重的链路调度算法。假设全联通分布式网络中所有节点均具有全双工能力，信息分组在产生和传输的过程中无丢包等情况。在链路建立前各个节点为自身分配权值，分布式网络中多节点满足链路建立条件时，根据调度权重决定的节点接入优先级和链路类型选取链路建立对象，权重值越高的节点参与链路传输的机会越大，从而在实现全双工链路调度的同时保证了节点公平性。

2.1 节点调度权重

节点调度权重由以下三个因素决定：

（1）个体因素：节点自身的收发能力、拓扑结构。

（2）环境因素：所有邻居节点的收发能力、拓扑结构。

（3）时间因素：节点接入链路的时间间隔、链路的调度间隔。

设节点等待发送的业务数为m，节点允许缓存的最大业务量为，邻居节点个数为n，其集合为N，节点作为发送节点的间隔时间为t,节点作为接收节点的间隔时间为t。假设b∈N(1 ≤≤n)，链路(,b)的调度间隔为t。 e和e表示节点的权重修正参数。定义E为节点的发送能力，E为节点的接收能力，B表示节点的发送系数，B表示节点的接收系数，根据式（3）～（6）计算。

式中，K表示节点自影响发送权重参数，K表示节点与邻居间互影响发送权重参数，定义如下：

式中，e表示节点是否被允许发送，允许时e=1，禁止时e=0。

K表示节点自影响接收权重参数，K表示节点与邻居间互影响接收权重参数，定义如下：

W表示节点的接收权重：

式中，e表示节点是否被允许接收，允许时e=1，禁止时e=0。

式（3）和式（4）是对节点自身收发能力的定义，若等待发送的业务数m越大，则节点在后续的调度过程中作为发送节点接入网络的机会越多，表明发送能力E越大；若m越小，则节点业务缓存队列的空位越多，在后续的调度过程中作为接收和中继转发节点接入网络的机会越多，表明接收能力E越大。式（5）和式（6）是出于对节点接入优先级的考虑，节点在选择邻居节点作为链路建立对象时，除目的节点以外的其他邻居节点都会受到限制，因此，节点的n越大则接入网络时受到限制的邻居节点越多，优先顺序应当靠后；节点及其邻居节点的业务队列会随时间累加，而t和t作为节点发送和接收的响应等待时间，考虑节点自身的负载均衡，t和t越大则节点的优先级越高。式（7）和式（10）是对发送自影响参数和接收自影响参数的定义，在式（5）和式（6）的基础上，加入了对节点与所有邻居节点建立链路的调度间隔的考虑，作为对节点所在邻域在时间因素下对整个网络影响的一个补正。

与上述同理，式（10）～（12）用于计算与节点的接收权重W和与之相关的参数。

W和W分别被定义为综合考虑个体、环境和时间因素下节点作为发送和接收节点的可能性，在下文中，W和W的作用体现在：（1）计算节点的调度总权重W，W与其所有邻居节点的W的比较用于定义优先节点；（2）若节点为优先节点，根据W和W的比较来判定节点的双工模式；（3）若节点不为优先节点，则W和W用于与非优先节点的其他节点竞争，由优先节点来判断节点能否成为建立链路的目的节点。

式（13）表示节点在不同状态下e和e的取值。

式（14）的W表示节点的调度总权重：

（优先节点）对于节点以及其任意邻居节点b∈N，若调度总权重满足

则节点为优先节点。时隙中的优先节点具有较高的机会参与链路调度。

2.2 调度原则

根据定义1 可得出下述定理1：

在一个由全向传输的全双工节点组成的网络中，同一时隙中任意两个优先节点的最短跳数至少为2。

设网络中两个节点、，其邻居节点集合分别为N、N，对于任意节点∈N，∈N均有W＞W，W＞W，则节点、为优先节点且≠，≠。若、最短跳数为1，则∈N，∈N，与≠，≠矛盾，故节点、之间最短跳数至少为2。

上述定理保证了优先节点之间的发送和接收互不干扰。

2.3 优先节点的双工模式

为了对优先节点工作的双工模式进行判定，提出节点全双工阈值的概念。

假设节点为优先节点，当节点数据收发能力满足以下关系时：

对于节点的所有邻居节点N均有：

此时节点所有邻居节点均具有双向传输的最大可能性。据此定义节点的全双工阈值ε：

（1）W≠0，W≠0，若 |W-W|≤ε，则SL=00，节点工作在全双工模式下；若W-W＞ε，则SL=01，节点工作在发送模式下；若W-W＜ε，则SL=10，节点工作在接收模式下。

（2）W≠0，W=0，则SL=01，节点工作在发送模式下。

（3）W=0，W≠0，则SL=10，节点工作在接收模式下。

3 链路调度过程

在链路调度开始前，所有节点需要对各自的邻居节点广播自身的B、B值，以获得节点与其邻居节点的调度权重。节点答复请求过程遵循CSMA/CA 工作机制。根据优先节点的工作模式的不同，链路的调度类型也有所不同。

（1）优先节点工作在全双工模式下的双向链路。如图4 所示，节点、分别是节点、的邻居节点，优先节点根据业务需求和调度权重选择节点作为建立全双工双向链路的目的节点，构建链路⇋(SL=SL=00)。为了避免对链路⇋的干扰，作为邻居节点的、此时应满足S=S=11，于是e=e=e=e=0，因此在修正和广播自身权重后，节点、应保持静默直到⇋传输过程结束。

图4 双向链路调度过程Fig.4 Scheduling process of bidirectional link

广播，询问邻点业务需求，有需求的邻点答复W、W。

得出max(W)、max(W)对应相同地址（节点）。

广播，包含地址。

答复并广播，短帧间隔后广播。

所有接收到、、的节点修正自身调度权重值并广播。

邻点除外，接收到后禁止发送数据，接收到后禁止接收数据。邻点除外，接收到后保持静默。

接收到和后广播。

（2）优先节点工作在全双工模式下的二级链路。如图5 所示，节点、、分别是节点、、的邻居节点，优先节点根据业务需求和调度权重分别选择节点、作为建立全双工二级链路中的上游节点和下游节点，构建链路→→(SL=01,SL=00,SL=10),于是e=0，e=e=0，e=0，因此在修正和广播自身权重后节点应保持禁止接收状态，节点应保持静默状态，节点应保持禁止发送状态直到→→传输过程结束。

图5 全双工模式下优先节点的二级链路调度过程Fig.5 Scheduling process of secondary link by full-duplex priority node

广播，询问邻点业务需求，有需求的邻点答复W、W。

得出max(W)、max(W)以及对应的地址（节点、）。

广播，包含、、地址。

答复并广播，答复并广播。和均包含地址。

所有接收到、、的节点修正自身调度权重值并广播。

邻点除外，接收到后禁止接收数据；邻点除外，接收到后禁止发送数据；邻点除、外，接收到后保持静默。

接收到和后广播。

（3）优先节点工作在发送模式下的二级链路。如图6 所示，节点、、分别是节点、、的邻居节点，优先节点根据业务需求和调度权重选择节点作为建立全双工二级链路中的中继节点，节点再根据业务需求和调度权重选择节点作为下游节点，构建链路→→(SL=01,SL=00,SL=10)，于是e=0，e=e=0，e=0，因此在修正和广播自身权重后节点应保持禁止接收状态，节点应保持静默状态，节点应保持禁止发送状态直到→→传输过程结束。

图6 发送模式下优先节点的二级链路调度过程Fig.6 Scheduling process of secondary link by sending priority node

广播，询问有业务需求邻点的W，邻点答复。

得出max(W)以及对应的地址（节点）。

广播，包含、地址。

接收到后广播，询问除外有业务需求邻点的W，邻点答复。

得出max(W)以及对应的地址（节点）。

广播，包含、、地址。

答复并广播，答复并广播。和均包含地址。

所有接收到、、的节点修正自身调度权重值并广播。

邻点除外，接收到后禁止接收数据；邻点除外，接收到后禁止发送数据；邻点除、外，接收到后保持静默。

0接收到和后广播。

（4）优先节点工作在接收模式下的二级链路。如图7 所示，节点、、分别是节点、、的邻居节点，优先节点根据业务需求和调度权重选择节点作为建立全双工二级链路中的中继节点，节点再根据业务需求和调度权重选择节点作为上游节点，构建链路→→(SL=01,SL=00,SL=10)，于是e=0，e=e=0，e=0，因此在修正和广播自身权重后节点应保持禁止接收状态，节点应保持静默状态，节点应保持禁止发送状态直到→→传输过程结束。

图7 接收模式下优先节点的二级链路调度过程Fig.7 Scheduling process of secondary link by receiving priority node

广播，询问有业务需求邻点的W，邻点答复。

得出max(W)以及对应的地址（节点）。

广播，包含、地址。

接收到后广播，询问除外有业务需求邻点的W，邻点答复。

得出max(W)以及对应的地址（节点）。

广播，包含、、地址。

答复并广播，答复并广播。和均包含地址。

所有接收到、、的节点修正自身调度权重值并广播。

邻点除外，接收到后禁止发送数据；邻点除外，接收到后禁止接收数据；邻点除、外，接收到后保持静默。

0接收到和后广播。

4 算法性能指标

4.1 公平性评价

传统MAC 协议中节点参与网络以随机接入的方式实现，成功发送数据的节点总是可以得到更多的信道占用机会，而失败的节点一直处于忙等状态，导致现实中有些节点会因为其他节点的恶意破坏而失去发送机会。

假设节点、和互为邻居节点，在不考虑节点待发业务的情况下，在传统MAC 协议中，假设网络接入周期为，节点、和接入网络的次序的可能情况是：

对比和，因为中过于频繁地接入网络导致接入网络的机会较少，而中每个节点接入网络机会相同，所以的节点接入公平性要好于。采用公平性指标：

式中，越小，说明节点的接入公平性越好。而Var=9.92，Var=0，说明的节点接入公平性达到最佳状态。

4.2 吞吐量分析

为了对网络吞吐量进行理论分析，文献[14]提出了全双工链路网络吞吐量概念，假设节点分组到达流满足均值为的泊松过程，每次发送一个数据分组且队列总不为空。理论上某一时隙内系统的最大网络吞吐量如式（18）所示：

其中，P表示系统的最大网络吞吐量，表示网络的信道容量，表示接入网络的节点数，τ表示同步时隙长度，τ表示业务时隙长度，τ+mτ表示时隙的总长度，·τ(0 ＜＜1)表示一个数据分组占用的时隙长度，(0 ＜≤1)表示二级和双向链路的调度成功率。据此可知网络吞吐量与时隙内共存链路数(,)成正比。

对于无次级链路调度的半双工系统，其最大吞吐量如式（19）所示：

对比式（18）和式（19）可知，相较于半双工链路调度，全双工系统理论上可实现最大吞吐量的翻倍。

4.3 时延分析

当半双工系统满足以下条件时：

（1）分布式网络中所有节点可被分为个不重叠的子网络；

（2）各子网包含节点数大于2 且均为完全图；

（3）所有节点的接入公平性达到最佳状态；

（4）各子网中链路之间无干扰。

可采用轮询系统中限定1 服务模型对每个子网络的平均等待时延进行推导。

文献[16]对限定1 服务模型的平均等待时延进行了理论推导，假设系统工作条件如下：

（4）第个子网中包含节点数为N(N＞2)，且各节点缓存足够大，不会产生丢包现象。

在Nδ(θ+γ)＜1 的条件下系统的概率分布达到稳态，则第个子网中的信息分组的平均等待时延为：

据此可得出整个半双工系统的平均等待时延为：

对于包含全双工节点的系统，信息分组的平均等待时延为：

5 仿真与结果分析

本文采用Matlab 仿真工具对所提出协议的性能进行分析，并和传统半双工（RTS/CTS）、FD-TDMA以及ContraFlow 协议在网络吞吐量、时延、公平性和链路调度间隔方面进行实验对比。

在一次实验中，100 m×100 m的区域内随机分布着20个通信节点，节点的最大通信距离为35 m，每个节点至少有两个邻居节点，其他仿真参数均参照文献[14]设置，如表1 所示。文中所使用的曲线图中的每个样点图均来自10 次实验的平均值。

表1 仿真参数表Table 1 Simulation parameter table

图8～图11 给出了在所有节点业务负载相同的情况 下，W-FD、传 统HD（RTS/CTS）、FD-TDMA 和ContraFlow 公平性、链路调度间隔、吞吐量和平均时延随信息分组到达率变化的曲线图。

图8 公平性对比曲线Fig.8 Comparison curve of fairness

图8 表示W-FD、HD（RTS/CTS）、FD-TDMA 和ContraFlow 的节点公平性对比，在信息分组到达速率较小时，此时服务速率要远大于分组到达率，导致四者方差近似一致，公平性对比不明显。但随着到达率的提高，图中HD（RTS/CTS）、FD-TDMA 和Contra-Flow 的方差曲线呈明显上升趋势，而W-FD 算法的方差趋势较为平稳，说明W-FD 相比HD、FD-TDMA 和ContraFlow 协议具有更好的节点公平性。图9 表示四种协议链路调度间隔时间的对比，图中每个采样点代表网络中任意两个邻居节点所在链路的响应等待间隔时间的均值。结果表明W-FD 的平均链路调度间隔总体上也小于另外三种协议。

图9 链路调度间隔对比曲线Fig.9 Comparison curve of link scheduling interval

采用单位时隙内共存链路数量对吞吐量进行定性分析。如图10 和图11 所示，随着分组到达率的增加，单位时隙内网络中的共存链路数（吞吐量）也随之增加。传统RTS/CTS 半双工链路调度算法在到达率约为50 分组/s 时共存链路数达到饱和，而本文提出的W-FD 在到达率约为100 分组/s 时吞吐量才达到饱和，且比传统半双工链路调度算法的最大吞吐量有明显提高，排队时延有明显降低。相比于Contra-Flow 协议，W-FD 在吞吐量和时延上略有优势，但与FD-TDMA 相比，在分组到达率较小时，W-FD 和FDTDMA 吞吐量和时延性能虽然相差无几，但随着到达率的增加，FD-TDMA 吞吐量和时延性能要逐渐优于W-FD。这是因为W-FD 采用竞争接入方式，在高负载时，碰撞概率的升高影响了吞吐量和时延性能的提升。

图10 时隙中共存链路数对比曲线Fig.10 Comparison curve of quantity of co-existing links in slot time

图11 平均等待时延对比曲线Fig.11 Comparison curve of average waiting delay

表2～表4 给出了各节点到达率在[1 ,10]、[1 1,50]和[5 1,100] 三个区间内随机取值的情况下，当节点数分别为20、50 和100 时W-FD、FD-TDMA 和Contra-Flow 的平均单位时隙内共存链路数、平均等待时延、节点休眠时间方差和平均链路调度间隔。其中每个数值均取自10 次实验平均值。

表2 节点数为20 时三种协议性能对比Table 2 Performance comparison of three protocols with 20 nodes

表3 节点数为50 时三种协议性能对比Table 3 Performance comparison of three protocols with 50 nodes

表4 节点数为100 时三种协议性能对比Table 4 Performance comparison of three protocols with 100 nodes

从表2～表4 可以得知，当各节点拥有不同的分组到达率时，随着节点数的增加，FD-TDMA 和Contra-Flow 的节点休眠时间方差增幅明显，而W-FD 算法依旧处于较低值。同时W-FD 算法下的平均链路调度间隔总体上也小于另外两者，这表明在分组到达不对称的多节点环境下，W-FD 具有更好的节点接入公平性。此外W-FD 的网络吞吐量和时延性能会随着节点数的增加而逐渐接近FD-TDMA 和ContraFlow。

实验表明，在所有节点拥有相同分组到达率的较少节点数的分布式网络中，随着到达率的增加，WFD 与FD-TDMA、ContraFlow 相比，虽然吞吐量和时延性能逊色于另外两者，但是能够体现出较好的节点接入公平性，而且降低了网络中的最大时延，改进时延尾部特性。另外在信息分组到达不对称的多节点网络中，随着节点数的增加，一定区域内网络中节点对数也随之增加，导致通信状况愈加复杂。在这种条件下，和FD-TDMA、ContraFlow 相比，W-FD 的吞吐量和时延能够得到有效保证，同时节点接入公平性更加得到突出。

6 结束语

为了实现分布式全双工链路在提高吞吐量和降低时延的同时保证节点接入的最大公平性，提出了一种综合考虑网络吞吐量、时延、节点公平性和调度间隔的分布式全双工链路调度算法W-FD，先对节点的调度权重进行了定义，再依据调度权重对链路进行调度。实验结果表明，W-FD 算法相比传统半双工链路调度在改善吞吐量和时延性能的同时具有较好的节点接入公平性，且W-FD在多节点环境下相比其他全双工链路调度算法在节点接入公平性方面更具备优势。

本文算法仅针对在非动态WLAN 结构下节点的接入，未曾考虑节点移动导致的链路中断等问题；此外，本文算法只对邻域内链路调度的过程进行了优化，在考虑整体数据传输最优路径的情况下还有更深的研究空间。