X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/LiCO.git/blobdiff_plain/0299cb811caaea53aec64c52be67397bc055f5c8..5175c89ff4c745da83f234c9fcad6bdd08fc8eb1:/PeCO-EO/articleeo.tex?ds=sidebyside diff --git a/PeCO-EO/articleeo.tex b/PeCO-EO/articleeo.tex index 40af2f4..a80c51c 100644 --- a/PeCO-EO/articleeo.tex +++ b/PeCO-EO/articleeo.tex @@ -27,7 +27,7 @@ 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. We propose such an approach called Perimeter-based Coverage Optimization 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 +region of interest is first subdivided into subregions and the protocol is then distributed among sensor nodes in each subregion. The novelty of our approach lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule @@ -100,8 +100,8 @@ This paper makes the following contributions. -The rest of the paper is organized as follows. In the next section we review -some related work in the field. Section~\ref{sec:The PeCO Protocol Description} +The rest of the paper is organized as follows. In the next section +some related work in the field is reviewed. Section~\ref{sec:The PeCO Protocol Description} is devoted to the PeCO 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 @@ -112,9 +112,9 @@ Section~\ref{sec:Conclusion and Future Works}. \section{Related Literature} \label{sec:Literature Review} -In this section, we summarize some related works regarding the -coverage problem and distinguish our PeCO protocol from the works presented in -the literature. +In this section, some related works regarding the +coverage problem is summarized, and specific aspects of the PeCO protocol from the works presented in +the literature are presented. The most discussed coverage problems in literature can be classified in three categories~\citep{li2013survey} according to their respective monitoring @@ -129,8 +129,8 @@ nodes or between disk of sensor nodes and boundaries. In \citep{Huang:2003:CPW:941350.941367} authors prove that if the perimeters of 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 -neighbors to a sensor and $n$ is the total number of sensors in the +each sensor. $d$ denotes the maximum number of sensors that are +neighbors to a sensor, and $n$ is the total number of sensors in the network. {\it In PeCO 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.} @@ -197,11 +197,20 @@ used~\citep{castano2013column,doi:10.1080/0305215X.2012.687732,deschinkel2012col +The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage Optimization (DiLCO) protocol, maintains the coverage and improves the lifetime in WSNs. It is an improved version +of a research work they presented in~\citep{idrees2014coverage}. First, they partition the area of interest into subregions using a divide-and-conquer method. DiLCO protocol is then distributed on the sensor nodes in each subregion in a second step. DiLCO protocol combines two techniques: a leader election in each subregion, followed by an optimization-based node activity scheduling performed by each elected leader. The proposed DiLCO protocol is a periodic protocol where each period is decomposed into 4 phases: information exchange, leader election, decision, and sensing. The simulations show that DiLCO is able to increase the WSN lifetime and provides improved coverage performance. {\it In the PeCO + protocol, We have proposed a new mathematical optimization model. Instead of trying to +cover a set of specified points/targets as in DiLCO protocol, 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. The idea is that an optimal scheduling will be obtained by minimizing a weighted sum of these deviations.} + + + + \section{ The P{\scshape e}CO Protocol Description} \label{sec:The PeCO Protocol Description} -In this section, we describe in details our Perimeter-based Coverage -Optimization protocol. First we present the assumptions we made and the models +In this section, the Perimeter-based Coverage +Optimization protocol is decribed in details. 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 executed by each node. @@ -217,11 +226,7 @@ of interest. We assume that all the sensor nodes are homogeneous in terms of communication, sensing, and processing capabilities and heterogeneous from 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 -aerial vehicle (UAV) flying regularly over the sensor field to collect -measurements from sensor nodes. A mobile sink node collects the measurements and -transmits them to the base station. We consider a Boolean disk coverage model, +algorithms. We consider a Boolean disk coverage model, which is the most widely used sensor coverage model in the literature, and all 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 @@ -232,11 +237,11 @@ complete coverage of a convex area implies connectivity among active nodes. The PeCO protocol uses the same perimeter-coverage model as \citet{huang2005coverage}. It can be expressed as follows: a sensor is said to be perimeter covered if all the points on its perimeter are covered by -at least one sensor other than itself. They proved that a network area is -$k$-covered if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors). +at least one sensor other than itself. Authors \citet{huang2005coverage} proved that a network area is +$k$-covered (every point in the area covered by at least k sensors) if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors). Figure~\ref{figure1}(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 +figure, 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 the intersection of the two sensing areas. These points are denoted for neighbor~$i$ by $iL$ and $iR$, respectively @@ -259,8 +264,8 @@ Figure~\ref{figure1}(b) describes the geometric information used to find the locations of the left and right points of an arc on the perimeter of a sensor node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the west side of sensor~$u$, with the following respective coordinates in the -sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates we can -compute the euclidean distance between nodes~$u$ and $v$: $Dist(u,v)=\sqrt{\vert +sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates +the euclidean distance between nodes~$u$ and $v$ is computed: $Dist(u,v)=\sqrt{\vert u_x - v_x \vert^2 + \vert u_y-v_y \vert^2}$, while the angle~$\alpha$ is obtained through the formula: \[ @@ -274,7 +279,7 @@ Every couple of intersection points is placed on the angular interval $[0,2\pi)$ in a counterclockwise manner, leading to a partitioning of the interval. Figure~\ref{figure1}(a) illustrates the arcs for the nine neighbors of sensor $0$ and Figure~\ref{figure2} gives the position of the corresponding arcs -in the interval $[0,2\pi)$. More precisely, we can see that the points are +in the interval $[0,2\pi)$. More precisely, the points are ordered according to the measures of the angles defined by their respective positions. The intersection points are then visited one after another, starting from the first intersection point after point~zero, and the maximum level of @@ -471,10 +476,10 @@ construct the set of active sensors in the sensing stage. \section{Perimeter-based Coverage Problem Formulation} \label{cp} -In this section, the coverage model is mathematically formulated. We -start with a description of the notations that will be used throughout the +In this section, the coverage model is mathematically formulated. The following +notations are used throughout the section.\\ -First, we have the following sets: +First, the following sets: \begin{itemize} \item $S$ represents the set of WSN sensor nodes; \item $A \subseteq S $ is the subset of alive sensors; @@ -495,7 +500,7 @@ a^j_{ik} = \left \{ \end{equation} Note that $a^k_{ik}=1$ by definition of the interval. -Second, we define several binary and integer variables. Hence, each binary +Second, several binary and integer variables are defined. Hence, each binary variable $X_{k}$ determines the activation of sensor $k$ in the sensing phase ($X_k=1$ if the sensor $k$ is active or 0 otherwise). $M^j_i$ is an integer variable which measures the undercoverage for the coverage interval $i$ @@ -510,7 +515,7 @@ sensor $j$ is given by $\sum_{k \in A} a^j_{ik} X_k$. To extend the network lifetime, the objective is to activate a minimal number of sensors in each period to ensure the desired coverage level. As the number of alive sensors decreases, it becomes impossible to reach the desired level of coverage for all -coverage intervals. Therefore we use variables $M^j_i$ and $V^j_i$ as a measure +coverage intervals. Therefore variables $M^j_i$ and $V^j_i$ are introduced as a measure of the deviation between the desired number of active sensors in a coverage interval and the effective number. And we try to minimize these deviations, first to force the activation of a minimal number of sensors to ensure the @@ -527,8 +532,8 @@ Our coverage optimization problem can then be mathematically expressed as follow \begin{array}{ll} \min \sum_{j \in S} \sum_{i \in I_j} (\alpha^j_i ~ M^j_i + \beta^j_i ~ V^j_i )&\\ \textrm{subject to :}&\\ -\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i \geq l \quad \forall i \in I_j, \forall j \in S\\ -\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i \leq l \quad \forall i \in I_j, \forall j \in S\\ +\sum_{k \in A} ( a^j_{ik} ~ X_{k}) + M^j_i = l \quad \forall i \in I_j, \forall j \in S\\ +\sum_{k \in A} ( a^j_{ik} ~ X_{k}) - V^j_i = l \quad \forall i \in I_j, \forall j \in S\\ X_{k} \in \{0,1\}, \forall k \in A \end{array} \right. @@ -544,9 +549,9 @@ brachytherapy treatment planning for optimizing dose distribution 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 constraints in the model is constant (constraints of coverage expressed for all -sensors), whereas the number of variables $X_k$ decreases over periods, since we -consider only alive sensors (sensors with enough energy to be alive during one -sensing phase) in the model. +sensors), whereas the number of variables $X_k$ decreases over periods, since +only alive sensors (sensors with enough energy to be alive during one +sensing phase) are considered in the model. \section{Performance Evaluation and Analysis} \label{sec:Simulation Results and Analysis} @@ -580,7 +585,7 @@ Initial energy & in range 500-700~Joules \\ Sensing period & duration of 60 minutes \\ $E_{th}$ & 36~Joules\\ $R_s$ & 5~m \\ - +$R_c$ & 10~m \\ $\alpha^j_i$ & 0.6 \\ $\beta^j_i$ & 0.4 @@ -604,14 +609,14 @@ 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 to +network coverage and a longer WSN lifetime. Higher priority is given 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 assigned to -$\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute +sensor~$j$. On the other hand, +$\beta^j_i$ is assigned to 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 +The following performance metrics are used to evaluate the efficiency of the approach. @@ -625,7 +630,7 @@ approach. because without network connectivity a sensor may not be able to send to a base station an event it has sensed. \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 + observe the area of interest. In our case, the sensor field is discretized as a regular grid, which yields the following equation: @@ -637,8 +642,8 @@ approach. where $n$ is the number of covered grid points by active sensors of every subregions during the current sensing phase and $N$ is total number of grid - points in the sensing field. In our simulations we have set a layout of - $N~=~51~\times~26~=~1326$~grid points. + points in the sensing field. In simulations a layout of + $N~=~51~\times~26~=~1326$~grid points is considered. \item {\bf Active Sensors Ratio (ASR)}: a major objective of our protocol is to 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 @@ -827,40 +832,44 @@ not ineffective for the smallest network sizes. \end{figure} +\subsubsection{\bf Impact of $\alpha$ and $\beta$ on PeCO's performance} +Table~\ref{my-labelx} explains all possible network lifetime result of the relation between the different values of $\alpha$ and $\beta$, and for a network size equal to 200 sensor nodes. As can be seen in Table~\ref{my-labelx}, it is obvious and clear that when $\alpha$ decreased and $\beta$ increased by any step, the network lifetime for $Lifetime_{50}$ increased and the $Lifetime_{95}$ decreased. Therefore, selecting the values of $\alpha$ and $\beta$ depend on the application type used in the sensor nework. In PeCO protocol, $\alpha$ and $\beta$ are chosen based on the largest value of network lifetime for $Lifetime_{95}$. + +\begin{table}[h] +\centering +\caption{The impact of $\alpha$ and $\beta$ on PeCO's performance} +\label{my-labelx} +\begin{tabular}{|c|c|c|c|} +\hline +$\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline +0.0 & 1.0 & 151 & 0 \\ \hline +0.1 & 0.9 & 145 & 0 \\ \hline +0.2 & 0.8 & 140 & 0 \\ \hline +0.3 & 0.7 & 134 & 0 \\ \hline +0.4 & 0.6 & 125 & 0 \\ \hline +0.5 & 0.5 & 118 & 30 \\ \hline +0.6 & 0.4 & 94 & 57 \\ \hline +0.7 & 0.3 & 97 & 49 \\ \hline +0.8 & 0.2 & 90 & 52 \\ \hline +0.9 & 0.1 & 77 & 50 \\ \hline +1.0 & 0.0 & 60 & 44 \\ \hline +\end{tabular} +\end{table} \section{Conclusion and Future Works} \label{sec:Conclusion and Future Works} -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 -partitioning the area of interest in a preliminary step. It works in periods and -is based on the resolution of an integer program to select the subset of sensors -operating in active status for each period. Our work is original in so far as it -proposes for the first time an integer program scheduling the activation of -sensors based on their perimeter coverage level, instead of using a set of -targets/points to be covered. - - -We have carried out several simulations to evaluate the proposed protocol. The -simulation results show that PeCO is more energy-efficient than other -approaches, with respect to lifetime, coverage ratio, active sensors ratio, and -energy consumption. +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 partitioning the area of interest in a preliminary step. It works in periods and +is based on the resolution of an integer program to select the subset of sensors operating in active status for each period. Our work is original in so far as it proposes for the first time an integer program scheduling the activation of sensors based on their perimeter coverage level, instead of using a set of targets/points to be covered. -We plan to extend our framework so that the schedules are planned for multiple -sensing periods. -We also want to improve our integer program to take into account heterogeneous -sensors from both energy and node characteristics point of views. +We have carried out several simulations to evaluate the proposed protocol. The simulation results show that PeCO is more energy-efficient than other approaches, with respect to lifetime, coverage ratio, active sensors ratio, and energy consumption. -Finally, it would be interesting to implement our protocol using a -sensor-testbed to evaluate it in real world applications. +We plan to extend our framework so that the schedules are planned for multiple sensing periods. We also want to improve our integer program to take into account heterogeneous sensors from both energy and node characteristics point of views. Finally, it would be interesting to implement our protocol using a sensor-testbed to evaluate it in real world applications. \bibliographystyle{gENO} -\bibliography{biblio} +\bibliography{biblio} %articleeo \end{document}