A secure and energy efficient ant routing algorithm

Abstract

In Mobile Ad hoc Networks (MANETs), setting up an ideal and proficient route linking the conveying bodies is the essential objective of the routing protocols. But any assault during the routing stage may upset the communication, paralyzing the whole network. So, providing security in routing for a protected communication between nodes has become a prime concern. In the present study, we propose a Secure Energy Efficient Ant Routing Algorithm (SEEARA) based on Ant Colony Optimization (ACO) algorithm and cryptographic primitives that exercises on power control and secure routing between a pair of network nodes and increases the performance and longevity of the network. Also, it can be realized during simulation studies that SEEARA shows a better solution in comparison with the previously proposed routing protocols.

Keywords

ACO MANET power control secure routing trust

1. Introduction

In recent years, a substantial evolution in the sphere of wireless communication in MANET has been noticed. Still the energy constrained behaviour of the wireless mobile nodes imposes many restrictions during the design and implementation of MANET routing protocols. To find an optimum and cost-effective path linking the sender and receiver nodes is the main aim of routing protocols which may deplete the energy of the participating nodes. Moreover, repeated data transmission through the same path causes huge power drainage which further adversely affects the network lifetime. Several energy aware routing schemes [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] are proposed in the literature. The Minimum Total Transmission Power Routing (MTPR) [1] computes the total power needed for transmission of packet through various paths and finally chooses the one with minimum power required, but the remaining power with nodes is not taken into consideration, which may lead to destruction of some nodes in the path resulting in path failure. Min-Max Battery Cost Routing (MMBCR) [2] computes the power of each node in a path and selects the minimum power nodes in each path. Then the path having the node with maximum battery power among these minimum powered nodes is selected. MMBCR extends lifetime of a network by choosing residual battery of a node but neglects the consumption factor and total transmission energy. The Conditional Max-Min Battery Capacity Routing (CMMBCR) [3] combines both the factors total transmission energy and residual energy of nodes under consideration. MTPR is applicable when all the participating nodes are above the threshold value fixed for battery protection, otherwise MMBCR is used. Minimum Drain Rate (MDR) [4] uses a metric called drain rate, which is computed as a ratio of residual battery power to average energy consumption rate of a node considering the ongoing traffic conditions. The path with minimum drain rate and minimize battery power is chosen.

On the other hand, MANET communication completely relies on the wireless links which suffer from contention affected from radio signals (e.g., noise, fading and interference). These links possess less bandwidth compared to the conventional wired networks. MANET is available to both genuine users and spiteful attackers. It becomes more vulnerable due to the lack of traffic monitoring and access control mechanism where MANET relies on the implicit trust relationship between the nodes involved to route packets [11]. In MANET, packets are broadcasted leading to a risk of snooping or interfering. Due to the limitation of resource cryptographic schemes that require larger computations may fail to be implemented as a result of which it is easily accessible to the external attackers [12]. Further a compromised node may be used for launching an internal attack. Threats also increase when MANET packets are transferred over multiple paths instead of a single path and suffers from many attacks like hole attack impersonation or spoofing, Denial of Service, byzantine, rushing attacks, etc. [11, 13] Unauthorized and compromised nodes may collapse the network communication entirely or partially by advertising incorrect paths, dropping packets or draining battery power of nodes.

Hence, routing in MANET becomes more challenging and requires the development of an adaptive, power aware, secure and efficient routing algorithm to avoid a complete breakdown of the network.

The adaptive and dynamic nature of ACO based algorithms makes it suitable to solve the complex problems during routing. This is a heuristic method as it builds a solution and its representation affects all ants present in the network. The probabilistic movement made by the ants within the system enables them to investigate new paths as well as to re-investigate the earlier traversed paths. The quality of the pheromone accumulation governs the artificial ants to move towards the optimum path, and its dispersion enables the system to overlook the old information and keep away from the quick convergence to the suboptimal solution. This behaviour of ACO motivates us to design the protocol using ACO metaheuristics.

ACO techniques in intelligent routing focus on exploring the use of searching techniques into the untouched areas of network (exploration) thereby using the past search results (exploitation) for getting optimal path from source to destination. In artificial ants, the exploitation leads to the reinforcement, but also sometimes may result in premature convergence. So, to handle this situation, randomization techniques may be used by the artificial ants while taking a decision [14, 15]. In ACO, a group of artificial ants combinedly works to construct a solution to an optimization problem based on the communication behavior as adopted by the real ants. An optimal path is chosen based on the pheromone concentration on that path. ACO is a heuristic method to build a solution and its representation affects all ants present in the network [16]. ACO provides better solutions than Genetic Algorithm (GA) and Simulated Annealing (SA) [17] for choosing a shortest path. ACO [18] based routing uses artificial ants, which are nothing but the control packets for collecting information about the path while moving from source node to destination node and use this collected information while moving from destination node to source node. Each node maintains a routing table with a list of entries for each neighbor node. The entries represent the pheromone values with certain variables and help in choosing neighbor goodness over others. Finally, multiple paths can be found, and the optimal path is chosen based upon the pheromone context.

Many secure routing protocols have been proposed by the researchers based on ACO algorithms to provide an optimized route discovery mechanism along with other features like battery optimization and quality of service; some of them are discussed in the literature survey. Still the challenge of designing an adaptive, power aware, secure and efficient routing protocol remains unsolvable as none of the proposed protocols are compliant with the dynamic environment of MANETs. We have proposed an algorithm, termed as Secure Energy Efficient Ant Routing Algorithm (SEEARA) that computes optimal, trustworthy and energy efficient, secure routes for MANETs. Lightweight cryptographic schemes (lightweight MAC, pair-wise key) are used to ensure a secure end-to-end delivery of packets in the network. A trust value is associated with every node to monitor their malicious behavior.

