Efficient multicast routing and backup algorithm in ad-hoc wireless networks
An ad hoc wireless network is a collection of mobile hosts that self-forming a temporary network without any required intervention of centralized system. In such environment, mobile hosts, which are not within transmission range from each other, require some other intermediate hosts to forward their packets to form a multi-hop communication. In this paper, an ad hoc network is modeled as a graph. Two nodes within the transmission range of each other are connected by an edge. Given a finite set of mobile nodes, a finite set of edges and a new multicast request, the wireless multicast tree problem (WMTP) is to find a multicast tree for the request so that the multicast loss probability is minimized. We prove the WMTP is NP-complete and a heuristic algorithm, called Degree-Based Multicast Routing Algorithm (DBMRA), is proposed. Based on the DBMRA, one algorithm was proposed to establish backup nodes for the multicast tree to improve the reliability. A node is needed to be backup only when it has a high probability to disconnect the multicast tree seriously. The qualification of a node to be backup is subject to a computed threshold which is determined by a statistic analysis. The theoretical and experimental analyses are presented to characterize the performance of our algorithms.
ad-hoc wireless networks multicast loss probability backup nodes mobile host (mh)