Constructing weakly connected dominating set for secure clustering in distributed sensor network

Hongjie Du; Weili Wu; Shan Shan; Donghyun Kim; Wonjun Lee

doi:10.1007/s10878-010-9358-y

Constructing weakly connected dominating set for secure clustering in distributed sensor network

Hongjie Du, Weili Wu, Shan Shan, Donghyun Kim, Wonjun Lee

School of Cybersecurity

Research output: Contribution to journal › Article › peer-review

16 Citations (Scopus)

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.

Original language	English
Pages (from-to)	301-307
Number of pages	7
Journal	Journal of Combinatorial Optimization
Volume	23
Issue number	2
DOIs	https://doi.org/10.1007/s10878-010-9358-y
Publication status	Published - 2012 Feb

Bibliographical note

Funding Information:
Acknowledgements This research was jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), a NRF Grant under (KRF-2008-314-D00354), and MKE, Korea under ITRC NIPA-2010-(C1090-1021-0008). The corresponding author is Wonjun Lee.

Keywords

DSN
Maximal independent set
Security
Unit disk graph
Weakly connected dominating set

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10878-010-9358-y

Cite this

@article{f42b084298e14c04bcb9bcbb1f8a8658,

title = "Constructing weakly connected dominating set for secure clustering in distributed sensor network",

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.",

keywords = "DSN, Maximal independent set, Security, Unit disk graph, Weakly connected dominating set",

author = "Hongjie Du and Weili Wu and Shan Shan and Donghyun Kim and Wonjun Lee",

note = "Funding Information: Acknowledgements This research was jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), a NRF Grant under (KRF-2008-314-D00354), and MKE, Korea under ITRC NIPA-2010-(C1090-1021-0008). The corresponding author is Wonjun Lee.",

year = "2012",

month = feb,

doi = "10.1007/s10878-010-9358-y",

language = "English",

volume = "23",

pages = "301--307",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Constructing weakly connected dominating set for secure clustering in distributed sensor network

AU - Du, Hongjie

AU - Wu, Weili

AU - Shan, Shan

AU - Kim, Donghyun

AU - Lee, Wonjun

N1 - Funding Information: Acknowledgements This research was jointly sponsored by MEST, Korea under WCU (R33-2008-000-10044-0), a NRF Grant under (KRF-2008-314-D00354), and MKE, Korea under ITRC NIPA-2010-(C1090-1021-0008). The corresponding author is Wonjun Lee.

PY - 2012/2

Y1 - 2012/2

N2 - 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.

AB - 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.

KW - DSN

KW - Maximal independent set

KW - Security

KW - Unit disk graph

KW - Weakly connected dominating set

UR - http://www.scopus.com/inward/record.url?scp=84858866273&partnerID=8YFLogxK

U2 - 10.1007/s10878-010-9358-y

DO - 10.1007/s10878-010-9358-y

M3 - Article

AN - SCOPUS:84858866273

SN - 1382-6905

VL - 23

SP - 301

EP - 307

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 2

ER -

Constructing weakly connected dominating set for secure clustering in distributed sensor network

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this