基于洋流模型的水下传感器网络实时定位算法

针对近海监控领域内水下传感器网络的节点随着海洋运动具有流动性的问题,提出了基于洋流模型的水下传感器网络实时定位算法(RTLC).利用洋流模型表示节点的运动模型消除流动性对定位造成的影响,成功模拟了节点在水中的移动速度.通过卡尔曼预测方法结合观测值与估计值优化运动模型,使其更贴近节点运动规律.采用信息记录机制及列表更新机制保证信息的时效性从而提高了定位准确度.通过仿真分析,RTLC算法性能优于基于移动预测的大规模水下传感器网络可扩展定位算法(SLMP),具有较高的定位覆盖度,较低的平均定位误差及平均通信能耗.     

NU2RA:一种路网中不确定移动对象范围查询分析方法

目前移动对象的各类查询研究大多假设对象的位置确切可知,但实际上除了更新时刻外,其他时间对象的位置只是一个可能的范围.因而大多数基于确切位置的查询算法并不可行.而现有的涉及不确定性的查询方法大多仅针对自由移动的不确定查询或者不确定目标.针对道路网中查询和目标位置均不确定的情况,提出了一种NU2RA分析方法.根据查询范围对网络进行划分,用分布码表示目标的可能分布,得到不确定目标与不确定查询范围的22类拓扑关系,并且给出了目标在不确定查询范围内的概率计算方法.该方法不依赖于具体的不确定移动对象模型,对不确定历史轨迹和不确定的近期将来运动趋势同样适用.     

一种移动对象数据库的自适应更新方法

更新频率的选择是移动对象数据库领域的一个难题.基于局部线性化思想,给出移动对象的常速率及常加速度-常角速度动态模型.接着,模糊逻辑定量化方法被用于描述移动对象的状态及推算误差.综合考虑推算距离误差、速度变化、时间间隔等多种因素,一个"或"门计算单元被用以判断是否需要更新.利用地图匹配的计算结果,根据道路的特征,提出自适应选择动态模型的方法.最后,用跑车实验验证了所述算法性能.本算法高度可配置,能够在自适应选择更新频率的情况下,较忠实记录移动对象状态信息.     

一种新的道路网络连续查询处理方法

基于道路网络的连续k近邻查询是移动对象数据库领域的研究重点和热点.提出了一种新的道路网络有向图模型,通过引入有向网络空间度量,利用基于内存的格网索引和线性链表结构来对移动对象当前位置和道路网络有向图模型进行存储和管理;基于有向距离度量提出了单向网络扩展(DNE)算法,以减少连续k近邻查询的网络扩展搜索代价.实验结果表明,DNE算法性能优于现有的连续k近邻查询处理算法.     

一种基于运动预测的蒙特卡罗定位算法

以蒙特卡罗算法为基础的无线传感器网络移动节点定位算法普遍存在定位误差较大的问题.针对实际应用中一般的运动模型,提出一种基于运动预测的蒙特卡罗定位(MCLMP)算法,通过构建节点运动模型,进行位置预测和滤波,并对过滤后的值进行加权计算.仿真结果表明,MCLMP算法相比以往算法定位精度提高了30％以上.     

一种基于固定网络的移动对象运动轨迹索引模型

实际应用中移动对象通常运动在城市固定道路上,针对此特征研究人员已提出一些相关索引模型,但都存在一定的局限性,表现为索引模型只管理对象的历史位置信息或实时位置信息以及只对窗口查询或轨迹查询进行优化.IMTFN是一种基于固定网络的移动对象运动轨迹索引模型,管理移动对象的实时位置信息和历史轨迹信息,并且有效优化窗口查询及轨迹查询操作.IMTFN由一个管理固定网络的2D R^＊-Tree、一组管理移动对象运动轨迹的1D R^＊-Tree以及记录移动对象实时位置信息的Hash结构组成.最后通过实验IMTFN分别与STR-Tree与FNR-Tree进行性能比较,证明IMTFN模型提供速度更快的查询操作.     

基于Kullback-Leibler分歧的变分滤波WSNs贝叶斯移动定位跟踪西

为了在降低资源能耗和带宽占用情况下,提高无线传感器网络WSNs移动目标定位跟踪的精度,提出了基于Kullback-Leibler分歧的变分滤波的WSNs贝叶斯移动目标定位跟踪算法。首先,利用高斯和Wishart分布在不考虑速度限制和方向移动限制情况下,构建WSNs移动定位的贝叶斯状态演化模型,并基于路径损耗模型构建移动目标定位的观测模型;其次,利用Kullback-Leibler分歧构建变分滤波的误差计算模型,通过周围激活节点实现移动节点目标的位置估计,设计了递归概率计算过程综合预测和更新两个过程,并实现了定位和目标跟踪的同步化;最后,通过仿真验证了所提模型在跟踪精度和资源节约上的优势。     

室内环境下基于IMM-EKF算法的移动目标定位

如何在视距(line-of-sight,LOS)与非视距(non-line-of-sight,NLOS)混合的室内环境中提高移动目标定位的精度,这是一项富有挑战性的工作.移动目标在室内环境移动时,其与传感器网络节点之间的信号传播在LOS与NLOS之间随机切换,导致移动节点定位精度下降.提出一种交互式多模型-扩展卡尔曼滤波(interactive multiple model-extended Kalman filter,IMM-EKF)定位算法.根据LOS?NLOS环境下不同的测距误差特性,在IMM框架中采用2个平行的卡尔曼滤波器(Kalman filter,KF)模型对测量距离同时进行滤波,根据滤波结果和测量值计算2个模型的似然概率,模型间的转换通过Markov链实现,2个KF滤波结果加权融合后获得IMM距离估计值.在EKF定位阶段,通过位置预测和更新估计出移动目标位置.仿真结果表明,IMM-EKF算法能够有效抑制NLOS对目标定位的影响,其定位精度优于单模型算法.     

WSN下一种基于时间序列分析的跟踪方法

针对Cricket室内定位系统在没有获得足够的距离信息时无法对移动目标进行准确定位的问题,提出了一种基于时间序列分析ARMA模型的方法。在距离信息不足时根据移动目标历史位置信息构造ARMA模型,得到预测位置,再根据预测位置结合距离信息进行目标定位。实验结果表明,在传感器网络中,该方法在移动目标跟踪上是可行和有效的。     

支持固定网络中频繁更新的移动对象混合索引模型

IMOFN是一种支持固定网络中频繁更新的移动对象混合索引模型,它由一棵描述固定道路网络的2D R*-Tree、一组对时间进行索引的1D R*-Tree和一个存储移动对象实时数据的Hash数组组成.IMOFN既管理了移动对象实时位置,支持位置的频繁更新;又保存了历史轨迹,提供了范围查询、拓扑查询以及轨迹查询等多种有效的实时和历史查询功能.通过实验与FNR-Tree和MON-Tree进行性能比较,证实了IMOFN模型高效的查询能力.     

基于公路网的移动对象数据库数据模型

移动对象数据库对大量移动对象的位置信息进行管理，能够支持传统数据库不能进行的时空查询，考虑到大多数移动对象的运动都固定在已知的路线中，基于公路网的移动对象数据模型、通过对公路网拓扑图的数字化转换，能够对移动对象进行有效的管理，该文采用实时平均法来反映每条线路的动态运行情况，对移动对象未来位置进行了精确预测。     

道路网中基于RRN-Tree的CKNN查询

现有针对基于道路网络的CKNN查询研究,主要是将道路网络以路段和节点的形式进行建模,转化成基于内存的有向/无向图,该模型存在2个问题:一个是道路网络中路段数据量大,导致索引结构分支过多、移动对象更新频繁;另一个是图表示方法不能很好地处理十字路口转向、U型转弯等交通规则。针对此问题,提出道路网中基于RRN-Tree的移动对象CKNN查询算法,包括索引结构设计和移动对象查询算法设计,采用路线对道路网建模,基于网络边扩展方式,实现复杂条件下的道路网络CKNN查询。实验结果表明,在各种网络密度和兴趣点对象分布密度下,与经典的IMA/GMA算法相比,基于RRN-Tree索引方法的查询性能提高1.5倍~2.13倍。     

Direction-aware KNN queries for moving objects in a road network

Recently more and more people focus on k-nearest neighbor (KNN) query processing over moving objects in road networks, e.g., taxi hailing and ride sharing. However, as far as we know, the existing k-nearest neighbor (KNN) queries take distance as the major criteria for nearest neighbor objects, even without taking direction into consideration. The main issue with existing methods is that moving objects change their locations and directions frequently over time, so the information updates cannot be processed in time and they run the risk of retrieving the incorrect KNN results. They may fail to meet users’ needs in certain scenarios, especially in the case of querying k-nearest neighbors for moving objects in a road network. In order to find the top k-nearest objects moving toward a query point, this paper presents a novel algorithm for direction-aware KNN (DAKNN) queries for moving objects in a road network. In this method, R-tree and simple grid are firstly used as the underlying index structure, where the R-tree is used for indexing the static road network and the simple grid is used for indexing the moving objects. Then, it introduces the notion of “azimuth” to represent the moving direction of objects in a road network, and presents a novel local network expansion method to quickly judge the direction of the moving objects. By considering whether a moving object is moving farther away from or getting closer to a query point, the object that is definitely not in the KNN result set is effectively excluded. Thus, we can reduce the communication cost, meanwhile simplify the computation of moving direction between moving objects and query point. Comprehensive experiments are conducted and the results show that our algorithm can achieve real-time and efficient queries in retrieving objects moving toward query point in a road network.

     

