ad hoc multicast routing with mobility prediction.
An ad hoc wireless network is an infrastructureless network composed of mobile hosts. The primary concerns in ad hoc networks are bandwidth limitations and unpredictable topology changes. Thus, efficient utilization of routing packets and immediate recovery of route breaks are critical in routing and multicasting protocols. A multicast scheme, On-Demand Multicast Routing Protocol (ODMRP), has been recently proposed for mobile ad hoc networks. ODMRP is a reactive (on-demand) protocol that delivers packets to destination(s) on a mesh topology using scoped flooding of data. We can apply a number of enhancements to improve the performance of ODMRP. In this paper, we propose a mobility prediction scheme to help select stable routes and to perform rerouting in anticipation of topology changes. We also introduce techniques to improve transmission reliability and eliminate route acquisition latency. The impact of our improvements is evaluated via simulation.
Introduction
An ad hoc network is a dynamically reconfigurable
wireless network with no fixed infrastructures. Each
host acts as a router and moves in an arbitrary man-
ner. Ad hoc networks are deployed in applications such
as disaster recovery and distributed collaborative com-
puting, where routes are mostly multihop and network
hosts communicate via packet radios. In a typical ad
hoc environment, network hosts work in groups to carry
out the given task. Hence, multicast plays an important
role in ad hoc networks. Multicast routing protocols
used in static networks such as Distance Vector Multicast
Routing Protocol (DVMRP) [7], Multicast Open
Shortest Path First (MOSPF) [19], Core Based Trees
(CBT) [3], and Protocol Independent Multicast (PIM)
[8], however, do not perform well in ad hoc networks.
Multicast tree structures are fragile and must be readjusted
continuously as connectivity changes. Further-
more, multicast trees usually require a global routing
substructure such as link state or distance vector. The
frequent exchange of routing vectors or link state tables,
triggered by continuous topology changes, yields exces-
This work was funded in part by the Defense Advanced Re-search
Projects Agency (DARPA) under contract DAAB07-97-
C-D321, as a part of the Global Mobile Information Systems
(GloMo) program.
Now with eWings Technologies, Plano, TX.
sive channel and processing overhead. Limited band-
width, constrained power, and mobility of network hosts
make the multicast protocol design particularly challenging

To overcome these limitations, several multicast protocols
have been proposed [4,9,16,13,22,23,27]. In
this study, we will use On-Demand Multicast Routing
Protocol (ODMRP) [16,17] as the starting scheme.
ODMRP applies on-demand routing techniques to
avoid channel overhead and improve scalability. It uses
the concept of forwarding group [5], a set of nodes which
is responsible for forwarding multicast data on shortest
paths between any member pairs, to build a forwarding
mesh for each multicast group. By maintaining and
using a mesh, ODMRP avoids drawbacks of multicast
trees in mobile wireless networks (for example, intermittent
connectivity, traffic concentration, frequent tree
reconfiguration, non-shortest path in a shared tree).
ODMRP takes a soft-state approach to maintain multi-cast
members. No explicit control message transmission
is required to leave the group.
The major strengths of ODMRP are its simplicity
and scalability. We can further improve its performance
by several enhancements. In this paper, we propose new
techniques to enhance the effectiveness and efficiency of
ODMRP. Our primary goals are the following:
R
R
R
R
R
Join Request
Join

Table

Figure

1. On-demand procedure for membership setup and maintenance

Improve adaptivity to node movement patterns
ffl Transmit control packets only when necessary
ffl Reconstruct routes in anticipation of topology changes
ffl Improve hop-by-hop transmission reliability
ffl Eliminate route acquisition latency
ffl Select stable routes
The remainder of the paper is organized as fol-
lows. Section 2 overviews the basic mechanism of
ODMRP. Section 3 describes new enhancements applied
to ODMRP. Section 4 follows with the simulation
results and concluding remarks are made in Section 5.
2. ODMRP

Overview

ODMRP establishes and maintains group membership
and multicast routes by the source on demand.
Similar to on-demand unicast routing protocols, a query
phase and a reply phase comprise the protocol (see Figure
1). While a multicast source has packets to send, it
periodically broadcasts to the entire network a member
advertising packet, called Join Request. This periodic
transmission refreshes the membership information
and updates the routes as follows. When a node receives
a non-duplicate Join Request, it stores the upstream
node address in its route table (i.e., backward learning)
and rebroadcasts the packet. When the Join Request
packet reaches a multicast receiver, the receiver creates
or updates the source entry in its Member Table. While
valid entries exist in the Member Table, Join Tables
are broadcasted periodically to the neighbors. When a
node receives a Join Table, it checks if the next node
Forwarding Group
Multicast Member Nodes
Forwarding Group Nodes

Figure

2. The forwarding group concept.
address of one of the entries matches its own address.
If matched, the node realizes that it is on the path to
the source and thus is a part of the forwarding group.
It then sets the FG FLAG and broadcasts its own Join
Table built upon matched entries. Each forwarding
group member hence propagates the Join Table until
the packet reaches the multicast source via the shortest
path. This process constructs (or updates) the routes
from sources to receivers and builds a mesh of nodes,
the forwarding group.
We visualize the forwarding group concept in Figure
2. The forwarding group is a set of nodes which
is in charge of forwarding multicast packets. It supports
shortest paths between any member pairs. All
nodes inside the "bubble" (multicast members and forwarding
group nodes) forward multicast data packets.
Note that a multicast receiver also can be a forwarding
group node if it is on the path between a multicast
source and another receiver. The mesh provides richer
connectivity among multicast members compared with
trees. Flooding redundancy among forwarding group
helps overcome node displacements and channel fading.
Hence, unlike trees, meshes do not require frequent reconfigurations

An example in Figure 3 illustrates the robustness of
a mesh configuration. Three sources (S 1
send multicast data packets to three receivers (R 1 , R 2 ,
and R 3
forwarding group nodes (A, B, and
C). Suppose the route from S 1 to R 2 is (S 1 -A-B-R 2 ).
In a tree configuration, if the link between nodes A and
breaks or fails, R 2
cannot receive any packets from
until the tree is reconfigured. ODMRP, on the other
hand, already has a redundant route (S 1
) to
R
R
R
A
Links
Multicast Routes
Sources:
Receivers: R R , R
Forwarding Nodes: A, B, C

Figure

3. Why a mesh?
deliver packets without going through the disconnected
link between nodes A and B.
Let us consider Figure 4 as an example of a Join
Table forwarding process. Nodes S 1 and S 2 are multicast
sources, and nodes R 1 , R 2 , and R 3 are multicast
receivers. Nodes R 2
and R 3
send their Join Tables to
both S 1 and S 2 via I 2 . R 1 sends its packet to S 1 via I 1
and to S 2 via I 2 . When receivers send their Join Tables
to next hop nodes, an intermediate node I 1 sets
the FG FLAG and builds its own Join Table since there
is a next node address entry in the Join Table received
from R 1 that matches its own address. Note that the
Join Table built by I 1 has an entry for sender S 1 but
not for S 2 because the next node for S 2 in the received
Join Table is not I 1 . In the meantime, node I 2 sets
the FG FLAG, constructs its own Join Table and sends
the packet to its neighbors. Even though I 2 receives
three Join Tables from the receivers, it broadcasts the
Join Table only once because the second and third table
arrivals carry no new source information. Channel
overhead is thus reduced dramatically in cases where
numerous multicast receivers share the same links to
the source.
After this group establishment and route construction
process, a multicast source can transmit packets to
receivers via selected routes and forwarding groups. Periodic
control packets are sent only when outgoing data
packets are still present. When receiving a multicast
data packet, a node forwards the packet only if it is not
a duplicate and the setting of the FG FLAG for the multicast
group has not expired. This procedure minimizes
traffic overhead and prevents sending packets through
stale routes.
In ODMRP, nodes do not need to send explicit con-
SIIRRR1212123Sender Next Node
Join Table of Node R
I
I
Join Table of Node I111

Figure

4. An example of a Join Table forwarding.
trol packets to leave the group. If a multicast source
wants to leave the group, it simply stops sending Join
Request packets since it does not have any multicast
data to send to the group. If a receiver no longer wants
to receive from a particular multicast group, it removes
the corresponding entries from its Member Table and
does not send the Join Table for that group. Nodes
in the forwarding group are demoted to non-forwarding
nodes if not refreshed (no Join Tables received) before
they timeout.
Unicast routing capability is one of the major
strengths of ODMRP. Not only can ODMRP coexist
with any unicast routing protocol, it can function as
both multicast and unicast. Thus, ODMRP can run
without any underlying unicast protocol. Other ad hoc
multicast protocols such as Adhoc Multicast Routing
Protocol (AMRoute) [4], Core Assisted Mesh Protocol
(CAMP) [9], Reservation-Based Multicast (RBM) [6],
and Lightweight Adaptive Multicast (LAM) [13] must
be run on top of a unicast routing protocol. CAMP,
RBM, and LAM in particular, only work with certain
underlying unicast protocols.
3. Enhancements
3.1. Adapting the Refresh Interval via Mobility
Prediction
ODMRP requires periodic flooding of Join Requests
to build and refresh routes. Excessive flooding,
however, is not desirable in ad hoc networks because
of bandwidth constraints. Furthermore, flooding often
causes congestion, contention, and collisions. Finding
the optimal refresh interval is critical in ODMRP per-
formance. Here we propose a scheme that adapts the
route refresh interval to mobility patterns and speeds
[24]. By utilizing the location and mobility information
provided by GPS (Global Positioning System) [15], we
predict the duration of time routes will remain valid. 1
With the predicted time of route disconnection, Join
Requests are only flooded when route breaks of ongoing
data sessions are imminent.
In our prediction method, we assume a free space
propagation model [21], where the received signal
strength solely depends on its distance to the trans-
mitter. We also assume that all nodes in the network
have their clocks synchronized (for example, by using
the NTP (Network Time Protocol) [18] or the GPS
clock itself). 2 Therefore, if we know the motion parameters
of two neighbors (such as speed, direction, radio
propagation range), we can determine the duration of
time these two nodes will remain connected. Assume
two nodes i and j are within the transmission range r
of each other. Let
) be the coordinate of mobile
host i and be that of mobile host j. Also let v i
be the speeds, and ' i
(0
be the moving directions of nodes i and j, respectively.
Then, the amount of time that they will stay connected,
, is predicted by:
where
sin
sin
, and
Note that when v is set to 1
without applying the above equation.
To utilize the information obtained from the predic-
tion, Join Request and Join Table packets must add
extra fields. When a source sends Join Requests, it
appends its location, speed, and direction. It sets the
MIN LET (Minimum Link Expiration Time) field to
the MAX LET VALUE since the source does not have any
previous hop node. The next hop neighbor, upon receiving
a Join Request, predicts the link expiration
1 We can obtain mobility speed and heading information from
GPS or the node's own instruments and sensors (for example,
campus, odometer, speed sensors).
Time synchronization of the nodes is done only at the boot time.
Once nodes have powered up and their clocks are synchronized,
it is not required to perform periodic updates (although we can
still perform periodic updates in large intervals).
time between itself and the previous hop using the equation
(3.1). The minimum between this value and the
MIN LET indicated by the Join Request is included
in the packet. The rationale is that as soon as a single
link on a path is disconnected, the entire path is
invalidated. The node also overwrites the location and
mobility information field written by the previous node
with its own information. When a multicast member
receives the Join Request, it calculates the predicted
LET of the last link of the path. The minimum between
the last link expiration time and the MIN LET value
specified in the Join Request is the RET (Route Expiration
Time). This RET value is enclosed in the Join
Table and broadcasted. If a forwarding group node receives
multiple Join Tables with different RET values
(i.e., lies in paths from the same source to multiple re-
ceivers), it selects the minimum RET among them and
sends its own Join Table with the chosen RET value
attached. When the source receives Join Tables, it
selects the minimum RET among all the received Join

Tables

. Then the source builds new routes by flooding
a Join Request before the minimum RET approaches
(i.e., route breaks). Note that multicast receivers need
not periodically transmit Join Tables. Since sources
flood Join Requests only when needed, receivers only
send Join Tables after receiving Join Requests.
In addition to the estimated RET value, we need
to consider other factors when choosing the route refresh
interval. If the node mobility rate is high and the
topology changes frequently, routes will expire quickly
and often. The source may propagate Join Requests
excessively and this excessive flooding can cause collisions
and congestion, and clogs the network with control
packets. Thus, the MIN REFRESH INTERVAL should
be enforced to avoid control message overflow. On the
other hand, if nodes are stationary or move slowly and
link connectivity remains unchanged for a long duration
of time, routes will hardly expire and the source
will rarely send Join Requests. A few problems arise
in this situation. First, if a node in the route suddenly
changes its movement direction or speed, the
predicted RET value becomes obsolete and we cannot
reconstruct routes in time. Second, when a non-member
node located remotely from multicast members
wants to join the group, it cannot inform the new
membership or receive data until it receives a Join Re-
quest. Hence, the MAX REFRESH INTERVAL should be
set. The selection of the MIN REFRESH INTERVAL and
the MAX REFRESH INTERVAL should be adaptive to net-work
situations (among others, traffic type, traffic load,
mobility pattern, mobility speed, channel capacity).
3.1.1. Alternative Method of Prediction
Since GPS may not work properly in certain situations
(for instance, indoor, fading), we are not always
able to accurately predict the link expiration time for
a particular link. Nevertheless, there is an alternative
method to predict the LET. This method is based on a
more realistic propagation model and is proposed in [1]
and [20]. Basically, a node periodically measures transmission
power samples from packets received from its
neighbor. From this information, the node computes
the change rate for a particular neighbor's transmission
power level. Therefore, it can predict the time when the
transmission power level will drop below the acceptable
value (hysteresis region).
3.2. Route Selection Criteria
In the basic ODMRP, a multicast receiver selects
routes based on the minimum delay (i.e., the route
taken by the first received Join Request). We can
apply a different route selection method when using
the mobility prediction. The idea is inspired by the
Associativity-Based Routing (ABR) protocol [25] which
chooses associatively stable routes. In our new algo-
rithm, instead of using the minimum delay path, we
choose a route that is the most stable (the one with the
largest RET). To select a route, a multicast receiver
must wait for an appropriate amount of time after receiving
the first Join Request so that it will know
all possible routes and their RETs. The receiver then
chooses the most stable route and broadcasts a Join

Table

. Route breaks will occur less often and the number
of Join Request propagation will reduce because
we use stable routes. An example that shows the difference
between two route selection algorithms is presented
in Figure 5. Two routes are available from the
source S to the receiver R. Route 1 has a path of (S-
A-B-R) and route 2 has a path of (S-A-C-R). If we
use the minimum delay as the route selection metric,
the receiver node R selects route 1. Route 1 has a delay
of seven (3 route 2 has a delay
of nine (3 9). Since the Join Request that
takes route 1 reaches the receiver first, node R chooses
R
(3,
(1,
(4,
(3,
(i,
link expiration time j
Path S-A-B-R S-A-C-R
Delay 7
Route 1 Route 2
Figure

5. Route selection example.
route 1. If we select the stable route instead, the receiver
chooses route 2. The route expiration time of
route 1 is two (min(5; 2; and that of route 2 is
four (min(5; 5; 4). The receiver selects the route
with the maximum RET, and hence selects route 2. We
evaluate different route selection methods by simulation
in Section 4.
3.3. Reliability
The reliable transmission of Join Tables plays an
important role in establishing and refreshing multicast
routes and forwarding groups. If Join Tables are
not properly delivered, ODMRP cannot achieve effective
multicast routing. The IEEE 802.11 MAC protocol
[11], which is the emerging standard in wireless
networks, performs reliable transmission by retransmitting
the packet if no acknowledgment is received. If the
packet is broadcasted, however, no acknowledgments or
retransmissions are sent. In ODMRP, the transmission
of Join Tables are broadcasted when there are multiple
entries. Thus, ODMRP must perform the hop-by-
hop Join Table delivery verification and retransmission

We adopt a scheme that was used in [14]. Figure 6
illustrates the mechanism. When node B transmits a
packet to node C after receiving a packet from node A,
node A can hear the transmission of node B if it is still
within B's radio propagation range. The packet transmission
by node B to node C is hence used as a passive
acknowledgment to node A. We can utilize this passive
acknowledgment to verify the delivery of a Join

Table

. Multicast sources must send active acknowledgments
to the previous hops since they do not have
any next hops to send Join Tables to unless they are
forwarding group nodes. When the node does not receive
any acknowledgment within the timeout interval,
Transmission
Passive Ack
Transmission

Figure

6. Passive acknowledgments.
it retransmits the message. If the node cannot verify the
packet delivery after an appropriate number of retrans-
missions, it considers the route to be invalidated. The
node then broadcasts a message to its neighbors specifying
that the next hop to the source cannot be reached.
Upon receiving this packet, each neighbor builds and
unicasts the Join Table to its next hop if it has a
route to the multicast source. If no route is known, it
simply broadcasts the packet specifying the next hop is
not available. In both cases, the node sets its FG FLAG.
The FG FLAG setting of every neighbor may create excessive
redundancy, but most of these settings will expire
because only necessary forwarding group nodes will be
refreshed in the next Join Table propagation phase.
3.4. Elimination of Route Acquisition Latency
The major drawback of on-demand routing protocols
is the delay required to obtain a route. This route acquisition
latency makes on-demand protocols less attractive
in networks where real-time traffic is exchanged.
In the basic ODMRP, when the source does not have
any multicast route information, it postpones the data
transmission for a certain period of time. In contrast to
unicast routing, the selection of the waiting time is not
straightforward. In unicast, the source can send data as
soon as it receives a Route Reply. In ODMRP, how-
ever, sources cannot transmit data immediately after
receiving the first Join Table since routes to receivers
that are farther away may not yet have been established.
To eliminate these problems, when a source has data
to send but does not know any multicast route, it floods
the data instead of the Join Request. The data packet
also replaces the periodic transmission of Join Re-
quests. 3 Basically, Join Data becomes a Join Request
with data payload attached. The flooding of
Join Data achieves data delivery in addition to constructing
and refreshing the routes. Although the size
of the flooded packet is larger compared with Join Re-
quests, route acquisition latency is eliminated.
4. Performance Evaluation
4.1. Simulation Environment
We implemented the simulator within the Global
Mobile Simulation (GloMoSim) library [26]. The GloMoSim
library is a scalable simulation environment for
wireless network systems using the parallel discrete-event
simulation capability provided by PARSEC [2].
Our simulation modeled a network of 50 mobile hosts
placed randomly within a 1000m \Theta 1000m area. Radio
propagation range for each node was 250 meters and
channel capacity was 2 Mbits/sec. Each simulation executed
for 600 seconds of simulation time. We conducted
multiple runs with different seed numbers for each scenario
and averaged collected data over those runs.
We used a free space propagation model [21] with a
threshold cutoff in our experiments. In the free space
model, the power of a signal attenuates as 1=d 2 where d
is the distance between radios. In the radio model, we
assumed the ability of a radio to lock on to a sufficiently
strong signal in the presence of interfering signals, i.e.,
capture. If the capture ratio (the minimum ratio
of an arriving packet's signal strength relative to those
of other colliding packets) [21] was greater than the
predefined threshold value, the arriving packet was received
and other interfering packets were dropped. We
used the IEEE 802.11 Distributed Coordination Function
(DCF) [11] as the medium access control proto-
col. The scheme used was Carrier Sense Multiple Ac-
cess/Collision Avoidance (CSMA/CA) with acknowl-
edgments. We developed a traffic generator to simulate
constant bit rate sources. The size of data payload was
512 bytes. Each node moved constantly with the pre-defined
speed. Moving direction was selected randomly,
and when nodes reached the simulation terrain bound-
ary, they bounced back and continued to move. We sim-
3 To differentiate between the flooded data that performs the Join
Request role and the ordinary data, we term the flooded data
packet as Join Data.
ulated one multicast group with one source. The multicast
members and the source were chosen randomly
with uniform probabilities. Members joined the group
at the start of the simulation and remained as members
throughout the simulation.
4.2. Methodology
To investigate the impact of our enhancements, we
simulated the following three schemes:
1. Scheme A: the basic ODMRP as specified in [10],
2. Scheme B: the enhanced ODMRP that uses the
minimum delay as the route selection metric, and
3. Scheme C : the enhanced ODMRP that uses the
route expiration time as the route selection metric.
Both enhanced schemes included reliable transmission
and route acquisition latency elimination features. We
evaluate the protocols as a function of speed and multicast
group size. In the first set of experiments, we set
the size of the multicast group constant to ten and vary
the speed from 0 km/hr to 72 km/hr. In the second set
of simulations, we set the node mobility speed constant
at km/hr and vary the multicast group size from two
(unicast) to twenty. The metrics of interest are:
ffl Packet delivery ratio: The number of data packets
actually received by multicast members over the
number of data packets supposed to be received by
multicast members.
ffl End-to-end delay: The time elapsed between the
instant when the source has data packet to send and
the instant when the destination receives the data.
Note that if no route is available, the time spent
in building a route (route acquisition latency) is included
in the end-to-end delay.
ffl Control overhead: The total control bytes trans-
mitted. We calculate bytes of data packet and Join
Data headers in addition to bytes of control packets
(Join Requests, Join Tables, active acknowledg-
ments) as control overhead.
ffl Number of total packets transmitted per data
packet delivered: The number of all packets (data
and control packets) transmitted divided by data
packet delivered to destinations. This measure shows
the efficiency in terms of channel access and is very
important in ad hoc networks since link layer protocols
are typically contention-based.0.60.81
Packet
Delivery
Mobility Speed (km/hr)
scheme A
scheme B
scheme C

Figure

7. Packet delivery ratio as a function of speed.
4.3. Simulation Results
4.3.1. Packet Delivery Ratio
The packet delivery ratio as a function of the mobility
speed and the multicast group size is shown in Figures
7 and 8, respectively. We can see from Figure 7 that
as speed increases, the routing effectiveness of scheme
A degrades rapidly compared with schemes B and C.
Both schemes B and C have very high delivery ratios of
over 96% regardless of speed. As they reconstruct the
routes in advance of topology changes, most data are
delivered to multicast receivers without being dropped.
Scheme A, however, periodically transmits Join Requests
and Join Tables (every 400 ms and 180 ms,
respectively) without adapting to mobility speed and
direction. Frequent flooding resulted in collisions and
congestion, leading to packet drops even in low mobility
rates. At high speed, routes that are taken at the Join
Request phase may already be broken when Join Tables
are propagated. In scheme A, nodes do not verify
the reception of transmitted Join Tables. Most Join
Tables failed to reach the source and establish the forwarding
group. Thus, when the source sends the data,
the multicast route is not properly built and packets can
not be delivered. Both schemes B and C enforce reliable
Join Table transmissions. The schemes appropriately
establish and refresh the routes and forwarding group
nodes even in high mobility situations and they proved
to be robust to the mobility speed.
In

Figure

schemes B and C outperform scheme A
again. The result shows that our enhanced protocols
are robust to multicast group size in addition to mobil-0.60.81
Packet
Delivery
Multicast Group Size
scheme A
scheme B
scheme C

Figure

8. Packet delivery ratio as a function of number of multi-cast
End-to-End
Delay
(millisecond)
Mobility Speed (km/hr)
scheme A
scheme B
scheme C

Figure

9. End-to-end delay as a function of speed.
ity speed. Scheme A's performance improves as the size
becomes larger. As the number of receivers increases,
the number of forwarding group nodes increases accord-
ingly. Hence, the connectivity of the multicast mesh
becomes richer and the redundancy of the paths helps
delivering data to destinations.
4.3.2. End-to-End Delay

Figures

show the end-to-end delay of each
scheme. Schemes B and C have shorter delays compared
with that of scheme A. In scheme A, sources flood
Join Requests and must wait for a certain amount of
time to send data until routes are established among
multicast members. In schemes B and C, on the con-
trary, sources flood Join Data immediately even before
they construct routes and forwarding group. The5155 10 15 20
End-to-End
Delay
(millisecond)
Multicast Group Size
scheme A
scheme B
scheme C

Figure

10. End-to-end delay as a function of number of multicast
Control
(Bytes)
Mobility Speed (km/hr)
scheme A
scheme B
scheme C

Figure

11. Control overhead as a function of speed.
route acquisition latency is eliminated and packets are
delivered to receivers in shorter delays. One may be
surprised to see that the delay of scheme B which uses
the minimum delay route is larger than that of scheme
C which uses the stable (and possibly longer delay)
route. Even though the route taken by Join Data
is the shortest delay route at that instant, it may not
be the minimum delay route later on as nodes move.
In addition, compared with stable routes, the minimum
delay routes disconnect more frequently which results
in data packets traversing through alternate and longer
routes formed by forwarding group nodes.
4.3.3. Control Overhead

Figure

11 shows the control byte overhead as a function
of mobility speed for each protocol. Remember
2e+064e+06
Control
(Bytes)
Multicast Group Size
scheme A
scheme B
scheme C

Figure

12. Control overhead as a function of number of multicast
members.
that the transmission of control packets in scheme A is
time triggered only without adapting to mobility speed.
Hence, the amount of control overhead does not increase
as the mobility speed increases. In fact, control overhead
decreases as nodes move faster. As Join Tables
are less likely to reach the target nodes in a highly mobile
environment, the Join Table propagations by the
next nodes are triggered fewer. Furthermore, data packets
(whose header is calculated as control overhead), are
transmitted fewer because forwarding group nodes and
routes are not established or refreshed appropriately as
the speed increases. On the other hand, the overhead of
schemes B and C goes up as mobility speed increases.
Since they use mobility prediction to adapt to mobility
speed, they send more Join Data and Join Tables
when mobility is high. In addition, Join Table
retransmission and active acknowledgment propagation
also increase with mobility and add to the control over-
head. It is important to observe that the overhead of
schemes B and C are both significantly less than that
of scheme A in low mobility cases because schemes B
and C transmit control packets only when necessary.
The enhanced schemes have more overhead when nodes
move fast, but the extra control packets are used efficiently
in delivering data (see Figure 7). When comparing
scheme B with scheme C, we can see that scheme
yields more overhead in low mobility although both
schemes produce nearly equal amount of overhead in
high mobility. Since scheme C chooses a stable route,
Join Data are flooded less often. When nodes move
relatively fast (for example, 72 km/hr in our simula-1525
Avg.
of
Total
Packets
Transmitted
Data
Packet
Delivered
Mobility Speed (km/hr)
scheme A
scheme B
scheme C

Figure

13. The Number of Total Packets Transmitted per Data
Packet Delivered as a Function of Speed.
tion), however, routes are broken often and links will
remain connected for a short duration of time. Sources
are thus likely to use MIN REFRESH INTERVAL and the
overheads incurred by schemes B and C become almost
identical.
In

Figure

12, control overhead of all schemes increases
when the number of multicast group increases.
As there are more multicast receivers, more Join Tables
are built and propagated. Schemes B and C have
much less overhead than that of scheme A. Scheme A
periodically sends Join Requests and Join Tables,
but enhanced schemes send Join Data and Join Tables
only in advance of topology changes. As expected,
scheme C further improves scheme B. The number of
control packet transmissions are less as scheme C uses
stable routes.
4.3.4. Number of Total Packets Transmitted per Data
Packet Delivered
The number of total packets (Join Requests, Join

Tables

, Join Data, Data, and active acknowledg-
ments) transmitted per data packet delivered is presented
in Figures 13 and 14. We have mentioned previously
that this measure indicates the channel access
efficiency. We can see the improvements made by enhanced
schemes from the results. In Figure 13, the number
for scheme A remains relatively constant to mobility
speed. As shown in Figures 7 and 11, the number of
data packets delivered and the amount of control bytes
transmitted both decrease as mobility increases. The
number for scheme A thus remains almost unchanging.
Avg.
of
Total
Packets
Transmitted
Data
Packet
Delivered
Multicast Group Size
scheme A
scheme B
scheme C

Figure

14. The Number of Total Packets Transmitted per Data
Packet Delivered as a Function of Number of Multicast Members.
The measures for schemes B and C gradually increase
with mobility speed. Both schemes deliver a high portion
of the data to destinations regardless of speed (see

Figure

7) and the number of data packets delivered remains
similar. Nevertheless, more control packets must
be sent in order to adapt to node mobility speed, and
thus the total number of transmitted packets increases
with speed.
In

Figure

14, the number of all packets transmitted
per data packet delivered decreases as the group size becomes
larger for all schemes. This result is expected as
the number of multicast members increases, the number
of data packets received by members increases accord-
ingly. Again, schemes B and C have greatly improved
the efficiency of scheme A.
5. Conclusion
We presented new techniques to improve the performance
of ODMRP. By using the mobility and link connectivity
prediction, we reconstruct routes and forwarding
groups in anticipation of topology changes. This
adaptive selection of the refresh interval avoids the un-necessary
control packet transmissions and the resulting
bandwidth wastage. We applied a new route selection
algorithm to choose routes that will stay valid for the
longest duration of time. The usage of stable routes
further reduces the control overhead. We used passive
acknowledgments and retransmissions to improve the
reliable Join Table delivery. The improved reliability
plays a factor in protocol enhancement since the
delivery of Join Tables is critical in establishing the
routes and forwarding group nodes. We also introduced
a method to eliminate the route acquisition latency.
Simulation results showed that our new methods improved
the basic scheme significantly. More data packets
were delivered to destinations, fewer control packets
were produced in low mobility, control packets were utilized
more efficiently in high mobility, and end-to-end
delay was shorter. The enhanced ODMRP is scalable,
robust to host mobility, and efficient in channel access.

Acknowledgements

Authors thank Dr. Ching-Chuan Chiang and Guangyu
Pei for their contributions.



--R

"Optimal Prioritization of Handovers in Mobile Cellular Networks,"
"PARSEC: A Parallel Simulation Environment for Complex Systems,"
"Core Based Trees (CBT) - An Architecture for Scalable Inter-Domain Multicast Routing,"
"AM- Route: Adhoc Multicast Routing Protocol,"
"Forwarding Group Multicast Protocol (FGMP) for Multihop, Mobile Wireless Networks,"
"A Reservation-Based Multicast (RBM) Routing Protocol for Mobile Networks: Initial Route Construction Phase,"
"Multicast Routing in Datagram Internetworks and Extended LANs,"
"The PIM Architecture for Wide-Area Multicast Routing,"
"A Multi-cast Routing Protocol for Ad-Hoc Networks,"
"On-Demand Multicast Routing Protocol (ODMRP) for Ad Hoc Net- works,"
IEEE Computer Society LAN MAN Standards Committee
Internet Engineering Task Force (IETF) Mobile Ad Hoc Networks (MANET) Working Group Charter
"A Lightweight Adaptive Multicast Algorithm,"
"The DARPA Packet Radio Net-work Protocols,"
Understanding the GPS: Principles and Applications
"On-Demand Multicast Routing Protocol,"
"On-Demand Multi-cast Routing Protocol (ODMRP) for Ad Hoc Networks,"
"Internet Time Synchronization: the Network Time Protocol,"
"Multicast Routing Extensions for OSPF,"
"Minimiz- ing Cellular Handover Failures Without Channel Utilization Loss,"
Principles and Practice
"Multicast Operation of the Ad-hoc On-Demand Distance Vector Routing Protocol,"
"MCEDAR: Multicast Core-Extraction Distributed Ad hoc Routing,"
"Mobility Prediction and Routing in Ad Hoc Wireless Networks,"
"Associativity-Based Routing for Ad-Hoc Mobile Networks,"
UCLA Parallel Computing Laboratory and Wireless Adaptive Mobility Laboratory
"AMRIS: A Multicast Protocol for Ad hoc Wireless Networks,"
--TR
Multicast routing in datagram internetworks and extended LANs
Core based trees (CBT)
Multicast routing extensions for OSPF
The PIM architecture for wide-area multicast routing
A preservation-based multicast (RBM) routing protocol for mobile networks
Multicast operation of the ad-hoc on-demand distance vector routing protocol
Mobility prediction and routing in <I>ad hoc</I> wireless networks
Communications
Forwarding Group Multicast Protocol (FGMP) for multihop, mobile wireless networks
Associativity-Based Routing for Ad Hoc Mobile Networks
Parsec

--CTR
Jianping Pan , Lin Cai , Y. Thomas Hou , Yi Shi , Sherman X. Shen, Optimal Base-Station Locations in Two-Tiered Wireless Sensor Networks, IEEE Transactions on Mobile Computing, v.4 n.5, p.458-473, September 2005
Caixia Chi , Dawei Huang , David Lee , XiaoRong Sun, Lazy flooding: a new technique for information dissemination in distributed network systems, IEEE/ACM Transactions on Networking (TON), v.15 n.1, p.80-92, February 2007
Xiaojiang Du , Dapeng Wu, Joint design of routing and medium access control for hybrid mobile ad hoc networks, Mobile Networks and Applications, v.12 n.1, p.57-68, January 2007
Jianping Pan , Y. Thomas Hou , Lin Cai , Yi Shi , Sherman X. Shen, Topology control for wireless sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
Vinod Namboodiri , Manish Agarwal , Lixin Gao, A study on the feasibility of mobile gateways for vehicular ad-hoc networks, Proceedings of the 1st ACM international workshop on Vehicular ad hoc networks, October 01-01, 2004, Philadelphia, PA, USA
Leslie D. Fife , Le Gruenwald, Research issues for data communication in mobile ad-hoc network database systems, ACM SIGMOD Record, v.32 n.2, p.42-47, June
Meng-Yen Hsieh , Yueh-Min Huang , Tzu-Chinag Chiang, Transmission of layered video streaming via multi-path on ad hoc networks, Multimedia Tools and Applications, v.34 n.2, p.155-177, August    2007
Alejandro Quintero, A User Pattern Learning Strategy for Managing Users' Mobility in UMTS Networks, IEEE Transactions on Mobile Computing, v.4 n.6, p.552-566, November 2005
ad hoc networks;mobile computing;multicast and routing protocols;mobility prediction