2. 华南理工大学 软件学院, 广州 510006
针对当前语义缓存一致性维护策略难以适应移动终端频繁切换、断接的问题, 提出使用移动代理技术来维护语义缓存一致性的方法.首先, 基于SMC-架构设计移动代理MSSAg和MTAg; 其次, 提出无小区切换和有小区切换2种情况下进行缓存一致性维护的方法.实验结果表明, 所提方法在减少缓存一致性恢复时间和降低网络通信量方面较其他算法有明显的改善, 可以有效地在频繁断接、移动和切换的环境中进行语义缓存一致性维护.
2. School of Software Engineering, South China University of Technology, Guangzhou 510006, China
Current semantic cache consistent maintenance strategy is difficult to adapt to frequent mobility, hand off and disconnect network environments. The article propose a new semantic cache scheme using mobile agent technology to maintain the cache consistency. Firstly, mobile agents MSSAg and MTAg are designed based on SMC-architecture. Secondly, the process of maintain cache consistency is discussed in two cases: without hand-off and with hand-off. Experiments show that the proposed cache maintenance method could reduce cache consistency restore time and save data communication cost effectively. It is particularly efficient for using in frequent mobility, hand off and disconnect network environments.
移动计算是消息传递技术和无线通信技术的融合，它使计算机或其他信息智能终端设备在无线环境下实现数据传输及资源共享.这种网络环境下，为终端设置缓存可以有效节省带宽资源并提供离线服务.然而，两层结构下的缓存维护方法存在通信开销大的问题，并且较少考虑小区切换.笔者采用移动代理技术进行缓存一致性维护，以适用于频繁切换的移动环境.
语义缓存方面的研究主要集中在一致性维护、缓存理论、预取策略和替换算法. Ren等[1]提出了查询与缓存匹配的判定定理以及查询裁剪算法.吴婷婷等[2]对查询导出和匹配进行了研究.李冬等[3]分析了语义缓存段与更新语句的条件谓词及投影属性的关系，将更新粒度裁剪至属性级.移动代理技术常用于进行分布式查询，跟踪移动对象和最优化无线通信开销等. Sergio Harri等[4]提出利用代理来最优化无线通信代价. Sergio Ilarri等[5]提出利用移动代理追踪移动对象位置.胡海洋等[6]提出基于代理的无线Web访问机制，有效避免了不必要的Web页面更新操作.
已有研究较少考虑切换情况下的语义缓存一致性维护问题，笔者提出使用移动代理技术来维护语义缓存一致性，并设计了各代理功能.分析了移动代理在无小区切换和有小区切换下的缓存一致性维护方法，仿真实验验证了算法的有效性.
1 基于代理的语义缓存一致性维护1.1 相关定义定义1 语义缓存项可表示为5元组：(SCID，SR，SA，SP，SVS).其中，SCID为索引号，SR为关系表，SA为投影属性集，SP为查询条件合取式，SVS为缓存项是否发生更新标志位：0表示无更新；1表示有更新.
定义2 MTAg-array：该队列用于存储由MSSAg代理创建的，或者当前处于运行状态的，或者从其他移动支持站(MSS，mobile support station)迁移过来并激活运行的MTAg代理.
定义3 MTAgUPD-queue：每个MTAg都有其对应的MTAgUPD-queue队列，用于存储缓存数据更新操作，更新结束后队列清空.
定义4 最大等待时间WTmax：设终端当前移动速度为V, 由该终端代理MTAg生成的子代理MTAg_sub在下一小区中等待的最大时间
设计移动代理MSSAg和MTAg，以支持移动、断接环境下的缓存维护，如图 1所示.利用移动代理进行MSS和移动终端(MT, mobile terminal)中缓存的一致性管理.当MT断接网络时，代其维护缓存一致性；当MT发生小区切换时，移动代理会预先到达该小区，等待用户的到达、激活并提供服务.代理功能说明如下.
|
图 1 移动代理关系图 |
MSSAg代理——驻守在MSS并负责MTAg的创建、销毁、接受与发送，维护本地MTAg队列的内容.生成缓存失效报告并通过广播信道发送出去.
MTAg代理——对每个终端生成MTAg并保存在MTAg-array中. MTAg终端维护其在MSS中保存的语义缓存备份的数据一致性.不管MT是否在线，MTAg都会根据服务器传来的最新数据修改情况，更新缓存的状态标志位Svs；并执行语义裁剪，将数据库更新转化为一系列能够在语义缓存局部数据库上执行的SQL语句，存储在MTAgUPD-queue中.当MT重新连接时，MTAg可以让MT读取MTAgUPD-queue队列，从而快速地将MT的局部缓存内容更新到最新值，以实现同步，达到同步后清空MTAgUPD-queue队列. MTAg还可以生成子代理，根据当前运行方向和速度，提前移动到下一个可能小区的MSS中等待用户的到达，当用户正式到达时，该MTAg就会被激活运行；反之，在经过最大时间的等待后销毁.
1.3 无切换情况在同一小区中，对于移动和断接情况，基于Agent技术的缓存维护流程如图 2所示.
|
图 2 无切换情况时基于代理的缓存维护流程 |
1) MSSAg周期性接收服务器的更新信息.
2) MSSAg将该信息分发给MTAg.
3) MTAg接收到数据更新信息，将该更新与其语义缓存描述进行匹配.将匹配的语义缓存项的Svs设为“1”，生成可运行于缓存中的与原更新语句等价的更新语句序列，并保存在MTAgUPD-queue中.
4) MSSAg根据MTAg维护的缓存有效情况，生成缓存失效报告，通过广播信道发送给小区中的各终端.
5) 在线终端通过收听广播失效报告，获得其缓存数据的有效性信息，对于无效的缓存项，终端可以立即更新；或者选择懒惰法，只对该缓存项进行失效标记，待需要时再进行更新.
6) 离线终端无法收听广播信息，当再次连接且离线时长大于广播周期时，通过读取并在缓存中运行更新操作序列，将局部缓存更新到最新状态，从而一致性也可得到维护.
1.4 有切换情况在终端移动并发生小区切换时，基于Agent技术的缓存维护流程如图 3所示.
|
图 3 有切换情况时基于代理的缓存维护流程 |
1) MSSAg周期性接收服务器的更新信息.
2) MSSAg和MTAg根据服务器的更新信息进行语义缓存一致性判断，生成更新语句序列.
3) MSSAg根据缓存有效情况，生成失效报告，并通过广播信道发送给小区中的移动终端.
4) 在线终端通过收听广播失效报告，获得其缓存数据的有效性信息.如果某缓存项无效，处理方法同1.3小节5).
5) 离线终端无法收听广播信息，再次连接且离线时长大于广播周期时，通过读取并运行更新操作序列恢复缓存至有效状态.
6) 终端的MTAg代理根据该当前的移动方向和速度估算[7]出下一个即将到达的小区和到达时间.然后生成子代理MTAg_sub，其职责有：① 移动至该小区，等待移动终端的到来，同时分配子代理的最大等待时间WTmax；② 当终端到达小区时，MTAg_sub即被激活并转为就绪状态；③ 否则，超时则MTAg_sub自行销毁.
7) 实际场景中，往往无法准确获取终端的方向，则使用位置判定表[7]就无法推算出未来小区和到达时间.此时MTAg_sub职责为：① 移动至所有相邻的小区中，等待终端并分配子代理的最大等待时间WTmax；② 移动终端到达小区时，MTAg_sub被激活并转为就绪状态；③ 超时则该MTAg_sub自行销毁.
8) 处于就绪状态的MTAg_sub，并不能够直接运行，因为其缓存一致性在等待时间内没有与服务器进行同步.因此，MTAg_sub需要向原MTAg发送验证缓存的请求并进行一致性验证，完成后转为运行状态.
2 实验及性能分析为验证算法性能，进行仿真实验，每次运行1 000次取平均结果进行分析，使用J2SE平台之JDK 1.6编程. 表 1给出了实验的主要参数及假设.
|
表 1 实验参数设置 |
实验1 无切换情况下实验结果及分析
首先，模拟缓存一致性维护过程，比较了文中提出的基于更新队列与粒度细化一致性维护算法与传统算法[8]和两层结构粒度细化算法(简称两层算法[4])在网络通信量方面的性能，实验结果如图 4所示.
|
图 4 3种算法的数据通信开销比较 |
对缓存中50~400个待更新元组进行一致性维护，实验表明文中算法和两层算法比传统算法有更低的网络通信量，且增长幅度也较小.这是因为传统算法对待UPDATE更新操作，先在缓存中执行DELETE操作，再执行SELETE操作以获取更新后的元组，再将它们插入到缓存中.因此只需要修改个别属性值的，却变成了整个元组的操作，从而增加了通信量.
随着更新元组数的增加网络通信量也会增加，但是由于文中算法采取粒度细化策略和更新队列机制，只有当产生补充查询时才会明显增加网络通信量.如图 5所示，补充查询率越接近50%，两算法在通信开销方面越接近，此时补充查询本身所产生的数据传输和缓存合并代价与其节省的开销相当.因此，当连续遇到补充查询，或者更新涉及的元组较少，则不妨采用类似传统方法来进行更新.
|
图 5 补充查询率变化条件下算法的数据通信开销比较 |
图 6给出了文中算法、传统代理算法[6]以及不采用代理算法[8]，在断接时间变化的情况下缓存恢复时间开销.广播失效报告周期为30 s，当断接时间小于30 s时，缓存维护时间都很低；当时间大于30 s时，Without-Agent策略无法再按照失效报告来维护缓存，因此会认为其缓存无效，需要重新验证或删除.为画图比较，给其设置了一个相对较大的数来表示. SMC-Agent策略利用MSSAg生成更新操作序列，即使在终端离线情况下，缓存一致性也可得到有效维护.而一般基于代理的算法是基于全属性的，没有进行更新裁剪，会导致一致性维护时数据传输开销大的问题.
|
图 6 3种算法的缓存一致性恢复时间开销比较 |
实验2 有切换情况下实验结果及分析
移动环境下用户位置经常变化，切换小区时有发生，这部分的模拟实验中，考虑2种情况下的缓存恢复，分析各自的“对接及缓存验证时间4”TJV.
情况1：WT＜WTmax，TJV = TJ1 + TV1.其中，TJ1为MT到达后与MTAg_sub确认的时间开销；TV1为MTAg_sub与父代理MTAg进行缓存数据迁移所耗费的时间开销. TJ1与TV1的值与有线和无线带宽相关，并且TV1的大小还与缓存项数目和更新率成正比.
情况2：WT≥WTmax，TJV = TJ2 + TV2.其中，TJ2=20 ms为本地MSS借助VLR与HLR和MT曾连接的上一MSS联系，通知其将相应的MTAg发送过来的时间开销；TV2为该MTAg进行缓存数据迁移所耗费的时间开销. TV2的值与有线带宽相关，并且还与缓存项数目和更新率成正比.
由表 2可见，2种情况下的平均对接及缓存验证时间分别是20.065 7 ms和38.531 8 ms，这样的时间开销还是可以接受的.当缓存更新率增加时，TJV也会成正比增加，如图 7所示.但是增加幅度不大，因为MTAg_sub是个轻量级代理，没有携带具体的缓存数据；当相应移动终端确认到达时，再去原MTAg处获取缓存信息，移动代理携带缓存数据迁移是发生在有线网络中的，实验中的带宽选取2 MB/s，实际场景中往往更大.
|
|
表 2 2种情况下的TJV比较 |
|
图 7 变化更新率条件下的TJV比较 |
在移动环境中，移动用户经常发生小区切换，与网络也会频繁断接.使用移动代理技术来维护语义缓存一致性，设计了两类移动代理：MSSAg和MTAg，对无小区切换和有小区切换两种情况下移动代理如何进行缓存一致性维护给出具体方法.实验表明，文中算法在网络通信量和缓存恢复时间方面较其他算法都有明显的改善.应用移动代理技术，在频繁断接、移动和切换的环境能够有效地进行语义缓存维护.
缓存预取策略在节省带宽资源和移动设备能量方面有重要意义，位置相关查询可以为移动终端提供与位置相关的个性化服务.后续工作将研究语义缓存在位置相关查询以及预取策略中的应用.
| [1] | Ren Q, Dunham M H, Kumar V. Semantic caching and query processing[J].IEEE Transactions on Knowledge and Data Engineering, 2003, 15(1): 192–210. doi: 10.1109/TKDE.2003.1161590 |
| [2] |
吴婷婷, 周兴铭. 基于语义缓存的移动查询导出[J]. 计算机学报, 2002, 25(10): 1104–1110.
Wu Tingting, Zhou Xingming. Extracting query results from semantic cache[J].Chinese Journal of Computers, 2002, 25(10): 1104–1110. doi: 10.3321/j.issn:0254-4164.2002.10.016 |
| [3] |
李东, 袁应化, 叶友, 等. 基于属性更新的语义缓存一致性维护算法[J]. 华南理工大学学报:自然科学版, 2009, 37(5): 139–144.
Li Dong, Yuan Yinghua, Ye You, et al. Algorithm of semantic caching coherency maintenance based on attribute update[J].Journal of South China University of Technology: Natural Science Edition, 2009, 37(5): 139–144. |
| [4] | Sergio H, Eduardo M, Arantza I. Monitoring continuous location queries using mobile agents[C]//Manolopoulos Y, Návrat P(Eds.). ADBIS 2002, LNCS, 2435: 92-105. |
| [5] | Sergio I, Eduardo M, Arantza I. Location-dependent queries in mobile contexts: distributed processing using mobile agents[J].IEEE Transactions on Mobile Computing, 2006, 5(8): 1029–1043. doi: 10.1109/TMC.2006.118 |
| [6] |
胡海洋, 胡华, 凌云. MAWA:基于移动Agent的一种高效可靠无线Web访问机制[J]. 计算机研究与发展, 2008, 45(4): 636–645.
Hu Haiyang, Hu Hua, Ling Yun. MAWA: an efficient and reliable web access scheme in mobile wireless environments based on mobile agents[J].Journal of Computer Research and Development, 2008, 45(4): 636–645. |
| [7] | Liang Rubing, Xia Qiang. A study of mobile terminal's cache management and channel allocation[J].Procedia Engineering, 2012, 29: 744–748. |
| [8] | Wan Hai, Li Lei. Design and implementation of semantic caching coherency control scheme toward distributed environment[C]//Proceedings of the 6th International Workshop on Advanced Parallel Processing Technologies. Hong Kong Springer, 2005: 41-51. |