Shortest path queries in mobile broadcast environments

Emerging technologies on Global Positioning Systems (GPS), wireless communications, networking, and Geographic Information Systems (GIS) makes it possible for people to access information related to their locations ubiquitously. In such wireless mobile environments, data-broadcasting can disseminate information to a large group of mobile clients effectively. Using data-broadcasting to provide different types of services, including range query, point query, and nearest neighbor search, has been extensively studied in recent years. Two measurements are usually considered when applying data-broadcasting to provide services, latency and tuning time. The latency is the time between the issuing and completion of a query and stands for the quality of service. The tuning time measures the actual time when a client listens to the broadcast and presents the power consumption. In this paper, we consider how to provide the shortest path service using data-broadcasting and use the idea of hierarchical graphs to propose the protocol. In our solution, the mobile client does not need to store the entire road network and can derive the shortest path by selectively tuning into the broadcast. On the server side, we focus on how to organize the broadcast. In the broadcast, we add a little additional information to reduce the tuning time; thus saving the energy. On the client side, we provide a process to compute the shortest path by listening to the corresponding broadcast. Last, we present and discuss our findings through extensive experiments. Our experimental results show that our approach performs well in terms of the latency and tuning time.