一種多約束條件下基于XGBoost的業(yè)務(wù)動態(tài)路徑規(guī)劃方法

趙瑜 鄒雨 陳志坤

摘要：針對多業(yè)務(wù)的動態(tài)路徑規(guī)劃問題，提出綜合考慮用戶級別、業(yè)務(wù)種類、任務(wù)屬性、QoS要求、網(wǎng)絡(luò)資源狀況等多條件，抽象表示為多要素，建立規(guī)劃約束模型，同時在約束圖中標(biāo)識上述要素，獲取實時網(wǎng)絡(luò)資源情況，根據(jù)實時網(wǎng)絡(luò)資源和拓?fù)湟晥D信息，基于XGBoost進(jìn)行最優(yōu)節(jié)點的訓(xùn)練和選擇，在更新后的拓?fù)渖嫌嬎阕顑?yōu)規(guī)劃路徑，在多個約束條件下達(dá)到最優(yōu)規(guī)劃，在資源最大化利用的前提下滿足用戶和業(yè)務(wù)的QoS要求，最后以實例進(jìn)行仿真驗證。提出了一種滿足多約束條件的按需業(yè)務(wù)動態(tài)規(guī)劃方法，設(shè)計了一種求解該問題的啟發(fā)式算法。

關(guān)鍵詞：啟發(fā)式算法；多約束條件；最優(yōu)路徑；規(guī)劃約束模型

中圖分類號：TP18文獻(xiàn)標(biāo)志碼：A文章編號：1008-1739（2022）24-64-5

0引言

隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大和復(fù)雜性的日益增加，網(wǎng)絡(luò)上所承載的業(yè)務(wù)也越來越多樣化且業(yè)務(wù)服務(wù)質(zhì)量（QoS）存在差異化。如何在已有網(wǎng)絡(luò)上盡可能多地滿足多樣化、差異化業(yè)務(wù)需求是需要追尋和亟待解決的問題。業(yè)務(wù)規(guī)劃是一個復(fù)雜且多約束幾近無解的問題，與業(yè)務(wù)規(guī)劃相關(guān)的問題有很多，包括業(yè)務(wù)類型、接入控制策略、資源調(diào)控策略、多徑路由、QoS和QoE等，體現(xiàn)在如下方面：首先，業(yè)務(wù)規(guī)劃需要在多應(yīng)用需求和網(wǎng)絡(luò)能力之間建立映射關(guān)系，即業(yè)務(wù)資源的最佳路徑規(guī)劃。其次，業(yè)務(wù)規(guī)劃的本質(zhì)是特征描述問題，即業(yè)務(wù)建模問題。對于接入控制策略，需要研究業(yè)務(wù)等級如何設(shè)定，對于暫時未能接入的業(yè)務(wù)，采取拒絕，還是排隊等待等問題。接入控制問題是一個多約束條件下的排隊問題。最后，對于資源調(diào)控策略，需要研究是否對不同業(yè)務(wù)類型采用不同的資源分配策略，針對數(shù)據(jù)速率動態(tài)變化的業(yè)務(wù)類型，應(yīng)該靜態(tài)分配還是動態(tài)分配資源等問題。資源分配策略是一個多維度的背包問題。

本文聚焦動態(tài)業(yè)務(wù)最優(yōu)資源路徑規(guī)劃問題，綜合考慮用戶級別、任務(wù)緊急程度、QoS要求、網(wǎng)絡(luò)資源、業(yè)務(wù)屬性要素等多個約束條件，尤其針對網(wǎng)絡(luò)運行過程中的動態(tài)業(yè)務(wù)對網(wǎng)絡(luò)資源的需求問題，提出了一種滿足多約束條件的按需業(yè)務(wù)動態(tài)路徑規(guī)劃方法，在業(yè)務(wù)資源調(diào)控過程中，將人工智能算法XGBoost應(yīng)用于最優(yōu)節(jié)點的選擇和匹配。

1基于多約束條件的業(yè)務(wù)規(guī)劃

