B.8. Location-aware Key Predistribution

The key predistribution algorithms discussed so far are based on a random deployment model. In practice, the deployment model (like the expected location of each node and the overall geometry of the deployment area) may be known a priori. This knowledge can be effectively exploited to tune the key predistribution algorithms so as to achieve better connectivity and higher resilience against node capture. As an example, consider sensor nodes deployed from airplanes in groups or scattered uniformly from trucks. Since the approximate tracks of these vehicles are planned a priori, the key rings of the nodes can be loaded appropriately to achieve the expected performance enhancements.

Two nodes that are in the physical neighbourhoods of one another need only share a pairwise key. Therefore, the basic objective of designing location-aware schemes is to predistribute keys in such a way that two nodes that are expected to remain close in the deployment area are given common pairwise keys, whereas two nodes that are expected to be far away after deployment need not share any pairwise key. The actual deployment locations of the nodes cannot usually be predicted accurately. Nonetheless, an approximate knowledge of the locations can boost the performance of the network considerably. The smaller the errors between the expected and actual locations of the nodes are, the better a location-aware scheme is expected to perform.

B.8.1. Closest Pairwise Keys Scheme

Liu and Ning [182] propose a modification of the random pairwise key scheme (Section B.5) based on deployment knowledge. Let there be n sensor nodes in the network with each node capable of storing m cryptographic keys. The expected deployment location of each node is provided to the key set-up server. For each node u in the network, the server determines m other nodes whose expected locations of deployment are closest to that of u and for which pairwise keys with u have not already been established. For every such node v, a new random key k_uv is generated. The key-plus-ID combination (k_uv, v) is loaded in u’s key ring, whereas the pair (k_uv, u) is loaded in v’s key ring.

This natural and simple-minded strategy provides complete security against node captures, as it is a pairwise key distribution scheme. Now, there is no limitation on the maximum supportable network size (under the reasonable assumption that there are much less than 2^l nodes in the network, where l is the bit length of a cryptographic key, say, 64 or 128). Moreover, the incorporation of deployment knowledge increases the connectivity of the network. In order to analyse this gain, we first introduce some formal notations.

For the sake of simplicity, we assume that the deployment region is two-dimensional, so that every point in that region is expressed by two coordinates x and y. Let u be a sensor node whose expected deployment location is (u_x, u_y) and whose actual deployment location is . This corresponds to a deployment error of . The actual location (or equivalently the error e_u) is modelled as a continuous random variable that can assume values in . The probability density function f_u of characterizes the pattern of deployment error. One possibility is to assume that is uniformly distributed within a circle with centre at (u_x, u_y) and of radius ∊ called the maximum deployment error. We then have:

Equation B.11

An arguably more realistic strategy is to model as a random variable following the two-dimensional normal (Gaussian) distribution with mean (u_x, u_y) and variance σ². The corresponding density function is:

Let u and v be two deployed nodes. We assume that each node has a communication range of ρ. We also make the simplifying assumption that the different nodes are deployed independently, that is, and are independent random variables. The probability that u and v lie in the communication ranges of one another can be expressed as a function of the expected locations (u_x, u_y) and (v_x, v_y) as:

Here, the integral is over the region C of defined by .

Let n′ denote the number of physical neighbours of u (or of any sensor node). We know that u shares pairwise keys with exactly m nodes. We assume that these key neighbours of u are distributed uniformly in a circle centred at u and of radius ρ′. The expected value of ρ′ is:

Let v be a key neighbour of u. The probability that v lies in the physical neighbourhood of u is given by

where C′ is the region (v_x – u_x)² + (v_y – u_y)² ≤ ρ^′2. Therefore, u is expected to have m × p(u) direct neighbours. Since the size of the physical neighbourhood of u is n′, the local connectivity, that is, the probability that u can establish a pairwise key with a physical neighbour is given by

In general, it is difficult to compute the above integrals. Liu and Ning [182] compute the probability p′ for the density function given by Equation (B.11) and establish that p′ ≈ 1 for small deployment errors, namely ∊ ≤ ρ. As ∊ increases, p′ gradually reduces to the corresponding probability for the random pairwise scheme.

In order to add sensor nodes at a later point of time, the key set-up server again uses deployment knowledge. The keys rings of the new nodes are loaded based on the expected deployment locations of these nodes and on the (expected or known) locations of the deployed nodes. Pairwise keys between the new and the deployed nodes are communicated to the deployed nodes over secure channels (routing through uncompromised nodes).

B.8.2. Location-aware Polynomial-pool-based Scheme

Several variants of the closest pairwise keys scheme have been proposed. Liu and Ning themselves propose an extension based on pseudorandom functions [182]. Du et al. propose a variant of the basic (EG) scheme based on a specific model of deployment [80]. We end this section by briefly outlining a location-aware adaptation of the polynomial-pool-based scheme (Section B.6).

For simplicity, let us assume that the deployment region is a rectangular area. This region is partitioned into a 2-dimensional array of rectangular cells. Let the partition consist of R rows and C columns. The cell located at the i-th row and the j-th column is denoted by C_i,j. The neighbours of the cell C_i,j are taken to be the four adjacent cells: C_i–1,j, C_i+1,j, C_i,j–1, C_i,j+1.

The key set-up server first decides a finite field with q just big enough to accommodate a cryptographic key. The server also chooses R×C random symmetric bivariate polynomials . The polynomial f_i,j is meant for the cell C_i,j. The degree t (in both X and Y) of each f_i,j is so chosen that each sensor node has sufficient memory to store the shares of five such polynomials.

Let u be a node to be deployed and let the expected deployment location of u lie in the cell C_i,j called the home cell of u. The key ring of u is loaded with the shares (evaluated at u) of the five polynomials corresponding to the home cell and its four neighbouring cells. More precisely, u gets the five shares: f_i,j(X, u), f_i–1,j(X, u), f_i+1,j(X, u), f_i,j–1(X, u), and f_i,j+1(X, u). The set-up server also stores in u’s memory the ID (i, j) of its home cell.

In the direct key establishment phase, each node u broadcasts the ID (i, j) of its home cell (or some messages encrypted by potential pairwise keys). Those physical neighbours whose home cells are either the same as or neighbouring to that of u can establish pairwise keys with u.

An analysis of the performance of this location-aware poly-pool-based scheme can be carried out along similar lines to the closest pairwise scheme. We leave out the details here and refer the reader to Liu and Ning [182].