Once a sensor nodes are deployed, a coverage algorithm is run to schedule the sensor nodes into cover sets so as to maintain sufficient coverage in the area of interest and extend the network lifetime. The WSN applications require (complete or partial) area coverage and complete target coverage. This chapter concentrates only on area coverage and target coverage problems because it is possible to transform the area coverage problem to target ( or point) coverage problem and vice versa. We exclude the barrier coverage problem from this discussion about the coverage problem because it is outside the scope of this dissertation. We have focused mainly on the area coverage problem. Therefore, we represent the sensing area of each sensor node in the sensing field as a set of primary points and then achieving full area coverage by covering all the points in the sensing field. The ultimate goal of the area coverage problem is to choose the minimum number of sensor nodes to cover the whole sensing region and prolonging the lifetime of the WSN.
-Many centralized and distributed algorithms for activity scheduling have been proposed in the literature and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. A distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and the only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near-optimal) solution based only on local information. Several algorithms to retain the coverage and maximize the network lifetime were proposed in~\cite{ref113,ref101,ref103,ref105}. Table~\ref{Table1:ch2} summarized the main characteristics of some coverage approaches in previous literatures.
+Many centralized and distributed coverage algorithms for activity scheduling have been proposed in the literature and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. The centralized algorithms have the advantage of requiring very low processing power from the sensor nodes which have usually limited processing capabilities. Moreover, a recent study conducted in \cite{ref226} concludes that there is a threshold in terms of network size to switch from a localized to a centralized algorithm.
+In a distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and the only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near-optimal) solution based only on local information. Table~\ref{Table0:ch2} shows a comparison between the centralized coverage algorithms and the distributed coverage algorithms.
-\subsection{Centralized Algorithms}
-\label{ch2:sec:03}
+
+\begin{table}[h]
+\caption{Centralized Coverage Algorithms vs Distributed Coverage Algorithms}
+\begin{center}
+\begin{tabular}{ |p{3cm}|p{5cm}|p{5cm}|}
+\hline
+
+\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} Communication \end{center}} & Require large power consumption for communication. & Require low power consumption for communication. \\ \hline
+
+\textbf{\begin{center} Decision \end{center}} & Ensure optimal (or near-optimal) solution. & Can not ensure optimal (or near-optimal) solution.\\ \hline
+
+\textbf{\begin{center} Redundancy \end{center}} & Provide less redundant active sensor nodes during monitoring the sensing field. & Provide more redundant active sensor nodes during monitoring the sensing field.\\ \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} Reliability \end{center}} & Less robust against sensor failure. & More robust against sensor failure. \\ \hline
+
+\end{tabular}
+\end{center}
+\label{Table0:ch2}
+\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.
+
+
+\section{Centralized Algorithms}
+\label{ch2:sec:02}
The major approach 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 nearly or close to the optimal solution since the algorithm has a global view of the whole network. Note that centralized algorithms have the advantage of requiring very low processing power from the sensor nodes, which usually have limited processing capabilities. The main drawback of this kind of approach is its higher cost in communications, since the node that will make the decision needs information from all the sensor nodes. Moreover, centralized approaches usually suffer from the scalability problem, making them less competitive as the network size increases.
-\subsection{Distributed Algorithms}
-\label{ch2:sec:04}
+\section{Distributed Algorithms}
+\label{ch2:sec:03}
In distributed and localized coverage algorithms, the required computation to schedule the activity of sensor nodes will be done by the cooperation among neighboring nodes. These algorithms may require more computation power for the processing by the cooperating sensor nodes, but they are more scalable for large WSNs. Localized and distributed algorithms generally result in non-disjoint set covers.
Many distributed algorithms have been developed to perform the scheduling so as to preserve coverage, see for example \cite{ref123,ref124,ref125,ref126,ref109,ref127,ref128,ref97}.
In \cite{ref133} authors prove that if the perimeters of sensors are sufficiently covered it will be the case for the whole area. They provide an algorithm in $O(nd~log~d)$ time to compute the perimeter coverage of
each sensor, where $d$ denotes the maximum number of sensors that are neighboring to a sensor and $n$ is the total number of sensors in the network.
+\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.
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.
+\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.
\contentsline {section}{\numberline {1.11}Conclusion}{39}{section.1.11}
\contentsline {chapter}{\numberline {2}Related Works on Coverage Problems}{41}{chapter.2}
\contentsline {section}{\numberline {2.1}Introduction}{41}{section.2.1}
-\contentsline {subsection}{\numberline {2.1.1}Centralized Algorithms}{43}{subsection.2.1.1}
-\contentsline {subsection}{\numberline {2.1.2}Distributed Algorithms}{45}{subsection.2.1.2}
-\contentsline {section}{\numberline {2.2}Conclusion}{48}{section.2.2}
-\contentsline {chapter}{\numberline {3}Evaluation Tools and Optimization Solvers}{51}{chapter.3}
-\contentsline {section}{\numberline {3.1}Introduction}{51}{section.3.1}
-\contentsline {section}{\numberline {3.2}Evaluation Tools}{51}{section.3.2}
-\contentsline {subsection}{\numberline {3.2.1}Testbed Tools}{52}{subsection.3.2.1}
-\contentsline {subsection}{\numberline {3.2.2}Simulation Tools}{53}{subsection.3.2.2}
-\contentsline {section}{\numberline {3.3}Optimization Solvers}{58}{section.3.3}
-\contentsline {section}{\numberline {3.4}Conclusion}{61}{section.3.4}
-\contentsline {part}{II\hspace {1em}Contributions}{63}{part.2}
-\contentsline {chapter}{\numberline {4}Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{65}{chapter.4}
-\contentsline {section}{\numberline {4.1}Introduction}{65}{section.4.1}
-\contentsline {section}{\numberline {4.2}Description of the DiLCO Protocol}{66}{section.4.2}
-\contentsline {subsection}{\numberline {4.2.1}Assumptions and Network Model}{66}{subsection.4.2.1}
-\contentsline {subsection}{\numberline {4.2.2}Primary Point Coverage Model}{67}{subsection.4.2.2}
-\contentsline {subsection}{\numberline {4.2.3}Main Idea}{68}{subsection.4.2.3}
-\contentsline {subsubsection}{\numberline {4.2.3.1}Information Exchange Phase}{69}{subsubsection.4.2.3.1}
-\contentsline {subsubsection}{\numberline {4.2.3.2}Leader Election Phase}{69}{subsubsection.4.2.3.2}
-\contentsline {subsubsection}{\numberline {4.2.3.3}Decision phase}{69}{subsubsection.4.2.3.3}
-\contentsline {subsubsection}{\numberline {4.2.3.4}Sensing phase}{69}{subsubsection.4.2.3.4}
-\contentsline {section}{\numberline {4.3}Primary Points based Coverage Problem Formulation}{70}{section.4.3}
-\contentsline {section}{\numberline {4.4}Simulation Results and Analysis}{72}{section.4.4}
-\contentsline {subsection}{\numberline {4.4.1}Simulation Framework}{72}{subsection.4.4.1}
-\contentsline {subsection}{\numberline {4.4.2}Modeling Language and Optimization Solver}{72}{subsection.4.4.2}
-\contentsline {subsection}{\numberline {4.4.3}Energy Consumption Model}{72}{subsection.4.4.3}
-\contentsline {subsection}{\numberline {4.4.4}Performance Metrics}{73}{subsection.4.4.4}
-\contentsline {subsection}{\numberline {4.4.5}Performance Analysis for Different Subregions}{74}{subsection.4.4.5}
-\contentsline {subsection}{\numberline {4.4.6}Performance Analysis for Primary Point Models}{80}{subsection.4.4.6}
-\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{85}{subsection.4.4.7}
-\contentsline {section}{\numberline {4.5}Conclusion}{91}{section.4.5}
-\contentsline {chapter}{\numberline {5}Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{93}{chapter.5}
-\contentsline {section}{\numberline {5.1}Introduction}{93}{section.5.1}
-\contentsline {section}{\numberline {5.2}MuDiLCO Protocol Description}{94}{section.5.2}
-\contentsline {subsection}{\numberline {5.2.1}Background Idea and Algorithm}{94}{subsection.5.2.1}
-\contentsline {section}{\numberline {5.3}Primary Points based Multiround Coverage Problem Formulation}{95}{section.5.3}
-\contentsline {section}{\numberline {5.4}Experimental Study and Analysis}{97}{section.5.4}
-\contentsline {subsection}{\numberline {5.4.1}Simulation Setup}{97}{subsection.5.4.1}
-\contentsline {subsection}{\numberline {5.4.2}Metrics}{98}{subsection.5.4.2}
-\contentsline {subsection}{\numberline {5.4.3}Results Analysis and Comparison }{99}{subsection.5.4.3}
-\contentsline {section}{\numberline {5.5}Conclusion}{104}{section.5.5}
-\contentsline {chapter}{\numberline {6}Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}{107}{chapter.6}
-\contentsline {section}{\numberline {6.1}Introduction}{107}{section.6.1}
-\contentsline {section}{\numberline {6.2}The PeCO Protocol Description}{108}{section.6.2}
-\contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{108}{subsection.6.2.1}
-\contentsline {subsection}{\numberline {6.2.2}The Main Idea}{111}{subsection.6.2.2}
-\contentsline {subsection}{\numberline {6.2.3}PeCO Protocol Algorithm}{111}{subsection.6.2.3}
-\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{112}{section.6.3}
-\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{114}{section.6.4}
-\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{114}{subsection.6.4.1}
-\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{115}{subsection.6.4.2}
-\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{116}{subsubsection.6.4.2.1}
-\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{116}{subsubsection.6.4.2.2}
-\contentsline {subsubsection}{\numberline {6.4.2.3}The Energy Consumption}{117}{subsubsection.6.4.2.3}
-\contentsline {subsubsection}{\numberline {6.4.2.4}The Network Lifetime}{117}{subsubsection.6.4.2.4}
-\contentsline {section}{\numberline {6.5}Conclusion}{120}{section.6.5}
-\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{121}{part.3}
-\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{123}{chapter.7}
-\contentsline {section}{\numberline {7.1}Conclusion}{123}{section.7.1}
-\contentsline {section}{\numberline {7.2}Perspectives}{124}{section.7.2}
-\contentsline {part}{Bibliographie}{139}{chapter*.6}
+\contentsline {section}{\numberline {2.2}Centralized Algorithms}{43}{section.2.2}
+\contentsline {section}{\numberline {2.3}Distributed Algorithms}{45}{section.2.3}
+\contentsline {subsection}{\numberline {2.3.1}GAF}{46}{subsection.2.3.1}
+\contentsline {subsection}{\numberline {2.3.2}DESK}{48}{subsection.2.3.2}
+\contentsline {section}{\numberline {2.4}Conclusion}{49}{section.2.4}
+\contentsline {chapter}{\numberline {3}Evaluation Tools and Optimization Solvers}{53}{chapter.3}
+\contentsline {section}{\numberline {3.1}Introduction}{53}{section.3.1}
+\contentsline {section}{\numberline {3.2}Evaluation Tools}{53}{section.3.2}
+\contentsline {subsection}{\numberline {3.2.1}Testbed Tools}{54}{subsection.3.2.1}
+\contentsline {subsection}{\numberline {3.2.2}Simulation Tools}{55}{subsection.3.2.2}
+\contentsline {section}{\numberline {3.3}Optimization Solvers}{60}{section.3.3}
+\contentsline {section}{\numberline {3.4}Conclusion}{63}{section.3.4}
+\contentsline {part}{II\hspace {1em}Contributions}{65}{part.2}
+\contentsline {chapter}{\numberline {4}Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{67}{chapter.4}
+\contentsline {section}{\numberline {4.1}Introduction}{67}{section.4.1}
+\contentsline {section}{\numberline {4.2}Description of the DiLCO Protocol}{68}{section.4.2}
+\contentsline {subsection}{\numberline {4.2.1}Assumptions and Network Model}{68}{subsection.4.2.1}
+\contentsline {subsection}{\numberline {4.2.2}Primary Point Coverage Model}{69}{subsection.4.2.2}
+\contentsline {subsection}{\numberline {4.2.3}Main Idea}{70}{subsection.4.2.3}
+\contentsline {subsubsection}{\numberline {4.2.3.1}Information Exchange Phase}{71}{subsubsection.4.2.3.1}
+\contentsline {subsubsection}{\numberline {4.2.3.2}Leader Election Phase}{71}{subsubsection.4.2.3.2}
+\contentsline {subsubsection}{\numberline {4.2.3.3}Decision phase}{71}{subsubsection.4.2.3.3}
+\contentsline {subsubsection}{\numberline {4.2.3.4}Sensing phase}{71}{subsubsection.4.2.3.4}
+\contentsline {section}{\numberline {4.3}Primary Points based Coverage Problem Formulation}{72}{section.4.3}
+\contentsline {section}{\numberline {4.4}Simulation Results and Analysis}{74}{section.4.4}
+\contentsline {subsection}{\numberline {4.4.1}Simulation Framework}{74}{subsection.4.4.1}
+\contentsline {subsection}{\numberline {4.4.2}Modeling Language and Optimization Solver}{74}{subsection.4.4.2}
+\contentsline {subsection}{\numberline {4.4.3}Energy Consumption Model}{74}{subsection.4.4.3}
+\contentsline {subsection}{\numberline {4.4.4}Performance Metrics}{75}{subsection.4.4.4}
+\contentsline {subsection}{\numberline {4.4.5}Performance Analysis for Different Subregions}{76}{subsection.4.4.5}
+\contentsline {subsection}{\numberline {4.4.6}Performance Analysis for Primary Point Models}{82}{subsection.4.4.6}
+\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{87}{subsection.4.4.7}
+\contentsline {section}{\numberline {4.5}Conclusion}{93}{section.4.5}
+\contentsline {chapter}{\numberline {5}Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{95}{chapter.5}
+\contentsline {section}{\numberline {5.1}Introduction}{95}{section.5.1}
+\contentsline {section}{\numberline {5.2}MuDiLCO Protocol Description}{96}{section.5.2}
+\contentsline {subsection}{\numberline {5.2.1}Background Idea and Algorithm}{96}{subsection.5.2.1}
+\contentsline {section}{\numberline {5.3}Primary Points based Multiround Coverage Problem Formulation}{97}{section.5.3}
+\contentsline {section}{\numberline {5.4}Experimental Study and Analysis}{99}{section.5.4}
+\contentsline {subsection}{\numberline {5.4.1}Simulation Setup}{99}{subsection.5.4.1}
+\contentsline {subsection}{\numberline {5.4.2}Metrics}{100}{subsection.5.4.2}
+\contentsline {subsection}{\numberline {5.4.3}Results Analysis and Comparison }{101}{subsection.5.4.3}
+\contentsline {section}{\numberline {5.5}Conclusion}{106}{section.5.5}
+\contentsline {chapter}{\numberline {6}Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}{109}{chapter.6}
+\contentsline {section}{\numberline {6.1}Introduction}{109}{section.6.1}
+\contentsline {section}{\numberline {6.2}The PeCO Protocol Description}{110}{section.6.2}
+\contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{110}{subsection.6.2.1}
+\contentsline {subsection}{\numberline {6.2.2}The Main Idea}{113}{subsection.6.2.2}
+\contentsline {subsection}{\numberline {6.2.3}PeCO Protocol Algorithm}{113}{subsection.6.2.3}
+\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{114}{section.6.3}
+\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{116}{section.6.4}
+\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{116}{subsection.6.4.1}
+\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{117}{subsection.6.4.2}
+\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{118}{subsubsection.6.4.2.1}
+\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{118}{subsubsection.6.4.2.2}
+\contentsline {subsubsection}{\numberline {6.4.2.3}The Energy Consumption}{119}{subsubsection.6.4.2.3}
+\contentsline {subsubsection}{\numberline {6.4.2.4}The Network Lifetime}{119}{subsubsection.6.4.2.4}
+\contentsline {section}{\numberline {6.5}Conclusion}{122}{section.6.5}
+\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{123}{part.3}
+\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{125}{chapter.7}
+\contentsline {section}{\numberline {7.1}Conclusion}{125}{section.7.1}
+\contentsline {section}{\numberline {7.2}Perspectives}{126}{section.7.2}
+\contentsline {part}{Bibliographie}{141}{chapter*.6}
