Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

3D camera sensor scheduling algorithms for indoor multi-objective tracking

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

With the advantages of sensing data’s diversity, camera sensor networks (CSNs) have been applied to objective tracking in both outdoor and indoor environments. In indoor objective tracking, the objectives’ moving mode and sensors’ deployment have limitation and particularity, which bring more challenges on persistent monitoring for CSNs. In this paper, we consider the indoor multi-objective tracking in three-dimensional (3D) CSNs and focus on the 3D camera sensor scheduling for objective tracking to improve the coverage quality of the objective trajectory and minimizing the whole working periods. We firstly introduce the active-period-minimizing scheduling problem in CSNs for indoor objective tracking, with the goal of minimizing the total active periods of sensors. We solve the problem via three algorithms: the first algorithm is designed based on our proposed projection-based algorithm for single-objective case; the second one is proposed with the main idea of path coloring and the third one is a divide-and-conquer strategy with an approximation ratio of \(H(\frac{area(\mathcal {B})}{gside^2})\). To evaluate these algorithms’ performance on the time efficiency, we conduct extensive simulation experiments and analyze their results on the time efficiency advantages and applicable scenarios.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  • Bai X, Zhao DN, Bai S, Wang Q, Li WL, Mu DM (2020) Minimum connected dominating sets in heterogeneous 3D wireless ad hoc networks, Ad Hoc Networks 97,102023

  • Brown T, Wang ZH, Shan T, Wang F, Xue JX (2017) Obstacle-aware wireless video sensor network deployment for 3D indoor monitoring. In: Proceedings of IEEE global communications conference (GLOBECOM), pp 1–6

  • Cardei M, Du DZ (2005) Improving Wireless Sensor Network Lifetime through Power Aware Organization. Wireless Netw 11(3):333–340

    Article  Google Scholar 

  • Cardei M, Wu J (2006) Energy-efficient Coverage Problems in Wireless Ad-hoc Sensor Networks. Comput Commun 29(4):413–420

    Article  Google Scholar 

  • Cardei M, Thai MT, Li YS, Wu J (2005) Energy-efficient Target Coverage in Wireless Sensor Networks, Proc. of IEEE International Conference on Computer Communications (INFOCOM), pp. 1976-1982

  • Costa DG, Guedes LA (2010) The coverage problem in video-based wireless sensor networks: a survey. Sensors 10:8215–8247

    Article  Google Scholar 

  • Deif DS, Gadallah Y (2014) Classification of wireless sensor networks deployment techniques. IEEE Commun Surv Tutor 16(2):834–855

    Article  Google Scholar 

  • Du XF, Wu WL, Kelley DF (1998) Approximations for subset interconnection designs. Theor Comput Sci 207:171–180

    Article  MathSciNet  Google Scholar 

  • Han K, Xiang L, Luo J, Liu Y (2012) Minimum-energy connected coverage in wireless sensor networks with omni-directional and directional features. In: Proceedings of ACM international symposium on Mobile Ad Hoc Networking and Computing. ACM, pp 85–94

  • Hong Y, Wang YC, Zhu YQ, Li DY, Chang MJ, Chen ZB (2019) Projection-based coverage algorithms in 3D camera sensor networks for indoor objective tracking. In: Proceedings of The 8th international conference on computational data and social networks (CSoNet), pp 309–320

  • Jia JL, Dong CL, Hong Y, Guo L, Yu Y (2019) Maximizing full-view target coverage in camera sensor networks. Ad Hoc Netw 94:101973

    Article  Google Scholar 

  • Liu XL, Yang B, Chen GL (2019) Full-view barrier coverage in mobile camera sensor networks. Wireless Netw 25:4773–4784

    Article  Google Scholar 

  • Shi T, Cheng SY, Li JZ, Gao H, Cai ZP (2019) Dominating sets construction in RF-based batery-free sensor networks with full coverage guarantee. ACM Trans Sensor Netw 15(4): Article 43

  • Wang Y, Cao GH (2011) On full-view coverage in camera sensor networks. In: Proceedings of IEEE international conference on computer communications (INFOCOM), pp 1781–1789

  • Wang Y, Song L et al (2016) IntenCT: Efficient Multi-Target Counting and Tracking by Binary Proximity Sensors. Proc. of IEEE International Conference on Sensing, Communication, and Networking (SECON), pp. 1-9

  • Xu S, Lyu W, Li H (2015) Optimizing coverage of 3d wireless multimedia sensor networks by means of deploying redundant sensors. International Journal of Advanced Studies in Computers, Science and Engineering 4(9):28

    Google Scholar 

  • Zygowski C, Jaekel A (2020) Optimal path planning strategies for monitoring coverage holes in Wireless Sensor Networks. Ad Hoc Netw 96:101990

    Article  Google Scholar 

Download references

Acknowledgements

This research was supported by the Fundamental Research Funds for the Central Universities (No. BLX201921). It was also supported in part by General Project of Science and Technology Plan of Beijing Municipal Education Commission (KM201910017006), Program of Beijing Excellent Talents Training for Young Scholar (2016000020124G056).

Author information

Authors and Affiliations

  1. School of Information, Beijing Forestry University, Beijing, 100083, People’s Republic of China

    Yi Hong & Zhibo Chen

  2. Engineering Research Center for Forestry-Oriented Intelligent Information Processing, National Forestry and Grassland Administration, Beijing, 100083, People’s Republic of China

    Yi Hong & Zhibo Chen

  3. School of Information, Renmin University of China, Beijing, 100872, People’s Republic of China

    Yongcai Wang & Deying Li

  4. Department of Computer Science, California State University Los Angeles, Los Angeles, CA, 90032, USA

    Yuqing Zhu

  5. Information Engineering College, Beijing Institute of Petrochemical Technology, Beijing, 102617, People’s Republic of China

    Jing Li

Authors
  1. Yi Hong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yongcai Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yuqing Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Deying Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Zhibo Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Jing Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yi Hong.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hong, Y., Wang, Y., Zhu, Y. et al. 3D camera sensor scheduling algorithms for indoor multi-objective tracking. J Comb Optim 39, 899–914 (2020). https://doi.org/10.1007/s10878-020-00532-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-020-00532-0

Keywords

Search

Navigation