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

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

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

路径节点驱动的低代价最短路径树算法721-728

摘要：Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT（shortestpathtree）;该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT（least-costshortestpathtreealgorithm）.通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.

利他驱动的应用层组播729-735

摘要：节点自私问题是目前应用层组播技术面临的挑战之一.自私节点可能有意或者无意地停止转发某些数据包,导致流媒体质量下降.为了解决应用层组播中节点自私性问题,提出了一种利他驱动的应用层组播,简称ADALM机制.ADALM根据一个节点对其他节点的转发贡献,计算出该节点的利他值;基于利他值构造组播树,使得利他值较大的节点位于树的较高层.和本领域其他研究相比,ADALM在利他值计算和组播树构造方面均有创新：首先,利他值基于父亲节点和孩子节点的反馈,使得系统可以有效地检测出自私节点;节点无需发送额外的探测包去测量其邻居节点的服务质量;在组播树的构造和维护过程中,仅需要调整O（lgN）个节点;最后,利他值计算和组播树构造采用分布式方法来实现.仿真结果表明,即使存在一定比例的自私节点,ADALM也能构造一棵高性能的组播树,并且具有较低的控制负荷.

SOSC：一种基于自组织语义聚类的P2P查询路由算法736-745

摘要：在没有辅助机制的条件下,非结构化P2P网络资源定位技术的效率比较低,很难同时获得较低的查询延迟、少量的定位成本和较高的查询命中率,为此,提出了一种基于自组织语义聚类的P2P查询路由算法SOSC.SOSC算法通过直接用节点共享资源的关键词频率向量表达节点语义,各节点均试图与最相似的节点建立邻居关系,以及以指数衰减方式传递节点语义向量,创造性地解决了对等计算环境中聚类语义的表达和传递问题,使得节点可感知周围节点的语义层次,从而使得各节点均可以语义聚类为基础进行快速路由.分析和实验均表明,SOSC算法具有较小的路由延迟、较低的查询代价和较高的查询命中率.

计算机研究与发展杂志研发动态

“超越摩尔定律的科学与工程”计划745-745

摘要：美国国家科学基金会将继续为“超越摩尔定律的科学与工程”计划（Science and Engineering Beyond Moore’s Law）拨款9618万美元，资助这项整合了纳米科技、计算科学、材料科学和物理学的多学科研究课题．该计划简称为SEBML，目标是通过支持那些可改进或取代现有半导体集成技术的研究项目，打破现有技术上的极限，突破摩尔定律，使纳米技术、计算方法、软件设计和芯片结构方面的基础研究能够推动新一代芯片制造技术的开发，进而保持美国在通信和计算领域的前沿地位．

在亚马逊云中搭建1万个核心的Linux超级计算机745-745

摘要：Cycle Computing已经在亚马逊的弹性云（EC2）上搭建了几个集群，目前可扩充到数千个核心．生物科技企业Genentech的科学家Jacob Corn需要1万个计算核心云集群计算能力来考察蛋白质的相互链接，这项研究最终有可能引入医学治疗过程．这1万个核心是由每8个核心带1250个实例构成，此外还有8．75TB的RAM和2PB的磁盘空间．

英鼓励中小企业积极参与信息通讯项目建设745-745

摘要：英国《政府信息通讯技术战略》正式出台．该战略旨在帮助英国政府降低信息通讯技术项目成本，以更好地服务于大众．该战略强调，中小企业具有极佳的创新能力，能够向政府提供更多更有创意、更灵活、性价比更高的产品和服务．因此在政府采购过程中，要鼓励中小企业积极参与．政府将在今后公布政府采购的细节，努力减少采购中的官僚主义，

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

开放网络环境下分布式动态频谱分配算法746-755

摘要：为了提升开放网络的通信效率、增加网络容量,研究了采用不同通信协议时无线设备的共存问题,提出一种基于开放网络的分布式动态频谱分配算法.该算法通过按轮次调整各个通信对端所使用的信道,将不同设备占用的工作信道均匀地分布于开放网络频谱的各个部分,提升了开放网络的总体容量.同时,探测指数的使用降低了算法运行的通信开销以及控制信令对邻居域内数据传输带来的干扰.仿真实验表明,该分配算法提升了网络整体工作效率,并从一定程度上保证了不同通信对端之间传输性能的公平性.

libpcap-MT：一种多线程的通用数据包捕获库756-764

摘要：libpcap数据包捕获函数库提供数据包捕获、过滤等上层API,目前广泛被网络协议分析、入侵检测等数据包处理系统使用.多核、多CPU通用计算平台为数据包的高速处理提供可能,但libpcap提供的单线程机制难以充分利用多核、多CPU平台的并行计算能力.设计并实现了一种支持多线程的libpcap：libpcap-MT.libpcap-MT在内核态进行高效的数据包分发,采用无锁的多缓存队列允许多线程同时读取数据包,提供灵活的数据包分发策略,接口与libpcap保持兼容.实验结果表明,使用libpcap-MT能够快速地将现有的系统多线程化,并且具有更好的性能和可扩展性.

基于谓词式覆盖技术的/订购机制及算法研究765-777

摘要：基于内容路由的/订购（Pub/Sub）技术具有异步、松散耦合和多对多通信等特点,使得能更好地应用于大规模分布式交互系统.而高效率的匹配算法、路由算法及较低的订购维护成本（规模）是实现基于内容路由的大规模Pub/Sub系统所要解决的关键问题.提出了谓词式关系（二叉树）的概念,在此基础上提出并实现了基于谓词式覆盖技术的订购算法、退订算法及启发式匹配算法（合称PRBT-＊算法）.通过将谓词式覆盖技术同选择性订购转发策略相结合,在提高事件匹配效率及路由效率的同时,显著降低了各级内容路由器订购规模.理论分析及大量实验对比表明,谓词式覆盖技术的引入,在降低各级内容路由器订购规模及提高算法效率和系统整体性能方面获得了良好的效果.

计算机研究与发展杂志研发动态

多源交互式应用层组播路由协议778-785

摘要：应用层组播无需扩充底层基础网络就可以实现较大范围的组播通信,已成为倍受瞩目的组播实现机制.但相对于传统的IP组播,应用层组播的网络延迟大,节点稳定性差,使得采用应用层组播来实现多源交互式组播应用成为一个独特的具有挑战性的问题.Thunder协议将组播结构分为核心网和树两部分：核心网通过Mesh-Tree结构追求快速转发以优化交互式过程;树允许更多的成员接收组播数据,却不会对交互过程产生影响,可提高协议的扩展性.实验表明,Thunder协议能够减小交互式应用层组播的网络延迟,具有较好的扩展性和容忍延迟变化特性,适用于各种不同规模网络.

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

基于延迟唤醒的无线传感器网络的分布式区域覆盖算法786-792

摘要：针对现有无线传感器网络中分布式区域覆盖算法中存在覆盖空洞现象、连通性和蚕食现象等问题,提出了一个保证区域全覆盖与网络全连通的临界条件,在此基础上,提出了一个基于延迟唤醒的分布式区域覆盖算法.该算法采用分轮机制,因此不需要预先了解网络的整体拓扑结构;基于延迟唤醒的活跃节点集选择机制在保证区域全覆盖、避免出现覆盖空洞现象的同时,减少了蚕食现象的发生.仿真实验表明,与现有分布式覆盖算法相比,该算法可在满足用户区域覆盖感知需求的基础上延长网络的生命周期.

机会网络中的消息传输路径特性研究793-801

摘要：高效的消息传输机制是机会网络的核心问题.在对CRA WDAD公开的Trace数据进行深入分析的基础上刻画了机会网络中的消息传输路径特性.节点的相遇时间分析指出节点间存在明显的聚集性,少量的节点相遇对网络的连通性和消息传输成功率起决定性作用.为分析该特性对消息传输路径的影响,构造了机会网络的时间演化图TEG（time evolving graph）模型以计算任意节点对间的消息单拷贝最小延迟路径（single copy minimald elay path,SC-MDP）.结果表明网络具有典型的＂小世界＂特性,即大多数消息平均通过较短路径可达目的节点.结论指出,探测并利用发生次数较少但对网络连通性具有重要影响的节点相遇进行消息转发,能够有效降低网络的传输代价和提高传输成功率.

自适应帧Aloha的RFID标签防冲突协议802-810

摘要：为减少重复识别标签的时间,在动态帧时隙Aloha的RFID标签防冲突协议的基础上提出了一种自适应的动态帧时隙Aloha（adaptive dynamic framed Aloha,ADFA）的防冲突协议.在ADFA协议中,阅读器每成功识别一个标签就自适应地给该标签分配一个时隙号,该时隙号规定了标签在一次识别过程中被阅读器识别的顺序,若当前识别过程中待识别的标签与上一次识别过程中的标签相比有较多的重复,ADFA协议就可以减少冲突和空时隙,从而减少标签识别时间.另外,为进一步减少ADFA协议识别标签的时间,还对其作了改进,在改进的ADFA协议中,提出了一种低复杂度标签估计和最优帧长方案.理论分析和仿真结果均表明,ADFA协议在重复识别标签时能够减少识别时间,改进ADFA协议的标签估计方法能够减少计算复杂度,而其最优帧长方案能使系统的吞吐量得到提高.

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

QBF求解算法研究综述811-822

摘要：近10年来,布尔可满足性（SAT）求解技术飞速发展,并已经成功应用于模型检验、定理证明等领域,特别是在限界模型检验（BMC）中取得了明显的进展,然而,由于命题逻辑公式的长度随系统规模指数倍增长,基于SAT的模型检验仍然存在状态空间爆炸问题.带量词的布尔公式（QBF）作为SAT公式的自然扩展,具有紧凑的空间结构、更强大、更直观的表达能力,能够简洁地描述模型检验中的公式.基于QBF的模型检验有希望缓解状态空间爆炸问题,成为当前研究的一个热点.总结了当前主流的QBF求解算法及常用的优化技术,指出了该领域中值得关注的新趋势.

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

基于网格和密度的海量数据增量式离群点挖掘算法823-830

摘要：处理海量和高维数据已经成为设计离群点算法面临的重要任务和挑战,针对海量数据的特点提出一种基于网格和密度的增量式离群点挖掘算法IGDLOF,算法的基本思想为：采用网格的七元组信息减少数据维数和数量,利用增量更新减少内存需求.通过代表点过滤相应的主体数据,先判断再进行近似密度计算的方法减少计算量,降低算法的复杂度.通过在真实和仿真数据集的测试表明,IGDLOF增量算法可与LOF算法保持相同的精确度,而执行效率得到显著的提高.

基于描述逻辑规则的语义Web服务组合831-840

摘要：针对OWL-S语义Web服务自动组合问题,提出了一种基于描述逻辑（DL）规则的建模和组合方法.将ServiceProfile中的原子服务及其输入、输出参数分别建模DL中角色和概念,将概念间上下位关系和ProcessProfile中组合流程模型建模为DL规则,以一种统一的方式刻画语义Web服务的静态功能语义和动态交互特征;提出了刻画顺序服务组合的DL规则链和描述Split＋Join结构的服务组（WSC）模型,将并发服务组合转为基于WSC的顺序组合,将语义Web服务组合归结为WSC和DL规则链发现过程.与已有的方法相比,该方法将语义Web服务组合问题统一在DL规则的框架下,弥补了基于DL无法描述Web服务动态特征的缺陷,避免了Petri网推理和谓词演算等进行Web服务组合时限于命题逻辑层面无法充分利用语义信息的问题,也克服了基于智能规划的组合方法限于顺序组合的问题.

基于不平衡学习的分类器博弈模型及其在中国象棋中的应用841-847

摘要：计算机博弈是人工智能领域中的热点研究课题.传统计算机博弈模型使用极大极小搜索与评估函数相结合的方式,棋力高低依赖于搜索的深度.在计算性能较低的平台上,搜索深度加深会延长反应时间.因此,提出了一种应用不平衡学习技术使用专家谱训练分类器的机器博弈解决方案,反应时间只相当于一层搜索,且更能体现学习的特性.使用3种经典的不平衡学习方法训练神经网络,并对结果进行了比较.验证了使用分类器模拟中国象棋策略的可能性,以及不平衡学习技术在该策略建模过程中起到的关键作用.

基于拟态物理学方法的全局优化算法848-854

摘要：受拟态物理学方法的启发,就物理个体与理想粒子的特征异同问题,通过建立拟态物理学方法与基于种群优化算法的映射关系,设计出一种面向全局优化函数的拟态物理学算法框架.这是一种基于群体的随机优化算法,每个样本解被看作一个具有质量、速度和位置属性的物理个体,个体质量是用户定义的有关其目标适应值的函数,个体的适应值越好质量就越大,则个体间的虚拟作用力就越大.利用牛顿万有引力定律定义了个体之间的虚拟作用力,制定了个体之间的引？斥力规则,使得适应值较好个体吸引适应值较差个体,适应值较差个体排斥适应值较好个体,最好个体则不受其他个体的吸引或排斥.该方法利用这种引？斥力规则使得整个种群向更好的搜索区域移动.实验结果表明该算法的有效性.