Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortest path tree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-cost shortest path tree algorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.

节点自私问题是目前应用层组播技术面临的挑战之一.自私节点可能有意或者无意地停止转发某些数据包，导致流媒体质量下降.为了解决应用层组播中节点自私性问题，提出了一种利他驱动的应用层组播，简称ADALM机制.ADALM根据一个节点对其他节点的转发贡献，计算出该节点的利他值；基于利他值构造组播树，使得利他值较大的节点位于树的较高层.和本领域其他研究相比，ADALM在利他值计算和组播树构造方面均有创新：首先，利他值基于父亲节点和孩子节点的反馈，使得系统可以有效地检测出自私节点；节点无需发送额外的探测包去测量其邻居节点的服务质量；在组播树的构造和维护过程中，仅需要调整O(lg N)个节点；最后，利他值计算和组播树构造采用分布式方法来实现.仿真结果表明，即使存在一定比例的自私节点，ADALM也能构造一棵高性能的组播树，并且具有较低的控制负荷.

在没有辅助机制的条件下，非结构化P2P网络资源定位技术的效率比较低，很难同时获得较低的查询延迟、少量的定位成本和较高的查询命中率，为此，提出了一种基于自组织语义聚类的P2P查询路由算法SOSC.SOSC算法通过直接用节点共享资源的关键词频率向量表达节点语义，各节点均试图与最相似的节点建立邻居关系，以及以指数衰减方式传递节点语义向量，创造性地解决了对等计算环境中聚类语义的表达和传递问题，使得节点可感知周围节点的语义层次，从而使得各节点均可以语义聚类为基础进行快速路由.分析和实验均表明，SOSC算法具有较小的路由延迟、较低的查询代价和较高的查询命中率.

为了提升开放网络的通信效率、增加网络容量,研究了采用不同通信协议时无线设备的共存问题,提出一种基于开放网络的分布式动态频谱分配算法.该算法通过按轮次调整各个通信对端所使用的信道,将不同设备占用的工作信道均匀地分布于开放网络频谱的各个部分,提升了开放网络的总体容量.同时,探测指数的使用降低了算法运行的通信开销以及控制信令对邻居域内数据传输带来的干扰.仿真实验表明,该分配算法提升了网络整体工作效率,并从一定程度上保证了不同通信对端之间传输性能的公平性.

libpcap数据包捕获函数库提供数据包捕获、过滤等上层API，目前广泛被网络协议分析、入侵检测等数据包处理系统使用.多核、多CPU通用计算平台为数据包的高速处理提供可能，但libpcap提供的单线程机制难以充分利用多核、多CPU平台的并行计算能力.设计并实现了一种支持多线程的libpcap：libpcap-MT.libpcap-MT在内核态进行高效的数据包分发，采用无锁的多缓存队列允许多线程同时读取数据包，提供灵活的数据包分发策略，接口与libpcap保持兼容.实验结果表明，使用libpcap-MT能够快速地将现有的系统多线程化，并且具有更好的性能和可扩展性.

基于内容路由的发布/订购(Pub/Sub)技术具有异步、松散耦合和多对多通信等特点,使得能更好地应用于大规模分布式交互系统.而高效率的匹配算法、路由算法及较低的订购维护成本(规模)是实现基于内容路由的大规模Pub/Sub系统所要解决的关键问题.提出了谓词式关系(二叉树)的概念,在此基础上提出并实现了基于谓词式覆盖技术的订购算法、退订算法及启发式匹配算法(合称PRBT-*算法).通过将谓词式覆盖技术同选择性订购转发策略相结合,在提高事件匹配效率及路由效率的同时,显著降低了各级内容路由器订购规模.理论分析及大量实验对比表明,谓词式覆盖技术的引入,在降低各级内容路由器订购规模及提高算法效率和系统整体性能方面获得了良好的效果.

