Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 1250-1259 |
| Number of pages | 10 |
| Journal | IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |
| Volume | E82-A |
| Issue number | 7 |
| State | Published - 07 1999 |
| Externally published | Yes |
Keywords
- Ad-hoc wireless networks
- Mobile host (mh)
- Multicast loss probability