【www.rjdtv.com--人工智能论文】

   摘 要 多 Agent 协作过程中的许多问题都可在分布式约束优化问题( DCOP) 框架下建模，但多局限于规划问题，且一般需 Agent 具有完全、准确收益函数． 针对 DCOP 局限性，定义动态分布式约束优化问题( DDCOP) ，分析求解它的两个关键操作: Exploration 和 Exploitation，提出基于混沌蚂蚁的 DDCOP 协同求解算法( CA－DDCOP) ． 该算法借鉴单只蚂蚁的混沌行为和蚁群的自组织行为，实现 Exploration 和 Exploitation，根据玻尔兹曼分布，建立平衡 Explora-tion 和 Exploitation 的协同方法． 通过多射频多信道无线 Ad Hoc 网络的信道分配验证该算法的有效性．
   关键词 混沌，协同求解，动态分布式约束优化，信道分配
   1 引 言分布式约束优化问题( Distributed ConstraintOptimization Problem，DCOP)是通过多 Agent 协作，实现资源或任务分配、协同决策的代价最小化或收益最大化． DCOP 提供了一种表示问题的形式，每个协作Agent控制一个或多个变量，多Agent共同优化约束． 实际应用中，很多问题可以建模为 DCOP，如多 Agent 规划协调、会议安排和机器人足球等． 一般，这类问题的目标是寻找变量最优值．DCOP 全局最优解的求解方法研究已取得很大进展． 这些方法主要分两类: 精确算法和近似算法．精确算法能确保返回最优解，如异步分布式约束最优 算 法 ( Asynchronous Distributed ConstraintOptimization，ADOPT)、最优异步部分交叉算法( Optimal Asynchronous Partial Overlay，OptAPO)、分布式伪代码树优化算法( Distributed PseudotreeOptimization Procedure，DPOP)、无承诺分支定界搜 索 算 法 ( No-Commitment Branch and BoundSearch，NCBB)、异步前向边界算法( AsynchronousForward-Bounding Algorithm，AFB)、多局部边界搜 索 算 法 ( Multiple Local Bounded Search，MULBS)，而近似算法是以快速方式找到一个最好的 近 似 解，如 分 布 式 随 机 算 法 ( DistributedStochastic Algorithm，DSA)、最大增益信息算法( Maximum Gain Message，MGM)，随时局部搜索算 法 ( Anytime Local Search for DistributedConstraint Optimization Problems，ALS_DisCOP)．然而，精确算法存在一定的局限，即，随着系统设备( 节点) 数目增加，协调开销指数级增长，特别是大规模应用和复杂场景． 其主要原因在于: 1) 精确算法运行中，需不断重建静态树结构; 2) 分布式算法中，Agent 之间通信导致网络过载; 3) 复杂规划或分配问题通常需处理速度尽可能快，因为尽可能快地得到一个近似解比在不可接受的时间内获得最优解更好; 4) 特别是在复杂的情况下 Agent 不知道初始收益矩阵( Payoff Matrix) ，必须探索环境，确定不同变量的收益． 所有的收益是依赖于 Agent 的联合行动，要求 Agent 在探索中认知，如水下机器人( 自主水下航行器) 测量水下结构，无人机测量环境现象，传统 DCOP 算法显得无能为力． 这类复杂DCOP 称为动态分布式约束优化问题 ( DynamicDistributed Constraint Optimization Problem，DDCOP) ． 因此，一个有效的 DCOP 算法必须解决上述 4 个方面的挑战．为解决 DDCOP，提出一种新型求解 DDCOP 的近似算法． 该算法思想基于蚂蚁个体的混沌行为和蚁群的自组织行为和作者已提出的自治群集的分布式协调算法，进一步提出基于混沌蚂蚁的动态分布式约束优化问题协同求解算法 ( Chaotic AntBased Dynamic Distributed Constraint OptimizationProblem，CA-DDCOP) ， 通 过 分 布 式 协 调 实 现DDCOP 协同求解．为构建 CA-DDCOP 算法，先根据单只蚂蚁的混沌行为表达式，建立 Agent 对其控制变量数值混沌选择方法，再根据蚂蚁个体受邻居和信息素作用的机制，形成动态协调方法，最后根据兰顿蚂蚁表现出混沌及涌现行为，且满足玻尔兹曼分布，建立Agent 对混沌选择值的接受概率，以体现个体微观层与群体宏观层决策之间的关系． 此外，为验证CA-DDCOP 算法的有效性，采用此算法解决多射频多信道无线 Ad Hoc 网络的信道分配问题( ChannelAssignment for Multi-Radio Multi-Channel WirelessAd Hoc Network，MRMC-CA) ．
       2 DDCOP 与 DCOP先分析 DDCOP 与 DCOP 的区别，然后讨论DCOP 相关算法，并指出这些算法求解 DDCOP 的局限性． 同时特别给出两种基于蚂蚁行为的分布式算法，显示出启发式近似算法求解动态复杂场景的分布式优化问题的优越性．
       2． 1 DDCOP 算法为更清楚理解DDCOP 与DCOP 的区别，下面对8 02模式识别与人工智能 26 卷两者进行解释． DCOP 由集中式约束优化问题扩展而来． 在 DCOP 中，每个 Agent 为它控制的变量赋值，变量和约束都是分布式、多维自治、可通信的，并给定一个全局目标函数． 但在 DDCOP 中，很多情况收益不是先验的，需通过 Exploration 操作获取．Agent 在进行 Exploration 操作同时，利用当前知识，进行 Exploitation 操作． 为实例分析 DDCOP，变量 x1，x2，x3分别受控于 Agent a1，a2，a3，x1，x3是x2的 两 个 邻 居，每 个 变 量 拥 有 一 个 离 散 域．Exploration 操作的收益在图 1 给出． 图 1 中 “? ”表示将来的、未知的收益． 由图1 可见，每个Agent可为其变量选择一个数值，实例的总收益依赖于这对Agent 的变量值，但约束收益只有在 Exploration 操作之后才能获得． 如当两个 Agent 执行时间步为 1时，总收益是 R1，2+ R2，3= 8 + 5 = 13． 显然，DDCOP全局最优解不是最大化最后收益，而是最大化在线( Online) 收益． 根据 DDCOP 特点，基于智能 Agent的建模方法较为合适． 因此，采用 Agent 作为处理和优化 DDCOP 主体，负责协调和处理它们之间的约束，即每个 Agent 能处理通信、决策甚至学习．图 1 3 个 Agent 的 DDCOPFig． 1 A DDCOP for 3 agents沿用 DCOP 的形式化方法［1］，将 DDCOP 定义如下．定义 1 动态分布式约束优化问题( DDCOP) ，DDCOP 可形式化五元组 DP = ( X，D，F，A，δ) :
