摘要:BSMA(bounded shortest multicast algorithm)被认为是最好的受限多播路由算法;然而,过长的计算时间限制了其应用.作为一种全局优化算法,遗传算法(GA)被越来越多地应用于解决多播路由问题.与传统的算法相比,遗传算法的全局搜索能力更强,但其易"早熟"的特点使它并不总是能够得到最优多播树.提出量子克隆多播路由算法,有效地解决了"遗传"多播路由算法中的"早熟"问题,量子交叉的引入,加快了算法的收敛速度.算法实现简单、控制灵活.仿真结果表明,该算法的性能优于BSMA算法和传统的遗传算法.

摘要:个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.

摘要:通过组合拟人启发式和模拟退火算法,提出了三维装箱问题的组合启发式算法.拟人启发式算法的主要思想来源于日常砌墙中的策略.利用找点法以及水平和垂直参考线规则来控制装填过程.用模拟退火算法改进拟人启发式.经过一些数据的测试,实验结果表明,该算法能够同文献中的优秀算法竞争.

摘要:研究了在门德尔遗传定理和哈代-维恩伯格平衡假设下,三元家庭基因型数据的单体分型和单体型频率估计问题.过去的研究仅仅关注个体间没有联系或者含有一般家系信息的基因型数据,而对这种特殊的三元家庭关注得不够.考虑到HAPMAP数据库中有一部分数据就基于这种三元家庭,现在有越来越多的需求要求直接分析这种特殊的家系结构.提出一个两段式的三元家庭中单体型频率的估计方法:i) 分型阶段,找出每一个三元家庭零重组单体构型;ii) 频率估计阶段,在前一阶段得到的单体构型基础上,应用EM算法来估计单体型频率.在程序包TRIOHAP中用C语言实现了单体分型算法和EM算法,并且使用模拟和实际数据测试了TRIOHAP的有效性和效率.实验结果表明,TRIOHAP要比其他那些忽略了三元家庭信息的常见单体型频率估计软件运行快很多.进一步地,由于TRIOHAP利用了这些信息,其估计结果更加可靠.

摘要:一般情况下,P3P问题可能出现1,2,3或4个解.但是,若3个控制点和摄像机光心这4点共圆,则会出现无穷多组解.利用"蒙特卡洛"方法模拟出P3P问题分别出现1,2,3,4个解的概率为0.9993,0.0007,0.0000,0.0000.结果论证了如下的事实,即在大多数情况下,P3P问题有唯一解.

摘要:传统的容错编译通常复制所有的计算并且使用完全冗余的存储单元来保证容错.这种完全冗余在存储空间和性能上的开销都是相当大的.在错误流分析的基础上提出错误流图的关键子图的概念以及通过关键结点和关键路径生成关键子图的方法,并设计了通过复制错误流关键子图实现部分冗余的算法.在保证有效容错能力的同时,部分冗余明显减小了经过容错编译的程序在存储空间和性能上的开销.实验显示,与复制全部错误流图的完全冗余相比,在结点覆盖率降低6.25%的情况下,部分冗余算法最多能够减少寄存器的使用数量6.25%,减少功耗超过17%,减少执行时间接近26%,同时提高性能超过22%.

摘要:高动态的计算环境使得QoS(quality of service)保障对于基于组件的分布式系统越来越重要,软件系统需要具备自我调整的能力以适应外部环境的变化.给出一种自适应的中间件配置框架,能够动态感知负载变化,并自动调整系统参数配置以保持用户所要求的服务质量.该框架的核心是一个基于分层排队网络的性能预测模型,用于指导搜索最优的资源配置,使性能需求得到最大的满足.在OnceAS应用服务器上进行原型实现,并以StockOnline应用做实验,比较了在使用和不使用该框架时的性能需求的满足情况.结果显示,在负载增加时,通过自配置框架的调控,应用性能需求的保障程度得到了较大的提升.

摘要:提出了一种基于Assume-Guarantee搜索复用的验证方法,对C程序源代码进行验证.其思想是,在程序的每点处都引入一个保守假设条件,并假设从任意点出发,变量取值满足该点假设条件的所有执行路径都不会违背给定性质,然后根据这些假设条件遍历所有可能的执行路径以验证给定的时序安全性质,并在遍历的过程中验证这些假设条件是否满足,如果不满足,则不断对其精化和加强.验证方法总是在保证假设条件可靠的前提下尽量使用较弱的条件,使得大量的执行路径由于满足假设条件而可以搜索复用,从而降低验证代价.应用该方法验证了Linux操作系统中SSL协议的实现程序openssl-0.9.6c满足SSL协议的初始握手规范.实验结果表明,该方法具有良好的实用性和可扩展性.

