基于病毒-抗体免疫博弈的WSN链路稳定算法

徐 锋,王 佶

(浙江大学 信息技术中心,杭州 310058)

0 概述

为提高无线传感器网络(Wireless Sensor Networks,WSN)在数据激增、吞吐受限等情景下的数据传输能力[1],研究人员提出了较多解决方案,主要从链路、能量、路由分区等方面,通过改进数据传输及节点分区方式,以提高WSN的数据传输质量[2-3]。路由分区解决方案主要分平面型和区域型两类[4],平面型方案需要大规模存储路由链路信息数据,难以适应超宽带网络环境下WSN的网络传输需求,区域型方案主要通过分层、分簇、区域分割等方式形成层次性传输结构,其具有较强的链路稳定性能。

在当前的WSN数据传输方案中,LEACH算法作为一种基本解决方案[5],主要采用簇状网络部署模式,结合更新机制稳定传输链路,最终改善网络能耗。但是,LEACH算法未能综合考虑网络运行参数,如节点分布、簇头能量、传输链路抖动等数据传输的影响因素,其性能难以满足当前WSN网络的超宽带传输需求。文献[6]提出了一种基于群扩散方案的WSN传输协议,该协议在LEACH算法的基础上引入节点能量裁决机制,采用周期统计机制获取能量最佳节点,将该节点作为中继传输节点,借助中继节点均值能量并群扩散方法来获取可使用的中继节点集合,从而提高链路在高抖动环境下的适应能力,降低网络抖动发生概率并达到链路稳定的效果,实验结果表明,该算法的传输性能优于LEACH算法。然而,文献[6]算法也存在网络吞吐受限的不足,在一定程度上限制了其适用范围。文献[7]基于数据分组报文集约化控制方案,提出了一种能够稳定传输链路的传输协议,该协议采用能量控制方式稳定中继传输链路节点,在区域分割完毕后将距离中继传输链路节点最近的节点作为备用节点,当主节点失效时自动启用备用节点,从而提高链路传输质量,并在一定程度上降低因网络抖动而导致的传输受阻、吞吐不畅等问题。然而,文献[7]协议仅选取能量最优的节点作为中继传输链路节点,未考虑网络出现大面积波动时导致备用节点失效的问题,难以适应复杂网络状况,特别是网络处于超宽带传输时,易因主、备节点均处于失效状态而出现链路抖动,降低了其实际部署价值。

针对WSN部署运行过程中存在的“热点”现象,文献[8]提出了一种基于轮询替换机制的传输协议,该协议首先在热度较高的区域插入标签,选取服务能力较高的节点作为中继节点,若区域热度较高,将自动启用周期轮询机制逐次替换区域中承担业务交换的中继节点,若链路出现抖动,也将自动进行切换。此外,该协议引入群分类机制训练能量较高的后备节点,能够显著降低WSN中因“热点”失效而导致的链路瘫痪概率,改善数据传输质量,且具有实现过程简单等优势。但是,文献[8]协议对超宽带传输场景考虑不足,单纯采用节点更换方式,难以应对链路抖动场景,在实际部署中容易因链路抖动而出现较为严重的拥塞现象,难以大范围推广。

综上,当前WSN数据传输解决方案难以将链路与节点纳入统一的优化机制中进行综合考虑,尤其无法通过训练方式实现节点的传输优化及区域分割,导致网络出现拥塞状况时极易引发节点瘫痪与链路抖动。为解决上述问题,本文提出一种基于病毒-抗体免疫博弈机制的超宽带WSN链路稳定算法。该算法主要由基于覆盖划分方法的网络初始化、基于病毒-抗体免疫博弈机制的区域最优分割、基于多参数判定机制的中继链路筛选方法3个部分构成。通过基于覆盖划分方法的网络初始化,可提高网络区域分割的效率,优化网络初始化过程中的节点覆盖性能。通过基于病毒-抗体免疫博弈机制的区域最优分割,以筛选出性能优越的区域节点与备用区域节点,使得算法网络区域初始化过程具有显著的分区优势。利用基于多参数判定机制的中继链路筛选方法,以改善区域节点间存在的链路抖动现象,提高网络的超宽带传输能力与链路运行质量。

1 网络模型

