物聯(lián)網(wǎng)中可分級的大數(shù)據(jù)流動態(tài)調(diào)度算法

鐘 健,楊 瓊,高 薇

(1.廣東技術(shù)師范大學(xué)天河學(xué)院 計算機(jī)科學(xué)與工程學(xué)院，廣州 510540；2.華東師范大學(xué) 教育信息技術(shù)學(xué)系，上海 200062；3.云南大學(xué) 軟件學(xué)院，昆明 650091)

隨著物聯(lián)網(wǎng)的飛速發(fā)展，物聯(lián)網(wǎng)將會接入海量、不同類型的智能設(shè)備(例如智能家電、自動駕駛汽車、智能手機(jī)等)[1-2]，這些智能設(shè)備之間會互相連接并互相通信，這種通信稱為M2M(machine to machine)通信[3]，是物聯(lián)網(wǎng)的一個重要部分。物聯(lián)網(wǎng)重點(diǎn)關(guān)注于人與人(H2H)、物理設(shè)備之間(M2M)的關(guān)系，M2M通信屬于連接的中心[4]。目前，M2M通信已廣泛地應(yīng)用于社會的各個領(lǐng)域中，例如醫(yī)療、安全、運(yùn)輸、智能抄表等[5]，根據(jù)Ericsson的報告，預(yù)計在2020年全球?qū)⒂?00億的設(shè)備，屆時M2M通信將產(chǎn)生巨大的流量[6]，因此物聯(lián)網(wǎng)中M2M通信將超過H2H通信(例如VoIP、媒體流、網(wǎng)頁流量等)的流量。物聯(lián)網(wǎng)中許多設(shè)備(例如智能手機(jī)、智能電視等)通過公共網(wǎng)絡(luò)(Wifi、WIMAX、LTE等)獲取數(shù)據(jù)，其中LTE網(wǎng)絡(luò)是無線網(wǎng)絡(luò)中應(yīng)用最為廣泛的公用網(wǎng)絡(luò)之一[7-8]。

LTE是蜂窩網(wǎng)中應(yīng)用最為廣泛的一個標(biāo)準(zhǔn)，LTE的優(yōu)點(diǎn)主要有覆蓋率高、具有無縫連接性、數(shù)據(jù)速率高、延遲低[9]，但LTE最初是為了典型的移動通信(H2H)而設(shè)計，因此不能較好地滿足M2M通信的特點(diǎn)與需求。M2M與H2H主要有以下3點(diǎn)區(qū)別[10]：數(shù)據(jù)量小、傳輸頻率較低；延遲容忍特性好；上行流量為主要流量。因?yàn)镸2M與H2H通信之間的差異，直接將M2M通信引入LTE網(wǎng)絡(luò)中會產(chǎn)生很多的問題，如果一個區(qū)域中同時引入大量的設(shè)備，將導(dǎo)致無線資源的緊缺，并擠壓H2H流量的空間。

為了滿足M2M通信上行流量大于下行流量的特點(diǎn)，LTE的上行數(shù)據(jù)調(diào)度器是一個亟待解決的問題。文獻(xiàn)[11]為LTE中H2H通信的調(diào)度器提出了改進(jìn)方案，假設(shè)M2M的應(yīng)用類型較少，并且未能解決H2H資源緊缺的問題，所以并不滿足M2M通信的特點(diǎn)。文獻(xiàn)[12-14]均對M2M通信提出了改進(jìn)策略，但這些方案并未解決調(diào)度器的公平性，并且并未控制M2M通信對H2H性能(吞吐量、QoS等)的影響。

針對上述問題，提出了動態(tài)的LTE上行數(shù)據(jù)包調(diào)度器，該調(diào)度器使用各設(shè)備的當(dāng)前流量信息與流量的分配記錄來將數(shù)據(jù)流分類，并為無線資源的分配設(shè)置優(yōu)先級。此外，利用統(tǒng)計的信息來度量網(wǎng)絡(luò)的擁塞度，通過動態(tài)地調(diào)節(jié)調(diào)度器來控制網(wǎng)絡(luò)的擁塞。本調(diào)度器主要有3個優(yōu)點(diǎn)：控制了M2M通信對H2H性能的影響；保證調(diào)度器的公平性，防止“餓死”的問題；滿足M2M應(yīng)用的QoS要求。

1 背景知識

1.1 M2M應(yīng)用的分類

