基于粒子群优化算法和博弈论的网络学习控制系统带宽调度

第36卷第7期 北京科技大学学报 Vol.36 No.7 2014年7月 Journal of University of Science and Technology Beijing Jul.2014 基于粒子群优化算法和博弈论的网络学习控制系统带 宽调度 严 翔”，李洪波，王立德”四，申萍 1)北京交通大学电气工程学院，北京1000442)清华大学计算机科学与技术系，北京100084 ☒通信作者，E-mail:ldwang(@biu.cdu.cm 摘要研究了双层网络学习控制系统的带宽调度优化问题.为了合理分配子系统的带宽，引入了网络定价体系和动态带宽 调度方法，建立了非合作博弈模型，从而将网络控制系统的网络资源分配问题转换为非合作博弈竞争模型下的Nh均衡点求 解问题.在此基础上，采用粒子群优化算法得到此框架下的纳什均衡解，并进一步给出了网络控制系统的时间片调度方法 仿真结果表明了所提方法的有效性 关键词网络控制系统：定价：博弈论：粒子群优化算法 分类号TP302.7 Bandwidth scheduling of a networked learning control system using particle swarm optimization and the game theory YAN Xiang",LI Hong-bo2,WANG Li-de,SHEN Ping 1)School of Electrical Engineering,Beijing Jiaotong University,Beijing 100044,China 2)Department of Computer Science&Technology,Tsinghua University,Beijing 100084,China Corresponding author,E-mail:ldwang@bjtu.edu.cn ABSTRACT The optimal bandwidth scheduling problem was studied for a two-ayer networked learning control system (NLCS).A dynamic bandwidth scheduling methodology based on the network pricing mechanism was proposed to allocate the bandwidth for each subsystem,so the network resource allocation problem was transformed into the solution of the Nash equilibrium with a non-cooperation game model.Under this framework,particle swarm optimization (PSO)was used to obtain the Nash equilibrium for NLCS,and the time slice scheduling method was also provided.Simulation results were given to demonstrate the effectiveness of the proposed ap- proach. KEY WORDS networked control systems:pricing:game theory:particle swarm optimization 网络控制系统(networked control systems,NC- 包括移动机器人、汽车控制以及航天器等A-.无 Ss)是一种通过网络形成闭环反馈，集通信网络和控 论采取哪种结构，与传统的点对点直接控制系统相 制系统于一体的分布式控制系统.网络控制系统结 比，网络控制系统的最大特点是系统中的传感器、控 构有两大类，分别为直接结构和分级结构口.前者 制器和执行器并不是直接的点对点连接，而是通过 在应用中，多个控制器可能被封装在一个控制单元 公共网络交换数据和控制信息.此种特性的优势在 来管理多个闭环回路，典型应用包括远程学习实验 于可以实现信息资源共享和远程分布控制，减少系 室和直流电机调速等-；后者在应用中由于远程 统布线、支持模块化设计、配置灵活、安装成本低和 控制器的存在，分级结构有更好的实时性，典型应用 易于维护，广泛应用于国防、航空航天、设备制造、智 收稿日期：20130508 基金项目：中央高校基本科研业务费资助项目(E11JB00310,E12B00140):国家重点基础研究发展计划资助项目(2012CB821206):国家自然 科学基金资助项目(61004021,61174069,61004023)：北京市自然科学基金资助项目(4122037) DOI:10.13374/j.issn1001-053x.2014.07.019:http://journals.ustb.edu.cn

第 36 卷 第 7 期 2014 年 7 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 7 Jul． 2014 基于粒子群优化算法和博弈论的网络学习控制系统带 宽调度 严 翔1) ，李洪波2) ，王立德1) ，申 萍1) 1) 北京交通大学电气工程学院，北京 100044 2) 清华大学计算机科学与技术系，北京 100084  通信作者，E-mail: ldwang@ bjtu． edu． cn 摘 要 研究了双层网络学习控制系统的带宽调度优化问题． 为了合理分配子系统的带宽，引入了网络定价体系和动态带宽 调度方法，建立了非合作博弈模型，从而将网络控制系统的网络资源分配问题转换为非合作博弈竞争模型下的 Nash 均衡点求 解问题． 在此基础上，采用粒子群优化算法得到此框架下的纳什均衡解，并进一步给出了网络控制系统的时间片调度方法． 仿真结果表明了所提方法的有效性． 关键词 网络控制系统; 定价; 博弈论; 粒子群优化算法 分类号 TP 302. 7 Bandwidth scheduling of a networked learning control system using particle swarm optimization and the game theory YAN Xiang1) ，LI Hong-bo2) ，WANG Li-de1)  ，SHEN Ping1) 1) School of Electrical Engineering，Beijing Jiaotong University，Beijing 100044，China 2) Department of Computer Science ＆ Technology，Tsinghua University，Beijing 100084，China  Corresponding author，E-mail: ldwang@ bjtu． edu． cn ABSTＲACT The optimal bandwidth scheduling problem was studied for a two-layer networked learning control system ( NLCS) ． A dynamic bandwidth scheduling methodology based on the network pricing mechanism was proposed to allocate the bandwidth for each subsystem，so the network resource allocation problem was transformed into the solution of the Nash equilibrium with a non-cooperation game model． Under this framework，particle swarm optimization ( PSO) was used to obtain the Nash equilibrium for NLCS，and the time slice scheduling method was also provided． Simulation results were given to demonstrate the effectiveness of the proposed ap￾proach． KEY WOＲDS networked control systems; pricing; game theory; particle swarm optimization 收稿日期: 2013--05--08 基金项目: 中央高校基本科研业务费资助项目( E11JB00310，E12JB00140) ; 国家重点基础研究发展计划资助项目( 2012CB821206) ; 国家自然 科学基金资助项目( 61004021，61174069，61004023) ; 北京市自然科学基金资助项目( 4122037) DOI: 10． 13374 /j． issn1001--053x． 2014． 07． 019; http: / /journals． ustb． edu． cn 网络控制系统( networked control systems，NC￾Ss) 是一种通过网络形成闭环反馈，集通信网络和控 制系统于一体的分布式控制系统． 网络控制系统结 构有两大类，分别为直接结构和分级结构［1］． 前者 在应用中，多个控制器可能被封装在一个控制单元 来管理多个闭环回路，典型应用包括远程学习实验 室和直流电机调速等［2 － 3］; 后者在应用中由于远程 控制器的存在，分级结构有更好的实时性，典型应用 包括移动机器人、汽车控制以及航天器等［4 － 6］． 无 论采取哪种结构，与传统的点对点直接控制系统相 比，网络控制系统的最大特点是系统中的传感器、控 制器和执行器并不是直接的点对点连接，而是通过 公共网络交换数据和控制信息． 此种特性的优势在 于可以实现信息资源共享和远程分布控制，减少系 统布线、支持模块化设计、配置灵活、安装成本低和 易于维护，广泛应用于国防、航空航天、设备制造、智

