分布式檢索系統中基于蟻群的移動agent動態遷移算法

摘 要:以真實蟻群算法為基礎，提出了一種分布式信息檢索下的移動agent動態遷移算法。該算法有如下特點:a)Agent能根據當前主機的狀態，自主選擇下一個負載輕的主機移動;b)Agent能找到一條開銷最小的路徑移動。仿真結果表明，該算法與固定路由算法相比，性能提高80%以上，并且算法無須依賴集中的遷移模塊。蟻群算法分布在各節點中，提高了系統的容錯性，具有分布、并行的特點。

關鍵詞:移動agent; 蟻群算法; 遷移策略; 分布式系統

中圖分類號:TP301.6; TP18 文獻標志碼:A

文章編號:1001-3695(2010)03-0868-03

doi:10.3969/j.issn.1001-3695.2010.03.016

Mobile agent dynamitic migration algorithm in distributed information

retrieval system based on ant colony algorithm

DANG Chen， WANG Jia-zhen， LIU Ai-zhen， ZHAO Xin-qing

(Staff Room of Network Communication， Dept. of Computer Engineering， Ordnance Engineering College， Shijiazhuang 050003， China)

Abstract:This paper distributed a mobile agent dynamitic migration algorithm in information retrieve system founded on real ant colony algorithm had two features: a)According to current hosts’ status， agent could independently choice the next host of small load factor to move; b)Agent could find a lowest overhead route to move. The experiments show that agents migration spending can be improved 80% than changeless routing algorithm. And the algorithm dispense with central migration program. The system fault tolerance has been enhanced because of ant colony algorithm being built in each host.

Key words:mobile agent; ant colony algorithm; migration strategy; distributed system

0 引言

近年來，移動agent作為一種新的分布式計算范型受到越來越多的學者的關注。與傳統的分布式范型相比(如RPC)，移動agent具有能減少網絡擁塞、克服網絡延時、增加分布式應用的健狀性和容錯性等優點，因此在數據挖掘、知識發現、分布式信息收集和檢索、電子商務和移動無線通信等眾多領域具有廣泛的應用前景。特別是在分布式信息檢索方面，由于因特網和無線移動業務的快速發展，眾多的信息分布在地域分散的多個節點上，這就造成用戶在收集和檢索信息時會有大量的數據在網間移動，從而為分布式信息的檢索增加了額外的開銷。在基于移動agent的分布式信息的檢索系統中，可以把agent發送到服務節點上進行檢索任務，這與通過遠程直接連接訪問的分布式信息系統相比，能有效地減少網絡帶寬、通信延時和降低網絡流量[1，2]。

在研究基于移動agent的分布式信息的檢索系統中，移動agent的遷移問題是影響檢索任務性能的重要因素之一。目前對移動agent的遷移路線問題的算法研究大體可以分為三類:a)靜態遷移算法。主要針對穩定的網絡狀態，一般系統指定一條路線或利用一個集中的遷移模塊，計算出一條最優路線，之后所有的agent都沿著這條路線移動。該類算法實現簡單，集中的遷移模塊也只需計算一次，無須額外的系統開銷。例如文獻[3]，將移動agent問題作為TSP(traveling salesman problem)來研究，這類算法測重于理論探討。b)動態遷移。針對網絡狀態不斷變化的情況，系統利用主機節點上的探測模塊不斷測量用戶業務和網絡狀態，并傳送至一個集中的遷移模塊，由此模塊動態地計算出當前最優路徑，來訪的agent沿著此最優路徑移動。由于頻繁地探測主機和傳送主機狀態信息會增加主機和網絡的負擔，同時遷移模塊計算量較大，也會增加駐留遷移模塊主機的計算負擔。除了算法本身的性能外，設定探測和同步信息的時間間隔以及啟動遷移模塊的計算周期對這類算法也尤其重要。對此有不同的動態算法[4~6]。c)自主智能遷移。是指移動agent移動到某個主機節點時，能完全自主地根據當前任務執行情況和網絡狀況智能地選擇最優路線移動，而不依賴于集中的遷移模塊。這類算法更能充分體現agent的異步性、自主性和并行性。對于分布式信息的檢索系統來說，由于來訪用戶量大，服務節點分布在不同的網絡中，網絡環境復雜，同步系統狀態困難，就非常需要自主智能遷移算法對系統提供支撐。

