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

软件学报 2006年第02期杂志 文档列表

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

无线传感器网络最小连通覆盖集问题求解算法175-184

摘要：降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战．在传感器节点高密度部署的环境中，在保证网络性能的前提下，仅将最少量的节点投入活跃工作状态，而将其余节点投入低功耗的睡眠状态，是一种节约系统能量的有效方法．如何计算同时满足“覆盖要求”（工作节点必须能够完全覆盖目标区域）和“连通性要求”（工作节点组成的通信网络必须是连通的）的最小节点集合，是一个NP难问题．设计了一种基于目标区域Voronoi划分的集中式近似算法（centralized Voronoi tessellation，简称CVT），用于计算完全覆盖目标区域所需要的近似最小节点集．当节点通信半径大于等于2倍感知半径时，CVT算法构造的节点集是连通的；当节点通信半径小于2倍感知半径时，设计了一种基于最小生成树（minimum spanning tree，简称MST）的连通算法来计算确保CVT算法构造的覆盖集连通所需的辅助节点．理论分析和实验数据表明，CVT（＋MST）算法的性能在时间复杂性和连通覆盖集大小方面都优于已有的贪婪算法．

寻找地震相关地区的时间序列相似性匹配算法185-192

摘要：把时间序列相似性匹配的基本概念和方法引入到地震预报的应用中．在分析现阶段时间序列研究成果的基础上，结合大量地震历史源数据和领域专家经验知识，提出了有关地震地区相关性的地震相似度定义和地震序列相似性匹配模型，并通过大量实验模拟对该模型进行了反复验证，实现了基于地震相似度的时间序列相似性匹配算法．同时，通过分析我国地震活动频繁区域近20年来的地震历史数据，应用地震区域序列相似性匹配算法进行了固定时间差的粗粒度和细粒度纵向序列相似性实验分析，取得了可信度较高的实验结果，为地震学预测的应用研究提供了较好的技术支持．

全国第5次程序设计语言发展与教学学术会议征文通知192-192

摘要：全国第5次程序设计语言发展与教学学术会议定于2006年10月在南京召开。本次会议由东南大学主办,将就程序设计语言现状与发展、各类程序设计语言及其设计与实现、程序设计语言教学与教材等方面的内容进行广泛的学术交流。会议论文集仍由国家出版社正式出版,其中部分优秀论文将在会后推荐给国内权威核心杂志发表。一、征文范围(包括但不限于)程序设计语言历史、现状与发展;面向对象语言及相关技术;各类建模语言及其设计、实现与应用面向网络应用的程序设计语言;程序设计语言分析、评价与比较程序设计语言语法、语义与语用;程序设计语言教学、教材与课件软件开发过程中各类描述语言;并发、并行与实时程序设计语言;面向网络与Web的

一种DNA测序纠错算法193-199

摘要：提出了一种新的测序纠错算法．该算法在对测序数据拼接之前对其进行检查，找出并修正测序序列中的错误，该算法将测序数据映射成欧拉超路，并通过一种称为合并变换的等价变换，通过一系列规则的限制和引导，动态地对欧拉超路进行简化．在此过程中，该算法将错误的边和正确的边对应起来，再通过替换纠错过程消除错误，在对T．tengcongensis（TT）和T．whipplei（TW）两个数据集的测试过程中，这种方法分别找出并修正了86％和83％的错误，而原欧拉序列拼接中的纠错算法对这两组数据集的纠错结果只有71％和53％．

不同通信模型下的全光树环网波长分配算法200-208

摘要：研究了波分复用全光树环网在不同通信模型下的波长分配算法及其最坏性能分析．对于静态模型，证明了5L／2是树环网所需波长数的紧界．对于动态模型，提出了一种近似比为∑i=1^hmaxrεRi[log｜V（r）｜]＋h的波长分配算法，其中h为树环网的基树的层数，Rf为树环网中处于第i层的环的集合，｜V（r）｜为环r上的节点数．对于增量模型，提出了一种近似度为O[log2（t＋1）]的波长分配算法，其中t为树环网中的环数．

第23届中国数据库学术会议NDBC2006征文通知208-208

软件学报杂志模式识别与人工智能

算法作曲的研究进展209-215

