TALK: Topology Aware LKH Key Management

Abstract

Cryptographic key management for wireless sensor networks (WSNs) and mobile ad-hoc networks (MANETs) is a particularly challenging task, as they mostly consist of high counts of resource constrained nodes, especially when group communication and dynamic network membership capabilities are required. The logical key hierarchy (LKH) is a well-known class of protocols which aims to solve the key management problem and minimize rekeying overhead, using hierarchical structures and taking advantage of multicast communication. In this work we propose a method for obtaining LKH structures by taking into account the topology of the underlying network, leading to a further decrease in rekeying costs, in terms of packet transmissions.

1. Introduction

Security is an essential element for any application of wireless networks. Its application in WSNs and MANETs is hindered by additional challenges and requirements which arise from their large scale and resource constrained nature. Key management, in particular, is one of the security aspects which requires a totally different approach from conventional networks.

Key management [1] refers to the procedures which support key establishment and the maintenance of ongoing keying relationships (replacing, canceling keys, etc.) between the network's nodes; it is an essential part of the security procedures of wireless networks. Several key management schemes exist, which support different communication flows and either dynamic or static networks.

Nowadays, in high-end device networks, there is a clear prevalence of public key algorithms, regarding key management functions. The most characteristic example is TLS [2] (and its predecessor, SSL [3]), used, among other applications, in the HTTPS protocol [4]. These networks and applications, however, are largely different from MANETs and WSNs, regarding node capabilities, node count, and traffic flow.

This gave rise to the development of key management protocols specifically designed for low resource, high node number wireless networks. Both private and public key based schemes were developed, each focused on particular features and aspects for optimization. Symmetric schemes [5] impose a generally lower computational and network overhead but need at least predistributed keys, and symmetric keys must not be compromised (or a suitable key revocation scheme needs to exist for such occasions). Conversely, in asymmetric schemes [5], no secret keys need to be distributed, and the main issues are the authenticity of the public keys, which must either be established by a certificate authority (CA) or by public key predistribution and the high computational overhead of the public key algorithms.

One key aspect that needs to be considered for key management schemes for MANETs and WSNs is group communication [6]. In MANETs particularly, there is a need for any network node to be able to communicate with any other node. Several prominent key management schemes, such as base station participation [7], polynomial [8], probabilistic [9], and their modern variations, such as [10], do not use a network-wide traffic encryption key (TEK). Thus, group communication using these schemes is impossible or impractical, as capability for communication between any two nodes is not guaranteed.

While not every application uses a group communication model for its core function, a substantial number of applications can benefit from data aggregation, as shown in [11–13]. However, the use of data aggregation requires the ability of nodes to communicate directly with several nodes other than the final recipient(s) of their data. In this case, a key management scheme that supports group communication should be considered. An oversimplified implementation of data aggregation can be established, where data is left as originally encrypted at the source until reception at the destination. However, although this does not necessitate the need for group communication, the additional overhead required per data-sent defeats the purpose of using aggregation.

Another key issue for MANET/WSN key management is scalability. As these types of networks can scale up to hundreds or thousands of nodes, the key management schemes must still be able to function efficiently. When coupled with a demand for the aforementioned group communication, which makes use of a network-wide secret key, inherently detrimental to scalability, several key management schemes ([7–9], as well as possible modifications which could add a network-wide key) proposed in the literature are rendered unsuitable.

One class of key management schemes which is scalable and also supports dynamic networks and group communication is the one based on the LKH [14]. The base concept was introduced by Wong et al. in [14, 15] and independently by Wallner et al. in [16]. Variations and adaptations of the main technique to mobile networks have appeared in [17–20] and others.

Most of these schemes generally have been mostly examined in theoretical single hop scenarios; however multihop network topologies and the relevant communication cost have not been considered. There are works that examine the structuring of networks, but without taking multihop communication into account: the optimal theoretical (single-hop) LKH structure in terms of number of messages is discussed by Lee et al. in [21], while finding computation-wise optimal key structures is presented by Zhu in [22]. In some works, multicast topology is taken into account in the formation of the hierarchies: the creation of location-aware structures is discussed in [17], where the formation is achieved by clustering the nodes, using their (assumed known) position. In [23], a topology-matchingkey management tree scheme is presented and is targeted at networks with an inherent hierarchy, which does not fit the profile of ad-hoc networks. In [24], a topological key hierarchy (TKH) approach is presented, in which key hierarchies are constructed based on their connection graph. Results presented show better performance than several LKH-class techniques. However, TKH is only compared to techniques that use randomly-picked structures and thus do not utilize the performance potential of LKH.

In this work we present a set of methods to form LKH structures for a multihop network, given its connection graph. The main characteristic which we seek to optimize is the number of packet transmissions needed for rekeying operations. More specifically we seek to optimize the mean and maximum number of packet transmissions for kick node operations in the LKH scheme. The methods that we propose include the selection of a Key-Server, the derivation of an initial hierarchical structure, based on the network topology, and, finally, a set of local optimization criteria, which improve the performance of the initial hierarchy.

The rest of the paper is organized as follows. In Section 2 a brief overview of the LKH scheme is presented. Section 3 presents an overview of TALK. The network and security assumptions we have made in this work are given in Section 4. In Section 5 we present methods to create preliminary LKH structures for a given network and Key-Server. In Section 6 we give a method to select a Key-Server which leads to minimal rekeying overhead. Procedures to optimize preliminary LKH tree structures taking into account the network topology are given in Section 7. Section 8 contains additional protocols and procedures needed for an actual implementation of our method on a real network. In Section 9 the application of our method is presented in detail for an example network. In Section 10 simulation results are presented on the performance of our method and protocols, and finally, in Section 11 we draw our conclusions.

2. Secure Communications with Logical Key Hierarchy (LKH)

