X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/JournalMultiPeriods.git/blobdiff_plain/1fe3b22ea7e88b87e651993466045645f755624d..5233a5d1825cb9b7d339cd22c7e752f17bb24572:/article.tex

diff --git a/article.tex b/article.tex
index a4752b1..c729d58 100644
--- a/article.tex
+++ b/article.tex
@@ -117,24 +117,24 @@ Optimization, Scheduling, Distributed Computation.
  
 \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
+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
+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,
+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
+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
+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 multirounds scheduling.
+we concentrate  on the area coverage  problem, with the  objective of maximizing
+the network lifetime by using an optimized multiround scheduling.
 
 % One of the major scientific research challenges in WSNs, which are addressed by a large number of literature during the last few years is to design energy efficient approaches for coverage and connectivity in WSNs~\cite{conti2014mobile}. The coverage problem is one  of the
 %fundamental challenges in WSNs~\cite{Nayak04} that consists in monitoring efficiently and continuously
@@ -177,15 +177,15 @@ algorithms in WSNs according to several design choices:
 \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  coverage  and  connected
-  coverage.
+\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.
 % The independency in the cover set (i.e. whether the cover sets are disjoint or non-disjoint) \cite{zorbas2010solving} is another design choice that can be added to the above list.
 
-\subsection{Centralized Approaches}
+\subsection{Centralized approaches}
+
 The major approach  is to divide/organize the sensors into  a suitable number of
 set covers where  each set completely covers an interest  region and to activate
 these set covers successively.  The centralized algorithms always provide nearly
@@ -199,23 +199,20 @@ suffer from the scalability problem, making them less competitive as the network
 size increases.
 
 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
+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 less reliable because a sensor may be
-involved   in   more  than   one   cover   sets. For instance, the proposed work in ~\cite{cardei2005energy, berman04}    
-
+scheduling  policies are less  resilient and  reliable because  a sensor  may be
+involved in more than one cover sets.
+%For instance, the proposed work in ~\cite{cardei2005energy, berman04}    
 
-
-
-In~\cite{yang2014maximum},  the  authors  have  proposed  a  linear  programming
+In~\cite{yang2014maximum},  the  authors have  considered  a linear  programming
 approach for selecting  the minimum number of working sensor  nodes, in order to
-as to preserve  a maximum coverage and extend lifetime of  the network. Cheng et
+preserve  a  maximum coverage  and  extend lifetime  of  the  network. Cheng  et
 al.~\cite{cheng2014energy} have defined a  heuristic algorithm called Cover Sets
 Balance (CSB), which choose a set of active nodes using the tuple (data coverage
 range, residual energy).   Then, they have introduced a  new Correlated Node Set
@@ -225,10 +222,6 @@ 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{castano2013column,rossi2012exact,deschinkel2012column}.
 
-
-
-
-
 \subsection{Distributed approaches}
 %{\bf Distributed approaches}
 In distributed  and localized coverage  algorithms, the required  computation to
@@ -238,28 +231,28 @@ 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.
 
-Some        distributed       algorithms        have        been       developed
-in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02, yardibi2010distributed, prasad2007distributed,Misra}
-to perform  the scheduling so  as to preserve coverage.   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  authors  in  \cite{yardibi2010distributed}  have  developed  a  Distributed
-Adaptive  Sleep Scheduling  Algorithm (DASSA)  for WSNs  with  partial coverage.
-DASSA  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 proposed  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
-proposed in \cite{Huang:2003:CPW:941350.941367}.
+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}.
 
 %Our Work, which is presented in~\cite{idrees2014coverage} proposed a coverage optimization protocol to improve the lifetime in
 %heterogeneous energy wireless sensor networks. 
@@ -267,23 +260,23 @@ proposed in \cite{Huang:2003:CPW:941350.941367}.
 
 The  works presented in  \cite{Bang, Zhixin,  Zhang} focuses  on coverage-aware,
 distributed energy-efficient,  and distributed clustering  methods respectively,
-which aims  to extend 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   proposed  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.
+which aims to extend 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 period of time  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
+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
@@ -291,11 +284,8 @@ 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.
-
-
-
-
+approach. In fact, in this paper we make a multiround optimization, while it was
+a single round optimization in our previous work.
 
 \iffalse
    
@@ -377,8 +367,6 @@ 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{castano2013column,rossi2012exact,deschinkel2012column}.
 
-
-
 \subsection{Distributed approaches}
 %{\bf Distributed approaches}
 In distributed  and localized coverage  algorithms, the required  computation to
@@ -388,28 +376,29 @@ 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.
 
