Sensors_**2009**, \(9\), 1625-1643; doi:10.3390/s90301625  
**Sensors**  
**ISSN 1424-8220**  
www.mdpi.com/journal/sensors  
_Article_  
**A Tabu Search WSN Deployment Method for Monitoring Geographically Irregular Distributed Events**  
**[PERSON] \({}^{1,\star}\), [PERSON] \({}^{2}\), [PERSON] \({}^{2}\) and [PERSON] \({}^{1}\)**  
\({}^{1}\) LIP6, University Paris 6, 104 avenue [PERSON], 75016 Paris, France  
\({}^{2}\) L2 TI, University Paris 13, 99 [PERSON], 93430 Villetaneuse, France  
E-mails: [EMAIL_ADDRESS], nadjib.achir@l2 ti.univ-paris13.fr,  
khaled.boussetta@l2 ti.univ-paris13.fr, [EMAIL_ADDRESS]  
\({}^{\star}\) Author to whom correspondence should be addressed. _Received: 28 January 2009 / Accepted: 24 February 2009 / Published: 9 March 2009_  
**Abstract:** In this paper, we address the Wireless Sensor Network (WSN) deployment issue. We assume that the observed area is characterized by the geographical irregularity of the sensed events. Formally, we consider that each point in the deployment area is associated a differentiated detection probability threshold, which must be satisfied by our deployment method. Our resulting WSN deployment problem is formulated as a Multi-Objectives Optimization problem, which seeks to reduce the gap between the generated events detection probabilities and the required thresholds while minimizing the number of deployed sensors. To overcome the computational complexity of an exact resolution, we propose an original pseudo-random approach based on the Tabu Search heuristic. Simulations show that our proposal achieves better performances than several other approaches proposed in the literature. In the last part of this paper, we generalize the deployment problem by including the wireless communication network connectivity constraint. Thus, we extend our proposal to ensure that the resulting WSN topology is connected even if a sensor communication range takes small values. **Keywords:** Wireless Sensor Network Deployment; Differentiated detection; Connectivity; Tabu Search heuristic. Introduction  
Over the last decade, Wireless Sensor Networks (WSN) have generated a considerable enthusiasm from the networking researchers community. Many efforts have been produced in order to apply WSN to a wide range of applications, such as: environmental monitoring, military target tracking, weather forecast, home automation, intrusion detection, etc. Basically, a WSN is a collection of small resource-constrained devices, which are typically composed of sensing components, computer processor, memory chips, and radio interface for transmitting and receiving information. The sensors could collaborate in order to observe and report the events occurring in their environment. When an event is detected, this information is routed from one node to another (multi-hops communication) and eventually gathered in gateway nodes or base stations. While the set of challenges in wireless sensor networks are diverse, researchers have mainly focused their efforts on fundamental networking challenges, which include: routing protocols, energy minimization, sensor localization, data gathering, etc [1]. In this paper we address a static wireless sensor network deployment problem. The performances of proposed solutions related to the protocol stack depend strongly on the network deployment process. The latter one consists in determining the required number of sensors and their positions to satisfy a certain number of constraints. Classical constraints are: coverage, events reliable detection, connectivity, etc. In this paper, we relax some of the assumptions that were considered in the literature with the aim to formulate a more realistic WSN deployment problem. The first generalization concerns the detection model. Indeed, most of works regarding WSN deployment assume a _binary detection model_. In this paper, a sensor is supposed to surely detect (detection probability is equal to 1) an event if and only if the distance between the sensor and the event is less than a particular sensing range.