基于轴面对称机制的物联网节点覆盖算法

蒋世华, 陈 琳

(1.长江大学文理学院, 荆州 434020；2.长江大学计算机科学学院, 荆州 434020)

物联网技术作为“中国制造2025”计划中关键一环，正在得到国家和有关方面日益重要的关注[1]。该技术主要通过在一定监测区域、物体、空间内部署若干具有数据搜集能力节点的方式，达到有序协同组网并将采集到的数据信息发送至sink节点的目的[2]。实践中由于物联网节点往往部署于较为复杂的环境，需要适应高污染、水下、野外等实际场景，节点处于能量受限状态将难以及时实现能量补充，使得整个网络数据采集、传输、处理过程将受到严重的阻碍[3]。

为解决特殊环境下物联网节点部署过程中存在的问题，研究者提出了一些具有前瞻性的解决方案，在一定程度上满足了实践需求。Slavyana等[4]使用层次划分方案，提出了一种基于能耗均衡竞争机制的物联网节点覆盖算法，算法主要采用热点部署方法，针对能量消耗程度较高的节点采用主备机制，并通过sink节点进行能量区域消耗探测，实现了能耗区域热点的实时备份，可显著降低网络因热点能耗受限而处于传输受阻的概率，具有覆盖效率较高的特点。但是，该算法在实现区域覆盖过程中需要采用递归方式进行覆盖收敛，节点密度较高时易出现收敛速度较慢的现象，使得网络拥塞现象难以得到较好的控制，降低了该算法的适应性。Yao等[5]基于经典的簇头竞争方案，提出了一种非均衡覆盖机制的物联网节点覆盖算法，算法首先通过sink节点进行地理位置探测，重点关注盲点区域的覆盖问题，网络分割过程采用准几何覆盖模型进行充分覆盖，大大提高了簇头的覆盖竞争能力，具有网络覆盖程度完善的特点。然而，该算法在实施过程中需要采用探测方式进行路由初始化，覆盖过程对路由收敛性能的要求较高，难以同时针对多个簇头节点进行充分竞争，容易因并发竞争而导致严重的网络拥塞现象，使得该算法无法在实践中得到广泛的应用。Chang等[6]针对当前算法难以适应高密度部署环境的不足，提出了一种基于休眠节点密度自适应调控方案的物联网节点覆盖算法，算法采用多跳模式实时改变休眠节点密度，可显著降低网络能耗水平，有效改善超宽带传输条件下物联网节点易受限的难题，传输稳定性能优越。但是，该算法在区域覆盖过程中也存在节点休眠机制较为复杂的不足，特别是需要针对休眠节点进行实时探测，导致算法实施过程中复杂度过高。

为了解决上述问题，提出了一种基于轴面对称机制的区域覆盖方法。采用等距分割模型，设计了基于轴面对称机制的区域覆盖方法，以提高网络覆盖能力，降低盲区现象的发生概率。随后，设计了基于热备机制的簇头轮询方法，通过部署多个镜像节点，对簇头节点进行热备，改善了簇头节点易受限的问题。最后，对初始化区域进行非等距分割，优化其网络传输能力。并通过仿真实验来测试本文算法的优越性能。

1 网络模型概述

由于物联网(internet of things, IOT)节点在实践中一般采用随机布撒方式进行动态部署[7]，节点采用自组网模式进行区域覆盖，不同区域内存有一个或多个簇头节点(cluster head node，CH)[8]，如图1所示。网络组建完毕后，区域节点(regional node，RN)可根据需要自行进入休眠模式或激活模式。数据传输过程中，RN节点均需要通过CH节点与sink节点建立传输链路并将自身数据上传至CH节点，从而完成数据传输。

图1 物联网节点部署模型

考虑到物联网节点进行数据传输过程均采用无线模式[9]，不同节点间发送能耗E(l,B)与距离呈现密切的比例关系，当两点间距离l小于覆盖半径(R)时，发送能耗满足二次方关系；当两点间距离(l)大于覆盖半径R时，发送能耗满足四次方关系。

(1)

式(1)中：B表示当前节点的传输带宽；P0为节点的初始功率。

节点接收数据时，也将消耗一定的能量，接收能耗Erec(l,B)仅与自身功率(P)相关，即节点运行功率越高，接收过程中消耗的能量越大，接收能耗Erec(l,B)满足

Erec(l,B)=BP

(2)

由于簇头节点需要同时进行两个传输过程：汇聚簇内节点传输的数据以及将接收到的数据传输至sink节点，其中前者满足式(2)，后者满足式(1)。不妨设区域内仅有1个簇头节点以及n个区域节点，则簇头节点汇聚簇内数据所消耗的能量Erec(l,B,n)满足

Erec(l,Bn,n)=nBnP

(3)

式(3)中：P表示簇头节点的功率；Bn表示第n个区域节点的汇聚带宽。

由于簇头节点汇聚带宽总量B满足

(4)

因此簇头节点的能耗总量ECH(l,B,n)满足

(5)

式(5)中：i、j分别为第i个和第j个节点，二者满足

i+j=m

(6)

式(6)中：m表示与当前簇头节点有数据传输关系的其余簇头节点总数。

据式(5)可知，簇头节点能耗量由式(1)、式(2)所决定，在确保数据传输质量的同时，簇头节点间距离应尽量处于互相覆盖范围之内，以便降低式(5)中四次方分项的比重。此外，由于传输过程中可能存在一定的数据损耗，簇头节点将会反复将数据进行发送，因此节点覆盖的过程除须考虑互相覆盖因素外，应进一步考虑对区域进行合理分割，降低路由冗余度，以便减少数据重传过程所带来的冗余带宽量的增加。

2 物联网节点覆盖算法

物联网节点覆盖过程应尽量降低簇头节点间尚未被覆盖的区域面积，且覆盖过程应具有较为简单的几何特性，以便在降低簇头节点能耗的同时，尽量减少数据重传输次数。因此，提出了一种新的基于轴面对称机制的物联网节点覆盖算法。该算法由3个部分构成：基于轴面对称机制的区域覆盖、基于热备机制的簇头轮询、基于量化部署机制的传输优化。

2.1 基于轴面对称机制的区域覆盖

在物联网节点覆盖算法当中，采用一定的区域覆盖方法可显著提高网络生存寿命，降低节点能耗水平[9]。特别是在高污染、高损耗性环境中改变网络部署结构，可有效解决节点受限带来的传输空洞现象[10]。考虑到节点充分覆盖因素，设计了基于轴面对称机制的区域覆盖方法。首先做如下定义。

定义1初级监测区域(primary monitoring area，PM)，PM区域为本文所提区域覆盖中基本监测区域，通过簇头节点间连线与覆盖区域交线形成，如图2所示。

图2 轴面对称示意图

定义2次级监测区域(secondary monitoring area，SM)，SM区域为图1所示簇头节点覆盖的交叉区域，该区域内节点可为轴面对称两侧节点同时覆盖。

定义3簇控制区域(cluster control area，CC)，CC区域为簇控制半径所覆盖的区域，涵盖本簇内全部的区域节点，区域节点负责数据采集与上传，簇头节点将通过其余簇头节点进行数据传中继传输，最终传输至sink节点。

定理1设两个CC区域中簇头节点间距离为r,设sink节点与簇头节点间最远距离为L,则簇间距离满足式(7)时，网络耗能总量Emax最低。

(7)

式(7)中：r为簇头节点间距离。

证明1由式(5)可知，若簇头节点间距离均在覆盖半径之内，则网络耗能总量Emax满足

(8)

式(8)中：Bm表示第m个簇头节点所对应的汇聚带宽；rm表示第m个簇头节点的覆盖半径。

显然，由拉格朗日定理可知[11]，仅当rm均为同一数值时，式(8)取最小值，由定理1得证。

基于轴面对称机制的区域覆盖方法需要sink节点与各簇头节点处于共线状态，因此进行区域覆盖过程中需要同时部署多个sink节点。此外，需要指定某个sink节点作为总sink节点，以便能够实时处理簇头节点汇聚的数据。

2.2 基于热备机制的簇头轮询

