Modelling and QoS implementation of wireless sensor networks based on the ant colony optimization approach

Published Online June 2018 in MECS

A traditional wireless sensor network (WSN) consists of a set of interconnected autonomous devices called “sensor motes” that can jointly measure changes in the environmental conditions in an area of interest and report to a processing place where decisions are taken about the area and/or further processing. Recent improvements in camera sensors and wireless communication technologies have led to the design of a new type of sensor networks called visual sensor networks (VSNs). Building around a distributed network of camera sensors, VSNs have expanded the range of WSN applications to areas that we could not fathom without the advances made by their underlying technologies. These include applications in smart parking for smart cities, detection and prediction of natural calamities, video surveillance for security systems such as pipeline monitoring, oil and gas exploration, real-time crop monitoring [1-3]. However, in contrast to traditional WSNs, VSNs are high bandwidth demanding networks which require transmission of high volume of data from camera sensors to sink nodes and/or much higher in-network processing and intelligence to reduce the amount of data to be transmitted over VSNs links. Energy conservation and throughput maximization are two important performance parameters upon which the quality of service provided and large scale deployment of VSNs depends as they are expected to remain functional for many years before replacing the battery of a sensor node while providing a continuous stream of image data continuously. Several approaches have been proposed in the literature to minimize sensor nodes’ energy consumption [4-7] but only few on VSNs throughput maximization.

• A.    The Relevance of Routing Protocol for Wireless Sensor Networks

In large scale WSNs, sensor nodes are distributed far from the data center (base station) and therefore use the neighboring nodes to relay the data packets towards the base station. Routing in WSNs is very important and it is different from conventional networks based on the following characteristics [8, 9] : In WSNs, the sensor nodes have limited capabilities in terms of energy source, memory and data processing. Efficient use of resources is important.

Most traffic in WSNs is many-to-one traffic data transmission. Data packets are transmitted from sensor nodes to the base station.

Sensor nodes are usually deployed in large numbers coupled with the resource constrained; it is difficult to uniquely assign individual sensor node an IP address.

Routing techniques in WSNs can be broadly grouped into two types: single path routing and multipath routing. Single path routing is simple and scalable, but not efficient for resource constrained WSNs [10] . It is simple because paths between source nodes and the destination node can be formed in a specific period of time. It is scalable because as the number of sensor nodes increases, the complexity and the method to establish routes between the source nodes and the base station remain the same.

On the other hand, multiple path routing transmits copies of the same data along different paths. It addresses the load balancing, security and reliability problems of the single path routing protocol [8, 11]. In case the primary path is unavailable due to congestion or low energy of the sensor nodes, an alternate path will be used to transmit the data packets to the base station. This increases the throughput of a network by sending pieces of data packets in parallel over different paths and restoring the entire information at the destination with the expectation of achieving better playback delay (the maximum delay taken by all the pieces of information to arrive at the destination) and minimized on-time packet delivery. Many multipath routing techniques have been proposed to improve network reliability by setting up disjoint paths in the sensor network (node-disjoint paths) [12,  13]. These techniques have attractive resilience properties but can be energy inefficient since the alternate node-disjoint path can be longer and therefore expends significantly more energy than that expended on the primary path. Braided multipath routing techniques have been proposed to relax the requirement for node disjointedness with the expectation of addressing the energy issues of node disjoint paths [14]. However, braided disjoint multipath routing protocol still builds around reliability requirements only, discounting the energy efficiency and throughput maximization. Owing to their structure, efficiently designed ant colony optimization (ACO) techniques provide the potential to achieve more efficient routing techniques for WSNs.

Routing protocols based on the ant colony optimization are efficient methods for minimizing energy consumption in WSNs. The ants communicate with each other by sensing the pheromone density on their paths. The idea was inspired by the study of ants’ mode of communication when organized into a colony. Dorigo and Birattari [15, 16] proposed an artificial algorithm based on the behavior of real ants in their colonies. The idea comes from observing the ants’ foraging behavior -how ants find the shortest paths between the food sources and their nest. When searching for food, ants first explore the area surrounding their nest in a random manner. While moving, ants deposit a chemical substance called pheromone on the paths as they are moving, forming pheromone trails between the food sources and the nest. Thus, when other ants are searching for food, they can smell the pheromone deposited on their paths and they tend to choose a path marked by strong pheromone concentration [17]. Each ant also tries to follow the pheromone trail left by the previous ants. Thus, increasing the amount of pheromone on the paths would continuously cause an increasing positive feedback which leads all the ants to a single path as shown in Fig.1. More ants will prefer to follow routes with a higher pheromone density since shorter routes can be traversed faster. In addition, pheromone deposited on the longer paths evaporates over time; the negative feedback received enables fewer ants to follow these paths. Thus, pheromone deposited on the non-optimal (longer) paths disappears over time. The ACO model was initially used to solve the travelling salesman problem (TSP). Since then, the model has been widely studied and improved.

