融合多維特征的ISP網(wǎng)絡(luò)拓?fù)淦ヅ鋬?yōu)化仿真

高雅娟，王玉峰

(中國(guó)礦業(yè)大學(xué)銀川學(xué)院，寧夏 銀川 750021)

1 引言

ISP發(fā)展之初，將接入服務(wù)作為主體，進(jìn)行ISP網(wǎng)絡(luò)拓?fù)淦ヅ鋬?yōu)化，可以實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的維護(hù)，匯聚鄰近節(jié)點(diǎn)，避免設(shè)備之間的異構(gòu)性與不兼容性，從而給用戶制造穩(wěn)定安全的網(wǎng)絡(luò)環(huán)境，但是緩解網(wǎng)絡(luò)壓力程度較低。

針對(duì)上述問(wèn)題，相關(guān)研究人員給出如下解決方案。文獻(xiàn)[1]在粒子群優(yōu)化基礎(chǔ)上實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)淦ヅ涞膬?yōu)化。該算法結(jié)合SDN方法將全局網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)進(jìn)行可視化處理，利用粒子群優(yōu)化，結(jié)合所處網(wǎng)絡(luò)鏈路資源狀態(tài)等數(shù)據(jù)，將通過(guò)最小優(yōu)化獲取鏈路最大利用率為目標(biāo)進(jìn)行全局優(yōu)先匹配。實(shí)驗(yàn)證明該方法能有效加強(qiáng)網(wǎng)絡(luò)吞吐量。文獻(xiàn)[2]利用最優(yōu)子網(wǎng)的虛擬網(wǎng)絡(luò)映射算法，對(duì)滿足約束條件的虛擬節(jié)點(diǎn)進(jìn)行合并，通過(guò)廣度優(yōu)先搜索方法構(gòu)建子網(wǎng)集合，達(dá)到粗化網(wǎng)絡(luò)拓?fù)淠康?，并將粗化后的虛擬網(wǎng)絡(luò)映射到最佳子網(wǎng)絡(luò)中。這種方法可以減少鏈路映射跳數(shù)，提高網(wǎng)絡(luò)請(qǐng)求接受率。文獻(xiàn)[3]基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，在反饋過(guò)程中計(jì)算AC值，利用鄰接矩陣作為反饋路徑，提出一種可達(dá)中心性算法，更準(zhǔn)確、有效地識(shí)別出重要節(jié)點(diǎn)。

上述優(yōu)化方法雖然一定程度上緩解拓?fù)洳黄ヅ鋯?wèn)題，但是沒(méi)有構(gòu)建明確的拓?fù)湫阅茉u(píng)價(jià)指標(biāo)，無(wú)法精確衡量拓?fù)湟恢滦浴；诖?，本文融合多維特征對(duì)ISP網(wǎng)絡(luò)拓?fù)淦ヅ溥M(jìn)行優(yōu)化。其創(chuàng)新之處在于構(gòu)建合理性能評(píng)價(jià)指標(biāo)，對(duì)ISP網(wǎng)絡(luò)無(wú)向圖進(jìn)行多維特性分析，融合多維特征，通過(guò)節(jié)點(diǎn)加入、退出、失效等過(guò)程，使匹配程度達(dá)到最大化，實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)淦ヅ鋬?yōu)化。

2 ISP網(wǎng)絡(luò)拓?fù)淦ヅ鋬?yōu)化性能指標(biāo)構(gòu)建

現(xiàn)階段，覆蓋網(wǎng)絡(luò)和拓?fù)淦ヅ涑潭鹊闹笜?biāo)主要指伸縮比。其中常用的是路徑伸縮比(PS)與時(shí)延伸縮比(LS)。文本通過(guò)時(shí)延伸縮比表達(dá)網(wǎng)絡(luò)拓?fù)淦ヅ涑潭?，其公式如?/p>

(1)

式中，n代表網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量，i與j為節(jié)點(diǎn)排列序號(hào)，0≤i，j

