4. Modified BIP Algorithm with Delay Bound Constraints

The Broadcast Incremental Power (BIP) algorithm was introduced in 20, and its improved performance against other proposed heuristics was demonstrated computationally. Also, a Multicast Incremental Power (MIP) algorithm was developed in 20 by removing the unnecessary transmissions in a complete broadcast tree obtained by BIP. The BIP algorithm is a greedy construction algorithm. At each iteration, it considers all possible transmissions from the set of covered nodes to the set of uncovered nodes. The transmission with the minimum incremental cost is added to the partial broadcast tree until all nodes are covered. Note that if a node i is already transmitting to a node j, then its incremental power consumption to cover an additional node k is . We modify the BIP algorithm to incorporate delay bound constraints and compare its performance to that of the filtered beam search in Sect. 5.

In the modified BIP (ModBIP) algorithm for our problem, the initializations of the sets T, C, NC and the delay vector Q are identical to those in FBS, i.e., T = , C = {1}, NC = V \ {1} and Q = [ q ₁, q ₂, ..., q _N} = [0, -1, ..., -1]. At each iteration, we consider all transmissions i ? j so that i ? C, j ? NC and q _i + 1 ? l