Examination Committee

Prof Xuhui HUANG, CHEM/HKUST (Chairperson)
Prof Wai Ho MOW, ECE/HKUST (Thesis Supervisor)
Prof Tat Ming LOK, Department of Information Engineering, The Chinese University of Hong Kong (External Examiner)
Prof Jun ZHANG, ECE/HKUST
Prof James SHE, ECE/HKUST
Prof Gary S H CHAN, CSE/HKUST

Abstract

Being a type of physical layer network coding, the compute-and-forward (CF) relaying strategy offers higher transmission rate than the traditional relaying strategies. 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 (SVPs). The classical SVP in its general form is very likely NP-hard and its intractability forms the foundation of lattice-based cryptography. In practical scenarios, solving the SVP, i.e., searching the best NC coefficient vector that provides the highest computation rate at a single relay, is essential to the CF 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.

Three methods are proposed: a low-complexity method based on quadratic programming relaxation that gives a suboptimal solution, an efficient method based on the sphere decoding idea and the Schnorr-Euchner search that gives the optimal solution, and a low-complexity method inspired by the Sahraei-Gastpar method 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 two 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 along with the proposed strategy.