Trusted and Optimized Platform for MANET:
CACO

Sonia Deswal; Renu Dalal; Priyanka

Trusted and Optimized Platform for MANET: CACO

Sonia Deswal^1#, Renu Dalal², Priyanka³

P.G Student, Department of Computer Science, PDMCE, MD University, Haryana, India
Assistant Professor, Department of Computer Science, AIACT&R, IP University, Delhi, India
Assistant Professor, Department of Computer Science, PDMCE, MD University, Haryana, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology

Abstract

MANET (Mobile ad-hoc network) is a type of ad hoc network that can alter locations and has the ability to self configure on the fly. Because MANETs are mobile, they are having wireless connections to connect to various other mobile nodes. Therefore there is a great need of trust scheme and also an optimization technique so that shortest path can be find out between the two communicating nodes in MANET. In this paper firstly we survey some optimization techniques which find out the optimizing path between the source and the destination. And then we propose a Cuckoo Ant Colony Optimization (CACO) model. In this model the Cuckoo Search algorithm is applied in MANET to find out the most trustworthy node among all the nodes who want to join the MANET. After finding, the most trustworthy node, if any node, say source node(S), wants to send some packet to the destination node(D) then ant colony optimization technique is applied to find out the optimized path among all paths from the S to D.

Keywords

Trust Model, Optimized Path, ACO, Genetic Algorithm, Cuckoo Search

INTRODUCTION

A Mobile Ad Hoc network is a collection of wireless mobile nodes that can allow people and devices to communicate with each other without the help of any existing centralized infrastructure. And security is a major issue in Ad Hoc networks. Securing protocols for mobile ad hoc networks presents exclusive challenges due to characteristics such as lack of pre deploys infrastructure, central policy and control [1]. A MANET is a self configuring network to form an arbitrary and temporary network. Each mobile node can function as a router or host. A MANET consists of mobile platforms known as nodes, which are free to move about arbitrarily [4].

Often the topology of MANET changes as nodes are mobile. Here the routing protocol plays a major role in determining the routes required for communication between the source and the destination through the intermediate nodes. The MANET gets new attractive applications since they offer good communication in the changing environment [3]. Though MANETs are really helpful in an infrastructure less environment but it has several drawbacks as well due to its security reasons. The MANETs are more prone to security attacks when compared to the wired networks. Due to the restricted features to the MANET such as restricted protection of features of every individual node, uneven behavior of connectivity of connectivity, deficit of certification authority, centralized monitoring or administration, security is difficult to maintain in these networks. Therefore there is a great need to provide a trusted platform in MANET. In this paper Section I gives the introduction to MANET, its features, important points of MANET, and why there is a need of trusted platform in MANET. Section II describes the related research which is used in ad hoc network for providing the trust. Various models have been proposed based on optimization techniques which prevents the ad-hoc network from all attacks and different kind of malicious activity and provides the trust and secure environment in MANET. Research on the trust model in ad hoc network is presented.

Section III presents various types of optimization techniques which can be used to find out the best optimized path from the given alternative solutions providing the solution is best in all possible ways like that of cost effectiveness to attain highest possible outcome from the S to D.

Section IV discusses about the proposed trust model which provides authenticity between mobile nodes and gives trustworthy atmosphere in mobile ad- hoc network as well as provides the optimized path from S to D. This section proposes the new trust model CACO for MANET, that achieves high security level for mobile nodes and only trustworthy nodes can enter in network.

Section V concludes the work presented in this paper giving the findings and future extensions of the work.

RELATED WORK

In this section, we discuss the base idea behind the working of CACO model. Efficient Distribution of Trust Authority Functions in Tactical Networks by Steffen Reidt and Stephen D. Wolthusen. In this a scheme for the efficient distribution of a trust authority in tactical networks is developed [6]. In this distribution scheme facilitates the determination of the TA nodes under the configuration of adaptable functions, which may e.g. consider battery powers, topological location in the network, and trust relations between nodes. A Hybrid Multi-path Ant QoS Routing Algorithm for MANETs by Radwa Attia, Rawya Rizk and Mahmoud Mariee [9]. In this, the two routing algorithms were presented inspired by the ant colony optimization technique. The first one is the Hybrid Multi-Ant (HMAnt) routing algorithm which combines reactive path eastablishment with proactive path maintenance. And the second one is the HMAnt with QoS provision (HMAnt-QoS) which satisfies QoS requirements of the incoming traffic. ACTP (Authenticity Check to provide Trusted Platform) by Renu Dalal, Manju Khari and Yudhvir Singh [7]. This model takes the concept of challenge & response by using symmetric key cryptography user authentication (UA) second approach [5], in which ACTP model test the trustworthiness of each node that want to join the network and then provided the PKI certificate (X.509) to trustworthy node for showing the authenticity of node. Key Management Schemes to Achieve Trust in MANETs by Renu Dalal and Manju Khari. In this, various key management schemes like that of Symmetric Key Management, Asymmetric Key Management, Group Key Management, Hybrid or Composite Key Management Schemes are studied [15]. Survey of Trust Schemes on Ad-Hoc Network by Renu Dalal and Manju Khari [16]. In this, survey of different Trust Model Schemes of MANET with their unique features, merits and demerits is done.

Also in the MANET network, there is more than one path from the source network to the destination network to send data packets. Therefore there is great need of optimizing the path from the source node to the destination node in MANET. An Improved Location- Aware Ant Colony Optimization based routing Algorithm for MANETs by Ajit R. Bandgar and Sandeep A. Thorat [8]. In this scheme, a new routing algorithm AntHocNet-Ls was proposed which is inspired from AntHocNet for routing which rely on simple mobile agents and their collective intelligence. Mobile ad hoc network is type of self configuring network which sets up link between node and provides communication between different nodes by self organizing. There is no physical infrastructure between the communicating nodes in a mobile ad hoc network. Therefore, to provide the trust between different nodes and to make the atmosphere of MANET malicious free, new trust model CACO is proposed which not only fulfilling the need of trust between communicating nodes but also provides an optimized path from the source node to destination node to send data packets from the source node to destination node.

In Fig. 1, the various Trusted Concepts which are used to provide trustworthiness among various nodes in MANET are presented. Most of the them uses the Key Management Schemes to provide trust between nodes whose share is approx 65%. The other concepts that uses to provide trust are the optimization techniques which are used approx 10% of the total trust models. And others which includes Maturity based, Protocol based, Cluster based, System Level Based and PKI based Trust Model Scheme share 25% of the total trusted models in MANET.

OPTIMIZATION TECHNIQUES

Optimization means Finding an alternative solution with the most cost effective or the given constraints, by maximizing desired factors and minimizing undesired ones. Here maximization means trying to attain the highest or maximum result or outcome without regard to cost or expense. In computer simulation (models) of business problems, optimization is achieved usually by using linear programming techniques of operations research [10]. There are various types of optimization techniques which are used to find out the best optimal solution from the given alternative solution providing the solution is best in all possible ways like that of cost effectiveness to attain highest possible outcome.

1) Genetic algorithms

The genetic algorithm was adopted from biological systems’ improved fitness through evolution (natural evolution) and was introduced by John Holland. Genetic algorithms work with a random population of solutions (chromosomes) [2].

The features of natural evolution are as follows:-

a) An individual’s characteristics are encoded on a chromosome.

b) According to the environment, each chromosome has certain fitness in which it exists.

c) Only the stronger individuals can survive and produce the off springs [1].

Four main parameters affect the performance of GAs:

ÃÂ¯ÃâÃÂ· Population size,

ÃÂ¯ÃâÃÂ· Number of generations,

ÃÂ¯ÃâÃÂ· Cross over rate, and

ÃÂ¯ÃâÃÂ· Mutation rate.

Larger population size (i.e. hundreds of chromosomes) and large number of generations (thousands) increase the likelihood of obtaining a global optimum solution, but substantially increase processing time [2].

Use of steps of genetic algorithm:-

a) Initial Population: Random population of n chromosomes is generated (suitable solution for the problem.

b) Fitness: The fitness function f(x) in the population of each chromosome is evaluated. According to the fitness function of each chromosome is selected. Each chromosomes fitness function can be designed as a 2-D function.

2) Ant Colony Optimization

ACO was developed by Dorigo. The ACO metaheuristic is based on generic problem representation and the definition of the ant’s behavior. ACO adopts the foraging behavior of real ants. When multiple paths are available from nest to food, ants do random walk initially [4]. During their trip to food as well as their return trip to nest, they lay a chemical substance called pheromone, which serves as a route mark that the ants have taken. Subsequently, the newer ants will take a path which has higher pheromone concentration and also will reinforce the path they have taken. As a result of this autocatalytic effect, the solution emerges rapidly [14].

3) Particle Swarm Optimization

PSO was developed by Kennedy and Eberhart [3]. The PSO is inspired by the flocks’ social behavior of migrating swarm birds in search of food. In PSO, each solution is a ‘bird’ in the flock and is referred to as a ‘particle’ [2]. Each particle is moved in the swarm by adding a velocity with its position towards the optimal point [3]. The process is initialized with a group of random particles (which we can also say solutions), N. the birds in the population only evolve their social behavior and accordingly their movement towards a destination. This mimics a flock of birds that communicate together as they fly. Each bird looks in a specific direction, and then when communicating together, they identify the bird that is in the best location. Accordingly, each bird speeds towards the best bird using a velocity that depends on its current position. Each bird, then, investigates the search space from its new local position, and the process repeats until the flock reaches a desired destination [12]. Throughout the process, each particle i monitors three values: its current position (Xi); the best position it reached in previous cycles (Pi); its flying velocity (Vi).

These three values are represented as follows:

Current position Xi = (Xi1,Xi2,…..Xis) (1)

Best previous position Pi = (Pi1,Pi2,….Pis) (2)

Flying velocity Vi = (Vi1,Vi2,…..Vis) (3)

4) Simulated Annealing Algorithm

Simulated Annealing (SA) is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete. For certain problems, simulated annealing may be more efficient than exhaustive enumeration- provided that the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution. The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. Both are attributes of the material that depend on its thermodynamic free energy. Heating and cooling the material affects both the temperature and the thermodynamic free energy [17].

5) Hill Climbing Technique

Hill Climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution. If the change produces a better solution, an incremental change is made to the new solution, repeating until no further improvements can be found.

Hill climbing is good for finding a local optimum (a solution that cannot be improved by considering a neighboring configuration) but it is not guaranteed to find the best possible solution (the global optimum) out of all possible solutions (the search space). The relative simplicity of the algorithm makes it a popular first choice amongst optimizing algorithms. it can return a valid solution even if it's interrupted at any time before it ends [18].

6) Cuckoo search algorithm

Cuckoo search (CS) is an optimization algorithm developed by Xin-she Yang and Suash Deb in 2009. It was inspired by the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of other birds (host birds of other species) [11]. Some host birds can engage direct conflict with the intruding cuckoos [13].

Cuckoo search (CS) uses the following representations:

Each egg in a nest represents a solution, and a cuckoo egg represents a new solution. The aim is to use the new and potentially better solutions (cuckoos) to replace a not-so-good solution in the nests.

PROPOSED WORK

MANET is a type of ad hoc network that can alter locations and has the ability to self configure on the fly. Because MANETS are mobile, they use wireless connections to connect to various networks.

Block diagram of CACO

In an ad-hoc network, routing decisions and resource management work is done in a distributed way only because of the presence an unadministered infrastructure less network. It is a peer-to-peer wireless network where nodes can communicate with each other, without the use of infrastructure such as access points or base stations. Nodes can join and leave the network at anytime and are free to move randomly and organize themselves arbitrarily. In MANETs, each node should not only work for itself, but should be cooperative with other nodes. To maintain the trust and to optimize the path between the source node to the destination node in the network, the new trust model for mobile ad-hoc network is proposed

Flow diagram of CACO Model

Explanation of Proposed Model(CACO)

This model uses the cuckoo search optimization technique to check the most trustworthy node among all the nodes who want to join the network and then allow only the most trustworthy node to join the network (NW1).

Node selection using cuckoo search

All nodes who want to join the mobile ad-hoc network send a request to the cuckoo. Then the cuckoo based on its functionality gives a challenge to all the nodes who want to join the network and all nodes gives response to Cuckoo. According to response of all nodes, cuckoo find out the best node among all the nodes and allow only that node to enter into the network.

Furthermore in MANET, routing is a difficult problem because of some characteristics of the network like that of traffic load and network topology changes rapidly. This type of distributed nature of routing in an mobile ad-hoc network highly resembles with the multi agent nature of ACO. The given ad-hoc network can be considered as a construction graph, the vertices are the routers and the links between them can be considered as the connectivity between the routers. Now the network route finding is just finding the shortest path among all the paths available from the source node to the destination node.

Working of the CACO Model

Step 1:- Initially network NW 1 is empty as there were no node.

Step 2:- The nodes who want to join the network, Cuckoo will test the authenticity of all nodes by giving a random challenge to them.

(a) Authenticity check of all nodes using cuckoo search.

(b)Working of cuckoo search is shown in figure below:

(1) All nodes who want to join the network send their identity to cuckoo.

(2) Cuckoo generates a random challenge for all nodes by sending a nonce, Rb, in plain text.

(3) Nodes respond to this message by sending back nonce and encrypting it.

Step 3:- Cuckoo found out the most suitable (best node) and permit it to enter it into the network.

Step 4:- All other nodes are rejected and stored in DBMN.

Step 5:- After joining the network, now the node actively participated in the network and can send and receive data from all other nodes in the network.

Step 6:- Now if any node, say S node, wants to send some data to the D node, then an ant colony optimization technique is applied to find the shortest path from the S node to the D node.

Working of ant colony optimization

(Data structure & Notations)

NS= Source Node, Dpkct= Dummy Packet, ACKpkct= Acknowledgement Packet, Sr= Successful Response Rate, Pc= Pheromone Calculation, Sr_count_i= increment Sr_count, Sr_count_d= decrement Sr_count.

Step 7:- NS calculates hash of Dpkct, and saves it in its memory, appends Destination node-ID and its immediate neighbor’s list and then send the Dpkct to b its immediate neighbor.

Step 8:- All immediate neighbors receives Dpkct and checks Destination node-ID.

(a) If the Destination node-ID does not matches the ID of one of the neighbors then they sends an acknowledgement to the NS (The NS upon getting the ACKpkct, de-attaches hash and compare it with value of hash previously saved. If a match is found then sets Sr=1, increments Sr_count by 1 in its pheromone list and calculates PC using below eq. 8) and forwards the Dpkct to their respective Neighbours and the same process continues until the destination node reaches.

(b) If any of the neighbor node does not sends an ACKpkct even after getting the Dpkct within a stipulated time, then the NS mark it as the selfish node and does not include it into its pheromone list.

(c) Step 9:- If the Destination node-ID matches the ID of one of the neighbors then that node will sends a hello message “ I am the destination” to the source and stop.

Pheromone Calculation

PC= (Sr*Sr_count_i)+((1-Sr)*Sr_count_d) (8)

MANUAL RESULTS OF CACO MODEL BY WORKING EXAMPLE

NW.1 is made up of different nodes in which nodes are trustworthy or we may say authentic.

Assume the following terms:

Nodes who want to join the network = N5, N6, N7.

Now Cuckoo will find out which node is the best node among all the requesting nodes by giving a random challenge to all nodes. The node which gives the response in lesser time among all nodes will assumed to be the best node by Cuckoo. The time after which each node gives response to Cuckoo is shown in following table:-

It is found that the node N5 gives response in lesser time among all nodes and therefore node N5 is allowed to enter into the network.

Here, NW.2 constructing with N1, N2, N3, N4, N5 nodes as shown in above figure. After random period say node N1 (source node) wants to send some data to node N3 (destination node). The source node firstly send a dummy data packet to all its neighbours to find out the shortest path.

The source node N1 attaches source ID and Destination ID to its dummy data packet and send to its neighbors. If the destination ID matches the Id of the neighbor then the neighbor node sends a message to the source “I am the destination”. Otherwise sends an acknowledgment packet to the source (the source node adds this neighbor node in its pheromone count) and forwards the dummy data packet to its neighbors and this process continues until the destination reaches.

In the above example, the source node N1 sends dummy data packet to its neighbor N2, and since it is not the destination node, it forwards the dummy data packet to its neighbors i.e., N4. Again this is also not the destination node, therefore it also forwards the dummy data packet to its neighbors i.e., N3 and N5. Now the destination node is reached and therefore it sends a reply message to the source “I am the destination node”. While the node N5 again forwards the dummy data packet to its neighbors i.e.,N3. And hence through this path also the source node also send the data. Therefore there are two paths from the source node and the destination node. These are as follows :-

Path1: N1- N2- N4- N3

Path2: N1-N2- N4- N5- N3

But we need the shortest path from the source node to the destination node and using the pheromone list node N1 found that the Path1 is the shortest path.

COMPARISON OF CACO MODEL WITH OTHER OPTIMIZATION PATH ALGORITHMS (MODELS) IN MANET

CONCLUSION AND FUTURE WORK

As we all know that MANET is very prone to security attacks due to its various functionalities. In this paper study of different optimization techniques is done. Some of them are used in MANET to provide trusted platform. In this paper we studied some optimization techniques and also compare them with our proposed model. we use two optimization techniques and proposes a new trust model CACO (which rejects the entry of not much suitable nodes to enter them in the mobile ad-hoc network and make it more secure) and concludes that the proposed model is the best model among all trusted model as it works on two phases. Manual results are shown in Section V. Now the implementation of the proposed algorithm can be done on any simulator like NS2, OPNET or MATLAB and its result can be analyzed to know the efficiency of the CACO model. Comparison study of simulated output of CACO trust model with other existing trust models is another task to do.

References

Kumar Nikhil, Swati Agarwal and Pankaj Sharma, “Application Of Genetic Algorithm In Designing A Security Model For Mobile Ad-hoc Network”, CS&IT-CSCP, DOI: 10.512/csit.2012.2116, 2012.
Emad Elbeltagi, Tarek Hegazy and Donald Grierson, “Comparison among five evolutionary-based optimization algorithms”, Advanced Engineering Informatics, January 19, 2005.
B.Nancharaiah and B.Chandra Mohan, “MANET link Performance using Ant Colony Optimization and Particle Swarm Optimization Algorithms”, International Conference on Communication and Signal Processing, April 3-5, 2013.
Bibhash Roy, Suman Banik, Parthi Dey, Sugata Sanyal and Nabendu Chaki, “Ant Colony based Routing for Mobile Ad-Hoc Networks towards Improved Quality of Services”, 2011
Wallner, D. M., Harder, E. J., and Agee, R. C., ‘Key Management for Multicast: Issues and architectures ’. Internet Draft, draft-wallner-key-arch- 01.txt, 1998.
Steffen Reidt and Stephen D. Wolthusen, "Efficient Distribution of Trust Authority Functions in Tactical Networks," 2007.
Renu Dalal, Manju Khari and Yudhvir Singh, “Authenticity Check to provide Trusted Platform in MANET (ACTP)”, 2nd International Conference on Communication, Computing & Security (ICCCS-2012), October 6-8,Odisha, India, Procedia Tecnology, Elsevier, 2012.
Ajit R. Bandgar and Sandeep A. Thorat, “An Improved Location- Aware Ant Colony Optimization based routing Algorithm for MANETs”, 4th ICCCNT, July 4-6, 2013.
Radwa Attia, Rawya Rizk and Mahmoud Mariee, “A Hybrid Multi-path Ant QoS Routing Algorithm for MANETs”, IEEE, 2009.
John Papandriopoulos, Subhrakanti Dey and Jamie S. Evans, “Distributed Cross-Layer Optimization of MANETs in Composite Fading”, IEEE ICC proceedings,2006.
Xin-She Yang and Suash Deb, “Cuckoo Search via L´evy Flights”, World Congress on Nature & Biologically Inspired Computing (NaBIC 2009), December 2009, India. IEEE Publications, USA, pp. 210-214, 2009.
Tarun Varshney, Aishwary Katiyar and Pankaj Sharma, “Performance Improvement of MANET under DSR Protocol using Swarm Optimization”, IEEE, 2014.
Ehsan Valian, Shahram Mohanna and Saeed Tavakoli, “Improved Cuckoo Search Algorithm for Global Optimization, International Journal of Communications and Information Technology, IJCIT, Dec. 2011.
Suparna Biswas, Priyanka Dey and Sarmistha Neogy, “Trusted Checkpointing Based on Ant Colony Optimization in MANET”, Third International Conference on Emerging Applications of Inforamtion Technology (EAIT), 2012.
Renu Dalal and Manju Khari, “ A Review on Key Management Schemes to Acheieve Trust in MANETs”, International Journal of Wireless & Mobile Networks (IJWMN), 2012.
Renu Dalal and Manju Khari, “Survey of Trust Schemes on Ad-Hoc Network”, Institute for Computer Sciences, Social Informatics and Telecommunications Engineering 2012, Springer, CCSIT 2012, Part I, LNICST 84, pp. 170–180, 2012
Sanghamitra Bandyopadhyay, Sriparna Saha, Ujjawal Maulik and Kalyanmoy Deb, “A Simulated Annealing- Based Multiobjective Optimization Algorithm: AMOSA”, IEEE Transactions on Evolutionary Computation, Vol. 12, No. 3, June 2008.
Wang.H, Wang.D and Yang.S, “A Memetic Algorithm With Adaptive Hill Climbing Strategy for Dynamic Optimization Problems”, Springer, 2009.