丁家瑞，劉凱，孫婕，劉志敏

（北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京 100871）

LTE 系統(tǒng)視頻業(yè)務(wù)的調(diào)度算法

丁家瑞，劉凱，孫婕，劉志敏

（北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京 100871）

實(shí)時(shí)性是評(píng)價(jià)實(shí)時(shí)視頻業(yè)務(wù)的重要指標(biāo)之一，目前針對(duì)實(shí)時(shí)視頻業(yè)務(wù)的已有調(diào)度算法還存在嚴(yán)重的時(shí)延拖尾現(xiàn)象。 重點(diǎn)研究了該問題，在分析已有調(diào)度算法的基礎(chǔ)上，提出了“最大吞吐率—最大權(quán)重時(shí)延優(yōu)先”（modified largest weighted delay first，MT-LWDF ） 算 法 ； 理 論 分 析 了 算 法 中 β 參 數(shù) 的 取 值 范 圍 ， 并 通 過 仿 真 確定 β 的最優(yōu)解，在 此基礎(chǔ)上，對(duì)視頻業(yè)務(wù)的平均時(shí)延、最大時(shí) 延、業(yè)務(wù) 速率、丟幀率等性 能進(jìn)行了 仿 真 ，并 與其他 6種 算 法 進(jìn) 行對(duì) 比 。 結(jié)果 表 明 ，提 出 的 MT-LWDF 算 法 在 優(yōu) 化 視 頻業(yè) 務(wù) 的 速 率 的 基 礎(chǔ) 上，有 效降 低 時(shí) 延 拖尾現(xiàn)象。

LTE；調(diào)度算法；視頻業(yè)務(wù)；仿真

1 引言

隨 著 通 信 技 術(shù) 的 飛 速 發(fā) 展 ，在 基 于 OFDM（orthogonal frequency division multiplexing）的 LTE（Long term evolution）［1］系統(tǒng)中實(shí)現(xiàn)的技術(shù)越來越多，然而無線通信系統(tǒng)視頻資源有限，如何高效地利用有限的資源支持高質(zhì)量的業(yè)務(wù)是現(xiàn)代無線通信技術(shù)的一個(gè)瓶頸，因此引起了下行鏈路調(diào)度算法的研究熱潮。

實(shí)時(shí)視頻業(yè)務(wù)因其實(shí)時(shí)性和高數(shù)據(jù)速率對(duì)調(diào)度算法 提出了更高的要求。根據(jù) LTE 系統(tǒng)中對(duì)視頻業(yè)務(wù)質(zhì)量的要 求［2］，實(shí) 時(shí) 視 頻 業(yè) 務(wù) 視 頻 幀 的 平 均 時(shí) 延 在 100 ms 以 內(nèi) ，分 組 丟 失 率 （packet loss rate，PLR）為 1‰ ，考 慮 到 一 幀 之中 有 8 個(gè) 視 頻 分 組 ，可 以 計(jì) 算 視 頻 丟 幀 率 （frame loss rate，F(xiàn)LR）為 1-（1-PLR）8=8‰。

目前，在 LTE 系統(tǒng)中適用于視頻業(yè)務(wù)的調(diào)度算法主 要分為兩類：一類是具有時(shí)延約束的，如最早截止時(shí)間優(yōu)先（earliest deadline first，EDF）算 法 、最 大 權(quán) 重 時(shí) 延 優(yōu) 先 （largest weighted delay first，LWDF）算 法 、改 進(jìn) 的 最 大 權(quán) 重 時(shí) 延 優(yōu) 先（modified largest weighted delay first，M-LWDF）算 法 、PPM（packet prediction mechanism）算 法 ；一 類 是 沒 有 時(shí) 延 約 束的 ，如 輪 詢 （round robin，RR）、比 例 公 平 （proportional fair，PF）、最 優(yōu) 信 道 質(zhì) 量 （best CQI，BCQI） 或 稱 最 大 吞 吐 率 （max throughput）、QoE（quality of experience）導(dǎo) 向 的 算 法 。