一种基于概率的路径预测与查询算法

研究了路网空间内的路径预测与查询技术,设计了基于统计信息和概率论的最优路径预测算法。实际应用中,路网错综复杂。提出可能路径集合的概念,并设计算法来提取当前路径预测涉及到的路网子网,减小路网规模和路径预测的复杂度。在空间网络环境下,现有移动对象位置预测技术主要针对短期预测,不能预测下一路口的交通情况。为了弥补这一缺陷,降低用户端的位置更新率,设计了路网移动模型来简洁描述提取自大量历史移动路径的移动统计特征,捕捉路口处转向模式。基于移动模型,提出了具有较高精度的交通预测模型来预测对象的运动路径。     

大数据环境下移动对象自适应轨迹预测模型

已有的轨迹预测算法针对移动对象运动模式,使用数学模型进行交通流模拟,难以对路网中的移动对象进行准确的描述.为了解决这一问题,提出基于隐马尔可夫模型(hidden Markov model,简称HMM)的自适应轨迹预测模型SATP(self-adaptive trajectory prediction model based on HMM),对大数据环境下移动对象海量轨迹利用基于密度的聚类方法进行位置密度分区和高效分段处理,减少HMM的状态数量.根据输入轨迹自动选取参数组合,避免HMM模型中隐状态不连续、状态停留等问题.实验结果表明,SATP模型在实验中表现出较高的预测准确性,并维持较低的时间开销.针对速度随机改变的移动对象,其平均预测准确率为84.1%;相同情况下,平均高出朴素预测算法46.7%.     

Path prediction and predictive range querying in road network databases

In automotive applications, movement-path prediction enables the delivery of predictive and relevant services to drivers, e.g., reporting traffic conditions and gas stations along the route ahead. Path prediction also enables better results of predictive range queries and reduces the location update frequency in vehicle tracking while preserving accuracy. Existing moving-object location prediction techniques in spatial-network settings largely target short-term prediction that does not extend beyond the next road junction. To go beyond short-term prediction, we formulate a network mobility model that offers a concise representation of mobility statistics extracted from massive collections of historical object trajectories. The model aims to capture the turning patterns at junctions and the travel speeds on road segments at the level of individual objects. Based on the mobility model, we present a maximum likelihood and a greedy algorithm for predicting the travel path of an object (for a time duration h into the future). We also present a novel and efficient server-side indexing scheme that supports predictive range queries on the mobility statistics of the objects. Empirical studies with real data suggest that our proposals are effective and efficient.     

基于后缀自动机的轨迹模式挖掘方法*

如何有效的从轨迹数据中挖掘轨迹模式和规律具有重要意义,本文基于交通路网研究移动对象轨迹预测,将序列分析方法和马尔科夫统计模型结合,提出了一种基于后缀自动机的变阶马尔科夫模型挖掘方法。该方法根据移动对象的历史轨迹数据进行学习训练,计算轨迹序列上下文的概率特征,建立序列的后缀自动机模型,结合当前实际轨迹数据,动态自适应预测将来的位置信息。实验结果表明：相比固定阶马尔科夫模型,随着阶数的增加（L>=2）,固定阶马尔科夫模型预测的精度逐步降低,而该方法能动态自适应,精度保持在81.3%左右,取得较好的预测效果;同时,该方法只需线性的时间和空间开销,大大降低了存储空间和时间,能实现大规模数据的在线学习。     

面向路网的移动对象全时态高效索引模型

针对现有索引模型的冗余搜索问题,考虑路网拓扑结构及交叉口转向约束条件,提出一种面向路网的移动对象全时态高效索引模型。采用添加临近路段信息的方法索引历史轨迹和实时位置信息,设计新型窗口查询算法,实现移动对象查找,并运用指数平滑法进行轨迹的预测。实验结果表明,该模型具有较好的更新及查询性能。     

分布式环境下大规模移动对象范围查询算法

移动对象的连续范围查询是许多基于位置的服务的核心问题。针对该问题,提出一种面向大规模移动对象并发范围查询的分布式搜索方法。首先,设计了一种由全局网格索引（GGI）和局部弹性四叉树构成的移动对象分布式动态索引（DDI）结构。其次,提出了一种基于DDI结构的分布式查询算法（DSA）,该算法首先引入了一种在移动对象和查询点的位置连续变化的情况下的查询结果增量更新策略;然后,在增量更新过程中引入一种面向多并发查询的共享计算优化策略,该策略能够根据已有计算结果对移动对象范围查询结果进行增量搜索。最后,基于德国路网模拟了3个具有不同空间分布的移动对象数据集,将DSA与NS(Naive Search)、GI(Grid Index)和分布式混合索引（DHI）进行对比。实验结果表明,与性能最好的对比算法DHI相比,DSA的初始查询时间减少了22.7%,增量查询时间减少了15.2%,性能优于对比算法。