Automated or semiautomated surveillance monitoring involves movement tracking and sensor handoff. In order to track moving objects over a large area, sensor coverage needs to overlap significantly. Overlapping coverage can be modeled using the concept of backup coverage, a location modeling approach that seeks to maximize primary and backup coverage simultaneously. This kind of sensor placement problem belongs to the class of NP-hard combinatorial optimization problems, so computational difficulty is expected when solving large problem instances, not to mention the need for dealing with multiple objectives. Beyond this, backup coverage for supporting sensor placement actually brings about confounding problem instances for branch-and-bound approaches because of the trade-off between primary and backup coverage. To address these difficulties, this paper develops a multiobjective evolutionary algorithm for the backup coverage problem to support sensor placement. The solutions of this algorithm are evaluated in terms of computational requirements and solution quality.
Get full access to this article
View all access options for this article.
References
1.
AlpOErkutEDreznerZ, 2003, “An efficient genetic algorithm for the p-median problem”Annals of Operations Research12221–42
2.
ArakakiR G ILorenaL A N, 2001, “A constructive genetic algorithm for the maximal covering location problem”, in Proceedings of MIC 2001: 4th Metaheuristics International Conference13–17
3.
AytugHSaydamC, 2002, “Solving large-scale maximum expected covering location problems by genetic algorithms: A comparative study”European Journal of Operational Research141480–494
4.
BattyM, 2006, “Icons of the early 21st century: 2: Security and surveillance”Environment and Planning B: Planning and Design331–2
5.
BeasleyJ EChuP C, 1996, “A genetic algorithm for the set covering problem”European Journal of Operational Research94392–404
6.
BerlinG N, 1972Facility Location and Vehicle Allocation for Provision of An Emergency Service PhD thesis, Department of Geography and Environmental Engineering, The Johns Hopkins University, Baltimore, MD
7.
BozkayaBZhangJErkutE, 2002, “An efficient genetic algorithm for the p-median problem”, in Facility Location: Applications and Theory Eds DreznerZHamacherH (Springer, Berlin) pp 179–205
8.
ChaudhryS SHeSChaudhryP E, 2003, “Solving a class of facility location problems using genetic algorithms”Expert Systems2086–91
9.
ChuT-PRappaportS S, 1997, “Overlapping coverage with reuse partitioning in cellular communication systems”IEEE Transactions on Vehicular Technology4641–54
10.
CoelloC A, 1999, “A comprehensive survey of evolutionary-based multiobjective optimization techniques”Knowledge and Information Systems: An International Journal1269–308
11.
CohonJ L, 1978Multiobjective Programming and Planning (Academic Press, New York)
12.
CollinsR TLiptonA JKanadeT, 2000a, “Introduction to the special section on video surveillance”IEEE Transactions on Pattern Analysis and Machine22745–746
13.
CollinsR TLiptonA JKanadeTFujiyoshiHDugginsDTsinYTolliverDEnomotoNHasegawaOBurtPWixsonL, 2000b, “A system for video surveillance and monitoring”, CMU-RI-TR-00-12, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA
14.
CookW JCunninghamW HPulleyblankW RSchrijverA, 1998Combinatorial Optimization (John Wiley, New York)
15.
DasIDennisJ E, 1997, “A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems”Structural and Multidisciplinary Optimization1463–69
16.
DaskinM SSternE H, 1981, “A hierarchical objective set covering model for emergency medical service vehicle deployment”Transportation Science15137–152
17.
DebK, 2001Multi-objective Optimization using Evolutionary Algorithms (John Wiley, New York)
18.
DebKPratapAAgarwalSMeyarivanT, 2002, “A fast and elitist multiobjective genetic algorithm: NSGA-II”IEEE Transactions on Evolutionary Computation6182–197
19.
DickABrooksM J, 2003, “Issues in automated visual surveillance”, in Proceedings of VIIth Digital Image Computing: Techniques and ApplicationsSydney, Australia, pp 195–204
20.
DodgeMKitchinR, 2005, “Codes of life: Identification codes and the machine-readable world”Environment and Planning D: Society and Space23851–881
21.
EhrgottMGandibleuxX, 2000, “A survey and annotated bibliography of multiobjective combinatorial optimization”OR Spectrum22425–460
22.
FogelD B, 1994, “Asymptotic convergence properties of genetic algorithms and evolutionary programming: Analysis and experiments”Cybernetics and Systems25389–407
GoldbergD E, 1989Genetic Algorithms in Search, Optimization and Machine Learning (Addison-Wesley, Boston, MA)
26.
GoodchildM FLeeJ, 1989, “Coverage problems and visibility regions on topographic surfaces”Annals of Operations Research18175–186
27.
GrahamS, 2002, “CCTV: The stealthy emergence of a fifth utility?”Planning Theory and Practice3237–241
28.
GrahamSWoodD, 2002, “Digitizing surveillance: Categorization, space, inequality”Critical Social Policy23227–248
29.
GulerSGriffithJ MPusheeI A, 2003, “Tracking and handoff between multiple perspective camera views”, in Proceedings of the 32nd Applied Imagery Pattern Recognition Workshop (AIPR'03)Washington, DC, 275–281
30.
HoganKReVelleC, 1986, “Concepts and applications of backup coverage”Management Science321434–1444
31.
HollandJ H, 1975Adaptation in Natural and Artificial Systems (The University of Michigan Press, Ann Arbor, MI)
32.
HosageC MGoodchildM F, 1986, “Discrete space location-allocation solution from genetic algorithms”Annals of Operations Research635–46
33.
HouckC RJoinesJ AKayM G, 1996, “Comparison of genetic algorithms, random restart and two-opt switching for solving large location-allocation problems”Computers and Operations Research23587–596
34.
JaramilloJ HBhaduryJBattaR, 2002, “On the use of genetic algorithms to solve location problems”Computers and Operations Research29761–779
35.
KhanSJavedOShahM, 2001, “Tracking in uncalibrated cameras with overlapping field of view”, in Proceedings of Performance Evaluation of Tracking and Surveillance PETS 2001Kauai, HI
36.
KimY-HRanaSWiseS, 2004, “Exploring multiple viewshed analysis using terrain features and optimisation techniques”Computers and Geosciences301019–1032
37.
KoskiJ, 1985, “Defectiveness of weighting method in multicriterion optimization of structures”Communications in Applied Numerical Methods1333–337
38.
LeeJ, 1991, “Analyses of visibility sites on topographic surfaces”International Journal of Geographical Information Systems5413–429
39.
LorenaL A NLopesL S, 1997, “Genetic algorithms applied to computationally difficult set covering problems”Journal of the Operational Research Society48440–445
40.
LyonD, (Ed.), 2002Surveillance and Social Sorting: Privacy, Risk, and Digital Discrimination (Routledge, London)
41.
MalcolmS AReVelleC, 2005a, “Models for preserving species diversity with backup coverage”Environment Modeling and Assessment10(2) 99–105
42.
MalcolmS AReVelleC, 2005b, “Representational success: A new paradigm for achieving species protection by reserve site selection”Environmental Modeling and Assessment10341–348
MitchellM, 1996An Introduction to Genetic Algorithms (MIT Press, Cambridge, MA)
45.
MonmonierM, 2002Spying with Maps: Surveillance Technologies and the Future of Privacy (The University of Chicago Press, Chicago, IL)
46.
MurrayA TKimKDavisJ WMachirajuRParentR, 2007, “Coverage optimization to support security monitoring”Computers Environment and Urban Systems31133–147
47.
NixA EVoseM D, 1992, “Modeling genetic algorithms with Markov chains”Annals of Mathematics and Artificial Intelligence579–88
48.
ObraczkaKManduchiRGarcia-Luna-AcevesJ J, 2002, “Managing the information flow in visual sensor networks”, in Proceedings of the Fifth International Symposium on Wireless Personal Multimedia Communication (WMPC)volume 3, 1177–1181
49.
PanayiotouC GCassandrasC G, 2000, “Call allocation in cellular communication systems with overlapping coverage”, in Proceedings of the 39th IEEE Conference on Decision and Controlvolume 1 (IEEE Press, New York) pp 55–60
50.
PavlidisIMorellasVTsiamyrtziaPHarpS, 2001, “Urban surveillance systems: From the laboratory to the commercial world”Proceedings of the IEEE891478–1497
51.
PereiraA G, 1996, “Generating alternative routes by multicriteria evaluation and a genetic algorithm”Environment and Planning B: Planning and Design23711–720
Rubenstein-MontanoBZandiI, 1999, “Application of a genetic algorithm to policy planning: The case of solid waste”Environment and Planning B: Planning and Design26893–907
55.
RudolphG, 1996, “Convergence of evolutionary algorithms in general search spaces”, in Proceedings of the Third IEEE Conference on Evolutionary Computation (IEEE Press, New York) pp 50–54
56.
SaydamCAytugH, 2003, “Accurate estimation of expected coverage: Revisited”Socio-Economic Planning Sciences3769–80
57.
SrinivasNDebK, 1995, “Multiobjective function optimization using nondominated sorting genetic algorithms”Evolutionary Computation2221–248
58.
SykesC J, 1999The End of Privacy (St. Martin's Press, New York)
59.
ThielG, 2000, “Automatic CCTV surveillance—towards the VIRTUAL GUARD”IEEE Aerospace and Electronics Systems Magazine153–9
60.
TianDGeorganasN D, 2005, “Connectivity maintenance and coverage preservation in wireless sensor networks”Ad Hoc Networks3744–761
61.
TzengG HLinJ-J, 1996, “Using backup coverage and TOPSIS fuzzy approach to emergency facilities layout in new development planning area”, in Proceedings of the 1996 Asian Fuzzy Systems SymposiumKenting, Taiwan, 109–114
62.
ValeraMVelastinS A, 2005, “Intelligent distributed surveillance systems: A review”IEEE Proceedings—Vision, Image and Signal Processing152192–204
63.
WelshB CFarringtonD P, 2003, “Effects of closed-circuit television on crime”The Annals of the American Academy of Political and Social Sciences587110–135
64.
XiaoN, 2006, “An evolutionary algorithm for site search problems”Geographical Analysis38227–247
65.
XiaoNBennettD AArmstrongM P, 2002, “Using evolutionary algorithms to generate alternatives for multiobjective site-search problems”Environment and Planning A34639–656
66.
XuMOrwellJLoweyLThirdeD, 2005, “Architecture and algorithms for tracking football players with multiple cameras”IEEE Proceedings—Vision, Image and Signal Processing152232–241
67.
ZhangHHouJ C, 2005, “Maintaining sensing coverage and connectivity in large sensor networks”AD Hoc and Sensor Wireless Networks189–124
68.
ZitzlerEDebKThieleL, 2000, “Comparison of multiobjective evolutionary algorithms: Empirical results”Evolutionary Computation8173–195