应用层组播无需扩充底层基础网络就可以实现较大范围的组播通信,已成为倍受瞩目的组播实现机制.但相对于传统的IP组播,应用层组播的网络延迟大,节点稳定性差,使得采用应用层组播来实现多源交互式组播应用成为一个独特的具有挑战性的问题.Thunder协议将组播结构分为核心网和外围树两部分:核心网通过Mesh-Tree结构追求快速转发以优化交互式过程;外围树允许更多的成员接收组播数据,却不会对交互过程产生影响,可提高协议的扩展性.实验表明,Thunder协议能够减小交互式应用层组播的网络延迟,具有较好的扩展性和容忍延迟变化特性,适用于各种不同规模网络.

针对现有无线传感器网络中分布式区域覆盖算法中存在覆盖空洞现象、连通性和蚕食现象等问题,提出了一个保证区域全覆盖与网络全连通的临界条件,在此基础上,提出了一个基于延迟唤醒的分布式区域覆盖算法.该算法采用分轮机制,因此不需要预先了解网络的整体拓扑结构;基于延迟唤醒的活跃节点集选择机制在保证区域全覆盖、避免出现覆盖空洞现象的同时,减少了蚕食现象的发生.仿真实验表明,与现有分布式覆盖算法相比,该算法可在满足用户区域覆盖感知需求的基础上延长网络的生命周期.

高效的消息传输机制是机会网络的核心问题.在对CRAWDAD公开发布的Trace数据进行深入分析的基础上刻画了机会网络中的消息传输路径特性.节点的相遇时间分析指出节点间存在明显的聚集性，少量的节点相遇对网络的连通性和消息传输成功率起决定性作用.为分析该特性对消息传输路径的影响，构造了机会网络的时间演化图TEG(time evolving graph)模型以计算任意节点对间的消息单拷贝最小延迟路径(single copy minimal delay path, SC-MDP).结果表明网络具有典型的“小世界”特性，即大多数消息平均通过较短路径可达目的节点.结论指出，探测并利用发生次数较少但对网络连通性具有重要影响的节点相遇进行消息转发，能够有效降低网络的传输代价和提高传输成功率.

为减少重复识别标签的时间,在动态帧时隙Aloha的RFID标签防冲突协议的基础上提出了一种自适应的动态帧时隙Aloha(adaptive dynamic framed Aloha, ADFA)的防冲突协议.在ADFA协议中,阅读器每成功识别一个标签就自适应地给该标签分配一个时隙号,该时隙号规定了标签在一次识别过程中被阅读器识别的顺序，若当前识别过程中待识别的标签与上一次识别过程中的标签相比有较多的重复，ADFA协议就可以减少冲突和空时隙，从而减少标签识别时间.另外,为进一步减少ADFA协议识别标签的时间,还对其作了改进,在改进的ADFA协议中,提出了一种低复杂度标签估计和最优帧长方案.理论分析和仿真结果均表明,ADFA协议在重复识别标签时能够减少识别时间,改进ADFA协议的标签估计方法能够减少计算复杂度,而其最优帧长方案能使系统的吞吐量得到提高.

近10年来，布尔可满足性(SAT)求解技术飞速发展，并已经成功应用于模型检验、定理证明等领域，特别是在限界模型检验(BMC)中取得了明显的进展，然而，由于命题逻辑公式的长度随系统规模指数倍增长，基于SAT的模型检验仍然存在状态空间爆炸问题.带量词的布尔公式(QBF)作为SAT公式的自然扩展，具有紧凑的空间结构、更强大、更直观的表达能力，能够简洁地描述模型检验中的公式.基于QBF的模型检验有希望缓解状态空间爆炸问题，成为当前研究的一个热点.总结了当前主流的QBF求解算法及常用的优化技术，指出了该领域中值得关注的新趋势.

