算法性能

算法性能（精选十篇）

算法性能 篇1

网络路由是指路由器从一个接口上收到数据包,根据数据包的目的地址进行定向并转发到另一个接口的过程[1]。目前,随着网络的覆盖面越来越广和负载的数据越来越复杂,早期的简单数据包传输已经无法满足用户对网络质量的高要求,如何更快速、有效地提高数据包转发性能成为网络路由中的一个亟待解决的难题。近几十年来,学术界和工业界始终将如何提高网络路由性能作为研究重点[2],尤其是网络路由算法,从最初寻找一条最好的路由路径到现在需兼顾解决失败处理、流量负载均衡、提高网络资源利用率等问题。

传统网络路由算法是以Floyd算法[2,3]为代表的最短路径算法,主要查找网络中两两结点间的最短路径,为数据包提供最短的传输路径,但其对链路失效处理、链路流量控制等方面不能满足现今互联网动态性方面的性能要求。随着学术界和工业界对路由算法的改进,沿有向无环图路由RAD算法[4]提供了一种解决上述问题的方法。处理失效时,Floyd算法速度较慢且需全局路由重新计算,RAD算法是速度很快的硬件级别的本地响应。当网络中出现流量激增时,Floyd算法在最短路径上易拥塞,RAD算法可将流量分载在其他路径上而有效地避免链路拥塞。但RAD算法对查找最短路径方面重视程度不高,易导致数据包传输时间过长。本文对Floyd算法和RAD算法进行了具体介绍,通过实验对两者在链路利用率、平均传输代价、链路流量负载、链路失效对网络的影响范围等方面的性能进行了分析比较,实现结果为进一步提高路由性能的研究提供参考,希望能将这两种算法的优点结合起来进行改进,以研究出一种高性能、低代价的路由算法提高网络的性能。

1 Floyd 算法与 RAD 算法

1. 1 Floyd 算法

Floyd算法是一种用于寻找给定加权图中顶点间最短路径的算法,以1978年图灵奖获得者斯坦福大学计算机科学系教授Robert W. Floyd命名。Floyd算法采用动态规划的原理计算两两顶点间最短路径[3],主要解决网络路由寻找最优路 径的问题。

算法用数学语言描述[3]为: 假设Di,j,k为从顶点i到顶点j的只以( 1…k) 集合中的顶点为中间顶点的最短路径的长度,若最短路径经过顶点k,则Di,j,k= Di,k,k -1+ Dk,j,k -1; 若最短路径不经过顶点k,则Di,j,k= Di,j,k -1。最后,Di,j,k= min( Di,k,k -1+ Dk,j,k -1,Di,j,k -1) ,经多次迭代可依次求出每对顶点间的最短路径[5]。

Floyd算法在网络路由中得到广泛应用,能够极大地减小了数据包从源地址到目的地址的传输代价,减少了网络中的转发开支。但是,由于每次进行数据包传输时,该算法需要对全局进行计算以获取每对顶点间的最短转发路径,一旦网络拓扑图发生改变,则需要付出开支很大的代价重新进行计算。

1. 2 RAD 算法

RAD算法由加州大学伯克利分校的Junda Liu于2011年提出并首次将有向无环图的思想应用在网络路由中,主要用于对网络中的失败处理、流量负载均衡等方面。

对一个网络拓扑图,将其看作一个无向图G,首先为G中每个顶点分配一个order值。选定一个目的顶点v,其邻居结点为N( d) 。对任何结点d≠v,则v < d,min( N( d) ) < d。然后为G中的每条边分配方向来构建一个DAG。对边( i,j) ,如果i < j,则j- > i; 如果j < i,则i - > j。边的指向代表在实际拓扑中数据包转发的路径。RAD算法构造的DAG始终保持连通性,当DAG因失败( 例如链路失效使得路由拓扑变得不连贯) 而不能为数据包转发提供连通性时,那么通过本地修复来重建连通性。若一个顶点有多个出边,RAD算法首先选择可用的另一条边。当一个顶点所有的出边都失效时,则进行“结点反转”,即将这个顶点所有入边的方向进行反转来保持DAG图的连通性[6]。

RAD算法主要致力于保证数据包在转发过程中不出现中断,并且能有效地避免链路上流量负载过大。但是RAD算法并不是每次都选择最短路径,加重了数据包从源地址到目的地址的传输代价,增加了网络中的传输开支。

2 实验及算法性能分析

2. 1 数据集及相关度量

本文采用了用Rocketfuel[7]度量的10个互联网服务提供商ISP( Internet service provider) 网络拓扑图[8],分别是1221、1239、1755、2914、3257、3356、3967、4755、6461和7018。这10个网络是由Spring[9]等人分别对Abovenet、AT&T、Ebone、Exodus、Level3、Sprint、Telstra、Tiscali( Europe) 、Verio和VSNL( India) 这些运营商的测量。拓扑图中的结点总数、边总数、结点的平均度、弹性结点数和弹性结点所占总结点数的百分比如表1所示。结点的平均度是指平均每个结点所拥有的边数。弹性结点是指出边大于1的结点。

中介中心性[10]用来判断某个结点在一个网络拓扑图中的重要程度,一个结点v的中介中心性g( v) 定义为,σst是从结点s到结点t的所有最短路径的数目,是这些最短路径中经过结点v的路径数目。即一个结点的中介中心性等于这个结点在网络中其余两两组合的结点的所有最短路径中出现的比例。

本文实验在Linux环境下使用Python编写实验代码,分别选择10个网络拓扑图中不同中介中心性的结点作为目的结点,从链路利用率、平均传输代价、流量负载及链路失效四个方面对两种算法进行实验,实验结果通过具有代表性的结点呈现,能反映两种算法的真实性能。

2. 2 链路利用率的比较

链路利用率是指利用路由算法构建转发路径时,整个网络中所有处于转发路径上的链路总数占总的物理链路数的百分比。两种算法链路利用率的如图1所示,实验结果表明: Floyd算法的链路利用率小于RAD算法; 并且对于这两种算法,选取一个网络中任意一个结点为目的结点的链路利用率是相同的。

在这10个拓扑图中,Floyd算法的链路利用率分别为:41. 82% 、26. 59% 、44. 88% 、34. 00% 、59. 16% 、11. 90% 、46. 08% 、83. 33% 、61. 56% 和30. 32% 。其中,4755的链路利用率最高,3356的链路利用率最低,这是由拓扑结构中处于最短路径上的边的比例所决定。RAD算法构造DAG时,将所有的边都包括在转 发路径内,使得整个 网络的链 路利用率 均为100% 。

2. 3 平均传输代价的比较

假设每条链路上的传输代价为1,对于拓扑结构图中的每个目的结点,计算所有其他结点到这个目的结点的传输代价的平均值就是平均传输代价。这两种路由算法平均传输代价实验结果如图2所示,三个图分别表示了10个拓扑图中中介中心性较高、处于中间和较低的结点为目的结点的实验结果。

实验结果表明: Floyd算法的平均传输代价低于RAD算法。如网络1221,选取三个不同的目的结点,Floyd算法得出的平均传输代价为3. 19、4. 36和5. 0,分别小于RAD算法得出的4. 25、6. 40和6. 72。若分别选取每个网络中结点中心性一致的结点,Floyd算法的结果也分别小于RAD算法。因为Floyd算法计算的是两个结点之间最短路径的传输代价,因此两个结点间所有路径上传输代价最小的。当一个结点有多条转发链路时,RAD算法以相等的概率选择每条链路并计算所有的传输路径( 包含了最短路径和最长路径) ,因此两个结点间的平均传输代价大于最短路径上的传输代价。

2. 4 链路流量负载值方差的比较

假设每个结点发出的流量为1,对于每个目的结点,所有其他结点向这个目的结点发送1个单位的流量,那么整个网络中每条链路上的流量值即为链路流量负载值。为了体现网络链路拥塞情况,本文用链路流量负载值的方差来衡量每条链路上流量负载的平衡程度。两种算法链路流量负载值方差的实验结果如图3所示,三个图分别表示了10个拓扑图中中介中心性较高、处于中间和较低的结点作为目的结点的实验结果。

