动态交通网络中最优路径查找算法*

在真实交通网络中,可能出现某高速公路在某一时刻内通过的车辆过多,从而改变了该时刻道路的即时速度,这就需要对道路的交通流量进行监控。针对这一问题,通过建立交通网络的速度模式库,根据道路可达速度的变化更新速度模式。基于A*算法与速度模式库,提出针对动态交通网络的最短路径查询算法。采用真实数据集对算法进行测试,结果表明,应用该方法能够有效地解决在速度模式发生变化的情况下最优路径的查找,使交通网络中的最优路径查询更为准确有效。     

A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases

A very important class of queries in GIS applications is the class of K-nearest neighbor queries. Most of the current studies on the K-nearest neighbor queries utilize spatial index structures and hence are based on the Euclidean distances between the points. In real-world road networks, however, the shortest distance between two points depends on the actual path connecting the points and cannot be computed accurately using one of the Minkowski metrics. Thus, the Euclidean distance may not properly approximate the real distance. In this paper, we apply an embedding technique to transform a road network to a high dimensional space in order to utilize computationally simple Minkowski metrics for distance measurement. Subsequently, we extend our approach to dynamically transform new points into the embedding space. Finally, we propose an efficient technique that can find the actual shortest path between two points in the original road network using only the embedding space. Our empirical experiments indicate that the Chessboard distance metric (L) in the embedding space preserves the ordering of the distances between a point and its neighbors more precisely as compared to the Euclidean distance in the original road network.     

北京城区环路交通系统模型研究

建立一个简化的北京城区多环路系统模型,运用最短路径算法,模拟在无环路和有环路的情况下,机动车从开始点到目的点的最短路径和最短时间,通过随机生成大量开始点和目的点,分析经过环路的机动车的时间减少量和路径增加量,从而全面研究环路对交通和环境的影响。实验结果表明,环路增加了人们的出行成本和环境压力,对于北京市的环境具有很大副作用。     

基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。     

Dynamic monitoring of optimal locations in road network databases

Optimal location (OL) queries are a type of spatial queries that are particularly useful for the strategic planning of resources. Given a set of existing facilities and a set of clients, an OL query asks for a location to build a new facility that optimizes a certain cost metric (defined based on the distances between the clients and the facilities). Several techniques have been proposed to address OL queries, assuming that all clients and facilities reside in an \(L_p\) space. In practice, however, movements between spatial locations are usually confined by the underlying road network, and hence, the actual distance between two locations can differ significantly from their \(L_p\) distance. Motivated by the deficiency of the existing techniques, this paper presents a comprehensive study on OL queries in road networks. We propose a unified framework that addresses three variants of OL queries that find important applications in practice, and we instantiate the framework with several novel query processing algorithms. We further extend our framework to efficiently monitor the OLs when locations for facilities and/or clients have been updated. Our dynamic update methods lead to efficient answering of continuous optimal location queries. We demonstrate the efficiency of our solutions through extensive experiments with large real data.     

Optimization and evaluation of shortest path queries

We investigate the problem of how to evaluate efficiently a collection of shortest path queries on massive graphs that are too big to fit in the main memory. To evaluate a shortest path query efficiently, we introduce two pruning algorithms. These algorithms differ on the extent of materialization of shortest path cost and on how the search space is pruned. By grouping shortest path queries properly, batch processing improves the performance of shortest path query evaluation. Extensive study is also done on fragment sizes, cache sizes and query types that we show that affect the performance of a disk-based shortest path algorithm. The performance and scalability of proposed techniques are evaluated with large road systems in the Eastern United States. To demonstrate that the proposed disk-based algorithms are viable, we show that their search times are significant better than that of main-memory Dijkstra's algorithm.     

k-Multi-preference query over road networks

Nowadays, the road network has gained more and more attention in the research area of databases. Existing works mainly focus on standalone queries, such as k-nearest neighbor queries over a single type of objects (e.g., facility like restaurant or hotel). In this paper, we propose a k-multi-preference (kMP) query over road networks, involving complex query predicates and multiple facilities. In particular, given a query graph, a kMP query retrieves of the top-k groups of vertices (of k facility types) satisfying the label constraints and their aggregate distances are the smallest. A naïve solution to this problem is to enumerate all combinations of vertices with k possible facility types and then select the one with the minimum sum distance. This method, however, incurs rather high computation cost due to exponential possible combinations. In addition, the existing solutions to other standalone queries are for a single type of facilities and cannot be directly used to answer kMP queries. Therefore, in this paper, we propose an efficient approach to process a kMP query, which utilizes an index with bounded space and reduces the computation cost of the shortest path queries. We also design effective pruning techniques to filter out false alarms. Through our extensive experiments, we demonstrate the efficiency and effectiveness of our proposed solutions.     

PS+Pre/Post: A novel structure and access mechanism for wireless XML stream supporting twig pattern queries

