Keywords

1 Introduction

A mobile ad hoc network (MANET) is a collection of wireless mobile nodes that dynamically forms a self-organizing network of mobile nodes. Such type of network faces challenges in terms of scalability, mobility, bandwidth limitations, and power constraints [1]. For MANET, there are three major categories for routing namely proactive (table-driven), reactive (on-demand) and hybrid (combined form of proactive and reactive) routing. The efficiency of routing mainly depends on the organization of the underlying network which can be achieved by clustering within the network which divides the network into a set of clusters either dis-joint or overlapping that saves energy and communication bandwidth in the ad-hoc networks. The clustered topology provides three basic benefits. First, a cluster structure facilitates the spatial reuse of resources to increase the system capacity. Secondly, in the routing process, the set of cluster heads forms the backbone in routing process. Also, the network is organized systematically into a set of clusters that makes an ad hoc network appear more stable [2]. In this paper we discuss a new technique of clustering using distributed spanning approach which organizes the network into a set of disjoint hierarchical clusters. Further this clustering technique will be used for an efficient hybrid routing within the network were routing within the cluster will be proactive while between the clusters will be reactive in nature.

The rest of the paper is organized as follows. Section 2 contains a brief explanation of the literature work related to clustering and routing in MANET. Section 3 of the paper is organized describes the proposed Cluster based Hybrid Routing Protocol (CBHRP) discussing the major phases of Dynamic Clustering and Hybrid routing with explained algorithm and demonstration. The simulation of the proposed protocol with experimental results is described in Sect. 4. Finally, Sect. 5 concludes the paper.

2 Related Work

Clustering in ad hoc networks provide a systematic organization of an infrastructure less network. Various clustering techniques are proposed like identifier based clustering, connectivity based clustering, mobility aware clustering, Low cost of maintenance clustering, etc. [2]. Various routing protocol for mobile ad hoc networks have been proposed in the literature like AODV, DSDV, DSR, ZRP, etc. Cluster based routing is another approach of routing in MANET. Jiang, Li and Tay proposed Cluster Based Routing Protocol (CBRP) which is used to organize network into disjoint or overlapping clusters and route the data packets efficiently in the network with the help of gateways [3]. Although the network was cluster-organized but the main demerits of CBRP occurs during routing. Due to the support for unidirectional links, there is a large routing overhead in the network. Also, the overlapping clusters increase the routing control overhead. A Distributed Weighted Cluster Based Routing Protocol was proposed [4] where cluster head selection is done according to neighbourhood table and calculates the weight of node using weight calculation algorithm. Routing procedure is same as in CBRP. In [5], Krishna et al. proposed a cluster based approach for routing in dynamic networks by forming overlapping clusters using boundary nodes. Although the network gets cluster-connected using the specified algorithm, it lacks the efficiency parameter related to the number of clusters and routing overhead. Also, for organizing the network, Distributed Spanning Tree (DST) approach is proposed in the literature [6, 7], where network is organized as a spanning tree using probing procedures by the selected nodes of the network. Being a reactive protocol, CBRP has the advantage of minimizing the sending of message by limited flooding using clustering and is better approach for large ad hoc networks. But has demerits in some issues like size of the cluster, overlapping nature of clusters and overhead due to unidirectional links within or between clusters. Also, the instability of clusters leads to the frequent re-organization which directly affects routing and network performance. In the next section, we will be eliminating the above discussed demerits of the existing cluster based routing by proposing a new technique of clustering that help in an efficient routing in the network.

3 Proposed Cluster Based Hybrid Routing Protocol

The proposed Cluster Based Hybrid Routing Protocol (CBHRP) first organizes the network into a set of disjoint hierarchical clusters by Dynamic Clustering method using Distributed Spanning Tree (DST) scheme and then perform hybrid routing for packet delivery from source to destination within the network. CBHRP has two phases, cluster formation using Dynamic Clustering and Route Discovery.

(a) Dynamic Clustering. The proposed dynamic clustering method provides a set of disjoint hierarchical clusters in the network and is based on distributed spanning tree [6] scheme that helps to maintain the network organization and improve its performance during routing. The procedure of cluster formation will start with assumptions like, each node is assigned a unique identification number, id. Each cluster is required to have a minimum number of members. The two data structures are used for maintaining the information of nodes in the network. Head Node Table (HNT): maintained by each head node and contains the information of other head nodes within its transmission range like id and distance of other head nodes, Leaf Node Table (LNT): maintained by both head and leaf nodes and stores the information of the neighbouring leaf nodes (of the same cluster) in terms of id and distance. Leaf nodes also store head node information in LNT. After the cluster formation, if there exists a cluster having lesser number of leaf nodes than required, then the cluster head merges to the nearest cluster head thus forming a sub-cluster and includes a hierarchy within the new cluster as shown in Fig. 1a and b. Such hierarchy distributes the load between cluster heads within the single cluster and minimizes the overhead of packet forwarding.

Fig. 1
figure 1

a Cluster A and Cluster B formed in a network. b Cluster B merges to Cluster A, forming hierarchy within Cluster A

Full size image

