On Efficient Gossiping in Radio Networks
On Efficient Gossiping in Radio Networks
复制标题
论无线电网络中的有效八卦
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
L. Gąsieniec
中科院分区：
文献类型：
--
作者：
L. Gąsieniec
通信网络通常被建模为连接图，其中节点通过（无向）有向链路交换信息（消息）。相关的通信协议决定了消息交换的方式。最流行的网络模型有：（1）消息传递模型，其中一个节点在一轮中可以通知其所有邻居； (2)电话模型也称为匹配模型，其中在执行消息交换的每个圆边中形成连接图中的匹配。最近，由于无线技术 (3) 的到来，无线网络模型在算法界引起了更多关注。在该模型中，节点发送的消息的目的地是该节点的所有邻居。然而，假设由于干扰，当且仅当其邻居之一在这一轮期间发送消息时，节点才能成功接收消息。
与信息传播相关的两个最基本的问题是：广播（一对多通信）和闲聊（全面信息交换）。在广播中，目标是将一条信息（广播消息）从一个可区分的源节点分发到网络中的所有其他节点。然而，在八卦中，网络中的每个节点都应该将自己的消息分发给网络中的每个其他节点。广播问题引起了人们的广泛关注，从而在上述模型中产生了大量有效的算法解决方案。然而，人们对八卦的了解却少之又少。后一个问题在算法上更复杂（原则上它是同时多源广播），因此它涉及更先进的通信策略。最近，由于人们对推动传感器网络基本应用的信息聚合方法的兴趣日益浓厚，对有效八卦方法的进一步研究获得了额外的动力。此外，当允许使用随机化时，八卦为优惠券收集问题的分布式版本提供了有趣的背景。
本文是对高效无线电八卦最重要发展的简短调查。我们在各种模型的背景下讨论确定性和随机的通信方法，同时考虑与网络大小和拓扑、连接方向以及消息大小上限相关的知识。利用这个机会，我们还进一步了解了在高效无线电广播和八卦研究期间出现的几种组合结构和算法解决方案。
A communication network is very often modelled as a graph of connections in which the nodes exchange information (messages) via (un)directed links. An associated communication protocol determines the way the messages are exchanged. Among the most popular network models are: (1) the message passing model in which a node in one round can inform all its neighbours; (2) the telephone model also known as the matching model where in each round edges along which the exchange of messages is performed form a matching in the graph of connections. More recently, due to arrival of wireless technology (3) the radio network model attracted more attention in algorithms community. In this model, a message transmitted by a node is destined for all neighbours of this node. It is assumed, however, that due to interference a node can successfully receive a message if and only if exactly one of its neighbours transmits during this round.
The two most fundamental problems in relation to information dissemination are: broadcasting (one-to-all communication) and gossiping (total information exchange). In broadcasting, the goal is to distribute a piece of information (broadcast message) from a distinguished source node to all other nodes in the network. In gossiping, however, each node in the network is expected to distribute its own message to every other node in the network. A lot of attention has been given to the broadcasting problem that resulted in a large volume of efficient algorithmic solutions in the models described above. However, much less is known about gossiping. The latter problem is more complex algorithmically (in principle it is a simultaneous multiple-source broadcasting) thus it concerns more advanced communication strategies. Further study on efficient gossiping methods gained recently an extra motivation through an increasing interest in, e.g., information aggregation methods that propel fundamental applications in sensor networks. Also when the use of randomisation is permitted gossiping provides an interesting context for a distributed version of the coupon collector problem.
This paper is a short survey on the most important developments in efficient radio gossiping. We discuss deterministic as well as randomized methods of communication in the context of a variety of models taking into account knowledge in relation to the network size and topology, orientation of connections and the upper bound on the size of messages. Using this opportunity we also shed more light on several combinatorial structures and algorithmic solutions that emerged during studies on efficient radio broadcasting and gossiping.