为便于研究,本文假定WSN节点的分布区域为矩形,大小为A×B。节点由sink节点、普通节点、区域节点3种构成:sink节点作为全局控制节点,具有最高的网络控制权及管理权,能够对网络中普通节点和区域节点进行统一管理及调配;普通节点主要承担数据采集及汇聚上传功能;区域节点主要用于汇聚区域数据并通过其余区域节点将数据上传至sink节点。此外,本文作如下假设:

1)节点不具有流动性,即节点在因失效而被更换前,其地理位置将不发生变化。

2)区域节点个数不具有稀疏性,即区域节点能够覆盖矩形区域,无死角现象。

3)传感器标识ID具有唯一性,且节点能够根据当前能量、数据采集、带宽、链路抖动等情况自主调节传输参数,依据传输距离优化传输链路。

4)区域内普通节点具有相似性,与区域节点处于高度融合状态;不同区域间的普通节点具有一定的不兼容性,且不同的区域节点无法跨区域管理普通节点。

1.1 节点能量消耗模型

图1所示为WSN数据传输及能量消耗模型结构,当传输带宽为B、传输距离为l时,节点能耗EEtran(B,l)满足:

EEtran(B,l)=BEEnode+BlxEEline

(1)

下一跳节点在接收数据时,其能耗EErecv(B,l)为:

EErecv(B,l)=BEEnode

(2)

其中,EEnode表示节点内部电路能耗功率,EEline表示天线对当前信号的放大功率,x表示传输模型指数[8],一般而言,当节点间的传输模型指数大于2时,两者间将不再建立直连链路。

图1 数据传输模型

根据上述假设,区域内普通节点具有相似性,与区域节点处于高度融合状态[9]。因此,区域节点能够将区域内k个普通节点的上传带宽B1,B2,…,Bk融合为区域带宽BBlocal并进行数据上传,区域节点因此所产生的能耗EElocal(BBlocal,k)满足:

EElocal(BBlocal,k)=BBlocalEElocal

(3)

其中,EElocal表示区域节点内部的电路能耗功率。

设WSN中区域数量为N,区域覆盖半径为d,任取一个区域并统计普通节点个数,可知区域内包含k个普通节点。由于区域内节点具有高度融合特性,因此普通节点的上传带宽为固定值BBlevel。区域节点需要汇聚数据并传输至sink节点,因此,区域内普通节点整体能耗EEall(BBlevel,d,k)满足:

EEall(BBlevel,d,k)=kBBlevelEEnode+kBBleveldxEEline

(4)

考虑到区域节点与该区域内普通节点的拓扑距离一般不超过1跳,因此,设传输模型指数x=1。此外,区域节点间同样需要进行数据中继,k个普通节点按均值BBlevel进行数据传输,区域节点将该数据汇聚到下一跳区域节点时能耗EEall(BBlevel,k)满足:

EEall(BBlevel,k)=kBBlevelEEnode

(5)

可以看出,能量消耗模型主要采用区域传输模式,以避免出现跨多个区域进行数据传输的情况。由式(3)、式(4)可知,节点进行数据传输时所消耗的能量与区域覆盖半径密切相关,通过区域划分的方式能够提高区域节点对普通节点的控制能力,避免因跳数过多而导致难以完全覆盖以及数据频繁重传的问题,最终改善网络传输质量。

1.2 链路覆盖模型

为保障节点间的链路均处于畅通状态,即普通节点-区域节点、区域节点-区域节点间链路畅通,区域节点应覆盖全部的普通节点。设区域节点LS的坐标为(Xa,Xb),任意普通节点OS的坐标为(Ya,Yb)。节点间的链路覆盖判决公式如下:

(6)

对网络中的全部区域节点进行遍历,按式(6)获取P(LS,OS),当链路覆盖全部节点时,满足:

(7)

其中,N为网络节点总个数。显然,当且仅当区域节点与各自所辖范围内普通节点均能建立链路时,网络中节点才均被链路覆盖。

本文算法将整个网络分割为非均匀分布的若干个区域,在满足链路稳定传输的情况下,网络能量开支最低,且数据传输带宽得到均衡。本文算法目标如下:

目标1区域内能量消耗尽量最低。联立式(4)、式(5)可知:

Target1=min(2kBBlevelEEnode+kBBleveldxEEline)

(8)

目标2链路覆盖范围最大化。由式(7)可知:

(9)

目标3区域分割数量m最少,其中,网络节点总数为N。