Rest of the paper is organized as follows. In Section 2 we have discussed about some of the secure ant-based routing protocols in MANET. Section 3 describes our proposed work Secure Energy Efficient Ant Routing Algorithm (SEEARA) for MANETs in detail. In Section 4 we have simulated our work along with the basic Ad-hoc On demand Distance Vector (AODV) [19], Secure Routing Protocol (SRP) [20] and the ACO based Ant Routing Algorithm (ARA) [21] and Secure Power Aware Ant Routing Algorithm (SPA-ARA) [22] routing protocols using NS-2.35 and the results are compared and analyzed. Finally, in Section 5 we have concluded our work.

2. Related work

ACO based routing protocols can be categorized into several types such as: basic ACO routing protocols, QoS aware ACO routing protocols, energy aware ACO routing protocols, location aware ACO routing protocols and security aware ACO routing protocols. But here in our study, we focus only on secure routing protocols. Also, we will discuss some other reactive routing protocols like AODV, SRP and ARA that we have considered as a measure of comparison during our simulation studies.

Vijaylaxmi and Palanively [23] proposed a Secure Antnet Routing protocol based on ACO and Elliptical Curve Cryptography (ECC) [24] described as SAR-ECC for cluster based networks. In this approach, the trust value of each neighbor node is measured by every node in a cluster. The trust value of a neighbor node is measured as a growing function correlating with the likelihood of packet delivery ratio. The source node during route discovery uses the AntNet [25] mechanism for establishing multiple routes. The source and destination nodes mutually authenticate each other using the concept of ECC. This mechanism estimates the trust value in view of the idea of uncertainty rather than the usual pheromone idea. Also trust value updating procedure and the benefits of combining cluster with ACO is not described.

Mehfuz and Doja [22] proposed a Secure Power Aware Ant Routing Algorithm named as SPA-ARA. Initially, a source node when requires to start a data transmission towards the destination node and gets no route information available, then the reactive forward ants (FANTs) are sent affixed with a cryptographic Message Authentication Code (MAC) generated using HMAC keyed hash algorithm [26]. Each intermediate node check for the validity of MAC and finding it to be correct, checks for the trust value of the sender with the previously fixed threshold value. When both are found to be positive, then a secret key is built up between the two nodes. Otherwise the FANT is discarded or killed. Repeating the procedure at each intermediary node, at the point when the FANT achieves the destination node an analogous backward ant (BANT) is generated. The BANT travels in the reverse of the path travelled by the FANT and at each intermediary node the MAC affixed with the BANT is validated utilizing the beforehand created secret key by FANT. During its travel, also the BANT updates the pheromone table. On reaching the source node, the authentication of nodes is completed by the BANT using the MAC attached to it. Further, the data packets are sent using the route information present on the pheromone table and secured with MAC attached to it. This scheme may declare some genuine nodes as malicious as if a node when measures the trust value of a node, some packet loss due to congestion shows it to drop packets. Also in this paper, nothing has been stated about the overheads occurring due to cryptographic operations.

Indrani and Selvakumar [27] proposed a technique for designing a multipath routing protocol which sets up numerous paths connecting the source and destination node utilizing the SI behavior of ACO algorithm, and uses the concept of trust values for securing the network by detecting the intrusions in the network. The protocol named as Swarm based intrusion Detection and Defence Technique (SBDT). Each node possessing a greater trust value, remaining bandwidth and energy, monitors all of its neighbor nodes and is termed as an active node (NA). During transmission of data, if any communicating neighbor node’s trust value falls below the threshold, at that point the NA distinguishes it as a malicious node and informs the source node about it. Further, a revocation process may be initiated by the source node to defend against the detected malicious node. Here, the NAs are solely responsible for the novelty of the intrusion detection system (IDS). The authors of this proposal have not given a clear explanation about the updating and estimation of the trust value, whereas it plays the key role to implement these IDS. Also, no explanation is given about the situation when a NA is compromised and behaves maliciously.

Sowmya et al. [28] have suggested an idea of Detection and Prevention of Blackhole Attack in MANET using ACO routing technique which is named as DPBA-ACO by us in this chapter during further studies. An AntNet routing algorithm which has been discussed before in this chapter is used to discover optimal routes within the network during routing using this protocol. A threshold value is used for the detection of blackhole attack in MANET which can be updated dynamically over a settled brief time interim. Threshold values can be computed as a normal of the difference between sequence numbers present within the routing table and the sequence number present with the BANT. A node suspected to be a blackhole node if it forwards a BANT packet with a higher sequence number than the threshold value. Once a node is detected as malicious, it is added into the blacklist and a control packet ALARM containing the blackhole nodes ID as a parameter is sent to the neighbors. By getting the ALARM packets, the network nodes get aware of the blackhole node and put it into their blacklist prohibiting the communication with that node. Hence, the blackhole node gets isolated from the network.

