Keywords

1 Introduction

Nowadays, the development of mobile technology applications such as web browsing, online banking, online gaming and social media, has stimulated the wide spread usage of wireless network. Therefore, wireless networks have become almost a necessity and a vital component of contemporary daily life.

In telecommunication field, networks can be classified in two categories. The first category is wired networks, which rely on physical links such as wires and optical fibers. The second category is wireless networks, which use radio transmission techniques to establish links between nodes. In addition, wireless networks can be split into two classes, as presented in Fig. 1, Infrastructure based wireless networks, which use fixed access points as gateways between wired and wireless area. For example, cellular networks (2G, 3G, and LTE), WiFi (IEEE 802.11), WiMax (IEEE 802.16) and infrastructure less networks broadly known as Ad Hoc networks do not rely on any pre-established infrastructure consequently Ad Hoc networks are self-organized, self-configured and self-administered. Furthermore, Ad Hoc Networks are single-hop like Bluetooth or multi-hop like Wireless Sensor Networks (WSN), Wireless Mesh Network (WMN) and Mobile Ad Hoc Network (MANET). In the following paragraphs will focus on routing in Mobile Ad Hoc Network [1].

Fig. 1.
figure 1

Network categories.

Full size image

Ad Hoc networking is a multi-level issue because of its autonomous operations; hence network layer should adapt its routing operations to several network constraints, such as nodes mobility, nodes Energy, scarce bandwidth and network size to establish efficient paths for data communication. In this context, many routing protocols has been designed in order to deal with different constraints and guarantee the quality of service required by mobile Ad Hoc network applications [2].

In the flowing, we will present a brief history and different issues in the design of mobile Ad Hoc routing protocols. In Sect. 3, we are going to present taxonomy of routing protocol in both wired network and Mobile Ad Hoc network in order to give a deep understanding of different strategies used in designing routing protocols and gain the proper knowledge about MANET routing protocols.

2 History and Challenges

2.1 Brief History

Back to 1972, the first Ad Hoc network generation called: Packet Radio Network (PRNET) was used by, The Defense Advanced Research Project Agency (DARPA), as trial to provide networking facilities in combat environment. Mainly, PRNET uses the combination of Areal Location of Hazardous Atmospheres (ALOHA) and Carrier Sense Multiple Access (CSMA) for multiple access and distance vector routing.

The second generation emerged in 1980, when PRNET was integrated into the Survival Adaptive Radio Networks (SURAN) project. This provided an infrastructure less packet switched network to the mobile battlefield. SURAN significantly improved upon the radios by making them smaller, cheaper, with scalability of algorithms, and more resilience to electronic attacks.

In the 1990s, Mobile devices like laptops, notebooks, PDAs and Software development became widely available for an easy interconnection of computers. At that time, commercial need for mobile interconnection has triggered the interest of several companies; therefore, the Institute of Electrical and Electronics Engineers (IEEE) established a subcommittee, IEEE802.11, to standardize technologies to be used for wireless Local Area Networks WLANs. Since the subcommittee was established involving experts to address the need of both infrastructure based and infrastructure less based communications [1,2,3].

2.2 Networking Challenges

Mobile Ad Hoc network is a set of smart mobile nodes, which form a dynamic and autonomous system. In mobile Ad Hoc networks, each node within the network has the ability to change its location and configure itself on the fly. These nodes are able to establish routes, anywhere and anytime, between a pair of source and destination using routing protocols. In addition, routes are generally multi-hop due to limited transmission range of mobile nodes, so routing protocols must be able to route data packets through intermediate nodes until reaching targeted destination [4].

In addition, nodes mobility, bandwidth-constrained, energy-constrained, and limited security of shared medium of Mobile Ad Hoc network make designing process of routing protocols most important and difficult instead of design process in fixed network. Due to the dynamic nature of mobile nodes, MANET experiences frequent link failures, which cause frequent network topology change, this has led to the design of various routing protocols. The purpose of each protocol is to solve problems for a specific MANET topology condition; therefore, the designer should have a prior knowledge about the condition or the context of the network targeted with routing protocol design. Therefore, different routing protocols perform differently with different networks’ conditions such as level of mobility, size of the network in terms of connected nodes number or type of packets being routed through the network.

