Algorithm and Convergence of MST Problem for Energy Efficient Routing in Wireless Sensor Networks

摘要

The rapid development of the theory and application makes it imperative to find the best strategies to improve the energy efficiency of wireless sensor networks. In this paper, we address the following question: given a multi-to-one wireless sensor network in physical space, what is the optimal routing strategy to enable the energy-efficiency of the network with regard to a given mission and a certain amount of initial energy. We have focused on energy consumption involving data generation, data fusion and data transmission. We model the wireless sensor network as an undirected graph and put that energy efficient routing problem into a constrained optimization problem. In order to solve the optimal routing, we introduce the Ant Colony Optimization Algorithm, which is relatively easier than other algorithms to implement in a distributed environment because of its distributed computing and positive feedback features. Then we prove the convergence of the algorithm. Finally, in the simulation experiments, we show that the routes derived from out algorithm yield noticeably energy efficiency. Our optimization strategy can be applied to other distributed networks.