A GPS system selects routes between two points with minimum physical distance or minimum driving time. Here we address a special sort of route selection problem. Given a road map with driving distance and wireless connectivity for every road segment, find a driving route that maximizes total wireless connectivity while its length is bounded by a predetermined value. during this thesis, we present three heuristic algorithms.
Initially they compute the shortest path for determining a distance bound. the primary modifies the road map by replacing each road segment with the ratio of the space 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 supported their distance from a shortest path. The closer the intersection to such a path, the upper the penalty value. Itselects among unexplored intersections one that has the minimum penalty value.
The final algorithm utilizes the primary algorithm twice for choosing a route once to seek out distance and communication capacity of every intersection from the origin then an equivalent from the destination.
Through extensive simulation of grid road networks, we discover that each one three algorithms select routes that have higher communication capacity than any shortest paths. More interesting is that the communication capacity gain is above the route length increase.
APPROACH
Building upon the very best connection capacity shortest paths found within the example we examine heuristic algorithms for locating 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 employed as a subroutine for further algorithms. Next, we alter Dijkstra’s shortest path algorithm to utilize the Wireless Connectivity Ratio Graph to seek out higher connectivity paths.
This is presented. we present an algorithm that prefers routes beyond the shortest paths while utilizing the WCRG. the ultimate algorithm is presented. during which we explore even more paths by determining an intermediate intersection to undergo so as to enhance 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 therefore the origin intersection, Org. The set of intersections whose final value of distance and connection capacity are known is kept in S. because the algorithm starts,S is an empty set.
Initialize-SP(WCG,Org)
1 for every Ik ∈ WCG.I
2 Ik.dist=∞;
3 Ik.cc= 0;
4 Org.dist= 0;
Algorithm for choosing 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 therefore the set of intersections adjacent to the intersection I k, respectively.
Algorithm for choosing Length-Bounded Route on WCRG with Penalty for Shorter Routes:
The algorithm presented here is meant to explore first paths faraway from the shortest path. to realize that objective, the algorithm penalizes intersections that are almost or on a shortest path to the destination so as to succeed in distances closer to the space bound.
The penalty value for every intersection is calculated by adding the present path distance and therefore the distance to the destination and subtracting that sum from the space bound. almost like the algorithm presented in the previous section, it works in two phases. The shortest distance from each intersection to the destination is calculated within the first phase using the modified Dijkstra’s algorithm.
Two-Pass Algorithm for choosing 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 undergo that intersection. It uses the ratio graph WCRG , rather than distance graph WCG.
Implementation:
For the implementation of the algorithms, we first must have Road Networks to check them on. the only thanks to do that is by utilizing two-dimensional arrays representing the adjacency matrix for the Road Networks. an equivalent sort of arrangement is employed for both the Wireless Capacity Graphs and therefore the Wireless Connectivity Ratio Graphs.
EXPERIMENTS AND RESULTS
In order to guage the performance of those algorithms, we’ve run them on many various road networks. Here we present those experiments and the results. In we individually analyze each algorithm for successes and shortcomings of the specified outcome. That is, we present example cases where each algorithm does and doesn’t find the optimal possible connection capacity within the specified bound.
Initial Evaluation of Algorithms:
We begin by determining cases during which each algorithm succeeds find higher connection capacity routes within a bound and cases where each fails to seek out a path that’s available.
Experimental Evaluation:
In order to research the presented algorithms, we utilize them on instances of randomized experimental road networks. That procedure is described during this section.
Algorithm Performance Comparison and Discussion:
Now, we are ready to evaluate the algorithms with reference to both experimental data and contrived failure situations from Section 6.1. While in world applications, the distribution of hotspots or cell towers is way from random, we will still make valid deductions from the info presented. From everything of the experimental data set, we will see that the ratio and two-pass algorithms perform very similarly.
SUMMARY AND FUTURE WORK
In this paper we’ve proposed and evaluated three algorithms for choosing 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 choosing routes that maximize wireless connection capacity while length of the chosen routes are bounded by a given length. it’s documented that bounded length path selection problem is NP-hard and hence a polynomial time algorithm is unlikely to exist.
Proposed algorithms might not find routes that have maximum wireless connection capacity, but results from extensive evaluations have shown that the communication capacity gain is above the route length increase.
For instance, when distance increase was bounded by 20%, on a mean path selected by one algorithm was 11.4% longer than the length of the shortest path but connection capacity was about 32.5% above that of all shortest paths. Solutions to the present problem have many practical applications.
For instance, one can select a driving route between two points such the entire driving time is not any morthan a given bound but allows the entire upload of a video to YouTube.
Another application would be distribution of car 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 world data by connecting to sources like opensignal.com to supply connection capacity would leave practical utilization of the algorithms. It should be possible to attach this data along side road network data and embed the algorithms into GPS guidance systems.
Source: University of Miami
Author: Brandon Clark Sato