Compute-and-forward network coding design for wireless relay networks

Abstract

Over the past several decades, wireless communications have rapidly expanded, and now are applied in many aspects of human life. Along with this trend is the growing demand for higher transmission throughput in the wireless communication scenario. To satisfy this increasing demand, the concept of cooperative communication has emerged, where users, i.e., nodes in a wireless network, help each other by relaying each other's messages to accomplish the transmission to the destination. The intermediate nodes in a transmission perform as relays, and different relaying strategies have been proposed with the goal being mitigating the interference and improving the throughput. Being a type of physical layer network coding, the compute-and-forward (CF) relaying strategy offers higher transmission rate than the traditional relaying strategies like amplify-and-forward, compress-and-forward, and decode-and-forward. The achievable transmission rate of a wireless relay network adopting the CF scheme depends on the network coding (NC) coefficient vectors. However, searching for optimal NC coefficient vectors turns out to be a combination of multiple shortest vector problems (SVP) in a lattice. The classical SVP in its general form is very likely NP-hard and its intractability forms the foundation of lattice-based cryptography. When there is no feedback from the destination, it is reasonable that each relay chooses the NC coefficient vector that maximizes its computation rate. For the case where feedback from the destination is available, based on certain low overhead feedback protocol, the CF design problem can be converted to the problem of finding a list of short NC coefficient vectors that provide the best computation rate at a single relay. Therefore, solving the SVP involved is essential to the CF protocol design and the problem has attracted much research attention. In this thesis, we mainly focus on developing efficient and effective algorithms for solving the SVP in CF, i.e., searching the best NC coefficient vector that provides the highest computation rate at a single relay. Three methods are proposed: 1. a low-complexity method based on quadratic programming relaxation that gives a sub-optimal solution, 2. an efficient method based on the sphere decoding idea and the Schnorr-Euchner search that gives the optimal solution, and 3. a low-complexity method based on line quantization search that also gives the optimal solution. We investigate the efficiency and effectiveness of the proposed methods with both theoretical analysis and numerical simulations. Besides developing algorithms for solving the SVP in CF, we also consider the applications of the developed algorithms in CF design. We first investigate different relay cooperation strategies in choosing the NC coefficient vectors, which perform differently in terms of the system transmission rate and the communication overhead. Then we propose a new low communication overhead strategy and compare it with the two existing strategies. The previously developed algorithms, with slight modifications, can be applied at the relays to find a set of best NC coefficient vectors.

Date of Award	2016
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology