Access control in heterogeneous multichannel wireless networks

ABSTRACT

We propose a multichannel wireless network architecture that supports nodes with differing multichannel capabilities. Both contention and contention-free medium access control (MAC) protocols are proposed for this heterogeneous multichannel network. In the contention MAC protocol, a new LRN control packet is defined that allows a pair of nodes to re-negotiate channel selection. This relaxes the assumption that nodes can sense the carrier on all supported channels in a short period of time. We model the scheduling problem for our contention-free MAC protocol as a weighted bipartite matching problem that minimizes the sum of the completion times with polynomial time complexity. We close with an illustration showing how the weighted bipartite matching generates a transmission schedule.

REFERENCES

• 1: "Software defined radio forum," http://www.sdrforum.org.
• 2: W. H. W. Tuttlebee, "Software-defined radio: Facets of a developing technology," IEEE Personal Communications, vol. 6, no. 2, pp. 38--44, April 1999.
• 3: W. H. W. Tuttlebee, "Advances in software-defined radio," IEE Electronic Systems and Software, vol. 1, no. 1, pp. 26--31, February 2003.
• 4: "DARPA's XG program," http://www.darpa.mil/ato/programs/xg/.
• 5: M. A. Marsan and D. Roffinella, "Multichannel local area network protocols," IEEE Journal on Selected Areas of Communications, vol. 1, no. 5, pp. 885--897, November 1983.
• 6: A. Nasipuri and S. Das, "Chapter 6: Multichannel MAC Protocols for Mobile Ad Hoc Networks," in Handbook of Algorithms for Wireless Networking and Mobile Computing, A. Boukerche, Ed. Chapman & Hall/CRC, 2006, pp. 99--122.
• 7: Jungmin So , Nitin H. Vaidya, Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989487]
• 8: A. Rangnekar, C. Wang, K. Sivalingam, and B. Li, "Chapter 5: Multiple Access Protocols and Scheduling Algorithms for Multiple Channel Wireless Networks," in Handbook of Algorithms for Wireless Networking and Mobile Computing, A. Boukerche, Ed. Chapman & Hall/CRC, 2006, pp. 77--98.
• 9: N. Choi, Y. Seok, and Y. Choi, "Multi-channel MAC protocol for mobile ad hoc networks," in Proceedings of IEEE Vehicular Technology Conference, October 2003, pp. 1379--1382.
• 10: A. Nasipuri and S. Das, "A multichannel CSMA MAC protocol for multihop wireless networks," in Proceedings of IEEE WCNC, September 1999, pp. 1402--1406, new Orleans, LA.
• 11: N. Jain, A. Nasipuri, and S. Das, "A multichannel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks," in Proceedings of IEEE International Conference on Computer Communication and Networks, October 2001, pp. 432--439, phoenix, AZ.
• 12: S.-L. Wu , C.-Y Lin , Y.-C. Tseng , J.-P. Sheu, A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks, Proceedings of the 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), p.232, December 07-07, 2000
• 13: R. Garces and J. Garcia-Luna-Aceves, "Collision avoidance and resolution multiple access for multichannel wireless networks," in Proceedings of IEEE INFOCOM, 2000, pp. 595--602.
• 14: M. McGarry, M. Maier, and M. Reisslein, "Ethernet PONs: A survey of dynamic bandwidth allocation (DBA) algorithms," IEEE Communications Magazine, vol. 42, no. 8, pp. S8--S15, August 2004.
• 15: S. Damodaran and K. Sivalingam, "Scheduling algorithms for multiple channel wireless local area networks," Computer Communications, vol. 25, no. 14, pp. 1305--1314, 2002.
• 16: M. Pinedo, Scheduling: Theory, Algorithms, and Systems, 2nd ed. Prentice Hall, 2002.
• 17: Zhi-Long Chen , Warren B. Powell, Solving Parallel Machine Scheduling Problems by Column Generation, INFORMS Journal on Computing, v.11 n.1, p.78-94, January 1999 [doi>10.1287/ijoc.11.1.78]
• 18: J. M. Van Den Akker , J. A. Hoogeveen , S. L. Van De Velde, Parallel Machine Scheduling by Column Generation, Operations Research, v.47 n.6, p.862-872, June 1999 [doi>10.1287/opre.47.6.862]
• 19: Ernest Davis , Jeffrey M. Jaffe, Algorithms for Scheduling Tasks on Unrelated Processors, Journal of the ACM (JACM), v.28 n.4, p.721-736, Oct. 1981 [doi>10.1145/322276.322284]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.3 Network Operations
          Subjects: Network management

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Management