## 4 Proposal: Tabu Search Approach
### Resolution without communication connectivity constraint  
In this section we present our pseudo-random deployment algorithm based on Tabu Search heuristic. In this stage we do not take into account the communication network connectivity constraint in the deployment process. Connectivity and coverage are related, because they are affected by the sensors position. We assume that a communication range is so large, \(R_{c}\geq\sqrt{3}R_{\textit{max}}\), in aim to apply the result (necessary conditions to ensure the connectivity) proposed in [12]. Hence, we guarantee the WSN connectivity and we are focused only on the event detection probabilities constraints. 1. _Initialization_ The convergence of Tabu Search method depends on the judicious choice of the initial solution (\(s_{0}\)). Ideally, the first solution has to be close to the optimal one, otherwise, since the maximum number of iterations is fixed, the algorithm may stop before reaching the best solution. We consider that the decision, \(D(x,y)\), of deploying a sensor in a point \(p_{(x,y)}\) is a random variable, which follows a Bernoulli distribution with parameter \(\alpha_{(x,y)}\). The binary form of the decision rule motivates the choice of the Bernoulli law. Precisely, \(D(x,y)\) can assume a value of \(1\) with a probability of \(\alpha_{(x,y)}\) and the value of \(0\) with a probability of \((1-\alpha_{(x,y)})\). The parameter \(\alpha_{(x,y)}\), associated to a point \(p_{(x,y)}\), is chosen as the percentage of the points located in the vicinity of \(p_{(x,y)}\) and not receiving the required probabilities of detection. The vicinity, denoted \(E_{(x,y)}\), is defined as the set of neighbor points located inside the maximum monitoring circle of a sensor which would be placed in \(p_{(x,y)}\). Formally, \[\alpha_{(x,y)}=\frac{1}{\|E_{(x,y)}\|}\sum_{(i,j)\in E_{(x,y)}}1_{\{r_{(i,j)} >\mathcal{P}_{(i,j)}\}}\] (3) Here \(1_{\{\text{cond}\}}\) is the indicating function, which is equal to \(1\) if the condition cond is true and \(0\) otherwise. The initialization stage of our Tabu Search approach follows these steps: * **Step 1:** The initial Tabu Search solution is started assuming zero deployed sensors. Thus, \(\forall p_{(x,y)}\in\mathcal{A}\), Bernoulli parameters are computed using equation 3 with \(\mathcal{P}_{(x,y)}=0\). * **Step 2:** Generate a list, \(L_{init}\), including all points of \(\mathcal{A}\). \(L_{init}\) is a decreasingly sorted list of points according to their Bernoulli parameters. * **Step 3:** In \(L_{init}\), select the point \(p_{(x,y)}\) with the highest Bernoulli parameter, and remove it from the list. If the actual detection probability \(\mathcal{P}_{(x,y)}\) associated to \(p_{(x,y)}\) is lower than \(r_{(x,y)}\), then a decision to deploy a sensor in \(p_{(x,y)}\) is randomly generated through a Bernoulli decision rule with parameter \(\alpha_{(x,y)}\). * **Step 4:** If the Bernoulli decision is to deploy a sensor (\(D(x,y)=1\)), then _(1)_ the probabilities of detection for all points in the vicinity of \(p_{(x,y)}\) (the set \(E_{(x,y)}\)) are recomputed. and _(2)_\(L_{init}\) is updated (sorted). * **Step 5:** If \(L_{init}\) is not empty, go back to **Step 3**. When the stop criterion of step 5 is satisfied, the resulting positions of deployed sensors are considered as the initial solution \(s_{0}\). The latter one is saved in the algorithm's memory, called the Tabu List. In the remaining, we will refer to this list as \(T\). The goal of the Tabu list is not to block the method on a local minimum of the cost function. 2. _Neighborhood exploration function_ After the initialization stage, a Tabu Search method executes \(N\) times the neighborhood exploration stage. Here, \(N\) is a chosen fixed parameter, which must be set in order to limit the number of Tabu Search iterations and to obtain a satisfactory (near to the optimal) solution.