Memarmosherefi et al. [29] proposed an approach named as Autonomous Bio-inspired Public Key Management (ABPKM) for defending attacks those occur in the network layer of the OSI model. This approach mainly combines the features of ACO algorithm to self-organized public key management schemes defending against the misbehavior of nodes and maintaining the correctness of keys. Initially, every node in the network issues a public key to its adjacent nodes along with initializing its trust value. During route discovery, a FANT is transmitted by the source towards the destination which keeps up a chain of public keys encountered on its path. On reaching the destination, the FANT is killed and a BANT is generated to traverse the path of FANT in reverse direction carrying the public key chain to the source. The source node authenticates those public keys and the chain with most noteworthy trust value is selected by the source for further data transmission. Also, the trust value of its neighbors is updated by every node starting from the source node hop by hop along the chain depending upon the result of authentication at the source node. The proposal again is re-improved by the addition of an agglomerative hierarchical clustering algorithm for providing more security towards the attacks like Sybil attack [30]. The node features like the total number of groups it belongs to, distance from the destination, its social degree and trust value for chains it participates in are gathered by the source node for clustering purpose. Also, a new parameter aggression value is introduced in this model for evaluating the level of danger within the network. In light of the different experimental and aggression values, the authors conclude that the mobile nodes can detect the attackers more efficiently in comparison with the static nodes.

Sridhar et al. [31] suggested an ANT Based Trustworthy Routing in Mobile Ad-hoc Networks Spotlighting Quality of Service based on the trust value calculation for every network node and selecting the node with higher trust value in comparison with the threshold value for routing. From this onwards, we use the name ANTBTR to identify this routing protocol. ANTBTR protocol provides an optimal and secure communication, and also provides an improvement for the QoS parameters like end-to-end delay and packet delivery ratio. Before transmission, this protocol selects the route and nodes participating in the route and checks their trust value against the threshold value. The nodes with trust value not as much as the threshold value is made out of the route, along with alternate nodes are selected to fulfill the purpose. Trust value calculation is made based upon a model proposed by the author. The model depends on various parameters of RREQ, RREP and Data. The parameter based on RREQ is a query request success rate (QRS) that represents the ratio of the neighbor nodes that accepted the RREQ packets sent by the sender with respect to the total number of neighbor nodes, query request failure rate (QRF), is the complement of QRS which means the number of neighbor nodes that did not accept the RREQ with respect to the total number of neighbor nodes. Similarly RREP parameters, query reply success rate (QPS) and query reply failure rate (QPF) describe the rate of success and failure of RREPs received from the nodes by the sender respectively. Data transmission parameters, data success rate (QDS) and data failure rate (QDF) represent the total amount of data successfully transmitted to the receiver and the data dropped during the transmission with respect to the total amount of data sent by the sender respectively. Also, the values of the parameters are normalized considering the various constraints that are responsible for the loss of data during transmission. The route discovery takes place between the nodes using the general ACO routing mechanism and the pheromones are updated after completion of one iteration of ants. The detailed mechanism of route discovery and path maintenance is not described by the authors.

Shanthi and Murugan [32] have suggested a Pair-wise Key Agreement and Hop-by-hop Authentication Protocol (PKAHAP) to provide secure communication in MANET. This protocol uses one round ID based authenticated group key agreement protocol (IDAGKA) [33] at each node for authenticating the data packets. Basically, the proposed swarm-based authenticated routing scheme consists of two types of ant agents such as FANT and BANT. Initially to start a transmission, the source node selects the routes to the destination based on the ACO technique. Source initiates the FANTs attached with a threshold trust value and sends them to the neighbors. The threshold value is compared with the neighbor node’s trust value and the neighbor node is updated in the routing table if it is found to be trustworthy, else finding the trust value of the node to be not as much as the threshold value, it gets eliminated from the routing table. This process repeats until the FANT reaches the destination. On achieving the destination, the FANT changed over into BANT and transmitted in the reverse direction on the path travelled by the FANT towards the source. During its travel BANT updates the pheromone values across the nodes and when it achieves the source, in light of the information contained by it, source decides the most trusted path to communicate. During data transmission, pair-wise keys are set up between every set of two nodes to provide security at each instance. To make the communication more secure, session keys are generated implicitly and used for encryption of the message transmitted during the communications between two nodes which avoids the situation of compromised or impersonated keys.

In our previous work [34] we have analyzed the effect of the blackhole attack on routing protocols considering basic AODV [19] and DSR [35] routing protocols. Further, in [36] we have suggested an energy aware scheme for detection and prevention of blackhole attack in MANET. Our protocol uses the ACO technique to find the shortest path from source to destination, applies the concept of power aware techniques to save energy, increasing the longevity of the link avoiding link failure and also uses the concept of digital signatures, watchdog and path rater for detection and avoidance of blackhole and grayhole attacks. Simulation study of the proposed scheme is made over some network parameters and found to be efficient in comparison to the basic AODV routing protocol.

3. Secure energy efficient ant routing algorithm (SEEARA)

Our proposed work Secure Energy Efficient Ant Routing Algorithm (SEEARA) as a hybrid multipath algorithm uses reactive as well as proactive routing approach depending upon the information accessible within the routing table of communicating nodes to choose multiple paths from source to destination. ACO techniques are used for optimal path discovery minimizing variability and errors in the network, whereas a lightweight MAC generated using Chaskey algorithm [37] and two party key establishment protocols are used with each packet transfer to provide security features. As SEEARA uses a lightweight MAC algorithm, generates low overhead in comparison to other previously proposed routing protocols. A two-way trust evaluation mechanism is associated with each node for authentication of malicious behavior of unauthorized and compromised nodes and to eliminate them during communication. The basic designing concepts and working methodology of our proposed routing protocol SEEARA is discussed and explained within this section in detail.

3.1 Data structures used

