<figure><img src="image_1.png" /></figure>

HAL
open science

# A Location-Based Algorithm for Supporting Multicast Routing in Mobile Ad-Hoc Networks

Le The Dung, Beongku An

<figure><img src="image_2.png" /></figure>

## ► To cite this version:

Le The Dung, Beongku An. A Location-Based Algorithm for Supporting Multicast Routing in Mobile Ad-Hoc Networks. 9th International Conference on Network and Parallel Computing (NPC), Sep 2012, Gwangju, South Korea. pp.542-549, 10.1007/978-3-642-35606-3_64. hal-01551333

HAL Id: hal-01551333

https://inria.hal.science/hal-01551333

Submitted on 30 Jun 2017

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Location-based Algorithm for Supporting Multicast
Routing in Mobile Ad-Hoc Networks

Le The Dung<fnref n="1" /> and Beongku An<fnref n="2" />

**Abstract.** In this paper, we propose a location-based algorithm for supporting multicast routing in mobile ad-hoc networks. Instead of having routing paths in advanced to forward data packets from source node to multicast receivers, this algorithm let each node which receives data packets independently, adaptively determines the routing paths to forward data packets based on the information of its neighbor nodes. Before forwarding data packets, mobile node checks and uses one of its neighbor nodes as the next hop. Therefore, the availability of routing segments is ensured, providing high performance even in high mobility environment. The performance of this algorithm for multicast routing is validated via simulation using OPNET.

**Keywords:** Mobile ad-hoc networks, Multicast routing, Mobile node's location

## 1 Introduction

Ad-hoc networks are decentralized, self-organizing networks, able to form a communication network without relying on any fixed infrastructure. Each mobile node in an ad-hoc network is equipped with radio transceiver which allows it to communicate with other nodes over wireless channel. Moreover, mobile node may use GPS device to obtain its location, velocity, moving direction to orient the routing decision. Since the transmission range of mobile nodes in ad-hoc networks is limited, communication among them is often multi-hop. Therefore, nodes may operate, if needed, as relays for data packets to be routed to the intended destination.

Ad-hoc networks have advantages over conventional networks. For example, they are more economical because they do not need to build fixed infrastructure, they increase mobility and flexibility because they can be brought up and torn down in a short time.

The multicast routing protocol in mobile ad-hoc networks (MANET) is currently getting the attraction from researchers because of the development of considerable number of multicast applications. The advantage of multicast routing is its capacity to efficiently save network resources by allowing source node to send data in a single transmission to a group of receivers. The classification of multicast routing protocols is presented in detailed in [1]. As in [1] multicast routing protocols can be grouped

<footnote n="1">¹Dept. of Electronics & Computer Engineering in Graduate School, Hongik University, Korea
thedung_hcmut@yahoo.com</footnote>

<footnote n="2">²Dept. of Computer & Information Communications Engineering, Hongik University, Korea
beongku@hongik.ac.kr</footnote>
according to their topologies which use two different taxonomies, i.e. reactive/proactive/hybrid and flat/hierarchical multicast routing protocols.

Recently, due to the availability of small, inexpensive, low power GPS receivers and techniques for finding relative coordinates based on signal strength, the location-based routing method can be used in mobile ad-hoc networks. Geocast [2] is an approach to delivery multicast data packets to a set of node within a specified geographic region. Several schemes for geocasting are proposed in [3]. In those schemes, all multicast receivers reside in a multicast region. Geomulticast routing was proposed in [4] for the case that multicast receivers reside in several regions. In Geomulticast routing, mobile nodes periodically send mobility information to their neighbor nodes. Then a mobile node is grouped into cluster if its mobility is less than a threshold. Cluster head is selected as the node which has the lowest id. By using the same process, several clusters may be merged to parent clusters. A multicast mesh is formed among cluster heads. Multicast data are delivered through this clustered head based limit mesh structure. In RSGM [5], the network area is divided into many square zones. Each mobile node uses its current location pos (x, y) to calculate its zID (a, b). The center of zone is also calculated. A zone leader is the node which is nearest to the zone center. Zone leaders flood LEADER packets in their zones periodically to announce their leadership, members in each zone send REFRESH packets to their zone leader to notify their membership. When a multicast member moves into a new zone, if that zone leader is unknown, it queries the neighbor node in the zone for the leader information. If it fails to get this information it will announce itself as a leader by flooding LEADER packet into the zone. The zone leaders are responsible for sending REPORT packets periodically to update zone membership information to the source node. Source node starts the multicast session by flooding ANNOUNCE packet into the network. Multicast packets are sent along the virtual distribution tree rooted at the source node to the multicast members.

The rest of this paper is organized as follows. The location-based algorithm consisting of mobile node's location updating, multicast data packet forwarding, and adaptive update interval of mobile's node location is described in Section 2. The performance results of this location-based algorithm are discussed in Section 3. Finally, the paper is concluded in Section 4.

# 2 The Proposed Location-based Algorithm

## 2.1 Basic Concepts

Our proposed location-based algorithm for multicast routing uses the information of multicast receivers' locations and neighbor nodes at each mobile node to choose the next hop for data packet forwarding. By using that information, the data packet forwarding algorithm can choose available best intermediate nodes to forward multicast data packets. Also, receivers and intermediate nodes can adaptively choose the information updating rate based on their mobility and network status.
## 2.2 Mobile node's location updating

In this section, we describe detailed steps of how to get the necessary information to guide the routing and how multicast data packets are sent from source node to multicast receivers.

*Step 1:* Each mobile node advertises its id and location by sending Introduce packet at adaptive rate. The format of Introduce packet is as follow.

<table><caption>Fig. 1. The format of Introduce packet.</caption><tr><td>Node ID</td><td>Node Location</td><td>TTL</td></tr></table>

*Step 2:* To join the multicast group, each multicast receiver sends Join packet to source node. The Join packets sent by multicast receivers consist of the IDs and current location of receivers. The format of Join packet is below.

<table><caption>Fig. 2. The format of Join packet.</caption><tr><td>Src Location</td><td>Receiver Location</td><td>Seq_Num</td></tr></table>

*Step 3:* After source node receives these Join packet, it send multicast data packets to every multicast receivers using the following data packet forwarding algorithm.

## 2.3 Location-based packet forwarding algorithm

Location-based packet forwarding algorithm is used for both Join packets and data packets. According to this algorithm, each mobile node independently chooses the next hop to forward packets (i.e. Join packets and data packets) based on the following priorities:

1. A node chooses the neighbor node which is the farthest node from it (i.e. having largest BH in Fig. 3).

$$ where \quad BH = \frac{AB^2 + BC^2 - AC^2}{2 \times AC} \quad (1) $$

2. If there are more than two nodes satisfying the above criteria, the node which is the nearest to the source node – receiver line (i.e. having smallest AH in Fig. 3) is selected.

$$ where \quad AH = AB \sin \left( \frac{AB^2 + BC^2 - AC^2}{2 \times AB \times AC} \right) \quad (2) $$

3. Finally, if these two criteria are still met, the node which has the lowest ID is selected.
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Algorithm for choosing next hop to forward data packets.</figcaption></figure>

To reach multicast receivers, data sent by source node consist of next hop ids determined by previous location-based packet forwarding algorithm. The information of receivers at source node is from Join packets sent by receivers to source node regularly. When source node receives Join packets, it will add the receiver information to Receiver Record Table (RRT) entry and set the timer. If any multicast receiver does not want to participate in multicast session, it simply stops sending Join packet to source node. After not receiving Join packet from a receiver, the timer of entry in RRT for that receiver expires and it is removed from RRT.

Node receiving data packet checks if its id matches one of the next-hop ids in data header. If yes, it will use the packet forwarding node to select next hop ids to forward the data packet. It eliminates unnecessary receiver information. It only keeps the receiver information (i.e. receiver location) to which data packets are forwarded. Fig. 4 illustrates how multicast data packets are forwarded from source node to multicast receivers.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Multicast data sending from source node (S) to multicast receivers (R1, R2, R3, R4).</figcaption></figure>

## 2.4 Adaptive update interval of mobile node's location

To eliminate unnecessary Introduce packets sent by mobile nodes to update its location information to their neighbor nodes, we propose the idea of adaptive update
interval of mobile node's location. All mobile nodes will listen to the data packets regardless of being intended receivers or not. If the chance of receiving data packet of a mobile node is small, its information (i.e. id, location) is not important to packet routing. Then it reduces the rate of sending Introduce packets to its neighbor nodes. If a mobile node receives data packets often, it knows that it may play an important role in packet routing. Therefore it sends Introduce packets more frequent. The data receiving rate is calculated as

$$ \text{Data ReceivingRate} = \frac{\text{num\_of\_data} \times \text{data\_rate}}{\text{elapsed\_time}} \quad (3) $$

# 3 Performance Evaluation

## 3.1 Simulation environment

The following table shows the settings of simulation parameters. We simulate one multicast group which has one multicast source and varying number of multicast receiver. Multicast receivers are chosen randomly. Source sends packet at constant rate of 20 packets per second. Each data packet has 512 bytes.

