在无线网络飞速发展的背景下,无线传感网成为了研究热点之一。其应用遍及国防军事、环境监测、城市管理、医疗保健、电子信息及工农业发展的方方面面。无线传感网主要由传感器构成。传感器具有体积小、能耗低的特点,且具备感应、计算、传输等功能。传感器的存在成功地将物理量转换为信息量,为各行各业的研究、控制提供了宝贵的数据。在结构上,无线传感网主要包含单层结构和双层结构。节点可直接向信宿节点传输数据,也可将数据汇聚到簇头节点,再转发到信宿端。由此产生具有不同目标与特点的路由算法。对无线传感网的研究中,Steiner树问题是主要的工具之一。Steiner树的研究范围十分广泛,其中的瓶颈Steiner树问题、最少Steiner点问题、调度问题、最小生成树问题等都是无线传感网重要的理论依据。本文主要研究无线传感网的修复算法。网络中传感器的损坏会将网络分成若干互不连通的分区。此时,对网络的修复可以从两个方面展开：1)节点移动自修复法：在人工不可及的区域中,通过节点自行移动修复网络的连通性。2)加入中继节点修复法：通过加入中继节点的方法修复网络连通性。在算法设计上,可以考虑网络覆盖率、连通性、鲁棒性和能量均衡等多个目标。节点移动修复算法要求网络在不可添加节点的情况下进行自行修复。该问题可以归纳为特殊的瓶颈Steiner树问题。本文以减少移动节点数与总移动距离为目标提出了改进的近似算法。算法引入了节点间的合作机制,根据节点度数、覆盖情况的不同采取不同的移动策略,把移动任务集中在无覆盖任务的一跳节点上,以此减少总移动距离。无线传感网也可通过加入中继节点的方法来修复网络的连通性。该问题可以归纳为最少Steiner点数问题,也称为SMT-MSP问题。本文以减少中继节点数并均衡节点能量为目标提出了改进的近似算法。在分区代表节点的选择上提出了新的模型,同时考虑节点位置与能耗。在中继节点位置的选择上,算法不仅借助最小生成树,Steiner树等经典方法,还添加了中继节点分担低能量传感节点传输任务的机制。此外,中继节点位置的选择考虑了相邻传感节点的能耗。以上策略均有助于进一步减少中继节点数,并均衡网络的能量消耗。最后,本文对下一步的工作进行了课题展望。