X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/LiCO.git/blobdiff_plain/6218ab50f32a9fd3c09d40b9196ce96128536e11..8d0a87bd6a095ec213dc2af5220c6e4904f7e4c0:/PeCO-EO/articleeo.tex?ds=sidebyside diff --git a/PeCO-EO/articleeo.tex b/PeCO-EO/articleeo.tex index a80c51c..215576a 100644 --- a/PeCO-EO/articleeo.tex +++ b/PeCO-EO/articleeo.tex @@ -91,8 +91,7 @@ This paper makes the following contributions. simulator OMNeT++, to demonstrate the efficiency of our protocol. We have compared our PeCO protocol to two approaches found in the literature: DESK~\citep{ChinhVu} and GAF~\citep{xu2001geography}, and also to our previous - work published in~\citep{Idrees2} which is based on another optimization model - for sensor scheduling. + protocol DilCO published in~\citep{Idrees2}. DilCO uses the same framework as PeCO but is based on another optimization model for sensor scheduling. \end{enumerate} @@ -197,7 +196,7 @@ 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 +The authors in \citep{Idrees2} propose a Distributed Lifetime Coverage Optimization (DiLCO) protocol, which 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 @@ -209,11 +208,11 @@ on perimeter coverage of each sensor. The model involves integer variables to ca \section{ The P{\scshape e}CO Protocol Description} \label{sec:The PeCO Protocol Description} -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. +%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. \subsection{Assumptions and Models} @@ -278,7 +277,7 @@ The arc on the perimeter of~$u$ defined by the angular interval $[\pi 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 +sensor $0$ and table~\ref{my-label} gives the position of the corresponding arcs 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 @@ -336,7 +335,7 @@ above is thus given by the sixth line of the table. 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 +mixed-doi:10.1155/2010/926075integer 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 Figure~\ref{figure3}, the maximum coverage level for this arc is set to $\infty$ @@ -357,7 +356,7 @@ optimization algorithm. The WSN area of interest is, in a first step, divided into regular homogeneous subregions using a divide-and-conquer algorithm. In a second step our protocol will be executed in a distributed way in each subregion -simultaneously to schedule nodes' activities for one sensing period. +simultaneously to schedule nodes' activities for one sensing period. In the study, sensors are assumed to be deployed almost uniformly over the region. The regular subdivision is made such that the number of hops between any pairs of sensors inside a subregion is less than or equal to 3. As shown in Figure~\ref{figure4}, node activity scheduling is produced by our protocol in a periodic manner. Each period is divided into 4 stages: Information @@ -375,7 +374,7 @@ taken into account since the sensors can update and then exchange their information (including their residual energy) at the beginning of each period. However, the pre-sensing phases (INFO Exchange, Leader Election, and Decision) are energy consuming, even for nodes that will not join the set cover to monitor -the area. +the area. Sensing period duration is adapted according to the QoS requirements of the application. \begin{figure}[t!] \centering @@ -476,8 +475,9 @@ 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. The following -notations are used throughout the +In this section, the perimeter-based coverage problem is mathematically formulated. It has been proved to be a NP-hard problem by\citep{doi:10.1155/2010/926075}. Authors study the coverage of the perimeter of a large object requiring to be monitored. For the proposed formulation in this paper, the large object to be monitored is the sensor itself (or more precisely its sensing area). + +The following notations are used throughout the section.\\ First, the following sets: \begin{itemize} @@ -500,16 +500,16 @@ a^j_{ik} = \left \{ \end{equation} Note that $a^k_{ik}=1$ by definition of the interval. -Second, several binary and integer variables are defined. Hence, each binary +Second, several 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 +($X_k=1$ if the sensor $k$ is active or 0 otherwise). $M^j_i$ is a variable which measures the undercoverage for the coverage interval $i$ corresponding to sensor~$j$. In the same way, the overcoverage for the same coverage interval is given by the variable $V^j_i$. -If we decide to sustain a level of coverage equal to $l$ all along the perimeter -of sensor $j$, we have to ensure that at least $l$ sensors involved in each -coverage interval $i \in I_j$ of sensor $j$ are active. According to the +To sustain a level of coverage equal to $l$ all along the perimeter +of sensor $j$, at least $l$ sensors involved in each +coverage interval $i \in I_j$ of sensor $j$ have to be active. According to the previous notations, the number of active sensors in the coverage interval $i$ of 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 @@ -525,33 +525,37 @@ to reach a coverage level as close as possible to the desired one. -Our coverage optimization problem can then be mathematically expressed as follows: +The coverage optimization problem can then be mathematically expressed as follows: \begin{equation} \left \{ \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 = 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 +\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\\ +X_{k} \in \{0,1\}, \forall k \in A \\ +M^j_i, V^j_i \in \mathbb{R}^{+} \end{array} \right. \end{equation} +If a given level of coverage $l$ is required for one sensor, the sensor is said to be undercovered (respectively overcovered) if the level of coverage of one of its CI is less (respectively greater) than $l$. If the sensor $j$ is undercovered, there exists at least one of its CI (say $i$) for which the number of active sensors (denoted by $l^{i}$) covering this part of the perimeter is less than $l$ and in this case : $M_{i}^{j}=l-l^{i}$, $V_{i}^{j}=0$. In the contrary, if the sensor $j$ is overcovered, there exists at least one of its CI (say $i$) for which the number of active sensors (denoted by $l^{i}$) covering this part of the perimeter is greater than $l$ and in this case : $M_{i}^{j}=0$, $V_{i}^{j}=l^{i}-l$. + $\alpha^j_i$ and $\beta^j_i$ are nonnegative weights selected according to the 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 +region. This kind of mixed-integer program is inspired from the model developed for brachytherapy treatment planning for optimizing dose distribution -\citep{0031-9155-44-1-012}. The integer program must be solved by the leader in +\citep{0031-9155-44-1-012}. The choice of variables $\alpha$ and $\beta$ should be made according to the needs of the application. $\alpha$ should be enough large to prevent undercoverage and so to reach the highest possible coverage ratio. $\beta$ should be enough large to prevent overcoverage and so to activate a minimum number of sensors. +The mixed-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 constraints in the model is constant (constraints of coverage expressed for all 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. +sensing phase) are considered in the model. \section{Performance Evaluation and Analysis} \label{sec:Simulation Results and Analysis} @@ -797,8 +801,8 @@ ratio greater than 50\%, we can see on Figure~\ref{figure8}(b) that the lifetim is about twice longer with PeCO compared to DESK protocol. The performance difference is more obvious in Figure~\ref{figure8}(b) than in Figure~\ref{figure8}(a) because the gain induced by our protocols increases with - time, and the lifetime with a coverage of 50\% is far longer than with -95\%. + time, and the lifetime with a coverage over 50\% is far longer than with +95\%. \begin{figure}[h!] \centering @@ -833,7 +837,8 @@ not ineffective for the smallest network sizes. \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}$. +Table~\ref{my-labelx} shows network lifetime results for the different values of $\alpha$ and $\beta$, and for a network size equal to 200 sensor nodes. The choice of $\beta \gg \alpha$ prevents the overcoverage, and so limit the activation of a large number of sensors, but as $\alpha$ is low, some areas may be poorly covered. This explains the results obtained for {\it Lifetime50} with $\beta \gg \alpha$: a large number of periods with low coverage ratio. With $\alpha \gg \beta$, we priviligie the coverage even if some areas may be overcovered, so high coverage ratio is reached, but a large number of sensors are activated to achieve this goal. Therefore network lifetime is reduced. The choice $\alpha=0.6$ and $\beta=0.4$ seems to achieve the best compromise between lifetime and coverage ratio. +%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 @@ -848,7 +853,7 @@ $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \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 +{\bf 0.6} & {\bf 0.4} & {\bf 94} & {\bf 57} \\ \hline 0.7 & 0.3 & 97 & 49 \\ \hline 0.8 & 0.2 & 90 & 52 \\ \hline 0.9 & 0.1 & 77 & 50 \\ \hline