## 4 Proposal: Tabu Search Approach
### Resolution without communication connectivity constraint
During the \(n^{th}\) iteration of the neighborhood exploration stage, a given number \(V\) of possible neighbors of the solution selected in the previous iteration, noted \(s_{n-1}\), are generated and evaluated. Neighboring solutions are possible solutions which can be reached from \(s_{n-1}\) by a basic transformation. Solutions which are present in the Tabu List \(T\) are considered unreachable neighbors. We propose two neighboring generation methods, namely **Suppression oriented stage** (\(H_{supp}\)) and **Additional oriented stage** (\(H_{add}\)). These two methods alternate in the successive iterations of our Tabu Search approach in order to determine the set \(V\). Both stages are detailed hereafter. * _Suppression oriented stage (\(H_{supp}\)):_ The aim of this stage is to suppress some sensors among those deployed in over-covered areas. The method proceeds with the following steps:
* **Step 1':*
* Compute the Bernoulli parameters for all \(p_{(x,y)}\in\mathcal{A}\) using the equation 4 and assuming the deployment obtained in the last Tabu Search iteration. \[\beta_{(x,y)}=\frac{1}{\|E_{(x,y)}\|}\sum_{(i,j)\in E_{(x,y)}}[(1-\frac{r_{( i,j)}}{\mathcal{P}_{(i,j)}})\times 1_{\{r_{(i,j)}<\mathcal{P}_{(i,j)}\}}]\] (4)
* **Step 2':*
* Generate a list, \(L_{supp}\), including all the points of \(\mathcal{A}\) where a sensor is deployed (\(D(x,y)=1\)). The list is then decreasingly sorted according to the resulting Bernoulli parameters. * **Step 3':*
* In \(L_{supp}\), select and remove the point \(p_{(x,y)}\) with the highest Bernoulli parameter, and randomly generated the decision to suppress the sensor in \(p_{(x,y)}\) through a Bernoulli decision rule with parameter \(\beta_{(x,y)}\). * **Step 4':*
* If the Bernoulli decision is to suppress the sensor (\(D(x,y)=0\)), then the probabilities of detection for all points in the vicinity of \(p_{(x,y)}\) are recomputed. In this case, the list \(L_{supp}\) is updated (sorted) with the new values of the Bernoulli parameters associated to each point in \(L_{supp}\). * **Step 5':*
* If \(L_{supp}\) is not empty, go back to **Step 3'**. Once the stop criteria on step 5' is satisfied, the next Tabu Search iteration alternates toward an additional stage. * _Additional oriented stage (\(H_{add}\)):_ The aim of this stage is to add more sensors to the actual deployed ones in under-covered areas. The execution is very similar to the initialization stage, except **Step 1*
* and **Step 2*
* are replaced by the following steps:
* **Step 1\":*
* Compute the Bernoulli parameters for all \(p_{(x,y)}\in\mathcal{A}\) using the equation 3 and assuming the deployment obtained in the last Tabu Search iteration. * **Step 2\":*
* Generate a list \(L_{add}\) including all the points of \(\mathcal{A}\) where a sensor is not deployed. The list one is then decreasingly sorted according to the resulting Bernoulli parameters. Steps 3, 4 and 5, as detailed in initialization stage, are repeatedly executed until that the list \(L_{add}\) is empty. 3. _Cost function and selection of new solution_ After the neighborhood exploration (a suppression or an additional oriented stage) during the \(n^{th}\) iteration, an elected solution \(s_{n}\) must be chosen among the \(V\) explored candidates. This solution (which cannot be in the Tabu list \(T\)) is the one which provided by minimizing a given cost function \(F\). The cost function reflects two objectives of the optimization problem described in section 3.2., minimize the number of deployed sensors and reduce the gap between the generated and requested event detection probabilities. The first objective could be quantified by counting the number of deployed sensors. Formally, as defined in section \(D(x,y)=1\), if a sensor is deployed in the point \(p_{(x,y)}\). Otherwise, \(D(x,y)=0\).