A near optimal Viterbi algorithm based routing scheme for multi-hop relay networks

In this paper, a novel routing algorithm for relay selection (RS) in multi-hop relay networks is proposed based on Viterbi algorithm with truncated decoding memory. It maps the network topology to a trellis diagram of a convolutional code. In the trellis, the branch metric is the inverse of the instantaneous SNR of the corresponding channel. Consequently, the path metric, which is the accumulated branch metrics along the path, is equal to the inverse of the equivalent SNR of the path. Information on the most recent w (window size) hops of the network is stored and a relay is selected on the first hop within the window. Simulation results confirm that the proposed routing algorithm can achieve near optimal outage performance with a large enough truncation window size. The proposed routing algorithm has a polynomial complexity and low communication overhead. Therefore, it is very efficient for relay networks with a large number of hops.