TY - JOUR

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

AU - Sheij, Shiann Tsong

AU - Fangtsou, Chao Tsong

AU - Hsu, Wu Hsiao

AU - Hsiao, Ming Ching

PY - 1999/7

Y1 - 1999/7

N2 - 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.

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.

KW - Ad-hoc wireless networks

KW - Mobile host (mh)

KW - Multicast loss probability

UR - http://www.scopus.com/inward/record.url?scp=0032596502&partnerID=8YFLogxK

M3 - 文章

AN - SCOPUS:0032596502

SN - 0916-8508

VL - E82-A

SP - 1250

EP - 1259

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 7

ER -