From: ali Date: Thu, 2 Jul 2015 09:31:33 +0000 (+0200) Subject: Update by Ali X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/commitdiff_plain/2110bab7680fe505290f47faca142b5fb67a3f2d Update by Ali --- diff --git a/CHAPITRE_06.tex b/CHAPITRE_06.tex index aeb9ffa..33c8fa3 100644 --- a/CHAPITRE_06.tex +++ b/CHAPITRE_06.tex @@ -17,7 +17,7 @@ In this chapter, we propose an approach called Perimeter-based Coverage Optimization protocol (PeCO). %The PeCO protocol merges between two energy efficient mechanisms, which are used the main advantages of the centralized and distributed approaches and avoids the most of their disadvantages. An energy-efficient activity scheduling mechanism based new optimization model is performed by each leader in the subregions. -The scheme is similar to the one described in section \ref{ch4:sec:02:03}. But in this approach, the optimization model is based on the perimeter coverage model in order to produce the optimal cover set of active sensors, which are taken the responsibility of sensing during the current period. +The scheme is similar to the one described in section \ref{ch4:sec:02:03}. But in this approach, the optimization model is based on the perimeter coverage model in order to produce the optimal cover set of active sensors, which are taking the responsibility of sensing during the current period. The rest of the chapter is organized as follows. The next section is devoted to the PeCO protocol description and section~\ref{ch6:sec:03} focuses on the coverage model formulation which is used to schedule the activation of sensor nodes. Section~\ref{ch6:sec:04} presents simulation results and discusses the comparison with other approaches. Finally, concluding remarks are drawn in section~\ref{ch6:sec:05}. @@ -57,8 +57,8 @@ arcs. \end{figure} Figure~\ref{pcm2sensors}(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, the euclidean distance between nodes~$u$ and $v$ is computed as follow: $Dist(u,v)=\sqrt{\vert - u_x - v_x \vert^2 + \vert u_y-v_y \vert^2}$, +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, the euclidean distance between nodes~$u$ and $v$ is computed as follow: $Dist(u,v)=\sqrt{\left( + u_x - v_x \right)^2 + \left( u_y-v_y \right)^2}$, while the angle~$\alpha$ is obtained through the formula: @@ -180,8 +180,8 @@ protocol applied by a sensor node $s_j$ where $j$ is the node index in the WSN. \emph{ Use the same previous cover set for current sensing stage}\; } \Else{ - \emph{Update $a^j_{ik}$; prepare data for IP~Algorithm}\; - \emph{$\left\{\left(X_{1},\dots,X_{k},\dots,X_{A}\right)\right\}$ = Execute Integer Program Algorithm($A$)}\; + \emph{Update $a^j_{ik}$; prepare data for MIP~Algorithm}\; + \emph{$\left\{\left(X_{1},\dots,X_{k},\dots,X_{A}\right)\right\}$ = Execute MIP Algorithm($A$)}\; \emph{A.PreviousSize = A.CurrentSize}\; } @@ -287,7 +287,9 @@ With the performance metrics, described in section \ref{ch4:sec:04:04}, we evalu In order to assess and analyze the performance of our protocol we have implemented PeCO protocol in OMNeT++~\cite{ref158} simulator. %Besides PeCO, three other protocols, described in the next paragraph, will be evaluated for comparison purposes. %The simulations were run on a laptop DELL 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 equal to 6, the original execution time on the laptop is multiplied by 2944.2 $\left(\frac{35330}{2} \times \frac{1}{6} \right)$. The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is employed to generate the integer 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. -PeCO protocol is compared with three other approaches. DESK \cite{DESK}, GAF~\cite{GAF}, and DiLCO~\cite{Idrees2} is an improved version of a research work we presented in~\cite{ref159}, where DiLCO protocol is described in chapter 4. Let us notice that the PeCO and the DiLCO protocols are based on the same scheme. 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 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 sensor perimeter. In our experimentations, we chose a level of coverage equal to one ($l=1$). +PeCO protocol is compared with three other approaches. DESK \cite{DESK}, GAF~\cite{GAF}, and DiLCO~\cite{Idrees2}. + %is an improved version of a research work we presented in~\cite{ref159}, where DiLCO protocol is described in chapter 4. + Let us notice that the PeCO and the DiLCO protocols are based on the same scheme. 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 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 sensor perimeter. In our experimentations, we chose a level of coverage equal to one ($l=1$). @@ -311,7 +313,7 @@ appears that PeCO provides a better coverage ratio and keeps a coverage ratio \label{ch6:sec:04:02:02} Having the less active sensor nodes in each period is essential to minimize the 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 20.16 \% active nodes during the same time interval. As the number of periods increases, PeCO 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}. +the three other approaches, while keeping a greater coverage ratio as shown in Figure \ref{fig333}. \\ \begin{figure}[h!] \centering @@ -398,7 +400,7 @@ $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline \label{ch6:sec:05} In this chapter, 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 because 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. +is based on the resolution of an mixed-integer program to select the subset of sensors operating in active status for each period. Our work is original because 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. %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. diff --git a/CONCLUSION.tex b/CONCLUSION.tex index 099f6db..b189387 100644 --- a/CONCLUSION.tex +++ b/CONCLUSION.tex @@ -28,7 +28,7 @@ In chapter 6, we have proposed an approach called Perimeter-based Coverage Optim the objective of maintaining a good coverage ratio while maximizing the network lifetime. %in order to optimize the lifetime coverage, so that it provides activity scheduling which ensures sensing coverage as long as possible. - Like DiLCO and MuDiLCO, the PeCO protocol is distributed among sensor nodes in each subregion. The novelty of our approach, in comparison with DiLCO and MuDiLCO, lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule sensors’ activities. A leader provides one schedule during the current period by executing the new integer program during the decision phase. The extensive simulation experiments have demonstrated that PeCO can offer longer lifetime coverage for WSNs. + Like DiLCO and MuDiLCO, the PeCO protocol is distributed among sensor nodes in each subregion. The novelty of our approach, in comparison with DiLCO and MuDiLCO, lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule sensors’ activities. A leader provides one schedule during the current period by executing the new mixed-integer program during the decision phase. The extensive simulation experiments have demonstrated that PeCO can offer longer lifetime coverage for WSNs. Finally, we outline some interesting issues that will be considered in our perspectives which are discussed in more detail next. @@ -38,14 +38,13 @@ Finally, we outline some interesting issues that will be considered in our persp In this dissertation, we have focused on the lifetime area coverage optimization problem and we were interested only in energy-efficient distributed protocols, considering static homogeneous sensor nodes. Several parameters, constraints, and requirements can have an important impact on the coverage performance in WSNs. Thus, various scenarios parameters might need to be taken into consideration in the future, such as fault-tolerance, k-coverage, $\alpha$-coverage, adjustable sensor’s sensing range network, heterogeneous network, mobility, etc. -In chapter 4, we have studied the impact of the number of subregions chosen to subdivide the area of interest, considering different network sizes. The optimal number of subregions will be investigated in the future. We also plan to study and propose a coverage protocol, which computes all active sensor schedules in one time, using optimization methods such as particle swarm optimization or evolutionary algorithms. -%A period will still consist of 4 phases, but the decision phase will compute the schedules for several sensing rounds which, aggregated together, define a kind of meta-sensing round. -The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead. +In chapter 4, we have studied the impact of the number of subregions chosen to subdivide the area of interest, considering different network sizes. The optimal number of subregions will be investigated in the future. +%We also plan to study and propose a coverage protocol, which computes all active sensor schedules in one time, using optimization methods such as particle swarm optimization or evolutionary algorithms. The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead. We also plan to design and propose a heterogeneous integrated optimization protocol in WSNs. This protocol would integrate three energy-efficient (coverage, routing and data aggregation) protocols so as to extend the network lifetime in WSNs. The sensing, routing, and aggregation jobs are also challenges in WSNs. This integrated optimization protocol will be executed by each cluster head, a leader node in our protocols. The cluster head will be selected in a distributed way and based on local information. -We plan to extend our PeCO protocol so that the schedules are planned for multiple sensing periods. We also want to improve our mathematical model to take into account heterogeneous sensors from both energy and node characteristics point of views. +We plan to extend our PeCO protocol so that the schedules are planned for multiple sensing periods. We consider the use of optimization methods such as particle swarm optimization or evolutionary algorithms to obtain quickly near optimal solutions. The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead. We also want to improve our mathematical model to take into account heterogeneous sensors from both energy and node characteristics point of views. Finally, it would be interesting to implement our protocols using a sensor-testbed to evaluate it in real world applications.