Five Significant Publications

[4] DongHoon Shin and Saurabh Bagchi, “Optimal Monitoring In Multi-Channel Multi-Radio Wireless Mesh Networks,” At the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc), May 18-21, 2009, pp. 229-238, New Orleans, Louisiana. (Acceptance rate: 31/175 = 17.7%)

[ Paper in pdf ]

Problem Statement: 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.

Contribution of Paper: This problem had been solved for single channel networks by a greedy approximation algorithm since the exact solution is NP-hard. The greedy algorithm achieved the best performance, in terms of the worst case, possible among all polynomial-time algorithms. In this paper, we solved the problem for multichannel multi-radio WMNs. The intuitive extension of the greedy algorithm destroys the property of best performance. Instead, we formulated the problem as an integer linear program, solved its linear program relaxation, and then used two rounding techniques that we developed by adapting existing rounding schemes. We thereby presented two approximation algorithms. The first, computationally-light algorithm, called probabilistic rounding algorithm gave an expected best performance in the worst case. The second, called deterministic rounding algorithm achieved the best worst-case performance in a deterministic manner. To evaluate how the three algorithms perform in practice, we simulated them in random networks and scale-free networks. We thus showed both the theoretical best approximation ratio and the practical tradeoff for deploying such a solution so that it converges quickly. In subsequent work (Infocom 2012), we showed how the solution can be made distributed and still reach the best possible approximation ratio within a tunable ratio, which is a configurable parameter that determines how long it takes for the distributed algorithm to execute.