Abstract
The ability of sensor nodes to enter a low power sleep mode is very useful for extending network longevity. We show how adversary nodes can exploit clustering algorithms to ensure their selection as cluster heads for the purpose of launching attacks that prevent victim nodes from sleeping. We present two such attacks: the barrage attack and the sleep deprivation attack. The barrage attack bombards victim nodes with legitimate requests, whereas the sleep deprivation attack makes requests of victim nodes only as often as in necessary to keep the victims awake. We show that while the barrage attack causes its victims to spend slightly more energy, it is more easily detected and requires more effort on behalf of the attacker. Thus, we have focused our research on the sleep deprivation attack. Our analysis indicates that this attack can nullify any energy savings obtained by allowing sensor nodes to enter sleep mode. We also analyze three separate methods for mitigating this attack: the random vote scheme, the round robin scheme, and the hash-based scheme. We have evaluated these schemes based upon their ability to reduce the adversary's attack, the amount of time required to select a cluster head, and the amount of energy required to perform each scheme. We have found that of the three clustering methods analyzed, the hash-based scheme is the best at mitigating the sleep deprivation attack.
Introduction
Power management is a major research issue in sensor networks, given that sensor nodes are constrained to operate upon limited battery supplies. In general, the total energy consumption of a sensor node can be categorized into the following three groups: 1) energy spent on computations, 2) energy used to communicate, and 3) energy spent as a result of the node's sleeping patterns. In this paper we focus on the ability of sensor nodes to enter a low power sleep mode for the purpose of extending the longevity of the network. It is widely accepted that this is an important issue, as sensor nodes spend most of their time in sleep mode, allowing the overall lifetime of the node to be greatly extended [3, 8, 11, 17, 28, 30].
The ability of sensor nodes to enter a sleep mode becomes a serious concern for sensor networks deployed in unattended and hostile environments. Limited tamper resistance inherent to a low cost sensor node leaves the node vulnerable to being compromised by an adversary [8, 9, 36]. Through compromised nodes, an adversary may launch security attacks against the sensor network ranging from the physical layer to the application layer. Due to the vast variety and novelty of attacks, we believe no single solution can address all the attacks. As such, we limit our work to addressing a specific type of attack aimed at disrupting the power management protocol in sensor applications such as target tracking.
We present two attacks that prevent victim nodes from sleeping: the barrage attack and the sleep deprivation attack. In the barrage attack, the victim is barraged with seemingly legitimate requests; however, the purpose of these requests is to waste the victim's limited power supply by causing it to stay out of its sleep mode and perform energy intensive operations. In the sleep deprivation attack, the malicious node makes requests to victim nodes only as often as is necessary to keep the victims awake. Thus victim nodes are kept awake, but are not made to perform energy intensive operations as is the case in the barrage attack. From our analysis, we have found that while the barrage attack causes its victims to spend slightly more energy, it is more easily detected and requires much more effort on behalf of the attacker. For these reasons, we have focused our research on the sleep deprivation attack.
To further analyze the sleep deprivation attack, we have used a clustering based target tracking network as the basis for our analytical model. It was the decision of the authors to utilize a specific application rather than a more general model in order to grant the reader further insight into the mechanisms of the sleep deprivation attack. Note that while our analysis was done based upon a particular implementation of target tracking, our results are readily applicable to any clustering based sensor network application. We show that for one set of network parameters, an adversary can double the power consumption of a 400 node network with as few as 20 compromised nodes. Further, we show that a single adversary node can simultaneously attack as many as 150 victims and still outlive its victims.
Given the detrimental effect of the sleep deprivation attack, we have analyzed three separate defense mechanisms to mitigate this attack: the random vote scheme, the round robin scheme, and the hash-based scheme. We have evaluated these schemes based upon their ability to mitigate the adversary's attack and the amount of time required to select a cluster head. We have found that of the three clustering methods analyzed, the hash-based scheme is the best at mitigating the sleep deprivation attack. Given the viability of the hash-based scheme, we have also analyzed the amount of energy it requires to select a cluster head.
The remainder of this article is organized as follows. In Section 2 we discuss related works. In Section 3 we introduce the framework used to perform our analysis. In Section 4 we compare the barrage attack and the sleep deprivation attack. In Section 5 we further analyze the sleep deprivation attack and in Section 6 we discuss methods to mitigate this attack. In Section 7 we make our conclusions.
Related Work
Sleep Deprivation Attack
The idea of the sleep deprivation attack was first proposed by Stajano [32, 33]. The victim of this attack is a battery powered computing device, such as a sensor node, which attempts to remain in a low power sleep mode for as long as possible without adversely affecting the nodes' applications. The attacker launches a sleep deprivation attack by interacting with the victim in a manner that appears to be legitimate; however, the purpose of the interactions is to keep the victim node out of its power conserving sleep mode. Thus, this attack can be used to dramatically reduce the lifetime of the victim. Further, this attack is difficult to detect given that it is carried out solely through the use of seemingly innocent interactions.
The work by Krishnaswami is one of the few works that has attempted to quantify the impact of sleep deprivation attacks on energy-constrained devices [22]. The approach used by Krishnaswami consisted of measuring the difference between the average power consumption of laptops and PDAs while the devices were idle (but not in sleep mode) and when the devices were under attack. We find Krishnaswami's approach to be overly simplistic in how devices were attacked. The adversary gives the victim a task that is specifically designed to burn inordinately large amounts of energy. Such an attack could be easily detected given that sensor nodes are by necessity, very diligent about their power management. We claim that a much more difficult to detect attack would be to have the adversary focus on keeping the victim out sleep mode, rather than try to have the victim actively processing.
Cluster Head Selection
In sensor networks, clustering is used to organize sensor nodes into groups based in part on their physical proximity [8]. One of the nodes in the cluster is delegated the task of being the cluster head. The main benefit of clustering is that it enables data fusion [4], whereby redundant data is pruned from the network. In the case of target tracking, several nodes may detect the same target. It is wasteful for each of these sensor nodes to transmit identical tracking information to a centralized data processor. A more efficient solution is to have a group of nodes perform local processing of sensor data and transmit a single message.
In the clustering algorithm proposed in [10], clusters are formed by having each sensor node wait a random amount of time. If a node has not had the opportunity to join a cluster after this random amount of time, then it can declare itself to be a cluster head and subsequently start soliciting neighboring nodes to join its cluster. To maintain the cluster, the cluster head will select its own successor. We foresee two vulnerabilities with this approach. First, during cluster formation, an adversary could ensure its selection as cluster head by immediately soliciting other nodes to join its cluster. Second, once an adversary node has been selected as cluster head, it can remain cluster head indefinitely by never selecting a successor. Consequently, this approach readily allows an adversary to launch a sleep deprivation attack.
In [1], each node declares itself a cluster head with a probability p. Each cluster head will then solicit any other node within k hops to join its cluster. Nodes receiving multiple solicitations join the closest cluster available. A node that has not received a cluster solicitation within a certain amount of time will then declare itself to be a cluster head, and will solicit other sensor nodes within k hops to join its cluster. Clearly this algorithm is vulnerable to a sleep deprivation attack by allowing a malicious node to simply declare itself a cluster head.
There are many other distributed clustering algorithms and sensor network applications that rely upon clustering (e.g. [1, 2, 12, 14–16, 19]), each of which assumes that participating nodes will act honestly. Thus, an adversary can exploit each of these algorithms to ensure its selection as cluster head. Given that clustering is a widely used algorithm, it is crucial to make it secure.
Target Tracking
For didactic purpose, we pose our discussion of the sleep deprivation attack within the context of a sensor network executing a distributed clustering target tracking application; however, our results are more generally applicable to any algorithm that relies upon clustering.
Target tracking research has focused on such issues as increasing the fidelity of sensor data, reducing redundant data, and reducing energy consumption. Since many of these algorithms [13, 25, 27, 31, 37–39] rely on a trusted cluster head, they are all susceptible to the sleep deprivation attack.
System Modelling
Model Assumptions
Node and Network Characteristics
We consider the placement of sensor nodes to be spread uniformly at random throughout a square region. The sensor nodes operate on non-renewable batteries; once a node exhausts its battery it is considered to be dead. To preserve their battery power, sensor nodes will cycle in and out of a low-power sleep state.
We assume the presence of a publish/subscribe routing protocol [18, 20]. A publish/subscribe protocol has two network primitives, a publish method and a subscribe method. The subscribe method is used by individual nodes to indicate their desire to receive data fitting a specified description. In our model, sensor nodes subscribe to all track records within z meters of their position. When a local group of nodes detects a target they will share sensor readings. One of these nodes is then elected as cluster head. This node aggregates the sensor data on behalf of the cluster and forms a track record. The track record is sent to all subscribed nodes by repeatedly invoking the publish method. The publish method is invoked one time for each subscribed node. For simplicity, we assume that track records are sent reliably (i.e., a track record will always reach its recipient node despite network errors or sleeping sensor nodes).
We assume a homogeneous network, where a cluster head is identical to any other node in the cluster in terms of capacity and resources. For simplicity we shall assume that nodes within the same cluster can communicate directly. This assumption could be relaxed by allowing multihop communication.
Security Assumption and Attack Model
We assume that sensor nodes do not have significant tamper resistance. Thus, an adversary is capable of compromising sensor nodes [8, 9, 36]. That is, the adversary can obtain data, keys, and the code inside compromised nodes. To launch attacks, the adversary reprograms the compromised nodes with malicious code and then redeploys them into the network. Compromised sensor nodes may launch attacks in different layers in the protocol stack, e.g., channel jamming in the physical layers [36], disrupting the collaboration of sensor nodes in the MAC layer protocol [7, 23, 29], attacking the routing protocol [21], jeopardizing the localization service [6, 24], or the sensor data [34]. Due to the diversity and novelty of attacks, no one-for-all solution exists. All of the aforementioned attacks have been addressed separately. As such, although compromised nodes (including cluster heads) may launch various attacks, in this work we limit our focus to identifying, analyzing, and defending against the attacks that specifically target the network's power management protocols.
We assume each sensor node is assigned a unique ID prior to deployment. Further, sensor nodes cannot impersonate uncompromised nodes. Preventing impersonation could be accomplished by requiring every node to authenticate its messages using pairwise keys shared with receiver nodes [26, 40]. This assumption ensures that a compromised node can only submit a single vote in a cluster head selection algorithm, such as the algorithm described in Section 6.3.
We consider the placement of adversary nodes to be uniformly random; this reflects the adversary's desire to spread its nodes in order to maximize their impact. In this article the terms malicious nodes and adversary nodes are synonymous to such compromised nodes.
Sensor Node States
To help quantify the impact of an adversary attack we have partitioned the nonadversary sensor nodes into three separate states: sleep, idle, and receive (note that the lack of a transmit state reflects the fact that nonadversary nodes do not generate network traffic in our model; we have made this assumption to help illuminate the impact of an adversary attack better). As Table 1 indicates, the state of a sensor node is defined by the status of its CPU and wireless radio. Accordingly, we consider the behavior of sensor nodes to cycle between the sleep state and the idle state, staying in each state for fixed time quantums. A sensor node in the idle state will enter the receive state upon receipt of a track record. This will only occur when the sensor node is subscribed to an adversary node. Once a sensor node has received a track record it will stay in idle mode for an extended period of time.
Nonadversary Node State Space
Nonadversary Node State Space
Similarly, we have partitioned the adversary nodes into two states: sleep, and transmit. Table 2 indicates the status of the CPU and wireless radio for each state. In order for an adversary node to maximize its energy, it will transmit track records to each of its subscribed nodes in rapid succession and then go to sleep.
Adversary Node State Space
To make our analysis realistic we have used values taken from actual sensor node specifications as seen in Table 3. We were able to obtain actual values for power, data rate [8], and packet size [5]. Given symmetric upload and download speeds for each link, we derived t rs , the time required to send or receive a packet. The timing values in Table 3 (t a , t ar , and t slp ) are based upon ongoing experiments being performed at our lab.
Model Parameters
In Fig. 1 we illustrate what we consider normal sensor node behavior when no tracking is occuring. A sensor node alternates between sleep mode for tslp seconds and idle mode for tidle seconds.
In Fig. 2 we illustrate the behavior that a sensor node would exhibit upon receiving a single track record (represented pictorially by “TR” in the figure). Initially the sensor node is alternating between sleep and idle states, until its idle state is cut short by receipt of a track record. After trs seconds, the node has received the entire track record and has determined that a possible target is coming its way. After waiting tar seconds for a target, the node determines it is safe to go back to sleep. At this point the node resumes the behavior exhibited by Fig. 1. There are three important observations to note. First, only a cluster head will generate a track record. Second, a track record is the only message that will interfere with a sensor node's sleep cycle. Third, tar is much larger than is depicted in Figs. 2 and 3.

