Optimization Algorithms for Information Retrieval and Transmission in Distributed Ad Hoc Networks

Abstract

An ad hoc network is formed by a group of self-configuring nodes, typically deployed in two or three dimensional spaces, and communicating with each other through wireless or some other media. The distinct characteristics of ad hoc networks include the lack of pre-designed infrastructure, the natural correlation between the network topology and geometry, and limited communication and computation resources. These characteristics introduce new challenges and opportunities for de- signing ad hoc network applications. This dissertation studies various optimization problems in ad hoc network information retrieval and transmission. Information stored in ad hoc networks is naturally associated with its location. To effectively retrieve such information, we study two fundamental problems, range search and object locating, from a distance sensitive point of view, where the retrieval cost depends on the distance between the user and the target information. We develop a general framework that is applicable to both problems for optimizing the storage overhead while maintaining the distance sensitive retrieval requirement. In addition, we derive a lowerbound result for the object locating problem which shows that logarithmic storage overhead is asymptotically optimal to achieve linear retrieval cost for growth bounded networks. Bandwidth is a scarce resource for wireless ad hoc networks, and its proper utilization is crucial to effective information transmission. To avoid conflict of wireless transmissions, links need to be carefully scheduled to satisfy various constraints. In this part of the study, we first consider an optimization problem of end-to-end on- demand bandwidth allocation with the single transceiver constraint. We study its complexity and present a 2-approximation algorithm. We then discuss how to estimate the end-to-end throughput under a widely adopted model for radio signal interference. A method based on identifying certain clique patterns is proposed and shown to have good practical performance.