一种基于不等分簇传感器网络的数据融合收集方法

本发明涉及无线传感器网络数据收集速度及节能领域，尤其涉及一种在传感器网 络中的基于不等分簇的数据融合收集方法。

TDMA调度是一种应用得非常广泛且效率较高的MAC层协议。在以往对于调度算法 的研究中，多集中在缩短调度时间或者采用分布式方法实现这两个方面上。

多对一的调度以往研究中已经被解决了。在早期研究中，提出了一个集遗传算法 和粒子算法于一体的进化算法来提高搜索能力；提出了启发式算法，通过调度尽可能多 的独立部分来增加并行传输的能力。

Liqi Shi等人提出跨层优化策略，实现无线传感器网络中的高能量使用效率和低 延迟。他们率先推导出在每一个链接上最节能的流，基于对每条连接上流的计算，他们提出 了一个拥有最小帧长度的包含TDMA调度方法的算法协议。

但是数据的融合传输问题与一般TDMA调度不同，在融合传输过程中每个节点产生 且仅产生一个数据包，而节点的数据收集有一个主要特征：在数据收集阶段只接受数据；在 发送阶段，一旦发送数据，则此节点不再接收数据；而且不管接收到多少个数据包，经过聚 合后都成为一个数据包。一些针对无线网络提出的数据融合协议也同样适用于无线传感器 网络，其中大多数研究将这个问题分成二个部分：一是逻辑网结构，二是传输的调度构造 树。调度算法的共同目标是使用最少的时间片。

但是在前面的研究中，都是假设网络中节点的发射半径是固定的，但是很多实际 网络中，网络参数如节点的发射半径，簇半径都是可调节的，而这些参数对网络的延迟与能 量消耗具有重要的影响。基于以上考虑，Habib M等人提出了节点发送半径与延迟，能量消 耗关系的优化。

虽然Habib M等人不是采用的TDMA方法，其选择优化网络参数来使网络延迟与能 量得到优化的思想同样可以用到TDMA调度中。在本发明所提供的方法中，我们通过优化网 络结构从而在整体上使得网络延迟与网络寿命得到优化。我们首先经过理论分析，给出了 延迟最小的优化簇半径的选择，然后提出了一种不等簇半径的数据收集优化的网络结构， 并通过巧妙的安排节点的调度时隙，使得一个传感器节点只醒来一次，连续完成所有操作， 以减少节点的状态转换的能量消耗，提高网络寿命。通通过实验证明，也可以发现，本发明 所提供的方法在能量消耗、延迟以及时间调度间隔等方面也均优于当前已有的调度算法。

本发明的目的在于提供一种传感器网络中的基于不等分簇的数据融合收集方法， 以解决现有分簇网络协议中的网络延迟较大，能量使用效率不高等问题。

为解决上述问题，本发明提供了一种基于不等分簇传感器网络中的数据融合收集 方法，至少包括以下步骤：

首先对现有网络形成一种远离区域的簇半径大，而近区域的簇半径小的 分簇网络，计算出的不等簇半径序列，对网络优化的分簇结构进行计算。算法如下：

步骤1：初始化传感器网络；

设定传感器网络中不等簇半径集合ro为空集以及传感器网络的数据融合收集时 间To为无穷大，nh＝1；

步骤2：依据公式计算最优不等簇半径：

其中，θj表示第j-1层节点成为第j层簇头节点的个数；nh＝Δh为簇内节点个数，h 为簇的层数，rk为第k层簇的簇半径，dk表示第k层簇头节点的儿子节点的度，ρ为传感器网络 中的传感器密度。

最外两层的不等簇半径按公式确定：且r_set＝{r_h,r_h-1}；

步骤3：执行操作r_set＝r_set∪r_j,j＝j+1后，判断r_total<R是否成立，若成立则返回步骤2，直到不成立时，转入步骤4；

步骤4：计算当前不等簇半径对应的传感器网络数据融合时间，Tu＝nh+jd+d0；

步骤5：判断T_u<T_o是否成立，如果成立，则将当前的T_u赋值给T_o，当前的r_set赋值给r_o，令n_h＝n_h+1，判断，n_h是否大于若大于，则以当前计算值作为不等簇半径的计算结构，若不等于，则返回步骤2。

其次，根据已得出的不等簇半径序列对网络成簇，算法实现思想如下：

