1Energy and Bandwidth-Efficient Key Distribution in Wireless Ad-Hoc Networks: A Cross-Layer Approach

Abstract—We address the problem of resource-efficient access control for group communications in wireless ad-hoc networks. Restricting the access to group data can be reduced to the problem of securely distributing cryptographic keys to group members, known as the key distribution problem (KDP). We examine the KDP under four metrics: (a) member key storage, (b) group controller (GC) transmissions, (c) multicast group (MG) update messages, and (d) average update energy. For each metric, we formulate an optimization problem and show that the KDP has unique solutions for metrics (a) and (b), while is NP-complete for (c) and (d). We propose a cross-layer heuristic algorithm called VP3 that bounds member key storage, and GC transmissions, while significantly reducing the energy and bandwidth consumption of the network. We define the notion of path divergence as a measure of bandwidth efficiency of multicasting, and establish an analytical worst-case bound for it. Finally, we propose On-line VP3 which dynamically updates the key assignment structure according to the dynamics of the communication group in a resource-efficient way. Index Terms—key distribution, secure group communication, key management, security, multicast, ad-hoc. I