关键词: 公路网, 移动终端, 位置相关查询, K 近邻, 缓存, 移动计算

Abstract:

The dynamic POIs ( Points of Interest) in highway networks are difficult to query. Most current researches focus only on the static POIs with the help of the Euclidean distance metrics,which are inefficient for the weak connection and frequent movement of mobile terminals in mobile computing environments. In order to solve this problem,a structure to store cell data objects is designed to describe the highway network graph model,and a continuous KNN ( K-Nearest Neighbor) query ( CQ-KNN) algorithm for mobile terminals is presented. For the purpose of improving the existing MKNN algorithm proposed by Wang et al,CQ-KNN algorithm combines the progressive probe and the edge information list retrieval,thus saving the cost of range query execution in MKNN algorithm when fixed layers are insufficient. Moreover,CQ-KNN algorithm employs the local cache strategy to support the continuous query of mobile terminals and adopts the cache consistency maintenance strategy based on the invalid broadcast location report. Simulated results show that CQ-KNN algorithm is superior to MKNN algorithm in terms of CPU processing speed and network response delay,and that it effectively supports the off-line approximate KNN query of mobile terminals.

Key words: highway network, mobile terminal, location-dependent query, K-nearest neighbor, cache, mobile computing