摘要：讨论了当今算法作曲这一研究领域中存在的一些主要问题．评述了这一领域所采用的一系列关键技术，包括Markov链、随机过程、基于音乐规则的知识库系统、音乐文法、人工神经网络技术以及遗传算法．得出的结论是，作曲系统可以朝着集多种方法为一体的混合型系统（hybrid system）的方向发展．系统应在音乐创作的各个层面上提供灵活的人机交互手段，以便提高系统的实用性和有效性．

一种基于图像灰度的快速匹配算法216-222

摘要：在图像模板匹配问题中，基于像素灰度值的相关算法尽管已经十分普遍，并得到广泛的应用，但目前此类算法都还存在有时间复杂度高、对图像亮度与尺寸变化敏感等缺点．为了克服这些缺点，提出一种新的基于图像灰度值的编码表示方法．这种方法将图像分割为一定大小的方块（称为R-块），计算每个R-块图像的总灰度值。并根据它与相邻R-块灰度值的排序关系进行编码．然后通过各个R-块编码值的比较，实现图像与模板的匹配晰算法中各个R-块编码的计算十分简单；匹配过程只要对编码值进行相等比较，而且可以采用快速的比较算法．新算法对像素灰度的变化与噪声具有鲁棒性，其时间复杂度是O（M^2log（N））．实验结果表明，新算法比现有的灰度相关算法的计算时间快了两个数量级．

小世界体系的多对多核联想记忆模型及其应用223-231

摘要：运用机器学习中新颖的核方法和社会网络中广泛存在的小世界现象，对Hattori等人提出的多模块多对多联想记忆模型（multi-module associative memory for many-to-many associations，简称（MMA）^2）进行了改进，构建出了一个基于小世界体系的多对多核联想记忆模型框架（small world structure inspired many to many kernel associative memory models,简称SWSI-M^2KAMs）．该框架不仅克服了原模型不能联机提交训练样本且迭代次数过多的缺陷，而且拓展了原模型的智能信息处理范围．更重要的是，通过核函数的选取，该模型框架可以衍生出更多新的多对多联想记忆模型，而且，由于小世界结构的引入，在一定程度上简化了模型的结构复杂度．最后的计算机模拟。证实了新的模型具有良好的多对多联想记忆功能．

基于二分频率变换的序列相似性查询处理技术232-241

摘要：作为基因功能预测的主要手段，序列相似性查询技术是生物信息学领域的研究热点．基因序列和结构的相似性往往决定了基因功能的相似性，因此可以通过基因序列的相似性查找来预测新基因的功能．分析了MRS索引中频率变化和小波变换等相关技术，讨论了它们的缺点和不足，提出了一种基于二分频率变换2-PFT的序列相似性查询处理技术．首先，设计了二分频率变换和相应的距离函数，使得系统较之频率变换和小波变换具有更高的过滤能力，极大地提高了系统的性能；其次，解决了处理任意长度查询的问题．理论证明和实验结果均表明，2-PFT系统的性能远远优于MRS系统．

基于Gaussian-Hermite矩的指纹奇异点定位242-249

摘要：在指纹分类和识别算法中，提取的奇异点（corc点和delta点）数目和奇异点的准确位置是非常重要的,介绍了一种基于Gaussiall-Hermite矩分布属性的自适应指纹奇异点定位方法，为了准确地确定奇异点，用到了指纹图像在多种尺度下的不同阶Gaussian-Hermite矩分布，并用一种基于主分量分析（principal component analysis，简称PCA）的方法分析指纹图像的Gaussian-Hermite矩分布，实验结果表明，该算法能够准确地确定奇异点位置。

口语对话中的语句分组250-258

摘要：研究了信息类自然口语对话中的交互模式及其自动分析．首先，基于话语分析中的Birmingham学派关于交互模式的工作和Halliday关于言语功能的分析，提出使用语句组采刻画交互模式，并建立原则性分类体系：然后，对语料中的交互模式进行标注分析；随后．才艮据影响语句组结构的主要因素建立交互模式分析算法，并在语料中进行实验．实验结果表明，语句组的整体分析正确率可达到55．4％～84．2％——取决于不同来源的扩展句子类型和语句主题的分析结果．

基于次范畴化的汉语多义动词模糊聚类259-266

