【摘要】 本发明涉及一种移动对象近邻检测的方法。现有的方法使用欧几里德距离或者使用道路网络中的Dijkstra最短距离进行近邻检测，这些方法在大规模的检测中将消耗大量的CPU计算资源。本发明使用近邻框对移动对象进行近邻检测。采用一种两层的优先级队列来记录索引移动对象之间的近邻关系，使用时间参数化的R树对移动对象进行索引。移动对象更新其位置和速度信息后，算法根据预先定义的近邻框对移动对象的所有朋友进行近邻检测。最后将结果通告给相关移动对象。本发明方法输入多个移动对象的朋友关系、对象的当前位置，由于仅计算相邻两移动对象的坐标关系得到近邻关系，而不是欧几里德距离和Dijkstra最短距离，从而提高了计算效率。 【专利类型】发明授权 【申请人】杭州电子科技大学 【申请人类型】学校 【申请人地址】310018 浙江省杭州市下沙高教园区2号大街 【申请人地区】中国 【申请人城市】杭州市 【申请人区县】上城区 【申请号】CN201210066062.3 【申请日】2012-03-14 【申请年份】2012 【公开公告号】CN102665164B 【公开公告日】2014-11-05 【公开公告年份】2014 【授权公告号】CN102665164B 【授权公告日】2014-11-05 【授权公告年份】2014.0 【IPC分类号】H04W4/02; H04W24/00; G01S19/42; G01S19/52 【发明人】徐建 【主权项内容】1.一种移动对象近邻检测的方法，其特征在于该方法包括以下步骤： 步骤(1)、移动对象朋友关系的索引和移动范围更新； 所述移动对象是指具有GPS定位和无线通信能力的智能计算终端； 移动对象的朋友关系采用一种两层的优先级队列来保持；所述的两层的优先级队列的结构具体如下： 对于每个移动对象维护一个本地的朋友列表优先级队列，按照触发时间的大小进行排序；每个移动用户本地的朋友列表优先级队列中最早触发时间的朋友对进入一个全局优先级队列；当移动用户ui位置更新到达后，更新本地的朋友列表优先级队列，删除全局优先级队列中用户ui的相应节点，将本地队列首节点插入；系统周期性的扫描全局优先级队列，对触发时间到期的朋友对进行近邻检测和通告处理；两层的优先级队列降低了算法的复杂度，从而优化系统的处理性能； 移动对象在每一个更新周期都会采用GPS对自身位置进行定位，采集移动速度和位置信息； 取得上一次发往服务器的预测PredictBox＝(tr, te, LB，LV)；其中tr是预测区域的引用时间，te是预测区域的过期时间，LB是对象在这一时间段内的物理移动范围，是根据当前位置信息和移动速度计算的矩形框，LV是对象的当前移动速度； 首先判断当前时间是否已经超过te；然后判断当前位置与预测位置的距离是否位于安全区域，也就是是否在预测的物理移动范围LB；以上任何一种条件满足，移动用户都会向服务器发送一个新的预测；如果两种情况都不是，移动用户就等待下一个更新周期； 步骤(2)、对移动对象进行索引； 服务器中移动用户的索引使用时间参数化的R树；时间参数化的R树能够有效地对移动用户的当前位置进行索引，并且带有对象的速度信息，因此可以对移动用户进行位置预测； 时间参数化的R树中每个非叶子结点都由多个最小包含矩形框MBR及指向子节点的指针组成；非叶子结点最小包含矩形框MBR为包含每个非叶子结点孩子当前的最小边界矩形；叶子结点由最小包含矩形框MBR和移动用户的指针组成；其中叶子结点的最小包含矩形框MBR为包含对应移动用户的最小边界矩形，通过移动用户的指针可以得到对象的详细信息；移动用户的详细信息包含当前位置信息，以及速度和最近的移动范围更新信息PB； 步骤(3)、对移动对象进行基于近邻框的近邻检测； 服务器对于每个超限安全区域更新进行近邻检测；超限安全区域更新指的是移动对象移动范围超越预测区域，其真实位置在预测区域外，移动对象向服务器发送位置更新信息；移动对象之间具有相互的朋友关系，但是不同对象定制不同近邻标准，也即不同对象具有不同的近邻标准；设uj是ui的朋友，那么ui也是uj的朋友，但是他们具有不同的近邻标准εi, j和εj, i；服务器接收到移动用户的PB消息后，更新其索引节点；它同时维护一个移动用户邻近朋友的列表；服务器先对列表中的所有朋友进行近邻检测，检测过程使用用户ui的近邻标准εi, j，更新用户ui的近邻朋友列表；接着，服务器对列表中所有朋友针对ui进行近邻检测，使用其朋友的近邻标准； 对于移动对象ui，ui的近邻标准为εi, j；在某一时刻检测其朋友列表中的用户uj是否在其近邻范围内，基于近邻框的近邻检测就是判断他们的坐标关系是否满足|ui.x-uj.x|≤εi, j且|ui.y-uj.y|≤εi, j； 由于在服务器中保留是用户的移动区域预测，对于近邻关系判断需要考虑用户在其安全域区内具体位置的不确定性；给定一个长宽分别为A、B的预测区域，两个用户ui, uj之间的XY轴方向距离关系有 : MinDX(ui, uj)＝max{|ui.x-uj.x|-ui.A-uj.A, 0} MaxDX(ui, uj)＝|ui.x-uj.x|+ui.A+uj.A MinDY(ui, uj)＝max{|ui.y-uj.y|-ui.B-uj.B, 0} MaxDY(ui, uj)＝|ui.y-uj.y|+ui.B+uj.B ui, uj之间确定具有近邻关系的条件是 MaxDX(ui, uj)≤εi, j且MaxDY(ui, uj)≤εi, j ui, uj之间确定不具近邻关系的条件是 MinDX(ui, uj)>εi, j且MinDY(ui, uj)>εi, j 由于ui，uj具有相互的朋友关系，在对ui进行近邻检测以后，还需要对uj进行近邻检测；为了简化这一过程，首先对两个用户的近邻框大小进行判断，先行检测较小的近邻框；如果对于较小的近邻框，移动用户ui，uj都具有近邻关系，那么对于另外一个用户来说显然也具有近邻关系；反之，就需要进一步判断对于较大近邻框的移动用户是否具有近邻关系； 检测完成后，用户ui的朋友就分为了三类：在未来的某个时间段t内，具有近邻关系，不具有近邻关系，在即将到来的某个时刻t’, t’

未经允许不得转载：http://www.zhongzhencnc.com/1791493787.html