基于和声搜索的能量有效路由算法

王宝亮，彭 程，李 科

(天津大学 电气自动化与信息工程学院，天津 300072)

0 引 言

随着物联网技术的飞速发展，越来越多的环境需要提供实时检测。无线传感网络(wireless sensor network，WSN)通过在布控范围内按需分布不同种类的传感器节点，实现对环境信息的收集。由于环境的不确定性，节点部署后往往得不到进一步的能量供应，这就要求网络有一定的自组织能力，避免能量黑洞的出现。

路由搜索问题属于一种典型的NP-Hard问题，目前，解决这类问题更多的是使用元启发算法[1]。国内外众多学者大多将焦点集中在遗传算法(GA)[2]、和声搜索算法(HS)、蚁群优化算法[3](ACO)及粒子群优化算法(PSO)[4]等等上。这些算法在解决实际问题时，往往针对不同的应用场景，结合具体的问题进行开发设计，没有统一有效的解决方案。

本文基于以上研究背景，选择和声搜索算法作为基础算法，提出了能有效延长网络运行时长的路由搜索策略。该算法相比之前同类算法，更加侧重提高WSN网络使用过程中边缘节点的参与度，在传统HS算法的基础上，结合全新的和声记忆库路由编码方式，引入更为有效分段式目标函数，同时在路由选择后期加入节点移除策略和角度偏移方法，进一步提高WSN运行后期边缘节点的使用频率，一定程度上延长网络的生命周期，可以获得较好的能量均衡效果。

1 相关工作

文献[5]提出了一种基于能量效率的和声搜索路由算法(EEHSBR)，其规定了路由传输的基本环境和限制条件，并使用传统的和声搜索算法进行分析实现，为HS算法的使用提供了一种全新的解决方案。文献[6]在EEHSBR 算法的基础上，更换了和声记忆库的编码形式和路由的生成方式，同时删除了部分冗余的参数，引入新的目标函数，提出一种IHSBEER算法。该算法总体来说兼顾了能量消耗和路径长度，但在网络使用后期，一味考虑路径长度会使节点的剩余能量差距明显，网络运行期间过于依赖于主要节点，使其能量迅速降低。

经典的HS算法具有较强的全局搜索能力，逻辑较为简单，控制流程的参数较少[7]，HMCR和PAR的配对使用可以解决大多数的问题。HS算法主要用于处理连续值的优化问题，无论是和声记忆库(harmony memory，HM)的生成还是微调阶段的处理，得到的值均为连续的。而路由的寻址问题上，节点分布是随机的，路径的选择是离散的，每个节点拥有唯一的ID编码[8]。无论是节点的选择，还是路径的选择都是离散分布的问题。因此，针对WSN路由问题的特点，经典的HS算法需要进行如下改进：

(1)新的路径以路径组Xi的形式保存在HM中

Xi=(s,x1,x2,x3,…d)

(1)

每条路径的第一个值为源节点s，最后一个值为目的节点d(即sink节点)，中间依次存放下一跳节点的信息。

(2)HM的维数不再统一为某一固定值，新路径的长度允许不同，HM中存放着有限条由源节点到目的节点的通路集合

(2)

(3)根据新路径的长度及其能耗情况设置相应的目标函数[9]，生成的新路径都需要经过目标函数的判断来决定是否可以使用。

(4)HMCR的取值不再固定，采用自适应的HMCR，避免引起早熟现象。

2 本文提出的算法

在这一节中，首先介绍了算法适用的系统模型，然后简述信息传递过程中使用的能量传输模型[10]；最后在经典HS算法基础上，详细介绍本文提出的BTPHS算法。

2.1 系统模型

本文算法在设计时，主要针对无后续能量补充的大范围部署节点的使用环境。因此对传感器节点的分布和使用情况做出如下约定：

(1)在M×M的有限区域内随机分布N个传感器节点；

(2)传感器节点确定后，不可随意移动，不可中途充电，且各个节点的初始能量相同；

(3)sink节点回收所有监测信息，具有不间断的电源供应，同时还具有一定的计算能力与存储空间，以便执行复杂的路由选择算法；

(4)各个节点间传递信息的过程均遵循能量传输模型；

(5)所有节点可检测本身的剩余能量，并拥有唯一标识ID。

2.2 能量传输模型

本文采用文献[11]提供的近似能量模型来估计信息传递过程中的能量消耗。节点能耗主要受数据包长度、节点间距等主要因素的影响。假设在一个基本的无线信道中，发射机或接收机的能耗系数为Eelec,发射放大器的能耗系数为Eamp。通信能耗模型如图1所示。

图1 通信能耗模型

节点在工作时，信息收集、数据收发、热量损耗等都会消耗能量，其中信息的传输所消耗的能量占据绝大多数。因此，在通信耗能模型中，只考虑通信过程中产生的能量损失。

通信过程中若将l比特数据传送至d米处，节点发送能耗为

ETx(l,d)=Eelec·l+Eamp·l·d2

(3)

节点接收能耗为

ERx(l)=Eelec·l

(4)

两节点间的能耗总和为

E(X)=2Eelec·l+Eamp·l·d2

(5)

2.3 本文的改进

如前所述，基于WSN的路由特性，新路径的生成与和声记忆库的储存形式都进行了相应的变化。为进一步平衡网络运行过程中能量的分布问题，本小节提出了一种侧重网络运行后期能耗均衡的BTPHS算法。该算法主要有3点改进策略：交叉变异、角度偏移方法及节点移除策略和分段式目标函数。

2.3.1 交叉变异

为了使交叉变异操作更容易理解，本节给出如下定义：

在HM中存在两条不同的路径Xi、Xj，若两个不同的无线传感器节点u、v同时存在于Xi、Xj中，则称节点u、v为一组扭转节点。

HS算法执行前期，搜索的范围较广，生成的路径线路普遍偏长，算法执行时间必然增长。这一改进策略在现有优秀和声的基础上进一步生成新和声，同时可以保证线路的多样性。交叉变异环节交换HM中两条已知线路的一部分，进而生成两条新的线路。具体而言，首先确定一组扭转节点；接着在两条线路中分别选定扭转节点间的线路段；然后交换线路段组成新的路由线路。

从图2中可以找到HM里存在的两条线路

图2 交叉变异过程

(6)

首先，确定一组扭节点(18,24)；选定两条线路中扭转节点间的路径并进行交换，得到两条全新的路径

(7)

由该操作产生的新路径不仅兼顾到HM中和声的优异性，同时不再进行算法的循环操作，缩短算法时间的同时，保障了新和声的多样性。

2.3.2 角度偏移方法和节点移除策略

节点部署后由自身的电池进行供电，存在严格的电量约束，为此在路由算法设计时，需要平衡网络的能耗需求。特别是在网络运行后期，关键节点不同于边缘节点，参与多次的信息传送任务，能量消耗较多。因此，BTPHS算法的主要思路是：提高循环后期边缘节点的使用频率，降低关键节点的曝光率。

文献[12]提出了一种改进算法，该算法在整个网络的运行阶段中，下一跳节点的生成策略主要考虑了邻居节点的剩余能量情况。因此，不均衡的能量分布仅仅体现在当前节点的邻居节点中，没有更好地体现全局能量的分布特点。为了考虑到网络整体能量的影响，BTPHS算法根据网络中实时最小能量Emin的大小，将整个网络的生命周期分为3个阶段，每个阶段在使用HS算法进行下一跳节点选择时，采取不同的节点选择策略(网络初始阶段每个节点拥有的初始能量值均为E0)。

策略1：当Emin的值介于[0.3E0,E0]时，整个网络的能量较为均衡，处于网络运行前期阶段，下一跳节点在选择时，采用经典的轮赌法进行。轮盘构成来源于邻居节点当前能量在总能量中的比例。在此阶段，该策略可以迅速识别当前网络的主干道，便于后续的分支使用。

