X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/471e797ea207eea3a79a42ef48e6c3b14f3c004b..refs/heads/master:/SlidesAli/These.tex?ds=sidebyside diff --git a/SlidesAli/These.tex b/SlidesAli/These.tex index 2e7b91c..769d815 100644 --- a/SlidesAli/These.tex +++ b/SlidesAli/These.tex @@ -1,5 +1,10 @@ \documentclass{beamer} +%\usepackage[timeinterval=10]{tdclock} + + + \usepackage{beamerthemefemto} + \usepackage[T1]{fontenc} \usepackage{amsfonts,amsmath,amssymb,stmaryrd} \usepackage[frenchb]{babel} @@ -28,7 +33,10 @@ \usepackage{array} \usepackage{picture} \usepackage{float} - + + +% \usepackage[font=Times,timeinterval=10, timeduration=2.0, timedeath=0, fillcolorwarningsecond=white!60!yellow, timewarningfirst=50,timewarningsecond=80,resetatpages=2]{tdclock} + \def\setgrouptext#1{\gdef\grouptext{#1}} \newenvironment{groupeditems}{\begin{displaymath}\left.\vbox\bgroup\setgrouptext}{% \egroup\right\rbrace\hbox{\grouptext}\end{displaymath}} @@ -56,7 +64,7 @@ \AtBeginSection[] { \begin{frame} -\frametitle{Presentation Outline} +\frametitle{Presentation outline} \tableofcontents[currentsection] \end{frame} } @@ -80,12 +88,14 @@ % \begin{document} - +%\initclock +%\tdclock %%%%%%%%%%%%%%%%%%%% %% SLIDE 01 %% %%%%%%%%%%%%%%%%%%%% \setbeamertemplate{background}{\titrefemto} \begin{frame}[plain] +%\transduration{0.75} \begin{center} \titlepage \end{center} @@ -98,8 +108,9 @@ %%%%%%%%%%%%%%%%%%%% %% SLIDE 02 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame} {Problem Definition, Solution, and Objectives} +\begin{frame} {Problem definition and solution} \vspace{-3.5em} + \begin{figure} \includegraphics[width=0.495\textwidth]{Figures/6} \hfill @@ -110,8 +121,8 @@ % \includegraphics[width=0.475\textwidth]{Figures/13} \end{figure} - \begin{block}{\textcolor{white}{ MAIN QUESTION?}} - \textcolor{black}{How to minimize the energy consumption and extend the network lifetime during covering a certain area?} + \begin{block}{\textcolor{white}{MAIN QUESTION}} + \textcolor{black}{How to minimize the energy consumption and extend the network lifetime when covering the area of interest?} \end{block} \end{frame} @@ -119,21 +130,26 @@ %%%%%%%%%%%%%%%%%%%% %% SLIDE 03 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{Problem Definition, Solution, and Objectives} +\begin{frame}{Problem definition and solution} -\begin{block}{\textcolor{white}{OUR SOLUTION}} -\bf \textcolor{black}{The area of interest is divided into subregions using a divide-and conquer method and then combine two efficient techniques:} +\begin{block}{\textcolor{white}{OUR SOLUTION $\blacktriangleright$ Distributed optimization process}} +\begin{enumerate} [i)] +\item \bf \textcolor{black}{Division into subregions} +\item \bf \textcolor{black}{For each subregion} +\end{enumerate} + \begin{itemize} - \item \bf \textcolor{magenta}{Leader Election for each subregion.} - % \item Activity Scheduling based optimization is planned for each subregion. + \item \bf \textcolor{magenta}{Leader election} + \item \bf \textcolor{magenta}{Activity Scheduling based optimization} \end{itemize} - \end{block} + \end{block} +\vspace{-1.5em} \begin{figure} - \includegraphics[width=0.475\textwidth]{Figures/div} - \hfill \includegraphics[width=0.475\textwidth]{Figures/div2} + \hfill + \includegraphics[width=0.475\textwidth]{Figures/act2} \end{figure} \end{frame} @@ -141,46 +157,46 @@ %%%%%%%%%%%%%%%%%%%% %% SLIDE 03.1 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{Problem Definition, Solution, and Objectives} - -\begin{block}{\textcolor{white}{OUR SOLUTION}} - \begin{itemize} - %\item Leader Election for each subregion. - \item \bf \textcolor{magenta}{Activity Scheduling based optimization is planned for each subregion.} - \end{itemize} - - \end{block} -\begin{figure} - \includegraphics[width=0.775\textwidth]{Figures/act} - -\end{figure} - -\end{frame} +%\begin{frame}{Problem Definition, Solution, and Objectives} +% +%\begin{block}{\textcolor{white}{OUR SOLUTION}} +% \begin{itemize} +% %\item Leader Election for each subregion. +% \item \bf \textcolor{magenta}{Activity Scheduling based optimization is planned for each subregion.} +% \end{itemize} +% +% \end{block} +%\begin{figure} +% \includegraphics[width=0.775\textwidth]{Figures/act} +% +%\end{figure} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%% %% SLIDE 03.2 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{Problem Definition, Solution, and Objectives} - -\begin{block}{\bf \textcolor{white}{Dissertation Objectives}} -\bf \textcolor{black}{Develop energy-efficient distributed optimization protocols that should be able to:} - \begin{itemize} - \item \bf \textcolor{blue}{Schedule node activities by optimize both coverage and lifetime.} - \item \bf \textcolor{blue}{Combine two efficient techniques: leader election and sensor activity scheduling.} - \item \bf \textcolor{blue}{Perform a distributed optimization process.} - \end{itemize} - - \end{block} - - -\end{frame} +%\begin{frame}{Problem Definition, Solution, and Objectives} +% +%\begin{block}{\bf \textcolor{white}{Dissertation Objectives}} +%\bf \textcolor{black}{Develop energy-efficient distributed optimization protocols that should be able to:} +% \begin{itemize} +% \item \bf \textcolor{blue}{Schedule node activities by optimize both coverage and lifetime.} +% \item \bf \textcolor{blue}{Combine two efficient techniques: leader election and sensor activity scheduling.} +% \item \bf \textcolor{blue}{Perform a distributed optimization process.} +% \end{itemize} +% +% \end{block} +% +% +%\end{frame} %%%%%%%%%%%%%%%%%%%% %% SLIDE 04 %% %%%%%%%%%%%%%%%%%%%% \begin{frame} - \frametitle{Presentation Outline} + \frametitle{Presentation outline} \begin{small} \tableofcontents[section,subsection] \end{small} @@ -211,9 +227,9 @@ \begin{femtoBlock} {Sensor \\} \begin{itemize} - \item Electronic Low-cost tiny device. - \item Sense, process and transmit data. - \item Limited energy, memory and processing capabilities. + \item Electronic low-cost tiny device + \item Sense, process and transmit data + \item Limited energy, memory and processing capabilities \end{itemize} \end{femtoBlock} @@ -226,18 +242,7 @@ \begin{figure}[!t] \includegraphics[height = 2cm]{Figures/sn.jpg} \end{figure} - - - % \begin{femtoBlock} {}% {SOME APPLICATIONS OF WSNs \\} - -% \includegraphics[height =1 cm]{1.png} -% \includegraphics[height =1cm]{2.png}\\ -% \includegraphics[height =1cm]{5.jpg} -% \includegraphics[height = 1cm]{traffic.jpg} -% \includegraphics[height = 1cm]{3.png} -% - - % \end{femtoBlock} + \end{columns} @@ -288,13 +293,16 @@ %%%%%%%%%%%%%%%%%%%% %% SLIDE 09 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{Energy-Efficient Mechanisms of a working WSN} +\begin{frame}{Energy-efficient mechanisms of a working WSN} \vspace{-2.5em} - \centering + \begin{figure}[!t] - - \includegraphics[height = 5cm]{Figures/WSN-M.pdf} +\centering + % \includegraphics[height = 5cm]{Figures/WSN-M.pdf} + \includegraphics[height = 4.8cm]{Figures/EEM.eps} \end{figure} + \vspace{-1.0em} + %\bf \textcolor{blue} {Our approach includes cluster architecture and scheduling schemes} \end{frame} %\begin{frame}{Energy-Efficient Mechanisms of a working WSN} @@ -308,22 +316,23 @@ %%%%%%%%%%%%%%%%%%%% %% SLIDE 10 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{Network Lifetime} +\begin{frame}{Network lifetime} \vspace{-1.5em} -\begin{block}{\textcolor{white} {Some Network Lifetime Definitions:}} -\small -\begin{enumerate}[i)] -\item \textcolor{black} {Time spent until death of the first sensor (or cluster head).} -\item \textcolor{black} {Time spent until death of all wireless sensor nodes in WSN.} -\item \textcolor{black} {Time spent by WSN in covering each target by at least one sensor.} -\item \textcolor{black} {Time during which the area of interest is covered by at least k nodes.} -\item \textcolor{black} {Elapsed time until losing the connectivity or the coverage.} +\begin{femtoBlock} + { Some definitions\\} + \begin{enumerate}[i)] +\item \textcolor{black} {Time spent until death of the first sensor (or cluster head)} +\item \textcolor{black} {Time spent until death of all wireless sensor nodes in WSN} +%\item \textcolor{black} {Time spent by WSN in covering each target by at least one sensor} +\item \textcolor{black} {Time spent in covering area of interest by at least k nodes} +\item \textcolor{black} {Elapsed time until losing the connectivity or the coverage} +\item \bf \textcolor{red} {Elapsed time until the coverage ratio becomes less than a predetermined threshold $\alpha$} \end{enumerate} -\end{block} + + \end{femtoBlock} + + -\begin{block}{\textcolor{white} {Network lifetime In this dissertation:}} -\textcolor{blue} {Time elapsed until the coverage ratio becomes less than a predetermined threshold $\alpha$.} -\end{block} \end{frame} @@ -333,87 +342,90 @@ %%%%%%%%%%%%%%%%%%%% \begin{frame}{Coverage in Wireless Sensor Networks} -\begin{block} <1-> {\textcolor{white} {Coverage Definition:}} -\textcolor{blue} {Coverage} reflects how well a sensor field is monitored efficiently using as less energy as possible. +\begin{block} <1-> {\textcolor{white} {Coverage definition}} +\textcolor{blue} {Coverage} reflects how well a sensor field is monitored efficiently using as less energy as possible \end{block} -\begin{block} <2-> {\textcolor{white} {Coverage Types:}} -\begin{enumerate} -\item \small \textcolor{blue} {Area coverage:} every point inside an area has to be monitored. -\item \textcolor{blue} {Target coverage:} only a finite number of discrete points called targets have to be monitored. +%\begin{block} <2-> {\textcolor{white} {Coverage types}} +\begin{block} {\bf \textcolor{white} {Coverage types}} +\begin{enumerate}[i)] +\item \small \textcolor{red} {Area coverage $\blacktriangleright$ every point inside an area has to be monitored} +\item \textcolor{blue} {Target coverage} $\blacktriangleright$ only a finite number of discrete points called targets has to be monitored -\item \textcolor{blue} {Barrier coverage:} detection of targets as they cross a barrier such as in intrusion detection and border surveillance applications. +\item \textcolor{blue} {Barrier coverage} $\blacktriangleright$ detection of targets as they cross a barrier such as in intrusion detection and border surveillance applications \end{enumerate} \end{block} -\begin{block} <3-> {\textcolor{white} {Coverage type in this dissertation:}} -The work presented in this dissertation deals with \textcolor{red} {area coverage}. -\end{block} +%\begin{block} <3-> {\textcolor{white} {Coverage type in this dissertation:}} +%The work presented in this dissertation deals with \textcolor{red} {area coverage}. +%\end{block} \end{frame} %%%%%%%%%%%%%%%%%%%% %% SLIDE 11 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{Existing Works} +\begin{frame}{Existing works} \vspace{-0.3em} -\begin{block} {\textcolor{white} {Coverage Approaches:}} -Most existing coverage approaches in literature classified into -\begin{enumerate}[A)] -\item Full centralized coverage algorithms. +\begin{block} {\textcolor{white} {Coverage approaches}} +%Most existing coverage approaches in literature classified into +\begin{enumerate}[i)] +\item \textcolor{blue} { Full centralized coverage algorithms} \begin{itemize} - \item Optimal or near optimal solution. - \item low computation power for the sensors (except for base station). - \item Higher energy consumption for communication in large WSN. - \item Not scalable for large WSNs. + \item Optimal or near optimal solution + \item Low computation power for the sensors (except for base station) + \item Higher energy consumption for communication in large WSN + \item Not scalable for large WSNs \end{itemize} -\item Full distributed coverage algorithms. +\item \textcolor{blue} {Full distributed coverage algorithms} + \begin{itemize} + \item Lower quality solution + \item Decision process is localized inside sensor and may requires a high computation power for dense WSNs + \item Less energy consumption for communication in large WSN + \item Reliable and scalable for large WSNs + \end{itemize} + \item \textcolor{red} {Hybrid approaches} \begin{itemize} - \item Lower quality solution. - \item less energy consumption for communication in large WSN. - \item Reliable and scalable for large WSNs. + \item \textcolor{red} {Globally distributed and locally centralized} \end{itemize} + \end{enumerate} \end{block} -\begin{block} {\textcolor{white} {Coverage protocols in this dissertation:}} -The protocols presented in this dissertation combine between the two above approaches. -\end{block} +%\begin{block} {\textcolor{white} {Coverage protocols in this dissertation:}} +%The protocols presented in this dissertation combine between the two above approaches. +%\end{block} \end{frame} -\begin{frame}{Existing Works: DESK algorithm} -\vspace{-1.5em} +\begin{frame}{Existing works $\blacktriangleright$ DESK algorithm (Vu et al.)} +\vspace{-2.0em} \begin{figure}[!t] - \includegraphics[height = 3.0cm]{Figures/DESK.eps} + \includegraphics[height = 5.0cm]{Figures/DESKp.eps} \end{figure} \vspace{-2.5em} \begin{itemize} - \item \small developed by Vu et al. - \item works in rounds. - \item requires only one-hop neighbor information. - \item each sensor decides its status (Active or Sleep) based on the perimeter coverage model. - \item whole area is K-covered if and only if the perimeters of all sensors -are K-covered. - - \end{itemize} + \item Requires only one-hop neighbor information (fully distributed) + \item Each sensor decides its status (Active or Sleep) based on the perimeter coverage model, without optimization + +\end{itemize} -\tiny \bf \textcolor{blue}{DESK is chosen for comparison because it works into rounds fashion similar to our approaches, as well as DESK is a full distributed coverage approach.} +%\tiny \bf \textcolor{blue}{DESK is chosen for comparison because it works into rounds fashion similar to our approaches, as well as DESK is a full distributed coverage approach.} \end{frame} -\begin{frame}{Existing Works: GAF algorithm} -%\vspace{-0.3em} +\begin{frame}{Existing works $\blacktriangleright$ GAF algorithm (Xu et al.)} + \vspace{-3.3em} \begin{columns}[c] @@ -423,33 +435,31 @@ are K-covered. \includegraphics[height = 2.7cm]{Figures/GAF1.eps} \end{figure} \vspace{-2.5em} - \tiny - \begin{itemize} - \item developed by Xu et al. - \item uses geographic location information to divide the area of interest into a fixed square grids. - \item Within each grid, only one node staying awake to take the responsibility of sensing and communication. - \item the fixed grid is square with r units on a side. - \item $r\leq \dfrac{R_c}{\sqrt{5}}$ - \item Distance(2,5) $\leq$ Communication Range ($R_c$). - \end{itemize} + \begin{figure}[!t] + \includegraphics[height = 3.3cm]{Figures/GAF2.eps} + \end{figure} \column{.52\textwidth} - -% \begin{itemize} -% \end{itemize} + \vspace{1.2em} +\small + \begin{itemize} + \item Distributed energy-based scheduling approach + \item Uses geographic location information to divide the area into a fixed square grids + \item Nodes are in one of three sates $\blacktriangleright$ discovery, active, or sleep + \item Only one node staying active in grid + \item The fixed grid is square with r units on a side + \item Nodes cooperate within each grid to choose the active node + \end{itemize} - \begin{figure}[!t] - \includegraphics[height = 3.3cm]{Figures/GAF2.eps} - \end{figure} - \vspace{-2.5em} - - \begin{itemize} - \item \tiny enat: estimated node active time - \item enlt: estimated node lifetime - \item Td,Ta, Ts: discovery, active, and sleep timers - \item Ta = enlt/2 - \item Ts = [enat/2, enat] - \end{itemize} + + +% \begin{itemize} +% \item \tiny enat: estimated node active time +% \item enlt: estimated node lifetime +% \item Td,Ta, Ts: discovery, active, and sleep timers +% \item Ta = enlt/2 +% \item Ts = [enat/2, enat] +% \end{itemize} @@ -457,182 +467,144 @@ are K-covered. \vspace{1.0em} -\tiny \bf \textcolor{blue}{GAF is chosen for comparison because it is famous and easy to implement, as well as many authors referred to it in many publications.} - - - +%\tiny \bf \textcolor{blue}{GAF is chosen for comparison because it is famous and easy to implement, as well as many authors referred to it in many publications.} \end{frame} -%%%%%%%%%%%%%%%%%%%% -%% SLIDE 12 %% -%%%%%%%%%%%%%%%%%%%% -\section{\small {Distributed Lifetime Coverage Optimization Protocol (DiLCO)}} - +\section{\small {The main scheme for our protocols}} -%%%%%%%%%%%%%%%%%%%% -%% SLIDE 13 %% -%%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small DiLCO Protocol $\blacktriangleright$ Assumptions and Network Model:} -\vspace{-0.5cm} +\begin{frame}{Assumptions for our protocols} +\vspace{-0.1cm} -\begin{femtoBlock} {} %{Assumptions and Network Model:} - - \begin{columns}[c] - - \column{.50\textwidth} - - \vspace{-1.0cm} - - \begin{enumerate} [$\divideontimes$] - \item Static Wireless Sensors. - \item Uniform deployment. - \item High density deployment. - \item Homogeneous in terms of: +\begin{enumerate} [$\divideontimes$] + \item Static wireless sensor, homogeneous in terms of \begin{itemize} - \item Sensing, Communication, and Processing capabilities + \item Sensing + \item Communication + \item Processing capabilities \end{itemize} - \item Heterogeneous Energy. - \item Its $R_c\geq 2R_s$. - \item Multi-hop communication. - \item Known location by: - \begin{itemize} - \item Embedded GPS or - \item Location Discovery Algorithm. - \end{itemize} + \item Heterogeneous initial energy + \item High density uniform deployment + \item $R_c\geq 2R_s$ + \begin{itemize} + \item Complete coverage $\Rightarrow$ connectivity (proved by Zhang and Zhou) + \end{itemize} + \item Multi-hop communication + \end{enumerate} - - - \column{.50\textwidth} - \begin{enumerate} [$\divideontimes$] - \item Using two kinds of packet: +\end{frame} + + +\begin{frame}{Assumptions for our protocols} +\vspace{-0.1cm} + +\begin{enumerate} [$\divideontimes$] + \item Known location by + \begin{itemize} + \item Embedded GPS + \item location discovery algorithm + \end{itemize} + + \item Using two kinds of packets \begin{itemize} - \item INFO packet. - \item ActiveSleep packet. + \item INFO packet + \item ActiveSleep packet \end{itemize} - \item Five status for each node: + \item Five status for each node \begin{itemize} - \item LISTENING, ACTIVE, SLEEP, COMPUTATION, and COMMUNICATION. + \item LISTENING + \item ACTIVE + \item SLEEP + \item COMPUTATION + \item COMMUNICATION \end{itemize} - \end{enumerate} - - \begin{femtoBlock} { \small Primary point coverage model} - \vspace{-1.2cm} - \begin{center} - \includegraphics[height = 4.0cm]{Figures/fig21.pdf} - - \end{center} - \end{femtoBlock} + \end{enumerate} - \end{columns} - \end{femtoBlock} - \end{frame} -%%%%%%%%%%%%%%%%%%%% -%% SLIDE 14 %% -%%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small DiLCO Protocol $\blacktriangleright$ Main Idea} -%\vspace{-3.2cm} -\begin{femtoBlock} {}%{Main Idea:\\} -\centering -\includegraphics[height = 2.5cm]{Figures/OneSensingRound.jpg} -\vspace{1.2cm} -\begin{enumerate} -\item \textcolor{blue}{ \textbf{INFORMATION EXCHANGE:}}\\ -Sensors exchanges through multi-hop communication, their: -\begin{itemize} -\item Position coordinates, -\item current remaining energy, -\item sensor node ID, and -\item number of its one-hop live neighbors. -\end{itemize} -\end{enumerate} -\end{femtoBlock} + +\begin{frame}{Assumptions for our protocols} + \vspace{-0.5cm} +\begin{center} + \includegraphics[height = 7.0cm]{Figures/Pmodelsn.pdf} +\end{center} + \end{frame} -%%%%%%%%%%%%%%%%%%%% -%% SLIDE 14.1 %% -%%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small DiLCO Protocol $\blacktriangleright$ Main Idea} -%\vspace{-3.2cm} -\begin{femtoBlock} {}%{Main Idea:\\} -\begin{enumerate} [2.] -\item \textcolor{blue}{ \textbf{ LEADER ELECTION:}}\\ -The selection criteria are, in order of importance: +\begin{frame}{General scheme} +\vspace{-0.2cm} +\begin{figure}[ht!] + \includegraphics[width=110mm]{Figures/GeneralModel.jpg} + \end{figure} + \begin{itemize} -\item larger number of neighbors, -\item larger remaining energy, and then in case of equality, -\item larger ID. +\item DiLCO and PeCO $\blacktriangleright$ one round sensing ($T=1$) +\item MuDiLCO $\blacktriangleright$ multiple rounds sensing ($t=1, \cdots, T$) \end{itemize} -\end{enumerate} -\begin{enumerate} [3.] -\item \textcolor{blue}{ \textbf{ DECISION:}} \\ -Leader solves an integer program (see next slide) to: +\end{frame} + + +\begin{frame}{General scheme} + \vspace{-0.2cm} +\begin{enumerate} [i)] +\item \textcolor{blue}{\textbf{INFORMATION EXCHANGE}} $\blacktriangleright$ Sensors exchange through multi-hop communication, their \begin{itemize} -\item Select which sensors will be activated in the sensing phase. -\item Send Active-Sleep packet to each sensor in the subregion. +\item Position coordinates, current remaining energy, sensor node ID, and number of its one-hop live neighbors + \end{itemize} -\end{enumerate} -\begin{enumerate} [4.] -\item \textcolor{blue}{ \textbf{ SENSING:}} \\ -Based on Active-Sleep Packet Information: + + +\item \textcolor{blue}{\textbf{LEADER ELECTION}} $\blacktriangleright$ The selection criteria are, in order \begin{itemize} -\item Active sensors will execute their sensing task. -\item Sleep sensors will wait a time equal to the period of sensing to wakeup. +\item Larger number of neighbors +\item Larger remaining energy +\item Larger ID +\end{itemize} + + +\item \textcolor{blue}{\textbf{DECISION}} $\blacktriangleright$ Leader solves an integer program to +\begin{itemize} +\item Select which sensors will be activated in the sensing phase +\item Send Active-Sleep packet to each sensor in the subregion \end{itemize} -\end{enumerate} + +\item \textcolor{blue}{\textbf{SENSING}} $\blacktriangleright$ Based on Active-Sleep Packet Information +\begin{itemize} +\item Active sensors will execute their sensing task +\item Sleep sensors will wait a time equal to the period of sensing to wakeup -\end{femtoBlock} +\end{itemize} +\end{enumerate} + \end{frame} + %%%%%%%%%%%%%%%%%%%% -%% SLIDE 15 %% +%% SLIDE 12 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small DiLCO Protocol $\blacktriangleright$ Coverage Problem Formulation} -\vspace{-0.3cm} -\begin{equation*} \label{eq:ip2r} -\left \{ -\begin{array}{ll} -\min \sum_{p \in P} (w_{\theta} \Theta_{p} + w_{U} U_{p})&\\ -\textrm{subject to :}&\\ -\sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, &\forall p \in P\\ -%\label{c1} -%\sum_{t \in T} X_{j,t} \leq \frac{RE_j}{e_t} &\forall j \in J \\ -%\label{c2} -\Theta_{p}\in \mathbb{N}, &\forall p \in P\\ -U_{p} \in \{0,1\}, &\forall p \in P \\ -X_{j} \in \{0,1\}, &\forall j \in J -\end{array} -\right. -\end{equation*} -\vspace{-0.3cm} -\begin{itemize} -\item \small $P$: the set of primary points. -\item $J$: the set of sensors. -\item $X_{j}$: indicates whether or not the sensor $j$ is actively sensing (1 - if yes and 0 if not). -\item $\Theta_{p}$: {\it overcoverage}, the number of sensors minus one that - are covering the primary point $p$. -\item $U_{p}$: {\it undercoverage}, indicates whether or not the primary point - $p$ is being covered (1 if not covered and 0 if covered). - \item $\alpha_{jp}$: denotes the indicator function of whether the primary point p is covered. -\end{itemize} +\section{\small {Distributed Lifetime Coverage Optimization Protocol (DiLCO)}} +%%%%%%%%%%%%%%%%%%%% +%% SLIDE 15 %% +%%%%%%%%%%%%%%%%%%%% +\begin{frame}{\small DiLCO protocol $\blacktriangleright$ Coverage problem formulation} +\vspace{0.2cm} +\centering +\includegraphics[height = 7.2cm]{Figures/modell1.pdf} \end{frame} @@ -640,7 +612,7 @@ X_{j} \in \{0,1\}, &\forall j \in J %%%%%%%%%%%%%%%%%%%% %% SLIDE 16 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small DiLCO Protocol $\blacktriangleright$ DiLCO Protocol Algorithm} +\begin{frame}{\small DiLCO protocol $\blacktriangleright$ DiLCO protocol algorithm} %\begin{femtoBlock} {} \centering %\includegraphics[height = 7.2cm]{Figures/algo.jpeg} @@ -655,11 +627,11 @@ X_{j} \in \{0,1\}, &\forall j \in J %%%%%%%%%%%%%%%%%%%% %% SLIDE 18 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small DiLCO Protocol $\blacktriangleright$ Simulation Framework} +\begin{frame}{\small DiLCO protocol $\blacktriangleright$ Simulation framework} \vspace{-0.8cm} \small \begin{table}[ht] -\caption{Relevant parameters for simulation.} +\caption{Relevant parameters for simulation} \centering \begin{tabular}{c|c} \hline @@ -687,9 +659,9 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 19 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small DiLCO Protocol $\blacktriangleright$ Energy Model \& Performance Metrics } +\begin{frame}{\small DiLCO protocol $\blacktriangleright$ Energy model \& performance metrics } %\vspace{-1.8cm} -\begin{femtoBlock} {Energy Consumption Model} +\begin{femtoBlock} {Energy consumption model} \vspace{-1.0cm} \begin{table}[h] %\centering @@ -712,14 +684,14 @@ Network Simulator & Discrete Event Simulator OMNeT++ \end{femtoBlock} \vspace{-0.5cm} -\begin{femtoBlock} {Performance Metrics} +\begin{femtoBlock} {Performance metrics} \small -\begin{enumerate}[$\mapsto$] +\begin{enumerate}[$\blacktriangleright$] \item {{\bf Coverage Ratio (CR)}} -\item{{\bf Number of Active Sensors Ratio (ASR)}} -\item {{\bf Energy Consumption}} -\item {{\bf Network Lifetime}} +\item {{\bf Active Sensors Ratio (ASR)}} +\item {{\bf Energy consumption $(Lifetime_{95}$, $Lifetime_{50})$}} +\item {{\bf Network lifetime $(Lifetime_{95}$, $Lifetime_{50})$}} %\item {{\bf Execution Time}} %\item {{\bf Stopped Simulation Runs}} @@ -732,7 +704,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 20 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{ \small DiLCO Protocol $\blacktriangleright$ Performance Comparison} +\begin{frame}{ \small DiLCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}[h!] @@ -751,7 +723,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 20 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{ \small DiLCO Protocol $\blacktriangleright$ Performance Comparison} +\begin{frame}{ \small DiLCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}[h!] @@ -780,7 +752,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 22 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{ \small DiLCO Protocol $\blacktriangleright$ Performance Comparison} +\begin{frame}{ \small DiLCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}%[h!] \begin{columns}[c] @@ -802,7 +774,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 23 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{ \small DiLCO Protocol $\blacktriangleright$ Performance Comparison} +\begin{frame}{ \small DiLCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}%[h!] \begin{columns}[c] @@ -833,24 +805,24 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 28 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Main Idea} -\vspace{-0.2cm} -\begin{figure}[ht!] - \includegraphics[width=110mm]{Figures/GeneralModel.jpg} -\caption{MuDiLCO protocol.} -\label{fig2} -\end{figure} -\end{frame} +%\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Main Idea} +%\vspace{-0.2cm} +%\begin{figure}[ht!] +% \includegraphics[width=110mm]{Figures/GeneralModel.jpg} +%\caption{MuDiLCO protocol.} +%\label{fig2} +%\end{figure} +%\end{frame} %%%%%%%%%%%%%%%%%%%% %% SLIDE 29 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Multiround Coverage Problem Formulation} +\begin{frame}{\small MuDiLCO protocol $\blacktriangleright$ Multiround coverage problem formulation} \vspace{0.2cm} \centering -\includegraphics[height = 7.2cm]{Figures/model2.pdf} +\includegraphics[height = 7.2cm]{Figures/modell2.pdf} \end{frame} @@ -869,7 +841,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 31 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Results Analysis and Comparison} +\begin{frame}{\small MuDiLCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}[h!] \centering @@ -883,7 +855,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 32 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Results Analysis and Comparison} +\begin{frame}{\small MuDiLCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}[h!] \centering @@ -924,7 +896,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 35 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Results Analysis and Comparison} +\begin{frame}{\small MuDiLCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}%[h!] \begin{columns}[c] @@ -944,7 +916,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 36 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Results Analysis and Comparison} +\begin{frame}{\small MuDiLCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}%[h!] \begin{columns}[c] @@ -964,14 +936,13 @@ Network Simulator & Discrete Event Simulator OMNeT++ -\section{\small {Perimeter-based Coverage Optimization (PeCO) to Improve Lifetime in WSNs -}} +\section{\small {Perimeter-based Coverage Optimization (PeCO)}} %%%%%%%%%%%%%%%%%%%% %% SLIDE 45 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small PeCO Protocol $\blacktriangleright$ Assumptions and Models} +\begin{frame}{\small PeCO protocol $\blacktriangleright$ Assumptions and models} \vspace{-0.5cm} \begin{figure}%[h!] @@ -982,7 +953,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ \column{.50\textwidth} $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} \right).$$ -\includegraphics[scale=0.40]{Figures/ch6/twosensors.jpg} +\includegraphics[scale=0.30]{Figures/ch6/twosensors.eps} \footnotesize \\~~~~~~~~~~~~~~~~~~~~~~~~~~(b) \\ \end{columns} \caption{(a) Perimeter coverage of sensor node 0 and (b) finding the arc of @@ -995,22 +966,27 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} %%%%%%%%%%%%%%%%%%%% %% SLIDE 46 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small PeCO Protocol $\blacktriangleright$ Assumptions and Models} +\begin{frame}{\small PeCO protocol $\blacktriangleright$ Assumptions and models} -\vspace{-0.5cm} +\vspace{-1.2cm} \begin{figure}%[h!] -\begin{columns}[c] - \column{.50\textwidth} -\includegraphics[scale=0.33]{Figures/ch6/expcm2.jpg} -\footnotesize \\~~~~~~~~~~~~~~~~~~~~~~~~~~(a)\\ -\column{.50\textwidth} -\includegraphics[scale=0.38]{Figures/tbl.jpeg} -\footnotesize \\~~~~~~~~~~~~~~~~~~~~~~~~~~(b) \\ -\end{columns} -\caption{(a) Maximum coverage levels for perimeter of sensor node $0$. and (b) Coverage intervals and contributing sensors for sensor node 0.} - \label{pcm2sensors} +%\begin{columns}[c] +% \column{.50\textwidth} +\includegraphics[scale=0.6]{Figures/ch6/expcm2.jpg} +%\footnotesize \\~~~~~~~~~~~~~~~~~~~~~~~~~~(a)\\ +%\column{.50\textwidth} +%\includegraphics[scale=0.38]{Figures/tbl.jpeg} +%\footnotesize \\~~~~~~~~~~~~~~~~~~~~~~~~~~(b) \\ +%\end{columns} +%\caption{(a) Maximum coverage levels for perimeter of sensor node $0$. and (b) Coverage intervals and contributing sensors for sensor node 0.} +% \label{pcm2sensors} \end{figure} +\vspace{-0.9cm} +\textcolor {red} {Set of sensors involved in coverage interval of sensor 0 between 5L to 6L $\Rightarrow$ [0,2,5]\\ +Maximum coverage level: 3 +}%$a^0_{i0}= 1$ +%For example, the interval between 3R to 4R is covered by 4 sensors (0,1,2,4), it means the coverage level is 4 \end{frame} @@ -1019,13 +995,13 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} %%%%%%%%%%%%%%%%%%%% %% SLIDE 47 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small PeCO Protocol $\blacktriangleright$ PeCO Protocol Algorithm} +\begin{frame}{\small PeCO protocol $\blacktriangleright$ PeCO protocol algorithm} \vspace{-0.7cm} %\includegraphics[height = 7.2cm]{Figures/algo6.jpeg} \begin{figure}[h!] \centering - \includegraphics[height = 7.2cm]{Figures/Algo3.png} + \includegraphics[height = 7.2cm]{Figures/ch6/Algo3n.pdf} \end{figure} \end{frame} @@ -1033,12 +1009,12 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} %%%%%%%%%%%%%%%%%%%% %% SLIDE 48 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small PeCO Protocol $\blacktriangleright$ Perimeter-based Coverage Problem Formulation} -\vspace{-0.7cm} +\begin{frame}{\small PeCO protocol $\blacktriangleright$ Perimeter-based coverage problem formulation} +\vspace{-0.72cm} \begin{figure}[h!] \centering -\includegraphics[scale=0.49]{Figures/model3.pdf} +\includegraphics[scale=0.5]{Figures/modell3.pdf} \end{figure} \end{frame} @@ -1048,7 +1024,7 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} %%%%%%%%%%%%%%%%%%%% %% SLIDE %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small PeCO Protocol $\blacktriangleright$ Performance Evaluation and Analysis} +\begin{frame}{\small PeCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}[h!] \centering @@ -1063,7 +1039,7 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} %%%%%%%%%%%%%%%%%%%% %% SLIDE %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small PeCO Protocol $\blacktriangleright$ Performance Evaluation and Analysis} +\begin{frame}{\small PeCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}[h!] \centering @@ -1077,7 +1053,7 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} %%%%%%%%%%%%%%%%%%%% %% SLIDE %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small PeCO Protocol $\blacktriangleright$ Performance Evaluation and Analysis} +\begin{frame}{\small PeCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}%[h!] \begin{columns}[c] @@ -1098,7 +1074,7 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} %%%%%%%%%%%%%%%%%%%% %% SLIDE %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small PeCO Protocol $\blacktriangleright$ Performance Evaluation and Analysis} +\begin{frame}{\small PeCO protocol $\blacktriangleright$ Performance comparison} \vspace{-0.5cm} \begin{figure}%[h!] \begin{columns}[c] @@ -1109,7 +1085,7 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} \includegraphics[scale=0.35]{Figures/ch6/R/LT50.eps} \footnotesize \\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(b) \\ \end{columns} -\caption{Network Lifetime for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.} +\caption{Network lifetime for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.} \label{fig3LT} \end{figure} @@ -1132,7 +1108,7 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} %%%%%%%%%%%%%%%%%%%% %% SLIDE %% %%%%%%%%%%%%%%%%%%%% -\section{\small {Conclusion and Perspectives}} +\section{\small {Conclusion and perspectives}} %%%%%%%%%%%%%%%%%%%% @@ -1143,22 +1119,21 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} \item Two-step approaches are proposed to optimize both coverage and lifetime performances, where: \begin{itemize} -\item Sensing field is divided into smaller subregions using divide-and-conquer method. -\item One of the proposed optimization protocols is applied in each subregion in a distributed parallel way. +\item Sensing field is divided into smaller subregions using divide-and-conquer method +\item One of the proposed optimization protocols is applied in each subregion in a distributed parallel way \end{itemize} -\item The proposed protocols (DiLCO, MuDiLCO, PeCO) combine two efficient mechanisms: +\item Our proposed protocols combine two efficient mechanisms \begin{itemize} \item Network leader election, and -\item Sensor activity scheduling based optimization. -\end{itemize} -\item Our protocols are periodic where each period consists of 4 -phases: -\begin{itemize} -\item Information exchange, -\item Network leader election, -\item Decision based optimization, -\item Sensing. +\item Sensor activity scheduling based optimization \end{itemize} +\item Our protocols are periodic where each period consists of 4 phases +%\begin{itemize} +%\item Information exchange +%\item Network leader election +%\item Decision based optimization +%\item Sensing. +%\end{itemize} \end{enumerate} @@ -1173,30 +1148,30 @@ phases: \begin{frame}{Conclusion} \begin{enumerate} [$\blacktriangleright$] -\item DiLCO and PeCO provide a schedule for one round per period. -\item MuDiLCO provides a schedule for multiple rounds per period. -\item Comparison results show that DiLCO, MuDiLCO, and PeCO protocols: +\item DiLCO and PeCO provide a schedule for one round per period +\item MuDiLCO provides a schedule for multiple rounds per period +\item Comparison results show that our protocols \begin{itemize} - \item maintain the coverage for a larger number of rounds. - \item use less active nodes to save energy efficiently during sensing. - \item are more powerful against network disconnections. - \item perform the optimization with suitable execution times. - \item consume less energy. - \item prolong the network lifetime. + \item Maintain the coverage for a larger number of rounds + \item Use less active nodes to save energy efficiently during sensing + \item More powerful against network disconnections +% \item Perform the optimization with suitable execution times + \item Consume less energy + \item Prolong the network lifetime \end{itemize} \end{enumerate} \end{frame} -\begin{frame}{Conclusion} +\begin{frame}{Publications} \tiny \begin{block}{\textcolor{white}{Journal Articles}} \begin{enumerate}[$\lbrack$1$\rbrack$] -\item Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier. Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks. \textit{Engineering Optimization, 2015, (Submitted)}. +\item Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier. Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks. \textit{\textcolor{red}{Engineering Optimization}, 2015, ($2^{nd}$ Revision Submitted)}. -\item Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier. Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks. \textit{Ad Hoc Networks, 2015, (Submitted)}. +\item Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier. Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks. \textit{\textcolor{red}{Ad Hoc Networks}, 2015, ($1^{st}$ Revision Submitted)}. -\item Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier. Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks. \textit{Journal of Supercomputing , 2015, (Submitted)}. +\item Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier. Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks. \textit{\textcolor{red}{Journal of Supercomputing}, 2015, ($1^{st}$ Revision Submitted)}. \end{enumerate} \end{block} @@ -1222,12 +1197,11 @@ Coverage and lifetime optimization in heterogeneous energy wireless sensor netwo %%%%%%%%%%%%%%%%%%%% \begin{frame}{Perspectives} \begin{enumerate} [$\blacktriangleright$] -\item Investigate the optimal number of subregions. -\item Design a heterogeneous integrated optimization protocol to integrate coverage, routing, and data aggregation protocols. -\item Extend PeCO protocol so that the schedules are planned for multiple -sensing periods. -\item Consider particle swarm optimization or evolutionary algorithms to obtain quickly near optimal solutions. -\item Improve our mathematical models to take into account heterogeneous sensors from both energy and node characteristics point of views. +\item Investigate the optimal number of subregions +\item Design a heterogeneous integrated optimization protocol to integrate coverage, routing, and data aggregation protocols +\item Extend PeCO protocol so that the schedules are planned for multiple rounds per period +\item Consider particle swarm optimization or evolutionary algorithms to obtain quickly near optimal solutions +\item Improve our mathematical models to take into account heterogeneous sensors from both energy and node characteristics point of views %\item The cluster head will be selected in a distributed way and based on local information. \end{enumerate}