From a858180eaddcc3839f05237bd8f39f34edc1f625 Mon Sep 17 00:00:00 2001 From: raphael couturier Date: Wed, 14 Jan 2015 21:34:59 +0100 Subject: [PATCH] reading until Section III --- LiCO_Journal.tex | 66 +++++++++++++++++++++++++----------------------- 1 file changed, 34 insertions(+), 32 deletions(-) diff --git a/LiCO_Journal.tex b/LiCO_Journal.tex index 4571961..02be4ac 100644 --- a/LiCO_Journal.tex +++ b/LiCO_Journal.tex @@ -45,7 +45,7 @@ Karine Deschinkel,~\IEEEmembership{} Michel Salomon,~\IEEEmembership{} and~Rapha\"el Couturier ~\IEEEmembership{} - \thanks{The authors are with FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comt\'e, + \thanks{The authors are with FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte, Belfort, France. Email: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr}} @@ -63,12 +63,14 @@ scheduling which ensures sensing coverage while minimizing the energy cost. In this paper, we propose such an approach called Lifetime Coverage Optimization protocol (LiCO). It is a hybrid of centralized and distributed methods: the region of interest is first subdivided into subregions and our protocol is then -distributed among sensor nodes in each subregion. A sensor node which runs LiCO -protocol repeats periodically four stages: information exchange, leader -election, optimization decision, and sensing. More precisely, the scheduling of -nodes' activities (sleep/wake up duty cycles) is achieved in each subregion by a -leader selected after cooperation between nodes within the same subregion. The -novelty of our approach lies essentially in the formulation of a new +distributed among sensor nodes in each subregion. +%%RAPH abstract too long +% A sensor node which runs LiCO +%protocol repeats periodically four stages: information exchange, leader +%election, optimization decision, and sensing. More precisely, the scheduling of +%nodes' activities (sleep/wake up duty cycles) is achieved in each subregion by a +%leader selected after cooperation between nodes within the same subregion. +The novelty of our approach lies essentially in the formulation of a new mathematical optimization model based on perimeter coverage level to schedule sensors' activities. Extensive simulation experiments have been performed using OMNeT++, the discrete event simulator, to demonstrate that LiCO is capable to @@ -121,23 +123,23 @@ lifetime of the WSNs~\cite{rault2014energy}. This paper makes the following contributions. \begin{enumerate} -\item We devise a framework to schedule nodes to be activated alternatively such +\item We have devised a framework to schedule nodes to be activated alternatively such that the network lifetime is prolonged while ensuring that a certain level of coverage is preserved. A key idea in our framework is to exploit spatial and - temporal subdivision. On the one hand the area of interest if divided into - several smaller subregions and on the other hand the time line is divided into + temporal subdivision. On the one hand, the area of interest if divided into + several smaller subregions and, on the other hand, the time line is divided into periods of equal length. In each subregion the sensor nodes will cooperatively choose a leader which will schedule nodes' activities, and this grouping of sensors is similar to typical cluster architecture. -\item We propose a new mathematical optimization model. Instead of trying to +\item We have proposed a new mathematical optimization model. Instead of trying to cover a set of specified points/targets as in most of the methods proposed in the literature, we formulate an integer program based on perimeter coverage of each sensor. The model involves integer variables to capture the deviations - between the actual level of coverage and the required level. So that an + between the actual level of coverage and the required level. Hence, an optimal scheduling will be obtained by minimizing a weighted sum of these deviations. -\item We conducted extensive simulation experiments, using the discrete event - simulator OMNeT++, to demonstrate the efficiency of our protocol. We compared +\item We have conducted extensive simulation experiments, using the discrete event + simulator OMNeT++, to demonstrate the efficiency of our protocol. We have compared our LiCO protocol to two approaches found in the literature: DESK~\cite{ChinhVu} and GAF~\cite{xu2001geography}, and also to our previous work published in~\cite{Idrees2} which is based on another optimization model @@ -153,7 +155,7 @@ is devoted to the LiCO protocol description and Section~\ref{cp} focuses on the coverage model formulation which is used to schedule the activation of sensor nodes. Section~\ref{sec:Simulation Results and Analysis} presents simulations results and discusses the comparison with other approaches. Finally, concluding -remarks are drawn and some suggestions given for future works in +remarks are drawn and some suggestions are given for future works in Section~\ref{sec:Conclusion and Future Works}. % that show that our protocol outperforms others protocols. @@ -167,7 +169,7 @@ the literature. The most discussed coverage problems in literature can be classified in three categories~\cite{li2013survey} according to their respective monitoring objective. Hence, area coverage \cite{Misra} means that every point inside a -fixed area must be monitored, while target coverage~\cite{yang2014novel} refer +fixed area must be monitored, while target coverage~\cite{yang2014novel} refers to the objective of coverage for a finite number of discrete points called targets, and barrier coverage~\cite{HeShibo}\cite{kim2013maximum} focuses on preventing intruders from entering into the region of interest. In @@ -178,7 +180,7 @@ nodes or between disk of sensor nodes and boundaries. In sensors are sufficiently covered it will be the case for the whole area. They provide an algorithm in $O(nd~log~d)$ time to compute the perimeter-coverage of each sensor, where $d$ denotes the maximum number of sensors that are -neighboring to a sensor and $n$ is the total number of sensors in the +neighbors to a sensor and $n$ is the total number of sensors in the network. {\it In LiCO protocol, instead of determining the level of coverage of a set of discrete points, our optimization model is based on checking the perimeter-coverage of each sensor to activate a minimal number of sensors.} @@ -203,28 +205,28 @@ each period. {\it Motivated by these works, LiCO protocol works in periods, decisions, followed by a sensing phase where one cover set is in charge of the sensing task.} -Various centralized and distributed approaches, or even a mixing of these two +Various centralized and distributed approaches, or even a mixing of these two concepts, have been proposed to extend the network lifetime. In distributed algorithms~\cite{yangnovel,ChinhVu,qu2013distributed} each sensor decides of its own activity scheduling after an information exchange with its neighbors. The -main interest of a such approach is to avoid long range communications and thus +main interest of such an approach is to avoid long range communications and thus to reduce the energy dedicated to the communications. Unfortunately, since each -node has only information on its immediate neighbors (usually the one-hop ones) +node has only information on its immediate neighbors (usually the one-hop ones) it may take a bad decision leading to a global suboptimal solution. Conversely, centralized -algorithms~\cite{cardei2005improving,zorbas2010solving,pujari2011high} always +algorithms~\cite{cardei2005improving,zorbas2010solving,pujari2011high} always provide nearly or close to optimal solution since the algorithm has a global view of the whole network. The disadvantage of a centralized method is obviously -its high cost in communications needed to transmit to a single node, the base -station which will globally schedule nodes' activities, data from all the other -sensor nodes in the area. The price in communications can be very huge since -long range communications will be needed. In fact the larger the WNS, the higher -the communication and thus energy cost. {\it In order to be suitable for - large-scale networks, in the LiCO protocol the area of interest is divided - into several smaller subregions, and in each one, a node called the leader is - in charge for selecting the active sensors for the current period. Thus our - protocol is scalable and a globally distributed method, whereas it is - centralized in each subregion.} +its high cost in communications needed to transmit to a single node, the base +station which will globally schedule nodes' activities, data from all the other +sensor nodes in the area. The price in communications can be very huge since +long range communications will be needed. In fact the larger the WNS is, the +higher the communication and thus the energy cost are. {\it In order to be + suitable for large-scale networks, in the LiCO protocol, the area of interest + is divided into several smaller subregions, and in each one, a node called the + leader is in charge of selecting the active sensors for the current + period. Thus our protocol is scalable and is a globally distributed method, + whereas it is centralized in each subregion.} Various coverage scheduling algorithms have been developed this last years. Many of them, dealing with the maximization of the number of cover sets, are @@ -239,7 +241,7 @@ optimization solver). The problem is formulated as an optimization problem energy constraints. Column generation techniques, well-known and widely practiced techniques for solving linear programs with too many variables, have also been -used~\cite{castano2013column,rossi2012exact,deschinkel2012column}. {\it In LiCO +used~\cite{castano2013column,rossi2012exact,deschinkel2012column}. {\it In the LiCO protocol, each leader, in charge of a subregion, solves an integer program which has a twofold objective: minimize the overcoverage and the undercoverage of the perimeter of each sensor.} -- 2.39.5