Special Issue: Computer Networks and Distributed Computing

• Articles • Previous Articles    

Double Barrier Coverage in Dense Sensor Networks

Cheng-Dong Jiang and Guo-Liang Chen   

  1. Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China
  • Received:2006-12-12 Revised:2007-10-19 Online:2008-01-15 Published:2008-01-10

When a sensor network is deployed to detect objects penetrating a protected region, it is not necessary to have every point in the deployment region covered by a sensor. It is enough if the penetrating objects are detected at some point in their trajectory. If a sensor network guarantees that every penetrating object will be detected by two distinct sensors at the same time somewhere in this area, we say {that} the network provides double barrier coverage (DBC). In {this paper}, we propose a new planar structure of Sparse Delaunay Triangulation (SparseDT), and prove some elaborate attributes of it. We develop theoretical foundations for double barrier coverage, and propose efficient algorithms with NS2 simulator using which one can activate the necessary sensors to guarantee double barrier coverage while the other sensors go to sleep. The upper and lower bounds of number of active nodes are determined, and we show that high-speed target will be detected efficiently with this configuration.

Key words: security protocol; protocol analysis; formal method; reflection Attack;

[1] Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava M B. Coverage problems in wireless ad-hoc sensor networks. In -\it Proc. INFOCOM}, vol.3, Anchorage, Alaska, USA, 2001, pp.1380--1387.

[2] Meguerdichian S, Koushanfar F, Qu G, Potkonjak M. Exposure in wireless ad-hoc sensor networks. In -\it Proc. MOBICOM}, Rome, Italy, 2001, pp.139--150.

[3] Liu B, Towsley D. On the coverage and detectability of wireless sensor networks. In -\it Proc. WiOpt'03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks}, Sophia-Antipolis, France, 2003.

[4] Thai M T, Wang F, Du Ding-Zhu. Coverage problems in wireless sensor networks: Designs and analysis. -\it International Journal of Sensor Networks, Special Issue on Coverage Problems in Sensor Networks}, 2006, accepted.

[5] Kumar S, Lai T H, Arora A. Barrier coverage with wireless sensors. In -\it Proc. MOBICOM}, Porta, T L, Lindemann C, Belding-Royer E M, Lu S (eds.), ACM, 2005, pp.284--298.

[6] Li Xiang-Yang, Calinescu G, Wan P J. Distributed construction of planar spanner and routing for ad hoc wireless networks. In -\it Proc. INFOCOM}, New York, USA, 2002, pp.1268--1277.

[7] Li Xiang-Yang, Stojmenovic I, Wang Y. Partial Delaunay triangulation and degree limited localized bluetooth scatternet formation. -\it IEEE Trans. Parallel Distrib. Syst.}, 2004, 15(4): 350--361.

[8] Xing Guoliang, Lu Chenyang, Pless R, Huang Qingfeng. Impact of sensing coverage on greedy geographic routing algorithms. -\it IEEE Trans. Parallel Distrib. Syst.}, 2006, 17(4): 348--360.

[9] Ara-\'u}jo F, Rodrigues L. Fast localized Delaunay triangulation. In -\it Proc. OPODIS}, Grenoble, France, -\it LNCS} 3544, Higashino T (ed.), Springer, 2004 pp.81--93.

[10] Guibas L J, Knuth D E, Sharir M. Randomized incremental construction of -Delaunay} and -Voronoi} diagrams. -\it Algorithmica}, 1992, 7: 381--413, also In -\it Proc. 17th Int. Colloq. Automata, Languages and Programming}, Warwick University, England, -\it LNCS} 443, Springer-Verlag, 1990, pp.414--431.

[11] Sack J, Urrutia G (eds.). Voronoi Diagrams. Handbook of Computational Geometry. Elsevier Science Publishing, 2000.

[12] Kumar S, Lai T H, Balogh J. On $k$-coverage in a mostly sleeping sensor network. In -\it Proc. MOBICOM}, Haas Z J, Das S R, Jain R (eds.), ACM, 2004, pp.144--158.
[1] Osman Hasan and Sofiéne Tahar, Senior Member, IEEE, Member, ACM . Formally Analyzing Expected Time Complexity of Algorithms Using Theorem Proving [J]. , 2010, 25(6): 1305-1320.
[2] Chao Cai, Zong-Yan Qiu, Senior Member, CCF, Member, IEEE, Hong-Li Yang, and Xiang-Peng Zhao. Global-to-Local Approach to Rigorously Developing Distributed System with Exception Handling [J]. , 2009, 24(2): 238-249.
[3] Zhiguo Wan, Robert H. Deng, Feng Bao, Bart Preneel, and Ming Gu. nPAKE^+: A Tree-Based Group Password-Authenticated Key Exchange Protocol Using Different Passwords [J]. , 2009, 24(1 ): 138-151 .
[4] Deng-Guo Feng and Xiao-Yun Wang. Progress and Prospect of Some Fundamental Research on Information Security in China [J]. , 2006, 21(5): 740-755 .
[5] Jian-Hua Zhao, Xuan-Dong Li, Tao Zheng, and Guo-Liang Zheng. Remove Irrelevant Atomic Formulas for Timed Automaton Model Checking [J]. , 2006, 21(1): 41-51 .
[6] Xiu-Li Sun, Wen-Yin Zhang, and Jin-Zhao Wu. Event-Based Operational Semantics and a Consistency Result for Real-Time Concurrent Processes with Action Refinement [J]. , 2004, 19(6): 0-0.
[7] JI QingGuang (季庆光), QING SiHan (卿斯汉), ZHOU YongBin (周永彬) and FENG DengGuo (冯登国). Study on Strand Space Model Theory [J]. , 2003, 18(5): 0-0.
[8] LIU Dongxi (刘东喜), LI Xiaoyong (李小勇) and BAI Yingcai (白英彩). An Attack-Finding Algorithm for Security Protocols [J]. , 2002, 17(4): 0-0.
[9] LI Layuan; LI Chunlin;. A Semantics-Based Approach for Achieving Self Fault-Tolerance of Protocols [J]. , 2000, 15(2): 176-183.
[10] DING Yiqiang;. An Improvement ofGNY Logic for the Reflection Attacks [J]. , 1999, 14(6): 619-623.
Full text



[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[5] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[6] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[7] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[8] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
[9] Shang Lujun; Xu Lihui;. Notes on the Design of an Integrated Object-Oriented DBMS Family[J]. , 1991, 6(4): 389 -394 .
[10] Xu Jianguo; Gou Yuchai; Lin Zongkai;. HEPAPS:A PCB Automatic Placement System[J]. , 1992, 7(1): 39 -46 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved