Reputation-based cluster head elections in wireless sensor networks

1. Introduction

The cluster structure is frequently employed in wireless sensor networks for energy savings,^1,2 load balancing, ³ distributed key management,^4,5 and so on. Generally, the cluster structure is generated by transforming a physical network into groups of adjacent nodes. These groups are called clusters and they are generated by a cluster formation protocol. If a leader is needed in a cluster, the nodes in the cluster should determine which node is best suited for the leader. The leader is called the cluster head (hereafter CH) and the protocol that determines the CH node in a cluster is called the CH election protocol. CHs collect data from other nodes and aggregate the data for delivery to the sink. Because attackers can manipulate the whole network by compromising all CHs, they will undoubtedly try to do so. Therefore, CHs should be changed as frequently as possible and a CH election protocol should be invoked periodically to achieve this. In addition, a CH election protocol should prevent compromised nodes from becoming CHs.

There are two main strategies for preventing attackers from becoming CHs. The first strategy is to prevent attackers from participating in the formation of initial clusters. If an attacker can freely participate in the formation of initial clusters, the attacker is considered a normal node. Later, the attacker can attack the CH election protocol for its benefit. Therefore, we need to eliminate as many attackers as possible during the cluster formation process. The issue concerning secure cluster formation is beyond the scope of this paper but is covered by Liu, ⁶ Sun et al., ⁷ and Rifà-Pous and Herrera-Joancomartí. ⁸ The second strategy is to prevent compromised nodes in each cluster from manipulating CH election results and facilitating their win in the elections. To achieve this goal, some properties such as unpredictability, non-manipulability, and agreement should be guaranteed in CH election results. The protocols in Buttyan and Holczer, ⁹ Sirivianos et al., ¹⁰ Dong and Liu ¹¹ satisfy the above properties under an environment where only naive attackers exist. However, intelligent attackers can easily violate the above properties and fabricate the CH election results for their own benefit. Furthermore, the protocols do not work well in an environment where message losses occur.

In this paper, we introduce a novel CH election scheme that can deal with the misbehavior of intelligent attackers. In our approach, each CH candidate contributes their random number towards generating a common value and the common value is employed for CH election. During the contribution process, an intelligent attacker may refuse its contribution or perform a partial contribution to change or split the election result. After the contribution, each CH candidate gives direct reputation values to other candidates according to their behavior during the CH election process and distributes the direct reputation list for other candidates. When each candidate gives a direct reputation value to another candidate, it considers the frequencies of successful and unsuccessful transmissions, the time interval between the last two successful transmissions, and the time interval between the last two unsuccessful transmissions. The more a node’s transmission succeeds, the higher the direct reputation value given to the node will be. The shorter a node’s time interval between the last two successful transmissions is, the higher the direct reputation value given to the node will be. Therefore, the direct reputation value of normal nodes is likely to be higher than that of malicious nodes. After receiving the direct reputation lists from all candidates, each candidate can compute indirect reputation values and combined reputation lists for all candidates. Since each candidate maintains the direct reputation lists as the number of members, the combined reputation lists are also generated as the number of members. Each candidate extracts the real reputation list where each item is the average of the combined reputation values. Each candidate can exclude some other candidates whose real reputation value is lower than the average of the real reputation list. Because the internal attackers are likely to be given a low reputation value, they are prone to be excluded from the CH candidates unless they take special actions. So, the internal attackers maximize their real reputation value and minimize the real reputation values of normal nodes to survive the reputation-based exclusion. However, the tactics cannot cause any significant effect to our scheme as long as the majority of nodes are normal. Besides, our approach allows the nodes that are excluded from the current CH election to participate in later CH elections in order to flexibly cope with message losses.

This paper is organized as follows. In Section 2, we review some related work covering secure cluster formation and secure CH election. Next, we describe the network and the threat model of our scheme in Section 3. We then provide the detailed description of our scheme in Section 4. Section 5 provides the background concerning simulation and modeling for wireless sensor networks. Section 6 compares our scheme with other rival schemes through simulation results and presents the comparison of the control overhead and the qualitative comparison. Section 7 discusses the method for avoiding collisions during the election process. Finally, we draw conclusions in Section 8.

2. Related work

Heinzelman et al. ¹ proposed LEACH (Low-energy Adaptive Clustering Hierarchy) where sensors declare themselves as a CH in line with a probability of being a CH. Since CHs deplete their energy resource faster than normal nodes, they are likely to die earlier than normal nodes. This scheme attempts to extend their lifetime by rotating the CH roles among all nodes; this extends the network lifetime as a whole. In this scheme, if some nodes have a higher probability than the threshold, they become CHs, and otherwise nodes join in one of them. However, this scheme has no measure to protect the cluster formation.

