-\subsection{Primary Point Coverage Model}
-\label{ch3:sec:02:02}
-\indent Instead of working with the coverage area, we consider for each
-sensor a set of points called primary points. We also assume that the
-sensing disk defined by a sensor is covered if all the primary points of
-this sensor are covered. By knowing the position (point center: ($p_x,p_y$)) of a wireless
-sensor node and its $R_s$, we calculate the primary points directly
-based on the proposed model. We use these primary points (that can be
-increased or decreased if necessary) as references to ensure that the
-monitored region of interest is covered by the selected set of
-sensors, instead of using all the points in the area.
-
-\indent We can calculate the positions of the selected primary
-points in the circle disk of the sensing range of a wireless sensor
-node (see figure~\ref{fig1}) as follows:\\
-$(p_x,p_y)$ = point center of wireless sensor node\\
-$X_1=(p_x,p_y)$ \\
-$X_2=( p_x + R_s * (1), p_y + R_s * (0) )$\\
-$X_3=( p_x + R_s * (-1), p_y + R_s * (0)) $\\
-$X_4=( p_x + R_s * (0), p_y + R_s * (1) )$\\
-$X_5=( p_x + R_s * (0), p_y + R_s * (-1 )) $\\
-$X_6= ( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (0)) $\\
-$X_7=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (0))$\\
-$X_8=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
-$X_9=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
-$X_{10}=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
-$X_{11}=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
-$X_{12}=( p_x + R_s * (0), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
-$X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
-$X_{14}=( p_x + R_s * (\frac{\sqrt{3}}{2}), p_y + R_s * (\frac{1}{2})) $\\
-$X_{15}=( p_x + R_s * (\frac{-\sqrt{3}}{2}), p_y + R_s * (\frac{1}{2})) $\\
-$X_{16}=( p_x + R_s * (\frac{\sqrt{3}}{2}), p_y + R_s * (\frac{- 1}{2})) $\\
-$X_{17}=( p_x + R_s * (\frac{-\sqrt{3}}{2}), p_y + R_s * (\frac{- 1}{2})) $\\
-$X_{18}=( p_x + R_s * (\frac{\sqrt{3}}{2}), p_y + R_s * (0) $\\
-$X_{19}=( p_x + R_s * (\frac{-\sqrt{3}}{2}), p_y + R_s * (0) $\\
-$X_{20}=( p_x + R_s * (0), p_y + R_s * (\frac{1}{2})) $\\
-$X_{21}=( p_x + R_s * (0), p_y + R_s * (-\frac{1}{2})) $\\
-$X_{22}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{\sqrt{3}}{2})) $\\
-$X_{23}=( p_x + R_s * (\frac{- 1}{2}), p_y + R_s * (\frac{\sqrt{3}}{2})) $\\
-$X_{24}=( p_x + R_s * (\frac{- 1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $\\
-$X_{25}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $.
-
-\begin{figure}[h!]
-\centering
- \begin{multicols}{3}
-\centering
-\includegraphics[scale=0.20]{Figures/ch3/fig21.pdf}\\~ ~ ~ ~ ~(a)
-\includegraphics[scale=0.20]{Figures/ch3/fig22.pdf}\\~ ~ ~ ~ ~(b)
-\includegraphics[scale=0.20]{Figures/ch3/principles13.pdf}\\~ ~ ~ ~ ~(c)
-\hfill
-\includegraphics[scale=0.20]{Figures/ch3/fig24.pdf}\\~ ~ ~(d)
-\includegraphics[scale=0.20]{Figures/ch3/fig25.pdf}\\~ ~ ~(e)
-\includegraphics[scale=0.20]{Figures/ch3/fig26.pdf}\\~ ~ ~(f)
-\end{multicols}
-\caption{Wireless Sensor Node represented by (a)5, (b)9, (c)13, (d)17, (e)21 and (f)25 primary points respectively}
-\label{fig1}
-\end{figure}
-
-
-
-\subsection{Main Idea}
-\label{ch3:sec:02:03}
-\noindent We start by applying a divide-and-conquer algorithm to partition the
-area of interest into smaller areas called subregions and then our protocol is
-executed simultaneously in each subregion.
-
-\begin{figure}[ht!]
-\centering
-\includegraphics[scale=0.60]{Figures/ch3/FirstModel.pdf} % 70mm
-\caption{DiLCO protocol}
-\label{FirstModel}
-\end{figure}
-
-As shown in Figure~\ref{FirstModel}, the proposed DiLCO protocol is a periodic
-protocol where each period is decomposed into 4~phases: Information Exchange,
-Leader Election, Decision, and Sensing. For each period there will be exactly
-one cover set in charge of the sensing task. A periodic scheduling is
-interesting because it enhances the robustness of the network against node
-failures. First, a node that has not enough energy to complete a period, or
-which fails before the decision is taken, will be excluded from the scheduling
-process. Second, if a node fails later, whereas it was supposed to sense the
-region of interest, it will only affect the quality of the coverage until the
-definition of a new cover set in the next period. Constraints, like energy
-consumption, can be easily taken into consideration since the sensors can update
-and exchange their information during the first phase. Let us notice that the
-phases before the sensing one (Information Exchange, Leader Election, and
-Decision) are energy consuming for all the nodes, even nodes that will not be
-retained by the leader to keep watch over the corresponding area.
-
-Below, we describe each phase in more details.
-
-\subsubsection{Information Exchange Phase}
-\label{ch3:sec:02:03:01}
-Each sensor node $j$ sends its position, remaining energy $RE_j$, and the number
-of neighbors $NBR_j$ to all wireless sensor nodes in its subregion by using an
-INFO packet (containing information on position coordinates, current remaining
-energy, sensor node ID, number of its one-hop live neighbors) and then waits for
-packets sent by other nodes. After that, each node will have information about
-all the sensor nodes in the subregion. In our model, the remaining energy
-corresponds to the time that a sensor can live in the active mode.
-
-\subsubsection{Leader Election Phase}
-\label{ch3:sec:02:03:02}
-This step includes choosing the Wireless Sensor Node Leader (WSNL), which will be responsible for executing the coverage algorithm. Each subregion in the area of interest will select its own WSNL independently for each round. All the sensor nodes cooperate to select WSNL. The nodes in the same subregion will select the leader based on the received information from all other nodes in the same subregion. The selection criteria are, in order of importance: larger number of neighbors, larger remaining energy, and then in case of equality, larger index. Observations on previous simulations suggest to use the number of one-hop neighbors as the primary criterion to reduce energy consumption due to the communications.
-
-
-\subsubsection{Decision phase}
-\label{ch3:sec:02:03:03}
-The WSNL will solve an integer program (see section~\ref{ch3:sec:03}) to select which sensors will be activated in the following sensing phase to cover the subregion. WSNL will send Active-Sleep packet to each sensor in the subregion based on the algorithm's results.
-
-
-\subsubsection{Sensing phase}
-\label{ch3:sec:02:03:04}
-Active sensors in the round will execute their sensing task to
-preserve maximal coverage in the region of interest. We will assume
-that the cost of keeping a node awake (or asleep) for sensing task is
-the same for all wireless sensor nodes in the network. Each sensor
-will receive an Active-Sleep packet from WSNL informing it to stay
-awake or to go to sleep for a time equal to the period of sensing until
-starting a new round.
-
-An outline of the protocol implementation is given by Algorithm~\ref{alg:DiLCO}
-which describes the execution of a period by a node (denoted by $s_j$ for a
-sensor node indexed by $j$). At the beginning a node checks whether it has
-enough energy to stay active during the next sensing phase. If yes, it exchanges
-information with all the other nodes belonging to the same subregion: it
-collects from each node its position coordinates, remaining energy ($RE_j$), ID,
-and the number of one-hop neighbors still alive. Once the first phase is
-completed, the nodes of a subregion choose a leader to take the decision based
-on the following criteria with decreasing importance: larger number of
-neighbors, larger remaining energy, and then in case of equality, larger index.
-After that, if the sensor node is leader, it will execute the integer program
-algorithm (see Section~\ref{ch3:sec:03}) which provides a set of sensors planned to be
-active in the next sensing phase. As leader, it will send an Active-Sleep packet
-to each sensor in the same subregion to indicate it if it has to be active or
-not. Alternately, if the sensor is not the leader, it will wait for the
-Active-Sleep packet to know its state for the coming sensing phase.
-
-
-\begin{algorithm}[h!]
-
- \BlankLine
- %\emph{Initialize the sensor node and determine it's position and subregion} \;
-
- \If{ $RE_j \geq E_{th}$ }{
- \emph{$s_j.status$ = COMMUNICATION}\;
- \emph{Send $INFO()$ packet to other nodes in the subregion}\;
- \emph{Wait $INFO()$ packet from other nodes in the subregion}\;
- %\emph{UPDATE $RE_j$ for every sent or received INFO Packet}\;
- %\emph{ Collect information and construct the list L for all nodes in the subregion}\;
-
- %\If{ the received INFO Packet = No. of nodes in it's subregion -1 }{
- \emph{LeaderID = Leader election}\;
- \If{$ s_j.ID = LeaderID $}{
- \emph{$s_j.status$ = COMPUTATION}\;
- \emph{$\left\{\left(X_{1},\dots,X_{k},\dots,X_{J}\right)\right\}$ =
- Execute Integer Program Algorithm($J$)}\;
- \emph{$s_j.status$ = COMMUNICATION}\;
- \emph{Send $ActiveSleep()$ to each node $k$ in subregion} \;
- \emph{Update $RE_j $}\;
- }
- \Else{
- \emph{$s_j.status$ = LISTENING}\;
- \emph{Wait $ActiveSleep()$ packet from the Leader}\;
-
- \emph{Update $RE_j $}\;
- }
- % }
- }
- \Else { Exclude $s_j$ from entering in the current sensing phase}
-
- % \emph{return X} \;
-\caption{DiLCO($s_j$)}
-\label{alg:DiLCO}
-
-\end{algorithm}
-
-
-
-\section{COVERAGE PROBLEM FORMULATION}
-\label{ch3:sec:03}
-\indent Our model is based on the model proposed by \cite{ref156} where the
-objective is to find a maximum number of disjoint cover sets. To accomplish
-this goal, the authors proposed an integer program which forces undercoverage
-and overcoverage of targets to become minimal at the same time. They use binary
-variables $x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our
-model, we consider that the binary variable $X_{j}$ determines the activation of
-sensor $j$ in the sensing phase. We also consider primary points as targets.
-The set of primary points is denoted by $P$ and the set of sensors by $J$.
-
-\noindent Let $\alpha_{jp}$ denote the indicator function of whether the primary
-point $p$ is covered, that is:
-\begin{equation}
-\alpha_{jp} = \left \{
-\begin{array}{l l}
- 1 & \mbox{if the primary point $p$ is covered} \\
- & \mbox{by sensor node $j$}, \\
- 0 & \mbox{otherwise.}\\
-\end{array} \right.
-%\label{eq12}
-\end{equation}
-The number of active sensors that cover the primary point $p$ can then be
-computed by $\sum_{j \in J} \alpha_{jp} * X_{j}$ where:
-\begin{equation}
-X_{j} = \left \{
-\begin{array}{l l}
- 1& \mbox{if sensor $j$ is active,} \\
- 0 & \mbox{otherwise.}\\
-\end{array} \right.
-%\label{eq11}
-\end{equation}
-We define the Overcoverage variable $\Theta_{p}$ as:
-\begin{equation}
- \Theta_{p} = \left \{
-\begin{array}{l l}
- 0 & \mbox{if the primary point}\\
- & \mbox{$p$ is not covered,}\\
- \left( \sum_{j \in J} \alpha_{jp} * X_{j} \right)- 1 & \mbox{otherwise.}\\
-\end{array} \right.
-\label{eq13}
-\end{equation}
-\noindent More precisely, $\Theta_{p}$ represents the number of active sensor
-nodes minus one that cover the primary point~$p$. The Undercoverage variable
-$U_{p}$ of the primary point $p$ is defined by:
-\begin{equation}
-U_{p} = \left \{
-\begin{array}{l l}
- 1 &\mbox{if the primary point $p$ is not covered,} \\
- 0 & \mbox{otherwise.}\\
-\end{array} \right.
-\label{eq14}
-\end{equation}
-
-\noindent Our coverage optimization problem can then be formulated as follows:
-\begin{equation} \label{eq:ip2r}
-\left \{
-\begin{array}{ll}
-\min \sum_{p \in P} (w_{\theta} \Theta_{p} + w_{U} U_{p})&\\
-\textrm{subject to :}&\\
-\sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, &\forall p \in P\\
-%\label{c1}
-%\sum_{t \in T} X_{j,t} \leq \frac{RE_j}{e_t} &\forall j \in J \\
-%\label{c2}
-\Theta_{p}\in \mathbb{N}, &\forall p \in P\\
-U_{p} \in \{0,1\}, &\forall p \in P \\
-X_{j} \in \{0,1\}, &\forall j \in J
-\end{array}
-\right.
-\end{equation}
