Mobile Networks and Applications 4 (1999) 193–207 193Tree multicast strategies in mobile, multihop wireless networksMario Gerla, Ching-Chuan Chiang and Lixia ZhangComputer Science Department, University of California, Los Angeles, CA 90095, USATree multicast is a well established concept in wired networks. Two versions, per-source tree multicast (e.g., DVMRP) and sharedtree multicast (e.g., Core Based Tree), account for the majority of the wireline implementations. In this paper, we extend the treemulticast concept to wireless, mobile, multihop networks for applications ranging from ad hoc networking to disaster recovery andbattlefield. The main challenge in wireless, mobile networks is the rapidly changing environment. We address this issue in our designby: (a) using “soft state”; (b) assigning different roles to nodes depending on their mobility (2-level mobility model); (c) proposing anadaptive scheme which combines shared tree and per-source tree benefits, and (d) dynamically relocating the shared tree RendezvousPoint (RP). A detailed wireless simulation model is used to evaluate various multicast schemes. The results show that per-source treesperform better in heavy loads because of the more efficient traffic distribution; while shared trees are more robust to mobility and aremore scalable to large network sizes. The adaptive tree multicast scheme, a hybrid between shared tree and per-source tree, combinesthe advantages of both and performs consistently well across all load and mobility scenarios. The main contributions of this study are:the use of a 2-level mobility model to improve the stability of the shared tree, the development of a hybrid, adaptive per-source andshared tree scheme, and the dynamic relocation of the RP in the shared tree.1. Introduction and backgroundWireless networks provide mobile users with ubiquitousinternet access and communication capability regardless oflocation. Usually, wireless networks are “last hop” exten-sions of a wireline network, i.e., they support single hopcommunications within a “cell”. In this paper we addressa novel type of wireless network called “multihop” or “ad-hoc” network. As a difference from “single hop” (i.e., cel-lular) networks [16] which require fixed base stations inter-connected by a wired backbone, multihop networks haveno fixed based stations nor wired backbone [14]. The mainapplication for mobile wireless multihopping is rapid de-ployment and dynamic reconfiguration in scenarios wherethe wireline network is not available or not cost effective(e.g., battlefield communications, search and rescue ad hocnetworking, etc.) [18]. In such cases, multihop wireless net-works provide a feasible and cost effective mean for com-munications among many mobile terminals [6,17,26,28].Multihopping poses several new challenges in the designof wireless network protocols. In this paper, we focus onmulticasting.The multicast service is critical in ad hoc network sce-narios characterized by the close collaboration of teams(e.g., rescue patrol, batallion, scientists, etc.) because of theaudio/video conferencing requirements and the sharing oftext and images. Multicasting in a mobile, multihop wire-less network is much more complex than in wired networksbecause of node mobility, broadcast radio channel and hid-den terminal effects. There are many different ways toattack this problem. In this paper we approach the problemby transferring and adapting to the wireless environment themulticast solutions used in wireline networks such as the In-ternet. We modify and extend these solutions to account formobility, dynamically changing topology and radio channelcharacteristics. To set the stage, we review below two pop-ular wired network multicast schemes, namely, per-sourceshortest tree and shared tree. We identify their limitationswhen applied to a wireless, mobile environment, and pre-view possible solutions.The per-source tree scheme consists of broadcasting thepacket from the source to all destinations along the sourcetree using “reverse path forwarding”. An arbitrary networknode will accept the packet broadcast by S as long as thepacket is received along the shortest path. This provisionis required in order to avoid endless looping. Examples ofper-source tree are DVMRP [9] and PIM dense mode [12].Per-source tree multicasting has many attractive properties.To begin with, the shortest tree rooted at each source (sinktree) generally comes for free since it is embedded in therouting tables of the most common routing algorithms suchas Distance Vector and Link State. Furthermore, source treemulticast distributes the traffic evenly in the network (as-suming that sources and receivers are evenly distributed), itrequires minimal initialization and maintenance, and it doesnot rely on a central control point (e.g., Rendezvous Point).In mobile networks, however, the per-source tree approachpresents a problem. Suppose a source moves faster than therouting tables can track it. In this case, some of the nodeshave obsolete routing tables which point in the “wrong di-rection”. Following the “reverse path forwarding” princi-ple, multicast packets are dropped at such nodes and maynever reach some of the receivers.Another popular wired network scheme is shared-treemulticast. In this scheme, a single tree rooted at a Ren-dezvous Point (RP) is maintained (instead of many per-source trees). Examples of the shared-tree approach areCBT [2,3] and PIM sparse mode [11]. The shared tree isless sensitive to source mobility and can in part overcomethe above mentioned fast moving source problem. Namely, Baltzer Science Publishers BV194 M. Gerla et al. / Tree multicast strategies in mobile, multihop wireless networksa very fast source will send its packet to the RP in unicastmode. Packets are correctly delivered to the RP on shortestpaths, irrespective of the speed of the source. The RP willthen multicast the packet on the shared tree to the intendeddestinations. This works as long as the shared tree is sta-ble. If ALL the nodes are moving fast (relative to routingtable updates), the shared tree solution also fails. In manypractical applications, however, it turns out that only a frac-tion of the nodes is fast moving, while the remaining nodesare static or relatively slow moving. This 2-level mobilitymodel, further elaborated in section 7, allows us to definea stable routing scheme and therefore a shared tree whichis robust to