摘要:提出了一种基于智能体的多目标社会进化算法用以求解多目标优化问题(multiobjective optimization problems,简称MOPs),通过多智能体进化的思想来完成Pareto 解集的寻优过程.该方法定义可信任度来表示智能体间的历史活动信息,并据此确定智能体的邻域、控制智能体间的行为.针对多目标问题的特点,设计了3 个进化算子分别体现适者生存、弱肉强食、多样性原则以及自学习的特性.同时采用擂台赛法则构造Pareto 解的存储种群.仿真实验结果表明,该算法能够较好地收敛到Pareto 最优解集上,并且具有良好的多样性.另外,通过对智能体局部邻域环境建立方式的分析结果表明引入“关系网模型”可有效提高算法的收敛速度,并能在一定程度上提高解的质量.

摘要:#SAT 问题是SAT 问题的扩展,需要计算出给定命题公式集合的模型个数.通过将问题求解沿着归结的反方向进行,并利用容斥原理解决由此带来的空间复杂性问题,提出了一种基于扩展规则的模型计数和加权模型计数问题求解框架,可以看作是目前所有模型计数问题求解方法的一种补方法.证明了该方法的完备性和有效性,设计了基于扩展规则的#SAT 求解系统:JLU-ERWMC.实验结果表明,JLU-ERWMC 在有些问题中优于目前最为高效的#SAT 问题求解系统.

摘要:针对Mean-Shift(中值漂移)算法中核函数带宽不能实时改变的缺陷,提出一种基于边界力的Mean-Shift核函数带宽自适应更新算法.在分析目标加权核直方图模型的基础上,引入区域似然度以提取目标的局部信息.然后,比较相邻帧间的区域似然度并构建边界力.通过对边界力的计算,得到边界点的位置,进而自适应地更新核函数带宽.实验结果表明,这些工作改善了Mean-Shift 算法在目标尺度和形态发生变化时的跟踪效果,并且可以满足实时性的需要.

摘要:提出一种潜在属性空间树分类器(latent attribute space tree classifier,简称LAST)框架,通过将原属性空间变换到更容易分离数据或更符合决策树分类特点的潜在属性空间,突破传统决策树算法的决策面局限,改善树分类器的泛化性能.在LAST 框架下,提出了两种奇异值分解斜决策树(SVD (singular value decomposition) oblique decision tree,简称SODT)算法,通过对全局或局部数据进行奇异值分解,构建正交的潜在属性空间,然后在潜在属性空间内构建传统的单变量决策树或树节点,从而间接获得原空间内近似最优的斜决策树.SODT 算法既能够处理整体数据与局部数据分布相同或不同的数据集,又可以充分利用有标签和无标签数据的结构信息,分类结果不受样本随机重排的影响,而且时间复杂度还与单变量决策树算法相同.在复杂数据集上的实验结果表明,与传统的单变量决策树算法和其他斜决策树算法相比,SODT 算法的分类准确率更高,构建的决策树大小更稳定,整体分类性能更鲁棒,决策树构建时间与C4.5 算法相近,而远小于其他斜决策树算法.

摘要:词汇级复述研究旨在为词汇获取复述.词汇级复述是上下文相关的,即对同一个词在不同上下文中应获取不同的复述词.提出了一种获取上下文相关词汇级复述的方法.该方法包括两部分:基于网络挖掘的候选复述词获取以及基于二元分类的复述词确认.在《人民日报》语料库上的实验结果表明:(1) 基于网络挖掘的候选复述词获取方法是切实可行的,平均为每个待复述词在每个给定的上下文句子中获取2.3 个正确复述词;(2) 利用二元分类的方法进行复述确认是有效的,其F 值达到0.6023;(3) 利用该方法抽取得到的复述中,有75.11%和98.31%无法通过两种常用的上下文无关方法,即基于辞典和基于聚类的方法来获得.这证明了所提出的上下文相关复述方法可以有效地补充传统的上下文无关方法.