F-LEACH protects the cluster formation of LEACH. ¹² In F-LEACH, if a node declares itself as a CH using common keys shared with the sink, the sink authenticates the node by decrypting the declaration message with the same keys. If the authentication succeeds, the sink broadcasts the authenticated CHs using µTESLA. ¹³ Normal nodes join one of the authenticated CHs. However, since this scheme does not authenticate the join of the normal nodes, a malicious node can become a cluster member freely. To deal with this problem, Oliveira et al. ¹⁴ proposed SecLEACH, where the sink authenticates the CHs and the CHs authenticate the join of normal nodes. F-LEACH and SecLEACH assume that some keys for the authentication are assigned to sensor nodes prior to their deployment. Both F-LEACH and SecLEACH can only keep external attackers from joining the cluster formation. In other words, they have no mechanism to prevent compromised nodes from declaring themselves as CHs or from joining in any cluster.

Liu ⁶ proposed a cluster formation scheme that employs pre-assigned polynomial shares to authenticate any CH declaration and any cluster join. For cluster formation, predetermined nodes declare themselves as CHs and other nodes join in any cluster directly or via a relay node. Because an external attacker has no polynomial shares, it cannot participate in the cluster formation. In the scheme, a normal node with many neighbors shuts itself down and a malicious node with many neighbors is reported to the sink to prevent wormhole attacks. Then, the sink expels the malicious node from the network by propagating the authenticated blacklist report. However, if an attacker compromises a relay node, the relay node can cut off the connection between its CH and serving nodes. Furthermore, attackers are going to compromise predetermined CHs because their roles are static.

A secure cluster formation scheme that checks the protocol conformity of nodes and excludes the nodes deviating from the protocol was proposed by Sun et al. ⁷ Firstly, the network is divided into cliques whose members are directly connected with each other. In a clique, each node checks that all nodes in the clique have the same clique membership. If a normal node finds any disagreement, it checks the protocol conformity of other nodes to determine which node is to blame for the disagreement. The scheme employs public key cryptography and µTESLA to recognize and remove non-conforming nodes during the conformity checking process. However, the scheme increases the number of clusters because it only deals with cliques and separates the cliques whenever it detects a suspicious node in the conformity checking process. Moreover, it induces a lot of communication overhead because it requires a lot of unicast transmissions between nodes during the conformity checking process.

Rifà-Pous and Herrera-Joancomartí ⁸ proposed a secure cluster formation scheme that is based on public key cryptography. The scheme forms clusters through three phases: the cluster discovery phase, CH designation phase, and cluster maintenance phase. In the cluster discovery phase, nodes in a cluster agree on the cluster membership with each other. In the cluster discovery phase, a CH is elected among nodes considering the number of neighbors and the frequency of CH role fulfillment. In the cluster maintenance phase, the elected CHs act as a local CA (Certification Authority) by issuing an authorization certificate to each node. However, this scheme assumes that all nodes never deviate from the cluster discovery protocol. For instance, if an attacker transmits its message to a part of all nodes in the cluster discovery phase, the agreement in the cluster membership is broken. It splits a cluster into multiple ones, and the split clusters elect their CH respectively in the CH designation phase. Thus, this scheme can generate many clusters under the selective transmission attack.

Crosby and Pissinou ¹⁵ proposed a CH election scheme where each node gives a reputation value to other nodes in line with their behavior. A node’s behavior is judged by other nodes counting how many times the node successfully transmits packets and how many times the node avoids the transmissions in the cluster. The more frequently a node succeeds its transmission, the higher the reputation value given to the node is. When a new CH should be elected, some nodes with a high reputation value are recommended for the CH role by members and one of them is selected as a new CH by the current CH. Because the current CH not only selects a new CH but also makes a blacklist to distribute it to other members, a compromised CH can make a blacklist that contains innocent victims. If a node is included in the blacklist, it loses its candidacy for CH in the cluster. Therefore, as the number of innocent victims increases, the probability that a compromised node is selected as a CH becomes higher due to the increasing ratio of compromised nodes to candidates.

Buttyan and Holczer ⁹ proposed a CH election scheme that hides the election process from external nodes through message encryption and decryption. However, even though external nodes cannot know which node is selected as the CH, a compromised node can easily reveal the selection result. Moreover, the compromised node can declare itself as a CH regardless of its qualification.

Sirivianos et al. ¹⁰ proposed the SANE (Secure Aggregator Node Election) protocol where all CH candidates contribute to the generation of a common value that is used for the CH election. SANE is divided into three sub-schemes in accordance with how to generate and distribute the common value. They are a Merkle’s puzzle-based scheme, commitment-based scheme, and seed-based scheme.

In Merkle’s puzzle-based scheme, the current CH establishes pairwise keys with its members. Then, each member generates a random value and encrypts it using the pairwise key shared with the current CH. Each member adds the encrypted random value to the sum that was delivered from a member and passes the sum to another member. This add and pass procedure is repeated until all members contribute to the sum accumulation. The last contributor node distributes the accumulated sum to all members and the current CH distributes all pairwise keys shared with members to all members in the cluster. All nodes can convert the accumulated sum into a plain sum of random numbers using the pairwise keys. The plain sum of random numbers is employed as a common value for CH election.

