Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2012年 第49卷 第8期    出版日期:2012-08-15
论文
一种基于约束优化的虚拟网络映射方法
李小玲, 郭长国, 李小勇, 王怀民,
2012, 49(8):  1601-1610. 
摘要 ( 588 )   HTML ( 0)   PDF (2155KB) ( 536 )  
相关文章 | 计量指标
虚拟网络映射问题将不同的虚拟网络应用映射到相同的基础设施网络中,这是一个极具挑战性的问题.针对该问题,提出了一种基于约束优化的虚拟网络映射方法,将映射问题分解为节点映射和链路映射两个阶段,其中,前者是将虚拟节点映射到物理节点上,后者将虚拟链路映射到物理路径上,它们都是NP难问题.针对节点映射和链路映射分别提出了node-mapping算法和link-mapping算法.node-mapping算法基于贪婪算法的思想,映射时考虑了物理节点所能提供的资源数量以及物理节点间距离两个因素,该算法能够保证基础设施网络中各节点间的负载相对均衡;同时,通过采用访问控制机制,过滤一些异常的虚拟网络请求,能够有效地提高资源的使用效率.link-mapping算法基于人工智能领域中的分布式约束优化思想,其能够保证得到的解是全局最优的,即映射链路的代价最小.最后,通过模拟实验对该方法进行验证,实验结果表明该方法在求解虚拟网络映射问题时的性能良好.
基于双向压力模型的多源应用层组播拥塞控制方案
高建敏 陆慧梅 刘 婧 曹元大
2012, 49(8):  1611-1617. 
摘要 ( 460 )   HTML ( 0)   PDF (1849KB) ( 469 )  
相关文章 | 计量指标
相比传统组播模式,多源应用层组播能用更少的网络资源实现多方交互式应用.但组播特性、应用层环境以及多源属性均会使得多源应用层组播的拥塞问题变得更加严重.因此,提出一种基于双向压力模型的多源应用层组播拥塞控制方案,该方案采用正反压的方式来避免组播流在节点上产生拥塞,并同时采用基于权重的缓冲转移策略来保证同一组内所有数据源的组播流在共享节点上公平地占用缓冲和带宽资源,并进一步讨论了环形拥塞问题的严重性和解决办法.PlanetLab实验网评测结果表明,该方案在实现多源应用层组播拥塞控制的同时,能够协调不同组播流的流量,实现其公平性和可扩展性.
一种无线公交车载网络MAC协议的设计及性能分析
匡罗贝 徐 明 喻 卫 陈颖文
2012, 49(8):  1618-1631. 
摘要 ( 411 )   HTML ( 0)   PDF (4683KB) ( 393 )  
相关文章 | 计量指标
为公交车乘客提供高质量的Internet服务,可以让其在乘车过程中享受娱乐甚至工作,进而大大提高乘客的生活质量.基于此,提出一种无线公交车载网络MAC协议——BusMAC,支持公交车乘客的Internet访问.该协议基于改进的公交车载网络结构,可以大大减少由于公交车上多个用户同时发起产生的大量访问冲突.BusMAC协议基于超帧结构,结合动态竞争机制和捎带机制可以大大减少公交车网络的通信瓶颈.通过建立请求竞争访问模型和数据调度访问模型,对BusMAC协议的性能进行了分析.大量仿真实验结果表明,BusMAC与传统结构及协议相比可以获得相当好的性能,且更加适合于公交车通信.真实移动性场景下的实验说明了该协议在实际系统部署中的可行性.
基于蜂窝结构的传感器网络覆盖问题求解算法
陆克中 江 钊 毛 睿 刘 刚 明 仲
2012, 49(8):  1632-1640. 
摘要 ( 667 )   HTML ( 0)   PDF (2679KB) ( 772 )  
相关文章 | 计量指标
在无线传感器网络中, 求解能够完全覆盖目标区域的最小覆盖集是个NP难问题.在传感器节点数目较多时, 目前只能通过近似算法求解.蜂窝结构是覆盖二维平面的最佳拓扑结构,但不能直接用于求解无线传感器网络的覆盖问题.提出了一种基于蜂窝结构的覆盖问题求解算法,在该算法迭代求解过程的每一阶段,选出一个节点加入到初始为空的节点集合中,并使得该节点集合的拓扑结构接近于蜂窝结构,直至该节点集合成为覆盖集.该算法在最坏情况下的时间复杂度为O(n\+3),这里n为传感器节点总数.实验结果表明该算法可在很短的时间内执行完,在所得覆盖集的大小方面要优于现有的覆盖问题求解算法.
网络处理器信道解码协处理部件算法级低功耗技术研究
宋丽华, 郭艳飞, 王 沁,
2012, 49(8):  1641-1648. 
摘要 ( 483 )   HTML ( 0)   PDF (1643KB) ( 543 )  
相关文章 | 计量指标
以网络处理器的RS(reed-solomon)信道解码协处理部件为研究对象,对传统的信道解码算法进行了低功耗改进并提出了新的LP-RSA算法.通过提前检测误码数的分布情况,该算法能够以尽快、尽少的运算完成求解.基于LP-RSA的解码协处理电路,可根据误码数的检测结果,控制不必要参与运算的电路模块进入休眠状态,节约大量电路翻转带来的功耗浪费.在相同实验条件下,基于LP-RSA的解码协处理部件较传统部件可获得约66.1%的低功耗收益.此外,其研究结果有助于网络处理器在低功耗通信领域的进一步推广和应用.
基于免疫计算的IEEE 802.16j网络基站及中继站选址优化
朱思峰, 刘 芳, 柴争义, 戚玉涛,
2012, 49(8):  1649-1654. 
摘要 ( 497 )   HTML ( 0)   PDF (1097KB) ( 493 )  
相关文章 | 计量指标
IEEE802.16j标准引入了中继站,从而能获得覆盖能力和容量的提升.与传统的单跳无线接入网络相比,IEEE802.16j网络具有以较低代价获得较高容量的优势.中继站和基站的联合优化是移动网络运营商进行网络规划的重要内容之一.由于中继站建站代价远小于基站建站代价,在给定候选站址和覆盖需求的前提下,通过对中继站和基站的站址进行联合优化可以减少基站的建设数目,从而降低网络的建设总代价.为了解决802.16j网络基站及中继站选址优化问题,给出了一个基于免疫计算的选址优化方案.设计了802.16j网络选址优化问题的数学模型,给出了求解选址优化问题的免疫优化算法,并进行了仿真实验.实验结果表明:所给出的方案能以较小的网络建设代价获得较大的网络容量增益,具有较好的应用价值.
一种安全性更高的正形置换发生器
童 言, 张焕国, 邓小铁,
2012, 49(8):  1655-1661. 
摘要 ( 445 )   HTML ( 0)   PDF (703KB) ( 474 )  
相关文章 | 计量指标
作为一种完全映射,正形置换是对称密码体制中一类重要的基础置换.正形置换已经被证明拥有完全平衡性.自1995年以来,国内外学者对于正形置换的研究主要集中在构造与计数方面,但是对于正形置换的密码学性质,比如差分均匀度和非线性度等则相对关注得较少,而具有良好密码学性质的正形置换可以直接用来设计对称密码算法中的密码学部件.修正了一个关于复合函数密码学性质的结论中关于非线性度所存在的问题;接着分析了一般BDLL正形置换发生器的抗差分分析和抗线性分析的密码学性质;然后基于复合函数提出了一种改进的正形置换发生器,并结合修正后的复合函数结论证明了该正形置换发生器相比于一般BDLL正形置换发生器,能够生成数量更多、拥有更高非线性度和代数次数的非线性正形置换.
一个改进的基于门限RSA签名的虚拟企业安全交互模型
张文芳, 王小敏, 何大可,
2012, 49(8):  1662-1667. 
摘要 ( 492 )   HTML ( 0)   PDF (818KB) ( 479 )  
相关文章 | 计量指标
针对L-P虚拟企业安全交互模型进行了深入分析,指出该方案由于没有考虑到RSA密钥结构的特殊性,直接在整数模φ(N)剩余类环Z\-φ(N)上实现分布式门限签名,因此存在代数构造问题.在此基础上,对L-P方案进行修正和改进,通过引入参数π并将环Z\-φ(N)中部分运算转换到整数环Z上,从而有效避免了环Z\-φ(N)中求逆及秘密参数泄露问题.理论分析证明:新方案为基于门限RSA签名机制实现虚拟企业的安全交互提供了正确可行的算法模型.
基于隐写编码和Markov模型的自适应图像隐写算法
张 湛, 刘光杰, 戴跃伟, 王执铨,
2012, 49(8):  1668-1675. 
摘要 ( 558 )   HTML ( 1)   PDF (2960KB) ( 406 )  
相关文章 | 计量指标
如何构造大容量、低失真和高统计安全的隐写算法一直是隐写研究的难点和热点.提出一种兼顾感知失真和二阶统计安全的自适应图像隐写算法设计思路.算法将载体各部分的平滑度引入隐写编码的生成过程,自适应地利用一簇隐写编码在载体各部分的合理运用降低载密图像失真度;在隐秘信息嵌入方式上利用基于Markov链模型的动态补偿方法提高载密图像统计安全性;算法对载体最低有效位和次最低有效位进行嵌入以保证嵌入容量.实验表明算法在相同嵌入量下相较双层随机LSB匹配算法以及仅使用一种隐写编码的算法,失真度更低且载体统计分布的改变更小,而在失真度和统计分布改变相近时嵌入容量更大.
基于系统调用属性的程序行为监控
李 珍 田俊峰 杨晓晖
2012, 49(8):  1676-1684. 
摘要 ( 663 )   HTML ( 0)   PDF (1632KB) ( 560 )  
相关文章 | 计量指标
程序的行为轨迹常采用基于系统调用的程序行为自动机来表示.针对传统的程序行为自动机中控制流和数据流描述的程序行为轨迹准确性较低、获取系统调用上下文时间开销大、无法监控程序运行时相邻系统调用间的程序执行轨迹等问题,提出了基于系统调用属性的程序行为自动机.引入了多个系统调用属性,综合系统调用各属性的偏离程度,对系统调用序列描述的程序行为轨迹进行更准确地监控;提出了基于上下文的系统调用参数策略,检测针对系统调用控制流及数据流的行为轨迹偏离;提出了系统调用时间间距属性,使得通过系统调用及其参数无法监控的相邻系统调用间的程序行为轨迹在一定程度上得到了监控.实验表明基于系统调用属性的程序行为自动机能够更准确地刻画程序行为轨迹,较传统模型有更强的行为偏离检测能力.
可证明安全的基于身份的认证密钥协商协议
高海英
2012, 49(8):  1685-1689. 
摘要 ( 569 )   HTML ( 1)   PDF (587KB) ( 533 )  
相关文章 | 计量指标
提出了一种具有私钥产生中心(private key generator, PKG)前向安全性的基于身份的认证密钥协商协议,协议中给出了一种利用用户双方的长期私钥和临时私钥联合计算共享密钥的方法.在标准模型下证明了协议的安全性,并且分析得出,即使攻击者能够同时获得双方的临时私钥或同时获得双方的长期私钥,共享密钥仍然是安全的.性能分析表明,该协议较好地平衡了计算复杂度和安全性这两个协议评价指标.
基于秘密共享的感知鲁棒图像Hash算法
秦 川, 张真诚, 郭 成,
2012, 49(8):  1690-1698. 
摘要 ( 663 )   HTML ( 1)   PDF (2032KB) ( 505 )  
相关文章 | 计量指标
数字图像在经过保持图像主要内容不变的操作后虽数字表示会发生变化,但其视觉感知效果不变,对应的图像Hash值也应不变,传统密码学中的Hash函数因其对数据每个比特变化的敏感性而不适合直接应用于图像Hash的计算.针对这一问题,提出一种有效的感知鲁棒图像Hash算法,并可应用于图像检索和图像认证等领域.首先通过图像缩放和基于整体变分的非线性滤波等操作对输入图像进行正则化预处理;接着在DCT域提取图像分块与其邻域的低频系数符号关系特征矩阵,该特征可反映图像局部视觉内容的分布特性;最后利用秘密共享机制对提取出的特征矩阵进行压缩得到依赖于密钥的二进制序列,置乱后即作为最终的图像Hash值.实验结果表明,该算法对常见保持图像内容不变的操作,如JPEG压缩、高斯低通滤波及图像缩放等具有较好的感知鲁棒性,同时对于视觉显著不同的图像具有极低的冲突概率.
细分曲面拟合的局部渐进插值方法
赵 宇 蔺宏伟 鲍虎军
2012, 49(8):  1699-1707. 
摘要 ( 643 )   HTML ( 0)   PDF (2157KB) ( 632 )  
相关文章 | 计量指标
逼近型细分方法生成的细分曲面其品质要优于插值型细分方法生成的细分曲面.然而,逼近型细分方法生成的细分曲面不能插值于初始控制网格顶点.为使逼近型细分曲面具有插值能力,一般通过求解全局线性方程组,使其插值于网格顶点.当网格顶点较多时,求解线性方程组的计算量很大,因此,难以处理稠密网格.与此不同,在不直接求解线性方程组的情况下,渐进插值方法通过迭代调整控制网格顶点,最终达到插值的效果.渐进插值方法可以处理稠密的任意拓扑网格,生成插值于初始网格顶点的光滑细分曲面.并且经证明,逼近型细分曲面渐进插值具有局部性质,也就是迭代调整初始网格的若干控制顶点,且保持剩余顶点不变,最终生成的极限细分曲面仍插值于初始网格中被调整的那些顶点.这种局部渐进插值性质给形状控制带来了更多的灵活性,并且使得自适应拟合成为可能.实验结果验证了局部渐进插值的形状控制以及自适应拟合能力.
自适应多分辨图像跟踪算法
吕 娜 冯祖仁
2012, 49(8):  1708-1714. 
摘要 ( 562 )   HTML ( 0)   PDF (2450KB) ( 370 )  
相关文章 | 计量指标
针对实时图像跟踪中目标尺度不断变化的问题,提出了一种新的最大后验概率指标下尺度自适应的多分辨图像跟踪算法.首先证明了后验概率指标的像素级计算特性,在该特性的基础上提出了一种最大后验跟踪算法.由于后验概率指标不仅可以按照特征进行计算,还可以按照像素进行计算,从而可以方便地实现不同尺度上的像素相似度贡献值的计算和比较,据此提出了一种新的目标尺寸自适应算法.此外,当目标尺寸较大时,可以采用不同的分辨率来计算候选匹配区域的匹配概率值,大大降低计算量,从而保证实时跟踪的时间需求.综合上述特点,给出了最大后验概率指标下目标尺寸自适应的多分辨图像跟踪算法.多组视频跟踪实验结果表明了本算法的有效性.
三维曲面的浮雕细节层提取方法
郑翰林 刘利刚
2012, 49(8):  1715-1720. 
摘要 ( 624 )   HTML ( 0)   PDF (1604KB) ( 498 )  
相关文章 | 计量指标
浮雕是在曲面上雕刻出凹凸起伏物体细节的一种雕塑,近年来受到许多人的关注.人们希望运用电脑技术将三维浮雕呈现在屏幕中,并对其进行再创作.在对浮雕进行分析前,很重要的一个问题是将浮雕细节部分从背景曲面中提取出来.该问题可以被看作曲面分割问题,但是现有的大部分方法都有其局限性,即对于带有细节的浮雕曲面并不能很好地提取出浮雕细节网格.使用迭代求解的手段能够更加准确地估计背景曲面,即基曲面的位置,从而能够更加准确而自动地提取出浮雕细节层网格.通过实验表明,该方法对于基曲面占优的浮雕网格具有很好的提取效果.
一种新的无监督前景目标检测方法
梁 鹏, 黎绍发, 王 成,
2012, 49(8):  1721-1729. 
摘要 ( 866 )   HTML ( 0)   PDF (3343KB) ( 469 )  
相关文章 | 计量指标
针对基于无监督特征提取的目标检测方法效率不高的问题,提出一种在无标记数据集中准确检测前景目标的方法.其基本出发点是:正确的特征聚类结果可以指导目标特征提取,同时准确提取的目标特征可以提高特征聚类的精度.该方法首先对无标记样本图像进行局部特征提取,然后根据最小化特征距离进行无监督特征聚类.将同一个聚类内的图像两两匹配,将特征匹配的重现程度作为特征权重,最后根据更新后的特征权重指导下一次迭代的特征聚类.多次迭代后同时得到聚类结果和前景目标.实验结果表明,该方法有效地提高Caltech256数据集和Google车辆图像的检测精度.此外,针对目前绝大部分无监督目标检测方法不具备增量学习能力这一缺点,提出了增量学习方法实现,实验结果表明,增量学习方法有效地提高了计算速度.
人脸识别中适合于小样本情况下的监督化拉普拉斯判别分析
楼宋江 张国印 潘海为 王庆军
2012, 49(8):  1730-1737. 
摘要 ( 566 )   HTML ( 0)   PDF (1148KB) ( 473 )  
相关文章 | 计量指标
提取有效特征对高维数据的模式分类起着关键的作用.无监督判别投影,通过最大化非局部散度和局部散度之比,在数据降维和特征提取上表现出较好的性能,但是它是一种非监督学习算法,并且存在小样本问题.针对这些问题,提出了监督化拉普拉斯判别分析,算法在考虑非局部散度和局部散度时考虑了样本的类别信息;通过丢弃总体拉普拉斯散度矩阵的零空间,并将类内拉普拉斯散度矩阵投影到总体拉普拉斯散度矩阵的主空间中,然后在该空间中进行特征问题的求解,从而避免了小样本问题.通过理论分析,该算法没有任何判别信息损失,同时在计算上效率也较高.在人脸识别上的实验验证了算法的正确性和有效性.
代价敏感的列表排序算法
卢 敏, 黄亚楼, 谢茂强, 王 扬, 刘 杰, 廖 振,
2012, 49(8):  1738-1746. 
摘要 ( 733 )   HTML ( 1)   PDF (1644KB) ( 538 )  
相关文章 | 计量指标
排序学习是信息检索与机器学习中的研究热点之一.在信息检索中,预测排序列表中顶部排序非常重要.但是,排序学习中一类经典的排序算法——列表排序算法——无法强调预测排序列表中顶部排序.为了解决此问题,将代价敏感学习的思想融入到列表排序算法中,提出代价敏感的列表排序算法框架.该框架是在列表排序算法的损失函数中对文档引入权重,且基于性能评价指标NDCG计算文档的权重.在此基础之上,进一步证明了代价敏感的列表排序算法的损失函数是NDCG损失的上界.为了验证代价敏感的列表排序算法的有效性,在此框架下提出了一种代价敏感的ListMLE排序算法,并对该算法开展序保持与泛化性的理论研究工作,从理论上验证了该算法具有序保持特性.在基准数据集上的实验结果表明,在预测排序列表中顶部排序中,代价敏感的ListMLE比传统排序学习算法能取得更好的性能.
分类回归树多吸引子细胞自动机分类方法及过拟合研究
方 敏, 牛文科, 张晓松,
2012, 49(8):  1747-1752. 
摘要 ( 573 )   HTML ( 0)   PDF (1063KB) ( 454 )  
相关文章 | 计量指标
基于多吸引子细胞自动机的分类方法多是二分类算法,难以克服过度拟合问题,在生成多吸引子细胞自动机时如何有效地处理多分类及过度拟合问题还缺乏可行的方法.从细胞空间角度对模式空间进行分割是一种均匀分割,难以适应空间非均匀分割的需要.将CART算法同多吸引子细胞自动机相结合构造树型结构的分类器,以解决空间的非均匀分割及过度拟合问题,并基于粒子群优化方法提出树节点的最优多吸引子细胞自动机特征矩阵的构造方法.基于该方法构造的多吸引子细胞自动机分类器能够以较少的伪穷举域比特数获得好的分类性能,减少了分类器中的空盆数量,在保证分类正确率的同时改善了过拟合问题,缩短了分类时间.实验分析证明了所提出方法的可行性和有效性.
聚类佳点集交叉的约束优化混合进化算法
龙 文, 梁昔明, 徐松金, 陈 富,
2012, 49(8):  1753-1761. 
摘要 ( 506 )   HTML ( 1)   PDF (1458KB) ( 423 )  
相关文章 | 计量指标
提出一种基于聚类佳点集多父代交叉和自适应约束处理技术的混合进化算法用于求解约束优化问题.新算法的主要特点是:在搜索机制方面,利用佳点集方法构造初始化种群,使个体能够均匀地分布在整个搜索空间.然后根据父代个体的相似度将种群个体进行聚类分析,从聚类中随机选择个体进行佳点集多父代交叉操作,利用多个父代个体所携带的信息产生新的具有代表性的子代个体,能够维持和增加种群的多样性.另外,引入局部搜索策略以提高算法局部搜索能力和收敛速度.在约束处理技术上,新算法引入了一个自适应约束处理技术,即根据当前种群中可行解的比例自适应选择不同的个体比较准则.通过15个标准测试函数验证了新算法的有效性.
基于MapReduce的分布式近邻传播聚类算法
鲁伟明 杜晨阳 魏宝刚 沈春辉 叶振超
2012, 49(8):  1762-1772. 
摘要 ( 1079 )   HTML ( 4)   PDF (4011KB) ( 620 )  
相关文章 | 计量指标
随着信息技术迅速发展,数据规模急剧增长,大规模数据处理非常具有挑战性.许多并行算法已被提出,如基于MapReduce的分布式K平均聚类算法、分布式谱聚类算法等.近邻传播(affinity propagation, AP)聚类能克服K平均聚类算法的局限性,但是处理海量数据性能不高.为有效实现海量数据聚类,提出基于MapReduce的分布式近邻传播聚类算法——DisAP.该算法先将数据点随机划分为规模相近的子集,并行地用AP聚类算法稀疏化各子集,然后融合各子集稀疏化后的数据再次进行AP聚类,由此产生的聚类代表作为所有数据点的聚类中心.在人工合成数据、人脸图像数据、IRIS数据以及大规模数据集上的实验表明:DisAP算法对数据规模有很好的适应性,在保持AP聚类效果的同时可有效缩减聚类时间.
类型化π演算的双代数语义
黎永基 李师贤 周晓聪
2012, 49(8):  1773-1780. 
摘要 ( 482 )   HTML ( 0)   PDF (864KB) ( 422 )  
相关文章 | 计量指标
证明互模拟同余通常冗长且易出错.双代数为解决该问题提供统一的框架:若行为函子保持弱回拉,共代数范畴到基范畴的忘却函子有右伴函子,则最大共代数互模拟同余.但已有双代数理论建模类型化π演算存在以下困难:行为函子不保持弱回拉,进程互模拟与共代数互模拟不一致.为解决以上两个问题,用稠密拓扑导出布尔范畴作为语义范畴,令行为函子保持弱回拉;定义一类行为函子,使最大进程互模拟与最大共代数互模拟一致,而迟语义和早语义对应的行为函子属于该类函子.进而给出π演算最大进程互模拟同余的双代数模型,为进一步应用双代数框架对其他复杂演算建模奠定了理论基础.
抽象数据类型的双代数结构及其计算
苏锦钿, 余珊珊,
2012, 49(8):  1787-1803. 
摘要 ( 533 )   HTML ( 0)   PDF (3105KB) ( 475 )  
相关文章 | 计量指标
程序语言中的许多抽象数据类型包含了可递归定义的语法构造和可共递归定义的动态行为特征,因此单纯利用代数或共代数难以给出完整的描述.双代数是同一载体集上的代数和共代数对,提供了一种从范畴论的角度探讨抽象数据类型上的语法构造和动态行为关系及性质的可行途径.给出抽象数据类型的双代数结构,并利用代数函子对共代数函子的分配律描述了语法构造与动态行为之间的自然转换关系;利用分配律对共代数和代数函子进行函子化提升,给出一种构造初始代数(或终结共代数)上的共代数(或代数)结构,并将其提升为初始(或终结)λ-双代数的方法.在此基础上,进一步将函子化提升应用于各种递归(包括迭代和原始递归)及共递归函数(包括共迭代和原始共递归)的定义及计算中,并给出相应的计算定律.
分级存储系统中一种数据自动迁移方法
张广艳, 丘建平,
2012, 49(8):  1804-1810. 
摘要 ( 637 )   HTML ( 3)   PDF (1764KB) ( 451 )  
相关文章 | 计量指标
分级存储系统通过将数据在不同性能设备间动态迁移以达到高性能.已有分级存储系统未能充分利用负载信息导致数据迁移严重影响应用性能.提出了一种分级存储系统中的数据自动迁移方法AutoMig,目标是提高前台应用的I/O性能.AutoMig综合文件访问历史、文件大小、设备利用情况等参数,对文件进行动态分级,并使用LRU队列维护快速存储设备中的文件状态;挖掘关联文件用于自动预取; 针对不同文件迁移操作采取不同的速率控制策略.对降级操作,根据负载变化动态调整迁移速率,对回迁操作则采取尽力而为的策略.在分级存储系统中的应用表明,与已有方法相比,AutoMig有效缩短了前台I/O响应时间.
基于UML的软件Markov链使用模型的构建
吴彩华, 刘俊涛, 彭世蕤, 李海鸿,
2012, 49(8):  1811-1819. 
摘要 ( 658 )   HTML ( 1)   PDF (1403KB) ( 444 )  
相关文章 | 计量指标
构建软件的使用模型是进行软件可靠性测试及软件可靠性评估的基础.近年来,如何由软件的UML模型构造软件的使用模型成为研究热点.对于大型的软件系统来说,应用现有方法构建的软件Markov链使用模型的状态空间过于庞大,模型描述困难,不利于测试用例的自动生成及软件可靠性评估.针对以上问题,提出了一种由UML模型构建Markov链使用模型的方法.该方法将场景的前置条件和后置条件作为 Markov链使用模型的状态,将场景的执行及执行概率作为状态之间的转移及转移概率.与现有方法相比,新方法构建的Markov链使用模型的状态空间小且无需人为干预,而且可以很方便地生成测试输入从而进行可靠性测试.针对UML模型的有效性,提出了经过可靠性评估扩展的UML模型生成Markov链使用模型的验证算法.最后通过一个卫星控制系统的实例对新方法的性能进行了验证.
加权3-Set Packing问题的核心化
李绍华 冯启龙 王建新 陈建二
2012, 49(8):  17811-786. 
摘要 ( 672 )   HTML ( 1)   PDF (603KB) ( 466 )  
相关文章 | 计量指标
Packing和Matching问题是一类重要的NP难解问题,该类问题的参数算法和核心化研究受到了人们广泛的关注.主要研究了加权3-Set Packing的核心化算法.对于加权3-Set Packing问题,基于对问题结构的深入分析,提出并证明了2个简化规则.首先限定加权3-Set Packing问题实例中包含给定2个元素的集合的个数,然后在限定问题实例中包含1个给定元素的集合的个数.基于对集合个数的限定,得到问题实例中总的集合个数的上界.并基于上述性质得到2个简化规则,可得到加权3-Set Packing问题大小为27k\+3-36k\+2+12k的核,该核心化结果是加权3-Set Packing问题的首个核心化结果.得到的加权3-Set Packing的核心化过程同样适用于加权3D-Matching问题的核化,可得到与加权3-Set Packing问题同样大小的问题核.