Wireless ad-hoc networks enable high utility applications for disaster recovery or military situations, mesh networks of homes, and wireless sensing networks. This work considers multiple-layer modeling, optimization, and design of multi-hop wireless ad hoc networks. It includes the two, currently debated, architectural choices - cross-layer and layered. The project contributes to practical design as well as fundamental/theoretical understanding. It considers three canonical problems: optimal correlated data aggregation, (cooperative) data relaying, and delay-throughput optimality. Mathematical tools used include information theory, stochastic decision processes, queuing theory and algorithm complexity. Simulations of the new models complement the mathematical analysis. Some of the resulting designs are prototyped experimentally. The project involves undergraduate and graduate students, a jointly developed outreach plan with a high school teacher, and course/laboratory development. Results, including software code, are disseminated through the project web page as well as regular publications.
The major research outcomes of this activity are: 1. Optimal Localized Decision Policies in Ad Hoc and Sensor Networks In computer networks, each node makes decisions based on its local information (i.e. without global knowledge) under uncertain conditions. For example, a sensor network node may need to decide whether to send its local samples immediately, thus minimizing delay, or wait for more samples to aggregate before sending the data, thus minimizing communication energy consumption. Similarly, an ad hoc network node may need to decide whether to select a particular neighboring node to forward a packet to, or to keep searching for other neighbors with more favorable channel conditions. These types of decision problems are quite common in wireless networks. In our work, we formally define them as stochastic decision problems, and derive optimal policies that maximize the expected reward. 2. Queuing Theoretic Models of Throughput and Delay in Wireless Ad Hoc and Mesh Networks Wireless mesh networks, represented for example by the new IEEE 802.16 (WiMAX) standard, are emerging as a promising means of providing connectivity to communities in both affluent and poor parts of the world. They are also proposed as a solution for the last-mile problem, and extending network access to rural areas. They build on the concept of ad-hoc networks, but they also rely on the presence of relatively more capable backbone mesh routers forming a two-level hierarchy, thus allowing mesh networks to have better capacity than infrastructure-less multihop ad hoc networks. In both types of networks, delay and throughput are two important performance metrics. In this work, we develop a queuing network model for characterizing the average end-to-end delay and maximum stable throughput (per source-destination pair) in ad-hoc and wireless mesh networks that employ random medium access (MAC) schemes. We analyze how the results obtained using the proposed queuing network framework compare against previous information theoretic results on asymptotic capacity of infrastructure-less ad hoc networks. 3. Information Theoretic Analysis of Geographic Routing Protocols Since routing protocols need to adjust to topology change, an overhead is incurred due to the exchange of routing messages. For variable topology networks, such an overhead may impose a significant limit on scalability and effective capacity. For example, it has been noted from measurement data that in certain modern networks (e.g. a portion of the U.S. Air Force network), such overheads constituted 80% of the total traffic carrying capacity. We developed an information-theoretic framework for the characterization of bounds on the least overhead incurred by various classes of routing protocols under a uniform traffic pattern. The minimum protocol overhead is related to the minimum amount of information (i.e. effort) needed to identify the current state of the system, possibly within a distortion bound. we can now characterize the highest possible effective capacity of a network, by subtracting the lowest capacity deficit among all possible protocol designs. 4. Analysis and design of algorithms for event capture using mobile sensors. Mobile sensors cover more area over a period of time than the same number of stationary sensors. However, the quality of coverage achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this research we consider the problem of event capture using mobile sensors. The events of interest arrive at certain points in the sensor field and fade away according to arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. For this scenario we analyze how the quality of coverage scales with the velocity, path and number of mobile sensors. We also present algorithms various motion planning problems. The results have wide range of applications in areas like surveillance, wildlife monitoring, hybrid sensor networks and under-water sensor networks. 5. Connectivity and routing in time-evolving networks. In this work, we investigated the relationship between the dynamism in the network and the network connectivity in mobile networks. A novel combinatorial time-graph model is proposed. This study provides a connection between the structure and the properties of time-graphs and the network connectivity in a dynamic network. To the best of our knowledge, there is no prior study that makes a similar attempt. The insights lead to design of weak state routing protocol The major educational and outreach outcomes are: 1. Development of a new course on Mobile Wireless Networks at RPI, offered every year. 2. Development of a sensor network research and teaching laboratory. 3. Outreach to high school students in collaboration with a local high school teacher. 4. Training of 7 PhD students and one MS student.
