基于n维空间模型的计算网格资源查找方法 06.pdf 论文
需积分: 0 166 浏览量
2009-07-31
20:30:57
上传
评论
收藏 169KB PDF 举报
收稿日期 : 2005 - 12 - 15
作者简介 :张树东
(
1969 -
)
,男 ,河北唐山人 ,博士 ,主要研究方向 :计算机网络、分布式计算 ; 曹元大
(
1944 -
)
,男 ,江苏人 ,教授 ,博士生
导师 ,主要研究方向 :计算机网络、人工智能 ; 廖乐健
(
1962 -
)
,男 ,湖北人 ,教授 ,博士生导师 ,主要研究方向 :人工智能、Web服务.
文章编号 : 1001 - 9081
(
2006
)
06Z - 0188 - 02
基于 n维空间模型的计算网格资源查找方法
张树东
1
,曹元大
2
,廖乐健
2
(
1. 中国科学院 软件研究所 ,北京 100080; 2. 北京理工大学 计算机学院 ,北京 100081
)
(
Shudong@ ios. cn
)
摘 要 :提出了描述计算网格资源的空间模型 , 按网格资源的性质将网格资源组织在 n维空间
中 , 并按资源之间的相似程度对资源进行关联 , 该模型不需建立资源的全局视图 , 系统复杂度不会
随着资源数量的增加而增大。基于资源空间模型的资源查找算法能够保证资源查找沿着正确的方向
进行 , 从而提高资源搜索效率。同时还给出了该算法的时间复杂和空间复杂度分析。
关键词 :计算网格 ;资源查找 ;空间模型
中图分类号 : TP393. 09 文献标识码 : A
网格是把地理位置上分散的资源集成在一起的基础设
施。通过网络连接起来的任何能提供服务的事物均可称之为
网格资源 , 提供通讯服务的网络也是一种网格资源 。高性能
计算是网格的一个重要应用 , 这种应用于计算的网格叫做计
算网格。本文的目的是研究计算网格下计算资源的查找问
题 , 涉及到的资源特指计算资源 。在网格环境下资源数量
多 , 地域分布广 , 需要一种有效的资源查找方法解决资源的
快速定位问题。
1 现有资源查找方法
现有网格系统中 ,资源查找主要有三种方式 :穷举查找方
法、集中查找方法和基于路由转发机制的资源查找算法。下
面给出这三种算法的简要描述。
集中查找算法
对于集中查找方法来说 , 网格系统拥有一个全局的网格
信息中心 ,该中心存储着所有资源节点的位置信息和资源与
资源节点的位置信息。在资源查找时 , 直接访问网格信息中
心 , 查找所需的资源。
穷举查找算法
对于穷举查找方法来说 , 系统中每个节点存储着所有资
源节点的位置信息 , 不包括资源与资源节点之间的对应关
系。在资源查找时 , 逐个访问各个资源节点 , 直至找到所需
的资源。
基于路由转发机制的资源查找算法
对于基于路由转发机制的资源查找方法来说 , 系统中的
每个节点都存放着所有资源的路由信息。在资源查找时 , 系
统按资源路由表中的信息 , 访问相邻的网格节点 , 直至找到
所需的网格资源。
集中查找方发简单、便捷 ,系统容易构建。但单一的网格
信息中心容易造成单点故障 , 另外 ,随着系统规模的扩大 ,
中心节点很可能造成系统的性能瓶颈和网络拥塞。穷举查找
算法和基于路由转发机制的资源查找算法虽然能够解决单点
问题 , 但系统需要维护全局网格视图 , 当网格系统规模非常
大时 , 全局网格视图的维护是非常困难的。另外穷举查找算
法的效率比较低。
2 网格资源的空间模型
2. 1 模型定义
在计算网格系统中 , 网格计算资源可以由 CPU速度 、内
存大小、磁盘空间大小、操作系统等参数进行描述。
定义 1 网格资源空间
假定用于描述网格计算资源的参数的个数为 n, n是一
个不是很大的正整数 , 这些参数之间彼此正交 , 这样网格计
算资源可以看成 n维实线性空间 , 用 R
n
表示。如果在其上面
定义内积
δ(
r
i
, r
j
)
,则 R
n
成为一个 n维欧氏空间 , 称为网格资
源空间。
定义 2 网格资源点
网格系统中每个资源对应于网格资源空间 R
n
中的一个
点 , 我们称之为网格资源点。
定义 3 资源相似度
内积
δ(
r
i
, r
j
)
是两个资源点在 R
n
中的距离,代表两个网格
资源之间的相似度。距离越小表示资源之间的相似程度越大。
对每个资源点来说可以建立以自己为中心的虚拟坐标
系 ,该坐标系的各坐标轴与空间参考坐标系的各坐标轴平行 ,
这样虚拟坐标轴将 R
n
分割成 2
n
各子区域 , 用 R
a
1
, R
a
2
, …,
R
a
n
,在每个子区域中找出与该资源点距离最近的一个资源点
作为资源查找的关联点。资源的查找沿着查找关联点进行。
2. 2 局部最优问题
设 a, c是 R
n
中的两个资源点 , 资源点 a在 2
n
各子区域中
的资源关联点为 a
1
, a
2
, …, a
2
n
,则 a, c和 a
i
(
i ∈ [1, 2, …, 2
n
)
可构成一个三角形
(
如图 1
(
a
)
所示
)
或成一条直线。
图 1 构成的三角形
当 a, c, a
i
成一条直线时 , 由于 a
i
时是该方向离 a最近的
点 , 所以这三点的排列顺序只有下面两种情况 : c a a
i
(
如图
1
(
b
)
所示
)
和 c a
i
a
(
如图 1
(
c
)
所示
)
。
第 26卷
2006年 6月
计算机应用
Computer Applications
Vol. 26
June 2006
© 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
评论0