A quadratic programming relaxation approach to compute-and-forward network coding design

In wireless networks, the compute-and-forward strategy is a promising physical layer network coding scheme that can achieve high rates by effectively exploiting the interference between users. However, the design of the optimal integer-valued equation coefficient vectors in a compute-and-forward scheme turns out to be a shortest vector problem, which is known to be NP hard. In this work, we consider the problem of designing the equation coefficient vector for each relay with the objective being maximizing the computation rate at that relay. By taking advantage of some useful properties, we show that the problem can be relaxed to a series of equality-constrained quadratic programmings and their closed-form solutions are derived by use of the Lagrange multiplier method, which is the key to the efficiency of our method. A quantization algorithm is then proposed to transform the real-valued approximations to the set of required integer-valued vectors, from which a suboptimal equation coefficient vector is obtained. Numerical results demonstrate that relative to existing methods, our method can offer comparable performance at an impressively low complexity.