9 - Ari

Journal of Network and Computer Applications 69 (2016) 77–97
Contents lists available at ScienceDirect
Journal of Network and Computer Applications

journal homepage: www.elsevier.com/locate/jnca
A power efficient cluster-based routing algorithm for wireless sensor

networks: Honeybees swarm intelligence based approach
Ado Adamou Abba Ari a,c,n, Blaise Omer Yenke b, Nabila Labraoui d, Irepran Damakoa b,
Abdelhak Gueroui a
a
LI-PaRAD, Université Paris Saclay, University of Versailles Saint-Quentin-en-Yvelines, France
b
LASE, University of Ngaoundere, Cameroon
c
FS, University of Maroua, Cameroon
d
STIC, University of Tlemcen, Algeria
art ic l e i nf o a b s t r a c t
Article history: The design of low-power scalable wireless sensor networks remains a key challenge of the research.
Received 30 November 2015 Clustering and routing have been widely studied for extending the lifetime of a network, which is a
Received in revised form critical issue in sensor networks. Routing involves non-negligible operations, which considerably affect
29 March 2016
the network lifetime and the throughput. The clustering technique with data aggregation on cluster
Accepted 26 April 2016
Available online 27 April 2016
heads has an influence on the overall performance of the network since it is favoring a maximum net-
work lifetime. This paper presents a novel cluster-based routing protocol called ABC-SD. The proposed
Keywords: protocol exploits the biologically inspired fast and efficient searching features of the Artificial Bee Colony
Clustering metaheuristic to build low-power clusters. For the choice of cluster heads, a multi-objective fitness
Routing
function is designed by using a Linear Programming formulation. The routing problem is addressed by a
Wireless Sensor Networks
cost-based function that makes a trade-off between the energy efficiency and the number of hops of the
Swarm Intelligence
ABC path. The clustering process is achieved at the Base Station with a centralized control algorithm, which
ABC-SD exploits energy levels and the neighborhood information of location-unaware sensors. As for the routing
Honeybees of gathered data, it is realized in a distributed manner. Furthermore, unlike the existing protocols in the
Bio-inspired literature, a realistic energy model is adopted in the considered network model. The proposed protocol is
intensively experimented with a number of topologies in various network scenarios and the results are
compared with the well-known cluster-based routing protocols that include the swarm intelligence
based protocols. The obtained results demonstrate the effectiveness of the proposed protocol in terms of
network lifetime, network coverage and the amount of packets delivered to the Base Station.
& 2016 Elsevier Ltd. All rights reserved.
1. Introduction phenomena, on a remote or inaccessible environment (Zungeru

et al., 2012; Ari et al., 2015). These applications are both in tracking
1.1. Background such as military strategies or seismic measurements, and in
monitoring applications such as prevention of natural disasters or
Sensor-based infrastructure such as Wireless Sensor Network agricultural irrigation management.
(WSN) provides promising Green Computing techniques for en- Each sensor in the network is equipped with a sensing unit, a
hancing information gathered on a specific environment to the radio transmission module, a power supply, a processing and data
end users. A WSN is an infrastructureless network consisting of ten storage devices. However, these components are designed with
to some thousands autonomous low power sensors organized in huge resource constraints. The limited energy source is the main
constraint of WSNs (Kuila and Jana, 2014; Titouna et al., 2016).
an ad hoc manner. These sensors are able to gather and process
Therefore, the energy saving of sensors is a challenging issue that
information from an environment, and communicate with each
needs investigation in order to prolong the network lifetime from
other. WSNs are usually used in both civilian and military appli-
months to years. Certainly, a number of issues has been studied for
cations to instrument, observe and react to an occurred event or improving WSNs. These research include energy consumption and
low power devices (Barberis et al., 2007; Srinivasan et al., 2010; Li
n
Corresponding author at: LI-PaRAD, Université Paris Saclay, University of Ver-
et al., 2014), Medium Access Control (MAC) protocols for WSNs
sailles Saint-Quentin-en-Yvelines, France. (Polastre et al., 2004; Kabara and Calle, 2012), clock synchroniza-
E-mail address: adoadamou.abbaari@gmail.com (A.A.A. Ari). tion techniques (Heidarian et al., 2012), secure data aggregation
http://dx.doi.org/10.1016/j.jnca.2016.04.020
1084-8045/& 2016 Elsevier Ltd. All rights reserved.
78 A.A.A. Ari et al. / Journal of Network and Computer Applications 69 (2016) 77–97
(Labraoui et al., 2013), and efficient routing techniques (Moussaoui the routing information towards the BS. However, given a network
et al., 2006; Saleem et al., 2011; Liu, 2012). Many designs of sensor topology, there is no deterministic polynomial algorithm that can
networks allow sensors to transmit their gathered data to a mobile partition the network into clusters (Avril et al., 2014). Moreover,
or static Base Station (BS) in multi-hop routing (Zungeru et al., since a sensor network can be seen as an undirected graph or a
2012; Elhabyan and Yagoub, 2014). However a robust and low- tree, there is at least one path (usually a number of paths) to reach
power mechanism of collecting and routing data towards the BS in a given destination, such as the CH location. So, the path estab-
an efficient way remains a challenge. Clustering is the most widely lishment process of the routing algorithm has to produce a set of
used technique for efficiently managing network energy con- selected low-cost paths among a number of possibilities. This has
sumption and scalability in order to increase network lifespan. to be done both for the intra-cluster and the inter-cluster com-
In WSNs, clustering techniques consist of partitioning the munications. Unfortunately, it is not evident to use a deterministic
network into a varied number of sensor groups called clusters. In polynomial algorithm for routes establishment (Yang et al., 2010).
each cluster, a leader called Cluster Head (CH) is elected either in a Swarm intelligence, which is the study of the collective beha-
distributed manner by sensors themselves (Zungeru et al., 2012; vior of social individuals' communities, provides efficient meta-
Cai et al., 2015) or by a centralized control algorithm (Latiff et al., heuristic tools and algorithms that deal with a lot of desirable and
2007; Karaboga et al., 2012). However, in the work proposed in interesting properties applied in WSNs as surveyed in Saleem et al.
Heinzelman et al. (2000), a sensor can take itself the CH position (2011), Zungeru et al. (2012). In other words, swarm intelligence
according to a random process and certain probability value. In can be seen as analogies between computing methods and bio-
each cluster, sensors gather data and send it to their corresponding logical behaviors of swarms in which collective intelligence can
CHs. The first kind of communication is known as the intra-cluster emerge. The considered swarms are colonies of social insects, bird
communication. The CH aggregates all received data and transmits flocking and fish schooling. Each kind of swarm is constituted of
it to the BS. The second type of communication is called inter- simple and autonomous individuals, which cooperate with each
cluster communication. Otherwise, in the design proposed in other to achieve some tasks necessary for the survival of the col-
Zungeru et al. (2012), the gathered data are transferred to the BS ony. In the context of WSNs, these simple and robust behaviors
by a flat routing approach. Unlike this way of designing, the have been successfully applied by identifying and modelling some
cluster-based routing algorithms allow only CHs to transfer col- analogies between the two systems. Clustering and routing in
lected data to the BS. This approach helps to reduce the rate of WSNs are well known optimization problems which are well in-
communication towards the BS and also permits to avoid collisions vestigated for developing many swarm intelligence based algo-
among communications generated by clusters. rithms (Kuila and Jana, 2014). For instance, the Ant Colony Opti-
Furthermore, as it is necessary that the intra-cluster commu- mization (ACO) metaheuristic (Dorigo et al., 2006) has been ap-
nications be carried out in a multi-hop manner within the cluster, plied for multipath cluster-based routing in Yang et al. (2010), the
it is also important and efficient that CHs' communications, i.e., the Particle Swarm Optimization (PSO) algorithm (Kennedy, 2010) has
inter-cluster communication, be performed in a multi-hop manner been used in Elhabyan and Yagoub (2014), Singh and Lobiyal
(Saleem et al., 2011). Note that, the intra-cluster communication is (2012) to optimize clustering, and the Artificial Bee Colony (ABC)
not always carried out by the multi-hop approach. In detail, the metaheuristic (Karaboga, 2010) has been successfully used for
protocol proposed in Heinzelman et al. (2000) exclusively allows clustering and routing in Karaboga et al. (2012). For more than a
sensors to directly transmit their gathered data to their respective decade, the ABC metaheuristic progressively draws the attention
CHs even if the communication range between them is very large. of researchers because of its efficiency in the solving of a number
Similar to the way in that protocol, CHs also directly communicate of optimization problems in wide domains. In this paper, we use
the aggregated information to the BS in a single hop approach. the ABC metaheuristic to build clusters and a cost function based
However, in real cases, the BS as well as CHs may be located far mechanism for the routing phase.
away from certain nodes in the sensing environment or even, the
BS may be positioned far away from the sensing environment (Ari 1.2. Authors' contributions
et al., 2015; Saleem et al., 2011). In these cases, the BS may not be
reachable by CHs in a single-hop communication. In addition, ac- In this paper, we address the problems of clustering and rout-
cording to the widely used energy model proposed in Heinzelman ing in WSNs. We formulated the clustering as a Linear Program-
et al. (2002), large distances affect the signal propagation and al- ming (LP) problem and the routing problem is solved by proposing
low a lot of power wastage. So, in order to avoid direct commu- a Cost-based Function (CF). The clustering algorithm allows the
nication between a CH and the BS, authors in Zungeru et al. (2012) efficient building of clusters by making a tradeoff between the
as well as those in Cai et al. (2015) allow intermediate sensors to energy consumption and the quality of the communication link
participate in the forwarding of data towards the BS. Un- within clusters. An initial population of bees is generated in order
fortunately, in homogeneous networks, the power supply as well to find the best CH according to the ABC metaheuristic. We de-
as the communication range of sensors is limited. These facts signed a multi-objective fitness function that uses the weighted
weaken their proposals. Authors in Kuila and Jana (2014) proposed sum approach, in the assignment of sensors to a cluster.
the use of special sensors provisioned with extra energy called Moreover, we adopt a routing strategy in which routes are pre-
gateways, which act as relay nodes in the inter-cluster commu- established at each round of the network. The routes establish-
nication. However, it seems not realistic for large-scale randomly ment is brought back to a problem of choosing the low-cost one
deployed sensor networks. Therefore, it seems beneficial to route among possible paths to reach a destination. We proposed a cost
packets by using an efficient and low-power multi-hop commu- function that allows to choose energy efficient paths. The clus-
nication model, both for intra-cluster and inter-cluster tering is achieved in a centralized control approach at the BS while
communication. the routing is achieved in a distributed manner. We perform in-
Clustering sensors provides many advantages for an efficiency tensive simulation on the proposed protocol under a realistic en-
management of WSNs. It allows power saving in sensors since CHs ergy consumption model that is based on the characteristics of the
are capable of eliminating redundant and false positive data by a Chipcon CC2420 radio transceiver. We compare our proposed
given aggregation process (Labraoui et al., 2013). By this way, the protocol with four existing well known protocols. The comparison
communication bandwidth is preserved. It also allows a good is conducted by using several performance metrics including en-
management of the inter-cluster routing since only CHs maintain ergy consumption, energy efficiency, amount of data packets
A.A.A. Ari et al. / Journal of Network and Computer Applications 69 (2016) 77–97 79
delivered to the BS and so on. In short, our main contributions can largely affects the lifetime. Otherwise, the CH status dynamically
be summarized as follows: rotates between sensors in each round according to a given
probability. Unfortunately, since the selection of CHs is randomly
LP formulation of the clustering problem. done, the distance between a given sensor and its corresponding
Routing problem addressed by a CF. CH may be too long. This causes a weak distribution of CHs over
ABC-based clustering algorithm with a tradeoff between the the sensing area and hence a lot of power wastage.
energy consumption and the quality of the communication link. Unlike the LEACH that is a completely distributed protocol, the
Pre-established routing mechanism in which routing paths are LEACH-C (Heinzelman et al., 2002), which is an amelioration of the
less costly in terms of power consumption. LEACH, uses a centralized control algorithm for the formation of
Integration of a realistic energy model and realistic network clusters. At the start of each network round, when receiving sen-
settings. sors’ locations and their energy levels during the network in-
Simulation of the proposed protocol to demonstrate its perfor- itialization step, the BS launches the clustering process. The clus-
mance compared to some existing protocols. tering algorithm in the LEACH-C uses the simulated annealing
approach with sensors' locations and their available power in-
1.3. Organization of the paper formation to build a predetermined number of CHs and so, a fixed
number of clusters, each with a certain number of members. This
The rest of the paper is organized as follows: Section 2 presents approach produces a better positioning of CHs on the sensing area,
a brief review of some cluster-based routing protocols for WSNs it slightly reduces the power consumption and data loss compared
and the most challenging issues; In Section 3, we first give an to LEACH. But the adopted single-hop routing mechanism remains
overview of the foraging behaviors of honeybees swarm in- a limitation. However, the LEACH-C protocol improves the LEACH
telligence and then, we present an algorithm simulating these in terms of data delivery at the BS and power consumption.
behaviors; the network model is presented in Section 4; in Section In the number of existing clustering algorithms for WSNs, there
5, the design goals as well as the proposed clustering and routing is an increasing interest in bio-inspired clustering approaches. The
algorithms are described; this is followed by the performance ABC algorithm (Karaboga, 2010), which is inspired by foraging
evaluation and discussion in Section 6; and the conclusion and behaviors of honeybee swarms has been successfully used to de-
directions for future work are presented in Section 7. sign clustering algorithms (Ari et al., 2016; Karaboga et al., 2012).
The clustering and routing strategy is performed at the initializa-
tion phase, as a centralized control mechanism at the BS and in-
2. Cluster-based routing in WSNs formation messages about the configuration and cluster organi-
zation are broadcast over the network. Similar to the LEACH ap-
Clustering sensors is usually adopted in large scale networks. proach in Heinzelman et al. (2000), the ABC-based clustering and
Like reported by Liu (2012), it is proved that the cluster-based routing protocol presented in Karaboga et al. (2012) performs the
networks, also known under the names of hierarchical or multi- election of the CH periodically. This choice introduces overhead
tier networks, are more scalable, provide more reliability, better communication in the network. However, because in their pro-
coverage, good fault tolerance and energy efficient. Moreover, posed semi-distributed approach, the CH election step is achieved
Moussaoui et al. (2006) argue that the clustering can be seen as a in a centralized manner by the BS, the energy cost of the CH
graph partitioning problem with some added constraints since the election process is minimized on sensors. Another semi-dis-
size and the geometric form of the obtained graphs (clusters) is tributed clustering strategy based on a non linear and linear pro-
not known in advance. Thus, because of these constraints, the gramming formulation of the clustering and routing problem is
clustering is known to be a NP-Hard optimization problem (Latiff proposed by Kuila and Jana (2014). The clustering problem is
et al., 2007). Nevertheless, the hierarchical routing issue for WSNs solved by using a PSO algorithm with an efficient particle encoding
has been investigated a lot and many protocols have been devel- scheme. The proposed fitness function enables a good balancing of
oped. These protocols include heuristic and meta-heuristic based consumed energy by CHs. Like the approach presented in Kar-
approaches. In this section, we give a brief and comprehensive aboga et al. (2012), the cluster formation is done in a centralized
review of the most relevant cluster-based routing protocols. We manner.
use some of them principally for the comparison purpose in Sec- Latiff et al. (2007) used the PSO algorithm (Kennedy, 2010),
tion 6.3. We draw the readers' attention on bio-inspired (meta- which is based on social behaviors of birds flocking or fish
heuristic) based approaches for cluster-based routing in WSNs. schooling to design the PSO-C protocol. The proposed protocol
Interested readers may refer to Ari et al. (2015), Liu (2012) for implements a centralized clustering algorithm at the BS. It is
extended reviews of cluster-based routing for sensor networks. In supposed that each sensor knows its location. In order to assign
particular, references (Zungeru et al., 2012; Nanda and Panda, sensors to a cluster, the BS, i.e., the clustering algorithm, considers
2014) provide a comprehensive global view of nature-inspired the energy level and the euclidean distance between a sensor and
approaches. selected CHs. A defined cost function that aims at minimizing the
Heinzelman et al. (2000) proposed a low energy adaptive intra-cluster distance while optimizing the power consumption of
clustering hierarchy called LEACH, which is the most popular and sensors is adopted. This allows the selection of the best set of CHs
widely referenced cluster-based routing protocol for WSNs. The that can maximize the cost function. In addition, the PSO-C algo-
adopted clustering mechanism allows the random creation of CHs rithm ensures that only sensors with sufficient remaining energy
in each round of the network. The selected CHs have the respon- are selected to a CH position. Authors compared the PSO-C pro-
sibility of the aggregation of data gathered by sensors. However, tocol with the above described LEACH and LEACH-C protocols. The
the LEACH algorithm allows the selection of a sensor to a CH po- results show that PSO-C outperforms the compared protocols in
sition even if its remaining energy is too low. This is a great limit terms of network lifetime and throughput. In their performance
because a sensor may die right away after it is selected as a CH. It comparison, authors found that the PSO-C protocol outperforms
will cause data loss since the next CH selection will occur in the the Genetic Algorithm (GA) and K-means based clustering proto-
next round. Furthermore, the data routing is performed in a sin- cols in terms of the convergence of the defined cost function, the
gle-tier, i.e., in a single-hop manner. This is not realistic for large data delivery and the network lifetime. In spite of the promising
scale WSNs. It causes the quick death of sensors and therefore, it performance outputted by this swarm intelligence based
Table 1
Summary of the relevant cluster-based routing protocols in the literature compared to the proposed approach.
Protocol Energy model Link quality based Location Clustering

on
Algorithm Approach Goal
LEACH (Heinzelman et al., 2000) First order Distance Unaware Distributed Random Load balancing
LEACH-C (Heinzelman et al., 2002) First order Distance Aware Centralized SA Energy efficiency
PSO-C (Latiff et al., 2007) First order Distance Aware Centralized PSO Energy efficiency
Bee-C (Fathian et al., 2007) First order Distance Aware Centralized Bee Energy efficiency
ABC-C (Karaboga et al., 2012) First order Distance Unaware Centralized ABC Energy efficiency – Throughput
Bee-Sensor-C (Cai et al., 2015) First order Signal strength Unaware Distributed Bee Energy efficiency – Scalability
PSO-HC (Elhabyan and Yagoub, 2014) cc2420 Signal strength Unaware Centralized PSO Energy efficiency – Link quality – Scalability
ABC-SD cc2420 Signal strength Unaware Centralized ABC Energy efficiency – Link quality – Scalability –
Throughput
algorithm, the PSO-C protocol assumes that sensors know their Elhabyan and Yagoub (2014) proposed a centralized PSO based
location. This fact seems not realistic for randomly deployed sen- protocol for hierarchical clustering (PSO-HC) in WSNs, which uses
sors and thus, non-scalable. a realistic energy model. The clustering algorithm of the PSO-HC
Fathian et al. (2007) introduced the Bee-C that is a multi-tier protocol is implemented at the BS. Authors adopted a clustering
cluster-based routing protocol for sensor networks. These authors mechanism that takes into consideration the sensor's received
proposed a metaheuristic algorithm inspired by the Honey Bee signal strength and their energy level. The received signal strength
Mating Optimization (HBMO), which is based on the reproduction helps in the evaluation of the communication link quality between
behaviors of honeybees. Like LEACH and LEACH-C protocols, the two sensors. To improve the scalability, a two-tier cluster is
main idea in the Bee-C design is the energy saving. To achieve this adopted in such a way that the coverage is maximized. Like PSO-C,
goal, authors designed a network with a continuous data dis- LEACH-C and LEACH protocols, the network operating time is
semination (principally for the energy saving purpose). Un- splitted into rounds in which CHs are selected. The PSO meta-
fortunately, while increasing the number of sensors, the Bee-C heuristic is exploited in the selection of a minimal number of ac-
protocol delivers poor results, it simply means that the protocol is tive CHs. In fact, since the whole coverage of the network is not
not scalable. well guaranteed in the case of a fixed number of CHs, authors
In the same order of ideas, Cai et al. (2015) proposed an ame- consider a predetermined percentage of CHs according to the
lioration of Bee-C called Bee-Sensor-C. Principally designed for network density. The performance analysis shows that PSO-HC
event driven sensor networks, the Bee-Sensor-C protocol uses a outperforms PSO-C, LEACH-C and LEACH protocols in terms of the
dynamic clustering scheme in order to reduce the routing over- average consumed energy and the throughput.
head and improves the scalability. Authors adopted an on-demand In Table 1, the main characteristics of the above reviewed
multipath cluster-based routing mechanism inspired by some protocols are summarized and the main differences with the
foraging behaviors of a bee swarm. Indeed, the Bee-Sensor-C proposed protocol are highlighted. To complete that Ari et al.
builds a cluster structure and selects the CH when an event occurs. (2015) gave another classification of some routing protocols for
Concretely, when an event occurs in a place of the sensing en- WSNs found in the literature.
vironment, all sensors close to that event may need to gather and
transfer the data. So, the first sensor that declares the event be-
comes the CH and other sensors have to follow him and by this 3. Overview of honeybees swarm intelligence
way, a cluster is constructed. However, the adopted on-demand
cluster construction will introduce a great overhead in a case of Honeybees are fascinating and highly organized insects capable
high event-driven and large-scale networks. Nevertheless, com- of individual cognitive abilities and self-organization. These in-
pared to Bee-C, Bee-Sensor-C improves the whole network sects grouped in a colony and living within a hive, show im-
performance. pressive auto-solving problem capabilities by exhibiting a combi-
The aforementioned protocols and many others in the litera- nation of individual traits and social cooperation that is un-
ture adopted the first order energy model initially proposed by paralleled in the animal kingdom (Winston, 1991). These in-
Heinzelman et al. (2002) for the LEACH-C protocol. Of course, it is dividual capabilities lead to unanimous intelligent decisions in a
the first stable theoretical modelling of energy consumption for collective self-organized manner and a decentralized control me-
radio sensors, but this model is unrealistic. Indeed, in this energy chanism. In a honeybee colony, individuals are organized to per-
model, authors have not taken into account the energy of listening form various tasks that are necessary to the survival of the colony.
that is known to be non-negligible in power discharging of a Indeed, they are engaged in several activities: foraging, mating,
wireless sensor battery (Barberis et al., 2007). Moreover, similar to waggle dance, polarization, defending the hive and swarming. In
the previous PSO-C protocol, most of the existing clustering and this work we use the honeybees swarm intelligence, which is fo-
routing protocols suppose that sensors know their locations. This cused on the collective behaviors that result from local and simple
implicitly implies that sensors are equipped with localization interactions of individuals of a honeybee Apis mellifera colony with
hardware. It is not realistic for large scale networks and also it their environment. Particularly, we are interested in their foraging
leads to the use of costly sensors. Furthermore, this energy model behaviors.
is essentially based on the distance between the sender and the
receiver for evaluating the link quality. Yet, a number of research 3.1. Foraging behaviors in honeybees
demonstrated that the distance is not a valid criteria for the eva-
luation of the quality of a link in a WSN. The most convincing work The foraging behaviors of honeybees Apis mellifera consists of a
that justifies this assertion is the empirical study of low-power remarkable set of simple and organized tasks in which individuals
wireless achieved by Srinivasan et al. (2010). The use of a realistic each with a role, are engaged. Indeed, in a honeybee colony, each
energy model is therefore necessary in designing realistic WSNs. individual has a defined role and some qualifications. There are
three types of individuals: the queen, the workers and the drones. ABC algorithm is based on a minimal modelling of the intelligent
The queen bee is a mated female bee and there is only one queen foraging behaviors of honeybees (Karaboga, 2010). The proposed
per hive, i.e., per colony. The queen has the main role since of model consists of three essential components that are previously
reproduction and cohesion, necessary to perpetuate the colony. described in Section 3.1, and of two leading modes. The compo-
Drones are male bees that have the main role of mating with the nents are three groups: employed foragers, unemployed foragers
queen for the reproduction of the colony. Workers that are female and food sources. The first are associated with particular food
bees as to them, are responsible for the foraging. They perform the sources and the second are in two types: onlookers and scouts.
most important task of the hive by making trips in order to supply Every time, onlookers and scouts are in the search of a rich food
water, pollen, nectar and other substances from blooming plants, source to exploit. In fact, the first half of the colony consists of
within 3–4 km around the hive (Tchuenguem Fohouo et al., 2014). employed bees and the second half consists of onlooker bees.
Workers make the link between the colony and the ambient Onlookers bees are foragers who watch the waggle dance of em-
environment. ployed foragers within the hive, for a decision of choosing a food
The swarm intelligence of honeybees Apis mellifera foraging source. That decision is taken according to the quality of the food
behavior has been studied by Karaboga (2010). The author pre- source. The scout bees as for them, have a job of searching new
sents three essential components on which he has built a minimal food sources.
model of foraging behaviors that leads to the emergence of a The self-organization and the collective intelligence in ABC are
collective intelligence. These components are given hereinafter: achieved by the leading modes. Thereof consists of the recruit-
ment of foragers to rich food sources and abandoning poor food
1. The food sources: The profitability of a food source depends on sources. According to the previously described four characteristics
many factors including its closeness to the hive, its richness or on which self-organization of honeybees relies (see Section 3.1),
the concentration of the energy within, and the facility of ex- the first is assimilated to a positive feedback and the second causes
tracting this energy. In order to simplify its model, Karaboga a negative feedback. Concretely, the proximity and richness of a
takes goodness to qualify these qualities. food source represents a good solution of a given optimization
2. The employed foragers: These worker bees are associated with a problem and the goodness of a food source is the fitness of the
particular food source, which is currently being exploited until associated solution. For a global optimization problem, the ABC
its exhaustion. They carry information about that particular algorithm consists of looking the best food source, i.e., the best
food source, i.e., the direction toward the food source, its dis- solution. The ABC scheme given in Algorithm 1 consists of four
tance from the hive and the profitability of the food source. So, phases: employed bees phase, onlooker bees phase, scout bees
these foragers share these information with other foragers who phase and the memorization of the best solution achieved so far
remained in the hive. (Karaboga, 2010).
3. The unemployed foragers: They are continually looking out for a
food source to exploit. Unemployed foragers are in two types: Algorithm 1. Algorithm simulating the ABC.
scouts that are engaged in the search of new food sources
Begin
around the hive, and onlookers, which wait in the hive and
1. nInitialization Phasen
establishing a food source through the information shared by
2. Generate initial population Xi , i = 1, … , SN
employed foragers.
3. Repeat
4. nEmployed Bees Phasen
In these components, we can see that the exchange of in-
5. For each employed bee
formation among bees on explored food sources is important for
6. Produce new solutions vi according to Eq. (1)
maintaining a collective knowledge. These information are ex-
7. Calculate the fitness according to Eq. (2)
changed by performing a special dance of bees called waggle
8. Apply the greedy selection process
dance. Indeed, an onlooker bee will decide by itself to employ the
9. nOnlooker Bees Phasen
most profitable food source according to a certain probability,
10. For each onlooker bee
simply by watching the dances and then choosing the best dancer
11. Choose a solution xi depending on pi
source (Karaboga, 2010). The self-organization that emerge from
12. Produce new solutions vi according to Eq. (1)
the foraging activity of honeybees relies on four characteristics:
13. Calculate the fitness according to Eq. (2)
14. Apply the greedy selection process
1. Positive feedback: it occurs for instance when the amount of
15. nScout Bees Phasen
nectar in a source increases or the number of onlookers visiting
16. When solutions cannot be improved (reach a limit para-
of a food source increases proportionally.
meter), then replace it with a new solution produced by a
2. Negative feedback: the exploitation process of exhausted food
formula given by Eq. (3)
sources is stopped by bees.
17. nMemorize the best solution so farn
3. Fluctuations: the scouts perform a random search process for
18. Until Maximum Cycle Number
discovering new food sources.
End
4. Multiple interactions: Employed bees share their knowledge
about food sources with onlookers waiting in the hive.
The aforementioned bio-inspired characteristics of honeybees Firstly, scout bees have the job of searching the positions of all
are used in solving optimization problems. The well known algo- food sources. In the ABC algorithm, initial positions of food sources
rithm in honeybees meta-heuristic is the Artificial Bee Colony al- are randomly generated. Each employed bee is associated to one
gorithm introduced by Karaboga (2010). randomly generated food source. For simplicity reasons, the
number of employed bees is equal to the number of food sources
3.2. Algorithm simulating artificial bee colony (SN). During employed bees phase, each employed bee determines
a new food source with a good amount of nectar, within the
The Artificial Bee Colony algorithm is a swarm based meta- neighborhood food source according to Eq. (1). Then, each em-
heuristic algorithm developed for numerical optimization. The ployed bee calculates the fitness, i.e., the goodness of the food
Table 2 radio transceiver of which the data sheet is given in Texas In-
Energy consumption of the different struments (2014). The Chipcon CC2420 is a low-cost highly in-
states.
tegrated 2.4 GHz IEEE 802.15.4 compliant and ZigBee™ radio
State Consumption (μA) transceiver designed for low power WSNs' applications. The
CC2420 features include a hardware support for packet handling,
idle 426 data buffering, multiple transmissions, clear channel assessment,
sleep 20
link quality indication and packets synchronization.
receive (rx) 19, 7 × 103
transmit (tx) 17, 4 × 103
In consonance with the IEEE 802.11 implementation of the
Received Signal Strength Indicator (RSSI) that is a measurement of
the power present in a received radio signal, in a wireless en-
source. If the current employed bee finds that the obtained fitness vironment, the received signal strength is assumed to be a realistic
value according to the formula given in Eq. (2) is higher than the approach for quantifying power consumption in WSN environ-
previous one, it moves to the new food source and abandons the ments (Li et al., 2014). To exploit that in our energy quantification,
old one, otherwise it remains on its old food source: it is assumed that a sensor battery has linear charge and discharge
characteristics. So, the energy Ei consumed by sensor si is
vij = xij + ψij × (xij − xkj ) (1)
equivalent to the accumulation resulting from that of its compo-
Where: nents (Barberis et al., 2007). The energy consumption of compo-
nents contains energy of event execution and the energy spent in
ψij = rand ( − 1; 1); the transition between states. The energy ES spent by a sensor
xk is a neighbor solution; within states is given in Eq. (4):
j ∈ {1, 2, …, D} is a randomly chosen parameter index, D is the
dimension of the solution vector.
ES = ∑ (pj × t j )
j (4)
The ith food source position is represented by the vector Where:

