无线传感器网络强化学习增强路由研究

张华南，李石君，金 红

1.广东培正学院数据科学与计算机学院，广东 广州 510830

2.武汉大学计算机学院，湖北 武汉 430072

3.湖北大学计算机与信息工程学院，湖北 武汉 430062

无线传感器网络（wireless sensor networks,WSN）通过相互连接的传感器设备实现了数据采集、数据传输与数据分析。实时监控系统是传感器网络的一个重要应用，传感器节点收集数据并通过多跳传输转发给汇聚节点，系统对实时通信有很强的要求。因此设计一个低延迟、高可靠性的路由协议是非常重要的。用于监控应用的路由协议有以下要求：

1）高可靠性 传感器的传输范围有限，采样数据需要通过多跳传输转发到目的地。如果传感器之间的链路质量差导致数据频繁丢失，则无法满足业务需求。

2）低延迟 从传感器采样的数据要快速传递到目的地，否则不可能对紧急情况给予反应。如在健康监测系统中，数据延迟对患有严重疾病的患者来说是致命的。因此，需要构建最短路径或通过负载均衡减少排队延迟，将数据及时转发到目的地。

3）能源效率 监测应用场景的传感器通常安装在电池更换困难的地方。如果某个特定节点的能量很快耗尽，就会导致网络寿命缩短。因此减少网络能量消耗是非常必要的。

传统的Ad-hoc 路由协议[1]能够保证可靠传输，满足WSN 源节点的业务需求，涉及到传感器维护路由路径的高计算能源开销。为了降低控制开销带来的能量消耗，基于树的路由是一种可行的解决方案。父节点选择是基于树的路由协议的一个关键角色，因为父节点和子节点之间的链路被用作路由路径。传统的树路由[2]使用到接收器的跳数作为父节点选择的决策标准。每个源节点都可以通过选择跳数最少的节点作为父节点来构建到接收器的最短路径。这种方法可以提供低延迟，但是在选择父节点的过程中没有考虑父节点和子节点之间的链路质量，因此不能保证可靠的传输。

路由协议在WSN 中起着重要的作用，可以保证可靠传输，满足单个节点的服务质量（quality of service,QoS）要求。网络节点的电池在野外是难以替代的，因此，路由协议应该以较低的能量开销创建路由路径。在响应式路由协议中，源节点在需要到目的节点的路由路径时发送路由请求消息。为了保证路由路径的可靠性，节点会定期广播控制消息，并向相邻节点检测链路状态。在移动自组织网络等节点频繁移动的网络中，响应式路由可以保证可靠的传输，但是为了维护路由路径，能量消耗显著增加。

为了减少控制消息的数量，主动路由协议（如优化的链路状态路由协议）会选择相邻节点间连通性高的节点作为父节点。为了维护拓扑信息，父节点必须定期广播控制消息。这种驱动路由可以减少控制消息的数量，因为只有父节点广播拓扑信息。但是，当需要传输大量节点信息时，广播开销和内存占用会增加。此外，在节点频繁移动的网络中，由于拓扑信息必须频繁广播，控制开销显著增加。为了降低广播开销带来的能量消耗，基于树的路由是小型WSN 的最佳解决方案。树型路由协议由一个根节点和多个传感器节点组成，节点之间具有父子关系，通过树型结构相互连接。每个节点选择最优的父节点并将数据转发给父节点，直到数据到达根节点。基于树的路由可以消除路径搜索并避免大量广播消息。父节点和子节点之间的通信链路作为路由路径，根据树的路由协议选择父节点[3]。

1 相关工作

为了构建稳定的树结构拓扑，文献[4-5] 采用链路质量作为决策标准。但是，在选择父节点时没有考虑负载均衡，因此，在特定的节点上可能会放置过多的负载，导致严重的丢包。为了防止拥塞，文献[6-7] 提出了一种负载敏感的父节点选择算法，但没考虑链路质量和能源效率。这些基于树的路由协议独立地解决不同的父节点选择问题。然而，无法同时解决传输可靠性、端到端延迟和能耗等多个性能指标。

为此，文献[8-9] 尝试在考虑多个认知指标的情况下选择最佳父节点。为了共同实现多个目标，采用了线性加权的方法[10]，其中每个节点通过多个指标计算加权[11]。然而，线性加权方法采用了主观权重，使性能指标之间缺乏灵活的权衡。为了克服这一局限性，提出了一种基于多标准决策（multi-criteria decision making,MCDM）的选择方案，该方案通过层次分析法（analytical hierarchy process,AHP）[12]确定多个决策准则（相对重要性）来寻找最佳父节点，然后通过简单加权法（simple additive weighting,SAW）[13]得到加权值。然而，决策者需要根据其偏好或目标网络的背景知识来计算每个指标的权重。此外，由于无线传感器网络的规模越来越大，部署也越来越复杂，因此在大规模无线传感器网络中寻找最优父节点具有挑战性。

为了消除决策者的偏见，并在复杂的部署场景中给出适应性决策，进而实现多个目标，如高可靠性、低延迟和能源效率，本文通过强化学习获得的关于目标网络的经验数据以找到最好的父节点。具体来说，使用多个认知指标定义一个状态空间、动作集和激励函数，通过试错找到最佳父节点。

2 系统模型和问题陈述

2.1 网络模型

网络模型如图1 所示，包括N个传感器节点和M个汇聚节点，其中Sink node 是汇聚节点，Sensor node 是传感器节点，Obstacle 是障碍物。这些节点构成了树状拓扑结构，其中汇聚节点位于树的顶层。树状结构通过树状路由协议自主配置。汇聚节点作为控制器，将从传感器节点采样的数据进行聚合，形成树状结构。假设传感器节点和汇聚节点都有固定的位置，节点间的链路质量取决于地理位置。然后，每个传感器节点在其邻居节点中选择一个父节点，并将数据传递给父节点，直到到达汇聚节点。

图1 汇聚节点和传感器节点的部署Figure 1 Deployment of sink nodes and sensor nodes

为了根据网络条件的变化选择最优的父节点，每个节点需要使用多个认知指标来识别当前的网络状态。主要目标是实现高可靠性、低延迟和能源效率[14]。但是，选择最佳父节点需要考虑很多因素，例如，多个传感器节点选择同一个父节点，在父节点上建立队列，导致排队延迟增加或数据包丢失。此外，父节点和子节点之间的链接质量取决于它们的地理位置，因此，障碍会使传输变得不可靠。

为了减少每次传输的延迟，每个节点都应该构建一条到目的地的最短路径。在树状路由中，到汇聚节点的跳数是选择父节点的决定性指标，即每个节点都可以通过将汇聚节点的跳数作为决策变量来保持较低的延迟。在这项工作中，采用跳数H作为决策变量，形成分层树状结构，减少端到端延迟[15]。

父节点和子节点之间的链接质量高度依赖于距离和障碍物。在链路质量较差的情况下，如果节点选择到汇聚节点的跳数最短节点作为父节点，则可能会造成因丢包和重传导致的额外能耗增加。用子节点和候选父节点之间接收到的信号强度P描述信号质量，每个节点在接收到邻近节点的Hello 消息时，可以很容易获得信号强度。

使用加权移动平均（weighted moving average,WMA）来防止测量值的突然变化，近期测量数据的权重较高，过去测量数据的权重较低，因此，将每个测量值乘以一个权重。设发送一个Hello 消息用时为t，则节点i与邻居节点在n个周期的信号强度WMA 值公式为

式中：Pi(i=1,2,···,n) 为节点i的信号强度WMA 值；时间因子t-n表示当前所处的时间点；权重系数wi决定了每一个历史数据在计算中所占的比重。