LS主要表示網(wǎng)絡(luò)時(shí)延方面的匹配程度，只能大概的進(jìn)行反映，無(wú)法得到拓?fù)淦ヅ涞脑敿?xì)特征[4]，因此精準(zhǔn)度較低。但是拓?fù)浣Y(jié)構(gòu)的匹配度對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)的改變與優(yōu)化起到關(guān)鍵作用，如果可以獲得局部匹配特征，不但能提高LS，還能改善整個(gè)ISP網(wǎng)絡(luò)的QOS。因此，本文對(duì)全局拓?fù)淦ヅ浔菺TMR與局部鄰居節(jié)點(diǎn)準(zhǔn)確度LNA兩個(gè)指標(biāo)進(jìn)行定義，從而更準(zhǔn)確的得到拓?fù)淦ヅ涞脑敿?xì)信息。

2.1 全局拓?fù)淦ヅ浔榷x

GTMR用于描述鏈路匹配程度，其描述不同網(wǎng)絡(luò)中相互匹配的鏈路數(shù)量和總鏈路數(shù)量的比值，表達(dá)式如下

(2)

2.2 鄰居節(jié)點(diǎn)準(zhǔn)確度定義

LNA值鄰居節(jié)點(diǎn)之間的匹配比例，關(guān)系式如下所示

(3)

圖1 不同鄰居節(jié)點(diǎn)集合關(guān)系示意圖

假設(shè)h=1，表示統(tǒng)計(jì)節(jié)點(diǎn)的1跳鄰居節(jié)點(diǎn)的準(zhǔn)確度。此時(shí)整個(gè)網(wǎng)絡(luò)中LNAi為1的節(jié)點(diǎn)數(shù)量與覆蓋網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的比值情況通過(guò)下述表達(dá)式獲取

(4)

式中，n為節(jié)點(diǎn)總數(shù)量，n≤i

3 融合多維特性的ISP網(wǎng)絡(luò)拓?fù)淦ヅ鋬?yōu)化

3.1 多維特性分析

本文利用無(wú)向圖G對(duì)多維特征進(jìn)行分析，G能夠通過(guò)對(duì)稱鄰接矩陣A代表[6]。G中的i與j節(jié)點(diǎn)之間存在邊關(guān)聯(lián)性，則Aij=Aji=1，反之Aij=0，Aji=0。一個(gè)圖的特征值其實(shí)是它的鄰接矩陣特征值，因此分析多維特性對(duì)優(yōu)化網(wǎng)路拓?fù)淦ヅ渚哂兄匾獌r(jià)值。

1)譜密度

無(wú)向圖G的譜其實(shí)為該圖鄰接矩陣A的特征密度值[7]，通常表示為ρ(λ)。很對(duì)有限系統(tǒng)來(lái)說(shuō)，ρ(λ)能夠描述為有關(guān)特征值的δ函數(shù)之和

(5)

假設(shè)N→∞時(shí)，它收斂于一個(gè)連續(xù)函數(shù)，這時(shí)λi表示此無(wú)向圖的鄰接矩陣特性值中第i個(gè)特征值。譜密度能夠描述特征值的分布規(guī)律。

現(xiàn)有研究成果說(shuō)明ER隨機(jī)圖的譜密度呈半圓狀，并且底邊區(qū)域呈指數(shù)分布。而無(wú)標(biāo)度圖的譜密度呈對(duì)稱連續(xù)函數(shù)，此函數(shù)的中間部分為三角形，兩邊為冪律分布。

上述分析表明，ISP拓?fù)鋱D不是ER隨機(jī)圖，其屬于一種無(wú)標(biāo)度圖，但又不滿足BA模型的分布。

2)無(wú)符號(hào)拉普拉斯譜

無(wú)向圖G的無(wú)符號(hào)拉普拉斯矩陣|L|的定義式為

|L|=D+A

(6)

式中，D為G的節(jié)點(diǎn)度對(duì)角矩陣，A為鄰接矩陣。無(wú)符號(hào)拉普拉斯譜(SLS)即為|L|特征集合。結(jié)合代數(shù)圖原理說(shuō)明，在單位矩陣的所有線性組合里，無(wú)符號(hào)拉普拉斯譜是劃分不同類型圖效果最顯著的譜，同樣表明，SLS可以描述拓?fù)湫再|(zhì)。

