并行入侵检测系统

并行入侵检测系统（精选7篇）

并行入侵检测系统 第1篇

软件脆弱性也称漏洞,是软件在设计与实现过程中能导致安全事故的缺陷和不足。脆弱性的存在本身并不影响软件的功能,不会造成任何安全事故。但是网络攻击者可以利用软件脆弱性,在未授权的情况下访问或破坏计算机系统,造成严重的安全事故。当前,普遍使用的符号执行技术受限于运算复杂度和计算能力,无法实现大规模应用。为此本课题设计并实现了基于动态符号执行的面向软件脆弱性并行检测系统的并行调度模块和通信模块,课题以此为牵引,对符号执行技术进行了研究,对基于符号执行技术的KLEE平台的搭建和使用进行了详细介绍,并对KLEE的测试结果进行了详细分析。

1 相关研究

符号执行是指不通过执行程序,用符号作为程序的输入,将程序进行模拟执行,从而来进行相关分析的技术。符号执行可分为静态符号执行和动态符号执行。

静态符号执行包括两类,分别为过程内分析和过程间分析,其中过程间分析又称为全局分析。过程内分析的概念是,在进行分析的过程中,只分析单个过程的代码。而全局分析的概念是,不仅单个过程中的代码进行分析,并且将整个程序的代码的上下文进行敏感分析。其中上下文敏感分析的概念是,在开始对当前函数进行内分析时,需要对当前的函数间调用信息和环境信息等进行分析和考虑。全局分析和过程内分析是相对独立又相互依赖的关系。

2 基于动态符号执行的软件脆弱性并行检测系统

2.1 系统总体架构

通过前期对符号执行技术原理和应用的研究,我们对理解基于动态符号执行的软件脆弱性并行检测系统奠定了基础。基于动态符号执行的软件脆弱性并行检测系统采用并行技术进行软件脆弱性检测,使系统不仅具有高代码高路径覆盖率,同时大大提升了软件脆弱性检测的效率。

2.2 系统功能概述

调度服务器 :调度服务器是系统的中心,数量为1个,工作于Windows 2003以上环境,负责与各个子系统通信,向子系统发布命令,并接收反馈。

总控中心 :总控子系统直接与用户进行交互,是系统对外的接口,用户的所有操作通过总控中心进行实现。

子系统 :子系统的数量大概在500-1000个,分为3种类型,包括测试子系统、分析子系统和求解子系统,支持Windows XP、Windows 7和Ubuntu 12.04LTE环境。每个子系统分为Agent部分和Execution部分,其中Agent部分负责子系统与外界的通信功能,Execution部分负责具体任务的执行的功能,如三类子系统的具体需要完成测试、分析和求解的功能。

3 并行调度模块设计与实现

3.1 算法设计思想

基于动态符号执行的软件脆弱性并行检测系统的并行调度问题是系统研发过程中的核心问题之一。调度服务器如何向三类子系统分配执行任务,对整个并行系统的执行效率影响极大。本章设计与实现的并行调度模块主要解决了三类子系统的调度问题和三类子系统任务调度问题。

3.2 子系统调度算法

并行系统共有测试子系统、分析子系统和求解子系统三类子系统,每类子系统的数量有多个。当任务到达,调度Server如何在每类子系统中选择执行任务的单位,即是子系统调度算法需要研究的问题。

3.3 任务调度算法

一个测试样本在经过测试子系统执行后,生成多个tracefile交由多个分析子系统分析,多个分析子系统分析得到的约束条件在多个求解子系统求解后得到多个新的测试用例,分别代表了不同的执行路径。分析子系统在分析多个tracefile时按照什么顺序选择文件?测试子系统在下一轮执行时如何选择测试样本?这个问题即是任务调度问题,任务调度问题关系到整个系统的路径覆盖率和执行效率。tracefile和测试样本的选择选择实质上是遍历路径的选择,任务调度算法即是对tracefile和测试样本的选择方法进行研究。

3.4 实现方案

在实现子系统调度和任务调度的过程中,需要对子系统信息、任务信息和任务内容进行存储。为了解决存储问题,系统在具体实现时,使用Hadoop分布式存储系统对各个子系统执行的任务内容进行存储,系统使用Oracle数据库对各个子系统的注册信息和状态信息以及各个子系统执行的任务基本信息进行存储。

4 总结与展望

可扩展并行入侵检测体系结构 第2篇

目前, 网络安全采用的主流方案是防火墙与入侵检测系统的联动部署。该方案通过数据分析对网段中多个主机系统进行检测, 同时其提供的主动网络保护更有利于提高整个内网的安全性。随着信息技术的发展, 传统的入侵检测系统已经不能满足人们对检测效率和可靠性的要求。一方面, 随着网络带宽飞速提高, 入侵检测需要分析处理的网络流量大大增加;另一方面, 网络攻击方式的层出不穷, 导致检测引擎需要匹配的特征库日益增大, 单个数据包的处理效率因而下降。

基于上述背景, 本文创新性地提出了一种可扩展并行入侵检测体系结构, 该结构利用了分发节点间和探测节点间的并行处理优势, 同时设计了合理的流量划分策略来保证并行处理过程中的负载平衡。通过该体系结构, 可以突破传统入侵检测系统面临的网络流量激增、规则库不断膨胀两大性能瓶颈。论文第2节阐述了实现方案, 主要包括介绍并行入侵检测体系结构, 流量划分策略。论文第3节进行性能测试, 第4节为结论。

2 设计方案

2.1 可扩展并行入侵检测体系结构

基于传统的检测架构和并行处理思想, 本文创新性提出了一套可扩展并行入侵检测体系结构——SPIDA (Scalable Parallel Intrusion Detection Architecture) , 该体系结构如图1所示。

SPIDA架构主要分为四个部分:分发模块, 检测分析模块, 管理模块以及负载反馈模块。分发模块根据流量划分策略将到达的报文映射到一个或多个检测引擎, 而检测分析模块则对接收到的报文进行相应的检查和分析。管理模块提供用户接口, 实时显示各检测引擎的负载情况和状态信息, 同时提供结果统计和相关配置等功能。为了反馈负载信息, 保证各检测引擎间的负载均衡, SPIDA在每个检测引擎上使用负载反馈模块来监测该检测引擎的当前负载, 并将负载情况传给分发模块, 分发模块再根据相应的负载均衡算法, 保证系统的负载均衡情况。

分发模块:分发模块由动态分发和负载均衡两个部分组成。动态分发部分按照一定的流量划分策略将接收的报文映射到一个或多个检测引擎。负载均衡部分负责接收每个负载反馈模块发来的负载信息, 然后对每个端口上的报文量进行调整。

