2004年第15卷第5期文章目次
2004, 15(5):633-640.
摘要:
传统相似性查询的维数约简方法导致时间序列的非线性和分形这些重要特征消失,基于小波变换的匹配方法是通过某一分辨级的距离标准来度量相似性.但是,在未知非平稳时间序列分形维数的情况下,序列相似性匹配的局部误差就会增大,曲线形状的相似性查询过程在一定程度上也因此受到影响.鉴于随机非平稳时间序列在时空动力学演化过程中呈现出非线性特征和分形特征,提出了序列分形时变维数的概念,原始分数布朗运动模型被加以改造成为一个具有局部自相似性的随机过程.给出了时变Hurst指数的估计式和算法,提出了一种新的序列相似性判别标准.在某一分辨级水平上进行曲线形状的相似性查询和度量,同时,对于局部相似性的局部维数曲线进行匹配.最后,用仿真算例对方法的有效性加以验证.
传统相似性查询的维数约简方法导致时间序列的非线性和分形这些重要特征消失,基于小波变换的匹配方法是通过某一分辨级的距离标准来度量相似性.但是,在未知非平稳时间序列分形维数的情况下,序列相似性匹配的局部误差就会增大,曲线形状的相似性查询过程在一定程度上也因此受到影响.鉴于随机非平稳时间序列在时空动力学演化过程中呈现出非线性特征和分形特征,提出了序列分形时变维数的概念,原始分数布朗运动模型被加以改造成为一个具有局部自相似性的随机过程.给出了时变Hurst指数的估计式和算法,提出了一种新的序列相似性判别标准.在某一分辨级水平上进行曲线形状的相似性查询和度量,同时,对于局部相似性的局部维数曲线进行匹配.最后,用仿真算例对方法的有效性加以验证.
2004, 15(5):641-649.
摘要:
在模拟集成电路设计中,关于X轴和y轴同时对称的Stack,以及模块之间的合并,对于增加器件之间的匹配和控制寄生是至关重要的.描述了模拟集成电路二轴对称Stack生成算法和模块合并算法.通过对于对称欧拉图和对称欧拉路径的研究,得出了多项理论结果.在此基础上,提出了时间复杂度为O(n)的伪器件插入算法、对称欧拉路径构造算法和二轴对称Stack生成算法.生成的Stack,不但关于X轴和y轴对称,而且具有公共质心(commoncentroid)的结构.还描述了模块合并算法,给出了计算最大合并距离的公式.该算法本质上是独立于任何拓扑表示的.实验结果验证了算法的有效性.
在模拟集成电路设计中,关于X轴和y轴同时对称的Stack,以及模块之间的合并,对于增加器件之间的匹配和控制寄生是至关重要的.描述了模拟集成电路二轴对称Stack生成算法和模块合并算法.通过对于对称欧拉图和对称欧拉路径的研究,得出了多项理论结果.在此基础上,提出了时间复杂度为O(n)的伪器件插入算法、对称欧拉路径构造算法和二轴对称Stack生成算法.生成的Stack,不但关于X轴和y轴对称,而且具有公共质心(commoncentroid)的结构.还描述了模块合并算法,给出了计算最大合并距离的公式.该算法本质上是独立于任何拓扑表示的.实验结果验证了算法的有效性.
2004, 15(5):650-659.
摘要:
算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n3).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ2≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og2(n)+3log2(1/σ)+log2log2n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og2n+3log2(1/σ)+4√2+log2n+log2(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n2)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og2n+3log2(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.
算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n3).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ2≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og2(n)+3log2(1/σ)+log2log2n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og2n+3log2(1/σ)+4√2+log2n+log2(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n2)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og2n+3log2(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.
2004, 15(5):660-665.
摘要:
低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高.
低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高.
2004, 15(5):666-675.
摘要:
提出了一种由3幅图像间一组对应消失线进行度量重建的方法.首先利用对应的消失线和模值约束计算出无穷远平面的单应矩阵,然后根据无穷远平面的单应矩阵保持绝对二次曲线的像不动的性质,线性求解摄像机内参数,最后得到度量重建.模拟实验和真实图像实验均验证了这种度量重建方法的可行性和正确性.
提出了一种由3幅图像间一组对应消失线进行度量重建的方法.首先利用对应的消失线和模值约束计算出无穷远平面的单应矩阵,然后根据无穷远平面的单应矩阵保持绝对二次曲线的像不动的性质,线性求解摄像机内参数,最后得到度量重建.模拟实验和真实图像实验均验证了这种度量重建方法的可行性和正确性.
2004, 15(5):676-688.
摘要:
主要讨论两方面的工作.首先,对三视校正问题进行理论分析,给出了校正后图像的基本矩阵与其约束条件之间的关系,讨论了三视校正过程中的6个自由参数的几何含义.这些结果为处理校正过程中带来的图像射影畸变提供了理论根据.其次,在RANSAC(random sampling consensus)框架下,提出了一种鲁棒的三视校正算法.与传统的校正算法不同,该算法不再只依赖于基本矩阵,而是直接利用了原始匹配点的信息.这种基于点的方法有两个优点:一方面,由于噪声的干扰,基本矩阵往往估计得不够准确;另一方面,由于基本矩阵的评价准则与校正结果的评价准则不同,即使从好的基本矩阵出发,也未必能获得好的校正结果.大量的模拟和真实图像实验表明,该算法具有很强的抗噪声及抗错误匹配的能力,能够获得令人满意的校正效果.
主要讨论两方面的工作.首先,对三视校正问题进行理论分析,给出了校正后图像的基本矩阵与其约束条件之间的关系,讨论了三视校正过程中的6个自由参数的几何含义.这些结果为处理校正过程中带来的图像射影畸变提供了理论根据.其次,在RANSAC(random sampling consensus)框架下,提出了一种鲁棒的三视校正算法.与传统的校正算法不同,该算法不再只依赖于基本矩阵,而是直接利用了原始匹配点的信息.这种基于点的方法有两个优点:一方面,由于噪声的干扰,基本矩阵往往估计得不够准确;另一方面,由于基本矩阵的评价准则与校正结果的评价准则不同,即使从好的基本矩阵出发,也未必能获得好的校正结果.大量的模拟和真实图像实验表明,该算法具有很强的抗噪声及抗错误匹配的能力,能够获得令人满意的校正效果.
2004, 15(5):689-696.
摘要:
团队是动态不可预测性环境下协作问题求解的有效方式,联合意图是团队联合求解的关键.因此,主体在团队活动中如何采用言语动作形成、维护、解除联合意图,是一个值得研究的重要问题.旨在设计一种基于主体通信语言FIPA(foundation forintelligent physical Agent)ACL(Agent communication language)的多主体团队交互协议.首先,分析了现有FIPA ACL支持团队联合求解的充分性问题.在概念上明确区分了联合请求与委托请求,指出委托请求言语动作不能充分支持团队协作.并扩展定义了联合请求,讨论了相关定理.然后,基于联合请求动作,提出一种主体团队交互协议,并给出了协议的形式化语义,最后讨论了协议的实际应用.区别于现有的基本动作请求协议、合同网协议以及拍卖协议,团队交互协议描述了另一类主体交互模式,对主体交互模块的设计具有指导意义.
团队是动态不可预测性环境下协作问题求解的有效方式,联合意图是团队联合求解的关键.因此,主体在团队活动中如何采用言语动作形成、维护、解除联合意图,是一个值得研究的重要问题.旨在设计一种基于主体通信语言FIPA(foundation forintelligent physical Agent)ACL(Agent communication language)的多主体团队交互协议.首先,分析了现有FIPA ACL支持团队联合求解的充分性问题.在概念上明确区分了联合请求与委托请求,指出委托请求言语动作不能充分支持团队协作.并扩展定义了联合请求,讨论了相关定理.然后,基于联合请求动作,提出一种主体团队交互协议,并给出了协议的形式化语义,最后讨论了协议的实际应用.区别于现有的基本动作请求协议、合同网协议以及拍卖协议,团队交互协议描述了另一类主体交互模式,对主体交互模块的设计具有指导意义.
2004, 15(5):697-705.
摘要:
在信息处理研究领域,现有的大多数聚类算法都需要人为地给出一些参数.然而,在没有先验知识的情况下,人为地确定这些参数是十分困难的,而且现有的聚类算法的时空效率也有待于进一步提高.为了解决这一难题,首先根据样本分布特性,通过数学分析,得到确定样本空间划分间隔数的数学函数,然后,再根据样本分布特性,采用爬山的策略得到样本类的划分,最后提出了一种实用而高效的聚类算法.从多个角度分析了该算法的性能,并将该算法应用于中文文本聚类.理论分析和应用结果都表明,该算法不仅不需要人为确定参数,同时,还可以提高信息处理的时空效率和性能.
在信息处理研究领域,现有的大多数聚类算法都需要人为地给出一些参数.然而,在没有先验知识的情况下,人为地确定这些参数是十分困难的,而且现有的聚类算法的时空效率也有待于进一步提高.为了解决这一难题,首先根据样本分布特性,通过数学分析,得到确定样本空间划分间隔数的数学函数,然后,再根据样本分布特性,采用爬山的策略得到样本类的划分,最后提出了一种实用而高效的聚类算法.从多个角度分析了该算法的性能,并将该算法应用于中文文本聚类.理论分析和应用结果都表明,该算法不仅不需要人为确定参数,同时,还可以提高信息处理的时空效率和性能.
2004, 15(5):706-711.
摘要:
在限时条件下的Agent之间的多议题协商中,最差的结果是没有达成协定.由于某一个议题没有达到平衡点而使得整个协商失败是影响协商效用的一个重要因素.给出了一个多议题整合效用评估机制,利用多议题整合效用中各议题因子之间的相关性进行保留值向量的等效置换,优化协商效用评估,在保证协商参与者整体协商效用的前提下动态放宽某个议题的保留值,促使协商双方避免协商僵局,快速达成一致的协定.实验数据表明,该机制有效地解决了协商僵局问题,提高了协商的成功率.
在限时条件下的Agent之间的多议题协商中,最差的结果是没有达成协定.由于某一个议题没有达到平衡点而使得整个协商失败是影响协商效用的一个重要因素.给出了一个多议题整合效用评估机制,利用多议题整合效用中各议题因子之间的相关性进行保留值向量的等效置换,优化协商效用评估,在保证协商参与者整体协商效用的前提下动态放宽某个议题的保留值,促使协商双方避免协商僵局,快速达成一致的协定.实验数据表明,该机制有效地解决了协商僵局问题,提高了协商的成功率.
2004, 15(5):712-719.
摘要:
传统索引方法对高维数据存在"维数灾难"的困难.而对数据分布的精确描述及对数据空间的有效划分是高维索引机制中的关键问题.提出一种基于矢量量化的索引方法.该方法使用高斯混合模型描述数据的整体分布,并训练优化的矢量量化器划分数据空间.高斯混合模型能更好地描述真实图像库的数据分布;而矢量量化的划分方法可以充分利用维之间的统计相关性,能够对数据向量构造出更加精确的近似表示,从而提高索引结构的过滤效率并减少需要访问的数据向量.在大容量真实图像库上的实验表明,该方法显著减少了支配检索时间的I/O开销,提高了索引性能.
传统索引方法对高维数据存在"维数灾难"的困难.而对数据分布的精确描述及对数据空间的有效划分是高维索引机制中的关键问题.提出一种基于矢量量化的索引方法.该方法使用高斯混合模型描述数据的整体分布,并训练优化的矢量量化器划分数据空间.高斯混合模型能更好地描述真实图像库的数据分布;而矢量量化的划分方法可以充分利用维之间的统计相关性,能够对数据向量构造出更加精确的近似表示,从而提高索引结构的过滤效率并减少需要访问的数据向量.在大容量真实图像库上的实验表明,该方法显著减少了支配检索时间的I/O开销,提高了索引性能.
2004, 15(5):720-729.
摘要:
结构连接是XML查询处理的核心操作,受到了研究界的关注.高效的算法是高效查询处理的关键.目前已经提出了许多结构连接的算法,它们中的大多数都基于如下的前提条件之一:输入元素集合存在索引或者有序.当这些条件不成立时，由于对输入数据临时排序或建索引的代价，这些算法的性能会大大下降.基于这样的观察，提出了一种基于区域划分的结构连接算法.该算法基于任务分解的思想，利用区域编码的特点对输入集合进行划分.给出了详细的算法设计，并对算法的I/O复杂性进行了分析.大量的实验结果显示，该算法具有良好的 性能，在输入数据无序或没有索引的情况下优于现有的排序合并算法，可以为查询计划提供更多的选择.
结构连接是XML查询处理的核心操作,受到了研究界的关注.高效的算法是高效查询处理的关键.目前已经提出了许多结构连接的算法,它们中的大多数都基于如下的前提条件之一:输入元素集合存在索引或者有序.当这些条件不成立时，由于对输入数据临时排序或建索引的代价，这些算法的性能会大大下降.基于这样的观察，提出了一种基于区域划分的结构连接算法.该算法基于任务分解的思想，利用区域编码的特点对输入集合进行划分.给出了详细的算法设计，并对算法的I/O复杂性进行了分析.大量的实验结果显示，该算法具有良好的 性能，在输入数据无序或没有索引的情况下优于现有的排序合并算法，可以为查询计划提供更多的选择.
2004, 15(5):730-740.
摘要:
对Tari等人提出的面向对象数据模型规范化理论的基本思想进行了介绍,分析了他们给出的对象范式生成方法,指出了这些方法所存在的问题.为了研究新的对象范式生成方法,对有向图顶点的含义进行了扩充,使其不仅可以是一个简单的顶点,还可以是一个有向图.基于这种扩充有向图,提出了一种对象范式生成算法,并给出了算法的时间复杂度分析和正确性证明.
对Tari等人提出的面向对象数据模型规范化理论的基本思想进行了介绍,分析了他们给出的对象范式生成方法,指出了这些方法所存在的问题.为了研究新的对象范式生成方法,对有向图顶点的含义进行了扩充,使其不仅可以是一个简单的顶点,还可以是一个有向图.基于这种扩充有向图,提出了一种对象范式生成算法,并给出了算法的时间复杂度分析和正确性证明.
2004, 15(5):741-751.
摘要:
网络化存储通过引入网络的概念将存储独立于服务器甚至通信网络,已经成为传统存储方式的有力替代者.然而,FC-SAN虚拟存储方式的存储性能依赖于存储对象的某些属性,在某些情况下,其性能甚至不如传统的LAN数据共享方式.就FC-SAN虚拟存储方式中的数据放置和访问路径选择对这一问题进行了研究.首先通过分析虚拟存储原理提出了一个数据访问耗时的线性模型;然后,就数据放置和访问路径选择提出了一个决策方法;并在进一步探讨这一方法的过程中，定义了“虚拟存储代价当量”的概念，用以评价FC-SAN虚拟存储环境中的数据放置的代价，从而为评价以及如何选择数据放置和访问路径提供了一种定量的手段.最后，在数字图书馆的一个海量存储原型系统中对上述的理论分析、各种条件进行了实验验证，并结合实际给出了“虚拟存储代价当量”的计算方法，验证了所提出的方法的有效性.
网络化存储通过引入网络的概念将存储独立于服务器甚至通信网络,已经成为传统存储方式的有力替代者.然而,FC-SAN虚拟存储方式的存储性能依赖于存储对象的某些属性,在某些情况下,其性能甚至不如传统的LAN数据共享方式.就FC-SAN虚拟存储方式中的数据放置和访问路径选择对这一问题进行了研究.首先通过分析虚拟存储原理提出了一个数据访问耗时的线性模型;然后,就数据放置和访问路径选择提出了一个决策方法;并在进一步探讨这一方法的过程中，定义了“虚拟存储代价当量”的概念，用以评价FC-SAN虚拟存储环境中的数据放置的代价，从而为评价以及如何选择数据放置和访问路径提供了一种定量的手段.最后，在数字图书馆的一个海量存储原型系统中对上述的理论分析、各种条件进行了实验验证，并结合实际给出了“虚拟存储代价当量”的计算方法，验证了所提出的方法的有效性.
2004, 15(5):752-756.
摘要:
与普通的数字签名不同,验证者要知道一个证实数字签名的有效性,必须得到一个称为证实者的第三方的合作与帮助.但除了签名者,其他任何人(包括证实者)都不能以签名者的名义产生有效的证实签名.同时,只要参与了验证,证实者就不能欺骗验证者.进一步地,在必要的时候,证实者还可以将证实签名转化为普通的数字签名,从而使得任何人都可以验证这些签名的有效性.王尚平等学者提出了一个基于DSA和RSA的证实数字签名方案,并认为他们的方案是安全而高效的.与现有的具体方案相比,他们的方案确实是高效的.但是,这一方案存在严重的安全缺陷,从而使得他们的尝试是不成功的.
与普通的数字签名不同,验证者要知道一个证实数字签名的有效性,必须得到一个称为证实者的第三方的合作与帮助.但除了签名者,其他任何人(包括证实者)都不能以签名者的名义产生有效的证实签名.同时,只要参与了验证,证实者就不能欺骗验证者.进一步地,在必要的时候,证实者还可以将证实签名转化为普通的数字签名,从而使得任何人都可以验证这些签名的有效性.王尚平等学者提出了一个基于DSA和RSA的证实数字签名方案,并认为他们的方案是安全而高效的.与现有的具体方案相比,他们的方案确实是高效的.但是,这一方案存在严重的安全缺陷,从而使得他们的尝试是不成功的.
2004, 15(5):757-766.
摘要:
安全性是移动自组网络组通信的基本需求,安全、高效的组密钥更新算法是保证组通信安全的关键.在移动自组网络分布式组密钥管理框架(distrbuted group key management framework,简称DGKMF)的基础上,提出了一种组密钥更新算法--DGR(distributed group rekeying)算法.该算法能够利用局部密钥信息更新组密钥,适合拓扑结构变化频繁、连接短暂、带宽有限的移动自组网络.为了进一步降低算法的通信代价,通过在组密钥更新时动态生成组密钥更新簇，对DGR算法进行了改进，提出了CDGR(cluster distributed group rekeying)算法，并讨论了上述算法的安全性、正确性和完备性，分析了算法的通信代价.最后，利用ns2模拟器对算法的性能进行了分析.模拟结果显示，DGR和CDGR算法在组密钥更新成功率和延迟等方面均优于其他算法，并且由于采用簇结构，CDGR算法的更新延迟低于DGR算法.
安全性是移动自组网络组通信的基本需求,安全、高效的组密钥更新算法是保证组通信安全的关键.在移动自组网络分布式组密钥管理框架(distrbuted group key management framework,简称DGKMF)的基础上,提出了一种组密钥更新算法--DGR(distributed group rekeying)算法.该算法能够利用局部密钥信息更新组密钥,适合拓扑结构变化频繁、连接短暂、带宽有限的移动自组网络.为了进一步降低算法的通信代价,通过在组密钥更新时动态生成组密钥更新簇，对DGR算法进行了改进，提出了CDGR(cluster distributed group rekeying)算法，并讨论了上述算法的安全性、正确性和完备性，分析了算法的通信代价.最后，利用ns2模拟器对算法的性能进行了分析.模拟结果显示，DGR和CDGR算法在组密钥更新成功率和延迟等方面均优于其他算法，并且由于采用簇结构，CDGR算法的更新延迟低于DGR算法.
2004, 15(5):767-771.
摘要:
Subhayan Sen等人提出了一个基于细胞自动机的分组密码系统(cellular automata based cryptosystem,简称CAC),但并没有给出CAC的某些构造模块的细节描述,从应用角度考虑,将其中的一个模块固定得到CAC的变形--SMCAC(samemajor-CACAC).对SMCAC进行密码分析,结果表明,CAC的这种变形在选择明文攻击下是极不安全的.对SMCAC进行分析的意义在于,知道CAC的具体设计细节以后,借鉴对SMCAC的分析,有可能对CAC密码系统本身的安全性造成威胁.
Subhayan Sen等人提出了一个基于细胞自动机的分组密码系统(cellular automata based cryptosystem,简称CAC),但并没有给出CAC的某些构造模块的细节描述,从应用角度考虑,将其中的一个模块固定得到CAC的变形--SMCAC(samemajor-CACAC).对SMCAC进行密码分析,结果表明,CAC的这种变形在选择明文攻击下是极不安全的.对SMCAC进行分析的意义在于,知道CAC的具体设计细节以后,借鉴对SMCAC的分析,有可能对CAC密码系统本身的安全性造成威胁.
2004, 15(5):772-782.
摘要:
随着远程会议、远程教育和交互式仿真等分布式多媒体应用的兴起,组播技术受到网络研究人员的重视.而这些应用的QoS(quality of service)需求又进一步推动了QoS敏感的组播路由协议的发展.在已提出的各种QoS组播路由协议中,如何提高呼叫成功率、增强规模伸缩性、降低控制报文开销,仍然是一个有待探索的问题.提出了一个新的QoS组播路由协议,其基本思想是使路由器只存储其两层邻居节点的可达性信息以及链路的QoS状态信息,以减少路由器存储开销,提高协议的规模伸缩性(scalability).协议采用受限的泛播技术,构造了一个接受节点发起的、采用多路径技术的、分布式路由算法.描述了协议的数据结构、组播树的构造算法,并给出了模拟实验结果.分析表明,基于受限泛播技术的组播路由协议具有节点存储开销小、呼叫接收成功率高等特点.虽然该协议付出了泛播引起的额外带宽开销较大的代价,但是由于协议所需要的控制数据总量不大,加上两层存储结构在一定程度上限制了泛播通信量,因此该方案具有很好的性能.
随着远程会议、远程教育和交互式仿真等分布式多媒体应用的兴起,组播技术受到网络研究人员的重视.而这些应用的QoS(quality of service)需求又进一步推动了QoS敏感的组播路由协议的发展.在已提出的各种QoS组播路由协议中,如何提高呼叫成功率、增强规模伸缩性、降低控制报文开销,仍然是一个有待探索的问题.提出了一个新的QoS组播路由协议,其基本思想是使路由器只存储其两层邻居节点的可达性信息以及链路的QoS状态信息,以减少路由器存储开销,提高协议的规模伸缩性(scalability).协议采用受限的泛播技术,构造了一个接受节点发起的、采用多路径技术的、分布式路由算法.描述了协议的数据结构、组播树的构造算法,并给出了模拟实验结果.分析表明,基于受限泛播技术的组播路由协议具有节点存储开销小、呼叫接收成功率高等特点.虽然该协议付出了泛播引起的额外带宽开销较大的代价,但是由于协议所需要的控制数据总量不大,加上两层存储结构在一定程度上限制了泛播通信量,因此该方案具有很好的性能.
2004, 15(5):783-790.
摘要:
n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能.随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对系统中存在链路故障的情况,提出了用于记录最优通路的安全通路向量(safety path vectors,简称SPVs)概念,并给出了建立SPVs及其容错路由算法.其中SPVs的赋值可以通过n-1轮邻节点之间的信息交换来完成,且算法中各节点的存储开销仅为n bits,因此,SPVs是安全向量(SVs)与扩展安全向量(ESVs)的一种扩展,具有比SVs和ESVs更好的记录最优通路的能力.另外，与基于最优通路矩阵(optimal path matrices,简称OPMs)及扩展最优通路矩阵(extended optimal path matrices,简称EOPMs)的容错路由算法相比,SPVs呈指数级地降低了算法的存储开销，且能够记录OPMs和EOPMs所不能记录到的最优通路信息.理论分析和仿真实验验证了SPVs的上述性能.
n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能.随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对系统中存在链路故障的情况,提出了用于记录最优通路的安全通路向量(safety path vectors,简称SPVs)概念,并给出了建立SPVs及其容错路由算法.其中SPVs的赋值可以通过n-1轮邻节点之间的信息交换来完成,且算法中各节点的存储开销仅为n bits,因此,SPVs是安全向量(SVs)与扩展安全向量(ESVs)的一种扩展,具有比SVs和ESVs更好的记录最优通路的能力.另外，与基于最优通路矩阵(optimal path matrices,简称OPMs)及扩展最优通路矩阵(extended optimal path matrices,简称EOPMs)的容错路由算法相比,SPVs呈指数级地降低了算法的存储开销，且能够记录OPMs和EOPMs所不能记录到的最优通路信息.理论分析和仿真实验验证了SPVs的上述性能.
联系方式
- 《软件学报 》
- 主办单位：中国科学院软件研究所
中国计算机学会 - 邮编：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
技术支持：北京勤云科技发展有限公司
