Construction of a Minimum Energy Broadcast Backbone with Bounded Delay in Heterogeneous Wireless Sensor Networks

Efficient broadcast in wireless sensor networks can exploit backbone structures, in relation to connected dominating sets in graphs. This paper proposes the construction of a backbone for broadcast in heterogeneous wireless sensor networks having minimum energy consumption and a delay bounded by a predefined constant h(max). For the purpose of the paper, we assume the sensors composing the network have an energy belonging to [W-min; W-max] such that W-max = c * W-min where c is a predefined constant. To address this problem we propose two different approaches. For small instances, we propose an integer linear program that computes an optimal solution for the problem. Since solving an integer linear program is NP-hard, obtaining solutions for large network instances may be impossible in a reasonable time, thus we propose an approximation algorithm that computes a solution for the problem in polynomial time and whose approximation ratio is c * h(max).