\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}The Main Idea}{7}}
\newlabel{figure4}{{4}{8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}PeCO Protocol Algorithm}{8}}
+\citation{doi:10.1155/2010/926075}
+\citation{doi:10.1155/2010/926075}
\newlabel{alg:PeCO}{{{1}}{9}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Perimeter-based Coverage Problem Formulation}{9}}
\newlabel{cp}{{4}{9}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Performance Evaluation and Analysis}{10}}
\newlabel{sec:Simulation Results and Analysis}{{5}{10}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Simulation Settings}{10}}
-\newlabel{table3}{{2}{10}}
+\newlabel{table3}{{2}{11}}
\citation{varga}
\citation{AMPL}
\citation{glpk}
\citation{idrees2014coverage}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Simulation Results}{12}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.1}\bf Coverage Ratio}{12}}
-\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.2}\bf Active Sensors Ratio}{12}}
\newlabel{figure5}{{5}{13}}
+\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.2}\bf Active Sensors Ratio}{13}}
\newlabel{figure6}{{6}{13}}
-\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.3}\bf Energy Consumption}{13}}
-\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.4}\bf Network Lifetime}{13}}
+\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.3}\bf Energy Consumption}{14}}
\newlabel{figure7}{{7}{14}}
-\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.5}\bf Impact of $\alpha $ and $\beta $ on PeCO's performance}{14}}
+\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.4}\bf Network Lifetime}{14}}
\newlabel{figure8}{{8}{15}}
-\newlabel{figure9}{{9}{15}}
-\@writefile{toc}{\contentsline {section}{\numberline {6}Conclusion and Future Works}{15}}
-\newlabel{sec:Conclusion and Future Works}{{6}{15}}
+\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.5}\bf Impact of $\alpha $ and $\beta $ on PeCO's performance}{15}}
\bibstyle{gENO}
\bibdata{biblio}
\bibcite{akyildiz2002wireless}{{1}{2002}{{Akyildiz et~al.}}{{Akyildiz, Su, Sankarasubramaniam, and Cayirci}}}
+\newlabel{figure9}{{9}{16}}
+\newlabel{my-labelx}{{3}{16}}
+\@writefile{toc}{\contentsline {section}{\numberline {6}Conclusion and Future Works}{16}}
+\newlabel{sec:Conclusion and Future Works}{{6}{16}}
\bibcite{anastasi2009energy}{{2}{2009}{{Anastasi et~al.}}{{Anastasi, Conti, Di~Francesco, and Passarella}}}
\bibcite{berman04}{{3}{2004}{{Berman and Calinescu}}{{}}}
\bibcite{cardei2005improving}{{4}{2005}{{Cardei and Du}}{{}}}
\bibcite{Deng2012}{{7}{2012}{{Deng, Jiguo~Yu, and Chen}}{{}}}
\bibcite{deschinkel2012column}{{8}{2012}{{Deschinkel}}{{}}}
\bibcite{AMPL}{{9}{November 12, 2002}{{Fourer, Gay, and Kernighan}}{{}}}
-\newlabel{my-labelx}{{3}{16}}
\bibcite{HeShibo}{{10}{2014}{{He et~al.}}{{He, Gong, Zhang, Chen, and Sun}}}
\bibcite{Huang:2003:CPW:941350.941367}{{11}{2005{a}}{{Huang and Tseng}}{{}}}
\bibcite{huang2005coverage}{{12}{2005{b}}{{Huang and Tseng}}{{}}}
-\bibcite{idrees2014coverage}{{13}{2014}{{Idrees et~al.}}{{Idrees, Deschinkel, Salomon, and Couturier}}}
-\bibcite{Idrees2}{{14}{2015}{{Idrees et~al.}}{{Idrees, Deschinkel, Salomon, and Couturier}}}
-\bibcite{jaggi2006}{{15}{2006}{{Jaggi and Abouzeid}}{{}}}
-\bibcite{kim2013maximum}{{16}{2013}{{Kim and Cobb}}{{}}}
-\bibcite{0031-9155-44-1-012}{{17}{1999}{{Lee et~al.}}{{Lee, Gallagher, Silvern, Wuu, and Zaider}}}
-\bibcite{li2013survey}{{18}{2013}{{Li and Vasilakos}}{{}}}
-\bibcite{ling2009energy}{{19}{2009}{{Ling and Znati}}{{}}}
-\bibcite{glpk}{{20}{2012}{{Makhorin}}{{}}}
-\bibcite{Misra}{{21}{2011}{{Misra, Kumar, and Obaidat}}{{}}}
-\bibcite{pc10}{{22}{2010}{{Padmavathy and Chitra}}{{}}}
-\bibcite{puccinelli2005wireless}{{23}{2005}{{Puccinelli and Haenggi}}{{}}}
-\bibcite{pujari2011high}{{24}{2011}{{Pujari}}{{}}}
-\bibcite{qu2013distributed}{{25}{2013}{{Qu and Georgakopoulos}}{{}}}
-\bibcite{rault2014energy}{{26}{2014}{{Rault, Bouabdallah, and Challal}}{{}}}
-\bibcite{doi:10.1080/0305215X.2012.687732}{{27}{2013}{{Singh, Rossi, and Sevaux}}{{}}}
-\bibcite{Tian02}{{28}{2002}{{Tian and Georganas}}{{}}}
-\bibcite{varga}{{29}{2003}{{Varga}}{{}}}
-\bibcite{ChinhVu}{{30}{2006}{{Vu et~al.}}{{Vu, Gao, Deshmukh, and Li}}}
-\bibcite{chin2007}{{31}{2009}{{Vu}}{{}}}
-\bibcite{wang2011coverage}{{32}{2011}{{Wang}}{{}}}
-\bibcite{5714480}{{33}{2010}{{Xing, Li, and Wang}}{{}}}
-\bibcite{xu2001geography}{{34}{2001}{{Xu, Heidemann, and Estrin}}{{}}}
-\bibcite{yan2008design}{{35}{2008}{{Yan et~al.}}{{Yan, Gu, He, and Stankovic}}}
-\bibcite{yang2014novel}{{36}{2014{a}}{{Yang and Chin}}{{}}}
-\bibcite{yangnovel}{{37}{2014{b}}{{Yang and Chin}}{{}}}
-\bibcite{Yang2014}{{38}{2014}{{Yang and Liu}}{{}}}
-\bibcite{yick2008wireless}{{39}{2008}{{Yick, Mukherjee, and Ghosal}}{{}}}
-\bibcite{Zhang05}{{40}{2005}{{Zhang and Hou}}{{}}}
-\bibcite{zhou2009variable}{{41}{2009}{{Zhou, Das, and Gupta}}{{}}}
-\bibcite{zorbas2010solving}{{42}{2010}{{Zorbas et~al.}}{{Zorbas, Glynos, Kotzanikolaou, and Douligeris}}}
-\endpage{18}
+\bibcite{doi:10.1155/2010/926075}{{13}{2010}{{Hung and Lui}}{{}}}
+\bibcite{idrees2014coverage}{{14}{2014}{{Idrees et~al.}}{{Idrees, Deschinkel, Salomon, and Couturier}}}
+\bibcite{Idrees2}{{15}{2015}{{Idrees et~al.}}{{Idrees, Deschinkel, Salomon, and Couturier}}}
+\bibcite{jaggi2006}{{16}{2006}{{Jaggi and Abouzeid}}{{}}}
+\bibcite{kim2013maximum}{{17}{2013}{{Kim and Cobb}}{{}}}
+\bibcite{0031-9155-44-1-012}{{18}{1999}{{Lee et~al.}}{{Lee, Gallagher, Silvern, Wuu, and Zaider}}}
+\bibcite{li2013survey}{{19}{2013}{{Li and Vasilakos}}{{}}}
+\bibcite{ling2009energy}{{20}{2009}{{Ling and Znati}}{{}}}
+\bibcite{glpk}{{21}{2012}{{Makhorin}}{{}}}
+\bibcite{Misra}{{22}{2011}{{Misra, Kumar, and Obaidat}}{{}}}
+\bibcite{pc10}{{23}{2010}{{Padmavathy and Chitra}}{{}}}
+\bibcite{puccinelli2005wireless}{{24}{2005}{{Puccinelli and Haenggi}}{{}}}
+\bibcite{pujari2011high}{{25}{2011}{{Pujari}}{{}}}
+\bibcite{qu2013distributed}{{26}{2013}{{Qu and Georgakopoulos}}{{}}}
+\bibcite{rault2014energy}{{27}{2014}{{Rault, Bouabdallah, and Challal}}{{}}}
+\bibcite{doi:10.1080/0305215X.2012.687732}{{28}{2013}{{Singh, Rossi, and Sevaux}}{{}}}
+\bibcite{Tian02}{{29}{2002}{{Tian and Georganas}}{{}}}
+\bibcite{varga}{{30}{2003}{{Varga}}{{}}}
+\bibcite{ChinhVu}{{31}{2006}{{Vu et~al.}}{{Vu, Gao, Deshmukh, and Li}}}
+\bibcite{chin2007}{{32}{2009}{{Vu}}{{}}}
+\bibcite{wang2011coverage}{{33}{2011}{{Wang}}{{}}}
+\bibcite{5714480}{{34}{2010}{{Xing, Li, and Wang}}{{}}}
+\bibcite{xu2001geography}{{35}{2001}{{Xu, Heidemann, and Estrin}}{{}}}
+\bibcite{yan2008design}{{36}{2008}{{Yan et~al.}}{{Yan, Gu, He, and Stankovic}}}
+\bibcite{yang2014novel}{{37}{2014{a}}{{Yang and Chin}}{{}}}
+\bibcite{yangnovel}{{38}{2014{b}}{{Yang and Chin}}{{}}}
+\bibcite{Yang2014}{{39}{2014}{{Yang and Liu}}{{}}}
+\bibcite{yick2008wireless}{{40}{2008}{{Yick, Mukherjee, and Ghosal}}{{}}}
+\bibcite{Zhang05}{{41}{2005}{{Zhang and Hou}}{{}}}
+\bibcite{zhou2009variable}{{42}{2009}{{Zhou, Das, and Gupta}}{{}}}
+\bibcite{zorbas2010solving}{{43}{2010}{{Zorbas et~al.}}{{Zorbas, Glynos, Kotzanikolaou, and Douligeris}}}
+\endpage{19}
\questionmark{}
-\begin{thebibliography}{42}
+\begin{thebibliography}{43}
\newcommand{\enquote}[1]{``#1''}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\normalfont{#1}}
a wireless sensor network.'' \emph{Mobile Networks and Applications} 10 (4):
519--528.
+\bibitem[Hung and Lui(2010)]{doi:10.1155/2010/926075}
+Hung, Ka-Shun, and King-Shan Lui. 2010. ``Perimeter Coverage Scheduling in
+ Wireless Sensor Networks Using Sensors with a Single Continuous Cover
+ Range.'' \emph{EURASIP Journal on Wireless Communications and Networking}
+ 2010.
+
\bibitem[Idrees et~al.(2014)Idrees, Deschinkel, Salomon, and
Couturier]{idrees2014coverage}
Idrees, Ali~Kadhum, Karine Deschinkel, Michel Salomon, and Rapha{\"e}l
Networks} 67: 104--122.
\bibitem[Singh, Rossi, and Sevaux(2013)]{doi:10.1080/0305215X.2012.687732}
-Singh, Alok, André Rossi, and Marc Sevaux. 2013. ``Matheuristic approaches for
- Q-coverage problem versions in wireless sensor networks.'' \emph{Engineering
- Optimization} 45 (5): 609--626.
+Singh, Alok, André Rossi, and Marc Sevaux. 2013. ``Metaheuristic approaches
+ for Q-coverage problem versions in wireless sensor networks.''
+ \emph{Engineering Optimization} 45 (5): 609--626.
\bibitem[Tian and Georganas(2002)]{Tian02}
Tian, Di, and Nicolas~D. Georganas. 2002. ``A coverage-preserving node
Capacity: max_strings=35307, hash_size=35307, hash_prime=30011
The top-level auxiliary file: articleeo.aux
The style file: gENO.bst
-Database file #1: articleeo.bib
+Database file #1: biblio.bib
Reallocated wiz_functions (elt_size=4) to 6000 items from 3000.
-You've used 42 entries,
+You've used 43 entries,
3679 wiz_defined-function locations,
- 965 strings with 13446 characters,
-and the built_in function-call counts, 30125 in all, are:
-= -- 2469
-> -- 1552
+ 970 strings with 13673 characters,
+and the built_in function-call counts, 30688 in all, are:
+= -- 2516
+> -- 1582
< -- 4
-+ -- 760
-- -- 421
-* -- 2096
-:= -- 4369
-add.period$ -- 96
-call.type$ -- 42
-change.case$ -- 281
-chr.to.int$ -- 49
-cite$ -- 42
-duplicate$ -- 2276
-empty$ -- 2260
-format.name$ -- 528
-if$ -- 6194
++ -- 773
+- -- 429
+* -- 2134
+:= -- 4458
+add.period$ -- 98
+call.type$ -- 43
+change.case$ -- 287
+chr.to.int$ -- 50
+cite$ -- 43
+duplicate$ -- 2321
+empty$ -- 2299
+format.name$ -- 539
+if$ -- 6306
int.to.chr$ -- 3
int.to.str$ -- 1
-missing$ -- 403
-newline$ -- 137
-num.names$ -- 168
-pop$ -- 1201
+missing$ -- 411
+newline$ -- 140
+num.names$ -- 172
+pop$ -- 1226
preamble$ -- 1
-purify$ -- 279
+purify$ -- 285
quote$ -- 0
-skip$ -- 1067
+skip$ -- 1089
stack$ -- 0
-substring$ -- 1285
-swap$ -- 1058
+substring$ -- 1296
+swap$ -- 1075
text.length$ -- 2
text.prefix$ -- 0
top$ -- 0
-type$ -- 375
+type$ -- 384
warning$ -- 0
-while$ -- 236
+while$ -- 240
width$ -- 0
-write$ -- 470
+write$ -- 481
-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
+This is pdfTeX, Version 3.1415926-2.4-1.40.13 (TeX Live 2012/Debian) (format=pdflatex 2013.9.3) 19 JUN 2015 15:28
entering extended mode
restricted \write18 enabled.
%&-line parsing enabled.
[3]
LaTeX Font Warning: Font shape `OT1/cmr/bx/sc' undefined
-(Font) using `OT1/cmr/bx/n' instead on input line 209.
+(Font) using `OT1/cmr/bx/n' instead on input line 208.
-
-Underfull \vbox (badness 10000) has occurred while \output is active []
-
-
-Underfull \vbox (badness 10000) has occurred while \output is active []
-
-
-Underfull \vbox (badness 10000) has occurred while \output is active []
-
-
-Overfull \vbox (36.0pt too high) has occurred while \output is active []
-
-
-Overfull \vbox (36.0pt too high) has occurred while \output is active []
-
-
-Overfull \vbox (650.43pt too high) has occurred while \output is active []
-
-
-Overfull \vbox (29.0pt too high) has occurred while \output is active []
-
-
-Overfull \vbox (701.0pt too high) has occurred while \output is active []
-
- [4]
Package epstopdf Info: Source file: <figure1a.eps>
(epstopdf) date: 2015-02-20 10:11:12
(epstopdf) size: 358485 bytes
(epstopdf) size: 78307 bytes
(epstopdf) Command: <repstopdf --outfile=figure1a-eps-converted-to.
pdf figure1a.eps>
-(epstopdf) \includegraphics on input line 255.
+(epstopdf) \includegraphics on input line 254.
Package epstopdf Info: Output file is already uptodate.
-
-<figure1a-eps-converted-to.pdf, id=29, 418.56375pt x 396.48125pt>
+<figure1a-eps-converted-to.pdf, id=24, 418.56375pt x 396.48125pt>
File: figure1a-eps-converted-to.pdf Graphic file (type pdf)
<use figure1a-eps-converted-to.pdf>
-Package pdftex.def Info: figure1a-eps-converted-to.pdf used on input line 255.
+Package pdftex.def Info: figure1a-eps-converted-to.pdf used on input line 254.
(pdftex.def) Requested size: 213.39566pt x 202.1362pt.
Package epstopdf Info: Source file: <figure1b.eps>
(epstopdf) date: 2015-02-20 10:11:12
(epstopdf) size: 57181 bytes
(epstopdf) Command: <repstopdf --outfile=figure1b-eps-converted-to.
pdf figure1b.eps>
-(epstopdf) \includegraphics on input line 256.
+(epstopdf) \includegraphics on input line 255.
Package epstopdf Info: Output file is already uptodate.
-<figure1b-eps-converted-to.pdf, id=30, 385.44pt x 269.005pt>
+<figure1b-eps-converted-to.pdf, id=25, 385.44pt x 269.005pt>
File: figure1b-eps-converted-to.pdf Graphic file (type pdf)
<use figure1b-eps-converted-to.pdf>
-Package pdftex.def Info: figure1b-eps-converted-to.pdf used on input line 256.
+Package pdftex.def Info: figure1b-eps-converted-to.pdf used on input line 255.
(pdftex.def) Requested size: 213.39566pt x 148.93011pt.
Underfull \vbox (badness 10000) has occurred while \output is active []
Overfull \vbox (29.0pt too high) has occurred while \output is active []
+Overfull \vbox (701.0pt too high) has occurred while \output is active []
+
+ [4]
+Underfull \vbox (badness 10000) has occurred while \output is active []
+
+
+Underfull \vbox (badness 10000) has occurred while \output is active []
+
+
+Underfull \vbox (badness 10000) has occurred while \output is active []
+
+
+Overfull \vbox (36.0pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (36.0pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (650.43pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (29.0pt too high) has occurred while \output is active []
+
+
Overfull \vbox (701.0pt too high) has occurred while \output is active []
[5 <./figure1a-eps-converted-to.pdf> <./figure1b-eps-converted-to.pdf>]
(epstopdf) size: 138861 bytes
(epstopdf) Command: <repstopdf --outfile=figure2-eps-converted-to.p
df figure2.eps>
-(epstopdf) \includegraphics on input line 299.
+(epstopdf) \includegraphics on input line 298.
Package epstopdf Info: Output file is already uptodate.
<figure2-eps-converted-to.pdf, id=41, 518.93875pt x 260.975pt>
File: figure2-eps-converted-to.pdf Graphic file (type pdf)
<use figure2-eps-converted-to.pdf>
-Package pdftex.def Info: figure2-eps-converted-to.pdf used on input line 299.
+Package pdftex.def Info: figure2-eps-converted-to.pdf used on input line 298.
(pdftex.def) Requested size: 362.77263pt x 182.4463pt.
Underfull \vbox (badness 10000) has occurred while \output is active []
(epstopdf) size: 48639 bytes
(epstopdf) Command: <repstopdf --outfile=figure3-eps-converted-to.p
df figure3.eps>
-(epstopdf) \includegraphics on input line 349.
+(epstopdf) \includegraphics on input line 348.
Package epstopdf Info: Output file is already uptodate.
<figure3-eps-converted-to.pdf, id=48, 332.24126pt x 276.03125pt>
File: figure3-eps-converted-to.pdf Graphic file (type pdf)
<use figure3-eps-converted-to.pdf>
-Package pdftex.def Info: figure3-eps-converted-to.pdf used on input line 349.
+Package pdftex.def Info: figure3-eps-converted-to.pdf used on input line 348.
(pdftex.def) Requested size: 177.82971pt x 147.74475pt.
Package epstopdf Info: Source file: <figure4.eps>
(epstopdf) date: 2015-02-20 10:11:12
(epstopdf) size: 76496 bytes
(epstopdf) Command: <repstopdf --outfile=figure4-eps-converted-to.p
df figure4.eps>
-(epstopdf) \includegraphics on input line 382.
+(epstopdf) \includegraphics on input line 381.
Package epstopdf Info: Output file is already uptodate.
<figure4-eps-converted-to.pdf, id=49, 493.845pt x 362.35374pt>
File: figure4-eps-converted-to.pdf Graphic file (type pdf)
<use figure4-eps-converted-to.pdf>
-Package pdftex.def Info: figure4-eps-converted-to.pdf used on input line 382.
+Package pdftex.def Info: figure4-eps-converted-to.pdf used on input line 381.
(pdftex.def) Requested size: 227.62204pt x 167.01096pt.
Underfull \vbox (badness 10000) has occurred while \output is active []
[10]
-LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 638.
+LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 642.
-LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 653.
+LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 657.
-LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 666.
+Underfull \vbox (badness 10000) has occurred while \output is active []
+Underfull \vbox (badness 10000) has occurred while \output is active []
-LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 673.
+Underfull \vbox (badness 10000) has occurred while \output is active []
-LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 675.
+Overfull \vbox (36.0pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (36.0pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (650.43pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (29.0pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (701.0pt too high) has occurred while \output is active []
+
+ [11]
+
+LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 670.
+LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 679.
+
+
+
+LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 681.
+
+
+
Underfull \vbox (badness 10000) has occurred while \output is active []
Overfull \vbox (701.0pt too high) has occurred while \output is active []
- [11]
+ [12]
Package epstopdf Info: Source file: <figure5.eps>
(epstopdf) date: 2015-02-06 11:42:02
(epstopdf) size: 29526 bytes
(epstopdf) size: 12638 bytes
(epstopdf) Command: <repstopdf --outfile=figure5-eps-converted-to.p
df figure5.eps>
-(epstopdf) \includegraphics on input line 734.
+(epstopdf) \includegraphics on input line 738.
Package epstopdf Info: Output file is already uptodate.
-<figure5-eps-converted-to.pdf, id=77, 484.81125pt x 350.30875pt>
+<figure5-eps-converted-to.pdf, id=81, 484.81125pt x 350.30875pt>
File: figure5-eps-converted-to.pdf Graphic file (type pdf)
<use figure5-eps-converted-to.pdf>
-Package pdftex.def Info: figure5-eps-converted-to.pdf used on input line 734.
+Package pdftex.def Info: figure5-eps-converted-to.pdf used on input line 738.
(pdftex.def) Requested size: 242.40503pt x 175.15395pt.
-
-
-LaTeX Warning: `!h' float specifier changed to `!ht'.
-
Package epstopdf Info: Source file: <figure6.eps>
(epstopdf) date: 2015-02-06 11:42:02
(epstopdf) size: 29515 bytes
(epstopdf) size: 12695 bytes
(epstopdf) Command: <repstopdf --outfile=figure6-eps-converted-to.p
df figure6.eps>
-(epstopdf) \includegraphics on input line 756.
+(epstopdf) \includegraphics on input line 760.
Package epstopdf Info: Output file is already uptodate.
-<figure6-eps-converted-to.pdf, id=78, 484.81125pt x 350.30875pt>
+
+<figure6-eps-converted-to.pdf, id=82, 484.81125pt x 350.30875pt>
File: figure6-eps-converted-to.pdf Graphic file (type pdf)
<use figure6-eps-converted-to.pdf>
-Package pdftex.def Info: figure6-eps-converted-to.pdf used on input line 756.
+Package pdftex.def Info: figure6-eps-converted-to.pdf used on input line 760.
(pdftex.def) Requested size: 242.40503pt x 175.15395pt.
Underfull \vbox (badness 10000) has occurred while \output is active []
Overfull \vbox (701.0pt too high) has occurred while \output is active []
- [12]
+ [13 <./figure5-eps-converted-to.pdf> <./figure6-eps-converted-to.pdf>]
Package epstopdf Info: Source file: <figure7a.eps>
(epstopdf) date: 2015-02-06 11:42:02
(epstopdf) size: 24136 bytes
(epstopdf) size: 8179 bytes
(epstopdf) Command: <repstopdf --outfile=figure7a-eps-converted-to.
pdf figure7a.eps>
-(epstopdf) \includegraphics on input line 779.
+(epstopdf) \includegraphics on input line 783.
Package epstopdf Info: Output file is already uptodate.
-<figure7a-eps-converted-to.pdf, id=82, 493.845pt x 350.30875pt>
+<figure7a-eps-converted-to.pdf, id=97, 493.845pt x 350.30875pt>
File: figure7a-eps-converted-to.pdf Graphic file (type pdf)
<use figure7a-eps-converted-to.pdf>
-Package pdftex.def Info: figure7a-eps-converted-to.pdf used on input line 779.
+Package pdftex.def Info: figure7a-eps-converted-to.pdf used on input line 783.
(pdftex.def) Requested size: 234.5788pt x 166.39838pt.
Package epstopdf Info: Source file: <figure7b.eps>
(epstopdf) date: 2015-02-06 11:42:02
(epstopdf) size: 8180 bytes
(epstopdf) Command: <repstopdf --outfile=figure7b-eps-converted-to.
pdf figure7b.eps>
-(epstopdf) \includegraphics on input line 780.
+(epstopdf) \includegraphics on input line 784.
Package epstopdf Info: Output file is already uptodate.
-<figure7b-eps-converted-to.pdf, id=83, 493.845pt x 350.30875pt>
+<figure7b-eps-converted-to.pdf, id=98, 493.845pt x 350.30875pt>
File: figure7b-eps-converted-to.pdf Graphic file (type pdf)
<use figure7b-eps-converted-to.pdf>
-Package pdftex.def Info: figure7b-eps-converted-to.pdf used on input line 780.
+Package pdftex.def Info: figure7b-eps-converted-to.pdf used on input line 784.
(pdftex.def) Requested size: 234.5788pt x 166.39838pt.
-
-
-LaTeX Warning: `!h' float specifier changed to `!ht'.
-
-
-Underfull \vbox (badness 10000) has occurred while \output is active []
-
-
-Underfull \vbox (badness 10000) has occurred while \output is active []
-
-
-Underfull \vbox (badness 10000) has occurred while \output is active []
-
-
-Overfull \vbox (36.0pt too high) has occurred while \output is active []
-
-
-Overfull \vbox (36.0pt too high) has occurred while \output is active []
-
-
-Overfull \vbox (650.43pt too high) has occurred while \output is active []
-
-
-Overfull \vbox (29.0pt too high) has occurred while \output is active []
-
-
-Overfull \vbox (701.0pt too high) has occurred while \output is active []
-
- [13 <./figure5-eps-converted-to.pdf> <./figure6-eps-converted-to.pdf>]
Package epstopdf Info: Source file: <figure8a.eps>
(epstopdf) date: 2015-02-06 11:42:03
(epstopdf) size: 24103 bytes
(epstopdf) size: 8351 bytes
(epstopdf) Command: <repstopdf --outfile=figure8a-eps-converted-to.
pdf figure8a.eps>
-(epstopdf) \includegraphics on input line 806.
+(epstopdf) \includegraphics on input line 810.
Package epstopdf Info: Output file is already uptodate.
-<figure8a-eps-converted-to.pdf, id=98, 493.845pt x 350.30875pt>
+<figure8a-eps-converted-to.pdf, id=99, 493.845pt x 350.30875pt>
File: figure8a-eps-converted-to.pdf Graphic file (type pdf)
<use figure8a-eps-converted-to.pdf>
-Package pdftex.def Info: figure8a-eps-converted-to.pdf used on input line 806.
+Package pdftex.def Info: figure8a-eps-converted-to.pdf used on input line 810.
(pdftex.def) Requested size: 234.5788pt x 166.39838pt.
Package epstopdf Info: Source file: <figure8b.eps>
(epstopdf) date: 2015-02-06 11:42:03
(epstopdf) size: 8466 bytes
(epstopdf) Command: <repstopdf --outfile=figure8b-eps-converted-to.
pdf figure8b.eps>
-(epstopdf) \includegraphics on input line 807.
+(epstopdf) \includegraphics on input line 811.
Package epstopdf Info: Output file is already uptodate.
-<figure8b-eps-converted-to.pdf, id=99, 493.845pt x 350.30875pt>
+<figure8b-eps-converted-to.pdf, id=100, 493.845pt x 350.30875pt>
File: figure8b-eps-converted-to.pdf Graphic file (type pdf)
<use figure8b-eps-converted-to.pdf>
-Package pdftex.def Info: figure8b-eps-converted-to.pdf used on input line 807.
+Package pdftex.def Info: figure8b-eps-converted-to.pdf used on input line 811.
(pdftex.def) Requested size: 234.5788pt x 166.39838pt.
+Underfull \vbox (badness 10000) has occurred while \output is active []
+
+
+Underfull \vbox (badness 10000) has occurred while \output is active []
+
+
+Underfull \vbox (badness 10000) has occurred while \output is active []
+
+
+Overfull \vbox (36.0pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (36.0pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (650.43pt too high) has occurred while \output is active []
-LaTeX Warning: `!h' float specifier changed to `!ht'.
+Overfull \vbox (29.0pt too high) has occurred while \output is active []
+
+
+Overfull \vbox (701.0pt too high) has occurred while \output is active []
+
+ [14 <./figure7a-eps-converted-to.pdf> <./figure7b-eps-converted-to.pdf>]
Package epstopdf Info: Source file: <figure9.eps>
(epstopdf) date: 2015-02-06 11:42:03
(epstopdf) size: 27000 bytes
(epstopdf) size: 7927 bytes
(epstopdf) Command: <repstopdf --outfile=figure9-eps-converted-to.p
df figure9.eps>
-(epstopdf) \includegraphics on input line 829.
+(epstopdf) \includegraphics on input line 833.
Package epstopdf Info: Output file is already uptodate.
-<figure9-eps-converted-to.pdf, id=100, 484.81125pt x 350.30875pt>
+
+<figure9-eps-converted-to.pdf, id=114, 484.81125pt x 350.30875pt>
File: figure9-eps-converted-to.pdf Graphic file (type pdf)
<use figure9-eps-converted-to.pdf>
-Package pdftex.def Info: figure9-eps-converted-to.pdf used on input line 829.
+Package pdftex.def Info: figure9-eps-converted-to.pdf used on input line 833.
(pdftex.def) Requested size: 242.40503pt x 175.15395pt.
LaTeX Warning: `!h' float specifier changed to `!ht'.
+LaTeX Warning: `h' float specifier changed to `ht'.
+
+
Underfull \vbox (badness 10000) has occurred while \output is active []
Overfull \vbox (701.0pt too high) has occurred while \output is active []
- [14 <./figure7a-eps-converted-to.pdf> <./figure7b-eps-converted-to.pdf>]
-
-LaTeX Warning: `h' float specifier changed to `ht'.
-
-
+ [15 <./figure8a-eps-converted-to.pdf> <./figure8b-eps-converted-to.pdf>]
+(./articleeo.bbl
Underfull \vbox (badness 10000) has occurred while \output is active []
Overfull \vbox (701.0pt too high) has occurred while \output is active []
- [15 <./figure8a-eps-converted-to.pdf> <./figure8b-eps-converted-to.pdf> <./fig
-ure9-eps-converted-to.pdf>] (./articleeo.bbl
+ [16 <./figure9-eps-converted-to.pdf>]
+Underfull \vbox (badness 10000) has occurred while \output is active []
+
+
Underfull \vbox (badness 10000) has occurred while \output is active []
Overfull \vbox (701.0pt too high) has occurred while \output is active []
- [16]
-Underfull \hbox (badness 4024) in paragraph at lines 120--122
+ [17]
+Underfull \hbox (badness 4024) in paragraph at lines 126--128
[]\OT1/cmr/m/n/10 Makhorin, An-drew. 2012. ``The GLPK (GNU Lin-ear Pro-gram-min
g Kit).'' \OT1/cmr/m/it/10 Avail-able:
[]
Missing character: There is no à in font cmr10!
Missing character: There is no © in font cmr10!
-Underfull \hbox (badness 10000) in paragraph at lines 167--169
+Underfull \hbox (badness 10000) in paragraph at lines 173--175
[]\OT1/cmr/m/n/10 Varga, A. 2003. ``OM-NeT++ Dis-crete Event Sim-u-la-tion Sys-
tem.'' \OT1/cmr/m/it/10 Avail-able:
[]
Overfull \vbox (701.0pt too high) has occurred while \output is active []
- [17])
+ [18])
Underfull \vbox (badness 10000) has occurred while \output is active []
Overfull \vbox (701.0pt too high) has occurred while \output is active []
- [18]
+ [19]
(./articleeo.aux)
LaTeX Font Warning: Size substitutions with differences
)
Here is how much of TeX's memory you used:
- 3709 strings out of 495059
- 48103 string characters out of 3182031
- 115292 words of memory out of 3000000
- 6817 multiletter control sequences out of 15000+200000
+ 3712 strings out of 495059
+ 48196 string characters out of 3182031
+ 114324 words of memory out of 3000000
+ 6820 multiletter control sequences out of 15000+200000
14560 words of font info for 56 fonts, out of 3000000 for 9000
14 hyphenation exceptions out of 8191
- 41i,14n,27p,748b,327s stack positions out of 5000i,500n,10000p,200000b,50000s
+ 41i,14n,27p,839b,355s stack positions out of 5000i,500n,10000p,200000b,50000s
</usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmbx10.pfb></us
r/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmbx9.pfb></usr/share
/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmbxti10.pfb></usr/share/tex
st/fonts/type1/public/amsfonts/cm/cmsy7.pfb></usr/share/texlive/texmf-dist/font
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, 737681 bytes).
+c/amsfonts/cm/cmti8.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfo
+nts/symbols/msbm10.pfb>
+Output written on articleeo.pdf (19 pages, 743136 bytes).
PDF statistics:
- 205 PDF objects out of 1000 (max. 8388607)
- 139 compressed objects within 2 object streams
+ 213 PDF objects out of 1000 (max. 8388607)
+ 145 compressed objects within 2 object streams
0 named destinations out of 1000 (max. 500000)
61 words of extra memory for PDF output out of 10000 (max. 10000000)
simulator OMNeT++, to demonstrate the efficiency of our protocol. We have compared
our PeCO protocol to two approaches found in the literature:
DESK~\citep{ChinhVu} and GAF~\citep{xu2001geography}, and also to our previous
- work published in~\citep{Idrees2} which is based on another optimization model
- for sensor scheduling.
+ protocol DilCO published in~\citep{Idrees2}. DilCO uses the same framework as PeCO but is based on another optimization model for sensor scheduling.
\end{enumerate}
-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
+The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage Optimization (DiLCO) protocol, which 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
\section{ The P{\scshape e}CO Protocol Description}
\label{sec:The PeCO Protocol Description}
-In this section, the Perimeter-based Coverage
-Optimization protocol is decribed in details. First we present the assumptions we made and the models
-we considered (in particular the perimeter coverage one), second we describe the
-background idea of our protocol, and third we give the outline of the algorithm
-executed by each node.
+%In this section, the Perimeter-based Coverage
+%Optimization protocol is decribed in details. First we present the assumptions we made and the models
+%we considered (in particular the perimeter coverage one), second we describe the
+%background idea of our protocol, and third we give the outline of the algorithm
+%executed by each node.
\subsection{Assumptions and Models}
Every couple of intersection points is placed on the angular interval $[0,2\pi)$
in a counterclockwise manner, leading to a partitioning of the interval.
Figure~\ref{figure1}(a) illustrates the arcs for the nine neighbors of
-sensor $0$ and Figure~\ref{figure2} gives the position of the corresponding arcs
+sensor $0$ and table~\ref{my-label} gives the position of the corresponding arcs
in the interval $[0,2\pi)$. More precisely, the points are
ordered according to the measures of the angles defined by their respective
positions. The intersection points are then visited one after another, starting
In the PeCO protocol, the scheduling of the sensor nodes' activities is formulated with an
-integer program based on coverage intervals. The formulation of the coverage
+mixed-doi:10.1155/2010/926075integer program based on coverage intervals. The formulation of the coverage
optimization problem is detailed in~Section~\ref{cp}. Note that when a sensor
node has a part of its sensing range outside the WSN sensing field, as in
Figure~\ref{figure3}, the maximum coverage level for this arc is set to $\infty$
The WSN area of interest is, in a first step, divided into regular
homogeneous subregions using a divide-and-conquer algorithm. In a second step
our protocol will be executed in a distributed way in each subregion
-simultaneously to schedule nodes' activities for one sensing period.
+simultaneously to schedule nodes' activities for one sensing period. In the study, sensors are assumed to be deployed almost uniformly over the region. The regular subdivision is made such that the number of hops between any pairs of sensors inside a subregion is less than or equal to 3.
As shown in Figure~\ref{figure4}, node activity scheduling is produced by our
protocol in a periodic manner. Each period is divided into 4 stages: Information
information (including their residual energy) at the beginning of each period.
However, the pre-sensing phases (INFO Exchange, Leader Election, and Decision)
are energy consuming, even for nodes that will not join the set cover to monitor
-the area.
+the area. Sensing period duration is adapted according to the QoS requirements of the application.
\begin{figure}[t!]
\centering
\section{Perimeter-based Coverage Problem Formulation}
\label{cp}
-In this section, the coverage model is mathematically formulated. The following
-notations are used throughout the
+In this section, the perimeter-based coverage problem is mathematically formulated. It has been proved to be a NP-hard problem by\citep{doi:10.1155/2010/926075}. Authors study the coverage of the perimeter of a large object requiring to be monitored. For the proposed formulation in this paper, the large object to be monitored is the sensor itself (or more precisely its sensing area).
+
+The following notations are used throughout the
section.\\
First, the following sets:
\begin{itemize}
\end{equation}
Note that $a^k_{ik}=1$ by definition of the interval.
-Second, several binary and integer variables are defined. Hence, each binary
+Second, several variables are defined. Hence, each binary
variable $X_{k}$ determines the activation of sensor $k$ in the sensing phase
-($X_k=1$ if the sensor $k$ is active or 0 otherwise). $M^j_i$ is an integer
+($X_k=1$ if the sensor $k$ is active or 0 otherwise). $M^j_i$ is a
variable which measures the undercoverage for the coverage interval $i$
corresponding to sensor~$j$. In the same way, the overcoverage for the same
coverage interval is given by the variable $V^j_i$.
-If we decide to sustain a level of coverage equal to $l$ all along the perimeter
-of sensor $j$, we have to ensure that at least $l$ sensors involved in each
-coverage interval $i \in I_j$ of sensor $j$ are active. According to the
+To sustain a level of coverage equal to $l$ all along the perimeter
+of sensor $j$, at least $l$ sensors involved in each
+coverage interval $i \in I_j$ of sensor $j$ have to be active. According to the
previous notations, the number of active sensors in the coverage interval $i$ of
sensor $j$ is given by $\sum_{k \in A} a^j_{ik} X_k$. To extend the network
lifetime, the objective is to activate a minimal number of sensors in each
-Our coverage optimization problem can then be mathematically expressed as follows:
+The coverage optimization problem can then be mathematically expressed as follows:
\begin{equation}
\left \{
\textrm{subject to :}&\\
\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
+X_{k} \in \{0,1\}, \forall k \in A \\
M^j_i, V^j_i \in \mathbb{R}^{+}
\end{array}
\right.
\end{equation}
+If a given level of coverage $l$ is required for one sensor, the sensor is said to be undercovered (respectively overcovered) if the level of coverage of one of its CI is less (respectively greater) than $l$. If the sensor $j$ is undercovered, there exists at least one of its CI (say $i$) for which the number of active sensors (denoted by $l^{i}$) covering this part of the perimeter is less than $l$ and in this case : $M_{i}^{j}=l-l^{i}$, $V_{i}^{j}=0$. In the contrary, if the sensor $j$ is overcovered, there exists at least one of its CI (say $i$) 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$.
+
$\alpha^j_i$ and $\beta^j_i$ are nonnegative weights selected according to the
relative importance of satisfying the associated level of coverage. For example,
weights associated with coverage intervals of a specified part of a region may
be given by a relatively larger magnitude than weights associated with another
-region. This kind of integer program is inspired from the model developed for
+region. This kind of mixed-integer program is inspired from the model developed for
brachytherapy treatment planning for optimizing dose distribution
-\citep{0031-9155-44-1-012}. The integer program must be solved by the leader in
+\citep{0031-9155-44-1-012}. The choice of variables $\alpha$ and $\beta$ should be made according to the needs of the application. $\alpha$ should be enough large to prevent undercoverage and so to reach the highest possible coverage ratio. $\beta$ should be enough large to prevent overcoverage and so to activate a minimum number of sensors.
+The mixed-integer program must be solved by the leader in
each subregion at the beginning of each sensing phase, whenever the environment
has changed (new leader, death of some sensors). Note that the number of
constraints in the model is constant (constraints of coverage expressed for all
sensors), whereas the number of variables $X_k$ decreases over periods, since
only alive sensors (sensors with enough energy to be alive during one
-sensing phase) are considered in the model.
+sensing phase) are considered in the model.
\section{Performance Evaluation and Analysis}
\label{sec:Simulation Results and Analysis}
is about twice longer with PeCO compared to DESK protocol. The performance
difference is more obvious in Figure~\ref{figure8}(b) than in
Figure~\ref{figure8}(a) because the gain induced by our protocols increases with
- time, and the lifetime with a coverage of 50\% is far longer than with
-95\%.
+ time, and the lifetime with a coverage over 50\% is far longer than with
+95\%.
\begin{figure}[h!]
\centering
\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}$.
+Table~\ref{my-labelx} shows network lifetime results for the different values of $\alpha$ and $\beta$, and for a network size equal to 200 sensor nodes. The choice of $\beta \gg \alpha$ prevents the overcoverage, and so limit the activation of a large number of sensors, but as $\alpha$ is low, some areas may be poorly covered. This explains the results obtained for {\it Lifetime50} with $\beta \gg \alpha$: a large number of periods with low coverage ratio. With $\alpha \gg \beta$, we priviligie the coverage even if some areas may be overcovered, so high coverage ratio is reached, but a large number of sensors are activated to achieve this goal. Therefore network lifetime is reduced. The choice $\alpha=0.6$ and $\beta=0.4$ seems to achieve the best compromise between lifetime and coverage ratio.
+%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
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
+{\bf 0.6} & {\bf 0.4} & {\bf 94} & {\bf 57} \\ \hline
0.7 & 0.3 & 97 & 49 \\ \hline
0.8 & 0.2 & 90 & 52 \\ \hline
0.9 & 0.1 & 77 & 50 \\ \hline
simulator OMNeT++, to demonstrate the efficiency of our protocol. We have compared
our PeCO protocol to two approaches found in the literature:
DESK~\citep{ChinhVu} and GAF~\citep{xu2001geography}, and also to our previous
- work published in~\citep{Idrees2} which is based on another optimization model
- for sensor scheduling.
+ protocol DilCO published in~\citep{Idrees2}. DilCO uses the same framework as PeCO but is based on another optimization model for sensor scheduling.
\end{enumerate}
-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
+The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage Optimization (DiLCO) protocol, which 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
\section{ The P{\scshape e}CO Protocol Description}
\label{sec:The PeCO Protocol Description}
-In this section, the Perimeter-based Coverage
-Optimization protocol is decribed in details. First we present the assumptions we made and the models
-we considered (in particular the perimeter coverage one), second we describe the
-background idea of our protocol, and third we give the outline of the algorithm
-executed by each node.
+%In this section, the Perimeter-based Coverage
+%Optimization protocol is decribed in details. First we present the assumptions we made and the models
+%we considered (in particular the perimeter coverage one), second we describe the
+%background idea of our protocol, and third we give the outline of the algorithm
+%executed by each node.
\subsection{Assumptions and Models}
Every couple of intersection points is placed on the angular interval $[0,2\pi)$
in a counterclockwise manner, leading to a partitioning of the interval.
Figure~\ref{figure1}(a) illustrates the arcs for the nine neighbors of
-sensor $0$ and Figure~\ref{figure2} gives the position of the corresponding arcs
+sensor $0$ and table~\ref{my-label} gives the position of the corresponding arcs
in the interval $[0,2\pi)$. More precisely, the points are
ordered according to the measures of the angles defined by their respective
positions. The intersection points are then visited one after another, starting
In the PeCO protocol, the scheduling of the sensor nodes' activities is formulated with an
-integer program based on coverage intervals. The formulation of the coverage
+mixed-doi:10.1155/2010/926075integer program based on coverage intervals. The formulation of the coverage
optimization problem is detailed in~Section~\ref{cp}. Note that when a sensor
node has a part of its sensing range outside the WSN sensing field, as in
Figure~\ref{figure3}, the maximum coverage level for this arc is set to $\infty$
The WSN area of interest is, in a first step, divided into regular
homogeneous subregions using a divide-and-conquer algorithm. In a second step
our protocol will be executed in a distributed way in each subregion
-simultaneously to schedule nodes' activities for one sensing period.
+simultaneously to schedule nodes' activities for one sensing period. In the study, sensors are assumed to be deployed almost uniformly over the region. The regular subdivision is made such that the number of hops between any pairs of sensors inside a subregion is less than or equal to 3.
As shown in Figure~\ref{figure4}, node activity scheduling is produced by our
protocol in a periodic manner. Each period is divided into 4 stages: Information
information (including their residual energy) at the beginning of each period.
However, the pre-sensing phases (INFO Exchange, Leader Election, and Decision)
are energy consuming, even for nodes that will not join the set cover to monitor
-the area.
+the area. Sensing period duration is adapted according to the QoS requirements of the application.
\begin{figure}[t!]
\centering
\section{Perimeter-based Coverage Problem Formulation}
\label{cp}
-In this section, the coverage model is mathematically formulated. The following
-notations are used throughout the
+In this section, the perimeter-based coverage problem is mathematically formulated. It has been proved to be a NP-hard problem by\citep{doi:10.1155/2010/926075}. Authors study the coverage of the perimeter of a large object requiring to be monitored. For the proposed formulation in this paper, the large object to be monitored is the sensor itself (or more precisely its sensing area).
+
+The following notations are used throughout the
section.\\
First, the following sets:
\begin{itemize}
\end{equation}
Note that $a^k_{ik}=1$ by definition of the interval.
-Second, several binary and integer variables are defined. Hence, each binary
+Second, several variables are defined. Hence, each binary
variable $X_{k}$ determines the activation of sensor $k$ in the sensing phase
-($X_k=1$ if the sensor $k$ is active or 0 otherwise). $M^j_i$ is an integer
+($X_k=1$ if the sensor $k$ is active or 0 otherwise). $M^j_i$ is a
variable which measures the undercoverage for the coverage interval $i$
corresponding to sensor~$j$. In the same way, the overcoverage for the same
coverage interval is given by the variable $V^j_i$.
-If we decide to sustain a level of coverage equal to $l$ all along the perimeter
-of sensor $j$, we have to ensure that at least $l$ sensors involved in each
-coverage interval $i \in I_j$ of sensor $j$ are active. According to the
+To sustain a level of coverage equal to $l$ all along the perimeter
+of sensor $j$, at least $l$ sensors involved in each
+coverage interval $i \in I_j$ of sensor $j$ have to be active. According to the
previous notations, the number of active sensors in the coverage interval $i$ of
sensor $j$ is given by $\sum_{k \in A} a^j_{ik} X_k$. To extend the network
lifetime, the objective is to activate a minimal number of sensors in each
-Our coverage optimization problem can then be mathematically expressed as follows:
+The coverage optimization problem can then be mathematically expressed as follows:
\begin{equation}
\left \{
\textrm{subject to :}&\\
\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
+X_{k} \in \{0,1\}, \forall k \in A \\
+M^j_i, V^j_i \in \mathbb{R}^{+}
\end{array}
\right.
\end{equation}
+If a given level of coverage $l$ is required for one sensor, the sensor is said to be undercovered (respectively overcovered) if the level of coverage of one of its CI is less (respectively greater) than $l$. If the sensor $j$ is undercovered, there exists at least one of its CI (say $i$) for which the number of active sensors (denoted by $l^{i}$) covering this part of the perimeter is less than $l$ and in this case : $M_{i}^{j}=l-l^{i}$, $V_{i}^{j}=0$. In the contrary, if the sensor $j$ is overcovered, there exists at least one of its CI (say $i$) 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$.
+
$\alpha^j_i$ and $\beta^j_i$ are nonnegative weights selected according to the
relative importance of satisfying the associated level of coverage. For example,
weights associated with coverage intervals of a specified part of a region may
be given by a relatively larger magnitude than weights associated with another
-region. This kind of integer program is inspired from the model developed for
+region. This kind of mixed-integer program is inspired from the model developed for
brachytherapy treatment planning for optimizing dose distribution
-\citep{0031-9155-44-1-012}. The integer program must be solved by the leader in
+\citep{0031-9155-44-1-012}. The choice of variables $\alpha$ and $\beta$ should be made according to the needs of the application. $\alpha$ should be enough large to prevent undercoverage and so to reach the highest possible coverage ratio. $\beta$ should be enough large to prevent overcoverage and so to activate a minimum number of sensors.
+The mixed-integer program must be solved by the leader in
each subregion at the beginning of each sensing phase, whenever the environment
has changed (new leader, death of some sensors). Note that the number of
constraints in the model is constant (constraints of coverage expressed for all
sensors), whereas the number of variables $X_k$ decreases over periods, since
only alive sensors (sensors with enough energy to be alive during one
-sensing phase) are considered in the model.
+sensing phase) are considered in the model.
\section{Performance Evaluation and Analysis}
\label{sec:Simulation Results and Analysis}
is about twice longer with PeCO compared to DESK protocol. The performance
difference is more obvious in Figure~\ref{figure8}(b) than in
Figure~\ref{figure8}(a) because the gain induced by our protocols increases with
- time, and the lifetime with a coverage of 50\% is far longer than with
-95\%.
+ time, and the lifetime with a coverage over 50\% is far longer than with
+95\%.
\begin{figure}[h!]
\centering
\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}$.
+Table~\ref{my-labelx} shows network lifetime results for the different values of $\alpha$ and $\beta$, and for a network size equal to 200 sensor nodes. The choice of $\beta \gg \alpha$ prevents the overcoverage, and so limit the activation of a large number of sensors, but as $\alpha$ is low, some areas may be poorly covered. This explains the results obtained for {\it Lifetime50} with $\beta \gg \alpha$: a large number of periods with low coverage ratio. With $\alpha \gg \beta$, we priviligie the coverage even if some areas may be overcovered, so high coverage ratio is reached, but a large number of sensors are activated to achieve this goal. Therefore network lifetime is reduced. The choice $\alpha=0.6$ and $\beta=0.4$ seems to achieve the best compromise between lifetime and coverage ratio.
+%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
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
+{\bf 0.6} & {\bf 0.4} & {\bf 94} & {\bf 57} \\ \hline
0.7 & 0.3 & 97 & 49 \\ \hline
0.8 & 0.2 & 90 & 52 \\ \hline
0.9 & 0.1 & 77 & 50 \\ \hline
@article{doi:10.1080/0305215X.2012.687732,
author = {Singh, Alok and Rossi, André and Sevaux, Marc},
-title = {Matheuristic approaches for Q-coverage problem versions in wireless sensor networks},
+title = {Metaheuristic approaches for Q-coverage problem versions in wireless sensor networks},
journal = {Engineering Optimization},
volume = {45},
number = {5},
year = {2013}
}
+@article{doi:10.1155/2010/926075,
+author = {Hung, Ka-Shun and Lui, King-Shan},
+title = {Perimeter Coverage Scheduling in Wireless Sensor Networks Using Sensors with a Single Continuous Cover Range},
+journal = {EURASIP Journal on Wireless Communications and Networking },
+volume = {2010},
+year = {2010}
+}
+
+
\noindent {\bf 8.} Since this paper is attacking the coverage problem, I would like to see more information on the amount of coverage the algorithm is achieving. It seems that there is a tradeoff in this algorithm that allows the network to increase its lifetime but does not improve the coverage ratio. This may be an issue if this approach is used in an application that requires high coverage ratio. \\
-\textcolor{blue}{\textbf{\textsc{Answer:} Your remark is interesting. Indeed, figures 8(a) and (b) highlight this result. PeCO methods allows to achieve a coverage ratio greater than $50\%$ for many more periods than the others three methods, but for applications requiring an high level of coverage (greater than $95\%$), DilCO method is more efficient. }}\\
+\textcolor{blue}{\textbf{\textsc{Answer:} Your remark is interesting. Indeed, figures 8(a) and (b) highlight this result. PeCO methods allows to achieve a coverage ratio greater than $50\%$ for many more periods than the others three methods, but for applications requiring an high level of coverage (greater than $95\%$), DilCO method is more efficient. It is explained at the end of section 5.2.4. }}\\
-%%%%%%%%%%%%%%%%%%%%%% ENGLISH and GRAMMER %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%% ENGLISH and GRAMMAR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent\textcolor{black}{\textbf{\Large English and Grammar:}} \\
\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:} 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. }}\\
+\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. \\
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 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:
+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 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 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.
\\
\begin{tabular}{|c|c|c|c|c|c|r|}
\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 solutions (Reference : "A feasibility pump heuristic for general mixed-integer problems", Livio Bertacco and Matteo Fischetti and Andrea Lodi, Discrete Optimization, issn 1572-5286).
+\\
+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}}}\\
\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:} }}.\\
+\textcolor{blue}{\textbf{\textsc{Answer:} Right. This observation has been added at the end of the introduction}}.\\
\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. A FAIRE }}.\\
+\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"} \\