由实验结果表明: Floyd算法的链路流量负载值的方差总大于RAD算法。如网络3967,选取不同的目的结点507、519和490,Floyd算法的结果分别为38. 33、135. 30和264. 17,RAD算法的结果分别为25. 39、128. 86和230. 52,均小于Floyd算法。若选取10个网络中结点中介中心性一致的结点,Floyd算法的结果也分别大于RAD算法。因为Floyd算法中流量集中在最短路径上而非最短路径上流量负载为0,而导致链路上的流量负载波动较大且流量分配不平衡,易出现拥塞。当一个结点有多条转发链路时,RAD算法以相等概率为每条链路分配流量,因而链路上的流量分配比较平均,可以很好地避免链路拥塞。

2. 5 链路失效对网络的影响范围的比较

单条或多条链路失效会由于连锁反应而影响到网络中的其他节点,最终导致大规模的链路故障甚至网络崩溃[11]。当一条随机的链路失效时,Floyd算法统计需要重新计算转发路径的结点总数作为一次失效对网络影响范围的评判指标,RAD算法统计需要进行“结点反转”的结点总数作为一次失效对网络影响范围的评判标准。本文每次随机选择一条链路进行失效实验,共进行了100次,取这100次链路失效影响的结点总数的平均值进行比较。两种算法的实验结果如图4所示,三个图分别表示10个拓扑图中中介中心性较高、处于中间和较低的结点为目的结点的实验结果。

实验结果表明: 当一条链路失效时,RAD算法中网络受到影响的范围比Floyd算法中要小得多。如网络3356,使用Floyd算法对不同的目的结点计算得出的链路影响的范围分别是30. 35、11. 42和147. 15,而使用RAD算法计算出的结果全部是0,这说明链路失效对于Floyd算法影响很大而RAD算法几乎不受影响。若任选一个网络,如3257,取结点508作为目的结点,随机进行100次失效,使用Floyd算法发现受影响的结点总数多次出现239个或234个。由表1可以看出,3257中只有242个结点,这表示一条链路失效时网络中的所有的结点几乎都要重新计算其转发路径,开销非常大。使用RAD算法时,受到影响的结点总数最多只有25个,多数情况下没有结点受到影响,大大降低了链路失效时重新计算的开销。

3 结 语

通过对Floyd算法和RAD算法的性能比较,发现在链路利用率、链路流量负载均衡和链路失效对网络的影响范围方面,RAD算法要优于Floyd算法。在平均传输代价方面,Floyd算法要优于RAD算法。RAD算法在失败处理和流量负载均衡方面的优势显著,但是它还存在一些不足。如RAD算法在构建DAG时,为顶点分配的order不唯一且不是最优,可能会出现某些边上流量负载过大的情况。在以后的工作中,我们将利用动态规划的思想求出每个顶点的最优order来解决这个问题。

摘要：路由算法是影响网络性能的重要因素之一,对路由算法的选择至关重要。介绍路由算法中的Floyd算法和RAD(Routing along DAGs)算法,并通过实验对两种算法性能作出分析和比较。实验分析结果显示:在链路利用率、链路流量负载均衡和链路失效对网络的影响范围方面,RAD算法要优于Floyd算法。在平均传输代价方面,Floyd算法要优于RAD算法。

算法性能 篇2

特征点提取技术一直是摄影测量和计算机视觉的研究热点.从兴趣算子的角度研究了几种主流特征点提取算法,通过大量的实验,从速度、精度、适应性方面,定量地比较和分析了各算法性能、优缺点和适应环境,针对特征点分布欠均匀的`问题,提出改进措施,并取得了较理想的结果.

作 者：张春美 龚志辉 黄艳 ZHANG Chun-mei GONG Zhi-hui HUANG Yan  作者单位：张春美,ZHANG Chun-mei(信息工程大学,测绘学院,河南,郑州,450052;73603部队,江苏,南京,210049)

龚志辉,黄艳,GONG Zhi-hui,HUANG Yan(信息工程大学,测绘学院,河南,郑州,450052)

刊 名：测绘科学技术学报  PKU英文刊名：JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY 年，卷(期)： 25(3) 分类号：P231 关键词：特征点提取   性能评估   重复率   局部熵  

算法性能 篇3

(1. 集美大学 航海学院，福建 厦门 361021；2. 大连海事大学 航海学院，辽宁 大连 116026；3. 中国电信九江分公司，江西 九江 332000)

0 引 言

随着世界海运事业的发展，船舶数量越来越多，船舶朝大型化、高速化方向发展，船舶的航行安全显得越来越重要，这客观上推动着船舶导航与自动化驾驶技术的发展.船舶在海上航行受到风、浪和流的影响，故只有正确控制和使用船舵才能使船舶在各种外界影响下保持航向或者改变航向，从而保证船舶安全迅速地从出发地到达目的地.自动舵具有减少人力、节约燃料、降低机械磨损等功能.目前,船舶航向控制领域出现各类先进的控制算法.为设计满足不同指标要求及适应各种应用场合的航向智能控制算法，通过选择若干主流算法集成到船舶智能操控(Ship Intelligent Handling and Control, SIHC)仿真平台桌面系统进行性能测试.本文基于文献[1]和[2]实现的算法及文献[2]提出的控制算法评价方法，着重对该平台集成的两种航向控制算法进行初步的性能测试.

1 SIHC仿真平台简介

SIHC仿真平台是用于船舶航行自动化基础研究的仿真测试平台，其中的本船具有航向和航迹两种自动控制模式，能实现船舶自动避碰与航迹自动监控，可用于船舶智能避碰决策算法与智能控制算法测试.该平台实现以下创新点：智能目标船功能；先进的仿真技术；集成6自由度液压/电动平台；接入船舶自动识别系统(Automatic Identification System, AIS)交通流功能；标准电子海图平台.本文测试使用的是SIHC仿真平台的桌面系统，主要由1台主控台计算机、1台目标船服务器、4台本船计算机构成，本船集成有丹麦航海研究所(Denmark Marine Institute)开发的6自由度船模.

2 船舶航向控制算法原理

2.1 普通PID航向自动舵原理

6自由度船模自带有普通PID航向自动舵.基于其自带的船模参数，可以更好地确定PID的3个参数的初始值，从而达到较好的航向控制效果.普通PID航向自动舵结构及原理分别见图1和2.从图1可以看出，该自动舵实际上由一个传统的PID航向自动舵和一个滤波器组成.

图1 普通PID航向自动舵结构

图2 普通PID航向自动舵原理

普通PID航向自动舵控制规律的传递函数形式为

式中:U(s)为输出舵角；E(s)为输入航向偏差；K为舵增益；TI为积分时间常数；Td为反舵时间； 1/Tg为滤波频率；1/α为差异化系数.

2.2 模糊自整定PID航向自动舵原理

模糊自整定PID控制[1]运用模糊数学的基本原理和方法，把模糊控制规则的条件及其操作用模糊集表示，并把这些规则和有关信息作为知识存入计算机知识库中，然后根据控制系统的实际响应情况运用模糊推理，自动实现对PID参数的最佳调整[3].模糊自整定PID控制算法由模糊自整定PID控制器、限幅环节和被控对象等3个部分组成，其原理见图3.

图3 模糊自整定PID控制原理

模糊自整定PID控制算法在运行中不断检测误差e(t)=ψ(t)-ψr(t)和误差的变化率ec(t)=de(t)/dt，然后根据模糊规则(见表1～3)对PID的3个参数kp，ki，kd进行调整，以满足不同e和ec对控制参数的不同要求，从而使被控对象具有良好的动、静态性能.其中，ψ表示受控系统的航向角，ψr表示其设定值.

在船舶模糊自整定PID自动舵中，必须测量误差和误差的变化率即艏摇角速率ec.

在本设计中，作为输入的e和ec的论域为

e,ec={-5,-4,-3,-2,-1,0,1,2,3,4,5}

作为输出的修正量Δkp,Δki,Δkd的论域为

Δkp，Δki，Δkd={-5,-4,-3,-2,-1,0,1,2,3,4,5}

选取的输入、输出变量词集[4]为

e,ec,Δkp，Δki，Δkd={NB,NM,NS,ZO,PS,PM,PB}

词集中的元素依次分别代表负大、负中、负小、零、正小、正中和正大.

表1 Δkp的模糊控制规则[5]

表2 Δki的模糊控制规则

表3 Δkd的模糊控制规则

根据工程技术人员的技术知识和实际操作经验，本设计中输入、输出变量的隶属度函数曲线NB部分均取降半正态分布曲线，PB部分均取升半正态分布曲线，NM,NS,ZO,PS和PM部分均取三角分布曲线[6],因此可以得出各模糊子集的隶属度.根据各模糊子集的隶属度赋值表和各参数模糊控制模型，应用模糊合成推理设计PID参数的模糊矩阵表，查出修正量代入式(1)～(3)：

在整个系统运行过程中，控制系统通过对模糊逻辑规则的结果处理、查表和计算，完成对PID参数的在线自整定.

3 航向控制算法性能评判方法

3.1 航向跟踪评判方法

为使船舶自动舵具有航迹(线)自动保持能力，必然要求自动舵具有航向跟踪功能，即在给定航向因接近计划航向的转向点需要改变的情况下，自动舵具有自动跟踪航向变化的能力.[1]

根据定值自动控制系统的性能指标及经验，航向跟踪的性能指标主要由超调量、跟踪响应速度、操舵次数、最大舵值和振荡次数组成.为得到这5个指标的权值，针对航向跟踪进行问卷调查.问卷中通过两两比较的方式让被调查者在速度快、精度高、耗油少等3个因素中选择最看重的因素.共发出问卷68份，速度快、精度高和耗油少被选中的次数分别为62，79和11.

问卷调查中的3个因素与这5个性能指标的相关程度有很大的差异：速度快是跟踪响应速度指标的最大关联因素；精度高是超调量指标的最大关联因素；耗油少是操舵次数、最大舵值、振荡次数这3个指标的最大关联因素.因此，可以分别算出5个性能指标的相应权值：超调量指标权值w1为0.45；跟踪响应速度指标权值w2为0.36；操舵次数、最大舵值、振荡次数这3个指标的权值w3，w4，w5理论上应该均为0.06.但是这5个性能指标的权值和不为1.经研究发现振荡次数指标比操舵次数和最大舵值这两个指标相对更重要，故其权值理应比另外两个大.以此得到超调量、跟踪响应速度、操舵次数、最大舵值、振荡次数这5个指标的权值依次分别为0.45，0.36，0.06，0.06，0.07.根据对船上工作人员的问卷调查，自动舵改向的最佳状态是零超调、无振荡、操舵两次、舵向改变10°时的响应时间控制在300 s以内、最大舵值不超过10°.故得出改向时自动舵的5个性能指标的隶属函数[10-11]如下：

超调量的隶属函数

f(x)=e-x2(x≥0)

跟踪响应速度的隶属函数

操舵次数的隶属函数

最大舵值的隶属函数

振荡次数的隶属函数

f(x)=e-x2(x≥0)

3.2 航向保持评判算法

船舶自动舵的航向保持功能是在给定航向不变的情况下能确保船舶在外界环境干扰作用下具有保持既定航向的能力.航向保持的性能指标主要由保向精度和舵机能耗组成.航向保持的性能指标为

式中：J为总体性能指标值；N为采样个数；ψ0(n)为设定航向；ψ(n)为实际航向；δn为当前舵角.对航向保持的评判主要从航向偏差和能耗方面考虑，所以J值越小，控制算法的航向保持性能越好.

为得到保向精度指标和舵机能耗指标的权值λ1和λ2，对一些有经验的船舶驾驶人员和航海教学人员进行一次问卷调查.在发出的58份问卷中，减少航向偏差和减少舵机能耗被选中次数分别为43和15，由此可以得出λ1和λ2分别为0.74和0.26.

4 评判结果及分析

4.1 航向跟踪测试方案与评判结果

考虑到不同船型及不同环境等因素，测试方案选取3种不同船型船模，即散货船、集装箱船和油船，另外为周全考虑又选取一条较小船模(巡逻艇)，船模信息见表4.环境设置分为8个等级，风向为40°，波浪周期为5 s，波浪方向为220°，具体的风速与浪高对应关系见表5.测试过程考虑流的影响，流速设置为1 kn，流向为120°.

表4 测试方案船模基本信息

表5 测试方案环境设置

在同一海域设置本船1和本船2，测试过程中两条船采用同样的船模.设定船舶的初始速度为该船的服务速度，船舶初始航向为0°，船舶航行全过程中其车钟都在FULL挡位.船舶开始运行后本船1和本船2分别采用模糊自整定PID航向自动舵和普通PID航向自动舵进行改向60°的操作，当两船航向改到60°且稳定后，结束测试.利用平台设计的接口，提取两船的数据，然后利用MATLAB分别画出两船的实际航迹向曲线.图4和5分别为船模III在环境7下的两种自动舵的实际航向及舵角变化曲线，其中，实线和虚线分别为普通PID自动舵和模糊自整定PID自动舵控制下的变化曲线.

图4 航向变化曲线 图5 舵角变化曲线

再利用上述航向跟踪性能评判方法对每次实验数据进行处理，得到的评判结果见表6.

从表6可以明显看出，在不同环境下两种自动舵的控制性能基本接近，且稳定性都较好，但是在风浪等级较高的环境条件下亦或对于较小的船模，普通PID自动舵的性能稍好.同时可以看出，两种自动舵对不同船型的控制性能有明显差异(巡逻艇的控制效果最好，其次是集装箱船，对油船的控制性能最差)，这显示出两种自动舵对不同船型航向跟踪的适应性存在不足.

4.2 航向保持测试方案评判结果

航向保持测试方案的环境设置和船模选取与航向跟踪测试方案一致.在同一海域设置本船1和本船2，测试过程中两船采用同样的船模，设定船舶的初始速度为该船的服务速度，船舶的初始航向为60°，船舶航行全过程中其车钟都在FULL挡位.船舶开始运行后本船1和本船2分别采用模糊自整定PID和普通PID航向自动舵保向，当两船的航向都稳定在60°时，结束测试.根据第3.2节的航向保持评判算法，利用MATLAB对实验输出的船首向及舵角等数据进行处理，所得评判结果见表7.

表7 航向保持评判结果

由船模I和II的评判结果分析可知：在航向保持过程中本船1的总体性能指标值比本船2的小，即模糊自整定PID自动舵比普通PID自动舵有更好的航向保持性能.对于船模Ⅲ，普通PID自动舵的航向保持性能较好.由于船模IV较小，在风浪等级较高的环境下两种自动舵对其丧失航向保持能力.表7同时显示，模糊自整定PID自动舵对集装箱船的航向保持控制性能最好.

5 结束语

借助SIHC仿真平台开展船舶自动控制算法仿真及性能测试，利用MATLAB工具，分别从航向跟踪和航向保持两个方面对该平台集成的普通PID自动舵和模糊自整定PID自动舵的控制性能进行测试.从测试结果可知：在航向保持方面，就一般的船型而言，模糊自整定PID自动舵的性能优于普通PID自动舵；在航向跟踪方面，普通PID自动舵和模糊自整定PID自动舵的控制性能近乎一致；在某些环境下，普通PID自动舵对某些船型的控制性能会稍胜一筹，但对不同船型的适应性有待日后进一步优化.在航向控制评判算法方面，航向跟踪性能评判的隶属函数的临界值还有待于进一步细致优化，以更客观精准地分析比较不同船舶航向控制算法性能的优劣.

参考文献：

[1] 李丽娜, 杨神化, 熊振南, 等. 船舶拟人智能避碰决策理论框架的研究[J]. 中国航海, 2009, 32(6): 30-34.

[2] ZHAO Q, LI L, CHEN G. Research on fuzzy self-tuning of PID autopilot[C]//ICTE 2011, ASCE, 2011: 985-990.

[3] 赵晴. 船舶航迹智能控制算法的研究[D]. 厦门: 集美大学, 2012.

[4] 刘洋, 米伟, 郭晨. 船舶航向模糊自整定操舵控制器的研究[J]. 中国航海, 2010, 33(1): 71-75.

[5] 季本山. 基于PLC的模糊PID船舶自动舵[J]. 上海海事大学学报, 2009, 30(4): 57-62.

[6] 陈水利, 李敬功, 王向公. 模糊集理论及其应用[M]. 北京: 科学出版社, 2005： 42-58.

[7] 李丽娜, 张寿桂. 航海自动化[M]. 2版. 北京: 人民交通出版社, 2012: 70-83.

[8] HTIN Aung Kyaw, XIAO Yingjie. Assessment on the Yangon river channel based on fuzzy synthetic evaluation[J]. 上海海事大学学报, 2007, 28(1): 50-56.

[9] 陈辰, 胡甚平. 基于模糊DEA的航运公司安全管理有效性评价[J]. 上海海事大学学报, 2012, 33(1): 12-15.

[10] 张晓平. 模糊综合评判理论与应用研究进展[J]. 山东建筑工程学院学报, 2003, 18(4): 90-93.

算法性能 篇4

关键词：入侵检测,模型构建,C4.5算法,BayesNet算法

1. 入侵检测系统的功能结构概述

入侵检测是从计算机网络或计算机系统中的若干关键点搜集信息, 并对其进行分析, 从中发现网络或系统中是否有了违反安全策略的行为和遭到袭击的迹象的一种机制。

入侵检测系统基本上不具有访问控制的能力, 它像一个有着多年经验、熟悉各种入侵方式的网络侦察员, 通过对数据包流的分析, 可以从数据流中过滤出可疑数据包, 再通过与已知的入侵方式或正常使用方式进行比较, 来确定入侵是否发生和入侵的类型并进行报警。网络管理员根据这些报警可以确切地知道所受到的攻击并采取相应的措施。

2. C4.5算法和Bayes Net算法的原理

2.1 C4.5算法的原理

C4.5是对著名的决策树归纳算法ID3的改进版本, 结合剪枝算法去除了不可能分支和过拟合分支, 以此避免过拟合问题, 并大幅度提高了其计算速度。

C4.5算法采用信息增益率作为选择分支属性的标准, 克服了ID3算法中信息增益选择属性时偏向选择取值多的属性不足, 并能够完成对连续属性离散化的处理, 还能够对不完整数据进行处理。C4.5算法属于基于信息论的方法, 它是以信息化为基础, 以信息熵和信息增益度为衡量标准, 从而实现了对数据的归纳分类。

C4.5算法的主要特点是准确性高, 分类模型构建速度快, 但对训练样本数量和质量要求较高, 对空值的适应性较差;C4.5算法算法由于以决策树为基本形式, 因而理解性较好。

2.2 Bayes Net算法原理

Bayes算法是由Microsoft SQL Server Analysis Services提供的一种基于贝叶斯定理的分类算法, 可用于预测性建模。贝叶斯分类器的分类原理是通过某对象的先验概率, 利用贝叶斯公式计算出其后验概率, 即该对象属于某一类的概率, 选择了具有最大后验概率的类作为该对象所属的类。

3. C4.5和Bayes Net算法的实验设计

3.1 实验使用的数据集

实验数据集分为训练数据集和测试数据集。本实验选用的训练数据集是KDD CUP 99。

KDD CUP 99的10%训练数据集中共有494 021条连接记录, 每一条连接记录都是由41个特征属性和一个决策类属性组成的, 共42个属性。特征属性用来描述这条连接记录的各项指标, 其中包含9个离散型属性和32个连续型属性。其中, 1~9是属于网络连接的基本特征属性, 10~22是属于网络连接的内容特征属性, 帮助对U2R和R2L攻击进行检测, 23~41是属于网络连接的流量特征属性 (2s时间单元) 。

本实验选择了weka系统, 该系统要求训练数据集格式为ARFF, 需要对三组数据进行格式处理, 以符合weka系统的需要。ARFF格式的文件头需要包含数据的关系名称以及各属性的定义及取值范围的说明。实验选取了三组数据, 分别从KDD CUP 99数据集中, 采用无放回抽样的方式来获取, 各组数据集中, 分别对三组数据进行处理, 生成三个ARFF文件, 分别命名为1.arff、2.arff和3.arff。使用weka系统的explorer功能, 通过文件选择按钮, 打开相应的数据文件。

3.2 实验详细设计

本实验选择了两种算法, 分别是C4.5算法和Bayes算法, 这两种算法在weka系统中, 定义为J48和Bayes Net。在Weka系统中, 作为一个公开的数据挖掘工作平台, 集合了大量能承担数据挖掘任务的机器学习算法, 包括对数据进行预处理, 分类, 回归、聚类、关联规则以及在新的交互式界面上的可视化, 实现了大量的用于数据挖掘的算法。

1) 将kddcup.data中的数据用UE编译器打开后, 从中选取了五种类别样本, 并分别进行三组数据无放回的随机抽取。

第一组:normal:25条, ipsweep:18条, smurf:24条, neptune:17条, buffer_overflow:2条;

第二组:normal:19条, ipsweep:15条, smurf:18条, neptune:15条, buffer_overflow:4条;

第三组:normal:16条, ipsweep:16条, smurf:13条, neptune:19条, buffer_overflow:8条;

2) 将文件格式更改为Weka文件系统支持的arff格式, 将其导入Weka系统中。

3) 用“Explorer”分别打开刚才得到的三个arff格式文件。

4) 切换到“Classify”选项卡, 点击“Choose”按钮之后选择Weka系统中的决策树J48算法和Bayes Net算法, 并采用十折交叉验证分别测试算法的准确性。

5) 点击“Start”按钮开始让算法生成模型。

4.J48算法和Bayes Net算法的实验结果分析

4.1 实验结果性能对比

TR Rate表示在分类器的所有预测结果中, 正确判定Positive的样本比率。FR Rate则表示错误判定Positive的样本比率。Precision是计算该属性的总体精度。通过三种性能的直观对比可有效进行对算法的评价。

第一组数据分析如表1:

第二组数据分析如表2:

第三组数据分析如表3:

5.性能分析总结

C4.5算法有如下优点:产生的分类规则易于理解。其缺点是:在构造树的过程中, 需要对数据集进行多次的顺序扫描和排序, 因而导致算法的低效。通过时间对比以及结合数据分析可知, 其C4.5的时间复杂度为O (mlog2m) , m为训练数据集合中样本个数。相对于Bayes Net算法, Bayes Net准确率高, 它的时间复杂度为O (n3) , n为训练数据集合的n个元组, 它在极小的训练样本中表现了极高的分类准确度, 但计算速度偏慢;在可理解性方面C4.5算法以其决策树的表达形式表现更好, 更适合入侵检测建模使用。

算法性能 篇5

空中目标声信号检测器是声探测系统中的重要组成部分,随着现代战场环境的日趋复杂化,被动声信号检测器以其自身独特的优势越来越受到人们的重视.文中提出了将语音信号检测中的过零率检测算法用于空中目标检测中的方法,并同传统的`能量检测算法相比较.通过计算机仿真试验,结果表明过零率检测算法不但具有算法简单、运算时间短的特点,而且其稳定性比能量检测算法要好,具有一定的识别空中目标的能力.

作 者：张国智 李京华 ZHANG Guo-zhi LI Jing-hua  作者单位：西北工业大学电子信息学院,西安,710072 刊 名：弹箭与制导学报  PKU英文刊名：JOURNAL OF PROJECTILES, ROCKETS, MISSILES AND GUIDANCE 年，卷(期)：2007 27(2) 分类号：V248 关键词：能量检测器   过零率检测器   目标检测  

★ 一种从低分辨率图像序列获取高分辨率图像的算法

分块查找算法性能分析 篇6

在计算机中,查找是经常需要用到的操作。在数据结构课程中,查找算法分为静态查找和动态查找两大类[1]。静态查找指的是在查找过程中其结构始终不发生变化的查找表,静态查找主要分为顺序查找和折半查找两大类,还有一种静态查找为索引查找[2]。在此,研究分块查找算法(即索引顺序查找算法)的性能,其中给出了通过二分查找和顺序查找两种不同的查找方式来确定块的算法。通常若找到与给定关键字相同的数据元素,则返回该数据元素在查找表中的位置。若在查找表中找不到要查找的对象,则返回0或者空指针。

为了讨论方便,存放数据的分块查找表类型定义如下:

2 分块查找算法

分块查找要求把顺序表分成若干块,每一块中的键值存储顺序是任意的,但要求前一块中的最大键值小于后一块中的最小键值。另外,还需要建立一个索引表,索引表中的每个索引项的索引值域用来存储对应块中的最大关键字。

