For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Randomized Time- and Energy-Optimal Routing in Single-Hop, Single-Channel Radio Networks
Jacir L. BORDIM Jiangtao CUI Koji NAKANO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
radio networks, routing protocols, energy-efficient, randomized algorithms,
Full Text: PDF>>
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), (1ip), initially stores si 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 = s1 + s2 + + sp time slots to route each item to its final destination. Similarly, each station S(i), (1ip), must be awake for at least si + di time slots to broadcast si items and to receive di items, where di 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 qi, (1ip), be the number of stations that have items destined for S(i), q=q1 +q2 ++ qp, and ri be the number of stations for which S(i) has items. When qi is known to station S(i), our routing protocol runs, with probability exceeding 1 - , (f > 1), in n + O(q + log f) time slots with each station S(i) being awake for at most si + di + O(qi + ri + log f) time slots. Since qidi, risi, and qn always hold, our randomized routing protocol is optimal. We also show that, when the value of di is known to S(i), our routing protocol runs, with probability exceeding 1 - , (f > 1), in O(n + log f) time slots with no station being awake for more than O(si + di + log f) time slots.