一种WSN消冗降耗多跳路由发现算法

李猛坤，郭小民，张 月，贾军营

（1.首都师范大学 管理学院，北京 100089；2.沈阳风驰软件股份有限公司，沈阳 110167）

近些年，物联网和无线移动智能终端的迅速普及催生了无线传感器网络（wireless sensor network，WSN）的迅猛发展[1-2]，目前，无线传感器网络被广泛应用于医疗、环境监测、气象监测及军事等领域，可实现对环境中各种物理现象或物理量的低功耗检测.相较于传统的传感器网络，WSN由多个传感器节点组成，这些传感器节点具有感知、计算和通信能力，并可以通过多种方式将收集的数据传给终端进行分析.因此，在不具备通用信息传输环境的条件下，WSN成为最好的选择，其可以有效解决有线传感器在面对偏僻区域或敌对环境时有线基础设施不可行的问题.

传感器节点是物联网的感知层面，节点一般采用电池进行供电，节点的使用时长直接关乎着网络的生命周期[3].近些年来，如何降低能耗，同时延长整个网络的生命周期，提高能量的利用效率，已成为WSN研究方向中的热门课题.合理的路由协议可以有效实现WSN的能耗优化[4-5].在单跳路由研究方面，文献[1-2]提出通过加入剩余能量的比例因子来提升网络能量，但其忽略了簇头节点传输到基站的能量消耗.文献[6]在单跳簇头选择策略上做了进一步优化，但并未给出整个数据传输过程的能耗策略.在多跳路由研究方面，文献[7]针对无目标场景的情况，在路径树的选择中通过多跳方式减小能耗，但其忽略了多跳路由带来的数据冲突问题.

WSN中的低功耗自适应分簇路由协议（low energy adaptive clustering hierarchy，LEACH）首次引入了节点聚类分簇的思想[8]，通过周期循环的方式试图让所有的节点都轮流充当簇头节点，从而平均分担发送数据所消耗的能量，以尽量减少系统总能量的消耗.但LEACH的边缘节点会出现能量易耗尽或能量负载不均衡的问题，且由于协议中节点随机分布，会导致簇头的位置分布不确定，使得有些节点可能没有簇头.每个簇内成员数量的差异过大，也会产生网络延时和网络数据冗余.此外，基于LEACH协议引入多跳路由还会导致数据冲突引起的数据延时和冗余等问题，而大多基于LEACH协议改进的多跳协议只是采用了随机分布的方式挑选簇头，忽略了数据转发融合的冗余问题以及簇头节点的分布问题.基于此，本文通过研究簇头节点的选取方式和多跳路由发现算法，提出一种消冗降耗多跳路由发现算法，在一定程度上解决多跳路由转发带来的数据冗余传输问题，从而降低簇头网络能耗，延长网络生存周期.

1 实验条件

1.1 LEACH算法的不足

在层次型WSN中，由于节点随机分布，每个簇头成员的数量不一致.设一个时钟周期为Round，一个簇内的时钟周期为period，period的大小由簇内的成员决定，簇头节点首先接收簇内节点发送的数据包，再将数据转发给下一个中继节点.

如图1所示，设有2个簇头节点p1和p2，p2内有7个簇成员，p1内有2个簇成员，p2为p1的中继节点.p1在t3时刻会将数据融合并转发给p2节点，而此时p2还在接收簇内成员的节点信息，这样就会造成数据冲突，导致p1节点重发.当簇内节点数量差异较大，并且簇头数量大的节点作为中继节点时，会造成更加严重的数据冲突问题，从而导致很高的丢包率，进而产生更大的能耗.因此，本实验采用时间同步协议为实验假设条件，在时间同步协议下，在簇内的一个period中节点可以同时接收簇内节点的数据包和来自其他簇头节点的数据包，并将数据融合后再进行转发，这样，在降低了数据冲突的同时，减少了重发的能耗损失，延长了整个系统的网络生命周期.

图1 数据冲突情况Fig.1 Data conflict

1.2 时间同步协议配置

同层级间采用TPSN时间同步，不同层级节点的时间同步采用双信道方式进行数据包发送，并使用传感器节点附带2个射频模块的装置.每个节点设计使用2个射频模块，一个射频模块进行簇内的收发，只有当节点成为簇头节点时启用另一个射频模块，并进行簇头间对数据包的收发.

协议运行步骤如下：

（1）利用簇头选择算法，确定节点是否作为簇头并启用双信道模式，同时广播包含簇首id信息的数据包.在广播阶段结束后，接收通过incode发送的簇内成员的数据包信息和通过outcode发送的其他簇头节点的数据包信息.

（2）非簇头节点选择最近的簇头节点并发送入簇申请takepart_REQ，包含节点id、剩余能量以及节点与网络中所有簇头的距离等信息.

（3）簇头节点接收信息后开始广播incode和outcode上的TPSN时隙表.

（4）广播结束后，各个簇头节点选择合适的中继转发节点，调整发送数据的发射功率和射频.

（5）对于稳定的传输节点，在簇内incode信道上接收来自簇内成员的数据信息，在outcode信道上接收其他簇头节点发送的数据信息.

（6）重复步骤（1），循环执行以上步骤，直到所有节点死亡.

2 簇头选择算法

2.1 簇头选择算法的改进

将节点剩余能量与所有节点剩余能量总和的比例因子，以及节点与基站的距离与所有节点与基站距离之和的比例因子，加入LEACH算法的参数阈值中，并使用多跳通信模型[9-10]，即距离基站节点较远的簇首节点需要选择中继节点转发数据，以降低网络能耗.设均衡因子M为

其中：μ和γ为权重比例系数且和为1.改进的簇头选择算法为

其中：P为簇头被选择的概率；r为已经完成的回合数.新的簇头选择公式（2）考虑了节点剩余能量Ei-rest和WSN的平均能量Eav.若当前周期内存活节点的数量为n，则整个WSN的能量消耗为

上述改进的簇头选择公式提高了剩余能量高的节点和距离基站近的节点被选为簇头的概率，因此可以大幅度提升整个WSN的生命周期.

2.2 模型建立

假设WSN具有如下限定条件：

（1）节点任意分布在一个100 m×100 m的正方形区域内，且节点放置后无运维支撑.

（2）每个节点的功能都相同，且有能量改变其自身发射功率直接与基站进行通信.

（3）节点有一定的计算和存储功能，以及数据融合能力.

（4）基站位置固定且能量不受限制.

WSN的节点能耗模型见图2，其中：Et为发射器消耗能量；Er为接收器消耗能量；εfs为有关放大率的接收器灵敏度；εamp为接收到噪声图像相关的放大能量；Eelec为数字编码等因素有关的电量；d为节点间距离.

图2 传感器节点能耗模型Fig.2 Energy consumption model of sensor node

簇头节点执行以下操作.

首先，通过上述公式选择簇头节点，簇头节点集合广播成为簇头.

其次，非簇头节点接收簇头发来的广播的报文，并通过距离选择加入簇头，发送join报文.

然后，对应的簇头接收确认加入的信息.

最后，簇头节点统计接收普通节点传来的报文数据，然后向基站发送数据.

2.3 仿真分析

使用Matlab软件模拟WSN节点，在仿真场景中配置一个100×100的区域，并随机生成400个节点.设置仿真参数见表1.

表1 仿真环境参数Tab.1 Simulation environment parameters

图3给出了随着发送信息总轮数的增加，原算法和改进算法网络中存活节点数的变化情况，以节点能量消耗完毕无法转发信息定义节点死亡.由图3可以看出，改进后的算法出现第1个死亡节点的总轮数以及所有节点死亡时的总轮数明显大于原算法，因此改进后的算法延长了整个网络的生命周期.

图3 2种算法的存活节点数Fig.3 Number of surviving nodes of two algorithms

图4为随着发送信息总轮数的增加，2种算法网络总能量的变化情况.由图4可以看出，改进后的算法减少了整个网络的总能量损耗速率，提升了数据发送系统的寿命.

图4 2种算法的系统总能量Fig.4 Total energy of system of two algorithms

