论文标题
自动稳定的构造最小薄弱的$ \ MATHCAL {ST} $ - 可触及的无循环图
Self-Stabilizing Construction of a Minimal Weakly $\mathcal{ST}$-Reachable Directed Acyclic Graph
论文作者
论文摘要
我们提出了一种自动化算法来构建一个最小的弱$ \ Mathcal {st} $ - 可触及的有向无环图（DAG），该图适用于在无线网络上路由消息。给定任意，简单，连接和无方向的图$ g =（v，e）$和两组节点，发件人$ \ nathcal {s}（\ subset v）$，并且目标是$ \ mathcal {t}（\ subset v）$，$ \ vec $ \ v $ $ \ v $ - $ g $上的dag，如果$ \ vec {g} $是一个dag，每个发件人都可以达到至少一个目标，并且每个目标都可以从$ \ vec {g} $中的至少一个发件人达到。我们说，如果$ \ vec {g} $的任何适当的子图形不再是弱$ \ Mathcal {st st} $，那么$ g $上的弱$ \ MATHCAL {st} $ - 触发dag $ \ vec {g} $是最小的。此DAG是原始版本（或强烈）$ \ Mathcal {st} $ - 可触及的DAG的轻松版本，每个发件人都可以达到每个目标。这是因为强烈的$ \ Mathcal {st} $ - 可触及的dag $ g $并不总是存在；某些图形也没有强烈的$ \ MATHCAL {ST} $ - 即使在情况下达到DAG，即使在$ | \ Mathcal {s} | = | = | \ Mathcal {t} | = 2 $中。另一方面，所提出的算法总是构造一个弱$ \ MATHCAL {ST} $ - 对于任何$ | \ MATHCAL {S} | $和$ | \ MATHCAL {t} | $的可及dag。此外，提出的算法是自动稳定的。即使构造的DAG通过分解或用尽在DAG中的电弧的节点的电池的电池偏离可及性要求，该算法也会自动重建DAG以再次满足需求。算法的收敛时间为$ O（d）$异步回合，其中$ d $是给定图的直径。我们进行小型模拟来评估所提出的算法的性能。仿真结果表明，当发送者节点或目标节点的数量较大时，其执行时间会减少。
We propose a self-stabilizing algorithm to construct a minimal weakly $\mathcal{ST}$-reachable directed acyclic graph (DAG), which is suited for routing messages on wireless networks. Given an arbitrary, simple, connected, and undirected graph $G=(V, E)$ and two sets of nodes, senders $\mathcal{S} (\subset V)$ and targets $\mathcal{T} (\subset V)$, a directed subgraph $\vec{G}$ of $G$ is a weakly $\mathcal{ST}$-reachable DAG on $G$, if $\vec{G}$ is a DAG and every sender can reach at least one target, and every target is reachable from at least one sender in $\vec{G}$. We say that a weakly $\mathcal{ST}$-reachable DAG $\vec{G}$ on $G$ is minimal if any proper subgraph of $\vec{G}$ is no longer a weakly $\mathcal{ST}$-reachable DAG. This DAG is a relaxed version of the original (or strongly) $\mathcal{ST}$-reachable DAG, where every target is reachable from every sender. This is because a strongly $\mathcal{ST}$-reachable DAG $G$ does not always exist; some graph has no strongly $\mathcal{ST}$-reachable DAG even in the case $|\mathcal{S}|=|\mathcal{T}|=2$. On the other hand, the proposed algorithm always constructs a weakly $\mathcal{ST}$-reachable DAG for any $|\mathcal{S}|$ and $|\mathcal{T}|$. Furthermore, the proposed algorithm is self-stabilizing; even if the constructed DAG deviates from the reachability requirement by a breakdown or exhausting the battery of a node having an arc in the DAG, this algorithm automatically reconstructs the DAG to satisfy the requirement again. The convergence time of the algorithm is $O(D)$ asynchronous rounds, where $D$ is the diameter of a given graph. We conduct small simulations to evaluate the performance of the proposed algorithm. The simulation result indicates that its execution time decreases when the number of sender nodes or target nodes is large.
