``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}
+
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.
-
-
\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.\\
+\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 F. Pedraza and 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 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 $W_\theta$ and $W_U$ must be properly chosen so as to guarantee that the maximum number of points are covered during each round. 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 points, 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 for the set of still alive sensors. The coverage is measured through the performance metrics "coverage ratio". The coverage ratio 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 :} }}
-
-
-
-\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:}} \\
-\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
- 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
- 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
-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.
Best regards\\
The authors
\end{flushright}
-
-
\end{document}
