基于頻譜系數(shù)和比例公平算法的網(wǎng)絡(luò)調(diào)度優(yōu)化策略

周忠華, 彭智朝

(1. 廣東財(cái)經(jīng)大學(xué) 網(wǎng)絡(luò)信息中心, 廣州 510320； 2. 天津大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 天津 300050)

在無(wú)線網(wǎng)絡(luò)通信系統(tǒng)中, 無(wú)線網(wǎng)絡(luò)資源管理技術(shù)是關(guān)鍵, 其在滿足用戶相關(guān)要求的條件下, 盡可能使資源調(diào)度和優(yōu)化最合理, 以提高無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的資源利用率, 同時(shí)保持用戶的公平性[1].

無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源優(yōu)化調(diào)度是一個(gè)與時(shí)序密切相關(guān)的問題, 其目標(biāo)為每個(gè)用戶在搶奪資源時(shí), 根據(jù)調(diào)度優(yōu)先級(jí)順序建立一個(gè)用戶服務(wù)隊(duì)列, 包括多方面內(nèi)容, 如調(diào)度代價(jià)、 調(diào)度目標(biāo)、 調(diào)度規(guī)則等. 相對(duì)于其他內(nèi)容, 調(diào)度規(guī)則更重要, 也稱為調(diào)度策略, 是無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源優(yōu)化調(diào)度問題的核心[2-4]. 最初的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源優(yōu)化調(diào)度策略基于數(shù)據(jù)分組理論, 首先構(gòu)建用戶服務(wù)質(zhì)量滿意度的相關(guān)約束條件, 然后對(duì)數(shù)據(jù)傳輸時(shí)間進(jìn)行分組, 再根據(jù)分組時(shí)間先后對(duì)數(shù)據(jù)進(jìn)行傳輸, 以獲得更優(yōu)的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源利用率. 由于該策略只考慮數(shù)據(jù)分組, 未考慮用戶之間的差異性, 因此無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源利用率較低, 無(wú)法滿足目前無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的實(shí)際應(yīng)用要求[5-6]. 之后, 人們提出了一種基于用戶分組的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源優(yōu)化調(diào)度策略, 相對(duì)于基于數(shù)據(jù)分組的調(diào)度策略, 其無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源優(yōu)化調(diào)度綜合性能更優(yōu), 因此已成為當(dāng)前的主要研究方向[7]. 在無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源優(yōu)化調(diào)度過程中, 吞吐量和公平性是評(píng)價(jià)調(diào)度結(jié)果的關(guān)鍵指標(biāo), 其中無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的吞吐量描述資源利用效率, 表示單位時(shí)間內(nèi)的數(shù)據(jù)傳輸量, 而公平性主要從用戶角度出發(fā), 即用戶對(duì)服務(wù)質(zhì)量的滿意度, 描述資源利用的公平性, 公平性越高表示用戶獲得的資源越均衡. 因此, 一個(gè)性能優(yōu)異的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源優(yōu)化調(diào)度策略必須考慮吞吐量和公平性. 目前的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源優(yōu)化調(diào)度策略主要分為3類: 第一類為輪詢調(diào)度策略, 假設(shè)無(wú)線網(wǎng)絡(luò)通信系統(tǒng)服務(wù)范圍內(nèi)的調(diào)度優(yōu)先級(jí)相等, 每個(gè)用戶被調(diào)度的概率相同, 使用戶獲得服務(wù)的機(jī)會(huì)均等, 該策略可獲得理論上最優(yōu)的公平性, 但由于其未考慮用戶的信道質(zhì)量差異性, 信道質(zhì)量差的用戶獲得較多的資源, 會(huì)對(duì)無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的吞吐量產(chǎn)生不利影響, 因此無(wú)法有效兼顧公平性和吞吐量的平衡; 第二類為基于最大載干比的調(diào)度策略, 基本工作原理與輪詢調(diào)度策略相反, 其設(shè)置了一個(gè)調(diào)度器, 在每個(gè)周期內(nèi), 盡可能選擇信道質(zhì)量最好的用戶實(shí)現(xiàn)調(diào)度, 使信道質(zhì)量越好的用戶獲得資源的概率越高, 使無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的吞吐量達(dá)到最大, 但信道質(zhì)量差的用戶獲得資源的概率很小, 公平性較差, 缺陷明顯； 第三類為比例公平調(diào)度策略, 其工作原理與前兩類策略不同, 首先為每個(gè)用戶設(shè)置一個(gè)優(yōu)先級(jí), 而用戶優(yōu)先級(jí)包含瞬時(shí)傳輸速率和歷史平均傳輸速率, 以體現(xiàn)用戶信道質(zhì)量, 提高信道質(zhì)量差用戶獲得資源的概率, 克服了輪詢調(diào)度策略只追求公平性和最大載干比調(diào)度策略只追求吞吐量的缺陷, 較好地兼顧了吞吐量和公平性, 已成為無(wú)線網(wǎng)絡(luò)通信系統(tǒng)中最常用的資源優(yōu)化調(diào)度策略. 但在實(shí)際應(yīng)用中, 比例公平調(diào)度策略也存在不足, 如考慮用戶的業(yè)務(wù)量對(duì)資源分配的影響, 以及資源損失嚴(yán)重等[8-11].

