位置共享

2024-08-22

位置共享篇1

现有电力信息系统数据资源共享方案主要是基于整合的技术和思想, 实现上主要采取统一数据模型[1,2]、建立数据中心[3,4]、封装服务[5,6]和整合应用系统[7]等措施。由于建立整个电力企业数据中心的不可行性以及电力各级部门对数据模型及面向服务和应用的若干整合方案选择的自主性, 不可避免会导致整合技术下资源共享的深度、广度和速度问题。

为此, 本文基于电力数据网络分级分层拓扑结构, 提出了一种基于位置索引的电力信息系统数据资源共享方案, 在较低开销的情况下实现了共享数据资源在系统内部搜索的高效性、可靠性和完备性。

1 系统框架

系统框架如图1所示。SPInet是国家电力信息网, 这是一个独立的电力专用数据通信网, 在电力企业分级管理模式下呈现出分级结构, 各级节点又分别作为核心节点引入3个网络层次:核心层、骨干层和接入层。SPInet节点提供共享资源并通过本地资源共享管理 (LRSM) 层, 各功能模块实现资源共享, 包括用于构建本地共享资源位置索引的索引构造器 (IM) 、用于汇聚本地和下层/级节点索引的索引汇聚器 (IA) 、用于均匀地向上层/级节点冗余发布本地汇聚索引信息的索引发布器 (IP) 、用于负责与用户进行查询交互的用户接口 (UI) 和用于在SPInet内搜索定位目标节点并汇总查询结果的查询管理器 (QM) 。

在该系统框架下, SPInet中所有共享资源均可本地存储, 全局共享。共享资源的搜索定位由QM实现, 当定位到目标节点后即由目标节点启动本地资源检索, 检索模型采用在信息检索中广泛使用的向量空间模型 (VSM) [8]。

2 术语和关键数据结构

2.1 术语定义

为方便描述, 定义术语如下:

网络级别L:在SPInet中, 各级网络分别包含具有明确上下级关系的2层节点。因此, 此处用节点级别Li (i=0, 1, 2, 3, 4) 等价表示网络级别。

域D和网络层次H:级节点作为核心节点引入的3个网络层次为核心层 (H1) 、骨干层 (H2) 和接入层 (H3) , 统称为一个域D。

层兄弟HB和级兄弟LB:HB指同一域中具有相同网络层次的所有节点;令SPInet中隶属于相同管理单位的所有节点为兄弟节点, 则LB指上级节点为兄弟关系的所有同级核心节点。

在上述定义下, 系统中任何域节点NID都可由一个二元组〈H, NID〉唯一确定, 任何级节点NID都可由一个三元组〈L, LB, NID〉唯一确定。显然, 核心节点具有域节点和级节点双重身份。

2.2 关键数据结构

2.2.1 节点关系链表

由于SPInet是由L0～L4各级和H1～H3各层节点构成的一个分级分层网络, 基于该共享方案的网络结构可由节点间的兄弟和父子关系描述。为此, 构造3类结构完全相同的节点关系链表如下:

1) 兄弟节点链表:用于存储本层/级按IP降序排列的具有兄弟关系的所有节点信息。

2) 父节点链表:用于存储本节点索引冗余发布选取的上级/层所有节点信息。

3) 子节点链表:用于存储本节点汇聚索引所属下级/层按IP降序排列的所有节点信息。

2.2.2 索引结构

1) 倒排索引

假设SPInet中的每个节点都维护一个文档集, 给定一个由一组关键字构成的查询Q={qi|i=1, 2, …}, QM将负责搜索定位SPInet中指定范围内的所有目标节点, 进而获取与查询相似的文档。

为利用VSM进行本地文档检索, 每个节点维护一个基于TF*IDF (term frequency*inverse document frequency) 规则的倒排索引列表Loc_list。

2) 域关键字索引

所有节点建立如图2所示的域关键字索引列表KHN_list (Kl, Hl, Nl) 。其中, Hl+Nl按从左到右顺序用一个位串表示, 所占存储空间LH-B为:

$L_{Η - B} = / / \frac{3 + \max (层兄弟节点数)}{8} / / (1)$

3) 级关键字索引

所有核心节点增建如图3所示的级关键字索引列表KLN_list (Kl, Ll, LBl, Nl) 。其中, LBl可由上级单位名称表示, Ll+Nl则按从左到右顺序用一个位串表示, 所占存储空间LL-B为:

$L_{L - B} = / / \frac{5 + \max (级兄弟节点数)}{8} / / (2)$

3 算法实现

3.1 索引发布算法

索引发布遵循从下层到上层和从下级到上级冗余分布的原则, 完整路线为:接入层→骨干层→核心层→上级节点→…→顶级节点。

在考虑索引冗余度r、索引分布距离、索引负载均衡等问题后, 索引发布算法步骤如下:

1) 查询本地父节点链表, 若活动节点数为r且非核心节点转步骤5, 核心节点转步骤7;

2) 计算父层/级节点数Sf;

3) 计算索引冗余分布距离d=Sf/r;

4) 选取r个索引冗余分布节点并添加到父节点链表:节点Ni的第j (1≤j≤r) 个索引冗余发布选取式为:

$(Ν_{f i} + d (j - 1)) m o d S_{f} (3)$

式中:Nfi表示父节点链表中第i个节点。

5) 向r个父节点发送汇聚后的KHN_list/KLN_list;

6) 父节点获取后修正层/级子节点链表并汇聚所有子节点索引信息后加入本地KHN_list/KLN_list, 若非核心节点转步骤1, 否则转步骤7;

7) 获取本节点网络级别Ll, 生成本地KLN_list合并汇聚的下级KLN_list后转步骤1;

8) 若节点级别为L0, 算法结束, 否则转步骤7。

3.2 索引汇聚算法

由于各节点索引向上级/层节点冗余发布, 若不采取适当措施, 必然造成网络层次/级别越高的节点索引存储开销越大的问题。为此设计了域内、域向级和级内3个不同层次的索引汇聚, 算法如下:

Input: In_KHN_list, In_KLN_list

Output: KHN_list, KLN_list

Global: struct *node_brother

//域内汇聚:汇聚下层子节点和本节点索引

In_KHN_list ← Out_KHN_lists from lower hierarchy

For each record of In_KHN_list

If (Ki==Kj∧Hi⊕Hj==0) //⊕表示异或运算

{//汇聚处理后加入KHN_list

Nout= (Ni|Nj) //按位或运算

Insert_into_KHN_list (Ki, Hi, Nout)

}

Else //否则分别加入KHN_list

{

Insert_into_KHN_list (Ki, Hi, Ni)

Insert_into_KHN_list (Kj, Hj, Nj)

}

For each new Keyword in local

//将本地新关键字加入本节点索引

Insert_into_KHN_list (Kl, Hl, Nl)

If (Hl!=001) //非核心节点

{//添加本层新索引并传上层父节点

For each new Keyword of KHN_list

{

Insert_into_Out_KHN_list (Keyword, Hl, Nl)

Send_to_father_nodes (out_KHN_list)

}

Else

//域向级的汇聚:本域索引向级索引汇聚

{

For each new Keyword of KHN_list

Insert_into_KLN_list (Keyword, LBl, Ll, Nl) //加入本级索引

}

//级内汇聚: 汇聚下级子节点和本级索引

In_KLN_list ← Out_KLN_lists from lower level

For each record of In_KLN_lists

If (Ki==Kj∧Li⊕Lj==0 ∧ LBi==LBj)

{//将同级关键字按兄弟关系进行汇聚处理

Nout= (Ni|Nj) //按位或运算

Insert_into_KLN_list (Ki, Li, LBi, Nout)

}

If (Li!=00001) //非L0级

{/添加本级新索引并传上级父节点

For each new Keyword of KLN_list

Insert_into_Out_KLN_list (Keyword, Ll, LBl, Nl)

Send_to_father_nodes (out_KLN_list) //传上级父节点

}

3.3 查询处理

当用户以SPInet内任一节点为入口通过关键字集合Q={qi|i=1, 2, …}给定查询时, QM可按需完成本地、本域和整个系统3种不同搜索范围的查询。查询处理流程见附录A图A1。

4 性能分析

4.1 存储代价

这里主要考虑索引的存储代价。由于核心节点需要同时存储域索引和级索引, 故这些节点存储索引的代价最高。若记层、级关键字总数分别为Nkeyword-H和Nkeyword-L, 平均长度分别为Lkeyword-H和Lkeyword-L, LB平均长度为LLB, LH-B和LL-B, 则层索引所需存储空间容量为:

SH=Nkeyword-H (Lkeyword-H+LH-B) (4)

级索引所需存储空间容量为:

$S_{L} = Ν_{k e y w o r d - L} (L_{k e y w o r d - L} + L_{L B} + L_{L - B}) (5)$

因此, 核心节点索引所需存储空间总容量为:

$S_{n o d e_Η_{l}} = S_{Η} + S_{L} \leq 2 S_{L}$

若级节点Node_Hl汇聚了105个关键字, 每个关键字及LLB长均为10 B, 级兄弟节点最多200个, 则有:Snode_Hl=9.2 MB。显然, 即使是核心节点, 索引存储开销也不会造成大的影响。

4.2 网络通信代价

网络通信代价可用传输所需字节数来衡量。因为目标文档下载的传输量依赖于文档大小, 此处仅考虑查询处理过程和维护索引的通信代价。

对于查询关键字个数为NQ-keyword、长度为LQ-keyword、查询涉及节点数为Nnode的一个查询Q, 其查询通信总代价为:

$C_{Q} = Ν_{Q - k e y w o r d} L_{Q - k e y w o r d} (Ν_{n o d e} - 1) (6)$

式 (6) 表明, 查询通信代价主要取决于通信节点数。本方案的查询通道基于位置索引, 定位目标明确, 故通信节点数已经降到了最低程度。

维护索引的通信代价首次较高, 之后则只需传输新增索引信息, 因此, 其代价与节点加入和退出以及文档增删的频度相关。

4.3 查询响应延迟

在本方案中, 查询响应延迟包括网络延迟和目标节点的本地查询处理延迟2部分。

本地查询处理延迟取决于本地文档数目Ndoc, 因通过倒排索引检索相关文档, 故目标节点本地查询时间复杂度为O (Ndoclg Ndoc) 。

网络延迟包括节点连接延迟和数据传输延迟。因为方案中同级/层节点并行执行, 节点连接延迟与命中目标节点所需平均网络层数NLayer和级数NHierarchy相关, 复杂度为O (NLayer+NHierarchy) ≪O (Nall-node) ;数据传输时间复杂度O (f (C/B) ) 取决于数据传输量C和网络带宽B。

可见, 索引的汇聚和目标节点的快速定位机制使本方案具有存储开销小、网络通信代价低和查询响应延迟低等优势。

5 实验

为验证方案的有效性, 在一台配置为CPU P4 2.4 GHz、内存1.0 GB、操作系统为Windows XP的PC机上, 利用相关测试文档集对本方案与无位置索引方案在资源定位效果和定位效率2方面进行了对比实验, 结果如图4所示。实验结果表明, 本方案在查全率相同的情况下, 查准率明显高于无位置索引检索, 尤其在查全率越高时效果越明显。

6 结语

本文所提出的信息资源共享方案通过索引发布和汇聚, 在较小系统开销的情况下有效解决了SPInet信息资源共享在深度和广度方面的扩展问题以及由此产生的资源定位速度问题。下一步, 将进一步研究关键字的汇聚、模式匹配、结果消重以及SPInet内的智能化信息检索等内容。

附录见本刊网络版 (http://www.aeps-info.com/aeps/ch/index.aspx) 。

摘要：为解决电力信息系统资源共享深度、广度和速度问题, 针对国家电力信息网 (SPInet) 分级分层拓扑结构, 提出了一种基于位置索引的信息资源共享方案。通过各节点对共享资源构建基于位串的位置索引并冗余发布和汇聚, 实现了基于查询多通道的目标节点快速准确定位。性能分析和仿真实验表明, 该方案具有资源定位的高效性、可靠性和搜索的完备性, 同时占用系统资源较少。

关键词：电力信息网,位置索引,资源定位,冗余发布,汇聚

参考文献

[1]李新叶, 李新芳.基于XML的供电企业分布式异构信息的检索.电力系统通信, 2008, 29 (3) :56-59.LI Xinye, LI Xinfang.Information retrieval based on XML indistributed and heterogeneous systems for power supplyenterprises.Telecommunications for Electric Power System, 2008, 29 (3) :56-59.

[2]王林青, 顾建炜, 曹一家, 等.基于CM/CIS的电力实时信息平台设计与实现.电力系统及其自动化学报, 2008, 20 (1) :46-51.WANG Linqing, GU Jianwei, CAO Yijia, et al.Design andimplementation of power real-time information platform basedon CM/CIS.Proceedings of the CSU-EPSA, 2008, 20 (1) :46-51.

[3]何鸣, 王皓, 谢红福.基于数据中心的故障信息管理系统.电力系统自动化, 2008, 32 (18) :104-107.HE Ming, WANG Hao, XIE Hongfu.A fault informationsystem based on data centre.Automation of Electric PowerSystems, 2008, 32 (18) :104-107.

[4]雷霆, 黄太贵, 李斌.基于数据平台的电力市场数据整合交换.电力系统自动化, 2008, 32 (24) :90-93.LEI Ting, HUANG Taigui, LI Bin.Data integration andexchange in power market based on data platform.Automationof Electric Power Systems, 2008, 32 (24) :90-93.

[5]唐跃中, 曹晋彰, 郭创新, 等.电网企业基于面向服务构架的应用集成研究与实现.电力系统自动化, 2008, 32 (14) :50-54.TANG Yuezhong, CAO Jinzhang, GUO Chuangxin, et al.Research and implementation of power grid enterpriseapplication integration based on services-oriented architecture.Automation of Electric Power Systems, 2008, 32 (14) :50-54.

[6]王继业.基于网格技术的电力信息资源整合方案.电力系统自动化, 2008, 32 (20) :84-87.WANG Jiye.An integration solution of power informationresources based on grid technology.Automation of ElectricPower Systems, 2008, 32 (20) :84-87.

[7]段斌, 林素烟, 周江龙.基于SRP和SAML的电力企业集成登录系统的设计.电力系统及其自动化学报, 2008, 20 (5) :29-34.DUAN Bin, LIN Suyan, ZHOU Jianglong.Design of integratedlogging-on system of power enterprise based on SRP andSAML.Proceedings of the CSU-EPSA, 2008, 20 (5) :29-34.