基于改进最小生成树的三维路由算法

崔颖，李巧珏，高山，陈立伟

哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001

无线传感器网络（wireless sensor networks，WSN）包含大量传感器节点和1 个基站（sink）节点，传感器节点分布在监控区域中采集数据，然后将数据上传到监控区域边缘的sink 节点，最后对数据进行分析。这些传感器节点收集、传输信息的过程中消耗能量，但由于它们采用电池供电，电池电量有限且不能被补充，所以能量的高效利用格外重要。合理的路由链路能够使网络能量利用率增加，延长网络寿命。无线传感器网络的早期研究主要是在理想二维平面中，但许多无线传感器网络的实际应用环境是在三维（3D）空间中，例如水下环境监测[1]、森林火灾跟踪[2]、精准农业[3-4]等。因此，研究三维无线传感器网络的路由链路具有重要意义。

早期基于二维无线传感器网络的研究有很多。低功耗自适应分簇路由协议(low energy adaptive clustering hierarchy，LEACH)[5]算法是最早的分簇算法，但簇头单跳传输至基站，簇节点消耗能量高，网络寿命降低。所以学者们提出了簇间多跳方式来减少簇头的能耗。孙爱晶等[6]采用多元素加权的路径评价函数，结合猫群算法求簇头的最优路由，减少了簇间的能量消耗，但簇内的能量消耗没有优化。廖福保等[7]和戴志强等[8]都使用了最小生成树方法求簇头至基站的多跳路径，使用了不同的多元素权重，但簇内的单跳都没有改进。Jin 等[9]提出基于路径树的多跳路由算法，簇头根据与基站距离从小到大顺序依次成树，形成簇间路由，也未改进簇内的单跳。以上算法使用智能优化算法或最小生成树算法对簇间多跳路由进行了改进，但都没有考虑从簇内单跳入手节约能耗。潘琢金等[10]在簇内路由中使用了最小生成树，这使得簇内节点的路由从单跳变成多跳，路由距离减小，节点消耗的能量减小，延长了网络寿命。但是其分簇时直接将网络分成了4 块，分簇过程中并没考虑其他信息，可移植性差。

近年来，三维的无线传感器网络逐渐成为研究热点。Somauroo 等[11]将基于链的路由协议（ power-efficient gathering in sensor information systems，PEGASIS）应用到3D 环境下，并且使用遗传算法代替了PEGASIS 中的贪婪算法进行链路的构建，同时结合了能量和距离选择C 簇头提高了网络性能，但簇内路由也并没有改进。Wang 等[12]提出了最小生成树和边缘相加运算的最优拓扑快速生成算法，求出三维最优刚性图，但权重仅由距离计算，没有考虑能量因素。Xu 等[13]提出了3D 无线传感器网络下的节能路由协议，对簇内路由进行了改进，减小了网络能耗，但没有考虑节点作为中继次数对簇内节点的影响。

基于以上问题，本文提出了基于改进最小生成树（improved minimum spanning tree，IMST）的三维路由协议（three dimensional routing protocol，3DRT）算法研究。

1 相关理论

1.1 网络模型

对所提算法以及仿真实验使用的网络模型做如下假设：

1）传感器节点随机部署在一个立方体区域内，每个节点都有全局唯一的标识号（identity document，ID）；

2）每个节点都具有相同的通信和处理能力；

3）每个节点都可独立地与基站通信，基站的位置已知且基站能量不受限；

4）所有节点部署后节点位置不改变，电池电量有限且无法充电；

5）节点可以根据信号强度得到自身的相对位置。

1.2 能量模型

网络相互间的通信采用自由空间无线通信能耗模型[5]，是根据节点间的欧氏距离d计算。能耗计算公式如下：

节点发送kbit 数据消耗的能量为

接收和融合kbit 数据消耗的能量分别为

式中Eda为融合1 bit 数据所消耗的能量。

1.3 K-means++算法

K-means++算法是对K-means 算法的改进，初始聚类中心不再是随机确定，而是选择距离上一个聚类中心更远的点作为下一个聚类中心。选出初始中心后，继续使用标准K-means 聚类。改进算法能够选出均匀的簇头，均衡网络能量。Kmeans++选取初始聚类中心的步骤如下：

1）随机确定第一个聚类中心；

2）更新每一个样本到已有聚类中心的最小距离；

3）根据距离大小确定每个样本成为下一个聚类中心的概率；

4）根据概率大小抽取下一个聚类中心；

5）重复步骤2）～4），直到选出K个聚类中心。

1.4 最小生成树算法

图1是具有N个顶点的带权连通图G，其中存在很多子图。如果某个子图中的任意2 个顶点既互相连通，又是树结构，那么子图G'叫做生成树。如果G'的各边权值之和最小，则G'为图G的最小生成树，如图1 中虚线即为G的最小生成树。

图1 带权连通图

最小生成树有2 种查找算法，分别为克鲁斯卡尔(Kruskal)算法和普利姆(Prim)算法，二者均为贪心算法。不同的是，Kruskal 算法对每个边按照权重大小进行排序，Prim 算法则是对节点进行操作。由于本文是寻找节点间的最优路由，所以采用Prim 算法。

Prim 算法步骤是随机从一个节点开始，找到这个节点相邻权重最小的边；将此边添加到这个节点上，形成一个集合；再从集合的节点中查找相邻权重最小的边，并添加到集合中；不断重复直到所有节点都在集合中。图1 中的具体步骤即为从b点开始，权重最小边为b-a，a的权重最小边为a-e，以此类推最后得到的最小生成树为b-ae-f-d-g-c。

1.5 CRITIC 算法

CRITIC (criteria importance though intercrieria correlation)是Diakoulaki 等[14]提出的一种客观权重赋权法，以对比强度和冲突性为基础确定指标的权重系数。对比强度表示同一指标在各个评价方案中的取值差距，以标准差的形式表现；冲突性是以指标之间的相关性为基础，如果2 个指标之间正相关强，则2 个指标冲突性低。计算权重时，对比强度与冲突性相乘后进行归一化处理，即可得到最终的权重。

2 基于改进最小生成树的三维路由协议

本文算法首先使用K-means++算法选择簇头，然后使用改进的最小生成树算法求出簇间和簇内的最优路由，最后进行数据传输。系统框图如图2 所示。

图2 基于改进最小生成树的三维路由协议系统框图

2.1 K-means++选举簇头

簇头既要接收、融合簇节点转发的信息，又要将信息传输出去，能量消耗大，所以引入Kmeans++算法，均衡选举簇头。利用其聚类中心相对距离远的特性，选出无线传感器网络中均匀分布的簇头，避免产生能量空洞。本文的初始簇头数是根据文献[15]中最优簇头数计算公式计算得到的，计算后的初始簇头数为10，且簇头数随着节点的死亡等比例减小。K-means++选举簇头具体步骤如下:

1）随机确定第一个簇头；

2）更新其他节点到已有簇头的最小距离；

3）根据距离大小确定每个节点成为下一个簇头的概率；

4）根据概率大小选择下一个簇头；

5）重复步骤2）～4），直至选出K个簇头；

6）计算每个节点到簇头的距离，并将其分到距离最小的簇头所在的簇中；

7）重新计算每个簇的中心（即属于该簇所有节点的位置的质心）；

8）将簇中心映射到距离最近的节点上，这些节点是此次迭代选出的簇头；

9）重复步骤6）～8），直至达到某个终止条件（迭代次数或最小误差变化），输出簇头。

2.2 基于优化最小生成树的三维路由协议

簇头选举完成后，对簇内及簇间使用优化的最小生成树路由协议。首先对簇头与簇内节点生成簇内路由树，然后对簇头与基站生成簇间路由树，最后进行数据传输。

2.2.1 簇间自适应单跳多跳

图3是基于最小生成树的路由示意，可以看出，节点e是经由簇头2 多跳至基站，然而根据式(1)、式(2)和sink 节点能量不受限的条件，能够看出单跳e-sink 的能耗小，所以最优路由应该是单跳而非多跳。由此对节点的能量传递消耗进行以下分析，找到最优路由的普遍结论。

图3 最小生成树路由示意

单跳情况时，节点传输能量消耗如式(1)，即节点e单跳至sink 的能量消耗为ETX，网络消耗能量也为ETX；当采用最小生成树多跳时，节点e多跳到sink，则节点e的能耗表示为

式中de,cluster2是节点e与簇头2 距离。簇头2 作为中继的消耗为

所以网络能量消耗为

距离公式为

式中de,sink是节点e与基站距离。由以上分析可知，满足ETX＜Eall即式(3)中的距离公式时，采用单跳传输。 但能量消耗是非确定多项式（nondeterministic polynominal，NP）难问题，几个节点间的分析并不能代表能量的总消耗，所以此处采用枚举法，取不同de,sink的值对网络分析，运行程序后得出的结果如表1。 可以看出， 当de,sink=20 时，第一个死亡节点轮数最大，所以当节点距基站距离小于等于20 m 时，节点单跳至基站。所以图3 中节点a、d、e均单跳至基站。

表1 单跳至基站距离与第一个死亡节点轮数

2.2.2 新权重与权重系数的计算

文献[10]使用的最小生成树算法的权重只考虑距离这一因素，但无线传感器网络中影响寿命的元素很多。由上节分析可知，作为中继的节点能耗高，因此本文在旧权重的基础上，加入能量与跳数，求出最优路由，减少能量消耗。新权重表达式为

式中：wi是节点i的总权重，wenergy,i、wdist,i、wneighbor,i分别为节点i的能量权重、距离权重和跳数权重，r1、r2、r3分别是能量权重、距离权重和跳数权重的权重系数。

式中：D为N×N维矩阵，代表两两节点间的距离，N为节点个数；e，n为1×N维矩阵，分别代表节点的能量、节点作为中继的次数；dij为节点i与节点j欧式距离，ei、ni分别为节点i的能量、节点i为中继的次数；max、min 分别为求最大最小值的函数。

2.2.3 CRITIC 计算权重系数

初始时由于能量差值小，所以赋值权重系数为等值，即1/3。但随着网络运行，节点的剩余能量减小，能量差值变大，其权重系数应该增大。为了调整权重系数，在一定轮次后重新计算权重系数，本文每100 轮后对权重系数重新判断。重新判断的依据为

式中：Em为前m轮消耗的总能量，m为经过的轮数，Er为当前第r轮消耗的能量。如果当前能量消耗大于之前的平均消耗，就将该轮的能量、距离和跳数作为CRITIC 的输入，重新计算权重系数。首先将能量、距离和跳数的数据标准化，其中能量是正向指标，距离和跳数是负向指标；然后计算对比性和矛盾性得到信息承载量，其中对比性由标准差表示，矛盾性用皮尔逊相关系数表示；最后由信息承载量归一化求出权重，回代式(4)得到权重公式。

2.3 算法复杂度分析

假设初始化阶段网络中共有N个节点，簇头数为k，算法复杂度分别从簇头选举和路由选择2 个阶段进行分析。在簇头选举阶段，Kmeans++算法迭代次数为M，节点数为N，簇头数为k，复杂度为O(MNk)，化简后为O(MN)；在路由选择阶段，节点数为N，簇头数为k，簇间多跳复杂度为O(k2)，簇内多跳复杂度为O((N-k)2)，因此该阶段复杂度为O(N2+2Nk)，化简后为O(N2)。因此，每轮的复杂度为O(N2+NM)，等于O(N2)，复杂度等同于算法执行所需要的基本运算次数，即所提算法每轮可以在O(N2)次的运算中得到结果，算法可行。

3 仿真分析

