基于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