摘要:提出基于相关分析的多数据流聚类算法.该算法将多数据流的原始数据快速压缩成一个统计概要.根据这些统计概要,可以增量式地计算相关系数来衡量数据间的相似度.提出了一种改进的k-平均算法来生成聚类结果.改进的k-平均算法可以动态、实时地调整聚类数目,并及时检测数据流的发展变化.还将算法应用到按照用户要求的聚类问题(COD),使得用户可以在任意的时间区间上查询聚类结果.提出了一种合理的时间片断划分机制,使得用户指定的任意时间区间都可以由这些时间片断组合而成.在模拟和真实数据上的实验结果都表明,该算法比其他方法具有更好的聚类质量、速度和稳定性,能够实时地反映数据流的变化.

摘要:全文索引技术(full-text index technique)作为提高全文检索时空效率的有效方式之一,近年来得到了广泛而深入的研究.根据全文索引实现技术的不同,将其分为三大类:索引技术、压缩与索引混合技术以及自索引技术(self-index technique).从上述分类角度综述了全文索引时空效率方法中具有代表性的一些方法和技术:倒排文件、签名文件、后缀树与后缀数组、基于这3 种索引的压缩技术、基于倒排文件的自索引与基于后缀数组的自索引的基本原理、所面临的问题及进展,并对这些技术的时空性能进行了详细的分析和比较,分析了各种技术的适应环境及优劣.最后总结了上述技术的特点,指出了存在的问题以及未来的研究方向.

摘要:直方图在查询优化过程中起着重要作用.在压缩数据库中利用查询处理的特点构建自适应直方图以便于查询优化或近似回答查询是尚待解决的问题.通过对查询缓冲池内的查询进行调度来追踪热点数据,并用查询结果中的反馈信息构建自适应直方图以加快自适应直方图的收敛速度.另外,还提出一种参数化方法来估计未被任何桶覆盖的区域中元组的个数.该直方图可以增量式地被维护.实验结果表明,这种直方图具有良好的平均精度、更快的收敛速度和更强的自适应能力.

摘要:随着P2P 技术在电子商务等领域的广泛应用,对分布在P2P 网络中的数据进行聚集操作的需求越来越迫切.但是,由于P2P 网络的大规模及分散性,这种聚集操作的实现颇具挑战性.而且在很多应用中,P2P 网络中的数据往往是随时间变化的,这进一步增加了聚集操作的难度.现有P2P 网络中的聚集算法均假定网络中的数据是非时变的,如果将其直接应用在存在时变数据的P2P 网络中,则会因为其聚集时间过长而导致聚集过程中数据已经发生变化的问题.为此,提出了一种P2P 网络中基于均衡采样的时变数据近似聚集算法,理论分析和实验结果表明,该聚集算法在处理时变数据时优于已有的算法,可以有效地应用于存在时变数据的P2P 网络中.

摘要:提出了一种新的自适应结构索引:AS-Index(adaptive structural index),能够克服现有静态索引和自适应索引的缺陷,具备高效的查询和调整性能.AS-Index 建立在F&B-Index 的基础之上,其索引结构包括F&B-Index,Query-Table 和Part-Table.Query-Table 能够记录频繁查询,避免了查询过程中的冗余操作.并且,在Query-Table 的基础上提出了自底向上的查询处理过程,能够充分利用现有的频繁查询高效地回答非频繁查询.Part-Table 用于优化包含祖先后裔边的查询,进一步提高了查询性能.现有的自适应结构索引的调整粒度是XML 元素节点,调整过程往往需要遍历整个文档.而AS-Index 是基于F&B-Index 节点的增量调整,其过程是局部的,高效的,并且能够支持复杂分支查询的调整.实验结果表明,AS-Index 在查询和调整性能上优于现有的XML 结构索引.同时,相比于现有的自适应结构索引,AS-Index 针对大规模文档具有更加优良的可扩展性.

