无线传感器网络的采样任务负载均衡与容错方法

摘要

本发明公开了一种基于无线传感器网络的采样任务分配方法，其特征在于，树形无线传感器网络中的根节点0接收到至少两个连续采样任务，获取所有连续采样任务的采样信息，采样信息包括每个连续采样任务t的开始时刻b、结束时刻e、采样时间长度l，其中，连续的采样任务是指持续采样一定时间且不能中断的采样任务；树形无线传感器网络中的根节点0将的每个连续采样任务t分配到k个不同的传感器上采集r次；所有传感器按照分配到的连续采样任务进行采样，并回传数据。

说明书

技术领域

本发明涉及通信技术领域，特别地，涉及一种基于数据共享的无线传感 器网络的采样任务负载均衡与容错方法。

背景技术

无线传感网络是由大量廉价微型的传感器节点通过无线通信的方式组成 的多跳自组织网络。这在地震、火山预警，铁轨故障检测，生态保护区环境 检测等领域得到了普遍的应用。将传感器按照一定的方式部署在美国金门大 桥上，传感器可以感知因为地震而产生的震动，通过分析采集到的震动数据 有助于对地震探测和震后救灾工作提供快速的信息支持；利用部署在铁轨上 的传感器采集铁轨震动的声波，通过分析声波的特点有助于检测铁轨是否出 现故障等意外情况，有助于铁轨维护，避免因此导致的事故；这些应用具有 共同的特点，即：因为金门大桥下、火山口、铁轨都是人迹罕至的地方，无 线传感网络按照一定的方式部署后很难进行调整，而且系统应该具有高可用 性，在完成监测任务的情况下，保持较长时间的工作状态。这几乎是每个无 线传感器网络共有的特点，除此之外这些采样的任务和传统的离散方式的点 采样不同，它们是一种连续的区间采样。传统的点采样仅仅需要传感器采集 一次数据就完成了任务，但是像利用声波检测铁轨故障的应用，需要根据一 段时间内分析采集的声波才能得出结论，仅仅在某一时刻采集一次数据没有 意义。因此传统在点采样上取得的研究成果并不能简单的应用到这些实际的 应用中。

如果有采样任务分配到传感器上，传感器就可以根据需求立即开始采样。 但是当有多个采样任务在一定的时间内都分配到传感器上时，传感器如果仍 然是按照“先到先服务”(First In First Service，简称为FIFS)的策略逐 一开始采样，那需要采样的任务量就是这些采样任务的简单相加。而实际中 这些采样任务存在时间重叠区，即：在某一时间段，多个采样任务都需要采 集数据，这段内采集的数据可以被多个任务共享。那么就有可能通过优化调 度的采样策略，让尽可能多的采样任务在重叠区采样。保证在完成采样任务 的前提下减少采样的任务量。通过减少采样的任务量可以节省传感器的能源， 提高传感器和整个无线传感网络的生命周期，同时采集的数据量减少也会缓 解网络传输的压力，避免因为网络拥塞引起的数据丢失和重传。

传统的点采样都是假设采样任务可以在某一时刻由传感器一次采样完成。 但实际上很多应用都会给每个采样任务分配一个时间窗口，在这个时间窗口 内完成采样任务而不是精确地限制在某一时刻完成。当多个采样任务分配到 一个传感器上时，某些采样任务的时间窗口很有可能出现重叠。而现有技术 并没有解决在重叠的时间区的采样任务之间存在数据共享时，优化采样的问 题。现有的采样方法缺乏有效的负载均衡和容错机制，树形多跳的无线传感 器网络缺乏效率、稳定性与鲁棒性。

针对现有技术中采样方法缺乏有效的负载均衡和容错机制，树形多跳的 无线传感器网络缺乏效率、稳定性与鲁棒性的问题，目前尚未有有效的解决 方案。

发明内容

针对现有技术中采样方法缺乏有效的负载均衡和容错机制，树形多跳的 无线传感器网络缺乏效率、稳定性与鲁棒性的问题，本发明的目的在于提出 一种基于数据共享的无线传感器网络的采样任务负载均衡与容错方法，能够 为采样方法有效的负载均衡和容错机制，提高树形多跳的无线传感器网络的 效率、稳定性与鲁棒性。

基于上述目的，本发明提供的技术方案如下：

根据本发明的一个方面，提供了一种基于数据共享的无线传感器网络的 采样任务负载均衡与容错方法，包括：

树形无线传感器网络中的根节点0接收到至少两个连续采样任务，获取 所有连续采样任务的采样信息，采样信息包括每个连续采样任务t的开始时 刻b、结束时刻e、采样时间长度l，其中，连续的采样任务是指持续采样一 定时间且不能中断的采样任务；树形无线传感器网络中的根节点0将的每个 连续采样任务t分配到k个不同的传感器上采集r次；所有传感器按照分配 到的连续采样任务进行采样，并回传数据。

其中，树形无线传感器网络中的根节点0将的每个连续采样任务t分配 到k个不同的传感器上采集r次，包括：树形无线传感器网络中的根节点0 将的每个连续采样任务t按结束时刻e由小到大排序并构建队列，依次指定 队列中的所有采样任务；树形无线传感器网络中的根节点0将指定的采样任 务t，检索其他与此采样任务t包含重叠部分的采样任务；树形无线传感器 网络中的根节点0计算采样任务t与此采样任务t包含重叠部分的采样任务 之间的重叠值，重叠值是指不同采样任务之间因为时间窗口有重叠可以共享 的最大的时间范围，重叠值中的不同采样任务的数量为两个以上；树形无线 传感器网络中的根节点0根据比较所有连续采样任务之间的重叠值的大小对 所有采样任务进行处理，其中，包含采样任务t且重叠值最大的多个采样任 务被从队列中移除；树形无线传感器网络中的根节点0根据贪心策略，采样 任务t与此采样任务t包含重叠部分的采样任务之间的最大重叠值，计算出 完成重叠值最大的多个采样任务将花费的采样时间I；传感器节点将重叠值 最大的多个采样任务的采样时间I平均分配到与采样任务所在探测范围有重 叠的多个从属于根节点0的k个叶节点0_j上r次，其中，对任意一属于根节 点0的叶节点0_j，若在某一次分配中获得了某段采样时间I_j，那么在后续分 配中根节点0不会将采样时间I_j再次分配到该叶节点0_j上，其中，0≤j≤k- 1；从属于根节点0的叶节点0_j对按照根节点0的采样时间要求，将被分配 到的采样时间平均分配到从属于叶节点0_j的所有传感器；当队伍中没有未处 理的采样任务剩余时，采样完成。

其中，树形无线传感器网络中的根节点0将每个连续采样任务t分配到 k个不同的传感器上采集r次，包括：对任意一属于根节点0的叶节点0_j， 在某一次分配中获得了某段采样时间I_j，令I_j所在区间为ST_j，则叶节点0_j上所有采样任务占用时间的总集为ST_total，其中，0≤j≤k-1；树形无线传感 器网络中的根节点0将的每个连续采样任务t按结束时刻e由小到大排序并 构建队列，依次指定队列中的所有采样任务；对于新到来的指定的采样任务 t，根节点0按照贪心策略将采样任务t分割为k个子任务t_i，其中，0≤i≤ k-1；将所有k个子任务t_i分配到k个叶节点0_j上r次；更新每个叶节点0_j的采样时间区间ST_total为旧采样时间区间与新分配的子任务t_i所占的时间区间 的并集；当队伍中没有未处理的采样任务剩余时，采样完成。

并且，根节点0按照贪心策略将采样任务t分割为k个子任务t_i包括： 传感器节点依次计算所有连续采样任务之间的重叠值，重叠值是指不同采样 任务之间因为时间窗口有重叠可以共享的最大的时间范围，重叠值中的不同 采样任务的数量为两个以上；传感器节点根据比较所有连续采样任务之间的 重叠值的大小对所有采样任务进行分组，其中，重叠值最大的多个采样任务 被分入同一个任务组，最终形成的任务分组数量不超过k个。