如果多个节点选择同一个邻居作为父节点，则该父节点将会负载过重。换句话说，当父节点接收到超过其处理能力的数据时，可能会发生缓冲区溢出。为了防止拥塞，采用缓冲区占用率作为选择父节点的决策变量。为防止测量数据的突然变化，定义相邻节点i的缓冲区占用率的n周期WMA，用来描述相邻节点i的缓冲区占用率Bi在时间序列中的演化过程，公式为

式中：Bi为第t个时间点上的WMA 值；指数项表示前n个时间点上的值与权重之间的线性组合；Bt为t时刻缓冲区占用率，公式为

式中：Bcur为t时刻的当前缓冲区；Bmax为最大缓冲区。

一般情况下，野外部署的传感器电池很难更换。如果某个特定节点的能量很快耗尽，就会导致网络寿命的缩短。为了提高整个网络的寿命，采用功耗比作为决策变量来选择父节点。功耗比E的公式为

式中：Tcu表示由于回退或重传引起的累积延迟；a为回退或帧重传的数量。L为有效载荷长度。Eidle、ETx、ERx和Esleep为每种收发模式的能耗，Etotal为总能耗。

在根据网络条件的变化找最优父节点的时候需要考虑多种因素，以在相互冲突的目标（即高可靠性、低延迟和能源效率）之间找到合理的平衡。在文献[16] 所提到的方法中，每个节点计算出每个邻居多个标准的加权和，然后选择具有最高加权值的节点，它合理地权衡了性能指标之间的关系。然而，决策者必须根据自己的偏好或对网络的背景知识来计算权重因子。相比之下，在这项工作中，强化学习（reinforcement learning,RL）模型使每个节点都能利用网络的经验数据，从而根据网络状态自适应地选择父节点。

3 树路由协议

本文提出的树路由协议由几个组件组成，协议框架如图2 所示。每个组件与其他组件交互以构建树状拓扑，并通过父节点选择找到最优路由路径。本节首先描述路由协议的基本操作，然后指定基于RL 模型的父节点选择算法。

图2 协议架构Figure 2 Protocol architecture

图2 中Event scheduler 是事件调度程序，RL-based parent selection 是指基于强化学习的父代选择，Loop detection 是循环检测，Control packet queue 是控制分组队列，Neighbor management 是邻居管理，Neighbor Table 是邻居表格。

3.1 树结构

汇聚节点定期广播消息，包括到汇聚节点的跳数、根节点、父节点选择和数据传输路径。当节点接收到构建消息时，将跳数存储在邻居表中，并将构建消息中的跳数加1，然后节点重新广播构建消息。由于节点选择跳数相同或更少的相邻节点作为父节点，因此节点的层次级别根据到汇聚节点的跳数自主确定。此外，每个节点定期广播一个Hello 消息，其中包含了提议的决策标准（即P、B和E）。每个节点收到邻居的Hello 消息后，将决策标准存储在邻居表中。这些变量用于在每个节点上选择父节点。树的构造细节在算法1 中给出。

3.2 父节点的选择

3.2.1 RL 模型

在RL 模型中，状态空间可以定义为3 个决策准则的集合，S={Pi,Bi,Ei},i∈N，即每个节点根据相邻节点的链路质量Jaccept、拥塞程度r=True 和剩余能量选择父节点。动作空间定义为邻居表中的一组候选父节点，应该注意的是候选父节点集只包含到汇聚节点的跳数与汇聚节点本身相同或更少的相邻节点；关于激励函数可以定义如下：如果选择一个节点作为父节点，该操作增加了帧重传、包错误率和能量消耗，则获得较低的激励，否则会得到很高的激励。

3.2.2 基于RL 的父节点选择算法

