DocumentCode :
1631040
Title :
The thinnest path problem for secure communications: A directed hypergraph approach
Author :
Jianhang Gao ; Qing Zhao ; Swami, Ananthram
Author_Institution :
Univ. of California, Davis, Davis, CA, USA
fYear :
2012
Firstpage :
847
Lastpage :
852
Abstract :
We formulate and study the thinnest path problem in wireless ad hoc networks. The objective is to find a path from the source to the destination that results in the minimum number of nodes overhearing the message by carefully choosing the relaying nodes and their corresponding transmission power. We adopt a directed hypergraph model of the problem and establish the NP-completeness of the problem in 2-D networks. We then develop a polynomial-time approximation algorithm that offers a √n/2 approximation ratio for general directed hypergraphs (which can model non-isomorphic signal propagation in space) and constant approximation ratio for disk hypergraphs (which result from isomorphic signal propagation). We also consider the thinnest path problem in 1-D networks and 1-D networks embedded in 2-D field of eavesdroppers with arbitrary unknown locations (the so-called 1.5-D networks). We propose a linear-complexity algorithm based on nested backward induction that obtains the optimal solution to both 1-D and 1.5-D networks. In particular, no algorithm, even with the complete knowledge of the locations of the eavesdroppers, can obtain a thinner path than the proposed algorithm which does not require the knowledge of eavesdropper locations.
Keywords :
ad hoc networks; computational complexity; relay networks (telecommunication); telecommunication security; 1.5D networks; 1D networks; 2D networks; NP-completeness; directed hypergraph approach; directed hypergraph model; disk hypergraphs; eavesdropper locations; eavesdroppers; isomorphic signal propagation; linear-complexity algorithm; nested backward induction; polynomial-time approximation algorithm; relaying nodes; secure communications; thinnest path problem; transmission power; wireless ad hoc networks; Approximation algorithms; Approximation methods; Heuristic algorithms; Mobile ad hoc networks; Power control; Shortest path problem; Time complexity;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4673-4537-8
Type :
conf
DOI :
10.1109/Allerton.2012.6483306
Filename :
6483306
Link To Document :
بازگشت