物聯網中可分級的大數據流動態調度算法

鐘 健,楊 瓊,高 薇

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

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

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

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

針對上述問題，提出了動態的LTE上行數據包調度器，該調度器使用各設備的當前流量信息與流量的分配記錄來將數據流分類，并為無線資源的分配設置優先級。此外，利用統計的信息來度量網絡的擁塞度，通過動態地調節調度器來控制網絡的擁塞。本調度器主要有3個優點：控制了M2M通信對H2H性能的影響；保證調度器的公平性，防止“餓死”的問題；滿足M2M應用的QoS要求。

1 背景知識

1.1 M2M應用的分類

M2M通信的主要應用場景是使用物理設備來監控一些環境或人體的參數，例如溫度、濕度、速度、位置與心跳等，將采集的數據通過網絡傳輸到服務器中，服務器對數據進行處理。按M2M的應用場景主要可以將M2M通信分為以下兩種。

事件-驅動型：監控區域內發生一個事件，設備將消息發送到服務器。因為事件一般發生在緊急的情況下，所以這種類型的應用需要高可靠性、實時性以及高優先級。突發傳輸模式屬于該類型。

時間-驅動型：大多數的M2M應用均屬于該類型，設備在常規的時間段將采集的數據發送到服務器進行處理，該類型的應用具有延遲容忍特性，且傳輸的優先級較低、網絡擁塞時可能被拒絕。

此外，M2M通信具有一些共同的特點，例如低移動性、數據量小以及能量約束等。總體而言，M2M設備發送的數據量高于其接收的數據量，所以本文重點研究上行數據包的調度器[15]。

1.2 LTE網絡的數據包調度器

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

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

圖1 LTE的幀結構

2 問題定義

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

(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)

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

(6)

PLu=128.1+37.6log10distu+

ξ+Peloss+Ffading

(7)

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

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

(8)

(9)

(10)

(11)

因為LTE的上行調度器限制分配到各設備的RB必須是連續的頻率，所以上行數據調度器的最優問題是NP-Hard問題[19]。

實踐可行的上行調度器可分為兩步[20]：

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

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

3 本文的調度器設計

3.1 靜態調度器

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

TDPS中調度器為H2H通信分配優先級，根據各H2H設備的資源需求保留充足的RB資源。因為吞吐量也受信道質量的影響，所以設備所需的RB并非直接由緩存的數據量決定，最終，本調度器使用資源分配的歷史記錄來估計當前H2H設備的RB資源需求，如式(2)所示：

(12)

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

(13)

(14)

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

(15)

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

(16)

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

3.2 動態調度器

因為事件驅動型設備對延遲較為敏感，網絡的擁塞會影響這些設備的QoS，為了解決該問題，在FDPS中根據擁塞的級別動態地選擇M2M設備的最大量。使用事件驅動型設備拒絕的請求比例計算TTIt時的擁塞度C(t)。動態調度器的處理過程如下所示：調度器使用圖2所示的狀態機來監控C(t)，決定當前的擁塞狀態，共有3個擁塞級別的狀態：低、中、高。每個擁塞狀態下，將式(13)的常量ρ設為一個合適的值來降低網絡的擁塞度，并提高請求的QoS。如果調度器發現φ≤C(t)≤ψ，則擁塞狀態為中等狀態；如果C(t)≥ψ，則為高等狀態；如果C(t)<φ，則為低等狀態，其中φ與ψ應滿足0<φ<ψ<1。狀態發生改變時，ρ值也變為新狀態對應的值。

圖2 擁塞的狀態轉換圖

4 實驗結果與分析

4.1 仿真環境

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

表1 仿真器參數設置(M2M流量的數據包大小為200字節)

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

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

4.2 性能評價指標

使用以下兩個性能指標平均調度器的性能：

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

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

(17)

(18)

4.3 與其他LTE調度器的比較

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

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

表2 仿真中各調度器的基本性質

4.4 實驗結果與分析

圖3所示是網絡吞吐量與M2M設備數量的關系，圖3(a)～(e)分別為VoIP、Video、CBR、事件驅動型M2M與時間驅動型M2M的性能結果。對于圖3(a)～(c)的H2H流量，CDPD_M2M調度器的結果最優。對Video與CBR兩個流量所有調度器的結果十分接近；對于VoIP流量，EDS_LTE、CDPD_M2M與RSA_M2M的結果接近，本調度器與QP_LTE調度器的性能較弱；對于CBR流量，QP_LTE調度器的性能較差，因為QP_LTE調度器中該流量的優先級設置較低。RSA_M2M的調度器對H2H流量的吞吐量性能最差，原因在于：RSA_M2M將H2H與M2M流量同等地對待，并未進行優化處理。

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

圖3 網絡吞吐量與M2M設備數量的關系

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

圖4 公平指數與M2M設備數量的關系

5 結束語

現有的M2M調度器方案并未解決調度器的公平性，并且未能控制M2M通信對H2H性能的影響。本文設計了動態的LTE上行數據包調度器，控制了M2M通信對H2H性能的影響，保證了調度器的公平性，防止餓死的問題，滿足了M2M應用的QoS要求。未來將研究采用人工智能算法優化LTE中M2M流量與H2H流量的權重值，從而進一步提高M2M通信的性能。