基于伪随机因子修正与爬虫机制的无线传感网路径生成算法∗

赖 玲，谢娅娅

(1.荆楚理工学院计算机工程学院，湖北 荆门 448000；2.荆楚理工学院，电子信息工程学院，湖北，荆门 448000)

无线传感网(Wireless Sensor Network，WSN)技术作为“中国制造2025”重要组成部分之一，正在工业化4.0 进程中起到举足轻重的支撑作用[1]。该技术主要采取自组织模式在一定地域内部署成本低廉的传感节点，通过传感节点进行数据采集、汇聚、传输至sink 节点，最终实现对某一空间分布区域内客体实现自主控制及数据感知，从而节约人力、物力并充分提升现有基础设施的服务支撑能力[2]。由于传感节点均采取无线通信方式，多部署在环境较为恶劣地域，若节点出现物理性损耗或能量受限，整个网络的数据采集将会受到严重影响[3]。此外，无线传感网多采用一次布撒成型的自组织部署模式，若某些节点及路径因传输过载而导致能量消耗过高，则将因能量受限而导致出现路径抖动，从而严重影响网络性能[4]。因此，采取一定措施降低节点能耗并优化网络传输路径，成为当前无线传感网研究领域的热点[5]。

针对无线传感网实际部署过程中存在的若干问题，研究者提出了一些具有前瞻性的无线传感网路径优化方案，如Gundabatini 等[6]提出了一种基于果蝇机制的无线传感网路径生成算法，将数据传输报文进行类型区分，尽量降低网络节点及链路负载，并将若干能量较低的节点及路径进行关闭处理，可显著抑制链路抖动现象，使其具有较好的节点休眠性能。但是，该算法也存在节点利用率较低的不足，在网络带宽负载较高时，其路径生成效果不佳，难以进一步降低链路抖动现象。Naim 等[7]基于网络分层结构，提出了一种利用k-means 机制的无线传感网路径生成算法，其主要对层次数据分组报文定义传输数据结构，引入跳数搜集及路径负反馈方案进行传输编码，通过能量优化方式进行全网路由统一调度，可显著降低因数据报文过载而导致路径抖动问题，使其具有较好的网络传输性能。然而，该算法在分层过程中需要频繁对网络节点进行层次分割，节点能量消耗水平较高，容易导致传输路径出现抖动现象。Seyedakbar 等[8]鉴于被动式寻径机制存在的网络拥塞控制困难的不足，提出了一种基于主动式路径搜寻机制的无线传感网路径生成算法，将节点剩余能量引入链路搜寻过程，采取平均能量最优准则裁决传输链路，优选能量较高的链路承担数据传输功能，可显著改善传输链路抖动问题，网络实时传输性能卓越。但是，该算法需要频繁进行网络节点遍历及能量排序操作，链路选取过程中对网络稳定性要求较高，使得算法在节点及链路出现抖动时存在路径生成效率较低的不足，难以适应较为复杂的网络部署环境。

针对当前研究中存在的不足，提出了一种基于爬虫机制的无线传感网路径生成算法。首先，按照节点能量及路径跳数部署诱饵，并根据诱饵最大化原则诱导爬虫来爬取剩余能量较高及传输跳数较少的节点，提高路径节点的传输性能，降低能量受限而导致节点失效。并引入均等分割方法，对网络区域进行栅格化处理，采取角度最小化原则来提高爬虫感知能力，有效降低因热点而导致节点出现受限现象，提升路径健壮性能。随后，通过评估节点剩余能量并引入回溯方式来构建伪随机因子修正机制，以均衡路径能耗，降低节点抖动频次。仿真实验证明了本文算法的性能。

1 本文网络模型

典型的无线传感网节点分布如图1 所示:节点分布为矩形区域，网络节点分为簇头节点(Cluster Head，CH 节点)和簇成员节点(Cluster Members，CM节点)。其中，节点采用随机部署模型，采用一次性布撒方式成网[9]。

图1 无线传感网节点分布

网络部署完成后，传感节点中源节点均需要通过搜寻中继节点(Relay 节点)，并通过中继节点将数据传输至sink 节点。考虑到传统被动式路径生成算法存在路径筛选效率较低的问题，本文采取基于爬虫机制的网络模型来进行数据爬取:将源节点设置为爬虫节点(Crawler)的初始位置，爬虫搜寻路径过程中，将根据网络节点能量及链路来设置诱饵，诱饵为节点能量和传输链路的加权平均，其余爬虫将根据诱饵的数量决定下一跳节点的筛选。网络在搜寻路径时，根据爬虫行为差异特征，将爬虫分为路径生成爬虫(Path Generation Crawler，PGC)和路径回退爬虫(Path Fallback Crawler，PFC)，其中。PGC拓扑移动的起点为源节点，PFC 拓扑移动的起点为sink 节点，见图2。

图2 爬虫网络模型

在图2 所示的爬虫网络模型中，设无线传感网在路径生成的起始阶段，整体网络节点个数为n，网络爬虫个数为m，第x个PGC 爬虫PGC(x)的起始路径为源节点，按模型(1)所示的概率择优选取中继节点。模型(2)表示PGC(x)对中继节点的期望，显然对于无线传感网而言，PGC(x)需要选取距离较短的节点作为中继节点。当PGC(x)经过多个中继节点并抵达目标节点后，将蜕变为路径回退爬虫PFC(x)，PFC(x)在从sink 节点回退到簇成员节点的过程中，将沿着诱饵最高的链路进行路径爬取，从而完成整个路径寻找过程。在此过程中，诱饵ω(t，i，j)将会按照 一 定速度逐步被蚕食。由于PFC(x)在回退过程中各节点剩余能量及链路传输质量会发生变化。因此，诱饵ω(t，i，j)也将因其余PGC 的影响而呈现衰弱态势。诱饵越多的路径将会有更高的几率被选定为传输路径，相应的诱饵数量会不断增加，传输质量较差路径的诱饵将不断散发，从而被选取为传输路径的概率亦将下降。其中，爬虫PGC(x)在选取中继节点时的概率P(t，x，i，j)为:

式中:x表示爬虫PGC(x)，i和j分别表示爬虫PGC(x)起始节点编号，ω(t，i，j)表示诱饵，ψ(t，i，j)表示爬虫PGC(x) 在从移动开始时的期望值。ω(t，s，u)表示网络中任意爬虫PGC 从节点s移动到节点u时的诱饵，ψ(t，s，u)表示任意爬虫PGC 从节点s移动到节点u时的期望值。L(i，j)表示节点i和j之间的距离，(xi，yi)和(xj，yj)分别表示节点i和节点j的坐标。a和b表示权重系数，

由模型(1)可知，爬虫PGC(x)在进行路径爬取过程中，将按照概率最大原则选取下一跳节点，并将距离因子按模型(2)赋予初始诱饵ω(t，i，j)。显然，当期望值ψ(t，i，j)较高时，说明爬虫与节点j间的距离较近，因此节点j将会有更高的概率被选举为中继节点。权重系数a越高，说明路径中能量因素占比也将越高；权重系数b越高，说明路径中距离因素占比也将越高。

此外，单纯按能量因素对诱饵ω(t，i，j)进行赋值可能存在能量受限的不足，因此，本文采取迭代模型对诱饵ω(t，i，j)进行处理:

式中:Δω(t，i，j)表示诱饵增加系数，Δω(t，x，i，j)表示爬虫PGC(x)在节点i和j之间爬取过程中的诱饵增加值，L(x，i，j)表示爬虫PGC(x)在节点i和j之间反复爬取过程中所遍历路径的总长度；t＋n表示本次诱饵经历n次爬取后形成的新诱饵。

2 本文无线传感网路径生成算法

由上文可知，采取模型(1)～模型(7)所示的爬取过程可在网络中初步建立起可用传输路径。但是，基于能量和路径因素，单纯采取爬取方式进行路径筛选将会存在如下三点不足:

①存在能量受限的可能性。无线传感网节点均需要通过无线方式进行数据传输，若爬虫完全按能量因素并采取模型(1)进行路径生成时，可能导致优质传输路径出现能量受限的现象[10]。

②网络拓扑出现空洞。无线传感网均采用自组织方式进行组网，爬虫进行路径爬取的过程也是网络拓扑更新的过程，若某节点因爬虫爬取频率过快，或者该节点与周围节点距离均较为接近，则将因节点能量失效较快而导致拓扑出现空洞，降低了所生成路径的传输性能[11]。

③中继节点的多跳性能出现下降现象。模型(6)基于爬取路径长度的方式增加诱饵量，虽然能够以较快速度积累诱饵，但诱饵量增加可能会导致路径以更高的频率被爬虫爬取，导致中继节点出现能量受限现象，从而降低了中继节点的多跳性能。

因此，针对单纯爬取方式生成传输路径存在的不足，提出了一种基于基于爬虫机制的无线传感网路径生成算法，其主要由基于栅格－角度机制的路径爬取激励和基于伪随机因子修正机制的节点转移概率更新两部分构成。

2.1 基于栅格－角度机制的路径能量爬取激励

考虑到爬虫PGC(x)主要按概率最大化原则并采取模型(1)来实现路径生成，而模型(1)所示的概率P(t，x，i，j)在频繁爬取过程中容易出现死锁现象，导致环路径的形成。此外，在任意时刻网络中的簇头节点和簇成员节点均存在休眠现象，当且仅当节点能量恢复完毕时将重新启动数据传输过程，会导致爬虫PGC(x)在进行路径爬取过程中将面临网络拓扑更迭较快的问题。此外，当爬虫PGC(x)爬取过程中出现下一跳节点缺失现象时，将会回退至起始位置重新进行路径爬取，从而导致节点能量消耗较快及爬取时间过长的不足。因此，为降低节点能量消耗并降低爬取时间，本文对网络进行栅格化分割，如图3 所示。

图3 网络栅格化分割

采用栅格化对网络区域进行分割后，可实现对传输路径的层次化评估，降低路径长度:在图3 中，网络按照栅格进行分割，其中栅格间距离为R。爬虫PGC(x)仅能选取H－1 和H＋1 两层节点进行路径爬取，与该爬虫相距在2R距离外的节点C、B将被抛弃，规避因传输路径过长而导致诱饵量下降的现象，改善节点能量受限概率。

但是，爬虫按栅格化网络进行爬取过程中可能存在多种选择，如图3 中的节点A1、A2、A3、A4均可作为下一跳传输节点。这是由于传感网具有节点密度较高的特性，使得节点个数较多，爬虫可供选择的下一跳中继节点将存在多样性。此外，若将邻域范围内节点确定为下一跳传输节点，也可能存在对sink 节点定位不足的问题，使得爬虫运动方向远离sink 节点，如图3 所示，爬虫若选取A1作为下一跳传输节点，将会出现远离sink 的现象，使得传输路径不断增长，降低了网络传输性能。

为降低传输路径长度，提高网络传输性能，进一步获取爬虫与各邻域内节点间的角度，如图4 所示，爬虫爬取过程中，优选角度最小的节点作为下一跳传输节点，此时爬虫对应爬取路径的性能要显著低于其他可用路径。

图4 按角度筛选下一跳中继节点

采取遍历模式对栅格进行处理，按角度筛选下一跳中继节点，虽然能够精确生成路径最佳的传输路径。但是，若某栅格内节点较多时将会出现多种选择，如图5 所示。对于sink 节点隶属栅格内的节点而言，因其均有可能承担最后一跳节点的传输任务，导致能量消耗量急剧上升。若节点能量耗尽，则整个网络传输路径将会受到严重影响，导致路径质量再次出现下降现象。为了降低栅格节点过载现象，本文基于栅格－角度机制，设计了一种路径能量爬取激励方法:方法对栅格内被爬取频次较多的节点进行标识，禁止其余爬虫对该节点进行爬取。此外，将能量剩余较高的节点增补进入路径，以便能够让栅格内节点有均等机会承担数据传输任务，从而降低网络平均能量消耗，增加网络生存时间。

图5 路径能量爬取方法

显然，对于图5 节点B1、B2、B3而言，若所处栅格区域内能量消耗较高，则按栅格－角度机制获取的角度及距离均无法对这三个节点进行区分。因此，爬虫PGC(x)在不断进行路径筛选过程中，将对某栅格内节点的剩余能量进行排序并筛选出能量最低的节点，记录其能量值为Emin(x)，并记录爬虫PGC(x)到该节点的跳数L(x)，按模型(8)来构建能量激励阈值EJL(x)，并通过该能量激励阈值进行路径爬取:

爬虫在下一跳节点选取过程中，优先选取模型(8)所示的能量激励阈值最高的节点作为下一跳节点。不过，同层次节点B1、B2、B3之间可能存在数据传输现象，见图6，在爬取过程中，爬虫将不断计算下一跳节点的能量激励阈值EJL(x)，具体工作原理见图6。

图6 能量激励阈值对路径的判定

在图6 中，不妨做如下假设:PGC(x1)，B2，sink为爬虫PGC(x1)的路径爬取结果，PGC(x2)，A1，B1，B2，sink 为爬虫PGC(x2)的路径爬取结果。当爬虫PGC(x1)和爬虫PGC(x2)同时抵达目的节点时，网络将按模型(8)记录爬虫PGC(x1)和爬虫PGC(x2)的能量激励阈值EJL(x1)和EJL(x2)，并按如下规则进行路径判定:

对于模型(9)而言，当且仅当某爬虫的能量激励阈值较高时，其爬取的路径将被选定为网络传输路径。

当路径选择完毕时，即爬虫PGC(x)最终抵达sink 节点后，由模型(1)～(7)可知，爬虫PGC(x)将蜕变为路径回退爬虫PFC(x)，导致诱饵ω(t，i，j)发生变化。为降低诱饵失效概率并引导爬虫以较快速率接近sink 节点，对诱饵ω(t，i，j)进行如下处理:

式中:i表示当前爬虫PGC(x)所处的节点，j表示爬虫PGC(x)拟爬取的下一跳节点，E(t，i，j)表示爬虫PGC(x)从i移动至j时所剩余的能量，Eall(t，i，j)表示路径上全部节点所剩下的能量，θ表示按栅格－角度处理后所选取的最小角度。L(i，j)表示节点i和节点j之间路径距离，L(j，sink)表示节点j与sink节点的路径距离。

PGC(x)对路径爬取完毕并按模型(10)更新诱饵后，将进入休眠状态，如图7 所示。

图7 基于栅格－角度机制的路径能量爬取激励

2.2 基于伪随机因子修正机制的节点转移概率更新

完成基于栅格－角度机制的路径能量爬取激励过程后，源节点与sink 节点间将建立数据交互关系，然而由于无线传感网节点具有的高密集度特性，使得爬虫难以实时获取各节点的剩余能量，特别是网络节点处于休眠状态时，爬虫对路径感知的能力将急剧下降，导致模型(1)所示的状态转移概率难以及时获取，因此sink 节点回溯至源节点的路径难以生成。针对该问题，本文设计了伪随机因子，用以提高爬虫PGC(x)对路径感知的能力，均衡路径上能量剩余较低且被爬取频次较高节点的能耗，进一步增强网络传输稳定性能。

针对当前爬虫PGC(x)，起点位置为i，下一跳节点位置为j，按如下模型获取伪随机因子Ω(i，j):

式中:E0(x，i)表示节点i的剩余能量，E0(x，j)表示节点j的剩余能量，E0(x)表示节点i的初始能量。

为进一步评估爬虫PGC(x)进行回溯操作时的概率，对模型(1)改写如下:

爬虫PGC(x)进行回溯操作时，下一跳节点筛选时优先根据模型(12)所示获取伪随机因子，并对模型(1)修正后再进行下一跳节点筛选，从而生成sink 节点回溯至源节点的可用路径。详细步骤如下所示:

Step 1 针对当前爬虫，首先获取节点剩余能量、节点初始能量、下一跳节点剩余能量，并记录当前所在节点位置和下一跳节点，如图8 所示。

图8 基于伪随机因子修正机制的节点转移概率更新

Step 2 按模型(12)所示构建伪随机因子，若同时存在多个可用下一跳节点，将同时计算并获取多个伪随机因子，转Step 3。

Step 3 按模型(1)重新生成并更新节点转移概率，仅仅选取更新概率最高的节点作为下一跳节点。

Step 4 逐次进行Step 1～3 过程，直到sink 节点至源节点的可用路径成功生成。

3 仿真实验

为便于对比本文算法的性能，设置NS2 仿真实验环境(Network Simulator Version 2，NS2)[12]。节点散布区域为矩形，大小为512 m×512 m；部署模型采取随机撒布模式，均采用sink 节点进行远程供电，位置不变，其余仿真参数见表1。为突出所提算法的优势，将当前常用的基于移动数据采集机制的无线传感网路径生成算法[13](Path Discovery Approach For Mobile Data Gathering in WSN，MDG-PDA 算法)和基于集成寻径机制的无线传感网路径生成算法[14](Ensemble Path Finding In Wireless Sensor Networks，EPF 算法)作为对照组。测试指标选取可用路径条数、节点受限比例、网络数据传输带宽三项。其中，MDG-PDA 算法一般用于需要高速传输数据且实时性较高的应用场景，例如车载网等方面。EPF 算法多用于立体传输场景，诸如无人机、战术数据链等方面。两种算法均在当前前沿领域有一定的应用。不失一般性，采用固定方式部署节点，部署区域为矩形，详细仿真参数表见表1。

表1 仿真参数表

3.1 可用路径条数

