计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2011年第05期杂志 文档列表

计算机学报杂志《物联网关键理论与技术》专题

《物联网关键理论与技术》专题 前言761-762

摘要：物联网是一种建立在互联网上的泛在网络,通过各种有线和无线网络与互联网融合,综合应用海量的传感器、智能处理终端、全球定位系统等,实现物与物、物与人,所有的物品与网络的连接,方便识别、管理和控制.物联网引领了信息产业革命的第三次浪潮,将成为未来社会经济发展、社会进步和科技创新的最重要的基础设施,

能量高效的无线传感器网络空间范围查询处理算法763-778

摘要：现有无线传感器网络空间范围查询处理算法能量消耗大且当节点失效时查询处理过程易被中断,无法返回查询结果.文中提出了一种能量高效的算法ESA（Energy-efficient Spatial window query processing Algorithm）.它将查询区域划分为若干个网格,每个网格中有一个簇头节点负责收集所在网格中其它节点的感知数据,对这些数据进行聚集运算得到部分查询结果,并将其发送至下一个网格的簇头节点,直至收集到查询区域内所有节点的感知数据,以生成最终的查询结果.ESA算法只需查询区域内的节点发送一次数据消息,减少了发送的数据消息数目.根据ESA的能耗公式给出了两种网格划分和簇头节点选择算法,以降低算法分发查询消息消耗的能量.设计了一种利用节点冗余保证查询处理过程鲁棒性的算法,避免了ESA因节点失效而中断.提出了两种感知数据收集算法,以减少簇头节点收集其邻居节点感知数据的能耗.最后,对ESA算法和现有的IWQE算法（Itinerary-based Window Query Execution）的性能进行了系统的理论和实验分析.分析结果表明：在绝大多数情况下,ESA算法在能量消耗、查询成功率和查询结果质量方面优于IWQE算法.

模糊随机环境下的无线传感器网络多约束多路径路由779-791

摘要：无线传感器网络路由约束同时存在模糊性和随机性,传统路由算法只考虑随机性,不能准确刻画无线传感器网络路由约束.文中引入模糊随机过程理论和模糊随机规划方法,对无线链路时延和可靠性的模糊性、随机性以及时变性进行统一建模,提出了一种模糊随机多约束多路径路由模型,能够更真实地反映无线传感器网络链路特征.在此基础上,设计了一种同时考虑模糊性、随机性和时变性的无线传感器网络多项式复杂度路由算法.仿真实验结果表明,文中所提出的算法能够灵活地调节路由约束强度,满足具体应用对不同服务质量的需要.

一种低耗能的数据融合隐私保护算法792-800

摘要：物联网中的隐私保护是实际应用中要解决的关键问题之一,作为物联网组成部分的无线传感器网络,希望在进行精确数据融合的同时,又能保护个人的隐私.文中提出了一种新的低能耗无线传感器网络数据融合隐私保护算法ESPART.一方面算法依靠数据融合树型结构本身的特性,减少数据通信量;另一方面算法分配随机时间片,避免碰撞.同时限制串通数据范围,降低数据丢失对精确度的影响.仿真结果显示,相比于SMART算法,ESPART可以在有效保护数据隐私的前提下,花费与TAG算法相同的时间和较少的数据通信量,得到精确的数据融合结果.

计算机学报杂志研究论文与技术报告

基于关系模型的进化算法收敛性分析与对比801-811

摘要：研究建立了一种等态等价关系与强/弱态偏序关系模型,用于分析进化算法在收敛性上的等价性与可比性.基于吸收态Markov（马尔可夫）性,满足等态关系的进化算法具有等价的收敛性,从而在收敛性意义上实现了进化算法的等价类划分.在等态关系基础上,建立了弱态和强态的偏序关系,提出了一种对比进化算法收敛性的数学工具,在此基础上设计了更为强态的进化算法.文章运用所得理论分析了采用不同变异算子的（1＋1）EA算法之间的关系,并用数值实验予以验证.文章提出的关系模型可以作为研究进化算法在收敛性上等价、对比和改进的一种理论基础.

基于语义相似度的数据库自适应查询松弛方法812-824

摘要：为了解决数据库空查询结果问题,提出了一种基于语义相似度的数据库自适应查询松弛方法.首先,基于初始查询条件和数据分布推测用户对查询指定属性的重视程度,据此提出了一种属性权重评估方法;然后,通过考察属性值的特征信息,分别提出了分类型属性值之间和数值型属性值之间的语义相似度评估方法;在此基础上,根据松弛阈值、属性权重和属性值之间的语义相似度,提出了一种自适应查询松弛重写算法.对于满足松弛查询的近似查询结果,按照它们对初始查询的满足度进行排序.实验结果表明,提出的属性权重和属性值之间的语义相似度评估方法性能稳定,评估结果合理,提出的查询松弛方法具有较高的查全率,能够较好地满足当前用户的需求和偏好.

KREAG：基于实体三元组关联图的RDF数据关键词查询方法825-835

