摘要:静态类型化XML处理语言为处理XML数据提供了新的途径,但现有的此类语言大多数效率较低.研究此类语言的一个重要问题——子类型关系的判定,并使用剪枝优化策略对XDuce的子类型关系判定算法进行优化.实验数据显示,优化后算法的执行效率平均提高20%.该策略具有普遍性,对所有使用类似算法的静态类型化XML处理语言都有效.

摘要:基于SAT的限界模型检测在处理实时系统时具有很高的复杂度.SMT求解器在计算可满足性的同时,还能处理算术和其他可判定性理论.在对实时系统进行检测时,用SMT求解器代替SAT求解器,系统里的时钟就可以用整型或实型变量表示,时钟约束则可以直接表示成线性算术表达式,从而使整个检测过程更加高效.带时间参数的计算树逻辑(timed computation tree logic,简称TCTL)被用来描述实时系统里的性质.同时,还对检测方法作了相应的改进.

摘要:经典的串匹配算法设计和分析中假设“字符互相独立并且等概率出现”,这与实际应用环境差异很大,导致出现很多问题.考虑了字符的概率分布和上下文的关联,同时兼顾应用的方便,提出了命中密度的概念.在给出基本定义和扩展定义后,通过对4种类型的代表性算法的理论和实验分析,给出了命中密度与算法性能之间的关系.同时,在对命中密度的分析中得出一些极具价值的结论.对命中密度概念的多角度理解以及对它与算法性能关系的深入剖析都说明,命中密度作为一个特征量,可以从一个侧面刻画模式串和文本之间的相关性,它对算法的设计和分析以及串匹配领域研究工作的扩展都具有指导意义.

摘要:Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*的最好算法.

摘要:数据缓存技术可以有效地减少网络拥塞,减轻服务器负载,加快信息访问速度.通过部署一组地域分布的缓存节点相互协作处理用户请求,可以进一步提高系统性能.在分布式缓存系统中,一个值得关注的问题是优化缓存的放置,使访问开销最小化.首先建立了一个理论模型来分析缓存副本放置对系统访问开销的影响.基于这个模型,缓存放置问题可以形式化地描述成一个最优化问题,提出了一种图算法来解决该问题.图算法使用修改的Dijkstra算法在访问代价图中寻找一条最短路径,该路径对应一种最优的缓存部署.理论上证明了图算法的正确性,并使用仿真实验对其性能进行评估.实验结果表明,图算法的性能优于大部分现有的分布式缓存机制.

摘要:基于规格说明的测试可以在不需要了解软件程序代码的情况下对软件进行功能测试.判定是形式规格说明中用于描述前、后置条件的主要形式.分析了基于规格说明的逻辑覆盖测试准则,针对已有的决定性逻辑覆盖测试准则的不足,提出了掩盖性逻辑覆盖测试准则,并对其进行了详细分析.提出了掩盖性逻辑覆盖测试准则的一个可行的测试生成算法.根据该准则生成的测试用例能够发现条件的掩盖性带来的错误.然后,从判定的结构入手,分析了条件之间的约束关系、复杂判定的分解与合成、判定之间的关系.这些分别能够阐明逻辑覆盖中条件间的耦合性问题、同一个条件在判定中的多次出现问题以及判定在程序中的位置问题.继而提出了全真判定覆盖、全假判定覆盖、完全子判定覆盖、唯一条件真覆盖以及唯一条件假覆盖等测试准则.满足这些测试准则的测试用例集能检测出不同类型的错误.最后,给出了这些测试准则之间的包含关系图,并建议了不同测试准则适用的应用场景.

摘要:Skyband查询是决策支持领域一类非常重要的查询.为了使数据库系统有效支持Skyband查询,必须解决Skyband基数估计的问题,即估计Skyband查询结果中包含的Skyband元素数,因为Skyband基数估计对于扩展数据库系统查询优化器的代价模型以便能够对Skyband查询进行优化非常重要.基于容斥原理的推广形式对Skyband基数进行理论分析并给出了时间和空间代价很小的对Skyband基数进行估计的算法.实验结果表明,该方法能够准确地对Skyband基数进行估计.

