Some minor changes

[JournalMultiPeriods.git] / article.tex

\documentclass[preprint,12pt]{elsarticle}

\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
\usepackage{multicol}
\usepackage{mathtools}  
\usepackage{colortbl}
\usepackage{multirow}

\SetAlFnt{\small}
\SetAlCapFnt{\large}
\SetAlCapNameFnt{\large}
\usepackage{algorithmic}
\algsetup{linenosize=\tiny}

\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
%% Use the option review to obtain double line spacing
%% \documentclass[authoryear,preprint,review,12pt]{elsarticle}

%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
%% for a journal layout:
%% \documentclass[final,1p,times]{elsarticle}
%% \documentclass[final,1p,times,twocolumn]{elsarticle}
%% \documentclass[final,3p,times]{elsarticle}
%% \documentclass[final,3p,times,twocolumn]{elsarticle}
%% \documentclass[final,5p,times]{elsarticle}
%% \documentclass[final,5p,times,twocolumn]{elsarticle}

%% For including figures, graphicx.sty has been loaded in
%% elsarticle.cls. If you prefer to use the old commands
%% please give \usepackage{epsfig}

%% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
%% The amsthm package provides extended theorem environments
%% \usepackage{amsthm}

%% The lineno packages adds line numbers. Start line numbering with
%% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
%% for the whole article with \linenumbers.
%% \usepackage{lineno}

\journal{Journal of Supercomputing}

\begin{document}

\begin{frontmatter}

%% Title, authors and addresses

%% use the tnoteref command within \title for footnotes;
%% use the tnotetext command for theassociated footnote;
%% use the fnref command within \author or \address for footnotes;
%% use the fntext command for theassociated footnote;
%% use the corref command within \author for corresponding author footnotes;
%% use the cortext command for theassociated footnote;
%% use the ead command for the email address,
%% and the form \ead[url] for the home page:
%% \title{Title\tnoteref{label1}}
%% \tnotetext[label1]{}
%% \author{Name\corref{cor1}\fnref{label2}}
%% \ead{email address}
%% \ead[url]{home page}
%% \fntext[label2]{}
%% \cortext[cor1]{}
%% \address{Address\fnref{label3}}
%% \fntext[label3]{}

\title{Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}

%% use optional labels to link authors explicitly to addresses:
%% \author[label1,label2]{}
%% \address[label1]{}
%% \address[label2]{}
%\author{Ali Kadhum Idrees, Karine Deschinkel, \\
%Michel Salomon, and Rapha\"el Couturier}

%\thanks{are members in the AND team - DISC department - FEMTO-ST Institute, University of Franche-Comt\'e, Belfort, France.
% e-mail: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr.}% <-this % stops a space
%\thanks{}% <-this % stops a space
 
%\address{FEMTO-ST Institute, University of Franche-Comt\'e, Belfort, France. \\ 
%e-mail: ali.idness@edu.univ-fcomte.fr, \\
%$\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr.}

\author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$, \\
  Michel Salomon$^{a}$, and Rapha\"el Couturier $^{a}$ \\
  $^{a}${\em{FEMTO-ST Institute, DISC department, UMR 6174 CNRS, \\
      Univ.  Bourgogne  Franche-Comt\'e (UBFC), Belfort, France}} \\
  $^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}}}

\begin{abstract}
Coverage and  lifetime are  two paramount problems  in Wireless  Sensor Networks
(WSNs). In this paper, a  method called Multiround Distributed Lifetime Coverage
Optimization  protocol (MuDiLCO)  is proposed  to maintain  the coverage  and to
improve the lifetime in wireless sensor  networks. The area of interest is first
divided into  subregions and  then the  MuDiLCO protocol  is distributed  on the
sensor nodes in  each subregion. The proposed MuDiLCO protocol  works in periods
during which sets of sensor nodes are  scheduled, with one set for each round of
a period, to remain active during the  sensing phase and thus ensure coverage so
as to  maximize the  WSN lifetime.   The decision  process is  carried out  by a
leader  node,  which  solves  an   optimization  problem  to  produce  the  best
representative  sets to  be used  during the  rounds of  the sensing  phase. The
optimization problem  formulated as an  integer program is solved  to optimality
through a  Branch-and-Bound method for  small instances.  For  larger instances,
the  best  feasible solution  found  by  the solver  after  a  given time  limit
threshold  is considered.   Compared  with some  existing protocols,  simulation
results based on  multiple criteria (energy consumption, coverage  ratio, and so
on) show that the proposed protocol can prolong efficiently the network lifetime
and improve the coverage performance.
\end{abstract}

\begin{keyword}
Wireless   Sensor   Networks,   Area   Coverage,   Network   Lifetime,
Optimization, Scheduling, Distributed Computation.
\end{keyword}

\end{frontmatter}

\section{Introduction}
 
\indent  The   fast  developments  of  low-cost  sensor   devices  and  wireless
communications have allowed the emergence of WSNs. A WSN includes a large number
of small, limited-power sensors that  can sense, process, and transmit data over
a wireless  communication. They communicate  with each other by  using multi-hop
wireless communications and cooperate together  to monitor the area of interest,
so that  each measured data can be  reported to a monitoring  center called sink
for further  analysis~\cite{Sudip03}.  There  are several fields  of application
covering  a wide  spectrum for  a  WSN, including  health, home,  environmental,
military, and industrial applications~\cite{Akyildiz02}.

On the one hand sensor nodes run on batteries with limited capacities, and it is
often  costly  or  simply  impossible  to  replace  and/or  recharge  batteries,
especially in remote and hostile environments. Obviously, to achieve a long life
of the  network it is important  to conserve battery  power. Therefore, lifetime
optimization is one of the most  critical issues in wireless sensor networks. On
the other hand we must guarantee  coverage over the area of interest. To fulfill
these two objectives, the main idea  is to take advantage of overlapping sensing
regions to turn-off redundant sensor nodes  and thus save energy. In this paper,
we concentrate  on the area coverage  problem, with the  objective of maximizing
the network lifetime by using an optimized multiround scheduling.

The MuDiLCO protocol (for  Multiround Distributed Lifetime Coverage Optimization
protocol) presented  in this paper  is an  extension of the  approach introduced
in~\cite{idrees2015distributed}.  
% In~\cite{idrees2015distributed},  the  protocol  is
%deployed over  only two subregions.  Simulation results  have shown that  it was
%more  interesting  to  divide  the  area  into  several  subregions,  given  the
%computation complexity.

