An optimization framework for monitoring multi-channel multi-radio wireless mesh networks

Authors: Dong-Hoon Shin, Saurabh Bagchi

Abstract:
This paper studies an optimal monitoring problem for behavior-based detection in multichannel multi-radio wireless mesh networks. In behavior-based detection, nodes overhear communications in their neighborhood to determine if the behaviors of their neighbors are legitimate. The objective of this work is to maximize the number of nodes being monitored by judiciously choosing a set of monitoring nodes and also channels for the chosen monitoring nodes. This problem is NP-hard, growing exponentially with the number of monitoring nodes. We develop three approximation algorithms, each of which achieves at least a constant factor of the optimum. Furthermore, one of our algorithms achieves the best possible approximation ratio among all polynomial-time algorithms, unless P = NP. We conduct simulations in random networks and scale-free networks to evaluate the coverage and the execution time of the three algorithms.

Keywords:
Wireless mesh networks
Multi-channel multi-radio wireless networks
Security monitoring
Approximation algorithm
LP rounding

Published in: Ad Hoc Networks (Volume 11, Issue 3, January 2013)

Publisher: Elsevier

ISSN Information: 1570-8705

An optimization framework for monitoring multi-channel multi-radio wireless mesh networks

Bình luận của bạn

*

*

*

*

 Captcha

Gửi bình luận nhập lại