为了找到最佳的父节点，定义了多个认知指标（包括跳数、接收信号强度、缓冲区占用率和功耗比）。主要思想是每个节点根据当前网络状态使用认知指标自适应地改变其父节点。显然考虑的认知指标越多，在选择父节点时获得的好处就越多，但是这样也可能会出现复杂的决策问题。为了解决这一问题，提出了基于RL 的父节点选择算法，该算法选择激励最高的节点作为父节点，算法2 给出了父节点选择的详细过程。给定一个状态S，每个节点根据贪心算法在相邻节点中选择一个父节点（第④～⑤行）。当父节点选择完成时，节点观察网络环境中的激励R和新状态S′（第⑥～⑧行）。节点向候选父节点发送加入请求（第⑨行）。选中的父节点接收到加入请求消息后，以接受加入消息或拒绝加入消息回复相应节点（第⑫～⑱行）。每个节点都会通过反复实验找到最优的父节点。

由于节点选择到汇聚节点的跳数与自己相同或更少的相邻节点作为父节点，因此节点的层次级别是根据跳数自主配置的。但是，每个节点可以选择一个同级的邻居节点（即到sink节点的跳数相同的节点）作为父节点，因此可以生成一个循环。为了检查父节点和子节点之间的循环，每个节点向候选父节点及其子节点列表发送一个连接请求消息（第⑨行）。接收连接请求消息的节点根据子节点列表检测一个循环（第⑲～㉔行）。如果没有检测到循环，节点将回复接受加入消息。否则，它返回一个拒绝加入的消息。

3.3 父节点更换率

由于无线传感器网络中的网络状况变化频繁，每个节点都需要定期更新父节点。例如，如果父节点长时间不更新，则特定节点负载过大。为了实现拓扑结构的稳定，每个节点都会根据Hello 消息间隔定期更新其父节点。但是，如果节点频繁更改父节点，可能会产生额外的开销。

4 仿真实现

4.1 仿真设置

仿真参数如表1 所示，进行100 次模拟，置信区间为95%。具体来说，运行3 600 s 的模拟，并将网络大小设置为5 000 m×5 000 m。为了构建大规模网络，将传感器节点的数量设置为100 个，sink 节点的数量设置为5。为了构建树状拓扑，sink 节点每隔20 s 周期性地广播一条构建消息。每个节点收到构建消息后，更新邻居表中sink 节点的跳数，并开始选择父节点。此外，所有节点每隔5 s 会周期性地向邻居发送Hello 消息。将构建消息和Hello 消息的大小分别设置为192 bits 和128 bits。为了验证所提出的方案，根据网络条件的变化自适应地改变父节点，从而在多个目标之间找到合理的权衡，并通过改变流量比特率和误码率来观察性能指标。为了模拟拥塞，将流量比特率从1 000 bits/s 改为5 000 bits/s。此外，将误码率从10-2更改为10-6，以使链路条件为动态。

表1 仿真参数Table 1 Simulation parameters

所设计的对比算法是基于线性加权和的父节点选择算法[17]和基于MCDM 的父节点选择算法。基于线性加权和的方案考虑了跳数、缓冲区占用率、链路质量和剩余能量作为决策指标，且每个指标的权重以相同的比例固定。基于MCDM 的父节点选择方案，当网络不稳定时，增加接收信号强度的权重，选择链路条件好的父节点。如果候选节点的链路条件差异不显著，则每个节点将另一个缓冲区占用率低、剩余能量高的节点替换为父节点[18]。

4.2 可靠性

根据链路情况，影响报文传递比的主要因素是拥塞导致的缓冲区溢出和误码。如图3 所示，随着流量比特率的增加，所有方案都会因拥塞而造成丢包。线性加权和方案在决策过程中考虑了链路质量。但是，由于多个指标之间的权重是相等的，即使发生缓冲区溢出，父节点也很少改变。由于基于MCDM 的方案具有较高的缓冲区占用率权重，所以其拥塞丢包比基于线性加权和的方案要小。随着误码率的增加，自适应地选择链路质量好的节点，从而获得更好的报文转发速率。