Target3=min(m/N)

(10)

联立Target1～Target3,本文目标可归结为如下模型:

(11)

其中,μi表示权重系数,取值为0～1,*表示目标选择。此外,权重系数满足:

(12)

链路覆盖模型主要采用等覆盖思想对网络节点进行均衡覆盖,并综合考虑能量消耗因素,通过式(6)、式(7)进行覆盖分割,能够提高链路覆盖能力,降低节点处于离线状态的概率。

2 WSN链路稳定算法设计

由于最终的网络数据均需要传输至sink节点[10],因此普通节点到sink节点间的传输链路具有多跳特性[11],若网络中存在多条传输链路时则会出现“热点”现象:某些区域节点因处于多条传输链路交汇处,其能量消耗将远超其余的区域节点[12]。此外,区域内的普通节点由于距离区域节点有远有近,由式(1)可知,它们的能耗也将有所不同。本文算法通过以下方式来解决网络中的“热点”问题,以稳定传输链路,改善节点能耗情况:

1)利用节点与链路之间存在的拮抗特性来构建病毒-抗体博弈机制,将区域内性能较优的节点视为病毒体,按照多维网络编码算法来建立病毒种群,并对其进行感染,将感染形成的抗体通过变异方式对链路抖动进行适应,以优化链路质量及区域传输性能,从而降低数据传输中存在的链路抖动现象。

2)基于能量-跳数均衡方法,设计多参数判定机制,按能量大小进行中继节点筛选,将全链路节点耗能总和作为判决指标,在跳数可达范围内实现能量和跳数的综合最优,确保每一个区域节点与sink节点间的链路处于稳定状态,从而改善链路传输质量。

如图2所示,本文算法在进行网络初始化时包含2个部分:1)区域节点选取阶段T1,sink节点选取最佳分区数量并通过路由表方式初始化链路数据;2)链路稳定传输阶段T2。为降低网络初始化过程中节点因发送各种数据分组而导致的能量消耗,仅当区域节点剩余能量低于阈值时进行区域节点主备切换。

图2 网络初始化示意图

考虑到WSN中节点处于密集状态时网络初始化过程较慢,因此,本文算法根据随机分布原则,将矩形区域按照覆盖点进行均匀分割,并将各覆盖区域中性能较好的节点建立为区域节点聚类集Ωlocal。sink节点通过病毒-抗体免疫博弈机制从Ωlocal中择优选取性能具有优势的区域节点,且将Ωlocal中最靠近被选区域节点的节点设置为备用节点,当区域节点发生故障时直接进行主备切换。图3所示为本文算法详细流程。

图3 WSN链路稳定算法流程

2.1 基于覆盖划分方法的网络初始化

在网络初始化过程中,sink节点通过监听网络数据分组对覆盖区域进行均匀分割。首先,sink发送Hello_c数据分组,节点收到该数据分组后,将自身ID与位置通过Re_hello数据分组发送到sink节点,其中,Re_hello数据分组包含节点剩余能量与位置信息;sink节点收到Re_hello数据分组后,保存全部节点信息并默认节点均为普通节点,当且仅当区域分割完毕后,做进一步区分;随后,sink节点根据网络中全部区域节点中覆盖半径最小节点的覆盖半径r,将区域分割为Llocal(Nnum)个覆盖,如图4所示。

图4 覆盖划分示意图

Llocal(Nnum)计算如下:

(13)

2.2 基于病毒-抗体免疫博弈机制的区域最优分割

在区域分割阶段,sink节点需要建立链路最稳定且区域分割数量最少的区域最优分割方案,并为节点之间的链路建立路由表。首先,sink节点根据距离-剩余能量建立阈值Δ:

(14)

其中,d(max,sink)表示节点与sink节点间的最大距离,d(min,sink)表示节点与sink节点间的最小距离,d表示节点与sink节点间的距离,E表示节点当前剩余能量,Emax表示网络中节点的最大能量,ω和σ表示裁决系数,R为节点的最大覆盖距离。

根据式(14)逐个对节点计算阈值,并按如下公式求取判决量ν:

(15)

其中,N表示网络中的节点个数。

当且仅当节点按式(14)求取的阈值大于判决量ν时,将自行加入区域节点聚类集Ωlocal,作为待选的区域节点。

2.2.1 区域节点选择

本文算法采用病毒-抗体免疫博弈机制,结合免疫算法进行区域节点及备用区域节点的选择,算法步骤具体如下:

1)收集网络中节点的详细信息,主要包括节点ID、节点坐标及节点剩余能量。

2)按如下方式确定区域节点与备用区域节点:

(1)设置免疫算法的基本参数。

(2)将区域节点聚类集Ωlocal视为种群集合并进行划分。

(3)确定基本目标参数,输出结果。

2.2.2 病毒种群初始化

按照式(16)构建区域节点聚类集Ωlocal,区域节点从该聚类集中选出。

Ωlocal={X1,X2,…,Xgroup(NUM)}

(16)

其中,group(NUM)表示病毒种群的总数量。结合式(16)和式(13),将区域节点纳入覆盖划分中:

Ωlocal∈A×B={D1,D2,…,Dgroup(NUM)}

(17)

相关参数同式(13)、式(16),Di表示第i个节点坐落在由式(13)确立的覆盖范围之内,即相应的节点坐标可被区域完全覆盖。

sink节点按照多维网络编码算法[13],将式(17)所示的待定区域节点的ID、初始能量、距离3个参数进行网络编码,形成样本空间为group(NUM)的病毒种群Ggroup:

Ggroup={V1,V2,…,Vgroup(NUM)}

(18)

病毒种群Ggroup中每一个病毒均为待选区域节点,需要通过感染机制筛选出感染能力最强的一组区域节点及备用节点,感染过程中需要充分考虑传染力及抗体博弈强度,以便能够筛选出变异效果最佳的病毒。

2.2.3 感染效果评估

由于WSN节点的能量基本上被数据传输所消耗[14],因此针对式(18)中的病毒,采用式(11)进行目标评估,并根据评估结果按降序方式对式(18)进行传染力排序,如下:

Ggroup={M1,M2,…,Mgroup(NUM)}

(19)

2.2.4 抗体博弈

本文基于蒙特卡洛方法[15],针对每个病毒因子感染能力的高低进行排序,某个病毒因子传染能力越高,则对应的抗体博弈强度也越大。对式(19)所示的病毒群体进行抗体复制操作,选取当前感染力最强的0.5Ggroup(NUM)病毒进行变异。初始变异率等于链路抖动率,针对感染力最强的0.5Ggroup(NUM)病毒进行变异处理,每个病毒均产生Ggroup(NUM)个抗体并形成抗体种群:

Ggroup(KT)={Y1,Y2,…,Ygroup(NUM)}

(20)

其中,KT∈(X,Ωlocal)。

在网络进行每一轮区域节点更新过程中,将抗体种群与病毒进行博弈,当且仅当病毒无法进行变异时,抗体种群才得到更新。其中,博弈方式如下:

(21)

2.2.5 博弈结束判定

本文病毒-抗体免疫博弈机制的结束条件定义为变异之后抗体种群与病毒种群间的差异值Γ无变化,Γ计算如下:

(22)

即网络在进行区域初始化的过程中,区域节点(对应病毒种群)与备用区域节点(对应抗体种群)之间可以互相取代时,博弈过程结束。此时,区域节点与备用区域节点的覆盖范围相同,且具有相同的链路覆盖能力(路由表相同),普通节点自行选择距离最近的区域节点并加入到该区域中。

2.3 基于多参数判定机制的中继链路筛选方法

通过病毒-抗体免疫博弈机制,可以从WSN中筛选出性能最佳的区域节点集合。然后,将普通节点纳入到各自所管辖的区域中。但是,由于区域节点往往无法通过一跳的方式与sink实现链路直连,因此需要通过多跳方式保证每一个区域节点与sink节点间的链路处于稳定状态,且跳数尽可能少,据此构建中继链路筛选方法如下:

(23)

其中,E(j)表示下一跳节点的剩余能量,Emax表示可达的下一跳节点中能量最高的节点所剩余能量,i_T表示区域节点i与sink节点间的跳数,max_T表示可达的下一跳区域节点中与sink节点的最大跳数,k1和k2表示权重系数,满足:

k1+k2=1

(24)

2.4 数据传输

