计算机研究与发展杂志 北大期刊 CSCD期刊 统计源期刊

计算机研究与发展 2008年第07期杂志 文档列表

计算机研究与发展杂志计算机网络

一种无线传感器网络拓扑的启发式分簇控制算法1099-1105

摘要：无线传感器网络的首要设计目标即延长网络生命期,而网络拓扑作为上层协议的重要平台,是实现这一目标的支撑基础.为了研究符合网络生命期目标要求的传感器网络拓扑控制方案,针对传统分簇算法的部署受限或可靠性缺乏等弊端,从理论上对分簇需求进行了建模分析,最终转化为携近似优化目标的簇划分及簇头选取问题,进而提出了一种启发式的分簇控制算法.通过实验对方案进行了性能分析和验证,结果表明该算法以较合理的簇规模进行分簇划分,所获拓扑结构具有全局能耗低、骨干网健壮性高的特点,能有效地延长WSN的生命期.

一种密集部署传感器网络的分簇算法1106-1114

摘要：针对分簇算法中的重新分簇所带来的高负载问题,提出了一种基于完全图的能量有效的分簇算法（CGCA）.系统启动时刻,CGCA把网络划分成多个完全图,每个完全图独立成簇.CGCA利用完全图中节点之间是等价的性质,只是在系统启动的时刻执行分簇算法,而在以后的重新选举簇头阶段,簇头只需要在每个簇的内部节点间进行轮换,而不是像以前的分簇算法需要进行全局性的触发来选举簇头,这使得CGCA的通信和计算负载可以大量减少,它在单个节点的处理复杂度和消息复杂度均为O（1）.另外,通过优先选择距离簇头近的节点加入簇内,CGCA不仅减少了簇头和簇内成员的簇内通信能量,而且使得簇头比较均匀地分布在部署区域.仿真实验表明：在节点密集部署的情况下,CGCA产生的消息交换个数远小于HEED分簇算法.最后在簇头均匀分布方面,CGCA也明显优于LEACH分簇算法.

两种新的push-pull平衡的大数据量无线传感器网络数据分发算法1115-1125

摘要：无线传感器网络中如何获得较低的通信代价同时在事件数据的push和pull之间实现更好的平衡是各种数据分发算法共同追求的目标.分析了目前已公认较好的两种典型的有结构和无结构的数据分发算法,指出了它们的优缺点.在此基础上,结合这两种算法使用的push-pull策略,针对不同应用环境下的无线传感器网络的ALL型查询的特定需求,提出了两种基于有结构和无结构存储模式相结合的混合型数据分发算法,分别是Hybrid-Dcs-Cn1（HDC1）算法和Hybrid-Dcs-Cn2（HDC2）算法.分析表明这两种算法在保证push-pull之间平衡的前提下解决了已有算法存在的热点问题：存储拷贝数多和查询性能低,能更好地适应传感器网络的特点,是两种能量高效的数据分发算法.

基于骨干结点集的移动IP组播路由算法研究1126-1132

摘要：为了优化移动IP组播生成树代价,减少移动结点切换加入时延和信息传输时延,引入了移动IP＂骨干结点集＂思想,设计了移动IP组播路由算法BNSBMR（bone node set-based multicast routing algorithm）.＂骨干结点集＂是移动IP环境下满足一定条件的IP子网接入路由器AR（access router）的集合.该算法通过＂骨干结点集＂降低移动IP组播生成树的代价;减少移动结点切换的加入时延;并通过路径优化降低信息传输时延.从理论上证明了算法的正确性,并分析了其计算复杂度.仿真实验表明：BNSBMR算法从树代价、加入时延、传输时延3个方面提高了移动IP环境下组播业务满足QoS约束的能力.

计算机研究与发展杂志信息安全

一种典型MANET匿名路由协议的分析与改进1142-1150

摘要：鉴于现有MANET匿名路由协议中不明确的敌手模型、未知安全性的密码学原语以及非严格的分析方法不能提供协议匿名性的信任,因此,对其中一种有代表性的匿名DSR进行了分析与改进.先从定义敌手攻击能力的角度明确敌手模型,并以数据分组与端节点不可关联性为目标定义协议的理想过程.然后,在路由发现阶段获得由UC安全的会话密钥组成的路径,在数据传输阶段用该密钥构造可验证的轻型路由洋葱.最后,在UC框架中基于理想过程证明协议的匿名性.

计算机研究与发展杂志人工智能

多Agent系统中信任和信誉系统研究综述1151-1160