图3 数据包传输率仿真结果Figure 3 Simulation results of packet delivery ratio

然而，在基于MCDM 的方案运行时不能改变指标之间的权重，因此它有一个明显的局限性，即难以响应网络场景的变化。而所提方案通过反复实验来学习如何在运行时应对网络条件的变化，因此能表现出最佳的性能。

4.3 延迟

影响树路由端到端延迟的主要因素是到汇聚节点的跳数和排队延迟。传统树路由是根据到汇聚节点的跳数来选择父节点的，当流量比特率较低时，性能最佳。但是，随着流量比特率的增加，到汇聚节点跳数较少的节点会发生拥塞，导致端到端时延急剧增加。为了解决这一问题，基于线性加权和的算法在决策过程中考虑了具有跳数的拥塞度量。如图4 所示，在基于线性加权和的方案中，由于指标之间的权值相同，随着流量比特率的增加，负载分配并不有效，从而会增加排队延迟。此外，当误码率增加时，可以选择链路质量较好的节点作为父节点，而不是跳数较低的节点，端到端延迟略有增加。

图4 端到端时延仿真结果Figure 4 Simulation results of end-to-end delay

在MCDM 的方案中，决策者预先确定了每个网络环境指标的权重，因此在预配置的网络场景中表现良好，但该方案不能应对运行时发生的网络条件变化。相比之下，每个节点根据网络环境通过Q-learning 学习优化，能够自适应地应对网络条件的变化，具有较好的性能。

4.4 能源效率

增强树路由能耗的主要原因是拥塞和链路断裂造成的丢包重传。在树形路由中，除了能量效率外，还需要平衡传感器节点之间的能量消耗，以保证路由路径的多样性。

传统的树路由是根据当前节点到汇聚节点的跳数选择父节点。流量拥塞会导致大量丢包，数据重传又导致能量消耗的增加，而且当链路质量较差时，重传次数也会增加。为了解决这一问题，基于线性加权和的方案在决策过程中同时考虑了链路质量和缓冲区占用率，但由于多个指标之间的权重没有适当调整，也难以响应网络条件的变化。结果如图5 所示，单位时间能耗最高，死节点数也最多。

图5 功耗比仿真结果Figure 5 Simulation results of power consumption ratio

因为决策者提前知道网络环境，并据此确定合适的权重，因此基于MCDM 的方案比基于线性加权和的方案性能更好。然而在运行时不能调整度量的权重。相比之下，本文方案通过各种认知指标来识别网络环境，并通过反复实验找到优化性能指标的最佳策略。结果表明，该方案比基于MCDM 的父节点选择方案具有更好的性能。

4.5 讨论

由于决策者基于先验知识预先确定了每个指标的权重，因此存在一个明显的限制，即权重不能在运行时更改。为了解决这个问题，使用多个认知指标来识别网络环境，并通过强化学习找到联合优化性能指标的最优策略。此外，使用WMA 来防止认知指标的突然变化。显然通过根据网络条件的变化自适应地改变父节点，在冲突的性能指标之间提供灵活的权衡。

研究表明，使用强化学习方法可以显著提高无线传感器网络中路由性能指标，减少能耗、降低延迟。然而，在实际应用时还需考虑诸多因素如拓扑结构变动、链路质量波动等复杂情况对算法性能带来影响。

5 结语

为了在树路由中实现多个目标，重新考虑在复杂部署场景中寻找最优父节点。通过强化学习利用目标网络的经验数据找到最佳父节点。分析了3 种类型的认知指标来应对各种网络场景；提出了将RL 应用于树路由的系统模型，并给出了树构造、环路检测和父节点更新的具体算法；定义状态空间、动作集和激励函数，通过强化学习找到最佳父节点。通过综合仿真，证明了本文提出的父节点选择方案可以在端到端延迟、分组传输比和能量消耗等性能指标之间取得平衡。