［3］將 LTE 系 統(tǒng) 信 道 質(zhì) 量 反 饋 與 視 頻 編 解 碼進(jìn)行結(jié)合以降低視頻誤碼率，在一定程度上使邊緣用戶實(shí)時(shí)業(yè)務(wù)質(zhì)量得到保證，但系統(tǒng)時(shí)延卻較高，因此該方法不在 本 文 討 論 范 圍 內(nèi) ； 參 考 文 獻(xiàn) ［4］將 RR、PF、BCQI 3 種 算 法進(jìn) 行 了 歸 納 總 結(jié) ； 參 考 文 獻(xiàn) ［5］基 于 EDF 算 法 與 比 例 公 平（PF）算 法 改 變 優(yōu) 先 級(jí) 函 數(shù) ，進(jìn) 行 用 戶 調(diào) 度 ；參 考 文 獻(xiàn) ［6］將EDF、LWDF 和 M-LWDF 算法進(jìn)行了歸納總結(jié)，并指出 EDF算法在有效控制系統(tǒng)時(shí)延的同時(shí)，很大程度上犧牲了吞吐率 ，因 此不適合信道 質(zhì) 量較差的 無 線 通信，而 M-LWDF 由于 基 于 PF 算 法 在 有 效 控 制 時(shí) 延 的 同 時(shí) 能 得 到 接近于 PF算法的吞吐量，在試驗(yàn)控制和吞吐量上都優(yōu)于 RR 調(diào)度算法；參 考 文 獻(xiàn) ［7］提 出 了 兼 顧 時(shí) 延 和 吞 吐 量 的 PPM （packet prediction mechanism）算 法 ，該 算 法 同 時(shí) 對(duì) 時(shí) 延 做 出 了 預(yù)測(cè) ；參 考 文 獻(xiàn) ［8］提 出 了 一 種 QoE 導(dǎo) 向 的 算 法 ， 該 算 法 監(jiān)測(cè)用戶信道質(zhì)量退化情況，信道質(zhì)量退化越嚴(yán)重，用戶優(yōu)先級(jí)越高。

本文在對(duì)以上8種算法進(jìn)行分析的基礎(chǔ)上提出了一種改進(jìn)型算法，稱為 “最大吞吐率—最大權(quán)重時(shí)延優(yōu)先”（max throughput-largest weighted delay first，MT-LWDF）算法，并與已有的算法進(jìn)行了性能對(duì)比。

2 幾種典型的調(diào)度算法

本文分析現(xiàn)有的視頻業(yè)務(wù)調(diào)度算 法，包括 RR、PF、BCQI、EDF、LWDF、M-LWDF、PPM、QoE 導(dǎo)向的算法。

2.1 RR 調(diào)度算法

RR算法輪流為扇區(qū)內(nèi)的用戶提供資源，旨在給用戶平等的機(jī)會(huì)獲得系統(tǒng)的 RB 資源，該算 法 下用戶的 優(yōu) 先 級(jí)函數(shù)可以表示如下。

其中，NUE代表扇區(qū)內(nèi)用戶總數(shù)，P1～discrete Uniform（1，NUE），Pj=（P0+j）mod（NUE+1）；j≠1。

RR算法使用用戶按照設(shè)定的順序， 以均等的機(jī)會(huì)獲得時(shí)域和頻域資源。如果用戶對(duì)資源的請(qǐng)求是等概率的，那么該算法在保證系統(tǒng)長(zhǎng)期公平性的同時(shí)也保證了系統(tǒng)在短期內(nèi)也是公平的，是資源分配算法中最公平的算法。然而，RR 算法僅僅關(guān)注系統(tǒng)的公平性，卻沒有考慮用戶的信道質(zhì)量是不同且時(shí)變的，因此該算法提供的傳輸可靠性并不高，從而導(dǎo)致系統(tǒng)吞吐率降低。所以 RR算法用戶傳輸速率的公平性較差。由于 RR算法具有最高的公平性，通常被當(dāng)作參考算法，用來和其他算法進(jìn)行比較。

2.2 PF 調(diào)度算法

PF 算法將單個(gè)用戶的瞬時(shí)傳輸速率 （信道質(zhì)量的衡量指標(biāo)之一）和該用戶在一個(gè)時(shí)間窗格內(nèi)傳輸速率的平均值進(jìn)行結(jié)合，如果傳輸速率平均值較大，說明在當(dāng)前時(shí)間窗內(nèi)該用戶的調(diào)度時(shí)間較長(zhǎng)，其調(diào)度優(yōu)先級(jí)需要被適當(dāng)降低。由此，PF 算法兼顧了公平性和用戶傳輸速率，實(shí)現(xiàn)了兩 者 之 間的均 衡 ，在 第 n 個(gè) 時(shí) 隙內(nèi) ，用 戶 的 調(diào) 度優(yōu) 先 級(jí) 函數(shù)可以表示如下。

其 中 ，rj（n）表 示 單 個(gè) 用 戶 j的 瞬 時(shí) 傳 輸 速 率 ，Rj（n-1）表示 一 個(gè) 時(shí) 間 窗 tc內(nèi) 用 戶 j的平均傳輸速率，且：

其物理意義是用戶在當(dāng)前時(shí)間窗內(nèi)的平均傳輸速率，等效于傳輸速率以一定時(shí)間內(nèi)的鏈路質(zhì)量為權(quán)重因子進(jìn)行加權(quán)平均。

PF 算法將信道的時(shí)變特性考慮在內(nèi)，根據(jù)該算法，若某用戶獲得更多的傳輸資源，其調(diào)度時(shí)間就會(huì)增加，那么該用戶的優(yōu)先級(jí)就會(huì)降低，此前優(yōu)先級(jí)較低的用戶就會(huì)獲得更高的傳輸機(jī)率。所以，PF 算法的公平性和系統(tǒng)傳輸效率介于 BCQI算法和 RR 算法之間。

2.3 BCQI調(diào)度算法

BCQI算法以使系統(tǒng)獲得最大吞吐率為目的，最大化利用無線信道的時(shí)變性特點(diǎn)，同速率的資源請(qǐng)求條件下，使信道質(zhì)量最好的用戶獲得最多的資源。在第n個(gè)時(shí)隙內(nèi)，該算法下用戶優(yōu)先級(jí)函數(shù)可以表示為：

由于該算法在計(jì)算優(yōu)先級(jí)時(shí)只考慮了用戶的信道質(zhì)量，只要信道質(zhì)量更好的用戶有資源請(qǐng)求，信道質(zhì)量較差的用戶就不會(huì)被調(diào)度，也就無法得到資源。

2.4 EDF 調(diào)度算法

EDF 算法只考慮用戶等待時(shí)延，將傳輸隊(duì)列最前端用戶 的 等 待 時(shí) 延 τHOL，j作 為 優(yōu) 先 級(jí) 參 數(shù) ，優(yōu) 先 級(jí) 與 該 參 數(shù) 正相關(guān)，時(shí)延越大優(yōu)先級(jí)越高。

其 中 ，τmax，j表 示 用 戶 j的 最 大 時(shí) 延 。

2.5 LWDF 調(diào)度算法

LWDF 算 法 在 EDF 算 法的 基 礎(chǔ) 上 考慮 了 用 戶 誤 碼 率和最大時(shí)延上限，用戶優(yōu)先級(jí)函數(shù)可以表示為：

其 中 ，τHOL，j表 示 用 戶 j待 傳 輸 數(shù) 據(jù) 分 組 隊(duì) 列 頭 的 等 待 時(shí)延，αj表示對(duì)應(yīng)的權(quán)重，δj表示第 j個(gè)用戶的最大誤碼率。

由于 LWDF 算法沒有考慮信道質(zhì)量的時(shí)變性 ，因此系統(tǒng)吞吐量不高。

2.6 M-LWDF 調(diào)度算法

M-LWDF 算法將 PF 調(diào)度算法與 LWDF 算 法進(jìn)行了結(jié)合，在考慮時(shí)延的同時(shí)也考慮了信道質(zhì)量，在時(shí)延和系統(tǒng)吞吐量之間實(shí)現(xiàn)了一種均衡。優(yōu)先級(jí)函數(shù)可以表示為：

2.7 PPM 調(diào)度算法

該算法將用戶數(shù)據(jù)分組時(shí)延（包含預(yù)測(cè)時(shí)延）和用戶移動(dòng)性結(jié)合，在降低用戶時(shí)延的同時(shí)也能兼顧系統(tǒng)吞吐量和誤碼率。該方法主要分為 5個(gè)步驟，具體如下。

步 驟 1 通 過 用 戶 端 反 饋 的 CQI （channel quality indicator）確定用戶的移動(dòng)性。

步驟2 根據(jù)用戶隊(duì)列中數(shù)據(jù)分組的剩余時(shí)延確定調(diào)度優(yōu)先級(jí)，剩余時(shí)間越少，優(yōu)先級(jí)越高。

步驟 3 預(yù)測(cè)用戶隊(duì)列中數(shù)據(jù)分組的延時(shí)情況，若預(yù)測(cè)該數(shù)據(jù)分組不會(huì)超時(shí)，則不執(zhí)行步驟 4，否則執(zhí)行。

步驟 4 若預(yù)測(cè)隊(duì)列中有數(shù)據(jù)分組會(huì)超時(shí)，則優(yōu)先處理，直至把所有預(yù)計(jì)超時(shí)的數(shù)據(jù)分組處理完畢。

步驟5 針對(duì)不同速率的用戶采用不同的調(diào)度算法。

由于該算法兼顧時(shí)延和吞吐量，其性能會(huì)介于 BCQI算法和 EDF 算法之間。

2.8 QoE 導(dǎo)向的算法

該算法在用戶端對(duì)用戶不同時(shí)隙的信道質(zhì)量波動(dòng)進(jìn)行檢測(cè)，得出信道質(zhì)量退化指標(biāo)并反饋給基站，基站通過該指標(biāo)配置用戶優(yōu)先級(jí)，用戶信道質(zhì)量退化越大，優(yōu)先級(jí)越高，這樣能保證信道質(zhì)量波動(dòng)較大的用戶獲得足夠的帶寬資源。為了保證狀態(tài)太差的用戶不會(huì)長(zhǎng)時(shí)間占用系統(tǒng)資源，該算法給每個(gè)用戶設(shè)定了最大調(diào)度時(shí)間上限。 該算法流程如圖 1所示。

圖1 QoE 導(dǎo)向的 算 法 流 程

該算法使信道質(zhì)量較差的用戶能得到較好的資源分配，但同時(shí)需要一定的檢測(cè)時(shí)間，根據(jù)仿真結(jié)果，短時(shí)間內(nèi) 該 算 法 的吞吐量低于 RR 算法，一定時(shí)間后會(huì)高于 RR算法。

2.9 典型調(diào)度算法的總結(jié)

RR 算法只考慮資源分配時(shí)用戶的公平性，所以，其在資源分配上最為公平，但用戶傳輸速率較差；BCQI算法只考慮了用戶的信道質(zhì)量，系統(tǒng)速率較高，相反，用戶資源分配公平性較差；PF 算法將信道的時(shí)變特性考慮在內(nèi)，算法的 公 平 性 和 系 統(tǒng) 傳 輸 速 率 介 于 BCQI算 法 和 RR 算 法 之間。QoE 導(dǎo)向的算法主要考慮信道質(zhì)量變差的用戶，算法公平性較好，但系統(tǒng)吞吐量不高。這 4種算法均沒有考慮時(shí)延。

EDF 算法將傳輸隊(duì)列最前端用戶的等待時(shí)延作為優(yōu)先級(jí)參數(shù)，最大程度上降低了系統(tǒng)傳輸時(shí)延，同時(shí)也犧牲了系統(tǒng)傳輸速率；LWDF 算法在 EDF 算法的基礎(chǔ)上考慮 了時(shí)延上限，但沒有考慮信道質(zhì)量，因此系統(tǒng)吞吐量也不高；M-LWDF 算 法 將 PF 調(diào) 度 算 法 與 LWDF 算法 進(jìn) 行 了 結(jié) 合 ，在考慮時(shí)延的同時(shí)也考慮了信道質(zhì)量，實(shí)現(xiàn)了時(shí)延和系統(tǒng)吞吐量之間的均衡。PPM 兼顧時(shí)延和吞吐量，同樣實(shí)現(xiàn)了時(shí)延和系統(tǒng)吞吐量之間的均衡。

3 最大吞吐率—最大權(quán)重時(shí)延優(yōu)先算法

根據(jù)前文討論，現(xiàn)有調(diào)度算法在時(shí)延處理和吞吐率優(yōu)化方面各有優(yōu)缺點(diǎn)，為了在保證時(shí)延的基礎(chǔ)上提升吞吐率，本文將 EDF 算法和 BCQI算法進(jìn)行結(jié)合來優(yōu)化調(diào) 度算法。

由于 EDF 算 法沒有 考 慮 信道質(zhì)量 ，致使其吞 吐 率 過低 ，而 M-LWDF 算 法 中 乘 以 PF 算 法 相 關(guān) 因 子 ，來 自 信 道質(zhì)量的影響因子不夠強(qiáng)。為此，本文首先依據(jù) BCQI算法，在式（5）中乘以吞吐率相關(guān)的因子，以提高信道質(zhì)量的影響進(jìn)而提升吞吐率。該優(yōu)化算法稱為線性時(shí)延權(quán)重優(yōu)先算法（LIN-LWDF），旨在同時(shí)優(yōu)化時(shí)延和吞吐率。

該優(yōu)化算法下用戶優(yōu)先級(jí)表達(dá)式為：

