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

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

1 引言

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

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

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

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

圖1 移動agent基本框架

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

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

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

根據(jù)移動agent基本框架設計出以下幾種移動agent服務器的基本服務：

1)應用服務：針對比特任務提供一種服務接口；

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

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

4)目錄服務：提供agent位置坐標，得到路由方案；

5)周期服務：建立agent、移動agent、序列化存儲agent、分配agent運行環(huán)境。

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

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

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

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

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

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

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

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

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

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

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

4 移動agent下自適應網(wǎng)絡斷邊重連

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

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

(1)

(2)

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

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

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

2)隨機設定節(jié)點v1、v2為定點與動點，若定點是節(jié)點v1，則動點v2的度值需滿足不小于2的條件；

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

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

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

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

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

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

(3)

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

(4)

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

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

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

(5)

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

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

(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)

當度值k取值為1時，有下列表達式

(8)

當度值k大于1時，有下列迭代方程組

(9)

對上列方程組求和，推導出下列表達式

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

(10)

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

(11)

5 自適應網(wǎng)絡斷邊重連實驗分析

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

表1 五個原始鄰域節(jié)點能力分布

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

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

(12)

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

(13)

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

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

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

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

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

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

(14)

(15)

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

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

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

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

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

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

由圖5所示的度關(guān)聯(lián)變化形式可以看出，在網(wǎng)絡連邊數(shù)量不斷提高的同時，度關(guān)聯(lián)指標值呈線性上揚趨勢。這是因為本文方法根據(jù)度分布函數(shù)與隨機鄰域節(jié)點的度分布函數(shù)，深入分析了自適應網(wǎng)絡的節(jié)點度值，所以才能夠在兩個具有高關(guān)聯(lián)度的節(jié)點間實現(xiàn)重連。

6 結(jié)論

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