An Energy-Efficient Protocol Using an Objective Function &Random Search with Jumps for WSN

Mohammed Kaddi ,Khelifa Benahmed and Mohammed Omari

Abstract:Wireless Sensor Networks (WSNs) have hardware and software limitations and are deployed in hostile environments.The problem of energy consumption in WSNs has become a very important axis of research.To obtain good performance in terms of the network lifetime,several routing protocols have been proposed in the literature.Hierarchical routing is considered to be the most favorable approach in terms of energy efficiency.It is based on the concept parent-child hierarchy where the child nodes forward their messages to their parent,and then the parent node forwards them,directly or via other parent nodes,to the base station (sink).In this paper,we present a new Energy-Efficient clustering protocol for WSNs using an Objective Function and Random Search with Jumps(EEOFRSJ) in order to reduce sensor energy consumption.First,the objective function is used to find an optimal cluster formation taking into account the ratio of the mean Euclidean distance of the nodes to their associated cluster heads (CH) and their residual energy.Then,we find the best path to transmit data from the CHs nodes to the base station(BS) using a random search with jumps.We simulated our proposed approach compared with the Energy-Efficient in WSNs using Fuzzy C-Means clustering (EEFCM) protocol using Matlab Simulink.Simulation results have shown that our proposed protocol excels regarding energy consumption,resulting in network lifetime extension.

Keywords:WSNs,clustering,energy Consumption,lifetime extension,random search with jumps,EEOFRSJ,EEFCM.

1 Introduction

The sensor networks are becoming more and more widespread.They are used in various fields.Their applications are more and more numerous and diversified.They can be classified mainly in military applications,environmental applications,medical and commercial applications [Akyildiz,Su,Sankarasubramaniam et al.(2002a)].

The WSN consists of hundreds and thousands of sensor nodes,which are randomly deployed in the sensor field and form a self-organized network system by radio communications.The sensor nodes have the ability to monitor physical or environmental conditions,such as temperature,sound and pressure.The sensor nodes detect,collect,andtransmit information from the region that is covered by the entire sensor array,and transmit it to each other or directly to the user [Akyildiz,Su,Sankarasubramaniam et al.(2002b)].

These sensor nodes consist of a sensing subsystem,a processing subsystem,a communication subsystem,and a power subsystem.Depending on the specificity of the application,the sensor nodes may also include additional components such as a location search system to determine their location (e.g.,GPS),a mobilizer to change their location or configuration (for example,the orientation of the antenna),and characterized by:low cost,low power,small size and short communication distance.WSNs are also characterized by the constraint of energy because data transmission is frequent and energy can be consumed quickly [Giuseppe,Marco,Mario et al.(2009)].This makes the data routing very special to reduce power consumption and extend the lifetime of WSNs.The general architecture and the major components of a wireless sensor node are shown in Fig.1.

Figure1:Sensor node structure

In WSNs,it is necessary to ensure distributed energy consumption within the network.This energy is consumed by various network features such as radio (communication),protocols (medium access control (MAC),routing),central processing unit (computation,aggregation) and acquisition.Therefore,the lifetime of the entire sensor array depends essentially on the lifetime of the individual node’s battery.For a sensor node,the energy consumed by communication tasks using radio transmissions is the dominant factor.

Many new algorithms have been proposed for the problem of data routing in sensor networks.These routing mechanisms have considered the characteristics of the sensor nodes with the requirements of the application and the architecture.All routing protocols can be classified into three categories as shown in Fig.2:data-centric,hierarchical,and location-based.Data-centric protocols are query-based and depend on the naming of the desired data,which helps eliminate the many redundant transmissions.Hierarchical protocols aim at grouping the nodes so that the CHs can do some aggregation and data reduction to save energy.Location-based protocols use position information to transmit data to the desired regions,rather than the entire network.

Figure2:Categories of WSNs routing protocols

In data-centric routing,the BS sends requests to certain regions and waits for data from the sensors in the selected regions.Since the data is requested by the queries,an attribute-based naming is needed to specify the properties of the data.SPIN (Sensor Protocols for Information via Negotiation) is the first data-centric protocol that considers data negotiation between nodes to eliminate redundant data and save energy.Later,the DD (Directed Diffusion) protocol was developed and became progress in the routing of centric data.Then,many other protocols have been proposed on the basis of a similar concept such as Flooding and Gossiping,EAR (Energy-Aware Routing) and RR (Rumor Routing).