In the commitment-based scheme, each member sends its commitment to other members in a peer-to-peer (P2P) manner. For every CH election round, each member generates a random value and encrypts it with a shared key to send to all members. Next, each member sends the original random value to other members. Receiving members verify the random values using the shared key and sum them to make an agreed common value.

In the seed-based scheme, each member generates its seed value and distributes it to other members in a broadcasting manner. The seed value is an initial random value that is employed to generate a new random value in every CH election round. For every CH election round, each member broadcasts an availability message. The availability message represents the sender’s explicit will to participate in the CH election. Members receiving the message store the sender and generate a new random number of the sender using the sender’s seed and the number of election rounds. After receiving all availability messages, all members can store the list of the senders and the sum of the new random numbers, which is employed as a common value.

Merkle’s puzzle-based scheme causes a lot of communication and computation overheads for generating and distributing the common value. Even though the commitment-based scheme and the seed-based scheme induce lower overheads than Merkle’s puzzle-based scheme, they have a common problem. That is, the last node that contributes to the generation of the common value can predict and manipulate a CH election result and even collapse the agreement property of the CH election result.

Dong et al. ¹¹ proposed a CH election scheme that strongly prevents external attackers from joining in CH elections through their ID assignment scheme, which tightly couples a node’s ID, its commitments, and its polynomial shares. In this scheme, nodes that do not distribute a participation message for CH election (that is, the current key in their key chain) or explicitly distribute a non-participation message are excluded from the CH candidates. The real CH is selected by randomly picking one node from the rest of the candidates. This scheme is vulnerable to an intelligent attack by internal attackers, while it has a strong countermeasure against external attackers. That is, an internal attacker can readily change a CH election result by avoiding distribution of its participation message. The attacker can also generate multiple CH election results by distributing its participation message to a subset of CH candidates. Although this scheme has a recovery algorithm for combining multiple election results into one result, it requires the voluntary cooperation of the CH candidates with the algorithm. However, because this algorithm goes against the interests of attackers, they will not cooperate with it. Besides, this scheme fully expels nodes that do not distribute their participation message more than once from the CH candidates. Therefore, this scheme cannot deal with the wireless network environment where message losses frequently occur.

3. Network and threat model

4. Reputation-based cluster head election in each cluster

In this paper, we assume that external attackers are expelled during the initial cluster formation process by a secure cluster formation protocol. Consequently, nodes referred to as attackers indicate internal nodes compromised by attackers. Our scheme consists of three steps. In the first step, each node generates its contribution value and broadcasts it. Then, each node gives direct reputation values to other nodes in the same cluster considering how well they obey the protocol. Protocol obedience is judged by measuring how many times other nodes successfully transmit their messages during the protocol operation and how many times other nodes fail their message transmission during the protocol operation. Therefore, the numbers increase incrementally and they can acquire more correct values with the lapse of time. For such a reason, the numbers should be weighted by the time interval between two successful transmissions and the time interval between two unsuccessful transmissions. A successful transmission is given a different value according to its received signal strength at a receiver side. The less signal strength is measured at a receiver, the smaller the value given to the sender by the receiver. After assigning direct reputation values to all members in the cluster, each node broadcasts the direct reputation list. We describe the first step in Section 4.2 in detail. In the second step, each node induces the indirect reputation values of other members using the received direct reputation lists and computes the combined value of other nodes to store it in the combined reputation table. Then, each node’s real reputation value is generated by averaging the combined reputation values assigned by other nodes. Lastly, each node computes the average of real reputation values for all members and excludes the nodes whose real reputation value is less than the computed average from CH candidates. The second step is described in detail in Section 4.3. In the third step, all nodes share a common value by aggregating the contribution values from CH candidates and elect a CH using the common value. We describe the third step in Section 4.4.

4.2. Transmission of contribution value and reputation list

Figure 1 presents the flowchart for the first step in our scheme. For every CH election round, each node generates its contribution value and broadcasts it. After all nodes transmit their contribution value, each node computes direct reputation values for other members considering how they conform to the CH election protocol. The protocol conformity can be judged by how many times the nodes transmit their message and by how many times they fail their message transmissions for the given transmissions. With the lapse of time, the numbers are likely to increase and the values become more correct. Therefore, they should be weighted by considering the time interval between two successful transmissions and the time interval between two unsuccessful transmissions. Considering the above aspects as a whole, we can make Equation (1).

OPEN IN VIEWER

Figure 1.

Flowchart for transmission of contribution value amd direct reputation list.

