自適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)斷邊重連方法設(shè)計(jì)與實(shí)現(xiàn)

董廣智，由 佳，王 戰(zhàn)

(海軍大連艦艇學(xué)院，遼寧 大連 116001)

1 引言

作為近幾年的熱點(diǎn)研究課題，自適應(yīng)網(wǎng)絡(luò)[1]已經(jīng)逐漸演變成一種重要的網(wǎng)絡(luò)模式，憑借靈活性、自適應(yīng)性、可擴(kuò)展性等諸多優(yōu)勢(shì)，在眾多傳統(tǒng)網(wǎng)絡(luò)模式中脫穎而出。由于該網(wǎng)絡(luò)模式下各節(jié)點(diǎn)既是服務(wù)器也是客戶機(jī)，其拓?fù)浣Y(jié)構(gòu)因自適應(yīng)調(diào)整而始終處于動(dòng)態(tài)變化中，并在各個(gè)節(jié)點(diǎn)上實(shí)現(xiàn)數(shù)據(jù)、帶寬、儲(chǔ)存空間等資源的共享。自適應(yīng)網(wǎng)絡(luò)的獨(dú)特屬性令處理能力較差的節(jié)點(diǎn)在高負(fù)載狀態(tài)下，偶有擁塞現(xiàn)象[2]發(fā)生，而強(qiáng)處理能力節(jié)點(diǎn)則大部分處于空閑狀態(tài)，這種情況使網(wǎng)絡(luò)搜索性能受到嚴(yán)重影響。

基于上述研究背景，提出一種自適應(yīng)網(wǎng)絡(luò)斷邊重連方法，通過充分利用節(jié)點(diǎn)的處理能力，斷開當(dāng)前的網(wǎng)絡(luò)連邊，重新與另一個(gè)鄰域節(jié)點(diǎn)相連，來平衡網(wǎng)絡(luò)負(fù)載。為應(yīng)對(duì)自適應(yīng)網(wǎng)絡(luò)的靈活性與自適應(yīng)性，將在網(wǎng)絡(luò)各主機(jī)間遷移不受限的移動(dòng)agent作為斷邊重連的技術(shù)支撐，構(gòu)建適用于自適應(yīng)網(wǎng)絡(luò)的移動(dòng)agent基本框架，用其動(dòng)態(tài)變化的物理位置抑制網(wǎng)絡(luò)的自適應(yīng)屬性；利用移動(dòng)agent的移動(dòng)性與自主性，賦予節(jié)點(diǎn)在主機(jī)環(huán)境中不斷移動(dòng)的能力與自身狀態(tài)保持的能力，為節(jié)點(diǎn)提供斷邊重連的決策依據(jù)，令網(wǎng)絡(luò)分流更高效；引用極小連通支配集，有助于降低冗余轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)量，提高方法的執(zhí)行速率。

2 適用于自適應(yīng)網(wǎng)絡(luò)的移動(dòng)agent基本框架構(gòu)建

利用移動(dòng)agent及服務(wù)器構(gòu)建出移動(dòng)agent的基本框架，如圖1所示。通過代理傳輸協(xié)議，服務(wù)器不僅讓agent遷移于各個(gè)主機(jī)之間，還實(shí)現(xiàn)了執(zhí)行環(huán)境與服務(wù)接口的供給。在服務(wù)器執(zhí)行agent的過程中，利用代理通信語言對(duì)移動(dòng)agent服務(wù)器的服務(wù)提出訪問申請(qǐng)。

圖1 移動(dòng)agent基本框架

位于移動(dòng)agent基本框架中最外層的是agent與外界的通信載體，即：安全措施庫與代理監(jiān)聽接口。其功能是運(yùn)行agent的安全舉措，屏蔽外界提出的非法訪問請(qǐng)求。

中間層的環(huán)境交互單元采用代理通信語言，令具有不同語言的代理與服務(wù)器保持有效交互與協(xié)調(diào)，使通信內(nèi)容語義不受代理通信語言限制。

