A unified solving approach for two and three dimensional coverage problems in sensor networks

被引:5
作者
Sterle, Claudio [1 ]
Sforza, Antonio [1 ]
Amideo, Annunziata Esposito [1 ]
Piccolo, Carmela [2 ]
机构
[1] Univ Naples Federico II, Dept Elect Engn & Informat Technol, Via Claudio 21, I-80125 Naples, Italy
[2] Univ Naples Federico II, Dept Ind Engn, Piazzale Tecchio, I-80125 Naples, Italy
关键词
Sensor placement; Sensor network; Two and three dimensional coverage; Camera placement; TARGET LOCATION; OPTIMIZATION; ALGORITHMS; PLACEMENT;
D O I
10.1007/s11590-016-1014-8
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
The problem of designing a wired or a wireless sensor network to cover, monitor and/or control a region of interest has been widely treated in literature. This problem is referred to in literature as the sensor placement problem (SPP) and in the most general case it consists in determining the number and the location of one or more kind of sensors with the aim of covering all the region of interest or a significant part of it. In this paper we propose a unified and stepwise solving approach for two and three dimensional coverage problems to be used in omni-directional and directional sensor networks. The proposed approach is based on schematizing the region of interest and the sensor potential locations by a grid of points and representing the sensor coverage area by a circle or by a circular sector. On this basis, the SPP is reduced to an optimal coverage problem and can be formulated by integer linear programming (ILP) models. We will resume the main ILP models used in our approach, highlighting, for each of them, the specific target to be achieved and the design constraints taken into account. The paper concludes with an application of the proposed approach to a real test case and a discussion of the obtained results.
引用
收藏
页码:1101 / 1123
页数:23
相关论文
共 26 条
[11]  
Dhillon SS, 2002, PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON INFORMATION FUSION, VOL II, P1581, DOI 10.1109/ICIF.2002.1021005
[12]   Approximation algorithms for art gallery problems in polygons [J].
Ghosh, Subir Kumar .
DISCRETE APPLIED MATHEMATICS, 2010, 158 (06) :718-722
[13]   On coverage issues in directional sensor networks: A survey [J].
Guvensan, M. Amac ;
Yavuz, A. Gokhan .
AD HOC NETWORKS, 2011, 9 (07) :1238-1255
[14]   CONCEPTS AND APPLICATIONS OF BACKUP COVERAGE [J].
HOGAN, K ;
REVELLE, C .
MANAGEMENT SCIENCE, 1986, 32 (11) :1434-1444
[15]  
Horster E., 2006, P 4 ACM INT WORKSH V, P111, DOI DOI 10.1145/1178782.1178800
[16]   Covering models and optimization techniques for emergency response facility location and planning: a review [J].
Li, Xueping ;
Zhao, Zhaoxia ;
Zhu, Xiaoyan ;
Wyatt, Tami .
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2011, 74 (03) :281-310
[17]  
Marrone S, 2015, TOP SAF RISK RELIAB, V27, P197, DOI 10.1007/978-3-319-04426-2_10
[18]   Modeling Coverage in Camera Networks: A Survey [J].
Mavrinac, Aaron ;
Chen, Xiang .
INTERNATIONAL JOURNAL OF COMPUTER VISION, 2013, 101 (01) :205-226
[19]   Optimal visual sensor placement for coverage based on target location profile [J].
Mostafavi, Seyed Akbar ;
Dehghan, Mehdi .
AD HOC NETWORKS, 2011, 9 (04) :528-541
[20]   Coverage optimization to support security monitoring [J].
Murray, Alan T. ;
Kim, Kamyoung ;
Davis, James W. ;
Machiraju, Raghu ;
Parent, Richard .
COMPUTERS ENVIRONMENT AND URBAN SYSTEMS, 2007, 31 (02) :133-147