TY - GEN
T1 - Localized flooding backbone construction for location privacy in sensor networks
AU - Xiang, Yingchang
AU - Cheng, Xiuzhen
AU - Xing, Kai
AU - Chen, Dechang
AU - Song, Min
PY - 2007
Y1 - 2007
N2 - Source and destination location privacy is a challenging and important problem in sensor networks. Nevertheless, privacy preserving communication in sensor networks is still a virgin land. In this paper, we propose to protect location privacy via a flooding backbone, which is modeled by a minimum connected dominating set (MCDS) in unit-disk graphs. We design an efficient and localized algorithm to compute an approximate MCDS. Theoretical analysis indicates that our algorithm generates a connected dominating set (CDS) with a size at most 148 •opt + 37, where opt is the cardinality of a MCDS. To our best knowledge, this algorithm is the first localized algorithm with a constant performance ratio for CDS construction in unit-disk graphs.
AB - Source and destination location privacy is a challenging and important problem in sensor networks. Nevertheless, privacy preserving communication in sensor networks is still a virgin land. In this paper, we propose to protect location privacy via a flooding backbone, which is modeled by a minimum connected dominating set (MCDS) in unit-disk graphs. We design an efficient and localized algorithm to compute an approximate MCDS. Theoretical analysis indicates that our algorithm generates a connected dominating set (CDS) with a size at most 148 •opt + 37, where opt is the cardinality of a MCDS. To our best knowledge, this algorithm is the first localized algorithm with a constant performance ratio for CDS construction in unit-disk graphs.
UR - http://www.scopus.com/inward/record.url?scp=35148844245&partnerID=8YFLogxK
U2 - 10.1109/SNPD.2007.343
DO - 10.1109/SNPD.2007.343
M3 - Conference contribution
AN - SCOPUS:35148844245
SN - 0769529097
SN - 9780769529097
T3 - Proceedings - SNPD 2007: Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing
SP - 167
EP - 171
BT - Proceedings - SNPD 2007
T2 - SNPD 2007: 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing
Y2 - 30 July 2007 through 1 August 2007
ER -