一種基于移動代理的并行路由算法研究

摘 要：提出了一種基于移動代理的并行路由算法，通過對網絡節點間的多條并行鏈路的充分利用，提高網絡帶寬的利用率，減少移動代理從源節點到目的節點的遷移響應時間。仿真實驗結果表明，與著名的蟻群算法和遺傳算法的性能相比，該并行路由算法具有更高的網絡利用率，同時具有更短的平均延遲時間，提高了應用系統的運行效率。

關鍵詞：移動代理; 路由算法; 最短路徑; 仿真

中圖分類號：TP393 文獻標志碼：A

文章編號：10013695(2008)09277803

Research of mobile agentbased sidebyside routing algorithm

DONG Xiangjun1，2， SHI Haoshan1， ZHAO Yonghui1， JIANG Fei1，3

(1.School of Electronic Information， Northwestern Polytechnical University， Xi’an 710072， China; 2.Institute of Scientific Technical Information of EAAF， Beijing 100000， China; 3.Dept. ofthe Fourth， Xi’an Communication College ofPLA， Xi’an 710106， China)

Abstract:This paper mentioned a mobile agentbased sidebyside routing algorithm. By using the sidebyside links between nodes in the network， this algorithm not only increased the bandwidth utilization rate， but also shortened the response time of the mobile agent’s migration from source node to destination node. In the simulation examination， the sidebyside routing algorithm was compared with the famous ant colony optimization and genetic algorithm. The result shows that the sidebyside routing algorithm mentioned bring higher bandwidth utilization rate and shorter response time. It helps the application system run with a higher efficiency.

Key words：mobile agent; routing algorithm; shortest path; simulation

0 引言

在基于移動代理的網絡應用系統中，移動代理的路由問題一直是研究的熱點，如何充分利用移動代理的遷移性和智能性來提高數據的傳輸效率，縮短系統的響應時間，是路由算法需要解決的問題。已有的路由算法有很多，如著名的蟻群算法^[1，2]、遺傳算法^[3，4]以及基于這兩種算法提出的改進算法^[5~8]。這些算法都是基于網絡優化中最優解的求解過程，通過特定的數學推理和算法迭代，從多條路徑中選擇一條最短路徑，使得數據通過該路徑傳輸效率最高。這些算法有一個共同的缺點，就是它們最終得到的路徑是惟一的一條路徑，也就是說除了這條路徑所歷經的網絡鏈路以外，其他的鏈路利用率是零，而且通常未被利用的鏈路比被利用的鏈路多得多，這就意味著應該還有辦法可以更好地利用這些空閑鏈路，使傳輸的數據量分散傳輸，最終在目的節點重組，這樣可以進一步減少數據傳輸的時間。本文提出的并行路由算法就是基于這種想法，通過數學推理得到的路由算法。

1 問題描述

在基于移動代理的網絡應用系統中，網絡環境是由若干網絡節點及節點間的鏈路組成的，因此網絡模型可用有向圖G=(V，A)表示。其中V={v1，v2，…，vn}為圖G的節點集，A={a1，a2，…，am}為圖G的鏈路集。網絡環境中每一條鏈路都有對應的網絡帶寬，稱為鏈路的實際帶寬，而對于那些不直接相連但經過若干個中繼節點相連的節點來說，它們之間的帶寬可用平均帶寬來描述。

定義1 在網絡環境G=（V，A）中的兩個不直接相連但經過若干個中繼節點相連的節點vp與vq之間建立一條虛擬鏈路，對于任意同樣大小的數據量d，當d通過實際鏈路經過多個中繼節點從節點vp到達節點vq的時間與它通過虛擬鏈路到達的時間相等時，該虛擬鏈路的帶寬稱為網絡環境G=(V，A)中節點vp與節點vq之間的平均帶寬。

定理1 設有網絡環境G=(V，A)。其中V={v1，v2，…，vn}為圖G的節點集，A={a1，a2，…，am}為圖G的鏈路集，節點vp(1≤p≤n)與節點vq(1≤q≤n，q≠p)之間有一條路徑，該路徑通過k-1個中繼節點相連，實際帶寬依次為c1，c2，…，ck，則節點vp到節點vq的平均帶寬c為1/(1/c1+1/c2+…+1/ck)。

證明 設有數據量d，根據定義1，有d/c1+d/c2+…+d/ck=d/c，整理得c=1/(1/c1+1/c2+…+1/ck)。證明完畢。

基于以上定義及定理，現在闡述本文提出的并行路由算法所要解決的網絡路由問題。如圖1（a）所示，兩節點間有l條實際路徑；它們可以以虛擬鏈路和對應的平均帶寬來簡化，如（b）所示；傳統的路由算法（遺傳算法、蟻群算法等）都是通過數學計算和迭代，在多條路徑中找出一條最優路徑。本文提出的并行路由算法的思想是將要傳輸的數據量d分解成多份，各自通過不同的路徑傳輸，如（c）所示，以此來提高網絡帶寬的利用率，進而縮短傳輸時間。問題的關鍵在于按照何種比例分解數據量d，才能使傳輸時間達到最短。

2 并行路由算法設計

2.1 算法理論推理

如圖1（c）所示，根據實際網絡環境中的帶寬，如何分解要傳輸的數據量，以達到帶寬的最高利用率和最短傳輸時間，是算法最終要解決的問題。通過以下定理給出算法推理。定理2 設有網絡環境G=(V，A)。其中V={v1，v2，…，vn}為圖G的節點集，A={a1，a2，…，am}為圖G的鏈路集，節點vp(1≤p≤n)與節點vq(1≤q≤n，q≠p)之間存在多條并行路徑，如圖1（c）所示，要傳輸的數據量d被分解成d1，d2，…，dl。則當各分解數據量通過各條鏈路的時間均相等時，整體傳輸時間為最短時間。即

min t=T*=d1/c1=d2/c2=…=dl/cls.t. d1+d2+…+dl=d

(1)

證明 因為節點vp與節點vq之間的多條鏈路是并行相接，所以整體數據的傳輸時間T=max{t1，t2，…，tl}，t1，t2，…，tl分別為各分解數據量通過l條路徑的傳輸時間。要想證明T*=d1/c1=d2/c2=…=dl/cl為min t，只需證明在d1，d2，…，dl中對任意一項作微小的增量Δd(Δd＞0)后，整體數據的傳輸時間T大于T*。

不妨令在d1作調整d1-Δd，根據條件d1+d2+…+dl=d，則至少有一個di(i∈{2，3，…，l})要作相應的調整di+Δd′（0＜Δd′≤Δd)，則

因此，T*=d1/c1=d2/c2=…=dl/cl為min t。證明完畢。

2.2 算法復雜度分析

根據定理2，并行路由算法所表達的數據傳輸最短時間min t的表達式已經給出，由定理2中的式（1）可以得到一個方程組來定量地計算min t以及多條并行路由所分解的數據量占整體數據量的比例。

在式（2）中，d為已知數據，若令d=1，則所求解(d1，d2，…，dl)為各分解數據量占整體數據量的比例。而最短時間min t可依據具體情況下給定的值來計算得到。

從算法的計算復雜度來看，由式（2）可知，求解(d1，d2，…，dl)的過程是求解線性方程組的過程，因此，求解問題為多項式問題（P問題），而所有的P問題都可在多項式時間內求得最優解。綜上所述，本文提出的并行路由算法為多項式時間算法。

23 算法runtime步驟

在基于移動代理的應用系統中，每個網絡節點都有移動代理的運行環境，即移動代理的runtime環境，移動代理可在此環境中生成、分解、遷移、銷毀，還可以與節點中的駐留代理合作，修改該節點的路由表信息。本文提出的并行路由算法就是通過移動代理的遷移性和智能性來實現的。

以圖2所示網絡拓撲為例，說明算法的實現過程，主要遵循以下四個步驟：

a)網絡帶寬記錄初始化。在應用系統的初始階段，向網絡中派遣測量代理，對各個相鄰節點間的實際帶寬進行測量，并記錄在網絡節點本地的帶寬記錄表中。格式如表1所示。

b)節點間通信路由統計。測量代理除了能夠測量網絡節點間的實際帶寬以外，還可以通過遍歷所有節點，來統計出任意兩節點間的所有可能的路由，這些路由將被測量代理記錄在各個源節點的初始路由表中。初始路由表格式如表2所示。

雖然這一操作在網絡規模較大時比較耗時，但是該操作是在系統正式運行前執行的，并且操作的刷新頻率也不會很高，所以不會對系統的運行效率造成過大的影響。另外，也可通過輔助方法來提高這一操作的執行效率，如無須將兩節點間所有的可能路由都記錄起來，只需通過一些算法（如遺傳算法）計算出相對較優的幾條路由即可，這樣做的好處是提高了初始化路由表的執行效率，不足是由于路由統計得不全面，導致通過并行路由算法計算得出的結果不一定是理論上的最優解。本文意在論述并行路由算法的特性，故在此統計的是全部路由。

c)計算數據量分解比例，寫入分解比例記錄表。根據式（2）計算所有并行路徑的數據量分解比例，將這一比例寫入分解比例記錄表中。也就是說，通過這一步驟，在每個節點的分解比例記錄表中，記錄著對于一組特定的源節點和目的節點，當移動代理遷移至本節點時，應以何種比例進行分解，并向哪些下一跳節點遷移。節點的分解比例記錄如表3所示。

d)移動代理攜帶數據量在節點間遷移。當攜帶數據量的移動代理遷移至某節點時，可遵循該分解比例記錄表中的比例值，將數據量拆分成多個子數據量，由子代理攜帶向不同節點遷移，同時為子代理標號，以便在目的節點重組各個子代理所攜帶的子數據量。

3 算法性能仿真

3.1 仿真環境

以圖2所示的網絡拓撲為仿真環境。以源節點1到目的節點2的數據傳輸問題為仿真實例，將遺傳算法、蟻群算法和本文提出的并行路由算法進行性能比較。

3.2 性能參數

采用兩個參數來描述算法的優化效果：

a）平均延遲時間。該延遲時間是指固定大小的數據量d從源節點傳輸到目的節點所花費的時間，用t表示，單位為s。通過該參數的比較，可最為直接地看出不同算法的優化效果。

b)鏈路流量。該流量是指在實驗過程中，網絡環境中的各個實際鏈路的數據流量，用f表示，單位為KB。通過這一參數的比較，可以看出不同算法在實際運用中，對網絡帶寬的利用率。

33 仿真結果及分析

從平均延遲時間的仿真結果可以看出，隨著傳輸數據量的增大，基于各個算法的應用系統平均延遲時間都有所增加，而其中基于本文提出的并行路由算法平均延遲時間增長得最慢，這是由于傳輸的數據量分為多個子數據量，從并行的不同鏈路傳輸，有效地利用了空閑帶寬，從而縮短平均延遲時間，而傳統的蟻群算法和遺傳算法都是只計算出一條路徑，平均延遲時間自然會略大一些。

從鏈路流量的仿真結果可以看出，蟻群算法和遺傳算法在某些鏈路上傳輸整體的數據量，其他鏈路則完全沒有流量，而本文提出的并行路由算法在所有鏈路上都有部分流量，對網絡環境的帶寬利用率明顯提高。

4 結束語

移動代理憑借其諸多的優勢應用于許多技術領域，在不同的基于移動代理的應用系統中，系統性能的提高很大程度上依賴于移動代理的遷移算法。本文提出的并行路由算法，將傳輸的數據量分解成多個子數據量，在不同的鏈路中傳輸，以此來達到最短的傳輸時間，同時達到最高的帶寬利用率，提高應用系統的運行效率。在仿真實驗中，與蟻群算法和遺傳算法作了性能比較，結果證明了本文提出的并行路由算法的有效性，對應用系統的運行效率起到了優化作用。

參考文獻：

［1］SIM K， SUN W. Ant colony optimization for routing and loadbalancing: survey and new directions[J].IEEE Trans on Systems， Man and Cyberneticspart A: Systems and Humans， 2003:560573.

[2]DORIGO M， BIRATTARI M，STUTZLE T. Ant colony optimization[J].IEEE Computational Intelligence Magazine，2006，1(4):2839.

[3]BAYIR M A，TOROSLUIH，COSAR A. Genetic algorithm for the multiplequery optimization problem[J].IEEE Trans on Systems，Man and Cyberneticspart C:Applications and Reviews，2007，37(1):147153.

[4]GOLONEK T， RUTKOWSKI J. Geneticalgorithmbased method for optimal analog test points selection[J].IEEE Trans on Circuits and SystemsII: Express Briefs，2007，54(2):117121.

[5]BEAN N，COSTA A. An analytic modeling approach for network routing algorithms that use ‘antlike’ mobile agents[J].Computer Networks，2005，49(2):243268.

[6]PETKO J S， WERNER D H. An auto polyploidybased genetic algorithm for enhanced evolution of linear polyfractal arrays[J].IEEE Trans on Antenas and Propagation，2007，55(3):583593.

[7]CHUNG W J， SMITH B， LIM S K. Node duplication and routing algorithms for quantumdot cellular automata circuits[C]//Proc ofIEEE Circuits Devices Syst.2006:497505.

[8]QU Wenyu， SHEN Hong， SUM J. New analysis on mobile agents based network routing[J].Applied Soft Computing，2005，6:108118.