\textcolor{blue}{ Compared  to our  previous paper~\cite{idrees2015distributed},
  in  this one  we study  the  possibility of  dividing the  sensing phase  into
  multiple rounds.   In fact, in this  paper we make a  multiround optimization,
  while it was a single round optimization in our previous work.  The idea is to
  take advantage  of the  pre-sensing phase  to plan  the sensor's  activity for
  several  rounds instead  of one,  thus saving  energy. In  addition, when  the
  optimization problem becomes  more complex, its resolution is  stopped after a
  given time  threshold. In this  paper we also  analyze the performance  of our
  protocol according to the number of  primary points used (the area coverage is
  replaced by the coverage of a  set of particular points called primary points,
  see Section~\ref{pp}).}

The remainder of the paper is organized as follows. The next section reviews the
related works in  the field.  Section~\ref{pd} is devoted to  the description of
MuDiLCO protocol.  Section~\ref{exp} introduces  the experimental  framework, it
describes the  simulation setup  and the  different metrics  used to  assess the
performances.   Section~\ref{analysis}  shows  the simulation  results  obtained
using the discrete event simulator OMNeT++ \cite{varga}.  They fully demonstrate
the usefulness  of the proposed  approach.  Finally, we give  concluding remarks
and some suggestions for future works in Section~\ref{sec:conclusion}.

\section{Related works} 
\label{rw}

\indent  This section is  dedicated to  the various  approaches proposed  in the
literature for  the coverage lifetime maximization problem,  where the objective
is to optimally schedule sensors' activities in order to extend network lifetime
in WSNs. Cardei  and Wu \cite{cardei2006energy} provide a  taxonomy for coverage
algorithms in WSNs according to several design choices:
\begin{itemize}
\item  Sensors   scheduling  algorithm  implementation,   i.e.   centralized  or
  distributed/localized algorithms.
\item The objective of sensor coverage, i.e. to maximize the network lifetime or
  to minimize the number of active sensors during a sensing round.
\item The homogeneous or heterogeneous nature  of the nodes, in terms of sensing
  or communication capabilities.
\item The node deployment method, which may be random or deterministic.
\item  Additional  requirements  for  energy-efficient and  connected coverage.
\end{itemize}

The choice of non-disjoint or disjoint cover sets (sensors participate or not in
many cover sets) can be added to the above list.

\subsection{Centralized approaches}

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  optimal solution since the  algorithm has 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.   Exact or  heuristic
  approaches  are designed  to provide  cover sets.  Contrary to  exact methods,
  heuristic  ones can  handle very  large  and centralized  problems.  They  are
  proposed to reduce  computational overhead such as  energy consumption, delay,
  and generally allow to increase the network 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{abrams2004set,cardei2005improving,Slijepcevic01powerefficient}.    In
the  case   of  non-disjoint   algorithms  \cite{pujari2011high},   sensors  may
participate in  more than one  cover set.  In some  cases, this may  prolong the
lifetime of the network in comparison  to the disjoint cover set algorithms, but
designing  algorithms for  non-disjoint cover  sets generally  induces a  higher
order  of complexity.   Moreover, in  case of  a sensor's  failure, non-disjoint
scheduling policies  are less  resilient and  reliable because  a sensor  may be
involved in more than one cover sets.

In~\cite{yang2014maximum},  the authors  have  considered  a linear  programming
approach  to select  the minimum  number of  working sensor  nodes, in  order to
preserve a  maximum coverage and  to extend lifetime  of the network.   Cheng et
al.~\cite{cheng2014energy} have defined a  heuristic algorithm called Cover Sets
Balance  (CSB), which  chooses  a set  of  active nodes  using  the tuple  (data
coverage range, residual  energy).  Then, they have introduced  a new Correlated
Node Set Computing (CNSC) algorithm to find  the correlated node set for a given
node.   After that,  they  proposed a  High Residual  Energy  First (HREF)  node
selection algorithm to minimize the number of  active nodes so as to prolong the
network  lifetime.   Various  centralized  methods based  on  column  generation
approaches                   have                    also                   been
proposed~\cite{gentili2013,castano2013column,rossi2012exact,deschinkel2012column}.
In~\cite{gentili2013}, authors highlight  the trade-off between
  the  network lifetime  and the  coverage  percentage. They  show that  network
  lifetime can be hugely improved by decreasing the coverage ratio.

\subsection{Distributed approaches}

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{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02,      yardibi2010distributed,
  prasad2007distributed,Misra}.   Distributed  algorithms typically  operate  in
rounds for  a predetermined duration. At  the beginning of each  round, a sensor
exchanges information with  its neighbors and makes a decision  to either remain
turned on or  to go to sleep for  the round. This decision is  basically made on
simple     greedy    criteria     like     the     largest    uncovered     area
\cite{Berman05efficientenergy}      or       maximum      uncovered      targets
\cite{lu2003coverage}.   The  Distributed  Adaptive Sleep  Scheduling  Algorithm
(DASSA) \cite{yardibi2010distributed}  does not require location  information of
sensors while  maintaining connectivity and  satisfying a user  defined coverage
target.  In  DASSA, nodes use the  residual energy levels and  feedback from the
sink for  scheduling the activity  of their neighbors.  This  feedback mechanism
reduces  the randomness  in scheduling  that would  otherwise occur  due to  the
absence of location information.  In \cite{ChinhVu}, the authors 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{Huang:2003:CPW:941350.941367}.

The  works presented  in  \cite{Bang, Zhixin,  Zhang}  focus on  coverage-aware,
distributed energy-efficient,  and distributed clustering  methods respectively,
which aim  at extending  the network  lifetime, while  the coverage  is ensured.
More recently, Shibo et al.  \cite{Shibo} have expressed the coverage problem as
a  minimum  weight submodular  set  cover  problem  and proposed  a  Distributed
Truncated Greedy  Algorithm (DTGA) to solve  it.  They take advantage  from both
temporal and spatial correlations between  data sensed by different sensors, and
leverage prediction, to improve the  lifetime.  In \cite{xu2001geography}, 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.

Some  other  approaches (outside  the  scope  of our  work)  do  not consider  a
synchronized and  predetermined time-slot where  the sensors are active  or not.
Indeed, each sensor  maintains its own timer and its  wake-up time is randomized
\cite{Ye03} or regulated \cite{cardei2005maximum} over time.

\section{MuDiLCO protocol description}
\label{pd}

\subsection{Assumptions and primary points}
\label{pp}

\textcolor{blue}{Assumptions and coverage model are identical to those presented
  in~\cite{idrees2015distributed}.}