M2M通信的主要應(yīng)用場景是使用物理設(shè)備來監(jiān)控一些環(huán)境或人體的參數(shù)，例如溫度、濕度、速度、位置與心跳等，將采集的數(shù)據(jù)通過網(wǎng)絡(luò)傳輸?shù)椒?wù)器中，服務(wù)器對數(shù)據(jù)進(jìn)行處理。按M2M的應(yīng)用場景主要可以將M2M通信分為以下兩種。

事件-驅(qū)動型：監(jiān)控區(qū)域內(nèi)發(fā)生一個事件，設(shè)備將消息發(fā)送到服務(wù)器。因?yàn)槭录话惆l(fā)生在緊急的情況下，所以這種類型的應(yīng)用需要高可靠性、實(shí)時性以及高優(yōu)先級。突發(fā)傳輸模式屬于該類型。

時間-驅(qū)動型：大多數(shù)的M2M應(yīng)用均屬于該類型，設(shè)備在常規(guī)的時間段將采集的數(shù)據(jù)發(fā)送到服務(wù)器進(jìn)行處理，該類型的應(yīng)用具有延遲容忍特性，且傳輸?shù)膬?yōu)先級較低、網(wǎng)絡(luò)擁塞時可能被拒絕。

此外，M2M通信具有一些共同的特點(diǎn)，例如低移動性、數(shù)據(jù)量小以及能量約束等?？傮w而言，M2M設(shè)備發(fā)送的數(shù)據(jù)量高于其接收的數(shù)據(jù)量，所以本文重點(diǎn)研究上行數(shù)據(jù)包的調(diào)度器[15]。

1.2 LTE網(wǎng)絡(luò)的數(shù)據(jù)包調(diào)度器

LTE規(guī)范的下行流量使用正交頻分復(fù)用接入(OFDMA)作為無線接入技術(shù)，上行流量則使用SC-FDMA來提高設(shè)備的能量效率。兩個技術(shù)均采用標(biāo)準(zhǔn)的信道，信道的無線資源由兩個域組成：頻率域與時間域，如圖1所示[16]。時間域中，無線資源分為若干傳輸時隙TTI(子幀)，時長為1 ms。一個TTI含有兩個0.5 ms的子時隙，每個子時隙包含7個symbol，一幀共包含10個TTI(20個時隙)。頻率域中，總可用帶寬分為12個子載波的子信道(每個信道為15 kHz)，共有180 kHz。資源塊(RB)是調(diào)度器最小的分配與調(diào)度單位。

數(shù)據(jù)調(diào)度器位于基站的介質(zhì)訪問層(MAC)，負(fù)責(zé)為設(shè)備分配RB(資源塊)。當(dāng)一個設(shè)備需要發(fā)送數(shù)據(jù)，首先向基站發(fā)送一個上行調(diào)度請求，并報告其緩存的數(shù)據(jù)量；然后，上行調(diào)度器根據(jù)數(shù)據(jù)流進(jìn)行調(diào)度決策，并將分配的RB結(jié)果與傳輸格式發(fā)送至設(shè)備。

圖1 LTE的幀結(jié)構(gòu)

2 問題定義

假設(shè)是U={1,…,U)是TTIt時請求資源的設(shè)備集合，R={1,…,R)是可用的RB集合，資源分配問題可定義為以下的優(yōu)化形式：

(1)

約束條件為：

Au,r∈{0,1);?u∈U,?r∈R

(2)

(3)

Ru={r|Au,r=1);?u∈U,?r∈R

(4)

r∈{i,i+1,…,i+l);?u∈U,?r∈Ru

(5)

根據(jù)文獻(xiàn)[17]，式(6)決定了傳輸?shù)哪芰?，Pu是TTIt時設(shè)備u的總傳輸能量，PLu是傳播的路徑損耗，P0與α是蜂窩相關(guān)的參數(shù)。根據(jù)文獻(xiàn)[18]的城市LTE場景，路徑損耗的計算方法為式(7)，其中distu是設(shè)備u與基站的距離(單位為km)，ξ是表示遮蔽效應(yīng)的隨機(jī)變量，假設(shè)其服從(均值為0、標(biāo)準(zhǔn)偏差為8 dB)的對數(shù)正態(tài)分布。Peloss是信號穿透障礙引起的穿透損耗，參數(shù)Ffading表示多徑信號引起的衰落(瑞麗衰落)效應(yīng)：

