## 3 Problem Statement
### Problem Formalization  
We consider a sensor field area, denoted \(\mathcal{A}\). In order to reduce the computational complexity of the problem, the area is discretized. We suppose that \(\mathcal{A}\) is a square, with a side equals to \(n\) units. A unit is defined as a normalized physical distance (example, \(1\) meter or \(10\) meters). To simplify, we will refer in the rest of this paper, to each square unit of \(\mathcal{A}\) by its barycenter **point**. In other words, when we say that a sensor is located in the point \(p_{(i,j)}\in\mathcal{A}\) then this means that the sensor is placed in the barycenter of the corresponding square unit. Similarly, the event detection probability of a unit square is computed considering the event detection probability of its barycenter. Finally, we consider that any event occurring inside a unit square is surely detected (event probability equals to \(1\)) by a sensor which would be placed in its barycenter point. In an efficiently monitoring, the event detection is formalized as a probabilistic detection model. Each point \(p_{(i,j)}\) in \(\mathcal{A}\) is associated a required minimum probability detection threshold, denoted \(r_{(i,j)}\). Ideally, a successful WSN deployment algorithm should lead to obtain that \(\forall p_{(i,j)}\in\mathcal{A}\) the measured detection probability of that point is greater than \(r_{(i,j)}\), and the sensor graph of connectivity \(G\) is connected. The detection probability in a point \(p_{(i,j)}\) is estimated by all the sensors in its vicinity, but the  
Figure 1: Sensor detection model  
event detection model is not collaborative. The detection probability of the point \(p_{(i,j)}\), denoted \(\mathcal{P}_{(i,j)}\), is estimated by all the sensors available in the monitored area as  
\[\mathcal{P}_{(i,j)}=1-\prod_{(x,y)\in Grid}[1-P((i,j),(x,y))]^{D(x,y)} \tag{2}\]  
where \(D(x,y)\) denotes the deployment bivalent variable. If \(D(x,y)\) equals to \(0\) means that no sensor is deployed at grid point \(p(i,j)\). If \(D(x,y)\) equals to \(1\) means that a sensor is deployed at grid point \(p(x,y)\). Obviously, if a sufficiently large number of sensors are deployed, it is possible to satisfy the objective: \(\mathcal{P}_{(i,j)}\geq r_{(i,j)}\), \(\forall p_{(i,j)}\in\mathcal{A}\). Nevertheless, taking into account cost considerations, the number of sensors is also a critical metric. In addition to the satisfaction of the requirement on the minimum detection probability thresholds, a second objective in a deployment problem is to minimize the number of sensors. Formally, the aim is to find the best WSN topology to the following multi-objectives optimization problem:  
1. Minimize the number of deployed sensors needed to satisfy the following two constraints (2 and 3). 2. For each point \(p_{(i,j)}\in\mathcal{A}\), minimize the difference between the required detection probability threshold \(r_{(i,j)}\), and the after-deployment resulting detection probability \(\mathcal{P}_{(i,j)}\). 3. Ensure the wireless communication network connectivity. A multi-objectives optimization problem described above is NP-Hard problem. The size of the solution space is finite but very large (\(2^{n^{2}}\)). We remind that the deployment field is a square, with a side equals to \(n\) units. To resolve this optimization problem, we can choose an exact method as Branch & Bound [17] that provides an optimal deployment (solution). Unfortunately, we cannot apply it to large areas because of its exponential complexity. The second alternative is to resolve the problem by using heuristics. Inopportunely, these methods cannot guarantee to obtain the optimal solution. However, the main advantage is the polynomial complexity and the running time which can be reasonable. In this paper, we propose a pseudo-random algorithm based on Tabu Search heuristic. We resolve our multi-objectives optimization problem on two stages. Firstly, we address our problem by missing the connectivity constraint.