其 中 相 關(guān) 參 數(shù) 如 前 文 所 示 。類 似 于 M-LWDF 算 法 ，LIN-LWDF 算法可能存在時(shí)延“拖尾”問題，為此，本文對(duì)時(shí)延較高的數(shù)據(jù)分組采用了指數(shù)型非線性影響因子。此外，在LTE 系統(tǒng)中，可以根據(jù)來自 用 戶反饋的 MCS 等 級(jí) ，進(jìn) 而 進(jìn)行 傳 輸 塊 （TB）索 引［9］映 射 （集 合 iTBS=｛1，2，… ，26，27｝），得 到高于線性增長(zhǎng)率的非線性對(duì)應(yīng)關(guān)系。

本文將這種時(shí)延指數(shù)型非線性關(guān)系映射到優(yōu)先級(jí)上的算法，稱為“最大吞吐率—最大權(quán)重時(shí)延優(yōu)先”（MT-LWDF）算法。優(yōu)先級(jí)表達(dá)式為：

由于 LTE 系統(tǒng)中 最小 的調(diào)度 單 位 是 子 幀 ，也 即 1 ms，所以在仿真實(shí)時(shí)視頻業(yè)務(wù)時(shí)，將毫秒（ms）作為時(shí)延的單位。

假設(shè)某一用戶為 j，其等待傳輸?shù)臄?shù)據(jù)分組隊(duì)列為 k，隊(duì)列頭的等待時(shí)延為。 τmin=1，視 頻 業(yè) 務(wù) 中 ，每 個(gè) 用 戶 的 數(shù) 據(jù) 分 組 平 均 時(shí) 延 最 高 為100 ms，考慮到個(gè)別數(shù)據(jù)分組存在較大時(shí)延的偶然性以及兼 顧 信 道 的 隨 機(jī) 性 ，設(shè) 定 τmax=150。

由于該算法的相對(duì)優(yōu)先級(jí)同時(shí)受到時(shí)延和速率的影響，所以提出以下約束條件來確定 β的取值范圍。

約 束 1 延 遲 參 數(shù) τHOL，j的 影 響 因 子 不 能 為 0， 也 即BCQI算法的 ri不 能 完 全 決 定 不 同 用 戶 的 相 對(duì) 優(yōu) 先 級(jí) 大小，否則，該算法將等同于 BCQI算法。約束關(guān)系表示為：

約 束 2 BCQI算 法 的 ri的 影 響 因 子 不 能 為 0， 也 即LWDF 算 法 的 τHOL，j不 能 完 全 決 定 不 同 用 戶 的 相 對(duì) 優(yōu) 先 級(jí) 大小，否則，該算法將等同于 LWDF 算法。約束關(guān)系表示為：

約 束 3 τHOL，j取 最 大 值 ，rj取 最 小 值 時(shí) ，該 算 法 的 優(yōu) 先級(jí) 不 能 小 于 τHOL，j取 最 小 值 ，rj取 最 大 值 時(shí) 的 優(yōu) 先 級(jí) 。約 束關(guān)系表示為：

參 考 文 獻(xiàn) ［1］中 規(guī) 定 了 rj的 取 值 范 圍 ，當(dāng) iTBS分 別 取18、17 時(shí)式（10）比值最小，其變換后的表達(dá)式為：

可得：

式（11）變換后的表達(dá)式為：

可得：

式（12）變換后的表達(dá)式為：

可得：

綜合式（16）～式（18）可得 β的取值范圍為：

基 于 BCQI算 法 對(duì) 不 同 iTBS、β取 值 下 的 相 對(duì) 優(yōu) 先 級(jí) 進(jìn)行 了 仿 真 ，如圖 2 所 示 。圖 2 中 ，圓圈表示優(yōu)先級(jí)，下 方 豎條表示時(shí)延因子對(duì)優(yōu)先級(jí)的影響。當(dāng) β取值較?。é?10）時(shí)相對(duì)優(yōu)先級(jí)變化不明顯，優(yōu)先級(jí)變化范圍重疊很多；當(dāng) β取 值 較 大 （β=1 500）時(shí) ， 時(shí) 延 因 子 對(duì) 優(yōu) 先 級(jí) 的 影 響 太 小 ，因此，采用的 β的范圍為 β∈［10，100］。

4 調(diào)度算法的仿真分析

由于視頻業(yè)務(wù)中用戶隨機(jī)接入并請(qǐng)求發(fā)送數(shù)據(jù)，其數(shù)據(jù)傳輸時(shí)間由具有隨機(jī)性的數(shù)據(jù)分組大小和信道速率決定 。而 半 馬 爾 科 夫 過 程 （semi-Markov process，SMP）是 采 用了指數(shù)形式的無記憶模型，因此數(shù)據(jù)傳輸時(shí)間不能直接用該方法分析建模。本文根據(jù)延時(shí)約束采用仿真方法來確定β的取值，然后分析提出的新算法和現(xiàn)有算法在吞吐率和時(shí)延方面的性能。

