Mecanismes optimises de planification des etats des capteurs pour la maximisation de la duree de vie dans les reseaux de capteurs sans fil.

摘要

In our first paper entitled "On the planning of wireless sensor networks: energy efficient clustering under the joint routing and coverage constraint", and published in IEEE Transactions on Mobile Computing, we address the optimal planning of sensors' states in cluster-based sensor networks. In that paper, we consider that any sensor can be in one of three states: active (turned on), turned off or cluster head, and a different power consumption is associated with each of these states. Our objective is to find an energy-optimal topology that maximizes network lifetime while ensuring simultaneously full area coverage and a fully clustered configuration in which the set of cluster heads is constrained to form a spanning tree used as a routing topology. We first formulated this problem as an Integer Linear Programming model that we proved NP-Complete. Then, we implemented a Tabu search heuristic to tackle the exponentially-increasing computation time of the exact resolution. Experimental results show that the proposed heuristic provides near-optimal network lifetime values within low computation times, which in practice is suitable for large-sized sensor networks. Our heuristic also offers better performance than other recent distributed clustering algorithms proposed in the scientific literature. In the second paper entitled "Energy-efficient clustering with transmit power assignment under coverage constraint in wireless sensor networks", submitted to the Wireless Communications and Mobile Computing journal (Wiley), we address the problem of maximizing network lifetime in a WSN, under coverage and clustering constraints. We consider sensors equipped with multiple transmit powers and thus capable of reaching a wider set of cluster heads at higher energy costs, and we propose to find the optimal assignment of states and transmit powers to sensors. We first model this problem as an Integer Linear Programming (ILP) optimisation problem that we prove NP-complete. Then, we propose a Tabu search heuristic to find acceptable-quality solutions within realistic processing times. Our simulation-based results show that our proposed heuristic provides better solutions compared to the optimal solutions generated by CPLEX, i.e., it outperforms, in terms of network lifetime, HEED---the well-recognized distributed clustering algorithm proposed in the literature. In our third paper entitled "A distributed energy-efficient clustering protocol for wireless sensor networks", published in the Computers and Electrical Engineering journal (Elsevier), we propose a new distributed clustering algorithm for WSN, called EECF. The novelty of EECF resides in the relevance of the information gathered by each sensor from its neighbors. Each sensor makes its decision to promote itself cluster head based on score functions exchanged with its one-hop neighbors, which hold information on the ability of its neighbors to become cluster heads. Simulation results show that our algorithm generates better results, in terms of network lifetime, than other distributed algorithms proposed in the recent scientific literature.;The main contributions of this thesis are: (1) The modeling of the energy-optimal sensor state planning problem in WSN, under the joint coverage, clustering and routing constraint. The exact solutions of this optimization problem represent an upper bound on the network lifetime and can thus serve as a comparison basis for evaluating the performance of other distributed clustering algorithms addressing the same problem, under the same constraints. To the best of our knowledge, no prior work in the literature has proposed such a bound for the global optimal sensor state planning under the same general integrated coverage, routing and clustering constraints. (2) The modeling of the problem of optimal allocation of states and transmit powers to the sensors in a WSN, under joint coverage and clustering constraints. Solutions of this problem provide an upper bound on the network lifetime and can thus serve as a comparison reference to assess the performance of other distributed algorithms addressing the same problem. (3) The proposal of a novel distributed clustering algorithm for WSN, which outperforms, in terms of lifetime of the network, other popular distributed algorithms proposed in the recent scientific literature. Our algorithm is therefore an improvement of the state-of-the-art on distributed cluster formation algorithms for WSN. (Abstract shortened by UMI.)