Xi = (xi1, xi2, … , xiD )T and the fitness of the food source located at
position Xi is f (Xi ). At the end of this phase, employed bees share The index j refers to one of the four states of the Chipcon
their knowledge, i.e., the information on the fitness value, with the CC2420: idle, sleep, reception or transmission. The values of
onlooker bees. Each onlooker has to select a food source according power consumption in each of these states are given in Table 2.
to the probability given by Eq. (2). That probability depends on the pj is the mean of the power consumed in each state j.
goodness of the food source. This scheme allows good food sources t j is the operation time in the corresponding state.
to have a greater chance of being chosen:
Then, the energy ET spent in transition between states is given
f (Xi )
pi = SN in Eq. (5):
∑n = 1 f (Xn ) (2)
ET = ∑ (et × ct ) (5)
When selecting their food sources, each onlooker selects a new
food source within the neighborhood food source and evaluates its Where:
fitness. The onlooker will memorize the new position if the ob-
tained fitness value is higher than the previous one and will forget ct is the occurrence frequency.
the old, otherwise it keeps the current food source. et is the mean of the consumed energy in each state transition.
Then, food sources are exploited by employed bees and on-
looker bees until their exhaustion. The best food source is looked Hence, the total energy consumed by the sensor si, Ei is given
up until reaching a certain number of cycles, i.e., the limit para- by Eq. (6). The values of pj and et are given in the data sheet of the
meter. Hence, if the fitness value is not improved during the Chipcon CC2420, which can be found in Texas Instruments (2014):
number of cycles, the food source is assigned as abandoned and
⎛ ⎞
the employed bee becomes a scout bee, then it is now the scout
bees phase. A new solution is randomly generated by the scout
Ei = ∑ (ES + ET ) = ∑ ⎜⎜ ∑ (pj × t j ) + ∑ (et × ct ) ⎟⎟
⎝ j ⎠ (6)
according to the formula in Eq. (3):
xij = l j + rand (0; 1) × (uj − l j ) (3)
4.2. Vocabulary
Where:
In the following, since we employ much technical terms,
xi is the abandoned food source; hereinafter, we described the following notations and expressions
l j ≤ xij ≤ uj . are considered. Table 3 gives the considered notations.
Table 3
4. Network model and vocabulary Notations.
In this section, we present the used realistic energy model Notation Description
based on the signal strength indicator. Moreover, we describe the CH Cluster Head
used vocabulary and the adopted assumptions. BS Base Station
RSSI Received Signal Strength Indicator
4.1. Energy model TDMA Time Division Multiple Access
MAC Medium Access Control
B-MAC Berkeley Media Access Control
Like done by Elhabyan and Yagoub (2014), our energy model UML Unified Modeling Language
uses sensors that include the realistic features of Chipcon CC2420
The considered expressions are given below:

Clusters
The sensing environment is a 2-dimensional square field de-
noted by + ⊆  ×  . Distributed
S = {s1, s2, …, sN }, the set of N sensor nodes. routing algorithm
The identifier of the BS is 0 and each sensor node has a unique

identifier id ∈ [1, N ] ∩  .
A Candidate to a CH position is represented by CHc
Our proposal
The set of CHs is represented by ℶ(ch) = {c1, c2, …, cm }, where m
is the number of CHs, i.e., the size of ℶ(ch).
The field of cluster represented by the CH cj, j ∈ [1, m] ∩  , is
denoted by ( j .
The followers' list of the CH cj, j ∈ [1, m] ∩  is represented by Base Station
f (c j ) . Centralized
The cluster member is represented by Clm . clustering algorithm
The number of Clm in the cluster represented by cj, j ∈ [1, m] ∩ 
is denoted by N (( j ), j ∈ [1, m] ∩  .
The xth x ∈ [1, N (( j )] ∩  cluster member of the cluster re- Fig. 1. Design scheme.
presented by the head cj, j ∈ [1, m] ∩  is represented by Clmj (x ).
The RSSI value received by sensor si from sensor sj , cluster-based routing in which the clustering algorithm uses some
i, j ∈ [1, N ] ∩  : i ≠ j , is represented by R(i, j ). foraging behaviors of honeybees.
The remaining energy of sensor si , i ∈ [1, N ] ∩  is represented Since the main goals are the achievement of a good scalability
by Er (si ). and the extension of the network lifetime, our proposed protocol
The neighbor table of sensor si , i ∈ [1, N ] ∩  is represented by design aims at providing a good load balancing within clusters by
5 (si ). using a multi-hop communication among sensors and their cor-
responding CHs. Indeed, the proposed approach schematized in
4.3. Assumptions Fig. 1 is designed in such a way that the clustering algorithm is
performed in a centralized manner at the BS while the routing is
Let us consider a network with N stationary randomly deployed performed in a distributed manner inside clusters and among CHs.
sensors on a two-dimensional square field. We assume that the BS So, the protocol acts in a semi-distributed manner.
is stationary and located at the coordinate (0, 0). Each sensor in the In fact, when receiving sensor's information at the start of each
network has a unique identifier i ∈ [1, N ] ∩  . Let us consider that round, the BS will build clusters by paying attention to the choice
all sensors are homogeneous and the computation and power of the CH, which is well achieved by the position update of the ABC
capabilities of all of them are the same. Each sensor can commu- algorithm and by doing so, the energy expenditure is reduced as
nicate with another sensor if that sensor is within its commu- we can see in the results of simulation (see Section 6.3). When
nication range. It is assumed that communication links are bidir- clusters are built, the BS sends a message to each sensor in order to
ectional. Sensors' batteries cannot be recharged and each sensor is inform it about the cluster in which it belongs and the id of its
equipped with a power control device that has capabilities to vary corresponding CH. Then, the distributed part of the proposed al-
their transmit/receive power. We assume that sensors are loca- gorithm, i.e., the routing mechanism, starts within each cluster by
tions unaware. However, the location of the BS is known by each paths discovery followed by data gathering and transferring op-
sensor. We assume that all sensors maintain a synchronization erations. These operations of transferring data to CHs follow a
protocol, which allows a consistent time synchronization among convergecast tree, i.e., many-to-one within the cluster. Transferring
the sensors in the network. aggregated data to the BS follows also the same process in which
many represent CH sensors and one represents the BS. Since a lot
of traffic is generated, particularly during the network initializa-
5. Algorithms design tion and the route discovery, our design implements a mechanism
that filters out redundant data. The whole steps performed in the
In this section, we first present the design goals of the proposed execution of the ABC-SD protocol is highlighted in Fig. 2.
ABC-SD approach and then, we describe specifications and the
used mechanisms in the proposed clustering and the routing 5.2. ABC-SD clustering mechanism
algorithms.
The clustering process is preceded by the setup of the network
5.1. Design goals that consists of bootstrapping and neighbor discovery.
The requirements of sensor-based applications require that 5.2.1. Bootstrapping and setup
sensor networks become smarter. Since sensors are designed with When the sensors deployment is carried out, each sensor
limited resources, networking these sensors remains a very ap- si , i ∈ [1, N ] ∩  and also the BS broadcasts a H _MSG packet that is
pealing and important issue of WSNs research. Thus, in this paper, received by each node positioned in the communication range of
we are positioned in WSNs’ applications that require the use of the hello sender. Each node maintains two informations about its
energy efficient routing strategies that aim at prolonging the neighbors in its neighbor table: the id of the neighbor and the
network lifetime while taking into account the delivery of a good value R(i, j ) of the RSSI received. Whenever a given sensor receives
network QoS, especially in terms of throughput and data delivery. a H _MSG packet, it adds an entry in its neighbor's table. At the end
Hence, given the requirements in terms of the applications' needs, of the neighbor discovery time, each sensor si , i ∈ [1, N ] ∩  sends
designing an energy efficient protocol for routing the gathered its triplet (id, Er (si ) , 5 (si )) to the BS by using a controlled flooding
data remains actual, given the resource limitations exhibited by mechanism that forces a sensor not to forward a packet if it al-
sensor's design. To achieve this goal, we designed a bio-inspired ready forwarded it. The flooding operation is executed during a
assignment of followers of each CH in ℶ(ch). So, the initial popu-

lation of the ABC algorithm is generated according to the number
of CHs. Each individual containing a sequence of m randomly se-
lected cj ∈ ℶ(ch), j ∈ [1, m] ∩  in such a way that each CH can
directly communicate with at least one CH and at least one CH can
directly communicate with the BS by exploiting their neighbor
tables. The number of elements of ℶ(ch) is not greater than 5% of
the whole sensors. For the followers assignment, a population of
bees is used to find the best CH where each bee flies in the m-
dimensions search space. Each CH is assimilated to an employed
bee.
The energy wastage that can be introduced by data transferring
is intended to be reduced in a way that the distance as well as the
number of hops among sensors and their corresponding CHs is
kept as small as possible. Since our proposed protocol aims at
being a multi-hops cluster-based routing protocol, the number of
hops within a cluster is not reduced but the path that takes the
data towards the CH is chosen in a way that the number of crossed
nodes is smallest as possible. This is explained in Section 5.3. So, to
achieve the distance shortening, each sensor si ∈ S , i ∈ [1, N ] ∩  ,
becomes a follower of a given cj ∈ ℶ(ch), j ∈ [1, m] ∩  , i.e., an
element of the list f (cj ), by considering the best RSSI value Rb (see
Eq. (10)) among the CH received R(i, j ) values. See Illustration 1 for
Fig. 2. The main steps of the proposed ABC-SD protocol. a good understanding:
Rb = max (R (i, j ))
certain time limit. When receiving the triplets, the BS starts the j ∈[1, m]∩ (10)
clustering process.
Illustration 1. If the CHs c1 and c2 receive RSSI values from sensor
5.2.2. Clustering process s3, s3 will be assigned as a follower of the CH that received the best
Before giving the description of our proposed clustering algo- RSSI from s3. Thereby, for each sensor si , i ∈ [1, N ] ∩  , sensors are
rithm, we present some mathematical concepts used for the evaluated and assigned to their corresponding heads.
clustering process. Let λ d (see Eq. (7)), d ∈  ⧹{0} represents the d-
dimensional Lebesgue measure defined on subsets of d : So, when the followers are built, the best CHs are selected ac-
cording to the fitness function depicted in Eq. (18), and the posi-
λ d (( ) = ∫( 1 dx
(7)
tion update process of the ABC algorithm (see Algorithm 1). The
proposed clustering algorithm is given thereafter (see Algorithm
Since the considered sensing environment + is a 2-dimen- 2). The main relationship between the proposed ABC-SD protocol
sional square field, the area of ( j ⊆  ×  is given by λ2 (( j ), and the original ABC protocol lies in the position update process of
j ∈ [1, N ] ∩  . Then, let us consider that, sensors are deployed by a the ABC algorithm, which is used in the optimization of sensors
random process that positions the sensors at random points in + . assignment to clusters in ABC-SD.
Now, for each ( j ⊆ + : j ∈ [1, N ] ∩  , let us consider the number
Algorithm 2. The ABC-SD clustering algorithm.
N (( j ) of sensors in ( j . Then, N (( j ) obeys the following axioms:
Begin
Axiom 1. {N (( j ) : ( j ⊆ + , j ∈ [1, N ] ∩  }, which is the set of
1. Construct the set ℶ(ch)
random variables that represents clusters, is a Poisson process on
the sensing environment + with the density parameter r > 0. 2. Generate the initial population Xj , j ∈ [1, m] ∩ 
3. Repeat
Axiom 2. N (( j ) has the Poisson distribution with parameter 4. For each sensor si , i ∈ [1, N ] ∩ 
rλ2 (( j ). The probability mass function of N (( j ) is given by Eq. (8) 5. Evaluate RSSI values received by each CH in Xj
(see Johnson et al., 2005): 6. Assign the sensor si to a CH according to Eq. (10)
7. Compute the fitness function according to Eq. (18)
p (k ) =
( rλ2 (( j ) )k
× e−rλ2 (( j) 8. Launch ABC algorithm for position update
k! (8)
9. Until Maximum Cycle Number
Axiom 3. Since areas ((1, (2, … , ( j ) are such that ⋃( j ⊆ + and End
⋂( j = ∅, the collection of variables (N ((1) , N (( j ) , … , N (( j )) is a
sequence of independent random variables.
Then, after the bootstrapping and setup phase, the BS has to Besides that, since the number of clusters in this approach
compute the set ℶ(ch) of CHs and construct the clusters. The follows the Poisson distribution, and as demonstrated in Johnson
process starts by the construction of the set SCHc of candidates to a et al. (2005), at the end of followers assignment, the number of
CH position according to Eq. (9). Having sufficient energy is the sensors within each cluster will follow a geometric distribution,
main condition to be eligible as a CHc. In other words, only the particularly in the case of data packets retransmission (see Section
sensor that has energy level above the threshold value εt, can be 6.1.2). That combination of the Poisson and the geometric dis-
taken as candidate: tributions is known as the geometric Poisson distribution that is
SCHc = {si , i ∈ [1, N ] ∩  : Er (si ) ≥ εt } (9) usually used in the description of clusters and their members.
At the end of the network configuration, the BS informs each
Next, the ABC algorithm presented in Section 3.2 is used in the sensor, the cluster in which it belongs, i.e., the id of its
corresponding CH, again by using a controlled flooding mechan-

ism. Also, each CH receives the number of sensors in its cluster, the
id of its next hop (i.e., the next CH or the BS) and optionally the id
of its child CH. Again, the controlled flooding operation is executed
during a certain time and after that time, each Clm starts the route
discovery process that is highlighted in Section 5.3. Then, when
that operation is completed, in order to save energy and as
adopted by Labraoui et al. (2013), the CH builds the TDMA slots
time of each Clm. This is described in the following section.
5.2.3. Network scheduling: energy saving method

The MAC layer protocol is quite important in the design of
sensor networks, especially for energy saving. Fairness, latency
and throughput are the main challenges in traditional MAC pro-
tocols. In addition to these challenges, sensor networks aim at Fig. 3. Cluster presented like a k-way tree where the CH is the root and at each
being designed with power efficiency and scalability. The S-MAC level of the tree, each sensor si ∈ c1 has no more than k children.
protocol, which is a complex and powerful MAC protocol designed

for WSNs, which allows sensors to periodically sleep, has been Section 5.3), it is now the time for CHs to build TDMA frames. In
introduced in order to achieve these aims. Of course, in the S-MAC fact, during the steady state phase (see Section 5.2.4), each sensor
protocol, the self-configuration of sensors is well performed and has to gather information and transmit it to its CH, at its TDMA
energy saving is significant, but latency and throughput remain slots time. Of course, in WSNs design, the way as well as the time
problems. However, adaptive listening improves it significantly of transmitting the data depends on the application requirements.
(Malesci and Madden, 2006). Indeed, tracking applications such as bush fire must immediately
In networks with clusters in which communications are relay the reported temperature that is higher than the fixed
achieved in a multi-hop manner, usually where there are N sender threshold, whereas soil monitoring application, e.g., in irrigated
sensors and one receiver sensor, i.e., many-to-one, a good time agriculture, sensors can just need to report gathered data during a
synchronization among all sensors is important particularly for defined time. In our approach, when each cluster completed the
synchronous networks, i.e., there is not idle time for sensors, all route discovery process, each CH builds distinct TDMA slots for its
sensors can send/receive packets in the same time. In the design of followers by dividing the time into a different size of a fixed
the proposed clustering approach, sensors' radios are not always number (the number of Clm of each cluster) of slots, each slot unit
turned on, as adopted by a wide number of clustering algorithms lasts st μs .
for sensors networks (Cai et al., 2015; Karaboga et al., 2012; Indeed, since sensors can communicate by using a multi-hop
Hammoudeh and Newman, 2015). Also, sleep periods can be dif- path, before switching off its radio, a sensor that is in the path of a
ferent from a sensor to another. Because of this fact, commu- given sensor has to wait a little extra time in which it receives and
nications in the proposed sensor network especially inside the forwards all packets that must transit through it. In our approach,
constructed clusters are asynchronous. So, in order to save energy, the path is seen as a tree where the CH is the root. A simple case is
each sensor has a TDMA slot time in which it wakes up its radio for given in Illustration 2.
sending or receiving packets.
A number of works showed that asynchronous networks do not Illustration 2. For instance, we schematize a cluster c1 with the
need complex and expensive synchronization needs. Interested set of followers f (c1) = {s1, s2, s3, s4 , s5, s6, s7, s8, s9, s10 } in Fig. 3. So,
readers may refer to Heidarian et al. (2012). In addition, because depending on the number of hops, the size of each slot may differ.
low-power operations are preferred in large-scale sensor net- An illustration of the TDMA frame of the cluster c1 is given in Fig. 4.
works, our design expects a medium access protocol that includes
Concretely, a fixed slot time is first assigned to all leaf nodes,
effective and low-power operations. That fact allows, the exten-
then progressively, the length of the slot time of the next hop is set
sion of the number of sensors. In this light, Polastre et al. (2004)
proposed a very simple and powerful implementation of MAC to one unit of slot (its own slot) plus the number of its sensor child,
protocols for ad hoc networks called B-MAC and the performance i.e., the depth of the subpath, times the unit of slot. The length St of
evaluation achieved by Kabara and Calle (2012) shows its values the slot time of an intermediary node is given by Eq. (11), h is the
added compared to others. Moreover, B-MAC alternates sleep and number of child sensors:
wake up periods during the network lifetime like other simplified St = (h + 1) × st (11)
medium access protocols designed for sensor networks.
Furthermore, B-MAC implements a sleep/wake up mechanism
known as the low power listening and the protocol is reconfigur-
able by upper layers through the proposed flexible application
interface. Our proposed protocol exploits the B-MAC features in
the construction of TDMA slot time. However, for simplicity rea-
sons, we assume that sensors can only access the channel during
their allocated slot time unlike the B-MAC in which a method of
periodically checking the channel for radio activity is im-
plemented. Moreover, since our routing protocol is a cluster-based
one, we introduced a mechanism in which each sensor can only
receive packets from its Clm (see Section 5.3), this allows the
avoidance of collisions. The implemented TDMA mechanism for
energy saving is highlighted in the following paragraphs.
In each round, at the end of the clustering process, the network
scheduling step takes place. After the route discovery process (see Fig. 4. An illustration for the construction of the TDMA frame for the cluster c1.
By assuming that, each sensor has to send its gathered data number of distinct CHs in the position vector of the ABC algorithm.
each u unit of time (a defined number of minutes or hours) and Like adopted by Heinzelman et al. (2000), the optimal number of
there is a small additional time ϵ in μs for data acknowledgement CHs should be approximately set to 5% of all nodes. Since in our
messages, each sensor will switch off its radio at time w (see Eq. proposed approach the fitness is used only for a comparison pur-
(12)): pose, without loss of generality, we assume that p ¼1.
The TDMA based multi-hop approach adopted for the intra-
w = u + St + ϵ (12)
cluster communication could slightly prolong the cluster sche-
This way of dividing the time periods for cluster scheduling duling time for a cluster with more Clm than others. This might
(TDMA) will allow that a sensor goes to sleep when it sends its introduce a supplementary delay. So, especially for the commu-
packet to its parent node (next hop) and when it receives and nication link quality, the QoS is considered as the second criterion,
forwards packets of its child nodes. The same mechanism, which which aims at maximizing the packet delivery to the BS while
also allows CHs to sleep in order to save their energy is im- reducing the delay. Thereby, in order to maximize the cluster
plemented for inter-cluster communication. In fact, since each CH communication link quality, let us define a quality parameter in-
knows its next hop towards the BS, which is either another CH or dicator QP Clmj (x ) , j ∈ [1, m] ∩  , x ∈ [1, N (( j )] ∩  of a member of
the BS itself, we implemented also simplified TDMA mechanism for the cluster with the head cj ∈ ℶ(ch) in Eq. (16). This quality in-
data transfer by CHs to the BS. Once it receives and aggregates all dicator includes Rm (Clmj (x )) (see Eq. (14)), which is the best RSSI
its followers’ gathered data, the CH sends the aggregated data in a value received by the Clmj (x ), and the worst value is Rw (Clmj (x ))
unique D _AGG message to the next hop toward the BS. After that, it (see Eq. (15)):
switches off its radio and wakes up at the start of the next u unit of
time in order to receive a new sequence of gathered data from its R m (Clmj (x)) = max (R (Clmj (x), i))
j ∈[1, m]∩ 
followers. Indeed, each CH receives its slots length and the fre-
i ∈ [1, N (( j )] ∩  and i≠x (14)
quency at which it will wake up for the inter-cluster commu-
nication, from the BS at the start of each round.
Besides that, in order to avoid interference of signals that R w (Clmj (x)) = min (R (Clmj (x), i))
j ∈[1, m]∩ 
usually exist in the case of large scale sensor networks, in addition
to the clear channel assessment feature, we use the effective col- i ∈ [1, N (( j )] ∩  and i≠x (15)
lision avoidance mechanism that uses the signal strength (RSSI)
implemented in the B-MAC protocol. At the end of the creation of ⎡ ⎤
1
the TDMA frame, each CH sends the slot length of each of its fol- QP Clmj (x) = ⎢ Rem (Clmj (x)) × ⎥
⎢⎢ Rem (Clmj (x)) − Rew (Clmj (x)) ⎥⎥ (16)
lowers again by using a controlled flooding mechanism. Then, the
steady-state phase is launched. QoS
Then, we define the QoS criterion f in Eq. (17) in such a way
that the quality of the communication link within the cluster be-
5.2.4. Steady-state comes maximal by minimizing the worst link qualities:
For each sensor, the steady-state phase consists of the use of its
N (( j )
TDMA slots time to transmit the gathered data to its corresponding
f QoS = ∑ QP Clmj (x)
CH, either in a single-hop or in a multi-hop manner, depending on x=1 (17)
the density of the cluster and the location of the CH. This is well
explained in Illustration 4 with an UML sequence diagram (see We bring back the fitness function to a linear programming
Section 5.3.2). When receiving all gathered data from its followers, problem. In fact, we need to minimize the energy loss and the
the CH aggregates the received data and sends it to the BS by using worst link quality. To achieve this, the two proposed criteria in Eqs.
the inter-cluster communication, i.e., by using intermediary CH or (13) and (17) are used to build a multi-objective fitness function.
directly to the BS if the next hop of the considered CH is the BS. For simplicity reasons, we use the weighting parameter α and β in
order to transform these objective functions into a single fitness
5.2.5. Fitness function derivation function. Thus, let us give the fitness function that includes the
The previously described clustering process in Section 5.2.2, energy level criterion, the QoS criterion and the weighting para-
aims at maximizing the network lifetime by well selecting CHs. In meters α and β, as a linear programming problem in Eq. (18):
the selection of CHs, we take into account two criteria: the energy Minimize fit = α × f energy + β × f QoS (18)
efficiency and the quality of service (QoS). The first constraint that
has to be respected is the energy saving criterion while choosing a Indeed, since the objective of the fitness function is to mini-
sensor as a CHc. Indeed, since the CH is responsible for data ag- mize the energy consumption and to minimize the use of worst
gregation and transferring all the Clm gathered data, more energy link, i.e., maximize the QoS, we use β to control the QoS and α to
is used and these sensors’ energy levels can decrease quickly. So, control the energy consumption. For a good weighting, α and β are
since in our network design there is no sensor with a particular subjected to the constraints given in Eqs. (19) and (20):
power resource, CHs must be selected in an optimal way. There- α=1−β (19)
fore, the evaluation of fitness considers the energy level of the CHc,
which should be greater than the fixed threshold value εt . More- 0<β<1 (20)
over, the proposed clustering algorithm aims at reducing the en-
ergy depletion that can be introduced during CHs' operations, by
minimizing the number of CHs since sensors' intra-cluster com- 5.3. ABC-SD routing mechanism
munication is achieved in a multi-hop manner. So, we define the
energy criterion of the fitness function fenergy in Eq. (13): Our proposed routing algorithm adopts an oblivious routing in
which the routing path is discovered by each Clm before starting
k
f energy = p × the steady-state phase. These paths cannot change throughout the
m (13)
round. The design of the routing algorithm is described before
where the constant p is a proportionality constant and k is the presenting the route discovery process in Section 5.3.2.
id type srcId destId hopC sumE minE data 1. Increments the number hopC of hops.
Fig. 5. The adopted unique packet format with its eight fields for the data transfer
2. Updates the sum of the remaining energy in the path sumE.
over the network. 3. If the Clm remaining energy is lower than that in the current
minE, replace the value of minE by the actual Clm remaining
Table 4 energy.
Descriptions of the fields in the packet format. 4. Adds the Clm id in the data field.
5. Rebroadcasts the P _DISC .
Field Description
id is the unique identifier assigned by sensor to a packet In this way, the packet will reach the CH. Certainly, because
type is the type of the message clusters are not really disjoints in practice, a Clm of a given cluster
srcId is id of the source sensor may receive a P _DISC packet from a Clm of a close cluster, if these
destId is the id of the destination sensor. destId always contains the id of the sensors are in the same communication range. In such a case, by
CH
hopC is the number of hops crossed by the packet before reaching the
using some features of the B-MAC protocol, the receiver will
destination consider the packet only if the destId field contains its CH id, i.e., if
sumE is the sum of the remaining energy of all sensors in the path they have the same CH. When receiving the P _DISC packet, the CH
minE is the energy of the sensor that has the minimum remaining energy in will launch a path acknowledgement packet P _ACK to the sender
the path
srcId. The P _ACK packet is built from the received P _DISC packet
data is the data field
by altering id, type, srcId and destId fields. The value of the id field
in the P _ACK packet structure is assigned by using the id of the
5.3.1. The packet format received P _DISC packet in such a way that a Clm (i.e., the sender)
In the design of the proposed routing protocol, we adopt a can recognize that it is the path acknowledgment message of its
unique packet format. The packet is structured into eight fields: sent path discovery message. Of course, since the CH may receive
packet id, packet type, source sensor id, CH id, the number of hops many versions of a same initial P _DISC message and launch path
in the path, sum of the remaining energy of the path, minimum acknowledgement messages for them, the source sensor may
energy of the path and data. The packet format is given in Fig. 5 therefore receive more than one P _ACK packet at the end of the
and the complete description of the packet fields is given in Ta- route discovery time. Well, in such a situation, the source sensor
ble 4. The fields hopC and sumE are initially set to zero. minE in- has to choose the best path.
itially contains the remaining energy of the sender, i.e., Er (srcId). The choice of the best path is achieved by making a tradeoff
Each packet in the whole network must have a unique identi- between the number of hops in the path and the path's available
fier. Permitting a unique identification of a packet is necessary for energy. In order to realize that, we introduced a non-linear choice
the used controlled flooding mechanism. So, each packet gener- parameter ζ in the design of the proposed routing algorithm that
ated by a sensor has an id compound of the sensor id that is aims at choosing the path with at least hops and better remaining
energy. So, let us define the cost-based function ζ (p (l )) that
concatenated with a sequence number. The field data is structured
evaluates the energy strength of a path p (l ) in Eq. (21):
differently depending on the type of the packet. The used mes-
sages are described in Table 5. ⎢ sumE − (n (p (l)))2 ⎥
ζ (p (l)) = ⎢ (n (p (l)))−1 × ⎥
The H _MSG message is executed in the same mind as the hello ⎣ minE − n (p (l)) ⎦ (21)
message of the B-MAC protocol. For a P _DISC message, the field
data initially contains the srcId. In the P _ACK message, fields id, where l ∈ [1, N (( j )[ ∩  : j ∈ [1, m] ∩  . l is the lth P _ACK packet
type, srcId and destId are modified as explained in Section 5.3.2. In received by the P _DISC sender, i.e., the Clm and n (p (l )) is the
addition to the information to transfer, the path toward the CH is number of hops in the path p (l ). Finally, when the best paths are
concatenated with the information in the data field in D _MSG chosen, each Clm sends a R _MSG to its CH by using the controlled
messages. The D _ACK message is transformed into a simple ACK flooding mechanism implemented in the proposed protocol. While
message like in the B-MAC implementation. receiving all R _MSG from its followers, the CH can now proceed to
the construction of TDMA frames as explained in Section 5.2.3. We
5.3.2. Route discovery mechanism give in the following, the algorithm (see Algorithm 3) for route
When the network is initialized and the clustering process is discovery, which is executed by each Clm.
completed, each Clm starts a route discovery in order to construct a Algorithm 3. The ABC-SD route discovery algorithm.
pre-determined path toward its CH. To start the route discovery
process, each Clm broadcasts a P _DISC message in the network Begin
with its CH id as the destination sensor. When a given Clm receives 1. broadcasts (P _DISC )
a P _DISC message, it will perform the following actions: 2. while (t1)
3. if (receive (P _DISC )) then
Table 5 4. hopC ¼hopC þ 1
The used messages in the ABC-SD routing algorithm. 5. sumE ¼ sumE þ Er (Clm )
6. if (Er (Clm ) < minE) then
Message Description
7. minE ¼ Er (Clm )
H _MSG is a hello neighborhood discover message 8. data ¼data ⊙Clm
P _DISC is a path discovery message
9. rebroadcasts (P _DISC )
P _ACK is a path acknowledgement message sent by the CH to a source
sensor 10. else if (receive( P _ACK )) then
R _MSG is a route message that contains the chosen path from a Clm and its 11. Compute the path strength according to Eq. (21)
CH 12. while (t2 )
D _MSG is a data message sent by each Clm to its CH
13. if (receive( P _ACK )) then
D _ACK is a data acknowledgement message sent by the CH to the sender
sensor
14. Compute the path strength according to Eq. (21)
D _AGG is an aggregated data by a CH for sending to the BS 15. else if (receive( P _DISC )) then
Fig. 6. Route discovery.
16. destroy( P _DISC ) t1, the sensor s5 sends the message s5(P_DISC). Sensors s4 and s5
17. Choose the best path among all computed path strength will then receive its sent discovery message since they are in its
18. Launch a R _MSG message. neighbor's table. So, the sensor s4 will forward the message s5
End (P_DISC) to its next hop, i.e., s3 and the sensor s3 will then forward
it to their head s2. In the same way, since the sensor s3 also directly
received the message s5(P_DISC), it will also forward again that
In this way, unlike other bio-inspired routing algorithms for message to their head s2. Thus, when receiving these discovery
WSNs like those proposed in Zungeru et al. (2012), Kuila and Jana messages the head s2 will launch two distinct acknowledgement
(2014), Cai et al. (2015), each sensor si , i ∈ [1, N ] ∩  keeps just one messages s5(P_ACK) to s5 since it received two distinct discovery
route towards its CH. Of course, while clustering and routing messages from s5, from two different paths. To conduct well the
processes are executed at the start of each round, the Clm estab- steps in Algorithm 3, we took a case that one of these acknowl-
lished route may not be the same. An illustration is given below. edgement messages reaches the sensor s5 during the time t2. At
last, the sensor s5 will inform its head s2 the chosen path by
Illustration 3. For instance, in Fig. 6, a sequence of performed launching the route message s5(R_MSG).
actions for establishing routes is described. In this illustration, we
take a simple case in which a cluster with the head s2 and its 5.3.3. Data transfer and acknowledgement mechanism
followers f (s2 ) = {s1, s3, s4 }. During the time t1, each follower will At the end of paths discovery process and the establishment of
perform a number of actions (send/receive messages) in order to routes between each Clm and their CH, then comes the time of data
receive one or more paths toward s2 and during the time t2, it will gathering and transferring, which is explained in Section 5.2.4. In
choose the best path and informs s2 the chosen route among the fact, during its slots time (see Eq. (12)), a sensor will send its
received paths. In the figure, the filled arrow —▶ represents the gathered data to its CH. In the simulation, we stored the total
send of a new message. The open arrow ⟶ represents the for- number of received data from each Clm in each round, in order to
warding message. The dashed arrow represents the path ac- analyse the energy efficiency and throughput metrics that is ex-
knowledgement message both in sending and forwarding. plained in Section 6.2. An illustration of this process is given
In this instance, let us take the case of sensor s5. At the start of hereinafter.
Fig. 7. Steady-state: a sequence of actions in data transfer and acknowledgement mechanism.

Illustration 4. To illustrate the data transmission step, i.e., the

steady-state, we provide an UML sequence diagram in Fig. 7. In
this instance, let us consider a case of the BS and two clusters
represented by heads s2 and s6. In the diagram, the filled arrow —▶
represents the send of a new message. The open arrow ⟶ re-
presents the forwarding message. The dashed arrow re-
presents the data acknowledgement message both in sending and
forwarding.
For simplicity reasons, we illustrate the inter-cluster commu-
nication just in the cluster with the head s2. So, lets define
f (s2 ) = {s3, s4 , s5 }. In the sequence diagram, let us take the case of
s4. The sensor s4 sends its gathered data to the head s2 by
launching the data message s4(D_MSG). Then its next hop, i.e., s3
will receive and forward that message to their head s2. When re-
ceiving the message, s2 will launch a data acknowledgement
message to s4. When receiving all data messages from their fol-
lowers during their cluster's TDMA frames, the heads s2 and s6
have to switch off their radios and wake it up at the appropriate
time for the inter-cluster communication.
Since data packets are exclusively sent towards the discovered

and registered path and because our design aims at providing a
WSN with less rate of data loss, we implement a simplified ac-
knowledgement message of a sent data packet. Indeed, during
data transfer on a given path, when a cluster member Clmj receives
a D _MSG from a Clmj − 1 in the same path p(l), the Clmj sends back a
D _ACK message to the Clmj − 1 during the additional time ϵ (see Eq.
(12)). When not receiving the D _ACK message after the first part of
ϵ (in our implementation, ϵ is divided in 7 different parts), Clmj−1 will
retransmit the D _MSG message 3 times again. This process is de-
scribed in Fig. 8.
The above described retransmission process is also used in the
inter-cluster communication. So, by this mechanism, a sent D _MSG
message is acknowledged hop-by-hop in p(l) until it reaches the Fig. 9. Flow chart of the ABC-SD cluster-based routing protocol.
CH.
In summary, in order to have a clear picture about the opera-
6.1. Theoretical analysis of energy consumption
tion of the proposed scheme, Fig. 9 provides a flow chart showing
the various phases and the whole operations of the ABC-SD 6.1.1. Energy consumption derivation
protocol. According to the proposed design, the consumed energy at
each round includes the energy of bootstrapping, the energy of
paths discovery and the energy of data transfer. At the beginning
of each round, the bootstrapping process in which each sensor
6. Performance evaluation
si , i ∈ [1, N ] ∩  discovers its neighbors takes place. Each sensor
has to broadcast a H _MSG packet that will be received by a number
In this section, we propose a performance evaluation of the
of sensors in its communication range. A priori, we cannot know
proposed routing algorithm, which includes a theoretical analysis
the number of neighbors of a given sensor since the deployment is
of energy consumption and the simulation according to some
done randomly. Despite that, we suppose that, in the adopted
proposed evaluation metrics.
sensors' deployment strategy, the maximum number of neighbors
ß is given in Eq. (22):
⎡ r ⎤
ß = ⎢N × ⎥
⎢ λ2 (+ ) ⎥ (22)
By taking that into account, the expended energy Eboot (sj ) by a

sensor sj , j ∈ [1, N ] ∩  in the bootstrapping process is equal to the
energy consumed Ei for sending the H _MSG plus the energy con-
sumed in the reception of ß H _MSG packets from its neighbors
(see Eq. (23)). Hence, the overall network energy consumed Eboot ,
i.e., the energy consumed by all sensors, in the bootstrapping
process is given in Eq. (24):
Eboot (sj ) = Ei × (1 + ß) (23)

Fig. 8. Packet retransmission process.
N consumption Edata − t in a best situation for data packets transfer for

Eboot = ∑ Eboot (sj ) = N·Ei × (1 + ß) the whole network is given in Eq. (33):
j=1 (24)
Edata − t (Clmj ) = 2·Ei ((n (p (l)) − 2) + 1) + 2·Ei (n (p (l)) − 1)
Then, the energy consumption in paths discovery is computed
according to the energy expended while sending and receiving = 4·Ei (n (p (l)) − 1) (32)
P _DISC and P _ACK packets. Let Epdisc (Clmj ) and Epack (Clmj ) be the
expended energies respectively in sending and receiving a P _DISC m N (( j )
packet (respectively, a P _ACK ) by the Clmj , which is a follower of Edata − t = ndata − t ∑ ∑ Edata − t (Clmj )
j=1 l= 1
the head cj ∈ ℶ(ch), j ∈ [1, m] ∩  . In a worst case, i.e., by assuming
m N (( j )
that a P _DISC packet sent by Clmj will be received by all followers of
= 4·Ei·ndata − t ∑ ∑ (n (p (l)) − 1)
the head cj, the expended energy Epdisc (Clmj ) (see Eq. (25)) is equal j=1 l= 1 (33)
to the energy consumed Ei by the Clmj , in the broadcast of the
Finally, according to the aforementioned energy derivations,
P _DISC packet and the energy consumed in the receiving and re-
broadcasting (i.e., 2·Ei ) of the P _DISC by followers, i.e., by the energy expenditure (Eexp) in each round, which includes the
Clmj ∈ f (cj ): expended energy in the bootstrapping, routes establishment and
data packets transfer, in a good network condition is given in Eq.
Epdisc (Clmj ) = Ei × (1 + 2·N (( j )) (25) (34):
For all members of the cluster with the head cj, the expended Eexp = Eboot + Ere + Edata − t
energy by P _DISC packets is computed as shown in Eq. (26) by m
multiplying the energy expended by one follower with the num- = Ei·(N × (1 + ß) + 2· ∑ N (( j )·(N (( j ) + n (p (l)) − 1)
ber of followers of the head cj. Then let us give in Eq. (27), Epdisc, j=1
which is the sum of the expended energy by each cluster, i.e., the m N (( j )
energy expended by each si , i ∈ [1, N ] ∩  : + 4·ndata − t ∑ ∑ (n (p (l)) − 1))
j=1 l= 1 (34)
Epdisc (cj ) = N (( j ) × Epdisc (Clmj ) = Ei·N (( j ) × (1 + 2·N (( j )) (26)
m m 6.1.2. Packets retransmission derivation

Epdisc = ∑ Epdisc (cj ) = Ei· ∑ N (( j )(1 + 2·N (( j )) The previous energy derivation for data packets transmission is
j=1 j=1 (27) achieved by assuming that all data packets are normally routed
Unlike the energy expended by the broadcast and reception of towards clusters. In practice, due to the hostile environment in
P _DISC packets, we compute the exact value of the energy ex- which WSNs are generally deployed, for instance, in a forest or in
pended for the P _ACK packets, since the acknowledgement paths an environment with many obstacles like buildings, loss of packets
are known. So, by using the number of hops n (p (l )) of each path p during the data transfer may occur. Therefore, according to the
(l) taken by P _ACK packets, the energy expended in an acknowl- adopted packet retransmissions mechanism previously described
edgement of a P _DISC packet initiated by the head cj to a follower in Section 5.3.3, let us define the probability P (p (l ) , k ) (see Eq.
Clmj is given in Eq. (28): (35)) of success on each data packet transmission on the path p(l):
Epack (Clmj ) = Ei × (1 + 2·(n (p (l)) − 2)) (28) P (p (l), k ) = e−rn (p (l)) (35)
where l ∈ [1, N (( j )[ ∩  . By considering all followers of the head where r > 0 is the density parameter of the used Poisson dis-
cj, i.e., each Clmj ∈ f (cj ), the expended energy for P _ACK packets by tribution in Section 5.2.2 for the distribution of clusters on the
each cluster is given in Eq. (29). In addition, the expended energy sensing environment. Then in the case of a data packet re-
by the network in P _ACK packets, which corresponds to the sum of transmission, the modeling of the energy consumed in a certain
each cluster's expended energy in P _ACK packets is given in number of retransmissions depends on the probability (see Eq.
Eq. (30). So, the energy expended in the routes establishment (Ere) (36)) that the kth retransmission leads to the first successful
is given in Eq. (31). transmission. That probability P (X = k ) is given such that the
number of data packet retransmissions follows the geometric
Epack (cj ) = N (( j ) × Epack (Clmj ) = Ei·N (( j )(1 + 2·(n (p (l)) − 2)) (29) distribution:
m m P (X = k ) = (1 − P (p (l), k ))k − 1·P (p (l), k ) (36)
Epack = ∑ Epack (cj ) = Ei· ∑ N (( j )(1 + 2·(n (p (l)) − 2))
j=1 j=1 (30) where X is the random variable that represents the number of
successes in a data packet delivery. Therefore, the energy con-
m
sumption Edata − r (Clmj ) for n retransmissions of one data packet sent
Ere = Epdisc + Epack = 2Ei· ∑ N (( j )·(N (( j ) + n (p (l)) − 1) by Clmj can be expressed as done in Eq. (37). Hence, in each round,
j=1 (31)
the energy consumption Edata − r for the retransmission of ndata − t
Furthermore, we can compute the expended energy in the data packets for the whole network is given in Eq. (38). In the
routing of data packets since the number of hops is known in routing algorithm, the maximum number of retransmissions is set
advance when a Clm tries to send its gathered data to its CH. to 3:
Thereby, the resulting energy consumption in a data packet
transfer toward a path p(l) is equal to the energy expended by the Edata − r (Clmj )
Clm in the sending and the energy expended by the CH at reception n N (( j )
plus the energy of reception and forwarding at the intermediary = ∑ ∑ {(1 − P (p (l), k ))k − 1·P (p (l), k )×
sensors in the path, plus the energy of sending and receiving the k=1 l= 1
D _ACK messages. (see Eq. (32)). So, by assuming that each Clm has
to send ndata − t data packets to its CH in each round, the energy
(E data − t (Cl mj ) + (k − 1) Ei } ) (37)
m 6.3. Simulation and discussion

Edata − r = ndata − t ∑ Edata − r (Clmj )
j=1 (38)
We evaluated the proposed ABC-SD protocol by conducting
This energy derivation provides a theoretical overview of the series of intensive experiments in various scenarios. To be closer to
overall network energy consumption in each round. Since, we aim the reality, we exploited the behaviors of the Chipcon CC2420 that
at providing a WSN with high throughput, i.e., with a maximum is briefly described in Section 4.1 and its complete data sheet can
be found in Texas Instruments (2014). In this simulation, we used
number of delivered packets, the introduced packets acknowl-
the realistic sensors' characteristics, the wireless channel and radio
edgement and the retransmission mechanism have added a sup-
models included in the Castalia 3.2 simulator. Castalia is a simulator
plementary energy consumption. But, as we observed in simula-
for WSNs and generally, for networks of low-power embedded
tion, the proposed clustering routing algorithm significantly im-
devices, which is based on the OMNetþ þ platform. Since, the
proves the overall performance of the considered WSNs. B-MAC is not found by default in the node communication module
of the Castalia simulator, for this simulation, we have integrated a
separated implementation in C þ þ of the B-MAC.
6.2. Metrics of the performance evaluation
Unlike the bio-inspired clustering and routing approaches
proposed in Kuila and Jana (2014), Karaboga et al. (2012), sensors
To evaluate the performance of the proposed algorithm, we
of the proposed WSN model are homogeneous and can perform
analyzed the following metrics: any task in the network. We have not used some special sensors
with particular behaviors that act as pre-deployed gateways. It is
6.2.1. Network lifetime
assumed that all sensors are locations unaware. Indeed, all sensors
Since the lifetime is an important characteristic commonly
of our network model are not equipped with a self-locating hard-
analyzed in sensor networks performance evaluation, in the si- ware such as the global positioning system. In the proposed clus-
mulation we observed 3 metrics to evaluate the network lifetime tering algorithm, we use an initial population of 50 bees and we run
of our algorithm: the positions update of the ABC algorithm under a maximum of 500
cycles. The ABC swarm parameters are summarized in Table 6.
Energy consumption: It is a metric that allows us to analyse the Experiments were carried out with randomly and uniformly
average energy expended by each si , i ∈ [1, N ] ∩  during the deployed stationary sensors on a square field of 100 × 100 m2 that
simulation times. represents the sensing area. The BS is positioned at the coordinate
Energy efficiency: This metric is measured by evaluating the ratio (0; 0) of the field. The initial energy of each sensor is equal to the
of the total number of delivered packets to the BS and the energy of two AA batteries, which is set to 18,720 J. To evaluate the
overall network's consumed energy during the simulation powerful and the full adaptability of the ABC-SD protocol, we
times. At a given simulation time, that ratio is calculated ac- consider four scenarios of networks in which each sensor network
cording to the formula given in Eq. (39). We use this metric to has a size of 100 × n: n = 1, 2, 3, 4 . In each considered network
analyze the network lifetime as well as the throughput: scenario, the proposed algorithm is executed during 5000 s. Since
∑ data packets delivered to the BS the number of sensors increases, in order to minimize the effect of
EE =
∑ sensor′s consumed energy (39) communication overhead, the length of each round is set to 500 s
and the TDMA slot length is taken 2/4 as of a second. The obtained
First sensor dead: This metric allows us to know the amount of results in both clustering and routing are presented in a combined
time that a sensor of our WSN design will be fully operative by output. The complete simulation parameters are given in Table 7.
evaluating the time until the first dead of a sensor during the In order to highlight the value added introduced by the pro-
simulation times.
posed clustering and routing approaches, the performance of the
ABC-SD protocol is compared with some well known cluster-based
6.2.2. Throughput
protocols for WSNs:
Given the fact that a lot of applications of WSNs need routing
protocols with a high rate of successful packets delivered to the BS, The LEACH (Heinzelman et al., 2000) protocol that is the widely
we use two metrics in order to analyse the throughput: used in comparison purpose, the most popular and completely
distributed clustering algorithm for WSNs.
Amount of delivered packets: This metric is used to evaluate the The LEACH-C (Heinzelman et al., 2002) protocol, which is the
amount of packets received by the BS at the end of the simu- centralized version of the LEACH protocol.
lation time. The PSO-C (Latiff et al., 2007) protocol that is a completely
Packet loss rate: This metric is calculated according to the for- centralized swarm based approach, which is inspired by social
mula given in Eq. (40) in order to know the rate of packet losses behaviors of bird flocking and fish schooling.
caused by the designed routing algorithm: The PSO-HC (Elhabyan and Yagoub, 2014) protocol that is a
∑ received data packets by the BS hierarchical bio-inspired clustering approach for WSNs.
PL = 1 −
∑ sent data packets to the BS (40)
The ABC-C (Karaboga et al., 2012) protocol that is a centralized
clustering protocol which is inspired by the foraging behaviors
of honeybees.
6.2.3. Network coverage
The network coverage is an important characteristic in sensor Table 6
networks, especially in WSNs requiring a high availability of ABC parameters.
gathered information. Even if sensors are well distributed on the
Parameter Value
sensing environment, unclustered sensor nodes cause the loss of
information on their coverage area. To evaluate the performance in Number of cycles 500
Population size 50
terms of network coverage, we reported the number of un-
Limit for neighborhood search 20
clustered sensors in each round during the simulation time.
Table 7 200 ABC-SD

Simulation parameters. ABC-C
180 PSO-HC
PSO-C
Average energy consumed by each sensor (J)

Parameter Value LEACH-C
160 LEACH
Square (m2) 100 100 140
BS location (0;0)
Number of sensors 100, 200, 300, 400 120
Maximum number of CHs 5%
100
Initial energy (J) 18,720
εt (J) 4680 80
Radio frequency (GHz) 2.4
Packets length (Bytes) 128 60
Packets rate (packet/s) 1
40
Transmission speed (Kbps) 250
Transmission range (m) 75 20
TDMA slot time (s) 0.4
CDMA MAC protocol B-MAC 0
100 200 300 400
Times (s) 5000
Round length (s) 500 Network scenarios (number of sensors)
Fig. 11. Energy consumption.
In each network scenario, we proceeded to 10 runs of these

aforementioned protocols, including the ABC-SD. In each simula- better than the LEACH and the LEACH-C. In the same mind, in their
tion run, 4 different network topologies are generated, totaling 40 proposed protocol, Elhabyan and Yagoub (2014) reported that, the
network topologies. Each result presented hereafter is the average PSO-HC protocol provides better results than the compared pro-
of outputs obtained in these runs. Also, all results are given at 99% tocols. The results obtained by the conducted experiments are
confidence interval. Before presenting the results, let us evaluate given in Figs. 11–19. These graphics show the obtained results of
by simulation the best value of the weighting parameter α used in the ABC-SD including the ABC-C, PSO-HC, PSO-C, LEACH-C and
the fitness function (see Section 5.2.5), which maximizes the LEACH protocols.
performance of the ABC-SD protocol. To do it, eleven distinct va- The energy consumption is measured by the average energy
lues of α ∈ [0; 1] have been tested. In order to choose the best one, expended by each sensor in each of the four network scenarios. It
we measure the average energy consumed by each sensor during can be observed in the results' diagrams presented in Fig. 11 that
the simulation time. While considering the network scenario with the proposed cluster-based ABC routing protocol performs better
100 sensors, it can be observed in obtained curves (see Fig. 10) that than the compared one in terms of energy consumption. In each
the best value of α is 0.1. Also, with the 3 other network scenarios, network scenario, the average energy expended by each sensor as
we found the same value of α. well as their standard deviations in each case is computed and
Globally, we measured the three principal metrics described highlighted in Table 8. It can clearly be seen that sensors in the
above in Section 6.2: network lifetime, the throughput and the ABD-SD protocol consume less energy than the sensors in the
network coverage. The network lifetime is studied here by the compared protocols. However, we must recognize that in terms of
measurement in each network scenario, of the energy consump- amount of variation of the expended energy by each sensor, i.e.,
tion of each sensor, the energy efficiency and the time at which the the standard deviation, the results obtained in PSO-C and LEACH-C
first sensor dies. In their experiments, Latiff et al. (2007) as well as protocols have the minimum dispersion.
Karaboga et al. (2012) showed that the PSO-C protocol performs Although it is needed that the quantity of the expended energy
by each sensor be minimal, the amount of data delivered at the BS,
100 in other terms, the reliability of the network, is very important
specially in the case of large scale WSNs. So, in Fig. 12, we present
the obtained energy efficiency that is equivalent to the amount of
data received by the BS with 1 joule of power, during the simu-
80 lation time in each network's scenario. Also, for evaluating the
network lifetime, diagrams in Fig. 13 show the time at which the
first sensor dies in each network's scenario. It can be seen that the
first dead sensor in ABC-SD occurs long after the first dead in
60 LEACH-C and LEACH. Moreover, according to the curves visible in
Fig. 12a–d, we conclude that the energy efficiency in the ABC-SD
Table 8
40 Average sensor's energy consumption (μ¯) and standard deviation (σ ) .
Protocol Network scenario
#100 #200 #300 #400

20
μ̄ s μ̄ s μ̄ s μ̄ s
ABC-SD 70.21 1.10 57.03 1.83 59.05 1.06 51.02 0.93

ABC-C 73.01 1.63 59.13 1.93 67.01 0.95 71.12 1.01
0 PSO-HC 75.10 1.97 60.41 1.94 64.63 1.02 54.06 1.04
0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 PSO-C 80.03 0.27 80.02 0.51 80.01 0.90 80.04 0.52
Times (s) LEACH-C 83.13 0.81 82.61 1.02 82.01 0.23 81.31 0.41
LEACH 158.01 3.09 162.14 2.36 150.10 0.93 147.03 1.68
Fig. 10. Energy consumed by each node in each value of α.
Fig. 12. Energy efficiency.
1600 important to note that, results obtained in PSO-HC, PSO-C and

ABC-SD
ABC-C
LEACH-C protocols are not much far away from each other. Un-
1400 PSO-HC
PSO-C
fortunately, the LEACH protocol presents poor results in all net-
LEACH-C work scenarios. This is due to the adopted long radio transmission
1200 LEACH
range and the single hop routing strategy in LEACH's design. In
1000 addition, in LEACH, there is a random and probabilistic based
mechanism for the selection of CHs that does not consider the
Times (s)
800 energy level of the sensor. Also, there is not a sleep/wakeup me-
chanism for energy conservation during the idle time. The adopted
600 strategies in their design led to weakness results, in particular, it
caused a considerable energy wastage and a low data delivery rate.
400
Furthermore, the adopted fitness function in the building of
200
clusters favored this visible gain in performance obtained in the
ABC-SD protocol. Indeed, the fitness function (see Section 5.2.5) is
0 designed in such a way that it takes into account the energy as
100 200 300 400
well as the QoS criteria. First, the energy criterion allows the
Network scenarios (number of sensors)
choice of CHs with sufficient energy since they act as relay sensors
Fig. 13. Time at which the first sensor dies. that aggregate and forward gathered data to the BS. Moreover,
since CHs and of course clusters change at each round, the power
used by CHs is balanced among other sensors. The second criterion
protocol is far better than the others since the proposed protocol as to it, concerns the assignment of the cluster members to a given
offers a high data delivery to the BS while consuming less power cluster according to the quality of the communication link. The
during all the simulation time. position update mechanism existing in the ABC algorithm used
However, it is important to note that the ABC-C protocol en- here in the proposed clustering algorithm efficiently helps us in
ables good results in terms of first dead. However, concerning the providing optimal assignment of cluster members. Moreover, the
results obtained in the evaluation of the energy efficiency in the adopted mechanism in the route discovery process allows the
ABC-C, the curves in Fig. 12 show good results for network sce- choice of the path with fewer number of hops, and which is less
narios with and 100 and 200 sensors, but in network scenarios power expensive (see the proposed model in Eq. (21)), in which
with 300 and 400 sensors, the ABC-C enabled results close to those gathered data will be forwarded to CHs. These mechanisms help
obtained in PSO-HC and PSO-C. This means that, the ABC-C pro- the ABC-SD for the well balancing of the overall power con-
tocol presents some shortcomings in terms of management of sumption of sensors. The results obtained here by the proposed
energy when the number of sensors grows. On the other hand, it is ABC-SD protocol, specially for network lifetime, confirm the
× 10 Table 10
2
Mean of packet loss rate (μ¯) and standard deviation (σ ) .
ABC-SD
1.8 ABC-C
PSO-HC Protocol Network scenario
PSO-C
1.6 LEACH-C
LEACH #100 #200 #300 #400
1.4
1.2
Throughput
ABC-SD 0.119 0.001 0.111 0.002 0.109 0.003 0.105 0.004

1
ABC-C 0.142 0.001 0.133 0.003 0.180 0.005 0.183 0.006
0.8 PSO-HC 0.183 0.001 0.180 0.002 0.178 0.005 0.172 0.006
PSO-C 0.206 0.001 0.219 0.003 0.226 0.004 0.235 0.005
0.6 LEACH-C 0.296 0.002 0.308 0.003 0.339 0.005 0.371 0.011
LEACH 0.332 0.005 0.349 0.008 0.361 0.008 0.392 0.019
0.4
0.2
0
100 200 300 400
Network scenarios (number of sensors)
Fig. 14. Amount of data packets received by the BS.
results obtained by authors in Karaboga et al. (2012). This is

probably favored by the use of the ABC optimization algorithm in
our clustering algorithm.
Even if in the design of sensor networks, it is necessary to save
sensor's energy as long as possible, keeping a good throughput is
also essential since the main objective in WSNs is to collect the
gathered data. Besides the energy consumption metrics, the
overall network performance is also measured by the amount of
packets delivered to the BS as well as the packets loss rate. Unlike
the much adopted evaluation of the amount of data packets re-
ceived by the BS, which considers the amount of aggregated data
packets sent by CHs to the BS, we computed that quantity by Fig. 15. Packets loss.
considering all the data received by each CH before the aggrega-
tion. This allowed us to know the exact amount of data generated
by the overall network. Then, always for the evaluation of the throughput, we execute
Diagrams in Fig. 14 present the amount of packets successfully considered protocols in order to evaluate the packet loss rate. The
means and their corresponding standard deviations of the packet
received by the BS from CHs in each network's scenario. Table 9
loss rate is given in Table 10. It is clear from Fig. 15 that, in all
shows the means and the standard deviations of the amount of
considered network scenarios, the packet loss rate for the ABC-SD
packets received by the BS of the 10 simulation runs. By observing
protocol is far lesser than in LEACH-C and LEACH protocols. These
the results obtained for ABC-SD and those of the compared pro-
protocols produce a high rate of data loss. This is owing to the
tocols, it can clearly be seen that the ABC-SD protocol produces a
adopted single hop communications.
greater amount of packets received by the BS. In addition, given
Besides, since the proposal includes a centralized clustering
the standard deviation values, the ABC-SD presents minimum
algorithm installed at the BS, we evaluated the impact of the
fluctuations in the mean while in PSO-C, LEACH-C and LEACH
communication overhead in the whole execution of the ABC-SD
protocols, there is a lot of fluctuations around the mean. Moreover,
protocol during the simulation. To achieve that, we computed the
as it is seen in the diagrams, the compared PSO based protocols,
cumulated amount of messages in each round, from the boot-
i.e., PSO-HC and PSO-C, also produce a good performance in this strapping and setup step till the establishment of route paths and
evaluation metric. However, results of this test show that the ABC- data transfer steps. Fig. 16 shows the evolution of the commu-
C protocol presents some difficulties to handle a growing amount nication overhead during each round in the four network scenar-
of sensors since the performance of the algorithm starts to de- ios. The obtained results show that the cumulated amount of
crease from 300 sensors. generated messages increases proportionally to the number of
sensors in each round. In addition, the adopted controlled flooding
Table 9 mechanism in the bootstrapping step contributed to contain the
Mean of throughput (μ¯ ( × 106)) and standard deviation (σ ( × 106)) .
blast of the generated messages. This implies that there is no
Protocol Network scenario
significant communication overhead in the ABC-SD.
Now, in order to evaluate the performance of the proposal in
#100 #200 #300 #400 terms of network coverage, we evaluated the number of un-
clustered sensors, i.e., the amount of inactive sensors, per round in
each network scenario. To achieve this, we suppose that a sensor is
ABC-SD 0.46 0.001 1.10 0.003 1.31 0.003 1.88 0.005 considered inactive if its energy level is not equal to zero and if it is
ABC-C 0.42 0.003 0.87 0.005 1.21 0.006 1.48 0.009 not a follower of a given CH. Diagrams in Fig. 17 show the com-
PSO-HC 0.41 0.002 0.84 0.002 1.26 0.003 1.70 0.007 parison of our proposal with the compared protocols in terms of
PSO-C 0.38 0.006 0.77 0.009 1.18 0.009 1.50 0.011 the average number of unclustered sensors per round. It can be
LEACH-C 0.40 0.009 0.80 0.017 1.20 0.023 1.64 0.096
LEACH 0.31 0.011 0.60 0.053 0.90 0.093 1.16 0.099
observed that the amount of unclustered sensors in ABC-SD is
significantly lesser than in its comparatives. This is allowed by the
× 106 180
2.5 ABC-SD
ABC-C
100 sensors 160 PSO-HC

200 sensors PSO-C
300 sensors LEACH-C
2 400 sensors 140
LEACH
Cumulated amount of messages
120
1.5
100
80
1
60
0.5 40
20
0
0 1 2 3 4 5 6 7 8 9 10 0
100 200 300 400
Rounds
Network scenarios (number of sensors) - 500*500
Fig. 16. The communication overhead in ABC-SD.
Fig. 18. Energy consumption in a sensing area of 500 × 500 m2 .
25
ABC-SD It can be observed from Fig. 18 that the ABC-SD enables good
ABC-C
results for the energy expenditure in each sensor than the com-
Average number of inactive sensors per round
PSO-HC
PSO-C
20 LEACH-C
pared protocol even if the sensing area becomes larger. Never-
LEACH theless, the standard deviations presented in Table 11 show that
the PSO-C protocol has a minimum dispersion. In addition, it is
15 important to note that the ABC-C and PSO-HC also outputted good
results when changing the sensing area. Fig. 19 reveals the effec-
tiveness of the ABC-SD in terms of amount of data packets re-
10 ceived by the BS with a minimum dispersion, in a sensing area of
500 × 500 m2. Although the ABC-SD enables a better throughput
than the compared, it can be found from Table 12 that the ABC-SD
5
enables higher dispersion in the results.
Finally, by returning to the design goals of the ABC-SD protocol
(see Section 5.1), the results obtained in the evaluation of the
0
100 200 300 400 network lifetime as well as the network coverage and the
Network scenarios (number of sensors) throughput, confirm that the ABC-SD protocol aims at maintaining
Fig. 17. Amount of unclustered sensors.
a good link quality, as well as providing a great number of deliv-
ered packets while preserving the sensor's power consumption as
best as possible.
adopted fitness function in the clustering algorithm which takes
care of energy consumption of sensors and the QoS of commu-
nication link within clusters. Moreover, it can be seen that the
ABC-C and PSO-HC protocols yield good results. This is respec- 7. Conclusion and future work
tively allowed by the positions update of the ABC algorithm in the
ABC-C and the adopted particle encoding scheme in the PSO-HC. The improvement of network performance remains an active
However, the results of the PSO-C protocol for this test are very issue of research in WSNs. In large-scale networks, it is demon-
poor. This is due to the used cost-based function for the intra- strated that, the optimal clustering mechanism has a strong in-
cluster communication, which does not allow far sensors to be fluence on the overall performance of the network. In this paper,
members of a cluster. Regarding the LEACH and LEACH-C protocols we investigated problems of clustering and routing in WSNs and
since their design's aim at balancing the load of CHs, sensors are then, we proposed a cluster-based routing protocol called ABC-SD.
assigned to CHs that are far away from them. This fact leads to a lot The clustering problem is formulated as a Linear Programming
of death of CHs and this considerably increases the amount of
unclustered sensors. Table 11
In the above presented results, we have used the 100 × 100 m2 Average sensor's energy consumption (μ¯) and standard deviation (σ ) – sensing area
of 500 × 500 m2.
sensing area varying the number of sensors in the performance
evaluation. However, in order to confirm the effectiveness of the Protocol Network scenario
ABC-SD, 10 simulation runs of the four network scenarios in an
area of 500 × 500 m2 with the BS positioned at the coordinate #100 #200 #300 #400
(0; 0) of the field have been used in order to evaluate the potential
impact of changing the sensing area on the average energy con-
sumed by each sensor and the throughput. Figs. 18 and 19 re- ABC-SD 74.81 1.03 59.98 1.63 61.82 1.01 52.72 1.03
spectively show the results of the average energy consumed by ABC-C 79.11 1.01 64.23 1.03 71.01 0.95 76.10 0.98
each sensor and the results obtained in the evaluation of the PSO-HC 81.41 2.12 71.44 2.14 76.43 1.69 74.96 1.53
throughput. In addition, in each network scenario, the average PSO-C 87.83 0.29 82.11 0.41 85.12 0.63 86.40 0.62
LEACH-C 99.03 1.01 98.93 1.04 97.03 0.98 96.33 0.30
energy expended by each sensor and the standard deviations is LEACH 169.01 3.54 178.41 2.97 165.32 1.97 164.09 2.19
given in Tables 11 and 12.
× 10 Furthermore, we would also focus on the design of a TDMA frame

2
in the case of variable packet length.
ABC-SD
1.8 ABC-C
PSO-HC
PSO-C
1.6 LEACH-C
LEACH Acknowledgement
1.4
1.2 This work was supported by the 185CMRB150029 project of the

Throughput
French Ministry of Foreign Affairs and International Development

1
under contract no. 847397H. We like to thank the editor and the
0.8 anonymous reviewers for their valuable remarks that helped us in
better improving the content and presentation of the paper.
0.6
0.4
0.2
References
0
100 200 300 400
Ari, A.A.A., Gueroui, A., Labraoui, N., Yenke, B.O., 2015. Concepts and evolution of
research in the field of wireless sensor networks. Int. J. Comput. Netw. Com-
Network scenarios (number of sensors) - 500*500 mun. 7 (1), 81–98.
Ari, A.A.A., Yenke, B.O., Labraoui, N., Gueroui, A., 2016. Energy efficient clustering
Fig. 19. Amount of data packets received by the BS in a sensing area of algorithm for wireless sensor networks using the ABC metaheuristic. In: 2016
500 × 500 m2 . International Conference on Computer Communication and Informatics (ICCCI).
IEEE, Coimbatore, India, pp. 1–6.
Avril, F., Bernard, T., Bui, A., Sohier, D., 2014. Clustering and communications
Table 12 scheduling in WSNs using mixed integer linear programming. J. Commun.
Mean of throughput (μ¯ ( × 106)) and standard deviation (σ ( × 106)) – sensing area of Netw. 16 (4), 421–429.
Barberis, A., Barboni, L., Valle, M., 2007. Evaluating energy consumption in wireless
500 × 500 m2 .
sensor networks applications. In: 2007 10th Euromicro Conference on Digital
System Design Architectures, Methods and Tools, DSD 2007. IEEE, Lübeck,
Protocol Network scenario Germany, pp. 455–462.
Cai, X., Duan, Y., He, Y., Yang, J., Li, C., 2015. Bee-Sensor-C: an energy-efficient and
#100 #200 #300 #400 scalable multipath routing protocol for wireless sensor networks. Int. J. Distrib.
Sens. Netw. (976127), 0–14.
μ̄ s μ̄ s μ̄ s μ̄ s Dorigo, M., Birattari, M., Stützle, T., 2006. Ant colony optimization. IEEE Comput.
Intell. Mag. 1 (4), 28–39.
ABC-SD 0.42 0.024 1.09 0.014 1.29 0.099 1.83 0.101 Elhabyan, R.S., Yagoub, M.C., 2014. PSO-HC: particle swarm optimization protocol
ABC-C 0.41 0.004 0.83 0.005 1.10 0.008 1.37 0.009 for hierarchical clustering in wireless sensor networks. In: 2014 International
PSO-HC 0.39 0.005 0.80 0.008 1.21 0.004 1.60 0.006 Conference on Collaborative Computing: Networking, Applications and Work-
PSO-C 0.31 0.008 0.74 0.010 1.14 0.010 1.46 0.019 sharing (CollaborateCom). IEEE, Miami, Florida, USA, pp. 417–424.
LEACH-C 0.38 0.012 0.79 0.014 1.17 0.029 1.59 0.101 Fathian, M., Amiri, B., Maroosi, A., 2007. Application of honey-bee mating optimi-
zation algorithm on clustering. Appl. Math. Comput. 190 (2), 1502–1513.
LEACH 0.27 0.016 0.59 0.061 0.79 0.125 1.01 0.163
Hammoudeh, M., Newman, R., 2015. Adaptive routing in wireless sensor networks:
QoS optimisation for enhanced application performance. Inf. Fusion 22, 3–15.
Heidarian, F., Schmaltz, J., Vaandrager, F., 2012. Analysis of a clock synchronization
protocol for wireless sensor networks. Theor. Comput. Sci. 413 (1), 87–105.
problem and the routing problem is solved with a cost-based
Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H., 2000. Energy-efficient
function. We opted for a centralized clustering optimization car- communication protocol for wireless microsensor networks. In: 2000 Pro-
ried out in the BS, which has a rich resource suitable for it. Clusters ceedings of the 33rd Annual Hawaii International Conference on System Sci-
are built in an energy efficient way by exploiting the efficient ences. IEEE, Maui, Hawaii, USA, pp. 10–20.
Heinzelman, W.B., Chandrakasan, A.P., Balakrishnan, H., 2002. An application-spe-
features and the fast convergence characteristics of the Artificial cific protocol architecture for wireless microsensor networks. IEEE Trans. Wirel.
Bee Colony metaheuristic. As for the routing problem, it is brought Commun. 1 (4), 660–670.
back to a problem of choosing a low-cost path among existing Johnson, N.L., Kemp, A.W., Kotz, S., 2005. Univariate Discrete Distributions vol. 444.
John Wiley & Sons, Inc., Hoboken, New Jersey.
paths from a source to a destination, for the intra-cluster com- Kabara, J., Calle, M., 2012. MAC protocols used by wireless sensor networks and a
munication. The choice of CHs in the clustering algorithm also general method of performance evaluation, Int. J. Distrib. Sens. Netw, http://dx.
helps us in the construction of routes for the inter-cluster com- doi.org/10.1155/2012/834784.
Karaboga, D., Okdem, S., Ozturk, C., 2012. Cluster based wireless sensor network
munication. Contrary to the existing protocols, the major con-
routing using artificial bee colony algorithm. Wirel. Netw. 18 (7), 847–860.
tributions of our proposal are illustrated as follows. Firstly, in order Karaboga, D., 2010. Artificial bee colony algorithm, Scholarpedia 5 (3), 6915.
to be closer to the real sensing environment and existing sensor's Kennedy, J., 2010. Particle swarm optimization. In: Encyclopedia of Machine
Learning. Springer, USA, pp. 760–766.
hardware, a realistic energy consumption model is used. Secondly,
Kuila, P., Jana, P.K., 2014. Energy efficient clustering and routing algorithms for
it defines a new cluster balancing mechanism that makes a trade- wireless sensor networks: particle swarm optimization approach. Eng. Appl.
off between sensor's energy level and the quality of the commu- Artif. Intell. 33, 127–140.
nication link. Thirdly, we designed a pre-established routes ap- Labraoui, N., Gueroui, M., Aliouat, M., Petit, J., 2013. Reactive and adaptive mon-
itoring to secure aggregation in wireless sensor networks. Telecommun. Syst.
proach in which the chosen routing path is less-costly in terms of 54 (1), 3–17.
power consumption and employs a least number of hops. Fourthly, Latiff, N.M.A., Tsimenidis, C.C., Sharif, B.S., 2007. Energy-aware clustering for
unlike the most existing methods, which focuses on one metric, wireless sensor networks using particle swarm optimization. In: 2007 IEEE
18th International Symposium on Personal, Indoor and Mobile Radio Com-
the ABC-SD protocol performs well in the above evaluation me- munications, PIMRC 2007. IEEE, Athens, Greece, pp. 1–5.
trics. Extensive simulations were made with a number of network Li, J., Zhou, H., Zuo, D.-C., Hou, K.M., Xie, H., Zhou, P., 2014. Energy consumption
topologies in different network sizes and the obtained results evaluation for wireless sensor network nodes based on queuing petri net, Int. J.
Distrib. Sens. Netw, http://dx.doi.org/10.1155/2014/262848.
show that, the proposed protocol delivers better performance than
Liu, X., 2012. A survey on clustering routing protocols in wireless sensor networks.
its comparatives in terms of the network lifetime, the network Sensors 12 (8), 11113–11153.
coverage and the amount of packets received by the BS. We expect Malesci, U., Madden, S., 2006. A measurement-based analysis of the interaction
several research contributions to be conducted from the reported between network layers in tinyOS. In: Wireless Sensor Networks. Springer,
Zurich, Switzerland, pp. 292–309.
results. As a future work, we plan to study the effects of mobile Moussaoui, O., Ksentini, A., Naimi, M., Gueroui, M., 2006. A novel clustering algo-
sensors as well as mobile BS in the proposed algorithm. rithm for efficient energy saving in wireless sensor networks. In: 2006
International Symposium on Computer Networks. IEEE, Istanbul, Turkey, pp. coccineus (Fabaceae) flowers at Ngaoundere (Cameroon). Int. J. Trop. Insect Sci.
66–72. 34 (02), 127–137.
Nanda, S.J., Panda, G., 2014. A survey on nature inspired metaheuristic algorithms Texas Instruments, 2014. Chipcon as smartrf® CC2420 Preliminary Datasheet (rev
for partitional clustering. Swarm Evolut. Comput. 16, 1–18. 1.2), 2004-06-09. Technical Report, 〈http://www.ti.com/lit/ds/symlink/cc2420.
Polastre, J., Hill, J., Culler, D., 2004. Versatile low power media access for wireless pdf〉 (accessed 27.06.15).
sensor networks. In: Proceedings of the 2nd International Conference on Em- Titouna, C., Aliouat, M., Gueroui, M., 2016. FDS: fault detection scheme for wireless
bedded Networked Sensor Systems. ACM, Baltimore, Maryland, USA, pp. 95– sensor networks. Wirel. Pers. Commun. 86 (2), 549–562.
107. Winston, M.L., 1991. The Biology of The Honey Bee. Harvard University Press, USA.
Saleem, M., Di Caro, G.A., Farooq, M., 2011. Swarm intelligence based routing pro- Yang, J., Xu, M., Zhao, W., Xu, B., 2010. A multipath routing protocol based on
tocol for wireless sensor networks: survey and future directions. Inf. Sci. 181 clustering and ant colony optimization for wireless sensor networks. Sensors 10
(20), 4597–4624. (5), 4521–4540.
Singh, B., Lobiyal, D.K., 2012. A novel energy-aware cluster head selection based on Zungeru, A.M., Ang, L.-M., Seng, K.P., 2012. Classical and swarm intelligence based
particle swarm optimization for wireless sensor networks. Hum.-Centric
routing protocols for wireless sensor networks: a survey and comparison. J.
Comput. Inf. Sci. 2 (1), 1–18.
Netw. Comput. Appl. 35 (5), 1508–1536.
Srinivasan, K., Dutta, P., Tavakoli, A., Levis, P., 2010. An empirical study of low-power
Zungeru, A.M., Ang, L.-M., Seng, K.P., 2012. Termite-hill: performance optimized
wireless. ACM Trans. Sens. Netw. (TOSN) 6 (2), 16.
swarm intelligence based routing algorithm for wireless sensor networks. J.
Tchuenguem Fohouo, F.-N., Fameni Tope, S., Brückner, D., 2014. Foraging and pol-
lination behaviour of Xylocopa olivacea (Hymenoptera: Apidae) on Phaseolus Netw. Comput. Appl. 35 (6), 1901–1917.

9 - Ari

Uploaded by

Copyright:

Available Formats

9 - Ari

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

9 - Ari

Uploaded by

Copyright:

Available Formats

Journal of Network and Computer Applications 69 (2016) 77–97

Contents lists available at ScienceDirect

Journal of Network and Computer Applications

A power efﬁcient cluster-based routing algorithm for wireless sensor

1. Introduction phenomena, on a remote or inaccessible environment (Zungeru

Protocol Energy model Link quality based Location Clustering

The ith food source position is represented by the vector Where:

The considered expressions are given below:

The identiﬁer of the BS is 0 and each sensor node has a unique

assignment of followers of each CH in ℶ(ch). So, the initial popu-

corresponding CH, again by using a controlled ﬂooding mechan-

5.2.3. Network scheduling: energy saving method

protocol, which is a complex and powerful MAC protocol designed

Fig. 6. Route discovery.

Fig. 7. Steady-state: a sequence of actions in data transfer and acknowledgement mechanism.

Illustration 4. To illustrate the data transmission step, i.e., the

Since data packets are exclusively sent towards the discovered

By taking that into account, the expended energy Eboot (sj ) by a

Eboot (sj ) = Ei × (1 + ß) (23)

N consumption Edata − t in a best situation for data packets transfer for

m m 6.1.2. Packets retransmission derivation

m 6.3. Simulation and discussion

Table 7 200 ABC-SD

Average energy consumed by each sensor (J)

Fig. 11. Energy consumption.

In each network scenario, we proceeded to 10 runs of these

Protocol Network scenario

#100 #200 #300 #400

ABC-SD 70.21 1.10 57.03 1.83 59.05 1.06 51.02 0.93

Fig. 12. Energy efﬁciency.

1600 important to note that, results obtained in PSO-HC, PSO-C and

ABC-SD 0.119 0.001 0.111 0.002 0.109 0.003 0.105 0.004

Network scenarios (number of sensors)

Fig. 14. Amount of data packets received by the BS.

results obtained by authors in Karaboga et al. (2012). This is

Average energy consumed by each sensor (J)

× 10 Furthermore, we would also focus on the design of a TDMA frame

1.2 This work was supported by the 185CMRB150029 project of the

French Ministry of Foreign Affairs and International Development

You might also like