X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/471e797ea207eea3a79a42ef48e6c3b14f3c004b..a5b27a679ef2809581fb27959ecfcf348dcbbe39:/SlidesAli/These.tex?ds=sidebyside diff --git a/SlidesAli/These.tex b/SlidesAli/These.tex index 2e7b91c..94c4bef 100644 --- a/SlidesAli/These.tex +++ b/SlidesAli/These.tex @@ -111,7 +111,7 @@ \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?} + \textcolor{black}{How to minimize the energy consumption and extend the network lifetime when covering a certain area?} \end{block} \end{frame} @@ -121,19 +121,21 @@ %%%%%%%%%%%%%%%%%%%% \begin{frame}{Problem Definition, Solution, and Objectives} -\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: distributed optimization process}} +\bf \textcolor{black}{Division into subregions}\\ +\bf \textcolor{black}{For each subregion:} \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,39 +143,39 @@ %%%%%%%%%%%%%%%%%%%% %% 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} %%%%%%%%%%%%%%%%%%%% @@ -211,9 +213,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 +228,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} @@ -295,6 +286,8 @@ \includegraphics[height = 5cm]{Figures/WSN-M.pdf} \end{figure} + + \bf \textcolor{blue} {Our approach: includes cluster architecture and scheduling schemes} \end{frame} %\begin{frame}{Energy-Efficient Mechanisms of a working WSN} @@ -308,9 +301,9 @@ %%%%%%%%%%%%%%%%%%%% %% SLIDE 10 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{Network Lifetime} +\begin{frame}{Network lifetime} \vspace{-1.5em} -\begin{block}{\textcolor{white} {Some Network Lifetime Definitions:}} +\begin{block}{\textcolor{white} {Some definitions:}} \small \begin{enumerate}[i)] \item \textcolor{black} {Time spent until death of the first sensor (or cluster head).} @@ -318,12 +311,13 @@ \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.} +\item \bf \textcolor{red} {Time elapsed until the coverage ratio becomes less than a predetermined threshold $\alpha$.} \end{enumerate} \end{block} -\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} +%\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,15 +327,15 @@ %%%%%%%%%%%%%%%%%%%% \begin{frame}{Coverage in Wireless Sensor Networks} -\begin{block} <1-> {\textcolor{white} {Coverage Definition:}} +\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. +\begin{block} <2-> {\textcolor{white} {Coverage types:}} +\begin{enumerate}[i)] +\item \small \textcolor{red} {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. \item \textcolor{blue} {Barrier coverage:} detection of targets as they cross a barrier such as in intrusion detection and border surveillance applications. @@ -350,70 +344,71 @@ -\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 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} +\begin{frame}{Existing works: DESK algorithm (Vu et al.)} \vspace{-1.5em} \begin{figure}[!t] - \includegraphics[height = 3.0cm]{Figures/DESK.eps} + \includegraphics[height = 4.0cm]{Figures/DESK.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. - + \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: GAF algorithm (Xu et al.)} + \vspace{-3.3em} \begin{columns}[c] @@ -423,33 +418,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: 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 +450,121 @@ 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, communication, and processing capabilities \end{itemize} - \item Heterogeneous Energy. - \item Its $R_c\geq 2R_s$. - \item Multi-hop communication. + \item Heterogeneous initial energy + \item High density uniform deployment + \item Its $R_c\geq 2R_s$ for imply connectivity among active nodes during complete coverage (hypothesis proved by Zhang and Zhou) + + \item Multi-hop communication \item Known location by: \begin{itemize} - \item Embedded GPS or - \item Location Discovery Algorithm. + \item Embedded GPS or location discovery algorithm \end{itemize} - \end{enumerate} - - - - \column{.50\textwidth} - \begin{enumerate} [$\divideontimes$] - \item Using two kinds of packet: + + \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: \begin{itemize} - \item LISTENING, ACTIVE, SLEEP, COMPUTATION, and COMMUNICATION. + \item \small LISTENING, ACTIVE, SLEEP, COMPUTATION, and 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} +\begin{frame}{Assumptions for our protocols} + \vspace{-0.5cm} +\begin{center} + \includegraphics[height = 7.0cm]{Figures/Pmodels.pdf} +\end{center} +\end{frame} -\end{enumerate} -\end{femtoBlock} + + +\begin{frame}{Our general scheme} +\vspace{-0.2cm} +\begin{figure}[ht!] + \includegraphics[width=110mm]{Figures/GeneralModel.jpg} + \end{figure} + +\begin{itemize} +\item DiLCO and PeCO $\blacktriangleright$ use one round sensing ($T=1$) +\item MuDiLCO $\blacktriangleright$ uses multiple rounds sensing ($T=1\cdots T$) +\end{itemize} + \end{frame} -%%%%%%%%%%%%%%%%%%%% -%% SLIDE 14.1 %% -%%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small DiLCO Protocol $\blacktriangleright$ Main Idea} -%\vspace{-3.2cm} -\begin{femtoBlock} {}%{Main Idea:\\} +\begin{frame}{Our 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 \textcolor{magenta}{Position coordinates}, \textcolor{violet}{current remaining energy}, \textcolor{cyan}{sensor node ID}, and \textcolor{red}{number of its one-hop live neighbors} + +\end{itemize} -\begin{enumerate} [2.] -\item \textcolor{blue}{ \textbf{ LEADER ELECTION:}}\\ -The selection criteria are, in order of importance: +\item \textcolor{blue}{\textbf{LEADER ELECTION}} $\blacktriangleright$ The selection criteria are, in order \begin{itemize} -\item larger number of neighbors, -\item larger remaining energy, and then in case of equality, -\item larger ID. +\item Larger number of neighbors +\item Larger remaining energy, and then in case of equality +\item Larger ID \end{itemize} -\end{enumerate} -\begin{enumerate} [3.] -\item \textcolor{blue}{ \textbf{ DECISION:}} \\ -Leader solves an integer program (see next slide) to: + + +\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. +\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} -\begin{enumerate} [4.] -\item \textcolor{blue}{ \textbf{ SENSING:}} \\ -Based on Active-Sleep Packet Information: + + +\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. +\item Active sensors will execute their sensing task +\item Sleep sensors will wait a time equal to the period of sensing to wakeup \end{itemize} - \end{enumerate} - -\end{femtoBlock} + \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} @@ -833,14 +765,14 @@ 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} %%%%%%%%%%%%%%%%%%%% @@ -850,7 +782,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ \vspace{0.2cm} \centering -\includegraphics[height = 7.2cm]{Figures/model2.pdf} +\includegraphics[height = 7.2cm]{Figures/modell2.pdf} \end{frame} @@ -964,8 +896,7 @@ 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)}} %%%%%%%%%%%%%%%%%%%% @@ -1038,7 +969,7 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} \begin{figure}[h!] \centering -\includegraphics[scale=0.49]{Figures/model3.pdf} +\includegraphics[scale=0.49]{Figures/modell3.pdf} \end{figure} \end{frame}