Efficient Multicast Routing and Backup Algorithm in Ad-Hoc Wireless Networks

Shiann-Tsong SHEU; Chao-Tsong FANGTSOU; Wu-Hsiao HSU; Ming-Ching HSIAO

Efficient Multicast Routing and Backup Algorithm in Ad-Hoc Wireless Networks

Shiann-Tsong SHEU, Chao-Tsong FANGTSOU, Wu-Hsiao HSU, Ming-Ching HSIAO

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.7 pp.1250-1260

Publication Date: 1999/07/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Multi-dimensional Mobile Information Networks)

Category

Cite this

Copy

Shiann-Tsong SHEU, Chao-Tsong FANGTSOU, Wu-Hsiao HSU, Ming-Ching HSIAO, "Efficient Multicast Routing and Backup Algorithm in Ad-Hoc Wireless Networks" in IEICE TRANSACTIONS on Fundamentals, vol. E82-A, no. 7, pp. 1250-1260, July 1999, doi: .
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_7_1250/_p

Copy

@ARTICLE{e82-a_7_1250,
author={Shiann-Tsong SHEU, Chao-Tsong FANGTSOU, Wu-Hsiao HSU, Ming-Ching HSIAO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Multicast Routing and Backup Algorithm in Ad-Hoc Wireless Networks},
year={1999},
volume={E82-A},
number={7},
pages={1250-1260},
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.},
keywords={},
doi={},
ISSN={},
month={July},}

Copy

TY - JOUR
TI - Efficient Multicast Routing and Backup Algorithm in Ad-Hoc Wireless Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1250
EP - 1260
AU - Shiann-Tsong SHEU
AU - Chao-Tsong FANGTSOU
AU - Wu-Hsiao HSU
AU - Ming-Ching HSIAO
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 1999
AB - 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.
ER -