技術(shù)報(bào)告小生境粒子群優(yōu)化abc支持型qos組播路由機(jī)制課件

1、小生境粒子群優(yōu)化支持型組播路由機(jī)制目錄1引言與相關(guān)工作問(wèn)題分析與建模2組播路由機(jī)制描述3仿真實(shí)現(xiàn)與性能評(píng)價(jià)4結(jié)論及下一步工作52022/7/242引言與相關(guān)工作2022/7/243引言與相關(guān)工作引言 隨著下一代互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展以及大量新型網(wǎng)絡(luò)應(yīng)用的涌現(xiàn)，特別是認(rèn)知網(wǎng)絡(luò)、物聯(lián)網(wǎng)、云計(jì)算和大數(shù)據(jù)等新技術(shù)的相互融合，用戶對(duì)網(wǎng)絡(luò)帶寬的需求以及網(wǎng)絡(luò)用戶數(shù)量都急劇增大。除此以外，網(wǎng)絡(luò)本身所具有的動(dòng)態(tài)性和異構(gòu)性等特點(diǎn)，也使得保證端到端的服務(wù)質(zhì)量和為組播用戶提供最佳接入方式變得很有挑戰(zhàn)性。 當(dāng)前的支持的路由機(jī)制存在著以下三個(gè)問(wèn)題：）網(wǎng)絡(luò)的異構(gòu)和鏈路參數(shù)的不精確性；）用戶只關(guān)心良好的用戶體驗(yàn)，對(duì)于參數(shù)需求難

2、以精確的描述；）網(wǎng)絡(luò)的運(yùn)營(yíng)受市場(chǎng)經(jīng)濟(jì)規(guī)律的支配，網(wǎng)絡(luò)用戶和運(yùn)營(yíng)商的效用互相矛盾，難以保證兩者的公平性。2022/7/244引言與相關(guān)工作相關(guān)工作從路由角度來(lái)看，支持型路由問(wèn)題是在多約束下的優(yōu)化問(wèn)題。對(duì)于此類問(wèn)題常用智能優(yōu)化算法進(jìn)行求解。比如：小生境蟻群算法、粒子群算法、遺傳算法、植物根系趨向性算法、螢火蟲算法等。本文的思想本文運(yùn)用模糊數(shù)學(xué)的方法對(duì)不精確的參數(shù)進(jìn)行了處理；通過(guò)用戶和運(yùn)營(yíng)商博弈，保證用戶和運(yùn)營(yíng)商之間的公平性，建立了多目標(biāo)優(yōu)化的數(shù)學(xué)模型；在聚類小生境粒子群算法基礎(chǔ)上，引入更新機(jī)制，設(shè)計(jì)一種動(dòng)態(tài)解聚類分析小生境粒子群算法（ ，）求解該組播路由問(wèn)題。2022/7/245問(wèn)題分析與建模20

3、22/7/246問(wèn)題分析與建模問(wèn)題分析在給定的網(wǎng)絡(luò)拓?fù)?)中為節(jié)點(diǎn)集，為邊集，即鏈路集合。任意兩個(gè)節(jié)點(diǎn)和之間可能存在多條邊，表示從節(jié)點(diǎn)到節(jié)點(diǎn)可以使用多條不同的通信鏈路轉(zhuǎn)發(fā)分組，如右圖所示。支持的組播路由問(wèn)題就可以轉(zhuǎn)化為，在網(wǎng)絡(luò)拓?fù)渲袑ふ乙豢脻M足組播用戶給定的需求且能保證對(duì)用戶和運(yùn)營(yíng)商公平的組播樹。2022/7/247問(wèn)題分析與建模建立模型. 刻畫組播請(qǐng)求參數(shù)和網(wǎng)絡(luò)的鏈路參數(shù)在網(wǎng)絡(luò)中組播路由的請(qǐng)求可以刻畫為元組 ，其中 為組播的源節(jié)點(diǎn)， 為組播目的節(jié)點(diǎn)集； 分別為請(qǐng)求的帶寬、延遲、延遲抖動(dòng)和出錯(cuò)率的約束區(qū)間。為簡(jiǎn)化問(wèn)題，對(duì)于節(jié)點(diǎn)的抖動(dòng)和處理時(shí)延，將其歸約到下游的邊，這樣對(duì)于每條鏈路就可以給出其帶

4、寬、延遲、延遲抖動(dòng)、出錯(cuò)率的保證區(qū)間。2022/7/248問(wèn)題分析與建模. 運(yùn)用模糊數(shù)學(xué)和博弈的方法刻畫組播樹可信度、用戶效用和運(yùn)營(yíng)商效用對(duì)于可信度的計(jì)算，首先需要確定一個(gè)組播用戶到源節(jié)點(diǎn)的端到端的帶寬、延遲、延遲抖動(dòng)和出錯(cuò)率的可信度，然后進(jìn)行加權(quán)求和，最終組播樹的可信度取決于源節(jié)點(diǎn)到所有組播用戶的路徑中可信度的最小值。對(duì)于用戶效用和運(yùn)營(yíng)商效用的計(jì)算，應(yīng)以滿足用戶需求為前提。對(duì)不同的參數(shù)需求區(qū)間，比如帶寬，首先確定其滿意度為低、中、高的三種隸屬函數(shù)，確定其隸屬度，計(jì)算用戶的綜合滿意度；然后分別制定用戶和運(yùn)營(yíng)商的策略集，結(jié)合滿意度和用戶偏好計(jì)算鏈路在不同策略對(duì)下用戶和運(yùn)營(yíng)商的效用 ，構(gòu)成效應(yīng)矩陣

5、，其中效應(yīng)矩陣的元素 是用戶和運(yùn)營(yíng)商在對(duì)應(yīng)策略對(duì)下效用對(duì) 。2022/7/249問(wèn)題分析與建模比較矩陣中的所有元素值，找到其中的非支配解集（最優(yōu)解集）。如果非支配解集中元素唯一，該策略對(duì)就是用戶和運(yùn)營(yíng)商博弈的納什均衡，選擇該非支配解；否則，根據(jù)式（）計(jì)算其優(yōu)先級(jí)，選擇優(yōu)先級(jí)最高的非支配解。最后將選出的非支配解對(duì)應(yīng)的策略對(duì)作為最佳策略對(duì)，其中 為偏向系數(shù)：（）2022/7/2410問(wèn)題分析與建模組播樹的可信度如式（）所示，其中表示源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑的可信度；組播樹上用戶效用如式（）所示 表示到的路徑，表示路徑上的跳數(shù)，表示用戶在鏈路上的效用；組播樹上運(yùn)營(yíng)商效用如式（）所示， 表示運(yùn)營(yíng)商在組播

6、樹上的鏈路數(shù)。（）（）（）2022/7/2411問(wèn)題分析與建模 建立多目標(biāo)模型組播路由問(wèn)題的解實(shí)際上是一棵在滿足需求約束下的包含所有組播目的節(jié)點(diǎn)的樹。為支持總最佳鏈接的特性，考慮用戶偏好、網(wǎng)絡(luò)的異構(gòu)性和公平性建立如下多目標(biāo)模型：（）（）（）（）對(duì)2022/7/2412問(wèn)題分析與建模對(duì)于每一個(gè)滿足約束的組播樹，其適應(yīng)度計(jì)算如式（）所示， 為可信度，為用戶在鏈路上的滿意度， 為上非支配解的最高優(yōu)先級(jí)， 為系數(shù)。（）2022/7/2413組播路由機(jī)制描述2022/7/2414組播路由機(jī)制描述解的構(gòu)成網(wǎng)絡(luò)中有個(gè)目的節(jié)點(diǎn)，先計(jì)算源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的備選路徑集合，假設(shè)有條，將他們編號(hào)為,，那么從每個(gè)節(jié)點(diǎn)

7、的備選路徑集中選擇一條，消除冗余路徑后就可以構(gòu)成一顆組播樹。按目的節(jié)點(diǎn)的順序選擇出的路徑序列 作為解的備選，如果它滿足約束則就是一個(gè)可行解，但不一定最優(yōu)。定義解在四個(gè)目標(biāo)上的取值為一個(gè)維向量，用它表示解的質(zhì)量 。非支配解是指在存在至少一個(gè)維度，在該維度上它優(yōu)于其他的所有解。定義兩個(gè)解之間的距離為，兩個(gè)解質(zhì)量的歐氏距離。如：解與解 的距離如式（）所示。（）2022/7/2415組播路由機(jī)制描述聚類算法定義滿足約束的一個(gè)解為粒子，粒子之間的距離為解之間的距離，然后對(duì)粒子群可以按照右邊所示的算法進(jìn)行聚類。主要思想：設(shè)定聚類半徑，最小聚類規(guī)模，分別以粒子群中的每一個(gè)粒子為聚類中心進(jìn)行聚類，同時(shí)記錄每個(gè)

