Microsoft Word - ETASR_V11_N5_pp7635-7640 Engineering, Technology & Applied Science Research Vol. 11, No. 5, 2021, 7635-7640 7635 www.etasr.com Mahdi et al.: A Multipath Cluster-Based Routing Protool For Mobile Ad Hoc Networks A Multipath Cluster-Based Routing Protocol For Mobile Ad Hoc Networks Mohammed A. Mahdi Computer Science and Information Department College of Computer Science and Engineering University of Ha’il Ha’il, Saudi Arabia wsabi3@gmail.com Tat-Chee Wan School of Computer Science Universiti Sains Malaysia Penang, Malaysia tcwan@usm.my Adnan Mahdi School of Electrical and Electronic Engineering, Universiti Sains Malaysia, Malaysia and College of Computer Science and Engineering, University of Hafr Al Batin, Saudi Arabia adnanmhdi@gmail.com Mohamed A.G. Hazber Computer Science and Information Department, College of Computer Science and Engineering University of Ha’il Ha’il, Saudi Arabia m.hazber@uoh.edu.sa Badiea Abdulkarem Mohammed Computer Engineering Department College of Computer Science and Engineering University of Ha’il Ha’il, Saudi Arabia b.alshaibani@uoh.edu.sa Abstract-A MANET (Mobile Ad-hoc Network) is a group of mobile network nodes dynamically forming a network without any pre-existing infrastructure. Multi-path routing protocols in MANETs try to discover and use multiple routes between source and destination nodes. Multipath routing is typically used to reduce average delay, increase transmission reliability, provide load balancing among multiple routes, and improve security and overall QoS (Quality of Service). In this paper, the Cluster Based Routing Protocol (CBRP), which is a single path MANET protocol is enhanced to use multiple paths. The traffic will be distributed among multiple paths to reduce network traffic congestion and decrease delay. An analytical model is used for multipath and single path CBRP routing protocols in MANETs to estimate the end-to-end delay and queue length. The analytical results show that the average delay and average queue length in multipath CBRP are less than the average delay and queue length in single path CBRP. Keywords-MANET; routing protocols; single path; multi path; CBRP I. INTRODUCTION A Mobile Ad-hoc Network (MANET) is a collection of wireless mobile nodes/routers. The nodes dynamically form a temporary network without the use of any existing network infrastructure or centralized administration. The mobile nodes are equipped with wireless interfaces that utilize radio channels to communicate with each other, without the need for centralized management [1]. MANETs can be used in classrooms, battlefields, and disaster recovery situations [1, 2]. Routing protocols are an important part of any network. They play the main role for any communication in the network and they are used to establish and correct efficient routes among a pair of network nodes and to deliver messages in a timely manner [3-5]. Routing protocols in MANETs are differentiated in terms of hop-by-hop or source routing, reactive or proactive approach, single path or multipath, distance vector or link state, and unicast or multicast [6]. Multipath routing is a technique to overcome the problems of frequent topological changes and link instability because the use of multiple paths could diminish the effect of possible link failures between the nodes [7, 8]. Thus, multipath routing protocols of wireless ad-hoc networks are superior over conventional single-path ad-hoc routing protocols [9] because the multipath routing protocols reduce end-to-end delay, provide more reliable network services, allow load balancing among multiple routes, provide higher aggregate bandwidth, improve security, and overall they improve the Quality of Service (QoS) [10, 11]. Various multipath routing protocols have been proposed for wireless ad hoc networks. A multipath routing protocol based on the source routing protocol DSR is the Salvage capable opportunistic Node-disjoint Multipath Routing (SNMR) [12]. A multipath routing protocol based on the Ad hoc On-demand routing scheme is the Ad hoc On-demand Multipath Distance Vector (AOMDV) [3, 10]. II. MANET ROUTING PROTOCOLS MANET routing protocols based on the schemes of discovering and maintaining paths are classified into three classes: reactive, proactive, and hybrid [13, 14] (Figure 1). In terms of reactivity, they are classified as reactive or proactive, and regarding the number of paths as single or multi-path. The reactive method is more efficient than the proactive method. The most common-known reactive routing protocols in MANETs (single-path and multipath) are described below. Corresponding author: Mohammed A. Mahdi Engineering, Technology & Applied Science Research Vol. 11, No. 5, 2021, 7635-7640 7636 www.etasr.com Mahdi et al.: A Multipath Cluster-Based Routing Protool For Mobile Ad Hoc Networks A. MANET Single-Path Routing Protocols MANET single path routing protocols mainly intend to maintain a single route between a source and a destination node. The most popular routing protocols of this type are AODV, DSR, and CBRP. Fig. 1. MANET routing protocol taxonomy. 1) Dynamic Source Routing (DSR) DSR [15, 16] is an on-demand routing protocol that is based on the concept of source routing. It is a simple and an efficient routing protocol, specifically designed for use in multi-hop wireless ad hoc networks. It consists of two mechanisms, Route Discovery and Route Maintenance, that work together to allow nodes to discover and maintain routes from the sources to arbitrary destinations in network. DSR computes the paths when necessary and then maintains them. It applies on-demand schemes for both path discovery and path maintenance. Thus, it makes the routing overhead traffic to scale automatically to the actual needed size, which is considered as its main advantage. 2) Ad hoc On-demand Distance Vector (AODV) AODV [17] is a reactive on-demand routing protocol that allows dynamic, self-starting, multi-hop routing among mobile nodes desiring to establish and maintain an MANET. It is essentially a combination of DSR and DSDV (Destination Sequenced Distance Vector) protocol. AODV uses the basic on-demand mechanisms of Route Discovery and Route Maintenance as in DSR and a next hop routing model with sequence numbers and periodic beacons to discover and maintain routes of DSDV. Also, when the ad-hoc network topology changes, an AODV sequence number method is used to avoid long-term loops. Moreover, AODV allows the mobile nodes to obtain routes quickly and does not require maintaining routes that are not in active communication. 3) Cluster-Based Routing Protocol (CBRP) CBRP [18-20] is a hierarchical on-demand routing protocol that uses source routing, like DSR, to avoid forming loops. CBRP is an efficient, scalable, and robust routing protocol for MANETs. It features more advantageous metrics than existing routing protocols, its overhead is less and its throughput is higher than AODV's. The CBRP is designed to be used in medium-to-large MANETs. CBRP groups the nodes of a network into several clusters. Each cluster has a cluster head which coordinates data transmission within the cluster and with other clusters. There are four possible states of the node in the cluster: NORMAL, ISOLATED, CLUSTERHEAD, and GATEWAY. Figure 2 shows these states. One of the advantages of CBRP is that only cluster heads exchange routing information, therefore the number of control overhead transmitted through the network is far less than the traditional flooding methods. Other features of CBRP [20] are: • Distributed operation is fully used. • During the dynamic route discovery process there is less flooding traffic. • Explicit exploitation of uni-directional links that would otherwise be unused. • Broken paths can be repaired locally without route rediscovery. • Sub-optimal routes can be shortened as they are used. Fig. 2. Cluster Based Routing Protocol (CBRP). B. MANET Multi-Path Routing Protocols Multi-path routing protocols try to discover a multiple route from the source node to the destination node. Multipath routing can effectively improve reliability, end-to-end delay, and achieve load balancing, but it is more complicated than single path routing [11]. Most multipath routing protocols proposed for wireless ad hoc networks are based on reactive routing. They are mostly created on the basis of DSR and AODV. 1) Ad hoc On-demand Multipath Distance Vector routing (AOMDV) AOMDV [3, 10] extends the AODV protocol to compute multiple paths between the source and the destination during route discovery. Multiple paths are computed to guarantee that the route is loop-free and disjoint. The AOMDV protocol calculates multiple loop-free paths, where every node maintains an advertised hop count for each destination node. Therefore, loop freedom is accomplished, and the advertised hop count represents the maximum hop count for all multiple paths. AOMDV has three novel aspects compared to other on-demand multipath protocols. First, it does not have high intermodal coordination overhead. Second, it ensures disjointness of alternate routes via distributed computations without the use of source routing. Finally, it computes alternate paths with minimal additional overhead. Engineering, Technology & Applied Science Research Vol. 11, No. 5, 2021, 7635-7640 7637 www.etasr.com Mahdi et al.: A Multipath Cluster-Based Routing Protool For Mobile Ad Hoc Networks 2) Salvage Capable Opportunistic Node-Disjoint Multipath Routing (SNMR) SNMR [12] is based on DSR. In SNMR, a route discovery attempt, a primary path, and a node disjoint route are created between the source and the destination node along with alternative routes for the intermediate nodes of the primary route. SNMR reduces the overhead caused by duplicate RREQ broadcasting in creating multiple routes and recovers quickly from connection failures due to its packet salvaging ability. Minimum overhead, node disjoint multipath, non-duplicate RREQ rebroadcasting, and packet salvaging are the main advantages of SNMR protocol. A bloom filter is used in SNMR for space saving. Within the primary route, the intermediate nodes are compressed in a bloom filter containing their hashed addresses. SNMR uses the hashed node address to check the presence of a node in the bloom filter. Therefore, an intermediate node can check if a neighboring node is included in the primary path or not. III. THE PROPOSED MULTIPATH CBRP This paper focuses on the enhancement of CBRP routing protocol to work as a multipath routing protocol with improved QoS. A. Overview Multipath CBRP routing protocol extends the single path CBRP to use multiple paths in distributing traffic from the source node (S) to destination node (D). CBRP is selected due to its above mentioned features. For example, CBRP has less routing overhead and higher throughput than the AODV protocol. CBRP repaires broken links locally without rediscovery, which leads to the reduction of broken links in the network and increased QoS. On the other hand, CBRP has higher average delay than AODV. Therefore, it should be enhanced to reduce the average delay. The proposed Multi Path CBRP (MP-CBRP) improves the QoS in MANETs. MP-CBRP uses the idea of disjoint paths to distribute data packets over multiple routes. This distribution increases packet delivery ratio, data throughput, and reduces the average delay and queue length because it decreases congestion. An analytical model is used for multipath CBRP routing protocol and single path CBRP routing protocol to estimate the end-to-end delay and queue length. Fig. 3. The proposed Multipath CBRP Routing Protocol (MP-CBRP). As shown in Figure 3 two paths are discovered from the source node (S) to destination node (D). Data traffic λ is distributed through these two paths, divided to λ1 and λ2. The λ1 is sent through path1 and λ2 is sent through path2. S is the source node and D the destination node. CH is the cluster head, RREQ is the Route Request, RREP the Route Reply and RC is the Route Cache. The pseudo code of the proposed MP-CBRP is illustrated in Figure 4 and the flow diagram of the proposed MP-CBRP is shown in Figure 5. Fig. 4. Pseudo code of the proposed MP-CBRP. B. Network Model To obtain the Average Delay and Queue Length for multipath CBRP, let us characterize the disjoint multipath network as follows: • The network with N disjoint path resources is characterized by the set of values � � ��1,�2,�3,� ,…,��� for the individual resources. A resource could be the data transmission capacity of the given communication channel. • The set � � 1, 2, 3,. . , ,…, �� represents the average arrival rate distribution across the set of the resources (�). • The set � � ��1,�2,�3,…,� ,…,��� represents the delay of values that applied on each of the n paths when the distribution of the traffic along the paths is λ, and the distribution of the resources along the paths is µ. • The set � � ��1,�2,�3,…,� ,…,��� represents the queue length values experienced on each of the n paths Engineering, Technology & Applied Science Research Vol. 11, No. 5, 2021, 7635-7640 7638 www.etasr.com Mahdi et al.: A Multipath Cluster-Based Routing Protool For Mobile Ad Hoc Networks when the distribution of the traffic along the paths is λ, and the distribution of the resources along the paths is µ. According to the above assumption, and using the queuing model M/M/1 queue [21] the delay (� ) and queue size (� ) can be calculated as: � � � ����� (1) � � �� ���� and � � �� �� (2) Fig. 5. Flow diagram of the proposed MP-CBRP. IV. RESULTS AND DISCUSSION The results are shown in the form of graphs. Graphs show the comparison between single path CBRP and MP-CBRP with two paths, based on the terms of average delay and queue length. Values of average arrival rate (λ): 0.1, 0.3, 0.5, 0.7, 0.9 are used for all the nodes in the network model of MP-CBRP and service rate µ=1. A. Average Delay Average delay is calculated by (1). Figures 6 and 7 illustrate the average delay for single path and MP CBRP routing protocol. Two paths have been considered for the MP CBRP, and two different scenarios have been considered. 1) Average Delay Scenario 1 Traffic is split equally between the two paths in the MP CBRP model. Figure 6 shows that the average delay for MP CBRP is lesser than the average delay of single path CBRP using different arrival rates. 2) Average Delay Scenario 2 Traffic is not split equally between the two paths in MP CBRP model. The traffic for path 1 is 30% and for path 2 is 70%. Figure 7 shows that the average delay of MP CBRP is lesser than the average delay of single path CBRP using different arrival rates. Fig. 6. Average delay for single path CBRP and equally divided traffic MP CBRP. Fig. 7. Average delay for single path CBRP and MP CBRP using 30% traffic for path1 and 70% traffic for path 2 Engineering, Technology & Applied Science Research Vol. 11, No. 5, 2021, 7635-7640 7639 www.etasr.com Mahdi et al.: A Multipath Cluster-Based Routing Protool For Mobile Ad Hoc Networks Figure 8 shows the results of average delay for scenario 1 and scenario 2. The average delay for MP-CBRP in scenario 1 is better than the average delay for MP-CBRP in scenario 2 due to the high network congestion in scenario 2. Fig. 8. Average delay for single-path CBRP and MP-CBRP (scenarios 1 and 2). B. Average Queue Length The average queue length is calculated by (2). Figures 9 and 10 illustrate the average queue length for single path CBRP and MP CBRP. Two paths have been considered for CBRP multipath, and two different scenarios have been considered. Fig. 9. Average queue length for single path and MP CBRP for scenario 1. 1) Average Queue Length Scenario 1 The traffic is split equally between the two paths in MP CBRP. Figure 9 shows that the average queue length for MP CBRP is better than the average queue length in single path CBRP that uses different arrival rates. 2) Average Queue Length Scenario 2 Traffic is not split equally between the two paths in MP CBRP model. The traffic for path 1 is 30% and for path 2 is 70%. Figure 10 shows that the average queue length for MP CBRP is better than average queue length in single path CBRP that uses different arrival rates. Figure 11 shows the results of average queue length for scenario 1 and scenario 2. The queue length of MP-CBRP in scenario 1 is better the average queue length of MP-CBRP in scenario 2 due to the high network congestion in scenario 2. Fig. 10. Average queue length for single path and MP CBRP for scenario 2. Fig. 11. Average queue length for single-path CBRP and MP-CBRP (scenarios 1 and 2). V. CONCLUSION This paper proposes the enhancement of the single path CBRP MANET protocol to work as an MP routing protocol. The mathematical model using the M/M/1 queueing model was used to evaluate the performance of MP-CBRP and single path CBRP routing protocols. The results show that the average delay and average queue length in MP-CBRP are better than the average delay and average queue length in single path CBRP. In the future, the Network Simulator (NS) will be used to evaluate the MP-CBRP. Engineering, Technology & Applied Science Research Vol. 11, No. 5, 2021, 7635-7640 7640 www.etasr.com Mahdi et al.: A Multipath Cluster-Based Routing Protool For Mobile Ad Hoc Networks REFERENCES [1] M. Al Mojamed, "Integrating Mobile Ad Hoc Networks with the Internet Based on OLSR," Wireless Communications and Mobile Computing, vol. 2020, Oct. 2020, Art. no. e8810761, https://doi.org/ 10.1155/2020/8810761. [2] V. K. Verma, A. Yadav, and T. Jain, Applications of Mobile Ad Hoc Network: Usage of Mobile Ad Hoc Network. LAP LAMBERT Academic Publishing, 2021. [3] R. Thiagarajan, M. R. Babu, and M. Moorthi, "Quality of Service based Ad hoc On-demand Multipath Distance Vector Routing protocol in mobile ad hoc network," Journal of Ambient Intelligence and Humanized Computing, vol. 12, no. 5, pp. 4957–4965, May 2021, https://doi.org/10.1007/s12652-020-01935-x. [4] S. Soni and J. S. Shah, "QoS frameworks for Multimedia Traffic in Mobile Adhoc Networks: A Comparative Review," Engineering, Technology & Applied Science Research, vol. 7, no. 3, pp. 1708–1712, Jun. 2017, https://doi.org/10.48084/etasr.1131. [5] T.-C. Wan, "Performance Evaluation of Single-Path And Multipath MANETs Routing Protocols for Dense and Sparse Topology," International Journal of Software Engineering and Computer Systems, vol. 3, no. 1, pp. 31–42, Feb. 2017, https://doi.org/10.15282/ijsecs. 3.2017.3.0025. [6] Z. Hui, Z. Lingli, Y. Yonghang, and C. Linlin, "A Survey of Multipath Load Balancing Based on Network Stochastic Model in MANET," in 2021 23rd International Conference on Advanced Communication Technology (ICACT), PyeongChang, South Korea, Feb. 2021, pp. 336– 341, https://doi.org/10.23919/ICACT51234.2021.9370843. [7] M. A. Mahdi, A. Mahdi, M. A. G. Hazber, and M. Kachout, "Performance Evaluation of Single-Path and Multipath MANETs Routing Protocols using Random Mobility Model," International Journal of Scientific and Research Publications (IJSRP), vol. 10, no. 4, Apr. 2020, Art. no. p10040, https://doi.org/10.29322/IJSRP.10.04. 2020.p10040. [8] A. Bhardwaj and H. El-Ocla, "Multipath Routing Protocol Using Genetic Algorithm in Mobile Ad Hoc Networks," IEEE Access, vol. 8, pp. 177534–177548, 2020, https://doi.org/10.1109/ACCESS.2020. 3027043. [9] H.-H. Choi and J.-R. Lee, "Local Flooding-Based on-Demand Routing Protocol for Mobile Ad Hoc Networks," IEEE Access, vol. 7, pp. 85937– 85948, 2019, https://doi.org/10.1109/ACCESS.2019.2923837. [10] Z. Chen, W. Zhou, S. Wu, and L. Cheng, "An Adaptive on-Demand Multipath Routing Protocol With QoS Support for High-Speed MANET," IEEE Access, vol. 8, pp. 44760–44773, 2020, https://doi.org/ 10.1109/ACCESS.2020.2978582. [11] D.-G. Zhang et al., "A Multi-Path Routing Protocol Based on Link Lifetime and Energy Consumption Prediction for Mobile Edge Computing," IEEE Access, vol. 8, pp. 69058–69071, 2020, https://doi.org/10.1109/ACCESS.2020.2986078. [12] J. Jin, S. Ahn, and H. Oh, "A multipath routing protocol based on bloom filter for multi-hop wireless networks," in 2015 International Conference on Information Networking (ICOIN), Cambodia, Jan. 2015, pp. 521–522, https://doi.org/10.1109/ICOIN.2015.7057960. [13] S. A. Mostafa, A. Mustapha, A. A. Ramli, M. A. Jubair, M. H. Hassan, and A. H. Abbas, "Comparative Analysis to the Performance of Three Mobile Ad-Hoc Network Routing Protocols in Time-Critical Events of Search and Rescue Missions," in Advances in Simulation and Digital Human Modeling, Cham, 2021, pp. 117–123, https://doi.org/10.1007/ 978-3-030-51064-0_16. [14] F. T. AL-Dhief, N. Sabri, M. S. Salim, S. Fouad, and S. A. Aljunid, "MANET Routing Protocols Evaluation: AODV, DSR and DSDV Perspective," MATEC Web of Conferences, vol. 150, 2018, Art. no. 06024, https://doi.org/10.1051/matecconf/201815006024. [15] Y.-C. Hu, D. A. Maltz, and D. B. Johnson, "The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4," Internet Engineering Task Force, Request for Comments RFC 4728, Feb. 2007. https://doi.org/10.17487/RFC4728. [16] S. A. Almazok and B. Bilgehan, "A novel dynamic source routing (DSR) protocol based on minimum execution time scheduling and moth flame optimization (MET-MFO)," EURASIP Journal on Wireless Communications and Networking, vol. 2020, no. 1, Oct. 2020, Art. no. 219, https://doi.org/10.1186/s13638-020-01802-5. [17] C. E. Perkins and E. M. Royer, "Ad-hoc on-demand distance vector routing," in Proceedings WMCSA’99. Second IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, USA, Feb. 1999, pp. 90–100, https://doi.org/10.1109/MCSA.1999.749281. [18] K. Karthick and R. Asokan, "Mobility Aware Quality Enhanced Cluster Based Routing Protocol for Mobile Ad-Hoc Networks Using Hybrid Optimization Algorithm," Wireless Personal Communications, vol. 119, no. 4, pp. 3063–3087, Aug. 2021, https://doi.org/10.1007/s11277-021- 08387-2. [19] M. Zhang and P. H. J. Chong, "Performance Comparison of Flat and Cluster-Based Hierarchical Ad Hoc Routing with Entity and Group Mobility," in 2009 IEEE Wireless Communications and Networking Conference, Budapest, Hungary, Apr. 2009, pp. 1–6, https://doi.org/ 10.1109/WCNC.2009.4917894. [20] M. Jiang, J. Li, and Y. C. Tay, "Cluster based routing protocol (CBRP) functional specification (Internet-Draft)." IETF, 1998. [21] C. H. Ng and S. Boon-Hee, Queueing Modelling Fundamentals: With Applications in Communication Networks, vol. 2. Wiley, 2007.