應(yīng)用于物聯(lián)網(wǎng)邊緣網(wǎng)關(guān)的隊列調(diào)度算法研究

袁 瑞, 蔣 偉, 胡 靜, 宋鐵成

(東南大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 南京 211102)

網(wǎng)關(guān)為非直連設(shè)備連接物聯(lián)網(wǎng)平臺的橋梁。物聯(lián)網(wǎng)網(wǎng)關(guān)整合了物聯(lián)網(wǎng)的多種接入手段[1]，接入大量設(shè)備節(jié)點，會產(chǎn)生大量需要轉(zhuǎn)發(fā)的數(shù)據(jù)。在網(wǎng)絡(luò)帶寬受限制的情況下，網(wǎng)關(guān)數(shù)據(jù)會產(chǎn)生積壓，子設(shè)備與物聯(lián)網(wǎng)平臺之間的通信鏈路被堵塞。

分組調(diào)度技術(shù)是實現(xiàn)網(wǎng)絡(luò)QoS(Quality of Service)的核心技術(shù)，是實現(xiàn)網(wǎng)絡(luò)DiffServ模型的主要手段，是用于解決網(wǎng)絡(luò)延遲和阻塞等問題的技術(shù)支撐。隊列調(diào)度的原理為將待轉(zhuǎn)發(fā)數(shù)據(jù)按照一定的標(biāo)準(zhǔn)分類為若干個隊列，并且按照規(guī)則選取合適的分組提供轉(zhuǎn)發(fā)服務(wù)。

為了優(yōu)化物聯(lián)網(wǎng)網(wǎng)關(guān)的數(shù)據(jù)傳輸模型，考慮在網(wǎng)關(guān)上植入調(diào)度機(jī)制。分組調(diào)度策略適用于不同網(wǎng)絡(luò)環(huán)境[2-3]，調(diào)度算法輕量化可以被應(yīng)用在邊緣環(huán)境[4-5]。由于物聯(lián)網(wǎng)網(wǎng)關(guān)具有一定的邊緣計算能力，在網(wǎng)關(guān)實現(xiàn)優(yōu)化的調(diào)度傳輸模型具有可行性。常見的可以應(yīng)用于邊緣網(wǎng)關(guān)的隊列調(diào)度算法[6]包括：基于優(yōu)先級的調(diào)度算法(Priority Queue,PQ)、基于輪詢的算法(Round Robin,RR)、基于GPS(General Processor Sharing)流模型的算法等。

PQ算法按照優(yōu)先級為各個隊列提供服務(wù)，只有當(dāng)優(yōu)先級高的隊列為空時才會為低優(yōu)先級隊列提供轉(zhuǎn)發(fā)服務(wù)，該算法是靜態(tài)的調(diào)度算法，低優(yōu)先級數(shù)據(jù)包會出現(xiàn)“餓死”現(xiàn)象；基于輪詢[7]的算法對所有隊列進(jìn)行輪詢調(diào)度，在某個隊列業(yè)務(wù)量較大時，會降低系統(tǒng)的性能；GPS模型則假設(shè)數(shù)據(jù)是理想化模型，按照每個隊列的權(quán)重比例分配帶寬，GPS算法假設(shè)數(shù)據(jù)包無限可分，但在實際應(yīng)用中無法實現(xiàn)。在GPS模型基礎(chǔ)上，前人提出了WFQ[8]、WF2Q[9]、WF2Q+(Worst-Case Fair Weighted Fair Queueing+)[10]等公平隊列調(diào)度算法，此類隊列調(diào)度技術(shù)按優(yōu)先級分配帶寬，適用于物聯(lián)網(wǎng)網(wǎng)關(guān)環(huán)境，可以在邊緣網(wǎng)關(guān)建立隊列管理機(jī)制，降低實時數(shù)據(jù)的時延。

為了優(yōu)化物聯(lián)網(wǎng)邊緣網(wǎng)關(guān)上行數(shù)據(jù)傳輸模型，考慮利用網(wǎng)關(guān)邊緣計算能力，在物聯(lián)網(wǎng)網(wǎng)關(guān)引入WF2Q+ 調(diào)度算法進(jìn)行隊列管理。在WF2Q+算法中優(yōu)先級隊列的基礎(chǔ)上引入實時隊列和低時延隊列[11](Low Latency Queue)的概念，可以在網(wǎng)絡(luò)擁堵的情況下保證對延時敏感的數(shù)據(jù)及時獲得轉(zhuǎn)發(fā)服務(wù)。在隊列調(diào)度模型后級聯(lián)令牌桶進(jìn)行流量整形，并且建立多網(wǎng)關(guān)協(xié)同傳輸模型。仿真結(jié)果表明，在傳輸方案中將隊列分為實時隊列、低時延隊列和優(yōu)先級隊列，可以降低數(shù)據(jù)傳輸時延，保障網(wǎng)絡(luò)通信穩(wěn)定可靠。