8、粒子能形成的聚類規(guī)模，每次輸出最大的一個(gè)子類，同時(shí)把輸出后的子類中的粒子從當(dāng)前種群中排除。不斷迭代，直到無(wú)法形成新的子類。2022/7/2416組播路由機(jī)制描述算法設(shè)維空間中的粒子 在時(shí)刻的位置為 ，速度為 ，同理在時(shí)刻的位置為 ，速度為 。 的表示形式如 ， 表示到目的節(jié)點(diǎn)（第維）的單播路徑序號(hào)， 的表示形式為 ，其中 表示粒子 第維上的速度。粒子的速度和位置更新公式如式（）（）所示。（）（）其中 為慣性權(quán)重， 分別為局部認(rèn)知系數(shù)和群體認(rèn)知系數(shù) ， 為隨機(jī)數(shù)。 分別表示當(dāng)前的局部最優(yōu)和全局最優(yōu)解。當(dāng) 時(shí)，稱為局部最優(yōu)（ ），當(dāng) 為全局最優(yōu)（ ）。2022/7/2417組播路由機(jī)制描述動(dòng)態(tài)解聚

9、類分析小生境粒子群算法算法主要分為三部分，首先是初始粒子群的生成及初始解集的構(gòu)建；然后是算法主體的迭代過(guò)程；最后從解集中輸出最優(yōu)解。其中迭代過(guò)程主要包含個(gè)操作：主粒子群的 、聚類、子類的 、邊界的更新，算法步驟如右所示。2022/7/2418仿真實(shí)現(xiàn)與性能評(píng)價(jià)2022/7/2419仿真實(shí)現(xiàn)與性能評(píng)價(jià)仿真實(shí)驗(yàn)部分為評(píng)估本文提出的路由機(jī)制的綜合性能，采用算法作為基準(zhǔn)算法，采用自組織蠕蟲算法（ , ），小生境遺傳算法（ ，）和作為對(duì)比算法進(jìn)行實(shí)例仿真。仿真程序使用如下四個(gè)網(wǎng)絡(luò)拓?fù)洹Ｋ鼈兎謩e基于美國(guó)的，中國(guó)的和，以及根據(jù) 的隨機(jī)圖模型生成的 個(gè)節(jié)點(diǎn)的隨機(jī)拓?fù)?。圖 拓?fù)鋱D圖 拓?fù)鋱D2022/7/2420仿真實(shí)現(xiàn)與性能評(píng)價(jià)圖 拓?fù)鋱D圖 隨機(jī)圖模型仿真實(shí)驗(yàn)部分2022/7/2421仿真實(shí)現(xiàn)與性能評(píng)價(jià)性能評(píng)價(jià)部分評(píng)價(jià)指標(biāo)選取路徑可信度、用戶效用、運(yùn)營(yíng)商效用以及用戶和運(yùn)營(yíng)商綜合效用對(duì)不同的算法機(jī)制進(jìn)行對(duì)比。2022/7/2422仿真實(shí)現(xiàn)與性能評(píng)價(jià)性能評(píng)價(jià)部分2022/7/2423結(jié)論及下一步工作2022/7/2424結(jié)論及下一步工作區(qū)別于當(dāng)前的單目標(biāo)處理組播路由的方式，本文綜合考慮鏈路參數(shù)不精確、用戶需求不精確和用戶與運(yùn)營(yíng)商之間的公平性因素，采用模糊數(shù)學(xué)和博弈論的方法，建立了一個(gè)保證網(wǎng)絡(luò)各方效用達(dá)到共贏的多目標(biāo)組播路由模型。為有效求解該模型，引入動(dòng)態(tài)更新機(jī)制改進(jìn)了小生境粒子群算法。該算法采