检测分析模块:检测分析模块包括多个检测引擎, 检测引擎可以根据需求动态增加, 充分体现了该架构的可扩展性。检测引擎检测分析由分发模块分发到自身的相关数据流。检测引擎的分析规则对检测结构有重要影响, 在这方面, 本文选择为每个检测引擎配置完整的规则集, 这种方案实现简单, 并且每个攻击引擎都具备检测所有攻击行为的能力。

管理模块:管理模块是系统与用户之间的接口, 本文利用Java语言开发了一整套管理操作界面。为了提高系统的性能同时降低结构的复杂性, 本文将管理模块做在一个检测机器上, 其他检测器与该检测器进行通信, 从而使管理模块能及时掌握系统的状态信息, 便于用户管理。管理模块主要提供权限管理、功能管理、日志管理三大功能, 其中主要的功能管理模块可以进行负载检测、检测结果统计和相关配置。

负载反馈模块:负载反馈模块在SPIDA中是转发模块和检测模块之间的反馈环节, 它实时监控各个检测引擎的负载情况, 并将负载信息反馈给模块, 模块再根据负载均衡算法, 动态地调整数据包在各个检测引擎之间的分发。而衡量负载的指标与用户在不同条件下的需求有很大关系, 所以采用在管理模块配置的方法来动态设定衡量负载的指标。

2.2 流量划分策略

在实现证据保持时, 本文主要基于Hash映射思想设计流量划分策略。其主要思路是对报文头的部分内容进行哈希函数, 由相同的检测引擎处理特征相同的报文流。

一般而言, 我们会采用单级映射, 主要对<源IP地址, 源端口号, 目的IP地址, 目的端口号, 协议类型>这五个元组进行Hash映射, 如果Hash值大于检测引擎数量, 则取模, 从而得到处理该报文的检测引擎。

本文发现只采用单级hash, 在检测引擎上很容易发生过载。因此在单级哈希的基础上又增加了一级哈希, 尽可能将报文均匀分到多个检测引擎上, 从而缓解检测引擎的负载。

这是本文所设计的两级Hash映射的流量划分:

1) 首先配置第一级哈希的报文域, 以检测单攻击源为例, 本文将采用的报文域是<desIP, srcIP>, 将目的IP地址和源IP地址相加的结果Hash到0—255这256个数上。

2) 然后在将这256个数哈希到3个检测引擎上 (这里假设共有3个检测引擎) 。

负载均衡的关键是实现报文流的转移, 并且在面对大报文流的情况下, 算法一定要满足两个条件: (1) 有效选择报文目的端口; (2) 报文转移速度要快。对此, 本文在Netmagic实验平台上设计了硬件负载均衡算法, 有效利用了硬件算法效率高的优势, 同时通过队列实现了在一个时钟节拍内的报文转移, 这大大提高了算法的效率。

下面是硬件算法的所实现的报文转移过程:

将报文通过一级哈希得到的哈希值0-255, 在分发模块内建立一个路由表, 这个路由表的大小为256, 其表项是这256个报文的哈希值和其所对应的端口号, 报文的转发到哪个端口就是通过查阅这个路由表得到的, 并且这个表也是动态变化的。在初始化时将256个哈希值分配到了3个检测引擎, 本文给每一个端口建一个大小为256队列, 每一个队列里存储的就是该端口所转发报文的哈希值。初始化时每个队列里分别有85, 85, 86个值。如图2所示。

当某个检测引擎发生过载时, 该检测引擎上的负载反馈模块就会发一条消息给分发模块, 告诉分发模块该检测引擎发生过载了, 分发模块则会查阅该检测引擎的端口的队列, 由于队列是遵循先进先出原则的, 因此本文会把该队列前端的哈希值弹出来, 然后将该哈希值放进下一个端口队列的后端。如图3所示。

最后将此哈希值及其转移到的端口号传给路由表, 修改此哈希值所对应的端口号, 完成报文流转移。如图4所示。

3 性能测试

3.1 环境搭建

性能测试主要包括测试系统证据保持能力, 系统的负载均衡能力, 高速网络环境下检测能力。测试环境搭建图如图5所示。

网络环境:Netmagic网络实验平台, UTP非屏蔽双绞线

攻击机环境配置如表1所示。

检测器环境配置如表2所示。

3.2 测试实施

3.2.1 证据保持测试

背景流:TCP报文;源和目的IP在192.168.100.0~192.168.100.255之间变化;源、目的MAC地址不变;端口随机变化;报文大小为100byte;流数=1条。使用IXExplorer发送。

攻击包:SYN Flood攻击包。使用SmartBits发送。

检测结果如表3所示。

传统入侵检测系统的漏报率在20%—30%之间, 而本文设计的基于两级哈希的流量划分方案使得漏报率降到9.2%。两级哈希算法的证据保持能力基本能满足人们对入侵检测准确率的要求。分析认为, 导致漏报率的部分原因是不同报文流之间有一定的相关性, 如果能够实现检测引擎之间的信息交流, 进行综合处理, 还能进一步提高检测的准确性。

3.2.2 负载均衡能力测试

背景流:TCP报文;源, 目的IP在

192.168.100.0~192.168.100.255之间变化;源、目的MAC地址固定;端口随机变化;报文大小为100byte;流数=1条。使用IXExplorer发送。

攻击包:SYN Flood攻击包。使用SmartBits发送。

现象:

1) 初始状态, 由于报文的随机性, 各检测器模块上的负载量差距比较大, 检测器1出现过载现象, 可以通过管理端观察到, 如图6所示。

2) 四分钟后, 三个检测器上的负载量差距不大, 并且都恢复正常, 如图7所示。

根据算法, 哈希值相同的数据包被分发到同一个检测器。但当该检测器负载超过预设的阈值时, 数据包被调度到其他的检测器, 从而使检测器的负载状态恢复正常。

3.2.3 高速网络环境下检测能力测试

背景流:TCP报文;源、目的IP在

192.168.100.0~192.168.100.255之间变化;源、目的MAC地址固定;端口随机变化;报文大小为100byte;流数=1条。使用IXExplorer发送。

攻击包:SYN Flood攻击包.使用SmartBits发送。

结果如表:

从上述结果中可以发现, 随着网络带宽的增多, 丢包率虽然在增加, 但是增加的幅度不大。因此, 本文的可扩展并行入侵体系结构在高速网络环境中有很高的可靠性。

4 结束语

本文提出了一种可扩展并行入侵检测系统, 其利用分发节点间和探测节点间的并行处理优势较为有效的解决了在大数据环境下流量瓶颈的问题。通过在实验平台上实现了自主设计的基于两级哈希映射的流量划分算法和负载均衡算法, 使系统的证据保持和负载均衡都得到了有效保证。通过测试结果, 系统在高速网络环境中漏报率和误报率较低, 有很高的可用性和有效性。