并且，传感器节点根据比较所有连续采样任务之间的重叠值的大小对所 有采样任务进行分组包括：获取所有连续采样任务的采样信息，采样信息包 括重叠区中出现的任务可以被检测到的传感器节点总数量k、重叠区出现的 采样任务集合S＝{t₁,t₂,...,t_n}；为采样任务集合绘制能示出所有连续采样任务与 其间关系的模型图G，其中，模型图G中每个连续采样任务以一个点表示， 每两个连续采样任务之间的重叠值以两点之间的线段边表示，每条边均有权， 权的值等于两端点所对应的两个连续采样任务之间的重叠值；比较模型图G 中的所有边的权，移除权最小的一条边；重复上一个移除模型图G中的边， 直到模型图G被分割为k个互不相连的子图为止，k个互不相连的子图中的顶 点的集合即为各传感器节点的采样任务集合。

并且，传感器节点将不同的连续采样任务以任务分组为单位，将所有任 务分组随机分配到与采样任务所在探测范围有重叠的多个传感器节点上。

另外，传感器节点将不同的连续采样任务以任务分组为单位，依照负载 均衡的原则，将所有任务按照不同传感器节点剩余的采样能力大小，均衡地 分配到与采样任务所在探测范围有重叠的多个传感器节点上。

在一个较佳实施例中，模型图G的绘制与切割包括：输入表示任务集合 的模型图G，和需要划分的子图个数k；将每个顶点按照相邻边的权重之和， 由大到小排序；选取第一个顶点作为初始顶点，标记为u，按顺序地从后面 的顶点中选取与u不直接相邻，但是具有公共顶点的顶点，标记为v，它们的 公共顶点构成的集合标记为S_u；从S_u中依次选取相邻边之和最小的顶点，标 记为w，分别计算w与u和v划分在一个子集中为系统带来的重叠值之O(u,w) 和O(v,w)；若O(u,w)>O(v,w)则去除G中v与w相连的边，更新模型图G为G’， 否则去除G中u与w相连的边，更新模型图G为G’；若G’被分为了k个子 图则返回G’；否则继续分割(G’,k)输出划分之后的k个子图。

从上面所述可以看出，本发明提供的技术方案通过依次检索所有采样任 务，并在根结点与叶节点上分别对采样任务按重叠值进行合并与含有冗余地 将采样任务分割给不同传感器的技术方案，为采样方法提供了有效的负载均 衡和容错机制，提高了树形多跳的无线传感器网络的效率、稳定性与鲁棒性。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实 施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅 仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性 劳动的前提下，还可以根据这些附图获得其他的附图。

图1为根据本发明实施例的一种基于数据共享的无线传感器网络的采样 任务负载均衡与容错方法流程图；

图2为现有技术中无优化策略按时离散点采样的采样时间轴示意图；

图3为现有技术中使用优化策略按时离散点采样的采样时间轴示意图；

图4为现有技术中无优化策略按时连续区间采样的采样时间轴示意图；

图5为根据本发明实施例的优化策略按时连续区间采样的采样时间轴示 意图；

图6为根据本发明实施例的一种基于数据共享的无线传感器网络的采样 任务负载均衡与容错方法中，同一时间段内多个采集任务根据重叠值绘制出 的模型图G；

图7为根据本发明实施例的一种基于数据共享的无线传感器网络的采样 任务负载均衡与容错方法中，针对三个连续的采样任务进行优化的采样时间 轴示意图；

图8为根据本发明实施例的一种基于数据共享的无线传感器网络的采样 任务负载均衡与容错方法中，表示三个连续的采样任务之间关系的模型图G；

图9为根据本发明实施例的一种基于数据共享的无线传感器网络的采样 任务负载均衡与容错方法中，一个3覆盖3冗余的1跳树形网络结构图；

