Accession Number : AD1003254


Title :   The Thinnest Path Problem


Descriptive Note : Journal Article


Corporate Author : Army Research Laboratory Adelphi United States


Personal Author(s) : Gao,Jianhang ; Zhao,Qing ; Swami,Ananthram


Full Text : http://www.dtic.mil/get-tr-doc/pdf?AD=AD1003254


Report Date : 22 Jul 2016


Pagination or Media Count : 14


Abstract : We formulate and study the thinnest path problem for secure communication in wireless ad hoc networks. The objective is to find a path from a source to its destination that results inthe minimum number of nodes overhearing the message by a judicious choice of relaying nodes and their corresponding transmission powers. We adopt a directed hypergraph model of the problem and establish the NP-completeness of the problem in 2-D networks. We then develop two polynomial-time approximation algorithms that offer and approximation ratios for general directed hypergraphs (which can model nonisotropic signal propagation in space) and constant approximation ratios for ring hypergraphs (which result from isotropic signal propagation). We also consider the thinnest path problem in 1-D networks and 1-D networks embedded in a 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 for both 1-D and 1.5-D networks. This algorithm does not require the knowledge of eavesdropper locations and achieves the best performance offered by any algorithm that assumes complete location information of the eavesdroppers.


Descriptors :   NETWORK SECURITY TECHNIQUES , AD HOC NETWORKS


Distribution Statement : APPROVED FOR PUBLIC RELEASE