基于MAMP模型的HVU算法

羅 曉

（中國民用航空局第二研究所,成都 610041）

基于MAMP模型的HVU算法

羅 曉

（中國民用航空局第二研究所,成都 610041）

提出利用混合P2P（M ixed Peer to Peer）架構結合MA（Mobile Agent）技術解決移動計算環境下數據可靠收斂問題,在此基礎上建立了MAMP（Mobile Agent and M ixed Peer Model）模型。分析了模型的系統結構和核心技術,重點闡述了MAMP模型的同步策略——HVU（Highest Votes to Update）算法,給出了嚴格的數學證明。實驗結果表明,該模型基礎下的算法具有較高的可靠性。

混合P2P;移動代理;JXTA協議;HVU算法

1 引 言

當今社會,科學技術的發展與移動電子產品的普及,以及大量PDA、掌上電腦和筆記本電腦等移動設備的大量應用,激發了個人通信網（PRN）、網絡計算機（NC）以及對等網絡（P2P）等新概念的產生。移動計算網絡環境正逐步形成[1,2],基于移動計算的網絡環境以其鮮明的特點如移動性、斷接性、帶寬多樣性、可伸縮性、弱可靠性、網絡通信的非對稱性、電源能力局限性等對計算機技術提出新的要求[3,4]。其中,基于移動計算環境的數據同步技術則是研究的熱點之一。

近年來,國內外的學者在這一方面做了很多工作,比如李艷等提出了一種數據同步模型[5],該模型基于關聯事務的移動數據庫同步原理,結合了優點突出的移動數據庫系統的三層數據模式,并能根據緩沖區內劃分的移動事務的結果集來組織更新數據的上載以及數據在同步服務器與主數據庫之間的交互,但對移動計算環境所帶來的重大調整缺乏有效地解決措施和手段。另外,清華大學學者盧福子等人根據Client-Server事務級同步機制建立了CSTR系統模型[6],CSTR系統具有以下特點:支持弱一致性復制,有效地控制并發操作,保證收斂的正確性;具有較小的同步開銷;有效提高一致性收斂速度;但是該系統采用了傳統的樂觀并發控制機制中的時間戳的沖突檢測方法,這種方法由于事務夭折率高而影響復制系統性能。綜上所述,傳統基于固網的數據同步機制需要在服務端和客戶端之間進行在線常連接的多次交互和傳遞數據才能完成,如果將這種復雜機制移植到移動計算環境下將是低效率和不可靠的。因此,必須提出一種新的機制來解決移動環境下的數據同步問題。本文提出了一種新的數據同步算法,該算法在MAMP模型的基礎上進行設計,避免了一些傳統上固有模型的弊端,具有一定的實踐意義。

2 MAMP模型

2.1 MAMP模型簡介

如圖1所示,MAMP模型是融合混合P2P（Mixed P2P）架構和Mobile Agent技術而提出的。其中,混合P2P架構克服了集中式P2P易被攻擊,以及純粹式P2P缺乏快速搜索機制和可擴展性差等問題[7]。它在分布式模式基礎上,將用戶節點按能力進行分類,讓某些節點擔任特殊任務,從而產生了在MAMP模型中的CN、SN和DC（數據專區）等核心概念;Mobile Agent技術則側重于解決復雜的數據同步策略實現,它利用本文提出的HVU算法來保障數據的一致性收斂狀態,同時它的遷移機制能與混合P2P架構契合在一起,滿足移動計算環境下數據同步的要求。

圖1 移動計算場景Fig.1Mobile computing scenreo

2.2 MAMP模型結構

圖2是圖1從邏輯功能角度的局部放大示意圖。圖中所出現的相關概念如下:

MA:Mobile Agent（移動代理）是執行HVU算法的可移動代碼片,它是數據同步機制的主體部分。

CN:Common Node（普通節點）是混合P2P架構中的對等點角色即邏輯上完全平等的節點,類似于JXTA協議[8]中的Peer概念。

LS:Light Weight Server（輕載服務器）是一個全新的概念。物理上它可以和CN是一樣的設備,邏輯上它僅比CN多了對DC的控制管理功能（如CN的加入和退出等）,而站在數據同步角度來看它和CN功能完全一樣。

