Data-driven Adaptive Adjustment Strategy for Strong Wind Alarm in High-speed Railway
-
摘要: 高速铁路在中国发展迅速，带来了全新的交通变革.较快的运行速度在带来效率提升的同时也增加了沿线强风对其运行安全的威胁.为了安全运行，铁路沿线部署了大量风速监测传感器，一旦监测到强风，将通过调度中心发出信号，调度沿线列车减速慢行甚至停车.在报警过程中，如何确定报警保持时间极具挑战.如果保持过短，则可能发生重复报警，增加处置次数，加重工作人员负担；若取消过晚，则影响轨道通过能力，带来不必要的效率损失.为此，本文提出一种高速铁路强风报警解除时间调整策略，用于改善这一问题.该策略通过轨道沿线部署的风速计装置，结合时空信息对短时未来强风情况进行预测，基于预测情况，自适应调整报警解除时间.该策略能够有效减少报警冗余时长，提高列车运行效率.Abstract: The rapid development of high-speed railways in China has changed the way people travel. The faster speed induces a growing threat of strong wind on safety. A large number of anemometers have been deployed alongside the railway for monitoring the strong wind. Dispatchers in the dispatch centers issue the scheduling instructions to the train drivers according to the measured wind speed. It is not trivial for the dispatchers to decide when to stop an alarm. If the alarm lasts too short, repeated alarms may occur, increasing the number of treatments and the burden on the staff. If it is stopped too late, track passing capacity will be affected and unnecessary efficiency loss may be caused. In this paper, an adjustment strategy for the stop time of high-speed railway alarm based on wind speed prediction is proposed to solve this emerged challenge. The strategy can effectively reduce the alarm redundancy time and improve operational efficiency.
-
Key words:
- High-speed railway /
- wind speed prediction /
- strong wind prediction /
- alarm duration adjustment
-
自多智能体系统理论提出以来, 其协调控制方面[1]的研究受到了国际学术界的广泛关注, 相关研究内容仅涉及多智能体系统一致性控制[2-3]或编队控制协议[4-5]、智能体动力学模型[6-7]和控制律设计[8-10], 而多智能体通信网络拓扑结构的连通性[11-12]研究未见有文献报道.通信网络拓扑结构的连通性是多智能体系统一致性控制与编队控制等的理论前提.网络连通性高效判定算法不仅是大规模多智能体系统一致性控制或编队控制的保证, 而且在图论[13-15]、现代移动通信[16-17]、计算机与交通[18]等各种网络中有着重要和广泛的应用.
在多智能体系统一致性控制或编队控制中, 如果两个智能体在规定的时间(通常为一个采样周期)内至少有一次数据交换, 则认为这两个智能体在通信方面是连通的.如此, 进行数据交换的多个智能体构成了一个移动通信网络.若所有智能体构成的这个移动通信网络在规定的时间内是连通的, 则称该网络的拓扑结构是连通的.这种多智能体通信网络常被建模为复杂无向网络(含自环和多重边), 而其拓扑结构的连通性检测和判定问题就可转化为复杂无向网络的连通性检测和判定问题.
迄今为止, 判定网络连通性的算法主要有两类:基于深度优先搜索技术的算法, 如Tarjan算法[19]和Gabow算法[20]等; 基于可达矩阵的算法和基于关系传递闭包的Warshall算法[21]等. Tarjan算法和Gabow算法是一类面向网络的直接搜索算法, 其优点是算法复杂度低(均为O$(n+m)$, 其中$n$为节点数, $m$为边数), 缺点是仅适合简单网络(无自环或多重边)且不易编程(需使用堆栈和标号技术). Warshall算法的优点是结构异常简洁且可采用效率更高的位运算方法, 缺点是算法复杂度高(O$(2n^3)$)且同样仅适用于简单网络.基于可达矩阵的连通性判定算法虽可用于复杂无向网络, 但由于其算法复杂度太高(O$(n^4)$)而很难适用于大规模移动通信网络或计算机互联网络的连通性判定.
针对具有$n$个节点的复杂无向网络, 本文给出了一种新的连通性判定算法, 该算法的时间复杂度和空间复杂度分别为O$(3n^2)$和O$(n^2+n)$.与基于可达矩阵的连通性判定算法和基于关系传递闭包的Warshall算法相比, 本文所给算法在时间复杂度上具有显著优势, 因而更适合大规模移动通信网络或计算机互联网络的连通性检测与判定.
1. 问题描述
给定一个无向网络$G$, 我们用$v_i\; (i = 1, 2, \cdots)$与$e_j\; (j=1, 2, \cdots)$分别表示$G$中的节点和边, 用$V(G) = \{v_1, v_2, \cdots\}$与$E(G) = \{e_1, e_2, \cdots\}$分别表示$G$中所有节点和所有边的集合, 则网络$G$可用一个偶对$(V, E)$表示, 记作$G = (V, E)$.
若用$n = |V(G)|$表示$V(G)$中节点的个数, $m = |E(G)|$表示$E(G)$中边的个数, 则网络$G$可另记为$G = (n, m)$. $n$称为网络$G$的阶数, 一个具有$n$个节点的网络称为$n$阶网络. $n$和$m$均为有限值的无向网络$G$称为有限无向网络.
除特别声明外, 本文所讨论的网络均指有限复杂无向网络, 原因在于大规模移动通信网络和计算机互联网络常被建模为复杂无向网络, 且复杂无向网络较简单无向网络具有更大的普适性.
定义1. 给定$n$阶无向网络$G$和网络的节点集$V(G) = \{v_1, v_2, \cdots, v_n\}$, 称$\overline{A} = \overline{A}(\overline{a_{ij}}) \in {\bf R}^{n \times n}$为$G$的邻接矩阵, 其中
$$ \begin{equation} { \overline{a_{ij}}} = \left\{ \begin{array}{ll} m_{ij}, & v_i~\text{与}~v_j~\text{之间有}~m_{ij}~\text{条边邻接} \\ 0, & v_i~\text{与}~v_j~\text{不邻接} \\ \end{array} \right. \end{equation} $$ 定义1中, $m_{ij} \geq 1$为整数.当$G$为简单无向网络时, $m_{ij} = 1$; 当$G$为复杂无向网络时, 则至少存在一个$m_{ij} > 1$.因本文仅考虑$G$的连通性, 所以将$m_{ij}$视为1并不影响$G$的连通性.
定义2. 给定$n$阶无向网络$G$和网络的节点集$V(G) = \{v_1, v_2, \cdots, v_n\}$, 设
$$ \begin{equation} { a_{ij}} = \left\{ \begin{array}{ll} 1, & \text{若}~v_i~\text{与}~v_j~\text{邻接}, \text{或}~i = j \\ 0, & \text{若~}v_i~\text{与}~v_j~\text{不邻接} \\ \end{array} \right. \end{equation} $$ (2) 则称: 1)由元素$a_{ij}\; (i, j = 1, 2, \cdots, n)$构成的$n$阶矩阵为网络$G$的邻居矩阵, 记作$A(G)$, 或简记为$A$; 2) $A$的第$i$行为网络$G$的第$i$个邻居集, 记作$A_i(G)$, 或简记为$A_i$.
我们以图 1和图 2所示无向网络为例来具体说明定义2中所涉及的概念.
图 1和图 2所示的无向网络各有8个节点, 它们的邻居矩阵分别是
$$ A(G1)=\begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{bmatrix} $$ $$ A(G2)=\begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{bmatrix} $$ 邻居集$A_i(Gj)\; (i = 1, 2, \cdots, n; j = 1, 2) $表示节点$v_i$与其邻接节点的关系, 其中取值为1的元素所对应的节点就是包含$v_i$在内的一个邻居组, 如$A_1(G1)$中包含$v_1$在内的邻居组是$\{v_1, v_2, v_3\}$.我们用$|A_i|$表示$A_i$中取值为1的元素个数、即邻居集$A_i$中邻居的个数, 如$|A_1(G1)| = 3$.显然, 每个邻居组中的节点及与它们相邻接的边一起构成网络$G$的一个连通子网络.此外, 我们称元素全为0的邻居集为零邻居集(对应空网络), 元素全为1的邻居集为全邻居集(对应连通网络).
给定一个无向网络, 由定义2和图论中邻接矩阵的定义可知, 复杂无向网络邻居矩阵与简单无向网络邻接矩阵的差别仅是对角线元素的取值有所不同, 邻居矩阵的对角线元素全为1, 而邻接矩阵的对角线元素全为0.
2. 算法理论基础与算法设计
2.1 算法理论基础
由定义2可知, $n\; (n \geq 2)$阶无向网络$G$的邻居集$A_i(G)$具有如下特点: 1)邻居集中只有2种元素1和0, 且至少有一个1; 2)各邻居集中元素的个数彼此相等; 3)每个邻居集对应一个邻居组, 每个邻居组彼此邻接且对应网络$G$的一个连通子网络.
定义2是一个新定义, 也是本文所给算法的基础.在具体给出基于邻居矩阵的网络连通性判定算法(下面简称本文所给算法)之前, 我们需先给出邻居集的相关运算规则.
定义3. 给定$n\; (n \geq 2)$阶无向网络$G$及相应的邻居集$A_i\; (i = 1, 2, \cdots, n)$, 邻居集的交与并的运算规则如下:
1) $A_i \cap A_j = \{z_k = x_k \cap y_k|x_k \in A_i, y_k \in A_j, k = 1, 2, \cdots, n\}$;
2) $A_i \cup A_j = \{z_k = x_k \cup y_k|x_k \in A_i, y_k \in A_j, k = 1, 2, \cdots, n\}$.
上式中各元素之间的运算($\cap$和$\cup$)均为布尔运算, 可采用效率更高的位运算方法实现.上述运算规则用于邻居集时具有明确意义:
1) 若两邻居集$A_i$、$A_j\; (i \neq j)$的交集$A_i \cap A_j$为零邻居集, 则由$A_i$、$A_j$决定的两个邻居组没有公共邻居, 反之则有公共邻居;
2) 没有公共邻居的两个邻居集的并集不构成新的邻居组, 即不构成$G$的新的连通子网络;
3) 有公共邻居的两个邻居集的并集$A_i \cup A_j$是一个新的邻居集, 该邻居集对应$G$的一个新的连通子网络; 新连通子网络是$A_i$、$A_j$所对应的连通子网络的并, 且显然有$|A_i \cup A_j| \geq \max(|A_i, A_j|)$.
本文所给算法主要涉及2种运算: 1)求两个邻居集$A_i$、$A_j\; (i \neq j)$的交集, 以验证它们是否有公共邻居, 若无则不求$A_i \cup A_j$; 2)若有公共邻居, 则求$A_i \cup A_j$.
两个邻居集$A_i$、$A_j\; (i \neq j)$的交并运算可按如下简便方法一次完成:
1) 求$A_i \cap A_j$, 对于$k= 1, 2, \cdots, n$, 依次检查$x_k \cap y_k$的取值, 当首次出现$x_k \cap y_k = 1$时, 停止本次求交运算;
2) 求$A_i \cup A_j = \{z_k = x_k \cup y_k|x_k \in A_i, y_k \in A_j, k = 1, 2, \cdots, n\}$.
本文所给算法的主要思路是: 1)给定$n\; (n \geq 2)$阶无向网络, 生成邻居矩阵$A(a_{ij}) \in {\bf R}^{n \times n}$和相应的邻居集$A_i\; (i = 1, 2, \cdots, n)$; 2)求$A_1 \cap A_i\; (i = 2, 3, \cdots, n)$以确定两个邻居集之间是否具有公共邻居; 若无, 令$i = i + 1$, 继续进行求交运算; 若有, 求$A_1 \cup A_i$并将运算结果赋予$A_1$; 上述求并与赋值运算结束后, 令$i = i + 1$, 继续进行这种求交和求并运算; 3)若上述运算进行到最后一步后, $|A_1| < $ $n$或$A_1$与所有剩余的邻居集之间没有相同的邻居, 则可判定所给网络不连通, 否则, 可判定所给网络连通.
2.2 算法设计
给定$n\; (n \geq 2)$阶无向网络$G$, 设: $G$的邻居矩阵$A(a_{ij})\in$ ${\bf R}^{n \times n}$和相应的邻居集$A_i\; (i = 1, 2, \cdots, n)$已经生成; $i$为$A(a_{ij})$的行循环变量, $j$与$k$为$A(a_{ij})$的列循环变量($i, j, k = 1, 2, \cdots, n$); $H=\{h_1$, $h_2$, $\cdots$, $h_n\}$为标号集, $h_i = 1$表示$A_1$与$A_i$进行过求并运算, $h_i = 0$表示$A_1$与$A_i$未进行过求并运算.下面我们具体给出复杂无向网络$G$的连通性判定算法.
基于邻居矩阵的复杂无向网络连通性判定算法
1) 赋初值: $i=j=k=0$, $H=\{h_i=0|i=1$, 2, $\cdots$, $n$};
2) $j=j+1$;
3) 如果$a_{1j}=0$且$j < n$, 转到2);如果$a_{1j}=$ $0$且$j=n$, 转到13);如果$a_{1j}=1$, $i=1$, 转到4);
4) $i=i+1$;
5) 如果$h_i=1$且$i < n$, 转到4);如果$h_i=1$且$i = n$, 转到11);如果$h_i=0$, 转到6);
6) 如果$a_{ij}=0$且$i < n$, 转到4);如果$a_{ij} = 0$且$i=n$, 转到11);如果$a_{ij}=1$, $k=1$, 转到7);
7) $k=k + 1$;
8) 如果$a_{ik}=0$且$k < n$, 转到7);如果$a_{ik} = 0$且$k=n$, 转到10);如果$a_{ik}=1$, $a_{1k} =:$ $a_{ik}$, 转到9);
9) 如果$k < n$, 转到7);如果$k=n$, 转到10);
10) $h_i =: 1$; 如果$i < n$, 转到4);如果$i=n$, 转到11);
11) 如果$j < n$, 转到2);如果$j=n$, $| A_1 | =$ $\sum_{j = 1}^{n}{ a_{1j}}$, 转到12);
12) 如果$|A_1|=n$, 输出结果:图$G$连通, 算法结束; 如果$|A_1| < n$, 转到13);
13) 输出结果:图$G$不连通; 算法结束.
步骤8)和10)中的符号$"=:"$表示赋值运算.
定理1. 任给$n\; (n \geq 2)$阶复杂无向网络$G$, 使用基于邻居矩阵的判定算法时, 网络$G$连通的充分必要条件是算法结束后$|A_1| = n$.
证明. 由本文所给算法可知, 当有公共邻居时, 每进行一次求并运算, $A_1$中所包含的邻居数(取值为1的元素数)或者保持不变或者增加.当保持不变且$A_1$包含网络$G$的全部节点, 即$|A_1| = n$时, 网络$G$连通; 当邻居数增加并最终导致$|A_1| = n$时, 网络$G$也连通.
反之, 设$|A_1| < n$时, 网络$G$连通. $|A_1| < n$有两种情况: 1) $|A_1| = 1$, 这表明节点$v_1$是悬挂点, 没有邻接边, 所以网络$G$不连通; 2)至少存在一个$A_i\; (i \in \{2, 3, \cdots, n\})$, 它在算法结束后与$A_1$没有相同的邻居, 即$A_i$对应的子网络与$A_1$对应的子网络没有公共节点, 这便导致$|A_1| < n$, 网络$G$不连通.上述两种情况都与假设矛盾, 则若要网络$G$连通, 必须要$|A_1| = n$.
图 3是本文所给算法的框图.
图 3 基于邻居矩阵的复杂无向网络连通性判定算法框图Fig. 3 Block diagram of the connectivity determination algorithm for complex undirected networks based on the neighbor matrix2.3 算法应用举例
我们以图$G1$和图$G2$所示无向网络为例来说明本文所给算法的具体应用.
例1. 图$G1$所示无向网络有8个节点, 其邻居矩阵$A(G1) \in$ ${\bf R}^{8 \times 8}$.算法运行前, $|A_1(G1)| = 3$, 算法运行后: $j = 1$, $|A_1(G1)| = 4$; $j = 2$, $|A_1(G1)| = 4$; $j = 3$, $|A_1(G1)| = 6$; $j = 4$, $|A_1(G1)| = 8$; $j = 5, 6, 7, 8$时, $|A_1(G1)| = 8$.因此, 可判定图$G1$所示无向网络连通.
例2. 图$G2$所示无向网络有8个节点, 其邻居矩阵$A(G2) \in {\bf R}^{8 \times 8}$.算法运行前, $|A_1(G2)| = 3$, 算法运行后: $j = 1$, $|A_1(G2)| = 3$; $j = 2$, $|A_1(G2)| = 3$; $j = 3$, $|A_1(G2)| = 3$; $j = 4, 5, 6, 7, 8$时, $|A_1(G2)| = 3 < 8$.因此, 可判定图$G2$所示无向网络不连通.
3. 算法复杂性分析
3.1 算法的时间复杂度
给定$n\; (n \geq 2)$阶无向网络$G$, 设其相应的邻居矩阵、邻居集分别为$A(a_{ij}) \in {\bf R}^{n \times n}$和$A_i\; (i = 1, 2, \cdots, n)$.本文所给算法涉及$a_{ij}$是否为1的比较运算, 将$a_{ik}\; (i \geq 2)$的值赋予$a_{1k}$的赋值运算, 以及两个元素$a_{1j}$、$a_{1k}\; (j \neq k)$的布尔或运算.按算法复杂性分析的常规做法, 我们将不考虑赋值运算并将一次比较运算视为一次加法运算.下面, 我们分3部分具体分析本文所给算法的时间复杂度.
1) 对于每一个$j \in \{1, 2, \cdots, n\}$, 本文所给算法需要比较$a_{ij}\; (1 \leq i \leq n)$是否等于1, 用于确定是否存在某个$i\; (2 \leq i \leq n)$使得$a_{1j} = a_{ij} = 1$, 即确定$A_1 \cap A_i$为非零邻居集.对于每一给定的$j$, 这种比较运算共需$n$次, 相当于$n$次加法运算.考虑最坏情况, 即当所有的$a_{1j} = 1\; (1 \leq j \leq n)$时, 这种比较运算总共需要$n^2$次加法运算.
2) 当$A_1 \cap A_i\; (2 \leq i \leq n)$为非零邻居集时, 需进行$A_1 \cup A_i$运算.考虑最坏情况, 即当所有的$a_{ik} = 1\; (2 \leq k \leq n)$时, $A_1 \cup A_i$需要$2(n - 1)$次布尔或运算, 当$i$遍历所有的取值时, 总共需要$2(n - 1)^2$次布尔或运算.
3) 本文所给算法最后需要求$|A_1|$并判定$|A_1|$是否小于$n$, 这部分总共需要$n$次加法运算.
设$J$为总的计算次数, 由上述3部分计算结果可知
$$ J = n^2 + 2(n - 1)^2 + n = 3n^2 - 3n + 2 $$ 因此, 本文所给算法的时间复杂度的上界为O$(3n^2)$.相比之下可知, 就复杂无向网络的连通性判定而言, 本文所给算法的时间复杂度远低于Warshall算法(O$(2n^3)$)和基于可达矩阵算法(O$(n^4)$)的时间复杂度.
3.2 算法的空间复杂度
本文所给算法仅需生成和使用一个邻居矩阵$A(a_{ij}) \in {\bf R}^{n \times n}$和一个标号集$H = \{h_i = 0$或$h_i = 1|i = 1, 2, \cdots, n\}$.因邻居矩阵元素的取值或为0或为1, 所以生成邻居矩阵共需占用$n^2$个存储单元.同理, 标号集$H$共需占用$n$个存储单元.因此, 本文所给算法的空间复杂度的上界为O$(n^2 + n)$.不难理解, 本文所给算法比Warshall算法和基于可达矩阵的算法具有更低的空间复杂度.
3.3 算法的最优分布式实现
分布式计算是一种分组并行计算, 可极大地提高计算效率.由图论和算法结构理论可知, 本文所给算法适合分布式计算.下面, 我们将简要讨论这个问题.
给定$n\; (n \geq 2)$阶无向网络$G$, 我们可以按如下规则将$n$个节点分成$k\; (2 \leq k \leq n)$组, 使得:
1) 每个组中的节点数不少于1个;
2) 任意两个组不包含相同的节点.
如此:
1) 当我们将每个组中的全部节点集结成(视作)一个节点时, $G$就成为具有$k$个节点的网络;
2) 每个组中的全部节点连同它们的邻接边一起构成$G$的一个子网络, 且全部$k$个子网络的并就是$G$;
3) 每个子网络都连通且全部$k$个子网络也连通, 则$G$连通, 否则, $G$不连通.
如果能将本文所给算法分别用于上述每个子网络及全部$k$个子网络时, 除仍可判定$G$的连通性外, 计算量将会大幅度减小.现在的问题是, 如何分组可使总的计算量达到最小?
定理2. 任给$n\; (n \geq 2)$阶无向网络$G$, 将$n$个节点分成$k$组.若分组数$k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}}$且每个组中的节点数均为$m = (2n)^{\frac{1}{3}}$, 则将本文所给算法用于$G$的连通性判定时, 计算量将会达到最小.
证明. 本文所给算法的时间复杂度为O$(3n^2)$, 即最大可能的计算量为$3n^2$.设将$n$个节点分成$k\; (2 \leq k \leq n)$组, 每个组中的节点数为$m_i\; (1 \leq i \leq k)$, $\sum_{i = 1}^{k}{ m_i} = n$, $J$为判定$G$的连通性所需最大计算量.由前面的分析可知, 判定每个子网络($m_i$个节点)连通性所需最大计算量为$3m_i^2$, 判定$k$个子网络连通性所需最大计算量为$3k^2$.如此
$$ \begin{align} \label{eq:3} J = \, &3k^2 + \sum\limits_{i = 1}^{k}{ [3m_i^2]} =\nonumber\\ & 3\left\{k^2 + \sum\limits_{i = 1}^{k - 1}{ m_i^2} + m_k^2\right\} =\nonumber\\ & 3\left\{k^2 + \sum\limits_{i = 1}^{k - 1}{ m_i^2} + (n - \sum\limits_{i = 1}^{k - 1}{ m_i})^2\right\} \end{align} $$ (3) 对于$1 \leq i \leq (k - 1)$, 我们有
$$ \begin{align} \label{eq:2} \frac{\partial J}{\partial m_i} =\, & 6\left[m_i - \left(n - \sum\limits_{i = 1}^{k - 1}{ m_i}\right)\right] =\nonumber\\& 6(m_i - m_k) \end{align} $$ (4) 令$\dfrac{\partial J}{\partial m_i} = 0$, 可得$m_1 = m_2 = \cdots = m_{k - 1} = m_k$.这表明, 若要$J$达到最小, 每个组中的节点数必须相等.设每个组的节点数为$m_i = m\; (1 \leq i \leq k)$, 代入前式可得: $J = 3(k^2 + km^2) = 3\left(k^2 + \dfrac{n^2}{k}\right)$.令$\dfrac{\partial J}{\partial k} = 3\left(2k - \dfrac{n^2}{k^2}\right) = 0$, 可得$k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}}$.另一方面, $J = 3(k^2 + km^2) = 3\left(\dfrac{n^2}{m^2} + nm\right)$.令$\dfrac{\partial J}{\partial m} = 3\left(n - \dfrac{2n^2}{m^3}\right) = 0$, 可得$m = (2n)^{\frac{1}{3}}$.这表明, 当$k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}}$, $m = (2n)^{\frac{1}{3}}$时, 使用本文所给算法可使计算量达到最小.
定理2所确定的分组方式就是本文所给算法的最优分布式实现方式.分组与不分组情况下的计算量之比为$3(2n)^{-\frac{2}{3}}$.显然, $n$越大, 计算量下降的幅度也越大.当$n = 500$时, 分组情况下的计算量仅是不分组情况下的计算量的$3\, \%$.
需要说明的是, 定理2中的$k$和$m$需取整数.下面, 我们举例说明如何确定$k$和$m$的取值问题.
例3. 设某一无向网络$G$具有$n = 497$个节点, 试确定节点的最优分组结果.
由定理2可得: $k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}} = \left(\dfrac{1}{2} \times 247\, 009\right)^{\frac{1}{3}} < \left(\dfrac{1}{2} \times 250\, 000\right)^{\frac{1}{3}} = 50$, 即$k < 50$; 同理可得, $k = \left(\dfrac{n^2}{2}\right)^{\frac{1}{3}} = \left(\dfrac{1}{2} \times 247\, 009\right)^{\frac{1}{3}} > \left(\dfrac{1}{2} \times 235\, 298\right)^{\frac{1}{3}} = 49$, 即$k > 49$.我们按两种方式分组: 1) $k = 50$, $m_i = 10\; (1 \leq i \leq 49)$, $m_{50} = 7$, 最大可能的计算量为$J = 3(50^2 + 49 \times 10^2 + 7^2) = 22\, 347$; 2) $k = 49$, $m_i = 10\; (1 \leq i \leq 42)$, $m_i = 11\; (43 \leq i \leq 49)$, 最大可能的计算量为$J = 3(49^2 + 42 \times 10^2 + 7 \times 11^2) = 20\, 166$.显然, 第2种分组方式可使最大可能的计算量达到最小.因此, $k$和$m$的取值应按第2种分组方式确定.
在大规模多智能体编队控制问题中, 各个智能体的相对位置比较固定, 定理2所给的最优分组方法在其通信网络的连通性判定方面更能发挥作用.
4. 结论
在引言部分, 我们论述了网络连通性判定算法、特别是高效连通性判定算法的理论与现实意义.
本文第1节给出了复杂无向网络邻居矩阵和邻居集的定义及相关概念, 它们是基于邻居矩阵的复杂无向网络连通性判定算法, 即本文所给算法的前提.
本文第2节给出了邻居集交与并的运算规则、相关概念及其集合解释.在此基础上, 给出了基于邻居矩阵的复杂无向网络连通性判定算法.该算法是本文的主要贡献, 显然它也适用于简单无向网络的连通性判定.
第3节分析给出了本文所给算法的时间复杂度O$((3n^2))$和空间复杂度O$((n^2 + n))$, 它较Warshall算法和基于可达矩阵的算法具有低得多的时间复杂度和空间复杂度.此外, 本节还给出了可使最大可能的计算量达到最小的最优分布式计算规则, 相关结果则是本文的另一有意义的贡献.
与现有算法相比, 本文所给算法的时间复杂度和空间复杂度均非常低、易于分布式计算, 更适合大规模动态复杂无向网络的连通性判定.需要说明的是, 本文所给算法不能直接用于复杂有向网络的连通性判定.我们今后的工作是将上述结果推广到复杂有向网络, 以期得到更一般和更高效的连通性判定算法.
-
表 1 高速铁路不同风速下行驶速度规定
Table 1 Speed constraints for the high-speed train at different wind speeds
风速(m/s) 列车运行规定(km/h) 15~20 限速300 20~25 限速200 25~30 限速120 > 30 禁止通行 
下载: 导出CSV
表 2 实验数据集
Table 2 Dataset for experiments
测量点 数量 均值(m/s) 最大值(m/s) 最小值(m/s) 测量点1 $1\, 209\, 600$ $3.64$ $20.0$ $-0.7$ 测量点2 $1\, 209\, 600$ $3.63$ $24.9$ $-0.4$ 测量点3 $1\, 209\, 600$ $3.63$ $29.9$ $-1.0$ 测量点4 $1\, 209\, 600$ $3.63$ $29.5$ $-1.2$ 测量点5 $1\, 209\, 600$ $3.62$ $22.7$ $-0.3$
下载: 导出CSV
表 3 风速预测准确度
Table 3 Performances of the wind prediction
模型 MAE (m/s) RMSE (m/s) MAPE (%) ARIMA 1-step 2.02 3.46 1.35 5-step 2.14 3.50 1.36 10-step 2.24 3.57 1.37 LSTM(128) 1-step 1.21 1.60 0.65 5-step 1.39 1.87 0.69 10-step 1.51 2.25 0.75 STA-RNN 1-step 0.98 1.25 0.20 5-step 1.11 1.40 0.22 10-step 1.21 1.80 0.25
下载: 导出CSV
表 4 强风预测效果
Table 4 Performances of the strong wind prediction
模型 精确度 召回率 $\rm F_{\rm score}$ STA-RNN 1.0 0.65 0.79 STA-RNN+SVM 1.0 0.73 0.84
下载: 导出CSV
-
[1] 王瑞, 陈苒, 包云. JR东日本铁路大风监测技术研究, 中国铁路, 2018, 07:96-102 http://d.old.wanfangdata.com.cn/Periodical/zhongguotl201807020Wang Rui, Chen Ran, Bao Yun. The study on JR-East monitoring technology of strong wind. China Railway, 2018, 07:96-102 http://d.old.wanfangdata.com.cn/Periodical/zhongguotl201807020 [2] 窦垭锡, 蔺伟, 刘畅.高速铁路大风报警信息实时传输系统方案研究.铁道运输与经济, 2018, 40(09):57-61, 85 http://d.old.wanfangdata.com.cn/Periodical/tdysyjj201809012Dou Ya-Xi, Lin Wei, Liu Chang. A research on the scheme of the real-time wind alarm transmission system of high-speed railway. Railway Transport and Economy, 2018, 40(09):57-61, 85 http://d.old.wanfangdata.com.cn/Periodical/tdysyjj201809012 [3] 王瑞.高速铁路大风监测系统运用规则优化研究.铁道运输与经济, 2018, 40(4):48-51, 57 http://d.old.wanfangdata.com.cn/Periodical/tdysyjj201804009Wang Rui. A study on the application rules of high-speed railway wind monitoring system. Railway Transport and Economy, 2018, 40(4):48-51, 57 http://d.old.wanfangdata.com.cn/Periodical/tdysyjj201804009 [4] Landberg L. Short-term prediction of the power production from wind farms. Journal of Wind Engineering and Industrial Aerodynamics, 1999, 80(1-2):207-220 doi: 10.1016/S0167-6105(98)00192-5 [5] Negnevitsky M, Johnson P, Santoso S. Short term wind power forecasting using hybrid intelligent systems. In: Proceedings of the 2007 IEEE Power Engineering Society General Meeting. Tampa, FL, USA: IEEE, 2007. 1-4 [6] Negnevitsky M, Potter C W. Innovative short-term wind generation prediction techniques. In: Proceedings of the 2006 Power Systems Conference and Exposition. Atlanta, GA, USA: IEEE, 2006. 60-65 [7] Ma L, Luan S Y, Jiang C W, Liu H L, Zhang Y. A review on the forecasting of wind speed and generated power. Renewable and Sustainable Energy Reviews, 2009, 13(4):915-920 doi: 10.1016/j.rser.2008.02.002 [8] Kiplangat D C, Asokan K, Kumar K S. Improved week-ahead predictions of wind speed using simple linear models with wavelet decomposition. Renewable Energy, 2016, 93:38-44 doi: 10.1016/j.renene.2016.02.054 [9] Box G E P, Jenkins G M, Reinsel G C, Ljung, G M. Time Series Analysis: Forecasting and Control. John Wiley & Sons, 2015 [10] Cadenas E, Rivera W, Campos-Amezcua R, Heard C. Wind speed prediction using a univariate ARIMA model and a multivariate NARX model. Energies, 2016, 9(2):109 doi: 10.3390/en9020109 [11] Yunus K, Thiringer T, Chen P. ARIMA-based frequency-decomposed modeling of wind speed time series. IEEE Transactions on Power Systems, 2016, 31(4):2546-2556 doi: 10.1109/TPWRS.2015.2468586 [12] Singh S N, Mohapatra A. Repeated wavelet transform based ARIMA model for very short-term wind speed forecasting. Renewable Energy, 2019, 136:758-768. doi: 10.1016/j.renene.2019.01.031 [13] Li L, Ota K, Dong M. Deep learning for smart industry:efficient manufacture inspection system with fog computing. IEEE Transactions on Industrial Informatics, 2018, 14(10):4665-4673 doi: 10.1109/TII.2018.2842821 [14] Li H, Ota K, Dong M. Learning IoT in edge:deep learning for the internet of things with edge computing. IEEE Network, 2018, 32(1):96-101 doi: 10.1109/MNET.2018.1700202 [15] Ota K, Dao M S, Mezaris V, Mezaris V, De Natale F G. Deep learning for mobile multimedia: a survey. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 2017, 13(3s): 34: 1-34: 22 [16] Kaur T, Kumar S, Segal R. Application of artificial neural network for short term wind speed forecasting, In: Proceedings of the 2016 Biennial International Conference On Power and Energy Systems: Towards Sustainable Energy. Bengaluru, India: IEEE, 2016. 1-5 [17] Chang G W, Lu H J, Chang Y R, Lee Y D. An improved neural network-based approach for short-term wind speed and power forecast. Renewable Energy, 2017, 105:301-311 doi: 10.1016/j.renene.2016.12.071 [18] Hu Q, Zhang R, Zhou Y. Transfer learning for short-term wind speed prediction with deep neural networks. Renewable Energy, 2016, 85:83-95 doi: 10.1016/j.renene.2015.06.034 [19] 汤鹏杰, 王瀚漓, 许恺晟. LSTM逐层多目标优化及多层概率融合的图像描述.自动化学报, 2018, 44(7):1237-1249 doi: 10.16383/j.aas.2017.c160733Tang Peng-Jie, Wang Han-Li1, Xu Kai-Sheng. Multi-objective layer-wise optimization and multi-level probability fusion for image description generation using LSTM. Acta Automatica Sinica, 2018, 44(7):1237-1249 doi: 10.16383/j.aas.2017.c160733 [20] Dong D, Sheng Z, Yang T. Wind power prediction based on recurrent neural network with long short-term memory units. In: Proceedings of the 2018 International Conference on Renewable Energy and Power Engineering. Toronto, Canada: IEEE, 2018. 34-38 [21] Qu X Y, Kang X N, Zhang C, Jiang S, Ma X D. Short-term prediction of wind power based on deep long short-term memory. In: Proceedings of the 2016 IEEE PES Asia-Pacific Power and Energy Engineering Conference. Xi'an, China: IEEE, 2016. 1148-1152 [22] Zhu Q M, Chen J F, Shi D Y, Zhu L, Bai X, Duan X Z, Liu Y L. Learning temporal and spatial correlations jointly: a unified framework for wind speed prediction. IEEE Transactions on Sustainable Energy, 2019, DOI: 10.1109/TSTE.2019.2897136 [23] Kalchbrenner N, Blunsom P. Recurrent continuous translation models. In: Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing. Seattle, WA, USA: ACL, 2013. 1700-1709 [24] Venugopalan S, Rohrbach M, Donahue J, Mooney R, Darrell T, Saenko K. Sequence to sequence-video to text. In: Proceedings of the 2015 IEEE International Conference on Computer Vision. Santiago, Chile: IEEE, 2015. 4534-4542 [25] Sutskever I, Vinyals O, Le Q V. Sequence to sequence learning with neural networks. In: Proceedings of the 2014 Advances in Neural Information Processing Systems. Montreal, Canada: MIT Press, 2014. 3104-3112 [26] Cho K, Van Merrienboer B, Bahdanau D, Bengio Y. On the properties of neural machine translation: encoder-decoder approaches[Online], available: https: //arxiv.org/pdf/1409.1259.pdf.October 7, 2014 [27] Qin Y, Song D, Chen H, Cheng W, Jiang G, Cottrell G. A dual-stage attention-based recurrent neural network for time series prediction. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence. San Francisco, CA, USA: AAAI Press, 2017. 2627-2633 [28] Vapnik V N. An overview of statistical learning theory. IEEE Transactions on Neural Networks, 1999, 10(5):988-999 doi: 10.1109/72.788640 [29] Du P, Wang J, Yang W, Niu T. Multi-step ahead forecasting in electrical power system using a hybrid forecasting system. Renewable Energy, 2018, 122:533-550 doi: 10.1016/j.renene.2018.01.113 [30] Xing Z, Pei J, Keogh E. A brief survey on sequence classification. ACM SIGKDD Explorations Newsletter, 2010, 12(1):40-48 doi: 10.1145/1882471.1882478 [31] He Y, Pei J, Chu X, Wang Y, Jin Z, Peng G. Characteristic subspace learning for time series classification. In: Proceedings of the 2018 IEEE International Conference on Data Mining. Singapore, Singapore: IEEE, 2018: 1019-1024 [32] Liang Y, Ke S, Zhang J, Yi X, Zheng Y. GeoMAN: multi-level attention networks for geo-sensory time series prediction. In: Proceedings of the 2018 International Joint Conference on Artificial Intelligence. Stockholm, Sweden: Morgan Kaufmann, 2018. 3428-3434 [33] Chen J, Hu K, Wang Q, Sun Y, Shi Z, He S. Narrowband internet of things:implementations and applications. IEEE Internet of Things Journal, 2017, 4(6):2309-2314 doi: 10.1109/JIOT.2017.2764475 [34] Zhou C, Gu Y, He S, Shi Z. A robust and efficient algorithm for coprime array adaptive beamforming. IEEE Transactions on Vehicular Technology, 2017, 67(2):1099-1112 http://cn.bing.com/academic/profile?id=dfd568a5657d9cf3ae1fe8872afdad51&encoded=0&v=paper_preview&mkt=zh-cn [35] Li C, He S, Shi Z, Chen J. Efficient antenna allocation algorithms in millimetre wave wireless communications. IET Communications, 2017, 12(5):543-551 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=73ac8d295985331f17bf3ae8336dfc63 期刊类型引用(4)
1. 周敏，顾灏璇，董海荣，刘仁伟，刘瑄. 考虑动车组周转和到发线运用的高铁列车运行多计划协同调整. 自动化学报. 2024(08): 1577-1588 . 
本站查看2. 林鹏，田宇，袁志明，张琦，董海荣，宋海锋，阳春华. 高速铁路信号系统运维分层架构模型研究. 自动化学报. 2022(01): 152-161 . 本站查看3. 杜广宇. 接触网支柱对风速计测量的影响及对策. 武汉大学学报(工学版). 2021(05): 454-460 . 百度学术4. 张煜昕，李永刚，史鸣谦，郭力兵，杨海民，胡上成. 数据驱动的船载外测数据实时处理软件架构设计与实现. 计算机工程与科学. 2021(11): 1979-1985 . 百度学术其他类型引用(5)
-
下载:
计量
- 文章访问数: 2287
- HTML全文浏览量: 633
- PDF下载量: 218
- 被引次数: 9
