摘要:数据竞争问题是并发程序开发与测试难题,发现数据竞争可能导致计算重复,重复会导致系统性能下降.从实例出发定义了并发计算重复问题(concurrent computation redundancy problem,简称CCRP),给出了相关性能指标和判断方法,设计了通用并发重复控制机制.并发程序一般都可以基于生产者-消费者模型进行CCRP 分析.以带数据源的生产者-消费者为例详细分析了CCRP,给出了单条件、条件交叉两种重复控制算法,算法具有不同的适用范围,都可以作为固定模式来解决CCRP,基于Petri 网作了相关性质的证明与仿真.并发程序实验结果说明了并发重复控制的必要性和有效性,比较了两种算法的差异.该研究对于数据竞争检测、并发程序设计具有参考价值.关键词: 并发控制;Petri 网;数据竞争;并发计算重复;并发重复控制

摘要:基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出“无标度”等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性.

摘要:新型支配机制的研究是进化多目标优化领域中的热点和难点之一,其中,ε支配最具代表性.但是,它的缺点在于对于不同几何形状的Pareto 前沿十分敏感.提出了一种改进ε支配机制的等度规映射方法,采用等度规映射把解映射到低维流形空间,发现隐藏于非支配解的几何分布,在低维流形空间进行ε支配的剪枝操作.与传统的ε支配相比,该机制不会丢失部分有效解,能够较好地保持解分布的均匀性.另外,为了克服传统ε支配丢失部分极端解的不足,设计了极端解校验算子.与NSGAII,SPEA2,NNIA 和εMOEA 相比,所提出的ε支配和极端解校验算子能够较好地保持解分布的均匀性和宽广性,改进了传统的ε支配.

摘要:利用最大团问题解空间特殊的结构特征,提出一种基于染色划分构建高维约束指导局部搜索移动方向的改进RLS 算法——RLS-II 算法,该算法提高了局部搜索向最优解靠近的概率.基于吸收态Markov 链理论,建立了RLS 和RLS-II 算法求解最大团问题的数学模型,分析了两种算法的吸收时间,并在77 个标准测试算例上对分析结果进行了实验验证.理论分析及实验结果都表明,染色划分过滤确实能够有效改善RLS 算法的性能,且平均染色组长度越大,性能改进的概率和幅度就越大.

摘要:覆盖控制是传感器网络的基本问题之一,基于全向感知模型的覆盖控制的研究已经积累了丰富的成果.近年来,得益于图像/视频、红外、超声波等传感器的引入,有向传感器网络覆盖控制问题得到广泛关注并发展成为研究热点.从有向感知模型及其特点入手,综述了该领域国内外的研究进展,着重分类讨论有向传感器网络覆盖控制的基本理论和算法.最后提出当前亟待解决的问题,并对其未来的发展趋势进行展望.

摘要:在无线Ad Hoc 网络中,拓扑控制算法能够使节点的传输功率小于最大传输功率,从而可以节省网络能量,提高网络容量.由于节点分布的随机性,在节点较为稀疏的区域,拓扑控制算法存在着局限性,因而提出了移动控制算法来改善拓扑控制算法的性能.在保证网络连通性的前提下,算法首先根据收集到的信息,通过构造网络最小生成树确定较长的通信链路,并移动网络中的部分节点使这些链路缩短,从而显著减小网络中较大的通信半径,提高了拓扑控制的性能.仿真实现了PMST-P,PMST-UV和LMST-LUV 这3 种移动控制算法,并对它们的性能进行了讨论和相互比较.

摘要:P2P 文件共享网络的信任评价机制正面临着各种恶意攻击,例如聚集反馈、合谋欺骗和虚假交易,严重影响了整个系统的性能.为了保护P2P 文件共享网络,提出了一种高精度自适应声誉机制,简称AARep 机制(accurateand adaptive reputation mechanism).经过分析发现,在信任评价系统中,除了对交易的评价,相关的交易信息也起着重要的作用.其贡献在于:1) 通过以下手段,增加了信任值计算的精度:引入交易衰减函数,根据交易次序区分交易的重要程度;过滤掉具有低相似度的可疑节点;利用置信因子来反映观测值的可靠性;2) 为了使置信因子起效,提出了一种简单的交易验证协议.实验结果表明, AARep 能够显著消除或者减少各种攻击的威胁,提高系统性能.

摘要:基于扩频的流水印通过扩频技术对水印信号进行编码,将其嵌入特定通信流中以确认网络主体间的通信关系,可以有效地对匿名滥用进行追踪.流水印的实施分为编码、调制、解调、解码等步骤.其中,水印载体的选择尤为重要,关系到水印的健壮性和隐秘性.已有扩频流水印方案选用流速率作为水印载体,由于大部分匿名通信应用,如Web 浏览、即时通信、远程登录等均产生交互式流量,其速率是非稳定的,因而以流速率作为水印载体具有很大的局限性.此外,目前已存在多种针对此类水印隐秘性的攻击技术,降低了追踪的效果.在扩频流水印模型的基础上,引入与特定流无关的基于时隙质心的水印载体,提出一种新型流水印技术.理论分析与实验结果表明,这种新型流水印能够适用于对交互式与非交互式流量的追踪,有着更为广泛的适用性.此外,新型流水印能够有效抵抗现有攻击,保证追踪的隐秘性.

摘要:副本复制是数据网格中提高数据访问效率的有效方法,如何提高副本复制的效率是一个关键性问题.现有的复制策略大多基于文件访问历史选择高价值副本进行复制,但其针对的都是节点已经访问过的文件.通过对虚拟组织文件访问特性进行深入分析,引入隐性高价值文件概念,提出虚拟组织副本协作预取机制(cooperative replicaprefetching mechanism,简称CoRPM),使得本地节点通过与虚拟组织中其他节点进行协作来获取隐性高价值文件副本.该机制首先给出了副本协作预取架构,各个虚拟组织节点上的文件预取模块以协作的方式为虚拟组织内节点提供文件预取服务;然后,在副本协作预取架构的基础上设计了副本协作预取流程,其核心算法包括以作业类型为中心的本地文件预取算法和预取文件选择算法.模拟实验结果表明,CoRPM 与已有的基于文件访问历史的副本复制策略相结合,可以更加有效地降低数据访问延迟.

摘要:代理移动IPv6(PMIPv6)是IETF 提出的基于网络的区域移动管理协议,依赖于区域移动锚点(localmobility anchor,简称LMA)和移动接入网关(mobile access gateway,简称MAG)两类移动管理实体实现系统功能.针对PMIPv6 网络中的MAG可靠性问题,提出一种基于池的移动接入网关容错方案(MAG fault-tolerant method basedon pool,简称MAGFT).方案引入MAG 池解决PMIPv6系中MAG 服务不可替代问题,实现对移动节点(mobilenode,简称MN)透明的MAG容错.针对PMIPv6系统所部署下层网络的不同,MAGFT 分别采用无重叠区部署和有重叠区部署两种模式在PMIPv6 域内构建多个MAG 池,使得域内各MAG 至少归属于一个池.当某MAG 失效时,它所在池内的某一有效MAG将快速接管其服务.理论分析和仿真实验结果表明,MAGFT可将容错时间控制在35ms~340ms.当容错时间在120ms 以下时,MAGFT 可完全避免MAG 失效对MN的TCP应用造成的影响;最差情况下,对分别处于WLAN、3G和卫星网络中的MN而言,MAGFT也可在MAG 失效发生后的1.1s,1.6s 或2.8s内恢复其TCP 应用吞吐量.对于UD 应用,MAGFT可在MAG失效发生后2s 内将MN 的收包率恢复至其稳定值.同时,方案引入的容错开销小,当系统处于较饱和的稳定服务状态时,容错信令开销相比系统基本信令是可忽略的.MAGFT 的引入对MN 接入延时略有增加,但增值控制在10ms以下.

摘要:针对移动Agent 电子商务环境,大多数基于声誉的信任算法是单维度的,评价的节点只对历史交易给出单一的评价,并不区分节点服务内容,给出的信任评价粒度较粗.对此,提出了一种基于声誉的多维度信任算法RMDT(reputation-based multi-dimensional trust).给出了一种新的推荐可信度计算方法,并运用自信因子综合直接信任和推荐信任来对网络内的节点进行信任评估.定义的时间敏感函数使RMDT 具有一定的奖惩机制,实现了信任的动态衰减.通过将交易评价体系和权重体系引入多维度机制,RMDT 较好地体现了个体偏好、风险态度等主观因素对信任计算的影响,增强了信任算法在交易单个属性上的敏感性.

摘要:随着无线网络技术的发展,基于无线多跳网的视频通信在智能交通、灾难应急和军事指挥等多个领域得到越来越广泛的应用.但是,如何保证无线视频的传输质量,是亟待解决的一个关键问题.已有多路径视频传输研究忽略了信道变化和路径间干扰.针对该问题,提出一种基于率失真预测的多路径选择优化算法.该算法不仅分析了网络拥塞对传输质量的影响,而且考虑了路径传输干扰等影响因素.首先,通过对无线信道建模,计算干扰条件下MAC层数据包碰撞概率和处理时间;其次,将无线节点建模为M/M/1/K排队系统,利用排队论预测网络拥塞导致的延迟和丢包;最后,通过建立视频传输与MAC 层性能以及网络拥塞之间的率失真函数关系,预测传输路径的视频失真.并以预测失真为尺度,选择失真近似最小的多路径作为路由.通过NS-2 网络模拟环境中的大量实验,验证了模型的有效性.仿真分析结果表明,该算法能够显著提高无线多跳网络中的视频传输质量.

