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

(東南大學(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é)點(diǎn)，會產(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ù)是實(shí)現(xiàn)網(wǎng)絡(luò)QoS(Quality of Service)的核心技術(shù)，是實(shí)現(xiàn)網(wǎng)絡(luò)DiffServ模型的主要手段，是用于解決網(wǎng)絡(luò)延遲和阻塞等問題的技術(shù)支撐。隊(duì)列調(diào)度的原理為將待轉(zhuǎn)發(fā)數(shù)據(jù)按照一定的標(biāo)準(zhǔn)分類為若干個(gè)隊(duì)列，并且按照規(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)具有一定的邊緣計(jì)算能力，在網(wǎng)關(guān)實(shí)現(xiàn)優(yōu)化的調(diào)度傳輸模型具有可行性。常見的可以應(yīng)用于邊緣網(wǎng)關(guān)的隊(duì)列調(diào)度算法[6]包括：基于優(yōu)先級的調(diào)度算法(Priority Queue,PQ)、基于輪詢的算法(Round Robin,RR)、基于GPS(General Processor Sharing)流模型的算法等。

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

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

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

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

1.1 WF2Q+算法原理

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

(1)

(2)

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

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

(3)

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

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

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

1.2 算法缺陷

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

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

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

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

考慮在WF2Q+算法的基礎(chǔ)上，將數(shù)據(jù)包分為實(shí)時(shí)數(shù)據(jù)、低時(shí)延數(shù)據(jù)和普通優(yōu)先級數(shù)據(jù)。數(shù)據(jù)包經(jīng)過分類器，分為實(shí)時(shí)隊(duì)列、低時(shí)延隊(duì)列和優(yōu)先級隊(duì)列。調(diào)度器根據(jù)3種不同隊(duì)列的調(diào)度機(jī)制從隊(duì)列中挑選數(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 實(shí)時(shí)隊(duì)列調(diào)度機(jī)制

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

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

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

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

(4)

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

(5)

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

(6)

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

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

優(yōu)先級隊(duì)列根據(jù)WF2Q+算法計(jì)算隊(duì)列虛擬服務(wù)完成時(shí)間，通過調(diào)度器選擇，出隊(duì)獲取轉(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í)，判斷令牌桶中是否有足夠的令牌數(shù)量發(fā)送該數(shù)據(jù)包，如果數(shù)量足夠，則可以直接發(fā)送，數(shù)據(jù)包發(fā)送后，令牌桶需要移除相應(yīng)數(shù)量的令牌。如果令牌桶中令牌數(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é)議接入多個(gè)網(wǎng)關(guān)時(shí)，建立多網(wǎng)關(guān)協(xié)同傳輸模型，子設(shè)備自主選擇網(wǎng)關(guān)進(jìn)行數(shù)據(jù)傳送，從而在單網(wǎng)關(guān)網(wǎng)絡(luò)擁擠時(shí)降低系統(tǒng)整體傳送時(shí)延。多網(wǎng)關(guān)協(xié)同傳輸模型如圖3所示。

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

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

(7)

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

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)

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

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

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

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

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

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

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

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

表1 令牌桶算法對時(shí)延影響

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

級聯(lián)令牌桶的改進(jìn)的WF2Q+算法可以區(qū)分實(shí)時(shí)隊(duì)列、低時(shí)延隊(duì)列和普通優(yōu)先級隊(duì)列，為實(shí)時(shí)數(shù)據(jù)提供更低的傳輸時(shí)延，并且算法具有應(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個(gè)不同的網(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ù)均勻分配給各個(gè)網(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)行隊(duì)列調(diào)度。取每個(gè)隊(duì)列前50個(gè)獲取轉(zhuǎn)發(fā)服務(wù)的數(shù)據(jù)包，各個(gè)隊(duì)列的平均時(shí)延如圖10所示。

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

圖10 隊(duì)列平均傳輸時(shí)延

4 結(jié)束語

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