The primary purpose of hierarchical routing is to effectively maintain the power consumption of sensor nodes by involving them in multi-hop communication in a particular cluster and by aggregating and merging data to reduce the number of messages sent to the sink.Cluster formation is usually based on the energy reserve of sensors and the proximity of the sensor to the CH.LEACH [Heinzelman,Chandrakasan and Balakrishnan (2002)] is one of the first hierarchical routing approaches for sensor networks.The idea proposed in LEACH has been a source of inspiration for many hierarchical routing protocols [Arati and Dharma (2001); Arati and Dharma (2002)],although some protocols have been developed independently [Lakshminarayanan and Randy (2000); Younis,Youssef and Arisha (2002)].So,this category includes also:PEGASIS-E [Vibha and Ajay (2013)],TEEN and APTEEN [Arati and Dharma (2001)],Energy-aware routing for cluster-based sensor networks [Younis,Youssef and Arisha(2002)],Self-organizing protocol [Lakshminarayanan and Randy (2000)].

Most routing protocols for sensor networks require location information for the sensor nodes.In most cases,location information is needed to calculate the distance between two particular nodes so that energy consumption can be estimated.Since there is no addressing scheme for sensor networks as Internet Protocol address (IP address) and nodes are spatially deployed in a region,location information can be used to route the data in an energy efficient manner.For example,if the region to be detected is known using the location of the sensors,the request can be broadcast only to that particular region which will eliminate the number of transmissions significantly.Some of the protocols cited here are designed primarily for ad hoc mobile networks and consider node mobility in design.However,they are equally applicable to sensor networks where there is little or no mobility.Note that there are other location protocols designed for ad hoc wireless networks,such as cartesian routing and path-based routing.However,many of these protocols are not applicable to sensor networks because they do not consider energy.In this group,there are some of the routing protocols such as MECN (Minimum Energy Communication Network),SMECN (Small Minimum Energy Communication Network),GAF (Geographic Adaptive Fidelity) and GEAR (Geographic and Energy Aware Routing).

In this paper,in order to extend a WSNs lifetime,we choose the hierarchical type as a routing protocol to send the collected data from the monitored zone to the BS.We present in this work a novel energy efficient clustering scheme which uses an objective function to form the clusters,and random search with jumps to determine an optimal path to send the aggregated data from the CHs nodes to the BS in a multi-hop mode.

The rest of this paper is organized as follows.In section two,the state-of-the-art techniques are shortly discussed.The local search and random search techniques are presented in the third section.Section four explains our proposed protocol (EEOFRSJ)which is based on multi-hop clustering using a random search with jumps.In section five,we present a performance evaluation of the proposed protocol via simulations and comparison with a peer protocol.Finally,Section six concludes the paper with some proposed future works.

2 Related work

In the hierarchical structure,there are two main categories:cluster-based approach and chain-based approach.In the first,the nodes are organized in clusters,where each cluster has his leader to collect data and transmit it to the BS.In the second type,the node is organized in a chain.

In the literature,there are several protocols and energy-efficient hierarchical routing algorithms for WSNs have been proposed to save energy and therefore extend the network lifetime.In the following paragraphs we present LEACH protocol and its variants,and then we explain the basic functions of ten protocols related to our work.

2.1 Leach and its variants

Low-Energy Adaptive Clustering Hierarchy (LEACH) [Heinzelman,Chandrakasan and Balakrishnan (2002)] is one of the most popular distributed cluster-based routing protocols.The idea of LEACH consists in forming a cluster of sensor nodes based on the amplitude of the received signal and using the CHs elected as routers.

The process of cluster formation in LEACH is illustrated in Fig.3.

Figure3:Cluster formation in LEACH

Execution process of LEACH based upon setup phase and data transmission phase; the duration of the second phase is longer than that of the first phase in order to minimize the overhead.In the first phase,the CH is randomly selected by generating a number (for each node n) that belongs to the interval [0-1].If the random number is less than the threshold value obtained by T(n) function,the node n becomes the CH in this round.Otherwise,the node joins the closest cluster.

Where p is the CH probability,G is the set of nodes that have not been chosen as CH before (1/p) rounds and r is the current round number.

Based on division multiple access (TDMA) schedule,the sensor nodes transmit their data to the CHs during their respective slots in the data transmission phase.These CHs collect data from all cluster members; fuse and aggregate gathered data using merge procedures,and transmit this data directly to the BS.Data collection is periodically sent to a central sink.In the LEACH protocol variants,we find that some protocols use the centralized approach while others use the decentralized approach for cluster formation.In the first types,the CHs nodes are chosen by the BS.Therefore,each node sends its characteristics such as its location and energy level to the BS.The global positioning system (GPS) or other tracking methods produce better clustering and require less transmission energy.The BS will select only the nodes that will become CH nodes with required characteristics and broadcast this information to all nodes in the network.LEACH-C protocol [Dhawan and Waraich (2014); Gnanambigai,Rengarajan and Anbukkarasi(2014)] and LEACH-F protocol [Dhawan and Waraich (2014); Manimala and Senthamil selvi (2013)] are examples of this type.When the BS cannot track nodes (no GPS),each sensor sends its own characteristics such as its position and to the final destination regardless of the position of the rest of the nodes in the network.As an example of this type,there is LEACH-B [Braman and Umapathi (2014); Usha and Sankarram (2014)]protocol and LEACH-A protocol [Zhao and Yang (2014)].

Unlike the LEACH protocol where CH sends data to the BS directly in a single hop; there are other LEACH protocol versions that use a multi-level hierarchy instead of being sent directly to the BS.

The TL-LEACH protocol [Kaur,Sharma and Kaur (2013)] operates in a two-level hierarchy.The aggregated data of each CH is collected by a CH nearer to the BS.The improvement of this protocol reduces the data transmission energy.Cluster nodes die early relative to other nodes,far from the BS,and TL-LEACH improves energy efficiency by using a CH node as a relay.

In MH-LEACH protocol [Gnanambigai,Rengarajan and Anbukkarasi (2014); Kaur,Sharma and Kaur (2013)],the cluster member nodes send data to their respective CH nodes,which then transfer data to the CH rather than the BS directly.This protocol adopts an optimal path between the CH and the BS.

Table1:Comparison between LEACH protocol variants

2.2 Others hierarchical routing protocol

PEGASIS-E (Power Efficient Gathering in Sensor Information System Extended) [Vibha and Ajay (2013)] is a chain-based protocol is an extension of PEGASIS.The basic idea of this protocol is that the nodes will be organized in a chain.So,that the nodes transmit and communicate only with their nearest neighbors.The only node that sends data from the chain directly to the BS is the leader.The chain formation criterion in PEGASIS-E is based on the average distance between the sensor nodes.PEGASIS-E protocol offers better performance in terms of energy dissipation and the amount of information sent to BS compared with classical PEGASIS.

Hadjila [Hadjila (2014)] proposes various solutions for the routing of the data in a WSN.First,he presents three routing algorithms based on the clustering with different approaches for the choice of the CHs and the transmission of the data towards the BS.Then,he is interested in another approach based on the chains.The choice of CHs is an important point in the design of routing protocols; he uses an original approach based on fuzzy logic to solve this problem.Finally,he combines cluster-based and chain-based approaches with metaheuristic “ant colony” to build shorter chains in clusters and thus reduce distances in order to save energy in transmissions.

In order to minimize energy consumption,Elkhediri et al.[Elkhediri,Nasria,Weic et al.(2014)] propose a method for optimizing the low energy adaptive hierarchy (O-LEACH)in order to improve the LEACH and LEACH-C protocols.The purpose of this method is to dynamically select the cluster based on the residual energy of the sensor nodes.In the proposed O-LEACH Algorithm the BS initiates the routing process for which the CH election in each round is based on the energy value of each sensor that must be greater than ten percent of its residual energy value.After selecting CH,the latter waits for the member nodes,creates the TDMA table and sends it to its members.Then the transmission phase will take place and if the energy is less than ten percent of its value,the process of LEACH will be launched.The results of the simulation show that the proposed algorithm provides greater stability compared to LEACH and LEACH-C.

