Frog-Based Routing Algorithm to Enhance the Network Lifetime of Wireless Sensor Networks

Published Online August 2017 in MECS DOI: 10.5815/ijcnis.2017.08.02

In the recent years, we find some WSN Protocols developed by the inspiration drawn from the collective behaviour of insects and animal societies [2]. We presented such evolutionary behaviour observed from the environment and incorporating similar techniques in different areas of WSN in our survey paper [3]. Some of the Bio-inspired Algorithm like PSO, ACO, BEES optimization, Elephant optimization, Cuckoo search, Bat Algorithm, Firefly Algorithm and Genetic Algorithm are discussed briefly in the survey paper. This paper proposes a bio-inspired Frog-Based Distributed Routing for WSN that establishes a routing path from source to sink, considering the nodes that have high residual Energy. Our proposed Algorithm is capable of identifying a routing path such that, there is an equal consumption of Energy by all the nodes which aims at maximum Lifetime of the Network. Simulation results for different performance metrics like Energy, Throughput and Packet delivery ratio are obtained and also compared with two other Energy Efficient Routing Protocols. The organization of the paper is as follows: In Section II we discuss Routing Protocols and Swarm Intelligence based Routing Protocols in WSN and the related work, Section III describes the Frog behaviour and incorporation of such technique in routing for WSN, Section IV presents the Algorithm and simulation results, Section V provides the comparative performance analysis of the proposed Frog based Routing algorithm with LEACH and SPIN protocol and finally we conclude the paper in section VI.

• II.    Routing And Related Work

Flat based Routing, Hierarchical based Routing and Location based Routing are the three categories of Routing [4].

Flat based Routing: Flooding is a technique used to build the Routing table. All the nodes are equal and perform similar functions of collecting the data and also act as relay nodes in transmitting data. Further the Flat based can be classified into three modes as: Traditional Flooding, Event driven and Query-driven Modes. In Traditional Flooding mode sensor nodes broadcast the received information to the neighbouring nodes until they reach the sink node. In Event driven mode, routing table helps in choosing the next hop and the sensed messages are broadcasted to the sink. SPIN, Rumour Routing, Energy-aware Routing are the different Event driven Protocols. Further in Query- driven mode, application specific request is broadcast by the sink node to its neighbours and the nodes that are requested would respond to it. Direct Diffusion and Gradient based Routing are the Query driven mode Protocols.

Hierarchical based Routing : The entire Network is divided into clusters. The different Layers help in choosing the cluster head and Routing. LEACH and PEGASIS are the single layer Hierarchical based Routing Protocols while TEEN, APTEEN and Cluster based Energy-aware Routing are Hierarchical tie-based.

Location based Routing : Also called as Geographic Protocols, assume that location is known to sensor nodes or computed, to transmit the data directly. Storm caused by Flooding can be avoided in this Routing. GEAR and MECN are the popular location based Routing.

Further Routing can be classified as Centralized and Distributed. In Centralized, the Routing is taken care by a single node called Sink. On the contrary in Distributed Routing, the information is gathered by every node, on its own and no topology information needs to be exchanged among the neighbouring nodes. Popularity for distributed WSNs is growing in the recent years. It has wide range of applications being robust to any network changes and is suitable for Dynamic Networks.

There exist some Protocols that are based on Swarm Intelligence principles. Swarm Intelligence is a science, addressing the behaviour of insects and animal societies that inspire in designing effective Routing Algorithm in a distributed manner. These Algorithms exhibit adaptability, scalability, flexibility and robustness which are the required properties for any Routing Protocol. Some of the works related to Swarm Intelligence are discussed below:

In Ant Colony Optimization (ACO) Routing, foraging behaviour of some Ant species forms an inspiration for developing the Routing Protocol. The Foraging behaviour can be described as follows: The first Ant goes in search of food and when back to the nest leaves behind the Pheromone trail. All other Ants follow similar such ways and the strengthened runway will indicate the shortest route. This is incorporated in WSN in solving dynamic and distributed problems of Routing [5]. Paper [6] gives a comprehensive overview of bio-inspired techniques which include Ant based and Genetic based approaches in solving Routing in Sensor Networks. Energy supply being a serious constraint of WSN, the authors of Paper [7] propose a Routing Algorithm based on ACO considering the path delay and balanced Power consumption to achieve dynamic and adaptive Routing. Aiming Network Lifetime to the maximum, Paper [8] presents a novel Routing approach that optimizes Routing and provides an effective multipath transmission of data using ACO Algorithm. Authors of Paper [9] developed an algorithm based on the behaviour of Queen-Ant in Ant colony, for transmission of remote information thus fulfilling long distance communication. Foraging behaviour of Honey Bees which, exhibit selforganization and division of labour acts as an inspiration to the authors of Paper [10]. A Routing algorithm is developed for wired networks with discovery of route on-demand. Comparison of the same is performed with FP-Ant, EEABR and AODV. The main objective of the authors of paper [11] was to design and develop new approaches for Routing attack which pose a major threat. This work is again inspired by the Bee and Ant Swarm attacks. The Authors of paper [12] propose a model based on the mobility of the Ant to develop a multipath routing algorithm that coordinates the nodes and control the power while communicating in Wireless Networks.

The Authors of Paper [13] have developed a Routing algorithm UFCA, which is Energy efficient for under water WSN inspired by Ultrasonic Frog calling. This algorithm does not require periodic flooding of messages or fixed routing tables for discovering the Routing path. The algorithm provides an optimal routing path in 3D under water WSNs with harsh conditions and taking into consideration the Energy consumption. Further the simulation results of UFCA are compared with Vectorbased forwarding and Energy Efficient Routing Protocol. Inspired by such work, this Paper proposes an FBR algorithm for Terrestrial WSN with a distributed approach, utilizing sleep schedule technique and equal consumption of Energy to Enhance the Network Lifetime. Simulation results are compared with LEACH and SPIN Protocols.

• III.    Frog Calling Behaviour and Proposed Routing

Frogs and Toads during their courtships and mate assessment, produce a rich variety of sounds and call. Sound produced are stereotypes in order to advertise their territory and also their location. Frogs that are listening respond by calling back or by going silent. The female Frog makes the initial call and in response to it the neighbouring male Frogs produce advertisement calls. Random calling of Frogs will overlap the calls causing interception and thus the female Frog will not be able to identify the call. During chorus calls an individual Frog keeps track of who calls, listening to their neighbour before calling in order to avoid overlapping of calls which leads to interference. Frogs exhibit self-organized calling behaviour by calling alternately to reduce the interception and conserve the Energy [14]. This selforganized Frog behaviour with sleep scheduled technique was incorporated for scheduled data transmission in WSN was presented in our earlier Paper [15].

Frog calling is linked with Physical size and female Frogs move towards the bigger Frog with louder call which also indicates to be the nearer one, thus establishing a path for itself. Other Frogs on hearing to the louder call go silent and hence conserve the Energy

[13], [16]. This paper incorporates a similar concept to identify a node with higher residual energy called as the Active node among the neighbouring nodes and develop an FBR Algorithm to establish Routing path in WSN. FBR algorithm is a sleep scheduled Energy efficient bioinspired distributed Algorithm. Simulation is carried out using Network Simulator NS2. Considering a WSN with random deployment of nodes, we assume that location of every sensor is known in the network. We identify a routing path considering the highest residual Energy node moving in a forward direction from source to destination. Neighbour discovery and Active node selection are two stages in identifying the Routing path consisting of Active nodes with high residual Energy through which the data is transmitted to sink.

Neighbour Discovery : The source node when ready for transmission of data broadcasts a message called ready to transmit to its neighbouring nodes that are within its transmission range similar to the call made by a female Frog. The boundary threshold for nearest neighbour is considered here as 250 meters. The neighbouring nodes whose distance to the sink is less than the distance between the source and the sink are chosen as neighbours considering the routing path in the forward direction.

Representing with notational terms, let us consider a WSN with number of nodes represented by λ, then the boundaries of WSN is given by:

Δ T n { λ }                      (1)

where,

Tn, represents the total node vector.

Selection of the source and the destination node randomly given by:

Δ n (T n [0, λ- 1])               (2)

Source node is uniformly distributed from 0 to λ-1 nodes.

Equation (4) and (5) gives the position of source and destination node.

Position of nodes individually to t 1 , t 2 is given by:

t₁ = s_n x - d_n I ^xI

t₂ = s_n y - d_n I ^yI

The distance is calculated by using the Euclidean distance formula as:

D =V (t₁ ∗ t₁) + (t₂ ∗ t₂)                (8)

Active node selection: The neighbouring nodes now exchange their residual Energy among themselves in a scheduled manner on a round robin fashion to avoid collision similar to the alternating Frog call behaviour. Once the nodes receive the other nodes energy message they compare with its own & if observed less will go to sleep mode until once again a node sends a broadcast message for transmission. R E is a function that gets all the residual energies of the neighbouring nodes given by

λ-1

R E ⇐ ∫ E 0

RE, the Residual Energy is calculated as follows: The Initial energy of the nodes,

I n ← ( β∈ R E [0,1,.....n])

The Final energy of the nodes,

F n ← ( β∈ R E [0,1,....n])

Residual Energy is given by, dn(Tn[0,λ-1])                (3)

R E I F_n - I_n

Destination node is uniformly distributed from o to λ-1 nodes.

[P_i j ], is similarity matrix containing the position of all the nodes. Similarity matrix indicates WSN Position boundaries.

Distance matrix X ⇐ [d] , provides the source and destination node position as coordinates.

To get exact WSN position of source or destination node, we use X vector position boundaries.

S n [X,Y] = ∑ X

D n [X,Y] = ∑ X

The neighbouring node with highest Residual Energy is identified as follows:

,

To obtain the residual energy from the forward neighbour, t =R(Cn,→fn(n))[X1]

Exempting all the preceding nodes (C n ) from the main node vector (T n ) and to get the neighbour from all the nodes in forward direction,

N n = T n (t)                  ₍₁₄₎

POS = POS (N )

Equation (15) gives the current node position.

T n (N n → D n )

Equation (16) indicates the transfer the packets from the current node to the neighbouring node.

