软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2004年第02期杂志 文档列表

PRAM和LARPBS模型上的近似串匹配并行算法159-169

摘要：近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用((m+1)个处理器和O(n/(+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.

IEEE／WIC／ACM2004网上智能与智能Agent技术联合国际会议（WI／IAT 2004）征文通知169-169

基因序列分析软件Hmmpfam的可扩展并行性能优化170-178

摘要：基于MPI(message passing interface)平台实现了HMMER软件包核心程序之一Hmmpfam的大规模并行计算.该版本针对原PVM(parallel virtual machine)并行版本在并行规模扩大后,master易成为通信瓶颈的问题,对通信结构进行了优化,提出了一种新的三层通信结构,在序列和HMM模型的两个层次上实现了并行化,并分别提供了有效的负载平衡策略,同时优化了I/O性能,在700多台处理机上达到95%的效率.

两种对URL的散列效果很好的函数179-184

摘要：在Web信息处理的研究中,不少情况下需要对很大的URL序列进行散列操作.针对两种典型的应用场合,即Web结构分析中的信息查询和并行搜索引擎中的负载平衡,基于一个含有2000多万个URL的序列,进行了大规模的实验评测.说明在许多文献中推荐的对字符串散列效果很好的ELFhash函数对URL的散列效果并不好,同时推荐了两种对URL散列效果很好的函数.

基于变异和动态信息素更新的蚁群优化算法185-192

摘要：尽管蚁群优化算法在优化计算中已得到了很多应用,但在进行大规模优化时,其收敛时间过长仍是应用该算法的一个瓶颈.为此,提出了一种高速收敛算法.该算法采用一种新颖的动态信息素更新策略,以保证在每次搜索中,每只蚂蚁都对搜索做出贡献;同时,还采取了一种独特的变异策略,以对每次搜索的结果进行优化.计算机实验结果表明,该算法与最新的改进蚁群优化算法相比,其收敛速度提高了数十倍乃至数百倍以上.

一种限定性的双层贝叶斯分类模型193-199

摘要：朴素贝叶斯分类模型是一种简单而有效的分类方法,但它的属性独立性假设使其无法表达属性变量间存在的依赖关系,影响了它的分类性能.通过分析贝叶斯分类模型的分类原则以及贝叶斯定理的变异形式,提出了一种基于贝叶斯定理的新的分类模型DLBAN(double-level Bayesian network augmented naive Bayes).该模型通过选择关键属性建立属性之间的依赖关系.将该分类方法与朴素贝叶斯分类器和TAN(tree augmented naive Bayes)分类器进行实验比较.实验结果表明,在大多数数据集上,DLBAN分类方法具有较高的分类正确率.

基于连续过松弛方法的支持向量回归算法200-206

摘要：支持向量回归(support vector regression,简称SVR)训练算法需要解决在大规模样本条件下的凸二次规划(quadratic programming,简称QP)问题.尽管此种优化算法的机理已经有了较为明确的认识,但已有的支持向量回归训练算法仍较为复杂且收敛速度较慢.为解决这些问题.首先采用扩展方法使SVR与支撑向量机分类(SVC)具有相似的数学形式,并在此基础上针对大规模样本回归问题提出一种用于SVR的简化SOR(successive overrelaxation)算法.实验表明,这种新的回归训练方法在数据量较大时,相对其他训练方法有较快的收敛速度,特别适于在大规模样本条件下的回归训练算法设计.

预估计混叠度的MAP超分辨率处理算法207-214

摘要：提出一种预估计混叠度的PEMAP(pre-estimated MAP(maximum a posteriori)算法,用于卫星图像的地面超分辨率处理.它通过频域分析确定卫星图像的混叠度,将其作为先验信息在空域控制MAP估计的循环迭代,联合估计帧间位移和高分辨率图像.该算法克服了最大后验概率MAP算法的盲目性和不稳定性,使其适应性更好.实际的卫星图像处理显示了较好的处理效果.

基于广义粗集覆盖约简的粗糙熵215-220

摘要：在广义粗集覆盖约简理论中,由于集合的上下近似是由其覆盖约简来确定的,因此有必要寻求一种新的度量来刻画知识和粗集的粗糙性.通过引入信息熵以刻画广义粗集覆盖约简的知识粗糙性以及粗集粗糙性,提出了一种新的知识粗糙性和粗集粗糙性度量.得到知识粗糙熵和粗糙集的粗糙熵都随广义覆盖约简的变细而单调减少的结论,从信息论观点出发,对不完备信息系统粗集理论进行了探讨.

基于非抽样小波字典的低速率视频编码221-228

摘要：目前,大多数视频编码器所采用的核心编码技术都是基于分块DCT(discreted cosine transform)变换对帧预测误差进行编码,在极低编码速率下,这类编码器往往会产生人眼敏感的方块效应.而基于匹配跟踪冗余信号分解的视频编码器具有比H.263编码器更高的编码性能,但由于该算法需要在一个冗余字典里搜索最佳匹配误差结构的原子函数,其实现所需要的运算量比传统的编码器要高很多,因此影响了这种编码器的效率.提出了基于树形结构的非抽样小波字典的匹配跟踪算法,能够充分利用字典函数之间存在的滤波结构关系,使得整个算法实现的计算量显著下降.同时,考虑到相邻帧运动信息的连续性,最后还给出一种基于晶格结构的有效原子位置信息编码方法.实验结果表明,该算法保持了原有的编码性能,在视频编码应用中具有很好的实用价值.

2004年全国软件与应用学术会议（NASAC2004）——征文通知228-228

交换式以太网中连续实时流媒体的可靠组播229-237

摘要：对目前局域网中连续实时流媒体的可靠组播进行了研究.首先分析了局域网影响可靠组播的几个特性,然后设计了局域网内针对连续实时流媒体的基于重传的可靠组播传输协议.协议中的错误恢复首先利用接收者检测包丢失,同时采用NAK(negative acknowledgment)抑制减少产生的反馈包;然后发送者根据NAK请求重传已经丢失的数据包;接收者根据本地播放时间限制决定接收或者丢弃迟到的重传包.实验结果和性能分析证明了该可靠组播协议的可靠性和有效性.

基于带参数整数小波变换可见数字水印238-249

摘要：构造出了带参数的整数小波,应用变型的Rijndael密码构造出了Hash函数.提出了一种基于带参数整数小波变换、离散余弦变换及变型Rijndael加密算法的可见数字水印算法.利用整数小波的参数变化,并结合Hash函数保证了水印的安全,同时使得该可见数字水印满足公开密码体制.通过理论分析和实验证明,该方法能够保证图像的质量和水印的安全,在版权保护方面具有广阔的应用前景.

用于IP追踪的包标记的注记250-258

摘要：拒绝服务攻击是一类最难对付的网络安全问题.近来,人们提出了多种对策.其中由Savage等人提出的一类基于概率的包标记方案比较有研究价值.这里先对拒绝服务攻击的对策作一简述,然后分析了几种包标记方案,指出了它们的一些缺陷,并提出了一些改进措施.其中,对基本型概率包标记方案的一个修改使得计算量大大减少.

基于位置预查询的因特网移动支持方案259-267

摘要：提出一种预查询移动支持方案(mobile Internet protocol_based on location pre-query,简称MIP_Q),以解决家乡网络的流量瓶颈和单点故障问题,从而提高移动通信的效率和可靠性.MIP_Q通过扩展域名服务系统管理和跟踪移动节点的当前位置信息,省去了家乡;采用并行切换控制方式,同时避免了MIP(mobile Internet protocol,简称MIP)中的三角路由和隧道路由问题;借助有效的计算方法,分析和比较了MIP_Q与MIP,MIP_LR的平均移动通信成本和切换时延;在实现方面与广泛应用的广域蜂窝移动网络进行了类比.结果表明:MIP_Q在切换效率和新增实体数等方面优于同类方案;MIP_Q可以极大地降低节点的移动通信成本,减小切换时延;MIP_Q具有良好的可行性.最后提出MIP_Q的仿真和实现方案.

基于Peer-to-Peer的分布式存储系统的设计268-277

摘要：分布式存储系统是p2p技术的一个重要的研究领域.当前对p2p系统的结构研究已经能够高度有效地控制节点路由次数,人们逐渐转向追求更为实际的路由距离.作为存储应用,分布式系统需要具备综合容错-恢复能力.在分析现有研究的基础上,建立一个接近实际网络节点分布的计算模型,通过已知的节点最优路径情况动态地预测网络真实路径的长度.利用评估算法聚集网络中相近的节点,使得同一分组的节点之间的距离最小化,提供更加合理的路由选择.对于存储的可靠性,提出了节点交叉管理模型和相应的数据迁移算法.这种管理策略及迁移算法的本地性特点显著提高了系统对各种事件的反应能力,保证了系统的可持续性.模拟结果显示,分组为路由选择提供了确实有效的判据,而且可以扩展到更大的规模.

基于重路由匿名通信系统的负载分析278-285

摘要：基于重路由匿名通信系统,如Mixes,Onion Routing,Crowds等,采用重路由机制在应用层转发数据,使实体之间的通信以间接的方式进行,从而有效地隐藏通信实体的身份信息,如主机的IP地址等.在性能方面,这种机制导致系统中产生额外的开销,如通信延时、负载等.着重从理论上分析了系统中的成员负载.通过深入考查基于重路由匿名通信系统的重路由机制,推导出了基于重路由匿名通信系统中成员负载的概率公式,证明了成员负载由系统中成员数目重路由路径数目以及重路由路径长度的概率分布所决定.应用该公式计算Crowds系统中成员的负载,得出精确的负载期望值为1/(1(pf)+1,改进了Reiter等人的分析结果O((n+1)/((1(pf)2n),证明了Crowds系统的成员负载不受系统中成员数目n的影响,具有良好的可伸缩性.并通过仿真实验验证了该分析结果.其结论为设计和规划匿名网络提供了理论依据.

多QoS约束的多播路由协议286-291

摘要：随着高性能网络、移动网络及Internet的不断发展,具有QoS约束的多播路由技术已成为网络及分布式系统领域的一个重要研究课题.研讨了具有多QoS约束的多播路由问题,其中主要包含延迟、延迟抖动、带宽、代价等QoS约束.描述了一种适应于研究QoS多播路由的网络模型,提出了一种具有多QoS约束的多播路由协议(multicast routing protocol with multiple QoS,简称MRPMQ).MRPMQ试图有效减少生成多QoS约束的多播树的开销.在MRPMQ中,一个多播组成员能够动态地加入/退出一个多播会晤,且不干扰现有的多播树.给出了该协议的正确性证明和复杂性分析.仿真实验结果表明,MRPMQ为多QoS约束多播路由提供了一种新的有效途径.