2005年第16卷第5期文章目次
2005, 16(5):643-651.
摘要:
计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.
计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.
2005, 16(5):652-658.
摘要:
为了解决计算资源和高速网络流量之间的矛盾,需要对IP流进行抽样或负载均衡等处理,而哈希算法是资源代价的核心.首先提出评价哈希算法性能的随机测度;其次从理论上证明比特之间异或运算和位移运算能够提高哈希值的随机特性,提出比特流之间哈希算法的原则;然后分析IP报文的4个字段:源IP、宿IP、源端口和宿端口的特性,由此提出相关的哈希算法;最后使用CERNET主干流量和PMA的数据验证算法的性能,并与IPSX和CRC32算法进行比较.研究表明,基于异或、位移原则的比特流哈希算法的执行效率和哈希值的均匀性两方面具有较好的性质,能够满足高速网络流量测量需求.
为了解决计算资源和高速网络流量之间的矛盾,需要对IP流进行抽样或负载均衡等处理,而哈希算法是资源代价的核心.首先提出评价哈希算法性能的随机测度;其次从理论上证明比特之间异或运算和位移运算能够提高哈希值的随机特性,提出比特流之间哈希算法的原则;然后分析IP报文的4个字段:源IP、宿IP、源端口和宿端口的特性,由此提出相关的哈希算法;最后使用CERNET主干流量和PMA的数据验证算法的性能,并与IPSX和CRC32算法进行比较.研究表明,基于异或、位移原则的比特流哈希算法的执行效率和哈希值的均匀性两方面具有较好的性质,能够满足高速网络流量测量需求.
2005, 16(5):659-668.
摘要:
布尔与数值变量相混合的约束问题有着广泛的应用,但是当约束中的数值变量间存在非线性关系时该问题求解起来十分困难.目前的许多求解方法都是不完备的,即这些方法不能完全肯定某些包含非线性数值表达式的约束是否能够成立.针对这种问题,提出了将非线性数值约束转化为特殊形式的优化问题,采用全局优化算法对其进行求解的方法.已经实现了一个基于此方法的原型工具.实验结果表明,该方法能够有效地求解非线性混合约束问题,并且总能够得到该约束条件是否可满足的结果.
布尔与数值变量相混合的约束问题有着广泛的应用,但是当约束中的数值变量间存在非线性关系时该问题求解起来十分困难.目前的许多求解方法都是不完备的,即这些方法不能完全肯定某些包含非线性数值表达式的约束是否能够成立.针对这种问题,提出了将非线性数值约束转化为特殊形式的优化问题,采用全局优化算法对其进行求解的方法.已经实现了一个基于此方法的原型工具.实验结果表明,该方法能够有效地求解非线性混合约束问题,并且总能够得到该约束条件是否可满足的结果.
2005, 16(5):669-675.
摘要:
目前存在的自动曲面简化算法在低分辨率的状态下往往忽略模型的重要几何特征,如尖角或者曲率大的区域,从而导致视觉上的退化.在Garland简化算法的基础上,引入尖特征度的概念,并将其加入到误差测度中,从而改变了边折叠顺序.简化模型不仅保留了模型的重要几何特征,而且合理分配三角网格,在曲率大的区域稠密,在平坦区域稀疏,简化效果更好.
目前存在的自动曲面简化算法在低分辨率的状态下往往忽略模型的重要几何特征,如尖角或者曲率大的区域,从而导致视觉上的退化.在Garland简化算法的基础上,引入尖特征度的概念,并将其加入到误差测度中,从而改变了边折叠顺序.简化模型不仅保留了模型的重要几何特征,而且合理分配三角网格,在曲率大的区域稠密,在平坦区域稀疏,简化效果更好.
2005, 16(5):676-683.
摘要:
现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m-1的扫描窗口.在每个扫描窗口内,算法批量地尝试m个可能位置,首先使用反向后缀自动机从窗口中间位置向前扫描模式前缀;若成功,则再使用正向有限状态自动机从中间位置向后扫描剩余的模式后缀.分析证明,LDM算法的最差、最好、平均时间复杂度分别达到了理论最好结果:O(n),O(n/m),O(n(1ogσm)/m).实际性能测试也验证了平均时间复杂度最优这一理论结果.而且,对于在较大字母表下查找短模式的情况,LDM算法速度在被测试算法中最快.总之,LDM算法不但适合进行离线模式匹配,而且还特别适合需要进行在线高速匹配的应用.
现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m-1的扫描窗口.在每个扫描窗口内,算法批量地尝试m个可能位置,首先使用反向后缀自动机从窗口中间位置向前扫描模式前缀;若成功,则再使用正向有限状态自动机从中间位置向后扫描剩余的模式后缀.分析证明,LDM算法的最差、最好、平均时间复杂度分别达到了理论最好结果:O(n),O(n/m),O(n(1ogσm)/m).实际性能测试也验证了平均时间复杂度最优这一理论结果.而且,对于在较大字母表下查找短模式的情况,LDM算法速度在被测试算法中最快.总之,LDM算法不但适合进行离线模式匹配,而且还特别适合需要进行在线高速匹配的应用.
2005, 16(5):684-690.
摘要:
Fork-Join任务图是一种并行处理的基本结构.虽然许多算法在任务满足某些条件时能产生最优调度,但往往没有考虑节省处理器个数和减少任务集的总完成时间,从而降低算法的加速比和效率.因此,提出一种基于任务复制的平衡调度算法,其时间复杂度为O(vq+vlogv),v和q分别表示任务集中任务的个数和使用的处理器个数.通过分析已用处理器的负载和空闲时间段,把任务尽量分配到已用的处理器上以均衡负载,从而提高其利用率.实验结果表明,该算法的加速比和总体效率优于其他算法.因此,该算法对于高性能应用程序的调度是一个较好的选择.
Fork-Join任务图是一种并行处理的基本结构.虽然许多算法在任务满足某些条件时能产生最优调度,但往往没有考虑节省处理器个数和减少任务集的总完成时间,从而降低算法的加速比和效率.因此,提出一种基于任务复制的平衡调度算法,其时间复杂度为O(vq+vlogv),v和q分别表示任务集中任务的个数和使用的处理器个数.通过分析已用处理器的负载和空闲时间段,把任务尽量分配到已用的处理器上以均衡负载,从而提高其利用率.实验结果表明,该算法的加速比和总体效率优于其他算法.因此,该算法对于高性能应用程序的调度是一个较好的选择.
2005, 16(5):691-699.
摘要:
提出了一种基于样本学习的协调颜色自动生成及搭配方法,并在此基础上开发了一个面向办公应用的自动配色方案创作与应用系统.该系统可以根据用户给定的彩色图片或者图案(例如公司的标志或者产品商标)自动提取其主要颜色,并在此基础上自动生成与之相协调的一组颜色,并通过使用智能优化算法给出合理的配色方案.实验表明,利用该算法生成的配色方案非常协调和合理,能够满足用户的个性化配色的需求.
提出了一种基于样本学习的协调颜色自动生成及搭配方法,并在此基础上开发了一个面向办公应用的自动配色方案创作与应用系统.该系统可以根据用户给定的彩色图片或者图案(例如公司的标志或者产品商标)自动提取其主要颜色,并在此基础上自动生成与之相协调的一组颜色,并通过使用智能优化算法给出合理的配色方案.实验表明,利用该算法生成的配色方案非常协调和合理,能够满足用户的个性化配色的需求.
2005, 16(5):700-707.
摘要:
指代消解在自然语言处理中起着越来越重要的作用.许多自然语言处理应用系统都需要高效、鲁棒的指代消解策略.然而,传统的指代消解方法需要用到句法知识、语义知识、上下文知识,甚至领域知识等多级知识,在目前的自然语言处理水平下,要有效获取这些知识是相当困难的.结合汉语的特点,提出了一种弱化语言知识的人称代词消解方法,仅仅用到了单复数特征、性别特征和语法角色特征.该方法主要分为两步,首先,利用这3种特征的简单约束关系,过滤与人称代词特征不一致的词,并形成可能的先行语候选集;然后,使用一个权值算法,计算候选的权值,并将最高权值的候选作为代词最终的先行语.权值算法并不是枚举式地计算每个候选的权值,而会通过动态评测机制,在合适的条件下自动终止计算,因而有效地控制了计算复杂度.此外,该方法不需要对文本进行深层的分析处理,实现起来也很容易.测试结果表明,该方法达到了满意效果.
指代消解在自然语言处理中起着越来越重要的作用.许多自然语言处理应用系统都需要高效、鲁棒的指代消解策略.然而,传统的指代消解方法需要用到句法知识、语义知识、上下文知识,甚至领域知识等多级知识,在目前的自然语言处理水平下,要有效获取这些知识是相当困难的.结合汉语的特点,提出了一种弱化语言知识的人称代词消解方法,仅仅用到了单复数特征、性别特征和语法角色特征.该方法主要分为两步,首先,利用这3种特征的简单约束关系,过滤与人称代词特征不一致的词,并形成可能的先行语候选集;然后,使用一个权值算法,计算候选的权值,并将最高权值的候选作为代词最终的先行语.权值算法并不是枚举式地计算每个候选的权值,而会通过动态评测机制,在合适的条件下自动终止计算,因而有效地控制了计算复杂度.此外,该方法不需要对文本进行深层的分析处理,实现起来也很容易.测试结果表明,该方法达到了满意效果.
2005, 16(5):708-717.
摘要:
提出一种基于视差点的方法来解决在高质量立体视差图生成过程中所出现的遮挡问题.首先证明同名核线对应的视差函数曲线可近似为一条分段直线,然后在此基础上引出视差点的概念.在视差点的结构中利用两个参数分别描述左右遮挡量,使得所提出的方法能够很好地解决遮挡问题.通过分析视差点及其邻域的灰度特性,提出一种分层假设证实和Marquardt-Levenberg(M-L)算法相结合的方法从同名核线图像中提取出候选视差点,然后采用不定期的动态规划(dynamic programming,简称DP)算法获得核线最优的视差函数.利用国际标准数据对提出的方法进行了测试,并与其他方法作比较,实验结果表明,它的匹配效果是目前核线最优方法中最好的,仅差于几种优秀的全局最优方法,但其计算复杂度要远低于全局的方法.
提出一种基于视差点的方法来解决在高质量立体视差图生成过程中所出现的遮挡问题.首先证明同名核线对应的视差函数曲线可近似为一条分段直线,然后在此基础上引出视差点的概念.在视差点的结构中利用两个参数分别描述左右遮挡量,使得所提出的方法能够很好地解决遮挡问题.通过分析视差点及其邻域的灰度特性,提出一种分层假设证实和Marquardt-Levenberg(M-L)算法相结合的方法从同名核线图像中提取出候选视差点,然后采用不定期的动态规划(dynamic programming,简称DP)算法获得核线最优的视差函数.利用国际标准数据对提出的方法进行了测试,并与其他方法作比较,实验结果表明,它的匹配效果是目前核线最优方法中最好的,仅差于几种优秀的全局最优方法,但其计算复杂度要远低于全局的方法.
2005, 16(5):718-726.
摘要:
面部特征标定是人脸识别中的一个关键问题.提出了一种基于样例学习的面部特征自动标定(人脸形状自动提取)方法.该方法是基于下面假设提出来的:人脸图像差和形状差之间存在一种近似的线性关系--相似的人脸图像在较大程度上蕴涵着相似的形状.因此,给定标注了特征点的人脸图像学习集,则任意新的输入人脸图像的面部形状可以采用如下方法估计:测量该人脸图像和训练集中图像的相似度,并将同样的相似度用于该人脸图像形状的重建.即:如果输入人脸图像可以表示为训练图像的优化的线性组合,那么同样的线性组合系数就可以直接用于训练集对应形状的线性组合从而得到输入人脸图像的形状.实验表明,该算法相对于其他传统的特征标定算法具有可比的精度和较快的速度.并且,还将此算法扩展到了多姿态情况下,实现了多姿态人脸图像形状的自动提取.
面部特征标定是人脸识别中的一个关键问题.提出了一种基于样例学习的面部特征自动标定(人脸形状自动提取)方法.该方法是基于下面假设提出来的:人脸图像差和形状差之间存在一种近似的线性关系--相似的人脸图像在较大程度上蕴涵着相似的形状.因此,给定标注了特征点的人脸图像学习集,则任意新的输入人脸图像的面部形状可以采用如下方法估计:测量该人脸图像和训练集中图像的相似度,并将同样的相似度用于该人脸图像形状的重建.即:如果输入人脸图像可以表示为训练图像的优化的线性组合,那么同样的线性组合系数就可以直接用于训练集对应形状的线性组合从而得到输入人脸图像的形状.实验表明,该算法相对于其他传统的特征标定算法具有可比的精度和较快的速度.并且,还将此算法扩展到了多姿态情况下,实现了多姿态人脸图像形状的自动提取.
2005, 16(5):727-732.
摘要:
介绍了一种有效的彩色图像边缘特征提取算法,提出了一种新的边缘方向编码--双轴对称方向编码,利用多重交叉验证的ROC(receiver operating characteristic)曲线对基于颜色及其边缘直方图的SVM(support vector machine)人脸检测进行平均性能评价.实验结果表明,图像颜色边缘特征比灰度边缘特征具有明显优势.通过分别与RGB三色直方图线性拼接,新的双轴对称边缘方向编码表现出比传统方向编码更好的SVM分类性能.利用颜色及其边缘直方图特征能够明显提高人脸检测性能,分辨出不同光照条件下、不同表情甚至部分遮挡的非深度旋转的彩色人脸.
介绍了一种有效的彩色图像边缘特征提取算法,提出了一种新的边缘方向编码--双轴对称方向编码,利用多重交叉验证的ROC(receiver operating characteristic)曲线对基于颜色及其边缘直方图的SVM(support vector machine)人脸检测进行平均性能评价.实验结果表明,图像颜色边缘特征比灰度边缘特征具有明显优势.通过分别与RGB三色直方图线性拼接,新的双轴对称边缘方向编码表现出比传统方向编码更好的SVM分类性能.利用颜色及其边缘直方图特征能够明显提高人脸检测性能,分辨出不同光照条件下、不同表情甚至部分遮挡的非深度旋转的彩色人脸.
2005, 16(5):733-743.
摘要:
在诸如机器人足球赛等典型的可分解马尔可夫决策过程(factored Markov decision process,简称FMDP)模型中,不同状态属性在不同的状态下,对于状态评估的影响程度是不同的,其中存在若干关键状态属性,能够唯一或近似判断当前状态的好坏.为了解决FMDP模型中普遍存在的"维数灾"问题,在效用函数非线性的情况下,通过对状态特征向量的提取近似状态效用函数,同时根据对FMDP模型的认知程度,从线性规划和再励学习两种求解角度分别进行约束不等式组的化简和状态效用函数的高维移植,从而达到降低计算复杂度,加快联合策略生成速度的目的.以机器人足球赛任意球战术配合为背景进行实验来验证基于状态特征向量的再励学习算法的有效性和学习结果的可移植性.与传统再励学习算法相比,基于状态特征向量的再励学习算法能够极大地加快策略的学习速度.但更重要的是,还可以将学习到的状态效用函数方便地移植到更高维的FMDP模型中,从而直接计算出联合策略而不需要重新进行学习.
在诸如机器人足球赛等典型的可分解马尔可夫决策过程(factored Markov decision process,简称FMDP)模型中,不同状态属性在不同的状态下,对于状态评估的影响程度是不同的,其中存在若干关键状态属性,能够唯一或近似判断当前状态的好坏.为了解决FMDP模型中普遍存在的"维数灾"问题,在效用函数非线性的情况下,通过对状态特征向量的提取近似状态效用函数,同时根据对FMDP模型的认知程度,从线性规划和再励学习两种求解角度分别进行约束不等式组的化简和状态效用函数的高维移植,从而达到降低计算复杂度,加快联合策略生成速度的目的.以机器人足球赛任意球战术配合为背景进行实验来验证基于状态特征向量的再励学习算法的有效性和学习结果的可移植性.与传统再励学习算法相比,基于状态特征向量的再励学习算法能够极大地加快策略的学习速度.但更重要的是,还可以将学习到的状态效用函数方便地移植到更高维的FMDP模型中,从而直接计算出联合策略而不需要重新进行学习.
2005, 16(5):744-753.
摘要:
提出了在输入-输出积空间中利用监督模糊聚类技术快速建立粗糙数据模型(rough data model,简称RDM)的一种方法.该方法将RDM模型的分类质量性能指标与具有良好特性的Gustafson-Kessel(G-K)聚类算法结合在一起,并通过引入数据对模糊类的推定隶属度的概念,给出了将模糊聚类模型转化为粗糙数据模型的方法,从而设计出一种通过迭代计算使目标函数最小的两个必要条件方程来获取RDM模型的有效算法,将Kowalczyk方法的多维搜索过程变为以聚类数目为参数的一维搜索,极大地减少了寻优时间.与传统的粗糙集理论和Kowalczyk方法相比,提出的方法具有更好的数据概括能力和噪声数据处理能力.最后,通过不同的数据集实验测试,结果表明了该方法的有效性.
提出了在输入-输出积空间中利用监督模糊聚类技术快速建立粗糙数据模型(rough data model,简称RDM)的一种方法.该方法将RDM模型的分类质量性能指标与具有良好特性的Gustafson-Kessel(G-K)聚类算法结合在一起,并通过引入数据对模糊类的推定隶属度的概念,给出了将模糊聚类模型转化为粗糙数据模型的方法,从而设计出一种通过迭代计算使目标函数最小的两个必要条件方程来获取RDM模型的有效算法,将Kowalczyk方法的多维搜索过程变为以聚类数目为参数的一维搜索,极大地减少了寻优时间.与传统的粗糙集理论和Kowalczyk方法相比,提出的方法具有更好的数据概括能力和噪声数据处理能力.最后,通过不同的数据集实验测试,结果表明了该方法的有效性.
2005, 16(5):754-760.
摘要:
建立柔性逻辑体系,既是现实世界复杂问题求解的需要,也是逻辑学发展的一种必然趋势.泛逻辑学是何华灿在探索复杂世界逻辑规律中建立起来的一个柔性逻辑体系.在分析其实现逻辑关系柔性化的思想和方法的基础上,探讨了概率逻辑关系柔性化的问题.理论上,概率逻辑是泛逻辑学的一个特例,因此应该能够在泛逻辑学框架内建立起柔性的概率逻辑体系.
建立柔性逻辑体系,既是现实世界复杂问题求解的需要,也是逻辑学发展的一种必然趋势.泛逻辑学是何华灿在探索复杂世界逻辑规律中建立起来的一个柔性逻辑体系.在分析其实现逻辑关系柔性化的思想和方法的基础上,探讨了概率逻辑关系柔性化的问题.理论上,概率逻辑是泛逻辑学的一个特例,因此应该能够在泛逻辑学框架内建立起柔性的概率逻辑体系.
2005, 16(5):761-770.
摘要:
最近涌现了各种进化方法来解决多目标优化问题,多数方法使用Pareto优胜关系作为选择策略而没有采用偏好信息.这些算法不能有效处理目标数目许多时的优化问题.通过在不同准则之间引入偏好来解决该问题,提出一种多目标调和遗传算法MOCGA(multi-objective concordance genetic algorithm).当同时待优化的目标数目增加时,根据决策者提供的信息使用弱优胜关系进行个体优劣的比较.这种算法被证明为能收敛至全局最优.对于目标数目为很多的优化问题,测试实验结果表明了这种新算法的有效性.
最近涌现了各种进化方法来解决多目标优化问题,多数方法使用Pareto优胜关系作为选择策略而没有采用偏好信息.这些算法不能有效处理目标数目许多时的优化问题.通过在不同准则之间引入偏好来解决该问题,提出一种多目标调和遗传算法MOCGA(multi-objective concordance genetic algorithm).当同时待优化的目标数目增加时,根据决策者提供的信息使用弱优胜关系进行个体优劣的比较.这种算法被证明为能收敛至全局最优.对于目标数目为很多的优化问题,测试实验结果表明了这种新算法的有效性.
16 隐式愿望及其形式化
2005, 16(5):771-778.
摘要:
隐式愿望的刻画是Agent理论研究中的一个重要课题.首先分析现有工作存在的问题,然后用逻辑语义学方法严格定义一种新的隐式愿望--pm-愿望后承,研究其主要性质并与相关工作进行比较,进而论证其合理性,包括符合直觉、有利于提高智能主体的自主性等等.
隐式愿望的刻画是Agent理论研究中的一个重要课题.首先分析现有工作存在的问题,然后用逻辑语义学方法严格定义一种新的隐式愿望--pm-愿望后承,研究其主要性质并与相关工作进行比较,进而论证其合理性,包括符合直觉、有利于提高智能主体的自主性等等.
2005, 16(5):779-785.
摘要:
讨论了基于模糊遗传机器学习机制的密歇根方法在多维分类问题上的应用及性能问题,并提出了一种新的模糊遗传学习方法.将每一模糊规则作为遗传算法中的一个个体,且具有相应的适应度函数值.在提取模糊规则的同时,还对每个属性维的模糊划分进行学习以获取较好的模糊集合参数.另外,该方法引入了基于相似性的选择机制,减轻了选择机制对低适应函数值个体造成的选择压力,保持了种群的多样性,从而有效地避免了遗传算法收敛到局部解的问题.实验结果表明,该方法在多维模糊分类器的构造问题上具有较高的正确分类率、适应性较好等性能.
讨论了基于模糊遗传机器学习机制的密歇根方法在多维分类问题上的应用及性能问题,并提出了一种新的模糊遗传学习方法.将每一模糊规则作为遗传算法中的一个个体,且具有相应的适应度函数值.在提取模糊规则的同时,还对每个属性维的模糊划分进行学习以获取较好的模糊集合参数.另外,该方法引入了基于相似性的选择机制,减轻了选择机制对低适应函数值个体造成的选择压力,保持了种群的多样性,从而有效地避免了遗传算法收敛到局部解的问题.实验结果表明,该方法在多维模糊分类器的构造问题上具有较高的正确分类率、适应性较好等性能.
18 中英文混合文章识别问题
2005, 16(5):786-798.
摘要:
当前,已经有大量为单一字符集(或语种)而设计的OCR(optical character recognition)分类器.同时,随着全球一体化,多语文档的出现越来越普遍.因此,设计多语文档处理系统势在必行.提出了一般性的解决方案:两项OCR技术、一个系统和语言判断.为了使研究工作具体化,实现了一个中英文混合文章处理系统.其中主要涉及了3个关键问题:系统流程控制、汉英语言区域分离和英文字符切分.与以往的系统相比,该系统增加了汉英语言区域分离模块,并将基于等间距性的新方法应用于该模块.为了验证本系统的有效性,综合以往的方法实现了另一个系统.实验结果表明,该系统的性能明显优于另一个系统,在杂志样和书籍样上的识别率分别从98.48%和98.68%提高到99.13%和99.25%.
当前,已经有大量为单一字符集(或语种)而设计的OCR(optical character recognition)分类器.同时,随着全球一体化,多语文档的出现越来越普遍.因此,设计多语文档处理系统势在必行.提出了一般性的解决方案:两项OCR技术、一个系统和语言判断.为了使研究工作具体化,实现了一个中英文混合文章处理系统.其中主要涉及了3个关键问题:系统流程控制、汉英语言区域分离和英文字符切分.与以往的系统相比,该系统增加了汉英语言区域分离模块,并将基于等间距性的新方法应用于该模块.为了验证本系统的有效性,综合以往的方法实现了另一个系统.实验结果表明,该系统的性能明显优于另一个系统,在杂志样和书籍样上的识别率分别从98.48%和98.68%提高到99.13%和99.25%.
2005, 16(5):799-809.
摘要:
将数据对象间的关联限制与K-means算法结合可以取得较好的效果,但由于划分是由K个中心决定的,每一类仅由一个中心决定,分隔的表示方法限制了算法效果的进一步提高.基于数据对象间的两类限制,定义了数据对象和集合间的两类关联,以及集合间的3类关联,在此基础上给出了结合限制的分隔模型.在模型中,基于集合间的正关联,多个子集中心可以用来表示同一类,使划分的表示可以更为灵活、精细.基于此模型,给出了相应的算法CKS(constrained K-meanswith subsets)来生成结合限制的分隔.对3个UCI数据集的实验结果显示:在准确率及健壮性上,CKS显著优于另一个结合关联限制的K-means类算法COP-K-means,与另一个代表性的算法CCL相比,也有相当优势;在时间代价上,CKS也有一定优势.
将数据对象间的关联限制与K-means算法结合可以取得较好的效果,但由于划分是由K个中心决定的,每一类仅由一个中心决定,分隔的表示方法限制了算法效果的进一步提高.基于数据对象间的两类限制,定义了数据对象和集合间的两类关联,以及集合间的3类关联,在此基础上给出了结合限制的分隔模型.在模型中,基于集合间的正关联,多个子集中心可以用来表示同一类,使划分的表示可以更为灵活、精细.基于此模型,给出了相应的算法CKS(constrained K-meanswith subsets)来生成结合限制的分隔.对3个UCI数据集的实验结果显示:在准确率及健壮性上,CKS显著优于另一个结合关联限制的K-means类算法COP-K-means,与另一个代表性的算法CCL相比,也有相当优势;在时间代价上,CKS也有一定优势.
2005, 16(5):810-818.
摘要:
大部分XML查询技术都是基于某种对XML树的编码方法.对XML树的编码,是指按照某种规则对XML树的每一个结点分配唯一的编码,目的是通过任意两个结点的编码,能够直接判断两个结点之间是否具有祖先后代关系.最常用的编码方法是区域编码方法(region based numbering scheme).然而,XML数据也会面临插入删除等更新问题.数据一旦更新,区域编码也要作相应的调整,才能保证基于这个编码的各种索引和查询算法的正确性.在编码的更新方面,目前研究得还不多.主要研究区域编码的更新问题,采用预留编码空间的方法,针对不同特征的XML数据和应用环境提出了一整套预留算法和编码更新算法,并做了大量的实验,检验这些算法的有效性.
大部分XML查询技术都是基于某种对XML树的编码方法.对XML树的编码,是指按照某种规则对XML树的每一个结点分配唯一的编码,目的是通过任意两个结点的编码,能够直接判断两个结点之间是否具有祖先后代关系.最常用的编码方法是区域编码方法(region based numbering scheme).然而,XML数据也会面临插入删除等更新问题.数据一旦更新,区域编码也要作相应的调整,才能保证基于这个编码的各种索引和查询算法的正确性.在编码的更新方面,目前研究得还不多.主要研究区域编码的更新问题,采用预留编码空间的方法,针对不同特征的XML数据和应用环境提出了一整套预留算法和编码更新算法,并做了大量的实验,检验这些算法的有效性.
2005, 16(5):819-826.
摘要:
WebGIS服务器向用户提供电子地图浏览服务.每一个请求/响应回合,服务器端都进行着具有多尺度特性的成批式数据访问.多尺度特性是指地图比例尺决定着地图显示内容的详略.基于R-tree的数据访问方法与多尺度性和成批性不相适应,存在"同级要素弱簇聚"和"I/O粒度偏小"两大问题,绘图数据访问效率不高.提出的多级R-tree能够解决上述两个问题.来自实验的统计数据表明,对于区域查询,基于多级R-tree的访问方法的效率明显高于基于R-tree索引的访问方法.使用多级R-tree能够有效地提高WebGIS服务器的响应速度.
WebGIS服务器向用户提供电子地图浏览服务.每一个请求/响应回合,服务器端都进行着具有多尺度特性的成批式数据访问.多尺度特性是指地图比例尺决定着地图显示内容的详略.基于R-tree的数据访问方法与多尺度性和成批性不相适应,存在"同级要素弱簇聚"和"I/O粒度偏小"两大问题,绘图数据访问效率不高.提出的多级R-tree能够解决上述两个问题.来自实验的统计数据表明,对于区域查询,基于多级R-tree的访问方法的效率明显高于基于R-tree索引的访问方法.使用多级R-tree能够有效地提高WebGIS服务器的响应速度.
2005, 16(5):827-837.
摘要:
XML查询语言将复杂路径表达式作为核心内容.为了加速路径表达式处理,基于路径分解和结构连接操作的处理策略需要更深入的研究.以目标节点为导向的XML路径查询处理框架被提了出来.该方法利用了扩展基本操作来减少连接操作的数目.在路径分解和查询计划选择的过程中,利用查询树中的目标节点来避免中间结果的传递.除了分解规则和策略以外,提出了一组扩展的基本操作和实现算法.初步的实验结果显示,该方法具有良好的性能.它为路径查询处理提供了更多的选择.
XML查询语言将复杂路径表达式作为核心内容.为了加速路径表达式处理,基于路径分解和结构连接操作的处理策略需要更深入的研究.以目标节点为导向的XML路径查询处理框架被提了出来.该方法利用了扩展基本操作来减少连接操作的数目.在路径分解和查询计划选择的过程中,利用查询树中的目标节点来避免中间结果的传递.除了分解规则和策略以外,提出了一组扩展的基本操作和实现算法.初步的实验结果显示,该方法具有良好的性能.它为路径查询处理提供了更多的选择.
2005, 16(5):838-845.
摘要:
讨论了时态变量"Now"的基本语义,即Now不仅可以表示当前时间,还能表示过去时间和将来时间.在语义分析的基础上,讨论了带变量时态关系运算中需要解决的基本问题,即变量Now值的确定问题,研究了相应时态关系数据操作,建立了带变量时态关系代数系统.
讨论了时态变量"Now"的基本语义,即Now不仅可以表示当前时间,还能表示过去时间和将来时间.在语义分析的基础上,讨论了带变量时态关系运算中需要解决的基本问题,即变量Now值的确定问题,研究了相应时态关系数据操作,建立了带变量时态关系代数系统.
2005, 16(5):846-856.
摘要:
深入了解Internet拓扑的结构性质有利于更好地设计和发展Internet.由于Internet规模巨大,以及获得完整的路由器级Internet拓扑方面的困难,目前无法研究整个路由器级Internet拓扑.因此,分别研究每个国家级或跨国因特网服务供应商(Internet service provider,简称ISP)网络拓扑结构成为了解Internet拓扑特征的一种可选方法.以中国教育科研网为例,简要描述了多点测量其路由器级拓扑结构的测量结果.分析了该实例拓扑图的节点度分布特征、较大特征值的有关性质以及谱密度分布特征.分析了该实例拓扑图的无符号拉普拉斯谱(SLS)、规格化拉普拉斯谱(NLS)以及群集系数等度量特征.分析结果表明,大型ISP拓扑确实具有某些幂律特征;不同于自治系统级拓扑的情形,对ISP拓扑的节点度补累积分布来说,幂律分布未必拟合得最好;ISP拓扑是一种无标度图,但不符合Barabasi-Albert(BA)生长模型;SLS和NLS具有区分不同的路由器级拓扑结构的能力;Internet路由器级拓扑的发展可能遵循一种不同于BA模型的生长过程.
深入了解Internet拓扑的结构性质有利于更好地设计和发展Internet.由于Internet规模巨大,以及获得完整的路由器级Internet拓扑方面的困难,目前无法研究整个路由器级Internet拓扑.因此,分别研究每个国家级或跨国因特网服务供应商(Internet service provider,简称ISP)网络拓扑结构成为了解Internet拓扑特征的一种可选方法.以中国教育科研网为例,简要描述了多点测量其路由器级拓扑结构的测量结果.分析了该实例拓扑图的节点度分布特征、较大特征值的有关性质以及谱密度分布特征.分析了该实例拓扑图的无符号拉普拉斯谱(SLS)、规格化拉普拉斯谱(NLS)以及群集系数等度量特征.分析结果表明,大型ISP拓扑确实具有某些幂律特征;不同于自治系统级拓扑的情形,对ISP拓扑的节点度补累积分布来说,幂律分布未必拟合得最好;ISP拓扑是一种无标度图,但不符合Barabasi-Albert(BA)生长模型;SLS和NLS具有区分不同的路由器级拓扑结构的能力;Internet路由器级拓扑的发展可能遵循一种不同于BA模型的生长过程.
2005, 16(5):857-868.
摘要:
作为一种全新的信息获取和处理技术,无线传感器网络可以在广泛的应用领域内实现复杂的大规模监测和追踪任务,而网络自身定位是大多数应用的基础.介绍了无线传感器网络自身定位系统和算法的性能评价标准和分类方法,着重综述了近年来该领域具有代表性的算法及系统的原理和特点,并指出未来的研究方向.
作为一种全新的信息获取和处理技术,无线传感器网络可以在广泛的应用领域内实现复杂的大规模监测和追踪任务,而网络自身定位是大多数应用的基础.介绍了无线传感器网络自身定位系统和算法的性能评价标准和分类方法,着重综述了近年来该领域具有代表性的算法及系统的原理和特点,并指出未来的研究方向.
2005, 16(5):869-877.
摘要:
由于XML(extensible markup language)本身是自描述的,所以XML数据流中存在大量冗余的结构信息.如何压缩XML数据流,使得在减少网络传输代价的同时有效支持压缩数据流上的查询处理,成为一个新的研究领域.目前已有的XML数据压缩技术,都需要扫描数据多遍,或者不支持数据流之上的实时查询处理.提出了一种XML数据流的压缩技术XSC(XML stream compression),实时完成XML数据流的压缩和解压缩,XSC动态构建XML元素事件序列字典并输出相关索引,能够根据XML数据流所遵从的DTD,产生XML元素事件序列图,在压缩扫描之前,产生更加合理的结构序列编码.压缩的XML数据流能够直接解压缩用于XPath的执行.实验表明,在XML数据流环境中,XSC在数据压缩率和压缩时间上要优于传统算法.同时,在压缩数据之上查询的执行代价是可以接受的.
由于XML(extensible markup language)本身是自描述的,所以XML数据流中存在大量冗余的结构信息.如何压缩XML数据流,使得在减少网络传输代价的同时有效支持压缩数据流上的查询处理,成为一个新的研究领域.目前已有的XML数据压缩技术,都需要扫描数据多遍,或者不支持数据流之上的实时查询处理.提出了一种XML数据流的压缩技术XSC(XML stream compression),实时完成XML数据流的压缩和解压缩,XSC动态构建XML元素事件序列字典并输出相关索引,能够根据XML数据流所遵从的DTD,产生XML元素事件序列图,在压缩扫描之前,产生更加合理的结构序列编码.压缩的XML数据流能够直接解压缩用于XPath的执行.实验表明,在XML数据流环境中,XSC在数据压缩率和压缩时间上要优于传统算法.同时,在压缩数据之上查询的执行代价是可以接受的.
2005, 16(5):878-885.
摘要:
传统的TCP协议在有线网络中能够良好地工作,但用于无线自组织网络时则性能有所下降.其原因在于,传统的TCP协议无法分辨网络丢包原因,如网络拥塞、链路断开、信道错误或者链路改变.为了提高TCP协议在无线自组织网络中的性能,提出了一种TCP协议的改进方案TCP Freeze-Probing.该方案是一种端到端方法,不需要网络中间节点的反馈合作同时,提出了一种基于TCP Freeze-Probing的吞吐量模型并利用仿真对模型进行了验证.分析和仿真结果表明,该方案能够有效地改进TCP在无线自组织网络的性能.
传统的TCP协议在有线网络中能够良好地工作,但用于无线自组织网络时则性能有所下降.其原因在于,传统的TCP协议无法分辨网络丢包原因,如网络拥塞、链路断开、信道错误或者链路改变.为了提高TCP协议在无线自组织网络中的性能,提出了一种TCP协议的改进方案TCP Freeze-Probing.该方案是一种端到端方法,不需要网络中间节点的反馈合作同时,提出了一种基于TCP Freeze-Probing的吞吐量模型并利用仿真对模型进行了验证.分析和仿真结果表明,该方案能够有效地改进TCP在无线自组织网络的性能.
2005, 16(5):886-893.
摘要:
了解网络内部链路特征对运维大型IP网络至关重要.前人在假定固定路由条件下采用端到端主动测量的方式从网络边缘推测网络内部链路行为特征.由于网络中存在导致随机路由的负载均衡设备,使以前的主动测量方法无法实施.采用累计生成函数和随机过程方法解决随机路由条件下的网络内部链路时延推测问题.仿真结果表明,算法可以很好地解决随机路由下的内部链路时延推测问题.根据链路时延分布,可以用来判决瓶颈链路,为网络运维提供极具价值的参考.
了解网络内部链路特征对运维大型IP网络至关重要.前人在假定固定路由条件下采用端到端主动测量的方式从网络边缘推测网络内部链路行为特征.由于网络中存在导致随机路由的负载均衡设备,使以前的主动测量方法无法实施.采用累计生成函数和随机过程方法解决随机路由条件下的网络内部链路时延推测问题.仿真结果表明,算法可以很好地解决随机路由下的内部链路时延推测问题.根据链路时延分布,可以用来判决瓶颈链路,为网络运维提供极具价值的参考.
2005, 16(5):894-902.
摘要:
针对网络海量存储系统的应用需求,提出了一个基于Peer-to-Peer思想的对象分布和定位模型,能够支持众多节点自发组成的动态网络结构.对该模型进行了比较完整的论述,依次建立了全局映射关系、路由表、对象定位和路由算法、对象索引分布方案和节点加入、退出时的维护算法,特别是提出了新的对象索引分布方案,提高了对象的平均访问成功率,围绕此方案,对模型的各组成部分进行了改进,实现了提出的5个性质.最后,通过建立模拟程序,验证了模型的分析预测结果,能够提供均衡的负载分布和较好的对象访问效率.
针对网络海量存储系统的应用需求,提出了一个基于Peer-to-Peer思想的对象分布和定位模型,能够支持众多节点自发组成的动态网络结构.对该模型进行了比较完整的论述,依次建立了全局映射关系、路由表、对象定位和路由算法、对象索引分布方案和节点加入、退出时的维护算法,特别是提出了新的对象索引分布方案,提高了对象的平均访问成功率,围绕此方案,对模型的各组成部分进行了改进,实现了提出的5个性质.最后,通过建立模拟程序,验证了模型的分析预测结果,能够提供均衡的负载分布和较好的对象访问效率.
2005, 16(5):903-910.
摘要:
主动队列管理是一个非常活跃的研究领域,相对于丢尾算法,AQM(active queue management)能够提供更短的平均队列延迟和更高的带宽利用率.虽然PI(proporrional integral)主动队列管理算法的性能优于RED(random early detection)算法,但是PI算法的收敛速度比较慢.以PI算法为基础提出了一种自适应PI算法API(adaptive proportional integral).API通过实时测量链路的报文丢失率,获得当前的负载信息,然后动态设置PI算法中的有关参数.通过ns-2模拟表明,相对于PI及其改进算法PIP(proportional integral based series compensation and position feedback compensation),API具有更快的收敛速度和更小的队列抖动.
主动队列管理是一个非常活跃的研究领域,相对于丢尾算法,AQM(active queue management)能够提供更短的平均队列延迟和更高的带宽利用率.虽然PI(proporrional integral)主动队列管理算法的性能优于RED(random early detection)算法,但是PI算法的收敛速度比较慢.以PI算法为基础提出了一种自适应PI算法API(adaptive proportional integral).API通过实时测量链路的报文丢失率,获得当前的负载信息,然后动态设置PI算法中的有关参数.通过ns-2模拟表明,相对于PI及其改进算法PIP(proportional integral based series compensation and position feedback compensation),API具有更快的收敛速度和更小的队列抖动.
2005, 16(5):911-915.
摘要:
顾名思义,代理签名让原始签名者可以将其数字签名权力委托给代理签名者,使其能够代理原始签名者签发指定的数字消息;盲签名使用户能将给定的消息让别人签发,而又不泄漏任何有关的信息给签名者.在Schorr盲签名的基础上,谭作文等结合代理签名和盲签名提出了一个基于离散对数的代理盲签名方案.研究表明该方案是不安全的.它既受到广泛伪造攻击,又是可连接的.我们还进一步说明,原文安全性定理的证明是不正确的.
顾名思义,代理签名让原始签名者可以将其数字签名权力委托给代理签名者,使其能够代理原始签名者签发指定的数字消息;盲签名使用户能将给定的消息让别人签发,而又不泄漏任何有关的信息给签名者.在Schorr盲签名的基础上,谭作文等结合代理签名和盲签名提出了一个基于离散对数的代理盲签名方案.研究表明该方案是不安全的.它既受到广泛伪造攻击,又是可连接的.我们还进一步说明,原文安全性定理的证明是不正确的.
2005, 16(5):916-930.
摘要:
通过使用peer-to-peer(P2P)计算模式在Internet物理拓扑基础上建立一个称为P2P覆盖网络(P2Poverlay network)的虚拟拓扑结构,有效地建立起一个基于Internet的完全分布式自组织网络路由模型--分级集中式自组织网络路由模型(hierarchical aggregation self-organizing network,简称HASN).分别描述了HASN路由模型的构建目标和体系结构,并详细分析了HASN采用的基于P2P计算模式的分布式命名、路由发现和更新算法HASN Scale,并在仿真实验的基础上,对HASN路由模型的性能进行了验证.
通过使用peer-to-peer(P2P)计算模式在Internet物理拓扑基础上建立一个称为P2P覆盖网络(P2Poverlay network)的虚拟拓扑结构,有效地建立起一个基于Internet的完全分布式自组织网络路由模型--分级集中式自组织网络路由模型(hierarchical aggregation self-organizing network,简称HASN).分别描述了HASN路由模型的构建目标和体系结构,并详细分析了HASN采用的基于P2P计算模式的分布式命名、路由发现和更新算法HASN Scale,并在仿真实验的基础上,对HASN路由模型的性能进行了验证.
2005, 16(5):931-939.
摘要:
着重研究了Internet上MPEG-4 FGS(fine grained scalable)视频流的自适应平滑传输,其主要目的在于,在网络带宽变化的情况下,提供稳定的视频回放质量.提出了一种新的基于TFRC(TCP-friendly rate control)的MPEG-4 FGS端到端视频流传输系统框架,在此框架的基础上,首先假设完整的可用带宽变化已知,并且提出了一种离线的自适应平滑算法.此后,给出一种基于改进的ARAR(autoregressive autoregressive)预测技术的在线自适应平滑算法.最后,以NS-2为实验平台进行了模拟实验.模拟实验表明,提出的离线和在线自适应平滑算法可以充分利用可用网络带宽,并且能够在可用网络带宽持续波动的情况下保证接收方的回放尽可能地平稳,从而达到获得最佳视觉效果的目的.
着重研究了Internet上MPEG-4 FGS(fine grained scalable)视频流的自适应平滑传输,其主要目的在于,在网络带宽变化的情况下,提供稳定的视频回放质量.提出了一种新的基于TFRC(TCP-friendly rate control)的MPEG-4 FGS端到端视频流传输系统框架,在此框架的基础上,首先假设完整的可用带宽变化已知,并且提出了一种离线的自适应平滑算法.此后,给出一种基于改进的ARAR(autoregressive autoregressive)预测技术的在线自适应平滑算法.最后,以NS-2为实验平台进行了模拟实验.模拟实验表明,提出的离线和在线自适应平滑算法可以充分利用可用网络带宽,并且能够在可用网络带宽持续波动的情况下保证接收方的回放尽可能地平稳,从而达到获得最佳视觉效果的目的.
2005, 16(5):940-945.
摘要:
线性复杂度是衡量序列密码学强度的重要指标,设计具有大的线性复杂度和k-error线性复杂度的序列是密码学和通信中的热点问题.Niederreiter首次发现了Fq上许多满足这个要求的周期序列.通过序列的广义离散傅立叶变换构造了一些Fq上具有极大1-error线性复杂度的周期序列,这些结果远远优于已知的结果.
线性复杂度是衡量序列密码学强度的重要指标,设计具有大的线性复杂度和k-error线性复杂度的序列是密码学和通信中的热点问题.Niederreiter首次发现了Fq上许多满足这个要求的周期序列.通过序列的广义离散傅立叶变换构造了一些Fq上具有极大1-error线性复杂度的周期序列,这些结果远远优于已知的结果.
2005, 16(5):946-959.
摘要:
基于流量需求的BGP最优路径选择是域间流量工程研究的一个问题.其中瓶颈区域的判定可为域间流量工程的决策过程提供重要的启发信息.然而,瓶颈区域的判定是NP难问题.在同时考虑域内链路和域间链路的前提下,提出多项式时间的基于流量需求的瓶颈区域的预测算法.在此基础上,系统地研究了流量、拓扑结构与瓶颈区域间的关系.模拟实验表明,预测算法的准确性超过90%,研究结果表明,拓扑结构是决定瓶颈区域的重要因素.
基于流量需求的BGP最优路径选择是域间流量工程研究的一个问题.其中瓶颈区域的判定可为域间流量工程的决策过程提供重要的启发信息.然而,瓶颈区域的判定是NP难问题.在同时考虑域内链路和域间链路的前提下,提出多项式时间的基于流量需求的瓶颈区域的预测算法.在此基础上,系统地研究了流量、拓扑结构与瓶颈区域间的关系.模拟实验表明,预测算法的准确性超过90%,研究结果表明,拓扑结构是决定瓶颈区域的重要因素.
2005, 16(5):960-969.
摘要:
节点可以自由、自主地进入网络拓扑并且无须基础网络设施的特性,使得移动Ad hoc网络被广泛应用于诸如灾难救援、战场等多种环境中.传统的Ad hoc路由协议主要是基于"最短路径"来考虑,会在网络中形成局部的"热点区域,,而影响网络的性能.对此,提出了一个新的参数"节点空闲度(leisure degree)",用来体现节点当前的传输状态.基于这个参数,联合了介质访问控制(medium access control,简称MAC)层和网络层来进行跨层设计,提出了一种新的基于"节点空闲度"的自适应路由协议LDAR(leisure degree adaptive routing),采用启发式的路由选择机制,有效地实现了拥塞控制和负载分担,提高了移动Adhoc网络的性能.通过模拟实验,结果显示了LDAR协议在静态网络和动态网络的环境下,都有比DSR协议更好的性能.
节点可以自由、自主地进入网络拓扑并且无须基础网络设施的特性,使得移动Ad hoc网络被广泛应用于诸如灾难救援、战场等多种环境中.传统的Ad hoc路由协议主要是基于"最短路径"来考虑,会在网络中形成局部的"热点区域,,而影响网络的性能.对此,提出了一个新的参数"节点空闲度(leisure degree)",用来体现节点当前的传输状态.基于这个参数,联合了介质访问控制(medium access control,简称MAC)层和网络层来进行跨层设计,提出了一种新的基于"节点空闲度"的自适应路由协议LDAR(leisure degree adaptive routing),采用启发式的路由选择机制,有效地实现了拥塞控制和负载分担,提高了移动Adhoc网络的性能.通过模拟实验,结果显示了LDAR协议在静态网络和动态网络的环境下,都有比DSR协议更好的性能.
37 基于角色的受限委托模型
2005, 16(5):970-978.
摘要:
角色委托是RBAC模型需要支持的一种重要安全策略.它的主要思想是系统中的主动实体将角色委托给其他主动实体,以便以前者名义执行特定的工作.角色委托者要对委托角色的使用负责,所以对委托角色进行使用限制是整个模型的关键组成部分.目前已有一些模型扩展了RBAC模型以支持角色委托,但是这些模型对委托限制的支持非常有限.提出了角色委托限制的需求,包括临时性限制、常规角色关联性限制、部分性限制和传播限制.并且,给出了一个支持临时性限制和常规角色关联性限制的基于角色的委托模型.给出模型的形式化描述,为模型在实际环境中的应用奠定了基础.
角色委托是RBAC模型需要支持的一种重要安全策略.它的主要思想是系统中的主动实体将角色委托给其他主动实体,以便以前者名义执行特定的工作.角色委托者要对委托角色的使用负责,所以对委托角色进行使用限制是整个模型的关键组成部分.目前已有一些模型扩展了RBAC模型以支持角色委托,但是这些模型对委托限制的支持非常有限.提出了角色委托限制的需求,包括临时性限制、常规角色关联性限制、部分性限制和传播限制.并且,给出了一个支持临时性限制和常规角色关联性限制的基于角色的委托模型.给出模型的形式化描述,为模型在实际环境中的应用奠定了基础.
38 类型化移动资源
2005, 16(5):979-990.
摘要:
在移动资源演算(MR)中发现了一种干扰现象,称为直接访问干扰,该现象比移动灰箱演算(MA)中的墙干扰现象更具破坏力,因为在MR中恶意的环境或上下文可以不受限制地访问进程内部的敏感资源.因而该干扰问题当被视为一种程序运行错误.为了控制直接干扰现象,提出了一种MR的变体:安全移动资源演算(SR).它使用了一种类型系统来避免所有的直接访问干扰的发生.基于该研究,MA中的强干扰现象实际上是直接访问干扰的一种特殊形式,自然地,在SR中也得到了相应的控制.最后给出一些用例,说明如何使用新设计的演算系统,以及它的健壮性.
在移动资源演算(MR)中发现了一种干扰现象,称为直接访问干扰,该现象比移动灰箱演算(MA)中的墙干扰现象更具破坏力,因为在MR中恶意的环境或上下文可以不受限制地访问进程内部的敏感资源.因而该干扰问题当被视为一种程序运行错误.为了控制直接干扰现象,提出了一种MR的变体:安全移动资源演算(SR).它使用了一种类型系统来避免所有的直接访问干扰的发生.基于该研究,MA中的强干扰现象实际上是直接访问干扰的一种特殊形式,自然地,在SR中也得到了相应的控制.最后给出一些用例,说明如何使用新设计的演算系统,以及它的健壮性.
2005, 16(5):991-999.
摘要:
提出一种普适于各种系统环境和网络规模的结构化P2P网络协议SmartBoa.与已有的结构化P2P路由协议(如Pastry,Chord等)相比,SmartBoa结点并不维护同样大小的路由表,而是各结点根据自身的带宽能力决定其路由表的大小(最强的结点可能记录全部结点的指针,最弱的结点可能只记录其中不足1%的一小部分),算法保证路由表大小正比于维护开销,充分利用所有结点的可用带宽,使路由效率达到最优;另一方面,SmartBoa并不因为系统规模的增大而增加对结点带宽的要求,因此与全连通的one-hop overlay相比,SmartBoa可以获得更好的可扩展性;再者,SmartBoa结点根据系统环境的变化动态地调节自身级别,并且可以通过逐渐调高级别的慢启动方式来克服one-hop overlay的启动时间过长的缺陷.总之,SmartBoa是一种可以运行于任何环境,不受限于系统规模的大小、结点能力的强弱、强弱结点的比例、结点出入的频率,并通过动态调节保证路由效率的P2P路由协议,适用于各种广域分布式系统.
提出一种普适于各种系统环境和网络规模的结构化P2P网络协议SmartBoa.与已有的结构化P2P路由协议(如Pastry,Chord等)相比,SmartBoa结点并不维护同样大小的路由表,而是各结点根据自身的带宽能力决定其路由表的大小(最强的结点可能记录全部结点的指针,最弱的结点可能只记录其中不足1%的一小部分),算法保证路由表大小正比于维护开销,充分利用所有结点的可用带宽,使路由效率达到最优;另一方面,SmartBoa并不因为系统规模的增大而增加对结点带宽的要求,因此与全连通的one-hop overlay相比,SmartBoa可以获得更好的可扩展性;再者,SmartBoa结点根据系统环境的变化动态地调节自身级别,并且可以通过逐渐调高级别的慢启动方式来克服one-hop overlay的启动时间过长的缺陷.总之,SmartBoa是一种可以运行于任何环境,不受限于系统规模的大小、结点能力的强弱、强弱结点的比例、结点出入的频率,并通过动态调节保证路由效率的P2P路由协议,适用于各种广域分布式系统.
2005, 16(5):1000-1011.
摘要:
在军事和商业领域中,由多个自治域形成的协作群体对共有资源(如客体、应用程序以及服务等)的访问问题越来越受到重视.协作中的基本事实是:尽管这些自治域有共同的目标,但同时有不同的自身利益.为了有效地保护共有资源,把"信任"的概念引入了协作访问控制中,并在基于量化权限的思想上,提出了细粒度的协作访问控制策略.在该策略里,权限的使用形式是元权限,也就是单位权限,它是访问共有客体权限的一个划分,可为多个域中不同用户所拥有.当访问共有资源时,参与者们所拥有的元权限的值之和以及人数必须达到规定的权限门限值和人数值,并且访问时间是所有参与者的共同许可访问时间段,这使得可以对协作资源进行有效地分布控制.另外,还引入了元权限的使用时间段约束.最后,证明了该细粒度协作访问控制策略关于协作系统的状态转换是保持安全的.
在军事和商业领域中,由多个自治域形成的协作群体对共有资源(如客体、应用程序以及服务等)的访问问题越来越受到重视.协作中的基本事实是:尽管这些自治域有共同的目标,但同时有不同的自身利益.为了有效地保护共有资源,把"信任"的概念引入了协作访问控制中,并在基于量化权限的思想上,提出了细粒度的协作访问控制策略.在该策略里,权限的使用形式是元权限,也就是单位权限,它是访问共有客体权限的一个划分,可为多个域中不同用户所拥有.当访问共有资源时,参与者们所拥有的元权限的值之和以及人数必须达到规定的权限门限值和人数值,并且访问时间是所有参与者的共同许可访问时间段,这使得可以对协作资源进行有效地分布控制.另外,还引入了元权限的使用时间段约束.最后,证明了该细粒度协作访问控制策略关于协作系统的状态转换是保持安全的.
2005, 16(5):1012-1020.
摘要:
Web信息检索的难点之一就是简短、模糊的用户查询与存在大量冗余和噪声的文档之间的不匹配.对Web文档信息特征进行分析,提出Web文档主特征词、主特征域和主特征空间的概念,在该空间上使用文档频度DF(document frequency)信息而非传统意义上的IDF(inverse document frequency)信息进行权值计算,并给出一个改进的相似度计算模型.使用该模型在10G和19G的两个大规模Web文档集合上进行了3组标准测试.比较实验表明,与传统IDF思想相比,在各项评价指标上,DF相关的主特征权值计算方法都能始终较大幅度地提高系统性能,最大达到18.6%的性能改善.
Web信息检索的难点之一就是简短、模糊的用户查询与存在大量冗余和噪声的文档之间的不匹配.对Web文档信息特征进行分析,提出Web文档主特征词、主特征域和主特征空间的概念,在该空间上使用文档频度DF(document frequency)信息而非传统意义上的IDF(inverse document frequency)信息进行权值计算,并给出一个改进的相似度计算模型.使用该模型在10G和19G的两个大规模Web文档集合上进行了3组标准测试.比较实验表明,与传统IDF思想相比,在各项评价指标上,DF相关的主特征权值计算方法都能始终较大幅度地提高系统性能,最大达到18.6%的性能改善.
2005, 16(5):1021-1027.
摘要:
中继路由系统由一组中继路由器组成,为不能交换路由信息的路由域提供中继路由.该系统的关键是为路由域配置恰当的中继路由器.为所有中继路由器分配一个泛播地址,将它们当作一个逻辑节点,借助泛播路由以最短路径到达该逻辑节点.此外,采用源路由的方法将数据报文路由至中继路由器.基于泛播的中继路由系统实现了中继路由的自动配置,提高了中继路由的性能和可靠性,并且与现有网络系统兼容,实施代价很小.
中继路由系统由一组中继路由器组成,为不能交换路由信息的路由域提供中继路由.该系统的关键是为路由域配置恰当的中继路由器.为所有中继路由器分配一个泛播地址,将它们当作一个逻辑节点,借助泛播路由以最短路径到达该逻辑节点.此外,采用源路由的方法将数据报文路由至中继路由器.基于泛播的中继路由系统实现了中继路由的自动配置,提高了中继路由的性能和可靠性,并且与现有网络系统兼容,实施代价很小.
2005, 16(5):1028-1038.
摘要:
由于能够提供高性能I/O,盘阵被广泛采用.但以往的盘阵扩展性不足.而用户或应用程序对外存容量和I/O性能需求是变化的,盘阵系统本身必须有很强的扩展性,以适应系统的I/O需求.因此,由于既具有盘阵的高性能I/O,又能通过增加或减去设备后进行数据重构实现性能的扩展,动态盘阵具有广泛的前景.动态盘阵的技术热点是数据分布算法和在线自适应数据重构技术,使得盘阵的性能和容量能够随着系统的扩展而伸缩,同时使得盘阵动态扩展时的数据重构对系统的影响非常小.主要工作是:第1,对动态盘阵的数据分布展开研究,并提出一种新的数据分布算法(D/H分布).在D/H分布中,盘阵扩展时始终保持各设备上空间和负载的平衡性,同时扩展时重构的数据最少;第2,针对D/H分布,提出基于控制理论的数据重构技术,使得盘阵动态扩展时的在线数据重构对请求QoS的影响非常小,同时使得数据重构能够尽快完成;第3,研究中针对Sperite trace和合成负载进行了大量模拟实验,结果表明,提出的基于控制理论的数据重构技术行之有效.
由于能够提供高性能I/O,盘阵被广泛采用.但以往的盘阵扩展性不足.而用户或应用程序对外存容量和I/O性能需求是变化的,盘阵系统本身必须有很强的扩展性,以适应系统的I/O需求.因此,由于既具有盘阵的高性能I/O,又能通过增加或减去设备后进行数据重构实现性能的扩展,动态盘阵具有广泛的前景.动态盘阵的技术热点是数据分布算法和在线自适应数据重构技术,使得盘阵的性能和容量能够随着系统的扩展而伸缩,同时使得盘阵动态扩展时的数据重构对系统的影响非常小.主要工作是:第1,对动态盘阵的数据分布展开研究,并提出一种新的数据分布算法(D/H分布).在D/H分布中,盘阵扩展时始终保持各设备上空间和负载的平衡性,同时扩展时重构的数据最少;第2,针对D/H分布,提出基于控制理论的数据重构技术,使得盘阵动态扩展时的在线数据重构对请求QoS的影响非常小,同时使得数据重构能够尽快完成;第3,研究中针对Sperite trace和合成负载进行了大量模拟实验,结果表明,提出的基于控制理论的数据重构技术行之有效.
联系方式
- 《软件学报 》
- 主办单位：中国科学院软件研究所
中国计算机学会 - 邮编：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
技术支持：北京勤云科技发展有限公司
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司
