当期目录

• 2010年, 第12期　刊出日期：2010-12-25 上一期    下一期
  本期栏目： 论文

论文

一种高效的多媒体无线传感器网络地理路由算法

刘樑骄1，李仁发1，李哲涛1,2，乐光学1,3

2010, 32(12): 1-4. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 451 )   PDF (610KB) ( 570 )   　　

针对多媒体无线传感器网络数据流巨大的特点，本文提出一种高效的地理路由算法AOGR。与现有的地理路由算法以路由单包时的性能最优化为目标相比，AOGR将一次会话中所有交互数据包作为整体，使得平均每包传输的路由跳数最少。它充分利用先行包在路由方面的参考作用以优化后续包的路由。随着路由数据包的增多，AOGR最终收敛于最短路径。最后，通过仿真实验验证该路由算法能够有效地减少GPSR协议在周边转发模式时产生的绕道跳数，路由平均跳数有明显减少。

面向端用户的流媒体业务性能监测与分析

张玫1,2，曾彬1，黎文伟2，张大方2

2010, 32(12): 5-7. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 440 )   PDF (557KB) ( 433 )   　　

目前，已有的流媒体业务性能测量工具主要用于对服务进行压力测试，不能反映终端用户的实际使

用性能。本文从端用户角度设计了合理反映流媒体业务性能的指标，提出并实现了一种基于主动业务仿真

的流媒体业务性能测量方法，能及时向流媒体服务器反馈信息，实现动态的质量控制，并为流媒体业务系

统的优化提供依据。

容迟网络中基于节点能量考虑的混合散发与等待路由算法

王贵竹,卢华庭,徐亮

2010, 32(12): 8-11. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 500 )   PDF (539KB) ( 416 )   　　

容迟网络DTN是一个新兴的研究领域，这种网络中节点之间的连接时常发生中断并且难以预测，目

前一个常用的解决办法是使用多拷贝路由。但是，考虑到网络中多数节点能量供应受限的特点，大量额外

的消息拷贝传输会使网络中部分节点能量迅速消耗，直至节点停止工作，导致整个网络的路由性能快速下

降。针对容迟网络中的散发等待路由算法［1］，利用网络中不同节点在能量供应方面不同的特点，本文

提出了混合散发等待路由算法。仿真结果表明，与二分法散发与等待路由算法相比，这种路由算法通过不

同程度地利用各节点上的能量供应，在递交成功率、平均延迟方面能够取得较大改善。

基于IPv6的应用服务器的研究与实现

汪永琳

2010, 32(12): 12-14. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 431 )   PDF (608KB) ( 398 )   　　

IPv4协议最终将被IPv6协议所取代，但目前基于IPv6协议的应用研究还处于初始阶段。本文分析了FTP协议对IPv6 协议的支持情况，提出了一种Linux环境下基于IPv6协议的FTP 服务器实现方案。对实现的FTP服务器进行了测试，利用Sniffer软件进行了抓包分析。实验表明，该FTP 服务器完全支持IPv6 协议,并能实现用户登录、密码验证、文件列表传送、文件下载、文件上传、文件删除等功能。

基于MAC欺骗技术的嗅探器原型设计与实现

陈信男1，胡华平1，2，岳虹2

2010, 32(12): 15-18. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 502 )   PDF (618KB) ( 386 )   　　

在基于交换环境的局域网内，针对ARP欺骗技术的防御手段日益成熟，导致基于ARP欺骗技术的嗅探器极易受到安全防护软件的拦截与查杀，失去嗅探效果。本文提出了一种非ARP欺骗技术，即MAC欺骗技术，并设计与实现了一种基于MAC欺骗技术的局域网嗅探器原型。与传统ARP欺骗技术相比，这种欺骗技术可以绕过多种ARP防御工具，成功截取网络数据以及对目标主机进行拒绝服务攻击。本文通过采用时间交替机制、过滤机制等多种关键技术，有效地提高了嗅探器的效率和准确率。经过测试，本嗅探器可较好地突破安全防护软件的拦截与查杀，实现嗅探效果。

一种面向嵌入式实时系统的安全策略优化生成方法

曹小峰1，杨文强2

2010, 32(12): 19-21. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 473 )   PDF (531KB) ( 463 )   　　

由于受到系统资源和实时性的限制，对于嵌入式实时系统的安全扩展很难延用通用计算机系统的安全设计方法，因此需要对其进行专门的研究。为了在确保实时性的前提下使嵌入式实时系统的安全性达到最优，本文提出了一套完整的安全设计方法，包括安全任务图模型和安全评估模型，在此基础上，又提出了一种基于整数线性规划的安全策略优化生成方法ILPOS。该安全策略优化生成方法同时解决了安全算法选择和实时可调度性检测两方面的问题，克服了一般分阶段优化方法的不足，从而充分地利用系统可用时间来实现安全扩展。仿真实验结果表明，与传统的启发式安全设计算法相比，ILPOS方法在各种实时性约束条件下都能有效地提高系统的安全性。

基于规划识别的入侵检测研究

蔡增玉1，谷文祥2，甘勇1，刘书如1

2010, 32(12): 22-26. doi: 10.3969/j.issn.1007130X.2010.1

摘要 ( 480 )   PDF (436KB) ( 511 )   　　

规划识别是人工智能的重要研究分支之一，在入侵检测领域中已有初步的应用。本文在介绍规划识别和入侵检测基本概念的基础上，按照规划识别方法分门别类地研究了基于事件层的规划识别、基于贝叶斯网络的规划识别、基于扩展目标规划图的规划识别、彩色Petri网、对手规划、行为状态图等在入侵检测领域的应用现状和进展；接着深入分析了规划识别和入侵检测的关系和相似之处；最后讨论了基于规划识别的入侵检测存在的问题，并指出了未来的发展趋势。本文综述了智能规划在入侵检测中应用的关键技术和存在的问题，研究内容对于相关人员从事入侵检测研究具有重要的参考价值。

网络入侵危险性评估的云理论实现

万彪

2010, 32(12): 27-29. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 460 )   PDF (410KB) ( 526 )   　　

由于任何网络安全手段都无法完全阻止网络攻击，保护网络的绝对安全，因此对网络入侵危险性进

行评估，进而采取相应的防御手段就非常重要。传统的评估方法都无法同时评估网络入侵的不确定性（模

糊性和随机性），基于此，利用云模型理论把模糊性和随机性有效集成在一起的优点，提出了一种基于云

理论的网络入侵风险评估方法。本文给出了方法的理论基础、设计思想和关键实现技术及评估过程，并提

出了一种改进的逆向云生成算法。该模型通过对系统资源监控，并对得到的数据进行处理，然后输入到云

控制器，云控制器根据设定的规则做出评估结果。实验结果表明，该方法最大限度地保留了网络入侵评估

过程中固有的不确定性,提高了评估结果的科学性和准确性。

基于Portal的统一身份认证与系统集成研究

胡建鹏

2010, 32(12): 30-33. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 543 )   PDF (572KB) ( 531 )   　　

门户技术在数字化校园建设领域得到了广泛应用，统一身份认证和应用系统集成是其中的核心技术

，单点登录是实现统一身份认证的途径，提出一种利用Cookie令牌和访问控制程序来实现跨域访问控制的

单点登录方案，并使用LDAP用户数据库来完成统一的用户的登录、认证和权限管理。按照校园各种网络应

用系统的不同类型，提出了四种满足不同集成需求的系统集成方式，并在此基础上实现了基于门户的数字

校园架构。

基于量子遗传算法的高效匹配搜索策略

高颖慧,王平,王鹏

2010, 32(12): 34-38. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 555 )   PDF (537KB) ( 387 )   　　

在大规模源图像上进行图像匹配时，最佳匹配点的搜索策略是匹配算法时间性能的决定因素，设计

高效匹配搜索策略是提高算法性能的关键。为了减少搜索时间和提高匹配实时性，本文基于匹配源图像划

分和量子遗传算法基本原理，提出了面向大规模源图像匹配的目标淘汰搜索策略TESS。TESS将基于整幅源

图像的全空间随机搜索的过程变成基于各个子图像的子空间并行搜索和逐步淘汰的过程，实现了匹配区域

