Full-View Area Coverage in Camera Sensor Networks: Dimension Reduction and Near-Optimal Solutions

The authors study the problem of minimum-number full-view area coverage in camera sensor networks, i.e., how to select the minimum number of camera sensors to guarantee the full-view coverage of a given region. Full-view area coverage is challenging because the full-view coverage of a 2-D continuous domain has to be considered. To tackle this challenge, the authors first study the intrinsic geometric relationship between the full-view area coverage and the full-view point coverage and prove that the full-view area coverage can be guaranteed, as long as a selected full-view ensuring set of points is full-view covered. This leads to a significant dimension reduction for the full-view area coverage problem. Next, the authors prove that the minimum-number full-view point coverage is NP-hard and propose two approximation algorithms to solve it from two different perspectives, respectively: 1) By introducing a full-view coverage ratio function, the authors quantify the “contribution” of each camera sensor to the full-view coverage through which we transform the full-view point coverage into a submodular set cover problem and propose a greedy algorithm (GA); and 2) by studying the geometric relationship between the full-view coverage and the traditional coverage, the authors propose a set-cover-based algorithm (SCA). The authors analyze the performance of these two approximation algorithms and characterize their approximation ratios. Furthermore, the authors devise two distributed algorithms that obtain the same approximation ratios as GA and SCA, respectively. Finally, the authors provide extensive simulation results to validate the analysis.

• Record URL:
  • https://doi.org/10.1109/TVT.2015.2498281
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/00189545
• Supplemental Notes:
  • Copyright © 2016, IEEE.
• Authors:
  • He, Shibo
  • Shin, Dong-Hoon
  • Zhang, Junshan
  • Chen, Jiming
  • Sun, Youxian
• Publication Date: 2016-9

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: pp 7448-7461
• Serial:
  • IEEE Transactions on Vehicular Technology
  • Volume: 65
  • Issue Number: 9
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • ISSN: 0018-9545
  • Serial URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=25

Subject/Index Terms

• TRT Terms: Algorithms; Cameras; Numerical approximation; Sensors
• Subject Areas: Data and Information Technology; Highways;

Filing Info

• Accession Number: 01614078
• Record Type: Publication
• Files: TRIS
• Created Date: Oct 25 2016 9:50AM