On optimizing the deployment cost of visual sensor networks

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

1. Introduction

Visual sensor networks (VSN) constitute a hot research topic [18], with numerous promising applications, including remote video surveillance, monitoring and assisting elderly and health patients, and habitat monitoring. VSN are generally deployed to autonomously and continuously monitor the totality of a geographic area of interest or a set of physical objects (targets) within that area [17]. Although, the price of cameras with networking capabilities drops significantly over the last years, minimizing the number of deployed cameras remains a first-class topic [11], because the overall system cost can increase significantly with the number of cameras, in particular where a wired network infrastructure is used to convey images towards a central processing node. On the other hand, depending on the application, the images of the observed targets must meet a number of quality criteria (e.g. number of pixels per inch) which either require using expensive cameras or reducing the distance between the cameras and targets which may decrease the number of targets that can be observed per camera. We study in this paper various techniques to solve the problem of tracking a set of targets with a required quality level objects on a two-dimensional place using a minimum of cameras. Our objective is to determine the cameras’ positions among a set of candidate locations along with their orientations. While small instances of this problem can be solved exactly using various mathematical formulations, as the problem size increases, solving such problem becomes computationally prohibitive. Indeed, Ai and Abouzeid [2] demonstrated that this problem is NP-hard in general. Consequently, besides the exact method formulated as a mixed-integer linear program, we introduce in this paper a number of suboptimal solution approaches, mainly based on meta-heuristic techniques. First, we adapt the generic framework of Particle Swarm Optimization (PSO). Next, in order to get insights on the effectiveness of this approach, we propose also three alternative approaches, based on greedy algorithms, genetic algorithms, and simulated annealing, respectively. The rest of paper is organized as follows. Section 2 discusses relevant literature on the subject. Section 3 describes the used coverage model, while our detailed mathematical model is given in Section 4. Our resolution methods are described in Section 5. Section 6 report and assess some numerical results. The last section concludes the paper and suggests some future research directions.

2. Related works

The coverage in visual sensor networks was studied by many works in the literature [8]. In [2], an exact integer linear program (ILP) and a Centralized Greedy Algorithm (CGA) for the maximum coverage with minimum sensors (MCMS) problem is given. A Distributed Greedy Algorithm (DGA) is also proposed. They used last centralized methods as comparative baseline. By incorporating a measure of the sensors residual energy into DGA, they also develop a Sensing Neighbourhood Cooperative Sleeping (SNCS) protocol which performs adaptive scheduling on a larger time scale. With this protocol, authors guaranteed the maximum coverage/lifetime network over the best existent protocol. Aziz et. al. [3] employed particle swarm optimization to build an algorithm which finds the near optimal deployment of sensors providing the best coverage. Then, they evaluated the fitness of the solution using Voronoi diagram. Their results showed that a good coverage is achieved in less time than existing approaches. The area coverage problem in a 2D/3D-grid space has been investigated in [9]. The solution process was based on binary particle swarm optimization inspired probability (BPSO-IP). This method is based on the PSO sharing mechanism information with a new probability based parameter. In addition, they proposed three other metaheuristics. They proved that PSO-IP overcomes the three other methods (on number of cameras deployed to ensure a total coverage), especially with large instances. Authors in [19] handled deployment in video sensor networks. They try to find optimal continuous deployment for angular coverage (cameras with 360° span) in tow stages, first a master problem try to find discrete positions from region of interest, next a sub-problem to determine which continuous points are not covered. They repeat this process iteratively until the sub-problem is infeasible. Authors in [6] studied a particular form of target coverage problem where the aim was to cover targets by at least k sensors that m-connected. They proposed a genetic approach to deal with this problem. The results were promising (better time complexity over other GA based methods). Author’s method, outperforms (selected potential positions) existing algorithms and greedy approach, in various scenarios of WSN. The authors in [4] proposed an algorithm to find the minimum number of visual activated sensors to cover all the targets. They took into account the multiple targets view from single node and explore the redundancy of nodes as energy savings (they considered active and sleep mode for redundant sensors). Finally, a two-phase algorithm, based on hybrid method (heuristic and exact solution), was designed in [1] to provide an approximate solution to the target coverage in a three-dimensional space. Note that our solution approach is partly inspired by the work in [9]. But as far as we know, no paper in the literature has formulated coverage problem in visual sensor networks that considers a continuous measure of image quality. Also, we designed an exact model as a means to evaluate the performance of various metaheuristic-based techniques.

