From: ali Date: Mon, 29 Jun 2015 14:22:49 +0000 (+0200) Subject: Update by Ali X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/commitdiff_plain/756ad5dc8d9d6c233545dc73899b374b9fce2618 Update by Ali --- diff --git a/ACRONYMS.tex b/ACRONYMS.tex index c07c9fe..e396dd2 100644 --- a/ACRONYMS.tex +++ b/ACRONYMS.tex @@ -10,76 +10,76 @@ \begin{abbreviations} -\item[WSN] Wireless Sensor Network -\item[DILCO] Distributed Lifetime Coverage Optimization -\item[MuDiLCO] Multiround Distributed Lifetime Coverage Optimization -\item[PeCO] Perimeter-based Coverage Optimization -\item[OMNeT++] Objective Modular Network Testbed -\item[DESK] Distributed Energy-efficient Scheduling for K-coverage -\item[GAF] Geographical Adaptive Fidelity -\item[PDA] Personal Digital Assistant -\item[WLAN] Wireless Local-Area Network -\item[MEMS] Micro-Electro-Mechanical Systems \item[ADC] Analog to Digital Converters -\item[VCO] Voltage-Controlled Oscillator -\item[PLL] Phase-Locked Loop -\item[GPS] Global Positioning System -\item[OS] Operating System -\item[CMOS] Complementary Metal-Oxide-Silicon -\item[MAV] Micro Aerial Vehicle -\item[ECG] Electrocardiogram -\item[SCADA] Supervisory Control and Data Acquisition -\item[QoS] Quality of Service -\item[DSC] Disjoint Set Covers -\item[MIP] Mixed Integer Programming -\item[LP] Linear Programming -\item[GAS] Geometrically based Activity Scheduling -\item[NCG] Node Coverage Grouping +\item[AIMMS] Advanced Interactive Multidimensional Modeling System +\item[AMPL] A Mathematical Programming Language +\item[ASR] Active Sensors Ratio +\item[BCP] Branch Cut and Price +\item[CBC] COIN-OR Branch and Cut \item[CG] Column Generation -\item[MLP] Maximum-network Lifetime Problem -\item[RMP] Restricted Master Problem -\item[PS] Pricing Subproblem -\item[GRASP] Greedy Randomized Adaptive Search Procedure -\item[VNS] Variable Neighborhood Search -\item[CSB] Cover Sets Balance +\item[CMOS] Complementary Metal-Oxide-Silicon \item[CNSC] Correlated Node Set Computing -\item[HREF] High Residual Energy First -\item[SHM] Structural Health Monitoring -\item[ESA] Effective Sensing Area -\item[MSCR] Maximum Sensing Coverage Region +\item[COIN-OR] COmputational INfrastructure for Operations Research +\item[CR] Coverage Ratio +\item[CSB] Cover Sets Balance \item[DASSA] Distributed Adaptive Sleep Scheduling Algorithm +\item[DESK] Distributed Energy-efficient Scheduling for K-coverage +\item[DILCO] Distributed Lifetime Coverage Optimization +\item[DSC] Disjoint Set Covers \item[DTGA] Distributed Truncated Greedy Algorithm +\item[EC] Energy Consumption +\item[ECG] Electrocardiogram +\item[ESA] Effective Sensing Area \item[FIT] Future Internet of the Things -\item[GUI] Graphical User Interface -\item[NED] NEtwork Description -\item[ns-2] Network Simulator-2 -\item[OPNET] Optimized Network Engineering Tool +\item[GAF] Geographical Adaptive Fidelity +\item[GAMS] General Algebraic Modeling System +\item[GAS] Geometrically based Activity Scheduling \item[GloMoSim] Global Mobile System Simulator -\item[SENSE] Sensor Network Simulator and Emulator -\item[GTSNetS] Georgia Tech Sensor Network Simulator +\item[GLPK] GNU Linear Programming Kit \item[GNU] GNU's Not Unix +\item[GPS] Global Positioning System +\item[GRASP] Greedy Randomized Adaptive Search Procedure +\item[GTSNetS] Georgia Tech Sensor Network Simulator +\item[GUI] Graphical User Interface +\item[HREF] High Residual Energy First +\item[IP] Integer Programming \item[LP] Linear Programming -\item[GLPK] GNU Linear Programming Kit -\item[MPS] Mathematical Programming System -\item[COIN-OR] COmputational INfrastructure for Operations Research -\item[BCP] Branch Cut and Price -\item[CBC] COIN-OR Branch and Cut -\item[OPL] Optimization Programming Language -\item[QP] Quadratic Programming -\item[QCP] Quadratically Constrained Programming +\item[MAV] Micro Aerial Vehicle +\item[MCU] Microcontroller Unit +\item[MEMS] Micro-Electro-Mechanical Systems \item[MILP] Mixed Integer Linear Programming +\item[MIP] Mixed Integer Programming \item[MIQP] Mixed-Integer Quadratic Programming \item[MIQCP] Mixed-Integer Quadratically Constrained Programming -\item[AIMMS] Advanced Interactive Multidimensional Modeling System -\item[AMPL] A Mathematical Programming Language -\item[GAMS] General Algebraic Modeling System +\item[MLP] Maximum-network Lifetime Problem \item[MPL] Mathematical Programming Language +\item[MPS] Mathematical Programming System +\item[MSCR] Maximum Sensing Coverage Region +\item[MuDiLCO] Multiround Distributed Lifetime Coverage Optimization +\item[NCG] Node Coverage Grouping +\item[NED] NEtwork Description +\item[ns-2] Network Simulator-2 +\item[OMNeT++] Objective Modular Network Testbed +\item[OPL] Optimization Programming Language +\item[OPNET] Optimized Network Engineering Tool +\item[OS] Operating System +\item[PDA] Personal Digital Assistant +\item[PeCO] Perimeter-based Coverage Optimization +\item[PLL] Phase-Locked Loop +\item[PS] Pricing Subproblem +\item[QCP] Quadratically Constrained Programming +\item[QoS] Quality of Service +\item[QP] Quadratic Programming +\item[RMP] Restricted Master Problem +\item[SCADA] Supervisory Control and Data Acquisition +\item[SENSE] Sensor Network Simulator and Emulator +\item[SHM] Structural Health Monitoring \item[UAV] Unmanned Aerial Vehicle -\item[WSNL] Wireless Sensor Node Leader -\item[MCU] Microcontroller Unit -\item[CR] Coverage Ratio -\item[EC] Energy Consumption -\item[ASR] Active Sensors Ratio +\item[VCO] Voltage-Controlled Oscillator +\item[VNS] Variable Neighborhood Search +\item[WLAN] Wireless Local-Area Network +\item[WSN] Wireless Sensor Network +%\item[WSNL] Wireless Sensor Node Leader \end{abbreviations} diff --git a/CHAPITRE_03.tex b/CHAPITRE_03.tex index 8d7ebc2..6bfb277 100644 --- a/CHAPITRE_03.tex +++ b/CHAPITRE_03.tex @@ -273,9 +273,12 @@ The Gurobi Optimizer~\cite{ref219,ref220,ref211} is a commercial optimization so \end{enumerate} -B. Meindl and M. Templ~\cite{ref212} studied the efficiency of above optimization solvers. They used a set of instances of difficult optimization problems called the attacker problems in order to achieve a performance comparison of GLPK, lp$\_$solve, CLP, GUROBI, and CPLEX optimization solvers. They considered a total of 200 problem instances for this study, 100 of these problem instances are based on problems with two dimensions, and 100 problem instances are three-dimensional. +B. Meindl and M. Templ~\cite{ref212} studied the efficiency of above optimization solvers. They used a set of instances of a difficult optimization problem called the Attacker problems (formulated as a LP) \cite{ref240} in order to achieve a performance comparison of GLPK, lp$\_$solve, CLP, GUROBI, and CPLEX optimization solvers. %They considered a total of 200 problem instances for this study, 100 of these problem instances are based on problems with two dimensions, and 100 problem instances are three-dimensional. -In tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} we report the result of their comparisons the running times of the five linear program solvers to find solutions to the 200 two-dimensional, 200 three-dimensional, and all 400 problem instances. In order to solve the attacker’s problem for a given problem instance, it is needed to both minimize and maximize any given problem. Therefore, a total of 400 problem instances had been solved when only 200 problem instances have been generated. The running time of the fastest solver has been scaled to one and the running times of the other linear solvers were scaled to reflect this scaling. +In tables~\ref{my-label1} and \ref{my-label2}, we report the result of their comparisons the running times of the five linear program solvers to find solutions for instances related to the two-dimensional problem, and for instances related to the three-dimensional problem (with more variables and constraints). +%to the 200 two-dimensional, 200 three-dimensional, and all 400 problem instances. +%In order to solve the attacker’s problem for a given problem instance, it is needed to both minimize and maximize any given problem. Therefore, a total of 400 problem instances had been solved when only 200 problem instances have been generated. +The running time of the fastest solver has been scaled to one and the running times of the other linear solvers were scaled to reflect this scaling. \begin{table}[h] @@ -306,21 +309,21 @@ In tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} we report the re \end{table} -\begin{table}[h] -\caption{Total (in seconds) and scaled running times for all problems (results of B. Meindl and M. Templ~\cite{ref212})} -\label{my-label3} -\resizebox{\textwidth}{!}{% -\begin{tabular}{|c|c|c|c|c|c|} -\hline -\textbf{Optimization Solvers} & \textbf{GLPK} & \textbf{lp\_solve} & \textbf{CLP} & \textbf{Gurobi} & \textbf{CPLEX} \\ \hline -\textbf{Total Running Time} & 48585 & 982737 & 667066 & 38708 & 257 \\ \hline -\textbf{Scaled Running Time} & 189 & 3822 & 2594 & 151 & 1 \\ \hline -\end{tabular} -} -\end{table} +%\begin{table}[h] +%\caption{Total (in seconds) and scaled running times for all problems (results of B. Meindl and M. Templ~\cite{ref212})} +%\label{my-label3} +%\resizebox{\textwidth}{!}{% +%\begin{tabular}{|c|c|c|c|c|c|} +%\hline +%\textbf{Optimization Solvers} & \textbf{GLPK} & \textbf{lp\_solve} & \textbf{CLP} & \textbf{Gurobi} & \textbf{CPLEX} \\ \hline +%\textbf{Total Running Time} & 48585 & 982737 & 667066 & 38708 & 257 \\ \hline +%\textbf{Scaled Running Time} & 189 & 3822 & 2594 & 151 & 1 \\ \hline +%\end{tabular} +%} +%\end{table} -The results in tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} indicate that open source solvers perform worse than standard commercial solvers when applied to instances of the attacker’s problem. The GLPK outperforms the other free and open source solvers, but is still slower than CPLEX and GUROBI. We have decided to use the GLPK as an optimization solver in this dissertation to solve the proposed integer programs during the decision phase of the nodes. We motivate the use of the GLPK optimization solver for many reasons, including: +The results in tables~\ref{my-label1} and \ref{my-label2} indicate that open source solvers perform worse than standard commercial solvers when applied to instances of the attacker’s problem. The GLPK outperforms the other free and open source solvers, but is still slower than CPLEX and GUROBI. We have decided to use the GLPK as an optimization solver in this dissertation to solve the proposed integer programs during the decision phase of the nodes. We motivate the use of the GLPK optimization solver for many reasons, including: \begin{enumerate} [(i)] diff --git a/CHAPITRE_04.tex b/CHAPITRE_04.tex index f0f1415..a692dc3 100644 --- a/CHAPITRE_04.tex +++ b/CHAPITRE_04.tex @@ -350,7 +350,7 @@ The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is employ \label{tab:EC} \begin{tabular}{|l||cccc|} \hline - {\bf Sensor status} & MCU & Radio & Sensor & {\it Power (mW)} \\ + {\bf Sensor status} & MCU & Radio & Sensing & {\it Power (mW)} \\ \hline LISTENING & On & On & On & 20.05 \\ ACTIVE & On & Off & On & 9.72 \\ diff --git a/CONCLUSION.tex b/CONCLUSION.tex index 317c8bb..099f6db 100644 --- a/CONCLUSION.tex +++ b/CONCLUSION.tex @@ -14,7 +14,7 @@ The first part of the dissertation has presented the scientific background inclu In chapter 1, we have started with a general overview on wireless sensor networks. We have described various concepts, mechanisms, types, applications, and challenges in WSNs. Several energy-efficient techniques so as to improve the network lifetime of WSNs have been presented. The coverage problem, the network lifetime, and the energy consumption modeling in WSNs have been explained. A brief survey about literature on coverage algorithms is achieved in chapter 2. We have classified those works into centralized and distributed algorithms. We have given a brief comparison of the main characteristics of each approach. Finally we have included in chapter 3 a comparative study of different evaluation tools dedicated to WSNs. In addition, we have illustrated various commercial and free optimization solvers considering the main features of each one. -In the second part of the dissertation, We have designed three new different optimization protocols, which schedule nodes’ activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. We propose two-step approaches. Firstly, the field of sensing is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of the proposed optimization protocols is applied in each subregion in a distributed parallel way to optimize both coverage and lifetime performances. The proposed protocols combine two efficient mechanisms: network leader election and sensor activity scheduling, where the challenges include how to select the most efficient leader in each subregion, the best +In the second part of the dissertation, we have designed three new different optimization protocols, which schedule nodes’ activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. We propose two-step approaches. Firstly, the field of sensing is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of the proposed optimization protocols is applied in each subregion in a distributed parallel way to optimize both coverage and lifetime performances. The proposed protocols combine two efficient mechanisms: network leader election and sensor activity scheduling, where the challenges include how to select the most efficient leader in each subregion, the best representative active nodes that will optimize the network lifetime while taking the responsibility of covering the corresponding subregion. diff --git a/INTRODUCTION.tex b/INTRODUCTION.tex index 8c3b11a..325a384 100644 --- a/INTRODUCTION.tex +++ b/INTRODUCTION.tex @@ -51,10 +51,10 @@ The main contributions in this dissertation concentrate on designing distributed The MuDiLCO protocol for Multiround Distributed Lifetime Coverage Optimization protocol, presented in chapter 5, is an extension of the approach introduced in chapter 4. In the DiLCO protocol, the activity scheduling based optimization is planned for each subregion periodically only for one sensing round. We study the possibility of dividing the sensing phase into multiple rounds. In fact, we make a multiround optimization, while it was a single round optimization in our previous contribution. The activation of the sensors is planned for many rounds in advance compared with the previous approach. %\item We devise a framework to schedule nodes to be activated alternatively such that the network lifetime is prolonged while ensuring that a certain level of coverage is preserved. A key idea in our framework is to exploit the spatial-temporal subdivision. On the one hand, the area of interest is divided into several smaller subregions and, on the other hand, the timeline is divided into periods of equal length. In each subregion, the sensor nodes will cooperatively choose a leader which will schedule nodes' activities, and this grouping of sensors is similar to typical cluster architecture. - + \item We design a third protocol, called Perimeter-based Coverage Optimization (PeCO). %which schedules nodes’ activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. This protocol is applied in a distributed way in regular subregions obtained after partitioning the area of interest in a preliminary step. It works in periods and is based on the resolution of an integer program to select the subset of sensors operating in active status for each period. -We have proposed a new mathematical optimization model. Instead of trying to cover a set of specified points/targets as in previous protocols and most of the methods proposed in the literature, we formulate mixed-integer program based on perimeter coverage of each sensor. The model involves integer variables to capture the deviations between the actual level of coverage and the required level. The idea is that an optimal scheduling will be obtained by minimizing a weighted sum of these deviations. This contribution is demonstrated in chapter 6. +We have proposed a new mathematical optimization model. Instead of trying to cover a set of specified points/targets as in previous protocols and most of the methods proposed in the literature, we formulate a mixed-integer program based on perimeter coverage of each sensor. The model involves integer variables to capture the deviations between the actual level of coverage and the required level. The idea is that an optimal scheduling will be obtained by minimizing a weighted sum of these deviations. This contribution is demonstrated in chapter 6. \item %We add an improved model of energy consumption to assess the efficiency of our protocols. We conducted extensive simulation experiments using the discrete event simulator OMNeT++, to demonstrate the efficiency of our protocols. We compared our proposed distributed optimization protocols with two approaches found in the literature: DESK~\cite{DESK} and GAF~\cite{GAF}. Simulation results based on multiple criteria (energy consumption, coverage ratio, network lifetime and so on) show that the proposed protocols can prolong efficiently the network lifetime and improve the coverage performance. diff --git a/Resume.tex b/Resume.tex index e3dbc74..7f4976f 100644 --- a/Resume.tex +++ b/Resume.tex @@ -19,7 +19,7 @@ Les réseaux de capteurs sans fil ont suscité beaucoup de travaux de recherche au cours des dernières années en raison de leur large gamme d'applications potentielles. Les caractéristiques des n\oe uds capteurs imposent des contraintes de consommation d'énergie et de capacité de traitement qui rendent caduque les protocoles des réseaux ad-hoc sans fil, avec de nombreux défis à résoudre. Parmi ces défis, on peut noter la préservation de la couverture, le contrôle de la topologie, le routage, la fusion de données, la sécurité, etc. La préservation de la couverture d'une région à surveiller, de manière permanente et efficace, tout en empêchant autant que possible un dysfonctionnement du réseau en raison du déchargement de la batterie de certains n\oe uds, est une des problématiques de recherche majeures. -Dans cette thèse, nous nous sommes intéressés au problème de la préservation de la couverture, ainsi qu'à efficacité qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudié les protocoles d'optimisation distribués avec l'objectif de prolonger la durée de vie opérationnelle du réseau. Les protocoles proposés doivent être efficaces en consommation énergétique induite par les calculs et les communications. Pour résoudre le problème, nous avons proposé des nouvelles approches qui s'articulen autour de deux étapes. Dans un premier temps, la région à surveiller est divisée en petites sous-régions en utilisant le concept de la méthode diviser pour mieux régner. Dans un second temps, un protocole est exécuté par chacun des n\oe uds capteurs dans chaque sous-région, afin d'optimiser la couverture et la durée de vie du réseau. Nous proposons trois protocoles distribués qui combinent, chacun, deux techniques efficaces: l'élection d'un n\oe ud leader dans chaque sous-région, suivie par la mise en oeuvre par celui-ci d'un processus d'ordonnancement d'activité des n\oe uds capteurs de sa sous-région. +Dans cette thèse, nous nous sommes intéressés au problème de la préservation de la couverture, ainsi qu'à efficacité qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudié les protocoles d'optimisation distribués avec l'objectif de prolonger la durée de vie opérationnelle du réseau. Les protocoles proposés doivent être efficaces en consommation énergétique induite par les calculs et les communications. Pour résoudre le problème, nous avons proposé des nouvelles approches qui s'articulent autour de deux étapes. Dans un premier temps, la région à surveiller est divisée en petites sous-régions en utilisant le concept de la méthode diviser pour mieux régner. Dans un second temps, un protocole est exécuté par chacun des n\oe uds capteurs dans chaque sous-région, afin d'optimiser la couverture et la durée de vie du réseau. Nous proposons trois protocoles distribués qui combinent, chacun, deux techniques efficaces: l'élection d'un n\oe ud leader dans chaque sous-région, suivie par la mise en oeuvre par celui-ci d'un processus d'ordonnancement d'activité des n\oe uds capteurs de sa sous-région. Le premier protocole proposé est appelé DiLCO, pour Distributed Lifetime Coverage Optimization. Dans ce protocole, la durée de vie est divisée en périodes, avec chaque période qui est composée de 4 phases: échange d'informations entre les n\oe uds d'une sous-région, élection d'un n\oe ud leader, phase de décision et surveillance. Le processus de décision est mis en oeuvre par le n\oe ud leader en résolvant un programme linéaire en nombres entiers qui permet de définir l'ensemble des n\oe uds de capteurs devant être actifs pour assurer la couverture durant la période courante. @@ -31,7 +31,8 @@ Dans le second protocole, qui est une évolution de DiLCO, nous cherchons à con %Ensuite, nous avons étudié le problème de l'optimisation multi-ronde de la zone de couverture dans un réseau de capteurs sans fil. Nous avons proposé le protocole d'optimisation multi-ronde distribué de la durée de vie de couverture (MuDiLCO) pour étudier la possibilité de fournir plusieurs ensembles de n\oe uds de capteurs de couverture pour la phase de surveillance. Ce protocole travaille également en périodes pendant lesquelles les ensembles de capteurs sont programmés pour rester actifs pour un certain nombre de rondes durant la phase de surveillance, pour assurer la couverture et maximiser la durée de vie du réseau. Le processus de décision est toujours effectué par le n\oe ud leader qui résout un programme entier pour définir un meilleur ensemble de capteurs à être utilisé pendant les rondes de la phase de surveillance. -Enfin, nous avons proposé un protocole d'optimisation de la couverture basé sur la couverture périmètre du capteurs (PeCO), qui est aussi un protocole distribué sur les n\oe uds de capteurs dans chaque sous-région. Notre contribution dans ce protocole consiste essentiellement dans la proposition d'un nouveau modèle d'optimisation basé sur le périmètre de couverture pour l'ordonnancement de l'activité des capteurs. Ce modèle de couverture est résolu par le leader durant la phase de décision pour définir un ensemble de capteurs actifs pour la phase de surveillance. +Enfin, nous avons proposé un protocole d'optimisation de la +couverture basé sur la couverture DU périmètre des capteurs (PeCO), qui est aussi un protocole distribué sur les n\oe uds de capteurs dans chaque sous-région. Notre contribution dans ce protocole consiste essentiellement dans la proposition d'un nouveau modèle d'optimisation basé sur le périmètre de couverture pour l'ordonnancement de l'activité des capteurs. Ce modèle de couverture est résolu par le leader durant la phase de décision pour définir un ensemble de capteurs actifs pour la phase de surveillance. Nous avons effectué plusieurs simulations en utilisant le simulateur à évènements discrets OMNeT++ pour valider l'efficacité de nos protocoles. Nous avons pris en considération les caractéristiques d'un capteur Medusa II pour la consommation d'énergie et le temps de calcul. En comparaison avec deux autres méthodes existantes, nos protocoles ont la capacité d'augmenter la durée de vie du réseau de capteurs et d'améliorer les performances de couverture. diff --git a/Thesis.toc b/Thesis.toc index ec2e93a..633865a 100644 --- a/Thesis.toc +++ b/Thesis.toc @@ -103,4 +103,4 @@ \contentsline {section}{\numberline {7.1}Conclusion}{129}{section.7.1} \contentsline {section}{\numberline {7.2}Perspectives}{130}{section.7.2} \contentsline {part}{Publications}{133}{chapter*.13} -\contentsline {part}{Bibliographie}{147}{chapter*.17} +\contentsline {part}{Bibliographie}{148}{chapter*.17} diff --git a/bib.bib b/bib.bib index 24ed356..155361b 100644 --- a/bib.bib +++ b/bib.bib @@ -2264,4 +2264,15 @@ title = {Perimeter Coverage Scheduling in Wireless Sensor Networks Using Sensors journal = {EURASIP Journal on Wireless Communications and Networking }, volume = {2010}, year = {2010} +} + +@article{ref240, + title={Solving the cell suppression problem on tabular data with linear constraints}, + author={Fischetti, Matteo and Salazar, Juan Jos{\'e}}, + journal={Management Science}, + volume={47}, + number={7}, + pages={1008--1027}, + year={2001}, + publisher={INFORMS} } \ No newline at end of file