Energy-efficient randomized routing in radio networks

ABSTRACT

The main contribution of this work is to present an energy-efficient routing protocol for single-channel, single-hop radio networks (RN, for short). Such networks are usually deployed in support of special events including search-and-rescue, disaster relief, law enforcement, and collaborative computing, among many others. An RN is typically populated by hand-held, commodity devices, running on batteries. Since recharging batteries may not be possible while on mission, we are interested in designing protocols that are highly energy-efficient. One of the most effective energy-saving strategies is to mandate individual stations to go to sleep whenever they are not transmitting or recieving messages. Consequently, we are interested in protocols that allow stations to power off their transceiver to the largest extent possible.Suppose that station S(i), (1 ≤ i ≤ p), of the RN stores si items. Each item has a unique destination which is the identity of the station to which the item must be routed. The routing problem asks to route all the items to their destinations, while expending as little energy as possible. Since, in the worst case, each item must be transmitted at least once, every routing protocol must take at least n = s1 + s2 ··· sp time slots to terminate. Similarly, each station S(i), (1 ≤ i ≤ p), must be awake for at least si + di time slots, where di denotes the number of items destined for S(i). It is well known that a station is expending power while its transceiver is active that is, while transmitting or receiving a packet. It is perhaps surprising at first that a station expends power even if it receives a packet that is not destined for it. Since in single-hop radio networks every station is within transmission range from every other station, the design of energy-efficient protocols is highly nontrivial! An additional complication stems from the inherent asymmetry of the routing problem: no destination knows the identity of the sender, precluding à priori arrangements between senders and receivers.We show that for every ƒ ≥ 1, the task of routing n items can be completed, with probability exceeding 1 - 1/ƒ, in n + O(q + ln ƒ) time slots and that no station S(i), (1 ≤ i ≤ p), has to be awake for more than si + di + O(qi + ri log p + log ƒ) time slots, where qi is the number of stations that have items destined for S(i), q = q1 + q2 + ··· + qp, and ri is the number of stations for which S(i) has items. Since qi ≤ di, ri ≤ si, and q ≤ n our protocol is close to optimal.

REFERENCES

• 1: Norman Abramson, Multiple Access Communications: Foundations for Emerging Technologies, IEEE Press, Piscataway, NJ, 1995
• 2: Anindo Bagchi , S. Louis Hakimi, Data Transfers in Broadcast Networks, IEEE Transactions on Computers, v.41 n.7, p.842-847, July 1992 [doi>10.1109/12.256452 ]
• 3: D. J. Baker, Data{voice communication over a multihop, mobile, high frequency network, Proc. MILCOM'97, Monterey, CA, 1997, 339-343.
• 4: John M. Rulnick , Nicholas Bambos, Mobile power management for wireless communication networks, Wireless Networks, v.3 n.1, p.3-14, March 1997 [doi>10.1023/A:1019168125436 ]
• 5: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection, Distributed Computing, v.5 n.2, p.67-71, September 1991 [doi>10.1007/BF02259748]
• 6: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 7: Uyless Black, Mobile and wireless networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 8: Jacir L. Bordim , JiangTao Cui , Tatsuya Hayashi , Koji Nakano , Stephan Olariu, Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks, Proceedings of the 10th International Symposium on Algorithms and Computation, p.215-224, December 16-18, 1999
• 9: P. H. Dana, The geographer's craft project, Dept. of Geography, UT Austin, Sept. 1999, http://www.utexas.edu/depts/grg/gcraf/notes/gps/gps.htm:
• 10: W. C. Filer and F. J. Bruno, Low cost packet radio, Proceedings of the IEEE, 75, (1987), 33-42.
• 11: M. Fine and F. A Tobagi, Demand assignment multiple access schemes in broadcast bus local area networks, IEEE Transactions on Computers, C-33, (1984), 1130-1159.
• 12: W. R. Franta and M. B. Bilodeau, Analysis of prioritized CSMA protocol based on staggered delays, Acta Informatica, 13, (1980), 299-324.
• 13: W. R. Franta and J. R. Heath, Measurement and analysis of HYPERchannel networks, IEEE Transactions on Computers, C-33, (1984), 1124-1130.
• 14: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 15: J. C. Haartsen, The Bluetooth radio system, IEEE Personal Communications, 7, (2000), 28-36.
• 16: E. P. Harris and K. W. Warren, Low power technologies: a system perspective, Proc. Third International Workshop on Mobile Multimedia Communications, Princeton, N J, September 1996.
• 17: A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen, Scalable routing strategies for ad-hoc networks, IEEE Journal on Selected Areas in Communications, 17, (1999), ~369-1379.
• 18: E. D. Kaplan, Understanding GPS: principles and applications, Artech House, Boston, 1996.
• 19: C. R. Lin and M. Gerla, Adaptive clustering for mobile wireless networks, IEEE Transaction on Special Areas of Communications, (1999), 1265-1275.
• 20: W. Mangione-Smith and P. S. Ghang, A low power medium access control protocol for portable multimedia devices, Proc. Third International Workshop on Mobile Multimedia Communications, Princeton, NJ, September 1996.
• 21: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 22: K. Nakano, Optimal sorting algorithms on bus-connected processor arrays, IEICE Transactions Fundamentals, E-76A, 11, (1994), 2008-2015.
• 23: Koji Nakano , Stephan Olariu, Randomized Initialization Protocols for Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.749-759, July 2000 [doi>10.1109/71.877833 ]
• 24: K. Nakano and S. Olariu, Randomized log log n-round leader election protocols in radio networks, Proc. SIROCCO'2000, June 2000, to appear.
• 25: Koji Nakano , Stephan Olariu , James L. Schwing, Broadcast-Efficient Protocols for Mobile Radio Networks, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1276-1289, December 1999 [doi>10.1109/71.819949 ]
• 26: M. Joa-Ng and I.-T. Lu, A peer-to-peer zone-based two-level link state routing for mobil e ad-hoc networks, IEEE Journal of Selected Areas in Communications, 17, (1999), 1415-1425.
• 27: B. Parkinson and S. Gilbert, NAVSTAR: global positioning system- ten years later, Proceedings of the IEEE, 1983, 1177-1186.
• 28: R. A. Powers, Batteries for low-power electronics, Proceedings of the IEEE, 83, (1995), 687-693.
• 29: A. K. Salkintzis and C. Chamzas, An in-band power-saving protocol for mobile data networks, IEEE Transactions on Communications, COM-46, (1998), 1194-1205.
• 30: R. Sanchez, J. Evans, and G. Minden, Networking on the battlefield: challenges in highly dynamic multihop wireless networks, Proc. of IEEE MILCOM'99, Atlantic City, NJ, October 1999.
• 31: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]
• 32: K. Sivalingam, M. B. Srivastava, and P. Agrawal, Low power link and access protocols for wireless multimedia networks, Proc. IEEE Vehicular Technology Conference VTC'97, Phoenix, AZ, May, 1997.
• 33: M. Stemm, P. Gauthier, and D. Harada, Reducing power consumption on network interfaces in hand-held devices, Proc. 3-rd International Workshop on Multimedia Communications, Princeton, 1996.
• 34: F. Tobagi and V. B. Hunt, Performance evaluation of carrier sense multiple access with collision detection, Computer Networks, 4, (1980), 435-467.
• 35: J. E. Wieselthier, G. D. Nguyen, and A. Ephemerides, Multicasting in energy-limited ad-hoc wireless networks, Proc. MILCOM'98, 1998.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

  G. Mathematics of Computing

General Terms:
Design, Measurement, Performance, Standardization, Theory