Optimal resource allocation and routing in wireless networks

We are in a time of fundamental change in the world's telecommunications infrastructure, with the nature and quantity of information transmission undergoing major transformation. With expanding interest in mobile access to this communications infrastructure has come rapid growth in the number of users of wireless communication networks. The backbone of this growth has been single-hop networks, such as cellular systems, in which service areas are under the central control of a base station. More recently, researchers began investigating ad hoc wireless networks, which operate without a central controller, with each node acting as a network router. In this dissertation, we formulate models for both kinds of wireless networks, and develop optimal policies (protocols) under a variety of system assumptions.; First, we formulate a problem in single-hop resource (multi-channel) allocation for wireless networks, under general arrival and connectivity processes at each mobile node. We provide conditions sufficient to guarantee the optimality of an index policy for this problem. We then refine the aforementioned sufficient conditions under additional assumptions on the arrival and connectivity processes.; Next, we define a problem which both extends and restricts the previous model. The extension is to include a switching cost when server (channel) allocation changes; this cost models the penalty paid when a communications resource is moved between customers. The restriction is to include only one server in the model. We provide conditions sufficient to guarantee the optimality of an index policy for this problem.; Finally, we present a time-invariant stochastic model for routing in ad hoc wireless networks, and we discuss the design decisions leading to this model. We first view the routing problem as a problem of centralized control, and prove optimality of an index policy. Then, we demonstrate that this index policy can be implemented in a distributed manner. We add quality of service considerations by allowing time-varying system parameters, and provide conditions under which we can specify an optimal policy for the time-varying system. We define three distributed algorithms, and prove each computes an optimal routing policy for the time-invariant problem. With these distributed algorithms, the original goal of finding an optimal decentralized protocol is attained.