小生境粒子群優(yōu)化ABC支持型QoS組播路由機制課件知識課件

小生境粒子群優(yōu)化ABC支持型

QoS組播路由機制

作者：馬連博胡書培王興偉黃敏

主講人：胡書培

單位：東北大學(xué)目錄1引言與相關(guān)工作問題分析與建模2組播路由機制描述3仿真實現(xiàn)與性能評價4結(jié)論及下一步工作52024/9/262引言與相關(guān)工作2024/9/263引言與相關(guān)工作引言

隨著下一代互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展以及大量新型網(wǎng)絡(luò)應(yīng)用的涌現(xiàn)，特別是認知網(wǎng)絡(luò)、物聯(lián)網(wǎng)、云計算和大數(shù)據(jù)等新技術(shù)的相互融合，用戶對網(wǎng)絡(luò)帶寬的需求以及網(wǎng)絡(luò)用戶數(shù)量都急劇增大。除此以外，網(wǎng)絡(luò)本身所具有的動態(tài)性和異構(gòu)性等特點，也使得保證端到端的服務(wù)質(zhì)量和為組播用戶提供最佳接入方式變得很有挑戰(zhàn)性。

當前的ABC支持的路由機制存在著以下三個問題：1）網(wǎng)絡(luò)的異構(gòu)和鏈路參數(shù)的不精確性；2）用戶只關(guān)心良好的用戶體驗，對于QoS參數(shù)需求難以精確的描述；3）網(wǎng)絡(luò)的運營受市場經(jīng)濟規(guī)律的支配，網(wǎng)絡(luò)用戶和運營商的效用互相矛盾，難以保證兩者的公平性。2024/9/264問題分析與建模2024/9/266問題分析與建模問題分析在給定的網(wǎng)絡(luò)拓撲G(V,E)中V為節(jié)點集，E為邊集，即鏈路集合。任意兩個節(jié)點和之間可能存在多條邊，表示從節(jié)點到節(jié)點可以使用多條不同的通信鏈路轉(zhuǎn)發(fā)分組，如右圖所示。ABC支持的組播路由問題就可以轉(zhuǎn)化為，在網(wǎng)絡(luò)拓撲中尋找一棵滿足組播用戶給定的QoS需求且能保證對用戶和運營商公平的組播樹。2024/9/267問題分析與建模建立模型1.刻畫組播QoS請求參數(shù)和網(wǎng)絡(luò)的鏈路參數(shù)在網(wǎng)絡(luò)中組播路由的QoS請求可以刻畫為6元組，其中

為組播的源節(jié)點，為組播目的節(jié)點集；分別為QoS請求的帶寬、延遲、延遲抖動和出錯率的約束區(qū)間。為簡化問題，對于節(jié)點的抖動和處理時延，將其歸約到下游的邊，這樣對于每條鏈路就可以給出其帶寬、延遲、延遲抖動、出錯率的保證區(qū)間。2024/9/268問題分析與建模2.運用模糊數(shù)學(xué)和博弈的方法刻畫組播樹可信度、用戶效用和運營商效用對于可信度的計算，首先需要確定一個組播用戶到源節(jié)點的端到端的帶寬、延遲、延遲抖動和出錯率的可信度，然后進行加權(quán)求和，最終組播樹的可信度取決于源節(jié)點到所有組播用戶的路徑中可信度的最小值。對于用戶效用和運營商效用的計算，應(yīng)以滿足用戶QoS需求為前提。對不同的參數(shù)QoS需求區(qū)間，比如帶寬，首先確定其滿意度為低、中、高的三種隸屬函數(shù)，確定其隸屬度，計算用戶的綜合滿意度；然后分別制定用戶和運營商的策略集，結(jié)合滿意度和用戶偏好計算鏈路在不同策略對下用戶和運營商的效用，構(gòu)成效應(yīng)矩陣Q，其中效應(yīng)矩陣的元素是用戶和運營商在對應(yīng)策略對下效用對。2024/9/269問題分析與建模比較矩陣中的所有元素值，找到其中的非支配解集（Pareto最優(yōu)解集）。如果非支配解集中元素唯一，該策略對就是用戶和運營商博弈的納什均衡，選擇該非支配解；否則，根據(jù)式（1）計算其優(yōu)先級，選擇優(yōu)先級最高的非支配解。最后將選出的非支配解對應(yīng)的策略對作為最佳策略對，其中為偏向系數(shù)：

（1）2024/9/2610問題分析與建模組播樹的可信度如式（2）所示，其中

表示源節(jié)點s到目的節(jié)點d的路徑的可信度；組播樹上用戶效用如式（3）所示表示s到d的路徑，

表示路徑上的跳數(shù)，

表示用戶u在鏈路l上的效用；組播樹上運營商效用如式（4）所示，

表示運營商在組播樹上的鏈路數(shù)。

（2）

（3）