并行入侵检测系统 第3篇

近年来, 计算行业正在从只使用CPU的“中央处理”向CPU与GPU并用的“协同处理”发展。为了打造这一全新的计算模式, NVIDIA公司开发了一种称为CUDA (Compute Unified Device Architecture, 统一计算设备架构) 的通用并行计算架构, 该架构使得GPU能够解决复杂的计算问题。得益于CUDA所带来的并行计算解决方案, 并行碰撞检测算法的研究迎来了新的机遇。并行计算是一种能够有效提高碰撞检测速度的方法, 经过分析研究, 提出了一种基于CUDA的并行碰撞检测算法。

1 并行碰撞检测算法的基本思想

我们所提出的是一种基于层次包围盒的并行碰撞检测算法。层次包围盒的碰撞检测算法由于具有较好的性能, 适用于复杂环境中的碰撞检测, 因而受到了广泛的研究。层次包围盒方法是利用体积略大而形状简单的包围盒把复杂的几何对象包裹起来, 在进行碰撞检测时首先进行包围盒之间的相交测试;如果包围盒相交, 再进行几何对象之间精确的碰撞检测[2]。在单处理器的情况下, 首先必须对两个需要进行碰撞检测的对象分别生成层次包围盒树 (简称包围树) , 再通过双重递归遍历两棵包围树来确定需要进行检测的部分。如果某个对象在模拟过程中发生位移或形变, 则必须在下一次进行碰撞检测前对该对象的包围树进行更新, 而更新过程依然是一个遍历树的过程。由此可见, 当一个对象含有的基本几何元素越多时, 生成包围树的时间越长, 并且包围树的深度越大, 遍历所需要的时间也更长。为了减少碰撞检测的系统消耗, 则利用并行的方法来生成包围树和避免双重递归遍历。根据分析, 层次包围盒的碰撞检测是一种典型的单指令多数据流[3] (Single Instruction Multiple Data, 简称SIMD) 问题, 即处理器多次执行重复的代码, 每次处理不同的数据。对于这类问题, 可以使用多个处理器, 每个处理器同一时刻执行相同的代码但处理不同的数据, 从而实现并行化。

1.1 并行生成包围树

生成一棵包围树有自顶向下和自底向上两种方法。自底向上生成包围树的方法与霍夫曼编码相似。单个处理器完成这项工作的方法是:

1) 根据给定的n个基本几何元素的包围盒构成n棵二叉树的集合F={T0, T1, , Tn}, 其中每棵二叉树Ti中只有一个根结点, 其左右子树均为空。

2) 从F中取出Ti, 用贪婪算法在其余的二叉树中找到与Ti距离最近的Tj, 将Ti与Tj作为左右子树构造一棵新的二叉树, 并且新二叉树根结点包围盒大小由其左右子树决定。重复该过程直到F中所有的二叉树被处理完。该过程的时间复杂度为O (n2) 。

3) 删除F中原有的二叉树, 将新生成的树全部加入F中。

4) 重复 (2) 和 (3) , 直到F只含有一棵树为止。

上述算法的时间复杂度为O (n2log2n) 。从生成树的过程来看, 处理器重复做相同的工作来处理不同的数据, 属于SIMD问题, 因此, 可以使用并行的方式。

提出的并行生成包围树算法的基本思想是:

1) 根据n个基本几何元素的包围盒构成n棵二叉树的集合F={T0, T1, , Tn}, 其中每棵二叉树中只有一个根结点, 其左右子树均为空。

2) 从F中取出Ti, 并行计算其余根结点到Ti的距离, 再用并行的方式找到与Ti距离最小的根结点Tj, 将Ti和Tj加入到集合H={S0, S1, , Sn}中。重复该过程直到F中所有的根结点全部加入H中, 其中S2i与Ssi+1之间的距离最小。

3) 用多个处理器undefined对有序集合H中的根结点进行处理, 由处理器Pi将H中S2i, S2i+1作为左右子树构造一棵新的二叉树。

4) 删除F中原有的二叉树, 将新生成的树全部加入F中。

5) 重复 (2) 、 (3) 和 (4) , 直到F只含有一棵树为止。

并行生成树的过程如图1所示。对于有n个根结点和p个处理器的情况, 该算法在计算根结点之间距离的时间复杂度是undefined;在上述算法 (2) 中, 总共需要进行undefined次查找, 并行查找最小值的时间复杂度为undefined, 那么得到集合H所需要的时间复杂度为undefined;在生成树时, 并行算法的时间复杂度为undefined。整个算法的时间复杂度为undefined, 与单处理器所采用的算法相比较, 当p越接近n时, 并行算法的效率越好。

1.2 并行遍历包围树

单处理器进行碰撞检测时需要对两棵包围树进行双重递归遍历。假设对象A与B进行碰撞检测, 若树A根结点与树B根结点的包围盒相交, 则树A向下遍历, 当到达树A的某个叶结点时, 用该叶结点遍历树B, 如果能到达树B的叶结点, 再进行进一步的几何元素相交测试。假设对象A的包围树含有n个结点, 对象B的包围树含有m个结点, 那么完成碰撞检测的时间复杂度为O (nm) 。

为了避免双重递归遍历所带来的系统消耗, 减少遍历的次数, 我们的想法是只生成对象A的包围树, 在碰撞检测时, 只为对象B的所有基本几何元素生成包围盒, 然后由多个处理器分别处理每个包围盒与树A的遍历问题。该方法的时间复杂度是undefined是处理器个数) , 与并行生成包围树一样, 当p越接近n时, 算法的效率越好。

2 并行碰撞检测算法的实现

自2006年NVIDIA公司推出统一渲染架构的G80核心以来, 可编程流处理器已取代原有的固定管线流程成为当今GPU发展的模式。G80核心拥有128个Streaming Processor (流处理器, 简称SP) , 每8个SP被划分为1个Streaming Multiprocessor (流多处理器, 简称SM) , 每个SM可容纳768个活动线程, 那么一个G80核心便可以同时建立12280个活动线程。而NVIDIA之后推出的G200核心, 拥有240个SP, 每个SM可容纳1024个线程, 能够同时建立的活动线程数更是高达30720个[4]。由此可见, GPU为并行计算提供了一个很好的解决方案。

CUDA技术是一种基于NVIDIA图形处理器的并行计算体系架构, 并使用标准C语言作为其编程语言。CUDA程序分为在host执行和在device执行两个部分, host就是传统的CPU, 而device就是支持CUDA的GPU。在执行CUDA程序时, host将需要并行计算的数据在内存中准备好, 传入显存中由device进行处理, 数据处理完成后再从显存传回内存中供用户使用。