本文旨在研究第三類算法，利用真實蟻群尋徑的思想[7]，移動agent在服務節點環境中釋放信息素，以達到節點間信息同步的作用。當agent移動到某個節點時，能根據當前節點的環境狀態智能地選擇下一個負載輕、時間距離短的節點來移動，并能避免網絡斷連、主機故障所引起的遷移失效問題。文獻[8~10]雖然也用蟻群算法對移動agent遷移問題進行了研究，但它們仍是通過收集網絡信息，利用集中的蟻群算法模塊計算最優路徑，屬于第二類算法。

1 基于移動agent的分布式信息檢索系統模型

1.1 信息檢索系統總體結構

信息檢索系統總體結構如圖1所示。目錄服務器提供Home服務器主機的查詢，并提供來自各分布式主機的注冊服務。目錄服務器保存了一組有效的服務節點注冊信息，包括惟一的服務節點主機名、提供服務的組件名和提供通信服務的組件名等。移動agent能查詢目錄服務器，以找到要訪問的服務節點地址。Home服務器是一直聯網的專用服務器。Home服務器為每個本地agent系統用戶提供一個停靠的場所，返回的移動agent在其上等待用戶端的檢索。

1.2 Agent系統體系結構

各信息服務節點提供了agent進行分布式信息檢索的運行環境，在其上可以運行agent、發送agent、接收agent以及管理agent。各信息服務節點就是一個分布式服務器，其體系結構大體可分為三層，如圖2所示。

1)應用層 移動agent在這一層運行并提交檢索任務。

2)服務agent層 該層是一些具有特定功能的靜態agent，它們提供計算資源并進行檢索任務。例如數據挖掘agent是一種利用特殊的算法從分布式數據庫中提取信息的靜態agent。

3)系統服務層 該層包括目錄服務、移動服務和通信服務等。目錄服務標志了agent能移動到的其他節點;通信服務能傳送和接收移動agent;移動服務為agent制訂遷移計劃。移動agent還可以利用其他系統服務和其他agent通信或復制agent等。

1.3 遷移問題描述

遷移問題描述中所用符號說明見表1。

表1 文中所用符號的說明

符號說明

n系統中主機節點的數量

S系統中主機節點的集合，即{v1，v2，…，vn}

v1，v2，…，vn節點標志

a1，a2，…，an移動agent的標志

Saiai要訪問的主機節點的集合，即ai的路由表，其中SaiS

d(vi，vj)vi、vj間的時間距離

NVi節點vi上的處理agent的閾值個數

N_maxvi節點vi上能處理的最多agent個數

F(vi)節點vi的負載感知度

D(Sai)ai在Sai上經過的節點序列，如〈v1，v2，…，vr〉

T(D(Sai))ai在Sai上總的檢索開銷

定義1 節點vi、vj之間的距離d(vi，vj)定義為

d(vi，vj)=∑kwkicki+w0ci→j(1)



其中:cki為MA在節點vi上進行檢索時所造成的第k項開銷(如檢索時間、檢索質量、檢索價格等);ci→k為從服務節點i移動到服務節點j的網絡時延;w為各開銷指標的權重。

定義2 ai總的檢索開銷為

T(D(Sai))=∑r-1id(vi，vi+1)(2)

其中:D(Sai)=〈v1，v2，…，vr〉。

定義3 節點vi的負載感知度定義為

F(vi)=1N_maxvi-Nvi(1-c)nvi+cN_maxvi-Nvi 其中Nvi

這里負載只與節點vi上當前移動agent個數n有關，每個主機都有一個最大可承受的agent數量N_maxvi。負載感知度F(vi)代表了主機感知本機agent負載大小的能力;Nvi是一個閾值常數，閾值越大，說明計算機能同時處理agent的數量越多，當n≤Nvi，由于對agent間彼此不受影響，負載感知度忽略為零;c為常數。

定義4 這里定義分布式信息檢索系統中移動agent遷移問題(ASMP)。設共有n個分布式信息服務節點，服務節點要么為MA提供服務，要么失效。MA在遍歷服務節點時，可以繞過失效或負載大的節點，并在有效節點上獲得服務。ASMP問題就是要令每個MA在遍歷所有有效服務節點時時間開銷最小，即

minimize ∑riT(D(Sai))，1≤i≤r

2 算法描述

在分布式信息檢索系統中，考慮三種用戶行為:a)具有時間限制的要求，即用戶希望移動agent在指定時間內返回;b)具有跳數限制的要求，即移動agent在訪問過幾個節點后就返回;c)MA訪問所有的節點后返回。可以將a)看做b)用戶行為的特例，因此可以僅考慮b)和c)用戶行為。蟻群算法作四點改進。

1)概率選擇

以某種概率選擇下一個要去的節點，這個概率是兩個節點之間距離及其路徑上所含有的信息素數量的函數。定義1/d(i，j)稱為啟發因子ηij。pkij(t)為第K個agent由節點i向j轉移的概率，它由式(4)計算:

pkij(t)=[τij(t)]α×[ηij]β∑k∈allowedk[τij(t)]α×[ηij]β+(F(vi))γ，如果j∈allowedk0否則(4)

其中:allowedk={n-tabuk}，tabu為禁忌表;參數α、β、γ分別表示信息素的濃度、啟發因子及負載感知度在轉移概率pkij(t)中的相對重要性。

2)各節點中信息素表中的信息素濃度按式(5)修正

τnew(i，j)=(1-ρ)×τold(i，j)+Δτk(i，j)(5)

其中:ρ為系數;(1-ρ)表示時間t與t+n之間信息素的揮發程度;Δτkij是第k個agent釋放在路徑(i，j)上的信息素的數量。它由式(6)計算:

Δτk(i，j)=(r-1)QT(D(Sak)) 如果第k個agent走過路徑(i，j)

0否則(6)

其中:Q是一個信息素增加強度系數;r-1為agent走過的節點跳數;r為節點數。

3)系統狀態獲取

在一個成功的分布式信息檢索系統中，由于來訪的用戶agent數量較大，信息節點分散在復雜的Internet環境中，同步網絡和節點狀態信息非常因難，同步時間把握不好會造成網絡的巨大負擔，較為典型的有三種同步策略:

策略1 利用backforward agent來更新[11]，agent到達目的節點后，創建一個后向agent，將收集的節點信息交給后向agent，利用后向agent把收集的信息存入各節點。但這會產生過多的進程，增加系統負擔，同時信息不能被沒走過的節點感知。

策略2 一步一更新，即agent每走一步，通過消息告訴相鄰節點當前節點和網絡狀態。但agent過多會形成消息風暴。

策略3 設置集中的管理模塊。Agent到達目的節點后，發送消息到管理模塊告知收集到的系統狀態。管理模塊保存最近一組系統狀態信息，當下一個agent進入系統時，agent查詢管理模塊，并攜帶這組系統狀態。Agent每移動到一個節點，就用這組狀態更改節點的相關表項，從而同步走過的每個節點的系統狀態表。

本文采用第三種同步策略，利用用戶agent通過異步方式達到同步信息的作用。由于agent攜帶最近其他agent探測的系統狀態信息，能較為實時地反映系統狀態。

4)算法流程

a)移動agent行為(各agent并行)

(a)在Home節點上，獲取最新路徑信息素集合MaSet;

(b)移動到下一個節點，用MaSet更新該節點信息素表;

(c)進行檢索任務，記錄檢索時間;

(d)記錄上一節點到本節點的旅行時間;

(e)重復(b)~(d)直到離開系統;

(f)向信息素管理模塊發送消息，傳送收集到的系統狀態信息;

(g)回到Home節點;

b)節點算法(各節點并行)

(a)接收agent，計算出agent旅行時間;

(b)統計當前節點的agent個數;

(c)接收agent離開請求，按式(4)計算概率，為agent確定下一個主機節點;

(d)發送agent到下一個主機節點;

c)信息素管理模塊

(a)從消息池中循環讀取agent發送的消息;

(b)按式(5)(6)計算出信息素，修正MaSet集合。

3 仿真實驗