SEEARA uses two types of agents and classifies them according to their directions of movement as Forward Ant (FANT) ant Backward Ant (BANT). When a data session started between a source node and a destination node, and up-to-date routing information is not available, then reactive FANTs are used to find paths from source to destination. FANTs are probabilistic and explore the network for collecting information regarding the quality of the route they follow. The information is stored by the FANT using data fields and a stack. On reaching the destination FANTs are converted into BANTs, which retraces the path of the FANTs deterministically from destination to source conforming the path discovered by the FANT during route discovery and path setup. BANT uses data fields along with a priority queue during its traversal. During its travel BANT updates the routing pheromone table and other data structures utilizing the information gathered by the FANT.

Table 1
Routing pheromone table

Destination node	Neighbour nodes
	${n}_{1}$	${n}_{2}$	${n}_{3}$	$\ldots$	${n}_{m}$
${d}_{1}$	$\Omega(d_{1},n_{1})$	$\Omega(d_{1},n_{2})$	$\Omega(d_{1},n_{3})$	$\ldots$	$\Omega(d_{1},n_{m})$
${d}_{2}$	$\Omega(d_{2},n_{1})$	$\Omega(d_{2},n_{2})$	$\Omega(d_{2},n_{3})$	$\ldots$	$\Omega(d_{2},n_{m})$
${d}_{3}$	$\Omega(d_{3},n_{1})$	$\Omega(d_{3},n_{2})$	$\Omega(d_{3},n_{3})$	$\ldots$	$\Omega(d_{3},n_{m})$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
${d}_{n}$	$\Omega(d_{n},n_{1})$	$\Omega(d_{n},n_{2})$	$\Omega(d_{n},n_{3})$	$\ldots$	$\Omega(d_{n},n_{m})$

At each node, routing information is maintained in a table called a routing pheromone table as represented in Table 1. The pheromone value $\Omega_{(i,j)}^{d}$ contains the goodness of path from node $i$ to destination $d$ with each possible next hop $j$ . The pheromone values are updated considering the end-to-end delay, number of hops, remaining bandwidth and remaining energy of nodes, which refers to the combination of maximum path availability with minimum time to travel along with minimum congestion.

Table 2

Trust pheromone table

Node	Trust value
$n_{1}$	$\tau(n_{1})$
$n_{2}$	$\tau(n_{2})$
$n_{3}$	$\tau(n_{3})$
$\vdots$	$\vdots$
$n_{n}$	$\tau(n_{n})$

Figure 1.

Route discovery process along with the data structures used.

New, neighbors are detected by the broadcast of hello messages periodically. Trust value for all the neighboring node is maintained by a node using a table known as trust pheromone table as represented in Table 2, and during neighbor discovery, the neighbor nodes are checked for their trustworthiness from the trust pheromone table. The secret key between the sender and its neighbor is established using a two-party key establishment protocol when a neighbor meets a trust value, otherwise the neighbor node with trust value less than the defined threshold is considered to be a malicious node and its participation in the communication is discarded. Further, during communication, the trust pheromone value $\tau(n_{1})$ for a node $n_{1}$ is updated using a two-way trust evaluation technique over the packet delivery ratio factor.

The movement of ant agents (FANT and BANT) along with the basic data structures used is explained pictorially in Fig. 1, considering a situation where source node S makes a route discovery to destination D with intermediary nodes A and B.

3.2 Route discovery and path setup

Initially during route discovery and path setup phase, a MAC is generated using a shared group key and a keyed hash algorithm. The source node creates a FANT from source to destination (FANT ${}_{\text{SD}}$ ) and attaches its MAC to it. Then, the FANT ${}_{\text{SD}}$ is broadcasted to its neighbour in search of a destination node. Onwards the source and destination nodes are selected randomly for route discovery.

An intermediate node $i$ after receiving the FANT ${}_{\text{SD}}$ , verifies the MAC using the shared group key K and getting it to be successful, i.e. when MAC found to be correct, the trust value is checked for the sender accessing from the trust pheromone table. If the sender node is found to be trustworthy, the receiver node, then considers it as neighbours and a two-party key establishment occurs between them to create a shared secret key for authentication. Otherwise the FANT ${}_{\text{SD}}$ is discarded by the receiver.

When the node $i$ is not a destination node, further it attaches its own address and time to FANT ${}_{\text{SD}}$ and rebroadcasts FANT ${}_{\text{SD}}$ to its neighbour, if it does not have a valid route to the destination.

Because of the broadcasting, ants can spread across the network so quickly trailing distinct path to destination. Hence, those ants who travelled maximum number of hops are killed or discarded. Broadcasting also makes duplicity of ants so natural that a particular node may receive several ants of the same type. Hence, when a node $i$ receive a matching ant of the similar type, then it gets rid of all keeping only those ants with the least number of hops and less travel time taken i.e. only the best ant is selected.

At each node $i$ , the ant is unicast or broadcast relying on the accessibility of routing information with the node. Considering an ant at node $i$ moving towards the destination node $d$ through a node $j$ can be selected using probabilistic metric next hop availability as represented in Eq. (1):

$\displaystyle N_{\textit{Hop}(i,j)}^{d}=\Bigg{(}\Omega_{(i,j)}^{d}\Bigg{/}\sum% ^{|{\textit{Neb}(i)}|}_{k=1}\Omega_{(i,k)}^{d}\Bigg{)}$ (1)

The new node selected using next hop availability is added to ant’s memory.

Repeating the procedure when the FANT ${}_{\text{SD}}$ achieves the destination, it is transformed into a BANT that starts from the destination and moves towards the source (BANT ${}_{\text{DS}}$ ) traversing the path kept by its FANT (FANT ${}_{\text{SD}}$ ) in reverse order.

When, backtracking the path of a FANT is not possible due to reasons like node movement, node failure etc., the BANT is discarded.

Otherwise BANT ${}_{\text{DS}}$ at each node, sets up a path following the same procedure as by FANT ${}_{\text{SD}}$ , whereas in each step additionally, it updates the routing pheromone table and trust pheromone table present at each of the nodes it traverses. Also, the MAC in BANT ${}_{\text{DS}}$ is replaced in every stage by a MAC calculated with the help of shared secret keys with the next hop found.

Considering BANT ${}_{\text{DS}}$ at the destination node moving towards the source, a MAC calculated using a pair-wise secret key shared between the destination node $d$ and its next hop towards source $d+1$ . The receiver node $d+1$ verifies the MAC of sender node $d$ and if found to be correct, then routing pheromone table is updated with regards to the number of hops, end to end delay, remaining bandwidth and remaining energy used, based on the Eq. (2):

$\displaystyle\Omega_{(i,j)}^{d}=\rho\times\Omega_{(i,j)}^{d}+({1-\rho})\times R$ (2)

where Backward Ant moves from destination node d and at a node $j$ moves towards source node $s$ through node $i$ . $\Omega_{(i,j)}^{d}$ is the routing pheromone table entry, $\rho$ is the evaporation constant that lies in a range $(0,1]$ . $R$ is the reinforcement factor which can be calculated by the product of three more factors $R_{\textit{delay}}$ , $R_{\textit{energy}}$ and $R_{\textit{bandwidth}}$ and can be computed as per the Eqs (4)–(6) respectively.

$\displaystyle R=R_{\textit{delay}}\times R_{\textit{energy}}\times R_{\textit{% bandwith}}$ (3) $\displaystyle R_{\textit{delay}}=\Bigg{(}\Bigg{(}\sum^{H_{({i,d})}-1}_{i=1}({1% +Q_{({i,i+1})}})\times({t_{(i)}})+H_{({i,d})}\times D_{\rm H}\Bigg{)}\Bigg{/}2% \Bigg{)}^{-1}$ (4) $\displaystyle R_{\textit{energy}}=\Bigg{(}{B_{(i,j)}^{d}\Bigg{/}\sum^{|{% \textit{Neb}(i)}|}_{k=1}B_{(i,k)}^{d}}\Bigg{)}$ (5) $\displaystyle R_{\textit{bandwidth}}=({\textit{Bandwidth}_{\textit{Avail}_{(j)% }}/\textit{Bandwith}_{\textit{Total}_{(j)}}})$ (6)

where $H_{(i,d)}$ is the number of hops from node $i$ to node $d$ , $Q_{({i,i+1})}$ is the number of packets in queue to be transferred from node $i$ to node $i+1$ , $t_{(i)}$ is the time taken for successful transmission of a packet from node $i$ to node $i+1$ , $D_{h}$ is the time taken for one hop under the unloaded condition called hop delay. Further, ${t}$ can be calculated as:

$\displaystyle t=D_{t}+D_{p}+D_{r}$ (7)

where $D_{t}$ is the transmission delay, $D_{p}$ is the propagation delay and $D_{r}$ is the delay due to processing of packets as routers.

Path with the maximum minimum residual battery energy (MMRB) of all nodes during the travel is determined and at node $i$ travelling from the destination node $d$ through node $j$ , the remaining battery is computed for neighbour node as in Eq. (8);

$\displaystyle B_{(i,j)}^{d}=\textit{MMRB}/H$ (8)

i.e. the minimum residual battery of all nodes travelled up to current node per number of hops during the travel of a backward ant. $\textit{Neb}(i)$ represents the neighbour nodes of node $i$ .

The trust pheromone table can be uploaded monitoring the packet delivery ratio and jitter (end-to-end delay from a packet to next packet) for each pair of nodes. Whenever we found that the features are varying considerably for a node, then the node is considered to be dropping packets. When a node is found to be so, then the node is considered to be malicious and its trust values are decreased. Otherwise, trust values are reinforced.

Here, we use a two-way trust evaluation technique [38] where trust value of a node is calculated based on observations made by itself as well as its neighbours. Hence, the trust pheromone table can be updated as per the Eq. (9).

$\displaystyle\tau_{(i)}=({({1-C1})\times\tau_{(i)}+\textit{PDR}_{(i,j)}})% \times\Bigg{(}\Bigg{(}{\sum^{|{\textit{Neb}(i)}|}_{k=1}({1-C2})\times\tau_{(k)% }}\Bigg{)}\Bigg{/}|{\textit{Neb}(i)}|\Bigg{)}$ (9)

where $\tau_{(i)}$ is trust pheromone table entry for node $i$ measured by node k and other neighbours of node $i$ , $C1$ is weighted parameter constant in the range from $[0,1]$ and $C2$ is the constant based on neighbour’s trust provided in the range from $[0,1]$ . PDR is the Packet Delivery Ratio and can be calculated as a ratio of the number of packets received by the receiver to the number of packets sent by the sender.

The power of nodes can be updated considering the power loss from battery during transmission of data to neighbours and receiving data from neighbours [39]. Accordingly, the energy consumption can be calculated as per the Eqs. (10) or (11).

$\displaystyle B_{(i)}=B_{(i)}-({E_{\textit{trans}}+bd_{\textit{SR}}^{\mu}})\times l$ (10) $\displaystyle B_{(i)}=B_{(i)}-({E_{\textit{sense}}+bd_{\textit{SR}}^{\mu}})\times l$ (11)

where $B_{(i)}$ is the residual battery power of a node $i$ , $b$ is a constant, $\mu$ is the path loss factor, $d_{\textit{SR}}$ is the Euclidian distance between the sender and receiver nodes, $l$ is the number of bits sent or received by the node, $E_{\textit{sense}}$ and $E_{\textit{trans}}$ are the amount of energy spent in sensing data during receiving data from sender and transmitting the data to the receiver respectively.

This procedure is repeated at each node visited by the BANT ${}_{\text{DS}}$ until the point that it accomplishes the source node. At last, on achieving the source node BANT ${}_{\text{DS}}$ establishes a good and secure route linking the source and destination.

4. Data forwarding

Using the method of route discovery and path setup as described previously, various suitable and secure paths are established connecting the source and destination nodes, which are reflected in the routing pheromone table.

Once the data session begins, the data packets are forwarded stochastically along with the MAC attached to it. MAC is verified at every node like that during the route discovery. The nodes are selected using the probabilistic next hop availability metric described before, i.e. the next node will be chosen with probabilistic conditions as per the routing pheromone value.

5. Route maintenance and link failures

In every certain interval of time, FANTs are sent by the source node proactively, but for certain situations, if the required information is not available in the routing pheromone table then the FANTs may be sent reactively. Finally the FANTs on reaching the destination node are converted into BANTs and retrace the path of the FANTs and update the required data structures during its travel towards the source. Depending upon the type of communication from one node to another, i.e. unicast or broadcast, the routing pheromone table entry is updated with current values of pheromone or new paths are discovered respectively.

Link failures are managed locally by the nodes. When link fails between a pair of nodes, then a route discovery process is initiated among those nodes to establish a link which may be proactive or reactive in nature depending upon the situation.

1 SEEARA

Number of nodes: $\{n_{1},n_{2},n_{3},\ldots,n_{n}\}$

The neighbour table: Contains all nodes present within the neighbourhood of any node.

The routing pheromone table: Contains the pheromone values for each link available to the next hop to transmit packets.

The trust pheromone table: Contains the pheromone values for indicating the trustworthiness of the next hop to transmit packets.

Threshold value for trust pheromone $=$ 0.5

Initially routing pheromone for all nodes $=$ 0 and trust pheromone for all nodes $=$ 1

Updated values in the pheromone tables required to transmit data.

Optimal and secure paths from source to destination by selecting next hop with highest probability.

Step 1: At a sender node:

MAC $=$ H(shared group key, message)

FA $=$ FA $+$ MAC

(routing information available in routing pheromone table)

Send FAs to next hop using next hop availability as described in Eq. (3)

Broadcast FAs

Step 2: At any intermediate node on receiving a FA:

(Verify(MAC) $==$ TRUE)

(Verify(trust value) $>$ threshold)

Establish secret key with the sender

Add the nodes information to FA

Discard FA

(intermediate node $!=$ destination node)

goto Step 1

Step 3: At destination node after receiving a FA:

BA $=$ FA

MAC $=$ H(secret key, message)

BA $=$ BA $+$ MAC

Send BA towards the sender following the reverse path travelled by the FA

Step 4: At any intermediate node on receiving a BA:

(Verify (MAC) $==$ TRUE)

Update the pheromone (P) in the routing pheromone table of each node on the path based on the information collected by the FANT about the factor number of hops, remaining path energy, path delay and remaining bandwidth as described in the Eq. (4)

Update the trust value ( $\tau$ ) in the trust pheromone table as computed at each node on the path based on the two-way trust evaluation technique and the factor packet delivery ratio as described in the Eq. (11)

Discard BA

(intermediate node $==$ source node)

goto Step 5

MAC $=$ H(secret key, message)

BA $=$ BA $+$ MAC

repeat Step 4

Step 5: At source node:

Multiple path established from source to destination.

Data transmission is initiated with each packet associated with MAC, selecting next hop with probability $N_{\textit{(Hop)sd}}$ from all available, by taking the pheromone values from routing table.

Step 6: For pheromone reinforcement Step 1 is repeated from the source node in every certain interval of time.

Step 7: On link failure, Step 1 is repeated from the node that has data to send, but required information is not available in the routing pheromone table.

6. Simulation results

The performance of our proposed routing algorithm SEEARA is assessed in comparison with the basic AODV, DSR, SRP, ARA and reconstructed SPA-ARA routing algorithms and the simulation and performance metric characteristics are explained. Table 3 characterizes the simulation scenario and parameter settings. Each algorithm runs with the same scenario as given in the Table 3 and their behavior is studied as well as differentiated.

6.1 Successful routes established

Dynamic behavior of Ad-hoc networks makes it challenging to find a route during network changes. So, we have taken the number of routes found as a simulation parameter to show the adaptability of our scheme to small as well as large scale networks where the topology changes dynamically. Figure 2 shows that within a particular time period, SEEARA establishes a number of successful routes from source to destination in comparison with others. Analysis of the results presents that SEEARA finds 52%, 41%, 12% and 4% more routes on an average in comparison with the ARA, AODV, DSR and SPA-ARA routing algorithms and the rate also goes increasing with increase in the time period.

Table 3
Simulation scenario and parameter settings for implementing SEEARA

Parameter name	Value
Number of nodes	50
Node distribution	Random
Area dimension	1500 $\times$ 750
Simulation time	300 s
Propagation	Radio-propagation model (two way)
Network type	Wireless
Traffic generator	CBR
MAC type	IEEE 802.11
Antenna type	OmniAntenna
Mobility pattern	Random
Node speed	10 to 15 m/s
Interface queue type	DropTail/PriQueue
Max packet in interface queue	50

Figure 2.

Comparison graph showing successful route established.

Figure 3.

Comparison graph showing energy standard deviation.

6.2 Energy standard deviation

Figure 3 shows that the energy standard deviation for SEEARA is very less in comparison with ARA, AODV and DSR, whereas for SPA-ARA, it is little more. Comparing the simulation values it has been found that SEEARA presents 46%, 42%, 35% and 16% less average standard deviation in comparison with ARA, AODV, DSR, and SPA-ARA respectively. It indicates that SEEARA distributes the energy across the network more uniformly increasing the lifetime of the network. Also energy consumption for SEEARA is less in comparison with other routing protocols due to the use of path with maximum of minimum remaining battery and once a route has been set up, its reliability in terms of energy of the route exists as due to less node errors, more packets can be transmitted with less energy.

6.3 Packet delivery ratio

The packet delivery ratio is one of the most important metrics for protocol evaluation. Figure 4 shows simulation results for various routing protocols under the metric packet delivery ratio and the observation exhibits that SEEARA improves the performance in contrast with all other routing protocols. The packet delivery ratio of SEEARA increases with a huge difference in comparison with ARA and AODV routing protocols by 2.89 and 2.48 times, respectively, moderate in comparison with SRP, by 0.23 times and, less with SPA-ARA by 0.05 times. When simulation time increases, the performance increases progressively. Good link quality obtained in SEEARA in terms of optimality and security increases the packet delivery ratio substantially in comparison with other compared protocols.

Figure 4.

Comparison graph showing packet delivery ratio.

Figure 5.

Comparison graph showing network throughput.

6.4 Network throughput

Figure 5 shows network throughput in which SEEARA shows a higher performance in comparisons with the routing protocols SRP and SPA-ARA with an increase of 83% and 29% respectively. The network throughput also goes increasing with increase in simulation time. Techniques used in SEEARA for optimal path selection, lowering packet loss and overhead, make it more efficient, increasing the network throughput.

6.5 Number of attackers vs. packet loss

Whenever the number of attackers in a network increases, it leads to a more vulnerable situation to drop packets, causing link failures, creating false routes and many more adversaries disrupting the entire network communication. Here, we have considered only the packet loss metric to study the effect of routing protocol vs. increasing number of attackers. Figure 6 shows the packet loss when there is an increase in number of attackers in the network. Our proposed routing protocol SEEARA is compared with two other routing protocols with security features enabled such as SRP and SPA-ARA. Analytical results show that SEEARA drops 40% and 14% less number of packets respectively in comparison with SRP and SPA-ARA routing protocols. We can say that the packet loss, increases with an increase in number of attackers, but SEEARA shows a better performance in those situations for using its secure cryptographic mechanisms along with the two-way trust evaluation technique in comparison with AODV and SPA-ARA routing protocols.

Figure 6.

Comparison graph showing packet loss with an increase in number of attackers.

7. Conclusion

In this paper, we have proposed an ACO based Secure Energy Efficient Ant Routing Algorithm (SEEARA) for MANET. We have evaluated our proposed routing protocol through simulation results shows its efficiency in terms of energy and security. The adaptive ACO technique is used for finding the optimal paths, organizing the cost of each route that improves the path selection and the system efficiency. ACO approach used in our scheme, as it provides better result in comparison to other routing protocols for providing more robust, effective and efficient routing protocol in MANET following a decentralized and distributed approach for path discovery and packet forwarding making routing to be self-organized without any prior planning. Use of MAC and key verification in every pair of nodes makes our routing protocol more secure in comparison to others, whereas it may lead to a higher amount of computational costs. Further, in our future studies, we will try to avoid these computational costs by using other newly developed security mechanisms to make our proposed routing protocol more efficient in terms of computations and memory requirements.

Footnotes

Appendix

Network Simulator 2 (NS-2) [40], is a discrete event simulator and is based on C++ for the implementation of models of the simulation. It utilizes command scripts oTcl to control the simulation.

References

Scott

Bambos

. Routing and channel assignment for low power transmission in PCS. 1996; 2: 498-502.

Singh

Woo

Raghavendra

. Power-aware routing in mobile ad hoc networks. 1998; 181-190.

Toh

. Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks. IEEE Communications Magazine. 2001; 39(6): 138-147.

Kim

Garcialunaaceves

Obraczka

Cano

Manzoni

. Power-aware routing based on the energy drain rate for mobile ad hoc networks. 2002; 565-569.

Liang

Yuansheng

. Maximizing battery life routing in wireless ad hoc networks. 2004; p. 90295.

Srinivas

Modiano

. Finding minimum energy disjoint paths in wireless ad-hoc networks. 2005; 11(4): 401-417.

Yuen

Sung

. On energy efficiency and network connectivity of mobile AD HOC networks. 2003; 38-45.

Pattanayak

Mishra

Jagadev

Nayak

. Power aware ad hoc on-demand distance vector (PAAODV) routing for MANETS. Journal of Convergence Information Technology. 2011; 6(6): 212-220.

Rath

Pattanayak

Pati

. Energy competent routing protocol design in manet with real time application provision. International Journal of Business Data Communications and Networking. 2015; 11(1): 50-60.

10.

Rath

Pattanayak

Pati

. Energy efficient MANET protocol using cross layer design for military applications. Defence Science Journal. 2016; 66(2): 146-150.

11.

Panda

Gadnayak

Panda

. MANET attacks and their countermeasures: A survey. International Journal of Computer Science and Mobile Computing (IJCSMC). 2013; 2(11): 319-330.

12.

Lou

Fang

. A survey of wireless security in mobile ad hoc networks: Challenges and available solutions. Ad Hoc Wireless Networking. 2004; 319-364.

13.

Meddeb

Triki

Jemili

Korbaa

. A survey of attacks in mobile ad hoc networks. International Conference on Engineering & MIS (ICEMIS). 2017; 1-7.

14.

Dressler

Akan

. A survey on bio-inspired networking. Computer Networks. 2010; 54(6): 881-900.

15.

Marwaha

Indulska

Portmann

. Biologically inspired ant-based routing in mobile ad hoc networks (MANET): A survey. 2009; 12-15.

16.

Neumann

Witt

. Ant colony optimization and the minimum spanning tree problem. Theoretical Computer Science. 2010; 411(25): 2406-2413.

17.

Alhamdy

Noudehi

Majdara

. Solving travelling salesman problem (TSP) using ants colony (ACO) algorithm and comparing with tabu search, simulated annealing and genetic algorithm. Journal of Applied Polymer Science. 2012; 8(1): 434-440.

18.

Lopezibanez

Stutzle

Dorigo

Marti

Pardalos

Resende

MGC

. MGC colony optimization: A component-wise overview. 2017; 1-37.

19.

Perkins

Beldingroyer

Das

. Ad HOC on-demand distance vector (AODV) routing. 2003; 3561: 1-37.

20.

Papadimitratos

Haas

. Secure routing for mobile ad hoc networks. in: The SCS Communication Networks and Distributed Systems Modelling and Simulation Conference (CNDS). 2002; 193-204.

21.

Gunes

Sorges

Bouazizi

. ARA-the ant-colony based routing algorithm for MANETs. 2002; 79-85.

22.

Mehfuz

Doja

. Swarm intelligent power-aware detection of unauthorized and compromised nodes in MANETs. Journal of Artificial Evolution and Applications. 2008; 2008: 1-16.

23.

Vijayalakshmi

Palanivelu

. Secure antnet routing algorithm for scalable adhoc networks using elliptic curve cryptography. Journal of Computer Science. 2007; 3(12): 939-943.

24.

Kapoor

Abraham

Singh

. Elliptic curve cryptography. Ubiquity. 2008.

25.

Di Caro

Dorigo

. AntNet: Distributed stigmergetic control for communications networks. Journal of Artificial Intelligence Research. 1999; 12(3/4): 2-37.

26.

Krawczyk

Bellare

Canetti

. HMAC: Keyed-hashing for message authentication. 1997; 2104: 1-11.

27.

Indirani

Selvakumar

. Swarm based detection and defence technique for malicious attacks in mobile ad hoc networks. International Journal of Computer Applications. 2012; 50(19).

28.

Rakesh

Hudedagaddi

. Detection and prevention of blackhole attack. MANET using ACO. 2012; 12(5): 12.

29.

Memarmoshrefi

Zhang

Hogrefe

. Investigation of a bio-inspired security mechanism. Mobile Ad HOC Networks. 2013; 709-716.

30.

Memarmoshrefi

Zhang

Hogrefe

. Social insect-based sybil attack detection in mobile ad-hoc networks. 2014; 141-148.

31.

Sridhar

Baskaran

. ANT based trustworthy routing in mobile ad hoc networks spotlighting quality of service. Computer Science and Information Technology. 2015; 3(1).

32.

Shanthi

Murugan

. Pair-wise key agreement and hop-by-hop authentication protocol for MANET. Wireless Networks. 2017; 23(4): 1025-1033.

33.

Reddy

Nalla

. Identity based authenticated group key agreement protocol. 2002; 215-233.

34.

Panda

Pattanayak

. Analysis of blackhole attack in AODV and DSR. International Journal of Electrical and Computer Engineering. 2018; 8: 3093-3102.

35.

Johnson

Maltz

Broch

. DSR: The dynamic source routing protocol for multi-hop wireless Ad HOC networks. Ad HOC Networking. 2001; 8(5): 139-172.

36.

Panda

Pattanayak

. Energy aware detection and prevention of black hole attack in MANET. International Journal of Engineering and Technology. 2018; 7(2): 135-140.

37.

Mouha

Mennink

Van Herrewege

Watanabe

Preneel

Verbauwhede

. Chaskey: An efficient MAC algorithm for 32-bit microcontrollers. 2014; 306-323.

38.

Geetha

Kannan

. SEBAR: Secure energy based ant routing algorithm for wireless sensor networks. Proceedings of the International Conference on Advances in Communication, Network and Computing. 2014; 21-22.

39.

Zhao

Gurusamy

. Lifetime maximization for connected target coverage in wireless sensor networks. IEEE ACM Transactions on Networking. 2008; 16(6): 1378-1391.

40.

McCanne Steven Sally

. The UCB/LBNL network simulator, software online. 1997.

A secure and energy efficient ant routing algorithm

Abstract

Keywords

1. Introduction

2. Related work

3. Secure energy efficient ant routing algorithm (SEEARA)

3.1 Data structures used

Table 1 Routing pheromone table

5. Route maintenance and link failures

6. Simulation results

6.1 Successful routes established

Table 3 Simulation scenario and parameter settings for implementing SEEARA

6.3 Packet delivery ratio

6.5 Number of attackers vs. packet loss

Footnotes

Appendix

References

Table 1
Routing pheromone table

Table 3
Simulation scenario and parameter settings for implementing SEEARA