姚铭明, 曹霑懋, 黄启嵩, 单志龙

(华南师范大学计算机学院, 广州 510631)

无线网状网[1](Wireless Mesh Networks,WMN)以网状路由器(Mesh Router,MR)、网状客户端(Mesh Client,MC)为节点组成，节点具有中继转发数据包的功能. 其中，可以直接接入互联网的MR被称为网关(Gateway,GW)，GW是连接无线网状网和互联网之间的桥梁，MR和GW一起称为无线骨干网络. 每个从MC发出的路由请求通过其关联的MR传输到骨干网络中，路由请求在到达与互联网相连的GW前需要通过多个MR.

由于无线网状网的灵活性和安装的简单性,允许其网络基础设施的低成本部署. 同时，无线网状网可用于扩展有线网络覆盖范围,可实现随时随地的连接，为无线网状网的普及提供了良好的基础. 若无线网状网只配置单个接口和信道，会存在一定的局限性，因为其节点不能同时发送和接收数据包. 为了提高无线网状网的性能和容量，每个节点可以配备多个接口和多个信道. 然而，由于无线信道资源的稀缺性和无线接口所支持的信道数量有限，在传输数据时网络性能会受到干扰和拥塞的严重影响，从而导致了一定的丢包和延迟[2]. 特别地，在无线网状网中，多个用户同时发出传输请求的情况时常出现[3]，多对传输请求同时发生而导致网络波动和产生干扰，这个共有现象称为多并发流问题. 在多并发流下，不同数据流所选择的路径不可避免地存在节点交叉或者局部链路重叠的情形，易引起数据流间的资源竞争，抢占节点资源，从而造成负载不均衡甚至拥塞现象. 另外，借助无线网络的设备数量呈指数级增长. 电脑、智能手机和平板设备等各种智能设备都需要借助无线网状网进行互联网接入[4]，在这些设备上运行的应用程序亦呈指数级增长，从而导致网络中的数据量也呈指数级增长，加剧了多并发流问题的严重性.

传统的路由方案总是基于固定的规则，只考虑单一的网络度量，如吞吐量、丢包率和端到端延迟等，而没有综合考虑整个网络环境情况. 在无线网状网中，单独使用这些指标来选择路由流量的路径可能不是一个好的解决方案. 例如，路径的跳数可能是最优的，但是该路径不一定是最优的，可能具有更多的干扰. 因此，为了能在合理时间内获得联合的最优解，我们需要以几个指标为前提去优化无线网状网中的路径.

在无线网状网中，路径寻找是针对一个流量请求，在源节点到目标节点之间确定一条可传输数据连通路径，该路径由有限个两两相连节点的链接构成，即节点的序列；信道分配问题是为所确定路径上的所有链接分配可用的信道；调度是将一个传输时隙分配给所找路径上的每一个链接；路由策略是无线网状网中从每一个路由请求的初始节点到目的节点的路由规划. 对于多并发流的问题，单从路由、信道分配或者调度方面考虑都被证明是NP-难问题[5]. 为了解决这个问题，学者们从不同的角度提出了解决方案，如：提出了联合信道分配和路由的方案来提高网络性能[6]；为了保证吞吐量，从服务质量(Quality of Service,QoS)的角度出发，基于OLSR路由协议[7]提出一种新的路由方案[8]；为改进功率分配、干扰和拥塞，提出了一种贪婪式的算法[9]. 然而，无线网状网以动态信道和负载条件为特征，因此，通过静态的计算路径转发的流量将无法保持高吞吐量. 而且，在高度动态的环境下，使用跟随瞬时网络条件的短期路由策略不能帮助实现长期最优性能，需要智能地根据这些网络环境自适应地选择链路，以实现网络资源的合理使用.

为了解决上述问题, 一个可行的方法是使用强化学习[10]算法. 强化学习已经应用于各种无线网络，如无线自组网络Ad Hoc[11]、无线传感器网络[12]和认知无线网络[13]. 除此之外，在无线网状网路由问题上，有学者利用强化学习得到网络性能表现上更优的方案，该方案考虑了网关周围的关键区域和多个网络性能度量来寻找路径[14]；还有从体验质量(Quality of Experience,QoE)的角度出发，利用强化学习动态调整每个节点发送数据包的策略[15]. 基于文献[11-15]的启发，在COSS方案[16]的基础上，本文提出了基于流量模式的Q-学习路由与调度(Q-learning Routing and Scheduling Concerning Traffic Mode,QRST)方案：依托信道分层模型[17]来表示网络拓扑，利用强化学习中的Q-learning算法寻找路径来完成路由传输，再将路由、信道分配和调度组合起来；根据网络资源的负载情况，自适应地针对每一个路由请求学习最优路由策略，然后进行组合调度优化. 最后，通过设置不同的网络配置进行虚拟计算实验，分析采用QRST、COSS、AODV方案的无线网状网的网络性能.