實(shí) 時(shí) 視 頻 業(yè) 務(wù) 源 模 型 ，采 用 3GPP［10］和 IEEE 視 頻 業(yè) 務(wù)文 檔［11］的 定 義 。視 頻 業(yè) 務(wù) 的 基 本 單 位 是 視 頻 幀 ，其 周 期 為100 ms，每 個(gè) 視 頻 幀 含 8 個(gè) 數(shù) 據(jù) 分 組 ，其 長(zhǎng) 度 及 間 隔 服 從截 斷 pareto 分布。 該 業(yè) 務(wù) 源 模 型 參 數(shù) 見 表 1。根 據(jù) 該 業(yè) 務(wù)源模型產(chǎn)生的數(shù)據(jù)分組的分布如圖 3所示。

圖2 不 同 iTBS、β 取 值 下 的 相 對(duì) 優(yōu) 先 級(jí) （BCQI 算 法 與 MT-LWDF 算 法 ）

本 文 采 用 的 仿 真 平 臺(tái) 基 于 TD-LTE 系 統(tǒng) 級(jí) 仿 真 平 臺(tái)［12］，仿真參數(shù)見表 2。

根 據(jù) 前 面 理 論 推 導(dǎo) 確 定 了 β的 范 圍 為 β∈ ［10，100］，在該范圍內(nèi)進(jìn)行離散化仿真可得如圖 4所示的仿真結(jié)果。

表1 實(shí)時(shí)視頻業(yè)務(wù)源模型參數(shù)

圖3 實(shí)時(shí)視頻業(yè)務(wù)源模型

根據(jù)該仿真結(jié)果可以確定當(dāng) β∈［35，40］時(shí)系統(tǒng)時(shí)延取得極小值，而同時(shí)系統(tǒng)速率取得局部極大值，由于本文算法在時(shí)延參數(shù)上基于 EDF 算法，故設(shè)定 β取值為 35。由仿真得到最優(yōu)的 β數(shù)值后，在 TD-LTE 仿真平臺(tái)中，對(duì)不同的調(diào)度算法的性能進(jìn)行仿真，得到不同的仿真結(jié)果。

表2 TD-LTE 系統(tǒng)級(jí)仿真平臺(tái)仿真參數(shù)

從 圖 5 可 以 看 出 ，在 系 統(tǒng) 速 率 方 面 BCQI算 法 優(yōu) 于PF 算 法 ，MT-LWDF 算 法 相 對(duì) 于 M-LWDF 算 法 提 升 約 6%，相對(duì)于 EDF 算法則 有更高的提 升，但略低于 BCQI算 法 ；LIN-LDWF 算 法 和 MT-LWDF 算 法 基 本 相 同 。時(shí) 延 方 面 ，BCQI算法最高 ，與 理論結(jié)果 相 符；MT-LWDF 算 法 相對(duì)于M-LWDF 算 法 降 低 約 5%；LIN-LDWF 算法 平 均 時(shí) 延 接 近 于M-LWDF，因?yàn)槠洳捎镁€性因子，所以時(shí)延改進(jìn)不明顯，由于指數(shù)因子的引進(jìn)，長(zhǎng)時(shí)延的數(shù)據(jù)分組優(yōu)先級(jí)被提高，MT-LWDF 算法降低時(shí)延的同時(shí)也在很大程度上減少了拖尾現(xiàn)象。

圖4 扇區(qū)速率與系統(tǒng)平均時(shí)延隨參數(shù) β 變化關(guān)系

圖5 7種調(diào)度算法下的系統(tǒng)速率和時(shí)延均值

從圖 6 可以看出，在非滿負(fù) 載情況下，EDF 算法速率分布范圍最小，BCQI算法速率分布最大，說明這兩種算法的用戶公平性一個(gè)最高一個(gè)最低，其他 5種算法速率分布差異性較小，公平性處于兩者之間。

圖6 7種調(diào)度算法下 UE 平均速率 CDF 曲線

時(shí)延分布是評(píng)價(jià)用戶 QoS 的一個(gè)重要參數(shù)，因此時(shí)延拖尾現(xiàn)象將拉長(zhǎng)時(shí)延分布，降低用戶 QoS。

