|dc.description.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.||en