摘要:由于能够有效隐藏攻击者,随机伪造源地址分布式拒绝服务攻击被广泛采用.抵御这种攻击的难点在于无法有效区分合法流量和攻击流量.基于此类攻击发生时攻击包源地址的统计特征,提出了能够有效区分合法流量和攻击流量,并保护合法流量的方法.首先设计了一种用于统计源地址数据包数的高效数据结构Extended Counting Bloomilter(ECBF),基于此,提出了随机伪造源地址分布式拒绝服务攻击发生时合法地址识别算法.通过优先转发来自合法地址的数据包,实现对合法流量的有效保护.采用真实互联网流量进行模拟,实验结果表明,所提方法能精确识别合法地址,有效地保护合法流量,尤其能够较好地保护有价值的交易会话.所提方法的时间复杂性为O(1),并且只需数兆字节的内存开销,可嵌入边界路由器或网络安全设备,如防火墙中,实现随机伪造源地址分布式拒绝服务攻击的在线过滤.

摘要:恶意代码相似性比较是恶意代码分析和检测的基础性工作之一,现有方法主要是基于代码结构或行为序列进行比较.但恶意代码编写者常采用代码混淆、程序加壳等手段对恶意代码进行处理,导致传统的相似性比较方法失效.提出了一种基于行为之间控制依赖关系和数据依赖关系的恶意代码相似性比较方法,该方法利用动态污点传播分析识别恶意行为之间的依赖关系,然后,以此为基础构造控制依赖图和数据依赖图,根据两种依赖关系进行恶意代码的相似性比较.该方法充分利用了恶意代码行为之间内在的关联性,提高了比较的准确性,具有较强的抗干扰能力;通过循环消除、垃圾行为删除等方法对依赖图进行预理,降低了相似性比较算法的复杂度,加快了比较速度.实验结果表明,与现有方法相比,该方法的准确性和抗干扰能力均呈现明显优势.

摘要:针对带有微结构表面的几何模型全局光照计算复杂、难以达到实时性要求的问题,提出一种基于高度梯度图分析的全局光照实时绘制方法.首先,定义微结构高度梯度图,并据此构建可见点的局部最高点集合.其次,给出面向微结构表面对象实时绘制的全局光照计算模型,将光照计算近似分解为环境光入射、光源直接光照和一次交互漫反射这3 种分量的计算.在环境光计算过程中,提出一种自适应环境光遮挡计算,借助局部最高点集合计算遮挡角.在直接光照中,给出一种微结构阴影的修正方法,搜索入射光方向的最近局部最高点剖面;通过比较剖面内光线投影与局部最高点的遮挡角,近似确定由微结构造成的阴影区域.最后,根据可见点的局部最高点集合确定一次交互漫反射的采样范围,进行渗色处理.整个全局光照计算方法在图像空间完成,较好地利用了延迟着色的思想和GPU 并行计算的特点.算法可以在使用低精度几何模型时表现出带有微结构表面的高精度模型的全局光照效果,且适用于动态场景和可变形物体的全局光照计算.

摘要:力导引布局算法是社会网络信息可视化领域的主流布局算法,但却在结构分析显示方面存在缺陷.产生的图像经常是节点聚集在屏幕中央,难以分辨结构信息.因此,提出了子群分析布局SAL(subgroup analysis layout)算法来解决这一问题.该算法通过角色分析和关键属性分析,对社会网络中的子群进行划分与分析,然后根据子群分析结果对力导引布局算法加以改进,包括2D 和3D 可视化.以对恐怖组织信息进行分析作为实例,也验证了SAL 算法在社会网络结构分析与显示方面具有一定的优越性.

摘要:针对摄像机位姿问题提出了一种加权线性方法,其关键思想是通过加权使经典线性方法的代数误差近似于重投影算法的几何误差,从而达到接近于最大似然估计(Levenberg-Marquardt 简称ML)的精度.通过对经典DLT(direct linear transformation)算法和EPnP 算法使用加权的方法,给出了加权DLT 算法(WDLT)和加权EPnP 算法(WEPnP).大量模拟数据和真实图像实验结果均表明,WDLT 和WEPnP 算法不仅能提高DLT 和EPnP 算法的精度,而且在深度较小的情况下优于Lu 的非线性算法.