工作單元含有執(zhí)行部分及其依據(jù)，其中，知識(shí)庫作為agent的感知部分，具有存儲(chǔ)知識(shí)與工作結(jié)構(gòu)的能力，該知識(shí)與結(jié)構(gòu)由移動(dòng)階段生成；agent運(yùn)行階段的當(dāng)前狀態(tài)即內(nèi)部狀態(tài)，對(duì)agent的工作執(zhí)行有一定的影響，反言之，工作執(zhí)行也對(duì)內(nèi)部狀態(tài)有一定的約束力；agent建立者設(shè)定的站點(diǎn)滯留時(shí)間、工作完成度等條件即約束條件，具有確保agent性能得到充分發(fā)揮的作用；移動(dòng)agent路由的決定性因素為路由方案[3]，一般分為靜態(tài)服務(wù)設(shè)施列表與規(guī)則下動(dòng)態(tài)路由兩種，動(dòng)靜態(tài)路由方案的選擇依據(jù)是工作求解階段的屬性。

根據(jù)移動(dòng)agent基本框架設(shè)計(jì)出以下幾種移動(dòng)agent服務(wù)器的基本服務(wù)：

1)應(yīng)用服務(wù)：針對(duì)比特任務(wù)提供一種服務(wù)接口；

2)安全服務(wù)：形成agent安全運(yùn)行環(huán)境；

3)事件服務(wù)：利用代理傳輸與通信協(xié)議，在各個(gè)agent之間相互發(fā)送事件；

4)目錄服務(wù)：提供agent位置坐標(biāo)，得到路由方案；

5)周期服務(wù)：建立agent、移動(dòng)agent、序列化存儲(chǔ)agent、分配agent運(yùn)行環(huán)境。

3 自適應(yīng)網(wǎng)絡(luò)框架及矢量化處理策略

以獨(dú)立集的最小連通支配集[4]為基礎(chǔ)，架構(gòu)自適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)，如圖2所示，各節(jié)點(diǎn)根據(jù)最大獨(dú)立集下最小連通支配集算法[5]，創(chuàng)建對(duì)應(yīng)鄰域節(jié)點(diǎn)的信息列表。

圖2 自適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)示意圖

為降低網(wǎng)絡(luò)復(fù)雜度，將節(jié)點(diǎn)的局部鄰域信息縮小于兩跳的界限中。此前需先利用極大獨(dú)立集的最小連通支配集算法，組建節(jié)點(diǎn)集。具體過程為：

首先，根據(jù)鄰域節(jié)點(diǎn)信息選取極小元，采用所選的獨(dú)立點(diǎn)架構(gòu)最大獨(dú)立集；

其次，根據(jù)所選支配點(diǎn)，得到極小連通支配集。

該網(wǎng)絡(luò)全部節(jié)點(diǎn)集V的組成部分是極小連通支配集Vp與非支配集Vc，其中，支配節(jié)點(diǎn)Vp幫助傳輸消息。

為保證自適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)能夠通過sink節(jié)點(diǎn)實(shí)現(xiàn)廣播功能，設(shè)計(jì)一種令各支配點(diǎn)與sink節(jié)點(diǎn)的間距得以存儲(chǔ)的廣播算法。該算法的設(shè)計(jì)理論依據(jù)為：對(duì)于極大獨(dú)立集的極小連通支配集，利用sink節(jié)點(diǎn)實(shí)施廣播操作，矢量化處理該自適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)。

假定sink節(jié)點(diǎn)的向量值是0，即id(sink).Dsink=0，某節(jié)點(diǎn)vi的向量值是Dvi=1，2，…，N，其原始向量值為id(vi).Dvi=∞，則滿足如下兩個(gè)條件：

1)節(jié)點(diǎn)vj發(fā)送信息massage(id(vj).Dvj，type)給節(jié)點(diǎn)vi，當(dāng)節(jié)點(diǎn)vi的向量值Dvi不小于節(jié)點(diǎn)vj的向量值Dvj時(shí)，Dvi=Dvj+1成立；反之，則告知鄰域節(jié)點(diǎn)vs；

2)當(dāng)節(jié)點(diǎn)vi屬于支配集Vp時(shí)，需節(jié)點(diǎn)vi把廣播轉(zhuǎn)發(fā)出去；反之，當(dāng)其屬于非支配集Vc時(shí)，只有發(fā)現(xiàn)信息中的向量值存在變化，方可告知鄰域節(jié)點(diǎn)。

