article

Joint bandwidth allocation, element assignment and scheduling for wireless mesh networks with MIMO links

Authors:

Liusheng Huang,

Huan LiAuthors Info & Claims

Computer Communications, Volume 31, Issue 7

Pages 1372 - 1384

https://doi.org/10.1016/j.comcom.2008.01.053

Published: 01 May 2008 Publication History

Abstract

With the unique features of spatial multiplexing and interference suppression, Multiple Input Multiple Output (MIMO) techniques have great potential in the improvement of network capacity over conventional antenna technologies. In order to exploit the benefit of simultaneous transmissions provided by MIMO, researchers have proposed a number of cross-layer optimizations and MAC layer designs to increase the throughput of wireless mesh or ad hoc networks, where the number of elements in the antenna arrays are pre-allocated or evenly assigned to the routers. In this paper, we argue that using the same number of elements in each antenna array in all routers is not a necessary condition for the improvement of system performance. This is because the requirement for the number of elements is quite different for each router. Especially at those critical routers that have huge aggregate traffic toward the gateway, more elements are needed not only for the traffic relay but also for the interference suppression. Based on this observation, we define the joint problem of bandwidth allocation, element assignment and scheduling to characterize the throughput benefits of cross-layer optimizations. We propose a Cost-Aware Element Assignment (CAEA) technique to minimize the total number of the antenna elements when still achieving the optimal bandwidth allocation. In addition, to verify the efficiency of the CAEA assignment, a heuristic Traffic-aware Stream-controlled Link Scheduling (TSLS) algorithm is proposed to provide a schedulable bandwidth allocation. We demonstrate through extensive simulations that our solutions (CAEA, TSLS) not only effectively save the total cost on antenna elements but also perform close to optimal on the average.

References

[1]

Akyildiz, I. and Wang, X., A survey on wireless mesh networks. IEEE Communications Magazine. v43. 23-30.

Digital Library

[2]

Gupta, P. and Kumar, P.R., The capacity of wireless networks. IEEE Transactions on Information Theory. v46 i2. 388-404.

Digital Library

[3]

Gesbert, D., Shafi, M., Shiu, D., Smith, P.J. and Naguib, A., From theory to practice: an overview of MIMO space-time coded wireless systems. IEEE Journal of Selected Areas in Communications. v21. 281-302.

Digital Library

[4]

A.J. Paulraj, D.A. Gore, R.U. Nabar, H. Bolcskei, An overview of MIMO communications - a key to gigabit wireless, in: Proceedings of IEEE, vol. 92, February 2004, pp. 198-218.

[5]

Shiu, D., Foschini, G.J., Gans, M.J. and Kahn, J.M., Fading correlation and its effect on the capacity of multiple-element antennas. IEEE Transactions on Communications. v48.

[6]

E. Baccarelli, M. Biagi, C. Pelizzoni, N. Cordeschi, F. Garzia, Interference suppression in MIMO systems for throughput enhancement and error reduction, in: Proceedings of ACM IWCMC, July 2006, pp. 611-616.

Digital Library

[7]

Zheng, L. and Tse, D.N.C., Diversity and multiplexing: a fundamental tradeoff in multiple-antenna channels. IEEE Transactions on Information Theory. v49. 1073-1096.

Digital Library

[8]

K. Sundaresan, R. Sivakumar, M.A. Ingram, T.Y. Chang, A fair medium access control protocol for ad-hoc networks with MIMO links, in: Proceedings of IEEE INFOCOM, vol. 4, 2004, pp. 2559-2570.

[9]

M.F. Demirkol, M.A. Ingram, Control using capacity constraints for interfering MIMO links, in: Proceedings of IEEE PIMRC, vol. 3, September 2002, pp. 1032-1036.

[10]

Anderson, J.B., Antenna arrays in mobile communications: gain, diversity, and channel capacity. IEEE Antennas and Propagation Magazine. v42. 12-16.

[11]

S. Gaur, J.S. Jiang, M.A. Ingram, M.F. Demirkol, Interfering MIMO links with stream control and optimal antenna selection, in: Proceedings of IEEE GLOBECOM, vol. 5, 2004, pp. 3138-3142.

[12]

J. Tang, G. Xue, W. Zhang, Maximum throughput and fair bandwidth allocation in multi-channel wireless mesh networks, in: Proceedings of IEEE INFOCOM, 2006, pp. 1-10.

[13]

T. Nandagopal, T.E. Kim, X. Gao, V. Bhargavan, Achieving MAC layer fairness in wireless packet networks, in: Proceedings of ACM MOBICOM, 2000.

Digital Library

[14]

Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D., Linear programming and network flows. 2005. third ed. John Wiley & Sons.

Digital Library

[15]

Khachiyan, L.G., A polynomial algorithm for linear programming. Doklady Akademiia Nauk SSSR. v244. 1093-1096.

[16]

Lingo software. Available from: <http://www.lindo.com/>.

[17]

K. Jain, J. Padhye, V.N. Padmanabhan, L. Qiu, Impact of interference on multi-hop wireless network performance, in: Proceedings of ACM MOBICOM, 2003, pp. 66-80.

Digital Library

[18]

P. Kyasanur, N.H. Vaidya, Capacity of multi-channel wireless networks: impact of number of channels and interfaces, in: Proceedings of ACM MOBICOM, 2005, pp. 43-57.

Digital Library

[19]

Kodialam, M. and Nandagopal, T., Characterizing achievable rates in multi-hop wireless mesh networks with orthogonal channels. IEEE/ACM Transactions on Networking. v13. 868-880.

Digital Library

[20]

Goldsmith, A., Jafar, S.A., Jindal, N. and Vishwanath, S., Capacity limits of MIMO channels. IEEE Journal of Selected Areas in Communications. v21. 684-702.

Digital Library

[21]

J.S. Jiang, M.F. Demirkol, M.A. Ingram, Measured capacities at 5.8GHz of indoor MIMO systems with MIMO interference, in: Proceedings of IEEE VTC-Fall, vol. 3, October 2003, pp. 1573-1577.

[22]

Raniwala, A., Gopalan, K. and Chiueh, T., Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks. ACM Mobile Computing and Communications Review. v8. 50-65.

Digital Library

[23]

M. Alicherry, R. Bhatia, L.E. Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, in: Proceedings of ACM MOBICOM, 2005, pp. 58-72.

Digital Library

[24]

A.H.M. Rad, V.W.S. Wong, Joint channel allocation, interface assignment and MAC design for multi-channel wireless mesh networks, in: Proceedings of IEEE INFOCOM, 2007, pp. 1469-1477.

Digital Library

[25]

Zorzi, M., Zeidler, J., Anderson, A.L., Rao, B.D., Proakis, J., Swindlehurst, A.L., Jensen, M.A. and Krishnamurthy, S.V., Cross-layer issues in MAC protocol design for MIMO ad hoc networks. IEEE Wireless Communications. 62-76.

Digital Library

[26]

T. Tang, M. Park, R.W. Heath Jr., S.M. Nettles, A joint MIMO-OFDM transceiver and MAC design for mobile ad hoc networking, in: Proceedings of IEEE IWWAN, June 2004, pp. 315-319.

[27]

M. Park, S.H. Choi, S.M. Nettles, Cross-layer MAC design for wireless networks using MIMO, in: Proceedings of IEEE GLOBECOM, vol. 5, 2005, pp. 2870-2874.

[28]

Wang, D. and Tureli, U., Joint MIMO-OFDM and MAC design for broadband multihop ad hoc networks. EURASIP Journal on Wireless Communications and Networking. 1-9.

Digital Library

[29]

Wong, K.K., Murch, R. and Letaief, K., Performance enhancement of multiuser MIMO wireless communication systems. IEEE Transactions on Communications. v50. 1960-1970.

[30]

R. Bhatia, L.E. Li, Throughput optimization of wireless mesh networks with MIMO links, in: Proceedings of IEEE INFOCOM, May 2007, pp. 2326-2330.

Digital Library

[31]

J. Liu, T.Y. Park, Y.T. Hou, Y. Shi, H.D. Sherali, Cross-layer optimization of MIMO-based mesh networks under orthogonal channels, in: Proceedings of IEEE WCNC, 2007, pp. 49-54.

[32]

K. Sundaresan, R. Sivakumar, Routing in ad-hoc networks with MIMO links, in: Proceedings of IEEE ICNP, 2005.

Digital Library

[33]

Han, B., Jia, W. and Lin, L., Performance evaluation of scheduling in IEEE 802.16 based wireless mesh networks. Elsevier Computer Communications. v30. 782-792.

Digital Library

[34]

