第
38
卷第
6
期
2013
年
6
月
武汉大学学报·信息科学版
Vol. 38 No. 6
June 2013
Geomatics and Information Science of Wuhan University
文章编号:
1671
8860(2013)06
0734 03
文献标志码:
A
空间数据访问规律的动态统计算法
潘少明
1
徐正全
l
刘小俊
l
Cl
武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路
129
号,
430079)
摘
要:根据日志信息得到的静态访问分布,不能真实反映系统当前的访问特征,而大规模分布式节点环境
下,简单的复制和分发将带来不可承载的网络流量。为此,提出一种基于
P2P
的海量空间数据访问分布动态
统计融合算法。通过节点映射和优选算法,充分利用节点闲置资源,优先选择服务能力“好”的节点进行统计
信息的融合。实验表明,该算法能满足大规模节点下空间数据访问分布的动态融合要求,且效率较高。
关键词:空间数据;访问规律;动态统计;全局;
P2P
中图法分类号:
P208
空间数据访问规律可以为空间数据的存储组
织、副本数量及其缓存和预取[
l-4 J
提供依据。
Danyel
提出数字地球系统中的影像瓦片请求符
合幕律分布时,可以很准确地匹配系统的实际运
行状况[
6
],但没有给出具体的分布特征。王浩揭
示了数字地球中影像数据的静态访问规律[汀,但
不能反映动态热点的变化。为提高数据分发性
能,马修军等提出→种
P2P
环境下将空间信息通
过同步复制的机制来保持信息的时效性和一致
性时,但带来了不可承载的网络流量。本文针对
上述问题提出一种新的基于节点代理的
P2P
海
量空间数据访问规律动态统计方法。
1
动态统计模型
1. 1
主要算法思想
P2P
环境下,每个服务器根据其所处范围加
入分组。每个节点都拥有分组内的其他邻居节点
列表,且每隔→个调度周期向分组内其他节点发
送自己的节点信息,称为节点映射(
peer
map,
PM
)。通过交换节点映射,分组内所有节点都可
以由节点列表了解邻居节点能力的分布情况;在
进行统计信息代理分发时,考虑节点带宽、负载和
服务延迟,选择合适的节点提供代理服务。区别
于随机节点选择的统计融合算法
Rand
,称该算法
为
PPC
(peer
providing
capability
)。具体过程
收稿日期:
2013
02
11,
为:
1
)所有节点依据规则加入分组时,分组内部
依据节点能力大小选择一个“好”节点作为代理节
点;所有代理节点依据相同规则继续分组,依次类
推,形成多层代理分组模型;
2
)分组内根据
P2P
的原则进行统计信息的
融合,分组内的融合信息由代理节点在上层分组
内继续融合,最后形成全局统计信息。
代理节点不但为分组内其他服务节点提供动
态统计信息的融合和分发,同时也要为其客户端
提供空间数据访问服务。设服务器节点总个数为
S
,统计的地形数据瓦片总块数为
N
,节点
i
称为
丸。定义节点
i
由一个三元组
<
b;
,q;
,c
;>
描述,
其中
b
;
表示节点带宽;
q
;
表示节点服务请求队列
长度;
C
;
表示节点服务的客户端个数。基于以上
定义,节点映射
PM
则是由不同节点的三元组组
成的内存块,按照<
i,<
b;,q;,c;>,j
,< 鸟,饵,
Cj
〉,…〉的形式组织。
1.2
节点选择算法
由于节点服务能力的差异性,选择一个“合
适”的节点进行统计信息的代理传输,必须在充分
考虑传输速度的同时,尽量降低对“好”节点的负
载。定义
PPC
作为节点选择依据,
PPC
最大的节
点被选择提供代理服务,如果存在相同
PPC
的节
点,则从中随机选择。节点
ρz
的服务能力
PPC
;定
义为:
项目来源:国家自然科学基金资助项目(
41271398
);国家
973
计划资助项目
C2011CB302306
)。
第
38
卷第
6
期
2013
年
6
月
武汉大学学报·信息科学版
Vol. 38 No. 6
June 2013
Geomatics and Information Science of Wuhan University
文章编号:
1671
8860(2013)06
0734 03
文献标志码:
A
空间数据访问规律的动态统计算法
潘少明
1
徐正全
l
刘小俊
l
Cl
武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路
129
号,
430079)
摘
要:根据日志信息得到的静态访问分布,不能真实反映系统当前的访问特征,而大规模分布式节点环境
下,简单的复制和分发将带来不可承载的网络流量。为此,提出一种基于
P2P
的海量空间数据访问分布动态
统计融合算法。通过节点映射和优选算法,充分利用节点闲置资源,优先选择服务能力“好”的节点进行统计
信息的融合。实验表明,该算法能满足大规模节点下空间数据访问分布的动态融合要求,且效率较高。
关键词:空间数据;访问规律;动态统计;全局;
P2P
中图法分类号:
P208
空间数据访问规律可以为空间数据的存储组
织、副本数量及其缓存和预取[
l-4 J
提供依据。
Danyel
提出数字地球系统中的影像瓦片请求符
合幕律分布时,可以很准确地匹配系统的实际运
行状况[
6
],但没有给出具体的分布特征。王浩揭
示了数字地球中影像数据的静态访问规律[汀,但
不能反映动态热点的变化。为提高数据分发性
能,马修军等提出→种
P2P
环境下将空间信息通
过同步复制的机制来保持信息的时效性和一致
性时,但带来了不可承载的网络流量。本文针对
上述问题提出一种新的基于节点代理的
P2P
海
量空间数据访问规律动态统计方法。
1
动态统计模型
1. 1
主要算法思想
P2P
环境下,每个服务器根据其所处范围加
入分组。每个节点都拥有分组内的其他邻居节点
列表,且每隔→个调度周期向分组内其他节点发
送自己的节点信息,称为节点映射(
peer
map,
PM
)。通过交换节点映射,分组内所有节点都可
以由节点列表了解邻居节点能力的分布情况;在
进行统计信息代理分发时,考虑节点带宽、负载和
服务延迟,选择合适的节点提供代理服务。区别
于随机节点选择的统计融合算法
Rand
,称该算法
为
PPC
(peer
providing
capability
)。具体过程
收稿日期:
2013
02
11,
为:
1
)所有节点依据规则加入分组时,分组内部
依据节点能力大小选择一个“好”节点作为代理节
点;所有代理节点依据相同规则继续分组,依次类
推,形成多层代理分组模型;
2
)分组内根据
P2P
的原则进行统计信息的
融合,分组内的融合信息由代理节点在上层分组
内继续融合,最后形成全局统计信息。
代理节点不但为分组内其他服务节点提供动
态统计信息的融合和分发,同时也要为其客户端
提供空间数据访问服务。设服务器节点总个数为
S
,统计的地形数据瓦片总块数为
N
,节点
i
称为
丸。定义节点
i
由一个三元组
<
b;
,q;
,c
;>
描述,
其中
b
;
表示节点带宽;
q
;
表示节点服务请求队列
长度;
C
;
表示节点服务的客户端个数。基于以上
定义,节点映射
PM
则是由不同节点的三元组组
成的内存块,按照<
i,<
b;,q;,c;>,j
,< 鸟,饵,
Cj
〉,…〉的形式组织。
1.2
节点选择算法
由于节点服务能力的差异性,选择一个“合
适”的节点进行统计信息的代理传输,必须在充分
考虑传输速度的同时,尽量降低对“好”节点的负
载。定义
PPC
作为节点选择依据,
PPC
最大的节
点被选择提供代理服务,如果存在相同
PPC
的节
点,则从中随机选择。节点
ρz
的服务能力
PPC
;定
义为:
项目来源:国家自然科学基金资助项目(
41271398
);国家
973
计划资助项目
C2011CB302306
)。