粗定位与匹配点精搜索的有效结合，从而大大缩短了最佳匹配点的搜索时间。实验结果表明，TESS搜索策

略带来了匹配速度的极大提高，且时间加速比随匹配源图像规模的增大而增大。

基于流形特征的视频情感分析与识别

李青1，蒋冬梅1，FAN Ping2,Ravyse Ilse2,Sahli Hichem2

2010, 32(12): 39-41. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 437 )   PDF (677KB) ( 569 )   　　

本文研究了基于Isomap的非线性降维方法，对由面部表情序列提取的面部动画参数特征进行降维，
分析了降维后的流形特征空间与认知心理学情感空间之间的关系。实验结果表明，Isomap降维后的情感流
形特征能够表现情感的强度变化，而且比PCA降维特征对情感强度的描述更加合理和平滑；情感识别实验
也表明，使用Isomap降维流形特征的识别率要高于原始情感特征和PCA降维特征，而且对各种情感的识别
结果更加均衡。

一种快速的车牌定位与提取算法

李宇成,王目树

2010, 32(12): 42-45. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 400 )   PDF (607KB) ( 916 )   　　

针对现有的车牌定位的各种局限性，本文提出了一种基于图像二维区域能量的车牌定位算法，给出
了该算法实用公式，并给出了基于图像能量的车牌提取算法以及车牌区域的验证方法。该方法充分利用了
车牌的纹理复杂、对比度鲜明、外型规则等特征构造能量图像，并对原有的能量算法进行了改进。其明显
的优点是可以避免直接对图像进行二值化时阈值难以确定的问题以及光照情况对颜色的影响。大量的实验
表明，该算法不仅简单、快速、准确率高，而且对车牌区域的噪声有很好的抑制作用。

一种抗碎云干扰的海上舰船目标检测方法

陈海亮,雷琳,周石琳

2010, 32(12): 46-49. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 476 )   PDF (738KB) ( 502 )   　　

针对恶劣成像条件下有碎云干扰的光学遥感图像中舰船目标的检测问题，结合干扰背景及目标自身
的特点，本文提出一种鲁棒的舰船目标检测算法。该算法首先用双参数局部CFAR直接提取ROI；再结合改
进的局部Radon变换及变换域峰值提取算法，提取舰船目标的外部信息——尾迹特征，完成对舰船的检测
。实测数据的实验表明，该方法能够可靠地检测出舰船目标，并有效地去除了碎云干扰所造成的虚警。

基于模糊贴近度的指纹匹配算法研究

朱贵良，宋瑞芳，樊学会

2010, 32(12): 50-52. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 447 )   PDF (507KB) ( 455 )   　　

针对已有的指纹匹配方法准确率低、算法复杂度高、易受指纹形变等噪声影响缺陷，本文提出了一
种基于模糊贴近度的新型指纹匹配算法。该算法以分叉点、转折点、指纹图像上两个点的连线所穿越的脊
线的数量等特征信息作为识别对象的特征指标，通过求出采样指纹与标准指纹的模糊贴近度，将其结果与
阈值V相比较，检测指纹的匹配程度。实验结果表明，该算法能够有效降低算法复杂度，提高指纹的匹配
准确率与效率，同时也可以有效避免因指纹旋转、平移形变或按压力度不均等因素产生的噪声对指纹匹配
精度的影响，可以满足实际应用的需求，为提高指纹识别的精确度提供了一种新方法。

灰度图像最大熵分割方法的改进

郑丽萍1 ,李光耀2,姜华1

2010, 32(12): 53-56. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 495 )   PDF (635KB) ( 860 )   　　

传统的最大熵分割方法只考虑了图像的灰度概率，忽略了对应的灰度值。为了充分利用灰度图像的
灰度信息和空间信息，改进了传统的二维灰度直方图，生成二维差值属性灰度直方图。另外，改进了灰度
均值和二维熵的计算方法。在计算熵时，以二维差值属性灰度直方图为基础，用空间信息值来代替灰度概
率，生成二维差值属性信息值熵。在实验中，对多张不同的灰度图像分别用改进的最大熵方法与传统的最
大熵分割方法进行分割，并对分割结果进行比较分析。实验结果表明，改进的最大熵分割方法能有效地分
割灰度图像及噪声图像，有很强的抗噪声能力，并能产生清晰的分割结果。