　　1) 变量集合 X = { x1，x2，…，xnn ∈ N} ;2) 离散域集合 D = { d1，d2，…，dnn ∈ N} ，di是变量 xi的值域;3) X 的一个具体取值珓x' = { x珓1，x珓2，…，x珓n} ，x珓i是xi的值，珓x' 称为一个组态( Configuration) ． 存在约束的任一变量组X'i?X对应的局部组态为珓xi' ?珓x'，那么 fi: x珓i' → R 称为组态珓x' 上的收益函数，即函数 fi( Xi') 表示变量组 X'i对应 Agent 的联合收益． 收益函数集合 F = { fi( Xi') ?Xi' ? X} ;4) Agent 集合 A = { a1，a2，…，ann ∈ N} ，每个Agent 控制一个或几个变量，并为其变量赋值;5) δ: A→X 为从Agent 到变量的映射关系，表明变量受控于 Agent，它们之间是双射关系．在上述关系中，寻找每个变量的值，构成 X*，满足所有函数的和最大( 总收益最大) ，即X*= arg max∑?Xi'?Xfi( Xi') ． ( 1)
       2． 2 DCOP 算法近些年，已提出几种 DCOP 算法及其变种． 本文仅概述几个经典算法，同时指出这些算法求解DDCOP 的不足．异步分布式约束最优算法( ADOPT)是一种精确异步 DCOP 算法，它有 3 个关键思想: 异步搜索、传播阈值和停止条件． 该算法首先建立深度优先搜索树，然后异步搜索通过局部视图修改局部变量．代价信息从底向上传播，数值信息从上向下传，迭代地紧缩上下界，直到最小代价下界等于其上界时，停止运行． 通过阈值可有效重新构造以前的部分解，使最坏情况的空间复杂度限制在多项式级． 然而，ADOPT 的每个 Agent 根据局部视图修改它的值，可能导致搜索区域再次被修改，产生指数级冗余信息．最优异步部分交叉算法( optAPO)是在调停者的干预下直接与约束通信，局部地集中问题．Agent 为提高局部视图，需增加知识． 当一个 Agent充当一个调停者，它计算整个问题中的部分解，在调停过程中，推荐其它 Agent 改变数值． 调停者以集中式的分枝限界算法，发现局部问题的最优解． 然而，有时协商 Agent 拒绝共享信息或放弃它们子问题的决策控制．分布式伪代码树优化算法( DPOP)是一种精确动态规划算法，它采用深度优先树和动态规划求解全局最优解，主要有 3 个阶段: 第一阶段是深度优先树 DFS 形成; 第二阶段是自下而上地计算和传播的代价; 第三阶段是由根节点开始，自上而下的数值传播． 尽管 DPOP 需多项式的运行时间和线性增长的消息量，但消息大小是指数空间中伪树的宽度． 因此，过多约束的大量消息限制了该算法的应用．综上所述，若采用3 种算法及变种解决 DDCOP，将遭遇静态树不断重建，从而导致放弃搜索边界，再次开始搜索． 因此，解决 DDCOP，需结构灵活和性能鲁棒的算法以应对复杂动态的环境．众所周知，自然界依赖自组织演化，特别是生物系统的自组织演化． 因此，社会性昆虫的自组织行为已引起一些学者关注和研究． 社会性昆虫群有成千上万只个体构成，它们之间没有任何主动的协调等: 一种动态分布式约束优化问题协同求解算法803有协调者，个体仅根据局部信息自发协调使整个群集表现出有序的行为，称为涌现． 涌现的主要特征体现在群集内部分工的可塑性，从事的各项任务个体数量的比率能反映内外部环境的变化． 下面，给出基于蚂蚁行为 DDCOP 算法，以表明这些启发式算法对求解复杂动态问题的优势．
      2． 3 基于蚂蚁行为的 DDCOP 算法基于群的广义分配问题算法 ( Swarm basedGeneralized Assignment Problem，Swarm-GAP)是求解复杂分布式任务分配的近似算法． 该算法以DCOP 建模，基于蚂蚁的分工协作理论设计． 该算法的协作 Agent 能以低通信和计算代价协调它们的行为．基于 蚂 蚁 的 大 团 队 任 务 分 配 ( Ant BasedAlgorithm for Task Allocation in Extreme Teams，eXtreme-Ants)算法受社会性昆虫劳动分工和猎物协作转运招募过程启发，采用 DCOP 建模． 该算法利用劳动分工提供快速、高效的决策，采用招募确保分配的任务并行执行，有效解决大规模、动态多Agent 环境的任务分配．由上述两算法可见，一些启发式算法能有效解决 DDCOP． 然而，经典的 DCOP 算法由于计算代价和通信负载而显得无效． 因此，本文试图通过模拟单只蚂蚁的混沌行为和整个蚁群的自组织行为来构建适合求解 DDCOP 的算法．
       3 CA-DDCOP 算法本节首先简述蚁群中存在的混沌和自组织行为，然后对它们形式化，并给出 CA-DDCOP 算法构建过程．3． 1 蚁群的混沌和自组织众多学者关注蚂蚁等社会性昆虫的主要原因在于这些昆虫群表现出自组织行为和高层的群集结构，群的能力大于个体之和，而个体功能相对简单．1991年，Cole指出，孤立的蚂蚁显示出短暂的、不稳定的活动，而蚁群自发产生有规律的活动．1991 年，Cole还报道，单只蚂蚁表现出低维的混沌，而蚁群具有周期性活动规律．1993 年，Solé 等进一步给出一个低维混沌映射，形成蚂蚁混沌行为表达式:
　　Z( t + 1) = Z( t) exp{ μ［1 － Z( t) ］} ， ( 2)其中，μ 是控制参数． 文献指出Cole的推测，在动物行为中存在混沌，已暗示个体行为的时空可能不会因随机世界变化而变化，但依赖于决定性的初始条件． 1995 年，Miramontes指出，系统中相互作用个体当处于混沌到有序的边界状态中，可能存在最优信息处理能力和最优适应能力． 由相互作用的混沌个体构成的蚁群能产生有规律的周期性活动．另外，2009 年，Couzin提出，蚁群表现出类似神经的行为，正像移动的神经网络．因此，上述研究表明单只蚂蚁的混沌行为和整个蚁群的自组织行为之间存在相互关系，且表现出一定的行为规律． 本文认为由蚂蚁个体的混沌行为到有序的宏观行为是一个连续的转换过程，由蚁群的自组织能力控制． 于是，从某种意义上，可将混沌和自组织视为求解 DDCOP 的一对耦合有效的操作: Exploration 和 Exploitation．
       3． 2 CA-DDCOP 算法为方便构建算法，先给出一些基本符号描述，然后形式化混沌和自组织过程．3． 2． 1 基本符号为表达方便，给出 CA-DDCOP 算法中的符号及表示意义． 假设每个 Agent 控制一个变量，即 Agentak( 1 ≤ k ≤ n) 控制 xk，两者对应． 故以下不对 ak和xk区分． 每个 Agent 具有一个感知范围 Rs、一个交互范围Ri和一个移动范围Rm，即Agent ak可感知到Rs内的其它 Agent，可与 Ri内的其它 Agent 交互通信，具有移动能力，且 Rm+ Ri≤ Rs． Agent ak从其值域dk选定一数值对其当前数值更新． 值得注意的是，Agent ak从其值域 dk选一数值时，受 Ri内的其它Agent 及环境因素( 如信息素等) 的影响． 以上 3 个范围 Rs，Ri，Rm之间的位置关系如图 2 所示．图 2 Rs，Ri和 Rm之间的位置关系Fig． 2 Relations of Rs，Riand RmRi内节点构成一个图结构，顶点表示 Agent，边表示一个 Agent 是另一个 Agent Ri内的邻居，且两者有约束关系．珓x = ( x珓1，x珓2，…，x珓n) 表示DDCOP 的一个解组态( Configuration) ，珓xk( 1 ≤k≤n) 表示Agentak的值，特别地，珓xl表示某 Agent Ri内局部组态． 所有可能的组态构成组态空间S． 对于组态珓x 和组态空8 04模式识别与人工智能 26 卷间 S，Agent ak的邻居定义为Γk( x珓) ? { j ∈ A ∶ j ≠ k，‖Locj－ Lock‖ ≤ Ri} ，其中，Locj是 Agent aj的位置． S 上的邻域系统是一个集合簇 Γ = { Γk}k∈A，满足下面条件:
　　1) Γk? S;2) ak? Γk;3) aj∈ Γk当且仅当 ak∈ Γj，Γk称为 Agent ak的邻域．在当前环境设置下，根据定义1，对式( 1) 细化．定义 2 组态质量( Quality of Configuration，QC) 在给定组态珓x 中，Agent ak的组态质量可定义为Qk( x珓) =∑j∈Γk( x珓)1［con( aj) = x珓( x珓k) ］Γk( x珓)， ( 3)其中，1·是指示函数，Γk( 珓x) 是 Agent ak的邻居集合，Γk( 珓x) 表示 Agent ak的邻居数量． 如果 Agent ak的珓xk满足约束 con( aj) ，那么指示函数值取1，否则取0．定义2 表明局部组态质量反映 Agent ak的取值珓xk满足它与其邻域 Agent 之间约束条件越多，式( 3)值越大． 因此，组态珓x 质量为Q( x珓) =∑珓xk∈珓xQk( x珓k) ， ( 4)因此，DDCOP 就是使其组态质量最大化，即max∑珓x∈SQ( x珓) ·P( x珓) ，s． t． P( x珓) ∈ ［0，1］，∑x～∈SP( x珓) = 1，( 5)其中，P(珓x) 所有 Agent 选择组态珓x 的分布函数． 可见，DDCOP 最优的组态为珓x*= arg max Q( x珓) ， ( 6)由式( 3) ～ 式( 6) 可知，计算组态质量QC 必须计算每个 Agent 的组态质量 Qk( x珓 ) ，而 Qk( x珓 ) 需知Agent ak的邻居及其局部组态珓xl．据上述分析，CA-DDCOP 算法的目标是，在约束条件下，所有 Agent 从各自的值域内选值使它们在 线 收 益 最 大． CA-DDCOP 算 法 必 须 具 备Exploration 和 Exploitation 的分布式协调框架，以便多个 协 作 Agent 能 够 同 时 执 行 Exploration 和Exploitation． 下面，结合蚂蚁的混沌行为和自组织行为，构建 CA-DDCOP 算法．3． 2． 2 混沌行为形式化因为多数 DDCOP 都是大规模的广义分配( Generalized Assignment Problem，GAP) ，如分布式任务分配［17－18］等． 这些 DDCOP 值域都是离散值，需将连续的混沌低维表达式进行转换，使之满足离散问题表达需要．首先，令 Z( t) =1μw( t) ，将( 2) 转化为w( t + 1) = w( t) exp［μ － w( t) ］． ( 7)当 μ = 3 时，式( 7) 处于混沌系统，即w( t + 1) =w( t) exp［3 － w( t) ］，图 3 给出其混沌序列． 由图 3可见，混沌分布式区间约为［0，7． 5］．图 3 式( 7) 混沌时间序列( μ = 3)Fig． 3 Chaotic time sequence of equation( 7) ( μ = 3)其次，离散化连续变量 wk( t) ，建立从 wk( t) 到珓xk的映射关系． 为此，将区间［0，7． 5］按需要划分成m 个相邻的区间 0，1 × 7． 5m[ )，1 × 7． 5m，2 × 7． 5m[ )，…，( m － 1) × 7． 5m，7． 5[ ]，m 是当前 Agent 可选用资源的总数． 若 wk( t) 落入第 m'∈［1，m］个区间，则当前 Agent 取第 m' 个可用的资源．总之，通过上述两步，每个 Agent 的连续混沌行为能选择对应的可用资源．
       3． 2． 3 自组织行为形式化为借鉴整个蚁群的自组织能力，建立 CA-DDCOP 算法的 Exploitation 操作过程． 先给出 3 个概念，组织能力、势能和受控势能; 再给出通过势函数计算势能的方法; 最后结合已有研究成果，提出个体的接受概率，建立个体微观层与群集宏观层之间的决策联系．蚂蚁是利用信息素寻路和协调它们之间的活动． Couzin［24］指出，蚂蚁通过在路径上累积信息素及对信息素的响应，彼此自发和间接协调活动，同时修改信息素，这个过程称为“Stigmergy”． 当觅食时，这个过程能使环境信息不断重建，将蚂蚁有效地分配到食物资源，并提供一种评判和选择多食物源中较近或利益最大的方法． 因此，信息素在整个蚁群觅食等活动中起到非常重要的协调作用，信息素浓度随时间演化而增大，蚁群的自组织协调作用能力也越大，最终形成有序的宏观行为． 将信息素的作用能9 期 葛方振 等: 一种动态分布式约束优化问题协同求解算法805力称为组织能力( Organizational Capacity) ，对所有蚂蚁的活动起到关键导向作用，且它随时间演化而增强． 势能是 Agent 的邻居对其影响的度量． 若再加上信息素组织能力影响后，称为受控势能．计算 Agent( 蚂蚁) 势能的方法． 对于给定组态珓x，势函数 UAl∶ Al?珓x 表示在组态空间 S 的相互作用，其中UAl∶珓x → R，Al是一个Ri内Agent( 蚂蚁) 构成的团( Clique) ． 势函数 UAl( x珓Al) 仅依赖珓xAl= { x珓k∶ k ∈ Al} ．令 j，k∈Al( j，k = 1，2，…，n，j ≠ k) 是两个 Agent，于是 Agent ak选择珓xk对应的局部势能 εk( x珓k) 为εk( x珓k，x珓j∈Γk) =∑k∈Al，Al?SU( Al)= U{ k}
