Menu
Earlier optimal key pre\(-\)distribution schemes (KPSs) for distributed sensor networks (DSNs) were proposed using combinatorial designs via transversal designs, affine, and partially affine resolvable designs. Here, nearly optimal KPSs are introduced and a class of such KPSs is obtained from resolvable group divisible designs. These KPSs are nearly optimal in the sense of local connectivity. A metric for the efficiency of KPSs is given. Further, an optimal KPS has also been proposed using affine resolvable \( L_{2} \)-type design.
Distributed Sensor Networks (DSNs) are ad–hoc mobile networks that include sensor nodes with limited computation and communication capabilities. Lee and Stinson [1,2] and Saurabh and Sinha [3] obtained optimal key pre\(-\)distribution schemes (KPSs) for DSNs from transversal designs, affine and partially affine resolvable designs which are classes of optimal \((v,\ b,\ r,\ k) -\)configurations. Those KPSs are optimal in the sense of local connectivity. Here nearly optimal KPSs are obtained from resolvable group divisible designs which are not affine. A metric for efficiency of KPSs is given and an optimal KPS has also been proposed using affine resolvable \(L_{2} -\)type Latin square design. A correspondence between combinatorial designs and KPSs for DSNs may be found in [1-3].
Eschenauer and Gligor [4] proposed a randomized KPS. Their scheme consists of three phases: key pre–distribution, shared–key discovery and path–key establishment. Lee and Stinson [1] used this framework in the constructions of deterministic KPSs from certain combinatorial designs. In the key pre–distribution phase, a large pool of keys and their key identifiers are generated. Every sensor node is loaded with a fixed number of keys chosen from the key pool, along with their key identifiers. After deployment of the DSNs, any two nodes in the same neighborhood of DSNs look for common keys in order to communicate; this is the shared-key discovery phase. If any two sensor nodes have no common keys, then they try to establish a secure two–hop path for communication which is the path–key establishment phase [5].
In this paper, some combinatorial constructions are presented for deterministic optimal and nearly optimal KPSs. The present construction is useful when an optimal \((v,\ b,\ r,\ k) -\)configuration is not available for the given \(v,\ b,\ r,\ k\). A recent survey on the constructions of KPSs for DSNs using some combinatorial designs may be found in [3].
A block design \(D(v,\ b,\ r,\ k)\) or \((X\mathcal{,\ B)}\) is an arrangement of the \(v\) elements of a set \(X\) into \(b\) subsets (blocks) of size \(k\) each such that each element of \(X\) occurs in exactly \(r\) blocks. For \(1 \leq i \leq v;1 \leq j \leq b\), \(D\) can be represented by a \(v \times b\) incident matrix \(N\) defined by \(N = \left( n_{ij} \right)_{v \times b},\) where \(n_{ij} = \left\{ \begin{matrix} 1\ \text{if}\ x_{i} \in B_{j} \\ 0\ \text{otherwise} \\ \end{matrix} \right.\ ,\) for \(B_{j}\mathcal{\in B.}\) Clearly each row and column sum of \(N\) are \(r\) and \(k\) respectively.
A block design \(D(v,\ b,\ r,\ k)\) is said to be resolvable if the \(b\) blocks, each of size \(k\) can be partitioned into \(r\) resolution classes of \(\frac{b}{r}\) blocks each such that in each resolution class every point is replicated exactly once. Clearly a necessary condition for a design \(D(v,\ b,\ r,\ k)\) to be resolvable is that \(r\) divides \(b\). Alternatively, if the incidence matrix \(N\) of a block design \(D(v,b,r,k)\) may be partitioned in to sub matrices as: \(N = \left( N_{1} \middle| N_{2} \middle| \cdots \middle| N_{t} \right)\) where each \(N_{i}(1 \leq i \leq t)\) is a \(v \times \frac{(v}{k})\) matrix such that each row sum of \(N_{i}\) is one, then the design is resolvable.
Further a resolvable design is said to be affine if any two blocks belonging to different resolution classes intersect in constant number of elements. Some examples of resolvable and affine resolvable designs are given in subsections 2.2–2.4.
Let \(v = mn\) elements be arranged in an \(m \times n\) array. A group divisible (GD) design is an arrangement of the \(v = mn\) elements in \(b\) blocks each of size \(k\) such that:
Every element occurs at most once in a block;
Every element occurs in \(r\) blocks;
Every pair of elements, which are in the same row of the \(m \times n\) array, occur together in \(\lambda_{1}\) blocks whereas every other pair of elements occur together in \(\lambda_{2}\) blocks.
The non–negative integers: \(v = mn,b,r,k\), \(\lambda_{1}\)and \(\lambda_{2}\) are known as parameters of the GD design and they satisfy the relations: \(bk = vr;(n – 1)\lambda_{1} + {n(m – 1)\lambda}_{2} = r(k – 1).\) Furthermore, if \(r – \lambda_{1} = 0\) then the GD design is singular; if \(r – \lambda_{1} > 0\) and \(rk – v\lambda_{2} = 0\) then it is semi–regular (SR); and if \(r – \lambda_{1} > 0\) and \(rk – v\lambda_{2} > 0\), the design is regular (R) [6].
Transversal designs are special classes of SRGD designs having \(\lambda_{1} = 0,\ k = m\). Some recent constructions of GD designs using certain combinatorial matrices may be found in [7,8].
Example 1. Consider the following resolvable solution of an SRGD design SR9 with parameters \(v = 8,b = 16,r = 4,k = 2,\lambda_{1} = 0,\lambda_{2} = 1,m = 2,n = 4\) as given in [6]:
RI: [(1 5) (2 6) (3 7) (4 8)];
RII: [(2 7) (1 8) (4 5) (3 6)];
RIII: [(4 6) (3 5) (2 8) (1 7)];
RIV: [(3 8) (4 7) (1 6) (2 5)].
The arrangement of \(v = 8\) elements in \(2 \times 4\) array is given as: \(\begin{matrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ \end{matrix}\)
Let \(v = n^{2}\)elements be arranged in an \(n \times n\) array. An \(L_{2} -\)type (Latin square) design is an arrangement of the \(v = n^{2}\) elements in \(b\) blocks each of size \(k\) such that:
Every element occurs at most once in a block;
Every element occurs in r blocks;
Every pair of elements, which are in the same row or in the same column of the \(n \times n\) array, occur together in \(\lambda_{1}\) blocks whereas every other pair of elements occur together in \(\lambda_{2}\) blocks.
The non–negative integers \(v = n^{2},b,r,k,\lambda_{1}\)and \(\lambda_{2}\) are known as parameters of the L2 – type design and they satisfy the relations: \(bk = vr;2(n – 1)\lambda_{1} + {(n – 1)}^{2}\lambda_{2} = r(k – 1).\) Some recent constructions of these designs may be found in [9].
Example 2. Consider an \(L_{2} -\)type design \(LS26\) as given in [6] with parameters \(v = b = 9,r = k = 4,n_{1} = n_{2} = 4,\lambda_{1} = 1,\lambda_{2} = 2\) whose blocks are given as:
\[(1 2 6 9); (2 4 6 8); (1 4 8 9); (2 5 7 9); (2 3 4 7); (3 4 5 9); (1 5 6 7); (3 6 7 8); (1 3 5 8)\]
The arrangement of \(v = 9\) elements in \(3 \times 3\) array is given as, \(\begin{matrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \\ \end{matrix}\)
A block design \(D(v,b,r,k)\) is said to be a \((v,b,r,k) -\)configuration if any two blocks intersect in at most one element. A \((v,b,r,k) -\)configuration is a \(\alpha -\)common intersection design (\(\alpha\) – CID) if \(\left| \{ B_{h}\mathcal{\in B:\ }B_{i} \cap \ B_{h} \neq \ \phi\ and\ B_{j} \cap \ B_{h} \neq \phi\}\ \right| \geq \alpha\), whenever \(B_{i} \cap \ B_{j} = \ \phi\) where \(B_{i},B_{j}\mathcal{\in B}\) are blocks of the configuration.
This implies that any two disjoint blocks intersect with at least \(\alpha\) blocks in common or any two disjoint blocks can be connected through at least \(\alpha\) blocks. In general, it is desirable to construct a \((v,b,r,k) -\)configuration with \(\alpha\) as large as possible for a given \((v,b,r,k)\). This maximum value of \(\alpha\) is denoted by \(\alpha^{*}(v,\ b,\ r,\ k) = k(r – 1)\). Such a configuration is called optimal [1,2]. The KPSs obtained from optimal configurations are optimal in the sense of local connectivity.
The efficiency of a KPS obtained from a \((v,b,r,k) -\)configuration is defined here as: \(E = \frac{\alpha}{k(r – 1).}\) Clearly \(E = 1\) for an optimal configuration. A KPS will be called nearly optimal if its efficiency \(E \approx 1\) when number of nodes is very large. If an optimal KPS for a given \(v,b,r,k\) is not available, we go for nearly optimal KPS. Some examples of such KPSs are given in Section 3.
A block design \(D(v,b,r,k)\) may be used to obtain a KPS having \(N = b\) sensor nodes, \(k\) is the number of keys per node with efficiency \(E = \frac{\alpha}{k(r – 1)\ \ \ }\)where \(\alpha\) is determined using the corresponding series of designs and \(\alpha^{*} = k(r – 1)\) if the KPS is optimal. A nearly optimal KPS will be denoted as \((N,\ k,\alpha,\ E).\)
Example 3. Consider an affine resolvable SRGD design SR23 as listed in [6] with parameters \(v = b = 9,r = k = 3,\lambda_{1} = 0,\lambda_{2} = 1,m = n = 3\) which is a \((9,\ 9,\ 3,\ 3) -\) configuration. The resolution classes are given as:
RI: [(1 2 3) (4 5 6) (7 8 9)];
RII: [(1 5 9) (2 6 7) (3 4 8)];
RIII: [(1 6 8) (2 4 9) (3 5 7)].
It is easy to verify that any two disjoint blocks of this design intersect with six blocks in common, i.e., \(\left| \{ B_{h}\mathcal{\in B:\ }B_{i} \cap \ B_{h} \neq \ \phi\ and\ B_{j} \cap \ B_{h} \neq \ \phi\}\ \right| = 6 = k(r – 1) = 6\) for \(B_{i} \cap \ B_{j} = \ \phi\) where \(B_{i},B_{j}\mathcal{\in B}\). Hence SR23 is an optimal \((9,\ 9,\ 3,\ 3) -\) configuration which is a 6 – CID. The arrangement of \(v = 9\) elements in \(3 \times 3\) array is given as, \(\begin{matrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \\ \end{matrix}\)
Let \(A = \left( a_{ij} \right)\) and \(B = \left( b_{ij} \right)\) be two \(m \times n\) matrices. Then their Hadamard product \(A \circledcirc B\) is also an \(m \times n\) matrix given by \(A \circledcirc B = \left( a_{ij}b_{ij} \right).\)
The following Series I of \(L_{2} -\)type designs may be found in [9]:
Series I: There exists an \(L_{2} -\)type design with parameters: \[\label{e1}v = n^{2},\ b = 2n,\ \ r = 2,k = n,\ \lambda_{1} = 1,\ \lambda_{2} = 0.\tag{1}\] The incidence matrix of above design is given as: \(N = \left( N_{1} \middle| N_{2} \right) = \begin{pmatrix} E_{1} & I_{n} \\ E_{2} & I_{n} \\ \vdots & \vdots \\ E_{n} & I_{n} \\ \end{pmatrix},\) where \(E_{i}(1 \leq i \leq n)\) is an \(n \times n\) matrix whose ith column contains only +1’s and 0 elsewhere. Now it is shown below that the design with parameters (1) is affine resolvable.
Since each row sum of \(N_{1}\) and \(N_{2}\) is one, the design is resolvable. Clearly the number of resolution classes is \(r = 2\) and each class contains \('n'\) blocks. The blocks corresponding to the \('n'\) columns of \(N_{1}\) form one resolution class \(\left( R_{1} \right)\ \)and the blocks corresponding to the \('n'\) columns of \(N_{2}\) form another resolution class \((R_{2})\). Further let \(B_{i}\) and \(B_{j}\ \)be two blocks from \(R_{1}\) and \(R_{2}\) respectively and let \(C_{i}\) and \(C_{j}\) be columns of \(N\) which represent the blocks \(B_{i}\) and \(B_{j}\) respectively. Since the Hadamard product \(C_{i} \circledcirc C_{j}\) contains one exactly once and remaining entry zero in the resultant column, any two blocks from different resolution classes intersect in exactly one element. Hence the design is affine resolvable.
The above Series I of \(L_{2} -\)type designs can be mapped to an optimal KPS having number of nodes \(N = b = 2n\), \('n'\) number of keys per node, \(\alpha^{*} = k(r – 1) = n\) and efficiency \(E = 1\) [vide Lemma 1 and [3], Section 4.1.2].
Example 4. For \(n = 250,\) we obtain an \(L_{2} -\)type design with parameters \(v = 62500,\ b = 500,\ \ r = 2,k = 250,\ \lambda_{1} = 1,\ \lambda_{2} = 0\ \)which can be mapped to an optimal KPS having number of nodes \(N = b = 500\), \(n = 250\) keys per node, \(\alpha^{*} = k(r – 1) = 250\) and efficiency \(E = 1.\)
Example 5. A GD design with parameters: \(v = mn,b,r,k,\lambda_{1} = 0,\lambda_{2} = 1\ \)is a \((v,\ b,\ r, k) -\) configuration and the configuration is optimal if the GD design is affine resolvable and \(b = kr.\)
Proof. Consider a GD design with parameters: \(v = mn,b,r,k,\lambda_{1} = 0,\lambda_{2} = 1\). Let \(B_{i}\) and \(B_{j}\) be any two distinct blocks of the GD with above mentioned parameters. Since any pair of distinct elements occur together in either one block or no block, we have \(\left| B_{i} \cap B_{j} \right| \leq 1\) and hence the above GD design is a \((v,\ b,\ r,\ k) -\)configuration. The proof of second part follows from Lemma 1 of [3].
The following Series of resolvable GD designs using generalized Hadamard matrices may be found in [7]:
Series II: There exists a GD design with parameters: \(v = p^{t}\left( p^{t} – 1 \right),r = p^{t},k = p^{t} – 1,b = \left( p^{t} \right)^{2},\ \lambda_{1} = 0,\ \lambda_{2} = 1,m = p^{t} – 1,n = p^{t}\) where \(p\) is a prime and \(t > 1\).
First, we show that any two disjoint blocks of Series II intersect with \(\alpha = (p^{t} – 2)(p^{t} – 1)\) blocks in common.
Let \(B_{i} = (\theta_{1},\theta_{2},\cdots,\theta_{k})\) and \(B_{j} = (\rho_{1},\rho_{2},\cdots,\rho_{k})\) be any two disjoint blocks and \(B_{i} \times B_{j}\) be their cartesian product if we consider them as sets. It is sufficient to count the blocks in which the elements (or unordered pairs) of \(B_{i} \times B_{j}\ \)occur. In \(B_{i} \times B_{j}\) there are total \(k^{2} = \left( p^{t} – 1 \right)^{2}\) pairs out of which \('k = p^{t} – 1'\) pairs of elements belong to the rows of \(m \times n\) array on which the GD design is based and thus these pairs cannot be part of any block of the GD design as \(\lambda_{1} = 0\). Hence \(\alpha = \left( p^{t} – 1 \right)^{2} – \left( p^{t} – 1 \right) = \left( p^{t} – 2 \right)\left( p^{t} – 1 \right).\)
The Series I may be mapped to a nearly optimal KPS \((N,\ k,\alpha,\ E)\) having \(N = b = \left( p^{t} \right)^{2}\) sensor nodes, \('k = p^{t} – 1'\) keys per node, \(\alpha = \left( p^{t} – 2 \right)\left( p^{t} – 1 \right)\) and efficiency given as: \(E = \frac{\alpha}{k(r – 1)} = \frac{(p^{t} – 2)(p^{t} – 1)}{{(p^{t} – 1)}^{2}} = 1 – \frac{1}{p^{t} – 1}\) which tends to 1 as \(t \rightarrow \infty.\) ◻
Example 6. Consider the following resolvable solution of an SRGD design SR26 with parameters: \(v = 12,b = 16,r = 4,k = 3,\lambda_{1} = 0,\lambda_{2} = 1,m = 3,n = 4\) as given in [6],
RI: [(1 2 3) (7 8 12) (5 9 10) (4 6 11)];
RII: [(1 11 12) (3 5 7) (6 8 10) (2 4 9)];
RIII: [(1 5 6) (3 4 8) (7 9 11) (2 10 12)];
RIV: [(1 8 9) (2 6 7) (3 10 11) (4 5 12)].
The arrangement of \(v = 12\) elements in \(3 \times 4\) array is given as, \(\begin{matrix} 1 & 4 & 7 & 10 \\ 2 & 5 & 8 & 11 \\ 3 & 6 & 9 & 12 \\ \end{matrix}\)
Consider disjoint blocks \(B_{1} = (1\ 2\ 3)\) and \(B_{2} = (7\ 8\ 12)\) of RI and consider the cartesian product \(B_{1} \times B_{2} = \{(1\ 7),\ (1\ 8),\ (1\ 12),\ (2\ 7),\ (2\ 8),\ (2\ 12),\ (3\ 7),\ (3\ 8),\ (3\ 12)\}\). We count the number of blocks in which these pairs occur. Since the pairs \((1\ 7),\ (2\ 8)\) and \((3\ 12)\) of elements belong to first, second and third rows respectively of the \(3 \times 4\) array, these pairs cannot be part of any block of SR26 as \(\lambda_{1} = 0\). Clearly the disjoint blocks intersect with six blocks: (1 11 12), (3 5 7), (3 4 8), (2 10 12), (1 8 9), (2 6 7) in common. It can be also verified that any pair of remaining disjoint blocks also intersects with six blocks in common. Hence \(\alpha = 6\) and SR26 is a \(6 -\)CID.
The following Table 1 lists nearly optimal KPSs using Series II having number of sensor nodes \(\leq\)1000 for different values of \(p\) and \(n\) with \(\lambda_{1} = 0,\lambda_{2} = 1\). The design numbers 1\(-\)6 listed below may be found in [6].
| No. | SRGD Parameters \((v,r,k,b,m,n)\) | KPSs \((N,k,\alpha,E)\) |
| 1 | \((6, 3, 2, 9, 2, 3)\) | \((9, 2, 2, 0.50)\) |
| 2 | \((12, 4, 3, 16, 3, 4)\) | \((16, 3, 6, 0.66)\) |
| 3 | \((20, 5, 4, 25, 4, 5)\) | \((25, 4, 12, 0.75)\) |
| 4 | \((42, 7, 6, 49, 6, 7)\) | \((49, 6, 30, 0.84)\) |
| 5 | \((56, 8, 7, 64, 7, 8)\) | \((64, 7, 42, 0.86)\) |
| 6 | \((72, 9, 8, 81, 8, 9)\) | \((81, 8, 56, 0.89)\) |
| 7 | \((110, 11, 10, 121, 10, 11)\) | \((121, 10, 90, 0.90)\) |
| 8 | \((156, 13, 12, 169, 12, 13)\) | \((156, 12, 132, 0.92)\) |
| 9 | \((240, 16, 15, 256, 15, 16)\) | \((256, 15, 210, 0.93)\) |
| 10 | \((272, 17, 16, 289, 16, 17)\) | \((289, 16, 240, 0.94)\) |
| 11 | \((342, 19, 18, 361, 18, 19)\) | \((361, 18, 306, 0.94)\) |
| 12 | \((506, 23, 22, 529, 22, 23)\) | \((529, 22, 462, 0.95)\) |
| 13 | \((600, 25, 24, 625, 24, 25)\) | \((625, 24, 552, 0.96)\) |
| 14 | \((702, 27, 26, 729, 26, 27)\) | \((729, 26, 650, 0.96)\) |
| 15 | \((812, 29, 28, 841, 28, 29)\) | \((841, 28, 756, 0.96)\) |
| 16 | \((930, 31, 30, 961, 30, 31)\) | \((961, 30, 870, 0.97)\) |
In a \((v,\ b,\ r,\ k) -\)configuration, the compromise of \('s'\) random nodes affect a given link with probability roughly equal to: \(fail(s) = 1 – \ \left( 1 – \frac{r – 2}{b – 2} \right)^{s}.\) Clearly for a larger resiliency, fail\((s)\) should have a smaller value [1].
Example 7. For \(q = p^{t} = 31,\) Series II yields nearly optimal \((930,\ 961,\ 31,\ 30) -\) configuration. This may be mapped to a KPS with 961 sensor nodes. Suppose 10 nodes are compromised, then \(fail\ (s) \approx 0.26\). This implies that any given link is affected with a probability of \(26\%\) when 10 nodes are compromised.
Furthermore, suppose that \(N_{i}\) and \(N_{j}\) are two neighboring nodes then the probability that \(N_{i}\) and \(N_{j}\) share a common key is: \(\Pr_{1} = \frac{k(r – 1)}{b – 1}\). Clearly \(\Pr_{1} = 1\) for a symmetric balanced incomplete block design having \(\lambda = 1\) and \(\Pr_{1} < 1\) for another block designs.
Let \(\eta\) denote the number of nodes in the intersection of the neighborhoods of the two nodes \(N_{i}\) and \(N_{j}\) where \(\eta\) depends on the size of the physical area where the nodes are deployed, the distance between nodes and on the total number of sensor nodes in the DSN. The probability that \(N_{i}\) and \(N_{j}\) do not share a common key, but there exists a node \(N_{h}\) such that \(N_{h}\) shares a key with both \(N_{i}\) and \(N_{j}\), is given as follows: \(\Pr_{2} = \left( 1 – \Pr_{1} \right)\left( 1 – {(1 – \frac{\alpha}{b – 2})}^{\eta} \right)\). Then the probability that \(N_{i}\) is connected to \(N_{j}\) via a path of length one or two is approximately: \(Pr = \Pr_{1} + \Pr_{2}\) [1,3].
Example 8. The values of \(\Pr_{1},\Pr_{2}\) and \(fail(s)\) for the optimal KPS obtained from Series I are:
\[\Pr_{1} = \frac{n}{2n – 1},\Pr_{2} = \frac{n – 1}{2n – 1}\left( 1 – \left( \frac{n – 2}{2(n – 1)} \right)^{\eta} \right),\ fail(s) = 0.\]
Clearly the value of \(fail(s)\) is the minimum which is desirable for a KPS.
Earlier Lee and Stinson [1,2] and Saurabh and Sinha [3] obtained optimal KPSs from transversal designs, affine and partially affine resolvable designs. Here nearly optimal KPS has been introduced and a class of such KPS has also been proposed using resolvable group divisible designs. An optimal KPS has also been obtained using affine resolvable \(L_{2} -\)type design. A metric for efficiency of KPSs is given. Some other resolvable combinatorial designs (which are not affine) such as rectangular designs, balanced incomplete block designs, \(L_{2} -\)type designs and triangular designs may also be used to obtain nearly optimal KPSs under certain conditions. The constructions of these schemes would be taken up as a future work.
The author declares that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.