An optimization framework for monitoring multi-channel multi-radio wireless mesh networks |
| |
| Authors: | Dong-Hoon Shin Saurabh Bagchi |
| |
| Affiliation: | 1. School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, AZ 85287, United States;2. School of Electrical and Computer Engineering, Purdue University, 465 Northwestern Avenue, West Lafayette, IN 47907, United States;1. Sense and Sense-abilities Programme, Institute for Infocomm Research, Singapore 138632, Singapore;2. Department of Electrical and Computer Engineering, National University of Singapore, Singapore 117576, Singapore;1. Xi’an University of Posts and Telecommunications, Xi’an, China;2. Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA;1. Department of Computer and Information Sciences, University of Hyderabad, Hyderabad 500 046, India;2. Lab-STICC, Université de Bretagne-Sud, F-56321 Lorient, France |
| |
| Abstract: | This paper studies an optimal monitoring problem for behavior-based detection in multi-channel 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: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
