2016 年 第 25 卷 第 期 http://www.c-s-a.org.cn 计 算 机 系 统 应 用 1 基 于 节 点 融 合 分 层 法 的 电 网 并 行 拓 扑 分 析 王 惠 中 1,2, 赵 燕 魏 1,2, 詹 克 非 1, 朱 宏 毅 1 ( 兰 州 理 工 大 学 电 气 工 程 与 信 息 工 程 学 院, 兰 州 730050) 2 ( 甘 肃 省 工 业 过 程 先 进 控 制 实 验 室, 兰 州 730050) 3 ( 国 网 甘 肃 省 电 力 公 司 电 力 科 学 研 究 院, 兰 州 730050) 3 摘 要 : 随 着 现 代 多 核 和 集 群 技 术 的 快 速 发 展, 并 行 计 算 设 计 成 为 提 高 计 算 效 率 的 主 流 技 术 之 一. 对 此, 提 出 了 一 种 基 于 节 点 融 合 和 分 层 的 并 行 网 络 拓 扑 分 析 新 方 法. 在 电 力 网 络 正 常 运 行 时, 首 先 利 用 节 点 的 邻 接 表 进 行 并 行 融 合, 对 电 网 进 行 静 态 电 气 岛 拓 扑 分 析, 并 完 成 电 气 岛 邻 接 表 的 分 层 ; 当 网 络 拓 扑 发 生 变 化 后, 根 据 节 点 所 在 回 路 链 表 的 属 性 及 并 行 深 度 优 先 搜 索 法 更 新 局 部 网 络 拓 扑 和 电 气 岛 邻 接 表. 最 后, 通 过 MATLAB 并 行 计 算 工 具 箱 (Parallel Computing Toolbox) 对 实 际 电 网 进 行 拓 扑 分 析, 计 算 结 果 验 证 了 本 方 法 的 正 确 性 和 快 速 性. 关 键 词 : 并 行 拓 扑 分 析 ; 节 点 融 合 ; 邻 接 表 ; 回 路 链 表 Grid Parallel Topology Analysis Based on Method of Node Integration and Layering WANG Hui-Zhong 1,2, ZHAO Yan-Yei 1,2, ZHAN Ke-Fei 1, ZHU Hong-Yi 3 1 (College of Electrical and Information Engineering, Lanzhou University of Technology, Lanzhou 730050, China) 2 (Key Laboratory of Gansu Advanced Control for Industrial Processes, Lanzhou 730050, China) 3 (Gansu Electric Power Research Institute, SGCC, Lanzhou 730050, China) Abstract: With the rapid development of modern multi-core and cluster technology, design of parallel computing to improve the efficiency has become one of the mainstream technologies. This paper puts forward a new method of node-based integration and hierarchical network topology in parallel. When in the normal operation of power network, using parallel fusion nodes adjacent table, to analyze static electric Island grid topology, electrical island adjacent to form and hierarchy. When the network topology changes, according to the attributes of the nodes and parallel depth first search method, it updates the local network topology and the electrical Island adjacency list. a practical network being analyzed by MATLAB s Parallel Computing Toolbox and the results prove the correctness and effectiveness of the proposed method. Key words: parallel topology analysis; node integration; adjacency list; linked list of loop 1 引 言 电 力 系 统 网 络 拓 扑 分 析 是 根 据 收 到 的 电 网 开 关 变 位 信 息, 采 用 合 理 的 算 法 确 定 元 件 的 连 接 关 系, 进 而 把 电 力 系 统 的 实 际 网 络 结 构 转 化 为 精 确 的 数 学 模 型. 它 是 电 力 系 统 仿 真 和 分 析 计 算 的 基 础, 可 为 状 态 估 计 潮 流 计 算 故 障 分 析 整 定 计 算 等 提 供 网 络 拓 扑 及 参 数 信 息 [1]. 常 用 的 电 网 拓 扑 分 析 算 法 主 要 有 矩 阵 法 [2-5] 搜 索 法 [6-] 节 点 连 通 岛 合 并 法 等. 矩 阵 法 主 要 是 在 邻 接 矩 阵 的 基 础 上 通 过 不 同 的 计 算 方 式 获 取 表 征 系 统 全 局 连 通 性 矩 阵, 其 方 法 的 运 算 复 杂 度 为 O(n3), 此 外 图 中 任 意 支 路 状 态 发 生 变 化 时, 该 算 法 的 通 用 性 差 [,10]. 树 搜 索 法 主 要 是 基 于 深 度 优 先 搜 索 法 和 广 度 优 先 搜 索 法 及 其 改 进 变 形 算 法, 此 类 算 法 对 变 电 站 复 杂 接 线 方 式 和 环 网 适 应 性 较 差. 同 时, 随 着 现 代 多 核 集 群 及 广 域 分 布 式 并 行 计 算 技 术 的 快 速 发 展, 传 统 算 法 不 能 有 效 利 用 现 行 并 行 计 算 平 台 ( 如 云 计 算 平 台 ), 这 也 大 大 制 约 了 电 网 拓 扑 效 率 的 提 高. 1 基 金 项 目 : 甘 肃 省 自 然 基 金 (130RJZA117) 收 稿 时 间 :2015-12-22; 收 到 修 改 稿 时 间 :2016-03-0 [doi:10.15/j.cnki.csa.005367] Software Technique Algorithm 软 件 技 术 算 法 15
计 算 机 系 统 应 用 http://www.c-s-a.org.cn 2016 年 第 25 卷 第 期 为 此 本 文 在 满 足 电 网 拓 扑 分 析 的 通 用 性 和 快 速 性 的 基 础 上, 从 并 行 计 算 的 角 度 出 发 提 出 了 基 于 节 点 融 合 分 层 法 的 电 网 并 行 拓 扑 分 析. 2 电 网 静 态 拓 扑 分 析 2.1 邻 接 表 邻 接 表 是 图 的 一 种 最 主 要 存 储 结 构. 在 图 论 中, 邻 接 表 描 述 图 中 每 个 点 的 所 有 边 或 弧. 1 5 3 6 2 7 图 1 节 点 系 统 其 中 较 小 的 节 点 号 作 为 节 点 i 的 连 通 岛 号, 结 果 如 图 3(a) 所 示, 即 在 此 图 中, 每 个 节 点 i 指 向 邻 接 节 点 号 最 小 的 节 点 ( 根 节 点 ); 接 着 追 踪 图 3(a) 中 的 路 线, 直 到 每 个 节 点 都 达 到 其 最 终 目 的, 此 时 第 一 组 电 气 岛 由 节 点 (1 5) 组 成, 第 二 组 电 气 岛 由 节 点 (2 6 7 ) 组 成, 第 三 组 和 第 八 组 电 气 岛 分 别 由 节 点 3 和 组 成. 其 次, 如 图 3(b) 所 示, 将 第 三 组 与 第 一 组 电 气 岛 合 并, 所 以 第 一 组 电 气 岛 现 在 由 节 点 (1 3 5) 组 成. 将 第 八 组 和 第 二 组 电 气 岛 合 并, 所 以 第 二 组 电 气 岛 现 在 由 节 点 (2 6 7 ) 组 成. 最 后, 由 图 3(c) 所 示, 此 时 所 有 节 点 均 并 入 第 一 组 电 气 岛, 这 就 意 味 着 原 图 只 有 一 条 连 通 分 量. 根 据 图 1 所 示 系 统, 其 邻 接 表 如 图 2 所 示. 图 中 顶 点 为 系 统 的 各 个 节 点, 邻 接 点 为 与 顶 点 相 连 接 的 节 点. (a) 7 (b) 图 2 节 点 系 统 邻 接 表 2.2 邻 接 表 的 节 点 融 合 算 法 2.2.1 算 法 基 本 原 理 在 一 个 网 络 拓 扑 图 中, 节 点 i 和 它 的 邻 接 节 点 j k 形 成 的 连 通 区 域 称 为 该 节 点 的 连 通 岛, 并 用 岛 内 所 包 含 节 点 i j k 中 最 小 节 点 号 作 为 该 连 通 岛 的 岛 号 [10], 即 该 节 点 为 该 连 通 岛 的 根 节 点. 若 多 个 电 气 连 通 岛 之 间 存 在 相 同 的 连 接 点, 则 连 通 岛 可 以 看 作 各 个 节 点 合 并 融 合 而 形 成 的 大 节 点, 因 此 可 进 一 步 进 行 合 并 融 合, 直 到 所 有 相 连 接 的 节 点 最 终 合 并 融 合 为 一 个 电 气 岛, 其 连 通 岛 号 为 最 小 节 点 号. 2.2.2 算 法 的 并 行 执 行 如 图 3 所 示, 开 始 时 根 据 边 与 节 点 关 系 生 成 邻 接 表. 首 先 比 较 节 点 i 及 其 邻 接 的 每 个 节 点 号 的 大 小, 将 (c) 图 3 算 法 执 行 步 骤 2.3 基 于 邻 接 表 的 节 点 融 合 及 分 层 在 节 点 合 并 过 程 中, 令 连 通 岛 的 根 节 点 为 父 层, 其 合 并 的 邻 接 点 为 其 子 层, 故 节 点 合 并 分 层 过 程 如 图 所 示, 最 终 形 成 分 层 的 电 气 岛 邻 接 表 如 图 (c) 所 示, 表 中 以 红 线 区 分 开 节 点 所 在 层. 16 软 件 技 术 算 法 Software Technique Algorithm
2016 年 第 25 卷 第 期 http://www.c-s-a.org.cn 计 算 机 系 统 应 用 7 (a) 7 (b) 连 支, 其 余 列 为 基 本 回 路 中 的 树 支. 根 据 静 态 拓 扑 分 析 中 节 点 融 合 分 层 生 成 的 电 气 连 通 岛 的 邻 接 表, 可 离 线 并 行 生 成 回 路 链 表. 其 生 成 步 骤 如 下 : 步 骤 1: 根 据 分 层 的 邻 接 表, 可 得 到 同 层 连 接 两 节 点 的 支 路 为 连 支, 定 义 为 同 层 连 支 ; 子 节 点 有 两 个 及 以 上 的 父 节 点 的 连 接 支 路, 其 中 一 条 支 路 为 树 支, 其 他 支 路 为 连 支, 定 义 为 跨 层 连 支. 因 此 除 去 连 支, 可 生 成 一 个 树, 其 最 终 的 根 节 点 为 电 气 岛 的 连 通 岛 号. 根 据 上 述 定 义, 由 图 (c) 所 示, 节 点 和 节 点 5 相 连 接 且 位 于 同 一 层, 故 连 支 -5 为 同 层 连 支 ; 由 此, 7- 亦 为 同 层 连 支. 节 点 7 有 两 个 父 层 节 点, 分 别 为 节 点 2 和 节 点, 选 其 中 支 路 7- 为 树 支, 则 支 路 7-2 为 跨 层 连 支. 步 骤 2: 通 过 各 个 连 支 的 两 节 点, 可 同 时 并 行 向 父 层 进 行 树 支 的 节 点 融 合, 形 成 各 个 连 支 所 在 的 基 本 回 路 链 表, 最 终 构 成 电 气 岛 的 回 路 链 表. 通 过 步 骤 1 中 所 得 连 支 -5, 由 节 点 和 节 点 5 两 节 点 并 行 向 父 层 进 行 树 支 节 点 融 合, 可 得 回 路 链 表 -5-1. 5 1 7 (c) 图 节 点 邻 接 表 的 融 合 及 分 层 过 程 通 过 节 点 的 融 合 分 层 完 成 电 网 的 静 态 拓 扑 分 析, 实 现 电 网 拓 扑 连 通 性 的 判 断, 并 为 电 网 的 并 行 动 态 拓 扑 更 新 做 好 数 据 准 备. 3 离 线 生 成 回 路 链 表 在 连 通 图 中 选 定 一 个 树 后, 任 意 添 加 一 条 连 支, 这 样 包 含 且 仅 包 含 一 条 连 支 的 回 路 即 为 基 本 回 路. 在 回 路 中 任 意 两 点 间 不 只 存 在 一 条 路, 因 此, 若 断 开 的 边 位 于 回 路 当 中, 则 电 气 岛 的 连 通 性 将 不 会 发 生 变 化. 鉴 于 连 支 在 回 路 的 以 上 特 性, 本 文 定 义 回 路 链 表 Lg(g 表 示 连 通 岛 号 ). 在 Lg 中, 第 1 列 为 基 本 回 路 中 的 其 他 连 支 同 时 并 行 向 父 层 进 行 树 支 节 点 融 合. 本 文 为 便 于 描 述, 默 认 回 路 链 表 中 末 节 点 指 向 首 节 点. 最 终 由 图 (c) 可 得 到 回 路 链 表 L1 如 图 5 所 示. 5 1 7 图 5 回 路 链 表 网 络 并 行 拓 扑 更 新 电 力 系 统 网 络 正 常 的 停 运 故 障 检 修 等 因 素 造 成 的 电 网 开 关 变 位, 反 映 在 电 网 拓 扑 上 主 要 分 为 支 路 的 断 开 和 闭 合 两 种 情 况. 其 中 支 路 断 开 可 分 为 : 回 路 中 连 支 断 开 回 路 中 树 支 断 开 非 回 路 中 树 支 断 开 三 种 情 况. 闭 合 支 路 又 分 为 : 同 一 电 气 岛 内 两 节 点 闭 合 不 同 电 气 岛 两 节 点 闭 合. 本 文 根 据 支 路 在 以 上 变 位 情 况, 可 同 时 并 行 对 其 邻 接 表 和 回 路 链 表 进 行 修 改, 而 邻 接 表 各 个 顶 点 又 可 Software Technique Algorithm 软 件 技 术 算 法 17
计 算 机 系 统 应 用 http://www.c-s-a.org.cn 2016 年 第 25 卷 第 期 同 时 并 行 进 行 修 改..1 网 络 中 支 路 断 开.1.1 回 路 中 连 支 断 开 回 路 中 连 支 断 开, 电 气 岛 连 通 性 不 受 影 响, 所 以, 对 其 邻 接 表 进 行 修 改, 并 行 删 除 断 开 支 路 顶 点 的 邻 接 点, 同 时 更 新 连 支 所 在 的 回 路 链 表, 删 除 其 所 在 回 路. 如 图 1 所 示 系 统, 若 连 支 -5 断 开, 则 电 气 岛 不 变, 修 改 邻 接 图 (c), 顶 点 和 5 彼 此 对 应 的 邻 接 点 可 同 时 并 行 删 除, 结 果 如 图 6 所 示 ; 并 从 回 路 链 图 中 删 除 其 所 在 回 路, 如 图 7 所 示. 1 图 6 邻 接 表 7 图 7 回 路 链 表.1.2 回 路 中 树 支 断 开 回 路 中 树 支 断 开, 电 气 岛 连 通 性 不 受 影 响, 故 修 改 邻 接 表 相 关 节 点, 同 时 修 改 回 路 链 表. 根 据 断 开 的 树 支 所 在 回 路 状 况, 回 路 链 表 的 修 改 又 可 分 为 以 下 两 种. 情 况 1: 基 本 回 路 中 树 支 断 开, 则 直 接 把 该 回 路 中 连 支 变 为 树 支, 并 将 该 回 路 从 回 路 链 表 中 删 除. 如 图 1 所 示 系 统, 树 支 1-5 断 开, 可 得 邻 接 表 图 和 回 路 链 表 如 图. 1 修 改 邻 接 图 (c), 如 图 10 所 示 ; 并 选 取 同 层 连 支 所 在 的 回 路 7--, 把 7- 变 为 树 支, 再 与 7-2-6- 合 并 成 新 的 回 路, 得 到 如 图 11 所 示 回 路 链 表. 6 7 2 7 图 10 邻 接 表 5 1 图 11 回 路 链 表.1.3 非 回 路 中 树 支 断 开 若 非 回 路 中 树 支 断 开, 则 电 气 岛 的 连 通 性 将 发 生 变 化, 最 终 发 生 分 裂. 在 此, 本 文 借 助 并 行 BFS( 并 行 深 度 优 先 搜 索 法 ), 由 断 开 节 点 沿 着 树 支 进 行 搜 索, 当 有 一 新 电 气 岛 形 成 即 结 束 搜 索, 拓 扑 更 新 完 成. 3 5 6 2 7 图 12 邻 接 表 5 3 图 邻 接 表 7 图 回 路 链 表 情 况 2: 断 开 树 支 在 多 条 回 路 中, 则 优 先 选 取 同 层 连 支 所 在 的 回 路 ( 否 则 任 取 一 条 跨 层 连 支 回 路 ), 将 连 支 变 为 树 支, 并 将 该 回 路 与 其 余 断 开 支 路 的 回 路 合 并, 在 此 基 础 上, 删 除 两 条 回 路 的 公 共 部 分, 并 将 该 回 路 删 除. 如 图 1 所 示 系 统, 若 树 支 7- 断 开, 则 电 气 岛 不 变, 如 图 1 所 示 系 统, 若 树 支 3-6 断 开, 由 于 其 不 在 回 路 中, 故 电 气 岛 发 生 解 裂. 此 时 由 断 开 节 点 3 和 节 点 6 同 时 分 别 进 行 并 行 BFS( 广 度 优 先 搜 索 ), 即 可 得 新 的 电 气 岛, 如 邻 接 表 10 所 示. 拓 扑 更 新 完 毕, 离 线 修 改 回 路 链 表, 可 得 回 路 链 表 L1 和 L2, 如 图 13 所 示. 5 1 7 6 2 2 图 13 回 路 链 表 1 软 件 技 术 算 法 Software Technique Algorithm
2016 年 第 25 卷 第 期 http://www.c-s-a.org.cn 计 算 机 系 统 应 用.2 网 络 中 支 路 闭 合 根 据 闭 合 支 路 两 节 点 的 不 同 位 置, 支 路 闭 合 可 分 为 2 种 情 况. 1) 同 一 电 气 岛 内 两 节 点 闭 合, 则 电 气 岛 连 通 性 不 受 影 响, 闭 合 支 路 为 连 支, 离 线 修 改 邻 接 表 和 回 路 链 表 即 可. 2) 不 同 电 气 岛 两 节 点 闭 合, 闭 合 支 路 为 树 支, 修 改 合 并 邻 接 表, 并 将 回 路 链 表 进 行 合 并..3 算 例 分 析 为 进 一 步 验 证 提 出 的 拓 扑 分 析 算 法 的 正 确 性 与 实 时 性, 在 四 核 AMD 处 理 器 Windows 10 操 作 系 统 环 境 下, 通 过 MatlabR2015a 中 并 行 计 算 工 具 箱 对 IEEE300- 节 点 系 统 和 波 兰 3375- 节 点 系 统 进 行 测 试 验 证 [11]. 本 文 算 法 与 两 种 传 统 矩 阵 算 法 进 行 了 比 较, 其 运 行 时 间 如 表 1 所 示. 表 1 几 种 算 法 拓 扑 分 析 所 需 时 间 算 法 程 序 运 行 时 间 /s 300 节 点 3375 节 点 邻 接 矩 阵 自 乘 法.336 15.12 连 通 矩 阵 平 方 法 2.021 5.07 本 文 算 法 0.6 0.06 由 表 1 可 以 看 出, 邻 接 矩 阵 自 乘 法 运 算 量 最 大, 耗 时 较 长 ; 连 通 矩 阵 平 方 法 减 少 了 矩 阵 自 乘 次 数, 时 间 大 幅 缩 短 ; 本 文 算 法 则 比 上 述 两 种 算 法 计 算 速 度 明 显 要 快. 当 拓 扑 结 构 发 生 变 化 时, 本 文 算 法 拓 扑 更 新 与 传 统 矩 阵 算 法 时 间 比 较, 运 行 时 间 如 表 2 所 示. 表 2 拓 扑 更 新 时 几 种 算 法 拓 扑 分 析 所 需 时 间 算 法 程 序 运 行 时 间 /s 300 节 点 3375 节 点 邻 接 矩 阵 自 乘 法.1 15.16 连 通 矩 阵 平 方 法 2.627 5.101 本 文 算 法 0.02 0.03 由 表 13 可 见, 拓 扑 结 构 发 生 变 化 时, 传 统 算 法 需 要 重 新 计 算, 耗 时 变 化 不 大 ; 而 本 文 算 法 只 局 部 并 行 更 新, 其 耗 时 明 显 减 少. 最 后, 通 过 上 述 两 个 表 可 以 表 明, 随 着 电 力 网 络 系 统 节 点 的 增 多, 本 文 算 法 与 传 统 算 法 相 比 效 率 优 势 更 加 明 显. 5 结 论 1) 本 文 从 并 行 计 算 的 角 度, 提 出 一 种 基 于 节 点 融 合 和 分 层 的 并 行 网 络 拓 扑 分 析 新 方 法. 正 常 情 况 下, 对 邻 接 表 的 各 节 点 进 行 并 行 融 合, 并 完 成 电 气 岛 邻 接 表 的 分 层 实 现 电 网 静 态 拓 扑 分 析 ; 然 后 离 线 生 成 电 气 岛 网 络 拓 扑 的 树, 并 根 据 连 支 生 成 回 路 链 表. 当 网 络 拓 扑 发 生 变 化 后, 根 据 节 点 所 在 回 路 链 表, 更 新 局 部 网 络 拓 扑 及 电 气 岛 邻 接 表, 当 断 开 树 支 不 在 任 何 回 路 时, 利 用 并 行 广 度 优 先 搜 索 法 进 行 搜 索, 完 成 拓 扑 更 新. 2) 针 对 IEEE300- 节 点 和 波 兰 3375- 节 点 系 统 电 网 进 行 拓 扑 分 析, 与 传 统 算 法 相 比, 计 算 结 果 验 证 了 该 方 法 的 正 确 性 和 快 速 性. 参 考 文 献 1 张 伯 明, 陈 寿 孙, 严 正, 等. 高 等 电 力 网 络 分 析. 北 京 : 清 华 大 学 出 版 社,2007. 2 王 湘 中, 黎 晓 兰. 基 于 关 联 矩 阵 的 电 网 拓 扑 辨 识. 电 网 技 术, 2001,25(2):10 12,16. 3 黄 正, 陈 凡, 张 雪 娇, 王 寒 娜, 刘 思 明. 电 网 拓 扑 分 析 算 法 的 研 究. 南 京 工 程 学 院 学 报 ( 自 然 科 学 版 ),2013,11(2):3. 姚 玉 斌, 叶 爽 利, 吴 志 良, 王 丹. 稀 疏 矩 阵 法 网 络 拓 扑 分 析. 电 力 系 统 保 护 与 控 制,2011,3(23):1 5,10. 5 姚 玉 斌, 宣 俭, 于 娜, 王 丹, 吴 志 良. 连 通 矩 阵 准 平 方 法 网 络 拓 扑 分 析. 电 力 系 统 保 护 与 控 制,2011,3(5):31 3. 6 Bose A, Clements K. Real-time modeling of power networks. Proc. of the IEEE, 17, 75(12): 1607 1622. 7 宋 少 群, 朱 永 利, 于 红. 基 于 图 论 与 人 工 智 能 搜 索 技 术 的 电 网 拓 扑 跟 踪 方 法. 电 网 技 术,2005,2(1):5. 梅 念, 石 东 源, 段 献 忠. 基 于 图 论 的 电 网 拓 扑 快 速 形 成 与 局 部 修 正 新 方 法. 电 网 技 术,200,32(13):35 3. 马 静, 张 俣 妤, 马 伟, 王 增 平. 基 于 关 联 矩 阵 标 记 法 与 回 路 矩 阵 的 电 网 拓 扑 分 析. 电 力 系 统 自 动 化,201,3(12):7 0. 10 张 烨, 周 苏 荃. 基 于 节 点 连 通 岛 合 并 法 网 络 动 态 拓 扑 分 析. 电 力 系 统 保 护 与 控 制,2013,1(5):72 76. 11 Zimmerman R, Murillo-Sanchez C, Gan DQ. MATPOWER: A MATLAB power system simulation package. Ithaca, NY: Power Systems Engineering Research Center at Cornell University, 2010. http://www.pserc.cornell.edu/ matpower/. [201-12-17]. Software Technique Algorithm 软 件 技 术 算 法 1