A genetic algorithm based solution to the Minimum-Cost Bounded-Error Calibration Tree problem

Sensors in wireless sensor networks are required to be self-calibrated periodically during their prolonged deployment periods. In calibration planning, employing intelligent algorithms are essential to optimize both the efficiency and the accuracy of calibration. The Minimum-Cost Bounded-Error Calibration Tree (MBCT) problem is a spanning tree problem with two objectives, minimizing the spanning tree cost and bounding the maximum post-calibration skew. The decision version of the MBCT problem is proven to be NP-Complete. In this paper, the GAWES algorithm is presented as a novel genetic algorithm based solution to the optimization version of the MBCT problem. GAWES adopts extreme efficient solution generation within the genetic algorithm to improve the search quality. It is demonstrated through experimentation that GAWES is superior to the existing state of the art algorithm, both in energy efficiency and calibration accuracy.