Several classes of network applications use group communication [6], where in order to achieve secure group communication when symmetric ciphers are considered, a TEK generally needs to be shared among members of the group. Alternative approaches such as probabilistic key distribution can be applied, but at a cost, introducing overhead for communication between nodes that do not share keys.

When the group membership changes, the TEK needs to be refreshed, where (a) in the case of a node joining the network and/or periodic key refreshing, the rekeying operation can be performed by simply multicasting the new key to the whole network, and (b) when a node departs (or needs to be kicked), the new key needs to be distributed to the network in a way that the departing node cannot capture it. LKH [16] solves this problem by laying out the network nodes as the leaves in a tree structure (Figure 1).

Figure 1

Logical key hierarchy—node kick example.

Each internal node i is then associated with a key encryption key (KEK) $K_i$ , shared among its descendants. The root represents the TEK, shared among all nodes. Finally, each network node i also holds a KEK $K(u_i)$ that is unique to it and shared only with the Key-Server.

When a node needs to leave the network, all keys corresponding to its path to the root node in the key tree must be renewed, according to the following set of bottom-up operations.

• (1)

The leaving node is removed from the tree.

(2)

For each internal node in the path from the node to the root, a message is sent to each subcluster i, corresponding to one of its children, encrypted with the corresponding KEK $K_i$ .

(3)

If the subcluster is a single leaf j, then the pairwise key $K(u_j)$ is used for the encryption.

For example, consider an 8-node network, laid out in a tree (Figure 1). To kick node $u_{\mathrm{7}}$ , the KEKs $K_{\mathrm{0}}$ , $K_{\mathrm{2}}$ , and $K_{\mathrm{6}}$ need to be changed. $K_{\mathrm{6}}$ is first sent to node 6, encrypted with $K(u_{\mathrm{6}})$ . Then $K_{\mathrm{2}}$ is updated, by sending it to $u_{\mathrm{4}}$ and $u_{\mathrm{5}}$ encrypted with $K_{\mathrm{5}}$ and to $u_{\mathrm{6}}$ encrypted with (the new) $K_{\mathrm{6}}$ . Lastly, $K_{\mathrm{0}}$ is updated, by sending it to $u_{\mathrm{0}}$ , $u_{\mathrm{1}}$ , $u_{\mathrm{2}}$ , and $u_{\mathrm{3}}$ encrypted with $K_{\mathrm{1}}$ and to $u_{\mathrm{4}}$ , $u_{\mathrm{5}}$ , and $u_{\mathrm{6}}$ encrypted with $K_{\mathrm{2}}$ :

$$\begin{array}{cc}& \hspace{0.17em}{\left\{K_{\mathrm{6}}\right\}}_{K\left(u_{\mathrm{6}}\right)}⟶u_{\mathrm{6}},\\ \hspace{0.17em}{\left\{K_{\mathrm{2}}\right\}}_{K_{\mathrm{5}}}⟶\left\{u_{\mathrm{4}},u_{\mathrm{5}}\right\},\\ \hspace{0.17em}{\left\{K_{\mathrm{2}}\right\}}_{K_{\mathrm{6}}}⟶u_{\mathrm{6}},\\ \hspace{0.17em}{\left\{K_{\mathrm{0}}\right\}}_{K_{\mathrm{1}}}⟶\left\{u_{\mathrm{0}},u_{\mathrm{1}},u_{\mathrm{2}},u_{\mathrm{3}}\right\},\\ \hspace{0.17em}{\left\{K_{\mathrm{0}}\right\}}_{K_{\mathrm{2}}}⟶\left\{u_{\mathrm{4}},u_{\mathrm{5}},u_{\mathrm{6}}\right\}.\end{array}$$

(1)

3. Overview of TALK (Topology Aware LKH Key Management)

This work presents a set of algorithms and protocols that aim to calculate a suitable Key-Server and LKH trees for a network, which reduces the traffic incurred on the network, when rekeying is needed.

The main metric which we seek to minimize is the total number of packets transmitted over the network. As previously mentioned, there are two main operations involved in LKH-based key management: (a) the node join operation and (b) the node kick operation. Since (a) is performed using a single broadcast from the Key-Server, we focus on (b) which is a much more overhead incurring operation.

TALK is logically separated into two parts: The Key-Server selection and the key tree formation. The first part is executed on network bootstrap and optionally repeated over large intervals, when massive topology changes take place or the Key-Server functionality has to be handed over to another node (e.g., low energy on the current Key-Server). The second part, the key tree formation, is also executed when a new Key-Server is selected, but it is a simpler procedure that can be executed more often, when the gains in rekeying traffic outweigh the structure change overhead. Local tree optimizations are also defined, opportunities for which can be found and applied without global network topology knowledge.

4. Network and Security Assumptions

In this work we assume the nodes of the network are capable of both unicast and broadcast communication. No routing information is assumed to be known or needed.

An uncompromisable Key Master Server is assumed, which has the capability for secure pairwise communication with all network nodes at network bootstrap. We assume that adversaries can eavesdrop all communication. Also, any number of nodes can be captured and their known secrets made known to adversaries, although detection of such an intrusion is outside the scope of this work. We do not consider Denial of Service attacks, that prevent nodes from receiving any legitimate network packets, but packet loss occurring due to traffic congestion is taken into account and is present in our simulations.

5. Initial Formation of the Key Tree

Our approach for the creation of LKH key trees is based on topological tree representations of the network, which we call topological network trees (TNTs). It is used for finding out the optimal node to function as a Key-Server and also as a basis for the final version of the key tree. It is extracted from the connectivity graph of the network and a selected root node, in a shortest hop count fashion.

The TNT is created (Algorithm 1) in a number of rounds equal to the maximum hop distance from the root. The set $s_u$ of nodes already included in the TNT is formed, and its complimentary set (unused nodes in TNT) $s_{nu}$ is updated in each round. In the first round $s_u$ contains only the root and $s_{nu}$ contains all other nodes. In each round we check for nodes in $s_{nu}$ which are connected to nodes in $s_u$ ; these are removed from $s_{nu}$ , included to the tree as children of members of $s_u$ with an inclusion update to $s_u$ . The process is repeated until $s_{nu}$ is empty and $s_u$ contains all the network nodes.