To study the impact of the heterogeneity of the nodes in terms of energy in hierarchically grouped WSNs,Kumar et al.[Kumar,Aseri and Patel (2009)] introduce an energyefficient heterogeneous clustered scheme for WSNs (EEHC) based on the weighted election probabilities of each node to become a CH based on the residual energy in each node.Kumar et al.[Kumar,Aseri and Patel (2009)] assume that a percentage of the sensor node population is equipped with additional energy resources.The optimal probability that a node will be elected as a CH is a function of spatial density when the nodes are uniformly distributed over the sensor field.This grouping is optimal in the sense that the energy consumption is well distributed on all the sensors and that the total consumption of energy is minimal.This optimal grouping depends strongly on the energy model used.The results of the simulation show that this approach is more effective in extending network life compared to LEACH.

Nawaz et al.[Nawaz and Bazaz (2010)] present a protocol for routing and aggregating data from WSNs.The proposed technique combines a gradient-based routing scheme with the hierarchical scheme of the LEACH protocol.With hybridization between these two protocols and taking into account the residual energy factor of the nodes when selecting the CHs a robust data aggregation and routing strategy is developed.The simulation results show that energy-efficient clustering and low-cost multi-hop communication increase the network’s lifetime over the LEACH routing protocol.

The objective of the research presented in Omar et al.[Omar,Burairah and AbdSamad(2017)] is to improve the LEACH protocol by proposing a new method for selecting CHs.This method is based on the center of gravity and the center of mass,taking into account the three dimensions of node energy,distance,and density.This would reliably improve WSN network performance by reducing power dissipation and extending network life.Data is transferred from CH to BS using the concept that considers two-hop transmission where all CHs first collect data from surrounding sensors and then send them to the BS.The results confirmed that the proposed improvement allows for the correct selection of CHs in high-density areas.

A cluster-based,energy-centric protocol was developed in Sarma et al.[Sarma and Gopi(2014)] to extend the life of the sensor network using the jumper firefly algorithm.The cluster configuration is performed using the firefly algorithm whose protocol is a centralized algorithm in which all clustering procedures will be performed at the BS.The latter runs the firefly algorithm to determine the best CHs that can minimize the cost function.A new cost function has been defined to minimize the intra-cluster distance in order to optimize the energy consumption of the network.It uses a high-energy node as a CH and produces clusters that are positioned evenly throughout the sensor’s field.The main idea of the proposed protocol is the selection of the intra-cluster distance between itself and the cluster member and the optimization of the energy management of the network.The BS has identified the optimal set of cluster leaders and their associated cluster members.The BS transmits information containing the CH Id (Identity) for each node to all nodes in the network.

In Oudani et al.[Oudani,Krit,Kabrane et al.(2017)],the focus is primarily on energy efficiency using the cluster-based hierarchical approach to propose a new method for maximizing network sensor lifetime.The proposed method is to conserve energy consumption when transmitting data to the BS based on improving the LEACH algorithm protocol,just to minimize the distance between BS and CH and to minimize the number of dead headshots relative to BS.This method consists of locating the selected CHs of the nodes that are far from BS at half the topology of the network; the goal of this work is to avoid the death of nodes which are very far from the BS and to give the node located at the half of the topology and the BS so that become CHs.the results are demonstrated by the simulation results,using Matlab Simulink,which show that this approach guarantees low power consumption and improves network lifetime by up to 45% compared to the LEACH protocol.

Hadjila et al.[Hadjila,Guyennet and Feham (2013)] propose an algorithm named EEFCM (Energy-Efficient in WSNs using Fuzzy C-Means Clustering),where the cluster formation mode works in three steps.In the first step,the clusters are formed using the Fuzzy C-Means method.Each cluster containing a set of nodes and the number of nodes is not necessarily equal in the clusters.In the second step,the CH is initially elected in each group in a random way because all the nodes have the same amount of initial energy;the election is performed after a rotation mechanism based on the remaining energy applied to select the next CH.Ordinary nodes send their collected data to the corresponding cluster leader.In the third step,the CHs receive and aggregate the data in order to send it to the BS.The data transmission between the CHs and the BS is performed in multi-hop mode.Calculation of the distances between the CHs and distances between the CHs and the BS allows building several chains,where each CH sends its collected data to the nearest CH.The nearest CH of the BS sends its data as well as data of other CHs directly to the BS.

In order to reduce energy consumption for WSN,authors in Wang et al.[Wang,Ju,Gao et al.(2018)] have proposed a new coverage control algorithm based on the particle swarms optimization (PSO).In order to achieve a balance between the coverage rate and the energy cost,the detection radius of each node must be adjusted.In the first phase,they randomly deployed the nodes in the area.Then,they partitioned the network into several grids.Afterward,they calculated the energy consumption and the coverage rate of each grid.In order to adjust the detection radius of the nodes in different networks,they adopted a PSO technique in the last phase.The results of the simulation show that the proposed algorithm can effectively improve the coverage rate and reduce the energy consumption compared with the other PSO variants presented in the literature.

In Tab.2,a comparison of these routing protocols was made based on various clustering parameters.

Table2:Comparison between nine routing protocols based on clustering parameters

3 Local search and random search

There are two types of metaheuristics:local searches,also known as single-solution methods,and population-based methods.Local research tends to intensify research by exploiting some of the research space while population-based methods tend to diversify it by exploring different parts of the research space.

The search space associated with a combinatorial optimization problem is often nonenumerable in a reasonable amount of time.In fact,we try to link some solutions together,so that one solution can be obtained from another.It is necessary to define a relation of a neighborhood which is an application that associates with any solution (of the search space) a set of solutions called neighbors.

Local searches are methods based on a neighborhood relationship and a procedure exploiting that neighborhood.The local searches are differentiated by the procedure of exploitation of the neighborhood; the neighborhood being able to be regarded as a parameter of this method.Local search is the oldest method of resolution.It starts with an initial solution,and,at each iteration,it replaces the current solution with the version that optimizes the objective function.The search ends when all the candidate neighbors are not optimal with respect to the current solution,so the local optimum is reached.

Algorithm 1:Pseudo code of a local search S ← S0; {generate an initial solution S0} While (stopping condition is not satisfied) do Generate N (s); {neighborhood generation} If no better neighbors then S ← S '; {selection of the best neighbor S' belongs to N (s) } endif; end while;

Random search is the simplest stochastic method.This method consists in drawing at each iteration a random solution.The objective functionfis evaluated at this point.The new value is compared to the previous one.If it is better than the previous one,this value is saved,along with the corresponding solution,and the process continues.Otherwise,we start from the previous point and start the process,until the stopping conditions are reached.

4 Our contribution

In cluster-based hierarchical routing algorithms,data transmission takes place in two phases:the transmission of data from ordinary nodes to CHs,then from CHs to the BS.The main challenges of energy-efficient cluster-based hierarchical routing protocols are the choice of CHs and the method of route data to BS.

With regard to the first challenge,most of the hierarchical protocols described in the previous section are based on the principle of LEACH protocol or based on one factor in order to determine the different clusters.In the LEACH protocol and in some of its variants,the CHs are not uniformly distributed in the sensing area,which means that the CHs can be at the edges of the cluster.Consequently,some nodes will have no CH in their neighborhoods.Also,the protocols proposed in Elkhediri et al.[Elkhediri,Nasria,Weic et al.(2014)],Kumar et al.[Kumar,Aseri and Patel (2009)] and Nawaz et al.[Nawaz and Bazaz (2010)] take the residual energy of the nodes like a factor of clustering,and the authors in Sarma et al.[Sarma and Gopi (2014)] and Oudani et al.[Oudani,Krit,Kabrane et al.(2017)] choose the distance between nodes as the factor to determine the CHs.

In order to determine the best CHs,we choose the residual energy of nodes and their distances to the elected CH as factors of the objective function.

Regarding the second challenge,some of the above-discussed protocols only address the single-hop routing of CHs to the BS.Indeed,they assume that cluster leaders can communicate directly with the BS.This becomes impossible when the extent of the network increases and this will cause a strong energy dissipation of the CH node if the BS is far from it.

