Michel - Still some points to be checked in section 5.2

[LiCO.git] / PeCO-EO / reponse.tex

diff --git a/PeCO-EO/reponse.tex b/PeCO-EO/reponse.tex
index ff5a80ce947dbd71d43ca51b9a4cbae0a0cafe71..b00dd1d194dfe02e47b11e0a3069363f5fb1e3f4 100644 (file)
--- a/PeCO-EO/reponse.tex
+++ b/PeCO-EO/reponse.tex
@@ -101,9 +101,9 @@ s used are very vague and do not bring out their key contributions. Some referen
 
 \noindent {\bf 8.}  Since this paper is attacking the coverage problem, I would like to see more information on the amount of coverage the algorithm is achieving. It seems that there is a tradeoff in this algorithm that allows the network to increase its lifetime but does not improve the coverage ratio. This may be an issue if this approach is used in an application that requires high coverage ratio.   \\
 
 
 \noindent {\bf 8.}  Since this paper is attacking the coverage problem, I would like to see more information on the amount of coverage the algorithm is achieving. It seems that there is a tradeoff in this algorithm that allows the network to increase its lifetime but does not improve the coverage ratio. This may be an issue if this approach is used in an application that requires high coverage ratio.   \\
 

-\textcolor{blue}{\textbf{\textsc{Answer:}  Your remark is interesting. Indeed, figures 8(a) and (b) highlight this result. PeCO methods allows to achieve a coverage ratio greater than $50\%$ for many more periods than the others three methods, but for applications requiring an high level of coverage (greater than $95\%$), DilCO method is more efficient.                                 }}\\
+\textcolor{blue}{\textbf{\textsc{Answer:}  Your remark is interesting. Indeed, figures 8(a) and (b) highlight this result. PeCO methods allows to achieve a coverage ratio greater than $50\%$ for many more periods than the others three methods, but for applications requiring an high level of coverage (greater than $95\%$), DilCO method is more efficient. It is explained at the end of section 5.2.4.                                }}\\

 
 

-%%%%%%%%%%%%%%%%%%%%%%  ENGLISH and GRAMMER %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%  ENGLISH and GRAMMAR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 
 \noindent\textcolor{black}{\textbf{\Large English and Grammar:}} \\
 
 
 \noindent\textcolor{black}{\textbf{\Large English and Grammar:}} \\
 


@@ -170,7 +170,7 @@ The paper entitled "Perimeter-based Coverage Optimization to Improve Lifetime in
 
 \noindent {\bf 3.} Page 9, the major problem with the present paper is, in my opinion, the objective function of the Mixed Integer Linear Program (2). It is not described in the paper, and looks like an attempt to address a multiobjective problem (like minimizing overcoverage and undercoverage). However, using a weighted sum is well known not to be an efficient way to address biobjective problems. The introduction of various performance metrics in Section 5.1 also suggests that the authors have not decided exactly which objective function to use, and compare their protocols against competitors without mentioning the exact purpose of each of them. If the performance metrics list given in Section 5.1 is exhaustive, then the authors should mention at the beginning of the paper what are the aims of the protocol, and explain how the protocol is built to optimize these objectives.  \\
 
 
 \noindent {\bf 3.} Page 9, the major problem with the present paper is, in my opinion, the objective function of the Mixed Integer Linear Program (2). It is not described in the paper, and looks like an attempt to address a multiobjective problem (like minimizing overcoverage and undercoverage). However, using a weighted sum is well known not to be an efficient way to address biobjective problems. The introduction of various performance metrics in Section 5.1 also suggests that the authors have not decided exactly which objective function to use, and compare their protocols against competitors without mentioning the exact purpose of each of them. If the performance metrics list given in Section 5.1 is exhaustive, then the authors should mention at the beginning of the paper what are the aims of the protocol, and explain how the protocol is built to optimize these objectives.  \\
 

-\textcolor{blue}{\textbf{\textsc{Answer:}  As far as we know, representing the objective function as a weighted sum of criteria to be minimized in case of multicriteria optimization is a classical method.                                        }}\\
+\textcolor{blue}{\textbf{\textsc{Answer:}  Right. The mixed Integer Linear Program adresses a multiobjective problem, where the goal is to minimize overcoverage and undercoverage for each coverage interval for each sensor. As far as we know, representing the objective function as a weighted sum of criteria to be minimized in case of multicriteria optimization is a classical method. In section 5, the comparison of protocols with a large variety of performance metrics allows to select the most appropriate method according to the QoS requirement of the application.                                       }}\\

 
 
 \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.    \\


@@ -178,20 +178,21 @@ The paper entitled "Perimeter-based Coverage Optimization to Improve Lifetime in
 \textcolor{blue}{\textbf{\textsc{Answer:}
 To implement PeCO on real sensors nodes with limited memories capacities, we can act on :
 \begin{itemize}
 \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:\\
+\item the solver : GLPK is memory consuming for the resolution of integer programming (IP) compared with other commercial solvers like CPLEX\textregistered. Commercial solvers generally outperform open source solvers  (See the report : "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
+\textregistered 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 (B \& B 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}
 \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.
+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 coverage interval. The following table gives the memory use 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 use with CPLEX\textregistered  to solve the LP-relaxation according to the number of constraints.

 \\
 \\

-\begin{tabular}{|c|c|c|c|c|c|}
+\begin{tabular}{|c|c|c|c|c|c|r|}

 \hline
 \hline

-Total number of nodes& S & I & GLPK IP & GLPK LP & number of nodes in the &CPLEX\\
-of nodes &&&&relaxation &branch-and-bound tree &\\
+Total number & S & I & GLPK IP & GLPK LP & nodes&CPLEX\\
+of nodes &&&&relaxation &B\&B tree &\\

 \hline
 100 & 6.25& 5&0.2 Mb & 0.2 Mb &1 &  64 Kb\\
 \hline
 \hline
 100 & 6.25& 5&0.2 Mb & 0.2 Mb &1 &  64 Kb\\
 \hline


@@ -200,13 +201,9 @@ of nodes &&&&relaxation &branch-and-bound tree &\\
 300 &18.5 & 17&3.6 Mb & 3.5 Mb & 3 &644 Kb\\
 \hline
 \end{tabular}
 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
-
+\\
+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 that the memory use with CPLEX\textregistered 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 solutions (Reference : "A feasibility pump heuristic for general mixed-integer problems", Livio Bertacco and Matteo Fischetti and Andrea Lodi, Discrete Optimization, issn 1572-5286).
+\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  coverage intervals).  

 \end{itemize}}}\\
 
 
 \end{itemize}}}\\
 
 


@@ -217,7 +214,7 @@ It is noteworthy that the difference of memory used with GLPK between the resolu
 
 \noindent {\ding{90} Page 12, lines 7-15, the authors mention that DiLCO protocol is close to PeCO. This should be mentioned earlier in the paper, ideally in Section 2 (Related Literature), along with the detailed description of DESK and GAF, the competitors of the proposed protocol, PeCO.  }  \\
 
 
 \noindent {\ding{90} Page 12, lines 7-15, the authors mention that DiLCO protocol is close to PeCO. This should be mentioned earlier in the paper, ideally in Section 2 (Related Literature), along with the detailed description of DESK and GAF, the competitors of the proposed protocol, PeCO.  }  \\
 

-\textcolor{blue}{\textbf{\textsc{Answer:}       }}.\\
+\textcolor{blue}{\textbf{\textsc{Answer:} Right. This observation has been added at the end of the introduction}}.\\

 
 
 
 
 
 


@@ -266,7 +263,7 @@ It is noteworthy that the difference of memory used with GLPK between the resolu
 
 \noindent {\ding{90}  Page 7, line 20 "regular homogeneous subregions" is too vague. }  \\
 
 
 \noindent {\ding{90}  Page 7, line 20 "regular homogeneous subregions" is too vague. }  \\
 

-\textcolor{blue}{\textbf{\textsc{Answer:} As mentioned in the previous remark, the spatial subdivision was not clearly explained in the paper. We added a discussion about this question in the article. Thank you for highlighting it. A FAIRE          }}.\\
+\textcolor{blue}{\textbf{\textsc{Answer:} As mentioned in the previous remark, the spatial subdivision was not clearly explained in the paper. We added a discussion about this question in the article. Thank you for highlighting it. }}.\\

 
 
 \noindent {\ding{90}   Page 7, line 24, replace "figure 4" with "Figure 4"}  \\
 
 
 \noindent {\ding{90}   Page 7, line 24, replace "figure 4" with "Figure 4"}  \\