基于HPSO的自适应路由节点优化部署策略

樊成鹏，张丽娜

(1.重庆华渝电气集团有限公司，重庆 400021；2.中北大学 信息与通信工程学院，太原 030051)

0 引言

近些年随着无线通信技术的不断进步，在各个领域中对于无线通信网络的应用不断增加，同时对于无线通信网络的技术研究也在不断发展。节点部署对于无线通信网络的成本，通信功耗，通信质量都有着不可忽视的影响[1,2]。好的节点部署策略可以使无线通信网络有更低的成本，更低的功耗以及更好的通信质量。

对于无线通信网络，其结构中包含了终端节点，路由节点及汇聚节点[3]。对于终端节点在网络中的位置，主要取决于终端节点所需要实现的功能。例如在农业物联网的节点部署过程中，对于温度监测终端节点的部署与光强监测终端节点的部署有不同的部署条件，其主要取决于农作物所处环境特点，即在部署过程中，此类终端节点部署的主要影响因素即实际应用的环境特点。无线通信网络中的汇聚节点主要功能是对于整体网络中的数据进行处理，相较于终端节点或汇聚节点，一般汇聚节点仅有1个或几个即可实现对全部网络内数据的处理，所以在一般的无线通信网络中，都是以汇聚节点的位置为中心进行其他节点的部署。

对于节点部署的过程，目前相关学者主要采用智能算法进行寻优，具体算法包括人工免疫算法(AIA,artificial immune algorithm)、遗传算法(GA,genetic algorithm)等。此类方法中节点坐标获取与功能划分或组网通信是分段完成的，无法同时将两部分协同寻优，也正由于此，此类方法的局限性趋于明显[4]。

一个完整高效的无线通信网络的设计，不仅仅在于节点间通讯功能的实现，更重要的是需要完善的、稳定的数据网络[5]。对于无线网络的设计，陈畅等针对网络能耗和寿命问题，通过对无线通信网络特征的多目标优化算法设计了一种传感器节点智能部署方法，但其方法仅通过调整组网通信规则，并未对节点部署有进一步优化研究[6]。吴海燕等通过优化图论方法实现光传感器节点的优化部署，但算法中限制条件及因素过多，虽算法达到理想的寻优结果，但算法效率降低[7]。陈欣等提出基于生物地理学优化算法的节点部署策略，算法优化后寻优效率改进，但该方法在节点数量变多时寻优精度下降[8]。但上述研究中对于节点的部署，均以提升算法寻优的效率或算法精度为优化目标，对节点的基础部署方法均未研究。宋伟奇等针对无线组网的能耗问题和数据拥塞问题，通过优化网络节点可靠性权值提出了一种网络节点的优化方法，但算法中权值需要每次针对特定应用背景进行设置，不具有通用性[9]。韦运玲等针对传感器网络特性而影响其寿命的问题，设计了一种基于自适应人工免疫网络算法的无线通信网络拓扑结构，虽延长了网络寿命，但该结构对实际传输应用背景过于限制[10]。Maheswari等通过分析F-SCH(Fuzzy based Super Cluster Head)方法，提出了一种利用模糊控制结合自适应结构提高整体网络节点的有效寿命的方法，但该方法需在超大规模传感网内进行应用[11]。

上述方法对于无线通信网络的部署策略都有一定的优化研究，但对于空间自适应节点的部署均未涉及[12-16]。同时上述方法的算法在优化过程以牺牲算法的准确性来提升算法效率。虽然目前已有众多方法用于优化无线通信网络，但在路由节点的控制上尚未有明确的优化方法[16-19]。本文提出一种基于优化混合粒子群算法(HPSO,hybrid particle swarm optimization,)结合自适应路由节点部署策略(ADS,adaptive routing node deployment strategy,)的路由节点部署方法。

1 算法模型

1.1 路由节点部署成本模型

相关学者对于无线通网络中的路由节点也有所研究[19]。本文针对无线通信网络中如何实现终端到汇聚节点所需部署最低成本的路由节点为算法寻优目标。其中路由节点部署成本主要包括部署的通信距离成本和节点组网关系功耗成本。其部署的总成本计算式如下：

P=α·Px+β·Pc

(1)

1.1.1 路由节点部署通信距离成本模型

路由节点部署过程中的成本，主要包含节点成本，部署后的通信功耗成本，节点部署成本即无线模块的基础成本与数量的积。通信功耗成本包括通信距离产生的成本及组网关系产生的成本。

无线通信网络中的组网可以分为一级通信关系和二级通信关系。一级通信关系即路由节点与路由节点间的组网和路由节点与汇聚节点间的组网。二级通信关系即终端节点与路由节点的组网。

节点间的通信距离计算式如下：

