Optimal monitoring in multi-channel multi-radio wireless mesh networks

ABSTRACT

Wireless mesh networks (WMN) are finding increasing usage in city-wide deployments for providing network connectivity. Mesh routers in WMNs typically use multiple wireless channels to enhance the spatial-reuse of frequency bands, often with multiple radios per node. Due to the cooperative nature of WMNs, they are susceptible to many attacks that cannot be defeated by using traditional cryptographic mechanisms of authentication or encryption alone. A solution approach commonly used for defending against such attacks is behavior-based detection in which some nodes overhear communication in their neighborhood to determine if the behavior by a neighbor is legitimate. It has been proposed to use specialized monitoring nodes deployed strategically throughout the network for performing such detection. The problem that arises is where to deploy these monitoring nodes, how to minimize their number, and which channels to tune their radios to, such that the maximum part of the network can be covered. This problem has been solved for single channel networks by a greedy approximation algorithm since the exact solution is NP-hard. The greedy algorithm achieves the best performance, in terms of the worst case, possible among all polynomial-time algorithms provided that P!=NP. In this paper, we solve the problem for multi-channel multi-radio WMNs. The intuitive extension of the greedy algorithm destroys the property of best performance. Instead, we formulate the problem as an integer linear program, solve its linear program relaxation, and then use two rounding techniques that we develop by adapting existing rounding schemes. We thereby present two approximation algorithms. The first, computationally-light algorithm, called probabilistic rounding algorithm gives an expected best performance in the worst case. The second, called deterministic rounding algorithm achieves the best worst-case performance in a deterministic manner. To evaluate how the three algorithms perform in practice, we simulate them in random networks and scale-free networks.

REFERENCES

• 1: A. Ageev and M. Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization, 8:307--328, 2004.
• 2: K. M. Anstreicher, Linear Programming in O([n³/ln n]L) Operations, SIAM Journal on Optimization, v.9 n.4, p.803-812, 1999 [doi>10.1137/S1052623497323194]
• 3: C. Chekuri and A. Kumar. Maximum coverage problem with group budget constraints and applications. In Proc. of Approximation, Randomization, and Combinatorial Optimization, pp. 72--83, October 2004.
• 4: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 5: A. Haq, A. Naveed, and S. Kanhere. Securing channel assignment in multi-radio multi-channel wireless mesh networks. In Proc. of IEEE WCNC, pp. 3111--3116, March 2007.
• 6: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 7: Issa Khalil, LITEWORP: A Lightweight Countermeasure for the Wormhole Attack in Multihop Wireless Networks, Proceedings of the 2005 International Conference on Dependable Systems and Networks, p.612-621, June 28-July 01, 2005 [doi>10.1109/DSN.2005.58]
• 8: P. Kyasanur and N. Vaidya. Detection and handling of MAC layer misbehavior in wireless networks. In Proc. of IEEE DSN, pp. 173--182, June 2003.
• 9: A. Naveed and S. Kanhere. Security vulnerabilities in channel assignment of multi-radio multi-channel wireless mesh networks. In Proc. of IEEE GLOBECOM, pp. 1--5, November 2006.
• 10: N. B. Salem and J.-P. Hubaux. Securing wireless mesh networks. IEEE Wireless Communications, 13(2):50--55, 2006.
• 11: A. Srinivasan, Distributions on Level-Sets with Applications to Approximation Algorithms, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.588, October 14-17, 2001
• 12: D. Subhadrabandhu, S. Sarkar, and F. Anjum. A framework for misuse detection in ad hoc networks--Part I. IEEE JSAC, 24(2):274--289, Feburary 2006.
• 13: Yi Yang , Sencun Zhu , Guohong Cao, Improving sensor network immunity under worm attacks: a software diversity approach, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374640]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

General Terms:
Algorithms, Security, Theory

Keywords:
approximation algorithm, lp rounding, multi-channel multi-radio wireless networks, security monitoring, wireless mesh networks