A Reasoning-Oriented Context Replacement Algorithm in Pervasive Computing

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 high-level 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.