基于形状分割的手写汉字笔划提取方法

袁媛,刘文才

2010, 32(12): 57-60. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 387 )   PDF (587KB) ( 518 )   　　

笔迹鉴别的目的是区分不同的书写者，而笔划提取是笔迹鉴别的基础。本文提出了一种用于笔迹鉴
别的手写汉字笔划提取算法，该算法定义了凹凸点与四种基本笔划相交类型的对应关系，通过字符图像轮
廓上的凹凸点检测来确定笔划相交区域和相交类型；接着，在各个相交区域上，根据其笔划相交类型进行
形状分割；最后，用对笔划轮廓两侧对应点进行跟踪的方法来进行细化。我们将该算法与基于细化和基于
段化的笔划提取算法进行比较，实验结果表明，该提取算法具有比较高的准确率和有效性，因此本文提出
的基于形状分割的手写汉字笔划提取方法具有较高的可操作性和实用价值。

料流轨迹图像中特征半径的分析和提取

李莹1,刘万军1,曲海成2

2010, 32(12): 61-64. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 333 )   PDF (1185KB) ( 294 )   　　

本文针对目前高炉布料轨迹测量分析的困难，引入模式识别技术，提出激光栅格物理标定方法，对
料流轨迹图像的边缘算法进行对比分析，分析不同算法的图像处理结果，采用非固定探测的方法获得边缘
算法的阈值。并根据不同激光波长的料流轨迹成像效果，对图像的特征半径的动态分析，对图像的不同特
征点采用不同长度的特征半径分析，得到料流轨迹落点分布和料流宽度信息，重建料流轨迹极坐标分布图
，为料流轨迹图像的信息获取提供更精确的数据，实现高炉操作的闭环控制自动化和工业信息化的精确要
求。

基于局部曲面拟合的散乱点云简化方法

张连伟，李焱，刘肖琳，史美萍，贺汉根

2010, 32(12): 65-68. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 478 )   PDF (826KB) ( 551 )   　　

随着数据获取手段的进步，散乱点云数据在三维重建中获得越来越广泛的应用，然而庞大的数据量
往往影响重建的效率。现有简化算法中采用的曲率计算方法精度不高，导致模型特征模糊。本文在分析曲
面特征的基础上给出了一种曲面特征的定量描述方法。该方法采用局部曲面拟合得到曲面在一点处的近似
曲面，然后用法曲率在360度范围内的平均值代替平均曲率来描述曲面在一点处的特征。简化时采用KD
树剖分点云数据，根据子节点所包含的采样点数、空间区域大小和曲面特征大小控制简化过程。实验结果
表明，该方法能够更好地保持曲面的几何特征，从而证明了算法的有效性。

基于三角网格模型简化的研究

闫涛1，姜晓峰2，王昱1

2010, 32(12): 69-72. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 392 )   PDF (947KB) ( 647 )   　　

三角网格模型需要大量的信息来记录点、边和面之间的连接关系，对于复杂模型更需要大量的存储空间，且在网络上传输的速度比较慢。三角网格模型的简化对于其存储、处理、传输以及实时绘制有着重要的意义。本文在针对国内外关于这一领域相关技术研究的基础上，设计出了一种基于三角形删除的简化算法。该算法首先计算三角形的权重，根据设定的权重差值比例来删除相应的三角网格模型区域，然后再对删除后的区域实行三角网格的重建。最后，以两个实例进行探讨，以原始网格模型与简化后的网格模型进行对比，说明本文所设计的网格模型简化算法即有效地实现了三角网格模型的简化，又保持了三角网格模型原有的基本特征，且使简化的效率得到了提高，达到了令人满意的结果。

直方图不变矩在零水印中的应用

何冰,王菊霞

2010, 32(12): 73-75. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 518 )   PDF (560KB) ( 387 )   　　

本文提出了一种使用直方图不变矩抗几何攻击零水印算法。该方法首先对图像直方图进行分析,然后计算该图像的直方图不变矩，最后使用直方图不变矩来构建水印系统。水印提取过程简单,只需计算所得图像的几个直方图不变量。文中给出了实验结果,并与基于几何矩不变量的算法进行了比较。经过仿真实验证明，该方法对于旋转、缩放等攻击具有很好鲁棒性的同时，对于普通的滤波、JPEG压缩攻击也具有很好的鲁棒性，且具有极低误检率。

蚁群智能模型检测算法

吴湘宁1,胡成玉1,汪渊2

2010, 32(12): 76-79. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 488 )   PDF (598KB) ( 341 )   　　

蚁群智能模型检测算法借鉴了自然界中蚂蚁通过信息素相互沟通，从而完成觅食、搬迁等需要协作的复杂社会活动的原理。通过分布在程序控制流图和状态图上的代理，即人工蚂蚁的回溯来跟踪寻找模型中的正确路径和错误路径，人工蚂蚁在控制流图上移动时，分别在正确路径和错误路径上释放两种不同的信息素，通过对两种信息素的对比，可自动定位出程序中引发特定错误的原因。由于人工蚂蚁之间相互独立、并行工作，因此算法能够同时、并行地跟踪多条正确路径和错误路径，也可同时定位出引发多个不同错误的不同原因。通过对中小规模程序的检测，结果表明，该算法是有效的。

有时间窗物流配送路径优化问题的并购算法

刘芳华,赵建民,徐慧英，朱信忠

2010, 32(12): 80-84. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 632 )   PDF (524KB) ( 432 )   　　

通过对市场资源优化配置中市场行为的了解，提取企业在市场中的行为之一并购行为的精华，并简化并购行为的模型。根据计算得到的企业劣信度，企业间进行合理的并购和重组，也是对市场资源再整合，使资源得到充分的优化配置，进而提高整体企业的市场竞争力。在建立有时间窗物流配送路径优化问题的数学模型基础上，构造有时间窗物流配送路径优化的并购算法模型。该模型包含编码、初始化、预处理、劣信度评估、并购操作、重组操作以及选择操作等七个模块。在Solomon数据集上进行多次实验，并与目前实验已经获得的最优解做比较，获取有时间窗物流配送路径优化问题的最优解或近似最优解。

一种混沌粒子群算法

孙湘1,周大为2,张希望2

2010, 32(12): 85-88. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 504 )   PDF (1320KB) ( 441 )   　　

针对传统的粒子群算法易陷入局部最小，且算法后期的粒子速度下降过快而失去搜索能力等缺陷，本文提出了一种基于混沌思想的新型粒子群算法。该算法通过生成混沌序列的方式产生惯性权重取代传统惯性权重线性递减的方案，使粒子速度呈现多样性的特点，从而提高算法的全局搜索能力；根据算法中粒子群体的平均粒子速度调节惯性权重，防止粒子速度过早降低而造成的搜索能力下降的问题；最后通过引入粒子群算法系统模型稳定时惯性权重和加速系数之间的约束关系，增强了粒子群算法的局部搜索能力。对比仿真实验表明，本文所提改进的混沌粒子群算法较传统粒子群算法具有更好的搜索性能。

稀疏线性方程组求解中的预处理技术综述

骆志刚,仲妍,吴枫

2010, 32(12): 89-93. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 499 )   PDF (417KB) ( 920 )   　　

稀疏线性方程组的高效求解是数值计算方向的研究热点之一，其中包括预处理技术的研究。本文从技术分类的角度，总结了稀疏线性方程组求解中的预处理技术。首先，介绍了填充元缩减策略，旨在减少求解过程中存储量的同时，仍能保持矩阵的稀疏结构；其次，介绍了不同结构系数矩阵的多种匹配技术，旨在获得矩阵的对角优势性；最后，介绍了具有天然并行性的因子分解近似逆预条件子构造方法和不完全分解预条件中的并行求解技术等。

一种面向普适计算的自适应软件平台的设计与实现

史殿习，丁博，李骁，王怀民

2010, 32(12): 94-97. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 478 )   PDF (666KB) ( 529 )   　　