摘要:为了实现Web图像检索结果的聚类,提出了一种Web图像的图聚类方法.首先定义了两种类型关联:单词与图像结点之间的异构链接以及单词结点之间的同构链接.为了克服传统的TF-IDF方法不能直接反映单词与图像之间的语义关联局限性,提出并定义了单词可见度(visibility)这一属性,并将其集成到传统的tf-idf模型中以挖掘单词-图像之间关联的权重.根据LDA(latent Dirichlet allocation)模型,单词-单词之间关联权重通过一个定义的主题相关度函数来计算.最后,应用复杂图聚类和二部图协同谱聚类等算法验证了在图模型上引入两种相关性关联的有效性,达到了改进了Web图像聚类性能的目的.

摘要:传统的TCP传输协议在高速长距离网络中存在许多局限,其传输性能不能满足日益增长的海量数据传输应用的需求.UDP传输协议尽管传输速率很高,却没有可靠性保证.分析了传统的传输协议在高速长距离网络中的局限,分类总结了近年来提出的各种改进的传输协议的主要设计思想以及在传输协议性能评价方面的工作,最后提出了目前研究中仍然存在的开放性问题和进一步的研究方向.

摘要:互联网逐渐成为通信基础设施并承载了更多的关键业务流量,即使瞬时中断也会对某些应用造成巨大损失.然而,传统路由协议在出现链路/节点故障等拓扑变化时存在收敛时间长、瞬时不可达以及环路的问题.实际测量发现,路由瞬时失效相当普遍.因此,研究人员提出多种能够保证流量无中断转发和快速恢复的路由协议.在分析瞬时失效现象以后,提出了生存性路由协议的分类方法,重点对一些重要的路由协议的核心路由机制进行深入分析,并比较其特点、性能、开销等.最后,结合该领域研究现状以及存在的问题,指出未来生存性路由的研究重点.

摘要:随着Internet规模的迅速扩大,复杂性和不确定性也随之增加,基于融合的网络态势感知必将成为网络管理的发展方向.在分析现有网络管理不足以及发展需求的基础上,介绍了网络态势感知的起源、概念、目标和特点.首先,提出了一个网络态势感知研究框架,介绍了研究历程,指出了研究重点以及存在的问题,并将现有评估方法分为3类:基于数学模型的方法、基于知识推理的方法、基于模式识别的方法.然后详细讨论了模型、知识表示和评估方法这3方面的研究内容,总结存在的共性问题,着重评价了每种评估方法的基本思路、评估过程和优缺点,并进行了对比分析.随后介绍了网络态势感知在安全、传输、生存性、系统评价等领域的应用研究.最后指出了网络态势感知的发展方向,并从问题体系、技术体系和应用体系3方面作了总结.

摘要:车用自组网作为移动自组网在智能交通系统中的应用,有望为人们提供更安全、效率更高的旅行方式.广播协议为危险警告、协同驾驶、路况通报等交通信息的发布提供了有效途径.简要介绍了车用自组网的特点和应用分类.采用分析和比较方法,讨论各种信息广播协议的特点、性能差异和应用范围,并针对车用自组网的特点及应用需求指出未来信息广播模型的设计思想和突破方向.

摘要:随着各种应用的需求和光网络技术的飞速发展,互联网领域出现了高速长距离光网络.最新研究发现,由于当前各种科学应用的迫切需求以及网络带宽的迅速提高,网络速率已经远远超出了终端系统的处理能力.在高速长距离光网络环境中,拥塞已经从网络转移到了终端,终端系统的处理能力逐渐成为传输速率的瓶颈.因此,各种终端性能自适应的高速传输协议应运而生.基于这一类协议改进的不同思路,对它们进行了分类描述,重点分析了这些协议的拥塞检测和速率适配机制以及各自的优缺点,在归纳和总结目前研究中仍然存在的开放性问题的同时,提出了进一步的研究方向.

