From: Karine Deschinkel Date: Fri, 19 Jun 2015 13:31:28 +0000 (+0200) Subject: modif biblio, article, reponse X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/LiCO.git/commitdiff_plain/8d0a87bd6a095ec213dc2af5220c6e4904f7e4c0?ds=inline;hp=a46087d6b626d4b027a6df8254829981f14e602d modif biblio, article, reponse --- diff --git a/PeCO-EO/articleeo.aux b/PeCO-EO/articleeo.aux index d9dd414..c627b72 100644 --- a/PeCO-EO/articleeo.aux +++ b/PeCO-EO/articleeo.aux @@ -44,6 +44,8 @@ \@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}} @@ -52,7 +54,7 @@ \@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} @@ -62,20 +64,21 @@ \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}}{{}}} @@ -84,39 +87,39 @@ \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{} diff --git a/PeCO-EO/articleeo.bbl b/PeCO-EO/articleeo.bbl index a03bf2a..b052e26 100644 --- a/PeCO-EO/articleeo.bbl +++ b/PeCO-EO/articleeo.bbl @@ -1,4 +1,4 @@ -\begin{thebibliography}{42} +\begin{thebibliography}{43} \newcommand{\enquote}[1]{``#1''} \providecommand{\natexlab}[1]{#1} \providecommand{\url}[1]{\normalfont{#1}} @@ -75,6 +75,12 @@ Huang, Chi-Fu, and Yu-Chee Tseng. 2005{\natexlab{b}}. ``The coverage problem in 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 @@ -153,9 +159,9 @@ Rault, Tifenn, Abdelmadjid Bouabdallah, and Yacine Challal. 2014. ``Energy 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 diff --git a/PeCO-EO/articleeo.blg b/PeCO-EO/articleeo.blg index b217694..d6a07f6 100644 --- a/PeCO-EO/articleeo.blg +++ b/PeCO-EO/articleeo.blg @@ -2,46 +2,46 @@ This is BibTeX, Version 0.99d (TeX Live 2012/Debian) 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 diff --git a/PeCO-EO/articleeo.log b/PeCO-EO/articleeo.log index 9d9db3b..1705ea3 100644 --- a/PeCO-EO/articleeo.log +++ b/PeCO-EO/articleeo.log @@ -1,4 +1,4 @@ -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. @@ -503,33 +503,8 @@ Overfull \vbox (701.0pt too high) has occurred while \output is active [] [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: (epstopdf) date: 2015-02-20 10:11:12 (epstopdf) size: 358485 bytes @@ -538,14 +513,13 @@ Package epstopdf Info: Source file: (epstopdf) size: 78307 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 255. +(epstopdf) \includegraphics on input line 254. Package epstopdf Info: Output file is already uptodate. - - + File: figure1a-eps-converted-to.pdf Graphic file (type 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: (epstopdf) date: 2015-02-20 10:11:12 @@ -555,14 +529,14 @@ Package epstopdf Info: Source file: (epstopdf) size: 57181 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 256. +(epstopdf) \includegraphics on input line 255. Package epstopdf Info: Output file is already uptodate. - + File: figure1b-eps-converted-to.pdf Graphic file (type 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 [] @@ -586,6 +560,30 @@ 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] +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>] @@ -597,14 +595,14 @@ Package epstopdf Info: Source file: (epstopdf) size: 138861 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 299. +(epstopdf) \includegraphics on input line 298. Package epstopdf Info: Output file is already uptodate. File: figure2-eps-converted-to.pdf Graphic file (type 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 [] @@ -639,14 +637,14 @@ Package epstopdf Info: Source file: (epstopdf) size: 48639 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 349. +(epstopdf) \includegraphics on input line 348. Package epstopdf Info: Output file is already uptodate. File: figure3-eps-converted-to.pdf Graphic file (type 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: (epstopdf) date: 2015-02-20 10:11:12 @@ -656,14 +654,14 @@ Package epstopdf Info: Source file: (epstopdf) size: 76496 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 382. +(epstopdf) \includegraphics on input line 381. Package epstopdf Info: Output file is already uptodate. File: figure4-eps-converted-to.pdf Graphic file (type 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 [] @@ -763,23 +761,40 @@ Overfull \vbox (701.0pt too high) 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. @@ -787,6 +802,14 @@ LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 677. +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 [] @@ -810,7 +833,7 @@ 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] + [12] Package epstopdf Info: Source file: (epstopdf) date: 2015-02-06 11:42:02 (epstopdf) size: 29526 bytes @@ -819,19 +842,15 @@ Package epstopdf Info: Source file: (epstopdf) size: 12638 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 734. +(epstopdf) \includegraphics on input line 738. Package epstopdf Info: Output file is already uptodate. - + File: figure5-eps-converted-to.pdf Graphic file (type 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: (epstopdf) date: 2015-02-06 11:42:02 (epstopdf) size: 29515 bytes @@ -840,13 +859,14 @@ Package epstopdf Info: Source file: (epstopdf) size: 12695 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 756. +(epstopdf) \includegraphics on input line 760. Package epstopdf Info: Output file is already uptodate. - + + File: figure6-eps-converted-to.pdf Graphic file (type 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 [] @@ -872,7 +892,7 @@ Overfull \vbox (29.0pt too high) 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: (epstopdf) date: 2015-02-06 11:42:02 (epstopdf) size: 24136 bytes @@ -881,14 +901,14 @@ Package epstopdf Info: Source file: (epstopdf) size: 8179 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 779. +(epstopdf) \includegraphics on input line 783. Package epstopdf Info: Output file is already uptodate. - + File: figure7a-eps-converted-to.pdf Graphic file (type 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: (epstopdf) date: 2015-02-06 11:42:02 @@ -898,44 +918,15 @@ Package epstopdf Info: Source file: (epstopdf) size: 8180 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 780. +(epstopdf) \includegraphics on input line 784. Package epstopdf Info: Output file is already uptodate. - + File: figure7b-eps-converted-to.pdf Graphic file (type 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: (epstopdf) date: 2015-02-06 11:42:03 (epstopdf) size: 24103 bytes @@ -944,14 +935,14 @@ Package epstopdf Info: Source file: (epstopdf) size: 8351 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 806. +(epstopdf) \includegraphics on input line 810. Package epstopdf Info: Output file is already uptodate. - + File: figure8a-eps-converted-to.pdf Graphic file (type 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: (epstopdf) date: 2015-02-06 11:42:03 @@ -961,19 +952,40 @@ Package epstopdf Info: Source file: (epstopdf) size: 8466 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 807. +(epstopdf) \includegraphics on input line 811. Package epstopdf Info: Output file is already uptodate. - + File: figure8b-eps-converted-to.pdf Graphic file (type 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: (epstopdf) date: 2015-02-06 11:42:03 (epstopdf) size: 27000 bytes @@ -982,19 +994,23 @@ Package epstopdf Info: Source file: (epstopdf) size: 7927 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 829. +(epstopdf) \includegraphics on input line 833. Package epstopdf Info: Output file is already uptodate. - + + File: figure9-eps-converted-to.pdf Graphic file (type 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 [] @@ -1018,11 +1034,8 @@ 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>] - -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 [] @@ -1046,8 +1059,10 @@ Overfull \vbox (29.0pt too high) 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 [] @@ -1071,8 +1086,8 @@ Overfull \vbox (29.0pt too high) 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: [] @@ -1080,7 +1095,7 @@ 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: [] @@ -1112,7 +1127,7 @@ Overfull \vbox (29.0pt too high) has occurred while \output is active [] Overfull \vbox (701.0pt too high) has occurred while \output is active [] - [17]) + [18]) Underfull \vbox (badness 10000) has occurred while \output is active [] @@ -1136,7 +1151,7 @@ Overfull \vbox (29.0pt too high) 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 @@ -1147,13 +1162,13 @@ LaTeX Font Warning: Some font shapes were not available, defaults substituted. ) 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 -Output written on articleeo.pdf (18 pages, 737681 bytes). +c/amsfonts/cm/cmti8.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) diff --git a/PeCO-EO/articleeo.pdf b/PeCO-EO/articleeo.pdf index 81c171e..54c4d6d 100644 Binary files a/PeCO-EO/articleeo.pdf and b/PeCO-EO/articleeo.pdf differ diff --git a/PeCO-EO/articleeo.tex b/PeCO-EO/articleeo.tex index 0927d21..215576a 100644 --- a/PeCO-EO/articleeo.tex +++ b/PeCO-EO/articleeo.tex @@ -91,8 +91,7 @@ This paper makes the following contributions. 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} @@ -197,7 +196,7 @@ used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012col -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 @@ -209,11 +208,11 @@ on perimeter coverage of each sensor. The model involves integer variables to ca \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} @@ -278,7 +277,7 @@ The arc on the perimeter of~$u$ defined by the angular interval $[\pi 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 @@ -336,7 +335,7 @@ above is thus given by the sixth line of the table. 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$ @@ -357,7 +356,7 @@ optimization algorithm. 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 @@ -375,7 +374,7 @@ taken into account since the sensors can update and then exchange their 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 @@ -476,8 +475,9 @@ construct the set of active sensors in the sensing stage. \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} @@ -500,16 +500,16 @@ a^j_{ik} = \left \{ \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 @@ -525,7 +525,7 @@ to reach a coverage level as close as possible to the desired one. -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 \{ @@ -534,25 +534,28 @@ Our coverage optimization problem can then be mathematically expressed as follow \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} @@ -798,8 +801,8 @@ ratio greater than 50\%, we can see on Figure~\ref{figure8}(b) that the lifetim 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 @@ -834,7 +837,8 @@ not ineffective for the smallest network sizes. \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 @@ -849,7 +853,7 @@ $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \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 +{\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 diff --git a/PeCO-EO/articleeo.tex~ b/PeCO-EO/articleeo.tex~ index 96b4465..215576a 100644 --- a/PeCO-EO/articleeo.tex~ +++ b/PeCO-EO/articleeo.tex~ @@ -91,8 +91,7 @@ This paper makes the following contributions. 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} @@ -197,7 +196,7 @@ used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012col -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 @@ -209,11 +208,11 @@ on perimeter coverage of each sensor. The model involves integer variables to ca \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} @@ -278,7 +277,7 @@ The arc on the perimeter of~$u$ defined by the angular interval $[\pi 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 @@ -336,7 +335,7 @@ above is thus given by the sixth line of the table. 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$ @@ -357,7 +356,7 @@ optimization algorithm. 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 @@ -375,7 +374,7 @@ taken into account since the sensors can update and then exchange their 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 @@ -476,8 +475,9 @@ construct the set of active sensors in the sensing stage. \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} @@ -500,16 +500,16 @@ a^j_{ik} = \left \{ \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 @@ -525,7 +525,7 @@ to reach a coverage level as close as possible to the desired one. -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 \{ @@ -534,24 +534,28 @@ Our coverage optimization problem can then be mathematically expressed as follow \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} @@ -797,8 +801,8 @@ ratio greater than 50\%, we can see on Figure~\ref{figure8}(b) that the lifetim 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 @@ -833,7 +837,8 @@ not ineffective for the smallest network sizes. \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 @@ -848,7 +853,7 @@ $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \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 +{\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 diff --git a/PeCO-EO/biblio.bib b/PeCO-EO/biblio.bib index b342afa..5c93e97 100644 --- a/PeCO-EO/biblio.bib +++ b/PeCO-EO/biblio.bib @@ -1028,7 +1028,7 @@ year = {2012}, @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}, @@ -1036,4 +1036,13 @@ pages = {609-626}, 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} +} + + diff --git a/PeCO-EO/reponse.tex b/PeCO-EO/reponse.tex index 4965597..b00dd1d 100644 --- a/PeCO-EO/reponse.tex +++ b/PeCO-EO/reponse.tex @@ -101,9 +101,9 @@ s used are very vague and do not bring out their key contributions. Some referen \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:}} \\ @@ -170,7 +170,7 @@ The paper entitled "Perimeter-based Coverage Optimization to Improve Lifetime in \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. \\ @@ -179,14 +179,15 @@ The paper entitled "Perimeter-based Coverage Optimization to Improve Lifetime in 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 @@ -200,7 +201,8 @@ of nodes &&&&relaxation &B\&B tree &\\ 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}}}\\ @@ -212,7 +214,7 @@ It is noteworthy that the difference of memory used with GLPK between the resolu \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}}.\\ @@ -261,7 +263,7 @@ It is noteworthy that the difference of memory used with GLPK between the resolu \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"} \\