Optimal Secure Spectrum-Efficient Routing in Multihop Wireless Networks

This article addresses the problem of finding the source-to-destination path that maximizes the secrecy spectral efficiency in a multihop wireless network that contains a malicious eavesdropper node. Since the resulting routing metric is nonisotonic, the problem cannot be solved by standard shortest path algorithms. However, we provide a polynomial-time algorithm that provides guaranteed optimal solutions to the problem. Our algorithm hinges upon the divide-and-conquer principle from optimization theory and a modification to the Bellman–Ford routing algorithm. Moreover, we illustrate that the case of multiple colluding eavesdropper nodes can be solved to optimality using the same framework of a single eavesdropper but prove that the case of multiple noncolluding eavesdropper nodes is NP-complete to solve. For the latter, we show that a modified Dijkstra algorithm can produce approximate solutions that are guaranteed to have no cycles. Our numerical results further illustrate the efficiency of our proposed approach.