摘要:无线传感器网络(wireless sensor networks,简称WSNs)由一组低功率且能量受限的传感器节点构成,设计此类网络的一个基本挑战便是最大化网络生命期的问题.在WSNs中,由于邻近传感器节点所收集的数据之间往往具有时空相关性,多采用数据聚合技术作为去除数据冗余、压缩数据大小的有效手段.合理地应用数据聚合技术,可以有效地减少数据传递量,降低网络能耗,从而延长网络生命期.研究了WSNs中结合数据聚合与节点功率控制的优化数据传递技术,提出了一种新的最大化网络生命期的路由算法.该算法采用遗传算法(genetic algorithm,简称GA)最优化数据聚合点的选择,并采用梯度算法进一步优化结果.该算法均衡节点能耗,并最大化网络生命期.仿真结果表明,该算法极大地提高了网络的生命期.

摘要:通过分析物联网资源寻址特性,对互联网资源寻址的层次迭代模型进行扩展.提出物联网资源寻址的通用层次模型,为解决由多种物品编码标准共存而引起的物联网资源寻址的特有问题提供理论模型依据.根据此模型,建立物联网资源寻址的应用结构模型,并通过对其功能性的实现,验证了通用层次模型的有效性及可行性.

摘要:基于网络协议层框架充分分析了TCP应用到Ad Hoc网络导致性能下降的原因,包括:物理层中易损耗的无线信道, MAC层中的过度竞争和不公平接入,网络层中节点移动引起的频繁路由失效,传输层中TCP采用的不合适机制,包括基于窗口的传输、基于数据包丢失的拥塞指示,拥塞窗口的慢启动和AIMD、对ACK自定时的依赖;提出了全新的适合Ad Hoc网络特性的跨层优化拥塞控制协议CCOC(cross-layer optimal congestion control).CCOC运用了跨层设计框架来改进MAC层的接入信道公平性、检测虚假链路失效、减少路由失效次数、加快路由切换后的重启动、运用SACK实现可靠传输和实施非线性优化论指导设计的自适应优化策略;描述了CCOC的协议体系结构;实施了详细的NS仿真实验,仿真结果表明,在几乎所有的仿真场景和移动环境下,CCOC比TCP和ATCP在许多重要性能指标,如吞吐量和公平性方面都有了明显的改进.

摘要:设计安全、合理的密钥管理方法,是解决无线传感器网络安全性问题的核心内容.提出了EEHS(a novel energy efficient and highly survivable dynamic key management scheme),是一种基于EBS(exclusion basis system)的、适合于大规模分簇式无线传感器网络的动态密钥管理方法,它具有安全性强、能量效率高、动态性能好、可扩展性强等特点.一种新型多项式密钥(同化多项式密钥)被运用在了EEHS的EBS管理密钥中,显著地提高了网络的抗捕获能力.当节点被捕获时,EEHS还可以动态取消并更新被捕获节点所拥有的全部密钥,最终驱逐被捕获的节点.为提高网络的能量效率和鲁棒性,EEHS将密钥分配和密钥生成等功能分配给簇内不同的功能节点,且传感器节点轮流作为功能节点使用.仿真与分析结果表明,与相关工作相比,EEHS可以显著提高网络的能量效率、延长网络寿命、加强网络安全性.

摘要:提出一种基于视频运动估计熵模型的自适应视频水印算法.该算法将人类视觉系统(human visual system,简称HVS)与视频分块运动估计(block motion estimation of video)相结合,获取视频序列帧中与运动相关的视频运动信息,然后利用熵模型对视频序列帧中的运动信息进行统计,从而得到一组基于视频序列帧间运动信息与人类视觉屏蔽特性相结合的非线性计算公式.利用该组计算公式,可以根据视频帧的内容自适应地计算每个方块的水印最大嵌入强度.实验结果表明,熵模型与非线性公式的引入较大幅度地提高了视频水印的透明性,并且能够有效地抵抗常见的针对视频水印的攻击,具有较高的安全性和鲁棒性.