·980· 北京科技大学学报 第36卷 能交通，过程控制及经济管理领域口 所示.下层通信网络(lower layer communication net-- 近年来，网络控制系统已成为国内外学术界的 wok,LLN)根据网络调度负责实时控制.假设下层 前沿方向和研究热点，相关文献层出不穷，如网络协 网络控制系统有M个控制闭环子系统，由于执行器 议-、网络诱导时延0-山、数据丢包2-、网络 (actuator)一般不发送数据，每个控制闭环设有两个 架构4-、网络调度6-切以及网络安全s-0.然 数据传输节点，传感器(sensor)节点和控制器(con- 而上述研究对象多是基于单层的网络结构，对更复 troller)节点，则网络总数据传输节点为2M.其中执 杂结构的网络控制系统和非线性系统研究得比较 行器是事件驱动式，而控制器和传感器是时间驱动 少.本文引入一种双层结构的网络学习控制系统 式，有相同的采样周期h,且大于系统轮询周期.各 (networked learning control system,NLCS).研究表 控制闭环的传感器根据各自的采样周期将各自信息 明，这种结构的网络控制系统具有更好的控制性能 (包括采样数据、节点标识和相关信息)打包发送到 和鲁棒性，适用于复杂的非线性控制系统-四.当 控制器；：控制器根据各自的传感器信息计算控制指 然，在网络资源有限条件下的网络学习控制系统中， 令并打包发送到相应的执行器：执行器根据所得最 不确定的网络诱导时延将严重影响系统的控制性能 新控制命令更新内部控制算法 和系统稳定性.因此，网络服务质量(quality of net-- work service,QoS)和控制系统性能(quality of con- 学习和调度中心 ol,QoC)不仅依赖于控制算法和体系结构，而且依 赖于对共享网络资源的分配和调度.一种优化的调 上层网络(UIN) 度算法将有助于更合理地分配带宽，是提高网络服 务质量和控制系统性能的关键 控制闭环 网络资源的有限性迫使网络中各节点对网络资 闭 源的需求形成一种竞争，各个节点为了获取各自最 闭环！ /控制器(C) 大的网络效用，将会独立、理性地选择一种优化调度 下层网络(ILN) 策略抢占网络资源，从而形成节点间的非合作博弈 事实上，网络中各节点、各类数据对网络资源的需求 和竞争都可以归结为博弈问题.将经济学模型和博 弈理论应用到网络资源分配是研究的一个热点问 题.博弈方法已经在网络流量控制、资源计费、网络 复杂的被控对象 调度和路由算法设计等方面3-2刘得到应用.采用 图1双层网络学习控制系统的架构图 Fig.1 Structure of the double-ayer NLCS 定价理论的网络资源分配也取得了不少成果，因为 网络定价机制是一种仲裁资源分配的有效手 与此同时，学习和调度中心通过上层通信网络 段4-，影子价格能够将网络负荷和带宽容量关联 (upper layer communication network,ULN)对子系统 起来.其中文献24幻提出了一种价格迭代和利率自 进行带宽分配和调度，带宽分配时序如图2所示. 适应的算法使得用户设定的价格能保证其自身效益 一次完整的带宽调度操作周期称为T。·首先在带 的最大化：在文献25]中，提出了一种基于拥塞控 宽轮询周期T。期间，各闭环控制器向中心提交带宽 制的定价策略，根据影子价格和分组评估价值调整 需求：接着在分配周期T、内，中心根据收集的信息 发送速率；文献26]提出一种基于拍卖的带宽分配 计算并分配带宽：最后在剩下的数据传输周期T 机制来解决在无线自组织网络流争用问题.鉴于 中，各控制闭环按照分配到的时间片交替发送数据， 此，本文基于网络定价的非合作博弈模型采用粒子 直到新周期的开始. 群优化算法(particle swarm optimization,PSO),实现 1.2直流电机系统建模 网络学习控制系统的带宽调度优化.仿真结果表明 不失一般性，电机控制系统的动态过程可由如 了所提方法的有效性 下连续时间状态方程描述？-： (1) 1问题描述 f (t)=Af (t)+Bu (t). 其中：∫。(t)∈R为状态向量，u(t)∈R为控制输 1.1网络学习控制系统的结构 入，A和B为具有适当维数的常数矩阵.考虑控制 一种典型的双层网络学习控制系统架构如图1 信号零阶保持的情况下，式(1)所示的网络电机控