Algorithm 1: Topological network tree creation.

$s_u$ = {KeyServer}

$s_{nu}$ = AllNodes − {KeyServer}

while   $s_{nu}$ not empty do

  temp = $\{\}$

  for all  i in $s_{nu}$   do

     for  all  j in $s_u$   do

     if  i  adjacent to j  then

       add i as child of j

        $s_{nu}$  −= $\{i\}$

       temp += $\{i\}$

       Break

     end if

     end for

  end for

end while

From the TNT we extract a topological key tree (TKT) using the following recursive algorithm, which creates a topological key subtree (TKsubT) corresponding to a branch in the TNT, rooted at the current node. (1) For the current node, check if it is an intermediate node in the TNT. $(\mathrm{1}\text{a})$ If so, create a logical node (LN), and then create a real node (RN), corresponding to the current node, as a child of this LN. $(\mathrm{2}\text{a})$ For each of the current node's children, run the algorithm, and attach all returned branches to the LN, and $(\mathrm{3}\text{a})$ return the created subtree. $(\mathrm{1}\text{b})$ If the current node is a leaf in the TNT, simply create a RN and return it. When Algorithm 2 is run for the root node in the TNT, it returns a tree which can be used for the purposes of LKH.

Algorithm 2: Topological key subtree creation.

function  makeTKSubT (cnode)

 if cnode has children then

  root = new LogicalNode

  tmp = copy (cnode)

  root.attachchild (tmp)

  for all children ch of cnode do

    tmp = makeTKsubT (ch)

    root.attachchild (tmp)

  end for

 else

  root = copy (cnode)

 end if return root

end function

6. Key-Server Selection

An important step in defining the LKH structures for a given network and topology is the selection of a node that will function as a Key-Server. Depending on the application and node capabilities, this can be predefined and can not be possible or impractical to change (due to the advanced computing capabilities that this node should have in order to accommodate the key management overhead). For the cases where a Key-Server has to be selected among the nodes of the network, it is essential to pick the one which results in small rekeying overhead. This procedure is executed at network deployment time, when initial node positions are established. As it is relatively resource intensive, it is repeated only when needed, as when the current Key-Server is running low on battery or when the network topology has changed so much that it is inefficient to keep the current Key-Server.

We propose two multicriteria selection methods for the Key-Server. (a) The first uses extended network topology information, found in the TNTs of the network and primarily involves calculations of kick node procedures, and (b) the second one involves only the less demanding criteria of the former.

The criteria employed in our approaches are the following:

• (i)

maximum distance from network nodes;

(ii)

sum of distances from network nodes;

(iii)

mean kick node packet cost using the TNT;

(iv)

maximum kick node packet cost using the TNT.

For a specific Key-Server candidate, the TNT is first extracted, followed by calculations for kicking all possible nodes and the mean value is kept; these rekeying operation cost calculations would normally be performed on the TKT, but as at this point the two trees are equivalent, so we perform the calculations on the TNT directly.

A topology matrix T is extracted from the TNT to facilitate easy rekeying overhead calculations. Each element in T is the number of children of a particular node. Each row corresponds to the same level of nodes in the TNT. Using zero-based indexing, the element (0,0) corresponds to the root node. The number of rows in the matrix is equal to the depth of the TNT, while the number of columns used is different for each row, the maximum being equal to the maximum number of nodes in a TNT level, which is at most the number of network nodes minus the root node (star topology). A topology matrix example is shown in Figure 2(b), corresponding to the TNT in Figure 2(a). Unused elements (shown as “N” in Figure 2(b)) can also be stored as zeroes, without affecting the behavior of T.

Figure 2

Example TNT and topology matrix.

Using this network topology representation, we can calculate the number of packet transmissions needed in order to kick a specific node from the network. The number of packets needed for multicast to the whole network is the number of nonzero, nonunused elements in T:

$$\begin{array}{cc}& {\displaystyle \sum }_x‍\hspace{0.17em}{\displaystyle \sum }_l‍\mathrm{sign}\left(T[l,x]\right),\end{array}$$

(2)

where sign $(x)=1(0)$ if x is positive (nonnegative). The index of the first child of a node $(l,r)$ is

$$\begin{array}{cc}& \left(l+\mathrm{1},{\displaystyle \sum }_{x=\mathrm{0}}^{r-\mathrm{1}}‍T\left[l,x\right]\right),\end{array}$$

(3)

while the index of the last child of a node $(l,r)$ is

$$\begin{array}{cc}& \left(l+\mathrm{1},{\displaystyle \sum }_{x=\mathrm{0}}^r‍\left(T\left[l,x\right]\right)-\mathrm{1}\right).\end{array}$$

(4)

Similarly, the index of the parent of a node $(l,r)$ is

$$\begin{array}{cc}& \text{Par}\left(T,l,r\right)=\left(l-\mathrm{1},\min \left(p:{\displaystyle \sum }_{k=\mathrm{0}}^p‍T\left[l,k\right]>x\right)\right).\end{array}$$

(5)

It should be noted that, in a recursive manner, the genealogical tree of a node can be computed by successive iterations of the aforementioned “parent”-equation.

The number of packets $\text{MulST}\hspace{0.17em}\hspace{0.17em}(T,l,r)$ , needed for a multicast transmission to a subtree in the network, can be calculated (in a recursive manner) as

$$\begin{array}{l}\text{MulST}\left(T,l,r\right)\hfill \\ \hspace{1em}\hspace{1em}=\mathrm{sign}\left(T[l,r]\right)+{\displaystyle \sum }_{x={\sum }_{x=\mathrm{0}}^{r-\mathrm{1}}T[l,x]}^{{\sum }_{x=\mathrm{0}}^r\left(T\right[l,x\left]\right)-\mathrm{1}}‍\text{MulST}(T,l+\mathrm{1},x).\hfill \end{array}$$

(6)

A leaf node $(l,r)$ can be removed from T by reducing its parent element by 1, removing its element from T, and shifting all nodes $\left(l,x\right)$ : for all $x>r$ to the left.

6.1. Number of Packets for Node-“Kicking”

In order to compute the number of packets needed to kick node $u_k=(l_k,r_k)$ , consider the following auxiliary variables: (a) the set $L=\left\{\text{Pa}{\text{r}}^i(T^{\prime },l_k,x_k),\mathrm{1}\le i\le l_k\right\}$ and (b) $T^{\prime }=T-(l_k,{\text{r}}_k)$ ; then the needed number of packets is

$$\begin{array}{l}P\left(u_k\right)={\displaystyle \sum }_{(l_i,x_i)\in L}‍T^{\prime }\left[l_i,x_i\right]\left(l_i+\mathrm{1}\right)\hfill \\ \hspace{1em}+\max \left(\text{MulST}\left(T^{\prime },l_i,x_i\right)-\mathrm{1,0}\right).\hfill \end{array}$$

(7)

For the “Key-Server” selection approach, the kick node packet cost is calculated for all leaves of the network; the mean and maximum cost will be used in the “Key-Server” selection process. The mean (maximum) number of packets for kicking a node is normally defined as the mean (maximum) values (from (7)) iterated through all network nodes. However, kicking internal nodes would result to changes in the network topology, and can disconnect the network graph. So, for the sake of simplicity, we calculate only the packet counts for kicking leaf nodes of the network.

6.2. Maximum Distance from Network Nodes

The Key-Server should not distanced from the far nodes of the network, since this will involve the transmission of signals with a large number of hops. Hence, for each node $u_i$ , its maximum distance in hops from all other network nodes is considered. Minimization of this criterion leads to selected Key-Server nodes that are close to the center of the network:

$$\begin{array}{cc}& M_d\left(u_i\right)=\underset{u_j\in \text{network}}{\max }\left(\text{hops}(u_i,u_j)\right).\end{array}$$

(8)

It should be noted that $M_d$ is also equal to the number of rows of the T matrix.

6.3. Sum of Distances from Network Nodes

In order to capture the need on a median-basis for the Key-Server to communicate with all nodes, there is a need to transmit messages to each node, and henceforth the sum of hop-counts from the candidate $u_i$ -node to all network nodes is considered:

$$\begin{array}{l}{S}_d\left(u_i\right)={\displaystyle \sum }_{\hspace{0.17em}}^{u_j\in \text{network}}\text{hops}\left(u_i,u_j\right)\hfill \\ ={\displaystyle \sum }_{l,x}‍l\times T\left[l,x\right].\hfill \end{array}$$

(9)

6.4. Extended Key-Server Selection Method

For the Key-Server node-selection, we calculate for each Key-Server candidate $u_i$ the following quantities: (a) $M_d(u_i)$ , (b) $S_d(u_i)$ , (c) the average number of packets needed to kick a node $P_a(u_i)$ , and (d) the maximum number of packets needed to kick a node $P_m(u_i)$ .

A fitness values is formed for each Key-Server candidate

$$\begin{array}{l}F\left(u_i\right)=w_d\frac{M_d\left(u_i\right)}{{\max }_{j\in T}{M}_d\left(u_j\right)}+w_s\frac{S_d\left(u_i\right)}{{\max }_{j\in T}{S}_d\left(u_j\right)}\hfill \\ \hspace{1em}+w_k^a\frac{P_a\left(u_i\right)}{{\max }_{j\in T}{P}_a\left(u_j\right)}+w_k^m\frac{P_m\left(u_i\right)}{{\max }_{j\in T}{P}_m\left(u_j\right)},\hfill \end{array}$$

(10)

where $w_d$ , $w_s$ , $w_{ka}$ , and $w_{km}$ are positive weights for each normalized quantity. The node that is selected as a Key-Server is the one with the smallest fitness value from (10). It should be noted that this method for the Key-Server selection takes into account the major terms involved in this operation. Among these terms, the ones that are computationally demanding are the $P_a(u_i)$ and $P_m(u_i)$ .

6.5. Simplified Key-Server Selection Method

In addition to our main Key-Server selection method, we proposed a simplified version, which can be used in situations where a very calculation overhead is of high importance. In this version, the more computationally demanding factors, $P_a(u_i)$ and $P_m(u_i)$ , are stripped from (10), which leads to a simple calculation, which also needs less information to be performed:

$$\begin{array}{cc}& F_s\left(u_i\right)=w_d\frac{M_d\left(u_i\right)}{{\max }_{j\in T}{M}_d\left(u_j\right)}+w_s\frac{S_d\left(u_i\right)}{{\max }_{j\in T}{S}_d\left(u_j\right)}.\end{array}$$

(11)

From a practical point of view, this selection is simple enough to be implemented on a real network. One possible implementation is the flooding of the network with hop-count packets, where each node transmits a message to the network, containing its node-identification and current hop count (starting at one). The nodes that receive this message forward it, thus increasing the hop count. If the message is received in multiple occasions at a node, a forwarding is triggered if and only if the received packet contains a smaller hop count. At the end of this process, each node stores the hop-distances from the other network's nodes and can simply find the largest hop-count $M_d$ and compute its corresponding $S_d$ -value. The results can either be sent to an authority which will select the Key-Server or can be advertised on the network, in a collaborative approach.

7. Optimization of the Key Tree

Once the Key-Server is selected and the TKT is created, we seek to optimize it with regard to the packets needed for rekeying. Local optimizations are applied, which are easily calculated and implemented in actual networks, where global network knowledge is difficult to achieve. In addition to the TKT construction time, these optimizations can be performed periodically or on opportunity detection.

In order to accomplish this task, we remove superfluous logical nodes (LNs) while at the same time, we create additional LNs in segments with many children.

7.1. Removal of Superfluous Logical Nodes

Depending on the structure of the underlying network, some parts of the TKT might be deeply nested, with a small number of leaves, which leads to an increased rekeying overhead. Our local optimization algorithm looks for nodes with one logical child and few real children and optimizes their logical child out, as in Figure 3. Specifically, the optimization is applied when a logical node is found with no more than one logical and one real child. It should be noted that the TKT creation algorithm does not produce LNs with only one logical child or one real child, but such nodes are possible, especially when considering membership changes during run-time.

Figure 3

Superfluous LN removal.

Regarding the rekeying cost in such key segments, let us consider a nested structure like in Figure 3(a), where there is a LN A with n RN children and a LN child B, which in turn has m RN descendants (not necessarily direct descendants). Let the mean cost in number of transmissions for a packet from the Key-Server to reach one of of A's children be $c_A$ . Let the corresponding cost for a packet from the Key-Server to one of B's descendants be $c_B$ . Let finally $\text{M}{\text{C}}_B$ be the cost for a multicast to the RN descendants of B and $\text{M}{\text{C}}_{B-\mathrm{1}}$ the mean for a multicast to all but one of the RN descendants of B. Then, the mean rekeying cost in the original nested part of the tree is

$$\begin{array}{cc}& \frac{m\left((m-\mathrm{1})c_B+\text{M}{\text{C}}_{B-\mathrm{1}}+n{c}_A\right)+n\left(\text{M}{\text{C}}_B+(n-\mathrm{1})c_A\right)}{m+n},\end{array}$$

(12)

while the mean rekeying cost for the flattened part of the tree is

$$\begin{array}{cc}& \frac{m((m-\mathrm{1})c_B+n{c}_A)+n(m{c}_B+(n-\mathrm{1})c_A)}{m+n}.\end{array}$$

(13)

From (12) and (13), it follows that when

$$\begin{array}{cc}& m\text{M}{\text{C}}_{B-\mathrm{1}}+n\text{M}{\text{C}}_B-nm{c}_B>\mathrm{0},\end{array}$$

(14)

the flattened version of the key tree is preferable, cost-wise. It should be noted that when $n=\mathrm{1}$ , (14) is reduced to

$$\begin{array}{cc}& m\text{M}{\text{C}}_{B-\mathrm{1}}+\text{M}{\text{C}}_B-m{c}_B>\mathrm{0}.\end{array}$$

(15)

Since

$$\begin{array}{cc}& m\text{M}{\text{C}}_{B-\mathrm{1}}={\displaystyle \sum }_{i=\mathrm{0}}^m‍\left(\text{M}{\text{C}}_B\text{-path}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{exclusive}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{node}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\right)\end{array}$$

(16)

implying that

$$\begin{array}{cc}& m\text{M}{\text{C}}_{B-\mathrm{1}}>(m-\mathrm{1})\text{M}{\text{C}}_B.\end{array}$$

(17)

Henceforth from (15) and (17)

$$\begin{array}{cc}& m\text{M}{\text{C}}_{B-\mathrm{1}}+m\text{M}{\text{C}}_B-m{c}_B>m\left(\text{M}{\text{C}}_B-c_B\right)\ge \mathrm{0}\end{array}$$

(18)

which is always true. Therefore, the following rule should be applied.

Rule #1. When there is one LN-A in the key tree which has one LN-child-B and one RN-child, it is always preferable to remove B from the tree and attach its descendants to A.

7.2. Creation of Additional Logical Nodes

Complementary to the optimization of over-nested parts of the key tree, there can also exist flat tree segments, which increase the rekeying cost in a linear relationship to the network size. Our optimization algorithm creates additional hierarchy to reduce the rekeying packet transmissions. Specifically it looks for LNs with multiple RN-children and at least one LN-child and subsequently creates a new LN-child and nests the RN-children under it, as shown in Figure 4.

Figure 4

Addition of new LNs.

The initial form of the considered tree segment (Figure 4(a)) is the same as in Section 7.1, with the rekeying cost described in (12):

$$\begin{array}{l}\frac{m}{m+n}\left(\left(m-\mathrm{1}\right)c_B+\text{M}{\text{C}}_{B-\mathrm{1}}+\text{M}{\text{C}}_A\right)\hfill \\ \hspace{1em}\hspace{1em}+\frac{n}{m+n}\left(\left(n-\mathrm{1}\right)c_A+\text{M}{\text{C}}_{A-\mathrm{1}}+\text{M}{\text{C}}_B\right).\hfill \end{array}$$

(19)

When the RN-children of A are nested under the new LN-C (Figure 4(b)), the corresponding rekeying cost for the tree segment becomes

$$\begin{array}{cc}& \frac{m((m-\mathrm{1})c_B+\text{M}{\text{C}}_{B-\mathrm{1}}+n{c}_A)+n(\text{M}{\text{C}}_B+(n-\mathrm{1})c_A)}{m+n}.\end{array}$$

(20)

Thus, it is beneficial to add LN-C when the cost in (12) is greater than in (20) or

$$\begin{array}{cc}& mn{c}_A-m\text{M}{\text{C}}_A-n\text{M}{\text{C}}_{A-\mathrm{1}}\ge \mathrm{0}.\end{array}$$

(21)

Since $\text{M}{\text{C}}_A>\text{M}{\text{C}}_{A-\mathrm{1}}$ , a conservative inequality to (21) can be derived as

$$\begin{array}{cc}& \frac{c_A}{\text{M}{\text{C}}_A}\ge \frac{m+n}{mn}.\end{array}$$

(22)

It should be noted that (22) can serve as a criterion for additional node creation where extended topology information is available. However, results of our simulations show that in most occasions, nesting RN-children of a LN-A which additionally has at least one LN-child, under a new LN-C, reduces the rekeying cost; this is due to the over-conservatism embedded in (22). Henceforth, the second optimization rule is as follows.