2.1 二分查找确定块的分块查找算法

2.2 顺序查找确定块的分块查找算法

3 分块查找算法的性能分析

从分块查找算法可以看出,查找过程实际上是由两部分组成,先对索引表进行二分查找或者顺序查找,确定待查记录在哪一块中,然后在已经确定的块中用顺序查找进行查找,即查找的性能与这两部分的查找性能有关。例如把n个关键字分为b块,其中前b-1块中的关键字数均为s=n/b,最后一块小于或等于s,索引表是一个递增有序表。

索引表能够用二分查找和顺序查找,而块内无序,只能用顺序查找。如果索引表用二分查找,则分块查找算法平均查找长度ASL=log2(b+1)-1+(s+1)/2=log2(n/s+1)+s/2;如果索引表用顺序查找,则分块查找算法平均查找长度ASL=(b+1)/2+(s+1)/2=(s^2+2s+n)/(2s)。在此,主要研究在等概率情况下计算分块查找成功时的平均查找长度的算法。

3.1 计算二分查找确定块时的平均查找长度算法

3.2计算顺序查找确定块时的平均查找长度算法

4 结语

关于查找算法很多文献都有介绍过,在文献[3]中给出了顺序查找法、二分查找法、二叉排序树查找法和散列查找法的平均查找长度的计算方法,但是对于分块查找算法没有介绍。通过描述分块查找的算法及其平均查找长度的计算,更能清楚分块查找算法的性能及适用范围,有助于读者更好地理解分块查找算法。

参考文献

