We consider source-initiated broadcast session traffic in an ad hoc wireless network operating under a hard constraint on the end-to-end delay between the source and any node in the network. We measure the delay to a given node in the number of hops data travels from the source to that node, and our objective in this paper is to construct an energy-efficient broadcast tree that has a maximum depth Δ, where Δ; represents the end-to-end hop constraint in the network. We characterize the optimal solution to a closely related problem in massively dense networks using a dynamic programming formulation. We prove that the optimal solution can be obtained by an algorithm of polynomial time complexity O(Δ²). The solution to the dynamic program indicates that there is a single optimal policy applicable to all massively dense networks. Elaborating on the insights provided by the structure of the problem in massively dense networks, we design an algorithm for finding a solution to the hop constrained minimum power broadcasting problem in general networks. By extensive simulations, we demonstrate that our proposed optimization-based algorithm generates broadcast trees within 20% of optimality for general dense networks.

The problem of generating the sequence of tests required to reach a diagnostic conclusion with minimum average cost, which is also known as a test-sequencing problem, is considered. The traditional test-sequencing problem is generalized here to include asymmetrical tests. In general, the next test to execute depends on the results of previous tests. Hence, the test-sequencing problem can naturally be formulated as an optimal binary AND/OR decision tree construction problem, whose solution is known to be NP-hard. Our approach is based on integrating concepts from one-step look-ahead heuristic algorithms and basic ideas of Huffman coding to construct an AND/OR decision tree bottom-up as opposed to heuristics proposed in the literature that construct the AND/OR trees top-down. The performance of the algorithm is demonstrated on numerous test cases, with various properties.