In this paper, a routing algorithm for WSNs based on ACO with special parameters is proposed. The main objective of this algorithm is to prolong the network lifetime utilization. The proposed protocol is referred to as modelling and QoS implementation of wireless sensor networks based on the ant colony approach. Our approach is different from [18] other approaches used in the literature. First, we consider four parameters to achieve energy efficiency in a network: the link cost between the two sensor nodes, the remaining energy level of a receiver node, sensor node local information and the amount of data packets a receiver node is currently processing.

Fig.1. Ants find the shorter path via pheromone deposits

• B.    Contributions and Outline

This paper revisits the issue of QoS in WSNs to propose a new routing protocol that uses ACO. The protocol builds upon a local optimization model which is translated into pheromone distribution for an ant colony optimization algorithm used to find multiple paths for the sensor readings from their points of collection to the data center (base station) of a WSN. MACO finds efficient routing paths for the sensor readings by relying on four local performance parameters at each sensor node: the link cost, the remaining energy of nodes, sensor nodes location information and the amount of data a neighboring node is currently processing. These parameters are combined into a mixed metric used to define 1) transition probabilities used by an ant located at a node to select its relay node to the destination 2) rules which ants use to update the pheromone values on the paths between the sensor nodes 3) a measure to reduce pheromone concentration on the optimal path and encourage search for new paths that were formerly non-optimal through evaporation. Simulation results show that the proposed MACO outperforms other ACO algorithms in terms of energy efficiency, delay and throughput.

The rest of this paper is organized as follows: Section II presents the related work while the routing problem is described in section III. The proposed routing solution is presented in section IV. Simulations and results are presented in section V. Finally, section VI concludes the paper with possible direction of future work.

• II.    Related Work

In recent years, many routing techniques for WSNs have been proposed for energy optimization. These include tree-based energy-balance routing protocol, routing protocol using message success rate and energy constrained routing solutions [19-21] .

Multi-objective QoS routing for wireless sensor networks (MQoSR) [22] . The authors used geographic routing mechanism combined with QoS to transmit data packet to the base station. They considered three routing metrics: the end-to-end reliability, energy consumption and delay in selecting the paths from source node to the base station. This approach is energy efficient; it minimizes sensor nodes’ energy consumption compared to selected protocols in the paper. However, the authors did not consider the amount of data a receiver node is currently processing before a sender node forwards data to it, which may increase the delay if the receiver node has more data to process.

Radi et al [23] proposed an interference-minimized multipath routing protocol (IM2PR) to discover a sufficient number of interfering paths between a source node and the base station in order to provide efficient data packets. IM2PR consists of three phases: i) initialization phase ii) path establishment phase iii) data packet transmission phase. These phases are used to regulate the traffic rate of individual paths. This approach performs better than the micro sensor multipath routing protocol and energy efficient data routing protocol by certain higher percentage in terms of energy consumption, packet reception ratio, packet delivery latency and goodput. However, this protocol is designed for a small network; the overhead may increase as the size of sensor nodes increases to a large network.

Amgoth and Jana [24] proposed a new energy efficient routing algorithm for WSNs. They used clustering method to divide the network into different clusters. The proposed approach was evaluated through simulation. The results showed that the approach saves more energy and prolongs network lifetime. However, the authors did not consider the fault tolerant and dynamic nature of the sensor networks.

Ehsan Amiri et al [25] proposed an energy efficient routing in wireless sensor networks based on fuzzy ant colony optimization called FACOR. The protocol combines the foraging behavior of ants with fuzzy logic in order for the ants to find optimal routes. In addition, a fuzzy inference system was used to determine the route quality. The simulation results showed that FACOR minimizes sensor nodes’ energy consumption, decreases the number of routing request packets and maximizes the network lifetime compared to selected routing protocols. However, storing large rule-base in sensor networks may be impractical due to limited memory of sensor nodes because the rule-base in fuzzy logic grows exponentially.

Energy-aware ant-based routing wireless multihop networks (EARA) is proposed in [26] . EARA is an extension of ARA [27] . The authors use new mechanisms to determine the fitness of a path and energy information dissemination in order to extend the network lifetime. They consider the residual energy of a sensor node in addition to the pheromone value to determine the probabilistic routing decision process. The ant agent energy value is periodically updated in a sensor node routing table. Thus, EARA is more energy efficient than ARA protocol. It increases the average network lifetime and extends network utilization. However, EARA protocol has high overhead per routing data packet.

An energy efficient ACO-based multiple paths routing algorithm (EAMR) [28] is proposed for WSNs. This protocol is a hybrid algorithm which uses both reactive and proactive routing for path discovery and route maintenance. It uses a new multipath mechanism which takes into account the energy consumption rate, the congestion status of the path, and sensor node hop from the base station. In this protocol, pheromone is only updated when a sensor node receives a backward ant unlike the conventional incremental pheromone. EAMR achieves better performance in terms of end-to-end delay, energy efficiency and data packet delivery ratio. However, EAMP uses proactive as one of the routing mechanisms; forward ant may constantly be forwarded even when there is no data packet to transmit. There is a likelihood to increase the energy consumption of sensor nodes.