根据所提出的算法, 首先是生成对象的包围树。定义一个基本几何元素的包围盒为一个含有包围盒顶点坐标、几何元素顶点坐标的结构体。由host为对象所有基本几何元素生成包围盒并存储在内存中的一维结构体数组中, 根据几何元素个数计算出包围树深度depth及每层结点的个数。假设包围树每层结点个数分别为ni, ni-1, , 2, 1 (i=depth-1) , 在显存中分配大小为ni+ni-1++2+1的结构体数组用于存储生成的包围树。将包围盒数组从内存中传入显存后, 在device上为数组中每一个元素建立一个对应的线程, 由这些线程完成以下工作:

1) 以数组中指定元素对应的包围盒作为目标, 计算其余包围盒与它之间的距离。该过程可以由多个线程并行完成, 每个线程负责与其对应的包围盒的处理。

2) 将包围盒数组调整成为有规则的序列, 使得数组下标为2i和2i+1 (i∈N) 的两个包围盒距离最近。这一过程的方法如图2所示。在Step 1中, 指定数组中第一个元素T0为目标包围盒, 计算其余包围盒到T0的距离并用并行查找最小值的方法找到与T0距离最近的包围盒。查找结束后, 与T0距离最近的包围盒将被移至数组中T1的位置。再指定T2作为目标, 用相同的方法找到与T2距离最近的包围盒。这一过程将被重复执行undefined次, 直到数组被调整完为止。

这里使用的并行查找最小值的方法如图3所示。将含有n个元素的数组分成n个只有一个元素的子序列, 使用undefined个处理器对两个相邻子序列进行合并, 得到undefined个新的子序列, 在合并时将对比两个子序列中第一个元素的值, 将较小的值作为合并后子序列中第一个元素的值, 再对新得到的undefined个子序列两两合并, , 如此反复直到合并成一个序列为止。整个过程结束后, 数组的最小值将位于数组第一个元素中。

3) 由多个线程生成包围树每层结点, 并存储在事先分配好的数组中。该过程如图4所示。

假设对象A与B进行碰撞检测, 并且device已为对象A生成包围树, 那么只需要为对象B所有基本几何元素生成包围盒, 用每个包围盒去遍历对象A的包围树。当host将对象B的包围盒数组从内存中传入显存后, 在device上建立与包围盒数目相同的线程, 由每个线程独立完成一个包围盒与包围树的遍历问题。由于CUDA不支持堆栈结构, 因此, CUDA线程深度遍历二叉树无法用递归或堆栈的方式实现。文献[5]中给出了一种模拟堆栈[5]的方法, 使得CUDA线程深度遍历二叉树得以实现。

3 实验结果

我们在中国科学院近代物理研究所的超级计算中心上对并行算法进行实验。该超算中心采用联想深腾7000G高性能服务器, 每个计算结点配置2个Intel Xeon 2.33GHZ处理器, 8G内存和4个G200核心, 能够获得50～150倍于通用CPU的加速计算效果。实验所用的碰撞场景如图5所示。在场景中水平放置一块布, 并固定布的两个角, 使其在受到重力作用自然下垂时呈悬挂状态。在布的下方放置一个球体, 使布在下垂过程中受到球体的阻挡而部分覆盖在球体上。当布覆盖在球体上并达到静止状态时, 开始统计并行算法和串行算法在生成包围树和遍历树所需要的平均时间。

表1是GPU并行算法和CPU串行算法执行时间的对比。从实验结果来看, 当问题规模较小时, GPU在生成包围树时所需要的时间比CPU要长, 其主要原因在于CUDA在组织线程、启动内核函数和分配任务所消耗的时间掩盖了实际的执行时间。在完成一次碰撞检测的时间方面, CPU随着问题规模的增大, 需要的时间也越来越长, 而GPU则只需要遍历一棵树的时间便能够完成碰撞检测, 较CPU有了明显的提高。

4 总结

在分析基于层次包围盒的碰撞检测算法的可并行性后, 提出了基于CUDA的并行碰撞检测算法。通过并行生成包围树和避免双重递归遍历包围树使得碰撞检测的效率得到了很大的提高。就此提出的并行生成包围树的思想, 同样可以用于更新包围树。实验证明, 在GPU上实现的并行碰撞检测算法能更好地满足实时性的需要。

摘要：碰撞检测是计算机图形仿真中的关键问题之一。尽管研究人员提出了许多优秀的碰撞检测算法, 但是随着仿真场景规模的增大, 在单处理器上实现的碰撞检测算法已经难以达到实时性的要求。因此, 当前研究的核心问题是如何提高碰撞检测的速度。在对已有算法研究分析的基础上, 提出了一种基于层次包围盒的并行碰撞检测算法。该算法的核心思想是用多处理器并行遍历层次树以避免单处理器需要两棵树相互遍历的情况, 并提出以并行的方式生成层次包围盒树来进一步提高算法效率。结合CUDA平台提供的并行计算解决方案, 整个算法在图形处理器上得以实现。结果表明, 该算法显著地提高了碰撞检测的速度, 满足实时性的需求。

关键词：计算机图形,碰撞检测,层次包围盒,并行,CUDA

参考文献

[1]石其.基于GPU的碰撞检测算法研究[D].长沙:湖南大学, 2009.

[2]马登武, 叶文, 李瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学报, 2006, 18 (4) :1058-1061.

[3]Michael J.Quinn.PARALLEL PROGRAMMING IN CWITHMPI AND OPENMP[M].北京:清华大学出版社, 2005.

[4]David B.Kirk, Wen-mei W.Hwu.Programming Mas-sively Parallel Processors[M].北京:清华大学出版社, 2009.

[5]曹家音.基于KD-Tree遍历的并行光线跟踪加速算法[J].科技传播, 2010 (17) :233-233, 224.

[6]熊一梅, 曾宪文, 陈一民.基于并行的快速碰撞检测算法的研究[J].计算机应用与软件, 2008, 25 (4) :48-50.

[7]Xavier Provot.Deformation Constraints in a Mass-SpringModel to Describe Rigid Cloth Behavior[J].In GraphicsInterface 1995, 18 (5) :147-154.

[8]陈?, 徐乃平.真实感布仿真中布与刚体的碰撞检测及修正[J].软件学报, 2001, 12 (12) :1874-1880.

[9]王晓荣, 王萌, 李春贵.基于AABB包围盒的碰撞检测算法的研究[J].计算机工程与科学, 2010, 32 (4) :59-61.