　　( x珓k) +∑j∈ΓkU{ k，j}
　　( x珓k，x珓j) ． ( 8)计算受控势能 Φ 数学模型如下:
　　yk( t) = yk( t － 1)( 1+rk)， ( 9)Φk( x珓k，t) =εk( x珓k，x珓j∈Γk)yk( t)． ( 10)式( 9) 、( 10) 用来计算 Agent ak在信息素和它的邻居作用下的受控势能． Φk( x珓k，t) 为Agent ak在t步的受控势能． 式( 9) 为连续的减函数，是式( 10)中的分母项，表达信息素组织能力随信息素浓度增大而增强，即自组织能力对单个 Agent 控制能力越强． 故yk( t) 是Agent ak当前步的组织变量，令yk( 0)= 0． 999． rk为 Agent ak的组织因子，它影响式( 10)的收敛速度，若 rk较大，收敛较快，反之，收敛较慢．因此，rk可根据具体问题设定，一般地0 ≤rk≤0． 5．考虑到 Agent 之间的自组织能力的差别，可采用随机函数设置，如rk= 0． 02 + 0． 4·rand( 1) ． 为便于理解，以rk= 0． 01 + 0． 2·rand( 1) 为例，给出自组织能力演化图，如图 4 所示．图 4 yk( t) 随时间演化过程Fig． 4 Time evolution process of yk( t)最后，计算 Agent 混沌选择数值的接受概率．Hamann 等指出，Langton蚂蚁系统满足玻尔兹曼分布式． 依据该研究成果，所有 Agent 可根据局部组态珓xl同时更新它们的混沌选择数值． Γk( x珓) 是Agentak根据其约束可选择的数值集合． 具体地，珓xk为Agent ak在t步的数值，珓yk为Agent ak在t + 1 步的可选数值． Agent ak从珓xk到珓yk的接受概率:
　　Pk( x珓k，y珓k珓xl) =exp［－ Φ( y珓k，x珓l( Al\ k)) ］∑x～k∈Γk( x～)exp［－ Φ( x珓k，x珓l( Al\ k)) ］，( 11)其中，Al\ k 为 Rs范围内除 Agent ak的所有 Agent 的集合，即 Al \ k= { r ∈ Al∶ r ≠ k} ; ( y珓k，x珓l( Al\ k)) 表示Agent ak选择珓yk，而其它 Agent 选择珓xl( Al\ k)． ( x珓k，珓xl( Al\ k)) 的含义与(珓yk，x珓l( Al\ k)) 类似．CA-DDCOP 算法通过下面方式更新 Agent 的组态珓x = ( x珓1，x珓2，…，x珓n) : 将式( 9) 、( 10) 中的受控势能Φ 代入式( 11) ，可得 Agent 选择各个值的条件概率．若第 t 次迭代的组态珓xt= ( x珓t1，x珓t2，…，x珓tn) ，则第 t + 1次迭代中对任意一个 k( k = 1，2，…，n) ，依据条件概率 Pk( x珓k珓x( t+1)1，…，x珓( t+1)k －1，x珓tk +1，…，x珓tn) 在组态空间中选择珓x( t+1)k． 通过多次信道选择后，所有的 Agent 将选择较低势能的信道组态，也就是具有较高收益的信道选择结果．3． 2． 4 CA-DDCOP 算法过程考虑 DDCOP 动态移动的因素，如无人机等，假设 Rs≥ Ri+ Rm隐含了位于 Loc( k，t) 的 Agent ak能够评估它的新邻居，因为当它移动到 Loc( k，t + 1)∈ Γk后，Ri内的其它 Agent 没有变化，依然在感知范围 Rs之内． 即，算法运行中，相邻两次迭代需Agent 位置信息能被感知到，确保算法并行运行．CA-DDCOP 算法过程如下所示．算法 1 CA-DDCOP 算法输入 初始化参数 Rm，Ri，Rs，最大迭代次数 T，当前迭代 t= 1，Agent 数量 n输出 最优或次优组态While( t ＜ = T)采用蚂蚁混沌行为产生 Agent ak的选择值珓yk;产生 Agent 的交互范围 Γs( x珓) ? { k ∈ A ∶ k ≠ s，‖Lock－ Locs‖ ≤ Ri} ;For each Agent ak∈ Γs( x珓)采用式( 8) 评估 εk( x珓k，x珓j∈Γk) ，采用式( 11) 计算P( x珓k，y珓k|珓xl) ;ΔΦ = Φ( y珓k) － Φ( x珓k) ;If ΔΦ ＜ 0珓xk= y珓k;Else8 06模式识别与人工智能 26 卷If rand［0，1］ ＜ P( x珓k，x珓k珓xl)珓xk= y珓k;End IfEnd IfEnd Fort = t + 1;End While由算法流程可看出，每个 Agent 通过混沌行为获得一个数值，该数值是否被接受取决于邻居和信息素的联合作用，经过 T 次协调，所有 Agent 会趋于最优和次优组态．
      4 MRMC 信道分配问题为验证 CA-DDCOP 算法性能，采用 CA-DDCOP算法解决多射频多信道( Multi-Radio Multi-Channel，MRMC) 无线 Ad Hoc 网络的信道分配问题( ChannelAssignment，CA) ． 在实际应用中，无线网络引入多射频多信道架构的是减少无线干扰，提高网络性能．但如何设计一种智能的信道分配算法，将每个节点的可用信道映射到射频，是一个挑战性问题． 因为MRMC 网络中，多个射频在不同信道上工作，只有两相邻节点拥有相同信道才可相互通信． 假设网络所有节点都有相同数量的射频，由鸽巢原理可知，当可用信道数小于每个节点射频数的 2 倍时，无论如何分配信道，都可保证网络连通; 否则，就需设计信道分配算法，确保网络连通． 不然会造成网络分割，降低网络覆盖．为此，先对 MRMC-CA 问题描述，再详细阐述CA-DDCOP 算法求解 MRMC-CA 问题，最后给出仿真实验结果．
       4． 1 MCMR-CA 问题描述很多信道分配方法仅考虑静态的内部干扰，如采用冲突图描述网络不同链接间的干扰关系，不能处理外部干扰，但可通过周期刷新分配方案，将静态信道分配方法扩展成动态分配方法． 本文根据文献，考虑邻居节点之间的内部干扰、外部干扰和节点间信息的不完整性，采用 CA-DDCOP 算法，设计一种动态干扰感知的信道分配算法，为每个射频分配合适的信道．
      4． 2 应用 CA-DDCOP 算法CA-DDCOP 算法的目标是在信道分配过程中，减少Ad Hoc网络内部、同一地点环境和其它无线干扰的影响． 算法实现过程． 节点先通过混沌行为将它的信道进行分配; 再计算节点的局部信道分配组态的受控势能，通过接受概率判断混沌选择的信道是否被接受，随后算法以迭代方式运行; 最后，为保证算法的动态性，设计一种动态同步机制，并描述信道分配算法．
       4． 2． 1 混沌选择信道对节点 i，根据式( 7) 计算 wk( t) ． 将信道集合 C按编号索引，形成序列 c1? c2? … ? cn，并分成 Ci和 Ci两类，Ci= { c kic= 1，?c ∈ C} 表示节点 i 分配射频的信道集合，Ci= C \ Ci表示待分配的信道． 令Ci= m，将区间［0，7． 5］按需要划分成 m 个相邻的 区 间［0，1 × 7． 5m) ，［1 × 7． 5m，2 × 7． 5m) ，…，［( m － 1) × 7． 5m，7． 5］． 若wk( t) 落入第m'∈［1，m］个区间，则当前节点 i 取第 m' 个可用的信道． 这样，每个节点通过连续混沌行为能选择可用信道．
      4． 2． 2 计算节点势能为计算节点的势能，需计算信道已使用的带宽比、信道冲突损失和信道切换时延．首先，量化信道已用带宽比． 节点采用 802． 11的虚拟载波监听机制，可根据 NAV 值得到信道被占用的时间． 在感知阶段 TSS，每个节点以感知时间周期 TSRate进行采样监视信道． 信道状态有“忙”和“闲”两种状态． Ti，busy( c) 为感知到“忙”时间，Ti，idle( c) 为感知“闲”时间． 因此，在感知阶段结束时，节点 i 感知到信道 c 的已用带宽比Bi，neig( c)=Ti，busy( c)Ti，busy( c)+ Ti，idle( c)． ( 12)其次，评估信道冲突带宽损失． 每个网络节点选定一个信道，不仅需要式( 12) 的信道负载，且需来自邻居节点的内部干扰． 令 Kic表示已被节点 i 分配到信道 c ∈ C 上的接收射频 R 的数量，Kic∈ { 0，1} ．具体地，节点 i 的信道分配策略 gi定义为gi= ( Ki1，Ki2，…，Ki C)T，节点 i 的策略 gi是所有信道分配给射频的方案． 节点 i 使用的接收射频 R 的数量Ki=∑Cj = 1Kij．将 N 个节点的一个策略方案作为一个策略组态，g = ( g1，g2，…，gN) = ( gi)i∈N称为策略向量，向量的第 i 列对应节点 i 的策略 gi．所有可能的策略组态集合GC = { ( gi)i∈Ngi∈ GCi，? ∈ N} ．对任何策略组态g = ( gj)j∈N和任何i∈N，g－i=9 期 葛方振 等: 一种动态分布式约束优化问题协同求解算法807( gj)j∈N \ i是除节点 i 之外所有节点的策略组态． 反过来，给定g－i= ( gj)j∈N \ i和gi，( gi，g－i) 则是一个策略组态 g = ( gi)i∈N． 注意节点 i 可能不完全知道 g－i． Ni表示节点i的干扰域内节点数，Ri( c) 表示集合Ni中在给定时间内调整它们的接收射频 R 到信道 c 上的节点数:
