X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/UIC2013.git/blobdiff_plain/8ab0f8781a3c93346920e6762d19e6ba7175f910..a0a53567a404570c213a399c92a3e11bd32b7113:/bare_conf.tex

diff --git a/bare_conf.tex b/bare_conf.tex
index 206d113..48f598c 100644
--- a/bare_conf.tex
+++ b/bare_conf.tex
@@ -11,7 +11,6 @@
 
 \hyphenation{op-tical net-works semi-conduc-tor}
 
-
 \usepackage{etoolbox}
 \usepackage{float} 
 \usepackage{epsfig}
@@ -40,7 +39,6 @@
 \DeclareGraphicsExtensions{.ps}
 \DeclareGraphicsRule{.ps}{pdf}{.pdf}{`ps2pdf -dEPSCrop -dNOSAFER #1 \noexpand\OutputFile}
 
-
 \begin{document}
 %
 % paper title
@@ -86,40 +84,67 @@ Optimization, Scheduling.
 
 \section{Introduction}
 
-\indent  The fast developments  in the  low-cost sensor  devices and
-wireless  communications  have allowed  the  emergence  the WSNs.  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, cooperate together to monitor the area of interest, 
-and the measured data can be reported to a monitoring center called sink  
-for analysis it~\cite{Sudip03}. There are several applications used the
-WSN including health, home, environmental, military, and industrial
-applications~\cite{Akyildiz02}. The coverage problem is one  of the
-fundamental challenges in WSNs~\cite{Nayak04} that consists in monitoring efficiently and continuously
-the area of interest. Thelimited energy  of sensors represents  the main challenge in  the WSNs
-design~\cite{Sudip03}, where it is difficult to replace and/or recharge their batteries because the the area of interest nature (such
-as hostile environments) and the cost. So, it is necessary that a WSN
-deployed  with high  density because  spatial redundancy  can  then be
-exploited to increase  the lifetime of the network. However, turn on
-all the sensor nodes, which monitor the same region at the same time
-leads to decrease the lifetime of the network. To extend the lifetime
-of the network, the main idea is to take advantage of the overlapping
-sensing regions  of some  sensor nodes to  save energy by  turning off
-some  of them  during the  sensing phase~\cite{Misra05}. WSNs require
-energy-efficient solutions to improve the network lifetime that is
-constrained by the limited power of each sensor node ~\cite{Akyildiz02}. In this paper, we concentrate on the area
-coverage  problem, with the objective of maximizing the network
-lifetime by using  an adaptive  scheduling. The area of interest is
-divided into subregions and an activity scheduling for sensor nodes is
-planned for each subregion. In fact, the nodes in a subregion can be
-seen as a cluster where each node sends sensing data to the cluster head or the sink node. Furthermore, the activities in a
-subregion/cluster can continue even if another cluster stops  due to
-too many node failures.  Our scheduling scheme considers rounds, where
-a round starts with a  discovery phase to exchange information between
-sensors of  the subregion, in order  to choose in a  suitable manner a
-sensor node to  carry out a coverage strategy.  This coverage strategy
-involves  the  solving  of  an  integer program,  which  provides  the
-activation of the sensors for the sensing phase of the current round.
+%\indent  The fast  developments  in the  low-cost  sensor devices  and
+%wireless  communications have  allowed  the emergence  the WSNs.   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, cooperate  together to  monitor the area  of interest,
+%and the  measured data can be  reported to a  monitoring center called
+%sink  for analysis it~\cite{Sudip03}.  There are  several applications
+%used  the WSN  including  health, home,  environmental, military,  and
+%industrial applications~\cite{Akyildiz02}. The coverage problem is one
+%of the fundamental challenges  in WSNs~\cite{Nayak04} that consists in
+%monitoring    efficiently    and     continuously    the    area    of
+%interest. Thelimited  energy of sensors represents  the main challenge
+%in the  WSNs design~\cite{Sudip03}, where  it is difficult  to replace
+%and/or  recharge their  batteries  because the  the  area of  interest
+%nature  (such  as  hostile  environments)  and the  cost.  So,  it  is
+%necessary  that  a WSN  deployed  with  high  density because  spatial
+%redundancy  can then  be exploited  to  increase the  lifetime of  the
+%network. However, turn on all the sensor nodes, which monitor the same
+%region at the same time leads to decrease the lifetime of the network.
+
+Recent   years  have  witnessed   significant  advances   in  wireless
+communications and embedded micro-sensing MEMS technologies which have
+led to the emergence of Wireless  Sensor Networks (WSNs) as one of the
+most promising  technologies \cite{Akyildiz02}. In  fact, they present
+huge   potential  in   several  domains   ranging  from   health  care
+applications to military applications. A sensor network is composed of
+a  large  number of  tiny  sensing devices  deployed  in  a region  of
+interest.  Each  device  has  processing  and  wireless  communication
+capabilities, which enable it to sense its environment, to compute, to
+store information  and to  deliver report messages  to a  base station
+\cite{Sudip03}.  One of  the main design issues in  WSNs is to prolong
+the network  lifetime, while  achieving acceptable quality  of service
+for  applications. Indeed,  sensors  nodes have  limited resources  in
+terms of memory, energy and computational power.
+
+Since sensor nodes have limited battery life and without being able to
+replace batteries,  especially in remote and  hostile environments, it
+is desirable that  a WSN should be deployed  with high density because
+spatial redundancy can  then be exploited to increase  the lifetime of
+the network. In such a high  density network, if all sensor nodes were
+to be  activated at the same  time, the lifetime would  be reduced. To
+extend the lifetime of the network, the main idea is to take advantage
+of the overlapping sensing regions of some sensor nodes to save energy
+by turning  off some of them during  the sensing phase~\cite{Misra05}.
+Obviously, the deactivation of nodes  is only relevant if the coverage
+of the monitored  area is not affected. In  this paper, we concentrate
+on  the area coverage  problem \cite{Nayak04},  with the  objective of
+maximizing the network lifetime  by using an adaptive scheduling.  The
+area of interest is divided into subregions and an activity scheduling
+for sensor nodes is planned for each subregion.  In fact, the nodes in
+a subregion  can be seen  as a cluster  where each node  sends sensing
+data  to  the  cluster  head  or  the  sink  node.   Furthermore,  the
+activities in a subregion/cluster can continue even if another cluster
+stops due to too many  node failures.  Our scheduling scheme considers
+rounds,  where a  round  starts  with a  discovery  phase to  exchange
+information between sensors of the  subregion, in order to choose in a
+suitable manner a sensor node  to carry out a coverage strategy.  This
+coverage strategy  involves the solving  of an integer  program, which
+provides the  activation of the sensors  for the sensing  phase of the
+current round.
 
 The remainder of the paper is organized as follows. The next section
 % Section~\ref{rw}
@@ -139,44 +164,42 @@ the coverage lifetime maximization  problem, where the objective is to
 optimally  schedule  sensors'  activities  in  order  to  extend  WSNs
 lifetime.
 
-In \cite{chin2007},  the author 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  1-hop  neighbor
-information,  and each  sensor decides  its status  (active  or sleep)
-based    on    the    perimeter    coverage    model    proposed    in
+In \cite{chin2007}, the author 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  1-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}.    More    recently,   Shibo   et
 al. \cite{Shibo}  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.  
-% TO BE CONTINUED      Distributed  Energy- Efficient
-
-The works presented in \cite{Bang, Zhixin, Zhang}  focuses on a Coverage-Aware, Distributed  Energy- Efficient and distributed clustering methods respectively, which aims to extend the network lifetime, while the coverage is ensured.
-
-S.  Misra  et al.  \cite{Misra}  proposed  a  localized algorithm  for
-coverage in  sensor networks. The algorithm conserve  the energy while
-ensuring  the network coverage  by activating  the subset  of sensors,
-with  the  minimum  overlap  area.The proposed  method  preserves  the
-network connectivity by formation of the network backbone. 
-
-J. A. Torkestani  \cite{Torkestani} proposed a learning automata-based
-energy-efficient  coverage protocol  named as  LAEEC to  construct the
-degree-constrained connected  dominating set (DCDS) in  WSNs. He shows
-that the correct choice of  the degree-constraint of DCDS balances the
-network load on the active nodes and leads to enhance the coverage and
-network lifetime.
+Greedy Algorithm (DTGA) to solve it. They take in particular advantage
+from  both temporal and  spatial correlations  between data  sensed by
+different sensors.
+
+The  works  presented  in  \cite{Bang,  Zhixin, Zhang}  focus  on  the
+definition  of  a  coverage-aware,  distributed  energy-efficient  and
+distributed clustering  methods respectively.  They aim  to extend the
+network  lifetime  while ensuring  the  coverage.   S.   Misra et  al.
+\cite{Misra05} proposed a localized algorithm which conserves energy and
+coverage  by  activating  the  subset  of  sensors  with  the  minimum
+overlapping area. It preserves  the network connectivity thanks to the
+formation of the  network backbone. J.~A.~Torkestani \cite{Torkestani}
+designed a Learning  Automata-based Energy-Efficient Coverage protocol
+(LAEEC)  to construct  a Degree-constrained  Connected  Dominating Set
+(DCDS)  in   WSNs.   He  showed   that  the  correct  choice   of  the
+degree-constraint  of DCDS  balances the  network load  on  the active
+nodes and leads to enhance the coverage and network lifetime.
  
 The main  contribution of our approach addresses  three main questions
-to build a scheduling strategy:
+to build a scheduling strategy.\\
 %\begin{itemize}
 %\item 
-{\bf How must the  phases for information exchange, decision and
-  sensing be planned over time?}   Our algorithm divides the time line
-  into a number  of rounds. Each round contains  4 phases: Information
-  Exchange, Leader Election, Decision, and Sensing.
+{\indent \bf  How must the  phases for information  exchange, decision
+  and sensing be  planned over time?}  Our algorithm  divides the time
+line into rounds.  Each round contains 4 phases: Information Exchange,
+Leader Election, Decision, and Sensing.
 
 %\item 
 {\bf What are the rules to decide which node has to be turned on
@@ -187,15 +210,13 @@ to build a scheduling strategy:
   objectives.
 
 %\item 
-{\bf Which  node should make such a  decision?}  The leader should make such a  decision. Our
-  work does not  consider only one leader to  compute and to broadcast
-  the scheduling decision  to all the sensors.  When  the network size
-  increases,  the network  is  divided into  many  subregions and  the
-  decision is made by a leader in each subregion.
+{\bf Which  node should make such  a decision?}  A  leader node should
+make such  a decision. Our work  does not consider only  one leader to
+compute and to  broadcast the scheduling decision to  all the sensors.
+When  the network  size increases,  the network  is divided  into many
+subregions and the decision is made by a leader in each subregion.
 %\end{itemize}
 
-
-
 \section{Activity scheduling}
 \label{pd}
 
@@ -212,8 +233,6 @@ then  our coverage  protocol  will be  implemented  in each  subregion
 simultaneously.   Our protocol  works in  rounds fashion  as  shown in
 figure~\ref{fig1}.
 
-
-
 \begin{figure}[ht!]
 \centering
 \includegraphics[width=85mm]{FirstModel.eps} % 70mm
@@ -357,7 +376,7 @@ $X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $.
 %\includegraphics[scale=0.10]{fig26.pdf}\\~ ~ ~(e)
 %\includegraphics[scale=0.10]{fig27.pdf}\\~ ~ ~(f)
 %\end{multicols} 
-\caption{Wireless sensor node represented by 13 primary points}
+\caption{Sensor node represented by 13 primary points}
 \label{fig2}
 \end{figure}
 
@@ -420,7 +439,7 @@ U_{p} = \left \{
 \label{eq14} 
 \end{equation}
 
-\noindent Our coverage optimization problem can then be formulated as follows
+\noindent Our coverage optimization problem can then be formulated as follows\\
 \begin{equation} \label{eq:ip2r}
 \left \{
 \begin{array}{ll}
@@ -436,9 +455,6 @@ X_{j} \in \{0,1\}, &\forall j \in J
 \end{array}
 \right.
 \end{equation}
-
-
-
 \begin{itemize}
 \item $X_{j}$  : indicates whether or  not the sensor  $j$ is actively
   sensing in the round (1 if yes and 0 if not);
@@ -459,7 +475,6 @@ 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.
  
-
 \section{Simulation results}
 \label{exp}
 
@@ -566,7 +581,7 @@ that even if a network is disconnected in one subregion, the other one
 usually  continues  the optimization  process,  and  this extends  the
 lifetime of the network.
 
-\subsection{The impact of the number of rounds on the energy saving ratio} 
+\subsection{Impact of the number of rounds on the energy saving ratio} 
 
 In this experiment, we consider a performance metric linked to energy.
 This metric, called Energy Saving Ratio (ESR), is defined by:
@@ -673,7 +688,7 @@ nodes.   Overall,  to  be  able to  deal  with  very  large  networks,  a
 distributed method is clearly required.
 
 \begin{table}[ht]
-\caption{THE EXECUTION TIME(S) VS THE NUMBER OF SENSORS}
+\caption{EXECUTION TIME(S) VS. NUMBER OF SENSORS}
 % title of Table
 \centering
 
@@ -711,12 +726,12 @@ Sensors number & Strategy~2 & Strategy~1  & Simple heuristic \\ [0.5ex]
 
 Finally, 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.  In  figure~\ref{fig8}, the
+monitoring an area has become disconnected.  In figure~\ref{fig8}, the
 network  lifetime for different  network sizes  and for  both strategy
-with two  leaders and the simple  heuristic is illustrated. 
-  We do  not consider  anymore the  centralized strategy  with one
-  leader, because, as shown above, this strategy results  in execution
-  times that quickly become unsuitable for a sensor network.
+with two leaders  and the simple heuristic is  illustrated.  We do not
+consider anymore the centralized strategy with one leader, because, as
+shown  above, this strategy  results in  execution times  that quickly
+become unsuitable for a sensor network.
 
 \begin{figure}[h!]
 %\centering
@@ -728,50 +743,48 @@ with two  leaders and the simple  heuristic is illustrated.
 \end{figure} 
 
 As  highlighted by figure~\ref{fig8},  the network  lifetime obviously
-increases when  the size  of the network  increases, with  our approach
-that leads to  the larger lifetime improvement.  By  choosing the  best 
-suited nodes, for each round,  to cover the  region of interest  and by
+increases when  the size of  the network increases, with  our approach
+that leads to  the larger lifetime improvement.  By  choosing the best
+suited nodes, for  each round, to cover the region  of interest and by
 letting the other ones sleep in order to be used later in next rounds,
-our strategy efficiently prolonges the network lifetime. Comparison shows that
-the larger  the sensor number  is, the more our  strategies outperform
-the simple heuristic.  Strategy~2, which uses two leaders, is the best
-one because it is robust to network disconnection in one subregion. It
-also  means   that  distributing  the  algorithm  in   each  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.
-
-\section{Conclusion and future works}
+our  strategy efficiently prolonges  the network  lifetime. Comparison
+shows that  the larger the sensor  number is, the  more our strategies
+outperform the simple heuristic.   Strategy~2, which uses two leaders,
+is the best  one because it is robust to  network disconnection in one
+subregion. It also means that  distributing the algorithm in each 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.
+
+\section{Conclusion and future work}
 \label{sec:conclusion}
 
-In this paper, we have  addressed the problem of the coverage and the lifetime
-optimization  in WSNs. To  cope with this problem, the  field of sensing
-is   divided   into   smaller   subregions  using   the   concept   of
+In this paper,  we have addressed the problem of  the coverage and the
+lifetime optimization in WSNs. To cope with this problem, the field of
+sensing  is  divided into  smaller  subregions  using  the concept  of
 divide-and-conquer method,  and then a  multi-rounds coverage protocol
 will optimize  coverage and  lifetime performances in  each subregion.
-The  simulations show the relevance  of the proposed
-protocol in  terms of lifetime, coverage ratio,  active sensors ratio,
-energy saving,  energy consumption, execution time, and  the number of
-stopped simulation  runs due  to network disconnection.   Indeed, when
-dealing with  large and dense 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.
-
-In  future work, we plan  to study  and propose  a coverage  protocol, which
-computes  all  active  sensor  schedules  in  one time,  using
-optimization  methods  such  as  swarms optimization  or  evolutionary
-algorithms.  
+The  proposed  protocol  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  representative active  nodes. Results from  simulations show
+the relevance of the proposed  protocol in terms of lifetime, coverage
+ratio,  active  sensors  ratio,  energy  saving,  energy  consumption,
+execution  time, and  the number  of  stopped simulation  runs due  to
+network  disconnection.  Indeed,  when  dealing with  large and  dense
+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.  In future  work, we
+plan to  study a  coverage protocol which  computes all  active sensor
+schedules  in one  time,  using optimization  methods  such as  swarms
+optimization or evolutionary algorithms.
 % use section* for acknowledgement
 %\section*{Acknowledgment}
 
-
-
-
 \bibliographystyle{IEEEtran}
 \bibliography{bare_conf}
 
-
 \end{document}
 
 