DC:Data Cluster（數據專區）如圖1的虛線區域所示。按照對相同數據的共享,可將網絡中的節點劃分為多個數據專區（Cluster）,一個數據專區內的所有節點共享某一個相同的數據子集,對某一數據項的每一次更新發生在由該數據項的所有共享者組成的數據專區內。一個數據專區由一個LS和其所轄的CN組成。

MAMP模型首先采用數據分割技術將網絡劃分為多個數據專區（Cluster）,即一個數據專區中的CN和LS共享某個數據集,如移動銷售中販賣同一產品的銷售人員組成一個數據專區;當專區內的某個CN或LS對該共享數據集發起更新操作時（銷售人員賣出該產品）,派遣出的MA遵照HVU算法,取得大多數CN（LS）的同意后,由MA發起更新廣播,同步區內的所有節點,將數據收斂一致。

圖2 MAMP模型結構Fig.2 MAMP model structure

3 MAMP模型同步算法

MAMP模型的核心問題在于如何確保在移動計算環境中數據的最終可靠收斂。受Available Copy（AC）[9]協議及其改進協議——投票協議 （Voting Protocol）的啟發,本文通過加入MA技術彌補以上協議在交互上的缺陷;參照實時數據庫技術中的優先級頂策略[10],挑選出成為最高優先級的MA,授予其一次對相關數據進行寫操作的權力。這樣就產生了一種新的數據更新算法——HVU（Highest Votes to Update）算法,并在MAMP模型中成功應用。

3.1 HVU算法的數學證明

HVU算法要保證一個數據專區DC中有N個節點,在一個更新回合中,有M個Agent發起同一數據的更新請求,但最多只有一個MA可以執行更新事務,即在移動計算環境中通過HUV算法保證這種松散結構的數據一致性。

假設一:對所有參與更新的MA都約定,在CN上的LT表中具有最高優先級的MA在該CN上具有最高優先級。

這個假設是合理的,每個MA可以通過直接訪問該CN或從其它已經訪問過該CN的MA處得到LT表的信息,通過這兩種方法得到的與表中具有最高優先級的MA的信息是一致的。

假設二:當出現多個MA在一次更新回合中至少有兩個相同的最高優先級時,MA的ID小者為此次回合的執行者。

定理一:設一個移動環境中有M個MA存在;同時任選一個DC（有N個CN和1個LS）,則在任何一個CN發起的數據更新操作回合中,只有一個MA可以獲得最高優先級。

證明:由假設一可知每個MA都根據同樣的策略在CN上競爭最高優先級,那么當一個MAi在本DC中得到了半數以上CN的最高優先級,那么其它所有的MA也認同MAi成為本回合的最高優先級;當DC內所有的MA的優先級都不可能再繼續累加時,優先級累計值最大的那個MA成為本回合的最高優先級,其余MA也都認可;如果出現平局,則由假設二保證了在一個數據更新回合中,只有一個MA成為最高優先級。

性質一:此時得到最高優先級的MA最少要移動N/M」+1次,最多移動N次。

證明:得到最高優先級的MA或者是訪問了超過N/2的CN,或者是在平局中依靠自己的ID得到最高優先級即移動了N/M」+1次。在每一種途徑中,MA都至少要訪問N/M」個CN,至多訪問N個CN。

3.2 收斂算法——HVU算法說明

HVU算法思想是基于混合P2P模式利用MA技術完成一個DC內所有節點的投票,當一個DC內的某個節點發生了本地數據更新,它派出一個MA攜帶本事務出發,巡游專區內其余節點,每到達一個節點,MA就會提出鎖請求,節點根據自身信息,向在該節點上具有最高優先級的那個MA頒發鎖,MA根據優先權積累策略積累優先權,根據優先級策略,當MA成為最高優先級時,它取得廣播該更新事務的權利,發起一次廣播,將本次更新事務廣播到區內各節點,并在收到各節點回復后,廣播提交信息,完成一次數據更新,最后釋放對相應數據項的鎖。