The procedure of dynamic clustering consists of the following four procedures.

  1. 1.

    Head Node Identification: To initiate dynamic clustering, each node calculates the resource status according to the number of resources (like power, etc.) left. The nodes with higher resource status than threshold consider themselves as Head nodes. These head nodes will create HNTs and will latter becomes the cluster head of their respective clusters.

  2. 2.

    Head Node Probing: Each head node initiates probing by calling HN_probe procedure, to find the leaf nodes within its range of transmission by broadcasting a HELLO packet with a minimum transmission power. After probing, head nodes wait for a specific threshold time to get replied from leaf nodes.

  3. 3.

    Leaf Node Reply: The non-head nodes within range of a head node will reply the head node whose request came earliest, with a reply message by calling LN_reply procedure. It creates LNT to maintain information of the replied head node. If a reply message is accepted, the head node creates LNT, including the details of the leaf node.

  4. 4.

    Cluster Merging, Creation and Maintenance: Each cluster is required to have a minimum cluster size, which is determined by the number of leaf nodes in a cluster. If any head fails to have it, will call merge procedure to merge with the nearby cluster head, updates its LNT and form the hierarchy. Also a new cluster is created if a node is uninitialized for a long time or if the head node of a cluster is not connected to any of the other head nodes, by calling the procedure create. For maintaining the clusters, HN_leave and LN_leave procedures are called by head and leaf nodes, respectively.

(b) Hybrid Routing. Once the network is modelled as DST based hierarchical structures, the routing procedure is initiated by the source and following steps are proposed to discover the route from the source to its destination.

  1. 1.

    The source initiates the route discovery process by generating RREQ packet containing the destination id and enters the source id in the active route list.

  2. 2.

    If the source node is a leaf node then it forwards RREQ to the respective head node and enters the head node id in the active route list, else the source node is itself the head node and proceeds to the next step.

  3. 3.

    If the present head node is not the destination, then a procedure is called by the head node to check whether the destination is one of its leaf nodes.

  4. 4.

    If the current head node finds the destination in its Leaf Node Table (LNT), then RREQ is forwarded to the destination which in response generates RREP packet containing active route list, is transmitted to its source with the reverse route of the active route list and proceed to Step 7 for the next event.

  5. 5.

    If the current head node is unable to find destination in its LNT, it then broadcasts received RREQ packet to the head nodes that are within the range as mentioned in its Head Node Table (HNT).

  6. 6.

    The head nodes receiving the broadcasted RREQ packet will execute Step 3 to check for the destination.

  7. 7.

    As RREP packet is received by the source node, the path is established according to the active route list received in RREP packet from the destination and the data packets will be transmitted accordingly. Figure 2a and b shows the path of RREQ and RREP packet between a sender and its receiver throughout the network.

    Fig. 2
    figure 2

    a RREQ path from node 10 to node 6. b RREP path via reverse route

    Full size image

Local Route Shortening: The Leaf Node Table of the leaf nodes also stores the information of their neighbouring leaf nodes (of the same cluster). It will increase the efficiency of the routing process, specifically the intra-cluster routing. If the leaf nodes of the same cluster are within the transmission range, then direct communication is possible, instead of forwarding the data to the head node.

Figure 2a and b shows the path of RREQ and RREP packet between a sender and its receiver throughout the network.

4 Experimental Results

In this section, we presented the simulation results related to the performance of dynamic clustering and its effect on routing. Compared to the existing clustering for dynamic networks [5], the proposed one have a decrement in the number of clusters with increasing degree in the network with the total number of nodes, N = 10 and 20, as shown in Fig. 3a. The topology formed after the network organization using dynamic clustering is compared to the best topology formed on the same network. Although there is a stable network organization, the average cost per path increases in the network. Figure 3b illustrates the variation in the average cost per path with the increasing number of nodes in the network.

Fig. 3
figure 3

Simulation results of dynamic clustering and hybrid routing

Full size image

Figure 3c demonstrates the variation in the average path length with increasing degree in the network of 10 nodes. Path estimation in the non-clustered network is done using flooding which determines the shortest path between the two nodes participating in the route estimation. Average path length is computed as the average of the path lengths between each source and destination in the network. The proposed clustered network has a higher average path length when compared to flooding. The routing overhead is the ratio of the path length between a source and a destination estimated by the proposed cluster based routing and the best routing using flooding algorithm, respectively. It is observed that routing overhead is lesser than 1.75 which is not high and lesser than the value evaluated by the existing clustering method [5].

5 Conclusion

We have presented a novel Cluster Based Hybrid Routing Protocol (CBHRP) comprising the features of hierarchical clustering and hybrid nature of routing. Dynamic Clustering has been proposed, forms the first phase of the proposed routing protocol which models the network into a set of disjoint hierarchical clusters using Distributed Spanning Tree (DST). Once the network is organized into clusters, the routing procedure can be employed by Route Discovery procedure forming the second phase of the protocol. The experimental results show that the proposed clustering is optimized with respect to the mobility parameter of the nodes and forms lesser number of clusters than the existing clustering method. The average path length and cost for the route estimation is higher than flooding process but the routing overhead is decreased by 12.5 % which shows an improvement during routing.