University Home
Ramaiah University of Applied Sciences Home Research

Design and Analysis of a Cluster-Based Hybrid Routing Protocol for Enhanced Quality-Of-Service in Mobile Ad-Hoc Networks

Author

  • Kaustubh Uday Nabar

    FET

    Faculty of Engineering and Technology

Abstract

This thesis presents design and development of a Cluster-based Hybrid routing protocol (CHLS-ACO) to address the problem of routing and provide enhanced Quality-of-Service (QoS) in MANETs. The development of CHLS-ACO is realised in three steps: (a) Clustering the nodes (b) Inter-connecting the developed clusters and © Incorporating the hybrid routing pattern.
CHLS-ACO addresses the conventional greedy clustering heuristics in MANET by implementing a non-greedy and Affinity Propagation-driven approach to cluster the nodes. Based on the proposed clustering approach, two new clustering algorithms namely MWC-AP (with multiple weighted clustering as the proximity criteria) and GMM-APD (with mobility as the proximity criteria) are proposed. The clustering procedure of MWC-AP and GMM-APD is based on the evolution of the network topology. The Cluster Head (CH) selection decisions are related to the posterior log probability value of the node. To comprehend the inherent dynamics of MWC-AP and GMM-APD, an analytical theory describing various events occurring on the timeline of node and cluster is presented. An objective function for the proposed clustering approach is formulated in terms of integer linear programming focussing on improving the cluster stability and cost. The relative performance enhancement shown by MWC-AP and GMM-APD with respect to some existing clustering algorithms is 13% — 110% (cluster stability), 4% — 88% (cluster quality) and 2% — 25% (cluster cost).
To realise inter-cluster communication, the clusters developed by MWC-AP/GMM-APD are connected using a novel Collaborative Gateway Selection Algorithm (CGSA-QoS). Through a collaboration between neighbouring CHs, the CGSA-QoS algorithm generates a minimum gateway set to interconnect the clusters. It also ensures energy and bandwidth efficiency during inter-cluster communication. The results reveal that, relative to some existing gateway selection schemes, CGSA-QoS inter-connects the clusters with approximately 27% less number of gateways and incurs about 33% — 37% less control overhead. In terms of longevity of gateways, CGSA-QoS manifests 16% — 34% enhanced performance. When node transmission range is greater than 100 m, CGSA-QoS manifests 17% — 26% bandwidth efficiency during inter-cluster communication.
In the inter-connected clustered network, CHLS-ACO employs a novel hybrid routing paradigm consisting of link state heuristics and Ant Colony Optimisation (ACO) meta-heuristics. With reference to each source node, CHLS-ACO segregates the connected clustered network into Intra-Cluster Region (ICR), Neighbour Inter-Cluster Region (NICR) and Distant Inter-Cluster Region (DICR). CHLS-ACO implements the link state approach to discover routes to the destination node in ICR and NICR, whereas ACO meta-heuristics are used for path discovery in DICR. The relative performance improvement shown by CHLS-ACO as compared to some existing routing protocols is 38% (routing overhead), 17% (throughput) and 70% (delay) and consequently helps to address the the routing problem. Lastly, the applicability of CHLS-ACO is examined in a symbiotic network architecture in which the MANET acts as a relay and implements CHLS-ACO to transmit data from the sensor network to the end user via the internet. The results reveal that CHLS-ACO delivers data to the user at a packet delivery of about 92% and at a response time of approximately 0.55 s.

Conclusion:
7.3. Original Contributions of the Thesis
The following are the original contributions of this thesis whose emphasis is on the design and development of a cluster-based hybrid routing protocol.

1. Clustering Procedure

  1. 1. Analysis and simulative studies on data clustering algorithms using the default Euclidean distance as the proximity criteria as well as MANET-based proximity criteria.
  2. 2. Proposition of a novel AP-driven distributed, non-greedy and network evolution-based clustering procedure in MANETs. 
  3. 3. Presentation of an analytical model to explain the intrinsic dynamics of the clustering procedure based on the events occurring on timeline of nodes and clusters.
  4. 4. Formulation of an objective function in terms of ILP to categorically explain the proposed clustering procedure.

2. Gateway selection procedure

  1. 1. An innovative gateway selection algorithm (CGSA-QoS) in which neighbouring CHs cooperate with each other to select the gateways considering QoS metrics is proposed.

3. Routing procedure

  1. A new cluster-based hybrid routing protocol (CHLS-ACO) is proposed in this thesis which implements a combination of heuristics and meta-heuristics using two different techniques namely: the link state approach and the ACO. 
  2. A novel pheromone model that calculates pheromone on each link considering the RPP value of that path.

4. Symbiotic network scenario

  1. 1. A symbiotic network architecture consisting of an alliance of WSN, MANET and Internet. The application of the proposed symbiotic network can be found in a real life scenario.