avec reponse

diff --git a/PeCO-EO/reponse.tex b/PeCO-EO/reponse.tex
index 1b8643c4e80224a99eea5f3557125d1d68d75050..ff5a80ce947dbd71d43ca51b9a4cbae0a0cafe71 100644 (file)
--- a/PeCO-EO/reponse.tex
+++ b/PeCO-EO/reponse.tex
@@ -82,7 +82,7 @@ adding some information about these values, since without it, you cannot underst
 \noindent {\bf 5.} Can you mathematically justify how you chose the values of alpha and beta? This is not
 very clear. I would suggest possibly adding more results showing how the algorithm performs with different alphas and betas.  \\
 
 \noindent {\bf 5.} Can you mathematically justify how you chose the values of alpha and beta? This is not
 very clear. I would suggest possibly adding more results showing how the algorithm performs with different alphas and betas.  \\
 

-\textcolor{blue}{\textbf{\textsc{Answer:} The choice of alpha and beta should be made according to the needs of the application. alpha should be enough large to prevent undercoverage and so to reach the highest possible coverage ratio. beta should be enough large to prevent overcoverage and so to activate a minimum number of sensors. The values of $\alpha_{i}^{j}$ can be identical for all coverage intervals $i$ of one sensor $j$ in order to express that the perimeter of each sensor should be uniformly covered, but  $\alpha_{i}^{j}$ values can be differenciated between sensors to force some regions to be better covered than others. The choice of $\beta \gg \alpha$  prevents the overcoverage, and so limit the activation of a large number of sensors, but as $\alpha$ is  low, some areas may be poorly covered. This explains the results obtained for {\it Lifetime50} with $\beta \gg \alpha$: a large number of periods with low coverage ratio. With $\alpha \gg \beta$, we priviligie the coverage even if some areas may be overcovered, so high coverage ratio is reached, but a large number of sensors are activated to achieve this goal. Therefore network lifetime is reduced. The choice $\alpha=0.6$ and $\beta=0.4$ seems to achieve the best compromise between lifetime and coverage ratio.                }}\\
+\textcolor{blue}{\textbf{\textsc{Answer:} The choice of alpha and beta should be made according to the needs of the application. Alpha should be enough large to prevent undercoverage and so to reach the highest possible coverage ratio. Beta should be enough large to prevent overcoverage and so to activate a minimum number of sensors. The values of $\alpha_{i}^{j}$ can be identical for all coverage intervals $i$ of one sensor $j$ in order to express that the perimeter of each sensor should be uniformly covered, but  $\alpha_{i}^{j}$ values can be differenciated between sensors to force some regions to be better covered than others. The choice of $\beta \gg \alpha$  prevents the overcoverage, and so limit the activation of a large number of sensors, but as $\alpha$ is  low, some areas may be poorly covered. This explains the results obtained for {\it Lifetime50} with $\beta \gg \alpha$: a large number of periods with low coverage ratio. With $\alpha \gg \beta$, we priviligie the coverage even if some areas may be overcovered, so high coverage ratio is reached, but a large number of sensors are activated to achieve this goal. Therefore network lifetime is reduced. The choice $\alpha=0.6$ and $\beta=0.4$ seems to achieve the best compromise between lifetime and coverage ratio.                }}\\

 
 
 
 
 
 


@@ -175,7 +175,39 @@ The paper entitled "Perimeter-based Coverage Optimization to Improve Lifetime in
 
 \noindent {\bf 4.}Page 11 Section 5.2, the sensor nodes are said to be based on Atmels AVR ATmega103L microcontroller. If I am not mistaken, these devices have 128 KBytes of memory, and I didn't find any clue that they can run an operating system like Linux. This point is of primary importance for the proposed protocol, since GLPK (a C API) is supposed to be executed by the cluster leader. In addition to that, GLPK requires a non negligible amount of memory to run properly, and the Atmels AVR ATmega103L microcontroller might be insufficient for that purpose. The authors are urged to provide references of previous works showing that these technical constraints are not preventing their protocol to be implemented on the aforementioned microcontroller. Then, on page 13, in Section "5.2.3 Energy Consumption", the estimation of $E_p^{com}$ for the considered microcontroller seems quite challenging and should be carefully documented. Indeed, this is a key point in providing a fair comparison of PeCO with its competitors.    \\
 
 
 \noindent {\bf 4.}Page 11 Section 5.2, the sensor nodes are said to be based on Atmels AVR ATmega103L microcontroller. If I am not mistaken, these devices have 128 KBytes of memory, and I didn't find any clue that they can run an operating system like Linux. This point is of primary importance for the proposed protocol, since GLPK (a C API) is supposed to be executed by the cluster leader. In addition to that, GLPK requires a non negligible amount of memory to run properly, and the Atmels AVR ATmega103L microcontroller might be insufficient for that purpose. The authors are urged to provide references of previous works showing that these technical constraints are not preventing their protocol to be implemented on the aforementioned microcontroller. Then, on page 13, in Section "5.2.3 Energy Consumption", the estimation of $E_p^{com}$ for the considered microcontroller seems quite challenging and should be carefully documented. Indeed, this is a key point in providing a fair comparison of PeCO with its competitors.    \\
 

-\textcolor{blue}{\textbf{\textsc{Answer:}                                              }}\\
+\textcolor{blue}{\textbf{\textsc{Answer:}
+To implement PeCO on real sensors nodes with limited memories capacities, we can act on :
+\begin{itemize}
+\item the solver : GLPK is memory consuming for the resolution of integer programming (IP) compared with other commercial solvers like CPLEX\texttrademark. Commercial solvers generally outperform open source solvers  (See "Analysis of commercial and free and open source
+solvers for linear optimization problems" by B. Meindl and M. Templ from Vienna University of Technology). Memory use depends on the number of variables and number of  constraints.  For linear programs (LP), a reasonable estimate of memory use with CPLEX\texttrademark is to allow one megabyte per thousand constraints. For integer programs, no simple formula exists since memory use depends so heavily on the size of the branch and bound tree. But, the estimate for linear programs still provides a lower bound. In our case, the characteristics of the integer programming (2) are the following:\\
+\begin{itemize}
+\item number of variables : $S* (2*I+1)$
+\item number of constraints : $2* I *S$
+\item number of non-zero coefficients : $2* I *S * B$
+\item number of parameters (in the objective function) : $2* I *S$
+\end{itemize}
+where $S$ denotes the number of sensors in the subregion, $I$ the average number of cover intervals per sensor, $B$ the average number of sensors involved in a cover interval. The following table gives the memory used with GLPK to solve the integer program (column 3) and its LP-relaxation (column 4) for different problem sizes. The sixth column gives an estimate of the memory used with CPLEX to solves the LP-relaxation according to the number of constraints.
+\\
+\begin{tabular}{|c|c|c|c|c|c|}
+\hline
+Total number of nodes& S & I & GLPK IP & GLPK LP & number of nodes in the &CPLEX\\
+of nodes &&&&relaxation &branch-and-bound tree &\\
+\hline
+100 & 6.25& 5&0.2 Mb & 0.2 Mb &1 &  64 Kb\\
+\hline
+200 & 12.5& 11&1.7 Mb & 1.6 Mb &1 & 281 Kb\\
+\hline
+300 &18.5 & 17&3.6 Mb & 3.5 Mb & 3 &644 Kb\\
+\hline
+\end{tabular}
+It is noteworthy that the difference of memory used with GLPK between the resolution of the IP and its LP-relaxation is very weak (not more than 0.1 Mb). The size of the branch and bound tree dos not exceed 3 nodes. This result leads one to believe the memory used with CPLEX for solving the IP would be very close to that for the LP-relaxation, that is to say around 100 Kb for a subregion containing $S=10$ sensors. Moreover the IP seems to have some specifities that encourage us to develop our own solver (coefficents matrix is very sparse) or to use an existing heuristic to find good approximate solution ().
+
+
+
+\item the subdivision of the region of interest. To make the resolution of integer programming tractable by a leader sensor, we need to limit the number of nodes in each subregion (the number of variables and constraints of the integer programming is directly depending on the number of nodes and neigbors). It is therefore necessary to adapt the subdvision  according to the number of sensors deployed in the area and their sensing range (impact on the number of  cover intervals).  
+\item heuristic
+
+\end{itemize}}}\\

 
 
 
 
 
 


@@ -250,7 +282,7 @@ The paper entitled "Perimeter-based Coverage Optimization to Improve Lifetime in
 
 \noindent {\ding{90}  Page 9, the constraints of the Mixed Integer Linear Program (2) are not numbered. There are two inequalities for overcoverage and undercoverage that are used to define Mij and Vij. Why not using replacing these inequalities by equalities? }  \\
 
 
 \noindent {\ding{90}  Page 9, the constraints of the Mixed Integer Linear Program (2) are not numbered. There are two inequalities for overcoverage and undercoverage that are used to define Mij and Vij. Why not using replacing these inequalities by equalities? }  \\
 

-\textcolor{blue}{\textbf{\textsc{Answer:}  In fact, replacing these inequalities by equalities does not impact the final result because of the structure of the integer programming. For minimizing the objective function, $M_{i}^{j}$ and $V_{i}^{j}$ should be set to the smallest possible value such that the inequalities are satisfied. It is explained in the answer 4 for the reviewer 1. So, at optimality, constraints are satisfied with equality. So, we thank for your remark and we changed it in the formulation, even if there is no incidence about the final result.}}\\
+\textcolor{blue}{\textbf{\textsc{Answer:}  For minimizing the objective function, $M_{i}^{j}$ and $V_{i}^{j}$ should be set to the smallest possible value such that the inequalities are satisfied. It is explained in the answer 4 for the reviewer 1. But, at optimality, constraints are not necessary satisfied with equality. For instance, if a sensor $j$ is overcovered, there exists at least one of its coverage interval (say $i$) for which the number of active sensors (denoted by $l^{i}$) covering this part of the perimeter is greater than $l$. In this case, $M_{i}^{j}=0$, $V_{i}^{j}=l^{i}-l$, the corresponding inequality $\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i  \geq l$ is a strict inequality since $\sum_{k \in A} ( a^j_{ik} ~ X_{k})=l^{i} > l$. }}\\

 
 \noindent {\ding{90}  Page 10, line 50, "or if the network is no more connected". In order to assess this, the communication range should be known, but it is not given in Table 2. }  \\
 
 
 \noindent {\ding{90}  Page 10, line 50, "or if the network is no more connected". In order to assess this, the communication range should be known, but it is not given in Table 2. }  \\