Sage Journals: Discover world-class research

Abstract

We study in this paper the problem of minimizing the number and the locations of deployed cameras in visual sensor networks where to objective is to monitor a set of targets with a predefined quality level. To this end, we first propose a mathematical programming formulation, based on mixed-integer linear programming (MILP), which is designed to provide optimal solutions in case where the deployment area is represented through a set of discrete potential locations of the cameras. Due to the combinatorial nature of such problems, finding exact solutions entails a tremendous computational cost. Consequently, we introduce various suboptimal solution approaches, based on a number of well-known metaheuristics, such as particle swarm optimization (PSO) and genetic algorithms. Numerical results show PSO succeeds to find the best solutions in the majority of considered scenarios. Furthermore, even for large instances, it provides better feasible solutions than those returned the MILPs after a significant amount of time.

Keywords

Visual sensor networks deployment problem mixed-integer linear programming particle swarm optimization genetic algorithms greedy algorithms simulated annealing target coverage

Get full access to this article

View all access options for this article.

References

J.-W.

Ahn ,

T.-W.

Chang ,

S.-H.

Lee and

Y.W.

Seo , Two-phase algorithm for optimal camera placement, Scientific Programming 2016 (2016), 7.

Ai and

A.A.

Abouzeid , Coverage by directional sensors in randomly deployed wireless sensor networks, Journal of Combinatorial Optimization 11(1) (2006), 21–41. doi:10.1007/s10878-006-5975-x.

N.A.B.A.

Aziz ,

A.W.

Mohemmed and

M.Y.

Alias , A wireless sensor network coverage optimization algorithm based on particle swarm optimization and Voronoi diagram, in: Networking, Sensing and Control, 2009. ICNSC’09. International Conference on, IEEE, 2009, pp. 602–607.

D.G.

Costa ,

Silva ,

L.A.

Guedes ,

Vasques and

Portugal , Optimal sensing redundancy for multiple perspectives of targets in wireless visual sensor networks, in: Industrial Informatics (INDIN), 2015 IEEE 13th International Conference on, IEEE, 2015, pp. 185–190.

Gorse , Binary particle swarm optimisation with improved scaling behaviour., in: ESANN, 2013.

S.K.

Gupta ,

Kuila and

P.K.

Jana , Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks, Computers & Electrical Engineering 56 (2016), 544–556.

Kennedy , Particle swarm optimization, in: Encyclopedia of Machine Learning, Springer, 2011, pp. 760–766.

Mavrinac and

Chen , Modeling coverage in camera networks: A survey, International journal of computer vision 101(1) (2013), 205–226. doi:10.1007/s11263-012-0587-7.

Morsly ,

Aouf ,

M.S.

Djouadi and

Richardson , Particle swarm optimization inspired probability algorithm for optimal camera network placement, Sensors Journal, IEEE 12(5) (2012), 1402–1412. doi:10.1109/JSEN.2011.2170833.

10.

Ozkan ,

Ermis and

Bekmezci , A hybrid matheuristic approach for designing reliable wireless multimedia sensor networks, in: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, ACM, 2015, pp. 875–882.

11.

Piciarelli ,

Esterle ,

Khan ,

Rinner and

G.L.

Foresti , Dynamic reconfiguration in camera networks: A short survey, IEEE Transactions on Circuits and Systems for Video Technology 26(5) (2016), 965–977. doi:10.1109/TCSVT.2015.2426575.

12.

Poli ,

Kennedy and

Blackwell , Particle swarm optimization, Swarm intelligence 1(1) (2007), 33–57. doi:10.1007/s11721-007-0002-0.

13.

B.I.

Schmitt , Convergence Analysis for Particle Swarm Optimization, FAU University Press, 2015.

14.

Trucco ,

Umasuthan ,

A.M.

Wallace and

Roberto , Model-based planning of optimal sensor placements for inspection, Robotics and Automation, IEEE Transactions on 13(2) (1997), 182–194. doi:10.1109/70.563641.

15.

P.J.

Van Laarhoven and

E.H.

Aarts , Simulated Annealing, Springer, 1987.

16.

Wang , Coverage problems in sensor networks: A survey, ACM Computing Surveys (CSUR) 43(4) (2011), 32. doi:10.1145/1978802.1978811.

17.

Y.-C.

Xu ,

Lei and

E.A.

Hendriks , Camera network coverage improving by particle swarm optimization, EURASIP Journal on Image and Video Processing 2011(1) (2010), 458283.

18.

F.G.

Yap and

H.-H.

Yen , A survey on sensor coverage and visual data capturing/processing/transmission in wireless visual sensor networks, Sensors 14(2) (2014), 3506–3527. doi:10.3390/s140203506.

19.

Yildiz ,

Akkaya ,

Sisikoglu and

M.Y.

Sir , Optimal camera placement for providing angular coverage in wireless video sensor networks, IEEE transactions on computers 63(7) (2014), 1812–1825. doi:10.1109/TC.2013.45.

20.

Yoon and

Y.-H.

Kim , An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks, IEEE Transactions on Cybernetics 43(5) (2013), 1473–1483. doi:10.1109/TCYB.2013.2250955.

On optimizing the deployment cost of visual sensor networks

Abstract

Keywords

Get full access to this article

References