一种并行的新闻视频镜头检测方法 第4篇

随着互联网络的推广普及，新闻视频已经成为一种重要的媒体类型，已经在人们的工作和生活中成为不可或缺的信息载体。它具有信息量大，表现力强，内容丰富、直观、生动，从而受到人们的高度重视。为了使人们快速地获取需要的信息，迫切需要自动地建立索引结构，以进行新闻视频的组织、管理和检索。在新闻视频镜头检测中，基于直方图的算法是在基于像素比较的方法上发展而来的，它也是最为普遍的镜头边界的检测方法。

比较常见的新闻视频镜头检测算法有全局阈值法、双重阈值渐变镜头检测法、滑动窗口法、基于K-L变换的新闻视频镜头检测方法等。随着视频存储的分辨率越来越大, 每帧图像处理的耗时不断上升, 特别是在面对海量视频的积累, 数据规模的不断扩大, 以及检测算法的愈加复杂, 镜头检测的处理时间越来越长, 已经成为新闻视频分析和检索技术发展应用的瓶颈。所以, 在能够保证检测效果的同时, 缩短大量的镜头检测处理时间就非常重要。随着并行计算的发展和高性能集群平台的应用, 为问题的解决提供了可能。

1 全局阈值法

常见的镜头检测方法都是建立在相邻两帧直方图差值之上的判定准则，而这些准则最成熟最简单的就是文献所提的全局阈值法，而且其它算法均是全局阈值法的变种。所以，本文重点讨论全局阈值法的并行化处理和实现。

全局阈值法用于计算直方图差异的量度很多，主要有欧几里德距离法、直方图交集检测法和矢量间的夹角等，常用的是欧氏距离。

假设对于视频中的相邻两帧图像，其归一化直方图分别为直方图共包含N种颜色。则这两帧图像的直方图距离为：

其中，H i (k) ，H j (k) 分别为归一化直方图Hi, Hi在第k个颜色上的取值。如果前后两帧的颜色分布基本相同，那么上式的距离值几乎等于0;如果前后两帧的颜色分布完全不同，则结果正好相反。

在进行镜头边界检测时，顺序计算视频流相邻两帧的直方图差异，当此差异值大于某个预先设定的阈值时，说明两帧间发生了较大的变化，即认为它们之间存在一个镜头突变切换。

2 并行新闻视频镜头检测算法

2.1 一般主从式并行算法

根据新闻视频镜头检测数据庞大的特点，对视频分割的数据域分解并行为主的主从式并行算法。此方式旨在维持其原有程序易用性的同时，协同各节点，将任务完整均匀地分配到各个计算节点，在其内部封装对MPI的调用，从而使实现MPI环境的并行执行。此并行设计的优点是各从节点相互独立，最大限度减少了节点间的通信，提高程序在集群计算机上执行的并行效率。同时，在视频处理函数库上，采用Inter的跨平台计算机视觉OpenCV，其优化的代码编写对其执行速度带来可观的提升。

2.2 基于关键帧分割的主从式并行算法

从集群的执行效率上看，一般主从式并行方法达到了最高，但是由于视频压缩格式的不同，强制的非解压分割会导致在视频帧提取时帧信息的丢失。当节点数越多时，丢失越多，误差就越大。为此，本文在一般主从式并行思路的基础上，提出一种基于关键帧分割的主从式并行算法。

2.2.1 任务分配。

在进行任务划分时，视频的总帧数可能与节点数整除，也可能不整除。所以，在分配任务时，依照先从后主，从节点尽量处理相同帧数，主节点负责管理和处理剩余较少不规则帧数的原则，达到各节点的负载均衡。假如视频总帧数为S帧，共N个节点，总帧数远大于节点数。

1) 由N-1个从节点执行M+1帧：

2)主节点的计算任务小于每个从节点：

2.2.2 关键帧分割。

全局阈值法是建立在视频解压后直方图处理上，必须保证每个节点任务区段的视频解码正确。针对以上特点，在进行任务分配的并行设计时，既要各节点的负载均衡，又要考虑任务区段视频帧信息的完整性。

根据视频存储采用压缩技术，存在关键帧，而且关键帧间隔距离没有规则的特点。修改OpenCV中cvSetCaptureProperty () 函数的参数，使其在视频定位时，定位指针指向当前分配帧号的下一个关键帧位置。如图1所示：根据任务分配原则，假设节点N的开始执行的任务起始帧号为第95帧，但是第95帧不是关键帧，其压缩算法的关键帧号为第100帧，那么当前定位指针就自动指向第100帧，视频提取的起始帧为第100帧。

各节点把当前定位指针的帧号发送给前一个节点，作为前一个节点的任务结束帧号。依次递推，保证所有的帧均被遍历执行。所有从节点先发送后接收，主节点先接收后发送，防止MPI运行死循环。

2.2.3 算法步骤。

基于关键帧分割的主从式并行算法的主要步骤为：

(1)由主节点根据集群计算机的节点数计算各节点所执行的大概帧数，并把此帧数值广播到所有节点。

(2)节点间传输相关关键帧号，各节点获得任务的起始帧号和结束帧号。

(3)各节点处理所分配区段视频帧，计算相邻帧直方图差值并求和sum。

(4)主节点收集所有节点的sum值再求和。

(5)主节点计算所有相邻帧直方图差值的平均值并分发到所有节点。

(6)各节点根据阈值计算切换帧号和数量num并输出。

(7)主节点收集各节点num值求和并输出。

按照以上的原则和方法，主节点先全局笼统性分配，从节点再自我细节性调整，通过关键帧号的依次传递，各节点获得任务起始帧号和结束帧号，以及完整的视频解码信息。同时，各节点处理的帧数大致相等，确保了集群系统的负载均衡和程序执行的正确性。

3 测试

3.1 测试环境

实验测试平台由8个计算刀片机柜组成的高性能集群系统。整个系统包含80个计算刀片，每个刀片为双路6核结点，配置2颗6核心Intel Xeon Westmere EP 2.93GHz CPU X5670, 24GB DDR3内存，1个40Gbps的IB QDR接口。

3.2 加速比和并行效率

为了验证基于关键帧分割的主从式并行算法的正确性和通用性，从已建的视频库中选取比较有代表性的几类新闻节目作为实验对象。实验测试使用了80个节点，程序运行稳定，结果正确。进一步分析其并行加速比和并行效率。

加速比：Sp (28) T1/Tp

并行效率：Ep (28) Sp/p

其中，是串行程序执行耗时，是同样计算平台下，并行程序的执行耗时，为计算节点数。