4 移動(dòng)agent下自適應(yīng)網(wǎng)絡(luò)斷邊重連

4.1 斷邊重連實(shí)現(xiàn)步驟

利用構(gòu)建的移動(dòng)agent基本框架結(jié)構(gòu)，按照如下流程完成自適應(yīng)網(wǎng)絡(luò)的斷邊重連：

(1)

(2)

其中，網(wǎng)絡(luò)平均度值可近似為p*N。

2)自適應(yīng)網(wǎng)絡(luò)連邊。斷邊重連方法的實(shí)現(xiàn)步驟如下所述：

1)以網(wǎng)絡(luò)內(nèi)任意一條連邊(v1，v2)為目標(biāo)對(duì)象；

2)隨機(jī)設(shè)定節(jié)點(diǎn)v1、v2為定點(diǎn)與動(dòng)點(diǎn)，若定點(diǎn)是節(jié)點(diǎn)v1，則動(dòng)點(diǎn)v2的度值需滿足不小于2的條件；

3)針對(duì)節(jié)點(diǎn)v3任意選擇其鄰域的一個(gè)節(jié)點(diǎn)v4。其中，節(jié)點(diǎn)v3需有別于節(jié)點(diǎn)v1、v2，且鄰域節(jié)點(diǎn)數(shù)量不少于一個(gè)；節(jié)點(diǎn)v4需有別于節(jié)點(diǎn)v1或者v2；

4)將初選連邊(v1，v2)斷開后，在連邊節(jié)點(diǎn)v1、v4間添一條連邊，實(shí)現(xiàn)自適應(yīng)網(wǎng)絡(luò)的斷邊重連。

4.2 網(wǎng)絡(luò)節(jié)點(diǎn)度值分析

由于斷邊重連的有效實(shí)現(xiàn)依據(jù)為節(jié)點(diǎn)度[6]，因此，需深入分析自適應(yīng)網(wǎng)絡(luò)的節(jié)點(diǎn)度情況。

假設(shè)網(wǎng)絡(luò)演化時(shí)間尺度[7]是t，演化完成后，k度值的節(jié)點(diǎn)抽選概率是p(k，t)，則時(shí)間尺度從t-1至t的斷邊重連階段里，斷開連邊(v1，v2)、連接連邊(v1，v4)的斷邊重連操作會(huì)導(dǎo)致度值k發(fā)生變化，使抽選概率轉(zhuǎn)變?yōu)閜(x，t)，變化的度值就是節(jié)點(diǎn)v2的降幅與節(jié)點(diǎn)v4的增幅，詳細(xì)情況如下所述：

1)節(jié)點(diǎn)v2度值降幅：該變化幅度包含k+1降至k與k降至k-1兩部分。假設(shè)節(jié)點(diǎn)v2的度值是k，自適應(yīng)網(wǎng)絡(luò)的連邊個(gè)數(shù)是M，則該節(jié)點(diǎn)的隨機(jī)選取概率是q1(k)，計(jì)算公式如下所示

(3)

2)節(jié)點(diǎn)v4度值增幅：該變化幅度包含k-1增至k與k增至k+1兩部分。同理得出下列節(jié)點(diǎn)v4的隨機(jī)鄰域節(jié)點(diǎn)度分布函數(shù)表達(dá)式

(4)

其中，自適應(yīng)網(wǎng)絡(luò)的度分布函數(shù)[8]為p(k)。

由此推導(dǎo)出時(shí)間尺度t演化終止后的網(wǎng)絡(luò)主方程式，如下所示

p(k，t+1)-p(k，t)=Wv2+Wv4

(5)

其中，節(jié)點(diǎn)v2的降幅是Wv2，節(jié)點(diǎn)v4的增幅是Wv4。

若時(shí)間尺度趨近于∞，經(jīng)不斷重復(fù)后，網(wǎng)絡(luò)與鄰域節(jié)點(diǎn)的度分布函數(shù)p(k)逐漸平穩(wěn)，此時(shí)有p(k，t+1)-p(k，t)=0，演算出主方程式的最終表達(dá)式，如下所示

(k+1)p(k+1)-kp(k)

