X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/Sensornets15.git/blobdiff_plain/c35114ab237b0488ab602957292a66784de10953..b8c6a5f1e74fdd26f663b1c0dd6454e15e84df73:/Example.tex?ds=sidebyside diff --git a/Example.tex b/Example.tex index db1b822..41f84a1 100644 --- a/Example.tex +++ b/Example.tex @@ -12,7 +12,7 @@ \usepackage{apalike} \usepackage{SCITEPRESS} \usepackage[small]{caption} - +\usepackage{color} \usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e} \usepackage{mathtools} @@ -50,14 +50,18 @@ Optimization, Scheduling.} scheduling performed by each elected leader. This two-step process takes place periodically, in order to choose a small set of nodes remaining active for sensing during a time slot. Each set is built to ensure coverage at a low - energy cost, allowing to optimize the network lifetime. More precisely, a - period consists of four phases: (i)~Information Exchange, (ii)~Leader - Election, (iii)~Decision, and (iv)~Sensing. The decision process, which + energy cost, allowing to optimize the network lifetime. + %More precisely, a + %period consists of four phases: (i)~Information Exchange, (ii)~Leader + %Election, (iii)~Decision, and (iv)~Sensing. + The decision process, which results in an activity scheduling vector, is carried out by a leader node - through the solving of an integer program. In comparison with some other - protocols, the simulations done using the discrete event simulator OMNeT++ - show that our approach is able to increase the WSN lifetime and provides - improved coverage performance. } + through the solving of an integer program. + {\color{red} Simulations are conducted using the discret event simulator OMNET++. + We refer to the characterictics of a Medusa II sensor for the energy consumption and the time computation. + In comparison with two other existing methods, our approach is able to increase the WSN lifetime and provides + improved coverage performance. }} + \onecolumn \maketitle \normalsize \vfill @@ -95,83 +99,95 @@ same subregion, in order to choose in a suitable manner a sensor node (the leader) to carry out the coverage strategy. In each subregion the activation of the sensors for the sensing phase of the current period is obtained by solving an integer program. The resulting activation vector is broadcast by a leader -to every node of its subregion. +to every node of its subregion. + +{\color{red} Our previous paper ~\cite{idrees2014coverage} relies almost exclusively on the framework of the DiLCO approach and the coverage problem formulation. +In this paper we strengthen our simulations by taking into account the characteristics of a Medusa II sensor ~\cite{raghunathan2002energy} to measure the energy consumption and the computation time. +We have implemented two other existing approaches (a distributed one DESK ~\cite{ChinhVu} and a centralized one GAF ~\cite{xu2001geography}) in order to compare their performances with our approach. +We also focus on performance analysis based on the number of subregions. } + The remainder of the paper continues with Section~\ref{sec:Literature Review} 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. -%For instance, in order to hide the occurrence of faults, or the sudden unavailability of -%sensor nodes, some distributed algorithms have been developed in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02}. -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} @@ -182,7 +198,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 @@ -198,7 +213,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. @@ -212,7 +227,6 @@ less accurate according to the number of primary points. \subsection{Main idea} \label{main_idea} - \noindent We start by applying a divide-and-conquer algorithm to partition the area of interest into smaller areas called subregions and then our protocol is executed simultaneously in each subregion. @@ -278,9 +292,6 @@ not. Alternately, if the sensor is not the leader, it will wait for the Active-Sleep packet to know its state for the coming sensing phase. - - - \begin{algorithm}[h!] \BlankLine @@ -322,6 +333,68 @@ Active-Sleep packet to know its state for the coming sensing phase. \section{\uppercase{Coverage problem formulation}} \label{cp} +{\color{red} +We formulate the coverage optimization problem with an integer program. +The objective function consists in minimizing the undercoverage and the overcoverage of the area as suggested in \cite{pedraza2006}. +The area coverage problem is transformed to the coverage of a fraction of points called primary points. +Details on the choice and the number of primary points can be found in \cite{idrees2014coverage}. The set of primary points is denoted by $P$ +and the set of sensors by $J$. As we consider a boolean disk coverage model, we use the boolean indicator $\alpha_{jp}$ which is equal to 1 if the primary point $p$ is in the sensing range of the sensor $j$. The binary variable $X_j$ represents the activation or not of the sensor $j$. So we can express the number of active sensors that cover the primary point $p$ by $\sum_{j \in J} \alpha_{jp} * X_{j}$. We deduce the overcoverage denoted by $\Theta_p$ of the primary point $p$ : +\begin{equation} + \Theta_{p} = \left \{ +\begin{array}{l l} + 0 & \mbox{if the primary point}\\ + & \mbox{$p$ is not covered,}\\ + \left( \sum_{j \in J} \alpha_{jp} * X_{j} \right)- 1 & \mbox{otherwise.}\\ +\end{array} \right. +\label{eq13} +\end{equation} +More precisely, $\Theta_{p}$ represents the number of active sensor +nodes minus one that cover the primary point~$p$. +In the same way, we define the undercoverage variable +$U_{p}$ of the primary point $p$ as: +\begin{equation} +U_{p} = \left \{ +\begin{array}{l l} + 1 &\mbox{if the primary point $p$ is not covered,} \\ + 0 & \mbox{otherwise.}\\ +\end{array} \right. +\label{eq14} +\end{equation} +There is, of course, a relationship between the three variables $X_j$, $\Theta_p$ and $U_p$ which can be formulated as follows : +\begin{equation} +\sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, \forall p \in P +\end{equation} +If the point $p$ is not covered, $U_p=1$, $\sum_{j \in J} \alpha_{jp} X_{j}=0$ and $\Theta_{p}=0$ by defintion, so the equality is satisfied. +On the contrary, if the point $p$ is covered, $U_p=0$, and $\Theta_{p}=\left( \sum_{j \in J} \alpha_{jp} X_{j} \right)- 1$. +\noindent Our coverage optimization problem can then be formulated as follows: +\begin{equation} \label{eq:ip2r} +\left \{ +\begin{array}{ll} +\min \sum_{p \in P} (w_{\theta} \Theta_{p} + w_{U} U_{p})&\\ +\textrm{subject to :}&\\ +\sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, &\forall p \in P\\ +%\label{c1} +%\sum_{t \in T} X_{j,t} \leq \frac{RE_j}{e_t} &\forall j \in J \\ +%\label{c2} +\Theta_{p}\in \mathbb{N}, &\forall p \in P\\ +U_{p} \in \{0,1\}, &\forall p \in P \\ +X_{j} \in \{0,1\}, &\forall j \in J +\end{array} +\right. +\end{equation} +The objective function is a weighted sum of overcoverage and undercoverage. The goal is to limit the overcoverage in order to activate a minimal number of sensors while simultaneously preventing undercoverage. Both weights $w_\theta$ and $w_U$ must be carefully chosen in +order to guarantee that the maximum number of points are covered during each +period. +} + + + + + + + +\iffalse + \indent Our model is based on the model proposed by \cite{pedraza2006} where the objective is to find a maximum number of disjoint cover sets. To accomplish this goal, the authors proposed an integer program which forces undercoverage @@ -410,6 +483,8 @@ undercoverage. Both weights $w_\theta$ and $w_U$ must be carefully chosen in order to guarantee that the maximum number of points are covered during each period. +\fi + \section{\uppercase{Protocol evaluation}} \label{sec:Simulation Results and Analysis} \noindent \subsection{Simulation framework} @@ -516,15 +591,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. @@ -542,8 +617,7 @@ the efficiency of our approach: connectivity is crucial because an active sensor node without connectivity towards a base station cannot transmit any information regarding an observed event in the area that it monitors. - - + \item {{\bf Coverage Ratio (CR)}:} it measures how well the WSN is able to observe the area of interest. In our case, we discretized the sensor field as a regular grid, which yields the following equation to compute the @@ -556,16 +630,10 @@ where $n$ is the number of covered grid points by active sensors of every subregions during the current sensing phase and $N$ is the total number of grid points in the sensing field. In our simulations, we have a layout of $N = 51 \times 26 = 1326$ grid points. -%The accuracy of this method depends on the distance between grids. In our -%simulations, the sensing field has been divided into 50 by 25 grid points, which means -%there are $51 \times 26~ = ~ 1326$ points in total. -% Therefore, for our simulations, the error in the coverage calculation is less than ~ 1 $\% $. - - \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 @@ -573,24 +641,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} @@ -612,16 +677,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 @@ -655,7 +720,7 @@ used for the different performance metrics. \begin{figure}[h!] \centering \includegraphics[scale=0.45]{R/EC.pdf} -\caption{Energy consumption} +\caption{Energy consumption per period} \label{fig95} \end{figure} @@ -663,11 +728,16 @@ 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. -%In fact, a distributed method on the subregions greatly reduces the number of communications and the time of listening so thanks to the partitioning of the initial network into several independent subnetworks. -%As shown in Figures~\ref{fig95} and ~\ref{fig50} , DiLCO-2 consumes more energy than the other versions of DiLCO, especially for large sizes of network. This is easy to understand since the bigger the number of sensors involved in the integer program, the larger the time computation to solve the optimization problem as well as the higher energy consumed during the communication. +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 and the number of node, 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 communication overhead and a more +difficult optimization problem. However, in comparison with DESK and GAF, our +approach has a reasonable energy overcost. \subsubsection{Execution time} @@ -702,8 +772,6 @@ prevents it to ensure a good coverage especially on the borders of subregions. Thus, the optimal number of subregions can be seen as a trade-off between execution time and coverage performance. -%The DiLCO-32 has more suitable times in the same time it turn on redundent nodes more. We think that in distributed fashion the solving of the optimization problem in a subregion can be tackled by sensor nodes. Overall, to be able to deal with very large networks, a distributed method is clearly required. - \subsubsection{Network lifetime} In the next figure, the network lifetime is illustrated. Obviously, the lifetime @@ -728,7 +796,6 @@ the larger level of coverage ($95\%$) in the case of our protocol, the subdivi in $16$~subregions seems to be the most appropriate. - \section{\uppercase{Conclusion and future work}} \label{sec:Conclusion and Future Works} @@ -755,8 +822,6 @@ there is an optimal number of subregions. Therefore, in case of our simulation context a subdivision in $16$~subregions seems to be the most relevant. The optimal number of subregions will be investigated in the future. - - \section*{\uppercase{Acknowledgements}} \noindent As a Ph.D. student, Ali Kadhum IDREES would like to gratefully