图2并行加速比曲线图和图3并行效率曲线图表明：1.此主从模式的并行检测方法可以达到接近线性增长的加速比。所以，对于节点数具有良好的可扩展性。2.四类视频的加速比和并行效率变化接近一致，说明该方法的性能不受视频内容和规模影响。

4 结论

本文通过对全局阈值法的并行处理，基于视频关键帧的任务分割，以及MPI消息传递接口的框架利用，而设计的一种基于关键帧分割的主从式并行新闻视频镜头检测方法。实现了镜头检测耗时的大幅降低，而且节点交互少，系统性能稳健，程序并行效率高，测试效果明显，为新闻视频的后期处理创造了条件。随着现代信息技术的发展，在未来新闻视频海量数据处理和视频处理实时化方面，并行新闻视频镜头检测方法的应用前景非常广阔。

参考文献

[1]庄越挺, 潘云鹤, 吴飞网.上多媒体信息分析与检索[M].北京:清华大学出版社, 2002.

[2]Z Liu, Q Huang.Classification of audio events in braodcast news[A].In:MMSP-98[C], CA, USA, 1998:364-369.

[3]章毓晋.基于内容的视觉信息检索[M].北京:科学出版社, 2003.

[4]JS Boreczky, LA Rowe.compamon of video shot bounaary detection techniques[J].Joumal of Electronic Imaging, 1996, 5 (2) :122—128.

[5]Zhang H J, Kankanhalli A, Smoliar S.Automatic partitioningof video[J].Multimedia Systems, 1993, 1 (1) :10-28.

[6]赵锞锞, 彭天强.一种稳健的新闻视频镜头检测方法[J].电子学报, 2009.

[7]陈国良.并行计算-结构.算法.编程[J], 北京:高等教育出版社, 2003.

[8]Linux HPC Cluster Installation, IBM Redbooks.

[9]沈志宇, 廖湘科, 胡子昂.并行程序设计[M], 长沙:国防科技大学出版社, 1997.

[10]都志辉.高性能计算并行编程技术MPI并行程序设计[M].北京:清华大学出版社, 2001.

[11]OpenCV中文网站:http://www.opencv.org.cn/.

并行入侵检测系统 第5篇

并行计算指的是在并行计算技术上所进行的运算过程, 通常还叫做"高性能计算"或是"超级计算"。并行计算与顺序计算正如其表面意思所示, 顺序计算指的是多个子问题必须逐一按照既定顺序进行处理, 每个子程序必须在之前的子程序完成之后才开始进行, 而且该子程序完成后下一个子程序才开始进行, 这无疑会降低计算效率, 耗费更多时间, 而并行计算则是多个没有因果问题的子程序可以同时并列运行, 则运行效率可以得到极大提升。

并行程序设计的第一步就是要将现有的程序进行并行分解, 即分解为可以并行运行的各个子程序。由于并行计算需要各个并行运算的子程序间没有相互因果关系, 因此分解的过程需要经过复杂的计算和分析过程。在并行算法中, 除了顺序程序和并发程序这两种常见的交互作用外, 还有动态调度和映射机制等行为会影响程序的整体进程。上述的是存储机制和运行机制的交互作用的改变, 而在具体的程序设计中, 还面临时序问题、空间和站点分配以及运行速度等问题会影响并行程序的运行结果, 情况是非常复杂的, 在系统的并行知识体系中, 还需要程序员丰富的经验来保证所完成的程序的可靠性。

2 并行算法的关键技术

在并行程序设计中, 与原有的顺序程序设计的关键技术不同, 主要有数据、空间分布和任务调度等特有步骤。下面对并行程序设计的关键技术进行介绍描述。

任务划分:原程序是顺序运行的, 上文中提到并行程序设计的第一步是将原程序分解并划分, 即分解为数个可以并行运行的任务, 通常为数个子程序, 也可以是一段语句或是一个循环中一个或一组迭代。

数据分布:在并行程序中, 数据的调用和存储情况与顺序程序也是不同的, 因此在并行程序设计中, 需要重新分配数据的存储状态, 方便数据在并行程序中被调用, 保证数据合理分布在存储器中。

任务同步:并行程序中各子程序或是语句虽然没有相互间之间的因果关联, 但是仍然需要协调运行, 并且系统要保证各子程序所需条件实时得到满足, 这样才能保证整体程序的流畅性和高效性。

任务通讯:并行程序中各子程序或语句运行时还要实时传递数据和参数以保证程序运行过程的准确性, 因此需要在不同的存储模式下针对其相应特点来建立任务间的相互通讯通道。

粒度:粒度指的是并行程序中单个任务的运行时间的长短。合理的任务分解则会产生程度合理大小的粒度, 过大或是过小的粒度对程序的执行都是不利的。

负载平衡:各任务不仅要有合理的粒度, 而且在任务分家中, 要尽量使任务有大致相等的执行时间与复杂度, 并且与整体的并行程序执行的总时间在数量级上保持相近。

确定性:由于并行性极易导致程序在每次的执行中会产生不同的时序关系, 并导致产生时序性错误, 这种错误的产生是随机性的, 很难重现并修复, 而且在以后的执行中是否会出现也是很难确定的。因此并行程序设计中的一个重点就在程序中添加适当的同步机制来保证程序的确定性。

3 并行算法在图像边缘检测中的应用

在数字图像处理中运用并行计算来处理是数字图像处理技术的一个趋势, 数字图像边缘检测算法有多种, 但是一般的思想都是使用边缘检测算子依次作用于图像的每一个像素点。逐像素的处理方式会导致计算量随图像增大而指数倍增加, 因此在实际的应用过程中有相当大的限制性, 下面介绍两种并行处理的方法。

(1) 静态均匀划分法

由于使用检测算子对图像逐像素处理的过程没有直接的因果关系, 因此理论上可以对各个像素同时并行处理, 但是这样做粒度过小, 正如前文中所述, 粒度过小对设备的要求过高, 虽然可以获得理论上最高的运行速度, 但是这样做也是不合理的。合理的方法应当是对图像适当的分块, 然后将各个分块分配到每一个处理节点, 由各节点独立运算。

分解的方法有多种, 常用的有按照行均匀划分、按照列均匀划分以及棋盘式的二维均匀划分。假设并行处理所用的处理机节点数目为p, 而原算法的复杂度为o K××M×N×, 静态均匀划分后逐项任务处理的算法时间复杂度为。

(2) 并行算法设计中的归约方法

归约方法是在并行算法程序设计中常用的一个方法, 在MPI中, 专门提供了MPI_REDUCE操作来进行归约处理, 这里我们选用其中的MPI_MAX使用在图像边缘检测中。