SLS的分布特征值為降序排列，λi的排列順序按照(i-1)(N-1)進(jìn)行規(guī)格化處理[8]。其中，N表示節(jié)點(diǎn)數(shù)量，雖然子圖之間規(guī)模與平均度不盡相同，但是SLS分布情況非常相似，特征值為1的概率都很高，且尾重特性及其相似。通過(guò)冪律擬合結(jié)果得出，所有子圖中全部高于1的特征值和排列順序之間均滿足冪律分布規(guī)則，特征指數(shù)較為相近。

3)規(guī)格化拉普拉斯譜

無(wú)向圖G的規(guī)格化拉普拉斯譜(NLS)矩陣L的定義式為

L=D-1/2×L×D-1/2

(7)

式中，L為G的拉普拉斯矩陣，L=D-A，D與A具有相同含義。NLS屬于L的特征集合，經(jīng)過(guò)規(guī)格化的拉普拉斯特征值區(qū)間為[0，2]，按照升序排列結(jié)果為：λ1≤λ2≤…≤λN。NLS的分布特征比較相似，均呈三個(gè)臺(tái)階狀分布，并且重?cái)?shù)相對(duì)大的特征值位置大致相同。

3.2 匹配優(yōu)化算法實(shí)現(xiàn)

對(duì)上述三個(gè)多維特征進(jìn)行融合，利用面向測(cè)量的方式，優(yōu)化網(wǎng)絡(luò)拓?fù)淦ヅ?。?yōu)化算法的實(shí)現(xiàn)主要包括新節(jié)點(diǎn)加入、節(jié)點(diǎn)失效與退出三個(gè)部分。

圖2 優(yōu)化方法框架圖

3.2.1 節(jié)點(diǎn)加入

(8)

根據(jù)上述條件，判斷出新加入節(jié)點(diǎn)需要符合如下連接條件：

1)網(wǎng)絡(luò)成本歸一化度量

將節(jié)點(diǎn)距離當(dāng)作網(wǎng)絡(luò)成本度量。若節(jié)點(diǎn)nodem+1和節(jié)點(diǎn)nodei發(fā)生連接，其中i∈{1，2，…，m}。兩個(gè)節(jié)點(diǎn)構(gòu)建的連接成本歸一化度量表示為mDi。

則mDi度量越大，構(gòu)建鏈路所花費(fèi)的成本越小。

2)網(wǎng)絡(luò)時(shí)延歸一化度量

將平均最短路徑距離當(dāng)作時(shí)延度量。如果有節(jié)點(diǎn)nodem+1與節(jié)點(diǎn)nodei存在連接時(shí)，且i∈{1，2，…，m}。在連接建立后，網(wǎng)絡(luò)時(shí)延表示為hi，兩個(gè)節(jié)點(diǎn)構(gòu)建的時(shí)延歸一化度量為mHi。此時(shí)度量值mHi越大，網(wǎng)絡(luò)時(shí)延越小。

3)網(wǎng)絡(luò)健壯性歸一化度量

將網(wǎng)絡(luò)遭到一定威脅后仍然正常傳輸?shù)牧髁慨?dāng)作健壯性度量。在nodem+1和nodei兩個(gè)節(jié)點(diǎn)發(fā)生連接后，網(wǎng)絡(luò)受到隨機(jī)攻擊或惡意攻擊后仍可以進(jìn)行正常通信的節(jié)點(diǎn)占比情況表示為ri，節(jié)點(diǎn)nodem+1與nodei的網(wǎng)絡(luò)健壯性歸一化度量表示為mRi，歸一化度量越高，網(wǎng)絡(luò)越健壯。

4)網(wǎng)絡(luò)吞吐量歸一化度量

將網(wǎng)絡(luò)臨界數(shù)據(jù)出現(xiàn)率作為吞吐量度量。假設(shè)在節(jié)點(diǎn)nodem+1與nodei建立聯(lián)系后，網(wǎng)絡(luò)吞吐量用ti表示，則兩個(gè)節(jié)點(diǎn)連接的吞吐量歸一化度量為mTi。此時(shí)，該度量越大吞吐量越高。

