Effective location-guided tree construction algorithms for small group multicast in MANET

Kai Chen, Klara Nahrstedt

Research output: Contribution to journalConference articlepeer-review


Group communication has become increasingly important in mobile ad hoc networks (MANET). Current multicast routing protocols in MANET have been shown to have large overhead due to dynamic network topology. To overcome this problem, there is a recent shift towards stateless multicast in small groups (DDM [1]). DDM queries the underlying unicast routing protocol to forward data packets towards members of a multicast group. The multicast distribution tree in DDM is implicit and cannot be controlled by the upper transport and application layers. In this paper, we introduce another small group multicast scheme, based on packet encapsulation, which uses novel packet distribution tree construction algorithms for efficient data delivery. The packet distribution tree is constructed explicitly with the goal of minimizing the overall bandwidth cost of the tree. The tree construction algorithms include a location-guided k-ary (LGK) tree and a location-guided Steiner (LGS) tree. Both of them utilize the geometric locations of the destination nodes as heuristics to compute the trees, and are accompanied by a hybrid location update mechanism to disseminate location information among a group of nodes. Our simulation results show that LGS tree has lower bandwidth cost than LGK tree when the location information of the nodes is up-to-date, and its cost is similar to that of an optimal Steiner multicast tree. When location information of the nodes is out-dated, LGK tree outperforms LGS tree due to its lower computational complexity.

Original languageEnglish (US)
Pages (from-to)1180-1189
Number of pages10
JournalProceedings - IEEE INFOCOM
StatePublished - 2002
EventIEEE Infocom 2002 - New York, NY, United States
Duration: Jun 23 2002Jun 27 2002

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Effective location-guided tree construction algorithms for small group multicast in MANET'. Together they form a unique fingerprint.

Cite this