In (1), s c i , j and u c i , j represent the number of successful and unsuccessful transmissions from node j, respectively, which are counted by node i. Because a compromised node can deliver its message to only a subset of nodes in the same cluster by lowering the transmission power, counting the message reception should be subdivided. To reflect the effect by this kind of attack, we considered the received signal strength of a message in counting the message reception. That is, the increasing value of s c i , j should depend on the received signal strength when a message is received by node i. If we assume that the two-ray ground reflection model is employed for radio propagation, a node can extract the transmission power of a received message using Equation (2), where P_r is the received power, d is the Euclidean Distance, L is the system loss, G_t and G_r are antenna gains, and h_t and h_r are antenna heights. If a node can extract the transmission power of a received message, it can also extract the maximum reachable distance of the message (d_r) using the transmission power, as in Equation (3), where E_{two_ray_amp} is the energy consumed by the amplifier and b is the bandwidth:

R i , j D = 1 − 1 max [ { w s s c i , j − w u u c i , j } , 0 ] + 1

(1)

P t = P r d 4 L G t G r h t 2 h r 2

(2)

d r = P t E two _ ray _ amp × b 4

(3)

If the maximum reachable distance of the message is the same as the cluster diameter, it means that the sender does not invoke a selective transmission attack. Therefore, node i increases s c i , j by one. Otherwise, the increasing value of s c i , j is determined by dividing the maximum reachable distance by the cluster diameter. Whenever a node i notifies that it receives no messages from a node j during a broadcast period (that is, distribution of contribution value or distribution of direct reputation list), it increases the counter of unsuccessful transmissions for the node (that is, u c i , j ). In addition, w s and w u represent the weight for the counters of successful and unsuccessful transmissions, respectively. They can be calculated by the Equations (4) and (5), where Δ s is the time interval between the latest two successful transmissions and Δ u is the time interval between the latest two unsuccessful transmissions:

w s = 1 − Δ s Δ s + Δ u

(4)

w u = 1 − Δ u Δ u + Δ s

(5)

Then, each node broadcasts the direct reputation list to share it with other members. Upon receiving a direct reputation list, each node checks whether there is any reputation value that is less than zero or larger than one in the list. If so, each node checks whether it is in the first election round or in the further round. In the case of the first round, it fills all direct reputation values of the list with one and saves the list in the reputation table. Otherwise, it preserves the sender’s previous reputation list in the reputation table. If a sender’s direct reputation list conforms to the legal range, each node replaces the sender’s previous reputation list with the one currently received. Then, each node estimates the maximum reachable distance of the message to increase the value of the counter for successful transmissions. That is, the increasing value of the counter for successful transmissions is determined by dividing the maximum reachable distance of the message by the cluster diameter. When there is no message received during a specific period of time, the first step of our scheme ends.

4.3. Reselection of CH candidates

Figure 2 demonstrates the flowchart for the second step in our scheme. Firstly, each node checks whether any node in the cluster avoids the transmission of its direct reputation list or not. If a node avoids the transmission of its direct reputation list, each node increases the silencer’s counter for unsuccessful transmissions by one. Then, each node updates two unsuccessful transmission times for the silencer, since the latest unsuccessful transmission time should be changed to the present. Then, each node i computes the indirect reputation value of any other node j in the same cluster using Equation (6), where m is the number of members in the cluster. In addition, each node i can calculate the combined reputation value for any other node j by combining the direct and indirect reputation values of the node j, as shown in Equation (7). After obtaining the combined reputation values, each node stores them into the combined reputation table. Lastly, each node can obtain its real reputation value by averaging all combined reputation values assigned by members in the cluster, as shown in Equation (8). Real reputation values for all members are summed and divided by the number of members in order to obtain the average real reputation value. Each node excludes the nodes whose real reputation value is less than the average real reputation value from CH candidates:

R i , j IND = ∑ k = 1 m − 1 R i , k D R k , j D m − 1

(6)

R i , j = R i , j D + R i , j IND 2

(7)

R real i = ∑ j = 1 m R j , i m

(8)

OPEN IN VIEWER

Figure 2.

Flowchart for reselection of cluster head (CH) candidates.

4.4. CH election

Figure 3 shows the flowchart for the third step in our scheme. Each node generates a random value by adding the contribution values of survived CH candidates and obtains a remainder by dividing the random value by the number of the reselected candidates. The remainder indicates the position of the CH role node in the candidate list.

OPEN IN VIEWER

Figure 3.

Flowchart for cluster head (CH) election.

5. Background of modeling sensor networks

Sensor networks can be applied to a wide variety of areas, such as health, military, and home. ¹⁶ In the military area, prominent characteristics of sensor networks, such as rapid deployment, self-organization, and fault tolerance, enable many useful applications, such as military reconnaissance, early warning systems, and targeting systems. In the health area, sensor networks can be employed to monitor and assist some patients. Other applications include the management of production facilities, monitoring pollution, monitoring disasters, and so on.

