Autonomic Navigation System Based on Predicted Traffic and VANETs

To avoid an expected traffic jam, drivers make detours based on limited information; however, the majority following the alike routes may result in an unexpected congestion. Conventional navigation approaches are unable to respond to the unexpected congestion because these approaches do not consider the routes taken by other vehicles. Navigation systems that utilize global traffic information can improve gas consumption, CO₂ emissions and travel time. Therefore, in this paper, the authors propose an autonomic navigation system (ANS) operating over vehicular ad-hoc networks (VANETs). The proposed ANS adopts a hierarchical algorithm to plan vehicle routes. The proposed ANS imitates the human nervous system when managing the navigation system, in which vehicles monitor traffic via VANETs. Moreover, this paper proposes a time-dependent routing algorithm that uses a novel traffic prediction method based on the routes of vehicles. This paper adopts EstiNet as simulator tool that dominates hundreds or thousands of VANET-based vehicles routing in two maps, Manhattan area, and Taipei city. The results show that the proposed ANS improves the average speed by 60.02 % when compared with the shortest path first (SPF) algorithm and by 15.49 % when compared with the distributed method of a traffic simulation in the Manhattan area. The proposed ANS also improves the average speed by 30.5 % when compared with the SPF algorithm and by 15.8 % when compared with the distributed method of a traffic simulation in the Taipei area. Furthermore, to emulate real environments, there is a scenario in which only a portion of the vehicles complies with the proposed ANS.     

The strategy and deployment plan for VICS

The objective of a vehicle information and communication system (VICS) is to disperse traffic by providing drivers with road traffic information to enable them to satisfy their natural desire to “get there faster”. Put simply, VICS is based on drivers' arbitrary selection of routes and on the automobile's unique ability to take any desired route. The objective is to promote the safe, smooth flow of traffic by naturally distributing the flow of traffic, which is done by guiding cars to the appropriate routes in accordance with drivers' instinctive desire to reach their destinations quickly by avoiding traffic congestion. VICS distributes road traffic information such as traffic jams or accidents to drivers in real time, and stimulates drivers for accurate and proper utilization     

基于终点的用户均衡交通分配模型求解算法

用户均衡分配模型是更接近实际交通状态的分配模型,它是建立在出行者总选择起迄点间交通时间最短的路径作为出行路线的行为假设基础上的。分析基于终点的用户均衡交通分配模型,指出该模型与基于路径均衡配流模型是等价的,在选择美国BPR路阻函数后,模型可以转化为带线性约束的非线性规划问题,并给出模型的矩阵表示。对这类问题,采用简便实用的仿射尺度算法求解,给出算法的基本思想及详细的实现过程。仿真结果显示,所得最优解满足Wardrop第一准则,表明该算法是有效的,可用于大型路网的配流计算。     

分布式全局调度动态反馈自由飞算法

在诸多空管算法基础上,提出了分割空域航线和时间并压缩的研究范式。单机根据空域航线点阵和时间窗矩阵的环境参数进行全局路径寻优,然后沿全局路径模拟飞行进行局部路径寻优,并将获得的环境参数随时回写空域航线点阵和时间窗矩阵,使得全局优化和局部优化动态反馈并逼近收敛一致。算法突破传统算法难以兼顾分布优化与集中优化的局限。     

Post‐Disaster least loaded lightpath routing in elastic optical networks

Disaster events directly affect the physical topology of core networks and may lead to simultaneous failure of multiple lightpaths leading to massive service outages for network operators. To recover from such a failure scenario, the existing routing algorithms running on network nodes (routers or switches) typically attempt to reestablish the connections over new routes with shortest distances and hop count approach. However, this approach may result in congestion on some links, while other links may have the unutilized capacity. Hence, intelligent lightpath computing techniques are required to efficiently route network traffic over the new routes by considering traffic load of each link in addition to distance and hop count to minimize network congestion. In this paper, we have proposed a capacity‐constrained maximally spatial disjoint lightpath algorithm to tackle the provisioning and restoration of disrupted lightpaths in a postdisaster scenario in the context of elastic optical networking. This algorithm computes an alternate least loaded lightpath for disrupted primary lightpath using capacity‐constrained shortest lightpath. Alternate lightpath selection is based on a criteria parameter for a lightpath to be least loaded and constrained by either the length or the spatial distance between primary and alternate lightpaths. The spatial distance between lightpaths enables to reestablish the disrupted connection request away from disaster proximity. The performance of the proposed algorithm is evaluated through simulation for several parameters like blocking probability, network utilization, connection success rates, and minimum spatial distance.     