3. Coverage model

Problems related to deployment of camera-based sensor networks can be generally classified according to the coverage type: (i) target coverage; (ii) area coverage. While in the second type, the objective is to cover a total geometric area with minimal camera sensors, our work is more related in the first type as we aim to cover a total number of given targets spread over some area.

To this end, we use the directional model [16] of camera coverage represented in Fig. 1.

Let assume that a camera is deployed over an Euclidean space A. We denote by $(x_{s}, y_{s})$ its Cartesian coordinates, and by $φ_{s}$ its orientation angle (i.e. ranging from 0 to 360°). As given in [14], the camera’s field of view can be represented with α, its aperture, and $W_{d}$ , its working distance. While a can be calculated from the equation: $\frac{a}{2 W_{d}} = tan (\frac{α}{2})$ . A target object (Fig. 2) located on some coordinates $(x_{t}, y_{t})$ is said to be covered by our camera if the three following constraints are satisfied:

Fig. 1.

Illustrations of: (a) Directional Model; (b) Three active cameras covering 4 targets.

$\begin{array}{l} (1a) & cos (φ) \cdot (x_{t} - x_{s}) + sin (φ) \cdot (y_{t} - y_{s}) ⩽ W_{d} \\ (1b) & - sin (φ) \cdot (x_{t} - x_{s}) + cos (φ) \cdot (y_{t} - y_{s}) ⩽ \frac{a}{2 W_{d}} \cdot (cos (φ) \cdot (x_{t} - x_{s}) + sin (φ) \cdot (y_{t} - y_{s})) \\ (1c) & - sin (φ) \cdot (x_{t} - x_{s}) + cos (φ) \cdot (y_{t} - y_{s}) ⩾ - \frac{a}{2 W_{d}} \cdot (cos (φ) \cdot (x_{t} - x_{s}) + sin (φ) \cdot (y - y_{s})) \end{array}$

Fig. 2.

Camera’s field of view.

4. Mathematical programming model

We introduce in the following our optimization model whose objective is to deploy a minimum number of cameras to cover a set of known targets in a two-dimensional space. Table 1 defines the main used notations.

Table 1
Problem’s formal notations

Variables Designation

N Set of possible camera locations

M Set of possible angles

T Set of targets

$(x_{i}, y_{i})$ Cartesian coordinates of a camera deployed in position $i \in N$

$(x_{i}^{t}, y_{j}^{t})$ Cartesian coordinates of the target $j \in T$

$d_{i j}$ The distance between camera i and target j

$φ_{k}$ Angle $k \in M$

δ Minimum required quality level

Variables	Designation
N	Set of possible camera locations
M	Set of possible angles
T	Set of targets
$(x_{i}, y_{i})$	Cartesian coordinates of a camera deployed in position $i \in N$
$(x_{i}^{t}, y_{j}^{t})$	Cartesian coordinates of the target $j \in T$
$d_{i j}$	The distance between camera i and target j
$φ_{k}$	Angle $k \in M$
δ	Minimum required quality level