即：首先，我们根据不等簇的半径序列对整个网络进行分层，再逐层对其进行分簇。在每一层中，我们很容易到其中心线，对于这层中的每一个节点，计算其与此层一跳内的节点的能量剩余比率，然后根据其距离中心线的距离和能量剩余比率作为自己竞争簇头的权值。计算公式为：其中Dist_p表示p节点距离sink的距离，E_ratio表示其与周围一跳节点的剩余能量比率；α₁和α₂因素影响因子，根据环境设定；p以W_p作为自己竞争簇头的权值，W_p越小，p广播簇头消息的优先级越高

离中心线越近，剩余能量越高的节点，竞争簇头的优先级越高，即广播簇头消息的 时隙越早。一个节点在其广播时隙达到时，如果仍未收到任何节点发送来广播簇头消息，则 自己标识为簇头，以此层的半径作为传输半径广播自己的簇头消息。当一个节点的广播时 隙达到之前，收到其他节点发过来的簇头消息后，则应先取消自己的竞选簇头事件，然后选 择距离自己最近的一个簇头加入。

最后，本发明方法采取一种实践的方式来解决由于网络节点分布的不均匀性以及 分簇控制算法的复杂性而导致一些理想的数据融合收集调度算法在实际分簇网络中无法 得到应用的问题。本发明方法的调度算法分为如下几个阶段：

(1)不等簇半径成簇阶段。这一阶段的主要目标是运用权利 要求4中所述方法，得到成簇后的网络参数，如每个簇头的度每层簇头最大的簇内度的系列Δ＝{Δ₁,Δ₂,...Δ_h}。

(2)簇间度的重新调整与填充：

(A)簇间度的调整：由于每层簇头节点最大的度并不一定按照理想的情况而且一定按照一定的梯度出现。为满足数据收集时的能量消耗最小，需要每层簇之间刚好能够衔接起来，以达到理想的每个节点从睡眠状态转到工作状态后的发送完所有数据后，再转入睡眠状态，并且处于工作状态的时隙数尽量小。这就需要对成簇后的簇的度进行调度，以达到使节点调度时的能量消耗最小的目的。

例如假设不等分簇算法构造的簇的层次为8层，从内到外每层簇内节点最大的度分别是：41,37,36,37,30,28,15,12。簇间节点的度d都为4。显然，按目前这种簇头间度的系列无法很好的衔接。因为，在第3层簇内节点收集完成时，第4层反而还在进行簇内节点收集，而还需要等第5层簇头的数据传到第4层，再传送到第3层，因而第3层节点需要等待较长的时间，这就浪费了能量。如果把上面的簇头节点的度的序列改成49,45,41,37,33,29,25,21的序列，即通过对簇内节点的度增加虚拟度的方法使得新的系列刚好满足使得最内层的簇内度最小，簇间的度等差序列为d。那么簇与簇间就能够进行较好的无缝衔接了。为得到这样的序列，我们采取了称为“加前”与“提后”的方法。操作的方法是对类似于从内到外每层的组成的序列：41,37,36,37,30,28,15,12，进行如下二个步骤的操作：

①加前，即从序列的右边向左边扫描每层簇内度组成的序列，对每一个数进行如 下的检查与操作：如果当前的数减去紧邻自己右边的数小于层间的度d，则当前检查的数为 紧邻右边的数加上d＝4。对前面的例子，“加前”操作后的结果如下所示：

49,45,41,37,32,28,16,12//“加前”从右向左

②“提后”，即对“加前”的结果从左到右扫描，对每一个数进行如下检查与操作：如 果当前的数据减去紧邻自己右边的数的值大于层间的度d，则将紧邻自己右边的数据用当 前的数减去d来替换，操作后的结果如下所示：

49,45,41,37,33,29,25,21//“提后”从左向右

(B)补充虚拟的簇间度：

如果调整后簇内的度大于调度前的度，那么就需要补充虚拟的度来使同一层簇头节点的簇内度相等。设第i层簇头节点的集合ξ_i，调整后第i层簇头节点的簇内度为Δ_i，用表示第i层的簇头节点k，其簇内度为Δ_i,k。那么补充虚拟的节点的原则为：如果Δ_i,k<Δ_i，那么建立虚拟的节点个数为τ_i,k＝Δ_i-Δ_i,k。所有的簇拟节点到簇头节点距离为无穷小的距离ε，而且只产生一个链路不会对除了之外的任何节点产生干扰。而且为虚拟节点的边赋予最高的调度优先级，即只要有虚拟节点存在于簇内，那么首先调度虚拟节点。可见簇内数据收集实际是在所有虚拟节点调度完成后，才真正开始工作，从而使得簇内节点多的簇先进行簇内数据收集，簇内节点少的簇晚进行簇内数据收集，从使使得每一层簇的数据收集完的最迟时间都在调度后的簇内度的序列内完成，由于调整后的每一层簇间的时序相差刚好满足簇间的数据收集，从而达到每个节点一旦从睡眠转入工作状态后就一直工作，在优化的时间内完成所有数据收集，然后重新转为睡眠状态，从而最节省能量。

做的目的可以保证簇头节点虚拟节为每一个簇内节点(CM)赋权重值为二类，虚拟 节点权重值为1，实节点的权重值为2.

(3)调度。调度的思想是：在每一时隙t到来时，首先为每一个簇随机选择一个簇内 节点作为数据发送者，将所有数据发送者与其所在簇的簇头节点组成的边放入边的集合 Ψ。然后对集合Ψ进行冲突消除，直到集合Ψ中的每一条边都没有冲突干扰。这样将集合Ψ 中每一条边的CMs节点发送数据的时隙安排在t时隙。

(4)在调度的过程中，最外层簇的簇内数据首先完成。因此，还需要进行簇间数据的收集。我们采用了一种较为简单而有效的方法来解决这个问题。即：当某一个簇内的数据全部收集完成后，那么此簇的簇头节点w_j就寻在簇头的发送半径内的每一个内层簇头节点，将自己做为普通节点加入到每一个内层簇头节点w_k上，作为w_k的普通节点，并标记自己到内层簇头节点边的级别为最低级。这样，我们对节点有三种级别：虚拟节点，其优先级最高，设级别为1；普通的簇内真实节点，优先级次之，设其级别为2；外层已经进行完数据收集的簇头节点，加入紧邻的内层簇头作为普通节点，其优先级最低，设其优先级为3。

有益效果

(1)研究发现，网络层的分簇大小对数据融合调度算法起到关键性的作用。因而本 发明方法的第一个突出贡献是给出了使得数据融合调度延迟最小的簇半径，从而从网络层 面上使得数据融合调度延迟得到优化。

(2)提出了近区域簇半径大，而远区域簇半径小的不等簇的传感器网络 分簇算法。随后，给出在不等簇网络结构下的TDMA数据融合调度算法，进一步大幅度的缩短 网络延迟。合理的安排不等簇半径的大小的比例关系，达到在外层簇头节点需要向内层簇 头节点传送数据时，内层簇头节点的簇内数据聚合刚好完成，大幅度的减少数据聚合所需 的时隙数，提高了网络性能。

(3)减少节点状态转换次数以提高网络寿命。本发明所提供方法首先通过不等簇 半径的网络结构使节点在每轮数据收集中只进行1次状态转换成为了可能。发明所提供方 法中通过推迟簇头节点度较小簇的数据收集时间，巧妙实现对传感器节点的连续调用以减 少状态转换的次数，有效提高网络寿命。分析表明本发明所提供方法节点的平均状态转换 次数接近1，已经达到最优的结果，而以往研究中最好结果为2次状态转化。同时本发明方法 也经过大量的仿真模拟来验证其正确性。

(4)本发明所提供方法的延迟与网络寿命优化策略是基于不同网络模型而做出的 假设，贴近于实践操作，因而具有较好的实际指导意义。

构成本申请的一部分的附图用来提供对本发明的进一步理解，本发明的示意性实 施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：

图1是本发明优选实施例的基于不等簇传感器网络的数据融合收集方法的操作流 程示意图；

图2是本发明优选实施例的不等簇网络调度时隙情况表；

图3是本发明优选实施例的等簇结构和不等簇结构在数据收集中的能量消耗情况 对比折线图；

图4是本发明优选实施例的不同方法下数据聚合时间的对比；

以下结合附图对本发明的实施例进行详细说明，但是本发明可以由权利要求限定 和覆盖的多种不同方式实施。

参见图1，基于不等簇传感器网络的数据融合收集方法，至少包括以下步骤：

首先对现有网络形成一种远离区域的簇半径大，而近区域的簇半径小的 分簇网络，计算出的不等簇半径序列，对网络优化的分簇结构进行计算。算法如下：

步骤1：初始化传感器网络；

设定传感器网络中不等簇半径集合ro为空集以及传感器网络的数据融合收集时 间To为无穷大，nh＝1；

步骤2：依据公式计算最优不等簇半径：

其中，θj表示第j-1层节点成为第j层簇头节点的个数；nh＝Δh为簇内节点个数，h 为簇的层数，rk为第k层簇的簇半径，dk表示第k层簇头节点的儿子节点的度，ρ为传感器网络 中的传感器密度。

最外两层的不等簇半径按公式确定：且r_set＝{r_h,r_h-1}；