The female Frog listens to its neighbours call and identifies a Frog with a louder call indicating a bigger size Frog and approaches towards it. Similar to the Frog behaviour, the node in WSN which has the highest residual Energy is chosen as Active node and hence a path is established for the transmission of data from source to the Active node. The Active node now identifies its neighbour and finds the next Active node among its neighbour and this is repeated until the Sink is reached. Thus a Routing path with high residual Energy node is established from source to sink with intermediate Active nodes. By choosing the highest residual energy nodes for transmission of data and inducing the other nodes to go to sleep, the Energy is conserved with enhancement in Network lifetime.

The above process is depicted diagrammatically in Fig. 1. Routing process is represented in six stages. In the first stage the source node and destination node being the sink are selected. In the second stage the neighbours to the source are discovered. Further in the third stage an Active node is identified which represents the node with highest residual energy among the neighbouring nodes. New neighbours are discovered to the present Active node in stage four and in stage five the process of identifying the next Active node among the neighbours is repeated. Finally, the stage six shows the Routing path developed from source to sink.

Fig.1. FBR Routing Process

• IV.    Algorithm and Simulation Results

Simulation was carried out using NS2 Network Simulator for Frog based Routing Algorithm. The notations used in the network model and their descriptions are listed in Table 1.

• Table 1.    Network Parameter Notations

  Variable	Description
  λ R t N n d as d ns	Number of Nodes in the Network Transmission range Node with highest residual Energy Distance between Active Node and Sink Distance between Neighbouring node and Sink

Consider a WSN with random deployment of nodes whose location is represented by X and Y coordinates. Table 2 below gives the Algorithm for Frog Based Routing in Steps. This algorithm identifies the nodes with highest residual energy here called as Active nodes from the source to the sink in a forward direction, thus establishing a Routing path. By considering the nodes with higher residual Energy we prolong the Network Lifetime with equal consumption of Energy by all the nodes.

• Table 2.    Frog Based Routing Algorithm

Input: WSN with Nodes deployed randomly with X & Y coordinates;

Outpu : Active node, Routing path;

Random topology is created with λ nodes.

Select Source and the Sink.

Let the Source be Active Node while (Sink is not reached)

Compute the distance d_as

If d as < R t

Transmit data to Sink else

Active node broadcasts - ready to transmit message

Identify the nodes in Rt range

Compute the distance dns of all nodes in this range to Sink if dns < das

Node discovered as a neighbour

Neighbours exchange the energy to identify Nn

N_n is declared as current Active node

Other neighbours go to SLEEP mode

Transmit data to Active node

Endwhile

Fig. 2 shows the residual Energy of all the nodes in the Network for FBR. From the graph we analyze that Residual Energy is nearly the same in all the nodes varying from 49 to 50 joules thus achieving equal consumption of energy and load sharing. This equal consumption of energy and load sharing which is required such that all nodes die around the same time to enhance the Network Lifetime.

Fig. 3 depicts the graph of Packet delivery Ratio. We can observe that the ratio is less initially, because the first stage comprises of identification of neighbours. The ratio goes to maximum of 90% during the transmission of data.

Fig. 4 is a graph showing Throughput. Throughput is high as there is no disruption in Packet delivery.

Fig.2. Residual Energy vs Nodes

Fig.3. Packet delivery Ratio Vs Time

Fig.4. Throughput vs Time

• V.    Performance Analysis of Fbr Algorithm with Leech And Spin Protocols

The graphs showed below makes a comparative performance analysis of FBR with LEACH and SPIN Protocols. In Fig. 5, Packet delivery ratio of FBR algorithm is high initially and later reduces slightly because of time gap in accessing files for distance and Energy.

Fig.5. Packet delivery Ratio of FBR, LEECH and SPIN vs Time

Fig. 6 shows the residual Energy graph for FBR, LEACH, and SPIN. The residual Energy of all the nodes in FBR is quite high compared to LEACH and SPIN Protocols as they share the same level of residual Energy.

Energy consumption of all the nodes in FBR algorithm is nearly equal varying from 40 to 50 joules which depicts efficient load sharing. Throughput of FBR in Fig. 7 is very high as there exists, a successful delivery of packets compared to LEACH and SPIN.

Fig.6. Residual Energy of FBR, LEECH and SPIN vs Nodes

Fig.7. Throughput of FBRA, LEECH and SPIN vs Nodes

• VI.    Conclusion

Enhancement of Network Lifetime with Energy Efficiency is the essential design requirement for any WSN. Routing being a challenging concern, research on routing protocols is one of the important research areas. We in this paper, inspired by the Frog behaviour have developed an Energy Efficient Distributed Routing algorithm that establishes a Routing path conserving the Energy using sleep scheduling technique. This algorithm utilizes the nodes with high residual Energy and considers only those nodes which are in a forward path, as neighbours for transmission of sensed data. Energy utilization, Throughput and Packet delivery ratio are the metrics used to evaluate this Routing algorithm. Simulation was carried out and results were compared with LEACH and SPIN Routing Protocols for performance analysis. As a future work the performance of this protocol can be analysed with other distributed Routing Protocols.