First, we introduce the binary variables $b_{i j}$ and $O_{i k}$ defined as follows: $\begin{array}{l} b_{i j} = \{\begin{matrix} 1 & if the camera at position i covers target j \\ 0 & otherwise \end{matrix} \\ O_{i k} = \{\begin{matrix} 1 & if the camera at position i is directed with angle k \\ 0 & otherwise \end{matrix} \end{array}$

The minimization of the number of deployed cameras can be expressed using variables $O_{i k}$ , as follows: $\begin{matrix} (2) & min \sum_{i \in N} \sum_{k \in M} O_{i k} \end{matrix}$

Meanwhile, the following set of constraints must be satisfied. $\begin{matrix} (3) & \sum_{k \in M} O_{i k} ⩽ 1, \forall i \in N \end{matrix}$ which ensures that only one angle can be active for a given camera. $\sum_{k \in M} O_{i k} = 0$ , corresponds to the situation where no camera is deployed at location i.

Also, each target must be associated to at least one camera, which is guaranteed through the following set of constraints: $\begin{matrix} (4) & \sum_{i \in N} b_{i j} ⩾ 1, \forall j \in T \end{matrix}$

Now, if $b_{i j} = 1$ for some camera position i and target j, we must ensure that j belong to the field of view of this camera. Thus, we rewrite the aforementioned set constraints (1a)–(1c) as follows: $\begin{array}{l} (5) & \sum_{k \in M} O_{i k} [cos (φ_{k}) \cdot (x_{j}^{t} - x_{i}) + sin (φ_{k}) \cdot (y_{j}^{t} - y_{i})] ⩽ W_{d} + L_{1} (1 - b_{i j}), \forall i \in N, \forall j \in T \\ \sum_{k \in M} O_{i k} [- (sin (φ_{k}) + \frac{a}{2 W_{d}} cos (φ_{k})) (x_{j}^{t} - x_{i}) + (cos (φ_{k}) - \frac{a}{2 W_{d}} sin (φ_{k})) (y_{j}^{t} - y_{i})] \\ (6) & ⩽ L_{2} (1 - b_{i j}), \forall i \in N, \forall j \in T \\ \sum_{k \in M} O_{i k} [(sin (φ_{k}) - \frac{a}{2 W_{d}} cos (φ_{k})) (x_{j}^{t} - x_{i}) - (cos (φ_{k}) - \frac{a}{2 W_{d}} sin (φ_{k})) (y_{j}^{t} - y_{i})] \\ (7) & ⩽ L_{3} (1 - b_{i j}), \forall i \in N, \forall j \in T \end{array}$ where $L_{1}, L_{2}, L_{3}$ are large constants. One can observe that these constraints are active only if the corresponding $b_{i j} = 1$ . Otherwise, they are trivially satisfied.

Finally, we enforce a minimum coverage quality for each target through the following constraint: $\begin{matrix} (8) & \sum_{i \in N} b_{i j} \frac{C}{d_{i j}^{2}} ⩾ δ, \forall j \in T \end{matrix}$ where C is a constant. This formula was inspired by the work on [16]. Here, the quality decrease quadratically to the distance away from the sensor.

Due to the potential number of binary variables for real-world instance, this problem is computationally-hard to solve in general. We introduce in the following section a set suboptimal solution methods with the aim to obtain high-quality solutions in a reasonable amount of time.

5. Suboptimal solution approaches

We present in this section various solutions methods to solve our problem, first by defining a greedy algorithm and then by proposing a set of algorithms based on metaheuristic techniques.

5.1. Greedy algorithm

The idea of the greedy Algorithm 1 is to find at each iteration the pairs $(p, k) \subseteq (N, M)$ (position and angle, respectively) which maximizes the number of new covered targets ( ${#cov_targets}_{Φ} (p, k)$ ). Ties are broken arbitrarily. Hence, we eliminate after each iteration the targets that are already covered $(Φ ∖ {{cov_targets}_{Φ} (\hat{p}, \hat{k})})$ . The algorithm stops once there is no more targets to cover $(Φ = \emptyset)$ .

Algorithm 1:

Greedy Algorithm

5.2. PSO-based algorithm

Particle swarm optimization (PSO) is a meta-heuristic method invented by Russel Eberhart (Electrical Engineer) and James Kennedy (socio-psychologist) in 1995 [7]. This method, inspired by social behaviour, has been thought as an optimization tool dealing with continuous functions initially then discontinuous ones lately [12]. The original algorithm considers a population of individuals (fish schools), looking for some optimal region (amount of food). However, in contrast to evolutionary algorithms, particles of PSO cooperate together to find the optimal rather than competing against each other. Note that many research works showed the capability of PSO to tackle large instances problems [5].

In general, a PSO algorithm consists in a group of individuals named particles, where each has its own position in the search space and represents a potential solution to the optimization problem. After each iteration, these particle move according to their components [13]. Specifically, at some iteration t, a particle p is characterized by the following:

Actual velocity $V_{t}^{p}$ ;

Actual position $X_{t}^{p}$ ;

Best neighbourhood solution $L_{t}^{p}$ .

The best solution found so far is denoted $G_{t}$ . Then, the particle movement is done according to: $\begin{array}{l} (9) & V_{t + 1}^{p} = ω V_{t}^{p} + C_{1} r_{1} (L_{t}^{p} - X_{t}^{p}) + C_{2} r_{2} (G_{t} - X_{t}^{p}) \\ (10) & X_{t + 1}^{p} = X_{t}^{p} + V_{t + 1}^{p} \end{array}$ ω is the inertia weight, $r_{1}$ and $r_{2}$ are two random numbers uniformly chosen from $[0, 1]$ , and $C_{1}, C_{2}$ are constant values. Finally t is the iteration index.

A given solution for our deployment problem is a position ${pos}_{i} \in N$ and angle ${ang}_{i} \in M$ combined in a vector as: $x_{i} = {pos}_{i} \times card (M) + {ang}_{i}$ (see Fig. 3), so: $\begin{matrix} X^{p} = ⟨ x_{1}, x_{2}, \dots, x_{\hat{n}} ⟩, \end{matrix}$ represents particle’s positions, while respective velocities are $\begin{matrix} V^{p} = ⟨ v_{1}, v_{2}, \dots, v_{\hat{n}} ⟩, \forall i ⩽ \hat{n}, v_{i} \in R \end{matrix}$

To enable “particle travel”, we allow two types of movement at each iteration:

Rotation: changing the orientation of one deployed camera.

Displacement: moving some camera to another position.

Fig. 3.

PSO solution.

Note that these movements are guided by the velocity parameter, which takes in our case a discrete value. Thus, we redefine (9) as follows: $\begin{matrix} (11) & V_{t + 1}^{p} = ⌊ ω . V_{t}^{p} + C_{1} r_{1} (L_{t}^{p} - X_{t}^{p}) + C_{2} r_{2} (G_{t} - X_{t}^{p}) ⌋ \end{matrix}$ where $⌊ \cdot ⌋$ is the floor function. Then, $\begin{matrix} (12) & X_{t + 1}^{p} = (X_{t}^{p} + V_{t + 1}^{p}) mod max_p \end{matrix}$ The function $mod$ ensures that the new position is in the range of $max_p$ possible positions/angles. The Algorithm 2 will take some fitness function f as input and will return the optimal positions along with orientations. The fitness function for this problem for any particle is defined as number of sensors effectively covering targets $f (X_{t}) = # sens$ at which we add a penalty as follows: $\begin{matrix} f (X_{t}) = # sens + L (card (T) - #cov_targs (X_{t})) \end{matrix}$ Such L is a large constant, and $#cov_targs (X_{t})$ , the number of covered targets. Note that if $#cov_targs (X_{t}) = card (T)$ , the penalty will be cancelled out. This penalty is added to distinguish between two solutions with the same sensor number, in this case, number of covered targets will determine the fittest one. L will be the factor of penalty and $L = card (T)$ will be a sufficient value.

Algorithm 2:

Proposed PSO algorithm

The stopping criteria corresponds to the situation where the velocity became near zero value ( $⩽ ε$ ).

Note that our fitness function f will be reused to evaluate solutions in the other metaheuristic methods (GA and SA), such we can compare these methods.

5.3. Simulated annealing algorithm

This method was developed in the mid 1980’s by various researchers [15]. It consists on generating initially a random solution, then to switch from one to another. A new solution is selected if it improves the objective function. Otherwise, this solution may be selected with a probability calculated as follows: $\begin{matrix} (13) & P (T, new_sol, sol) = exp (\frac{Δ E}{T}) \end{matrix}$ where $Δ E = f (sol) - f (new_sol)$ , gives the amount of fitness variations and T is a temperature parameter. We note that this algorithm is mostly inspired from a process of cooling molten metal. We have to cool the metals very slowly to get a strong crystal ( $Decrease (T)$ ). The process is repeated after a fixed iteration accomplished.

Algorithm 3:

Proposed SA algorithm

The $Move$ function in Algorithm 3 gives a new solution from the current one by operating a displacement/rotation. We then evaluate the fitness function and accept the new solution with the probability described above.

Algorithm 4:

Proposed GA algorithm

5.4. Genetic algorithm

A genetic algorithm (GA) is a metaheuristic population-based optimization method [20]. GA starts with a random population of $GA_size$ possible solutions, on which it applies some natural evolution operators (Crossover and Mutation) to obtain a new solution. The process is repeated until some satisfied criteria is reached (maximum iterations) [10]. Algorithm 4 shows a pseudo code for such method. We define $GA_size$ to be the size of the initial population, β as the percentage of selected parents to crossover and γ rate of mutation according to $P_{mut}$ (Table 2). The genetic operators used in this paper are defined below: Selection

Roulette-wheel method, i.e. β fittest solution (most probably chosen) from the initial $GA_size$ population.

Crossover

The single crossover point was adapted i.e tow parents are selected, from which we define a crossover point, and swap genotypes of both parents to generate tow new child.

Mutation

Perturb a solution (displace or rotate a camera) within γ rate of mutation and $P_{mut}$ mutation’s probability.

Replacement

replace old members by new fittest one.

After all, we get now, five approaches to handle the problem. One exact solution (MILP formulation), one greedy method and three metaheursitics based methods (PSO, SA and GA). This exact solution will guide us judge the quality of the solution obtained by those approximated methods, thus why we conduct next experiments.

6. Experiments and results

We discuss in this section a number of numerical experiments related to our different approaches. First, the most important parameter to define in order to implement our metaheuristics, is the solution coding or representation.

Each solution is encoded directly where the vector X represents camera positions and angles (Fig. 3). This coding solution was adopted for the three methods (PSO, GeA, SiA). Given $M_{ang} = card (M)$ , the number of all possible orientations for angle $m_{i} \in M$ , and for each position $n_{i} \in N$ , the corresponding encoding is given by $x_{i} = n_{i} M_{ang} + m_{i}$ . By this equation we have only to save vectors of such numbers, which combine the two informations (position and angle). A solution’s vector X has a size equal to $\hat{n}$ .

The experiments were executed on a computer with Intel^® Core™ i5-2400 CPU @ 3.10 GHz × 4 and 8.0 GB of RAM. We summarizes in Table 2 the main parameters used to implement different methods.

Table 2
Approaches parameters

Parameters Values

$C = 100.0$ , $W_{d} = 50$ , $α = \frac{π}{4}$

PSO ω 0.6

$C_{1}$ , $C_{2}$ 1.4

$swarm_size$ 40

SiA Temperature 1000.0

GeA $g a_size$ [50, 200]

β 10%

γ 3%

$P_{mut}$ 0.04

	Parameters	Values
$C = 100.0$ , $W_{d} = 50$ , $α = \frac{π}{4}$
PSO	ω	0.6
$C_{1}$ , $C_{2}$	1.4
$swarm_size$	40
SiA	Temperature	1000.0
GeA	$g a_size$	[50, 200]
β	10%
γ	3%
$P_{mut}$	0.04

Figures 4(a)–4(e) depict examples of the solutions determined by our five approaches on a problem instance of 20 targets spread over area of 100 × 100 possible locations.

Fig. 4.

Illustrations of: (a) Cplex solution; (b) PSO solution; (c) Greedy solution; (d) SA solution; (e) GA solution.

To experiment the impact of δ on found solutions, we solve by our exact approach ten (10) instances of a 50 targets spread over 100 × 100 area with $δ = {0.0, 0.0652, 0.1, 0.2, 0.3}$ , $δ = 0.0$ , means that we relax the quality constraint. From Fig. 5 we can clearly see that the increase of the quality increase linearly the number of sensors involved in the solution. This is due to the fact that the increase of δ enforce camera’s to move close to targets to assume the prescribed level of quality. The model with these quality constraint become more harder to solve due to numerical constraints added.

Fig. 5.

Sensors found by CPX for different qualities.

Next, we solve 4 sets of problem instances with 50, 100, 150 and 200 targets, respectively, using also the five methods. For each instances, we experimented two grid scenarios: Grid1 (50 × 50) and Grid2 (100 × 100). For each scenario, we solve by the five approaches ten (10) instances of the problem.

All over these experiments we refer to the exact method by CPX, the greedy one by GRD, GiA for the genetic algorithm, SiA for the simulated annealing method and PSO refer to the PSO approach. As can be seen from Fig. 6(a) and 6(b), the solution returned by the GRD Algorithm is the closest to the optimal one given by CPX for instances having 50 or less targets. It performs even better than PSO. However, From 100 targets and moreover PSO does better than the other metaheuristics. Figures 7(a) and 7(b) confirm that all over configurations, PSO has the closest behaviour to the exact CPX method. Box plot for either CPX and PSO for all targets (50,100,150 and 200) are ranging in nearly same values better than GRD. GeA and SiA has almost similar look. On another hand, Tables 3 and 4 summarizes the computational performances of the 5 approaches. A first observation is that GeA and SiA are much faster than the other at the price of lower solution quality. The best compromise between computation time and solution quality is achieved by PSO. This is particularly true for large problem instances.

Fig. 6.

Sensors found by different approaches on: (a) Grid 1 (50 × 50) (b) Grid 2 (100 × 100).

Fig. 7.

Sensors found by different approaches on: (a) Grid 1 (50 × 50) (b) Grid 2 (100 × 100).

Table 3

Times $(s)$ execution (50 and 100 targs) for methods on Grid1

$# 50$					$# 100$

CPX	GRD	SiA	GeA	PSO	CPX	GRD	SiA	GeA	PSO
36.65	3.67	0.12	0.63	1.67	49.74	111.24	0.49	5.53	9.88
101.11	3.20	0.14	0.57	2.03	49.82	67.96	0.52	5.79	12.59
65.95	9.36	0.13	0.58	0.90	62.26	33.06	0.50	5.39	9.43
103.97	3.39	0.13	0.56	1.63	57.99	26.24	0.50	5.09	11.22
249.08	4.15	0.13	0.60	1.57	54.29	89.88	0.50	6.34	12.88
99.74	4.33	0.10	0.69	1.88	65.94	46.44	0.51	5.67	10.82
241.65	3.94	0.13	0.57	1.09	79.22	82.75	0.50	5.77	11.69
227.37	4.61	0.13	0.64	2.41	69.08	40.34	0.46	5.71	13.72
90.14	4.87	0.14	0.60	1.66	53.30	29.29	0.44	5.94	11.54
125.79	3.67	0.13	0.57	1.55	45.12	98.95	0.49	5.68	9.65

Table 4

Times $(s)$ execution (150 and 200 targs) for methods on Grid2

$# 150$					$# 200$

CPX	GRD	SiA	GeA	PSO	CPX	GRD	SiA	GeA	PSO
613.30	1008.69	1.33	23.14	133.33	331.55	4225.45	2.76	60.08	304.50
324.76	1052.03	1.27	21.62	127.33	325.34	6844.17	2.74	59.72	302.83
379.24	509.54	1.29	20.76	135.24	385.72	5841.31	2.85	56.47	284.40
1414.12	2214.69	1.29	21.72	135.37	1174.23	4733.51	2.84	56.06	286.16
803.44	1511.55	1.29	22.84	129.60	338.19	2080.72	2.78	61.12	342.49
873.50	1170.91	1.29	22.51	131.50	513.67	3580.72	2.67	55.36	287.92
1101.33	1693.92	1.28	22.52	131.79	337.85	2755.93	2.74	60.23	298.97
770.95	561.73	1.34	21.54	133.62	332.81	6924.91	2.71	53.09	274.55
3509.43	2055.67	1.29	23.67	138.21	506.92	2745.50	2.80	65.84	302.85
365.91	1587.12	1.26	20.65	126.84	342.86	4865.16	2.68	56.23	303.40

In another set of experimentations, we seek to determine the impact of the grid size, which corresponds to the number of possible camera location per area unit; on the solution quality. To do so, we consider two scenarios with 50 and 200 targets, respectively, uniformly spread over an area of 400 × 400 m² (named IG50 and IG200, respectively). We evaluate both the mean number of cameras and computation time over 10 instances for each scenario. The results, depicted in Fig. 8(b)), show that CPX and PSO approaches are the more sensitive to grid (ranging from 75,85 to 55,72 cameras). As expected, as the grid density increases, the number of required cameras decreases as additional camera locations are available. It is worth to mention that GRD is not very sensible to this refinement in contrast to SiA and GeA. This is mainly due to the algorithm, since increased positions will cause the approach to explore more possibilities to maximize targets and this method is position-dependant. This changing is less important from Fig. 8(a) and PSO solutions were more accurate (the nearest sensor’s number found). Notice also that PSO behave as well as the CPX exact solution (both graphs have almost the same curve).

We can conclude that even if GeA and SiA are not as efficient than the other methods, one can design a hybrid approach where these two methods are used to provide in a timely manner good initial solutions than can feed CPX or PSO in a second stage.

Fig. 8.

Impact of grid refinement: (a) 50 targets, (b) 200 targets.

7. Conclusion

We studied in this paper the problem of cost-effective deployment of visual sensor networks. To this end, we first formulated the problem as a mixed-integer linear program where the objective is to minimize the number of deployed cameras subject to coverage and quality constraints. As the problem is NP-hard in general, we further designed a number of metaheuristic-based algorithm methods with the aim to obtain high quality solutions in a reasonable amount of time. Experimental results exhibited that the PSO-based algorithm achieved the best compromise between CPU time and objective quality. The results illustrated also the impact of grid density, to some extent the targets can be covered by less cameras at the price of higher computational cost. As future work, we plan to extend our model to consider connectivity and energy-efficiency constraints.

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.