面向智慧家居的异构自组织网络分簇算法＊

邓晓平，马路娟

(山东建筑大学信息与电气工程学院，山东 济南 250101)

0 引言

随着5G 的商用，作为5G 重要应用场景之一的智慧家居受到了学术界和工业界的广泛关注。据预测，我国智慧家居市场规模2022 年有望超过250 亿美元，占全球市场份额的25%左右[1]。然而，随着数据流量和连接数量的爆发性增长，原有的集中式架构不能满足大量设备的接入需求，支持设备随时接入和退出的自组织网络成为智慧家居领域的研究热点[2]。基于分簇的层次化自组织网络架构可以减少网络中的通信量，提高网络的可扩展性，并降低节点移动性带来的影响。

低功耗自适应集簇分层型协议(Low Energy Adaptive Clustering Hierarchy,LEACH)是分簇算法的典型代表，其基本思想是以循环的方式随机选择簇头节点，将整个网络的能量负荷平均分配到每个节点，从而达到降低网络能源消耗、提高网络生存周期的目的[3]。在此之后，一系列基于LEACH 的改进型算法被提出[4-6]。Ahmed[7]根据路径成本和节点之间的连接数来选择每个簇的簇头。Mustafa[8]提出了三层架构LEACH 协议。韩广辉[9]在簇头选取时引入了节点的剩余能量以及网络的平均能量，使剩余能量比网络平均能量高的节点优先充当簇头。李芳芳[10]采用分布式自协商和集中式相结合的成簇算法。近几年也有一些其他分簇算法被提出。Ahmad[11]提出了一种启发式的分簇算法，提高了簇的有效性和可靠性，并降低了控制开销。已有分簇算法大都针对无线传感器网络提出，基于节点平等性假设，并且以降低能耗为目标，不适用于节点异构、时延和到达率敏感的智慧家居网络。

为进一步改善设备的到达率和时延均衡性，本文在充分调研分析智慧家居网络的特点基础上，提出了适合智慧家居网络的分簇算法，其创新性与贡献具体如下：

⑴在分簇算法中，分簇算法自动适应家庭拓扑，避免了簇头和成员节点之间穿墙通信造成信号的严重衰减；

⑵在簇头决策阶段，提出了对节点进行多维度优先级划分的方法，确保了选出的簇头具有更好的通信能力和计算能力、更长的生命周期、更低的失效率；

⑶在数据发送阶段，给出了基于业务特征选择信道分配策略，降低了传输时延；

⑷部署构造了仿真环境，并进行了性能验证。仿真结果表明，与传统的LEACH 分簇算法相比，所给出的异构自组织网络分簇算法更加适合具有突发数据的智慧家居网络，并且设备的时延更加均衡。

1 智慧家居网络特点分析

要设计适合智慧家居网络的分簇算法，有必要对这种网络的特点进行分析，其特点主要体现在以下几方面。

1.1 异构性

智慧家居网络是一个典型的异构网络，网络中的设备在通信能力、计算能力、存储能力等方面都存在很大差异。已有的分簇算法大都基于同构网络，即所有节点都是完全一致的。即使在某些算法中，考虑了网络的异构性，也是只考虑了节点的初始能量不同，不符合智慧家居网络的实际情况。

1.2 覆盖范围较小

家庭网络覆盖范围相对较小，一般只有几十平米，最多几百平米。并且，我们可以很容易得到家庭户型图和固定设备的摆放位置，为分簇算法提供依据。

1.3 数据流具有突发性和不均匀性

无线传感网节点不断采集周边环境的数据，通过固定的周期上传数据，数据流是均匀分布的。但是对于家庭网络来说，既有周期上传的数据，也有突发的数据。

2 面向智慧家居网络的分簇算法

本文所给出的分簇算法的过程分为初始化阶段、分簇阶段和数据传输阶段。初始化阶段分为区域划分阶段和簇划分阶段，分簇阶段分为簇头选举阶段和簇形成阶段，数据传输阶段分成很多帧，每一帧分为突发时隙阶段和固定时隙阶段，帧结构如图1所示。

图1 帧结构

2.1 算法假设

适合智慧家居网络的分簇算法基于以下合理假设。

⑴房子的户型图和设备在房间中的位置已知。

⑵ 将家庭中的设备按照能量供给方式分为两类：常带电设备和充电设备，假设固定设备都是常带电设备，定义为A 类设备，移动设备都是充电设备，定义为B 类设备。假设节点知道自己属于哪一类，并且B类设备可以感知自己的剩余能量。

⑶ 将家庭中的设备按照通信距离远近分为两类：I类设备和II类设备，I类设备指的是使用移动蜂窝网通信的设备，II 类设备指的是使用Wi-Fi、蓝牙、Zigbee和D2D通信的设备。

⑷用一个计算能力系数C 来表示设备的计算能力，C是介于0到1之间的一个小数，0表示该设备不具有计算能力，1 表示该设备具有整个家庭网络中最强的计算能力。假设节点知道自己的计算能力系数。

⑸将整个家庭中的设备按照是否定期上传数据分为两类：周期设备和突发设备。假设节点知道自己属于哪一类，并且周期设备知道自己的上传周期是多长。

2.2 初始化

初始化工作的第一步是利用设备的地理位置信息，以房间为单位将设备划分成不同的区域，小房间划分成一个区域，大房间划分成多个区域，每个区域就是一个簇，给每个簇进行编号。簇半径按照图2所示方法予以确定，该方法将整个家庭网络按照房间划分成大小不等的矩形区域，小房间被划分成一个区域，大房间被划分成多个区域。每个矩形区域都能被完全包含在半径为Ri的圆中，要求：Ri≤R0,i=1,2,3,4,5,6。

图2 簇的划分

2.3 簇形成

簇头选举只在已经划分好的区域内进行，不需要跟基站进行通信，只需要在簇头选举完成后通知基站，处理本地化，降低了基站负载，缩短了簇头选举时间。在选举簇头的过程中，充分考虑家庭网络的异构性，每个区域根据设备类型不同和应用场景不同采用不同的簇头选择标准。并且基于节点地理位置选择簇头，使选出的簇头与簇成员之间具有更小距离。

⑴设备筛选

只有I类设备参与簇头选举，II类设备在簇头选举阶段关闭自己的通信模块，不参与簇头选举，如果簇中存在A 类设备，B 类设备不参与簇头选举，当簇中不存在A类设备时，才在B类设备中选择簇头，这个过程称为设备筛选，如图3 所示。当存在A 类设备的家庭网络中发生断电时，A 类设备将完全失效，重新在B 类设备中选择簇头。

图3 设备筛选流程图

⑵计算竞争值

如果是A 类设备竞选簇头，就不考虑移动速度和剩余能量，将计算能力C 节点位置系数L 按照一定系数加权。位置系数是按照节点在簇中所处地理位置决定的，越靠近簇中心的设备位置系数越大，位于簇的圆心位置的设备位置系数为1，位于圆周上的设备位置系数为0，如图4 所示为簇i内设备位置系数的计算方法，设备1 的位置系数是1，设备3 的位置系数是0，设备2 的系数。设备i的竞争值Wi=w1Ci+w2Li，其中w1+w2=1，w1和w2的值根据具体的应用场景来确定。选择竞争值最大的设备作为本簇的簇头。

图4 位置系数示意图

如果是B 类设备竞争簇头，就要考虑移动速度和剩余能量，分别将移动速度和剩余能量归一化为速度系数和能量系数。速度系数用S来表示，固定设备的速度系数为1，定义整个家庭网络中具有最大速度Vmax的设备速度系数为0，设备i的速度为Vi时速度系数。假设整个网络的充电设备中具有最大剩余能量Emax的设备能量系数是1，能量为0 的设备能量系数是0，则具有剩余能量Ei的设备能量系数Ni=EiEmax。设备i的竞争值Wi=w1Ci+w2Li+w3Si+w4Ni，其中w1+w2+w3+w4=1，w1，w2，w3，w4的值根据具体应用场景来确定。选择竞争值最大的设备作为本簇的簇头。

每个设备将自己的竞争值在簇内进行广播。如果接收到其他节点的竞争值大于自己的竞争值，则关闭通信模块直到簇头选举阶段结束；如果在整个簇头选举阶段，一直没有收到比自己大的竞争值，则该节点当选为簇头，并在簇头选举阶段结束后广播自己当选簇头这一结果。

簇内成员节点收到本簇簇头的当选广播后，向簇头发送加入请求，簇头收到后予以确认，加入到自己的簇成员列表中，如图5所示。

图5 簇形成流程图

2.4 数据传输

在家庭环境中，能量不再是首要考虑的问题，因此应尽量使用单跳传输，降低传输时延，包括簇头与基站的通信，簇头与成员的通信，一个簇内成员之间的通信，簇头与簇头的通信等。使用CDMA 来避免不同簇之间相互干扰，给每个簇分配不同的扩频码，如图6所示。

图6 扩频码分配

将整个数据传输阶段分为很多帧，每一帧包括m个突发时隙和n个固定时隙，突发时隙用来传输突发数据，固定时隙用来传输周期上传的数据，突发时隙和固定时隙所占一个帧的比例根据本簇内业务需求灵活确定。固定时隙阶段每个时隙固定分配给某个周期上传数据的设备，在每个帧的这个时隙到来时该设备上传数据；突发时隙阶段的时隙可以灵活分配，允许一个设备占用多个时隙，如图7，设备1 和设备2是突发设备，设备3、4、5是周期设备。

图7 时隙分配图

3 仿真分析

3.1 仿真场景

以某智慧家居公司的实际部署构建仿真场景，房屋户型图和节点分布如图8所示。

图8 仿真场景

家庭内的设备包括以下类型，括号内的数字表示该类型设备的数量。

⑴ I 类A：冰箱⑵、彩电⑶、洗衣机⑵、空调⑷、热水器⑴；

⑵I类B：手机⑸；

⑶II 类A：温湿度传感器⑻、光照传感器⑹、可燃气体探测器⑴、红外探测器⑴、灯⑾、门磁⑹、微波炉⑴、电炊具⑴、洗碗机⑴、智能浴缸⑴、智能抽水马桶⑴、电表⑴、水表⑴、燃气表⑴、抽油烟机⑴、加湿机⑴；

⑷II类B：PDA+笔记本电脑⑷。

3.2 参数设置

信号穿透不同障碍物的衰减值如表1所示。

表1 损耗附加值取值表

能耗与功率设置如表2所示。

表2 能耗与功率设置

数据上传周期及数据包大小如表3所示。

表3 家庭内各设备数据上传周期及数据包大小

3.3 仿真结果

智慧家居环境更关注的性能是时延和可靠性，因此我们选择时延和到达率作为本次仿真的性能评价指标，并将适合智慧家居的分簇算法（SH）与经典分簇算法LEACH进行比较。

当突发时隙在每个帧中设置为三个，突发数据大小为1.5*106bits 时，端到端时延和到达率的仿真结果图9和图10所示。

图9 端到端时延对比图

从图9 可以看出，对于I 类设备和II 类A设备而言，两种算法的时延差别不大，但是对于II 类B 设备，SH 算法比LEACH 算法的时延降低了36%，这是因为对II 类B 设备来说，数据包大而且传输速率低，在LEACH 算法中一个帧无法完成一个数据包的传输。而在适合智慧家居的分簇算法中，数据包比较大的突发数据可以占用长达三个时隙的突发时隙，保证任何数据都可以在一个帧内传输完成，因此时延较低。从图10 可以看出，对于所有设备,适合智慧家居的分簇算法都达到了100%，这是因为在分簇的过程中采用了先分簇再选择簇头的方法，保证一个簇中的所有设备都处于同一房间中，避免了设备之间穿墙通信造成的较大衰减，而且使得一个簇内的设备距离较近，提高了成员设备与簇头的可达性。

图10 到达率对比图

将突发数据包大小分别设置为3*106bits，4.5*106bits，6*106bits，7.5*106bits，9*106bits，突发时隙分别设置为6，9，12，15，18 个，观察端到端时延的均衡性变化规律，结果如图11和图12所示。

图11 LEACH算法设备端到端时延

图12 适合智慧家居的分簇算法设备端到端时延

在LEACH算法中，A类设备对突发数据包的大小不敏感，B类设备随着突发数据包的增大而增大，尤其是对于II类B设备，当数据包变为原来的五倍时，时延也变为原来的五倍。

适合智慧家居的分簇算法中，四种设备的时延都会随着突发数据包的增大而增大，其中B 类设备的时延增长率更快，当突发数据包为原来的5 倍时，I 类B设备和II类B设备的时延分别为原来的三倍和四倍。

综合以上时延和到达率的仿真结果，与LEACH算法相比，适合智慧家居的分簇算法可以显著提升到达率和降低时延，并且使不同类型设备之间的时延更加均衡。

4 结论

针对智慧家居网络的特点，本文提出了一种基于节点异构性和地理位置的智慧家居网络分簇算法，并且基于智慧家居实际部署进行了仿真分析。根据仿真试验结果，可以得出以下结论：①通过将簇的范围限制在一个房间之内，并且选择具有蜂窝网络通信能力的设备作为簇头，可以使设备的到达率达到100%；②通过在数据帧中设置突发时隙，可以显著降低具有突发数据的设备时延；③采用固定时隙和突发时隙相结合的帧结构，可以提高不同类型设备的时延均衡性。本论文给出的算法为进一步提高实际智慧家居系统中无线通信模块的网络性能提供了基础。