摘要:SPEM(software process engineering metamodel)是国际标准化组织制定的标准元模型,正日益成为软件过程建模领域的行业标准,但在过程执行方面,SPEM还存在不足.将软件过程看作是一种特殊的工作流,提出了一种应用工作流运行机制支持软件过程执行的方法.通过将SPEM模型转换为XPDL(XML process definition language)模型,利用XPDL引擎支持SPEM模型的执行.制定了SPEM和XPDL之间的映射规则,设计了转换算法并开发了转换引擎.该方法被应用在SoftPM项目中,成功地基于XPDL引擎Shark实现了对软件过程模型的执行支持.

摘要:为了解决工作流时间建模与时序一致性验证问题,以时序逻辑和模型检查为基础,提出了一种工作流时间建模与时序一致性验证方法.该方法用一阶逻辑描述工作流模型及其时间信息,用时序逻辑描述工作流的时序约束,用模型检查算法对时序约束进行验证与分析.该方法不是针对某一种时序约束提出来的,而是能够验证任何用时序逻辑描述的工作流时序约束.该方法还能够对未通过验证的时序约束提供工作流运行实例作为反例,帮助用户定位模型的问题.以一个工作流时间建模和时序一致性验证的实例证实了所提出方法的有效性.

摘要:在基于识别的界面中,用户的满意度不但由识别准确度决定,而且还受识别错误的纠正过程的影响.提出一种基于多通道融合的连续手写笔迹识别错误的纠正方法.该方法允许用户通过口述书写内容纠正手写识别中的字符提取和识别的错误.该纠错方法的核心是一种多通道融合算法.该算法通过利用语音输入约束最优手写识别结果的搜索,可纠正手写字符的切分错和识别错.实验评估结果表明,该融合算法能够有效纠正错误,计算效率高.与另外两种手写识别错误纠正方法相比,该方法具有更高的纠错效率.

摘要:侧重于建立形式概念分析与粗糙集之间融合的理论基础.利用形式概念分析中名义梯级背景(nominal scale)的概念,对信息系统进行平面梯级(plain scaling)得到了衍生的形式背景.证明了粗糙集理论中的划分、上下近似、独立、依赖、约简等核心概念都可以在相应的衍生背景中进行表示.揭示了粗糙集理论在分析处理数据时的局限性,指出了利用梯级的方法可以扩展粗糙集理论.

摘要:噪声是影响进化计算(evolutionary computation,简称EC)算法性能的一个重要因素.对于传统EC中的噪声,已有许多研究成果,但交互式进化计算(interactive evolutionary computation,简称IEC)的噪声研究成果却较少.首先回顾了传统EC中噪声的定义、来源、类型及各种处理噪声的方法;其次,从IEC的理性用户观点出发,研究了IEC的适应值噪声及收敛鲁棒性.其中,空间的映射关系、个体间的占优关系以及IEC的收敛等是研究收敛鲁棒性的两个定理(强条件定理和弱条件定理)的基础.这两个定理表明,理性用户条件下的噪声不会影响算法全局收敛性.在这两个定理的基础上进一步得出了如下结论:有效的适应度尺度变换是弱条件定理的一部分,IEC中"真"适应值是用户偏好等.并以不满足弱条件定理,即破坏算法收敛性为依据,给出了IEC中适应值噪声的狭义定义.实验进一步验证了这两个定理.上述结论为进一步研究IEC作了必要的铺垫.

摘要:针对片上网络(network on chip,简称NoC)的节点数量少、距离近、物理实现复杂度受到限制的特点,提出了一种新的Xmesh拓扑结构,并为该结构提出了XM路由算法.该结构在经典的mesh结构的基础上添加了两个对角线型的回边,缩短了节点间的距离,而且路由计算的复杂性不高,实现的复杂度基本没有增加.将Xmesh与经典的Mesh和Torus结构进行了理论分析比较,同时,在Popnet模拟器上基于均衡负载和热点负载两种负载模式进行性能比较.模拟结果表明,Xmesh平均延时不到Mesh结构的70%.对于均衡负载,当网络规模较小时,Xmesh的延时比Torus的更小;对于热点负载,当热点距离网络中心或者对角线比较近时,Xmesh的延时比Torus的小10%～30%.反之,其延时比Torus的大10%～30%.总的来说,Xmesh的性能与Torus比较接近,但其物理实现更为简单,Xmesh比Mesh结构的性能更好.

