自适应供电（精选7篇）
自适应供电 篇1
0 引言
配电网供电分区划分是配电网规划的一个关键问题，其结果直接影响配电网运行的经济性和供电可靠性。针对这一大规模、非线性问题，国内外已有一些学者进行了研究。传统的自由分区法、均一网格法和等负荷分区法没有考虑地块间的负荷差异等因素[1,2,3]。文献[4]考虑了各地区经济发展、灾害分布和地理环境等因素的影响，但该文献依旧采用的基于行政区划的分区方法。文献[5]提出了一种以各分区负荷最均匀为目标的启发式分区方法，该方法的核心仍然是等负荷分区，不能体现分区负荷密度的差异和变电站容量的差异。文献[6]利用Vorono图进行了变电站供电区域的划分，但该方法是在假定负荷均匀分布的前提下提出的，没有考虑负荷分布的不均匀和负荷对可靠性要求的差异。文献[7]从更好地实现配电网集中式差动保护的角度，研究了配电网分区的方法。提出将配电网转化成带权的广义节点的网络，然后根据各广义节点间的拓扑结构来进行分区。文献[8]从可靠性评估的角度提出了基于矩阵分析及运算的配电网分区方法。
本文在假设负荷分布不均匀，且负荷对供电可靠性要求不同的前提下，提出了一种基于自适应权重Voronoi图(以下简称“自适应V图”)的供电区域划分方法，根据单元地块的属性及变电站负载率自动调整权重因子，较好地解决了区域功能定位、负荷密度、负荷类型、行政区划和地理环境等因素对配电网分区产生的影响。
1 配电网供电分区的原则
《城市中低压配电网改造技术导则》(以下简称“导则”)、《配电网规划设计技术实施细则》均对配网分区有明确要求：中压配电网应依托变电站布点，划分为若干个相对独立的分区配电网，分区配电网应有明确的供电范围，不宜交错重叠。利用自适应V图进行配电网优化分区着重考虑以下几个问题。
(1)合理的供电半径。各分区内变电站应该有明确的供电范围，不宜跨区供电；分区面积大小适中，确保分区内变电站供电半径合理。
(2)满足容载比要求。按照分区供电的原则，各分区内变电容载比应满足《导则》要求，并且在校核分区容载比时，应当考虑到该分区负荷未来几年的增长速度。
(3)考虑区域功能定位。配电网规划应当与城市规划相协调，配电网分区应当充分考虑城市各区域的功能定位，同一功能定位的各单元地块应尽可能划分为同一分区。
(4)体现属地化管理。为了方便配电网的运行管理，配电网供电分区应尽可能与各供电所的管辖范围一致，同时兼顾道路、河流等地理因素。
2 自适应权重Voronoi图
2.1 基本Voronoi图
定义：设欧式平面上的一个点集为，则任意点的Voronoi图定义为
其中：表示点x与pi间的欧式距离；x为平面上的点。
区域V(pi)称为以pi为生长点(或顶点)的Voronoi多边形(简称V多边形)。各个生长点的V多边形可以共同组成最近点意义下的V图，如图1所示。
平面上的Voronoi图可以看成是点集P中每个顶点以相同的速度向外扩张，直到彼此相遇为止而在平面上形成的图形。这一描述与供电区域划分具有极大的相似性，可以反映变电站位于负荷中心及其空间影响范围。
2.2 常规加权Voronoi图
常规加权Voronoi图是基本Voronoi图的一种扩展形式。欧式平面上的点集，对每个顶点，分别赋以非负实数权重，称为点x和pi之间的加权距离，为点x与pi之间的欧式距离，则，点pi在权重为wi时的Voronoi区域为
同样，常规加权Voronoi图也适用于空间剖分，位于常规加权Voronoi图的某V曲边形中的每个点到该曲边形发生元的距离，与该点到其他曲边形发生元的距离之比小于两个发生元的权重之比。常规加权Voronoi图用于各发生元权重有较明显差别情况下的空间剖分。这一特性表明，可以利用权重来反映负荷分布不均匀、各变电站额定容量不同对供电区域划分的影响。
2.3 自适应权重
常规加权Voronoi图应用于供电分区划分时，各发生元的权重是固定的，即假定在同一个分区内各地块的负荷密度相同。实际上因为各地块的功能定位不同，在同一分区内，位于发生元不同方向上的地块负荷情况可能差异较大。另外，常规加权V图也不能准确反映归属地及地理因素对供电分区划分的影响。考虑以上因素，将供电区域按照街道、河流划分为若干地块单元，自适应权重V图发生元在扩散过程中，根据各单元地块具体情况及变电站负载情况动态调整发生元的权重，发生元在各个方向上的扩散速度将不再固定。
自适应权重主要考虑的是变电站带负载能力、供电半径、归属地、及地理障碍对供电分区划分的影响。变电站主变容量不同，当前负载率不同，向周边负荷供电的能力也就不同。为了减少电网投资和网络损耗，负荷点至变电站的距离应最短，同时线路路径应尽量避免跨越河流、山川、高速、铁路等屏障。因此，可以根据变电站主变负载率、负荷密度、供电距离及其路径条件和归属地情况构造自适应权重wi。
其中，rMi为负荷密度系数，设地块i的负荷密度为，取该地区的平均负荷密度作为基准值，则地块i方向的负荷密度系数为为主变负载率系数，设变电站i主变容量Si，当前负荷Li，则变电站i的负载率系数为为供电距离系数，设负荷点至变电站的供电距离为Di，则,为基准值，城镇取2 km，农村取10 km;为考虑自然地理屏障的修正系数，根据跨越难度确定，难度越大数值越小，取值范围0～1;为归属地系数，负荷点与变电站在同一管理区域取1，分属不同区域取0;a、b、c、d、e为加权系数，a+b+c+d+e+f=1，为简化起见，此处令a=b=c=d=e=0.2。
3 配电网供电分区的划分
3.1 应用自适应V图划分供电分区的基本步骤
根据已知变电站容量、位置和供电区域内负荷分布，应用自适应V图划分供电分区的流程如图2所示，其中n为生成元数量，每个生成元沿m个方向扩散，具体步骤如下。
(1)首先根据街道或自然障碍将供电区域划分成若干小地块，根据各地块的面积、用地属性和发展前景计算各个地块的用电负荷。
(2)将供电区域内的变电站抽象为元点，即V图生成元。
(3)以生成元为圆心，应用搜索策略向各个方向扩散，计算各个方向上地块的负载率系数rLi，供电距离系数rDi，屏障修正系数rBi归属地系数rPi和负荷密度系数rMi，从而得到生成元在该方向上的权重，动态调整生成元在不同方向上的扩散速度。
(4)判断变电站负载率是否已到安全负载率上限，如变电站i已达到安全上限，则该变电站退出地块搜索，若所有变电站负载率均已达安全上限，结束地块搜索，转步骤(7)；如未达到，执行步骤(5)。
(5)判断生成元各扩散方向分区边界是否与相邻分区相遇，如相遇，中止这两个分区在该方向上的扩散。
(6)如果所有地块搜索均完毕或所有变电站负载率均已达安全上限，则结束搜索，各生成元形成的多边形Voronoi区域就是变电站的供电区域；否则转步骤(3)。
(7)以变电站为生成元划分的供电区域不宜直接作为配电网供电分区的结果，需要进行适当调整。
这是因为在城市高负荷区域可能集中分布有多座变电站，应用V图得到的分区面积就会偏小，且这类地区常常有一级重要负荷需双电源点供电，这样就不能直接按变电站的供电范围划分供电分区。可以根据城市规划中区域功能定位、各变电站供电区域的面积及归属地，适当合并变电站供电区域，最终确定配电网分区。此时可能会出现同一分区内存在2～3座变电站的情况。
3.2 虚拟生成元
在以变电站为生成元，应用V图分区时，当某些乡镇(或新建开发区)内无变电站时，该乡镇(或开发区)就会被分割后，划分到周边相邻分区中。这一结果往往与实际运行管理的情况不相符，还有可能造成部分分区过大，达不到配电网分区指导配电网规划、建设和运行的目的。
针对这一情况，本文引入了“虚拟生成元”的概念，即一个虚拟的变电站。该虚拟生成元的容量和位置确定，可以分为以下几种情况。
(1)该区域内有在建或规划建设的变电站；以该变电站的容量和位置作为虚拟生成元即可。
(2)该区域由区外紧邻的变电站供电；按照该变电站供电容量分配拆分变电站，即虚拟生成元的容量为向该区域供电的容量，虚拟生成元的位置为该区域的负荷中心。
(3)该区域内暂时无新建变电站规划，且供电变电站相聚较远：根据该区域负荷预测的结果，按照容载比要求，确定虚拟生成元容量，并将虚拟生成元布置在负荷中心。
4 算例
某市城区的供电区域总面积为52.61 km2，包括城区(中干河以东、新328国道以北)、经济开发区(中干河以西)和桥头镇(中干河以东、新328国道以南)三个行政单位。根据城市规划，城市空间布局分为5个居住组团(旧城、城北、城西、城南、城东)和4个工业组团(开发区北、开发区南组团、石黄-梁徐工业组团、民营产业中心组团)，如图3所示。
目前区域内共有6座变电站，分别为110 kV官庄变(63 MVA),110 kV太宇变(63+50 MVA),110 kV姜堰变(80 MVA),110 kV中干河变(50 MVA),110 kV城西变(50+40 MVA)和110 kV黄村变(50 MVA)。
采用基本V图划分配电网供电分区结果如图4和表1所示。本文采用的基本V图考虑了变电站容量因素，因此各分区变电站的负载率均在合理范围之内，且变电站基本处于分区中心位置。但因为未考虑地理障碍及行政归属地影响，所以分区结果存在跨越大河(中干河)、交通快速路(新328国道，同时为景观道路)、及跨行政区域、跨功能组团的现象。
图5和表2是基于自适应V图(无虚拟元)配网分区的结果。显而易见，与基本V图相比，自适应V图可以很好地处理地理障碍和行政归属地与配网分区的关系。图6以分区6为例说明了自适应V图生成元的扩散过程，具体参数如表3所示(因篇幅所限本文仅列出了前2步的数据)。
但从表2也可以看出，无虚拟元自适应V图可能会出现个别分区面积偏大和个别变电站负载率偏高或偏低的情况。解决该问题的方法有两种：(1)减小式(3)中rPi归属地系数的权重e，可能又会带来跨区供电的问题；(2)引入虚拟元。考虑110 kV姜堰变位于老城区增容扩建困难，而110 kV太宇变容量较充裕，为避免大量10 kV线路跨越主干道景观道和跨区域供电，规划在分区4建设开关站，即虚拟元1(50 MVA)，其容量来自110 kV太宇变，如图7所示。远景年，根据负荷增长情况，可以考虑将该开关站扩建为变电站。虚拟元2主要是考虑城北组团为新建旅游开发区，未来负荷增长潜力较大，而110 kV姜堰变供电压力较大，且供电距离偏大，建议增设变电站，现状容量暂由110 kV姜堰变提供。基于含虚拟元的自适应V图配网分区结果如图7和表4所示，有效解决了供电面积、变电容量和归属地之间的矛盾。
5结论
(1)基于自适应权重V图的配电网分区方法综合考虑了负荷密度、主变负载率、供电半径、地理屏障和归属地等因素，可以根据负荷分布的实际情况灵活调整各个方向上的扩散速度，不仅保证了各分区变电站负载率、供电半径均在合理范围之内，同时避免了跨越大江大河、主干道，及跨区域供电的情况，使得分区结果更贴近实际需求、方便运行管理。
(2)结合城市发展规划，根据区域功能定位情况及未来负荷增长趋势，在恰当的位置引入虚拟元，使得配电网分区与城市规划衔接的更好，有利于配网从现状网架向目标网架的过渡，实现配网的可持续发展。
参考文献
[1]肖峻,高海霞.城市中压配电网评估方法与实例研究[J].电网技术,2005,29(20):77-81.XIAO Jun,GAO Haixia.Evaluation method and case study of urban medium voltage distribution network[J].Power System Technology,2005,29(20):77-81.
[2]肖峻,崔艳妍,王建民,等.配电网规划的综合评价指标体系与方法[J].电力系统自动化,2008,32(15):36-40.XIAO Jun,CUI Yanyan,WANG Jianmin,et al.A hierarchical performance assessment method on the distribution network planning[J].Automation of Electric Power Systems,2008,32(15):36-40.
[3]李智宇,陈建福.基于优化分区的配电网规划研究及实践[J].广西电力,2006(4):1-4.LI Zhiyu,CHEN Jianfu.Study and practice about distribution network planning based on optimal partitioning[J].Guangxi Electric Power,2006(4):1-4.
[4]刘念,马丽.计及抗灾能力和地区特点的配电网规划方案综合评估[J].电网技术,2012,30(5):219-225.LIU Nian,MA Li.Synthetical assessment on distribution network planning scheme considering anti-disaster ability and regional characteristics[J].Power System Technology,2012,30(5):219-225.
[5]宋蒙,刘健,刘巩权.基于优化分区的城市配电网架规划[J].继电器,2005,33(23):31-35.SONG Meng,LIU Jian,LIU Gongquan.Urban distribution network planning based on optimal partitioning[J].Relay,2005,33(23):31-35.
[6]杨丽徙,王金凤,王家耀.基于Voronoi图的配电变压器定位和供电区域的[J].测绘通报,2004(5):33-35.YANG Lixi,WANG Jinfeng,WANG Jiayao.Locating of distribution transformers and power supply area plotting based on Voronoi diagrams[J].Journal of Mapping,2004(5):33-35.
[7]张新昌,张项安,刘星.基于广义节点的配电网区域控制划分[J].电力系统保护与控制,2014,42(7):122-127.ZHANG Xinchang,ZHANG Xiangan,LIU Xing.Partition operation on distribution network based on theory of generalized node[J].Power System Protection and Control,2014,42(7):122-127.
[8]张彼德,刘代伟,周江平,等.基于图论及联系数的复杂配电网可靠性评估[J].电力系统保护与控制,2012,40(21):74-79,155.ZHANG Bide,LIU Daiwei,ZHOU Jiangping,et al.Reliability evaluation of complex distribution networks based on graph theory and connection number[J].Power System Protection and Control,2012,40(21):74-79,155.
[9]TEMRAZ H K,SALAMA M M A.A planning model for siting,sizing and timing of distribution substations and defining the associated service area[J].Electric Power Systems Research,2002,62(2):145-151.
[10]YU Yixin,HUANG Chunhua,WANG Chengshan,et al.Optimal planning of distribution substation locations and sizes-model and algorithm[J].International Journal of Electrical Power&Energy Systems,1996,18(6):353-357.
[11]黄伟,庞琳,曹彬,等.基于分区解耦的配电网状态估计的分布式并行计算[J].电力系统保护与控制,2014,42(15):45-51.HUANG Wei,PANG Lin,CAO Bin,et al.Parallel and distributed computing for an area-decoupled state estimation method for distribution system[J].Power System Protection and Control,2014,42(15):45-51.
自适应供电 篇2
基于可分离变压器感应耦合的非接触电能传输技术,克服了通过导线直接接触进行电能传输的传统供电方式的缺点,减少了供电系统对环境的高频电磁污染,同时避免了机构磨损和积碳等问题。由于不存在电火花,因此其对特殊环境的安全具有重要意义[1,2]。受到工作原理和其他因素的影响,非接触供电系统的传输效率和功率相对较低,而提高系统的传输效率又是节能的必然要求。在实际的非接触供电系统中,负载往往是时变的,随机、动态的负载直接影响系统的传输效率[3,4,5]。本文针对随机负载的应用条件,通过智能调谐方法提高非接触供电系统的传输效率。
1 谐振频率对系统效率的影响
无论是感性电路还是容性电路,都可以通过补偿的方式改变电路的特性,根据原边和副边补偿电容位置的不同,非接触供电系统一般分为4种拓扑结构[6]。但无论何种拓扑结构,电路分析所采用的方法都是类似的,因此本文不讨论非接触供电系统电路的补偿方式,而只是假定电路是存在感性和容性元件的串联补偿型电路。简化中间环节如整流与逆变后,非接触供电系统可以用图1所示的物理结构来描述[7]。
可分离变压器的原、副边线圈之间的气隙使一次侧原边线圈及二次侧副边线圈都存在较大的漏感,这是导致系统效率低下的原因之一。同时,由于漏感,系统模型应考虑互感的特征[8,9]。图1中,ui为原边系统激励电源电压,ii为流过变压器原边的电流,Ri为原边线圈内阻,Ci为原边电路所含器件的电容,Li为原边电感,M为互感系数;io为副边工作电流,Lo为副边电感,Co为副边电路所含器件的电容,ZL为负载阻抗(本文中可看作纯电阻负载,下文以RL表示)。本文忽略了副边内阻Ro,将其看作该负载阻抗的一部分。
根据图1,分别对变压器的原边系统和副边系统列出环路电压方程:
其中,ω为激励电源的角频率。方程中对可分离变压器采用了互感模式,这是因为可分离变压器的原边与副边之间无物理连接,完全是一种开放的结构,能量的传递完全依靠互感的作用。
为节约能源,电力系统应尽量提高传输效率,因此本文采用传输效率作为衡量系统性能的指标。定义传输效率η为副边负载RL得到的功率PL与原边输入功率Pi的比值。RLC电路处于谐振状态时,电路中的电流最大,电能传输能力最强,因此应使可分离变压器的原边和副边同时处于谐振状态,此时系统的工作角频率满足式(3):
解方程式(1)—(3),得到系统的传输效率表达式:
从式(4)可以看出,系统处于谐振状态时,影响系统电能传输效率的主要因素有谐振频率、互感系数、负载阻抗以及原边内阻。对于一个确定的系统,其内阻已经无法改变,而互感系数与变压器的材料、变压器结构和原、副边的相对位置等因素有关,因此,本文主要针对系统的工作频率进行探讨。令式(4)中M、RL、Ri为定值,单独考察ω对传输效率的影响,得到图2所示的趋势图形。从式(4)和图2可知,升高系统的谐振频率可提高电能的传输效率,但是当频率增大到一定程度时,其对传输效率的贡献将迅速减小,甚至变得非常微弱,且过高的电路变换频率会大幅增加系统成本和设计难度。因此,兼顾传输效率和系统成本,宜将谐振频率设定在50~100 k Hz。
2 负载变化对系统工作状态的影响
由式(4)可见,增大负载电阻可以提高传输效率,但是实际的负载是动态、随机的。如通用非接触充电系统,每次受电体的负载都可能不同,且可能同时存在多个负载。负载的变化不仅影响系统的传输效率,而且会通过改变原边阻抗影响系统稳定性。假定系统处于谐振状态,即工作频率满足式(3),那么在副边负载变化后,根据式(1)、(2)可得原边系统基波等效阻抗Z的表达式:
由式(5)可见,负载改变后,阻抗的电抗值也会随之变化,即负载的改变导致原边电路的特性发生了变化。如果此时电源的激励频率不变,则系统必然偏离谐振状态。换言之,即使系统原来处于谐振状态,由于负载RL或其他参数的改变,系统的固有谐振频率必然发生变化,导致系统偏离谐振状态[10,11,12]。此时,如果系统激励电源的频率不变,系统将会失谐,导致传输能力下降。因此,在负载变化后,如何使系统重新进入谐振状态具有重要意义[13,14]。
3 基于最大电流原则的自适应调谐方法
至少存在2种情况会导致实际的非接触供电系统偏离原来的谐振状态:负载的改变,随机性的负载改变了系统原边的固有谐振频率;系统中器件的参数会随着时间和环境改变,例如电容受环境的影响以及老化等,此时式(3)不再成立。为了保证系统的传输效率和功率,必须使偏离谐振状态的系统回归谐振状态[15,16,17]。
在图1的电路中,原边系统和副边系统都是RLC串联电路,系统偏离谐振状态后,可以通过调整激励电源的工作频率,使系统重新回到谐振状态,但是谐振频率可能升高,也可能降低,而谐振频率的小幅下降就可能引起传输效率的大幅下降。因此通过改变激励电源频率使系统回归谐振状态并非最优方案。
本文采用固定电源频率调节参数的方法进行自适应调谐。系统工作过程中激励电源的频率一般较高且保持不变,以保证系统的传输效率。通过调节补偿电容值,使偏离谐振状态的系统重新进入谐振状态。RLC串联电路发生谐振时回路中的电流最大,通过检测回路电流来判断系统是否处于谐振状态。调谐的基本原理如图3所示,原边系统中的补偿电容C1和副边中的补偿电容C2是可变的,它们单独与直流电机相连,通过改变直流电机的转角,可以连续改变C1和C2的值,即改变了原边和副边的容抗值,从而改变系统的谐振频率。调谐过程如下:
a.计算机检测电流值;
b.通过控制直流电机转动固定的角度,将补偿电容值增大一个步长,再重新检测电流值,如果此时的电流值大于上一次检测到的电流值,转步骤c,否则转步骤d;
c.将补偿电容值增大一个步长并检测电流值,重复该步骤直至后一次检测到的电流小于前一次检测到的电流,说明前一次设定的电容值恰好使系统处于谐振状态,回路中的电流最大,调谐过程结束;
d.将补偿电容减小一个步长,再次检测电流,重复该步骤直至检测到的电流大于上一次检测到的电流,转步骤c。
上述调谐方法同时应用在原边电路和副边电路中,以保证原边和副边都工作在谐振状态。
4 实验
本文采用自行开发的非接触供电装置验证本文方法的有效性。实验装置原边和副边的耦合电感被制作成直径为30 mm的空心圆形,两线圈之间的气隙固定为1.5 mm。实验装置的电路原理同图3,参数如下:RL阻值可调,最大功率为100 W;Ri=3Ω,Ro=2Ω;Li=Lo=43μF;Ci=0.2μF,Co=0.1μF;C1、C2在0~10μF内可调,电源激励频率恒为55 k Hz。实验开始时,将RL调至3Ω。此时关闭控制系统,使可调电容C1和C2脱离电路,系统工作在开环状态。待系统进入稳态后,非谐振状态下的负载电流io见图4;然后将可调电容C1和C2接入电路,开启控制系统,待系统进入稳态后,谐振状态下的负载电流i′o见图5。通过比较电流io和i′o的波形和幅度,观察控制系统的自适应调谐能力。需要说明的是,电容C1和C2的调节不是同步的,而是各自独立进行的;实验过程中RL阻值不断变化。
电流的测量是通过电压转换的形式进行的,实际测量的是电路中固定电阻Ro两端的电压,因此Ro实际上是采样电阻。采用示波器检测采样电阻Ro两端的电压,以观测负载电流状态。
从图4和图5可以看出,在保持激励电源的频率不变的条件下,改变负载后,由于系统未进入谐振状态,负载电路中的电流形态变坏,已经不是标准的正弦波形,电流值也很低。开启控制功能后,系统具有自动调谐功能,重新进入谐振状态后,流过负载的电流值上升,电流波形也接近正弦波。
5 结论
谐振频率、负载阻抗对传输效率有重要影响,且负载和电路参数的变化会引起原边和副边系统偏离谐振状态,从而恶化系统的传输性能。为了保证系统良好的传输能力,必须使系统重新回到谐振状态。针对非接触供电系统的负载具有随机性的特点,设计了采用固定激励电源频率与调节电路器件参数相结合的自适应调谐方法,激励电源保持较高的固定工作频率,根据最大电流原则调节回路的补偿电容值,使系统重新回归谐振状态。实验结果表明,失谐的系统完全可以重新进入谐振状态。回归谐振状态后,系统的传输效率和功率都大幅提高。
必须说明的是,虽然本文对保持非接触供电系统的调谐方法进行了探讨,但仍有许多问题值得进一步研究,例如如何使系统快速达到谐振状态等。
摘要：建立了基于可分离变压器的感应耦合电能传输系统的物理模型,从理论上研究了传输效率的影响因素。数学分析表明,动态负载会导致电路系统的电抗发生改变,因此系统会偏离谐振状态。提出了采用固定激励电源频率与动态调节电路无功器件参数相结合的方法进行自适应调谐。激励电源保持较高的固定工作频率,实时检测负载电流,根据最大电流原则调节回路的补偿电容值,使系统重新回归谐振状态。实验结果表明,所提方法能使系统重新回归谐振状态。
自适应混合入侵防御 篇3
关键词：自适应,入侵防御系统,异常分类器,签名过滤系统,指令集随机化
1 引言
由于信息安全与网上信息对抗的需求,使得如何增强计算机系统和网络系统的安全性的研究成为了举世瞩目的焦点[1]。网络防御系统的目标是预先对入侵活动和攻击性网络数据进行拦截,避免其造成损失[2],但一个关键问题是网络防御系统对攻击行为不能自动做出一个可靠的,有针对性的及适应性的反应[3]。当溢出被一些未曾见过的攻击利用时,这个问题将会被放大。网络防御系统通常是由基于网络的IDS(Intrusion Detection System)的和包过滤防火墙组成,由于这些这些系统本身的缺点,使它们难以确定和描述新的攻击并智能化的应对它们。
由于IDS只能被动的检测攻击,而攻击防范往往是留给防火墙的任务。当然成功阻止一次确定的攻击通信需要一个灵活和明确的策略,此外大量的网络流量与签名进行匹配往往需要专业的硬件设备并假设这些签名准确的存在。另外加密流量和隧道流量成了IDS和防火墙共同的问题,因此无论是IDS还是防火墙都无法确定一个数据包在终端主机被进行了怎样的处理,从而导致它们做出错误的决定[4]。
这些阻碍促使我们将安全控制策略的放置更接近终端主机(例如,分布式防火墙)[5]。这种方法对系统安全性的保护不仅有利于企业级网络,而且还包括那些家庭网络用户。这种“纵深防御”表明传统的外围防御(如:防火墙)已被应用到基于主机的防护机制中。本文设计了这样一个系统,它采用混合异常检测及签名检测的方案,自适应地应对新的攻击。
2 自适应混合防御系统关键部件及技术
2.1 混合检测
一般情况下,检测系统仅仅依赖于签名并不能启用防御系统来应对前所未见的攻击行为。另外,基于异常的分类器可以识别新的行为,但往往无法分辨以前所未见的这些行为是“好”还是“坏”。这个盲点通常会导致较高误报率,并要求这些分类器进行过大量的训练。
混合检测系统以入侵防御系统IPS(Intrusion Prevention System)为基础:是一个有自动反应能力来阻止攻击行为的系统。我们的混合系统的核心是一种基于异常的分类器,它结合反馈信息调整其模型并自动生成已知恶意行为的签名。我们的异常检测是基于PayL[6],但也可用于其他分类器[7]。
对于一个混合系统最大的障碍是反馈信息的来源。理想的情况下,它应该是自动化的并且对用户是透明的。例如,对垃圾邮件分类器的反馈可能是用户在自己的电子邮件点击按钮,通知客户端的邮件服务器,以考虑将其归类为垃圾邮件或不适当的电子邮件。这种反馈循环是一个网上监督式学习的实例,它将监督负担分配给了每一个系统用户。我们系统的反馈机制加强了无监督的网上学习。信息来源是基于X86模拟器,STEM[8],即以指令集随机化增强保护系统进程。
2.2 指令集随机化
ISR是创造一个独特的运行环境的过程并以此有效地阻止代码注入式攻击。创建这种环境的目的是在这个指令集执行一些可逆转换。
因为攻击者通过精心设计与所预期的执行环境相匹配,致使攻击者不会轻易改变他的攻击代码,而攻击代码与特殊环境的不匹配致使攻击代码在特殊环境执行无效,从而导致攻击失败。ISR方法以前已被证明在阻止代码注入式攻击上的成功[9,10],这种技术通常与空间地址混合来阻止“跳成libc”攻击。
指令集随机化需要执行环境有能力以终止在运行时随机的或解码的二进制指令流。对于机器代码,这一要求意味着,要么处理器硬件包含解码逻辑,要么该处理器以软件的形式出现。
ISR的实践形式,使我们能捕获注入代码和与它相关的被列为异常的输入。Barrantes等人[11]表明,在一些控制流字节切换(两个或三个指令)到注入代码的过程中,代码注入攻击被保护的二进制文件失败。因此,在程序停止执行时,指令指示器(有很高的几率)表明此代码是恶意代码。我们可以提取这些代码,并传送给我们的过滤器来创建一个新的签名并更新我们的分类器的模型。
3 设计与实现
FLIPS的设计基于两个主要部分:应用程序监管框架和过滤代理。该设计的一个主要目标是保持系统的模块化并可扩展部署在一个主机上。(图1显示了这种设计的高级视图。)受保护的程序可以是一个服务器等待请求或是接收客户端程序的输入,如果被视为恶意的将被过滤代理丢弃。如果监控器检测出被保护的程序出现了错误,这标志过滤器在更新其签名和模型。
过滤代理的主要功能是对输入进行评分和分级并选择性的进行丢弃,代理则是两个主要分类方案的混合。基于特征的过滤器可以对某个请求进行评分和丢弃如果它与已知的恶意数据相匹配,而基于异常的分类器则可以对输入程序进行评分和丢弃如果它超出了正常的模型范围。
应用程序监管框架的主要功能是阻止溢出,修复可能被利用的漏洞,并将溢出信息汇报给过滤器和分类器。监管框架可以包括些基于主机的监控器,由它们提供给代理各种补充的反馈信息。我们的原型实现是基于一种提供与代码注入式攻击有关信息的监控器。
请求从过滤代理通过,如果被认为是恶意的将被丢弃。包过滤防火墙为应用程序提供保护,只允许本地代理实例连接应用程序。应用程序处理这些请求并通过代理传回响应。如果某个输入引起代码注入攻击,监管框架会将注入代码连接到代理,代理将会更新其模型和签名。
3.1 HTTP代理和Pay L
HTTP代理是一个简单的对每个输入请求产生一个新的线程实例的HTTP服务器。在服务程序中,代理调用一系列对H T T P请求的过滤器对象。我们的默认过滤器执行维护三个基于签名的过滤器和一个分类器对象。PayL实现了分级界面以对每个基于异常的H T T P请求给予标记。当代理启动时,它创建一个PayL实例并提供给PayL一个traffc文件样本用以改进。
我们构建了一个HTTP代理(Apache)以保护HTTP服务器免受恶意请求的攻击,代理通过调用三个过滤机制及P a y L来决定如何处理每一个H T T P请求。
过滤器实现的核心是将其划分为两个子程序,checkRequest()程序执行基本过滤和分类工作。它维持4数据结构用以支持过滤功能。第一个为“可疑”输入要求清单(由PayL确定)。这一清单作为一个缓存为匹配以证实的恶意输入提供了良好的反馈机制,但值得注意的是,此清单并不用于删除请求。其余的数据集合形成一个三级过滤结构,在权衡复杂性的同时更加积极的实现过滤。这些清单并不是通过PayL确定而是通过反馈机制产生。第一层的过滤为直接匹配。该过滤器是最实惠的,即使略有质变但它却最有可能阻止恶意请求。第二个过滤器是一个反向查找过滤器,它们的存储请求由PayL的评分来决定。最后,由最长公共子串过滤器来提供昂贵但却是捕获恶意请求的最有效手段。
第二个组件作为代理的反馈机制,它是一个后台线程监听,关注来自于S T E M所包含的恶意二进制代码,此线程仅读取一个字节并检查它们是否与我们先前所熟知的“可疑”输入相匹配(如PayL分类),如果不是,那么该线程将会把检测范围扩大到之前见过的包含那些缓存较小的所有请求。匹配是目前最常用的子算法,如果匹配成功,则该请求将被用在上述筛选数据结构。如果没有,以此恶意字节序列为基础,一个新的请求将被创建并写入过滤器。
我们的监管架构是一个应用级程序库,它提供了一个模拟器在去随机性指令流和底层硬件正常执行的指令流之间自由切换的能力,如图3所示,将要被仿真的代码段将4个特殊标签包裹起来。
此程序为一个使用S T E M标签的实例。
STEM是一个x86模拟器,可以有选择地调用任意的代码段,允许我们在同一进程内部混合仿真及非仿真的执行。模拟器允许我们监测当执行指令时的随机处理错误,撤销由内部代码故障引起的内存变化,并模拟一个从上述调用函数返回的错误,我们的一个主要假设是我们能够在错误和异常集之间建立一个映射,这种错误和异常可能出现在程序的执行以及该程序代码处理的错误集。
3.3 ISR技术
主循环由仿真器读取,解码,执行以及每次撤销一个指令组成,在抓取指令之前每一项是随机发生的,由于x86架构包含可变长度的指令,在指令流翻译出足够的字节是解码成功的关键。否则,可能会产生无效的操作。为了使问题简化,我们假设每个指令的最大长度为(16字节)。16位字XOR'd伴随16位密钥,并复制到缓冲区。获取/解码函数读取缓冲区和提取一个指令。伴随处理指令的准确长度程序计数器是递增的。如果指令在1 5字节或更少的情况下,不必要的去随机将会发生,但这是可变长度指令不可避免的一个副作用。如果注入的代码位于执行路径的任何位置,异或函数会将其转换为一个非法操作码或指令,这样将会访问无效的内存地址。如果在仿真过程中发生异常,S T E M将会通知在指令指示器中的代码服务器,STEM每捕捉1KB的代码将会打开一个简单的TCP套接字代理,然后STEM将模拟一个从函数处返回的错误。
4 模拟实验
我们目的是表明主动防御和签名相结合是有价值的,甚至是一个相当优化的代理执行。我们的评估主要有三个目的:
1.表明该系统能够很好的进行分类。
2.表明该系统可以在端至端间执行。
3.表明该系统具有相对良好的性能。
第一个目标是为PayL计算出完整的ROC曲线。第二个目标是通过一个端对端的实验检验该系统检测攻击的速度。记录过滤器捕捉到的攻击字节,建立适当的过滤规则,并终止下一个此攻击实例。我们像代理发送由同样攻击组成的请求流并测量代理过滤的时间。第三个目标是测量代理服务器处理两种不同H T T P痕迹的额外时间。
Apache2.0.52作为一个简单的修改配置文件的基本生产服务器实例,关闭“KeepAlive”的属性设置,然后,一个简单的awk脚本重建HTTP请求。代理服务器由JAVA编写,与Linux平台下Sun JDK 1.5.0,并在Linux平台下Sun JVM 1.5.0上运行。代理服务器运行在双核至强2.0GHz处理器,1GB内存,操作系统为Fedora Core 3,内核版本2.6.10-1.770 FC3smp。生产服务器平台运行在双核至强2.8 H z处理器,1 G B内存,操作系统为Fedora Core 3,内核版本2.6.10-1.770FC3smp。代理服务器与生产服务器通过一个千兆以太网交换机连接,实验进行前对服务器进行重置,同样数据进行重复进行10次实验。
我们通过运行Apache web服务器和执行微基准测试在一些shell实用程序上,以此来评估STEM的性能。我们选择Apache flood httpd实验工具,以评估和比较非仿真和仿真的Apache版本处理请求的速度。在实验中,我们通过已处理的请求总数来决定测量性能,如表4所示,每秒处理请求的总数是由在一小段时间内所发送、处理的请求推测得到,而并不是意味我们的Apache实体每秒能够承受6000次请求。"emurand"符号表明STEM的(随机仿真)使用。
我们选择了一些常见的公式并测量有S T E M和没有S T E M情况下大负荷工作不同试验类型的性能。如预想中的一样,在仿真大部分应用时会对性能有很大影响。实验表明,仅在仿真潜在易受攻击的代码部分时存在明显超越整个系统仿真性能的情况。
PayL是一个基于内容的异常检测器。为了在FLIPS混合PayL,采用PayL在HTTP上的请求。在网络要求上测试PayL运营的有效性,收集了5MB的HTTP协议。这个数据集合有多种红色代码和其他恶意要求。作为底线标准,可以人工识别恶意入侵。接收机工作特性曲线如图4。
从图中可以看出,关于HTTP的PayL的分类结果比较普通。当所有的红色编码和尼姆达疑问被成功的防御,仍有许多看起来不是异常的入侵的查询,PayL不能辨认。如果P a y L工具来观察整个HTTP请求,包括实体自身,结果将更精确。PayL本身并不能保护服务器,并且需要更多的信息来调整其模型。
5 结束语
传统的入侵检测系统侧重于查明试图攻破计算机系统和网络。现有的入侵检测,无论是基于主机的IDS还是基于网络的IDS,在很大程度上都依赖于网络管理员的能力和直觉,需要人工地调整入侵检测系统。攻击事例和管理员的经验是入侵检测中最为重要的两个方面,IDS的开发与升级需要攻击事例和管理员经验这两方面长时间的原始积累。
我们提出FLIPS入侵防御系统,采用了异常分类组合方式和签名匹配二进制代码块注入攻击,此种混和式检测系统的反馈由STEM来提供,x86模拟器能够将指令集的执行随机化(ISR)。STEM可以识别插入的代码,自动恢复的攻击,并将攻击代码提交给异常和签名分类器。我们已经展示了FLIPS如何发现,制止,修复,并创建一个以前未知的攻击签名。虽然我们只展示了FLIPS对HTTP服务器保护的实现,然而FLIPS的机制也广泛适用于基于主机的入侵防御。
参考文献
[1]孙宇.网络入侵防御系统(IPS)架构设计及关键问题研究[D].天津:天津大学,2005.
[2]刘才铭.基于免疫的多通道入侵防御模型[J].计算机应用研究,2008,2(25):.
[3]R.E.OVERILL.How Re(Pro)active Should an IDSBe?In Proceedings of the 1st International Workshop onRecent Advances in Intrusion Detection(RAID)[C].Septem-ber 1998.
[4]M.HANDLEY,V.PAXSON,and C.KREIBICH.Network Intrusion Detection:Evasion,Tra?c Normalization,and End-to-End Protocol Semantics[C].In Proceedings ofthe USENIX Security Conference,2001.
[5]S.IOANNIDIS,A.D.KEROMYTIS,S.M.BELLOVIN,and J.M.SMITH.Implementing a Distributed Firewall.InProceedings of the 7th ACM International Conference onComputer and Communications Security(CCS)[C],2000,11:190-199.
[6]K.WANG and S.J.STOLFO.Anomalous Payload-based Network Intrusion Detection.In Proceedings of the 7thInternational Symposium on Recent Advances in IntrusionDetection(RAID)[C].,2004,9:203-222.
[7]C.KRUGEL,T.TOTH,and E.KIRDA.Service Spe-cific Anomaly Detection for Network Intrusion Detection.In Proceedings of the ACM Symposium on Applied Com-puting(SAC)[C],2002.
[8]S.SIDIROGLOU,M.E.LOCASTO,S.W.BOYD,andA.D.Keromytis.Building a Reactive Immune System forSoftware Services.In Proceedings of the USENIX AnnualTechnical Conference[C],2005,(6):149-161.
[9]E.G.BAntes,D.H.Ackley,S.Forrest,T.S.Palmer,D.Stefanovic,andD.D.Zovi.Randomized Instruction SetEmulation to Distrupt Binary Code Injection Attacks.InProceedings of the 10th ACM Conference on Computer andCommu-nications Security(CCS)[C],2003,10.
[10]G.S.Kc,A.D.Keromytis,and V.Prevelakis.Coun-tering Code-Injection Attacks With Instruction-SetRandomization.In Proceedings of the 10th ACM Confer-ence on Computer and Communications Security(CCS)[C],2003,10.
自适应供电 篇4
自适应网关发现方法可以认为是混合式网关发现方法的一种特殊情况,其基本思想可归纳为:网关节点通过分析MANET节点的活跃程度和请求网关服务的频率来感知网络状况,通过设置GWADV报文的转发跳数来扩展或收缩主动式网关发现覆盖区域。除了网关通告跳数TTL,如何避免广播风暴、如何基于节点和网关的负载动态选择或切换路由,也是自适应技术的研究范围。
本文结合现有的自适应网关接入机制,进行了改进设计并实现仿真。在所有MANET节点上运行AODV路由协议,网关节点同时运行AODV协议和有线路由协议[3]。在这种方案中,网关的自适应性主要体现在以下几点。
(1)MANET节点的自适应:
一是动态接入:多网关情况下,节点根据网关负载GW(Gateway Weight)对收到的GWADV进行判定,选择其中负载最小的网关进行反向路由建立。
二是流量感知:节点根据邻居列表NNL(Neighbor Node List)及自身负载NW(Node Weight)对收到的RREQ有选择的进行转发,避免浪费链路资源,引起不必要的洪泛。
三是路径质量感知:源节点收到路由回复RREP,根据路径质量PW(Path Weight)选择默认网关路由和备用网关路由。
(2)网关节点的自适应
一是接入网关广播的网关通告半径(TTL)和网关通告的发送间隔随着网络规模以及接入节点到接入网关的距离变化而进行变化。
二是网关收到源节点发送的转发数据包,根据其到达间隔,监控路径质量,及时提醒源节点进行路由切换以减少网络延迟和丢包率。
1 数据结构
1.1 源节点列表
网关节点维护一份移动节点列表MNL(Mobile Nodes List)[4],该列表记录所有请求网关服务的源节点的序列号、IP地址、距离网关的跳数和活跃时间。MNL相关表项的建立与更新基于源节点发送的RREQ,网关节点接收后对其中相关字段进行解析以获取信息。其中,源节点的活跃时间设定于其相关信息初次写入MNL列表,若活跃期内表项信息更新则予以延长,若过期表项信息未更新则删除信息,因为此时该节点或者是不再需要网关接入服务,或者是脱离网关的当前服务范围。
通过MNL列表,网关节点了解需要提供服务的源节点数目及其位置分布,下文中如何设置发送GWADV的TTL值也基于此列表信息,从而实现GWADV的最佳覆盖。
1.2 邻居节点列表及双向链路的判定
无论是移动节点收到GWADV后获取至网关的多跳路径,还是源节点创建并发送RREQ自行寻求至网关的多条路径,这一系列路由发现过程都会因为采用泛洪方式进行报文转发而给网络造成巨大开销,导致大量的冗余分组、激烈的信道竞争以及报文冲突,出现所谓的广播风暴。为排除因单向链路而产生的无效广播分组,相邻节点定时通过HELLO分组探测局部拓扑情况,判定彼此是否为对称无线链路,并判断彼此是否拥有相同的对称邻居节点。
移动节点S维护一份邻居节点列表NNL(Neighbor Node List),该列表记录接收到的HELLO分组的发送者M,将其视作自己的邻居节点。NNL结构如图1所示。其中,邻居ID记录M的IP地址,对称链路记录S与M之间是否为双向链路。若S在M的HELLO分组[5]中看到自己在其邻居名单中,就判定M为对称邻居节点(简称邻居节点),设置对称链路字段,否则不设置。
当M被设置为邻居节点,S还要判断自己和M的对称邻居节点是否完全相同。S检索M的HEL-LO分组中包含的邻居信息,若发现与M的邻居节点并不完全重合,设置共有邻居字段。最后,NNL中的每条记录都设置了存活期限并在被更新后延长。存活期内未再次接收到M的HELLO分组,则删除NNL中有关M的记录,表明以M为下一跳的全部路由已经失效。
2 路由判据设计
2.1 网关节点负载的定义
网关根据MNL的表项信息定义网关负载GW(Gateway Weight)为:
其中,DS为移动节点至网关节点的跳数,NN为向网关节点请求服务的源节点数目,QL为网关节点缓冲区内待转发的数据包队列长度,且n+m+k=1。
显然,MANET结点会选择距离最近、转发任务最轻的网关作为其服务请求对象。考虑距离和负载对网络通信的影响不同,取n>m>k,即跳数的影响最大,其次为请求服务的节点数目,待转发的数据包大小被认为影响最小[6]。权值的选取根据网络环境的具体情况及网络性能的具体参数而确定。
2.2 移动节点负载和路径质量的定义
由于无线通信的特性,节点在传输数据之前要侦听无线信道,判断是否有其他节点正在传输数据。只有共享信道空闲时,节点才能启动数据传输。因此,邻居节点的通信量直接决定了节点进行数据传输时的空等时间,即自组织网络中端到端时延不仅取决于当前节点的负载,而且受制于邻居节点的负载。
定义节点负载NW(Node Weight)为一定的时间间隔内待发送数据包队列的平均长度。对节点S,在采样周期内共采集M个样本,则节点S的负载为:
其中,NW(k)是第k次采样时队列的实时长度,NW是采样周期内队列的平均长度。M越大,对节点负载的度量越准确。
定义路由质量PW(Path Weight)为路径中各节点的负载与节点数目之和:
其中,PN为路径上的节点数目,s<t且s+t=1,即跳数越少且各节点负载越小的路径越好。
3 适应路由策略
3.1 自适应网关通告
网关周期性向MANET广播网关通告来表明自己的存在。GWADV[8]消息包含:消息ID、网关全局地址、网络前缀、TTL、网关当前服务的源节点数量NN和网关节点待转发数据包队列长度QL等,其中NN和QL作为移动节点收到公告后计算GW的依据。同时,为避免非对称链路的影响,对GWADV进一步扩展,将局部拓扑信息即邻居节点信息添加到消息中,使MANET节点对GWADV进行有选择的转发。
(1)TTL的自适应选值
已知网关节点通过查询MNL便可了解源节点的分布情况,据此来动态修正网关通告的TTL,实现GWADV自适应广播。每个发送网关通告的周期,网关节点根据下式计算网关通告半径TTL:
其中,NN为向该网关节点请求服务的源节点数量;DS(i)表示i节点与网关节点的跳数。
(2)GWADV的发送间隔
在一个广播网关通告的周期内加入或离开该网关的源节点数目S可反映源节点的活跃程度[9]。引入阈值low<high,则广播间隔I的自适应公式为:
网关通告间隔的调整主要是基于网络拓扑的变化程度。当网络拓扑不稳定且源节点较活跃时,网关需要缩短广播间隔以及时更新源节点信息,反之则增加广播间隔以降低网络开销。
(3)基于时延给出路径转换信号
当路由建立,源节点向网关发送分组数据包,网关节点对来自同一个源节点的数据包进行计时,并计算各分组的传输间隔T:
第一个分组传输间隔为T1,下一个分组传输间隔为T2,取ΔT=T2-T1。设n=0,若ΔT>0,则n=n+1,否则n清零。当n=k时,即连续k个来自相同源节点的数据包传输间隔处于持续增大的状态,网关节点通过反向路由通知各中间节点和源节点,源节点在发送下一个分组时,选择备用网关路由发送数据。
3.2 自适应网关发现
将MANET节点分成三类:请求网关服务的源节点、已知网关路由并回复RREP的节点和转发RREQ的中间节点,分别叙述其自适应寻路过程。
(1)源节点
在网关通告GWADV的广播范围之外的源节点,通过发送网关路由请求分组RREQ来寻求网关服务。对RREQ格式进行扩展,增加邻居节点信息NNL和节点负载信息NW,以此排除单向链路的干扰并为路由质量PW的计算提供依据。RREQ格式如图2所示。
当源节点收到RREP消息,进行网关路由的建立。从RREP中获取各节点负载NW,按照式(3)计算该路径质量PW。若源节点收到来自不同网关的路由回复,则根据不同的PW,选择值最小的路由作为其默认网关路由,再选取值次小的作为备用网关路由。路由表结构如图3所示。
(2)中间节点(具有到网关的有效路由)
当中间节点收到一个GWADV消息,首先检查是否曾收到与该消息ID和IP地址相同的GWADV,若有则丢弃新收到的消息,否则查看消息中包含的邻居节点信息:
一是若邻居节点信息中包含本节点,则认为本节点和发送GWADV的上游节点之间存在双向链路,建立或更新相应的反向路由,并转发该消息。
二是若消息中邻节点信息中不包含本节点,则认为本节点和发送GWADV的上游节点之间为单向链路,丢弃该消息。
建立或更新到上游节点的反向路由进行以下操作:
一是若该节点没有至网关的路由,则创建该路由表项,根据GWADV中的NN和QL字段,按照式(1)计算网关负载GW,并将自己的邻居节点写入相应字段,然后将该通告进行转发。若该节点收到来自不同网关的GWADV,则根据计算出的GW,选择负载最小的路由作为默认网关路由,并转发该网关的GWADV,其他网关的通告丢弃。
二是若该节点已有至网关的默认路由,则按照式(1)计算网关负载GW,并判断是否进行网关切换。网关切换的条件是新网关的负载与当前网关的负载之差大于一定阈值,以此避免频繁的网关切换所带来的路由抖动。
至此该节点成为具有到网关节点有效路由的节点,收到RREQ后回复RREP,RREP与RREQ结构相同,源节点根据其中包含的节点负载信息选择性的建立全局连接。
三是中间节点(不具有到网关的有效路由)
当中间节点收到一个RREQ消息,若曾收到与该消息ID和源地址相同的RREQ,则直接丢弃,否则根据本节点MAC层及网络层提供信息,按照式(2)计算自己的节点负载NW,决定是否进行转发。节点有两种状态:繁忙和可用(繁忙:NW>U;可用:NW<U;U为拥塞指数),当节点处于繁忙状态时,丢弃所有收到的RREQ;当节点处于可用状态,在RREQ中的节点负载列表中添加自己的NW,搜索邻居节点列表,向双向链路的邻居节点广播RREQ。
4 仿真与分析
设置一个MANET网络场景,各节点运行改进后的路由协议,并按随机的移动速度保持运动状态。在仿真区域配置2个网关,位于仿真区域的对角,并在其上同时运行改进后的路由协议和有线路由协议。每个网关通过一个路由器与一个固定节点连接,均通过100Mbit/s的有线链路连接。具体参数设置如表1所示。
选取以下参数作为比较标准,将上文进行改进的路由协议与普通混合式路由协议进行比对分析:
(1)分组投递率:成功投送到目的节点的分组数据包在源节点发送的所有分组数据包中的所占比率。
(2)网络延时:从源节点发送分组数据包到目的节点接收分组数据包,该过程产生的所有时延,主要包含路由建立时间、数据包在缓冲区等待发送时间和正常的传播时间等。
(3)网络归一化开销:与寻路有关的分组消息(GWADV、RREQ和RREP等)在网络所有传输分组中的所占比率。
分组投递率和网络时延决定了网络接入性能,由图4(a)-图4(b)可知本文算法的性能较优,因为在非对称链路普遍存在的环境下,普通混合式路由算法盲目转发RREQ,导致一些因链路不对称而实际无效的路径被采用。失败后重新进行路由发现,因为建立路由的时间延长,相关数据可能因超时而被丢弃。另外,没有自适应机制使得网关通告范围不能根据MANET状态动态改变,默认网关路由的建立不能根据网关和移动节点的负载进行选择,因此分组投递率较低且网络时延较大,特别随着节点活跃程度增加,链路断裂趋于频繁,互联性能进一步恶化。
在网络开销方面,由图4(c)可知普通混合式路由算法开销巨大,因为其MANET节点盲目转发沿所有链路而来的网关发现消息,且当非对称链路造成路由发现失败,重新寻路造成了更多的开销。源节点位置随机且各节点高速移动,固定网关通告范围使得更多节点采取被动式按需寻路,RREQ等分组数量巨大。本文算法不仅避免了非对称链路的影响,而且引入基于节点负载判定是否转发分组的机制,在很大程度上节省开销。虽然周期性发送包含大量邻居节点信息的HELLO消息牺牲了部分互联开销,但本算法的开销仍然较少,尤其当节点移动速度增加时,其优势更加明显。
5 结束语
对MANET网络和固定网络互联的自适应网关发现算法进行优化。利用邻居节点信息在路由广播消息中的扩展解决单向链路问题;依据网关节点对MANET的感知实现网关通告广播范围和周期的自适应调整;通过采样并计算各节点的负载情况实现路由建立选择与更新的自适应。与已有算法的仿真对比显示,本文算法实现了互联性能的优化和路由开销的降低。
摘要：在移动自组网接入Internet的过程中,为适应节点高速移动导致网络拓扑频繁更新的特性,在混合式路由发现中引入自适应机制,从网关通告跳数的合理范围、广播风暴的避免、各节点和网关负载的动态变化等方面进行自适应性优化。以AODV路由协议为基础,改进网关发现算法的自适应机制,在NS2平台进行仿真,实现移动自组网与有线网络的互联,且其接入性能有一定程度优化。
关键词：移动自组网,Internet接入,网关发现,自适应
参考文献
[1]Cavalcanti D,Kumar A,Agrawal DP.Wireless Ad Hoc Networking[M].New York:Auerbach Publications,2007:483-503.
[2]Jeonkeun Lee,Dongkyun kim,J J Gareia-Luna-Aeeves et al.Hybrid gateway advertisement scheme for eonnecting mobile Ad Hoc networks to the Internet[J].IEEE,2012:191-195.
[3]刘元安,刘凯明,翟临博,等.移动自主网与Internet互联中的自适应网关发现算法[J].吉林大学学报,2011,41(4):1157-1163.
[4]沈斌,柯海燕,胡中功,等.MANET与Internet互联时的自适应增强机制[J].计算机工程与应用,2012,36(3):112-116.
[5]沈彬,李波,石冰心.基于HELLO机制的Adhoc与Internet高效互联[J].微电子学与计算机,2006(10):90-95.
短波电台自适应的实现 篇5
短波通信具有通信距离远、使用灵活机动、组网性能好的独特优点。
短波自适应通信网是覆盖范围广、技术先进、安全可靠、自动化程度高的中远距离无线电通信网。该系统对于提高通信能力和应急通信能力, 都具有十分重要的意义。短波系统采用了新型自适应控制器, 并开发了相应的主控软件, 配合508综合业务终端使用, 大大提高了自动化程度和综合性能。
二、短波自适应的工作原理
短波自适应电台可以通过链路质量分析 (LQA) 和自动链路建立 (ALE) 两种重要手段使通信在最佳信道上进行。
2.1链路质量分析 (LQA)
链路质量分析是一种实时信道质量估计技术。对信道LQA就是对信道参数进行测量和分析, 然后对信道的质量进行评分并将信道从最佳到最差排序。通信时可根据LQA矩阵中各信道的排列次序, 择优选取工作频率。
船与基站主要进行点对点通信, 两个电台之间进行双向的LQA的基本过程如下:
第一步, 探测呼叫。主叫台通过某一信道向目标台发出探测信号 (包括主叫台和目标台识别地址的编码信号) 。目标台识别后, 接受并测量其信号质量, 进行评分, 并记录下来。
第二步, 应答。目标台在同一信道上向主叫台发出应答信号, 其中包含来自主叫台探测信号的质量评分信息。主叫台接受并记录该信息, 同时对来自目标台的应答信号的质量进行测量、评分和纪录。这样, 主叫台就掌握了通过该信道双向传输信号的质量评分, 从而得到该信道的质量总评分。
第三步, 确认。主叫台再次通过该信道向目标台发出信号, 其中包含对该信道的质量总评分信息, 从而保证主叫台和目标台关于该信道的质量评分记录完全一致。至此, 对一个信道的双向LQA过程结束。双方又开始对另一个信道按上述“探测呼叫——应答——确认”这三个步骤进行双向LQA。
对所有信道逐个进行双向LQA, 就可得到每个信道的质量评分, 然后双方均按评分的高低顺序, 将所有的信道排序, 并存入存储器中。
2.2自动链路建立 (ALE)
在工作过程中, 主呼台的自适应控制器根据LQA的结果, 在LQA表中选出最佳信道进行呼叫。一旦双方信道沟通, 两个电台均会发出“建链成功”声音, 通知操作员可以进行通信。若是在所有信道上均无法沟通信道, 主呼台将显示相应的提示信息。
被呼自适应电台处于扫描状态, 接收机则对已编程入本台地址的全部信道和本台所属网络地址的信道集合进行循环扫描。当在某个信道上接收到呼叫信号时, 工控便自动停止扫描, 并在该信道上向主呼台发射响应信息, 当再次收到主呼台的“认可”信息后, 就完成了自动链路建立。
三、基于自适应的短波监控系统
传统的单一手键报通信是以手键为终端, 由经过专业训练的报务员敲击手键发报完成报文通信, 属于人工终端, 存在着很多弊端。自适应技术实现了信道建立和沟通联络的自动化, 而要实现短波真正的自动化, 508终端的自动化也是必不可少的。
自适应短波通信系统既可以用于点对点通信, 也可以用于多点之间组网通信, 收发信机主要用于发送和接受数据, 工作种类有上边带、下边带、调幅话、等幅报。
自适应控制器是此系统所以实现自适应通信的核心装置, 它能不断的进行信道扫描, 从中选择最佳信道进行建链, 确保通信成功。在原系统的基础上, 设备增加了终端控制设备508终端, 从而结束了以往单一手键报操作的历史, 它可在短波信道上完成数据传输、传真、声码语音通信等多种业务。
通过计算机监控台和508终端得以利用软件实现对硬件的灵活控制, 该监控软件分为应用程序软件和控制软件两部分, 应用程序软件提供终端的用户界面, 完成各种用户功能, 实现对硬件设备的管理和设置。
屏幕画面简洁, 明确醒目, 操作起来很方便, 操作人员无需专门训练也能很快上手。
四、不足之处和应对措施
自适应电台有时链路建立时间太长, 为了发报, 常常需要等上很长的时间。链路建立时间跟LQA的评估速度和信道数有关。我们所能做的就是尽可能的减少信道数目优化选择频率。
五、结束语
短波通信系统自适应监控的实现, 大大提高了短波通信系统的自动化程度, 实际应用过程中, 灵活的使用频率, 将更有力保障短波通信任务的完成。
摘要：本文总结了短波自适应通信的实现过程, 并就在实际应用中发现的问题提出了应对措施。
关键词：短波通信,自适应短波电台,508短波综合业务终端,LQA,ALE
参考文献
[1]短波系统改造”技术任务书.2006年1月
无线内容自适应技术研究 篇6
关键词：content adaptation,自适应,网络感知,多媒体
0 引言
互联网的迅速发展使网络中传播的内容资源更为丰富, 同时也使用户对网络的需求日益增加, 尤其是对图像、音频、流媒体视频等多媒体内容的需求不断提高。由于多媒体内容的访问往往占用较大带宽, 加之用户访问量的不断增大, Web服务器的负荷也在日益加重, 网络吞吐量下降。在无线网络环境中, 由于带宽的限制、空气介质带来的冲突以及多媒体内容访问量的增加而产生的网络整体性能下降更为明显, 对用户体验度的影响程度也更为严重。形形色色的无线终端设备, 如:智能手机、掌上电脑、PDA使无线乃至移动环境下访问互联网变得更为便捷, 但同时也形成了接入网带宽不同, 终端设备能力差异的无线异构网络, 这也使得不同的终端用户享受到同样高水平的网络服务质量变得十分困难。
为了在无线异构网络环境中提高内容的可读性同时改善用户体验度, 有研究者提出了内容自适应策略。这是一种动态调整被访问内容以满足终端用户接入网络带宽, 用户偏好和终端设备能力限制的机制[1]。图1描述了内容自适应实现的基本流程。在无线异构网络环境中, 内容自适应技术考虑到终端设备能力的局限性 (比如屏幕大小及分辨率、支持图像格式、应用程序种类等因素) , 在发送内容前对内容的格式或大小进行调整, 从而发送更适合终端设备读取的内容。同时该策略也可以根据用户接入网络的特征和当前的网速, 对内容进行适当的降质, 降低质量后的内容保持原有内容的核心, 但容量大大减小, 从而减轻了对网络传输的负担。内容自适应研究的相关技术包括[2]:
(1) 用以支持内容自适应的多媒体处理和分析算法。
(2) 能够可靠探测用户设备软硬件能力的机制。
(3) 定义用户偏好的标准方法及对其在会话间跟踪的机制。
(4) 有效测量当前用户与服务器之间网络连接特征的方式。
(5) 判断在各种条件下何时以及如何执行内容自适应算法的策略。
1 内容自适应策略
无论在有线或无线网络环境中, 采取一种适当有效的自适应算法是完成整套内容自适应过程的关键。内容自适应策略的核心思想是在保留内容关键信息的同时根据用户所处的网络环境、软硬件环境与特点需求对内容进行一定程度的处理和转化。对内容进行处理的技术有很多, 一些现有的多媒体处理技术可以被用于实现更智能的信息发送。Hewlett-Packard实验室的研究人员定义了一套异构网络中自适应内容分发的框架, 其中将一些主要的内容自适应策略按其应用归为五大类[2], 表1按多媒体内容包含的四种种类 (视屏、图像、音频、文字) 对这五类技术所采用的自适应方法进行了概括。它们包括:
信息提取 (Information abstraction)
模式转换 (Modality transformation)
数据转换编码 (Data transcoding)
数据优先 (Data prioritization)
目的分类 (Purpose classification)
2 用户信息获取策略
用户信息主要包括三方面的内容:用户设备能力, 网络特征和用户偏好。获得用户信息是实现内容自适应的第一步, 也是自适应算法的依据。现有的一些技术可以被用于收集与测量用户信息。例如:分析用户发送的请求 (如HTTP请求的头文件) 可以获得用户设备方面的信息, 如浏览器类型、设备屏幕尺寸等信息, 也可间接估计该设备的最大可用带宽等信息。又比如:提供界面给用户提交用户的偏好, 设备的能力, 以及所使用网络连接的属性等等。其他获取用户信息的技术还包括会话跟踪, 系统及网络负载自动测量, 浏览器行为分析等等。
2.1 网络监控
为了对网络环境的变化实时捕捉, 应用程序必须找到一种方法对网络进行监控。通常来说, 网络监控指的是收集网络状态的原始数据如带宽、时延, 但一些系统还有能力将原始数据进行统计转换并根据应用软件的语法格式显示结果[3]。
最常见的网络监控方法的分类是基于该方法所产生的流量[3,4]。若采用主动监控的方法, 网络测量数据是通过发送附加的测试信息而获得的, 因此这将不可避免地给网络带来额外的流量。反之, 若采用被动监控技术, 系统仅以程序产生的流量作为依据, 并通过与网络其他节点的通信获得数据。网络状态的信息完全由穿梭于网络中的数据分组所表征, 因此不会引入额外的网络流量。
2.1.1 主动监控
主动监控可以通过在单一主机上运行简单的探测服务实现, 也可以利用探针分布于网络各处的复杂监控系统。前种方式的例子有standard ping[5]和bprobes[6]。后种方式的例子有NIMI[7], topology-d[8], 以及基于代理的系统[9]。由于引入了额外流量, 主动监控在监控过程中有更好的主动性和控制权。它可以简便地测量两台主机之间整条网络路径的特征, 比如分组往返一次的时间 (Round Trip Time) , 平均丢包率 (Packet loss) , 以及可用带宽。但是这种监控方式比较难获得网络中具体某一点的信息。
对于资源有限的网络如无线网络来说, 额外的流量始终是一个问题。除此之外, 主动监控的另一个问题是, 由测试数据包获得的结果往往不符合实际用户数据包的产生的结果 。因此, 监控结果可能无法完全代表实际使用情况。然而, 通过使用测试包来模拟实际用户数据包, 主动监控可以测量到网络任何一处的质量, 甚至那些没有流量的链路, 这适用于连接初始化和服务器的选择。
2.1.2 被动监控
被动监控是目前网络感知的应用中常见的监控方式。与主动监控相比, 被动监控可以对网络中特定一点进行精确的评估, 如准确的比特率或分组速率等。被动监控较主动监控更准确, 因为它测量的是实际用户数据。但是, 为了能获得更可靠的测量数据, 快速的处理是至关重要的, 而被动监控很容易导致信息过时 , 这是由于信息只有在主机连接远程站点时才会被收集。
被动监控的例子有SNMP (Simple Network Management Protocol) , 一些特殊的硬件软件系统如Nprobe[10]和SPAND[11]等。
2.1.3 混合监控
根据上述讨论, 很明显主动监控和被动监控各有优缺点, 双方互补而并不互斥。因此, 一种混合监控策略可以结合两者优势而成为一种更好地解决办法。文献[12]中介绍了一种混合监控系统:EXPAND。这种监控方式只在被动监控信息不可用的情况下采取主动探测, 例如当前网络无连接的情况下主机想了解网络状况以建立一条新的连接。基于该模型的实验表明, 混合模式可以减少主动探测所引入的额外流量, 同时获得准确的信息。
3 构架设计
内容自适应策略的构架问题讨论的是自适应决策和算法在何处进行。常见的位置有服务器、代理 (Proxy) 、用户端以及综合型。每一种设计都有其优缺点, 这里比较关心的问题是:系统实现的难易程度, 网络带宽、CPU和内存的利用效率, 内容自适应的有效性以及内容转换的相关版权问题等[2]。
3.1 基于服务器的自适应构架
基于服务器实现内容自适应的构架中, 服务器负责探测用户设备能力和网络状况, 随后根据预先设计算法提供最优的自适应策略。该构架的优点在于它可以进行静态 (off-line) 和动态 (on-the-fly) 的内容自适应。前者指的是在任何时刻为原作内容自动创建多个版本;后者指的是当请求发生时对内容进行实时的自适应处理。因此, 基于服务器的设计对内容有更好的著作控制, 内容的作者也可以参与决定在不同环境中内容的转换方式。在安全性较高的网络环境中 (如电子商务) , 网页往往被加密, 因此自适应也只能由服务器来完成。
这种构架也有其不足之处。由于传输带宽的限制, 用户通常需要从地理上较近的服务器上获取内容以减少跳数缩短内容下载时间。而在基于服务器的内容自适应系统中, 这意味着执行自适应算法的服务器必须分布在网络各处, 服务器设计也必须考虑到数据同步问题, 对引入的额外资源消耗进行负载均衡。静态自适应方式创建的多个版本的内容也将同时存在于各台服务器中, 从而耗费大量存储资源。
3.2 基于代理的自适应构架
基于代理的构架中, 用户通过代理向提供内容的服务器发出请求, 代理截获服务器发送的内容从而决定和执行自适应策略, 转换后的内容随后发送至用户。一般假设代理与服务器之间的带宽远大于代理到用户的带宽, 因此内容从服务器到代理的下载时间是可以忽略不计的。这种构架中自适应发生的位置更靠近用户, 避免内容版本的过多复制。并且服务器和用户端都无需作任何改变, 同一台代理可以为多台服务器执行内容自适应处理, 从而有利于大规模应用。
然而, 由于代理从众多服务器中获得内容, 内容的格式差异显著, 因此, 基于代理的自适应方式对内容的转换结果缺乏著作控制, 结果没有统一的格式和评价优劣的标准。版权问题同样也是这种设计的缺点之一。
4 无线自适应内容分发
随着无线网络技术的发展, 越来越多的无线终端设备如PDA, Pocket PC, 智能手机随之出现, 移动用户的数量也在日益攀升。考虑到这样一个异构和多变的网络环境, 加上多媒体应用对网络资源的依赖, 让移动多媒体应用实现网络感知 (Network aware) 变得非常关键。下文将主要以移动环境为例, 讨论移动多媒体传输带来的问题, 以及针对这些问题对网络提出的特殊要求如何采取一种能够对网络感知的内容自适应策略。
4.1 移动多媒体应用的局限性
在无线领域, 许多应用程序如电子邮件已经能够成功地在移动无线网络中运行, 但是要将多媒体应用程序完整的移植到无线环境中来还具有相当大的挑战, 这些程序往往需要处理各种格式的内容, 包括文字、图像、动画、声音、视频等等[3]。尤其对于音频和视频内容来说, 它们对网络带宽有更高的要求。例如, 在速度低于30kbps的第二代移动蜂窝网络 (如:GSM) 中, 视频的传送非常困难;而在802.11a的WLAN (带宽6Mbps～54Mbps) 或3G移动网络UMTS (带宽最高可达2Mbps) 中传送视频才更具有实际意义[3]。除了带宽资源受限, 无线性与移动性的特性都给网络质量带来挑战。这些挑战包括带宽变化不定、误码率起伏不定、可能的不对称连接、切换过程中不被预料的质量下降等等。表2对移动网络多媒体应用可能带来的问题作了归纳, 其中按问题产生的主要因素 (无线性、移动性和多媒体) 将问题分为三大类[3]。
4.2 网络感知的移动多媒体传输
考虑到移动多媒体传输的种种局限性, 网络感知的内容传输技术被视为是解决该问题的一种解决方案。所谓网络感知就必须通过某种方法探测终端用户的网络特征参数, 这些参数可以是带宽、时延界限、安全性等方面的信息。在这些参数中, 网络带宽可以说是最为重要的网络性能指标。为了测量终端网络的性能参数, 前文已经介绍了几种网络监控的方法 (主动、被动、混合) , 采取一种适合于移动网络特征的监控方式将更有利于网络数据的实时、准确的探测。基于移动网络环境变化莫测的事实, 需要一种能够使移动多媒体应用程序快速地探测网络变化的监控方法。主动监控会给有限的网络资源带来额外的流量负担, 获得结果需很大是延迟, 因此不常被用于灵活多变的网络。另一方面, 被动监控对测量某些种类的参数有局限性, 如:错误概率、丢包率, 同时也无法测量关闭或断开的连接上的数据, 而这些情况在无线网络中是很常见的[12]。尽管目前常见的网络感知应用模型大多基于被动监控, 我们依然相信一种集主动和被动优点的混合监控方式将是移动多媒体应用网络的最佳监控方案。
除了选择合适的监控策略, 网络构架也是重要的考虑因素。基于用户终端设备的构架方案简便易实现, 但其并没有起到减轻网络负载的作用, 内容仍然以完整的形式被传输到用户手中, 再根据设备的能力作相应的处理。并且自适应依靠的是用户端应用软件自身的能力, 对于一些计算和存储能力有限的移动设备而言, 这也将耗费很大资源。因此基于服务器或者代理的构架更适合于无线移动环境内容自适应分发。前文以对两者的优劣进行了比较分析, 基于代理的方式使自适应发生在离用户较近的地方, 优化了网络资源最薄弱的用户接入网环节上内容的传输, 部署也相对容易, 因此比基于服务器的构架更显优势。但是根据具体的无线网络情况以及对内容版权问题的考虑, 基于代理的方式也不是唯一的选择, 有些情况下, 采用混合的构架方式更具实际意义。
5 结束语
本文在介绍了内容自适应基本概念的基础上, 对其核心技术作了逐一分析, 主要包括自适应策略、网络监控测控、构架等等。其次本文对内容自适应技术应用于无线领域中的可能性作出分析, 并对移动环境多媒体应用存在的诸多局限性进行了阐述, 并讨论了自适应技术在此类环境中应用的方法。选择一种合适的混合监控策略与适应网络特性的自适应构架方式, 无线网络的传输性能将得到提升。
参考文献
[1]Stephen J.H.Yang, Norman W.Y.Shao, Risk C.S.Chen.A multi-media content adaptation mechanism to implement universal access onlearning environment[J].IEEE Communications Magazine, 2003.
[2]Wei-Ying Ma, Ilja Bedner, Grace Chang, et al.A framework for adap-tive content delivery in heterogeneous network environments[J].Hewlett-Packard Laboratories, 2005.
[3]Jinwei Cao, Dongsong Zhang, Kevin M.McNeill, et al.An Overview ofNetwork-Aware Applications for Mobile Multimedia Delivery[C].pro-ceedings of the 37th Hawaii International conference on System Scienc-es, 2004.
[4] Caripe W, Cybenko G, Moizumi K, et al.Network awareness and mobile agent systems[J].IEEE Communications Magazine, 1998, 36:44-49.
[5] Toshiya M, Kazuo N, Shouji M, et al.QOS MONITORING SYSTEM[R].Yokogawa, Technical Report No.34, 2002.
[6]Carter R L, Crovella M E.Measuring bottleneck-link speed in packetswitched networks[R].Computer Science Department, Boston Universi-ty, Technical Report BU-CS-96-006, March 1996.
[7] Paxson V, Adams A, Mathis M.Experiences with NIMI[C]. presented at Proceedings of the Passive & Active Measurement Workshop, 2000.
[8] Obraczka K, Gheorghiu G.The performance of a service for network-aware applications[C].presented at Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, Welches, Oregon, United States, 1998.
[9]Wijata Y I, Niehaus D, Frost V S.A scalable agent-based network mea-surement infrastructure[J].IEEE Communications Magazine, 2000, 38:174-183.
[10]Moore A, Hall J, Harris E, et al.Architecture of a Network Monitor[J].presented at Proceedings of the Fourth Passive and Active Mea-surement Workshop (PAM 2003) , 2003.
[11]Seshan S, Stemm M, Katz R H.SPAND:shared Passive Network Per-formance Discovery[C].presented at 1st Usenix Symposium on InternetTechnologies and Systems (USITS’97) , Monterey, CA, 1997.
动态自适应微粒群优化算法 篇7
关键词：粒子群优化算法,惯性权重系数,动态自适应
1 引言
粒子群优化算法(Particle Swarm Optimization,PSO)是由James Kennedy博士和R. C. Eberhar博士于1995年提出的。该算法源于对鸟群、鱼群觅食行为的模拟。该算法具有易于描述、便于实现、需要调整的参数很少、使用规模相对较小的群体、收敛需要评估函数的次数少、收敛速度快、并行处理、鲁棒性好等特点,能以较大的概率找到问题的全局最优解且计算效率比传统随机方法高,有深刻的智能背景,既适合科学研究,又适合工程应用。因此, PSO一经提出立刻引起了演化计算领域研究者的广泛关注,并在短短几年时间里涌现出大量的研究成果,在函数优化、神经网络训练[1]、函数优化问题[2]、模糊系统控制、分类、模式识别、信号处理、机器人技术等领域获得了成功应用。
2 粒子群优化算法描述
2.1 算法原理
PSO先生成初始种群,即在可行解空间中随机初始化一群粒子,每个粒子都为优化问题的一个可行解,目标函数为之确定一个适应值(fitness value) 。PSO不像其他进化算法那样对于个体使用进化算子,而是将每个个体看作是在n维搜索空间中的一个没有体积和重量的粒子,每个粒子将在解空间中运动,一个速度决定其方向和距离。通常粒子将追随当前的最优粒子而动,经逐代搜索最后得到最优解。在每一代中,粒子将跟踪两个极值,一为粒子本身迄今找到的最优解pbest,另一为全种群迄今找到的最优解gbest。假设在D维搜索空间中,有m个粒子组成一群体,第i个粒子在D维空间中的位置表示为Xi=(xi1,xi2,Lxid),第i个粒子经历过的最好位置记为Pi=(pi1,pi2,…pid,), 每个粒子的飞行速度为Vi=(vi1,vi2,…vid),i=1,2,…m。在整个群体中,所有粒子经历过的最好位置为Pg=(pi1,pi2,…pid),每一代粒子根据下面的公式更新自己的速度和位置:
Vi=wvid+c1r1(pid-xid)+c2r2(pgb-xid) (1)
Xi=Xi+Vi (2)
其中,w为惯性权重;c1和c2为学习因子;r1和r2是[0,1]之间的随机数。公式由三部分组成,第一部分是粒子先前的速度,说明了粒子目前的状态;第二部分是认知部分,是从当前点指向此粒子自身最好点的一个矢量,表示粒子的动作来源于自身经验的部分;第三部分为社会部分,是一个从当前点指向种群最好点的一个矢量,反映了粒子间的协同合作和知识的共享。三个部分共同决定了粒子的空间搜索能力。第一部分起到了平衡全局和局部搜索的能力。第二部分使粒子有了足够强的全局搜索能力,避免局部极小。第三部分体现了粒子间的信息共享。在这三部分的共同作用下粒子才能有效的到达最好位置。更新过程中,粒子每一维的位置、速度都被限制在允许范围之内。如果当前对粒子的加速导致它在某维的速度Vi超过该维的最大速度Vdmax,则该维的速度被限制为该维最大速度上限Vdmax。一般来说,Vdmax的选择不应超过粒子的宽度范围,如果Vdmax太大,粒子可能飞过最优解的位置;如果太小,可能降低粒子的全局搜索能力。
3 粒子群优化算法的改进策略
分析基本粒子群优化算法,其搜索过程有两个不足:1)初始化过程是随机的,随机过程虽然大多可以保证初始解群分布均匀,但对个体的质量不能保证,解群中有一部分远离最优解。如果初始解群较好,将会有助于求解效率与解的质量。由于粒子初始化和进化过程的随机性,使pbest和gbest的更新带有一定的盲目性,影响了进化过程的收敛。2)利用式(1)和(2)更新自己的速度和位置,本质是利用本身信息、个体极值信息和全局极值三个信息,来指导粒子下一步迭代位置。这实际上是一个正反馈过程,当本身信息和个体极值信息占优势时,该算法容易陷入局部最优解,分析式(1)和(2)进一步可以发现,当某些粒子的位置及其pbest接近群体的gbest时,其速度更新由wvid决定。w<1时,粒子的运行速度越来越小,接近于零,粒子运行出现“惰性”。随着进化的进行,其他粒子将很快聚集到这些惰性粒子的周围,使进化过早地收敛到局部最优点。总之,微粒群算法存在两个缺点:其一是粒子群优化算法的收敛速度比较慢。其二是粒子群优化算法容易陷入到局部极值点中,导致得不到全局最优解。
为改善粒子群优化算法的不足,改进策略可谓层出不穷,这方面的研究非常庞杂,这些改进基于各种不同的策略和方法。但从根本目的来说,都是为了改进粒子群优化算法的以上两个缺点。对于第一种缺点,在解决实际问题时,通常需要在一定的时间内达到相应的精度,如果耗费很长的计算时间来得到一个可行解,有时是不值得的。造成这种问题的原因是粒子群优化算法并没有很充分的利用计算过程中得到的信息,在每一步迭代中,仅仅利用了全局最优和个体最优的信息,此外,算法本身没有比较充分的优选机制,以淘汰比较差的待选解,从而导致算法收敛速度较慢。要解决这方面的问题,需要充分的吸收进化算法的优点,在粒子的操作中,加入繁殖、变异和优选算子[3],以加快算法的收敛速度。另外一个思路就是把粒子群优化算法较强的全局搜索能力与基于梯度算法的较好局部搜索能力相结合,设计一种混合算法,以克服二者的缺点,发挥二者的优点。造成第二种现象的原因有两方面,一是待优化函数的性质,有许多测试函数是多峰函数、形状复杂,而粒子群优化算法并不是从理论上严格证明收敛于任何类型函数的全局极值点,因此对于复杂的测试函数,很可能难以得到满意的结果。二是粒子群优化算法在运行时,由于算法的参数设计或者是粒子数的选择不恰当等原因,导致在计算的过程中,粒子的多样性迅速的消失,造成算法“早熟”现象,从而导致算法不能收敛到全局极值点。这两个因素通常密不可分的纠缠在一起,很难说在一个具体的问题中,到底是那一个因素在起作用,使得算法不能收敛到全局极值点。有比较多的改进是基于这两个方面的因素,对于第一个方面的缺点,有些研究者试图在函数优化的过程中,动态的改变函数的某些全局或局部的形态,使得函数的形状逐渐的变得简单,但同时又不改变函数的全局极值点的性质。比如可以设计一个变换,随着优化过程的进行,使得函数最终由多峰函数变为单峰函数,从而克服此问题。第二个方面的问题通常可以采用如下方法解决:对粒子群的多样性设置某些指标,比如粒子群的炳,随着计算的进行,实时监测这些指标,这些指标超过某个事先设定的临界值,则对整个群体实施某种操作比如按指定的概率重新初始化,从而改善群体的多样性,克服早熟的问题。
基于上面的理论分析,本节重点讨论以下几个方面PSO算法的改进策略及其效果:调整惯性权重,采用不同的惯性权重调整策略,兼顾全局与局部的寻优能力;引入收缩因子,加快算法的收敛速度,提高算法的性能。
3.1 引入收缩因子
引入收缩因子的粒子群优化算法,其速度更新如下式所描述:
Vid=∅[vid+c1v1(pid-xid)+c2r2(jpgd-xid)]
其中,收缩因子
undefined
实验结果表明,与使用惯性权重的粒子群优化算法相比,使用收缩因子的粒子群优化算法有更快的收敛速度。其实只要恰当地选取因子,带收缩因子的粒子群优化算法可被看作是PSO算法的一个特例。
3.2 调整惯性权重
PSO算法存在易陷入局部最优,出现早熟收敛的问题,许多研究都集中于参数惯性权重w的改进上,w对算法能否收敛具有重要作用,它使粒子保持运动惯性,使其有扩展搜索空间的趋势,改变其取值可以调整算法全局和局部搜索能力的平衡。
在PSO中,搜索陷入局部极值往往表现为微粒几乎停止不动。当群体的最优适应值长时间未发生变化(停滞)时,应根据群体早熟收敛程度自适应地调整惯性权重。若对整个群体采用同样的自适应操作,则一方面全局寻优和局部寻优是矛盾的,不能够同时进行;另一方面,当群体已收敛到全局最优附近时,优秀粒子被破坏的概率会随着其惯性权重的增加而增加,这使PSO算法的性能有所下降。为了充分发挥自适应操作的效能,本文的自适应调整策略,不仅用到群体早熟收敛信息,还根据个体适应值的不同将群体分为三个子群,分别采用不同的自适应操作,使得群体始终保持惯性权重的多样性。惯性权重较小的粒子用来进行局部寻优,加速算法收敛;惯性权重较大的粒子早期用来进行全局寻优,后期用来跳出局部最优,避免早熟收敛。这样,具有不同惯性权重的粒子各尽其责,全局寻优和局部寻优同时进行,在保证算法能全局收敛和收敛速度之间做了一个很好的折衷。
适应值为fi的粒子,其惯性权重w的具体调整方法如下:
3.2.1 fi优于f′arg
满足此条件的粒子是群体中较优的粒子,已经比较接近全局最优,所以应被赋予较小的惯性权重,以加速向全局最优收敛。本文根据粒子适应值按式(3)调整粒子w的惯性权重:
undefined
其中wmin为w的最小值,本文取wmin=0.5。粒子适应值越佳,其惯性权重相应越小,加强了局部寻优。
3.2.2 fi优于farg,但次于f′arg
满足此条件的粒子是群体中一般的粒子,具有良好的全局寻优能力和局部寻优能力。如果惯性权值ω随着搜索的进行按余弦规律减小,开始搜索时ω能较长时间保持较大值以提高搜索效率,在搜索后期ω能较长时间保持较小值以提高搜索精度,本文ω的修正公式为:
undefined
其中: ωmax为搜索开始时最大的ω,ωmin为搜索结束时最小的ω,iter为迭代所进行的步数,MaxStep为允许最大迭代步数。
3.2.3 fi次于farg
满足此条件的粒子是群体中较差的粒子,对其惯性权重的调整引用文献[4]中调整控制参数的方法:
undefined
算法停滞时,若粒子分布较为分散,则△较大,由式(5)降低粒子的w,加强局部寻优,以使群体趋于收敛;若粒子分布较为聚集,如算法陷入局部最优,则△较小,由式(5)增加粒子的w,使粒子具有较强的探查能力,从而有效地跳出局部最优。式(5)中参数k1和k2的选择对算法的性能有较大的影响。k1主要用来控制w的上限,k1越大,w的上限越大。根据前面分析,k1的选取应使式(5)能够提供大于1的惯性权重。本文取k1=1.5,显然w∈(0.5,1.1)。k2主要用来控制式(5)的调节能力,若k2过大,在早期停滞时,w会迅速变得很小,这虽然会加快收敛,却使算法在早期全局寻优能力不足,若k2过小,则式(5)的调节能力不是很明显,尤其是在后期算法不能有效地跳出局部最优。
此外,当算法未搜索到全局最优适应值时,或不满足最优要求时,可采用惯性权重的变异策略。对种群当前的最优粒子的惯性权重按下式进行变异:
w=w(1+ησ) (6)
其中,σ为满足高斯分布的随机数。如此,即可以较大的概率产生小幅度的扰动以实现局部搜索,又可适当产生大幅度扰动以实现大步长迁移来走出局部极小区域。η初值为1.0,每隔一定的迭代代数置η=βη,其中β为[0.01,0.9]之间的随机数。
3.3 算法流程
动态自适应粒子群优化算法DAPSO是在基本粒子群优化算法的基础上,根据群体早熟收敛程度和个体适应值来调整惯性权重的一种改进粒子群优化算法。Logistic方程是一个典型的随机动态系统:
zn+1=μzn(1+zn)n=0,1,2,… (7)
式中μ为控制参量,取μ=4,设0≤z0≤1,系统(7)完全处于随机运动状态。由任意初值z0∈[0,1],可迭代出一个确定的时间序列z1,z2,z3,…。本算法采用次方程对最优位置进行动态优化。算法具体流程如下:
Step 1:初始化设置最大允许迭代次数或适应度误差限,以及相关参数。
Step 2:动态初始化粒子位置和速度。
1)随机产生一个n维每个分量数值在0-1之间的向量,z1=(z11,z12,z12,…z1n),n为目标函数中的变量个数,根据式(7),得到N个向量z1,z2,z3,…zn。
2)将zi的各个分量载波到对应变量的取值区间。
3)计算粒子群的适应值,并从N个初始群体中选择性能较好的M个解作为初始解,随机产生M个初始速度。
Step 3:如果粒子适应度优于个体极值pbest,pbest设置为新位置。
Step 4:如果粒子适应度优于全局极值gbest,gbest设置为新位置。
Step 5:根据公式(1), (2)更新粒子的速度和位置。
Step6:对最优位置Pg=(Pg1,Pg2,…PgD)进行动态优化。将Pgi(i=1,2,…D)映射到方程(3.5)的定义域[0,1],zi=(pgi-ai)/(bi-ai),(i=1,2,…D),然后,用Logistic方程进行迭代产生随机运动变量序列zi(m)(m=1,2,…),再把产生的变量序列通过逆映射pgi(m)=ai+(bi-ai)zi(m)返回到原解空间,得:
Pg(m)=(Pg1(m),Pg2(m),…PgD(m))=(m=1,2,…)
在原解空间中对随机动态变量经历的每一个可行解Pg(m)(m=1,2,…)计算其适应值,得到性能最好的可行解P*。
Step7:用P*取代当前群体中任意一个粒子的位置。
Step8:判断算法的终止条件是否满足,若满足转向Step 10,否则执行Step 9;
Step 9:根据粒子适应值不同采取相应的自适应策略,分别按照公式(3),(4),(5),(6)调整惯性权重w,转向Step 3;
Step 10:若满足停止条件,则搜索停止,输出全局最优位置。
3.4 算法效果分析
为了检测动态自适应粒子群优化算法的效果,采用四个典型的测试函数进行实验,这些函数是:f1(Rastrigrin Function)、f2(Rosenbrock Function)、f3(Griewank Function)、f4(Ackley Function),函数的具体表示形式如下:
(1) 函数f1(Rastrigrin Function)
f(x)=undefined[xi2-10cos(2πxi+10)],|xi|≤5.12
minf(x*)=f(0,0,L 0)=0
Rastrigrin函数为多峰函数,当xi=0时达到全局极小点,在s={xi∈[-5.12,5.12],i=1,2,…n}范围内大约有10n个局部极小点。
(2) f2(Rosenbrock Function)
f(x)=undefined(100(xi+1-xi2)2+(xi-1)2),|xi|≤50
minf(x*)=f(1,1,… 1)=0
Rosenbrock函数由K.A.DeJONG提出,此函数是非凸的病态二次函数,其极小点易于找到,但要收敛到全局极小点则十分困难。
(3)函数f3(Griewank Function)
undefinedundefined
undefined
Griewank函数,当xi=0时达到全局极小点,当undefined时,达到局部极小点。
(4)函数f4(Ackley Function)
undefinedundefinedundefinedundefinedcos(2πxi))+20+e,|xi|≤32
minf(x*)=f(0,0,… 0)=OAckley函数,当xi=0时达到全局极小点。动态自适应算法的实验结果:
从上述结果可以发现,动态自适应微粒群算法基本保持了基本PSO算法的简单、容易实现的特点,而且计算精度比基本PSO算法精度要高,改善了粒子群优化算法摆脱局部极值点的能力,提高了算法的收敛速度,且兼顾全局寻优和局部寻优,能够有效地避免早熟收敛。
4 结论与展望
本论文在分析基本微粒群算法的基础上,评析了微粒群算法的优缺点,并对惯性权重进行了调整,改进了微粒群算法的性能。PSO的研究领域在不断持续发展,仍然存在大量有待研究的问题。如:选择具有最大改善的粒子作为社会影响源,对这种粒子可进行动态变异自适应;没有速度的PSO算法,没有速度的粒子群将改变我们以往对群体的观点;并行PSO算法,开发高效的并行算法,充分利用PSO算法的隐并行性。以上列出的仅仅是PSO算法研究中一部分具有挑战性的问题,实际的研究不仅于此。考虑如何建立智能优化算法的统一框架,加强算法的理论基础研究,以及将算法扩展应用到不同的实际领域,都是有价值的努力方向。
参考文献
[1] 刘宇,覃征,卢江.多模态粒子群集成神经网络.计算机研究与发展,2005(9):1519-1526.
[2] 王俊伟,.粒子群优化算法的改进及应用.东北大学博士论文,沈阳市,2006.
[3] 孟庆红,多目标进化算法及其应用研究.西安电子科技大学博士论文,西安市,2005.