Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD 2007)
Localized Flooding Backbone Construction for Location Privacy in Sensor Networks
Haier International Training Center, Qingdao, China
July 30-August 01
ISBN: 0-7695-2909-7
Dechang Chen, Uniformed Services University of the Health Sciences, USA
Kai Xing, The George Washington University, USA
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.
Citation:
Yingchang Xiang, Dechang Chen, Xiuzhen Cheng, Kai Xing, Min Song, "Localized Flooding Backbone Construction for Location Privacy in Sensor Networks," snpd, vol. 3, pp.167-171, Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD 2007), 2007
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb