论文部分内容阅读
无线Mesh网络和无线传感器网络是两类特殊的无线自组织网络。无线Mesh网络主要应用于替代传统的用于连接最终用户的最后一英里线路，以降低接入用户的布线成本。无线传感器网络则主要应用于环境检测、目标跟踪、战场监视等目的。
在无线Mesh网络中，仍然需要一个由有线网络组成的骨干网络用以连接Internet和无线接入点，因此仍然需要特定形式的布线优化。本文将其抽象为特殊的数学模型，并给出了近似算法。在无线传感器网络中，较之普通的无线自组网节点的能量和计算能力更为有限，计算能力也相对较低，因此节能策略更为急迫。本文在充分考虑数据融合等需求后，提出了一种多播节能策略，并且给出了实现协议。
本文的主要内容与贡献有：
a)通过讨论用户节点的需求和无线连接层的约束，将优化无线Mesh网络中的骨干网络的问题抽象为准组Steiner树模型；证明了该问题是NP难的，并且给出了在最坏情况多项式算法的近似比下限。
b)根据不同的策略给出了三种不同的近似算法一基于普通Steiner树的改进算法，基于组最小生成树的改进算法以及基于重叠点的Steiner树的改进算法。并且通过模拟实验，证明了基于重叠点的Steiner树的改进算法具有最好的性能。
c)在综合考虑数据融合和实际应用的基础上，基于重叠点的Steiner树的改进算法，设计了一种在无线传感器网络中的多播骨干网络构造协议，分析了该协议所需要的包复杂度，并且给出了它的具体实现。