基于MAMP模型的HVU算法

羅 曉

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

基于MAMP模型的HVU算法

羅 曉

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

提出利用混合P2P（M ixed Peer to Peer）架構(gòu)結(jié)合MA（Mobile Agent）技術(shù)解決移動計(jì)算環(huán)境下數(shù)據(jù)可靠收斂問題,在此基礎(chǔ)上建立了MAMP（Mobile Agent and M ixed Peer Model）模型。分析了模型的系統(tǒng)結(jié)構(gòu)和核心技術(shù),重點(diǎn)闡述了MAMP模型的同步策略——HVU（Highest Votes to Update）算法,給出了嚴(yán)格的數(shù)學(xué)證明。實(shí)驗(yàn)結(jié)果表明,該模型基礎(chǔ)下的算法具有較高的可靠性。

混合P2P;移動代理;JXTA協(xié)議;HVU算法

1 引 言

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

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

2 MAMP模型

2.1 MAMP模型簡介

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

圖1 移動計(jì)算場景Fig.1Mobile computing scenreo

2.2 MAMP模型結(jié)構(gòu)

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

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

CN:Common Node（普通節(jié)點(diǎn)）是混合P2P架構(gòu)中的對等點(diǎn)角色即邏輯上完全平等的節(jié)點(diǎn),類似于JXTA協(xié)議[8]中的Peer概念。

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

DC:Data Cluster（數(shù)據(jù)專區(qū)）如圖1的虛線區(qū)域所示。按照對相同數(shù)據(jù)的共享,可將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為多個數(shù)據(jù)專區(qū)（Cluster）,一個數(shù)據(jù)專區(qū)內(nèi)的所有節(jié)點(diǎn)共享某一個相同的數(shù)據(jù)子集,對某一數(shù)據(jù)項(xiàng)的每一次更新發(fā)生在由該數(shù)據(jù)項(xiàng)的所有共享者組成的數(shù)據(jù)專區(qū)內(nèi)。一個數(shù)據(jù)專區(qū)由一個LS和其所轄的CN組成。

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

圖2 MAMP模型結(jié)構(gòu)Fig.2 MAMP model structure

3 MAMP模型同步算法

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

3.1 HVU算法的數(shù)學(xué)證明

HVU算法要保證一個數(shù)據(jù)專區(qū)DC中有N個節(jié)點(diǎn),在一個更新回合中,有M個Agent發(fā)起同一數(shù)據(jù)的更新請求,但最多只有一個MA可以執(zhí)行更新事務(wù),即在移動計(jì)算環(huán)境中通過HUV算法保證這種松散結(jié)構(gòu)的數(shù)據(jù)一致性。

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

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

假設(shè)二:當(dāng)出現(xiàn)多個MA在一次更新回合中至少有兩個相同的最高優(yōu)先級時,MA的ID小者為此次回合的執(zhí)行者。

定理一:設(shè)一個移動環(huán)境中有M個MA存在;同時任選一個DC（有N個CN和1個LS）,則在任何一個CN發(fā)起的數(shù)據(jù)更新操作回合中,只有一個MA可以獲得最高優(yōu)先級。

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

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

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

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

HVU算法思想是基于混合P2P模式利用MA技術(shù)完成一個DC內(nèi)所有節(jié)點(diǎn)的投票,當(dāng)一個DC內(nèi)的某個節(jié)點(diǎn)發(fā)生了本地?cái)?shù)據(jù)更新,它派出一個MA攜帶本事務(wù)出發(fā),巡游專區(qū)內(nèi)其余節(jié)點(diǎn),每到達(dá)一個節(jié)點(diǎn),MA就會提出鎖請求,節(jié)點(diǎn)根據(jù)自身信息,向在該節(jié)點(diǎn)上具有最高優(yōu)先級的那個MA頒發(fā)鎖,MA根據(jù)優(yōu)先權(quán)積累策略積累優(yōu)先權(quán),根據(jù)優(yōu)先級策略,當(dāng)MA成為最高優(yōu)先級時,它取得廣播該更新事務(wù)的權(quán)利,發(fā)起一次廣播,將本次更新事務(wù)廣播到區(qū)內(nèi)各節(jié)點(diǎn),并在收到各節(jié)點(diǎn)回復(fù)后,廣播提交信息,完成一次數(shù)據(jù)更新,最后釋放對相應(yīng)數(shù)據(jù)項(xiàng)的鎖。

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

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

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

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

3.3 HVU算法思想描述

4 仿真試驗(yàn)分析

4.1 實(shí)驗(yàn)平臺

J2SDK1.5.X、Sun公司JXTA協(xié)議及應(yīng)用平臺InstanP2P、IBM的Aglet平臺。網(wǎng)絡(luò)無線環(huán)境正常覆蓋,網(wǎng)絡(luò)斷接隨機(jī)出現(xiàn)。

4.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)共做了3組。第1組:模擬3個節(jié)點(diǎn);在每個節(jié)點(diǎn)上,可供請求的鎖數(shù)量在60～150個之間;隨機(jī)產(chǎn)生10個攜帶更新事務(wù)的MA;重復(fù)執(zhí)行30次。第2組:模擬5個節(jié)點(diǎn);在每個節(jié)點(diǎn)上,可供請求的鎖數(shù)量在60～150個之間;隨機(jī)產(chǎn)生70個攜帶更新事務(wù)的MA;重復(fù)執(zhí)行30次。第3組:模擬7個節(jié)點(diǎn);在每個節(jié)點(diǎn)上,可供請求的鎖數(shù)量在60～150個之間;隨機(jī)產(chǎn)生120個攜帶更新事務(wù)的MA;重復(fù)執(zhí)行30次。每一組實(shí)驗(yàn)執(zhí)行完畢后,單事務(wù)平均完成時間為結(jié)果的參考指標(biāo)。得到的實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 HVU算法仿真結(jié)果圖Fig.3 Simulation result of HVU algorithm

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

5 結(jié) 論

本文針對移動計(jì)算環(huán)境的特點(diǎn),結(jié)合混合P2P架構(gòu)和MA技術(shù),提出了MAMP模型和HUV算法,通過大量的實(shí)驗(yàn)表明該模型和算法能較好地解決移動環(huán)境的斷接性和弱可靠性問題。上述研究成果已經(jīng)部分應(yīng)用在民航機(jī)場的移動調(diào)度產(chǎn)品中。

未來的工作包括:

（1）研究CN在并發(fā)事務(wù)壓力下的鎖資源優(yōu)化管理,提升HUV算法的執(zhí)行效率;

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

（3）簡化Sun公司的InstanP2P,使之能更好地適應(yīng)民航業(yè)務(wù)場景需求。

[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] 馮玉才,李東,王元珍,等.一種移動數(shù)據(jù)庫管理系統(tǒng)的體系結(jié)構(gòu)[J].計(jì)算機(jī)研究與發(fā)展,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] 丁治明,孟小峰,王珊.復(fù)制的移動數(shù)據(jù)庫系統(tǒng)事務(wù)級同步處理策略[J].軟件學(xué)報(bào),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] 李艷,藍(lán)雯飛.移動數(shù)據(jù)庫中數(shù)據(jù)同步技術(shù)的研究[J].重慶科技學(xué)院學(xué)報(bào)（自然科學(xué)版）,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] 盧福子.移動數(shù)據(jù)庫同步技術(shù)研究[D].北京:清華大學(xué),2004.

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

[7] 李東,曹忠升,馮玉才,等.移動數(shù)據(jù)庫技術(shù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究,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技術(shù)研究[J].湖北大學(xué)工學(xué)報(bào),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:一個弱一致性的復(fù)制數(shù)據(jù)庫系統(tǒng)[J].計(jì)算機(jī)工程,1999,25（4）:45-47..

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

[10] 李東,馮玉才,王元珍.適于移動數(shù)據(jù)庫的客戶/服務(wù)器體系結(jié)構(gòu)研究[J].計(jì)算機(jī)應(yīng)用研究,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年獲碩士學(xué)位,現(xiàn)為中國民航局第二研究所高級工程師,主要研究領(lǐng)域?yàn)闄C(jī)場信息集成技術(shù)、計(jì)算機(jī)仿真、數(shù)據(jù)庫技術(shù)等。

LUO Xiao was born in Chongqing,in 1970.He