图10为根据本发明实施例的一种基于数据共享的无线传感器网络的采样 任务负载均衡与容错方法中，一个3覆盖3冗余的2跳树形网络结构图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，下面将结合本发明 实施例中的附图，对本发明实施例中的技术方案进一步进行清楚、完整、详 细地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部 的实施例。基于本发明中的实施例，本领域普通技术人员所获得的所有其他 实施例，都属于本发明保护的范围。

无线传感器网络部署完成后很难人工地调整位置或更换部件。现有技术 多从节约能源，提高网络的生命周期和数据传输的可靠性等角度出发，取得 了很多成果。然而，从数据层面出发，通过优化采样任务量的角度达到提高 系统生命周期和稳定传输的技术还没有有效的方法，尤其是当采样任务可以 被多个传感器探测到时，优化采样任务的调度策略，利用任务之间的数据共 享压缩采样时间，并考虑传感器的实际负载情况，实现负载均衡的调度策略 在现有技术中还是空白。

对于离散点采样任务，存在一个完成的时间窗口，完成一次采样任务就 要求在这个任务的时间窗口内采集一次数据，这是带有时间限度的离散点采 样问题。如图2与图3所示，如果存在两个离散点采样任务，且它们的完成 时间窗口在时间轴上重叠，如果不进行策略优化，在采样任务到达时候就立 即开始采样，则如图2所示，无线传感器需要进行两次采样。而使用优化过 的贪心算法允许无线传感器在它们的时间重叠区采样一次，如图3所示的采 集的数据可以同时被两个任务共享，从而减少了采样的任务量。

对于连续区间的采样任务，存在一个完成的时间窗口，完成一次采样任 务就要求在这个任务的时间窗口内连续采集一定时间区间的数据。如图4与 图5所示，如果存在两个连续区间采样任务，且它们的完成时间窗口在时间 轴上重叠，如果不进行策略优化，在采样任务到达时候就立即开始采样，则 如图4所示，无线传感器需要采样的时间长度l＝l₁+l₂。而使用优化过的贪心 算法允许无线传感器在它们的时间重叠区。如图5所示，l＜l₁+l₂。因此，采 集的数据可以同时被两个任务共享，从而减少了采样时间。

对于连续采样任务，假设不同的采样任务的时间窗口没有重叠。如果重 叠区域可以被k个传感器探测到，不妨将第i个采样任务表示为t_i，每个任务 需要的采样时间长度为l_i，那么对于任务的集合S＝{t₁,t₂,...,t_n}，实际问题等价 于是否存在S的k个不相交的子集S_j(j＝1,2,…,k)使得 k子集划分问题具有NP完全的时间复杂度，其时间复杂 度不能完全以多项式形式写出，必定包含指数形式项，故多个任务上的采样 量的优化问题是NP完全问题，多项式时间内不能得出优化问题的最优解。

除此之外，在实际传感器网络中，对于连续任务集合S_j，每个任务的时 间窗口是个时间区间，在不同的任务之间寻求最少的采样时间使得而这个求解l的过程也是NP完全问题。因此实际中寻找一个既能最大程度的 利用任务之间的数据共享减少数据采样量，又能保持负载均衡的解决方案几 乎是不可能的。本发明重点从提高任务之间的数据共享，尽可能的减少数据 的采样量的角度出发，提出有效的分配方案。因为如果我们得到了分配方案， 即使不同方案需要的采样量不同，通过调整传感器执行采样方案的策略也可 以达到在较长时间内负载均衡的目的。

根据本发明的实施例，提供了一种基于数据共享的无线传感器网络的采 样任务调度方法。

如图1所示，根据本发明的实施例的提供了一种基于数据共享的无线传 感器网络的采样任务负载均衡与容错方法包括：

步骤S101，树形无线传感器网络中的根节点0接收到至少两个连续采样 任务，获取所有连续采样任务的采样信息，采样信息包括每个连续采样任务 t的开始时刻b、结束时刻e、采样时间长度l，其中，连续的采样任务是指 持续采样一定时间且不能中断的采样任务。

步骤S103，树形无线传感器网络中的根节点0将的每个连续采样任务t 分配到k个不同的传感器上采集r次。

步骤S105，所有传感器按照分配到的连续采样任务进行采样，并回传数 据。

我们首先定义k覆盖r冗余的树形网络模型。一个k覆盖网络是指每个 网络区域均可被k个传感器探测到。图9示出的是一个3覆盖3冗余的1跳 树形网络，其中，圆圈代表节点或传感器，大圆范围代表网络区域，大圆区 域内的多个时间轴代表网络区域内的多个采样任务。如图9所示，1跳树形 网络不设置叶节点，根节点0直接连接至三个传感器00、01、02。在如图9 所示的3覆盖3冗余1跳树形网络中，每个采样任务t均被三个传感器00、 01、02采集3次，三个传感器00、01、02将采集到的数据上传到根节点0。 这种采集方式可以在网络中某些节点出错的情况下，依然确保采样任务顺利 完成。比如传感器00出现故障时，若没有进行冗余数据采集，传感器00采 集的数据会丢失造成数据损失；而3冗余模型下，每个传感器都能独立完成 全部需要采集的数据，传感器00出现故障时，只要传感器01、02正常工作， 则数据安全不受影响。

图9示出的3覆盖3冗余的1跳树形网络，本质上是更大树形网络的一 个基本工作单元，包含了节点与传感器。在更大的树形网络中，譬如图10所 示的3覆盖3冗余的2跳树形网络中，可以认为3覆盖3冗余的2跳树形网 络是由3个3覆盖3冗余的1跳树形网络组成的复合网络。其中，根节点0 与两个叶节点00、01为一个基本工作单元，叶节点00与三个传感器000、 001、002为一个基本工作单元，，叶节点01与三个传感器010、011、012为 一个基本工作单元，所有基本工作单元的工作模式本质上均与图9示出的3 覆盖3冗余的1跳树形网络的工作模式相同，其中，两个叶节点00、01起到 了在2跳树形网络中承上启下的作用。

对于多跳树形网络，根节点0将的每个连续采样任务t分配到k个不同 的传感器上采集r次的分配方式需要实现两次：在根节点0上实现，与在叶 节点0_j上实现。

其中，在根节点0上的实现方法(被称为下沉算法)包括：

树形无线传感器网络中的根节点0将的每个连续采样任务t按结束时刻 e由小到大排序并构建队列，依次指定队列中的所有采样任务；

树形无线传感器网络中的根节点0将指定的采样任务t，检索其他与此 采样任务t包含重叠部分的采样任务；

树形无线传感器网络中的根节点0计算采样任务t与此采样任务t包含 重叠部分的采样任务之间的重叠值，重叠值是指不同采样任务之间因为时间 窗口有重叠可以共享的最大的时间范围，重叠值中的不同采样任务的数量为 两个以上；

树形无线传感器网络中的根节点0根据比较所有连续采样任务之间的重 叠值的大小对所有采样任务进行处理，其中，包含采样任务t且重叠值最大 的多个采样任务被从队列中移除；

树形无线传感器网络中的根节点0根据贪心策略，采样任务t与此采样 任务t包含重叠部分的采样任务之间的最大重叠值，计算出完成重叠值最大 的多个采样任务将花费的采样时间I；

传感器节点将重叠值最大的多个采样任务的采样时间I平均分配到与采 样任务所在探测范围有重叠的多个从属于根节点0的k个叶节点0_j上r次， 其中，对任意一属于根节点0的叶节点0_j，若在某一次分配中获得了某段采 样时间I_j，那么在后续分配中根节点0不会将采样时间I_j再次分配到该叶节 点0_j上，其中，0≤j≤k-1；

从属于根节点0的叶节点0_j对按照根节点0的采样时间要求，将被分配 到的采样时间平均分配到从属于叶节点0_j的所有传感器；

当队伍中没有未处理的采样任务剩余时，采样完成。

而在叶节点0上的实现方法(被称为叶算法)包括：

对任意一属于根节点0的叶节点0_j，在某一次分配中获得了某段采样时 间I_j，令I_j所在区间为ST_j，则叶节点0_j上所有采样任务占用时间的总集为 ST_total，其中，0≤j≤k-1；

