基于交通规则的道路网络中移动对象连续最近邻监视方法

摘要

本发明公开了一种基于交通规则的道路网络中移动对象连续最近邻监视方法，其包括以下步骤：S1、建立道路网络模型；S2、根据道路网络模型，建立查询对象q的扩展树并将其初始化，得到查询对象q的k近邻集合；S3、根据查询对象q的当前位置更新道路网络模型并返回步骤S2，实现对道路网络中移动对象连续最近邻的监视。本发明在q.result中保存了查询对象q最新的k近邻，当提出查询对象q的k近邻时，则将当前查询时间t以及查询对象集合{q}作为参数调用本方法，可以获得t时刻查询对象q最新的k近邻q.result。本发明会连续对道路网络和扩展树进行更新，使得本方法完全实用于道路网络中移动对象连续最近邻的监视。

说明书

技术领域

本发明涉及移动对象时空查询领域，具体涉及一种基于交通规则的道路网络中移动对象连续最近邻监视方法。

背景技术

随着移动计算的快速发展，出现了大量基于移动对象的应用，这些应用要求高效的移动对象时空查询。其中k近邻(k-Nearest Neighbor，简称k-NN)查询是移动对象数据库研究领域中一个基本问题，受到了研究人员的广泛关注。

早期的研究主要是针对静态数据空间，查询当前最近邻。随着应用的深入，产生了很多基于k-NN的扩展研究，连续最近邻查询(Continous k-NN，简写为CkNN)是其中最重要的一种扩展。它是指移动对象在空间中连续移动，查询能够实时地返回查询对象最新的k近邻。

早期提出的一些连续k近邻查询方法只针对欧氏距离空间，不能够用于道路网络的连续k最近邻查询。另有一部分研究被设计用于处理静态对象的连续最近邻查询，即查询对象保持静止。然而，这些方法存在问题是没有结合道路网络移动环境特征以及运动对象速度、方向固定，实用性差。

发明内容

针对现有技术中的上述不足，本发明提供的一种基于交通规则的道路网络中移动对象连续最近邻监视方法解决了现有k近邻查询方法在道路网络中的实用性差的问题。

为了达到上述发明目的，本发明采用的技术方案为：

提供一种基于交通规则的道路网络中移动对象连续最近邻监视方法，其包括以下步骤：

S1、获取移动对象和查询对象q，建立包含交通规则的道路网络模型，并得到道路网络拓扑结构；

S2、根据道路网络模型，建立查询对象q的扩展树并将其初始化，得到查询对象q的k近邻集合；

S3、根据移动对象和查询对象q的当前位置，以及道路网络拓扑结构更新道路网络模型；

S4、判断是否还需对查询对象q的最近邻进行监视，若是则返回步骤S2，否则结束监视，完成对道路网络中移动对象连续最近邻的监视。

进一步地，道路网络模型包括道路模型T_edge、道路交点模型T_node、移动对象模型T_obj和查询对象模型T_query；

道路模型T_edge为6元组(rid,<n_s,n_e>,<e_i.w_p,e_i.w_n>,<s_pmax,s_nmax>,S_obj,e.IL)，其中rid是该道路的编号；<n_s,n_e>分别是该道路的起点和终点；<e_i.w_p,e_i.w_n>分别是该道路正方向及反方向的权值；<s_pmax,s_nmax>分别是该道路正方向以及道路反方向最大速度限制；S_obj是该道路上当前移动对象集合；e.IL是受道路影响的查询列表，它是三元组<q,n,d>的列表，n是该道路起点n_s或者终点n_e，d为一个数字，其表示查询对象q受到该道路影响，影响区间为该道路从节点n出发d的范围，即该道路从n出发d范围内的对象都属于查询对象q的k近邻集合；

道路交点模型T_node为2元组(conid,rules)，其中conid表示该连接id；rules表示该连接处的交通规则集合<RoadID_from,END_from,RoadID_to,END_to>；RoadID_from和RoadID_to分别表示移动对象将要离开和进入的道路id，END_from为一个布尔型数据，表示移动对象离开道路RoadID_from时是否处于该道路的终点n_e，如果处于道路终点，则END_from的值为1，否则END_from的值为0；END_to表示移动对象进入道路RoadID_to时是否处于该道路的终点n_e，如果处于道路终点，则END_to的值为1，否则处于道路起点，END_to的值为0；