(6)

PLu=128.1+37.6log10distu+

ξ+Peloss+Ffading

(7)

使用香農(nóng)定理測量設(shè)備u的頻譜效率Cu，單位為bit/s，如下所示：

Cu=BRB|Ru|log2(1+γu)

(8)

(9)

(10)

(11)

因?yàn)長TE的上行調(diào)度器限制分配到各設(shè)備的RB必須是連續(xù)的頻率，所以上行數(shù)據(jù)調(diào)度器的最優(yōu)問題是NP-Hard問題[19]。

實(shí)踐可行的上行調(diào)度器可分為兩步[20]：

步驟1時間域數(shù)據(jù)包調(diào)度(TDPS)：選出優(yōu)先級最高的設(shè)備集合。為了定義TTIt、設(shè)備u的優(yōu)先級，本文設(shè)計了一個效用函數(shù)MTD(u,t)。

步驟2頻率域數(shù)據(jù)包調(diào)度(FDPS)：使用啟發(fā)式算法遍歷步驟1所選設(shè)備的所有分配方案，根據(jù)優(yōu)先級函數(shù)MFD(u,r)選擇最優(yōu)的方案，最終找到式(1)全局最優(yōu)解的近似解。

3 本文的調(diào)度器設(shè)計

3.1 靜態(tài)調(diào)度器

大量的M2M設(shè)備連接到網(wǎng)絡(luò)中，如果同時傳輸數(shù)據(jù)可能導(dǎo)致極高的網(wǎng)絡(luò)擁塞，擁塞會導(dǎo)致RB資源緊缺并影響H2H的性能。為了解決M2M通信對H2H影響的問題，本文為TDPS設(shè)計了一個M2M設(shè)備數(shù)量的控制機(jī)制。

TDPS中調(diào)度器為H2H通信分配優(yōu)先級，根據(jù)各H2H設(shè)備的資源需求保留充足的RB資源。因?yàn)橥掏铝恳彩苄诺蕾|(zhì)量的影響，所以設(shè)備所需的RB并非直接由緩存的數(shù)據(jù)量決定，最終，本調(diào)度器使用資源分配的歷史記錄來估計當(dāng)前H2H設(shè)備的RB資源需求，如式(2)所示：

(12)

如果M2M設(shè)備傳輸?shù)臄?shù)據(jù)量較低(低于1 000比特)，則為每個M2M設(shè)備分配一個固定的資源量。因此，本調(diào)度器為FDPS選定的設(shè)備數(shù)量設(shè)置最大值，如式(13)所示，并為M2M與H2H通信分別保留一定的RB資源，分別如式(14)、(15)所示，式中uM是M2M設(shè)備的集合。通過將H2H與M2M通信的資源分離，獨(dú)立地對兩種通信進(jìn)行調(diào)度，因此本文僅關(guān)注M2M設(shè)備的調(diào)度。

(13)

(14)

RDH(t)=|R|-RDM(t)

(15)

本調(diào)度器使用效用函數(shù)選擇FDPS中的M2M設(shè)備，如式(16)所示，式中Tavg(u,t)是設(shè)備u吞吐量的指數(shù)平均數(shù)指標(biāo)(EMA)，D(u)是請求的截止時間,等于最大延遲與緩存數(shù)據(jù)消耗時間的差值。式(16)中常量ω是保證調(diào)度公平性的權(quán)重。

(16)

未被選擇的M2M設(shè)備u將等待一個隨機(jī)時間(0～μD個TTI)，然后發(fā)出一個請求，其中μ是一個常量(0≤μ≤1)。后續(xù)的請求則相應(yīng)地后移，從而避免大量的設(shè)備短期內(nèi)請求資源所導(dǎo)致的擁塞問題。

3.2 動態(tài)調(diào)度器

因?yàn)槭录?qū)動型設(shè)備對延遲較為敏感，網(wǎng)絡(luò)的擁塞會影響這些設(shè)備的QoS，為了解決該問題，在FDPS中根據(jù)擁塞的級別動態(tài)地選擇M2M設(shè)備的最大量。使用事件驅(qū)動型設(shè)備拒絕的請求比例計算TTIt時的擁塞度C(t)。動態(tài)調(diào)度器的處理過程如下所示：調(diào)度器使用圖2所示的狀態(tài)機(jī)來監(jiān)控C(t)，決定當(dāng)前的擁塞狀態(tài)，共有3個擁塞級別的狀態(tài)：低、中、高。每個擁塞狀態(tài)下，將式(13)的常量ρ設(shè)為一個合適的值來降低網(wǎng)絡(luò)的擁塞度，并提高請求的QoS。如果調(diào)度器發(fā)現(xiàn)φ≤C(t)≤ψ，則擁塞狀態(tài)為中等狀態(tài)；如果C(t)≥ψ，則為高等狀態(tài)；如果C(t)<φ，則為低等狀態(tài)，其中φ與ψ應(yīng)滿足0<φ<ψ<1。狀態(tài)發(fā)生改變時，ρ值也變?yōu)樾聽顟B(tài)對應(yīng)的值。

圖2 擁塞的狀態(tài)轉(zhuǎn)換圖

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

4.1 仿真環(huán)境

使用LTE-Sim仿真器[21]測試本調(diào)度器的性能，仿真設(shè)置一個基站，M2M設(shè)備為固定設(shè)備、H2H設(shè)備設(shè)為速度為4 km/h的移動狀態(tài)來仿真行人。M2M與H2H設(shè)備均勻地分布于以基站為圓心、半徑等于1 km的圓形區(qū)域內(nèi)。帶寬設(shè)為10 MHz(50個RB)，仿真時間為5 000個TTI(5 s)。每組仿真重復(fù)30次，使結(jié)果達(dá)到95%的置信度。表1總結(jié)了仿真的主要參數(shù)，表中未涉及的參數(shù)設(shè)為仿真器的缺省值。LTE-Sim仿真器原本存在許多的缺省參數(shù)，比如：信道衰落模型默認(rèn)為多徑衰落以及多普勒效應(yīng)，因?yàn)楸疚乃惴ㄊ菂f(xié)議層的調(diào)度程序，其他的物理層參數(shù)并不是本文的考察重點(diǎn)，所以這些缺省參數(shù)對各個方法是相同的。

表1 仿真器參數(shù)設(shè)置(M2M流量的數(shù)據(jù)包大小為200字節(jié))

流量類型設(shè)備數(shù)量最大延遲流量格式VoIP40100G.795視頻40200H.263CBR40300128 kbps時間驅(qū)動型M2M70%分組到達(dá)間隙分組到達(dá)間隙=[0.05,5]事件驅(qū)動型M2M30%50 ms泊松過程(γ=0.02)

仿真設(shè)置3種主要的H2H流量：VoIP、video與常量比特率流量(CBR)，每個H2H流量類型設(shè)置40個設(shè)備，時間驅(qū)動型M2M設(shè)備的突發(fā)傳輸建模為一個泊松過程，速度設(shè)為γ=0.02個數(shù)據(jù)包/TTI。時間驅(qū)動型的M2M設(shè)備隨機(jī)地從范圍[0.05,5]s中選擇設(shè)備的固定傳輸間隙。兩種M2M設(shè)備的數(shù)據(jù)包大小均為200個字節(jié)。

4.2 性能評價指標(biāo)

使用以下兩個性能指標(biāo)平均調(diào)度器的性能：

總吞吐量：評價網(wǎng)絡(luò)的QoS性能，如式(17)所示。

Jain公平指數(shù)：評價調(diào)度器的公平性，如式(18)所示。

(17)

(18)

4.3 與其他LTE調(diào)度器的比較

本文選擇了近期4個性能較好的調(diào)度器進(jìn)行比較，如表2所示，分別為QP_LTE[12]、EDS_LTE[22]、CDPD_M2M[14]、RSA_M2M[23]。這4個調(diào)度器均為M2M設(shè)備保留40%的RB資源。

本調(diào)度器對H2H設(shè)備使用PF調(diào)度器，被拒絕請求的等待時間設(shè)為最大值，即D(u)的10%。式(16)中參數(shù)ω設(shè)為0.95。使用式(13)仿真靜態(tài)的調(diào)度器，為M2M設(shè)備保留40%的RB資源，動態(tài)調(diào)度器的ρ值隨著擁塞級別的增加而提高，低、中、高級擁塞對應(yīng)的ρ值分別設(shè)為0.32、0.4、0.48。動態(tài)調(diào)度器參數(shù)φ與ψ的值根據(jù)實(shí)驗(yàn)結(jié)果分別設(shè)為φ=0.2，ψ=0.6，此時達(dá)到最小延遲容忍的數(shù)據(jù)包百分比最低。