5)連接判斷度量measure

如果在優(yōu)化過(guò)程中成本權(quán)重、時(shí)延權(quán)重、健壯性權(quán)重與吞吐量權(quán)重分別表示為：wD、wH、wR與wT，因此新加入節(jié)點(diǎn)nodem+1和存在最大連接度量measure并且沒(méi)有構(gòu)建鏈路的節(jié)點(diǎn)i建立新鏈路。假設(shè)此時(shí)出現(xiàn)很多節(jié)點(diǎn)均滿足該條件，需要隨機(jī)挑選一個(gè)備用節(jié)點(diǎn)與新加入節(jié)點(diǎn)構(gòu)建連接。其中

measure=wDmDi+wHmHi+wRmRi+wTmTi

stwD+wH+wR+wT=1

(9)

其中，wD∈[0，1]，wH∈[0，1]，wR∈[0，1]，wT∈[0，1]。

圖3 節(jié)點(diǎn)加入算法

其中DR存在動(dòng)態(tài)變化性質(zhì)，在算法初始化過(guò)程中，DR=R，此時(shí)建立上圖中(a)所示的示意圖；在DR發(fā)生改變時(shí)，需要對(duì)J與新產(chǎn)生的DR以及子節(jié)點(diǎn)存在的關(guān)系進(jìn)行判斷，結(jié)合三角形邊長(zhǎng)關(guān)系，可以得到三種節(jié)點(diǎn)跳數(shù)發(fā)生的處理情況，從而確定最佳父節(jié)點(diǎn)添加到網(wǎng)絡(luò)中。

3.2.2 節(jié)點(diǎn)退出

為確保整個(gè)ISP網(wǎng)絡(luò)中節(jié)點(diǎn)之間的兼容性、貫通性，維護(hù)鄰居關(guān)系和層次關(guān)系，并且降低網(wǎng)絡(luò)拓?fù)涞木S護(hù)成本，把需要退出節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為動(dòng)態(tài)根節(jié)點(diǎn)形式。在網(wǎng)絡(luò)節(jié)點(diǎn)退出過(guò)程中，必須對(duì)其子節(jié)點(diǎn)與父節(jié)點(diǎn)做合理調(diào)整。假如退出的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，需要將退出消息發(fā)送到父節(jié)點(diǎn)，之后直接退出即可；假設(shè)不屬于葉子節(jié)點(diǎn)，此時(shí)需要先將退出消息傳送給父節(jié)點(diǎn)，并且找到更佳的節(jié)點(diǎn)代替該父節(jié)點(diǎn)。

3.2.3 節(jié)點(diǎn)失效

若節(jié)點(diǎn)發(fā)生失效情況，該節(jié)點(diǎn)不能將消息傳輸給父節(jié)點(diǎn)與子節(jié)點(diǎn)。此時(shí)，需要通過(guò)廣播方式將消息傳送到其它節(jié)點(diǎn)。假設(shè)失效節(jié)點(diǎn)是葉子節(jié)點(diǎn)，利用發(fā)現(xiàn)節(jié)點(diǎn)把失效信息傳遞給父節(jié)點(diǎn)；當(dāng)失效節(jié)點(diǎn)不屬于葉子節(jié)點(diǎn)時(shí)，將失效節(jié)點(diǎn)全部子節(jié)點(diǎn)退出，使其重新回到網(wǎng)絡(luò)中。以此完成了ISP網(wǎng)絡(luò)拓?fù)淦ヅ鋬?yōu)化。

4 仿真研究

為驗(yàn)證所提方法的合理性，本文利用BRITE拓?fù)渖善餍纬闪鶄€(gè)不相同規(guī)模的網(wǎng)絡(luò)拓?fù)洌簕100，200，400，800，1600，3200}，節(jié)點(diǎn)最小度設(shè)為3，且位置符合隨機(jī)分布條件。仿真中，將本文方法與文獻(xiàn)[1]、文獻(xiàn)[2]、文獻(xiàn)[3]方法進(jìn)行對(duì)比，以鄰居節(jié)點(diǎn)準(zhǔn)確度最大值、節(jié)點(diǎn)消耗個(gè)數(shù)與全局拓?fù)淦ヅ浔茸鳛樵u(píng)價(jià)指標(biāo)。