Timing diagram of normal node behavior when no tracking is occurring.

Timing diagram of normal node behavior after receiving track record.

Timing diagram of node under sleep deprivation attack.
Figure 3 illustrates a sensor node being victimized by a sleep deprivation attack. The attacker sends the victim a track record every tar + trs seconds. Each time the victim is just about to decide that it can go to sleep mode, it receives another track record. Thus the victim is kept perpetually awake.
Figure 4 shows a sensor node that is under a barrage attack. Notice that the adversary sends the victim track records as rapidly as possible (i.e., every trs seconds).

Timing diagram of node under barrage attack.
In this section we explain the tradeoffs between the sleep deprivation attack and the barrage attack. Further, we explain why the sleep deprivation attack would be the preferable method of attack from the perspective of the attacker.
In both the sleep deprivation attack and the barrage attack the victim will never enter its low power sleep mode. The difference between the two attacks is that the victim of a barrage attack will be actively performing work, whereas the victim of a sleep deprivation attack will, for the most part, remain idle. In this section we investigate the difference between these two attacks based upon the following: 1) the victim's power consumption, 2) detectability of the attack, and 3) the power required of the adversary.
Power Consumption of Victim
Consider the following scenario. A particular sensor node cycles in and out of its low power
sleep mode. The proportion of time that the sensor node is asleep versus awake is denoted by the
variable x. This sensor node has been given a small workload, thus it spends 300 mW
in idle mode and 1 mW in sleep mode, giving the following equation denoting the sensor node's
average power consumption in mW:
Thus this node spends 1 mw of power when x = 0 and it spends 300 mw of ow power when x = 1.
Now consider if this same node was victimized by a sleep deprivation attack or a barrage attack. In the sleep deprivation attack, the adversary will interact with the sensor node intermittently so that it will never go to sleep, thus the victim will spend an average of 300 mW of power. Alternatively, if the adversary was to utilize a barrage attack, the victim will be constantly receiving messages, causing it to spend 440 mW of power. Clearly the victim of a sleep deprivation attack spends slightly less power than the victim of a barrage attack. It is also clear that the relative impact of either attack is directly proportional to x.
An energy draining attack must remain undetected for as long as possible in order to waste a maximum amount of energy. An easily detected attack allows the victim to rapidly take remedial action, such as ignoring the requests of a detected attacker, before the attack can cause significant damage.
We speculate that the sleep deprivation attack would be much more difficult to detect than the barrage attack based on the observation that it generates messages at relatively infrequent rate. Using the parameters in Table 3, the barrage attack requires 254 messages to be sent every minute, whereas the sleep deprivation attack only requires a single message to be sent.
Energy Required of Attacker
Since the adversary nodes are compromised sensor nodes, they would be more likely to perform an attack that can cause a lot of damage without requiring a lot of energy to perform.
In a barrage attack the adversary has to transmit a network message every trs seconds, whereas in sleep deprivation attack the adversary only has to generate a network message every trs + tar seconds. Thus, the adversary has to spend a lot more power to launch the barrage attack. Considering that the adversary could simultaneously launch sleep deprivation attacks upon multiple sensor nodes for less power consumption than would be required to launch a barrage attack on a single node, it seems likely that the battery-constrained adversary nodes would prefer the sleep deprivation attack.
Sleep Deprivation Attack
In Section 4 we showed that the sleep deprivation attack is a serious threat to a sensor network given that it nullifies any energy savings that would have been obtained by the victim's low power sleep mode. In this section we illustrate how an adversary can utilize the security vulnerabilities inherent to distributed cluster formation for the purpose of launching a sleep deprivation attack. We show that the sleep deprivation attack can as much as double the overall power consumption of a 400 node network. Further, we find that this can be accomplished with as few as 20 adversary nodes.
To quantify the impact of this attack we measure the average node's power consumption. This is a useful metric because it measures the network-wide impact of the adversary's attack. As a point of clarification, only the power consumption of non-adversary nodes will be measured in this metric.
Derivation of Model
We now derive the equations that we have used to analyze the impact of the sleep deprivation attack.
Probability of Subscribing to an Adversary Node
Using a geometric argument, the probability that a sensor node will be subscribed to an adversary
cluster head, given that each node is deployed in a square region of length L and
each node subscribes to all track records within a radius of size z <
L, is:
The complement of this equation gives the probability that a sensor node is not subscribed to a
particular adversary node. Given C, adversary nodes with uniformly random
placement, the probability that a given node will be subscribed to at least one malicious cluster
head is:
Note that this analysis will be slightly skewed due to fringe effects. Nodes on the edges of the network are less likely to be in contact with a adversary cluster head. However, only for small networks will these fringe effects be substantial, and thus we shall ignore their effects in our analysis.
To determine the average node's power consumption we have partitioned sensor nodes into two groups: those that are subscribed to adversary cluster heads and those that are not.
Nodes that are not subscribed to an adversary cluster head alternate between the idle state for
tidle seconds and the sleep state for tslp
seconds. Thus, the rate that these nodes expend energy is:
Nodes that are subscribed to an adversary cluster head alternate between an extended idle state
for tar seconds and the receive state for tr
seconds. Thus, nodes subscribed to a malicious cluster head expend energy at the following rate:
Utilizing the equations for p, Pnrm, and
Patk, it is straightforward to attain the average power consumption for
non-adversary nodes:
Assume each adversary node goes through two states: first it sends out a track record to each of
its subscribed nodes and then it sleeps. Adversary nodes send these messages as rapidly as possible
in order to maximize sleep time. This is modeled by each adversary node sending x
such messages to x victim nodes. As Fig. 3 indicates, the victims have to receive track records
every tar + trs seconds to be coerced into staying out
of sleep mode. Thus, the adversary spends xtrs seconds sending messages
and tar + trs —
xtrs seconds sleeping. Therefore, the total power required of the
adversary is:
Figure 5 illustrates the effect of malicious nodes on a network containing 400 legitimate nodes for different subscription radii (i.e., z). Our results indicate that as more malicious nodes are inserted, the average power consumption increases asymptotically to Pidle, meaning that at some point every sensor node will never go to sleep. We have also observed that it is desirable to keep z as small as possible to minimize the effect of malicious nodes. Unfortunately, this also reduces the ability of tracking nodes to give each other advance notice of a potential target. Thus, a network designer should carefully consider the implications of selecting a particular subscription radius.

