Update by Ali

[ThesisAli.git] / CHAPITRE_02.tex

diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex
index f20f9873b576e48a339a3514adb1ad8085dad224..1534b6a03b3f3bd655abb2891155a4a14df1ff1a 100755 (executable)
--- a/CHAPITRE_02.tex
+++ b/CHAPITRE_02.tex
@@ -151,7 +151,10 @@ In \cite{GAF}, Xu et al. have developed an algorithm, called Geographical Adapti
 
 For two adjacent grids, (for example, A and B in figure\ref{gaf1}) all sensor nodes inside A can communicate with sensor nodes inside B and vice versa. Therefore, all the sensor nodes are equivalent from the point of view the routing. The size of the fixed grid is based on the radio communication range $R_c$. It is supposed that the fixed grid is square with $r$ units on a side as shown in figure~\ref{gaf1}. The distance between the farthest two possible sensor nodes in two adjacent grids such as, B and C in figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$. For instance, the sensor node \textbf{2} of grid B can communicate with the sensor node \textbf{5} of grid C So, 
 
 
 For two adjacent grids, (for example, A and B in figure\ref{gaf1}) all sensor nodes inside A can communicate with sensor nodes inside B and vice versa. Therefore, all the sensor nodes are equivalent from the point of view the routing. The size of the fixed grid is based on the radio communication range $R_c$. It is supposed that the fixed grid is square with $r$ units on a side as shown in figure~\ref{gaf1}. The distance between the farthest two possible sensor nodes in two adjacent grids such as, B and C in figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$. For instance, the sensor node \textbf{2} of grid B can communicate with the sensor node \textbf{5} of grid C So, 
 

-distance(2,5)  $\leq$  $R_c$
+
+\begin{eqnarray}
+Distance(2,5)  \leq  R_c 
+\end{eqnarray}

 
 \begin{eqnarray}
 r^2 + \left(2r \right)^2 \leq R_c^2 
 
 \begin{eqnarray}
 r^2 + \left(2r \right)^2 \leq R_c^2 


@@ -176,7 +179,22 @@ The sensor node sets a timer to $T_d$ seconds after entering in the discovery st
 \subsection{DESK}
 \label{ch2:sec:03:2}
 
 \subsection{DESK}
 \label{ch2:sec:03:2}
 

-In~\cite{DESK}, the author design 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 design 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 satisfied. 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}. 
+
+DESK is based on the result from \cite{ref133}. In \cite{ref133}, the whole area is k-covered if and only if the perimeter of sensing regions of all sensors are k-covered. The coverage level of perimeter of a sensor $s_i$ is determined by calculating the angle corresponding to the arc that each of its neighbors covers its perimeter. Figure~\ref{figp}~(a) illuminates such arcs whilst figure~\ref{figp}~(b) shows the angles corresponding with those arcs, which were posted into the range [0,2$ \pi $]. According to figure~\ref{figp}~(b), the coverage level of sensor $s_i$ can be calculated via traversing the range from 0 to  2$ \pi $.
+
+
+\begin{figure}[h!]
+  \centering
+  \begin{tabular}{@{}cr@{}}
+    \includegraphics[scale=0.6]{Figures/ch2/P2.jpg} & \raisebox{4cm}{(a)} \\  
+    \includegraphics[scale=0.6]{Figures/ch2/P1.jpg} & \raisebox{4cm}{(b)}
+  \end{tabular}
+  \caption{Determining the perimeter-coverage of $s_i$’s perimeter.}
+  \label{figp}
+\end{figure} 
+
+

 
 \begin{figure}[h!]
 \centering
 
 \begin{figure}[h!]
 \centering


@@ -185,7 +203,7 @@ In~\cite{DESK}, the author design a novel distributed heuristic, called Distribu
 \label{desk}
 \end{figure}
 
 \label{desk}
 \end{figure}
 

