计算机工程与科学杂志 北大期刊 CSCD期刊 统计源期刊

计算机工程与科学 2008年第12期杂志 文档列表

计算机工程与科学杂志计算机网络与安全

一种面向汇聚网络处理器模型的负载均衡算法1-4

摘要：本文提出一种由多个网络处理器组成的汇聚网络处理器转发子系统路由器结构模型，并设计了算法DIHDA对多网络处理器的负载进行均衡分配。实验结果表明，该算法能够在保持负载均衡的同时获得较好的报文保序效果，综合性能优于目前已有的同类算法。

一种基于体系结构的Web服务组合描述方法5-8

摘要：Web服务组合能够快速开发复杂的Web服务，以促进Web服务的增值。在分析并比较现有的Web服务组合方法的基础上，提出了一种形式化和工业化方法相结合的Web服务组合描述方法。针对Web服务及其组合的特点，研究了基于体系结构的Web服务组合描述方法，采用扩展的XYZ／ADL定义Web服务及描述其交互的连接件，最后结合一个实例描述Web服务组合的工作方式。

复杂社会网络的介数性质近似计算方法研究9-14

摘要：随着计算机和互联网的迅猛发展，面向互联网的社会网络挖掘和分析成为一个新的课题。从互联网挖掘的社会网络往往规模巨大，这对网络分析算法的性能提出了更高的要求。介数值作为图的重要结构性质，广泛应用于基于图的聚类、分类算法，如何降低其计算的复杂性是急需解决的问题。目前，常用的方法是利用对最短路径长度的近似来降低网络分析算法的复杂性，但已有的近似方法没有考虑现实大规模网络的复杂网络特性，对最短路径长度的近似方法也不能直接用于介数值的近似。本文提出了一种新的介数近似计算方法，其基本思想是结合复杂网络的结构特性，利用通过网络中枢节点的路径来近似最短路径，以近似的最短路径求得介数的近似值。这为图的结构性质的近似估算提供了一种新颖的思路。通过与传统的介数计算方法和近似方法进行实验比较，验证了本文的算法能够大幅降低计算复杂性，并保持较高的近似有效性，并通过对实验数据的分析得到了若干有益的结论，为进一步的研究工作奠定了基础。

无线传感器网络中能耗均衡的覆盖控制算法15-18

摘要：覆盖控制作为无线传感器网络的一个基本问题，对网络的生存时间、部署策略、通信协议和组网等问题的解决具有重要影响。在传感器节点随机冗余部署方式下，传统的方式是在保证覆盖要求和通信连通的前提下仅将最少量的节点投入活跃工作状态，从而降低网络能耗。但是，若频繁地激活同一批节点，会造成这些节点由于能耗过快而较早失效，使整个网络的冗余程度降低。然而，冗余度是传感器网络在单个节点性能有限的情况下提高整个网络的可靠性、容错性、精确性等的基础。为此，本文提出了一个能耗均衡ECB的覆盖问题，指出它是NP完全的，并给出了一个集中式近似算法。该算法根据节点的剩余能量赋于每个节点非负权，再基于Voronoi划分和贪心边方法，在保证覆盖要求的同时选择权和最小的节点激活。仿真实验结果表明，ECB算法求得的活跃节点集小，可以达到有效覆盖，并且可以保持网络的冗余度。

有向传感器网络中基于概率感知模型的最小连通k覆盖集算法19-22

摘要：无线传感器网络的基本问题之一是，网络节点如何利用有限的能量对人们所关注的物理世界进行满意的监测，这可抽象为最小连通k覆盖集问题。传统的最小连通k覆盖集问题是基于确定型全向感知模型的，该模型过于理想化，不能适用于复杂的应用环境，也不能应用于有向传感器网络中。针对上述局限，本文提出了有向传感器网络中基于概率感知模型的最小连通k覆盖集问题（MCKS），并指出这是NP难问题；设计了基于0-1整数规划和最小生成树的集中式近似算法（IPA）和基于覆盖效益探测的分布式近似算法（CBDA），分别证明两种算法最终得到的是MCKS问题的可行解，并分析了算法的时间复杂度、性能比和通信复杂度。通过仿真实验并与ILP算法和BGA算法进行比较的结果表明：在基于概率感知模型的条件下，IPA和CBDA能够有效实现有向传感器网络中的连通k覆盖，并且激活节点数目较少，网络寿命延长。

基于k—Means改进算法的分布式拒绝服务攻击检测23-26

摘要：分布式拒绝服务（DDoS）攻击是当前主要的网络安全威胁之一。本文分析了DDoS攻击的本质特征，提出了结合流量及流特征分布熵的检测策略，并根据问题需要改进了k—means聚类算法，并用之建立攻击检测模型。最后，使用LLDOS1．0数据集对该模型进行测试。实验结果表明，该模型具有良好的检测精度，验证了检测策略的有效性。

无线传感器网络密钥管理方案综述27-31

摘要：无线传感器网络密钥管理方案是无线传感器网络研究的热点问题之一。本文结合无线传感器网络的特点，分析了无线传感器网络中密钥管理方案的安全要求和评价指标，介绍了一些主要的密钥管理方案，并对它们进行了分析和比较，最后指出了研究方向。

计算机工程与科学杂志图形与图像

多指纹识别比较研究32-35

摘要：多指纹识别系统包括多手印系统和多手指系统。本文分析了多手印系统和多手指系统的具体模型，并通过五种典型的多生物特征融合技术Sum、Min、Product、Vote、Max对多指纹识别系统进行了比较研究。实验结果显示，多手指系统能够取得优于多手印系统的性能，多手印系统采用Max规则效果较好，而多手指系统采用Sum规则效果较好。这些结论有助于设计多指纹识别系统。

参数曲线曲面实奇异点的计算36-40

摘要：本文主要讨论了利用Grobner基理论对参数曲线（面）的奇异点进行判断和计算。如果曲线（面）存在奇异点，由定义可知它的导矢（法矢）等于0。因此，曲线（面）奇异点的判定就是方程组的求解问题。由Hilbert弱零点定理可知，若一组多项式方程无公共零点，则其生成理想约化的Grobner基为[1]。在计算时，首先根据Grobner基理论判断曲线（面）是否存在奇异点。当存在奇异点时，利用区间算法对实奇异点进行隔离和迭代。在确定奇异点的存在性时，根据曲线（曲面）的导矢（法矢）方程的Grobner基直接进行判断，而不需要求解非线性代数方程组。若曲线曲面存在奇异点，进一步采用区间方法对奇异点进行隔离以确定曲线段或曲面片的正则性。该方法可以得到参数曲线曲面的所有实奇异点且达到任意精度。

基于视觉噪声的粒子滤波定位法在RoboCup中的应用41-42

摘要：本文在足球机器人仿真组中引入基于视觉噪声的粒子滤波定位法的视觉信息处理策略，智能体通过此法更新其内部维持的世界模型，为上层决策提供一个更加精确的世界模型。

一种基于灰度直方图的遥感影像阴影自动检测方法43-44

摘要：在高分辨率全色遥感影像中，阴影的存在既给目标识别带来了困难，又包含了地物的层次和高度信息。本文运用灰度统计直方图的势函数对全色遥感影像的灰度统计直方图函数进行拟合，使用一阶差分找到直方图势函数的第一个谷点，以该谷点对应的灰度值对原始影像做阈值分割完成阴影检测。实验表明，在各种复杂地物环境下，本文方法都能完成灰度分割阚值的自动选取，其阴影检测结果是快速有效的。

基于深度优先搜索的一般图匹配算法45-48

摘要：对于一般图的匹配问题，Edmonds算法以Berge定理为基础，采用广度优先搜索增广路，图中可能存在“花”。遇到这种情况，要对它进行缩减“花”处理，再进行搜索。当找到增广路时，要将缩减图恢复，算法显得复杂。Gabow等算法使用先给固的顶点和边编号，并使用了不同数组和虚拟顶点，避免了处理花。算法的复杂性为O（n^3），但增加了空间复杂性。本文提出的基于深度优先搜索算法，在搜索增广路时不会出现“花”的情况，算法相对简单；同时，算法时间效率为O（n＊degree（n）），degree（n）为顶点的平均度数。另外，当图的边动态增减时，使用该算法可以很快调整最大匹配，并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。

一种基于核方法的手写数字图像去噪算法49-50

摘要：手写体数字图像去噪是手写数字图像识别主要的预处理过程。本文从统计特征的角度给出了图像噪声特点，并根据该特点运用核主成分分析的方法对图像进行去噪，给出并分析了基于该思想的去噪实验结果，最后给出了手写数字图像去噪问题未来的研究方向。

计算机工程与科学杂志算法研究

几种改进PSO算法在带时间窗车辆路径问题中的比较与分析55-59

摘要：车辆路径问题属于完全NP问题，也是运筹学中的热点问题。虽然目前有很多人进行研究，但搜索效率和迭优率较低，而且计算所得平均费用偏高。鉴于此，本文分别用二阶振荡PSO、随机惯性权重PSO、带自变异算子PSO、模拟退火PSO求解带时间窗车辆路径问题。通过仿真实验给出了这四种改进PSO算法在求解该问题时的不同；同时，与文献[1]中的遗传算法、标准PSO算法求解该问题进行了比较并得出结论：本文中用到的四种改进PSO算法都能更有效地降低成本，缩短运行时间，提高达优率，而且随机惯性权重PSO表现尤为突出。

目标可移动的直线搜索问题的在线算法研究60-62

摘要：直线搜索问题也被叫做迷失的奶牛问题，解决这个问题的算法叫做线性螺旋搜索。该算法被证明是解决这个问题的最佳在线算法，它的竞争比是9。如果这个问题中的目标可以移动，那么这个问题就被强化了。本文将提出被强化后的问题的最佳在线算法及其竞争比。Minimax定理在这个算法中扮演着重要角色。

贝叶斯网等价类学习算法63-67

摘要：贝叶斯网用一种紧凑的形式表示联合概率分布，具有完备的语义和坚实的理论基础，目前已成为人工智能领域处理不确定性问题的最佳方法之一。贝叶斯网学习是其关键问题，传统学习方法存在如下不足：（1）随节点数增多非法结构以指数级增加，影响学习效率；（2）在等价结构之间进行打分搜索，影响收敛速度；（3）假设每个结构具有相同的先验概率，造成等价类中包含结构越多则先验概率越高。本文提出一种学习马尔科夫等价类算法，该算法基于骨架空间进行状态转换，利用从骨架空间到等价类空间的映射关系实现学习贝叶斯网等价类。实验数据证明，该方法可有效缩小搜索空间规模，相对于在有向图空间搜索的算法加快了算法的收敛速度，提高了执行效率。

基于最小二乘支持向量机的特征增量学习算法68-71

摘要：本文针对传统的增量学习算法无法处理后采集到的样本中含有新增特征的问题，设计适应样本特征维数增加的训练算法。在基于最小二乘支持向量机的基础上，提出了特征增量学习算法。该算法充分利用先前训练得到的分类器的结构参数，仅对新增特征采用最小二乘支持向量机进行学习。实验结果表明，该算法能够在保证分类精度的同时，有效地提高训练速度并降低存储空间。

限制树宽的图的最小标记生成数算法72-74

摘要：本文研究了图的最小标记生成树问题。首先介绍在一般图上基于搜索树的最小标记生成树的算法；然后考虑了限制树宽的图，得到了效率更高的算法。该算法在树宽为常数的情况下，时间复杂度关于图的顶点个数为多项式，从而也证明了最小标记生成树在限制树宽的图上属于确定参数可解问题。