下一代WLAN高能效目標喚醒時間調(diào)度策略

陳清華，梁國喜

1(浙江工業(yè)大學 計算機科學與技術(shù)學院， 杭州 310014)

2(溫州職業(yè)技術(shù)學院 信息技術(shù)系， 浙江 溫州 325035)

E-mail ：47449970@qq.com

1 引 言

基于IEEE 802.11[1]的WLAN(Wireless Local Area Network，無線局域網(wǎng))由于其移動性、部署靈活性強、維護成本低、可伸縮性強等優(yōu)點，應(yīng)用廣泛.隨著網(wǎng)絡(luò)訪問要求的提高和需求的增加，像眾多公共場所都部署了大量的AP(Access Point，接入點)以方便用戶不間斷地接入網(wǎng)絡(luò).面對有限的免授權(quán)頻譜資源，高密度WLAN由于其信道接入的競爭機制和干擾，網(wǎng)絡(luò)性能急劇下降.

為此，IEEE協(xié)會于2013年成立了新任務(wù)組并啟動對下一代高效WLAN協(xié)議ax[3]的研究，擬引入多項新技術(shù)，如基于正交頻分復(fù)用多址的多用戶傳輸機制、空間復(fù)用等[3，4]，來提升網(wǎng)絡(luò)性能，并計劃于2019年正式發(fā)布.

由于能源的稀缺性，在下一代WLAN中，節(jié)能機制也是其重點關(guān)注和改進的問題之一.WLAN中的AP往往由電源供電、位置基本固定，較少研究[5]涉及AP節(jié)能，更多的是對無線移動終端的節(jié)能研究[6].一般地，終端站點可關(guān)閉無線收發(fā)器進入休眠狀態(tài)以降低能耗，處于休眠狀態(tài)時間越長、用來傳輸?shù)臅r間越短，設(shè)備則越節(jié)能.基于此，文獻[7]通過機器學習的方法來確定站點是否進入休眠.文獻[8]提出通過調(diào)整休眠站點的偵聽間隔來提高吞吐率；文獻[9]中依據(jù)緩沖區(qū)限制等信息動態(tài)設(shè)定偵聽間隔，使得站點僅在信道條件較好時醒來傳輸數(shù)據(jù)；文獻[10]提出經(jīng)由第一個醒來時間來控制每個信標幀時槽(Beacon Slot)內(nèi)競爭站點數(shù)來提高吞吐率.此外，Si等人[11]提出通過控制流量指示圖僅讓在有下行數(shù)據(jù)的部分站點醒來，減少競爭以提升整體吞吐率.

為節(jié)能，下一代WLAN創(chuàng)新性地提出廣播TWT節(jié)能機制，它以TBTT(Target Beacon Transmission Time，目標信標幀傳輸時間)調(diào)度為前導，通過控制站點傳輸時間來廣播TWT 服務(wù)時間提高性能.Maddalena等[13]指出結(jié)合多用戶傳輸?shù)腡WT機制具有更高的吞吐率和更低的能耗.然而，在下一代WLAN協(xié)議草案中，TBTT調(diào)度機制轉(zhuǎn)由無線網(wǎng)絡(luò)接口硬件廠商實現(xiàn).不難驗證，同時醒來的站點數(shù)不均衡必然引起部分信標幀時槽內(nèi)的過度競爭和部分時槽內(nèi)的資源浪費，引致吞吐率和能效的下降.然而，目前缺少適用于多用戶傳輸機制的廣播TWT中的TBTT調(diào)度策略.文獻[14]雖對有限TWT服務(wù)期間提出了多用戶數(shù)據(jù)傳輸方案并做了分析，但也未有提及TBTT的調(diào)度方法.本文提出一種基于分組的TBTT調(diào)度方案(Grouping-based TBTT Scheduling Scheme，GTSS)，通過控制同時醒來站點數(shù)，在保障吞吐率的前提下減少競爭，并最終達到提高終端站點能效的目標.主要工作及貢獻有：

