面向BLE健康监护网络的负载均衡算法

2021-05-20 06:50李晓卉李小钰丁月民朱时晖
计算机工程与设计 2021年5期
关键词:路由链路能量

李 锐,李晓卉,李小钰,丁月民,朱时晖

(1.武汉科技大学 信息科学与工程学院,湖北 武汉 430081;2.华中科技大学同济医学院 同济医院,湖北 武汉 430030;3.天津理工大学 计算机科学与工程学院,天津 300384;4.建荣半导体(深圳)有限公司 工程部,广东 深圳 518051)

0 引 言

BLE Mesh[1]技术的诞生解决了传统蓝牙传输距离过短的瓶颈[2],因此这项技术应用越来越广泛[3-5]。然而,目前学术上对BLE Mesh网络协议研究偏少,常用的几种协议不能满足市场上各种应用的需求。在本文研究的面向BLE Mesh的健康监护网络中,一方面网络中有部分节点时常处于移动状态;另一方面现有BLE Mesh路由协议未考虑负载均衡导致部分节点能量消耗过快。因此,现有协议难以满足以保证服务质量为首要目标的数据传输需求,这就很容易导致监护信息无法及时有效地送达,从而造成安全隐患。

目前常用的BLE Mesh算法中,CSR Mesh算法的优点是简单可靠,但其在路由过程中,具有资源占用大、节点消耗能量快等劣势,并且当节点经常处于移动的状态下,容易产生断链,需要重新发现路由,导致数据无法稳定传输[6];而机会路由算法应用在本网络中由于移动节点的存在,导致最优节点的选择有着很大的不确定性,且最优节点一旦确定,单一的路由路径就被确定,易出现绕远路情况,同样无法保证能耗最优[7]。部分学者采用AOMDV算法进行路由,由于备用路由的存在,其在一定程度上可以增加网络的稳定性和容错能力,并相对平衡了各节点能量消耗。然而AODMV采用单一的跳数作为路由判据,并未考虑节点移动和剩余能量等因素,故选择的路由往往也不一定是最佳路由[8]。而一些考虑剩余能量的协议,如文献[9]将剩余能量运用到机会路由协议中,文献[10]通过设置能量阈值来选择代理父节点,从而选择最佳路由。这些协议对节点的剩余能量划分过于绝对,没有动态地考虑节点能量,故无法保证达到负载均衡。

综合来看,在现有的路由协议的设计中,所考虑的路由指标往往是固定不变的。而在实际应用中,随着节点位置和剩余能量等的动态变化,路径的选择同样要随着变化做动态调整。如何通过网络的动态变化设计出动态的链路指标,再借助动态链路指标指导路由建立则是一种新的路由算法设计思路。鉴于以上设计思路,本文提出一种负载均衡多径路由算法(load-balancing ad-hoc on-demand multipath distance vector routing,L-AOMDV),其在AOMDV的基础上,一方面考虑了监护网络中移动节点的移动特性,另一方面考虑了路由节点的动态剩余能量,最终通过引入负载均衡链路状态指标(load-balancing link quality indicator,LLQI)指导路由建立。

1 网络结构和相关模型构建

本节主要介绍网络的结构和动态剩余能量计算模型与节点移动状态概率计算模型的详细设计。

1.1 网络结构

传统的BLE Mesh网络中,各节点都具有路由功能,但未对节点的功能进行划分,导致节点在健康监护的实际应用时,功耗过大。为了进一步优化BLE Mesh健康监护网络节点功耗[11,12],本文采用一种新的网络拓扑结构,该结构将BLE Mesh节点分为3类:固定终端节点、固定路由节点和可移动节点。

其中固定终端节点采用低功耗广播(low power advertisement,ADV LOW)广播自身设备信息,其仅定期采集传感器信息,然后将信息发送至其它固定路由节点,或获取固定路由节点的控制信息;固定路由节点具备固定终端节点的功能,同时其可利用广播中继(advertisement relay,ADV RELAY)接收和中继其它节点的信息,起路由功能;而可移动节点具备固定路由节点的全部功能,属于全功能节点,其具有一定的运算能力并可根据蓝牙信标获取自身位置[13],另外其采用标准低功耗蓝牙的关贸总协定(general agreement on tariffs and trade,GATT)与手机通信。

整个网络拓扑结构如图1所示。

图1 网络拓扑结构

1.2 动态剩余能量计算模型

如果简单地以当前节点的剩余能量作为影响路由判据的相关因子,则可能不能设计出最佳判据,因为这种策略忽略了能量消耗的速度,例如某个路由节点当前剩余能量较多,然而其能量消耗速度过快,在选择路径时也应降低此节点的选择权重。为了动态获得节点的剩余能量,可通过构建模型滚动预测未来时间段节点的剩余能量,再通过未来节点剩余能量的多少来设计路由判据影响因子。由于预测仅参考过去剩余能量这一个指标,预测模型必须简单、精度相对较高,且计算难度不能过大,因此本文采用灰色一阶一元预测模型GM(1,1) 来预测节点的剩余能量[14],灰色预测模型具有样本数量要求低、算法相对简便、短期预测精度高等优点,因此比较适合在本系统中预测未来各节点的剩余能量[15],预测步骤如下:

每隔固定时间t,记录固定路由节点的剩余能量,持续记录的总时间为T=nt,记录完毕,将数据传输给全功能节点进行处理,即得到滚动的固定路由节点的剩余能量时间序列为

x=(x(1),x(2),…,x(n))

(1)

式中:x(n) 表示在n时刻固定路由节点的剩余能量值。

对剩余能量序列按照式(2)进行累加

(2)

得到累加的剩余能量序列

X=(X(1),X(2),…,X(n))

(3)

对X建立灰色模型的一次微分方程,其方程如式(4)所示

(4)

(5)

式中:Yn和B的计算分别如下

(6)

(7)

(8)

1.3 节点移动状态概率计算模型

由于被监护者为可移动节点,根据被监护者的特征,即其不是随机的在网络的各个区域移动,而是其有很大概率会在某些固定区域之间移动,故可构建一种简单的模型计算出移动节点处于各个区域的概率,得到概率之后,在设计路由判据时将区域概率因素考虑进来,则设计的链路更偏向于选择移动节点出现频率高的区域中的路由节点。下面是构建该模型的方法:

在布置固定路由节点之后,根据节点平面分布,先记录下固定路由节点的位置信息,然后根据布点情况将整个区域平均划分为多个,如图2所示分布,可将整个网络划分为9个区域,设区域序列Z=(Z1,Z2,…,Z9), 则Z1至Z9表示这9个区域。为了获取可移动节点的位置情况,需要在应用区域四周布置数个蓝牙信标,通过信标即可随时记录可移动节点的位置情况。

图2 节点划分区域

由于移动节点可通过蓝牙信标得到当前的位置,故每隔固定时间t,记录移动节点的区域位置,持续滚动记录的总时间为T=nt,记录完毕,可得到T时间段内移动节点处于各区域的序列为

(9)

式中:序列D即表示移动节点在T时间内依次处于各区域的情况。由式(10)可统计出T时间内移动节点处于各个区域的概率Ni为

(10)

2 L-AOMDV路由算法

L-AOMDV算法考虑了节点的动态剩余能量和移动特性,即在构建链路时优先考虑动态剩余能量大的路由节点和移动节点出现频率高的区域内的固定路由节点,上一节介绍了如何通过两个模型计算得到节点的动态剩余能量和移动节点的区域概率,本节详细介绍利用这两个指标设计出新的路由判据——负载均衡链路状态指标,并介绍整个算法流程。

2.1 负载均衡链路状态指标

首先需要考虑链路的质量因素。对于确定的网络设备,一般有着固定范围的链路质量值LQI,且一般由MAC层计算得到。设LQImax和LQImin为LQI的上下限,对于相邻两个节点间链路质量的权值标准化由式(11)表示

(11)

式中:YLQIab为节点a到节点b的归一化链路质量指标。

其次考虑路由节点的动态剩余能量对网络的影响,未来时间段剩余能量高的固定路由节点影响整个链路质量的权重会高于剩余能量低的节点。设Emax为初始的节点最大能量,定义Ej为固定路由节点能量指标系数,则

(12)

接下来考虑网络中的移动节点对网络的影响,由于移动节点处在各区域的概率不同,故各Zi区域内的固定路由节点影响整个链路质量的权重不同。定义Ti为处于Zi区域的固定路由节点状态指标系数,则

(13)

式中:Ni为上一节得到的固定路由节点区域概率,λ为调节因子,调节状态指标系数的大小,其值越大则状态指标系数数值越小,状态指标系数值越小则移动状态对整个链路指标的影响度也就越小。

结合式(12)和式(13)可得到节点a与节点b之间的负载均衡链路状态指标系数Rab

Rab=TiaTibEaEb

(14)

