From 1e8d9ca3bf21ff3289e0673fd5371073cc80fe24 Mon Sep 17 00:00:00 2001 From: Michel Salomon Date: Mon, 20 Oct 2014 16:28:27 +0200 Subject: [PATCH] Modification in 5.2.2. Energy consumption --- Example.tex | 179 ++++++++++++++++++++++++++++------------------------ 1 file changed, 97 insertions(+), 82 deletions(-) diff --git a/Example.tex b/Example.tex index ec92390..28aa4d4 100644 --- a/Example.tex +++ b/Example.tex @@ -102,72 +102,82 @@ where a review of some related works is presented. The next section describes the DiLCO protocol, followed in Section~\ref{cp} by the coverage model formulation which is used to schedule the activation of sensors. Section~\ref{sec:Simulation Results and Analysis} shows the simulation -results. The paper ends with a conclusion and some suggestions for further work +results. The paper ends with a conclusion and some suggestions for further work in Section~\ref{sec:Conclusion and Future Works}. \section{\uppercase{Literature Review}} \label{sec:Literature Review} -\noindent In this section, we summarize some related works regarding the coverage -problem and distinguish our DiLCO protocol from the works presented in the -literature. - -The most discussed coverage problems in literature -can be classified into three types \cite{li2013survey}: area coverage \cite{Misra} where -every point inside an area is to be monitored, target coverage \cite{yang2014novel} where the main -objective is to cover only a finite number of discrete points called targets, -and barrier coverage \cite{Kumar:2005}\cite{kim2013maximum} to prevent intruders from entering into the region of interest. In \cite{Deng2012} authors transform the area coverage problem to the target coverage problem taking into account the intersection points among disks of sensors nodes or between disk of sensor nodes and boundaries. -{\it In DiLCO protocol, the area coverage, i.e. the coverage of every point in - the sensing region, is transformed to the coverage of a fraction of points - called primary points. } - +\noindent In this section, we summarize some related works regarding the +coverage problem and distinguish our DiLCO protocol from the works presented in +the literature. + +The most discussed coverage problems in literature can be classified into three +types \cite{li2013survey}: area coverage \cite{Misra} where every point inside +an area is to be monitored, target coverage \cite{yang2014novel} where the main +objective is to cover only a finite number of discrete points called targets, +and barrier coverage \cite{Kumar:2005}\cite{kim2013maximum} to prevent intruders +from entering into the region of interest. In \cite{Deng2012} authors transform +the area coverage problem to the target coverage problem taking into account the +intersection points among disks of sensors nodes or between disk of sensor nodes +and boundaries. {\it In DiLCO protocol, the area coverage, i.e. the coverage of + every point in the sensing region, is transformed to the coverage of a + fraction of points called primary points. } The major approach to extend network lifetime while preserving coverage is to divide/organize the sensors into a suitable number of set covers (disjoint or -non-disjoint), where each set completely covers a region of interest, and to +non-disjoint), where each set completely covers a region of interest, and to activate these set covers successively. The network activity can be planned in advance and scheduled for the entire network lifetime or organized in periods, -and the set of active sensor nodes is decided at the beginning of each period \cite{ling2009energy}. -Active node selection is determined based on the problem requirements (e.g. area -monitoring, connectivity, power efficiency). For instance, Jaggi et al. \cite{jaggi2006} -address the problem of maximizing network lifetime by dividing sensors into the maximum number of disjoint subsets such that each subset can ensure both coverage and connectivity. A greedy algorithm is applied once to solve this problem and the computed sets are activated in succession to achieve the desired network lifetime. -Vu \cite{chin2007}, Padmatvathy et al. \cite{pc10}, propose algorithms working in a periodic fashion where a cover set is computed at the beginning of each period. -{\it Motivated by these works, DiLCO protocol works in periods, where each period contains a preliminary - phase for information exchange and decisions, followed by a sensing phase - where one cover set is in charge of the sensing task.} - -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 +and the set of active sensor nodes is decided at the beginning of each period +\cite{ling2009energy}. Active node selection is determined based on the problem +requirements (e.g. area monitoring, connectivity, power efficiency). For +instance, Jaggi et al. \cite{jaggi2006} address the problem of maximizing +network lifetime by dividing sensors into the maximum number of disjoint subsets +such that each subset can ensure both coverage and connectivity. A greedy +algorithm is applied once to solve this problem and the computed sets are +activated in succession to achieve the desired network lifetime. Vu +\cite{chin2007}, Padmatvathy et al. \cite{pc10}, propose algorithms working in a +periodic fashion where a cover set is computed at the beginning of each period. +{\it Motivated by these works, DiLCO protocol works in periods, where each + period contains a preliminary phase for information exchange and decisions, + followed by a sensing phase where one cover set is in charge of the sensing + task.} + +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 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 DiLCO protocol, the area coverage is divided into several smaller - subregions, and in each one, a node called the leader is in charge for +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 DiLCO protocol, the area coverage 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 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 (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 DiLCO protocol, each leader, in each subregion, solves an integer - program with a double objective consisting in minimizing the overcoverage and - limiting the undercoverage. This program is inspired from the work of - \cite{pedraza2006} where the objective is to maximize the number of cover - sets.} - +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 +(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 DiLCO + protocol, each leader, in each subregion, solves an integer program with a + double objective consisting in minimizing the overcoverage and limiting the + undercoverage. This program is inspired from the work of \cite{pedraza2006} + where the objective is to maximize the number of cover sets.} \section{\uppercase{Description of the DiLCO protocol}} \label{sec:The DiLCO Protocol Description} @@ -178,7 +188,6 @@ techniques: network leader election and sensor activity scheduling for coverage preservation and energy conservation, applied periodically to efficiently maximize the lifetime in the network. - \subsection{Assumptions and models} \noindent We consider a sensor network composed of static nodes distributed @@ -194,7 +203,7 @@ sensor coverage model in the literature. Thus, since a sensor has a constant sensing range $R_s$, every space points within a disk centered at a sensor with the radius of the sensing range is said to be covered by this sensor. We also assume that the communication range $R_c \geq 2R_s$. In fact, Zhang and -Zhou~\cite{Zhang05} proved that if the transmission range fulfills the previous +Hou~\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. @@ -508,15 +517,15 @@ receive such packets, we use the equation giving the energy spent to send a 1-bit-content message defined in~\cite{raghunathan2002energy} (we assume symmetric communication costs), and we set their respective size to 112 and 24~bits. The energy required to send or receive a 1-bit-content message is thus - equal to 0.2575 mW. - -Each node has an initial energy level, in Joules, which is randomly drawn in the -interval $[500-700]$. If its energy provision reaches a value below the -threshold $E_{th}=36$~Joules, the minimum energy needed for a node to stay -active during one period, it will no longer take part in the coverage task. This -value corresponds to the energy needed by the sensing phase, obtained by -multiplying the energy consumed in active state (9.72 mW) by the time in seconds -for one period (3,600 seconds), and adding the energy for the pre-sensing phases. + equal to 0.2575~mW. + +Each node has an initial energy level, in Joules, which is randomly drawn in +$[500-700]$. If its energy provision reaches a value below the threshold +$E_{th}=36$~Joules, the minimum energy needed for a node to stay active during +one period, it will no longer take part in the coverage task. This value +corresponds to the energy needed by the sensing phase, obtained by multiplying +the energy consumed in active state (9.72 mW) by the time in seconds for one +period (3,600 seconds), and adding the energy for the pre-sensing phases. According to the interval of initial energy, a sensor may be active during at most 20 periods. @@ -549,8 +558,8 @@ points in the sensing field. In our simulations, we have a layout of $N = 51 \times 26 = 1326$ grid points. \item {{\bf Energy Consumption}:} energy consumption (EC) can be seen as the - total amount of energy consumed by the sensors during $Lifetime_{95}$ or - $Lifetime_{50}$, divided by the number of periods. Formally, the computation + total amount of energy consumed by the sensors during $Lifetime_{95}$ + or $Lifetime_{50}$, divided by the number of periods. Formally, the computation of EC can be expressed as follows: \begin{equation*} \scriptsize @@ -558,22 +567,21 @@ points in the sensing field. In our simulations, we have a layout of $N = 51 + E^{a}_m+E^{s}_m \right)}{M}, \end{equation*} -where $M$ corresponds to the number of periods. The total amount of energy consumed by -the sensors (EC) comes through taking into consideration four main energy -factors. The first one, denoted $E^{\scriptsize \mbox{com}}_m$, represents the -energy consumption spent by all the nodes for wireless communications during -period $m$. $E^{\scriptsize \mbox{list}}_m$, the next factor, corresponds to -the energy consumed by the sensors in LISTENING status before receiving the -decision to go active or sleep in period $m$. $E^{\scriptsize \mbox{comp}}_m$ -refers to the energy needed by all the leader nodes to solve the integer program -during a period. Finally, $E^a_{m}$ and $E^s_{m}$ indicate the energy consumed -by the whole network in the sensing phase (active and sleeping nodes). - +where $M$ corresponds to the number of periods. The total amount of energy +consumed by the sensors (EC) comes through taking into consideration four main +energy factors. The first one, denoted $E^{\scriptsize \mbox{com}}_m$, +represents the energy consumption spent by all the nodes for wireless +communications during period $m$. $E^{\scriptsize \mbox{list}}_m$, the next +factor, corresponds to the energy consumed by the sensors in LISTENING status +before receiving the decision to go active or sleep in period $m$. +$E^{\scriptsize \mbox{comp}}_m$ refers to the energy needed by all the leader +nodes to solve the integer program during a period. Finally, $E^a_{m}$ and +$E^s_{m}$ indicate the energy consumed by the whole network in the sensing phase +(active and sleeping nodes). \end{itemize} %\end{enumerate} - %\subsection{Performance Analysis for different subregions} \subsection{Performance analysis} \label{sub1} @@ -595,16 +603,16 @@ chosen to remain active during the sensing phase. \subsubsection{Coverage ratio} Figure~\ref{fig3} shows the average coverage ratio for 150 deployed nodes. It -can be seen that both DESK and GAF provide a coverage ratio which is slightly better -compared to DiLCO in the first thirty periods. This can be easily explained by -the number of active nodes: the optimization process of our protocol activates -less nodes than DESK or GAF, resulting in a slight decrease of the coverage -ratio. In case of DiLCO-2 (respectively DiLCO-4), the coverage ratio exhibits a -fast decrease with the number of periods and reaches zero value in period~18 -(respectively 46), whereas the other versions of DiLCO, DESK, and GAF ensure a -coverage ratio above 50\% for subsequent periods. We believe that the results -obtained with these two methods can be explained by a high consumption of energy -and we will check this assumption in the next subsection. +can be seen that both DESK and GAF provide a coverage ratio which is slightly +better compared to DiLCO in the first thirty periods. This can be easily +explained by the number of active nodes: the optimization process of our +protocol activates less nodes than DESK or GAF, resulting in a slight decrease +of the coverage ratio. In case of DiLCO-2 (respectively DiLCO-4), the coverage +ratio exhibits a fast decrease with the number of periods and reaches zero value +in period~18 (respectively 46), whereas the other versions of DiLCO, DESK, and +GAF ensure a coverage ratio above 50\% for subsequent periods. We believe that +the results obtained with these two methods can be explained by a high +consumption of energy and we will check this assumption in the next subsection. Concerning DiLCO-8, DiLCO-16, and DiLCO-32, these methods seem to be more efficient than DESK and GAF, since they can provide the same level of coverage @@ -646,7 +654,14 @@ The results depict the good performance of the different versions of our protocol. Indeed, the protocols DiLCO-16/50, DiLCO-32/50, DiLCO-16/95, and DiLCO-32/95 consume less energy than their DESK and GAF counterparts for a similar level of area coverage. This observation reflects the larger number of -nodes set active by DESK and GAF. +nodes set active by DESK and GAF. Now, if we consider a same protocol, we can +notice that the average consumption per period increases slightly for our +protocol when increasing the level of coverage, whereas it increases more +largely for DESK and GAF. In case of DiLCO It means that even if a larger +network allows to improve the number of periods with a minimum coverage level +value, this improvement has a higher energy cost per period due to +communications and a more difficult optimization. However, in comparison with +DSK and GAF, our approach has a reasonable energy overhead. \subsubsection{Execution time} -- 2.39.5