X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/b8c29e4970d4776b8a6b2aecaeac93b05fa8114a..4db673f695b83fcf69011cdea52cb6d3d7c78892:/CHAPITRE_02.tex?ds=inline diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex old mode 100644 new mode 100755 index 635c15a..7aaafbe --- a/CHAPITRE_02.tex +++ b/CHAPITRE_02.tex @@ -102,6 +102,14 @@ The works presented in~\cite{ref134,ref135,ref136} focus on coverage-aware, dist Shibo et al.~\cite{ref137} have expressed the coverage problem as a minimum weight submodular set cover problem and proposed a Distributed Truncated Greedy Algorithm (DTGA) to solve it. They take advantage from both temporal and spatial correlations between data sensed by different sensors, and leverage prediction, to improve the lifetime. +In \cite{ref160} authors transform the area coverage problem to the target +coverage one taking into account the intersection points among disks of sensors +nodes or between disk of sensor nodes and boundaries. + + +In \cite{ref133} 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 neighboring to a sensor and $n$ is the total number of sensors in the network. + In \cite{ref84}, Xu et al. have described an algorithm, called Geographical Adaptive Fidelity (GAF), which uses geographic location information to divide the area of interest into fixed square grids. Within each grid, it keeps only one node staying awake to take the responsibility of sensing and communication. Figure~\ref{gaf1} gives an example of fixed square grid in GAF. @@ -170,89 +178,97 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e \caption{Main characteristics of some coverage approaches in previous literatures.} \begin{tabular}{@{} cl*{13}c @{}} & & \multicolumn{10}{c}{Characteristics} \\[2ex] - & & \mcrot{1}{l}{50}{\footnotesize Distributed} & \mcrot{1}{l}{50}{\footnotesize Centralized} & \mcrot{1}{l}{50}{ \footnotesize Area coverage} & \mcrot{1}{l}{50}{\footnotesize Target coverage} & \mcrot{1}{l}{50}{\footnotesize k-coverage} & \mcrot{1}{l}{50}{\footnotesize Heterogeneous nodes}& \mcrot{1}{l}{50}{\footnotesize Homogeneous nodes} & \mcrot{1}{l}{50}{\footnotesize Disjoint sets} & \mcrot{1}{l}{50}{\footnotesize Non-Disjoint sets} & \mcrot{1}{l}{50}{\footnotesize Energy-Efficient} & \mcrot{1}{l}{50}{\footnotesize Work in Rounds} & \mcrot{1}{l}{50}{\footnotesize Adjustable Radius} \\ + & & \mcrot{1}{l}{50}{\footnotesize Distributed} & \mcrot{1}{l}{50}{\footnotesize Centralized} & \mcrot{1}{l}{50}{ \footnotesize Area coverage} & \mcrot{1}{l}{50}{\footnotesize Target coverage} & \mcrot{1}{l}{50}{\footnotesize k-coverage} & \mcrot{1}{l}{50}{\footnotesize Heterogeneous nodes}& \mcrot{1}{l}{50}{\footnotesize Homogeneous nodes} & \mcrot{1}{l}{50}{\footnotesize Disjoint sets} & \mcrot{1}{l}{50}{\footnotesize Non-Disjoint sets} & \mcrot{1}{l}{50}{\footnotesize SET K-COVER } & \mcrot{1}{l}{50}{\footnotesize Work in Rounds} & \mcrot{1}{l}{50}{\footnotesize Adjustable Radius} \\ \cmidrule[1pt]{2-14} -& \tiny Z. Abrams et al. (2004)~\cite{ref114} & & & & & & & & & & & & &\\ +& \tiny Z. Abrams et al. (2004)~\cite{ref114} & \OK &\OK & \OK & & & &\OK & \OK & & \OK & & &\\ + +& \tiny M. Cardei and D. Du (2005)~\cite{ref115} & & \OK & & \OK & & & \OK & \OK & & \OK & & &\\ + +& \tiny S. Slijepcevic and M. Potkonjak (2001)~\cite{ref116} & & \OK & \OK & & & & \OK & \OK & & \OK & & &\\ -& \tiny M. Cardei and D. Du (2005)~\cite{ref115} & & & & & & & & & & & & &\\ +& \tiny Manjun and A. K. Pujari (2011)~\cite{ref117} & & \OK & & \OK & & & \OK & & \OK & & & &\\ -& \tiny S. Slijepcevic and M. Potkonjak (2001)~\cite{ref116} & & & & & & & & & & & & &\\ +& \tiny M. Yang and J. Liu (2014)~\cite{ref118} & & \OK & \OK & & & & \OK & & \OK & & & & \\ -& \tiny Manjun and A. K. Pujari (2011)~\cite{ref117} & & & & & & & & & & & & &\\ +& \tiny S. Wang et al. (2010)~\cite{ref144} & & \OK & \OK & & & & \OK & & \OK & & \OK & & \\ -& \tiny M. Yang and J. Liu (2014)~\cite{ref118} & & & & & & & & & & & & &\\ +& \tiny C. Lin et al. (2010)~\cite{ref147} & & \OK & \OK & & & & \OK & & \OK & & & & \\ -& \tiny S. Wang et al. (2010)~\cite{ref144} & & & & & & & & & & & & &\\ +& \tiny S. A. R. Zaidi et al. (2009)~\cite{ref148} & & \OK & \OK & & & & \OK & & \OK & & & & \\ -& \tiny C. Lin et al. (2010)~\cite{ref147} & & & & & & & & & & & & &\\ +& \tiny Y. Li et al. (2011)~\cite{ref142} & & \OK & \OK & & & \OK & \OK & \OK & & \OK & & \OK &\\ -& \tiny S. A. R. Zaidi et al. (2009)~\cite{ref148} & & & & & & & & & & & & &\\ +& \tiny H. M. Ammari and S. K. Das (2012)~\cite{ref152} & \OK & \OK & \OK & & \OK & & \OK & & \OK & & \OK & &\\ -& \tiny Y. Li et al. (2011)~\cite{ref142} & & & & & & & & & & & &\\ +& \tiny L. Liu et al. (2010)~\cite{ref150} & & \OK & & \OK & & \OK & & \OK & & \OK & & &\\ -& \tiny H. M. Ammari and S. K. Das (2012)~\cite{ref152} & & & & & & & & & & & & &\\ +& \tiny H. Cheng et al. (2014)~\cite{ref119} & & \OK & \OK & & & & \OK & & \OK & & & &\\ -& \tiny L. Liu et al. (2010)~\cite{ref150} & & & & & & & & & & & & &\\ +& \tiny M. Rebai et al. (2014)~\cite{ref141} & & \OK & \OK & & & & \OK & & \OK & & & &\\ -& \tiny H. Cheng et al. (2014)~\cite{ref119} & & & & & & & & & & & & &\\ +& \tiny L. Aslanyan et al. (2013)~\cite{ref151} & & \OK & \OK & & & & \OK & & \OK & \OK & \OK & &\\ -& \tiny M. Rebai et al. (2014)~\cite{ref141} & & & & & & & & & & & & &\\ +& \tiny X. Liu et al. (2014)~\cite{ref143} & & \OK & \OK & & & & \OK & & \OK & \OK & \OK & &\\ -& \tiny L. Aslanyan et al. (2013)~\cite{ref151} & & & & & & & & & & & & &\\ +& \tiny F. Castano et al. (2013)~\cite{ref120} & & \OK & & \OK & & & \OK & & \OK & \OK & & &\\ -& \tiny X. Liu et al. (2014)~\cite{ref143} & & & & & & & & & & & & &\\ +& \tiny A. Rossi et al. (2012)~\cite{ref121} & & \OK & & \OK & & \OK & \OK & & \OK & \OK & & \OK &\\ -& \tiny F. Castano et al. (2013)~\cite{ref120} & & & & & & & & & & & & &\\ +& \tiny K. Deschinkel et al. (2012)~\cite{ref122} & & \OK & & \OK & & & \OK & & \OK & \OK & & &\\ -& \tiny A. Rossi et al. (2012)~\cite{ref121} & & & & & & & & & & & & &\\ -& \tiny K. Deschinkel et al. (2012)~\cite{ref122} & & & & & & & & & & & & &\\ -\rot{\rlap{Some Proposed Coverage Protocols in previous literatures}} +& \tiny A. Gallais et al. (2008)~\cite{ref123} & \OK & & \OK & & & \OK & \OK & & \OK & & \OK & \OK &\\ -& \tiny A. Gallais et al. (2006)~\cite{ref123} & & & & & & & & & & & & &\\ +& \tiny D. Tian and N. D. Georganas (2002)~\cite{ref124} & \OK & & \OK & & & & \OK & & \OK & & \OK & &\\ -& \tiny D. Tian and N. D. Georganas (2002)~\cite{ref124} & & & & & & & & & & & & &\\ +& \tiny F. Ye et al. (2003)~\cite{ref125} & \OK & & \OK & & & & \OK & & \OK & & & &\\ -& \tiny F. Ye et al. (2003)~\cite{ref125} & & & & & & & & & & & & &\\ +& \tiny H. Zhang and J. C. Hou (2005)~\cite{ref126} & \OK & & \OK & & & & \OK & & \OK & & \OK & &\\ -& \tiny H. Zhang and J. C. Hou (2005)~\cite{ref126} & & & & & & & & & & & & &\\ +& \tiny W. B. Heinzelman et al. (2002)~\cite{ref109} & \OK & & \OK & & & & \OK & & \OK & & \OK & &\\ -& \tiny W. B. Heinzelman et al. (2002)~\cite{ref109} & & & & & & & & & & & & &\\ +& \tiny T. Yardibi and E. Karasan (2010)~\cite{ref127} & \OK & & \OK & & & & \OK & & \OK & & \OK & &\\ -& \tiny T. Yardibi and E. Karasan (2010)~\cite{ref127} & & & & & & & & & & & & &\\ +& \tiny S. K. Prasad and A. Dhawan (2007)~\cite{ref128} & \OK & & & \OK & & & \OK & & \OK & & \OK & &\\ -& \tiny S. K. Prasad and A. Dhawan (2007)~\cite{ref128} & & & & & & & & & & & & &\\ +& \tiny S. Misra et al. (2011)~\cite{ref129} & \OK & & \OK & & & & \OK & & \OK & & & &\\ -& \tiny S. Misra et al. (2011)~\cite{ref129} & & & & & & & & & & & & &\\ +& \tiny P. Berman et al. (2005)~\cite{ref130} & \OK & \OK & \OK & & & & \OK & & \OK & \OK & &\\ -& \tiny P. Berman et al. (2005)~\cite{ref130} & & & & & & & & & & & &\\ +& \tiny J. Lu and T. Suda (2003)~\cite{ref131} & \OK & & \OK & & & & \OK & & \OK & & \OK & &\\ -& \tiny J. Lu and T. Suda (2003)~\cite{ref131} & & & & & & & & & & & & &\\ -& \tiny J. Cho et al. (2007)~\cite{ref145} & & & & & & & & & & & & &\\ -& \tiny V. T. Quang and T. Miyoshi (2008)~\cite{ref146} & & & & & & & & & & & & &\\ +& \tiny J. Cho et al. (2007)~\cite{ref145} & \OK & & \OK & & & & \OK & & \OK & & & &\\ -& \tiny D. Dong et al. (2012)~\cite{ref149} & & & & & & & & & & & & &\\ +& \tiny V. T. Quang and T. Miyoshi (2008)~\cite{ref146} & \OK & & \OK & & \OK & & \OK & & \OK & & \OK & &\\ -& \tiny B. Wang et al. (2012)~\cite{ref134} & & & & & & & & & & & & &\\ +\rot{\rlap{Some Proposed Coverage Protocols in previous literatures}} -& \tiny Z. Liu et al. (2012)~\cite{ref135} & & & & & & & & & & & & &\\ +& \tiny D. Dong et al. (2012)~\cite{ref149} & \OK & & \OK & & & & \OK & & \OK & & \OK & &\\ -& \tiny L. Zhang et al. (2013)~\cite{ref136} & & & & & & & & & & & & &\\ +& \tiny B. Wang et al. (2012)~\cite{ref134} & \OK & & \OK & & & & \OK & & \OK & & \OK & &\\ -& \tiny S. He et al. (2012)~\cite{ref137} & & & & & & & & & & & & &\\ +& \tiny Z. Liu et al. (2012)~\cite{ref135} & \OK & & \OK & & & & \OK & & \OK & & \OK & &\\ -& \tiny Y. Xu et al. (2001)~\cite{ref84} & & & & & & & & & & & & &\\ +& \tiny L. Zhang et al. (2013)~\cite{ref136} & \OK & & \OK & & & \OK & \OK & & \OK & & \OK & &\\ -& \tiny C. Vu et al. (2006)~\cite{ref132} & & & & & & & & & & & & &\\ +& \tiny S. He et al. (2012)~\cite{ref137} & \OK & \OK & \OK & & & & \OK & & \OK & & & &\\ + +& \tiny Y. Xu et al. (2001)~\cite{ref84} & \OK & & \OK & & & & \OK & & \OK & & & &\\ + +& \tiny C. Vu et al. (2006)~\cite{ref132} & \OK & & \OK & & \OK & & \OK & & \OK & & \OK & &\\ + +& \tiny X. Deng et al. (2012)~\cite{ref160} & \OK & & \OK & & & & \OK & & \OK & & & &\\ + +& \tiny X. Deng et al. (2005)~\cite{ref133} & \OK & & \OK & & \OK & & \OK & & \OK & & & &\\ &\textbf{\textcolor{red}{ \tiny DiLCO Protocol (2014)}} & \textbf{\textcolor{red}{\OK}} & & \textbf{\textcolor{red}{\OK}} & & & \textbf{\textcolor{red}{\OK}} & \textbf{\textcolor{red}{\OK}} & & & &\textbf{\textcolor{red}{\OK}} & & \\ -&\textbf{\textcolor{red}{ \tiny MuDiLCO Protocol (2014)}} & \textbf{\textcolor{red}{\OK}} & & \textbf{\textcolor{red}{\OK}} & & & \textbf{\textcolor{red}{\OK}} & \textbf{\textcolor{red}{\OK}} & & & &\textbf{\textcolor{red}{\OK}} & & \\ +&\textbf{\textcolor{red}{ \tiny MuDiLCO Protocol (2014)}} & \textbf{\textcolor{red}{\OK}} & & \textbf{\textcolor{red}{\OK}} & & & \textbf{\textcolor{red}{\OK}} & \textbf{\textcolor{red}{\OK}} & & & \textbf{\textcolor{red}{\OK}} &\textbf{\textcolor{red}{\OK}} & & \\ &\textbf{\textcolor{red}{ \tiny LiCO Protocol (2014)}} & \textbf{\textcolor{red}{\OK}} & & \textbf{\textcolor{red}{\OK}} & & & \textbf{\textcolor{red}{\OK}} & \textbf{\textcolor{red}{\OK}} & & & &\textbf{\textcolor{red}{\OK}} & & \\ @@ -267,6 +283,7 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e + \section{Conclusion} \label{ch2:sec:05} This chapter has been described some coverage problems proposed in the literature, and their assumptions and proposed solutions.