2013年 第50卷 第5期
摘要：
在传感网和物联网的大力发展过程中，覆盖问题始终是该领域关注的核心问题.目前在诸多应用中，网络部署受各类影响因素的制约以及传感设备自身条件的限制，无法实现监测区域的完全覆盖.但如果借助某些特定的移动设备并按照有针对性的移动策略实施移动覆盖，就可以实现监测区域内的补全覆盖.基于此应用提出了一类新的覆盖问题——移动全覆盖问题，即在网络稀疏覆盖的环境下，利用移动节点的移动覆盖实现监测区域的全覆盖问题.针对该问题提出了分而治之的节点移动策略.首先，按照移动节点通信半径将整个监测区域划分成多个子区域；其次，以四叉树分层遍历的策略作为移动节点在子区域间的移动方案；最后，针对每个子区域内静态节点的覆盖状况制定相应的区域内的移动策略.实验结果表明采用本文提出的移动策略可以实现在移动节点移动较小距离的前提下达到整个区域的全覆盖，从而解决了稀疏网络环境下的全覆盖问题.
在传感网和物联网的大力发展过程中，覆盖问题始终是该领域关注的核心问题.目前在诸多应用中，网络部署受各类影响因素的制约以及传感设备自身条件的限制，无法实现监测区域的完全覆盖.但如果借助某些特定的移动设备并按照有针对性的移动策略实施移动覆盖，就可以实现监测区域内的补全覆盖.基于此应用提出了一类新的覆盖问题——移动全覆盖问题，即在网络稀疏覆盖的环境下，利用移动节点的移动覆盖实现监测区域的全覆盖问题.针对该问题提出了分而治之的节点移动策略.首先，按照移动节点通信半径将整个监测区域划分成多个子区域；其次，以四叉树分层遍历的策略作为移动节点在子区域间的移动方案；最后，针对每个子区域内静态节点的覆盖状况制定相应的区域内的移动策略.实验结果表明采用本文提出的移动策略可以实现在移动节点移动较小距离的前提下达到整个区域的全覆盖，从而解决了稀疏网络环境下的全覆盖问题.
摘要：
提高小区边缘用户性能是蜂窝移动通信系统的经典难题.下一代蜂窝移动通信系统3GPP LTE通过有效的小区间干扰协调以及频率资源分配来改善小区边缘用户性能.提出一种自适应软频率复用算法，根据系统负载情况自适应地为各小区分配主、副载波及其发射功率，在实现系统吞吐量优化的同时保证小区中心和边缘区域速率需求.算法首先通过穷尽搜索和贪婪递减策略，获得单小区最优资源分配，然后在不同小区间迭代执行单小区算法直到系统吞吐量不变为止.仿真结果表明，算法通过多次迭代后，系统吞吐量保持不变并输出一种优化的资源分配方案.与同类频率分配算法相比，可以有效提升小区边缘用户的吞吐量，同时获得更高的系统容量，更适用于高速率的LTE系统.
提高小区边缘用户性能是蜂窝移动通信系统的经典难题.下一代蜂窝移动通信系统3GPP LTE通过有效的小区间干扰协调以及频率资源分配来改善小区边缘用户性能.提出一种自适应软频率复用算法，根据系统负载情况自适应地为各小区分配主、副载波及其发射功率，在实现系统吞吐量优化的同时保证小区中心和边缘区域速率需求.算法首先通过穷尽搜索和贪婪递减策略，获得单小区最优资源分配，然后在不同小区间迭代执行单小区算法直到系统吞吐量不变为止.仿真结果表明，算法通过多次迭代后，系统吞吐量保持不变并输出一种优化的资源分配方案.与同类频率分配算法相比，可以有效提升小区边缘用户的吞吐量，同时获得更高的系统容量，更适用于高速率的LTE系统.
摘要：
基于图论方法提出了一种新的证据信任模型(graph theory based evidential trust model, GTETM)，解决了现有证据信任模型中普遍存在的在信任聚合过程中缺少对信任链之间依赖关系的有效处理等引起的模型性能下降问题.同时，GTETM在建模实体的信任度时区分实体的服务信任度与反馈信任度，并在证据理论框架下提出两种不同的信任传递方法，增强了模型抵抗恶意推荐攻击的能力.仿真实验表明，与已有信任度量模型相比，GTETM具有更强的抑制策略欺骗及共谋行为的能力，在信任度量准确性方面也有较大提高.
基于图论方法提出了一种新的证据信任模型(graph theory based evidential trust model, GTETM)，解决了现有证据信任模型中普遍存在的在信任聚合过程中缺少对信任链之间依赖关系的有效处理等引起的模型性能下降问题.同时，GTETM在建模实体的信任度时区分实体的服务信任度与反馈信任度，并在证据理论框架下提出两种不同的信任传递方法，增强了模型抵抗恶意推荐攻击的能力.仿真实验表明，与已有信任度量模型相比，GTETM具有更强的抑制策略欺骗及共谋行为的能力，在信任度量准确性方面也有较大提高.
摘要：
针对动态安全策略在策略表达、判决和验证等方面具有的重要意义，提出了一种可用于动态安全策略表达、决策和验证的逻辑系统SSML.首先，给出了SSML逻辑系统的语法和语义，并且证明了一般意义上的SSML逻辑系统查询评估问题是不可判定的，从而表明不存在通用的SSML安全策略语义查询评估算法.其次，研究SSML子语言特性，发现两类语法受限的SSML动态安全策略——NDel型安全策略和TDel型安全策略.虽然前者不允许在安全策略中出现删除规则，后者只允许完全信任的管理人员执行删除规则，但它们的查询评估问题是可判定的，并且分别构造出它们的查询评估算法—— OLDTE和OLDTT.最后，通过实例说明如何使用OLDTE或OLDTT实现安全策略验证，从而证明这两类动态安全策略具有广泛的应用前景，对动态安全策略及其安全性分析方法的研究具有重要意义.
针对动态安全策略在策略表达、判决和验证等方面具有的重要意义，提出了一种可用于动态安全策略表达、决策和验证的逻辑系统SSML.首先，给出了SSML逻辑系统的语法和语义，并且证明了一般意义上的SSML逻辑系统查询评估问题是不可判定的，从而表明不存在通用的SSML安全策略语义查询评估算法.其次，研究SSML子语言特性，发现两类语法受限的SSML动态安全策略——NDel型安全策略和TDel型安全策略.虽然前者不允许在安全策略中出现删除规则，后者只允许完全信任的管理人员执行删除规则，但它们的查询评估问题是可判定的，并且分别构造出它们的查询评估算法—— OLDTE和OLDTT.最后，通过实例说明如何使用OLDTE或OLDTT实现安全策略验证，从而证明这两类动态安全策略具有广泛的应用前景，对动态安全策略及其安全性分析方法的研究具有重要意义.
摘要：
依据图像信源区域平稳性质，分析LSB匹配隐写对图像区域统计特性的影响，提出一种基于区域随机性特征的隐写分析方法.运用分块处理划分图像区域，对各区域像素进行Hilbert扫描并提取像素最低有效位比特序列，进而将比特序列作异或运算所得到的参量定义为区域随机性度量指标，最后统计并分析区域随机性指标直方图，提取直方图信息熵、特殊取值及原点矩3类特征，结合Fisher线性分类器对载体、载密图像进行判别.实验结果表明，该方法在不同图像库和不同嵌入率条件下对LSB匹配隐写均表现出良好的检测性能，与现有典型检测算法相比其检测性能具有明显提高.
依据图像信源区域平稳性质，分析LSB匹配隐写对图像区域统计特性的影响，提出一种基于区域随机性特征的隐写分析方法.运用分块处理划分图像区域，对各区域像素进行Hilbert扫描并提取像素最低有效位比特序列，进而将比特序列作异或运算所得到的参量定义为区域随机性度量指标，最后统计并分析区域随机性指标直方图，提取直方图信息熵、特殊取值及原点矩3类特征，结合Fisher线性分类器对载体、载密图像进行判别.实验结果表明，该方法在不同图像库和不同嵌入率条件下对LSB匹配隐写均表现出良好的检测性能，与现有典型检测算法相比其检测性能具有明显提高.
摘要：
绝大部分的角色挖掘方法都是从无到有地进行构建，所有角色都是新挖掘出来的，而没有考虑事先已经存在的角色集合.而且从已有角色集合的方法中提出的相似度定义均不满足交换律；提出一种混合角色挖掘方法，以top-down方法预先定义部分角色，以bottom-up方法挖掘候选角色集合.定义加权结构复杂度并以此作为系统状态优化的指标.给出满足交换律的相似度定义，以此作为与原有角色集近似度量的指标，并提出相似度计算算法.在此基础上提出最小扰动混合角色挖掘的定义和算法；分析算法复杂度并作出性能评估，评估结果表明算法准确率和效率均有明显提高.
绝大部分的角色挖掘方法都是从无到有地进行构建，所有角色都是新挖掘出来的，而没有考虑事先已经存在的角色集合.而且从已有角色集合的方法中提出的相似度定义均不满足交换律；提出一种混合角色挖掘方法，以top-down方法预先定义部分角色，以bottom-up方法挖掘候选角色集合.定义加权结构复杂度并以此作为系统状态优化的指标.给出满足交换律的相似度定义，以此作为与原有角色集近似度量的指标，并提出相似度计算算法.在此基础上提出最小扰动混合角色挖掘的定义和算法；分析算法复杂度并作出性能评估，评估结果表明算法准确率和效率均有明显提高.
摘要：
为了有效过滤数据流中的有害信息，通常在数据流上注册大量查询，同时构建过滤器来计算这些查询.在多媒体流环境中，查询和过滤器常常是一种“多对多”的连接，也就是说，对于单个过滤器的计算可能会同时给出多个查询的结果.在这种情况下，如何排序所有的过滤器来获得最小的过滤代价变得非常重要.对于过滤器的排序一般依赖于3个指标：过滤器本身的执行代价c、过滤器连接的查询数目p以及过滤器对于随机样本判断为真的概率s.目前基于贪心的排序算法虽然在一定程度上给出了近似最优的结果，但是还存在以下两个问题：1) 指标s只是简单依据经验值设定，不能随着流的变化而自适应变化；2)将3个指标融合成一个代价函数进行排序，而没有深入分析各个指标之间的关系.考虑到以上方法存在的不足，提出一个层次排序算法(adaptive hierarchal ordering, AHO)来高效地过滤多媒体数据流.该算法首先依据过滤器的指标c和p进行分类，然后再在每个类别上按照s进行二次排序.在真实多媒体流环境中的过滤结果证明: AHO可以在不降低准确度的情况下，自适应调整过滤器顺序，其性能优于已有的贪心排序算法.
为了有效过滤数据流中的有害信息，通常在数据流上注册大量查询，同时构建过滤器来计算这些查询.在多媒体流环境中，查询和过滤器常常是一种“多对多”的连接，也就是说，对于单个过滤器的计算可能会同时给出多个查询的结果.在这种情况下，如何排序所有的过滤器来获得最小的过滤代价变得非常重要.对于过滤器的排序一般依赖于3个指标：过滤器本身的执行代价c、过滤器连接的查询数目p以及过滤器对于随机样本判断为真的概率s.目前基于贪心的排序算法虽然在一定程度上给出了近似最优的结果，但是还存在以下两个问题：1) 指标s只是简单依据经验值设定，不能随着流的变化而自适应变化；2)将3个指标融合成一个代价函数进行排序，而没有深入分析各个指标之间的关系.考虑到以上方法存在的不足，提出一个层次排序算法(adaptive hierarchal ordering, AHO)来高效地过滤多媒体数据流.该算法首先依据过滤器的指标c和p进行分类，然后再在每个类别上按照s进行二次排序.在真实多媒体流环境中的过滤结果证明: AHO可以在不降低准确度的情况下，自适应调整过滤器顺序，其性能优于已有的贪心排序算法.
摘要：
XML作为半结构化数据模型的代表，其文档较大，存储动态有序树时需要较多空间成为其明显的缺点，对XML文档进行二进制的编码压缩可以有效地减少存储空间.提出了一种不仅可以对有序树进行空间高效存储，又可以实现有序树的动态化操作的封装包结构.此结构通过将有序树的二进制编码段分段处理的方法，减少了修改量.并通过三重定位的方法快速选定要修改的封装包.针对有序树动态化后出现的节点意义丢失的问题，提出了对树进行辅助描述的高效节点序号表，通过节点序号表可以记录每个节点的内容及意义，进而补充了二进制编码只能表示树结构的缺点.并通过建立有效的序号修改表对其进行快速高效的更新.通过设计对动态树的各种常用操作，并计算出各种操作的空间及时间复杂度，表明了通过此结构可以实现动态有序树的空间高效存储.
XML作为半结构化数据模型的代表，其文档较大，存储动态有序树时需要较多空间成为其明显的缺点，对XML文档进行二进制的编码压缩可以有效地减少存储空间.提出了一种不仅可以对有序树进行空间高效存储，又可以实现有序树的动态化操作的封装包结构.此结构通过将有序树的二进制编码段分段处理的方法，减少了修改量.并通过三重定位的方法快速选定要修改的封装包.针对有序树动态化后出现的节点意义丢失的问题，提出了对树进行辅助描述的高效节点序号表，通过节点序号表可以记录每个节点的内容及意义，进而补充了二进制编码只能表示树结构的缺点.并通过建立有效的序号修改表对其进行快速高效的更新.通过设计对动态树的各种常用操作，并计算出各种操作的空间及时间复杂度，表明了通过此结构可以实现动态有序树的空间高效存储.
摘要：
Top-k相互Skyline查询返回相互Skyline查询中的前k个对象.这种查询是数据分析者寻找有意义对象进行决策支持的一种重要直觉工具.然而,这种查询还没有引起研究社区足够的注意力.介绍了几种新颖的算法,包括Topk-TBBS,Topk-dMBBS,Topk-wMBBS.主要的思想是信息重用和高效的修剪策略.特别地,Topk-wMBBS算法由于完全重用了搜索中的节点信息,并利用了最好优先BF搜索策略.因而它获得了最好的性能.同时证明了该算法有最优的I/O访问效率.最后,使用了2个真实数据集和4个服从不同分布的合成数据集进行了集中实验.实验结果表明,提出的算法无论是变化参数k的大小、数据集的尺寸和Cache尺寸都是有效的,且具有很高的效率,尤其Topk-wMBBS具有最小的I/O访问次数.
Top-k相互Skyline查询返回相互Skyline查询中的前k个对象.这种查询是数据分析者寻找有意义对象进行决策支持的一种重要直觉工具.然而,这种查询还没有引起研究社区足够的注意力.介绍了几种新颖的算法,包括Topk-TBBS,Topk-dMBBS,Topk-wMBBS.主要的思想是信息重用和高效的修剪策略.特别地,Topk-wMBBS算法由于完全重用了搜索中的节点信息,并利用了最好优先BF搜索策略.因而它获得了最好的性能.同时证明了该算法有最优的I/O访问效率.最后,使用了2个真实数据集和4个服从不同分布的合成数据集进行了集中实验.实验结果表明,提出的算法无论是变化参数k的大小、数据集的尺寸和Cache尺寸都是有效的,且具有很高的效率,尤其Topk-wMBBS具有最小的I/O访问次数.
摘要：
当T为t-模时，基于模糊取大和T的模糊联想记忆网络(FAM)存在局限性，当T为三角模，是t-模的广义形式，将这种FAM推广成基于Max-T的模糊联想记忆网络Max-T FAM.则Max-T FAM实现了从一个向量空间到另一向量空间的映射，从Max-T FAM的值域角度，分析了它的存储能力，并建立了一个三角模T的伴随蕴涵算子新概念，利用该伴随蕴涵算子，在无需T为连续的、严格增等条件下，提出了Max-T FAM的一个简洁的通用离线学习算法和通用在线学习算法.从理论上严格证明了只要Max-T FAM能完整可靠地存储所给的多个模式对，则这两种算法都能轻易找到使得网络能完整可靠存储这些模式对的所有连接权矩阵的最大者.最后，用实验证明了Max-T FAM模型和所提出的学习算法的有效性.
当T为t-模时，基于模糊取大和T的模糊联想记忆网络(FAM)存在局限性，当T为三角模，是t-模的广义形式，将这种FAM推广成基于Max-T的模糊联想记忆网络Max-T FAM.则Max-T FAM实现了从一个向量空间到另一向量空间的映射，从Max-T FAM的值域角度，分析了它的存储能力，并建立了一个三角模T的伴随蕴涵算子新概念，利用该伴随蕴涵算子，在无需T为连续的、严格增等条件下，提出了Max-T FAM的一个简洁的通用离线学习算法和通用在线学习算法.从理论上严格证明了只要Max-T FAM能完整可靠地存储所给的多个模式对，则这两种算法都能轻易找到使得网络能完整可靠存储这些模式对的所有连接权矩阵的最大者.最后，用实验证明了Max-T FAM模型和所提出的学习算法的有效性.
摘要：
边缘划分问题是数据分析的核心问题之一.针对晶体数据的边缘分类问题，引入同调论的思想，提出了胞腔同调边缘算法和正则胞腔同调边缘学习算法及上同调边缘学习算法，并将其应用于晶体结构预测和分类.鉴于晶体数据满足对称群的基本性质，引用同调代数的方法从机器学习的角度来研究数据的边缘分类问题.为了从不同角度构造分类模型，先从相对同调边缘展开为局部同调和定向同调，再深入到上同调边缘算法和腔胞同调边缘算法，由着重系数定理扩展到正则胞腔同调，进而延伸至相对流形.仿真结果表明了算法的有效性.
边缘划分问题是数据分析的核心问题之一.针对晶体数据的边缘分类问题，引入同调论的思想，提出了胞腔同调边缘算法和正则胞腔同调边缘学习算法及上同调边缘学习算法，并将其应用于晶体结构预测和分类.鉴于晶体数据满足对称群的基本性质，引用同调代数的方法从机器学习的角度来研究数据的边缘分类问题.为了从不同角度构造分类模型，先从相对同调边缘展开为局部同调和定向同调，再深入到上同调边缘算法和腔胞同调边缘算法，由着重系数定理扩展到正则胞腔同调，进而延伸至相对流形.仿真结果表明了算法的有效性.
摘要：
三角曲面的降阶问题一直是CAGD领域的一个难点问题，近年来受到关注.对L2范数下多三角Bézier曲面在拼接边界满足GC\+1约束的降阶逼近问题进行研究，包括:1)给出了一种L2范数下单一三角Bézier曲面的一次降多阶的逼近算法;2)对两个三角Bézier曲面在拼接边界上满足GC\+1约束的降阶逼近算法进行研究，提出一种通过调整两个三角Bézier曲面片距离拼接边界的第2排内部控制点来满足GC\+1约束的降阶逼近算法;3)研究基于调整三角Bézier曲面片内部控制点的多三角曲面片在各拼接边界满足GC\+1约束的曲面降阶算法.算法首先按照2)中的方法，确定每两个三角Bézier曲面片在公共边界满足GC\+1约束的降阶逼近所需要调整的内部控制点，然后构造blending函数.通过将每个三角Bézier曲面所对应的多组控制点进行混合，形成新的混合降阶曲面的三角Bézier格式，并在理论上证明该混合三角Bézier降阶曲面片与其周边的各降阶曲面片仍保持GC\+1约束.实验结果表明，所提方法简单实用，逼近效果好.
三角曲面的降阶问题一直是CAGD领域的一个难点问题，近年来受到关注.对L2范数下多三角Bézier曲面在拼接边界满足GC\+1约束的降阶逼近问题进行研究，包括:1)给出了一种L2范数下单一三角Bézier曲面的一次降多阶的逼近算法;2)对两个三角Bézier曲面在拼接边界上满足GC\+1约束的降阶逼近算法进行研究，提出一种通过调整两个三角Bézier曲面片距离拼接边界的第2排内部控制点来满足GC\+1约束的降阶逼近算法;3)研究基于调整三角Bézier曲面片内部控制点的多三角曲面片在各拼接边界满足GC\+1约束的曲面降阶算法.算法首先按照2)中的方法，确定每两个三角Bézier曲面片在公共边界满足GC\+1约束的降阶逼近所需要调整的内部控制点，然后构造blending函数.通过将每个三角Bézier曲面所对应的多组控制点进行混合，形成新的混合降阶曲面的三角Bézier格式，并在理论上证明该混合三角Bézier降阶曲面片与其周边的各降阶曲面片仍保持GC\+1约束.实验结果表明，所提方法简单实用，逼近效果好.
摘要：
由于边界区域的匹配精度是立体匹配问题的瓶颈,这里采用一种基于特征的匹配算法来重点研究场景中边界区域的匹配.首先针对立体匹配问题,提出一种基于RBF的边界提取算法,使得边界区域成为待匹配的像素点.研究像素点匹配需要满足的约束,构建相应的能量方程,接着采用Hopfield网络对能量函数进行优化来获得问题的求解.由于针对的是整个边界区域,直接将特征点输入网络会导致神经元数目过多、复杂度过高.为了降低算法复杂度,提出从视差空间上来构造网络模型.最后通过大量实验来验证算法的性能,包括标准图片、噪声图片与真实的场景图片.实验证明新算法能大大提高边界区域精度,克服了立体匹配的瓶颈,明显提高了整体区域精度,算法有很强的鲁棒性和实用性,即使在复杂情况下也能取得较好的效果.
由于边界区域的匹配精度是立体匹配问题的瓶颈,这里采用一种基于特征的匹配算法来重点研究场景中边界区域的匹配.首先针对立体匹配问题,提出一种基于RBF的边界提取算法,使得边界区域成为待匹配的像素点.研究像素点匹配需要满足的约束,构建相应的能量方程,接着采用Hopfield网络对能量函数进行优化来获得问题的求解.由于针对的是整个边界区域,直接将特征点输入网络会导致神经元数目过多、复杂度过高.为了降低算法复杂度,提出从视差空间上来构造网络模型.最后通过大量实验来验证算法的性能,包括标准图片、噪声图片与真实的场景图片.实验证明新算法能大大提高边界区域精度,克服了立体匹配的瓶颈,明显提高了整体区域精度,算法有很强的鲁棒性和实用性,即使在复杂情况下也能取得较好的效果.
摘要：
基于程序谱的错误定位技术由于其较高的定位效率已成为当前软件调试领域研究热点之一.这种技术通常根据测试覆盖信息计算程序语句发生错误的可疑度来进行错误定位.然而，这种技术会随着程序中错误数目的增多效率不断下降.鉴于此，提出了一种基于条件执行切片谱的多错误定位技术(conditioned execution slicing spectrum-based multiple fault localization, CESS-MFL)，以提高多错误定位的效率.CESS-MFL技术首先根据输入变量的谓词条件构建错误相关条件执行切片的谱矩阵，然后依次计算错误相关条件执行切片中的元素(语句或语句块)的可疑度，并生成可疑度报告.实验验证了CESS-MFL技术比当前流行的基于程序谱的Tarantula技术、基于程序切片的Intersection技术、Union技术有更高的多错误定位效率，并且可在有效的时间和空间复杂度内完成.
基于程序谱的错误定位技术由于其较高的定位效率已成为当前软件调试领域研究热点之一.这种技术通常根据测试覆盖信息计算程序语句发生错误的可疑度来进行错误定位.然而，这种技术会随着程序中错误数目的增多效率不断下降.鉴于此，提出了一种基于条件执行切片谱的多错误定位技术(conditioned execution slicing spectrum-based multiple fault localization, CESS-MFL)，以提高多错误定位的效率.CESS-MFL技术首先根据输入变量的谓词条件构建错误相关条件执行切片的谱矩阵，然后依次计算错误相关条件执行切片中的元素(语句或语句块)的可疑度，并生成可疑度报告.实验验证了CESS-MFL技术比当前流行的基于程序谱的Tarantula技术、基于程序切片的Intersection技术、Union技术有更高的多错误定位效率，并且可在有效的时间和空间复杂度内完成.
摘要：
形式验证是提高软件可信程度的重要方法，基于逻辑推理对程序性质进行严格的自动证明是当前的研究热点，但尚无可供工业界使用的产品，其根源在于自动定理证明方面的困难.介绍在通过程序分析建立起各程序点的形状图的基础上，如何利用形状图提供的信息来支持程序验证的方法.提出一种利用形状图信息来消除访问路径别名，使得指针程序中非指针部分的性质仍然可以用Hoare逻辑来进行验证的方法，并证明了该方法的可靠性.还提出一种在不使用自定义谓词的情况下，易变数据结构上数据性质的描述和验证方法.另外，介绍所设计并实现的基于上述方法的PointerC语言的程序验证器的原型.它不仅能自动验证操作易变数据结构程序的性质，也能自动验证使用一维数组的程序的性质.
形式验证是提高软件可信程度的重要方法，基于逻辑推理对程序性质进行严格的自动证明是当前的研究热点，但尚无可供工业界使用的产品，其根源在于自动定理证明方面的困难.介绍在通过程序分析建立起各程序点的形状图的基础上，如何利用形状图提供的信息来支持程序验证的方法.提出一种利用形状图信息来消除访问路径别名，使得指针程序中非指针部分的性质仍然可以用Hoare逻辑来进行验证的方法，并证明了该方法的可靠性.还提出一种在不使用自定义谓词的情况下，易变数据结构上数据性质的描述和验证方法.另外，介绍所设计并实现的基于上述方法的PointerC语言的程序验证器的原型.它不仅能自动验证操作易变数据结构程序的性质，也能自动验证使用一维数组的程序的性质.
摘要：
网构软件所面临的复杂、开放和动态变化的运行环境使其运行时行为常常会偏离需求规约.已有一些研究工作提出基于目标模型和需求推理实现软件需求的运行时监控和自修复，但还缺少实现框架，特别是缺少符合网构软件分布式和社会化特性的需求监控实现方法.针对这一问题，提出一种基于Agent的网构软件需求监控框架.框架中的需求监控Agent通过非侵入的方式实现对作为其宿主系统的网构软件实体的监控和干预，并通过Agent间的通信和协作实现社会化的目标委托和协作监控.为了验证框架的有效性，通过一个案例分析，对框架和工具实现进行了有效性评估.
网构软件所面临的复杂、开放和动态变化的运行环境使其运行时行为常常会偏离需求规约.已有一些研究工作提出基于目标模型和需求推理实现软件需求的运行时监控和自修复，但还缺少实现框架，特别是缺少符合网构软件分布式和社会化特性的需求监控实现方法.针对这一问题，提出一种基于Agent的网构软件需求监控框架.框架中的需求监控Agent通过非侵入的方式实现对作为其宿主系统的网构软件实体的监控和干预，并通过Agent间的通信和协作实现社会化的目标委托和协作监控.为了验证框架的有效性，通过一个案例分析，对框架和工具实现进行了有效性评估.
摘要：
随着网络上完成相同功能的Web服务数量不断增长，服务使用者在选择服务之前，通常需要根据服务的历史使用信息对未使用过的服务质量进行预测.考虑到调用时刻用户输入、网络环境及服务运行环境的差异，提出了一种基于服务调用特征模式的个性化QoS预测方法.该方法通过对服务的历史使用信息进行分析，抽取出服务的常用调用特征模式，当用户调用某服务时，根据用户调用服务时特征，找到其对应的调用模式，若在该模式下有使用信息则直接返回给用户；若没有则根据模式的相似度，采用协作过滤算法为其进行预测.实验结果表明该方法可以显著提高Web服务质量预测的准确性，并且效率较高.
随着网络上完成相同功能的Web服务数量不断增长，服务使用者在选择服务之前，通常需要根据服务的历史使用信息对未使用过的服务质量进行预测.考虑到调用时刻用户输入、网络环境及服务运行环境的差异，提出了一种基于服务调用特征模式的个性化QoS预测方法.该方法通过对服务的历史使用信息进行分析，抽取出服务的常用调用特征模式，当用户调用某服务时，根据用户调用服务时特征，找到其对应的调用模式，若在该模式下有使用信息则直接返回给用户；若没有则根据模式的相似度，采用协作过滤算法为其进行预测.实验结果表明该方法可以显著提高Web服务质量预测的准确性，并且效率较高.
摘要：
协同过滤是电子商务推荐系统中应用最成功的推荐技术之一，但是传统的协同过滤推荐算法存在推荐精度低和抗攻击能力差的缺陷.针对这些问题，提出了一种基于双重邻居选取策略的协同过滤推荐算法.首先基于用户相似度计算的结果，动态选取目标用户的兴趣相似用户集.然后提出了一种用户信任计算模型，根据用户的评分信息，计算得到目标用户对兴趣相似用户的信任度，并以此作为选取可信邻居用户的依据.最后，利用双重邻居选取策略，完成对目标用户的推荐.实验结果表明该算法不仅提高了系统推荐精度，而且具有较强的抗攻击能力.
协同过滤是电子商务推荐系统中应用最成功的推荐技术之一，但是传统的协同过滤推荐算法存在推荐精度低和抗攻击能力差的缺陷.针对这些问题，提出了一种基于双重邻居选取策略的协同过滤推荐算法.首先基于用户相似度计算的结果，动态选取目标用户的兴趣相似用户集.然后提出了一种用户信任计算模型，根据用户的评分信息，计算得到目标用户对兴趣相似用户的信任度，并以此作为选取可信邻居用户的依据.最后，利用双重邻居选取策略，完成对目标用户的推荐.实验结果表明该算法不仅提高了系统推荐精度，而且具有较强的抗攻击能力.
摘要：
针对事务存储系统下的错误检测问题，提出了一种基于冗余事务的事务存储系统的错误检测方法(error detection by redundant transaction, EDRT).该方法为每个事务创建一个副本事务，并利用富余的处理器核资源同时执行原始事务和副本事务，通过比较原始事务和副本事务的执行结果达到检测错误的目的.在检错比较数据集的获取上，EDRT方法利用了事务存储系统自身的版本管理机制，实现了对用户透明的在线接近最小数据比较集的获取.将EDRT方法应用于日志事务存储系统，提出了针对容错日志事务存储系统的设计问题的解决方法.最后，使用了包括4个SPLASH-2典型用例在内的5个测试程序对该方法进行了验证测试，实验结果表明EDRT检错方法相对整个程序的平均检错开销在3.68%左右，而相对于程序内事务部分的平均检错开销也只有12.07%左右.通过与双模冗余检错方法(dual modular redundancy error detection mechanism, DMR)的对比，EDRT方法与DMR方法的平均检错开销比只有0.05%左右.
针对事务存储系统下的错误检测问题，提出了一种基于冗余事务的事务存储系统的错误检测方法(error detection by redundant transaction, EDRT).该方法为每个事务创建一个副本事务，并利用富余的处理器核资源同时执行原始事务和副本事务，通过比较原始事务和副本事务的执行结果达到检测错误的目的.在检错比较数据集的获取上，EDRT方法利用了事务存储系统自身的版本管理机制，实现了对用户透明的在线接近最小数据比较集的获取.将EDRT方法应用于日志事务存储系统，提出了针对容错日志事务存储系统的设计问题的解决方法.最后，使用了包括4个SPLASH-2典型用例在内的5个测试程序对该方法进行了验证测试，实验结果表明EDRT检错方法相对整个程序的平均检错开销在3.68%左右，而相对于程序内事务部分的平均检错开销也只有12.07%左右.通过与双模冗余检错方法(dual modular redundancy error detection mechanism, DMR)的对比，EDRT方法与DMR方法的平均检错开销比只有0.05%左右.
摘要：
准确地获取应用程序在真实系统上运行的访存地址序列(traces)是进行内存系统调度及结构优化的基础.HMTT是自主研发的软硬件结合的内存监测分析系统，能够实时获取完整的全系统访存traces.但是得到的traces与应用程序上层事件之间存在语义鸿沟问题，比如上层函数执行流与访存traces的同步问题.针对该问题提出了一种软硬件结合获取包含函数级别语义信息访存traces的方法，软件方面通过二进制插桩的方式，直接修改内存中的进程映像，在目标函数的入口及出口各插入标记tag访存指令，进而能够被HMTT卡监测并识别.采用二进制插桩不需要程序的源代码，不需要对程序重新编译链接，而且引入的运行开销很小.实验表明采用软硬件结合的方式能够有效地获取包含函数级别语义信息的访存traces，对于SPECCPU2006中的访存密集型程序引入的性能开销只是原程序的62%，而使用Pin工具的纯软件方式获取访存traces将导致至少10.4倍的性能开销.
准确地获取应用程序在真实系统上运行的访存地址序列(traces)是进行内存系统调度及结构优化的基础.HMTT是自主研发的软硬件结合的内存监测分析系统，能够实时获取完整的全系统访存traces.但是得到的traces与应用程序上层事件之间存在语义鸿沟问题，比如上层函数执行流与访存traces的同步问题.针对该问题提出了一种软硬件结合获取包含函数级别语义信息访存traces的方法，软件方面通过二进制插桩的方式，直接修改内存中的进程映像，在目标函数的入口及出口各插入标记tag访存指令，进而能够被HMTT卡监测并识别.采用二进制插桩不需要程序的源代码，不需要对程序重新编译链接，而且引入的运行开销很小.实验表明采用软硬件结合的方式能够有效地获取包含函数级别语义信息的访存traces，对于SPECCPU2006中的访存密集型程序引入的性能开销只是原程序的62%，而使用Pin工具的纯软件方式获取访存traces将导致至少10.4倍的性能开销.
摘要：
模拟器是计算机体系结构研究的重要工具.近年来并行计算机体系结构的发展给计算机模拟带来了巨大的挑战.一方面，随着体系结构朝着多核以及众核处理器发展，模拟的目标系统规模随着模拟核数以摩尔定律的速度增加而不断增大；另一方面，串行模拟的速度因为模拟器运行所在宿主机主频提速减缓而停滞不前.上述两方面的原因使得传统的串行模拟方式无法满足对新兴体系结构模拟规模和速度的需求.以众核处理器和众核集群这两种体系结构为例，并行模拟技术在并行计算机体系结构模拟中是必要而且可行的.对于众核处理器的模拟，使用并行离散事件模拟对其进行加速，在模拟精度不变的前提下，提高模拟速度10.9倍.对于众核集群的模拟，模拟的目标系统总规模达到1024核，并且支持MPI/Pthreads混合编程的运行环境.
模拟器是计算机体系结构研究的重要工具.近年来并行计算机体系结构的发展给计算机模拟带来了巨大的挑战.一方面，随着体系结构朝着多核以及众核处理器发展，模拟的目标系统规模随着模拟核数以摩尔定律的速度增加而不断增大；另一方面，串行模拟的速度因为模拟器运行所在宿主机主频提速减缓而停滞不前.上述两方面的原因使得传统的串行模拟方式无法满足对新兴体系结构模拟规模和速度的需求.以众核处理器和众核集群这两种体系结构为例，并行模拟技术在并行计算机体系结构模拟中是必要而且可行的.对于众核处理器的模拟，使用并行离散事件模拟对其进行加速，在模拟精度不变的前提下，提高模拟速度10.9倍.对于众核集群的模拟，模拟的目标系统总规模达到1024核，并且支持MPI/Pthreads混合编程的运行环境.
摘要：
利用虚拟机的灵活性和快速部署能力，设计并实现了任务部署与调度系统(task deployment and dispatch system，TDDS).TDDS能够根据用户的需求，为用户的计算任务提供可以进行资源配置的集群计算环境，满足了用户对不同操作系统、不同应用程序和不同计算资源的需求.TDDS还使用了负载均衡策略，以提高物理集群资源的利用率.提出了两种虚拟机部署策略，用以加快虚拟集群部署的速度.TDDS尽量控制虚拟机系统镜像的大小和访问频率，以提高部署的效率.实验表明，TDDS系统能够快速灵活地部署用户所需要的计算环境和计算资源，负载均衡的调度策略也切实提高了物理集群处理任务的能力，提高了集群的使用率.
利用虚拟机的灵活性和快速部署能力，设计并实现了任务部署与调度系统(task deployment and dispatch system，TDDS).TDDS能够根据用户的需求，为用户的计算任务提供可以进行资源配置的集群计算环境，满足了用户对不同操作系统、不同应用程序和不同计算资源的需求.TDDS还使用了负载均衡策略，以提高物理集群资源的利用率.提出了两种虚拟机部署策略，用以加快虚拟集群部署的速度.TDDS尽量控制虚拟机系统镜像的大小和访问频率，以提高部署的效率.实验表明，TDDS系统能够快速灵活地部署用户所需要的计算环境和计算资源，负载均衡的调度策略也切实提高了物理集群处理任务的能力，提高了集群的使用率.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