\iffalse
We  consider a  randomly and  uniformly  deployed network  consisting of  static
wireless sensors.  The sensors are  deployed in high density to ensure initially
a high  coverage ratio  of the interested  area.  We  assume that all  nodes are
homogeneous  in   terms  of  communication  and   processing  capabilities,  and
heterogeneous  from the  point  of view  of  energy provision.   Each sensor  is
supposed  to get information  on its  location either  through hardware  such as
embedded GPS or through location discovery algorithms.
   
To model  a sensor node's coverage  area, we consider the  boolean disk coverage
model   which  is  the   most  widely   used  sensor   coverage  model   in  the
literature. Thus, each  sensor has a constant sensing range  $R_s$ and all space
points within  the disk centered  at the sensor  with the radius of  the sensing
range  is  said  to  be  covered  by  this sensor.   We  also  assume  that  the
communication   range  satisfies   $R_c  \geq   2R_s$.   In   fact,   Zhang  and
Zhou~\cite{Zhang05} proved that if  the transmission range fulfills the previous
hypothesis, a complete coverage of  a convex area implies connectivity among the
active nodes.\fi

\textcolor{blue}{We  consider a  scenario where  sensors are  deployed in  high
  density to ensure initially a high coverage ratio of the interested area. Each
  sensor  has  a  predefined  sensing  range $R_s$,  an  initial  energy  supply
  (eventually different  from each other)  and is  supposed to be  equipped with
  module for  locating its geographical  positions. All space points  within the
  disk centered at the sensor with the radius of the sensing range is said to be
  covered by this sensor.}

\indent Instead of working with the coverage area, we consider for each sensor a
set of  points called  primary points~\cite{idrees2014coverage}. We  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  of  wireless sensor  node
(centered  at the  the position  $\left(p_x,p_y\right)$) and  its sensing  range
$R_s$,  we define  up to  25 primary  points $X_1$  to $X_{25}$  as described  on
Figure~\ref{fig1}.  The optimal  number  of primary  points  is investigated  in
section~\ref{ch4:sec:04:06}.

The coordinates of the primary points are defined 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 * (\frac{\sqrt{2}}{2})) $\\
$X_7=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
$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 * (0)) $\\
$X_{11}=( p_x + R_s *  (\frac{\sqrt{2}}{2}), p_y + R_s * (0))$\\
$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
  \includegraphics[scale=0.375]{fig26.pdf}
  \label{fig1}
  \caption{Wireless sensor node represented by up to 25~primary points}
\end{figure}

\subsection{Background idea}

The  WSN  area of  interest  is,  at  first,  divided into  regular  homogeneous
subregions  using a  divide-and-conquer algorithm.  Then, 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 and with  high density  over the region.  The regular
subdivision is  made so  that the number  of hops between  any pairs  of sensors
inside a subregion is less than or equal to 3.

As can  be seen  in Figure~\ref{fig2},  our protocol  works in  periods fashion,
where   each   period   is    divided   into   4~phases:   Information~Exchange,
Leader~Election,  Decision, and  Sensing. \textcolor{blue}{Compared  to protocol
  DiLCO described in~\cite{idrees2015distributed},} each sensing phase is itself
divided into $T$ rounds of equal duration and for each round a set of sensors (a
cover  set) is  responsible  for the  sensing  task. In  this  way a  multiround
optimization process is performed  during each period after Information~Exchange
and Leader~Election  phases, in order to  produce $T$ cover sets  that will take
the           mission           of           sensing           for           $T$
rounds. \textcolor{blue}{Algorithm~\ref{alg:MuDiLCO} is  executed by each sensor
  node~$s_j$ (with enough remaining energy) at the beginning of a period.}
\begin{figure}[t!]
\centering \includegraphics[width=125mm]{Modelgeneral.pdf} % 70mm
\caption{The MuDiLCO protocol scheme executed on each node}
\label{fig2}
\end{figure}

