动态环境下移动对象导航系统相关技术的研究

论文摘要

近年来,可穿戴计算机、移动计算及无线自组网技术飞速发展,应用移动对象的场合越来越多,另一方面,GPS技术和传感器技术快速发展,为移动对象提供位置相关服务的导航系统有了越来越广泛的应用。本文中主要针对移动对象导航系统的范围概率查询和路径规划两个主要模块进行了论述。动态环境下,受通信带宽、移动对象本身、数据库存储空间等的限制,使用传统数据库技术来实时地追踪移动对象并存储其精确位置是不现实的,只能更新并记录特定时刻的信息,对于没有精确记录的时刻的位置范围查询,其结果必然是不精确的。本文的目标就是对这种不精确性进行估计,然后给出一个概率结果。文中提出了特定的模型、支持该模型的索引,以及相应的查询算法。传统的路径规划算法针对的是静态的环境,即以环境不发生改变为前提。而现实的移动对象位置是不断变化的,其本身所用的导航系统面临的是不断改变的环境,若还按原来的算法,当环境信息发生改变时,则只能先更新环境信息,然后再重新运行一遍算法,这无疑是低效的——算法的上一次运行对本次运行没有任何帮助,两次运行在时间上是基本相当的。在大自然中,蚂蚁为了觅食在不断改变的环境下仍能找到较优的路径,受此启发的蚁群算法特别适合解决动态路径规划问题,它能够在改变的环境中自适应地找到新的最优路径,但是现有的蚁群算法也有许多不足之处,如计算时间相对较长,受堵塞路段负反馈影响而收敛速度变慢等问题,为了克服以上的缺点,本文在综合现有蚁群算法基础上,提出了用混合蚁群算法解决动态环境路径规划问题的框架,引入了“局部抖动技术”,最后通过仿真实验证明本课题所提出的基于蚁群算法的动态路径规划算法是可行的,融合了局部抖动技术的改进蚁群算法确实在某些特定的动态环境下能够提高性能。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题来源及意义
• 1.2 移动对象导航系统简介
• 1.3 研究现状
• 1.3.1 移动对象数据库研究现状
• 1.3.2 蚁群算法研究现状
• 1.4 本文主要研究内容及论文结构
• 第2章 移动对象范围概率查询
• 2.1 概述
• 2.2 移动对象查询处理程序
• 2.2.1 查询的分类
• 2.2.2 信息更新频率的控制
• 2.3 本课题解决方案
• 2.3.1 数据模型
• 2.3.2 索引及相关存储结构
• 2.3.3 查询处理算法
• 2.4 本章小结
• 第3章 蚁群算法求解动态路径规划
• 3.1 最优路径规划
• 3.1.1 图论及相关概念
• 3.1.2 对路径规划问题的描述
• 3.2 Dijkstra改进算法求解路径规划
• 3.3 蚁群算法概述
• 3.3.1 问题的描述
• 3.3.2 几种主要的蚁群算法
• 3.3.3 蚁群算法的理论探索
• 3.4 用改进的蚁群算法解决动态路径规划问题
• 3.4.1 信息素下界
• 3.4.2 状态转移规则
• 3.4.3 全局信息素更新规则
• 3.4.4 局部抖动技术
• 3.5 本章小结
• 第4章 仿真实验及结果分析
• 4.1 仿真实验
• 4.1.1 测试平台
• 4.1.2 测试方法
• 4.2 结果分析
• 4.2.1 关于参数的设置
• 4.2.2 三种模式的性能比较与分析
• 4.3 本章小结
• 结论
• 参考文献
• 致谢