業(yè)務(wù)規(guī)劃算法的輸入包括業(yè)務(wù)屬性要素[1-2]（用戶級別、業(yè)務(wù)種類、任務(wù)屬性和QoS要求）和網(wǎng)絡(luò)資源狀況（源節(jié)點、目的節(jié)點、已用資源、可用資源、鏈路帶寬、鏈路狀態(tài)和鏈路利用率），輸出按需業(yè)務(wù)所包括的每一個業(yè)務(wù)的源、目的地之間的最優(yōu)規(guī)劃路徑。

1.1多約束條件下的路徑規(guī)劃算法

算法步驟如下：

①獲取待規(guī)劃的業(yè)務(wù)，屬性要素包括業(yè)務(wù)源和目的，在什么時間（業(yè)務(wù)運行時間）、什么地方（業(yè)務(wù)運行的節(jié)點和鏈路），運行何種業(yè)務(wù)（數(shù)據(jù)、話音、視頻），通常稱為4W，將待規(guī)劃的業(yè)務(wù)加入業(yè)務(wù)集合。

②根據(jù)策略對業(yè)務(wù)集合中的業(yè)務(wù)進(jìn)行優(yōu)先級排序，即按業(yè)務(wù)屬性中的用戶屬性、任務(wù)屬性和所需業(yè)務(wù)資源生成QoS優(yōu)先級要求。QoS優(yōu)先級確定原則：首先比較用戶級別，用戶級別高則對應(yīng)業(yè)務(wù)的優(yōu)先級高；當(dāng)用戶級別一定時，比較任務(wù)重要性，任務(wù)重要性高則業(yè)務(wù)優(yōu)先級高；當(dāng)用戶級別和任務(wù)重要性一定時，比較業(yè)務(wù)類型，融合通信業(yè)務(wù)的優(yōu)先級高于多媒體會議業(yè)務(wù)，多媒體會議業(yè)務(wù)的優(yōu)先級高于多媒體電話業(yè)務(wù)。

③從業(yè)務(wù)集合中取優(yōu)先級最高的業(yè)務(wù)進(jìn)行規(guī)劃，設(shè)業(yè)務(wù)的源和目的分別為和，業(yè)務(wù)所需要的帶寬為。

④建立一個與業(yè)務(wù)關(guān)聯(lián)的約束模型[3-5]=（ ， ），其中，為約束模型的頂點集合，為約束模型的邊集合，為與業(yè)務(wù)關(guān)聯(lián)的約束圖。

目標(biāo)函數(shù)越小，樹的結(jié)構(gòu)越優(yōu)。XGBoost的學(xué)習(xí)過程就是建立最佳決策樹結(jié)構(gòu)的過程，從深度為0的樹開始，采用貪婪策略遍歷所有特征，利用式（6）計算節(jié)點分裂獲得的增益，找到最優(yōu)的特征進(jìn)行分裂生成左右子節(jié)點，重復(fù)上述過程直到條件滿足時迭代停止。

2仿真實驗驗證

以3個不同應(yīng)用需求同時請求資源為例，驗證本文所提的規(guī)劃算法，應(yīng)用需求描述如下：應(yīng)用業(yè)務(wù)包括從1到3的電話業(yè)務(wù)，從2到4的交互式視頻業(yè)務(wù)，從視頻服務(wù)器到1的視頻流業(yè)務(wù)（提供高動態(tài)態(tài)勢）。獲取業(yè)務(wù)屬性要素，電話業(yè)務(wù)所需的帶寬為64 kb/s，交互式業(yè)務(wù)需要的帶寬為1 Mb/s（高清），視流需要的帶寬為2 Mb/s。

將上述3個業(yè)務(wù)加入規(guī)劃集合，基于策略進(jìn)行優(yōu)先級排序，假設(shè)3個業(yè)務(wù)的用戶級別一樣，根據(jù)任務(wù)緊急程度進(jìn)行優(yōu)先級排序：電話業(yè)務(wù)的優(yōu)先級最高，視頻流業(yè)務(wù)的優(yōu)先級次之，交互式視頻的優(yōu)先級最低。

待規(guī)劃的網(wǎng)絡(luò)拓?fù)淙鐖D1所示。