X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/b8c29e4970d4776b8a6b2aecaeac93b05fa8114a..d6d8c544df886c9662e0200ee2a41ebdfd670cb0:/CHAPITRE_02.tex?ds=sidebyside diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex old mode 100644 new mode 100755 index 635c15a..bcf9002 --- a/CHAPITRE_02.tex +++ b/CHAPITRE_02.tex @@ -38,7 +38,7 @@ in WSNs. Cardei and Wu~\cite{ref113} provide a taxonomy for coverage algorithms The choice of non-disjoint or disjoint cover sets (sensors participate or not in many cover sets), coverage type ( area, target, or barrier), coverage ratio, coverage degree (how many sensors are required to cover a target or an area) can be added to the above list. -Once a sensor nodes are deployed, a coverage algorithm is run to schedule the sensor nodes into cover sets so as to maintain sufficient coverage in the area of interest and extend the network lifetime. The WSN applications require (complete or partial) area coverage and complete target coverage. Many centralized algorithms and distributed algorithms for activity scheduling have been proposed in the literature, and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. A distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near optimal) solution based only on local information. Several algorithms to retain the coverage and maximize the network lifetime were proposed in~\cite{ref113,ref153,ref103,ref105}. Table~\ref{Table1:ch2} summarized the main characteristics of some coverage approaches in previous literatures. +Once a sensor nodes are deployed, a coverage algorithm is run to schedule the sensor nodes into cover sets so as to maintain sufficient coverage in the area of interest and extend the network lifetime. The WSN applications require (complete or partial) area coverage and complete target coverage. Many centralized algorithms and distributed algorithms for activity scheduling have been proposed in the literature, and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. A distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near optimal) solution based only on local information. Several algorithms to retain the coverage and maximize the network lifetime were proposed in~\cite{ref113,ref101,ref103,ref105}. Table~\ref{Table1:ch2} summarized the main characteristics of some coverage approaches in previous literatures. \subsection{Centralized Algorithms} @@ -86,7 +86,7 @@ Various centralized methods based on column generation approaches have also be \label{ch2:sec:04} In distributed and localized coverage algorithms, the required computation to schedule the activity of sensor nodes will be done by the cooperation among neighboring nodes. These algorithms may require more computation power for the processing by the cooperating sensor nodes, but they are more scalable for large WSNs. Localized and distributed algorithms generally result in non-disjoint set covers. -Many distributed algorithms have been developed to perform the scheduling so as to preserve coverage, see for example \cite{ref123,ref124,ref125,ref126,ref109,ref127,ref128,ref129}. +Many distributed algorithms have been developed to perform the scheduling so as to preserve coverage, see for example \cite{ref123,ref124,ref125,ref126,ref109,ref127,ref128,ref97}. Distributed algorithms typically operate in rounds for a predetermined duration. At the beginning of each round, a sensor exchanges information with its neighbors and makes a decision to either remain turned on or to go to sleep for the round. This decision is basically made on simple greedy criteria like the largest uncovered area \cite{ref130} or maximum uncovered targets \cite{ref131}. The Distributed Adaptive Sleep Scheduling Algorithm (DASSA) \cite{ref127} does not require location information of sensors while maintaining connectivity and satisfying a user defined coverage target. In DASSA, nodes use the residual energy levels and feedback from the sink for scheduling the activity of their neighbors. This feedback mechanism reduces the randomness in scheduling that would otherwise occur due to the absence of location information. @@ -102,8 +102,16 @@ 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{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. + +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{GAF}, 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. \begin{figure}[h!] \centering @@ -134,7 +142,7 @@ The sensor nodes in GAF can be in one of three states: active, sleep, or discove The sensor node sets a timer to $T_d$ seconds after entering in discovery state. As soon as the timer fires, the sensor node broadcast its discovery message and enters in active state. The active sensor node sets a timeout value $T_a$ to define how long it can stay in active state. After $T_a$, the sensor node will return to the discovery state. Whilst, during its active state, it re-broadcasts its discovery message at intervals $T_d$ periodically. The sensor node with discovery or active state can change its state to sleep when it detects that some other equivalent node will handle routing inside the grid. The sensor nodes in the sleeping state wake up after a sleeping time $T_s$ and go back to the discovery state. In GAF, load balancing is performed by means of periodic election of the leader (i.e., the active node that handle the routing inside the fixed grid). A rank-based election algorithm has been used to elect the leader. It is based on the remaining energy of sensor nodes inside the fixed square grid so as to extend the network lifetime In proportionally with network density. -In~\cite{ref132}, the author have designed a novel distributed heuristic, called Distributed Energy-efficient Scheduling for k-coverage (DESK), which ensures that the energy consumption among the sensors is balanced and the lifetime maximized while the coverage requirement is maintained. This heuristic works in rounds, requires only one-hop neighbor information, and each sensor decides its status (active or sleep) based on the perimeter coverage model from~\cite{ref133}. Figure~\ref{desk} shows the DESK network time line. +In~\cite{DESK}, the author have designed a novel distributed heuristic, called Distributed Energy-efficient Scheduling for k-coverage (DESK), which ensures that the energy consumption among the sensors is balanced and the lifetime maximized while the coverage requirement is maintained. This heuristic works in rounds, requires only one-hop neighbor information, and each sensor decides its status (active or sleep) based on the perimeter coverage model from~\cite{ref133}. Figure~\ref{desk} shows the DESK network time line. \begin{figure}[h!] \centering @@ -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{ref97} & \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{GAF} & \OK & & \OK & & & & \OK & & \OK & & & &\\ + +& \tiny C. Vu et al. (2006)~\cite{DESK} & \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.