摘要:均匀网格划分是一种重要的场景空间组织结构,在光线跟踪绘制、碰撞检测、路径规划等方面有着广泛的应用.特别是由于其计算简单,很适合动态环境的处理.由于该结构的创建时间、空间需求和应用效率与网格分辨率密切相关,优化的网格划分一直是国际上探讨的重要问题.对此,提出一种新的优化划分方法,确保该结构的创建时间和空间需求都是O(N)复杂度的.这里,N 是场景的面片数.同时,在相关的应用计算方面,比如光线跟踪,可与目前最好的加速计算结构相媲美.实验结果表明,该优化划分方法所产生的层次网格结构具有与当前主流的加速结构kd树相当的加速效率,且大幅降低了创建时间,优于已有的类似工作.

摘要:在传统的静态资源预留机制(static resource reservation mechanism,简称SRRM)下,用户的预留请求一旦通过接纳测试就立即被调度到某个资源上.因此,SRRM 无法考虑在预留提前时间(book-ahead time)内作业队列的变化对调度目标产生的影响以及资源故障对预留任务的影响.提出了一种动态的网格资源预留机制(dynamic resourcereservation mechanism,简称DRRM),在该机制下,通过接纳测试的预留请求在其实际使用资源时才被调度.引入了资源-预留图(resource-reservation graph,简称RRG)对DRRM 进行说明,并给出了RRG 的修改规则.DRRM 能够感知预留提前时间内资源状态的变化,根据其运行时信息动态地调度已接纳的预留请求.模拟实验结果表明,与SRRM 相比,DRRM损失了一定的预留请求接纳率,但大大减少了预留任务对非预留任务的抢占,显著提高了网格资源的有效利用率,并且对网格资源故障具有更好的容错效果.

摘要:为了提高非平衡进程到达(unbalanced process arrival,简称UPA)模式下MPI广播的性能,对UPA模式下的广播问题进行了理论分析,证明了在多核集群环境中通过节点内多个MPI 进程的竞争可以有效减少UPA 对MPI广播性能的影响,并在此基础上提出了一种新的优化方法,即竞争式流水化方法(competitive and pipelined method,简称CP).CP方法通过一种节点内进程竞争机制在广过程中尽早启动节点间通信,经该方法优化的广播算法利用共享内存在节点内通信,利用由竞争机制产生的引导进程执行原算法在节点间通信.并且,该方法使节点间通信和节点内通信以流水方式重叠执行,能够有效利用集群系统各节点的多核优势,减少了MPI广播受UPA的影响,提高了性能.为了验证CP方法的有效性,基于此方法优化了3种典型的MPI广播算法,分别适用于不同消息长度的广播.在真实系统中,通过微基准测试和两个实际的应用程序对CP广播进行了性能评价,结果表明,该方法能够有效地提高传统广播算法在UPA模式下的性能.在应用程序的负载测试实验结果中,CP广播的性能较流水化广播的性能提高约16%,较MVAPICH2 1.2中广播的性能提高18%~24%.

摘要:针对传统连续数据保护技术中使用的快照存储技术难以高效存储足够多快照的问题,提出了一种新的快照存储技术,即基于凸点集合的快照存储技术(convex point SNAPshot,简称CSNAP).在讨论了CSNAP 技术使用的数据结构,并引进了在数据结构中加入指针构成的凸点概念的基础上,分析了凸点集合具有的基本性质,并给出了利用凸点集合储存快照的相关算法,同时还给出了一种使用逆行代价改进CSNAP 的方法.最后通过在实际工作负载和随机合成工作负载下的模拟实验说明了,在平均情况下,使用改进的CSNAP 技术,可以将快照占用的储存空间减少到传统方法的10%以下.

摘要:近年来,为了缓解日益严重的功耗问题,异构并行体系结构已成为超级计算机发展的一个重要趋势.图形处理器(graphics processing unit,简称GPU)凭借其超高的计算性能和性能功耗比,作为一种高效的加速部件已被广泛应用于高性能计算领域.但是,GPU 先天的可靠性缺陷势必加剧超级计算机的可靠性问题.目前,国际上关于CPU-GPU 异构系统容错技术的研究工作主要将GPU 从异构系统中独立出来,以每次调用为粒度对其进行容错处理.设计了一种面向CPU-GPU 异构系统的Lazy 容错方法,给出了基于编译指导命令的容错框架及其约束,并讨论了相关的编译实现和优化方法,最后通过实验验证了该方法的正确性.实验结果表明,与现有的容错方法相比,利用所设计的LazyFT 容错方法对GPGPU(general purpose computation on graphics hardware)程序进行容错处理,可以明显降低容错代价.