Deterministic Leader Election in Multi-hop Beeping Networks - (Extended Abstract)
Deterministic Leader Election in Multi-hop Beeping Networks - (Extended Abstract)
复制标题
多跳蜂鸣网络中的确定性领导者选举 -（扩展摘要）
DOI：
10.1007/978-3-662-45174-8_15
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Roger Wattenhofer
中科院分区：
文献类型：
--
作者：
Klaus;J. Seidel;Roger Wattenhofer
研究了蜂鸣声模型下多跳无线网络的确定性leader选举问题。更具体地说，我们解决了显式领导者选举：一个节点被选为领导者，其他节点知道它的标识符，算法在网络处于静止状态时终止。假设没有网络的初始知识，即节点既不知道网络的大小也不知道它们的程度，它们只有一个唯一的标识符。我们的主要贡献是在运行时间为O（D logn）轮的同步蜂鸣声模型中提供了一种确定性的显式领导者选举算法。这是通过将快速局部选举算法与无线网络中同步和通信的两种新技术相结合来实现的。
We study deterministic leader election in multi-hop radio networks in the beeping model. More specifically, we address explicit leader election: One node is elected as the leader, the other nodes know its identifier, and the algorithm terminates at some point with the network being quiescent. No initial knowledge of the network is assumed, i.e., nodes know neither the size of the network nor their degree, they only have a unique identifier. Our main contribution is a deterministic explicit leader election algorithm in the synchronous beeping model with a run time of O(D logn) rounds. This is achieved by carefully combining a fast local election algorithm with two new techniques for synchronization and communication in radio networks.