In our proposed protocol,we adopt a hierarchical approach with multi-hop routing as to remedy this problem such as that used by Nawaz et al.[Nawaz and Bazaz (2010)] and Omar et al.[Omar,Burairah and AbdSamad (2017)],but by using a new technique.

4.1 Network model

In this paper,we use the same sensor network model as used by Heinzelman et al.[Heinzelman,Chandrakasan and Balakrishnan (2002)].In our model,the nodes are uniformly distributed in N*M surveillance zone.

During the deployment of the nodes,we took into account the following criteria:

? The sink node and all other nodes are stationary.The location of the nodes has to be known either through GPS or an automatic position detection mechanism.

? The nodes are all homogeneous,and they have the same initial energy E0,sensing rangeRsand radio communication rangeRc.

? Each node can have different roles:monitoring nodes,relay nodes,and CHs.

? The BS is not limited in terms of energy,memory and computing power.

? The links are symmetrical so that the energy necessary to transmit a message from nodeito nodejis the same as from nodejto nodei.

? Data fusion is used to reduce the total sent data.

4.2 Energy consumption model

In our proposed protocol,we use the same simple model shown in Heinzelman et al.[Heinzelman,Chandrakasan and Balakrishnan (2002)] for the radio hardware energy consumption where the transmitter dissipates energy to run the radio electronics and the power amplifier,and the receiver dissipates energy to run the radio electronics.Both the free-space channel (energy dissipation ofd2) and the multi-path channel (energy dissipation ofd4) are used according to the distance (d) between the transmitter and the receiver.Thus,the energy consumption for the transmission of a packet ofLbits at a distanced (ETX(L,d))is given by the following equation:

To receive a message ofLbits,the receiver consumesERX(L):

WhereEelec(L,d)is sufficient energy to transmit or receive a 1 bit,εfsis the amplifier parameter of transmission corresponding to the free-space,εmpis the amplifier parameter of transmission corresponding to the two-ray models,andd0is the threshold transmission distance which is given by:

Figure4:Energy model used

4.3 The proposed technique

Our proposed protocol consists of three phases.The first phase is the cluster creation phase.In this stage,the clusters will be formed through the use of an objective function called “Cost”.The second phase is the inter-cluster communication phase.In this stage,we determine the optimal mode of communication between the CHs by using a random search with jumps.The third phase is the data transmission phase:both intra-cluster and inter-cluster data transmission are launched.

Cluster creation phase:

? CHs election;

? Clusters and CHs (CHi) are fixed;

? Scheduling transmission plan of each ordinary node by CH.

Since our proposed protocol is a centralized algorithm in which all clustering operations will be performed at the BS,we assume that the BS has all the information about the energy levels and the location of all network nodes.In this phase,the BS chooses randomly 10% (like exist in Hadjila et al.[Hadjila,Guyennet and Feham (2013)]) of nodes having an energy level greater than or equal to the average residual energy (ARE)of the entire network as candidate node (Eq.(5)).

WhereE(ni)is the current residual energy of the living node i andMis the total live nodes.

The BS runs and calculates the various parameters defined below to determine the bestkCHs from candidate nodes of the current cycle for an optimal condition (We chosek=5%like Heinzelman et al.[Heinzelman,Chandrakasan and Balakrishnan (2002)]).Then the ordinary nodes join the nearest CH to form the clusters.Therefore,an objective function called “Cost” is used to select the best CHs (Eq.(9)).The smallest value of the cost function represents the best combination of CHs among others:

The Euclidean distance is used to calculate the distance between CH and the cluster member node:

Wherexi and yi (respectively xjand yi) are the coordinates of member nodei(respectiveley CHj).

The functionf1is used to maximize the ratio of the mean Euclidean distance of the nodes to their associated CH.

Where d(ni,CHk) is the Euclidean distance between the node i and its CHkand |Ck| is the number of nodes that belong to the CkCluster.

The functionf2is to minimize the ratio of the total energy of all the ordinary nodes and the total current energy of the CHs in the current iteration:

Where M is the total number of ordinary nodes,K is the total number of CHs,E(ni)is the current energy of ordinary nodei,and E(CHi) is the current energy of the CHi.

So,the objective function used to select the best CH is:

Wherewis used to control the contribution of each of the sub-objectivesf1andf2.

