\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}
%%%%%%%%%%%%%%%%%%%%
\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}
%%%%%%%%%%%%%%%%%%%%
%% 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}
%%%%%%%%%%%%%%%%%%%%
\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}
\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}
\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}
%%%%%%%%%%%%%%%%%%%%
%% 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).}
\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}
%%%%%%%%%%%%%%%%%%%%
\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.
-\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]
\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}
\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}
%%%%%%%%%%%%%%%%%%%%
%% 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}
%%%%%%%%%%%%%%%%%%%%
\vspace{0.2cm}
\centering
-\includegraphics[height = 7.2cm]{Figures/model2.pdf}
+\includegraphics[height = 7.2cm]{Figures/modell2.pdf}
\end{frame}
-\section{\small {Perimeter-based Coverage Optimization (PeCO) to Improve Lifetime in WSNs
-}}
+\section{\small {Perimeter-based Coverage Optimization (PeCO)}}
%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h!]
\centering
-\includegraphics[scale=0.49]{Figures/model3.pdf}
+\includegraphics[scale=0.49]{Figures/modell3.pdf}
\end{figure}
\end{frame}
