update by Ali

[ThesisAli.git] / CHAPITRE_02.tex

diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex
index 195cc84c636c9b2a888fbb0cb67fec6083ce66f6..f20f9873b576e48a339a3514adb1ad8085dad224 100755 (executable)
--- a/CHAPITRE_02.tex
+++ b/CHAPITRE_02.tex
@@ -77,10 +77,10 @@ In a distributed algorithms, on the other hand, the decision process is localize
 \end{table}
 
 
 \end{table}
 
 

-

 In this dissertation, the sensing field is divided into smaller subregions using divide-and-conquer method. The division continues until the distance between each two sensors inside the subregion is 3 or 2 hops maximum. This division have made our protocols more scalable for the large networks, less energy consumption for communication, less processing power for decision, more reliable against network failure, and a longer lifetime. Our proposed protocols are distributed on the sensor nodes of the subregions. The protocols in each subregion work in independent and simultaneous way with the protocols in the other subregions. If the network disconnected in one subregion, it will not effect on the other subregions of the sensing field.  There is no a fixed sensor node in the subregion execute the optimization algorithm. Each period of the network lifetime, the sensor nodes in the subregion cooperate in order to select a sensor node according to a predefined priority metrics to execute the optimization algorithm. The local optimal schedule resulted from the optimization algorithm is applied within the subregion. The elected sensor node sends a packet to every sensor within the subregion to inform him to stay active or sleep during this period. Each optimization algorithm in a subregion provides locally optimal solution, so the solution for all the sensing field is near-optimal. 
 
 In this dissertation, the sensing field is divided into smaller subregions using divide-and-conquer method. The division continues until the distance between each two sensors inside the subregion is 3 or 2 hops maximum. This division have made our protocols more scalable for the large networks, less energy consumption for communication, less processing power for decision, more reliable against network failure, and a longer lifetime. Our proposed protocols are distributed on the sensor nodes of the subregions. The protocols in each subregion work in independent and simultaneous way with the protocols in the other subregions. If the network disconnected in one subregion, it will not effect on the other subregions of the sensing field.  There is no a fixed sensor node in the subregion execute the optimization algorithm. Each period of the network lifetime, the sensor nodes in the subregion cooperate in order to select a sensor node according to a predefined priority metrics to execute the optimization algorithm. The local optimal schedule resulted from the optimization algorithm is applied within the subregion. The elected sensor node sends a packet to every sensor within the subregion to inform him to stay active or sleep during this period. Each optimization algorithm in a subregion provides locally optimal solution, so the solution for all the sensing field is near-optimal. 
 

-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.
+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. In table~\ref{Table1:ch2}, the "SET K-COVER" characteristic refers to the maximum number of disjoint or non-disjoint sets of sensors such that each set cover can assure the coverage for the whole region. The k-coverage characteristic refers to that every point inside the monitored area is always covered by at least k active sensors.
+

 
 
 \section{Centralized Algorithms}
 
 
 \section{Centralized Algorithms}


@@ -126,8 +126,8 @@ Many distributed algorithms have been  developed to perform the scheduling so as
 X. Deng et al. \cite{ref133} formulate the area coverage problem as a decision problem, whose goal is to determine whether every point in the area of interest is monitored by at least k sensors. The 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. Thier solutions can be translated to distributed protocols to solve the coverage problem.
 
 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}. 
 X. Deng et al. \cite{ref133} formulate the area coverage problem as a decision problem, whose goal is to determine whether every point in the area of interest is monitored by at least k sensors. The 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. Thier solutions can be translated to distributed protocols to solve the coverage problem.
 
 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}. 