-kNp2(k)+(k-1)Np2(k-1)=0

(6)

根據(jù)該式可以看出，0度值的度分布函數(shù)結(jié)果也是0，即

p(0)=0

(7)

當(dāng)度值k取值為1時(shí)，有下列表達(dá)式

(8)

當(dāng)度值k大于1時(shí)，有下列迭代方程組

(9)

對(duì)上列方程組求和，推導(dǎo)出下列表達(dá)式

(k+1)p(k+1)-kNp2(k)-2p(2)+Np2(1)=0

(10)

將0度值的度分布函數(shù)結(jié)果代入上式，得出如下公式

(11)

5 自適應(yīng)網(wǎng)絡(luò)斷邊重連實(shí)驗(yàn)分析

在構(gòu)建的自適應(yīng)網(wǎng)絡(luò)框架中添加13000個(gè)節(jié)點(diǎn)，各節(jié)點(diǎn)均存在5個(gè)原始鄰域節(jié)點(diǎn)(即每個(gè)節(jié)點(diǎn)每次重連時(shí)的最多節(jié)點(diǎn)數(shù)量為5)，其能力分布情況由每個(gè)節(jié)點(diǎn)上的Gnutella客戶端軟件獲得，如表1所示。

表1 五個(gè)原始鄰域節(jié)點(diǎn)能力分布

5.1 基于集聚系數(shù)的自適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)集中程度分析

采用集聚系數(shù)反映所建網(wǎng)絡(luò)結(jié)構(gòu)的集中度，探討該網(wǎng)絡(luò)是否具備參與斷邊重連實(shí)驗(yàn)的可行性。整個(gè)網(wǎng)絡(luò)的集聚系數(shù)均值計(jì)算公式如下所示，網(wǎng)絡(luò)集中程度隨著系數(shù)值的增加而提升

(12)

其中，cvi表示節(jié)點(diǎn)vi的集聚系數(shù)(i=1，2，…，N)，由下式解得

(13)

其中，連接該節(jié)點(diǎn)的閉合三角形有svi個(gè)，其度值是kvi。

圖3為自適應(yīng)網(wǎng)絡(luò)集聚系數(shù)示意圖。

圖3 自適應(yīng)網(wǎng)絡(luò)集聚系數(shù)示意圖

根據(jù)圖3所示的網(wǎng)絡(luò)集聚系數(shù)變化形式可以看出：斷邊重連概率越大，該移動(dòng)agent自適應(yīng)網(wǎng)絡(luò)的集中性越強(qiáng)，且始終未出現(xiàn)較大波動(dòng)；但當(dāng)斷邊重連概率較小時(shí)，網(wǎng)絡(luò)集中度也呈現(xiàn)出較高水平。這說明構(gòu)建的自適應(yīng)網(wǎng)絡(luò)基于獨(dú)立集的最小連通支配集，大幅降低了網(wǎng)絡(luò)復(fù)雜度，因?yàn)槔胹ink節(jié)點(diǎn)實(shí)施廣播操作，矢量化處理了自適應(yīng)網(wǎng)絡(luò)的結(jié)構(gòu)，所以即便是在小概率斷邊重連的情況下，依然具有較好的網(wǎng)絡(luò)集中度，有效地抑制了網(wǎng)絡(luò)隨機(jī)性，能夠相對(duì)可靠地對(duì)其斷邊重連的效果作出檢驗(yàn)。

5.2 基于網(wǎng)絡(luò)負(fù)載與度關(guān)聯(lián)的網(wǎng)絡(luò)斷邊重連效果分析

該實(shí)驗(yàn)環(huán)節(jié)采用網(wǎng)絡(luò)負(fù)載與度關(guān)聯(lián)兩種指標(biāo)[9]，描述不同斷邊概率下本文方法斷邊重連的有效性與準(zhǔn)確性。網(wǎng)絡(luò)負(fù)載與度關(guān)聯(lián)指標(biāo)的計(jì)算公式分別如下所示，其中，網(wǎng)絡(luò)飽和度隨著負(fù)載數(shù)值的減小而下降，有效性越好；度關(guān)聯(lián)指標(biāo)數(shù)值越大，關(guān)聯(lián)度越高，準(zhǔn)確度越理想

