Energy-efficient initialization protocols for ad-hoc radio networks

作     者：Bordim, JL Cui, JT Hayashi, T Nakano, K Olariu, S 

作者机构：Nagoya Inst Technol Dept Elect & Comp Engn Nagoya Aichi 4668555 Japan Old Dominion Univ Dept Comp Sci Norfolk VA 23529 USA 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (IEICE Trans Fund Electron Commun Comput Sci)

年 卷 期：2000年第E83A卷第9期

页      面：1796-1803页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：radio networks initialization protocols energy-efficient randomized algorithms 

摘      要：The main contribution of this work is to propose energy-efficient randomized initialization protocols for ad-hoc radio networks (ARN for short). First, we show that if the number n of stations is known beforehand, the single-channel ARN can be initialized by a protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log n) time slots. We then go on to address the case where the number n of stations in the ARN is not known beforehand;We begin by discussing, an elegant protocol that provides a tight approximation of n. Interestingly, this protocol terminates, with high probability, in O((log n)(2)) time slots and no station has to be awake for more than O(log n) time slots. We use this protocol to design an energy-efficient initialization protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log n) time slots. Finally, we design an energy-efficient initialization protocol for the k-channel ARN that terminates, with high probability, in O(n/k + log n) time slots, with no station being awake for more than O(log n) time slots.