Download files
Abstract
The wireless mesh network (WMN) is a promising technology for deploying wireless infrastructure to provide users with always-on-line service anywhere anytime. In the future, high-speed wireless meshes will enable a whole new range of exciting multicast applications, such as IP-TV and video on demand. When implementing multicasting in a WMN, reliability becomes one of the major issues because: (1) the failure of nodes or wireless links may disrupt the multicast transmission, and (2) the lossy nature of radio communication causes random packet loss in wireless links. In this thesis, our main objective is to develop effective and efficient algorithms for reliable multicast in WMNs with a minimal consumption of network resources. More specifically, we focus on protecting multicast sessions from the above two categories of faults, node or link failure and opportunistic packet loss.
The first contribution of this thesis is the design of a resilient forwarding mesh (RFM) to protect a multicast session from a link or node failure. An RFM effectively establishes two node-disjoint paths for each source-destination pair. An optimal resilient forwarding mesh (ORFM) is the RFM with the minimum number of transmissions, by utilising wireless broadcast advantage. We provide integer linear programming (ILP) formulations and several heuristic algorithms to find approximate solutions to the ORFM problem. Our simulation results show that a resilient forwarding mesh can provide "1+1" protection to the multicast session with limited additional overhead compared with a single multicast tree.
The second contribution of this thesis is the comprehensive solution on reliable multicast in single rate WMNs against opportunistic packet loss. We first design a novel multicast routing metric called the expected multicast transmission (EMT). EMT captures the effects of opportunistic link packet delivery ratio, MAC layer retransmission and wireless broadcast advantage at the same time. The EMT of a MAC layer multicast transmission is defined as the expected number of data transmissions (including retransmissions) required for a packet to reach all the recipients. The objective of multicast routing is to build a multicast tree with the minimum total EMT for all transmitters (including the source node and all forwarders). We prove that this minimum EMT tree problem is NP-complete and provide ILP formulations, as well as a Lagrangian relaxation solution to reduce the computation time. In order to solve the problem in polynomial time, we design one centralised algorithm with the performance bound analysis and a distributed multicast protocol, probabilistically reliable on-demand multicast (PROD). The simulation results show that the minimum EMT multicast tree (MMT) formed by PROD outperforms shortest path tree and minimum forwarder tree in terms of packet delivery ratio and transmission overhead.
The third contribution of this thesis is the low latency reliable multicast routing by utilising the rate diversity feature in wireless transmission. We design an expected minimum multicast delay (EMMD) rate allocation scheme for link layer single hop multicast transmission, which minimises the expected transmission delay when all recipients have received the packet successfully. We propose a Markov chain method to calculate the expected multicast delay based on EMMD, called minimum transmission delay (MTD), which is used as the metric for multicast routing. We give ILP formulations to obtain the optimal multicast tree that is the one with the minimum total EMMD for all transmitters. Given the NP-completeness of the minimum EMMD tree problem, we design a greedy centralised algorithm and extend it to a distributed version, called multi-rate reliable multicast (MRRM) routing protocol. Both of the algorithms achieve low time-complexity but also effectively reduce the end-to-end multicast latency.