1 预备知识

1.1 强化学习的介绍

强化学习(Reinforcement Learning,RL)是一种计算学习方法，是智能体不断与环境进行交互，并根据经验调整其策略来最大化其长远的所有奖励累积值的一个过程.

智能体是强化学习的执行个体，我们可以预设参数让智能体根据所处的环境自主做出决策. 如图1所示：当智能体在t时刻选择一个合适的动作at后，环境的状态st变为状态st+1，得到奖励rt+1；然后，智能体继续选择下一个合适的动作，环境的状态又会改变，从而得到新的奖励值，直到完成特定的目标为止.

图1 强化学习模型图解

一个强化学习的系统可以由6个要素组成：(1)智能体的动作a. 具体地，智能体在t时刻采取的动作记为at. (2)环境的状态s. 具体地，在t时刻的环境状态记为st. (3)环境的奖励r. 智能体采取动作at后得到的奖励记为rt+1，该奖励会在t+1时刻得到. (4)智能体的策略π. 策略是一个智能体的行为模型，是从状态到行为的映射函数，即智能体会依据策略π来选择动作. (5)值函数. 值函数是一个期望函数，表示的是智能体在当前状态s和策略π的累积折扣回报，一般有2种表示形式. 第1种表示形式为：

(1)

其中，γ为折扣因子，取值为0<γ<1，用来权重即时和未来的奖励;第2种表示形式为：

(2)

表示的是智能体在当前策略π下，给定状态s和动作a时的累积折扣回报. (6)模型. 模型是用来预测环境下一步可能发生的变化的一套描述系统，环境状态的转化模型可以表示为一个概率模型，是在状态s下采取动作a后转到下一个状态s′的概率的一个集合.

一般来说，决策是由一个智能体在与环境交互的过程中，通过反复学习做出的. 最终目标是让智能体学习到一个最优策略，使其在与环境交互过程中的累积奖励最大化. 智能体面临的一个挑战是利用与探索：智能体必须利用以前学习的知识，但又必须探索其环境中的新动作和状态，以便寻找更好的策略.

1.2 网络模型的介绍

本文采用的是笛卡尔乘积(Cartesian Product of Graph,CPG)模型[18]，以便在无线网状网中对多并发流的路径进行讨论和研究. 多并发流下的无线网状网结构可用Γ={G,I,Ω,ξ,{(fi,di)}}来表示，其中：

(1)G=(V,E)为一个无线网络的网状拓扑结构图，其中|V|代表节点数量，|E|代表边的数量；

(2)I为G上节点之间的无线干扰关系；

(3)Ω={c1,c2,…,cq}为网络拓扑图上可用正交信道的集合，其中q为可用正交信道的数量；

(4)ξ为节点接口数量；

(5){(fi,di)}(i=1,2,…,ρ)为多个源节点与目标节点对的集合；

(6)Λ={λi}={(fi,di),zi}为列表{(fi,di)}相对应的传输请求队列，zi>0为数据的大小.

在该无线网状网模型中，I的干扰判定条件为：

(1) 2个不同的发射节点sender_node间的距离不小于2跳；

(2) 2个不同的接收节点receiver_node间的距离不小于1跳；

(3) 发射节点sender_node与接收节点receiver_node间的距离大于1跳.

同一信道中的可共存条件为(1)∧(2)∧(3).

2 QRST方案的设计

本文在COSS方案的基础上，针对多并发流问题提出了一个基于网络负载的智能调度方案. 该方案由路由方案和调度方案组成.

2.1 路由方案的设计

首先，获取正交信道的数量g，CPG网络模型将网络拓扑分为g个虚拟的网络层，每层的网络拓扑结构相同，但各个节点之间所属的正交信道不同. 每个节点上有多个信道和接口，节点的身份转化为g个虚拟网络层信道差异的节点，虚拟计算时仍把分层的节点看作同一个节点. 然后，为每一条路径分配可用信道时，需逐层检查当前网络层下信道的可用性，若该路径上的当前链接在当前网络层下能满足同一信道中链接可共存条件的干扰关系I，则将当前网络层所属的信道分配给链接.

