X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/1e919d0378443dea59144e8027dff818b86105cf..7c91ad0ef9e5b3ba9e8d84cfed55bc7692a8e359:/CHAPITRE_02.tex?ds=inline diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex index 195cc84..c3082a7 100755 --- 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} - 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} @@ -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}. -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. @@ -140,7 +140,7 @@ The works presented in~\cite{ref134,ref135,ref136} focus on coverage-aware, dist \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 @@ -149,7 +149,12 @@ In \cite{GAF}, Xu et al. have described an algorithm, called Geographical Adapti \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, + + +\begin{eqnarray} +Distance(2,5) \leq R_c +\end{eqnarray} \begin{eqnarray} r^2 + \left(2r \right)^2 \leq R_c^2 @@ -159,7 +164,8 @@ or 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 @@ -168,12 +174,27 @@ The sensor nodes in GAF can be in one of the three states: active, sleep, or dis \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} -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 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 @@ -182,23 +203,25 @@ In~\cite{DESK}, the author have designed a novel distributed heuristic, called D \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 +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{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} -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$. +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 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 -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. @@ -209,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] - & & \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} @@ -277,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 & &\\ -\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 & &\\ @@ -301,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 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} @@ -317,10 +340,29 @@ 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. -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. -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 +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. +Many coverage algorithms for maintaining the coverage and improving the network lifetime in WSNs were proposed. On one hand, the full centralized coverage algorithms provide optimal or near optimal solution with low computation power but they deplete the battery power due to the communication overhead, as well as they are not scalable for large size networks. On the other hand, the distributed coverage algorithms provide a lower quality solution in comparison with centralized approaches and consume more power for computation but they are reliable, scalable, and provide low communication overhead in WSNs. Whatever the case, this would result in a shorter lifetime coverage in WSNs As shown in table \ref{Table0:ch2}, each of the two coverage approaches has advantages and disadvantages. Therefore, each approach can be used based on the application requirements. We conclude from this chapter that it is desirable to introduce a hybrid approach that take into account the advantages of both centralized and distributed coverage approaches. This hybrid approaches can provide a good quality coverage and prolong the network lifetime. + + + + + + + + + + + + + + + + + + +%Many coverage algorithms for maintaining the coverage and improving the network lifetime in WSNs were proposed. On one hand, the centralized coverage algorithms provide optimal or near optimal solution with low computation power but they deplete the battery power due to the communication overhead, as well as they are not scalable for large size networks. On the other hand, the distributed coverage algorithms provide a lower quality solution in comparison with centralized approaches and consume more power for computation but they are reliable, scalable, and provide low communication overhead on the WSNs. + %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 % Several centralized approaches have been demonstrated, where they are concentrated on modeling the coverage problem and provide the maximum cover set so as to extend the network lifetime. The proposed algorithms are executed in a central node and based on global information. The central node transmits the resulted schedule to other nodes in the network. Even if the centralized algorithms have been produced optimal or near optimal solutions, It seems to be difficult and unpractical to apply the full centralized approaches in WSNs. On the other hand, many distributed algorithms have been described. These approaches seem to be more realistic to be used in WSNs from point of view of designer, but they can not assure optimal or near optimal solutions so as to extend the network lifetime as long time as possible.