Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2008年 第45卷 第7期    出版日期:2008-07-15
论文
XN-Store: 一种原生XML数据库的存储方案
王 鑫 袁晓洁 汪陈应 张海威
2008, 45(7):  . 
摘要 ( 509 )   PDF (1490KB) ( 606 )  
相关文章 | 计量指标
随着XML相关标准的推广与应用,Web上出现了大量的XML文档.为了进行有效的管理,有必要将XML文档存储到数据库中.存储方案已成为XML数据管理领域研究的一个重要课题.将XML文档映射为关系表,存储到传统的RDBMS中,会破坏XML数据的树形结构,造成查询效率的下降.提出了一种新的用于原生XML数据库的存储方案——XN-Store.该方案基于索引结构将XML节点作为记录直接存储到分页文件中,建立起持久化文档对象模型,从而保持了XML数据原有的树形结构.XN-Store不仅降低了XML文档的存储空间开销,而且实现了XML节点的快速串行化输出和访问操作.作为通用的原生XML存储方案,XN-Store支持各种二级索引的创建,以提高XML查询处理的效率.采用多种数据集,分别在XN-Store和先前的XML存储系统上进行实验,比较存储空间、存储时间、串行化时间和节点访问时间.实验结果表明,XN-Store是一种高性能的原生XML数据库存储方案.
一种基于位置数据库聚类的动态适应缓存位置信息策略
洪 亮 卢炎生 陈锦富 丁晓锋
2008, 45(7):  . 
摘要 ( 299 )   PDF (1070KB) ( 451 )  
相关文章 | 计量指标
移动环境中提高定位移动用户性能的一个重要方法是缓存用户的位置信息.然而已经提出的缓存策略针对的是单个用户,造成缓存的效率不高.针对群体用户提出了一种基于位置数据库聚类的动态适应缓存位置信息(DACaL)策略.其中位置数据库聚类算法通过挖掘群体移动用户的运动模式对位置数据库进行聚类,以确定缓存层次和降低位置管理的代价.动态适应缓存位置信息算法根据聚类结果对位置数据库进行重组,在相邻聚类之间缓存位置信息,建立旁路指针,以缩短消息传输的路径和减少查询位置数据库的次数.实验表明,DACaL策略能够有效地降低总体代价,性能上优于相关策略.
一种密集部署传感器网络的分簇算法
李建波, 黄刘生, 徐宏力, 王继春, 徐 犇,
2008, 45(7):  . 
摘要 ( 252 )   PDF (992KB) ( 499 )  
相关文章 | 计量指标
针对分簇算法中的重新分簇所带来的高负载问题,提出了一种基于完全图的能量有效的分簇算法(CGCA).系统启动时刻,CGCA把网络划分成多个完全图,每个完全图独立成簇.CGCA利用完全图中节点之间是等价的性质,只是在系统启动的时刻执行分簇算法,而在以后的重新选举簇头阶段,簇头只需要在每个簇的内部节点间进行轮换,而不是像以前的分簇算法需要进行全局性的触发来选举簇头,这使得CGCA的通信和计算负载可以大量减少,它在单个节点的处理复杂度和消息复杂度均为O(1).另外,通过优先选择距离簇头近的节点加入簇内,CGCA不仅减少了簇头和簇内成员的簇内通信能量,而且使得簇头比较均匀地分布在部署区域.仿真实验表明:在节点密集部署的情况下,CGCA产生的消息交换个数远小于HEED分簇算法.最后在簇头均匀分布方面,CGCA也明显优于LEACH分簇算法.
分布式的SPKI/SDSI2.0证书链搜索算法
耿秀华, 韩 臻, 金 砺, 王青龙,
2008, 45(7):  . 
摘要 ( 377 )   PDF (848KB) ( 412 )  
相关文章 | 计量指标
信任管理是一种适用于大规模分布式网络的访问控制机制,SPKI/SDSI2.0是目前信任管理体系中最成熟、最普及的一个.可目前已有的SPKI/SDSI2.0证书链搜索算法都是集中式的,而SPKI/SDSI2.0系统是一种分布式系统,证书是以分布式方式分发和存储的.针对此问题,首先给出一种合理的SPKI/SDSI2.0分布式证书存储策略,其中的证书是对象方完全可追溯的(subject-traces-all).在此基础上,提出了一种分布式的SPKI/SDSI2.0证书链搜索算法DCCDS,它是面向目标的(goal-directed).理论分析表明,算法具有较高的执行效率,而且可以实现对委托深度(delegation depth)的细粒度控制.
分布式概念格的属性约简研究
杨 彬 徐宝文
2008, 45(7):  . 
摘要 ( 255 )   PDF (634KB) ( 514 )  
相关文章 | 计量指标
概念格的属性约简是形式化概念分析理论的重要研究内容之一. 传统的格属性约简方法主要是针对非分布式环境下单个形式背景的, 而随着数据分布存储和处理的广泛应用, 研究基于分布式环境下概念格的属性约简具有重要的意义. 为此,提出属性的超集和确定集的概念,刻画了形式背景中不同类型属性的局部特征与全局特征,推导出属性约简的判定定理;在此基础上, 给出计算分布式环境下概念格属性约简的ADSCL和DRCL算法. ADSCL算法用于计算属性的超集和最小确定集,这些约简信息将作为DRCL算法的输入, 以计算得到全局形式背景的约简.理论分析和实验结果表明, 该算法是有效可行的.
基于迭代切距离原型学习算法的步态识别
陈昌由 张军平
2008, 45(7):  . 
摘要 ( 275 )   PDF (757KB) ( 546 )  
相关文章 | 计量指标
作为唯一远程生物认证技术,步态识别一方面越来越受到人们的重视,提出了很多相应的算法,另一方面,它又面临着很多挑战,其难点之一是如何从多帧步态中有效地提取步态特征.针对此问题,并基于步态能量图(GEI)在步态特征表示上的效果,提出了一种迭代切距离原型学习算法.假定各人的步态分布在不同流形上面,首先用切距离改进步态能量图的定义,进而用迭代的方法来解一个最优解问题,从而学习出步态原型图,再通过PCA对步态原形进行特征提取,最后进行识别.证明了该方法的收敛性,实验结果表明所提出的方法取得了比GEI更好的识别率,并证明了步态流形的假设的合理性.
多Agent系统中信任和信誉系统研究综述
贺利坚, 黄厚宽, 张 伟,
2008, 45(7):  . 
摘要 ( 469 )   PDF (1118KB) ( 589 )  
相关文章 | 计量指标
MAS环境同人类社会类似, 充斥着大量不确定因素,因此,在MAS环境中引入信任来解决合作与交互问题具有重要意义. 信任通常来源于直接信任和信誉两种途径,信誉系统是用于支持信任评价的机制. 信誉系统的研究范围分为个体层和系统层两个层次,信誉系统的研究工作更关注个体层,信任的评价要符合准确性等特点. 信誉系统中信任的表示一般采用基于认知观点和数值观点的方法. 信誉系统采用集中式、分布式和混合式3种体系结构,各种模型都需要明确信任表示、传播与汇总的方法. 目前两个较为成功的分布式多Agent信誉系统是ReGreT和FIRE. 信息不精确的问题是信誉系统中的基本问题,也是一个迫切需要深入研究的课题. 信誉系统研究中的一个突出问题是尚无公认的测试平台,Agent信誉和信任测试床(ART)项目作了有益的探索. 在上述评述的基础上,可以在新模型和机制的构建、现有模型改进和完善、测试平台的研究和开发等方面有待进一步开展工作.
一种无线传感器网络拓扑的启发式分簇控制算法
刘林峰, 刘 业,
2008, 45(7):  1099-1105. 
摘要 ( 536 )   HTML ( 0)   PDF (869KB) ( 425 )  
相关文章 | 计量指标
无线传感器网络的首要设计目标即延长网络生命期,而网络拓扑作为上层协议的重要平台,是实现这一目标的支撑基础. 为了研究符合网络生命期目标要求的传感器网络拓扑控制方案,针对传统分簇算法的部署受限或可靠性缺乏等弊端,从理论上对分簇需求进行了建模分析,最终转化为携近似优化目标的簇划分及簇头选取问题,进而提出了一种启发式的分簇控制算法. 通过实验对方案进行了性能分析和验证,结果表明该算法以较合理的簇规模进行分簇划分,所获拓扑结构具有全局能耗低、骨干网健壮性高的特点,能有效地延长WSN的生命期.
两种新的push-pull平衡的大数据量无线传感器网络数据分发算法
陶孜谨 龚正虎 卢泽新
2008, 45(7):  1115-1125. 
摘要 ( 588 )   HTML ( 0)   PDF (1936KB) ( 463 )  
相关文章 | 计量指标
无线传感器网络中如何获得较低的通信代价同时在事件数据的push和pull之间实现更好的平衡是各种数据分发算法共同追求的目标.分析了目前已公认较好的两种典型的有结构和无结构的数据分发算法,指出了它们的优缺点.在此基础上,结合这两种算法使用的push-pull策略,针对不同应用环境下的无线传感器网络的ALL型查询的特定需求,提出了两种基于有结构和无结构存储模式相结合的混合型数据分发算法,分别是Hybrid-Dcs-Cn1(HDC1)算法和Hybrid-Dcs-Cn2(HDC2)算法.分析表明这两种算法在保证push-pull之间平衡的前提下解决了已有算法存在的热点问题:存储拷贝数多和查询性能低,能更好地适应传感器网络的特点,是两种能量高效的数据分发算法.
基于骨干结点集的移动IP组播路由算法研究
周 灵, 孙亚民,
2008, 45(7):  1126-1132. 
摘要 ( 386 )   HTML ( 0)   PDF (942KB) ( 496 )  
相关文章 | 计量指标
为了优化移动IP组播生成树代价,减少移动结点切换加入时延和信息传输时延,引入了移动IP“骨干结点集”思想,设计了移动IP组播路由算法BNSBMR (bone node set-based multicast routing algorithm).“骨干结点集”是移动IP环境下满足一定条件的IP子网接入路由器AR(access router)的集合.该算法通过“骨干结点集”降低移动IP组播生成树的代价;减少移动结点切换的加入时延;并通过路径优化降低信息传输时延.从理论上证明了算法的正确性,并分析了其计算复杂度.仿真实验表明: BNSBMR算法从树代价、加入时延、传输时延3个方面提高了移动IP环境下组播业务满足QoS约束的能力.
一种典型MANET匿名路由协议的分析与改进
章 洋
2008, 45(7):  1142-1150. 
摘要 ( 383 )   HTML ( 0)   PDF (829KB) ( 382 )  
相关文章 | 计量指标
鉴于现有MANET匿名路由协议中不明确的敌手模型、未知安全性的密码学原语以及非严格的分析方法不能提供协议匿名性的信任,因此,对其中一种有代表性的匿名DSR进行了分析与改进.先从定义敌手攻击能力的角度明确敌手模型,并以数据分组与端节点不可关联性为目标定义协议的理想过程.然后,在路由发现阶段获得由UC安全的会话密钥组成的路径,在数据传输阶段用该密钥构造可验证的轻型路由洋葱.最后,在UC框架中基于理想过程证明协议的匿名性.
基于用户满意度的学习服务发现算法
朱郑州 吴中福 吴开贵
2008, 45(7):  1161-1168. 
摘要 ( 416 )   HTML ( 0)   PDF (1132KB) ( 483 )  
相关文章 | 计量指标
针对用户对e-Learning服务发现系统提供的服务不满意或者满意程度不稳定的问题,引入了用户满意度因子,设计了一个学习服务发现算法——eLSDAUS. 该算法允许用户参与服务发现的过程,对服务发现的效果进行评价.学习服务发现系统把用户的评价反馈到学习服务发现算法,利用修正函数修正更新发布服务各属性的匹配度权值,优化反馈给用户的综合匹配度的计算.实验表明,在发布的学习服务数量超过1万时,该算法能够提高服务发现的查准率3%,而且随着发布服务数量的增多,效果会更好.经过127天的学习,用户对服务发现结果的总体满意比率可超过93%.
基于模糊cmeans算法的空间数据分类和预测
胡彩平 秦小麟
2008, 45(7):  1183-1188. 
摘要 ( 496 )   HTML ( 0)   PDF (599KB) ( 529 )  
相关文章 | 计量指标
空间分类和预测是空间数据挖掘中一个非常重要的方法,但对它们的研究目前尚处于初始阶段.通过引入空间对象对模糊聚类的模糊隶属度的概念,提出了基于模糊cmeans算法的空间数据分类和预测的方法(SFCM).该方法首先用模糊cmeans方法对数据集论域空间进行聚类,但由于空间数据具有空间自相关的特性,在用模糊cmeans算法进行空间聚类时加入了空间信息.然后计算每个空间对象对所有聚类的模糊隶属度并从中找出模糊隶属度最大的聚类.最后用该聚类中心对象的因变量的值作为该空间对象的因变量的估计值.理论分析和实验结果表明,该算法是有效可行的.
基于局部信息熵的加权子空间离群点检测算法
倪巍伟, 陈 耿, 陆介平, 吴英杰, 孙志挥,
2008, 45(7):  1189-1194. 
摘要 ( 558 )   HTML ( 0)   PDF (721KB) ( 679 )  
相关文章 | 计量指标
离群点检测作为数据挖掘的一个重要研究方向,可以从大量数据中发现少量与多数数据有明显区别的数据对象.“维度灾殃”现象的存在使得很多已有的离群点检测算法对高维数据不再有效.针对这一问题,提出基于局部信息熵的加权子空间离群点检测算法SPOD.通过对数据对象在各维进行邻域信息熵分析,生成数据对象相应的离群子空间和属性权向量,对离群子空间中的属性赋以较高的权值,进一步提出子空间加权距离等概念.采用基于密度离群点检测的思想,分析计算数据对象的子空间离群影响因子,判断是否为离群点.算法能够有效地适应于高维数据离群点检测,理论分析和实验结果表明算法是有效可行的.
树上推广的Multicut问题的近似算法
张 鹏
2008, 45(7):  1195-1202. 
摘要 ( 837 )   HTML ( 0)   PDF (713KB) ( 493 )  
相关文章 | 计量指标
给定边上有费用的树T,终端集合族X={S\-1,S\-2,…,S\-l},推广的Multicut问题询问费用最小的边集,使得在树上删除边集中的边能够断开每一个终端集.推广的Multicut问题有其独立的研究意义,因为该问题分别是经典的Multicut问题和Multiway Cut问题的自然推广,同时也是推广的Steiner Forest问题的对偶问题.树上推广的Multicut问题的完全版本可以归约到树上经典的Multicut问题近似求解.对于该问题的Prize-collecting版本,给出了原始对偶的3倍近似算法.对于该问题的k版本,通过非一致的途径给出了近似比为min{2(l-k+1),k}的近似算法.以及找到了该问题的k版本与k-稠密子图问题之间的一个有趣的联系,从而证明了将k版本的树上推广的Multicut问题近似到O(n\+\{16-ε\})以内是困难的(对某个小的常数ε>0).
中文网页语义标注:由句子到RDF表示
荆 涛, 左万利, 孙吉贵, 车海燕,
2008, 45(7):  1221-1231. 
摘要 ( 806 )   HTML ( 1)   PDF (1282KB) ( 595 )  
相关文章 | 计量指标
语义网远景的实现需要自动化的语义标注方法.提出了一种在领域本体指导下,针对中文网页的语义标注方法.运用统计学方法与自然语言处理技术,以文档中句子为处理对象,采取识别和组合两个阶段来完成句子向RDF表示的映射.它具有以下特点:以统计方法获得领域相关词汇,构造领域词汇标注列表作为外部领域知识,降低对通用语言本体的依赖;显式的属性类型标注方法识别出句子中表达关系的词汇,标注为属性类型,利于后续关系抽取;构造句子的句法依存关系树(森林),按照依存关系对词汇进行组合,形成RDF陈述.实验结果显示此方法较基于主谓宾语法关系的语义标注方法更为有效.
DTI扩散张量的一种稳健估计方法
白 衡 高玉蕊 王世杰 罗立民
2008, 45(7):  1232-1238. 
摘要 ( 622 )   HTML ( 1)   PDF (1501KB) ( 609 )  
相关文章 | 计量指标
为了获得更精确的DTI扩散张量场,提出了一种基于约束M估计子的稳健估计方法.首先对扩散加权图像序列进行双树复数小波降噪预处理,以减少热噪声影响.然后通过试探法找到一个合适的回归起始点,并通过Cholesky分解对扩散张量进行正定约束.最后寻找局部最小获得DTI扩散张量的约束M估计,并在模拟二阶张量场和真实DTI数据集上进行了实验.与最小二乘法和M估计子回归模型相比,该方法可以更有效地排除热噪声和生理性离群点影响,对DTI扩散张量估计很有价值.
以改善精度为目标的人手跟踪方法研究
冯志全, 杨 波, 李 毅, 王中华, 郑艳伟,
2008, 45(7):  1239-1248. 
摘要 ( 524 )   HTML ( 0)   PDF (2035KB) ( 446 )  
相关文章 | 计量指标
分别从UKF滤波器的内在机理和人手运动模型两个方面入手,以改善跟踪结果的精确度为基本目标,重点对UKF算法中存在的部分理论问题进行了探讨,在此基础上提出了改进后的UKFDUT算法,同时也对IMM进行了改进,把IMM模型变为MM模型,再进一步将UKFDUT算法和MM模型相融合,得到UKFDUT+MM算法.研究表明,Sigma点具有一些特性,通过对这些特性进行研究,可以找到改进跟踪精度的新途径;把MM模型和人手模型评价标准相结合,可以取得比单独使用IMM更好的跟踪精度.实验结果也表明了算法的有效性和令人满意的跟踪精度.
一种姿态无关的人体模型骨骼提取方法
于 勇, 王兆其, 夏时洪, 毛天露,
2008, 45(7):  1249-1258. 
摘要 ( 580 )   HTML ( 1)   PDF (2514KB) ( 439 )  
相关文章 | 计量指标
随着三维扫描技术的逐渐成熟,三维人体扫描模型的骨骼提取逐渐成为虚拟人建模研究领域的热点之一.现有的三维人体模型骨骼提取方法,存在手工标注任务繁重、对模型姿态过于敏感、计算结果不准确等问题.提出了一种新的三维人体模型的骨骼提取算法:首先,根据Morse原理,将测地距离作为Morse函数的要素,实现姿态无关的人体模型特征点以及拓扑结构的提取;其次,将测地距离等值面作为基础数据,采用截面似圆性判别准则提取模型关节中心所在等值面,从而获得关节中心的准确结果.实验结果表明,与已有算法相比,该方法具有模型姿态无关、计算结果准确等特性,并且能够完全自动地提取三维人体扫描模型的骨骼.
基于Catmull-Clark细分的曲面布尔运算基础研究
袁 鸿 刘 浩 廖文和
2008, 45(7):  1259-1268. 
摘要 ( 701 )   HTML ( 0)   PDF (2123KB) ( 731 )  
相关文章 | 计量指标
基于Catmull-Clark细分,提出一种对平面四边型网格进行操作的基础布尔运算,包括曲面求交、裁剪和网格级基础布尔运算.首先将细分曲面的求交转换为对一定细分层次的细分控制网格求交,得到满足一定精度要求的交线;采用局部修改交点处的控制网格拓扑结构和控制网格顶点位置的方法,实现了对细分曲面的裁剪;最后提出一种对一定细分层次的四边形控制网格进行操作的布尔运算,称之为细分曲面网格级布尔运算,包括布尔交、布尔并和布尔差3种运算,并给出了运算的基本原则与应用实例.
ARP:同时多线程处理器中共享Cache自适应运行时划分机制
隋秀峰, 吴俊敏, 陈国良,
2008, 45(7):  1269-1277. 
摘要 ( 584 )   HTML ( 1)   PDF (2120KB) ( 384 )  
相关文章 | 计量指标
同时多线程是一种延迟容忍的体系结构,采用共享的二级Cache,在每个周期内可以执行多个线程的多条指令,这就会增加对存储层次的压力.文中主要研究了SMT处理器中多个并发执行的线程之间共享Cache的划分问题,尤其是Cache共享中的公平性问题以及它和吞吐量之间的关系.传统的LRU策略会根据线程的需要隐式地划分共享Cache,给具有较高需求的线程分配较多的Cache空间,对Cache的管理具有不公平性,从而会引起线程饿死、优先级反转等问题.实现了一种自适应、运行时划分机制(ARP)来管理共享Cache.ARP采用公平性作为划分的度量,并且使用动态划分算法来优化公平性,该算法具有易于实现,所需剖析较少的特点,硬件上使用经典的监控器来收集每个线程的栈距离信息,其存储开销不到0.25%.实验结果显示,与基于LRU的Cache划分相比,ARP可以将一个2路SMT处理器的公平性提高2.26倍,而将吞吐量平均提高14.75%.