论文部分内容阅读
基于位置服务依赖于对移动对象的高效管理。不确定性是移动对象最重要的特点之一,表现在属性不确定性,位置不确定性和存在不确定性等。针对移动对象的不确定性,需要将查询结果的不精确性限定在一定的范围内,以便于提供更可靠和优质的位置服务。已有的不确定移动对象查询和更新的研究中,主要侧重于提高查询效率以提供实时性的位置服务,存在更新效率低下的问题。另外在查询过程中,无法适应移动对象属性动态变化。本文研究了不确定移动对象的查询与更新技术,提出了室内障碍环境下支持属性动态变化的多目标优化查询算法和频繁位置更新的不确定移动对象索引结构,主要的研究工作如下:(1)将不确定移动对象多目标优化查询算法与室内障碍空间相结合,研究分析现有的室内障碍环境下移动对象距离计算模型,改进了基于可视区域的距离计算模型。提出一种支持目标对象属性动态调整的多目标优化算法DSP-Topk(Dynamic and Support Pruning Topk)。算法面向具有多属性的不确定移动对象,采用预处理的裁剪策略降低目标对象集合规模,引入目标对象动态调整机制,提出动态集和静态集的概念。实验结果验证了DSP-Topk算法的正确性和查询性能优势。(2)在已有支持移动对象不确定性索引TPU-tree的基础上,提出一种支持移动对象运动轨迹关联的索引结构GTPU-tree(Group Time-Parameterized Uncertain-tree)。GTPU-tree利用空间轨迹相似度来描述移动对象轨迹的相似性,将相似度大的移动对象划分为一个群组。基于GTPU-tree提出了一种混合更新策略。混合更新策略通过减少位置更新的次数降低更新代价,另外周期性检测同群组中移动对象轨迹相似性,保证同一个群组中的移动对象具有较高的轨迹相似度。实验验证了GTPU-tree索引在不确定移动对象频繁位置更新时降低更新代价的优势。(3)在GTPU-tree的基础上进一步思考改进提出HGTPU-tree(Hash Group Time-Parameterized Uncertain-tree)索引。通过零级索引哈希表支持自底向上的查询方式,在不确定移动对象位置更新时,缩短叶子节点的查询时间,并通过群组划分减少更新次数,从而降低更新代价;在内存开销方面,HGTPU-tree利用同步更新机制解决了已有自底向上更新的索引由于内存开销过大,特别在移动对象数目较多时,系统稳定性下降的问题。