## 4 Proposal: Tabu Search Approach
### Resolution without communication connectivity constraint
In order to minimize the cost function, \(F\) includes the following term: \[\sum_{(x,y)\in\mathcal{A}}D(x,y)\] (5) The second objective is integrated into the cost function through the following _penalty function_: \[Penalty=\sum_{(x,y)\in\mathcal{A}}\frac{\left[r_{(x,y)}-\mathcal{P}_{(x,y)} \right]^{+}}{r_{(x,y)}}\] (6) Here \(\left[r_{(x,y)}-\mathcal{P}_{(x,y)}\right]^{+}\) denotes the projection of \(r_{(x,y)}-\mathcal{P}_{(x,y)}\) in \(I\!\!R\ ^{+}\). Formally, \[\left[r_{(x,y)}-\mathcal{P}_{(x,y)}\right]^{+}=\left(r_{(x,y)}-\mathcal{P}_{(x,y)}\right)\times 1_{\{r_{(x,y)}>\mathcal{P}_{(x,y)}\}}\] (7) According to the expression of penalty function, a successful deployment solution should lead to obtain detection probabilities higher than (or ideally equal to) the required detection thresholds. If it is not satisfied, the penalty function value translates how far is the solution to the required thresholds. This is exactly the second objective of the optimization problem. From the above objective expressions, the authors define two cost functions \(F_{supp}\) and \(F_{add}\). The function \(F_{supp}\) is used to choose the best next iteration solution in the case of a _suppression oriented stage_. The function \(F_{supp}\) is formulated using only the equation 6. On the other hand, the cost function \(F_{add}\) is used in the case of _additional oriented stage_. In this case, the two both termsassociated to each objective of optimization problem are integrated into the cost function through the following additive expression:  
\[F_{add}=\sum_{(x,y)\in\mathcal{A}}\left[D(x,y)\right]+Penalty \tag{8}\]  
The pseudo code of Tabu search deployment process is illustrated in Algorithm 1. ```
Compute initial solution \(s_{0}\); \(s_{out}=s_{0}\);  bool sup-sensors = true;  Tabu-List = \(\{s_{0}\}\), set of \(T\) last solutions visited; for i=0 to \(N\)do  neighborhood = \(\O\); ifsup-sensors == truethen for j=1 to \(V\)do \(s_{i}^{j}\) = \(H_{supp}(s_{i})\);  neighborhood = neighborhood + \(\{s_{i}^{j}\}\);  Cost-Function \(=F_{supp}\); else for j=1 to \(V\)do \(s_{i}^{j}\) = \(H_{add}(s_{i})\);  neighborhood = neighborhood + \(\{s_{i}^{j}\}\);  Cost-Function \(=F_{add}\); for j=1 to \(V\)do if\(s_{i}^{j}\)\(\in\)Tabu-Listthen  neighborhood = neighborhood \(\backslash\{s_{i}^{j}\}\);  Select the best solution \(s_{i}^{best}\) in neighborhood, \(s_{i}^{best}\) minimizes the cost function;  Cost-Function \(\left(s_{i}^{best}\right)=min_{s_{i}^{j}\in neighborhood}\left[\text{ Cost-Function }\left(s_{i}^{j}\right)\right]\); \(s_{i+1}=s_{i}^{best}\); %update output solution \(s_{out}\)%; ifCost-Function \(\left(s_{i}^{best}\right)\) \(<\) Cost-Function \(\left(s_{out}\right)\)then \(s_{out}=s_{i}^{best}\); %update Tabu-List%;  Tabu-List = Tabu-List + \(\{s_{i}^{best}\}\); %Alternate between \(H_{supp}\) and \(H_{add}\)%;  sup-sensors = not(sup-sensors);
```  
**Algorithm 1**_Tabu search_ pseudo code  
The computational complexity of Tabu search is equal to \(O(NVm^{2}n^{2})\). \(N\) is the number of iterations of Tabu search process and \(V\) is the size of the neighborhood. These two parameters are chosen by the designer, they are calibrated according to the specific deployment scenario. A coverage circle of sensor covers a set of cells in the area, \(m\) represents the number of cells in length or width of sub-area covered by a sensor. \(m\) depends on the maximum radius circle \(R_{max}\), \(m\) is equal to \(\lceil\frac{R_{max}}{\sqrt{2}}\rceil\). We remark that the Tabu search complexity depends on the deployment area dimensions, detection characteristic of sensor (\(R_{max}\)), and parameters of Tabu Search algorithm (\(N\), \(V\)). If \(N\), \(V\) and \(m\) are not large, the product \(NVm^{2}\) is equal to constant \"a\", so we have a quadratic complexity \(O(a.n^{2})\).