X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/127dd5ebfa42d2c6220639b057082517a4502c38..471e797ea207eea3a79a42ef48e6c3b14f3c004b:/SlidesAli/These.tex?ds=inline diff --git a/SlidesAli/These.tex b/SlidesAli/These.tex index 4658b27..2e7b91c 100644 --- a/SlidesAli/These.tex +++ b/SlidesAli/These.tex @@ -52,7 +52,7 @@ \setbeamertemplate{section in toc}[sections numbered] \setbeamertemplate{subsection in toc}[subsections numbered] - +\pagenumbering{roman} \AtBeginSection[] { \begin{frame} @@ -101,17 +101,17 @@ \begin{frame} {Problem Definition, Solution, and Objectives} \vspace{-3.5em} \begin{figure} - \includegraphics[width=0.475\textwidth]{Figures/6} + \includegraphics[width=0.495\textwidth]{Figures/6} \hfill % \includegraphics[width=0.475\textwidth]{Figures/8} % \hfill - \includegraphics[width=0.475\textwidth]{Figures/10} + \includegraphics[width=0.495\textwidth]{Figures/10} % \hfill % \includegraphics[width=0.475\textwidth]{Figures/13} \end{figure} \begin{block}{\textcolor{white}{ MAIN QUESTION?}} - How to reduce the redundancy while coverage preservation for prolong the network lifetime continuously and effectively when monitoring a certain area of interest? + \textcolor{black}{How to minimize the energy consumption and extend the network lifetime during covering a certain area?} \end{block} \end{frame} @@ -122,10 +122,10 @@ \begin{frame}{Problem Definition, Solution, and Objectives} \begin{block}{\textcolor{white}{OUR SOLUTION}} -The area of interest is divided into subregions using a divide-and conquer method and then combine two efficient techniques : +\bf \textcolor{black}{The area of interest is divided into subregions using a divide-and conquer method and then combine two efficient techniques:} \begin{itemize} - \item Leader Election for each subregion. + \item \bf \textcolor{magenta}{Leader Election for each subregion.} % \item Activity Scheduling based optimization is planned for each subregion. \end{itemize} @@ -146,7 +146,7 @@ The area of interest is divided into subregions using a divide-and conquer metho \begin{block}{\textcolor{white}{OUR SOLUTION}} \begin{itemize} %\item Leader Election for each subregion. - \item Activity Scheduling based optimization is planned for each subregion. + \item \bf \textcolor{magenta}{Activity Scheduling based optimization is planned for each subregion.} \end{itemize} \end{block} @@ -162,12 +162,12 @@ The area of interest is divided into subregions using a divide-and conquer metho %%%%%%%%%%%%%%%%%%%% \begin{frame}{Problem Definition, Solution, and Objectives} -\begin{block}{\textcolor{white}{Dissertation Objectives}} -Develop energy-efficient distributed optimization protocols that should be able to: +\begin{block}{\bf \textcolor{white}{Dissertation Objectives}} +\bf \textcolor{black}{Develop energy-efficient distributed optimization protocols that should be able to:} \begin{itemize} - \item Schedule node activities by optimize both coverage and lifetime. - \item Combine two efficient techniques: leader election and sensor activity scheduling. - \item Perform a distributed optimization process. + \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} @@ -310,18 +310,19 @@ Develop energy-efficient distributed optimization protocols that should be able %%%%%%%%%%%%%%%%%%%% \begin{frame}{Network Lifetime} \vspace{-1.5em} -\begin{block}{\textcolor{white} {Some network lifetime defintions:}} +\begin{block}{\textcolor{white} {Some Network Lifetime Definitions:}} +\small \begin{enumerate}[i)] -\item \small Time spent until death of the first sensor ( or cluster head ). -\item Time spent until death of all wireless sensor nodes in WSN. -\item Time spent by WSN in covering each target by at least one sensor. -\item Time during which the area of interest is covered by at least k nodes. -\item Elapsed time until losing the connectivity or the coverage. +\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.} \end{enumerate} \end{block} \begin{block}{\textcolor{white} {Network lifetime In this dissertation:}} -Time elapsed until the coverage ratio becomes less than a predetermined threshold $\alpha$. +\textcolor{blue} {Time elapsed until the coverage ratio becomes less than a predetermined threshold $\alpha$.} \end{block} @@ -340,17 +341,17 @@ Time elapsed until the coverage ratio becomes less than a predetermined threshol \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:} is to cover only a finite number of discrete points called targets. +\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. -\item \textcolor{blue} {Barrier coverage:} is to detect targets as they cross a barrier such as in intrusion detection and border surveillance applications. +\item \textcolor{blue} {Barrier coverage:} 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 area coverage. +The work presented in this dissertation deals with \textcolor{red} {area coverage}. \end{block} \end{frame} @@ -367,13 +368,13 @@ Most existing coverage approaches in literature classified into \begin{itemize} \item Optimal or near optimal solution. \item low computation power for the sensors (except for base station). - \item High communication overhead. + \item Higher energy consumption for communication in large WSN. \item Not scalable for large WSNs. \end{itemize} \item Full distributed coverage algorithms. \begin{itemize} \item Lower quality solution. - \item High communication overhead especially for dense WSNs. + \item less energy consumption for communication in large WSN. \item Reliable and scalable for large WSNs. \end{itemize} \end{enumerate} @@ -388,6 +389,79 @@ The protocols presented in this dissertation combine between the two above appro \end{frame} +\begin{frame}{Existing Works: DESK algorithm} +\vspace{-1.5em} +\begin{figure}[!t] + \includegraphics[height = 3.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. + + \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.} + + +\end{frame} + +\begin{frame}{Existing Works: GAF algorithm} +%\vspace{-0.3em} +\vspace{-3.3em} + \begin{columns}[c] + +\column{.58\textwidth} + + \begin{figure}[!t] + \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} + + \column{.52\textwidth} + +% \begin{itemize} +% \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} + + + +\end{columns} + +\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.} + + + +\end{frame} %%%%%%%%%%%%%%%%%%%% %% SLIDE 12 %% @@ -421,7 +495,7 @@ The protocols presented in this dissertation combine between the two above appro \item Heterogeneous Energy. \item Its $R_c\geq 2R_s$. \item Multi-hop communication. - \item Know Its location by: + \item Known location by: \begin{itemize} \item Embedded GPS or \item Location Discovery Algorithm. @@ -504,7 +578,7 @@ The selection criteria are, in order of importance: \begin{enumerate} [3.] \item \textcolor{blue}{ \textbf{ DECISION:}} \\ -Leader solves an integer program(see next slide) to: +Leader solves an integer program (see next slide) 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. @@ -529,8 +603,7 @@ Based on Active-Sleep Packet Information: %% SLIDE 15 %% %%%%%%%%%%%%%%%%%%%% \begin{frame}{\small DiLCO Protocol $\blacktriangleright$ Coverage Problem Formulation} -\begin{femtoBlock} { } -\noindent Our coverage optimization problem can then be formulated as follows: +\vspace{-0.3cm} \begin{equation*} \label{eq:ip2r} \left \{ \begin{array}{ll} @@ -546,17 +619,20 @@ X_{j} \in \{0,1\}, &\forall j \in J \end{array} \right. \end{equation*} - +\vspace{-0.3cm} \begin{itemize} -\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 +\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} -\end{femtoBlock} + \end{frame} @@ -583,7 +659,7 @@ X_{j} \in \{0,1\}, &\forall j \in J \vspace{-0.8cm} \small \begin{table}[ht] -\caption{Relevant parameters for network initializing.} +\caption{Relevant parameters for simulation.} \centering \begin{tabular}{c|c} \hline @@ -639,11 +715,12 @@ Network Simulator & Discrete Event Simulator OMNeT++ \begin{femtoBlock} {Performance Metrics} \small \begin{enumerate}[$\mapsto$] -\item {{\bf Network Lifetime}} + \item {{\bf Coverage Ratio (CR)}} +\item{{\bf Number of Active Sensors Ratio (ASR)}} \item {{\bf Energy Consumption}} -\item{{\bf Number of Active Sensors Ratio (ASR)}} -\item {{\bf Execution Time}} +\item {{\bf Network Lifetime}} +%\item {{\bf Execution Time}} %\item {{\bf Stopped Simulation Runs}} \end{enumerate} @@ -756,7 +833,7 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% %% SLIDE 28 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Main Idia} +\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Main Idea} \vspace{-0.2cm} \begin{figure}[ht!] \includegraphics[width=110mm]{Figures/GeneralModel.jpg} @@ -771,54 +848,22 @@ Network Simulator & Discrete Event Simulator OMNeT++ %%%%%%%%%%%%%%%%%%%% \begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Multiround Coverage Problem Formulation} \vspace{0.2cm} -\small -Our coverage optimization problem can then be formulated as follows -\vspace{-0.2cm} -\begin{equation*} - \min \sum_{t=1}^{T} \sum_{p=1}^{P} \left(W_{\theta}* \Theta_{t,p} + W_{U} * U_{t,p} \right) \label{eq15} -\end{equation*} - -Subject to -\vspace{-0.2cm} -\begin{equation*} - \sum_{j=1}^{|J|} \alpha_{j,p} * X_{t,j} = \Theta_{t,p} - U_{t,p} + 1 \label{eq16} \hspace{6 mm} \forall p \in P, t = 1,\dots,T -\end{equation*} - -\begin{equation*} - \sum_{t=1}^{T} X_{t,j} \leq \lfloor {RE_{j}/E_{th}} \rfloor \hspace{6 mm} \forall j \in J, t = 1,\dots,T - \label{eq144} -\end{equation*} - -\begin{equation*} -X_{t,j} \in \lbrace0,1\rbrace, \hspace{10 mm} \forall j \in J, t = 1,\dots,T \label{eq17} -\end{equation*} - -\begin{equation*} -U_{t,p} \in \lbrace0,1\rbrace, \hspace{10 mm}\forall p \in P, t = 1,\dots,T \label{eq18} -\end{equation*} - -\begin{equation*} - \Theta_{t,p} \geq 0 \hspace{10 mm}\forall p \in P, t = 1,\dots,T \label{eq178} -\end{equation*} - - - - +\centering +\includegraphics[height = 7.2cm]{Figures/model2.pdf} \end{frame} %%%%%%%%%%%%%%%%%%%% %% SLIDE 30 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ MuDiLCO Protocol Algorithm} -%\vspace{0.2cm} -\begin{femtoBlock} {} -\centering -%\includegraphics[height = 7.2cm]{Figures/algo2.jpeg} -\includegraphics[height = 7.2cm]{Figures/Algo2.png} -\end{femtoBlock} -\end{frame} +%\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ MuDiLCO Protocol Algorithm} +%%\vspace{0.2cm} +%\begin{femtoBlock} {} +%\centering +%\includegraphics[height = 7.2cm]{Figures/Algo2.png} +%\end{femtoBlock} +%\end{frame} %%%%%%%%%%%%%%%%%%%% @@ -865,15 +910,15 @@ U_{t,p} \in \lbrace0,1\rbrace, \hspace{10 mm}\forall p \in P, t = 1,\dots,T \la %%%%%%%%%%%%%%%%%%%% %% SLIDE 34 %% %%%%%%%%%%%%%%%%%%%% -\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Results Analysis and Comparison} -\vspace{-0.5cm} -\begin{figure}[h!] -\centering -\includegraphics[scale=0.5]{Figures/R1/T.pdf} -\caption{Execution Time (in seconds)} -\label{fig77} -\end{figure} -\end{frame} +%\begin{frame}{\small MuDiLCO Protocol $\blacktriangleright$ Results Analysis and Comparison} +%\vspace{-0.5cm} +%\begin{figure}[h!] +%\centering +%\includegraphics[scale=0.5]{Figures/R1/T.pdf} +%\caption{Execution Time (in seconds)} +%\label{fig77} +%\end{figure} +%\end{frame} %%%%%%%%%%%%%%%%%%%% @@ -989,11 +1034,11 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} %% SLIDE 48 %% %%%%%%%%%%%%%%%%%%%% \begin{frame}{\small PeCO Protocol $\blacktriangleright$ Perimeter-based Coverage Problem Formulation} -\vspace{-1.1cm} +\vspace{-0.7cm} \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{Figures/ch6/formula6.png} +\includegraphics[scale=0.49]{Figures/model3.pdf} \end{figure} \end{frame} @@ -1012,6 +1057,7 @@ $$\alpha = \arccos \left(\dfrac{Dist(u,v)}{2R_s} \label{fig333} \end{figure} + \end{frame} %%%%%%%%%%%%%%%%%%%% @@ -1110,7 +1156,7 @@ phases: \begin{itemize} \item Information exchange, \item Network leader election, -\item Decision based optimization, and +\item Decision based optimization, \item Sensing. \end{itemize} \end{enumerate} @@ -1142,19 +1188,47 @@ phases: \end{enumerate} \end{frame} +\begin{frame}{Conclusion} +\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. 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. Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks. \textit{Journal of Supercomputing , 2015, (Submitted)}. +\end{enumerate} +\end{block} + +\begin{block}{\textcolor{white}{Technical Reports}} + +\begin{enumerate}[$\lbrack$1$\rbrack$] +\item Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el +Distributed lifetime coverage optimization protocol in wireless sensor networks. Technical Report DISC2014-X, University of Franche-Comte - FEMTO-ST Institute, DISC Research Department, Octobre 2014. +\end{enumerate} +\end{block} + +\begin{block}{\textcolor{white}{Conference Articles}} +\begin{enumerate}[$\lbrack$1$\rbrack$] +\item Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el +Coverage and lifetime optimization in heterogeneous energy wireless sensor networks. In ICN 2014, The Thirteenth International Conference on Networks, pages 49–54, 2014. +\end{enumerate} +\end{block} + +\end{frame} %%%%%%%%%%%%%%%%%%%% %% SLIDE 52 %% %%%%%%%%%%%%%%%%%%%% \begin{frame}{Perspectives} \begin{enumerate} [$\blacktriangleright$] -\item The optimal number of subregions will be investigated. +\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 We plan to consider particle swarm optimization or evolutionary algorithms to obtain quickly near optimal solutions. +\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. +%\item The cluster head will be selected in a distributed way and based on local information. \end{enumerate}