\begin{algorithm}[h!]                
  \BlankLine  
  \If{ $RE_j \geq E_{R}$ }{
      \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{LeaderID = Leader election}\;
      \If{$ s_j.ID = LeaderID $}{
        \emph{$s_j.status$ = COMPUTATION}\;
        \emph{$\left\{\left(X_{1,k},\dots,X_{T,k}\right)\right\}_{k \in J}$ =
          Execute Integer Program Algorithm($T,J$)}\;
        \emph{$s_j.status$ = COMMUNICATION}\;
        \emph{Send $ActiveSleep()$ packet to each node $k$ in subregion: a packet \\
          with vector of activity scheduling $(X_{1,k},\dots,X_{T,k})$}\;
        \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}
  
\caption{MuDiLCO($s_j$)}
\label{alg:MuDiLCO}
\end{algorithm}

\textcolor{blue}{As  already   described  in~\cite{idrees2015distributed}},  two
types of packets are used by the proposed protocol:
\begin{enumerate}[(a)] 
\item INFO  packet: such a packet  will be sent by  each sensor node to  all the
  nodes inside a subregion for information exchange.
\item  Active-Sleep  packet: sent  by  the  leader to  all  the  nodes inside  a
  subregion to inform  them to remain Active  or to go Sleep  during the sensing
  phase.
\end{enumerate}

There are five status for each sensor node in the network:
\begin{enumerate}[(a)] 
\item LISTENING: sensor node is waiting for a decision (to be active or not);
\item  COMPUTATION: sensor  node  has been  elected as  leader  and applies  the
  optimization process;
\item ACTIVE: sensor node is taking part in the monitoring of the area;
\item SLEEP: sensor node is turned off to save energy;
\item COMMUNICATION: sensor node is transmitting or receiving packet.
\end{enumerate}

This  protocol minimizes  the  impact of  unexpected node  failure  (not due  to
batteries running out of energy), because it works in periods.  On the one hand,
if a  node failure  is detected before  making the decision,  the node  will not
participate to this  phase, and, on the  other hand, if the  node failure occurs
after  the  decision, the  sensing  task  of  the  network will  be  temporarily
affected: only  during the  period of  sensing until a  new period  starts.  The
duration of the rounds is a  predefined parameter. Round duration should be long
enough to  hide the  system control  overhead and short  enough to  minimize the
negative effects in case of node failures.

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 (Information  Exchange, Leader  Election, and  Decision) are
energy  consuming for some  nodes, even  when they  do not  join the  network to
monitor the area.

At the beginning  of each period, each sensor which  has enough remaining energy
($RE_j$) to be alive during at least  one round ($E_{R}$ is the amount of energy
required    to   be    alive   during    one   round)    sends   (line    3   of
Algorithm~\ref{alg:MuDiLCO})  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 (line 4).

After that, each  node will have information  about all the sensor  nodes in the
subregion.  The  nodes in  the same  subregion will select  (line 5)  a Wireless
Sensor Node Leader (WSNL) 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.

%Each WSNL will solve an integer program to  select which cover
%  sets will be  activated in the following sensing phase  to cover the subregion
%  to which it belongs.  $T$ cover sets will be produced, one for each round. The
%  WSNL will send an Active-Sleep packet to each sensor in the subregion based on
%  the algorithm's results,  indicating if the sensor should be  active or not in
%  each round of the sensing phase.
\subsection{Multiround Optimization model}
\label{mom}

As  shown in  Algorithm~\ref{alg:MuDiLCO}  at  line 8,  the  leader (WNSL)  will
execute an  optimization algorithm  based on  an integer  program to  select the
cover sets to be activated in the following sensing phase to cover the subregion
to which it belongs.   $T$ cover sets will be produced, one  for each round. The
WSNL will send an  Active-Sleep packet to each sensor in  the subregion based on
the algorithm's results (line 10), indicating  if the sensor should be active or
not in each round of the sensing phase.

The integer  program is based on  the model proposed by  \cite{pedraza2006} with
some modifications, where the objective is  to find a maximum number of disjoint
cover sets.  To fulfill 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  binary variables  $X_{t,j}$  to
determine the possibility  of activating sensor $j$ during round  $t$ of a given
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$. Only sensors able to be
alive  during  at  least  one  round   are  involved  in  the  integer  program.
\textcolor{blue}{Note that the proposed integer  program is an extension of that
  formulated  in~\cite{idrees2015distributed},  variables  are  now  indexed  in
  addition with the number of round $t$.}

For a  primary point  $p$, let $\alpha_{j,p}$  denote the indicator  function of
whether the point $p$ is covered, that is:
\begin{equation}
\alpha_{j,p} = \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$ during
round $t$ is equal to $\sum_{j \in J} \alpha_{j,p} * X_{t,j}$ where:
\begin{equation}
X_{t,j} = \left \{ 
\begin{array}{l l}
  1& \mbox{if sensor $j$  is active during round $t$,} \\
  0 &  \mbox{otherwise.}\\
\end{array} \right.
%\label{eq11} 
\end{equation}
We define the Overcoverage variable $\Theta_{t,p}$ as:
\begin{equation}
 \Theta_{t,p} = \left \{ 
\begin{array}{l l}
  0 & \mbox{if the primary point $p$}\\
    & \mbox{is not covered during round $t$,}\\
  \left( \sum_{j \in J} \alpha_{jp} * X_{t,j} \right)- 1 & \mbox{otherwise.}\\
\end{array} \right.
\label{eq13} 
\end{equation}
More  precisely, $\Theta_{t,p}$  represents the  number of  active  sensor nodes
minus  one  that  cover  the  primary  point $p$  during  round  $t$.   The
Undercoverage variable  $U_{t,p}$ of the primary  point $p$ during  round $t$ is
defined by:
\begin{equation}
U_{t,p} = \left \{ 
\begin{array}{l l}
  1 &\mbox{if the primary point $p$ is not covered during round $t$,} \\
  0 & \mbox{otherwise.}\\
\end{array} \right.
\label{eq14} 
\end{equation}

Our coverage optimization problem can then be formulated as follows:
\begin{equation}
 \min \sum_{t=1}^{T} \sum_{p=1}^{|P|} \left(W_{\theta}* \Theta_{t,p} + W_{U} * U_{t,p}  \right)  \label{eq15} 
\end{equation}

Subject to
\begin{equation}
  \sum_{j=1}^{|J|} \alpha_{j,p} * X_{t,j}   = \Theta_{t,p} - U_{t,p} + 1 \label{eq16} \hspace{6 mm} \forall p \in P, t = 1,\dots,T
\end{equation}

\begin{equation}
  \sum_{t=1}^{T}  X_{t,j}   \leq  \floor*{RE_{j}/E_{R}} \hspace{10 mm}\forall j \in J\hspace{6 mm} 
  \label{eq144} 
\end{equation}

\begin{equation}
X_{t,j} \in \lbrace0,1\rbrace,   \hspace{10 mm} \forall j \in J, t = 1,\dots,T \label{eq17} 
\end{equation}

\begin{equation}
U_{t,p} \in \lbrace0,1\rbrace, \hspace{10 mm}\forall p \in P, t = 1,\dots,T  \label{eq18} 
\end{equation}

\begin{equation}
 \Theta_{t,p} \geq 0 \hspace{10 mm}\forall p \in P, t = 1,\dots,T \label{eq178}
\end{equation}

\begin{itemize}
\item $X_{t,j}$:  indicates whether  or not the  sensor $j$ is  actively sensing
  during round $t$ (1 if yes and 0 if not);
\item $\Theta_{t,p}$ - {\it overcoverage}:  the number of sensors minus one that
  are covering the primary point $p$ during round $t$;
\item  $U_{t,p}$ -  {\it undercoverage}:  indicates whether  or not  the primary
  point $p$  is being covered during round $t$ (1  if not covered  and 0 if
  covered).
\end{itemize}

The first group  of constraints indicates that some primary  point $p$ should be
covered by at least  one sensor and, if it is not  always the case, overcoverage
and undercoverage variables  help balancing the restriction  equations by taking
positive values. The constraint  given by equation~(\ref{eq144}) guarantees that
the sensor has enough energy ($RE_j$  corresponds to its remaining energy) to be
alive during  the selected rounds knowing  that $E_{R}$ is the  amount of energy
required to be alive during one round.

There are  two main  objectives.  First,  we limit  the overcoverage  of primary
points in order to activate a minimum  number of sensors.  Second we prevent the
absence  of  monitoring  on  some  parts of  the  subregion  by  minimizing  the
undercoverage.  The weights  $W_\theta$ and $W_U$ must be properly  chosen so as
to guarantee  that the maximum number  of points are covered  during each round.
In our simulations,  priority is given to the coverage  by choosing $W_{U}$ very
large compared to $W_{\theta}$.

The size of the problem depends on  the number of variables and constraints. The
number of variables  is linked to the  number of alive sensors  $A \subseteq J$,
the  number of  rounds $T$,  and the  number of  primary points  $P$.  Thus  the
integer program contains  $A*T$ variables of type  $X_{t,j}$, $P*T$ overcoverage
variables and $P*T$ undercoverage variables.  The number of constraints is equal
to $P*T$ (for constraints (\ref{eq16})) $+$ $A$ (for constraints (\ref{eq144})).

\iffalse
\subsection{Sensing phase}

The sensing phase consists of $T$ rounds. Each sensor node in the subregion will
receive an Active-Sleep packet from WSNL, informing it to stay awake or to go to
sleep for each  round of the sensing  phase.  Algorithm~\ref{alg:MuDiLCO}, which
will  be executed  by  each sensor  node~$s_j$  at the  beginning  of a  period,
explains how the Active-Sleep packet is obtained.
\fi

\section{Experimental framework}
\label{exp}

\subsection{Simulation setup}

We  conducted  a series  of  simulations  to  evaluate  the efficiency  and  the
relevance  of  our   approach,  using  the  discrete   event  simulator  OMNeT++
\cite{varga}.  The  simulation parameters are summarized  in Table~\ref{table3}.
Each experiment for a network is run over 25~different random topologies and the
results presented  hereafter are  the average  of these  25 runs.   We performed
simulations for five  different densities varying from 50  to 250~nodes deployed
over a  $50 \times 25~m^2  $ sensing field.   More precisely, the  deployment is
controlled at  a coarse  scale in order  to ensure that  the deployed  nodes can
cover the sensing field with the given sensing range.

\begin{table}[ht]
\caption{Relevant parameters for network initializing.}
\centering
\begin{tabular}{c|c}
  \hline
Parameter & Value  \\ [0.5ex]
\hline
Sensing field size & $(50 \times 25)~m^2 $   \\
Network size &  50, 100, 150, 200 and 250~nodes   \\
Initial energy  & 500-700~joules  \\  
Sensing time for one round & 60 Minutes \\
$E_{R}$ & 36 Joules\\
$R_s$ & 5~m   \\     
$W_{\theta}$ & 1   \\
$W_{U}$ & $|P|^2$ \\
\end{tabular}
\label{table3}
\end{table}

Our protocol  is declined into  four versions: MuDiLCO-1,  MuDiLCO-3, MuDiLCO-5,
and  MuDiLCO-7, corresponding  respectively to  $T=1,3,5,7$ ($T$  the number  of
rounds in one sensing period). Since the time resolution may be prohibitive when
the size of  the problem increases, a  time limit threshold has  been fixed when
solving large  instances. In these cases,  the solver returns the  best solution
found, which  is not necessary  the optimal one. In  practice, we only  set time
limit values for  $T=5$ and $T=7$.  In  fact, for $T=5$ we limited  the time for
250~nodes,  whereas for  $T=7$  it  was for  the  three  largest network  sizes.
Therefore we  used the  following values  (in second):  0.03 for  250~nodes when
$T=5$, while for $T=7$ we chose 0.03,  0.06, and 0.08 for respectively 150, 200,
and 250~nodes.  These time limit thresholds have been set empirically. The basic
idea is to consider the average execution  time to solve the integer programs to
optimality for 100 nodes  and then to adjust the time  linearly according to the
increasing  network size.   After that,  this  threshold value  is increased  if
necessary so that the  solver is able to deliver a  feasible solution within the
time limit. In  fact, selecting the optimal  values for the time  limits will be
investigated in the future.

 In the  following, we will make  comparisons with two other  methods. The first
 method,  called DESK  and proposed  by \cite{ChinhVu},  is a  fully distributed
 coverage  algorithm.   The  second method,  called  GAF~\cite{xu2001geography},
 consists in dividing the region into fixed squares.  During the decision phase,
 in each square, one  sensor is then chosen to remain  active during the sensing
 phase time.

Some preliminary experiments were performed to study the choice of the number of
subregions  which subdivides  the sensing  field, considering  different network
sizes. They show that as the number of subregions increases, so does the network
lifetime. Moreover,  it makes  the MuDiLCO protocol  more robust  against random
network  disconnection due  to node  failures.  However,  too many  subdivisions
reduce the advantage  of the optimization.  In fact, there  is a balance between
the benefit from the optimization and the  execution time needed to solve it. In
the following  we have  set the number  of subregions  to~16 \textcolor{blue}{as
  recommended in~\cite{idrees2015distributed}}.

\subsection{Energy model}
\textcolor{blue}{The      energy     consumption      model     is      detailed
  in~\cite{raghunathan2002energy}.   It  is   based   on   the  model   proposed
  by~\cite{ChinhVu}. We refer to the sensor  node Medusa~II which uses an Atmels
  AVR ATmega103L  microcontroller~\cite{raghunathan2002energy} to  use numerical
  values.}   \textcolor{red}{Est-ce qu'il  faut en  ecrire plus  et redonner  le
  tableau de valeurs?}

\iffalse
\subsection{Energy model}

We  use an  energy consumption  model  proposed by~\cite{ChinhVu}  and based  on
\cite{raghunathan2002energy} with slight  modifications.  The energy consumption
for  sending/receiving the packets  is added,  whereas the  part related  to the
sensing range is removed because we consider a fixed sensing range.

For our  energy consumption model, we  refer to the sensor  node Medusa~II which
uses an Atmels  AVR ATmega103L microcontroller~\cite{raghunathan2002energy}. The
typical  architecture  of a  sensor  is composed  of  four  subsystems: the  MCU
subsystem which is capable of computation, communication subsystem (radio) which
is responsible  for transmitting/receiving messages, the  sensing subsystem that
collects  data, and  the  power supply  which  powers the  complete sensor  node
\cite{raghunathan2002energy}. Each  of the first three subsystems  can be turned
on or  off depending on  the current status  of the sensor.   Energy consumption
(expressed in  milliWatt per second) for  the different status of  the sensor is
summarized in Table~\ref{table4}.

\begin{table}[ht]
\caption{The Energy Consumption Model}
\centering
\begin{tabular}{|c|c|c|c|c|}
  \hline
Sensor status & MCU & Radio & Sensing & Power (mW) \\ [0.5ex]
\hline
LISTENING & on & on & on & 20.05 \\
\hline
ACTIVE & on & off & on & 9.72 \\
\hline
SLEEP & off & off & off & 0.02 \\
\hline
COMPUTATION & on & on & on & 26.83 \\
\hline
\end{tabular}

\label{table4}
\end{table}

For the sake of simplicity we ignore the  energy needed to turn on the radio, to
start up the sensor node, to move from one status to another, etc.
Thus, when a sensor becomes active (i.e.,  it has already chosen its status), it
can turn its radio  off to save battery.  MuDiLCO uses two  types of packets for
communication. The size of the INFO  packet and Active-Sleep packet are 112~bits
and 24~bits  respectively.  The value  of energy  spent to send  a 1-bit-content
message is  obtained by using  the equation in  ~\cite{raghunathan2002energy} to
calculate the  energy cost  for transmitting  messages and  we propose  the same
value for receiving  the packets. The energy  needed to send or  receive a 1-bit
packet is equal to 0.2575~mW.

The initial energy of each node is  randomly set in the interval $[500;700]$.  A
sensor node will  not participate in the  next round if its  remaining energy is
less than  $E_{R}=36~\mbox{Joules}$, the minimum  energy needed for the  node to
stay alive  during one round.  This  value has been computed  by multiplying the
energy consumed in  active state (9.72 mW)  by the time in second  for one round
(3600 seconds).   According to the interval  of initial energy, a  sensor may be
alive during at most 20 rounds.
\fi

\subsection{Metrics}

\textcolor{blue}{To evaluate  our approach  we consider the  performance metrics
  detailed in~\cite{idrees2015distributed},  which are: Coverage  Ratio, Network
  Lifetime  and  Energy  Consumption.   Compared to  the  previous  definitions,
  formulations of  Coverage Ratio and  Energy Consumption are enriched  with the
  index of round $t$.}

\begin{enumerate}[i]
  
\item {{\bf Coverage  Ratio (CR)}:} the coverage ratio measures  how much of the
  area  of  a sensor  field  is  covered. In  our  case,  the sensing  field  is
  represented as  a connected grid  of points  and we use  each grid point  as a
  sample point to compute the coverage. The coverage ratio can be calculated by:
\begin{equation*}
\scriptsize
\mbox{CR}(\%) = \frac{\mbox{$n^t$}}{\mbox{$N$}} \times 100,
\end{equation*}
where $n^t$ is  the number of covered  grid points by the active  sensors of all
subregions during round  $t$ in the current  sensing phase and $N$  is the total
number of grid points in the sensing field of the network. In our simulations $N
= 51 \times 26 = 1326$ grid points.

\item{{\bf Number  of Active Sensors Ratio  (ASR)}:} it is important  to have as
  few  active  nodes  as possible  in  each  round,  in  order to  minimize  the
  communication overhead and maximize the  network lifetime.  The Active Sensors
  Ratio is defined as follows:
\begin{equation*}
\scriptsize  \mbox{ASR}(\%) = \frac{\sum\limits_{r=1}^R
  \mbox{$A_r^t$}}{\mbox{$|J|$}} \times 100,
\end{equation*}
where $A_r^t$ is the number of  active sensors in the subregion $r$ during round
$t$ in the  current sensing phase, $|J|$  is the total number of  sensors in the
network, and $R$ is the total number of subregions in the network.

\item {{\bf Network Lifetime}:} we define the network lifetime as the time until
  the  coverage  ratio  drops  below  a  predefined  threshold.   We  denote  by
  $Lifetime_{95}$ (respectively $Lifetime_{50}$) the amount of time during which
  the network  can satisfy  an area coverage  greater than  $95\%$ (respectively
  $50\%$). We assume that the network is alive until all nodes have been drained
  of  their  energy   or  the  sensor  network   becomes  disconnected.  Network
  connectivity is important  because an active sensor  node without connectivity
  towards a  base station cannot  transmit information on  an event in  the area
  that it monitors.

\item {{\bf  Energy Consumption  (EC)}:} the average  energy consumption  can be
  seen as the total energy consumed by the sensors during the $Lifetime_{95}$ or
  $Lifetime_{50}$  divided by  the  number of  rounds.  EC  can  be computed  as
  follows:

  \begin{equation*}
    \scriptsize
    \mbox{EC} = \frac{\sum\limits_{m=1}^{M} \left[ \left( E^{\mbox{com}}_m+E^{\mbox{list}}_m+E^{\mbox{comp}}_m \right) +\sum\limits_{t=1}^{T_m} \left( E^{a}_t+E^{s}_t \right) \right]}{\sum\limits_{m=1}^{M} T_m},
  \end{equation*}

where  $M$ is  the  number  of periods  and  $T_m$ the  number  of  rounds in  a
period~$m$, both  during $Lifetime_{95}$  or $Lifetime_{50}$.  The  total energy
consumed by the  sensors (EC) comes through taking into  consideration four main
energy  factors.   The  first  one  ,  denoted  $E^{\scriptsize  \mbox{com}}_m$,
represents  the  energy  consumption  spent   by  all  the  nodes  for  wireless
communications  during period  $m$.  $E^{\scriptsize  \mbox{list}}_m$, the  next
factor, corresponds  to the energy consumed  by the sensors in  LISTENING status
before  receiving   the  decision  to  go   active  or  sleep  in   period  $m$.
$E^{\scriptsize \mbox{comp}}_m$  refers to the  energy needed by all  the leader
nodes to solve the integer program during a period. Finally, $E^a_t$ and $E^s_t$
indicate the energy consumed by the whole network in round $t$.

%\item {Network Lifetime:} we  have defined the network  lifetime as the  time until all
%nodes  have  been drained  of  their  energy  or each  sensor  network monitoring  an area has become  disconnected.
\end{enumerate}

\iffalse
\begin{enumerate}
 \setcounter{5}
\item {{\bf  Execution Time}:}  a sensor node  has limited energy  resources and
  computing power, therefore it is important that the proposed algorithm has the
  shortest possible execution  time. The energy of a sensor  node must be mainly
  used for the sensing phase, not for the pre-sensing ones.
  
\item {{\bf Stopped simulation runs}:} a simulation ends when the sensor network
  becomes disconnected (some nodes are dead and are not able to send information
  to the base station). We report the number of simulations that are stopped due
  to network disconnections and for which round it occurs.

\end{enumerate}
\fi

\section{Experimental results and analysis}
\label{analysis}

\subsection{Performance analysis for different number of primary points}
\label{ch4:sec:04:06}

In this section,  we study the performance of MuDiLCO-1  approach (with only one
round  as  in~\cite{idrees2015distributed})  for different  numbers  of  primary
points. The  objective of this  comparison is to  select the suitable  number of
primary points to be used by  a MuDiLCO protocol.  In this comparison, MuDiLCO-1
protocol is used  with five primary point models, each  model corresponding to a
number of primary  points, which are called Model-5 (it  uses 5 primary points),
Model-9, Model-13,  Model-17, and  Model-21. \textcolor{blue}{Note  that results
  presented in~\cite{idrees2015distributed}  correspond to Model-13  (13 primary
  points)}.

\subsubsection{Coverage ratio} 

Figure~\ref{Figures/ch4/R2/CR} shows the average coverage ratio for 150 deployed
nodes.  As can be seen, at the beginning the models which use a larger number of
primary points provide slightly better coverage  ratios, but latter they are the
worst.   Moreover, when  the number  of  periods increases,  the coverage  ratio
produced by all models decrease due to  dead nodes.  However, Model-5 is the one
with the slowest decrease due to lower  numbers of active sensors in the earlier
periods.  Overall  this model is  slightly more  efficient than the  other ones,
because it offers a good coverage ratio for a larger number of periods.

\begin{figure}[t!]
\centering
 \includegraphics[scale=0.5] {R2/CR.pdf} 
\caption{Coverage ratio for 150 deployed nodes}
\label{Figures/ch4/R2/CR}
\end{figure} 

\subsubsection{Network lifetime}

Finally, we study the  effect of increasing the number of  primary points on the
lifetime of  the network.  As highlighted  by Figures~\ref{Figures/ch4/R2/LT}(a)
and \ref{Figures/ch4/R2/LT}(b),  the network  lifetime obviously  increases when
the  size of  the network  increases, with  Model-5 which  leads to  the largest
lifetime improvement.

\begin{figure}[h!]
\centering
\centering
\includegraphics[scale=0.5]{R2/LT95.pdf}\\~ ~ ~ ~ ~(a) \\

\includegraphics[scale=0.5]{R2/LT50.pdf}\\~ ~ ~ ~ ~(b)

\caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$}
  \label{Figures/ch4/R2/LT}
\end{figure}

Comparison shows that Model-5, which uses  less number of primary points, is the
best one because it is less energy  consuming during the network lifetime. It is
also  the better  one  from the  point  of  view of  coverage  ratio, as  stated
before. Therefore, we have chosen the model with five primary points for all the
experiments presented thereafter.

\subsection{Coverage ratio} 

Figure~\ref{fig3} shows  the average coverage  ratio for 150 deployed  nodes. We
can notice  that for the  first 30~rounds both DESK  and GAF provide  a coverage
which is a little  bit better than the one of MuDiLCO.  This  is due to the fact
that, in comparison with MuDiLCO which  uses optimization to put in SLEEP status
redundant sensors,  more sensor  nodes remain  active with DESK  and GAF.   As a
consequence,  when the  number  of rounds  increases, a  larger  number of  node
failures can be observed in DESK and  GAF, resulting in a faster decrease of the
coverage ratio.  Furthermore,  our protocol allows to maintain  a coverage ratio
greater than  50\% for far more  rounds.  Overall, the proposed  sensor activity
scheduling based on optimization in  MuDiLCO maintains higher coverage ratios of
the area of interest  for a larger number of rounds. It  also means that MuDiLCO
saves more energy,  with less dead nodes,  at most for several  rounds, and thus
should extend  the network lifetime.  MuDiLCO-7  seems to have most  of the time
the best coverage ratio up to round~80, after that MuDiLCO-5 is slightly better.

\begin{figure}[ht!]
\centering
 \includegraphics[scale=0.5] {F/CR.pdf} 
\caption{Average coverage ratio for 150 deployed nodes}
\label{fig3}
\end{figure} 

\subsection{Active sensors ratio} 

It is crucial to have as few active nodes as possible in each round, in order to
minimize    the    communication    overhead   and    maximize    the    network
lifetime. Figure~\ref{fig4}  presents the active  sensor ratio for  150 deployed
nodes all along the network lifetime. It appears that up to round thirteen, DESK
and GAF have  respectively 37.6\% and 44.8\% of nodes  in ACTIVE status, whereas
MuDiLCO clearly outperforms  them with only 24.8\% of  active nodes.  Obviously,
in that case DESK and GAF have less active nodes, since they have activated many
nodes at the beginning. Anyway, MuDiLCO  activates the available nodes in a more
efficient manner.

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{F/ASR.pdf}  
\caption{Active sensors ratio for 150 deployed nodes}
\label{fig4}
\end{figure} 

\subsection{Stopped simulation runs}

A simulation ends  when the sensor network becomes disconnected  (some nodes are
dead and are not  able to send information to the base  station).  We report the
number of  simulations that are  stopped due  to network disconnections  and for
which round it  occurs.  Figure~\ref{fig6} reports the  cumulative percentage of
stopped simulations  runs per round for  150 deployed nodes.  This  figure gives
the  break  point  for  each  method.  DESK  stops  first,  after  approximately
45~rounds, because it consumes  the more energy by turning on  a large number of
redundant nodes during the sensing phase. GAF stops secondly for the same reason
than DESK.  Let us emphasize that the  simulation continues as long as a network
in a subregion is still connected.

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{F/SR.pdf} 
\caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes}
\label{fig6}
\end{figure} 

\subsection{Energy consumption} \label{subsec:EC}

We  measure  the  energy  consumed  by the  sensors  during  the  communication,
listening, computation, active, and sleep status for different network densities
and   compare   it   with   the  two   other   methods.    Figures~\ref{fig7}(a)
and~\ref{fig7}(b)  illustrate  the  energy  consumption,  considering  different
network sizes, for $Lifetime_{95}$ and $Lifetime_{50}$.

\begin{figure}[h!]
  \centering
  \begin{tabular}{cl}
    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC95.pdf}} & (a) \\
    \verb+ + \\
    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC50.pdf}} & (b)
  \end{tabular}
  \caption{Energy consumption for (a) $Lifetime_{95}$ and 
    (b) $Lifetime_{50}$}
  \label{fig7}