式中:Tia为节点a对应的状态指标系数值,例如节点a处于Z2区域,则Tia=T2,同理Tib为节点b对应的状态指标系数值,Ea和Eb分别为节点a和节点b的能量指标系数值。

再根据式(15)可得到两个节点之间的负载均衡链路状态指标LLQIab

LLQIab=RabYLQIab

(15)

LLQIab数值越高表明两节点间链路质量和能量均衡性能越好。

最后计算整条链路的负载均衡链路状态指标,对于从源节点到目的节点的完整链路,其负载均衡链路状态指标计算如式(16)表示

(16)

LLQIpath即为整个路径的负载均衡链路状态指标,数值越大表示整条链路的通信性能和负载均衡度越好。

2.2 算法流程图

L-AOMDV算法的流程如图3所示。

图3 L-AOMDV算法流程

整个路由算法分为路由发现、路由维护和路由更新3个部分。

整个算法在路由发现阶段查找出所有可能的节点不相交多路径;由于在路由请求和应答报文中包含负载均衡链路状态指标,因此可以计算得到各条路径的负载均衡链路状态指标;在选择路径时选择指标最大的作为主路径,并预留两条备用路径。在普通模式下采用主路由进行通信,若监护人健康出现异常,则系统进入紧急模式,此时系统同时采用主路径和备用路径传输数据,以保证网络的稳定性和可靠性。

当路径建立后,系统进入路由维护状态,在此期间,目的节点定期向源节点发送维护消息,维护信息中包含节点的剩余能量信息和移动节点的位置信息,在这一过程中系统会时刻检测维护消息中的LLQI值。

若检测的LLQI值出现异常,系统进入路由更新状态:当第一次检测到LLQI值降低到预警值的时候,开始进行备用路由更新,源节点发送更新信息沿每一条备用路径到达目的节点,并且重新计算链路的LLQI值,当源节点第二次检测到链路状态降低到预警值的时候,开始切换备用路径,在备用路径选择链路状态最好的路由进行通信,并且将原路径从路由表中删除,当所有备用路径都失效时,重新进行路由发现。

3 仿真与结果

为评估L-AOMDV在BLE Mesh健康监测网络中的有效性,本文在MATLAB上开发了L-AOMDV算法,并和CSR Mesh路由算法与AOMDV算法进行仿真对比。

3.1 仿真参数设置

仿真的社区健康监护BLE Mesh网络的区域为30*30 m2的区域。考虑到现实中场景布点数量的不同,本次仿真分别采用10个至40个节点对其进行模拟,其中包含较少量的移动节点,整个节点区域共划分为9个,固定节点随机分散在这9个区域之中,移动节点按照一定轨迹在3个-7个区域内移动,获取位置间隔时间t设为20 min,记录总时间设为9t。在相同条件下,经仿真测得,调节因子λ数值在1.3-1.7之间具有较好的实验效果,若调节因子λ过低则路由开销过大且分组投递率并没有明显提升;若调节因子λ过高,则移动状态概率计算对提升网络性能没有起到积极的效果,本次仿真中调节因子λ取1.5。确定调节因子λ之后,继续在相同条件下求得调节因子σ的最优值,经仿真测得调节因子σ数值在2.5-3.4之间时,路由开销总体增加不多,却可有效延长网络的生命周期,在本次仿真中调节因子σ取3.1。在不考虑紧急模式的情况下,具体的仿真参数见表1。

表1 仿真场景参数

3.2 仿真性能指标

为了更好地评估各种算法在健康监护网络中的性能差异,本文以分组投递率作为算法性能评估的基础指标。分组投递率可用于表征数据包投递成功的概率,若此数值过低,则表明算法性能较低,不适合采用。

在保证有较高的分组投递率的前提下,再选择平均节点死亡个数作为负载均衡性能的评估指标,若算法的负载均衡性能越好,则平均节点死亡个数的值越低。

另外,为了综合地了解算法的其它性能,例如数据包投递过程中所用时间与网络的复杂度等,本文选择平均路由跳数作为算法性能评估的辅助指标,借助此指标可以更全面地了解算法的性能。

3.3 仿真结果分析

3种算法的分组投递率仿真结果如图4所示。随着节点数量的增加,3种路由算法的分组投递率均随之上升。由图可知,L-AOMDV有更高的分组投递率,其原因在于一方面L-AOMDV能通过LLQI值,优先向移动节点出现频率高的区域内的固定路由节点建链,以此保证在移动节点移动过程中的通信顺畅;另一方面L-AOMDV考虑了节点的未来剩余能量,这一定程度避免了部分节点过早死亡对网络的影响。而AOMDV仅根据网络初始状态下的路由发现跳数建立路由表,无法保证在移动节点移动过程中的链路稳定性。CSR Mesh由于每次仅能建立一条链路,在移动节点移动的情况下无法保障该链路的有效性。

