2009年第20卷第11期文章目次
2009, 20(11):2915-2924.
摘要:
在头驱动句法分析模型下,基于经典插值平滑算法,提出了以统计空间中平均事件数为基础的直接插值平滑建模原则,并应用经典的误差理论分析了该原则的合理性.基于该原则并借鉴语言模型中其他插值平滑算法对模型的零点进行假设的方法,在头驱动句法分析模型下,重新构造了4种平滑算法.实验数据显示,新平滑算法在高于经典平滑算法性能的同时,显著降低了自由参数的扰动程度,从实验的角度证明了该平滑建模原则的有效性.
在头驱动句法分析模型下,基于经典插值平滑算法,提出了以统计空间中平均事件数为基础的直接插值平滑建模原则,并应用经典的误差理论分析了该原则的合理性.基于该原则并借鉴语言模型中其他插值平滑算法对模型的零点进行假设的方法,在头驱动句法分析模型下,重新构造了4种平滑算法.实验数据显示,新平滑算法在高于经典平滑算法性能的同时,显著降低了自由参数的扰动程度,从实验的角度证明了该平滑建模原则的有效性.
2009, 20(11):2925-2938.
摘要:
为了解决高维无约束数值优化问题,借鉴协同进化和精英策略的思想,提出了M-精英协同进化算法.该算法认为,适应度较高的个体群(称为精英种群)在整个种群进化中起着主导作用.算法将整个种群划分为由M个精英组成的精英种群和由其余个体组成的普通种群这样两个子种群,依次以M个精英为核心(称为核心精英)来选择成员以组建M个团队.若选中的团队成员是其他精英,则该成员与核心精英利用所定义的协作操作来交换信息;若团队成员选自普通种群,则由核心精英对其进行引导操作.其中,协作操作和引导操作由若干不同类型的交叉或变异算子的组合所定义.理论分析证明,算法以概率1收敛于全局最优解.对15个标准测试函数进行的测试显示,该算法能够找到其中几乎所有被测函数的最优解或好的次优解.与3个已有的算法相比,在评价次数相同时,该算法所求解的精度更高.同时,该算法的运行时间较短,甚至略短于同等设置下的标准遗传算法.此外，对参数的实验分析显示,该算法对参数不敏感,易于使用.
为了解决高维无约束数值优化问题,借鉴协同进化和精英策略的思想,提出了M-精英协同进化算法.该算法认为,适应度较高的个体群(称为精英种群)在整个种群进化中起着主导作用.算法将整个种群划分为由M个精英组成的精英种群和由其余个体组成的普通种群这样两个子种群,依次以M个精英为核心(称为核心精英)来选择成员以组建M个团队.若选中的团队成员是其他精英,则该成员与核心精英利用所定义的协作操作来交换信息;若团队成员选自普通种群,则由核心精英对其进行引导操作.其中,协作操作和引导操作由若干不同类型的交叉或变异算子的组合所定义.理论分析证明,算法以概率1收敛于全局最优解.对15个标准测试函数进行的测试显示,该算法能够找到其中几乎所有被测函数的最优解或好的次优解.与3个已有的算法相比,在评价次数相同时,该算法所求解的精度更高.同时,该算法的运行时间较短,甚至略短于同等设置下的标准遗传算法.此外，对参数的实验分析显示,该算法对参数不敏感,易于使用.
2009, 20(11):2939-2949.
摘要:
基于最大散度差判别准则提出了一种模糊最大散度差准则,并根据模糊最大散度差准则提出一种聚类方法(fuzzy maximum scatter difference discriminant criterion based clustering algorithm,简称FMSDC).该方法通过迭代优化方法实现聚类的同时还可以实现特征降维.该方法首先在最大散度差判别准则中引入模糊概念;然后通过具体原则设定模糊最大散度差判别准则中的参数η,从而在一定程度上降低了由参数η引起的敏感性;最后分别根据模糊隶属度μik、最优鉴别矢量ω进行聚类和特征降维.实验结果表明,FMSDC方法不但具有基本的聚类功能,而且具有较好的鲁棒性和较强的特征降维能力.
基于最大散度差判别准则提出了一种模糊最大散度差准则,并根据模糊最大散度差准则提出一种聚类方法(fuzzy maximum scatter difference discriminant criterion based clustering algorithm,简称FMSDC).该方法通过迭代优化方法实现聚类的同时还可以实现特征降维.该方法首先在最大散度差判别准则中引入模糊概念;然后通过具体原则设定模糊最大散度差判别准则中的参数η,从而在一定程度上降低了由参数η引起的敏感性;最后分别根据模糊隶属度μik、最优鉴别矢量ω进行聚类和特征降维.实验结果表明,FMSDC方法不但具有基本的聚类功能,而且具有较好的鲁棒性和较强的特征降维能力.
2009, 20(11):2950-2964.
摘要:
从数据存储组织、查询优化和处理、原型系统和基准测试等方面介绍当前RDF数据管理的研究进展和比较分析,讨论存在的问题并给出未来的研究方向.
从数据存储组织、查询优化和处理、原型系统和基准测试等方面介绍当前RDF数据管理的研究进展和比较分析,讨论存在的问题并给出未来的研究方向.
2009, 20(11):2965-2976.
摘要:
研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的Apriori性质,给出了一种基于深度优先搜索策略的挖掘算法.该算法使用高效的期望支持度计算方法和搜索空间裁剪技术,使得计算子图模式的期望支持度所需的子图同构测试的数量从指数级降低到线性级.实验结果表明,该算法比简单的深度优先搜索算法快3～5个数量级,有很高的效率和可扩展性.
研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的Apriori性质,给出了一种基于深度优先搜索策略的挖掘算法.该算法使用高效的期望支持度计算方法和搜索空间裁剪技术,使得计算子图模式的期望支持度所需的子图同构测试的数量从指数级降低到线性级.实验结果表明,该算法比简单的深度优先搜索算法快3～5个数量级,有很高的效率和可扩展性.
2009, 20(11):2977-2987.
摘要:
引入了一个XML结构完整性约束体系.这个体系描述了XML文档中节点或路径之间的5种结构关系,包括路径蕴涵、路径同现、路径互斥、必需性包含和排他性包含.给出了这些结构完整性约束的语法和语义定义,并研究了它们在XML查询优化中的作用.基于子路径的概念,提出了有结构完整性约束的路径表达式的最小化算法.该算法以路径蕴涵闭包为工具,不仅可以删除路径表达式的冗余,还可以识别无效路径表达式.实验结果表明了该算法的正确性和有效性.
引入了一个XML结构完整性约束体系.这个体系描述了XML文档中节点或路径之间的5种结构关系,包括路径蕴涵、路径同现、路径互斥、必需性包含和排他性包含.给出了这些结构完整性约束的语法和语义定义,并研究了它们在XML查询优化中的作用.基于子路径的概念,提出了有结构完整性约束的路径表达式的最小化算法.该算法以路径蕴涵闭包为工具,不仅可以删除路径表达式的冗余,还可以识别无效路径表达式.实验结果表明了该算法的正确性和有效性.
2009, 20(11):2988-3000.
摘要:
对互联网覆盖路由相关研究工作进行了调研;按照Internet分层概念重点考查了网络层和传输层的覆盖路由的结构和方法;并且考查了覆盖路由其他相关问题的研究,包括覆盖路由性能的影响因素、多个覆盖网络路由之间的相互作用等.分析了已有研究工作的关键技术的优缺点.最后讨论了未来可能的研究方向,为互联网覆盖路由的研究提供参考.
对互联网覆盖路由相关研究工作进行了调研;按照Internet分层概念重点考查了网络层和传输层的覆盖路由的结构和方法;并且考查了覆盖路由其他相关问题的研究,包括覆盖路由性能的影响因素、多个覆盖网络路由之间的相互作用等.分析了已有研究工作的关键技术的优缺点.最后讨论了未来可能的研究方向,为互联网覆盖路由的研究提供参考.
2009, 20(11):3001-3009.
摘要:
近年来,双线性对获得了广泛的密码应用.实现这些应用的效率,取决于双线性对的计算速度.分类回顾了双线性对有效计算方面的已有进展,并提出了进一步工作的可能性.
近年来,双线性对获得了广泛的密码应用.实现这些应用的效率,取决于双线性对的计算速度.分类回顾了双线性对有效计算方面的已有进展,并提出了进一步工作的可能性.
2009, 20(11):3010-3022.
摘要:
深入研究了UWB(ultra wideband)无线传感器网络中基于匹配滤波门限检测的TOA(time of arrival)估计算法.针对现有算法的不足,提出了一种三步TOA估计算法:先确定DP(direct path)搜索区域,然后使用门限检测确定DP的粗略位置,最后精确搜索到DP的中心.其中,用于计算检测门限的门限因子依据匹配滤波输出的峭度动态设置,设置模型独立于信道模式,其正确性通过与使用固定门限因子所获得的性能对比进行了验证.与其他算法的性能对比仿真结果表明,所提出的三步TOA估计算法在运算效率和TOA估计精度上取得了较好折衷,适合于当前实际应用.还通过对TOA估计误差的统计分析讨论了测距结果的可信度:依据峭度将测距结果划分为可信和不可信两个级别,并为各级别的TOA估计误差分别了建立概率密度模型.在定位模块中有效利用这些可信度信息,可进一步提高定位精度.
深入研究了UWB(ultra wideband)无线传感器网络中基于匹配滤波门限检测的TOA(time of arrival)估计算法.针对现有算法的不足,提出了一种三步TOA估计算法:先确定DP(direct path)搜索区域,然后使用门限检测确定DP的粗略位置,最后精确搜索到DP的中心.其中,用于计算检测门限的门限因子依据匹配滤波输出的峭度动态设置,设置模型独立于信道模式,其正确性通过与使用固定门限因子所获得的性能对比进行了验证.与其他算法的性能对比仿真结果表明,所提出的三步TOA估计算法在运算效率和TOA估计精度上取得了较好折衷,适合于当前实际应用.还通过对TOA估计误差的统计分析讨论了测距结果的可信度:依据峭度将测距结果划分为可信和不可信两个级别,并为各级别的TOA估计误差分别了建立概率密度模型.在定位模块中有效利用这些可信度信息,可进一步提高定位精度.
2009, 20(11):3023-3033.
摘要:
在综合考虑传感器网络中节点链路接入、数据包传输能耗及节点剩余能量的基础上,提出了一种自适应能耗均衡路由策略,并给出了相应的数学最优化模型及求解算法.优化的目标是均衡网络能耗,进而最大化网络寿命.首先采用跨层分析的方法设计了符合传感器节点计算能力的分布式动态路由树生成算法及各节点的路由选择策略函数;然后通过构造一个双层规划模型使传感器网络的整体能耗趋向均衡,尽可能地延长网络寿命.一个数值例子说明,提出的路由选择策略、双层规划模型及求解算法是可行且有效的.
在综合考虑传感器网络中节点链路接入、数据包传输能耗及节点剩余能量的基础上,提出了一种自适应能耗均衡路由策略,并给出了相应的数学最优化模型及求解算法.优化的目标是均衡网络能耗,进而最大化网络寿命.首先采用跨层分析的方法设计了符合传感器节点计算能力的分布式动态路由树生成算法及各节点的路由选择策略函数;然后通过构造一个双层规划模型使传感器网络的整体能耗趋向均衡,尽可能地延长网络寿命.一个数值例子说明,提出的路由选择策略、双层规划模型及求解算法是可行且有效的.
2009, 20(11):3034-3044.
摘要:
针对组播协议在大规模分布式交互系统应用中面临的可扩展性问题,提出一种基于内容的双向共享组播路由协议CBSMRP(content-based bi-directional shared multicast routing protocol).该协议结合运用了主动路由思想和基于内容的发布-订购模式,在基于CBT(core-based tree)结构的双向共享组播树中,根据数据包的内容实现主动路由和双向过滤,不仅解决了组播地址的维护和分配等问题,而且能够有效地减轻系统的网络负载.仿真实验及实际应用表明,该协议具有较好的扩展性,能够满足大规模分布式交互系统的网络通信要求.
针对组播协议在大规模分布式交互系统应用中面临的可扩展性问题,提出一种基于内容的双向共享组播路由协议CBSMRP(content-based bi-directional shared multicast routing protocol).该协议结合运用了主动路由思想和基于内容的发布-订购模式,在基于CBT(core-based tree)结构的双向共享组播树中,根据数据包的内容实现主动路由和双向过滤,不仅解决了组播地址的维护和分配等问题,而且能够有效地减轻系统的网络负载.仿真实验及实际应用表明,该协议具有较好的扩展性,能够满足大规模分布式交互系统的网络通信要求.
2009, 20(11):3045-3059.
摘要:
实验表明,无线传感网的链路存在短时时变特性.链路估计方法对中长时链路变化具有路由指示能力,而对短时变化链路表现不佳.在精细梯度模型下提出一种基于ARQ(automatic repeat-request)的多链路协同转发协议(multi-link cooperative forwarding protocol on fine-grain gradient strategy,简称MCFS),通过单发多收和基于随机同步竞争窗的自举应答算法来消除链路短时变化的影响.通过基于非齐次马尔可夫链的短时时变链路模型上的NS2仿真,实验结果表明:MCFS协议能够有效适应短时链路变化;在可控条件下,具有比基于HOP/PRR的单链路优化协议、分离和缠绕多路径更好的网络抵达率和能量效率;这种性能优势与网络规模和部署密度无关.
实验表明,无线传感网的链路存在短时时变特性.链路估计方法对中长时链路变化具有路由指示能力,而对短时变化链路表现不佳.在精细梯度模型下提出一种基于ARQ(automatic repeat-request)的多链路协同转发协议(multi-link cooperative forwarding protocol on fine-grain gradient strategy,简称MCFS),通过单发多收和基于随机同步竞争窗的自举应答算法来消除链路短时变化的影响.通过基于非齐次马尔可夫链的短时时变链路模型上的NS2仿真,实验结果表明:MCFS协议能够有效适应短时链路变化;在可控条件下,具有比基于HOP/PRR的单链路优化协议、分离和缠绕多路径更好的网络抵达率和能量效率;这种性能优势与网络规模和部署密度无关.
2009, 20(11):3060-3076.
摘要:
提出了一种基于逻辑的信任多集方法,它与已有的密码协议安全性分析方法本质上不同:每个参与主体建立的新信任只应依赖于该主体已拥有的信任和接收或发送的包含了信任的新鲜性标识符的消息本身.在基于匹配对话和不可区分性的计算模型下,证明了给出的保证密码协议单方认证安全、双方认证安全、单方密钥安全和双方密钥安全的充分必要条件分别满足4个可证安全定义.实例研究和对比分析表明,信任多集方法有以下特点:首先,安全性分析结果要么证明了一个密码协议是安全的,要么指出了密码协议安全属性的缺失,由安全属性的缺失能够直接导出构造攻击的结构;其次,分析方法与密码协议和攻击者能力的具体形式化描述无关;最后,不仅可用于手工分析,而且便于开发出自动验证系统.
提出了一种基于逻辑的信任多集方法,它与已有的密码协议安全性分析方法本质上不同:每个参与主体建立的新信任只应依赖于该主体已拥有的信任和接收或发送的包含了信任的新鲜性标识符的消息本身.在基于匹配对话和不可区分性的计算模型下,证明了给出的保证密码协议单方认证安全、双方认证安全、单方密钥安全和双方密钥安全的充分必要条件分别满足4个可证安全定义.实例研究和对比分析表明,信任多集方法有以下特点:首先,安全性分析结果要么证明了一个密码协议是安全的,要么指出了密码协议安全属性的缺失,由安全属性的缺失能够直接导出构造攻击的结构;其次,分析方法与密码协议和攻击者能力的具体形式化描述无关;最后,不仅可用于手工分析,而且便于开发出自动验证系统.
2009, 20(11):3077-3085.
摘要:
移动Ad hoc网络路由质量受到很多因素的影响.目前,多数移动Ad hoc网络路由协议利用单一跳数或其他基准作为路由产生的判据,使得协议整体性能的改善比较困难.提出一种考虑节点能量、通信干扰、丢失率和移动性(energy, interference, communication drop rate and mobility,简称EIDM)的综合选路基准.使用自适应权重,该基准能够根据网络状态调节各因子的作用.模拟实验结果显示,EIDM很好地减缓了热点效应.
移动Ad hoc网络路由质量受到很多因素的影响.目前,多数移动Ad hoc网络路由协议利用单一跳数或其他基准作为路由产生的判据,使得协议整体性能的改善比较困难.提出一种考虑节点能量、通信干扰、丢失率和移动性(energy, interference, communication drop rate and mobility,简称EIDM)的综合选路基准.使用自适应权重,该基准能够根据网络状态调节各因子的作用.模拟实验结果显示,EIDM很好地减缓了热点效应.
2009, 20(11):3086-3100.
摘要:
在大规模移动自组织网中,利用节点位置信息辅助建立路由被认为是一种有效提高无线网络路由可扩展性的方法.提出了一种可扩展与高效的、适用于移动自组织网络的路由算法——分簇覆盖的节点位置信息辅助路由算法(CLAR).CLAR使用如最小簇改变(LCC)算法,建立并保持的单跳分簇结构为拓扑.已有文献证明,LCC是更新成本最小的保持簇头节点密度均一的分簇算法.CLAR利用网络节点的位置信息提高无线网络路由的网络层性能,由目标节点的位置信息预测并构造一个较小的、形状为等腰三角形、矩形或圆形的区域.该区域需保证覆盖目标节点可能存在的位置,且根据源节点与目标节点间的相对位置决定该区域适宜的形状,从而限制源节点在一个较小的“请求域”内寻找可用路由,而不是在网络内盲目寻找.仿真实验结果表明,与其他路由算法相比较,CLAR路由算法在路由建立所需时长、路由代价、平均时延及数据包冲突等参数上表现优良.同时,算法保持了低平均时延、高数据包到达率、低控制开销及低路由寻找次数等优势.
在大规模移动自组织网中,利用节点位置信息辅助建立路由被认为是一种有效提高无线网络路由可扩展性的方法.提出了一种可扩展与高效的、适用于移动自组织网络的路由算法——分簇覆盖的节点位置信息辅助路由算法(CLAR).CLAR使用如最小簇改变(LCC)算法,建立并保持的单跳分簇结构为拓扑.已有文献证明,LCC是更新成本最小的保持簇头节点密度均一的分簇算法.CLAR利用网络节点的位置信息提高无线网络路由的网络层性能,由目标节点的位置信息预测并构造一个较小的、形状为等腰三角形、矩形或圆形的区域.该区域需保证覆盖目标节点可能存在的位置,且根据源节点与目标节点间的相对位置决定该区域适宜的形状,从而限制源节点在一个较小的“请求域”内寻找可用路由,而不是在网络内盲目寻找.仿真实验结果表明,与其他路由算法相比较,CLAR路由算法在路由建立所需时长、路由代价、平均时延及数据包冲突等参数上表现优良.同时,算法保持了低平均时延、高数据包到达率、低控制开销及低路由寻找次数等优势.
联系方式
- 《软件学报 》
- 主办单位：中国科学院软件研究所
中国计算机学会 - 邮编：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
技术支持：北京勤云科技发展有限公司
