Group communication has become increasingly important in MANET, because a group of mobile users often need to collaborate with one another. Current multicast routing protocols in MANET have been shown to incur large signaling overhead due to frequent topology changes. This problem is worse when there are a large number of multicast lgroups in the network. To overcome this problem, there is a recent shift towards stateless multicast for a small group of users in MANET.
In this project, we introduce a new small group multicasting scheme based on packet encapsulation in MANET. Our scheme builds an overlaying multicast packet distribution tree on top of the underlying unicast network routing protocol (Figure 4). Multicast data is encapsulated in a unicast envelop and transmitted between the group nodes. A list of destination addresses is explicitly included in each packet. Based on the list of destinations, a node constructs a packet distribution tree using our tree construction algorithms, with the goal of minimizing the overall bandwidth cost of the tree. This overlay packet distribution tree provides us with a flexible structure to perform transport and application level packet processing and routing, yet retains low bandwidth costs similar to those of a router-assisted multicasting scheme.
We introduce two novel tree construction algorithms based on the geometric locations of the nodes. We first argue and prove by simulation that on average, longer geometric distance translates into more network level hops along the shortest path. Thus, we replace the requirement to construct the least-cost tree in the number of hops into a tree with the shortest overall distance. We propose two algorithms to construct a packet distribution tree: 1) a location-guided k-ary (LGK) tree based on geometric proximity of the subtrees; 2) a location-guided Steiner (LGK) tree based on a modified version of the well-known Takahashi-Matsuyama heuristic.
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, the bandwidth cost difference between LGS and LGK becomes insignificant, and LGK outperforms LGS due to its lower computational complexity.
New: We recently propose a new algorithm called Location Guided Directional (LGD) tree to the family of location-guided trees. The LGD algorithm gives a nice trade-off between the LGS and LGK trees in terms of performance and complexity. See the submitted journal paper below for details.
Publications
- Kai Chen, Klara Nahrstedt, Effective Location-Guided Tree Construction Algorithms for Small Group Multicast in MANET, in Proc. of IEEE INFOCOM 2002, New York, NY, June, 2002. pp. 1180-1189.
- Kai Chen, Klara Nahrstedt, Effective Location-Guided Overlay Multicast in Mobile Ad Hoc Networks, submitted to the International Journal of Wireless and Mobile Computing (IJWMC), Special Issue on Group Communications in Ad Hoc Networks, Inderscience Publishers.