摘要：语义网数据的大量增加使得RDF数据查询成为一个重要研究主题.关键词查询方式不需要掌握数据模式或查询语言,更适合普通用户使用.文中提出一种RDF数据关键词查询方法KREAG（Keyword query over RDF data based on Entity-triple Association Graph）.为了支持用户对属性或关系名进行查询,将RDF数据建模为顶点带标签的实体三元组关联图.该模型保证了RDF数据中实体间关联转化为关联图中顶点间的通路,且文本信息全部封装到关联图顶点标签上.在此基础上,将关键词查询问题转化为关联图上查找有向斯坦纳树问题.在保证近似比为m的前提下（m为查询关键词的个数）,利用近似算法实现快速查询响应.通过合理的评分方式衡量查询结果的相关性,支持top-k查询.算法的时间复杂度为O（m.｜V｜）,其中｜V｜为实体三元组关联图中顶点个数.实验表明KREAG较其它方法具有更快的响应时间,同时能够有效地实现RDF数据的关键词查询.

动态不确定环境下多目标路径规划方法836-846

摘要：提出一种在动态不确定环境下求解多目标问题时快速调整移动路径的方法.首先提出采用逆向多目标启发式搜索进行全局规划,求解问题的最优路径集合;然后提出动态多目标路径规划方法,先根据当前观测进行全局规划,在移动过程中探测到不一致的环境信息时,通过对先前搜索中部分信息的重用,在全局规划的基础上进行增量重规划,调整当前状态与目标状态之间的移动路径.研究结果表明：采用增量重规划的求解方法通过搜索信息的重用提高求解效率,能够有效地处理动态不确定环境下的多目标路径规划问题.

有限域上高效的细粒度数据完整性检验方法847-855

摘要：基于交叉检验思想的细粒度数据完整性检验方法在实现完整性检验的同时可以对少数错误进行准确和高效的隔离,从而避免因偶然错误或个别篡改造成整体数据失效的灾难性后果.针对需要隔离多个错误时现有方案效率不高的问题,提出了多维结构下基于有限域均匀划分的完整性交叉检验方法,相应地构造了高效的多错完整性指示编码.该方法将完整性检验Hash数据分为若干组,任一组Hash可在某一中间粒度独立指示所有数据对象的完整性,多组Hash结合起来则在更小的基本粒度指示数据的完整性.该方法实现了模块化的Hash结构,对于GF（q）上的d维向量空间,每增加（d-1）组共（d-1）q个Hash即可多指示一个错.分析了该编码在不同参数下的性能,分析结论和实验结果表明该编码效率高,具有灵活的参数选择,可满足各种应用的不同需要.

一种结合词项语义信息和TF-IDF方法的文本相似度量方法856-864

摘要：传统的文本相似度量方法大多采用TF-IDF方法把文本建模为词频向量,利用余弦相似度量等方法计算文本之间的相似度.这些方法忽略了文本中词项的语义信息.改进的基于语义的文本相似度量方法在传统词频向量中扩充了语义相似的词项,进一步增加了文本表示向量的维度,但不能很好地反映两篇文本之间的相似程度.文中在TF-IDF模型基础上分析文本中重要词汇的语义信息,提出了一种新的文本相似度量方法.该方法首先应用自然语言处理技术对文本进行预处理,然后利用TF-IDF方法寻找文本中具有较高TF-IDF值的重要词项.借助外部词典分析词项之间的语义相似度,结合该文提出的词项相似度加权树以及文本语义相似度定义计算两篇文本之间的相似度.最后利用文本相似度在基准文本数据集合上进行聚类实验.实验结果表明文中提出的方法在基于F-度量值标准上优于TF-IDF以及另一种基于词项语义相似性的方法.

一种面向测试需求部分覆盖的测试用例集约简技术879-888

摘要：软件系统开发中频繁面对局部更新和部分缺陷修改,此时需要选择性回归测试;为降低其测试工作量需要解决部分覆盖用例集约简问题.文中基于选择性回归测试形式化定义多目标用例集约简,并设计HATS算法解决该问题.HATS算法遵循启发式贪婪搜索框架,定义权重因子α平衡两方面目标：其一是减少用例集规模;其二是避免对无关需求的覆盖.实验结果表明：同现有约简技术和算法相比较,通过适当设置因子,αHATS算法能够降低用例集规模、减少对无关需求的覆盖、同时缓解对缺陷检测能力的影响.文中的创新贡献在两方面：其一根据选择性回归测试定义多目标用例集约简问题;其二是设计HATS算法以更少的测试用例数量维持缺陷检测效果.

一种面向数据流程序的软件流水并行化方法889-898

摘要：数据流编程被广泛应用于多媒体、图像处理和信号处理等领域.多核处理器为数据流程序提供了强大并行计算资源,如何利用多核处理器的并行性以提高数据流程序性能,对满足媒体处理等实时性需求具有重要意义.基于多核处理器提出了一种面向数据流程序的软件流水并行化方法,利用整数线性规划理论对软件流水中的计算、通信资源和流水线执行阶段等进行统一的形式化建模,在最大化流水线计算速率的同时最小化通信开销;同时对存储资源进行了形式化建模,提高存储访问的性能.通过设计数据流编程语言DFBrook,在Cell处理器实现了上述方法.实验结果表明,该软件流水并行方法比其它方法在提高数据流程序性能的同时,降低了通信开销.

