X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/JournalMultiPeriods.git/blobdiff_plain/ebd4a0db25967c8125c94bc1f93627812fde498a..dcd17c328de094da5e719e97a6d0f65908d72356:/article.tex

diff --git a/article.tex b/article.tex
index b867546..a4752b1 100644
--- a/article.tex
+++ b/article.tex
@@ -67,7 +67,7 @@
 %% \address{Address\fnref{label3}}
 %% \fntext[label3]{}
 
-\title{Multiperiod Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}
+\title{Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}
 
 %% use optional labels to link authors explicitly to addresses:
 %% \author[label1,label2]{}
@@ -89,7 +89,7 @@ $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcom
 %continuously  and  effectively  when  monitoring a  certain  area  (or
 %region) of  interest. 
 Coverage and  lifetime are  two paramount problems  in Wireless  Sensor Networks
-(WSNs). In this paper, a method called Multiperiod Distributed Lifetime Coverage
+(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
@@ -126,14 +126,14 @@ 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
+we concentrate  on the area coverage problem, with the  objective of maximizing
 the network lifetime by using an optimized multirounds 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
@@ -184,6 +184,120 @@ algorithms in WSNs according to several design choices:
 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}
+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
+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 take the decision needs
+information from all the  sensor nodes. Moreover, centralized approaches usually
+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
+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}    
+
+
+
+
+In~\cite{yang2014maximum},  the  authors  have  proposed  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
+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
+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{castano2013column,rossi2012exact,deschinkel2012column}.
+
+
+
+
+
+\subsection{Distributed approaches}
+%{\bf 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.
+
+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}.
+
+%Our Work, which is presented in~\cite{idrees2014coverage} proposed a coverage optimization protocol to improve the lifetime in
+%heterogeneous energy wireless sensor networks. 
+%In this work, the coverage protocol distributed in each sensor node in the subregion but the optimization take place over the the whole subregion. We consider only distributing the coverage protocol over two subregions. 
+
+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.
+
+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
+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.
+
+
+
+
+
+\iffalse
    
 \subsection{Centralized Approaches}
 %{\bf Centralized approaches}
@@ -263,6 +377,8 @@ 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
@@ -337,7 +453,7 @@ 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 Multiperiod 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
@@ -347,6 +463,10 @@ 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.
 
+
+
+
+\fi
 %The main contributions of our MuDiLCO Protocol can be summarized as follows:
 %(1) The high coverage ratio, (2) The reduced number of active nodes, (3) The distributed optimization over the subregions in the area of interest, (4) The distributed dynamic leader election at each round based on some priority factors that led to energy consumption balancing among the nodes in the same subregion, (5) The primary point coverage model to represent each sensor node in the network, (6) The activity scheduling based optimization on the subregion, which are based on the primary point coverage model to activate as less number as possible of sensor nodes for a multirounds to take the mission of the coverage in each subregion, (7) The very low energy consumption, (8) The higher network lifetime.
 %\section{Preliminaries}
@@ -383,7 +503,7 @@ approach.
 %minimizing  overcoverage (points  covered by  multiple  active sensors
 %simultaneously).
 
-%In this section, we introduce a Multiperiod Distributed Lifetime Coverage Optimization protocol, which is called MuDiLCO. It is  distributed on each subregion in the area of interest. It is based on two efficient techniques: network
+%In this section, we introduce a Multiround Distributed Lifetime Coverage Optimization protocol, which is called MuDiLCO. It is  distributed on each subregion in the area of interest. It is based on two efficient techniques: network
 %leader election and sensor activity scheduling for coverage preservation and energy conservation continuously and efficiently to maximize the lifetime in the network.  
 %The main features of our MuDiLCO protocol:
 %i)It divides the area of interest into subregions by using divide-and-conquer concept, ii)It requires only the information of the nodes within the subregion, iii) it divides the network lifetime into periods, which consists in round(s), iv)It based on the autonomous distributed decision by the nodes in the subregion to elect the Leader, v)It apply the activity scheduling based optimization on the subregion, vi)  it achieves an energy consumption balancing among the nodes in the subregion by selecting different nodes as a leader during the network lifetime, vii) It uses the optimization to select the best representative non-disjoint sets of sensors in the subregion by optimize the coverage and the lifetime over the area of interest, viii)It uses our proposed primary point coverage model, which represent the sensing range of the sensor as a set of points, which are used by the our optimization algorithm, ix) It uses a simple energy model that takes communication, sensing and computation energy consumptions into account to evaluate the performance of our Protocol.
@@ -430,14 +550,14 @@ is the subject of another study not presented here.
 \subsection{Background idea}
 %%RC : we need to clarify the difference between round and period. Currently it seems to be the same (for me at least).
 The area of  interest can be divided using  the divide-and-conquer strategy into
-smaller  areas,  called  subregions,  and  then our  MuDiLCO  protocol  will  be
+smaller  areas,  called  subregions,  and  then our MuDiLCO  protocol will be
 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.
+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.
 \begin{figure}[ht!]
 \centering \includegraphics[width=100mm]{Modelgeneral.pdf} % 70mm
 \caption{The MuDiLCO protocol scheme executed on each node}
@@ -449,13 +569,13 @@ sensing task.
 % set cover responsible for the sensing task.  
 %For each round a set of sensors (said a cover set) is responsible for the sensing task.
 
-This protocol is  reliable against an unexpected node  failure, because it works
+This protocol is reliable against an unexpected node failure, because it works
 in periods. 
 %%RC : why? I am not convinced
- 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
+ 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.
 %%RC so if there are at least one failure per period, the coverage is bad...
 
@@ -1120,7 +1240,7 @@ 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    (Multiperiod   Distributed   Lifetime   Coverage
+protocol,   called   MuDiLCO    (Multiround  Distributed   Lifetime   Coverage
 Optimization)  combines two  efficient techniques:  network leader  election and
 sensor activity scheduling.
 %,  where the challenges
@@ -1149,7 +1269,7 @@ an excessive energy consumption.
 
 \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
+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. 
@@ -1179,7 +1299,7 @@ student   services,  and   international  mobility).%,   and  the   University
 %% TeX file.
 
 \bibliographystyle{elsarticle-num} 
-\bibliography{biblio}
+\bibliography{article}
   
 \end{document}
 