3 Taxonomy of Routing Protocols

The main function of routing in networking world is to make possible the transfer of information and communication between two parties whether in wired or wireless networks.

3.1 Routing in Wired Network

There are two main and commonly used routing protocols for wired networks namely: distance vector and link state algorithms as shown in Fig. 2.

Fig. 2.
figure 2

Wired Routing

Full size image

3.1.1 Distance Victor Routing

In distance victor routing (DVR), which is commonly known as Bellman Ford Algorithm, route computing between the source and destination is accomplished using different metrics such as number of hop, queue length and delay. Each router maintains a routing table or vector indicating the best known distance to each destination and which route to use to get there. Every neighboring router exchanges the necessary information with each other to keep these tables updated. The main disadvantages of Distance Vector routing protocol are loops and count-to-infinity problems. The best known DVR protocol is Routing Information Protocol (RIP) which solves the issue of count to infinity by introducing the maximum hop count of 16 and looping issue by Time to Live (TTL) [5].

3.1.2 Link State Routing

Link state routing (LSR) has been developed to overcome DVR drawback. It use Dijkstra’s algorithm to calculate the shortest path. Routing operation consist of a periodic flooding of link state information through the network to update the current status of links. In case of any topology change a notification will be flooded throughout the entire network to re-compute new routes and update topology information. The main routing protocols in this category are Open Short path First (OSPF) and Intermediate System to Intermediate System (ISIS) [5].

3.2 Routing in Wireless Ad Hoc Network

The main building bloc in Ad Hoc networking is routing. Therefore, designing routing protocols have attracted the interest of researchers. Since several routing protocols have been proposed in order to meet required functionalities related to a specific application field. As a result, there is no routing protocol that could fit to all Ad Hoc networking contexts [6, 7]. Routing protocols can be classified using several approaches, depending of the purpose or the goal for which the protocol is designed. See illustration in Fig. 3. There are different criteria for classifying routing protocols in ad hoc networks:

Fig. 3.
figure 3

Routing classification

Full size image

  • Communication Model

  • Network structure

  • Scheduling model

  • State Information

  • Route establishment

  • Type of Cast

  • Type of path

3.3 Communication Model

Routing protocols can be designed to work on different wireless communication schemes. Wireless communication models can be single channel or multi-channel [8]. Firstly, single channel schemes were designed for Medium Access Control (MAC) to address physical layer deficiencies and provide reliable information to upper layers, these schemes suffer from hidden and exposed terminal problems, as illustrated in Fig. 4, fairness and power consumption issues related to radio communication in mobile ad hoc networks. Most of designed protocols have partially solved the intrinsic problems of wireless communication. On the other hand, multichannel schemes have shown better capabilities to handle the hidden and exposed terminal problems due to the usage of more than one channel in their network. Multichannel protocols are generally used in Time Division Multiple Access (TDMA) or Carrier Sense Multiple Access (CSMA) based networks. In contrast, single channel are Carrier Sense Multiple Access with Collision Avoidance (CSMA-CA) scheme based.

Fig. 4.
figure 4

Hidden and exposed terminal problems

Full size image

3.4 Network Structure

Depending on how nodes participate in routing task, routing protocols can be flat or hierarchical [6, 7, 9]. In flat protocols, all nodes have the same responsibilities in the entire routing process. Hence, routing control messages are globally managed in a uniform manner, which cause scalability problem in large networks. For example, Destination sequenced Distance Victor (DSDV) and Ad Hoc On demand Distance Victor (AODV). In hierarchical protocols, the main concern is reducing routing control messages in order to scale to large networks. For example, Zone-based Hierarchical Link State (ZHLS). Thus, nodes are dynamically organized into clusters. In hierarchical scheme, only cluster head nodes know the topology information. Other nodes just send data to these cluster head nodes, which in turn will execute the entire routing process such as finding optimal path to the destination.

3.5 Scheduling Model