While many networking and security protocols have been developed for a wide variety of sensor network applications, many researchers have made much effort to model and simulate their own protocol in the network using well-known simulators, such as OPNET, OMNET++, ns-2, TOSSIM, and so on. For example, Ramachandran et al. ¹⁷ proposed a group-based routing protocol for sensor networks and analyzed its performance through many simulations. As another example, Boukerche et al. ¹⁸ presented extended versions of two existing routing protocols to save energy consumption and enhance the scalability. The authors implemented their own protocol using C++ to model and simulate the communication environment of nodes. Hosseingholizadeh and Abhari ¹⁹ proposed an energy-saving scheme where the energy-consuming factor of nodes is classified into four parts and a corresponding countermeasure is invoked whenever each factor exceeds a specified threshold. The authors designed the software architecture of a node through an agent in the simulations and implement those countermeasures through the communication of the agents.

In sensor networks, nodes often should sense the environment where they reside and intellectually recognize complex phenomena in the environment. Even though many modeling and simulation tools for sensor networks have been developed and employed, their primary focus is to model and simulate the communication function of nodes in the network. ²⁰ For this reason, they naturally have a lack of ability to model and simulate the self-organization, the interaction between the network and an external object, sensing a complex adaptive environment. Since many promising applications of sensor networks are emerging, this lack of ability to model and simulate the complex adaptive environment becomes a limitation factor when we design a new possible application using sensor network simulations. As an alternative to these network modeling tools, we can use agent-based modeling tools, which have emerged recently. Niazi and Hussain ²⁰ show the differences between the network modeling and agent-based modeling and the reasons why we have to use the agent-based modeling tools. First of all, the network modeling tools cannot properly model the data generation of nodes in a complex adaptive environment, because they only rely on a probability distribution when they model the data generation of sensor nodes in the network. Contrarily, agent-based modeling tools can exactly model the data generation, since they can model a phenomenon such as gathering or dispersion as well as a peripheral object interacting with the network. In addition, using a formal specification method in the agent-based modeling not only can enhance the correctness of the modeling but also can easily verify the generated model. As of now, many agent-based modeling tools are available. For instance, Mason is a Java-based tool and StarLogo and NetLogo are Logo-based tools. ²¹

Niazi and Hussain ²¹ show how to model and simulate complex networks, such as P2P networks, ad hoc networks, and sensor networks, using NetLogo, which is a representative agent-based modeling tool. Prominent characteristics of NetLogo are as follows. Firstly, NetLogo can easily model human users, intelligent agents, mobile robots, and any concept required in the model. Secondly, implementation details, such as antenna pattern, propagation model, and a specific medium access control (MAC) layer implementation, can be implemented through extra coding work as needed. Thirdly, in NetLogo, interesting variables can be declared as global variables and measured to obtain a statistical value. Lastly, an analyst can trace a variable in real time in the model without modifying the code.

Even though the agent-based modeling tools provide many useful benefits in modeling a complex adaptive environment, we could not employ one of those tools in modeling and simulating our scheme due to the following reasons. Firstly, our model does not need any peripheral object, any interaction with a peripheral object around the network, or any non-network concept. In other words, in our scheme, we only need to model and simulate the nodes and their communication. As described earlier, employing a network modeling tool is enough to model network nodes and their communication. Secondly, due to unfamiliarity with an agent-based tool and lack of time to learn one of them, we leave the employment of an agent-based tool in modeling and simulating our scheme as a future research item.

6. Evaluation

6.1. Simulations

6.1.1. Implementation details of simulations

We implemented our scheme and other rival schemes on the ns-2 simulation environment ²² to evaluate their security and energy efficiency. In order to implement our scheme and other rival schemes on the ns-2 environment, we designed the skeleton of the sensor node and the sink as shown in Figure 4. In Figure 4, the thick arrows show how a message is sent to the sink from a sensor. In the design of the sensor node and the sink, most of the components are borrowed from the implementation of the Mobile Node class in the ns-2 environment. In our implementation, newly added components are Energy Resource, Resource Manager, RCAgent, BSAgent, and Application. The Energy Resource is employed to keep track of a node’s energy. The initial energy level is set at the beginning of the simulation and, throughout the simulation, energy is removed by the Application as the node performs energy-consuming work and by the network interface (that is, NetIF in Figure 4) during packet transmission and reception. The Application can also find out the amount of residual energy at any given time through an interface to the Resource Manager. The Resource Manager provides a common interface between the Application and the Energy Resource. The Application updates the status of the node’s Energy Resource through the Resource Manager. For example, three functions that the Resource Manager provides to the Application are add, remove, and query. We implemented a simple energy dissipation model where a transmitter dissipates its energy to run the radio electronics and the power amplifier, and a receiver dissipates its energy to run the radio electronics. The amount of energy removed for computation and communication is defined at the beginning of the simulation.

OPEN IN VIEWER

Figure 4.