策略2：当Emin的值介于[0.1E0,0.3E0]时，网络中能量开始出现一定程度的偏差，处于网络运行中期阶段，下一跳节点在选择时，采用角度偏移方法。利用角度偏移法选择节点i的下一跳的具体步骤如下：

首先确定源节点s和sink节点d的具体坐标(xs,ys)、(xd,yd)，并生成一个指向节点d的主干向量D，D计算规则如下

(8)

统计节点i的所有邻居节点的个数记作N0相应的坐标(xt,yt)，组成坐标集；以节点i的坐标(xi,yi)为始，依次计算指向坐标Pt

Pt:((xt,xi),(yt,yi)),t=1,2,3,…,N0

(9)

计算N0个指向坐标Pt与主干向量D之间的夹角θ，θ值的大小由其对应的余弦函数值进行控制，其计算规则如下

(10)

在系统模型的前提下，节点的分布具有随机性，故θ值也是随机的。余弦函数值的大小与偏离角度是一一对应的关系，当偏离角度超过90°时，余弦函数值会出现负数的情况，此时，信息可能会造成回传的情况。因此，需要终止此次偏移。主干向量方向上的节点用于传输信息的频率较高，剩余能量普遍较低。BTPHS算法通过控制θ值的大小，干预下一跳节点的选择方向，在下一跳节点选取时，偏离主干向量方向，增加边缘节点的曝光率和参与度。

策略3：当Emin的值介于[0,0.1E0]时，网络中能量差距已经很大，处于网络运行后期阶段，下一跳节点在选择时采用节点移除策略。该策略的基本思想如下：

网络的容错率在每一个时段都是不同的，并且每个阶段都有可能因为评判机制的不同而造成更大的能量差距。网络运行的截止标志为网络中首次出现节点能量为0的时刻，因此，当下一跳节点濒临死亡时，BTPHS算法进行选择性删除。在下一轮选择时，若节点p的当前能量值低于0.1E0，本算法将节点p进行暂时删除，使其不进入下一次的选择范围[13]。删除节点的个数同样需要限制，删除节点过多，会导致出现信息无法传输到目的节点，因此，删除节点的总数不能超过0.2N。

2.3.3 分段式目标函数

目标函数是整个BTPHS算法的最终评判目标，路径选择成功与否很大程度上取决于目标函数的筛选过程。目标函数在选择时，需要衡量多个因素，来保证整个搜索过程向最优解的方向逐步靠近[14]。列入衡量的因素包括：新路径的长度L(即信息传递过程中途径节点的个数)、路径的节点平均剩余能量E(X)、全局最小能量Emin等。不仅如此，针对网络中不同阶段的能量分布特点，目标函数也需要进行相应的变化，来保证整个网络向良性方向发展。根据2.3.2节提到的3个节点选择策略，BTPHS算法将目标函数分为3个不同的部分进行分段判别，如式(11)所示

(11)

在网络运行前期，BTPHS算法主要侧重于生成路径长度短、能耗相对较少的路由路径，尽快组成最优和声搜索库；在网络运行中期，部分节点能量损耗较为严重，BTPHS算法在选择线路时，开始有意识地避开这些节点，生成的线路不再刻意要求长度最短，但依旧要保证整体网络的能耗水平较低；在网络运行后期，个别节点已经处在能量耗尽的边缘，生成新路径的过程中，这些节点已经被视为死亡节点，新路径的长度必然会增加，此时，BTPHS算法再衡量新路径标准时，不再考虑路径长度L的因素。显然，根据式(11)表述的数学意义，路径长度越短、路径平均剩余能量和网络最小剩余能量越大，目标函数值越大，符合这些特征的路由方案越容易保留下来。

综上，BTPHS算法的算法流程如下：

BTPHS算法：

输入：节点分布坐标及能量信息

源节点s

目的节点d

输出：当前最优路径R