1)在盡可能滿足用戶需求的情況下，提出了結(jié)合多用戶傳輸特性的TBTT同時調(diào)度方案，通過對站點偵聽間隔進行分組、編排第一個TBTT時刻和初始索引的飄移，實現(xiàn)了在每個信標幀時槽內(nèi)醒來站點數(shù)的均衡化.

2)提出了分組算法并對方案的最壞、最優(yōu)以及平均情況做了分析，并結(jié)合上行多用戶隨機接入過程對該方案進行了仿真實驗.

3)仿真實驗中，以未采用節(jié)能方案的情況為參考，將GTSS方案、先到先服務(wù)(FCFS)、隨機(RND)方案進行了比較，從上行和下行鏈路分別驗證了本方案在保障整體吞吐率的情況下，具有更高的能效和更小的丟包率.

2 網(wǎng)絡(luò)模型

IEEE 802.11ax草案3.0[4]中廣播TWT工作機制，當存在站點需要休眠時，站點發(fā)送含偵聽間隔參數(shù)的TWT請求幀至AP.AP接收到請求后，發(fā)送包含是否可以進入休眠狀態(tài)、第一個TBTT及其最終偵聽間隔等相關(guān)信息的TWT響應(yīng)幀至請求站點.當請求站點接受該響應(yīng)后，若不存在繼續(xù)保持活躍狀態(tài)的必要條件，則進入休眠直至第一個TBTT時刻到來，并開啟收發(fā)器來接收相應(yīng)的信標幀.站點根據(jù)其中的AP緩存區(qū)狀態(tài)信息以及廣播TWT信息元，可以選擇參與或修改其已有的廣播TWT時間，并在指定的TWT服務(wù)期間醒來傳輸數(shù)據(jù).針對有固定設(shè)施的WLAN，如圖1所示，提出了一種基于分組的TBTT確定方案GTSS.AP是集中控制的匯聚點，用來調(diào)度所有休眠需求站點的TBTT，以實現(xiàn)控制每個信標幀時槽內(nèi)醒來的站點個數(shù).

圖1 應(yīng)用場景

網(wǎng)絡(luò)中包的到達具有隨機性和獨立性，假設(shè)站點間的包到達為一泊松過程.同時，下一代WLAN中可并行使用的26-tone子信道個數(shù)高達37個.相鄰的子信道可合并供一個用戶使用以獲得更高的速率.信道越寬，同等條件下速率越高，接近倍率關(guān)系.因此，提出如下具體假設(shè)：

1)網(wǎng)絡(luò)中存在n個需休眠的站點，其中第i個站點記為si;

3)在每個TWT服務(wù)期間內(nèi)，AP可用的RU(Resource Unit，資源單位)數(shù)為m個，每個資源單位使用相同的傳輸速率r.AP可以將多個連續(xù)資源單位合并成更大的資源單位，并以此獲得相應(yīng)倍數(shù)的數(shù)據(jù)傳輸速率.

GTSS詳細工作流程如下：

1)請求休眠的站點發(fā)送TWT請求幀至AP，其偵聽間隔記為T={ti|i=1，2，…，n}.該偵聽間隔是管理參數(shù)信標幀間隔(Beacon Interval)的整數(shù)倍，為一正整數(shù)；

2)AP調(diào)用GTSS方案確定TBTT值，并通過TWT響應(yīng)幀將醒來時刻返回至各個站點.站點si的第一個TBTT值記為fi(i∈{1，2，…，n})；

3)站點接收到TWT響應(yīng)幀后，進入休眠狀態(tài)，并在指定的TBTT時刻wi=fi+mi×ti(mi是≥0的整數(shù))醒來接收信標幀.對應(yīng)的信標幀中攜帶了TWT服務(wù)期間信息；

