Geosphere: consistently turning MIMO capacity into throughput

Abstract

This paper presents the design and implementation of Geosphere, a physical- and link-layer design for access point-based MIMO wireless networks that consistently improves network throughput. To send multiple streams of data in a MIMO system, prior designs rely on a technique called zero-forcing, a way of "nulling" the interference between data streams by mathematically inverting the wireless channel matrix. In general, zero-forcing is highly effective, significantly improving throughput. But in certain physical situations, the MIMO channel matrix can become "poorly conditioned," harming performance. With these situations in mind, Geosphere uses sphere decoding, a more computationally demanding technique that can achieve higher throughput in such channels. To overcome the sphere decoder's computational complexity when sending dense wireless constellations at a high rate, Geosphere introduces search and pruning techniques that incorporate novel geometric reasoning about the wireless constellation. These techniques reduce computational complexity of 256-QAM systems by almost one order of magnitude, bringing computational demands in line with current 16- and 64-QAM systems already realized in ASIC. Geosphere thus makes the sphere decoder practical for the first time in a 4 × 4 MIMO, 256-QAM system. Results from our WARP testbed show that Geosphere achieves throughput gains over multi-user MIMO of 2× in 4 × 4 systems and 47% in 2 × 2 MIMO systems.

References

1. Agilent Technologies. shape mimo Performance and Condition Number in LTE Test: App. Note, 2009.
2. E. Agrell, T. Eriksson, A. Vardy, and K. Zeger. Closest point search in lattices. riptsize IEEE Trans. Inf. Theory, 48(8):2201--2214, Aug. 2002.
3. H. Artés. Efficient detection algorithms for shape mimo channels. riptsize IEEE Tr. Sig. Proc., 51(11):2808--20, 2003.
4. L. Azzam and E. Ayanoglu. Reduced complexity sphere decoding via a reordered lattice representation. riptsize IEEE Tr. Comms., 57(9):2564--69, 2009.
5. L. Barbero and J. Thompson. Fixing the complexity of the sphere decoder for shape mimo detection. riptsize IEEE Trans. on Wireless Comms., 7(6):2131--2142, 2008.
6. M. Barrenechea et al. Implementation of complex enumeration for multiuser shape mimo vector precoding. In Proc. of Eur. Sig. Proc. Conf., 2011.
7. F. Borlenghi et al. A 772 Mbit/s 8.81 bit/nJ 90 nm shape cmos soft-input soft-output sphere decoder. In Proc. of riptsize IEEE Asian Solid State Circ. Conf., 2011.
8. F. Borlenghi et al. A 2.78 mm2 65 nm shape cmos gigabit shape mimo iterative detection and decoding receiver. In Proc. of the ESSCIRC, pages 65--68, 2012.
9. J. Boutros et al. Soft-input soft-output lattice sphere decoder for linear channels. In riptsize GLOBECOM, 2003.
10. A. Burg, M. Borgmann, M. Wenk, M. Zellweger, W. Fichtner, and H. Bolcskei. shape vlsi implementation of shape mimo detection using the sphere decoding algorithm. riptsize IEEE J. of Solid-State Circ., 40(7):1566--1577, 2005.
11. A. Chan and I. Lee. A new reduced-complexity sphere decoder for multiple antenna sys. In riptsize IEEE ICC, 2002.
12. C. Chen and L. Wang. On the performance of the zero-forcing receiver operating in the multiuser shape mimo system with reduced noise enhancement effect. In Proc. of riptsize IEEE Globecom, 2005.
13. S. Chen, T. Zhang, and Y. Xin. Relaxed shape k-best shape mimo signal detector design and shape vlsi implementation. riptsize IEEE Trans. on shape vlsi Sys., 15(3):328--337, 2007.
14. T. Cui, S. Han, and C. Tellambura. Probability distribution based node pruning for sphere decoding. riptsize IEEE Trans. on Veh. Tech., 62(4):1586--96, 2013.
15. T. Cui, T. Ho, and C. Tellambura. Statistical pruning for near maxiumum likelihood detection of shape mimo systems. In riptsize IEEE ICC, 2007.
16. T. Cui and C. Tellambura. An efficient generalized sphere decoder for rank-deficient shape mimo systems. riptsize IEEE Comms. L., 9(5):423--5, 2005.
17. M. Damen, H. El Gamal, and G. Caire. On maximum likelihood detection and the search for the closest lattice point. riptsize IEEE T. Inf. Th., 49(10):2389--402, 2003.
18. M. Damen et al. Generalized sphere decoder for asymmetrical space-time communication architecture. riptsize IEEE Elec. L., 36(2):166--67, 2000.
19. P. Dayal and M. Varanasi. A fast generalized sphere decoder for optimum decoding of under-determined shape mimo systems. In Proc. of Allerton Conf., 2003.
20. A. Ghasemmehdi and E. Agrell. Faster recursions in sphere decoding. riptsize IEEE T. Inf. Th., 57(6):3530--6, 2011.
21. S. Gollakota, S. Perli, and D. Katabi. Interference alignment and cancellation. In riptsize SIGCOMM, 2009.
22. R. Gowaikar and B. Hassibi. Statistical pruning for near-maximum likelihood decoding. riptsize IEEE Tr. on Sig. Proc., 55(6):2661--75, 2007.
23. A. Gudipati and S. Katti. Strider: Automatic rate adaptation and collision handling. In riptsize SIGCOMM, 2011.
24. Z. Guo and P. Nilsson. Algorithm and implementation of the shape k-best sphere decoding for shape mimo detection. riptsize IEEE J. Sel. Areas Commun., 24(3):491--503, 2006.
25. C. Hess et al. Reduced-complexity shape mimo detector with close-to-shape ml error rate performance. In riptsize ACM Great Lakes riptsize VLSI Symp., 2008.
26. B. Hochwald, T. Marzetta, and V. Tarokh. Multiple-antenna channel hardening and its implications for rate feedback and scheduling. riptsize IEEE Trans. on Info. Theory, 50(9), Sept. 2004.
27. B. Hochwald, C. Peel, and A. Swindlehurst. A vector-perturbation technique for near-capacity multiantenna multiuser communication. riptsize IEEE Trans. on Comms., 53(3):537--544, 2005.
28. B. Hochwald and S. Ten Brink. Achieving near-capacity on a multiple-antenna channel. riptsize IEEE Trans. Comms., 51(3):389--399, Mar. 2003.
29. B. Hochwald and S. Vishwanath. Space-time multiple access: Linear growth in the sum rate. In Proc. of Allerton Conf., 2002.
30. J. Jaldén, L. Barbero, B. Ottersten, and J. Thompson. The error probability of the fixed-complexity sphere decoder. riptsize IEEE Tr. on Sig. Proc., 57(7):2711--20, 2009.
31. P. Kafle et al. Spatial correlation and capacity measurements for wideband shape mimo channels in indoor office environment. riptsize IEEE Trans. on Wireless Comms., 7(5):1560--1571, 2008.
32. N. Kita et al. Measurement of Demel condition number for 2x2 shape mimo-shape ofdm channels. In riptsize IEEE VTC, 2004.
33. E. Kreyszig. Advanced Engineering Mathematics. Wiley & Sons, Inc., 2006.
34. Q. Li and Z. Wang. Improved shape k-best sphere decoding algorithms for shape mimo systems. In Proc. of riptsize IEEE Int. Symp. on Circuits and Sys., 2006.
35. K. Lin, S. Gollakota, and D. Katabi. Random access heterogeneous shape mimo networks. In riptsize SIGCOMM, 2011.
36. J. Maurer, G. Matz, and D. Seethaler. Low-complexity and full-diversity shape mimo detection based on condition number thresholding. In riptsize IEEE ICASSP, 2007.
37. B. Mennenga and G. Fettweis. Search sequence determination for tree search based detection algorithms. In riptsize IEEE Sarnoff Symp., 2009.
38. M. Mohaisen and K. Chang. Fixed-complexity sphere encoder for multi-user shape mimo systems. Journal of Communications and Networks, 13(1):63--69, 2011.
39. S. Mondal et al. Design and implementation of a sort-free shape k-best sphere decoder. riptsize IEEE Trans. on shape vlsi Sys., 18(10):1497--1501, 2010.
40. K. Nikitopoulos et al. Complexity-efficient enumeration techniques for soft-input, soft-output sphere decoding. riptsize IEEE Comms. L., 14(4):312--4, 2010.
41. C. Peel et al. A vector-perturbation technique for near-capacity multiantenna multiuser communication. riptsize IEEE Trans. on Comms., 53(1):195--202, 2005.
42. J. Perry, P. Iannucci, K. Fleming, H. Balakrishnan, and D. Shah. Spinal codes. In riptsize ACM SIGCOMM, 2012.
43. Rice Univ. Wireless Open Access Research Platform (shape warp). http://warp.rice.edu/trac.
44. S. Roger, A. Gonzalez, V. Almenar, and A. Vidal. Combined shape k-best sphere decoder based on the channel matrix condition number. In riptsize IEEE ISCCSP, 2008.
45. K. Sayana, S. Nagaraj, and S. Gelfand. A shape mimo zero-forcing receiver with soft interference cancellation for shape bicm. In Proc. of the riptsize IEEE Workshop on Sig. Proc. Advances in Wireless Comms., 2005.
46. C. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math. Prog., 66(2):181--191, 1994.
47. M. Shabany and P. Gulak. Scalable shape vlsi architecture for shape k-best lattice decoders. In riptsize IEEE ISCAS, 2008.
48. M. Shabany, K. Su, and P. Gulak. A pipelined scalable high-throughput implementation of a near-shape ml shape k-best complex lattice decoder. In riptsize IEEE ICASSP, 2008.
49. W. Shen et al. Rate adaptation for 802.11 multiuser shape mimo networks. In MobiCom, 2012.
50. B. Shim and I. Kang. Sphere decoding with a probabilistic tree pruning. riptsize IEEE Trans. on Signal Processing, 56(10):4867--4878, 2008.
51. B. Shim and I. Kang. On further reduction of complexity in tree pruning based sphere search. riptsize IEEE Trans. on Comms., 58(2):417--22, 2010.
52. M. Stojnic et al. Further results on speeding up the sphere decoder. In riptsize IEEE ICASSP, 2006.
53. G. Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press, 4$^\textth$ edition, 2009.
54. C. Studer and H. Bölcskei. Soft-input soft-output sphere decoding. In riptsize IEEE ISIT, 2008.
55. K. Su and I. Wassell. A new ordering for efficient sphere decoding. In riptsize IEEE ICC, 2005.
56. K. Tan et al. shape sam: Enabling practical spatial multiple access in wireless shape lan. In MobiCom, 2009.
57. H. Teague et al. Field results on shape mimo performance in shape umb systems. In riptsize IEEE VTC, 2008.
58. I. Telatar. Capacity of multi-antenna Gaussian channels. Eur. Trans. Telecomms., 10(6):585--596, Dec. 1999.
59. D. Tse and P. Viswanath. Fundamentals of Wireless Communication. Cambridge University Press, 2005.
60. H. Vikalo, B. Hassibi, and T. Kailath. Iterative decoding for shape mimo channels via modified sphere decoding. riptsize IEEE Trans. on Wireless Comms., 3(6):2299--2311, 2004.
61. J. Wang et al. User selection with zero-forcing beamforming achieves the asymptotically optimal sum rate. riptsize IEEE Tr. on Sig. Proc., 56(8):3713--26, 2008.
62. M. Wenk, L. Bruderer, A. Burg, and C. Studer. Area-and throughput-optimized shape vlsi architecture of sphere decoding. In riptsize EEE/IFIP VLSI-SOC, 2010.
63. M. Wenk et al. shape k-best shape mimo detection shape vlsi architectures achieving up to 424 Mbps. In riptsize ISCC, 2006.
64. M. Winter et al. A 335 Mb/s 3.9 mm$^2$ 65 nm shape cmos flexible shape mimo detection-decoding engine achieving 4G wireless data rates. In riptsize IEEE ISSCC, 2012.
65. E. Witte et al. A scalable shape vlsi architecture for shape siso single tree-search sphere decoding. riptsize IEEE Trans. on Circ. and Sys., 57(9):706--710, 2010.
66. K. Wong et al. A shape vlsi architecture of a shape k-best lattice decoding algorithm for shape mimo channels. In riptsize ISCC, 2002.
67. Q. Yang et al. BigStation: Enabling scalable real-time signal processing in large shape mu-mimo systems. In riptsize SIGCOMM, 2013.
68. T. Yoo and A. Goldsmith. On the optimality of multiantenna broadcast scheduling using zero-forcing beamforming. riptsize IEEE JSAC, 24(3):528--541, 2006.
69. A. Zanella, M. Chiani, and M. Win. shape mmse reception and successive interference cancellation for shape mimo systems with high spectral efficiency. riptsize IEEE Trans. on Wireless Comms., 4(3):1244--1253, 2005.
70. W. Zhao and G. Giannakis. Reduced complexity closest point decoding algorithms for random lattices. riptsize IEEE Trans. on Wireless Comms., 5(1):101--111, 2006.

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks