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

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

计算机学报杂志综论

计算机网络服务质量优化方法研究综述1-14

摘要：优化方法为设计更好的计算机网络服务质量保证机制提供了有力的理论支持．相较于传统启发式的网络设计方法，优化方法可以从理论上找到问题的最优解，从而从根本上克服了启发式方法不能证明方案优劣程度的缺陷．因此，基于优化方法的机制设计与性能评价成为了当前网络服务质量领域中的一个前沿研究领域．大量的研究着眼于从优化理论的角度重新建立网络模型，按照优化理论给出的求解机制和实施方案设计网络协议．计算机网络的优化可以划分为资源分配、任务调度、网络资源部署和系统参数配置等4方面问题．对计算机网络服务质量的优化建模、求解、实施和评价成为当今研究的热点．根据最新网络服务质量优化的研究进展，文中对计算机网络服务质量研究中所涉及到的优化技术进行了研究与综述，主要包括4个方面：系统地描述了计算机网络模型优化算法的通用表达形式，并将其按照不同的方式进行分类；探讨了不同结构的优化模型对应的求解方案；对比分析了不同优化算法的实施方案，给出了方案之间的联系与区别；归纳了计算机网络中优化方案的性能和代价评价方法．最后，对全文进行了总结，并展望了进一步的研究方向．

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

BitTorrent假块污染攻击的对抗方法研究15-24

摘要：作为当前最为流行的P2P文件共享系统，BitTorrent容易受到假块污染攻击的威胁．文中剖析了假块污染攻击的攻击原理，通过建立简化的系统随机模型得出了攻击效果所能达到的理论上限，分析了影响攻击效果的主要因素，并通过仿真实验和广域网实验进行了攻击可行性的验证，比较了在不同攻击条件下的攻击效果．最后给出了针对块污染攻击的对抗方法，通过基于双Hash值的SmartHash算法来改进BitTorrent的内容完整性校验协议，仿真实验表明该方法在对抗块污染攻击时是可行和有效的．

抗适应性选择身份攻击的匿名HIBE方案25-37

摘要：构造了一个新的匿名基于身份加密（IBE）方案，并将其扩展为一个匿名分等级基于身份加密（HIBE）方案．新方案的构造中使用了合数阶双线性群，利用相同子群中的元素对公共参数和密文进行盲化，从而实现方案的匿名性；利用不同子群中的元素构造用户私钥，从而达到正确解密的目的．其安全性证明使用了Lewko和Waters提出的构造双系统加密的新技术．新的匿名HIBE方案具有较短的密文，并且能够在标准模型下达到抗适应性选择身份攻击安全，而此前的匿名HIBE方案仅能达到抗选定身份攻击安全．

基于RSA的网关口令认证密钥交换协议38-46

摘要：网关口令认证密钥交换协议是一个三方协议，使得用户和网关在服务器的协助下建立起一个安全的会话密钥，从而实现用户和网关之间的安全通信．已有的网关口令认证密钥交换协议都是基于Diffie—Hellman密钥交换设计的．利用张木想所设计的PEKEP协议，提出了基于RSA体制的可证明安全的网关口令认证密钥交换协议．在随机预言模型下，基于RSA假设证明了协议的安全性．该协议可以抵抗e次剩余攻击和不可检测在线字典攻击．

eCK模型下可证明安全的双方认证密钥协商协议47-54

摘要：如何构造安全的密钥协商协议是信息安全领域富有挑战性的问题之一．然而目前多数安全协议只能达到“启发式”安全，协议的安全性假设和效率也不够理想．针对这些问题，文中提出了一种新的两轮双方认证密钥协商协议，通过分析新掷议的安全属性指出了构造双方认证密钥协商的一些原则．随后，在eCK模型下对新协议进行了严格的形式化证明，根据相关文献，eCK模型是目前关于双方密钥协商协议的安全程度最高的形式化模型．性能分析表明，新协议较好地平衡了计算量和安全性假设这两个协议评价指标．另外，为了实现新协议的密钥确认属性，文中提出了一种三轮变体协议．

分布式计算环境下的动态可信度评估模型55-64

摘要：随着计算机网络的发展，分布式计算技术得到了广泛的应用，这使得网络节点间的信任问题变得日益突出．参考社会学的人际关系信任模型，基于Dempster—Sharer证据理论和Shapley熵，文中设计出了分布式计算环境下的动态可信度评估模型，这一可信度评估模型清晰地反映了可信度的动态性、连续性和不确定性等特性．该模型通过历史交互信息获得直接可信度，并根据每个节点的信用记录和其直接可信度函数的信息量对其直接可信度进行修正，然后综合考虑修正后的各个节点的直接可信度信息，利用Dempster规则合成计算出综合可信度．最后利用仿真实验分析了新模型对可信度的评估效果，并对未来的工作做了展望．

无线Mesh网中频带宽度与时槽长度可变的公平性优化算法65-75

摘要：改善无线Mesh网中各流间公平性至关重要．目前无线接口已具备频率捷变特性，能动态配置中心频率与频带宽度，可用于提高无线Mesh网的公平性．现有频谱分配算法尽管采用了更灵活的组合信道方式，但仍局限于信道化的框架，对频率捷变特性利用不足，制约了公平性的提升．为了进一步改善无线Mesh网的公平性，文中利用频带宽度与时槽氏度连续可变的特点，提出了一种新的优化算法．该算法用尽可能少的时槽进行链路调度后，联合分配时槽长度及各时槽内无线链路的频带宽度与中心频率，从而获得更好的可行方案．仿真结果显示，与现有算法相比，所提算法基于不同的干扰模型时可提高无线Mesh网的公平性46％～91％．

雪花结构：一种新型数据中心网络结构76-86

摘要：该文分析了传统数据中心的不足以及新型数据中心具备的新特点，借鉴已有数据中心结构，依据著名的科赫曲线（Koch curve），提出了新型数据中心网络结构一雪花结构．该结构充分考虑了数据中心的可扩展性，在保证交换机与服务器较低数量比例（0．125～0．333）的前提下，可以在较短的平均路径内实现节点间路由机制，具有较小的网络开销．

无线传感器网络中基于熵评判的关联支配集构造算法87-95

摘要：无线传感器网络通常是密集分布的，因此相邻网络节点感知的数据之间具有很大的相关性．为了在无线传感器网络中进行数据冗余缩减，文中提出了一个基于熵评判的关联支配集构造算法（EECDS），算法首先通过评价高斯随机变量的熵值来判断网络节点间的数据相关性，然后分布式地构造一个关联图，最后根据关联图信息移除网络中的冗余节点，构建一个连通关联支配集．基于连通关联支配集的数据采集策略能在密集无线传感器网络中进行高效的数据冗余缩减，显著降低网络的能量消耗，延长网络的生命周期．

MANETs稳定性路由的移动自适应策略研究96-104

摘要：在移动AdHoc网络中，节点移动造成网络拓扑实时变化，并增加了路由的复杂性．已有稳定性路由算法往往关注于建立一条相对稳定的路由，而忽略了路由建立后稳定路由对于节点移动的适应性．针对这一问题，首先提出了一种针对稳定性路由的移动自适应策略，该策略主要包括3个关键技术：路由建立过程中稳定性参数的双向评估、节点移动状态改变时的异步通告和链路稳定性更新以及基于链路稳定性的多径路由维护．然后在此基础上，设计了一种具有移动自适应特性的稳定性路由算法．仿真结果表明：提出的移动自适应策略及稳定性路由算法能进一步提高路由性能，更好地适应动态多变的移动AdHoc网路环境．

对称逻辑公式在L3^＊逻辑度量空间中的分布105-114

摘要：在三值逻辑系统L3^＊中引入了对称三值R0函数的概念，在此基础上给出了对称逻辑公式和准对称逻辑公式的定义．研究了在逻辑等价意义下对称逻辑公式的性质，给出了L3^＊和经典逻辑系统L中对称逻辑公式之间的关系及其计数问题，证明了n元对称逻辑公式占全体n元逻辑公式的比例随n的增大而趋向于零，且全体对称逻辑公式的真度之集却在[0，1]中稠密．然而全体对称逻辑公式之集是逻辑度量空间中的无处稠密集．

基于空间缩放和吸引子的粒子群优化算法115-130

摘要：为解决粒子群优化（Particle Swarm Optimization，PSO）算法中粒子越界、算法进化后期收敛速度慢和早熟收敛的问题，通过分析PSO算法中粒子运动行为和算法稳定性，提出了一种基于空间缩放和吸引子的粒子群优化（PSO with search space zoomed factor and attractor，SzAPSO）算法．该算法利用对搜索空间进行缩放的边界变异策略有效控制了粒子搜索范围，保证了算法全局探测能力；算法中吸引子的引入增加了感兴趣区域的粒子密度，提高了算法局部开发能力．实验结果表明，SzAPSO算法收敛速度快、精度高，且具有较好的鲁棒性．

一种用户为中心、基于多视图合成的服务组合方法131-142

摘要：用户为中心的服务组合旨在直接地反映用户需求、提高建模灵活性和降低应用构建成本．然而，当前的用户编程方法仍然存在挑战：一方面传统方法以服务为基本元素，忽视了应用背后的业务数据，用户难以从熟知的业务数据角度表达建模需求；另一方面传统方法以控制流为中心，需要精确描述组合细节，非专业的用户不易理解和操作且难以表达业务约束．文中提出一种用户为中心、基于多视图合成的服务组合方法，通过体征数据模型显式建模业务数据，将服务组合的需求转化为在多个视图编程操作；并给出一种候选流程的构造算法，参照用户的视图操作合成服务组合流程．案例和实验分析表明，文中方法可降低用户构造服务组合的复杂性并提高建模的效率．

ELF：基于无用块消除和低重用块过滤的共享Cache管理策略143-153

摘要：当代CMP处理器通常采用基于LRU替换策略或其近似算法的共享最后一级Cache设计．然而，随着LLC容量和相联度的增长，LRU和理论最优替换算法之间的性能差距日趋增大．为此已提出多种Cache管理策略来解决这一问题，但是它们多数仪引‘对单一的内存访问类型，且对Cache访问的频率信息关注较少，因而性能提升具有很大的局限性．文中提出一种统一的Cache管理策略ELF，不仅可以覆盖多种访存行为，而且能够同时考虑程序中数据的临近性和使用频率信息．根据LLC中Cache块在其生命期内使用频率较低这一实验结果，ELF策略能够（1）通过基于汁数的算法预测出无用块并将其尽早替换；（2）通过动态插入和提升策略过滤低重用数据，从而尽量保留那些潜在的活动数据并且使得一部分工作集免受低使用频率数据的干扰．在4路CMPs上的实验结果显示，ELF可以将全局性能平均提升14．5％，同时与PIPP和TADIP相比，可以分别达到1．06倍和1．09倍的加速比．

基于线程的MPI通信加速器技术研究154-164

摘要：为了针对多核系统构建更高效的MPI支撑环境，文中提出了一种基于线程的MPI加速器，称作MPIActor．MPIActor是一种用于协助传统MPI库的透明中问件，用户可以在编译期选择是否在单线程MPI程序中采用该中间件．加入MPIActor后，每个节点内的MPI进程都被映射成同一进程中的多个线程，从而节点内的通信可通过轻量级的线程通信机制实现．作者给出了MPIActor的基本设计，详细阐述了其工作机制、通信体系结构及关键技术，并在真实系统上分别针对MVAPICH2和OpenMPI并行环境利用0SULATENCY基准测试进行了性能评测．实验结果表明在两种MPI环境上进行节点内8KB～4MB数据通信时MPIActor都能使通信性能平均提高一倍左右．

一种基于FPGA的高斯随机数生成器的设计与实现165-173

摘要：基于FPGA的高斯随机数生成器需要满足可重构、高吞吐率和高硬件资源使用效率等要求．文中提出了一种易于硬件实现的状态转换逻辑结构，并给出了均匀分布随机数周期和输出位宽的配置方法和配置原则．文中详细分析了应用“最值分析法”和“静态误差分析法”求解Box Muller算法实现过程中各操作数位宽的具体过程．硬件实现结果在Xilinx Vertex5上的工作速度为491MHz，吞吐率为9．82×10^8samples／second，硬件资源使用效率为2．085×10^8samples／second／slice．文中作者使用DIEHARD测试集、X^2和K—S方法对产生的随机数质量进行了检测，文中给出了结果．

计算机学报杂志短文

基于投递概率预测的DTN高效路由174-181

摘要：在延迟容忍网络中，基于配额的多拷贝路由通过对消息拷贝数量的限制来控制开销，如何在控制开销的前提下尽可能提高消息投递成功率是其需要解决的关键问题．文中首先分析了提高消息投递成功率的配额分配策略，然后据此提出一种基于投递概率预测的配额路由算法．该路由算法根据节点的本地信息预测到其它节点的投递概率，在复制消息时，根据节点间投递概率的差别分配拷贝配额．仿真结果表明，该算法能较为明显地提高投递成功率并减小延时．

分簇VLIW结构下利用数据依赖图优化调度的研究182-192

摘要：应用的需求促使如今的处理器必须尽可能高地利用程序中所存在的指令级并行度，然而，高指令级并行的硬件和指令调度技术会给寄存器资源带来极大的压力．要在单一寄存器堆的情况下，既维持高的指令级并行度，又保持高的运行时钟频率是一件非常困难的事情，这是因为，当指令级并行度足够高时，在单一寄存器堆情况下，寄存器堆访问端口数目的限制会使得对寄存器堆的访问时间成为制约性能提高的关键因素．为了在利用高的指令级并行度的同时维持高的运行时钟频率，可以将寄存器堆和功能单元划分到不同的簇中．每一个簇中的功能单元可以直接访问簇内的寄存器堆，而簇问的数据交互则需要占用专用的资源来进行．因此，分簇结构下的编译器不仅要通过调度实现最大程序的指令级并行度，还应该对指令的分簇进行细致的安排以限制簇间的数据交互．该文致力于通过对数据依赖图（Data Dependence Graph）分析和划分，从而在最小化簇问的数据交互的同时，平衡各簇的利用情况，提高能够获得的指令级井仃度，从而优化分簇式VLIW结构的调度性能．实验结果证明，该文所提出的方法可以极大地减少簇间的数据交互量，提高所能获得的指令级并行度，从而对调度结果的性能加以改善．