基于PID控制器的无线局域网帧聚合算法研究

徐健锐
摘 要: 针对高速IEEE 802.11无线局域网(WLAN)中的统计延迟保证问题,提出一种新型的比例?积分?微分(PID)控制器帧聚合算法。通过构建有效容量模型,该聚合算法不需要考虑信道的任何信息,只利用平均的队列级别度量就可以实现QoS统计延迟保障,在接入点实施提出的PID控制器,以此决定分配给每个链接的时间宽限值。模拟结果表明,提出的基于PID的聚合算法要比具有最大聚合尺寸的最早到期优先服务算法和基于截止期限的聚合算法更胜一筹,改善了信道的利用率和无线站点的最大数量。
关键词: IEEE 802.11; 无线局域网; 帧聚合; PID控制器
中图分类号: TN98?34 文献标识码: A 文章编号: 1004?373X(2017)21?0015?04
Research on PID controller based frame aggregation algorithm
for wireless local area network
XU Jianrui1, 2
(1. School of Computer Science and Communication Engineering, Jiangsu University, Zhenjiang 212013, China;
2. Zhenjiang Branch, Jiangsu Union Technical Institute, Zhenjiang 212016, China)
Abstract: A novel frame aggregation algorithm based on proportional integral derivative (PID) controller is proposed for the statistical delay guaranteeing in high?speed IEEE 802.11 wireless local area network (WLAN). By constructing the effective capacity model, the aggregation algorithm doesn′t need to consider any information of the channel, and uses the average queue level measurement to realize the QoS statistics delay guaranteeing. The proposed PID controller is used for the access point to determine the time limit value of each link, which is allocated by the frame aggregation algorithm. The simulation results show that the aggregation algorithm based on PID is better than the earliest deadline priority service algorithm based on maximum aggregation size and the aggregation algorithm based on deadline, and can improve the utilization rate of the channel and increase the maximum quantity of wireless sites.
Keywords: IEEE 802.11; wireless local area network; frame aggregation; PID controller
0 引 言
随着网络播放应用程序的日益普及,比如优酷和网络直播電视,高质量的视频交付对服务提供商、设备和网络供应商而言,变得越来越重要[1?2]。此外,预计到2019年, 由于智能手机的快速发展,消费视频流量将构成所有互联网消费流量[3]的80%。因此大多数视频流量最终将通过无线链接进行交付,特别是通过WiFi网络,比如无线局域网(WLAN)行业已经通过引入IEEE 802.11n以及最近的IEEE 802.11ac标准来应对这种需求[4?5]。然而,由于争用开销和发送冗长报头的速度太慢,多输入多输出可用的高数据率并没有很好地利用。
根据IEEE 802.11标准的规定,有两种类型的聚合,即聚合介质访问控制服务数据单元(A?MSDU)和聚合介质访问控制协议数据单元(A?MPDU)。为了获得最佳性能,在设置聚合尺寸的同时,应该考虑通道的条件。例如,如果码率低,那么大的传输机会(TXOP),即大的聚合尺寸则会占用有限的无线资源[6?7]。同样,在高数据率下传输小数据包将不能充分地利用多输入多输出链接。
本文运用有效容量的理论在波动的通道中设置合适的TXOP。本文提出一种建立在有效容量基础上的帧聚合算法,它能在高速的无线局域网中提供统计的延迟保证。本文提出的聚合方案并没有使用物理层或者信道状态信息,但它能够在复杂信道中找到一个适宜的聚合尺寸,提出基于有效容量的方法仅仅依赖于队列级别指标。此聚合算法在增强分布式信道访问(EDCA)上面实现,受到所有WiFi设备的支持。另外,它在发射机端即可完全实现,如在下行流量运用接入点(AP),无需对IEEE 802.11 MAC进行任何更改。相比最早到期优先(EDF)的算法和基于截止期限的聚合算法,本文提出的聚合方案要更胜一筹,EDF算法需要在最大数量的无线站点(STA)和信道效率方面调度最大的聚合尺寸。
1 模型构建
设一个无线链路的固定随机服务速率表示为[rt,]链接的信源率为[μ],利用偏差理论和切诺夫界限,列队和服务延迟的分布可以近似表示为[8?9]:
[PrD(t)≥Dmax≈γ(μ)e-θ(μ)Dmax] (1)
式中:[γ(μ)]表示链接的利用率;[θ(μ)]表示链接的服务质量指数;[Dmax]表示一个给定的统计延迟界限;[ε]为初始设置的概率值;超时概率表示为[PrD(t)≥Dmax]。统计的QoS保证[γ(μ),θ(μ)]以[Dmax,ε]的形式表现。
期望的QoS指数表示为[θ],则链路的有效容量可以表示为:
[EC(θ,μ)=Γ(θ)=-limt→∞μθtlogEe-oμC(t)] (2)
式中[C(t)]表示累积的随机信道服务分布。QoS指数决定了统计延迟。信源率[μ]要求的有效容量可表示为:
[θ=Γ-1(μ)] (3)
如果式(1)满足等式,可以运用以下近似值来获取[θ]:
[θ=γμγμS+Q] (4)
式中:[S]表示抽样传送的平均剩余服务时间;[Q]表示平均的队列长度。
求解式(1)中的[θ,]要求超时概率少于或者等于[ε]的目标值,即[PrD(t)≥Dmax≤ε]。得到如下条件:
[θ≥-log(ε/γ)Dmax] (5)
可以通過延迟约束和目标超时概率的形式[Dmax,ε]来表示给定的统计QoS要求。因此,对于给定的统计QoS要求和通信量抵达率[μ]而言,以下条件必须得到满足:
[γμγμS+Q+log(εγ)Dmax≥0] (6)
可见所有参数,包括非空链路队列[γ]的概率、平均队列长度[Q]以及数据包平均的剩余服务时间[S]都可以很容易并且准确地在接入点进行估算。
2 提出的PID控制帧聚合算法
假设一个独立的802.11n基本服务集(BSS)具备许多无线站点和一个将通信量转发到无线站点的接入点[10?11]。每个帧到达每个无线站点都需要在接入点排队,以聚合的形式发送出去,根据本文提出的聚合方案,其大小由接入点的信标决定。
假设某个下行链路[l][l=1,2,…,L],规定的QoS必要条件为[Dl,εl]。在每个信标间隔BI期间,该链路指定的时间宽限为[Tl]。本文的目标是让接入点给下行链路安排一个给定的数量[L,]资源使用率达到最小,即在式(6)约束限制下,满足QoS要求的总的时间宽限值,有效地将系统容量最大化:
[minl=1LTl] (7)
s.t. [γl(Tl)μlγlμlSt(Tl)+Qt(Tl)+logεlγl(Tl)Dt≥0,]
[?l=1,2,…,L ] (8)
[l=1LTl≤BI] (9)
优化问题还是具有非凸性。因此,本文通过设计PID控制器,使用启发式的方法解决式(7)中存在的优化问题。可以根据以下公式为每个链路独立解决:
[minTl] (10)
[γl(Tl)μlγlμlSt(Tl)+Ql(Tl)+logεlγl(μl)Dt≥0] (11)
由此得出结论,记录[β-0]的误差对于构建基于PID控制器而言是个合适的选择。
[βl(t)=γl(Tl)μlγlμlSt(Tl)+Ql(Tl)+logεlγl(μl)Dt] (12)
PID控制器在一个给定的链路中的示意图如图1所示。接入点经常控制[βl,]而且在每个信标间隔的最后时刻,它都可以计算出误差值,[el=βl-0]适用于所有链路。然后为下一个信标间隔更新每个链路的时间宽限,根据式(13),应用PID控制法则,分别将适当的增益[kP,][kI]和[kD]的累积总和应用于误差中。
[Τl(t+1)=Τl(t)-kPel+kIu=t-Ttel(u)+kDel(t)-el(t-1)BI] (13)
3 仿真结果与分析
将提出的基于PID的聚合算法的性能和另外两种算法进行比较,即具有最大聚合的最早到期优先(EDF)算法[10]和参考文献[6]中提出的基于截止期限的聚合算法。将两种算法分别简称为“最早到期优先”和“截止期限”。在ns?3模拟环境中,假设有一个独立的802.11n基本服务单元,包含1个接入点和10个无线站点,在下行方向从接入点接收所有的通信量。本文方案完全是在接入点一端实施,而且它没有修改802.11介质访问控制层的任何功能。
在评估本文提出的PID聚合算法时,分析了通道利用率、端到端的平均延迟时间和超时概率。表1列出了主要仿真参数。
当无线站点的数量从1~10变化,目标超时概率为1%时,图2~图4对本文提出的PID聚合算法(简称为PID控制)和最早到期优先算法以及截止期限算法进行了比较。图2给出了信道利用率,而且体现了本文提出的PID聚合算法性能最佳。特别是当存在4个无线站点时,PID能够满足所需的超时概率,同时保持信道利用率接近50%,而最早到期优先算法和截止期限算法利用的信道时间更多,分别为80%和75%。有8个无线站点时,PID达到的最高利用率为98%,而最早到期优先算法和截止期限算法在7个无线站点时,几乎分别达到100%和95%。截止期限算法的利用率低是由于它在接入点建立了大型的队列,从而导致数据包丢包。
如图3所示,提出的PID控制算法与最早到期优先算法和截止期限算法相比,服务的无线站点更多,同时可以满足统计延迟保证[5 s,1%]。特别是当[ε]的目标值为1%时,截止期限算法具备最低容量仅支持5个无线站点,而最早到期优先算法可以多支持一个无线站点。然而,PID可以支持多达8个无线站点,比最早到期优先算法能提供大约30%更高的容量。这是由于信道利用率更好,正如前面图2所示。
此外,当无线站点的数量从1~10变化,目标超时概率为1%时,每种聚合算法的平均延迟如图4所示。基于截止期限的聚合算法在无线站点达到6个时,保持着平均延迟略低于5 s的延迟界限。然而,在此之后平均延迟很快就会变大。最早到期优先算法在无线站点的数量少时,能提供很小的延迟,这表明最早到期优先算法过度供应了数据包,这也解释了它比截止期限算法的信道效率略低的原因。然而,PID的平均延迟保持在最早到期优先算法和截止期限算法之间,但仍远远低于目标延迟界限,这是可以接受的。
接下來,根据不同的QoS需求[D,ε]评估如何实施提出的PID聚合算法。图5为延迟界限对每个无线站点的信道利用率的影响。由于延迟界限的放松,通过给每个无线站点分配较小的时间宽限,本文的PID聚合器可以更有效地利用信道。例如,当只有一个无线站点,延迟界限在1~20 s之间变化时,每个无线站点的时间宽限从15.38 ms降低到11.7 ms,降低了接近25%,如果存在许多无线站点时,这是一个重要的改进。例如,当只有6个无线站点,延迟界限在1~20 s之间变化时,信道利用率可以降低11%。
4 结 论
本文提出一种新型的帧聚合算法,为高数据率的无线局域网络提供了统计延迟保障。本文的聚合算法不需要考虑信道的任何信息,因为它只利用平均的队列级别度量,结合有效容量的概念实现统计延迟保障。本文的方法是基于在接入点实施的PID控制器,以此决定分配给每个链接的时间宽限值。模拟结果表明,本文提出的基于PID的聚合算法要比具有最大聚合尺寸的最早到期优先服务算法和基于截止期限的聚合算法更胜一筹。
参考文献
[1] LIU J, YAO M, QIU Z. Enhanced two?level frame aggregation with optimized aggregation level for IEEE 802.11n WLANs [J]. IEEE communications letters, 2015, 19(12): 2254?2257.
[2] NOMA A M, OTHMAN M, LUN K Y, et al. Two?level frames aggregation with enhanced A?MSDU for IEEE 802.11n WLANs [J]. Wireless personal communications, 2015, 82(3): 1601?1614.
[3] HONG K, KIM J P, KIM M S, et al. Channel measurement?based access point selection in IEEE 802.11 WLANs [J]. Pervasive & mobile computing, 2016, 30(C): 58?70.
[4] BELLALTA B. IEEE 802.11ax: high?efficiency WLANS [J]. IEEE wireless communications, 2015, 23(1): 38?46.
[5] SARRET M G, ASHTA J S, MOGENSEN P, et al. A multi?QoS aggregation mechanism for improved fairness in WLAN [C]// Proceedings of 2013 the 78th IEEE Vehicular Technology Conference. Las Vegas: IEEE, 2013: 1?5.
[6] RAMASWAMY V, SIVARASU A, SRIDHARAN B, et al. A bi?scheduler algorithm for frame aggregation in IEEE 802.11n [J]. International journal of wireless & mobile networks, 2014, 5(6): 91?99.
[7] 邵新明.IEEE 802.11n帧聚合机制的研究[D].天津:天津大学,2012.
[8] WU D, NEGI R. Effective capacity: a wireless link model for support of quality of service [J]. IEEE transactions on wireless communications, 2003, 2(4): 630?643.
[9] FERNG H W, LEONOVICH A. Periods scheduling under the HCCA mode of IEEE 802.11e [J]. IEEE transactions on wireless communications, 2014, 13(12): 7037?7049.
[10] LIU W J, FENG K T, TSENG P H. Optimality of frame aggregation?based power?saving scheduling algorithm for broadband wireless networks [J]. IEEE transactions on wireless communications, 2014, 13(2): 577?591.
[11] DAVY A, MESKILL B, DOMINGO?PASCUAL J. An empirical study of effective capacity throughputs in 802.11 wireless networks [C]// Proceedings of 2012 IEEE Global Communications Conference. [S.l.]: IEEE, 2012: 1770?1775.