Algorithms for Selecting Higher Wireless Connection-Capacity Routes

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 paper, we present three heuristic-algorithms. Initially they compute maximum connection-capacity shortest path for determining a bound for route length. The first algorithm (i) augments the road map by replacing each road segment with ratio of the distance of the road segment and its wireless communication capacity, and (ii) selects a route on the augmented map that satisfies route-length bound. The second algorithm assigns a penalty value to intersections based on their distance from a shortest path -- closer the intersection, higher the penalty. The algorithm selects among unexplored intersections one that has the minimum penalty value. The final algorithm utilize the first algorithm twice for selecting a route -- once to find distance and communication capacity of each intersection from the origin and then to find the same from the destination. Through extensive simulation of grid road networks it was found that on an average all three algorithms select routes that have higher communication capacity than any shortest paths. The most interesting observation is 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.