一种波长转换范围受限全光网中的波长分配算法

本文研究了波长转换范围受限全光网中的动态路由和波长分配问题,提出了一种固定备选路由条件下新的路由和波长分配算法.算法引入了波长相关性的概念,用波长关联权值定量描述了各路由的前后链路上不同波长之间的相互依赖关系.在建立连接时首先使用那些依赖性强,对其他路由影响小的波长,从全局的角度出发选择最优的路由和波长分配方案.计算机仿真表明,本文算法能够适用于稀疏网络和网状网,在均匀业务强度或者大部分业务量来自于长跳路由的情况下,本文算法能够显著降低网络阻塞概率和使用的波长转换器数目,有效提高系统性能.     

VANET-based secure taxi service

Taxi service is an important type of point-to-point transportation in many cities. One of the major concerns is the safety of both passengers and taxi drivers. In this paper, based on the framework of VANET (Vehicular Ad-hoc NETwork), we propose a novel secure taxi service scheme to tackle the problem. First, a driver needs to authenticate himself using a password before he can provide any service. Second, after picking up a passenger, the taxi’s OBU (on-board unit) needs to continuously send its current location to the trusted server. This location is then double-verified with RSU (road-side unit) signatures. We also design a cooperative tracking mechanism to locate a taxi in case of emergency. In some occasions, taxi passengers as well as taxi drivers are concerned with their privacy (such as travelling route). We incorporate privacy-preserving measures into our scheme. The taxi’s OBU uses pseudo identities instead of real identity for all ongoing transmissions so that a passenger’s travelling route (or the driver’s travelling route when he/she is not carrying any passengers) cannot be traced by a third party easily. We show by simulation that the total delay (from 1 to 9 s) introduced by all security measures is small while the total number of messages required to be transmitted in the network is reasonable.     

Dynamic routing and wavelength assignment for limited-range wavelength conversion

We propose a dynamic routing and wavelength assignment algorithm in an all-optical network with limited-range wavelength conversions. For each randomly arrived request, the correlation of different wavelengths on different links in all possible routes is described by the wavelength weight in our algorithm. We try to assign wavelengths on each candidate route using a shortest-path algorithm based on the wavelength weight and choose the best as its route and wavelength assignment scheme. Numerical results obtained for NSFNET and a 12-node ring show that our algorithm can greatly reduce the blocking probability and the number of required conversions under uniform traffic or traffic dominated by larger hop routes.     

关于出租车载客地点序列推荐技术的研究

在大城市中,出租车已成为实现智能交通运输系统不可或缺的一环。然而,由于一些出租车司机的驾驶经验,和对城市活动的熟悉程度的不足,使得其在寻找乘客时会采取毫无目的的随机漫游策略。这就导致了出租车司机的收益不高,同时也造成了能源的消耗以及环境的污染。针对此问题,将提出出租车载客地点的推荐模型,使得模型给出的推荐地点序列能获得较高的期望收益。具体来说,将基于出租车GPS轨迹数据建立出租车载客地点的马尔科夫决策过程模型,并给出求解该模型的2种算法。仿真实验结果显示,与典型的TopK方法相比,给出的推荐结果能更好地提高单位时间内出租车司机的收益。     

Bayonet-corpus: a trajectory prediction method based on bayonet context and bidirectional GRU