Skeleton of sensor node and the sink on the ns-2 environment.

We adopted the MAC protocol that was employed by Heinzelman et al. ¹ in the implementation of our scheme. The protocol is a combination of carrier-sense multiple access (CSMA), time division multiple access (TDMA), and a simple model of the direct sequence spread spectrum (DSSS). TDMA is implemented within the Application by having the Application send data to the RCAgent during a specified TDMA time-slot. CSMA is implemented in the MacSensor class, and DSSS is implemented jointly within the Application and the MacSensor class.

We had two options for implementing the CH election protocols of our scheme and other rival schemes. Firstly, we could implement those protocols within the Application, like the implementation in Heinzelman et al. ¹ Secondly, we could implement those protocols within the RCAgent. Since the current implementation of the RCAgent had only a small number of variables and functions that we could reuse in our extended implementation, we had to add numerous variables and functions to implement the CH election protocols. For this reason, we mainly reused the existing codes of the Application and added required variables and functions within the Application.

6.1.2. Simulation settings

In the simulation environment, 100 nodes were randomly deployed in a 100 m × 100 m square field and initial clusters were generated using a cluster formation protocol. Initially, all nodes had 10 Joules of energy and consumed their energy using the energy model of Heinzelman et al. ¹ We assumed that there were no collisions when nodes communicated with each other for CH elections. If each node employs a MAC protocol that is based on the CSMA, this assumption is quite unrealistic. However, we can avoid the collisions on MAC layers by employing a TDMA-based protocol and multiple spreading codes. Refer to Section 7 for the details concerning the collision avoidance. During the simulation time of 1800 seconds, attackers selected nodes randomly and compromised them from 3 to 900 seconds. All nodes elected a CH in their cluster every 30 seconds. To concentrate on the CH election protocol, we did not implement the steady-state operation of nodes between consecutive CH elections. In the steady-state operation, a CH aggregates data sent from the normal nodes and sends the aggregated data to the sink. Therefore, we have only control packets for CH elections in the simulations. Half of the clusters suffered from silence attacks, while the other clusters suffered from selective transmission attacks.

We compared our scheme with the seed-based scheme, ⁸ the commitment-based scheme, ⁸ and the key-chain-based scheme. ⁹ The reason why we chose these schemes for comparison is that they generate a common value using a similar method to one another and elect a CH using the common value. Besides, they suffered from the same attacks. We ran each scheme 20 times for each number of compromised nodes and averaged the results to draw a representative value. The network topology and the compromised nodes were changed for every execution. In a cluster, all compromised nodes invoked the same kind of attack. This was essential because the objectives of two attacks (that is, the silence attack and the selective transmission attack) conflict with each other. To facilitate our comparison, we developed the following metrics.

Average number of CHs per cluster: this is computed by summing the number of CHs per cluster through all election rounds and dividing the sum by the number of election rounds. This metric represents the resiliency of a CH election scheme against the cluster split trials by compromised nodes.

CH winning frequency of compromised nodes per election: this is computed by summing the CH winning frequencies of compromised nodes through all election rounds and dividing the sum by the number of election rounds. This metric represents the robustness against the election result modifications by compromised nodes.

Energy consumption per node: this is computed by summing the expended energy of all nodes during the simulation and dividing the sum by the number of nodes. This metric represents the energy efficiency of a CH election scheme.

6.1.3. Simulation results

Figure 5 illustrates how many CHs are generated in a cluster as the number of compromised nodes increases. Because the seed-based scheme and the commitment-based scheme do not properly deal with the selective transmissions of compromised nodes, they greatly increase the number of CHs even under a small number of compromised nodes. The key chain-based scheme mitigates the increase of CHs via a protocol that merges multiple clusters into a single cluster when compromised nodes are sparse. However, if compromised nodes increase, they can collapse the operation of the merge protocol. Our scheme hardly increases the number of CHs per cluster regardless of the increase of compromised nodes, as shown in Figure 5.

OPEN IN VIEWER

Figure 5.

Average number of cluster heads (CHs) per cluster versus the number of compromised nodes.

Figure 6 shows the CH winning frequency of compromised nodes as the number of compromised nodes increases. As presented in Figure 6, the seed-based scheme and the commitment-based scheme increase the CH winning frequency of compromised nodes in line with the increase of compromised nodes. This is because compromised nodes can easily forecast a CH election result and change the CH election result by avoiding the transmission of their contribution values. The key-chain-based scheme provides better security than the preceding two schemes, because it excludes nodes that avoid transmitting their contribution values more than once. However, if compromised nodes alternately avoid their transmissions, this scheme also allows many compromised nodes to survive the exclusion. Therefore, the key-chain-based scheme is also vulnerable to the increase of compromised nodes. Even though our scheme also increases the CH winning frequencies of the compromised nodes as the number of compromised nodes increases, the increasing slope is very gentle, as shown in Figure 6.

OPEN IN VIEWER

