一种基于最小生成树的数据聚合方法

摘要

本发明公开了一种基于最小生成树的数据聚合方法，其主要步骤包括：部署无线传感器；选择簇头；分簇；簇内节点构成简单图模型；簇内权值的计算；簇内节点构建最小生成树；簇内数据聚合；簇头权值的计算；簇头节点构成简单图模型；簇头节点构建最小生成树；簇头数据聚合；均衡节点能耗；簇的维持。本发明通过合理布置传感器节点和对节点进行分簇，使传感器节点的能耗均匀分布，延长了整个无线传感器网络的生命周期，使得所有节点的能量能够得到高效的利用。

主权项

一种基于最小生成树的数据聚合方法，其特征在于，具体包括：步骤1、部署无线传感器：在检测区域内，将无线传感器部署在检测区域；步骤2、选择簇头：将整个检测区域按网格进行均匀划分，使每个网格的大小形状相同，在每个网格中选择位置距离网格中心最近的传感器节点作为簇头；步骤3、分簇：簇头选择完成后，簇头广播Cluster{ID，N，Hop}信息，其中，ID为节点的编号，N为Cluster信息转发的跳数，且N的初值为0，Hop为系统设定的跳数；处于簇头附近的邻居节点收到Cluster信息后N增加1再转发这一信息，直到N=Hop就不再转发Cluster信息；簇头的邻居节点转发Cluster信息后再向将Cluster信息转发给自己的邻居节点，然后发送一个反馈信息Join{ID，N，Eir，dij，ki}给将Cluster信息转发给自己的节点，最终将Join信息转发给簇头表示自己加入该簇，其中，Eir表示该节点此时的剩余能量，dij表示两节点间的距离，ki表示该节点能够监测得到的数据包的大小；如果一个节点收到了多个Cluster信息，节点就选择N值小的加入该簇，若N相等节点就随便选择一个簇并加入到该簇；如果节点没有收到Cluster信息，则节点发送Help信息，加入离自己最近的一个簇；步骤4、簇内节点构成简单图模型：通过步骤3得到簇内所有节点在簇内所处的位置，将每个节点当做图的一个顶点，每两个相邻节点间用边相连接；步骤5、簇内权值的计算：通过所述步骤3，簇头获取簇内成员节点的Eir、dij和ki，计算相邻两节点i，j之间的权值，权值的计算公式为：Wij=a1(Eir+Ejr)+a2dij+a3(ki+kj)    （1）其中，Ejr、kj分别表示节点j的剩余能量和节点j能够监测得的数据的大小，且a1+a2+a3=1；步骤6、簇内节点构建最小生成树：根据所述步骤4得到的簇内节点构成的简单图模型和所述步骤5得到的权值，构建簇内节点最小生成树；步骤7、簇内数据聚合：簇内节点的最小生成树构造完成后，传感器节点开始正常工作，从最低一级传感器节点开始，将收集的数据传给父节点，父节点将自己收集的数据和子节点传来的数据聚合后再传给自己的父节点，最终将聚合数据传输给簇头；步骤8、簇头权值的计算：通过步骤3分簇完成后，簇头获得整个簇内节点的位置、节点剩余能量和传感器节点可能监测得到数据的大小信息，其中，Ecir=E1r+E2r+…+Eir表示整个簇的剩余能量值，Kci表示簇头聚合的数据大小，Dij表示相邻簇头间的距离，对相邻两 簇头i，j之间权值进行计算，权值定义为：Wij=b1(Ecir+Ecjr)+b2Dij+b3(Kci+Kcj)    （2）其中，Ecjr和Kcj分别表示簇头j的剩余能量值和簇头j聚合的数据大小，且b1+b2+b3=1；步骤9、簇头节点构成简单图模型：将每个簇头当做图的一个顶点，相邻簇头之间用边相连接，每条边的权值由公式（2）计算得到；步骤10、簇头节点构建最小生成树：由步骤8给出的簇头节点构成的简单图模型后，构建簇头节点最小生成树；步骤11、簇头数据聚合：簇头节点的最小生成树构造完成后，从最低一级簇头开始，将收集的数据传给父节点，父节点将自己聚合的数据和子节点传来的数据聚合后再传给自己的父节点，最终将聚合数据传输给基站；步骤12、均衡节点能耗：根据预先设定的轮数阈值M，每进行M轮后，重新选择簇头，然后重新进行步骤2‑11，其中，节点的能耗可由LEACH能耗模型进行估算；步骤13、簇的维持：簇内节点死亡后，就可能会造成簇内的最小生成树路径失效，所以在节点即将死亡前，节点发送一个Die信息给簇头，表示自己即将死亡，簇头接收这一信息后，簇头就开始对簇内节点重新构建最小生成树。