-This is pdfTeX, Version 3.1415926-2.4-1.40.13 (TeX Live 2012/Debian) (format=pdflatex 2015.5.30) 8 JUN 2015 15:36
+This is pdfTeX, Version 3.1415926-2.4-1.40.13 (TeX Live 2012/Debian) (format=pdflatex 2013.9.3) 11 JUN 2015 10:50
entering extended mode
restricted \write18 enabled.
%&-line parsing enabled.
[4]
Package epstopdf Info: Source file: <figure1a.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-20 10:11:12
(epstopdf) size: 358485 bytes
(epstopdf) Output file: <figure1a-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:30
+(epstopdf) date: 2015-02-20 10:12:43
(epstopdf) size: 78307 bytes
(epstopdf) Command: <repstopdf --outfile=figure1a-eps-converted-to.
pdf figure1a.eps>
Package pdftex.def Info: figure1a-eps-converted-to.pdf used on input line 255.
(pdftex.def) Requested size: 213.39566pt x 202.1362pt.
Package epstopdf Info: Source file: <figure1b.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-20 10:11:12
(epstopdf) size: 241675 bytes
(epstopdf) Output file: <figure1b-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:31
+(epstopdf) date: 2015-02-20 10:12:44
(epstopdf) size: 57181 bytes
(epstopdf) Command: <repstopdf --outfile=figure1b-eps-converted-to.
pdf figure1b.eps>
[5 <./figure1a-eps-converted-to.pdf> <./figure1b-eps-converted-to.pdf>]
Package epstopdf Info: Source file: <figure2.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-20 10:11:12
(epstopdf) size: 508784 bytes
(epstopdf) Output file: <figure2-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:31
+(epstopdf) date: 2015-02-20 10:12:44
(epstopdf) size: 138861 bytes
(epstopdf) Command: <repstopdf --outfile=figure2-eps-converted-to.p
df figure2.eps>
[6 <./figure2-eps-converted-to.pdf>]
Package epstopdf Info: Source file: <figure3.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-20 10:11:12
(epstopdf) size: 196938 bytes
(epstopdf) Output file: <figure3-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:32
+(epstopdf) date: 2015-02-20 10:12:45
(epstopdf) size: 48639 bytes
(epstopdf) Command: <repstopdf --outfile=figure3-eps-converted-to.p
df figure3.eps>
Package pdftex.def Info: figure3-eps-converted-to.pdf used on input line 349.
(pdftex.def) Requested size: 177.82971pt x 147.74475pt.
Package epstopdf Info: Source file: <figure4.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-20 10:11:12
(epstopdf) size: 428048 bytes
(epstopdf) Output file: <figure4-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:33
+(epstopdf) date: 2015-02-20 10:12:45
(epstopdf) size: 76496 bytes
(epstopdf) Command: <repstopdf --outfile=figure4-eps-converted-to.p
df figure4.eps>
[11]
Package epstopdf Info: Source file: <figure5.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-06 11:42:02
(epstopdf) size: 29526 bytes
(epstopdf) Output file: <figure5-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:33
+(epstopdf) date: 2015-02-20 10:12:46
(epstopdf) size: 12638 bytes
(epstopdf) Command: <repstopdf --outfile=figure5-eps-converted-to.p
df figure5.eps>
LaTeX Warning: `!h' float specifier changed to `!ht'.
Package epstopdf Info: Source file: <figure6.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-06 11:42:02
(epstopdf) size: 29515 bytes
(epstopdf) Output file: <figure6-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:34
+(epstopdf) date: 2015-02-20 10:12:46
(epstopdf) size: 12695 bytes
(epstopdf) Command: <repstopdf --outfile=figure6-eps-converted-to.p
df figure6.eps>
[12]
Package epstopdf Info: Source file: <figure7a.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-06 11:42:02
(epstopdf) size: 24136 bytes
(epstopdf) Output file: <figure7a-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:34
+(epstopdf) date: 2015-02-20 10:12:46
(epstopdf) size: 8179 bytes
(epstopdf) Command: <repstopdf --outfile=figure7a-eps-converted-to.
pdf figure7a.eps>
Package pdftex.def Info: figure7a-eps-converted-to.pdf used on input line 779.
(pdftex.def) Requested size: 234.5788pt x 166.39838pt.
Package epstopdf Info: Source file: <figure7b.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-06 11:42:02
(epstopdf) size: 24138 bytes
(epstopdf) Output file: <figure7b-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:34
+(epstopdf) date: 2015-02-20 10:12:47
(epstopdf) size: 8180 bytes
(epstopdf) Command: <repstopdf --outfile=figure7b-eps-converted-to.
pdf figure7b.eps>
[13 <./figure5-eps-converted-to.pdf> <./figure6-eps-converted-to.pdf>]
Package epstopdf Info: Source file: <figure8a.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-06 11:42:03
(epstopdf) size: 24103 bytes
(epstopdf) Output file: <figure8a-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:35
+(epstopdf) date: 2015-02-20 10:12:47
(epstopdf) size: 8351 bytes
(epstopdf) Command: <repstopdf --outfile=figure8a-eps-converted-to.
pdf figure8a.eps>
Package pdftex.def Info: figure8a-eps-converted-to.pdf used on input line 806.
(pdftex.def) Requested size: 234.5788pt x 166.39838pt.
Package epstopdf Info: Source file: <figure8b.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-06 11:42:03
(epstopdf) size: 24855 bytes
(epstopdf) Output file: <figure8b-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:35
+(epstopdf) date: 2015-02-20 10:12:47
(epstopdf) size: 8466 bytes
(epstopdf) Command: <repstopdf --outfile=figure8b-eps-converted-to.
pdf figure8b.eps>
LaTeX Warning: `!h' float specifier changed to `!ht'.
Package epstopdf Info: Source file: <figure9.eps>
-(epstopdf) date: 2015-06-05 16:52:43
+(epstopdf) date: 2015-02-06 11:42:03
(epstopdf) size: 27000 bytes
(epstopdf) Output file: <figure9-eps-converted-to.pdf>
-(epstopdf) date: 2015-06-05 17:04:35
+(epstopdf) date: 2015-02-20 10:12:48
(epstopdf) size: 7927 bytes
(epstopdf) Command: <repstopdf --outfile=figure9-eps-converted-to.p
df figure9.eps>
)
Here is how much of TeX's memory you used:
3709 strings out of 495059
- 48103 string characters out of 3182030
+ 48103 string characters out of 3182031
115292 words of memory out of 3000000
6817 multiletter control sequences out of 15000+200000
14560 words of font info for 56 fonts, out of 3000000 for 9000
s/type1/public/amsfonts/cm/cmsy8.pfb></usr/share/texlive/texmf-dist/fonts/type1
/public/amsfonts/cm/cmti10.pfb></usr/share/texlive/texmf-dist/fonts/type1/publi
c/amsfonts/cm/cmti8.pfb>
-Output written on articleeo.pdf (18 pages, 737715 bytes).
+Output written on articleeo.pdf (18 pages, 737681 bytes).
PDF statistics:
205 PDF objects out of 1000 (max. 8388607)
139 compressed objects within 2 object streams
\begin{array}{ll}
\min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\
\textrm{subject to :}&\\
-\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i = l \quad \forall i \in I_j, \forall j \in S\\
-\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i = l \quad \forall i \in I_j, \forall j \in S\\
+\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i \geq l \quad \forall i \in I_j, \forall j \in S\\
+\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i \leq l \quad \forall i \in I_j, \forall j \in S\\
X_{k} \in \{0,1\}, \forall k \in A
+M^j_i, V^j_i \in \mathbb{R}^{+}
\end{array}
\right.
\end{equation}
+The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage Optimization (DiLCO) protocol, maintains the coverage and improves the lifetime in WSNs. It is an improved version
+of a research work they presented in~\citep{idrees2014coverage}. First, they partition the area of interest into subregions using a divide-and-conquer method. DiLCO protocol is then distributed on the sensor nodes in each subregion in a second step. DiLCO protocol combines two techniques: a leader election in each subregion, followed by an optimization-based node activity scheduling performed by each elected leader. The proposed DiLCO protocol is a periodic protocol where each period is decomposed into 4 phases: information exchange, leader election, decision, and sensing. The simulations show that DiLCO is able to increase the WSN lifetime and provides improved coverage performance. {\it In the PeCO
+ protocol, We have proposed a new mathematical optimization model. Instead of trying to
+cover a set of specified points/targets as in DiLCO protocol, we formulate an integer program based
+on perimeter coverage of each sensor. The model involves integer variables to capture the deviations between the actual level of coverage and the required level. The idea is that an optimal scheduling will be obtained by minimizing a weighted sum of these deviations.}
+
+
+
+
\section{ The P{\scshape e}CO Protocol Description}
\label{sec:The PeCO Protocol Description}
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 assume that each sensor node can directly transmit its
-measurements to a mobile sink node. For example, a sink can be an unmanned
-aerial vehicle (UAV) flying regularly over the sensor field to collect
-measurements from sensor nodes. A mobile sink node collects the measurements and
-transmits them to the base station. We consider a Boolean disk coverage model,
+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 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
\begin{array}{ll}
\min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\
\textrm{subject to :}&\\
-\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i = l \quad \forall i \in I_j, \forall j \in S\\
-\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i = l \quad \forall i \in I_j, \forall j \in S\\
+\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i \geq l \quad \forall i \in I_j, \forall j \in S\\
+\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i \leq l \quad \forall i \in I_j, \forall j \in S\\
X_{k} \in \{0,1\}, \forall k \in A
\end{array}
\right.
\end{figure}
+\subsubsection{\bf Impact of $\alpha$ and $\beta$ on PeCO's performance}
+Table~\ref{my-labelx} explains all possible network lifetime result of the relation between the different values of $\alpha$ and $\beta$, and for a network size equal to 200 sensor nodes. As can be seen in Table~\ref{my-labelx}, it is obvious and clear that when $\alpha$ decreased and $\beta$ increased by any step, the network lifetime for $Lifetime_{50}$ increased and the $Lifetime_{95}$ decreased. Therefore, selecting the values of $\alpha$ and $\beta$ depend on the application type used in the sensor nework. In PeCO protocol, $\alpha$ and $\beta$ are chosen based on the largest value of network lifetime for $Lifetime_{95}$.
+
+\begin{table}[h]
+\centering
+\caption{The impact of $\alpha$ and $\beta$ on PeCO's performance}
+\label{my-labelx}
+\begin{tabular}{|c|c|c|c|}
+\hline
+$\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
+0.0 & 1.0 & 151 & 0 \\ \hline
+0.1 & 0.9 & 145 & 0 \\ \hline
+0.2 & 0.8 & 140 & 0 \\ \hline
+0.3 & 0.7 & 134 & 0 \\ \hline
+0.4 & 0.6 & 125 & 0 \\ \hline
+0.5 & 0.5 & 118 & 30 \\ \hline
+0.6 & 0.4 & 94 & 57 \\ \hline
+0.7 & 0.3 & 97 & 49 \\ \hline
+0.8 & 0.2 & 90 & 52 \\ \hline
+0.9 & 0.1 & 77 & 50 \\ \hline
+1.0 & 0.0 & 60 & 44 \\ \hline
+\end{tabular}
+\end{table}
\section{Conclusion and Future Works}
\label{sec:Conclusion and Future Works}
-In this paper we have studied the problem of Perimeter-based Coverage Optimization in
-WSNs. We have designed a new protocol, called Perimeter-based Coverage Optimization, which
-schedules nodes' activities (wake up and sleep stages) with the objective of
-maintaining a good coverage ratio while maximizing the network lifetime. This
-protocol is applied in a distributed way in regular subregions obtained after
-partitioning the area of interest in a preliminary step. It works in periods and
-is based on the resolution of an integer program to select the subset of sensors
-operating in active status for each period. Our work is original in so far as it
-proposes for the first time an integer program scheduling the activation of
-sensors based on their perimeter coverage level, instead of using a set of
-targets/points to be covered.
-
-
-We have carried out several simulations to evaluate the proposed protocol. The
-simulation results show that PeCO is more energy-efficient than other
-approaches, with respect to lifetime, coverage ratio, active sensors ratio, and
-energy consumption.
+In this paper we have studied the problem of Perimeter-based Coverage Optimization in WSNs. We have designed a new protocol, called Perimeter-based Coverage Optimization, which schedules nodes' activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. This protocol is applied in a distributed way in regular subregions obtained after partitioning the area of interest in a preliminary step. It works in periods and
+is based on the resolution of an integer program to select the subset of sensors operating in active status for each period. Our work is original in so far as it proposes for the first time an integer program scheduling the activation of sensors based on their perimeter coverage level, instead of using a set of targets/points to be covered.
-We plan to extend our framework so that the schedules are planned for multiple
-sensing periods.
-We also want to improve our integer program to take into account heterogeneous
-sensors from both energy and node characteristics point of views.
+We have carried out several simulations to evaluate the proposed protocol. The simulation results show that PeCO is more energy-efficient than other approaches, with respect to lifetime, coverage ratio, active sensors ratio, and energy consumption.
-Finally, it would be interesting to implement our protocol using a
-sensor-testbed to evaluate it in real world applications.
+We plan to extend our framework so that the schedules are planned for multiple sensing periods. We also want to improve our integer program to take into account heterogeneous sensors from both energy and node characteristics point of views. Finally, it would be interesting to implement our protocol using a sensor-testbed to evaluate it in real world applications.
\bibliographystyle{gENO}
-\bibliography{biblio}
+\bibliography{biblio} %articleeo
\end{document}
\textcolor{blue}{\textbf{\textsc{Answer:}
To implement PeCO on real sensors nodes with limited memories capacities, we can act on :
\begin{itemize}
-\item the solver : GLPK is memory consuming for the resolution of integer programming (IP) compared with other commercial solvers like CPLEX\texttrademark. Commercial solvers generally outperform open source solvers (See "Analysis of commercial and free and open source
-solvers for linear optimization problems" by B. Meindl and M. Templ from Vienna University of Technology). Memory use depends on the number of variables and number of constraints. For linear programs (LP), a reasonable estimate of memory use with CPLEX\texttrademark is to allow one megabyte per thousand constraints. For integer programs, no simple formula exists since memory use depends so heavily on the size of the branch and bound tree. But, the estimate for linear programs still provides a lower bound. In our case, the characteristics of the integer programming (2) are the following:\\
+\item the solver : GLPK is memory consuming for the resolution of integer programming (IP) compared with other commercial solvers like CPLEX\textregistered. Commercial solvers generally outperform open source solvers (See the report : "Analysis of commercial and free and open source
+solvers for linear optimization problems" by B. Meindl and M. Templ from Vienna University of Technology). Memory use depends on the number of variables and number of constraints. For linear programs (LP), a reasonable estimate of memory use with CPLE\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 cover interval. The following table gives the memory used with GLPK to solve the integer program (column 3) and its LP-relaxation (column 4) for different problem sizes. The sixth column gives an estimate of the memory used with CPLEX to solves the LP-relaxation according to the number of constraints.
+where $S$ denotes the number of sensors in the subregion, $I$ the average number of cover intervals per sensor, $B$ the average number of sensors involved in a coverage interval. The following table gives the memory used with GLPK to solve the integer program (column 3) and its LP-relaxation (column 4) for different problem sizes. The sixth column gives an estimate of the memory used with CPLEX to solves the LP-relaxation according to the number of constraints.
\\
-\begin{tabular}{|c|c|c|c|c|c|}
+\begin{tabular}{|c|c|c|c|c|c|r|}
\hline
-Total number of nodes& S & I & GLPK IP & GLPK LP & number of nodes in the &CPLEX\\
-of nodes &&&&relaxation &branch-and-bound tree &\\
+Total number & S & I & GLPK IP & GLPK LP & nodes&CPLEX\\
+of nodes &&&&relaxation &B\&B tree &\\
\hline
100 & 6.25& 5&0.2 Mb & 0.2 Mb &1 & 64 Kb\\
\hline
300 &18.5 & 17&3.6 Mb & 3.5 Mb & 3 &644 Kb\\
\hline
\end{tabular}
-It is noteworthy that the difference of memory used with GLPK between the resolution of the IP and its LP-relaxation is very weak (not more than 0.1 Mb). The size of the branch and bound tree dos not exceed 3 nodes. This result leads one to believe the memory used with CPLEX for solving the IP would be very close to that for the LP-relaxation, that is to say around 100 Kb for a subregion containing $S=10$ sensors. Moreover the IP seems to have some specifities that encourage us to develop our own solver (coefficents matrix is very sparse) or to use an existing heuristic to find good approximate solution ().
-
-
-
-\item the subdivision of the region of interest. To make the resolution of integer programming tractable by a leader sensor, we need to limit the number of nodes in each subregion (the number of variables and constraints of the integer programming is directly depending on the number of nodes and neigbors). It is therefore necessary to adapt the subdvision according to the number of sensors deployed in the area and their sensing range (impact on the number of cover intervals).
-\item heuristic
-
+It is noteworthy that the difference of memory used with GLPK between the resolution of the IP and its LP-relaxation is very weak (not more than 0.1 Mb). The size of the branch and bound tree dos not exceed 3 nodes. This result leads one to believe the memory used with CPLEX for solving the IP would be very close to that for the LP-relaxation, that is to say around 100 Kb for a subregion containing $S=10$ sensors. Moreover the IP seems to have some specifities that encourage us to develop our own solver (coefficents matrix is very sparse) or to use an existing heuristic to find good approximate 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}}}\\