Aniba, G. and Aissa, S., Adaptive scheduling for MIMO wireless networks: cross-layer approach and application to HSDPA. IEEE Transactions on Wireless Communications. v6. 259-268.

Digital Library

[35]

Anton-Haro, C., Svedman, P., Bengtsson, M., Alexiou, A. and Gameiro, A., Cross-layer scheduling for multi-user MIMO systems. IEEE Communications Magazine. 39-45.

Digital Library

[36]

G. Sharma, R.M. Ravi, B.S. Ness, On the complexity of scheduling in wireless networks, in: Proceedings of ACM MOBICOM, 2006, pp. 227-238.

Digital Library

[37]

G. Brar, D.M. Blough, P. Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, in: Proceedings of ACM MOBICOM, 2006, pp. 2-13.

Digital Library

[38]

W. Wang, X.Y. Li, O. Frieder, Y. Wang, W.Z. Song, Efficient interference-aware TDMA link scheduling for static wireless networks, in: Proceedings of ACM MOBICOM, 2006, pp. 262-273.

Digital Library

Cited By

Vieira Fde Rezende JBarbosa V(2016)Scheduling wireless links by vertex multicoloring in the physical interference modelComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.02.00899:C(125-133)Online publication date: 22-Apr-2016
https://dl.acm.org/doi/10.1016/j.comnet.2016.02.008
Blough DSanti PSrinivasan R(2014)On the feasibility of unilateral interference cancellation in MIMO networksIEEE/ACM Transactions on Networking10.1109/TNET.2013.228682922:6(1831-1844)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1109/TNET.2013.2286829
Vieira FDe Rezende JBarbosa VFdida S(2013)Local heuristic for the refinement of multi-path routing in wireless mesh networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2012.09.00957:1(273-285)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.comnet.2012.09.009
Show More Cited By

Index Terms

Joint bandwidth allocation, element assignment and scheduling for wireless mesh networks with MIMO links

Recommendations

Slot allocation algorithms in centralized scheduling scheme for IEEE 802.16 based wireless mesh networks

In IEEE 802.16 based wireless mesh networks (WMNs), TDMA (Time Division Multiple Access) is employed as the channel access method and only TDD (Time Division Duplex) is supported and there are no clearly separate downlink and uplink subframes in the ...
Joint multi-radio multi-channel assignment, scheduling, and routing in wireless mesh networks

The IEEE 802.11 DCF and EDCA mechanisms based on CSMA/CA are the most widely used random channel access mechanisms in wireless mesh networks (WMNs), but unfortunately these cannot effectively eliminate hidden terminal and exposed terminal problems in ...
A distributed channel assignment protocol for rate separation in wireless mesh networks

Wireless Mesh Networks (WMNs) support the cost-effective broadband access for Internet users. Although today's IEEE 802.11 PHY and MAC specifications provide multi-channel and multi-rate capabilities, exploiting available channels and data rates is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer Communications

Computer Communications Volume 31, Issue 7

May, 2008

217 pages

ISSN:0140-3664

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2008.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 May 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Vieira Fde Rezende JBarbosa V(2016)Scheduling wireless links by vertex multicoloring in the physical interference modelComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.02.00899:C(125-133)Online publication date: 22-Apr-2016
https://dl.acm.org/doi/10.1016/j.comnet.2016.02.008
Blough DSanti PSrinivasan R(2014)On the feasibility of unilateral interference cancellation in MIMO networksIEEE/ACM Transactions on Networking10.1109/TNET.2013.228682922:6(1831-1844)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1109/TNET.2013.2286829
Vieira FDe Rezende JBarbosa VFdida S(2013)Local heuristic for the refinement of multi-path routing in wireless mesh networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2012.09.00957:1(273-285)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.comnet.2012.09.009
Bansal MTrivedi A(2013)Cross-Layer Optimization of Multichannel Multiantenna WMNsWireless Personal Communications: An International Journal10.1007/s11277-012-0884-z71:2(1443-1459)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1007/s11277-012-0884-z
Vieira Fde Rezende JBarbosa VFdida S(2012)Scheduling links for heavy traffic on interfering routes in wireless mesh networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.5555/2160997.216117456:5(1584-1598)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.5555/2160997.2161174
Yazdanpanah MAssi CShayan Y(2011)Cross-layer optimization for wireless mesh networks with smart antennasComputer Communications10.1016/j.comcom.2011.06.00534:16(1894-1911)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1016/j.comcom.2011.06.005

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents