Uniform Leader Election Protocols in Radio Networks
Uniform Leader Election Protocols in Radio Networks
复制标题
DOI：
10.1109/icpp.2001.952068
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
K. Nakano;S. Olariu
中科院分区：
文献类型：
--
作者：
K. Nakano;S. Olariu
无线电网络是没有中央仲裁器的分布式系统，由n个无线电收发器组成，此后称为站。我们假设这些站点是相同的，无法通过序列号或制造编号进行区分。领导者选举问题要求指定一个站作为领导者。在这项工作中，我们专注于单信道，单跳无线电网络。我们假设时间是分时隙的，并且所有传输都发生在时隙边界。在每个时隙中，站以某种概率在信道上发送，直到最终其中一个站被宣布为领导者。如果在每个时隙中，每个站以相同的概率发送，则称领导者选举协议是均匀的。在一篇开创性的论文中，Willard（1986）提出了一种用于单信道单跳无线电台的统一领导者选举协议，该协议终止于log log n+o（log log n）期望时隙。15年来，威拉德的协议是否具有“高概率”的相同时间性能一直悬而未决。“我们的主要贡献之一是表明，不幸的是，情况并非如此。具体地说，我们证明了对于每一个参数f/spl在/e/sup O（n）/，为了保证终止概率超过1-1/f，Willard协议必须占用log log n+/spl Ω/（/spl radic/f）个时隙.这项工作的亮点是一个新的统一的领导选举协议，终止的概率超过1-1/f，在log log n+o（log log n）+O（log f）时隙。最后，我们提供的模拟结果表明，我们的领导选举协议优于威拉德的协议在实践中。
A radio network is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations are identical and cannot be distinguished by serial or manufacturing number. The leader election problem asks to designate one of the stations as leader. In this work, we focus on single-channel, single-hop radio networks. We assume that time is slotted and all transmissions occur at slot boundaries. In each time slot, the stations transmit on the channel with some probability until, eventually, one of the stations is declared leader. A leader election protocol is said to be uniform if, in each time slot, every station transmits with the same probability. In a seminal paper, Willard (1986) presented a uniform leader election protocol for single-channel single-hop radio stations terminating in log log n+o(log log n) expected time slots. It was open for more than 15 years whether Willard's protocol featured the same time performance with "high probability." One of our main contributions is to show that, unfortunately, this is not the case. Specifically, we prove that for every parameter f/spl isin/e/sup O(n)/, in order to ensure termination with probability exceeding 1-1/f, Willard's protocol must take log log n+/spl Omega/(/spl radic/f) time slots. The highlight of this work is a novel uniform leader election protocol that terminates, with probability exceeding 1-1/f, in log log n+o(log log n)+O(log f) time slots. Finally, we provide simulation results that show that our leader election protocol outperforms Willard's protocol in practice.