基于超图的热计量表物联网分簇算法

陈云云

摘要：为了提高热表物联网中热表数据传送的准确性和及时性，文章把超图理论引入热表物联网中，提出了一种基于超图的热表物联网分簇算法，此算法是把物联网采集数据的这种网络拓扑结构看成是一个超图模型，在超图模型划分的簇域中举出一个簇头，它作为本地基站将簇内节点传给它进行数据融合后再传给基站，提高数据传输的成功率，降低了节点消耗的能量，延长了网络寿命。最后通过仿真，将基于超图的热表物联网分簇算法与传统经典的LEACH算法进行比较，实验结果表明该算法能够有效地提高数据传输成功率，并减少节点能量消耗。

关键词：超图；热量表；物联网；分簇算法

随着中国经济建设和热力事业的蓬勃发展，物联网应用到热力系统成为人们关注的焦点，把物联网理念引入热力系统之后，很大程度上提高了热力系统的信息化水平，特别是对热表数据抄送具有十分重要的意义。如何对热量表采集的数据进行处理，使数据能够快速、准确地传送到管理主机，一直是目前研究热表物网者迫切需要解决的问题。超图作为一般化图的推广自1973年berge在文献[1]中系统提出之后就备受人们的关注，关于超图理论的应用也越来越广泛。为了使热表传感器在传送数据时降低能量的消耗，同时提高数据传送的快速准确，本文将超图理论引入热表物联网中，提出了一种基于超图的热表物联网数据分簇算法。

基于超图的热表物联网分簇算法设计的重点是降低能量的消耗，把物联网采集数据的这种网络拓扑结构看成是一个超图模型，在超图模型划分的簇域中举出一个簇头，它作为本地基站将簇内节点传给它进行数据融合后再传给基站，提高数据传输的成功率，降低了节点消耗的能量，延长了网络寿命。

1 基于超图的热表物联网信息处理方案

基于超图的热表物联网分簇算法是一种层次型拓扑结构，将热表传感器网络的拓扑结构抽象为超图模型，此模型根据一定的规则要求划分为簇域，在簇域中选取簇头作为数据控制的中心节点，将簇内的数据在本地进行数据融合后再转发给基站更近的簇头或直接发送到基站，这样减少了数据转发的次数，并节省了网络中节点传输的能量。

I.I 超图定义

定义1：设V={v₁，v₂，v₃…v_n}是一个集合，集合里有n个结点，ξ={e₁，e₂，e₃…e_n）也是一个集合，且满足 ，可以称H=（V，ξ）是在v上的超图。

定理1：如果超图为超树，当且仅当其对应的二分图G是树。

由于顶点和超边的二元关系的复杂性，一个连通超图H的生成树T并不总是存在的。

1.2 超图模型

用超图 来抽象表示一个层次型的传感器网络。其中 是节点的集合，并且其中的每个节点对应每个传感器节点， 是超边的集合，把监测的网络结构看作是超边，把 记为主干超边，则 ，其中M为 的头节点， 为E，的网关节点，作用是与其他连接 为E，的剩余节点。根据已有的网格划分算法网络簇结构可以分为2类：

（l）相邻的网格之间有共同的网关节点，即 。

（2）相邻的网络之间无共同的网关节点，节点之间进行通信可以通过网关，即 。

根据定理1可以推出，给定一个连通超图，依据（1）划分的网格来生成超树是不可能的，如果基于（l）来划分网络，可能出现的分簇情况如图1所示，抽象的超图如图2所示。如果基于方式（2）来划分网格，抽象的超图如图3所示，可以选择2个网格之间节点连接权值最小的2个节点作为2个网关节点，这2个网关节点连成一条边，称为超边e，以连接2个主干超边。基于方式（2）划分网格可以生成超树T。

1.3 方案描述

本文提出的基于超图的热表物联网分簇算法，其设计思想是簇首的选取是通过计算簇内结点权值的大小来确定，权值最大的作为簇首，具体的算法描述是把热表区域划分为n个正方形区域，如图4所示。

首先用标定的方法标定坐标点（在正方形的中心），标定好之后，依据各个坐标点与传感器距离的长短，把传感器加入到簇域内。

划分好簇域后，在每个簇域内任意选取一个标记点H，选取之后，首先计算H的权值，然后再计算域内其他结点的权值，把这几个权值进行比较，选取权值最大的节点为簇头，最后簇头节点作为中心节点进行数据的广播。

在划分好的簇域中，本文把簇域内的簇头看作是一个路由器，簇域内的每个节点把采集到的数据直接传送给路由器节点（也就是簇头节点），路由器收到数据之后，对数据进行分析、处理和转发，也就是说把热表传感器的所有数据汇聚到基站，然后通过无线网络发送到热力公司。

2 算法分析和仿真

仿真的监测环境设置在lOOmXlOOm区域内，设置监测区域的上方是汇聚的结点，即（100，300）。设置通信圆半径为15.6m，每个节点的初始能量IOJ，本文对基于超图的热表物联网分簇算法（HCTA）进行仿真，并与经典的LEACH算法进行比较，主要评价基于超图的热表物联网热表传感器算法性能：数据传输成功。

首先计算传输数据的成功率，如图5所示。通过仿真可以得到HCTA算法数据传输成功率较LEACH算法高。这是因为在超图算法中划分了多个簇域，在每个簇域中计算节点的权值，把权值最大的记为簇头，把簇头看作是路由器给基站发送数据，当路由器的能量低到一定值后，给基站发送特定的数据，基站对数据进行分析来判断网络运行的情况，从而判断是否重新选取簇头，这样做使得在通信的过程中平衡了网络的能量，从而使网络能够持续运行，而LEACH算法中簇头的选取是随意的，如果基站与簇头通信的过程中判断需要重新选取簇头，则簇头的选取是无规则的，任意选取，最后导致多个簇头与基站进行数据传输，这样做使得在通信的过程中过多地消耗了网络的能量，从而使网络不能够持续运行，数据传输的成功率下降。

3 结论

把超图理论引入热表物联网之后，降低了热表传感器各个节点消耗的能量，延长了网络寿命，从而保证了数据传送的准确性和实时性。文中把物联网大规模的无线传感器网络拓扑抽象为超图模型，提供高效网络服务。通过仿真可以看出，此算法优于经典的LEACH算法，不但能够有效地提高数据传输成功率，而且能够减少节点消耗的能量。