3 多跳路由路径

3.1 簇内多跳路由能耗分析

簇内网络中继节点能耗示意图如图5所示.图中，C节点为簇首，A、B为C的簇内成员.

图5 中继节点能耗示意图Fig.5 Energy consumption of relay nodes

设向一个节点发送数据的能量消耗为

在有中继节点的情况下，即传输中继为B，B融合A的数据后再发送至C，消耗的能量为

其中：Eelec为电路能耗系数；εfs为自由空间放大系数；k为传输的数据量；Emerge为融合能耗系数.当E2（D1，D2，C）

3.2 基于能耗最小原则的簇内最短路径

首先初始化节点分布，在节点中划分簇头及其覆盖节点.对于不同簇头共同覆盖的节点，采用距离与簇头节点剩余能量的权重选择簇头，从而使区域划分更利于低耗能.基于节点剩余能量、下一跳的传输距离与耗能作为每条路径的权重，在簇内寻找所有节点到簇首耗能最小的路径.

对于初始化设定的簇头节点，因为这些簇头节点也与其他节点一样有着相同的能耗，只是在逻辑上有着簇头的身份，所以当某个簇头节点的能量消耗至预设值时，则使用改进的簇头选择算法重新选择新的簇头节点.

3.3 多跳路径的构建

3.3.1 簇头间多跳路径的构建

分簇阶段结束后，网络的各个层级已实现了时间同步，在此基础上开始进行稳定的信息传输.簇头节点的能耗主要在数据传输上，因此簇头节点通过寻找到基站的中继节点可以有效减少能量的损耗.簇头节点通过中继节点向基站传输数据的路径具有方向性.将簇头按照与基站的距离由小到大建立一个有序的簇头集合，在该集合中，根据距离和剩余能量权重确定中继节点，从而建立中继节点集合和非中继节点集合.当所有簇头都确定中继节点集合后，则多跳路径构建完成.

多跳路径构建的具体步骤如下：

（1）确定中继节点集合的第1个节点，并记录其路径信息.

将距离基站最近的簇头节点CH1连接到多跳路径中，CH1为有序簇头集合C0的第1个元素，将基站节点加入中继节点集合Choice，并记录CH1的路径信息为

其中：ECO（CH1，Choice1）为节点setup总耗能，ETR（CH1，Choice1）为簇头节点传输数据能耗，ERE（CH1，Choice1）为节点接收数据能耗.设簇头节点与可选择中继节点的距离为d，则

（2）将排序后的簇头节点依次加入中继节点集合.设CHj是当前需要选择中继节点的簇头，它可以选择的所有中继节点的集合为Choice（j），在Choice（j）中利用多跳路径权重Wch（Choice（j））选择中继节点，

其中：REST为剩余能量权重因子，EChoice(j)-rest为可选中继节点的剩余能量；EDChoice(j)-dis为可选中继节点在路径上的能耗.中继节点选择完毕后按照类似CH1的方式记录CHj的路径信息.

由权重公式（18）可知，节点的剩余能量越大，路径传输能量越小，则权重因子越大，即成为簇头节点的概率越大.

（3）检查簇头节点是否需要更换中继节点，当簇头节点挑选完中继节点后，计算每个簇头节点直接与基站通讯的能耗是否小于使用中继节点的总能耗ECO（CHj，Choicej），若小于则直接将当前节点的中继节点更换为基站.

（4）检查多跳路径是否构建完成.

上述构建多跳路径的流程如图6所示.

图6 多跳路径构建流程Fig.6 Build process of Multi-hop path

3.3.2 非簇头节点多跳路径的构建

根据簇头间建立多跳路径的方法，构建非簇头节点的多跳路径，先建立到达最近簇头节点的距离由近及远的节点集合，此时的簇头节点包括基站节点，这意味着基站也可以直接接收普通节点的信息传输，建立非簇头节点的中继节点集合，集合中包含基站及簇头节点，然后通过距离与剩余能量权重选择中继节点，并加入集合.

构建非簇头多跳路径的步骤如下：

