Topology control and channel assignment in wireless multi-hop networks

Abstract

Recent years have seen significant interest in using the wireless multihop networking paradigm to build mesh networks, ad hoc networks, and sensor networks. A key challenge in multihop wireless networks is to guarantee network capacity to meet user requirements. In this dissertation, we propose to improve the network performance through topology control in wireless mesh networks, as well as use additional frequency spectrum in wireless sensor networks. In the first part, we consider the problem of joint power control and routing to maximize the network throughput in wireless mesh networks. First, we present two mathematical formulations for the joint problem according to two diferent definitions of network throughput. To reduce the computation cost, we next decompose this joint problem into two subproblems: the power control sub-problem and the routing sub-problem. For the power control sub-problem, we design two heuristic algorithms to assign transmission powers to mesh routers, such that the total interference or the maximum node interference in the network is minimized. For the routing sub-problem, we design two linear programming formulations to maximize the total throughput or the minimal per-node throughput. However, the overheads of its multi-path routing may reduce the throughput significantly when it is implemented in real networks. Therefore, we next analyzed the topology control and capacity of mesh networks. Based on the analysis, we propose a Relative-Closest Connect-First single-path routing topology control algorithm. In our proposed method, a node that has a closest relative distance to a gateway has the high priority to be connected to the sub-tree rooted from the gateway. Our proposed topology control method combines the merits of the shortest path tree, the load balancing and the greedy methods. Besides the centralized method, we present its distributed version, to make it more practical for the implementation. In the second part, we present a novel approach to minimize the latency of data aggregation by using partially overlapped channels. We first propose a joint tree construction, channel assignment and scheduling algorithm for this problem. The basic idea is to select a parent and assign a feasible channel to each node such that it can be scheduled in a timeslot that has been used by other nodes, meanwhile leaving unconsidered nodes more chances to avoid conflicts. Next, we give a distributed implementation of this joint scheme. Simulation results demonstrate that our joint scheme can significantly reduce the data aggregation latency, especially in high-density sensor networks. To our best knowledge, this is the first work in the literature that minimizes the data aggregation latency by using partially overlapped channels.

Date of Award	2 Oct 2009
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Xiaohua JIA (Supervisor)