## 2 Related Works  
In the recent years, there have been many research activities and advances in sensor networks. However, a small number of them have addressed WSN deployment process. In the literature, we found some works which studied the deployment with a probabilistic detection model. Other works integrate the connectivity constraints but assume a binary detection model. To the best of our knowledge, no work have yet considered the deployment process including at the same time the network connectivity requirement, a probabilistic detection model, and a non-uniform event detection probabilities constraints. Earlier works such as [4; 5; 6] considered that the environment is unknown or that the area is inaccessible (e.g. a battle field). Consequently, random geographical sensors deployment is assumed. On the other hand, some works considered that sensors are likely to be deployed in a regular structured manner through hand placement (e.g. based on grid). Such approach is adapted to monitor a phenomenon with a sensing characteristic that is uniformly distributed in an area. [PERSON] and al. [7] used a binary detection model and presented a grid coverage strategy for effective surveillance and target location in distributed WSN. They have considered two types of sensors having with different characteristics (cost and range). Thereafter, they have considered an integer linear programming (ILP) approach to find the solution which minimizes the sensors's cost while ensuring the complete coverage of the studied area. Note that, although the ILP could lead to obtain exact resolution, this method will raise important computational complexity for realistic case studies (especially for large surface areas), since the problem under study is known to be NP-hard. In [8], the authors assumed a probabilistic detection model, which is expressed as an exponential function of the distance between the location of the targeted event and the sensor position. This model was considered in the proposal of two new deployment algorithms. Both approaches seek toward an optimal area coverage under the constraints of imprecise detections. The solutions are based on a grid structure. The first algorithm, _Max_Avg_Cov_, aims to maximize the average coverage of the grid points. The second one, _Max_Min_Cov_ aims to maximize the coverage of the grid points which are the least effectively covered. Both _Max_Avg_Cov_ and _Max_Min_Cov_ were initially designed for an area with uniform detection probability, however they can easily adapted in the case of an area with non-uniform detection probability. Unfortunately, the two strategies suffer from high computational complexity, it is equal to \(O(n^{4})\). In [9], the authors proposed a new deployment strategy called _Min-Miss_. This strategy is an iterative algorithm, one sensor is deployed at each step. The authors defined for each point, in the deployment field, a new metric named over miss probability. The later quantifies the benefit in coverage when a new sensor is added. The main idea of _Min-Miss_ is the following. At first, all possible free grid points (no sensors are deployed in these points) are selected to form a set. Thereafter, for each point of this set the authors compute the over miss probability metric. Finally, a new sensor is deployed at point that minimizes the over miss probability metric. That means, a sensor is deployed in a position that maximizes the event detection probabilities in the deployment field. The main drawback of this approach is the huge computational complexity of such operation, which is equal to \(O(n^{6})\). In [10], the authors addressed explicitly a WSN deployment problem for non-uniform detection requirement. As in [8], they propose to use a probabilistic detections model. They formulated the differentiated deployment problem as an integer linear programming deployment problem, which has been proved to be NP-hard. Finally, they propose a deployment heuristics, named _Diff_Deploy_.