Authors in [29] presented a particle swarm optimization (PSO) based on routing algorithm to extend sensor network lifetime. They developed an algorithm to minimize the energy consumption of gateway nodes that are nearer to the base station. The proposed method is compared to two related algorithms based on the number of data packets received at the base station, the standard deviation of current energy and the number of dead sensor nodes.

• III.    Routing Problem

This section is divided into three subsections. In the first subsection, network model is discussed. The following subsection discusses the radio energy model and the third subsection will present the MACO routing protocol.

• A.    Network Model

A sensor network consists of N sensor nodes randomly distributed in a sensor field. The network is modeled as an undirected graph G (N, L), where N is a set of sensor nodes. Each node i has maximum transmission radio range with radius r meters. L is the set of two-way edges that link two sensor nodes together such that the nodes i,j e N and i * j. It is assumed that sensor nodes i and j can communicate with each other if and only if the distance between them is less than or equal to r.

• B.    Radio Energy Model

Every sensor node in wireless sensor network contains a radio communication subsystem consisting of transmitter/receiver electronics, antennae and an amplifier. In order to calculate the energy dissipated by these components, this paper adopts the radio energy model presented in [30] . The energy associated with the transfer of q bits of data packet between a transmitter and a receiver node is presented in this model.

E_e iec is the energy needed to run the electronics of the transmitter/receiver, and E_amp is the energy required to amplify the transmitted signal. The value of E_amp depends on the distance between the sensor nodes.

Given a threshold transmission distance d₀ , the free space propagation model using parameter E_fs is used when dy < d ₀ and the two-ray ground reflection model using parameter E_tr when d (j > d ₀ . Using these two models, the energy needed to amplify a signal is expressed s follows

E _

^ amp

(E F5 *d²,if d_tJ< d o [e_T R *d⁴,if d ij > d o

where d₀ and E_tr

= (-^) and the values of the parameters E_fs \ Etr'

are set to 10 pJ/bit/m2 and 0.0013 pJ/bit/m4

respectively [30] . During network operation, the average energy consumption of the sensor network is expressed as follows

N

E avg = 1/ N ^ E A ( i )                 (2)

i = 1

where N is the number of sensor nodes in a network. E _A (i) represents the difference between the initial and final energy of each sensor node, it is expressed as follows:

E_&(1)= E o — E f              (3)

where E_o and E_F are the initial and final energy of each sensor node respectively. The threshold energy E_T is determined using the remaining energy of neighbouring nodes of i. Thus, E_T is given by

E t = T^E^i)            (4)

• C.    ACO-based Routing Protocol

The development of the ACO algorithm was inspired by the observation of an ant colony. They live in groups and their behavior is governed by the goal of colony survival rather than being focused on the individual’s survival. Ants’ foraging behavior shows how ants discover the shortest path between their nest and the food source [31]. The concept of natural behavior of ants is used in ACO routing algorithms to solve energy problem in wireless sensor networks [28, 32]. Different paths can be constructed from source nodes to a destination node with more data packets dynamically sent on higher quality paths, which leads to load balancing among the sensor nodes. ACO-based routing algorithms perform better than other non-ACO based algorithms based on their iterative and proactive behavior.

• IV.    The Proposed Routing Solution

The proposed protocol is divided into two phases: discovery path phase and data transmission phase. In the protocol, when a source node has a data packet for the destination node (base station), first it checks to see if the path of the next-hop node is contained in its tabu (memory). If the path is contained, it transmits directly to the next-hop node. However, if the source node does not have the information of the next-hop node to the base station, it begins a route discovery process by sending an advertisement (ADVT) message to all the sensor nodes in its surroundings. Each sensor node retransmits the message to the neighboring node until all the nodes have received the ADVT message. Based on the routing method, each sensor node has a routing table in its tabu as presented in table 1.

• Table 1. Sensor Node Information

  S _I D	NH_ ID	sn	Current Energy	Pheromo ne value	Hop coun t	Dist. to BS	Doc ket
  a	i	1	Ec(i)	hj	b(i)	d(i,z)	0
  b	j	2	Ec(j)	^ j,k	h(j)	d(j, z)	0
  c	к	3	Ec(k	^ k,l	h(k)	d(k, z)	0
  .		N	…..

  
  

where S_ID denote source nodes identification, NH_ID represent neighbor nodes identification. Each sensor node is assigned a unique serial number S_n while the source node is initialized to zero. The number is incremented by 1 based on the distance of a node from its source node. E^c is the current energy of a sensor node, λ_i, j is the amount of pheromone value on the link between nodes i and j. Initially, the pheromone value in the network is the same. Thus, as an ant traverses the network, the pheromone value continues to change. h(i) indicates the path length from node i to the base station. d(i,z) is the distance of a node to the base station. The optimal path is determined based on the quality of pheromone on the path between a node and the base station. Finally, docket contains information about the number of ants that have visited a sensor node. It is initialized to zero, if docket = 1, it shows the current node has been visited by an ant.

The protocol uses two types of ants: search ants (SA) and backward ants (BA). SA travel from source nodes to a destination node, gathering information about the neighboring nodes and new paths as they are traversing along the paths. Similarly, the BA travel back from a destination node to the source nodes over the recorded paths that the SA travelled to update the information in each node as they traverse. Backward ants are created in order to prevent premature convergence of search ants on the constructed paths. It is assumed that the number of SA is equal to the number of source nodes; they are used to find paths from the source nodes to the destination node. A source node that wants to forward data to the destination node launches a SA and sends to the next node. When a neighboring node receives a SA, it checks its tabu if SA information is previously stored. If yes, the SA is discarded; otherwise, the sensor node saves the routing information of the SA, updates its tabu using the information in table 1 and forwards the SA to the next hop node. Other sensor nodes in the network that receive the SA likewise update their tabu and forward the SA to the next neighboring nodes until all the search ants get to the destination node. In the proposed approach, each visited sensor node is not saved in the memory of the search ant, instead the search ant saves the information of the last two visited sensor nodes only. This approach can minimize the amount of the data packets to be transmitted and saves energy. Moreover, a sensor node cannot just select another node as its next hop node, the process of selecting a reliable next-hop node is presented in section 4.1. Moreover, once a SA reached the destination, a new packet BA is created. The destination node will forward the BA to the source nodes along the paths travelled by the SA. Message format for both search and backward ants is shown in table 2.

Table 2. Message Format for the MACO Ants

Message format: P_ID NH_ID S_K Emin g sum Hop count (Hp) L(t) where P_ID represents the previous sensor node identification, NH_ID is the next neighboring node identification. S_K is the sequence number of the search ant, Emm is the minimum current energy of the sensor nodes in the route. Esum is the sum of the current energy of the sensor nodes in the route. Hop count (Hp) is the path length between a source node and the current node for a SA or the path length between the destination and the current node for a BA. L(t) is called time-to-live, it gives the number of hops that a SA can travel before it is discarded. If the value of L(t) decreases to zero before a SA reaches the base station, its message is discarded. In order to balance energy consumption among the sensor nodes and extend the network lifetime utilization, we modify the ACO transition probability equations and present them as follows.

• A.    Path Selection Procedure

Unlike conventional ACO based approaches, MACO adopts a controlled neighbor broadcast scheme in path discovery to prevent flooding the network with search ants. Paths are selected based on probability. A sensor node i will select sensor node j as a relay node based on probability value P_r(i,j,t). The value determines the probability of selecting from candidate lists a node j as a relay node. The probability is expressed as follows

Pr(i,;,t) =

( М<Ч^)Г*[М<Чф/<     .

{ 2_iг^f[ ^ i, _i( _t )] “¹ * [ _^ i, _i( _t )] “² * [ п i, _i( _t )] “³ * [ ф _i( _t )] “^{4 , if j e N} (5)

I 0                            if j E N where N,5 is the set of neighboring nodes that the SA has traversed. In order to calculate the probability value, we formulate a model for each parameter and present them below. «1, «2, «3, and «4 are the control parameters. Higher value of «1 increases the probability of choosing a link with high link cost between sensor nodes i and j.

Higher value of « 2 increases the probability of selecting a node with more residual energy from candidate list. Higher value of « 3 increases the probability of an ant taking a shorter route. « ₄ is a parameter that controls selection of the next relay node and the amount of data currently processing at node j at time t. A higher value of « ₄ increases the chances of node i selecting a path with minimum energy cost and chooses a node that processes less amount of data.

• B.    Maximizing the Reward Function

The objective function of data routing is to deliver data packets to the destination with minimum energy cost. To achieve this objective, it is necessary to assign a higher value to the weight W ij of the link l_t j between two sensor nodes with higher residual energy, so that it will have higher probability to be selected during execution. On the other hand, if the link consumes more energy for transmitting a data packet, a lower value is assigned to the weight of the link so that it will have a lower probability to be selected for data transmission. The routing consists of finding an optimal set of paths from a source node to a base station D such that sensor nodes’ energy consumption, and the delay are minimized while the throughput is maximized. The routing problem can be considered as a multi-constrained local optimization problem consisting of finding each sensor node, a subset ofits neighbors N , that solves the following routing problem

Max Eje^ toijXj(6)

Subject to

Pr(i,j, t) > Pr(i, l, t) if ^M (t) > ^ (t)(7)

Pr(iJ,t) > Pr(i,l,t) if n,,j

Pr (i,j, t) > Pr (i, l, t) if фj (t) < Ф1 (t)

x- E {0,1}                  (10)

where ш^- is the weight of the link between two sensor nodes, variable x- is one if and only if node j is contained in the routing path of neighboring nodes N_t; otherwise it is zero. P_r(i,j,t") is the probability that node i selects node j as the next hop to the destination at time t. fi,j(t), П_1;- and ф₇•(t) are probability functions that determine the choice of selecting the next-hop node and they are determined as follows

• i)    Link weight( Шц)

E0-mm(Ec(l),EcU))  T

“» =—^—*Tp

E_q is the initial energy, E^c (i) is the current energy level of node i, C[,j is the link quality between nodes i and j. T_p is the transmission power, (t) is the time taken to transmit data from node i to j.

• ii)    Current energy level of a sensor node:

The current energy of neighboring nodes N influences the likelihood of node i selecting node j E N_t as the next-forwarder node. The energy metric is expressed as follows

^,j(t) = у      '_m          (12)

^,j           LlEN_t,^EC(4^(t)

This equation enables a node with higher current energy level has higher probability to be selected as the next-hop node.

• iii)    Sensor node location information

In designing a good routing protocol, location information is needed in order to determine the distance between two sensor nodes so that energy consumption can be calculated. Thus, location information can be exploited in transmitting data in an energy efficient way. The distance between the neighboring nodes significantly influences the probability at which node i selects j as the next-hop node. The location function, П^- is defined as follows

Пц = — JE^ (13) LlENp dl,D where dj,D is the distance between sensor node j and the base station D. This equation enables node j E Nt closer to the destination node has higher chances to be selected as the next forwarder node. However, if there is no any closer node to choose, then the SA returns to the former hop node and it is added to the tabu list of the SA.

• iv)    Data packets delay

Data packets transmission may be delayed if a receiver node j is processing large amount of data packets. Other data packets have to wait in a queue till the processing is completed at time t + 1. This increases the total delivery time of data packets. a- (t) denotes the delay value for node j and is expressed as follows a,-(t) ф() =                  (14)

^j           LlEN_i,^al^(t)

Equations (12) – (14) ensure that those sensor nodes with low residual energy, long communication distance, high load will have a lower chance of being selected as relay nodes. As presented above, the multi-constrained routing problem is a local optimization problem consisting of finding a minimal set of neighbors that maximizes throughput, minimizes energy usage and delays. Thus, an ant at node i selects node j according to the probability transition rule in equation (5) and deposits pheromone as it is moving along the paths to the destination node. The quantity of pheromone each search ant deposited on the path between nodes i and j is determined by this equation

^/i,j     ^{

^/max

^/min

if 5M> /_ if /min < 8ц < /max if 5 ц < /min

₅= hm--Hp^ * e™0      (16)

“1           Hp where /min and /max are the lower and upper bounds imposed on the amount of pheromone deposited on the paths respectively. Hmax denotes the maximum allowed number of hops for ants in the network, H p has been defined above and E™8 is average energy of sensor nodes that a search ant has visited. The pheromone limit values are introduced to prevent ants to converge quickly on a small number of edges which can cause the algorithm to be trapped in local optimal [33]. This makes the pheromone concentration to be controlled in a moderate range and effectively prevents local optimal convergence. The lower and upper bound values are defined as follows

_ (M-m)

^/min      ^                    ⁽¹⁷⁾

and

/max = 1000 * (M - m) + ^    (18)

where m and M are the minimum and maximum edge costs respectively.

• C.    Pheromone Update

Once all ants have constructed the paths, the pheromone level is updated. The amount of pheromone value deposited on the path between node i and j at time t is updated by equations (19) and (20)

^-i,i(t + 1) =

max { Лт^,тт{(1 - p^/t) + AAu(t + 1), Amaz}}

^At ■ 1) -ф /h '.,„,)    ⁽2⁰⁾

where p (0 < p < 1) is the pheromone evaporation rate; it is used to vary the intensity of the existing trail over time. ф is the impact factor. AA,,, is the quantity of pheromone left by an ant on the edge (i,j) in the discovery process. Thus, the value of A/^; is set to zero if a search ant does not traverse through the edge. Other terms used in the expressions have been defined above. Algorithm 1 represents the basic operation of a search ant for MACO. Thus, after all search ants have reached the destination node, then the destination node creates response packets BA.

Algorithm 1: Proposed search ants algorithm for MACO

Begin

• 1:    Initialise the number of SA in the network

• 2:    if L(t) <> 0 before SA reaches the destination then

• 3:  A SA is launched at the source node

• 4:    else

• 4:    discard the message

• 5:    if node i is a destination node then

• 6:   create a BA;

• 7:    else

• 8:    choose node j as the next neighbour node using equation (5) and send

• 9:    SA to the node

• 10:   update the current energy of nodes i and j

• 11:      if next node selected is visited then

• 12:     return to the preceding sensor node

• 13:        select another sensor node as the next relay node

• 14:  using equations (19)- (20) to update the pheromone

value of link (ij);

• 15:  end if

• 16:    end if

• 17:    end if

• 18:    End

using equation (21) and decrements the variable 5„ such that when the first set of backward ants get to the source nodes, these variables are reset to zero for subsequent ants. The quantity of pheromone trail deposited on the path as it is moving towards the source node is determined as follows

^t,i(t + 1) —

max { Amin,min{(1  p)Atj(t) + AAtj(t + 1), Amax}}

1⁽amax^—ap)*^avg ^avg*Op

0,

, if ant traverses on edge (i, j) otherwise where Hmax denotes the maximum number of hops for ants that can traverse in a network, Eavg is average energy of sensor nodes that an ant has visited. The update rule is determined as follows

at^ (t + 1) — (1- pyrtJ (t) +   ..'      (23)

1                                       1              I *Dj| where Y is a coefficient and S„ is the number of sensor nodes visited by the backward ant. Thus, after the node has updated all the parameters, it sends the backward ant to the next hop node on the path. Once each backward ant reaches the source node, it is discarded. This process creates paths between the source nodes and the destination node where source nodes can transmit their data to the destination node. Algorithm 2 contains backward ants algorithm for the proposed protocol.

The pheromone trail update defined from equations (19) – (23) consists of i) pheromone deposit ii) pheromone evaporation. The pheromone deposit is adding a chemical substance to the paths constructed by the ants. The pheromone evaporation is an exploration mechanism used to avoid pheromone concentration along the optimal paths from being excessively high and encourages ants to explore non-optimal paths [34]. Thus, after all the constructed paths have been updated, optimal path found by the ants in the current iteration is stored. When a sufficient large number of iterations is reached or the maximum computation time is obtained after all the iterations, the optimal solution is used for data transmission. The best solution is selected through minimum path cost defined by gbest — minZN-^TCxi+r-xi^^+Tyi+r-yi)2 (24)

In order to evaluate the proposed protocol, 20 sensor nodes are randomly distributed as shown in Fig. 2. The network consists of a source node (S), 18 sensor nodes and a destination node (D), and Ec denotes the current energy of each sensor node. The source node launches a search ant to find paths to the destination node while a backward ant updates paths found by the search ant in order to determine the optimal path from source node to the destination node.

Algorithm 2: Backward ants algorithm for MACO

Begin

• 1:    if node i has reached the destination node then

• 2:    create a new backward ant (BA)

• 3:    Backward ant traverses along the path constructed by the SA

• 4:    if BA has not reached the source node then

• 5:    update the link( i,j) with the pheromone value obtained from equations (21) – (23)

• 6:    compute the E""", E^su™ and path length

• 7:    if a BA reaches the source node then

• 8:    compute the optimal path between the source node and the base station

• 9:  end if

• 10:    end if

• 11:    end if

• 12:    repeat step 1

• 13:    End

Fig.2. Sensor nodes distribution and current energy of the nodes

Table 3 shows the result that was obtained.

As suggested earlier, the proposed protocol consists of the following metrics i) link cost between node i and node j ii) the remaining energy level at node j (next-hop node) iii) the sensor nodes’ location information iv) the amount of data currently processing at node j. These four metrics are mapped into a new ACO probability transition as expressed in equation (5).

Table 3. Results Obtained Based on the Proposed Algorithm to Determine the Optimal Path from the Source Node (S) o the Destination Node (D) with 20 Sensor Nodes

Paths from S to D	No. of Nodes	No. of links	Next hop node	Pheromone	Probability	Optimal path
S-1-7-11-10-13-18-D	8	7	1	19.4	0.26	No
S-1-7-11-10-13-14-D	8	7	1	19.1	0.95	No
S-1-8-10-13-14-D	7	6	1	18.8	0.84	Yes
S-1-8-10-13-18-D	7	6	1	18.5	0.69	No
S-1-7-11-12-13-14-D	8	7	1	16.3	0.72	No
S-1-7-11-12-13-18-D	8	7	1	17.2	0.81	No
S-1-7-11-12-17-18-D	8	7	1	17.8	0.27	No
S-4-7-11-12-17-18-D	8	7	4	15.4	0.38	No
S-4-7-11-10-13-14-D	8	7	4	13.6	0.55	No
S-4-7-11-10-13-18-D	8	7	4	16.7	0.71	No
S-2-5-15-16-D	6	5	2	14.5	0.46	No
S-2-5-6-14-D	6	5	2	16.9	0.52	No
S-2-3-9-14-D	6	5	2	17.8	0.67	No
S-2-5-15-14-D	6	5	2	15.6	0.38	No

• E. Data Transmission

After multiple paths have been constructed, the data packets are transmitted through an energy efficient path. When a sensor node i receives a data packet destined for a base station (destination node), it forwards the data to the next-hop node j based on probability defined above. However, if node i has no information of node j in its tabu, it forwards the data packets to a neighboring node j that has sufficient energy and minimum delay of a path. However, if sensor node i has no next hop-node, the data packet is discarded. In order to keep alive and maintain the path, the proposed protocol updates the pheromone value dynamically. The optimal path constructed between the source node and the destination node will be used for data transmission to the base station. Thus, in a dynamic sensor network, pheromone control is used as a mechanism for the dynamic reconfiguration of the network to find newer optimal paths when the previously discovered path becomes congested or unavailable for data transmission. Pheromone control is used as a measure to reduce the impact from earlier experience and encourages the search for new paths that were previously non-optimal. For instance, at time t, all ants travel along the optimal path and converge to a destination node D. They leave a very high concentration of pheromone on the optimal path denoted with bigger circles in Fig. 3. At time t,+1, the pheromone concentration is reduced by a factor p and denoted with lighter circles. At time t,+2, the pheromone concentration is further decreased by some factors as shown in the figure. It continues to decrease until the pheromone on the optimal path has evaporated. This encourages a search for new paths that were previously non-optimal by subsequent ants at each iteration. This enables several ants to produce different solutions during one iteration. In this case, QoS routing can be used to save the micro-cloud energy stored in the batteries and thus prolong the lifetime of the cloud-IoT infrastructure.

base station.

• • Performance of EARA is the worst among the protocols because it always uses the primary path constructed for its data transmission.

  

  Fig.3. Pheromone evaporation

  
  
  
  
  

Table 4. Simulation Parameters

Parameters	Values
Number of sensor nodes	100 ~500
Network dimension	200m * 200m
Eelec	50nJ/bit
Packet size	96 bits
Transmission range R	50 m
pheromone (p) value	0.8
Threshold energy	0.75 J
Transmission energy	0.0013pJ/bit/m4
Receive energy	10pJ/bit/m2
Simulation time	1000 sec
Transmit data rate	250kbps
Physical and MAC model	IEEE 802.15.4

• V.    Simulations and Results

Performance of the proposed approach is evaluated considering the following performance metrics: energy consumption, average transmission delay, packet delivery latency and network lifetime. The sensor nodes are randomly distributed in a network area of 200m * 200m and the initial energy of every sensor node was set to 1.5Joule. Table 4 contains parameters used in the simulation and a MATLAB-based simulation tool is used for the implementation. The performance of the scheme is compared with other related routing protocols, namely FACOR [25], EARA [26] and EAMR [28, 35]. The number of sensor nodes varied from 100 to 500. The simulation runs were repeated 75 times to get the average results which are used for plotting the figures.

• A.    Network Lifetime

The sensor network lifetime for the routing schemes is shown in Fig. 4. It reveals that in all these schemes, the network lifetime increases with the network size, but only slightly.

Fig.4. Sensor network lifetime

• B.    Energy Consumption

Further experiments were conducted to compare the energy consumption of the proposed protocol with other three protocols and presented the result in Fig. 5. The result shows an increase in energy consumption in all the networks. EAMR and MACO consumed less energy compared to FACOR and EARA protocols. The reason is that data loss in EAMR is minimal, as it uses an alternate path if the primary path fails. MACO implements a proactive approach that considers the residual energy of the receiver node before data transmission, thus reducing data loss and minimizing retransmission of the data packet. This leads to higher efficiency and lower energy use. EARA consumed the highest energy among the four protocols, because it focused on a collision avoidance model that did not translate into energy efficiency. By combining four routing parameters into a mixed routing metric, MACO outperformed the other three protocols.

Fig.5. Comparing the energy consumption

• C.    Throughput

Throughput is defined as the amount of data successfully transmitted from a source node to a destination node in a specific amount of time. Fig. 6 shows the throughput obtained by the four routing schemes for different sensor network sizes varying from 100 to 500. It is observed that as the number of sensor nodes increases, throughput for each protocol likewise increases. This might result from the protocols being able to find more parallel paths between the nodes and the base station. The throughput of MACO is significantly larger than EARA, FACOR and EAMR protocols. The reason is that MACO computes a minimal set of good parallel paths that optimize its mixed metric.

Fig.6. Throughput versus number of sensor nodes

• D.    Packet Delivery Ratio

Packet delivery ratio is the percentage of data packets delivered successfully to the base station. Fig. 7 shows the data packet delivery ratio for different network sizes. These results are in agreement with the throughput results obtained above. MACO outperforms the other protocols as it does not dissipate neither energy nor route packets on non-optimal paths. It is observed that the packet delivery rates for the proposed protocol almost remain constant with the increase in network size. This reveals that as a relative measure, the packet delivery ratio can be considered as a metric that characterizes each of the routing protocols.

Table 5 shows average energy consumption for all the protocols. As explained above, the total energy consumption increases as the network size increases while the average energy consumption of sensor nodes decreases. Thus, MACO consumes the least of energy compared to EAMR, FACOR and EARA protocols.

Fig.7. Packet delivery ratio versus number of sensor nodes

Table 5. Average Energy Consumption

Energy consumption (10-6 J)	Number of sensor nodes
	100	200	300	400	500
EARA	9.245	5.801	4.491	3.791	2.904
FACOR	8.937	5.745	4.326	3.465	2.793
EAMR	8.507	5.683	4.159	3.247	2.726
MACO	8.214	5.619	3.864	2.516	1.983

• E.    Data Packets Transmission Reliability

Data packets transmission reliability for the four protocols is investigated using a network size of 200 sensor nodes randomly distributed over a 200*200 m2 network area. Fig. 8 shows the average data packets transmission reliability taken by the sensor readings for the four protocols. MACO presents the highest data packets reliability compared to EAMR, FACOR and EARA protocols. The reason is that the proposed protocol is able to dynamically reconfigure the network to find newer paths after a certain period to avoid loss of data packets along the optimal path. Finally, it is able to select a node that processes less data as a relay node which reduces queueing delay.

Fig.8. Packets transmission reliability

• F.    Standard Deviation of Energy

This metric gives the average variance between current energy levels on all sensor nodes. Standard deviation of the current energy at the interval of 100 communication rounds is computed and the result is presented in Fig.9. The proposed approach has resulted in uniform energy dissipation by the sensor nodes. MACO shows a significant reduction on the standard deviation compared with selected protocols. Hence, it shows that MACO can efficiently balance the energy consumption on all the sensor nodes.

Fig.9. Standard deviation of current energy of sensor nodes

• G.    Packet Delivery Overhead

Packet delivery overhead is defined as the ratio of the number of data packets forwarded during the route establishment and data transmission processes to the number of data packets received at the base station. Fig. 10 and Fig. 11 show MACO, EAMR, FACOR and EARA packet delivery overhead for 100 sensor nodes and 500 sensor nodes respectively. Packet delivery overhead increases as the packet generation rate increases for the two network sizes considered in all the protocols as shown in the figures. Increments in overhead are due to the fact that increasing the number of sensor nodes results in an increase in the number of data packets transmission along multiple paths to the base station. Thus, MACO reduces the packet delivery overhead by 31%, 47% and 58% compared to the EAMR, FACOR and EARA protocols respectively for a network size of 100 sensor nodes. Similarly, when the number of sensor nodes is 500, packet delivery overhead in MACO decreases by 42%, 58% and 65% compared to the selected protocols. The reasons for these variations can be explained as follows. First, EAMR, FACOR and EARA protocols use a flooding mechanism to establish multiple paths between the source nodes and the base station. On the other hand, MACO reduces packet delivery overhead using a minimal subset of neighboring nodes in the route establishment process. Second, based on the MACO approach, the constructed paths incur a minimal number of transmissions per packet delivery compared to the three protocols. MACO has the least packet delivery overhead, hence it saves more energy.

Fig.10. Packet delivery overhead against packet generation rate (pps) for 100 sensor nodes

Fig.11. Packet delivery overhead against packet generation rate (pps) for 500 sensor nodes

• H.    Death of Sensor Nodes

The experiments were performed by varying the initial energy assigned to each sensor node. Table 6 provides the study of sensor nodes’ lifetime for all the four protocols considered. We are able to determine the number of rounds passed when 5%, 15%, 25%, 35% and 50% sensor nodes die with base station location at (100, 275)m. The results show that MACO performs better than EAMR, FACOR and EARA protocols before 50% of the sensor nodes die. Moreover, it is observed that FACOR shows an improvement over the proposed protocol after 50% sensor nodes die. This is due to many parameters introduced into the scheme.

Table 6. Number of Rounds till Death of Sensor Nodes

Energy (J/node)	Protocol	Percentage of sensor nodes death
		5	15	25	35	50
0.5	EARA	904	1028	1136	1194	1317
	FACOR	965	1032	1151	1245	1342
	EAMR	972	1054	1178	1263	1378
	MACO	985	1087	1185	1279	1379
1.0	EARA	2104	2276	2373	2465	2584
	FACOR	2165	2305	2380	2492	2596
	EAMR	2187	2319	2391	2510	2611
	MACO	2204	2326	2413	2536	2604
1.5	EARA	2710	3012	3215	3295	3365
	FACOR	2762	3114	3246	3306	3384
	EAMR	2831	3158	3261	3323	3391
	MACO	2942	3184	3275	3314	3387

• VI.    Conclusion and Future Work

This paper revisits the ant colony optimization – a meta-heuristic method for solving combinational optimization problems with the goal of modelling and QoS implementation of wireless in sensor networks. An energy-efficient routing protocol based on ACO that builds upon a mixed metric and its mapping into efficient pheromone distribution to achieve local optimizations with the expectation of reaching global routing efficiency is proposed. Simulation results show that, building around its local optimization, MACO performed better than selected routing protocols (EAMR, FACOR and EARA) in terms of energy efficiency, throughput maximization and delay minimization in sensor networks. Service and application aware routing through service differentiation are key features that can play a key role when provisioning QoS in IoT deployments. In the case of visual sensor networks, they can be used to protect the services and applications running on some specific visual sensor motes. Using the service-aware routing paradigm in [36], MACO can be extended into a service aware multipath ant colony optimization (SAMACO) algorithm that routes the sensor readings according to the motes’ service requirements. Differentiation of services can also be built around the path aware routing algorithms proposed in [37] where parallel paths are computed from the source nodes to the sink of the network, but constrained by specific QoS requirements for each path. These include requirements based on QoS metrics such as delay, energy, throughput and reliability or any other relevant metrics. Building upon the studies referred to the Ant Colony Optimization Approach above, QoS extensions can be performed in both IoT and lightweight cloud computing platforms through efficient traffic engineering. These extensions are potential avenues for future research work.