為了解決當(dāng)前無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源優(yōu)化調(diào)度過程中存在的問題, 本文設(shè)計(jì)一種基于頻譜系數(shù)和比例公平算法的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度優(yōu)化策略. 首先建立無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的信道模型, 通過自適應(yīng)遺傳算法確定最合理的頻譜系數(shù); 然后根據(jù)比例公平算法將無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的資源分配給用戶, 并針對(duì)傳統(tǒng)比例公平算法的不足進(jìn)行改進(jìn); 最后在MATLAB 2016平臺(tái)上對(duì)無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的性能進(jìn)行分析.

1 無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的信道模型

無(wú)線網(wǎng)絡(luò)通信系統(tǒng)通過信道進(jìn)行信號(hào)傳輸, 因此信號(hào)傳輸質(zhì)量與信道質(zhì)量密切相關(guān), 由于其他因素的干擾, 信號(hào)在信道傳輸過程中, 會(huì)產(chǎn)生一些衰變, 即發(fā)生路徑損耗. 若考慮路徑損耗因素, 則第u個(gè)用戶的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)信道模型為

L(db,u)=K+10αlgdb,u,

(1)

其中:b為無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的中心;db,u為信號(hào)衰變程度. 用戶u的無(wú)線網(wǎng)絡(luò)通信范圍內(nèi)在第t時(shí)刻瞬時(shí)信號(hào)的信噪比計(jì)算公式為

(2)

其中:Ho,u,n(t)為子帶頻率響應(yīng);Pc為功率分配;Iu,n(t)和N0分別為噪聲和相應(yīng)的功率頻譜密度; Δf為子載波帶寬;Iu,n(t)和Δf分別為

(3)

Δf=Bb/Nsc.

(4)

平均功率分配為

(5)

其中FC和FE分別為無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的中心和邊緣區(qū)域[11].

無(wú)線網(wǎng)絡(luò)通信系統(tǒng)有多個(gè)通信中心, 每個(gè)中心有Nsc個(gè)子載波, 無(wú)線網(wǎng)絡(luò)通信系統(tǒng)在第n個(gè)基通信中心數(shù)據(jù)的傳輸速率為

r(γu,n(t))=Nscρ(γu,n(t)).

(6)

由于受外界環(huán)境因素的干擾, 無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的數(shù)據(jù)傳輸可能會(huì)產(chǎn)生一定錯(cuò)誤, 因此真實(shí)的數(shù)據(jù)傳輸速率為

(7)

其中θ(γu,n(t))的確定方式為

(8)

2 傳統(tǒng)比例公平調(diào)度策略

在比例公平調(diào)度策略中, 每個(gè)用戶都有一個(gè)調(diào)度優(yōu)先級(jí), 在第t個(gè)時(shí)隙, 調(diào)度優(yōu)先級(jí)計(jì)算公式為

(9)

其中:ri(t)為第i個(gè)用戶的瞬時(shí)傳輸速率;Ri(t)為第t個(gè)時(shí)隙的平均傳輸速率. 當(dāng)t=1時(shí),Ri(t)=1,pi(t)越大, 則用戶分配到的資源越多; 隨著無(wú)線網(wǎng)絡(luò)通信系統(tǒng)工作時(shí)間的不斷增加,Ri(t)不斷增大,pi(t)隨之變小, 則一些用戶就無(wú)法分配到資源. 在每個(gè)時(shí)隙完成時(shí), 用戶均會(huì)對(duì)Ri(t)進(jìn)行更新處理：

(10)

其中tc表示參考時(shí)隙數(shù). 比例公平調(diào)度策略的工作流程如圖1所示.

圖1 比例公平調(diào)度策略的工作流程Fig.1 Workflow of proportional fairness scheduling strategy

3 無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度優(yōu)化策略設(shè)計(jì)

3.1 確定最優(yōu)頻譜系數(shù)

