在无线通信领域中存在多种典型分布式密集部署网络场景,例如在紧急情况和灾害场景等场合得到广泛应用的Ad Hoc网络,以及下一代Wi-Fi、物联网(internet of things, IoTs)、mesh网络等场景,大量设备密集部署导致数据传输产生冲突。在这些场景中,存在如语音视频、游戏、虚拟现实技术(virtual reality, VR)等具有严格时延需求的业务,这些业务对于多优先级数据处理产生了更高要求,多个节点的业务传输过程具有不同的服务质量需求,例如警告信息需要尽快可靠传输、其他业务不需要立即传输但是具有不同的优先级需求,这些业务只有延迟满足一定条件时才认为传输成功,需要网络协议有效地为不同类型业务提供差异化服务。目前MAC协议中CSMA/CA机制由于其灵活、无中心节点的特性得到广泛应用,但随着网络负载的加重,由于随机竞争产生的冲突使得网络性能下降,低时延业务需求无法得到满足。为了支持不同业务QoS需求,IEEE 802.11ax协议采用增强型分布式信道访问的优先级机制(enhanced distributed channel access,EDCA),通过为不同类型的业务配置相应竞争窗口实现优先级区分,但在密集部署场景中时延敏感业务盲目使用更小的退避窗口会增加碰撞概率,使得延迟时间和信道丢包率增加,低时延业务性能反而下降。
在现有的研究中,支持分组优先级的考虑是有限的。文献[1]通过数学分析使用更合理的CW窗口改进EDCA机制实现差异化控制,但这些机制只适用于流量负载较小的场景,对于节点更密集的场景,更高的冲突概率使得对应机制性能下降,难以保障对应业务需求。
以上问题的一个重要原因是无序竞争导致的冲突,因此一些文献提出了通过提前对信道资源预约以减少无序竞争的分布式带内信道预约MAC方案[2-3]。目前基于信道预约机制的协议多数单纯将业务分为2类,并对其中低时延业务进行预约:文献[4]提出了针对时延敏感业务的预约机制,并及时释放未利用的信道资源以提高利用率;文献[5]提出了一种多信道预约机制,根据控制信令携带的业务类型决定数据信道传输的先后顺序。此类预约机制保障了高优先级业务性能,但将信道资源分割成了多个小资源块,容易使得传输时间碎片化导致资源浪费,并且同属高优先级的业务类型也有不同的服务质量需求,但在机制上没有区分。部分信道预约协议针对多种业务分别进行差异化预约,文献[6]采用一种确定性半退避预约机制,即在成功获得信道传输机会后由AP为其指定采用的无冲突固定退避值,通过为不同的业务类型设置不同范围的固定退避值以实现优先级,能够实现为不同优先级业务差异服务,但每种业务的固定退避值仍采用EDCA的参数直接指定,不能根据实际场景需求进行调整,通过退避值预约的方式无法保证时延满足需求。
因此现有研究存在的问题有:①多数信道预约的文献没有对被预约的业务进行差异化保障,无法满足不同业务的差异化服务质量需求。②少数文献对不同种类业务区分优先级预约,但这些机制存在缺点,差异化参数直接根据优先级指定,没有根据服务质量需求和网络状况细化每一种业务预约参数。
针对以上问题,本文提出了一种差异化业务保障的自适应信道预约多址接入协议。协议核心思想是针对每种业务的容忍时延需求,通过建立的差异化预约参数与平均预约偏移时长关系数学模型,提出自适应算法,精细计算满足时延需求的每种业务预约参数。
1 系统模型考虑一个无中心节点网络, 所有节点通过本文提出的基于CSMA/CA扩展的信道预约机制接入信道, 使用相同的信道。协议主要针对的场景是节点密集部署的高负载网络, 节点间能够通过载波侦听感知到其他节点的传输行为, 每种业务具有不同的服务质量需求。
假设网络中共存在ktotal种业务类型, 其中klow种业务类型具有严格的时延需求, 此类业务较少并且只有在一定时间内传输到对端才认为成功传输。
首先为每种业务根据重要程度评估对应权重系数αi, 权重系数越大业务重要程度越高。本文通过业务时延效用对时延敏感业务的时延需求进行定量刻画, 每种业务存在下界容忍时延Limin和上界容忍时延Limax, 当业务i从产生到传输至对端所需时延Tdelay小于Limin时, 认为本次传输达到了最满意的服务质量需求; 当该时延大于Limin但小于Limax时, 认为本次传输没有达到最满意的时延需求但仍然有效; 当该时延大于Limax时认为本次传输过程无效。
每种业务时延与效用关系根据对应应用场景进行评估, 业务i对应的传输效用通过Ui表示, 已有文献提出Z型效用曲线[7], 即时延低于下界容忍时延时效用为1, 高于上界容忍时延时效用为0。该类型效用曲线能够准确体现实时业务需求, 即超过一定时间后相应信息失效(对应效用为0), 低于一定时间时由于时间较短不会感知到区别, 即达到最满意的传输需求(对应效用为1), 在以上2个容忍时延之间随着传输时延增加效用降低。因此本文采用该类型效用曲线, 滚降函数有多种具体形式, 本文采用平方滚降函数, 即业务传输效用根据(1)式计算
(1) |
本文提出的DSGARM协议采用改进的预约机制, 其中有严格时延需求的时延敏感业务采用预约方式, 对于时延没有严格需求的普通业务通过CSMA机制传输。
图 2展示了信道预约机制的基本流程: 对于预约源节点, 在获得信道传输机会后, 如果本次传输结束时队列中仍存在待传输数据包则发起预约, 确定预约时间段τ(t1, t2)后, 根据预约时段开始时间和持续时间组预约指示信息协议数据单元(reservation instruction MAC protocol data unit, RSV MPDU)并插入当前传输的数据帧中。对于邻居节点, 接收到预约帧后记录其中预约时段, 并在对应时间保持静默。为了克服隐藏终端, 对于预约目的节点, 接收到预约帧时需在ACK中插入该RSV MPDU进行转发, 使得预约源节点的隐藏终端能够接收到预约信息。
图 3展示了本文提出的预约机制中预约时段排列方式, 信道资源周期性划分为预约时段和随机竞争时段, 前者用于时延敏感业务通过预约机制传输, 后者用于随机竞争。预约周期由协议指定,全网统一, 根据预约帧中的同步信息对每个周期开始时间进行同步。定义预约资源所占比例为εRSV, 该比例通过网络中预约资源对应业务量决策调整, 并通过预约资源最大占比εmax进行限制, 即最多允许比例为εmax的信道资源用于预约, 以防止信道资源被高优先级业务完全占据。节点预约帧中携带下个预约周期开始时间, 网络中所有节点通过该信息同步每个预约周期开始时间。
传统的预约时段随机选取方式容易产生碎片化问题, 该问题指的是相邻2个预约时间段存在间隔但间隔较小, 导致这段时间内无法通过随机接入完成一次基本传输, 造成对应时间信道资源浪费。因此将预约时段连续排列从而减少预约时段对随机竞争时段传输的碎片化影响。
根据εRSV确定预约时段总时长, 每次使用的预约持续时长可根据队列状况调整。每个节点根据2.3节算法计算业务类型对应的预约窗口大小Nk, 即从未来未被其他节点预约的Nk个预约时段中随机选取一个时段。如果该数据包已在队列等待较长时间, 可根据最大容忍时延需求临时使用更短预约偏移时间, 但应保持在统计上平均选取的偏移时间与决策的预约窗口相对应。对于预约传输机会中未被预约的时间段, 在对应时间到达以后可以通过CSMA接入信道。如果完成预约传输后存在剩余信道资源, 则可以发送预约取消帧释放对应预约资源。
为了缓解预约导致的碎片化问题, 对预约时段采用柔性处理, 引入柔性预约时长Tflex, 该时间根据基本传输时长确定,远小于一次基本传输时间。节点获得信道传输机会并发起传输时, 如果本次传输需跨入其他节点预约时段, 并且占据的预约时间小于Tflex, 则允许占据该部分时间进行传输。节点在广播预约信息时, 额外通过时段指示ID预约时段信息, 预约时段对应节点发起传输时, 在帧中指示本次传输机会在预约周期中对应的预约时段序号, 邻居节点根据已完成的预约传输指示ID判断本节点预约时段是否到达。当邻居节点由于柔性预约时间等原因调整预约传输时段开始和结束时间时, 通过该机制灵活确定对应预约时间段开始和结束时间, 其中Tflex时长较短, 因此不会对预约偏移时间产生较大影响。
2.2 预约参数决策协议流程预约参数决策过程根据每种业务对应预约权重αi, 通过2.3节算法根据业务容忍时延需求和邻居节点业务类型, 代入模型计算并修正满足时延需求的权重系数, 并根据该权重系数计算每种业务使用的预约窗口大小。
节点发起预约时预约帧中携带业务类型和本次决策预约权重信息, 所有节点维护活跃邻居节点权重列表, 当单个邻居节点传输多种业务类型时, 独立记录每种业务类型信息。当超过Tupd没有收到来自某邻居对应业务类型预约信息时, 将此邻居从活跃邻居列表中删除。当活跃邻居节点列表变化数量超过Cth时, 重新根据差异化预约窗口算法决策并更新各个业务类型采用的预约窗口大小。Tupd决定了活跃邻居节点列表更新的间隔, 在设置时需大于节点竞争信道平均所需时间, 以避免因冲突等原因导致活跃邻居节点被删除。Cth与算法决策频率呈负相关, 应用时根据设备计算能力确定满足算法耗时的阈值。
2.3 差异化预约参数算法流程差异化预约参数算法基本思想是: 调整不同业务使用的预约窗口大小,使之与对应业务权重系数的倒数α′呈正比, 并保证每种业务预约偏移时间满足容忍时延需求, 决策满足以上条件的每种业务权重系数以及对应使用的预约窗口大小, 并使得总预约比例合适。其中预约偏移时间和总预约比例根据邻居节点预约窗口大小通过差异化预约参数模型计算, 总预约传输比例指的是预约时段中通过算法决策的预约传输占用比例, 决策时不会占用全部预约时段, 而是为突发业务或新入网没有预约机会的节点保留部分空闲时段。算法整体分为预约窗口自适应调整算法和预约权重系数修正算法两部分。
预约窗口自适应调整算法通过给定的每种业务预约权重以及维护的活跃邻居预约信息列表, 计算每种业务类型对应预约窗口大小Ni=μ/αi, 其中μ为预约窗口常数, 通过调整μ使得对应预约参数配置时计算的预约传输比例为PRSVsuit。该算法流程为: 设置初始搜索迭代步长, 对于每一步搜索中对应的节点预约窗口大小, 通过差异化预约参数模型计算对应参数下总预约传输比例, 由于预约窗口常数与总预约传输比例呈负相关, 根据该特性在每个对应迭代步长搜索过程调整窗口常数并在当前迭代步长下搜索到目标解。
预约权重计算算法根据当前网络状况计算能够满足每种业务时延需求的预约权重系数。由于当节点业务量较大或者突发业务占比较多时、可能出现数据包在队列中等待时延较长的情况, 因此使用更严格的限制时延Lic, min=λLimin作为预约权重系数计算标准。该算法流程如图 4所示。
首先将业务优先级评估结果作为初始权重系数, 通过预约窗口选择算法计算每种业务对应预约窗口大小以及预约偏移时长, 如果该时延满足限制条件, 则采用该权重系数对应决策结果; 否则滑动该业务对应预约窗口并计算对应权重, 直到所有业务均满足容忍时延需求。当通过算法决策需要为某类业务调整预约权重系数时, 表示此时网络状况较为繁重, 此类业务将固定使用满足限制时延的最大预约偏移时间。
3 差异化预约参数模型 3.1 模型基本思想假设给定节点k使用的预约窗口大小为Nk, 网络中使用预约机制节点数为m, 考虑饱和业务场景, 即每当节点预约传输机会到达后,队列中存在待传输业务并发起新的预约传输。该模型用于计算给定每个节点不同的预约窗口大小时, 该节点选择预约偏移时段的概率以及预约时段占用比例。
由于节点k可以在未来Nk+m-1个未被预约时间段中选取空闲时段, 并且可能有m-1个时段已被其他节点预约, 因此节点可能选择的预约时段范围是未来Nk+m-1个时段。定义节点发起预约时可以选择的时段范围为后向预约窗口, 部分时段能通过一次预约对后向预约窗口中时段进行保留,将这些时段的集合定义为前向预约窗口。因此前向预约窗口与后向预约窗口长度分别为Nk+m-2和Nk+m-1。前向预约窗口第i个时段定义为Tlefti, 后向预约窗口第j个时段定义为Trightj, 统一表示将前向预约窗口与后向预约窗口按时间顺序排列为总预约窗口, 即后向预约窗口中的第j个时段也表示为Trightj=TallNk+m-2+j。
根据预约窗口类型示意图(见图 5), 每次选取预约时段时, 后向预约窗口中越靠后的时段可以被前向预约窗口其他节点预约的概率更小。模型计算的基本思想为: 通过将时间轴从前向预约窗口开始推进到结束, 依次计算前向预约窗口各个时段选择对应预约时段的概率, 由此得到后向预约窗口中各个时段已被预约的概率, 进而计算选择后向预约窗口每个时段作为预约时段的概率。
3.2 模型基本流程由于预约时段选择具有无记忆性, 可认为在前向预约窗口中, 每个时段曾被本节点预约的概率相等, 近似认为在前向预约窗口初始时刻节点k拥有的预约时段处于前向预约窗口中每个时段的概率为1/(Nk+m-1)。
定义当时间轴推进到前向预约窗口第t个时段时, 时段Talli已被节点k预约的概率为Rtk, i, 将此时第i个时段未被任何节点预约的概率表示为Sti, 则有
(2) |
随着时间轴从前向预约窗口开始到结束, 当时间轴推进到前向预约窗口第t个时段时, 该时段有概率Rtk, t被节点k预约, 假设此时该节点有Ptk(Tallt, Tallj)的概率选择时段Tallj作为预约时段, 该时段位于时段Tallt的后向预约窗口中, 则时段Tallj处于被预约状态概率增加, 增加的概率为时段Tallt处于被预约状态概率Rtk, t乘以选择时段Tallj作为预约状态概率。因此有以下累加计算公式成立
(3) |
式中:j表示选择的目的预约时段;k表示对应节点, 有j∈[i+1, i+Nk+m-1], k∈[1, m], 每一步累加公式对于所有目的时段和节点均进行计算。
以下求解对于给定节点k, 在当前时段为Talls时, 从该时段对应的后向预约窗口中选取各个时段作为预约时段的概率。由于节点在后向预约窗口各个时段中选择的总概率和为1, 即有
(4) |
根据选择后向预约窗口中各个时段概率与对应时段空闲概率呈正比, 以及(4)式可得出
(5) |
假设所有节点最大的预约窗口大小为Nmax, 因此可以对前向预约窗口中Nmax+m-2个时段, 依次根据(3)式和(5)式通过每个节点对应的概率转移公式, 求解出当时间轴推进到当前传输时段时, 后向预约窗口中各个时段被预约占用的概率, 将该概率集合代入(5)式可求解出选择后向预约窗口各个时段的概率集合ΦRSV={PRSV1, …, PRSVNk+m-1}。
用b(t)表示当前时段为t时给定节点k剩余预约时段数的随机过程。当剩余时段数为1时, 节点的预约传输过程将会在下一时段到达, 此时发起传输并选择新预约时段。假设稳态时剩余预约时段数为i的概率是bi, 因此根据图 6对应状态转移图,稳态时对于预约窗口大小为Nk的节点得到以下方程
(6) |
通过归一化条件
(7) |
由于b(t)=1对应状态为预约传输阶段, 因此b1为单个节点处于预约传输状态概率, 对应的平均预约偏移时段数期望为
(8) |
对于平均预约持续时长为Tintmax, 预约资源占据信道总比例为εRSV时, 平均预约偏移时长为Toffset=ERSVTintmax/εRSV。
以上各式给出了给定预约窗口为Nk时每个节点预约时段占比, 对于节点k代入以上各式求解得到该节点的预约传输比例为PinRSVk, 由此计算得到网络总预约传输占比为
对于时间复杂度。假设节点数为m, 预约窗口大小为N, 执行单次模型计算的时间复杂度为O(N2m)。对于算法的搜索过程, 给定迭代步长为Δ时, 针对预约权重计算算法与预约窗口自适应调整算法,在执行遍历搜索的过程中最坏情况的时间复杂度均为O(N/Δ), 即线性时间复杂度。
对于空间复杂度, 现有信道预约方案均需记录邻居节点预约时间信息。算法额外存储开销为本次预约业务类型信息与决策权重信息, 预约业务类型信息和决策权重信息大小分别为1字节和2字节。模型计算过程中产生的临时变量为常数级, 算法决策过程中记录的变量为每个节点的时延。因此协议对于节点数为m的情况, 空间复杂度为O(m)。
对于空口协议开销。增加的存储开销为本次预约业务类型信息与决策权重信息, 单个预约帧中以上信息所占总字节数为3。对比方案中仍传输预约帧, 因此引入的额外开销为每个预约帧中增加3字节, 该大小与数据帧相比可以忽略。
因此本文提出的协议时间复杂度、空间复杂度以及空口协议开销均较小。
4 仿真结果分析 4.1 评估参数说明本文引入以下参数对网络性能进行评估。定义时延敏感业务加权平均时延效用(weighted average delay utility, WADU), 用符号Uw表示, 对应Uw计算公式定义为
(9) |
定义网络加权有效吞吐量Hw, 该指标通过每种业务的权重以及传输效用对业务吞吐量进行加权处理, 假设业务i对应吞吐量为Hi, 则Hw计算公式为
(10) |
仿真参数配置如表 1所示。假设网络中存在4种业务E0, E1, E2和E3, 比例分别为10%, 20%, 30%, 40%, 其中E0和E1业务具有明确的时延需求, E2和E3业务是普通业务。本文基于一个NS3搭建的仿真平台[8]增加提出的DSGARM预约协议。对比方案SCRP机制[4]是近年最新提出的一种改进带内预约机制, 通过为低时延业务预约保障此类业务性能; 802.11ax协议[9]采用EDCA机制对应的竞争窗口参数配置, 4种业务分别对应VO、VI、BE和BK业务参数。
仿真参数 | 参数值 | 仿真参数 | 参数值 | |
SIFS时长/μs | 40 | 数据包大小/Byte | 1 500 | |
Slot时长/μs | 20 | 聚合度 | 3 | |
传输速率/(Mbit·s-1) | 21 | 仿真时长/s | 100 | |
Phy报头/bit | 128 | Mac报头/bit | 272 | |
L0min/ms | 29 | L0max/ms | 60 | |
L1min/ms | 80 | L1max/ms | 120 | |
α0 | 1.68 | α1 | 1.12 | |
α2 | 0.64 | α3 | 0.56 | |
λ | 0.85 | PRSVsuit | 0.85 |
仿真结果如图 7~10所示。图 7展示了时延敏感业务中E0业务和E1业务的时延, 图 8展示了加权平均时延效用。802.11ax协议在密集场景中时延较大, 因此仿真结果数据中时延性能进行以10为底的对数处理以便于直观展示。当节点数较少、各种业务时延性能均满足时, DSGARM协议为各种业务分配了不同的优先级, 保证了时延敏感业务最低的时延性能。当网络节点数增多、E0业务服务质量逐渐不满足时延需求时, DSGARM协议通过自适应调整参数保障该业务时延需求, 因此该协议加权平均时延效用在密集场景中保持为1;SCRP和802.11ax协议在节点数增加后部分时延敏感业务不满足容忍时延需求、加权平均时延效用逐渐降低, 其中802.11ax协议由于冲突加剧下降更快。
图 9和图 10展示了网络中普通业务的吞吐量性能和加权有效吞吐量性能。由于802.11ax EDCA机制采用激进的退避窗口,因此普通业务冲突概率较大的情况,DSGARM机制在保证普通业务传输机会的同时,由于碎片化时间处理相比SCRP机制有一定提升。对于加权有效吞吐量DSGARM高于另外2种机制在节点更密集时,性能提升更显著。
以上仿真结果说明,本文提出的DSGARM协议能够在密集部署场景下,依然实现较高的吞吐量。针对有特殊时延需求的业务,通过提出的算法能够准确通过自适应参数调整保证此类业务QoS。与对比预约机制SCRP协议和传统的802.11ax协议相比有明显的性能增益,并且相比于SCRP机制能够根据业务需求通过自适应算法更好的满足低时延业务需求,与此同时还能改善普通业务的性能。
5 结论为了保证不同类型业务的服务质量需求,本文提出了一种基于差异化业务保障的信道预约机制,首先建立了数学模型针对不同预约参数下网络性能进行分析,根据建立的模型提出了针对不同业务类型差异化保障算法,能够根据业务容忍时延需求和网络状况自适应调整预约参数,将该算法应用于本文提出的信道预约协议中。仿真结果显示该机制和现有预约机制相比具有优势。近期课题组提出了粒子化接入思想[10]和网络波理论[11],均是保证网络服务质量和有序接入的重要方法。信道预约机制是支撑和实现上述思想和理论的重要方法,因此本文提出的预约协议在后续扩展中将与其结合。
[1] | ABU-KHADRAH A I, ZAKARIA Z, OTHMAN M, et al. Enhance the performance of EDCA protocol by adapting contention window[J]. Wireless Personal Communications, 2017, 96(2): 1945-1971. DOI:10.1007/s11277-017-4277-1 |
[2] | LI B, LI W, VALOIS F, et al. Performance analysis of an efficient MAC protocol with multiple-step distributed in-band channel reservation[J]. IEEE Trans on Vehicular Technology, 2009, 59(1): 368-382. |
[3] | LIU Z, LI B, YANG M, et al. An adaptive channel reservation mac protocol based on forwarding traffic of key nodes[EB/OL]. (2023-05-10)[2023-06-25]. https://arxiv.org/abs/2306.06425 |
[4] | CHENG J, LI B, YANG M, et al. Soft channel reservation towards latency guarantee for the next generation WLAN: IEEE 802.11 be[C]//International Conference on Internet of Things as a Service, Cham, 2021: 450-461 |
[5] | LEE J. An efficient reservation-based MAC protocol for multi-priority traffic in slotted multi-channel distributed cognitive radio networks[J]. IEEE Access, 2020, 8: 185830-185841. DOI:10.1109/ACCESS.2020.3029843 |
[6] | LEI J, TAO J, HUANG J, et al. A differentiated reservation MAC protocol for achieving fairness and efficiency in multi-rate IEEE 802.11 WLANs[J]. IEEE Access, 2019, 7: 12133-12145. DOI:10.1109/ACCESS.2019.2892760 |
[7] | KUMAR A, ABDELHADI A, CLANCY C. A delay-optimal packet scheduler for M2M uplink[C]//2016 IEEE Military Communications Conference, 2016: 295-300 |
[8] | QU Q, LI B, YANG M, et al. Survey and performance evaluation of the upcoming next generation WLANs standard-IEEE 802.11 ax[J]. Mobile Networks and Applications, 2019, 24(5): 1461-1474. DOI:10.1007/s11036-019-01277-9 |
[9] | 802.11 Working Group of the IEEE LAN/MAN Standards Committee. IEEE standard for information technology-telecommunications and information exchange between systems local and metropolitan area networks-specific requirements part 11: wireless lan medium access control(MAC) and physical layer(PHY) specifications amendment 1: enhancements for high efficiency WLAN[S]. IEEE Std 802.11ax2021(Amendment to IEEE Std 802.11), 2021 |
[10] | LI B, SUN K, YAN Z, et al. Idea and theory of particle access[EB/OL]. (2023-05-15)[2023-06-25]. https://arxiv.org/abs/2203.1519 |
[11] | LI B, YANG M, YAN Z. Theory of network wave[EB/OL]. (2023-04-21)[2023-03-01]. https://arxiv.org/abs/2203.05241 |