移动对象模型T_obj为5元组(oid,e_j,t_u,dist,v_i)，其中oid表示移动对象的编号；e_j表示该移动对象所处的道路；t_u表示该移动对象最近的更新时间；dist表示该移动对象在t_u时刻与其所在边e_j的开始节点n_s之间的距离dist；v_i表示该移动对象在t_u时刻的移动速度，速度为正表示移动对象从起点向终点移动，反之则表示移动对象从终点向起点移动；

查询对象模型为T_query，包括移动对象的信息、查询对象q的当前kNN集合q.result，查询对象q到第k个最近邻的距离q.kNN_dist，以及查询对象q的扩展树T_q。

进一步地，步骤S2具体包括以下步骤：

S2-1、采用Dijkstra算法从查询对象q出发，沿着查询对象q的移动方向扩展道路网络，将用于存放扩展过程中遇到的道路交点的最小堆H_node和用于存放扩展过程中遇到的移动对象集合O_encount初始化为空，将查询对象q的扩展树根节点设为q点，初始化查询结果q.result，同时将q点到道路网络中所有结点的最短距离设为∞；

S2-2、根据移动对象q的移动速度获取其在道路移动方向上的道路连接v，并记录该道路上从q点到v点区段对查询对象q的影响；

S2-3、将得到的道路连接v插入到扩展树和最小堆H_node中，并记录q点到v点的最短网络距离；

S2-4、将道路qv上的移动对象加入到查询对象q的k近邻中，同时将查询对象q到达任一移动对象O_i的距离为key插入到移动对象集合O_encount中；其中O_i∈O，O为位于道路qv上的所有移动对象集合；

S2-5、判断查询对象q当前的k近邻集合是否包含了k个对象，若是则得到查询对象q的k近邻集合并进入步骤S3，否则进入步骤S2-6；

S2-6、从最小堆H_node中抽取具有最小key的结点n，获取节点n在扩展树T_q中的父结点到结点n的道路，并删除该道路；

S2-7、依次选取除结点n在扩展树T_q中的父结点以外的所有的邻接结点n_adj，直至查询对象q当前的k近邻集合是否包含了k个对象，得到查询对象q的k近邻集合。

进一步地，步骤S3具体包括以下步骤：

S3-1、更新移动对象模型T_obj：根据移动对象O_i当前处于新道路e_new上的位置信息更新移动对象O_i在移动对象模型T_obj中所对应的信息；

S3-2、更新道路模型T_edge：根据更新后的移动对象O_i的id和移动对象模型T_obj找到包含移动对象O_i的道路e_j，并从道路e_j的移动对象列表中删除移动对象e_j，将移动对象e_j加入新道路e_new的移动对象列表中，并更新每条道路的权值；

S3-3、更新查询模型T_query：根据结点n与所有邻接结点n_adj所形成的道路上的移动对象信息更新查询对象q的k近邻集合q.result、查询对象q到第k个近邻的网络距离q.kNN_dist和移动对象集合O_encount。

进一步地，步骤S3-3中更新移动对象集合O_encount的具体方法包括以下步骤：

S3-3-1、从原有移动对象集合O_encount中删除不属于以当前查询对象q位置为根节点的子树上道路的移动对象；

S3-3-2、判断保留在移动对象集合O_encount中的移动对象数量是否大于等于k，若是则进入步骤S3-3-4，否则进入步骤S3-3-3；

S3-3-3、以当前查询对象q的位置为根节点，采用与步骤S2-1至步骤S2-4相同的方法对删除掉部分移动对象的移动对象集合O_encount进行补充；

S3-3-4、将留存的移动对象至查询对象q上一位置的距离减去查询对象移动的距离，得到当前时刻查询对象q与更新后移动对象集合O_encount中每个移动对象的距离。