据2.1节可知，覆盖过程满足定理1时，网络中簇头节点能耗将处于最低。由于物联网节点均采用一次布撒成型的方式进行节点部署，因此需要考虑簇头节点受限时如何进行簇头节点轮询[12]。基于本文提出的轴面对称机制的区域覆盖方法，进一步在节点覆盖过程中设置镜像节点作为热备簇头节点，详情如下。

步骤1将整个节点分布区域逐个分割为长条区域，长为xi,宽为yj,如图3所示。

步骤2按图3所示对长条区域进行节点覆盖：逐次按照式(7)确定的簇头节点间距离(r)对长条区域进行分割，如图4所示，其中相邻两区域的拓扑距离(d)满足

图3 网络区域分割

图4 长条区域分割

(9)

式(9)中：a为CC区域内不同传输周期内相隔最远两个节点间归一化平均距离。

步骤3按式(7)所示的距离进行区域分割后，获取PM区域总数。

步骤4确定区域分割完毕后，各区域内镜像节点个数。不妨设各区域内簇头节点能量消耗速度相同，按式(10)确定镜像节点个数(N)。

(10)

式(10)中：z为第z个区域内的簇头节点。

由式(10)可知，越是靠近sink节点的簇头节点，其分簇区域内镜像节点个数也将越多。这是由于越靠近sink节点的簇头节点，其承载的汇聚带宽总量也将越大[13]，因此须设置较多数量的镜像节点，防止簇头节点失效而导致网络数据传输受阻。

步骤5当簇头节点失效时，随机启动一个镜像节点，并将当前簇头节点重新设置为镜像节点，直到新的簇头节点因能量耗尽而处于受限状态为止。

2.3 基于量化部署机制的传输优化

考虑到基于热备机制的簇头轮询方法均采用等距方式进行节点覆盖，由式(10)可知，靠近sink节点的区域内需要部署更多的镜像节点。由于镜像节点与簇头节点之间需要进行数据同步，会使得相应区域内簇头节点能耗水平不断增加，因此需要对上述等距覆盖模式进行改进，以便数据传输能够得到进一步优化。

定理2设簇头节点间距离为r,按式(9)所示进行覆盖时，可完全覆盖长条区域，覆盖方法如图5所示。

图5 长条区域覆盖示意图

证明2由于覆盖区域可看作多个三角形，由直角三角形知识可知[14]：

r2=d2+(1/2a)2

(11)

式(11)化简可得

(12)

显然式(12)与式(9)具有相同的形式。定理2得证。

联立定理1和定理2可知，节点覆盖完毕后，整个网络区域将被等距分割。通过结合式(8)与式(12)，对此时的能耗进行微分，可得

(13)

式(13)中：Emax为网络耗能总量；ri表示第i个节点与区域内簇头节点之间的簇间距离。

显然，式(13)满足

(14)

式(14)中：L表示簇头节点与sink节点的最远距离。

对式(14)求偏导，并令式(14)取最小值，可得

(15)

则所有分区内簇头节点个数m满足

(16)

按照式(16)确定的分簇数量进行分簇，可以得到能耗最佳的分簇方案，此时网络可被节点充分覆盖，且能耗水平最低。

3 仿真实验

为测试本文算法的性能，采用NS2仿真实验平台进行仿真实验[15]。实验环境设置如下：网络覆盖区域为矩形区域，长度为10 000 m，宽度为8 000 m；sink节点均位于区域边缘，其中本文算法sink节点存在多个，对照组算法sink节点为个；节点采用物联网算法中常用的5G制式节点，信号采用正交发射模式进行预成型[16]。对照组实验采用当前常用的改进蚁狮算法的无线传感器网络覆盖优化[17](coverage optimization of wireless sensor networks based on improved ant lion algorithm，LAL算法)和基于改进粒子群算法的无线传感器网络覆盖策略[18](coverage strategy of wireless sensor networks based on improved particle swarm optimization，IPS算法)。对比参数选取网络拥塞次数、簇头节点受限数、网络传输带宽三项指标。仿真参数如表1所示。

表1 仿真参数

实验开始后，按照传输周期作为截止时间点，实时记录网络拥塞次数、簇头节点受限数、网络传输带宽，直到网络数据传输完毕。实验环境分别采用高斯信道和莱斯信道，分别用于模拟低干扰环境和高干扰环境两种实验场景。