Rule #2. When there is one LN with multiple RN-children and at least one LN-child, then create a new LN-child and nest the RN-children under it, if (20) is satisfied.

Since the knowledge of the network's topology for validating (20) is immense, an over-conservative variation of the previous Rule #2 can be employed by switching (22) with (20).

8. Adaptation and Additional Protocols for Implementation on a Sensor Network

The procedures described above require an extensive knowledge of the network topology, in order to function. Specifically, in order for every node to calculate its fitness value as a Key-Server, four (two) factors need to be calculated for the extended (simplified) Key-Server selection method. We focus on the extended version, the requirements of which are a superset of those of the simplified method.

To calculate its fitness value, each node $u_i$ needs to compute its own parameters $M_d(u_i)$ , $S_d(u_i)$ , $P_a(u_i)$ , and $P_m(u_i)$ . As described in Section 6, the calculation of the latter two requires a TNT representation of the network, rooted on $u_i$ , while the first two quantities can also be computed using this knowledge.

This information is gained via a flooding of the routing information; once the aforementioned parameters are calculated, the evaluation of (11) requires the computation of the terms ${\max }_{j\in T}(·)$ . These can be made known throughout the network by a simple flooding of the parameters' values of each node and the fitness values $F(u_i)$ , $i\in T$ can then take place. Subsequently the node that is selected as a Key-Server can proceed to form and optimize the TKT of the network. Overall, the following steps are required on an actual network to select a suitable Key-Server and form a TKT:

• (1)

flooding of routing information;

(2)

calculation of $M_d(u_i)$ , $S_d(u_i)$ , $P_a(u_i)$ , and $P_m(u_i)$ at each node;

(3)

flooding of the previously calculated parameters and computation of their maximum values over all network's nodes;

(4)

calculation of fitness values at each node;

(5)

flooding of the fitness values and selection of the minimum fitness value along with the respective node identification;

(6)

calculation of the optimized TKT at the selected Key-Server node.

In the sequel, we provide a detailed description of each step.

8.1. Flooding of Routing Information

The goal of this step is for all nodes to acquire a tree representation of the network, rooted on themselves. It is assumed that initially all nodes have no information on the network topology. At the beginning, all nodes start broadcasting the routing information that they currently hold.

The structure of the packets being broadcast from a node is a chain of nodes stemming at each node; this corresponds to a topological chain, (i.e., node k in the chain is a neighbor with nodes $k-\mathrm{1}$ and $k+\mathrm{1}$ ). In general, when it is time for a node to broadcast a routing information packet, it selects one of its reachable nodes and broadcasts a packet with a route chain leading to that node. In the beginning, since the nodes are unaware of the network's topology, they broadcast a generic message announcing their existence.

In our prototype implementation, target nodes are selected by selecting a random node (among the known ones) and then recursively picking random descendants until a network-leaf has been found. This leaf is selected as a target node. The use of leaves as target nodes aims to exploit available packet space, in order to broadcast more routing information in a single packet.

The structures used for storage of routing information contain (a) the node's identification number, (b) the number of hops needed to reach it, (c) a link to its parent, and (d) links to its children. When a routing packet is received at a node, the node checks if the packet contains new and/or more efficient routing paths, compared to the ones already known. The checking starts at the first element in the packet, that is, the node which actually broadcast the packet. Two checks are made for each element $p_k$ in the packet (k denoting the order within the packet): (i) whether $p_k$ is already known and (ii) whether the new route path is shorter than the one already known; if the new route is longer than the one known, this packet is ignored.

If $p_k$ was previously unknown, then it is added as a child to $p_{k-\mathrm{1}}$ , the previous node in the routing packet. Similarly, the number of hops k to reach it is also stored in the structure.

If $p_k$ was already known, but the new route is shorter than the stored one, the route is updated. The parent of $p_k$ is switched to $p_k$ , its hop distance is updated, and finally, the hop distances of all its descendants are updated to reflect the new route.

This procedure is equivalent to the one described in Section 5. One difference is that the former picks lexicographically first parents, when there are multiple options for the placement of a node, while this one favors the one that was found first, in order to minimize changes in the topology.

8.2. Calculation of Fitness Function Factors $M_d$ , $S_d$ , $P_a$ , and $P_m$ at Each Node

This step contains most of the calculations mentioned in Section 6. Since a TNT exists in each node, the noted parameters in the fitness equation (10) can be calculated at the respective nodes using the aforementioned procedure.

8.3. Flooding of ${\max }_{j\mathbf{\in }T}{M}_d\mathbf{\left(}{S}_d\mathbf{\right)}\mathbf{\left[}{P}_a\mathbf{\right]}{P}_m\mathbf{\left(}{u}_j\mathbf{\right)}$ Values

This step aims to make the ${\max }_{j\in T}{M}_d(S_d)[P_a]P_m(u_j)$ values known to all network nodes by a simple periodic broadcasting to the network from each node of its these parameters' stored values. In the beginning, each node broadcasts its own values and when a packet with new values arrives, the maximum values are updated and are broadcast at the next interval.

8.4. Calculation of Fitness Values $F_s\mathbf{\left(}{u}_i\mathbf{\right)}$ at Each Node

After a large interval, all needed values in (10) are known at each node, and its fitness value can be locally calculated.

8.5. Flooding of ${\min }_{i\mathbf{\in }T}{F}_s\mathbf{\left(}{u}_i\mathbf{\right)}$ and Node Identification

At this time, each node holds its own fitness value, and these values are broadcast in order for all nodes to acknowledge the one with the minimum value. In a procedure similar to the step of Section 8.3, the pair of (a) $F_s(u_i)$ fitness value and (b) i-node identification are periodically broadcast, and the minimum is kept at each node. In order to resolve any conflicts, when two nodes with the same fitness exist, the lexicographically first (by its identification number) is selected.