步骤3：执行操作r_set＝r_set∪r_j,j＝j+1后，判断r_total<R是否成立，若成立则返回步骤2，直到不成立时，转入步骤4；

步骤4：计算当前不等簇半径对应的传感器网络数据融合时间，Tu＝nh+jd+d0；

步骤5：判断T_u<T_o是否成立，如果成立，则将当前的T_u赋值给T_o，当前的r_set赋值给r_o，令n_h＝n_h+1，判断，n_h是否大于若大于，则以当前计算值作为不等簇半径的计算结构，若不等于，则返回步骤2。

其次，根据已得出的不等簇半径序列对网络成簇，算法实现思想如下：

即：首先，我们根据不等簇的半径序列对整个网络进行分层，再逐层对其进行分簇。在每一层中，我们很容易到其中心线，对于这层中的每一个节点，计算其与此层一跳内的节点的能量剩余比率，然后根据其距离中心线的距离和能量剩余比率作为自己竞争簇头的权值。计算公式为：其中Dist_p表示p节点距离sink的距离，E_ratio表示其与周围一跳节点的剩余能量比率；α₁和α₂因素影响因子，根据环境设定；p以W_p作为自己竞争簇头的权值，W_p越小，p广播簇头消息的优先级越高。离中心线越近，剩余能量越高的节点，竞争簇头的优先级越高，即广播簇头消息的时隙越早。一个节点在其广播时隙达到时，如果仍未收到任何节点发送来广播簇头消息，则自己标识为簇头，以此层的半径作为传输半径广播自己的簇头消息。当一个节点的广播时隙达到之前，收到其他节点发过来的簇头消息后，则应先取消自己的竞选簇头事件，然后选择距离自己最近的一个簇头加入。

最后，本发明方法采取一种实践的方式来解决由于网络节点分布的不均匀性以及 分簇控制算法的复杂性而导致一些理想的数据融合收集调度算法在实际分簇网络中无法 得到应用的问题。本发明方法的调度算法分为如下几个阶段：

(1)不等簇半径成簇阶段。这一阶段的主要目标是运用权利 要求4中所述方法，得到成簇后的网络参数，如每个簇头的度每层簇头最大的簇内度的系列Δ＝{Δ₁,Δ₂,...Δ_h}。

(2)簇间度的重新调整与填充：

(A)簇间度的调整：由于每层簇头节点最大的度并不一定按照理想的情况而且一定按照一定的梯度出现。为满足数据收集时的能量消耗最小，需要每层簇之间刚好能够衔接起来，以达到理想的每个节点从睡眠状态转到工作状态后的发送完所有数据后，再转入睡眠状态，并且处于工作状态的时隙数尽量小。这就需要对成簇后的簇的度进行调度，以达到使节点调度时的能量消耗最小的目的。

①加前，即从序列的右边向左边扫描每层簇内度组成的序列，对每一个数进行如 下的检查与操作：如果当前的数减去紧邻自己右边的数小于层间的度d，则当前检查的数为 紧邻右边的数加上d＝4。

②“提后”，即对“加前”的结果从左到右扫描，对每一个数进行如下检查与操作：如 果当前的数据减去紧邻自己右边的数的值大于层间的度d，则将紧邻自己右边的数据用当 前的数减去d来替换；

(B)补充虚拟的簇间度：

如果调整后簇内的度大于调度前的度，那么就需要补充虚拟的度来使同一层簇头节点的簇内度相等。设第i层簇头节点的集合ξ_i，调整后第i层簇头节点的簇内度为Δ_i，用表示第i层的簇头节点k，其簇内度为Δ_i,k。那么补充虚拟的节点的原则为：如果Δ_i,k<Δ_i，那么建立虚拟的节点个数为τ_i,k＝Δ_i-Δ_i,k。所有的簇拟节点到簇头节点距离为无穷小的距离ε，而且只产生一个链路不会对除了之外的任何节点产生干扰。而且为虚拟节点的边赋予最高的调度优先级，即只要有虚拟节点存在于簇内，那么首先调度虚拟节点。可见簇内数据收集实际是在所有虚拟节点调度完成后，才真正开始工作，从而使得簇内节点多的簇先进行簇内数据收集，簇内节点少的簇晚进行簇内数据收集，从使使得每一层簇的数据收集完的最迟时间都在调度后的簇内度的序列内完成，由于调整后的每一层簇间的时序相差刚好满足簇间的数据收集，从而达到每个节点一旦从睡眠转入工作状态后就一直工作，在优化的时间内完成所有数据收集，然后重新转为睡眠状态，从而最节省能量。

