互联网体系结构评估模型、机制及方法研究综述
摘要：互联网体系结构评估模型是推动互联网体系结构持续发展的理论支撑，它可以为运营商提供网络体系结构设计的相关建议，从而使运营商可选取最适合的协议或机制构建符合各种应用需求的互联网体系结构．随着互联网应用日趋多样化，互联网的安全性、稳定性、移动性等面临越来越大的挑战．互联网体系结构的演进已经成为学术界和工业界的共识，面向现有体系结构问题的修补策略以及革命式的体系结构方案不断被提出，借鉴前者的稳定性和后者的创新性，我们提出了一种基于演进式的互联网体系结构发展思路．为了更好地了解各种互联网体系结构发展方案，近年来，研究人员分别从协议、框架等不同方面对体系结构的服务能力、发展能力和安全能力进行了评估，互联网体系结构评估方法已经成为未来互联网体系结构研究的一大热点．文中介绍了与互联网体系结构发展密切相关的五种特性的基本评估模型，包括可服务性、可扩展性、可部署性、可演化性和可信性评估模型；归纳了用于构造互联网体系结构评估模型的机制，重点讨论了效用机制在这五类基本评估模型中的应用；并对用于实现互联网体系结构评估的若干方法进行了总结．基于上述讨论，文中最后从互联网体系结构的内在特性和外在特性出发，提出了一种基于适应能力的互联网体系结构可演进性评估系统，并对互联网体系结构评估领域的发展进行了展望．无线传感器网络具有跟踪质量保证的节点选择算法
摘要：目标跟踪广泛地应用于无线传感器网络的各个领域．该文研究无线传感器网络目标跟踪中的节点选择问题，提出了具有跟踪质量保证的跟踪节点选择算法．该算法在保证给定目标跟踪可靠性要求的同时对网络生存期进行优化．文中首先分析了影响传感器节点生存期的3个因素，包括节点感知数据的可靠性、节点剩余能量以及节点通信和采样的能量消耗．在此基础上建立节点生存期函数，在满足用户给定目标跟踪可靠性要求的前提下选择使网络生存期最大化的节点参与目标跟踪．实验结果表明该文所提出的节点选择算法可以有效延长网络生存期．基于指数上鞅的统计端到端时延分析
摘要：借助有效的端到端时延分析可实现大规模网络的QoS控制，运用统计网络演算理论中最小加代数的卷积运算规则计算端到端时延界日益引起人们的重视．随着网络规模的不断扩大，统计端到端时延界应同时具有良好的可扩展性和一定的紧致性，而目前满足这一要求的理论成果还比较少．通过结合最小加代数的卷积运算规则和Doob不等式，并采用矩母函数（Moment Generating Function，MGF）对到达曲线和服务曲线进行描述，文中给出了一种基于指数上鞅的端到端时延界表达式．该时延界不仅可以线性扩展，而且数值分析结果表明，在相同假设条件下，该时延界比现有的线性时延界具有更好的紧致性．MFT^2-BGP：基于多转发树的无中断域间路由协议
摘要：BGP通过触发全局、反应式收敛应对链路或节点失效引起的拓扑变化，然而BGP协议收敛时间长、收敛过程中的瞬时失效严重降低了数据平面转发性能，难以支持关键业务流量．该文提出了容忍失效的MFT^2-BGP，通过利用路径标识符以较低的消息开销构造符合BGP策略的多转发树，使得每个AS获得多样性路径，当出现瞬时失效时，在不改变协议动态性的情况下，允许节点动态切换报文转发路径以实现无中断报文转发，通过嵌入“失效根源信息”以降低收敛时间，抑制瞬时失效以降低路由系统的扰动．通过在Internet—like拓扑上的大量实验表明，在链路失效场景中与其它协议相比，MFT^2-BGP能有效改善收敛时间，降低转发中断时间，改善路由系统稳定性．LabelCast：一种普适的SDN转发平面抽象
摘要：在互联网体系结构演进过程中试验和部署新型网络协议比较困难，基于Openflow的软件定义网络SDN提供了一种简单易行的方法．OpenFlow基于流表实现了多级流水转发处理，然而Openflow不支持对网络中计算和存储等资源的描述，因此很难支持以内容为中心的新型网络．为扩展SDN能力，提出了一种普适的转发平面抽象LabelCast，以将多态网络地址映射到定长标签．转发平面基于Label表来查找和调度弱语义的转发操作相关的指令，Cast表对网络协议语义或状态相关的服务进行组织，支持动态扩展新型服务以满足新型网络体系结构复杂的处理功能．LabelCast能够支持基于流的端到端的交换和以数据或服务为中心的非端到端的新型网络体系结构，为SDN提供了一种普适的转发平面抽象．视频解码计算复杂度的线性建模理论及在线预测方法
摘要：视频解码是一类最典型的多媒体应用，其计算量大、耗能高．现代多媒体计算平台可利用视频解码计算复杂度固有的动态变化特征来自适应地调整所需计算资源，从而节省能耗，其前提是对视频解码计算复杂度进行准确估计．作者基于解码计算复杂度与帧长之间的线性关系，提出了一种利用状态变量法对解码计算复杂度进行理论建模和在线估计的方法．与传统的直接对帧长和计算复杂度之间的输入一输出依赖关系进行建模所不同，这里将视频解码系统表征为由视频内容特征的状态变化所驱动的系统．首先从语义层面对解码器各模块的解码复杂度进行分析，并导出各模块计算复杂度与语义参数间的依赖关系模型，总解码复杂度为各子模块的复杂度之和．经过化简得到解码计算复杂度与帧长之间的线性模型，其中模型系数为上述语义参数的函数，表征了视频内容特征的状态变化，被定义为状态变量．再结合压缩视频流中相邻帧语义参数之间的相关性，将系统状态方程定义为反映视频内容变化程度的分段线性函数．根据I帧和P帧状态轨迹特性及其在压缩码流中位置属性的不同，分别进行计算复杂度在线估计：对于I帧，采用统计分析方法获得其状态变量的均值并进行在线估计；而对P帧，则是在运行过程中利用状态方程对状态变量进行实时更新和计算复杂度估计．在基于SimpleScaIar的软件仿真平台和基于DSP的嵌入式硬件平台上分别对H．264、MPEG-4压缩码流的解码计算复杂度进行在线估计，实验结果表明：对解码计算复杂度的平均估计误差在7％以内，预测精度非常高，而且状态方程更新过程简单，在线运行复杂度低，特别适用于嵌入式移动设备．一种抛物反射折射圆像的拟合方法
摘要：基于圆的摄像机标定有着无可比拟的优势．目前，虽有文献证明了圆在反射折射摄像机下的像是一条四次曲线，但由于存在遮挡，仅仅部分封闭曲线在像平面上是可见的，且通过其可见部分无法拟合圆像的方程，进而无法标定摄像机参数．因此，当摄像机位率为1且斜率为0时，作者提出了一种抛物反射折射圆像的拟合方法，为研究基于圆的摄像机标定算法奠定了基础．首先，推导出了抛物反射折射圆像需要满足的条件；其次，在这些条件基础上提出了一种抛物反射折射圆像的拟合方法；最后，利用拟合得到的抛物反射折射圆像和通过抛物镜面的投影轮廓线估计得到的摄像机主点直接计算出摄像机焦距，以此评价文中拟合方法的性能．大量的模拟实验和真实实验均验证了文中拟合方法的有效性．基于图像匹配-点云融合的建筑物立面三维重建
摘要：随着计算机技术的快速发展，基于图像的建筑物三维重建逐渐成为计算机图形学和计算机视觉领域的研究热点之一．由于建筑物图像背景复杂、序列长且杂乱无序，现有的三维重建算法存在耗时长、局部几何细节重建效果差的问题．文中针对这些不足提出了一种基于图像匹配实现点云融合的建筑物立面三维重建算法．首先寻找新添加的建筑物局部图像在原始图像集中的匹配图像，组成规模较小的图像集并重建出局部点云模型，然后通过匹配不同点云模型在同一幅图像上的投影点，找到点云模型之间的一致对应点集，接着求解点云集合之间的最佳对齐变换，实现整体和局部点云模型的融合，最终生成建筑物立面完整的三维模型．实验表明，采用文中算法进行三维重建，可以有效地减少重建时间，提高重建精度．SAM：一种容错的末级缓存可扩展地址映射方法
摘要：随着半导体工艺进步，多核处理器超过60％的片上面积由片上缓存占据．由于特征尺寸缩小及供电电压下降，片上缓存较以往更容易发生错误．缓存错误包括可恢复的软错误（softerror）及不可恢复的不稳定位（erraticbit）失效．传统容错技术主要研究针对单个缓存模块的保护．当缓存中包含成百上千个模块时，即使单个缓存模块出错的概率很低，系统中有一个或多个缓存出错的概率也相对较高．文中提出可扩展地址映射（SAM）方法，支持对可缓存地址空间灵活高效的映射，提高末级缓存的可靠性．通过对末级缓存地址空间进行重构，只要有末级缓存模块可以工作，SAM就能够保证系统正确运行．SAM可应用于共享或集群缓存组织方式．文中提出的算法能根据末级缓存中出错缓存模块的数目变化，动态调整集群缓存组织方式下的集群大小．实验结果表明，SAM方法可在多种出错环境下保证系统功能正确，且性能平滑下降．KFUR：一个新型内核扩展安全模型
摘要：保障内核扩展的安全性对操作系统具有重要意义．当前存在大量针对内核函数使用规则的攻击，内核扩展中也存在大量违反内核函数使用规则的错误，因此针对内核函数使用规则的安全性检测十分必要．虽然存在多种提高内核扩展安全性的方法，但很少有方法对内核函数的使用规则进行安全性检测．文中设计了KFUR（Kernel Function Usage Rule）内核扩展安全模型系统，用于在运行时检测内核扩展调用内核函数是否遵守内核函数使用规则．如果内核扩展调用内核函数满足模型安全运行条件，则允许对该内核函数进行调用，否则将错误报告给操作系统内核并终止该内核扩展的运行．文中所述研究在Linux操作系统上对KFUR安全模型系统进行实现，并将其运用于e1000网卡驱动、SATA硬盘驱动和HDA声卡驱动内核扩展．安全性评测表明安全模型系统能够对内核函数使用规则进行安全性检测，性能评测表明安全模型系统带来的开销很小．大规模层次分类问题研究及其进展
摘要：随着信息技术的发展，互联网数据急剧增长．为了有效地组织和管理这些海量网页信息，通常按照一个大规模的概念或主题类别层次对网络上的信息进行分类，以更好地搜索和访问这些网络资源．在这个过程中，大规模层次分类问题研究如何将互联网上的网页文档准确地分到类别层次中的各个类别．该文对大规模层次分类问题进行了分析．首先，给出了大规模层次分类问题的定义，分析了大规模层次分类问题的求解策略；其次，对大规模层次分类问题的求解方法加以分类，在分类基础上，介绍了各种典型的求解方法并进行了对比；最后总结了各种大规模层次分类问题求解方法并指出了未来的研究方向．基于差分演化算法的软子空间聚类
摘要：软子空间聚类算法的性能主要取决于其目标函数和搜索策略．文中提出了一种基于差分演化算法的软子空间聚类算法DESC．首先，设计了一个结合模糊加权类内相似性和界约束权值矩阵的新目标函数．然后，提出了新的隶属度计算方法．最后，引入了一种有效的全局搜索算法～复合差分演化算法，并运用该算法优化新目标函数和搜索子空间中的聚类．实验表明，新目标函数和复合差分演化算法的引入有效地提高了软子空间聚类算法的性能，新算法较已有软子空间聚类算法有明显优势．连续属性完全贝叶斯分类器的学习与优化
摘要：针对连续属性朴素贝叶斯分类器不能有效利用属性之间的条件依赖信息，而依赖扩展又很难实现属性条件联合密度估计和结构学习协同优化的问题，文中在使用多元高斯核函数估计属性条件联合密度的基础上，建立了具有多平滑参数的连续属性完全贝叶斯分类器，并给出将分类准确性标准与区间异步长划分完全搜索相结合的平滑参数优化方法，再通过时序扩展构建了动态完全贝叶斯分类器．我们使用UCI机器学习数据仓库中连续属性分类数据和宏观经济数据进行实验，结果显示，经过优化的两种分类器均具有良好的分类准确性．基于最小圆覆盖区域划分的索引过滤算法
摘要：过滤算法设计是信息内容安全处理系统中的一个重要环节，过滤速度成为衡量过滤系统性能的首要因素．索引结构是处理大规模数据的一种有效方式，但目前索引方法都是针对特定检索领域而设计，在实际过滤应用中，并不能满足过滤实时性需求．为了加快信息过滤中数据查询的判定速度，文中提出一种基于最小圆覆盖的区域划分方法，构建了适合过滤的索引结构：F—tree．该算法充分考虑实际过滤环境中正例（正常信息）多、反例（敏感信息）少的非平衡数据分布特性，利用最小圆覆盖划分方法得到最大否定判断区域．在查询阶段，正例以最大概率落入否定区域，根据否定性判定原理可以对正例快速否定判定，从而加快整体查询的判定速度．实验表明，与现有算法相比，所提出的算法减少了查询中的距离计算次数，有效提高了过滤查询性能．多维代价图模型上最优路径查询问题的研究
摘要：近年来，图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系．最短路径查询是图研究领域中一类非常重要的查询并有着广泛的应用．然而，目前大多数关于最短路径的查询都是定义在单代价（权重）图模型下的．现实世界中，基于单一代价所选择的最短路径并不明智，比如路程最短的路径需要花费极高的费用．该文中，作者介绍了多维代价图模型的概念，并给出了多维代价图模型下基于函数的最优路径的定义．现有的计算最短路径的方法都利用了最短路径的子路径最优的性质：最短路径上的任意两点间的子路径是这两点的最短路径．因此，在计算最短路径的过程中，对访问过的每个顶点，只需保留起点到该点的最短路径即可．不幸的是，多维代价图模型下，当评分函数是非线性的时候，子路径最优的性质并不成立．因此，目前的方法均不能应用于多维代价图模型下基于函数的最优路径查询问题．该文给出了一个best—first search分支界限法并给出3种优化策略．进一步，给出了一个顶点过滤算法，该算法能从图中过滤掉大部分不属于最优路径的顶点．最后，用真实数据集上的实验验证了算法的有效性．劣质数据库上阈值相似连接结果大小估计
摘要：劣质数据普遍存在于现代数据管理系统中，严重影响了数据的质量，从而降低了数据的实用性以及数据的价值，这为数据管理带来了新的挑战．当前，已经有不少管理劣质数据的数据模型被提出，实体关系数据模型是其中一种，其中每条元组表示一个现实世界中的实体．该模型允许劣质数据的存在，给出了衡量数据质量的方法，并且可根据用户对结果质量的需求给出达到一定质量的查询结果．鉴于该模型的特点，传统的查询代价估计方法不再适用，需要新的代价估计技术．文中研究如何估计连接操作结果的大小，提出了在应用局部敏感Hash算法对属性值聚类的基础上，再进行采样估计的方法，并且在聚类过程中考虑数据质量对查询结果的影响．与传统随机采样方法对比，实验结果表明文中估计方法有更好的准确性．一种基于不变量的工作流协同模型分解方法
摘要：现代企业计算的业务过程越来越复杂，有很多分散且相对独立的组织机构，为了协同来自不同组织的业务过程，文中提出一种IOPN模型（面向交互的Petri网）用于描述跨组织的工作流协同，该模型包含组织内的过程模型和组织间的交互关系．为了确保IOPN模型能够被正确地执行，文中提出IOPN模型的弱合理性（relaxed soundness）作为IOPN模型的正确性标准之一．IOPN模型是一种复合模型，其规模一般较大，采用基于状态空间的分析方法，容易产生状态空间爆炸问题，为此文中提出基于不变量的分解方法，能够将一个弱合理的无回路10PN模型分解为一组顺序图，并提出相关定理：一个无回路IOPN模型是弱合理的当且仅当其可以被分解为一组合法的顺序图．可重写Petri网：位置可重写及性质分析
摘要：针对Petri网对动态系统重构形式化描述和建模能力的不足，提出了可重写Petri网和位置可重写Petri网的基本概念．分析了位置可重写Petri网保持有界性、保守性、可重复性及活性等性质．给出了位置可重写Petri网保持活性的一个充要条件．证明了共享合成Petri网是位置可重写Petri网的一个实例，建立了退化的位置可重写Petri网模拟共享合成Petri网的算法．所得结果能够为动态重构系统的Petri网形式化建模提供理论方法，为大规模动态分布式系统的形式化验证提供有效途径．