朱晓建，沈军

(1.东南大学 计算机科学与工程学院，江苏 南京 211189；2.东南大学 计算机网络和信息集成教育部重点实验室, 江苏 南京 211189)

1 引言

无线ad hoc网络由一组无线设备组成，在不需要使用网络基础设施的情况下，可以实现快速临时组网，具有广泛的应用。在无线ad hoc网络中，节点使用电池提供能量，而电池的能量十分有限，一旦电池的能量耗尽，节点将不能继续工作，网络将不再连通。因此，在无线ad hoc网络中，节能是一个核心问题，针对越来越多的多播应用，如何构造最小能耗多播树是一个重要问题。

文献[1]指出在无线ad hoc网络中无论使用全向天线还是使用有向天线，构造最小能耗多播树问题是一个NP难解问题，因此需要设计有效的启发式算法以求得较好的近似最优解。文献[2]提出了在使用全向天线的情况下构造最小能耗广播树的BIP(broadcast incremental power)算法和构造最小能耗多播树的MIP(multicast incremental power)算法，MIP算法首先利用BIP算法构造一棵广播树，然后对该广播树进行修剪得到多播树，未考虑不同的中继节点选择对构造多播树的影响。文献[3]提出了在使用有向天线的情况下构造最小能耗广播树的D-BIP(directional BIP)算法和构造最小能耗多播树的D-MIP(directional MIP)算法，与MIP算法基于BIP算法类似，D-MIP算法是基于D-BIP算法的。文献[4]提出了一种优化最小能耗广播树的r-shrink算法，该算法首先基于其他算法构造一棵广播树，然后以降低树的总能耗为目标，对树的结构进行调整。文献[5]提出了一种构造最小能耗广播树的模拟退火算法，利用BIP算法构造初始解，求解质量显著优于BIP算法，但仅对中小规模网络的最小能耗广播树问题求解效果较好。……