Q-Learning Based Distributed Adaptive Algorithm for Topological Stability

为了说明链路稳定性研究在移动自组织网络中的重要性，通过图1所示场景进行简要说明。从图1中可以观察到，移动自组织网络包含4个节点A，B，C，D。节点A需要向D发送数据包，所以节点A广播路由请求分组并发现要发送数据包到D必须经过节点B或C。此时节点B正迅速远离A和D节点，而节点C缓慢向A移动。如果节点A选择B作为转发节点，由于B的移动性，(A, B)链路不稳定，很容易断开。由于C是缓慢向A节点移动，所以在传输的过程中(A, C)链路相比(A, B)将会有更长的时间保持良好稳定联接。A选择C作为下一跳传输节点转发到D，更有助于信息的可靠网络传输。通过上述场景可以看出，根据平均联接有效时长选择最稳定的路径可以避免未来链路失效，从而改善路由。

由于每个节点具有移动性，作为最短路径的一条链路可能在联接建立之后迅速断开。中断的链路会导致路由服务质量下降。因此，在MANET中节点之间构建相对稳定的拓扑联接可以避免链路故障，很大程度上改善了网络通信服务质量。

强化学习算法是一类经典的在线机器学习算法，智能体根据环境状态输入，通过与环境交互得到反馈奖赏来选择当前环境状态的最佳动作^[7]。强化学习系统主要包括5个部分：环境、状态$s$、动作$a$、奖励$r$和智能体(Agent)。强化学习以“尝试”的方式进行学习和强化，并形成好的动作策略。整个系统的框架如图2所示。

强化学习是由仿生学习、自动控制等理论发展而来，其基本原理是：如果Agent的某个行为策略导致环境正的奖励(强化信号)，则此行为策略便会加强，反之减弱。Agent的目标是在每个离散状态学习最优策略使期望奖赏最大化。

强化学习中Q-learning算法由于其较好的算法性能，被广泛研究和使用。其状态集$S$由集合$\{ {{s_1},{s_2}, \cdots ,{s_i}, \cdots } \}$组成，动作集$A$由$\{ {{a_1},{a_2}, \cdots ,{a_j}, \cdots } \}$组成。不同状态动作对$( {{s_i},{a_j}} )$对应Q值矩阵$i$行$j$列的元素，状态动作集对应的Q值可表示为Q值矩阵。分布式强化学习时，每个节点独立训练学习，并保持一个Q值矩阵不断学习更新。定义评估函数值${Q_t}( {{s_i},{a_j}} )$为Agent在$t$时刻状态${s_i}$下选取动作${a_j}$计算获得的Q值，其中${s_i} \in S$，${a_j} \in A$，并且在下一状态选取最优动作的折扣奖励累积值。在Q-learning算法不断的学习过程中，每个网络节点的Agent通过递归的方式不断更新该节点Q值，以获得最大的长期累积奖励，最终可以得到预期目标下此节点的最佳学习策略。各个节点的Q值更新函数为^[7]：