QRST方案中，在路径发现的阶段，对给定路由请求的节点对(fi,di)，采用强化学习中的Q-lear-ning算法来寻找路径. Q-Learning算法是一种使用时序差分求解强化学习控制问题的方法，在Q-Learning算法中，将Q值Q(s,a)定义为在状态s下选择行为a并遵循最优策略的估计值. 因此，Q-Learning算法的最终目标是通过估计其Q值来寻找最优策略. 在Q-Learning算法中，学习到Q值，然后使用即时奖励和折扣奖励进行更新，并保存在一个大小为|s|*|a|的状态价值函数表中，其中，|s|为状态的数量，|a|为动作的数量. 在状态中选择的动作的Q值更新如下：

Q(st,at))，

(3)

其中，α(0<α<1)表示学习率，γ(0<γ<1)表示折扣系数. 如果α=1，则智能体将会忘记其先前学习的Q值，并用最新估计的奖励替换该Q值.γ越接近于0，智能体越注重下一步的奖励；γ越接近于1，智能体越注重整体的奖励情况. 更新迭代在利用与探索之间的折衷采用ε-greedy策略，该策略通过设置一个较小的ε值，使用1-ε的概率贪婪地选择目前认为是最大行为价值的动作，而用ε的概率随机从所有m个可选动作中选择一个. 用公式表示为：

(4)

ε-greedy策略的优点是：当时间趋于无穷大时，该策略可以保证每个动作被无限次地采样，这是Q-learning算法收敛的必要条件. 利用Q-learning算法寻找路径流程如算法1所示.

算法1Q-learning寻找路径算法

输入：迭代次数T,状态s,动作a,学习率α,折扣系数γ,探索率ε

输出：状态价值函数表

初始化s和状态价值函数表

forTdo

使用ε-greedy策略，在状态s下选择动作a，从而确定下一跳节点，并获得新状态s′和奖励值r

更新Q(s,a):

s=s′

ifs′是目标节点

结束当前迭代

else

继续寻找目标节点

end if

end for

rt(st,at)=-Cm(sender_node,receiver_node)+

Ce(sender_node,receiver_node)，

(5)

其中，Cm(sender_node,receiver_node)代表发送节点和接收节点之间所有信道的数量，也是CGP模型的虚拟层层数，Ce(sender_node,receiver_node)代表发送节点和接收节点之间所有被占用的信道数量. 可用资源越多的节点的奖励值越大，反之亦然. 在QRST方案中，能根据网络负载来寻找路径，避免节点负载过重的区域，智能地选择负载较轻的节点，从而避免资源竞争的现象.

QRST方案的路由模型(图2)寻找路径的步骤如下：首先，根据网络拓扑结构建立强化学习智能体和初始化状态价值函数表：将没有相连的节点赋予一个非常大的负值，以确保智能体无法到达相连的节点，其他相连节点的Q值初始化为0. 然后，智能体将路由请求作为输入，通过源节点和中继节点尝试寻找目的节点，每当节点i向其邻居节点j发送数据包时，节点j通过反馈信号做出响应，该反馈信号表示其到达下一个邻居节点的估计值. 在QRST方案中，反馈的Q值是节点i到节点j的网络资源剩余量. 节点i收到反馈后，智能体利用式(3)来更新当前位置对应状态价值函数表中的Q值，即Q(i,j)，随后继续为下一个节点寻找其邻居节点，直到找到目的节点. 再根据设定好的迭代次数，继续重复为该路由请求寻找路径，从而根据网络资源迭代收敛状态价值函数表，寻找到一条最优路径. 路径上的每条链路都与网络资源的剩余量相关联，对于状态价值函数表中每个状态-动作对，在经过采样之后，计算其Q值，并将此Q值用于估计沿着路由向目的节点发送数据包时的网络资源量. 由于使用了Q值的查找，因此，QRST方案的收敛性得到了保证[18].

图2 QRST方案的路由模型

2.2 调度方案的设计

在QRST方案中，首先，根据输入的每一个路由请求λi，为其源节点与目标节点对(fi,di)找到合适的路径，该路径由一个或多个两两相连的节点对构成；然后，为每个节点对分配信道和时隙来传输数据，在一个时隙下，激活更多的链接以传输更多的数据包和路由请求[19]，从而有效利用网络资源.

