X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/LiCO.git/blobdiff_plain/763029a4541714157feb2e5fd05ab5e66fd145b0..refs/heads/master:/LiCO_Journal.tex?ds=inline diff --git a/LiCO_Journal.tex b/LiCO_Journal.tex index f18c11d..051f111 100644 --- a/LiCO_Journal.tex +++ b/LiCO_Journal.tex @@ -56,12 +56,12 @@ \begin{abstract} The most important problem in a Wireless Sensor Network (WSN) is to optimize the -use of its limited energy provision, so that it can fulfill its monitoring task -as long as possible. Among known available approaches that can be used to +use of its limited energy provision, so that it can fulfill its monitoring task +as long as possible. Among known available approaches that can be used to improve power management, lifetime coverage optimization provides activity scheduling which ensures sensing coverage while minimizing the energy cost. In this paper, we propose such an approach called Perimeter-based Coverage Optimization -protocol (PeCO). It is a hybrid of centralized and distributed methods: the +protocol (PeCO). 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: @@ -69,16 +69,16 @@ distributed among sensor nodes in each subregion. %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 +The novelty of our approach lies essentially in the formulation of a new +mathematical optimization model based on the perimeter coverage level to schedule sensors' activities. Extensive simulation experiments have been performed using -OMNeT++, the discrete event simulator, to demonstrate that PeCO is capable to +OMNeT++, the discrete event simulator, to demonstrate that PeCO can offer longer lifetime coverage for WSNs in comparison with some other protocols. \end{abstract} % Note that keywords are not normally used for peerreview papers. \begin{IEEEkeywords} -Wireless Sensor Networks, Area Coverage, Network lifetime, Optimization, Scheduling. +Wireless Sensor Networks, Area Coverage, Network Lifetime, Optimization, Scheduling. \end{IEEEkeywords} \IEEEpeerreviewmaketitle @@ -105,12 +105,12 @@ The energy needed by an active sensor node to perform sensing, processing, and communication is supplied by a power supply which is a battery. This battery has a limited energy provision and it may be unsuitable or impossible to replace or recharge it in most applications. Therefore it is necessary to deploy WSN with -high density in order to increase the reliability and to exploit node redundancy +high density in order to increase reliability and to exploit node redundancy thanks to energy-efficient activity scheduling approaches. Indeed, the overlap of sensing areas can be exploited to schedule alternatively some sensors in a low power sleep mode and thus save energy. Overall, the main question that must be answered is: how to extend the lifetime coverage of a WSN as long as possible -while ensuring a high level of coverage? So, this last years many +while ensuring a high level of coverage? These past few years many energy-efficient mechanisms have been suggested to retain energy and extend the lifetime of the WSNs~\cite{rault2014energy}. @@ -125,7 +125,7 @@ This paper makes the following contributions. \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 + temporal subdivision. On the one hand, the area of interest is 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 @@ -172,7 +172,7 @@ fixed area must be monitored, while target coverage~\cite{yang2014novel} refer 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 -\cite{Deng2012} authors transform the area coverage problem to the target +\cite{Deng2012} authors transform the area coverage problem into the target coverage one taking into account the intersection points among disks of sensors nodes or between disk of sensor nodes and boundaries. In \cite{Huang:2003:CPW:941350.941367} authors prove that if the perimeters of @@ -211,14 +211,14 @@ own activity scheduling after an information exchange with its neighbors. The 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) -it may take a bad decision leading to a global suboptimal solution. Conversely, +it may make a bad decision leading to a global suboptimal solution. Conversely, centralized 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 +sensor nodes in the area. The price in communications can be 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 PeCO protocol, the area of interest @@ -227,7 +227,7 @@ higher the communication and thus the energy cost are. {\it In order to be 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. +Various coverage scheduling algorithms have been developed these past few 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 @@ -286,7 +286,7 @@ used~\cite{castano2013column,rossi2012exact,deschinkel2012column}. {\it In the \section{ The PeCO Protocol Description} \label{sec:The PeCO Protocol Description} -\noindent In this section, we describe in details our Lifetime Coverage +\noindent In this section, we describe in details our Perimeter-based Coverage Optimization protocol. First we present the assumptions we made and the models we considered (in particular the perimeter coverage one), second we describe the background idea of our protocol, and third we give the outline of the algorithm @@ -303,7 +303,7 @@ distributed in a bounded sensor field is considered. The wireless sensors are deployed in high density to ensure initially a high coverage ratio of the area of interest. We assume that all the sensor nodes are homogeneous in terms of communication, sensing, and processing capabilities and heterogeneous from -energy provision point of view. The location information is available to a +the energy provision point of view. The location information is available to a sensor node either through hardware such as embedded GPS or location discovery algorithms. We assume that each sensor node can directly transmit its measurements to a mobile sink node. For example, a sink can be an unmanned @@ -315,7 +315,7 @@ sensor nodes have a constant sensing range $R_s$. Thus, all the space points within a disk centered at a sensor with a radius equal to the sensing range are said to be covered by this sensor. We also assume that the communication range $R_c$ satisfies $R_c \geq 2 \cdot R_s$. In fact, Zhang and Zhou~\cite{Zhang05} -proved that if the transmission range fulfills the previous hypothesis, a +proved that if the transmission range fulfills the previous hypothesis, the complete coverage of a convex area implies connectivity among active nodes. The PeCO protocol uses the same perimeter-coverage model as Huang and @@ -327,9 +327,9 @@ $k$-covered if and only if each sensor in the network is $k$-perimeter-covered ( Figure~\ref{pcm2sensors}(a) shows the coverage of sensor node~$0$. On this figure, we can see that sensor~$0$ has nine neighbors and we have reported on its perimeter (the perimeter of the disk covered by the sensor) for each -neighbor the two points resulting from intersection of the two sensing +neighbor the two points resulting from the intersection of the two sensing areas. These points are denoted for neighbor~$i$ by $iL$ and $iR$, respectively -for left and right from neighbor point of view. The resulting couples of +for left and right from a neighboing point of view. The resulting couples of intersection points subdivide the perimeter of sensor~$0$ into portions called arcs. @@ -427,7 +427,7 @@ above is thus given by the sixth line of the table. %The optimization algorithm that used by PeCO protocol based on the perimeter coverage levels of the left and right points of the segments and worked to minimize the number of sensor nodes for each left or right point of the segments within each sensor node. The algorithm minimize the perimeter coverage level of the left and right points of the segments, while, it assures that every perimeter coverage level of the left and right points of the segments greater than or equal to 1. -In the PeCO protocol, scheduling of sensor nodes' activities is formulated with an +In the PeCO protocol, the scheduling of the sensor nodes' activities is formulated with an integer program based on coverage intervals. The formulation of the coverage optimization problem is detailed in~section~\ref{cp}. Note that when a sensor node has a part of its sensing range outside the WSN sensing field, as in @@ -557,7 +557,7 @@ protocol applied by a sensor node $s_k$ where $k$ is the node index in the WSN. \end{algorithm} In this algorithm, K.CurrentSize and K.PreviousSize respectively represent the -current number and the previous number of alive nodes in the subnetwork of the +current number and the previous number of living nodes in the subnetwork of the subregion. Initially, the sensor node checks its remaining energy $RE_k$, which must be greater than a threshold $E_{th}$ in order to participate in the current period. Each sensor node determines its position and its subregion using an @@ -565,7 +565,7 @@ embedded GPS or a location discovery algorithm. After that, all the sensors collect position coordinates, remaining energy, sensor node ID, and the number of their one-hop live neighbors during the information exchange. The sensors inside a same region cooperate to elect a leader. The selection criteria for the -leader, in order of priority, are: larger number of neighbors, larger remaining +leader, in order of priority, are: larger numbers of neighbors, larger remaining energy, and then in case of equality, larger index. Once chosen, the leader collects information to formulate and solve the integer program which allows to construct the set of active sensors in the sensing stage. @@ -574,11 +574,11 @@ construct the set of active sensors in the sensing stage. % The leader has the responsibility of applying the integer program algorithm (see section~\ref{cp}), which provides a set of sensors planned to be active in the sensing stage. As leader, it will send an Active-Sleep packet to each sensor in the same subregion to inform it if it has to be active or not. On the contrary, if the sensor is not the leader, it will wait for the Active-Sleep packet to know its state for the sensing stage. -\section{Lifetime Coverage problem formulation} +\section{Perimeter-based Coverage Problem Formulation} \label{cp} \noindent In this section, the coverage model is mathematically formulated. We -start with a description of the notations that will be used throughout the +start with a description of the notations that will be used throughout the section. First, we have the following sets: @@ -670,7 +670,7 @@ relative importance of satisfying the associated level of coverage. For example, weights associated with coverage intervals of a specified part of a region may be given by a relatively larger magnitude than weights associated with another region. This kind of integer program is inspired from the model developed for -brachytherapy treatment planning for optimizing dose distribution +brachytherapy treatment planning for optimizing dose distribution \cite{0031-9155-44-1-012}. The integer program must be solved by the leader in each subregion at the beginning of each sensing phase, whenever the environment has changed (new leader, death of some sensors). Note that the number of @@ -736,11 +736,11 @@ pre-sensing phases. According to the interval of initial energy, a sensor may be active during at most 20 periods. The values of $\alpha^j_i$ and $\beta^j_i$ have been chosen to ensure a good -network coverage and a longer WSN lifetime. We have given a higher priority for +network coverage and a longer WSN lifetime. We have given a higher priority to the undercoverage (by setting the $\alpha^j_i$ with a larger value than $\beta^j_i$) so as to prevent the non-coverage for the interval~$i$ of the -sensor~$j$. On the other hand, we have given a little bit lower value for -$\beta^j_i$ so as to minimize the number of active sensor nodes which contribute +sensor~$j$. On the other hand, we have assigned to +$\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute in covering the interval. We introduce the following performance metrics to evaluate the efficiency of our @@ -768,7 +768,7 @@ approach. points in the sensing field. In our simulations we have set a layout of $N~=~51~\times~26~=~1326$~grid points. \item {\bf Active Sensors Ratio (ASR)}: a major objective of our protocol is to - activate nodes as few as possible, in order to minimize the communication + activate as few nodes as possible, in order to minimize the communication overhead and maximize the WSN lifetime. The active sensors ratio is defined as follows: \begin{equation*} @@ -805,7 +805,7 @@ approach. In order to assess and analyze the performance of our protocol we have implemented PeCO protocol in OMNeT++~\cite{varga} simulator. Besides PeCO, two other protocols, described in the next paragraph, will be evaluated for -comparison purposes. The simulations were run on a laptop DELL with an Intel +comparison purposes. The simulations were run on a DELL laptop with an Intel Core~i3~2370~M (2.4~GHz) processor (2 cores) whose MIPS (Million Instructions Per Second) rate is equal to 35330. To be consistent with the use of a sensor node based on Atmels AVR ATmega103L microcontroller (6~MHz) having a MIPS rate @@ -816,7 +816,7 @@ program instance in a standard format, which is then read and solved by the optimization solver GLPK (GNU linear Programming Kit available in the public domain) \cite{glpk} through a Branch-and-Bound method. -As said previously, the PeCO is compared with three other approaches. The first +As said previously, the PeCO is compared to three other approaches. The first one, called DESK, is a fully distributed coverage algorithm proposed by \cite{ChinhVu}. The second one, called GAF~\cite{xu2001geography}, consists in dividing the monitoring area into fixed squares. Then, during the decision @@ -824,22 +824,22 @@ phase, in each square, one sensor is chosen to remain active during the sensing phase. The last one, the DiLCO protocol~\cite{Idrees2}, is an improved version of a research work we presented in~\cite{idrees2014coverage}. Let us notice that PeCO and DiLCO protocols are based on the same framework. In particular, the -choice for the simulations of a partitioning in 16~subregions was chosen because -it corresponds to the configuration producing the better results for DiLCO. The +choice for the simulations of a partitioning in 16~subregions was made because +it corresponds to the configuration producing the best results for DiLCO. The protocols are distinguished from one another by the formulation of the integer program providing the set of sensors which have to be activated in each sensing phase. DiLCO protocol tries to satisfy the coverage of a set of primary points, -whereas PeCO protocol objective is to reach a desired level of coverage for each +whereas the PeCO protocol objective is to reach a desired level of coverage for each sensor perimeter. In our experimentations, we chose a level of coverage equal to one ($l=1$). \subsubsection{\bf Coverage Ratio} Figure~\ref{fig333} shows the average coverage ratio for 200 deployed nodes -obtained with the four protocols. DESK, GAF, and DiLCO provide a little better -coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, against 98.76\% +obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better +coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, compared to the 98.76\% produced by PeCO for the first periods. This is due to the fact that at the -beginning DiLCO protocol puts in sleep status more redundant sensors (which +beginning the DiLCO protocol puts to sleep status more redundant sensors (which slightly decreases the coverage ratio), while the three other protocols activate more sensor nodes. Later, when the number of periods is beyond~70, it clearly appears that PeCO provides a better coverage ratio and keeps a coverage ratio @@ -863,7 +863,7 @@ substantial increase of the coverage performance. \subsubsection{\bf Active Sensors Ratio} Having the less active sensor nodes in each period is essential to minimize the -energy consumption and so maximize the network lifetime. Figure~\ref{fig444} +energy consumption and thus to maximize the network lifetime. Figure~\ref{fig444} shows the average active nodes ratio for 200 deployed nodes. We observe that DESK and GAF have 30.36 \% and 34.96 \% active nodes for the first fourteen rounds and DiLCO and PeCO protocols compete perfectly with only 17.92 \% and @@ -881,9 +881,9 @@ Figure \ref{fig333}. \subsubsection{\bf Energy Consumption} -We study the effect of the energy consumed by the WSN during the communication, +We studied the effect of the energy consumed by the WSN during the communication, computation, listening, active, and sleep status for different network densities -and compare it for the four approaches. Figures~\ref{fig3EC}(a) and (b) +and compared it for the four approaches. Figures~\ref{fig3EC}(a) and (b) illustrate the energy consumption for different network sizes and for $Lifetime95$ and $Lifetime50$. The results show that our PeCO protocol is the most competitive from the energy consumption point of view. As shown in both @@ -913,17 +913,17 @@ while keeping a good coverage level. \subsubsection{\bf Network Lifetime} -We observe the superiority of PeCO and DiLCO protocols in comparison against the +We observe the superiority of PeCO and DiLCO protocols in comparison with the two other approaches in prolonging the network lifetime. In Figures~\ref{fig3LT}(a) and (b), $Lifetime95$ and $Lifetime50$ are shown for different network sizes. As highlighted by these figures, the lifetime -increases with the size of the network, and it is clearly the larger for DiLCO +increases with the size of the network, and it is clearly largest for DiLCO and PeCO protocols. For instance, for a network of 300~sensors and coverage ratio greater than 50\%, we can see on Figure~\ref{fig3LT}(b) that the lifetime is about twice longer with PeCO compared to DESK protocol. The performance difference is more obvious in Figure~\ref{fig3LT}(b) than in Figure~\ref{fig3LT}(a) because the gain induced by our protocols increases with -the time, and the lifetime with a coverage of 50\% is far more longer than with + time, and the lifetime with a coverage of 50\% is far longer than with 95\%. \begin{figure}[h!] @@ -943,13 +943,13 @@ Figure~\ref{figLTALL} compares the lifetime coverage of our protocols for different coverage ratios. We denote by Protocol/50, Protocol/80, Protocol/85, Protocol/90, and Protocol/95 the amount of time during which the network can satisfy an area coverage greater than $50\%$, $80\%$, $85\%$, $90\%$, and $95\%$ -respectively, where Protocol is DiLCO or PeCO. Indeed there are applications +respectively, where the term Protocol refers to DiLCO or PeCO. Indeed there are applications that do not require a 100\% coverage of the area to be monitored. PeCO might be an interesting method since it achieves a good balance between a high level coverage ratio and network lifetime. PeCO always outperforms DiLCO for the three lower coverage ratios, moreover the improvements grow with the network size. DiLCO is better for coverage ratios near 100\%, but in that case PeCO is -not so bad for the smallest network sizes. +not ineffective for the smallest network sizes. \begin{figure}[h!] \centering \includegraphics[scale=0.5]{R/LTa.eps} @@ -963,8 +963,8 @@ not so bad for the smallest network sizes. \section{Conclusion and Future Works} \label{sec:Conclusion and Future Works} -In this paper we have studied the problem of lifetime coverage optimization in -WSNs. We have designed a new protocol, called Lifetime Coverage Optimization, which +In this paper we have studied the problem of Perimeter-based Coverage Optimization in +WSNs. We have designed a new protocol, called Perimeter-based Coverage Optimization, which schedules nodes' activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. This protocol is applied in a distributed way in regular subregions obtained after @@ -987,7 +987,7 @@ simulation results show that PeCO is more energy-efficient than other approaches, with respect to lifetime, coverage ratio, active sensors ratio, and energy consumption. %Indeed, when dealing with large and dense WSNs, a distributed optimization approach on the subregions of WSN like the one we are proposed 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. We have identified different research directions that arise out of the work presented here. -We plan to extend our framework such that the schedules are planned for multiple +We plan to extend our framework so that the schedules are planned for multiple sensing periods. %in order to compute all active sensor schedules in only one step for many periods; We also want to improve our integer program to take into account heterogeneous @@ -998,7 +998,7 @@ sensor-testbed to evaluate it in real world applications. \section*{Acknowledgments} -\noindent As a Ph.D. student, Ali Kadhum IDREES would like to gratefully +\noindent As a Ph.D. student, Ali Kadhum IDREES would like to gratefully acknowledge the University of Babylon - IRAQ for financial support and Campus France for the received support. This work is also partially funded by the Labex ACTION program (contract ANR-11-LABX-01-01).