A knapsack problem formulation for relay selection in secure cooperative wireless communication

Cooperative jamming (CJ) schemes support secure wireless communication in the presence of one or more eavesdroppers. Larger numbers of cooperative relays provide better secrecy rate, while increasing the communication and synchronization needs associated with cooperative beamforming. For low density networks (small number of relays) the secrecy rate changes rapidly with an increase in the number of relays, while for higher density networks increasing the number of relays has significantly smaller effect on the secrecy rate. This research considers a resource-aware approach: instead of using all available relays, choose the smallest set of active relays that meet a predetermined performance goal. The problem is formulated as a knapsack problem that may be solved through an exhaustive search. As this search method has exponential complexity, three heuristic algorithms are proposed, offering significant complexity reduction. The first one relies on the individual relay secrecy rate with a greedy algorithm. The second one is based on the beamforming weights norms, and the third one successively selects relay nodes that minimize the performance gap between the temporal secrecy rate and the given secrecy rate goal. Simulation results demonstrate that relatively high secrecy rate may be achieved with a small number of active relays. The first method performs better for low secrecy rate threshold levels, while the second does so at high threshold. The third method combines the advantages of the previous two and offers performance very close to the optimum at the expense of higher complexity than the first two.