普适计算的适应性特征带来了有必要在软件平台层面解决的一系列共性问题，包括如何定义所支持的自适应软件体系结构、如何为上层应用的自适应提供必要的公共服务、如何使平台自身可以适应多维资源受限环境等。针对这些挑战，提出了对普适计算设备/资源进行适应性抽象的自主单元的概念，在此基础上给出了面向普适计算的自适应软件平台UbiStar的系统架构及其核心机制的设计与实现，并对UbiStar平台对适应性软件所提供的支持机制进行了概括，最后对相关工作进行了分析与比较。

扩展双精度浮点并行计算：MPI方法

杨灿群，杨学军，易会战

2010, 32(12): 98-101. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 421 )   PDF (362KB) ( 433 )   　　

双精度浮点并行计算将不能满足高性能计算领域对计算精度的要求，但是目前还没有高性能的超双精度并行计算的解决方法。基于并行编程语言MPI，本文提出了扩展双精度浮点的并行计算实现方法，并且使用精度敏感的圆周率计算BBP算法验证了该方法的正确性和性能。

气象应用基准测试程序MM5 Benchmark并行性能优化

朱小谦，张卫民，宋君强，胡庆丰

2010, 32(12): 102-106. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 406 )   PDF (607KB) ( 428 )   　　

由美国国家大气研究中心（NCAR）和宾夕法尼亚大学（PSU）共同开发的MM5模式是目前气象领域广泛采用的中尺度模式之一。由于MM5模式的广泛应用和计算特点，MM5 Benchmark成为了高性能计算领域衡量计算机实用性能的典型应用之一。本文介绍了MM5模式的并行计算方法，针对目前流行的Intel Itanium2 CPU特点，在性能分析的基础上，从编译选项、代码优化、区域分解、处理机拓扑结构等方面对程序性能进行优化。实际测试结果表明，在某国产巨型机上优化后的持续计算性能最大提高20％左右。

可信服务组合研究综述

朱锐, 王怀民

2010, 32(12): 107-112. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 540 )   PDF (485KB) ( 537 )   　　

系统形态正从面向封闭的、熟识用户群体和相对静态的形式向开放的、公共可访问的和动态协作的服务模式转变。实体之间存在很大的陌生性，信任保障机制作用就显得举足轻重。本文从可信的角度对服务组合面临的挑战进行了综述，阐述了可信服务组合的基本概念、核心技术，比较全面地概括、分析了可信服务选取、组合服务运行保障机制、安全交互机制以及服务组合可信度评估等几个方面的研究内容，并对这些技术进行了总结和比较。此外，还指出了目前研究存在的不足以及未来的发展趋势。

一种基于共享前缀的两级索引结构

喻波，赵国鸿，陈曙晖

2010, 32(12): 113-116. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 434 )   PDF (461KB) ( 443 )   　　

大多数倒排索引结构并未提出词汇表的组织形式，传统的基于Hash算法组织的词汇表存在大量碰撞的索引词。本文提出一种基于共享前缀的两级索引结构，通过对汉字、英文、数字进行统一编码，把具有相同首字的索引词映射到一级索引的相同位置；二级索引使用共享前缀树的结构组织索引词，既能通过二分查找快速定位索引文件存储块的位置，又能通过共享前缀的方式减少对相同字的存储，有效地减少了索引文件占用的存储空间。实验结果表明，该结构索引文件与源文档大小的压缩比达到0.59，与顺序索引和Hash索引相比，具有较高的时空效率。

语义信息集成中格式异构解决方案

周建芳1,丰洪才1，李禹生2

2010, 32(12): 117-121. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 421 )   PDF (510KB) ( 380 )   　　

基于本体的语义信息集成能够解决分布环境下异构数据源之间的模式异构，而对于广泛存在的上下文异构却无法解决。由于上下文异构是暗含的语义，无法为信息系统俘获和理解，要解决上下文异构，必须将上下文语义进行形式化描述。本文首先提出了一种将暗含的上下文语义进行形式化描述的方法，然后在此基础上提出了一种基于元数据格式表示的上下文转换方法来解决上下文异构中的格式异构。该方法避免了已有转换方法需要反复定义大量映射的缺点，提高了上下文转换的灵活性、适应性和扩展性。

语义网检索中的知识收集方法研究

王志华1，王鹏2

2010, 32(12): 122-124. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 440 )   PDF (480KB) ( 387 )   　　

