Topology control in wireless mesh networks with directional antennas

Abstract

With the development of wireless networks, many studies have been done to improve the network performance. Among those studies, wireless mesh networks have become a hot research interest in recent years. A wireless mesh network is an infrastructure wireless network composed by gateway nodes, non-gateway nodes and end-users. The back bone of the mesh networks is formed by gateway nodes and non-gateway nodes with wireless links. Gateway nodes connect to Internet by wired links. The end users directly connect with mesh back bone by wireless links, and access the Internet by mesh back bone. We found that only limited studies about topology control by using directional antennas have been done. One interesting study to optimize performance by using directional antennas was proposed by Kumar et al. In their work, a topology control algorithm was presented to create a tree with bounded degree, based on the approximation algorithm of minimal degree spanning tree. However, the throughput is not the direct objective in their algorithm, which means that their algorithm may not be optimal in throughput. Based on the work of Kumar et al, we formulate the throughput of each node as traffic delivery ratio. With each node equipped with m non-steerable directional antennas, two topology control algorithms for the wireless mesh networks are presented . Our objective is to maximize the minimal traffic delivery ratio from each node to the gateway nodes in both algorithms, by adjusting the orientations of the directional antennas appropriately. The MTDR (maximizing traffic delivery ratio) algorithm is based on an approximating degree bounded algorithm. In every step, the algorithm chooses a pair of links to be added and removed, so that the number of the maximal degree nodes is decreased by one. Then, the maximal degree of the topology will be decreased gradually until it is equal or smaller than the number of equipped directional antennas. We show by simulation that the MTDR algorithm improves the throughput significantly, compared with Kumar et al’s work. Moreover, we study how each parameter, such as the beam width of antennas, and the number of antennas on each node, has impact on the network performance. Many advantages of directional antennas are not utilized in the MTDR algorithm. We have improved our topology control method and proposed the EMTDR (extended maximizing traffic delivery ratio) algorithm for the single channel wireless mesh networks with m directional antennas equipped on each node. The objective of the EMTDR algorithm is the same as the MTDR algorithm. By allowing each antenna to connect to multiple nodes, the EMTDR algorithm improves performance by 40% ~ 280%, compared with the MTDR algorithm.

Date of Award	17 Feb 2010
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Xiaohua JIA (Supervisor)