在边缘检测算法中常用的检测算子如Prewitt、Robinson、Kirsch等, 共同的特点是分别有八个不同方向的模板算子, 通过这八个不同方向的模板算子对图像进行处理, 然后取其中的最大值, 因此针对这个特点, 我们可以进行归约处理。首先在各个处理机节点处分别存储图像, 然后对八个不同方向的模板算子编号处理。在k≤3 (处理机节点数p=2k) 的情况下, 在每个处理机节点处可以使用8/p个模板算子来处理图像, 而在k≥3的情况下, 则可以同时使用静态均匀划分, 对划分出的每个图像块分别使用八个模板算子来处理。归约方法最后获得的算法复杂度同样为。

摘要：随着数字图像越来越清晰, 图像处理的数据量越来越大, 原有算法已经很难满足时间复杂度的要求, 而并行计算则可以很好地解决这个问题。本文介绍了并行算法的特点和关键技术, 并介绍了并行算法在图像边缘检测中的具体应用, 有很好的指导意义。

关键词：并行算法,图像边缘检测,MPI,数字图像处理

参考文献

[1]田玲.图像边缘检测中并行算法的应用与研究[D].电子科技大学, 硕士学位论文, 2005.

并行入侵检测系统 第6篇

最大似然检测MLD(Maximum Likelihood Detection)[3]能够达到最优检测效果,但其复杂度随发送天线数和调制阶数呈指数增长,很难在实际中广泛应用。球形译码SD(Sphere Decoder)检测算法[4,5]是一种深度优先遍历算法,它在降低平均计算复杂度的同时能够达到最优检测性能,但其复杂度会随着不同的信道条件而变得不稳定。参考文献[6]介绍了一种基于信道矩阵QR分解[7]的M分支树搜索算法(QRD-M),该算法是一种广度优先遍历算法,其不需要对整个信号空间进行搜索,但可以在每一层选取适当的最大搜索分支数M,在保证合理复杂度的同时达到逼近ML检测性能的效果。

因此,本文提出一种基于QRD-M的多天线分组并行检测算法,该算法首先根据列范数大小对信道矩阵进行排序,据此将多根(比如8根)发送天线分成两组(每组4根发送天线),然后分别在每组组内并行采用灵活配置的QRD-M检测算法,在降低了多天线信号检测过高复杂度的同时,获得了较好的系统性能。

1 系统模型

考虑如图1所示的系统模型,包含NT个发射天线和NR个接收天线的V-BLAST结构[8]的MIMO通信系统,且NTNR。主要由调制编码、MIMO检测、解调等模块组成。

系统在接收端的接收信号矢量y可表示为:

其中,y为NR维接收信号列向量,x为NT维发送信号列向量,n为NR维独立同分布复高斯噪声信号列向量,信道矩阵H=[H1,H2,,HNT],假设为非相关瑞利平坦衰落信道,列向量Hj=[h1,j,h2,j,,hNR,j]T表示第j个发送天线到NR个接收天线的信道矩阵,hi,j表示第j个发送天线到第i个接收天线之间的信道矩阵系数,由独立同分布复高斯随机变量组成。

2 检测算法

2.1 传统的QRD-M检测算法

根据矩阵论的知识,信道矩阵H可进行如下QR分解[9]:

其中y軇=QHy、η=QHn分别变换后的接收信号矢量和噪声向量。传统的QRD-M检测算法流程如下:

(1)首先检测信号层xNT,xNT即为第NT个天线上的发送信号,相当于从R的最后一行开始检测,并将检测结果代入至上一次,抵消已检测信号的干扰,直至所有的天线都完成检测。利用式(4)计算第i(1iNT)层的累积分支度量。

其中C为星座符号集合。保留的累积分支度量值中最小的M个分支对应的信号估计值,完成第i层的信号检测。

(2)基于前i层把保留的符号估计值再利用式(5)对i+1层的当前分支度量值进行计算,并得到i+1层的累积分支度量,进而与步骤(1)中类似,保留M个信号估计值。

(3)当i=NT时,对M个幸存路径中输出累积分支度量值最小的一个,算法结束。44 MIMO系统传统QRD-M(M=4)检测算法的树形结构如图2所示。

2.2 基于QRD-M的多天线分组MIMO检测算法

2.2.1 算法思想

本文对传统的QRD-M算法主要分两步进行改进。

(1)将发送天线按照信道矩阵H列范数大小顺序进行分组,使得具有较大检测信噪比的天线首先被检测,保证较优的检测顺序,同时分组之后相当于减少了天线个数,而且组内可以采用检测算法进行并行处理,从而降低了处理复杂度;

(2)引入参考文献[10]中定义的变量Sm,即QRD-M算法中第一级MLD的序列长度,在传统QRD-M算法中,Sm是由M决定的,因此Sm的选取不够灵活,显然Sm的长度越大越逼近MLD的检测性能。在完成发送天线分组后,组内对于不同的调制方式和不同的天线数采用灵活配置的策略,将Sm值和M值独立设置。对于低阶调制和较少天线数的系统配置时,由于QRD-M的信号树的层数及每层分支数较少,为了获得更好的检测效果,建议采用较大的Sm值;对于高阶调制和较多天线数的系统配置时,建议采用较小的Sm值,可以有效的实现性能与复杂度的折衷设计。

2.2.2 算法流程

改进算法的具体步骤如下:

(1)对信道矩阵H=[H1,H2,,HNT]按照列范数大小进行排序。不失一般性,假设norm(H1)

(2)对Ho及其转置矩阵Horev分别进行QR分解:

与传统QRD-M检测类似,检测顺序分别从R和Rrev的最后一层开始,而本文算法检测至NT/2或者「NT/2骎层则结束。如图4所示。

(3)选定M值和Sm值后,即可以确定在每一层需计算的累积分支度量以及保留的分支个数。当层数iSm时,则根据2.1节中的传统QRD-M算法保留累积分支度量值中最小的M个分支对应的信号估计值。

(4)两组组内并行检测至NT/2或者「NT/2骎层时,选取各自幸存路径中累积分支度量值最小的分支,并将两组检测结果合并后作为最终检测结果输出,算法结束。

3 算法分析

本文主要针对LTE-A引入的8发8收天线配置进行分析,本算法对于更多或更少天线数配置同样具有普适性。

3.1 复杂度比较

QRD-M检测算法的复杂度主要是以检测过程中信号树搜索的总分支数决定的。设检测层数为NT(不失一般性,NT为偶数),调制阶数Qm,本文算法遍历的总分支数为:

对于88天线配置的MIMO系统,采用BPSK和QPSK两种调制方式时,在不同的M和Sm条件下,计算出搜索的总分支数如表1和表2所示。

3.2 性能仿真与分析

