粒子群算法在综合布线中的应用

　　【摘要】针对综合布线工程中最难以设计的水平子系统，本文提出采用粒子群算法作为优化设计算法。通过粒子群算法的优化可以使得布线结构的设计更加优化，能够有效降低施工的成本。通过对比实验证明本文方法较传统算法的优化结果更好。
　　【关键词】综合布线；水平子系统；粒子群算法；最优化
　　【中图分类号】TP301.6【文献标识码】A
　　1前言
　　随着计算机和通信技术的飞速发展，各种设备能够通过网络互联，已成为一种基本的应用需求。而实现设备间网络互联应用的重要基础则是信息通路的建设；信息通路通常需要采用实体通信介质（一般为各种缆线）来进行联接，从而实现信息通路。实现信息通路就必然涉及到建筑物间和建筑物内的综合布线系统（PDS，PremisesDistributionSystem），然而在传统的结构化布线的设计当中，一般却难以获得最优化的布线方案，这使得整个信息网络实现方案存在着各种浪费和不合理的现象。
　　粒子群优化算法PSO（ParticleSwarmOptimization）是Kenney和Eberhart于1995年提出的一种智能优化算法，PSO算法源于对鸟群和鱼群等群体运动行为的研究，是一种基于迭代的优化工具。与常规的遗传算法（GA）相比较，它具有算法简单，收敛速度快，且对目标函数要求少等特点，因而得到了广泛重视，已成为一种重要的优化工具。本文通过在综合布线的设计过程引入粒子群算法，克服了传统方法的缺陷，使综合布线方案得到了进一步的优化，达到了总体布线长度最优的目的。
　　2基本理论
　　2.1综合布线系统及水平子系统
　　综合布线系统是一套开放式的布线系统，一般划分为：工作区子系统（WorkArea）、水平子系统（Horizontal）、管理子系统（Administration）、干线子系统（Backbone）、设备间子系统（EquipmentRoom）以及建筑群子系统（CampusSubsystem）六个子系统。它既能使各种类型的数据分别和交换设备或信息管理系统相连接，也能使这些设备与外部信息网络相连接。通常在PDS的应用中需要充分考虑通信技术的发展，设计时要留有足够的技术储备，能充分满足用户长期的需求。所以在设计结构化综合布线方案时，必须充分考虑所采用的网络技术及布线结构的优化，避免硬件资源的冗余和浪费。布线方案应具有高度的灵活性，各种设备位置的改变，网络拓扑结构的调整，应确保尽量不需重新布线，只要在配线间作适当的调整便可满足要求。
　　目前水平子系统基本都采用星形拓扑结构，其主要功能是实现信息插座和管理子系统间的联接。在选择水平子系统的联接介质时，需要根据建筑物内具体信息点的类型、容量、带宽和传输速率来确定。在水平子系统中一般采用超五类或六类非屏蔽的双绞电缆。由于水平子系统线路结构复杂，其设计量和工程施工量都是综合布线工程的重点，亦是本文讨论的重点，其他子系统本文暂不讨论。
　　2.2粒子群算法
　　粒子群算法是将每个粒子个体抽象为一个在维搜索空间中没有质量和体积的微粒（点），并在搜索空间中以一定的速度飞行。空间中的粒子追随当前种群中的最优粒子运动，直到在整个解空间中搜索到最优解为止。在每次迭代中，粒子通过追踪两个极值来更新自己。一个是粒子自己找到的最优解，称为个体极值；另一个是整个粒子群目前找到的最优解，称为全局极值在找到这两个最优值时，每个粒子会根据以下公式来更新自己的速度和位置：
　　其中，vk是粒子的速度向量；xk是粒子当前的位置；co，c1，c2表示群体认知系数。co一般取（0，1）之间的随机数；c1，c2取（0，2）之间的随机数。在每一维粒子的速度都会被限制在一个最大速度vMax（vMax>0）内，即vk>vMax或vk<-vMax时，vk=vMax或vk=-vMax。粒子群初始位置和速度随机产生，然后按照公式（1）进行迭代，直至达到最大迭代次数或找到满意的解为止。
　　3粒子群算法在综合布线中的应用
　　在工程施工中，水平子系统一般是分别对单一的楼层进行设计施工。通常水平结构中会存在一个或多个交换设备，并将建筑中同一水平结构中的所有工作子系统进行联接。施工目标是：要求所有工作子系统的数据都能汇聚，并能到达垂直干线子系统。因为不同楼层的建筑结构不尽相同，如何针对不同的物理结构设计不同布线结构，从而使得整个水平子系统的结构最为合理，即工程造价最低化、信息延迟最小化成了设计中首先要解决的问题。
　　对问题的描述：可移动的交换节点与终端之间的距离的总和，目标要求为距离总和最小化。约束条件为：节点与终端之间的距离不能大于90m，之后还需考虑实际施工的可行性，如是否有强电的支持及是否为架空等因素。通过对问题的数学分析，该问题为一带约束条件的路径最优化问题。问题本身为NP难题，目前还没有常规方法可以计算出精确解。通常采用"贪婪法"和"分支定界法"来求近似解，但效果并不理想。
　　针对布线最优化问题，粒子群算法应用的流程如下：
　　Step1：初始化种群中的粒子（初始位置x0和初速度v0），网络交换节点数目n，网络终端数目m。设定算法迭代次数TNow=0，最大迭代次数TMax。并随机给出一个合理的线路联接方案X0=（xij）nxm，并计算该方案的总体布线长度；
　　L0=l（x），（l（x）?90）
　　Step2：若TNow?TMax，算法终止，输出X0。否则转Step3；
　　Step3：按照公式（1）对算法粒子进行迭代，并随机生成网络交换节点i和终端j，令xik=0（k=1，2，…，m，k≠j），xij=1，此时变量记为X1；
　　Step4：若新方案合理（不存在l（x）>90），则计算新的总体布线长度L1，并且TNow←TNow+1；否则转Step3；Step5：若总体布线长度存在L1
　　在给定初始值之后，可以根据实际问题规模的大小选择相适应的最大迭代次数TMax。因为对问题求解的工程目标通常为总体造价最低，在新解生成时应注意交换节点的数量是可以变化的，所以还要了解多少长度的连接距离和一个交换节点等价，并考虑多种数量的交换节点的设计方案，并通过实际情况加以选择。
　　需要特别注意的是，在具体优化过程中可能会在算法执行中出现L1=L0，X1≠X0的情况，即不同的布线结构但布线总体长度一致的情况。本文的建议是采用随机的方式接受新方案，即设定一个随机数KRandom，若KRandom?0.5则接受新方案X0←X1，否则保留原有方案。
　　4对比实验及分析
　　A校办公楼对网络建设要求及基本格局情况：网络布局为单一水平结构，共有27间房间，其中包括2间会议室和1间网络管理室，普通房间需要布置2个信息接入端口，会议室A需要布置10个信息接入端口，会议室B需要布置8个信息接入端口，如图1所示。网络要求100Mbps到桌面，采用超5类双绞线材作为传输介质。
　　普通房间的信息端口共计48个，会议室共计18个，总计信息端口66个。考虑交换端口的容量及以后可能新增加的终端，并留有部分供维护和替换的端口，采用了3台24口的交换设备。算法设定交换节点为3，网络终端接口为66，起始迭代数TNow=0，终止迭代数TMax=1000，计算目标为布线总体长度最小化Min（L0）。计算所使用的设备为酷睿2双核3.2GHz的CPU，内存为2GB。
　　对比算法采用传统的"贪心算法"和"分支定界算法"两种算法。三种算法分别就该平面结构的布线工程进行10次给定不同的初始状态进行优化。表1为几种算法优化结果的比较。
　　通过表1可以看出，在综合布线中运用了粒子群算法优化后，无论是平均目标出长度还是最优目标长度的值都优于传统算法，优化率分别为5.36%和6.57%。这说明粒子群算法运用在综合布线设计中有效，可以使得布线工程趋于最优化，使得工程费用得以降低，减少了在设计中的不合理浪费。
　　从表2中可以看出，粒子群算法是三种对比算法中耗时最长的，这是因为粒子群算法是基于多重迭代计算的，每次迭代都需要对每个粒子进行比较和更新，所以时耗较长。但是从这里也可以看出，就目前时耗情况而言完全处于可以接受的范围内。加上粒子群算法本身所具备的天然并行性，若将其应用于计算机机群之上则可以获得更好的优化结果。
　　5结束语
　　综合布线系统工程中最为复杂的是水平子系统的结构优化，传统算法对于布线结构的优化程度不高，这在一定程度上造成了浪费。本文通过分析布线工程的计算模型，提出采用粒子群算法来对布线结构进行优化，相较传统算法获得的结果更好，使得工程应用中的费用得以降低，后续实验也证明本文方法的有效性。
　　参考文献
　　[1]何志议.智能大厦结构化综合布线系统设计方案综述[J].电气应用，2003（12）：39-42.
　　[4]李江涛.智能建筑结构化布线施工图计算机辅助优化设计研究[D].重庆：重庆大学，2004.
　　[5]尚晓航，解文彬，马颂阳.介质长度对五类非屏蔽双绞线电气性能的影响[J].北京联合大学学报，2006，20（3）：64-68.
　　[6]JavadSadri，Agenetic.BinaryParticleSwarmOptimizationModel[C].2006IEEECongressonEvolutionaryComputationVancouver，BC，Canada，2006.1.
　　作者简介：
　　谭岳武（1948-），男，湖南望城人，副教授；现任教于湖南信息科学职业学院，主要从事算法理论、算法应用的研究。
　　谭阳（1979-），男，湖南望城人，硕士，讲师，主要从事信息安全、智能计算等方向的研究。