摘要:IP地址真实性验证成为构建可信网络的基础,基于源-目的标识(密钥)的自治域级IP欺骗过滤和基于源标识(公钥)的端系统级IP认证均采用了端-端方式试图解决IP欺骗.端-端认证方式实现简单,但却忽略了IP欺骗报文对中间网络的泛洪攻击,防御效果差.提出面向IP欺骗防御联盟成员的域间IP欺骗防御服务增强机制——ESP(enhanced spoofing prevention).ESP引入开放的路由器协同机制,提供了源-目的路径中ESP节点信息通告和协同标记的框架.基于源标识IP欺骗防御,ESP融入了路径标识,不仅减小了源标识冲突概率,而且混合型标识支持了ESP节点根据报文标识提前过滤IP欺骗报文.基于BGP(border gateway protocol),提出前缀p-安全节点的概念和检测理论,有效控制了源标识传播范围,减小了ESP节点的标记和过滤开销.ESP继承了基于标识的防御机制的可部分部署性,能够很好地支持动态路由和非对称路由.应用Routeview提供的RIB(routing information base)进行评估,ESP增强了IP欺骗防御服务的能力,而且能够提前过滤IP欺骗报文.

摘要:多路径路由实现是移动ad hoc网络可靠运行的有效保证.针对多路径路由协议的安全性分析,建立了基于UC(universally composable)框架的可证明安全路由协议的新方法.基于攻陷的网络拓扑模型,扩展了可模糊路由概念,提出了多路径可模糊路由集合概念,用于描述攻陷网络拓扑结构的移动ad hoc网络多路径路由;基于UC安全模型,提出了基于UC-RP(universally composable security framework for ad hoc networks routing protocol)框架的路由协议形式化安全定义;针对MNDP(multiple node-disjoint paths)协议存在的安全问题,提出了新的移动ad hoc网络节点不相交多路径动态源路由协议(简记为SMNDP(security multiple node-disjoint paths)协议).将基于UC-RP框架的可证明安全路由协议的新方法应用于SMNDP协议的安全分析.SMNDP协议的可证明安全性可以归约为消息认证码和签名机制的安全性.SMNDP协议实现了路由发现协议的正确性、节点身份的认证性和路由消息的完整性.

摘要:衡量一种路由算法优劣的两个重要指标是路由表的大小和路径的长度,但这两个方面通常是互相矛盾的.紧凑路由(compact routing)研究旨在设计路由算法在这两个指标上获得优化的平衡(tradeoff).目前,已有许多学者针对任意拓扑的网络提出了普适(universal)的紧凑路由方法(compact routing scheme).但是,真实的网络都具有特定的拓扑,普适的紧凑路由方法并没有利用真实网络呈现的特定拓扑特征,因而在这类网络上未必能取得最优的性能.最近的研究发现,许多真实网络都具有无标度特征和强聚集特征,利用这两类拓扑特征,提出了一种针对这类网络的紧凑路由方法.该路由方法将网络看成是由一个骨干树和一些捷径组成,在任意源节点和目的节点之间路由,使用路径的长度不超过它们的最短路径长度加上一个整数b.路由表大小限制在O(clog2n)比特,其中,b和c是由网络结构决定的参数.实验结果表明,在无标度网络上,b和c可以同时取较小的值.与以往的紧凑路由方法相比,该方法在平均性能上表现更好.

摘要:在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.

摘要:给出了一种具有最优代数免疫度的偶数元布尔函数的构造,同时还给出了一种具有最优代数免疫度的平衡旋转对称偶数元布尔函数的构造.在构造过程中用到了线性代数和组合计数中的有关结论,这些函数对代数攻击均有很强的抵抗能力.构造的平衡旋转对称布尔函数还可用在Hash算法的轮函数中,增加了算法的安全性.

摘要:通用移动通信系统采用3GPP认证与密钥协商协议作为其安全框架,该协议对GSM存在的安全隐患作了有效的改进.对3GPP认证与密钥协商协议进行安全性研究,分析其容易遭受4种类型攻击方式.为了解决上述存在的安全隐患,提出在位置更新与位置不变两种情况下的基于公钥密码学的认证与密钥协商协议,采用形式化的分析方式证明了所提出算法的安全性,并将该协议与已有协议在安全性方面进行了比较.结果显示,所提出的协议算法能够极大地增强3GPP认证与密钥协商协议的安全性.