-Cho et al.~\cite{ref145} proposed a distributed node scheduling protocol, which can retain sensing coverage needed by applications and increase network lifetime via putting in sleep mode some redundant nodes. In this work, the effective sensing area (ESA) concept of a sensor node is used, which refers to the sensing area that is not overlapping with another sensor's sensing area. A sensor node and by computing its ESA can determine whether it will be active or sleep. The suggested  work permits to sensor nodes to be in sleep mode opportunistically whilst fulfill the needed sensing coverage. The authors in~\cite{ref146},  defined a maximum sensing coverage region problem (MSCR) in WSNs and then proposed a distributed algorithm to solve it. The maximum observed area fully covered by a minimum active sensors. In this work, the major property is to getting rid from the redundant sensors  in high-density WSNs and putting them in sleep mode, and choosing a smaller number of active sensors so as to be sure  that the full area is k-covered, and all events appeared in that area can be precisely and timely detected. This algorithm minimized the total energy consumption and increased the lifetime. 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.
-A graph theoretical framework for connectivity-based area coverage with configurable coverage granularity was proposed~\cite{ref149}. A new coverage criterion and scheduling approach is proposed based on cycle partition. This method is capable of build a sparse coverage set in distributed way by means of only connectivity information. This work considers only the communication range of the sensor is smaller two times the sensing range of sensor. Shibo et al.~\cite{ref137} have expressed the area 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. The authors in \cite{ref160}, designed an energy-efficient approach to area coverage problems by transforming the area coverage problem to the target coverage problem taking into account the  intersection points among disks of sensors nodes or between disk of sensor nodes and boundaries. They proposed two mechanisms for the converted target coverage problems to produce cover sets can cover the sensing
+Cho et al.~\cite{ref145} propose a distributed node scheduling protocol, which can retain sensing coverage needed by applications and increase network lifetime via putting in sleep mode some redundant nodes. In this work, the effective sensing area (ESA) concept of a sensor node is used, which refers to the sensing area that is not overlapping with another sensor's sensing area. A sensor node can determine whether it will be active or sleep by computing its ESA. The suggested  work permits to sensor nodes to be in sleep mode opportunistically whilst fulfill the needed sensing coverage. The authors in~\cite{ref146},  define a maximum sensing coverage region problem (MSCR) in WSNs and then propose a distributed algorithm to solve it. The maximum observed area fully covered by a minimum active sensors. In this work, the major property is to get rid of the redundant sensors  in high-density WSNs and putting them in sleep mode, and choosing a smaller number of active sensors so as to ensure the full area is k-covered, and all events appearing in that area can be precisely and timely detected. This algorithm minimizes the total energy consumption and increases the network lifetime. 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.
+A graph theoretical framework for connectivity-based area coverage with configurable coverage granularity was proposed~\cite{ref149}. A new coverage criterion and scheduling approach is proposed based on cycle partition. This method is capable of build a sparse coverage set in distributed way by means of only connectivity information. This work considers only the communication range of the sensor is smaller two times the sensing range of sensor. Shibo et al.~\cite{ref137} have expressed the area coverage problem as a  minimum  weight submodular set cover problem  and propose 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. The authors in \cite{ref160}, design an energy-efficient approach to area coverage problems by transforming the area coverage problem to the target coverage problem taking into account the  intersection points among disks of sensors nodes or between disk of sensor nodes and boundaries. They proposed two mechanisms for the converted target coverage problems to produce cover sets can cover the sensing

 field completely. Simulations results show that this approach can prolong the lifetime of the network compared with other works.
 
 The works presented in~\cite{ref134,ref135,ref136} focus on coverage-aware, distributed energy-efficient, and distributed clustering methods respectively, which aim at extending the network lifetime, while the coverage is ensured.
 field completely. Simulations results show that this approach can prolong the lifetime of the network compared with other works.
 
 The works presented in~\cite{ref134,ref135,ref136} focus on coverage-aware, distributed energy-efficient, and distributed clustering methods respectively, which aim at extending the network lifetime, while the coverage is ensured.


@@ -140,7 +140,7 @@ The works presented in~\cite{ref134,ref135,ref136} focus on coverage-aware, dist
 \subsection{GAF}
 \label{ch2:sec:03:1}
 
 \subsection{GAF}
 \label{ch2:sec:03:1}
 