表2 仿真中各調(diào)度器的基本性質(zhì)

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

圖3所示是網(wǎng)絡(luò)吞吐量與M2M設(shè)備數(shù)量的關(guān)系，圖3(a)～(e)分別為VoIP、Video、CBR、事件驅(qū)動型M2M與時間驅(qū)動型M2M的性能結(jié)果。對于圖3(a)～(c)的H2H流量，CDPD_M2M調(diào)度器的結(jié)果最優(yōu)。對Video與CBR兩個流量所有調(diào)度器的結(jié)果十分接近；對于VoIP流量，EDS_LTE、CDPD_M2M與RSA_M2M的結(jié)果接近，本調(diào)度器與QP_LTE調(diào)度器的性能較弱；對于CBR流量，QP_LTE調(diào)度器的性能較差，因?yàn)镼P_LTE調(diào)度器中該流量的優(yōu)先級設(shè)置較低。RSA_M2M的調(diào)度器對H2H流量的吞吐量性能最差，原因在于：RSA_M2M將H2H與M2M流量同等地對待，并未進(jìn)行優(yōu)化處理。

本調(diào)度器對于時間驅(qū)動型與事件驅(qū)動型M2M流量均獲得了最高的吞吐量，如圖3(d)、(e)所示，因?yàn)镽SA_M2M調(diào)度器設(shè)計了訪問控制機(jī)制，所以對于事件驅(qū)動型M2M也獲得了較好的性能。圖3(d)可看出：M2M設(shè)備數(shù)量越高，事件驅(qū)動型M2M流量的吞吐量應(yīng)當(dāng)越高，5個調(diào)度器基本滿足該理論。對于時間驅(qū)動型流量，隨著M2M設(shè)備數(shù)量的提高，QP_LTE與RSA_M2M反而呈下降趨勢，并未較好地滿足M2M通信的要求。

圖3 網(wǎng)絡(luò)吞吐量與M2M設(shè)備數(shù)量的關(guān)系

圖4所示是5個調(diào)度器的公平指數(shù)與M2M設(shè)備數(shù)量的關(guān)系，圖4(a)～(e)分別顯示了VoIP、Video、CBR、事件驅(qū)動型M2M與時間驅(qū)動型M2M流量的性能結(jié)果。對于H2H流量，因?yàn)?個調(diào)度器均使用了PF算法，所以都獲得了較高的公平性指數(shù)。CDPD_M2M調(diào)度器因?yàn)樵O(shè)計了截止期策略，所以對H2H流量也獲得了較好的公平性效果。因?yàn)镼P_LTE調(diào)度器中為CBR流量分配了較低的優(yōu)先級，所以QP_LTE調(diào)度器對于CBR流量呈下降趨勢，當(dāng)M2M設(shè)備的數(shù)量較高時，M2M流量使用保留的40%資源，所以后期呈穩(wěn)定趨勢。對于事件驅(qū)動型M2M流量，本算法明顯獲得了最優(yōu)的結(jié)果。此外，使用截止期策略(本算法、EDS_LTE，CDPD_M2M)的調(diào)度器優(yōu)于直接使用最小延遲的調(diào)度器。對于時間驅(qū)動型M2M通信，分配低延遲容忍的調(diào)度器(QP_LTE、RSA_M2M兩個調(diào)度器)比高延遲容忍的調(diào)度器(本算法、EDS_LTE，CDPD_M2M 3個調(diào)度器)獲得了更好的公平性性能，原因在于：時間驅(qū)動型M2M設(shè)備僅獲得了極少的資源，所以設(shè)備間的資源差異較低，反而導(dǎo)致公平性較優(yōu)。

圖4 公平指數(shù)與M2M設(shè)備數(shù)量的關(guān)系

5 結(jié)束語

現(xiàn)有的M2M調(diào)度器方案并未解決調(diào)度器的公平性，并且未能控制M2M通信對H2H性能的影響。本文設(shè)計了動態(tài)的LTE上行數(shù)據(jù)包調(diào)度器，控制了M2M通信對H2H性能的影響，保證了調(diào)度器的公平性，防止餓死的問題，滿足了M2M應(yīng)用的QoS要求。未來將研究采用人工智能算法優(yōu)化LTE中M2M流量與H2H流量的權(quán)重值，從而進(jìn)一步提高M(jìn)2M通信的性能。