通过上述过程,普通节点采集的数据即可通过区域节点发送到sink节点。然而,由于WSN均采用无线方式进行数据传输[16-17],为防止区域节点间存在频率干涉现象,本文按QPSK预发射方式[18-19]对区域节点逐个采用不同的发射频率,且信号处于正交状态。处于中继状态的区域节点收到上一跳区域节点后,将自动采用本区域内的发射频率并将数据发送到下一跳区域节点或sink节点,直到数据能够完整地传输至sink节点为止。

3 实验结果与分析

3.1 实验环境与指标参数

为便于评估本文算法的性能,选取NS2仿真环境,计算机操作系统为Win10,CPU主频为5.5 GHz,16 GB内存。WSN节点分布区域为矩形,大小为1 000 m×1 000 m,节点密度不低于1个/m2,采用随机撒点分布模型。实验中选择的性能指标为:1)中继链路首次瘫痪发生的轮数,主要用于评估区域节点的运行质量;2)网络稳定时间,即从网络开始采集数据直到中继链路瘫痪的时间;3)拥塞发生次数,用以评估链路拥塞情况。此外,为降低误差,每组仿真重复10次,取均值作为最终结果。在式(11)中,μ1取0.4,μ2取0.3,μ3取0.3;在式(23)中,权重系数k1和k2作为仿真评估参数,将在下文实验中进行对比。将文献[20]中的LEACH算法和文献[21]中的LMS-A算法作为对照算法。

3.2 中继链路首次瘫痪发生轮数

为测试WSN中中继链路首次出现故障的轮数,将3种算法的区域节点最大覆盖半径R均设定为50 m。其中,本文算法权重系数k1和k2均设为0.5。由图5可以看出,本文算法发生中继链路首次瘫痪的轮数要远高于LEACH算法和LMS-A算法,说明本文算法采用的病毒-抗体免疫博弈机制及多参数判定机制能够获取较高质量的网络区域分割效果,且能够显著提高中继链路的传输质量,降低区域节点发生瘫痪的概率。LEACH算法由于未能综合考虑能量、链路等因素,因此传输过程中发生中继链路抖动的概率较高,LMS-A算法虽然从链路角度对区域节点传输质量进行了监控,但该算法未消除区域节点数据传输时的频率干涉现象,容易导致较为严重的链路抖动,因此,其发生中继链路抖动并瘫痪的概率高于本文算法。

图5 3种算法中继链路首次瘫痪发生轮数对比

3.3 网络稳定时间

参数设置同3.2节,由图6可以看出,本文算法网络稳定时间始终较高,说明病毒-抗体免疫博弈机制及多参数判定机制能够较好地稳定数据传输链路,减少链路瘫痪和网络瘫痪现象。LEACH算法对链路因素考虑不足,且未对网络区域初始过程进行优化,因此,其网络运行稳定程度低于本文算法。LMS-A算法虽然从传输链路角度对区域节点进行了优化,但是未能消除频率干涉现象,容易导致区域节点间吞吐困难等问题,因此,其网络稳定性也低于本文算法。

图6 3种算法网络稳定时间对比

3.4 拥塞发生次数

参数设置同3.2节,由图7可以看出,本文算法采用的病毒-抗体免疫博弈机制及多参数判定机制能够大幅降低拥塞发生次数,与LEACH算法和LMS-A算法相比优势明显,主要原因在于病毒-抗体免疫博弈机制能够实现区域节点的最优选取,且通过主备方式避免因区域节点失效而导致的拥塞现象,此外,多参数判定机制能起到稳定链路的作用,因此,本文算法拥塞发生概率较低。LEACH算法和LMS-A算法的中继链路瘫痪概率较高,这是由于LEACH算法未对链路抖动情况加以考虑,出现区域传输抖动概率较高,而LMS-A算法未能消除区域间的干涉现象,容易因区域节点失效而发生拥塞现象,因此,这2种算法的拥塞发生次数显著高于本文算法。

图7 3种算法拥塞发生次数对比

4 结束语

本文提出一种基于病毒-抗体免疫博弈机制的超宽带WSN链路稳定算法,通过病毒-抗体免疫博弈机制改善区域节点的初始化及后续更新过程,采用多参数判定机制进一步优化区域间的链路,使用PSK预发射方式降低区域节点间的频率干涉概率,最终解决链路拥塞问题并降低链路瘫痪概率。实验结果表明,该算法具有良好的链路稳定性。下一步将引入区域间的链路综合判定机制,以提高本文算法的链路切换效率及其在复杂环境下的部署性能。