软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2011年第10期杂志 文档列表

软件学报杂志算法设计与分析

并发计算重复问题与控制方法2263-2278

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

适合复杂网络分析的最短路径近似算法2279-2290

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

一种改进ε支配的等度规映射方法2291-2304

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

采用染色划分改进的RLS算法及性能分析2305-2316

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

软件学报杂志计算机网络与信息安全

有向传感器网络覆盖控制算法2317-2334

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

AdHoc网络中改善拓扑控制性能的移动控制算法2335-2345

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

一种P2P文件共享网络高精度自适应声誉机制2346-2357

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

基于时隙质心流水印的匿名通信追踪技术2358-2371

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

网格虚拟组织副本协作预取机制2372-2384

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

基于池的PMIPv6移动接入网关容错方案2385-2400

摘要：移动IPv6（PMIPv6）是IETF提出的基于网络的区域移动管理协议，依赖于区域移动锚点（localmobilityanchor,）简称LMA）和移动接入网关（mobileaccessgateway,简称MAG）两类移动管理实体实现系统功能．针对JPMIPv6网络中的MAG可靠性问题，提出一种基于池的移动接入网关容错方案（MAGfault-tolerantmethodbasedonpool，简称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应用吞吐量．对于UDP应用，MAGFT可在MAG失效发生后2s内将MN的收包率恢复至其稳定值．同时，方案引入的容错开销小，当系统处于较饱和的稳定服务状态时，容错信令开销相比系统基本信令是可忽略的．MAGFT的引入对MN接入延时略有增加，但增值控制在10ms以下．

基于声誉的多维度信任计算算法2401-2411

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

率失真优化的无线多跳网络多路径选择算法2412-2424

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

随机伪造源地址分布式拒绝服务攻击过滤2425-2437

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

基于行为依赖特征的恶意代码相似性比较方法2438-2453

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

软件学报杂志计算机图形学与计算机辅助设计

基于梯度图的微结构表面全局光照实时绘制2454-2466

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

适于社会网络结构分析与可视化的布局算法2467-2475

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

摄像机位姿的加权线性算法2476-2487

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

中国科学院软件研究所诚聘海内外高层次人才2487-2487

摘要：中国科学院软件研究所成立于1985年3月1日，是一所致力于计算机科学理论和软件高新技术的研究与发展的综合性基地型研究所。秉承“创新求实，永竞一流”的精神，软件研究所不断迈上新的台阶，目前已形成了以多个国家重点实验室和国家工程研究中心为龙头的基础前沿研究、战略高技术研究和高技术应用三大科研体系，建立了计算机科学、计算机软件、计算机应用技术等重点学科领域和相关重点学科方向的学科布局。