(2)

一级、二级通信关系单位距离的功耗分别是R1d、R2d，则，节点间距离为dx时，一级、二级通信关系产生的功耗如下式：

(3)

(4)

通信距离产生总计成本如下式：

(5)

1.1.2 路由节点部署组网结构功耗成本模型

无线网络中组网关系如图1所示。

图1 组网关系示意图

如图1中所示，组网节点结构主要包括汇聚节点、路由节点和终端节点[20-22]。通信结构主要分为一级通信关系和二级通信关系。汇聚节点仅与路由节点进行通信，本文假设每一个一级通信关系传输对于发送节点的功耗是R1si，接收节点的功耗是R1ri。每一个二级通信关系传输对于节点的功耗是R2si，接收功耗是R2ri。假设共计有n1个一级通信关系，n2个二级通信关系。

则该网络组网结构一级通信关系产生的功耗如下式：

R1c=ω1c·n1·(R1si+R1ri)

(6)

则该网络组网结构一级通信关系产生的功耗如下式：

R2c=ω1c·n2·(R2si+R2ri)

(7)

则该网络组网结构产生的总功耗如下式：

R=R1c+R2c

(8)

设组网结构一级通信关系单位功耗产生的成本是Pc1，二级通信关系单位功耗产生的成本是Pc2。则组网结构总计成本为：

Pc=ac·Pc1·R1c+bc·Pc2·R2c

(9)

路由节点部署过程中的成本，主要包含节点成本，部署后的通信功耗成本。

1.2 路由节点通信距离限制关系模型

本文在路由节点部署时，通信距离应满足数据发送接收双方节点最小通信距离限制，通信限制关系模型如下式：

Dh>Dr>Dz

(10)

即汇聚节点覆盖范围最大，其次是路由节点，终端节点通信距离限制范围最小。

1.3 路由节点通信限制关系模型

在进行路由节点部署时，对于一个节点，其所无线通信节点数是k，则：

对于一个汇聚节点，与其通信的节点数量如下：

0

(11)

对于一个路由节点，与其通信的节点数量如下：

0

(12)

对于一个终端节点，与其通信的节点数量如下：

kz=1

(13)

即每一个终端节点仅能和一个路由节点通信。

1.4 路由节点部署通信质量评价模型

无线通信网络中，对于通信质量的评估，本文通过自由空间损耗进行比较。自由空间损耗主要与通信频率和通信距离有关。在本文无线通信网络中，一级通信关系采用同一频率，二级通信关系也采用同一频率。故主要用通信距离计算自由空间损耗。

本文中定义每一个通信关系间的自由空间损耗如下式：

L=20lg(d+dL)

(14)

式中，dL是自由空间损耗常数。

2 算法设计

本文方法以ADS进行节点坐标部署，并采用优化HPSO进行部署迭代寻优，最终得到最低成本条件下的最佳部署结果。总体流程图如图2所示。

图2 路由节点部署总体流程图

2.1 优化HPSO算法设计

2.1.1 HPSO设计

本文中HPSO主要基于PSO并加入GA算法特性，使其在迭代过程中也具有交叉，变异等过程，从而更快速寻优。基于优化HPSO的流程图如图3所示。

图3 优化HPSO流程图

算法中，适应度函数计算式如下(在进行粒子种群进化时，适应度值越低则粒子越优秀)：

(15)

式中α为本方法中在计算适应度函数时限制的最高成本。K是适应度常数。

HPSO粒子更新表达式如下：

(16)

(17)

上式即在常规粒子群算法基础上，使惯性权重线性递减，随着迭代的进行，算法搜索越来越精确。

2.1.2 HPSO淘汰机制

本方法中采用基于优化HPSO结合ADS。本文HPSO在优化过程中，随着算法中各个粒子个体适应度值的不断趋优，在算法中采用了淘汰机制，如下式：

(18)

即子代适应度值优于父代时，子代保留，否则，子代淘汰。在本方法中的淘汰机制中粒子种群进化所需的淘汰比例式如下：

(19)

其中，W为每代中的淘汰比例，W0为淘汰个数最小阈值，n为当前迭代的顺序数；β用于控制在种群迭代过程中淘汰的数量随迭代顺序数变化水平；V为常数。

2.1.3 HPSO多样性补充机制

每一代粒子在淘汰过后，种群多样性迅速下降，本方法在下一代种群中加入按照一定淘汰比例的随机生成全新粒子，以补充种群多样性。

K=N·w

(20)

即在原有种群中加入P1到PK的个体，其中K与N的关系满足w的正比例关系。

2.2 ADS算法设计

