分布式网络中CKNN查询的BORA优化汇聚
2016-07-04叶李
叶 李
(中国西南电子技术研究所，成都 610036)
分布式网络中CKNN查询的BORA优化汇聚
叶李
(中国西南电子技术研究所，成都 610036)
摘要：针对时空数据库中，移动对象轨迹的连续K近邻查询(continuousKnearest neighbor query，CKNN)的查询效率较低的问题，以及在分布式的移动对象数据库(moving objects databases，MOD)环境下，提升对应查询结果的数据汇聚效率问题进行了研究。在CKNN查询中，设计优化了查询海滩线的更新算法，通过在轨迹数据结构中增加更新标志位，减少了轨迹线段参与的判定运算；同时在假设的类网格覆盖的分布式空间环境下，利用基于Bresenham覆盖的路由汇聚(Bresenham-based overlay for routing and aggregation，BORA)方法，进行查询结果的汇聚；并针对不同近邻参数、轨迹数目、移动对象速度、汇聚方式等对查询时间的影响进行了仿真实验；仿真结果表明，不同参数数值的增加延长了处理时间，基于BORA的汇聚方式比一般的汇聚方式节省了更多的处理时间，提高了系统查询及处理的效率。
关键词：移动对象数据库；连续K近邻查询；查询汇聚；BORA算法
0引言
在基于定位系统的移动对象相关应用中，作为基础技术的移动对象数据库 (moving objects databases, MOD)得到了广泛应用[1-3]。目前，移动对象数据库的研究和应用主要集中在高效的数据存储、管理、时空数据的获取以及各种数据查询的处理等方面。大部分的研究工作都基于存在一个中心服务器，进行集中处理的假设，这实际上限制了移动对象数据库的应用范围。本文在前期工作的基础上[4]，针对分布式处理环境条件下，基于典型类网格结构下的移动对象数据服务进行研究。
在类网格结构的传感器网络条件下，每个网格存在一个基站(base station ,BS)。基站所对应的移动对象数据由基站所配备的移动对象数据库服务保存。基站之间的通信由相邻节点彼此连接，各个基站负责的通信范围包括2个方面，一是在基站范围内的所有移动对象用户，其次是基站对应的相邻节点。基站根据需要与相邻基站建立通信链接并传输数据，并且基站将处理对应网格范围内所提交的时空数据查询。在类网格条件下的查询处理中，移动对象数据库中的对象移动轨迹在所提交的查询时间范围条件下通常可能跨越了多个网格。因此，彼此相邻的基站所返回的查询结果通常包含了冗余数据。为了提高通信性能，查询结果在向目的基站传输的途中将遵循一定的路由和汇聚策略。一个理想的路由汇聚策略必须包含以下特性，首先能实现查询结果的部分汇聚，其次是保留一定程度上的并行处理能力以避免过于频繁的数据汇聚[4]。
在基于Bresenham覆盖的路由汇聚方法(Bresenham-based overlay for routing and aggregation，BORA)的前期工作中[4]，包含多个网格的范围查询结果通过BORA算法在全局范围内数据汇聚与传输的性能上取得了显著效果。实验中，一个网格内的范围查询结果是全部查询结果的一部分，多个部分查询结果沿着查询节点到汇聚节点的Bresenham路径进行数据的汇聚操作，通过数据汇聚消除了冗余，实际上在数据传输过程中减少了数据传输量，节省了传输时间。
就连续K近邻查询来说，BORA算法的应用在操作中与范围查询并不一样。本文就连续K近邻查询结果在类网格模式下的BORA汇聚方式进行了研究，确认具体的汇聚方式，并通过实验结果验证了BORA算法对连续K近邻查询结果在汇聚与传输方面起到提高性能的作用，并确定了相关的影响因素。
1相关工作
分布式移动对象数据库就架构设计而言，并行计算与分布式数据库系统是其发展的两个基础技术，这也是数据库系统中两个重要的研究领域。随着技术的发展，移动对象数据库系统与应用得到了越来越多的关注。近年来，许多的研究工作都集中在移动对象数据库中关于数据查询的有效性处理方面。这些查询都基于不同的运动模型，一种是有关于定位和时间的序列更新数据[5-6]，另一种是在前一种的基础上增加了运动的速度信息[7]。关于移动对象数据库的主要研究工作集中在数据的有效存储、时空数据的获取以及不同的数据查询处理方面。大部分研究工作都假设存在一个包含移动对象数据库的集中处理环境，即存在一个中心服务器处理相关的数据查询和其他的对应操作。
与之相对应的分布式环境中，文献[8-9]研究了授权的移动用户方对时空查询的部分结果进行保存和相关维护的技术，另外增加查询-认知技术的航位推算更新策略[5]也将显著节省通信成本。但就这种方式而言，这种近似移动对象数据库的处理能力也是假设为中心集成式的。项目MobiEyes[8-9]研究了服务器与一系列移动客户端之间，在最小化全局通信下的负载平衡问题。在这个项目中，其运动模型包含了定位、时间和速度，并且航位推算策略也扩展为包含了保存和维护连续查询结果的技术。在传感器网络环境下，关于路由树生成和部分查询结果汇聚技术已经得到了一定的应用[10-11]。汇聚的主要目的在于减少参与节点的能耗，延长整个网络的生存周期并保证数据质量。文献[12]就传感器网络环境中的并行和并发数据传输问题进行了研究，以节能为主要目的，解决了最小化包碰撞和丢弃的问题。
在与相关的网络通信问题方面，项目ECO[13]对给定网络下建立通信模式，以实现有效的数据并发应用这一问题进行了研究。本文通过运用与文献[13]类似的简单网络架构模型，来验证在分布式环境下，基于BORA算法的连续K近邻查询的汇聚方式及其对性能产生影响的相关因素。
另外，近邻查询一直是近十多年来时空数据库研究中的核心问题。随着移动定位服务(mobile location services, MLS)的发展，针对历史轨迹数据的K近邻查询已成为数据分析的重要手段，在此基础上对服务进行改进或提出新的服务模式。文献[14]就历史轨迹数据中的近邻查询进行了广泛细致的分析，确定了基本的查询分类和算法；文献[15-16]就历史轨迹数据中的轨迹的连续近邻查询进行了更深入的分析，设计了BFTKNN算法。但他们的主要工作都集中在减少类R树(R-tree-like)结构中的节点访问次数及对最优遍历和最深遍历算法的研究上，主要目的是减少主存和CPU耗用。但就迭代更新查询结果的优化问题上，并没有得到深入的研究。本文针对类R树的数据结构中保存的移动对象历史轨迹数据连续K近邻查询进行了研究，主要的工作集中在迭代更新查询结果的优化问题上。
2CKNN查询及优化
一般情况下，连续最近邻查询的结果保存在一个链表中，表示为NodeList。链表NodeList中存储的数据结构表示为Node，每个Node包含了轨迹ID、运动参数、开始时间、结束时间、最大距离、最小距离及更新标志。为了加快查询速度，每个NodeList对象中还包含了整个链表的最大距离和最小距离值。连续K近邻查询的结果是多个NodeList构成的列表，记为NodeTable。
链表NodeList通常包含多个Node，每个Node对应不同的轨迹数据，与查询轨迹之间的距离根据时间变化成抛物线模式。在实际的几何形状上看来，整个NodeList的数据表现为一条海滩线，具体的一个例子如图1中的虚线OldLine所示。在多近邻查询的情况下，当迭代更新一条对应的NodeList时，对应海滩线上的每一段抛物线都需要通过距离比较判定轨迹对应的抛物线，以确定更近邻节点段，最后生成新的海滩线，如图1中的NewLine所示。如果对NodeTable中每层NodeList中的每段Node都进行类似的判定比较，则更新算法的速度必定非常缓慢。
由图1可知，判定轨迹的抛物线线段A完全取代了线段1成为更近邻，在这种情况下，原存在的各层近邻节点实际上逐层升高成为上一层近邻，而线段A成为最近邻；类似的情况也存在线段C上，形成的最近邻海滩线如图1中红色线段所示，包括了线段A、线段2的右半边和线段3的左半边及线段C；关于线段B，由于并不能确定该线段成为第2层近邻，所以必须跟下一层NodeList进行判定。按此方式依次进行逐层检测判定，直至完成NodeTable的更新。随着层次的增加，所需进行判定的抛物线线段也逐层减少。
为了优化K近邻查询效率，提高迭代更新近邻列表的速度，文中在判定轨迹对应的NewNode结构中增加更新标志位。通过标志位的布尔开关，决定该部分轨迹线段是否参与主要耗时的判定运算。初始判定时，设置标志位初值为真，根据NewNode替代NodeList中的Node节点成为更近邻的不同情况，将NewNode节点根据需要拆分，成为更近邻的部分线段时其标志位设置为假，未成为更近邻部分线段时对应的标志位设置为真。
图1 近邻海滩线的更新Fig.1 Update of nearest neighbor beach line
优化更新K近邻NodeTable结构的算法UpdateKNNTable如算法1所示。在基于类R树的数据结构上的最优或最深遍历的基础上，确定需要判定的轨迹节点，作为算法的输入参数。算法首先将该轨迹数据初始化成一近邻链表NodeList，其中，仅有包含该轨迹信息的一个节点。然后根据NodeTable的大小，从最近邻开始，调用算法UpdateBeachLine，更新逐层对应的NodeList。UpdateBeachLine接收传入参数，是该层对应的K-NodeList和更新链表NodeList，返回布尔变量bupdate和新生链表NewNodeList。在UpdateBeachLine的执行中，实际上将K-NodeList和NodeList中对应的节点在根据距离远近的情况下进行了拆分和互换。布尔变量bupdate实际上是更新后的NodeList中各节点更新标志的或值，如果该值为假，则表示NodeList作为一个新对象取代了原来的K近邻链表，因此将其值插入到(K+1)-NodeList之前。如果该值为真，说明NodeList中至少存在一个节点包含需要判定的轨迹节点，因此将经过UpdateBeachLine更新后的NodeList作为下一次调用的传入参数，迭代更新海滩线(K+1)-NodeList。
算法1: UpdateKNNTable
Input: 判定轨迹Trajectory
Output: 更新后的NodeTable
1将Trajectory数据初始化成一NodeList对象；
2如果NodeTable的大小为0，则将NodeList加入到NodeTable对象中；返回。
3否则循环，从NodeTable的最近邻链表开始，扫描各层K对应的K-NodeList；
4如果NodeList的最小距离大于K-NodeList的最大距离，继续循环；
5否则UpdateBeachLine(K-NodeList, NodeList)，接收返回值bupdate以及更新后链表NodeList；
6如果bupdate为假，将NodeList插入在(K+1)-NodeList之前；跳出循环；
7否则更新后的NodeList作为传入参数，继续下一层循环；
8如果NodeTable中链表数目小于K，将NodeList插入到NodeTable最后一行；大于K则将最后一行删除。
更新海滩线的具体操作如算法2所示。首先按时间顺序查找NodeList中更新标志为新的Node节点，得到Node节点的时间信息后，在K-NodeList中确定对应时间段的节点K-Node，进行比较判别。具体的情况可大致分为6类，如图2所示。图2a对应算法2中2-3行，这是最简单的情况，其余的判定都需要根据两轨迹间距离方程的Delta数值进行判定。当Delta小于0，即两抛物线没有交点的情况，对应图2b和算法2中的5-7行。Delta等于0的情况对应图2c和算法2中8-10行。比较复杂的情况是当Delta大于0时，这时又需要分为多种情形进行判定。第1种情形是两交点对应的时间点t1和t2不在节点对应时间段[Ts,Te]，如图2d所示，主要存在A,B,C3种模式，但可直接通过判别节点在对应时间段的最大值方式确定交换与否，对应算法2中12-14行；第2种情形即t1和t2都在对应时间段[Ts,Te]，则需要将Node和K-Node都根据t1和t2拆分成3段，进行拼接，如图2e所示，对应算法2中15-17行；最后的一种情形则是仅有一个交点对应的时间点在[Ts,Te]，如图2f所示，对应算法2中18-20行，Node和K-Node根据交点时刻拆分成2段后进行拼接。
图2 近邻轨迹的比较Fig.2 Comparison of nearest neighbor trajectory
通过Node和K-Node的拆分拼接或交换操作，提高了K近邻更新操作的效率。而Node结构中增加更新标志位的方式，使得每层NodeList更新操作时需要检查的节点降低到最少。
算法2: UpdateBeachLine
Input:K-NodeList, NodeList
Output: bupdate及更新后链表NodeList
1循环，查找NodeList中更新标志为真的Node，确定在K-NodeList对应时间段的K-Node，进行判别；
2如果Node的最大值小于K-Node的最小值，在K-NodeList和NodeList中的对应时间段内，互换节点，Node的更新标志设置为假；
3另外如果K-Node的最大值小于Node的最小值，循环继续；
4其他情况下根据两轨迹段间的距离方程，确定其Delta数值；
5Delta小于0时：
6如果Node的最大值小于K-Node的最大值，互换节点，Node的更新标志设置为假；
7否则，循环继续；
8Delta等于0时：
9如果Node的最大值小于K-Node的最大值，互换节点，Node的更新标志设置为假；
10否则，循环继续；
11Delta大于0时：
12如果两个交点对应的时间点t1和t2都不在节点对应的时间段内：
13如果Node的最大值小于K-Node的最大值，互换节点，Node的更新标志设置为假；
14否则，循环继续；
15如果两个交点对应的时间点t1和t2都在节点对应的时间段内，将Node和K-Node根据t1和t2分别拆分成三段；
16如果Node的最小值大于K-Node的最小值，将K-Node原本对应的节点用t1前的k-Node，t1到t2时刻的Node(对应更新标志设置为假)，t2后的K-Node形成的链表代替；而Node对应的节点用t1前的Node，t1到t2时刻的K-Node，t2后的Node形成的链表代替；
17否则将k-Node原本对应的节点用t1前的NewNode(对应更新标志设置为假)，t1到t2时刻的K-Node，t2后的NewNode(对应更新标志设置为假)形成的链表代替；而NewNode对应的节点用t1前的K-Node，t1到t2时刻的NewNode，t2后的K-Node形成的链表代替；
18如果两个交点对应的时间点仅存在一个时间点t在节点对应的时间段内，则将Node和K-Node根据t分别拆分成两段；
19如果Node在t时刻的值大于K-Node，将K-Node原本对应的节点用t时刻前的K-Node，t后的Node(对应更新标志设置为假)形成的链表代替；而Node对应的节点用t时刻前的Node，t后的K-Node形成的链表代替；
20否则将K-Node原本对应的节点用t时刻前的Node(对应更新标志设置为假)，t后的K-Node形成的链表代替；而Node对应的节点用t时刻前的K-Node，t后Node的形成的链表代替；
21更新布尔变量bupdate，其值取决于NodeList中所有节点更新标志或的结果。
3网络设置及BORA汇聚
一般来说，移动对象的轨迹定义为一个序列的点的集合，表示为Tr={(x1,y1,t1), (x2,y2,t2),…,(xn,yn,tn)}，当(i
在网络通信方面，本文所设定的类网格网络中，各网格中对应的服务器也假设通过相邻节点进行通信的彼此连接。为了计算和评估实际的通信容量，需要考虑多方面的因素，包括通信链接的容量、往返时延(round-trip time,RTT)、发送/接收窗口大小、数据包的错误率或丢失率等[13]。在本文的研究工作中，为了评估2台服务器之间通信性能，设定传输n个数据包所消耗的时间的计算方式为：t1+t2×n，其中，t1表示在服务器之间建立链接的往返时延；t2表示单位数据包接收所消耗的时间，可近似计算为：接收窗口大小/RTT。
针对路由和结果汇聚的BORA算法是基于Bresenham直线算法的思想来处理在类网格覆盖的分布式空间环境下，查询区域向汇聚中心如何汇聚与传输查询结果的问题[2]。Bresenham直线算法是用来描绘由2点所决定的直线的算法，它会算出一条线段在n维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制计算机画面中的直线，是计算机图形学中最先发展出来的算法[12]。
BORA算法通过各查询区域与汇聚中心的Bresenham路径构建BORA树。通常在给定的一个查询范围，其区域为一个任意的多边形，表示为R；在网络中，与R相交的网格区域节点都将参与此给定范围查询的运算，所有参与运算的节点表示为CR={C1,C2,…}；而节点查询结果所汇聚向的对象节点表示为Cd。通过Cd和所有CR成员之间的Bresenham路径的网格节点都将是参与查询或结果汇聚的节点。各个节点通过执行BORA树的构造算法建立了一个虚拟的BORA汇聚树，BORA树以汇聚中心为根，Bresenham路径上节点为各中间节点，CR中的节点为叶节点。由于对象节点相对查询区域而言存在有多种可能位置，BORA树的根节点可能拥有1—8个子节点。这些特殊情况包括对象节点与查询区域的凸包的2个顶点共线或者就在查询区域内等。在BORA树构造完成后，各个节点服务器上在获取本地查询结果的基础上进行部分汇聚操作。在基于BORA树的汇聚方案中，向父节点传输的查询结果是传输节点和其所有子树的查询结果的汇聚结果。查询命令是通过递归式的从上至下的发布，而查询结果是从下至上的汇聚。每个网格服务器按算法执行BORA树的构造和数据的传输，直到给定查询的处理完成。
对于类网格模式下对应轨迹的某节点CKNN查询的NodeTable，其每层NodeList的首尾两节点与相邻节点对应的NodeList的尾首节点可能存在相同的对应近邻轨迹ID，对应近邻时间段相连的情况。这种情况下将对应两节点合并成一个节点，时间段属性对应拓展，这也是在汇聚操作中处理，以进一步减小数据传输量。
4实验分析
文中就基于BORA汇聚的CKNN查询进行了各项实验评估其各项参数对性能的影响。对每一项K近邻查询结果，通过基于BORA方式和Naïve方进行比较评估其性能。试验中关于移动对象的历史信息存储在类似R-tree的数据结构中，通过公开的程序库Spatial Index Library实现具体功能。Spatial Index Library提供了空间数据索引的一个通用框架，定义了通用的接口，简化了主存和存储设备的管理，实现了R*-tree, MVR-tree以及TPR-tree等数据结构。实验是在Pentium Intel Core2 Duo 2.26 GHZ，3 GB内存，Cygwin平台下运行的，主要的实验参数和内容如下。
1)设定对象移动范围为100×100 km的正方形区域，划分为50×50的等距网格。
2)移动对象的轨迹是改进后的RWP(random way-point model)生成的模拟数据，使得各段采集数据的速度在设定范围内随机变化。总共生成6 000条轨迹，轨迹的起始点和移动方向都是在移动范围内随机生成，速度在15-120 km/h；路径中任意一线段对应的最大移动速度随机设定为速度的70%-100%。每条轨迹已预先按照路径存储在通过的网格MOD中。轨迹的总长在15-120 km，轨迹包括的线段数目呈正态分布，1 km的长度通常包括4-8个线段。
3)就K近邻查询而言，随机选择查询时间的起始和终止值，查询时间的长度随机不定。
4)通信方式是各个网格MOD节点向目的节点逐节传送的，每个网格对应的MOD服务器负责对应区域内的数据接收和传输，速率假设为128 kbit/s。
首先，实验就轨迹数目在不同汇聚方式下，对各汇聚方式处理时间的影响进行评估。为了准确评估轨，实验选择了不同的轨迹数目，每个网格选择了100到1 000条不等。而其他影响因素，都假设为一个固定值：如对象的移动速度都假设在80 km/h左右，并且对象运动轨迹段中心到汇聚中心的距离被设定为整个移动区域的对角线长度的60%。图3显示了不同轨迹数目对处理时间的影响。可以看出，基于BORA的方法比Naïve的方法节省了更多的时间；而随着轨迹数目的增加，节省时间的总量也在增加。分析其原因，是因为随着轨迹数目的增加，所查询轨迹的最近邻结果包含更多记录的可能性也随之增加，因此各种汇聚方式都增加了所需要传输的数据。
图3 轨迹数目对不同汇聚方式处理时间的影响Fig.3 Influence of trajectories number
接下来，就移动对象的速度对处理时间的影响进行评估。实验中，轨迹的运行速度假设为15—120 km/h，在每个网格中的轨迹数目设定为800。图4显示了对象移动速度对处理时间的影响。可以看出，随着对象移动速度的增加，处理时间近似线性增加。这也是因为随着轨迹运动速度的增加，所查询轨迹的最近邻结果包含更多记录的可能性也随之增加，从而增加了总体的处理时间。
图4 移动对象速度对处理时间的影响Fig.4 Influence of moving object velocity
关于K近邻查询中参数K对处理时间的影响由图5可以看出，其中每个网格的轨迹数目设定为400。图5中显示了最近邻，2-NN和4-NN查询在对象不同移动速度下对处理时间的影响。结果表明，随着参数K和移动速度的增加，所需传输的数据增加，使得各汇聚方式所需的处理时间增加。但不管何种情况下，基于BORA的汇聚方式总是优于Naïve方式。
图5 近邻参数K对处理时间的影响(轨迹数目400)Fig.5 Influence of K (400 trajectories)
最后，就汇聚距离对处理时间的影响进行分析。汇聚距离指的是轨迹段的中心与汇聚节点位置的距离。试验中在给定汇聚节点的条件下，假设每个网格的轨迹数目为400条，对象移动速度为60 km/h。各个轨迹段中心到汇聚节点的距离根据与设定的移动范围的对角长度的相对比例转换为百分比，然后根据其对应的百分比平均到10%到100%。实验结果比较了Naïve和BORA的汇聚方式，根据图6可以看出，其处理时间上都基于汇聚距离的长度呈线性增加。
图6 汇聚距离对处理时间的影响(轨迹数目400)Fig.6 Influence of aggregate distance (400 trajectories)
5结论
在过去的10年中，关于移动对象连续K近邻查询技术得到了广泛关注。但在分布式的移动对象数据库环境下，相关查询的优化、结果的汇聚问题还没有得到解决。在实验室设定的类网格覆盖的分布式空间网络环境下，每个网格由一个基站负责处理相关的通信问题，还配备服务器拥有移动对象数据库，保存对应网格区域内的移动对象相关的轨迹信息，处理对应的查询操作；并通过与相邻节点的链接，协同处理跨网格的相关查询操作与结果汇聚。BORA汇聚基于Bresenham算法的思想，沿着查询节点到汇聚节点的Bresenham路径进行查询结果的汇聚操作，在保留一定程度的并行能力和查询结果的汇聚上实现了较好的平衡。
本文在前期工作的基础上，在连续K近邻查询中，通过在轨迹数据结构中增加更新标志位的方法，避免了在更新连续K近邻查询结果的操作中，频繁重复检查已确定节点的问题。将BORA算法应用到各节点查询结果的汇聚操作中，这比一般情形的汇聚方式更加优越。通过实验结果可以看出，随着参数K、轨迹数目以及对象运动速度的增加，BORA算法节省了更多的处理时间，提高了系统处理效率。
参考文献：
[1]陈瑛, 陈钊滢, 叶小平. M-相点数据索引SPindex[J]. 计算机科学, 2015, 42(1): 206-209.
CHENG Ying, CHENG Zhaoying, YE Xiaoping. SPindex:Spatial Index Based on M-phase Points[J]. Computer Science, 2015, 42(1):206-209.
[2]金培权, 汪娜, 张晓翔,等. 面向室内空间的移动对象数据管理[J]. 计算机学报, 2015(9):1777-1795.
JIN Peiquan, WANG Na, ZHANG Xiaoxiang, et al. Moving Object Data Management for Indoor Spaces [J] . Chinese Journal of Computers, 2015(9):1777-1795.
[3]G¨UTING R H, SCHNEIDER M. Moving Objects Databases[M]. Burlington USA: Morgan Kaufmann, 2005.
[4]TRAJCEVSKI G, DING H, SCHEUERMANN P, et al. BORA: Routing and Aggregation for Distributed Processing of Spatio-Temporal Range Queries [C]//Proceedings of the 2007 International Conference on Mobile Data Management. [s.l.]:IEEE, 2007:36-43.
[5]MOKBEL M, XIONG X, AREF W. Sina: Scalable incremental processing of continuous queries in spatio-temporal databases [C]//In ACM SIGMOD Internation Conference on Management of Data. New York, NY, USA :ACM, 2004:623-634.
[6]XING X, MOKBEL M, AREF W, et al. Scalable spatio-temporal continuous query processing for location-aware services [C]//In International Conference on Scientific and Statistical Database Management (SSDBM).[s.l.]:IEEE, 2004:317-326.
[7]WOLFSON O,SISTLA A P,CHAMBERLAIN S,et al.Updating and querying databases that track mobile units[J].Distributed and Parallel Databases,1999,7(3):257-387.
[8]GEDIK B, LIU L. Mobieyes: Distributed processing of continuous queries on moving objects in a mobile system [C]//In International Conference on Extending the Database Technology (EDBT). Berlin Heidelberg: Springer, 2004:67-87.
[9]GEDIK B, LIU L. Mobieyes: A distributed location monitoring service using moving location queries [J]. IEEE Transactions on Mobile Computing, 2006,5(10):67-87.
[10] BOULIS A, GANERIWAL S, SRIVASTAVA M. Aggregation in sensor networks: Energy-accuracy trade offs
[J]. Ad Hoc Network, 2003s, 1 (2-3):317-331.
[11] YOUSSEF M, YOUNIS M, ARISHA K. A constrained shortest-path energy-aware routing algorithm for wireless sensor networks [C]//In IEEE-WCNC. [s.l.]:IEEE, 2002:794-799.
[12] ZADOROZHNY V, CHRYSANTHIS P. Network-aware wireless sensor data management [C]// In MDM. Japan: Conference Publication, 2006.
[13] LOWEKAMP B, BEGUELIN A. Eco: Efficient collective operations for communication in heterogeneous networks [C]∥In IPPS. Honolulu, HI:IEEE, 1996:399-405.
[14] FRENTZOS E,GRATSIAS K,PELEKIS N,et al.,Algorithms for nearest neighbor search on moving object trajectories[J].Geoinformatica,2007,11(2):159-193.
[15] GAO Y J, LI C, CHEN G C, et al. Efficient k-nearest-neighbor search algorithms for historical moving object trajectories [J]. Journal of Computer Science and Technology, 2007, 22( 2): 232-244.
[16] GAO Y J, LI C, CHEN G C, et al. Efficient algorithms for historical continuous k nn query processing over moving object trajectories [M].[s.l.]: Advances in Data and Web Management, 2007:188-199.
BORA optimized aggregation of CKNN query in distributed settings
YE Li
(Southwest China Institute of Electronic Technology, Chengdu 610036, P.R.China)
Abstract:In spatial and spatio-temporal databases and distributed settings of MOD(moving objects databases), the problem of lack of efficiency of continuousKnearest neighbor query about moving object trajectories, and that of query optimization and results aggregation were researched. TheKNearest Neighbor query efficiency is promoted by adding the update flag in trajectory data structure. And in assumed grid-like coverage of spatial universe of discourse, the aggregation problem of continuousKnearest neighbor is resolved by revised BORA (Bresenham-based overlay for routing and aggregation) algorithm. The influence of different parameters, such asK, number of trajectories, moving velocity and aggregation method were demonstrated in experiments. It can be seen that the increase of different parameter prolongs the processing time, but the BORA based aggregation saved more processing time and improved the efficiency of system.
Keywords：moving objects database; continuousKnearest neighbor query; query aggregation; BORA algorithm
DOI：10.3979/j.issn.1673-825X.2016.03.026
收稿日期：2016-03-18
修订日期：2016-05-05通讯作者：叶李forefell@sohu.com
基金项目：国家自然科学基金项目(61379159)；重庆市科委自然科学基金项目(cstc2014jcyjA1350)
Foundation Items：The National Natural Science Foundation of China(61379159)；The Natural Science Foundation Project of CQ CSTC (cstc2014jcyjA1350)
中图分类号：TP3
文献标志码：A
文章编号：1673-825X(2016)03-0435-08
作者简介：
叶李(1977-)，男，四川达州人，工程师，博士，主要研究方向为侦察对抗总体设计。E-mail:forefell@sohu.com。
(编辑：魏琴芳)