Effect of subscription radius in sleep deprivation attack.
To show that the attack is viable for an adversary to perform, we utilize the equation for Padv to show the energy required for the attacker to launch the attack. In Fig. 6 we have plotted the energy required of an adversary node to attack various numbers of victims. From our analysis, an adversary node could simultaneously attack up to 150 nodes before its power consumption became higher than that of its victims, and thus from a power perspective this attack does not require the attacker to expend a great deal of energy. Therefore, we conclude that the sleep deprivation attack enables the adversary to cause a lot of damage without expending a lot of effort.

Energy required for attacker to launch attack upon differing numbers of victims.
We have shown that the sleep deprivation attack greatly increases the sensor network's power consumption without requiring excessive power to be consumed by the adversary. To launch this attack, the adversary nodes must become cluster heads, which we have shown to be exceptionally easy. In this section we propose several algorithms that make it much more difficult for the adversary to become a cluster head, and consequently, these techniques greatly reduce the impact of the sleep deprivation attack. We assume adversary nodes are interested in increasing their chances at becoming cluster heads. Thus, we do not consider an attack where the adversary intentionally delays cluster head selection.
Random Vote Cluster Head Selection
We have observed that clustering algorithms rely on the honesty of all participating nodes, allowing a malicious node to generate false information to ensure its selection as cluster head. The random vote scheme counteracts this characteristic by randomizing cluster head selection.
Overview of Random Vote Scheme
A group of local nodes using the random vote scheme form a cluster by performing the following
steps: Each node locally broadcasts its unique ID. Each node uses a pseudorandom number generator to pick the ID of the local node it desires to
become the next cluster head. Nodes locally broadcast the ID of their desired cluster head. Each node repeats step 2 until a single node attains a majority of votes. This node will become
the next cluster head.
Each sensor node is only allowed to cast one vote at a time. However, in the case of a tie, the nodes will restart the algorithm at step 2. We refer to the execution of steps 2 through 4 as a round or iteration. Thus, the random vote algorithm is potentially composed of several rounds.
Analysis of Random Vote's Effectiveness at Increasing Attack Tolerance
For simplicity we have assumed that the N legitimate nodes and the C compromised nodes in the network have been evenly divided into G clusters. Thus, we assume that there are n legitimate nodes per cluster and c malicious nodes per cluster.
To determine the effectiveness of the random vote scheme, we have derived an equation indicating
the probability that any of the malicious nodes in the cluster will be selected as cluster head,
given that i out of n nonmalicious nodes have voted for it. The
adversarial nodes in the local cluster wait until all other nodes have voted so that they can all
vote for the adversary node that currently has the most votes. The probability that this node
attains a majority of the n + c votes is modeled with a
binomial distribution as follows:
Similarly, the probability that any of the n nonadversary nodes are selected as
a cluster head is:
The equations for prand,c and prandy,n are only for a single iteration of the algorithm. We utilize the three state Markov chain in Fig. 7 to determine the probability of either an adversary node or a non-adversary node being elected once the algorithm has completed. In this figure, the states sc and sn represent the selection of a malicious node as cluster head and selection of a legitimate node as cluster head respectively. State su represents any intermediate iterations where the algorithm fails to select a cluster head. Further, su is also the initial state of the algorithm. We denote the steady state probability that a legitimate node is selected as cluster head as prand,n′ and the steady state probability that an adversary node is selected as cluster head as prand,c′.

Markov chain representation of random selection of cluster heads.
In an argument similar to what was used to formulate p, the probability of a
legitimate node being subscribed to at least one cluster containing adversary nodes is:
The product of prand,c and p′ gives the
probability that a legitimate node is subscribed to an adversary cluster head. Using this product,
the network's average power consumption is:
Without any defense mechanism in place, a malicious node is selected as cluster head with a probability of 1. In Fig. 8 we illustrate p′ as a function of the number of compromised nodes in the cluster (c) and the total number of nodes in the cluster (n + c). This graph shows that, given a single adversary node in a cluster, the random vote scheme nearly halves the probability that the adversary node will be selected as cluster head. However, this probability jumps to nearly 1 when multiple adversary nodes are located in the same cluster. It may startle the reader to see that when n + c is even the adversary appears to have a better chance of becoming a cluster head. This is a direct result of the difference between attaining a majority for odd and even numbers.

Probability that the random vote scheme selects an adversary cluster head.
In order for this algorithm to be complete, any of the n +
c nodes in the local cluster must attain a majority of the votes, otherwise the
nodes will keep voting. We can model this phenomenon using expected value as follows:
In Fig. 9 we utilized equation I to investigate the amount of time the random vote algorithm requires to complete when we vary the parameters n and c. If a vote message is represented in 30 bytes, it would take about 24 ms to transmit a single vote. Since each round requires n + c votes, this graph indicates that the random vote algorithm requires an acceptable amount of time to complete for moderate sized clusters (i.e., n < 7). However, for clusters where there are more than 7 nodes, the algorithm incurs too much latency. For example, when there are 10 nodes in the cluster, the algorithm would require an average of 166s to complete.

Time required for random vote algorithm to complete.
The lack of scalability in the random vote clustering algorithm of Section 6.1 caused us to consider another approach to secure cluster formation. The round robin scheme is based on the observation that if each node maintained more state, i.e., if clusters were maintained for long periods of time, a more scalable solution would be possible. With such a scheme, cluster heads could be elected in a round robin fashion.
The round robin scheme operates in two phases. The first phase is a bootstrapping phase where the initial clusters are formed. The second phase is a maintenance phase, during which the precise membership of each cluster is updated due to node mobility, addition of new nodes to the network, and removal of nodes from the network.
Analytical Model
Assuming an average of c adversary nodes and n legitimate nodes
in each cluster, the proportion of time that the c adversary nodes can launch a
sleep deprivation attack from a particular cluster is:
In Fig. 10 we have used the equation for pc,rr to see how likely the round robin scheme is to elect an adversary cluster head. Comparison of Figs. 10 and 8 illustrates that the round robin scheme makes it much more difficult for the adversary to become a cluster head. In fact, the adversary nodes are just as likely to become a cluster head as is any other node.

Probability that round robin scheme selects an adversary cluster head.
A nice property of the round robin scheme is that it only requires a single iteration to select a cluster head. Each node must keep track of exactly which nodes are in the cluster and which node is the current cluster head. Thus, when a new cluster head is needed, each node can independently determine who the new cluster head should be. However, this scheme requires that each sensor node must maintain a list indicating which nodes are in its cluster at all times. Such a list would require an unrealistic amount of per-node storage for larger clusters.
The lack of scalability that daunts the random vote scheme in Section 6.1 and the excessive overhead inherent to the round robin scheme in Section 6.2 motivated us to come up with the hash-based cluster head selection scheme, which we shall call the hash-based scheine for brevity. This scheme performs dynamic clustering in an attack and fault tolerant manner without excessive overhead.
Hashed Clustering Overview
In this scheme, each node generates a random number and then broadcasts their number's hash. This allows each node to commit to their particular number without revealing it until all participating nodes have likewise committed. This process ensures that a cluster head is selected at random, so long as there is at least one “honest” node participating in the algorithm.
To prevent a malicious node from claiming to be multiple nodes, we assume that every message has been authenticated using an authenticated broadcast scheme such as μTESLA [26].
The hash algorithm operates by having each participating node execute the following steps: Generate an integer, ri, using a pseudorandom number generator and
locally broadcast a commit message of the form 〈ID, H
(ID, r
i
)〉, where
ID denotes the node's identifier and H (·) denotes a
fixed length collision-resistant hash function. Wait for enough time to pass, To, that it is sufficiently unlikely
that any more commit messages will be received. Then locally broadcast a
list message 〈(ID1, &,
IDY)〉, where (IDt, &,
IDY) is a list of all IDs extracted from step 1, including the nodes own
ID as well. For each list message received, verify that the local list of IDs is the same as
the received list of IDs. Send a request commit message to any node whose ID is
listed in another node's list message, but is not listed in the
node's own list of IDs: 〈IDdest〉. For each request commit message received whose
IDdest field matches the node's own ID, reply by repeating the
original commit message. Wait for To seconds to pass. Then locally broadcast a
reveal message, to disclose r
i
:
〈ID, r
i
〉. Verify each r
i
with its associated
commit message. Wait for To seconds to pass. If any reveal messages
have not been received, transmit a request reveal message:
〈H (ID,
r
i
)〉. Any node that has a verified r
i
can respond to a
request reveal message. Given Y participating nodes, the cluster head will be the node whose ID matches
the following result:
The key observation regarding the security of this scheme is that every participating node must send out its commit message prior to receiving any reveal messages. This can be ensured with a high likelihood by selecting a sufficiently high value for To. Alternatively, this security could be guaranteed by building a communication scheme that is amenable to sensor networks and provides end-to-end reliability by utilizing current research efforts [30, 35].
Likelihood of an Adversary Cluster Head
In this section we analyze the likelihood of an adversary node being elected cluster head in the hash-based scheme.
Notice that the output of the hash-based scheme (i.e., step 9) will be a random integer so long
as at least one of the participating nodes is not an adversary node. This is because a random number
added to a nonrandom number yields a random number. Thus, the malicious nodes will not affect the
random output of the hash-based scheme by colluding. As the following equation indicates, the
probability that a adversary node is selected to become a cluster head is the same as any node in
the cluster:
Notice that the probability that an adversary becomes cluster head in the hash-based scheme is the same as in the round robin scheme (i.e., pc,h = pc,rr). Thus, Fig. 10 also applies to the hashed-based scheme.
In this section we derive a timing model to show that the hash scheme is capable of forming
clusters in a reasonable amount of time. Consider the hashing scheme within the context of a simple
communication model, where R is the rate at which data can be transmitted and the
total number of nodes that are participating in the algorithm is n +
c. In the hash algorithm, each of the n +
c nodes must generate a commit, list, and a
reveal message. The total amount of time spent transmitting n
+ c packets, each of which contains Msize bits,
is:
The probability that a given message is not received by at least one of the n + c
− 1 other nodes is pe. In this case, the node will have
to retransmit the message. The average number of times a given message is transmitted until it is
correctly received by all interested nodes is approximated as:
Each of the n + c nodes generates a single
commit message and a single reveal message. To account for
reliable transmission, each of these messages will be transmitted an average of
Nrsndl times, giving the total number of commit
messages and reveal messages as:
There is sufficient redundancy in having each node generate a list message, that we assume each unreceived commit and reveal message will be detected. Each node transmits its list message only once. Thus, NListALL, the total number of list messages generated, is n + c.
Each commit and reveal causes a request
message with probability pe. Thus, the average number of request
commit messages and request reveal messages is:
The sum of all commit, reveal, list, request commit, and request
reveal messages gives NrsndALL, the total number of packets
transmitted by n + c nodes on average. Given a transmission
rate of R, the total time spent by n + c
nodes communicating a total of NrsndAll packets is:
We estimate To with the amount of time required to reliably transmit
n + c messages:
While not included in our model, the actual value for To also depends
upon the expected size of a cluster, which is dependent upon sensor range and the density of nodes
in the network. Further, the time spent waiting in step 2 would be slightly less than it would be in
steps 5 and 7 as there are not retransmissions occurring during step 2. Since there are three points
in which the nodes wait for a time period of To, and we have the total
time spend communicating, the total time spent by the algorithm is:
In Fig. 11 we used the equation for Ttotal to illustrate the time that could be expected for the hash-based algorithm to execute. Each grouping of six bars corresponds to a different choice of pe and Msize. In order rom left to right, we have used (pe = .1, Msize = 400). (pe = .01, Msize = 400), (pe = .1, Msize = 300), (pe = .01, Msize = 300). Within each grouping we varied the number of nodes within the cluster (i.e., n + c) from 5 to 10. We do not consider which nodes amongst these n + c nodes are adversary nodes, as doing so does not change the amount of time the hash-based algorithm requires to complete. The most important feature that this figure indicates is that the amount of time required to select a cluster head in the hash-based scheme scales linearly with the number of nodes in the cluster. Thus, this approach is scalable. We also note that even with a very high error probability (i.e., pe = .1) our scheme completes in a reasonable amount of time.

Time required for hash-based scheme to select a cluster head.
To determine the energy consumed by the hash scheme, we perform an average case analysis upon a single node. Note that we assume that communication energy dominates computational energy.
Given that a sensor node on average transmits a total of NrsndAll/
(n + c) messages, the total energy that a node expends
transmitting is:
We assume that a node not sending a message is actively listening to the network: and the amount
of energy spent receiving is:
Thus, the total energy spent by a single node in the hash algorithm is:
In Fig. 12 we have utilized equation Etotal to determine the energy required for a node participating in the cluster head selection algorithm. This graph uses the same data points used in Fig. 11, except the y-axis of this graph refers to the total energy expended by a single node participation in cluster head selection. We can see from this graph that the hash-based scheme does not require excessive energy consumption on behalf of participating nodes, and thus is amenable for use in sensor networks.

Per-node energy required for hash-based scheme to select a cluster head.
In this paper we have shown a novel attack that an adversary can exploit upon sensor network applications that utilize distributed clustering. This attack, called the sleep deprivation attack, exploits the fact that conventional clustering algorithms rely upon the honesty of participating nodes. Thus, a malicious node can ensure its selection as cluster head, and consequently, it can launch a sleep deprivation attack against the network. In this attack, a malicious cluster head sends vietim nodes seemingly legitimate messages; however, the purpose of these messages is to keep its victims out of their low power sleep mode. The end result of this attack is greatly reduced node lifetime, potentially partitioning the network into disjointed pieces.
We also explain why an adversary would utilize a sleep depriation attack, by comparing it to a more aggressive attack where the victim nodes are barraged with requests. We have found that the sleep deprivation attack is attractive (from the perspective of an attacker) due to its low cost in terms of energy and communication. Further, this attack is not readily detected.
Given the dire consequences of this attack, we have proposed three schemes by which its impact can be reduced: 1) the random vote scheme, 2) the round robin scheme, and 3) the hashed-based scheme. We have found that the hashed-based scheme is superior to the other two methods in terms of resilience towards attack and required overhead.
Footnotes
Acknowledgments
This research is sponsored by the Defense Advance Research Projects Agency (DARPA), and administered by the Army Research Office under Emergent Surveillance Plexus MURI Award No. DAAD19-01-1-0504. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsoring agencies. This work is also supported by NSF CAREER 0093085 and DARPA/MARCO GSRC Grant. Sencun Zhu's work is supported by NSF Grant CNS-0524156.