图4 分组投递率仿真结果

当节点设置为40个节点,所有的节点初始能量设置为2 J时,3种路由算法的平均节点死亡个数情况如图5所示。由图可知,随着时间的增加,L-AOMDV算法中的节点死亡速率远低于另外两种路由算法,且在路由开始运行的50 min内,L-AOMDV算法中无节点死亡。这表示在各节点均有相同的能量下,L-AOMDV算法能够延迟第一个节点的死亡时间;在相同时间段内,采用L-AOMDV算法的网络中死亡的节点数目最少。在现实中,则表示不会出现某个健康监护节点过早死亡从而导致某项数据遗失的情况,也意味着不需要频繁地给某些节点补充能量。出现以上结果是因为L-AOMDV尽可能优先选择能量相对较高的节点进行通信,也尽可能优先选择移动节点出现频率高的区域内的固定路由节点进行通信,这相当于负载均衡地分担给了整个网络,另外由于节点死亡速率变慢,也相当于延长了整个网络的生命周期。

图5 平均节点死亡个数对比

路由跳数仿真结果如图6所示,随着节点数量的增加,3种路由算法的平均路由跳数均随之上升。L-AOMDV所耗路由跳数高于AOMDV与CSR Mesh,这是因为AOMDV 与CSR Mesh会优先选择路由跳数最短的路径进行路由,而L-AOMDV会考虑移动节点的位置和节点的未来剩余能量。L-AOMDV较之AOMDV与CSR Mesh而言,路由跳数增加,网络的开销和复杂度会相应有所增加。对于复杂度,由于健康信息的数据量相对较少且设定的发送间隔周期较长,从仿真结果来看,分组投递率的显著提高表明复杂度的提高对本应用影响不大。对于网络整体开销的增加,由于健康监护系统对数据传输稳定性和有效性要求较高,因此以一定的开销换取更长的网络生命周期是可以接受的。

图6 平均路由跳数仿真结果

图7为一段时间内源节点与目的节点通信过程中生成的3条路径的LLQI值展示情况。在通信伊始,由于路径1的LLQI值最高,故选取路径1作为主路由通信。随着网络复杂度的增加以及部分节点能量的减少,各路径的LLQI值均有所下降。在运行过程中,当路径1的LLQI值低于设定的阀值,而路径2的LLQI值相对较高时,则表明路径2的通信性能更佳,此时开始切换备用路径,选择路径2作为主路由通信。通过以上备用路由的切换过程也进一步表明了L-AOMDV算法所采用策略的有效性。

图7 L-AOMDV算法中多路径LLQI值

综上所述,在存在移动节点的BLE Mesh健康监护网络中,L-AOMDV算法在性能上较AOMDV与CSR Mesh算法存在一定优势,其一方面保证了数据投递的成功率,另一方面又延长了网络的生命周期,有效增强了网络性能。虽然L-AOMDV算法在路由开销方面会略高,但是在对稳定性和有效性要求更高的健康监护网络下,L-AOMDV算法更能够满足健康监护网络的需求。

4 结束语

针对健康监护系统中存在可移动节点和传统算法未考虑负载均衡因素造成BLE Mesh网络数据传输不稳定的问题,本文提出了一种负载均衡多径路由算法——L-AOMDV,在算法中综合考虑了节点的移动特性和未来剩余能量并引入更加有效的负载均衡链路状态指标——LLQI来指导建立链路,同时在路由维护中通过及时更新LLQI的值来选取最佳备用链路;另外系统还优化了BLE Mesh网络的拓扑结构和设立了紧急模式来进一步提升网络的可靠性。仿真结果表明,L-AOMDV算法比传统的CSR Mesh算法和AOMDV算法有更高的投递率和更长的网络生命周期,因此在家庭社区健康监护系统中,其更能够保证数据传输的稳定性和有效性。

猜你喜欢
路由链路能量
天空地一体化网络多中继链路自适应调度技术
能量之源
探究路由与环路的问题
诗无邪传递正能量
基于数据包分割的多网络链路分流系统及方法
基于预期延迟值的扩散转发路由算法
开年就要正能量
凝聚办好家长学校的正能量
基于3G的VPDN技术在高速公路备份链路中的应用
PRIME和G3-PLC路由机制对比