摘要:多维空间的skyline 查询处理是近年来数据库领域的一个研究重点和热点.Vlachou 等人首次考虑如何在P2P 网络中有效进行子空间上的skyline 查询,并提出“扩展skyline 集合”的概念来减少预处理时的网络传输量.然而实验评估表明,扩展skyline 集合只能有限地减少子空间skyline 查询预处理的数据传输量.基于此,提出一种缩减处理时数据传输量的有效方法TPAOSS(three-phase algorithm for optimizing skyline scalar).TPAOSS 算法根据全空间skyline 集合与子空间skyline 集合间的语义关系分3 个阶段来传输必要的数据,其中第1 阶段发送全空间skyline 对象;第2 阶段接收种子skyline 对象;而第3 阶段基于Bloom filter 技术发送种子skyline 对象在子空间上的重复对象.为了降低第2 阶段的数据传输量,给出两种接收种子skyline 对象的有效策略.理论分析和实验评估结果表明,所给出的算法具有有效性和实用性.

摘要:基于非共享策略,围绕着降低系统反应延迟与通信负荷的目标,提出了一种分两阶段渐进求解的分布式算法BOCS(based on the change of skyline),并对算法的关键实现环节,如协调站点与远程站点间的通信、skyline 增量的计算等进行了系统优化,使算法在通信负荷与反应延迟上达到了较好的综合性能.理论分析证明,在所有基于非 共享策略的算法中,BOCS 算法通信最优.大量的对比实验结果也表明,所提出的算法高效、稳定且具有良好的可扩展性.

摘要:提出一种面向查询扩展的矩阵加权关联规则挖掘算法,给出与其相关的定理及其证明过程.该算法采用4种剪枝策略,挖掘效率得到极大提高.实验结果表明,其挖掘时间比原来的平均时间减少87.84%.针对现有查询扩展的缺陷,将矩阵加权关联规则挖掘技术应用于查询扩展,提出新的查询扩展模型和更合理的扩展词权重计算方法.在此基础上提出一种伪相关反馈查询扩展算法——基于矩阵加权关联规则挖掘的伪相关反馈查询扩展算法,该算法能够自动地从前列n 篇初检文档中挖掘与原查询相关的矩阵加权关联规则,构建规则库,从中提取与原查询相关的扩展词,实现查询扩展.实验结果表明,该算法的检索性能确实得到了很好的改善.与现有查询扩展算法相比,在相同的查全率水平级下,其平均查准率有了明显的提高.

摘要:提出一种移动对象数据库模型——Dynamic Transportation Network Based Moving Objects Database(简称DTNMOD),并给出了DTNMOD中基于移动对象时空轨迹的网络实时动态交通流分析方法.在DTNMOD中,交通网络被表示成动态的时空网络,可以描述交通状态、拓扑结构以及交通参数随时间的变化过程;网络受限的移动对象则用网络移动点表示.DTNMOD 模型包含了完整的数据类型和查询操作的定义,因此可以在任何可扩充数据库(如PostgreSQL 或SECONDO)中实现,从而得到完整的数据库模型和查询语言.为了对相关模型的性能进行比较与分析,基于PostgreSQL 实现了一个原型系统并进行了一系列的实验.实验结果表明,DTNMOD 提供了良好的区域查询及连接查询性能.

摘要:节约能量以提高网络寿命是传感器网络研究面临的重要挑战.网内聚集查询在中间节点对数据进行预处理,可以减少消息传送的数量或者大小,从而实现能量的有效利用,但是,目前的聚集查询研究假设采样数据都是正确的.而目前的异常检测算法以检测率作为首要目标,不考虑能量的消耗,也不考虑查询的特点.所以将两方面的研究成果简单地结合在一起并不能产生很好的效果.分析了错误和异常数据可能对聚集结果造成的影响,提出了健壮聚集算法RAA(robust aggregation algorithm).RAA 对传统聚集查询进行了改进,在聚集的同时利用读向量相似性判断数据是否发生了错误或异常,删除错误数据,聚集正常数据并报告异常,使用户可以对网络目前状况有清晰的理解.最后,比较了RAA 和TAGVoting(在使用TAG(tiny aggregation)算法聚集的同时利用Voting算法进行异常检测),实验结果表明,RAA 算法在能量消耗和异常检测率方面都优于TAGVoting.

摘要:多跳无线网络中隐藏节点导致节点之间的冲突频繁、数据重传率高、网络吞吐量下降.而802.11 DCF 中 的RTS/CTS(ready-to-send/clear-to-send)机制不能有效地防止隐藏节点,特别是随着网络中节点通信速率的提高,由于节点的信噪比要求也相应提高,接收节点受到更大范围内隐藏节点的干涉,RTS/CTS 机制防止隐藏节点的效率急 剧降低.首先,在考虑网络积累干涉以及环境噪音的情况下分析了多跳无线网络中的隐藏节点问题.然后,提出一种 双信道无冲突MAC(media access control)协议DCCFMA(double channel collision free media access).DCCFMA 协议采用双信道结构,接收节点根据数据信道中发送节点的信号强度动态调节控制信道的发射功率,以完全覆盖接收节 点周围所有的隐藏节点,保证接收节点在接收过程中不受干涉.DCCFMA 协议能够有效地解决多跳无线网络中的隐藏节点问题.仿真结果表明,与802.11DCF 相比,DCCFMA 机制下的平均网络吞吐量增加了24%.

摘要:在P2P 系统中,声誉模型是建立节点间信任关系的重要方法之一,但现有的P2P 声誉模型几乎都是纯分散式的,具有信任收敛慢、信任管理复杂和网络开销大等缺点.在TLT(two-level trust)中,节点自发组织为信任簇,信任评价以簇为单位.每个簇由簇首和成员节点组成,簇首和成员节点之间是一种相互信任的关系:簇首为了提高自身的簇间服务信任,利用簇内服务信任观察成员节点的服务性能,过滤恶意的成员节点;成员节点为了提高服务声誉和接受更好的服务,利用代理信任考察簇首的管理能力.分析和仿真结果表明:在TLT 中,节点的信任值收敛快,恶意行为能够被快速识别;TLT 可扩展性好,如信任管理简单和网络开销小.

摘要:研究了缓存控制对媒体流用户层QoS 的影响.多媒体系统信宿端通常采用播放缓存来补偿时延抖动,提高媒体流播放的连续性.缓存控制虽然能够降低时延抖动的影响,却增加了端到端时延.时延或时延抖动是用户可感知的QoS 参数,缓存控制对用户层QoS 的影响究竟如何呢?利用已有的应用层向用户层QoS 映射的研究结果,分析缓存控制参数与端到端QoS 参数、应用层QoS 参数的关系,获得了缓存控制参数与用户层QoS 参数的关系.从理论上深入挖掘缓存控制对用户层QoS 参数的作用,给出了提供确定时延和时延抖动保障的缓存容量值,论证了在网络环境一定时存在提供最佳用户层QoS 的缓存容量值.实验结果验证了分析.

摘要:提出了无线传感器网络基于两跳邻居信息的实时路由.包的截止期要求映射为速率要求的路由决策方法在SPEED 中首先提出,而本文提出的路由决策是基于两跳速率.如果没有节点能够满足给定速率,采用节能的概率丢包策略降低截止期错失率,可以提高能效.如果截止期松弛,嵌入平衡能耗的代价函数缓解某些节点被频繁选为转发节点的情况,以达到网络的能耗平衡.在仿真中模拟了物理层和MAC 层,采用了通过Mica2 Motes 实验得到的损耗链路模型.仿真结果显示,提出的路由方案比基于单跳信息的SPEED-S 路由的截止期错失率更低,能量效率更高,而且在端到端延迟的性能总体上没有降低.该设计可用于对服务质量要求较高的基于传感器网络的实时应用中.

摘要:结构化P2P 覆盖网络与实际物理网络的拓扑不匹配问题是影响结构化P2P 网络路由性能的重要因素.提出了检测并降低重复链路使用的拓扑一致性解决方案DDL(detecting and decreasing links overlapped scheme).DDL从实际物理网络路由出发,通过检测覆盖网络三点路由经历的实际物理链路重复利用的情况,在适当的条件下,通过重定向报文的发送,降低路由经历的物理链路数.根据不同的重复链路的定义,给出了后向和前向两种检测重复链路的方法.DDL是一种从物理链路层面解决P2P 网络拓扑一致性问题的方法,可以使用在任何结构化P2P 网络中,不受限于覆盖网络层的组织方式.性能分析及仿真实验结果表明,使用DDL方案能够显著提高覆盖网络与物理网络的拓扑一致性.

摘要:动态策略支持与授权粒度是访问控制的关键问题.现有的研究只关注安全策略的描述能力,却忽略了对策略结构与授权粒度的分析,从而无法全面满足动态策略支持与最小授权要求.指出Lampson 访问矩阵模型是对最细粒度访问控制的抽象,普通安全策略则根据应用安全需求对Lampson 访问矩阵进行聚合.基于安全标签的聚合性描述框架(a escriptive framework of groupability basing on security labels,简称GroSeLa)可将普通安全策略映射为Lampson 访问矩阵,该框架分为基本组件与扩展两部分:前者分析用于实现矩阵聚合的安全策略结构;后者则指出实现全面动态策略支持必须支持的7 类管理性需求.在此基础上,提出5 项聚合性指标:聚合因子、动态因子、策略规模、授权粒度与职责隔离支持.对4 类经典安全策略ACL,BLP,DTE 与RBAC 的评估,是从矩阵聚合的角度分析不同的安全策略在表达性、可用性与授权粒度上的差异.

摘要:目前,存在众多的随机性检测项目,并且许多项目都带有参数.选择所有的项目进行检测不现实,因此需要研究检测项目之间的关系.从统计学角度出发,对检测项目的相关性进行研究,首先定义了检测项目之间存在的4 种关系,提出了检测项目相关度的概念,然后利用熵值法对检测项目相关度进行度量,并证明了这4 种关系与相关度的联系,同时给出了一种计算相关度的算法和一个基于相关度的检测项目选择策略.所研究的结果为随机性检测项目及其参数选择提供了理论依据.与此同时,利用相关度对NIST 在评选AES 中所采用的检测项目进行研究,发现了其中一些检测项目之间存在着依赖关系.

摘要:目前在具有后向无关联性的本地验证撤销群签名方案中,公钥长度和时间间隔的总数线性相关,撤销列表的大小与时间间隔的总数和被撤销用户的总数线性相关.因此,当时间间隔总数和被撤销成员总数比较大时,所需的存储空间和撤销验证时的开支都比较高.在DTDH和q-SDH假设下,提出一种具有后向无关联性的本地验证撤销群签名方案,它具有较短公钥长度和撤销列表.

摘要:随着计算机软、硬件技术的不断进步和应用需求的日益增长,以计算机为中心的计算系统的应用范围越来越广,其复杂程度也在迅速提高,人们对如何评估和提高计算系统的可信赖性的需求日益迫切.首先给出了计算系统的可信赖性的定义,并系统地定义了一整套量化评价指标;同时,对计算系统面临的各种可信赖性威胁进行了详细的归类分析.传统的方法难以应对复杂系统面临的各种可信赖性问题,人们仍在不断地寻求新的技术.虚拟化技术在这种应用背景下走向复兴,成为一大研究热点.介绍了已有的虚拟化技术在增强系统可信赖性上相关的研究成果,并且总结了虚拟化技术在增强系统可信赖性方面的各种特性和机制.然而由于现有的计算系统体系结构的限制,难以将虚拟化技术在增强系统可信赖性方面的优势充分地发挥出来.面向服务的体系结构(service oriented architecture,简称SOA)以其松散耦合、平台无关性等特点很好地适应了虚拟化技术的需求.因此,最后将SOA 和虚拟化技术相结合,提出了一种增强计算系统可信赖性的系统架构,即面向服务的虚拟化SOV(service oriented virtualization),并且分析了SOV 系统如何在遭受各种可信赖性威胁时,运用体系结构优势和虚拟化技术的各种机制保证系统可信赖性.