Superimposed code based channel assignment in multi-radio multi-channel wireless mesh networks

ABSTRACT

Motivated by the observation that channel assignment for multiradio multi-channel mesh networks should support both unicast and local broadcast¹, should be interference-aware, and should result in low overall switching delay, high throughput, and low overhead, we propose two flexible localized channel assignment algorithms based on s-disjunct superimposed codes. These algorithms support the local broadcast and unicast effectively, and achieve interference-free channel assignment under certain conditions. In addition, under the primary interference constraints², the channel assignment algorithm for unicast can achieve 100% throughput with a simple scheduling algorithm such as the maximal weight independent set scheduling, and can completely avoid hidden/exposed terminal problems under certain conditions. Our algorithms make no assumptions on the underlying network and therefore are applicable to a wide range of MR-MC mesh network settings. We conduct extensive theoretical performance analysis to verify our design.

REFERENCES

• 1: Pradeep Kyasanur , Nitin H. Vaidya, Capacity of multi-channel wireless networks: impact of number of channels and interfaces, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080835]
• 2: Gurashish Brar , Douglas M. Blough , Paolo Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161092]
• 3: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080836]
• 4: Murali Kodialam , Thyaga Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080837]
• 5: A. P. Subramanian, R. Krishnan, S. R. Das, and H. Gupta, "Minimum-interference channel assignment in multi-radio wireless mesh networks."
• 6: Ashish Raniwala , Kartik Gopalan , Tzi-cker Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.2, April 2004 [doi>10.1145/997122.997130]
• 7: A. Raniwala and T. Chiueh, "Architecture and algorithms for an ieee 802.11-based multi-channel wireless mesh network," in IEEE Infocom, 2005.
• 8: M. K. Marina and S. R. Das, "A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks," in 2nd International Conference on Broadband Networks, 2005, pp. 381-- 390.
• 9: Pradeep Kyasanur , Nitin H. Vaidya, Routing and link-layer protocols for multi-channel multi-interface ad hoc wireless networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.10 n.1, p.31-43, January 2006 [doi>10.1145/1119759.1119762]
• 10: B.-J. Ko, V. Misra, J. Padhye, and D. Rubenstein, "Distributed channel assignment in multi-radio 802.11 mesh networks," in Wireless Communications and Networking Conference (WCNC), 2007, pp. 3978--3983.
• 11: K. N. Ramachandran, E. M. Belding, K. C. Almeroth, and M. M. Buddhikot, "Interference-aware channel assignment in multi-radio wireless mesh networks," in Infocom, 2006.
• 12: H. Skalli, S. K. Das, L. Lenzini, and M. Conti, "Traffic and interference aware channel assignment for multi-radio wireless mesh networks," in Technical Report, 2006.
• 13: 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]
• 14: 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
• 15: P.Kyasanur and N.H.Vaidya, "Routing and interface assignment in multi-channel multi-interface wireless networks," in Wireless Communications and Networking Conference, 2005 IEEE, vol. 4, 2005, pp. 2051--2056.
• 16: Paramvir Bahl , Ranveer Chandra , John Dunagan, SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023742]
• 17: Alan A. Bertossi , Maurizio A. Bonuccelli, Code assignment for hidden terminal interference avoidance in multihop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.441-449, Aug. 1995 [doi>10.1109/90.413218]
• 18: J. Garcia-Luna-Aceves and J. Raju, "Distributed assignment of codes for multihop packet--radio networks," in Milcom '97: Proceedings of the 1997 Military Communications Conference. IEEE Computer Society, 1997, pp. 450--454.
• 19: W. H. Kautz and R. C. Singleton, "Nonrandom binary superimposed codes," in IEEE Trans. Inform. Theory, vol. IT-10, 1964, pp. 363--377.
• 20: D. Du and F. Hwang, "Combinatorial group testing and its applications," 2nd Edition, World Scientific, 2000.
• 21: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.709-718, January 07-09, 2001, Washington, D.C., United States
• 22: D. Stinson, T. van Trung, and R. Wei, "Secure frameproof codes, key distribution patterns, group testing algorithms and related structures," in Journal of Stat. Planning and Inference, vol. 86, no. 2, 2000, pp. 595--617.
• 23: Piotr Indyk, Deterministic Superimposed Coding with Applications to Pattern Matching, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.127, October 19-22, 1997
• 24: Shiva Chaudhuri , Jaikumar Radhakrishnan, Deterministic restrictions in circuit complexity, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.30-36, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237824]
• 25: Annalisa De Bonis , Ugo Vaccaro, Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels, Theoretical Computer Science, v.306 n.1-3, p.223-243, 5 September 2003 [doi>10.1016/S0304-3975(03)00281-0]
• 26: A. D'yachkov, V. Lebedev, P. Vilenkin, and S. Yekhanin, "Cover-free families and superimposed codes: Constructions, bounds, and applications to cryptography and group testing," in IEEE International Symposium on Information Theory, 2001.
• 27: Danyo Danev, Some constructions of superimposed codes in Euclidean spaces, Discrete Applied Mathematics, v.128 n.1, p.85-101, 15 May 2003 [doi>10.1016/S0166-218X(02)00438-9]
• 28: A. D. yachkov, A. M. Jr, and V.V.Rykov, "New constructions of superimposed codes," in Information Theory, IEEE Transactions on, vol. 46, no. 1, 2000, pp. 284--290.
• 29: D. Charles Engelhart , Anand Sivasubramaniam, Almost Disjunct Codes in Large Scale Multihop Wireless Network Media Access Control, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.453-463, September 27-29, 2005 [doi>10.1109/MASCOT.2005.13]
• 30: Anthony J. Macula, A simple construction of d-disjunct matrices with certain constant weights, Discrete Mathematics, v.162 n.1-3, p.311-312, Dec. 25, 1996 [doi>10.1016/0012-365X(95)00296-9]
• 31: A. G. D'yachkov and V. V. Rykov, "Optimal superimposed codes and designs for renyi's search model," Journal of Statistical Planning and Inference, vol. 100, no. 2, pp. 281--302, 2002.
• 32: Andrew Brzezinski , Gil Zussman , Eytan Modiano, Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161094]
• 33: A. Dimakis and J. Walrand, "Sufficient conditions for stability of longest queue first scheduling: Second order properties using fluid limits," Advances of Applied Probability, vol. 38, no. 2, pp. 505--521, 2006.
• 34: "Wimax/802.16 revealed." {Online}. Available: http://www.wi-fiplanet.com/tutorials/article.php/3550476
• 35: "What is ieee 802.16e." {Online}. Available: http://www.wimax.com/education/faq/faq45
• 36: A. J. Macula, V. V. Rykov, and S. Yekhanin, "Trivial two-stage group testing for complexes using almost disjunct matrices," Discrete and Applied Mathematics, vol. 137, pp. 97--107, 2004.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
channel assignment, interference, multi-radio multi-channel wireless mesh networks, superimposed codes