5.1. Network Connectivity
Since the ordinary nodes are in charge of normal network operations, the "network connectivity probability" is defined as the probability of establishing secure communication link between two neighboring ordinary nodes. As shown in (5), if two neighboring ordinary nodes share enough number of derived keys, they can establish pairwise key, that is, establish a secure communication link.
Two neighboring ordinary nodes
U and
V must share derived keys if the following conditions hold:
(1)
and
share at least one root key;
(2)
at least one of their common auxiliary nodes picks one or more initial keys from the key groups whose root keys are shared by
and
.
Now we discuss how to satisfy the two above-mentioned conditions in order to establish pairwise key between two neighboring ordinary nodes.
Let
be the number of common derived keys between
U and
V through the common auxiliary node
. The total number of common derived keys
m between
U and
V through all their
g common auxiliary nodes thus is
. Then we can give the following conclusions.
Lemma 1.
Assuming that two neighboring ordinary nodes U and V have only a common auxiliary node, if U shares exactly i root keys with V, the common derived keys shared between them must be no more than
.
Proof.
Each root key can authenticate at most
M initial keys, since the common derived keys must come from key groups which root keys are shared between
U and
V, if
U and
V share
i root keys and the common auxiliary node picks all the
initial keys of the total
i key groups, these keys will be authenticated by
U and
V, then they will share
common derived keys. Otherwise, if any one of the initial keys among these
keys is not picked by the common auxiliary node, the common derived keys shared between
U and
V must be no more than
.
Theorem 2.
Assume that neighboring ordinary nodes U and V have g common auxiliary nodes, and the number of common derived keys shared between U and V through each of g common auxiliary nodes is
respectively (
); then the number of root keys shared between U and V must be at least
.
Proof.
If
U and
V share
i root keys, according to Lemma 1, the common derived keys shared between them must range from 0 to
. If they can generate
m
i
common derived keys through the common auxiliary node
, they must share at least
root keys. For all the
, if
U and
V share enough number of root keys to ensure generating the maximum common derived keys amongst
through one of common auxiliary nodes, they are able to generate other common derived keys through other common auxiliary nodes. Therefore, the number of shared root keys must be at least
.
Assume that
U shares
i root keys with
V and there is only one common auxiliary node between
U and
V. Obviously,
U and
V can generate at most
common derived keys. To ensure
U and
V share
m common derived keys, there are
ways to let the common auxiliary node select
m different initial keys from these
i key groups. Similarly, there are
ways to let the common auxiliary node randomly select
different initial keys from the remaining
key groups. Hence, the total number of ways that the common auxiliary node selects initial keys from initial key pool should be
When two neighboring ordinary nodes U and V have g common auxiliary nodes, the total number of ways that U and V share m derived keys can be calculated as follows:
First,
U and
V have
different ways to randomly select
root keys from root key pool.
Second, the shared derived keys, that is,
between
U and
V, must range from 0 to
m and
. Hence there are
ways to let every common auxiliary node provide shared initial keys. According to Theorem 2,
U must share at least
root keys with
V. Once
are fixed, the number of shared root keys will range from
to
. Hence, the total number of ways by which
V randomly selects root keys from the root key pool is given by
. The total number of ways that
g common auxiliary nodes randomly select initial keys is
, where
for
is defined in (6).
Hence, the probability that two neighboring ordinary nodes share
derived keys when they have
(
) common auxiliary nodes can be calculated as follows:
Let
be the probability of two neighboring ordinary nodes sharing sufficient derived keys to establish pairwise key. Obviously,
.
two neighboring ordinary nodes share insufficient derived keys to establish pairwise key
. Hence, we have
From (8), we can conclude that the system parameters, such as, the number of common auxiliary nodes, the size of the initial key group, the number of initial key groups, and may influence the network connectivity performance.