4)站點休眠時，發(fā)往站點的數(shù)據(jù)存儲在AP緩沖區(qū)中.當站點醒來時可發(fā)起請求以接收存儲在AP緩沖區(qū)中的數(shù)據(jù)；如若發(fā)生緩沖區(qū)溢出，AP可向占用緩沖區(qū)較大STA提出修改偵聽間隔的請求；對于流量較小的站點，則適當增大偵聽間隔以提高能效.具體如何調(diào)整偵聽間隔不在本文范圍內(nèi).

同時，為分析一個信標幀時槽內(nèi)的競爭程度，本文給出以下評價指標的定義.

定義1.(競爭水平dcl)一個TBTT內(nèi)同時醒來的站點個數(shù).

根據(jù)定義，可以得到以下公式：

(1)

其中，gi(t)定義如下

(2)

其中，dcl(0)=0.

定義2.(競爭抖動dcv)指競爭水平的變化范圍，用最大競爭水平與最小競爭水平之差來表示.

定義3.(鄰近競爭抖動方差dcva)用來描述相鄰信標幀時槽內(nèi)資源需求的變化程度.

(3)

3 基于LI特征的TBTT調(diào)度方法

由上述過程可知：對于任一個站點si，其所有醒來時刻可以用二元組表示.因此，站點si的所有TBTT可表示為一個具有非負整數(shù)且模一致的剩余類[fi]ti={wi|wi≡fimod(ti)}={wi=fi+mi×ti│mi≥0，mi∈Z}.其中，Z表示整數(shù)集合.為簡化，使用[fi]表示[fi]ti.

引理1.對于任意兩個站點si和sj，如果其偵聽間隔互質(zhì)，則si和sj必定在將來某個時間點同時醒來.

證明：根據(jù)中國剩余定理，給定[fi]、[fj]，且ti與tj的最大公約數(shù)為1(互質(zhì))，則一定存在某個TBTT時刻x∈[fi]∩[fj]，且在ti×tj內(nèi)x是唯一解.命題得證.

引理2.對于任意兩個站點si和sj，如果tj是ti的整數(shù)倍，fi≠fj，fi

證明：根據(jù)已知條件，設(shè)tj=γ·ti，其中γ為大于0的整數(shù).由[fj]的定義可以得到[fj]={wj=fj+mj×tj│mj≥0，mj∈Z}={wj=fj+mj·γ·ti│mj≥0，mj∈Z}?[fj]ti.即：[fj]tj?[fj]ti.由fi≠fj得到fj?[fi]ti，且[fj]ti∩[fj]ti=?.因此，[fj]tj∩[fi]ti=?.對于所有的wi∈[fi]和wj∈[fj]有wi≠wj.亦即，si和sj必定不會在將來某個時間點同時醒來.

引理3.對于偵聽間隔不能整除，但有公因子的兩個站點，通過設(shè)定適當?shù)牡谝粋€TBTT，可使得兩個站點在將來某一TBTT同時醒來.(證明略)

引理4.偵聽間隔不能整除但有公因子的兩個站點，通過設(shè)定適當?shù)牡谝粋€TBTT可使得兩個站點必定不會在將來的任一TBTT同時醒來.(證明略)

基于上述引理對偵聽間隔特征和第一個TBTT的影響分析，GTSS方案首先對偵聽間隔值進行分組并將對應(yīng)站點歸入到不同的組別，接著對組內(nèi)具有共同偵聽間隔屬性的站點進行TBTT調(diào)度.最后，通過初始索引的飄移實現(xiàn)組間錯位和醒來站點的均衡化.具體分為以下步驟：

步驟1.(分組)根據(jù)偵聽間隔值的不同性質(zhì)，對站點分組，偵聽間隔具有倍數(shù)關(guān)系的站點進入同一組.算法見3.1.

步驟2.(內(nèi)部分組)對組內(nèi)偵聽間隔具有倍數(shù)關(guān)系的站點，依據(jù)引理2，設(shè)置合理的第一個TBTT值可將站點的TBTT錯開，并達到控制組內(nèi)每個信標幀時槽醒來站點數(shù)量的目標.算法見3.2.

步驟3.(飄移)所有組別的初始索引均從第1個空位開始，勢必引起每個周期內(nèi)第一個TBTT醒來站點數(shù)突發(fā).通過初始索引的隨機飄移實現(xiàn)一定的均衡.算法詳見3.3.

3.1 組間分組算法

算法1中給出的分組過程先按升序排列各偵聽間隔，然后依據(jù)偵聽間隔倍數(shù)關(guān)系將站點歸入相應(yīng)組別.以T={8，18，9，3，3，4，2，6，12，6，9}為例，得到偵聽間隔的子集劃分結(jié)果為：SubT1={2，4，8}，SubT2={3，6，12}和SubT3={9，18}；得到站點子集劃分：SubS1={s1，s6，s7}，SubT2={s4，s5，s8，s9，s10}和SubT3={s2，s3，s11}.

算法1.Inter-Grouping Algorithm

輸入：T={t1，t2，…，tn}

輸出：所有偵聽間隔的分割子集SubT1，SubT2，…，SubTu以及站點分割子集SubS1，SubS1，…，SubSu

1.Td={distinctti|ti∈T}，To=ascending orderedTd，u=0;

2. whileTo≠? do

3.t=the first element inTo;

4. fori= 1：udo

5. iftj|tthen

6.SubT=SubTi;

7. break;

8. end

9. end

10. ifSubT==? then

11.u=u+1;

12. end

13.SubTi=SubT∪{t};

14.To=To-{t};

15. end

16. Split all STAsi∈SintoSubSk，ifti∈SubTk，k=1，2，…，u;

非空集合T分割得到的任意子集具有以下屬性：

1)子集不為空，且任意兩兩子集不相交；

2)任意子集中最大元素為所有元素的公倍數(shù)，稱其為內(nèi)部信標周期(Intra Beacon Cycle)；

3)若子集中存在一個元素為質(zhì)數(shù)，則該元素必定是最小元素，亦即，第一個元素；

4)若有ti，tj∈SubTk?T，如果有j>i，則tj>ti；

5)若有ti，tj∈SubTk?T，如果有tj>ti，則ti|tj.

推論1.滿足上述屬性的子集劃分結(jié)果中，算法1得到的子集個數(shù)最小.(反證法，證明略)

3.2 內(nèi)部分組算法

對分割后的任意子集的TBTT確定過程如算法2所述.以SubTk={2，4，4，4，4，4，4，8，8，8，16}為例，首先最小元素先被分配，由于列表為空，產(chǎn)生新的長度為16的列表，并占據(jù)列表第一個非空單元.同時，站點會在3，5，…，15等時刻醒來，對應(yīng)列表位置被標記為非空.結(jié)果如圖2所示.

圖2 內(nèi)部分組算法結(jié)果示例

算法2.Intra-Grouping Algorithm

輸入：SubTk，SubSk

輸出：對于任意站點si∈SubSk，的第一個TBTTfi

1.LCM=the last element inSubTk;

2.ln=1，list[ln][LCM]=?;

3. fori=1：length(SubTk)

4. Find the first vacant unitfiinlist[ln][LCM]

5. for allwi=fi+mi×ti，wherewi≤LCM

andmi≥0

6. Setlist[ln][wi]=thei-th element inSubSk;

7. iflist[ln][LCM] is full andi≠length(SubTk)then

8. setln=ln+1;

9. Generate a newlist[ln][LCM];

10. end

11. end

推論2.在最大競爭水平與競爭抖動上，內(nèi)部TBTT調(diào)度算法達到了最優(yōu).

3.3 初始索引的隨機飄移過程

圖3以T={3，2，2，10，9，3，2，3，3，6}為實例從整體上描述了分組和組內(nèi)分組的結(jié)果.易得出，dcl_max=5，dcl_min=2，dcv=3，且最大的競爭站點數(shù)總是出現(xiàn)在第一個信標幀時槽內(nèi).根據(jù)引理2、3，通過適當?shù)木幣艂陕犻g隔有倍數(shù)關(guān)系或存在公因子的站點可在任意時刻都不會同時醒來的目標.圖3實例中的站點s2與s4的偵聽間隔具有倍數(shù)關(guān)系，通過初始索引的飄移達到減少最大競爭水平dcl_max的目的.

由于每個組內(nèi)列表的最后一個列表存在有空閑的單元，對非空單元的初始索引的飄移并不會帶來任何有益的效果.

圖3 初始索引飄移前

因此，對每個組內(nèi)的最后一個列表的初始索引進行飄移結(jié)果即可.對初始索引飄移后的一種結(jié)果如圖4所示.

圖4 初始索引飄移后的TBTT編排結(jié)果圖

dcl_max≤?dcl_avg」+u，

(4)

dcl_max≥max{?dcl_avg」-u+1，0}.

(5)

其中，u代表偵聽間隔的分組個數(shù).

4 仿真與分析

下一代WLAN的MAC層下行傳輸采用的集中式調(diào)度，而對于上行訪問，Matlab仿真中使用的是基于多用戶傳輸機制的UORA隨機過程.通過編程模擬了MAC層的隨機訪問過程，使用不同的方案對醒來時間做了調(diào)度.使用的關(guān)鍵參數(shù)如表1所示，其中AP使用的是20MHz的帶寬，子信道大小為26-tone，對應(yīng)采納的速率為11.8Mbps.根據(jù)協(xié)議，其可用的最大數(shù)量為9.同時假設(shè)，信道條件是理想的.

當前，鮮有文獻對結(jié)合多用戶傳輸?shù)膯拘褧r間調(diào)度策略有所提及.因此，仿真主要對比了GTSS與先到先服務(wù)(FCFS)、隨機(RND)方案以及未采用節(jié)能方案在相關(guān)性能指標上的差異.

4.1 信標幀時槽內(nèi)醒來站點個數(shù)分析

首先，對最大醒來站點數(shù)、競爭抖動、鄰近競爭抖動方差等指標進行了分析.當偵聽間隔值服從均值為10、方差為5的正態(tài)分布，結(jié)果如圖5所示.隨站點數(shù)的增加，F(xiàn)CFS方案中最大醒來站點數(shù)等于所有站點數(shù)，而最小醒來站點數(shù)接近于0，其效果最差.由于偏差較大，圖5(a)未顯示FCFS 的結(jié)果.相比RND方法， GTSS最小、最大醒來站點數(shù)間波動小.從5(b)看出，鄰近競爭抖動方差GTSS表現(xiàn)最為平接近于0，其效果最差.由于偏差較大，圖5(a)未顯示FCFS的結(jié)果.相比RND方法， GTSS最小、最大醒來站點數(shù)間波動小.從5(b)看出，鄰近競爭抖動方差GTSS表現(xiàn)最為平穩(wěn).此外，仿真對服從范圍為[2,20]的均勻分布偵聽間隔取值也進行了分析，其比較結(jié)果近似于正態(tài)分布，GTSS優(yōu)勢更為明顯.篇幅有限，結(jié)果圖不再給出.

表1 仿真參數(shù)表

圖5 信標幀時槽內(nèi)站點競爭數(shù)分析(正態(tài)分布)

4.2 性能指標分析

站點在偵聽間隔時間間隔內(nèi)到達的包數(shù)量服從i.i.d.的泊松分布(下行包到達均值為50個/秒，上行為12個/秒)，仿真的結(jié)果如圖6所示.下行數(shù)據(jù)傳輸由AP集中調(diào)度發(fā)送，因此，圖6(a)中沒有休眠的站點數(shù)據(jù)實時收發(fā)，吞吐率最高.而FCFS由于醒來時刻的突發(fā)性，易發(fā)生流量的不均衡和AP緩存的溢出，其吞吐率最差.當網(wǎng)絡(luò)服務(wù)能力鄰近極限時， GTSS的網(wǎng)絡(luò)吞吐率趨近于沒有采用能量節(jié)省的方案，優(yōu)于RND方案，超過FCFS方案40%以上.

能量消耗與處于收發(fā)狀態(tài)的時間長短密切相關(guān).如圖6(b)所示，沒有能量節(jié)省的方案中由于沒有休眠狀態(tài)能效(每消耗1mJ能量傳輸?shù)臄?shù)據(jù)量)最低，F(xiàn)CFS次之.而GTSS相比于RND在能效上的優(yōu)勢也同樣體現(xiàn)在網(wǎng)絡(luò)容量臨界處.此外，AP存在緩存的限制、服務(wù)能力極限，不當?shù)恼{(diào)度會使得緩沖區(qū)中的下行數(shù)據(jù)會發(fā)生丟包.從圖6(c)中對丟包率分析來看，GTSS接近沒有能量節(jié)省的方案，并優(yōu)于RND和FCFS.相同情況下，GTSS能服務(wù)更多數(shù)量的站點.

圖6 仿真結(jié)果比較(下行)

上行鏈路發(fā)送數(shù)據(jù)采用的是隨機接入機制，易發(fā)生碰撞而導致額外的能量開銷.因此，隨著站點數(shù)增加，網(wǎng)絡(luò)性能到達頂峰后開始下滑.從圖7中易得出，當站點數(shù)較多時，采用了TWT的方案由于其對站點信道訪問的時刻做了分配，比沒有采用TWT的方案具有更高的吞吐率和能效.采用TWT的方案中，GTSS由于醒來站點數(shù)的均衡化，比FCFS具有更高的吞吐率和能效.而在接近峰值時，GTSS性能略高于RND.同樣地，隨著站點數(shù)的增加，同樣數(shù)據(jù)量傳輸消耗的總體能量急劇增加，能效下滑.

在偵聽間隔確定的情況下，第一個醒來時刻決定了每個信標幀時槽中服務(wù)的站點數(shù).當所有站點的偵聽間隔值歸入一個子集時，一個TBTT時刻內(nèi)最大醒來站點數(shù)最小化；而當所有站點偵聽間隔分別歸入不同子集時，GTSS等同于隨機.從仿真總體結(jié)果上看，相比RND策略，GTSS更具確定性.同時，當網(wǎng)絡(luò)趨近于服務(wù)界限時，GTSS不會因為系統(tǒng)資源需求的抖動造成緩存溢出和鄰近TBTT傳輸服務(wù)的波動，最終導致更大的丟包率和吞吐率的下降，其性能優(yōu)勢顯現(xiàn).而對于FCFS方案，站點醒來時刻將很大程度上取決于站點提出休眠和系統(tǒng)決策發(fā)生時刻，該方案同RND一樣具有很大的不確定性.當網(wǎng)絡(luò)初始化、重啟動時，F(xiàn)CFS將造成某一個時刻的服務(wù)瓶頸.綜上，GTSS方案具有更高的適應(yīng)性.特別是當采用的偵聽間隔服從一定的規(guī)律，即落入同一個組別時，具有明顯的吞吐率和能效優(yōu)勢.

圖7 仿真結(jié)果比較(上行)

5 結(jié)束語

以密集部署WLAN為研究背景，針對由競爭不均衡導致的網(wǎng)絡(luò)性能下降、終端低能效問題，提出了一種基于IEEE 802.11ax協(xié)議的分組TBTT調(diào)度方案(GTSS).該方案通過對第一個醒來時刻的調(diào)度來控制每個信標幀時槽內(nèi)醒來站點數(shù)以緩解競爭及負載不均衡問題.理論分析了醒來站點數(shù)的特征，仿真證明了所提方案在吞吐率、能效和丟包率方面具有更好的性能.該方案同樣適用于終端能源潰乏、對時延不敏感的周期性上行傳輸場景.后續(xù)將關(guān)注偵聽間隔動態(tài)調(diào)整，探討以集中控制為核心的確定性信道訪問機制及信道資源分配策略，還將從TWT角度對AP能耗問題進行研究.