针对传统信息检索中存在的缺乏知识表示和语义处理能力低的问题，本文提出了一个基于本体的语义网信息检索框架，该框架包括知识收集与储存层、人机交互层和知识处理层。对该框架中知识收集与储存层的关键技术及实现进行了介绍，主要包括领域本体库的构建、元数据的提取和知识库的构建等功能。其中，对元数据提取中的核心技术的实现，如领域本体库的解析、文件预处理、语义标注、知识抽取等作了详尽的介绍。

一种基于聚类和协同过滤的组合推荐算法

刘旭东1,葛俊杰1,陈德人2

2010, 32(12): 125-127. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 522 )   PDF (466KB) ( 660 )   　　

协同过滤技术是目前电子商务推荐系统中最为主要的技术之一，但随着系统规模的日益扩大，它面临着算法可扩展性和数据稀疏性两大挑战。针对上述问题，本文提出了一种基于聚类和协同过滤的组合推荐算法。首先利用聚类对项目进行分类，在用户感兴趣的类里进行推荐计算，有效地解决了算法的可扩展性问题；接着在每一类中使用基于项目的协同过滤对未评价的项目进行预测，把较好的预测值填充到原用户项集合中，有效地缓解了数据稀疏性问题；最后根据协同过滤推荐在相似项目的范围内计算邻居用户，给出最终的预测评分并产生推荐。实验结果表明，本算法有效地解决了上述两个问题，提高了推荐系统的推荐质量。

基于多级相关图的大规模词典完美哈希函数构造算法

李海涛

2010, 32(12): 128-133. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 384 )   PDF (654KB) ( 472 )   　　

在哈希函数中，如果两个不同的单词被映射到同一个槽，那么我们称为冲突。当哈希函数存在冲突时，将降低词典查找的速度。由于完美哈希函数完全避免了冲突，因此在许多对查找性能要求较高的应用中广泛使用。本文就此提出了一种基于多级相关图的大规模词典完美哈希函数的构造算法。词典单词的每个字符（首字母除外）都用两个平滑函数平滑为两个字符，构建平滑后词典对应的多级相关图，多级相关图的结点度都比较小，而且分布比较均匀，因此更容易生成完美哈希函数。实验表明：基于多级相关图的哈希函数构造算法适用于大规模词典，填充因子接近1，同时工作空间比已有算法都要小。

蚂蚁算法在带时间窗车辆路径问题中的应用及参数分析

张潇，王江晴

2010, 32(12): 134-136. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 465 )   PDF (346KB) ( 501 )   　　

带时间窗的车辆路径问题是一个典型的NPHard问题，本文将蚂蚁算法应用于带时间窗车辆路径问题，构造了该问题的表达方法，建立了相应的算法模型，对算法参数进行了分析并提出了相应的参数改进方案。仿真实验表明，改进后的算法可以快速、有效地求解带时间窗车辆路径问题，具有较好的可行性和适用性。

基于记忆双导向变异的故障检测器生成方法

姜大伟,韩莉,常志英

2010, 32(12): 137-139. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 413 )   PDF (524KB) ( 338 )   　　

人工免疫算法中的阴性选择算法已经成功应用于故障诊断领域。为了生成更加优良的故障检测器，提高算法性能，本文在传统阴性选择算法的基础上，提出了一种基于免疫记忆双导向变异的故障检测器生成方法。该算法定义了一个免疫记忆集合，把与自体集合或成熟检测器集合发生匹配的检测器放入到免疫记忆集合里，并对这一检测器进行双导向变异，以减少资源浪费和冗余的发生。本文数据采用实属编码形式。仿真结果表明，新算法在故障检测性能方面优于传统算法，具有较高的故障诊断率，算法平均运行时间明显缩短。本文为故障诊断方法的研究拓宽了道路，具有一定的理论和现实意义。

面向资源优化的周期分配方法和总线访问配置研究

谢勇1，李仁发1，李哲涛1,2

2010, 32(12): 140-144. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 460 )   PDF (649KB) ( 289 )   　　