-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.
+In \cite{GAF}, Xu et al. have developed an algorithm, called Geographical Adaptive Fidelity (GAF). It 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
 
 \begin{figure}[h!]
 \centering


@@ -149,7 +149,9 @@ In \cite{GAF}, Xu et al. have described an algorithm, called Geographical Adapti
 \label{gaf1}
 \end{figure}
 
 \label{gaf1}
 \end{figure}
 

-The fixed grid is defined where, each two adjacent grids, for example, A and B in figure\ref{gaf1}, all the 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 grid such as, B and C in figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$ so as to satisfy the definition of fixed square grid. 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}
 r^2 + \left(2r \right)^2 \leq R_c^2 
 
 \begin{eqnarray}
 r^2 + \left(2r \right)^2 \leq R_c^2 


@@ -159,7 +161,8 @@ or
 r \leq \dfrac{R_c}{\sqrt{5}} 
 \end{eqnarray}
 
 r \leq \dfrac{R_c}{\sqrt{5}} 
 \end{eqnarray}
 

-The sensor nodes in GAF can be in one of the three states: active, sleep, or discovery. Figure~\ref{gaf2} shows the state transition diagram. Each sensor node is initiated with discovery state. In discovery state, the radio of each sensor node is turned on after that the discovery messages are exchanged among the sensor nodes so as to discover the other nodes within the same grid. The discovery message consisted of four fields like, node id, grid id, estimated node active time (enat), and node state. The node uses its location and grid size to determine the grid id.   
+The sensor nodes in GAF can be in one of the three states: active, sleep, or discovery. Figure~\ref{gaf2} shows the state transition diagram. Each sensor node is initiated with discovery state. 
+In discovery state, the radio of each sensor node is turned on. Thereafter, the discovery messages are exchanged among the sensor nodes within the same grid. The discovery message consists of four fields, node id, grid id, estimated node active time (enat), and node state. The node uses its location and grid size to determine the grid id.   

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


@@ -168,12 +171,12 @@ The sensor nodes in GAF can be in one of the three states: active, sleep, or dis
 \label{gaf2}
 \end{figure}
 
 \label{gaf2}
 \end{figure}
 

-The sensor node sets a timer to $T_d$ seconds after entering in the discovery state. As soon as the timer fires, the sensor node broadcast its discovery message and enters the active state. The active sensor node sets a timeout value $T_a$ to define how long it can stay in the 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.
+The sensor node sets a timer to $T_d$ seconds after entering in the discovery state. As soon as the timer fires, the sensor node broadcasts its discovery message and enters the active state. The active sensor node sets a timeout value $T_a$ to define how long it can stay in the 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.

 
 \subsection{DESK}
 \label{ch2:sec:03:2}
 
 
 \subsection{DESK}
 \label{ch2:sec:03:2}
 

-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.
+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.

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


@@ -182,21 +185,21 @@ In~\cite{DESK}, the author have designed a novel distributed heuristic, called D
 \label{desk}
 \end{figure}
 
 \label{desk}
 \end{figure}
 

-DESK works into rounds manner. The network lifetime 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 wake up 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 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
+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

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

-  \dfrac{\eta}{n_i^\alpha l(e_i,r_i)^\beta} * W + z & \mbox{If $e_i \geq e_threshold$} \\
+  \dfrac{\eta}{n_i^\alpha l(e_i,r_i)^\beta} * W + z & \mbox{If $e_i \geq e_{threshold}$} \\

   W & \mbox{Otherwise.}\\
 \end{array} \right.
 %\label{eq12} 
 \notag
 \end{equation} 
 
   W & \mbox{Otherwise.}\\
 \end{array} \right.
 %\label{eq12} 
 \notag
 \end{equation} 
 

-Where: $\alpha, \beta,$ and $\eta$ are constants, 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 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$.

 
 

-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 it in 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
+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.
 
 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.