Publication Date

2014-12-12

Availability

Open access

Embargo Period

2014-12-12

Degree Name

Master of Science (MS)

Department

Computer Science (Arts and Sciences)

Date of Defense

2014-12-12

First Committee Member

Dilip Sarkar

Second Committee Member

Mitsunori Ogihara

Third Committee Member

Manohar Murthi

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. It selects 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.

Keywords

algorithm; shortest path; bounded maximum length path; communication capacity

Share

COinS