From 6f5a87acc5438d5384b912e12224586f3e757f32 Mon Sep 17 00:00:00 2001 From: raphael couturier Date: Thu, 15 Jan 2015 15:32:48 +0100 Subject: [PATCH 1/1] reading until the end of IV --- LiCO_Journal.tex | 78 +++++++++++++++++++++++------------------------- 1 file changed, 38 insertions(+), 40 deletions(-) diff --git a/LiCO_Journal.tex b/LiCO_Journal.tex index 02be4ac..7e788d4 100644 --- a/LiCO_Journal.tex +++ b/LiCO_Journal.tex @@ -64,16 +64,15 @@ this paper, we propose such an approach called Lifetime Coverage Optimization protocol (LiCO). 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. -%%RAPH abstract too long -% A sensor node which runs LiCO -%protocol repeats periodically four stages: information exchange, leader -%election, optimization decision, and sensing. 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 +% A sensor node which runs LiCO protocol repeats periodically four stages: +%information exchange, leader election, optimization decision, and sensing. +%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 sensors' activities. Extensive simulation experiments have been performed using -OMNeT++, the discrete event simulator, to demonstrate that LiCO is capable to +OMNeT++, the discrete event simulator, to demonstrate that LiCO is capable to offer longer lifetime coverage for WSNs in comparison with some other protocols. \end{abstract} @@ -319,7 +318,7 @@ $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 complete coverage of a convex area implies connectivity among active nodes. -LiCO protocol uses the same perimeter-coverage model than Huang and +The LiCO protocol uses the same perimeter-coverage model as Huang and Tseng in~\cite{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 @@ -359,17 +358,17 @@ obtained through the formula: $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} 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{pcm2sensors}(a) illustrates the arcs for the nine neighbors of -sensor $0$ and figure~\ref{expcm} gives the position of the corresponding arcs +sensor $0$ and Figure~\ref{expcm} gives the position of the corresponding arcs in the interval $[0,2\pi]$. More precisely, we can see that 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 first intersection point after point~zero, and the maximum level of +from the first intersection point after point~zero, and the maximum level of coverage is determined for each interval defined by two successive points. The maximum level of coverage is equal to the number of overlapping arcs. For example, between~$5L$ and~$6L$ the maximum level of coverage is equal to $3$ -(the value is highlighted in yellow at the bottom of figure~\ref{expcm}), which -means that at most 2~neighbors can cover the perimeter in addition to node $0$. +(the value is highlighted in yellow at the bottom of Figure~\ref{expcm}), which +means that at most 2~neighbors can cover the perimeter in addition to node $0$. Table~\ref{my-label} summarizes for each coverage interval the maximum level of coverage and the sensor nodes covering the perimeter. The example discussed above is thus given by the sixth line of the table. @@ -428,11 +427,11 @@ above is thus given by the sixth line of the table. %The optimization algorithm that used by LiCO 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 LiCO protocol, scheduling of sensor nodes' activities is formulated with an +In the LiCO protocol, scheduling of 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 -figure~\ref{ex4pcm}, the maximum coverage level for this arc is set to $\infty$ +Figure~\ref{ex4pcm}, the maximum coverage level for this arc is set to $\infty$ and the corresponding interval will not be taken into account by the optimization algorithm. @@ -457,14 +456,14 @@ 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. -As shown in figure~\ref{fig2}, node activity scheduling is produced by our +As shown in Figure~\ref{fig2}, node activity scheduling is produced by our protocol in a periodic manner. Each period is divided into 4 stages: Information (INFO) Exchange, Leader Election, Decision (the result of an optimization problem), and Sensing. For each period there is exactly one set cover responsible for the sensing task. Protocols based on a periodic scheme, like LiCO, are more robust against an unexpected node failure. On the one hand, if -node failure is discovered before taking the decision, the corresponding sensor -node will not be considered by the optimization algorithm, and, on the other +a node failure is discovered before taking the decision, the corresponding sensor +node will not be considered by the optimization algorithm. On the other hand, if the sensor failure happens after the decision, the sensing task of the network will be temporarily affected: only during the period of sensing until a new period starts, since a new set cover will take charge of the sensing task in @@ -543,7 +542,7 @@ protocol applied by a sensor node $s_k$ where $k$ is the node index in the WSN. } \emph{$s_k.status$ = COMMUNICATION}\; - \emph{Send $ActiveSleep()$ to each node $l$ in subregion} \; + \emph{Send $ActiveSleep()$ to each node $l$ in subregion}\; \emph{Update $RE_k $}\; } \Else{ @@ -557,20 +556,19 @@ protocol applied by a sensor node $s_k$ where $k$ is the node index in the WSN. \label{alg:LiCO} \end{algorithm} -In this algorithm, K.CurrentSize and K.PreviousSize refer to the current size -and the previous size of the subnetwork in the subregion respectively. That -means the number of sensor nodes which are still alive. 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 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 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. +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 +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 +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 +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. %After the cooperation among the sensor nodes in the same subregion, the leader will be elected in distributed way, where each sensor node and based on it's information decide who is the leader. The selection criteria for the leader in order of priority are: larger number of neighbors, larger remaining energy, and then in case of equality, larger index. Thereafter, if the sensor node is leader, it will execute the perimeter-coverage model for each sensor in the subregion in order to determine the segment points which would be used in the next stage by the optimization algorithm of the LiCO protocol. Every sensor node is selected as a leader, it is executed the perimeter coverage model only one time during it's life in the network. @@ -592,7 +590,7 @@ First, we have the following sets: \end{itemize} $I_j$ refers to the set of coverage intervals which have been defined according to the method introduced in subsection~\ref{CI}. For a coverage interval $i$, -let $a^j_{ik}$ denote the indicator function of whether sensor~$k$ is involved +let $a^j_{ik}$ denotes the indicator function of whether sensor~$k$ is involved in coverage interval~$i$ of sensor~$j$, that is: \begin{equation} a^j_{ik} = \left \{ @@ -670,7 +668,7 @@ X_{k} \in \{0,1\}, \forall k \in A $\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 a relatively larger magnitude than weights associated with another +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 \cite{0031-9155-44-1-012}. The integer program must be solved by the leader in @@ -872,7 +870,7 @@ rounds and DiLCO and LiCO protocols compete perfectly with only 17.92 \% and 20.16 \% active nodes during the same time interval. As the number of periods increases, LiCO protocol has a lower number of active nodes in comparison with the three other approaches, while keeping a greater coverage ratio as shown in -figure \ref{fig333}. +Figure \ref{fig333}. \begin{figure}[h!] \centering @@ -917,14 +915,14 @@ while keeping a good coverage level. We observe the superiority of LiCO and DiLCO protocols in comparison against the two other approaches in prolonging the network lifetime. In -figures~\ref{fig3LT}(a) and (b), $Lifetime95$ and $Lifetime50$ are shown for +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 and LiCO 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 +ratio greater than 50\%, we can see on Figure~\ref{fig3LT}(b) that the lifetime is about two times longer with LiCO 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 +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 95\%. -- 2.39.5