式中，$\alpha $为学习率，$0 < \alpha < 1$；$\gamma $为奖励折扣因子，$0 < \gamma < 1$；${a_j}$为当前动作，${a'_j}$为策略在${s'_i}$状态上对应的最大Q值动作；${s_i}$为当前状态；${s'_i}$为${s_i}$执行动作${a_j}$后转移到的状态；$R_{{s_i} \to {{s'}_i}}^{{a_j}}$为在状态${s_i}$下执行动作${a_j}$后转移到状态${s'_i}$得到的奖励值；$\mathop {\max }\limits_{{{a'}_j}} {Q_t}( {{{s'}_i},{{a'}_j}} )$表示状态${s'_i}$下所有状态动作对中最大Q值，代表当前策略取得的新状态最好预期值对当前策略Q值计算的影响。

强化学习应用到MANET中，多数情况下是解决动态情况下找寻最短路径的问题和解决QoS问题^[8-10]。本文在强化学习的基础上结合移动自组织网络中节点之间信息交互时携带的RSSI值，提出了自适应拓扑稳定性算法寻找稳定链路联接。

基于Q-learning 的分布式自适应拓扑稳定性算法是由强化学习Q-learning算法与自适应区间更新算法两种方法结合产生一种预测周围移动邻居节点拓扑稳定联接的算法。该方法利用强化学习思想建立模型，通过实时处理当前节点接收到的邻居节点RSSI值进行强化学习，并对此邻居节点的链路联接状态进行预测，每个节点都维护一张状态Q值矩阵表以及一个自适应学习区间，根据RSSI值来分区间判断当前链路质量，算法的结构框图如图3所示。

图3中，如果当前节点接收到某个邻居节点RSSI值处于自适应区间$[a, b]$内，则执行Q-learning算法进行联接状态预测；若处于自适应区间外，则执行联接状态直接决策。自适应区间$[a, b]$的边界依据直接决策失误情况进行上、下边界的区间扩展调节。通过两种方法的结合可以提高判决效率，提升算法判决精度，从而使预测模型更加高效、快速适应环境的变化做出准确状态判断。

自适应区间更新算法服务于Q-learning算法，为其提供更适合的强化学习区间范围。本文假设节点发射功率为0 dBm，考虑环境等因素影响，节点间稳定联接临界强度值为−77 dBm。初始化区间$[a, b]$中上界$a$与下界$b$的值都等于−77 dBm，这样形成3个区间$\left[ {0, a} \right)$、$[a, b]$、$\left( {b, - \infty } \right)$。区间$[a, b]$为Q-learning算法学习区间，进行强化学习决策；区间外$\left[ {0, a} \right)$、$\left( {b, - \infty } \right)$进行状态的直接决策。随着算法执行，区间$[a, b]$的值不断更新，进行区间扩展。自适应区间更新及决策算法流程如下：

1) 设定初始的阈值${d_{\rm {win}}} = - 77\;{\rm{dBm}}$，节点根据当前采集到某邻居节点的RSSI，当大于阈值判定为稳定联接状态${s_1}$，小于阈值判定为非稳定联接状态${s_2}$。状态变量$s$表示节点与邻居节点的联接状态，表示为：

2) 当前节点根据其邻居节点的RSSI，按照式(2)进行状态判定，作为下一时刻节点与此邻居节点联接状态的预测$\hat s$；假设下一时刻信号强度为$\rm{RSS} I'$，又根据式(2)判定下一时刻实际联接状态为$s'$，若$s' \ne \hat s$，则根据情况调整区间$\left[ {a,b} \right]$，初始状态$a = b = - 77\;{\rm{ dBm}}$。按照流程1)判定出错时，若$a < \rm{RSSI} $，则调整$a = \rm{RSSI} $；若$b > \rm{RSSI} $，则调整$b = \rm{RSSI} $。直接决策调整边界公式表示为：

3) 直接决策：按照式(2)进行状态直接决策，在直接决策区间$\left[ {0, a} \right)$内，直接判决为${s_1}$状态；在直接决策区间$\left( {b, - \infty } \right)$内，直接判决为${s_2}$状态。

4) 节点根据每一邻居节点前后时刻接收信号强度值，按照式(2)进行决策区间边界调整；按照流程3)进行直接决策区间的状态判定；而对于直接决策区间外的自适应区间$[a, b]$，按照Q-learning算法进行强化学习和状态决策，并对Q值矩阵进行持续更新。

5) 不同时刻，节点按照流程2)～流程4)邻居节点接收信号强度进行边界循环更新和状态决策。

该算法可以异步分布式执行，网络中各个节点独立按照上述算法进行自主学习决策。每个节点对其各邻居节点进行联接状态稳定关系判定，最终由稳定联接状态的邻居节点构成此节点的稳定邻居集。由相互稳定联接的节点形成移动无线自组织网络的稳态拓扑。

