2003年第14卷第7期文章目次
2003, 14(7):1187-1194.
摘要:
对JIAJIA和MPI (message passing interface)是进行了比较.JIAJIA和MPI分别代表共享存储和消息传递的编程模式.MPI显式进行数据传输,编程复杂;JIAJIA由底层维护数据一致性,并附加提供简单的消息传递函数,编程容易、灵活.JIAJIA分配共享内存时开销较大,初始化时间比MPI长.提出了一个关于并行加速比与进程数目之间关系的近似经验公式,推出JIAJIA和MPI性能差距随着进程数目的增多而增大的结论.测试结果表明,大部分应用程序的JIAJIA和MPI版本的并行性能差距不超过10%.对于通信量很小的应用程序,其JIAJIA和MPI的性能差距较小,而通信量本身较大的应用程序,其JIAJIA和MPI的性能差距主要取决于运行时产生的实际通信量.
对JIAJIA和MPI (message passing interface)是进行了比较.JIAJIA和MPI分别代表共享存储和消息传递的编程模式.MPI显式进行数据传输,编程复杂;JIAJIA由底层维护数据一致性,并附加提供简单的消息传递函数,编程容易、灵活.JIAJIA分配共享内存时开销较大,初始化时间比MPI长.提出了一个关于并行加速比与进程数目之间关系的近似经验公式,推出JIAJIA和MPI性能差距随着进程数目的增多而增大的结论.测试结果表明,大部分应用程序的JIAJIA和MPI版本的并行性能差距不超过10%.对于通信量很小的应用程序,其JIAJIA和MPI的性能差距较小,而通信量本身较大的应用程序,其JIAJIA和MPI的性能差距主要取决于运行时产生的实际通信量.
2003, 14(7):1195-1202.
摘要:
在研究无序树包含匹配的基础上,提出一种新的基于XML的软件构件查询匹配算法.该算法可以在保持较高构件查准率的前提下,显著地提高构件的查全率,并提供对布尔查询的支持.此外,通过合理地设定约束条件以及利用动态规划的方法,将计算查询匹配代价的算法时间复杂度限定为多项式级,确保构件查询具有足够的查询效率.最后,通过在构件库原型系统RCRS上进行的一系列实验,进一步证明了新的查询匹配算法在软件构件查询实际应用中的可行性和有效性.
在研究无序树包含匹配的基础上,提出一种新的基于XML的软件构件查询匹配算法.该算法可以在保持较高构件查准率的前提下,显著地提高构件的查全率,并提供对布尔查询的支持.此外,通过合理地设定约束条件以及利用动态规划的方法,将计算查询匹配代价的算法时间复杂度限定为多项式级,确保构件查询具有足够的查询效率.最后,通过在构件库原型系统RCRS上进行的一系列实验,进一步证明了新的查询匹配算法在软件构件查询实际应用中的可行性和有效性.
2003, 14(7):1203-1212.
摘要:
随着实时应用领域的逐渐扩大,不仅传统嵌入式系统的需求日益紧迫,而且这种情况也渗透到桌面环境.为了满足国内用户在这方面的广泛需求,基于红旗Linux操作系统,开发了RFRTOS实时操作系统.主要从实时调度策略、内核抢占机制、细粒度定时器几方面讨论了RFRTOS的实时支持.实验结果表明,所作改进有效地提高了Linux的调度精度,满足了软实时方面的需求.
随着实时应用领域的逐渐扩大,不仅传统嵌入式系统的需求日益紧迫,而且这种情况也渗透到桌面环境.为了满足国内用户在这方面的广泛需求,基于红旗Linux操作系统,开发了RFRTOS实时操作系统.主要从实时调度策略、内核抢占机制、细粒度定时器几方面讨论了RFRTOS的实时支持.实验结果表明,所作改进有效地提高了Linux的调度精度,满足了软实时方面的需求.
2003, 14(7):1213-1220.
摘要:
基于构件的软件开发被认为是解决软件危机的最新成果,但其实践并未达到预期效果:构件设计的方法学还不完善,缺乏对实际应用的明确指导.给出一种业务构件设计方法,应用聚类算法来识别两类业务构件(过程构件和实体构件),以需求模型作为聚类分析样本点的数据来源,并给出样本点关联值的计算方法.通过引入"聚集点实体"的概念改进识别业务构件的准确性,给出构件粒度的计算公式,以降低业务构件的复杂度.最后描述了业务构件接口的设计步骤.
基于构件的软件开发被认为是解决软件危机的最新成果,但其实践并未达到预期效果:构件设计的方法学还不完善,缺乏对实际应用的明确指导.给出一种业务构件设计方法,应用聚类算法来识别两类业务构件(过程构件和实体构件),以需求模型作为聚类分析样本点的数据来源,并给出样本点关联值的计算方法.通过引入"聚集点实体"的概念改进识别业务构件的准确性,给出构件粒度的计算公式,以降低业务构件的复杂度.最后描述了业务构件接口的设计步骤.
2003, 14(7):1221-1228.
摘要:
高层架构恢复对软件维护和软件进化至关重要.把实现架构恢复的聚类问题看作优化问题,通过对常规遗传算法中初始群体产生策略、选择操作方法、交叉概率和变异概率的自适应性等重要参数和关键环节的改进,设计并实现了混合遗传聚类算法(hybrid genetic clustering algorithm,简称HGCA).同时也对该算法的有效性和综合性能进行了实验分析,结果表明,该算法对初始群体的产生有较好的约束作用.与传统遗传算法相比,它的群体性能和收敛性能都较优,且收敛精度高.同时,基于MoJo度量模型的相似性度量值充分说明了HGCA算法对架构恢复的正确性和有效性.
高层架构恢复对软件维护和软件进化至关重要.把实现架构恢复的聚类问题看作优化问题,通过对常规遗传算法中初始群体产生策略、选择操作方法、交叉概率和变异概率的自适应性等重要参数和关键环节的改进,设计并实现了混合遗传聚类算法(hybrid genetic clustering algorithm,简称HGCA).同时也对该算法的有效性和综合性能进行了实验分析,结果表明,该算法对初始群体的产生有较好的约束作用.与传统遗传算法相比,它的群体性能和收敛性能都较优,且收敛精度高.同时,基于MoJo度量模型的相似性度量值充分说明了HGCA算法对架构恢复的正确性和有效性.
2003, 14(7):1229-1237.
摘要:
任何复杂系统都要受到某些基本规律的约束,包括宏观、中观与微观的多层次规律的约束.怎样从一个系统的这些偶然现象(观测数据)中找出它的必然规律,是知识发现(KDD)与数据挖掘(DM)的首要任务,也是研究目标.建立了一个基于演化计算与自然分形相结合的多尺度的动态预测系统.它以微分方程描述系统的宏观行为,以自然分形刻画系统的微观行为.同时,以股票市场数据(君安证券股票数据)和科学观测数据(武汉汛期雨量数据)为例,进行了分析与预测模拟.数值实验表明,该系统的描述(拟合)性能优越,即使是对起伏波动很大的时间序列,也能拟合得很好,预测效果也较好.
任何复杂系统都要受到某些基本规律的约束,包括宏观、中观与微观的多层次规律的约束.怎样从一个系统的这些偶然现象(观测数据)中找出它的必然规律,是知识发现(KDD)与数据挖掘(DM)的首要任务,也是研究目标.建立了一个基于演化计算与自然分形相结合的多尺度的动态预测系统.它以微分方程描述系统的宏观行为,以自然分形刻画系统的微观行为.同时,以股票市场数据(君安证券股票数据)和科学观测数据(武汉汛期雨量数据)为例,进行了分析与预测模拟.数值实验表明,该系统的描述(拟合)性能优越,即使是对起伏波动很大的时间序列,也能拟合得很好,预测效果也较好.
2003, 14(7):1238-1242.
摘要:
通过重新定义全局误差函数,提出了一种基于神经网络的多示例回归算法,并在基准数据集上对该算法进行了测试,取得了较好的效果.
通过重新定义全局误差函数,提出了一种基于神经网络的多示例回归算法,并在基准数据集上对该算法进行了测试,取得了较好的效果.
2003, 14(7):1243-1249.
摘要:
提出了一种求解约束函数优化问题的方法.它不使用传统的惩罚函数,也不区分可行解和不可行解.新的演化算法将约束优化问题转换成两个目标优化问题,其中一个为原问题的目标函数,另一个为违反约束条件的程度函数.利用多目标优化问题中的Pareto优于关系,定义个体Pareto强度值指标以便对个体进行排序选优,根据Pareto强度值排序和最小代数代沟模型设计出新的实数编码遗传算法.对常见测试函数的数值实验证实了新方法的有效性、通用性和稳健性,其性能优于现有的一些演化算法.特别是对于一些既有等式约束又有不等式约束的复杂非线性规划问题,该算法获得了更高精度的解.
提出了一种求解约束函数优化问题的方法.它不使用传统的惩罚函数,也不区分可行解和不可行解.新的演化算法将约束优化问题转换成两个目标优化问题,其中一个为原问题的目标函数,另一个为违反约束条件的程度函数.利用多目标优化问题中的Pareto优于关系,定义个体Pareto强度值指标以便对个体进行排序选优,根据Pareto强度值排序和最小代数代沟模型设计出新的实数编码遗传算法.对常见测试函数的数值实验证实了新方法的有效性、通用性和稳健性,其性能优于现有的一些演化算法.特别是对于一些既有等式约束又有不等式约束的复杂非线性规划问题,该算法获得了更高精度的解.
2003, 14(7):1250-1257.
摘要:
提出了一种基于表面法向的高斯混合模型的距离图像分割算法.它充分利用了表面法向高斯混合模型的物理含义,使数据聚类的次数减少,并利用Expectation-Maximization(EM)算法估计出的模型参数计算模型的后验概率实现了自动模型选择.算法针对两种距离相机的60幅真实距离图像进行了实验.将实验结果与几个流行的分割算法进行了客观比较.
提出了一种基于表面法向的高斯混合模型的距离图像分割算法.它充分利用了表面法向高斯混合模型的物理含义,使数据聚类的次数减少,并利用Expectation-Maximization(EM)算法估计出的模型参数计算模型的后验概率实现了自动模型选择.算法针对两种距离相机的60幅真实距离图像进行了实验.将实验结果与几个流行的分割算法进行了客观比较.
2003, 14(7):1258-1266.
摘要:
区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(logdn),综合性能为O((logn)2d)(使用CqCu模型)或O(K(logn)d)(使用Cqnq+Cunu模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.
区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(logdn),综合性能为O((logn)2d)(使用CqCu模型)或O(K(logn)d)(使用Cqnq+Cunu模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.
2003, 14(7):1267-1274.
摘要:
随着聚类分析对象数据集规模的急剧增大,改进已有的算法以获得满意的效率受到越来越多的重视.讨论了一类采用数据空间网格划分的基于密度的聚类算法的均值近似方法.该方法过滤并释放位于稠密超方格中的数据项,并利用其重心点近似计算其对周围数据元素的影响因子.给出均值近似在聚类算法中的实现策略及其误差估计.均值近似方法在有效减少内存需求、大幅度降低计算复杂度的同时对聚类精确度影响甚微.实验结果验证了该方法能够取得令人满意的效果.
随着聚类分析对象数据集规模的急剧增大,改进已有的算法以获得满意的效率受到越来越多的重视.讨论了一类采用数据空间网格划分的基于密度的聚类算法的均值近似方法.该方法过滤并释放位于稠密超方格中的数据项,并利用其重心点近似计算其对周围数据元素的影响因子.给出均值近似在聚类算法中的实现策略及其误差估计.均值近似方法在有效减少内存需求、大幅度降低计算复杂度的同时对聚类精确度影响甚微.实验结果验证了该方法能够取得令人满意的效果.
2003, 14(7):1275-1281.
摘要:
有许多文章提出了根据DTD将XML映射成关系的方法,但都没有考虑XML的语义,而语义信息对数据存储模式设计、查询优化、更新异常检查等来说是十分重要的,如果在DTD上指定了XML的函数依赖,在映射到关系数据库中就需要将其考虑进去.基于Hybrid Inlining方法并考虑XML函数依赖,提出了一种既能保持XML文档的内容和结构信息,又能保持函数依赖信息的映射方法.通过这种方法可以减少存储冗余,同时证明了映射后的关系都满足第三范式.
有许多文章提出了根据DTD将XML映射成关系的方法,但都没有考虑XML的语义,而语义信息对数据存储模式设计、查询优化、更新异常检查等来说是十分重要的,如果在DTD上指定了XML的函数依赖,在映射到关系数据库中就需要将其考虑进去.基于Hybrid Inlining方法并考虑XML函数依赖,提出了一种既能保持XML文档的内容和结构信息,又能保持函数依赖信息的映射方法.通过这种方法可以减少存储冗余,同时证明了映射后的关系都满足第三范式.
13 无线传感器网络
2003, 14(7):1282-1291.
摘要:
集成了传感器、微机电系统和网络三大技术而形成的传感器网络是一种全新的信息获取和处理技术.在简要介绍传感器网络体系结构的基础上,分析和展望了一些有价值的应用领域.结合已有研究,总结并详细阐述了包括低功耗路由技术和介质访问控制方法等在内的热点研究问题.最后,针对应用需求,提出了几点研究设想.
集成了传感器、微机电系统和网络三大技术而形成的传感器网络是一种全新的信息获取和处理技术.在简要介绍传感器网络体系结构的基础上,分析和展望了一些有价值的应用领域.结合已有研究,总结并详细阐述了包括低功耗路由技术和介质访问控制方法等在内的热点研究问题.最后,针对应用需求,提出了几点研究设想.
2003, 14(7):1292-1299.
摘要:
在Mogent系统所实现的通信算法基础上,借助通讯录再次提出一种基于组播和地址注册的通信算法,它更加有效,能适应多种迁移和通信模式,可以较好地解决移动Agent通信所面临的难题.
在Mogent系统所实现的通信算法基础上,借助通讯录再次提出一种基于组播和地址注册的通信算法,它更加有效,能适应多种迁移和通信模式,可以较好地解决移动Agent通信所面临的难题.
15 安全协议的设计与逻辑分析
2003, 14(7):1300-1309.
摘要:
随着网络应用的迅速发展,网络安全的问题日益重要.研究下述课题:安全协议的设计原则;安全协议设计中形式化方法的应用;各种形式化分析方法,特别是逻辑分析方法的特点.另外,还探讨了串空间模型在逻辑分析中的应用以及串空间模型指导安全协议形式化设计的可能性.
随着网络应用的迅速发展,网络安全的问题日益重要.研究下述课题:安全协议的设计原则;安全协议设计中形式化方法的应用;各种形式化分析方法,特别是逻辑分析方法的特点.另外,还探讨了串空间模型在逻辑分析中的应用以及串空间模型指导安全协议形式化设计的可能性.
2003, 14(7):1310-1317.
摘要:
提出了一种基于动态阈值的保护信道(guard channel,简称GC)方案.该方案的目标是使新增连接和切换连接的阻塞率保持一定的比例关系,从而保证连接之间的优先级和公平性,同时优化和改善了越区切换的性能指标:切换连接的阻塞率、新增连接的阻塞率以及系统资源的利用率.此外,算法的自调节特性使系统能够适应负载的动态变化,保证了阻塞率的平稳性.最后,分析与模拟的结果证明了该方案的可行性.
提出了一种基于动态阈值的保护信道(guard channel,简称GC)方案.该方案的目标是使新增连接和切换连接的阻塞率保持一定的比例关系,从而保证连接之间的优先级和公平性,同时优化和改善了越区切换的性能指标:切换连接的阻塞率、新增连接的阻塞率以及系统资源的利用率.此外,算法的自调节特性使系统能够适应负载的动态变化,保证了阻塞率的平稳性.最后,分析与模拟的结果证明了该方案的可行性.
2003, 14(7):1318-1323.
摘要:
Web及其应用程序的普及使得Web服务器的性能测试变得越来越重要,而现有的测试工具都具有一定的适应性限制.总结了Web服务器性能测试的指标和原则,提出了一个更加合理的测试指标--加权响应时间.介绍了一个Web服务器性能测试工具WebMark.它用事件驱动的方式管理异步I/O,通过修改Client的TCP/IP协议栈来模拟Internet环境.使用它对Apache进行了全面测试,证明了研制WebMark这样一个功能强大的测试工具是十分必要的.
Web及其应用程序的普及使得Web服务器的性能测试变得越来越重要,而现有的测试工具都具有一定的适应性限制.总结了Web服务器性能测试的指标和原则,提出了一个更加合理的测试指标--加权响应时间.介绍了一个Web服务器性能测试工具WebMark.它用事件驱动的方式管理异步I/O,通过修改Client的TCP/IP协议栈来模拟Internet环境.使用它对Apache进行了全面测试,证明了研制WebMark这样一个功能强大的测试工具是十分必要的.
2003, 14(7):1324-1337.
摘要:
随着组播应用的不断增加以及参与者的增多,组播领域的研究一直受到人们的广泛关注.而另一方面,近年来,移动设备迅速得到了普及,并且无线网络技术也得到了飞速的发展,因此,如何为移动主机提供更好的支持引起了人们的普遍关注.由于组播应用所具有的可扩展性强、高效等特点在移动这种资源受限的环境中显得尤为突出和重要,因此,移动环境中的组播应用引起了人们越来越多的重视,在该领域展开了大量的研究.详细地介绍了现有的主要移动组播算法和协议,讨论了每种算法或协议的适应范围以及优点,比较深入地剖析了其中存在的缺陷和问题,并且对这些移动组播算法和协议进行了综合对比.同时,特别针对移动环境可靠性较差的特点,对移动环境中进行可靠组播所面临的新问题以及相关研究现状进行了讨论.希望通过这些说明和对比,能够帮助研究者为其特定的需求选择适当的移动组播算法或协议.最后,讨论了移动环境中IP组播未来的研究方向.
随着组播应用的不断增加以及参与者的增多,组播领域的研究一直受到人们的广泛关注.而另一方面,近年来,移动设备迅速得到了普及,并且无线网络技术也得到了飞速的发展,因此,如何为移动主机提供更好的支持引起了人们的普遍关注.由于组播应用所具有的可扩展性强、高效等特点在移动这种资源受限的环境中显得尤为突出和重要,因此,移动环境中的组播应用引起了人们越来越多的重视,在该领域展开了大量的研究.详细地介绍了现有的主要移动组播算法和协议,讨论了每种算法或协议的适应范围以及优点,比较深入地剖析了其中存在的缺陷和问题,并且对这些移动组播算法和协议进行了综合对比.同时,特别针对移动环境可靠性较差的特点,对移动环境中进行可靠组播所面临的新问题以及相关研究现状进行了讨论.希望通过这些说明和对比,能够帮助研究者为其特定的需求选择适当的移动组播算法或协议.最后,讨论了移动环境中IP组播未来的研究方向.
2003, 14(7):1338-1344.
摘要:
解决由Agent移动产生的可靠性通信问题.在分析已有方法的基础上,提出一种保证移动Agent之间可靠、高效通信的"主动通信"机制,并给出它的可靠性分析和通信效率分析.它能够在通信双方自由移动的情况下,将消息可靠、高效地从发送方提交给接收方,并承诺消息传递的exactly-once语义,为Agent通信语言等高层通信方式奠定了可靠的基础.
解决由Agent移动产生的可靠性通信问题.在分析已有方法的基础上,提出一种保证移动Agent之间可靠、高效通信的"主动通信"机制,并给出它的可靠性分析和通信效率分析.它能够在通信双方自由移动的情况下,将消息可靠、高效地从发送方提交给接收方,并承诺消息传递的exactly-once语义,为Agent通信语言等高层通信方式奠定了可靠的基础.
联系方式
- 《软件学报 》
- 主办单位：中国科学院软件研究所
中国计算机学会 - 邮编：100190
- 电话：010-62562563
- 电子邮箱：jos@iscas.ac.cn
- 网址：https://www.jos.org.cn
- 刊号：ISSN 1000-9825
- CN 11-2560/TP
- 国内定价：70元
您是第位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司
