1 \documentclass[14]{article}
13 \usepackage[small]{caption}
18 \usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
19 \usepackage{mathtools}
24 %\usepackage[T1]{fontenc}
25 %\usepackage[latin1]{inputenc}
27 \renewcommand{\labelenumii}{\labelenumi\arabic{enumii}}
28 %\titleformat*{\section}{\Large\bfseries}
30 %\title{Response to the reviewers of \bf "Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks"}
31 %\author{Ali Kadhum Idrees, Karine Deschinkela, Michel Salomon and Raphael Couturier}
39 \vspace{-0.5cm}\hspace{-2cm}FEMTO-ST Institute, UMR 6714 CNRS
41 \hspace{-2cm}University Bourgogne Franche-Comt\'e
43 \hspace{-2cm}IUT Belfort-Montb\'eliard, BP 527, 90016 Belfort Cedex, France.
48 Detailed changes and addressed issues in the revision of the article
50 ``Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks''\\
53 by Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Raph\"ael Couturier
58 Dear Editor and Reviewers,
60 First of all, we would like to thank you very much for your kind help to improve
61 our article named: `` Distributed Lifetime Coverage Optimization Protocol in
62 Wireless Sensor Networks ''. We highly appreciate the detailed valuable
63 comments of the reviewers on our article. The suggestions are quite helpful for
64 us and we incorporate them in the revised article. We are happy to submit to you
65 a revised version that considers most of your remarks and suggestions to improve
66 the quality of our article.
68 As below, we would like to clarify some of the points raised by the reviewers
69 and we hope the reviewers and the editors will be satisfied by our responses to
70 the comments and the revision for the original manuscript.
73 \section*{Response to Reviewer $\#$1 Comments}
75 The paper present a new system to optimize sensord detections. The work present
76 the algorithm in a cleare and well descrived way. The main problem is connected
77 with the luck of examples and also on the practical applications. I suggest in
78 future to make a more formal description of the process.\\
81 \textcolor{blue}{\textbf{\textsc{Answer:} Right. We have included a paragraph
82 on the examples and practical applications of WSNs in section~1. }}
83 \textcolor{red}{Je pense que la question porte sur un exemple d'application de
85 \textcolor{magenta}{Je pense que oui.}
88 \section*{Response to Reviewer $\#$3 Comments}
90 This work proposed a distributed lifetime coverage optimization (DiLCO) protocol
91 to apply to predefined subregions, which are generated from the area of interest
92 using a classical divide-and-conquer method, to improve the lifetime of a
93 wireless sensor network. Their proposed protocol is devised with a two-step
94 process, including a leader election technique in each subregion and a sensor's
95 activity scheduling by each elected leader. In general, it is a good idea to
96 pre-divide the network domain into several sub-areas, and assign a single
97 cluster head in each sub-area for achieving more balanced energy dissipation for
98 the wireless sensor network. As we known, Heinzelman et al. (2000) first
99 proposed a clustering protocol called LEACH for periodical data-gathering
100 applications. Also many variants of LEACH protocol or a variety of distributed
101 protocols had proposed enhanced energy efficient adaptive clustering protocols
102 by pre-dividing the network domain into several sub-areas, and assigning a
103 single cluster head in each sub-area to achieve more balanced energy
104 dissipation. Hence, I suggest that the authors could clearly state the
105 differences and benefits between their leader selection technique and the
106 methods of cluster head election in LEACH or other distributed
107 protocols. Moreover, they used the two protocols, DESK and GAF, for assessing
108 the performance of their protocols is not convincible. The authors may include
109 more well-known or recently developed protocols for comparison.
112 \textcolor{blue}{\textbf{\textsc{Answer :}
113 %The difference between our leader selection technique and the methods of cluster head election in LEACH or other distributed protocols in that our approach assumes 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 using divide-and-conquer concept such that the number of hops between any pairs of sensors inside a subregion is less than or equal to~3. The sensors inside each subregion cooperate to elect one leader. Leader applies sensor activity scheduling based optimization to provide the schedule to the sensor nodes in the subregion. The advantage of our approach is to minimize the energy consumption required for communication. The sensors only require to communicate with the other sensors inside the subregion to elect the leader instead of communicating with other nodes in the WSN. \\Whereas in LEACH and other cluster head election methods, the cluster heads are elected in distributed way where sensors elect themselves to be local cluster-heads at any given time with a certain probability. These cluster-head nodes broadcast their status to the other sensors in the network. Each sensor node determines to which cluster it wants to belong by choosing the cluster-head that requires the minimum communication energy. Once all the nodes are organized into clusters, each cluster-head creates a schedule for the nodes in its cluster. \\\\
114 In our approach, the leader selection technique is quite different from the
115 LEACH protocol or from its variants. Contrary to the LEACH protocol, the
116 division of the area of interest into subregions is assumed to be performed
117 before the head election. Moreover, we assume that sensors are deployed almost
118 uniformly and with high density over the area of interest, such that the
119 division is fixed and regular. As in LEACH, our protocol works in round fashion.
120 In each round, during the pre-sensing phase, nodes make autonomous decisions. In
121 LEACH, each sensor elects itself to be a cluster head, and each non-cluster head
122 will determine its cluster for the round. In our protocol, nodes in the same
123 subregion select their leader. In both protocols, the amount of remaining energy
124 in each node is taken into account to promote the nodes that have the most
125 energy to become leader. Contrary to the LEACH protocol where all sensors will
126 be active during the sensing-phase, our protocol allows to deactivate a subset
127 of sensors through an optimization process which reduces significantly the
128 energy consumption. \\\\ As explained by the reviewer, there is a large variety
129 of energy-efficient protocols for WSN. We focus on GAF and DESK protocols for
130 two main reasons. First, our protocol is inspired by both of them. DiLCO uses a
131 regular division of the area as in GAF protocol and a temporal division in
132 rounds as in DESK. Second, GAF and DESK are well-known protocols, easy to
133 implement, and often used as references for comparison. \textcolor{red}{je ne
134 sais pas si on ne devrait pas inclure une ref \`a LEACH dans la biblio, mais je
135 ne sais pas trop comment l'introduire dans le papier...}
136 \textcolor{magenta}{Le premier paragraphe de ta r\'eponse me semble pas mal, juste pour situer
137 notre protocole par rapport à LEACH. On pourrait le mettre dans la section~2 ?}\\\\ }}
138 %In fact, GAF algorithm is chosen for comparison as a competitor because it is famous and easy to implement, as well as many authors referred to it in many publications. DESK algorithm is also selected as competitor in the comparison because it works into rounds fashion (network lifetime divided into rounds) similar to our approaches, as well as DESK is a full distributed coverage approach. }}
140 % Michel => TO BE CONTINUED
142 \noindent The following improvements may be suggested to make it even better:\\
143 \noindent {\bf 1. What is the "new idea" or contribution of this work?} \\
144 \textcolor{blue}{\textbf{\textsc{Answer :}
145 The contribution of this work is to design a protocol that focuses on the area coverage problem with the objective of maximizing the network lifetime. Our proposition, the Distributed Lifetime Coverage Optimization
146 (DiLCO) protocol, maintains the coverage and improves the lifetime in WSNs. Our protocol combines two energy efficient mechanisms: leader election and sensor activity scheduling based optimization to optimize the coverage and the network lifetime inside each subregion. we strengthen our simulations by taking into account the characteristics of a Medusa II sensor (Raghunathan et al., 2002) to measure the energy consumption and the computation time. We have implemented two other existing distributed approaches: DESK (Vu et al., 2006) and GAF (Xu et al., 2001)) in order to compare their performances with our approach.
149 \noindent {\bf 2. There are many parameters (listed in Page 5) that must be predefined before the proposed method begins. The reviewer suggests that the all special characters and symbols should be described or defined in the text. } \\
150 \textcolor{blue}{\textbf{\textsc{Answer :} All special characters and symbols have been carefully checked : they were always described and defined in the text, except for $E_{th}$ in algorithm 1. So we added a description in section 3.2 before its use in the algorithm.}}\\
152 \noindent {\bf 3. From their simulations using the five versions: DiLCO-2, DiLCO-4, DiLCO-8, DiLCO-16, and DiLCO-32. The authors concluded that the more subregions enable the extension of the network lifetime. From their experimental simulations, the subdivision in 16 subregions seems to be the most relevant. However, I was wondering if this was possible to derive an expression for the real optimal number of subregions. In general, the optimal number of subregions depends on the size of sensor field and the location of base station.} \\
153 \textcolor{blue}{\textbf{\textsc{Answer :} In fact, the optimal number of subregions depends on the area of interest size, sensing range of sensor, and the location of base station. The optimal number of subregions will be investigated in future. }}\\
155 \noindent {\bf 4. The authors should try to indicate which parameters are critical to performance, is there a significant parameter difference, $w_U$ and $w_\Theta$ in Eq. (4) for example, when the protocol is applied of different WSNs? } \\
156 \textcolor{blue}{\textbf{\textsc{Answer :} As mentioned in the paper, the integer
157 program is based on the model proposed by F. Pedraza, A. L. Medaglia, and
158 A. Garcia (``Efficient coverage algorithms for wireless sensor networks'')
159 with some modifications. The originality of the model is
160 to solve both objectives in a parallel fashion : maximizing the coverage and minimizing the overcoverage. Nevertheless the weights
161 $w_\theta$ and $w_U$ must be properly chosen so as to guarantee that the
162 maximum number of points which are covered during each round is maximum. By
163 choosing $w_{U}$ much larger than $w_{\theta}$, the coverage of a
164 maximum of primary points is ensured. Then for the same number of covered
165 primary points, the solution with a minimal number of active sensors is
166 preferred. It has been proved in the paper mentioned above that this guarantee is satisfied for a weighting constant $w_{U}$ greater than $P$ (when $w_{\theta}$ is fixed to 1). }}\\
168 \noindent {\bf 5. It is unclear whether the parameters of the other two protocols were optimized at all. If they were not, as I suspect, there is no way of knowing whether, indeed, the proposed protocol outperforms the other two on the simulations of WSNs reported in the paper. All experiments would have to be made replicable and the comparisons with other protocols should be fair and crystal clear.} \\
169 \textcolor{blue}{\textbf{\textsc{Answer :} The parameters of the other two protocols were optimized at all as well as we used the same energy consumption model of one of them with slight modification for ensuring fair comparison. }}\\
171 \noindent {\bf 6. I think the authors have a not too bad work here in hands, but the resulting paper is lacking some of convincible originality.} \\
172 \textcolor{blue}{\textbf{\textsc{Answer :} To the best of our knowledge, no hybrid coverage optimization protocol (as our DiLCO protocol) that is globally distributed on the subregions and locally centralized using optimization has ever been proposed in the literature. DiLCO protocol is based on combination of two energy efficient mechanisms: leader election and sensor activity scheduling based optimization so as to optimize the coverage and the network lifetime in each subregion. }}\\
174 \section*{Response to Reviewer $\#$5 Comments}
175 The paper addresses the problem of lifetime coverage in wireless sensor networks. The main issue here is the energy to maintain full coverage of the network while achieving sensing, communication, and computation tasks. The author suggest a new protocol, named DiLCO, aiming at solving the aforementioned objective using a discrete optimization approach. The focus of the paper is clear and the basic idea looks attractive. However, from my opinion, number of clarifications are needed in order for me to be able to validate the whole contribution of the authors. Some of them include:
177 \noindent {\bf 1. The concept of efficiency is not clearly stated, is it the amount of energy used by the protocol or the time it takes to completion ? (line 52 of the introduction "most efficient")} \\
178 \textcolor{blue}{\textbf{\textsc{Answer :} The concept of efficiency refers to the ability of maintaining the best coverage as long as possible. As previously explained, the model with the appropriate weights ensures that a maximum number of points are
179 covered by the set of still alive sensors. The efficiency is measured through
180 the performance metrics "coverage ratio" and "network lifetime". Coverage ratio remains around 100\% as
181 long as possible (as long as there are enough alive sensors to cover all
182 primary points) and then decreases. Network Lifetime is defined as the time until the coverage ratio drops below a predefined threshold. }}\\
184 \noindent {\bf 2. The topology of the graph is not considered in the paper. Isn't it important ? In which class of graphs the author think they will perform better ? are there some disadvantageous topologies ?} \\
185 \textcolor{blue}{\textbf{\textsc{Answer :} The study of the topology of the graph is out of the scope of our paper. We do not focus on specific patterns of sensors' deployment. We consider a highly dense network of sensors uniformly deployed in the area of interest. }}\\
186 %Uniform graph partition is used by subdividing the sensing field into smaller subgraphs (subregion) using divide-and-conquer concept. The subgraph consists of sensor nodes which are previously deployed over the sensing field uniformly with high density to ensure that any primary point on the sensing field is covered by at least one sensor node. The graph partition problem has gained importance due to its application for clustering. The topology of the graph has important impact on the protocol performance. Random graph has negative effect on our DiLCO protocol because we suppose that the sensing field is subdivided uniformly. }}
188 \noindent {\bf 3. In line 42 of section 3, why do we need $R_c \geq 2R_s$ ? Isn't it sufficient to have $Rc > Rs$ ? What is the implication of a stronger hypothesis ? How realistic is it ? Again, this raised the question of the topology.}\\
189 \textcolor{blue}{\textbf{\textsc{Answer :} We assume that the communication range $R_c$ satisfies the condition $Rc \geq 2R_s$. In fact, Zhang and Hou ("Maintaining Sensing Coverage and. Connectivity in Large Sensor Networks",2005) proved that if the transmission range fulfills the previous hypothesis, the complete coverage of a convex area implies connectivity among active nodes. In this paper, communication ranges and sensing ranges of real sensors are given. Communication range is comprised between 30 and 300 meters. And the sensing range does not exceed 30m. \textcolor{red}{In the case of MEDUSA II sensor node,...........}}}\\
191 \noindent {\bf 4. In line 63 of subsection 3.2, it is not clear why the periodic scheduling is in favor of a more robust network. Please, explain.} \\
192 \textcolor{blue}{\textbf{\textsc{Answer :} We explain it in the subsection 3.2. : " A periodic scheduling is
193 interesting because it enhances the robustness of the network against node failures. First, a node that has not enough energy to complete a period, or
194 which fails before the decision is taken, will be excluded from the scheduling
195 process. Second, if a node fails later, whereas it was supposed to sense the
196 region of interest, it will only affect the quality of the coverage until the
197 definition of a new cover set in the next period. " }}\\
199 \noindent {\bf 5. The next sentence mention "enough energy to complete a period". This is another point where the author could be more rigorous. Indeed, how accurate is the evaluation of the required energy for a period ?} \\
200 \textcolor{blue}{\textbf{\textsc{Answer :} The evaluation of the required energy to complete a period takes into account the energy consumed for information exchange with neigbors inside a subregion and the energy needed to stay active during the sensing period. Here, the sensing period duration is equal to one hour but may adapted dynamically according to the QoS requirements. The threshold value $E_{th}$ has been fixed to 36 Joules. This value has been computed by multiplying the energy consumed in the active state (9.72 mW) by the time in second for one period (3600 seconds), and adding the energy for the pre-sensing phases. We explain that in subsection 5.1. In our simulation, the time computation required by a leader to solve the integer program does not exceed 1000 seconds regardless the size of the network and the number of subregions (see figure 4), except the case with two subregions (DilCO-2) where the times computation become much too long as the network size increases. So the energy required for computation $E^{comp}$, estimated to 26.83 mW per second, will never exceed 26.83 Joules. All sensors whose remaining energy is greater than $E_{th}=36$ Joules are potential leaders. Once a leader is selected, it will be itself included in the coverage problem formulation only if its remaining energy before computation is greater than $E_{th}+E^{comp}$. We added a sentence in section 3.2. before the description of the algorithm to clarify this point. Recall that $E^{comp}>E_{th}$ makes no sense. In such a case, the energy required for the decision phase would be greater than the energy required for the sensing phase.}}\\
202 \noindent {\bf 6. About the information collected (line 36-38) , what are they used for ?} \\
203 \textcolor{blue}{\textbf{\textsc{Answer :} The information collected is used for leader election and decision phases. Details on the INFO packet have been added at the end of section~3.2. After
204 the information exchange among the sensor nodes in the subregion, each node
205 will have all the information needed to decide if it will be the leader or
206 not. The decision is based on selecting the sensor node that has the larger
207 number of one-hop neighbors. If this value is the same for many sensors, the
208 node that has the largest remaining energy will be selected as a leader. If
209 there exists sensors with the same number of neighbors and the same value
210 for the remaining energy, the sensor node that has the largest index will be
211 finally selected as a leader. }}\\
213 \noindent {\bf 7. The way the leader is elected could emphasize first on the remaining energy. Is it sure that the remaining energy will be sufficient to solve the integer program algorithm ?} \\
214 \textcolor{blue}{\textbf{\textsc{Answer :} You are right. We have answered this question in previous comments. Remaining energy for DiLCO-4, DiLCO-8, DiLCO-16, and DiLCO-32 protocol versions will be sufficient to solve the integer program algorithm (see Figure 4: Execution time in seconds) in so far as the time computation does not exceed 1000 seconds. Therefore the energy required for computation $E^{comp}$, estimated to 26.83 mW per second, will never exceed 26.83 Joules. However only sensors able to be alive during one sensing period will be included in the coverage problem formulation. To sum up, a sensor may be elected as a leader only if its remaining energy is greater than $E^{comp}$, a leader may participate in the sensing phase only if its remaining energy is greater than $E_{th}+E^{comp}$. Recall that $E_{th}>E^{comp}$.}}\\
216 \noindent {\bf 8. Regarding the MIP formulation at the end of section 4, the first constraint does not appear as a constraint for me as it is an invariant (as shown on top)} \\
217 \textcolor{blue}{\textbf{\textsc{Answer :} This constraint is essential to make the integer program consistent. Whithout this constraint, one optimal solution may be $\theta_p=0 \quad \forall p \in P$, and $U_p=0 \quad \forall p \in P$, whatever the values of $X_j$. And no real optimization is performed. }}\\
219 \noindent {\bf 9. How $ w_\theta $ and $ w_U $ are chosen ? (end of section 4). How dependent if the method toward these parameters ?} \\
220 \textcolor{blue}{\textbf{\textsc{Answer :} Both weights $ w_\theta $ and $ w_U $ must be carefully chosen in order to guarantee that the maximum number of points are covered during each period. In fact, $ w_U $ should be large enough compared to $w_{\Theta}$ to prevent overcoverage and so to activate a minimum number of sensors. We discuss this point in our answer for question 4 of reviewer 3.}}\\
222 \noindent {\bf 10. In table 2, the "listening" and the "computation" status are both (ON, ON, ON), is that correct ?} \\
223 \textcolor{blue}{\textbf{\textsc{Answer :} Yes, in both cases, sensors continue their processing, communication, and sensing tasks. }}\\
225 \noindent {\bf 11. In line 60-61, you choose active energy as reference, is that sufficient for the computation ?} \\
226 \textcolor{blue}{\textbf{\textsc{Answer :} We discuss this point in our answers for question 5 and 7.}}\\
228 \noindent {\bf 12. The equation of EC has the communication energy duplicated} \\
229 \textcolor{blue}{\textbf{\textsc{Answer :} In fact, there is no duplication. The first one, denoted $E^{\scriptsize \mbox{com}}_m$, represents the energy consumption spent by all the nodes for wireless
230 communications during period $m$. The second, $E^{\scriptsize \mbox{comp}}_m$ refers to the energy needed by all the leader nodes to solve the integer program during a period. }}\\
232 \noindent {\bf 13. Figure 2 should be discussed including the initial energy and the topology of the graph} \\
233 \textcolor{blue}{\textbf{\textsc{Answer :} Each node has an initial energy level, in Joules, which is randomly drawn in $[500-700]$. If its energy provision reaches a value below the threshold $E_{th}$ = 36 Joules, the minimum energy
234 needed for a node to stay active during one period, it will no longer take part in the coverage task. As previously explained in answer 2, we consider a highly dense network of sensors uniformly deployed in the area of interest.}}\\
236 \noindent {\bf 14. You mention a DELL laptop. How this could be assimilated to a sensor ?} \\
237 \textcolor{blue}{\textbf{\textsc{Answer :} In fact, simulations are performed on a laptop DELL. But to be consistent with the use of real sensors in practice, we multiply the execution times obtained with the DELL laptop by a constant. This is explained in subsection 5.2.3.}}\\
239 \noindent {\bf 15. In figure 4, what makes the execution times different ?} \\
240 \textcolor{blue}{\textbf{\textsc{Answer :} The execution times are different according to the size of the integer problem to solve. The size of the problem depends on the number of variables and
241 constraints. The number of variables is linked to the number of alive sensors
242 $J$, and the number of primary points
243 $P$. Thus the integer program contains $J$ variables of type $X_j$,
244 $P$ overcoverage variables and $P$ undercoverage variables. The number of
245 constraints is equal to $P$.}}\\
247 \noindent {\bf 16. Why is it important to mention a divide-and-conquer approach (conclusion)} \\
248 \textcolor{blue}{\textbf{\textsc{Answer :} it is important to mention a divide-and-conquer approach because of the subdivision of the sensing field is based on this concept. }}\\
250 \noindent {\bf 17. The connectivity among subregion should be studied too.} \\
251 \textcolor{blue}{\textbf{\textsc{Answer :} Yes you are right, we will investigated it more precisely in future. Up to now, we make the assumption that the communication range $R_c$ satisfies the condition $Rc \geq 2R_s$. In fact, Zhang and Hou ("Maintaining Sensing Coverage and. Connectivity in Large Sensor Networks",2005) proved that if the transmission range fulfills the previous hypothesis, the complete coverage of a convex area implies connectivity among active nodes. Therefore, as long as the coverage ratio is greater than $95\%$, we can assume that the connectivity is maintained. And we check it this hypothesis by simulation with OMNET++.}}\\\\
258 We are very grateful to the reviewers who, by their recommendations, allowed us
259 to improve the quality of our article.