1 隊列調(diào)度算法簡析

為了降低物聯(lián)網(wǎng)網(wǎng)關(guān)傳輸時延，在網(wǎng)關(guān)搭建隊列調(diào)度機(jī)制、比較傳統(tǒng)調(diào)度算法后，選擇基于WF2Q+算法進(jìn)行改進(jìn)。

1.1 WF2Q+算法原理

WF2Q+算法的基本思想[10]是維護(hù)一個系統(tǒng)虛擬時間V(t)。包裹經(jīng)過分類器后，形成多個具有不同優(yōu)先級的隊列，每個隊列計算一個虛擬服務(wù)開始時間Si(等于隊列i頭部的數(shù)據(jù)包虛擬服務(wù)開始時間)和隊列虛擬服務(wù)結(jié)束時間Fi(等于隊列i頭部的數(shù)據(jù)包虛擬服務(wù)介紹時間)。隊列i第k個包裹到達(dá)時，虛擬服務(wù)開始時間Si和虛擬服務(wù)結(jié)束時間Fi需要根據(jù)公式進(jìn)行更新：

(1)

(2)

WF2Q+算法將系統(tǒng)虛擬時間函數(shù)更新公式的定義為

VWF2Q+(tj-1+τ)=max(VWF2Q+(t)+W(t,t+τ),mini∈B(Si))

(3)

式中：W(t,t+τ)為在(t,t+τ)時間內(nèi)數(shù)據(jù)包得到的服務(wù)量；B為非空隊列集合。

WF2Q+算法采用SEFF(Smallest Eligible Virtual Finish-Time First)分組策略，首先對于等待調(diào)度的隊列進(jìn)行測試，只有虛擬服務(wù)開始時間Si小于系統(tǒng)虛擬時間V(t)的分組才具有出隊資格；其次在具有通過測試的隊列中選擇具有最小的虛擬服務(wù)結(jié)束時間Fi的隊列，為其提供轉(zhuǎn)發(fā)服務(wù)。

WF2Q+算法在眾多公平隊列調(diào)度算法中提供了最為嚴(yán)格的時延控制，并且可以提供最小的WFI(Time Worst-Case Fair Index)指數(shù)。

1.2 算法缺陷

WF2Q+算法的缺陷在于對于所有業(yè)務(wù)流都按比例分配帶寬，并不能區(qū)分實時業(yè)務(wù)流和非實時業(yè)務(wù)流。當(dāng)實際網(wǎng)絡(luò)波動、帶寬不足時，實時性業(yè)務(wù)會得不到即時的轉(zhuǎn)發(fā)服務(wù)。并且當(dāng)存在突發(fā)性數(shù)據(jù)流進(jìn)入網(wǎng)關(guān)時，網(wǎng)絡(luò)會出現(xiàn)擁塞現(xiàn)象。

2 改進(jìn)的隊列調(diào)度模型

針對WF2Q+算法的不足，本文提出了一種改進(jìn)的WF2Q+調(diào)度策略，搭建了多網(wǎng)關(guān)協(xié)同傳輸?shù)哪Ｐ?。該算法可以區(qū)分實時數(shù)據(jù)隊列、低時延隊列和普通優(yōu)先級隊列，并且加入令牌桶作為流量監(jiān)管機(jī)制，很好地提升了網(wǎng)絡(luò)時延性能，可以應(yīng)對突發(fā)數(shù)據(jù)流造成網(wǎng)絡(luò)擁堵崩潰的情況。

2.1 單網(wǎng)關(guān)改進(jìn)的WF2Q+策略

考慮在WF2Q+算法的基礎(chǔ)上，將數(shù)據(jù)包分為實時數(shù)據(jù)、低時延數(shù)據(jù)和普通優(yōu)先級數(shù)據(jù)。數(shù)據(jù)包經(jīng)過分類器，分為實時隊列、低時延隊列和優(yōu)先級隊列。調(diào)度器根據(jù)3種不同隊列的調(diào)度機(jī)制從隊列中挑選數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，最后利用令牌桶算法進(jìn)行流量整形。單網(wǎng)關(guān)改進(jìn)的WF2Q+算法模型如圖1所示。

圖1 單網(wǎng)關(guān)改進(jìn)的WF2Q+算法模型

2.1.1 實時隊列調(diào)度機(jī)制

實時隊列具有最高的數(shù)據(jù)優(yōu)先級，并不經(jīng)過隊列調(diào)度器。當(dāng)實時隊列非空時，直接占用帶寬，獲取轉(zhuǎn)發(fā)服務(wù)。實時隊列內(nèi)部采用先入先出(First In First Out,FIFO)規(guī)則。當(dāng)實時隊列為空時，啟用調(diào)度器為其他隊列提供服務(wù)。

2.1.2 低時延隊列調(diào)度機(jī)制

為了保證帶寬有限條件下數(shù)據(jù)的時效性，引入低時延隊列。低時延隊列不產(chǎn)生數(shù)據(jù)積壓時，可以看作普通優(yōu)先級隊列，根據(jù)隊列權(quán)重分配帶寬，根據(jù)調(diào)度規(guī)則選擇數(shù)據(jù)包出列。當(dāng)?shù)蜁r延隊列產(chǎn)生數(shù)據(jù)積壓時，則對隊列權(quán)值進(jìn)行調(diào)整。

WF2Q+算法根據(jù)隊列權(quán)重分配帶寬，因此隊列i末尾數(shù)據(jù)包傳輸時延為

(4)

式中：B為非空隊列集合；φi為隊列i設(shè)定的權(quán)值；QLcrt為當(dāng)前隊列長度；bandwidth為隊列分配帶寬。根據(jù)希望獲得的隊列最大時延，設(shè)定隊列最大長度QLmax和隊列長度閾值Qth。根據(jù)隊列長度反饋，在數(shù)據(jù)包進(jìn)入隊列時，為低時延隊列動態(tài)分配時延為

(5)

此時隨著數(shù)據(jù)包積壓，低時延隊列會被分配獲取更大的權(quán)值。同時，為了保障網(wǎng)絡(luò)極端擁擠環(huán)境下隊列延遲情況，在數(shù)據(jù)包k出隊時，修改虛擬服務(wù)結(jié)束時間更新函數(shù)為

(6)

當(dāng)隊列長度超過最大長度QLmax時，包裹出隊只為隊列虛擬服務(wù)完成時間帶去很小的增益，隊列可以更好地?fù)屨汲鲫牱?wù)，從而控制隊列時延。

2.1.3 優(yōu)先級隊列調(diào)度機(jī)制

優(yōu)先級隊列根據(jù)WF2Q+算法計算隊列虛擬服務(wù)完成時間，通過調(diào)度器選擇，出隊獲取轉(zhuǎn)發(fā)服務(wù)。

2.1.4 令牌桶算法

令牌桶(Token-Bucket，TB)為一種流量監(jiān)管機(jī)制[12]，能供控制調(diào)度器以固定的速率發(fā)送數(shù)據(jù)，可以應(yīng)對突發(fā)性大量數(shù)據(jù)造成網(wǎng)絡(luò)擁堵的情況，并對數(shù)據(jù)的發(fā)送速率進(jìn)行限制。

令牌桶自身有一定的容量可以存儲一些令牌，令牌以恒定的速率存放到令牌桶中[13]。如果令牌桶已經(jīng)處于滿桶狀態(tài)，應(yīng)停止向令牌桶中添加令牌。當(dāng)有數(shù)據(jù)包到達(dá)時，判斷令牌桶中是否有足夠的令牌數(shù)量發(fā)送該數(shù)據(jù)包，如果數(shù)量足夠，則可以直接發(fā)送，數(shù)據(jù)包發(fā)送后，令牌桶需要移除相應(yīng)數(shù)量的令牌。如果令牌桶中令牌數(shù)量不夠，等待令牌數(shù)量足夠的時候再發(fā)送該數(shù)據(jù)包。令牌桶算法原理如圖2所示。

圖2 令牌桶算法原理

令牌桶可以對流量進(jìn)行整形，令牌桶具有一定深度的容量，可以允許突發(fā)性的數(shù)據(jù)流，總體數(shù)據(jù)發(fā)送速率雖然受到了限制，但是網(wǎng)絡(luò)具有更好的穩(wěn)定性。