为了能够清晰地阐述该调度方案，需要提前定义若干符号. 记Τ为网络拓扑的更新周期，Li为节点对(fi,di)的路径长度，P为所有可兼容路径的集合，Fc(j)为判断当前节点j是否有可用信道的函数. QRST方案的目标是在Γ中实现网络资源的最大化利用，即最大化多并发流链接的数量. 调度方案的具体流程如下：

(1)在调度开始前，先收集拓扑网络的信息，包括节点状态、传输请求和拓扑结构等；

(2)在调度时，将周期Τ分为多个时隙ti(ti=1,2,…,T). 在每个时隙中，方案先用Q-lear-ning算法为每一个路由请求寻找路径，然后逐一遍历未加入集合P的路径是否为当前时隙下的可兼容路径. 若满足同一信道中链接的干扰关系I，则将该路径加入P；

(3)若当前网络资源已经无法分配信道，则进入下一个时隙，再逐一检查未加入P的所有路径，直到所有路径都加入到P.

参考文献[19],该调度方案(算法2)将网络拓扑的更新周期分为多个时隙，通过逐一遍历所有路径，为符合可兼容条件的路径分配信道和时隙，从而实现所有路径的组合优化调度，最大化同一时隙下可兼容路径的数量，提高了网络资源的利用. 通过这种方式组合正交信道上若干条无干扰链路构成的路径被称为可兼容路径. 该路径上的所有链路都分配了合适的信道，避免了无线干扰I，使其不会与先前已分配好资源的路径产生冲突，以实现多并发传输.

算法2基于网络负载的调度方案

输入：网络结构Γ

输出：可兼容路径集合P

初始化P

初始化信道和接口

forTdo

for 路由请求集合Λdo

Q-learning算法为给定路由请求的节点对(fi,di)寻找路径;

for 路径的链接Ldo

if 两节点间存在可用信道

在时隙t下，为该链接分配信道

else

不分配信道，且将该链接放到下一个时隙t+1下

end if

end for

if 路由请求(fi，di)所有的链接都分配了信道

将该信道加入P中

end if

end for

end for

3 虚拟计算实验与结果分析

本节通过python程序虚拟计算，比较在不同网络资源配置和路由请求下，分别采用QRST、AODV、COSS方案的无线网状网的网络性能变化.

实验场景是在1 000 m*1 000 m的区域范围内随机生成36个节点，节点间的传输距离为100 m，如图3所示.

图3 36个节点的随机网络拓扑图

为保证实验的准确性，每组实验都要进行10次，每次实验条件中仅路由请求的节点对不同，最终取10次实验结果的平均值以避免随机性. 在Python虚拟计算实验下，每一跳可以传输一个数据包，所需时间均为1个时隙(5 ms)，1个时间周期为0.5 s(100个时隙). 具体参数如下：可用接口数量R分别为4、8、12、16、20，可用信道数量分别为8、16、32，学习率α=0.01，探索率ε=0.1，折扣因子γ=0.9，数据包大小为1 MB，数据包个数为250个，链路容量为200 MB/s，传输距离为150 m.

在性能指标上，采用能够反映无线网状网性能的指标：无线网状网的平均吞吐量、平均激活链路数量和路由请求传输完成时间. 这些指标的具体定义如下：

(1)平均吞吐量：单位时间内无线网状网中所有目标节点所接收到的数据总量. 该指标可以有效衡量网络的性能：平均吞吐量越高，则表示网络性能越好.

(2)平均激活链路数量：单位时间内无线网状网中激活的链路数量. 该指标为网络中并发的链路数量，可以有效衡量网络性能.

(3)路由请求传输完成时间：无线网状网中所有路由请求从开始传输数据到全部数据被接收所需的时间. 该指标可以有效地评估网络的承载能力:传输所需时间越短，说明网络在单位时间内传输的数据量越多，单位时间内能够承载的数据流数量越多，网络承载能力越强.

3.1 不同流量模式下的网络性能表现

在固定网络资源配置下，通过改变随机路由请求的数量，分析采用QRST、COSS和AODV方案的无线网状网的性能表现. 由在不同数量的路由请求下的平均吞吐量(图4)可知：采用QRST方案的平均吞吐量明显高于采用COSS、AODV方案的，这表明QRST方案充分利用了各个时隙下的网络资源来传输数据包，同时能够有效避免高负载现象的出现；随着路由请求数量的增加，QRST方案的性能优越性愈加明显.

