\emph{ \begin{center} \Large Distributed Coverage Optimization Techniques for Improving
Lifetime of Wireless Sensor Networks \end{center}}
%\emph{ \begin{center} \large By \end{center}}
-\emph{ \begin{center} \large Ali Kadhum Idrees \\ The University of Franche-Comt\'e, 2015 \end{center}}
+\emph{ \begin{center} \large Ali Kadhum Idrees \\ University of Franche-Comt\'e, 2015 \end{center}}
%\emph{ \begin{center} \large The University of Franche-Comt\'e, 2015 \end{center}}
\emph{ \begin{center} \large Supervisors: Raphaël Couturier, Karine Deschinkel, and Michel Salomon \end{center}}
-Wireless sensor networks (WSNs) have recently received a great deal of research attention due to their wide range of potential applications. in many different fields. Many important characteristics are provided by the WSNs and the sensors that make them different from other wireless ad-hoc networks, and very promising in a wide range of applications. On the other hand, these characteristics are imposed lots of limitations on the WSNs that would lead to several challenges in the network. These challenges might include coverage, topology control, routing, data fusion, security, and many others. One of the main research challenges faced in wireless sensor networks is to preserve continuously and effectively the coverage of an area of interest to be monitored, while simultaneously preventing as much as possible a network failure due to battery-depleted nodes.
+Wireless sensor networks (WSNs) have recently received a great deal of research attention due to their wide range of potential applications. Many important characteristics are provided by the WSNs which make them different from other wireless ad-hoc networks. These characteristics are imposed lots of limitations on the WSNs that would lead to several challenges in the network. These challenges might include coverage, topology control, routing, data fusion, security, and many others. One of the main research challenges faced in wireless sensor networks is to preserve continuously and effectively the coverage of an area of interest to be monitored, while simultaneously preventing as much as possible a network failure due to battery-depleted nodes.
-In this dissertation, we highly focus on the area coverage problem, energy-efficiency is also the foremost requirement. We have considered a distributed optimization protocols with the ultimate objective of prolonging the network lifetime. The proposed distributed optimization protocols ( including algorithms, models, and solving integer programs) should be energy-efficient protocols. To address
+In this dissertation, we highly focus on the area coverage problem, energy-efficiency is also the foremost requirement. We have considered distributed optimization protocols with the ultimate objective of prolonging the network lifetime. The proposed distributed optimization protocols (including algorithms, models, and solving integer programs) should be energy-efficient protocols. To address
this problem, this dissertation proposes two-step approaches. Firstly, the sensing field is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of our proposed distributed optimization protocols is distributed and applied on the
-sensor nodes in each subregion so as to optimize the coverage and the lifetime performances. In this dissertation, three coverage optimization protocols are proposed. These protocols combine two efficient techniques: leader election for each subregion, followed by an optimization-based planning of activity scheduling decisions for each subregion.
+sensor nodes in each subregion so as to optimize the coverage and the lifetime performances. In this dissertation, three coverage optimization protocols are proposed. These protocols combine two efficient techniques: leader election for each subregion, followed by an optimization-based planning of sensor activity scheduling decisions for each subregion.
-First, we propose a Distributed Lifetime Coverage Optimization (DILCO) protocol in WSNs. In this protocol, the lifetime is divided into periods. Each period consists of 4 phases: information exchange, leader election, decision, and sensing. The decision process is
+First, we propose a protocol called Distributed Lifetime Coverage Optimization (DILCO). In this protocol, the lifetime is divided into periods. Each period consists of 4 phases: information exchange, leader election, decision, and sensing. The decision process is
carried out by a leader node, which solves an integer program in order to provide only one cover set of active sensor nodes to ensure coverage during the sensing phase of the current period.
- Then we move to address the problem of a multiround optimization of the area coverage problem in WSNs. The Multiround Distributed Lifetime Coverage Optimization (MuDiLCO) protocol is suggested so as to study the possibility of providing multiple cover sets of sensors for the sensing phase. MuDiLCO protocol also works in periods
-during which sets of sensor nodes are scheduled to remain active for a number of rounds during the sensing phase, to ensure coverage so as to maximize the
-lifetime of WSN. The decision process is carried out by a leader node, which solves an integer program to produce the best representative sets to be used during the rounds of the sensing phase.
+ Then we address the problem of a multiround optimization of the area coverage problem in WSNs. The Multiround Distributed Lifetime Coverage Optimization (MuDiLCO) protocol is suggested so as to study the possibility of providing multiple cover sets of sensors for the sensing phase. MuDiLCO protocol also works in periods
+during which sets of sensor nodes are scheduled to remain active for a number of rounds during the sensing phase, to ensure coverage so as to maximize the lifetime of WSN. The decision process is still carried out by a leader node, which solves an integer program to produce the best representative sets to be used during the rounds of the sensing phase.
-Last but not least, we propose a Perimeter-based Coverage Optimization (PeCO) protocol to maintain the coverage and improve the network lifetime in WSNs. It is a hybrid of centralized and distributed methods, where it is also distributed among sensor nodes in each subregion.The novelty of our approach lies essentially in the formulation of a new
-mathematical optimization model based on the perimeter coverage level to schedule
-sensors' activities. The PeCO protocol resolves a new integer program coverage model by the leader during the decision phase so as to provide only one cover set of sensors for the sensing phase.
+Last but not least, we propose a Perimeter-based Coverage Optimization (PeCO) protocol which is also distributed among sensor nodes in each subregion.The novelty of our approach lies essentially in the formulation of a new
+mathematical optimization model based on the perimeter coverage level to schedule sensors' activities. A new integer program coverage model is solved by the leader during the decision phase so as to provide only one cover set of sensors for the sensing phase.
Extensive simulations are conducted using the discrete event simulator OMNET++ to validate the efficiency of each of our proposed protocols. We refer to the characteristics of a Medusa II sensor for the energy consumption and the time computation. In comparison with two other existing methods, our protocols are able to increase
-the WSN lifetime and provides improved coverage performance.
+the WSN lifetime and provide improved coverage performance.
\textbf{KEY WORDS:} Wireless Networks, Wireless Sensor Networks, Area Coverage, Network Lifetime, Optimization, Scheduling, Distributed Algorithms, Centralized Algorithms, Robustness, Connectivity, Parallel Algorithms, Energy-efficiency, Heterogeneous Energy Network, Homogeneous Network.
In a distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and only informations 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 the energy consumption for computation is increased. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give an optimal (or near-optimal) solution based only on local informations. Moreover, a recent study conducted in \cite{ref226} concludes that there is a threshold in terms of network size to switch from a distributed to a centralized algorithm. Table~\ref{Table0:ch2} shows a comparison between centralized coverage algorithms and distributed coverage algorithms.
-\begin{table}[h]
+\begin{table}[h!]
\caption{Centralized Coverage Algorithms vs Distributed Coverage Algorithms}
\begin{center}
\begin{tabular}{ |p{3cm}|p{5cm}|p{5cm}|}
\textbf{\begin{center} Characteristics \end{center}} & \textbf{\begin{center} Centralized Coverage Algorithms \end{center}} & \textbf{\begin{center} Distributed Coverage Algorithms \end{center}}\\ \hline
-\textbf{\begin{center} Computation \end{center}} & Require low processing power where the algorithm is executed only in one elected node. & Require large processing power due to execution the algorithm in every node in WSN. \\ \hline
+\textbf{\begin{center} Computation \end{center}} & Require low processing power where the algorithm is executed only in one node. & Require large processing power due to executing the algorithm in every node in WSN. \\ \hline
\textbf{\begin{center} Communication \end{center}} & Sensor nodes communicate directly with the base station, therefore, they require low-power consumption for communication. & Sensor nodes require high power consumption for communication because of the frequent exchange of hello packets. \\ \hline
\textbf{\begin{center} Energy Consumption \end{center}} & Energy consumption is large especially when the network size and/or density increase. & Energy consumption is low because they have lower communication cost. \\ \hline
-\textbf{\begin{center} Scalability \end{center}} & Scalable only with dividing the sensing field into smaller subregions. & More scalable for large networks. \\ \hline
+\textbf{\begin{center} Scalability \end{center}} & Not scalable, but they can overcome this problem by dividing the sensing field into smaller subregions. & More scalable for large networks. \\ \hline
\textbf{\begin{center} Reliability \end{center}} & Less robust against sensor failure. & More robust against sensor failure. \\ \hline
\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 two sensors inside the subregion is 3 or 2 hops maximum. This division makes our protocols more scalable for large networks, less energy consumer for communication, less energy consumption for processing, and more reliable against network failure. 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 is disconnected in one subregion, it will not affect the other subregions of the sensing field. There is no fixed sensor node in the subregion for executing the optimization algorithm. Each period of the network lifetime, the sensor nodes in the subregion cooperate in order to select a sensor node to execute the optimization algorithm according to predefined priority metrics. The resulting local optimal schedule from 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 an optimal solution, so the solution for the whole 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 two sensors inside the subregion is 3 or 2 hops maximum. This division makes our protocols more scalable for large networks, less energy consumer for communication and processing, and more reliable against network failure. 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 is disconnected in one subregion, it will not affect the other subregions of the sensing field. There is no fixed sensor node in the subregion for executing the optimization algorithm. Each period of the network lifetime, the sensor nodes in the subregion cooperate in order to select a sensor node to execute the optimization algorithm according to predefined priority metrics. The resulting local optimal schedule from 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 an optimal solution, so the solution for the whole sensing field is near-optimal.
Several algorithms to maintain the coverage and maximize the network lifetime were proposed in~\cite{ref113,ref101,ref103,ref105}.
Table \ref{x11} summarizes the main characteristics of some coverage approaches in previous literatures.
The major idea of most centralized algorithms is to divide/organize the sensors into a suitable number of cover sets, where each set completely covers an interest region and to activate these cover sets successively. The centralized algorithms always provide optimal or near-optimal solution since the algorithm has a global view of the whole network. Energy-efficient centralized approaches differ according to several criteria \cite{ref113}, such as the coverage objective (target coverage or area coverage), the node deployment method (random or deterministic), and the heterogeneity of sensor nodes (common sensing range, common battery lifetime).
The first algorithms proposed in the literature consider that the cover sets are disjoint: a sensor node appears in exactly one of the generated cover sets~\cite{ref114,ref115,ref116}. For instance, Slijepcevic and Potkonjak \cite{ref116} propose an algorithm, which allocates sensor nodes in mutually independent sets to monitor an area divided into several fields. Their algorithm builds a cover set by including in priority the sensor nodes which cover critical fields, that is to say, fields that are covered by the smallest number of sensors. The time complexity of their heuristic is $O(n^2)$ where $n$ is the number of sensors. M. Cardei et al.~\cite{ref227}, suggest a graph coloring technique to achieve energy savings by organizing the sensor nodes into a maximum number of disjoint dominating sets, which are activated successively. They have defined the maximum disjoint dominating sets problem and they have produced a heuristic that computes the disjoint cover sets so as to monitor the area of interest. The dominating sets do not guarantee the coverage of the whole region of interest. Abrams et al.~\cite{ref114} design three approximation algorithms for a variation of the set k-cover problem, where the objective is to partition the sensors into covers such that the number of covers that include an area, summed over all areas, is maximized.
-Their work builds upon previous work in~\cite{ref116} and the generated cover sets do not provide complete coverage of the monitoring zone.
+Their work is built upon previous work in~\cite{ref116} and the generated cover sets do not provide complete coverage of the monitoring zone.
-The authors in~\cite{ref115} propose a heuristic to compute the Disjoint Set Covers (DSC). In order to compute the maximum number of covers, they first transform DSC computation into a maximum-flow problem, which is then formulated as a Mixed Integer Programming problem (MIP). Based on the solution of the MIP, they design a heuristic to compute the final number of covers. The results show a slight performance improvement in terms of the number of produced DSC in comparison to~\cite{ref116}, but it incurs higher execution time due to the complexity of the mixed integer programming solving. Zorbas et al. \cite{ref228} present B\{GOP\}, a centralized target coverage algorithm introducing sensor candidate categorization depending on their coverage status and the notion of critical target to call targets that are associated with a small number of sensors. The total running time of their heuristic is $0(m n^2)$, where
+The authors in~\cite{ref115} propose a heuristic to compute the Disjoint Set Covers (DSC). In order to compute the maximum number of covers, they first transform DSC into a maximum-flow problem, which is then formulated as a Mixed Integer Programming problem (MIP). Based on the solution of the MIP, they design a heuristic to compute the final number of covers. The results show a slight performance improvement in terms of the number of produced DSC in comparison to~\cite{ref116}, but it incurs higher execution time due to the complexity of the mixed integer programming solving. Zorbas et al. \cite{ref228} present B\{GOP\}, a centralized target coverage algorithm introducing sensor candidate categorization depending on their coverage status and the notion of critical target to call targets that are associated with a small number of sensors. The total running time of their heuristic is $0(m n^2)$, where
$n$ is the number of sensors and $m$ the number of targets. Compared to algorithm's results of Slijepcevic and Potkonjak \cite{ref116}, their heuristic produces more cover sets with a slight growth rate in execution time. L. Liu et al.~\cite{ref150} formulate the maximum disjoint sets for maintaining target coverage and connectivity problem in WSN. They propose a graph theoretical framework to study the joint problem of connectivity and coverage in a WSN with random deployment of nodes with no restrictions on the sensing and communication ranges of nodes. They propose heuristic algorithms to find the suitable number of nodes to guarantee connectivity and coverage while maximizing network lifetime.
%This work did not take into account the sensor node failure, which is an unpredictable event because the two solutions are full centralized algorithms.
Y. Li et al.~\cite{ref142} present a framework with heuristic strategies to solve the area coverage problem. The framework converts any complete coverage problem to a partial coverage one with any coverage ratio. They execute a complete coverage algorithm to find full coverage sets with virtual radii and then transform the coverage sets to a partial coverage sets by adjusting sensing radii. This framework has four strategies, two of them are designed for network, where the sensors have fixed sensing range and the other two are for network, where the sensors have adjustable sensing range. The properties of the algorithms can be maintained by this framework and the transformation process has a low execution time. The simulation results validate the efficiency of the four proposed strategies. More recently, Deschinkel and Hakem \cite{ref229} introduce a near-optimal heuristic algorithm for solving the target coverage problem in WSN. The sensor nodes are organized into disjoint cover sets, each capable of monitoring all the targets of the region of interest. %Those covers sets are scheduled periodically.
lifetime increases compared with related work~\cite{ref115}. The authors in~\cite{ref148}, address the problem of minimum cost area coverage in which full coverage is performed by using the minimum number of sensors for an arbitrary geometric shape region. A geometric solution to the minimum cost coverage problem under a deterministic deployment is proposed. The probabilistic coverage solution which provides a relationship between the probability of coverage and the number of randomly deployed sensors in an arbitrarily-shaped region is suggested.
%The authors explained that with a random deployment about seven times more nodes are required to supply full coverage compared to deterministic deployment.
The work in~\cite{ref144} address the area coverage problem by proposing a Geometrically based Activity Scheduling scheme, named GAS, to fully cover the area of interest in WSNs. The authors deal with a small area, called target area coverage, which can be monitored by a single sensor instead of area coverage, which focuses on a large area that should be monitored by many sensors cooperatively. They explain that GAS is capable to monitor the target area by using the fewest number of sensors and it can produce as many cover sets as possible. A novel area coverage method to divide the sensors called Node Coverage Grouping (NCG) is suggested~\cite{ref147}. The sensors in the connectivity group are within sensing range of each other and the data collected by those in the same group are supposed to be similar. They prove that dividing N sensors via NCG into connectivity groups is an NP-hard problem. So, a heuristic algorithm of NCG with time complexity of $O(n^3)$ is proposed.
-For some applications, such as monitoring an ecosystem with extremely diversified environment, it might be premature assumption that sensors near to each other sense similar data. The problem of k-coverage over the area of interest in WSNs is addressed in~\cite{ref152}. It is mathematically formulated and the spatial sensor density for full k-coverage is determined. The relation between the communication range and the sensing range is constructed by this work to retain the k-coverage and connectivity in WSN. After that, four configuration protocols are proposed for treating the k-coverage in WSNs. Simulation results show that their protocols outperform an existing distributed k-coverage configuration protocol. The work presented in~\cite{ref151} solves the area coverage and connectivity problem in sensor networks in an integrated way. The network lifetime is divided into a fixed number of rounds. A coverage bitmap of sensors of the domain is generated in each round and based on this bitmap, it is decided which sensors stay active or go to sleep. They check the connection of the graph via laplacian of the adjacency graph of active sensors in each round. %The generation of coverage bitmap by using Minkowski technique, the network is able to providing the desired ratio of coverage.
+For some applications, such as monitoring an ecosystem with extremely diversified environment, it might be a premature assumption that sensors near to each other sense similar data. The problem of k-coverage over the area of interest in WSNs is addressed in~\cite{ref152}. It is mathematically formulated and the spatial sensor density for full k-coverage is determined. The relation between the communication range and the sensing range is constructed by this work to retain the k-coverage and connectivity in WSN. After that, four configuration protocols are proposed for treating the k-coverage in WSNs. Simulation results show that their protocols outperform an existing distributed k-coverage configuration protocol. The work presented in~\cite{ref151} solves the area coverage and connectivity problem in sensor networks in an integrated way. The network lifetime is divided into a fixed number of rounds. A coverage bitmap of sensors of the domain is generated in each round and based on this bitmap, it is decided which sensors stay active or go to sleep. They check the connection of the graph via laplacian of the adjacency graph of active sensors in each round. %The generation of coverage bitmap by using Minkowski technique, the network is able to providing the desired ratio of coverage.
They define the connected coverage problem as an optimization problem and a centralized genetic algorithm is used to find the solution.
Recent studies show an increasing interest in the use of exact schemes to solve optimization problems in WSNs \cite{ref230,ref231,ref121,ref122,ref120}. Column Generation (CG) has been widely used to address different versions of Maximum-network Lifetime Problem (MLP). CG decomposes the problem into a Restricted Master Problem (RMP) and a Pricing Subproblem (PS). The former maximizes lifetime using an incomplete set of columns and the latter is used to identify new profitable columns. A. Rossi et al.~\cite{ref121} introduce an efficient implementation of a genetic algorithm based on CG to extend the lifetime and maximize target coverage in wireless sensor networks under bandwidth constraints. The authors show that the use of metaheuristic methods to solve PS in the context of CG allows to obtain optimal solutions quite fast and to produce high-quality solutions when the algorithm is stopped before returning an optimal solution. More recently, F. Castano et al. \cite{ref120} address the maximum network lifetime and the target coverage problem in WSNs with connectivity and coverage constraints. They consider two cases to schedule the activity of a set of sensor nodes, keeping them connected while network lifetime is maximized. First, the full coverage of the targets is required, second only a fraction of the targets has to be monitored at any instant of time. They propose an exact approach based on column generation boosted by a Greedy Randomized Adaptive Search Procedure (GRASP) and a Variable Neighborhood Search (VNS) to address both of these problems. Finally, a multiphase framework combining these two approaches is constructed sequentially using these two heuristics at each iteration of the column generation algorithm. The results show that combining the two heuristic methods enhances the results significantly.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.4]{Figures/ch2/GAF2.eps}
-\caption{ Example of fixed square grid in GAF.}
+\caption{ State transitions in GAF.}
\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 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). Inside each fixed square grid, sensor nodes collaborate with each other to play different roles. For example, nodes will elect
-one sensor node (based on the remaining energy of sensor nodes inside the fixed square grid) to stay awake for a certain period of time, and then the rest go to sleep. This sensor node is responsible for monitoring and reporting data to the base station on behalf of the nodes
-in the square grid.
+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. Sensor node changes its state to Discovery to give a chance to other nodes within the same grid to become Active.
+%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 Sleeping 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). Inside each fixed square grid, sensor nodes collaborate with each other to play different roles. For example, nodes will elect
+one sensor node (based on the remaining energy of sensor nodes inside the fixed square grid) to stay awake for a certain period of time, and then the rest go to sleep. This sensor node is responsible for monitoring, routing, and reporting data to the base station on behalf of the nodes in the square grid. For nodes with same state, GAF gives nodes with longer expected lifetime (enat) higher rank, therefore they are called high rank nodes.
%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}
+\subsection{Distributed Energy-efficient Scheduling for K-coverage (DESK)}
\label{ch2:sec:03:2}
-The authors in~\cite{DESK} 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}.
+% The authors in~\cite{DESK} design a novel distributed heuristic, called Distributed Energy-efficient Scheduling for K-coverage (DESK), which
+DESK is a novel distributed heuristic to ensure that the energy consumption among the sensors is balanced and the lifetime maximized while the coverage requirement is satisfied~\cite{DESK}. 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 DESK \cite{ref133}, the whole area is K-covered if and only if the perimeters 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 $.
-
+In DESK \cite{ref133}, the whole area is K-covered if and only if the perimeters of all sensors are K-covered. The coverage level 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 in the range [0,2$ \pi $]. According to figure~\ref{figp}~(a) and (b), the coverage level of sensor $s_i$ can be calculated as follows.
+%via traversing the range from 0 to 2$ \pi $.
+For each sensor $s_j$ such that $d(s_i,s_j)$ $<$ $2R_s$, calculate the angle of $s_i$'s arc, denoted by [$\alpha_{j,L}$, $\alpha_{j,R}$], which is perimeter covered by $s_j$, where $\alpha= arccos(d(s_i, s_j)/2R_s)$ and $d(s_i,s_j)$ is the Euclidean distance between $s_i$ and $s_j$. After that, locate the points $\alpha_{j,L}$ and $\alpha_{j,R}$ of each neighboring sensor $s_j$ of $s_i$ on the line segment $[0, 2\pi]$. These points are sorted in ascending order into a list L. Traverse the line segment from 0 to $2\pi$ by visiting each element in the sorted list L from the left to the right and determine the perimeter coverage of $s_i$. Whenever an element $\alpha_{j,L}$ is traversed, the level of perimeter coverage should be increased by one. Whenever an element $\alpha_{j,R}$ is traversed, the level of perimeter coverage should be decreased by one.
+
\begin{figure}[h!]
\centering
\begin{tabular}{@{}cr@{}}
\label{desk}
\end{figure}
-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 is 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 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 their 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$ of node $s_i$ is dynamic and can be changed at any time based on the status of its 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 neighbors which need $s_i$ to be active. The waiting time is defined as follows:
\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}$} \\
- W & \mbox{Otherwise.}\\
+ \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 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 means that the segment of the perimeter of the considered sensor overlapping with that neighbor is already covered by active sensors.
+where $\alpha, \beta,$ and $\eta$ are constant, z is a random number between [0; d], where d is a time duration, to avoid the case where two sensors 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 redundancy) of a neighbor refers to one that does not contribute to the perimeter coverage of the considered sensor. This means that the segment of the perimeter of the considered sensor overlapping with that neighbor is already covered by active sensors.
-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. Each sensor 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 is covered by other active neighbors, it will send mASK2SLEEP message to that sensor u. 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.
+Typically, the algorithm works as follows. At the beginning of each round, there are no active sensors. 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. Each sensor stores this information into a list L in the increasing order of the angle $\alpha $. Each sensor sets its timer $w_i$ with the assumption 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 one hop neighbors about its status change. Its neighbors execute the perimeter coverage model to recalculate their coverage level. If a node finds any neighbor u that is useless in covering its perimeter, i.e., the perimeter that u covers is covered by other active neighbors, it will send mASK2SLEEP message to that sensor u. 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 sensor node receives a mGOSLEEP message, it removes the neighbor sending that message out of its list L. All the sensors have to decide their status in the decision phase. After that, the active sensors perform the sensing task during the sensing phase.
%The period the average
\begin{flushleft}
\centering
-\caption{Main characteristics of some coverage approaches in previous literatures.}
+\caption{Main characteristics of some coverage approaches in literature.}
\label{x11}
\begin{tabular}{@{} cl*{13}c @{}}
+ & & \\
& & \multicolumn{10}{c}{Characteristics} \\[2ex]
- \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} \\
+ \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 or Periods} & \mcrot{1}{l}{50}{\footnotesize Adjustable Radius} \\
\cmidrule[1pt]{2-14}
& \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 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}{\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 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}{\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}} & & \\
+&\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}} & &\textbf{\textcolor{red}{\OK}} & & \\
\cmidrule[1pt]{2-14}
\end{tabular}
\section{Conclusion}
\label{ch2:sec:05}
-This chapter describes some coverage proposed problems in the literature, with their assumptions and proposed solutions.
-The coverage problem is considered as 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 aim 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.
+This chapter describes some coverage problems in the literature, with their assumptions and proposed solutions.
+The coverage is considered as an essential requirement for many applications in WSNs because the better the coverage of an area of interest, the better the sensing measurements of the physical phenomenon. Therefore, many extensive researches have been focused on that problem. These researches aim 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.
%Whatever the case, this would result in a lower 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 an hybrid approach to 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.
+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 an hybrid approach to take into account the advantages of both centralized and distributed coverage approaches. A such hybrid approach can provide a good quality coverage and prolong the network lifetime.