XML data broadcast is an efficient way to disseminate XML data to a large number of mobile clients in mobile wireless networks. Recently, several indexing methods have been proposed to improve the performance of XML query processing in terms of access time and tuning time over XML streams. However, existing indexing methods cannot process twig pattern XML queries. In this paper, we propose a novel structure for streaming XML data called PS+Pre/Post by integrating the path summary technique and the pre/post labeling scheme. Our proposed XML stream structure exploits the benefits of the path summary technique and the pre/post labeling scheme to efficiently process different types of XML queries over the broadcast stream. Experimental results show that our proposed XML stream structure improves the performance of access time and tuning time in processing different types of XML queries.     

Shortest hop multipath algorithm for wireless sensor networks

Shortest hop or distance path is one of the most common methods used for relaying messages in a wide variety of networks. It provides an efficient message relaying to destination in terms of energy and time. There are many algorithms for constructing shortest hop or distance path. However, according to our knowledge, no algorithm for constructing a shortest hop multipath for wireless sensor networks (WSNs) has yet been proposed in the literature. In this paper, we propose a novel distributed shortest hop multipath algorithm for WSNs in order to generate energy efficient paths for data dissemination or routing. The proposed algorithm generates shortest hop braided multipath to be used for fault-tolerance or load-balancing. It guarantees the BFS tree and generates near optimal paths in O(V.D+V) message complexity and O(D²) time complexity regarding the communication costs towards the sink after termination of algorithm.     

基于等效网络的车辆导航系统路线规划算法

在实际交通行为中,不可避免地存在着交叉口时间延迟,而且交通管制信息如交叉口转向限制也普遍存在,这些交通特征使得常规的最短路算法难以满足车辆导航系统路线规划的要求。提出基于“节点-弧段-特征”的数据结构存储方案,能够完整描述路网的平面拓扑和交通特征属性;针对具有交叉口转向限制和交叉口延迟等特征的交通网络,首先采用对偶图方法构造等效网络,在等效网络中采用常规的最短路算法计算最优路线,然后将它转化为原道路网中的行车路线。试验证明这种方法能够有效解决包含交通特征的车辆导航系统路线规划问题.     

A multi-resolution surface distance model for <Emphasis Type="Italic">k</Emphasis>-NN query processing

A spatial k-NN query returns k nearest points in a point dataset to a given query point. To measure the distance between two points, most of the literature focuses on the Euclidean distance or the network distance. For many applications, such as wildlife movement, it is necessary to consider the surface distance, which is computed from the shortest path along a terrain surface. In this paper, we investigate the problem of efficient surface k-NN (sk-NN) query processing. This is an important yet highly challenging problem because the underlying environment data can be very large and the computational cost of finding the shortest path on a surface can be very high. To minimize the amount of surface data to be used and the cost of surface distance computation, a multi-resolution surface distance model is proposed in this paper to take advantage of monotonic distance changes when the distances are computed at different resolution levels. Based on this innovative model, sk-NN queries can be processed efficiently by accessing and processing surface data at a just-enough resolution level within a just-enough search region. Our extensive performance evaluations using real world datasets confirm the efficiency of our proposed model.     

云环境下利用用户到数据中心建模的高效节能路由算法

针对云计算用户、服务、供应商和数据中心的密度不断增长导致传输数据、网络流量和基础设施的大量能耗问题,提出针对云数据的高效节能路由算法。其目的是在用户和数据中心之间定位出最低能量消耗路线,同时确保用户需求。首先,对用户到数据中心的连通性进行建模,分析了网络拓扑结构;然后为了用户意图最简化和能量最小化,通过遍历节点最小数的基线最短路径算法进行评估,将用户任务通过最节能路径发送到数据中心,从而最小化能量损耗和服务响应时间(SRT)。实验的网络拓扑结构使用互联网服务提供商(ISP)的分支设计。实验结果表明提出的算法具有更短的路由路径长度和更低的路由能耗。此外,最短路径方法只有在成功发送或接收之后才能确定最节能的路由。     

一种面向城市复杂路网最短路径提取的定向收敛算法*

为提高城市复杂路网最短路径提取的效率,针对路网数据量大、结构密集等特点,研究了路网节点之间最短路径的分布特征,通过引入收敛点方式,设计并实现了一种面向复杂路网最短路径快速提取的定向收敛算法。为检验该算法的有效性,利用某城市道路交通网络进行了实验和分析,并与Dijsktra算法、A*算法等比较,证实了该算法能够提高路径搜索效率,且随着城市路网规模的扩大定向收敛算法的高效性将愈加明显。     

Top-<Emphasis Type="Italic">k</Emphasis> query processing in mobile-P2P networks using economic incentive schemes

This work proposes the E-Top system for the efficient processing of top-k queries in mobile ad hoc peer to peer (M-P2P) networks using economic incentive schemes. In E-Top, brokers facilitate top-k query processing in lieu of a commission. E-Top issues economic rewards to the mobile peers, which send relevant data items (i.e., those that contribute to the top-k query result), and penalizes peers otherwise, thereby optimizing the communication traffic. Peers use the payoffs (rewards/penalties) as a means of feedback to re-evaluate the scores of their items for re-ranking purposes. The main contributions of E-Top are three-fold. First, it proposes two economic incentive schemes, namely ETK and ETK+, in which peers act individually towards top-k query processing. Second, it extends ETK and ETK+ to propose a peer group-based economic incentive scheme ETG. Third, our performance evaluation shows that our schemes are indeed effective in improving the performance of top-k queries in terms of query response times and accuracy at reasonable communication traffic cost.     

一种考虑交通限制信息的道路网络模型

随着城市交通网络的发展,实际道路中的交通限制信息使得道路网络中的最优路径规划变得更加复杂,针对这一问题,笔者讨论了一种考虑交通限制信息的道路网络模型,并详细阐述了该模型的存储方法及各种常见交通限制信息的解决方案,然后给出了利用此模型求解最优路径的改进的Diiktra算法描述。最后,笔者根据北京市道路数据建立道路网络,通过实际数据进行验证,实验结果表明,该模型及算法能满足实际道路网络的最优路径分析的需要,具有一定的应用价值。     

基于MapX的电子地图路径规划软件设计

文章设计了基于MapX的可视化电子地图路径规划软件,实现了地图操作中的放大、缩小、漫游、测距、图层控制等功能。该软件可作为交通道路电子导航使用,根据Dijkstra算法完成任意起始点和目的地之间的最短路径计算,提供求懈最短路径功能,根据蚁群算法求解真实路网的路径规划问题,可以在指定的节点范围内寻找一条最优路径,实现路径规划功能。该软件操作简单方便,用户很容易就可以掌握该软件的使用,实现旅游信息的快速查询,给用户带来了方便快捷的信息服务。     

Weighted path queries on semistructured databases

Path queries have been extensively used to query semistructured data, such as the Web and XML documents. In this paper we introduce weighted path queries, an extension of path queries enabling several classes of optimization problems (such as the computation of shortest paths) to be easily expressed. Weighted path queries are based on the notion of weighted regular expression, i.e., a regular expression whose symbols are associated to a weight. We characterize the problem of answering weighted path queries and provide an algorithm for computing their answer. We also show how weighted path queries can be effectively embedded into query languages for XML data to express in a simple and compact form several meaningful research problems.     

A distributed mobile database implementation on Pocket PC mobile devices communicating over Bluetooth

This paper describes a distributed database system implementation built on top of stand-alone mobile databases found on mobile devices. At the heart of the architecture are elected devices that take on the role of data directories which collect the schema of the databases and become the contact points for all nodes that wish to submit queries against the distributed database. The system is implemented on Pocket PCs that run the Microsoft WinCE operating system and communicate using Bluetooth, thus limiting the architecture to eight devices, which is a restriction imposed by piconets. Sample databases were configured on the devices that ran the SQL Server CE database engine, and a list of 170 sample queries of varying complexities were designed to conduct performance evaluation. This evaluation involved measurement of query response time, generated traffic, and device energy consumption. The obtained results indicated the feasibility of the system and its potential for providing mobile users with a framework for aggregating disparate data that are stored in mobile databases in the wireless ad hoc network.     

Voronoi-based range and continuous range query processing in mobile databases

With the wide availability of mobile devices (smart phones, iPhones, etc.), mobile location-based queries are increasingly in demand. One of the most frequent queries is range search which returns objects of interest within a pre-defined area. Most of the existing methods are based on the road network expansion method – expanding all nodes (intersections and objects) and computing the distance of each node to the query point. Since road networks are extremely complex, node expansion approaches are inefficient. In this paper, we propose a method, Voronoi Range Search (VRS) based on the Voronoi diagram, to process range search queries efficiently and accurately by partitioning the road networks to some special polygons. Then we further propose Voronoi Continuous Range (VCR) to satisfy the requirement for continuous range search queries (moving queries) based on VRS. Our empirical experiments show that VRS and VCR surpass all their rivals for both static and moving queries.     

高速公路多匝道远程协同控制技术研究

传统高速公路多匝道控制方法大多是使用线圈进行参数采集,使交通调节率计算不精准,导致技术控制精准度较低,针对该问题,提出了多匝道远程协同控制技术研究。结合高速公路协同环境,限制主线交通,计算车辆进入路网后周期性路径距离和预测时间的通行成本,根据实际路况对系数进行调整,当参数系数为0时,通行成本最低即为最优规划路径,并触发路径诱导执行。充分考虑匝道总流量约束条件,执行诱导方案,获取最短控制周期,使用模糊逻辑算法计算控制周期内的控制率,从而实现多匝道控制目的。通过实验对比结果可知,该技术控制精准度较高,为保障高速公路安全运行奠定基础。