树形无线传感器网络中的根节点0将的每个连续采样任务t按结束时刻 e由小到大排序并构建队列，依次指定队列中的所有采样任务；

对于新到来的指定的采样任务t，根节点0按照贪心策略将采样任务t 分割为k个子任务t_i，其中，0≤i≤k-1；

将所有k个子任务t_i分配到k个叶节点0_j上r次；

更新每个叶节点0_j的采样时间区间ST_total为旧采样时间区间与新分配的子 任务t_i所占的时间区间的并集；

当队伍中没有未处理的采样任务剩余时，采样完成。

其中，根节点0按照贪心策略将采样任务t分割为k个子任务t_i包括： 传感器节点依次计算一个或多个采样任务t之间的重叠值，重叠值是指不同 采样任务之间因为时间窗口有重叠可以共享的最大的时间范围，重叠值中的 不同采样任务的数量为两个以上；传感器节点根据比较所有连续采样任务之 间的重叠值的大小对所有采样任务进行分组，其中，重叠值最大的多个采样 任务被分入同一个任务组，最终形成的任务分组数量不超过k个。

其中，传感器节点根据比较所有连续采样任务之间的重叠值的大小对所 有采样任务进行分组包括：

获取所有连续采样任务的采样信息，采样信息包括重叠区中出现的任务 可以被检测到的传感器节点总数量k、重叠区出现的采样任务集合 S＝{t₁,t₂,...,t_n}；

为采样任务集合绘制能示出所有连续采样任务与其间关系的模型图G， 其中，模型图G中每个连续采样任务以一个点表示，每两个连续采样任务之 间的重叠值以两点之间的线段边表示，每条边均有权，权的值等于两端点所 对应的两个连续采样任务之间的重叠值；

比较模型图G中的所有边的权，移除权最小的一条边；

重复上一个移除模型图G中的边，直到模型图G被分割为k个互不相连的 子图为止，k个互不相连的子图中的顶点的集合即为各传感器节点的采样任 务集合。

并且，传感器节点将不同的连续采样任务以任务分组为单位，将所有任 务分组随机分配到与采样任务所在探测范围有重叠的多个传感器节点上。

并且，传感器节点将不同的连续采样任务以任务分组为单位，依照负载 均衡的原则，将所有任务按照不同传感器节点剩余的采样能力大小，均衡地 分配到与采样任务所在探测范围有重叠的多个传感器节点上。

上述内容已经阐明，多个任务的完成时间窗口出现重叠，就可以提高任 务之间的数据共享从而减少采样时间。

兹定义：重叠值是指不同连续采样任务之间因为完成时间窗口有重叠可 以共享的最大时间范围。

一个采样任务可以用开始时刻b，结束时刻e，和采样的时间长度为l等 属性来表示。如图4与图5所示，采样任务t_i和t_j的完成时间窗口相互重叠， 它们的采样时间长度为分别为l_i和l_j，则它们的重叠值为 O(t_i,t_j)＝min{l_i,l_j,|e_i-b_j|}。而如果有三个采样任务t_i，t_j和t_k的完成时间窗口出 现了重叠，O(t_i,t_j,t_k)＝min{l_i,l_j,l_k,|e_i-b_j|,|e_i-b_k|,|e_j-b_k|}。当有更多的采样任务出现重 叠时，依次类推。

重叠值可以度量不同采样任务之间可以共享的数据量，利用不同采样任 务之间的重叠值可以为任务集合的划分提供有效的依据。如图7与图8所示 的t₁,t₂和t₃三个任务，其中O(t₂,t₃)大于O(t₁,t₂)，因此可以将任务集合 S＝{t₁,t₂,t₃}，划分为两个子集S₁＝{t₁}和S₂＝{t₂,t₃}，这样可以使得系统所需的采 样量最小，同时结合无线传感器的能量等因素，将S₁和S₂分配到不同的节点 上，可以在保持系统采样量最少的情况下，保持负载均衡。

