[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{Ad Hoc Networks}

\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,  UMR  6174  CNRS,   \\  University  Bourgogne  Franche-Comt\'e,
      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.   \textcolor{blue}{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 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.   \textcolor{blue}{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}.
\textcolor{blue}{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 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{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.

The MuDiLCO protocol (for  Multiround Distributed Lifetime Coverage Optimization
protocol) presented  in this paper  is an  extension of the  approach introduced
in~\cite{idrees2014coverage}.   In~\cite{idrees2014coverage},  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. Compared to our previous paper, in this one we study the
possibility of dividing  the sensing phase into multiple rounds  and we also add
an  improved  model of  energy  consumption  to  assess  the efficiency  of  our
approach. In fact, in this paper we make a multiround optimization, while it was
a single round  optimization in our previous work.  \textcolor{blue}{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}.


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

\subsection{Assumptions}

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.

\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 it's  sensing range
$R_s$,  we define  up to  25 primary  points $X_1$  to $X_{25}$  as decribed  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}

\textcolor{blue}{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.   Each  sensing  phase may  be  itself
divided into $T$ rounds \textcolor{blue} {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.
\begin{figure}[t!]
\centering \includegraphics[width=125mm]{Modelgeneral.pdf} % 70mm
\caption{The MuDiLCO protocol scheme executed on each node}
\label{fig2}
\end{figure} 

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.   \textcolor{blue}{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.

We define two types of packets that will be 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}

Below, we describe each phase in more details.

\subsection{Information Exchange Phase}

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.

\subsection{Leader Election phase}

This step  consists in 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 period.  All
the sensor  nodes cooperate to  elect a 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.

\subsection{Decision phase}

Each WSNL will  \textcolor{blue}{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.}

As shown in Algorithm~\ref{alg:MuDiLCO}, the leader will execute an optimization
algorithm based on an integer program. 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.

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_{tj} \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}$.

\textcolor{blue}{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})).}

\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.

\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}

\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}

\textcolor{blue}{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 consists
  in considering  the average execution  time to  solve the integer  programs to
  optimality, then in  dividing this average time by three  to set the threshold
  value.  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 full  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.

\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.

\subsection{Metrics}

To evaluate our approach we consider the following performance metrics:

\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.

\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}

\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  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.

\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 thirty 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.  \textcolor{blue}{MuDiLCO-7 seems  to have
  most of the  time the best coverage  ratio up to round~80,  after 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}

Figure~\ref{fig6} reports the cumulative  percentage of stopped simulations runs
per round  for 150  deployed nodes.  This figure gives  the breakpoint  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.

% TO BE CONTINUED
\textcolor{blue}{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 solve the  integer program to optimality
  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.}


\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 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. The times obtained for $T=1,3$
or $5$ seem bearable, but for $T=7$ they become quickly unsuitable for a sensor
node, especially when  the sensor network size increases.   Again, we can notice
that if we want  to schedule the nodes activities for a  large number of rounds,
we need to choose a relevant number of subregions in order to avoid a complicated
and cumbersome optimization.  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.

%While MuDiLCO-1, 3, and 5 solves the optimization process with suitable execution times to be used on wireless sensor network because it distributed on larger number of small subregions as well as it is used acceptable number of round(s) T.  We think that in distributed fashion the solving of the optimization problem to produce T rounds in a subregion can be tackled by sensor nodes. Overall, to be able to deal with very large networks, a distributed method is clearly required.

\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\% is greater than 38\%  when switching from GAF
to MuDiLCO-3.  The  slight decrease 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. 
%\textcolor{red}{As can be seen in these figures, the lifetime increases with the size of the network, and it is clearly largest for the MuDiLCO
%and the GA-MuDiLCO protocols. GA-MuDiLCO prolongs the network lifetime obviously in comparison with both DESK and GAF, as well as the MuDiLCO-7 version for $lifetime_{95}$.  However, comparison shows that MuDiLCO protocol and GA-MuDiLCO protocol, which use distributed optimization over the subregions are the best ones because they are robust to network disconnection during the network lifetime as well as they consume less energy in comparison with other approaches.}
\begin{figure}[t!]
  \centering
  \begin{tabular}{cl}
    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/LT95.pdf}} & (a) \\
    \verb+ + \\
    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/LT50.pdf}} & (b)
  \end{tabular}
  \caption{Network lifetime for (a) $Lifetime_{95}$ and 
    (b) $Lifetime_{50}$}
  \label{fig8}
\end{figure} 

% By choosing the best suited nodes, for each round, by optimizing the coverage and lifetime of the network to cover the area of interest with a maximum number rounds and by letting the other nodes sleep in order to be used later in next rounds, our MuDiLCO protocol efficiently prolonges the network lifetime. 

%In Figure~\ref{fig8}, Comparison shows that our MuDiLCO protocol, which are used distributed optimization on the subregions with the ability of producing T rounds, is the best one because it is robust to network disconnection during the network lifetime as well as it consume less energy in comparison with other approaches. It also means that distributing the protocol in each sensor node and subdividing the sensing field into many subregions, which are managed independently and simultaneously, is the most relevant way to maximize the lifetime of a network.


%We see that our MuDiLCO-7 protocol results in execution times that quickly become unsuitable for a sensor network as well as the energy consumption seems to be huge because it used a larger number of rounds T during performing the optimization decision in the subregions, which is led to decrease the network lifetime. On the other side, our MuDiLCO-1, 3, and 5 protocol seems to be more efficient in comparison with other approaches because they are prolonged the lifetime of the network more than DESK and GAF.


\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.
%,  where the challenges
%include how to select the  most efficient leader in each subregion and
%the best cover sets %of active nodes that will optimize the network lifetime
%while taking the responsibility of covering the corresponding
%subregion using more than one cover set during the sensing phase. 
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. Nevertheless, results also show that
it is not possible to plan the activity of sensors over too many rounds, because
the resulting optimization problem leads to too high resolution 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).
As a Ph.D.  student, Ali Kadhum IDREES would like to gratefully acknowledge the
University  of Babylon  - Iraq  for the  financial support,  Campus  France (The
French  national agency  for the  promotion of  higher  education, international
student   services,  and   international  mobility).%,   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'.