Optimally Increasing Secure Connectivity in Multihop Wireless Adhoc Networks

Optimally Increasing Secure Connectivity in Multihop Wireless Adhoc Networks

Bülent Yener

Seyit Ahmet Camtepe

Sahin Albayrak

We consider the problem of how to maximize secure connectivity of Multihop Wireless Ad-hoc Networks (MWANET) after deployment. Two approaches, based on graph augmentation problems with nonlinear edge costs, are formulated. The first one is based on establishing a secret key using only the links that are already secured by secret keys. This problem is in NPC and does not accept polynomial time approximation scheme PTAS since minimum cutsets to be augmented do not admit constant costs. The second one is based of increasing the power level between a pair of nodes that has a secret key to enable them physically connect. This problem can be formulated as the optimal key establishment problem with interference constraints with biobjectives: (i) maximizing the concurrent flow, (ii) minimizing the cost. We show that both problems are NP-Hard and MAX-SNPHard (i.e., it is NP-Hard to approximate them within a factor of 1 + ² for ² > 0) with a reduction to MAX3SAT problem. Thus, we design and implement a fully distributed algorithm for authenticated key establishment for a MWANET where each sensor knows only its one-hop neighborhood. Our witness based approach finds witnesses in at most two hop neighborhood with a probability close to one for large MWANET deployments.

Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY

CS-09-01