從圖 7 中可以看出，M-LWDF 算法拖尾比 較長(zhǎng)，超出了 時(shí) 延 上 限 ，而 采 用 線 性 因 子 的 LIN-LWDF 算 法 并 沒 能 解決該現(xiàn)象。MT-LWDF 算法因指數(shù)因子的引進(jìn)有 效降低了拖 尾 現(xiàn) 象 ，將 時(shí) 延 分 布 上 限 由 160 ms 降 低 到 90 ms，拖 尾范 圍 降 低 了 44%， 使 得 MT-LWDF 算 法 時(shí) 延 范 圍 接 近 于EDF 算法，說明該算法在改善拖尾現(xiàn)象的同時(shí)優(yōu)化了系統(tǒng)速率。

圖7 7種 調(diào) 度 算 法 下 UE 平均時(shí)延 CDF 曲 線

圖8 7種 調(diào) 度 算 法 下 UE 最大時(shí)延 CDF 曲 線

除平均時(shí)延分布外，圖 8中的最大時(shí)延分布也能反映拖尾現(xiàn)象。和圖 7 的 UE 平均時(shí)延類似，在最大時(shí)延方面，MT-LWDF 算法降低了 M-LWDF 算法中的拖尾現(xiàn)象。使最大 時(shí) 延 上 限 由 220 ms 降 低 到 110 ms，降 低 了 50%。同 平 均時(shí) 延 一 樣 ，LIN-LWDF 算 法 在 最 大 時(shí) 延 分 布 方 面 沒 能 得 到有效改善。

在前文提到，視頻業(yè)務(wù)理論丟幀率（FLR）為 8‰。從圖 9可 以 看 出 ，EDF、M-LWDF、MT-LWDF、LIN-LWDF 4 種 算 法都能滿足丟幀率要求，而 RR、PF、BCQI算法則不能滿足丟幀率要求。而實(shí)際上，由于不同算法下系統(tǒng)速率不同，實(shí)際傳輸?shù)囊曨l幀數(shù)目也不同，針對(duì)丟幀率沒有很高的研究意義。

5 結(jié)束語

首先，本文重點(diǎn)針對(duì)視頻業(yè)務(wù)延時(shí)問題，在分析了已有調(diào)度算法的基礎(chǔ)上，將系統(tǒng)速率納入算法的考慮范圍，并基于時(shí)延和系統(tǒng)速率提出了具有指數(shù)型非線性權(quán)重的MT-LWDF 算法。

然后，根據(jù)理論分析得出 β的取值范圍為 β∈［10，100］，由 于 MT-LWDF 算法中時(shí) 延 和 速率兩個(gè) 參 數(shù)的隨機(jī) 性 ，無法通過理論計(jì)算推導(dǎo)出最優(yōu) β的解析解，所以采用仿真的方法確定 β=35 時(shí)系統(tǒng)時(shí)延可在局部取得極小值，同時(shí) 系統(tǒng)速率在局部取得極大值。

最后，將 β=35 設(shè)為仿真參數(shù)對(duì) 7 種調(diào)度算法進(jìn)行 仿真得到不同指標(biāo)下的仿真結(jié)果，并根據(jù)這些指標(biāo)將優(yōu)化的MT-LWDF 算 法 與 其 它 算 法 對(duì) 比 分 析 ，得 出 ：MT-LWDF 算法 有 效 降 低 了 拖 尾 現(xiàn) 象 ，將 時(shí) 延 分 布 上 限 由 160 ms 降 低到 90 ms，拖 尾 范 圍 降 低 了 44%，同 時(shí) 將 最 大 時(shí) 延 上 限 由220 ms 降 低 到 110 ms，拖 尾 范 圍 降 低 了 50%。

圖9 7種調(diào)度算法下的系統(tǒng)的丟幀率與總傳輸幀數(shù)

參考文獻(xiàn)：

［1］ 3GPP.Group radio access network-requirements for evolved UTRA （E-UTRA）and evolved UTRAN （E-UTRAN）：3GPP TS 25.913［S］.2007.

［2］ Standardized QCI characteristics.Group services and system aspects-policy and charging control architecture （Release 13）：3GPP TS 23.203［S］.2015.

［3］ RADHAKRISHNAN R，NAYAK A.Cross layer design for efficient video streaming over LTE using scalable video coding［C］／The 2012 IEEE International Conference on Communications（ICC），June 10-15，2012，Ottawa，ON，Canada.New Jersey：IEEE Press，2012：6509-6513.

