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

作     者：Shin, Dong-Hoon Bagchi, Saurabh 

作者机构：Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ 85287 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA 

出 版 物：《AD HOC NETWORKS》 (特别网络)

年 卷 期：2013年第11卷第3期

页      面：926-943页

核心收录：

学科分类：0810[工学-信息与通信工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation [CNS-831999, CNS-0829588] Direct For Computer & Info Scie & Enginr Division Of Computer and Network Systems Funding Source: National Science Foundation 

主　　题：Wireless mesh networks Multi-channel multi-radio wireless networks Security monitoring Approximation algorithm LP rounding 

摘      要：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. (C) 2012 Elsevier B.V. All rights reserved.