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

当期目录

2009年 第46卷 第4期    出版日期:2009-04-15
论文
一种支持多维数据范围查询的对等计算索引框架
张 蓉 钱卫宁 周傲英
2009, 46(4):  529-540. 
摘要 ( 495 )   HTML ( 0)   PDF (2042KB) ( 598 )  
相关文章 | 计量指标
如何有效地支持多维数据范围查询是传统数据管理领域的研究热点之一.但是,在大规模分布式系统中,这仍然是一个具有挑战性的研究工作.VBI-tree 是一个对等计算环境下基于平衡树的索引架构,在该架构上可以实现集中式环境下的多种支持多维数据索引的层次化树结构,例如R-tree, X-tree和M-tree等.VBI-tree设计的查询算法保证查询可以从树的任意位置开始,而不是像集中式环境下层次化树结构那样采用从树的根节点开始查询的方法,从而成功地避免了根节点引起的系统性能瓶颈问题.对于有N个节点的网络,索引方法可以保证查询效率是O(logN).VBI-tree提出了基于AVL-tree旋转的网络重构负载均衡策略可以有效地均衡负载.另外,在数据操作频繁的情况下,为了提高索引的性能,在VBI-tree上建立特殊的祖先-子孙链接形成VBI\+*-tree的结构.通过使用祖先-子孙链接,可保证对于相关查询区域的探索尽量发生在同层节点之间,而不是一直往根节点方向发送,从而减轻上层节点的查询负担,并且显著地降低了更新代价.模拟实验验证了提出的方法的有效性.
报文分流最优策略研究
周安福 刘 敏 李忠诚
2009, 46(4):  541-548. 
摘要 ( 542 )   HTML ( 2)   PDF (1084KB) ( 819 )  
相关文章 | 计量指标
在向下一代互联网络演进的过程中,一个重要的趋势是IP网络将成为语音、视频等应用的主要承载.VoIP是一个重要的语音应用.然而,IP网络的丢包造成了VoIP的服务质量不能得到保证,并且对于VoIP而言,连续丢包对其服务质量的影响要远大于分散丢包.报文分流是近年来学术界讨论的一种提高VoIP服务质量的方法,其基本思想是把1个VoIP会话的报文分散到多个网络链路传输,从而把连续丢包转化为分散丢包,缓解丢包对VoIP服务质量的影响.然而,目前的研究只局限于用一种特定的分流策略(平均分流)说明报文分流的潜力.报文分流的理论基础,比如报文分流能在多大程度上提高VoIP的服务质量,什么是最优的分流策略等,并不明了.对报文分流的理论基础进行了研究,首次给出了分流策略与VoIP服务质量的定量关系描述,给出并证明了Bernoulli网络丢包模型下的最优分流策略.同时,以ns-2仿真实验验证了该最优分流策略在Gilbert网络丢包模型下的有效性.
普适环境中面向推理的上下文缓存置换算法
林 欣, 李善平, 杨朝晖, 徐 建,
2009, 46(4):  549-557. 
摘要 ( 468 )   HTML ( 0)   PDF (1256KB) ( 520 )  
相关文章 | 计量指标
上下文缓存是减少上下文信息访问开销、降低信息传输数量、缓解连接中断引起的程序不可用性的有效途径.面向推理的上下文缓存置换算法CORA的目标是使上下文缓存达到较高命中率,有效节省普适计算中传输上下文的开销.CORA采用状态空间对低级上下文到高级上下文的推理进行建模,对各种上下文推理方法具有普遍适用性.CORA算法分为两个部分:1)在缓存端,该算法计算低级上下文的访问概率和预计失效时间,获得数据的缓存价值,作为上下文缓存置换的依据,以提高缓存的命中率;2)在传感器端设置相应的可变化范围,当传感器读数超出该范围时,主动更新缓存,以保证缓存数据的一致性.模拟实验将CORA和经典的缓存置换算法LRU进行对比,分别通过改变缓存容量、对上下文访问概率的不均匀程度和上下文更新访问比来考察两种算法的命中率,结果显示,当缓存容量相对上下文总数较小、访问概率分布较不均匀、更新访问比较高的情况下,CORA的命中率大大高于LRU.由此证明,CORA更适用于较为动态的普适计算环境.
分簇的扩展超宽带传感网生存期的下界
徐 娟, 洪永发, 蒋昌俊,
2009, 46(4):  558-565. 
摘要 ( 429 )   HTML ( 0)   PDF (954KB) ( 449 )  
相关文章 | 计量指标
无线传感网的一个基本挑战是能量受限,因此网络生存期是无线传感网最关心的课题.考虑了随机分布在面积为S\-n=λn的正方形上的n个传感节点和1个基站组成的跳时冲击无线电超宽带(TH-IR UWB)传感网.分别推导了完全分簇和常规分簇的扩展TH-IR UWB传感网生存期的渐近下界.结果表明,完全分簇的静态扩展网络生存期下界比常规分簇的提高了λn/(log(λn))\+2倍,而理想情形下的完全分簇的扩展网络生存期下界则比常规分簇的提高了(λn)\+{1/2}/(log(λn))\+{3/2}倍,因此完全分簇能极大地提高网络生存期.研究也表明对于常规分簇的扩展TH-IR UWB传感网,理想情形下生存期的下界比静态网络提高了(λn/log(λn))\+{1/2}倍,因此节点或基站在部署区域内随机移动能提高常规分簇传感网的生存期.下界公式也揭示了生存期与节点数n或部署区域面积成反比,因此大规模扩展TH-IR UWB传感网不实用.
基于三角形重心扫描的改进APIT无线传感器网络自定位算法
周 勇, 夏士雄, 丁世飞, 张 磊, 敖 欣,
2009, 46(4):  566-574. 
摘要 ( 599 )   HTML ( 0)   PDF (2117KB) ( 438 )  
相关文章 | 计量指标
传感器节点的自定位问题是无线传感器网络的重要研究内容之一.APIT是一种主要的非基于测距的定位算法.相对于其他非基于测距定位算法,APIT具有定位精度高、通信开销小等优点.但是,APIT要求有较高的锚节点密度,而且在APIT测试过程中,边界效应以及低邻居节点密度容易增加InToOut和OutToIn测试错误的发生次数.另外,APIT算法中的网格扫描算法对于OutToIn错误的容错性较差且其执行效率低.针对以上问题,提出了一种基于三角形重心扫描的改进APIT算法.首先,分析了APIT测试中的两种典型错误InToOut和OutToIn错误产生的原因,引入了对APIT测试方法的两处改进;然后,分析了网格扫描算法对节点定位精度和算法执行效率的影响,提出了一种三角形重心扫描法,有效改进了算法的定位精度和执行效率;最后,通过仿真实验验证了改进后的算法不但可以有效地减少InToOut和OutToIn两类错误发生的次数,提高平均定位精度,改善算法的性能,而且对OutToIn错误的容错性更强,执行效率更高,能够显著地提高节点的平均精度.
一种基于PSO的有效能量空洞避免的无线传感器路由算法
刘安丰 吴贤佑 陈志刚
2009, 46(4):  575-582. 
摘要 ( 543 )   HTML ( 0)   PDF (1542KB) ( 536 )  
相关文章 | 计量指标
无线传感器网络路由的一个重要问题是如何有效地均衡整个网络的能量消耗水平,避免形成能量空洞,从而导致整个网络过早死亡.基于无线传感器网络特性,首先将路由问题转化为线性规划问题,并证明了路由问题与线性规划问题的等价性.在此基础上,利用粒子群算法(particle swarm optimization algorithm, PSO)来求解能量空洞避免路由问题.算法重新定义了PSO的粒子、粒子的运算与“飞行”规则,提出了基于PSO的无线传感器路由优化算法.算法不仅能够适用于平面网络,经过稍加改进同样可以适用于层次网络的路由算法.通过理论分析证实了算法的正确性,同时大量的模拟实验证实了算法的有效性.
基于Hash函数的RFID安全认证协议研究
丁振华, 李锦涛, 冯 波,
2009, 46(4):  583-592. 
摘要 ( 494 )   HTML ( 0)   PDF (1099KB) ( 573 )  
相关文章 | 计量指标
无线传输、信号广播、资源受限等特点使RFID技术存在潜在安全隐患.在对RFID技术所面临的安全问题进行了详细地描述和分析后,提出了认证识别的单一会话模式和连续会话模式的概念,基于Hash函数设计了一个介于RFID标签和后端服务器之间的安全认证协议HSAP,以解决假冒攻击、重传攻击、追踪、去同步化等安全问题,并基于GNY逻辑给出了形式化的证明.由于在RFID标签中仅仅使用了Hash函数和或操作,因此HSAP协议跟先前的工作相比更适合于低成本RFID系统.
AES算法的并发错误检测方法及其VLSI实现
赵 佳 韩 军 曾晓洋 韩 林
2009, 46(4):  593-601. 
摘要 ( 581 )   HTML ( 1)   PDF (920KB) ( 510 )  
相关文章 | 计量指标
提出了一种AES算法的抗差分差错分析的并发错误检测方法——二维奇偶校验方法.与原有的一维奇偶校验方法相比,该方法提供了更为优化的奇偶校验位设置,更重要的是能够同时检测水平和垂直方向上的奇数个错误,在保持了对单个错误的100%的覆盖率的同时,将对多个错误的覆盖率大大提升.由于水平和垂直校验位计算模块可以复用,因此与原有的一维奇偶校验方法相比,该方法增加的硬件开销很小,对硬件实现的关键路径和吞吐率都没有影响,是一种理想的低成本高效率的抗差分差错分析的并发错误检测方法.
基于多维数据流挖掘技术的入侵检测模型与算法
毛国君 宗东军
2009, 46(4):  602-609. 
摘要 ( 440 )   HTML ( 0)   PDF (1324KB) ( 834 )  
相关文章 | 计量指标
网络访问数据有着数据流的高速、无穷达到的特点,所以利用传统多遍扫描数据库的挖掘技术来构建入侵检测模型是不可行的.针对网络访问数据流的特点,提出了一种基于多维数据流挖掘技术的入侵检测模型.此模型将传统的误用检测和异常检测两种入侵检测方法进行有机融合,因此能够克服目前广泛使用的误用检测方法无法检测新的攻击类型的缺点,并且也能够保持检测的高效性.网络访问数据记录的结构是复杂的,一个访问行为总是联系到许多属性,所以分析的难度很大.因此,引入多维频度等概念来解决网络数据流的模式表示和生成问题.同时,针对多维频度模式的特点,提出了一种新型数据结构MaxFP-Tree.在MaxFP-Tree的基础上,给出了一种高效的挖掘网络访问数据流的学习算法MaxFPinNDS.MaxFPinNDS采用衰减机制挖掘,可以快速地形成一个数据流的最近时期数据所隐含的最大频繁项目集.实验表明,设计的入侵检测模型是有效的.
基于动作单元分析的人体动画合成方法研究
朱登明, 王兆其,
2009, 46(4):  610-617. 
摘要 ( 428 )   HTML ( 0)   PDF (1512KB) ( 549 )  
相关文章 | 计量指标
从运动捕获数据中提取出反映人体运动规律的基本动作单元,合成新的人体动画已成为研究热点.但已有动作单元提取方法忽略了运动序列的时序性和不同关节之间的运动相关性.针对该问题,提出了一种新的基本动作单元提取方法,首先,采用PCA方法对高维人体运动数据进行降维分析,并采用马氏距离平方度量姿态间的相似性;其次,结合动态时间归整方法和误差平方和准则对时序运动序列进行自动切分和标注;最后,建立不同动作单元之间的概率转移模型构建运动图,并根据约束条件合成新的逼真人体动画.
适于图像压缩的二维8×8 DCT查表快速算法研究
纪秀花, 张彩明, 刘 慧,
2009, 46(4):  618-628. 
摘要 ( 567 )   HTML ( 0)   PDF (1012KB) ( 611 )  
相关文章 | 计量指标
基于基本图像的概念及其对称性,提出一种计算二维8×8 离散余弦变换(DCT)量化后系数的查表快速算法.新算法在消除乘法运算的同时也减少了加法运算量.通过设计查找表结构和组织数据,使得每次访问存储器得到的不是一个乘积数据而是一组乘积数据,有效地减少了查表次数;通过研究基本图像的对称性及DCT计算过程中数据的范围情况,减小了查找表(LUT)的长度.整个计算过程具有很强的并行性.在图像变换编码时,利用新算法可只计算需要被编码和传输的低频变换系数,以大大减少运算量.
基于小波多分辨率分析的指横纹定位新算法
毛贤光 赖晓铮 赖声礼 戴宏跃
2009, 46(4):  629-636. 
摘要 ( 479 )   HTML ( 0)   PDF (1850KB) ( 455 )  
相关文章 | 计量指标
针对指横纹感兴趣区域(ROI)难以准确定位的问题,在明确提出指横纹ROI定义的前提下,提出利用小波多分辨率分析进行指横纹ROI自动检测定位的新算法.该方法利用纹理相似性原理,在高频子图采用基于特征向量和区域生长法产生指横纹的候选子区域集合,然后利用低频子图Radon投影得到的指横纹的区域特征对候选子区域进行验证,最后结合直线拟合手指轮廓得到指横纹在原图的有效位置,最终实现指横纹ROI的精准定位.实验证明该算法不仅能有效克服噪声以及手形姿态变化的影响,并且对多种情况有很强的鲁棒性.
二维测试数据压缩的优化
周 彬 吴新春 叶以正
2009, 46(4):  637-643. 
摘要 ( 507 )   HTML ( 0)   PDF (1272KB) ( 418 )  
相关文章 | 计量指标
为了减少内建自测试方案中的测试数据,基于输入精简技术(横向压缩)和TRC测试集嵌入技术(竖向压缩)的二维测试数据压缩的BIST方案,采用改进的输入精简算法和基于相容性判断的TRC种子选择算法,同时对横向和纵向压缩进行优化,包括在相同的相容百分数(PC)的条件下,确定位百分数(PSB)对竖向压缩的影响和在相同的PSB条件下竖向压缩算法中的PC对竖向压缩的影响两个方面.针对ISCAS89实验电路的实验结果表明,每一个PSB值都有一个最优的PC值范围[PC\-{low_limit},PC\-{high_limit}]使存储位数最小,并且PSB与最优的PC\-{low_limit}和PC\-{high_limit}之间满足近似的线性关系.相对于现有的测试数据压缩方案,采用该优化的二维测试数据压缩方案实现的测试电路,不仅存储位数可减少20%~75%,而且可以达到ATPG工具所能达到的故障覆盖率.另外,测试控制逻辑电路简单,可重用性好.最后,由于在测试向量生成器和被测电路之间没有引入逻辑门,因此,不会对电路的性能产生影响.
基于变异和信息素扩散的多维背包问题的蚁群算法
冀俊忠 黄 振 刘椿年
2009, 46(4):  644-654. 
摘要 ( 624 )   HTML ( 1)   PDF (1514KB) ( 538 )  
相关文章 | 计量指标
针对蚁群算法在求解大规模多维背包问题时存在的迭代次数过多、精度不高的不足,提出一种新的高性能的蚁群求解算法.算法将信息素更新和随机搜索机制的改进相融合.首先,基于对较优解的偏爱,采用Top-k策略从每次迭代的k个解中挖掘出对象间的关联距离;其次,以对象为信源借助关联距离建立信息素的扩散模型,通过信息素扩散的耦合补偿,强化了蚂蚁间的协作和交流;最后,利用一种简单的变异策略对迭代的结果进行优化.在通用数据集上的大量实验表明:与最新的蚁群算法相比,新算法不仅能获得更好的最优解,而且收敛速度有显著的提高.
基于ε占优的正交多目标差分演化算法研究
龚文引 蔡之华
2009, 46(4):  655-666. 
摘要 ( 529 )   HTML ( 0)   PDF (1625KB) ( 733 )  
相关文章 | 计量指标
演化多目标优化是目前演化计算中热门研究方向之一.但是, 要设计一种高效、鲁棒的演化多目标优化算法,使其找到接近最优和完整的非劣解集是一项很困难的任务.为了能有效求解多目标优化问题, 提出了一种新的多目标差分演化算法.新算法具有如下特征: 1)利用正交实验设计和连续空间量化的方法产生初始群体, 使得初始群体中的个体可以均匀分布于搜索空间, 并且可以使好的个体在演化过程中得到利用;2)采用Archive群体保存非劣解, 并利用ε占优方法更新Archive群体, 从而可以使算法较快获得分布很好的Pareto解集;3)为了加快算法收敛, 提出一种基于随机选择和精英选择的混合选择机制.通过8个标准测试函数对新算法进行测试, 并与其他一些多目标演化算法进行比较, 其结果表明新算法可以有效逼近真实Pareto前沿且分布均匀, 并且在收敛性和多样性的求解精度和稳定性上与其他算法相当.同时, 通过实验的方法验证了新算法改进之处的有效性, 并进一步讨论了差分演化算法中CR取值和混合选择机制中选择控制参数λ取值对算法性能的影响.
JLU-RLAO和JLU-QLAO:两个不确定智能规划求解系统
孙吉贵, 殷明浩, 吕 帅,
2009, 46(4):  667-675. 
摘要 ( 1159 )   HTML ( 0)   PDF (924KB) ( 453 )  
相关文章 | 计量指标
不确定环境下的智能规划问题往往假设世界状态的转移概率是确切可知的,然而规划建模专家有时只能在信息不完备的条件下进行建模,从而只能通过猜测或者不完全统计的方法来获取不完备的有关状态转移不确定性的定量信息,有时甚至只能获取相关的定性信息.在2004年概率规划比赛冠军LAO系统的基础上设计了JLU-RLAO系统和JLU-QLAO系统.它们可以在无法获得精确的状态转移概率条件下,依然保证规划求解的健壮性.实验结果表明,JLU-RLAO系统和JLU-QLAO系统可以快速高效地解决上述不确定智能规划问题.
新的流形学习方法统一框架及改进的拉普拉斯特征映射方法
侯臣平 吴 翊 易东云
2009, 46(4):  676-682. 
摘要 ( 744 )   HTML ( 0)   PDF (1171KB) ( 570 )  
相关文章 | 计量指标
流形学习是多个领域的重要研究课题.通过考察各种流形学习方法,提出了一种新的流形学习方法的统一框架,并在此框架下对拉普拉斯特征映射方法(Laplacian eigenmap, LE)进行了分析.进一步,基于此框架,提出了一种改进拉普拉斯特征映射方法(improved Laplacian eigenmap,ILE).它建立在LE方法和最大差异延展算法(maximum variance unfolding,MVU)的基础上,在保持流形谱图拉普拉斯特征的同时,以最大化任意两点之间的差异为目标.ILE有效地解决了拉普拉斯特征映射方法对邻域选择敏感以及MVU方法大计算量、局部限制过强等问题,且能够保持数据聚类性质,挖掘数据内蕴特征.通过实验说明了ILE的有效性.
关联文本分类的规则修正策略
邱江涛, 唐常杰, 曾 涛, 刘胤田,
2009, 46(4):  683-688. 
摘要 ( 484 )   HTML ( 0)   PDF (768KB) ( 528 )  
相关文章 | 计量指标
通过分析基于关联规则的文本分类,发现在保持分类规则对正例样本正确分类的同时减少对反例样本的错误分类可以提高分类的精确度.基于否定选择算法的思想提出了分类规则修正策略,用反例样本集合对分类规则进行耐受,从分类规则错误判别的反例样本中再产生规则,与原来的规则组成新规则,称为增强关联规则.基于修正策略产生的增强关联规则可以大幅度地减少对反例样本的错误分类,从而提高分类的精确度.通过形式化证明和实验,分类规则修正策略的有效性得到验证.
基于语音和笔的手写数学公式纠错方法
姜映映, 敖 翔, 田 丰, 王绪刚, 戴国忠,
2009, 46(4):  689-697. 
摘要 ( 682 )   HTML ( 2)   PDF (1378KB) ( 529 )  
相关文章 | 计量指标
采用识别技术的用户界面往往由于识别率的限制容易出错,如何为这类界面提供自然高效的纠错方法十分重要.手写数学公式具有二维结构,难以识别和纠错.提出一种用于纠正手写数学公式识别错误的多通道技术.它允许用户使用笔纠正切分错误,用笔和语音纠正符号识别和表达式结构分析错误.该技术的核心是一个多通道融合算法.融合算法以笔选择的符号和语音作为输入,根据语音输入的类型是数学术语或者数学符号分别选择融合方法,最后修正手写公式并输出最有可能的识别结果.实验结果表明,该技术能有效地纠正手写数学公式识别中的错误,它比基于笔的单通道纠错技术更加高效.
一种基于反馈信息的地址寄存器提升方法
张 超, 吕 方, 王 蕾, 冯晓兵,
2009, 46(4):  698-704. 
摘要 ( 496 )   HTML ( 0)   PDF (1539KB) ( 493 )  
相关文章 | 计量指标
在MIPS,ALPHA,SPARC和PowerPC等体系结构中,对全局变量和静态变量的访问一般采用间接寻址的方式.由于变量地址和变量值不在同一数据段,使得数据访问的局部性不好.这样,每次访问变量地址会导致大量冗余的数据cache不命中访存操作.此外,这种寻址方式会产生两条连续的有数据依赖的操作,降低了程序的指令级并行性.提出了基于反馈信息的地址寄存器提升算法(address register promotion based on feedbacks, ARPF).该算法减少了对全局变量地址和静态变量地址的冗余访问,提高了程序的ILP(instruction level parallelism),同时避免了由于寄存器压力增加导致性能下降.在龙芯编译器上实现了该算法.实验表明ARPF对SPEC CPU2000INT所有测试用例有1%~6%的性能提升.