ABSTRACT:
A GPS system selects routes between two points with minimum physical distance or minimum driving time. Here we address a different type of route selection problem. Given a road map with driving distance and wireless connectivity for each road segment, find a driving route that maximizes total wireless connectivity while its length is bounded by a predetermined value. In this thesis, we present three heuristic algorithms.
Initially they compute the shortest path for determining a distance bound. The first modifies the road map by replacing each road segment with the ratio of the distance and wireless communication capacity, and selects a route on this modified road map that satisfies the length bound.
The second assigns a penalty value to intersections based on their distance from a shortest path. The closer the intersection to such a path, the higher the penalty value. Itselects among unexplored intersections one that has the minimum penalty value.
The final algorithm utilizes the first algorithm twice for selecting a route once to find distance and communication capacity of each intersection from the origin and then the same from the destination.
Through extensive simulation of grid road networks, we find that all three algorithms select routes that have higher communication capacity than any shortest paths. More interesting is that the communication capacity gain is higher than the route length increase.
BACKGROUND INFORMATION
First we define a road network as a weighted graph. Every vertex of the graph is an intersection of two or more road segments. The weights of a road segment is its physical distance or time it takes to drive from one end to the other end of the road segment.
- Definition 1 (Road Network)
- Definition 2 (Path)
- Definition 3 (Path Length)
- Definition 4 (Wireless Capacity Graph)
- Definition 5 (Wireless Connection Capacity)
- Definition 6 (Wireless Connectivity Ratio Graph)
APPROACH
Building upon the highest connection capacity shortest paths found in the example we examine heuristic algorithms for finding longer paths that have higher connection capacity without sacrificing computational complexity.First a modified version of Dijkstra’s shortest path algorithm from is presented.
This algorithm finds a shortest path with maximum communication capacity and is used as a subroutine for further algorithms. Next, we alter Dijkstra’s shortest path algorithm to utilize the Wireless Connectivity Ratio Graph to find higher connectivity paths.
This is presented. we present an algorithm that prefers routes further from the shortest paths while utilizing the WCRG. The final algorithm is presented. in which we explore even more paths by determining an intermediate intersection to pass through in order to improve connectivity.
Max Connection-Capacity SP Selection Algorithm:
The algorithm initializes the variables by calling the procedure Initialize-SP(WCG,Org). The inputs to initialization procedure are the wireless connection capacity graph WCG and the origin intersection, Org. The set of intersections whose final value of distance and connection capacity are known is kept in S. As the algorithm starts,S is an empty set.
Initialize-SP(WCG,Org)
1 for each Ik ∈ WCG.I
2 Ik.dist=∞;
3 Ik.cc= 0;
4 Org.dist= 0;
Algorithm for Selecting Length-Bounded Route on WCRG:
Before we present the algorithm, some additional notations are necessary. For an intersection Ik, the known ratio-distance from the origin intersection, Org, is denoted as Ik. ratioDist, which is computed using the ratio values in C. Also, WCRG.I and WCRG.Adj[Ik] denotes the set of intersections in WCRG and the set of intersections adjacent to the intersection I k, respectively.
Algorithm for Selecting Length-Bounded Route on WCRG with Penalty for Shorter Routes:
The algorithm presented here is designed to explore first paths away from the shortest path. To achieve that objective, the algorithm penalizes intersections that are near to or on a shortest path to the destination in order to reach distances closer to the distance bound.
The penalty value for each intersection is calculated by adding the current path distance and the distance to the destination and subtracting that sum from the distance bound. Similar to the algorithm presented in the previous section, it works in two phases. The shortest distance from each intersection to the destination is calculated in the first phase using the modified Dijkstra’s algorithm.
Two-Pass Algorithm for Selecting Length-Bounded Route on WCRG:
The final algorithm we present here searches for a path by choosing an intermediate intersection and stitching together the shortest-ratio paths which pass through that intersection. It uses the ratio graph WCRG , instead of distance graph WCG.
Implementation:
For the implementation of the algorithms, we first must have Road Networks to test them on. The simplest way to do this is by utilizing two-dimensional arrays representing the adjacency matrix for the Road Networks. The same type of data structure is utilized for both the Wireless Capacity Graphs and the Wireless Connectivity Ratio Graphs.
EXPERIMENTS AND RESULTS
In order to evaluate the performance of these algorithms, we have run them on many different road networks. Here we present those experiments and the results. In we individually analyze each algorithm for successes and shortcomings of the desired outcome. That is, we present example cases where each algorithm does and does not find the optimal possible connection capacity within the desired bound.
Initial Evaluation of Algorithms:
We begin by determining cases in which each algorithm succeeds in finding higher connection capacity routes within a bound and cases where each fails to find a path that is available.
Experimental Evaluation:
In order to analyze the presented algorithms, we utilize them on instances of randomized experimental road networks. That procedure is described in this section.
Algorithm Performance Comparison and Discussion:
Now, we are able to evaluate the algorithms with respect to both experimental data and contrived failure situations from Section 6.1. While in real world applications, the distribution of hotspots or cell towers is far from random, we can still make valid deductions from the data presented. From the entirety of the experimental data set, we can see that the ratio and two-pass algorithms perform very similarly.
SUMMARY AND FUTURE WORK
In this paper we have proposed and evaluated three algorithms for selecting driving routes between two points on a road network. Unlike standard GPS systems that select shortest or fastest driving routes, the proposed algorithms are for selecting routes that maximize wireless connection capacity while length of the selected routes are bounded by a given length. It is well known that bounded length path selection problem is NP-hard and hence a polynomial time algorithm is unlikely to exist.
Proposed algorithms may not find routes that have maximum wireless connection capacity, but results from extensive evaluations have shown that the communication capacity gain is higher than the route length increase.
For instance, when distance increase was bounded by 20%, on an average path selected by one algorithm was 11.4% longer than the length of the shortest path but connection capacity was about 32.5% higher than that of all shortest paths. Solutions to this problem have many practical applications.
For instance, one can select a driving route between two points such that the total driving time is no morthan a given bound but allows the complete upload of a video to YouTube.
Another application would be distribution of automobile traffic in congested urban streets.
Making higher speed broadband available on less traveled streets will divert traffic from most congested roads.
Application of the algorithms to real world data by connecting to sources such as opensignal.com to provide connection capacity would allow for practical utilization of the algorithms. It should be possible to connect this data together with road network data and embed the algorithms into GPS guidance systems.
Source: University of Miami
Author: Brandon Clark Sato