Routing and Scheduling Algorithms in Resource-Limited Wireless Multi-Hop Networks

The recent advances in the area of wireless networking present novel opportunities for network operators to expand their services to infrastructure-less wireless systems.Such networks, often referred to as ad-hoc or multi-hop or peer-to-peer networks, require architectures which do not necessarily follow the cellular paradigm. They consist of entirely wireless nodes, fixed and/or mobile, that require multiple hops (and hence relaying by intermediate nodes) to transmit their messages to the desired destinations. The distinguishing features of such all-wireless network architectures give rise to new trade-offs between traditional concerns in wireless communications (such as spectral efficiency, and energy conservation) and the notions of routing, scheduling and resource allocation. The purpose of this work is to identify and study some of these novel issues, propose solutions in the context of network control and evaluate the usual network performance measures as functions of the new trade-offs.To these ends, we address first the problem of routing connection-oriented traffic with energy efficiency in all-wireless multi-hop networks. We take advantage of the flexibility of wireless nodes to transmit at different power levels and define a framework for formulating the problem of session routing from the perspective of energy expenditure. A set of heuristics are developed for determining end-to-end unicast paths with sufficient bandwidth and transceiver resources, in which nodes use local information in order to select their transmission power and bandwidth allocation. We propose a set of metrics that associate each link transmission with a cost and consider both the cases of plentiful and limited bandwidth resources, the latter jointly with a set of channel allocation algorithms. Performance is measured by call blocking probability and average consumed energy and a detailed simulation model that incorporates all the components of our algorithms has been developed and used for performance evaluation of a variety of networks.In the sequel, we propose a "blueprint" for approaching the problem of link bandwidth management in conjunction with routing, for ad-hoc wireless networks carrying packet-switched traffic. We discuss the dependencies between routing, access control and scheduling functions and propose an adaptive mechanism for solving the capacity allocation (at both the node-level and the flow-level) and the route assignment problems, that manages delays due to congestion at nodes and packet loss due to error prone wireless links, to provide improved end-to-end delay/throughput. The capacity allocations to the nodes and flows and the route assignments are iterated periodically and the adaptability of the proposed approach allows the network to respond to random channel error bursts and congestion arising from bursty and new flows