Efficient integer programming formulations for optimum sink location and routing in heterogeneous wireless sensor networks

Sensors spend most of their limited battery energy on communicating the collected environmental information to sinks. Therefore, the determination of the optimal sink locations and sensor-to-sink information flow routes becomes important for the survivability of sensor networks. In this work, we address these important design issues using an integrated approach and propose new mixed-integer linear programming models to determine the optimal sink locations and information flow paths between sensors and sinks when sensor locations are given. The first group of proposed models is energy-aware and tries to minimize total routing energy, whereas the second group is financially driven with the objective of minimizing total cost. We do not only report computational results providing information on the solution efficiency of the new formulations, and the accuracy of their linear programming relaxations, but also propose and test new heuristics and lower bounding approaches for the most efficient formulation.