Predicting travel trajectory of vehicles can not only provide personalized services to users, but also have a certain effect on traffic guidance and traffic control. In this paper, we build a Bayonet-Corpus based on the context of traffic intersections, and use it to model a traffic network. Besides, Bidirectional Gated Recurrent Unit (Bi-GRU) is used to predict the sequence of traffic intersections in one single trajectory. Firstly, considering that real traffic networks are usually complex and disorder and cannot reflect the higher dimensional relationship among traffic intersections, this paper proposes a new traffic network modeling algorithm based on the context of traffic intersections: inspired by the probabilistic language model, a Bayonet-Corpus is constructed from traffic intersections in real trajectory sequence, so the high-dimensional similarity between corpus nodes can be used to measure the semantic relation of real traffic intersections. This algorithm maps vehicle trajectory nodes into a high-dimensional space vector, blocking complex structure of real traffic network and reconstructing the traffic network space. Then, the bayonets sequence in real traffic network is mapped into a matrix. Considering the trajectories sequence is bidirectional, and Bi-GRU can handle information from forward and backward simultaneously, we use Bi-GRU to bidirectionally model the trajectory matrix for the purpose of prediction.     

Real Time Anomalous Trajectory Detection and Analysis

GPS-equipped taxis can be considered as pervasive sensors and the large-scale digital traces produced allow us to reveal many hidden facts about the city dynamics and human behaviors. In this paper we present a novel GPS-based taxi system which can detect ongoing anomalous passenger delivery behaviors leveraging our proposed iBOAT method. To achieve real time monitoring, we reduce the response time of iBOAT by more than five times with an inverted index mechanism adopted. We evaluate the effectiveness of the system with large scale real life taxi GPS records while serving 200,000 taxis. With this system, we obtain about 0.44 million anomalous trajectories out of 7.35 million taxi delivery trips, which correspond to 7600 taxis’ GPS records in one month time in the city of Hangzhou, China. Through further analysis of these anomalous trajectories, we observe that: (1) Over 60 % of the anomalous trajectories are “detours” that travel longer distances and time than normal trajectories; (2) The average trip length of drivers with high-detour tendency is 20 % longer than that of normal drivers; (3) The length of anomalous sub-trajectories is usually less than a third of the entire trip, and they tend to begin in the first two thirds of the journey; (4) Although longer distance results in a greater taxi fare, a higher tendency to take anomalous detours does not result in higher monthly revenue; and (5) Taxis with a higher income usually spend less time finding new passengers and deliver them in faster speed.     

Hamilton模型在智慧文旅设计中的应用研究

旅游线路优化问题是旅行规划中一个重要课题,是旅游业发展到一定阶段的必然要求。对传统Hamilton算法进行优化改进,对云南省的5A级景点线路进行了优化。并将该算法设计成程序,便于游客的线路选择。研究结果发现:使用该方法对景点的经纬度数据进行一次分配,便可获最短的旅行线路。这种算法减少了线路选择的时间,操作更加简单,展示了定量研究方法在旅游线路优化设计中的应用潜力。     

基于贪婪算法的旅游路线优化问题

针对目前国内旅游线路的设计多偏向于从景区特色出发,而较少从旅行时间和路径入手的问题,利用贪婪算法设计数学模型。在旅行者不多于15天的旅行约束条件下,对国内201个5A风景区进行聚类分块,将201个景区简化为31个省市。算得从西安市出发到各省市的旅行时间并得到21条符合要求的旅行路线。将相关结果以更直观的图像形式展现,为旅行路线的设计研究提供了参考。     

Estimation of left-turning travel time at traffic intersection

Traffic guidance is a promise approach of traffic congestion alleviation, and the travel time is one of the most important basic data for the reasonable and effective route planning which is the core of traffic guidance. The traffic intersection is one of the chief components of the whole traffic road networks, so the estimation of travel time of the intersection plays an important role in traffic guidance. This paper pays more attention to the estimation of travel time for left-turning lane connected to an intersection, introduces the features for travel time estimation, and designs an estimator based on the learning vector quantity (LVQ) neural network. A suite of reasonable test shows that the method can effectively estimate the travel time of vehicles at left-turning lane with lower error to the real data.     

A linear‐based trunk reservation routing algorithm for ATM networks

In this paper a practical routing algorithm is proposed that increases the network throughput irrespective of the network traffic load. Its effectiveness is based on an efficient cost function which achieves a successful trade‐off between the use of the minimum‐hop routes and the application of the load‐balancing concept. Moreover, it employs the known Trunk Reservation notion according to a probability that increases linearly with the traffic load. This results in an effective compromise of the performance of the algorithm between light and heavy traffic loads. Finally, its simplicity and its suitability for a real‐time application render it as an efficient routing algorithm for ATM networks. Copyright © 1999 John Wiley & Sons, Ltd.     

