Algorithms for routing and channel assignment in wireless infrastructure networks

Wireless communication is a rapidly growing segment of the communication industry, with the potential to provide low-cost, high-quality, and high-speed information exchange between portable devices. To harvest the available bandwidth efficiently in a wireless network, they employ multiple orthogonal channels over multiple radios at the nodes. In addition, nodes in these networks employ directional antennas as radios to improve spatial throughput. This dissertation develops algorithms for routing and broadcasting with channel assignment in such networks. First, we compute the minimum cost path between a given source-destination pair with channel assignment on each link in the path such that no two transmissions interfere with each other. Such a path must satisfy the constraint that no two consecutive links on the path are assigned the same channel, referred to as "channel discontinuity constraint." To compute such a path, we develop two graph expansion techniques based on minimum cost perfect matching and dijkstra's algorithm. Through extensive simulations, we study the effectiveness of the routing algorithms developed based on the two expansion techniques and the benefits of employing the minimum cost perfect matching based solution. Secondly, we study the benefits of sharing channel bandwidth across multiple flows. We model the routing and channel assignment problem in two different ways to account for the presence and absence of inter-flow bandwidth sharing. Benefits of multiple paths between a source-destination pair motivates the problem of computing multiple paths between a source-destination pair with channel assignment such that all the paths can be active simultaneously to achieve maximal flow between the pair in the considered network. Since finding even two such paths is NP-hard, we formulate the problem as an integer linear program and develop efficient heuristic to find these paths iteratively. Thirdly, we compute a broadcast tree from a given root with channel assignment such that all the links in the broadcast tree can be active simultaneously without interfering with each other. Since finding such a tree is an NP-hard problem, we formulate the problem as an integer linear program (ILP) and develop heuristics to find the broadcast tree with channel assignment. We evaluate and compare the performance of the developed heuristics with respect to their success rate, average depth of the obtained tree, and average path length from root to a node in the network. This dissertation also analyzes the blocking performance of a channel assignment scheme in a multi-channel wireless line network. We assume that the existing calls in the network may be rearranged on different channels to accommodate an incoming call. The analysis is limited to single-hop calls with different transmission ranges.;Finally, this dissertation evaluates the performance of disjoint multipath routing approaches for all-to-all routing in packet-switched networks with respect to packet overhead, path lengths, and routing table size. We develop a novel approach based on cycle-embedding to obtain two node-disjoint paths between all source-destination pairs with reduced number of routing table entries maintained at a node (hence the reduced look up time), small average path lengths, and less packet overhead. We study the trade-off between the number of routing table entries maintained at a node and the average length of the two disjoint paths by: (a) formulating the cycle-embedding problem as an integer linear program; and (b) developing a heuristic. We show that the number of routing table entries at a node may be reduced to at most two per destination using cycle-embedding approach, if the length of the disjoint paths are allowed to exceed the minimum by 25%.