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

当期目录

2008年 第45卷 第3期    出版日期:2008-03-15
论文
无线传感器网络中间件研究进展
李仁发 魏叶华 付 彬 陈洪龙
2008, 45(3):  383-391. 
摘要 ( 474 )   HTML ( 0)   PDF (419KB) ( 658 )  
相关文章 | 计量指标
无线传感器网络作为一种新兴的技术,受到了学术界和工业界的广泛关注.然而随着传感器网络及其应用的发展,系统的复杂性也随之增加,与传统网络相比无限传感器网络又具有其独特的特征,使得无线传感器网络的程序开发变得更加困难.中间件提供了一个编程抽象,方便了应用程序的开发,缩减了应用程序和底层设备的间隙.针对无线传感器网络的特点,分析了无线传感器网络中间件设计面临的问题,对有关设计方法进行了分类评述,并对几种典型中间件进行了比较,最后从通信范式、QoS支持和安全等方面提出了一些改进思路.
多级能量异构传感器网络的负载均衡成簇算法
王向辉 张国印 谢晓芹
2008, 45(3):  392-399. 
摘要 ( 427 )   HTML ( 0)   PDF (490KB) ( 406 )  
相关文章 | 计量指标
在多级能量异构无线传感器网络中,节点的初始能量在一定的范围内随机分布,负载均衡和降低能耗是能量异构网络成簇算法的一个重要挑战.现有的分布式成簇算法主要是针对能量同构或二级异构网络设计的,无法实现节点能量多级异构时的负载均衡,因此提出了适用于多级能量异构传感网络的负载均衡成簇算法LBCA(load balance clustering algorithm). LBCA根据传感器网络的能量分布情况选择簇头节点和实现负载均衡,可以有效地延长网络的稳定周期.簇头选择过程中,当探测区域能量分布均衡时,拥有较低平均通信能耗的节点将优先成为簇头节点,有利于降低探测区域内的总通信能耗;当探测区域能量分布不均衡时,具有较高剩余能量的节点将优先成为簇头节点,有利于实现探测区域内的负载均衡.将LBCA与主要的分布式成簇方案进行了比较,模拟实验结果显示,在多级能量异构传感器网络中,LBCA可以更好地实现负载均衡,极大地提高网络的稳定周期.
网络编码的研究进展
杨 林, 郑 刚, 胡晓惠,
2008, 45(3):  400-407. 
摘要 ( 478 )   HTML ( 0)   PDF (379KB) ( 1895 )  
相关文章 | 计量指标
网络编码允许网络节点在传统数据转发的基础上参与数据处理,已成为提高网络吞吐量、鲁棒性和安全性的有效方法.在介绍网络编码基本原理的基础上,比较了集中式和分布式网络编码构造方法的优缺点,并对实用网络编码设计中涉及的同步、纠错、编解码速度等问题进行了评述;进而,对网络编码在无线网络、P2P系统、分布式文件存储和网络安全等领域的最新应用进行了总结;最后对网络编码的理论和应用研究的发展趋势进行了分析与展望.设计简单高效的实现机制,并与其他领域的技术如信道编码与调制、路由算法、队列调度以及流媒体技术等的结合,将是网络编码发展的一个重要趋势.
一种基于概率统计方法的P2P系统信任评价模型
吴 鹏 吴国新 方 群
2008, 45(3):  408-416. 
摘要 ( 322 )   HTML ( 0)   PDF (446KB) ( 495 )  
相关文章 | 计量指标
现有的P2P系统信任评价模型正面临着两种恶意节点的攻击行为——策略性欺骗和不诚实推荐,严重影响了模型计算节点信任评价的准确性和有效性.针对现有模型存在的不足,提出了一种基于概率统计方法的信任评价模型.该模型借鉴人类社会中主观信任关系的概念,依据直接经验和反馈信息,利用概率统计方法分别计算节点的直接信任和推荐信任,并通过区分直接经验的重要程度,区分反馈信息及其推荐者的可信度,提高信任评价模型的有效性.仿真实验分析说明,与已有的信任评价模型相比,该模型能够更有效地抑制策略性欺骗和不诚实推荐的威胁,特别是复杂的协同作弊方式对系统的攻击.
一种基于概率统计方法的P2P系统信任评价模型
吴 鹏 吴国新 方 群
2008, 45(3):  408-416. 
摘要 ( 301 )   HTML ( 0)   PDF (446KB) ( 411 )  
相关文章 | 计量指标
现有的P2P系统信任评价模型正面临着两种恶意节点的攻击行为——策略性欺骗和不诚实推荐,严重影响了模型计算节点信任评价的准确性和有效性.针对现有模型存在的不足,提出了一种基于概率统计方法的信任评价模型.该模型借鉴人类社会中主观信任关系的概念,依据直接经验和反馈信息,利用概率统计方法分别计算节点的直接信任和推荐信任,并通过区分直接经验的重要程度,区分反馈信息及其推荐者的可信度,提高信任评价模型的有效性.仿真实验分析说明,与已有的信任评价模型相比,该模型能够更有效地抑制策略性欺骗和不诚实推荐的威胁,特别是复杂的协同作弊方式对系统的攻击.
面向多核片上Trace数据流合成的队列调度算法设计及实现
扈 啸 陈书明
2008, 45(3):  417-427. 
摘要 ( 526 )   HTML ( 0)   PDF (673KB) ( 405 )  
相关文章 | 计量指标
多核片上Trace数据流包含各处理器核中用于调试的实时运行信息,经由专用数据通路和输出管脚传输.用于多Trace数据流合成的队列调度算法是影响片上Trace系统性能的关键技术之一.针对Trace数据流合成的特点,提出一种基于服务请求门限和最小服务粒度双重约束的懒惰队列调度算法.该算法通过设置各队列的服务请求门限控制队长分布,通过设置最小服务粒度和懒惰服务切换减少队列切换开销.提出基于溢出的缓冲利用率指标,用于评价调度算法设置队列优先级的实际效果.实验结果表明,能够按设置的队列优先级充分利用缓冲容量,有效降低各缓冲队列的溢出.用Verilog硬件设计语言实现了该算法并进行逻辑综合.同某主流算法比较,面积增加2015μm\+2,平均溢出率降低30%.
具有多出入口区域的节点移动和分布研究
公维宾 常义林 沈 中 张 颖
2008, 45(3):  428-435. 
摘要 ( 461 )   HTML ( 0)   PDF (459KB) ( 379 )  
相关文章 | 计量指标
在Ad Hoc网络的仿真研究中,节点移动模型的选择会严重影响到网络的拓扑结构和通信协议的性能.然而,现有移动模型大多是为理想环境设计的,不能适用于真实环境.在理想移动模型RWP(Random Waypoint)的基础上,提出了具有多出入口区域的RWP节点移动模型(RWP with entrances, RWPWE).在该模型中,区域出入口是节点进出区域的必经之地,节点在区域内的移动符合RWP节点移动模型,通过引入域内停留概率来完成节点在区域内外移动的转移,并从节点移动速度、移动时间、移动路程和空间分布概率等几个方面研究了区域出入口的影响.理论分析和实验仿真的结果表明,由于出入口的存在,与RWP模型相比节点的移动更加复杂,节点的空间分布也显著不同,这些差别将会影响到网络的拓扑性能和对网络协议的评价.
网络流量长相关特性的滑窗时变估计算法
魏进武, , 张 进, 邬江兴,
2008, 45(3):  436-442. 
摘要 ( 442 )   HTML ( 0)   PDF (473KB) ( 376 )  
相关文章 | 计量指标
网络流量在动态演进过程中呈现出长相关(LRD)特性,定量描述LRD特性是网络行为研究的重要问题之一.由于传统LRD估计算法采用全域求和平均,造成序列中突发信息损失,致使传统算法均不能在复杂条件下有效估计LRD. 在引入时变Hurst指数函数的概念后,提出了时域滑窗时变Hurst(SWTV-H)估计算法.SWTV-H算法在某一分辨率水平上给出局域内Hurst指数的估计,并通过局域时移实现流量序列全域内LRD趋势的动态估计.分别用仿真以及真实网络流量数据对其有效性进行了验证,与传统算法的估计结果相比,SWTV-H算法能更准确估计LRD特性,且具有更好的鲁棒性.
MIPv6切换性能测量和瓶颈分析
陈 吉, 郑红霞, 谢高岗,
2008, 45(3):  443-453. 
摘要 ( 398 )   HTML ( 1)   PDF (671KB) ( 323 )  
相关文章 | 计量指标
MIPv6(mobile IPv6)是IETF(Internet Engineering Task Force)工作组提出的IP层移动解决方案.切换是影响MIPv6性能的关键因素.从网络层、传输层和应用层3个层次测量分析MIPv6切换性能,确定协议层次性能相互影响与切换性能瓶颈.根据网络层切换过程,改进其测量移动检测时延的方法,测量MIPv6各个阶段的切换时延并提出减少各阶段时延的建议,分析发现切换性能瓶颈.进一步完成传输层性能测量,分析移动切换对TCP滑动窗口的影响,发现TCP的特性将影响切换过程中上层应用的性能;以FTP应用为例,测量并分析了移动切换对上层应用的影响.相关结论对设计高效的移动切换协议提供了研究基础.
协同演化算法研究进展
董红斌, 黄厚宽, 印桂生, 何 军,
2008, 45(3):  454-463. 
摘要 ( 645 )   HTML ( 0)   PDF (402KB) ( 1217 )  
相关文章 | 计量指标
协同演化算法(coevolutionary algorithms, CEA)是当前国际上计算智能研究的一个热点,它运用生物协同演化的思想,是针对演化算法的不足而兴起的,通过构造两个或多个种群,建立它们之间的竞争或合作关系,多个种群通过相互作用来提高各自性能,适应复杂系统的动态演化环境,以达到种群优化的目的.介绍了协同演化算法的研究状况以及目前的研究进展,概述了它的基本算法、主要特点、理论与技术,同时介绍了一些主要的应用领域,指出了协同演化算法的研究方向.
基于群体多样性反馈控制的自组织微粒群算法
介 婧, 曾建潮, 韩崇昭,
2008, 45(3):  464-471. 
摘要 ( 438 )   HTML ( 1)   PDF (460KB) ( 542 )  
相关文章 | 计量指标
微粒群算法是一种新型的群智能算法,已被广泛用于各种复杂优化问题的求解,但算法依然面临着过早收敛问题.为克服算法的早熟问题,提出了自组织微粒群算法.将微粒群体视为自组织系统,引入负反馈机制.群体多样性是影响微粒群算法全局优化性能的关键因素,把群体多样性作为个体微粒可感知的群体动态信息,用于动态调整惯性权重或加速度系数,通过不同的特性参数实现微粒的集聚或分散,使群体维持适当的多样性水平以利于全局搜索.用于复杂函数优化问题的求解,并与其他典型改进算法进行了性能比较.仿真结果表明,基于多样性控制的自组织微粒群算法可以有效避免早熟问题,提高微粒群算法求解复杂函数的全局优化性能.
选取最大可能预测错误样例的主动学习算法
龙 军 殷建平 祝 恩 蔡志平
2008, 45(3):  472-478. 
摘要 ( 603 )   HTML ( 1)   PDF (357KB) ( 569 )  
相关文章 | 计量指标
通过选取并提交专家标注最有信息量的样例,主动学习算法中可以有效地减轻标注大量未标注样例的负担.采样是主动学习算法中一个影响性能的关键因素.当前主流的采样算法往往考虑选取的样例尽可能平分版本空间.但这一方法假定版本空间中的每一假设都具有相同的概率成为目标函数,而这在真实世界问题中不可能满足.分析了平分版本策略的局限性.进而提出一种旨在尽可能最大限度减小版本空间的启发式采样算法MPWPS(the most possibly wrong-predicted sampling),该算法每次采样时选取当前分类器最有可能预测错误的样例,从而淘汰版本空间中多于半数的假设.这种方法使分类器在达到相同的分类正确率时,采样次数比当前主流的针对平分版本空间的主动学习算法采样次数更少.实验表明,在大多数数据集上,当达到相同的目标正确率时,MPWPS方法能够比传统的采样算法采样次数更少.
基于GPGP协同机制的多Agent车间调度方法研究
马 鑫 梁艳春
2008, 45(3):  479-486. 
摘要 ( 250 )   HTML ( 0)   PDF (556KB) ( 484 )  
相关文章 | 计量指标
车间调度作为车间制造系统的重要组成部分,影响着整个车间制造系统的敏捷性和智能性.但是,由于资源和工艺约束的并存,使得车间调度成为一类NP-hard问题.基于静态的智能算法与动态的多Agent思想,提出了一种结合通用部分全局规划(generalized partial global planning,GPGP)机制与多种智能算法的多Agent车间调度模型,设计了从“初始宏观调度”到“微观再调度”的大规模复杂问题的调度步骤,并构建了一个柔性强且Agent可自我动态调度的仿真系统.同时,从理论上总结了GPGP基本协同机制的策略,实现了二级多目标优化调度.最后使用DECAF仿真Agent 软件模拟了车间调度的GPGP协同机制,并与CNP,NONE机制进行了比较.结果表明,所提出的模型不仅提高了调度的效率,而且降低了资源的损耗.
多Agent动态影响图的近似计算方法
姚宏亮 王 浩 汪荣贵 李俊照
2008, 45(3):  487-495. 
摘要 ( 359 )   HTML ( 0)   PDF (578KB) ( 459 )  
相关文章 | 计量指标
由于复杂系统具有高维性和不确定性常难以表示处理,因而知识表示和计算方法是复杂系统研究中的公开难题.当前,多Agent影响图不能建模动态环境和多Agent,马尔可夫决策过程难以表示Agents之间结构关系的问题,因而提出一种用局部概率因式表示动态环境中多Agent之间关系的新决策模型——多Agent动态影响图(MADIDs).针对MADIDs模型的联合概率分布和联合效用函数在计算上的高维问题,研究该模型的近似计算方法.给出MADIDs概率结构部分的一种分层分解的分布近似方法,并通过对该近似方法的误差和复杂性的分析,给出一个可对近似分布的精度和复杂性进行均衡的函数δ(k);给出一种BP神经网络通过局部效用的学习来近似计算MADIDs的联合效用.在模型实例上的实验结果显示了MADIDs模型近似计算方法的有效性.
半监督鲁棒联机聚类算法
金 骏 张道强
2008, 45(3):  496-502. 
摘要 ( 371 )   HTML ( 0)   PDF (424KB) ( 472 )  
相关文章 | 计量指标
将监督信息引入到聚类算法中去,在先前提出的鲁棒联机聚类算法(ROC)的基础上,通过引入以样本类标号形式给出的监督信息,提出了一种半监督的鲁棒联机聚类算法(Semi-ROC).在算法的聚类精度和鲁棒性能上,算法Semi-ROC比ROC和AddC有着更好的性能,在人工数据集和UCI标准数据集上的实验结果表明,Semi-ROC能有效地利用少量的监督信息来提高算法的聚类性能,得到较优的结果.另外,在添加噪声的情况下,算法Semi-ROC比原始的联机聚类算法AddC和ROC都更加鲁棒.
一种基于物理的实时细节保持变形算法
车英慧 梁晓辉 赵沁平
2008, 45(3):  503-509. 
摘要 ( 431 )   HTML ( 0)   PDF (491KB) ( 377 )  
相关文章 | 计量指标
实时变形是计算机图形学研究的热点问题之一,复杂物体的实时变形至今仍未得到很好的解决.从物理变形方法和多分辨率网格编辑技术的优点出发,提出了一种适合于复杂弹性物体的实时变形算法.在预处理阶段,将原始精细网格模型进行简化以建立其基网格表示,基于基网格对模型的局部细节特征进行编码;在实时绘制阶段,在基网格上进行物理变形操作,并通过变形后的基网格和细节编码重构出变形后的精细网格.以上过程充分利用图形硬件的并行处理能力,利用像素处理器进行大部分计算操作.实验结果表明,该算法在变形过程中较好地保持了物体的局部特征,适合于表面细节复杂物体的实时变形应用.
基于软硬件分区的AVS高清视频解码器结构
贾惠柱, 解晓东, 高 文,
2008, 45(3):  510-518. 
摘要 ( 431 )   HTML ( 0)   PDF (513KB) ( 525 )  
相关文章 | 计量指标
硬件的强大处理能力及软件的灵活性和可编程性,使得视频解码芯片的结构从硬件转向软硬件分区结构.作为新兴的标准,AVS视频标准对解码器的软硬件分区结构提出新的挑战.从AVS视频标准算法和实现复杂度入手,提出一种AVS高清视频解码器软硬件分区结构,实现满足基准档次6.0级别的AVS高清视频码流的实时解码,支持灵活的音视频同步、错误恢复、缓冲区管理和系统控制机制.已经在AVS101芯片上实现,硬件采用7阶宏块级同步流水,软件任务在RISC处理器上实现,可以在148.5MHz工作频率下对NTSC,PAL,720p(60f/s),直至1080i(60field/s)节目的实时解码显示.
碰撞响应中方向穿透深度算法的研究
刘 莉, 王兆其, 夏时洪, 李淳NFEED,
2008, 45(3):  519-526. 
摘要 ( 669 )   HTML ( 0)   PDF (549KB) ( 423 )  
相关文章 | 计量指标
方向穿透深度是碰撞响应的基础,在增强虚拟环境的逼真性和真实感方面起到了重要的作用.现有的方向穿透深度算法,很难同时兼顾计算速度和计算精度,实用性受到很大限制.提出一种新的方向穿透深度计算方法,无须对凹多面体进行凸分解,就能精确地计算任意多面体间的方向穿透深度.在此基础上,提出一种基于体分解的包围体层次——ISBVH,极大地提高了算法的效率.
运动串:一种用于行为分割的运动捕获数据表示方法
杨跃东 王莉莉 郝爱民
2008, 45(3):  527-534. 
摘要 ( 485 )   HTML ( 0)   PDF (490KB) ( 480 )  
相关文章 | 计量指标
运动数据的行为分割是运动捕获过程中非常重要的一环.针对现有分割方法的不足,提出了一种可用于行为分割的运动数据表示方法,并基于该表示实现了数据的行为分割.运动数据经过谱聚类(spectral clustering)、时序恢复和最大值滤波法(max filtering)后生成一个字符串,该字符串称为运动串,然后采用后缀树(suffix tree)分析运动串,提取出所有静态子串和周期子串,对这些子串进行行为标注,从而实现运动数据的行为分割.实验表明,基于运动串的分割具有较好的鲁棒性和分割效果.
基于错误驱动算法组合分类器及其在问题分类中的应用
李 鑫 黄萱菁 吴立德
2008, 45(3):  535-541. 
摘要 ( 400 )   HTML ( 0)   PDF (422KB) ( 482 )  
相关文章 | 计量指标
开放领域问答系统(QA)能够给用户提供相对简洁、准确的结果,越来越受到人们的关注.问题分类把问题分成若干语义类型,是QA系统的一个重要的模块,它的准确性直接影响到QA系统的性能.为提高分类器性能,在问题分类任务中使用了集成学习方法,并且实验比较了词汇、句法、同义词集等不同的分类特征及错误驱动、投票法、BP神经网络等分类器集成方法.通过采用基于错误驱动集成分类器,用规则方法TBL作为统计方法SVM的补充;利用来自Wordnet的同义词集和名词的上位概念及Minipar的依存关系等语言知识作为分类特征,在公开测试集中取得了更高的分类精度.
一种层次化的检索结果聚类方法
张 刚 刘 悦 郭嘉丰 程学旗
2008, 45(3):  542-547. 
摘要 ( 529 )   HTML ( 0)   PDF (357KB) ( 534 )  
相关文章 | 计量指标
检索结果聚类能够帮助用户快速地浏览搜索引擎返回的结果.传统的聚类方法由于不能生成有意义的类别标签因此是不适合的,为了改善检索结果层次化聚类的效果,采用了基于标签的聚类算法,提出了将DF、查询日志、查询词上下文特征融合的类别标签抽取算法,并以抽取的标签构造基础类别图,通过GBCA算法构建层次化聚类结果.实验证明了多特征融合模型的有效性;GBCA算法在类别标签抽取和F-Measure两个评价指标上都比STC和Snaket算法有很大的提高.
滑动窗口数据流上多极值查询资源共享策略研究
田 李 王 乐 李爱平 邹 鹏 贾 焰
2008, 45(3):  548-556. 
摘要 ( 297 )   HTML ( 1)   PDF (570KB) ( 350 )  
相关文章 | 计量指标
为了提高在同一数据流上同时计算多个连续极值查询(MAX或MIN)时的处理能力,对查询间资源共享技术进行了研究.提出了一种称为“关键点集”的裁剪策略,系统仅需保存少量数据即可满足所有查询的需要.发掘多个查询间的相似性和可共享的计算存储资源,提出了一个多极值查询处理算法MCEQP.采用链表结构实现的该算法,当一个新数据到达时最多需要O(M+K)时间即可更新全部K个查询的结果,其中M为关键点集包含数据的个数. MCEQP采用触发器驱动的方式,只在某些特定时刻才需要计算因数据失效引起的查询结果变化,更新K个查询结果所需时间为O(K).理论分析和实验证明,对于滑动窗口数据流上的多个极值查询,MCEQP算法在降低存储开销和提高性能方面均优于现有的通用方法.
安全高效的水印认证协议
许文丽, 于叶云, 王育民,
2008, 45(3):  557-562. 
摘要 ( 408 )   HTML ( 0)   PDF (348KB) ( 388 )  
相关文章 | 计量指标
基于完全零知识交互证明系统和位委托方案,提出了可证明的安全水印认证协议.现有文献大都使用基于Cox的扩频数字水印方案或对其进行修改后的扩频水印方案.采用了鲁棒性较强的更适合于版权保护的乘法嵌入规则,在宿主信号中嵌入水印;水印检测时,在充分考虑了不同的变换域、信道特性以及人类视觉特性的基础上,采用基于广义高斯分布和Weibull分布模型的各种变换域的鲁棒优化检测器.使用位委托方案对数字水印信息进行委托,并联合使用随机序列隐藏水印嵌入位置信息.协议确保了在证明相应水印存在的同时,没有泄露任何有关水印的敏感信息,防止了蓄意攻击者利用认证过程中泄露的有关水印的敏感信息(如水印、水印位置、提取密钥等)来移除或伪造水印.数字水印方案对各种变换域的水印检测器给予了较全面的考虑,所以,应用该协议进行水印认证,其安全性、有效性、鲁棒性和实用性都有较大提高.
基于整数耦合帐篷映射的单向Hash函数及其性能分析
刘建东
2008, 45(3):  563-569. 
摘要 ( 429 )   HTML ( 0)   PDF (425KB) ( 484 )  
相关文章 | 计量指标
提出一种基于整数耦合帐篷映射的单向Hash函数,并对其特性进行了分析.提出的算法采用双向耦合映像格子模型,用整数帐篷映射取代了传统的逻辑函数,具有较为理想的混淆与扩散特性.应用该算法,可将任意长度的明文序列单向散列为160比特Hash值.实验与分析结果表明,这种Hash函数具有很好的单向性、抗碰撞性,满足单向Hash函数的各项性能要求.该算法全部采用有限整数集内的简单位操作完成,便于软硬件实现,并且有高的执行效率.