# Energy Efficient and Safe Weighted Clustering Algorithm for Mobile Wireless Sensor Networks

Authors: Amine Dahane; Abdelhamid Loukil; Bouabdellah Kechar; Nasr-Eddine Berrached
Journal: Mobile Information Systems
 (2015)

---

## Abstract

The main concern of clustering approaches for mobile wireless sensor networks (WSNs) is to prolong the battery life of the individual sensors and the network lifetime. For a successful clustering approach the need of a powerful mechanism to safely elect a cluster head remains a challenging task in many research works that take into account the mobility of the network. The approach based on the computing of the weight of each node in the network is one of the proposed techniques to deal with this problem. In this paper, we propose an energy efficient and safe weighted clustering algorithm (ES-WCA) for mobile WSNs using a combination of five metrics. Among these metrics lies the behavioral level metric which promotes a safe choice of a cluster head in the sense where this last one will never be a malicious node. Moreover, the highlight of our work is summarized in a comprehensive strategy for monitoring the network, in order to detect and remove the malicious nodes. We use simulation study to demonstrate the performance of the proposed algorithm.


---

## Body

## 1. Introduction

After the success of theoretical research contributions in previous decade, wireless sensor networks (WSNs) have become now a reality [1–3]. Their deployment in many societal, environmental, and industrial applications makes them very useful in practice. These networks consisted of large number of small size nodes which sense ubiquitously some physical phenomenon (temperature, humidity, acceleration, noise, light intensity, wind speed, etc.) and report the collected data to the sink station by using multihop wireless communications. Although the nodes are able to self-organize and collaborate together in order to establish and maintain the network, they are battery powered, limited in terms of processing, storage, and communication capabilities [4]. WSNs are considered in many cases as stationary, but topology changes can happen due to a weak mobility (new nodes join the network and existing nodes experience hardware failure or exhaust their batteries) [5]. In other scenarios, the mobility can occur when nodes are carried by external forces such as wind, water, or air [6] so that the network topology can be affected accordingly and can be changed slowly. This second kind of mobility, known as one form of strong mobility in the literature in the sense where nodes are forced to move physically in the deployment area, has been considered in this paper. Clustering means grouping nodes which are closed to each other and it has been widely studied in ad hoc networks [3, 7–14]. More recently, it has been used in WSNs [14–21] where the purpose in general is to reduce useful energy consumption and routing overhead. Figure 1 illustrates how inside the cluster two kinds of nodes can be found: one node called cluster head (CH) or coordinator (in Figure 1: CH1, CH2, and CH3) which is responsible for coordinating the cluster activities and several ordinary nodes called cluster members (CMs) (in Figure 1: CM1 and CM2) that have direct access only to one CH. An ordinary node which is able to hear two or more CHs is called a gateway (G) (in Figure 1: the gateway G2 can hear CH1, CH2, and CH3, while the gateway G1 can hear CH1 and CH2) instead. So, each communication initiated by a cluster member to a destination inside the cluster must pass by CH. If the destination is outside the cluster, the communication must be forwarded by a gateway. Recent research studies recognize that organizing mobile WSNs, in the sense defined above, into clusters by using a clustering mechanism is a challenging task [9, 19]. This is due to the fact that CHs carry out extra work and consequently consume more energy compared to CMs during the network operations and this will lead to untimely death causing network partition and therefore failure in communication link. For this reason, one of the most frequently encountered problems in this mechanism is to search for the best way to elect CH for each cluster. Indeed, a CH can be selected by computing the quality of nodes. This may depend on several metrics: connectivity degree, mobility, residual energy, and the distance of a node from its neighbors. Significant improvement in performance of this quality can be achieved by combining these metrics [3, 9, 10, 12, 19, 21].Figure 1
Clustering formation of WSNs composed of 150 sensor nodes deployed in a 570 m × 555 m space area with a radio range = 100 m.In this paper, we propose an energy efficient and safe weighted clustering algorithm for mobile WSNs using a combination of the above metrics to which we added a behavioral level metric. The latter metric is decisive and allows the proposed clustering algorithm to avoid any malicious node in the neighborhood to become a CH, even if the remaining metrics are in its favor. The election of CHs is carried out using weights of neighboring nodes which are computed based on selected metrics. So this strategy ensures the election of legitimate CHs with high weights. The preliminary results obtained through simulation study demonstrate the effectiveness of our algorithm in terms of the number of equilibrate clusters and the number of reaffiliations, compared to WCA (Weighted Clustering Algorithm) [3], DWCA (Distributed Weighted Clustering Algorithm) [9], and SDCA (Secure Distributed Clustering Algorithm) [21]. These results also reveal that our approach is suitable if we plan to use it in network layer reactive routing protocols instead of proactive ones once the clustering mechanism is launched.We can enumerate the contributions of our paper as follows:(i)
maintaining stable clustering structure and offering a better performance in terms of the number of reaffiliations using the proposed algorithm ES-WCA (Energy Efficient and Safe Weighted Clustering Algorithm);(ii)
detecting common routing problems and attacks in clustered WSNs, based on behavior level;(iii)
showing clearly the interest of the routing protocols in energy saving and therefore maximizing the lifetime of the global network.The remaining part of this paper is organized as follows. Section2 briefly surveys the related works on clustering algorithms proposed for ad hoc networks and in particular those developed for WSNs. In Section 3, we emphasize on the security problems in WSNs. Section 4 introduces and explains the selected metrics for the proposed approach of clustering. More details on the proposed algorithm are given in Section 5. Section 6 presents the simulation tool developed for evaluation. Simulation results are provided to show the effectiveness of the proposed algorithm. Section 7 concludes the paper and outline directions of future works.


## 2. Related Works

In this section, we outline some approaches of clustering used in ad hoc networks and WSNs. Research studies on clustering in ad hoc networks involve surveyed works on clustering algorithms [11, 22] and cluster head election algorithms [10, 16]. Abbasi and Younis [17] presented taxonomy and classification of typical clustering schemes, then summarized different clustering algorithms for WSNs based on classification of variable convergence time protocols and constant convergence time algorithms, and highlighted their objectives, features, complexity, and so forth. A single metric based on clustering as in paper [23] shows that the node with the least stability value is elected as CH among its neighbors. However, the choice of CH which has a lower energy level could quickly become a bottleneck of its cluster. Er and Seah [8] designed and implemented a dynamic energy efficient clustering algorithm (DEECA) for mobile ad hoc networks (MANETs) that increases the network lifetime. The proposed model elects first the nodes that have a higher energy and less mobility as cluster heads, then periodically monitors the cluster head’s energy, and locally alters the clusters to reduce the energy consumption of the suffering cluster heads. The algorithm defines a yellow threshold to achieve some sort of local load balancing and a red threshold to trigger local reclustering in the network. However, the cluster formation in this scheme is not based on connectivity so the formed clusters are not well connected; consequently, this increases the reaffiliation rate and maximizes reclustering situations. Jain and Reddy [24] have proposed a novel method of modeling wireless sensor network using fuzzy graph and energy efficient fuzzy based k-Hop clustering algorithm which takes into account the dynamic nature of network, volatile aspects of radio links, and physical layer uncertainty. They have defined a new centrality metric, namely, fuzzy k-hop centrality. The proposed centrality metric considers residual energy of individual nodes, link quality, hop distance between the prospective cluster head, and respective member nodes to ensure better cluster head selection and cluster quality, which results in better scalability, balancing of energy consumption of nodes, and longer network lifetime. Other proposals use a strategy based on computed weight in order to elect CHs [3, 9, 10, 12]. The main strategy of these algorithms is based mainly on adding more metrics such as the connectivity degree, mobility, residual energy, and the distance of a node from its neighbors, corresponding to some performance in the process of electing CHs. Although the algorithms which use this strategy allow us to ensure the election of better CHs based only on their high computed weight from the considered metrics, they unfortunately do not ensure that the elected CHs are legitimated nodes, that is, whether the election process of CHs is safe or not. Safa et al. [13] propose a novel cluster based trust-aware routing protocol (CBTRP) for MANETs to protect forwarded packets from intermediary malicious nodes. The proposed protocol ensures the passage of packets through trusted routes only by making nodes monitor the behavior of each other and update their trust tables accordingly. However, in CBTRP all nodes monitor the network which lead to rapid drainage of node energy and therefore minimize the lifetime of the network. In Section 3, we show that WSNs are vulnerable to various types of attacks [24, 25]. In the last decade, several studies proposed solutions to solve attacks in WSNs by using cryptography, such as SPINS [26]. However, cryptography alone is not enough to prevent node compromise attacks and novel misbehavior in WSNs [27]. Little effort has been made to include the security aspect in the clustering mechanism. Yu et al. [4, 28] try to secure the clustering mechanism against wormhole attack in ad hoc networks (communication between CHs). However, this is done after forming clusters, not during the election procedure of CHs. Liu [4, 29] surveyed the clustering algorithms available for WSNs but that was done from the perspective of data routing. Hai et al. [30] propose a lightweight intrusion detection framework integrated for clustered sensor networks by using an overhearing mechanism to reduce the sending alert packets. Elhdhili et al. [31] propose a reputation based clustering algorithm (RECA) that aims to elect trustworthy, stable, and high energy cluster heads but during the election procedure, not after forming clusters. Benahmed et al. [21] used clustering mechanism based on weighted computing as an efficient solution to detect misbehavior nodes during distributed monitoring process in WSNs. However, they focused only on the misbehavior of malicious nodes and not on the nature of attacks, the formed clusters are not homogeneous, the proposed algorithm SDCA is not coupled with a routing protocols, and it does not give much importance to energy consumption.In this paper, the proposed approach focuses around strategy of distributed resolution which enables us to generate a reduced number of balanced and homogeneous clusters in order to minimize the energy consumption of the entire network and prolong sensors lifetime. The introduction of a new metric (the behavioral level metric) promotes a safe choice of a cluster head in the sense where this last one will never be a malicious node. Thus, the highlight of our work is summarized in a comprehensive strategy for monitoring the network, in order to detect and remove the malicious nodes.The fact that WSNs include limited energy resources (batteries) due mainly to their small size, our algorithm shows clearly the interest of the routing protocols in energy saving which therefore maximize the lifetime of the network by coupling it with AODV and then DSDV protocols [5, 32, 33].


## 3. Security in WSNs

The typical attacks in WSNs include Sinkhole attack, Black Hole attack, Hello Flood attack, and Node Outage which are the most common network layer attacks on WSNs [30, 34–38]. These selected attacks have been summarized in the following sections.


### 3.1. Sinkhole

Sinkhole attack is one of the most devastating ones: it is very hard to protect against [36, 39]. In a Sinkhole attack, the adversary’s goal is to redirect nearly all the traffic from a particular area through a compromised node, creating a metaphorical sinkhole with the adversary at the center so that all traffic in the surrounding will be absorbed by the malicious node. Because nodes, on or near the path followed by transmitted packets, have many opportunities to tamper with application data. Sinkhole attacks can enable many other attacks such as selective forwarding, for example [40].


### 3.2. Black Hole

In this attack, malicious nodes advertise very short paths (sometimes zero-cost paths) to every other node, forming routing black holes within the network [41]. As their advertisement propagates, the network routes more traffic in their direction. In addition to disrupting traffic delivery, this causes intense resource contention around the malicious node as neighbors compete for limited bandwidth. These neighbors may themselves be exhausted prematurely, causing a hole or partition in the network.


### 3.3. Hello Flood Attack

Many routing protocols use “Hello” broadcast messages to announce themselves to their neighbor nodes. The nodes that receive this message assume that source nodes are within range and add source nodes to their neighbor list. The Hello Flood attacks can be caused by a node which broadcasts a Hello packet with very high power, so that a large number of nodes even far away in the network choose it as the parent node [14]. These nodes are then convinced that the attacker node is their neighbor, so that all the nodes will respond to the Hello message and waste their energy.


### 3.4. Node Outage

If a node acts as an intermediary, an aggregation point, or a cluster head, what happens if the node stops working? Protocols used by the WSNs must be robust enough to mitigate the effects of failures by providing alternate routes [34].


## 3.1. Sinkhole

Sinkhole attack is one of the most devastating ones: it is very hard to protect against [36, 39]. In a Sinkhole attack, the adversary’s goal is to redirect nearly all the traffic from a particular area through a compromised node, creating a metaphorical sinkhole with the adversary at the center so that all traffic in the surrounding will be absorbed by the malicious node. Because nodes, on or near the path followed by transmitted packets, have many opportunities to tamper with application data. Sinkhole attacks can enable many other attacks such as selective forwarding, for example [40].


## 3.2. Black Hole

In this attack, malicious nodes advertise very short paths (sometimes zero-cost paths) to every other node, forming routing black holes within the network [41]. As their advertisement propagates, the network routes more traffic in their direction. In addition to disrupting traffic delivery, this causes intense resource contention around the malicious node as neighbors compete for limited bandwidth. These neighbors may themselves be exhausted prematurely, causing a hole or partition in the network.


## 3.3. Hello Flood Attack

Many routing protocols use “Hello” broadcast messages to announce themselves to their neighbor nodes. The nodes that receive this message assume that source nodes are within range and add source nodes to their neighbor list. The Hello Flood attacks can be caused by a node which broadcasts a Hello packet with very high power, so that a large number of nodes even far away in the network choose it as the parent node [14]. These nodes are then convinced that the attacker node is their neighbor, so that all the nodes will respond to the Hello message and waste their energy.


## 3.4. Node Outage

If a node acts as an intermediary, an aggregation point, or a cluster head, what happens if the node stops working? Protocols used by the WSNs must be robust enough to mitigate the effects of failures by providing alternate routes [34].


## 4. Metrics for CHs Election

This section introduces the different metrics used for cluster head election by focusing on behavior level metric.


### 4.1. The Behavior Level of Nodeni (BLi)

The behavioral level of a nodeni is a key metric in our contribution. Initially, each node is assigned an equal static behavior level “BLi = 1.” However, this level can be decreased by the anomaly detection algorithm if a node misbehaves. For computing the behavior level of each node, nodes with a behavior level less than threshold behavior will not be accepted as CH candidates even if they have the other interesting characteristics such as high energy, high degree of connectivity, or low mobility. Nevertheless, abnormal nodes and suspect nodes may belong to a cluster as CM but never as CH. So, we define the behavior level of each sensor node ni, noted BLi, in any neighborhood of the network as illustrated in Figure 2.Figure 2
Behavior levelBLi∈[0,1].B
L
i is classified by the following mapping function:(1)MpBLi=Normalnode:0.8≤BLi≤1Abnormalnode:0.5≤BLi<0.8Suspectnode:0.3≤BLi<0.5Maliciousnode:0≤BLi<0.3.The values in formula (1) are chosen on the basis of several reputed models of WSNs adopted by numerous researchers like Shaikh et al. [42] and Lehsaini et al. [43]. The monitor node watches its neighbors to know what each one of them does with the messages it receives from another neighbor. If the neighbor of the monitor changes, delays, replicates, or simply keeps a message that should be retransmitted, the monitor counts a failure. Number of failures have influence on the behavior of neighbors; for instance, if the monitor counts one failure from a neighbor, its behavior will decrease by 0.1 units. This allows the monitor (cluster head) to differentiate malicious nodes (that make much failure) of a legitimate node (that make fewer failure) in case there are collisions.


### 4.2. The Mobility of Nodeni  (Mi)

Our objective is to have stable clusters. So, we have to elect nodes with low relative mobility as CHs. To characterize the instantaneous nodal mobility, we use a simple heuristic mechanism as presented in the formula below (2) [4, 44]:(2)Mi=1T∑t=1Txt-xt-12+yt-yt-12,where xt,yt and xt-1,yt-1 are the coordinates of node ni at time t and t-1, respectively. T is the period for which this parameter is estimated.In our previous paper [4], the considered mobility has a particular sense by the fact that a mobile node does not move from one location to another in the space area of its own will, but in our case, it moves through the forces acting from the outside. These external forces can act from time to time sporadically. In contrary, the malicious node can use its own ability to move freely in the space area. The behavior of the malicious node by moving frequently inside the same cluster (case illustrated by Figure 3) or from a cluster to another is a normal behavior to not attract attention of the neighborhood and therefore be detected. The idea of our algorithm to ensure the choice of a legitimate CH is to never elect a node that moves frequently and even it has the best performance metrics, but this malicious node does nothing just mobility, so in this paper our algorithm (ES-WCA) detects the internal misbehavior of nodes during distributed monitoring process in WSNs by the follow-up of the messages exchanged between the nodes. ES-WCA is based on the ideas proposed by da Silva et al. [45] used in his efficient and accurate IDS in detecting different kinds of simulated attacks.Figure 3
(a) Clustering mechanism in mobile WSNs before moving nodes and (b) after moving nodes 1, 5, and 4.
(a)
(b)


### 4.3. The Distance between Nodeni and Its Neighbors (Di)

This is likely to reduce node detachments and enhance cluster stability. For each nodei, we compute the sum of the distance Di with all its neighbors j. This distance is given, as in [3, 4, 9], by(3)Di=∑j∈Nidisti,j.


### 4.4. The Residual Energy of Nodeni (Eri)

The residual energy of a nodeni, after transmitting a message of k bits at distance d from the receiver, is calculated according to [4, 16](4)Eri=E-ETxk,d+ERxeleck,where (i)
E: the node’s current energy;(ii)
ETxk,d=k·Eelec+k·Eamp·d2: it refers to the required energy to send a message, where Eamp is the required amplifier energy;(iii)
ERxeleck=kEelec: it refers to the energy consumed while receiving a message.


### 4.5. The Degree of Connectivity of Nodeni at Time t (Ci)

It represents the number ofni’s neighbors given by (5) according to [4](5)Ci=Ni,where (i)
Ni=ni/disti,j<txrangewithi≠j,(ii)
disti,j: outdistance separating two nodes ni and nj,(iii)
txrange: the transmission radius.For each node, we must calculate its weight Pi, according to the equation:(6)Pi=w1∗BLi+w2∗Eri+w3∗Mi+w4∗Ci+w5∗Di,where w1, w2, w3, w4, and w5 are the coefficients corresponding to the system criteria, so that (7)w1+w2+w3+w4+w5=1.We propose to generate homogeneous clusters whose size lies between two thresholds: ThreshUpper and ThreshLower.These thresholds are arbitrarily selected or they depend on the topology of the network. Thus, if their values depend on the topology of the network, they are calculated as follows according to [43]:(i)
u: the node that has the maximum number of neighbors with one jump:(8)δ12u=min⁡δ12ui:ui∈U,(ii)
v: the node that has the minimal number of neighbors with one jump: (9)δ12v=min⁡δ12vi:vi∈U.We denote AVG by the average cardinal of the groups with one jump of all the nodes of the network:(10)AVG=∑i=1nδ12uiN,where N represents the number of nodes in the network. Thus, the two thresholds are calculated as follows: (11)ThreshUpper=12δ12u+AVG,ThreshLower=12δ12v+AVG.The calculated weight for each sensor is based on the above parameters (BLi,Mi,Di,Eri, and Ci). The values of coefficients wi should be chosen depending on the basis of the importance of each metric in considered WSNs applications. For instance, it is possible to assign a greater value to the metric BLi compared to other metrics if we promote the safety aspect in the clustering mechanism. It is also possible to assign the same value for each coefficient wi in the case where all metrics are considered as having the same importance. An approach based on these weight types will enable us to build a self-organizing algorithm which forms a small number of homogenous clusters in size and radius by geographically grouping close nodes. The resulting weighted clustering algorithm reduces energy consumption and guaranties the choice of legitimate CHs.


## 4.1. The Behavior Level of Nodeni (BLi)

The behavioral level of a nodeni is a key metric in our contribution. Initially, each node is assigned an equal static behavior level “BLi = 1.” However, this level can be decreased by the anomaly detection algorithm if a node misbehaves. For computing the behavior level of each node, nodes with a behavior level less than threshold behavior will not be accepted as CH candidates even if they have the other interesting characteristics such as high energy, high degree of connectivity, or low mobility. Nevertheless, abnormal nodes and suspect nodes may belong to a cluster as CM but never as CH. So, we define the behavior level of each sensor node ni, noted BLi, in any neighborhood of the network as illustrated in Figure 2.Figure 2
Behavior levelBLi∈[0,1].B
L
i is classified by the following mapping function:(1)MpBLi=Normalnode:0.8≤BLi≤1Abnormalnode:0.5≤BLi<0.8Suspectnode:0.3≤BLi<0.5Maliciousnode:0≤BLi<0.3.The values in formula (1) are chosen on the basis of several reputed models of WSNs adopted by numerous researchers like Shaikh et al. [42] and Lehsaini et al. [43]. The monitor node watches its neighbors to know what each one of them does with the messages it receives from another neighbor. If the neighbor of the monitor changes, delays, replicates, or simply keeps a message that should be retransmitted, the monitor counts a failure. Number of failures have influence on the behavior of neighbors; for instance, if the monitor counts one failure from a neighbor, its behavior will decrease by 0.1 units. This allows the monitor (cluster head) to differentiate malicious nodes (that make much failure) of a legitimate node (that make fewer failure) in case there are collisions.


## 4.2. The Mobility of Nodeni  (Mi)

Our objective is to have stable clusters. So, we have to elect nodes with low relative mobility as CHs. To characterize the instantaneous nodal mobility, we use a simple heuristic mechanism as presented in the formula below (2) [4, 44]:(2)Mi=1T∑t=1Txt-xt-12+yt-yt-12,where xt,yt and xt-1,yt-1 are the coordinates of node ni at time t and t-1, respectively. T is the period for which this parameter is estimated.In our previous paper [4], the considered mobility has a particular sense by the fact that a mobile node does not move from one location to another in the space area of its own will, but in our case, it moves through the forces acting from the outside. These external forces can act from time to time sporadically. In contrary, the malicious node can use its own ability to move freely in the space area. The behavior of the malicious node by moving frequently inside the same cluster (case illustrated by Figure 3) or from a cluster to another is a normal behavior to not attract attention of the neighborhood and therefore be detected. The idea of our algorithm to ensure the choice of a legitimate CH is to never elect a node that moves frequently and even it has the best performance metrics, but this malicious node does nothing just mobility, so in this paper our algorithm (ES-WCA) detects the internal misbehavior of nodes during distributed monitoring process in WSNs by the follow-up of the messages exchanged between the nodes. ES-WCA is based on the ideas proposed by da Silva et al. [45] used in his efficient and accurate IDS in detecting different kinds of simulated attacks.Figure 3
(a) Clustering mechanism in mobile WSNs before moving nodes and (b) after moving nodes 1, 5, and 4.
(a)
(b)


