摘要:降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足"覆盖要求"(工作节点必须能够完全覆盖目标区域)和"连通性要求"(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralized Voronoi tessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小节点集.当节点通信半径大于等于2倍感知半径时,CVT算法构造的节点集是连通的;当节点通信半径小于2倍感知半径时,设计了一种基于最小生成树(minimum spanning tree,简称MST)的连通算法来计算确保CVT算法构造的覆盖集连通所需的辅助节点.理论分析和实验数据表明,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小方面都优于已有的贪婪算法.

摘要:把时间序列相似性匹配的基本概念和方法引入到地震预报的应用中.在分析现阶段时间序列研究成果的基础上,结合大量地震历史源数据和领域专家经验知识,提出了有关地震地区相关性的地震相似度定义和地震序列相似性匹配模型,并通过大量实验模拟对该模型进行了反复验证,实现了基于地震相似度的时间序列相似性匹配算法.同时,通过分析我国地震活动频繁区域近20年来的地震历史数据,应用地震区域序列相似性匹配算法进行了固定时间差的粗粒度和细粒度纵向序列相似性实验分析,取得了可信度较高的实验结果,为地震学预测的应用研究提供了较好的技术支持.

摘要:提出了一种新的测序纠错算法.该算法在对测序数据拼接之前对其进行检查,找出并修正测序序列中的错误.该算法将测序数据映射成欧拉超路,并通过一种称为合并变换的等价变换,通过一系列规则的限制和引导,动态地对欧拉超路进行简化.在此过程中,该算法将错误的边和正确的边对应起来,再通过替换纠错过程消除错误.在对T.tengcongensis(TT)和T.whipplei(TW)两个数据集的测试过程中,这种方法分别找出并修正了86%和83%的错误,而原欧拉序列拼接中的纠错算法对这两组数据集的纠错结果只有71%和53%.

摘要:研究了波分复用全光树环网在不同通信模型下的波长分配算法及其最坏性能分析.对于静态模型,证明了5L/2是树环网所需波长数的紧界.对于动态模型,提出了一种近似比为∑_i=1^hmax_r∈Ri[log|V(r)|]+h的波长分配算法,其中h为树环网的基树的层数,R_i为树环网中处于第i层的环的集合,|V(r)|为环r上的节点数.对于增量模型,提出了一种近似度为O[log₂(t+1)]的波长分配算法,其中t为树环网中的环数.

摘要:讨论了当今算法作曲这一研究领域中存在的一些主要问题.评述了这一领域所采用的一系列关键技术,包括Markov链、随机过程、基于音乐规则的知识库系统、音乐文法、人工神经网络技术以及遗传算法.得出的结论是,作曲系统可以朝着集多种方法为一体的混合型系统(hybrid system)的方向发展.系统应在音乐创作的各个层面上提供灵活的人机交互手段,以便提高系统的实用性和有效性.

摘要:在图像模板匹配问题中,基于像素灰度值的相关算法尽管已经十分普遍,并得到广泛的应用,但目前此类算法都还存在有时间复杂度高、对图像亮度与尺寸变化敏感等缺点.为了克服这些缺点,提出一种新的基于图像灰度值的编码表示方法.这种方法将图像分割为一定大小的方块(称为R-块),计算每个R-块图像的总灰度值,并根据它与相邻R-块灰度值的排序关系进行编码.然后通过各个R-块编码值的比较,实现图像与模板的匹配新算法中各个R-块编码的计算十分简单;匹配过程只要对编码值进行相等比较,而且可以采用快速的比较算法新算法对像素灰度的变化与噪声具有鲁棒性,其时间复杂度是O(M²log(N)).实验结果表明,新算法比现有的灰度相关算法的计算时间快了两个数量级.

摘要:运用机器学习中新颖的核方法和社会网络中广泛存在的小世界现象,对Hattori等人提出的多模块多对多联想记忆模型(multi-module associative memory for many-to-many associations,简称(MMA)²)进行了改进,构建出了一个基于小世界体系的多对多核联想记忆模型框架(small world structure inspired many to many kernel associative memory models,简称SWSI-M²KAMs).该框架不仅克服了原模型不能联机提交训练样本且迭代次数过多的缺陷,而且拓展了原模型的智能信息处理范围.更重要的是,通过核函数的选取,该模型框架可以衍生出更多新的多对多联想记忆模型,而且,由于小世界结构的引入,在一定程度上简化了模型的结构复杂度.最后的计算机模拟,证实了新的模型具有良好的多对多联想记忆功能.

摘要:作为基因功能预测的主要手段,序列相似性查询技术是生物信息学领域的研究热点.基因序列和结构的相似性往往决定了基因功能的相似性,因此可以通过基因序列的相似性查找来预测新基因的功能.分析了MRS索引中频率变化和小波变换等相关技术,讨论了它们的缺点和不足,提出了一种基于二分频率变换2-PFT的序列似性查询处理技术.首先,设计了二分频率变换和相应的距离函数,使得系统较之频率变换和小波变换具有更高的过滤能力,极大地提高了系统的性能;其次,解决了处理任意长度查询的问题.理论证明和实验结果均表明,2-PFT系统的性能远远优于MRS系统.

摘要:在指纹分类和识别算法中,提取的奇异点(core点和delta点)数目和奇异点的准确位置是非常重要的.介绍了一种基于Gaussian-Hermite矩分布属性的自适应指纹奇异点定位方法,为了准确地确定奇异点,用到了指纹图像在多种尺度下的不同阶Gaussian-Hermite矩分布,并用一种基于主分量分析(principal component analysis,简称PCA)的方法分析指纹图像的Gaussian-Hermite矩分布.实验结果表明,该算法能够准确地确定奇异点位置.

摘要:研究了信息类自然口语对话中的交互模式及其自动分析.首先,基于话语分析中的Birmingham学派关于交互模式的工作和Halliday关于言语功能的分析,提出使用语句组来刻画交互模式,并建立原则性分类体系;然后,对语料中的交互模式进行标注分析;随后,根据影响语句组结构的主要因素建立交互模式分析算法,并在语料中进行实验.实验结果表明,语句组的整体分析正确率可达到55.4%～84.2%--取决于不同来源的扩展句子类型和语句主题的分析结果.

摘要:描述了应用模糊k均值方法聚类汉语多义动词的实验,共涉及到60个汉语动词,40个多义词,20个单义词.首先,自动获取每个动词的次范畴化框架的概率分布,然后,导出这些动词的模糊聚类.结果表明,纯洁度和对精确度的综合量度较好地反映了聚类性能,尽管动词的句法行为在一定程度上体现了深层语义,但汉语动词的句法行为不易从单一的语义层预测出来.

摘要:在轮询带宽调度和随机带宽调度两种经典算法的基础上,提出了一种基于邻居集合的带宽资源调度算法来分析和优化WiMAX(world interoperability for microwave access)网络的带宽分配和调度过程.该算法通过使用邻居集合和优先列表,对网络中的用户站,尤其是对使用Mesh模式连接的用户站之间的带宽调度进行了优化,使无线网络的带宽资源能够在网络局部得到优化调度,以达到优化整个无线网络的带宽调度效率.NS2模拟结果表明,该算法具有更低的延迟和更高的吞吐量,能够更好地利用网络资源.

摘要:时延是准确测量时延抖动、带宽等网络性能指标的基础.目前的时延测量方法由于存在时钟误差和位置误差因而精度较差.提出一种改进的时延测量方法,以TSC(time stamp counter)寄存器取代系统时钟计时来消除测量的时钟误差,将时间戳记录位置由应用程序转移到网卡驱动来消除位置误差,极大地提高了时延测量精度.实验结果表明,与传统方法相比,不同包长度下,所提出的方法可降低测量误差21%～150%,且测量结果稳定,对系统吞吐量基本无影响.该方法基于通用PC架构,测量成本低,适于普遍采用.

摘要:PIM-SM(protoc01-independent multicast-dense mode)协议是目前Internet首选的域内组播路由协议.影响其广泛应用的一个主要问题是该协议的控制报文负载比较大.为了对协议进行改进和优化,首先需要建立性能模型并进行准确的性能分析.利用随机Petri网(stochastic Petri net,简称SPN)模型对整个PIM-SM复杂的协议行为进行了建模,并在其SPN模型的基础上,结合路由器的实现,对协议中每种消息消耗的路由器处理负载和占用的网络带宽进行了分析和实验,发现Register消息和Join/Prune消息消耗的路由器处理负载比较多,而Join/Prune消息和Bootstrap消息占用的网络带宽比较大.根据性能分析的结论对PIM-SM协议进行了改进.与原来的协议相比,改进后的协议性能明显提高.

摘要:基于当前入侵检测技术在检测到攻击的情况下没有良好的反应策略过滤攻击流量这一问题,提出了基于攻击流量特征聚类的特征提取算法AFCAA(anomaly traffic character aggregation algorithm).针对一般DOS(denial ofservice)/DDOS(distributed denial ofservice)攻击流数据包头中具有某些相似的特性,AFCAA通过运用重心原理进行统计聚类,在一定的欧氏距离范围内对基于目的IP的攻击流样本相应字段进行聚类划分,动态地提取出攻击流的重心作为攻击的特征.然后,及时地把其特征传输给Net Filter,可以进行高效的过滤,并保护正常流量的传输.实验结果表明,对当前流行的多种拒绝服务攻击,应用AFCAA系统的软件路由器都能够较准确地获取异常流量的特征,从而有效地进行过滤,减少攻击包传播的危害,保护有限的网络资源.

摘要:在分布式环境下,利用信任管理机制来实现存取控制已得到人们的一致认同.但是,许可证的存储策略一直是这个领域中一个尚未完全解决的重要问题,而且它直接影响到许可证链的查找等问题.提出了利用许可证的发布者和主体两维信息,采用分布哈希表和Hilbert曲线对许可证进行分布定位的新的许可证存储策略.这种存储策略不仅具有很好的负载平衡的特性,而且为许可证的查找提供了充分的灵活性.同时,利用Hilbert曲线生成时的递归特性及其所具有的局部保持性,实现了在分布式环境中基于部分关键字的许可证查找.在此基础上,提出一种许可证链查找算法,实现了在查询过程中构造最小的许可证图,从而大幅度减少网络中的信息传输量.

摘要:半脆弱水印因为在多媒体内容认证方面的重要作用而受到人们密切的关注.为了能够区分偶然攻击与恶意篡改,半脆弱水印需要对一般的内容保护图像操作有一定的鲁棒性.由于JPEG压缩应用的普遍性,在保持较高的对篡改检测能力的情况下,提高抗JPEG压缩性能一直是半脆弱水印的重要问题.根据图像相邻小波高频系数之间的大小关系在JPEG压缩之后大多数没有发生变化这一事实,提出了一种新的抗JPEG压缩的半脆弱水印算法.实验结果表明,该算法计算简单,嵌入容量大,有很好的抗JPEG压缩性能,同时对篡改的定位也很精确.

摘要:在多对单传输模式下,数据分配是P2P分层流媒体中的核心问题.为了提高请求节点服务质量,同时也为了减少对Root节点带宽的占用,分两种情形予以讨论.一种是Root节点不参与的情形,其目标是最大化请求节点的服务质量.对此提出了一种基于多叉树搜索裁剪的精确算法和一种启发式近似算法.另一种是Root节点可参与的情形,其目标是在满足请求节点服务质量的同时,最大化节约Root节点的带宽资源.分析了该情形下目标问题的复杂性,提出一种启发式近似算法.仿真实验表明,在不同参数条件下,所提出的算法比同类算法都有性能上的改进.

摘要:TAE(tweakable authenticated encryption)模式是一种基于可调分组密码的加密认证模式.研究结果表明,安全的可调分组密码不是安全的TAE模式的充分条件.只有当可调分组密码是强安全的时候,TAE模式才是安全的.同时,还给出了TAE模式的一些改进,得到模式MTAE(modifiedtweakable authenticated encryption),并且证明了其安全性.

摘要:结构化P2P网络是构建于物理网络拓扑之上的一层Overlay网络,两层之间的唯一联系是Hash散列函数,这种Hash关系使得节点的逻辑ID号与物理位置之间不存在任何联系.从分析Hash散列函数的性质入手,归纳出目的节点、传统(chord)语义路由中继节点序列、聚类邻居节点集三者之间的逻辑关联特性,并将其应用于所提出的基于自组织聚类的语义路由改进算法SCSRAA(self-organizing clustering semantic routing advarced algorithm)中,从而达到提高语义路由效率的研究目的.针对自组织模式下聚类节点仅存在局部视图的特性,详细讨论了聚类算法及节点获取其他节点物理位置信息的各种规则,给出了SCSRAA路由算法详尽的描述及理论分析.仿真实验表明,该算法具有较强的语义路由效率提升能力.

摘要:规划问题是一类复杂的问题.由于规划问题中各个目标之间往往存在着实现上的顺序关系,发掘这种顺序关系并加以利用是提高规划算法效率的一种途径.由于判定目标间的顺序关系同样是PSPACE完全的,因而为利用目标间的顺序关系首先需要有效地提取目标间的顺序关系.给出了一种利用状态不变式来提取目标间顺序关系的GOWN(goal ordering with invariants)方法,并在比较目标间的顺序关系时,通过抽象和合一的手段,有效地控制了问题的增长规模,提高了处理效率.