## 5 Performance Analysis  
In order to evaluate and to compare the performance of our Tabu Search approach deployment method, we implemented our proposal and the deployment strategies found in the literature, namely: Random, Grid, Min_Miss[9], Max_Min_Cov[8], Max_Avg_Cov[8], Diff-Deploy[10], and DAA[11]. The comparison is based on different metrics as number of sensors deployed, satisfaction rate in detection probabilities \(\theta\) (percentage of area units receiving a detection probability larger or equal than the requested event detection probability threshold), computational complexity, memory consumption, and network communication connectivity. We compare the deployment methods in two stages. Initially, we focus the comparison on all the metrics introduced bellow except network connectivity. Afterwards, the comparison will include the network connectivity. We fixed sensor parameters values, \(\alpha\), \(\beta\), \(R_{max}\), and \(R_{c}\) to \(1\), \(1\), \(5\), and \(3\) respectively. We chose \(R_{c}\) less than \(\sqrt{3}R_{max}\) in order to illustrate how our deployment algorithm can ensure and build the connectivity with a small connectivity range. We remainder that if \(R_{c}\) is greater than \(\sqrt{3}R_{max}\), the sufficient condition to guarantee the connectivity is the full coverage of deployment area. We considered an area with \(50*50\) units. The required detection probabilities thresholds are illustrated in Figure 2, they vary from \(0.2\) to \(0.9\). For a regular deployment we chose a grid topology, so the shape is rectangle. In Mesh method, we chose the triangle shape for meshes. To divide a mesh, we placed a new sensor in the middle of one given arc. The cost function is the miss detection probabilities rate, it is equal to \((1-\theta)\). We calibrated the Tabu search process by fixing the number of iterations, the size of the Tabu list and the size of neighborhood explored to \(100\), \(10\), and \(15\) respectively. We fixed a confidence level for results of stochastic deployment strategies (Tabu Search and Random) to \(99.70\%\). Figure 3 shows the deployed sensors positions obtained by our Tabu Search approach. The num  
Figure 2: Area 50*50 with its desired detection probability valuesber of deployed sensors is equal to \(234\pm 2\) sensors, for a satisfaction rate \(\theta\) is equal to \(97.10\pm 0.24\%\). For the same number of sensors, \(234\), the satisfaction rate obtained when using the Random, Grid, Min_Miss,Max_Min_Cov,Max_Avg_Cov,Diff-Deploy, and DDA approaches are equal to \(73.45\pm 1.06\%\), \(83.12\%\), \(85.88\%\), \(83.36\%\), \(82.56\%\), \(96.72\%\), and \(93.24\%\) respectively. However, to reach the satisfaction rate obtained by the Tabu Search approach (\(97.10\%\)), in table 1 we show the minimal number of sensors that above deployment strategies must deploy. We can notice from the above results that our proposal Tabu Search and Diff-Deploy reduce highly the number of deployed sensors while improving the satisfaction rate. But the computational complexity of Diff-Deploy is equal to \(O(\frac{4}{3}n^{6})\) is larger than the computational complexity of our proposal Tabu Search which is equal to \(O(a.n^{2})\). Also the memory consumption in Diff-Deploy \begin{table}
\begin{tabular}{|c|c|} \hline \hline Deployment strategy & Number of sensors \\ \hline \hline Random & 570 \\ \hline \hline Grid & 540 \\ \hline \hline Min\_Miss & 351 \\ \hline \hline Max\_Min\_Cov & 385 \\ \hline \hline Max\_Avg\_Cov & 524 \\ \hline \hline Diff-Deploy & 235 \\ \hline \hline DDA & 251 \\ \hline \hline Tabu Search & 234 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Number of deployed sensors to reach \(97.10\%\) of satisfaction rate  
Figure 3: Tabu Search approach: Sensors positions  
is more important than the memory consumed in Tabu Search, because Diff-Deploy manipulates square matrix with \(n^{4}\) elements. DDA method gives also a satisfactory result but is more complex (\(O(n^{6})\)) than Tabu Search.