为了进一步验证算法的有效性,现对所提出的算法进行计算机仿真,并与传统算法进行对比。仿真假设无信道编码且为理想的信道估计,设置仿真条件为:采用V-BLAST传输机制,BPSK和QPSK两种调制方式;发射天线数NT=8,接收天线数NR=8;每对收发天线间假设为平坦瑞利衰落信道。

图5和图6分别为BPSK(取M=2)和QPSK(取M=4两种调制方式下,传统QRD-M检测算法与本文算法(Sm=1,Sm=2,Sm=3,Sm=4)的检测性能比较。可以看出,当Sm=1时,本文算法与传统算法性能相当,这是因为本文算法在Sm=1时,信号树每层仍只保留M=2(BPSK)和M=4(QPSK)个分支,其需要计算的总分支数与传统算法相同,因此性能无明显改善;当Sm=2时,本文算法在达到误码率为10-4时,BPSK调制方式下与传统算法相比有大约3 dB的增益,QPSK方式下大约有2 dB的增益,然而根据表1,BPSK方式下其所需计算的总分支数仅仅比传统方案多4个,QPSK方式下比传统方案多24个;当Sm=3时,本文算法的检测性能较传统算法有了更大的改进,BPSK方式下其所需计算的分支数比传统方案多16个,QPSK方式下比传统方案多136个;当Sm=4时,本文算法的检测性能基本达到饱和效果,较Sm=3时有略微的改进。

因此根据性能需要以及复杂度的折衷,可灵活配置Sm的大小。例如,采用BPSK调制方式时,宜采用Sm=2和Sm=3两种检测方案;采用QPSK调制方式时,则采用Sm=2的检测方案更为适宜。

本文针对未来移动通信系统中多天线处理复杂度过高的问题,提出了一种基于QRD-M的多天线分组并行检测算法。该方法首先将发送天线按照列范数大小分成两组,组内并行采用改进的QRD-M算法,灵活配置第一级ML检测的序列长度来实现性能需要和复杂度的折衷。本文分析比较了所提算法与传统算法的复杂度,通过计算机仿真证明了在相近的复杂度下本文算法能够获得更好的检测性能。

参考文献

[1]Li Qinghua,Li Guangjie,Lee Wookbong,et al.MIMO techniques in WiMAX and LTE:a feature overview[J].IEEE Communications Magazine,2010,48(5):86-92.

[2]ZHANG C,ARIYAVISITAKUL S L.LTE-advanced and4G wireless communications[J].IEEE Communication Network-ing&Broadcasting.2012,50(2):102-103.

[3]王东明.无线MIMO系统中迭代检测与信道估计技术研究[D].南京:东南大学,2006.

[4]VITERBO E,BOUTROUS J.A universal lattice code dec-oder for fading channels[J].IEEE Transactions on Informa-tion Theory,1999,45(5):1639-1642.

[5]DAMEN M O,GAMAL H E I,CAIRE G.On maximum-likelihood detection and the search for the closest lattice Point[J].IEEE Transactions on Information Theory,2003,49(10):2389-2402.

[6]KIM K J,Yue Jiang,ILTIS R A,et al.A QRD-M/Kalman Filter-based Detection and Channel Estimation Algorithm for MIMO-OFDM Systems[J].IEEE Transactions on Wire-less Communications,2005,4(2):710-721.

[7]陈亮,李建东,陈东.改进的基于QR分解的分层空时检测算法[J].电子与信息学报,2010,32(6):1505-1509.

[8]WOLNIANSKY P W,FOSCHINI G J,GOLDEN G D,et a V-BLAST:An architecture for realizing very high data rates over the rich-scattering wireless channel[C].1998 International Symposium on Signals Systems and Electron-ics.Pisa,Italy:[s.n.],1998:295-300.

[9]张贤达.矩阵分析与应用[M].北京:清华大学出版社,2004.

并行入侵检测系统 第7篇

多用户信号检测可归结为组合优化问题。当连接权值对称时,Hopfield神经网络(HNN)所述能够在瞬间获得组合优化的近优解,但易陷入局部最小。线性最小均方误差(MMSE)多用户检测具有与最优多用户检测相近的误码率性能,但是求解线性MMSE算法需要求解矩阵的逆,其运算量很大,不符合实时检测要求,限制了它的应用。本文以最小均方误差为准则,利用HNN特有的如文献[1]所述的并行干扰抵消结构及其固有的能量函数快速下降特性,得到了以MMSE为准则,利用HNN进行并行干扰抵消求解的多用户检测(MHNN)算法。

1 算法原理

线性MMSE多用户检测算法的设计目标是使第个用户的发送信号与其估计值之间的均方误差达到最小。即选择第个用户信号的线性变换使得

其中,如文献[1]所定义,ck是一个维列矢量。若令,并令表示k个用户的线性算子,则可等价为在MMSE准则下求最佳矩阵,使均方误差定义的代价函数最小化。

设k第个用户为期望用户,表示期望用户均方误差最小化的线性滤波器系数,则

其中,<>表示内积,表示二范数,是扩频序列的互相关矩阵。定义

基于MMSE准则的HNN线性多用户检测算法,其原理如图1所示。

2 在MC-CDMA系统中的算法仿真与性能分析

信道参数为最大多径扩展10μs,MC-CDMA系统[2]的循环前缀为10.8μs,每个子信道上的数据符号持续时间为0.5ms。扩频波形为32位长的Wals H码,期望用户1的SNR=10d B,远近效应。由图2可见SNR=10d B时,在的平台上可容纳的激活用户数为31,说明该算法在接近满载的MCCDMA系统中的BER同样能达到移动通信系统的指标,表明该算法具有良好的抗多址干扰、环境噪声以及抗多径时延的性能。(如图2)

3 小结

本文分析了基于HNN的最优多用户检测算法,针对其能量函数易陷于局部极小点的问题,将基于MMSE准则的线性多用户检测算法与Hopfield神经网络相结合,由于利用HNN神经网络进行并行处理取代了MMSE算法的矩阵求逆运算,因而显著降低了算法的计算复杂度。

摘要：基于神经网络运算速度快,并行处理能力强的特点,本文以最小均方误差为准则,利用Hopfield神经网络特有的并行干扰抵消结构及其固有的能量函数快速下降特性,提出了基于Hopfield神经网络的并行干扰抵消多用户检测算法,既解决了局部最优的问题,又降低了MMSE的计算复杂度。

关键词：HNN,GMHNN,移动终端

参考文献

[1]Yanping Li,Chengrui Zhang,Huakui Wang and Shengkun Wang.Blind Adaptive NPCA Algorithm Based on Neural Network Tracking Subspace[J],Sensing,Computing and Automation.2006,(8):783～786