Complexity of increasing the secure connectivity in wireless ad hoc networks


Autoria(s): Camtepe, Seyit A.
Contribuinte(s)

Boyd, Colin

Simpson, Leonie

Data(s)

01/07/2013

Resumo

We consider the problem of maximizing the secure connectivity in wireless ad hoc networks, and analyze complexity of the post-deployment key establishment process constrained by physical layer properties such as connectivity, energy consumption and interference. 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 shared keys. This problem is in NP-hard and does not accept polynomial time approximation scheme PTAS since minimum cutsets to be augmented do not admit constant costs. The second one extends the first problem by 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 bi-objectives: (i) maximizing the concurrent key establishment flow, (ii) minimizing the cost. We prove that both problems are NP-hard and MAX-SNP with a reduction to MAX3SAT problem.

Formato

application/pdf

Identificador

http://eprints.qut.edu.au/59426/

Publicador

Springer

Relação

http://eprints.qut.edu.au/59426/1/SACamtepe_Paper30_22042013.pdf

DOI:10.1007/978-3-642-39059-3_25

Camtepe, Seyit A. (2013) Complexity of increasing the secure connectivity in wireless ad hoc networks. Lecture Notes in Computer Science : Information Security and Privacy, 7959, pp. 363-378.

Direitos

Copyright 2013 Springer

The original publication is available at SpringerLink http://www/springerlink.com

Fonte

School of Electrical Engineering & Computer Science; Information Security Institute; Science & Engineering Faculty

Palavras-Chave #080303 Computer System Security #Wireless sensor networks #key pre-distribution #complexity of key establishment
Tipo

Journal Article