做的目的可以保证簇头节点虚拟节为每一个簇内节点(CM)赋权重值为二类，虚拟 节点权重值为1，实节点的权重值为2.

(3)调度。调度的思想是：在每一时隙t到来时，首先为每一个簇随机选择一个簇内 节点作为数据发送者，将所有数据发送者与其所在簇的簇头节点组成的边放入边的集合 Ψ。然后对集合Ψ进行冲突消除，直到集合Ψ中的每一条边都没有冲突干扰。这样将集合Ψ 中每一条边的CMs节点发送数据的时隙安排在t时隙。

(4)在调度的过程中，最外层簇的簇内数据首先完成。因此，还需要进行簇间数据的收集。我们采用了一种较为简单而有效的方法来解决这个问题。即：当某一个簇内的数据全部收集完成后，那么此簇的簇头节点w_j就寻在簇头的发送半径内的每一个内层簇头节点，将自己做为普通节点加入到每一个内层簇头节点w_k上，作为w_k的普通节点，并标记自己到内层簇头节点边的级别为最低级。这样，我们对节点有三种级别：虚拟节点，其优先级最高，设级别为1；普通的簇内真实节点，优先级次之，设其级别为2；外层已经进行完数据收集的簇头节点，加入紧邻的内层簇头作为普通节点，其优先级最低，设其优先级为3。

图2为本发明优选实施例的不等簇网络调度时隙情况表；从表中可以看出，本发明 方法的不等簇网络结构下的融合传输调度有如下特征：(A)节点的状态转换仅需要1次。本 发明所提出的不等分簇结构和调度算法，保证了每一层簇间数据发送的连续性，节点一旦 工作，则一直工作到所有数据收集完成。(B)能量消耗最小化。即使是同一层的簇头节点其 开始工作时隙并不相同，但结束工作的时隙则基本一致。这是因为在调度时，要尽量推迟节 点唤醒的时间，以减少节点苏醒状态的时间，从而节省能量消耗。所以，我们在每一层中增 加了虚拟调度的边，先调度虚拟的边，从而推迟节点开始工作的时隙以节点不必要有苏醒 状态的能量消耗。(C)聚合传输所需时间少。表中的最内层簇头节点最大的“结束工作的时 间”就是整个网络聚合传输调度所需要的时间。与等簇方式相对比，本发明所提供策略的数 据聚合收集时间大幅缩短。

图3为等簇结构和不等簇结构在数据收集中的能量消耗情况对比折线图。(a)展示 了在网络规模R＝520m，节点数目N从2000到3000变化的情况下，两种不同结构的网络中执 行数据聚合传输所需的能耗对比情况。从图中可以看到，随着网络节点个数的增长，网络的 总能量消耗也随之增长。但最重要的是，在各种节点数目下，采用本发明方法的优化不等簇 结构进行数据收集的能量消耗均明显低于等簇结构。(b)展现了网络节点数目N＝2500，网 络规模R从450到650变化的情况下，两种不同结构进行数据聚合传输的能耗对比。图中3条 曲线均保持平稳的小波动趋势，验证了网络能耗与网络规模R无关的结论。同时，在不同的 网络规模下，本发明方法的不等簇结构所需要的能耗明显优于等簇结构下的能量消耗。从 这两个统计图中，我们可知，无论等簇结构采用何种能耗计算方式，本发明方法所提供的方 案依然能优化能量消耗达到15％以上。

图4为不同方法下数据聚合时间的对比。(a)中可以看到网络规模R＝520m，节点数 目N从2000到3000变化的情况下，两种不同结构的网络中执行数据聚合传输所需的时间对 比情况。图中的曲线上扬趋势体现了网络聚合传输所需要的时间和节点的数目成正比关 系。图中另一个重要的信息是，即使节点数目变化，采用本发明方法中的优化不等簇结构进 行聚合传输所需的时间均明显低于等簇结构。(b)中展现了网络节点数目N＝2500，网络规 模R从450到650变化的情况下，两种不同结构进行聚合传输的时间对比。由于网络节点的分 布的随机性，网络的聚合传输时间存在小范围的波动，但从图中仍可看出聚合传输事件几 乎不受网络规模R的变化的影响。在不同的网络规模下，本发明中的不等簇结构所需要的时 隙数也优于等簇结构下的时隙数。从两个图中来看，在部分网络环境下，聚合传输时间的优 化率将近达到20％，即使从整体上来看，优化水平也在10％左右。

因而，综上来看，本发明所提出的策略有着明显的性能优化优势且有着很强的实 践指导意义。