在該算法中借鑒了優先級頂（Priority Ceiling,PC）策略思想,該策略假定在每一個事務執行前就知道其要存取的數據,并且對每一個數據維護一個包含要存取它的多個事務ID及其優先級的表。規定當一個攜帶對某一數據項的更新事務的Agent成為該數據項的最高優先級時,它得到廣播本次更新事務的權利;否則,它將被已成為該數據項的最高優先級的那個Agent所阻塞,直至鎖被釋放。一個數據更新回合定義為從某數據產生本地更新開始（Mobile Agent攜帶任務被派發）,到該更新事務被成為最高優先級的Agent廣播提交后釋放鎖結束為止。

PC策略原是在實時系統中提出來的,是鎖式并發控制的一種方法,目的是防止死鎖和阻塞鏈的形成。其思想是每一個數據設置一個“優先級頂”,它定義為要存取該數據的事務的優先級最高者。一個事務要獲得對一個數據的鎖,其優先級必須嚴格地高于當前由其它事務鎖住的各數據的最高優先級（記為H-PC）,否則它就被鎖住在最高優先級的數據的事務（記為THPC）所阻塞。該策略形式描述如下:

另外,該算法涉及基于Mobile Agent的優先權累積策略及平局策略。策略假設一個DC內共有N個節點（包括LS和CN）,在一個數據更新回合中,MA通過與DC內的各CN、LS及其它MA交互,得知其它MA優先權的積累情況,同時其攜帶該信息繼續訪問其它節點,在自己的鎖表LT上積累鎖信息。當通過不斷學習積累了足夠的信息后,它就知道DC范圍內某個MA對這把鎖有最高優先權。

如果在巡游的過程中,一個MA得到的鎖的數量超過N/2,那么此時它成為本回合的最高優先級;如果一個MA得到鎖的數量加上它所知道的其它MA得到鎖的數量,剛好等于Cluster內總的節點數N,MA已經不可能再累加鎖的數量了。此時,得到鎖數量最多的MA成為本回合最高優先級;如果m個MA分別都得到了s個CN或LS上的最高優先權,且有m×s=N,稱這種情況為平局,此時,依靠MA的ID來解決僵局。

3.3 HVU算法思想描述

4 仿真試驗分析

4.1 實驗平臺

J2SDK1.5.X、Sun公司JXTA協議及應用平臺InstanP2P、IBM的Aglet平臺。網絡無線環境正常覆蓋,網絡斷接隨機出現。

4.2 實驗結果分析

實驗共做了3組。第1組:模擬3個節點;在每個節點上,可供請求的鎖數量在60～150個之間;隨機產生10個攜帶更新事務的MA;重復執行30次。第2組:模擬5個節點;在每個節點上,可供請求的鎖數量在60～150個之間;隨機產生70個攜帶更新事務的MA;重復執行30次。第3組:模擬7個節點;在每個節點上,可供請求的鎖數量在60～150個之間;隨機產生120個攜帶更新事務的MA;重復執行30次。每一組實驗執行完畢后,單事務平均完成時間為結果的參考指標。得到的實驗結果如圖3所示。

圖3 HVU算法仿真結果圖Fig.3 Simulation result of HVU algorithm

結果表明,當MA數量增加到大于100時,完成更新事務的平均時間會急劇增加,跟蹤分析程序日志發現均為獲得鎖的仲裁時間過長導致此現象,從而說明鎖資源的管理在更新事務完成時間中成為影響效率的關鍵,這為下一步的算法效率提升提供了解決方向。另外,程序日志表明,無論網絡質量如何,即使隨機出現網絡斷接情況時,除少量增加更新事務完成時間外無更新事務失敗,這表明算法能較好適應移動環境的低可靠性特點。

5 結 論

本文針對移動計算環境的特點,結合混合P2P架構和MA技術,提出了MAMP模型和HUV算法,通過大量的實驗表明該模型和算法能較好地解決移動環境的斷接性和弱可靠性問題。上述研究成果已經部分應用在民航機場的移動調度產品中。

未來的工作包括:

（1）研究CN在并發事務壓力下的鎖資源優化管理,提升HUV算法的執行效率;

（2）研究LS的移動接管機制,使MAMP模型在容錯性上進一步提升性能;

（3）簡化Sun公司的InstanP2P,使之能更好地適應民航業務場景需求。

[1] Alonso R,Korth H F.Database System Issue in Nomadic Computing[C]//Proceeding of the ACM International Conference on Management of Data.New York,USA:ACM,1993:388-392.