（4）2024/9/2611問題分析與建模建立多目標模型組播路由問題的解實際上是一棵在滿足QoS需求約束下的包含所有組播目的節(jié)點的樹。為支持總最佳鏈接的特性，考慮用戶偏好、網(wǎng)絡(luò)的異構(gòu)性和公平性建立如下多目標模型：

（6）

（7）

（8）

（9）對

2024/9/2612問題分析與建模對于每一個滿足QoS約束的組播樹，其適應(yīng)度計算如式（10）所示，

為可信度，

為用戶在鏈路l上的滿意度，為l上非支配解的最高優(yōu)先級，

為系數(shù)。

（10）2024/9/2613組播路由機制描述2024/9/2614組播路由機制描述解的構(gòu)成網(wǎng)絡(luò)中有m個目的節(jié)點，先計算源節(jié)點到每個目的節(jié)點的備選路徑集合，假設(shè)有n條，將他們編號為1,2,…,n，那么從每個節(jié)點的備選路徑集中選擇一條，消除冗余路徑后就可以構(gòu)成一顆組播樹。按目的節(jié)點的順序選擇出的路徑序列

作為解的備選，如果它滿足QoS約束則就是一個可行解，但不一定最優(yōu)。定義解在四個目標上的取值為一個4維向量，用它表示解的質(zhì)量。非支配解是指在存在至少一個維度，在該維度上它優(yōu)于其他的所有解。定義兩個解之間的距離為，兩個解質(zhì)量的歐氏距離。如：解

與解

的距離如式（11）所示。

（11）2024/9/2615組播路由機制描述聚類算法定義滿足QoS約束的一個解為粒子，粒子之間的距離為解之間的距離，然后對粒子群可以按照右邊所示的算法進行聚類。主要思想：設(shè)定聚類半徑R，最小聚類規(guī)模M，分別以粒子群C中的每一個粒子為聚類中心進行聚類，同時記錄每個粒子能形成的聚類規(guī)模，每次輸出最大的一個子類，同時把輸出后的子類中的粒子從當前種群中排除。不斷迭代，直到無法形成新的子類。2024/9/2616組播路由機制描述PSO算法設(shè)n維空間中的粒子在t時刻的位置為，速度為，同理在t+1時刻的位置為，速度為。的表示形式如，表示s到目的節(jié)點j（第j維）的單播路徑序號，的表示形式為，其中表示粒子第j維上的速度。粒子的速度和位置更新公式如式（12）（13）所示。

（12）

（13）其中為慣性權(quán)重，分別為局部認知系數(shù)和群體認知系數(shù)，為隨機數(shù)。分別表示當前的局部最優(yōu)和全局最優(yōu)解。當

時，稱為局部最優(yōu)PSO（Local-bestPSO），當為全局最優(yōu)PSO（Global-bestPSO）。2024/9/2617組播路由機制描述動態(tài)Pareto解聚類分析小生境粒子群算法算法主要分為三部分，首先是初始粒子群的生成及初始Pareto解集的構(gòu)建；然后是算法主體的迭代過程；最后從Pareto解集中輸出最優(yōu)解。其中迭代過程主要包含4個操作：主粒子群的Local-bestPSO、聚類、子類的Global-bestPSO、Pareto邊界的更新，算法步驟如右所示。2024/9/2618仿真實現(xiàn)與性能評價2024/9/2619仿真實現(xiàn)與性能評價仿真實驗部分為評估本文提出的路由機制的綜合性能，采用SPEA算法作為基準算法，采用自組織蠕蟲算法（Self-OrganizingWormAlgorithm,SOWA），小生境遺傳算法（NichedGeneticAlgorithms，NGA）和作為對比算法進行實例仿真。仿真程序使用如下四個網(wǎng)絡(luò)拓撲。它們分別基于美國的NSFNet，中國的CERNET和CERNET2，以及根據(jù)Waxman的隨機圖模型生成的30個節(jié)點的隨機拓撲。

圖1NSFNet拓撲圖圖2CERNET拓撲圖2024/9/2620仿真實現(xiàn)與性能評價圖3CERNET2拓撲圖圖4隨機圖模型仿真實驗部分2024/9/2621仿真實現(xiàn)與性能評價性能評價部分評價指標選取路徑可信度、用戶效用、運營商效用以及用戶和運營商綜合效用對不同的算法機制進行對比。

2024/9/2622仿真實現(xiàn)與性能評價性能評價部分

2024/9/2623結(jié)論及下一步工作2024/9/2624結(jié)論及下一步工作區(qū)別于當前的單目標處理組播路由的方式，本文綜合考慮鏈路參數(shù)不精確、用戶QoS需求不精確和用戶與運營商之間的公平性因素，采用模糊數(shù)學(xué)和博弈論的方法，建立了一個保證網(wǎng)絡(luò)各方效用達到共贏的多目標組播路由模型。為有效求解該模型，引入