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

当期目录

2013年 第50卷 第7期    出版日期:2013-07-15
论文
传感器网络中基于LT码的提高数据持续性方案
梁俊斌, 李陶深,
2013, 50(7):  1349-1361. 
摘要 ( 577 )   HTML ( 0)   PDF (2568KB) ( 362 )  
相关文章 | 计量指标
在环境恶劣且无固定Sink的无线传感器网络,节点为了避免意外死亡而丢失数据,需要能量有效地将数据分发到其他一部分节点上存储,以等待移动Sink进行采集.提出了一种新的基于Luby变换码(Luby transform codes)、简称LT码的数据持续性提高方案(LT-codes based scheme for improving data persistence, LTSIDP),其中LT码是一类纠删码.LTSIDP将数据的存储过程分为2个步骤:第1步,节点根据一段时间内接收数据包的情况估计网络中数据包的数量和节点的总数,进而计算出基于LT码存储数据所需要的参数;第2步,节点再根据获得的参数对接收到的数据进行存储.每一轮LTSIDP执行结束后,移动Sink可以在一定时间段内的任意时刻和任意地点进入网络,访问少量仍然存活的节点就能获得所有源数据.理论分析和实验表明,LTSIDP不仅能获得比已有算法更高的数据持续性,而且能量更有效.
基于证据理论的无线传感器网络链式路由算法
唐良瑞 陈媛媛 冯 森
2013, 50(7):  1362-1369. 
摘要 ( 416 )   HTML ( 0)   PDF (1998KB) ( 525 )  
相关文章 | 计量指标
目前存在的许多链式路由算法在链首选举时仅考虑了节点剩余能量,基于Pegasis的节能协议(energy-efficient Pegasis-based protocol, EEPB)算法虽然综合考虑了节点剩余能量与节点到基站的距离两方面因素,但简单地将这两方面因素加权的综合考虑并未完全消除两种因素判决结果的不一致性.基于此,提出一种基于证据理论的链式路由算法(chain routing algorithm based on evidence theory, CRET).首先,在链首选举时利用D-S证据理论,选用节点剩余能量和节点到基站的距离两个评价指标来确定节点是否能成为链首节点,分别建立隶属度函数,进而求得基本概率分配值,再利用D-S证据理论合成法则将两个评价指标进行融合判决.其次,为了避免长链的产生,CRET算法在建链阶段考虑了已经加入链的节点,并且所有节点都是与距离自己最近的节点相连成链.仿真结果表明,CRET算法在平衡节点能耗和延长网络寿命方面比EEPB算法具有更加优越的性能.
标准模型下基于身份的群代理签名方案
谷 科, 贾维嘉, 李超良, 陈荣元,
2013, 50(7):  1370-1386. 
摘要 ( 360 )   HTML ( 0)   PDF (1436KB) ( 497 )  
相关文章 | 计量指标
目前已提出的群代理签名方案存在两个问题,首先缺乏在完整的群代理签名安全模型下证明方案的安全性;其次在标准模型下的群代理签名方案没有涉及到用户身份这一概念,具有一定的使用局限性.针对上述两个问题,在Boldyreva等人提出的代理签名安全模型的基础上提出一个完整的群代理签名可证安全模型,同时为了展示该安全模型的有效性,给出一个群代理签名方案的可证安全实例.该实例通过对Paterson等人提出的标准模型下基于身份的签名方案进行扩展,提出在标准模型下基于身份的群代理签名方案,并在可证安全模型下证明新方案具有在自适应选择消息攻击下存在基于身份的群代理签名不可伪造性,其安全性在标准模型下可归约于CDH问题假定.与目前已有的标准模型下基于公钥密码体制的群代理签名方案相比,该群代理签名方案增加了用户身份的概念,同时具有更完备的可证安全性.
实值n维混沌映射否定选择算法
张凤斌 王天博
2013, 50(7):  1387-1398. 
摘要 ( 474 )   HTML ( 3)   PDF (6071KB) ( 470 )  
相关文章 | 计量指标
针对传统的基于二进制的混沌否定选择算法在检测器生成阶段对混沌映射产生的混沌序列离散化生成的候选检测器,不利于知识和数据的分析,也会造成检测器集生成速度慢及检测效率低等问题,提出了基于实值的混沌否定选择算法.引入混沌理论,采用混沌特性更好的自映射构造n维混沌映射生成候选检测器中心点,改进了传统的检测器生成机制,更适合处理高维空间问题;对原有的V-detector算法进行了优化,通过定向移动与计算几何中心相结合的思想确定检测半径.旨在满足预期覆盖率条件下尽量使半径取值最大化,扩大检测器集的覆盖范围,减少检测器数量.实验结果表明,该算法提高了检测器集的生成速度和检测效率.
基于行为的结构化文档多级访问控制
熊金波, 姚志强, 马建峰, 李凤华, 李 琦,
2013, 50(7):  1399-1408. 
摘要 ( 693 )   HTML ( 0)   PDF (1014KB) ( 620 )  
相关文章 | 计量指标
针对当前云计算环境中因缺乏多级安全机制而使结构化文档容易产生信息泄露和非授权访问等问题,提出基于行为的多级访问控制(action-based multilevel access control model, AMAC)模型并给出策略的形式化描述.利用信息流中的不干扰理论建立AMAC不干扰模型,并证明AMAC模型中多级访问控制策略的安全性.与已有访问控制模型的比较与分析表明,AMAC模型既可以利用角色、上下文和用户访问行为以提高访问控制策略的灵活性,还可以依据用户,用户访问行为和结构化文档的安全等级实现多级安全机制.
理性的安全两方计算协议
张 恩, 蔡永泉,
2013, 50(7):  1409-1417. 
摘要 ( 954 )   HTML ( 2)   PDF (1158KB) ( 1025 )  
相关文章 | 计量指标
在传统的安全两方计算协议中,一方在得到计算结果后,可能会告诉另一方一个错误的结果,或者立即中断协议,这样不能保证协议的完全公平性.针对此问题,结合博弈论和密码学理论,提出一种理性的安全两方计算协议.首先假设理性的参与者最大的利益是得到计算结果,其次是越少的其他人得到结果越好.然后,研究了参与者遵守和背离协议的策略、效用和动机,构建了安全两方计算的博弈模型.在所设计的协议中,参与者遵守协议是参与者的最优策略,任何参与者的欺骗行为都能被检验,参与者背离协议,没有遵守协议的收益大,这样参与者有动机发送真实的数据,最终,每个参与者都能得到计算结果.分析表明,协议是安全和公平的.
改进的多接收者签密方案
李慧贤, 陈绪宝, 巨龙飞, 庞辽军, 王育民,
2013, 50(7):  1418-1425. 
摘要 ( 772 )   HTML ( 2)   PDF (913KB) ( 571 )  
相关文章 | 计量指标
针对现有签密方案存在的可能泄漏接收者隐私、解签密不公平和无公开验证性等问题,采用拉格朗日插值函数方法对其进行改进,提出了一个新的基于身份的多接收者签密方案.新方案将接收者解签密所需的身份信息揉合在一起,实现对接收者隐私的保护,具有解签密匿名性;每一个接收者解密所需密文信息相同,满足解签密公平性;任何第三方在仅拥有密文时就可验证密文发送方的身份,满足公开可验证性.与现有签密方案相比,新方案具有更小的计算量和密文长度.在随机预言模型下,给出了新方案基于双线性Diffie-Hellman(bilinear Diffie-Hellman, BDH)问题假设和计算Diffie-Hellman(computational Diffie-Hellman, CDH)问题假设的安全性证明.
一种新的局部空间排列算法
刘胜蓝, 冯 林, 金 博, 吴振宇,
2013, 50(7):  1426-1434. 
摘要 ( 634 )   HTML ( 0)   PDF (3081KB) ( 362 )  
相关文章 | 计量指标
局部切空间排列算法(local tangent space alignment, LTSA)是一种经典的非线性流形学习方法,能够有效地对非线性分布数据进行降维,但它无法学习局部高曲率数据集.针对此问题,给出了描述数据集局部曲率的参数,并提出一种局部最小偏差空间排列(locally minimal deviation space alignment, LMDSA)算法.该算法考虑到局部切空间低鲁棒性的缺陷,在计算局部最小偏差空间的同时,能够发现数据的局部高曲率现象,通过参数控制及邻域间的连接信息,减少计算局部高曲率空间的可能,进而利用空间排列技术进行降维,手工流形及真实数据集的实验证实了该算法学习局部高曲率数据集的有效性.
自适应学习集成优化算法及矩阵特征值求解
薛 羽, 庄 毅, 孟 新, 张友益,
2013, 50(7):  1435-1443. 
摘要 ( 692 )   HTML ( 0)   PDF (1518KB) ( 503 )  
相关文章 | 计量指标
为了增强数值优化算法的高效性和鲁棒性,提出一种基于自适应学习的集成算法 (self-adaptive-learning-based ensemble algorithm, SALBEA).在SALBEA中,采用贪婪繁殖算子、进化搜索策略学习算子、X进化算子、种群多样性维持算子改进算法进化结构.此外,SALBEA通过引入概率选择模型和自适应学习机制集成了4种有效的进化搜索策略.首先,为了评估所提算法的性能,采用26个测试函数进行算法对比测试,实验结果表明SALBEA比同类算法具有更好的高效性和鲁棒性.最终,将SALBEA用于求解矩阵特征值这一数值计算问题,结果表明该算法求解精度较高,具有较好的应用前景.
基于核方法的User-Based协同过滤推荐算法
王 鹏 王晶晶 俞能海
2013, 50(7):  1444-1451. 
摘要 ( 861 )   HTML ( 2)   PDF (1955KB) ( 746 )  
相关文章 | 计量指标
作为在实际系统中运用最为广泛和成功的推荐技术,协同过滤算法得到了研究者们的广泛关注.传统的协同过滤算法面临着数据稀疏和冷启动等问题的挑战,在计算用户之间相似度时只能考虑有限的数据,因此难以对用户之间的相似度进行准确的估计.提出了一种基于核密度估计的用户兴趣估计模型,并基于此模型,提出了一种基于核方法的user-based协同过滤推荐算法.通过挖掘用户在有限的评分数据上表现出来的潜在兴趣,该算法能更好地描述用户兴趣在项目空间上的分布,进而可以更好地估计用户之间的兴趣相似度.实验表明,该算法可以有效地提高推荐系统的性能,尤其在数据稀疏的情况下能显著地提高推荐结果的质量.
面向信息检索的快速聚类算法
刘 铭 刘秉权 刘远超
2013, 50(7):  1452-1463. 
摘要 ( 607 )   HTML ( 0)   PDF (3516KB) ( 650 )  
相关文章 | 计量指标
随着信息检索技术的迅猛发展,针对检索系统的改进已逐渐成为研究的热点.聚类是一种有效的改进策略,通过对检索结果进行聚类,可以使用户快速地定位到自己感兴趣的检索信息所在的类别.然而,传统的检索聚类算法要么运行效率低下,要么类别划分能力不强,使它们无法真正地用于检索系统中.针对此问题,提出了一种新颖的检索聚类算法,该算法首先通过极大极小值理论从检索返回的文档集中抽取多个聚点,并依此形成初始文档类划分结果.在此基础上,算法对初始文档类的特征集合进行细化调整以使类别的划分更加精确;同时对不满足收敛条件的文档类进行层次分裂以解决信息的分层描述问题.实验表明:此算法的时间复杂度与现有的检索聚类技术相差不多,并且由于对特征集合进行迭代调整使得类别的划分更加准确合理.
应急资源多目标优化调度模型与多蚁群优化算法研究
文仁强, 钟少波, 袁宏永, 黄全义,
2013, 50(7):  1464-1472. 
摘要 ( 557 )   HTML ( 0)   PDF (1991KB) ( 861 )  
相关文章 | 计量指标
大规模自然灾害发生后,极易出现多地同时提出多类型资源需求的局面.基于灾后应急资源调度的特点,建立了考虑多需求点、多供应点、多资源类型、且多个资源供应点能为多个资源需求点协同配备资源的多目标优化调度模型.模型中对调度路线的可靠度进行了考虑,增强了实用性.设计了求解模型的多蚁群优化算法,在全局信息素更新规则中引入精英策略,指导多蚁群间相互交换与共享信息,加快全局非劣解搜索效率.多目标多蚁群优化算法将资源定位配置与路线安排问题进行了集成解决.算例分析表明该算法能够很好地处理大型复杂网络.
列存储系统面向列的连接顺序优化研究
王 梅 陆戌辰 乐嘉锦
2013, 50(7):  1473-1483. 
摘要 ( 559 )   HTML ( 0)   PDF (2349KB) ( 434 )  
相关文章 | 计量指标
连接操作是影响列存储数据查询效率的重要操作之一.对于列存储系统中的连接操作优化,以往的研究工作大多专注于对数据组织结构的优化以及辅助物理结构的建立上,极少涉及逻辑层特别是早期的连接策略优化.为此,根据列存储数据的特点和分析型查询需求的特征,提出了一种新的列存储连接优化方法.该方法采用提早优化的策略,使用“事实表下推”的优化规则,并在多事实表查询条件下引入浓密树进行连接顺序决策,以较小的时空复杂度获得“最优”的连接执行顺序.使用代价估计模型对提出的连接策略优化方法进行了理论验证.同时,在大规模数据仓库基准数据集SSB上通过实验验证了提早优化机制及下推规则的有效性.
基于分形搜索树的嵌入式小波图像编码算法
唐国维, 王苫社, 张 岩, 赵德斌,
2013, 50(7):  1484-1490. 
摘要 ( 614 )   HTML ( 0)   PDF (2054KB) ( 394 )  
相关文章 | 计量指标
与单纯采用分形编码方法相比,基于小波的分形图像编码可以较好地解决方块效应问题且能够有效降低匹配搜索时间,但在低频子带使用分形编码会导致重构图像质量下降,同时针对匹配搜索仍是分形编码主要时间开销的问题,提出一种基于分形搜索树的嵌入式小波图像编码算法.采用Haar小波对图像进行多级分解,对低频子带直接采用DPCM编码,高频部分则依据不同尺度子带的重要性采取自适应方式划分值域块,然后构建一种分形搜索树结构以确定定义域池并采用“Z”形扫描进行匹配搜索,最后对获得的分形参数进行算术编码.实验结果表明,该算法重构图像质量比同类算法有所提高,特别在中低码率下PSNR值提高明显,当码率小于0.40bpp时,PSNR平均提高0.40~2.48dB,同时算法执行时间明显减少.
利于GPU计算具有线性并行度的P/G网SOR求解算法
唐 亮 骆祖莹 赵国兴 杨 旭
2013, 50(7):  1491-1500. 
摘要 ( 632 )   HTML ( 0)   PDF (2473KB) ( 428 )  
相关文章 | 计量指标
近年来电子设计自动化(EDA)研究人员尝试利用图形处理器(graphic processing unit, GPU)提供的高性能计算能力对IC参数分析进行加速研究.为了利用GPU进行电源线/地线网络(power/ground network, P/G网)快速分析,设计了一种基于经典的连续过松弛(successive over-relaxation, SOR)算法的高效P/G网分析并行算法.基于GPU并行计算加速原理,此算法进行了如下改进:1)采用红-黑次序的松弛策略.将所有的节点分为红黑两类,红色节点的所有邻点只有黑色节点、黑色节点的所有邻点只有红色节点,红色节点与黑色节点交替松弛,保证了GPU并行计算中的数据一致性.对于具有N个节点的P/G网而言,一次红色节点或黑色节点松弛可以同时对N/2个节点进行松弛操作,即理论上可以同时启动N/2个并行线程.2)优化数据结构.实现了对数据空间的合并访问,以保证对GPU全局存储空间的最优访问.3)在共享存储器内通过并行归约对松弛标记进行快速统计,同时利用zero-copy技术进行松弛标记的快速拷贝,以快速决定是否继续松弛.大量的实验结果表明:与单线程的CPU程序相比,此算法的加速倍数随GPU所提供物理线程的数目增加而线性增加,可以获得最大242倍的加速效果,是目前EDA研究领域中加速效果最好的GPU算法.
基于描述逻辑的特征语义建模及验证
沈国华, 张 伟, 黄志球, 张钰龙, 金澜涛, 何文民, 贾 哲, 赵子玥,
2013, 50(7):  1501-1512. 
摘要 ( 517 )   HTML ( 2)   PDF (2191KB) ( 488 )  
相关文章 | 计量指标
在软件产品线方法中,特征模型已被广泛用于获取领域需求以支持软件复用.但在一定程度上,各种方法对刻画特征模型以及特征之间约束关系存在语义上的冗余和混乱,不能有效对特征模型进行验证,也限制各种不同特征建模方法之间特征信息的共享.采用描述逻辑刻画了特征模型中的特征类、特征间关系与约束等方面,定义了特征间互斥、需要等约束的规则集合,用于对知识库中的语义特征模型实例进行一致性、完整性验证.并结合一个具体领域,对基于描述逻辑的特征建模及推理验证进行了详细论述.此研究对于领域特征模型的语义建模与验证、支持领域模型共享具有一定的指导作用.
问题驱动的需求捕获中问题分析与解决技术研究
王 波 赵海燕 张 伟 金 芝 梅 宏
2013, 50(7):  1513-1523. 
摘要 ( 540 )   HTML ( 0)   PDF (2314KB) ( 354 )  
相关文章 | 计量指标
问题驱动的需求捕获方法广泛应用于需求获取.然而,利益相关者通常难以找到真实的、一致的问题解决方案并清晰地表达出来.协同式的问题分析与解决方法可以帮助利益相关者找到并表达出真实、一致的解决方案.方法的基本思想是:首先各个利益相关者平等地、按照一定流程协同地分析问题表述的可理解性、问题的价值、问题存在原因;然后利益相关者协同地识别解决方案.通过关联原因和解决方案来保证解决方案的客观性.通过问题的分类,提出问题及协同元素的元模型,及时关注相关联的问题,评估利益相关者的参与程度,用以帮助利益相关者分析与解决问题.选取“高校学生选课系统”进行实例研究,结果显示协同式问题分析与解决是一种在实际应用中行之有效的方法.
面向多请求的Web服务全局优化选择模型研究
康国胜, 刘建勋, 唐明董, 刘小青 ,
2013, 50(7):  1524-1533. 
摘要 ( 553 )   HTML ( 2)   PDF (2047KB) ( 457 )  
相关文章 | 计量指标
在大量相似Web服务共存竞争的环境下,基于服务质量的Web服务选择成为服务计算领域的热点问题之一.现有的Web服务选择方法主要研究单个服务请求或多个合作关系的服务请求共同选择某一个服务的情形,未考虑多个独立的服务请求同时请求同种功能服务的互相竞争性.针对该问题,根据Web服务与服务需求之间的匹配度,利用0-1整数规划建立全局优化服务选择模型,并结合实际提出通用可行的解决多请求的全局优化服务选择算法(global optimal service selection for multiple requests, GOSSMR),在保证Web服务需求质量得到满足的情况下,避免过多的请求同时选择同一个服务,做到资源合理利用,避免服务负载失衡,提高系统的性能.仿真实验验证了模型算法的可行性和有效性.
一种语义保持的C克隆代码无定型过程提取方法
边奕心 王甜甜 苏小红 马培军
2013, 50(7):  1534-1541. 
摘要 ( 504 )   HTML ( 2)   PDF (1622KB) ( 464 )  
相关文章 | 计量指标
克隆代码又被称为重复代码,是一种代码坏味.针对传统的保持语法结构不变的过程提取方法提取克隆代码时存在的对某些克隆代码无法直接提取的问题,提出一种新的语义保持的克隆代码无定型过程提取方法.该方法结合程序依赖图和抽象语法树对程序进行语义分析,取消了传统的保持语法结构不变的过程提取算法对语句结构一致性的约束,保留了语义一致性约束,从而解决了传统方法不易处理的连续但不能直接提取的克隆代码提取问题,降低了对未标记语句提升的需求,并且不需要对跳转语句进行特殊处理.实验结果表明该方法可以提取传统的保持语法结构不变的过程提取方法不能提取的克隆代码,提高了克隆代码过程提取的准确性和适用性.
软件可靠性预测的相关向量机模型
楼俊钢, 江建慧, 沈张果, 蒋云良,
2013, 50(7):  1542-1550. 
摘要 ( 654 )   HTML ( 2)   PDF (1897KB) ( 488 )  
相关文章 | 计量指标
相关向量机是一种解决回归问题非常有效的方法,针对软件失效时间及其之前的m个失效时间数据使用相关向量机进行学习,以建立失效时间之间内在的依赖关系,由此构建新的基于相关向量机的软件可靠性预测模型.在4个数据集上的实验结果表明,新模型在预测能力上较之广泛使用的基于支持向量机或人工神经网络的软件可靠性预测模型有明显的提高,同时也表明现时失效数据的预测能力比很久之前观测的失效数据更强,最后通过实验对合理的m值及不同数据集上核函数参数取值进行研究.
一种基于冗余线程的GPU多副本容错技术
贾 佳, 杨学军, 李志凌,
2013, 50(7):  1551-1562. 
摘要 ( 734 )   HTML ( 1)   PDF (2751KB) ( 389 )  
相关文章 | 计量指标
目前随着通用GPU(general purpose computation on graphic processing units, GPGPU)性能的不断提高,利用CPU和GPU构建的异构系统已经成为高性能计算领域的研究热点.然而随着并行计算系统的不断增长,系统可靠性越来越低,已成为并行计算向大规模扩展的一个不容忽视的制约因素.由于商用GPGPU容错能力较弱,所以由CPU和GPU构建的大规模异构并行系统的可靠性问题更为尖锐,尚缺乏实用的容错手段,针对这一现实问题提出了一种基于冗余线程的GPU多副本容错技术:RB-TMR(Rollback TMR),同时根据异构系统的编程模型及程序特征对这一面向异构系统的容错机制的设计实现及其编译框架进行了具体分析和描述.最后通过10个案例对此技术进行了实现并评估了其性能.这一技术为异构系统的容错技术研究提供了新的思路,具有重大意义.
云环境下可用性感知的并行任务调度方法
曹 洁, 曾国荪, 钮 俊, 许金超,
2013, 50(7):  1563-1572. 
摘要 ( 504 )   HTML ( 1)   PDF (1791KB) ( 609 )  
相关文章 | 计量指标
云计算是一种新兴的计算模式,倡导一切皆服务.云计算由于能够共享分布在世界各地的计算资源,在大规模计算和数据存储中越来越受到重视.云计算是当前IT工业界、学术界研究的热点领域,云环境中的资源可用性已成为云计算不可忽视的问题.对于云计算,当处理器的处理速度不同,不是一直可用于计算时,可用性成为设计和发展云计算系统的关键需求.根据并行任务图及树形云平台的结构特点,分别讨论了影响并行任务可用性需求和计算资源可用性保障的关键因素,给出一种可用性的量化计算公式.并且通过感知任务“可用性需求”和计算资源“可用性保障”,实现可用性匹配,提出了两种可用性感知的调度算法Afsa和Agsa.模拟实验表明该算法能够改善云环境中资源可用性和可靠性,对提高任务调度的成功率具有实际意义.