Wireless ad hoc networks consist of a set of autonomous nodes which spontaneously create impromptu communication links, and then collectively perform a task with little help from centralized servers or established infrastructure. Because of the stringent constraints on system resources, as well as highly dynamic and even lossy wireless communication environments, wireless ad hoc networks face challenges for providing information search and extraction with good scalability and efficiency. Scalability and efficiency are assessed mainly with respect to the metric of network communication cost. This thesis explores these issues through the development of novel approaches in two types of emerging wireless networks: mobile ad hoc networks and sensor networks.
We study the information search problem and use wireless mobile ad hoc networks as an example. We propose adaptive strategies that combine both proactive advertising by the servers and on-demand discovery by the mobile hosts. These adaptive strategies determine the relative rate of proactive advertising and on-demand discovery according to system characteristics such as host mobility level and offered load.
We study the information extraction problem and use wireless sensor networks as an example. First, a scalable and robust data aggregation algorithm for information extraction is proposed to obtain the overall data distribution. This data aggregation algorithm exploits the mixture model and the expectation maximization algorithm for parameter estimation. Second, we present energy-aware prediction models, analyze the performance tradeoff between reducing communication cost and limiting prediction cost, and design algorithms to exploit the benefit of energy-aware prediction.
Throughout our study, our efforts focused on dealing with various challenges introduced by the dynamic network environments and stringent resource constraints. This thesis shows that with our efforts the communication cost can be significantly reduced. For example, the adaptive strategies reduce traffic cost by several times compared to the previous proactive strategies and reactive strategies. The proposed framework using data aggregation and prediction reduces communication cost by up to one order of magnitude compared to centralized solutions without aggregation.