图4 采用3种方案的无线网状网在不同数量路由请求下的平均吞吐量(|R|=16∧|C|=32)

由相同的网络配置下的平均激活链路数量(图5)可知：(1)平均激活链路数量的曲线趋势与平均吞吐量的大体一致；(2)采用QRST方案的平均激活链路数量高于采用COSS、AODV方案的，其原因是QRST方案充分利用了网络资源，为每条链路选择合适的分配信道，并发的链路之间不产生干扰，从而使每条链路都能高效率地传输数据.

图5 采用3种方案的无线网状网在不同数量路由请求下的平均激活链路数量(|R|=16∧|C|=32)

由相同网络配置下的传输时间(图6)可知：采用QRST方案的传输时间比采用另外2种方案的略长一些，其原因可能是平均激活链路的数量多了，需略微牺牲传输时间来换取更高的吞吐量和激活的链路数量.

图6 采用3种方案的无线网状网在不同数量路由请求下的传输时间(|R|=16∧|C|=32)

为了探讨QRST方案中Q-learning算法的迭代次数对网络性能表现的影响，将迭代次数分别设置为300、400、500次. 由图7可知：在足够多的迭代次数下，采用QRST方案的无线网状网在网络性能表现上并没有太大变化.

图7 采用QRST方案的无线网状网在不同迭代次数下的多组路由请求的平均吞吐量(|R|=16∧|C|=32)

在确定网络配置和流量模式下，分析QRST方案中学习过程对网络性能的影响. 由图8可知：(1)前150次迭代过程的阶段中，采用QRST方案的平均吞吐量会有一定的波动，这是因为此时Q还未完全收敛，所以会有不同的路径，从而影响网络性能的表现；(2)到了150次的学习次数后，平均吞吐量的表现逐渐稳定在一个范围内波动.

图8 30对路由请求的学习过程对平均吞吐量的影响(|R|=4∧|C|=8)

3.2 不同网络资源配置下的网络性能表现

在确定随机路由请求数量为30对的情况下，将网络资源配置设置为可控变量，分析采用QRST、COSS、AODV方案的无线网状网在不同网络资源配置下的平均吞吐量.

由图9至图11可知：

图9 |C|=8且不同接口数时采用3种方案的无线网状网的平均吞吐量

图10 |C|=16且不同接口数时采用3种方案的无线网状网的平均吞吐量

图11 |C|=32且不同接口数时采用3种方案的无线网状网的平均吞吐量

(1)当|C|=8时，采用QRST方案的平均吞吐量始终低于采用COSS、AODV方案的. 其原因是QRST方案中Q-learning算法寻找路径是采用信道数量作为奖励值，所以在信道资源匮乏的时候，采用QRST方案的平均吞吐量要低于采用COSS、AODV方案的.

(2)在|C|=16时，采用QRST方案的平均吞吐量与采用COSS方案的相差无几，两者均稍高于采用AODV方案的；随着接口数量的增加，采用QRST方案的平均吞吐量高于采用COSS、AODV方案的.

(3)在|C|=32时，随着接口数量的增加，QRST方案所带来的性能提升要优于另外2种方案：在|R|=12时，采用QRST方案的平均吞吐量已高于采用COSS、AODV方案的，而且是大幅度的提升，说明在|R|=12时，QRST方案已经能充分利用网络资源，而采用COSS、AODV方案的平均吞吐量要在|R|=16时才能有如此大幅的提升，但仍低于采用QRST方案的，说明QRST方案在网络资源充足的前提下，能够较好地应对无线网状网中多并发流的问题.

4 结论

为了解决无线网状网中多并发流这一现象引发的路由和网络资源配置紧张的问题，在COSS方案的基础上，本文提出了基于流量的Q-学习路由与调度方案(QRST). 该方案首先获取网络的基本信息，包括拓扑结构和路由请求；然后使用强化学习中的Q-learning算法来寻找路径；基于所得到的路径，为路由分配无干扰的信道，形成可兼容路径；最后组合调度所有可兼容路径完成传输. 虚拟计算实验表明：QRST方案在不同流量模式下能取得较好的网络性能，在一定的网络配置下的网络性能也优于采用AODV、COSS方案的.