When the CHs are elected,the nodes decide which cluster to join based on the power of the signals received from the CHs.If two received signals have the same power,then the CH to be joined is chosen randomly.If the received signal is powerful,the node will need less energy to transmit its data to the CH.Each ordinary node transmits a join request to the chosen CH using a CSMA (Carrier Sense Multiple Access) MAC protocol.The join request consists of the node Id,the CH Id,and a header.During this phase,all CHs must keep their radio turned on.After receiving requests from all the joining nodes,each CH allocates a specified duration to the cluster members to establish a communication link,so these nodes can go into sleep mode for the rest of the time.For this reason,each CH allocates to each member node a turn in a TDMA scheduling,and it is only during the allocated time that the nodes can transmit their collected data to the CH.This allows the nodes to turn off their radio antennas and go to the sleeping state to save more energy.In addition,using the TDMA schedule will allow nodes to avoid collisions and interference between nodes in the cluster.

Inter-cluster communication phase

Once the clusters are established,the BS applies the second proposed algorithm using a metaheuristic technique called random search to obtain a shorter path to the BS.The latter sends organizational information of the selected chain to all CHs.

The shorter path is obtained by calculating the costs of the different paths connecting all CH.The cost of each path is the sum of the costs of all the links that make this path.The link cost between two nodes is calculated by considering the transmission power and the receiving power of CHs.So,the link cost between two nodesiandjCan be computed using Eq.(10):

WhereLCi;jis the link cost betweeniandj,TPiis the transmission power ofiandRPjis the receiving power ofj.

The best path that connects all CHs is obtained by running the following algorithm,which is our second proposed algorithm using a jump in random search method.

To determine the best path,we consider the case of sending the data directly from CHs to the BS as an initial solution (S0).Then we classify the set of possible solutions into several subsets.Each subset contains different paths but the last node Id (leader) of each path is identical.So,the subset differs depending on the leader number (the last nodes of the path) chosen to collect all data from other CHs in order to be sent to the BS.The BS randomly chooses a solution from one of these subsets,calculates its cost and compares it with the cost of the current solution.If it is the best one,it is chosen as an optimal solution.Otherwise,the BS chooses another solution among the solutions of the same subset to find the best local solution until the maximum number of iterations is exceeded with no improvement.In this case,the BS makes a jump by selecting another subset and repeats the same procedure.

Figure5:Example of intra-cluster and inter-cluster communication

Algorithm 3 is used to find the optimal path between the CHs.

Algorithm 3:Inter-cluster communication procedure Input:SC: set of solutions; S0 :initial solution; V (SC) :subset solutions; OS :optimal solution; CS :current solution; OSC :optimal solution cost; CSC :current solution cost; J :jumper; I, R:Counter; Output:Construct_ inter-cluster communication paths Initialization:OS ← S0 ; CS ← S0 ; CSC ← CS0 ; OSC ← CS0 ; I ←0 ; R ←0 ; Begin While (I < iterations number) do {test of max of iterations number for selecting the best path in the current round } If (R < = J) Then { jump test} U ← Rand [ V (SC)]; { randomly select a new path from a subset} If (CSC (U) < OSC) Then OS ← U ; Else R ← R + 1; End If; CS ← OS ; I ← I + 1; Else U ← Rand [ SC- V (SC)] {randomly select a new solutions from another subset} If (CSC (U) < OSC) Then OS ← U ; End If; CS ← OS ; I ← I + 1; R ←0; End If; End While; End.

In this phase,the objective of the proposed protocol is to reduce the number of nodes directly communicating with the BS by forming paths of communication between CHs.these paths reduce the data transmission distance from the CHs to the BS,passing by several jumps.

Data transmission phase

After running the two previous procedures,the BS sends all the information obtained to begin intra-cluster and inter-cluster data transmission.The steps of this phase are:

? Activate the radio of the CHs and nodes that want to send the data according to their TDMA;

? Put off the radio of the other ordinary nodes;

? Communication from ordinary nodes to CHs (intra-cluster);

? When the CHs receive data from all members of the group,they perform data processing functions (aggregation and data compression);

? The CHs transmit aggregated and compressed data to BS according to multi-hop communication using the optimal found solution (inter-cluster).

5 Simulation & results

5.1 Simulation settings

To validate the performance of our proposed approach,we use the MATLAB language as a simulation environment.We have kept the same energy model as well as the same hypotheses previously assumed.Two parameters are chosen to evaluate the proposed protocol,which are the consumed energy and the number of live nodes.We named our proposed protocol “EEOFRSJ” (Energy-Efficient clustering protocol for WSNs using an Objective Function and Random Search with Jumps).

In the simulation,we use a network of 100 nodes distributed over an area of 100*100 m2.The position of the BS is outside the surveillance zone at location (50,150).In each round,the live nodes transmit one packet of data.In our simulation,the size of the data packet is 1000 bits.Each node has initial energy equal to 0.1 J.For the contribution of both sub-objectivesf1andf2to be equal,we choosew=0,5.There is no stopping criterion,the simulation only ends when all the nodes consume all their energy.Tab.3 summarizes all the simulation parameters taken in this simulation.

Our simulation is divided into two parts:

First part

In this part,we evaluate the performance of EEOFRSJ and compare its performance with EEFCM [Hadjila,Guyennet and Feham (2013)] using the same simulation parameters shown in the Tab.3.

Second part

In order to show the impact of scalability on EEOFRSJ,we performed other simulations using the same parameters (Tab.3) with different networks sizes.We compared EEOFRSJ with EEFCM varying the network size between 300 nodes and 600 nodes.

Table3:Simulation parameters

5.2 Results of simulation and analysis

The results obtained are shown in the following figures:

Fig.6 shows the simulation results of the energy consumption of nodes in each round for our protocol EEOFRSJ compared with EEFCM protocol.

Figure6:Energy consumption vs. number of rounds

Fig.7 represents a comparison between both protocols in term of number of the live nodes in each round.

Figure7:Number of live nodes vs. number of rounds

Fig.8 and Fig.9 represent the variation of energy consumption with respect to the number of rounds in different networks containing respectively 300 nodes and 600 nodes for both protocols.

Figure8:Energy consumption in a 300-node WSN vs. number of rounds

Figure9:Energy consumption in a 600-node WSN vs. number of rounds

The last two figures show the simulation results of live nodes according to the number of rounds in different networks.

Figure10:Number of live nodes in a 300-node WSN vs. number of rounds

Figure11:Number of live nodes in a 600-node WSN vs. number of rounds

5.3 Results analyses

We performed several simulations (20 times) of EEOFRSJ routing protocols using the same simulation parameters.The results of the above figures represent an averaging of these simulations.

We observe from the simulation result shown in Fig.6 that EEFCM protocol consumes a lot of energy compared to our EEOFRSJ protocol.

The simulation results in Fig.7 show that the first node dies in EEFCM protocol after 1411 rounds,but after 1500 in EEOFRSJ protocol.We also observe that the last node dies in EEFCM protocol after 1751 rounds,while in EEOFRSJ protocol,the last node dies after 1812.

According to the simulation results shown in Fig.8 and Fig.9,EEOFRSJ shows higher efficiency in term of both consumption energy and network lifetime compared with EEFCM protocol.This is due to the effectiveness of the objective function used for selecting the best CHs as well as also the algorithm used for data transmission from CHs to BS.

In Fig.10 and Fig.11,we observe that EEOFRSJ consumes lesser energy and it has a long network lifetime compared with EEFCM protocol.EEOFRSJ maintained the same high efficiency compared to EEFCM protocol even with higher network sizes.We can deduce that our approach fits better with a large-scale network.

6 Conclusion

In WSNs,the concept of clustering is particularly effective when faced with the problem of energy consumption.In this paper,we have proposed an approach called EEOFRSJ which consists firstly of forming clusters by using an objective function based on the distance between ordinary nodes and their CHs,as well as their residual energy.The mode of data transmission to the BS is based on a random search algorithm with jumps.The results of the simulations show that our protocol has better performance compared to EEFCM protocol in terms of energy consumption and network lifetime.In addition,the scalability of the EEOFRSJ protocol is also verified by simulation.As a future work,we suggest the comparison of our protocol with other WSN clustering protocols,including more affecting simulation parameters,and testing them in mobile WSNs.