在无线传感器网络中,路由树往往用于数据收集。在不同的路由树中,每个节点发送和接收的数据量不同,所以不同路由树的性能也不同。由于传感器节点的能量受限,找到使整个网络存活时间最长的路由树是一个关键问题,然而最优路由树问题已经被证明是一个NP难问题。目前针对此问题的算法通常是启发式算法和近似算法,不能保证获得最优解,且此类算法的性能评估需要与最优解进行对比。尽管精确算法的时间复杂度是指数级的,但是不同精确算法的运行时间不同。本文以提高计算效率、降低运行时间为目标提出了两个精确算法。主要工作如下:(1)提出了利用计算机多核CPU的性能来加速已有精确算法的方法。已有的精确算法基于单个CPU进行计算,未充分利用多核资源。提出方法的核心思想是将原问题进行分解,得到多个独立的子问题,在多个CPU核心上运行,通过并行计算的思想达到加速精确算法运行的目的。(2)提出了一个基于分支定界的精确算法,包括一种新的定界方法和一种网络预处理机制。定界方法通过两次定界使上界逐渐优化,更加细粒度。网络预处理机制可以进一步缩减解集空间,减小问题规模。大量的仿真实验表明基于多核计算的方法可以有效加速已有的精确算法,提出的分支定界算法在运行时间和成功求解问题的数量上都有显著提升。