面向多维数据的语义索引对等网络的构建方法

摘要

面向多维数据的语义索引对等网络的构建方法，兼顾了节点的自身属性和多维数据本身的特点，将对等网络和多维数据的语义相结合，提出了构建面向多维数据网络处理领域的语义索引对等网络的方案，旨在结合对等计算技术和多维数据的语义来解决分布式计算领域中多维数据索引的问题。该发明提出的方法并不是简单地将对等网络和多维数据处理集成在一起，而是从多维数据和网络节点的语义出发，重新构建了索引网络的底层拓扑结构，实现了多维数据的网络快速索引，并为多维数据的传输等网络服务提供了基础。以解决分布式计算领域中多维数据索引的问题。较之其他分布式索引，该方案在利用对等计算的前提下，综合考虑了Peer节点语义和多维数据语义，实现了多维数据的快速索引。

说明书

技术领域

本发明提出了一种侧重于在多维数据领域中构建语义索引网络的构建方法，利用对等计算思想，结合多维数据的语义提出一种分布式的索引网络构建方法，属于分布式计算应用领域。

背景技术

“数字地球”和“智慧地球”是目前的一个研究热点，海量多维数据的索引和传输已经成为是该研究中的一个瓶颈问题。对等计算采用了分布式、自组织的对等组网和计算模式，从体系结构上解决了单点失效和服务器性能瓶颈等问题。利用“对等网络”分布计算的特点，建立面向多维数据服务的语义索引网络，可以提高海量多维数据的索引效率，加快多维数据的传输速度。

在对等网络中，每一个节点(Peer)大都同时具有信息消费者、信息提供者和信息通讯等三方面的功能，节点所拥有的权利和义务都是对等的。对等网络技术与传统C/S结构网络相比，具有高可扩展性、健壮性、负载均衡等很多优势，对等网络技术已经广泛应用于一维数据的流媒体网络传输中，有效解决了大量用户并发访问的问题，并得到学术界和产业界的广泛认可。

近年来，多维数据的研究和应用在多个领域也得到了快速发展，例如在数字地球、数字城市、复杂系统中的智能交通、汽车导航、海量卫星遥感影像数据的搜索与共享、多媒体3D游戏等领域。

因此，将对等网络计算与多维数据应用相融合，利用分布在网络中众多廉价的对等体，缓解大量并发访问“数字地球”的压力，是一种可行的解决方法。但是在目前现有的索引网络研究工作中，对网络中节点语义和多维数据语义的综合考虑，没有明确提出，而语义索引网络中节点的动态性问题更是没有确定，由此我们需要一种新方法，重新构建面向多维数据的语义索引网络，主要包括：节点语义和多维数据语义的形式化定义以及在语义分析基础上索引网络的结构研究和索引流程设计等问题。

发明内容

技术问题：本发明的目的是提供一种面向多维数据的语义索引对等网络的构建方法，以解决分布式计算领域中多维数据索引的问题。较之其他分布式索引，该方案在利用对等计算的前提下，综合考虑了Peer节点语义和多维数据语义，实现了多维数据的快速索引。

技术方案：本发明的方法强调多维数据的分布式索引，综合考虑了对等计算和多维数据等的语义，其目的是解决分布式环境中的多维数据的快速索引和传输等问题。

该方法兼顾了节点的自身属性和多维数据本身的特点，将对等网络和多维数据的语义相结合，提出了构建面向多维数据网络处理领域的语义索引对等网络的方案，具体如下：

a.首先，构建基于分布式四叉树的结构化语义对等网络的上层；

a1.根据网络中对等节点自身的先续/后续关系和同步关系的属性，构建多维数据服务本体库：

a2.在网络对等节点中构建用于服务分类查找的关键字匹配器；

a3.在网络对等节点中构建用于支持多维数据范围等各种复杂语义服务的语义匹配器和查询代理；

a4.综合多维数据服务本体库、关键字匹配器、语义匹配器和查询代理，完成上层网络中一个汇聚节点对等节点的构建；

a5.根据这些对等节点所包含的多维数据的空间区域，形成对等节点的聚簇，至此完成上层结构化网络构建；

b.接着，构建下层非结构化语义对等网络；

b1.根据两个控制点的相似度Sim(CtrlPX，CtrlPY)的公式：

$\mathrm{Sim}(\mathrm{CtrlPX},\mathrm{CtrlPY})=\underset{T\in \mathrm{Set}(\mathrm{CtrlPX},\mathrm{CtrlPY})}{\mathrm{Max}}\left[P\left(T\right)\right]=P\left(\mathrm{NSCP}(\mathrm{CtrlPX},\mathrm{CtrlPY})\right)=\mathrm{CtrlPNum}/N---\left(1\right)$

计算得到多维数据之间的相似程度；

其中，Set(CtrlPX，CtrlPY)是CtrlPX和CtrlPY最近的公共超类控制点的集合，T是该集合中一个控制点元素，P(T)是对应控制点T在该划分层的所有空间控制点中出现的概率，Max[]是取最大值的函数，NSCP(CtrlPX，CtrlPY)是求在四叉树中距离CtrlPX和CtrlPY最近的公共超类节点的函数，CtrlPNum是T出现的统计次数，N是该划分层的所有控制点出现的统计次数总和；

b2.根据聚类评价函数EFBC的公式

$\mathrm{EFBC}=P\left(\mathrm{Sim}(\mathrm{RPeer},\mathrm{EPeer})\right)*\frac{C_1*\mathrm{dist}(\mathrm{RPeer},\mathrm{EPeer})}{\mathrm{Vavg}}+(1-P\left(\mathrm{Sim}(\mathrm{RPeer},\mathrm{EPeer})\right)*C_2*(T1+T2)---\left(2\right)$

计算得到聚类评价函数的值；

其中RPeer表示聚簇Peer中的汇聚节点，对应的空间数据的控制点为CtrlPX；EPeer表示子簇Peer中的边缘节点，对应的空间数据的控制点为CtrlPY；Sim(RPeer，EPeer)可由Sim(CtrlPX，CtrlPY)求出；P(Sim(RPeer，EPeer))是当前新加入的汇聚节点和边缘节点的组内相似度的概率；Vavg是对等体之间消息的平均传输速度，dist(RPeer，EPeer)是当前新加入的汇聚节点和边缘节点的组内相似度的传输距离；T1是拥有N个节点的Chord环上汇聚节点之间的查找时间；T2是对等体之间消息的平均传输时间，可以通过dist(PeerX，PeerY)计算得到，其中PeerX和PeerY是网络中任意两个对等体；C₁和C₂是归一化时用的常数；

b3.下层网络中的对等节点视为边缘节点，它按照聚类评价函数的值选择最优的汇聚节点作为簇头，加入该组；

b4.组内节点，根据网络性能的不同拥有不同的状态集，并且按照其包含的多维数据四叉树划分的结果，形成一个个基于分布式四叉树的子簇；

b5.这些子簇对等节点包含的其他模块和聚簇对等节点相似，至此，完成了下层网络的构建；

c综合上述构建的上层网络和下层网络，形成了一个面向多维数据的语义索引对等网络，通过该网络用户可以高效地完成对多维数据的分布式索引服务，具体如下：

d.多维数据的用户端向语义索引网络提交包含一定空间区域的网络索引服务请求；

e.语义索引网络通过分布式四叉树对此空间区域进行语义分析，

f.接着找到网络中的汇聚节点；

g.然后沿着汇聚节点基于面向多维数据索引网络的数据查询流程，继续查找；

h.如果到了最大的划分层(fmax)，还没有找到所需数据时，返回失败消息；

i.当从语义索引网络找到所需的所有分片(Tile)文件之后，在各个对等节点端进行合并，完成一次网络索引服务请求。

有益效果：本发明方法提出了一种侧重于多维数据领域中构建语义索引网络的构建方法，旨在结合对等计算技术和多维数据的语义来解决分布式计算领域中多维数据索引的问题。该发明提出的方法并不是简单地将对等网络和多维数据处理集成在一起，而是从多维数据和网络节点的语义出发，重新构建了索引网络的底层拓扑结构，实现了多维数据的网络快速索引，并为多维数据的传输等网络服务提供了基础。

下面我们给出具体的说明。

(1)面向多维数据的索引网络体系结构：

这是兼顾了节点的自身属性和多维数据本身的特点。目前一般的索引网络，由于没有综合考虑多维数据和网络节点的语义，会造成虚拟拓扑网络与实际物理网络不匹配问题。而在本发明的方法中，我们在分析多维数据语义的基础上，同时参考了相应的对等网络节点物理位置参照坐标，依据节点坐标间的Euclidean欧氏距离，参与度量聚类节点的网络性能方面的代价，以此作为新节点在选择一个簇进行加入时的综合评价指标，使得构成的聚类网络拓扑结构得到优化。

(2)基于面向多维数据索引网络的数据发布流程：

●设初始多维数据文件存放于一个集中式服务器上。

●服务器将初始多维数据文件先按Grid分割到fmin层，每个分片Tile文件大小为初始文件的1/4fmin，将这些文件均匀发布到Chord环上。

●Chord环上的节点，将Chord环上的文件再向下划分一个层次，每个分片Tile文件大小为初始文件的1/4fmin+1，将这些文件的索引存储在四叉树的fmin+1层的控制点上。

●同理，递归划分下去，直到四叉树的fmax层。

(3)基于面向多维数据索引网络的数据查询流程：

图3是客户端数据查询的一般流程，具体如下：

●客户端必须先和Chord环上的任一节点取得联系，并向其发送查询请求消息。

●这需要引入额外的机制，如采用引导服务器维护Chord节点列表，当客户端需查询时，为其随机返回一个Chord节点。(消息1，2，3)

●查询仍采用四叉树查询算法(消息4，5，6)；

●当查询范围包括某个控制点后，就直接从该控制点获得相应的Tile文件分片，而不必再向更深层次查找；否则，就继续在下层中查找，直到fmax层；

●最后，客户端将查询获得的所有分片(包括不同层次的Tile)文件，进行合并。

(4)基于面向多维数据索引网络的Cache数据发布流程：

当一个Peer(通过查询)拥有某个控制点上的Tile文件(Cache数据)后，它就可以申请加入该控制点的分组，发布共享Cache数据。Cache数据发布的一般流程如下：

●客户端必须先和Chord环上的任一节点取得联系，并向其发送数据发布请求消息。(与查询类似)

●已控制点为条件，查询四叉树上相同控制点的索引分组；

●该Peer加入控制点分组，并成为其Ordinary节点。

附图说明

图1是面向多维数据的索引网络体系结构示意图，主要分为两层：上层为基于分布式四叉树的结构化语义对等网络；下层为非结构化语义对等网络。

图2是多维数据及其控制点示意图，表明本发明的方法中多维数据语义模型。

图3是客户端对多维数据进行查询的流程，这是基于本发明的语义索引网络拓扑结构的一个典型应用。

具体实施方式

一、索引网络的体系结构

基于对等计算的索引网络的体系结构是保障了分布式索引目的的实现，以Peer节点语义和多维数据语义为基础，通过统一的标准接口来管理和索引对等网络上多维数据等资源。该体系结构在实现对等网络基本功能的基础上，建立了分层的分簇的索引机制。图1给出了面向多维数据的语义索引网络的体系结构，它在网络分层聚类的层次结构基础上，结合多维数据的语义，对各层都进行了详细的规划和设计，尤其在索引服务和分簇机制中，引入了语义的分析。整个索引网络层次结构主要分为两层：上层为基于分布式四叉树的结构化语义对等网络；下层为非结构化语义对等网络。下面给出结构中各个层次的具体说明：

1：上层由多个聚簇Peer组成，每个聚簇Peer按照分布式四叉树对多维数据的划分，分别负责一定的空间区域，在聚簇Peer中包含多维数据/服务本体库、关键字匹配器、语义匹配器和查询Agent，

多维数据服务本体库：利用本体自身的属性来描述这种关系(如先续/后续关系、合作关系和同步关系等)，从而丰富原有多维数据服务的语义内容，为将来多维数据服务优化打下基础；

关键字匹配器：实现高效、快速地服务分类查找(如多关键字查找等)；

语义匹配器和查询Agent：实现支持各种复杂语义的服务查找(如基于多维数据范围和QoS指标等查找)；其中，每一个Peer节点都包含查询Agent，它负责根据多维数据服务本体库完成聚簇Peer和子簇Peer中的索引和传输等服务的发现。

2：下层由多个子簇Peer组成，这些子簇Peer包含的模块和聚簇Peer相似，但是在语义匹配器的设计时，综合了每个Peer和多维数据的语义，它们根据语义的不同，分属于不同的聚簇Peer。

这些Peer是多维数据按照分布式四叉树进行划分之后形成的，多维数据的语义主要是通过多维数据之间的相似程度来表达，而多维数据之间的相似程度又可以通过图2中的控制点来描述。

所谓控制点，是对多维数据描述的一种抽象，假定所有数据都是一个最大的矩形里面的一个个矩形块(包围盒)，对这个最大的矩形做四叉树划分操作，那么每次划分都会在十字线上产生一个交点。显然，这个交点和十字线对应着一个矩形块，可以用来表示二维的多维数据，我们定义这样带有坐标的交叉点为控制点。

图2中控制点O，对应整个空间区域进行0层四叉树划分；控制点A、AA、AAA和AAAA，分别对应第一、二、三和四层划分得到的控制点；而A、B、C和D对应的则是同一层次划分得到的同级别的控制点，其余可以类推得到。

3：多维数据服务提供者和多维数据服务请求者

多维数据服务提供者通过服务本体、WSDL(Web服务描述语言)向索引网络注册具体的多维数据服务，这是一种分布式数据索引和服务的发现机制。其中，多维数据服务是用WSDL来描述的，通过对这些WSDL进行映射，把它们映射到新的对等体中的多维数据服务本体，为索引网络Peer中的查询Agent提供查询基础。

多维数据服务请求者则通过用户接口从索引网络并行地检索、并执行所需的服务。通过Peer中查询Agent把请求服务的语义和本体注册器中已有服务信息相匹配，从而提高发现服务的“精度”。

由于采用了对等计算来优化索引网络，多维数据服务的注册信息在多个聚簇Peer中同步更新。同时，本体注册器按照已匹配的分类信息，可以很方便地把这些新注册的服务聚簇到不同的对等体组，这样既避免了多维数据服务发现时进行全局查找，可以先在语义相似的组中查找，从而减少检索次数；此外，对等计算还把原来单点责任分散到各个不同的对等体组，提高了多维数据服务系统的可靠性。

二、方法流程

通过面向多维数据的语义索引网络来优化分布式计算领域中多维数据索引的问题，我们首先需要定义多维数据和网络节点的语义并进行形式化的描述。然后在这种描述的基础上，分别构建索引网络的上层：基于分布式四叉树的结构化语义对等网络和索引网络的下层：非结构化语义对等网络。最后，设计多维数据服务提供者和多维数据服务请求者中相应的模块，完成面向多维数据的语义索引网络的构建。

主要工作流程：

(1)多维数据和网络节点语义的形式化描述

我们以简单的二维数据为例来说明(二位以上的多维数据描述可以类推得到)，根据多维数据和网络节点语义可以将不同的Peer聚集到不同的簇内。

由图2可知，二维数据的数据结构采用了分布式四叉树，两个多维数据的相似度对应于多维数据的包围盒经过四叉划分之后得到的控制点的相似度。两个多维数据用ObjX和ObjY表示，对应于其控制点用CtrlPX和CtrlPY表示，那么，Sim(ObjX，ObjY)～Sim(CtrlPX，CtrlPY)，而Sim(CtrlPX，CtrlPY)可以用四叉树划分上的所有共同“超类控制点”所具有的最大信息含量来表示。为此，我们引入最近超类控制点(Nearest SupperControl Point，NSCP)的概念，即在四叉树中距离CtrlPX和CtrlPY最近的公共超类节点，设为NSCP(CtrlPX，CtrlPY)。此时，控制点的相似度形式化的公式可以定义如下：

公式1(两个控制点的相似度，Sim(CtrlPX，CtrlPY))。

$\mathrm{Sim}(\mathrm{CtrlPX},\mathrm{CtrlPY})=\underset{T\in \mathrm{Set}(\mathrm{CtrlPX},\mathrm{CtrlPY})}{\mathrm{Max}}\left[P\left(T\right)\right]=P\left(\mathrm{NSCP}(\mathrm{CtrlPX},\mathrm{CtrlPY})\right)=\mathrm{CtrlPNum}/N---\left(1\right)$

其中，Set(CtrlPX，CtrlPY)是CtrlPX和CtrlPY最近的公共超类控制点的集合，T是该集合中一个控制点元素，P(T)是对应控制点T在该划分层的所有空间控制点中出现的概率，CtrlPNum是T出现的统计次数，N是该划分层的所有控制点出现的统计次数总和。可见，公式1取P(T)的最大值，既表达了CtrlPX和CtrlPY的相似程度，又反映了其对应的NSCP所包含的信息量，值越大，则包含的空间信息量越大，两个控制点对应的多维数据包围盒的相似度也越大。

对于一个动态的网络环境，网络中节点是可以随机地加入或者离开，但是根据节点的计算性能、稳定性、可用带宽等自身属性以及其拥有数据等语义的不同，可以对节点进行分类，为表述的一致性，先给出下列定义。

定义1(汇聚节点，RendezvousPeer)。它由自身计算性能强，网络相对稳定的节点充当，这些节点分布在Chord环上，分别负责一片相对固定的空间区域。

定义2(边缘节点，EdgePeer)。它是网络中随机性较强的节点，可以按照当前的聚类评价函数选择最优的汇聚节点作为簇头，加入该组，组内按照四叉树划分，形成一个基于分布式四叉树的簇，综合评价指标的定义如公式2。

聚类评价函数EFBC(Evaluate Function Based on Clustering)。

$\mathrm{EFBC}=P\left(\mathrm{Sim}(\mathrm{RPeer},\mathrm{EPeer})\right)*\frac{C_1*\mathrm{dist}(\mathrm{RPeer},\mathrm{EPeer})}{\mathrm{Vavg}}+(1-P\left(\mathrm{Sim}(\mathrm{RPeer},\mathrm{EPeer})\right)*C_2*(T1+T2)---\left(2\right)$

其中RPeer表示聚簇Peer中的汇聚节点，对应的空间数据的控制点为CtrlPX；EPeer表示子簇Peer中的边缘节点，对应的空间数据的控制点为CtrlPY；Sim(RPeer，EPeer)可以由Sim(ObjX，ObjY)求出；P(Sim(RPeer，EPeer))是当前新加入的汇聚节点和边缘节点的组内相似度的概率；Vavg是对等体之间消息的平均传输速度，Dist(RPeer，EPeer)是当前新加入的汇聚节点和边缘节点的组内相似度的传输距离；T1是Chord环上汇聚节点之间的查找时间，N是Chord环上节点的总数；T2是对等体之间消息的平均传输时间，可以通过Dist(PeerX，PeerY)计算得到，其中PeerX和PeerY是网络中任意两个对等体；C₁和C₂是归一化时用的常数。公式(4)的基本思想是通过归一化之后取簇内评价和簇外评价之和的最大值，以此作为检索时选择遍历路径的评价指标，使得检索过程得到优化。

结合图2，可以选取对应第二层划分的16个控制点(AA，AB，AC，AD，...，DD)的节点作为Chord环上的汇聚节点，对应第三、第四层划分控制点(AAA，AAB，AAC，AAD，...，DDDD)的节点作为边缘节点。

(2)语义索引网络拓扑结构的构建

(2.1)索引网络上层的构建

该层是基于分布式四叉树的结构化语义对等网络，首先根据多维数据四叉树划分后的控制点映射到Chord环上，使用Chord模型管理多维数据的分布式存储，改善了系统的并发访问性能。

(2.2)索引网络下层的构建

该层是非结构化语义对等网络，由多个子簇Peer组成，这些子簇Peer根据第(1)部分的语义来聚类，包含的模块和聚簇Peer相似，但不同的是这些Peer节点拥有不同的状态集，任何节点都需同时维护Header节点状态集S_H以及Ordinary节点状态集S_O.以此增强索引网络的鲁棒性，具体的节点状态集如下。

●状态集S_H

$\forall s\in S_H,$s＝(Controlpoint，Parent，Ordinarypeerslist，Childrenlist，Tilefile)

其中，

controlpoint控制点是s的唯一标识，用s(u)∈S_H，表示S_H中控制点为u的元素s。

parent表示该controlpoint的父节点，parent＝null表示Chord网上f_min层的控制节点。

Ordinarypeerslist表示本组内其他ordinary节点列表。

childrenlist表示四叉树的四个孩子节点列表。

Tilefile表示存储在本节点的数据分片文件链接。

●状态集S_O

$\forall s\in S_O,$s＝(header，controlpoint，Tilefile)

其中，

header表示本组的头节点，可唯一标识s，同上s(h)∈S_O。

controlpoint表示所属的控制点组，也可唯一标识s(为方便处理，冗余的)。

Tilefile表示存储在本节点的数据分片文件。

(3)多维数据服务提供者和多维数据服务请求者中相应模块的设计

本模块的设计不仅可以提高检索等网络服务的精度，而且可以增强网络服务的扩展性。多维数据服务提供者通过服务本体、WSDL(Web服务描述语言)向索引网络注册具体的多维数据服务，这是一种分布式数据索引和服务的发现机制。其中，多维数据服务是用WSDL来描述的，通过对这些WSDL进行映射，把它们映射到新的对等体中的多维数据服务本体，为索引网络Peer中的查询Agent提供查询基础。

多维数据服务请求者则通过用户接口，从索引网络并行地检索、执行所需的服务。通过Peer中查询Agent把请求服务的语义和本体注册器中已有服务信息相匹配，从而提高发现服务的“精度”。

为了方便描述，我们假定有如下应用实例：

某个多维数据应用领域中构建语义索引网络的用户(用A表示)提交对某个多维数据的索引处理请求(用R表示)，则其具体实施方式为：

(1)多维数据服务器端启动；

(2)初始多维数据文件的分割；

(3)分割之后的多维数据文件在语义索引网络的上层发布；

(4)根据分布式四叉树再在语义索引网络的下层继续向下划分，直到fmax层；

(5)用户A启动对等客户端程序，向语义索引网络(设为乙)提交R请求；

(6)乙处理用户A的作业请求：

第一步：乙根据作业请求多维数据的区域生成请求消息；

第二步：乙对A提出的请求采用分布式四叉树查询算法进行查询；

(7)语义索引网络的用户，基于对等计算的思想，它们可以既是数据索引服务的请求者，又可以是数据索引服务的提供者；

(8)语义索引网络中服务的提供者通过WSDL来描述服务；

(9)语义索引网络中服务的请求者通过查询Agent来检索服务；

(10)当A将从乙并行获得了相应Tile文件之后，进行合并得到一个完整的多维数据，至此结束一次R任务。