Multi-hop wireless networks have been widely deployed in different application areas. These include wireless sensor networks, wireless mesh networks, and wireless vehicular ad-hoc networks. Resource allocation and routing are two critical issues for multi-hop wireless networks. The appropriate allocation of the limited resources, such as energy or channel, can usually improve the network performance dramatically. On the other hand, routing is usually coupled with resource allocation, which affects the network topology. The problem itself can even be regarded as a high level resource allocation, because it is equivalent to allocating the set of wireless links and bandwidth for each particular application. Due to the difference in hardware characteristics and application background, different networks should be given special design considerations. In this dissertation, we discuss several research topics related with resource allocation and routing in multi-hop wireless networks.
First, we investigate the problem of sleep scheduling of sensors in dense wireless sensor networks with the goal of reducing energy consumption. The basic idea is to partition sensors into groups such that a connected backbone network can be maintained by keeping only one arbitrary node from each group in active status. Unlike previous approaches that use geographic partitions, we propose to partition nodes based on their measured connectivity. The proposed scheme not only ensures K-vertex connectivity of the backbone network, but also outperforms other approaches in irregular radio environments.
Second, we study the channel assignment with partially overlapping channels in wireless mesh networks. Unlike previous studies that focus on the channel assignment with non-overlapping channels only, we propose efficient channel assignment algorithms that use both non-overlapping and overlapping channels. We show that the network capacity can be dramatically increased by using partially overlapping channels, and the proposed algorithms find better solutions than existing algorithms.
Third, as both static channel assignment and dynamic channel assignment have their own strengths and drawbacks, we propose a hybrid wireless mesh networking architecture, which combines the advantages of both channel assignment approaches. We discuss both the channel assignment algorithms and routing protocols used in this hybrid architecture. We demonstrate that our proposed approach achieves better adaptivity to the changing traffic and lower data delivery delay.
Fourth, we study the application of multi-source video on-demand streaming in wireless mesh networks. We focus on the problem of finding the maximum number of high-quality and independent paths from the user to the multiple video sources by considering the effect of wireless interference. We propose efficient routing algorithms that aim at minimizing the network congestion caused by each new video session. We show that it not only improves the average video streaming performance, but also increase the network's capacity of satisfying video requests.
Finally, we present a routing algorithm for vehicular ad-hoc networks with the goal of efficient data delivery under low and median vehicle densities. We consider the deployment of static nodes at road intersections to help relay data. We propose an algorithm that determines whether a vehicle forwards a packet to the static node and when the static node forwards the packet to vehicles. We show that our proposed routing algorithm achieves lower data delivery delay than the previous algorithms.