A Near Optimal Routing Scheme for Multi-Hop Relay Networks Based on Viterbi Algorithm

In a wireless multi-hop relay network, the optimal routing scheme with exhaustive path search entails high computational complexity and large storage requirement, and is impractical for a large number of hops. In this paper, the authors propose a suboptimal path selection scheme, based on Amplify-and-Forward (AF) protocol, that has outage performance close to the optimal routing scheme, but with much less complexity. The proposed scheme draws on the analogy between the node distribution of a commonly used relay network model and the trellis of a convolutional code, and applies the Viterbi algorithm in selecting a path to maximize the end-to-end Signal-to-Noise Ratio (SNR).