[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

A polynomial time algorithm for a variant of shortest vector problem with applications in compute-and-forward design

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

In wireless communication networks, one of the most significant problems in Compute-and-Forward (CPF) strategy based on Integer-Forcing (IF) technique is to search the optimal integer coefficient vector for a relay to decode the received messages. While this is a variant of shortest vector problem (SVP), which is prohibitively complex in its general form. In this paper, we mainly focus on the optimal integer solution with non-zero entries in multi-source one-relay model. For comparison we extend the number (or dimension) of communication nodes from 2 to any larger integer n based on an existing 2-dimensional search algorithm with non-zero entries. Then we add this non-zero-entries constraint to an existing search algorithm and make some improvements to search the optimal integer vector by solving an optimization problem over only one variable instead of searching all vector components, which has a much lower time complexity. We prove that our new search algorithm is more efficient with polynomial complexity compared with the extended n-dimensional algorithm, meanwhile the same optimal integer solution is guaranteed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Nazer, B., Gastpar, M.: Compute-and-forward: Harnessing interfer-ence through structured codes. IEEE Trans. Inf. Theory. 57, 6463–6486 (2011)

    Article  Google Scholar 

  2. Nazer, B., Gastpar, M.: Reliable physical layer network coding. Proc. IEEE. 99, 438–460 (2011)

    Article  Google Scholar 

  3. Zamir, R.: Lattices are everywhere. In: Proceedings of the 4th Annual Workshop on Information Theory and its Applications, pp. 392–421 (2009)

  4. Wen, J., Chang, X.W.: Success probability of the Babai estimators for box-constrained integer linear models. IEEE Trans. Inf. Theory. 63, 631–648 (2017)

  5. Erez, U., Zamir, R.: Achieving (1/2)log(1+SNR) on the AWGN channel with lattice encoding and decoding. IEEE Trans. Inf. Theory. 50, 2293–2314 (2004)

    Article  Google Scholar 

  6. Ahlswede, R., Cai, N., Li, S.Y., Yeung, R.W.: Network information flow. IEEE Trans. Inf. Theory. 46, 1204–1216 (2000)

    Article  MathSciNet  Google Scholar 

  7. Koetter, R., Mdard, M.: Beyond routing: an algebraic approach to network coding. IEEE/ACM Trans. Netw. 11, 782–795 (2003)

    Article  Google Scholar 

  8. Wieselthier, J.E., Nguyen, G.D., Ephremides, A.: Energy-efficient multicasting of session traffic in bandwidth- and transceiver-limited wireless networks. Clust. Comput. 5, 179–192 (2002)

    Article  Google Scholar 

  9. Wen, J., Li, D., Zhu, F.: Stable Recovery of Sparse Signals via lp-Minimization. Appl. Comput. Harmon. Anal. 38, 161–176 (2015)

  10. Zhan, J., Nazer, B., Erez, U., Gastpar, M.: Integer-forcing linear receivers. IEEE Trans. Inf. Theory. 60, 7661–7685 (2014)

    Article  MathSciNet  Google Scholar 

  11. Zhan, J., Nazer, B., Erez, U., Gastpar, M.: Integer-forcing linear receivers: a new low-complexity MIMO architecture. In: IEEE Vehicular Technology Conference Fall (VTC 2010-Fall), pp. 1–5 (2010)

  12. Dadush, D., Peikert, C., Vempala, S.: Enumerative lattice algorithms in any norm via m-ellipsoid coverings. In: IEEE 52nd Annual Symposium on FOCS, pp. 580–589 (2011)

  13. Dadush, D., Micciancio, D.: Algorithms for the densest sub-lattice problem. SODA. SIAM. 1103-1122 (2013)

  14. Alekhnovich, M., Khot, S.A., Kindler, G., Vishnoi, N.K.: Hardness of approximating the closest vector problem with preprocessing. In: 46th Annual IEEE Symposium on FOCS, pp 216–225 (2005)

  15. Pappi, K.N., Diamantoulakis, P.D., Otrok, H., Karagiannidis, G.K.: Cloud compute-and-forward with relay cooperation. IEEE Trans. Wireless Commun. 14, 3415–3428 (2015)

  16. Wei, L., Chen, W.: Compute-and-forward network coding design over multi-source multi-relay channels. IEEE Trans. Wireless Commun. 11, 3348–3357 (2012)

    Article  Google Scholar 

  17. Chen, Z., Fan, P.Y., Letaief, K.B.: Compute-and-forward: optimization over multisourcecmultirelay networks. IEEE Trans. Veh. Technol. 64, 1806–1818 (2015)

    Article  Google Scholar 

  18. Wei, L., Chen, W.: Efficient compute-and-forward network codes search for two-way relay channel. IEEE Commun. Lett. 16, 1204–1207 (2012)

    Article  Google Scholar 

  19. Shukla, S., Muralidharan, V.T., Rajan, B.: Wireless network-coded accumulate-compute and forward two-way relaying. IEEE Trans. Veh. Technol. 65, 1367–1381 (2016)

    Article  Google Scholar 

  20. Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44, 463–471 (1985)

    Article  MathSciNet  Google Scholar 

  21. Sahraei, S., Gastpar, M.: Compute-and-forward: finding the best equation. In: 52nd Annual Allerton Conference on Communication, Control, and Computing, pp. 227–233 (2014)

Download references

Acknowledgements

This work was supported by the National Natural Science Foundation of China (61472024, U1433203), Development Program for Distinguished Young Teachers in Higher Education of Guangdong Province (Grant No. Yq2013147).

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, Beihang University, Beijing, China

    Chao Tong & Jun Li

  2. Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB, Canada

    Jinming Wen

Authors
  1. Chao Tong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jun Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jinming Wen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jinming Wen.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tong, C., Li, J. & Wen, J. A polynomial time algorithm for a variant of shortest vector problem with applications in compute-and-forward design. Cluster Comput 22 (Suppl 5), 10415–10424 (2019). https://doi.org/10.1007/s10586-017-1032-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-017-1032-z

Keywords

Search

Navigation