\end{figure} 

The  results  show  that  MuDiLCO  is  the  most  competitive  from  the  energy
consumption point of view.  The other  approaches have a high energy consumption
due to  activating a  larger number  of redundant  nodes as  well as  the energy
consumed during the different status of the sensor node.

Energy consumption  increases with the  size of the  networks and the  number of
rounds.  The curve Unlimited-MuDiLCO-7 shows  that energy consumption due to the
time spent to optimally solve the integer program increases drastically with the
size  of the  network. When  the resolution  time is  limited for  large network
sizes, the  energy consumption remains  of the  same order whatever  the MuDiLCO
version. As can be seen with MuDiLCO-7.

\subsection{Execution time}
\label{et}

We observe  the impact of the  network size and of  the number of rounds  on the
computation  time.   Figure~\ref{fig77} gives  the  average  execution times  in
seconds  (needed to  solve the  optimization  problem) for  different values  of
$T$. The  modeling language  for Mathematical Programming  (AMPL)~\cite{AMPL} is
employed to  generate the Mixed  Integer Linear  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.  The original  execution time is  computed on  a laptop
DELL  with Intel  Core~i3~2370~M  (2.4 GHz)  processor (2  cores)  and the  MIPS
(Million Instructions Per Second) rate equal to 35330. To be consistent with the
use of a  sensor node with Atmels  AVR ATmega103L microcontroller (6  MHz) and a
MIPS rate equal to 6 to run the optimization resolution, this time is multiplied
by 2944.2  $\left( \frac{35330}{2} \times  \frac{1}{6} \right)$ and  reported on
Figure~\ref{fig77} for different network sizes.

\begin{figure}[ht!]
\centering
\includegraphics[scale=0.5]{F/T.pdf}  
\caption{Execution Time (in seconds)}
\label{fig77}
\end{figure} 

As expected,  the execution time increases  with the number of  rounds $T$ taken
into account to  schedule the sensing phase. Obviously, the  number of variables
and  constraints of  the integer  program increases  with $T$,  as explained  in
section~\ref{mom}, the times obtained for $T=1,3$  or $5$ seem bearable. But for
$T=7$, without any limitation of the  time, they become quickly unsuitable for a
sensor node, especially  when the sensor network size  increases as demonstrated
by  Unlimited-MuDiLCO-7.   Notice  that  for  250 nodes,  we  also  limited  the
execution   time  for   $T=5$,  otherwise   the  execution   time,  denoted   by
Unlimited-MuDiLCO-5, is  also above MuDiLCO-7.  On  the one hand, a  large value
for  $T$ permits  to reduce  the energy-overhead  due to  the three  pre-sensing
phases, on  the other  hand a  leader node  may waste  a considerable  amount of
energy to solve the optimization problem. Thus, limiting the time resolution for
large instances  allows to reduce the  energy consumption without any  impact on
the coverage quality.

\subsection{Network lifetime}

The next  two figures,  Figures~\ref{fig8}(a) and \ref{fig8}(b),  illustrate the
network lifetime  for different network sizes,  respectively for $Lifetime_{95}$
and  $Lifetime_{50}$.  Both  figures show  that the  network lifetime  increases
together with the  number of sensor nodes, whatever the  protocol, thanks to the
node  density  which results  in  more  and more  redundant  nodes  that can  be
deactivated and thus save energy.  Compared to the other approaches, our MuDiLCO
protocol  maximizes the  lifetime of  the network.   In particular  the gain  in
lifetime for a coverage  over 95\%, and a network of  250~nodes, is greater than
43\% when switching from GAF to MuDiLCO-5.
%The lower performance that can be observed  for MuDiLCO-7 in case
%of  $Lifetime_{95}$  with  large  wireless  sensor  networks  results  from  the
%difficulty  of the optimization  problem to  be solved  by the  integer program.
%This  point was  already noticed  in subsection  \ref{subsec:EC} devoted  to the
%energy consumption,  since network lifetime and energy  consumption are directly
%linked.
Overall, it  clearly appears that computing  a scheduling for several  rounds is
possible  and  relevant,  providing  that   the  execution  time  to  solve  the
optimization problem  for large instances  is limited.  Notice that  rather than
limiting the execution time, similar results  might be obtained by replacing the
computation of the exact  solution with the finding of a  suboptimal one using a
heuristic  approach. For  our  simulation setup  and  considering the  different
metrics, MuDiLCO-5 seems to be the best suited method compared to MuDiLCO-7.