北 京 科 技 大 学 学 报 第 36 卷 能交通、过程控制及经济管理领域［7］． 近年来，网络控制系统已成为国内外学术界的 前沿方向和研究热点，相关文献层出不穷，如网络协 议［8 － 9］、网络诱导时延［10 － 11］、数据丢包［12 － 13］、网络 架构［14 － 15］、网络调度［16 － 17］以及网络安全［18 － 20］． 然 而上述研究对象多是基于单层的网络结构，对更复 杂结构的网络控制系统和非线性系统研究得比较 少． 本文引入一种双层结构的网络学习控制系统 ( networked learning control system，NLCS) ． 研究表 明，这种结构的网络控制系统具有更好的控制性能 和鲁棒性，适用于复杂的非线性控制系统［21 － 22］． 当 然，在网络资源有限条件下的网络学习控制系统中， 不确定的网络诱导时延将严重影响系统的控制性能 和系统稳定性． 因此，网络服务质量( quality of net￾work service，QoS) 和控制系统性能( quality of con￾trol，QoC) 不仅依赖于控制算法和体系结构，而且依 赖于对共享网络资源的分配和调度． 一种优化的调 度算法将有助于更合理地分配带宽，是提高网络服 务质量和控制系统性能的关键． 网络资源的有限性迫使网络中各节点对网络资 源的需求形成一种竞争，各个节点为了获取各自最 大的网络效用，将会独立、理性地选择一种优化调度 策略抢占网络资源，从而形成节点间的非合作博弈． 事实上，网络中各节点、各类数据对网络资源的需求 和竞争都可以归结为博弈问题． 将经济学模型和博 弈理论应用到网络资源分配是研究的一个热点问 题． 博弈方法已经在网络流量控制、资源计费、网络 调度和路由算法设计等方面［23 － 24］得到应用． 采用 定价理论的网络资源分配也取得了不少成果，因为 网络定价机制是一种仲裁资源分配的有效手 段［24 － 26］，影子价格能够将网络负荷和带宽容量关联 起来． 其中文献［24］提出了一种价格迭代和利率自 适应的算法使得用户设定的价格能保证其自身效益 的最大化; 在文献［25］中，提出了一种基于拥塞控 制的定价策略，根据影子价格和分组评估价值调整 发送速率; 文献［26］提出一种基于拍卖的带宽分配 机制来解决在无线自组织网络流争用问题． 鉴于 此，本文基于网络定价的非合作博弈模型采用粒子 群优化算法( particle swarm optimization，PSO) ，实现 网络学习控制系统的带宽调度优化． 仿真结果表明 了所提方法的有效性． 1 问题描述 1. 1 网络学习控制系统的结构 一种典型的双层网络学习控制系统架构如图 1 所示． 下层通信网络( lower layer communication net￾work，LLN) 根据网络调度负责实时控制． 假设下层 网络控制系统有 M 个控制闭环子系统，由于执行器 ( actuator) 一般不发送数据，每个控制闭环设有两个 数据传输节点，传感器( sensor) 节点和控制器( con￾troller) 节点，则网络总数据传输节点为 2M． 其中执 行器是事件驱动式，而控制器和传感器是时间驱动 式，有相同的采样周期 h，且大于系统轮询周期． 各 控制闭环的传感器根据各自的采样周期将各自信息 ( 包括采样数据、节点标识和相关信息) 打包发送到 控制器; 控制器根据各自的传感器信息计算控制指 令并打包发送到相应的执行器; 执行器根据所得最 新控制命令更新内部控制算法． 图 1 双层网络学习控制系统的架构图 Fig． 1 Structure of the double-layer NLCS 与此同时，学习和调度中心通过上层通信网络 ( upper layer communication network，ULN) 对子系统 进行带宽分配和调度，带宽分配时序如图 2 所示． 一次完整的带宽调度操作周期称为 TO． 首先在带 宽轮询周期 TP 期间，各闭环控制器向中心提交带宽 需求; 接着在分配周期 TA 内，中心根据收集的信息 计算并分配带宽; 最后在剩下的数据传输周期 TT 中，各控制闭环按照分配到的时间片交替发送数据， 直到新周期的开始． 1. 2 直流电机系统建模 不失一般性，电机控制系统的动态过程可由如 下连续时间状态方程描述［27 － 28］: f · p ( t) = Afp ( t) + Bu( t) ． ( 1) 其中: fp ( t) ∈Ｒq 为状态向量，u( t) ∈Ｒg 为控制输 入，A 和 B 为具有适当维数的常数矩阵． 考虑控制 信号零阶保持的情况下，式( 1) 所示的网络电机控 · 089 ·