仿真環境按真實的基于移動agent的分布式信息系統來建立[12]。硬件環境主要包括:

a)30個節點構成4個子網，組成類似于廣域網的拓撲結構。通過實際測試，在子網內兩節點間傳送一個agent的時間在2~15 ms，在子網間為30~70 ms，并且agent在服務器節點上進行一次特定檢索任務的時間在1~8 ms。因每次測試所得時間不同，實驗的環境完全是動態的。

b)節點所用的計算機為Intel Pentium4，CPU 3.0 GHz， 512 MB內存。注冊服務器節點為Intel XeonTM 4， CPU 3.0 GHz，1 GB內存。顯然，當計算機計算能力增強時，所得仿真結果性能會更好。

c)設置三臺Home節點，每個節點以每10 ms發送一個執行特定檢索任務的agent。集中的管理模塊安裝在注冊節點上。

實驗1 比較固定路線遷移和用本算法遷移的性能。統計agent離開系統的時間，每30個agent離開系統時統計一次agent平均遷移時間，并做圖，如圖3所示。采用固定路線遷移算法所用的平均時間為1 281.1 ms，本算法agent所用的平均時間為220.21 ms，性能提高了大約82.81%。

實驗2 把每個agent遷移跳數設為29，并把其中一個節點(記為節點a)的負載值設為大于負載閾值，以每30個agent統計一次來計算到達節點a的agent個數，如圖4所示。統計到達節點a的agent個數為230，占所有agent個數的0.153 3%，從而可以看到，使用本算法可以繞過負載感知度大的節點。

從圖中可以看到，在系統初始時，由于要探測網絡的初始狀態，要消耗一部分的用戶agent的時間性能。可以作以下改進，在系統負載不太大的時間段里(如子夜)，可以啟動測試agent來探測網絡狀態，以減少用戶agent的時間性能。

4 結束語

本文算法能實時探測系統狀態并感知系統最優路徑，無須集中的遷移計劃模塊，agent能根據各節點當前系統狀態選擇負載輕、路徑短的線路遷移。仿真結果說明，與固定遷移算法相比有很大的性能提高，并能應用于基于移動agent的分布式信息檢索系統中。

參考文獻:

[1]MOIZUMI K， CYBENKO G. The traveling agent problem[J]. Ma-thematics of Control，Signals and Systems， 1998，14(3):213-232.

[2]BREWINGTON B， GRAY R， MOIZUMIL K. Mobile agents in distributed information retrievall[C]//Proc ofIntelligence Information Agent. Berlin : Springer-Verlag ， 1991:355-395.

[3]MOIZUMI K. Mobile agent planning problems[D].[S.l.]: Dartmouth College， 1998.

[4]BAEK J W， YEOM H Y. D-agent an approach to mobile agent planning for distributed information retrieval[J]. IEEE Trans on Consumer Electronics， 2003，49(1):115-122.

[5]劉大有，楊博，楊鯤，等. 基于旅行圖的移動agent遷移策略[J].計算機研究與發展，2003，40(6):838-845.

[6]張正球，蔡聲鎮，余敏. 一種改進的基于遷移計劃圖的移動agent遷移策略[J].計算機應用研究， 2007，24(1):40-42.

[7]COLORNI A，DORIGO M，MANIEZZO V. Distributed optimization by ant colonies[C]//Proc of the European Conference on Artificial Life. Paris: Amsterdam Elsevier Publishing， 1991:134-142.

[8]駱正虎. 移動agent系統若干關鍵技術問題研究[D].合肥:合肥工業大學， 2002.

[9]杜榮華，姚剛，吳泉源. 蟻群算法在移動agent遷移中的應用研究[J]. 計算機研究與發展， 2007，44(2):282-287.

[10]鄧江沙，姚剛. 改進的蟻群算法在求解旅行agent問題中的應用[J]. 計算機技術與發展， 2006，16(7):233-235.

[11]CARO G， DORIGO M. AntNet: distributed stigmergetic control for communications networks[J]. Journal of Artificial Intelligence Research， 1998，9: 317-365.

[12]黨辰，王嘉禎，王素貞.一種基于組件的移動agent平臺設計與實現[J].計算機工程與設計， 2009，30(3):700-702.