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

当期目录

2006年 第43卷 第2期    出版日期:2006-02-15
论文
DELIC:一种高效节能的与节点位置无关的传感器网络覆盖协议
毛莺池, 刘 明, 陈力军, 陈道蓄, 谢 立,
2006, 43(2):  187-195. 
摘要 ( 411 )   HTML ( 1)   PDF (604KB) ( 584 )  
相关文章 | 计量指标
现有的覆盖协议大多数都依赖于GPS、有向天线等基础设施或者定位机制,使节点获得其物理位置,这不仅成本高、能耗大,而且存在准确定位的问题.提出了一个分布的、高效节能、与节点位置无关的传感器网络覆盖协议(DELIC).在DELIC协议中,节点与邻居交换信息并通过能量大小竞选工作节点,其他未竞选成功的节点关闭通信设备.模拟实验结果表明,DELIC协议不仅可以提供高质量的覆盖性能,而且具有良好的节能性能. DELIC协议性能超过OGDC,PEAS,GAF-like,Sponsor Area协议.
一种基于自适应缓存机制的报文分类算法
张建宇 韦 韬 邹 维
2006, 43(2):  196-203. 
摘要 ( 479 )   HTML ( 0)   PDF (455KB) ( 539 )  
相关文章 | 计量指标
提出了一种高效、适用性好、易于实现的报文分类算法CSAC(classification on self-adaptive cache).该算法通过缓存属性子空间内报文集合的分类查询路径,将查询结果复用于同一子空间后续报文的分类.而缓存命中失效时也不必从头开始查询,减少了失效的时间开销.根据通信流量上下文变化对缓存运行状态造成的影响,算法采用自适应缓存机制,通过动态调整缓存的粒度、结构和缓存项在散列桶中的位置,有效地保证了缓存命中率.此外,算法不需要预处理过程,支持多维复杂规则(如4~7层属性、逻辑匹配操作等)和规则增量更新,比较适合于网络边界安全、用户流量审计和负载均衡等报文分类比较复杂的应用.采用CSAC算法开发的高端防火墙和入侵检测设备在实际网络环境中的性能良好.
PFED:一种基于预测的公平的主动队列管理算法
高文宇, 王建新, 陈松乔,
2006, 43(2):  204-210. 
摘要 ( 561 )   HTML ( 2)   PDF (393KB) ( 634 )  
相关文章 | 计量指标
对多个著名的主动队列管理算法进行了深入的理论分析和实验比较,对它们的优点和不足进行了总结,并在此基础上提出了一种新的主动队列管理算法PFED(prediction-based fair early drop). PFED的主要目标是:①通过对流量较为精确的预测,结合对分组丢弃概率更为合理的计算,将队列长度的变化稳定在一个理想的水平;②对非响应流实施有效的惩罚,提高算法的公平性;③通过合理的分组丢弃将队列(分组)的到达速率控制在链路的服务速率之下.仿真实验表明,PFED很好地实现了上述3个目标.
一个两步蓝牙散射网形成算法TBSF
李 香 杨孝宗
2006, 43(2):  211-217. 
摘要 ( 525 )   HTML ( 3)   PDF (346KB) ( 530 )  
相关文章 | 计量指标
蓝牙是一门新兴的低功耗、低成本短距离无线技术,它使便携设备能方便快捷地形成短距离无线网,同时为构建成本低廉的移动自组网带来了新的选择方案.提出一个异步的、完全分布式蓝牙散射网构造算法——TBSF,首先由所有蓝牙节点生成一系列独立匹克网,然后互连匹克网成为散射网. 基于节点邻居个数选择主或桥节点,通过一个节点角色转换图确定桥节点充当的角色.任意两个相邻匹克网之间通过惟一的连接路由互连,最终形成一个连通的散射网,主和桥节点构成散射网的一个连通支配集.仿真实验表明,TBSF算法创建散射网具有较好特性.
双向路径重选的自组网负载均衡路由协议
郑相全, 郭 伟,
2006, 43(2):  218-223. 
摘要 ( 449 )   HTML ( 0)   PDF (298KB) ( 430 )  
相关文章 | 计量指标
基于跨层负载感知和双向路径重选的自组网负载均衡路由协议(CLBLR)在路由发现阶段和路由维护阶段,将整个路径中各节点MAC层的总平均估计时延和路径总业务流负载结合起来,共同作为路由选择和路由调整的重要依据,通过双向路径重选方法实现最优路径选择和网络业务流的均衡分布和均衡传输.协议通过禁止中间节点对路由请求进行应答和阻止不必要的路由请求分组,经由重负载中间节点转发,以保证路由发现时能够利用最新负载信息,并避免了节点在重负载情况下成为新建路由的中间节点,使协议具有一定的拥塞控制功能,以间接的方式实现了请求接纳控制.上述措施使分组传输路由很好地避免了拥塞节点,减少了网络瓶颈对网络性能的影响.仿真表明,CLBLR在分组丢失率、平均端到端时延和路由附加开销等方面具有良好性能,其优良的分布式控制特征能适应自组网的动态环境.
自治型网络信息服务的建模
董文宇, 孙东红, 许 可, 李学东,
2006, 43(2):  224-230. 
摘要 ( 503 )   HTML ( 2)   PDF (369KB) ( 523 )  
相关文章 | 计量指标
自治服务是网络信息服务的新的需求,它使人机交互变得更加智能.为此提出了基于情景演算的自治型网络信息服务的建模方法.在标准的情景演算基础上,增加了对有效性约束常识的描述,建立了情景演算的分层知识库表示,将抽象的数学描述转化为较直观的描述模型;还设计了一种基于XML的情景演算建模语言ScML,以结构化文本脚本的形式描述了实际的应用需求并利用XML Schema实现了ScML的语法约束,利用XML XSL实现了从ScML脚本到Java代码的生成;最后给出日程管理服务的例子.
移动自组网中基于移动预测和概率的能量有效组播路由算法
罗玉宏 陈松乔 王建新
2006, 43(2):  231-237. 
摘要 ( 431 )   HTML ( 0)   PDF (426KB) ( 555 )  
相关文章 | 计量指标
移动自组网中节点的使用寿命很大程度上依赖于电池能量的有效利用.通过研究移动节点能量的剩余和使用情况,提出了一种新的关于节点能量估价函数PCF(power cost function)计算方法,能够较好地反映当前节点的能耗值.并且结合PCF提出一种基于移动预测和概率构造能量有效组播树M-REMiT(an algorithm based on mobility prediction and probability for refining energy-efficient multicast tree)的分布式算法,在节点移动的情况下,利用概率优化方法减少一棵组播树的总能量消耗,延长了组播树中每个节点的使用寿命.模拟结果显示这个组播算法比以前相关的算法具有更好的性能.
无线自组网络中基于簇结构的安全方案
张晓宁 冯登国
2006, 43(2):  238-243. 
摘要 ( 340 )   HTML ( 0)   PDF (359KB) ( 482 )  
相关文章 | 计量指标
无线自组网络是一种不需要基础通信设施的自组织网络,正得到越来越多的应用.当前自组网络的安全性研究正成为一个热点.对基于簇结构的自组网络进行了安全分析,并且针对存在的安全问题提出了新的安全解决方案.主要贡献在于:①提出了一个保护簇首的安全机制;②针对节点簇间漫游的安全隐患,提出一个基于请求的节点信息共享机制,并给出了相应的算法.对该方案进行了仿真实验,结果显示,该方案具有充分的可行性.与已有方案相比,该方案具有较完善的安全机制,网络性能也较好.
基于遗传算法的盲源信号分离
易叶青, 林亚平, 林 牧, 李小龙, 王 雷,
2006, 43(2):  244-252. 
摘要 ( 467 )   HTML ( 2)   PDF (558KB) ( 531 )  
相关文章 | 计量指标
从混合观测数据向量中恢复不可观测的各个源信号是阵列处理和数据分析的一个典型问题.独立分量分析是解决该问题的新技术,而基于四阶累计量的联合对角化(JADE)算法是独立分量分析最常用的算法,但此算法在k>2时得到近似解,且结果不精确.提出了一种基于遗传算法盲源信号分离的算法,此算法克服了JADE算法的不足,理论分析和仿真结果表明了该算法的可行性和有效性.
基于结合空间拓扑和方向关系信息的空间推理
孙海滨 李文辉
2006, 43(2):  253-259. 
摘要 ( 477 )   HTML ( 0)   PDF (461KB) ( 475 )  
相关文章 | 计量指标
结合了定性空间推理中著名的区域连接演算(region connection calculus, RCC)和基于区域的方向关系演算(cardinal direction calculus, CDC),并且给出两个演算在两个方向上的交互表,即RCC8-To-CDC 和CDC-To-RCC8.给出了结合RCC8和CDC知识的约束满足问题的路径一致算法(path consistency algorithm)(该算法是对Allen著名的路径一致算法的修改),并且采用两个队列实现了该算法,采用这种结构可以实现并行计算.在该算法中,基于以上两个交互表的交互操作被嵌入到算法里面来保证整个约束满足问题的一致性.算法的计算复杂性证明是多项式的.
感知器在语言模型训练中的应用
于 浩, 步丰林, 高剑峰,
2006, 43(2):  260-267. 
摘要 ( 546 )   HTML ( 2)   PDF (498KB) ( 735 )  
相关文章 | 计量指标
感知器(perceptron)是神经网络模型中的一种,它可以通过监督学习(supervised learning)的方法建立模式识别的能力.将感知器应用到语言模型的训练中,实现了感知器的两种不同训练规则以及多种特征权值计算方法,讨论了不同的训练参数对训练效果的影响.在训练之前,使用了一种基于经验风险最小化(empirical risk minimization, ERM)的特征选择算法确定特征集合.感知器训练之后的语言模型在日文假名到汉字(kana-kanji)的转换中进行评估.通过实验对比了感知器的两种训练规则以及变形算法的性能,同时发现通过感知器训练的模型比传统模型(N-gram)在性能上有了很大的提高,使相对错误率下降了15%~20%.
融合聚类触发对特征的最大熵词性标注模型
赵 岩 王晓龙 刘秉权 关 毅
2006, 43(2):  268-274. 
摘要 ( 622 )   HTML ( 0)   PDF (407KB) ( 638 )  
相关文章 | 计量指标
为解决传统HMM词性标注模型不能包含远距离词特征的问题,提出了形如“W\-A→W\-B?T\-B”的触发对来承载远距离词特征信息,并采用平均互信息量度对触发对特征进行选择.在最大熵框架下,将选择后的触发对特征加入到词性标注系统中.利用矢量空间模型提供的语义相似度计算功能进行词语聚类,聚类的结果和语义词典融合,建立聚类触发对特征用来解决触发词“W\-A”的数据稀疏问题.实验结果表明,与HMM相比,融合了聚类触发对特征的最大熵模型标注错误率减少了34%.
一种基于容错粗糙集的Web搜索结果聚类方法
易高翔 胡和平
2006, 43(2):  275-280. 
摘要 ( 319 )   HTML ( 0)   PDF (387KB) ( 516 )  
相关文章 | 计量指标
一些Web聚类方法把类严格作为互斥的关系,聚类效果不理想.一种基于容错粗糙集的k均值的聚类解决了这一问题.首先运用向量模型表示Web文档信息,采用常规方法得到文本特征词集,然后利用某些特征词协同出现的价值,构造特征词容错关系,扩充特征词的描述能力,最后用特征词容错类描述文档之间的相似关系,实现了Web搜索结果聚类,并提出了简单直观的衡量聚类精度的T模型.实验结果表明,利用容错关系聚类的类标记描述性强、容易理解、明显优于普通k均值算法.
计算主动数据库中不可归约规则集的有效算法
郝忠孝, 熊中敏,
2006, 43(2):  281-287. 
摘要 ( 469 )   HTML ( 0)   PDF (362KB) ( 437 )  
相关文章 | 计量指标
主动数据库中规则集的可终止性判定是一个重要问题,已经成为一个研究热点.有些研究工作提出了在编译阶段运用触发图和活化图的方法解决这个问题,其中的一个关键技术就是计算主动规则集的不可归约规则集.现有的计算方法由于具有一定保守性,使得计算出的不可归约规则集仍可进一步地归约,这无疑将影响到规则集的可终止性判定的准确性和运行阶段规则分析的效率.经过深入分析活化规则可无限执行的特点,提出了活化路径等概念.基于这些概念,提出了一个计算主动规则集的不可归约规则集的有效算法,使现有方法求得的不可归约规则集得到进一步的归约.
基于直方图的XPath含值谓词路径选择性代价估计
王 宇, 孟小峰, 王 珊,
2006, 43(2):  288-294. 
摘要 ( 367 )   HTML ( 0)   PDF (455KB) ( 455 )  
相关文章 | 计量指标
路径选择性代价估计是XML查询优化的基础,也是研究的热点.目前的方法采用大量正态分布和独立性分布假设是造成误差的根本原因.定义了一种新颖的值-位置直方图用于统计XML数据中的结构和值的分布情况,并提出了6种直方图运算.在此基础上,给出用直方图计算估计路径中任一结点选择性的方法.实验证明,这种方法无需独立性分布假设,也能在数据结构和数值分布不均匀的情况下,精确地估计路径选择性代价.
ASGT:基于预测和自适应性的移动事务并发控制方法
李晓荣, 施伯乐,
2006, 43(2):  295-300. 
摘要 ( 439 )   HTML ( 0)   PDF (382KB) ( 445 )  
相关文章 | 计量指标
在高质量的无线通信网络中,带宽不稳定和用户移动性成为影响移动事务处理的主要因素,导致事务冲突率上升、吞吐量下降和峰值情况复杂等结果.一种新的并发控制方法ASGT能够:①具有比2PL更小的阻塞面和更高的并发度;②预先发现非串行化调度,有效降低阻塞率,缩短阻塞时间. ASGT结合MWDL方法能够提高系统性能,降低调度代价.理论分析和模拟实验证明了ASGT方法的性能.
联机分析处理中的非规则维建模
李泽海, 孙吉贵, 赵 君, 于海鸿,
2006, 43(2):  301-306. 
摘要 ( 433 )   HTML ( 2)   PDF (370KB) ( 395 )  
相关文章 | 计量指标
预聚集技术通过预先计算并保存原始数据上的查询结果以实现联机分析处理系统的快速查询响应能力.然而,在实际应用中,许多非规则维的结构难以使用传统多维模型进行建模,从而影响了预聚集技术的使用.为此,基于子级别到父级别的部分映射定义级别之间的部分序关系,进而提出了一个支持非覆盖、非映上等非规则维中维级别关系建模的维模型.同时,在维模型基础上,定义了支持非规则维的立方体模型以及典型的联机分析处理操作.多维模型与关系模式的转换定义和实例分析证明了该多维模型可以实现对各种非规则维的建模支持,保证了预聚集技术在联机分析处理中的使用.
Norm驱动的网格工作流状态机模型
张世超, 徐寅俊, 顾 宁, 施伯乐,
2006, 43(2):  307-313. 
摘要 ( 405 )   HTML ( 0)   PDF (393KB) ( 521 )  
相关文章 | 计量指标
动态的网格环境赋予了网格工作流新的特征,从而进一步增加了工作流程的不确定性和复杂性.提出了Norm驱动的网格工作流状态机模型——GridWSM,利用Norm丰富的语义表达能力和适于描述复杂系统的特征来描述网格工作流系统中任务的动态调度,并利用其推理功能来完善Norm描述、检验Norm的语义冲突,不仅确保了Norm描述的完备性,而且反映了工作流程的实时变化,为系统仿真提供了理论基础.模型的原型系统NormTools验证了网格排序流程的Norm描述,检查出所有的错误.
一种基于协商的软件过程协同方法
赵欣培, 李明树, 陈振冲, 王 青,
2006, 43(2):  314-320. 
摘要 ( 380 )   HTML ( 1)   PDF (370KB) ( 442 )  
相关文章 | 计量指标
大型软件系统的开发大多要求多人协同完成.软件过程协同的一个重要特点是协同的参与者都试图通过实施协同任务来取得最大化的获利,因而协同的决策和实施不是强制性的,而是由软件开发人员或软件组织经过协商来进行的.传统的软件过程建模方法中对软件过程协同的描述是刚性的,即在满足进入条件或者被显式调用时,协同就一定会被触发,并按照一个规定好的规则或方针来实施,这样的方法难以适应软件过程协同中所表现的协商特性.提出了一个基于协商的软件过程协同方法,将软件过程描述为一组相对独立的、自治的、理性的、协作的软件过程Agent,过程Agent之间的协同关系由过程Agent通过协商确定,相比传统的方法,具有能够更好地适应软件过程协同的特点.
分支测试中测试路径用例的简化生成方法
毛澄映 卢炎生
2006, 43(2):  321-328. 
摘要 ( 261 )   HTML ( 2)   PDF (519KB) ( 550 )  
相关文章 | 计量指标
结构性测试是对过程式和面向对象程序都非常有效的测试方法,分支覆盖准则被实践证明是其中性价比最高的一种策略.通过深入研究DD图的性质并分析FTPS算法的不足,提出了一种简便、快捷和适合于大规模程序的非约束边集近似求解算法Find_SemiUE;还给出了基于正(逆)向广度(深度)生成树的分支测试路径用例集的简化生成算法Generate_PathSet,该算法在时间和空间开销上较FTPS算法均有较大提高.此外,所证明的关于DD图的结论也值得借鉴用于该图的更深一步研究.
多线程程序数据竞争的静态检测
吴 萍, 陈意云, 张 健,
2006, 43(2):  329-335. 
摘要 ( 812 )   HTML ( 0)   PDF (431KB) ( 896 )  
相关文章 | 计量指标
多线程并发程序的广泛使用带来了更多的数据竞争错误.传统的数据竞争静态检测由于对并发语义和别名信息的保守分析会导致很多假错误.因此,提出了一个精确有效的静态检测框架:分析应用了精确的别名分析并静态模拟了访问事件发生序;为提高分析效率,检测算法提出了一个以对象为中心,结合Escape分析缩小检测范围的检测算法并配合设计了压缩的别名等价类表示.检测框架在一个静态Java编译器JTool上做了实现,对于测试程序取得了很好的分析结果.
Cobol到Java翻译中的数据类型转换方法
石学林 张兆庆 武成岗
2006, 43(2):  336-342. 
摘要 ( 867 )   HTML ( 9)   PDF (384KB) ( 593 )  
相关文章 | 计量指标
将Cobol代码迁移到新的平台,如Java是减轻Cobol代码维护负担的一个有效方法.怎样将Cobol数据平滑迁移到新平台则是必须解决的基本问题之一.以前的大部分研究工作都直接将Cobol数据映射到现代程序设计语言中的基本数据类型,比如int,float等.但是,这种简单映射并不能保持原来的Cobol语义,从而导致目标码并不能与原来的代码运行一致.首先利用数据抽象技术对Cobol数据进行初步建模,在此基础上进一步提出了一个纯Java的功能等价的封装方法,可以有效地将Cobol数据描述映射到Java类型系统.该方法已经在一个Cobol2Java翻译系统——C2J翻译器中得到实现,并且应用于一个近400万行的真实银行商用系统.实验结果表明,此方法可以在保持功能等价的情况下,将Cobol数据无需手工干预地迁移到Java平台.
一种选择折叠计数状态转移的BIST方案
梁华国, 方祥圣, 蒋翠云, 欧阳一鸣, 易茂祥,
2006, 43(2):  343-349. 
摘要 ( 431 )   HTML ( 0)   PDF (404KB) ( 379 )  
相关文章 | 计量指标
提出了一种选择折叠计数状态转移的BIST方案,它是在基于折叠计数器的基础上,采用LFSR编码折叠计数器种子,并通过选定的存储折叠距离来控制确定的测试模式生成,使得产生的测试模式集与原测试集相等.既解决了测试集的压缩,又克服了不同种子所生成的测试模式之间的重叠、冗余.实验结果证明,建议的方案不仅具有较高的测试数据压缩率,而且能够非常有效地减少测试应用时间,平均测试应用时间仅仅是类似方案的4%.
集成电路高层故障模型间关系分析方法
杨修涛, 鲁 巍, 李晓维,
2006, 43(2):  350-355. 
摘要 ( 437 )   HTML ( 2)   PDF (294KB) ( 343 )  
相关文章 | 计量指标
集成电路的测试变得日益重要,传统的门级测试虽然效果很好,但是随着电路规模的增大而面临着测试时间太长的困境.高层测试可以很好地缓解测试时间过长的问题,但最大的困难是缺少恰当的故障模型.通过对高层故障模型与门级固定型故障模型间关系可以建立高层故障模型的评估规则,在该规则下可以再对高层故障模型间关系进行分析,以确定彼此间的覆盖关系.归纳模型间的互相覆盖以确定彼此是否包含,这有助于对高层故障模型进行评估,寻找能够对应逼近门级固定型(stuck-at)故障模型的高层故障模型序列,该模型序列有望指导新的测试生成.最后,以对ITC99中标准时序电路的实验来说明该理论方法.
三维服装仿真中的“服装-人体”快速冲突检测及响应算法
毛天露, 王兆其, 夏时洪,
2006, 43(2):  356-361. 
摘要 ( 431 )   HTML ( 0)   PDF (331KB) ( 540 )  
相关文章 | 计量指标
三维服装仿真可以为三维人体动画生成逼真的服装动态效果,但其中的冲突检测与仿真计算的时间复杂度太高,其实用性一直受到很大限制.提出了一种快速的“服装-人体”冲突检测及响应算法,在人体运动状态下,快速检测服装与人体之间的位置冲突,其时间复杂度仅为O(n)(n为服装模型上的顶点数目).在此基础上,提出一种合理有效的冲突响应机制,并实现快速稳定的三维服装仿真,取得了真实的仿真结果.
数据分发管理匹配算法的R-树实现
蒋夏军 吴慧中 李蔚清
2006, 43(2):  362-367. 
摘要 ( 555 )   HTML ( 2)   PDF (338KB) ( 530 )  
相关文章 | 计量指标
数据分发管理(DDM)是高层体系结构(HLA)接口规范的6类服务之一,高效的区域匹配算法是DDM研究的重点和难点.当前的多种匹配算法往往只适用于特定的应用环境,且效率不够理想. R-树法是在空间索引技术的基础上提出的一种新的匹配算法,该方法用R-树对DDM区域的矩形进行组织,并利用Hash索引对其叶结点的组织方式进行了改进.实验结果表明R-树法可有效减少动态DDM的维护开销,提高分布交互仿真的实时性.通过调整R-树的相关参数,可以进一步改善匹配算法的性能.
基于检索的人体运动识别和模拟
赵国英, 李振波, 邓 宇, 李 华,
2006, 43(2):  368-373. 
摘要 ( 402 )   HTML ( 1)   PDF (395KB) ( 461 )  
相关文章 | 计量指标
运动识别和模拟是人体运动分析中重要的研究内容.实现了以检索为基础的实验性的运动分析系统.小波矩具有平移、旋转和缩放不变性,能够提取局部多层次特征,被用来作为特征描述运动序列以及动作.根据相似性实现运动识别,利用动态时间变形(DTW)实现序列的动作匹配,在poser建模、依据正多面体分割的金字塔模型得到多视点投影视频的数据库中进行识别和匹配,并以三维模型的形式显示出来.实验结果可以模拟人体运动以及为进一步分析提供初始分析数据.