基于Q-learning的分布式自适应拓扑稳定性算法中，每一个移动节点可以视为一个Agent，这样整个网络的动态变化都可认为是一个分布式多Agent协作系统。对于每个Agent，假设其环境状态集为$S$，动作集为$A$，奖赏函数为$R_{{s_i} \to {{s'}_i}}^{{a_j}}$，动作选择策略为${\text π} ( {{s_i},{a_j}} )$。根据Q-learning算法基本结构描述如下：

1) 状态集$S$：由离散的状态构成。状态定义为：

式中，${s_1}$状态为根据当前接收到某邻居节点RSSI，节点与某邻居节点处于稳定联接状态；${s_2}$状态为根据当前接收到某邻居节点RSSI，与某邻居节点处于非稳定联接状态。

2) 动作集$A$：每个Agent可以采取的动作分为预判稳定联接状态和预判非稳定联接状态两个类型。动作集定义为：

式中，${a_1}$为预判稳定状态；${a_2}$为预判非稳定状态。

3) 奖励函数$R_{{s_i} \to {{s'}_i}}^{{a_j}}$：${s_i} \to {s'_i}$表示前后时刻的实际状态转移。强化学习过程中，奖励函数是Agent在状态${s_i}$下采取行动${a_j}$预判状态，参照实际转移状态${s'_i}$后的奖惩值，它表明在特定状态下采取动作决策的好坏程度。在算法设计的过程中，设定奖赏函数值如表1所示，由8种情况组成。由于非稳定联接关系误判为稳定联接关系，以及稳定联接关系误判为非稳定联接关系，上面两种情况造成的网络影响相对恶劣，所以加重了奖惩数值，分别予以$R_{{s_1} \to {s_2}}^{{a_1}} = - 5$和$R_{{s_2} \to {s_2}}^{{a_1}} = - 5$的惩罚。

根据表1分析，可以得到奖赏函数定义式：

式中，${s_i}\xrightarrow{{{a_j}}}{s'_i}$表示状态${s_i}$采取动作${a_j}$，发生状态转移${s_i} \to {s'_i}$。不同状态执行动作后，根据执行动作的状态预判与转移的实际状态的异同设置奖励值。综合上述状态、动作、奖励值的结构描述得到本文Q-learning算法的状态转移图如4所示。

4) 动作选择策略${\text π} ( {{s_i},{a_j}} )$：Q-learning算法的策略选择决定了Agent怎样去平衡探索和开发之间的问题。Agent通过探索可以持续学习发现更优的策略；通过开发选择转向期望状态最佳动作。本文算法选择$\varepsilon - $贪心策略来确定最优动作，每次选择Q值最大的动作。即：

5) 更新Q值函数：综合动作、奖励值的设计，根据式(1)的方法进行函数的更新。

为了验证算法有效性和稳定性，通过Python仿真环境设计了3组实验来研究本文所提出算法的性能。为了能够更加真实地建立MANET中节点运动的随机性以及各个节点之间速度以及运动方向的随机性模型，在仿真场景的设计中采用了MANET中经典的运动模型—随机游走移动模型^[11](random walk mobility model, RWM)来验证本文算法性能。

实验设定在150×150 m²的网络区域内生成移动节点，每个移动节点选择随机的方向运动、随机的运动时间、随机的停顿时间，实验中设定节点数目为15个且每个节点之间的运动互不影响。表2所示为仿真实验的系统参数。

根据上述的仿真参数设定，将本文算法应用到RWM移动模型中进行算法的有效性测试。仿真中设定RSSI的测量模型为自由空间传播模型^[12]，计算公式如下：

式中，Loss是传播损耗，单位为dB，与传输路径有关；$d$是距离，单位为km，$f$是工作频率，单位为MHz。假设各个节点发射信号为窄带信号，工作频率为2 400 MHz，并且发射功率为0 dBm时，可以得到${\rm{RSSI = }} - {\rm{Loss}}$，根据节点的最大通信距离$d = 0.07$时计算得到RSSI值为$ - 77\;{\rm{ dBm}}$。考虑电磁波在空气中的损耗，设定了可以稳定联接的临界值为$ - 77\;{\rm{ dBm}}$。

在算法开始执行前，设定初始的学习迭代次数为200轮、通过学习200轮之后得到策略表以及强化学习区间，对测试数据进行100轮预测来计算准确率，将100轮预测的联接状态结果与节点在实际移动过程中各个节点联接状态进行统计平均，计算出每个节点在100轮预测过程中的准确率。

图5为仿真环境都相同的情况下，分别设定不同学习率$\alpha $为0.1、0.5、0.7的准确率值对比图。

根据图5中不同学习率$\alpha $对准确率的影响曲线分析可知，当学习率$\alpha $的取值为0.1时所有节点的准确率值均维持在95%左右，并且各个节点之间的预测准确率变化值相差不大，整个曲线变化比较平缓；而在学习率$\alpha $取值为0.5或0.7时准确率比0.1时均有所下降，并且各个节点的预测准确率相差变大，曲线的变化程度较明显。出现该现象是由于在执行本文算法进行预测的过程中，节点主要根据邻居节点过去运动经验来判断下一传输时刻联接的状态程度，如果学习率$\alpha $增大将增大Agent的探索过程则对节点的运动经验的取值变小，从而导致节点的预测错误的几率增加。但是在不同学习率$\alpha $的影响下准确率维持在0.8～0.95，从而证明算法的稳定性。因此，在接下来的实验过程中均选取学习率$\alpha $为0.1作为本文算法中的参数。

为了证明算法的有效性，通过在RWM模型中分别应用本文提出的基于Q-learning的分布式自适应拓扑稳定性算法与通过强化学习算法直接得到策略表来判断稳定联接次数比较。实验设定两次仿真环境均相同的情况下，分别统计测试数据100轮中每个节点预测联接状态的准确次数率。

根据图6所示，本文提出的基于Q-learning的分布式自适应拓扑稳定性算法的准确率比单独使用Q学习算法的准确率整体提高了30%左右，故本文算法在预测的准确率方面明显优于单独使用Q学习算法，其原因是各个Agent通过自适应的强化学习区间的不断更新将每次的学习变化范围扩大，自适应区间外直接判断联接状态，自适应区间内随着不断的强化学习经验的积累做出更加精确地预测，提升算法的性能。两种算法的比较也说明本文算法的有效性。

图7为通过随机的抽取某一轮预测过程中单个节点预测得到的网络拓扑联接关系，与图8的节点在实际运动过程中的真实联接关系进行比较。实验仿真环境与上述两个实验相同，仿真中实际联接稳定的阈值设定为${d_{\rm {win}}} = - 77\;{\rm{ dBm}}$，根据设定阈值判断稳定联接邻居节集。

根据图7中处于1号节点通信范围内的节点集合为{4,9,10,13,15}，在预测稳定拓扑联接过程中，生成的联接关系集合为{4,10,13,15}，预测出9号节点不能在下一传输时刻稳定联接。通过预测拓扑联接关系与图8真实拓扑联接关系比较表明，预测结果与真实联接关系相一致。强化学习的过程中每个Agent都会对其他节点的运动特性有累积性的学习，不会因为节点处于通信范围内判断为稳定联接链路，Agent会根据节点当前的运动状态以及策略表中学习得到的经验来有效避免在短时间内可能会快速断开的链路联接，所以9号节点在预测过程中被判断非稳定联接状态。

本文通过研究MANET中移动节点对网络拓扑影响，提出了基于强化学习的分布式自适应算法。算法中每个节点通过对其他节点运动特性学习得到下一传输时刻稳定联接的邻居集合，通过稳定联接集合预测移动节点之间网络拓扑的稳定联接关系，可以更好地适应网络拓扑变化。MANET中稳定的拓扑联接关系很大程度上改善了路由选择，同时也提高了网络通信服务质量。实验结果表明，基于Q-learning的分布式自适应拓扑稳定性算法高效稳定且准确度高，能够有效地实现网络拓扑联接的稳定性选择。