An Energy Efficient Ranking Protocol for Radio Networks

• NAKANO Koji

  School of Engineering, Hiroshima University

抄録

A radio network (RN for short) is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations run on batteries and expends power while broadcasting/receiving a data packet. Thus, the most important measure to evaluate protocols on the radio network is the number of awake time slots, in which a station is broadcasting/receiving a data packet. We also assume that the stations are identical and have no unique ID number, and no station knows the number n of the stations. For given n keys one for each station, the ranking problem asks each station to determine the number of keys in the RN smaller than its own key. The main contribution of this paper is to present an optimal randomized ranking protocol on the k-channel RN. Our protocol solves the ranking problem, with high probability, in O(n/k+log n) time slots with every station being awake for at most O(log n) time slots. We also prove that any randomized ranking protocol is required to run in expected Ω(n/k+log n) time slots with at least one station being awake for expected Ω(log n) time slots. Therefore, our ranking protocol is optimal.

収録刊行物

• IEICE transactions on fundamentals of electronics, communications and computer sciences

  IEICE transactions on fundamentals of electronics, communications and computer sciences 89 (5), 1346-1354, 2006-05-01

  一般社団法人電子情報通信学会

キーワード

• power-aware computing
• adhoc networks
• sorting
• distributed algorithms
• randomized algorithms

詳細情報

• CRID: 1571698602535216256
• NII論文ID: 110007502849
• NII書誌ID: AA10826239
• ISSN: 09168508
• 本文言語コード: en
• データソース種別:
  • CiNii Articles