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

趙瑜 鄒雨 陳志坤

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

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

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)志碼：A文章編號(hào)：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ī)劃是一個(gè)復(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ù)建模問題。對(duì)于接入控制策略，需要研究業(yè)務(wù)等級(jí)如何設(shè)定，對(duì)于暫時(shí)未能接入的業(yè)務(wù)，采取拒絕，還是排隊(duì)等待等問題。接入控制問題是一個(gè)多約束條件下的排隊(duì)問題。最后，對(duì)于資源調(diào)控策略，需要研究是否對(duì)不同業(yè)務(wù)類型采用不同的資源分配策略，針對(duì)數(shù)據(jù)速率動(dòng)態(tài)變化的業(yè)務(wù)類型，應(yīng)該靜態(tài)分配還是動(dòng)態(tài)分配資源等問題。資源分配策略是一個(gè)多維度的背包問題。

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

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

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

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

算法步驟如下：

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

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

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

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

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

2仿真實(shí)驗(yàn)驗(yàn)證

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

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

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