In this chapter, we propose an approach called Perimeter-based Coverage Optimization
protocol (PeCO).
%The PeCO protocol merges between two energy efficient mechanisms, which are used the main advantages of the centralized and distributed approaches and avoids the most of their disadvantages. An energy-efficient activity scheduling mechanism based new optimization model is performed by each leader in the subregions.
-The scheme is similar to the one described in section \ref{ch4:sec:02:03}. But in this approach, the optimization model is based on the perimeter coverage model in order to produce the optimal cover set of active sensors, which are taken the responsibility of sensing during the current period.
+The scheme is similar to the one described in section \ref{ch4:sec:02:03}. But in this approach, the optimization model is based on the perimeter coverage model in order to produce the optimal cover set of active sensors, which are taking the responsibility of sensing during the current period.
The rest of the chapter is organized as follows. The next section is devoted to the PeCO protocol description and section~\ref{ch6:sec:03} focuses on the coverage model formulation which is used to schedule the activation of sensor nodes. Section~\ref{ch6:sec:04} presents simulation results and discusses the comparison with other approaches. Finally, concluding remarks are drawn in section~\ref{ch6:sec:05}.
\end{figure}
Figure~\ref{pcm2sensors}(b) describes the geometric information used to find the locations of the left and right points of an arc on the perimeter of a sensor node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the
-west side of sensor~$u$, with the following respective coordinates in the sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates, the euclidean distance between nodes~$u$ and $v$ is computed as follow: $Dist(u,v)=\sqrt{\vert
- u_x - v_x \vert^2 + \vert u_y-v_y \vert^2}$,
+west side of sensor~$u$, with the following respective coordinates in the sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates, the euclidean distance between nodes~$u$ and $v$ is computed as follow: $Dist(u,v)=\sqrt{\left(
+ u_x - v_x \right)^2 + \left( u_y-v_y \right)^2}$,
while the angle~$\alpha$ is obtained through the formula:
\noindent The WSN area of interest is, in a first step, divided into regular homogeneous subregions using a divide-and-conquer algorithm. In a second step our protocol will be executed in a distributed way in each subregion simultaneously to schedule nodes' activities for one sensing period. Sensor nodes are assumed to be deployed almost uniformly over the region. The regular subdivision is made such that the number of hops between any pairs of sensors inside a subregion is less than or equal to 3.
-As shown in Figure~\ref{fig2}, node activity scheduling is produced by our protocol in a periodic manner. Each period is divided into 4 stages: Information (INFO) Exchange, Leader Election, Decision (the result of an optimization problem), and Sensing. For each period, there is exactly one set cover responsible for the sensing task. Protocols based on a periodic scheme, like PeCO, are more robust against an unexpected node failure. On the one hand, if a node failure is discovered before taking the decision, the corresponding sensor
+As shown in Figure~\ref{fig2}, node activity scheduling is produced by our protocol in a periodic manner. Each period is divided into 4 stages: Information (INFO) Exchange, Leader Election, Decision (the result of an optimization problem), and Sensing. For each period, there is exactly one set cover responsible for the sensing task. Protocols based on a periodic scheme, like PeCO, are more robust against an unexpected node failure. On the one hand, if a node failure is discovered before taking the decision, the corresponding sensor
node will not be considered by the optimization algorithm. On the other hand, if the sensor failure happens after the decision, the sensing task of the network will be temporarily affected: only during the period of sensing until a new period starts, since a new set cover will take charge of the sensing task in the next period. The energy consumption and some other constraints can easily be taken into account since the sensors can update and then exchange their information (including their residual energy) at the beginning of each period. However, the pre-sensing phases (INFO Exchange, Leader Election, and Decision)
are energy consuming, even for nodes that will not join the set cover to monitor the area.
\emph{ Use the same previous cover set for current sensing stage}\;
}
\Else{
- \emph{Update $a^j_{ik}$; prepare data for IP~Algorithm}\;
- \emph{$\left\{\left(X_{1},\dots,X_{k},\dots,X_{A}\right)\right\}$ = Execute Integer Program Algorithm($A$)}\;
+ \emph{Update $a^j_{ik}$; prepare data for MIP~Algorithm}\;
+ \emph{$\left\{\left(X_{1},\dots,X_{k},\dots,X_{A}\right)\right\}$ = Execute MIP Algorithm($A$)}\;
\emph{A.PreviousSize = A.CurrentSize}\;
}
\item larger remaining energy;
\item and then in case of equality, larger index.
\end{enumerate}
-Once chosen, the leader collects information to formulate and solve the integer program which allows to construct the set of active sensors in the sensing stage.
+Once chosen, the leader collects information to formulate and solve the integer program which allows to construct the set of active sensors in the sensing stage. The flowchart of PeCO protocol executed in each sensor node is presented in Figure \ref{flow6}.
+
+\begin{figure}[ht!]
+\centering
+\includegraphics[scale=0.45]{Figures/ch6/Algo3.pdf} % 70mm
+\caption{The flowchart of PeCO protocol.}
+\label{flow6}
+\end{figure}
\section{Perimeter-based Coverage Problem Formulation}
In order to assess and analyze the performance of our protocol we have implemented PeCO protocol in OMNeT++~\cite{ref158} simulator.
%Besides PeCO, three other protocols, described in the next paragraph, will be evaluated for comparison purposes.
%The simulations were run on a laptop DELL with an Intel Core~i3~2370~M (2.4~GHz) processor (2 cores) whose MIPS (Million Instructions Per Second) rate is equal to 35330. To be consistent with the use of a sensor node based on Atmels AVR ATmega103L microcontroller (6~MHz) having a MIPS rate equal to 6, the original execution time on the laptop is multiplied by 2944.2 $\left(\frac{35330}{2} \times \frac{1}{6} \right)$. The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is employed to generate the integer program instance in a standard format, which is then read and solved by the optimization solver GLPK (GNU linear Programming Kit available in the public domain) \cite{glpk} through a Branch-and-Bound method.
-PeCO protocol is compared with three other approaches. DESK \cite{DESK}, GAF~\cite{GAF}, and DiLCO~\cite{Idrees2} is an improved version of a research work we presented in~\cite{ref159}, where DiLCO protocol is described in chapter 4. Let us notice that the PeCO and the DiLCO protocols are based on the same scheme. In particular, the choice for the simulations of a partitioning in 16~subregions was chosen because it corresponds to the configuration producing the better results for DiLCO. The protocols are distinguished from one another by the formulation of the integer program providing the set of sensors which have to be activated in each sensing phase. DiLCO protocol tries to satisfy the coverage of a set of primary points, whereas PeCO protocol objective is to reach a desired level of coverage for each sensor perimeter. In our experimentations, we chose a level of coverage equal to one ($l=1$).
+PeCO protocol is compared with three other approaches. DESK \cite{DESK}, GAF~\cite{GAF}, and DiLCO~\cite{Idrees2}.
+ %is an improved version of a research work we presented in~\cite{ref159}, where DiLCO protocol is described in chapter 4.
+ Let us notice that the PeCO and the DiLCO protocols are based on the same scheme. In particular, the choice for the simulations of a partitioning in 16~subregions was chosen because it corresponds to the configuration producing the better results for DiLCO. The protocols are distinguished from one another by the formulation of the integer program providing the set of sensors which have to be activated in each sensing phase. DiLCO protocol tries to satisfy the coverage of a set of primary points, whereas PeCO protocol objective is to reach a desired level of coverage for each sensor perimeter. In our experimentations, we chose a level of coverage equal to one ($l=1$).
\label{ch6:sec:04:02:02}
Having the less active sensor nodes in each period is essential to minimize the energy consumption and thus to maximize the network lifetime. Figure~\ref{fig444} shows the average active nodes ratio for 200 deployed nodes. We observe that DESK and GAF have 30.36 \% and 34.96 \% active nodes for the first fourteen rounds, and DiLCO and PeCO protocols compete perfectly with only 17.92 \% and 20.16 \% active nodes during the same time interval. As the number of periods increases, PeCO protocol has a lower number of active nodes in comparison with
-the three other approaches, while keeping a greater coverage ratio as shown in Figure \ref{fig333}.
+the three other approaches, while keeping a greater coverage ratio as shown in Figure \ref{fig333}. \\
\begin{figure}[h!]
\centering
\label{ch6:sec:05}
In this chapter, we have studied the problem of Perimeter-based Coverage Optimization in WSNs. We have designed a new protocol, called Perimeter-based Coverage Optimization, which schedules nodes' activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. This protocol is applied in a distributed way in regular subregions obtained after partitioning the area of interest in a preliminary step. It works in periods and
-is based on the resolution of an integer program to select the subset of sensors operating in active status for each period. Our work is original because it proposes for the first time an integer program scheduling the activation of sensors based on their perimeter coverage level, instead of using a set of targets/points to be covered. We have carried out several simulations to evaluate the proposed protocol. The simulation results show that PeCO is more energy-efficient than other approaches, with respect to lifetime, coverage ratio, active sensors ratio, and energy consumption.
+is based on the resolution of an mixed-integer program to select the subset of sensors operating in active status for each period. Our work is original because it proposes for the first time an integer program scheduling the activation of sensors based on their perimeter coverage level, instead of using a set of targets/points to be covered. We have carried out several simulations to evaluate the proposed protocol. The simulation results show that PeCO is more energy-efficient than other approaches, with respect to lifetime, coverage ratio, active sensors ratio, and energy consumption.
%We plan to extend our framework so that the schedules are planned for multiple sensing periods. We also want to improve our integer program to take into account heterogeneous sensors from both energy and node characteristics point of views. Finally, it would be interesting to implement our protocol using a sensor-testbed to evaluate it in real world applications.
