Efficient multicast routing and backup algorithm in Ad-hoc wireless networks

Shiann Tsong Sheij*, Chao Tsong Fangtsou, Wu Hsiao Hsu, Ming Ching Hsiao

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

1 Scopus citations


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 languageEnglish
Pages (from-to)1250-1259
Number of pages10
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number7
StatePublished - 07 1999
Externally publishedYes


  • Ad-hoc wireless networks
  • Mobile host (mh)
  • Multicast loss probability


Dive into the research topics of 'Efficient multicast routing and backup algorithm in Ad-hoc wireless networks'. Together they form a unique fingerprint.

Cite this