本发明的有益效果为：本发明在q.result中保存了查询对象q最新的k近邻，当提出查询对象q的k近邻时，则将当前查询时间t以及查询对象集合{q}作为参数调用本方法，获得t时刻查询对象q最新的k近邻q.result，并将其直接返回即可。本发明在每个查询时间点均会对道路网络和扩展树进行更新，使得本方法完全实用于道路网络中移动对象连续最近邻的监视，有利于司机选择接客顺序或接客路线。

附图说明

图1为本发明的流程示意图；

图2为实施例中包含交通规则的道路网络及4NN查询示意图；

图3为由图2得到的基于q点的扩展树；

图4为实施例中3个移动对象更新后的扩展树示意图；

图5为图4中部分标记移动后的扩展树示意图。

具体实施方式

下面对本发明的具体实施方式进行描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。

如图1所示，该基于交通规则的道路网络中移动对象连续最近邻监视方法包括以下步骤：

S1、获取移动对象和查询对象q，建立包含交通规则的道路网络模型，并得到道路网络拓扑结构；

S2、根据道路网络模型，建立查询对象q的扩展树并将其初始化，得到查询对象q的k近邻集合；

S3、根据移动对象和查询对象q的当前位置，以及道路网络拓扑结构更新道路网络模型；

S4、判断是否还需对查询对象q的最近邻进行监视，若是则返回步骤S2，否则结束监视，完成对道路网络中移动对象连续最近邻的监视。

道路网络模型包括道路模型T_edge、道路交点模型T_node、移动对象模型T_obj和查询对象模型T_query；

道路模型T_edge为6元组(rid,<n_s,n_e>,<e_i.w_p,e_i.w_n>,<s_pmax,s_nmax>,S_obj,e.IL)，其中rid是该道路的编号；<n_s,n_e>分别是该道路的起点和终点；<e_i.w_p,e_i.w_n>分别是该道路正方向及反方向的权值；<s_pmax,s_nmax>分别是该道路正方向以及道路反方向最大速度限制；S_obj是该道路上当前移动对象集合；e.IL是受道路影响的查询列表，它是三元组<q,n,d>的列表，n是该道路起点n_s或者终点n_e，d为一个数字，其表示查询对象q受到该道路影响，影响区间为该道路从节点n出发d的范围，即该道路从n出发d范围内的对象都属于查询对象q的k近邻集合；

道路交点模型T_node为2元组(conid,rules)，其中conid表示该连接id；rules表示该连接处的交通规则集合<RoadID_from,END_from,RoadID_to,END_to>；RoadID_from和RoadID_to分别表示移动对象将要离开和进入的道路id，END_from为一个布尔型数据，表示移动对象离开道路RoadID_from时是否处于该道路的终点n_e，如果处于道路终点，则END_from的值为1，否则END_from的值为0；END_to表示移动对象进入道路RoadID_to时是否处于该道路的终点n_e，如果处于道路终点，则END_to的值为1，否则处于道路起点，END_to的值为0；

移动对象模型T_obj为5元组(oid,e_j,t_u,dist,v_i)，其中oid表示移动对象的编号；e_j表示该移动对象所处的道路；t_u表示该移动对象最近的更新时间；dist表示该移动对象在t_u时刻与其所在边e_j的开始节点n_s之间的距离dist；v_i表示该移动对象在t_u时刻的移动速度，速度为正表示移动对象从起点向终点移动，反之则表示移动对象从终点向起点移动；

查询对象模型为T_query，包括移动对象的信息、查询对象q的当前kNN集合q.result，查询对象q到第k个最近邻的距离q.kNN_dist，以及查询对象q的扩展树T_q。

步骤S2具体包括以下步骤：

S2-1、采用Dijkstra算法从查询对象q出发，沿着查询对象q的移动方向扩展道路网络，将用于存放扩展过程中遇到的道路交点的最小堆H_node和用于存放扩展过程中遇到的移动对象集合O_encount初始化为空，将查询对象q的扩展树根节点设为q点，初始化查询结果q.result，同时将q点到道路网络中所有结点的最短距离设为∞；

S2-2、根据移动对象q的移动速度获取其在道路移动方向上的道路连接v，并记录该道路上从q点到v点区段对查询对象q的影响；