Members join the multicast group at the beginning of simulation and remain as members during the simulation. Source begins to send data right after it receives the Join packet and continues sending the data throughout the simulation.

<table><caption>Table 1. Simulation parameters.</caption><thead><tr><td>Environment Factors</td><td>Defined Configuration</td></tr></thead><tbody><tr><td>Simulator</td><td>OPNET</td></tr><tr><td>Simulation Area</td><td>1000m × 1000m</td></tr><tr><td>Simulation Time</td><td>300sec</td></tr><tr><td>Number of Nodes</td><td>50</td></tr><tr><td>Radio Range</td><td>250m</td></tr><tr><td>Mobility</td><td>Random Waypoint</td></tr><tr><td>Node Speed</td><td>0~60km/h</td></tr><tr><td>Node Pause Time</td><td>0~10sec (randomly)</td></tr><tr><td>MAC Protocol</td><td>IEEE 802.11</td></tr></tbody></table>

## 3.2 Simulation results

We run the simulation and take the average values to evaluate how our proposed multicast routing protocol can efficiently support the multicast routing services by using following metrics:

* *PDR*: the ratio of the number of data packets received at multicast receivers to the number of data packets transmitted at source node.

* *Normalized control overhead*: the ratio of total number of control overheads to the number of data packets received at multicast receivers.
<figure><img src="image_6.png" /><figcaption>Fig. 5. PDR (Packet Delivery Ratio) as a function of node mobility.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6. PDR (Packet Delivery Ratio) as a function of number of multicast member nodes.</figcaption></figure>

Fig. 5 and Fig. 6 present PDR as functions of node mobility and number of multicast member nodes (i.e. scalability of the network), respectively. As we can see in Fig. 5 and Fig. 6, our proposed algorithm still maintains high PDR under high node mobility and scales well as the number of multicast member node increases because each node adaptively selects next hop to forward data based on the updated information of its neighbor nodes. The update interval of node's location is optimized by using adaptive strategy, giving latest neighbor node's information with the lowest number of control overheads.
<figure><img src="image_8.png" /><figcaption>Fig. 7. Normalized control overhead as a function of number of node mobility.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 8. Normalized control overheads as a function of number of multicast member nodes.</figcaption></figure>

Fig. 7 and Fig. 8 present the normalized control overhead as functions of node mobility and multicast member nodes, respectively. In our proposed algorithm, approximately for every 4 multicast data packets successfully delivered at receivers, a control overhead is needed at node mobility of 20km/h and 40km/h. While approximately for every 3 multicast data packets successfully delivered at receivers, a control overhead is needed at node mobility of 60km/h. As the number of multicast member nodes increases, our proposed location-based algorithm shows efficient multicast data transmission (i.e. for every 4, 5, and 7 multicast data packets successfully delivered at receivers, a control overhead is needed) because a node may use its neighbor information to select several next nodes for multicast data packet forwarding.
# 4 Conclusions

In this paper, we propose a location-based algorithm for supporting multicast routing in mobile ad-hoc networks. This algorithm sends multicast data packets based on the location information of multicast receivers. Each node uses packet forwarding algorithm to adaptively select next nodes for multicast data forwarding. The update interval of mobile node's location used in packet forwarding algorithm is optimized by adaptive strategy at each node.

The performance evaluation using OPNET of our proposed algorithm shows that it can support efficient multicast routing with high PDR under high node mobility and scales well as the number of multicast member nodes increases.

# Acknowledgment

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2011-0025907).

# References

1. Luo Junhai, Ye Danxia, Xue Liu, Fan Mingyu: A Survey of Multicast Routing Protocols for Mobile Ad-Hoc Networks. In: IEEE Communications Survey & Tutorials, vol. 11, no. 1, pp. 78-91, 2009.

2. J. C. Navas, T. Imielinski: Geocast – geographic addressing and routing. In: Proc. of ACM/IEEE Int. Conf. on Mobile Computing and Networking, pp. 66-76, 1997.

3. Young-Bae Ko, Nitin H. Vaidya: Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithm. In: Proc. of Second IEEE Workshop on Mobile Computing Systems and Applications, pp. 101-110, 1999.

4. Beongku An, Symeon Papavassiliou: Geomulticast: architectures and protocols for mobile ad hoc wireless networks. In: Journal of Parallel and Distributed Computing, vol. 63, pp. 182-195, 2003.

5. Xiaojing Xiang, Xin Wang, Yuanyuan: Stateless Multicasting in Mobile Ad Hoc Networks. In: IEEE Transactions on Computer, vol. 59, no. 8, pp. 1076-1090, 2010.