Efficient Routing and Scheduling in Wireless Networks

The temporal and spatial variation in wireless channel conditions, node mobility make it challenging to design protocols for wireless networks. In this thesis, we design efficient routing and scheduling algorithms which adapt to changing network conditions caused by varying link quality or node mobility to improve user-level performance. We design and analyze routing protocols for static, mobile and heterogeneous wireless networks. We analyze the performance of opportunistic and cooperative forwarding in static mesh networks showing that opportunism outperforms cooperation; we identify interference as the main cause for mitigating the potential gains achievable with cooperative forwarding. For mobile networks, we quantitatively analyze the tradeoff between state information collection (sampling frequency and number of bits per sample) and power consumption for a fixed source-to-destination goodput constraint. For heterogeneous networks comprising of both static and mobile nodes, we propose a greedy algorithm (adaptive-flood) which dynamically classifies individual nodes as routers/flooders depending on network conditions and demonstrate that it achieves performance equivalent to, and in some cases significantly better than, that of network-wide routing or flooding alone. Last, we consider an application-level wireless streaming scenario where multiple clients are streaming different videos from a cellular base station. We design a greedy algorithm for efficiently scheduling multiple video streams from a base station to mobile clients so as to minimize the total number of application-playout stalls. We develop models for coarse timescale wireless channel variation to aid network and application-layer protocol design