## 4.3. The Distance between Nodeni and Its Neighbors (Di)

This is likely to reduce node detachments and enhance cluster stability. For each nodei, we compute the sum of the distance Di with all its neighbors j. This distance is given, as in [3, 4, 9], by(3)Di=∑j∈Nidisti,j.


## 4.4. The Residual Energy of Nodeni (Eri)

The residual energy of a nodeni, after transmitting a message of k bits at distance d from the receiver, is calculated according to [4, 16](4)Eri=E-ETxk,d+ERxeleck,where (i)
E: the node’s current energy;(ii)
ETxk,d=k·Eelec+k·Eamp·d2: it refers to the required energy to send a message, where Eamp is the required amplifier energy;(iii)
ERxeleck=kEelec: it refers to the energy consumed while receiving a message.


## 4.5. The Degree of Connectivity of Nodeni at Time t (Ci)

It represents the number ofni’s neighbors given by (5) according to [4](5)Ci=Ni,where (i)
Ni=ni/disti,j<txrangewithi≠j,(ii)
disti,j: outdistance separating two nodes ni and nj,(iii)
txrange: the transmission radius.For each node, we must calculate its weight Pi, according to the equation:(6)Pi=w1∗BLi+w2∗Eri+w3∗Mi+w4∗Ci+w5∗Di,where w1, w2, w3, w4, and w5 are the coefficients corresponding to the system criteria, so that (7)w1+w2+w3+w4+w5=1.We propose to generate homogeneous clusters whose size lies between two thresholds: ThreshUpper and ThreshLower.These thresholds are arbitrarily selected or they depend on the topology of the network. Thus, if their values depend on the topology of the network, they are calculated as follows according to [43]:(i)
u: the node that has the maximum number of neighbors with one jump:(8)δ12u=min⁡δ12ui:ui∈U,(ii)
v: the node that has the minimal number of neighbors with one jump: (9)δ12v=min⁡δ12vi:vi∈U.We denote AVG by the average cardinal of the groups with one jump of all the nodes of the network:(10)AVG=∑i=1nδ12uiN,where N represents the number of nodes in the network. Thus, the two thresholds are calculated as follows: (11)ThreshUpper=12δ12u+AVG,ThreshLower=12δ12v+AVG.The calculated weight for each sensor is based on the above parameters (BLi,Mi,Di,Eri, and Ci). The values of coefficients wi should be chosen depending on the basis of the importance of each metric in considered WSNs applications. For instance, it is possible to assign a greater value to the metric BLi compared to other metrics if we promote the safety aspect in the clustering mechanism. It is also possible to assign the same value for each coefficient wi in the case where all metrics are considered as having the same importance. An approach based on these weight types will enable us to build a self-organizing algorithm which forms a small number of homogenous clusters in size and radius by geographically grouping close nodes. The resulting weighted clustering algorithm reduces energy consumption and guaranties the choice of legitimate CHs.


## 5. Weighted Clustering Algorithm (ES-WCA)

In this section, we first present some assumptions of the proposed algorithm: Energy Efficient and Safe Weighted Clustering algorithm (ES-WCA). Then we present in detail an extended version of ES-WCA [4] followed by an illustrative example.


### 5.1. Assumptions

This paper is based on the following assumptions.(i)
The network formed by the nodes and the links can be represented by an undirected graphG=(U,E), where U represents the set of nodes ni and E represents the set of links ei [3, 4].(ii)
All sensor nodes are deployed randomly in a 2-dimension (2D) plane.(iii)
A node interacts with its one-hop neighbors directly and with other nodes via intermediate nodes using multihop packet forwarding based on a routing protocol such as ad hoc on demand distance vector [5, 32] or DSDV [33].(iv)
The radio coverage of sensor nodes is a circular region centered on this node with radiusR.(v)
Two sensor nodes cannot be deployed in exactly the same positionx, y in a 2D space.(vi)
All sensor nodes are identical or homogeneous. For example, they have the same radio coverage radiusR.(vii)
Each node can determine its position at any moment in a 2D space.(viii)
Each cluster is monitored by only one CH.(ix)
Each CM communicates directly with its CH for the transmission of security metrics.(x)
A CH communicates directly with the base station for the transmission of security information and possible alerts.


### 5.2. Proposed Algorithm

The ES-WCA algorithm that we present below is based on the ideas proposed by Chatterjee et al. [3], Lehsaini et al. [43], and Zabian et al. [10], with modifications made for our application. This algorithm runs in three phases: the setup phase, the reaffiliation phase, and the monitoring phase. ES-WCA combines each of the above system parameters with certain weighting factors chosen according to the system needs.


#### 5.2.1. The Setup Phase

ES-WCA uses three types of messages in the setup phase (Algorithm1). The message CHmsg is sent in the network by the sensor node which has the greatest weigh. The second one is the JOINmsg message which is sent by the neighbor of CH if it wants to join this cluster. Finally, a CH must send a response ACCEPTmsg message as shown in Figure 4.Algorithm 1:Algorithm setup phase.
Begin
(1)Assign values to the coefficients w1,w2,w3,w4,w5;
(2)For any node ni∈G  make:
(3)ni forms a list of its neighbors N(i) through the Message {who_are_neighbors};
(4)Ni=∅;
(5)Calculate its weight Pi:
(6)Pi=w1∗BLi+w2∗Eri+w3∗Mi+w4∗Ci+w5∗Di;
(7) Initialize Time Cluster and the state vector of all
nodes ni∈G Vector_State (Id, CH, Weight, List_Neighbors, Size, Nature)
(8) CH = 0, Size = 0;
(9) Nature = “None”;
(10) Repeat
(11)Any node ni∈G Broadcasts a message “Hello”;
(12)If  N(i)<>∅  Then
(13)Choose v∈N(i);
(14)Weightv=max⁡weightw/w∈Ni;
(15)the node that have thesame maximum weight, the CH is
the node that has the best criteria ordered by their
importance (
BL
i
, Eri, Ci,  Di  and  Mi) if all criteria of
nodes are equal, the choice is random.
(15)Else  ni is a CH of itself.
EndIf
(16)Update the state vector of the elected CH;
(17)CH = ID;
(18)Size = 1;
(19)Nature = CH;
(20)Send the message “CHmsg” by CH to its neighbors N(CH);
(21)J = Count (N(CH));
(22)For  I = 1 to J  Do
(23)If  (ni∈N(CH) receives the message && ni→ CH = 0)
(24)  Then  ni sends a message “JOINmsg” to CH
(25)If (CH → Size < ThreshUpper)
(26)  Then CH sends a message “ACCEPTmsg” to Node ni;
(27)    CH executes the accession process;
(28)    CH → Size = CH → Size + 1;
(29)    ni executes the accession process;
(30)    ni→ CH = CH → Id;
(31)    Else go to (10);
EndIf
EndIf
End For
(32)Until expired (TimeCluster);
End.Figure 4
Procedure of affiliation of node “U” to a cluster.The node which has the greatest weight begins the procedure by broadcasting CH message to their 1-hop neighbors to confirm its role as a leader of the cluster. The neighbors confirm their role as being member nodes by broadcasting a JOINmsg message. In the case when nodes have the same maximum weight, the CH is chosen by using the best parameters ordered by their importance. If all parameters of nodes are equal, the choice is random.


#### 5.2.2. The Reaffiliation Phase