In the literature, most routing protocol classification in Ad Hoc network are based on their route establishment and maintenance strategies [2, 10,11,12]. Routing protocol is considered proactive or table-driven if nodes maintain route information all the time to all destinations. Thus, when a source node has data to send it looks up its routing information data base and start immediately sending data to the destination, which guaranty lower transmission delay. The drawback of proactive routing is periodic routing table updates, which cause routing overhead problem. In reactive or on demand routing protocols, like AODV, route information is acquired and maintained only when a source has data traffic to send. Generally, reactive protocols have two main operations: the first operation is route discovery, which is initiated when a source needs a route to a destination. The second operation is route maintenance, which consists of repairing failed links through active route due to topology changes.

3.6 State Information

Routing protocols may be described in terms of the state information acquired at each node. Two main categories are distinguished: topology based protocols and destination based protocols that are broadly used in traditional wired routing protocols. In topology-based protocols, nodes maintain global view of network topology [13]. This approach is known as link State, where link sate packets (LSP) are exchanged between the whole network’s nodes. Every node constructs and maintains a global network topology from the LSPs it receives, and computes the best routes to all other nodes using Dijkstra’s algorithm. In destination based protocols nodes do not maintain large scale topology information. The main destination based protocols are Distance victor where every node periodically exchanges distance vector with its neighbors. When a node receives distance vector information from its neighbors, it computes new routes and updates its distance vector database. The complete path then established, in a distributed scheme, by combining the next hop of nodes on the path from the source to the destination. Distance vector routing protocols have less computational complexity and message overhead.

3.7 Route Establishment

Routing protocols can be distinguished according the way a data packet is forwarded from the source to the destination. There are two approaches [1, 2]: First, source routing protocols, such as Dynamic Source Routing (DSR), which place the entire route information in the packet header then intermediate nodes only forward the packet according to route information stored in the header. In this approach intermediate nodes do not need to compute and maintain updated routing information, as a result much less time is needed for traffic delivery and much less control traffic is generated. However, Source routing do not scale very well in large network and dynamic topology, especially when the route is long, data packet header become large and consume too much of scarce bandwidth. Second approach is hop by hop, which use next hop information stored at each node involved into an active path, like OLSR. Thus, when a node receive a packet, it lookup the routing table and forward the packet to the next hop. The advantage of this strategy is that routes are adaptable to the dynamically changing environment. The drawback of hop-by-hop routing is that each intermediate node has to maintain routing information for each active route and each node may require being aware of their surrounding neighbors through the use of beaconing messages.

3.8 Type of Cast

Routing protocols can be classified depending on their type of cast. For example: OLSR, AODV and DSDV. Unicast Routing Protocol is the most developed for MANET applications. In the unicast routing one separate copy is sent to each receiver from the source node. Thus, data packet is replicated at the source node and then delivered to each destination node; see Fig. 5a. Unicast process consumes more much bandwidth due to redundant data packets. Multicast routing protocol, like on demand Multicast Routing Protocol (OMRP), has become very important in multimedia communications. To send simultaneously the same data packet to multiple receivers, the simplest way is broadcasting. However, broadcast consumes considerable bandwidth and power, which should be avoided as much as possible in mobile Ad Hoc networks due to scarce bandwidth and limited nodes’ energy. In Multicast process, the network replicates data packet instead of replicating by source node in Unicast process, which lead to optimal use of scarce bandwidth. See Fig. 5b.

Fig. 5.
figure 5

Types of cast

Full size image

Another type of routing protocols is geo-cast routing protocols illustrated in Fig. 5c. This routing scheme has been adopted in VANET routing; it consists of sending data packet to a set of nodes inside a specific geographical area [13, 14].

3.9 Type of Path

Some routing protocols are able to find multiple paths to a destination, like Multipath Ad hoc on demand Distance Victor protocol (AODVM), which make routing efficient in case of frequent links break due to nodes mobility. In contrast, others routing protocols are simple and find only one path to a destination. Single path routing protocols should re-compute new route each time a link failure is detected which become more complicated in highly dynamic environment [15].

4 Conclusion

In this paper, we highlight different challenges that researchers are facing in designing Mobile Ad Hoc routing protocols, such as high node mobility and hence dynamic topology, restricted bandwidth and limited energy. Furthermore, we present taxonomy of routing protocols to understand different strategies that could be flowed to develop a routing protocol according to specific network context. In next phase, we are going to review common routing protocols and discuss their advantages and disadvantages in a highly dynamic network.