(14)

(15)

式中，G表示網(wǎng)絡(luò)吞吐值，d表示網(wǎng)絡(luò)帶寬；連邊vi的兩個(gè)節(jié)點(diǎn)度值分別是kvi、kvi+1。

圖4為網(wǎng)絡(luò)負(fù)載均衡效果示意圖。

圖4 網(wǎng)絡(luò)負(fù)載均衡效果示意圖

根據(jù)圖4所示的網(wǎng)絡(luò)負(fù)載變化情況可以看出：隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的持續(xù)增加，網(wǎng)絡(luò)負(fù)載指標(biāo)值大幅下降，證明該方法基于構(gòu)建的移動(dòng)agent基本結(jié)構(gòu)，利用最大獨(dú)立集下最小連通支配集算法，將節(jié)點(diǎn)的局部鄰域信息成功縮小于兩跳的界限中，故具有一定的有效性；當(dāng)節(jié)點(diǎn)數(shù)量降至一定程度時(shí)，網(wǎng)絡(luò)負(fù)載指標(biāo)值逐漸趨于平緩且略有上升趨勢(shì)，說明過多的節(jié)點(diǎn)個(gè)數(shù)會(huì)對(duì)agent移動(dòng)路由的動(dòng)靜態(tài)方案選取產(chǎn)生較大負(fù)擔(dān)，導(dǎo)致負(fù)載均衡操作失效，這點(diǎn)將在今后工作中繼續(xù)深入探究。

圖5為度關(guān)聯(lián)示意圖。

圖5 度關(guān)聯(lián)示意圖

由圖5所示的度關(guān)聯(lián)變化形式可以看出，在網(wǎng)絡(luò)連邊數(shù)量不斷提高的同時(shí)，度關(guān)聯(lián)指標(biāo)值呈線性上揚(yáng)趨勢(shì)。這是因?yàn)楸疚姆椒ǜ鶕?jù)度分布函數(shù)與隨機(jī)鄰域節(jié)點(diǎn)的度分布函數(shù)，深入分析了自適應(yīng)網(wǎng)絡(luò)的節(jié)點(diǎn)度值，所以才能夠在兩個(gè)具有高關(guān)聯(lián)度的節(jié)點(diǎn)間實(shí)現(xiàn)重連。

6 結(jié)論

復(fù)雜網(wǎng)絡(luò)理論迅猛進(jìn)步，橫跨學(xué)科的網(wǎng)絡(luò)研究范圍日益拓寬，這對(duì)復(fù)雜網(wǎng)絡(luò)的探索難度提出了前所未有的挑戰(zhàn)。隨著計(jì)算機(jī)技術(shù)的飛躍式發(fā)展，復(fù)雜性科學(xué)日漸興起，網(wǎng)絡(luò)分析的探究方向更是逐漸演變成應(yīng)用領(lǐng)域中新的里程碑。移動(dòng)agent模型憑借其自身優(yōu)勢(shì)，能夠較好地描述個(gè)體之間、網(wǎng)絡(luò)之間的互動(dòng)關(guān)系，故基于此，提出一種自適應(yīng)網(wǎng)絡(luò)的斷邊重連方法。雖然該方法已經(jīng)初見研究雛形，但仍需從以下幾個(gè)方面做進(jìn)一步優(yōu)化：為滿足當(dāng)前即時(shí)性需求，需嘗試采用一些主流的智能算法，并將改進(jìn)計(jì)算量(即自適應(yīng)網(wǎng)絡(luò)的快速運(yùn)行)作為下一個(gè)討論課題，加快斷邊重連的執(zhí)行速度；應(yīng)利用社團(tuán)結(jié)構(gòu)劃分算法來改善自適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)，為斷邊重連的理想實(shí)現(xiàn)奠定基礎(chǔ)。在今天的技術(shù)發(fā)展環(huán)境下，本文方法經(jīng)過不斷改進(jìn)與創(chuàng)新，有望成為計(jì)算機(jī)領(lǐng)域中均衡網(wǎng)絡(luò)負(fù)載的一種有效手段，打破負(fù)載給自適應(yīng)網(wǎng)絡(luò)帶來的局限性。