]> AND Private Git Repository - JournalMultiPeriods.git/blobdiff - reponse.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
update figure of primary points model by Ali
[JournalMultiPeriods.git] / reponse.tex
index 4c48b6fa73ef42e82cb364ce58d6d55b7731565a..5cd12b7cf1dd7d4ba9cbd44ea765f330da3d5576 100644 (file)
@@ -33,192 +33,210 @@ Detailed changes and addressed issues in the revision of the article
 ``Multiround Distributed Lifetime Coverage Optimization \\
  Protocol in Wireless Sensor Networks''\\
   
 ``Multiround Distributed Lifetime Coverage Optimization \\
  Protocol in Wireless Sensor Networks''\\
   
-
 by Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Raph\"ael Couturier
 
 \medskip
 
 \end{center}
 by Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Raph\"ael Couturier
 
 \medskip
 
 \end{center}
+
 Dear Editor and Reviewers,
 
 First of all, we would like to thank you very much for your kind help to improve
 Dear Editor and Reviewers,
 
 First of all, we would like to thank you very much for your kind help to improve
-our article  named: `` Multiround Distributed Lifetime Coverage Optimization
-Protocol in Wireless Sensor Networks
-''.  We  highly  appreciate the  detailed  valuable
-comments of the reviewers on our  article. The suggestions are quite helpful for
-us and we incorporate them in the revised article. We are happy to submit to you
-a revised version that considers most of your remarks and suggestions to improve
-the quality of our article.
+our  article named:  ``  Multiround Distributed  Lifetime Coverage  Optimization
+Protocol  in Wireless  Sensor Networks  ''.  We  highly appreciate  the detailed
+valuable comments  of the reviewers  on our  article. The suggestions  are quite
+helpful for us and  we incorporate them in the revised article.  We are happy to
+submit  to  you a  revised  version  that considers  most  of  your remarks  and
+suggestions to improve the quality of our article.
 
 As below, we  would like to clarify  some of the points raised  by the reviewers
 and we hope the reviewers and the  editors will be satisfied by our responses to
 the comments and the revision for the original manuscript.
 
 
 As below, we  would like to clarify  some of the points raised  by the reviewers
 and we hope the reviewers and the  editors will be satisfied by our responses to
 the comments and the revision for the original manuscript.
 
-
-
 \section*{Response to Reviewer No. 1 Comments}
 
 \section*{Response to Reviewer No. 1 Comments}
 
-The paper entitled "Multiround Distributed Lifetime Coverage Optimization
-Protocol in Wireless Sensor Networks" introduces MuDiLCO, a distributed protocol
-to enhance the use of WSN by splitting the network lifetime into periods, and by
-breaking each sensing activity of a period into a series of rounds. A sensor
-called the leader is elected, and based on local data, solves a Mixed Integer
-Linear Program in order to schedule the activity of its neighbors over the
-sensing rounds of the current period.
+The  paper  entitled  ``Multiround Distributed  Lifetime  Coverage  Optimization
+Protocol  in  Wireless  Sensor  Networks''  introduces  MuDiLCO,  a  distributed
+protocol  to enhance  the use  of  WSN by  splitting the  network lifetime  into
+periods, and  by breaking  each sensing activity  of a period  into a  series of
+rounds.  A sensor called the leader is  elected, and based on local data, solves
+a  Mixed  Integer Linear  Program  in  order to  schedule  the  activity of  its
+neighbors over the sensing rounds of the current period.
 
 The contribution of this paper is interesting, but probably needs to be deepened
 in order to reach the standards of a publication in Ad Hoc Networks.\\
 
 
 The contribution of this paper is interesting, but probably needs to be deepened
 in order to reach the standards of a publication in Ad Hoc Networks.\\
 
+\noindent\textcolor{black}{\textbf{MAJOR COMMENTS:}}\\
+
+\noindent {\bf 1.}  Page 6, Section 3.2 The author didn't explain how subregions
+are created.  This  is an important point, as clustering  may have a significant
+impact  on solution  quality.  Not  only  the size  of the  subregion should  be
+discussed and analyzed, but also the clustering strategy.\\
+
+\textcolor{blue}{\textbf{\textsc{Answer:}  In  our  work,  we  assume  that  the
+    sensors are deployed almost uniformly and with high density 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.
+% In particular, we discuss the number of subregions in......
+}}\\
+
+\noindent {\bf 2.} Page 8 The objective function (5) of the Mixed Integer Linear
+Program appears to  be very questionable. Indeed  overcoverage and undercoverage
+may  compensate each  other,  so  the same  objective  value  may represent  two
+incomparable situations. It seems that the semantic of the objective function is
+not well  defined, as one may  wonder what exactly is  (quantitatively speaking)
+the problem  objective.  Coverage breach is  obviously an issue in  WSN, but why
+penalizing overcoverage? A  two-phase approach where breach  is minimized first,
+and then overcoverage is minimized would probably make more sense.\\
+
+\textcolor{blue}{\textbf{\textsc{Answer:} As mentioned in  the paper the integer
+    program is based  on the model proposed  by F. Pedraza, A.  L. Medaglia, and
+    A. Garcia  (``Efficient coverage algorithms for  wireless sensor networks'')
+    with some modifications.  Their initial approach consisted  in first finding
+    the maximum coverage obtainable using the  available sensors and then to use
+    this information as input to the problem of minimizing the overcoverage. But
+    this two-steps approach  is time consuming. The originality of  the model is
+    to solve  both objectives  in a parallel  fashion. Nevertheless  the weights
+    $W_\theta$ and  $W_U$ must be  properly chosen so  as to guarantee  that the
+    maximum number of points which are  covered during each round is maximum. By
+    choosing  $W_{U}$ very  large compared  to $W_{\theta}$,  the coverage  of a
+    maximum of  primary points  is ensured.  Then for a  same number  of covered
+    primary points,  the solution  with a  minimal number  of active  sensors is
+    preferred.  }}\\
+
+\noindent {\bf  3.}  Page 9  In the MILP formulation,  it is possible  that some
+point p  is never  covered at all,  which means  that some part  of the  area to
+monitor  may  never be  monitored  by  the WSN.   The  authors  are referred  to
+``$\alpha$-coverage to  extend network  lifetime on wireless  sensor networks'',
+Optim. Lett. 7, No. 1, 157-172 (2013)  by Gentilli et al to enforce a constraint
+on the minimum coverage of each point.\\
+
+\textcolor{blue}{\textbf{\textsc{Answer:}  As  previously explained,  the  model
+    with the  appropriate weights ensures  that a  maximum number of  points are
+    covered by the set of still  alive sensors. The coverage is measured through
+    the performance metrics ``coverage ratio''. This one remains around 100\% as
+    long as  possible (as long  as there are enough  alive sensors to  cover all
+    primary   points)   and   then   decreases.  The   problem   introduced   in
+    ``$alpha$-coverage to extend network  lifetime on wireless sensor networks''
+    by Gentilli is quite different. In this problem, the coverage ratio is fixed
+    to a predetermined value ($\alpha$) and  the amount of time during which the
+    network   can  satisfy   a  target   coverage  greater   than  $\alpha$   is
+    maximized.}}\\
+
+\noindent {\bf 4.}  Page 13 The  criterion ``Energy Consumption'' is the average
+consumption per  round. But the  duration of  a round is  a feature that  can be
+arbitrarily set in the algorithm.   Computing the average energy consumption per
+unit of  time over the  network lifetime would be  better, as it  is independent
+from the number and duration of rounds.\\
+
+\textcolor{blue}{\textbf{\textsc{Answer :} Yes, you are right. It is possible to
+    obtain  the average  energy consumption  per unit  of time  by dividing  the
+    criterion defined in section~4.3 by the round duration.}}
+
+\noindent {\bf  5.} Page 15-18  Figures 2-6  mention four different  versions of
+MuDiLCO. The  performance of  these different versions  should be  analyzed with
+more  details for  each  figure.   Alternatively, the  authors  may remove  some
+versions of MuDiLCO if they do not bring any valuable insight. \\
+
+\textcolor{blue}{\textbf{\textsc{Answer :}  Right. Therefore we  have completely
+    re-written section 5 to highlight the most significant results.}}
 
 
-\noindent\textcolor{black}{\textbf{MAJOR COMMENTS:}} \\
-
-\noindent {\bf  1.}     Page 6, Section 3.2
-The author didn't explain how subregions are created. This is an important
-point, as clustering may have a significant impact on solution quality. Not only
-the size of the subregion should be discussed and analyzed, but also the
-clustering strategy.\\
-
-\textcolor{blue}{\textbf{\textsc{Answer:} 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. In particular, we discuss the number of subregions in......}}\\
-
-
-\noindent {\bf  2.}     Page 8
-The objective function (5) of the Mixed Integer Linear Program appears to be
-very questionable. Indeed overcoverage and undercoverage may compensate each
-other, so the same objective value may represent two incomparable situations. It
-seems that the semantic of the objective function is not well defined, as one
-may wonder what exactly is (quantitatively speaking) the problem objective.
-Coverage breach is obviously an issue in WSN, but why penalizing overcoverage? A
-two-phase approach where breach is minimized first, and then overcoverage is
-minimized would probably make more sense.
-    \\
-
-\textcolor{blue}{\textbf{\textsc{Answer:} As mentioned in the paper the integer program is based on the model proposed by () with some modifications. Their initial approach consisted in first finding the maximum coverage obtainable from available sensors to then use this information as input to the problem of minimizing the overcoverage. But this two-steps approach is time consuming. The originality of the model is to solve both objectives in a parallel fashion. Nevertheless the weights      }}\\
-
-
-
-\noindent {\bf 3.}   Page 9
-In the MILP formulation, it is possible that some point p is never covered at
-all, which means that some part of the area to monitor may never be monitored by
-the WSN. The authors are referred to "alpha-coverage to extend network lifetime
-on wireless sensor networks", Optim. Lett. 7, No. 1, 157-172 (2013) by Gentilli
-et al to enforce a constraint on the minimum coverage of each point.  \\
-
-\textcolor{blue}{\textbf{\textsc{Answer:}       }}\\
-
-
-\noindent {\bf 4.}  Page 13
-The criterion "Energy Consumption" is the average consumption per round. But the
-duration of a round is a feature that can be arbitrarily set in the algorithm.
-Computing the average energy consumption per unit of time over the network
-lifetime would be better, as it is independent from the number and duration of
-rounds.  \\
-
-\textcolor{blue}{\textbf{\textsc{Answer :}        }}
-
-
-
-\noindent {\bf 5.}    Page 15-18
-Figures 2-6 mention four different versions of MuDiLCO. The performance of these
-different versions should be analyzed with more details for each figure.
-Alternatively, the authors may remove some versions of MuDiLCO if they do not
-bring any valuable insight. \\
-
-
-\textcolor{blue}{\textbf{\textsc{Answer :}        }}
-
-
-\noindent {\bf 6.}   Page 19 (most major point)
-The authors state that solving the Mixed Integer Linear Program is
-time-consuming, and use this point for explaining why MuDiLCO-7 is not as
-efficient as other versions. Why not using a heuristic (or a metaheuristic) for
-addressing the problem instead of using an exact solver? A straightforward and
-easily implementable idea to cut CPU time would be to return the best feasible
-solution found by the solver after a given time threshold for example. Doing so
-is very likely to save time and energy, and to improve the results of MuDiLCO-7
-in particular.  \\
-
-
-\textcolor{blue}{\textbf{\textsc{Answer :}        }}
-
+\bigskip
+\noindent {\bf  6.}  Page 19 (most  major point) The authors  state that solving
+the  Mixed Integer  Linear Program  is time-consuming,  and use  this point  for
+explaining why MuDiLCO-7 is not as efficient  as other versions. Why not using a
+heuristic (or  a metaheuristic) for addressing  the problem instead of  using an
+exact solver?  A straightforward and easily  implementable idea to cut  CPU time
+would be to return the best feasible  solution found by the solver after a given
+time threshold for example. Doing so is very likely to save time and energy, and
+to improve the results of MuDiLCO-7 in particular.\\
+
+\textcolor{blue}{\textbf{\textsc{Answer :}  Your remark is very  interesting. We
+    have observed  that the  optimal solution  of the  integer program  is often
+    obtained after  the exploration  of very few  nodes of  the Branch-and-Bound
+    tree. Therefore we conducted new simulations  by applying your idea. That is
+    to say we have stopped the resolution of the Branch-and-Bound method after a
+    time threshold empirically defined and  we retain the best feasible solution
+    found  by the  solver. This  approach  allows to  improve significantly  the
+    results with multirounds, especially for MuDiLCO-7, as shown in the paper.}}
 
 \bigskip
 
 \noindent\textcolor{black}{\textbf{MINOR COMMENTS:}} \\
 
 
 \bigskip
 
 \noindent\textcolor{black}{\textbf{MINOR COMMENTS:}} \\
 
-\noindent  {\ding{90}    Page 2
-The paragraph that begins with "The remainder of the paper is organized as
-follows" should mention the content of Section 5.    }  \\
-
-\textcolor{blue}{\textbf{\textsc{Answer:}  Right, fixed.  Section 5 is included as a subsection 4.4 within section 4.    }}\\
-
-\noindent  {\ding{90}   Page 3
-The sentence "the centralized approaches usually suffer from the scalability
-problem, making them less competitive as the network size increase" should
-probably be tempered: heuristics and metaheuristics can handle very large and
-centralized problems (even if exact approaches can't), and these approaches are
-very popular in WSN.     } \\
-
-\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed    }}\\
-
-\noindent  {\ding{90}    Page 5
-"The choice of number and locations of primary points is the subject of another
-study not presented here". The authors should provide at least one reference
-about the aforementioned study.      }  \\
-
-\textcolor{blue}{\textbf{\textsc{Answer:}          }}\\
-
-\noindent {\ding{90}     Page 6, Figure 1:
-All rounds seem to have the same duration. This should be stated explicitly, and
-justified (in column generation based approaches, "rounds" to not have the same
-duration).           }  \\
-
-\textcolor{blue}{\textbf{\textsc{Answer:} All rounds have the same duration. It is explicitly explained
- in paragraph ... in section ....  This assumption leads to an integer formulation of the optimization problem. The decision variables are binary variables, $X_{t,j}$  for the activation ($X_{t,j}=1$)  or not ($X_{t,j}=0$) of the sensor $j$ during the round $t$. Column generation based approaches can be applied when the decision variables of the optimization problem are continuous. In this case the variables are the time intervals during which the sensors of a cover set (not necessarily disjoint) are active. The time intervals are not equal. Concerning the choice of round duration of equal length, it is correlated
+\noindent {\ding{90}  Page 2 The paragraph  that begins with ``The  remainder of
+  the paper is  organized as follows'' should mention the  content of Section 5.
+}  \\
+
+\textcolor{blue}{\textbf{\textsc{Answer:} Right,  fixed.  Section 5  is included
+    as subsection 4.5 within section 4.}}\\
+
+\noindent {\ding{90}  Page 3 The  sentence ``the centralized  approaches usually
+  suffer  from the  scalability problem,  making  them less  competitive as  the
+  network  size   increase''  should   probably  be  tempered:   heuristics  and
+  metaheuristics can handle  very large and centralized problems  (even if exact
+  approaches  can't),  and these  approaches  are  empirically very  popular  in
+  WSN.}\\
+
+\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed.}}\\
+
+\noindent {\ding{90}  Page 5  ``The choice  of number  and locations  of primary
+  points  is the  subject of  another study  not presented  here''. The  authors
+  should provide at least one reference about the aforementioned study.}\\
+
+\textcolor{blue}{\textbf{\textsc{Answer:}  Right.  We  have  included a  section
+    (section~4.4) dedicated to the choice and the number of primary points.}}\\
+
+\noindent  {\ding{90}  Page 6,  Figure  1:  All rounds  seem  to  have the  same
+  duration.   This  should  be  stated  explicitly,  and  justified  (in  column
+  generation based approaches, ``rounds'' do not have the same duration).}\\
+
+\textcolor{blue}{\textbf{\textsc{Answer:} All rounds have  the same duration. It
+    is  explicitly  explained in  the  second  paragraph of  section~3.2.   This
+    assumption leads to an integer formulation of the optimization problem.  The
+    decision  variables  are  binary  variables, $X_{t,j}$  for  the  activation
+    ($X_{t,j}=1$) or not  ($X_{t,j}=0$) of the sensor $j$ during  the round $t$.
+    Column  generation  based  approaches  can  be  applied  when  the  decision
+    variables  of the  optimization problem  are  continuous. In  this case  the
+    variables are  the time intervals  during which the  sensors of a  cover set
+    (not necessarily  disjoint) are active.   The time intervals are  not equal.
+    Concerning the  choice of round duration  of equal length, it  is correlated
     with the types of applications, with the amount of initial energy in sensors
     with the types of applications, with the amount of initial energy in sensors
-    batteries,  and  also   with  the  duration  of  the   exchange  phase.  All
+    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 the network 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
     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 the network 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.   }}\\
-
-\noindent  {\ding{90}  Page 11 in Table 1
-$W_\Theta$ should be replaced with $W_\theta$
-              } \\
+    period.}}\\
 
 
-\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\
+\noindent  {\ding{90} Page  11 in  Table 1  $W_\Theta$ should  be replaced  with
+  $W_\theta$}\\
 
 
-\noindent {\ding{90}    Page 12
-Don't italicize "mW" in "equal to 02575 mW"            } \\
+\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed.}}\\
 
 
-\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\
+\noindent {\ding{90} Page 12 Don't italicize ``mW'' in ``equal to 02575 mW'' }\\
 
 
-\noindent {\ding{90}  Page 14
-ML is not defined (see the denominator of the large, unnumbered formula that
-defines EC).          }  \\
+\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed.}}\\
 
 
-\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\
+\noindent  {\ding{90} Page  14 ML  is not  defined (see  the denominator  of the
+  large, unnumbered formula that defines EC).}\\
 
 
-\noindent {\ding{90}  Page 19 Section 6
+\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed.}}\\
 
 
-"Sensing phase itself divided into T rounds" -> T should be italic.           } 
-\\
+\noindent {\ding{90}  Page 19 Section  6 ``Sensing  phase itself divided  into T
+  rounds'' -> T should be italic.}\\
 
 
-\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed }}.\\
+\textcolor{blue}{\textbf{\textsc{Answer:} Right, fixed.}}\\
 
 \noindent {\ding{90}  Page 18 Section 5.5
 The name of the solver used to solve the Mixed Integer Linear Program should be
 
 \noindent {\ding{90}  Page 18 Section 5.5
 The name of the solver used to solve the Mixed Integer Linear Program should be
-given.   }  \\
-
-\textcolor{blue}{\textbf{\textsc{Answer:}   Right, fixed         }}.\\
+given.}\\
 
 
+\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.
@@ -226,7 +244,5 @@ to improve the quality of our article.
 Best regards\\
 The authors
 \end{flushright} 
 Best regards\\
 The authors
 \end{flushright} 
-
 
 \end{document}
 
 \end{document}