摘要：MAS环境同人类社会类似,充斥着大量不确定因素,因此,在MAS环境中引入信任来解决合作与交互问题具有重要意义.信任通常来源于直接信任和信誉两种途径,信誉系统是用于支持信任评价的机制.信誉系统的研究范围分为个体层和系统层两个层次,信誉系统的研究工作更关注个体层,信任的评价要符合准确性等特点.信誉系统中信任的表示一般采用基于认知观点和数值观点的方法.信誉系统采用集中式、分布式和混合式3种体系结构,各种模型都需要明确信任表示、传播与汇总的方法.目前两个较为成功的分布式多Agent信誉系统是ReGreT和FIRE.信息不精确的问题是信誉系统中的基本问题,也是一个迫切需要深入研究的课题.信誉系统研究中的一个突出问题是尚无公认的测试平台,Agent信誉和信任测试床（ART）项目作了有益的探索.在上述评述的基础上,可以在新模型和机制的构建、现有模型改进和完善、测试平台的研究和开发等方面有待进一步开展工作.

基于用户满意度的学习服务发现算法1161-1168

摘要：针对用户对e-Learning服务发现系统提供的服务不满意或者满意程度不稳定的问题,引入了用户满意度因子,设计了一个学习服务发现算法——eLSDAUS.该算法允许用户参与服务发现的过程,对服务发现的效果进行评价.学习服务发现系统把用户的评价反馈到学习服务发现算法,利用修正函数修正更新服务各属性的匹配度权值,优化反馈给用户的综合匹配度的计算.实验表明,在的学习服务数量超过1万时,该算法能够提高服务发现的查准率3%,而且随着服务数量的增多,效果会更好.经过127天的学习,用户对服务发现结果的总体满意比率可超过93%.

分布式概念格的属性约简研究1169-1176

摘要：概念格的属性约简是形式化概念分析理论的重要研究内容之一.传统的格属性约简方法主要是针对非分布式环境下单个形式背景的,而随着数据分布存储和处理的广泛应用,研究基于分布式环境下概念格的属性约简具有重要的意义.为此,提出属性的超集和确定集的概念,刻画了形式背景中不同类型属性的局部特征与全局特征,推导出属性约简的判定定理;在此基础上,给出计算分布式环境下概念格属性约简的ADSCL和DRCL算法.ADSCL算法用于计算属性的超集和最小确定集,这些约简信息将作为DRCL算法的输入,以计算得到全局形式背景的约简.理论分析和实验结果表明,该算法是有效可行的.

基于迭代切距离原型学习算法的步态识别1177-1182

摘要：作为唯一远程生物认证技术,步态识别一方面越来越受到人们的重视,提出了很多相应的算法,另一方面,它又面临着很多挑战,其难点之一是如何从多帧步态中有效地提取步态特征.针对此问题,并基于步态能量图（GEI）在步态特征表示上的效果,提出了一种迭代切距离原型学习算法.假定各人的步态分布在不同流形上面,首先用切距离改进步态能量图的定义,进而用迭代的方法来解一个最优解问题,从而学习出步态原型图,再通过PCA对步态原形进行特征提取,最后进行识别.证明了该方法的收敛性,实验结果表明所提出的方法取得了比GEI更好的识别率,并证明了步态流形的假设的合理性.

基于模糊c-means算法的空间数据分类和预测1183-1188

摘要：空间分类和预测是空间数据挖掘中一个非常重要的方法,但对它们的研究目前尚处于初始阶段.通过引入空间对象对模糊聚类的模糊隶属度的概念,提出了基于模糊c-means算法的空间数据分类和预测的方法（SFCM）.该方法首先用模糊c-means方法对数据集论域空间进行聚类,但由于空间数据具有空间自相关的特性,在用模糊c-means算法进行空间聚类时加入了空间信息.然后计算每个空间对象对所有聚类的模糊隶属度并从中找出模糊隶属度最大的聚类.最后用该聚类中心对象的因变量的值作为该空间对象的因变量的估计值.理论分析和实验结果表明,该算法是有效可行的.

基于局部信息熵的加权子空间离群点检测算法1189-1194

摘要：离群点检测作为数据挖掘的一个重要研究方向,可以从大量数据中发现少量与多数数据有明显区别的数据对象.＂维度灾殃＂现象的存在使得很多已有的离群点检测算法对高维数据不再有效.针对这一问题,提出基于局部信息熵的加权子空间离群点检测算法SPOD.通过对数据对象在各维进行邻域信息熵分析,生成数据对象相应的离群子空间和属性权向量,对离群子空间中的属性赋以较高的权值,进一步提出子空间加权距离等概念.采用基于密度离群点检测的思想,分析计算数据对象的子空间离群影响因子,判断是否为离群点.算法能够有效地适应于高维数据离群点检测,理论分析和实验结果表明算法是有效可行的.

计算机研究与发展杂志算法理论

树上推广的Multicut问题的近似算法1195-1202

摘要：给定边上有费用的树T,终端集合族X={S1,S2,…,Sl},推广的Multicut问题询问费用最小的边集,使得在树上删除边集中的边能够断开每一个终端集.推广的Multicut问题有其独立的研究意义,因为该问题分别是经典的Multicut问题和Multiway Cut问题的自然推广,同时也是推广的Steiner Forest问题的对偶问题.树上推广的Multicut问题的完全版本可以归约到树上经典的Multicut问题近似求解.对于该问题的Prize-collecting版本,给出了原始-对偶的3倍近似算法.对于该问题的k版本,通过非一致的途径给出了近似比为min{2（l-k＋1）,k}的近似算法.以及找到了该问题的k版本与k-稠密子图问题之间的一个有趣的联系,从而证明了将k版本的树上推广的Multicut问题近似到O（n1/6-ε）以内是困难的（对某个小的常数ε〉0）.

计算机研究与发展杂志数据库技术

一种基于位置数据库聚类的动态适应缓存位置信息策略1203-1210

摘要：移动环境中提高定位移动用户性能的一个重要方法是缓存用户的位置信息.然而已经提出的缓存策略针对的是单个用户,造成缓存的效率不高.针对群体用户提出了一种基于位置数据库聚类的动态适应缓存位置信息（DACaL）策略.其中位置数据库聚类算法通过挖掘群体移动用户的运动模式对位置数据库进行聚类,以确定缓存层次和降低位置管理的代价.动态适应缓存位置信息算法根据聚类结果对位置数据库进行重组,在相邻聚类之间缓存位置信息,建立旁路指针,以缩短消息传输的路径和减少查询位置数据库的次数.实验表明,DACaL策略能够有效地降低总体代价,性能上优于相关策略.

XN-Store：一种原生XML数据库的存储方案1211-1220

摘要：随着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数据库存储方案.

计算机研究与发展杂志信息处理

中文网页语义标注：由句子到RDF表示1221-1231

摘要：语义网远景的实现需要自动化的语义标注方法.提出了一种在领域本体指导下,针对中文网页的语义标注方法.运用统计学方法与自然语言处理技术,以文档中句子为处理对象,采取识别和组合两个阶段来完成句子向RDF表示的映射.它具有以下特点：以统计方法获得领域相关词汇,构造领域词汇标注列表作为外部领域知识,降低对通用语言本体的依赖;显式的属性类型标注方法识别出句子中表达关系的词汇,标注为属性类型,利于后续关系抽取;构造句子的句法依存关系树（森林）,按照依存关系对词汇进行组合,形成RDF陈述.实验结果显示此方法较基于主谓宾语法关系的语义标注方法更为有效.

DTI扩散张量的一种稳健估计方法1232-1238

摘要：为了获得更精确的DTI扩散张量场,提出了一种基于约束M估计子的稳健估计方法.首先对扩散加权图像序列进行双树复数小波降噪预处理,以减少热噪声影响.然后通过试探法找到一个合适的回归起始点,并通过Cholesky分解对扩散张量进行正定约束.最后寻找局部最小获得DTI扩散张量的约束M估计,并在模拟二阶张量场和真实DTI数据集上进行了实验.与最小二乘法和M估计子回归模型相比,该方法可以更有效地排除热噪声和生理性离群点影响,对DTI扩散张量估计很有价值.

计算机研究与发展杂志图形与图像处理

以改善精度为目标的人手跟踪方法研究1239-1248

摘要：分别从UKF滤波器的内在机理和人手运动模型两个方面入手,以改善跟踪结果的精确度为基本目标,重点对UKF算法中存在的部分理论问题进行了探讨,在此基础上提出了改进后的UKFDUT算法,同时也对IMM进行了改进,把IMM模型变为MM模型,再进一步将UKFDUT算法和MM模型相融合,得到UKFDUT＋MM算法.研究表明,Sigma点具有一些特性,通过对这些特性进行研究,可以找到改进跟踪精度的新途径;把MM模型和人手模型评价标准相结合,可以取得比单独使用IMM更好的跟踪精度.实验结果也表明了算法的有效性和令人满意的跟踪精度.

一种姿态无关的人体模型骨骼提取方法1249-1258

摘要：随着三维扫描技术的逐渐成熟,三维人体扫描模型的骨骼提取逐渐成为虚拟人建模研究领域的热点之一.现有的三维人体模型骨骼提取方法,存在手工标注任务繁重、对模型姿态过于敏感、计算结果不准确等问题.提出了一种新的三维人体模型的骨骼提取算法：首先,根据Morse原理,将测地距离作为Morse函数的要素,实现姿态无关的人体模型特征点以及拓扑结构的提取;其次,将测地距离等值面作为基础数据,采用截面似圆性判别准则提取模型关节中心所在等值面,从而获得关节中心的准确结果.实验结果表明,与已有算法相比,该方法具有模型姿态无关、计算结果准确等特性,并且能够完全自动地提取三维人体扫描模型的骨骼.