From d2af1567d110987ebd8f80152c8a37de9dbd5d26 Mon Sep 17 00:00:00 2001 From: Michel Salomon Date: Wed, 31 Dec 2014 15:21:12 +0100 Subject: [PATCH] Michel : Section LiCo description (en cours) --- IEEEtran.cls | 0 LiCO_Journal.tex | 75 +++++++++++++++++++++++++++-------------------- pcm.jpg | Bin 3 files changed, 43 insertions(+), 32 deletions(-) mode change 100755 => 100644 IEEEtran.cls mode change 100755 => 100644 LiCO_Journal.tex mode change 100755 => 100644 pcm.jpg diff --git a/IEEEtran.cls b/IEEEtran.cls old mode 100755 new mode 100644 diff --git a/LiCO_Journal.tex b/LiCO_Journal.tex old mode 100755 new mode 100644 index 149aab7..1775b94 --- a/LiCO_Journal.tex +++ b/LiCO_Journal.tex @@ -80,7 +80,7 @@ Wireless Sensor Networks, Area Coverage, Network lifetime, Optimization, Schedul \IEEEpeerreviewmaketitle -\section{\uppercase{Introduction}} +\section{Introduction} \label{sec:introduction} \noindent The continuous progress in Micro Electro-Mechanical Systems (MEMS) and @@ -201,42 +201,46 @@ 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.} -% MICHEL TO BE CONTINUED FROM HERE -Various approaches, including centralized, or distributed algorithms, have been -proposed to extend the network lifetime. In distributed -algorithms~\cite{yangnovel,ChinhVu,qu2013distributed}, information is -disseminated throughout the network and sensors decide cooperatively by -communicating with their neighbors which of them will remain in sleep mode for a -certain period of time. The centralized +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 sensors 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 to reduce the energy dedicated to the comunications. Unfortunately, since +each 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. +Converseley, centralized algorithms~\cite{cardei2005improving,zorbas2010solving,pujari2011high} always -provide nearly or close to optimal solution since the algorithm has global view -of the whole network. But such a method has the disadvantage of requiring high -communication costs, since the node (located at the base station) making the -decision needs information from all the sensor nodes in the area and the amount -of information can be huge. {\it In order to be suitable for large-scale - network, 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.} - -A large variety of coverage scheduling algorithms has been developed. Many of -the existing algorithms, dealing with the maximization of the number of cover -sets, are heuristics. These heuristics involve the construction of a cover set -by including in priority the sensor nodes which cover critical targets, that is -to say targets that are covered by the smallest number of sensors -\cite{berman04,zorbas2010solving}. Other approaches are based on mathematical +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 comunications can be very huge since +long range communications will be needed. In faxt 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.} + +Various coverage scheduling algorithms have been developed this last years. +Many of them, dealing with the maximization of the number of cover sets, are +heuristics. These heuristics involve the construction of a cover set by +including in priority the sensor nodes which cover critical targets, that is to +say targets that are covered by the smallest number of sensors +\cite{berman04,zorbas2010solving}. Other approaches are based on mathematical programming formulations~\cite{cardei2005energy,5714480,pujari2011high,Yang2014} -and dedicated techniques (solving with a branch-and-bound algorithms available -in optimization solver). The problem is formulated as an optimization problem +and dedicated techniques (solving with a branch-and-bound algorithm available in +optimization solver). The problem is formulated as an optimization problem (maximization of the lifetime or number of cover sets) under target coverage and 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 - protocol, each leader, in each subregion, solves an integer program with the - double objective consisting in minimizing the overcoverage and the - undercoverage of the perimeter of each sensor. -} - + 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.} %\noindent Recently, the coverage problem has been received a high attention, which concentrates on how the physical space could be well monitored after the deployment. Coverage is one of the Quality of Service (QoS) parameters in WSNs, which is highly concerned with power depletion~\cite{zhu2012survey}. Most of the works about the coverage protocols have been suggested in the literature focused on three types of the coverage in WSNs~\cite{mulligan2010coverage}: the first, area coverage means that each point in the area of interest within the sensing range of at least one sensor node; the second, target coverage in which a fixed set of targets need to be monitored; the third, barrier coverage refers to detect the intruders crossing a boundary of WSN. The work in this paper emphasized on the area coverage, so, some area coverage protocols have been reviewed in this section, and the shortcomings of reviewed approaches are being summarized. @@ -276,10 +280,17 @@ used~\cite{castano2013column,rossi2012exact,deschinkel2012column}. {\it In LiCO %\uppercase{\textbf{Our Protocol}}. In this paper, a Lifetime Coverage Optimization Protocol, called (LiCO) in WSNs is suggested. The sensing field is divided into smaller subregions by means of divide-and-conquer method, and a LiCO protocol is distributed in each sensor in the subregion. The network lifetime in each subregion is divided into periods, each period includes 4 stages: Information Exchange, Leader election, decision based activity scheduling optimization, and sensing. The leaders are elected in an independent, asynchronous, and distributed way in all the subregions of the WSN. After that, energy-efficient activity scheduling mechanism based new optimization model is performed by each leader in the subregions. This optimization model is based on the perimeter coverage model in order to producing the optimal cover set of active sensors, which are taken the responsibility of sensing during the current period. LiCO protocol merges between two energy efficient mechanisms, which are used the main advantages of the centralized and distributed approaches and avoids the most of their disadvantages. - \section{ The LiCO Protocol Description} \label{sec:The LiCO Protocol Description} -\noindent In this section, we describe our Lifetime Coverage Optimization Protocol which is called LiCO in more detail. + +\noindent In this section, we describe in details our Lifetime Coverage +Optimization protocol. First we present the assumptions we made and the models +we considered (in particular the perimter coverage one), second we describe the +background idea of our protocol, and third we give the outline of the algorithm +executed by each node. + +% MICHEL TO BE CONTINUED FROM HERE + % It is based on two efficient-energy mechanisms: the first, is partitioning the sensing field into smaller subregions, and one leader is elected for each subregion; the second, a sensor activity scheduling based new optimization model so as to produce the optimal cover set of active sensors for the sensing stage during the period. Obviously, these two mechanisms can be contribute in extend the network lifetime coverage efficiently. %Before proceeding in the presentation of the main ideas of the protocol, we will briefly describe the perimeter coverage model and give some necessary assumptions and definitions. diff --git a/pcm.jpg b/pcm.jpg old mode 100755 new mode 100644 -- 2.39.5