（1）添加基站和簇头节点到非簇头中继节点集合，并记录路径信息.

（2）将非簇头节点依次加入非簇头中继节点集合.

（3）检查非簇头节点是否需要更换中继节点.

（4）检查非簇头多跳路径是否构建完成.

4 仿真实验与分析

使用Matlab软件进行仿真测试，将本文算法与LEACH算法和EAMMH（energy aware multi-hop multipath hierarchical）算法[9]进行比较.

4.1 仿真实验场景及参数设置

设计一个100 m×100 m的矩阵模型，模拟1 km2的农业湿度监测，初始设定100个传感器节点，记录和监测每个节点的转发数据量与能耗.手动设定路由协议，将模拟区域划分为10个小区域，并挑选出10个簇头节点，轮时设为20 s/round，节点初始能量设为0.1 J，其他参数设置同表1.网络执行一轮固定转发为一次数据通讯，当簇头节点能量低于50%时更换簇头，直到存活节点数量小于20.

4.2 算法性能比较与分析

区域内随机分布的传感器节点与基站位置见图7.

图7 节点与基站位置Fig.7 Locations of nodes and base station

图8给出了节点平均能量随着发送信息总轮数增加的变化情况.由图8可见，当工作25轮时，LEACH的节点平均能量已低于0.060 J，EAMMH的节点平均能量高于0.065 J，而本文算法的平均能量高于0.070 J.当工作50轮时，LEACH的节点平均能量已经接近0.030 J，EAMMH的节点平均能量低于0.040 J，而本文算法的平均能量接近0.045 J.当工作100轮时，LEACH的节点平均能量已经小于0.010 J，EAMMH的节点平均能量接近0.010 J，而本文算法的平均能量接近0.017 J.本文算法的节点平均能量明显高于其他2种算法，说明新算法提高了整个WSN的负载均衡，减小了转发数据的整体能耗.

图8 3种算法的节点平均能量Fig.8 Average energy of nodes of three algorithms

图9给出了死亡节点数随着工作总轮数增加的变化情况.由图9可见，在工作18轮、21轮和26轮时，LEACH、EAMMH和本文算法分别出现了第1个死亡节点，当工作50轮时，LEACH的死亡节点已经达到58个，其他2种算法的死亡节点接近30个.以上结果说明新算法延长了网络的生命周期，提高了能量的利用率.

图9 3种算法的死亡节点数Fig.9 Number of death nodes of three algorithms

为观察大数据传输的能耗过程，将节点初始能量调至0.5 J，节点数量增加至400个.对于LEACH和本文算法，图10给出了存活节点数随着工作总轮数增加的变化情况.由图10可见，LEACH的第1个死亡节点出现在工作约700轮时，本文算法的第1个死亡节点出现在工作约1 200轮时，而且本文算法所有节点死亡时的工作轮数超过LEACH约200轮，因此新算法明显提升了网络生命周期.

图10 大数据传输网络中2种算法的存活节点数Fig.10 Number of surviving nodes of two algorithms in large data transmission network

图11给出了LEACH和本文算法网络总能量的变化情况.由图11可见，LEACH和本文算法的网络总能量分别在工作约1 550轮和1 750轮时耗尽，这进一步说明新算法的能量利用率提升明显，传递了更多的节点信息.

图11 大数据传输网络2种算法的系统总能量Fig.11 Total energy of system of two algorithms in large data transmission network

5 结语

本文以WSN能量优化为目的，对多跳路由选择算法进行研究，在簇头选择的策略上加入剩余能量参数，并在多跳路由选择方面优化路径权重参数，通过仿真验证了新算法的整体系统能耗和能量均衡优于已有算法，一定程度上解决了簇头能耗较大，网络生存周期较短等问题.

本研究存在一定的局限性，即缺少减小冲突的实证研究.现有相关研究表明[11-14]，在簇头分配接收数据时隙问题上可以使用双射频分工方式或者同簇异频的方式，来减小接收簇头节点信息与向其他节点转发信息带来的数据冗余传输，在降低整个网络耗能的同时可以减少数据冲突.