汽车系统的功能多样性和智能化发展，引起车内ECU数量的大量增加，给汽车成本的降低带来巨大压力。ECU节点通过TTP总线构成了以周期性任务触发、基于TDMA技术的消息分发、基于抢占的FPS调度等为特点的分布式体系结构。实时性和资源利用率是上述体系结构需要考虑的两个关键问题，特别是随着汽车系统复杂性的快速增长，对解决上述问题提出了严峻的挑战。本文提出一种利用GP进行周期分配和总线访问配置，并结合FPS进行实时调度分析，在保证系统时限的前提下，最小化系统资源利用率的方法，以减缓ECU数量的增加，降低系统成本。在具备工业实用价值的任务集基础之上进行的仿真实验结果表明了该方法的有效性和可扩展性。

一种动态可重构系统的实时任务调度算法

焦铬1,2，李仁发2，彭日光2，李浪1,2，邹祎1

2010, 32(12): 145-148. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 399 )   PDF (528KB) ( 386 )   　　

硬件任务的软实时调度是影响动态可重构系统性能的关键因素之一。本文提出了一种基于顶点链表的硬件任务间最小空间调度算法MSSA，该算法将硬件任务按照长、宽及调度时间构成一个三维资源模型，以到达任务与已放置任务在三维空间的邻接度来构建代价函数，获取具有最大代价函数值的放置位置和启动时间，可使任务安排得更紧凑，减小对系统资源的浪费，提高并行度。仿真实验表明，与MSG4V和Stuffing算法相比，本文算法具有更高的芯片利用率和任务接受率。

RS-485总线短路故障检测技术研究

崔三俊1,2，李成海1，徐欣中1

2010, 32(12): 149-151. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 509 )   PDF (451KB) ( 339 )   　　

短路故障是RS485总线的常见故障，其危害较大，容易造成总线控制芯片的损坏。RS485总线一般通过发送检测报文来判定总线工作是否正常，该类方法的反应较慢，且不能避免接口电路的损坏。本文提出了一种基于电流检测的短路故障检测方法，它可以实时在线检测分支电路的短路故障，从而可立即屏蔽掉故障分支点，避免短路故障进一步损坏系统。

面向Web Service的动态负载均衡设计与实现

周顺

2010, 32(12): 152-156. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 444 )   PDF (480KB) ( 465 )   　　

负载均衡是分布式系统的资源管理模块，它的主要功能是合理和透明地在服务器之间分配系统负载，以达到系统的综合性能最优。基于中间件的负载均衡技术在整合异构系统、透明访问和扩展能力等方面具有优势。在中间模块上可以灵活实现多种负载均衡算法，来调整和满足不同应用的负载均衡需求，提高系统的扩展性、配置性、健壮性。本文参考分布式系统中的模型，构建了基于Web Service的负载均衡器，实现了动态负载均衡调度策略。为了准确地描述系统的负载，选择CPU利用率、内存利用率、系统响应时间、输入输出流量和进程数作为衡量系统负载的参量；为了避免因监测服务器而加大均衡器的压力，策略中将负载信息采集程序运行在机群内的各服务结点上，当相邻采集周期的负载差值超过标准值后调用均衡器上的Web服务，报告自身的负载状况，使均衡器根据负载信息进行同步操作，更换服务序列。最后通过仿真实验证明本策略在异构Web平台中具有可行性。

AODV算法在视频监控系统中的应用与研究

蒋文芳1，赵利1，莫金旺2

2010, 32(12): 157-160. doi: 10.3969/j.issn.1007130X.2010.

摘要 ( 595 )   PDF (613KB) ( 687 )   　　

在Linux嵌入式系统平台上，针对按需距离矢量路由协议AODV算法在无线Mesh网络的应用开发问题，本文采用比较有代表性的UU实现方法，提出了基于Netfilter功能框架的AODV协议在Linux平台上实现的具体方法,在真实的无线网络环境下实现AODV路由协议。将AODV应用开发到嵌入式Linux平台上，并在此基础上用IEEE802.11b标准的网卡组建一个无线自组织网络，从而扩展IEEE802.11的组网方式。最后，在Linux 操作系统上实现了AODV路由协议，并通过视频监控系统验证了AODV协议实现的功能与相应的协议标准中所定义的基本功能的一致性。