普适环境中面向推理的上下文缓存置换算法

A Reasoning-Oriented Context Replacement Algorithm in Pervasive Computing

上下文缓存是减少上下文信息访问开销、降低信息传输数量、缓解连接中断引起的程序不可用性的有效途径.面向推理的上下文缓存置换算法CORA的目标是使上下文缓存达到较高命中率,有效节省普适计算中传输上下文的开销.CORA采用状态空间对低级上下文到高级上下文的推理进行建模,对各种上下文推理方法具有普遍适用性.CORA算法分为两个部分:1)在缓存端,该算法计算低级上下文的访问概率和预计失效时间,获得数据的缓存价值,作为上下文缓存置换的依据,以提高缓存的命中率;2)在传感器端设置相应的可变化范围,当传感器读数超出该范围时,主动更新缓存,以保证缓存数据的一致性.模拟实验将CORA和经典的缓存置换算法LRU进行对比,分别通过改变缓存容量、对上下文访问概率的不均匀程度和上下文更新访问比来考察两种算法的命中率,结果显示,当缓存容量相对上下文总数较小、访问概率分布较不均匀、更新访问比较高的情况下,CORA的命中率大大高于LRU.由此证明,CORA更适用于较为动态的普适计算环境.

Using context cache is an effective way to reduce the overhead of context access, decrease the amount of information transmission and improve the application availability when disconnections occur. A reasoning-oriented context replacement algorithm （CORA） is presented, which aims at promoting the hit rate of context cache and reducing the overhead of context transmission. CORA adopts context state space as a general model for diverse context reasoning methods used to infer highlevel contexts from low-level contexts. CORA is composed of two parts. 1） at the cache end, to promote hit rate, it computes the estimated access probability and invalidation time of low-level contexts to get their caching values as the criterion for cache replacement; 2） at the sensor end, to maintain data consistency, an error bound is set to trigger a proactive update when the sensor reading is out of the bound. Simulation experiments are conducted to compare CORA with the classical cache replacement algorithm LRU （least recently used）. Their hit rates are compared by changing the cache size, unevenness of contexts＇ access probabilities and update-access ratio. The results demonstrate that CORA can get higher hit rate than LRU when the cache size is small, contexts＇ access probabilities are uneven, and update-access ratio is high, which means that CORA is more suitable for pervasive computing environment.