［4］ 劉 壯.LTE 系 統(tǒng) 中 下 行 鏈 路 的 分 組 調(diào) 度 算 法 研 究 ［D］. 北 京 ：北京郵電大學(xué)，2014. LIU Z.Research on the downlink packet scheduling algorithm in LTE system ［D］.Beijing：Beijing University of Posts and Telecommunications，2014.

［5］ LIU B，TIAN H，XU L L.An efficient downlink packet scheduling algorithm for real time traffics in LTE systems ［C］／／The 2013 Consumer Communications and Networking Conference （CCNC），Jan 11-14，2013，Las Vegas，NV，USA. New Jersey：IEEE Press，2013：364-369.

［6］ CAPOZZI F，PIRO G，GRIECO L A，et al.Downlink packet scheduling in LTE cellular networks：key design issues and a survey［J］.IEEE Communications Surveys&Tutorials，2013（15）：678-700.

［7］ WEI K L，CHIH W H，HUAN K T，et al.A LTE downlink scheduling mechanism with the prediction of packet delay［C］／／The 2015 7th International Conference on Ubiquitous and Future Networks （ICUFN），July 7-10，2015，Sapporo，Japan. ［S. l.：s.n.］，2015：257-262.

［8］ LIU Y L，ZHU D L，WEI M，et al.A QoE-oriented scheduling scheme for HTTP streaming service in LTE system ［C］／2015IEEE Symposium on Computers and Communication （ISCC），July 6-9 ，2015 ，Larnaca ，Cyprus.New Jersey ：IEEE Press，2015：889-894.

［9］ Technical Specification Group Radio Access Network.Physical layer procedures for universal terrestrial radio access （UTRA）（Release 12）：3GPP TR36.213［S］.2015.

［10］3GPP R1-070674.Feasibility study for OFDM for UTRAN enhancement：3GPP TR 25.892（Release 6）［S］.2004.

［11］IEEE 802.16 Task Group m.IEEE 802.16m evaluation methodology document （EMD）［S］.2009.

［12］何金薇，丁璐，劉志敏.LTE 系統(tǒng)級(jí)仿真建模實(shí)現(xiàn)及其優(yōu)化［J］.計(jì) 算 機(jī) 工 程 與 應(yīng) 用 ，2012，48（22）：104-108. HE J W，DING L，LIU Z M.The realization of modeling and optimization ofLTE system-levelsimulation ［J］.Computer Engineering and Application，2012，48（22）：104-108.

A scheduling algorithm for optimizing video traffic

DING Jiarui，LIU Kai，SUN Jie，LIU Zhimin
School of Electronics Engineering and Computer Science，Peking University，Beijing 100871，China

Real-time is an important criterion for evaluation of the real-time video traffic.Most of the existing scheduling algorithms have a wide distribution of user time delay.Firstly，based on the analysis of the existing scheduling algorithms and system rate，an algorithm called MT-LWDF was proposed.Secondly，obtained the range of β after the theoretical analysis，the optimal value of β was got by computer simulation.Then，β was set with the optimal value，the simulation relating to average delay of the system，maximum delay of the users，rate of the system，video frame loss rate and other performance was done.And the results indicate that MT-LWDF algorithm can reduce the distribution of user delay at the same time of optimizing the rate of the system.

LTE，scheduling algorithm，video traffic，simulation

The National High-tech R&D Program （863 Program）（No.2012AA011401）

TN92

：A

10.11959／j.issn.1000-0801.2016109

丁家瑞（1990-），男，北京大學(xué)信息科學(xué)技術(shù)學(xué)院碩士生，主要研究方向?yàn)樾盘?hào)處理、綠色通信和無線通信協(xié)議。

劉凱（1990-），男，北京大學(xué)信息科學(xué)技術(shù)學(xué)院碩士生，主要研究方向?yàn)闊o線通信系統(tǒng)和綠色無線通信節(jié)能技術(shù)。

孫婕（1992-），女，北京大學(xué)信息科學(xué)技術(shù)學(xué)院碩士生，主要研究方向?yàn)闊o線通信系統(tǒng)、無線通信協(xié)議。

劉志敏（1963-），女，北京大學(xué)信息科學(xué)技術(shù)學(xué)院副教授，主要研究方向?yàn)橐苿?dòng)通信、無線資源管理和綠色無線通信節(jié)能技術(shù)。

2016-01-20；

2016-03-09

劉 志 敏 ，liuzm@pku.edu.cn

國(guó)家高技術(shù)研究發(fā)展計(jì)劃（“863”計(jì)劃）基金資助項(xiàng)目（No.2012AA011401）