Sage Journals: Discover world-class research

Abstract

In the near future wireless sensor networks will be employed in a wide variety of applications establishing ubiquitous networks that will pervade society. The inherent vulnerability of these massively deployed networks to a multitude of threats, including physical tampering with nodes exacerbates concerns about privacy and security. For example, denial of service attacks (DoS) that compromise or disrupt communications or target nodes serving key roles in the network, e.g. sink nodes, can easily undermine the functionality as well as the performance delivered by the network. Particularly vulnerable are the components of the communications or operation infrastructure. Although, by construction, most sensor network systems do not possess a built-in infrastructure, a virtual infrastructure, that may include a coordinate system, a cluster structure, and designated communication paths, may be established post-deployment in support of network management and operation. Since knowledge of this virtual infrastructure can be instrumental for successfully compromising network security, maintaining the anonymity of the virtual infrastructure is a primary security concern.

Somewhat surprisingly, in spite of its importance, the anonymity problem has not been addressed in wireless sensor networks. The main contribution of this work is to propose an energy-efficient protocol for maintaining the anonymity of the virtual infrastructure in a class of sensor network systems. Our solution defines schemes for randomizing communications such that the cluster structure, and coordinate system used remain undetectable and invisible to an observer of network traffic during both the setup and operation phases of the network.

Keywords

wireless sensor networks energy-efficient protocols scalable protocols traffic anonymity

1. Introduction

Recent advances in nano-technology made it technologically feasible and economically viable to develop low-power, battery-operated devices that integrate special-purpose computing with low-power sensing and wireless communications capabilities [16], [23], [24], [40], [49], [55], [59]. It is expected that these small devices, referred to as sensor nodes, will be mass-produced making production costs negligible [20], [44], [60], [76]. Individual sensor nodes have a non-renewable power supply and, once deployed, must work unattended. We envision a massive random deployment of sensor nodes, numbering in the thousands or tens of thousands. Aggregating sensor nodes into sophisticated computation and communication infrastructures, called sensor networks, will have a significant impact on a wide array of applications including military, scientific, industrial, health, and domestic. The fundamental goal of a wireless sensor network is to produce, over an extended period of time, meaningful global information from local data obtained by individual sensor nodes [1], [11], [15], [28], [49], [55], [63], [64], [70].

However, a wireless sensor network is only as good as the information it produces [2]–[6], [8], [9], [12]–[14], [17]–[19], [45]. In this respect, perhaps the most important concern is information security. Indeed, in most application domains sensor networks will constitute a mission critical component requiring commensurate security protection [41], [45], [48], [71]–[75]. Sensor network communications must prevent disclosure and undetected modification of exchanged messages. Due to the fact that individual sensor nodes are anonymous and that communication among sensors is via wireless links, sensor networks are highly vulnerable to security attacks. If an adversary can thwart the work of the network by perturbing the information produced, stopping production, or pilfering information, then the perceived usefulness of sensor networks will be drastically curtailed. Thus, security is a major issue that must be resolved in order for the potential of wireless sensor networks to be fully exploited [21]–[24], [29]–[39]. The task of securing wireless sensor networks is complicated by the fact that the sensors are mass-produced anonymous devices with a severely limited energy budget and initially unaware of their location [1], [41]–[43], [51]–[53].

In many application domains, safeguarding output data assets, data produced by the sensor network and consumed by the end user (application), against loss or corruption is a major security concern. In these application domains, a sensor network is deployed into a hostile target environment for a relatively extended amount of time. The network self-organizes and works to generate output data that is of import to the application. For example, a sensor network may be deployed across a vast expanse of enemy territory ahead of a planned attack; the network system monitors the environment and produces reconnaissance data that is key to a mission planning application. Periodically, during the network lifetime, a mobile gateway, mounted on a person, land or airborne vehicle, or a satellite, collects the output data assets from the network system, to maintain an up to date state. This means the network system must store the output data assets from the time it is produced until it is collected. Therefore, securing the output data assets in the network is an important problem in this class of applications [7], [10], [15], [26], [27], [34], [45], [48], [50]–[52], [54], [56]–[58], [62], [63].

We view an attack on the output data assets in the sensor network as a type of denial of service attacks. This is based on the abstraction that output data is stored in a logical repository, and, that access to this output data repository constitutes, in effect, a service provided by the network system to the application; corruption or loss of output data denies the application access to that service. Many wireless sensor networks are mission-oriented, must work unattended, and espouse data-centric processing. Consequently, they are significantly different in their characteristics from ad-hoc networks; security solutions designed specifically for wireless sensor networks are therefore required.

1.1 What is Anonymity?

With the recent growth and wide acceptance of novel applications including e-banking, e-commerce, e-voting, and e-government, concerns about privacy and security have become extremely important. In all these applications anonymity protects the identity of the sender or receiver and guarantees that both parties involved in a communication transaction remain anonymous to each other. Recent years have seen a flurry of activity and many anonymous communication systems have been developed for the Internet [3], [7], [8], [9], [11], [32], [33], [34], [41], [43], [61], [62]. Most of the work on anonymity is concerned with sender anonymity, receiver anonymity, and mutual anonymity. Of the various forms of anonymity mentioned above, sender anonymity seems to be the most critical in current applications. In e-voting, for example, a vote should not be traceable back to the voter that cast it. Likewise, users may not wish to disclose their identities when visiting web sites. Quite recently, traffic anonymity has also received well-deserved attention in the literature. Indeed, if an adversary can identify traffic patterns and routers effecting them, the security risks to the traffic increase multifold. In a homeland security context, a group of terrorists may attempt a surgical operation taking out those routers whose loss will inflict the heaviest damage on the network.

Recently, the problem of securing ad-hoc networks has received a great deal of well-deserved attention in the literature [5], [6], [9], [29], [30], [33], [42], [48]. Somewhat surprisingly, however, in spite of its importance, the anonymity problem has not been addressed in wireless sensor networks.

We view this work as an initial contribution towards developing a lightweight solution for the anonymity problem in wireless sensor networks. In this paper, we focus primarily on structure anonymity in a wireless sensor network. Although the exact statement of the problem we address are presented in Sec. 5, suffice it to say that the basic infrastructure of a wireless sensor network that is constructed immediately after deployment is a coordinate system that affords natural clustering. Our main contribution is to protect the coordinate system from an external adversary by making the process of acquiring the coordinate system anonymous and, thus, invisible, to the adversary.

2. The Network Model

The network model used in this paper is a derivative of the model introduced in [46], [67]. Specifically, we assume a class of wireless sensor networks consisting of a large number of sensors nodes randomly deployed in the environment of interest. A training process, as explained below, establishes a coordinate system and defines a clustering of all nodes. In post training, the network undergoes multiple operation cycles during its lifetime. The training process also endows the role of sink upon one or more of the defined clusters. The sink role is transient, however, since new sink clusters are designated at the beginning of each operation cycle. Each sink cluster, henceforth called sink, acts as a repository for a portion of the sensory data, generated in the network during an operation cycle. At the end of an operation cycle, each sink transfers data stored in its repository to a gateway. In the following we describe the three primary entities in our network model in more detail.

2.1 The Sensor Node

We assume a sensor to be a device that possesses three basic capabilities; sensing, computing, and communication. At any point in time, a sensor node is either performing one of a fixed set of sensor primitive operations, or is idle (asleep).

We assume that individual sensor nodes have four fundamental constraints:

Sensors are anonymous; initially a sensor node has no unique identifier,

Each sensor has a limited non-renewable energy budget,

Each sensor attempts to maximize the time it is in sleep mode; a sensor wakes up at specific (possibly random) points in time for short intervals under the control of a timer, and

Each sensor has a modest transmission range, perhaps a few meters with the ability to send and receive over a wide range of frequencies. In particular, communication among sensor nodes in the sensor network must be multi-hop.

2.2 The Sink

The sink granularity in our network model is a cluster in a trained network. For each operation cycle a number of clusters are designated to serve as sinks. This means that all nodes in a sink cluster serve as sink nodes. Coarser sink granularity supports higher sink storage capacity, and thus potentially longer operation cycles. However, coarser sink granularity, as envisioned here, comes at a potentially higher risk of anonymity attacks due to the space correlation among sink nodes. If it is discovered that a node, x, is a sink node then it immediately follows that there exists at least one other sink node (typically more) in the vicinity of x. Thus, the success of an anonymity attack in our model is sensitive to the probability of identifying the first node in a sink. One approach to decrease the latter probability is to have only a subset of the nodes in a sink cluster serve as sink nodes. There is a tradeoff between sink granularity, and hence its capacity and operation longevity, and the amount of security a sink has against anonymity attacks.

A notable advantage of our sink model is that sinks are dynamic configurations of regular nodes in the sensor network, as opposed to being, for example, special supernodes. This makes the system less complex to design and operate, and eliminates a would-be attractive focus for anonymity attacks. Another major advantage is that the sink, in our model, is not a single point of failure, in two distinct ways. First, the network uses multiple sink entities, as opposed to a single sink entity. Second, a sink entity is not a single node; rather it is a set of nodes.

The solution proposed in this paper for the anonymity problem uses whole cluster granularity for the sink. It encompasses techniques for randomly and securely choosing sinks for an operation cycle, and maintaining the anonymity of these sinks.

2.3 The Gateway

The gateway is an entity that connects the sensor network system to the outside world. The gateway is not constrained in mobility, energy, computation, or communication capabilities. There are two basic functions for the gateway in our network model:

(i)
Training. The gateway performs the network training process, post deployment. For training purposes the gateway is assumed to be able to send long-range, possibly, directional broadcasts to all sensors. It should be noted that our training process does not involve any transmission from the sensor nodes deployed in the network. Thus, in principle, the gateway does not have to be geographically co-located with the sensor nodes during the training process.
(ii)
Harvesting (data collection). At the end of an operation period, the gateway must collect sensory data stored in each sink. In a simple collection scenario the gateway traverses the deployment environment to collect data from all the sinks. If we assume that nodes comprising a sink perform collaborative data fusion, then the harvesting process requires a relatively short period of time. Specific harvesting protocols are beyond the scope of this paper.
(iii)
Harvesting (data collection). At the end of an operation period, the gateway must collect sensory data stored in each sink. In a simple collection scenario the gateway traverses the deployment environment to collect data from all the sinks. If we assume that nodes comprising a sink perform collaborative data fusion, then the harvesting process requires a relatively short period of time. Specific harvesting protocols are beyond the scope of this paper.

In our proposed solution for the anonymity problem discussed in detail in Sec. 4, the gateway is assigned the additional function of a group key management server for the sensor network.
3. Network Organization and Clustering

Figure 1(a) features an untrained sensor network immediately after deployment in an environment that is represented here as a 2-dimensional plane. For simplicity, we assume that the trainer is centrally located relative to all deployed nodes. Namely, considering the nodes to be points in the plane, we assume, in this paper, that the trainer is located at the center of the smallest circle in the plane that contains all deployed nodes. It should be noted that this is not a necessary condition. To be specific, our proposed training scheme is applicable if the trainer is located either at the center of, or at a point outside of the smallest circle that contains all deployed nodes.

Figure 1

(a) An untrained sensor network with a centrally located trainer; (b) A trained sensor network

The primary goal of training is to establish a coordinate system, to provide the nodes location awareness in that system, and to organize the nodes into clusters. The coordinate system, and clustering are briefly explained next. We refer the interested reader to [20] for an in-depth description of the training process.

3.1 The Coordinate System

The training process establishes a polar coordinate system as exemplified by Figure 1(b). The coordinate system divides the sensor network area into equiangular wedges. In turn, these wedges are divided into sectors by means of concentric circles or coronas centered at the trainer location. Corona radii can be determined based on several criteria, e.g. in [46], [67] they are designed to maximize the efficiency of sensors-to-sink multihop communication. The intersection of every wedge and corona defines a unique sector; each sector is uniquely identifiable by the combination of its unique wedge identifier, and unique corona identifier. The training process guarantees that each node belongs to one and only one sector in the coordinate system, and that each node knows the identity of its sector [46], [67].

Let c, and w be, respectively, the set of coronas, and the set of wedges defined by the training process. The resulting coordinate system can thus be formally represented by {(r₀, r₁, …, r_|c|–1), θ}, where r_i is the radius of corona i, 0 ≤ i ≤|c|–1, θ is the wedge angle, and |w|= 2π/θ . A fundamental assumption here is that any coordinate system is designed such that all nodes located in the same sector can communicate using direct (single hop) transmission.

3.2. Clustering

A major advantage of our coordinate system is that sectors implement the concept of clustering (at no additional cost). A sector effectively constitutes a cluster; clusters are disjointed, and are uniquely identifiable. All nodes located in the same sector are members of the same cluster, and have the same location coordinates, namely, the corona and wedge identifiers corresponding to that sector. This clustering scheme is ideally suited for sensor nodes that are intrinsically anonymous. Wadaa et al. proposed in [67] a scalable training protocol where each untrained node incurs a communication cost equal to log|w|+log|c|, and the nodes do not transmit any messages during the training process.

4. The Work Model

The work model defines how sensor nodes work collaboratively to generate and store sensory data during an operation cycle. We propose a work model that is based on two principles:

Intra-cluster activity generates sensory data of interest to the application, and

Inter-cluster activity transports each granule of sensory data to a sink, randomly chosen from among those available, for storage.

4.1 Intra-cluster Activity

In our model, the sensory data resulting from intra-cluster activity encodes states of a process of interest. Namely, we assume that the goal of intra-cluster activity is to monitor a process (or phenomenon), and report on its local state at any point in time. The state space of the phenomenon is given by {s₀,s₁,s₂, …, s_z}. State s₀denotes the normal state, and each of s_i, 1 ≤ i ≤ z denotes an exception state. The assumption here is each state s_i, 1 ≤ i ≤ z, corresponds to an application-defined exception of a particular type. The normal state corresponds to the fact that no exception of any type is detected.

We propose a transaction-based model for managing the computation and reporting of target process states. The model is a specialization of a transaction-based management model for sensor networks introduced in [46], [67]. In this model, intra-cluster activity proceeds as follows. For a given cluster, subsets of nodes located in the cluster dynamically band together forming workforces.

Periodically, members of each workforce collaborate to perform an instance of a state computation transaction preloaded into each node. The transaction computes and reports the local process state. Note that the system allows for a fresh transaction to be downloaded to the nodes at the beginning of each operation cycle. In the simplest case, performing an instance of the state computation transaction entails that each member in the corresponding workforce perform a sensing operation and formulate a node report. A specific member of the workforce, designated as a transaction instance manager, then receives all node reports, and formulates a Transaction Instance Report (TIR). The TIR is the encoding of the local process state of interest at the time. This TIR is subsequently transported to a sink for storage. In principle, after transmitting the TIR the corresponding workforce disbands. For simplicity, we assume that at most one transaction instance is in progress in a given cluster at any given point in time.

The state diagram in Figure 2 represents the behavior of an arbitrary workforce in a cluster assuming the special case of a target process that has one normal state, s0, and one exception state, s1. T in the figure denotes the state computation transaction.

Figure 2

A model for workforce behaviour assuming a two-state target process and a canonical transaction

Two important design parameters in the above transaction-based model are workforce size, and workforce setup. These are discussed in the following.

Workforce size

This is application dependent. Applications negotiate QoS requirements, for example, the ‘confidence level’ associated with TIRs. These QoS parameters are, in turn, mapped to constraints at the transaction level. A constraint we assume in the anonymity solution proposed in this paper is that the average workforce size must be larger than or equal to λ, where λ is derived from application-level QoS parameters.

Workforce setup

This is governed by criteria such as load balancing or energy conservation, and thus represents a system concern. We distinguish two basic approaches to workforce setup, static and dynamic. The dynamic approach trades dynamic load balancing at the node level, and robustness to node failures for added delay time and energy overhead of the setup protocol. The static approach trades savings in energy and time of static setup for dynamic load balancing at the node level and robustness to node failures. In our proposed anonymity solution, we organize the node population of a cluster, prior to each operation cycle, into a fixed number of static workforces that have the same size on the average. Workforces are tasked to work (do an instance of the state computation transaction) in a round-robin fashion. The goal of our approach is to eliminate the energy and time overhead of dynamic setup while achieving load balancing at the coarser granularity of a workforce.

4.2 Inter-cluster Activity

As indicated earlier, the goal of inter-cluster activity in our work model is to route TIRs from their clusters of origin to the sinks, by means of multi-hop communication. We define a hop in a route as a direct transmission from one cluster to a neighbor cluster. A cluster u_j is a neighbor of a cluster u_i if and only if both u_j and u_i are located in the same corona, or the same wedge, for all i and j, i ≠ j. It follows that in any instance of the coordinate system defined in Sec. 3, each cluster has either three or four neighbors. The set of all neighbors of a cluster u_i is called the neighborhood of u_i. In the our proposed anonymity solution we define a distributed inter cluster routing protocol that yields optimal routes in terms of the number of hops from source to sink, and is highly scalable in the number of clusters in the network. Scalability can be attributed to two characteristics of the protocol. First, the protocol uses no dynamic global or regional state information. This eliminates the need for control messages to support routing. Second, the protocol uses distributed (incremental) route computation; the destination of hop i, computes, in turn, the destination of hop i+1,i≥1. In the remainder of this paper we assume the availability of a MAC layer that supports inter-cluster communication.

5. The Anonymity Problem

In this section we formulate a definition for the anonymity problem addressed in this paper. The problem is defined in the context of the network system described earlier. First, we introduce an anonymity threat model.

5.1 The Anonymity Threat Model

The threat model assumed in this paper emanates from a data-centric view of the sensor network. The model is predicated on the assumption that the end-goal of anonymity attacks on the sensor network is to identify and eliminate the minimum number of nodes to inflict maximum loss of data assets; eliminating a node means disabling that node so that it is permanently non operational. In our sensor network model, TIRs are the data assets of import to the end user (application). For any operation cycle, if a sink suffers a permanent failure before transferring the contents of its TIR repository to the gateway, then a portion of the data assets corresponding to the cycle is irrevocably lost. Therefore, sinks, or nodes comprising them to be precise, are the assumed targets of anonymity attacks in our model. Specifically, the goal of the adversary system is to eliminate all sink nodes. There are two main approaches to eliminating sink nodes:

Brute-Force (Sink nodes are not identified)

This may take the form of randomly eliminating nodes in the network on the assumption that, statistically, some sink nodes will be eliminated in the process. Coarse sink granularity, and sink redundancy mitigate the risk of loss of data assets as a result of this type of attack. A trivial special case is the massive elimination of all nodes in the network.

Smart (Sink nodes are identified)

The adversary system analyzes network traffic to deduce information about network topology, traffic flow patterns, and other system attributes. The goal is to discover, i.e. compromise the anonymity of, sink nodes, and, hence, eliminate them.

In this paper we assume the adversary system engages in smart elimination attacks. The specifics of the architecture and the implementation of the adversary system are assumed unknown.

5.2 Terminology and Notation

The main goal of this subsection is to establish terminology and notation that will be used in our solution to the anonymity problem.

Trudy	Denotes the adversary system
m	A message transmitted in the sensor network system post deployment. (Note that the transmitter is either a sensor node or the gateway.)
ts(m)	A global time stamp assigned by Trudy to message m,
l(m)	The unique location, in an arbitrary coordinate system used by Trudy, of the transmitter of message m in the 2-dimensional deployment plane.
r	^node,r^gateway The nominal transmission radius of a sensor node, and the gateway, respectively
cvr(m)	This is the cover of message m. Specifically, cvr(m) is the set of nodes that are located in the circular area with radius r^node, and center l(m) in the deployment plane
trace(m)	The trace of message m; if m is routed along a path of length g, trace(m) is the sequence of messages (m⁽¹⁾ m⁽²⁾,⃛,m^(g)), m(ⁱ) is the retransmission of m, or an encryption thereof, over hop number i, 1 ≤ i ≤ g. Note that m⁽¹⁾=m
source(m)	The transmitter of message m
destination(m)	The designated receiver of message m

The assumptions underlying our anonymity threat model can be summarized as follows:

A. Pre-deployment

All nodes are trusted

Nodes are in a secure environment

Trudy does not have access to any message m transmitted in the system.

B Post deployment (training and operation cycles)

Trudy receives every message transmitted in the system. Note that receiving a message does not imply being able to interpret it. A message m transmitted in the system is represented in Trudy's system as follows:

(m, t s (m), l (m), c v r (m))

5.3 Anonymity Problem Statement

Let I be an arbitrary time interval, that starts post deployment, and let the set M = {(m_i, ts(m_i), l(m_i), cvr(m_i)) |1 ≤ i ≤ h} be the set of all messages transmitted in the system (and hence recorded by Trudy) during the interval I. Also, let the coordinate system, O, established by training be given by {(r₀,r₁, …, r |c| −1)q}, and the set of all nodes located in sink clusters be denoted by S.

The anonymity problem (from Trudy's point of view) can thus be stated as follows:

Given:

M = {(m_{i}, t s (m_{i}), l (m_{i}), c v r (m_{i})) | 1 \leq i \leq h}

(1)

Find:

m_{q} \in M : (\exists m_{p} \in M : t r a c e (m_{p}) = (m_{p}^{(1)}, m_{p}^{(2)}, \dots, m_{p}^{(g_{p})}) \land m_{q} = m_{p}^{(g_{p})}), g_{p} \geq 1

(2)

Note that for the message m_q in (2), destination(m_q) ∊ S. In general, for each message m_q that satisfies (2), it follows that

\exists x : x \in c v r (m_{q}) \land x \in S

The challenge for the sensor network system is to devise training, intra cluster, and inter cluster protocols that minimize the probability that the anonymity problem stated in equations (1), and (2) is solved, for arbitrary O,I,S, and M. In this work we only look at the problem of providing anonymity during the training period.

6. Providing Anonymity for Sensor Network Training

The main goal of this section is to propose a protocol for training that addresses the anonymity problem formulated above. The primary goal of the training protocol is to establish the canonical coordinate system,O_s, for the network, anonymous to Trudy. For a given sensor network system, the canonical coordinate system is the instance of the polar coordinate system described in 3.4.1 that has the maximum precision. O_sdefines the set of canonical coronas, c_s, and the set of canonical wedges, w_s; we assume that |cs| and |w_s| are powers of 2. O_s is defined by ${(r_{0}, r_{1}, \dots, r_{| C_{s} | - 1}), θ_{s}}, r_{i} = (i + 1) \times ε_{s}, 0 \leq i \leq | c_{s} | - 1$ , where ∊_s and θ_s are, respectively, the smallest corona width, and the smallest wedge angle for the system; ∊_s, and θ_s characterize the system precision.

Post training, the coordinate system used during any operation cycle is derived from the canonical coordinate system using three integer parameters, α, β , and γ . Here, α, β, and γ represent, respectively, wedge rotation, wedge grouping, and corona grouping parameters. Let C(x,O) and W(x,O) denote, respectively, the corona, and the wedge where node x is located according to coordinate system O. For a given operation cycle, e, if the rotation and grouping parameters are α, β , and γ , then the coordinate system used for cycle e is defined as follows:

O_{e} = {(r_{0}, r_{1}, \dots, r_{| c_{e} | - 1}), θ_{e}}, w h e r e r_{i} = (i + 1) \times ε_{e}, 0 \leq i \leq | c_{e} | - 1, ε_{e} = γ_{e} \times ε_{s}, θ_{e} = β_{e} \times θ_{s}

Note that α_e ∊ [0,| w_s | −1], β_e ∊ [0, log | w_s |], and γ_e ∊ [0, log | c_s |]. The corona, and wedge of x according to O_e are defined as follows,

C (x, O_{e}) = C (x, O_{s}) d i v 2^{(log | c_{s} |) - γ_{e}}

(3)

W (x, O_{e}) = ((W (x, O_{s}) + α_{e}) mod | w_{s} |) d i v 2^{(log | w_{s} | - β_{e})}

(4)

In equation (3) above, γ_e determines the corona precision of the coordinate system O_e, the minimum precision (a single corona) corresponds to γ_e and the maximum precision (that of the canonical coordinate system) corresponds to γ_e = log | c_s |. In equation (4) β _e determines the wedge precision of O_e in an analogous manner. The left hand operand of the div operator in (4) is a translation for W(x,O_s) about the true anchor point an amount equal to α _e canonical wedges.

We are now in a position to present the details of our proposed anonymity-compliant training protocol.

6.1 Preconditions

(i)
Sensor nodes are randomly and uniformly deployed in a deployment area. The deployment area completely contains a circular area called the network area; nodes located in the network area will comprise our trained sensor network. The mission of the nodes that are located outside the network area is to generate fake message traffic to help keep the network area anonymous.
(ii)
The gateway is mobile
(iii)
Pre deployment, the following is loaded into each sensor node:
Secret key, K_master used for decrypting training protocol messages from the gateway. Also, K_master is used to derive the keys K_α, K_β, and K_γ, as proposed in [12]. K_α, K_β, and K_γ are used to generate at random values for α, β, γ , respectively, for the successive operation cycles.

The parameters q_s, ∊_s, D, and r^gateway. D is the diameter of the network area, we assume r^gateway » D.

(iv)
Internal clocks in all sensor nodes are synchronized to the gateway.
6.2 Training Protocol (gateway side)

(i)
Do a random traversal of the deployment area, visiting a set of random anchor points A = {a₁,a₂, …, a_A,}, For each a_i, 1 ≤ i ≤| A |, do: i.1.
Transmit a call-for-training message: Transmit an omni directional broadcast message using r^gateway. The message is encrypted by K_master and contains a Boolean flag f that identifies a_i as either the true anchor point or a false anchor point; the true anchor point is the geographical center of the circular network area. ii.2.
Corona train: using the sink side of the training protocol described in [67] do corona training to establish coronas for O_s, such that $| c_{s} | = \frac{r^{g a t e w a y}}{ε_{s}}$

iii.3.
Wedge train: using the analogous sink side of the wedge training protocol described in [67], do wedge training to establish the wedges for O_s.

(ii)
Terminate the protocol

Note that the corona training done in step i.2 covers an area considerably larger than the network area. This means that corona training, in this case, defines fake coronas that lie outside the network area (i.e. at a distance more than the diameter D from the true anchor point). The objective is to help keep the diameter D unknown. Because sensor nodes know D, each node, after learning the canonical corona it is located in, can determine if it is located in the network area, and hence, in the trained network. The multiplicity and randomness of anchor points help keep the true anchor point unknown.
6.3 Training Protocol (node side)

In the following assume node x is the node executing the protocol.

(i)
Compute | c_s | = r^gateway / ∊_s, | w_s | = 2π / θ_s
(ii)
Do forever: i.1.
Receive the next call-for-training message: receive and decrypt, using K_master, the next call-for-training message, m.
ii.2.
If the Boolean flag f in m is true, then do: ii.2.1.
HGet corona trained: invoke the node side of the training protocol described in [67] to get corona trained to learn the canonical corona number you are located in, c(x,O_s).
ii.2.2.
Compute your corona radius: Compute r = (C(x,O_s) + 1) × ∊_s. (Note that if r ≤ D then you know you are located in the network area, and thus will be a node in the trained network, otherwise you know you do not belong to the trained network.)
ii.2.3.
If you belong to the trained network, do: ii.2.3.1.
Compute | c_s | = D/∊_s
ii.2.3.2.
Get wedge trained: invoke the node side of the training protocol described in [20] to get wedge trained to learn the canonical wedge number you are located in, W(x,O_s). ii.2.3.3.
Using K_α,K_β, and K_γ generate via a random number generator (or a preloaded CBC block as described in [12]), respectively, the parameters α ₁,β₁, γ ₁ for the first operation cycle.

ii.2.3.4.
Compute
$\begin{aligned} C (x, O_{1}) = C (x, O_{s}) d i v 2^{(log | c_{s} | - γ_{1})}, and \\ W (x, O_{1}) = ((W (x, O_{s}) + α_{1}) mod | w_{s} |) d i v 2^{(log | w_{s} | - β_{1})} \end{aligned}$

ii.2.3.5.
Terminate the protocol.

Else

Sleep for |w_s| message times; terminate the protocol.

Else

Sleep for |c_s|+|w_s| message times.

7. Concluding Remarks and Directions for Future Work

It is widely recognized that sensor network research is in its infancy. In particular, there is precious little known about how to get sensor networks to self-organize in a way that maximizes the operational longevity of the network and that guarantees a high level of availability in the face of potential security attacks. However, given the characteristics of sensor networks, anonymity protocols developed for wired, cellular, or ad-hoc networks do not apply.

We view this paper as an initial contribution towards developing a lightweight solution for the anonymity problem in wireless sensor networks. Research is underway toward a solution that provides security not only for the various individual layers of the system but also for the entire system in an integrated fashion.

References

Akyildiz

I. F.

Sankarasubramanian

, and Cayirci

, “Wireless sensor networks: A survey,” Computer Networks, vol. 38, no. 4, pp. 393–422, Month 2002.

Anderson

, and Kuhn

, “Tamper resistance a cautionary note,” Proceedings of the Second Usenix Workshop on Electronic Commerce, 1996, pp. 1–11.

Ateniese

Herzberg

Krawczyk

, and Tsudik

, “Untraceable mobility or how to travel incognito,” Computer Networks, vol. 31, no. 8, pp. 871–884, Month 1999.

Bahl

Russell

Wang

Y. M.

Balachandran

Voelker

G. M.

, and Miu

, “PAWNs: satisfying the need for ubiquitous secure connectivity and location services,” IEEE Wireless Communications, vol. 9, no. 1, pp. 40–48, Month 2002.

Basagni

Herrin

Rosti

, and Bruschi

, “Secure pebblenets,” Proceedings of MobiHoc, 2001.

Basagni

Mastrogiovanni

, and Petrioli

, “A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks,” Proceeding of IEEE MASS, 2004.

Berthold

Federrath

, and Köhntopp

, “Project anonymity and unobservability in the Internet,” Proceedings of Computers Freedom and Privacy (CFP 2000), Workshop on Freedom and Privacy by Design, 2000.

Beresford

, and Stajano

, “Location privacy in pervasive computing,” Pervasive Computing, vol. 2, no. 1, pp. 46–55, Month 2003.

Capkun

Hubaux

J.-P.

, and Jakobsson

, “Secure and privacy-preserving communication in hybrid ad hoc networks,” EPFL-IC Tech. Rep. IC/ 2004/10, 2004.

10.

Cardei

, and Du

D. Z.

, “Improving wireless sensor network lifetime through power aware organization,” ACM Wireless Networks, in press.

11.

Carman

D. W.

Kruus

P. S.

, and Matt

B. J.

, “Constraints and approaches for distributed sensor network security,” Tech. Rep. 00-010, NAI Labs, 2000.

12.

Carman

D.W.

Matt

B.J.

, and Cirincione

G.H.

, “Energy-efficient and low-latency key management for sensor networks.,” Proceedings of the twenty-third. Army Science Conference, 2002.

13.

Chan

, and Perrig

, “ACE: An emergent algorithm for highly uniform cluster formation,” Proceedings of the First European Workshop on Sensor Networks (EWSN), LNCS 2920, January 2004.

14.

Chan

Perrig

, and Song

, “Random key pre-distribution schemes for sensor networks,” Proceedings of IEEE Symposium on Security and Privacy. Oakland, CA, 2003.

15.

Culler

Estrin

, and Srivastava

, “Overview of sensor networks,” IEEE Computer, vol. 31, no. 8, pp. 41–49, Month 2004.

16.

Delin

K. A.

, and Jackson

S. P.

, “The sensor web: A new instrument concept,” Proceedings of SPIE Symposium on Integrated Optics, 2001.

17.

DiPietro

Mancini

L. V.

, and Jajodia

, “Providing secrecy in key management protocols for large wireless sensor networks,” Journal of AdHoc Networks, vol. 1, no. 4, pp. 455–468, 2003.

18.

DiPietro

Mancini

L. V.

, and Mei

, “Random key assignment for secure wireless sensor networks,” Proceedings of the First Workshop on Security in Ad Hoc and Sensor Networks, 2003.

19.

Deng

Han

Y. S.

Chen

, and Varshney

, “A key management scheme for wireless sensor networks using deployment knowledge,” Proceedings of IEEE INFOCOM 04, 2004.

20.

DUST™ Networks, M1010 mote http://www.dust-inc.com/pdf/M1010-Mote.pdf (accessed 02/03/05).

21.

Ephremides

Wieselthier

, and Baker

, “A design concept for reliable mobile radio networks with frequency hopping signaling,” Proceedings of the IEEE, vol. 75, no. 1, pp. 56–73, 1987.

22.

Eschenauer

, and Gligor

, “A key management scheme for distributed sensor networks,” Proceedings of the Ninth ACM Conference on Computer and Communications Security, 2003.

23.

Estrin

Culler

Pister

, and Sukhatme

, “Instrumenting the physical world with pervasive networks,” Pervasive Computing, vol. 1, no. 1, pp. 59–69, Month 2002.

24.

Estrin

Govindan

Heidemann

, and Kumar

, “Next century challenges: Scalable coordination in sensor networks,” Proceedings of MOBICOM, 1999.

25.

Golumbic

, Algorithmic graph theory and perfect graphs. New York: Academic Press, 1980.

26.

Gracanin

Eltoweissy

Olariu

, and Wadaa

, “On modeling wireless sensor networks,” Proceedings of the IEEE Workshop on Mobile Ad Hoc and Sensor Networks, 2004.

27.

Gracanin

Eltoweissy

Olariu

, and Wadaa

, “Extensible wireless sensor networks,” Journal of Wireless Networks, in press, 2005.

28.

Hemingway

Brunette

Anderl

, and Boriello

, “The flock: Mote sensors sing in undergraduate curriculum,” IEEE Computer, vol. 37, no. 8, pp. 72–78, 2004.

29.

Y.-C.

Johnson

D. B.

, and Perrig

, “SEAD: Secure efficient distance vector routing in mobile wireless ad hoc networks,” Proceedings of the Fourth Workshop on Mobile Computing Systems and Applications, 2002.

30.

Hubaux

Buttyan

, and Capkun

, “The quest for security in mobile ad hoc networks,” Proceedings of MobiHoc, 2001.

31.

Jones

Wadaa

Olariu

Wilson

, and Eltoweissy

, “Towards a new paradigm for securing wireless sensor networks,” Proceedings of the Workshop on New Security Paradigms, 2003.

32.

Karlof

, and Wagner

, “Secure routing in sensor networks: attacks and countermeasures,” Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications, 2003.

33.

Kong

Hong

, and Gerla

, “An anonymous on demand routing protocol with untraceable routes for mobile ad hoc network,” UCLA Computer Science Tech. Rep. 030020, 2003.

34.

Lampson

, “Computer security in the real world,” IEEE Computer, vol. 37, no. 6, pp. 37–48, Month 2004.

35.

Levis

Lee

Welsh

, and Culler

, “TOSSIM: Accurate and scalable simulation of entire tinyOS applications,” Proceedings of the First International Conference on Embedded Networked Sensor Systems, 2003.

36.

Liu

, and Ning

, “Establishing pairwise keys in distributed sensor networks,” Proceedings of the Tenth ACM Conference on Computer and Communications Security, 2003.

37.

Liu

, and Ning

, “Location-based pairwise key establishments for static sensor networks,” Proceedings of ACM Workshop on Security in Ad Hoc and Sensor Networks, 2003.

38.

Liu

, and Ning

, “Multi-level μTESLA: A broadcast authentication system for distributed sensor networks,” ACM Transactions in Embedded Computing Systems, 2004.

39.

Marti

Giuli

Lai

, and Baker

, “Mitigating routing misbehavior in mobile ad hoc networks,” Proceedings of ACM MOBICOM, 2000.

40.

Martinez

Hart

J. K.

, and Ong

, “Environmental sensor networks,” IEEE Computer, vol. 37, no. 8, pp. 50–56, Month 2004.

41.

Menezes

A. J.

van Oorschot

, and Vanstone

, Handbook of Applied Cryptography. CRC Press: Boca Raton, 1996.

42.

Molva

Samfat

, and Tsudik

, “Authentication of mobile users,” IEEE Network, vol. 8, no. 2, pp. 26–34, Month 1994.

43.

Montenegro

, and Castelluccia

, “Statistically unique and cryptographically verifiable (SUCV) identifiers and addresses,” Proceedings of the Symposium Network and Distributed System Security, 2002.

44.

National Research Council , Embedded Everywhere. Washington, DC: National Academies Press, 2001.

45.

Newsome

Shi

Song

, and Perrig

, “The sybil attack in sensor networks: Analysis and defenses,” Proceedings of IEEE International Conference on Information Processing in Sensor Networks, 2004.

46.

Olariu

Wadaa

Wilson

, and Eltoweissy

, “Wireless sensor networks: leveraging the virtual infrastructure,” IEEE Network, vol. 18, no. 4, pp. 51–56, Month 2004.

47.

Olariu

, and Xu

, “A virtual infrastructure for massively deployed sensor networks,” Computer Communications, in press, 2005.

48.

Papadimitratos

, and Haas

Z. J.

, “Secure routing for mobile ad hoc networks,” Proceedings of Communication Networks and Distributed Systems, 2002.

49.

Park

Locher

Savvides

Srivastava

M. B.

Chen

Muntz

, and Yue

, “Design of a wearable sensor badge for smart kindergarten,” Proceedings of the Sixth International Symposium on Wearable Computers, 2002.

50.

Pearlman

M. R.

Haas

Z. J.

Sholander

, and Tabrizi

S. S.

, “On the impact of alternate path routing for load balancing in mobile ad hoc networks,” Proceedings of MobiHoc, 2000.

51.

Perrig

Canetti

Tygar

, and Song

, “The TESLA broadcast authentication protocol,” RSA CryptoBytes, vol. 5, no. 2, pp. 2–13, Month 2002.

52.

Perrig

Szewczyk

Wen

Culler

, and Tygar

J. D.

, “SPINS: Security protocols for sensor networks,” Wireless Networks, vol. 8, no. 5, pp. 521–534, 2002.

53.

Perrig

Stankovic

, and Wagner

, “Security in wireless sensor networks,” Communications of the ACM, vol. 47, no. 6, pp. 53–57, Month 2004.

54.

Pfitzmann , and Köhntopp

, “Anonymity, unobservability, and pseudonymity — a proposal for terminology,” In Federrath

ed., DIAU'00 LNCS 2009, 2000, pp. 1–9.

55.

Polastre

Szewcyk

Mainwaring

Culler

, and Anderson

, “Analysis of wireless sensor networks for habitat monitoring,” In Sivalingam

Raghavendra

, & Znati eds., Wireless Sensor Networks. Kluwer Academic, 2004, pp. 399–423.

56.

Przydatek

Song

, and Perrig

, “SIA: Secure information aggregation in sensor networks,” Proceedings of the First ACM Conference on Embedded Networked Sensor Systems, 2003.

57.

Reed

M. G.

Syverson

P. F.

, and Goldschlag

D. M.

, “Anonymous connections and onion routing,” IEEE Journal on Selected Areas in Communications, vol. 16, no. 4, 1998.

58.

Reiter

M. K.

, and Rubin

A. D.

, “Crowds: Anonymity for web transactions,” ACM Transactions on Information and System Security, vol. 1, no. 1, pp. 66–92, 1998.

59.

Ryokai

, and Cassell

, “StoryMat:A play space for collaborative storytelling,” Proceedings CHI'99, 1999.

60.

Saffo

, “Sensors, the next wave of innovation,” Communications of the ACM, vol. 40, no. 2, pp. 93–97, Month 1997.

61.

Samfat

Molva

, and Asokan

, “Untraceability in mobile networks,” Proceedings of ACM MOBICOM, 1995.

62.

Shields

, and Levine

B. N.

, “A protocol for anonymous communication over the Internet.,” Proceedings of the ACM Conference on Computer and Communications Security, 2000.

63.

Sohrabi

Gao

Ailawadhi

, and Pottie

, “Protocols for self-organization of a wireless sensor network,” IEEE Personal Communications, vol. 7, no. 5, pp. 16–27, Month 2000.

64.

Sohrabi

, “Methods for scalable self-assembly of ad hoc wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 3, no. 4, pp. 317–331, 2004.

65.

Srivastava

Muntz

, and Potkonjak

, “Smart Kindergarten: Sensor-based wireless networks for smart developmental problem-solving environments,” Proceedings of ACM MOBICOM, July 2001.

66.

Szewczyk

Polastre

Mainwaring

Anderson

, and Culler

, “An analysis of a large scale habitat monitoring application,” Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems, 2004.

67.

Wadaa

Olariu

Wilson

Eltoweissy

, and Jones

, “Training a wireless sensor network,” Mobile Networks and Applications, vol. 10, pp. 151–167, Month, 2005.

68.

Wadaa

Olariu

Wilson

, and Eltoweissy

, “Scalable key management for secure communications in wireless sensor networks,” Proceedings of the International Workshop on Wireless Ad-hoc Networking, 2004.

69.

Wang

, and Olariu

, “A unifying look at clustering in mobile ad hoc networks,” Wireless Communications and Mobile Computing, vol. 4, pp. 623–637, Month 2004.

70.

Warneke

Last

Leibowitz

, and Pister

, “SmartDust: communicating with a cubic-millimeter computer,” IEEE Computer, vol. 34, no. 1, pp. 44–55, Month 2001.

71.

Wood

A. D.

, and Stankovic

J. A.

, “Denial of service in sensor networks,” IEEE Computer, vol. 35, no. 4, pp. 54–62, Month 2002.

72.

Yan

, and Stankovic

J. A.

, “Differentiated surveillance for sensor networks,” Proceedings of ACM SenSys, November 2003.

73.

Yang

, and Lu

, “Self-organized network layer security in mobile ad hoc networks,” Proceedings of the FirstACM Workshop on Wireless Security, 2002.

74.

Yau

, and Mitchell

C. J.

, “Security vulnerability in ad hoc networks,” Proceedings of the Seventh International Sysmposium on Communication Theory and Applications, 2003.

75.

Luo

, and Zhang

, “Statistical en-route filtering of injected false data in sensor networks,” Proceedings of IEEE INFOCOM 2004, 2004.

76.

Zhirnov

V. V.

, and Herr

D. J. C.

, “New frontiers: self-assembly and nano-electronics,” IEEE Computer, vol. 34, no. 1, pp. 34–43, Month 2001.

77.

Zhou

, and Haas

Z.J.

, “Securing ad-hoc networks,” IEEE Network, vol. 13, no. 6, pp. 24–30, Month 1999.

78.

Zhu

Setia

, and Jajodia

, “LEAP: Efficient security mechanisms for large-scale distributed sensor networks,” Proceedings of the ACM Conference on Computer and Communications Security, 2003.

79.

Zhu

Setia

Jajodia

, and Ning

, “An interleaved hop-by-hop authentication scheme for filtering false data in sensor networks,” Proceedings of IEEE Symposium on Security and Privacy, 2004.

Protecting the Communication Structure in Sensor Networks

Abstract

Keywords

1. Introduction

1.1 What is Anonymity?

2. The Network Model

2.1 The Sensor Node

2.2 The Sink

2.3 The Gateway

3.2. Clustering

4. The Work Model

4.1 Intra-cluster Activity

Workforce size

Workforce setup

5. The Anonymity Problem

5.1 The Anonymity Threat Model

Brute-Force (Sink nodes are not identified)

Smart (Sink nodes are identified)

5.2 Terminology and Notation

A. Pre-deployment

B Post deployment (training and operation cycles)

5.3 Anonymity Problem Statement

References