利用表2 中的仿真参数对提出算法进行Python 仿真以评估其性能，并在相同三维环境下对LEACH[5]、基于最小生成树的非均匀分簇路由协议(mst2017)[7]以及基于K-means 聚类的无线传感器网络WSN 能耗均衡路由算法KBECRA[16]进行仿真对比。

表2 仿真参数

3.1 网络寿命分析

图4是在相同三维环境下不同算法网络中存活节点随轮数变化的对比，网络寿命可以用第一个死亡节点轮数代表。表3 给出了具体的死亡节点轮数，其中RFND为第一个节点死亡的轮数，RHND为一半节点死亡的轮数，RAND为所有节点死亡的轮数。

表3 不同算法网络中传感器节点死亡轮数

图4 不同算法网络中存活节点数对比

由表3 可以得到，IMST_3DRT 的RFND分别比3D-mst2017、 3D-KBECRA、 3D-LEACH 提高了12.5%、7.0%和30.6%，RHND分别提高了15.0%、27.9%和31.9%，RAND分别提高了52.4%、70.8%和41.6%。因为IMST_3DRT 采用簇内多跳，其簇内节点数据传输的距离减小、能耗也减小。而且多跳路由时，父节点接收子节点的消息，代替簇内单跳时簇头接收簇内所有节点消息的情况，均衡了簇内节点能耗，延长了网络寿命。

3.2 能量消耗分析

图5是网络的剩余能量随轮数变化对比，与3D-mst2017、3D-KBECRA、3D-LEACH 这3 种算法比较，IMST_3DRT 的剩余能量依次提高了22.1%、31.5%和38.9%。因为所提算法簇内多跳时，下一跳节点由能量、距离和跳数的加权和决定，当能量消耗变大时，权重系数根据当前参数重新计算，所以网络的利用率增加，减少了能量消耗，延长了网络寿命。

图5 不同算法网络剩余能量对比

3.3 吞吐量分析

吞吐量是直到最后一个节点死亡时网络传输的数据量总和。图6 是3 个场景下吞吐量的对比，3 个场景的节点数都为100，仿真范围依次是边长为70、100、125 m 的三维立方体。可以看出，3 个场景下吞吐量的变化趋势相同，IMST_3DRT＞3D-mst2017＞ 3D-KBECRA＞3D-LEACH。因为随着网络寿命增长，传输的数据量也增加，所以其趋势与寿命长度呈正相关。因而可以得出结论，改进的最小生成树路由效果大于簇内单跳。

图6 不同场景吞吐量对比

3.4 时延分析

传播时延由信道长度除以电磁波在信道上的传播速率得到。图7 是3 个场景下时延的对比图，场景与3.3 节相同。由图7 可以看出3 个场景下IMST_3DRT 的时延最小。在场景1 下，其他3 种方法时延大致相同；在场景2、3 下的时延：3D-KBECRA≥3D-LEACH＞3D-mst2017。 因 为IMST_3DRT 簇内使用改进最小生成树的生成路由，簇内节点的传输距离减小，时延也减小，而3D-mst2017 是基于最小生成树的簇间多跳，因此小于簇间单跳的3D-KBECRA 和3D-LEACH。

图7 不同场景时延对比

4 结束语

目前，三维的无线传感器网络广泛应用于实际环境，本文针对簇内节点单跳能耗大的问题，提出了基于改进最小生成树的路由协议，该算法能够减少簇内节点能耗，延长网络寿命。该算法使用K-means++算法选举簇头，保证簇头均衡分布。数据传输时，簇间路由将近基站节点单跳至基站，减少了中继节点的能耗，簇内使用改进的最小生成树路由协议，减小了簇内节点的传输能耗。计算权重时引入了能量和跳数，系数采用CRITIC 算法，利用各个要素之间的相对关系求出更合适的权重系数，选举更均衡的下一跳。仿真分析结果表明，相较于其他比较算法，本文所提算法能够减少能耗，延长网络生命周期。

本文研究发现，距离近的节点会产生大量重叠信息，增加网络能耗，在以后的工作中，可以加入调度算法进行研究。