From: Michel Salomon Date: Fri, 26 Jun 2015 14:37:45 +0000 (+0200) Subject: Updates completed X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/LiCO.git/commitdiff_plain/27b71d0f349b075890c36c261dabbf78ef2f26d3?ds=sidebyside Updates completed --- diff --git a/PeCO-EO/articleeo.aux b/PeCO-EO/articleeo.aux index 9a891ae..378ac92 100644 --- a/PeCO-EO/articleeo.aux +++ b/PeCO-EO/articleeo.aux @@ -86,7 +86,6 @@ \bibcite{cardei2005improving}{{4}{2005}{{Cardei and Du}}{{}}} \bibcite{cardei2005energy}{{5}{2005}{{Cardei et~al.}}{{Cardei, Thai, Li, and Wu}}} \newlabel{my-labelx}{{4}{17}} -\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Acknowledgements}{17}} \bibcite{castano2013column}{{6}{2014}{{Casta{\~n}o et~al.}}{{Casta{\~n}o, Rossi, Sevaux, and Velasco}}} \bibcite{iamigo:cplex}{{7}{2010}{{CPLEX}}{{}}} \bibcite{Deng2012}{{8}{2012}{{Deng, Jiguo~Yu, and Chen}}{{}}} diff --git a/PeCO-EO/articleeo.log b/PeCO-EO/articleeo.log index 0b75357..a6a177f 100644 --- a/PeCO-EO/articleeo.log +++ b/PeCO-EO/articleeo.log @@ -1,4 +1,4 @@ -This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.1.24) 25 JUN 2015 22:43 +This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.1.24) 26 JUN 2015 16:36 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -1248,7 +1248,7 @@ s/type1/public/amsfonts/cm/cmsy8.pfb> -Output written on articleeo.pdf (19 pages, 746258 bytes). +Output written on articleeo.pdf (19 pages, 746265 bytes). PDF statistics: 213 PDF objects out of 1000 (max. 8388607) 145 compressed objects within 2 object streams diff --git a/PeCO-EO/articleeo.pdf b/PeCO-EO/articleeo.pdf index 5e5e642..e07fd5b 100644 Binary files a/PeCO-EO/articleeo.pdf and b/PeCO-EO/articleeo.pdf differ diff --git a/PeCO-EO/articleeo.tex b/PeCO-EO/articleeo.tex index 5f74aa3..e98acfc 100644 --- a/PeCO-EO/articleeo.tex +++ b/PeCO-EO/articleeo.tex @@ -17,7 +17,7 @@ \author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$$^{\ast}$\thanks{$^\ast$Corresponding author. Email: karine.deschinkel@univ-fcomte.fr}, Michel Salomon$^{a}$ and Rapha\"el Couturier $^{a}$ $^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, \\ - University Bourgogne Franche-Comt\'e (UBFC), Belfort, France}} \\ + University Bourgogne Franche-Comt\'e, Belfort, France}} \\ $^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}} } @@ -233,16 +233,16 @@ and provides improved coverage performance. {\it In the PeCO protocol, a new A WSN consisting of $J$ stationary sensor nodes randomly and uniformly distributed in a bounded sensor field is considered. The wireless sensors are deployed in high density to ensure initially a high coverage ratio of the area -of interest. We assume that all the sensor nodes are homogeneous in terms of +of interest. All the sensor nodes are supposed to be homogeneous in terms of communication, sensing, and processing capabilities and heterogeneous from the energy provision point of view. The location information is available to a sensor node either through hardware such as embedded GPS or location discovery -algorithms. We consider a Boolean disk coverage model, which is the most widely -used sensor coverage model in the literature, and all sensor nodes have a +algorithms. A Boolean disk coverage model, which is the most widely used sensor +coverage model in the literature, is considered and all sensor nodes have a constant sensing range $R_s$. Thus, all the space points within a disk centered at a sensor with a radius equal to the sensing range are said to be covered by -this sensor. We also assume that the communication range $R_c$ satisfies $R_c -\geq 2 \cdot R_s$. In fact, \citet{Zhang05} proved that if the transmission +this sensor. We also assume that the communication range $R_c$ satisfies $R_c +\geq 2 \cdot R_s$. In fact, \citet{Zhang05} proved that if the transmission range fulfills the previous hypothesis, the complete coverage of a convex area implies connectivity among active nodes. @@ -537,7 +537,7 @@ First, the following sets: sensor~$j$. \end{itemize} $I_j$ refers to the set of coverage intervals which have been defined according -to the method introduced in subsection~\ref{CI}. For a coverage interval $i$, +to the method introduced in Subsection~\ref{CI}. For a coverage interval $i$, let $a^j_{ik}$ denote the indicator function of whether sensor~$k$ is involved in coverage interval~$i$ of sensor~$j$, that is: \begin{equation} @@ -748,7 +748,7 @@ be consistent with the use of a sensor node based on Atmels AVR ATmega103L microcontroller (6~MHz) having a MIPS rate equal to 6, the original execution time on the laptop is multiplied by 2944.2 $\left(\frac{35330}{2} \times \frac{1}{6} \right)$. Energy consumption is calculated according to the power -consumption values, in milliWatt per second, given in Table~\ref{tab:EC} +consumption values, in milliWatt per second, given in Table~\ref{tab:EC}. based on the energy model proposed in \citep{ChinhVu}. \begin{table}[h] @@ -807,13 +807,13 @@ Figure~\ref{figure5} shows the average coverage ratio for 200 deployed nodes obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, compared to the 98.76\% produced by PeCO for the first periods. This is due to the fact that at -the beginning LiCO and PeCO protocols put to sleep status more redundant sensors -(which slightly decreases the coverage ratio), while the three other protocols -activate more sensor nodes. Later, when the number of periods is beyond~70, it -clearly appears that PeCO provides a better coverage ratio and keeps a coverage -ratio greater than 50\% for longer periods (15 more compared to DiLCO, 40 more -compared to DESK). The energy saved by PeCO in the early periods allows later a -substantial increase of the coverage performance. +the beginning DiLCO and PeCO protocols put to sleep status more redundant +sensors (which slightly decreases the coverage ratio), while the two other +protocols activate more sensor nodes. Later, when the number of periods is +beyond~70, it clearly appears that PeCO provides a better coverage ratio and +keeps a coverage ratio greater than 50\% for longer periods (15 more compared to +DiLCO, 40 more compared to DESK). The energy saved by PeCO in the early periods +allows later a substantial increase of the coverage performance. \parskip 0pt \begin{figure}[h!] @@ -977,7 +977,7 @@ views. Finally, it would be interesting to implement PeCO protocol using a sensor-testbed to evaluate it in real world applications. -\subsection{Acknowledgements} +\subsection*{Acknowledgements} The authors are deeply grateful to the anonymous reviewers for their constructive advice, which improved the technical quality of the paper. As a Ph.D. student, Ali Kadhum IDREES would like to gratefully acknowledge the diff --git a/PeCO-EO/reponse.tex b/PeCO-EO/reponse.tex index 45c1d69..ce66393 100644 --- a/PeCO-EO/reponse.tex +++ b/PeCO-EO/reponse.tex @@ -74,7 +74,7 @@ application of these methods for the coverage scheduling problem.\\ \textcolor{blue}{\textbf{\textsc{Answer:} To the best of our knowledge, no integer linear programming based on perimeter coverage has been already - proposed in the literature. As specified in the paper, in section 4, it is + proposed in the literature. As specified in the paper, in Section 4, it is inspired from a model developed for brachytherapy treatment planning for optimizing dose distribution. In this model the deviation between an actual dose distribution and a required dose distribution in each organ is @@ -86,7 +86,7 @@ application of these methods for the coverage scheduling problem.\\ assumption made on the selection criteria for the leader seems too vague. \\ \textcolor{blue}{\textbf{\textsc{Answer:} The selection criteria for the leader - inside each subregion is explained in page~9, at the end of subsection~3.3 + inside each subregion is explained in page~9, at the end of Section~3.3 After information exchange among the sensor nodes in the subregion, each node will have all the information needed to decide if it will the leader or not. The decision is based on selecting the sensor node that has the larger @@ -127,14 +127,14 @@ optimization problem.\\ for which the number of active sensors (denoted by $l^{i}$) covering this part of the perimeter is greater than $l$ and in this case : $M_{i}^{j}=0$, $V_{i}^{j}=l^{i}-l$. This explanation has been added in the penultimate - paragraph of section~4.}}\\ + paragraph of Section~4.}}\\ \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:} To discuss this point, we added - subsection 5.2.5 in which we study the protocol performance, considering + Section 5.2.5 in which we study the protocol performance, considering $Lifetime_{50}$ and $Lifetime_{95}$ metrics, for different couples of values for alpha and beta. Table 4 presents the results obtained for a WSN of 200~sensor nodes. It explains the value chosen for the simulation settings @@ -164,16 +164,16 @@ not bring out their key contributions. Some references are not consistent and I suggest using the journals template to adjust them for overall consistency.\\ \textcolor{blue}{\textbf{\textsc{Answer:} References have been carefully checked - and seem to be consistent with the journal template. In section~2, ``Related + and seem to be consistent with the journal template. In Section~2, ``Related literature'', we refer to papers dealing with coverage and lifetime in - WSN. Each paragraph of this section discusses the literature related to a + WSN. Each paragraph of this Section discusses the literature related to a particular aspect of the problem : 1. types of coverage, 2. types of scheme, 3. centralized versus distributed protocols, 4. optimization method. At the end of each paragraph we position our approach.}}\\ \noindent {\bf 7.} The methodology is implemented in OMNeT++ (network simulator) and tested against 2 existing algorithms and a previously developed method by -the authors. The simulation results are thorough and show that the proposed +the authors. The simulation results are thorough and show that the proposed method improves the coverage and network lifetime compared with the 3 existing methods. The results are similar to previous work done by their team.\\ @@ -196,16 +196,16 @@ coverage ratio. \\ a coverage ratio greater than $50\%$ for far more periods than the others three methods, but for applications requiring a high level of coverage (greater than $95\%$), DiLCO method is more efficient. It is explained at - the end of section 5.2.4.}}\\ + the end of Section 5.2.4.}}\\ %%%%%%%%%%%%%%%%%%%%%% ENGLISH and GRAMMAR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent\textcolor{black}{\textbf{\Large English and Grammar:}}\\ -\noindent {\ding{90} The first paragraph of every section is not indented.}\\ +\noindent {\ding{90} The first paragraph of every Section is not indented.}\\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed. The first paragraph of - every section is indented in the new version. }}\\ + every Section is indented in the new version. }}\\ \noindent {\ding{90} You seem to be writing in the first person. I suggest rewriting sentences that include “we” “our” or “I” in the third person. (There @@ -246,46 +246,132 @@ coverage ratio. \\ carefully revised and the readability improved. The new version has been checked by an English teacher.}}\\ -% TO BE CONTINUED - \section*{Response to Reviewer No. 2 Comments} -The paper entitled "Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks", by Ali Kadhum Idrees, Karine Deschinkela, Michel Salomon and Raphael Couturier proposes a new protocol for Wireless Sensor Networks called PeCO (Perimeter-based Coverage Optimization protocol) that aims at optimizing the use of energy by conjointly exploiting a spatial and temporal subdivision. The protocol is based on solving a Mixed Integer Linear Program at each leader node, and at each iteration of the protocol. The results obtained by PeCO are compared with three other competitors.\\ +The paper entitled ``Perimeter-based Coverage Optimization to Improve Lifetime +in Wireless Sensor Networks'', by Ali Kadhum Idrees, Karine Deschinkel, Michel +Salomon, and Rapha\"el Couturier proposes a new protocol for Wireless Sensor +Networks called PeCO (Perimeter-based Coverage Optimization protocol) that aims +at optimizing the use of energy by conjointly exploiting a spatial and temporal +subdivision. The protocol is based on solving a Mixed Integer Linear Program at +each leader node, and at each iteration of the protocol. The results obtained by +PeCO are compared with three other competitors.\\ \noindent\textcolor{black}{\textbf{MAJOR COMMENTS:}} \\ -\noindent {\bf 1.} The protocol framework is not described in details. In particular, the spatial and temporal subdivision (page 2, line 11) that is at the core of PeCO, is not described nor justified in much detail. How to implement an efficient spatial subdivision? On page 10, line 11, the number of subdivisions is said to be equal to 16, but the clustering algorithm used is not mentioned. Is this number dependent of the size of the sensing area? Of the number of sensors? Of the sensing range? The proposed protocol cannot be adopted by practitioners if such an important step is not documented. Temporal subdivision suffers from the same lack of description and justification: why should time intervals have the same duration? If they have the same duration, how should this common duration should be chosen? \\ - -\textcolor{blue}{\textbf{\textsc{Answer:} Spatial and temporal choices of subdivision are not the topics of the paper. In the study, we assume that the deployment of sensors is almost uniformly over the region. So we only need to fix a regular division of the region into subregions to make the problem tractable. The subdivision is made such that the number of hops between any pairs of sensors inside a subregion is less than or equal to 3. Concerning the choice of the sensing period duration, it is correlated with the types of applications, with the amount of initial energy in sensors batteries and also with the duration of the exchange phase. All applications do not have the same requirements of Quality of Service. Here information exchange is executed every hour but the length of the sensing period could be reduced and adapted dynamically. On the one hand a small sensing period would allow to be more reliable but would have higher communication costs. On the other hand the choice of a long duration may cause problems in case of nodes failure during the sensing period. Explanation has been given throughout the paper. In particular the sensing duration is discussed in section 5.1.}}\\ - - -\noindent {\bf 2.}Page 9, Section 4, is the Perimeter-based coverage problem NP-hard? This question is important for justifying the use of a Mixed Integer Linear Programming model. \\ - -\textcolor{blue}{\textbf{\textsc{Answer:} The perimeter scheduling coverage problem is NP-hard in general, it has been proved - in the paper entitled "Perimeter Coverage Scheduling in Wireless Sensor Networks Using Sensors with a Single Continuous Cover Range" from Ka-Shun Hung and King-Shan Lui (EURASIP Journal on Wireless Communications and Networking 2010, 2010:926075 doi:10.1155/2010/926075). In this paper, authors study the coverage of the perimeter of a large object requiring to be monitored. In our study, the large object to be monitored is the sensor itself (or more precisely its sensing area). This point has been highlighted at the beginning of section 4. }}\\ - - -\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:} 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 1.} The protocol framework is not described in details. In +particular, the spatial and temporal subdivision (page 2, line 11) that is at +the core of PeCO, is not described nor justified in much detail. How to +implement an efficient spatial subdivision ? On page 10, line 11, the number of +subdivisions is said to be equal to 16, but the clustering algorithm used is not +mentioned. Is this number dependent of the size of the sensing area? Of the +number of sensors? Of the sensing range? The proposed protocol cannot be adopted +by practitioners if such an important step is not documented. Temporal +subdivision suffers from the same lack of description and justification: why +should time intervals have the same duration? If they have the same duration, +how should this common duration should be chosen?\\ + +\textcolor{blue}{\textbf{\textsc{Answer:} Spatial and temporal choices of + subdivision are not the topics of the paper. In the study, we assume that + the deployment of sensors is almost uniform over the region. So we only + need to fix a regular division of the region into subregions to make the + problem tractable. The subdivision is made such that the number of hops + between any pairs of sensors inside a subregion is less than or equal + to~3. Concerning the choice of the sensing period duration, it is correlated + with the types of applications, with the amount of initial energy in sensors + batteries and also with the duration of the exchange phase. All applications + do not have the same Quality of Service requirements. In our case + information exchange is executed every hour, but the length of the sensing + period could be reduced and adapted dynamically. On the one hand a small + sensing period would allow to be more reliable but would have higher + communication costs. On the other hand the choice of a long duration may + cause problems in case of nodes failure during the sensing period. + Several explanations on these points are given throughout the paper. In + particular, we discuss the number of subregions in Section 5.2 and the + sensing duration in the second paragraph of Section 5.1.}}\\ + +\noindent {\bf 2.}Page 9, Section 4, is the Perimeter-based coverage problem +NP-hard? This question is important for justifying the use of a Mixed Integer +Linear Programming model.\\ + +\textcolor{blue}{\textbf{\textsc{Answer:} The perimeter scheduling coverage + problem is NP-hard in general, it has been proved in the paper entitled + "Perimeter Coverage Scheduling in Wireless Sensor Networks Using Sensors + with a Single Continuous Cover Range" from Ka-Shun Hung and King-Shan Lui + (EURASIP Journal on Wireless Communications and Networking 2010, 2010:926075 + doi:10.1155/2010/926075). In this paper, authors study the coverage of the + perimeter of a large object requiring to be monitored. In our study, the + large object to be monitored is the sensor itself (or more precisely its + sensing area). This point has been highlighted at the beginning of + Section~4.}}\\ + +\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:} Right. The mixed Integer Linear + Program adresses a multiobjective problem, where the goal is to minimize + overcoverage and undercoverage for each coverage interval of a 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.\\ \textcolor{blue}{\textbf{\textsc{Answer 1:} 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\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: +\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} -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. -\\ +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. +\medskip \\ \begin{tabular}{|c|c|c|c|c|c|r|} \hline Total number & S & I & GLPK IP & GLPK LP & nodes&CPLEX\\ @@ -298,112 +384,148 @@ of nodes &&&&relaxation &B\&B tree &\\ 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 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). +\medskip \\ +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} -A discussion about memory consumption has been added in section 5.2}} -\bigskip -\textcolor{blue}{\textbf{\textsc{Answer 2:} -In section 5.2 we give a table with the power consumption values which are used to compute the energy consumption. These ones are based on the energy model of (Vu et al. 2006). +A discussion about memory consumption has been added in Section 5.2}} +\bigskip \\ +\indent \textcolor{blue}{\textbf{\textsc{Answer 2:} In Section 5.2 we give a table with + the power consumption values which are used to compute the energy + consumption. These ones are based on the energy model of (Vu et al. 2006). }} - +\bigskip \noindent\textcolor{black}{\textbf{MINOR COMMENTS:}} \\ +\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:} Right. This observation has been added at the end of the introduction}}.\\ - - - -\noindent {\ding{90} Page 2, line 20, "An optimal scheduling" should be replaced with "An optimal schedule" } \\ - -\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\ - - +\textcolor{blue}{\textbf{\textsc{Answer:} Right. This observation has been added + at the end of the introduction.}}\\ -\noindent {\ding{90} Page 4, we first read (line 23) "we assume that each sensor node can directly transmit its measurements to a mobile sink", then on line 30, "We also assume that the communication range Rc satisfies $Rc >=2Rs$. In fact, Zhang and Hou (2005) proved that if the transmission range fulfills the previous hypothesis, the complete coverage of a convex area implies connectivity among active nodes.". These two assumptions seems redundant. } \\ +\noindent {\ding{90} Page 2, line 20, ``An optimal scheduling" should be + replaced with ``An optimal schedule" } \\ -\textcolor{blue}{\textbf{\textsc{Answer:} Yes, you are right and we removed sentences about the sink. Indeed we consider multi-hops communication.}}.\\ +\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed.}}\\ +\noindent {\ding{90} Page 4, we first read (line 23) ``we assume that each + sensor node can directly transmit its measurements to a mobile sink", then on + line 30, "We also assume that the communication range $Rc$ satisfies $Rc + >=2Rs$. In fact, Zhang and Hou (2005) proved that if the transmission range + fulfills the previous hypothesis, the complete coverage of a convex area + implies connectivity among active nodes.". These two assumptions seems + redundant.} \\ +\textcolor{blue}{\textbf{\textsc{Answer:} Yes, you are right and we removed + sentences about the sink. Indeed we consider multi-hop communication.}}\\ -\noindent {\ding{90} Page 4, line 37, a definition for k-covered is missing (the sentence is an equivalence property).} \\ +\noindent {\ding{90} Page 4, line 37, a definition for k-covered is missing (the + sentence is an equivalence property).} \\ -\textcolor{blue}{\textbf{\textsc{Answer:} Right. A network area is said to be $k$-covered if every point in the area covered by at least k sensors. We added this definition in the paper}}.\\ +\textcolor{blue}{\textbf{\textsc{Answer:} Right. A network area is said to be + $k$-covered if every point in the area is covered by at least k sensors. We + added this definition in the paper.}}\\ - - - -\noindent {\ding{90} Page 5, lines 34 and 37, replace [0, $2\pi$] with [0, $2\pi$) } \\ +\noindent {\ding{90} Page 5, lines 34 and 37, replace [0, $2\pi$] with [0, + $2\pi$) } \\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\ - - - -\noindent {\ding{90} Page 5, line 36 and 43, replace "figure 2" with "Figure 2" } \\ +\noindent {\ding{90} Page 5, line 36 and 43, replace ``figure 2" with ``Figure 2" +} \\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\ - - - -\noindent {\ding{90} Page 5, line 50, replace "section 4" with "Section 4" } \\ +\noindent {\ding{90} Page 5, line 50, replace ``section 4" with ``Section 4" } \\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\ - -\noindent {\ding{90} Page 5, line 51, replace "figure 3" with "Figure 3"} \\ +\noindent {\ding{90} Page 5, line 51, replace ``figure 3" with ``Figure 3"} \\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\ +\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. }}.\\ +\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"} \\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\ -\noindent {\ding{90} Page 7, line 47, replace "Five status" with "Five statuses" } \\ +\noindent {\ding{90} Page 7, line 47, replace ``Five status" with ``Five statuses" } \\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\ - - -\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:} 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 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:} 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. } \\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed}}.\\ +\noindent {\ding{90} Page 10, line 53, the ``Coverage ratio" definition is + provided for a given period p? Then in the formula on top of page 11, N is set + to 51 times 26, why? Is it somehow related to the sensing area having size 50 + times 25? } \\ -\noindent {\ding{90} Page 10, line 53, the "Coverage ratio" definition is provided for a given period p? Then in the formula on top of page 11, N is set to 51 times 26, why? Is it somehow related to the sensing area having size 50 times 25? } \\ +\textcolor{blue}{\textbf{\textsc{Answer:} Yes, the ``Coverage ratio" definition + is provided for a given period p. N is set to 51 times 26 = 1326 grid points + because we discretized the sensing field as a regular grid, a point on the + contour and a point every meter. Yes, it is related to the sensing area + having size 50 meters times 25 meters.}}\\ -\textcolor{blue}{\textbf{\textsc{Answer:} Yes, the "Coverage ratio" definition is provided for a given period p. N is set to 51 times 26 = 1326 grid points because we discretized the sensing field as a regular grid, a point on the contour and a point every meter. Yes, it is related to the sensing area having size 50 meters times 25 meters. }}\\ - - -\noindent {\ding{90} Page 11, line 17 in the formula of ASR, |S| should be replaced with J (where J is defined page 4 line 16). } \\ +\noindent {\ding{90} Page 11, line 17 in the formula of ASR, |S| should be + replaced with J (where J is defined page 4 line 16). } \\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\ - -\noindent {\ding{90} Page 13, line 41 and 43, replace "figure 8" with "Figure 8" } \\ +\noindent {\ding{90} Page 13, line 41 and 43, replace ``figure 8" with ``Figure 8" +} \\ \textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\ - - -We are very grateful to the reviewers who, by their recommendations, allowed us to improve the quality of our article. +We are very grateful to the reviewers who, by their recommendations, allowed us +to improve the quality of our article. \begin{flushright} Best regards\\