一種改進的基于遷移計劃圖的移動Ａｇｅｎｔ遷移策略
2007-01-01 00:00:00張正球蔡聲鎮余敏
計算機應用研究 2007年1期
摘要：在分析了現有遷移策略的基礎上，提出一種改進的基于遷移計劃圖的結構化遷移策略。該遷移策略能根據當前網絡的軟硬件環境及其他負載信息，在滿足預算約束條件下考慮服務質量和服務價格等因素，動態地為移動Agent規劃出一條最佳遷移路徑；該策略還能避免網絡斷連、主機故障及服務失效引起的遷移失敗。
關鍵詞：移動Agent； 遷移計劃圖； 遷移策略； 服務價格
中圖法分類號：TP311．52文獻標識碼：A
文章編號：1001－3695(2007)01－0040－03
1引言
移動Agent技術涉及遷移策略、通信機制、安全體系等多方面技術，其中遷移策略是其基礎核心技術[1]。遷移策略的優劣直接影響MA的性能乃至其任務的完成[2]，它已成為移動Agent技術領域的研究熱點。Acharya等人最先意識到硬件資源及其使用狀況對MA遷移路徑的影響，他們為Sumatra系統設計了信息監測模塊，該模塊收集各種硬件的負載信息，作為MA選擇遷移路徑的重要依據[3]。M．Ashraf等人從通信性能的角度研究了MA的遷移策略，他們提出了最優決策圖的概念，并應用于移動Agent系統中，為MA規劃出一條最佳遷移路徑，使遷移過程中的通信開銷達到最小。這些工作在遷移策略方面進行了有益的探索，但它們均具有共同的缺點，即設計者事先根據網絡的軟硬件環境及一些約束條件為MA規劃出一條靜態最佳遷移路徑，它們仍然不能刻畫MA在執行任務過程中軟硬件環境的動態變化，也不能保證網絡斷連或主機故障等導致的遷移失敗。劉大有和楊博等人對此提出了基于旅行圖的遷移策略[4]；筆者在文獻[5]中提出了基于遷移計劃圖的遷移機制，它們能有效地根據網絡軟硬件環境的變化為MA動態地規劃出一條遷移路徑，但仍然要求旅行圖中所有節點的主機已知。然而在多數情況下，設計者無法事先預知MA將訪問的所有主機，另外路徑的選擇沒有在滿足消費者預算約束的條件下考慮服務質量和服務價格等因素。本文利用有向無環圖的概念，提出一種改進的基于遷移計劃圖的結構化移動Agent遷移策略。該遷移策略能根據MA的任務、當前網絡的軟硬件環境及其他負載信息，在滿足消費者預算約束的條件下考慮服務質量和服務價格等因素，動態地規劃出MA的最佳遷移路徑。該策略充分體現了MA遷移的自主性和反應性，同時避免了網絡斷連、主機故障及服務失效引起的遷移失敗。
2遷移計劃圖
定義1G=（V，R），其中，集合V是節點的有限集合，每個節點Vi表示一個二元組(Ei，Hosti )，Hosti表示主機，Ei表示在Hosti上執行的操作(或稱子任務)，它一般是Agent對象中的某一方法或方法集合；R是頂點之間直接偏序關系
這種遷移計劃圖能表示三種基本遷移模式，即順序遷移模式、選擇遷移模式和并行遷移模式。圖1(a)表示順序遷移，Agent從V1出發依次經過各個節點到達Vn；圖1(b)表示并行遷移，Agent從V1出發可以創建n個子Agent并行遷移到K個后繼節點。考慮到生成多個子Agent在網絡中并行遷移并共同執行任務需要共享數據狀態及保持同步等，從而使得對Agent難以管理和控制，本文仍由Agent自身逐一訪問這些并行節點并執行相應的子任務，訪問這些節點沒有先后次序但需訪問所有并行的后繼節點。圖1(c)表示選擇遷移，Agent從V1出發有K條路徑供選擇遷移，Agent可以從中選擇任意一條路徑遷移，保證規劃出一條最佳遷移路徑；另外為解決主機斷連及服務失效引起的遷移失敗，在選擇路徑前后分別增加選擇入口虛接點（“（”，Null）和選擇出口虛接點（“）”，Null），使得在這些異常情況下能回到選擇入口重新選擇另一條遷移路徑。反復使用這三種基本遷移模式能構造出復雜的遷移計劃圖（注意：遷移計劃圖允許選擇遷移嵌套但不允許交叉，另外不支持循環遷移模式），
并能很好地描述移動Agent的遷移語義。但是在移動Agent系統中，MA在完成一個任務前，往往無法事先預知MA將訪問的所有主機，即很難為MA制定一個確定的遷移路徑（路徑中包括三種遷移模式），因此改進了遷移計劃圖。
3改進的遷移計劃圖
定義2G=（V，R），其中，集合V是節點的有限集合，每個節點Vi是一個三元組(Ei，Hosti，RCi)，Hosti表示主機，Ei表示在Hosti上執行操作(或稱子任務)，它一般是Agent對象中的某一方法或方法集合，RCi表示MA在主機Hosti上執行子任務E時所需利用Hosti主機上的資源名（或對所需服務資源的約束條件）；R仍是頂點之間直接偏序關系
在改進的遷移計劃圖中，節點Vi中的主機Hosti與資源RCi有關聯，往往是根據執行任務時所需的服務資源來決定遷移到哪臺主機Hosti上，因此節點Vi的表示形式主要有以下兩種（對于主機和資源無直接關聯的，同樣可以采用如下相應的形式表示）：
（2）當MA在運行前制定結構化的遷移計劃圖時，不能夠預先知道執行子任務Ei所需遷移到哪臺具體主機上使用其主機上的具體資源時，也即只知道移動Agent要完成這一個子任務及其所需資源的相應約束條件時，RCi表示為RCi (R_C， R_R， M_U_F)。其中，R_C(Resource_Class)表示所需資源的種類x； R_R(Resource_Restriction)表示移動Agent對資源x的約束條件，包括對資源的服務質量、服務花費時間、服務價格等參數進行約束，如{90≥服務質量≥60，30s≥服務花費時間≥5s，20元≥服務價格≥10元，…}；M_U_F(Make_Utility_Fuction)是MA對該資源類的效用函數（它是用戶根據該MA從消費該商品所獲得的滿意程度來確定的）。此時主機是未知的主機，用Host表示，遷移計劃圖的節點Vi是非確定性節點，表示為如下形式：
這樣，即使節點Vi中的資源不是具體資源且Host為未知主機，移動Agent也能通過資源約束條件動態地找到所能勝任的主機和符合約束條件的服務資源，順利完成子任務，確保MA繼續往后執行子任務。
在定義遷移計劃圖時，如果能預先確定所有的節點Vi，則遷移計劃圖就變成一個確定的遷移計劃圖，遷移計劃圖中的所有節點均被具體表示為(Ei，Hosti，Ri)，本文稱這樣的遷移計劃圖為靜態遷移計劃圖。由于MA完成一個特定的任務往往有多個可選的子任務集，只要執行完一個子任務集就可以完成這個特定的任務，因此一個靜態遷移計劃圖中仍然可能存在選擇遷移模式。如圖2所示，{V1，V2}與{V3，V4}就是可選的子任務集。
需要注意的是，靜態遷移計劃圖是在移動Agent執行任務前就確定的，不是在移動Agent遷移過程中動態規劃出的，并且它也只有在移動Agent系統相對穩定以及所需的服務資源在一定的時間內其性能（即參數）不會改變的情況下才存在靜態遷移計劃圖，如果不是在這種情況下，靜態遷移計劃圖將失去意義，甚至導致遷移失敗。
另外改進的遷移計劃圖要求必須有一個終節點，執行完這個終節點就執行完整個任務，這樣在動態規劃遷移路徑時用來判斷是否順利遷移成功并執行完整個任務。
遷移計劃圖采用鄰接表作為其存儲結構(節點信息單獨用數組存儲)，且在頭節點中增加一個存放頂點入度的數組(選擇出口虛節點無論在圖中的入度是多少，入度均為1)。
4遷移路徑選擇標準
在改進的遷移計劃圖中，存在順序遷移模式、并發遷移模式和選擇遷移三種遷移模式，因此一個改進的遷移計劃圖可能包含多個解圖即多條遷移路徑，在此種情況下，ＭＡ選擇其中最佳的遷移路徑進行遷移，選擇最佳的前提是有一個選擇標準。本文認為一個好的選擇標準應能綜合考慮多個選擇節點的系統軟硬件資源并能夠及時高效地反映出系統資源的動態變化，據此為MA選擇一條最佳的遷移路徑。從軟件資源的角度出發，我們認為影響路徑選擇的主要指標是服務價格、服務質量、服務花費時間；從硬件資源的角度出發，我們認為影響路徑選擇的主要因素是Agent遷移到目標節點機所要耗費的時間、ＣＰＵ利用率和Ｉ/Ｏ利用率等。
本文利用經濟學中的商品效用來集中反映這些軟硬件環境指標。經濟學中的商品效用是指消費者從消費該商品所獲得的滿意程度，消費者效用不僅在于商品本身具有的滿足人們某種欲望的客觀物質屬性，而且還依賴于消費者的主觀感受、消費者對商品的偏好，可用效用函數表示。在此，可以將主機上的服務資源作為商品，把MA作為消費者，對MA自身為服務資源定義一個效用函數，這樣就為MA選擇一條最佳的遷移路徑提供了計算依據。由于當前服務需求的多樣化等特性，不同的用戶有不同的選擇標準，本文提出如下幾種選擇標準：①性價比最高標準。從其多個能滿足MA資源約束條件的服務資源及其所在的主機中選擇性價比最高的服務資源，即MA對該服務資源的效用值與服務資源的服務價格之比為最大的服務資源。②效用最大化標準。從其多個能滿足MA資源約束條件的服務資源及其所在的主機中選擇使自己效用最大化（即為出價函數出價最高）的服務資源。③價格最小化標準。從其多個能滿足MA資源約束條件的服務資源及其所在的主機中選擇服務資源的服務價格最小的服務資源。
對于非確定性節點，根據自身需要在非確定性節點信息中定義好MA對該服務資源的效用函數，函數形式可以表示為
U=f(服務質量，服務花費時間，遷移到節點機所耗費的時間等各種參數)
當MA執行到該非確定性節點時，由MA的感知模塊到服務資源數據服務器上查詢能滿足MA約束條件的服務資源及其所在的主機。如果存在多個能滿足MA約束條件的服務資源及其所在的主機，此時利用效用函數計算出這些具體的服務資源對MA的效用，再根據這些服務資源的服務價格選擇一個合適的資源。
對于遷移計劃圖中的多條選擇路徑，也同樣可以根據這個方法來選擇一條最佳的遷移路徑。當MA在執行任務即遷移前先確定選擇使用一個選擇標準，在遷移過程中，遷移到一個選擇入口虛節點時，利用效用函數計算出每條路徑對MA的效用和需要的花費，再根據選擇標準去選擇一條最佳的遷移路徑。
5遷移計劃圖的動態規劃算法
本文設計的遷移計劃圖動態規劃算法的思想是使用拓撲排序的方法來規劃遷移路徑的。MA在遷移過程中，找到入度為0的節點Vi(Ei，Host)，然后MA遷移到目標主機Host上并執行子任務Ei，同時對該節點的每個鄰接點的入度減1；任務完成后又去找到入度為0的節點(Ei，Host)，Agent就是這樣循環訪問入度為0的節點，直到Agent完成遷移計劃(即執行完所有任務)。為了避免重復檢測入度為0的節點，本算法采用一個棧Indegree存放所有入度為0的節點，棧作為Agent的數據部分隨Agent遷移，算法復雜度為O(n+e)。遷移計劃圖的動態規劃算法程序存放在Agent平臺上，由Agent平臺負責解析和執行。本文設計的動態規劃算法描述如下：
（1）MA出發遷移前初始化。
（2）找一個入度為0的節點Vi(Ei，Host，R)作為MA的當前起點，轉（3）；此時若不存在入度為0的節點，則轉（9）。
（3）判斷MA的當前節點Vi(Ei，Host，R)，如果是確定性節點，轉（4）；如果是非確定性節點轉（5）；如果是選擇入口虛節點，轉（7）；如果是選擇出口虛節點，轉（8）。
（4） 判斷節點Vi中的Host當前能否完成子任務Ei，如果能，MA遷移至主機Host上，執行完子任務Ei，并將節點Vi的所有鄰接點的入度減1，轉（2）；如果不能，則該節點相當于非確定性節點，轉（5）。
（5）由MA的感知模塊到服務資源數據服務器上查詢能滿足MA約束條件的服務資源及其所在的主機。如果存在能滿足MA約束條件的服務資源及其所在的主機，則根據遷移路徑選擇標準選擇一個能提供最佳服務的主機Host，MA遷移至主機Host上，執行完子任務Ei，并將節點Vi的所有鄰接點的入度減1，轉（2）；否則，說明不存在滿足MA約束條件的服務資源及其所在的主機，此時轉（6）。
（6）返回到前一個選擇入口虛節點，如果前面無選擇入口虛節點，則MA遷移失敗，算法結束；否則將該選擇入口虛節點作為MA的當前起點Vi(Ei，Host，R)，轉（7）。
（7）找到MA的當前起點Vi的選擇路徑，如果存在多條，則根據遷移路徑選擇標準選擇一條最佳的遷移起點Vj，將其作為MA的當前起點Vi，轉（3）；如果不再存在選擇路徑，則說明此節點的所有選擇路徑均已遷移失效，轉（6）。
（8）將選擇出口虛節點的所有鄰接點的入度減1，轉（2）。
（9）判斷MA是否已經遷移到終節點，若是，則MA遷移成功，順利執行完任務，算法結束；否則遷移失敗（可能存在環），作異常處理，并告知任務沒有執行完成。
6遷移策略的評價
本文提出的遷移策略是一種改進的基于遷移計劃圖的結構化移動Agent遷移策略。改進的遷移計劃圖能有效地描述移動Agent的遷移語義，能構造出靈活的遷移計劃圖，并突破性地提出利用經濟學中的商品效用來集中反映這些軟硬件環境指標；另外遷移計劃圖的動態規劃算法也非常簡單且高效，能動態地規劃出一條最佳的遷移路徑。該遷移策略相比其他遷移策略具有如下優點：①遷移計劃圖與功能體分離，結構清晰，便于分別設計和管理，并可以動態裝配，也具有較好的復用性。②制定遷移計劃圖時，不要求在遷移前預知Agent待訪問的所有主機。③動態規劃算法能根據遷移計劃圖和當前網絡的軟硬件環境及其他負載信息，依據遷移路徑選擇策略動態地規劃出Agent的最佳遷移路徑，充分體現了Agent遷移的自主性和反應性，同時減少了遷移時間開銷，提高了完成任務的效率。④動態規劃算法的高效性和可靠性，這能在很大程度上避免網絡斷連、主機故障及服務失效所引起的遷移失敗，保證了MA遷移順利進行。
7結束語
本文提出了一種改進的基于遷移計劃圖的結構化遷移策略。該遷移策略能根據當前網絡的軟硬件環境及其他負載信息，在滿足預算約束條件下考慮服務質量和服務價格等因素，動態地為移動Agent規劃出一條最佳遷移路徑，該策略還能避免網絡斷連、主機故障及服務失效引起的遷移失敗。今后的工作將進一步完善遷移計劃圖，使其描述Agent的遷移語義更完整，具有更強的表達能力，同時相應地改進遷移計劃圖的動態規劃算法。
參考文獻：
［1］張冠群， 陶先平，李新，等.Mogent系統遷移機制的設計和實現[J].計算機研究與發展， 2001，38(9)：10351041.
［2］T Chia， S Kannapan. Strategically Mobile Agents[C]. Proc. of the 1st Int’l Workshop on Mobile Agents， Berlin： Springer， 1997.149161.
［3］A Acharya， M Ranganathan， J Saltz. Sumatra：A Language for Resour￣ce Aware Mobile Programs[A]. J Vitek， C Tschudineds. Proc. of Mobile Object Systems： Towards the Programmable Internet[M]. Berlin:Springer，1997.111130.
［4］劉大有， 楊博，等. 基于旅行圖的移動Agent遷移策略[J]. 計算機研究與發展，2003，40(6)：838845.
［5］張正球， 章志明， 余敏. 基于遷移計劃圖的Agent遷移機制[J]. 計算機工程， 2005，31(16):222224.
作者簡介：
張正球（1978），男，江西臨川人，講師，碩士，主要研究方向為移動計算、信息安全；
蔡聲鎮 (1954)，男，福建晉江人，副教授，主要研究方向為智能信息系統；
余敏(1964)，女，江西南昌人，教授，博士，主要研究方向為移動計算、分布式系統。
注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