[2] David Howard Ralner.ROAM:A Scalable Replication forMobile and Distributed Computing[D].Los Angeles,California:University of California Los Angeles,1998.

[3] 馮玉才,李東,王元珍,等.一種移動數據庫管理系統的體系結構[J].計算機研究與發展,2001,38（5）:15-17.

FENG Yu-cai,LI Dong,WANG Yuan-zhen,et al.An Architecture of Mobile Database ManagementSystem[J].Journal of Computer Research and Development,2001,38（5）:620-625.（in Chinese）

[4] 丁治明,孟小峰,王珊.復制的移動數據庫系統事務級同步處理策略[J].軟件學報,2002,13（2）:258-265.

DING Zhi-ming,MENG Xiao-feng,WANG Shan.A Novel Transactional Synchronization Scheme for Replicated Mobile Database Systems[J].Journal of Software,2002,13（2）:258-265.（in Chinese）

[5] 李艷,藍雯飛.移動數據庫中數據同步技術的研究[J].重慶科技學院學報（自然科學版）,2008,10（6）:112-113.

LI Yan,LAN Wen-fei.The Research on Data SynchronizationMethod inMobile Database[J].Journal of Chongqing U-niversity of Science and Technology（Natural Science Edition）,2008,10（6）:112-113.（in Chinese）

[6] 盧福子.移動數據庫同步技術研究[D].北京:清華大學,2004.

LU Fu-zi.Research on the Synchronization Technology of Mobile Database[D].Beijing:Tsinghua University,2004.（in Chinese）

[7] 李東,曹忠升,馮玉才,等.移動數據庫技術研究綜述[J].計算機應用研究,2000,17（10）:4-7.

LI Dong,CAO Zhong-sheng,FENG Yu-cai,et al.The Survey of Mobile Database Technology[J].App lication Research of Computers,2000,17（10）:4-7.（in Chinese）

[8] 閆旭東,徐國旺,楊濤.基于JXTA的P2P技術研究[J].湖北大學工學報,2010,25（5）:104-106.

YAN Xu-dong,XU Guo-wang,YANG Tao.The Study of the P2P Technology Based on JXT A[J].Journal ofHubei University of Technology,2010,25（5）:104-106.（in Chinese）

[9] 李霖,周興銘.WCSR:一個弱一致性的復制數據庫系統[J].計算機工程,1999,25（4）:45-47..

LI Ling,ZHOU Xing-min.WCSR[J].Computer Engineering,1999,25（4）:45-47.（in Chinese）

[10] 李東,馮玉才,王元珍.適于移動數據庫的客戶/服務器體系結構研究[J].計算機應用研究,2001,18（4）:32-34.

LI Dong,FENG Yu-cai,WANG Yuan-zhen.The Research on Client/Server Architecture for Mobile Database[J].Application Research of Computers,2001,18（4）:32-34.（in Chinese）

HVU Algorithm Based on MAMP Model

LUO Xiao
（The Second Research Institute of Civil Aviation Administration of China,Chengdu 610041,China）

To solve the problem of data reliable consistency in mobile computing,the MAMP（Mobile Agent and Mixed Peer Model）model based on mixed P2P（Peer to Peer）network and MA（Mobile Agent）is proposed.The synchronization strategy of MAMP,that is HVU（Highest Votes to Update）algorithm,is discussed after analysis of system structure and core technique.Strict mathematic proving is given.Experiments demonstrate algorithm based the proposed model has higher reliability.

mixed P2P;mobile agent（MA）;JXTA p rotocol;HVU algorithm

the M.S.degree in1995.He is now a senior engineer at The Second Research Institute ofCAAC.His research interests include airport information integration,computer simulation and data base technology,etc.

Email:lxdj@vip.sina.com

TP311

A

10.3969/j.issn.1001-893x.2011.02.012

1001-893X（2011）02-0062-05

2010-12-01;

2011-01-13

羅 曉（1970-）,男,重慶人,1995年獲碩士學位,現為中國民航局第二研究所高級工程師,主要研究領域為機場信息集成技術、計算機仿真、數據庫技術等。

LUO Xiao was born in Chongqing,in 1970.He