Fast-converging chain-cluster-based routing protocols using the Red-Deer Algorithm in Wireless Sensor Networks

Abstract

Purpose

The performance of Wireless Sensor Networks (WSNs) applications is bounded by the limited resources of battery-enabled Sensor Nodes (SNs), which include energy and computational power; the combination of which existing research seldom focuses on. Although bio-inspired algorithms provide a way to control energy usage by finding optimal routing paths, those which converge slower require even more computational power, which altogether degrades the overall lifetime of SNs.

Design/methodology/approach

Hence, two novel routing protocols are proposed using the Red-Deer Algorithm (RDA) in a WSN scenario, namely Horizontal PEG-RDA Equal Clustering and Horizontal PEG-RDA Unequal Clustering, to address the limited computational power of SNs. Clustering, data aggregation and multi-hop transmission are also integrated to improve energy usage. Unequal clustering is applied in the second protocol to mitigate the hotspot problem in Horizontal PEG-RDA Equal Clustering.

Findings

Comparisons with the well-founded Ant Colony Optimisation (ACO) algorithm reveal that RDA converges faster by 85 and 80% on average when the network size and node density are varied, respectively. Furthermore, 33% fewer packets are lost using the unequal clustering approach which also makes the network resilient to node failures. Improvements in terms of residual energy and overall network lifetime are also observed.

Originality/value

Proposal of a bio-inspired algorithm, namely the RDA to find optimal routing paths in WSN and to enhance convergence rate and execution time against the well-established ACO algorithm. Creation of a novel chain cluster-based routing protocol using RDA, named Horizontal PEG-RDA Equal Clustering. Design of an unequal clustering equivalent of the proposed Horizontal PEG-RDA Equal Clustering protocol to tackle the hotspot problem, which enhances residual energy and overall network lifetime, as well as minimises packet loss.

Citation

Dayal, K. and Bassoo, V. (2022), "Fast-converging chain-cluster-based routing protocols using the Red-Deer Algorithm in Wireless Sensor Networks", Applied Computing and Informatics, Vol. ahead-of-print No. ahead-of-print. https://doi.org/10.1108/ACI-10-2021-0289

1. Introduction

Wireless Sensor Networks (WSNs) can be defined as an ad hoc network of wirelessly interconnected Sensor Nodes (SNs) deployed over a large geographical area. These tiny devices are equipped with three basic capabilities, namely sensing, communication and processing [1]. After sensing and collecting data from the SNs, they are routed to a Base Station (BS) for further processing [2].

Being affordable in cost and lightweight in size, the nodes can easily be deployed in huge quantities at any location of interest [3, 4]. The four main underlying components of an SN include the sensing, computing, communication and power unit [5]. Battery-enabled SNs are expected to operate for long periods without any replacement [6]. However, constraints such as computational power and energy still remain to be some of the prime concerns [7]. Although energy-efficient techniques such as clustering, data aggregation and multi-hop transmission address the limited energy availability of SNs, routing protocols still consume too much computational power. Hence, the following contributions are presented in this paper [8]:

1. Proposal of a bio-inspired algorithm, namely the Red-Deer Algorithm (RDA) to find optimal routing paths in WSN and to enhance convergence rate and execution time against the well-established Ant Colony Optimisation (ACO) algorithm.

2. Creation of a novel chain cluster-based routing protocol using RDA, named Horizontal PEG-RDA Equal Clustering.

3. Design of an unequal clustering equivalent of the proposed Horizontal PEG-RDA Equal Clustering protocol to tackle the hotspot problem, which enhances residual energy and overall network lifetime, as well as minimises packet loss.

The rest of the paper is structured as follows: Section 2 reviews some routing protocols in the literature. Section 3 sheds light on the system model and Section 4 provides comparative analyses between RDA and ACO. Section 5 presents the proposed routing protocols and an analysis thereof. Lastly, Section 6 summarises the main contributions and findings of the work and outlines future works.

2. Related works

Designed by Lindsey and Raghavendra [9], Power Efficient GAthering in Sensor Information System (PEGASIS) is a chain-based routing protocol which relies on chain formation. Although transmission of packets takes place in a multi-hop manner which curtails energy demand, the main drawback in PEGASIS is that no consideration is given to the distance between the primary node and the remaining ones during chain formation. Hence, in large WSNs, longer chains can be formed leading to an increase in delay.

Horizontal PEG-ACO Clustering is a cluster-based and chain-based protocol proposed by Ramluckun and Bassoo [10]. Despite its enhancements in network lifetime and energy efficiency, nodes in the upper level cluster expend the highest amount of energy in transmitting data to the BS [11]. Moreover, being responsible for collecting intra- and inter-cluster data, the CHs in the upper level cluster have to withstand a tremendous load by transmitting the aggregated packets to the BS located far away [12]. Henceforth, the nodes perish quicker resulting in network partitioning [13]. This problem, referred to as the hotspot problem, can be solved by employing an unequal clustering technique which is tackled in this paper.

Wang, Gao and Zhou [14] used mobile sinks to improve the coverage and network lifetime of SNs in TSCR-M (trajectory scheduling method based on coverage rate). The particle swarm optimisation (PSO) algorithm is employed to determine the data collection point of the mobile sinks to increase the coverage radius of SNs.

Enhanced PEGASIS (EPEGASIS) proposed by Wang, Gao and Yin [15] also introduces mobile sinks to decrease the distance between sensors and sinks during data transmission. Simulation results showed significant improvement of EPEGASIS against PEGASIS with regard to network lifetime and energy usage.

Designed by Tabatabaei [16], SSFBCA (social spider fuzzy based clustering algorithm) aims at maximising the residual energy of all nodes by employing the SSO algorithm and fuzzy logic for clustering to choose the node with the highest energy level and closest to sink as CH. Mobile sinks are also used to distribute the residual energy of each node better.

DCCHP (duty cycling centralized hierarchical protocol) introduced by Hady [17] uses a duty cycling technique to put nodes in the sleep state after determining the importance of data being monitored. Nodes sensing unimportant data within a time period are put in passive mode for some time and vice versa.

In the above-mentioned protocols, only the energy constraint of SNs was factored in. Convergence comparisons were not made in either [14] or [16]. Metaheuristic algorithms were employed, which further inhibited routing protocols' analysis where both the energy and memory constraints should be considered.

2.1 Red-Deer Algorithm

RDA is a novel algorithm, inspired by the behaviours of red deers (RDs), which comprise roaring, fighting and mating [18].

In order to solve the Travelling Salesman Problem in WSNs, RDs are generated to identify the solutions in the search space [18]. A population of RDs consists of a number of males (commanders and stags) and females (hinds). Each RD represents a unique route that they have randomly been allocated in the solution space. Thus, each solution is denoted by a sequence of nodes using the nodes’ position as reference. Each node when travelled upon by the RDs forms a chain along which data will be routed. The formation of the chain is crucial in determining the length of the path to be taken. Here, the optimised (fitness) solution pertains to the order of nodes which yields the minimum distance when travelled upon.

So far in the literature, convergence comparisons have been made between RDA, genetic algorithm and PSO by Fathollahi-Fard, Hajiaghaei-Keshteli and Tavakkoli-Moghaddam [19]. Similar comparisons were made by the same authors in [18], against ABC (artificial bee colony) and simulated annealing. Another recent work using RDA was carried out by Ambareesh and Madheswari [20] whereby RDA was hybridised with a Salp Swarm (SS) algorithm. The proposed algorithm was also evaluated in terms of fitness value against RDA and SS, amongst others. In all papers, RDA was highly performant in terms of convergence, which can be beneficial in addressing the limited constraints of SNs mentioned earlier. Additionally, despite all these comparisons, RDA remains to be studied against other well-founded bio-inspired algorithms and implemented in routing protocols. Hence, in this paper, RDA will be thoroughly compared against ACO and RDA-based routing protocols will be devised and simulated in a WSN scenario.

3. System model

3.1 Network model and assumptions

N nodes are randomly spread into a square-based sensing area of length M. A single BS with an infinite energy source is also deployed at a predetermined location. Additional assumptions considered for the simulation are as follows:

1. The nodes are homogeneous in nature.

2. They are equipped with the same battery capacity and are non-rechargeable.

3. All the nodes are in the active mode and are periodically sensing data in the network.

4. Static clustering is performed after network formation and nodes deployment.

3.2 Radio energy model

A radio energy model is taken from Sabor, Abo-Zahhad, Sasaki and Ahmed [21] to estimate the amount of energy expended by SNs during the communication process. The total energy expended by the transmitter is

(1)ETX(L, d)= {Eelec∗ L + εfs∗L∗d2,  if d < d0Eelec∗ L + εmp∗L∗d4,  if d ≥ d0

where d₀ is a threshold value that determines whether transmission takes place using the free space or multipath model. It is given by

(2)d0= εfsεmp

where εfs and εmp are the energy dissipated per bit in the free space and multipath propagation model, respectively.

Energy spent by the receiver component is given by

(3)ERX−elec(L)=Eelec∗L

3.3 Implementation of RDA

The phases involved in finding the best solution in RDA are detailed as follows [20]:

1. (1)

   Generation of RDs

A random population of size N_pop is first generated to represent the RDs. A 1 x N array of RDs is represented as follows:

(4)RD =[R1, R2, R3..., RN]

where R is assumed to represent a solution in the search space.

The best RDs from the population are then grouped as the male RDs, N_male while the remaining population is defined as the hinds (female RDs), N_hind. The number of hinds is calculated as follows:

(5)Nhind=Npop−Nmale

1. (2)

   Initiation of roaring among male RDs

In this stage, male RDs have the chance to increase their attractiveness by roaring. The fitness values between each male RD and its neighbouring male RD are compared and if the latter has the best fitness value, its position in the solution is updated.

1. (3)

   Selection of best male RDs as male commanders

Male RDs exude different characteristics depending on their ability to roar, attract hinds and mate. Due to these differences, only γ percent of the best males are selected as male commanders, N_Com. The rest of the male RDs are denoted as stags, N_stag, given by

(6)NCom = round{γ∗Nmale}

(7)Nstag=Nmale−NCom

1. (4)

   Initiation of fights between commanders and stags

Each commander approaches all the stags at random for a one-to-one battle. After every fight, two new solutions (routes) are generated along with the two initial ones which pertain to the commander and stag. The one having the better fitness value replaces the commander in the solution. In other words, the fighting process enables the best male RD to get elected as commander.

1. (5)

   Formation of harems

The number of hinds allocated to a harem is proportional to the power of the commander which is defined by the objective function of the commander. In hindsight, the better the fitness value of the commander, the more hinds will be under its control. The power of each commander can be calculated from Eqs. (8) and (9):

(8)Vn=vn−maxiNCom{vi}

where vn is the objective function of the n^th commander and Vn is its normalised value. The following equation calculates the normalised power of the commanders:

(9)Pn = |Vn∑i = 1NComVi|

The number of hinds per harem possessed by each commander is then calculated as follows:

(10)N.haremn = round{Pn∗Nhind}

where N.haremn represents the number of hinds, Nhind in the n^th harem.

1. (6)

   Initiation of mating between male RDs and female RDs

The mating process is important in diversifying an RD population. The commanders and/or stags then mate with the hinds.

• Mating of commander with α percent of hinds in his harem

Each commander randomly mates with α percent of hinds in its harem which is given by

(11)N.haremnmate = round{α∗N.haremn}

where N.haremnmate is the number of hinds selected to mate in each harem, n.

• Mating of commander with β percent of hinds in another harem

In the second mating phase, each commander of a harem mates with β percent of hinds from any randomly chosen harem k, other than its own harem. The number of hinds in the kth harem is calculated by

(12)N.haremkmate=round{β∗N.haremn}

where N.haremkmate represents the number of hinds in the k^th harem.

The importance of this mating phase is for the commander to grow the size of its territory.

• Mating of stag with the nearest hind

Lastly, each stag mates with the hind found in its neighbourhood. The distance between each stag and the ith hind is calculated from Eq. (13) and the hind closest to the stag is chosen for the mating process. An additional solution (offspring) is created for each mating that occurs.

(13)di= ∑j ∈ J(stagj − hindji)2

where the distance between each stag and the ith hind is denoted as di.

1. (7)

   Selection of the next generation

The next generation of RDs is then selected in two ways. Firstly, a percentage of the best solution is selected as the male RDs which includes the commanders and stags. Secondly, the remaining population, i.e. the hinds, are chosen from the population of hinds and offspring generated previously using the roulette wheel selection technique.

For each solution, the fitness value is calculated as a mathematical summation of the distance travelled from one node to another, until the entire network is travelled upon.

4. Comparative analyses between RDA and ACO

In this section, comparative analyses are made between RDA and ACO in terms of convergence rate and execution time. The analyses are made by varying the network size and node density. The comparison parameters for RDA and ACO are provided in Table 1 and a description of the performance metrics is given in Table 2.

4.1 Varying network size

In this section, three different network sizes: 50 × 50m, 100 × 100m and 200 × 200m, each equipped with 100 nodes are simulated for the comparative analysis.

In Figure 1, as the number of rounds increases, the fitness value for both ACO and RDA decreases. After several iterations, a steady curve is observed which implies that the algorithm is about to converge to its optimum solution. It can also be deduced that the best fitness value is different for each network size and the time taken to converge is more significant for larger network sizes.

The main reason behind the fast-converging ability of RDA is attributed to the balance it strikes between the intensification and diversification phases. The roaring and fighting phases enhance the intensification phase, while the different mating phases improve upon the diversification phase. The selection of the next generation of RDs helps in escaping the local optimum much faster. RDA also adopts a hierarchy when dividing its population into commanders, stags and hinds. It then arranges the position of the RDs based on their fitness values to find the optimum solution faster.

Moreover, since mating occurs between the commanders and hinds, the offspring generated have a greater probability of having a better fitness value than the parents. Through this process, any suboptimal solution is rapidly replaced by an optimal one, achieving convergence faster. On the other hand, in ACO, the gradual build-up of pheromone at a particular location in the search space signals all the ants towards that location, thereby creating a local optimum which causes the ants into thinking that the optimal solution has been reached which might not be the case.

In terms of the execution time, from Figure 2(a), RDA reduces the amount of time taken to produce the best solution compared to ACO. From the figure, the percentage improvement of RDA against ACO is on average 85% for the different network sizes.

4.2 Varying node density

The analysis between RDA and ACO is made by varying the number of nodes from 50 to 200 in a 100m × 100m field.

The time taken to yield optimal solutions for ACO increased proportionally as the number of nodes increased while RDA maintained the lowest execution time across all node densities, as shown in Figure 2(b). The convergence rate pattern for both algorithms increased proportionally as the node density increased, similar to Figure 1. The percentage improvement of RDA against ACO for node densities of 50, 100 and 200 are 65%, 85% and 90%, respectively.

It can be concluded that RDA offers a greater degree of accuracy in terms of the optimal solution, and stability in terms of the number of iterations it takes to converge. Shorter execution times imply greater computational efficiency, that is, more time can be dedicated to the communication process. Since RDA uses fewer computational resources, it generates fewer overhead than ACO.

5. Novel PEG-RDA protocols

5.1 PEG-RDA equal clustering

The proposed Horizontal PEG-RDA Clustering is a chain-cluster-based protocol with a (P x P) m² network size shown in Figure 3(a). It is first split into equally spaced rectangular clusters, whereby each cluster has an equivalent size of (P x P/q) m², where q signifies the number of clusters. The use of static clustering reduces communication overhead. For packet routing in each horizontal cluster, RDA is used to compute the shortest route. The fast-converging algorithm can make optimal use of the nodes’ limited processing power.

CH selection is then initiated with the highest-level cluster. This technique considers distance and residual energy of the SNs to elect the most suitable node as CH which aids in energy balancing. Once the chain of CHs is obtained, intra-packet transmission across all the clusters is held simultaneously and the packets are collected by their respective CHs. Afterwards, inter-packet transmission from the lower level to the upper level cluster takes place in a multi-hop manner and the aggregated packets are directly sent by the uppermost CH to the BS. The multi-hop strategy helps in reducing the otherwise long-chain construction found in PEGASIS.

5.2 PEG-RDA unequal clustering

An unequal clustering approach is implemented to solve the hotspot problem present in the proposed PEG-RDA Clustering to efficiently distribute energy among the CHs in the network. A similar approach from [5] is adopted. The clusters are of unequal widths as shown in Figure 3(b).

Fewer nodes are allocated to the clusters closer to the BS, indicating fewer intra-cluster traffic generation. As a result of this, more energy is saved for inter-cluster packet transmission. Similarly, nodes in clusters farther away from the BS can spend most of their energy in intra-packet transmission rather than inter-packet transmission since they have a comparatively higher node density [23].

5.3 Flowchart

The steps involved in designing both proposed protocols are outlined in Figure 4. After network formation, the latter is horizontally clustered into rectangles. Nodes are deployed, RDA is used to perform chain formation and CHs are then chosen from each cluster. After the completion of intra-packet transmission per cluster, packets are routed from cluster to cluster, and finally to the BS.

5.4 Analysis of proposed RDA protocols

In this section, comparative analyses are made between the two proposed RDA protocols, in terms of residual energy, alive nodes and packet loss. Horizontal PEG-ACO Clustering proposed by Ramluckun and Bassoo [10] is used as a baseline for the analysis. The proposed protocols are simulated on MATLAB. The network parameters have been referenced from [10] and the RDA parameters similar to those in Table 1 have been used.

5.4.1 Residual energy

Residual energy, an indication of the total amount of energy left in a network, is plotted against the number of rounds to observe the energy consumption pattern among the nodes.

From Figure 5, Horizontal PEG-RDA Equal Clustering performs just as good as Horizontal PEG-ACO Clustering since both ACO and RDA display the same accuracy in yielding optimal solutions.

When unequal clusters are employed, Horizontal PEG-RDA Unequal Clustering exhibits a remarkable improvement in terms of residual energy as from the 811th round. By having a lower node density at the uppermost cluster, nodes in that cluster can dedicate their energy mostly spent on intra-cluster packet transmission, towards inter-cluster packet transmission. Since lower level clusters are the least affected by the burden of inter-cluster traffic, the allocation of a higher node density enables them to sustain the network’s operation for a slightly longer period. Thus, the efficient distribution of energy through the variation in cluster size increases the residual energy as from the 811th round after the death of all the nodes in the upper level cluster.

5.4.2 Alive nodes

Alive nodes are nodes that still have some energy left to sustain a network’s operations. To further support the previous analysis, round numbers at which different percentages of the total nodes deployed die are tabulated for each protocol in Table 3.

From Table 3, PEG-RDA Unequal Clustering outperforms the other protocols above 20%. Improvements visible after first node death are indicative of the ability of PEG-RDA Unequal Clustering to balance the energy consumption in the remaining clusters in the network once all the nodes in the upper level cluster have died, hence the overall prolonged lifetime. Enhancements of 14% and 9% can be noted in PEG-RDA Unequal Clustering, at 20 and 50%, respectively, compared to PEG-RDA Equal Clustering.

5.4.3 Packet loss

Reliability is defined as the successful collection of packets by the CHs in each cluster and sent to the BS. It is plotted as the total number of packets dropped in each round [22].

From Figure 6, Horizontal PEG-ACO Equal Clustering suffers the most from packet loss. The graph of Horizontal PEG-ACO Equal Clustering showcases packet loss at five different stages denoted by the vertical lines, each pertaining to the rounds at which messages generated by the nodes in a cluster are dropped. The first vertical line corresponds to packets that have been dropped during intra-packet transmission in the highest-level cluster. When the lower level clusters forward aggregated data, the nodes in the topmost cluster cannot sustain data forwarded by their own member nodes in subsequent rounds. Therefore, when a node’s energy is depleted during intra-packet transmission, all the previously aggregated packets by the node are lost and not received by the BS. A period of stability as denoted by the horizontal line is also observed whereby no packets are lost and transmission proceeds normally until nodes in the next cluster begin to die.

The slight decrease in packet loss in Horizontal PEG-ACO Equal Clustering can be attributed to the higher degree of accuracy that RDA guarantees when determining the shortest path.

From the Horizontal PEG-RDA Unequal Clustering graph, 814 fewer packets in total are lost after the death of the upper level cluster, compared to Horizontal PEG-RDA Equal Clustering. The stability period following this loss is also more prolonged than that in Horizontal PEG-ACO Equal Clustering. PEG-RDA Unequal Clustering also achieves a 33% reduction in packet loss compared to PEG-RDA Equal Clustering, which indicates that it is more fault-tolerant and reliable than its equal clustering equivalent.

6. Conclusion and future works

In this paper, RDA has been implemented in a routing protocol to highlight its fast-converging ability in a typical WSN scenario compared to the well-established ACO algorithm. New routing protocols were proposed with RDA, one of which was closely aimed at solving the hotspot problem in PEG-RDA Equal Clustering. Comparisons were made to evaluate the rate of convergence and execution time of RDA in contrast to ACO. Performance evaluation revealed that RDA is a more accurate and faster-converging algorithm compared to ACO. The results also proved that the unequal clustering method improved upon PEG-RDA Equal Clustering, in terms of residual energy, alive nodes and packet loss. Therefore, by combining the benefits of RDA and energy-efficient techniques, RDA-based routing protocols can be devised to tackle the limited energy and computing resources available in SNs altogether. Future works could further improve upon the convergence rate of RDA by hybridising the algorithm with other metaheuristic algorithms such as Genetic Algorithm.

Figures

Figure 1

Impact of network size on convergence rate between ACO and RDA

Figure 2

(a) Impact of network size on execution time between ACO and RDA, (b) Impact of node density on execution time between ACO and RDA

Figure 3

(a) Horizontal PEG-RDA equal clustering, (b) horizontal PEG-RDA unequal clustering

Figure 4

Steps involved in horizontal PEG-RDA clustering

Figure 5

Residual energy vs. round number

Figure 6

Packet loss vs. round number

Table 1

Comparison parameters for ACO and RDA

Algorithms	Parameters
ACO	Iterations = 10000, number of ants = 40, pheromone exponent = 1, heuristic exponent = 1, evaporation rate = 0.05
RDA	Iterations = 10000, population size = 100, number of males = 15, number of hinds = 85, α = 0.9, β = 0.9, γ  = 0.4

Table 2

Performance metrics description

Metrics	Explanation
Convergence rate	The rate of convergence is the time taken for a population to converge to an optimum solution. Best fitness values obtained at each iteration are plotted and the algorithm that takes the fewest number of rounds to yield the best solution is regarded as the fastest converging one
Execution time	Execution time is defined as the time taken for SNs in a WSN to complete a particular task. In this paper, it refers to the time taken for the algorithms to ultimately reach the optimal solution [22]

Table 3

Comparison of rounds at which different % of nodes die in a network of 100 nodes

Proposed protocols	1%	20%	50%	80%	100%
Horizontal PEG-ACO clustering	1093	1115	1676	1871	1955
Horizontal PEG-RDA equal clustering	1096	1115	1681	1872	1957
Horizontal PEG-RDA unequal clustering	800	1274	1827	1959	1979