Constructing weakly connected dominating set for secure clustering in distributed sensor network
- Authors
- Du, Hongjie; Wu, Weili; Shan, Shan; Kim, Donghyun; Lee, Wonjun
- Issue Date
- 2월-2012
- Publisher
- SPRINGER
- Keywords
- DSN; Security; Weakly connected dominating set; Maximal independent set; Unit disk graph
- Citation
- JOURNAL OF COMBINATORIAL OPTIMIZATION, v.23, no.2, pp.301 - 307
- Indexed
- SCIE
SCOPUS
- Journal Title
- JOURNAL OF COMBINATORIAL OPTIMIZATION
- Volume
- 23
- Number
- 2
- Start Page
- 301
- End Page
- 307
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/106098
- DOI
- 10.1007/s10878-010-9358-y
- ISSN
- 1382-6905
- Abstract
- Secure clustering problem plays an important role in distributed sensor networks. Weakly Connected Dominating Set (WCDS) is used for solving this problem. Therefore, computing a minimum WCDS becomes an important topic of this research. In this paper, we compare the size of Maximal Independent Set (MIS) and minimum WCDS in unit disk graph. Our analysis shows that five is the least upper bound for this ratio. We also present a distributed algorithm to produce a weakly connected MIS within a factor 5 from the minimum WCDS.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - School of Cyber Security > Department of Information Security > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.