ES-WCA uses four types of messages in the reaffiliation phase (Algorithm2). The message RE_AFF_CH is sent in the network by the CH whose cluster size is less than ThreshUpper. The second one is the REQ_RE_AFF message which is sent by the neighbors of CH if it wants to join this cluster. Finally a CH must send a response ACCEPT_RE_AFF message or DROP_AFF message as illustrated by Figure 5. Accordingly, in this phase we propose to reaffiliate the sensor nodes belonging to clusters that have not attained the cluster size ThreshLower to those that did not achieve ThreshUpper in order to reduce the number of clusters formed and organize them so as to obtain homogeneous and balanced clusters.Algorithm 2:Algorithm reaffiliation phase.
Inputs:
T
h
r
e
s
h
U
p
p
e
r,ThreshLower;
Outputs: set of clusters
Begin
(1)For num_cl = 1 to Count (Cluster) Do
(2) If (Size (Cluster [num_cl]) < ThreshUpper)
Then
(3)  CH sends a message “RE_AFF_CH” to its neighbors
(N(CH));
(4)J = Count (N(CH));
EndIf
(5)For  I=1 to J  Do
(6) If (ni∈N(CH) receives the message)
&& (ni∈(Size (Cluster [num_cl]) < ThreshLower)
Then
(7)  ni sends a Select message “REQ_RE_AFF” to the CH;
(8) If (Size (Cluster [num_cl]) < ThreshUpper)
Then
(9)  CH sends a message “ACCEPT_RE_AFF” to ni;
(10)   CH updates its state vector;
(11)   CH → CH → Size = Size + 1;
(12)ni updates its state vector;
(13)ni → CH → ID = ID;
(14)Else CH sends a “FIN_AFF” message to ni;
(15)   Go to (2);
EndIF
(16)Else  ni sends a “DROP_AFF” message to CH;
EndIf
End For
End For
End.Figure 5
Procedure of reaffiliation of node “U” to a cluster.With the help of 3 figures (Figures6, 7, and 8), our algorithm setup phase is demonstrated. Table 1 shows the quantitative results of the different criteria applied on the normal nodes (BLi≥0.8). Table 2 shows the weights Pi of neighbors for each node which has behavior BLi higher than 0.8. The circles in Figure 6 represent the nodes, their identity Ids are at the top, and their levels of behavior are at the bottom. According to Table 2, node 1 could be attached to either CH11 or CH8 (since they have the same weight). However, the behavior level of node 11 is greater than that of node 8 (BL11>BL8). So, node 1 will be attached to CH11. For the other nodes, we have various conditions. Node 4 declares itself as a CH. Node 5 will be attached to CH4. Node 6 declares itself as a CH, because it is an isolated node. Node 8 will be attached to CH4. Node 10 is connected to CH5, but node 5 is attached to CH4. Thus, node 10 declares itself as a CH. Node 11 declares itself as a CH. These results give us the representation shown in Figure 7. Node 2 is connected to CH4 and CH10. Node 2 will be attached to CH4, because CH4 has the maximum weight (968.133). Node 3 is connected to CH4, which implies that node 3 will be attached to CH4. Node 7 is not connected to any CH, so node 7 declares itself as CH. Node 9 is connected to CH4, and then node 9 will be attached to CH4. Node 12 is not connected to any CH, which implies that node 12 declares itself as a CH. These results give us the representation shown in Figure 8. We propose to generate homogeneous clusters whose size lies between two thresholds: ThreshUpper=9 and ThreshLower=6. For that, we suggest to reaffiliate the sensor nodes belonging to the clusters that have not attained the cluster size ThreshLower to those that did not reach ThreshUpper. Node 4 has the highest weight and his size is less than ThreshUpper. Nodes 1, 7, and 10 are neighbors of node 4 with 2 hops and belong to the clusters that have not attained the cluster size ThreshLower, so these nodes get merged to cluster 2. Clusters 1, 3, and 4 will be homogeneous with cluster 1 when the network becomes densely.Table 1
Values of the various criteria of normal nodes.
Ids
BL
i
Er
i
C
i
D
i
M
i
P
i
1
0.86
3842.12
3
1.15
1.20
769.632
4
0.81
4832.54
5
2.30
0.30
968.133
5
0.88
4053.25
3
1.30
0.55
811.829
6
0.85
4620.43
0
0.00
0.20
924.361
8
0.81
4816.80
4
1.05
1.40
964.753
10
0.95
3650.25
2
0.55
0.10
730.805
11
0.91
4819.60
1
0.70
2.20
964.753Table 2
Weights of neighbors.
Ids
1
4
5
6
8
10
11
1
769.632
964.753
964.753
4
968.133
811.829
964.753
5
968.133
811.829
730.805
6
924.361
8
769.632
964.753
10
968.133
811.829
730.805
11
769.632
964.753Figure 6
Topology of the network.Figure 7
Identification of clusters node.Figure 8
The final identification of clusters.At the end of this example, we obtain a network of four clusters (as shown in Figure9).Figure 9
Final cluster structure (reaffiliation phase).There are five situations that require the maintenance of clusters:(i)
battery depletion of a node,(ii)
behavior level of a node less than or equal 0.3,(iii)
adding, moving, or deleting a node.In all of these cases, if a nodeni is CH then the setup phase will be repeated.


#### 5.2.3. The Monitoring Phase

Monitoring in WSNs can be both local and global. The local monitoring can be with respect to a node and the global monitoring can be with respect to the network, but in sensor networks, for detecting some types of errors and security anomalies, the local monitoring would be insufficient [46]. For this reason, we adopt in this paper a hybrid approach that is global monitoring based on distributed local monitoring. The general architecture of our approach is illustrated in Figure 10. Our simulator, baptized “Mercury,” detects the internal misbehavior nodes during distributed monitoring process in WSNs by the follow-up of the messages exchanged between the nodes. We assume that the network has already a mechanism of prevention to avoid the external attacks. By using a set of rules, all the received messages are analyzed. A similar approach is used by da Silva et al. [45] and Benahmed et al. [21].Figure 10
Monitoring phase architecture.Algorithm 4  (monitoring phase algorithm). The monitoring process involves a series of steps as illustrated by the flowchart in (Figure 11).Figure 11
Monitoring phase.Step 1  (this step runs in each
C
H
i
). Each CHi becomes the monitor node of its cluster members and broadcasts a “Start Monitoring” message with its Idi to its entire cluster CMs.Step 2  (calculation of security metrics performed by each member
n
i
of the cluster
i
). Each node ni (i<>j) receives the message “Start Monitoring” and calculates its security metrics as follows.(i)
Number of packets sent byni at time interval is Δt=t0,t:Nbp_Send(ni,Δt).(ii)
Number of packets received by nodeni at time interval is Δt=t0,t0:Nbp_Received(ni,Δt).(iii)
Delay between the arrivals of two consecutive packets is(12)Delay_BPni,t=Arrival_PTi-Arrival_PTi-1.(iv)
Energy consumption: the energy consumed by the nodej in receiving and sending packets is measured using the following equation:(13)Ecni,Δt=Erni,t0-Erni,t1,where Δt is the time interval t0,t1;Er(ni,t0) is the residual energy of node ni at time t0; Er(ni,t1) is the residual energy of node ni at time t1and Ec(ni,Δt) is the energy consumption of node ni at time interval Δt.Step 3  (sending all metrics to the CH). After each consumption of the security metrics, the state of a node ni at time t is denoted by state (ni,ti). For storage volume economy, each node keeps only the latest calculation state.(i)
In the initial deployment, each CM in cluster “i” sends some states (state(ni,ti)) to the CHi for making a normal behavior model of node ni by using a learning mechanism.(ii)
Each state contains the following information:(14)Id,NbpSendni,Δt,NbpReceivedni,Δt,DelayBPni,t,Ecni,Δt.(iii)
If (state(ni,ti) − state (ni,ti-1) >ϵ)
then nodenisends a message (ϵ a given threshold):
Msg = (Id,NbpSendni,Δt, NbpReceivedni,Δt, DelayBPni,t, Ecni,Δt)to its CHi for monitoring purposes.Otherwise, no information is sent to the CH.(iv)
The message received by CHi will be stored in a table Tmet for future analysis.(v)
If a sensor nodeni does not respond during this monitoring period, it will be considered as misbehaving.(vi)
The behavior level of sensor nodeni is computed using the following equation:(15)BLi=BLi-rate.The “rate” is fixed on the basis of the nature of the application. For example, if it is fault tolerant or not. In our case, we took rate = 0.1.Step 4  (misbehavior detection, which is performed by CH
i
).(i)
For each nodeni in the cluster “i,” the state in time slot “t” is expressed by the three-dimensional vector:(16)S=St1,St2,St3,where
(a)
St1 is the number of packets dropped by ni, defined as follows:(17)St1=∑PsReceivedbyni-∑PsSentbyni-∑Psdestinedbyni,with(18)∑PsReceivedbyni=∑PsSentbyni+∑Psdestinedbyni+∑Pslostbyni.For a normal node,St1≈0.(b)
St2 is the delay between the arrival of two consecutive packets:(19)St2=Delay_BPni,t.(c)
St3 is the energy consumption:(20)St3=Ecni,Δt.Here,t∈[t0,t]=Δt.(ii)
In our case, the first interval is used for the training data set ofn time slots. We calculate the mean vector S- of S by using (21)S-=∑t=t0tn-1Stn.(iii)
After modeling a normal behavior model for each sensor node, the behaviors of all nodes are sent to the base station for further analysis. We then compute the deviationdS by using (22)dS=S-S-.(iv)
When the deviationd(S) is larger than threshold Th (which means that it is out of the range of normal behavior), it will be judged as a misbehaving node. In this case, the level of behavior is BLi≈0. This is called the punishing algorithm:(23)dS>Th:niisanabnormalnodedS≤Th:niIsanormalnode.The punishing algorithm is presented in Algorithm 3.Algorithm 3:Punishing algorithm.
Begin
(1)I≔0;
(2)I≔I+1;
(3)If ((I = Rate)  &&  (BLi<=0.1))
// Rate: parameter of maximum number of faults
defined by the administrator
BLi=BLi-Rate;
(4)// Classification of the node according to its BLi
(5)MpBLi=Normal node:0.8≤BLi≤1Abnormal node:0.5≤BLi<0.8Suspect node:0.3≤BLi<0.5Malicious node:0≤BLi<0.3
(6)If (BLi≤0.3) Then
(7)  If (ni is CM) Then
(8)Suppression of the node of the list of the members;
(9)Addition of the node to the blacklist;
EndIf
(10)If (ni is CH) Then    // CH: Cluster Head
(11) Addition of the node to the blacklist;
(12) Set up Phase;
EndIf
EndIf
EndIf
End.


## 5.1. Assumptions

This paper is based on the following assumptions.(i)
The network formed by the nodes and the links can be represented by an undirected graphG=(U,E), where U represents the set of nodes ni and E represents the set of links ei [3, 4].(ii)
All sensor nodes are deployed randomly in a 2-dimension (2D) plane.(iii)
A node interacts with its one-hop neighbors directly and with other nodes via intermediate nodes using multihop packet forwarding based on a routing protocol such as ad hoc on demand distance vector [5, 32] or DSDV [33].(iv)
The radio coverage of sensor nodes is a circular region centered on this node with radiusR.(v)
Two sensor nodes cannot be deployed in exactly the same positionx, y in a 2D space.(vi)
All sensor nodes are identical or homogeneous. For example, they have the same radio coverage radiusR.(vii)
Each node can determine its position at any moment in a 2D space.(viii)
Each cluster is monitored by only one CH.(ix)
Each CM communicates directly with its CH for the transmission of security metrics.(x)
A CH communicates directly with the base station for the transmission of security information and possible alerts.


## 5.2. Proposed Algorithm

The ES-WCA algorithm that we present below is based on the ideas proposed by Chatterjee et al. [3], Lehsaini et al. [43], and Zabian et al. [10], with modifications made for our application. This algorithm runs in three phases: the setup phase, the reaffiliation phase, and the monitoring phase. ES-WCA combines each of the above system parameters with certain weighting factors chosen according to the system needs.


### 5.2.1. The Setup Phase

ES-WCA uses three types of messages in the setup phase (Algorithm1). The message CHmsg is sent in the network by the sensor node which has the greatest weigh. The second one is the JOINmsg message which is sent by the neighbor of CH if it wants to join this cluster. Finally, a CH must send a response ACCEPTmsg message as shown in Figure 4.Algorithm 1:Algorithm setup phase.
Begin
(1)Assign values to the coefficients w1,w2,w3,w4,w5;
(2)For any node ni∈G  make:
(3)ni forms a list of its neighbors N(i) through the Message {who_are_neighbors};
(4)Ni=∅;
(5)Calculate its weight Pi:
(6)Pi=w1∗BLi+w2∗Eri+w3∗Mi+w4∗Ci+w5∗Di;
(7) Initialize Time Cluster and the state vector of all
nodes ni∈G Vector_State (Id, CH, Weight, List_Neighbors, Size, Nature)
(8) CH = 0, Size = 0;
(9) Nature = “None”;
(10) Repeat
(11)Any node ni∈G Broadcasts a message “Hello”;
(12)If  N(i)<>∅  Then
(13)Choose v∈N(i);
(14)Weightv=max⁡weightw/w∈Ni;
(15)the node that have thesame maximum weight, the CH is
the node that has the best criteria ordered by their
importance (
BL
i
, Eri, Ci,  Di  and  Mi) if all criteria of
nodes are equal, the choice is random.
(15)Else  ni is a CH of itself.
EndIf
(16)Update the state vector of the elected CH;
(17)CH = ID;
(18)Size = 1;
(19)Nature = CH;
(20)Send the message “CHmsg” by CH to its neighbors N(CH);
(21)J = Count (N(CH));
(22)For  I = 1 to J  Do
(23)If  (ni∈N(CH) receives the message && ni→ CH = 0)
(24)  Then  ni sends a message “JOINmsg” to CH
(25)If (CH → Size < ThreshUpper)
(26)  Then CH sends a message “ACCEPTmsg” to Node ni;
(27)    CH executes the accession process;
(28)    CH → Size = CH → Size + 1;
(29)    ni executes the accession process;
(30)    ni→ CH = CH → Id;
(31)    Else go to (10);
EndIf
EndIf
End For
(32)Until expired (TimeCluster);
End.Figure 4
Procedure of affiliation of node “U” to a cluster.The node which has the greatest weight begins the procedure by broadcasting CH message to their 1-hop neighbors to confirm its role as a leader of the cluster. The neighbors confirm their role as being member nodes by broadcasting a JOINmsg message. In the case when nodes have the same maximum weight, the CH is chosen by using the best parameters ordered by their importance. If all parameters of nodes are equal, the choice is random.


### 5.2.2. The Reaffiliation Phase

ES-WCA uses four types of messages in the reaffiliation phase (Algorithm2). The message RE_AFF_CH is sent in the network by the CH whose cluster size is less than ThreshUpper. The second one is the REQ_RE_AFF message which is sent by the neighbors of CH if it wants to join this cluster. Finally a CH must send a response ACCEPT_RE_AFF message or DROP_AFF message as illustrated by Figure 5. Accordingly, in this phase we propose to reaffiliate the sensor nodes belonging to clusters that have not attained the cluster size ThreshLower to those that did not achieve ThreshUpper in order to reduce the number of clusters formed and organize them so as to obtain homogeneous and balanced clusters.Algorithm 2:Algorithm reaffiliation phase.
Inputs:
T
h
r
e
s
h
U
p
p
e
r,ThreshLower;
Outputs: set of clusters
Begin
(1)For num_cl = 1 to Count (Cluster) Do
(2) If (Size (Cluster [num_cl]) < ThreshUpper)
Then
(3)  CH sends a message “RE_AFF_CH” to its neighbors
(N(CH));
(4)J = Count (N(CH));
EndIf
(5)For  I=1 to J  Do
(6) If (ni∈N(CH) receives the message)
&& (ni∈(Size (Cluster [num_cl]) < ThreshLower)
Then
(7)  ni sends a Select message “REQ_RE_AFF” to the CH;
(8) If (Size (Cluster [num_cl]) < ThreshUpper)
Then
(9)  CH sends a message “ACCEPT_RE_AFF” to ni;
(10)   CH updates its state vector;
(11)   CH → CH → Size = Size + 1;
(12)ni updates its state vector;
(13)ni → CH → ID = ID;
(14)Else CH sends a “FIN_AFF” message to ni;
(15)   Go to (2);
EndIF
(16)Else  ni sends a “DROP_AFF” message to CH;
EndIf
End For
End For
End.Figure 5
Procedure of reaffiliation of node “U” to a cluster.With the help of 3 figures (Figures6, 7, and 8), our algorithm setup phase is demonstrated. Table 1 shows the quantitative results of the different criteria applied on the normal nodes (BLi≥0.8). Table 2 shows the weights Pi of neighbors for each node which has behavior BLi higher than 0.8. The circles in Figure 6 represent the nodes, their identity Ids are at the top, and their levels of behavior are at the bottom. According to Table 2, node 1 could be attached to either CH11 or CH8 (since they have the same weight). However, the behavior level of node 11 is greater than that of node 8 (BL11>BL8). So, node 1 will be attached to CH11. For the other nodes, we have various conditions. Node 4 declares itself as a CH. Node 5 will be attached to CH4. Node 6 declares itself as a CH, because it is an isolated node. Node 8 will be attached to CH4. Node 10 is connected to CH5, but node 5 is attached to CH4. Thus, node 10 declares itself as a CH. Node 11 declares itself as a CH. These results give us the representation shown in Figure 7. Node 2 is connected to CH4 and CH10. Node 2 will be attached to CH4, because CH4 has the maximum weight (968.133). Node 3 is connected to CH4, which implies that node 3 will be attached to CH4. Node 7 is not connected to any CH, so node 7 declares itself as CH. Node 9 is connected to CH4, and then node 9 will be attached to CH4. Node 12 is not connected to any CH, which implies that node 12 declares itself as a CH. These results give us the representation shown in Figure 8. We propose to generate homogeneous clusters whose size lies between two thresholds: ThreshUpper=9 and ThreshLower=6. For that, we suggest to reaffiliate the sensor nodes belonging to the clusters that have not attained the cluster size ThreshLower to those that did not reach ThreshUpper. Node 4 has the highest weight and his size is less than ThreshUpper. Nodes 1, 7, and 10 are neighbors of node 4 with 2 hops and belong to the clusters that have not attained the cluster size ThreshLower, so these nodes get merged to cluster 2. Clusters 1, 3, and 4 will be homogeneous with cluster 1 when the network becomes densely.Table 1
Values of the various criteria of normal nodes.
Ids
BL
i
Er
i
C
i
D
i
M
i
P
i
1
0.86
3842.12
3
1.15
1.20
769.632
4
0.81
4832.54
5
2.30
0.30
968.133
5
0.88
4053.25
3
1.30
0.55
811.829
6
0.85
4620.43
0
0.00
0.20
924.361
8
0.81
4816.80
4
1.05
1.40
964.753
10
0.95
3650.25
2
0.55
0.10
730.805
11
0.91
4819.60
1
0.70
2.20
964.753Table 2
Weights of neighbors.
Ids
1
4
5
6
8
10
11
1
769.632
964.753
964.753
4
968.133
811.829
964.753
5
968.133
811.829
730.805
6
924.361
8
769.632
964.753
10
968.133
811.829
730.805
11
769.632
964.753Figure 6
Topology of the network.Figure 7
Identification of clusters node.Figure 8
The final identification of clusters.At the end of this example, we obtain a network of four clusters (as shown in Figure9).Figure 9
Final cluster structure (reaffiliation phase).There are five situations that require the maintenance of clusters:(i)
battery depletion of a node,(ii)
behavior level of a node less than or equal 0.3,(iii)
adding, moving, or deleting a node.In all of these cases, if a nodeni is CH then the setup phase will be repeated.


### 5.2.3. The Monitoring Phase

Monitoring in WSNs can be both local and global. The local monitoring can be with respect to a node and the global monitoring can be with respect to the network, but in sensor networks, for detecting some types of errors and security anomalies, the local monitoring would be insufficient [46]. For this reason, we adopt in this paper a hybrid approach that is global monitoring based on distributed local monitoring. The general architecture of our approach is illustrated in Figure 10. Our simulator, baptized “Mercury,” detects the internal misbehavior nodes during distributed monitoring process in WSNs by the follow-up of the messages exchanged between the nodes. We assume that the network has already a mechanism of prevention to avoid the external attacks. By using a set of rules, all the received messages are analyzed. A similar approach is used by da Silva et al. [45] and Benahmed et al. [21].Figure 10
Monitoring phase architecture.Algorithm 4  (monitoring phase algorithm). The monitoring process involves a series of steps as illustrated by the flowchart in (Figure 11).Figure 11
Monitoring phase.Step 1  (this step runs in each
C
H
i
). Each CHi becomes the monitor node of its cluster members and broadcasts a “Start Monitoring” message with its Idi to its entire cluster CMs.Step 2  (calculation of security metrics performed by each member
n
i
of the cluster
i
). Each node ni (i<>j) receives the message “Start Monitoring” and calculates its security metrics as follows.(i)
Number of packets sent byni at time interval is Δt=t0,t:Nbp_Send(ni,Δt).(ii)
Number of packets received by nodeni at time interval is Δt=t0,t0:Nbp_Received(ni,Δt).(iii)
Delay between the arrivals of two consecutive packets is(12)Delay_BPni,t=Arrival_PTi-Arrival_PTi-1.(iv)
Energy consumption: the energy consumed by the nodej in receiving and sending packets is measured using the following equation:(13)Ecni,Δt=Erni,t0-Erni,t1,where Δt is the time interval t0,t1;Er(ni,t0) is the residual energy of node ni at time t0; Er(ni,t1) is the residual energy of node ni at time t1and Ec(ni,Δt) is the energy consumption of node ni at time interval Δt.Step 3  (sending all metrics to the CH). After each consumption of the security metrics, the state of a node ni at time t is denoted by state (ni,ti). For storage volume economy, each node keeps only the latest calculation state.(i)
In the initial deployment, each CM in cluster “i” sends some states (state(ni,ti)) to the CHi for making a normal behavior model of node ni by using a learning mechanism.(ii)
Each state contains the following information:(14)Id,NbpSendni,Δt,NbpReceivedni,Δt,DelayBPni,t,Ecni,Δt.(iii)
If (state(ni,ti) − state (ni,ti-1) >ϵ)
then nodenisends a message (ϵ a given threshold):
Msg = (Id,NbpSendni,Δt, NbpReceivedni,Δt, DelayBPni,t, Ecni,Δt)to its CHi for monitoring purposes.Otherwise, no information is sent to the CH.(iv)
The message received by CHi will be stored in a table Tmet for future analysis.(v)
If a sensor nodeni does not respond during this monitoring period, it will be considered as misbehaving.(vi)
The behavior level of sensor nodeni is computed using the following equation:(15)BLi=BLi-rate.The “rate” is fixed on the basis of the nature of the application. For example, if it is fault tolerant or not. In our case, we took rate = 0.1.Step 4  (misbehavior detection, which is performed by CH
i
).(i)
For each nodeni in the cluster “i,” the state in time slot “t” is expressed by the three-dimensional vector:(16)S=St1,St2,St3,where
(a)
St1 is the number of packets dropped by ni, defined as follows:(17)St1=∑PsReceivedbyni-∑PsSentbyni-∑Psdestinedbyni,with(18)∑PsReceivedbyni=∑PsSentbyni+∑Psdestinedbyni+∑Pslostbyni.For a normal node,St1≈0.(b)
St2 is the delay between the arrival of two consecutive packets:(19)St2=Delay_BPni,t.(c)
St3 is the energy consumption:(20)St3=Ecni,Δt.Here,t∈[t0,t]=Δt.(ii)
In our case, the first interval is used for the training data set ofn time slots. We calculate the mean vector S- of S by using (21)S-=∑t=t0tn-1Stn.(iii)
After modeling a normal behavior model for each sensor node, the behaviors of all nodes are sent to the base station for further analysis. We then compute the deviationdS by using (22)dS=S-S-.(iv)
When the deviationd(S) is larger than threshold Th (which means that it is out of the range of normal behavior), it will be judged as a misbehaving node. In this case, the level of behavior is BLi≈0. This is called the punishing algorithm:(23)dS>Th:niisanabnormalnodedS≤Th:niIsanormalnode.The punishing algorithm is presented in Algorithm 3.Algorithm 3:Punishing algorithm.
Begin
(1)I≔0;
(2)I≔I+1;
(3)If ((I = Rate)  &&  (BLi<=0.1))
// Rate: parameter of maximum number of faults
defined by the administrator
BLi=BLi-Rate;
(4)// Classification of the node according to its BLi
(5)MpBLi=Normal node:0.8≤BLi≤1Abnormal node:0.5≤BLi<0.8Suspect node:0.3≤BLi<0.5Malicious node:0≤BLi<0.3
(6)If (BLi≤0.3) Then
(7)  If (ni is CM) Then
(8)Suppression of the node of the list of the members;
(9)Addition of the node to the blacklist;
EndIf
(10)If (ni is CH) Then    // CH: Cluster Head
(11) Addition of the node to the blacklist;
(12) Set up Phase;
EndIf
EndIf
EndIf
End.


## 5.2.1. The Setup Phase

ES-WCA uses three types of messages in the setup phase (Algorithm1). The message CHmsg is sent in the network by the sensor node which has the greatest weigh. The second one is the JOINmsg message which is sent by the neighbor of CH if it wants to join this cluster. Finally, a CH must send a response ACCEPTmsg message as shown in Figure 4.Algorithm 1:Algorithm setup phase.
Begin
(1)Assign values to the coefficients w1,w2,w3,w4,w5;
(2)For any node ni∈G  make:
(3)ni forms a list of its neighbors N(i) through the Message {who_are_neighbors};
(4)Ni=∅;
(5)Calculate its weight Pi:
(6)Pi=w1∗BLi+w2∗Eri+w3∗Mi+w4∗Ci+w5∗Di;
(7) Initialize Time Cluster and the state vector of all
nodes ni∈G Vector_State (Id, CH, Weight, List_Neighbors, Size, Nature)
(8) CH = 0, Size = 0;
(9) Nature = “None”;
(10) Repeat
(11)Any node ni∈G Broadcasts a message “Hello”;
(12)If  N(i)<>∅  Then
(13)Choose v∈N(i);
(14)Weightv=max⁡weightw/w∈Ni;
(15)the node that have thesame maximum weight, the CH is
the node that has the best criteria ordered by their
importance (
BL
i
, Eri, Ci,  Di  and  Mi) if all criteria of
nodes are equal, the choice is random.
(15)Else  ni is a CH of itself.
EndIf
(16)Update the state vector of the elected CH;
(17)CH = ID;
(18)Size = 1;
(19)Nature = CH;
(20)Send the message “CHmsg” by CH to its neighbors N(CH);
(21)J = Count (N(CH));
(22)For  I = 1 to J  Do
(23)If  (ni∈N(CH) receives the message && ni→ CH = 0)
(24)  Then  ni sends a message “JOINmsg” to CH
(25)If (CH → Size < ThreshUpper)
(26)  Then CH sends a message “ACCEPTmsg” to Node ni;
(27)    CH executes the accession process;
(28)    CH → Size = CH → Size + 1;
(29)    ni executes the accession process;
(30)    ni→ CH = CH → Id;
(31)    Else go to (10);
EndIf
EndIf
End For
(32)Until expired (TimeCluster);
End.Figure 4
Procedure of affiliation of node “U” to a cluster.The node which has the greatest weight begins the procedure by broadcasting CH message to their 1-hop neighbors to confirm its role as a leader of the cluster. The neighbors confirm their role as being member nodes by broadcasting a JOINmsg message. In the case when nodes have the same maximum weight, the CH is chosen by using the best parameters ordered by their importance. If all parameters of nodes are equal, the choice is random.


## 5.2.2. The Reaffiliation Phase

ES-WCA uses four types of messages in the reaffiliation phase (Algorithm2). The message RE_AFF_CH is sent in the network by the CH whose cluster size is less than ThreshUpper. The second one is the REQ_RE_AFF message which is sent by the neighbors of CH if it wants to join this cluster. Finally a CH must send a response ACCEPT_RE_AFF message or DROP_AFF message as illustrated by Figure 5. Accordingly, in this phase we propose to reaffiliate the sensor nodes belonging to clusters that have not attained the cluster size ThreshLower to those that did not achieve ThreshUpper in order to reduce the number of clusters formed and organize them so as to obtain homogeneous and balanced clusters.Algorithm 2:Algorithm reaffiliation phase.
Inputs:
T
h
r
e
s
h
U
p
p
e
r,ThreshLower;
Outputs: set of clusters
Begin
(1)For num_cl = 1 to Count (Cluster) Do
(2) If (Size (Cluster [num_cl]) < ThreshUpper)
Then
(3)  CH sends a message “RE_AFF_CH” to its neighbors
(N(CH));
(4)J = Count (N(CH));
EndIf
(5)For  I=1 to J  Do
(6) If (ni∈N(CH) receives the message)
&& (ni∈(Size (Cluster [num_cl]) < ThreshLower)
Then
(7)  ni sends a Select message “REQ_RE_AFF” to the CH;
(8) If (Size (Cluster [num_cl]) < ThreshUpper)
Then
(9)  CH sends a message “ACCEPT_RE_AFF” to ni;
(10)   CH updates its state vector;
(11)   CH → CH → Size = Size + 1;
(12)ni updates its state vector;
(13)ni → CH → ID = ID;
(14)Else CH sends a “FIN_AFF” message to ni;
(15)   Go to (2);
EndIF
(16)Else  ni sends a “DROP_AFF” message to CH;
EndIf
End For
End For
End.Figure 5
Procedure of reaffiliation of node “U” to a cluster.With the help of 3 figures (Figures6, 7, and 8), our algorithm setup phase is demonstrated. Table 1 shows the quantitative results of the different criteria applied on the normal nodes (BLi≥0.8). Table 2 shows the weights Pi of neighbors for each node which has behavior BLi higher than 0.8. The circles in Figure 6 represent the nodes, their identity Ids are at the top, and their levels of behavior are at the bottom. According to Table 2, node 1 could be attached to either CH11 or CH8 (since they have the same weight). However, the behavior level of node 11 is greater than that of node 8 (BL11>BL8). So, node 1 will be attached to CH11. For the other nodes, we have various conditions. Node 4 declares itself as a CH. Node 5 will be attached to CH4. Node 6 declares itself as a CH, because it is an isolated node. Node 8 will be attached to CH4. Node 10 is connected to CH5, but node 5 is attached to CH4. Thus, node 10 declares itself as a CH. Node 11 declares itself as a CH. These results give us the representation shown in Figure 7. Node 2 is connected to CH4 and CH10. Node 2 will be attached to CH4, because CH4 has the maximum weight (968.133). Node 3 is connected to CH4, which implies that node 3 will be attached to CH4. Node 7 is not connected to any CH, so node 7 declares itself as CH. Node 9 is connected to CH4, and then node 9 will be attached to CH4. Node 12 is not connected to any CH, which implies that node 12 declares itself as a CH. These results give us the representation shown in Figure 8. We propose to generate homogeneous clusters whose size lies between two thresholds: ThreshUpper=9 and ThreshLower=6. For that, we suggest to reaffiliate the sensor nodes belonging to the clusters that have not attained the cluster size ThreshLower to those that did not reach ThreshUpper. Node 4 has the highest weight and his size is less than ThreshUpper. Nodes 1, 7, and 10 are neighbors of node 4 with 2 hops and belong to the clusters that have not attained the cluster size ThreshLower, so these nodes get merged to cluster 2. Clusters 1, 3, and 4 will be homogeneous with cluster 1 when the network becomes densely.Table 1
Values of the various criteria of normal nodes.
Ids
BL
i
Er
i
C
i
D
i
M
i
P
i
1
0.86
3842.12
3
1.15
1.20
769.632
4
0.81
4832.54
5
2.30
0.30
968.133
5
0.88
4053.25
3
1.30
0.55
811.829
6
0.85
4620.43
0
0.00
0.20
924.361
8
0.81
4816.80
4
1.05
1.40
964.753
10
0.95
3650.25
2
0.55
0.10
730.805
11
0.91
4819.60
1
0.70
2.20
964.753Table 2
Weights of neighbors.
Ids
1
4
5
6
8
10
11
1
769.632
964.753
964.753
4
968.133
811.829
964.753
5
968.133
811.829
730.805
6
924.361
8
769.632
964.753
10
968.133
811.829
730.805
11
769.632
964.753Figure 6
Topology of the network.Figure 7
Identification of clusters node.Figure 8
The final identification of clusters.At the end of this example, we obtain a network of four clusters (as shown in Figure9).Figure 9
Final cluster structure (reaffiliation phase).There are five situations that require the maintenance of clusters:(i)
battery depletion of a node,(ii)
behavior level of a node less than or equal 0.3,(iii)
adding, moving, or deleting a node.In all of these cases, if a nodeni is CH then the setup phase will be repeated.


## 5.2.3. The Monitoring Phase

Monitoring in WSNs can be both local and global. The local monitoring can be with respect to a node and the global monitoring can be with respect to the network, but in sensor networks, for detecting some types of errors and security anomalies, the local monitoring would be insufficient [46]. For this reason, we adopt in this paper a hybrid approach that is global monitoring based on distributed local monitoring. The general architecture of our approach is illustrated in Figure 10. Our simulator, baptized “Mercury,” detects the internal misbehavior nodes during distributed monitoring process in WSNs by the follow-up of the messages exchanged between the nodes. We assume that the network has already a mechanism of prevention to avoid the external attacks. By using a set of rules, all the received messages are analyzed. A similar approach is used by da Silva et al. [45] and Benahmed et al. [21].Figure 10
Monitoring phase architecture.Algorithm 4  (monitoring phase algorithm). The monitoring process involves a series of steps as illustrated by the flowchart in (Figure 11).Figure 11
Monitoring phase.Step 1  (this step runs in each
C
H
i
). Each CHi becomes the monitor node of its cluster members and broadcasts a “Start Monitoring” message with its Idi to its entire cluster CMs.Step 2  (calculation of security metrics performed by each member
n
i
of the cluster
i
). Each node ni (i<>j) receives the message “Start Monitoring” and calculates its security metrics as follows.(i)
Number of packets sent byni at time interval is Δt=t0,t:Nbp_Send(ni,Δt).(ii)
Number of packets received by nodeni at time interval is Δt=t0,t0:Nbp_Received(ni,Δt).(iii)
Delay between the arrivals of two consecutive packets is(12)Delay_BPni,t=Arrival_PTi-Arrival_PTi-1.(iv)
Energy consumption: the energy consumed by the nodej in receiving and sending packets is measured using the following equation:(13)Ecni,Δt=Erni,t0-Erni,t1,where Δt is the time interval t0,t1;Er(ni,t0) is the residual energy of node ni at time t0; Er(ni,t1) is the residual energy of node ni at time t1and Ec(ni,Δt) is the energy consumption of node ni at time interval Δt.Step 3  (sending all metrics to the CH). After each consumption of the security metrics, the state of a node ni at time t is denoted by state (ni,ti). For storage volume economy, each node keeps only the latest calculation state.(i)
In the initial deployment, each CM in cluster “i” sends some states (state(ni,ti)) to the CHi for making a normal behavior model of node ni by using a learning mechanism.(ii)
Each state contains the following information:(14)Id,NbpSendni,Δt,NbpReceivedni,Δt,DelayBPni,t,Ecni,Δt.(iii)
If (state(ni,ti) − state (ni,ti-1) >ϵ)
then nodenisends a message (ϵ a given threshold):
Msg = (Id,NbpSendni,Δt, NbpReceivedni,Δt, DelayBPni,t, Ecni,Δt)to its CHi for monitoring purposes.Otherwise, no information is sent to the CH.(iv)
The message received by CHi will be stored in a table Tmet for future analysis.(v)
If a sensor nodeni does not respond during this monitoring period, it will be considered as misbehaving.(vi)
The behavior level of sensor nodeni is computed using the following equation:(15)BLi=BLi-rate.The “rate” is fixed on the basis of the nature of the application. For example, if it is fault tolerant or not. In our case, we took rate = 0.1.Step 4  (misbehavior detection, which is performed by CH
i
).(i)
For each nodeni in the cluster “i,” the state in time slot “t” is expressed by the three-dimensional vector:(16)S=St1,St2,St3,where
(a)
St1 is the number of packets dropped by ni, defined as follows:(17)St1=∑PsReceivedbyni-∑PsSentbyni-∑Psdestinedbyni,with(18)∑PsReceivedbyni=∑PsSentbyni+∑Psdestinedbyni+∑Pslostbyni.For a normal node,St1≈0.(b)
St2 is the delay between the arrival of two consecutive packets:(19)St2=Delay_BPni,t.(c)
St3 is the energy consumption:(20)St3=Ecni,Δt.Here,t∈[t0,t]=Δt.(ii)
In our case, the first interval is used for the training data set ofn time slots. We calculate the mean vector S- of S by using (21)S-=∑t=t0tn-1Stn.(iii)
After modeling a normal behavior model for each sensor node, the behaviors of all nodes are sent to the base station for further analysis. We then compute the deviationdS by using (22)dS=S-S-.(iv)
When the deviationd(S) is larger than threshold Th (which means that it is out of the range of normal behavior), it will be judged as a misbehaving node. In this case, the level of behavior is BLi≈0. This is called the punishing algorithm:(23)dS>Th:niisanabnormalnodedS≤Th:niIsanormalnode.The punishing algorithm is presented in Algorithm 3.Algorithm 3:Punishing algorithm.
Begin
(1)I≔0;
(2)I≔I+1;
(3)If ((I = Rate)  &&  (BLi<=0.1))
// Rate: parameter of maximum number of faults
defined by the administrator
BLi=BLi-Rate;
(4)// Classification of the node according to its BLi
(5)MpBLi=Normal node:0.8≤BLi≤1Abnormal node:0.5≤BLi<0.8Suspect node:0.3≤BLi<0.5Malicious node:0≤BLi<0.3
(6)If (BLi≤0.3) Then
(7)  If (ni is CM) Then
(8)Suppression of the node of the list of the members;
(9)Addition of the node to the blacklist;
EndIf
(10)If (ni is CH) Then    // CH: Cluster Head
(11) Addition of the node to the blacklist;
(12) Set up Phase;
EndIf
EndIf
EndIf
End.


## 6. Simulation Results

This section presents the implementation of the proposed approach using the Borland C++ language and the analysis of the obtained results.


### 6.1. The Simulator “Mercury”

We try to complete the theoretical study by implementing our own wireless sensor network simulator “Mercury.” On the other hand, a bit of simulators for WSNs such as TOSSIM [47] and Power-TOSSIM [48] are irrelevant with our goal and purpose and in order to avoid many complications we established our own mercury simulator. It is established on an object-oriented design and a distributed approach such as self-organization mechanism which is distributed at the level of each sensor; it provides a set of interfaces for configuring a simulation and for choosing the type of event scheduler used to drive the simulation. A simulation script generally begins by creating an instance of this class and calling various methods to create nodes and topologies and configure other aspects of the simulation. Mercury uses two routing protocols for delivering data from sensor nodes to the Sink station: a reactive protocol AODV (ad hoc on demand distance vector) [5] and a proactive protocol DSDV (destination sequenced distance vector) [6]. To determine and evaluate the results of the execution of algorithms that are introduced previously; the number of sensors to deploy must be inferior or equal to 1000. There are two types of sensor nodes deployment on the sensor field: random and manual. Mercury offers users the ability to select a sensor type from 5 types of existing sensor, each of them has its proper characteristics (radius, energy, etc.). Unity of the energy used is as Nanojoules: (1 Joule = 109 NJ). Mobility has influence on energy and the behavior of sensors; for instance, if the sensor moves one meter away from its original location, its energy will diminish by 100,000 NJ and its behavior will also decrease by 0.001 units. This allows users to differentiate a malicious node (that moves frequently) of a legitimate node (that can changes position with reasonable distances). Since sensors nodes move due to the forces acting from the outside, no power consumption for mobility must be taken into consideration in all simulations that we have carried for evaluation [4].


### 6.2. Discussion and Results

To evaluate our ES-WCA algorithm, we have performed extensive simulation experiments. This section provides our experimental results and discussions. In all the experiments,N varies between 10 and 1000 sensor nodes. The transmission range (R) varies between 10 and 175 meters (m) and the used energy (E) is equal to 50000 NJ. The sensor nodes are randomly distributed in a “570 m × 555 m” space area by the following function:for(intn=0;n<node_tobe_deployed;n++).
{hhhhhhhhhhX_=rand⁡()%image_Field_Of_Collecting→width;Y_=rand()%image_Field_Of_Collecting→Height;}hhhhhhhhhhThe performance of the proposed ES-WCA algorithm is measured by calculating (i) the number of clusters, (ii) number of reaffiliations, (iii) choice of ES-WCA with AODV or DSDV, and (iiii) detection of misbehavior nodes and the nature of attacks during the distributed monitoring process.In our experiments, the values of weighting factors used in the weight calculation are as follows:w1 = 0.3, w2 = 0.2, w3 = 0.2, w4= 0.2, and w5 = 0.1. It is noted that these values are arbitrary at this time and for this reason they should be adjusted according to the system requirements. To evaluate the performance of the proposed ES-WCA algorithm by comparing it with alternative solutions, we studied the effect of the density of the networks (number of sensor nodes in a given area) and the transmission range on the average number of formed clusters. Then we compared it with a WCA proposed in [3], DWCA proposed in [9], and SDCA proposed in [21].Figure12 illustrates the variation of the average number of clusters with respect to the transmission range. The results are shown for N which varies between 200 and 1000. We found that there is opposite relationship between clusters and transmission range. This is on the grounds that a cluster head with a considerable transmission range will cover a large area.Figure 12
Average number of clusters versus transmission range (R).Figure13 depicts the average number of clusters that are formed with respect to the total number of nodes in the network. The communication range used in this experiment is 200 m. From Figure 13, it is seen that ES-WCA consistently provides about 61.91% less clusters than DWCA and about 38.46% than SDCA, when there were 100 nodes in the network. When the node number is equal to 20 nodes, the performance of ES-WCA is similar to DWCA in terms of number of clusters; however, if the node density had increased, ES-WCA would have produced constantly less clusters than SDCA and DWCA, respectively, regardless of the node number. Because of the use of a random deployment, the result of ES-WCA is unstable between 60 and 90. So, the increase in the number of clusters depends on the increase of the distance between the nodes. As a result, our algorithm gave better performance in terms of the number of clusters when the node density in the network is high, and this is due to the fact that ES-WCA generates a reduced number of balanced and homogeneous clusters, whose size lies between two thresholds: ThreshUpper and ThreshLower (reaffiliation phase) in order to minimize the energy consumption of the entire network and prolong sensors lifetime.Figure 13
Average number of clusters versus number nodes (N) for ES-WCA, DWCA, and SDCA.Figure14 shows the variation of the average number of clusters with respect to the transmission range. The results are shown for varying N. We notice an inverse relationship, and the average number of clusters decreases with the increase in the transmission range. As shown in Figure 14, the proposed algorithm produced 16% to 35% fewer clusters than WCA [3] when the transmission range of nodes was 10 m. When the node density increased, ES-WCA constantly produced less clusters than WCA regardless of the node number. With 70 nodes in the network, the proposed algorithm produced about 47% to 73% less clusters than WCA. The results show that our algorithm gave a better performance in terms of the number of clusters when the node density and transmission range in the network are high.Figure 14
Average number of clusters versus transmission range ES-WCA and WCA.Figure15 interprets the average number of reaffiliations that are established with esteem to the total number of nodes in the network. The number of reaffiliations incremented linearly when there were 30 or more nodes in the network for both WCA and DWCA. But for our algorithm, the number of reaffiliations increased starting from 50 nodes. We submit to engender homogeneous clusters whose size is between two thresholds: ThreshUpper=18 and ThreshLower=9. According to the results, our algorithm presented a better performance in terms of the number of reaffiliations. The benefit of decreasing the number of reaffiliations mainly comes from the localized reaffiliation phase in our algorithm. The result of the remaining amount of energy per node for each protocol AODV and DSDV is presented in Figure 16 such as R equal to 35 m. As shown in the above-mentioned figure, the remaining energy for each node in AODV protocol is greater than that in DSDV protocol such as AODV which consumes 22, 74% less than DSDV. According to the results, the network consumes 19, 23% of the total energy when we use an AODV protocol (192322.091 NJ). However, it consumes 41, 97% with a DSDV protocol (419740.129 NJ). We also observe that the network lost 6 nodes with DSDV but only one node with AODV because of the depletion of its battery. This result clearly shows that AODV outperforms DSDV. This is due to the tremendous overhead incurred by DSDV when exchanging routing tables and the periodic exchange of the routing control packets. So, our algorithm gave a better performance in terms of saving energy when it is coupled with AODV.Figure 15
Average number of reaffiliations.Figure 16
Remaining energy per node using ES-WCA.We consider that the network will be inoperative when the nodes of the neighborhood of the sink exhaust their energy as exemplified. In Figure17, we appraise the network lifetime by changing the number of nodes such as R equal to 70 m. When there were 20 nodes in the network, AODV increases the network period about 88, 47% compared to DSDV and about 57,9% for N=100. Also, this is for the reason that in a DSDV protocol each node must have a global view of the network. This in turn raises the number of the exchanged control packets (overhead) in the full network and it decreases the residual energy of each node which has a direct effect on the network lifetime. There are 9 nodes in an active state but the network is inoperative. We discover that the increase in the total of nodes does not have a powerful factor on the network lifetime except between N=60 and N=80.Figure 17
Network lifetime depending on number of nodes using ES-WCA.To illustrate the effect of abnormal behavior in the network, in our experiments we propagated 200 nodes with 5 malicious nodes. The cases of the malicious nodes will pass from a normal node with a yellow color to an abnormal node with a blue color, to a suspicious node with a grey color, and lastly, to a malicious node with a black color. All the cases of the CMs are discovered by their CH. Malicious CHs are disclosed by the base station.Figure18(b) displays the total of clusters established according to the transmission range. Figures 19(a), 19(b), and 19(c) display the measure results for a scenario with malicious nodes which are achieved by the generator of bad behavior. The generated attacks are explained in Section 3. We can identify that these nodes migrate from a normal case to an abnormal or suspicious state and finally to a malicious state as expected. Table 3 presents the Ids of malicious nodes and their categories of attacks in the course of the dissemination of a monitoring mechanism in the network by the follow-up of the messages exchanged between the nodes. When Packets_sent N1,N2, Packets_received N3,N4. Thus, N1 is the total of packets sent before attacks, and N2 is the total of packets sent after attacks, while N3 is the total of packets received before attacks and N4 is the total of packets received after attacks. We regard that these malicious nodes increment N1, as the sensors (71, 181), reduce N1, like the sensor 190, increment N3, as the sensor (162), and lastly break sending data like node 41. From Figure 20 it is observed that the sensor nodes (3, 17) are malicious and have a behavior level less than 0.3, its behavior decreased by 0.1 units, and when the monitor (CH) counts one failure an alarm is raised. However, packets from malicious nodes are not processed and no packet will be forwarded to them. The sensor node 11 has the behavior level less then threshold behavior so it will not be accepted as a CH candidate even if it has the other interesting characteristics (Eri,Ci, Di, and Mi). On the other side the behavior level in Figure 21 decreased by 0.001 units in our first work [4] when the malicious node moves frequently. We note that sensor (6) is suspicious so if it continues to move frequently its behavior will gradually be decreased until it reaches the malicious state; in this case this node will be deleted from the neighborhood and finally it will be added to the black list.Table 3
Detection of the nature of attacks.
IDs
Packets_Sent
Packets_Received
Attack
41
(19, 13)
(16, 14)
Node Outage
71
(24, 152)
(20, 34)
Hello Flood
162
(15, 8)
(22, 112)
Sinkhole
181
(16, 179)
(26, 42)
Hello Flood
190
(58, 32)
(50, 51)
Black HoleFigure 18
(a) Graph connectivity of 200 nodes. (b) Network after clustering formation.
(a)
(b)Figure 19
(a) Sensors with a blue color are abnormal but not malicious. (b) The grey sensors have a suspect behavior. (c) The sensors with a black color are compromised and are exhibiting malicious behavior.
(a)
(b)
(c)Figure 20
Behavior level of some sensors (moves frequently).Figure 21
Behavior level of some sensors before and after attacks.


## 6.1. The Simulator “Mercury”

We try to complete the theoretical study by implementing our own wireless sensor network simulator “Mercury.” On the other hand, a bit of simulators for WSNs such as TOSSIM [47] and Power-TOSSIM [48] are irrelevant with our goal and purpose and in order to avoid many complications we established our own mercury simulator. It is established on an object-oriented design and a distributed approach such as self-organization mechanism which is distributed at the level of each sensor; it provides a set of interfaces for configuring a simulation and for choosing the type of event scheduler used to drive the simulation. A simulation script generally begins by creating an instance of this class and calling various methods to create nodes and topologies and configure other aspects of the simulation. Mercury uses two routing protocols for delivering data from sensor nodes to the Sink station: a reactive protocol AODV (ad hoc on demand distance vector) [5] and a proactive protocol DSDV (destination sequenced distance vector) [6]. To determine and evaluate the results of the execution of algorithms that are introduced previously; the number of sensors to deploy must be inferior or equal to 1000. There are two types of sensor nodes deployment on the sensor field: random and manual. Mercury offers users the ability to select a sensor type from 5 types of existing sensor, each of them has its proper characteristics (radius, energy, etc.). Unity of the energy used is as Nanojoules: (1 Joule = 109 NJ). Mobility has influence on energy and the behavior of sensors; for instance, if the sensor moves one meter away from its original location, its energy will diminish by 100,000 NJ and its behavior will also decrease by 0.001 units. This allows users to differentiate a malicious node (that moves frequently) of a legitimate node (that can changes position with reasonable distances). Since sensors nodes move due to the forces acting from the outside, no power consumption for mobility must be taken into consideration in all simulations that we have carried for evaluation [4].


## 6.2. Discussion and Results

To evaluate our ES-WCA algorithm, we have performed extensive simulation experiments. This section provides our experimental results and discussions. In all the experiments,N varies between 10 and 1000 sensor nodes. The transmission range (R) varies between 10 and 175 meters (m) and the used energy (E) is equal to 50000 NJ. The sensor nodes are randomly distributed in a “570 m × 555 m” space area by the following function:for(intn=0;n<node_tobe_deployed;n++).
{hhhhhhhhhhX_=rand⁡()%image_Field_Of_Collecting→width;Y_=rand()%image_Field_Of_Collecting→Height;}hhhhhhhhhhThe performance of the proposed ES-WCA algorithm is measured by calculating (i) the number of clusters, (ii) number of reaffiliations, (iii) choice of ES-WCA with AODV or DSDV, and (iiii) detection of misbehavior nodes and the nature of attacks during the distributed monitoring process.In our experiments, the values of weighting factors used in the weight calculation are as follows:w1 = 0.3, w2 = 0.2, w3 = 0.2, w4= 0.2, and w5 = 0.1. It is noted that these values are arbitrary at this time and for this reason they should be adjusted according to the system requirements. To evaluate the performance of the proposed ES-WCA algorithm by comparing it with alternative solutions, we studied the effect of the density of the networks (number of sensor nodes in a given area) and the transmission range on the average number of formed clusters. Then we compared it with a WCA proposed in [3], DWCA proposed in [9], and SDCA proposed in [21].Figure12 illustrates the variation of the average number of clusters with respect to the transmission range. The results are shown for N which varies between 200 and 1000. We found that there is opposite relationship between clusters and transmission range. This is on the grounds that a cluster head with a considerable transmission range will cover a large area.Figure 12
Average number of clusters versus transmission range (R).Figure13 depicts the average number of clusters that are formed with respect to the total number of nodes in the network. The communication range used in this experiment is 200 m. From Figure 13, it is seen that ES-WCA consistently provides about 61.91% less clusters than DWCA and about 38.46% than SDCA, when there were 100 nodes in the network. When the node number is equal to 20 nodes, the performance of ES-WCA is similar to DWCA in terms of number of clusters; however, if the node density had increased, ES-WCA would have produced constantly less clusters than SDCA and DWCA, respectively, regardless of the node number. Because of the use of a random deployment, the result of ES-WCA is unstable between 60 and 90. So, the increase in the number of clusters depends on the increase of the distance between the nodes. As a result, our algorithm gave better performance in terms of the number of clusters when the node density in the network is high, and this is due to the fact that ES-WCA generates a reduced number of balanced and homogeneous clusters, whose size lies between two thresholds: ThreshUpper and ThreshLower (reaffiliation phase) in order to minimize the energy consumption of the entire network and prolong sensors lifetime.Figure 13
Average number of clusters versus number nodes (N) for ES-WCA, DWCA, and SDCA.Figure14 shows the variation of the average number of clusters with respect to the transmission range. The results are shown for varying N. We notice an inverse relationship, and the average number of clusters decreases with the increase in the transmission range. As shown in Figure 14, the proposed algorithm produced 16% to 35% fewer clusters than WCA [3] when the transmission range of nodes was 10 m. When the node density increased, ES-WCA constantly produced less clusters than WCA regardless of the node number. With 70 nodes in the network, the proposed algorithm produced about 47% to 73% less clusters than WCA. The results show that our algorithm gave a better performance in terms of the number of clusters when the node density and transmission range in the network are high.Figure 14
Average number of clusters versus transmission range ES-WCA and WCA.Figure15 interprets the average number of reaffiliations that are established with esteem to the total number of nodes in the network. The number of reaffiliations incremented linearly when there were 30 or more nodes in the network for both WCA and DWCA. But for our algorithm, the number of reaffiliations increased starting from 50 nodes. We submit to engender homogeneous clusters whose size is between two thresholds: ThreshUpper=18 and ThreshLower=9. According to the results, our algorithm presented a better performance in terms of the number of reaffiliations. The benefit of decreasing the number of reaffiliations mainly comes from the localized reaffiliation phase in our algorithm. The result of the remaining amount of energy per node for each protocol AODV and DSDV is presented in Figure 16 such as R equal to 35 m. As shown in the above-mentioned figure, the remaining energy for each node in AODV protocol is greater than that in DSDV protocol such as AODV which consumes 22, 74% less than DSDV. According to the results, the network consumes 19, 23% of the total energy when we use an AODV protocol (192322.091 NJ). However, it consumes 41, 97% with a DSDV protocol (419740.129 NJ). We also observe that the network lost 6 nodes with DSDV but only one node with AODV because of the depletion of its battery. This result clearly shows that AODV outperforms DSDV. This is due to the tremendous overhead incurred by DSDV when exchanging routing tables and the periodic exchange of the routing control packets. So, our algorithm gave a better performance in terms of saving energy when it is coupled with AODV.Figure 15
Average number of reaffiliations.Figure 16
Remaining energy per node using ES-WCA.We consider that the network will be inoperative when the nodes of the neighborhood of the sink exhaust their energy as exemplified. In Figure17, we appraise the network lifetime by changing the number of nodes such as R equal to 70 m. When there were 20 nodes in the network, AODV increases the network period about 88, 47% compared to DSDV and about 57,9% for N=100. Also, this is for the reason that in a DSDV protocol each node must have a global view of the network. This in turn raises the number of the exchanged control packets (overhead) in the full network and it decreases the residual energy of each node which has a direct effect on the network lifetime. There are 9 nodes in an active state but the network is inoperative. We discover that the increase in the total of nodes does not have a powerful factor on the network lifetime except between N=60 and N=80.Figure 17
Network lifetime depending on number of nodes using ES-WCA.To illustrate the effect of abnormal behavior in the network, in our experiments we propagated 200 nodes with 5 malicious nodes. The cases of the malicious nodes will pass from a normal node with a yellow color to an abnormal node with a blue color, to a suspicious node with a grey color, and lastly, to a malicious node with a black color. All the cases of the CMs are discovered by their CH. Malicious CHs are disclosed by the base station.Figure18(b) displays the total of clusters established according to the transmission range. Figures 19(a), 19(b), and 19(c) display the measure results for a scenario with malicious nodes which are achieved by the generator of bad behavior. The generated attacks are explained in Section 3. We can identify that these nodes migrate from a normal case to an abnormal or suspicious state and finally to a malicious state as expected. Table 3 presents the Ids of malicious nodes and their categories of attacks in the course of the dissemination of a monitoring mechanism in the network by the follow-up of the messages exchanged between the nodes. When Packets_sent N1,N2, Packets_received N3,N4. Thus, N1 is the total of packets sent before attacks, and N2 is the total of packets sent after attacks, while N3 is the total of packets received before attacks and N4 is the total of packets received after attacks. We regard that these malicious nodes increment N1, as the sensors (71, 181), reduce N1, like the sensor 190, increment N3, as the sensor (162), and lastly break sending data like node 41. From Figure 20 it is observed that the sensor nodes (3, 17) are malicious and have a behavior level less than 0.3, its behavior decreased by 0.1 units, and when the monitor (CH) counts one failure an alarm is raised. However, packets from malicious nodes are not processed and no packet will be forwarded to them. The sensor node 11 has the behavior level less then threshold behavior so it will not be accepted as a CH candidate even if it has the other interesting characteristics (Eri,Ci, Di, and Mi). On the other side the behavior level in Figure 21 decreased by 0.001 units in our first work [4] when the malicious node moves frequently. We note that sensor (6) is suspicious so if it continues to move frequently its behavior will gradually be decreased until it reaches the malicious state; in this case this node will be deleted from the neighborhood and finally it will be added to the black list.Table 3
Detection of the nature of attacks.
IDs
Packets_Sent
Packets_Received
Attack
41
(19, 13)
(16, 14)
Node Outage
71
(24, 152)
(20, 34)
Hello Flood
162
(15, 8)
(22, 112)
Sinkhole
181
(16, 179)
(26, 42)
Hello Flood
190
(58, 32)
(50, 51)
Black HoleFigure 18
(a) Graph connectivity of 200 nodes. (b) Network after clustering formation.
(a)
(b)Figure 19
(a) Sensors with a blue color are abnormal but not malicious. (b) The grey sensors have a suspect behavior. (c) The sensors with a black color are compromised and are exhibiting malicious behavior.
(a)
(b)
(c)Figure 20
Behavior level of some sensors (moves frequently).Figure 21
Behavior level of some sensors before and after attacks.


## 7. Conclusion and Future Works

In this paper, we have presented a new algorithm called “ES-WCA” for promoting the self-organization of mobile sensor networks. This algorithm is fully decentralized and aims at creating a virtual topology with the purpose to minimize frequent reelection of the cluster head (CH) and avoid overall restructuring of the entire network. Simulations result attest of the outperformance of our algorithm compared to WCA and DWCA in every sense. It yields a low number of clusters and it preserves the network structure better than WCA and DWCA by reducing the number of reaffiliations. The proposed algorithm selects the most robust and safe CHs with the responsibility of monitoring the nodes in their clusters and maintaining clusters locally. Our third algorithm analyses and detects specific misbehavior in the WSNs. The results show that in scenarios in which mobile WSNs are with a low density or with a small size, the choice of ES-WCA with AODV is comparable to ES-WCA with DSDV to show clearly the interest of the routing protocols in energy saving. However, the difference in favor between ES-WCA and AODV becomes very important in case of a high node density. This is due to the tremendous overheads incurred by ES-WCA with DSDV when exchanging routing tables and exchanging routing control packets. Future work includes considering further the concept of redundancy by using the “sleep” and “wakeup” mechanism in case of node failure, providing in-network processing by aggregating correlated data in order to reduce both the energy consumption and the congestion issue.



---

*Source: 475030-2015-10-04.xml*