Minimum delay broadcast scheduling for wireless mesh networks with power control and directional antennas

Abstract

Wireless mesh network is a promising key technology for next generation wireless communications and has recently attracted much attention from both the academic and industrial communities. It can integrate multiple access techniques such as Ad hoc networks, WLANs and so on. Compared with existing wireless networking techniques, wireless mesh network enables larger communication range, higher network throughput and lower cost. With the development of broadband multimedia, the applications, such as web conferences, video-on-demand and online games, are widely used in our daily life and impose a high requirement for network bandwidth, the quality of services and the communication efficiency. Such applications are usually based on the traditional broadcast operation which leads to speed bottleneck and affects the system throughput. Thus, how to improve the performance of these applications in wireless mesh networks is an important issue. Power control is an efficient way to improve the network throughput. To assign a proper power to each relay node can solve the problems such as network connectivity and interference management. Meanwhile, power control can be jointly considered with transmission scheduling and routing to improve the system performance. Directional antennas have been used to increase transmission data rate and reduce interference in recent years. Directional antennas can make the energy concentrated on the specific directions to increase the received signal strength at the receivers and reduce the interference on other directions. Our thesis aim to minimize the total transmis sion delay for the gateway (i.e., the source node) to broadcast a packet to all the mesh routers in the network with power control and directional antennas. The task is to handle the issues of broadcast routing, transmission scheduling and power control. The major work and contributions are described as follows. (1) Discuss the issue of joint power control and scheduling for minimizing broadcast delay in wireless mesh networks. The problem of our concern is: given a gateway node as the source node and a set of mesh routers, assuming that the routing tree rooted from the source node is fixed, our goal is to compute an optimal power assignment with transmission schedule such that the total delay for the gateway node to broadcast a packet to all mesh routers in the network is minimized. We first formulate the problem as a non-convex quadratically constrained programme and show its NP-hardness. Then we propose a balanced method for power control and transmission scheduling. We introduce a new metric called standard deviation of average remaining broadcast time of nodes to determine the priority of the two parameters. When this standard deviation is above a threshold, the transmitting nodes will take the data-rate-first approach to increase the data rate; otherwise, the concurrency-first approach will be used to increase the number of concurrent transmissions in the system. Theoretical analysis is given to show the upper and lower bound of standard deviation of average remaining broadcast time of nodes. Extensive simulations have demonstrated that our proposed method can reduce the broadcast delay significantly as compared with fixed transmission power method and existing power control methods. In addition, the results also show that our balanced method performs better than both pure data-rate-first method and concurrency-first method. (2) Study the issue of joint routing and scheduling for maximizing throughput for video streaming in wireless mesh networks. The problem of our concern is as follows. We are given a gateway node and a set of mesh routers, our task is to build a broadcast routing tree rooted from the gateway node and compute an optimal transmission schedule such that the network throughput for the gateway node to broadcast steaming data to all the mesh routers is maximized. We divide the whole time period into several time frames and convert the problem of maximizing the total throughput into minimizing the length of the time frame. The problem is formulated as a mixed integer programming and is NP-hard. We propose a three-step method. First, we build a broadcast tree to minimize the total interference of network. Then we use the local-search method to adjust the structure of the broadcast tree obtained above to minimize the sum of transmission time of the non-leaf nodes. Three constraints must be satisfied during the tree adjustment: 1) the total interference will not increase; 2) The network is connected; 3) The sum of the transmission time is strictly decreased. Last, we propose a heuristic method to do transmission scheduling. Simulation results show the performance of our method. (3) Discuss the issue of minimizing broadcast delay by using directional antennas in WLANs. The problem of our concern is as follows. There is an AP equipped with directional antennas and a set of clients that are served by the AP. Given the transmit power of AP and the fixed beamwidth of directional antennas, our task is to find the beam orientations of directional antennas and compute an optimal transmission schedule such that the total transmission delay for all clients to receive the broadcast data is minimized. The data broadcasting problem we investigate is NP-hard. We propose a two-phase method to solve the problem. In the first phase, we use singlelobe beam pattern to cover all clients by adjusting the beam orientations, such that the total transmission delay is minimized. In the second phase, based on the results obtained from the first phase, we group these single-lobes into a set of multi-lobes to minimize the total transmission delay. The solution for each subproblem is optimal. Extensive simulations are conducted to evaluate our proposed method. (4) Discuss the issue of routing and transmission scheduling by using directional antennas to minimize broadcast delay in wireless mesh networks. Our objective is to minimize the total transmission delay for all the other nodes to receive a broadcast packet from the source, by determining the set of relay nodes and computing the number and orientations of beams formed by each relay node. We propose a heuristic solution with two steps. Firstly we construct a broadcast routing tree by defining a new routing metric to select the relay nodes and compute the optimal antenna beams for each relay node. Then we use a greedy method to make scheduling of concurrent transmissions without causing beam interference. Extensive simulations have demonstrated that our proposed method can reduce the broadcast delay significantly compared with the methods using omnidirectional antennas and single-rate transmission.

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