skip to main content
10.1145/1080810.1080814acmconferencesArticle/Chapter ViewAbstractPublication PagesdialmConference Proceedingsconference-collections
Article

On lower bounds for MAC layer contention in CSMA/CA-based wireless networks

Published: 02 September 2005 Publication History

Abstract

Wireless LANs operating within unlicensed frequency bands require random access schemes such as CSMA/CA, so that wireless networks from different administrative domains (for example wireless community networks) may co-exist without central coordination, even when they happen to operate on the same radio channel. Yet, it is evident that this lack of coordination leads to an inevitable loss in efficiency due to contention on the MAC layer. The interesting question is, which efficiency may be gained by adding coordination to existing, unrelated wireless networks, for example by self-organization. In this paper, we present a methodology based on a mathematical programming formulation to determine the parameters (assignment of stations to access points, signal strengths and channel assignment of both access points and stations) for a scenario of co-existing CSMA/CA-based wireless networks, such that the contention between these networks is minimized. We demonstrate how it is possible to solve this discrete, non-linear optimization problem exactly for small problems. For larger scenarios, we present a genetic algorithm specifically tuned for finding near-optimal solutions, and compare its results to theoretical lower bounds. Overall, we provide a benchmark on the minimum contention problem for coordination mechanisms in CSMA/CA-based wireless networks.

References

[1]
lp_solve. http://groups.yahoo.com/group/lp_solve/.
[2]
E. Amaldi, A. Capone, M. Cesana, and F. Malucelli. Optimizing WLAN Radio Coverage. In IEEE International Conference on Communications (ICC 2004), pages 180--184, Paris, France, June 2004.
[3]
F. Glover and R.E. Woolsey. Note on converting the 0-1 polynomial programming problems to zero-one linear programming problems. Operations Research, 22:180--181, 1974.
[4]
D.A. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.
[5]
J. K. Han, B. S. Park, Y. S. Choi, and H. K. Park. Genetic Approach with a New Representation for Base Station Placement in Mobile Communications. In 54th IEEE Vehicular Technology Conference (VTC 2001 Fall), pages 2703--2707, October 2001.
[6]
A. Hills and B. Friday. Radio Resource Management in Wireless LANs. IEEE Communications Magazine, 42(10):9--14, December 2004.
[7]
S. Hurley. Planning Effective Cellular Mobile Radio Networks. IEEE Transactions on Vehicular Technology, 51(2):243--253, March 2002.
[8]
M. Kamenetsky and M. Unbehaun. Coverage Planning for Outdoor Wireless LAN Systems. In 2002 International Zurich Seminar on Broadband Communications Access, Transmission, Networking, pages 491--496, March 2002.
[9]
P. Karn. MACA -- A New Channel Access Method for Packet Radio. In Proceedings of the ARRL 9th Computer Networking Conference, pages 134--140, London, Ontario Canada, September 1990.
[10]
I. Katzela and M. Naghshineh. Channel Assignment Schemes for Cellular Mobile Telecommunication Systems: A Comprehensive Survey. IEEE Personal Communications, 3(3):10--31, June 1996.
[11]
S. O. Krumke, M. V. Marathe, and S. S. Ravi. Models and Approximation Algorithms for Channel Assignment in Radio Networks. Wireless Networks, 7(6):575--583, November 2001.
[12]
C.Y. Lee and H.G. Kang. Cell planning with Capacity Expansion in Mobile Communications: A Tabu Search Approach. IEEE Transactions on Vehicular Technology, 49(5):1678--1691, March 2000.
[13]
Y. Lee, K. Kim, and Y. Choi. Optimization of AP Placement and Channel Assignment in Wireless LANs. In IEEE Conference on Local Computer Networks (LCN 2002), 2002.
[14]
R.A. Leese. A Unified Approach to the Assignment of Radio Channels on a Regular Hexagonal Grid. Transactions on Vehicular Technology, 46(4):968--980, November 1997.
[15]
K. K. Leung and B.-J. Kim. Frequency Assignment for IEEE 802.11 Wireless Networks. In 58th IEEE Vehicular Technology Conference (VTC 2003 Fall), pages 1422--1426. IEEE, October 2003.
[16]
X. Ling and K.L. Yeung. Joint Access Point Placement and Channel Assignment for 802.11 Wireless LANs. In IEEE Wireless Communications and Networking Conference (WCNC 2005), 2005.
[17]
Y. Matsunaga and R.H. Katz. Inter-Domain Radio Resource Management for Wireless LANs. In IEEE Wireless Communications and Networking Conference (WCNC 2004), pages 2183--2188, Atlanta, Georgia, USA, March 2004.
[18]
ITU-R P.1238-2. Propagation data and prediction methods for the planning of radio communication systems and radio local area networks in the frequency range of 900 MHz to 100 GHz, 2001.
[19]
P. Struhsake. WLAN Channel Bonding: Causing Greater Problems Than It Solves. White Paper SPLY003, Texas Instruments, September 2003.
[20]
Y. Wang, L. Cuthbert, and J. Bigham. Intelligent Radio Resource Management for IEEE 802.11 WLAN. In IEEE Wireless Communications and Networking Conference (WCNC 2004), pages 1365--1370, Atlanta, Gergia USA, March 2004.
[21]
IEEE 802.11 WG. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Standard, August 1999.

Cited By

View all
  • (2009)Minimizing contention through cooperation between densely deployed wireless LANsWireless Networks10.1007/s11276-007-0072-315:6(741-754)Online publication date: 1-Aug-2009
  • (2009)Mathematical Optimization Models for WLAN PlanningGraphs and Algorithms in Communication Networks10.1007/978-3-642-02250-0_11(283-309)Online publication date: 9-Nov-2009
  • (2007)Integrated Access Point Placement and Channel Assignment for Wireless LANs in an Indoor Office Environment2007 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks10.1109/WOWMOM.2007.4351711(1-10)Online publication date: Jun-2007
  • Show More Cited By

Index Terms

  1. On lower bounds for MAC layer contention in CSMA/CA-based wireless networks

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computing
      September 2005
      120 pages
      ISBN:1595930922
      DOI:10.1145/1080810
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 02 September 2005

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. CSMA/CA
      2. community networks
      3. contention
      4. lower bound
      5. wireless LANs

      Qualifiers

      • Article

      Conference

      Dial M - POMC 05
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 21 of 68 submissions, 31%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 20 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2009)Minimizing contention through cooperation between densely deployed wireless LANsWireless Networks10.1007/s11276-007-0072-315:6(741-754)Online publication date: 1-Aug-2009
      • (2009)Mathematical Optimization Models for WLAN PlanningGraphs and Algorithms in Communication Networks10.1007/978-3-642-02250-0_11(283-309)Online publication date: 9-Nov-2009
      • (2007)Integrated Access Point Placement and Channel Assignment for Wireless LANs in an Indoor Office Environment2007 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks10.1109/WOWMOM.2007.4351711(1-10)Online publication date: Jun-2007
      • (2006)On self-coordination in wireless community networksProceedings of the 11th IFIP TC6 international conference on Personal Wireless Communications10.1007/11872153_22(251-262)Online publication date: 20-Sep-2006
      • (2006)The case for virtualized wireless access networksProceedings of the First international conference, and Proceedings of the Third international conference on New Trends in Network Architectures and Services conference on Self-Organising Systems10.1007/11822035_9(90-104)Online publication date: 18-Sep-2006

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media