Abstract
Sensor networks are deployed in, and react with, chaotic environments. Self-organizing peer-to-peer networks have admirable survivability characteristics. This chapter discusses random network formalisms for designing, modeling, and analyzing survivable sensor networks. Techniques are given for determining critical values. Applications in system security and surveillance networks are given.
Introduction
RANDOM graph theory originated with seminal work by Erdös and Rényi in the 1950s. Until then, graph theory analyzed either specific graph instances or deterministically defined graph classes. Erdös and Rényi considered graph classes where the existence of edges between nodes was determined probabilistically. Their results were theoretically interesting and found applications in many practical domains [1].
Erdös and Rényi used the same probability value to assign edges between any two nodes in the graph. As an extension to this in the 1990s, Strogatz and Watts studied “small world” graphs [2]. The term small world originates with Milgram's six degrees of separation model of social networks created in the 1960s. Strogatz and Watts' work considers networks where the probability of edges existing between nodes is not uniform. They were specifically interested in clustered graphs, where edges are more likely to exist between nodes with common neighbors. To study this phenomenon, they defined classes of pseudo-random graphs. These graphs combine a deterministic structure and a limited number of random edges. Their results have been used to analyze both social networks and technical infrastructures.
An alternative approach to studying similar systems has been proposed by Barabási [1]. His group considered the probability distributions of graph node degree found in graph models of existing systems. This analysis shows that the probability of a node having degree d follows an inverse power law (i.e., is proportional to d −γ where γ is a constant). They also explain how this property can emerge from positive feedback in evolving systems. These models appear to be appropriate for studying a wide range of natural and large-scale technical systems. Important results from this model include quantification of the dependability of the Internet [3], and analysis of computer virus propagation [4].
Random graph concepts are also widely used in percolation theory [5]. Percolation theory studies flow through random media. The model of random media is usually built from a regular tessellation of an n-dimensional space. Edges may or may not exist between neighboring vertices of the tessellation with a uniform probability. Applications of percolation theory include oil extraction. We consider this model as an example of sensor networks with a planned wireless infrastructure.
Another random network model, given in [6], is used to study ad hoc wireless networks. A set of nodes is randomly distributed in a two-dimensional region. Each node has a radio with a given range r. A uniform probability exists (in [6] the probability is 1) for edges being formed between nodes as long as they are within range of each other. This network model has obvious practical applications. Many of its properties resemble those of Erdös-Rényi graphs, yet it also has significant clustering like the small-world model. We use this model when analyzing ad hoc wireless systems.
Probabilistic Connectivity Matrices
A graph is traditionally the tuple [V, E]. V is a set of vertices, and E is a set of edges. Each edge e is defined as (i,j) where i and j designate the two vertices connected by e. In this paper, we consider only undirected graphs where (i,j) = (j,i). An edge (i,j) is incident on vertices i and j. We do not consider multi-graphs where multiple edges can connect the same end-points. We use the terms vertex and node interchangeably. Edge and link are also used synonymously.
We represent a graph by its connectivity matrix. The connectivity matrix M is a square matrix where each element m(i,j) is 1 (0) if there is (not) an edge connecting vertices i and j. For undirected graphs this matrix is symmetric.
As a matter of convention, the diagonal of the matrix can consist of either zero's or one's. One's are frequently used, based on the simple assertion that each vertex is connected to itself. We use the convention where the diagonal is filled with zeros.
A walk of length z is an ordered list of z edges ((i 0 ,j 0 ),(i 1 ,j 1 ),…,(i z ,j z )), where each vertex j a is the same as vertex ia+1. A path of length z is a walk where all i a are unique. If j z is the same as i 0 , the path is a cycle.
A useful property of connectivity matrices is the fact that element m z (i,j) of the power z of graph G's connectivity matrix M (i.e., M z ) is the number of walks of length z from vertex i to vertex j that exist on G [7].
We use probabilistic connectivity matrices to represent random graph classes. These matrices replace the binary values for connectivity matrix elements m(k,j) with the associated probabilities of an edge existing between nodes k and j. In which case, graph instances can be constructed by traversing the upper triangular half of the probabilistic connectivity matrix L and comparing the element value l i, j to a uniform random variable r in the range zero to one. If l i, j < r, then an edge is inserted between nodes i and j. If not, none exists. A nonprobabilistic connectivity matrix is made by setting l i, j to one in the first case, else it is zero. Detailed examples for graph classes can be found in [8] and [9].
Parameters
Expected Number of Hops
Theorem. element (j,k) of M z is the probability that a walk of length z existing between nodes j and k.
Proof. The proof is by induction. By definition, each element (j,k) is the probability of an edge existing between nodes j and k. M 2 is the result of multiplying matrix M with itself. Equation (16) is used to calculate each element (j,k) since all values are probabilities. As explained in Section 7, this calculates the probability of a path of length two existing between nodes j and k by exhaustively enumerating the likelihood of the path passing through each intermediate node in the graph. Using the same logic, M z can be calculated from M z−1 using matrix multiplication to consider all possible intermediate nodes between nodes j and l. Where M z−1 has the probabilities of a walk of length z−1 between j and k, and M has the values defined previously.
Phase Change
Theorem. For Erdös-Rényi graphs of n nodes with 0 < p < 1 the probability of an edge existing between any two nodes and probabilistic connectivity matrix M, the critical point for the property of graph connectivity occurs when M = M2]. When M « M2, the graph is in its sub-critical phase. When M » M 2 , the graph is in its supercritical phase. (Note that, as a probability, p is constrained to real values.)
Proof. By definition, all nondiagonal elements of the Erdös-Rényi graph matrix have the same value p and the diagonal elements have value zero. By symmetry, all nondiagonal elements of M n for any n will have the same value (remember that diagonal elements are constrained to remain zero). We use the symbols <, >, », and » to compare these matrices by referring to the value of the nondiagonal elements.
Non-diagonal elements of M 2 are 1−(1−P2)n−1. From theorem 4, there is the likelihood that a path of two hops exists between any two nodes in the graph. Let P (2) represent non-diagonal elements of M 2 [i.e., 1−(1−P2)n−2]. P(2) is monotone increasing with respect to P. Both P and P(2) are constrained to range [0‥1]. The minimum (maximum) value 0 (1) of both occurs when P is 0 (1).
If P (2) > P, the probability that a path of three hops exists between two nodes (P (3) ) is greater than the probability a path of two hops exists (P (2) ). P (3) is computed as 1−(1−P (2) P)n−1, which is monotone increasing with respect to both P and P (2) . Using the same logic, the probability that any two nodes are connected increases as the path length increases as long as P (2) > P. As P(n−1) approaches 1, a single giant component exists almost certainly. By definition, the graph is in its supercritical phase.
By symmetry, when P (2) < P the likelihood that a path of j hops connects any two nodes decreases monotonically with j. As P(n-1) approaches 0, a giant component is almost certain not to exist and the graph is almost certainly disjoint. By definition, the graph is in its subcritical phase.
When M « M 2 the graph has been shown to be in its supercritical phase and when M » M 2 the graph has been shown to be in its subcritical phase. This leaves M ∼ M 2 as the critical phase. By definition, the critical phase is the neighborhood of the critical point so the critical point can be calculated as the point where M = M 2 . QED
Applications
Network Viability
Consider a surveillance network charged with reporting when a member of a class of objects (targets) traverses a given surveillance domain (terrain). Reports are sent to a user community that we assume, for the sake of discussion, is external to the terrain. The network will be viable as long as it assures that:
an object traversing the terrain is detected (with acceptable error rates), and the user community is alerted. More details in [10].
This criterion is a tautology: the network is viable as long as it performs its mission. To date, the implications of this tautology have been overlooked. For example, the following methods of determining network viability do not fit the criterion:
Network connectivity – If full network connectivity is needed, the sensor network is a giant serial system. Network availability will fall exponentially with the number of sensor nodes (n), and thus large networks will have an unacceptable mean time to failure. For networks with any redundancy, some nodes can be isolated from the network without compromising its application. Sensing coverage – refers to placing nodes so that sensor detection regions have little overlap, but the system monitors the entire terrain. Since sensing ranges and coverage regions are unpredictable, problems with this “cookie cutter” approach are well known [11], and often due to environmental influence [12]. Real-world approaches consider distributed surveillance as a tracking problem using sensors with finite space and time sampling rates [13, 14]. Coverage approaches ignore sensor errors, background noise, and occlusion. In addition, coverage analysis creates a serial system, which fails when any component fails. Once again, we have a serial system where dependability falls exponentially with network size.
Network connectivity ignores sensing issues. Sensing coverage ignores wireless communications issues.
We propose a network viability criterion that is a direct consequence of the network model in [6], where nodes with a fixed communications range are placed at random in the terrain. Simulations show that ad hoc networks with range limited communications exhibit phase change phenomena like those found in random graph and percolation theories.
In these models, network behavior has two phases. In the first phase, the probability of connection between nodes is small and the network has a large number of isolated components. As the connection probability grows, the expected size of the largest component grows logarithmically. In the second phase, the network is dominated by a unique giant component that contains most of the system nodes. There are still isolated holes in the network. The size of the largest hole shrinks logarithmically as the connection probability increases. The transition between these two phases is extremely steep. For random graphs, the curve of the maximum component size versus edge probability takes the form. In percolation theory, the inflection point of this curve is referred to as the percolation threshold.
Percolation theory has established these properties for systems with a giant component [5]:
For systems above the percolation threshold, a path exists that connects the terrain's external boundaries. At the percolation threshold, property 1 is self-similar over scales.
Consider sensor networks with nodes either randomly placed, in a regular tessellation, or a weighted combination of the two. Sensor nodes are vertices in a random graph structure. Edges between vertices represent either an active communications link, or detection of a target passing between nodes. In practice, the edge probability distribution is the minimum of the two likelihoods.
Above the phase change (percolation threshold) a single giant component connects most of the sensor nodes (O(n)). It has at least one path connecting all the terrain's external boundaries (property 1). This property is true for subsets of the system across scales (property 2). Thus, for a sensor network with a giant component, targets traversing the network will be detected by at least one node that can report the detection to the user community. Therefore, the network fulfills our viability criterion.
This shows the network is viable while it has a giant component. In our simulation, we infer the loss of the giant component from the loss of property 1. When there is no path between the terrain's external boundaries, the giant component is fractured. Consider the worst-case scenarios for networks with initial configurations above the percolation threshold:
A target entering the network cannot be detected and/or reported while in a hole. Since the largest hole above the percolation threshold is O(log n), this is the upper limit of the target's ability to avoid detection in the initial network configuration. As nodes lose power:
maximum hole size grows logarithmically, the network becomes sparse, and the network approaches the percolation threshold.
As long as we are above the percolation threshold property 1 holds and a target has to pass through a graph edge to traverse the terrain. Once it does so, a node connected to the giant component detects the target and notifies the user community. Property 2 says that property 1 holds for regions inside the terrain up to the percolation threshold.
To identify cloned nodes in sensor networks that use random key predistribution we proposed a method in [15, 16] for identifying the keys that are used by cloned nodes. The system can recover from a cloning attack by terminating connections using cloned keys. Care is taken to quantify the limitations of the proposed approach.
An important factor in this approach is the threshold value α, which is the likelihood that a legitimate key is marked as cloned. The main limitation on α is the percolation threshold where the network fractures. Figure 1 plots the maximum component size of the network versus the false positive rate α. Note that for values of α less than 60% the network maintains 100% connectivity. Above that value nodes start being excluded from the network, with a phase change occurring when α is between 80% and 90%. This is an artifact of the Erdos-Renyi topology of the graph. If a node has one key in common with any other network node, it can connect to the network.
Variation of maximum component size for different values of False Positive rate α.
Figure 2 plots the maximum component size of the network versus the false positive rate α for both grid and ad hoc networks. The figure shows an inflection point for component size when the value of α is somewhere between 0.3 and 0.5. In ad hoc networks, the inflection point occurs when α is approximately 0.8. False positive rates above those values will fracture the network and disable the sensor network. The prediction model in [15], predicts that the phase change in the ad hoc network occurs at α = 0.62. Also, a known result from the percolation theory is that the inflection point for grid networks of 4 neighbors occurs when the probability of connection between any two nodes is 0.5. The corresponding value of α for grid networks is 0.47. These predictions are consistent with our simulation results.
Maximum component size as the false positive rate α varies for (a) grid and (b) ad hoc topologies.
Figure 3 shows the number of cloned keys detected for different α settings and different numbers of clones for both ad hoc and grid networks. These values do not include false positives. The keys that are detected are the keys that are most highly used in the network. As can be seen from the figures, larger values of α result in a larger number of cloned keys being detected, but this comes at the cost of a higher number of legitimate keys being falsely detected as clones. This is an acceptable tradeoff, since this result in very few legitimate nodes being rejected from the network.
Number of cloned keys detected versus α. The key ring size k is 50. (a) Grid Networks and (b) ad hoc networks.
We note that the approach presented here allows the network designer to determine in advance when the network will fracture as a function of α.
This paper discusses the importance of random graph and percolation theory in designing sensor networks. We explain how probabilistic connectivity matrices can be used to find the percolation threshold of a sensor network. That threshold determines whether or not the network contains a unique giant component.
We then explained the importance of this result. Only networks with a giant component are capable of successfully executing surveillance missions. We also explain how the percolation threshold fundamentally limits the ability of many networks to detect and remove cloned nodes. This has important security implications.