在無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的資源調(diào)度優(yōu)化策略中, 由于要考慮吞吐量, 而吞吐量與網(wǎng)絡(luò)頻譜系數(shù)密切相關(guān), 因此要選擇最優(yōu)頻譜系數(shù)的信道使用戶接入通信系統(tǒng). 設(shè)Sa表示無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的平均時(shí)延,Su和Sd分別表示上行鏈路和下行鏈路的時(shí)延, 則最優(yōu)頻譜系數(shù)就是盡可能選時(shí)延最小的信道, 計(jì)算公式為

式中相關(guān)參數(shù)見文獻(xiàn)[2]. 由式(11)可見, 其為一個(gè)典型的NP難問題, 常規(guī)算法無(wú)法求解其最優(yōu)解, 因此本文采用自適應(yīng)遺傳算法, 先對(duì)式(11)的最優(yōu)解進(jìn)行搜索, 再根據(jù)最優(yōu)解確定最優(yōu)頻譜系數(shù).

遺傳算法對(duì)式(11)求解的基本思想為： 首先初始化種群, 每個(gè)個(gè)體代表式(11)問題的一個(gè)可行解, 并對(duì)每個(gè)個(gè)體的優(yōu)劣進(jìn)行評(píng)價(jià), 根據(jù)評(píng)價(jià)結(jié)果排序, 選擇較好的個(gè)體直接進(jìn)入下一代種群, 然后將未直接進(jìn)入下一代種群的個(gè)體進(jìn)行自適應(yīng)的交叉、 變異操作, 產(chǎn)生新種群, 同樣對(duì)新種群個(gè)體的優(yōu)劣進(jìn)行評(píng)價(jià), 不斷重復(fù)上述步驟, 直至達(dá)到最大進(jìn)化代數(shù)時(shí), 輸出最優(yōu)個(gè)體, 最后根據(jù)最優(yōu)個(gè)體的解碼結(jié)果得到式(11)的最優(yōu)解.

在算法初期, 自適應(yīng)遺傳算法的交叉概率Pc和變異概率Pm分別為

(12)

(13)

其中:fmax和favg分別表示最大和平均適應(yīng)度值；Pc0和Pm0分別表示Pc和Pm的初值;k為進(jìn)化代數(shù), 應(yīng)滿足

(14)

在算法后期, 自適應(yīng)遺傳算法的交叉概率Pc和變異概率Pm分別為

(15)

(16)

3.2 改進(jìn)的比例公平調(diào)度策略

傳統(tǒng)比例公平調(diào)度策略基于數(shù)據(jù)傳輸?shù)乃矔r(shí)速率和信道質(zhì)量使用戶盡可能多地獲得資源, 增加用戶增益, 是一種長(zhǎng)期公平； 對(duì)于一個(gè)用戶, 尤其對(duì)一些有訪問時(shí)延上限的用戶, 無(wú)法保證其短期公平, 即在其允許訪問時(shí)延范圍內(nèi), 得到有效資源分配, 無(wú)法獲得高質(zhì)量服務(wù), 因此本文提出一種改進(jìn)的比例公平調(diào)度策略. 在無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的資源調(diào)度優(yōu)化時(shí), 考慮用戶所允許的訪問時(shí)延, 則調(diào)度判決計(jì)算公式為

(17)

其中：Ti(t)為第t個(gè)時(shí)隙的吞吐量；λc為最大訪問時(shí)延;λi(t)為到t時(shí)隙已產(chǎn)生的訪問時(shí)延. 已產(chǎn)生訪問時(shí)延的更新公式為

(18)

由式(18)可知, 當(dāng)λi(t)=0時(shí), 第i個(gè)用戶獲得資源調(diào)度機(jī)會(huì). 一個(gè)用戶所允許的訪問時(shí)延值越大, 則其K*越大, 獲得資源調(diào)度概率越大. 由式(17)可見, 改進(jìn)的比例公平調(diào)度策略可有效保證短期服務(wù)時(shí)間, 具有較好的短期公平性, 較好地解決了傳統(tǒng)比例公平調(diào)度策略中存在的短期服務(wù)時(shí)間公平與傳輸速度之間的矛盾.

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)參數(shù)

為了分析本文提出的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度優(yōu)化策略的有效性和優(yōu)越性, 選擇傳統(tǒng)公平比例策略和文獻(xiàn)[1]的資源調(diào)度優(yōu)化策略進(jìn)行對(duì)比實(shí)驗(yàn), 利用MATLAB 2016工具箱實(shí)現(xiàn)仿真測(cè)試, 主要分析短期公平性、 長(zhǎng)期公平性、 吞吐量和吞吐率等性能, 無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的參數(shù)設(shè)置列于表1.

