• 2007年第18卷第11期文章目次
    全 选
    显示方式: |
    • >综述文章
    • 流量矩阵估算的研究

      2007, 18(11):2669-2682.

      摘要 (8453) HTML (0) PDF 951.00 K (9063) 评论 (0) 收藏

      摘要:流量矩阵是许多网络规划和流量工程任务的关键输入,精确的流量矩阵至关重要,但直接监控非常具有挑战性.因此,如何根据对有限链路的测量数据和路由信息等先验信息,通过合理建模来推断流量矩阵,成为重要的研究课题.首先给出了流量矩阵的基本概念和估算原理;然后对近年来提出的20多种不同的解决流量矩阵估算问题的方法进行分类剖析,总结了目前流量矩阵估算方法的最新研究进展,并讨论了部分方法的性能和估算误差;最后讨论了未来流量矩阵估算的研究趋势和应用前景.

    • PRAM和LARPBS模型上有向序列翻转距离并行算法

      2007, 18(11):2683-2690.

      摘要 (3872) HTML (0) PDF 575.67 K (5013) 评论 (0) 收藏

      摘要:分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn).

    • 覆盖算法的概率模型

      2007, 18(11):2691-2699.

      摘要 (4820) HTML (0) PDF 695.51 K (6329) 评论 (0) 收藏

      摘要:要从本质上提高覆盖算法的精度,必须在算法中引入全局的优化计算.为此,先将覆盖算法扩展成核覆盖算法(以高斯函数为核函数),再利用高斯函数的概率意义(高斯分布),为核覆盖算法建立一个有限混合概率模型,在此基础上,利用"最大似然原理"引入全局优化计算,并利用EM(expectation maximization)方法进行求解,完成对覆盖算法的全局优化计算,从而扩大覆盖方法的使用范围并提高算法的精度,且将它从确定的模型扩展成概率的模型,后者更具抗噪声干扰的能力.最后给出模拟实验,实验比较结果表明,经优化后的概率模型确实提高了算法的精度.

    • 免疫克隆算法求解动态多目标优化问题

      2007, 18(11):2700-2711.

      摘要 (4995) HTML (0) PDF 1.06 M (6035) 评论 (0) 收藏

      摘要:求解动态多目标优化(dynamic multi-objective optimization,简称DMO)问题的主要困难在于目标函数、约束条件或者相关的问题参数是随时间不断变化的.基于免疫克隆选择学说,提出一种用于解决DMO问题的新算法--动态多目标免疫克隆优化(immune clonal algorithm for DMO,简称ICADMO).该算法改进了现有的克隆策略,采用整体克隆的方式;在选择策略上,根据Pareto-占优的概念,将抗体群中的个体分为支配个体和非支配个体,对非支配个体进行选择.采用3个特色算子,使其很好地保持了所得解的多样性、均匀性和收敛性.通过数值实验,与DBM(direction-based method)算法进行比较,结果表明,新算法在收敛性、多样性以及解分布的广度方面都体现了很好的性能.

    • 基于支持度理论的广义Modus Ponens问题的最优解

      2007, 18(11):2712-2718.

      摘要 (4106) HTML (0) PDF 534.21 K (4990) 评论 (0) 收藏

      摘要:为了将模糊推理纳入逻辑的框架并从语构和语义两个方面为模糊推理奠定严格的逻辑基础,通过将模糊推理形式化的方法移植到经典命题逻辑系统中,把FMP(fuzzy modus ponens)问题转化为GMP(generalized modus ponens)问题,并基于公式的真度概念提出了公式之间的支持度,进一步利用支持度的思想引入了GMP问题以及CGMP(collective generalized modus ponens)问题的一种新型最优求解机制.证明了最优解的存在性,同时指出,在经典命题逻辑系统中存在着与模糊逻辑完全相似的推理机制.该方法是一种程度化的方法,这就使得求解过程从算法上实现成为可能,并对知识的程度化推理有所启示.

    • 基于向量集约简的精简支持向量机

      2007, 18(11):2719-2727.

      摘要 (4464) HTML (0) PDF 615.63 K (5498) 评论 (0) 收藏

      摘要:目前的支持向量集约简法在寻找约简向量的过程中需要求解一个无约束的多参数优化问题,这样,像其他非线性优化问题一样,求解过程需要面对数值不稳定或局部最小值问题.为此,提出了一种基于核聚类的SVM(support vector machine)简化方法.此方法首先在特征空间中对支持向量进行聚类,然后寻找特征空间中的聚类中心在输入空间中的原像以形成约简向量集.该方法概念简单,在简化过程中只需求解线性代数问题,从而解决了现存方法存在的瓶颈问题.实验结果表明,该简化法能够在基本保持SVM泛化性能的情况下极大地约简支持向量,从而提高SVM的分类速度.

    • 一种基于多类型偏好的偏好逻辑

      2007, 18(11):2728-2739.

      摘要 (5212) HTML (0) PDF 786.66 K (5230) 评论 (0) 收藏

      摘要:针对目前缺乏多类型偏好共存的偏好逻辑系统的现状,提出并构造了一个能够描述和推理多种类型偏好的逻辑系统MPL(logic of many kinds of preference).在进一步提出MPL语言LMPL基于最粗糙/最细致描述原则的非单调语义基础上,通过分级知识库这种常用偏好表示方法的LMPL重写,初步考察了LMPL表示能力,最后进行总结并提出需要进一步研究解决的问题.

    • 自适应扩散混合变异机制微粒群算法

      2007, 18(11):2740-2751.

      摘要 (5026) HTML (0) PDF 898.77 K (6020) 评论 (0) 收藏

      摘要:为了避免微粒群算法(particle swarm optimization,简称PSO)在全局优化中陷入局部极值,分析了标准PSO算法早熟收敛的原因,提出了自适应扩散混合变异机制微粒群算法(InformPSO).结合生物群体信息扩散的习性,设计了一个考虑微粒分布和迭代次数的函数,自适应调整微粒的"社会认知"能力,提高种群的多样性;模拟了基因自组织和混沌进化规律,引入克隆选择使群体最佳微粒gBest实现遗传微变、局部增值,具有变异确定性;利用Logistic序列指导gBest随机漂移,进一步增强逃离局部极值能力.基于种群的随机状态转移过程,证明了新算法具有全局收敛性.与其他几种PSO变种相比,复杂基准函数仿真优化结果表明,新算法收敛速度快,求解精度高,稳定性好,能够有效抑制早熟收敛.

    • >综述文章
    • 挖掘多关系关联规则

      2007, 18(11):2752-2765.

      摘要 (8403) HTML (0) PDF 879.97 K (11337) 评论 (0) 收藏

      摘要:关联规则的挖掘是数据挖掘中的一项重要和基础的技术,已进行了多方面的深入研究,有着广泛的应用.传统数据挖掘算法是针对单表数据进行处理的,在应用于多关系数据挖掘时存在诸多问题.对多关系关联规则的挖掘问题进行了重新定义和总结.提出了多关系关联规则挖掘的一个框架,并对已有算法进行了分类.然后对各类代表性算法进行了描述、分析和对比,对尚存在的问题进行了分析和总结.最后,对该领域未来的研究工作提出了建议.

    • DNA序列数据挖掘技术

      2007, 18(11):2766-2781.

      摘要 (9263) HTML (0) PDF 849.06 K (14776) 评论 (0) 收藏

      摘要:DNA序列数据是一类重要的生物数据.研究DNA序列数据解读其含义是后基因组时代的主要研究任务.数据挖掘是目前最有效的数据分析手段之一,用于发现大量数据所隐含的各种规律,也是生物信息学采用的主要数据分析技术.将数据挖掘技术用于DNA序列数据分析,已得到了广泛关注和快速发展,并取得了许多研究成果.综述了DNA序列数据挖掘领域的研究状况和进展,提出了3个研究阶段:基于统计的挖掘方法应用阶段、一般化挖掘方法应用阶段和专门的DNA序列数据挖掘方法设计阶段.阐述了DNA序列数据挖掘的基础是序列相似性,评述了DNA序列数据挖掘领域所采用的关键技术,包括DNA序列模式、关联、聚类、分类和异常挖掘等,分析讨论了其相应的生物应用背景和意义.最后给出DNA序列数据挖掘进一步研究的热点问题,包括DNA序列数据新的存储和索引机制的设计、根据生物领域知识的数据挖掘新模型和算法的设计等.

    • 数据库中的知识隐藏

      2007, 18(11):2782-2799.

      摘要 (8578) HTML (0) PDF 1.09 M (8671) 评论 (0) 收藏

      摘要:伴随着数据共享、隐私保护、知识发现等多重需求而产生的PPDM(privacy preserving data mining),成为数据挖掘和信息安全领域近几年来的研究热点.PPDM中主要考虑两个层面的问题:一是敏感数据的隐藏与保护;二是数据中蕴涵的敏感知识的隐藏与保护(knowledge hiding in database,简称KHD).对目前的KHD技术进行分类和综述.首先介绍KHD产生的背景,然后着重讨论敏感关联规则隐藏技术和分类规则隐藏技术,接着探讨KHD方法的评估指标,最后归结出KHD后续研究的3个方向:数据修改技巧中基于目标距离的优化测度函数设计、数据重构技巧中的反向频繁项集挖掘以及基于数据抽样技巧的通用知识隐藏方法设计.

    • 缓冲交叉开关交换结构性能分析

      2007, 18(11):2800-2809.

      摘要 (3758) HTML (0) PDF 631.24 K (4894) 评论 (0) 收藏

      摘要:分析了一种缓冲交叉开关交换结构在突发流量到达下的性能.通过建立分析模型,给出了每个输入端口拥有单个或多个输入队列的缓冲交叉开关结构的饱和吞吐.结果显示,对于单输入队列结构而言,随着突发平均长度的增加,饱和吞吐迅速从1下降,并收敛于0.5.随着每个输入端口输入队列数目的增加,饱和吞吐率逐渐接近1.仿真实验验证了分析模型的准确性.该结果可以用于指导基于缓冲交叉开关的路由交换设备的优化设计.

    • Web集群中基于控制论的分布式QoS量化控制

      2007, 18(11):2810-2818.

      摘要 (4428) HTML (0) PDF 627.63 K (5266) 评论 (0) 收藏

      摘要:基于控制理论提出一种分布式Web集群QoS量化控制机制,具有分布控制,灵活、有效的系统化设计,高可扩展,高可用及易于部署等特点.系统的实现及实验验证了该方案的可行性和有效性.

    • 无结构P2P覆盖网络的拓扑优化

      2007, 18(11):2819-2829.

      摘要 (4048) HTML (0) PDF 694.73 K (5581) 评论 (0) 收藏

      摘要:研究了全分布无结构P2P(peer-to-peer)网络拓扑的最优化问题.通常认为,无结构P2P网络拓扑属于Power-Law结构.然而,Power-Law并非对所有应用都是最好的选择.首先研究了无结构P2P覆盖网络结构对无结构P2P搜索的影响,给出了结点度分布、访问频率模式和搜索成功率之间的关系.然后基于数据访问频率分布,给出了结点度的优化分布模型.实验结果表明,该无结构P2P拓扑优化结构在提高搜索成功率方面是有效的.该工作对构造合理的覆盖网络拓扑具有重要意义,同时将加深对无结构P2P环境下数据部署问题的认识.

    • 一种基于路由器矢量边采样的IP追踪技术

      2007, 18(11):2830-2840.

      摘要 (4041) HTML (0) PDF 856.92 K (6136) 评论 (0) 收藏

      摘要:提出了一种新型的边采样方法"路由器矢量边采样"(RVES),使得概率包标记(probability packet marking,简称PPM)设备容易实现和部署.在图论模型上,RVES以网络接口替代路由器作为顶点,以路由器"矢量边"替代传统采样边.该方法实施简单,标记概率的策略配置灵活,可以有效解决分布式拒绝服务(router's vector-edge-sampling,简称DDoS)攻击的重构问题.基于传统边采样的PPM相关技术依然适用于RVES方法.原理样机已经研制出并部署在Internet上.实验结果验证了该方法的有效性和可行性.

    • 一种基于控制流的程序行为扩展模型

      2007, 18(11):2841-2850.

      摘要 (4046) HTML (0) PDF 635.08 K (5205) 评论 (0) 收藏

      摘要:提出一种基于控制流的程序行为扩展模型EMPDA(extended model based on push down automaton).对控制流模型加入不变性约束扩展,该模型能够表达程序正常运行时所应保持的不变性质约束,增强了模型的监控能力;通过以实际应用区分系统调用重要性,将模型划分为核心模型和辅助模型,以降低模型整体消耗,提高模型学习效率.实验结果表明,该扩展模型较之原模型有更好的覆盖速度、误报率以及检测能力.

    • 一种支持多维资源描述的高效P2P路由算法

      2007, 18(11):2851-2862.

      摘要 (4099) HTML (0) PDF 757.07 K (5634) 评论 (0) 收藏

      摘要:在分析现有P2P(peer to peer)路由算法的基础上,提出了一种基于二阶矩定位、支持多维资源数据描述的高效资源路由算法--FAN(flabellate addressable network)路由算法.FAN算法将节点映射到统一的多维笛卡尔空间,并以节点相对空间原点的二阶矩作为子空间管理和资源搜索的依据.FAN路由算法具有O(log(N/k))的高路由效率,在节点加入和退出FAN网络时,更新路由信息的代价为O(klog(N/k)).实验结果表明,FAN路由算法具有路由效率高、维护代价小的优点,是一种P2P环境中支持多维资源数据描述的高效结构化资源路由算法.而且,目前部分基于CAN(content-addressable network)网络的改进算法也可以在FAN网络中适用,并获得更好的路由效率和更低的维护代价.

    • 基于帧间中频能量关系的自适应视频水印算法

      2007, 18(11):2863-2870.

      摘要 (4126) HTML (0) PDF 591.39 K (4930) 评论 (0) 收藏

      摘要:通过分析发现了视频帧间中频能量关系对于光度失真和空间同步失真的近似不变性.基于这种近似不变性,提出了一种可以根据人类的视觉系统特性,自适应地调整嵌入强度的鲁棒视频水印算法.实验表明,该算法可以有效抵抗光度失真、空间同步失真及其组合失真.

    • 基于证人不可区分的通用可复合安全并行可否认认证

      2007, 18(11):2871-2881.

      摘要 (4391) HTML (0) PDF 813.58 K (5941) 评论 (0) 收藏

      摘要:针对并行可否认认证问题,在UC(universally composable)安全框架中,基于WI(witness indistinguishable)提出了一种新的研究思路和解决方法.根据可否认认证的安全目标,形式化地建立了UC安全的并行可否认认证模型.利用可验证平滑投影哈希函数和非承诺加密体制,构造了一类新的并行可否认认证协议结构,基于确定性复合剩余假设和确定性Diffie-Hellman假设,实现了一个具体的协议方案.在公共参考串模型中,利用UC框架解决并行协议仿真问题,与定时假设和公共目录方案相比,不需要限定攻击者能力.新方案具备前向可否认性,是自适应攻击者UC安全的.不同于CCA2加密体制结构或多陷门承诺结构的并行可否认认证,协议效率得到了改善.

    • 结合信源特性与网络拥塞控制的可靠性视频传输算法

      2007, 18(11):2882-2892.

      摘要 (3743) HTML (0) PDF 914.33 K (5253) 评论 (0) 收藏

      摘要:提出了一种用于在无线网络中传输视频的结合信源特性及网络拥塞控制的鲁棒性算法.通过场景建模以及特性分析,将分级编码产生的所有码流层划分成不同的类型,并根据它们对网络拥塞控制的贡献以及对重建图像质量的贡献不同,将其分成两个不同的队列.系统根据不同的网络丢包状态(即丢包是由网络拥塞引起还是由无线信道的不可靠传输引起)动态地调整信源速率、不等错误保护强度以及拥塞控制策略.仿真结果表明,该方法与MPEG-4信源编码加固定速率Turbo码方法以及动态调整信源、信道编码速率加选择性丢I,B,P包的网络拥塞控制方法相比,能够提供更好的性能.

    • 对低轮AES-256的相关密钥-不可能差分密码分析

      2007, 18(11):2893-2901.

      摘要 (4118) HTML (0) PDF 547.38 K (5046) 评论 (0) 收藏

      摘要:研究AES-256抵抗相关密钥-不可能差分密码分析的能力.首先给出相关密钥的差分,该差分可以扩展到8轮(甚至更多轮)子密钥差分;然后构造出一个5.5轮的相关密钥不可能差分特征.最后,给出一个对7轮AES-256的攻击和4个对8轮AES-256的攻击.

    • 一种基于部件空间分布的三维模型检索方法

      2007, 18(11):2902-2913.

      摘要 (4362) HTML (0) PDF 905.90 K (5749) 评论 (0) 收藏

      摘要:三维形状分析是三维模型检索的关键问题.提出一种基于三维模型部件空间分布的形状特征描述方法.此方法的主要思想是依据认知心理学的理论,在描述对象形状时强调它的结构属性.首先将三维模型分割为若干个组成部件,每个部件用一个曲面片表示,然后采用曲面片的质心位置、面积占总面积的百分比的组合作为部件特征,最后将满足指定条件的部件特征的集合作为三维模型的形状特征.基于这一特征表示,给出了一种三维模型检索方法.该方法具有受模型精度和连通性影响较小、相似性度量的计算速度较快的优点.实验结果验证了该检索方法的有效性.

    • PDE曲面的Bézier逼近

      2007, 18(11):2914-2920.

      摘要 (4316) HTML (0) PDF 803.33 K (4801) 评论 (0) 收藏

      摘要:为了实现PDE(partial differential equation)曲面造型技术与传统CAD(computer aided design)造型系统的数据交换,基于约束优化的思想,给出了PDE曲面的Bézier逼近算法,并利用张量积Bézier曲面的细分性质对该算法进行了优化.所给出的计算实例及误差比较结果说明了该算法的有效性.

    • 基于角色几何碰撞体估计的实时服装仿真

      2007, 18(11):2921-2931.

      摘要 (4893) HTML (0) PDF 847.66 K (5499) 评论 (0) 收藏

      摘要:提出了一种快速处理三维服装仿真中角色与服装碰撞的方法.该方法能够满足交互式实时仿真环境的需求.在预处理阶段,根据蒙皮动画的特点,将角色的几何形状以球和简化凸包等简单碰撞体进行估计.在实时模拟阶段,这些碰撞体跟随骨架运动并代替角色模型网格完成与虚拟服装之间的碰撞处理.此外,为了能够快速计算碰撞响应信息,该方法还利用外围映射机制进一步开发了相交测试的空间局部性.实验结果表明,应用该方法可以有效避免衣片与角色模型之间的相互穿透,同时大幅度地减少碰撞处理计算量.实时仿真系统对于复杂服装网格仍然保持了较高的模拟帧速率.

    • 一种基于非对称逆布局模型的彩色图像表示方法

      2007, 18(11):2932-2941.

      摘要 (4265) HTML (0) PDF 962.40 K (5740) 评论 (0) 收藏

      摘要:借助于Packing问题的思想,提出了一种基于非对称逆布局的模式表示模型(non-symmetry and anti- packing pattern representation model,简称NAM)的彩色图像表示方法.通过描述NAM和彩色图像的二进制位平面分解(binary-bit plane decomposition,简称BPD)方法,给出了一种全新的基于NAM的彩色图像表示算法,并对算法的总数据量进行了分析.理论分析和实验结果均表明,与流行的基于分层结构的线性四元树的彩色图像表示方法相比,基于NAM的表示方法能够更有效地减少数据存储空间,是彩色图像模式表示的一种良好方法.这种方法可以应用于彩色图像模式表示的各个方面,在降低存储空间、提高传输速度、加快处理过程、模式匹配等方面具有良好的理论参考意义和实际应用价值.

    • >综述文章
    • P2P视频点播内容分发策略

      2007, 18(11):2942-2954.

      摘要 (8477) HTML (0) PDF 922.41 K (10390) 评论 (0) 收藏

      摘要:视频点播目前已成为对等(peer-to-peer,简称P2P)网络中一项重要的应用,引起了人们的不少研究兴趣.由于P2P网络能够为VoD(video-on-demand)应用的大规模实现提供底层网络的支持,许多正在出现的P2P VoD分发策略都能够提供在P2P网络中最基本的数据传输方式.对以往主要的P2P VoD内容分发策略进行了总结和概括.首先介绍了设计P2P VoD策略的相关重要问题,并把策略根据内容分发方式的不同分成4种类型.最后讨论了它们的应用层性能,并提出未来可以延续的工作.

    • 面向多投影显示墙的画面校正技术

      2007, 18(11):2955-2964.

      摘要 (4676) HTML (0) PDF 720.26 K (6296) 评论 (0) 收藏

      摘要:多投影显示墙是缓解对超高分辨率显示屏幕不断增长的需求与单台显示设备分辨率有限性之间矛盾的有效手段,但目前还缺乏规范化的模式和方法以支持高精度、高可靠性的画面校正.提出一种颜色校正方案以解决上述问题.首先介绍多投影显示墙画面校正中存在的主要问题和现有的解决方法;在此基础上,给出了多投影显示墙的画面校正流程和几何校正方法;然后讨论了多投影显示墙画面校正结果的评价标准,提出了投影仪的广义颜色模型和基于搜索技术的视觉无缝方法.该方案使用数码相机实现了高精度的视觉无缝画面校正,从而提高了构造多投影显示墙的效率并降低了维护成本.校正结果在多种类型的投影墙系统中得到验证和应用,对指导多投影显示墙的搭建和维护具有较高的理论与实践价值.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编:100190
  • 电话:010-62562563
  • 电子邮箱:jos@iscas.ac.cn
  • 网址:https://www.jos.org.cn
  • 刊号:ISSN 1000-9825
  •           CN 11-2560/TP
  • 国内定价:70元
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号