一种基于蚁群算法和非线性长度的多约束路由算法

在分析了多种路由算法的基础上,设计了一种基于蚁群算法的多约束路由算法。该算法采用了非线性路径长度,通过蚂蚁的周游获得长度更短的多约束路径。仿真表明,该算法在最短路径获取和路由发现成功率方面都有高效的表现。     

Increased network routing efficiency through coordinated Fibbing

For finding the best route in a network, distributed routing offers robustness but has poor flexibility while central control of software‐defined networking is just the opposite. The Fibbing architecture can run distributed routing protocols on software‐defined networking and has both robustness and flexibility. The 2 main steps of Fibbing's process are (1) compute a route that is available for the network according to the network topology and the flow request and (2) add fake nodes and fake links to augment the network topology in conformity with the distributed routing protocol and the route computed in the first step. Both of the 2 steps affect the performance of the network, but Fibbing does not consider them coordinately, and the cost of choosing the routes can be reduced further. In this paper, a coordinated algorithm for Fibbing is proposed to determine a lowest‐cost route. In the process to calculate an available route, our algorithm accommodates not only the network topology and the flow request but also the fake nodes and the fake links. The experiments on random topologies and classic topologies show that our algorithm can reduce the numbers of the fake nodes and the costs of the chosen routes, with the improved flow request acceptance ratios achieved.     

智能化交通模糊控制系统研究

避免城市道路交通堵塞的有效途径，是实时的根据交通线路的通行情况，帮助驾驶员进行决策，选择合适的行驶线路。本文以车辆通行某线路的实际时间与车辆通行该线路的预测时间的偏差作为依据，模糊决策该线路的交通状况，并将决策结果实时的发布给驾驶员，可达到有效引导交通的作用。     

SMART: Statistically Multiplexed Adaptive Routing Technique for Ad Hoc Networks

This paper develops a common solution to the problems of discovery, maintenance, and use of multiple routes in ad hoc networks. The performance criterion is the average time taken by a packet to reach its destination through multiple hops. A source node considers each of its neighbors (reachable by direct wireless transmission) as a next-hop for every possible destination. The effect of delay at a next-hop and beyond, until the packet reaches its destination, is approximately modeled as an equivalent M/M/1 queuing system. Available neighbors at every node provide multiple routes. Multiple routes are statistically multiplexed to distribute the load as well as to deal with changes in data rates and network configuration. The potential of each next-hop neighbor of a node in providing a viable route is estimated on-line and the proportions of traffic routed through these multiple neighbors are also updated adaptively.We study this approach and conduct extensive experiments over a network with two extreme cases of simulated traffic patterns, the Poisson, and the self-similar types. Even when the network topology is static, our algorithm responds to bursts in the traffic pattern and reduces buffer losses through the use of alternative, less congested routes. We also present simulation experiments and results to demonstrate the effectiveness of our algorithm in the presence of mobility, using self-similar traffic. Mobility is simulated by means of the random waypoint model in which nodes move with varying speeds. Results show that our simple unified approach handles the problems of mobility as well as network congestion very well.     

Discovering long lifetime routes in mobile ad hoc networks

In mobile ad hoc networks, node mobility causes frequent link failures, thus invalidating the routes containing those links. Once a link is detected broken, an alternate route has to be discovered, incurring extra route discovery overhead and packet latency. The traffic is also interrupted at the transport layer, and proper traffic recovery schemes have to be applied. To reduce the frequency of costly route re-discovery procedures and to maintain continuous traffic flow for reliable transport layer protocols, we suggest discovering long lifetime routes (LLR). In this paper, we first propose g-LLR, a global LLR discovery algorithm, that discovers LLRs of different route lengths for any given pair of nodes. We then propose a distributed LLR discovery scheme (d-LLR) that discovers two of the most desirable LLRs through one best-effort route discovery procedure. Simulations show that the lifetimes of the routes discovered by d-LLR are very close to those discovered by g-LLR. Simulations also show that the performance of different transport layer protocols is greatly improved by using LLRs. More importantly, traffic can remain continuous using the provided LLRs. D-LLR can be implemented as an extension to existing ad hoc routing protocols, and it improves the performance of transport layer protocols without modifications on them.