Figure 6.

Cluster head (CH) winning frequency of compromised nodes per election versus the number of compromised nodes.

Figure 7 shows the average amount of energy consumed by each node for CH elections. The seed-based scheme provides the best energy efficiency as compared to other schemes, because each node transmits only a short availability message in CH elections. It seems strange that the key-chain-based scheme reduces the amount of energy consumed by nodes even if the number of compromised nodes increases. This is because the key-chain-based scheme excludes a suspicious node from CH candidates when the node is silent more than once. Therefore, the excluded node will not consume energy any longer. Note that nodes consume almost the same amount of energy in our scheme. This is because compromised nodes in our scheme can participate in the next CH election even though they are excluded in the current election. This strategy ensures that our scheme is able to cope with message losses, which occur frequently in the wireless network environment.

OPEN IN VIEWER

Figure 7.

Energy consumption per node versus the number of compromised nodes.

Figure 8 shows how the message loss rate affects the number of generated CHs per cluster. Note that the number of compromised nodes was set to 30 in this simulation setting. As shown in Figure 8, the commitment-based scheme and the seed-based scheme generate more CHs as the message loss rate increases. This is because many different candidate lists are generated for CH election. This increases the number of common values shared among nodes in a cluster and generates more CHs. In Figure 8, the key-chain-based scheme appears to provide the superior security under the loss-prone environment. However, as shown in Figure 8, the scheme increases clusters with no CHs as the message loss rate increases. Note that the key-chain-based scheme considers a cluster having no CH as a useless cluster. In particular, if the message loss rate exceeds 2%, one out of two clusters has no CH. Therefore, it is difficult to claim that the key-chain-based scheme provides better security than the commitment- and the seed-based schemes. The reason why some clusters have no CHs is that a node can declare itself as a CH only when it gets recommendations from more than half of the nodes. However, if message losses frequently occur, some prominent candidates fail to obtain recommendations from more than half of the nodes. In addition, Figure 8 shows that our scheme hardly increases the number of CHs, even though the message loss rate rises up and provides the best security over other schemes.

OPEN IN VIEWER

Figure 8.

Average number of cluster heads (CHs) per cluster versus message loss rate.

Figure 9 shows how the increase of message loss rate affects the CH winning frequency of compromised nodes. The seed-based scheme and the commitment-based scheme generate many CHs in a cluster as the message loss rate increases and, consequently, this raises the CH winning frequency of compromised nodes. One observable fact is that the key-chain-based scheme reduces the CH winning frequency of compromised nodes as the message loss rate increases. This is because clusters with no CHs increase as message losses increase, as shown in Figure 8. Our scheme decreases the CH winning frequency of compromised nodes compared with other schemes. Moreover, our scheme limits the CH winning frequency of compromised nodes under a specific number (that is, two in Figure 9), regardless of the increase of message loss rate.

OPEN IN VIEWER

Figure 9.

Cluster head (CH) winning frequency of compromised nodes per election versus message loss rate.

Figure 10 shows how the increase of message loss rate affects the variation of energy consumption per node. All schemes reduce the energy consumption per node very slightly as the message loss rate increases. This is because the number of messages received by nodes decreases due to message losses. In particular, the commitment-based scheme is more affected by message losses because nodes transmit more messages than other schemes.

OPEN IN VIEWER

Figure 10.

Energy consumption per node versus message loss rate.

6.2. Effect of node increase

In this section, we introduced an additional simulation to find how the increase of nodes affects the security and performance of CH election schemes. In the extra simulation, we fixed the number of compromised nodes to 30 and assumed that no message is lost.

Figure 11 shows that the increase of nodes does not have a great impact on the number of generated CHs in all schemes. In Figure 11, the key-chain-based scheme seems to provide the best performance among others. However, since it produces some clusters having no CH, it is difficult to claim its superiority over other schemes. Considering such an aspect, we can claim that our scheme demonstrates the best performance over other schemes, as shown in Figure 11.

OPEN IN VIEWER

Figure 11.

Average number of cluster heads (CHs) per cluster versus the number of nodes.

Figure 12 shows the CH winning frequency of compromised nodes as the number of nodes increases. As shown in Figure 12, the increase of nodes reduces the CH winning frequency of compromised nodes in all schemes. This is natural because the number of compromised nodes is fixed and the number of normal nodes increases. Note that our scheme suppresses the CH winning frequency of compromised nodes better than other schemes.

OPEN IN VIEWER

Figure 12.

Cluster head (CH) winning frequency of compromised nodes per election versus the number of nodes.

Figure 13 shows the variation of energy consumption as the number of nodes increases. As shown in Figure 13, all schemes increase the energy consumption of nodes as the number of nodes increases. This is because the added nodes also join the CH election protocol and consume their energy resource.

OPEN IN VIEWER

Figure 13.

Energy consumption per node versus the number of nodes.