[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2007.

[2]马靖善,秦玉平.静态查找算法性能分析[J].渤海大学学报(自然科学版),2014,35(1):23-27

[3]秦玉平,王丽君,刘伟.查找算法平均查找长度的计算方法[J].渤海大学学报(自然科学版),2011,32(4):353-357.

MUSIC算法的性能比较 篇7

关键词：DOA,求根MUSIC,空间平滑技术,改进MUSIC算法,修正MUSIC算法,智能天线

波达方向估计 (DOA) 在智能天线系统上行多用户信号分离、下行选择性发送及移动无线通信定位技术应用中有着重要的意义[1]。基于DOA估计的智能天线可定位和追踪信号, 不仅增强了兴趣信号 (Signalof-Interest) , 且减少了干扰信号的作用, 广泛应用于无线通信系统[2]。R.O.Schmidt博士于1979年提出的多重信号分类 (MUSIC) 法[3]是一种经典的高分辨能力的空间谱估计方法, MUSIC算法利用信号子空间与噪声子空间的正交性, 构造空间谱函数, 通过谱峰搜索来检测信号的DOA。其具有分辨率高、性能稳定及精度高等特点, 对小于阵元数的信源良好的DOA估计性能, 得到了广泛的应用。但其计算量大及对于相干[4]、低信噪比、角度间隔小的信号无法分辨等, 限制了MUSIC算法的高分辨优势。针对以上问题, RootMUSIC算法[5]以求根过程代替谱搜索大幅减少了计算量, 基于空间平滑技术的MUSIC算法[6]则对相干信号也能正确分辨、改进MUSIC算法[7]及修正MUSIC算法[8]则不仅可分辨相干信号, 且对于小信噪比及角度间隔较小的信号也能正确分辨。通过对这几种改进MUSIC算法的分析比较, 为实际应用提供了参考。

1 经典MUSIC法

经典MUSIC算法是根据窄带数据模型以几何观点考察信号参数估计的问题。如图1所示, 入射信号以入射角θ入射到一N元等距线阵, 阵元间距为d, 波长为λ。则信源相对于参考阵元的方向向量为

式中, (·) T表示转置。

对于来自空间远场的M个信源, 阵列接收到的信号为

其中, A=[a (θ1) , a (θ2) , …, a (θM) ]T是方向矩阵, S (t) =[s1 (t) , s2 (t) , …, sM (t) ]T是入射信号矢量, N (t) =[n1 (t) , n2 (t) , …, nN (t) ]T是噪声矢量。

计算式的协方差矩阵的特征值分解

式中, (·) H表示共轭转置;Rs为信号协方差矩阵;σ2为噪声功率;∑s为主特征值矩阵;Vs, Vn分别为信号子空间与噪声子空间。

由RxxVn=σ2Vn, 可得

可知

这说明构成A的M个方向矢量与N-M个小特征值相关的特征向量正交, 定义MUSIC空间谱估计为

MUSIC谱中M个最大峰值对应于入射到阵列上的M个信号DOA。PMUSIC (θ) 对应的并不是真实的功率谱, 但它能真实且高分辨率地反映各信号的DOA。

2 几种改进MUSIC算法

2.1 求根MUSIC算法

在式 (3) 的基础上, 定义一多项式, 如下

式中, Z=[1, z, …, zN-1]T。

多项式的阶数为2 (N-1) , 即有N-1对相互共轭的根, 其中有M对根{z1, z2, …, zM}正好分布在单位圆上, 即。在实际中, 因数据存在误差, 只需取M个最接近于单位圆的根即可。根据zi与方向矢量的对应关系, 可得

求根MUSIC算法是以一关于的矢量代替方向向量, 从而用求根过程代替谱峰搜索, 大幅减少了运算量。

2.2 基于空间平滑技术的MUSIC法

以上的MUSIC算法都是基于Rxx满秩时信号子空间与噪声子空间正交的原理, 即入射信号之间弱相关或不相关。为使信源相干或相关时仍能获得正确的DOA估计, 采用空间平滑技术对相干信号进行预处理来修正MUSIC算法。空间平滑可分为前向平滑、后向平滑和前后向平滑, 但前两种方法有效阵元少, 故文中采用前后向平滑技术, 即双向平滑技术。

空间平滑技术是通过将N元等距线阵划分为q个重叠的子阵, 每个子阵的阵元数为p, 满足p+q-1=N。

计算所有前向平滑 (从左到右) 子阵协方差矩阵的平均值, 即前向平滑协方差矩阵, 如下

式中, Aj为前向平滑第个子阵的方向矢量。

同样, 计算所有后向平滑 (从右到左) 子阵协方差矩阵的平均值, 即后向平滑协方差矩阵。令K为一p维反向单位矩阵

则后向平滑协方差矩阵可表示为

式中, (·) *表示共轭。

则双向平滑协方差矩阵可表示为

由上可知, 空间平滑技术是牺牲有效阵元来保证协方差矩阵满秩, 再利用经典MUSIC算法进行谱估计, 得到相关信号的DOA。

2.3 改进MUSIC法

IMUSIC算法是从噪声子空间角度对相干信号进行预处理来修正MUSIC算法, 使得修正后的噪声子空间与方向矩阵充分正交。首先, 设J为一N维反向单位矩阵, 令

其次, 对进行特征值分解

得到特征值 (按从大到小排列) 矩阵S和特征向量矩阵U, 可知噪声子空间为Vu=U (∶, (M+1) ∶N) 。令

式中, diag (·) 表示取对角线元素构成列向量。再对进行特征值分解, 得到噪声子空间为Vuu。

最后, 对两次得到的噪声子空间取平均, 即

再将其带入式就可对相干信号进行DOA估计。

2.4 修正MUSIC算法

令Y (t) =J·X (t) *, 则有

在经典MUSIC算法、Root-MUSIC算法和IMUSIC算法中, 只利用了X (t) 或Y (t) 的自协方差矩阵信息, 若再利用X (t) 或Y (t) 的互协方差矩阵信息, 则整个协方差矩阵的信息量将大幅增加, 提高算法的性能。

故令R=[RxyRxxRyyRyx], 再通过特征值分解, 求得噪声子空间, 带入式进行DOA估计。该法充分利用了接收到的数据信息。

综合以上对各种改进算法的介绍, 可知RootMUSIC算法与经典MUSIC算法的原理相同, 只是以求根过程代替谱峰搜索过程;SST-MUSIC算法、IMUISC算法及MMUSIC算法则是对经典MUSIC算法进行预处理, 其实现算法不同, 实质都是采用空间平滑的思想来去相干。

3 仿真与分析

在如图1所示的等距直线阵中, 设阵元数N=15, 阵元间距d=0.5λ, 信源数M=4, 入射角θ=[27°, 30°, 45°, 60°], p=q=8, 快拍数为1 024。

(°)

由表1知, 信号不相关时, Root-MUSIC算法分辨率高, 在小信噪比、角度间隔小时仍能很好地分辨, 但因求根过程计算存在误差, 其DOA估计稍有偏差, 偏差<0.4°;信号相关时, 仍可较好地分辨, 虽然其DOA估计偏差变大, 但偏差不超过。

图3~图5为4种MUSIC类算法在信号非相关时的性能比较, 该类算法随信噪比的降低, 其分辨率降低。从图中可知, 经典MUSIC算法与MMUSIC的空间谱重叠, 可分辨角度间隔小的信号, 谱峰尖锐。SST-MUSIC对于角度间隔小的信号分辨率低, IMUSIC与MMUSIC空间谱相似, 但IMUSIC在低信噪比时对于角度间隔小的信号无法分辨。

图6~图8为4种MUSIC类算法在信号3、4相关时的性能比较, 该类算法随信噪比的降低, 其分辨率降低。从图中可知, 经典MUSIC算法失效, 无法分辨相关信号。SST-MUSIC可分辨相关信号, 但无法分辨角度间隔小的信号。IMUSIC在低信噪比时谱峰有偏差。MMUSIC能较好地分辨低信噪比和角度间隔小的信号, 且峰值尖锐。

4 结束语

本文在不同仿真条件下对比了经典MUSIC算法、求根MUSIC算法、基于空间平滑技术的MUSIC算法、改进MUSIC算法和修正MUSIC算法的性能。从仿真结果分析可知, 该类算法的分辨率随信噪比的降低而降低。求根MUSIC算法、改进MUSIC算法及修正MUSIC算法能分辨低信噪比、相关及角度间隔小的信号, 性能较好。其中, 修正MUSIC算法性能稳定, 无偏差, 谱峰尖锐, 且计算复杂度低, 其性能最优。对超分辨DOA估计算法的分析有利于智能天线在无线通信中的应用, 具有重要意义。

参考文献

[1]赵谦, 张保军.通信系统中Matlab基础与仿真应用[M].西安:西安电子科技大学出版社, 2010.

[2]DHOPE T S, SIMUNIC D, DJUREK M.Application of DOA estimation algorithms in smart antennas systems[J].Studies in Informatics and Control, 2010, 19 (4) :445-452.

[3]ABDULLAH A, CHAHINE S A, RAMMAL M, et al.A smart antenna simulation for estimation using MUISC and ESPRIT algorithms[C].Beijing:Radio Science Conference, 2006.

[4]何伟刚.基于相干信号源的改进MUSIC算法[J].电子科技, 2011, 24 (8) :8-11.

[5]陈小龙, 关键, 黄勇.DOA估计算法性能分析及仿真[J].海军航空工程学院学报, 2009, 24 (2) :191-194.

[6]周菊瑄, 蒋志勇, 杨双.智能天线中DOA估计算法的研究[J].通信技术, 2008, 41 (6) :97-99.

[7]赵谦, 董民, 梁文娟.DOA估计算法的一种修正MUSIC算法的研究[J].计算机工程与应用, 2012, 48 (10) :102-105.

基于信道性能的频谱分配算法 篇8

参考文献[2]提出了颜色敏感图着色 (CSGC) 频谱分配算法, 考虑了各信道间的干扰性以及频谱效益的差异性, 使网络总效益最大化, 但是其未考虑信道性能等因素对实际应用的影响。在实际应用中, 主用户PU (Primary User) 的接入具有时变特性, 当主用户到达时, 若次用户SU (Secondary User) 没有及时撤离, 则会对主用户的通信产生干扰, 这就要求次用户进行频谱切换或中断。频繁的频谱切换会增加系统的感知时间、执行切换的次数, 也会增加次用户的等待时长, 降低系统性能[5]。参考文献[6]提出考虑了信道可用率的频谱分配算法, 但是其没有考虑到次用户传输时间对可用率的影响, 次用户所需的传输时间越长, 信道相对可用率越低;其次, 也没有考虑到信道衰落因子这个因素。信道衰落因子的大小会直接影响到信道的信噪比、检测概率[7]以及误码率, 继而影响到系统实际的效益值。综上所述, 次用户需要根据主用户的信道特性, 结合自身业务量的大小, 选择合适的信道进行传输。

本文利用ON-0FF模型对授权信道使用情况进行建模, 采用基于次用户业务时间的相对频谱利用率、信道衰落因子来衡量信道性能, 最后结合CSGC[8]算法进行频谱分配, 该算法可以在提升实际总效益的同时, 降低信道的切换概率以及误码率。

1 问题描述

如果把主用户在授权信道上的通信活动看成是ON与OFF两个状态交替出现的更新过程, 即ON-OFF模型, 假设共有M个信道, 则对于信道m (1≤m≤M) , Tmoff表示信道空闲状态的持续时间, 其服从参数为λm的负指数分布:

同理, 信道忙碌状态的持续时间Tmon服从参数为μm的负指数分布:

其状态转移图如图1所示。

若t=0时刻信道处于空闲状态, 则根据马尔科夫链以及更新公式[9]可得信道m的瞬时可用率为:

信道m的平均可用概率为:

信道平均可用概率是指频谱空穴出现、可被次用户使用的概率。参考文献[6]根据信道平均可用概率式 (4) 的大小来优化CSGC算法中的信道效益矩阵。但是, 参考文献[6]没有考虑到次用户本身的传输时间对可用概率的影响, 即没有由传输时长和频谱空穴时长综合决定次用户的信道选择。

设次用户n的业务时间为Tn, 则称次用户n在信道m上完成传输的最小概率为相对信道可用概率Pn, m:

频谱空洞时变特性对不同的次用户有差异。信道相对可用概率是指频谱空穴被某个次用户使用, 使次用户在此频带上能够完成传输的概率, 即在业务完成之前不发生切换的概率。信道相对可用概率越高, 则意味着次用户在数据传输中切换的概率越小、切换次数越少, 由此切换成本降低, 实际效益得到提高。

设本文采用BPSK调制, 则次用户n在信道m上进行传输时的误码率、实际效益、检测概率分别为:

其中, Pn, mG、hn, m分别为次用户n在信道m上的发射功率以及信道衰落因子 (信道增益) , Qn, m (·) 为泛化Q函数, λ为频谱感知判决门限。Pn, mG与次用户和主用户的相对距离有关, 这里不做讨论。

在以往的频谱分配文献中, 都没有考虑信道衰落对频谱分配的影响。从式 (6) 、 (7) 、 (8) 可以看出, BER的大小与信道衰落因子有关, 衰落越明显, 误码率越高。衰落越大, 实际效益值越低, 检测准确率越低。

因此, 在进行频谱分配的过程中, 需要考虑到相对信道利用率以及信道衰落因子这两个因素。

2 基于信道性能的CSGC算法

一般图着色模型建模如下:其中n表示次用户 (1≤n≤N) , m表示信道 (1≤m≤M) , N、M分别为认知网络中次用户数量和授权信道数量。

(1) 空闲矩阵L。L={ln, m|ln, m∈{0, 1}}N×M, 即次用户可使用的频谱矩阵。当ln, m=1时, 表示次用户n可以使用信道m, ln, m=0, 表示不可用。

(2) 效益矩阵B。B={bn, m}N×M, bn, m表示次用户n使用信道m给系统带来的效益。LB={ln, m·bn, m}, 当ln, m=0时, 表示信道不可用, 实际效益为0。

(3) 干扰矩阵C。认知用户在使用相同信道时可能会互相会产生干扰。C={cn, k, m|cn, k, m∈{0, 1}}N×N×M, cn, k, m=1表示次用户n和次用户k同时使用信道m时会产生干扰, cn, k, m=0表示不会产生干扰。

(4) 无干扰分配矩阵A。A={an, m|an, m∈{0, 1}}N×M, an, m=1表示信道m被分配给次用户n。矩阵A必须满足无干扰条件:

不同次用户在不同频带上的可用信道性能不同、衰落因子不同、理想效益不同, 因此, 在实际应用中, 要考虑各个方面因素的影响。由此提出基于信道性能的CSGC频谱分配算法。

R为实际效益矩阵, 本文将R矩阵表示成信道相对可用率Pn, m以及信道衰落因子hn, m两个因素的函数, 如式 (9) 所示:

其中, rn, m表示次用户n在信道m上获得的实际效益值, 即综合考虑了两个因素后的效益。因此, 其目标函数为:

本文采用协作式最大化总带宽 (CMSB) 准则[2], 使得节点可取得协作最大总效益, 标记为labeln*:

其中Dn, m为信道m上与用户n有干扰的用户个数,

本文所提出的基于信道性能的CSGC频谱分配算法流程如图2所示。

3 算法仿真与性能分析

本节分析比较未考虑信道性能的CMSB算法[2], 只考虑信道利用率[6]的方法和本文提出的基于多种信道性能的频谱分配算法在切换概率、误码率、实际总效益等方面的性能。

取信道数目M=10, 次用户数目N为1~10, 每个信道随机生成500组次用户到达率和离开率, 0≤λm, μm≤1, m=1, 2, …10, 次用户n (1≤n≤N) 的业务量传送时间都设为500 s。图3 (a) 、 (b) 分别给出了参考文献[2]、参考文献[6]算法以及本文算法的切换概率和误码率。实验取200次仿真结果的平均值。从图3可以看出, 虽然本文算法的切换概率略低于只考虑切换概率的信道选择算法, 但误码率明显低于后者。

取信道数目M=10, 次用户数目N为10, B、L、C矩阵根据参考文献[10]附录产生, 图4 (a) 、 (b) 分别给出了本文算法与参考文献[2]和参考文献[6]算法在50次试验中实际效益值的比较。从图中可以看出, 本文算法的实际效益值高于后两种算法。

本文主要研究信道状态转换概率、衰落因子以及次用户通信时间对整个系统实际总效益的影响。仿真结果表明, 该算法在降低系统整体切换概率、误码率的同时, 提高了系统实际总效益。

摘要：频谱分配是认知无线电的关键技术之一, 各授权信道的可用概率与授权用户的到达率以及次用户业务量传送时间有关, 并且实际效益还与该信道的衰落因子相关。提出了基于以上信道性能的CSGC频谱分配算法, 该算法通过优先分配相对信道利用率高、信道衰落小的信道, 达到最大化实际总效益的目的。仿真结果表明, 该算法是有效的。

关键词：相对信道利用率,认知无线电,信道衰落因子,CSGC

参考文献

[1]Federal Communications Commission.Spectrum Policy Task Force Report[R].ET Docket, 2002, 02-135.

[2]Zheng Haitao, Peng Chunyi.Collaboration and fairness in opportunistic spectrum access[C].IEEE International Conference Communication.May 2005:3132-3136.

[3]Zhang Dongmei, Xu Youyun, Cai Yueming.Liner water filling power allocation algorithm in OFDMA system[J].Journal of Electronics&Information Technology, 2007, 29 (6) :1286-1289.

[4]DIRK H H.Ensemble modem structure for imperfect transmission media[P].U.S.Patent 4679227, 1987, 4731816, 1988 and 4833796, 1989.

[5]HAUSI C, HAGENAUER J.Iterative network and channel decoding for the two-way relay channel[C].Proc.of IEEE ICC’06.Istanbul, Turkey:IEEE, 2006:11-18.

[6]张伟卫, 赵知劲, 王海泉.一种结合信道性能的频谱分配算法[J].现代电子技术, 2010, 33 (23) :49-51.

[7]TEVFIK Y, HUSEYIN A.A survey of spectrum sensing algorithms for cognitive radio applications[C].in Proc of IEEE Conference on Communications, 2009:116-122.

[8]Peng Chunyi, Zheng Haitao, Zhao Ben Y.Utilization and fairness in spectrum assignment for opportunistic spectrum access[C].IEEE International Conference on Communications (ICC) , 2006, 11:555-576.

[9]HAUSL C, DUPRAZ P.Joint network-channel coding for the multiple-access relay channels[C].Proc.of Intern.Workshop on Wireless Ad-hoc and Sensor Networks (IW-WAN) , New York, USA:IWWAN, 2006:19-22.

种群规模对遗传算法性能的影响 篇9

遗传算法 (GA) 由美国Michigan大学的Holland教授于1975年首先提出, 后经De Jong、GoldBerg等人改进推广, 广泛应用于各类问题。它是一种模拟自然界生物进化过程与机制的全局概率优化搜索方法。在经典的遗传算法中, 种群的规模始终是固定不变的, 这与实际的生物进化过程不符。在人类或其他生物进化的过程中, 种群的规模的发展是有其一定的规律的, 不可能固定不变。随着人类或其他生物对环境的适应度的提高, 种群的规模也在逐步调整。经典的遗传算法采用固定的种群规模, 使得种群不能根据其总体适应度来动态地调节其规模, 不能很好解决全局收敛和收敛速度间的突出矛盾, 在很大程度上影响了遗传算法的收敛速度和解的质量。

本文主要通过实验研究种群规模 (PS) 对遗传算法性能:进化代数 (EGN) 、收敛时间 (CT) 和全局搜索能力 (GSC) 的影响。通过四个经典函数的测试, 结果表明种群规模对遗传算法各个性能的变化均有上升或下降的变化。

从直观上看, 当种群规模增大时, 算法的计算时间, 也就是收敛时间将会增大;而种群规模如果增大了, 那么算法收敛到最优解的可能性就会增大, 即全局搜索能力会增强;再者, 当种群规模增大了, 在解空间中搜索时, 可以在相对较少的代数中找到最优解, 那么进化代数也随着种群规模的增大而变小了。

一、算法步骤

Step1.随机初始化种群, P={xi i=1, 2, …, μ}, μ是种群规模, 每一个个体xi= (x1i, x2i, …, xni) 是决策变量的维数;

Step2.利用适应度函数来评价个体适应度;

Step3.若满足收敛条件, 则停止迭代并给出最优个体, 否则进行下一步;

Step4.进行遗传操作:

Step4.1.实行精英策略, 保留本代一定比例的最优个体至下一代;

Step4.2.利用线性排序选择方法进行选择, 采用两点线性交叉, 执行均匀变异操作。

二、测试函数

试验所用的四个函数都是要找出他们的最大值。函数定义如表1。 (表1)

三、实验结果及分析

在以下试验中, 进化参数设置如下:对每个种群设置收敛精度为ε=0.001, 选择概率为Ps=0.25, 交叉概率为Pc=0.7, 变异概率为Pm=0.05, f1、f3进化代数为800, f2、f4最大进化代数为2000。

1、收敛代数 (EGN) 和种群规模 (PS) 之间的关系如表2所示。

(表2、图1) 从表2中可以看出进化代数随着种群规模的增加而降低, 但不同的函数具有不同的下降速率曲线, 并且呈波动型下降, 而不是单调的下降。尤其是对Rosenbrock函数f4来说, 它的收敛代数波动幅度最大。

2、收敛时间 (CT) 和种群规模 (PS) 之间的关系如表3所示。

(表3) 由表3可以看出收敛时间在开始阶段下降, 经过某个特定值之后, 时间随着种群规模的扩大而增加。

3、

为了测试全局搜索能力和种群规模的关系, 我们把算法分别独立运行30次, 得到全局最优解的总次数为k, 利用k/30表示全局搜索能力。全局搜索能力 (GSC) 和种群规模 (PS) 的具体关系如表4所示。 (表4) 从表4可以看出, 随着种群规模的扩大全局搜索能力会增强, 但可以看出也不是单调的。

四、结论

在研究了种群规模对GA的进化代数 (EGN) 、收敛时间 (CT) 、全局搜索能力 (GPS) 的影响之后, 我们可以得到如下结论: (1) 当种群规模增大时, 进化代数降低; (2) 当种群规模增大时, 全局搜索能力增强; (3) 当种群规模增大时, 收敛时间在初始阶段会下降, 而当种群达到某个规模后, 收敛时间又会增加。同时, 上述变化都不是单调增加或者减少的, 而是随着种群规模的增大, 改变是波动或震荡的; (4) 对于四个不同的函数, 各个性能的变化率都不相同, 有不同的上升或下降速率, 也就是说种群规模对算法性能影响的大小跟函数的选取也有关。

参考文献

[1]李敏强, 寇纪淞, 林丹等.遗传算法的基本理论与应用[M].北京:科学出版社, 2004.

[2]王力, 侯燕玲.基于遗传算法通用试题库系统研究[J].微计算机信息, 2008.5.3.

信噪比盲估计算法性能比较 篇10

文献[2][3]中使用极大似然估计法,将信号的信噪比估计转变为信号幅度值估计,文献[4][5]中利用接收信号的高阶矩估计信噪比。上述算法在各自特定的条件下非常有效,但大多在非协作通信的条件下不再适用,而且有些需要进行较大维数的矩阵运算,计算量大,难以满足实时性要求。

本文提出了一种基于功率谱差分的信噪比盲估计算法,并将其与基于奇异值分解的信噪比盲估计法在性能上作了详细比较,进行了仿真验证。可以发现,文中提出的算法具有明显的计算简单、估计精确等优点。

在高斯白噪声背景下,对于接收到的信号,可表示为:

其中,x(n)是信号分量,y(n)是观测信号,σ(n)为白噪声,N是采样得到的观测数据长度。

1 基于奇异值分解的信噪比盲估计

由(1)式,可以估计接收信号的m阶自协方差矩阵:

其中,

Cy是非负定矩阵,根据信号分量与噪声分量间的不相关性,可对其进行奇异值分解:

其中,U=[u1,u2,…,up,up+1,up+2,…,um]为Cy的特征空间,DP是由自协方差矩阵Cy的特征值构成的对角阵。

由上式可以看出,σ2为Cy的m-p重特征值,且是最小的m-p个特征值,将它们所对应的特征向量所张成的空间Un=[up+1,up+2,…,um]称为噪声子空间,将由剩余的特征值对应的特征向量所张成的空间Us=[u1,u2,…,up]称为信号子空间。此时接收信号的信噪比可以由特征值表示为:

但实际上,由于信号能量与噪声能量的交叉,使得部分信号能量分布在噪声子空间内,从而导致通过奇异值分解得到的噪声子空间的特征值并不是相等的m-p个值,此时由MDL准则[15],可估计信号子空间的维数,过程如下:

(1)首先对由式(4)得到的特征值进行排序,设λ1≥λ2≥…≥λm定义球形检验函数:

(2)定义MDL目标函数:

其中,K为利用信号遍历性计算信号期望值时的数据长度。信号子空间的维数可估计为:

(3)估计出信号子空间维数后,可估计噪声的功率:

(4)由式(5)修正后可求得信噪比的估计值:

2 基于功率谱差分的信噪比盲估计

在进行信号实时监测中,较大维数的矩阵运算给应用带来了困难,本章从频域出发,利用白噪声功率谱的平坦特征,提出一种基于功率谱分析的信噪比盲估计算法。

由式(1),可估计出接收信号的功率谱:

图1是某一含噪信号的功率谱,从图1可以看出,信号分量存在的频率段,功率谱幅度呈现明显的上凸,从几何学的角度,可以利用导数知识将功率谱图变化最快的地方提取出来,即近似对应着功率谱图中信号分量上凸段的端点。对图1中的功率谱进行前向差分:

其中,nfft是功率谱估计中FFT的长度。得到结果如图2所示。

由图2可以看出,在信号分量出现的频率段端点,功率谱差分图出现了明显的峰值,信号分量频段两端,分别对应着正峰和负峰,因此,实施功率谱差分后,可以设置门限,分别进行正负谱峰搜索,得到信号分量对应的频段估计。考虑到信号的拖尾性,为了保证取得信号分量能量的完整性,对于正谱峰,取其左侧第一个过零点为该信号分量频率段的左端点,对于负谱峰,取其右侧第一个过零点为该信号分量频率段的右端点。为了使功率谱差分后的峰值明显,要求估计出的功率谱尽可能平滑,因此,本文选择Welch法估计功率谱。

令估计出的信号分量频率段左右端点分别为ωL和ωH,则该信号分量的带宽可估计为:

其中,fs为采样频率。该信号分量的中心频率可估计为:

考虑到白噪声谱的平坦性,整个频段内的噪声功率可以利用非信号频率段的功率谱进行估计:

信号分量的功率可估计如下:

进而求得信噪比:

3 实验与仿真分析

实验信号为一段样本长度N为32768的QPSK复信号,采样频率为80MHz,其中QPSK信号的载波频率为20MHz,码速率为5MHz,成形滤波器为升余弦滤波,其滚降系数为0.5,信道为高斯白噪声信道,噪声功率为3dB,信噪比变化范围为-10~10dB,信号的协方差矩阵维数m取值为64(一般取值为50~100),计算期望值时的数据长度K取为N/2。利用Welch法估计功率谱时,每段数据长度L取为256,FFT长度与数据长度一致,段与段之间的重叠度取为50%。

3.1 算法复杂度比较

对于奇异值分解法估计信噪比,包括自协方差矩阵、奇异值分解、MDL法估计信号子空间维数和信噪比估计4个主要计算部分,如表1中所列。其中,决定计算复杂度的是奇异值分解,因此,基于奇异值分解的信噪比盲估计法的运算量为max,m是自协方差矩阵的维数,N是样本数据长度。

对于本文提出的基于功率谱差分算法,包括Welch法估计功率谱、功率谱差分、谱峰搜索和信噪比估计4个主要计算部分,如表2中所列。其中,决定计算复杂度的是利用Welch法估计功率谱及信噪比计算,运算量为o(N),N是样本数据长度。

由表1、表2可知,本文提出算法与基于奇异值分解的信噪比盲估计算法相比,具有更小的计算量,易于实现,能够更好地满足实时性要求。

3.2 算法性能比较

Mente Carlo仿真500次,得到两种算法在-10~10dB范围内的盲信噪比估计偏差与均方误差分别如图3、图4所示。

由图3可以看出,与奇异值分解法相比,本文提出算法在给定范围内的信噪比估计偏差一直较小,两者大约相差3dB。由图4可以看出,随着信噪比降低,两种算法估计出的信噪比均方误差均在逐渐增大,但本文算法估计出的信噪比误差波动小,在稳定度上较奇异值分解法有很大提高,算法的稳健性更强。

4 总结

本文介绍了基于奇异值分解的信噪比盲估计算法的基本原理,针对矩阵分解的计算复杂性,提出了一种基于功率谱差分的信噪比盲估计算法。研究表明,该算法与前者相比,不但具有较小的计算量,而且信噪比估计精度及稳定度均有较大提高。另外,该算法还适用于频域不重叠的单通道多信号的信噪比盲估计,具有较强的工程应用性。

摘要：为了实现非协作环境下的通信信号信噪比估计,本文在功率谱分析的基础上,提出了一种基于功率谱差分的信噪比盲估计算法,并将其与传统的基于奇异值分解的信噪比盲估计算法进行了比较。理论与仿真结果表明,与传统方法相比,本文提出的算法不但复杂度低,而且在低信噪比情形下仍具有较高的估计精确度和稳健性。

关键词：信噪比盲估计,异值分解,功率谱差分,Welch法

参考文献

[1]唱亮,汪芙平.非协作通信中的盲信噪比估计算法.通信学报,2008,29(3):76-81

[2]隋丹,葛临东.一种新的基于改进PASTd的中频信号盲信噪比估计算法.电子与信息学报,2007,29(7):1657~1661

[3]孙钢灿,安建平,杨杰,杨凯.非协作通信中的信噪比估计算法.北京理工大学学报,2009,29(8):708-712

[4]彭耿,黄知涛,陆凤波,姜文利.中频通信信号信噪比的快速盲估计.电子与信息学报,2010,32(1):102-106