鄰居節(jié)點(diǎn)準(zhǔn)確度最大值對(duì)比測(cè)試獲得的實(shí)驗(yàn)結(jié)果如表1所示：

表1 不同方法優(yōu)化結(jié)果對(duì)比表

從表1中可以看出，本文方法網(wǎng)絡(luò)拓?fù)涞腖AN值匹配程度均高于其它文獻(xiàn)方法。在節(jié)點(diǎn)數(shù)量沒(méi)有超過(guò)800時(shí)，本文方法和對(duì)比方法最大值相差不大，但是超過(guò)800時(shí)，獲得的最大值差距明顯。因此在ISP網(wǎng)絡(luò)中，本文算法拓?fù)淦ヅ鋬?yōu)化算法性能更佳。

節(jié)點(diǎn)消耗個(gè)數(shù)對(duì)比結(jié)果如圖4所示。

圖4 不同優(yōu)化算法維護(hù)開銷對(duì)比圖

從圖4中可以看出本文優(yōu)化算法對(duì)網(wǎng)絡(luò)的維護(hù)開銷低于其它文獻(xiàn)方法，其中，本文方法在節(jié)點(diǎn)規(guī)模為3200時(shí)的維護(hù)代價(jià)最高，為2.3N，而其它文獻(xiàn)方法分別為2.5N、3.2N和4.1N，最高差可達(dá)1.8，說(shuō)明本文方法對(duì)節(jié)點(diǎn)的利用效率較高。

全局拓?fù)淦ヅ浔葘?duì)比測(cè)試結(jié)果如圖5所示。

圖5 不同方法拓?fù)淦ヅ浔葴y(cè)試結(jié)果

由圖5可知，本文方法的節(jié)點(diǎn)返回個(gè)數(shù)一直高于其它文獻(xiàn)方法，說(shuō)明本文方法優(yōu)化后，網(wǎng)絡(luò)拓?fù)洳黄ヅ洮F(xiàn)象減弱，可完成對(duì)節(jié)點(diǎn)位置優(yōu)劣、流量傳輸效率、網(wǎng)絡(luò)延時(shí)、靈敏度等高要求的業(yè)務(wù)。

5 結(jié)論

為改善ISP網(wǎng)絡(luò)拓?fù)洳黄ヅ淙毕?，本文利用融合多維特征方法對(duì)其進(jìn)行匹配優(yōu)化。得出如下結(jié)論：

1)根據(jù)時(shí)延伸縮比表達(dá)網(wǎng)絡(luò)拓?fù)淦ヅ涑潭?，?gòu)建性能評(píng)價(jià)指標(biāo)，在節(jié)點(diǎn)規(guī)模為3200時(shí)的維護(hù)代價(jià)最高，為2.3N，與其它方法最高差可達(dá)1.8，對(duì)節(jié)點(diǎn)的利用效率高達(dá)99%，滿足ISP網(wǎng)絡(luò)拓?fù)淦ヅ湫枨螅?/p>

2)在構(gòu)建性能評(píng)價(jià)指標(biāo)后，對(duì)多維特征進(jìn)行分析，強(qiáng)化多維特征，在節(jié)點(diǎn)數(shù)量超過(guò)800時(shí)，獲得的最大值差距明顯，節(jié)省了維護(hù)開銷，均衡節(jié)點(diǎn)負(fù)載，適用于ISP網(wǎng)絡(luò)。

3)通過(guò)新節(jié)點(diǎn)加入、節(jié)點(diǎn)退出和節(jié)點(diǎn)失效操作實(shí)現(xiàn)拓?fù)淦ヅ鋬?yōu)化的目的?？赏瓿筛哽`敏度、高要求的網(wǎng)絡(luò)業(yè)務(wù)。