计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2006年第05期杂志 文档列表

计算机学报杂志研究论文与技术报告

一种满足QoS约束的自适应多径Ad Hoc网络路由协议681-689

摘要：提出一种以网关为中心的满足QoS约束的自适应多径路由协议GC-AQMR.该协议不仅保证建立从源节点到网关的链路不相交的多条路由,同时使中间节点也保留到网关的多径路由信息,当网络拥塞或路径失效时,中间节点根据这些信息可自适应地进行路由调整.模拟实验表明：采用GC-AQMR协议的SWAN系统在报文转发率、平均端到端时延、实时业务公平性以及端到端平均吞吐量等性能指标上,均优于基于AODV协议的SWAN系统.

Internet网络的访问直径分析690-698

摘要：结合复杂网络理论与CAIDA授权的关于Internet网络的真实海量数据,从复杂网络理论角度对真实的Internet数据进行分析与研究.首先借助物理学和生物学研究的方法,将Internet网络视为具有生命涨落特征的活体系统,形式化定义了Internet物理特征量--访问直径.然后根据目标复杂系统涨落演化特点,提出了3种基于Logistic模型的、以带衰减因子的正余弦函数组合模拟振荡涨落的数学模型.使用浮点型遗传算法分别进行拟合实验,并通过实验结果对上述3种模型进行优选.最终优选模型的拟合准确度为97.87%,预测准确度为97.47%,准确度高,符合Internet网络真实数据变化情况.文中使用模型对较远未来网络情况进行了预测,并得出结论：从现在开始至2011年12月,将是Internet网络高速发展时期,之后发展速度变缓,并于2021年10月左右趋于稳定,此时Internet网络访问直径为10.2073跳.最后,应用文中模型重点预测出了2008年8月北京奥运期间Internet网络访问直径为10.7726跳,并得出奥运期间Internet网络效率较高的结论.

使用模糊线性回归的自组网有效洪泛699-704

摘要：简单地描述了自组网的特点,对相关工作进行了比较;说明了大多数预测方法不适合自组网应用;为了保持拓扑稳定,文中采取了一个模糊线性回归模型用于预测长寿命链路;提出了一个路径可靠性和路径寿命的分析建模架构.分析结果表明,基于长寿命路径选路的路由协议可靠性更好,寿命更长.仿真结果也表明,和AODV路由协议相比,该协议有高的分组递交率和低的控制开销.

一种高效的计算带宽请求微时隙的算法705-710

摘要：首先提出了一种基于HFC网络和DOCSIS规范精确计算带宽请求微时隙的算法,该算法根据用户数据长度、MAC管理报文的大小计算出不同RF（射频）条件下发送上行数据所需要的最少微时隙数,有效提高了网络带宽利用率.其次,在算法实现上提出了一种优化的快速实现方法,引入Hash算法,构造了一个Hash函数,大大降低了算法的运算时间,可满足实时系统的要求.该算法已成功应用于由自主开发的物理层和MAC层芯片组成的HDTV（高清晰度电视）双向系统平台.实际网络环境下的测试结果表明该算法及其实现完全满足HDTV双向点播、VoIP、Internet网络通信等应用需求,在实际应用中表现出了良好的性能和可靠性.

关键方程的新推广711-718

摘要：给出了关键方程的全新的推广,构造了一个齐次关键模方程,并用域F上的两个变元的多项式环F[x,y]的齐次理想刻画该方程的解空间;证明了齐次关键模方程可以用来解决卷积码的盲识别问题,这是一个全新的研究课题,在智能通信、信息截获和密码分析等领域有重要的应用;利用该方法得到的二元多项式齐次理想Gr（o）bner基的快速算法,给出了求解齐次关键模方程的快速算法,也给出了详细的计算实例.大量的实验也证实了该文的各项理论分析结果.

LS-Ensem：一种用于回归的集成算法719-726

摘要：借鉴Friedman提出的基于函数空间的梯度下降搜索的思想,提出了一种新的集成学习算法——LS-Ensem算法.该算法只要求个体函数满足一个很宽松的条件,从而避免了每轮迭代中寻找最优个体函数所需的大量计算,显著地降低了算法的计算复杂性.理论分析表明该算法具有指数级收敛速度以及良好的泛化性能,文中还给出了泛化误差的界.仿真结果验证了理论分析的结论,并且还显示出LS-Ensem算法能够有效地抑制过拟合发生.

PHGA-COFFEE：多序列比对问题的并行混合遗传算法求解727-733

摘要：设计了一个求解多序列比对问题的并行混合遗传算法（与之相应的软件称为PHGA-COFFEE）.该算法采用COFFEE函数作为个体的适应度函数,构造了六种遗传算子,特别是设计了两种新颖的变异算子,其中一种变异算子基于COFFEE的一致性信息设计,以改善算法的整体搜索能力.另一种变异算子基于动态规划方法设计,以增强其局部搜索能力.通过对BAliBASE中144个测试例的测试,证明该算法是有效的.与已有的算法相比,该算法对处于朦胧区和具有N/C末端延伸的序列比对问题有更强的问题求解能力.同时通过对算法并行化,其运行时间显著缩短.

基于欧氏距离的矩形Packing问题的确定性启发式求解算法734-739

摘要：使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形Packing问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC和GSRC得到了验证.

多Agent系统问题求解的广义粒子模型方法740-750

摘要：提出一种多Agent系统分布式问题求解的新的广义粒子模型,将复杂环境下多Agent系统资源分配和任务规划的优化问题转变为广义粒子模型中的粒子运动学和动力学问题.广义粒子模型可以描述和处理的复杂环境包括多Agent系统中的Agent之间存在的随机、并发、多类型的交互行为.各Agent有不同的个性、自治性、生命周期、拥塞程度和故障几率等.本文讨论了广义粒子模型和多Agent系统分布式问题求解的关系,提出了广义粒子模型的数学物理模型和多Agent系统分布式问题求解算法,并且证明了它们的正确性、收敛性、稳定平衡性等基本性质.通过复杂环境下多Agent系统资源分配和任务规划问题的实验和比较,证实了广义粒子模型方法的有效性及其特点.

一类MPEG-4 FGS流视频传输的质量定义及算法751-759

摘要：对MPEG-4 FGS流视频的客观质量及质量变化指标的严格定义,是保证其在IP上有效传输以满足终端表示的可达主观质量的必要手段.基于PSNR（MSE）建立了MPEG-4 FGS流视频的相关客观质量和质量变化指标定义,提出了视频分段场景基础上的质量最优化问题,通过状态迁移图和动态规划解决了FGS流视频的最优传输策略问题.并且用试验数据对FGS流视频的优化传输的控制粒度及实时传输算法进行了对比分析.

基于球面谐波基图像的任意光照下的人脸识别760-768

摘要：提出了一种基于球面谐波基图像的光照补偿算法,用以在任意光照条件下进行人脸识别.算法分两步进行：光照估计和光照补偿.基于人脸形状大致相同和每个人脸的反射率基本相等的假设,首先估计了输入人脸图像光照的9个低频谐波系数.根据光照估计的结果,提出了两种光照补偿方法：纹理图像和差图像.纹理图像为输入图像与其光照辐照图之商,与输入图像的光照条件无关.差图像为输入图像与平均人脸在相同光照下的图像之差,通过减去平均人脸在相同光照下的图像,减弱了光照的影响.在CMU-PIE人脸库和Yale B人脸库上的实验表明,通过光照补偿,不同光照下人脸图像识别率有了很大提高.

基于多尺度小波包分析的肺音特征提取与分类769-777

摘要：提出了一种适于非平稳肺音信号的特征提取方法.以4种肺音信号（正常、气管炎、肺炎和哮喘）为样本数据,通过分析肺音信号的时频分布特点,选择了具有任意多分辨分解特性的小波包.对小波包进行空间划分后找到了适合肺音特征提取的最优基,并基于最优基对肺音信号进行快速多尺度的分解,得到了各级节点的高维小波系数矩阵,建立了小波系数与信号能量在时域上的等价关系,并将能量作为特征值,构造了低维的作为分类神经网络的输入特征矢量,大大降低了输入特征的维数.研究表明该算法的识别性能是高效的.

基于正交完备U-系统的参数曲线图组表达778-785

摘要：为了探索参数曲线图组的频谱性质,引进一类属于L2[0,1]的正交完备分片k次多项式系统（简称U-系统）.该系统下的U级数展开式具有良好的平方逼近及一致逼近性质,而且能用有限项U级数实现对分段k次多项式参数曲线图组的精确表达;基于U-系统理论,给出了用以计算给定几何图组U-谱的信息转换算法,该算法具有直观、简便、快速的特点.构建的数据处理平台可用于几何信息的分析与综合,并且能在信息安全（信息隐藏、数字水印）及模式识别等方面有实用价值;提供了用U-系统表达参数曲线图组的实验图例.

低成本的两级扫描测试结构786-791

摘要：提出了一种两级扫描测试结构：根据电路结构信息对时序单元进行分组,同组的时序单元在测试生成电路中共享同一个伪输入;将时序单元划分到不同的时钟域,在测试向量的置入过程中只有很小一部分时序单元发生逻辑值的翻转;引入新的异或网络结构,消除了故障屏蔽效应.实验结果表明,该两级测试结构与以往的方法相比,在保证故障覆盖率的同时,大大降低了测试时间、测试功耗和测试数据量.

RAID-VCR：一种能够承受三个磁盘故障的RAID结构792-800

摘要：提出了一种新RAID结构——RAID-VCR.这种结构仅需要3个额外的磁盘来保存校验信息,但是却能够承受任意模式的3个成员磁盘故障.与现有的其它RAID结构相比,RAID-VCR的容灾能力大幅提高,但是对磁盘空间利用率和系统吞吐量的影响却非常小.RAID-VCR的编码和解码过程都是基于简单的XOR操作,并且以明文方式保存了用户数据,从而可以高效地执行读操作.仿真实验结果表明,RAID-VCR的编码和解码性能较好,具有很好的应用前景.

K-ary N-cube网络中的维度气泡流控与无死锁完全自适应路由801-807

摘要：利用虚跨步切换技术中消息的依存关系只与相邻缓冲区队列相关的特点,设计了一种称为维度气泡流控（DBFC）的新型流控策略.该流控策略建立在虚跨步（VCT）切换和信约流控机制之上,通过分析端口信约值和路由信息实现点点间的流控.在无边带k-ary n -cube网络中,如果采用DBFC流控策略,即使网络中存在环相关,设计的自适应维度气泡路由（ADBR）算法仍可实现无死锁的最短距离的路由.对于以上结论,文中提供了详细的证明.最后,通过修改模拟工具RSIM的网络模拟器--NETSIM的代码,实现了DBFC流控策略和ADBR算法.模拟结果显示,ADBR算法在性能上比常用的维序路由优越,在报文延迟上有近17.5%的降低.

一种新的MPI Allgather算法及其在万亿次机群系统上的实现与性能分析808-814

摘要：给出一个新的MPI Allgather算法--邻居交换算法（neighbor exchange）.提出的平均逻辑通信距离的概念和计算公式,可以有效地衡量通信的局部性.通过分析,发现在4种MPI Allgather算法中,邻居交换和环算法均具有最优的通信局部性.在万亿次机群深腾6800和曙光4000A上对4个MPI Allgather算法进行的性能测试和分析结果表明,邻居交换算法的长消息通信性能最优,中长消息通信性能不稳定,短消息通信性能次于递归倍增和Bruck算法.

嵌入式处理器中访存部件的低功耗设计研究815-821

摘要：以“龙芯1号”处理器为研究对象,探讨了嵌入式处理器中访存部件的低功耗设计方法.通过对访存部件的结构、功耗以及关键路径进行分析,利用局部性原理,提出一种根据虚拟地址历史记录进行判断的方法,可以显著减少TLB和Cache对RAM块的访问次数,使得TLB部件功耗平均降低了28.1%,Cache部件功耗平均降低了54.3%,处理器总功耗平均降低了23.2%,而关键路径延时反而减少,处理器性能略有提高.