　　Ri( c) =∑j∈NiKjc．于是，Ri( C) /Ni称为信道c上干扰节点的浓度，即信道 c 上的冲突节点占干扰域内节点的比率． 这样节点 i 以信道已用比和信道冲突比的平均值作为带宽损失:Mi，B( c，g－i) =Bi，neig( c) + Ri( c) /Ni2．然而，节点的决策代价不仅依赖于所选信道的可用带宽，且还考虑切换时延惩罚． 根据文献，802． 11 需考虑切换时延，通常为 10 μs ～ 80 μs． 在射频切换频率时，较长的切换时延影响协议的性能． 考虑切换时延与 Hello 消息间隔 TH的关系，如果 TH足够大，切换时延就可忽略不计; 相反，较长的切换时延就应考虑更高的代价，使节点少切换信道． 设节点i 使用信道 ci，任何信道 c 的切换时延损失函数为Mi，D( c，g－i) =DsTH， c ≠ ci0， otherwise{最后，节点 i 选择信道 c 的损失函数是带宽和切换时延损失之权重和:
　　Mi( c，g－i) = γMi，B( c，g－i) + ( 1 － γ) Mi，D( c，g－i) ，( 13)其中，γ 是权重调节参数，γ ∈［0，1］． 这样，Mi表示节点 i 的损失矩阵，矩阵的行表示节点 i 的策略( 即，信道选择的策略) ，列是其它 Agent 所有的可能策略 g－i．这里，用信道损失 Mk( c，g－k) 代替式( 8) 中的势能 εk( x珓k，x珓j∈Γk) ． 依据 CA-DDCOP 算法原理，经过多次信道选择之后，所有 Agent 将选择具有较低损失函数的信道组态，也就得到了具有较高目标函数值的信道组态．
       4． 2． 3 节点同步机制求解 MRMC-CA 问题，本文是采用信息交互方式使所有节点之间同步，而不是采用专用信道控制．由于每个节点分配一个不同的信道到接收射频 R，网络拓扑结构可能会被分割． 为避免网络分割，节点必须能感知到它邻居节点的接收射频 R 使用的信道，并通过广播 Hello 消息向它邻居节点通报它的接收射频 R 的信道．Hello 消息发送时机． 当一个新节点加入网络或当一个节点停止从其邻居接收 Hello 消息时，该节点要发送 Hello 消息，通报所有可用信道． 一旦一个节点已知其一跳邻居的接收射频 R 的信道，节点切换到这些信道的发送射频 T，并每隔时间 TH发送一次 Hello 消息．数据传输． 一个节点从邻居节点收集信息之后，就可传输数据． 节点可采用不同信道向不同邻居节点发送信息． 设每个信道有一个数据包队列，数据包根据接收邻居的信道加入相应的队列． 当发送射频T 切换到每个信道，开始发送所有或部分相应队列的数据包．发送控制． 每个节点采用随机方式访问所有需要发送数据的信道． 当信道切换之后，发送射频 T 在该信道的最大时间为 Tmax，即发送时间最大为 Tmax．发送射频 T 切换时延为常数 Ds．发送射频 T 切换． 当节点切换到新的信道可能导致它与邻居的 CTS/RTS 失效． 因此，为避开这种失效引起的冲突，在节点切换到新的信道之后，等待Dt个时间单位．接收射频 R 切换． 切换接收射频 R 到任何信道前，必须通过Hello消息通知其邻居． Hello消息包括两部分内容: 目标信道和切换定时器 TS，TS通常比TH大，设 TS稍微大于 2TH．节点同步机制过程． 由于Ad Hoc网络的业务是随机的、突发性的，所以网络中各个节点的信道损失函数值是时刻变化的． 某些信道会因数据流量的增大而变得拥塞，有些信道因传输数据结束而空闲． 因此，需要节点周期性地监测各自信道损失函数值Mi( c，g－i) ，当 Mi( c，g－i) 大于给定的阈值，开始执行表 2 的 MRMC-CA 步骤，为每个节点获得合适的信道． 然后按下列步骤同步机制执行: 1) 节点 i 有数据发送，先发送 Hello 消息，进入一个时间周期 Dt，为发送数据做准备; 2) 节点 i 的切换发送射频 T 到该信道，等待 Dt，才能开始数据发送; 3) 节点 i 发送数据包时间至多 Tmax，然后切换发送射频 T 到另一信道，开始另一信道的数据传输过程，直到该 TH状态结束; 4) 当节点 i 需接收数据时，先发送 Hello 消息，再切换接收射频到其信道．
       4． 2． 4 MRMC-DDCOP 问题求解过程每个节点视为 CA-DDCOP 中的一个 Agent． 将损失函数式( 13) 看作Agent之间的势能． 于是，根据CA-DDCOP 算法，给出 MRMC-CA 问题求解过程，如下所示．8 08模式识别与人工智能 26 卷算法 2 MRMC-CA 问题求解过程输入 节点 i 的 Ri和 Rs内的节点集合 Ni，其中 Ri为3Rs/4，Rs为信号传输最大距离输出 节点i感知到信道c的已用带宽比Bi，neig( c) 和它选择信道 c 的损失函数值 Mi，t( c，g－i)If 第一次分配混沌选择信道 c ∈ ci到 R 射频;ElseRepeat混沌选择信道 c ∈ ci到 R 射频;采用式( 12) 评估 Bi，neig( C) ;采用式( 13) 计算节点 i 的损失函数作为节点间作用势能 Mi，t( c，g－i) ;采用式( 11) 计算信道 c 分配到接收射频 R 的接受概率P( c) ;△M = Mi，t( c，g－i) － Mi，t －1( c，g－i) ;Until( △M ＜ 0 OR rand［0，1］ ＜ P( c) )切换信道 c 到接收射频 R;End If本算法在开始阶段对节点的信道分配是混沌的，并非最优分配，但随着每个节点从邻居节点收集信息，以一定的概率接受混沌选择的信道，会逐步形成信道使用情况的均衡态．
      5 性能评估本节为评估 MRMC-CA 问题求解方法，首先给出仿真实验环境，然后与相关算法进行性能比较和分析，进而说明 CA-DDCOP 算法的有效性．5． 1 仿真环境本节对所提出的信道分配算法进行评估，并与其它算法比较，仿真实验在 Matlab7． 0 上进行． 将CA-DDCOP 算法与另两种干扰感知的信道分配算法Urban-X、SICA对比分析，每个算法运行 40次． CA-DDCOP 算 法 的 参 数 设 置 如 表 1． 另 外，CA-DDCOP 算法中 rk= 0． 01 + a·rand( 1) ，其中 a 分别为 0． 1、0． 2、0． 3、0． 4，每个 a 运行 10 次．表 1 求解 MRMC-CA 问题的参数默认值Table 1 Default values of parameters in solving MRMC-CA参数 默认值 参数 默认值Rs250m Tmax3msRi3Rs/4 TSS1sRmRs/4 TSRate1msγ 0． 8 Ds80μsTH6ms Dt80μsUrban-X 中，每个节点采用 3 个射频，分别为接受射频、发送射频和专用信道射频． 专用信道在整个网络生命周期中保持不变． Urban-X 算法考虑节点发送流量和信道的外部干扰． Urban-X 节点需知道它的邻居的流量信息，并依据节点的活动流量为节点分配一个优先级，优先级越高的节点占有最好信道的机会越多． 节点通过专用信道向它两跳内的邻居广播它的控制信息．SICA 是一种基于在线学习的半动态信道分配算法，是本文提出算法的基础，同样也考虑了内外部干扰和信道切换时间惩罚． 每个节点采用两个射频，分别是接受射频和发送射频．网络仿真场景如下． 仿真场景面积为 1000m ×1000m，100kbpsCBR 数据流，包大小 1kB，节点数 25～ 100． CA-DDCOP 和 SICA 采用 2 个信道，Urban-X采用3 个信道． Mi( c，g－i) 阈值设置为0． 5． 虚拟载波监听机制，建模为一个开关( On-off) 过程，即信道的忙、闲对应于开和关． 忙状态固定在10ms 时间段，空闲状态的时间呈负指数分布． Urban-X、SICA 算法的其它参数设置按相应的文献要求．
       5． 2 性能分析在仿真实验中，先给出 CA-DDCOP 算法解决MRMC 信道分配问题的动态寻优过程，其次将CA-DDCOP 算法的性能与相关算法进行比较分析．为调查 CA-DDCOP 算法的动态寻优过程，给出连续 10s 内平均数据传输率变化情况．该实验中，有50 个节点，采用2 对CBR 数据流，共运行 200s，每隔 5s 对信道进行重新分配，共 40 次．图 5 CA-DDCOP 算法的动态寻优过程Fig． 5 Dynamic optimization process of CA-DDCOP由图 5 可看出 CA-DDCOP 算法是逐步寻优过程． 在开始阶段对信道分配并不理想，有时平均数据传输率较低，但经多次协调之后，平均数据传输率明显提高，逐步趋于稳定较优状态．下面采用两个网络性能指标对算法进行评估和9 期 葛方振 等: 一种动态分布式约束优化问题协同求解算法809比较分析．1) 数据传输率( Data Delivery Ratio，DDR) ． 目的节点接收到的数据量与源节点发送的数据量的比值． 采用2对CBR数据流，源节点与目的节点间平均跳数为 4． 分析数据传输率与网络规模的关系． 显示不同数量的节点的网络的性能．图 6 显示 CA-DDCOP 算法的传输率分别高于Urban-X、SICA 约 15% 、5% ． 尽管 Urban-X 使用 3 个信道，CA-DDCOP 和 SCIA 仅使用 2 个信道，但CA-DDCOP 和 SCIA 的 数 据 传 输 率 明 显 高 于Urban-X． CA-DDCOP 传输率高于 SICA 主要在于CA-DDCOP 考虑节点混沌选择信道与邻域内节点信道组态的关系，而 SICA 仅考虑单个节点选择最好信道．平均数据传输率与网络节点数之间的关系Fig． 6 Relation between average data delivery ratio andnumber of nodes为 进 一 步 分 析 网 络 传 输 负 载 增 大 时，CA-DDCOP 算法数据传输率变化情况． 给出当数据流增加时，算法的平均数据传输率变化情况． 该图显 示 当 CBR 数 据 流 从 2 对 增 大 到 12 对，CA-DDCOP 的 数 据 传 输 率 变 化 最 小， 表 明CA-DDCOP 算法对流量负载增加不太敏感． 原因在于，CA-DDCOP 是基于局部信息的分布式协调机制设计，能有效协调信道分配，尽可能减少网络射频和信道的协调时间．2) 端到端平均时延． 数据包从源节点到达目的节点的平均时延．图8 给出3 种算法的端到端平均时延． 由图8 可知，CA-DDCOP、SICA 的时延明显低于 Urban-X，SICA 随节点数增加，时延增幅大于 CA-DDCOP． 原因在于，CA-DDCOP、SICA 考虑所有信道的发送射频 T 及时切换，而 Urban-X 不管信道有没有数据发送，需等待预定的时间段，才切换发送射频 T．CA-DDCOP 时延增幅小于 SICA，说明 CA-DDCOP的分布式协调策略优于 SICA 的非合作博弈策略．平均数据传输率与 CBR 流负载之间的关系Fig． 7 Relation between average data delivery ratio and CBRtraffic loads图 8 端到端平均时延比较Fig． 8 Comparison of end-to-end average delay with numberof nodes
      6 结 束 语本文提出求解动态分布式约束优化问题的算法CA-DDCOP． 该算法根据 DDCOP 的特性，将蚂蚁的混沌 行 为 和 自 组 织 行 为 作 为 求 解 DDCOP 的Exploitation 和 Exploitation 一对耦合操作，实现DDCOP 的协同求解方法． 然后，将 CA-DDCOP 算法应用于多射频多信道 Ad Hoc 网络的信道分配MRMC-CA． 在考虑信道分配的内外部干扰和信道切换时延的情况下，构建信道分配方案． 通过仿真，并与 Urban-X和SICA比较分析，结果表明CA-DDCOP算法求解 MRMC-CA 问题，可有效避开内外干扰，提高数据传输率和减少时延．
      参 考 文 献［1］Modi P J，Shen Weishen，Tambe M，et al． ADOPT: AsynchronousDistributed Constraint Optimization with Quality Guarantees．

本文来源：http://www.rjdtv.com/jisuanjilunwen/754.html