摘要:可扩展路由器控制平面节点间通信的瓶颈问题是制约软件体系结构大规模扩展的关键因素.针对此问题,在传统的软件体系结构的支撑模型中引入了传输适配子层的结构,上行的数据流经特征抽取与已注册的任务进行模式匹配,从而完成了对控制信息流基于内容的分类与分流,提高了其有效通信率.进一步根据任务的分布率、分散数和流量率这3个特征对模型进行了性能分析,表明了适配层的引入可以消除面间冗余流量和通信的可扩展瓶颈.最后通过实验验证了理论分析的正确性.

摘要:受资源类型多样化、搜索复杂度的制约,现有的P2P文件共享系统中的搜索机制是基于文件名的关键字匹配,这种方法不能发现关键字与资源内容之间的深层关系,因此不能实现语义检索.针对这个问题,提出一种新的搜索方案,该方案建立在已有的搜索机制之上,利用用户的搜索行为和下载行为的规律自动发现关键字和资源间的深层关系,在底层的P2P网络上构建一个元数据空间以辅助搜索.该方案具有实现代价小、时间复杂度低、可进化和支持语义搜索的优点.在Maze系统上的实验表明,该方案具有较高的查询命中率和查询准确率.

摘要:无结构P2P覆盖网络并非规则网络,也非纯粹的随机网络,结点在拓扑结构中体现出非对等性,在接收查询消息的数量上具有非均衡性.研究了结点连接度分布、数据流行程度与搜索成功率之间的关系,并针对数据的不同流行程度给出了结点连接度的最优分配模型.最后给出了一种实现最优结点度分配的主动复制策略.实验结果表明,基于拓扑信息的主动复制是一种提高无结构P2P搜索性能的可行方法.

摘要:数据收集是无线传感器网络的一个基本功能.然而,现有的数据收集模式大都是基于静止基站的网络结构,导致基站周围的节点由于担负着网络内的所有负载而快速死亡,成为网络性能的瓶颈.研究如何利用移动基站收集数据来达到负载平衡.提出了一个利用移动基站协助数据收集的模式(movement-assisted data gathering,简称MADG),它将基站移动区域设置为缓冲区,首先将数据沿最短路径传输到缓冲区内,然后在基站移动的过程中进行数据收集.证明了缓冲区位置设置在距离中心时数据传输总能耗最少,并证明了存在一个缓冲区位置使得最大节点负载最小化,进而确定了同时考虑到能源消耗和负载平衡的基站移动区域.理论分析和实验结果表明,提出的数据收集模式在很大程度上降低了网络节点的最大负载,并且减少了数据传输能源中的消耗,分别比固定基站和同类工作的最大网络负载降低95%和80%以上.

摘要:提出了基于聚集和协议分析防御分布式拒绝服务攻击(aggregate-based protocol analysis anti-DDoS,简称APA-ANTI-DdoS)模型来检测和防御DDoS攻击.APA-ANTI-DDoS模型包括异常流量聚集、协议分析和流量处理.异常流量聚积把网络流量分为正常流量和异常流量;协议分析寻找异常流量中DDoS攻击流量的特征;流量处理则根据当前的DDoS攻击流量特征,过滤异常流量并测试当前聚积流量的拥塞控制特性,恢复被误判的流量.随后实现了APA-ANTI-DDoS系统.实验结果表明,APA-ANTI-DDoS模型能很好地识别和防御DDoS攻击,能在误判时恢复非攻击流量,保证合法的正常网络通信.

摘要:目前,IEEE 802.16标准推荐采用基于截断二进制指数回退算法的竞争解决方案.分析了该方案同IEEE 802.11竞争机制的区别,给出了传送机会利用率u、带宽请求延时d以及带宽请求丢失率p_d等性能指标的计算方法.通过性能模拟,讨论了初始化回退窗口W、用户站数目n以及单位时间帧内传送机会数目N_to等参数对性能指标的影响,进而得出基站调整性能参数的一般策略.这些策略对于基站进行上行带宽资源的分配具有指导意义.

摘要:为了在更高带宽的网络中进行有效的入侵检测分析,研究了入侵检测中的数据获取技术,提出了一种可扩展的高效入侵监测框架SEIMA(scalable efficient intrusion monitoring architecture).在SEIMA结构模型中,通过将高效网络流量负载分割器与多个并行工作的入侵检测传感器相结合,从而可以将入侵检测扩展应用到更高的网络带宽中;通过使用高效地址翻译技术和缓冲区管理机制实现了旁路操作系统的高性能用户级网络报文传输模型,以便提高单传感器的报文处理性能;通过采用有限自动机的方法构建了基于用户层的多规则报文过滤器以消除多余数据包的处理开销.模拟环境和实际环境下的测试结果表明,SEIMA在提高网络入侵检测系统数据获取效率的同时,能够降低系统CPU的利用率,从而可以将更多的系统资源用于更复杂的数据分析过程.

摘要:提出了一种基于原始图像的Tchebichef矩实现的几何攻击不变性第二代盲水印算法,利用原始图像的Tchebichef矩估计图像可能经历的几何攻击的参数来还原图像,其中,原始图像的Tchebichef矩可作为水印检测器的密钥.水印嵌入过程结合人类视觉系统的特性,且可在任何图像变换域中实现,给出了小波域的一种实现方法.水印检测过程采用独立分量分析技术不仅可以检测到水印而且可以提取水印,实现了真正意义上的盲检测.实验结果表明,该水印算法对于通用水印测试软件Stirmark提供的各种攻击具有很好的鲁棒性.

摘要:提出一个专门针对协同环境下CAD模型的多层次动态的安全访问控制(multi-level and dynamic security access control,简称MLDAC)模型.该模型利用一种多层次的权限模型,以简化权限定义及其分配过程,丰富了权限表达能力,实现了产品模型的多粒度访问控制.通过参照工作流的基本理念,引入权限的依赖关系及权限状态迁移概念,实现了权限的动态授权管理.通过实践证明,MLDAC模型可以对协同设计操作进行更加有效的控制,符合设计任务间的分工性、依赖性和交互性的特点.

摘要:提出了一种以代数B-样条曲线为表达形式、基于有向距离场的隐式曲线重建方法.首先给定一个表示封闭曲线、可能带有噪音且分布不均匀的平面点云,采用移动最小平方(moving least square,简称MLS)方法对点云去噪、重采样,得到一个低噪音、分布均匀的"线状"点云,再通过Level Set方法建立该"线状"点云的离散几何距离场,最后用一个代数B-样条函数光顺拟合该离散距离场,代数函数的零点集即为重建曲线.曲线重建过程可以归结为求解线性方程组问题.这种重建方法不仅可以得到高质量的重建曲线,还可以得到曲线周围的距离场信息.同时,避免了隐式曲线重建中经常出现的多余分支问题.

摘要:复杂光照条件下的人脸识别是一个困难但需迫切解决的问题,为此提出了一种有效的光照归一化算法.该方法根据面部光照特点,基于数学形态学和商图像技术对各种光照条件下的人脸图像进行归一化处理,并且将它发展到动态地估计光照强度,进一步增强消除光照和保留特征的效果.与传统的技术相比,该方法无须训练数据集以及假定光源位置,并且每人只需一幅注册图像.在耶鲁人脸图像库B上的测试表明,该算法以较小的计算代价取得了优良的识别性能.

摘要:基于Bézier三角曲面的de Casteljau算法,同时运用一些恒等式和基本不等式,给出了两类有理Bézier三角曲面片低阶导矢的上界.第一类上界是用控制顶点凸包直径表示的,在一阶偏导的情况下,它是对已有上界的改进;在二阶偏导情况下,当最大权因子与最小权因子比值大于2时,它也是对已有上界的改进.第二类上界是用相邻控制顶点间距离的最大值来表示的.

摘要:提出了一种基于几何细节映射的点模型的形状编辑方法.几何细节是曲面的一个重要属性,定义几何细节为原始曲面及其基曲面之间的向量差,该基曲面由多层次B样条所构成.通过基曲面上的局部仿射坐标,则可以得到与之对应的多分辨率几何细节表示,曲面的低频信息和高频信息易被用户所指定的频段分离.通过调节基曲面的形状,再将这些几何细节映射上去,可以对模型进行保细节的变形;如果将几何细节映射到其他物体上,将可以得到几何细节迁移的结果.为点模型开发了多种特征保持的编辑算子,实验结果表明,所提出的方法是一种有效的点模型造型算法.

摘要:提出了四边形网格的三分细分模式.对于正则和非正则四边形网格,分别采用不同的细分模板获得新的细分顶点.从双三次B样条中推导出正则四边形网格的三分细分模板,极限曲面C²连续;对细分矩阵进行傅里叶变换,推导出非正则四边形网格的三分细分模板,极限曲面C¹连续.提出的三分细分模式可以解决任意拓扑四边形网格的曲面细分问题.与其他细分模式相比,具有收敛速度快、适用范围广等优点.最后给出了四边形网格细分的实例.

摘要:利用运动捕获数据,通过学习获得虚拟人运动的统计模型,从而创建真实、可控的虚拟人运动.提出了一种方法:通过对原始运动数据聚类,提取出局部动态运动特征--动态纹理,并用线性动态系统描述,有选择地注释有明确含义的线性动态系统,构建注释动态纹理图.利用这一统计模型,可生成真实感强、可控的虚拟人运动.结果表明,这种方法在交互环境中能够生成流畅、自然的人体运动.