Beeping models are models for networks of weak devices, such as sensor networks or biological networks. In these networks, nodes are allowed to communicate only via emitting beeps: unary pulses of energy. Listening nodes only the capability of {\it carrier sensing}: they can only distinguish between the presence or absence of a beep, but receive no other information. The noisy beeping model further assumes listening nodes may be disrupted by random noise. Despite this extremely restrictive communication model, it transpires that complex distributed tasks can still be performed by such networks. In this paper we provide an optimal procedure for simulating general message passing in the beeping and noisy beeping models. We show that a round of \textsf{Broadcast CONGEST} can be simulated in $O(\Delta\log n)$ round of the noisy (or noiseless) beeping model, and a round of \textsf{CONGEST} can be simulated in $O(\Delta^2\log n)$ rounds (where $\Delta$ is the maximum degree of the network). We also prove lower bounds demonstrating that no simulation can use asymptotically fewer rounds. This allows a host of graph algorithms to be efficiently implemented in beeping models. As an example, we present an $O(\log n)$-round \textsf{Broadcast CONGEST} algorithm for maximal matching, which, when simulated using our method, immediately implies a near-optimal $O(\Delta \log^2 n)$-round maximal matching algorithm in the noisy beeping model.
翻译:脉冲信号模型是针对弱设备网络,例如传感器网络或生物网络的网络模型。在这些网络中,节点只能通过发射脉冲信号进行通信:一种一元脉冲能量信号。接收节点只有一项「载波感知」的能力:只能区分脉冲信号的存在或不存在,但不能获得其他信息。嘈杂的脉冲信号模型还假定受到随机噪声的干扰。尽管具有极其严格的通信模型,但这些网络仍然可以执行复杂的分布式任务。在本文中,我们提供了一种在脉冲和嘈杂脉冲模型中模拟普遍信息传递的最优过程。我们展示出,可以在嘈杂(或非噪声性)脉冲模型的$O(\Delta\log n)$ 轮内模拟 \textsf{Broadcast CONGEST}。而在该模型中,在 $O(\Delta^2\log n)$ 轮内模拟\textsf{CONGEST}。这里的 $\Delta$ 是网络的最大度数。我们还证明了没有模拟可以使用渐近更少的轮数。这允许许多图算法在脉冲信号模型中高效实现。例如,我们提出了一个 $O(\log n)$- 轮 \textsf{Broadcast CONGEST}算法来查找最大匹配。当使用我们的方法进行模拟时,它立即意味着在噪声脉冲模型中可以获得近乎最优的 $O(\Delta \log^2 n)$-轮最大匹配算法。