第7期 严翔等：基于粒子群优化算法和博弈论的网络学习控制系统带宽调度 ·981· 控制闭环M安 式中：J= （a+B,:）= (a+Bc/）, 控制闭环 控制闭环1 h= x:,0<8<1:优化求解过程中常量：可忽 学习和调度 略不计；比例因子ω的引入是为了保留部分带宽以 中心 应对意外过载情况，从而避免系统性能的突然恶化； 周期 T x和x可通过相应控制闭环的资源约束条件以 及最大允许时延界(maximum allowable delay bound, MADB)得到BU 图2带宽分配时序图 Fig.2 Timing diagram of bandwidth allocation 2 主要结果 制系统模型可被离散化为下式： 2.1网络定价 f(k+1)=Ff(k)+Gu (k) (2) 本节讨论基于网络定价体系的博弈建模问题 计算如下： 定价体系可以被当成网络服务提供者和多个用户或 F=e“,G=edrB Jo (3) 者数据流的有限集合的博弈.定价策略主要包括不 1.3网络学习控制系统的性能分析 基于使用的定价机制(none-usage-based pricing, 网络学习控制系统的系统性能可以由该系统中 NBP)和基于使用的定价机制(usage-based pricing, 所有控制闭环子系统联合描述，而各控制闭环子系 UBP)两种模式2-.不基于使用的定价机制虽然 统的性能则可以采用某个取值域的性能函数来描 定价简单，操作方便，但是无法利用价格杠杆调节用 述，如误差函数.文献29]指出，可以采用绝对误差 户的资源分配，影响资源利用率，且容易导致网络拥 积分(integral absolute error,IAE)来评估网络学习 塞：而基于使用的定价机制的单位带宽价格可以随 控制系统的系统性能，且带宽分配越少控制性能越 着用户对网络资源使用情况的不同而跟踪变化，这 差（误差越大），但带宽分配越多并不意味着控制性 种动态定价机制以用户总体满意度最大为目标，可 能能够无限提升.事实上，在允许采样周期变化范 实现网络资源的高效利用和用户公平性. 围内和网络非过载情况下，系统绝对误差积分e与 本文应用基于使用的定价机制建立动态定价模 采样周期1之间可以获得如下近似关系： 型，以系统总体收益最优为目标，计算出相应的动态 e,(t:）=a:+Bl (4) 价格.将前文提到的每个控制闭环子系统称为一个 其中，心，和B.取决于各自控制闭环子系统 用户，每个用户并不知道其他用户的存在以及他们 文献B0]指出，对于控制闭环i,其采样周期t: 目前的状态，各自根据自己的控制系统性能需求提 和所分配带宽x:之间的关系如下式所示： 出自己的带宽策略，记为x·显然，在网络带宽资源 受限的网络学习控制系统中，所有控制闭环子系统 (5) 形成了一种非合作博弈.每个用户的收益由该用户 式中：x:为控制闭环i所分配到的带宽比例；C表示 对一个给定网络服务质量下得到的相应控制系统性 控制闭环的控制操作时间，包括数据在传感器和控 能和其对此网络服务质量所付出之差决定.用户i 制器之间，控制器和执行器之间的传输时间，以及控 需要支付的金额y:=Ax:,入为单位带宽价格.每位 制器处理数据所花时间. 用户的收益函数表述如下式： 本文一方面需要尽量为每个控制闭环提供服务 S,(x)= U(x）-y,y:>0: (7) 以提升其控制系统性能，另一方面又需要尽量平衡 U(0), y:=0. 每个控制闭环的带宽需求从而使得各个控制闭环的 而基于网络定价结合以绝对误差积分评估系统性能 控制系统性能能够得到保证.因此，对于带宽资源 的方法，用户收益函数可变化为下式： 有限的网络学习控制系统而言，上述问题可描述成 S:(x）=ln(（1+x:/B,c:）-y:=ln（1+x:/B,c）-x 如下多目标优化问题： (8) min8J1+(1-8)J2, 每位用户根据自己的收益独立制定自己的报价 (6) 24≤1-0，≤≤ 策略，显然每位用户都不会离谱地报高价，因为过高 的报价只会降低自己的最终收益

第 7 期 严 翔等: 基于粒子群优化算法和博弈论的网络学习控制系统带宽调度 图 2 带宽分配时序图 Fig． 2 Timing diagram of bandwidth allocation 制系统模型可被离散化为下式: f( k + 1) = Ff( k) + Gu( k) ． ( 2) 计算如下: F = eAh ，G = ∫ h 0 eAτ dτB． ( 3) 1. 3 网络学习控制系统的性能分析 网络学习控制系统的系统性能可以由该系统中 所有控制闭环子系统联合描述，而各控制闭环子系 统的性能则可以采用某个取值域的性能函数来描 述，如误差函数． 文献［29］指出，可以采用绝对误差 积分( integral absolute error，IAE) 来评估网络学习 控制系统的系统性能，且带宽分配越少控制性能越 差( 误差越大) ，但带宽分配越多并不意味着控制性 能能够无限提升． 事实上，在允许采样周期变化范 围内和网络非过载情况下，系统绝对误差积分 e 与 采样周期 t 之间可以获得如下近似关系: ei ( ti ) = αi + βi ti ． ( 4) 其中，αi 和 βi 取决于各自控制闭环子系统． 文献［30］指出，对于控制闭环 i，其采样周期 ti 和所分配带宽 xi 之间的关系如下式所示: ti = ci xi ． ( 5) 式中: xi 为控制闭环 i 所分配到的带宽比例; ci 表示 控制闭环的控制操作时间，包括数据在传感器和控 制器之间，控制器和执行器之间的传输时间，以及控 制器处理数据所花时间． 本文一方面需要尽量为每个控制闭环提供服务 以提升其控制系统性能，另一方面又需要尽量平衡 每个控制闭环的带宽需求从而使得各个控制闭环的 控制系统性能能够得到保证． 因此，对于带宽资源 有限的网络学习控制系统而言，上述问题可描述成 如下多目标优化问题: min δJ1 + ( 1 － δ) J2， s． t． ∑ M i = 1 xi ≤ 1 － ω，xmin i ≤ xi ≤ xmax i { ． ( 6) 式中: J1 = ∑ M i = 1 ( αi + βi ti ) = ∑ M i = 1 ( αi + βici /xi ) ， J2 = ∑ M i = 1 xi，0 ＜ δ ＜ 1; 优化求解过程中常量 αi 可忽 略不计; 比例因子 ω 的引入是为了保留部分带宽以 应对意外过载情况，从而避免系统性能的突然恶化; xmin i 和 xmax i 可通过相应控制闭环的资源约束条件以 及最大允许时延界( maximum allowable delay bound， MADB) 得到［31］． 2 主要结果 2. 1 网络定价 本节讨论基于网络定价体系的博弈建模问题． 定价体系可以被当成网络服务提供者和多个用户或 者数据流的有限集合的博弈． 定价策略主要包括不 基于使用的定价机制 ( none-usage-based pricing， NBP) 和基于使用的定价机制( usage-based pricing， UBP) 两种模式［32 － 33］． 不基于使用的定价机制虽然 定价简单，操作方便，但是无法利用价格杠杆调节用 户的资源分配，影响资源利用率，且容易导致网络拥 塞; 而基于使用的定价机制的单位带宽价格可以随 着用户对网络资源使用情况的不同而跟踪变化，这 种动态定价机制以用户总体满意度最大为目标，可 实现网络资源的高效利用和用户公平性． 本文应用基于使用的定价机制建立动态定价模 型，以系统总体收益最优为目标，计算出相应的动态 价格． 将前文提到的每个控制闭环子系统称为一个 用户，每个用户并不知道其他用户的存在以及他们 目前的状态，各自根据自己的控制系统性能需求提 出自己的带宽策略，记为 xi ． 显然，在网络带宽资源 受限的网络学习控制系统中，所有控制闭环子系统 形成了一种非合作博弈． 每个用户的收益由该用户 对一个给定网络服务质量下得到的相应控制系统性 能和其对此网络服务质量所付出之差决定． 用户 i 需要支付的金额 yi = λxi，λ 为单位带宽价格． 每位 用户的收益函数表述如下式: Si ( xi ) = Ui ( xi ) － yi， yi ＞ 0; Ui ( 0) ， y { i = 0． ( 7) 而基于网络定价结合以绝对误差积分评估系统性能 的方法，用户收益函数可变化为下式: Si ( xi ) = ln ( 1 + xi /βici ) － yi = ln ( 1 + xi /βici ) － λxi ． ( 8) 每位用户根据自己的收益独立制定自己的报价 策略，显然每位用户都不会离谱地报高价，因为过高 的报价只会降低自己的最终收益． · 189 ·

·982 北京科技大学学报 第36卷 在网络学习控制系统框架下，下层通信网络中 定理3非合作网络学习控制博弈的Nash均 的每个用户都希望最大化自己的最终收益.一般而 衡是唯一的. 言，在给定其他用户调度策略的情况下，如果没有任 证明：Nash均衡唯一性的证明可以参考定理2， 何一个用户有动力选择其他调度策略（此时该策略 详细的推导可参看文献B5],为行文简洁，本文不 所得的效用己经是最大)，那么网络中就没有一个 再赘述. 用户有动力打破这种均衡，称这样的均衡为Nash均 至此，本文成功地将网络学习控制系统的网络 衡.兼顾个体与整体最佳性能的资源调度方式就是 资源分配问题转换为非合作博弈竞争模型下的 在Nash均衡点分配带宽.为了方便得到非合作网 Nash均衡点求解问题.然而除了一些现代启发式优 络学习控制博弈(NNLCG)模型中Nash均衡存在性 化算法（如遗传算法等)，传统的数值计算方法对于 和唯一性的证明，先给出如下两个定义： 精确求解Nash均衡点比较困难，因此本文又引入粒 定义1有N个用户的非合作网络学习控制博 子群优化算法来快速寻找Nash均衡点. 弈NG=(T,{X},{S()}),其中T={1,2,…, 2.2粒子群优化算法设计 N是参与用户的索引集合，X={xm",x}(xmn> 粒子群优化算法源于对鸟群捕食行为的模 0)是用户i的策略空间，S(·)(如式(8)所示)是节 拟，是一种基于群智能(swarm intelligence)的随机优 点的收益函数 化启发式搜索技术.最早由Kennedy和Eberhart于 定义2在凸集X:上的函数S(·):X,→定 1995年提出，因其实现简单、全局搜索能力强且计 义为在x:上是拟凹，当且仅当下式成立： 算高效，目前己发展出各种改进算法，并广泛应用于 S(x:+（1-)xx-）≥ 各种优化问题，如函数优化、神经网络训练？-测 min(S(x,x-）,S,(xx-）). (9) 假设在n维连续搜索空间（解空间）中粒子群 其中，x,x∈X,专∈0,1]. 的第i个粒子或个体(i=1,2,…,m)位置表示为 定理1在N人博弈NG=(亚，{P,},{u x:(k）=1x.2…,xm]T,粒子的速度用y:(k)= (·)}),j∈亚中，若策略空间为{P}是欧几里德空 .1.2,…,]T表示，该粒子迄今所获得的具有 间的一个非空紧致凸子集，且其收益函数u(σ)是 最优适应度值的位置称为最优位置，记为p:(k)= 在o上连续且在σ；上拟凹，则此博弈NG存在Nash p.1P.2…,P.n]T,粒子之间局部信息的相互交流 均衡. 将产生整个粒子群的迄今最优位置，记为P,(k)= 证明：定理I的推导可利用经典Kakutani固定 点理论完成，关于该定理的详细证明可参考文献 P1P2…P]I.对于每一代，粒子寻优遵循以 下基本公式： 34. 定理2非合作网络学习控制博弈NG=(T, (k+1)=()+C1rand(0,a,）p(k)- {X},{S,(·)}),i∈T中存在Nash均衡. xij(]Czrand(0,a2).i (k)-xi(k)], (12) 证明：本定理可以通过验证非合作网络学习控 制博弈NG=(T,{X},{S:(·)}),i∈T满足定理 x(+1)=x(k)+,(k+1).(13) 1的两个条件来证明.其中每个用户的策略空间定 式中j=1,2,,n为n维向量的第j个分量；k为迭 义在区间x,x“](x>0).假设x≤x总 代次数；C,和C2为加速常数，均为非负值；rand(0, 是成立的，显然满足了第一个条件.下面证明对于 a1)与rand(0,a2)分别产生0，a1]和0，a2]之间均 每个用户i,收益函数S(x)在x:上是拟凹的 匀分布的随机数，其引入将增加认知和社会搜索方 收益函数S(x)对x:的一阶微分为 向的随机性和算法的多样性.算法的中止条件是最 aS;(x,)1 大迭代次数或粒子群已搜索到的最优位置满足预定 -入 (10) dx Bc:+xi 最小适应阈值. 收益函数S:(x)对x:的二阶微分为 2.3调度算法 aS(x）1 确定了网络学习控制系统非合作博弈竞争模型 B,6+)<0. (11) 下的Nash均衡点，就要根据Nash均衡点的带宽分 由上式可知收益函数S(x)在x上连续可微， 配进行网络调度，这里上层通信网络采用轮询调度 且在x:上是凹的，一个凹函数同样也是拟凹的，第 机制来完成一次系统数据传输周期T,·假设每个时 二个条件也成立，至此该定理证明完毕 间片的长度为T,,且T,≥c,即在一个时间片内可

北 京 科 技 大 学 学 报 第 36 卷 在网络学习控制系统框架下，下层通信网络中 的每个用户都希望最大化自己的最终收益． 一般而 言，在给定其他用户调度策略的情况下，如果没有任 何一个用户有动力选择其他调度策略( 此时该策略 所得的效用已经是最大) ，那么网络中就没有一个 用户有动力打破这种均衡，称这样的均衡为 Nash 均 衡． 兼顾个体与整体最佳性能的资源调度方式就是 在 Nash 均衡点分配带宽． 为了方便得到非合作网 络学习控制博弈( NNLCG) 模型中 Nash 均衡存在性 和唯一性的证明，先给出如下两个定义: 定义 1 有 N 个用户的非合作网络学习控制博 弈 NG = ( Γ，{ Xi} ，{ Si (·) } ) ，其中 Γ = { 1，2，…， N} 是参与用户的索引集合，Xi = { xmin i ，xmax i } ( xmin i ＞ 0) 是用户 i 的策略空间，Si (·) ( 如式( 8) 所示) 是节 点的收益函数． 定义 2 在凸集 Xi 上的函数 Si (·) : Xi→Ｒ1 + 定 义为在 xi 上是拟凹，当且仅当下式成立: Si ( ξxi + ( 1 － ξ) x'i，x － i ) ≥ min ( Si ( xi，x － i ) ，Si ( x'i，x － i ) ) ． ( 9) 其中，xi，x'i∈Xi，ξ∈［0，1］． 定理 1 在 N 人 博 弈 NG = ( Ψ，{ Pj } ，{ uj (·) } ) ，j∈Ψ 中，若策略空间为{ Pj} 是欧几里德空 间的一个非空紧致凸子集，且其收益函数 uj ( σ) 是 在 σ 上连续且在 σj 上拟凹，则此博弈 NG 存在 Nash 均衡． 证明: 定理 1 的推导可利用经典 Kakutani 固定 点理论完成，关于该定理的详细证明可参考文献 ［34］． 定理 2 非合作网络学习控制博弈 NG = ( Γ， { Xi} ，{ Si (·) } ) ，i∈Γ 中存在 Nash 均衡． 证明: 本定理可以通过验证非合作网络学习控 制博弈 NG = ( Γ，{ Xi} ，{ Si (·) } ) ，i∈Γ 满足定理 1 的两个条件来证明． 其中每个用户的策略空间定 义在区间［xmin i ，xmax i ］( xmin i ＞ 0) ． 假设 xmin i ≤xmax i 总 是成立的，显然满足了第一个条件． 下面证明对于 每个用户 i，收益函数 Si ( x) 在 xi 上是拟凹的． 收益函数 Si ( x) 对 xi 的一阶微分为 Si ( xi ) xi = 1 βici + xi － λ． ( 10) 收益函数 Si ( x) 对 xi 的二阶微分为 S2 i ( xi ) x 2 i = － 1 ( βici + xi ) 2 ＜ 0． ( 11) 由上式可知收益函数 Si ( x) 在 x 上连续可微， 且在 xi 上是凹的，一个凹函数同样也是拟凹的，第 二个条件也成立，至此该定理证明完毕． 定理 3 非合作网络学习控制博弈的 Nash 均 衡是唯一的． 证明: Nash 均衡唯一性的证明可以参考定理 2， 详细的推导可参看文献［35］，为行文简洁，本文不 再赘述． 至此，本文成功地将网络学习控制系统的网络 资源分配问题转换为非合作博弈竞争模型下的 Nash 均衡点求解问题． 然而除了一些现代启发式优 化算法( 如遗传算法等) ，传统的数值计算方法对于 精确求解 Nash 均衡点比较困难，因此本文又引入粒 子群优化算法来快速寻找 Nash 均衡点． 2. 2 粒子群优化算法设计 粒子群优化算法［36］源于对鸟群捕食行为的模 拟，是一种基于群智能( swarm intelligence) 的随机优 化启发式搜索技术． 最早由 Kennedy 和 Eberhart 于 1995 年提出，因其实现简单、全局搜索能力强且计 算高效，目前已发展出各种改进算法，并广泛应用于 各种优化问题，如函数优化、神经网络训练［37 － 38］． 假设在 n 维连续搜索空间( 解空间) 中粒子群 的第 i 个粒子或个体( i = 1，2，…，m) 位置表示为 xi ( k) =［xi，1，xi，2，…，xi，n］T ，粒子的速度用 vi ( k) = ［vi，1，vi，2，…，vi，n］T 表示，该粒子迄今所获得的具有 最优适应度值的位置称为最优位置，记为 pi ( k) = ［pi，1，pi，2，…，pi，n］T ，粒子之间局部信息的相互交流 将产生整个粒子群的迄今最优位置，记为 pg ( k) = ［pg，1，pg，2，…，pg，n］T ． 对于每一代，粒子寻优遵循以 下基本公式: vi，j ( k + 1) = vi，j ( k) + C1 rand( 0，a1) ［pi，j ( k) － xi，j ( k) ］+ C2 rand( 0，a2) ［pg，j ( k) － xi，j ( k) ］， ( 12) xi，j ( k + 1) = xi，j ( k) + vi，j ( k + 1) ． ( 13) 式中: j = 1，2，…，n 为 n 维向量的第 j 个分量; k 为迭 代次数; C1 和 C2 为加速常数，均为非负值; rand( 0， a1 ) 与 rand( 0，a2 ) 分别产生［0，a1］和［0，a2］之间均 匀分布的随机数，其引入将增加认知和社会搜索方 向的随机性和算法的多样性． 算法的中止条件是最 大迭代次数或粒子群已搜索到的最优位置满足预定 最小适应阈值． 2. 3 调度算法 确定了网络学习控制系统非合作博弈竞争模型 下的 Nash 均衡点，就要根据 Nash 均衡点的带宽分 配进行网络调度，这里上层通信网络采用轮询调度 机制来完成一次系统数据传输周期 TT ． 假设每个时 间片的长度为 TL，且 TL≥c max i ，即在一个时间片内可 · 289 ·

第7期 严翔等：基于粒子群优化算法和博弈论的网络学习控制系统带宽调度 ·983· 以完成一个控制闭环的数据传输，则在一个T时间 based bandwidth allocation,NPBA)方法的初始种群 段内，共有l=T/T个时间片，L为当前可用时间片 数为100，经过10代的进化，整体适应度快速收敛 序列集合，每个用户将拥有一组以时间序列表示所 并趋于稳定，达到Nash均衡，根据所得的均衡解 占据时间片的序列集合L:例如，对于一个有L1= x=0.220.370.31]T,1L1=93进行带宽分 10个时间片的分配，其中用户i的L:={1,4,9},表 配和系统性能评估；另外，本文又采用了平均带宽分 示它占据了第一、第四和第九个时间片，剩余可用的 配(equal bandwidth allocation,EBA)方法进行了仿 时间片序列集为{2,3,5,6,7,8,10}.具体的网络调 真实验对比，每个子系统的所得带宽为x:=（1- 度算法过程如下： w)/M,在可用总带宽相同的情况下，分别采用两种 Step1对于给定的带宽分配策略x',按降序 策略所得的绝对误差积分和带宽分配比例(ratio of 对各个用户所得带宽进行排序. bandwidth,RoB)结果如图3所示，相应各回路的阶 Step2计算每个用户占有的时间片数量为 跃响应如图4所示.不难看出，虽然采用平均带宽 l=Lx:」小，其中l为T时间段内的时间片总数 分配方法的个别子系统优于采用基于网络定价的带 Step3设定索引序号i=M. 宽分配方法的相应子系统，如控制闭环1中采用平 Step4计算用户i的时间片间隔d:=[1/x:l. 均带宽分配方法的绝对误差积分低于基于网络定价 Step5初始化计数器r=minh,h∈L,b=0, 的带宽分配方法，且阶跃响应曲线也优于基于网络 L=}. 定价的带宽分配方法，但采用平均带宽分配方法的 Step6当b≤l,和m=r+bd,≤l有一个条件不 平均绝对误差积分值却高于基于网络定价的带宽分 满足，转Step8,否则转Step7. 配方法，说明采用基于网络定价的带宽分配策略的 Step7如果m主L且m≤l时，更新m←-m+1 网络控制系统具有更优越的整体系统性能.其主要 直到得到一个m∈L的值，并将这个m放入L,的时 原因在于：平均带宽分配方法虽然因个别子系统获 间序列集，更新b←-b+1,L←-L-{m},然后转Step 得较高带宽分配而使其系统性能增强，但平均带宽 6;否则结束此用户的时间片调度，转Step8. 分配策略并未考虑带宽分配与系统性能提高之间的 Step8更新i-i-l,如果此时i=0,结束算 投入产出比，忽略了经济效果的评价指标，从而形成 法；否则转Step4. 部分回路带宽不足而另一部分回路带宽过剩的局 面：相反基于网络定价博弈带宽调度策略可有效迫 3实验与结果分析 使各控制回路工作于Nash均衡点，通过合理的分配 为了验证算法的有效性，本文采用MATLAB实 带宽而使得网络控制系统达到整体性能最优 现上述优化算法，并针对网络电机控制系统进行仿 1.8 EBA 真实验.仿真测试系统包括三个网络电机控制子系 1.6 一EBA均值 ◆NPBA 统，各子系统模型均采用公式(1)描述，具体系统参 1.4 -NPBA均值 数如表1所示.其余参数设置如下：w=0.1,T。= 1.2 0.5s,T=0.005s,Tp=0.03s,剩余时间即为Tr 值得指出的是，带宽分配周期T,相对于轮询周期 1.0 T非常小，可忽略不计 0.8 表1网络电机控制系统主要控制参数 0.6 Table 1 Parameters of the networked de motor subsystem 040 网络电机控制子系统 参数A 参数B 控制闭环序列 r-1579.9 -411 「318.4731 图3仿真实验结果对比 控制闭环1 430.3 -0.1」 0 Fig.3 Comparison of simulation results 控制闭环2 11 01 基于网络定价的带宽分配策略的网络调度时序 -217.4」 L1669.5J 图如图5所示，其中末端的空闲时间片为保留带宽. -579.9 -4.11 18.4713 控制闭环3 30.3 -0.01 0 不难看出，各控制闭环的网络节点均获得了相应比 例的带宽资源来发送数据，且各子系统具有满意的 基于网络定价的带宽分配(network pricing- 控制性能.上述仿真实验结果表明了本文所采用算

第 7 期 严 翔等: 基于粒子群优化算法和博弈论的网络学习控制系统带宽调度 以完成一个控制闭环的数据传输，则在一个 TT 时间 段内，共有 l = TT /TL 个时间片，L 为当前可用时间片 序列集合，每个用户将拥有一组以时间序列表示所 占据时间片的序列集合 Li ． 例如，对于一个有| L | = 10 个时间片的分配，其中用户 i 的 Li = { 1，4，9} ，表 示它占据了第一、第四和第九个时间片，剩余可用的 时间片序列集为{ 2，3，5，6，7，8，10} ． 具体的网络调 度算法过程如下: Step 1 对于给定的带宽分配策略 x* ，按降序 对各个用户所得带宽进行排序． Step 2 计算每个用户占有的时间片数量为 li = ?lxi」，其中 l 为 TT 时间段内的时间片总数． Step 3 设定索引序号 i = M． Step 4 计算用户 i 的时间片间隔 di =「1 /xi?． Step 5 初始化计数器 r = min h，h∈L，b = 0， Li = { } ． Step 6 当 b≤li 和 m = r + bdi≤l 有一个条件不 满足，转 Step 8，否则转 Step 7． Step 7 如果 mL 且 m≤l 时，更新 m←m + 1 直到得到一个 m∈L 的值，并将这个 m 放入 Li 的时 间序列集，更新 b←b + 1，L←L － { m} ，然后转 Step 6; 否则结束此用户的时间片调度，转 Step 8． Step 8 更新 i←i － 1，如果此时 i = 0，结束算 法; 否则转 Step 4． 3 实验与结果分析 为了验证算法的有效性，本文采用 MATLAB 实 现上述优化算法，并针对网络电机控制系统进行仿 真实验． 仿真测试系统包括三个网络电机控制子系 统，各子系统模型均采用公式( 1) 描述，具体系统参 数如表 1 所示． 其余参数设置如下: ω = 0. 1，TO = 0. 5 s，TL = 0. 005 s，TP = 0. 03 s，剩余时间即为 TT ． 值得指出的是，带宽分配周期 TA 相对于轮询周期 TL 非常小，可忽略不计． 表 1 网络电机控制系统主要控制参数 Table 1 Parameters of the networked dc motor subsystem 网络电机控制子系统 参数 A 参数 B 控制闭环 1 － 1579. 9 － 4. 1 [ ] 430. 3 － 0. 1 318. 473 [ ] 0 控制闭环 2 0 1 [ ] 1 － 217. 4 0 [ ] 1669. 5 控制闭环 3 － 579. 9 － 4. 1 [ ] 30. 3 － 0. 01 18. 4713 [ ] 0 基于网络定价的带宽分配 ( network pricing￾based bandwidth allocation，NPBA) 方法的初始种群 数为 100，经过 10 代的进化，整体适应度快速收敛 并趋于稳定，达到 Nash 均衡，根据所得的均衡解 x* =［0. 22 0. 37 0. 31］T ，| L | = 93 进行带宽分 配和系统性能评估; 另外，本文又采用了平均带宽分 配( equal bandwidth allocation，EBA) 方法进行了仿 真实验对比，每个子系统的所得带宽为 xi = ( 1 － ω) /M，在可用总带宽相同的情况下，分别采用两种 策略所得的绝对误差积分和带宽分配比例( ratio of bandwidth，ＲoB) 结果如图 3 所示，相应各回路的阶 跃响应如图 4 所示． 不难看出，虽然采用平均带宽 分配方法的个别子系统优于采用基于网络定价的带 宽分配方法的相应子系统，如控制闭环 1 中采用平 均带宽分配方法的绝对误差积分低于基于网络定价 的带宽分配方法，且阶跃响应曲线也优于基于网络 定价的带宽分配方法，但采用平均带宽分配方法的 平均绝对误差积分值却高于基于网络定价的带宽分 配方法，说明采用基于网络定价的带宽分配策略的 网络控制系统具有更优越的整体系统性能． 其主要 原因在于: 平均带宽分配方法虽然因个别子系统获 得较高带宽分配而使其系统性能增强，但平均带宽 分配策略并未考虑带宽分配与系统性能提高之间的 投入产出比，忽略了经济效果的评价指标，从而形成 部分回路带宽不足而另一部分回路带宽过剩的局 面; 相反基于网络定价博弈带宽调度策略可有效迫 使各控制回路工作于 Nash 均衡点，通过合理的分配 带宽而使得网络控制系统达到整体性能最优． 图 3 仿真实验结果对比 Fig． 3 Comparison of simulation results 基于网络定价的带宽分配策略的网络调度时序 图如图 5 所示，其中末端的空闲时间片为保留带宽． 不难看出，各控制闭环的网络节点均获得了相应比 例的带宽资源来发送数据，且各子系统具有满意的 控制性能． 上述仿真实验结果表明了本文所采用算 · 389 ·