8.6. Calculation of Optimized TKT at the Selected Key-Server Node

At this time, the new Key-Server is chosen and can calculate the optimized key tree, as described in Section 7. Finally, keys must be generated for each key tree node and transmitted to the appropriate nodes.

9. LKH Application Example

As an application example, assume the 20 node network of Figure 5, in which we need to use LKH. We focus on the algorithmic procedure, assuming centralized and complete network knowledge.

Figure 5

Example network.

9.1. Selection of the Key-Server

To create an LKH structure for the given network, it must first be decided which node will function as the Key-Server. To that end, the procedure described in Section 6 is followed. The criteria used for the selection of the Key-Server are the maximum distance (equation (8)), the sum of distances (equation (9)) from the rest of the nodes, and the mean and maximum of packet transmissions for a kick operation, when using the corresponding TKT (7). The selected weight parameters were $w_d=\mathrm{2}$ , $w_s=\mathrm{1}$ , $w_k^a=\mathrm{5}$ , and $w_k^m=\mathrm{5}$ . The values calculated for each of the possible Key-Servers (i.e., all network nodes for this case) are shown in Table 1.

Table 1

Parameter values used in Key-Server selection.

Node ID	$M_d$	$S_d$	$P_a$	$P_m$	$F(u_i)$
0	6	57	39.25	79	8.14
1	5	56	37.77	67	7.25
2	4	43	22.62	35	4.53
3	6	57	39.25	79	8.14
4	6	56	37.00	79	7.99
5	5	58	38.17	65	7.22
6	4	44	25.92	45	5.16
7	5	45	26.85	56	5.98
8	7	87	78.25	121	13.00
9	5	58	38.17	65	7.22
10	5	58	38.17	65	7.22
11	6	57	39.73	76	8.05
12	4	48	28.58	45	5.38
13	6	70	54.23	93	9.83
14	6	60	40.38	80	8.29
15	7	72	57.36	105	10.83
16	7	87	78.25	121	13.00
17	5	58	38.17	65	7.22
18	7	78	62.75	108	11.37
19	7	71	56.00	104	10.69

The node with identification index number 2 minimizes the fitness function (10) and is selected to function as a Key-Server for the network.

9.2. Initial Formation of the Key Tree

As soon as the Key-Server has been selected, the rest of the key tree can be formed. The step of the initial formation of the tree is performed first (this procedure is actually performed at the selection of the Key-Server for all candidates, but it is presented here only for the actual chosen Key-Server, for conciseness and clarity).

As described in Section 5, using the selected root node (Key-Server) and connection graph, a TNT is extracted, shown in Figure 7(a). The operation of our tree creation algorithm is as follows.

• (i)

Initially,

$$\begin{array}{l}\hspace{0.17em}{s}_u=\left\{\mathrm{2}\right\},\hfill \\ s_{nu}=\left\{\mathrm{0,1},\mathrm{3,4},\mathrm{5,6},\mathrm{7,8},\mathrm{9,10,11,12,13,14,15,16},\right.\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\mathrm{17},\left.\mathrm{18,19}\right\}.\hfill \end{array}$$

(23)

(ii)

Nodes in $s_{nu}$ are checked for adjacency to nodes in $s_u$ . $s_u$ contains only node 2, and the nodes adjacent to that are 6, 7, and 12. They are removed from $s_{nu}$ and appended to $s_u$ . The sets are now

$$\begin{array}{cc}& \hspace{0.17em}{s}_u=\left\{\mathrm{2,6},\mathrm{7,12}\right\},\\ \hspace{0.17em}{s}_{nu}=\left\{\mathrm{0,1},\mathrm{3,4},\mathrm{5,8},\mathrm{9,10,11,13,14,15,16,17,18,19}\right\}.\end{array}$$

(24)

 

The current tree is shown in Figure 6(a).

(iii)

Nodes in $s_{nu}$ are checked for adjacency to 2, 6, 7, and 12. Nodes 0, 3, 4, 11, and 14 are adjacent to 7. Node 1 is adjacent to 6. Nodes 5, 9, 10, and 17 are adjacent to both 6 and 12, and they are appended to the tree as children of 6, due to lexicographical priority (the algorithm checks for adjacency using lexicographical order). The sets are now

$$\begin{array}{cc}& \hspace{0.17em}{s}_u=\left\{\mathrm{0,2},\mathrm{3,4},\mathrm{5,6},\mathrm{7,10,11,12,14,17}\right\},\\ \hspace{0.17em}{s}_{nu}=\left\{\mathrm{1,8},\mathrm{9,13,15,16,18,19}\right\}.\end{array}$$

(25)

 

The current tree is shown in Figure 6(b).

(iv)

The nodes that are adjacent to the ones in $s_u$ are 1 (to 6), 15 and 19 (to 0), and 18 (to 14). The sets are now

$$\begin{array}{cc}& \hspace{0.17em}{s}_u=\left\{\mathrm{0,1},\mathrm{2,3},\mathrm{4,5},\mathrm{6,7},\mathrm{10,11,12,14,17,18,19}\right\},\\ \hspace{0.17em}{s}_{nu}=\left\{\mathrm{8,9},\mathrm{13,15,16,18}\right\}.\end{array}$$

(26)

 

The current tree is shown in Figure 6(c).

(v)

The remaining nodes, 8 and 16, are added to the tree as children of 13. The resulting TNT is shown in Figure 7(a).

Figure 6

Intermediate trees of the example network.

Figure 7

Initial trees of the example network.

The TKT is then extracted from the TNT using Algorithm 2. Essentially, for each non-leaf RN (excluding the root node), a LN is created and positioned in its place in the tree, and the RN is attached as a child of the newly created LN.

Specifically in our example, the nodes 0, 1, 6, 7, 13, and 14 are such internal RNs. LNs L0, L1, L6, L7, L13, and L14 are created and take the place in the tree, which are then attached beneath the latter. The resulting TKT is shown in Figure 7(b).

9.3. Optimization of the Key Tree

After the TKT-formation, its optimization takes place, based on the following steps.

• (1)

The TKT is searched for superfluous LNs (LNs with no more than 1 LN and 1 RN child). In our example, the only superfluous LN is L1 (its children are 1 and L13). As such, it is removed and its children are attached to its parent, L6. The result is shown in Figure 8(a).

(2)

The tree is searched for segments where additional nodes should be created (LNs with at least one LN child and multiple RN children). The first such node found is L2, which has the LN children L6 and L7 and the RN children 2 and 12. A new LN LMC2 is created under L2, and 2 and 12 are nested under it, as shown in Figure 8(b).

(3)

The next candidate segment for additional LNs is the one under L6, which has 1 LN child and 5 RN children. The new LN LMC6 is created under L6, and the 5 RN children are nested under it, as shown in Figure 8(c).

(4)

The last candidate segment for additional LNs is the one under L7, which has 2 LN children and 4 RN children. The new LN LMC7 is created under L7, and the 4 RN children are nested under it, as shown in Figure 8(d).

Figure 8

Optimizations of the key tree.

Simulations were performed for the previous four optimization steps of the process, measuring the mean and maximum number of packets required for rekeying. The results are shown in Table 2.

Table 2

Simulation results for the example network.

	$P_a(u_i),i\in T$	$P_m(u_i),i\in T$
TKT	22.62	35
Step $1$ optimization	22.00	31
Step $2$ optimization	22.00	31
Step $3$ optimization	21.54	27
Step $4$ optimization	20.85	24

10. Simulation Studies

In order to evaluate our key tree generation method performance, we implemented our algorithms and protocols on top of the Contiki OS [25] and ran simulations on the Cooja Network Simulator [26]. The nodes of the networks were TelosB nodes [27], emulated using MSPSim [28], an instruction-level simulator for Texas Instruments' MSP430 based systems.

For the purposes of our measurements, the network nodes were roughly synchronized, and the same predefined time periods were given for each calculation and communication step. The measurements taken were the actual time needed for each step, (a) the output of each factor of the fitness function and (b) the final result for each node.

In the sequel, we present the results produced for the network used in Section 9, shown in Figure 5. Time results are shown in Table 3. Table 4 shows the difference in calculated results versus the theoretical results, which is due to the topology information being acquired from the actual network, subject to limited bandwidth, collisions, and limited time.

Table 3

Computation/networking timing needs per procedure's step.

Operation	Time (ms)
Complete network mapping	11623
Network mapping at key server node	4473
Maximum values flooding	2566
Extended fitness calculation	average: 43/range: 34–53
Quick fitness calculation	4
Fitness value flooding	507
Key tree creation at Key-Server	166
Key tree optimization at Key-Server	20
Total procedure time	14925

Table 4

Difference of theoretical versus network calculations.

Characteristic	Average	Maximum
	difference (%)	difference (%)
Maximum distance	0	0
Sum of distances	0	0
Average rekeying cost	4.1	12.5
Maximum rekeying cost	9.8	15
Fitness values	2.8	5.9

As shown in Table 3, the entire procedure needs, for our network, less than 15 seconds, which is quite reasonable, taking into account that it will only be run at network bootstrap and possibly few times at runtime, when deemed necessary by severe topology changes, having a negative impact on rekeying performance.

If we assume that the network topology changes can be detected, it is relatively easy to calculate the current rekeying performance and evaluate the gain of modifying the key tree structure to improve the latter. It should be noted that that the combined fitness calculation, key tree creation, and optimization need a mere 229 ms ( $=\mathrm{43}\hspace{0.17em}\text{ms}+\mathrm{166}\hspace{0.17em}\text{ms}+\mathrm{20}\hspace{0.17em}\text{ms}$ ).

Examining Table 4, we can observe the difference of theoretical and simulated results. The maximum distance and sum of distances factors are exactly the same for both cases. These factors depend on the initial key tree creation procedure, described in Section 5, and its adaptation for the networked-version, described in Section 8. The centralized theoretical version is designed to connect nodes to the root using minimum hop-distances, resulting in minimum results for these factors. The simulated results are exactly the same, meaning that the route network discovery protocol also yields minimum hop-distance connections.

Associating the rekeying cost into a network load context, as shown in [29], a packet rate of up to 12.8 packets/second at the Key-Server could be used before the appearance of packet loss. The rekeying process will take a time proportionate to the number of unique rekeying messages created and sent by the Key-Server. With the selected (optimal) Key-Server in our example network, the number of unique messages can reach 14, before optimizations and 9 after optimizations. This translates to 1.09 and 0.7 seconds, accordingly, needed for the rekeying procedure. However, when a nonoptimal Key-Server is chosen, the number of unique messages jumps to 24 and the time to 1.875 seconds accordingly.

Regarding the rekeying cost metrics, we observe some difference between theoretical and simulation values, which is is due to a subtle difference in their key creation algorithm. In the centralized theoretical model, we choose the lexicographically first option, when there are multiple possible parents for a specific node. In the network version, however, we keep the firstly discovered parent, when a newly found one does not reduce the node distance, aiming to minimize changes in stored topologies. These differences however do not have a great impact on the calculated fitness value, the difference averaging at 2.8% between theoretical and simulation results.

11. Conclusions

In this work we presented a novel method to apply logical key hierarchy class key management to multihop networks, using knowledge of the network topology in order to reduce rekeying overhead. A multicriterion approach of selecting the Key-Server is presented followed by a method for defining an LKH structure using the connection graph of the network and the selected Key-Server node, which is comprised of an initial tree formation step and subsequent tree optimization steps. Due to the simplicity of the recalled procedures, the presented methods presented can easily be implemented on actual low resource MANETs and optimization can also be done at runtime, providing low cost key management for such networks.