2.2 多網(wǎng)關(guān)協(xié)同傳輸模型

當(dāng)物聯(lián)網(wǎng)子設(shè)備可以根據(jù)不同協(xié)議接入多個網(wǎng)關(guān)時，建立多網(wǎng)關(guān)協(xié)同傳輸模型，子設(shè)備自主選擇網(wǎng)關(guān)進(jìn)行數(shù)據(jù)傳送，從而在單網(wǎng)關(guān)網(wǎng)絡(luò)擁擠時降低系統(tǒng)整體傳送時延。多網(wǎng)關(guān)協(xié)同傳輸模型如圖3所示。

圖3 多網(wǎng)關(guān)協(xié)同傳輸模型

網(wǎng)關(guān)l的隊列i計算參數(shù)ηli與當(dāng)前隊列長度QLcrt、隊列分配帶寬有關(guān)，定義為

(7)

多網(wǎng)關(guān)協(xié)同傳輸模型可以避免各個網(wǎng)關(guān)之間傳輸負(fù)載不均衡的現(xiàn)象。根據(jù)網(wǎng)關(guān)傳輸能力，均衡地分配網(wǎng)關(guān)的傳輸任務(wù)，從而降低整體傳輸時延。

3 仿真實驗與結(jié)果分析

在Linux環(huán)境下，搭建網(wǎng)絡(luò)仿真環(huán)境。仿真6條數(shù)據(jù)流，實時數(shù)據(jù)流發(fā)送速率為64 kbit/s，在改進(jìn)的WF2Q+算法下不設(shè)定權(quán)重，在WF2Q+算法下設(shè)定權(quán)重為10，隊列號為1，低時延數(shù)據(jù)包發(fā)送速率均為 128 kbit/s，設(shè)定最大隊列長度QLmax為1024，隊列長隊閾值Qth為512，權(quán)重分別設(shè)定為5和4，隊列號分別對應(yīng)為2和3；優(yōu)先級數(shù)據(jù)包發(fā)送速率為256 kbit/s具有3種權(quán)重：3、2和1，分別對應(yīng)隊列4、5和6。數(shù)據(jù)流從0.0 s開始發(fā)送，對于每個隊列，取前50個數(shù)據(jù)包進(jìn)行時延分析。

3.1 單網(wǎng)關(guān)改進(jìn)WF2Q+策略仿真結(jié)果分析

單網(wǎng)關(guān)仿真拓?fù)浣Y(jié)構(gòu)如圖4所示。

圖4 單網(wǎng)關(guān)仿真拓?fù)浣Y(jié)構(gòu)

首先驗證改進(jìn)的WF2Q+算法對實時數(shù)據(jù)、低時延數(shù)據(jù)的時延控制，分別模擬鏈路帶寬不足(0.3 Mbit/s)和帶寬嚴(yán)重不足(0.1 Mbit/s)的情況，仿真對比WF2Q+算法和改進(jìn)的WF2Q+算法對不同業(yè)務(wù)流時延的影響，兩種算法均使用令牌桶算法進(jìn)行流量整形，時延統(tǒng)計結(jié)果如圖5和圖6所示。

由圖5、圖6可以看出，當(dāng)帶寬不足時，改進(jìn)的WF2Q+算法可以將低時延隊列的傳輸延遲控制在一定時間之內(nèi)；當(dāng)帶寬嚴(yán)重不足時，改進(jìn)的WF2Q+算法仍然可以保證實時業(yè)務(wù)流的傳輸，并且降低了低時延數(shù)據(jù)流的傳輸時延增長速度。

圖5 帶寬為0.1 Mbit/s時不同業(yè)務(wù)流時延

圖6 帶寬為0.3 Mbit/s時不同業(yè)務(wù)流時延

其次驗證令牌桶算法對數(shù)據(jù)傳輸穩(wěn)定性的影響。分別仿真鏈路帶寬充足(1 Mbit/s)和帶寬較為不充足(0.5 Mbit/s)情況下，突發(fā)速率為768 kbit/s高優(yōu)先級(權(quán)重為5)低時延數(shù)據(jù)流，數(shù)據(jù)流從0.1 s持續(xù)至0.15 s。對比使用改進(jìn)的WF2Q+算法級聯(lián)或不級聯(lián)令牌桶算法產(chǎn)生的傳輸時延。仿真結(jié)果如圖7和圖8所示。

圖7 帶寬為0.5 Mbit/s時不同業(yè)務(wù)流時延

圖8 帶寬為1 Mbit/s時不同業(yè)務(wù)流時延

統(tǒng)計帶寬分別為0.5 Mbit/s、1.0 Mbit/s時，級聯(lián)或不級聯(lián)令牌桶情況下，各個隊列產(chǎn)生的最大傳輸時延，WF2Q+/TB表示在改進(jìn)的WF2Q+算法后級聯(lián)令牌桶算法，WF2Q+則表示單獨使用改進(jìn)的WF2Q+算法，隊列產(chǎn)生的最大傳輸時延結(jié)果如表1所示。

表1 令牌桶算法對時延影響

比較仿真結(jié)果，令牌桶算法使鏈路更加穩(wěn)定，存在突發(fā)數(shù)據(jù)流時，令牌桶算法可以更快速降低傳輸時延，并且控制隊列時延最大值。

級聯(lián)令牌桶的改進(jìn)的WF2Q+算法可以區(qū)分實時隊列、低時延隊列和普通優(yōu)先級隊列，為實時數(shù)據(jù)提供更低的傳輸時延，并且算法具有應(yīng)對突發(fā)數(shù)據(jù)流的能力，可以保證網(wǎng)關(guān)傳輸?shù)姆€(wěn)定性。

3.2 多網(wǎng)關(guān)協(xié)同傳輸模型仿真結(jié)果與分析

多網(wǎng)關(guān)協(xié)同傳輸仿真拓?fù)浣Y(jié)構(gòu)如圖9所示。

圖9 多網(wǎng)關(guān)協(xié)同傳輸仿真拓?fù)浣Y(jié)構(gòu)

仿真結(jié)構(gòu)中，假設(shè)子設(shè)備可以選擇傳送數(shù)據(jù)給3個不同的網(wǎng)關(guān)。假設(shè)網(wǎng)關(guān)1鏈路帶寬為0.1 Mbit/s，網(wǎng)關(guān)2、網(wǎng)關(guān)3的鏈路帶寬為0.2 Mbit/s。發(fā)送端產(chǎn)生的數(shù)據(jù)包根據(jù)規(guī)則自主挑選網(wǎng)關(guān)，經(jīng)過網(wǎng)關(guān)到達(dá)接收端。對照組假定發(fā)送端產(chǎn)生的數(shù)據(jù)均勻分配給各個網(wǎng)關(guān)，網(wǎng)關(guān)對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，網(wǎng)關(guān)內(nèi)部均采用改進(jìn)的WF2Q+算法進(jìn)行隊列調(diào)度。取每個隊列前50個獲取轉(zhuǎn)發(fā)服務(wù)的數(shù)據(jù)包，各個隊列的平均時延如圖10所示。

由圖10可以看出，多網(wǎng)關(guān)協(xié)同傳輸模型可以降低子設(shè)備數(shù)據(jù)傳輸整體時延。數(shù)據(jù)包自主選擇路徑傳送，優(yōu)化了傳輸路徑選擇策略。

圖10 隊列平均傳輸時延

4 結(jié)束語

基于WF2Q+算法提出了一種應(yīng)用于物聯(lián)網(wǎng)網(wǎng)關(guān)傳輸模型中的改進(jìn)的WF2Q+隊列調(diào)度策略。該策略對優(yōu)先隊列算法無法區(qū)分會話優(yōu)先級的情況進(jìn)行了優(yōu)化，引入了實時隊列、低時延隊列、優(yōu)先級隊列的分類，保障了網(wǎng)絡(luò)堵塞情況下實時隊列和低時延隊列的及時傳輸，級聯(lián)令牌桶算法保證調(diào)度模型在遇到突發(fā)數(shù)據(jù)流時具有穩(wěn)定性。在改進(jìn)隊列調(diào)度算法的基礎(chǔ)上提出了多網(wǎng)關(guān)協(xié)同傳輸模型，數(shù)據(jù)包依據(jù)規(guī)則自主選擇傳輸路徑，保證了單網(wǎng)關(guān)傳輸帶寬有限情況下數(shù)據(jù)包可以正常傳輸至物聯(lián)網(wǎng)平臺。該傳輸模型具有很好的應(yīng)用前景和實用意義。