林业位置服务平台中基于道路网络的KNN查询研究

摘要

林业信息化建设是推进由“数字林业”向“智慧林业”转变的重要保障，迫切需要将成熟的、先进的技术和创新的理念相结合以更好地服务于林业。基于位置服务是指采用无线定位、GIS、Internet、无线通讯、数据库等相关技术交叉融合的一种基于空间位置的移动信息服务，是通过获取移动用户的位黄信息为用户提供包括路径引导、位置查询、应急指挥、紧急呼叫等众多服务的技术基础，在紧急救援、个人定位、车辆导航、人员调度等方面得到广泛的应用，具有良好的发展前景。将基于位置服务技术引入到林业中，对推动林业信息化建设，加快“智慧林业”发展进程具有重要的支撑作用。
　　本文针对林业部门在人员管理、应急指挥方面智能化管理的迫切需要，分析了构建林业位置服务平台的关键技术，对位置服务中基于道路网络的移动对象K最近邻查询关键问题展开深入研究，并构建了林业位置服务监测平台，为人员管理和应急指挥提供人员定位、路径规划、指挥调度等提供支撑。
　　论文主要研究工作和创新点有以下几个方面:
　　(1)阐述了基于位置服务的关键技术，分析各关键技术环节需要解决的问题，针对林区环境特点，确定本文采用的研究方法和研究手段;
　　(2)道路网模型是实现基于道路网络K最近邻查询的基础，在分析已有道路网模型优缺点的基础上，基于林区道路网特点，提出基于路径建模的道路网络模型，能够表示单、双行路以及十字路口的转向规则;
　　(3)在基于道路网络的移动对象索引中，道路网和移动对象并不是孤立存在的，因此，在索引结构中需要对道路网和移动对象同时索引，从索引结构查询性能和更新性能两方面综合考虑，应将静态的道路网和动态的移动对象分别存储，基于这一思想，本文提出具有三层结构的索引结构，利用R树对静态的道路网络进行索引，使用hash表和邻接列表对移动对象及道路边连接关系进行索引;
　　(4)基于已经建立的道路网模型和移动对象索引结构，研究基于道路网络的K最近邻查询问题，为了满足位置服务平台中对查询请求的快速响应的要求，一方面利用预计算技术计算各道路边节点之间的最短路径;另一方面，考虑到查询时通常将方向关系作为查询约束条件，将方向关系约束条件引入到最近邻查询问题中，提出基于方向关系约束的K最近邻查询算法，进一步提高算法的查询速度;通过实验对比分析，提出的基于预计算技术的PC_KNN算法和基于方向约束的CDR_ CKNN算法都表现出良好的查询性能。
　　(5)以“基于物联网的监测技术及在林业上的应用研究项目”为依托，基于林业部门现有的GPS对讲设备、项目搭建的无线传感器设备、无线电台等通信设备，基于位置服务技术研究思路，运用WebGIS技术、GPS定位技术、无线通信技术和空间数据库技术，构建林业位置服务平台，实现林区基础地理信息的显示、查询、浏览等基本操作以及人员位置数据采集、位置监控、轨迹回放、调度指挥等基于位置服务的应用。
　　通过研究位置服务平台在林业建设中的关键技术，能够解决护林员、消防车辆、森林火点的定位、监测与跟踪、数据的获取和传输、数据的存储与管理、信息查询、地图显示等问题，能够为日常的管理工作提供科学、准确、高效的解决方案;通过研究基于道路网络的K最近邻查询问题，能够完善基于位置服务的查询请求，为实现人员管理、制定防火指挥决策提供科学有效的指导。因此，本文的研究对丰富林业信息化建设内容，加快林业信息化建设进程起到推动和促进作用。

目录

摘要

1 绪论

1．1 课题背景及研究意义

1．1．1 智慧林业与林业信息化

1．1．2 基于位置服务简介

1．2 基于位置服务(LBS)在林业领域应用状况

1．3 基于道路网的KNN查询国内外文献综述

1．3．1 道路网模型研究现状

1．3．2 道路网中移动对象索引研究现状

1．3．3 基于道路网络的移动对象KNN查询研究现状

1．4 本文研究的目的和意义

1．5 本文主要研究内容及拟解决关键问题

1．5．1 本文研究内容

1．5．2 本文拟解决的关键问题

1．6 研究方法与技术路线

1．6．1 研究方法

1．6．2 技术路线

2 林业位置服务平台关键技术

2．1 定位技术

2．1．1 卫星定位技术

2．1．2 基于网络的定位技术

2．2 空间数据库

2．2．1 空间数据库概述

2．2．2 空间数据查询及索引

2．3 通信技术

2．3．1 常用通信方式概述

2．3．2 森林通信系统解决方案

2．4 地理信息系统

2．4．1 地理空间数据

2．4．2 地理信息系统的基本功能

2．4．3 GIS空间数据管理方法

2．5 本章小结

3 道路网模型

3．1 林区道路网概况

3．2 道路网建模相关问题

3．2．1 道路网数据的分类

3．2．2 图形理论

3．2．3 图的表示方法

3．3 现有道路网模型分析

3．3．1 图表示模型

3．3．2 2D表示和图表示混合结构

3．3．3 多种模型混合

3．4 改进的基于路径的道路网模型

3．4．1 道路网及移动对象数据模型

3．4．2 道路网及移动对象数据结构

3．5 本章小结

4 道路网环境下的移动对象索引

4．1 移动对象索引相关问题

4．1．1 移动对象信息存储

4．1．2 移动对象运动空间

4．2 移动对象索引技术

4．2．1 IMORS索引

4．2．2 FNR-Tree索引

4．2．3 MON-Tree索引

4．2．4 ANR-Tree索引

4．3 基于路径的移动对象索引结构设计

4．3．1 索引结构设计

4．3．2 RRN-Tree索引结构的插入和删除操作

4．3．3 索引结构的更新

4．4 本章小结

5 基于道路网的移动对象CKNN查询算法设计

5．1 最短路径计算方法

5．1．1 最优路径分析模型

5．1．2 Dijkstra算法

5．1．3 A*算法

5．2 最短路径预计算处理

5．2．1 预计算技术

5．2．2 预计算路径交叉点最短路径

5．3 基于路径建模索引的KNN查询算法

5．3．1 相关定义

5．3．2 INE_KNN算法

5．3．3 PC_KNN算法

5．3．4 INE KNN和PC_KNN实验对比

5．4 基于方向约束的CKNN查询算法

5．4．1 相关定义

5．4．2 基于方向谓词约束的KNN查询算法设计

5．4．3 CKNN查询实现

5．4．4 实验对比及分析

5．5 本章小结

6 林业位置服务平台构建

6．1 林业位置服务平台空间数据存储与管理

6．1．1 林业位置服务平台数据内容

6．1．2 林业位置服务平台数据模型与存储

6．2 林业位置服务平台体系结构

6．2．1 林业位置服务平台组成

6．2．2 林业位置服务平台体系结构

6．3 林业位置服务平台主要功能实现

6．3．1 林业位置服务平台软件开发环境

6．3．2 最短路径分析

6．3．3 K最近邻查询分析

6．3．4 移动对象的K最近邻查询

6．4 本章小结

结论

参考文献

攻读学位期间发表的学术论文

致谢

声明