初始化：HM HMCR R rand Tmax

(1)fort=1,2,3,…,Tmaxdo

(2)while路由线路未达到d

(3)ifrand

(4)then下一跳节点从HM中选取

(5)else下一跳节点从邻居节点中选取

(6)endif

(7)ifEmin>0.3E0

(8) 下一跳采用轮赌法进行选取

(9)elseifEmin>0.1E0

(10) 下一跳采用角度偏倚法进行选取

(11)else下一跳采用节点去除法进行选取

(12)endif

(13)endwhile

(14)if新路径Routing优于HM中的任意一条

(15) 更新HM

(16)endif

(17)endfor

(18)R←Routing

(19)ReturnR

3 实验部分

本节给出了BTPHS算法的仿真实验结果。仿真软件使用Matlab 2018a，运行设备为Mac mini 2014，2.6 GHz Intel Core i5，内存为8 G。根据有效通讯半径，随机生成8个不同的节点分布场景。场景中的节点数量从10个依次递增至80个，增量为10个节点。为验证BTPHS算法的可行性，实验部分引入两种同样基于和声搜索算法的对比算法EEHSBR、IHSBEER进行比较。对于每个实验场景，测试环节均使用两个指标来评价算法的表现：网络寿命(即网络中第一个节点死亡时发送信息的轮数)和平均剩余能量(网络中所有节点能量的平均值)。

为了更加全面验证BTPHS算法的可行性，在数据传输环节，本文模拟设计了两种不同的发送形式：固定节点持续发送和全节点循环发送。

固定节点持续发送：所有传感器节点拥有相同的初始能量，数据包均从某一固定节点发送至sink节点。

全节点循环发送：所有传感器节点拥有相同的初始能量，每个传感器节点定期向sink节点发送数据包。

相关参数见表1。实验结果均为模拟进行20次得到的平均值。

表1 参数设置

3.1 节点调度测试

本节实验测试的内容主要针对2.3.2节所提出的角度偏移及节点移除策略。在8个不同的节点分布场景中，测试算法在全节点循环发送过程中节点的活跃程度。节点活跃度反映了节点在WSN中的使用频率，界定标准采用当前节点的剩余能量值。剩余能量越低，节点在网络使用过程中消耗的能量越多，该节点的频率越高，即节点的活跃度越高。本文选定3个不同的剩余能量阈值进行3组对比实验，测试条件如下：

测试A：网络死亡时，剩余能量不足E0的；

测试B：网络死亡时，剩余能量不足0.9E0的；

测试C：网络死亡时，剩余能量不足0.8E0的。

结果如图3～图5所示。角度偏移及节点移除策略的主要目的是尽可能多地利用边缘节点进行传输。在WSN中，信息传递主要依赖于主干道上的节点，考虑到传播时效，生存成本等因素，边缘节点的使用很难完全替代主干道上的传感器节点。测试A表示在整个网络生存过程中，所有参与节点的个数情况，此时只要节点参与传输信息，即被统计在内。

图3 测试A下的节点活跃度

图4 测试B下的节点活跃度

图5 测试C下的节点活跃度

图3可以看出，3种算法在节点数较少的环境下表现基本持平，当环境中的节点个数增多时，BTPHS算法调动的节点明显增多。

图4和图5可看作边缘节点的轻度、中度使用行为。剩余能量可以快速衡量出节点是否多次参与网络传输，剩余能量阈值降低，筛选出的节点活跃度越高。两种情况下BTPHS算法的表现均优于EEHSBE算法和IHSBEER算法，这是因为2.3.2节提出的改进策略在生成信息传递路径时，下一跳节点的选择为边缘节点提供了更多的可能性，增大的边缘节点的曝光率。图3～图5显示的3组实验结果进一步验证了角度偏移及节点移除策略的可行性。

3.2 固定节点持续发送下的实验结果