摘要：描述了应用模糊k均值方法聚类汉语多义动词的实验，共涉及到60个汉语动词，40个多义词，20个单义词．首先，自动获取每个动词的次范畴化框架的概率分布，然后，导出这些动词的模糊聚类．结果表明，纯洁度和对精确度的综合量度较好地反映了聚类性能，尽管动词的句法行为在一定程度上体现了深层语义，但汉语动词的句法行为不易从单一的语义层预测出来．

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

基于邻居集合的WiMAX网络带宽资源调度算法267-274

摘要：在轮询带宽调度和随机带宽调度两种经典算法的基础上，提出了一种基于邻居集合的带宽资源调度算法来分析和优化WiMAX（world interoperability for microwave access）网络的带宽分配和调度过程．该算法通过使用邻居集合和优先列表，对网络中的用户站，尤其是对使用Mesh模式连接的用户站之间的带宽调度进行了优化，使无线网络的带宽资源能够在网络局部得到优化调度，以达到优化整个无线网络的带宽调度效率．NS2模拟结果表明，该算法具有更低的延迟和更高的吞吐量，能够更好地利用网络资源．

基于通用PC架构的高精度网络时延测量方法275-284

摘要：时延是准确测量时延抖动、带宽等网络性能指标的基础．目前的时延测量方法由于存在时钟误差和位置误差因而精度较差．提出一种改进的时延测量方法，以TSC（time stamp counter）寄存器取代系统时钟计时来消除测量的时钟误差，将时间戳记录位置由应用程序转移到网卡驱动来消除位置误差，极大地提高了时延测量精度．实验结果表明，与传统方法相比，不同包长度下，所提出的方法可降低测量误差21％～150％，且测量结果稳定，对系统吞吐量基本无影响．该方法基于通用PC架构，测量成本低，适于普遍采用．

PIM-SM协议的建模与改进285-294

摘要：PIM-SM（protocol-independent multieast-dense mode）协议是目前Internet首选的城内组播路由协议．影响其广泛应用的一个主要问题是谊协议的控制报文负载比较大．为了对协议进行改进和优化，首先需要建立性能模型并进行准确的性能分析刑用随机Petri网（stochastic Petrinet，简称SPN）模型对整个PIM-SM复杂的协议行为进行了建模，并在其SPN模型的基础上，结合路由器的实现，对协议中每种消息消耗的路由器处理负载和占用的网络带宽进行了分析和实验，发现Register消息和Join／Prune消息消耗的路由器处理负载比较多，而Join／Prune消息和Bootstrap消息占用的网络带宽比较大片艮据性能分析的结论对PIM-SM协议进行了改进与原来的协议相比澉进后的协议性能明显提高．

基于特征聚类的路由器异常流量过滤算法295-304

摘要：基于当前入侵检测技术在检测到攻击的情况下没有良好的反应蓑略过滤攻击流量这一问题，提出了基于攻击流量特征聚类的特征提取算法AFCAA（anomaly traffic character aggregation algorithm）．针对一般DOS（denial of service）／DDOS（distributed denial of service）攻击流数据包头中具有某些相似的特性，AFCAA通过运用重心原理进行统计聚类，在一定的欧氏距离范围内对基于目的IP的攻击流样本相应字段进行聚类划分，动态地提取出攻击流的重心作为攻击的特征．然后，及时地把其特征传输给Net Filter,可以进行高效的过滤，并保护正常流量的传输．实验结果表明，对当前流行的多种拒绝服务攻击，应用AFCAA系统的软件路由器都能够较准确地获取异常流量的特征，从而有效地进行过滤，减少攻击包传播的危害，保护有限的网络资源．

基于Hilbert曲线的许可证存储策略及查找算法305-314

摘要：在分布式环境下，利用信任管理机制来实现存取控制已得到人们的一致认同．但是，许可证的存储策略一直是这个领域中一个尚未完全解决的重要问题，而且它直接影响到许可证链的查找等问题．提出了利用许可证的者和主体两维信息，采用分布哈希表和Hilbert曲线对许可证进行分布定位的新的许可证存储策略．这种存储策略不仅具有很好的负载平衡的特性，而且为许可证的查找提供了充分的灵活性。同时，利用Hilbert曲线生成时的递归特性及其所具有的局部保持性，实现了在分布式环境中基于部分关键字的许可证查找．在此基础上．提出一种许可证链查找算法，实现了在查询过程中构造最小的许可证图，从而大幅度减少网络中的信息传输量.