\begin{figure}[t!]
  \centering
  \begin{tabular}{cl}
    \parbox{9.5cm}{\includegraphics[scale=0.5125]{F/LT95.pdf}} & (a) \\
    \verb+ + \\
    \parbox{9.5cm}{\includegraphics[scale=0.5125]{F/LT50.pdf}} & (b)
  \end{tabular}
  \caption{Network lifetime for (a) $Lifetime_{95}$ and 
    (b) $Lifetime_{50}$}
  \label{fig8}
\end{figure} 

\section{Conclusion and future works}
\label{sec:conclusion}

We have addressed  the problem of the coverage and  of the lifetime optimization
in wireless sensor networks.   This is a key issue as  sensor nodes have limited
resources in terms of memory, energy, and computational power. To cope with this
problem,  the field  of sensing  is divided  into smaller  subregions using  the
concept  of divide-and-conquer  method, and  then  we propose  a protocol  which
optimizes coverage and  lifetime performances in each  subregion.  Our protocol,
called MuDiLCO (Multiround Distributed  Lifetime Coverage Optimization) combines
two  efficient   techniques:  network   leader  election  and   sensor  activity
scheduling. The  activity scheduling in  each subregion works in  periods, where
each  period consists  of four  phases:  (i) Information  Exchange, (ii)  Leader
Election, (iii)  Decision Phase  to plan  the activity of  the sensors  over $T$
rounds, (iv) Sensing Phase itself divided into $T$ rounds.