6.4. Qualitative comparison

In this section, we compare our reputation-based scheme with other schemes that were employed for the simulation study according to the required properties for CH election. The required properties for CH election were previously described in Section 3.2.

The key-chain-based scheme provides the lowest unpredictability among all schemes because the order of being the CH in a cluster is known to all nodes. In other schemes, only the last contributor of a common value can predict which node is going to be the CH. So, the last contributors can also manipulate the CH election results in their cluster by launching silence attacks. Even though the key-chain-based scheme slightly enhances the manipulability by excluding some compromised nodes from CH candidates, the exclusion does not work well when the compromised nodes increase and they alternately launch a silence attack. The reputation-based scheme excludes malicious nodes very well, as long as the number of normal nodes is larger than that of compromised nodes. That is, if the majority of members are normal nodes, they give a small reputation value to the compromised nodes. Therefore, the compromised nodes’ reputation value is likely to be lower than the cluster’s average reputation value, and the compromised nodes are excluded from the CH candidates.

The commitment-based scheme and the seed-based scheme have no countermeasure when compromised nodes attempt to break the agreement property by launching selective transmission attacks. Therefore, the agreement property in a cluster can be easily broken. Even though the key-chain-based scheme slightly enhances the property using a merge protocol, it does not work well when compromised nodes increase and they refuse to cooperate with the protocol. In the reputation-based scheme, normal nodes well exclude compromised nodes which launch selective transmission attacks as long as the majority of members in a cluster are normal nodes. As a result, the candidate membership view among normal nodes is almost consistent.

Furthermore, the commitment-based scheme and the seed-based scheme have no mechanism for dealing with message loss. So, they are very vulnerable to message loss. In the key-chain-based scheme, message loss is more serious because some clusters cannot elect a CH due to the shortage of recommendation messages. Because our scheme allows the nodes excluded in the current election to take part in the next election again, it is very immune to message loss. We summarize the above descriptions in Table 1.

OPEN IN VIEWER

Table 1.

Qualitative comparison of cluster head election schemes.

Properties	Commitment-based scheme	Seed-based scheme	Key-chain-based scheme	Reputation-based scheme
Unpredictability	Medium	Medium	Low	Medium
Non-manipulability	Medium	Medium	Medium	High
Agreement property	Low	Low	Medium	High
Immunity from message loss	Low	Low	Low	High

7. Collision avoidance

During the CH election period, each node broadcasts its messages for the generation of the common value and the exclusion of malicious nodes. A broadcast message can collide with other messages sent from other nodes in the same cluster or in other clusters.

To reduce the collisions in the inter-cluster communication, each cluster employs its unique DSSS code. With enough spreading codes, each cluster can filter out the transmissions from neighboring clusters as noise. ¹ After the initial cluster formation, a representative node in each cluster (e.g. lowest ID node) can advertise its existence to the sink. Here, the first node to advertise its existence is assigned the first code on a predefined list, the second node to advertise its existence is assigned the second code, and so on.

Even if we can avoid the collisions in the broadcast transmissions between neighboring clusters, the transmissions between neighboring nodes in the same cluster can cause some collisions. To resolve this problem, a representative node in each cluster can set up a TDMA schedule and transmit the schedule to the nodes in the cluster. Once the schedule is known to all nodes in the cluster, each node can always turn off their radio, except during its transmission time. This enables the collision avoidance of messages between nodes in the same cluster and significantly saves the energy of nodes.

8. Conclusions

In clustered sensor networks, CH election results are likely to be predicted and manipulated by compromised nodes, and they can easily violate the agreement property of a CH election result. In this paper, we present an effective method that finds such compromised nodes and excludes them from the CH candidates. Firstly, our scheme makes each CH candidate evaluate the behavior of other candidates in order to give a direct reputation value to them. Then, the direct reputation lists are distributed to other nodes and the receivers compute the indirect reputation values and the combined reputation values for other nodes using the direct reputation lists. Next, the combined reputation values are averaged to extract the real reputation value for each node. Lastly, each node excludes potential attackers from the CH candidates by comparing the real reputation values of nodes. Besides, our scheme can flexibly respond to message losses because it allows the excluded nodes to compete with other nodes in future CH elections. Simulation results have proven that the proposed scheme enhances the non-manipulability and the agreement property of CH election results compared to other schemes. Other simulation results have shown that the proposed scheme provides higher security than other schemes, even in an environment with message losses. Additional simulation results have shown that the proposed scheme preserves its performance even though the number of nodes increases.

As a future work item, we plan to model our scheme and rival schemes using an agent-based modeling tool, such as NetLogo. Since the agent-based modeling tool can model not only the network nodes and their communication but also peripheral objects around the network and their interaction with the network, we can observe the performance of each scheme in an almost real-world environment. Besides, it is expected that we can observe how the peripheral objects and their interaction with the network affect the performance and the security of each scheme.