本方法中，ADS主要采用建立当前节点可视空间范围的方法。在进行路由节点自适应部署时，从终端传感器节点开始，采取可视域确立下一节点的方法。从起点起依次进行操作，在部署完节点后每次与终点进行距离判断，当与终点距离大于阈值时继续部署，直至距离终点的长度小于阈值时将当前节点直接与终点相连接。ADS具体步骤如下：

1)初始化相关参数，根据实际通信能力确定通信距离阈值。

2)在起点处建立自适应节点部署可视域模型，确定算法内节点的空间可视域。

3)在已确立的可视域内建立可视域内节点选择模型，进行第一个路由节点的部署。

4)从起点依次进行所有路由节点的相邻部署。每次进行部署时，对当前节点与终点的距离进行计算。当此距离大于节点通信最大距离时，继续进行下一节点的部署。

5)当距离终点的距离小于最大通信距离时，则不再进行继续部署，当前节点即为最后一个通信节点。

2.2.1 自适应节点部署可视域模型

在已知当前节点部署坐标后，下一节点进行自适应部署过程时，需要在节点可视域内进行部署。路由节点的可视域如图4所示。

图4 节点可视域示意图

可视域范围如下式：

(21)

x2+y2+z2

(22)

即可视域内最远坐标小于节点有效通信距离。

2.2.2 可视域内节点选择模型

在已知当前节点部署坐标后，下一节点进行自适应部署过程时，需要在节点可视域内进行部署。

方法中通过当前路由节点与汇聚节点的坐标位置关系，先缩减可视域范围，并依据节点实际可部署范围建立可行点集。通过对可行点集内启发函数的计算，根据选择概率确定下一节点的坐标。缩小可视域范围如图5所示。

图5 节点缩小后可视域示意图

根据路由节点部署限制范围得到的可行点集原理图如图6所示。

图6 节点可视域内可行点集示意图

启发函数如下式：

H(i,j,k)=D(i,j,k)w1·S(i,j,k)w2·Q(i,j,k)w3

(23)

式中，D(i,j,k)代表当前节点到下一节点的距离，Q(i,j,k)代表下一节点到目标节点间的距离，S(i,j,k)计算式如下：

(24)

式中，di,i-1代表当前节点可视域和上一节点可视域重合的范围。在完成启发函数的计算后，选择概率计算方法如下;

(25)

由上式可以得到下一节点的具体部署坐标。

3 实验与结果分析

本文实验硬件环境为Inter®CoreTMi5-4210M CPU @2.60 GHz，运行内存16 G。采用Matlab仿真平台。

3.1 算法参数初始化设定

基于优化HPSO算法结合ADS的初始化参数设定如表1所示。

表1 算法参数

3.2 结果与分析

实验节点包括49个终端传感器和一个汇聚节点。部署区域为200*200 m范围，路由节点通信范围最大为75 m，汇聚节点最大通信范围100 m，终端节点最大通信距离50 m，空间路由节点部署如图7所示。

图7 空间路由节点部署图

在上述实验的基础上，本文分别采用ADS与GA和AIA与本文方法进行对比试验[23-24]。

3种方法进行三十次算法迭代后得到的通信距离变化过程如图8所示。

图8 通信距离变化过程图

由图8可得，3种方法在刚开始迭代时并未出现明显差距，随着迭代的进行，本文方法较其他两种方法通信距离更低，随着迭代次数的增加，本文方法的寻优精确度越来越高。

3种方法得到的一级通信关系、二级通信关系距离如图9所示。

图9 3种方法一级、二级通信关系图

由图9可得，较GA与AIA，本文方法的一级、二级通信关系的通信距离均是最小。

由表2数据可得，本文方法具有最低的自由空间损耗，即本文方法所部署得到的路由节点网络结构通信质量较好。

表2 3种方法实验结果

本文方法相较于GA和AIA，在保证通信质量的基础上，路由节点部署成本可降低8%～10%，算法迭代效率(寻优时间)可提升14%～33%。

4 结束语

近些年来，无线通信技术的不断发展，致使了无线通信网络的不断成熟。无线通信网络中，节点部署是影响其特性是否良好的关键因素之一。高效的节点部署可以降低网络成本，提高网络通信质量。节点部署的核心即是以已知环境作为条件进行最佳的网络结构寻优。对于一个无线通信网络，一般其汇聚节点位置最先确定，终端节点的部署主要取决于网络功能与环境间的相互影响，则需要进行部署的即为无线网络内的路由节点。

本方法首先用自适应性的节点部署顺序，将 HPSO进行初始化处理，并加入淘汰机制有效提高了整体算法的寻优效率。本方法较AIA和GA而言，降低了节点部署的成本条件下，提高了算法效率。同时本方法结果中通信负载大的路由节点较少，将总通信任务尽可能均匀分布，提高了节点寿命。