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

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

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

一种支持多维数据范围查询的对等计算索引框架529-540

摘要：如何有效地支持多维数据范围查询是传统数据管理领域的研究热点之一．但是，在大规模分布式系统中，这仍然是一个具有挑战性的研究工作．VBI—tree是一个对等计算环境下基于平衡树的索引架构，在该架构上可以实现集中式环境下的多种支持多维数据索引的层次化树结构，例如R—tree，X—tree和M—tree等．VBI—tree设计的查询算法保证查询可以从树的任意位置开始，而不是像集中式环境下层次化树结构那样采用从树的根节点开始查询的方法，从而成功地避免了根节点引起的系统性能瓶颈问题．对于有N个节点的网络，索引方法可以保证查询效率是O（logN）．VBI—tree提出了基于AVL—tree旋转的网络重构负载均衡策略可以有效地均衡负载．另外，在数据操作频繁的情况下，为了提高索引的性能，在VBI—tree上建立特殊的祖先一子孙链接形成VBI^＊-tree的结构．通过使用祖先一子孙链接，可保证对于相关查询区域的探索尽量发生在同层节点之间，而不是一直往根节点方向发送，从而减轻上层节点的查询负担，并且显著地降低了更新代价．模拟实验验证了提出的方法的有效性．

报文分流最优策略研究541-548

摘要：在向下一代互联网络演进的过程中，一个重要的趋势是IP网络将成为语音、视频等应用的主要承载．VoIP是一个重要的语音应用．然而，IP网络的丢包造成了VoIP的服务质量不能得到保证，并且对于VoIP而言，连续丢包对其服务质量的影响要远大于分散丢包．报文分流是近年来学术界讨论的一种提高VoIP服务质量的方法，其基本思想是把1个VoIP会话的报文分散到多个网络链路传输，从而把连续丢包转化为分散丢包，缓解丢包对VoIP服务质量的影响．然而，目前的研究只局限于用一种特定的分流策略（平均分流）说明报文分流的潜力．报文分流的理论基础，比如报文分流能在多大程度上提高VoIP的服务质量，什么是最优的分流策略等，并不明了．对报文分流的理论基础进行了研究，首次给出了分流策略与VoIP服务质量的定量关系描述，给出并证明了Bernoulli网络丢包模型下的最优分流策略．同时，以ns-2仿真实验验证了该最优分流策略在Gilbert网络丢包模型下的有效性．

普适环境中面向推理的上下文缓存置换算法549-557

摘要：上下文缓存是减少上下文信息访问开销、降低信息传输数量、缓解连接中断引起的程序不可用性的有效途径．面向推理的上下文缓存置换算法CORA的目标是使上下文缓存达到较高命中率，有效节省普适计算中传输上下文的开销．CORA采用状态空间对低级上下文到高级上下文的推理进行建模，对各种上下文推理方法具有普遍适用性．CORA算法分为两个部分：1）在缓存端，该算法计算低级上下文的访问概率和预计失效时间，获得数据的缓存价值，作为上下文缓存置换的依据，以提高缓存的命中率；2）在传感器端设置相应的可变化范围，当传感器读数超出该范围时，主动更新缓存，以保证缓存数据的一致性．模拟实验将CORA和经典的缓存置换算法LRU进行对比，分别通过改变缓存容量、对上下文访问概率的不均匀程度和上下文更新访问比来考察两种算法的命中率，结果显示，当缓存容量相对上下文总数较小、访问概率分布较不均匀、更新访问比较高的情况下，CORA的命中率大大高于LRU．由此证明，CORA更适用于较为动态的普适计算环境．

分簇的扩展超宽带传感网生存期的下界558-565

摘要：无线传感网的一个基本挑战是能量受限，因此网络生存期是无线传感网最关心的课题．考虑了随机分布在面积为Sn=λn的正方形上的，2个传感节点和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无线传感器网络自定位算法566-574

摘要：传感器节点的自定位问题是无线传感器网络的重要研究内容之一．APIT是一种主要的非基于测距的定位算法．相对于其他非基于测距定位算法，APIT具有定位精度高、通信开销小等优点．但是，APlT要求有较高的锚节点密度，而且在APIT测试过程中，边界效应以及低邻居节点密度容易增加InToOut和OutToIn测试错误的发生次数．另外，APIT算法中的网格扫描算法对于0utToIn错误的容错性较差且其执行效率低．针对以上问题，提出了一种基于三角形重心扫描的改进APIT算法．首先，分析了APIT测试中的两种典型错误InToOut和OutToIn错误产生的原因，引入了对APIT测试方法的两处改进；然后，分析了网格扫描算法对节点定位精度和算法执行效率的影响，提出了一种三角形重心扫描法，有效改进了算法的定位精度和执行效率；最后，通过仿真实验验证了改进后的算法不但可以有效地减少InToOut和OutToIn两类错误发生的次数，提高平均定位精度，改善算法的性能，而且对OutToIn错误的容错性更强，执行效率更高，能够显著地提高节点的平均精度．

一种基于PSO的有效能量空洞避免的无线传感器路由算法575-582

摘要：无线传感器网络路由的一个重要问题是如何有效地均衡整个网络的能量消耗水平，避免形成能量空洞，从而导致整个网络过早死亡．基于无线传感器网络特性，首先将路由问题转化为线性规划问题，并证明了路由问题与线性规划问题的等价性．在此基础上，利用粒子群算法（particle swarm optimization algorithm，PSO）来求解能量空洞避免路由问题．算法重新定义了PSO的粒子、粒子的运算与“飞行”规则，提出了基于PSO的无线传感器路由优化算法．算法不仅能够适用于平面网络，经过稍加改进同样可以适用于层次网络的路由算法．通过理论分析证实了算法的正确性，同时大量的模拟实验证实了算法的有效性．

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

基于Hash函数的RFID安全认证协议研究583-592

摘要：无线传输、信号广播、资源受限等特点使RFID技术存在潜在安全隐患．在对RFID技术所面临的安全问题进行了详细地描述和分析后，提出了认证识别的单一会话模式和连续会话模式的概念，基于Hash函数设计了一个介于RFID标签和后端服务器之间的安全认证协议HSAP，以解决假冒攻击、重传攻击、追踪、去同步化等安全问题，并基于GNY逻辑给出了形式化的证明．由于在RFID标签中仅仅使用了Hash函数和或操作，因此HSAP协议跟先前的工作相比更适合于低成本RFID系统．

AES算法的并发错误检测方法及其VLSI实现593-601

摘要：提出了一种AES算法的抗差分差错分析的并发错误检测方法——二维奇偶校验方法．与原有的一维奇偶校验方法相比，该方法提供了更为优化的奇偶校验位设置，更重要的是能够同时检测水平和垂直方向上的奇数个错误，在保持了对单个错误的100%的覆盖率的同时，将对多个错误的覆盖率大大提升．由于水平和垂直校验位计算模块可以复用，因此与原有的一维奇偶校验方法相比，该方法增加的硬件开销很小，对硬件实现的关键路径和吞吐率都没有影响，是一种理想的低成本高效率的抗差分差错分析的并发错误检测方法．

计算机研究与发展杂志学术活动

全国第6届智能CAD与数字娱乐（CIDE2009）学术会议征文通知601-601

摘要：为了进一步促进我国在智能CAD、计算机动画、数字娱乐及数字艺术等领域的研究与应用，由中国图像图形学会计算机动画与数字娱乐专业委员会和中国人工智能学会智能CAD与数字艺术专业委员会联合主办、泰山学院承办的第6届智能CAD与数字娱乐学术会议，将于2009年8月15—17日在雄伟壮丽的世界首例双遗产——泰山举行．

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

基于多维数据流挖掘技术的入侵检测模型与算法602-609

摘要：网络访问数据有着数据流的高速、无穷达到的特点，所以利用传统多遍扫描数据库的挖掘技术来构建入侵检测模型是不可行的．针对网络访问数据流的特点，提出了一种基于多维数据流挖掘技术的入侵检测模型．此模型将传统的误用检测和异常检测两种入侵检测方法进行有机融合，因此能够克服目前广泛使用的误用检测方法无法检测新的攻击类型的缺点，并且也能够保持检测的高效性．网络访问数据记录的结构是复杂的，一个访问行为总是联系到许多属性，所以分析的难度很大．因此，引入多维频度等概念来解决网络数据流的模式表示和生成问题．同时，针对多维频度模式的特点，提出了一种新型数据结构MaxFp-Tree．在MaxFp-Tree的基础上，给出了一种高效的挖掘网络访问数据流的学习算法MaxFPinNDS．MaxFPinNDS采用衰减机制挖掘，可以快速地形成一个数据流的最近时期数据所隐含的最大频繁项目集．实验表明，设计的入侵检测模型是有效的．

计算机研究与发展杂志学术活动

第9届全国虚拟现实与可视化学术会议（CCVRV’09）征文通知609-609

摘要：由中国系统仿真学会虚拟现实技术应用专业委员会、中国计算机学会虚拟现实与可视化技术专业委员会、中国图像图形学会虚拟现实与可视化技术专业委员会主办，北京航空航天大学承办的第9届全国虚拟现实与可视化技术及应用学术会议将于2009年10月在北京举行．本次会议将集聚国内从事虚拟现实与可视化技术的研究人员和工程技术人员，广泛开展学术交流、研究发展战略、推动成果转化、共同促进虚拟现实与可视化技术的发展与应用．

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

基于动作单元分析的人体动画合成方法研究610-617

摘要：从运动捕获数据中提取出反映人体运动规律的基本动作单元，合成新的人体动画已成为研究热点．但已有动作单元提取方法忽略了运动序列的时序性和不同关节之间的运动相关性．针对该问题，提出了一种新的基本动作单元提取方法，首先，采用PCA方法对高维人体运动数据进行降维分析，并采用马氏距离平方度量姿态间的相似性；其次，结合动态时间归整方法和误差平方和准则对时序运动序列进行自动切分和标注；最后，建立不同动作单元之间的概率转移模型构建运动图，并根据约束条件合成新的逼真人体动画．

适于图像压缩的二维8×8DCT查表快速算法研究618-628

摘要：基于基本图像的概念及其对称性，提出一种计算二维8×8离散余弦变换（DCT）量化后系数的查表快速算法．新算法在消除乘法运算的同时也减少了加法运算量．通过设计查找表结构和组织数据，使得每次访问存储器得到的不是一个乘积数据而是一组乘积数据，有效地减少了查表次数；通过研究基本图像的对称性及DCT计算过程中数据的范围情况，减小了查找表（LUT）的长度．整个计算过程具有很强的并行性．在图像变换编码时，利用新算法可只计算需要被编码和传输的低频变换系数，以大大减少运算量．

基于小波多分辨率分析的指横纹定位新算法629-636

摘要：针对指横纹感兴趣区域（ROI）难以准确定位的问题，在明确提出指横纹ROI定义的前提下，提出利用小波多分辨率分析进行指横纹ROI自动检测定位的新算法．该方法利用纹理相似性原理，在高频子图采用基于特征向量和区域生长法产生指横纹的候选子区域集合，然后利用低频子图Radon投影得到的指横纹的区域特征对候选子区域进行验证，最后结合直线拟合手指轮廓得到指横纹在原图的有效位置，最终实现指横纹ROI的精准定位．实验证明该算法不仅能有效克服噪声以及手形姿态变化的影响，并且对多种情况有很强的鲁棒性．

二维测试数据压缩的优化637-643

摘要：为了减少内建自测试方案中的测试数据，基于输入精简技术（横向压缩）和TRC测试集嵌入技术（竖向压缩）的二维测试数据压缩的BIST方案，采用改进的输入精简算法和基于相容性判断的TRC种子选择算法，同时对横向和纵向压缩进行优化，包括在相同的相容百分数（PC）的条件下，确定位百分数（PSB）对竖向压缩的影响和在相同的PSB条件下竖向压缩算法中的PC对竖向压缩的影响两个方面．针对ISCAS89实验电路的实验结果表明，每一个PSB值都有一个最优的PC值范围EPClow-limit，PC high-limit使存储位数最小，并且PSB与最优的PClow-limit和PChigh-limit之间满足近似的线性关系．相对于现有的测试数据压缩方案，采用该优化的二维测试数据压缩方案实现的测试电路，不仅存储位数可减少20％～75％，而且可以达到ATPG工具所能达到的故障覆盖率．另外，测试控制逻辑电路简单，可重用性好．最后，由于在测试向量生成器和被测电路之间没有引入逻辑门，因此，不会对电路的性能产生影响．

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

基于变异和信息素扩散的多维背包问题的蚁群算法644-654

摘要：针对蚁群算法在求解大规模多维背包问题时存在的迭代次数过多、精度不高的不足，提出一种新的高性能的蚁群求解算法．算法将信息素更新和随机搜索机制的改进相融合．首先，基于对较优解的偏爱，采用Top—κ策略从每次迭代的κ个解中挖掘出对象间的关联距离；其次，以对象为信源借助关联距离建立信息素的扩散模型，通过信息素扩散的耦合补偿，强化了蚂蚁间的协作和交流；最后，利用一种简单的变异策略对迭代的结果进行优化．在通用数据集上的大量实验表明：与最新的蚁群算法相比，新算法不仅能获得更好的最优解，而且收敛速度有显著的提高．

基于ε占优的正交多目标差分演化算法研究655-666

摘要：演化多目标优化是目前演化计算中热门研究方向之一．但是，要设计一种高效、鲁棒的演化多目标优化算法，使其找到接近最优和完整的非劣解集是一项很困难的任务．为了能有效求解多目标优化问题，提出了一种新的多目标差分演化算法．新算法具有如下特征：1）利用正交实验设计和连续空间量化的方法产生初始群体，使得初始群体中的个体可以均匀分布于搜索空间，并且可以使好的个体在演化过程中得到利用；2）采用Archive群体保存非劣解，并利用ε占优方法更新Archive群体，从而可以使算法较快获得分布很好的Pareto解集；3）为了加快算法收敛，提出一种基于随机选择和精英选择的混合选择机制．通过8个标准测试函数对新算法进行测试，并与其他一些多目标演化算法进行比较，其结果表明新算法可以有效逼近真实Pareto前沿且分布均匀，并且在收敛性和多样性的求解精度和稳定性上与其他算法相当．同时，通过实验的方法验证了新算法改进之处的有效性，并进一步讨论了差分演化算法中CR取值和混合选择机制中选择控制参数λ取值对算法性能的影响．

计算机研究与发展杂志学术活动

DMAMH’2009国际会议征文通知第4届数字媒体及其在博物馆和文化遗产中的应用666-666

摘要：第4届数字媒体及其在博物馆和文化遗产中的应用（DMAMH’2009）国际会议由中国图像图形学会虚拟现实专委会主办．本次会议的目的是为数字媒体、博物馆、多媒体领域的研究人员提供一个最新技术知识和经验的交流平台，并讨论今后对相关领域未来研究的方向．届时将有该领域世界著名专家作报告，会议论文集将由IEEE出版（EI检索）．