图9 为高斯信道和莱斯信道两种信道条件下，本文算法、MDG-PDA 算法和EPF 算法的可用路径条数测试结果。由图可知，本文算法具有可用路径条数较高的优势，这是由于本文算法针对无线传感网路径生成过程中存在的节点受限现象，将网络分布区域进行栅格化处理，基于角度优先原则确定中继节点，可显著降低传输路径长度，具有路径生成质量较高的特点。特别是本文算法针对部分中继节点使用频次较高的特点，在同栅格区域内采取能量激励阈值模式确定较低能量的节点作为中继传输节点，因而可显著降低因能量受限而导致路径抖动的现象，可用路径条数较多。MDG-PDA 算法主要采取移动sink 节点的方式搜寻可用路径，将路径切割为弦与线段之和，导致簇内路径跳数较高，使得该算法可用路径长度较长，进而使得中继节点使用强度要显著高于本文算法，路径因能量受限极易出现抖动现象，因而该算法的可用路径条数较低。EPF 算法采用非均衡聚类模式对网络区域进行划分，承担中继节点的簇头节点亦存在非均衡特性，使得节点能量消耗水平较高，特别是该算法按照时长反馈最短方式筛选中继传输节点，初始筛选的中继传输节点受限时易引发连锁受限现象，从而降低了该算法的可用路径条数。

图9 可用路径条数测试

3.2 节点受限比例

图10 为高斯信道和莱斯信道条件下，本文算法与MDG-PDA 算法和EPF 算法在节点受限比例的测试结果。由图可知，本文算法节点受限比例始终处于较低水平，显示了较高的路径节点爬取质量。这是由于本文算法除对网络分布区域进行栅格化处理从而减少路径重复选择，针对传输热点现象，采用能量激励阈值均衡化热点区域节点使用频次，因而降低传感节点被反复选取概率，节点较少出现因能量消耗过高而受限的现象。MDG-PDA 算法虽然采用分区机制，并结合边长切割方案初选簇内传输路径，由于该算法路径冗余度较高，使得传输拓扑较为复杂，中继节点同时被多个节点爬取的概率要显著高于本文算法，导致节点能量消耗水平较高，从而引发节点较易出现受限现象。EPF 算法考虑到簇头节点作为中继传输节点的重要性，优选时长反馈较短的节点作为下一跳节点，然而由于该方案未对簇头节点附近区域出现的传输热点现象进行处理，使得簇头节点易出现频繁的数据重传输事件，导致节点能耗水平高于本文算法，从而增加了节点受限比例，表现出了较为不稳定的数据传输性能。

图10 节点受限比例测试

3.3 网络传输带宽

图11 为高斯信道和莱斯信道条件下，本文算法、MDG-PDA 算法和EPF 算法的网络传输带宽测试结果。为不失一般性，本文将网络传输带宽规定为sink 节点接收的实时带宽。由图11 可知，本文算法执行过程中，同等节点传输率条件下能实现更高的网络带宽，体现了较好的网络传输性能。这是由于本文算法除通过栅格－角度机制优化传输路径之外，还采用能量激励阈值方式进一步降低网络传输热点现象，因而具有较低的节点受限现象。此外，本文算法设计了伪随机因子机制，均衡路径上能量剩余较低且被爬取频次较高节点的能耗，可实现逐点爬取能量较为均衡的网络节点，因而网络传输性能较高，体现了较高的网络传输带宽。MDG-PDA算法在采用边长切割方案生成簇内传输路径时，未对临近簇头附近的热点进行能量均衡化处理，节点受限现象较为严重，使得该算法的路径抖动情况要高于本文算法，网络传输带宽因而较低。EPF 算法虽然采用时长反馈最短机制对高负载进行均衡化处理，然而由于采用非均衡聚类模式对网络区域进行划分，使得网络节点传输流量亦呈现非均衡特性，导致节点负载程度要显著高于本文算法，降低了算法的传输性能，因而同等节点传输率条件下该算法占用的网络带宽要低于所提算法。

图11 网络传输带宽测试

4 结束语

针对当前无线传感网部署过程中存在的路径感知能力较差、节点及网络性能较弱等不足，提出了一种基于爬虫机制的无线传感网路径生成算法。通过对网络区域进行栅格－角度分割，设计了一种新的路径爬取激励方法。可优化节点爬取路径的健壮性能，均衡节点能量消耗及传输跳数，显著提高爬虫运动速度及路径生成效率。随后，通过评估节点能耗，设计了基于伪随机因子修正机制的节点转移概率更新方法，主要采取均衡路径能耗的方式，优选能量剩余较高且被爬取频次较高节点，进一步降低节点抖动频次，提升网络传输能力。

下一步，将针对本文算法在移动环境中性能较差的弱点，拟引入移动拓扑－频次自适应控制机制，提升爬虫对高拓扑更迭环境的适应能力，提升本文算法在节点移动场合下的部署效果。