表1 無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的主要仿真參數(shù)Table 1 Main simulation parameters of wireless network communication system

4.2 短期服務(wù)時(shí)間保證分析

短期服務(wù)時(shí)間保證性能通常采用訪問時(shí)延概率進(jìn)行評(píng)價(jià), 訪問時(shí)延概率越小, 表示短期服務(wù)時(shí)間越有保證, 即短期公平性越好, 計(jì)算公式為

(19)

3種無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度優(yōu)化策略的訪問時(shí)延概率變化曲線如圖2所示. 由圖2可見, 隨著訪問時(shí)延的不斷增加, 所有策略的訪問時(shí)延概率均逐漸減小, 即短期公平性越來(lái)越好, 在相同訪問時(shí)延條件下, 本文無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度優(yōu)化策略的訪問時(shí)延概率明顯小于對(duì)比策略, 表明本文策略降低了用戶等待資源分配的時(shí)間, 可更好地保證用戶的短期服務(wù)時(shí)間.

4.3 長(zhǎng)期公平性分析

圖3 不同策略下服務(wù)時(shí)間率的對(duì)比Fig.3 Comparison of service time rates of different strategies

當(dāng)無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的數(shù)量為10時(shí), 3種無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度優(yōu)化策略服務(wù)時(shí)間率(用戶服務(wù)時(shí)間與總服務(wù)時(shí)間之比)的對(duì)比如圖3所示. 由圖3可見, 對(duì)比策略的服務(wù)時(shí)間率變化范圍較大, 說(shuō)明用戶獲得的服務(wù)時(shí)間不公平, 信道質(zhì)量好的用戶占用了更多的服務(wù)時(shí)間, 而本文策略的服務(wù)時(shí)間率變化范圍較小, 很平均, 這主要是由于本文策略考慮了用戶所允許的訪問時(shí)延, 克服了對(duì)比策略存在的缺陷, 改善了用戶服務(wù)時(shí)間的長(zhǎng)期公平性.

4.4 吞吐量增益分析

吞吐量增益值為信道傳輸速率與服務(wù)時(shí)間率的乘積, 不同策略下吞吐量增益的對(duì)比結(jié)果如圖4所示. 由圖4可見, 本文無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度優(yōu)化策略的吞吐量增益值大于1, 而對(duì)比策略的吞吐量增益值均小于1, 這主要是由于對(duì)比策略無(wú)法為訪問時(shí)延受限的用戶提供短期公平性, 而本文策略通過自適應(yīng)遺傳算法確定最優(yōu)頻譜系數(shù), 根據(jù)最優(yōu)頻譜系數(shù)用戶接入的信道, 可實(shí)現(xiàn)良好的信道傳輸速率, 用戶服務(wù)短期公平性更優(yōu), 服務(wù)時(shí)間率更大, 能獲得更優(yōu)的吞吐量增益, 從而驗(yàn)證了本文策略的優(yōu)越性.

4.5 無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的平均吞吐率分析

不同策略下無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的平均吞吐率變化曲線如圖5所示. 由圖5可見, 本文策略的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)平均吞吐率明顯高于對(duì)比策略, 表明本文策略較好地解決了當(dāng)前無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度過程中存在的吞吐問題, 獲得了較好的無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度優(yōu)化結(jié)果.

圖4 不同策略下吞吐量增益的對(duì)比Fig.4 Comparison of throughput gains of different strategies

圖5 不同策略下平均吞吐率的對(duì)比Fig.5 Comparison of average throughput of different strategies

綜上所述, 本文針對(duì)當(dāng)前無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度和優(yōu)化過程中存在的不足, 首先采用自適應(yīng)遺傳算法對(duì)頻譜系數(shù)優(yōu)化的數(shù)學(xué)模型進(jìn)行求解, 找到最優(yōu)頻譜系數(shù)的信道, 使用戶盡可能獲取高質(zhì)量的信道; 然后考慮訪問時(shí)延受限的用戶, 采用改進(jìn)公平比例策略實(shí)現(xiàn)無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的資源調(diào)度和優(yōu)化; 最后通過對(duì)比實(shí)驗(yàn)分析了無(wú)線網(wǎng)絡(luò)通信系統(tǒng)資源調(diào)度策略的綜合性能. 實(shí)驗(yàn)結(jié)果表明, 本文策略可較好地保證用戶服務(wù)的短期和長(zhǎng)期公平性, 提高了用戶的吞吐量增益, 使無(wú)線網(wǎng)絡(luò)通信系統(tǒng)的平均吞吐率得到顯著改善, 具有廣闊的應(yīng)用前景.