Minimum-Energy Broadcast Tree Problem

• INSTANCE: Wireless ad-hoc network $M = (N,L)$ consisting of set of nodes $N$ , location function $L : N \rightarrow \mathbb{Z}_{+}^2$ , for each node $v_i \in N, k$ power levels $w_{i,1} \leq w_{i,2} \leq ... \leq w_{i,k}$ , a receiver sensitivity $\vartheta >0$ propagation function $\gamma\colon \mathbb{Z}^2\times \mathbb{Z}^2\to \mathbb{R}_+$

• SOLUTION: An arborescence $T=(N,E)$ , power assignment $p=(p_i)_{v_i\in N}$ with $p_i\in \{w_{i,1},\ldots , w_{i,k}\}$ for all $v_i\in N$ such that for each directed edge $e=(v_i,v_j)$ in $T$ , $p_i-\gamma (L(v_i),L(v_j))\geq\vartheta$

• COST FUNCTION: $\sum_{v_i\:\mbox{non-leaf in $T$}}p_i$

• OBJECTIVE: Minimize.

  within $O((k + 1)^{1/\epsilon} n^{3/\epsilon}$ , where $n=\vert N\vert$ is the number of nodes in the wireless network, $k$ is the number of power levels at each node, and $\epsilon$ is constant with $0 < \epsilon < 1$ [86].

• Hardness: NP-hard [86].

• Comment: When every node is equipped with the same type of battery, an approximation algorithm has a better performance ratio than that in the general case setting, and the algorithm takes $O(kn^2 \log n)$ time [86].