Simulations results  show the  relevance of  the proposed  protocol in  terms of
lifetime, coverage  ratio, active  sensors ratio, energy  consumption, execution
time. Indeed,  when dealing with  large wireless sensor networks,  a distributed
approach, like the one  we propose, allows to reduce the  difficulty of a single
global optimization problem by partitioning it in many smaller problems, one per
subregion, that can  be solved more easily. Furthermore, results  also show that
to plan the activity of sensors for large network sizes, an approach to obtain a
near optimal solution  is needed.  Indeed, an exact resolution  of the resulting
optimization  problem leads  to prohibitive  computation  times and  thus to  an
excessive energy consumption.

%In  future work, we plan  to study and propose adjustable sensing range coverage optimization protocol, which computes  all active sensor schedules in one time, by using
%optimization  methods. This protocol can prolong the network lifetime by minimizing the number of the active sensor nodes near the borders by optimizing the sensing range of sensor nodes.
% use section* for acknowledgement

\section*{Acknowledgment}
This  work   is  partially  funded   by  the  Labex  ACTION   program  (contract
ANR-11-LABX-01-01). Ali Kadhum  IDREES would like to  gratefully acknowledge the
University of  Babylon - Iraq for  the financial support and  Campus France (The
French  national agency  for the  promotion of  higher education,  international
student services, and  international mobility) for the support  received when he
was Ph.D. student in France.
%, and the University ofFranche-Comt\'e - France for all the support in France.




%% \linenumbers

%% main text
%\section{}
%\label{}

%% The Appendices part is started with the command \appendix;
%% appendix sections are then done as normal sections
%% \appendix

%% \section{}
%% \label{}

%% If you have bibdatabase file and want bibtex to generate the
%% bibitems, please use
%%
%%  \bibliographystyle{elsarticle-num} 
%%  \bibliography{<your bibdatabase>}
%% else use the following coding to input the bibitems directly in the
%% TeX file.

\bibliographystyle{elsarticle-num} 
\bibliography{article}
  
\end{document}

%%\bibitem{}

%\end{thebibliography}
%\end{document}
\endinput
%%
%% End of file `elsarticle-template-num.tex'.