一种面向非规则引用的Cell多核处理器自适应Cache行策略899-911

摘要：非规则问题是大规模并行应用中普遍存在和影响程序效率的关键问题,软件Cache是Cell处理器上解决该问题的一种普遍手段.鉴于通常的软件Cache忽略了非规则引用的内存访问模式,将Cache行设定为一个固定的长度,而加重内存带宽负荷及制约Cache利用率的问题,文中提出了一种自适应的Cache行算法,它根据非规则内存访问的特点,在程序执行过程中不断地调整Cache行的大小,因此减少了传输的数据量.同时,针对不同的Cache行大小,设计了一种相应的软件Cache结构——混合行大小的Cache.它包含多种Tag项数组,每种Tag项数组对应于一种Cache行大小.该Cache设计是一种分级的结构,因为当长Cache行的Tag项数组缺失的时候直接进行缺失处理,而当短Cache行的Tag项数组发生缺失的时候启动缺失处理,同时检查长Cache行的Tag项数组是否命中,若命中,则终止缺失处理.通过对Tag项数组的分级查找,Cache的命中率有了显著的提高.除此之外,文中提出了一种新的行索引对齐的Cache替换策略,它能够在多种不同的Cache行大小并存的情况下实现LRU替换策略.实验表明该文提出的自适应的软件Cache行策略极大地减少了冗余的数据传输,提高了Cache的命中率.同时,与固定的1024B,512B,256B,128B的Cache行的性能相比,自适应的Cache行策略的执行速度分别提高了28.9%,29.7%,32.1%和33.5%.

BW-netRAID：一种后端集中冗余管理的网络RAID系统912-923

摘要：在大型网络存储系统中,在设备间采用冗余策略是提高数据可靠性的重要方法.针对目前网络存储系统前端集中冗余管理中存在的性能瓶颈问题,结合带外虚拟化存储管理架构,文中提出了一种前端并行数据传输和后端集中冗余管理的网络RAID存储系统.应用服务器从元数据服务器获得地址映射信息后可直接并行访问存储设备,充分利用了所有存储节点的聚合I/O性能;冗余管理服务器在磁盘上以日志方式缓存镜像块数据,然后在后台异步计算校验块,并将新校验块数据更新到对应的存储设备节点,从而避免了前端集中冗余管理的单点性能瓶颈和可靠性问题.对不同访问活跃度的数据采用RAID1/RAID5异构分布的管理方法,取得了系统性能、可靠性和价格的平衡.

一种递归定义的可扩展片上网络拓扑结构924-930

摘要：晶体管工艺的持续发展导致片上处理器数的逐渐增多,片上系统的核间通信要求吞吐量高、延时低、可扩展性好,传统的片上总线和crossbar互连结构已无法满足片上系统的通信需求,为此研究者提出新的片上互连结构,称为片上网络.为满足片上网络的特有通信需求,提出了一种可扩展的拓扑结构Rgrid及其路由算法DR,它缩短了片上处理器间的平均距离并且比Torus结构容易实现.作者在龙芯用户级模拟器上分别实现Mesh和Rgrid结构,运行Splash2并行测试程序集比较这两种结构的性能优劣.运行程序结果表明,Splash2程序在Rgrid结构中运行得到的IPC比在Mesh结构增加了0.5%~148%,Rgrid结构的平均延时比Mesh小5%~81%.

图像超分辨率重建的非局部正则化模型与算法研究931-942

摘要：利用图像非局部不连续性测度的概念,建立了面向图像超分辨的非局部正则化能量泛函和相应的变分框架.理论分析了该框架与目前关于双边滤波等一类广义邻域滤波器和经典的变分偏微分方程模型之间的联系.推导了该非局部泛函约束的变分模型最优解满足的积分形式欧拉-拉格朗日方程,并研究了其最速下降流满足的若干重要性质.基于图理论,设计了图像超分辨的自适应加权迭代算法.最后通过选择不同势函数的非局部正则化泛函进行图像去噪、去马赛克效应和图像超分辨处理,性能分析表明：相同势函数下,非局部正则化方法优于同类局部正则化方法,峰值信噪比提高0.5~1.0dB.

两种改进的EDF软实时动态调度算法943-950

摘要：软实时系统中,任务的随意抢占浪费了CPU资源,过多的任务丢失降低了系统的调度性能.文章引入＂动态模糊阈值＂概念,提出了两种新的类似EDF调度的模糊阈值调度算法.两种算法在任务执行过程中,分别通过缩短和延长当前任务截止期至动态模糊阈值的方法节约资源、提高任务完成率.给出模糊阈值的临界值计算公式,分析算法的可调度性,进行仿真与性能分析比较.结果表明,与EDF调度算法比较,两种算法有效地提高了重要任务的完成率,当截止期被延长时,任务的错失率明显降低,当截止期被缩短时,任务间的切换次数大大减少.因此,新算法提高了CPU的利用率,改善了系统的实时性能.