图6和图7分别显示了两个指标在8个实验环境中的对比情况。两幅实验对比图中的横轴表示不同规模场景下的传感器节点个数，图6的纵轴表示网络的生命周期(当出现能量黑洞时，网络一共循环的信息传递轮数)，图7的纵轴表示平均剩余能量。

图6 网络寿命对比

图7 平均剩余能量对比

从图6的结果可以看出，BTPHS算法在部分场景中体现出了最好的结果，特别是在节点数目较大的环境中。WSN范围内节点数目越多意味着节点间的路由关系更复杂，每个节点邻居路由的数量也会相应更多。因此，在网络循环的后期，WSN网络的抗风险性就会越大，人为删除疑似死亡节点后，网络依旧可以生成可行的路由方案，进一步延长网络的使用时间。

对比图7可以看到，基于和声搜索的3种不同的算法在剩余能量的控制上差别不是很大，从这一点可以得出，和声搜索算法适于解决NP-hard问题。剩余能量相差不大表明，在该环境下，3种算法生成的路由方案在总体能耗表现上较为平衡。较高的能量剩余意味着较低的能量成本，IHSBEER算法的优化，降低了网络工作期间的平均能量算耗。BTPHS算法着重使用边缘节点，在算法循环后期，牺牲路径长度，提高边缘节点的曝光率，路径总能耗随即增加，符合算法最初的设计逻辑。故在平均剩余能量表现方面，BTPHS算法在大部分的实验场景中，均略低于IHSBEER算法，这一现象表明，BTPHS算法在均衡能量方面表现更为优秀，在现有能量环境下，可以更多利用曝光率低的节点进行工作。

3.3 全节点循环发送下的实验结果

图8和图9分别显示了两个指标在8个实验环境中的对比情况。

图8 网络寿命对比

图9 平均剩余能量对比

从图8中可以观察到，在8种不同的节点分布环境下，BTPHS算法的表现依旧突出。节点分布范围更大，节点总数更多，但单位面积内节点的分布密度却变小。从测试数据可以看出，BTPHS算法获得的轮数有着显著提升，特别是在50节点的测试环境中，相比EEHSBR算法提升12.9%，相比IHSBEER算法提升5.52%。BTPHS算法中的交叉变异环节，可以在网络运行后期，通过扭转节点对路径的切割与拼接，实现路径的大范围变化，从而有效避免濒临死亡节点的利用。图9显示的测试结果大体与固定节点持续发送横式下的实验数据相似。

随着网络面积增大，节点密度降低，BTPHS算法向sink节点传输相同大小的数据包时，消耗的能量偏多，维持的轮数相比其它算法有进一步的提升，这一测试结果验证了BTPHS算法的可行性。

3.4 结 论

从两种测试环境的对比情况可以看到，BTPHS算法在节点较多的环境中，表现尤为突出。在能耗损失方面略输于EEHSBR算法和IHSBEER算法，与此同时，由于角度偏移方法和节点移除策略的引入，使得边缘节点进入路由方案的概率有所提升，进一步分担主干路上节点的使用频率。目标函数从单一的评判标准更新为三段式评判，保证BTPHS算法在不同阶段选择出当下最优的转发路径。在保持网络能量效率的前提下，可以提高网络的可拓展性。对于当前的大多数应用，如智能家居、工业和制造自动化等，节点的数量较为中等，结合Matlab的仿真结果可以得出，BTPHS算法在路由选择领域有广泛的发展前景。

4 结束语

本文提出了一种基于和声搜索的能量路由算法BTPHS，该算法以HS算法为基础，生成新的路由方案，并根据目标函数不断优化和声库中的路由路线，从而不断产生最优解。该算法主要思想是提高边缘节点的参与度，通过角度偏移方法和节点移除策略不断降低主干道节点的使用频率。经检测BTPHS算法生成路由方案，可以进一步平衡能量分布情况，还能一定程度上延长的网络的使用周期。但BTPHS算法在运行时长上依旧有提升的空间，同时，节点移除策略的引入，使得网络可能造成回路、短路现象，后续还需要进一步完善。