假设在一个时间段内的所有采样任务都是已知的。当多个任务分配到传 感器上时，S＝{t₁,t₂,...,t_n}表示在重叠区出现的采样任务集合。k表示重叠区中 出现的任务可以被检测到的传感器的数量。因此实际问题转化为如何将S分 解为它的k个不相交的真子集S₁,...,S_k，每个真子集S_i需要采样时间为l_i(l_i≥0)， 同时使得完成所有的任务所需要的采样时间最小。

为了更好地理解任务的调度方法，我们将任务集合看作一张图，其中每 个任务有一个顶点表示，任务之间如果存在重叠就连一条边，边的权重就是 它们之间重叠值。如图6所示，如果在无线传感器网络中重叠的区域产生了 5个采样任务。顶点u,v,w…分别表示这5个任务，如果任务的完成时间窗口 存在重叠那么就在相应的顶点之间连一条边，而且边上的权重是它们之间的 重叠值。这样就得到了类似图8所示的任务集合以及任务之间关系的模型图 G。

我们提出了一个贪心策略，根据不断的去除模型图G的边，最终使得模 型图G分裂为k个子图而且满足总采样量最小的要求。贪心策略的每一步都 寻求使得任务集合中不同的任务之间的“重叠值”之和最大，从而将任务的 集合S划分为k个不相交的子集S₁,...,S_k。具体表现到模型图G上就是通过“去 边”的操作，使得每次去掉的边都使得任务的重叠值之和变得更大，直到模 型图G被分为k个子图。贪心策略的有效性是不断地分析那些与多个其他任 务都有重叠值的“中间任务”，它们因为和多个任务的时间完成窗口出现重叠， 和不同的任务划分到一个任务子集中，就会产生不同的重叠值。不断地将重 叠值比较大的任务划分到一个集合，直到出现k个不相交的子集为止。例如， 当有多个采样任务时，如图8所示，如果k＝2，显然将t₂和t₃一起构成集合S₂， t₁单独构成集合S₁，会使整个任务集合S的重叠值之和变得最大，从而也使得 任务之间的数据共享最大，完成所有任务的采样时间最小。不断地在任务集 合中寻找这样特征的任务，每次筛选都将任务之间重叠值较小的一对任务划 分开来，这表现到模型图G上就是去除它们之间的边，一般这个边是表示中 间任务的顶点与其他顶点的相邻边中重叠值最小的一个。

具体过程如下述算法所示。

算法一为Part(G,k)方法，需要输入表示任务集合的模型图G，和需要划 分的子图个数k，该方法包括：

步骤S801，将每个顶点按照相邻边的权重之和，由大到小排序；

步骤S803，按顺序地选取具有公共顶点的两个顶点u和v作为初始顶点， 将公共顶点的集合，标记为S_u；

步骤S805，从S_u中依次选取相邻边之和最小的顶点，标记为w，分别计 算w与u和v划分在一个子集中为系统带来的重叠值之和O(u,w)和O(v,w)；

步骤S807，若O(u,w)大于O(v,w)则去除G中v与w相连的边，更新模型图 G为G’，否则去除G中u与w相连的边，更新模型图G为G’；

步骤S809，若模型图G’被分为了k个子图返回模型图G’；否则执行 Part(G’,k)方法继续拆分。

这种方法通过去除重叠值较小的边，不断地使得系统的重叠值变大的任 务划分为一个集合，最终使得任务集合在满足任务之间数据共享最大的前提 下，划分为k个不相交的子集。

综上所述，借助于本发明的上述技术方案，通过依次检索所有采样任务， 并在根结点与叶节点上分别对采样任务按重叠值进行合并与含有冗余地将采 样任务分割给不同传感器的技术方案，为采样方法提供了有效的负载均衡和 容错机制，提高了树形多跳的无线传感器网络的效率、稳定性与鲁棒性。

所属领域的普通技术人员应当理解：以上所述仅为本发明的具体实施例 而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修 改、等同替换、改进等，均应包含在本发明的保护范围之内。