From: ali Date: Mon, 11 May 2015 09:04:39 +0000 (+0200) Subject: Update by Ali X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/LiCO.git/commitdiff_plain/0299cb811caaea53aec64c52be67397bc055f5c8 Update by Ali --- diff --git a/PeCO-EO/articleeo.aux b/PeCO-EO/articleeo.aux index b3e8863..d1ccafa 100644 --- a/PeCO-EO/articleeo.aux +++ b/PeCO-EO/articleeo.aux @@ -53,27 +53,27 @@ \citation{varga} \citation{AMPL} \citation{glpk} +\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Simulation Results}{11}} \citation{ChinhVu} \citation{xu2001geography} \citation{Idrees2} \citation{idrees2014coverage} -\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Simulation Results}{11}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.1}\bf Coverage Ratio}{12}} \newlabel{figure5}{{5}{12}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.2}\bf Active Sensors Ratio}{12}} \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}} -\bibstyle{gENO} -\bibdata{biblio} -\bibcite{akyildiz2002wireless}{{1}{2002}{{Akyildiz et~al.}}{{Akyildiz, Su, Sankarasubramaniam, and Cayirci}}} \newlabel{figure7}{{7}{14}} \@writefile{toc}{\contentsline {section}{\numberline {6}Conclusion and Future Works}{14}} \newlabel{sec:Conclusion and Future Works}{{6}{14}} +\bibstyle{gENO} +\bibdata{biblio} +\bibcite{akyildiz2002wireless}{{1}{2002}{{Akyildiz et~al.}}{{Akyildiz, Su, Sankarasubramaniam, and Cayirci}}} \bibcite{anastasi2009energy}{{2}{2009}{{Anastasi et~al.}}{{Anastasi, Conti, Di~Francesco, and Passarella}}} -\bibcite{berman04}{{3}{2004}{{Berman and Calinescu}}{{}}} \newlabel{figure8}{{8}{15}} \newlabel{figure9}{{9}{15}} +\bibcite{berman04}{{3}{2004}{{Berman and Calinescu}}{{}}} \bibcite{cardei2005improving}{{4}{2005}{{Cardei and Du}}{{}}} \bibcite{cardei2005energy}{{5}{2005}{{Cardei et~al.}}{{Cardei, Thai, Li, and Wu}}} \bibcite{castano2013column}{{6}{2013}{{Casta{\~n}o et~al.}}{{Casta{\~n}o, Rossi, Sevaux, and Velasco}}} diff --git a/PeCO-EO/articleeo.log b/PeCO-EO/articleeo.log index f4869bc..f0d9217 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) 20 FEB 2015 14:20 +This is pdfTeX, Version 3.1415926-2.4-1.40.13 (TeX Live 2012/Debian) (format=pdflatex 2014.3.11) 10 MAY 2015 00:35 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -258,21 +258,24 @@ Package: subfigure 2002/07/30 v2.1.4 subfigure package \subfig@top=\skip53 \subfig@bottom=\skip54 )) +(/usr/share/texlive/texmf-dist/tex/latex/tools/indentfirst.sty +Package: indentfirst 1995/11/23 v1.03 Indent first paragraph (DPC) +) (./articleeo.aux) \openout1 = `articleeo.aux'. -LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 7. -LaTeX Font Info: ... okay on input line 7. -LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 7. -LaTeX Font Info: ... okay on input line 7. -LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 7. -LaTeX Font Info: ... okay on input line 7. -LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 7. -LaTeX Font Info: ... okay on input line 7. -LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 7. -LaTeX Font Info: ... okay on input line 7. -LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 7. -LaTeX Font Info: ... okay on input line 7. +LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 8. +LaTeX Font Info: ... okay on input line 8. +LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 8. +LaTeX Font Info: ... okay on input line 8. +LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 8. +LaTeX Font Info: ... okay on input line 8. +LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 8. +LaTeX Font Info: ... okay on input line 8. +LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 8. +LaTeX Font Info: ... okay on input line 8. +LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 8. +LaTeX Font Info: ... okay on input line 8. (/usr/share/texlive/texmf-dist/tex/context/base/supp-pdf.mkii [Loading MPS to PDF converter (version 2006.09.02).] \scratchcounter=\count123 @@ -336,89 +339,89 @@ e )) LaTeX Font Warning: Font shape `OT1/cmr/m/n' in size <13> not available -(Font) size <12> substituted on input line 20. +(Font) size <12> substituted on input line 21. LaTeX Font Warning: Font shape `OT1/cmr/bx/n' in size <13> not available -(Font) size <12> substituted on input line 20. +(Font) size <12> substituted on input line 21. LaTeX Font Warning: Font shape `OT1/cmr/bx/it' in size <13> not available -(Font) size <12> substituted on input line 20. +(Font) size <12> substituted on input line 21. -LaTeX Font Info: Try loading font information for OML+cmr on input line 20. +LaTeX Font Info: Try loading font information for OML+cmr on input line 21. (/usr/share/texlive/texmf-dist/tex/latex/base/omlcmr.fd File: omlcmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions ) LaTeX Font Info: Font shape `OML/cmr/m/it' in size <10> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 20. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 21. LaTeX Font Info: Font shape `OML/cmr/m/it' in size <7> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 20. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 21. LaTeX Font Info: Font shape `OML/cmr/m/it' in size <5> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 20. -LaTeX Font Info: Try loading font information for OMS+cmr on input line 20. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 21. +LaTeX Font Info: Try loading font information for OMS+cmr on input line 21. (/usr/share/texlive/texmf-dist/tex/latex/base/omscmr.fd File: omscmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions ) LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <10> not available -(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 20. +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 21. LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <7> not available -(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 20. +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 21. LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <5> not available -(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 20. -LaTeX Font Info: Try loading font information for OMX+cmr on input line 20. -LaTeX Font Info: No file OMXcmr.fd. on input line 20. +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 21. +LaTeX Font Info: Try loading font information for OMX+cmr on input line 21. +LaTeX Font Info: No file OMXcmr.fd. on input line 21. LaTeX Font Warning: Font shape `OMX/cmr/m/n' undefined -(Font) using `OMX/cmex/m/n' instead on input line 20. +(Font) using `OMX/cmex/m/n' instead on input line 21. -LaTeX Font Info: Try loading font information for U+msa on input line 20. +LaTeX Font Info: Try loading font information for U+msa on input line 21. (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd File: umsa.fd 2009/06/22 v3.00 AMS symbols A ) -LaTeX Font Info: Try loading font information for U+msb on input line 20. +LaTeX Font Info: Try loading font information for U+msb on input line 21. (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd File: umsb.fd 2009/06/22 v3.00 AMS symbols B ) LaTeX Font Info: Font shape `OML/cmr/m/it' in size <8> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 20. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 21. LaTeX Font Info: Font shape `OML/cmr/m/it' in size <6> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 20. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 21. LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <8> not available -(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 20. +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 21. LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <6> not available -(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 20. -LaTeX Font Info: Calculating math sizes for size <11> on input line 42. +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 21. +LaTeX Font Info: Calculating math sizes for size <11> on input line 43. LaTeX Font Warning: Font shape `OT1/cmr/m/n' in size <5.5> not available -(Font) size <5> substituted on input line 42. +(Font) size <5> substituted on input line 43. LaTeX Font Info: Font shape `OML/cmr/m/it' in size <11> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 42. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 43. LaTeX Font Info: Font shape `OML/cmr/m/it' in size <7.69997> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 42. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 43. LaTeX Font Info: Font shape `OML/cmr/m/it' in size <5.5> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 42. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 43. LaTeX Font Warning: Font shape `OML/cmm/m/it' in size <5.5> not available -(Font) size <5> substituted on input line 42. +(Font) size <5> substituted on input line 43. LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <11> not available -(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 42. +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 43. LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <7.69997> not available -(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 42. +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 43. LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <5.5> not available -(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 42. +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 43. LaTeX Font Warning: Font shape `OMS/cmsy/m/n' in size <5.5> not available -(Font) size <5> substituted on input line 42. +(Font) size <5> substituted on input line 43. -Underfull \hbox (badness 10000) in paragraph at lines 60--74 +Underfull \hbox (badness 10000) in paragraph at lines 61--75 [] @@ -500,40 +503,40 @@ 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 199. +(Font) using `OT1/cmr/bx/n' instead on input line 200. Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-20 10:11:12 +(epstopdf) date: 2015-05-08 17:47:31 (epstopdf) size: 358485 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:43 +(epstopdf) date: 2015-05-09 17:25:26 (epstopdf) size: 78307 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 249. +(epstopdf) \includegraphics on input line 250. 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 249. +Package pdftex.def Info: figure1a-eps-converted-to.pdf used on input line 250. (pdftex.def) Requested size: 213.39566pt x 202.1362pt. Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-20 10:11:12 +(epstopdf) date: 2015-05-08 17:47:31 (epstopdf) size: 241675 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:44 +(epstopdf) date: 2015-05-09 17:25:27 (epstopdf) size: 57181 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 250. +(epstopdf) \includegraphics on input line 251. 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 250. +Package pdftex.def Info: figure1b-eps-converted-to.pdf used on input line 251. (pdftex.def) Requested size: 213.39566pt x 148.93011pt. Underfull \vbox (badness 10000) has occurred while \output is active [] @@ -561,21 +564,21 @@ 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) date: 2015-05-08 17:47:31 (epstopdf) size: 508784 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:44 +(epstopdf) date: 2015-05-09 17:25:27 (epstopdf) size: 138861 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 293. +(epstopdf) \includegraphics on input line 294. 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 293. +Package pdftex.def Info: figure2-eps-converted-to.pdf used on input line 294. (pdftex.def) Requested size: 362.77263pt x 182.4463pt. Underfull \vbox (badness 10000) has occurred while \output is active [] @@ -603,21 +606,21 @@ Overfull \vbox (701.0pt too high) has occurred while \output is active [] [5 <./figure1a-eps-converted-to.pdf> <./figure1b-eps-converted-to.pdf>] Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-20 10:11:12 +(epstopdf) date: 2015-05-08 17:47:31 (epstopdf) size: 196938 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:45 +(epstopdf) date: 2015-05-09 17:25:28 (epstopdf) size: 48639 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 343. +(epstopdf) \includegraphics on input line 344. 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 343. +Package pdftex.def Info: figure3-eps-converted-to.pdf used on input line 344. (pdftex.def) Requested size: 177.82971pt x 147.74475pt. Underfull \vbox (badness 1648) has occurred while \output is active [] @@ -648,21 +651,21 @@ Overfull \vbox (701.0pt too high) has occurred while \output is active [] [6 <./figure2-eps-converted-to.pdf> <./figure3-eps-converted-to.pdf>] Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-20 10:11:12 +(epstopdf) date: 2015-05-08 17:47:31 (epstopdf) size: 428048 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:45 +(epstopdf) date: 2015-05-09 17:25:29 (epstopdf) size: 76496 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 376. +(epstopdf) \includegraphics on input line 377. 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 376. +Package pdftex.def Info: figure4-eps-converted-to.pdf used on input line 377. (pdftex.def) Requested size: 227.62204pt x 167.01096pt. Underfull \vbox (badness 1953) has occurred while \output is active [] @@ -765,27 +768,27 @@ 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 632. +LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 633. -LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 647. +LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 648. -LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 660. +LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 661. -LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 667. +LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 668. -LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 669. +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 671. +LaTeX Font Warning: Command \scriptsize invalid in math mode on input line 672. @@ -814,38 +817,21 @@ Overfull \vbox (701.0pt too high) has occurred while \output is active [] [11] Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-06 11:42:02 +(epstopdf) date: 2015-05-08 17:47:31 (epstopdf) size: 29526 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:46 +(epstopdf) date: 2015-05-09 17:25:29 (epstopdf) size: 12638 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 728. +(epstopdf) \includegraphics on input line 729. 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 728. -(pdftex.def) Requested size: 242.40503pt x 175.15395pt. -Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-06 11:42:02 -(epstopdf) size: 29515 bytes -(epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:46 -(epstopdf) size: 12695 bytes -(epstopdf) Command: -(epstopdf) \includegraphics on input line 750. -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 750. +Package pdftex.def Info: figure5-eps-converted-to.pdf used on input line 729. (pdftex.def) Requested size: 242.40503pt x 175.15395pt. Underfull \vbox (badness 10000) has occurred while \output is active [] @@ -872,99 +858,96 @@ 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 <./figure5-eps-converted-to.pdf>] +Package epstopdf Info: Source file: +(epstopdf) date: 2015-05-08 17:47:31 +(epstopdf) size: 29515 bytes +(epstopdf) Output file: +(epstopdf) date: 2015-05-09 17:25:30 +(epstopdf) size: 12695 bytes +(epstopdf) Command: +(epstopdf) \includegraphics on input line 751. +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 751. +(pdftex.def) Requested size: 242.40503pt x 175.15395pt. Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-06 11:42:02 +(epstopdf) date: 2015-05-08 17:47:31 (epstopdf) size: 24136 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:46 +(epstopdf) date: 2015-05-09 17:25:30 (epstopdf) size: 8179 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 773. +(epstopdf) \includegraphics on input line 774. 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 773. +Package pdftex.def Info: figure7a-eps-converted-to.pdf used on input line 774. (pdftex.def) Requested size: 234.5788pt x 166.39838pt. Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-06 11:42:02 +(epstopdf) date: 2015-05-08 17:47:31 (epstopdf) size: 24138 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:47 +(epstopdf) date: 2015-05-09 17:25:31 (epstopdf) size: 8180 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 774. +(epstopdf) \includegraphics on input line 775. 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 774. +Package pdftex.def Info: figure7b-eps-converted-to.pdf used on input line 775. (pdftex.def) Requested size: 234.5788pt x 166.39838pt. LaTeX Warning: `!h' float specifier changed to `!ht'. Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-06 11:42:03 +(epstopdf) date: 2015-05-08 17:47:31 (epstopdf) size: 24103 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:47 +(epstopdf) date: 2015-05-09 17:25:31 (epstopdf) size: 8351 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 800. +(epstopdf) \includegraphics on input line 801. 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 800. +Package pdftex.def Info: figure8a-eps-converted-to.pdf used on input line 801. (pdftex.def) Requested size: 234.5788pt x 166.39838pt. Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-06 11:42:03 +(epstopdf) date: 2015-05-08 17:47:31 (epstopdf) size: 24855 bytes (epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:47 +(epstopdf) date: 2015-05-09 17:25:31 (epstopdf) size: 8466 bytes (epstopdf) Command: -(epstopdf) \includegraphics on input line 801. +(epstopdf) \includegraphics on input line 802. 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 801. +Package pdftex.def Info: figure8b-eps-converted-to.pdf used on input line 802. (pdftex.def) Requested size: 234.5788pt x 166.39838pt. -LaTeX Warning: `!h' float specifier changed to `!ht'. - -Package epstopdf Info: Source file: -(epstopdf) date: 2015-02-06 11:42:03 -(epstopdf) size: 27000 bytes -(epstopdf) Output file: -(epstopdf) date: 2015-02-20 10:12:48 -(epstopdf) size: 7927 bytes -(epstopdf) Command: -(epstopdf) \includegraphics on input line 823. -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 823. -(pdftex.def) Requested size: 242.40503pt x 175.15395pt. - - LaTeX Warning: `!h' float specifier changed to `!ht'. @@ -991,8 +974,27 @@ 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 <./figure6-eps-converted-to.pdf>] (./articleeo.bbl -Underfull \vbox (badness 10000) has occurred while \output is active [] + [13 <./figure6-eps-converted-to.pdf>] +Package epstopdf Info: Source file: +(epstopdf) date: 2015-05-08 17:47:31 +(epstopdf) size: 27000 bytes +(epstopdf) Output file: +(epstopdf) date: 2015-05-09 17:25:32 +(epstopdf) size: 7927 bytes +(epstopdf) Command: +(epstopdf) \includegraphics on input line 824. +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 824. +(pdftex.def) Requested size: 242.40503pt x 175.15395pt. + + +LaTeX Warning: `!h' float specifier changed to `!ht'. Underfull \vbox (badness 10000) has occurred while \output is active [] @@ -1019,6 +1021,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 [] [14 <./figure7a-eps-converted-to.pdf> <./figure7b-eps-converted-to.pdf>] +(./articleeo.bbl Underfull \vbox (badness 10000) has occurred while \output is active [] @@ -1138,13 +1141,13 @@ LaTeX Font Warning: Some font shapes were not available, defaults substituted. ) Here is how much of TeX's memory you used: - 3701 strings out of 495059 - 47855 string characters out of 3182031 - 116213 words of memory out of 3000000 - 6813 multiletter control sequences out of 15000+200000 + 3708 strings out of 495059 + 48092 string characters out of 3182030 + 116289 words of memory out of 3000000 + 6816 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,419b,327s stack positions out of 5000i,500n,10000p,200000b,50000s + 41i,14n,27p,419b,325s stack positions out of 5000i,500n,10000p,200000b,50000s -Output written on articleeo.pdf (17 pages, 734726 bytes). +Output written on articleeo.pdf (17 pages, 734629 bytes). PDF statistics: 202 PDF objects out of 1000 (max. 8388607) 137 compressed objects within 2 object streams diff --git a/PeCO-EO/articleeo.pdf b/PeCO-EO/articleeo.pdf index bf3d33f..bc80ba6 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 c0c6f7b..40af2f4 100644 --- a/PeCO-EO/articleeo.tex +++ b/PeCO-EO/articleeo.tex @@ -1,865 +1,866 @@ -% gENOguide.tex -% v4.0 released April 2013 - -\documentclass{gENO2e} -%\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e} -%\renewcommand{\algorithmcfname}{ALGORITHM} -\begin{document} - -%\jvol{00} \jnum{00} \jyear{2013} \jmonth{April} - -%\articletype{GUIDE} - -\title{{\itshape Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}} - -\author{Ali Kadhum Idrees$^{a}$, Karine Deschinkel$^{a}$$^{\ast}$\thanks{$^\ast$Corresponding author. Email: karine.deschinkel@univ-fcomte.fr}, Michel Salomon$^{a}$ and Rapha\"el Couturier $^{a}$ -$^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte, - Belfort, France}};} - - -\maketitle - -\begin{abstract} -The most important problem in a Wireless Sensor Network (WSN) is to optimize the -use of its limited energy provision, so that it can fulfill its monitoring task -as long as possible. Among known available approaches that can be used to -improve power management, lifetime coverage optimization provides activity -scheduling which ensures sensing coverage while minimizing the energy cost. We propose such an approach called Perimeter-based Coverage Optimization -protocol (PeCO). It is a hybrid of centralized and distributed methods: the -region of interest is first subdivided into subregions and our protocol is then -distributed among sensor nodes in each subregion. -The novelty of our approach lies essentially in the formulation of a new -mathematical optimization model based on the perimeter coverage level to schedule -sensors' activities. Extensive simulation experiments demonstrate that PeCO can -offer longer lifetime coverage for WSNs in comparison with some other protocols. - -\begin{keywords}Wireless Sensor Networks, Area Coverage, Energy efficiency, Optimization, Scheduling. -\end{keywords} - -\end{abstract} - - -\section{Introduction} -\label{sec:introduction} - -\noindent The continuous progress in Micro Electro-Mechanical Systems (MEMS) and -wireless communication hardware has given rise to the opportunity to use large -networks of tiny sensors, called Wireless Sensor Networks -(WSN)~\citep{akyildiz2002wireless,puccinelli2005wireless}, to fulfill monitoring -tasks. A WSN consists of small low-powered sensors working together by -communicating with one another through multi-hop radio communications. Each node -can send the data it collects in its environment, thanks to its sensor, to the -user by means of sink nodes. The features of a WSN made it suitable for a wide -range of application in areas such as business, environment, health, industry, -military, and so on~\citep{yick2008wireless}. Typically, a sensor node contains -three main components~\citep{anastasi2009energy}: a sensing unit able to measure -physical, chemical, or biological phenomena observed in the environment; a -processing unit which will process and store the collected measurements; a radio -communication unit for data transmission and receiving. - -The energy needed by an active sensor node to perform sensing, processing, and -communication is supplied by a power supply which is a battery. This battery has -a limited energy provision and it may be unsuitable or impossible to replace or -recharge it in most applications. Therefore it is necessary to deploy WSN with -high density in order to increase reliability and to exploit node redundancy -thanks to energy-efficient activity scheduling approaches. Indeed, the overlap -of sensing areas can be exploited to schedule alternatively some sensors in a -low power sleep mode and thus save energy. Overall, the main question that must -be answered is: how to extend the lifetime coverage of a WSN as long as possible -while ensuring a high level of coverage? These past few years many -energy-efficient mechanisms have been suggested to retain energy and extend the -lifetime of the WSNs~\citep{rault2014energy}.\\\\ -This paper makes the following contributions. -\begin{enumerate} -\item We have devised a framework to schedule nodes to be activated alternatively such - that the network lifetime is prolonged while ensuring that a certain level of - coverage is preserved. A key idea in our framework is to exploit spatial and - temporal subdivision. On the one hand, the area of interest is divided into - several smaller subregions and, on the other hand, the time line is divided into - periods of equal length. In each subregion the sensor nodes will cooperatively - choose a leader which will schedule nodes' activities, and this grouping of - sensors is similar to typical cluster architecture. -\item We have proposed a new mathematical optimization model. Instead of trying to - cover a set of specified points/targets as in most of the methods proposed in - the literature, we formulate an integer program based on perimeter coverage of - each sensor. The model involves integer variables to capture the deviations - between the actual level of coverage and the required level. Hence, an - optimal scheduling will be obtained by minimizing a weighted sum of these - deviations. -\item We have conducted extensive simulation experiments, using the discrete event - 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. -\end{enumerate} - - - - - - -The rest of the paper is organized as follows. In the next section we review -some related work in the field. Section~\ref{sec:The PeCO Protocol Description} -is devoted to the PeCO protocol description and Section~\ref{cp} focuses on the -coverage model formulation which is used to schedule the activation of sensor -nodes. Section~\ref{sec:Simulation Results and Analysis} presents simulations -results and discusses the comparison with other approaches. Finally, concluding -remarks are drawn and some suggestions are given for future works in -Section~\ref{sec:Conclusion and Future Works}. - -\section{Related Literature} -\label{sec:Literature Review} - -\noindent In this section, we summarize some related works regarding the -coverage problem and distinguish our PeCO protocol from the works presented in -the literature. - -The most discussed coverage problems in literature can be classified in three -categories~\citep{li2013survey} according to their respective monitoring -objective. Hence, area coverage \citep{Misra} means that every point inside a -fixed area must be monitored, while target coverage~\citep{yang2014novel} refers -to the objective of coverage for a finite number of discrete points called -targets, and barrier coverage~\citep{HeShibo,kim2013maximum} focuses on -preventing intruders from entering into the region of interest. In -\citep{Deng2012} authors transform the area coverage problem into the target -coverage one taking into account the intersection points among disks of sensors -nodes or between disk of sensor nodes and boundaries. In -\citep{Huang:2003:CPW:941350.941367} authors prove that if the perimeters of -sensors are sufficiently covered it will be the case for the whole area. They -provide an algorithm in $O(nd~log~d)$ time to compute the perimeter-coverage of -each sensor, where $d$ denotes the maximum number of sensors that are -neighbors to a sensor and $n$ is the total number of sensors in the -network. {\it In PeCO protocol, instead of determining the level of coverage of - a set of discrete points, our optimization model is based on checking the - perimeter-coverage of each sensor to activate a minimal number of sensors.} - -The major approach to extend network lifetime while preserving coverage is to -divide/organize the sensors into a suitable number of set covers (disjoint or -non-disjoint)\citep{wang2011coverage}, where each set completely covers a region of interest, and to -activate these set covers successively. The network activity can be planned in -advance and scheduled for the entire network lifetime or organized in periods, -and the set of active sensor nodes is decided at the beginning of each period -\citep{ling2009energy}. Active node selection is determined based on the problem -requirements (e.g. area monitoring, connectivity, or power efficiency). For -instance, \citet{jaggi2006} address the problem of maximizing -the lifetime by dividing sensors into the maximum number of disjoint subsets -such that each subset can ensure both coverage and connectivity. A greedy -algorithm is applied once to solve this problem and the computed sets are -activated in succession to achieve the desired network lifetime. -\citet{chin2007}, \citet{yan2008design}, \citet{pc10}, propose algorithms -working in a periodic fashion where a cover set is computed at the beginning of -each period. {\it Motivated by these works, PeCO protocol works in periods, - where each period contains a preliminary phase for information exchange and - decisions, followed by a sensing phase where one cover set is in charge of the - sensing task.} - -Various centralized and distributed approaches, or even a mixing of these two -concepts, have been proposed to extend the network lifetime \citep{zhou2009variable}. In distributed algorithms~\citep{Tian02,yangnovel,ChinhVu,qu2013distributed} each sensor decides of its -own activity scheduling after an information exchange with its neighbors. The -main interest of such an approach is to avoid long range communications and thus -to reduce the energy dedicated to the communications. Unfortunately, since each -node has only information on its immediate neighbors (usually the one-hop ones) -it may make a bad decision leading to a global suboptimal solution. Conversely, -centralized -algorithms~\citep{cardei2005improving,zorbas2010solving,pujari2011high} always -provide nearly or close to optimal solution since the algorithm has a global -view of the whole network. The disadvantage of a centralized method is obviously -its high cost in communications needed to transmit to a single node, the base -station which will globally schedule nodes' activities, data from all the other -sensor nodes in the area. The price in communications can be huge since -long range communications will be needed. In fact the larger the WNS is, the -higher the communication and thus the energy cost are. {\it In order to be - suitable for large-scale networks, in the PeCO protocol, the area of interest - is divided into several smaller subregions, and in each one, a node called the - leader is in charge of selecting the active sensors for the current - period. Thus our protocol is scalable and is a globally distributed method, - whereas it is centralized in each subregion.} - -Various coverage scheduling algorithms have been developed these past few years. -Many of them, dealing with the maximization of the number of cover sets, are -heuristics. These heuristics involve the construction of a cover set by -including in priority the sensor nodes which cover critical targets, that is to -say targets that are covered by the smallest number of sensors -\citep{berman04,zorbas2010solving}. Other approaches are based on mathematical -programming formulations~\citep{cardei2005energy,5714480,pujari2011high,Yang2014} -and dedicated techniques (solving with a branch-and-bound algorithm available in -optimization solver). The problem is formulated as an optimization problem -(maximization of the lifetime or number of cover sets) under target coverage and -energy constraints. Column generation techniques, well-known and widely -practiced techniques for solving linear programs with too many variables, have -also been -used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012column}. {\it In the PeCO - protocol, each leader, in charge of a subregion, solves an integer program - which has a twofold objective: minimize the overcoverage and the undercoverage - of the perimeter of each sensor.} - - - -\section{ The P{\scshape e}CO Protocol Description} -\label{sec:The PeCO Protocol Description} - -\noindent In this section, we describe in details our Perimeter-based Coverage -Optimization protocol. 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} -\label{CI} - -\noindent A WSN consisting of $J$ stationary sensor nodes randomly and uniformly -distributed in a bounded sensor field is considered. The wireless sensors are -deployed in high density to ensure initially a high coverage ratio of the area -of interest. We assume that all the sensor nodes are homogeneous in terms of -communication, sensing, and processing capabilities and heterogeneous from -the energy provision point of view. The location information is available to a -sensor node either through hardware such as embedded GPS or location discovery -algorithms. We assume that each sensor node can directly transmit its -measurements to a mobile sink node. For example, a sink can be an unmanned -aerial vehicle (UAV) flying regularly over the sensor field to collect -measurements from sensor nodes. A mobile sink node collects the measurements and -transmits them to the base station. We consider a Boolean disk coverage model, -which is the most widely used sensor coverage model in the literature, and all -sensor nodes have a constant sensing range $R_s$. Thus, all the space points -within a disk centered at a sensor with a radius equal to the sensing range are -said to be covered by this sensor. We also assume that the communication range -$R_c$ satisfies $R_c \geq 2 \cdot R_s$. In fact, \citet{Zhang05} -proved that if the transmission range fulfills the previous hypothesis, the -complete coverage of a convex area implies connectivity among active nodes. - -The PeCO protocol uses the same perimeter-coverage model as \citet{huang2005coverage}. It can be expressed as follows: a sensor is -said to be perimeter covered if all the points on its perimeter are covered by -at least one sensor other than itself. They proved that a network area is -$k$-covered if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors). - -Figure~\ref{figure1}(a) shows the coverage of sensor node~$0$. On this -figure, we can see that sensor~$0$ has nine neighbors and we have reported on -its perimeter (the perimeter of the disk covered by the sensor) for each -neighbor the two points resulting from the intersection of the two sensing -areas. These points are denoted for neighbor~$i$ by $iL$ and $iR$, respectively -for left and right from a neighboing point of view. The resulting couples of -intersection points subdivide the perimeter of sensor~$0$ into portions called -arcs. - -\begin{figure}[ht!] - \centering - \begin{tabular}{@{}cr@{}} - \includegraphics[width=75mm]{figure1a.eps} & \raisebox{3.25cm}{(a)} \\ - \includegraphics[width=75mm]{figure1b.eps} & \raisebox{2.75cm}{(b)} - \end{tabular} - \caption{(a) Perimeter coverage of sensor node 0 and (b) finding the arc of - $u$'s perimeter covered by $v$.} - \label{figure1} -\end{figure} - -Figure~\ref{figure1}(b) describes the geometric information used to find the -locations of the left and right points of an arc on the perimeter of a sensor -node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the -west side of sensor~$u$, with the following respective coordinates in the -sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates we can -compute the euclidean distance between nodes~$u$ and $v$: $Dist(u,v)=\sqrt{\vert - u_x - v_x \vert^2 + \vert u_y-v_y \vert^2}$, while the angle~$\alpha$ is -obtained through the formula: - \[ -\alpha = \arccos \left(\frac{Dist(u,v)}{2R_s} -\right). -\] -The arc on the perimeter of~$u$ defined by the angular interval $[\pi - - \alpha,\pi + \alpha]$ is said to be perimeter-covered by sensor~$v$. - -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 -in the interval $[0,2\pi]$. More precisely, we can see that 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 -from the first intersection point after point~zero, and the maximum level of -coverage is determined for each interval defined by two successive points. The -maximum level of coverage is equal to the number of overlapping arcs. For -example, -between~$5L$ and~$6L$ the maximum level of coverage is equal to $3$ -(the value is highlighted in yellow at the bottom of figure~\ref{figure2}), which -means that at most 2~neighbors can cover the perimeter in addition to node $0$. -Table~\ref{my-label} summarizes for each coverage interval the maximum level of -coverage and the sensor nodes covering the perimeter. The example discussed -above is thus given by the sixth line of the table. - - -\begin{figure*}[t!] -\centering -\includegraphics[width=127.5mm]{figure2.eps} -\caption{Maximum coverage levels for perimeter of sensor node $0$.} -\label{figure2} -\end{figure*} - - - - - \begin{table} - \tbl{Coverage intervals and contributing sensors for sensor node 0 \label{my-label}} -{\begin{tabular}{|c|c|c|c|c|c|c|c|c|} -\hline -\begin{tabular}[c]{@{}c@{}}Left \\ point \\ angle~$\alpha$ \end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ left \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ right \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Maximum \\ coverage\\ level\end{tabular} & \multicolumn{5}{c|}{\begin{tabular}[c]{@{}c@{}}Set of sensors\\ involved \\ in coverage interval\end{tabular}} \\ \hline -0.0291 & 1L & 2L & 4 & 0 & 1 & 3 & 4 & \\ \hline -0.104 & 2L & 3R & 5 & 0 & 1 & 3 & 4 & 2 \\ \hline -0.3168 & 3R & 4R & 4 & 0 & 1 & 4 & 2 & \\ \hline -0.6752 & 4R & 1R & 3 & 0 & 1 & 2 & & \\ \hline -1.8127 & 1R & 5L & 2 & 0 & 2 & & & \\ \hline -1.9228 & 5L & 6L & 3 & 0 & 2 & 5 & & \\ \hline -2.3959 & 6L & 2R & 4 & 0 & 2 & 5 & 6 & \\ \hline -2.4258 & 2R & 7L & 3 & 0 & 5 & 6 & & \\ \hline -2.7868 & 7L & 8L & 4 & 0 & 5 & 6 & 7 & \\ \hline -2.8358 & 8L & 5R & 5 & 0 & 5 & 6 & 7 & 8 \\ \hline -2.9184 & 5R & 7R & 4 & 0 & 6 & 7 & 8 & \\ \hline -3.3301 & 7R & 9R & 3 & 0 & 6 & 8 & & \\ \hline -3.9464 & 9R & 6R & 4 & 0 & 6 & 8 & 9 & \\ \hline -4.767 & 6R & 3L & 3 & 0 & 8 & 9 & & \\ \hline -4.8425 & 3L & 8R & 4 & 0 & 3 & 8 & 9 & \\ \hline -4.9072 & 8R & 4L & 3 & 0 & 3 & 9 & & \\ \hline -5.3804 & 4L & 9R & 4 & 0 & 3 & 4 & 9 & \\ \hline -5.9157 & 9R & 1L & 3 & 0 & 3 & 4 & & \\ \hline -\end{tabular}} - - -\end{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 -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$ -and the corresponding interval will not be taken into account by the -optimization algorithm. - - \newpage -\begin{figure}[h!] -\centering -\includegraphics[width=62.5mm]{figure3.eps} -\caption{Sensing range outside the WSN's area of interest.} -\label{figure3} -\end{figure} - - -\subsection{The Main Idea} - -\noindent 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. - -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 -(INFO) Exchange, Leader Election, Decision (the result of an optimization -problem), and Sensing. For each period there is exactly one set cover -responsible for the sensing task. Protocols based on a periodic scheme, like -PeCO, are more robust against an unexpected node failure. On the one hand, if -a node failure is discovered before taking the decision, the corresponding sensor -node will not be considered by the optimization algorithm. On the other -hand, if the sensor failure happens after the decision, the sensing task of the -network will be temporarily affected: only during the period of sensing until a -new period starts, since a new set cover will take charge of the sensing task in -the next period. The energy consumption and some other constraints can easily be -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. - -\begin{figure}[t!] -\centering -\includegraphics[width=80mm]{figure4.eps} -\caption{PeCO protocol.} -\label{figure4} -\end{figure} - -We define two types of packets to be used by PeCO protocol: - -\begin{itemize} -\item INFO packet: sent by each sensor node to all the nodes inside a same - subregion for information exchange. -\item ActiveSleep packet: sent by the leader to all the nodes in its subregion - to transmit to them their respective status (stay Active or go Sleep) during - sensing phase. -\end{itemize} - - -Five status are possible for a sensor node in the network: - -\begin{itemize} -\item LISTENING: waits for a decision (to be active or not); -\item COMPUTATION: executes the optimization algorithm as leader to - determine the activities scheduling; -\item ACTIVE: node is sensing; -\item SLEEP: node is turned off; -\item COMMUNICATION: transmits or receives packets. -\end{itemize} - - -\subsection{PeCO Protocol Algorithm} - -\noindent The pseudocode implementing the protocol on a node is given below. -More precisely, Algorithm~\ref{alg:PeCO} gives a brief description of the -protocol applied by a sensor node $s_k$ where $k$ is the node index in the WSN. - - - -\begin{algorithm} - % \KwIn{all the parameters related to information exchange} -% \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)} -% \BlankLine - %\emph{Initialize the sensor node and determine it's position and subregion} \; - -\noindent{\bf If} $RE_k \geq E_{th}$ {\bf then}\\ -\hspace*{0.6cm} \emph{$s_k.status$ = COMMUNICATION;}\\ -\hspace*{0.6cm} \emph{Send $INFO()$ packet to other nodes in subregion;}\\ -\hspace*{0.6cm} \emph{Wait $INFO()$ packet from other nodes in subregion;}\\ -\hspace*{0.6cm} \emph{Update K.CurrentSize;}\\ -\hspace*{0.6cm} \emph{LeaderID = Leader election;}\\ -\hspace*{0.6cm} {\bf If} $ s_k.ID = LeaderID $ {\bf then}\\ -\hspace*{1.2cm} \emph{$s_k.status$ = COMPUTATION;}\\ -\hspace*{1.2cm}{\bf If} \emph{$ s_k.ID $ is Not previously selected as a Leader} {\bf then}\\ -\hspace*{1.8cm} \emph{ Execute the perimeter coverage model;}\\ -\hspace*{1.2cm} {\bf end}\\ -\hspace*{1.2cm}{\bf If} \emph{($s_k.ID $ is the same Previous Leader)~And~(K.CurrentSize = K.PreviousSize)}\\ -\hspace*{1.8cm} \emph{ Use the same previous cover set for current sensing stage;}\\ -\hspace*{1.2cm} {\bf end}\\ -\hspace*{1.2cm} {\bf else}\\ -\hspace*{1.8cm}\emph{Update $a^j_{ik}$; prepare data for IP~Algorithm;}\\ -\hspace*{1.8cm} \emph{$\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$);}\\ -\hspace*{1.8cm} \emph{K.PreviousSize = K.CurrentSize;}\\ -\hspace*{1.2cm} {\bf end}\\ -\hspace*{1.2cm}\emph{$s_k.status$ = COMMUNICATION;}\\ -\hspace*{1.2cm}\emph{Send $ActiveSleep()$ to each node $l$ in subregion;}\\ -\hspace*{1.2cm}\emph{Update $RE_k $;}\\ -\hspace*{0.6cm} {\bf end}\\ -\hspace*{0.6cm} {\bf else}\\ -\hspace*{1.2cm}\emph{$s_k.status$ = LISTENING;}\\ -\hspace*{1.2cm}\emph{Wait $ActiveSleep()$ packet from the Leader;}\\ -\hspace*{1.2cm}\emph{Update $RE_k $;}\\ -\hspace*{0.6cm} {\bf end}\\ -{\bf end}\\ -{\bf else}\\ -\hspace*{0.6cm} \emph{Exclude $s_k$ from entering in the current sensing stage;}\\ -{\bf end}\\ -\label{alg:PeCO} -\end{algorithm} - - - -In this algorithm, K.CurrentSize and K.PreviousSize respectively represent the -current number and the previous number of living nodes in the subnetwork of the -subregion. Initially, the sensor node checks its remaining energy $RE_k$, which -must be greater than a threshold $E_{th}$ in order to participate in the current -period. Each sensor node determines its position and its subregion using an -embedded GPS or a location discovery algorithm. After that, all the sensors -collect position coordinates, remaining energy, sensor node ID, and the number -of their one-hop live neighbors during the information exchange. The sensors -inside a same region cooperate to elect a leader. The selection criteria for the -leader, in order of priority, are: larger numbers of neighbors, larger remaining -energy, and then in case of equality, larger index. Once chosen, the leader -collects information to formulate and solve the integer program which allows to -construct the set of active sensors in the sensing stage. - - -\section{Perimeter-based Coverage Problem Formulation} -\label{cp} - -\noindent In this section, the coverage model is mathematically formulated. We -start with a description of the notations that will be used throughout the -section.\\ -First, we have the following sets: -\begin{itemize} -\item $S$ represents the set of WSN sensor nodes; -\item $A \subseteq S $ is the subset of alive sensors; -\item $I_j$ designates the set of coverage intervals (CI) obtained for - sensor~$j$. -\end{itemize} -$I_j$ refers to the set of coverage intervals which have been defined according -to the method introduced in subsection~\ref{CI}. For a coverage interval $i$, -let $a^j_{ik}$ denotes the indicator function of whether sensor~$k$ is involved -in coverage interval~$i$ of sensor~$j$, that is: -\begin{equation} -a^j_{ik} = \left \{ -\begin{array}{lll} - 1 & \mbox{if sensor $k$ is involved in the } \\ - & \mbox{coverage interval $i$ of sensor $j$}, \\ - 0 & \mbox{otherwise.}\\ -\end{array} \right. -\end{equation} -Note that $a^k_{ik}=1$ by definition of the interval. - -Second, we define several binary and integer variables. 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 -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 -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 -period to ensure the desired coverage level. As the number of alive sensors -decreases, it becomes impossible to reach the desired level of coverage for all -coverage intervals. Therefore we use variables $M^j_i$ and $V^j_i$ as a measure -of the deviation between the desired number of active sensors in a coverage -interval and the effective number. And we try to minimize these deviations, -first to force the activation of a minimal number of sensors to ensure the -desired coverage level, and if the desired level cannot be completely satisfied, -to reach a coverage level as close as possible to the desired one. - - - - -Our coverage optimization problem can then be mathematically expressed as follows: - -\begin{equation} -\left \{ -\begin{array}{ll} -\min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\ -\textrm{subject to :}&\\ -\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i \geq l \quad \forall i \in I_j, \forall j \in S\\ -\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i \leq l \quad \forall i \in I_j, \forall j \in S\\ -X_{k} \in \{0,1\}, \forall k \in A -\end{array} -\right. -\end{equation} - -$\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 -brachytherapy treatment planning for optimizing dose distribution -\citep{0031-9155-44-1-012}. The 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 we -consider only alive sensors (sensors with enough energy to be alive during one -sensing phase) in the model. - -\section{Performance Evaluation and Analysis} -\label{sec:Simulation Results and Analysis} - - -\subsection{Simulation Settings} - - -The WSN area of interest is supposed to be divided into 16~regular subregions -and we use the same energy consumption than in our previous work~\citep{Idrees2}. -Table~\ref{table3} gives the chosen parameters settings. - -\begin{table}[ht] -\tbl{Relevant parameters for network initialization \label{table3}}{ - -\centering - -\begin{tabular}{c|c} - -\hline -Parameter & Value \\ [0.5ex] - -\hline -% inserts single horizontal line -Sensing field & $(50 \times 25)~m^2 $ \\ - -WSN size & 100, 150, 200, 250, and 300~nodes \\ - -Initial energy & in range 500-700~Joules \\ - -Sensing period & duration of 60 minutes \\ -$E_{th}$ & 36~Joules\\ -$R_s$ & 5~m \\ - -$\alpha^j_i$ & 0.6 \\ - -$\beta^j_i$ & 0.4 - -\end{tabular}} - - -\end{table} -To obtain experimental results which are relevant, simulations with five -different node densities going from 100 to 300~nodes were performed considering -each time 25~randomly generated networks. The nodes are deployed on a field of -interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a -high coverage ratio. Each node has an initial energy level, in Joules, which is -randomly drawn in the interval $[500-700]$. If its energy provision reaches a -value below the threshold $E_{th}=36$~Joules, the minimum energy needed for a -node to stay active during one period, it will no more participate in the -coverage task. This value corresponds to the energy needed by the sensing phase, -obtained by multiplying the energy consumed in active state (9.72 mW) with the -time in seconds for one period (3600 seconds), and adding the energy for the -pre-sensing phases. According to the interval of initial energy, a sensor may -be active during at most 20 periods. - -The values of $\alpha^j_i$ and $\beta^j_i$ have been chosen to ensure a good -network coverage and a longer WSN lifetime. We have given a higher priority to -the undercoverage (by setting the $\alpha^j_i$ with a larger value than -$\beta^j_i$) so as to prevent the non-coverage for the interval~$i$ of the -sensor~$j$. On the other hand, we have assigned to -$\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute -in covering the interval. - -We introduce the following performance metrics to evaluate the efficiency of our -approach. - - -\begin{itemize} -\item {\bf Network Lifetime}: the lifetime is defined as the time elapsed until - the coverage ratio falls below a fixed threshold. $Lifetime_{95}$ and - $Lifetime_{50}$ denote, respectively, the amount of time during which is - guaranteed a level of coverage greater than $95\%$ and $50\%$. The WSN can - fulfill the expected monitoring task until all its nodes have depleted their - energy or if the network is no more connected. This last condition is crucial - because without network connectivity a sensor may not be able to send to a - base station an event it has sensed. -\item {\bf Coverage Ratio (CR)} : it measures how well the WSN is able to - observe the area of interest. In our case, we discretized the sensor field as - a regular grid, which yields the following equation: - - -\[ - \scriptsize - \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100 -\] - - - where $n$ is the number of covered grid points by active sensors of every - subregions during the current sensing phase and $N$ is total number of grid - points in the sensing field. In our simulations we have set a layout of - $N~=~51~\times~26~=~1326$~grid points. -\item {\bf Active Sensors Ratio (ASR)}: a major objective of our protocol is to - activate as few nodes as possible, in order to minimize the communication - overhead and maximize the WSN lifetime. The active sensors ratio is defined as - follows: - -\[ - \scriptsize - \mbox{ASR}(\%) = \frac{\sum\limits_{r=1}^R \mbox{$|A_r^p|$}}{\mbox{$|S|$}} \times 100 -\] - - where $|A_r^p|$ is the number of active sensors in the subregion $r$ in the - current sensing period~$p$, $|S|$ is the number of sensors in the network, and - $R$ is the number of subregions. -\item {\bf Energy Consumption (EC)}: energy consumption can be seen as the total - energy consumed by the sensors during $Lifetime_{95}$ or $Lifetime_{50}$, - divided by the number of periods. The value of EC is computed according to - this formula: - -\[ - \scriptsize - \mbox{EC} = \frac{\sum\limits_{p=1}^{P} \left( E^{\mbox{com}}_p+E^{\mbox{list}}_p+E^{\mbox{comp}}_p - + E^{a}_p+E^{s}_p \right)}{P}, -\] - - where $P$ corresponds to the number of periods. The total energy consumed by - the sensors comes through taking into consideration four main energy - factors. The first one, denoted $E^{\scriptsize \mbox{com}}_p$, represents the - energy consumption spent by all the nodes for wireless communications during - period $p$. $E^{\scriptsize \mbox{list}}_p$, the next factor, corresponds to - the energy consumed by the sensors in LISTENING status before receiving the - decision to go active or sleep in period $p$. $E^{\scriptsize \mbox{comp}}_p$ - refers to the energy needed by all the leader nodes to solve the integer - program during a period. Finally, $E^a_{p}$ and $E^s_{p}$ indicate the energy - consumed by the WSN during the sensing phase (active and sleeping nodes). -\end{itemize} - - -\subsection{Simulation Results} - -In order to assess and analyze the performance of our protocol we have -implemented PeCO protocol in OMNeT++~\citep{varga} simulator. Besides PeCO, two -other protocols, described in the next paragraph, will be evaluated for -comparison purposes. The simulations were run on a DELL laptop with an Intel -Core~i3~2370~M (1.8~GHz) processor (2 cores) whose MIPS (Million Instructions -Per Second) rate is equal to 35330. To be consistent with the use of a sensor -node based on Atmels AVR ATmega103L microcontroller (6~MHz) having a MIPS rate -equal to 6, the original execution time on the laptop is multiplied by 2944.2 -$\left(\frac{35330}{2} \times \frac{1}{6} \right)$. The modeling language for -Mathematical Programming (AMPL)~\citep{AMPL} is employed to generate the integer -program instance in a standard format, which is then read and solved by the -optimization solver GLPK (GNU linear Programming Kit available in the public -domain) \citep{glpk} through a Branch-and-Bound method. - -As said previously, the PeCO is compared to three other approaches. The first -one, called DESK, is a fully distributed coverage algorithm proposed by -\citep{ChinhVu}. The second one, called GAF~\citep{xu2001geography}, consists in -dividing the monitoring area into fixed squares. Then, during the decision -phase, in each square, one sensor is chosen to remain active during the sensing -phase. The last one, the DiLCO protocol~\citep{Idrees2}, is an improved version -of a research work we presented in~\citep{idrees2014coverage}. Let us notice that -PeCO and DiLCO protocols are based on the same framework. In particular, the -choice for the simulations of a partitioning in 16~subregions was made because -it corresponds to the configuration producing the best results for DiLCO. The -protocols are distinguished from one another by the formulation of the integer -program providing the set of sensors which have to be activated in each sensing -phase. DiLCO protocol tries to satisfy the coverage of a set of primary points, -whereas the PeCO protocol objective is to reach a desired level of coverage for each -sensor perimeter. In our experimentations, we chose a level of coverage equal to -one ($l=1$). - -\subsubsection{\bf Coverage Ratio} - -Figure~\ref{figure5} shows the average coverage ratio for 200 deployed nodes -obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better -coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, compared to the 98.76\% -produced by PeCO for the first periods. This is due to the fact that at the -beginning the DiLCO protocol puts to sleep status more redundant sensors (which -slightly decreases the coverage ratio), while the three other protocols activate -more sensor nodes. Later, when the number of periods is beyond~70, it clearly -appears that PeCO provides a better coverage ratio and keeps a coverage ratio -greater than 50\% for longer periods (15 more compared to DiLCO, 40 more -compared to DESK). The energy saved by PeCO in the early periods allows later a -substantial increase of the coverage performance. - -\parskip 0pt -\begin{figure}[h!] -\centering - \includegraphics[scale=0.5] {figure5.eps} -\caption{Coverage ratio for 200 deployed nodes.} -\label{figure5} -\end{figure} - - - - -\subsubsection{\bf Active Sensors Ratio} - -Having the less active sensor nodes in each period is essential to minimize the -energy consumption and thus to maximize the network lifetime. Figure~\ref{figure6} -shows the average active nodes ratio for 200 deployed nodes. We observe that -DESK and GAF have 30.36 \% and 34.96 \% active nodes for the first fourteen -rounds and DiLCO and PeCO protocols compete perfectly with only 17.92~\% and -20.16~\% active nodes during the same time interval. As the number of periods -increases, PeCO protocol has a lower number of active nodes in comparison with -the three other approaches, while keeping a greater coverage ratio as shown in -figure \ref{figure5}. - -\begin{figure}[h!] -\centering -\includegraphics[scale=0.5]{figure6.eps} -\caption{Active sensors ratio for 200 deployed nodes.} -\label{figure6} -\end{figure} - -\subsubsection{\bf Energy Consumption} - -We studied the effect of the energy consumed by the WSN during the communication, -computation, listening, active, and sleep status for different network densities -and compared it for the four approaches. Figures~\ref{figure7}(a) and (b) -illustrate the energy consumption for different network sizes and for -$Lifetime95$ and $Lifetime50$. The results show that our PeCO protocol is the -most competitive from the energy consumption point of view. As shown in both -figures, PeCO consumes much less energy than the three other methods. One might -think that the resolution of the integer program is too costly in energy, but -the results show that it is very beneficial to lose a bit of time in the -selection of sensors to activate. Indeed the optimization program allows to -reduce significantly the number of active sensors and so the energy consumption -while keeping a good coverage level. - -\begin{figure}[h!] - \centering - \begin{tabular}{@{}cr@{}} - \includegraphics[scale=0.475]{figure7a.eps} & \raisebox{2.75cm}{(a)} \\ - \includegraphics[scale=0.475]{figure7b.eps} & \raisebox{2.75cm}{(b)} - \end{tabular} - \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.} - \label{figure7} -\end{figure} - - - -\subsubsection{\bf Network Lifetime} - -We observe the superiority of PeCO and DiLCO protocols in comparison with the -two other approaches in prolonging the network lifetime. In -Figures~\ref{figure8}(a) and (b), $Lifetime95$ and $Lifetime50$ are shown for -different network sizes. As highlighted by these figures, the lifetime -increases with the size of the network, and it is clearly largest for DiLCO -and PeCO protocols. For instance, for a network of 300~sensors and coverage -ratio greater than 50\%, we can see on figure~\ref{figure8}(b) that the lifetime -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\%. - -\begin{figure}[h!] - \centering - \begin{tabular}{@{}cr@{}} - \includegraphics[scale=0.475]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\ - \includegraphics[scale=0.475]{figure8b.eps} & \raisebox{2.75cm}{(b)} - \end{tabular} - \caption{Network Lifetime for (a)~$Lifetime_{95}$ \\ - and (b)~$Lifetime_{50}$.} - \label{figure8} -\end{figure} - - - -Figure~\ref{figure9} compares the lifetime coverage of our protocols for -different coverage ratios. We denote by Protocol/50, Protocol/80, Protocol/85, -Protocol/90, and Protocol/95 the amount of time during which the network can -satisfy an area coverage greater than $50\%$, $80\%$, $85\%$, $90\%$, and $95\%$ -respectively, where the term Protocol refers to DiLCO or PeCO. Indeed there are applications -that do not require a 100\% coverage of the area to be monitored. PeCO might be -an interesting method since it achieves a good balance between a high level -coverage ratio and network lifetime. PeCO always outperforms DiLCO for the three -lower coverage ratios, moreover the improvements grow with the network -size. DiLCO is better for coverage ratios near 100\%, but in that case PeCO is -not ineffective for the smallest network sizes. - -\begin{figure}[h!] -\centering \includegraphics[scale=0.5]{figure9.eps} -\caption{Network lifetime for different coverage ratios.} -\label{figure9} -\end{figure} - - - - -\section{Conclusion and Future Works} -\label{sec:Conclusion and Future Works} - -In this paper we have studied the problem of Perimeter-based Coverage Optimization in -WSNs. We have designed a new protocol, called Perimeter-based Coverage Optimization, which -schedules nodes' activities (wake up and sleep stages) with the objective of -maintaining a good coverage ratio while maximizing the network lifetime. This -protocol is applied in a distributed way in regular subregions obtained after -partitioning the area of interest in a preliminary step. It works in periods and -is based on the resolution of an integer program to select the subset of sensors -operating in active status for each period. Our work is original in so far as it -proposes for the first time an integer program scheduling the activation of -sensors based on their perimeter coverage level, instead of using a set of -targets/points to be covered. - - -We have carried out several simulations to evaluate the proposed protocol. The -simulation results show that PeCO is more energy-efficient than other -approaches, with respect to lifetime, coverage ratio, active sensors ratio, and -energy consumption. - -We plan to extend our framework so that the schedules are planned for multiple -sensing periods. - -We also want to improve our integer program to take into account heterogeneous -sensors from both energy and node characteristics point of views. - -Finally, it would be interesting to implement our protocol using a -sensor-testbed to evaluate it in real world applications. - -\bibliographystyle{gENO} -\bibliography{biblio} - - -\end{document} +% gENOguide.tex +% v4.0 released April 2013 + +\documentclass{gENO2e} +%\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e} +%\renewcommand{\algorithmcfname}{ALGORITHM} +\usepackage{indentfirst} +\begin{document} + +%\jvol{00} \jnum{00} \jyear{2013} \jmonth{April} + +%\articletype{GUIDE} + +\title{{\itshape Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}} + +\author{Ali Kadhum Idrees$^{a}$, Karine Deschinkel$^{a}$$^{\ast}$\thanks{$^\ast$Corresponding author. Email: karine.deschinkel@univ-fcomte.fr}, Michel Salomon$^{a}$ and Rapha\"el Couturier $^{a}$ +$^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte, + Belfort, France}};} + + +\maketitle + +\begin{abstract} +The most important problem in a Wireless Sensor Network (WSN) is to optimize the +use of its limited energy provision, so that it can fulfill its monitoring task +as long as possible. Among known available approaches that can be used to +improve power management, lifetime coverage optimization provides activity +scheduling which ensures sensing coverage while minimizing the energy cost. We propose such an approach called Perimeter-based Coverage Optimization +protocol (PeCO). It is a hybrid of centralized and distributed methods: the +region of interest is first subdivided into subregions and our protocol is then +distributed among sensor nodes in each subregion. +The novelty of our approach lies essentially in the formulation of a new +mathematical optimization model based on the perimeter coverage level to schedule +sensors' activities. Extensive simulation experiments demonstrate that PeCO can +offer longer lifetime coverage for WSNs in comparison with some other protocols. + +\begin{keywords}Wireless Sensor Networks, Area Coverage, Energy efficiency, Optimization, Scheduling. +\end{keywords} + +\end{abstract} + + +\section{Introduction} +\label{sec:introduction} + +The continuous progress in Micro Electro-Mechanical Systems (MEMS) and +wireless communication hardware has given rise to the opportunity to use large +networks of tiny sensors, called Wireless Sensor Networks +(WSN)~\citep{akyildiz2002wireless,puccinelli2005wireless}, to fulfill monitoring +tasks. A WSN consists of small low-powered sensors working together by +communicating with one another through multi-hop radio communications. Each node +can send the data it collects in its environment, thanks to its sensor, to the +user by means of sink nodes. The features of a WSN made it suitable for a wide +range of application in areas such as business, environment, health, industry, +military, and so on~\citep{yick2008wireless}. Typically, a sensor node contains +three main components~\citep{anastasi2009energy}: a sensing unit able to measure +physical, chemical, or biological phenomena observed in the environment; a +processing unit which will process and store the collected measurements; a radio +communication unit for data transmission and receiving. + +The energy needed by an active sensor node to perform sensing, processing, and +communication is supplied by a power supply which is a battery. This battery has +a limited energy provision and it may be unsuitable or impossible to replace or +recharge it in most applications. Therefore it is necessary to deploy WSN with +high density in order to increase reliability and to exploit node redundancy +thanks to energy-efficient activity scheduling approaches. Indeed, the overlap +of sensing areas can be exploited to schedule alternatively some sensors in a +low power sleep mode and thus save energy. Overall, the main question that must +be answered is: how to extend the lifetime coverage of a WSN as long as possible +while ensuring a high level of coverage? These past few years many +energy-efficient mechanisms have been suggested to retain energy and extend the +lifetime of the WSNs~\citep{rault2014energy}.\\\\ +This paper makes the following contributions. +\begin{enumerate} +\item We have devised a framework to schedule nodes to be activated alternatively such + that the network lifetime is prolonged while ensuring that a certain level of + coverage is preserved. A key idea in our framework is to exploit spatial and + temporal subdivision. On the one hand, the area of interest is divided into + several smaller subregions and, on the other hand, the time line is divided into + periods of equal length. In each subregion the sensor nodes will cooperatively + choose a leader which will schedule nodes' activities, and this grouping of + sensors is similar to typical cluster architecture. +\item We have proposed a new mathematical optimization model. Instead of trying to + cover a set of specified points/targets as in most of the methods proposed in + the literature, we formulate an integer program based on perimeter coverage of + each sensor. The model involves integer variables to capture the deviations + between the actual level of coverage and the required level. Hence, an + optimal schedule will be obtained by minimizing a weighted sum of these + deviations. +\item We have conducted extensive simulation experiments, using the discrete event + 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. +\end{enumerate} + + + + + + +The rest of the paper is organized as follows. In the next section we review +some related work in the field. Section~\ref{sec:The PeCO Protocol Description} +is devoted to the PeCO protocol description and Section~\ref{cp} focuses on the +coverage model formulation which is used to schedule the activation of sensor +nodes. Section~\ref{sec:Simulation Results and Analysis} presents simulations +results and discusses the comparison with other approaches. Finally, concluding +remarks are drawn and some suggestions are given for future works in +Section~\ref{sec:Conclusion and Future Works}. + +\section{Related Literature} +\label{sec:Literature Review} + +In this section, we summarize some related works regarding the +coverage problem and distinguish our PeCO protocol from the works presented in +the literature. + +The most discussed coverage problems in literature can be classified in three +categories~\citep{li2013survey} according to their respective monitoring +objective. Hence, area coverage \citep{Misra} means that every point inside a +fixed area must be monitored, while target coverage~\citep{yang2014novel} refers +to the objective of coverage for a finite number of discrete points called +targets, and barrier coverage~\citep{HeShibo,kim2013maximum} focuses on +preventing intruders from entering into the region of interest. In +\citep{Deng2012} authors transform the area coverage problem into the target +coverage one taking into account the intersection points among disks of sensors +nodes or between disk of sensor nodes and boundaries. In +\citep{Huang:2003:CPW:941350.941367} authors prove that if the perimeters of +sensors are sufficiently covered it will be the case for the whole area. They +provide an algorithm in $O(nd~log~d)$ time to compute the perimeter-coverage of +each sensor, where $d$ denotes the maximum number of sensors that are +neighbors to a sensor and $n$ is the total number of sensors in the +network. {\it In PeCO protocol, instead of determining the level of coverage of + a set of discrete points, our optimization model is based on checking the + perimeter-coverage of each sensor to activate a minimal number of sensors.} + +The major approach to extend network lifetime while preserving coverage is to +divide/organize the sensors into a suitable number of set covers (disjoint or +non-disjoint)\citep{wang2011coverage}, where each set completely covers a region of interest, and to +activate these set covers successively. The network activity can be planned in +advance and scheduled for the entire network lifetime or organized in periods, +and the set of active sensor nodes is decided at the beginning of each period +\citep{ling2009energy}. Active node selection is determined based on the problem +requirements (e.g. area monitoring, connectivity, or power efficiency). For +instance, \citet{jaggi2006} address the problem of maximizing +the lifetime by dividing sensors into the maximum number of disjoint subsets +such that each subset can ensure both coverage and connectivity. A greedy +algorithm is applied once to solve this problem and the computed sets are +activated in succession to achieve the desired network lifetime. +\citet{chin2007}, \citet{yan2008design}, \citet{pc10}, propose algorithms +working in a periodic fashion where a cover set is computed at the beginning of +each period. {\it Motivated by these works, PeCO protocol works in periods, + where each period contains a preliminary phase for information exchange and + decisions, followed by a sensing phase where one cover set is in charge of the + sensing task.} + +Various centralized and distributed approaches, or even a mixing of these two +concepts, have been proposed to extend the network lifetime \citep{zhou2009variable}. In distributed algorithms~\citep{Tian02,yangnovel,ChinhVu,qu2013distributed} each sensor decides of its +own activity scheduling after an information exchange with its neighbors. The +main interest of such an approach is to avoid long range communications and thus +to reduce the energy dedicated to the communications. Unfortunately, since each +node has only information on its immediate neighbors (usually the one-hop ones) +it may make a bad decision leading to a global suboptimal solution. Conversely, +centralized +algorithms~\citep{cardei2005improving,zorbas2010solving,pujari2011high} always +provide nearly or close to optimal solution since the algorithm has a global +view of the whole network. The disadvantage of a centralized method is obviously +its high cost in communications needed to transmit to a single node, the base +station which will globally schedule nodes' activities, and data from all the other +sensor nodes in the area. The price in communications can be huge since +long range communications will be needed. In fact the larger the WNS is, the +higher the communication and thus the energy cost are. {\it In order to be + suitable for large-scale networks, in the PeCO protocol, the area of interest + is divided into several smaller subregions, and in each one, a node called the + leader is in charge of selecting the active sensors for the current + period. Thus our protocol is scalable and is a globally distributed method, + whereas it is centralized in each subregion.} + +Various coverage scheduling algorithms have been developed these past few years. +Many of them, dealing with the maximization of the number of cover sets, are +heuristics. These heuristics involve the construction of a cover set by +including in priority the sensor nodes which cover critical targets, that is to +say targets that are covered by the smallest number of sensors +\citep{berman04,zorbas2010solving}. Other approaches are based on mathematical +programming formulations~\citep{cardei2005energy,5714480,pujari2011high,Yang2014} +and dedicated techniques (solving with a branch-and-bound algorithm available in +optimization solver). The problem is formulated as an optimization problem +(maximization of the lifetime or number of cover sets) under target coverage and +energy constraints. Column generation techniques, well-known and widely +practiced techniques for solving linear programs with too many variables, have +also been +used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012column}. {\it In the PeCO + protocol, each leader, in charge of a subregion, solves an integer program + which has a twofold objective: minimize the overcoverage and the undercoverage + of the perimeter of each sensor.} + + + +\section{ The P{\scshape e}CO Protocol Description} +\label{sec:The PeCO Protocol Description} + +In this section, we describe in details our Perimeter-based Coverage +Optimization protocol. 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} +\label{CI} + +A WSN consisting of $J$ stationary sensor nodes randomly and uniformly +distributed in a bounded sensor field is considered. The wireless sensors are +deployed in high density to ensure initially a high coverage ratio of the area +of interest. We assume that all the sensor nodes are homogeneous in terms of +communication, sensing, and processing capabilities and heterogeneous from +the energy provision point of view. The location information is available to a +sensor node either through hardware such as embedded GPS or location discovery +algorithms. We assume that each sensor node can directly transmit its +measurements to a mobile sink node. For example, a sink can be an unmanned +aerial vehicle (UAV) flying regularly over the sensor field to collect +measurements from sensor nodes. A mobile sink node collects the measurements and +transmits them to the base station. We consider a Boolean disk coverage model, +which is the most widely used sensor coverage model in the literature, and all +sensor nodes have a constant sensing range $R_s$. Thus, all the space points +within a disk centered at a sensor with a radius equal to the sensing range are +said to be covered by this sensor. We also assume that the communication range +$R_c$ satisfies $R_c \geq 2 \cdot R_s$. In fact, \citet{Zhang05} +proved that if the transmission range fulfills the previous hypothesis, the +complete coverage of a convex area implies connectivity among active nodes. + +The PeCO protocol uses the same perimeter-coverage model as \citet{huang2005coverage}. It can be expressed as follows: a sensor is +said to be perimeter covered if all the points on its perimeter are covered by +at least one sensor other than itself. They proved that a network area is +$k$-covered if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors). + +Figure~\ref{figure1}(a) shows the coverage of sensor node~$0$. On this +figure, we can see that sensor~$0$ has nine neighbors and we have reported on +its perimeter (the perimeter of the disk covered by the sensor) for each +neighbor the two points resulting from the intersection of the two sensing +areas. These points are denoted for neighbor~$i$ by $iL$ and $iR$, respectively +for left and right from a neighboing point of view. The resulting couples of +intersection points subdivide the perimeter of sensor~$0$ into portions called +arcs. + +\begin{figure}[ht!] + \centering + \begin{tabular}{@{}cr@{}} + \includegraphics[width=75mm]{figure1a.eps} & \raisebox{3.25cm}{(a)} \\ + \includegraphics[width=75mm]{figure1b.eps} & \raisebox{2.75cm}{(b)} + \end{tabular} + \caption{(a) Perimeter coverage of sensor node 0 and (b) finding the arc of + $u$'s perimeter covered by $v$.} + \label{figure1} +\end{figure} + +Figure~\ref{figure1}(b) describes the geometric information used to find the +locations of the left and right points of an arc on the perimeter of a sensor +node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the +west side of sensor~$u$, with the following respective coordinates in the +sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates we can +compute the euclidean distance between nodes~$u$ and $v$: $Dist(u,v)=\sqrt{\vert + u_x - v_x \vert^2 + \vert u_y-v_y \vert^2}$, while the angle~$\alpha$ is +obtained through the formula: + \[ +\alpha = \arccos \left(\frac{Dist(u,v)}{2R_s} +\right). +\] +The arc on the perimeter of~$u$ defined by the angular interval $[\pi + - \alpha,\pi + \alpha]$ is said to be perimeter-covered by sensor~$v$. + +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 +in the interval $[0,2\pi)$. More precisely, we can see that 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 +from the first intersection point after point~zero, and the maximum level of +coverage is determined for each interval defined by two successive points. The +maximum level of coverage is equal to the number of overlapping arcs. For +example, +between~$5L$ and~$6L$ the maximum level of coverage is equal to $3$ +(the value is highlighted in yellow at the bottom of Figure~\ref{figure2}), which +means that at most 2~neighbors can cover the perimeter in addition to node $0$. +Table~\ref{my-label} summarizes for each coverage interval the maximum level of +coverage and the sensor nodes covering the perimeter. The example discussed +above is thus given by the sixth line of the table. + + +\begin{figure*}[t!] +\centering +\includegraphics[width=127.5mm]{figure2.eps} +\caption{Maximum coverage levels for perimeter of sensor node $0$.} +\label{figure2} +\end{figure*} + + + + + \begin{table} + \tbl{Coverage intervals and contributing sensors for sensor node 0 \label{my-label}} +{\begin{tabular}{|c|c|c|c|c|c|c|c|c|} +\hline +\begin{tabular}[c]{@{}c@{}}Left \\ point \\ angle~$\alpha$ \end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ left \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Interval \\ right \\ point\end{tabular} & \begin{tabular}[c]{@{}c@{}}Maximum \\ coverage\\ level\end{tabular} & \multicolumn{5}{c|}{\begin{tabular}[c]{@{}c@{}}Set of sensors\\ involved \\ in coverage interval\end{tabular}} \\ \hline +0.0291 & 1L & 2L & 4 & 0 & 1 & 3 & 4 & \\ \hline +0.104 & 2L & 3R & 5 & 0 & 1 & 3 & 4 & 2 \\ \hline +0.3168 & 3R & 4R & 4 & 0 & 1 & 4 & 2 & \\ \hline +0.6752 & 4R & 1R & 3 & 0 & 1 & 2 & & \\ \hline +1.8127 & 1R & 5L & 2 & 0 & 2 & & & \\ \hline +1.9228 & 5L & 6L & 3 & 0 & 2 & 5 & & \\ \hline +2.3959 & 6L & 2R & 4 & 0 & 2 & 5 & 6 & \\ \hline +2.4258 & 2R & 7L & 3 & 0 & 5 & 6 & & \\ \hline +2.7868 & 7L & 8L & 4 & 0 & 5 & 6 & 7 & \\ \hline +2.8358 & 8L & 5R & 5 & 0 & 5 & 6 & 7 & 8 \\ \hline +2.9184 & 5R & 7R & 4 & 0 & 6 & 7 & 8 & \\ \hline +3.3301 & 7R & 9R & 3 & 0 & 6 & 8 & & \\ \hline +3.9464 & 9R & 6R & 4 & 0 & 6 & 8 & 9 & \\ \hline +4.767 & 6R & 3L & 3 & 0 & 8 & 9 & & \\ \hline +4.8425 & 3L & 8R & 4 & 0 & 3 & 8 & 9 & \\ \hline +4.9072 & 8R & 4L & 3 & 0 & 3 & 9 & & \\ \hline +5.3804 & 4L & 9R & 4 & 0 & 3 & 4 & 9 & \\ \hline +5.9157 & 9R & 1L & 3 & 0 & 3 & 4 & & \\ \hline +\end{tabular}} + + +\end{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 +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$ +and the corresponding interval will not be taken into account by the +optimization algorithm. + + \newpage +\begin{figure}[h!] +\centering +\includegraphics[width=62.5mm]{figure3.eps} +\caption{Sensing range outside the WSN's area of interest.} +\label{figure3} +\end{figure} + + +\subsection{The Main Idea} + +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. + +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 +(INFO) Exchange, Leader Election, Decision (the result of an optimization +problem), and Sensing. For each period there is exactly one set cover +responsible for the sensing task. Protocols based on a periodic scheme, like +PeCO, are more robust against an unexpected node failure. On the one hand, if +a node failure is discovered before taking the decision, the corresponding sensor +node will not be considered by the optimization algorithm. On the other +hand, if the sensor failure happens after the decision, the sensing task of the +network will be temporarily affected: only during the period of sensing until a +new period starts, since a new set cover will take charge of the sensing task in +the next period. The energy consumption and some other constraints can easily be +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. + +\begin{figure}[t!] +\centering +\includegraphics[width=80mm]{figure4.eps} +\caption{PeCO protocol.} +\label{figure4} +\end{figure} + +We define two types of packets to be used by PeCO protocol: + +\begin{itemize} +\item INFO packet: sent by each sensor node to all the nodes inside a same + subregion for information exchange. +\item ActiveSleep packet: sent by the leader to all the nodes in its subregion + to transmit to them their respective status (stay Active or go Sleep) during + sensing phase. +\end{itemize} + + +Five statuses are possible for a sensor node in the network: + +\begin{itemize} +\item LISTENING: waits for a decision (to be active or not); +\item COMPUTATION: executes the optimization algorithm as leader to + determine the activities scheduling; +\item ACTIVE: node is sensing; +\item SLEEP: node is turned off; +\item COMMUNICATION: transmits or receives packets. +\end{itemize} + + +\subsection{PeCO Protocol Algorithm} + +The pseudocode implementing the protocol on a node is given below. +More precisely, Algorithm~\ref{alg:PeCO} gives a brief description of the +protocol applied by a sensor node $s_k$ where $k$ is the node index in the WSN. + + + +\begin{algorithm} + % \KwIn{all the parameters related to information exchange} +% \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)} +% \BlankLine + %\emph{Initialize the sensor node and determine it's position and subregion} \; + +\noindent{\bf If} $RE_k \geq E_{th}$ {\bf then}\\ +\hspace*{0.6cm} \emph{$s_k.status$ = COMMUNICATION;}\\ +\hspace*{0.6cm} \emph{Send $INFO()$ packet to other nodes in subregion;}\\ +\hspace*{0.6cm} \emph{Wait $INFO()$ packet from other nodes in subregion;}\\ +\hspace*{0.6cm} \emph{Update K.CurrentSize;}\\ +\hspace*{0.6cm} \emph{LeaderID = Leader election;}\\ +\hspace*{0.6cm} {\bf If} $ s_k.ID = LeaderID $ {\bf then}\\ +\hspace*{1.2cm} \emph{$s_k.status$ = COMPUTATION;}\\ +\hspace*{1.2cm}{\bf If} \emph{$ s_k.ID $ is Not previously selected as a Leader} {\bf then}\\ +\hspace*{1.8cm} \emph{ Execute the perimeter coverage model;}\\ +\hspace*{1.2cm} {\bf end}\\ +\hspace*{1.2cm}{\bf If} \emph{($s_k.ID $ is the same Previous Leader)~And~(K.CurrentSize = K.PreviousSize)}\\ +\hspace*{1.8cm} \emph{ Use the same previous cover set for current sensing stage;}\\ +\hspace*{1.2cm} {\bf end}\\ +\hspace*{1.2cm} {\bf else}\\ +\hspace*{1.8cm}\emph{Update $a^j_{ik}$; prepare data for IP~Algorithm;}\\ +\hspace*{1.8cm} \emph{$\left\{\left(X_{1},\dots,X_{l},\dots,X_{K}\right)\right\}$ = Execute Integer Program Algorithm($K$);}\\ +\hspace*{1.8cm} \emph{K.PreviousSize = K.CurrentSize;}\\ +\hspace*{1.2cm} {\bf end}\\ +\hspace*{1.2cm}\emph{$s_k.status$ = COMMUNICATION;}\\ +\hspace*{1.2cm}\emph{Send $ActiveSleep()$ to each node $l$ in subregion;}\\ +\hspace*{1.2cm}\emph{Update $RE_k $;}\\ +\hspace*{0.6cm} {\bf end}\\ +\hspace*{0.6cm} {\bf else}\\ +\hspace*{1.2cm}\emph{$s_k.status$ = LISTENING;}\\ +\hspace*{1.2cm}\emph{Wait $ActiveSleep()$ packet from the Leader;}\\ +\hspace*{1.2cm}\emph{Update $RE_k $;}\\ +\hspace*{0.6cm} {\bf end}\\ +{\bf end}\\ +{\bf else}\\ +\hspace*{0.6cm} \emph{Exclude $s_k$ from entering in the current sensing stage;}\\ +{\bf end}\\ +\label{alg:PeCO} +\end{algorithm} + + + +In this algorithm, K.CurrentSize and K.PreviousSize respectively represent the +current number and the previous number of living nodes in the subnetwork of the +subregion. Initially, the sensor node checks its remaining energy $RE_k$, which +must be greater than a threshold $E_{th}$ in order to participate in the current +period. Each sensor node determines its position and its subregion using an +embedded GPS or a location discovery algorithm. After that, all the sensors +collect position coordinates, remaining energy, sensor node ID, and the number +of their one-hop live neighbors during the information exchange. The sensors +inside a same region cooperate to elect a leader. The selection criteria for the +leader, in order of priority, are: larger numbers of neighbors, larger remaining +energy, and then in case of equality, larger index. Once chosen, the leader +collects information to formulate and solve the integer program which allows to +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. We +start with a description of the notations that will be used throughout the +section.\\ +First, we have the following sets: +\begin{itemize} +\item $S$ represents the set of WSN sensor nodes; +\item $A \subseteq S $ is the subset of alive sensors; +\item $I_j$ designates the set of coverage intervals (CI) obtained for + sensor~$j$. +\end{itemize} +$I_j$ refers to the set of coverage intervals which have been defined according +to the method introduced in subsection~\ref{CI}. For a coverage interval $i$, +let $a^j_{ik}$ denotes the indicator function of whether sensor~$k$ is involved +in coverage interval~$i$ of sensor~$j$, that is: +\begin{equation} +a^j_{ik} = \left \{ +\begin{array}{lll} + 1 & \mbox{if sensor $k$ is involved in the } \\ + & \mbox{coverage interval $i$ of sensor $j$}, \\ + 0 & \mbox{otherwise.}\\ +\end{array} \right. +\end{equation} +Note that $a^k_{ik}=1$ by definition of the interval. + +Second, we define several binary and integer variables. 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 +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 +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 +period to ensure the desired coverage level. As the number of alive sensors +decreases, it becomes impossible to reach the desired level of coverage for all +coverage intervals. Therefore we use variables $M^j_i$ and $V^j_i$ as a measure +of the deviation between the desired number of active sensors in a coverage +interval and the effective number. And we try to minimize these deviations, +first to force the activation of a minimal number of sensors to ensure the +desired coverage level, and if the desired level cannot be completely satisfied, +to reach a coverage level as close as possible to the desired one. + + + + +Our coverage optimization problem can then be mathematically expressed as follows: + +\begin{equation} +\left \{ +\begin{array}{ll} +\min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\ +\textrm{subject to :}&\\ +\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i \geq l \quad \forall i \in I_j, \forall j \in S\\ +\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i \leq l \quad \forall i \in I_j, \forall j \in S\\ +X_{k} \in \{0,1\}, \forall k \in A +\end{array} +\right. +\end{equation} + +$\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 +brachytherapy treatment planning for optimizing dose distribution +\citep{0031-9155-44-1-012}. The 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 we +consider only alive sensors (sensors with enough energy to be alive during one +sensing phase) in the model. + +\section{Performance Evaluation and Analysis} +\label{sec:Simulation Results and Analysis} + + +\subsection{Simulation Settings} + + +The WSN area of interest is supposed to be divided into 16~regular subregions +and we use the same energy consumption model as in our previous work~\citep{Idrees2}. +Table~\ref{table3} gives the chosen parameters settings. + +\begin{table}[ht] +\tbl{Relevant parameters for network initialization \label{table3}}{ + +\centering + +\begin{tabular}{c|c} + +\hline +Parameter & Value \\ [0.5ex] + +\hline +% inserts single horizontal line +Sensing field & $(50 \times 25)~m^2 $ \\ + +WSN size & 100, 150, 200, 250, and 300~nodes \\ + +Initial energy & in range 500-700~Joules \\ + +Sensing period & duration of 60 minutes \\ +$E_{th}$ & 36~Joules\\ +$R_s$ & 5~m \\ + +$\alpha^j_i$ & 0.6 \\ + +$\beta^j_i$ & 0.4 + +\end{tabular}} + + +\end{table} +To obtain experimental results which are relevant, simulations with five +different node densities going from 100 to 300~nodes were performed considering +each time 25~randomly generated networks. The nodes are deployed on a field of +interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a +high coverage ratio. Each node has an initial energy level, in Joules, which is +randomly drawn in the interval $[500-700]$. If its energy provision reaches a +value below the threshold $E_{th}=36$~Joules, the minimum energy needed for a +node to stay active during one period, it will no longer participate in the +coverage task. This value corresponds to the energy needed by the sensing phase, +obtained by multiplying the energy consumed in the active state (9.72 mW) with the +time in seconds for one period (3600 seconds), and adding the energy for the +pre-sensing phases. According to the interval of initial energy, a sensor may +be active during at most 20 periods. + +The values of $\alpha^j_i$ and $\beta^j_i$ have been chosen to ensure a good +network coverage and a longer WSN lifetime. We have given a higher priority to +the undercoverage (by setting the $\alpha^j_i$ with a larger value than +$\beta^j_i$) so as to prevent the non-coverage for the interval~$i$ of the +sensor~$j$. On the other hand, we have assigned to +$\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute +in covering the interval. + +We introduce the following performance metrics to evaluate the efficiency of our +approach. + + +\begin{itemize} +\item {\bf Network Lifetime}: the lifetime is defined as the time elapsed until + the coverage ratio falls below a fixed threshold. $Lifetime_{95}$ and + $Lifetime_{50}$ denote, respectively, the amount of time during which is + guaranteed a level of coverage greater than $95\%$ and $50\%$. The WSN can + fulfill the expected monitoring task until all its nodes have depleted their + energy or if the network is no more connected. This last condition is crucial + because without network connectivity a sensor may not be able to send to a + base station an event it has sensed. +\item {\bf Coverage Ratio (CR)} : it measures how well the WSN is able to + observe the area of interest. In our case, we discretized the sensor field as + a regular grid, which yields the following equation: + + +\[ + \scriptsize + \mbox{CR}(\%) = \frac{\mbox{$n$}}{\mbox{$N$}} \times 100 +\] + + + where $n$ is the number of covered grid points by active sensors of every + subregions during the current sensing phase and $N$ is total number of grid + points in the sensing field. In our simulations we have set a layout of + $N~=~51~\times~26~=~1326$~grid points. +\item {\bf Active Sensors Ratio (ASR)}: a major objective of our protocol is to + activate as few nodes as possible, in order to minimize the communication + overhead and maximize the WSN lifetime. The active sensors ratio is defined as + follows: + +\[ + \scriptsize + \mbox{ASR}(\%) = \frac{\sum\limits_{r=1}^R \mbox{$|A_r^p|$}}{\mbox{$|J|$}} \times 100 +\] + + where $|A_r^p|$ is the number of active sensors in the subregion $r$ in the + current sensing period~$p$, $|J|$ is the number of sensors in the network, and + $R$ is the number of subregions. +\item {\bf Energy Consumption (EC)}: energy consumption can be seen as the total + energy consumed by the sensors during $Lifetime_{95}$ or $Lifetime_{50}$, + divided by the number of periods. The value of EC is computed according to + this formula: + +\[ + \scriptsize + \mbox{EC} = \frac{\sum\limits_{p=1}^{P} \left( E^{\mbox{com}}_p+E^{\mbox{list}}_p+E^{\mbox{comp}}_p + + E^{a}_p+E^{s}_p \right)}{P}, +\] + + where $P$ corresponds to the number of periods. The total energy consumed by + the sensors comes through taking into consideration four main energy + factors. The first one, denoted $E^{\scriptsize \mbox{com}}_p$, represents the + energy consumption spent by all the nodes for wireless communications during + period $p$. $E^{\scriptsize \mbox{list}}_p$, the next factor, corresponds to + the energy consumed by the sensors in LISTENING status before receiving the + decision to go active or sleep in period $p$. $E^{\scriptsize \mbox{comp}}_p$ + refers to the energy needed by all the leader nodes to solve the integer + program during a period. Finally, $E^a_{p}$ and $E^s_{p}$ indicate the energy + consumed by the WSN during the sensing phase (active and sleeping nodes). +\end{itemize} + + +\subsection{Simulation Results} + +In order to assess and analyze the performance of our protocol we have +implemented PeCO protocol in OMNeT++~\citep{varga} simulator. Besides PeCO, two +other protocols, described in the next paragraph, will be evaluated for +comparison purposes. The simulations were run on a DELL laptop with an Intel +Core~i3~2370~M (1.8~GHz) processor (2 cores) whose MIPS (Million Instructions +Per Second) rate is equal to 35330. To be consistent with the use of a sensor +node based on Atmels AVR ATmega103L microcontroller (6~MHz) having a MIPS rate +equal to 6, the original execution time on the laptop is multiplied by 2944.2 +$\left(\frac{35330}{2} \times \frac{1}{6} \right)$. The modeling language for +Mathematical Programming (AMPL)~\citep{AMPL} is employed to generate the integer +program instance in a standard format, which is then read and solved by the +optimization solver GLPK (GNU linear Programming Kit available in the public +domain) \citep{glpk} through a Branch-and-Bound method. + +As said previously, the PeCO is compared to three other approaches. The first +one, called DESK, is a fully distributed coverage algorithm proposed by +\citep{ChinhVu}. The second one, called GAF~\citep{xu2001geography}, consists in +dividing the monitoring area into fixed squares. Then, during the decision +phase, in each square, one sensor is chosen to remain active during the sensing +phase. The last one, the DiLCO protocol~\citep{Idrees2}, is an improved version +of a research work we presented in~\citep{idrees2014coverage}. Let us notice that +PeCO and DiLCO protocols are based on the same framework. In particular, the +choice for the simulations of a partitioning in 16~subregions was made because +it corresponds to the configuration producing the best results for DiLCO. The +protocols are distinguished from one another by the formulation of the integer +program providing the set of sensors which have to be activated in each sensing +phase. DiLCO protocol tries to satisfy the coverage of a set of primary points, +whereas the PeCO protocol objective is to reach a desired level of coverage for each +sensor perimeter. In our experimentations, we chose a level of coverage equal to +one ($l=1$). + +\subsubsection{\bf Coverage Ratio} + +Figure~\ref{figure5} shows the average coverage ratio for 200 deployed nodes +obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better +coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, compared to the 98.76\% +produced by PeCO for the first periods. This is due to the fact that at the +beginning the DiLCO protocol puts to sleep status more redundant sensors (which +slightly decreases the coverage ratio), while the three other protocols activate +more sensor nodes. Later, when the number of periods is beyond~70, it clearly +appears that PeCO provides a better coverage ratio and keeps a coverage ratio +greater than 50\% for longer periods (15 more compared to DiLCO, 40 more +compared to DESK). The energy saved by PeCO in the early periods allows later a +substantial increase of the coverage performance. + +\parskip 0pt +\begin{figure}[h!] +\centering + \includegraphics[scale=0.5] {figure5.eps} +\caption{Coverage ratio for 200 deployed nodes.} +\label{figure5} +\end{figure} + + + + +\subsubsection{\bf Active Sensors Ratio} + +Having the less active sensor nodes in each period is essential to minimize the +energy consumption and thus to maximize the network lifetime. Figure~\ref{figure6} +shows the average active nodes ratio for 200 deployed nodes. We observe that +DESK and GAF have 30.36 \% and 34.96 \% active nodes for the first fourteen +rounds and DiLCO and PeCO protocols compete perfectly with only 17.92~\% and +20.16~\% active nodes during the same time interval. As the number of periods +increases, PeCO protocol has a lower number of active nodes in comparison with +the three other approaches, while keeping a greater coverage ratio as shown in +Figure \ref{figure5}. + +\begin{figure}[h!] +\centering +\includegraphics[scale=0.5]{figure6.eps} +\caption{Active sensors ratio for 200 deployed nodes.} +\label{figure6} +\end{figure} + +\subsubsection{\bf Energy Consumption} + +We studied the effect of the energy consumed by the WSN during the communication, +computation, listening, active, and sleep status for different network densities +and compared it for the four approaches. Figures~\ref{figure7}(a) and (b) +illustrate the energy consumption for different network sizes and for +$Lifetime95$ and $Lifetime50$. The results show that our PeCO protocol is the +most competitive from the energy consumption point of view. As shown in both +figures, PeCO consumes much less energy than the three other methods. One might +think that the resolution of the integer program is too costly in energy, but +the results show that it is very beneficial to lose a bit of time in the +selection of sensors to activate. Indeed the optimization program allows to +reduce significantly the number of active sensors and so the energy consumption +while keeping a good coverage level. + +\begin{figure}[h!] + \centering + \begin{tabular}{@{}cr@{}} + \includegraphics[scale=0.475]{figure7a.eps} & \raisebox{2.75cm}{(a)} \\ + \includegraphics[scale=0.475]{figure7b.eps} & \raisebox{2.75cm}{(b)} + \end{tabular} + \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.} + \label{figure7} +\end{figure} + + + +\subsubsection{\bf Network Lifetime} + +We observe the superiority of PeCO and DiLCO protocols in comparison with the +two other approaches in prolonging the network lifetime. In +Figures~\ref{figure8}(a) and (b), $Lifetime95$ and $Lifetime50$ are shown for +different network sizes. As highlighted by these figures, the lifetime +increases with the size of the network, and it is clearly largest for DiLCO +and PeCO protocols. For instance, for a network of 300~sensors and coverage +ratio greater than 50\%, we can see on Figure~\ref{figure8}(b) that the lifetime +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\%. + +\begin{figure}[h!] + \centering + \begin{tabular}{@{}cr@{}} + \includegraphics[scale=0.475]{figure8a.eps} & \raisebox{2.75cm}{(a)} \\ + \includegraphics[scale=0.475]{figure8b.eps} & \raisebox{2.75cm}{(b)} + \end{tabular} + \caption{Network Lifetime for (a)~$Lifetime_{95}$ \\ + and (b)~$Lifetime_{50}$.} + \label{figure8} +\end{figure} + + + +Figure~\ref{figure9} compares the lifetime coverage of our protocols for +different coverage ratios. We denote by Protocol/50, Protocol/80, Protocol/85, +Protocol/90, and Protocol/95 the amount of time during which the network can +satisfy an area coverage greater than $50\%$, $80\%$, $85\%$, $90\%$, and $95\%$ +respectively, where the term Protocol refers to DiLCO or PeCO. Indeed there are applications +that do not require a 100\% coverage of the area to be monitored. PeCO might be +an interesting method since it achieves a good balance between a high level +coverage ratio and network lifetime. PeCO always outperforms DiLCO for the three +lower coverage ratios, moreover the improvements grow with the network +size. DiLCO is better for coverage ratios near 100\%, but in that case PeCO is +not ineffective for the smallest network sizes. + +\begin{figure}[h!] +\centering \includegraphics[scale=0.5]{figure9.eps} +\caption{Network lifetime for different coverage ratios.} +\label{figure9} +\end{figure} + + + + +\section{Conclusion and Future Works} +\label{sec:Conclusion and Future Works} + +In this paper we have studied the problem of Perimeter-based Coverage Optimization in +WSNs. We have designed a new protocol, called Perimeter-based Coverage Optimization, which +schedules nodes' activities (wake up and sleep stages) with the objective of +maintaining a good coverage ratio while maximizing the network lifetime. This +protocol is applied in a distributed way in regular subregions obtained after +partitioning the area of interest in a preliminary step. It works in periods and +is based on the resolution of an integer program to select the subset of sensors +operating in active status for each period. Our work is original in so far as it +proposes for the first time an integer program scheduling the activation of +sensors based on their perimeter coverage level, instead of using a set of +targets/points to be covered. + + +We have carried out several simulations to evaluate the proposed protocol. The +simulation results show that PeCO is more energy-efficient than other +approaches, with respect to lifetime, coverage ratio, active sensors ratio, and +energy consumption. + +We plan to extend our framework so that the schedules are planned for multiple +sensing periods. + +We also want to improve our integer program to take into account heterogeneous +sensors from both energy and node characteristics point of views. + +Finally, it would be interesting to implement our protocol using a +sensor-testbed to evaluate it in real world applications. + +\bibliographystyle{gENO} +\bibliography{biblio} + + +\end{document}