Name
Abstract | ||
|---|---|---|
Local monitoring is an effective mechanism for the security of wireless sensor networks (WSNs). Existing schemes assume the existence of sufficient number of active nodes to carry out monitoring operations. Such an assumption, however, is often difficult for a large-scale sensor network. In this work, we focus on designing an efficient scheme integrated with good self-monitoring capability as well as providing an infrastructure for various security protocols using local monitoring. To the best of our knowledge, we are the first to present the formal study on optimizing network topology for edge self-monitoring in WSNs. We show that the problem is NP-complete even under the unit disk graph (UDG) model and give the upper bound on the approximation ratio in various graph models. We provide polynomial-time approximation scheme (PTAS) algorithms for the problem in some specific graphs, for example, the monitoring-set-bounded graph. We further design two distributed polynomial algorithms with provable approximation ratio. Through comprehensive simulations, we evaluate the effectiveness of our design. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/TPDS.2010.72 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
monitoring-set-bounded graph,various graph model,protocols,efficient scheme,security,unit disk graph,communication complexity,unit disk graph model,network topology,edge self-monitoring,np-complete problem,local monitoring,distributed polynomial algorithms,telecommunication network topology,np-complete.,polynomial-time approximation scheme,approximation ratio,self-monitoring,sensor networks,specific graph,graph theory,wireless sensor networks,telecommunication security,provable approximation ratio,good self-monitoring capability,security protocols,sensor network,algorithm design and analysis,polynomials,upper bound,wireless sensor network,national security,np complete,algorithm design,security protocol,np complete problem,approximation algorithms,self monitoring,polynomial time approximation scheme | Graph theory,Approximation algorithm,Key distribution in wireless sensor networks,Computer science,Computer network,Communication complexity,Network topology,Wireless sensor network,Polynomial-time approximation scheme,Distributed computing,Unit disk graph | Journal |
Volume | Issue | ISSN |
22 | 3 | 1045-9219 |
Citations | PageRank | References |
14 | 0.86 | 21 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dezun Dong | 1 | 178 | 31.90 |
| Xiangke Liao | 2 | 622 | 74.79 |
| Yunhao Liu | 3 | 8810 | 486.66 |
| Changxiang Shen | 4 | 127 | 14.57 |
| Xinbing Wang | 5 | 2642 | 214.43 |