-DESK works into rounds manner. The network lifetime is divided into R rounds. Each round consists of two phases: decision phase and sensing phase. The length of round is dRound that means each sensor node executes this algorithm every dRound unit of time. The decision phase at the starting of each round should be taken within W unit of time, where $W<< dRound$ as shown in figure~\ref{desk}. All the sensor nodes should be temporarily awakened in the decision phase so as to decide its status. Every sensor node $s_i$ decides its status to be active or sleep after $w_i$ of waiting time. The waiting time $w_i$ is dynamic and it can be changed at any time based on the status of its sensor neighbors, the remaining energy $e_i$ of $s_i$, and its contribution $c_i$ in the coverage level of the network, where $c_i$ is defined as the number of the neighbors $n_i$ who need $s_i$ to be active. The waiting time has been defined as follow
+Figure~\ref{desk} shows the DESK network time line. DESK works into rounds fashion. The network lifetime is divided into R rounds. Each round consists of two phases: decision phase and sensing phase. The length of round is dRound that means each sensor node executes this algorithm every dRound unit of time. The decision phase at the starting of each round should be taken within W unit of time, where $W<< dRound$ as shown in figure~\ref{desk}. All the sensor nodes should be temporarily awakened in the decision phase so as to decide its status. Every sensor node $s_i$ decides its status to be active or sleep after $w_i$ of waiting time. The waiting time $w_i$ is dynamic and it can be changed at any time based on the status of its sensor neighbors, the remaining energy $e_i$ of $s_i$, and its contribution $c_i$ in the coverage level of the network, where $c_i$ is defined as the number of the neighbors $n_i$ who need $s_i$ to be active. The waiting time has been defined as follow

 
 \begin{equation}
 w_{i} = \left \{ 
 
 \begin{equation}
 w_{i} = \left \{ 


@@ -197,11 +215,13 @@ w_{i} = \left \{
 \notag
 \end{equation} 
 
 \notag
 \end{equation} 
 

-Where $\alpha, \beta,$ and $\eta$ are constant, z is a random number between [0; d], where d is a time slot, to avoid the case where two sensors having the same $w_i$ to be active at the same time. $l(e_i, r_i)$ is the function computing the lifetime of sensor $s_i$ in terms of its current remaining energy $e_i$ and its sensing range $r_i$.
+Where $\alpha, \beta,$ and $\eta$ are constant, z is a random number between [0; d], where d is a time slot, to avoid the case where two sensors having the same $w_i$ to be active at the same time. $l(e_i, r_i)$ is the function computing the lifetime of sensor $s_i$ in terms of its current remaining energy $e_i$ and its sensing range $r_i$. 
+DESK uses two types of messages, mACTIVATE message by which a sensor informs others that it becomes active, and mASK2SLEEP by which a sensor suggests a neighbor to go to sleep due to its uselessness. The concept of uselessness or a redundant neighbor refers to one that does not contribute to the perimeter coverage of the considered sensor.   This is mean the segment of the perimeter of the considered sensor overlapping with that neighbor is already k-covered by already active sensors.
+

 
 

-Typically, the algorithm works as follows: all the sensor nodes collect the information (coordinates, current residual energy, and sensing range) from the one-hop neighbors and store information into a list L (in the increasing order) by executing the perimeter coverage model. Each sensor node set its timer to $w_i$ and initially it is proposed that all of its neighbors need it to join the
-network. When the sensor node $s_j$ joins the network,  it broadcasts a mACTIVATE message to inform all of its 1-hop neighbors about its status change. Its neighbors execute the perimeter coverage model to recalculate its coverage level. If it finds any neighbor u that is useless in covering its perimeter, i.e., the perimeter that u covers was covered by other active neighbors, it will send mASK2SLEEP message to that sensor. When the sensor node receives  mASK2SLEEP message, it updates its counter $n_i$, contribution $c_i$ and recalculate waiting time $w_i$. It then
-check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e., it receives mASK2SLEEP message from all of its neighbors), then it will send message mGOSLEEP to all of its neighbors telling them that it is about to go to sleep, and set a timer $R_i$ for waking up in next round and at last go to sleep. If the sensor node receives  mGOSLEEP message, it removes the neighbor sending that message out of its list L.
+
+Typically, the algorithm works as follows. At the beginning of each round, no sensors are active. All sensors are in listening mode, i.e. all wait for the time to make a decision while still doing sensing job. All the sensor nodes collect the information (coordinates, current residual energy, and sensing range) from the one-hop neighbors. It stores this information into a list L in the increasing order of the angle $\alpha $ . Each sensor node set its timer to $w_i$ and initially it is proposed that all of its neighbors need it to join the network. When the sensor node $s_j$ joins the network,  it broadcasts a mACTIVATE message to inform all of its 1-hop neighbors about its status change. Its neighbors execute the perimeter coverage model to recalculate its coverage level. If it finds any neighbor u that is useless in covering its perimeter, i.e., the perimeter that u covers was covered by other active neighbors, it will send mASK2SLEEP message to that sensor. When the sensor node receives  mASK2SLEEP message, it updates its counter $n_i$, contribution $c_i$ to coverage level, and recalculate waiting time $w_i$. It then
+check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e., it receives mASK2SLEEP message from all of its neighbors), then it will send message mGOSLEEP to all of its neighbors telling them that it is about to go to sleep, and set a timer $R_i$ for waking up in next round and at last go to sleep. If the sensor node receives  mGOSLEEP message, it removes the neighbor sending that message out of its list L. All the sensors have to decide its status in the decision phase. After that, the active sensors perform the sensing task during the sensing phase.

 
 
 
 
 
 


@@ -212,7 +232,7 @@ 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]
 \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 SET K-COVER } & \mcrot{1}{l}{50}{\footnotesize Work in Rounds}  & \mcrot{1}{l}{50}{\footnotesize Adjustable Radius}  \\
