Application-specific topology-independent routing for multi-hop wireless networks

Provisioning of rich routing building blocks to mobile ad-hoc networking applications has been of high interest. Several multi-hop wireless network applications need flexibility in describing paths their traffic will follow. To accommodate this need, previous work has proposed several viable routing schemes such as Dynamic Source Routing (DSR) and Trajectory-Based Routing (TBR). However, tradeoffs involved in the interaction of these routing schemes and the application-specific requirements or constraints have not been explored. Particularly, techniques to help the application to do the right routing choices based on a desired metric are much needed. Depending on the application's goals, routing choices should be steered for different metrics rather than the traditional notion of shortest-path in terms of distance. For instance, obstacle or hostility avoidance would require accurate paths, end-to-end traffic engineering/balancing would require minimum utilization paths, low delay routing for multimedia traffic would require short distance paths, and, finally, low loss routing for reliable end-to-end transfers would require minimum congestion paths. Our focus in this dissertation is the of paths. First, we consider techniques that minimize routing protocol state costs under application-based constraints. We study the constraint of of the application's desired route, as this constraint provides a range of choices to the applications. As a crucial part of this optimization framework, we investigate the tradeoff between the packet header size and the network state. We, then, apply our framework to the case of TBR with application-based accuracy constraints in obeying a given trajectory and show that approximating trajectories under such accuracy constraints is NP-hard. We develop heuristics solving this problem and illustrate their performance. Second, we take our TBR framework to a more general solution by adding automated trajectory generator and end-to-end traffic engineering support. We focus on the context of multi-hop wireless protocols for which application-specific needs are emphasized along with a highly dynamic underlying network environment. We propose a framework supporting a standardized way of interfacing between the network routing and the wireless applications. We use this framework to develop a roadmap-based trajectory planning scheme to engineer the end-to-end traffic over multi-hop wireless networks. We illustrate how our roadmap-based approach can automate the process of planning/selecting the trajectories so that better balancing of the traffic is achieved. We compare our roadmap-based trajectory planning approach to its shortest-path routing counterpart, Greedy Parameter Stateless Routing (GPSR), and show that beneficial tradeoffs can be attained.