S2-3、将得到的道路连接v插入到扩展树和最小堆H_node中，并记录q点到v点的最短网络距离；

S2-4、将道路qv上的移动对象加入到查询对象q的k近邻中，同时将查询对象q到达任一移动对象O_i的距离为key插入到移动对象集合O_encount中；其中O_i∈O，O为位于道路qv上的所有移动对象集合；

S2-5、判断查询对象q当前的k近邻集合是否包含了k个对象，若是则得到查询对象q的k近邻集合并进入步骤S3，否则进入步骤S2-6；

S2-6、从最小堆H_node中抽取具有最小key的结点n，获取节点n在扩展树T_q中的父结点到结点n的道路，并删除该道路；

S2-7、依次选取除结点n在扩展树T_q中的父结点以外的所有的邻接结点n_adj，直至查询对象q当前的k近邻集合是否包含了k个对象，得到查询对象q的k近邻集合。

步骤S3具体包括以下步骤：

S3-1、更新移动对象模型T_obj：根据移动对象O_i当前处于新道路e_new上的位置信息更新移动对象O_i在移动对象模型T_obj中所对应的信息；

S3-2、更新道路模型T_edge：根据更新后的移动对象O_i的id和移动对象模型T_obj找到包含移动对象O_i的道路e_j，并从道路e_j的移动对象列表中删除移动对象e_j，将移动对象e_j加入新道路e_new的移动对象列表中，并更新每条道路的权值；

S3-3、更新查询模型T_query：根据结点n与所有邻接结点n_adj所形成的道路上的移动对象信息更新查询对象q的k近邻集合q.result、查询对象q到第k个近邻的网络距离q.kNN_dist和移动对象集合O_encount。

步骤S3-3中更新移动对象集合O_encount的具体方法包括以下步骤：

S3-3-1、从原有移动对象集合O_encount中删除不属于以当前查询对象q位置为根节点的子树上道路的移动对象；

S3-3-2、判断保留在移动对象集合O_encount中的移动对象数量是否大于等于k，若是则进入步骤S3-3-4，否则进入步骤S3-3-3；

S3-3-3、以当前查询对象q的位置为根节点，采用与步骤S2-1至步骤S2-4相同的方法对删除掉部分移动对象的移动对象集合O_encount进行补充；

S3-3-4、将留存的移动对象至查询对象q上一位置的距离减去查询对象移动的距离，得到当前时刻查询对象q与更新后移动对象集合O_encount中每个移动对象的距离。

在本发明的一个实施例中，图2为某一道路网络及4NN查询示意图，图3为基于图2的扩展树示意图，此时q.kNN_dist为50，即移动对象q到达移动对象p₄的网络距离。其中p1-p6均为移动对象，n₁-n₁₃均为结点，结点q为该扩展树的叶子结点，虚线及其下发的节点(n₃、n₅、n₆、n₈和n₁₂)不属于该扩展树，同时除节点q以外的移动对象p1、p2、p3、p4点和p6也不属于该扩展树，结点旁边括号的数字表示从移动对象q出发到达该结点的最短网络距离，对于n₁₁下方的叶子结点，其表示道路n₁₁n₁₂上距离n₁₁长度为10的划分位置。在移动对象q的下一个查询时刻时，假设有3个移动对象p4、p5和p6的位置发生了更新，更新类型包括移动对象依然在扩展树T_q内、依然在扩展树T_q外、由外到内和由内到外，前两种更新类型不会影响结果变化，后两者会引起移动对象q的k近邻结果发生变化，图4给出了更新(移动对象p6向n₁₂方向移动了一定距离，但仍然处于扩展树之外，移动对象p4向n₅方向移动了一定距离并移出了扩展树范围，移动对象p5从道路n₁₃n₁进入了道路n₁n₂)以后的移动对象位置。当移出扩展树的移动对象数不超过进入扩展树的移动对象数时，图4中的部分标记会向根节点移动一定距离，得到图5所示的扩展树。

根据查询对象q的新位置q_new可分为2种类型更新：

类型1(查询对象退出扩展树)此时q_new位于扩展树以外。

类型2(查询对象游弋于扩展树内)此时q_new仍然位于扩展树以内。

在图2的移动环境中，查询对象q移动到了道路n₅n₄上。从图2对应的扩展树图3可以看出，道路n₅n₄不处于扩展树范围内，因此不能利用扩展树及O_encount中信息对当前q的k近邻进行计算，此时需要执行：1、从扩展树中所有道路的e.IL中删除q；2、重新对k近邻进行重新初始化。

在图2的移动环境中，查询对象q移动到了道路n₁n₇上。此时q_new处于分支n₁n₇之间，以q_new为根结点的子树对当前q_new的k近邻计算仍然有用，因此可以利用这些信息。查询对象发生更新以后，需要对数据模型中的道路情况以及O_encount和k近邻结果进行维护，其主要步骤如下：

1、修改道路模型T_edge：查询对象更新以后，原来会对查询产生影响的道路可能就不再对该查询产生影响，因此需要从这些道路的e.IL中删除对象q。这里只需要在扩展树中找出不属于以q_new为根结点的子树的那些道路，例如图3中的n₁n₂、n₁n₁₁等，将q从这些道路的e.IL中删除。

2、维护O_encount：这里需要：(1)从O_encount中删除不属于以q_new为根结点的子树上道路的对象。(2)更新O_encount中剩下对象的距离，只需要从原来的距离中减去q的移动距离。

3、维护查询模型T_query：从扩展树可以看出，此时，以q_new为根结点的子树上所有对象仍然属于q_new的k近邻，经过对O_encount进行维护后，这些对象的更新信息都存放于O_encount中，而O_encount中原来不属于q的k近邻的对象极有可能成为q_new的k近邻，并且优于非O_encount中对象。因此此时执行下面步骤：

(1)将O_encount中前k个对象加入到新的k近邻中；

(2)如果不够k个，则对以q_new为根结点的子树进行扩展，这里需要先更新该子树的信息，即修改q_new到子树中各结点的距离，然后用该子树的叶子结点初始化H_node，并以此进行扩展得到更新以后的扩展树，在扩展过程中继续维护O_encount中对象信息。

当处于扩展树的道路权值发生变化时，分为2种情况：

(1)道路权值减少的处理。例如图2中道路n₁n₁₁权值减少。

此更新可能导致不属于扩展树的移动对象进入扩展树中，例如道路n₁₁n₁₂的移动对象p₆可能进入扩展树替换掉其他的k近邻，而对于处于扩展树T_q中其他部分(即除n₁n₁₁以及以n₁₁为根结点的子树)的对象来说，从q出发到达它们的距离和最短路径都有可能发生变化，但是会发生变化的只有T_q中以结点n为根结点的子树上的对象，n必须满足dist(q,n)>dist(q,n₁₁)，否则不会发生变化。因此，当道路n₁n₁₁权值减少时，完成以下3个步骤：

a)从T_q中删除以结点n为根结点的子树，n满足dist(q,n)>dist(q,n₁₁)，并从该子树所包含边的IL中删除q，同时从O_encount中删除受影响的对象；

b)更新以n₁₁为根结点的子树上所有对象和结点的key，并修改O_encount相应对象信息；

c)以当前扩展树的叶子结点初始化H_node，对扩展树进行扩展。

(2)道路权值增大的处理。例如图2中道路n₁n₇权值增大。

此时，从q到达n₁n₇上的移动对象o的距离应该修改为当前距离加上权值变化值。扩展树中位于以n₇为根结点的所有道路上的移动对象最短路径及距离都会产生影响(因为从q到达这些对象可以不通过n₁，而通过其他结点到达)，所以需要：

a)从扩展树删除以n₇为根结点的子树；

b)对当前扩展树进行扩展(用扩展树中叶子结点初始化H_node，同时对O_encount进行维护)。

综上所述，本发明在q.result中保存了查询对象q最新的k近邻，当提出查询对象q的k近邻时，则将当前查询时间t以及查询对象集合{q}作为参数调用本方法，获得t时刻查询对象q最新的k近邻q.result，并将其直接返回即可。本发明在每个查询时间点均会对道路网络和扩展树进行更新，使得本方法完全实用于道路网络中移动对象连续最近邻的监视。