Randomized Time- and Energy-Optimal Routing Single-Hop, Single-Channel Radio Networks

スポンサーリンク

概要

• 論文の詳細を見る

• A Radio Network (RN, for short) is a distributed system with no central arbiter, consisting of p radio stations each of which is endowed with a radio transceiver. In this work we consider single-hop, single channel RNs, where each station S(i), (1 ≦ i ≦ p), initially stores s_i, items which are tagged with the unique destination they must be routed. Since each item must be transmitted at least once, every routing protocol must take at least n = s_1 + s_2 + ... + s_p time slots to route each item to its final destination. Similarly, each station S(i), (1 ≦ i ≦ p), must be awake for at least s_i + d_i time slots to broadcast s_i, items and to receive d_i items, where d_i denotes the number of items destined for S(i). The main contribution of this work is to present a randomized time- and energy-optimal routing protocol on the RN. Let q_i, (1 ≦ i ≦ p), be the number of stations that have items destined for S(i), q = q_11 + q_2 + ... + q_p, and r_i be the number of stations for which S(i) has items. When q_i is known to station S(i), our routing protocol runs, with probability exceeding 1 - 1/fnof, (fnof > 1), in n + O(q + log fnof) time slots with each station S(i) being awake for at most s_i + d_i + O(q_i + r_i + log fnof) time slots. Since q_i ≦ d_i, r_i ≦ s_i, and q ≦ n always hold, our randomized routing protocol is optimal. We also show that, when the value of d_i is known to S(i), our routing protocol runs, with probability exceeding 1 - 1/fnof, (fnof > 1), in O(n + log fnof) time slots with no station being awake for more than O(s_i +d_i +iog fnof) time slots.

• 社団法人電子情報通信学会の論文
• 2003-05-01

著者

• Cui Jiangtao

  Department Of Intelligence And Computer Engineering Nagoya Institute Of Technology

• Nakano Koji

  School Of Information Science Japan Advanced Institute Of Technology

• Nakano Koji

  School Of Engineering Hiroshima University

• BORDIM acir

  School of Information Science, Japan Advanced Institute of Technology

• Bordim Acir

  School Of Information Science Japan Advanced Institute Of Technology

関連論文

• An Energy-Efficient Initialization Protocol for Wireless Sensor Networks with No Collision Detection
• Energy-Efficient Initialization Protocols for Ad-Hoc Radio Networks
• An Energy Efficient Leader Election Protocol for Radio Network with a Single Transceiver(Discrete Mathematics and Its Applications)
• Accelerating the CKY Parsing Using FPGAs
• An Energy Efficient Ranking Protocol for Radio Networks(Discrete Mathematics and Its Applications)
• Special Section on Foundations of Computer Science
• Randomized Time- and Energy-Optimal Routing Single-Hop, Single-Channel Radio Networks
• Halftoning Through Optimization of Restored Images : A New Approach with Hardware Acceleration
• An Image Retrieval System Using FPGAs
• Hardware n Choose k Counters with Applications to the Partial Exhaustive Search(Programmable Logic, VLSI, CAD and Layout, Recent Advances in Circuits and Systems-Part 1)

スポンサーリンク