+        \multicolumn{2}{c}{\footnotesize Coverage Approach} & \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}
 
 
         \cmidrule[1pt]{2-14}
 
 


@@ -280,7 +300,7 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
 
 & \tiny  V. T. Quang and T. Miyoshi (2008)~\cite{ref146}  & \OK &   & \OK &  & \OK &  & \OK &  & \OK &  & \OK &  &\\
 
 
 & \tiny  V. T. Quang and T. Miyoshi (2008)~\cite{ref146}  & \OK &   & \OK &  & \OK &  & \OK &  & \OK &  & \OK &  &\\
 

-\rot{\rlap{Some Proposed Coverage Protocols in previous literatures}} 
+%\rot{\rlap{Some Proposed Coverage Protocols in previous literatures}} 

 
 & \tiny  D. Dong et al. (2012)~\cite{ref149}  & \OK &  & \OK &  &  &  & \OK &  & \OK &  & \OK &  &\\
 
 
 & \tiny  D. Dong et al. (2012)~\cite{ref149}  & \OK &  & \OK &  &  &  & \OK &  & \OK &  & \OK &  &\\
 


@@ -304,7 +324,7 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
 
 &\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 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}}  &    &  \\
+&\textbf{\textcolor{red}{ \tiny PeCO Protocol (2015)}}                  &  \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}}   &   &   & \textbf{\textcolor{red}{\OK}}  & \textbf{\textcolor{red}{\OK}}   &   &  &   &\textbf{\textcolor{red}{\OK}}  &    &  \\

 
         \cmidrule[1pt]{2-14}
     \end{tabular}
 
         \cmidrule[1pt]{2-14}
     \end{tabular}


@@ -320,9 +340,10 @@ 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}
 
 \section{Conclusion}
 \label{ch2:sec:05}

-This chapter has been described some coverage problems proposed in the literature, and their assumptions and proposed solutions.
-The coverage problem has been considered an essential requirement for many applications in WSNs because the better
-coverage of an area of interest provides better sensing measurements of the physical phenomenon. So, many extensive researches have been focused on that problem. These researches have aimed at designing mechanisms that efficiently manage or schedule the sensors after deployment, since sensor nodes have a limited battery life.
+This chapter describes some coverage proposed problems in the literature, with their assumptions and proposed solutions.
+The coverage problem has been considered an essential requirement for many applications in WSNs because the better coverage of an area of interest provides better sensing measurements of the physical phenomenon. Therefore, many extensive researches have been focused on that problem. These researches have aimed at designing mechanisms that efficiently manage or schedule the sensors after deployment, since sensor nodes have a limited battery life.
+
+

 In spite of many energy-efficient protocols for maintaining the coverage and improving the network lifetime in WSNs were proposed, none of them ensure the coverage for the sensing field with optimal minimum number of active sensor nodes, and for a long time as possible. In full centralized algorithms, the optimal solutions can be given by using optimization approaches, but in the same time, a high energy is consumed for the execution time of the algorithm and the communications among the sensors in the sensing field. Therefore, the  full centralized approaches are not a good candidate to be used especially in large WSNs. Whilst, a fully distributed algorithms can not give optimal solutions because these algorithms use only local information of the neighboring sensors, but in the same time, the energy consumption during the communications and executing the algorithm is highly lower. Whatever the case, this would result in a shorter lifetime coverage in WSNs
 
 
 In spite of many energy-efficient protocols for maintaining the coverage and improving the network lifetime in WSNs were proposed, none of them ensure the coverage for the sensing field with optimal minimum number of active sensor nodes, and for a long time as possible. In full centralized algorithms, the optimal solutions can be given by using optimization approaches, but in the same time, a high energy is consumed for the execution time of the algorithm and the communications among the sensors in the sensing field. Therefore, the  full centralized approaches are not a good candidate to be used especially in large WSNs. Whilst, a fully distributed algorithms can not give optimal solutions because these algorithms use only local information of the neighboring sensors, but in the same time, the energy consumption during the communications and executing the algorithm is highly lower. Whatever the case, this would result in a shorter lifetime coverage in WSNs