-Some        distributed       algorithms        have        been       developed
-in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02,    yardibi2010distributed}
-to perform  the scheduling so  as to preserve coverage.   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}.  In \cite{Tian02}, the  scheduling scheme is divided into
-rounds,  where each  round has  a self-scheduling  phase followed  by  a sensing
-phase.  Each  sensor broadcasts  a message containing  the node~ID and  the node
-location to its  neighbors at the beginning of each  round.  A sensor determines
-its status by a  rule named off-duty eligible rule, which tells  him to turn off
-if its sensing area is covered by its neighbors. A back-off scheme is introduced
-to let each sensor  delay the decision process with a random  period of time, in
-order  to avoid  simultaneous conflicting  decisions between  nodes and  lack of
-coverage on any area.  In \cite{prasad2007distributed} a model for capturing the
-dependencies between different  cover sets is defined and  it proposes localized
-heuristic based  on this  dependency. The algorithm  consists of two  phases, an
-initial setup phase during which each sensor computes and prioritizes the covers
-and a  sensing phase during which  each sensor first decides  its on/off status,
-and then remains on or off for the rest of the duration.
+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}.
+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}.   In  \cite{Tian02},  the scheduling  scheme  is
+divided into rounds, where each round  has a self-scheduling phase followed by a
+sensing phase.  Each sensor broadcasts  a message containing the node~ID and the
+node  location to  its  neighbors at  the  beginning of  each  round.  A  sensor
+determines its status by a rule named off-duty eligible rule, which tells him to
+turn off if its  sensing area is covered by its neighbors.  A back-off scheme is
+introduced to let each sensor delay the decision process with a random period of
+time, in  order to  avoid simultaneous conflicting  decisions between  nodes and
+lack  of coverage  on any  area.   In \cite{prasad2007distributed}  a model  for
+capturing  the dependencies  between  different  cover sets  is  defined and  it
+proposes localized heuristic based on this dependency. The algorithm consists of
+two  phases,  an initial  setup  phase during  which  each  sensor computes  and
+prioritizes  the covers  and  a sensing  phase  during which  each sensor  first
+decides  its on/off  status, and  then remains  on or  off for  the rest  of the
+duration. 
 
 The  authors  in  \cite{yardibi2010distributed}  have  developed  a  Distributed
 Adaptive  Sleep Scheduling  Algorithm (DASSA)  for WSNs  with  partial coverage.
@@ -526,7 +515,7 @@ 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
-working nodes in the active mode.
+active nodes.
 
 Instead  of working  with a  continuous coverage  area, we  make it  discrete by
 considering for each sensor a set of points called primary points. Consequently,
@@ -556,8 +545,10 @@ implemented in each subregion in a distributed way.
 As  can be seen  in Figure~\ref{fig2},  our protocol  works in  periods fashion,
 where  each is  divided  into 4  phases: Information~Exchange,  Leader~Election,
 Decision, and Sensing.  Each sensing phase may be itself divided into $T$ rounds
-and for each round a set of sensors  (said a cover set) is  responsible for the
-sensing task. A multiround optimization process executed in each period after information exchange and leader election in order to produce a $T$ cover sets of sensors to take the mission of sensing for $T$ rounds.
+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}[ht!]
 \centering \includegraphics[width=100mm]{Modelgeneral.pdf} % 70mm
 \caption{The MuDiLCO protocol scheme executed on each node}
@@ -865,10 +856,10 @@ Sensing time for one round & 60 Minutes \\
 $E_{R}$ & 36 Joules\\
 $R_s$ & 5~m   \\     
 %\hline
-$w_{\Theta}$ & 1   \\
+$W_{\Theta}$ & 1   \\
 % [1ex] adds vertical space
 %\hline
-$w_{U}$ & $|P^2|$
+$W_{U}$ & $|P|^2$
 %inserts single line
 \end{tabular}
 \label{table3}
@@ -894,7 +885,7 @@ reduces 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. Therefore, we  have set the number  of subregions to 16 rather  than 32. 
 
-\subsection{Energy Model}
+\subsection{Energy model}
 
 We  use an  energy consumption  model  proposed by~\cite{ChinhVu}  and based  on
 \cite{raghunathan2002energy} with slight  modifications.  The energy consumption
@@ -1052,7 +1043,6 @@ network in round $t$.
 
 \end{enumerate}
 
-
 \section{Results and analysis}
 
 \subsection{Coverage ratio} 
@@ -1076,7 +1066,7 @@ the area of interest for a larger number of rounds. It also means that MuDiLCO-T
 saves more  energy, with less dead nodes,  at most for several  rounds, and thus
 should extend the network lifetime.
 
-\begin{figure}[t!]
+\begin{figure}[ht!]
 \centering
  \includegraphics[scale=0.5] {R1/CR.pdf} 
 \caption{Average coverage ratio for 150 deployed nodes}
@@ -1097,7 +1087,7 @@ Obviously, in  that case DESK  and GAF have  less active nodes, since  they have
 activated many nodes at the beginning. Anyway, MuDiLCO-T activates the available
 nodes in a more efficient manner.
 
-\begin{figure}[t!]
+\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.5]{R1/ASR.pdf}  
 \caption{Active sensors ratio for 150 deployed nodes}
@@ -1120,14 +1110,14 @@ still connected.
 
 %%% The optimization effectively continues as long as a network in a subregion is still connected. A VOIR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-\begin{figure}[t!]
+\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.5]{R1/SR.pdf} 
 \caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes }
 \label{fig6}
 \end{figure} 
 
-\subsection{Energy Consumption} \label{subsec:EC}
+\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
@@ -1174,7 +1164,7 @@ 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}[t!]
+\begin{figure}[ht!]
 \centering
 \includegraphics[scale=0.5]{R1/T.pdf}  
 \caption{Execution Time (in seconds)}
@@ -1194,7 +1184,7 @@ 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}
+\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}$
@@ -1205,7 +1195,7 @@ deactivated  and  thus save  energy.   Compared  to  the other  approaches,  our
 MuDiLCO-T 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 bee observed for MuDiLCO-7
-in case of  $Lifetime_{95}$ with large wireless sensor  networks result from the
+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
@@ -1231,18 +1221,18 @@ linked.
 %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}
+\section{Conclusion and future works}
 \label{sec:conclusion}
 
-In this  paper, we have addressed the  problem of the coverage  and 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.
+We have addressed  the problem of the coverage and  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
