From: ali Date: Sun, 28 Jun 2015 12:10:16 +0000 (+0200) Subject: Update by Ali X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/commitdiff_plain/f9157ba2e39271ecb959fbf34a56449b890e5eb7 Update by Ali --- diff --git a/CONCLUSION.tex b/CONCLUSION.tex index 7485fe1..317c8bb 100644 --- a/CONCLUSION.tex +++ b/CONCLUSION.tex @@ -11,20 +11,24 @@ In this dissertation, we have concentrated on the design of distributed optimiza The first part of the dissertation has presented the scientific background including WSNs, brief survey of related works, and evaluation tools as well as optimization solvers. -In chapter 1, We 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. +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 design three new different optimization protocols, which schedules 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. -In chapter 4, we propose an optimization protocol called Distributed Lifetime Coverage Optimization protocol (DiLCO), which optimizes the coverage and the lifetime of a wireless sensor network. DiLCO protocol is distributed in each sensor node in the subregions of the sensing field. It is implemented in each subregion simultaneously and independently. The proposed DiLCO protocol is a periodic protocol where each period consists of 4 phases: information exchange, leader election, decision, and sensing. The sensor nodes collaborate in each subregion to elect the leader. The leader applies activity scheduling based optimization in order to provide only one optimal set of active sensor nodes that takes the mission of sensing during this period. The performance of our DiLCO protocol has been evaluated by a series of simulations. We have presented a comparison between our proposed protocol and two other existing protocols known in the literature: DESK and GAF. The experimental results have validated our protocol and showed its efficiency in the optimization of the coverage and the lifetime compared to the two benchmarking methods. +In chapter 4, we propose an optimization protocol called Distributed Lifetime Coverage Optimization protocol (DiLCO), which optimizes the coverage and the lifetime of a wireless sensor network. DiLCO protocol is distributed in each sensor node in the subregions of the sensing field. It is implemented in each subregion simultaneously and independently. The proposed DiLCO protocol is a periodic protocol where each period consists of 4 phases: information exchange, leader election, decision, and sensing. The sensor nodes collaborate in each subregion to elect the leader. The leader applies activity scheduling based on optimization in order to provide only one optimal set of active sensor nodes that takes the mission of sensing during this period. The performance of our DiLCO protocol has been evaluated by a series of simulations. We have presented a comparison between our proposed protocol and two other existing protocols known in the literature: DESK and GAF. The experimental results have validated our protocol and showed its efficiency in the optimization of the coverage and the lifetime compared to the two benchmarking methods. -Next, we propose in chapter 5 a method called Multiround Distributed Lifetime Coverage Optimization protocol (MuDiLCO), which is an extension of the DiLCO protocol introduced in chapter 4. MuDiLCO implemented an activity scheduling based optimization in order to provide multiple sets of active sensor nodes, for several rounds in the sensing phase. We have thus introduced an improved coverage optimization model that make a multiround optimization, whilst it was a single round optimization in DiLCO. We have conducted many simulations comparing the proposed MuDiLCO protocol for different number of rounds, as well as with DiLCO, DESK, and GAF. +Next, we have proposed in chapter 5 a method called Multiround Distributed Lifetime Coverage Optimization protocol (MuDiLCO), which is an extension of the DiLCO protocol introduced in chapter 4. MuDiLCO provides multiple sets of active sensor nodes, for several rounds in the sensing phase. We have thus introduced an improved coverage optimization model that make a multiround optimization, whilst it was a single round optimization in DiLCO. We have conducted many simulations comparing the proposed MuDiLCO protocol for different number of rounds, as well as with DiLCO, DESK, and GAF. -In chapter 6, we propose an approach called Perimeter-based Coverage Optimization protocol (PeCO) in order to optimize the lifetime coverage, so that it provides activity scheduling which ensures sensing coverage as long as possible. Like DiLCO and MuDiLCO, the PeCO protocol is distributed among sensor nodes in each subregion. The novelty of our approach, in comparison with DiLCO and MuDiLCO, lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule sensors’ activities. A leader provides one schedule during the current period by executing the new integer program during the decision phase. The extensive simulation experiments have demonstrated that PeCO can offer longer lifetime coverage for WSNs. +In chapter 6, we have proposed an approach called Perimeter-based Coverage Optimization protocol (PeCO), which schedules nodes' activities (wake up and sleep stages) with +the objective of maintaining a good coverage ratio while maximizing the network +lifetime. +%in order to optimize the lifetime coverage, so that it provides activity scheduling which ensures sensing coverage as long as possible. + Like DiLCO and MuDiLCO, the PeCO protocol is distributed among sensor nodes in each subregion. The novelty of our approach, in comparison with DiLCO and MuDiLCO, lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule sensors’ activities. A leader provides one schedule during the current period by executing the new integer program during the decision phase. The extensive simulation experiments have demonstrated that PeCO can offer longer lifetime coverage for WSNs. Finally, we outline some interesting issues that will be considered in our perspectives which are discussed in more detail next. @@ -34,12 +38,14 @@ Finally, we outline some interesting issues that will be considered in our persp In this dissertation, we have focused on the lifetime area coverage optimization problem and we were interested only in energy-efficient distributed protocols, considering static homogeneous sensor nodes. Several parameters, constraints, and requirements can have an important impact on the coverage performance in WSNs. Thus, various scenarios parameters might need to be taken into consideration in the future, such as fault-tolerance, k-coverage, $\alpha$-coverage, adjustable sensor’s sensing range network, heterogeneous network, mobility, etc. -In chapter 4, we have studied the impact of the number of subregions chosen to subdivide the area of interest, considering different network sizes. The optimal number of subregions will be investigated in the future. We also plan to study and propose a coverage protocol, which computes all active sensor schedules in one time, using optimization methods such as particle swarm optimization or evolutionary algorithms. A period will still consist of 4 phases, but the decision phase will compute the schedules for several sensing rounds which, aggregated together, define a kind of meta-sensing round. The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead. +In chapter 4, we have studied the impact of the number of subregions chosen to subdivide the area of interest, considering different network sizes. The optimal number of subregions will be investigated in the future. We also plan to study and propose a coverage protocol, which computes all active sensor schedules in one time, using optimization methods such as particle swarm optimization or evolutionary algorithms. +%A period will still consist of 4 phases, but the decision phase will compute the schedules for several sensing rounds which, aggregated together, define a kind of meta-sensing round. +The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead. -We also plan to design and propose a heterogeneous integrated optimization protocol in WSNs. This protocol would integrate three energy-efficient (coverage, routing and data aggregation) protocols so as to extend the network lifetime in WSNs. The sensing, routing, and aggregation jobs are also challenges in WSNs. This integrated optimization protocol will be executed by each cluster head, a leader node in our protocols, in the wireless sensor network. The cluster head will be selected in a distributed way and based on local information. +We also plan to design and propose a heterogeneous integrated optimization protocol in WSNs. This protocol would integrate three energy-efficient (coverage, routing and data aggregation) protocols so as to extend the network lifetime in WSNs. The sensing, routing, and aggregation jobs are also challenges in WSNs. This integrated optimization protocol will be executed by each cluster head, a leader node in our protocols. The cluster head will be selected in a distributed way and based on local information. -We plan to extend our PeCO protocol so that the schedules are planned for multiple sensing periods. We also want to improve our integer program to take into account heterogeneous sensors from both energy and node characteristics point of views. +We plan to extend our PeCO protocol so that the schedules are planned for multiple sensing periods. We also want to improve our mathematical model to take into account heterogeneous sensors from both energy and node characteristics point of views. Finally, it would be interesting to implement our protocols using a sensor-testbed to evaluate it in real world applications. diff --git a/entete.tex b/entete.tex index 96a4eb9..f63aa14 100644 --- a/entete.tex +++ b/entete.tex @@ -98,7 +98,7 @@ %%-------------------- %% Set the English abstract \thesisabstract[english]{ -In this dissertation, we focus on the area coverage problem, energy-efficiency is also the foremost requirement. We have considered distributed optimization protocols with the ultimate objective of prolonging the network lifetime. To address this problem, this dissertation proposes two-step approaches. Firstly, the sensing field is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of our proposed distributed optimization protocols is distributed and applied on the sensor nodes in each subregion so as to optimize the coverage and the lifetime performances. Three coverage optimization protocols are proposed, They combine two efficient techniques: leader election for each subregion, followed by an optimization-based planning of sensor activity scheduling for each subregion. Extensive simulations are conducted using the discrete event simulator OMNeT++ to validate the efficiency of each of our proposed protocols. We refer to the characteristics of a Medusa II sensor for the energy consumption and the time computation. In comparison with two other existing methods, our protocols are able to increase the WSN lifetime and provide improved coverage performance. +In this dissertation, we focus on the area coverage problem, energy-efficiency is also the foremost requirement. We have considered distributed optimization protocols with the ultimate objective of prolonging the network lifetime. To address this problem, this dissertation proposes two-step approaches. Firstly, the sensing field is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of our proposed distributed optimization protocols is distributed and applied on the sensor nodes in each subregion so as to optimize the coverage and the lifetime performances. Three coverage optimization protocols are proposed. They combine two efficient techniques: leader election for each subregion, followed by an optimization-based scheduling of sensor activity for each subregion. This scheduling is carried by formulating and solving linear programs. For the first two protocols, undercoverage and overcoverage of a specified set of points are minimized. For the third protocol, the new proposed model is based on perimeter coverage level. Extensive simulations are conducted using the discrete event simulator OMNeT++ to validate the efficiency of each of our proposed protocols. We refer to the characteristics of a Medusa II sensor for the energy consumption and the time computation. In comparison with two other existing methods, our protocols are able to increase the WSN lifetime and provide improved coverage performance. } \thesiskeywords[english]{ Wireless Sensor Networks, Area Coverage, Network Lifetime, Distributed Optimization, Scheduling.} @@ -107,7 +107,7 @@ In this dissertation, we focus on the area coverage problem, energy-efficiency i %%-------------------- %% Set the French abstract \thesisabstract[french]{ -Dans cette thèse, nous nous sommes intéressé au problème de la zone de couverture ainsi qu'à l'efficacité énergétique qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudié des protocoles d'optimisation distribués avec l'objectif ultime de prolonger la durée de vie du réseau. Pour résoudre le problème, nous avons proposé de nouvelles approches en deux phases. 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. Ensuite, l'un de nos protocoles d'optimisation distribués est exécuté par chaque n\oe ud capteur 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 de décision via l'optimisation de l'ordonnancement d'activité des n\oe uds capteurs de sa sous-région. Nous avons effectué plusieurs simulations en utilisant le simulateur à évènements discrets OMNeT++ pour valider l'efficacité de nos protocoles proposés. 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. +Dans cette thèse, nous nous sommes intéressés au problème de couverture ainsi qu'à l'efficacité énergétique qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudié des protocoles d'optimisation distribués avec l'objectif de prolonger la durée de vie du réseau. Pour résoudre le problème, nous avons proposé de nouvelles approches articulées en deux phases. 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. Ensuite, l'un de nos protocoles d'optimisation distribués est exécuté par chaque n\oe ud capteur 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. Cet ordonnancement est porté par la formulation et la résolution de programmes linéaires. Pour les deux premiers protocoles, il s'agit de minimiser simultanément la non couverture ou la sous-couverture d'un ensemble de points particuliers. Pour le troisième protocole, le nouveau modèle propose repose sur la couverture du périmètre de chacun des capteurs. Nous avons effectué plusieurs simulations en utilisant le simulateur à évènements discrets OMNeT++ pour valider l'efficacité de nos protocoles proposés. 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. }