处理海量和高维数据已经成为设计离群点算法面临的重要任务和挑战,针对海量数据的特点提出一种基于网格和密度的增量式离群点挖掘算法IGDLOF,算法的基本思想为:采用网格的七元组信息减少数据维数和数量,利用增量更新减少内存需求.通过代表点过滤相应的主体数据,先判断再进行近似密度计算的方法减少计算量,降低算法的复杂度.通过在真实和仿真数据集的测试表明,IGDLOF增量算法可与LOF算法保持相同的精确度,而执行效率得到显著的提高.

针对OWL-S语义Web服务自动组合问题,提出了一种基于描述逻辑(DL)规则的建模和组合方法.将ServiceProfile中的原子服务及其输入、输出参数分别建模DL中角色和概念,将概念间上下位关系和ProcessProfile中组合流程模型建模为DL规则,以一种统一的方式刻画语义Web服务的静态功能语义和动态交互特征;提出了刻画顺序服务组合的DL规则链和描述Split+Join结构的服务组(WSC)模型,将并发服务组合转为基于WSC的顺序组合,将语义Web服务组合归结为WSC和DL规则链发现过程.与已有的方法相比,该方法将语义Web服务组合问题统一在DL规则的框架下,弥补了基于DL无法描述Web服务动态特征的缺陷,避免了Petri网推理和谓词演算等进行Web服务组合时限于命题逻辑层面无法充分利用语义信息的问题,也克服了基于智能规划的组合方法限于顺序组合的问题.

计算机博弈是人工智能领域中的热点研究课题.传统计算机博弈模型使用极大极小搜索与评估函数相结合的方式,棋力高低依赖于搜索的深度.在计算性能较低的平台上,搜索深度加深会延长反应时间.因此,提出了一种应用不平衡学习技术使用专家谱训练分类器的机器博弈解决方案,反应时间只相当于一层搜索,且更能体现学习的特性.使用3种经典的不平衡学习方法训练神经网络,并对结果进行了比较.验证了使用分类器模拟中国象棋策略的可能性,以及不平衡学习技术在该策略建模过程中起到的关键作用.

受拟态物理学方法的启发,就物理个体与理想粒子的特征异同问题,通过建立拟态物理学方法与基于种群优化算法的映射关系,设计出一种面向全局优化函数的拟态物理学算法框架.这是一种基于群体的随机优化算法,每个样本解被看作一个具有质量、速度和位置属性的物理个体,个体质量是用户定义的有关其目标适应值的函数,个体的适应值越好质量就越大,则个体间的虚拟作用力就越大.利用牛顿万有引力定律定义了个体之间的虚拟作用力,制定了个体之间的引/斥力规则,使得适应值较好个体吸引适应值较差个体,适应值较差个体排斥适应值较好个体,最好个体则不受其他个体的吸引或排斥.该方法利用这种引/斥力规则使得整个种群向更好的搜索区域移动.实验结果表明该算法的有效性.

提出了基于赋权粗糙隶属度的文本情感分类方法.该方法将特征倾向强度引入到文本的向量空间表示法中,建立了基于二元组属性(特征,特征倾向强度)的文本表示模型.提出了基于情感倾向强度序的属性离散化方法,将特征选择寓于离散化过程,达到数据降维的目的.利用特征倾向强度,定义了赋权粗糙隶属度,用于新文本的情感分类.在真实汽车评论语料上,与支持向量机分类模型进行比较实验表明,基于赋权粗糙隶属度的文本情感分类方法在对数据进行一定程度的压缩后仍表现出较好的分类性能.

基于Jarecki和Shmatikov的带承诺加密电路技术和Pedersen的可验证门限秘密共享方案,提出了一种新的适用于恶意环境的移动代码保护协议.新协议使用一组服务器来代理部分零知识证明过程并共享密钥.当诚实的服务器多于2/3时,新协议:1)能同时保护输入输出的安全,较现有协议有更高安全性;2)适用于无交互的移动代码环境;3)使得发起者无需和执行者交互就能验证移动代码的正确性,从而避免恶意发起者使用恶意代码来破坏执行者的安全性;4)使得发起者和执行者能公平地得到正确的输出.

软件需求模型及其检测是软件需求工程中的重要工作.在分析现有需求建模方法和软件行为相关研究的基础上,对将软件行为概念引入需求模型进行了详细的阐述,提出一个面向软件行为的需求模型描述语言BDL(behavior description language),定义了它的语法、语义;讨论了CCS(calculus of communication system)与BDL的转换关系,构造了BDL到CCS的转换函数M;给出了需求模型的系统一致性、系统安全性、行为可信性及行为非终止性等4种系统特性的时序逻辑描述;最后用模型验证工具CWB(Concurrency WorkBench)对BDL描述的具体实例进行验证分析.

动态网格环境中用户截止时间保障是工作流调度问题的一个挑战.利用随机服务模型来描述网格资源的动态处理能力及其动态负载压力，提出了截止时间满意度的概念和工作流截止时间满意度的计算方法.将以DAG图形式表示的任务执行关系转换为以数值表示的任务执行优先级，并根据最大截止时间满意度优先的思想，确定执行工作流子任务的候选资源；将工作流全局截止时间划分问题描述为一个约束下的非线性规划问题并通过已有方法求解该问题，提出了一种截止时间满意度增强的工作流调度算法(DSESAW).仿真实验采用实际网格应用和系统数据来验证所提出算法的性能表现，实验结果表明新算法在网格环境的自适应性和用户截止时间保障方面优于其他两种实际网格系统中的调度算法.

基于XSLT技术的SBML与其他生物建模语言之间的转换方法存在无法保证转换结果的确定性、语法正确性及不能满足模型转换的工业化需求等缺陷.针对以上问题,提出了利用图文法定义SBML Schema及其他生物建模语言,并且利用Triple Graph Grammar构造SBML与其他建模语言之间的转换方法.在此基础上,提出了一种基于单路径尝试条件的转换算法,该算法具有多项式时间复杂性,能够保证转换目标对象的确定性与语法正确性,给出了相关证明,并且讨论了该条件在生物模型转换中的适用性.与传统方法相比,该方法利用可视化方法实现转换,简化了定义过程;无需动态检查转换过程,只要转化规则正确即可保证转换结果正确;同时支持扩增传播以及模型间双向转换.最后,通过Petri网与SBML之间的转换例子证实了该算法的正确性与有效性.

嵌入式系统对于功耗和面积具有很高的要求.便签存储器(scratchpad memory, SPM)与同等容量Cache相比具有能耗低、片上面积小等优点,现已成为嵌入式处理器中广泛采用的片上存储器.高效的SPM管理策略对于降低系统功耗具有重要意义.传统的SPM管理策略通过编译器采用软件方式进行.随着移动设备及网络互联设备的发展,嵌入式程序的部署方式已趋于多样化,致使传统基于程序特征分析（profiling）的SPM管理方式在某些方面存在局限.提出了一种软硬件结合的基于随机采样（random sampling）的动态SPM管理策略,通过实时监控程序访存特征等手段在运行时动态预测核心工作集（core working set）.该方法区别于传统方法之处在于无需依赖profiling信息和编译器进行SPM管理,而通过跟踪程序运行时访存动态特征指导SPM管理.实验表明,该方法可以充分发挥SPM在功耗、面积等方面的优势;通过与一种经典的SPM管理策略相比,所提出的方法在保证系统性能不降低的前提下,提高了SPM管理的灵活性、通用性.

结构脆弱性是大规模分布式系统的典型脆弱性类型之一.针对大规模分布式系统实体间复杂的依赖关系和冗余备份机制，构建了实体拓扑模型.该模型采用简单有向图描述实体间依赖关系，采用故障容忍机制刻画节点间的冗余关系，并引入权值刻画节点或边失效对于业务流程的影响.在此基础上，提出了基于权值的大规模分布式系统结构脆弱性分析算法，该算法通过权值计算和基于故障传递的剪枝方法发现并验证结构脆弱性.通过算法分析和实现充分验证了算法的有效性.