3.1 网络拥塞次数

图6为本文算法、LAL算法和IPS算法在网络拥塞次数上的仿真测试结果，由图6可知，本文算法在低干扰环境和高干扰环境下均具有较好的网络拥塞控制能力，相应的网络拥塞次数较低。这是由于本文算法针对物联网节点覆盖过程中存在的盲区以及热点现象，设计了基于轴面对称机制的区域覆盖方法进行节点充分覆盖，覆盖面较为全面；并通过基于热备机制的簇头轮询方法，预置较多数量的镜像节点用于缓解网络拥塞现象，因而网络拥塞控制能力较强。LAL算法主要通过设计连续性边界收缩因子提高网络覆盖速度，且构建动态混合变异方法进一步增强节点覆盖能力，然而由于该算法未进一步通过备份机制提高簇头节点对区域节点的控制能力，因而较易发生网络拥塞现象。IPS算法主要通过引入递减的惯性权重系数，提高各簇头节点对区域节点的覆盖能力，然而由于该算法并未考虑到优化节点覆盖半径，降低因节点覆盖半径不可控因素而导致的区域覆盖失败现象，因此该算法易因区域覆盖存在盲点而导致网络流量出现过载现象，致使网络拥塞次数较高。

图6 网络拥塞次数

3.2 簇头节点受限数

图7为本文算法、LAL算法和IPS算法在簇头节点受限数上的仿真测试结果，由图7可知，本文算法在两种不同的干扰环境下均具有簇头节点受限数较低的优势，显示了良好的区域覆盖及簇头节点控制能力。这是由于本文算法考虑到物联网节点进行覆盖过程中存在的区域分割困难以及簇头节点轮询困难等不足，对簇头节点进行了轴面对称分割，预置一定数量的簇头节点进行二次覆盖，提高了节点对受限现象的规避能力，并采用基于量化部署机制的传输优化方法优化区域传输质量，因此簇头节点因能量受限或数据拥塞而出现瘫痪的概率较低，使得仿真实验中显示了较少的簇头节点受限现象。LAL算法针对簇头节点易受限的难题，主要通过构建动态混合变异方法优化节点覆盖质量，但对数据拥塞或能量受限等极限现象考虑不足，因而簇头节点受限概率高于本文算法。IPS算法采用了惯性权重系数优化节点覆盖方案，然而由于该算法在进行区域分割过程中均采用等距分割方式，并未考虑通过优化节点覆盖半径的方式降低簇头节点能耗水平，因此出现簇头节点受限现象高于本文算法，显示了较高数量的簇头节点受限数。

图7 簇头节点受限数

3.3 网络传输带宽

图8为本文算法、LAL算法和IPS算法在网络传输带宽上的仿真测试结果。由图8可知，本文算法网络传输带宽始终处于较高水平，显示了较为优越的网络传输能力。这是由于本文算法采用轴面对称机制并结合簇头轮询方法，可显著提高网络节点覆盖能力，规避传输盲区，起到了较好的数据优化传输效果，因而具有较好的网络传输能力。LAL算法单纯采用动态混合变异方法提高簇头节点覆盖及数据传输能力，未考虑采用主备机制提高簇头节点传输能力，因而具有较低的网络传输带宽。IPS算法采用了惯性权重系数优化节点覆盖方案提高簇头节点覆盖能力，然而由于该方案采用等距方式进行节点覆盖，容易存在一定的传输盲区，因而网络发生拥塞的概率较高，降低了网络传输性能。

图8 网络传输带宽

4 结论

为提高物联网部署过程中节点覆盖性能，提出了一种基于轴面对称机制的物联网节点覆盖算法，算法主要由基于轴面对称机制的区域覆盖方法、基于热备机制的簇头轮询方法、基于量化部署机制的传输优化方法三部分构成，可显著提高网络节点覆盖能力，改善簇头节点传输性能，具有较好的节点覆盖效果与网络传输能力。

下一步，将针对本文算法需要部署多个sink节点的不足，拟采用节点层次分割方案，引入多级汇聚传输机制，进一步提高本文算法的覆盖性能与网络传输能力，促进算法在实践中的进一步推广。