IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 2006 E89-A(5):1355-1361; doi:10.1093/ietfec/e89-a.5.1355

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by BORDIM, J. L. Articles by NAKANO, K. Search for Related Content Social Bookmarking          What's this?

Copyright © 2006 The Institute of Electronics, Information and Communication Engineers

Special Section on Discrete Mathematics and Its Applications -- Papers

An Energy Efficient Leader Election Protocol for Radio Network with a Single Transceiver

Jacir Luiz BORDIM¹, Yasuaki ITO² and Koji NAKANO²

¹ The author is with the Department of Computer Science, University of Brasilia, 70910-900 Brasilia - DF, Brazil., ² The authors are with the School of Engineering, Hiroshima University, Higashihiroshima-shi, 739-8527 Japan. E-mail: nakano{at}hiroshima-u.ac.jp

In this work we present an energy efficient leader election protocol for anonymous radio network populated with n mobile stations. Previously, Nakano and Olariu have presented a leader election protocol that terminates, with probability exceeding 1 – 1/f (f 1), in log logn + o(log log n)+ O(log f) time slots [14]. As the above protocol works under the assumption that every station has the ability to transmit and monitor the channel at the same time, it requires every station to be equipped with two transceivers. This assumption, however, is unrealistic for most mobile stations due to constraints in cost, size, and energy dissipation. Our main contribution is to show that it is possible to elect a leader in an anonymous radio network where each station is equipped with a single transceiver. Quite surprisingly, although every station has only one transceiver, our leader election protocol still runs, with probability exceeding 1 – 1/f(f 1), in log log n + o(log logn)+ O(log f) time slots. Moreover, our leader election protocol needs only expected O(n) total awake time slots, while Nakano and Olariu's protocol needs expected O(nlog logn) total awake time slots. Since every leader election protocol needs at least (n) awake time slots, our leader election protocol is optimal in terms of the expected awake time slots.

Key Words: adhoc networks, collision detection, distributed algorithms, randomized algorithms

---

Manuscript received August 22, 2005. Manuscript revised November 6, 2005. Final manuscript received December 15, 2005.

References

[1] H. Abu-Amara, "Fault-tolerant distributed algorithms for election in complete networks," IEEE Trans. Comput., vol.37, no.4, pp.449–453, 1988.

[2] Y. Afek and E. Gafni, "Time and message bounds for election in synchronous and asynchronous complete networks," SIAM J. Comput., vol.20, pp.376–394, 1991.

[3] R. Bar-Yehuda, O. Goldreich, and A. Itai, "Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection," Distrib. Comput., vol.5, pp.67–71, 1991.

[4] J. Bentley and A. Yao, "An almost optimal algorithm for unbounded search," Inf. Process. Lett., vol.5, pp.82–87, 1976.

[5] D. Bertzekas and R. Gallager, Data Networks, Second Edition, Prentice-Hall, 1992.

[6] E.D. Kaplan, Understanding GPS: Principles and applications, Artech House, Boston, 1996.

[7] E. Korach, S. Moran, and S. Zaks, "Optimal lower bounds for some distributed algorithms for a complete network of processors," Theor. Comput. Sci., vol.64, pp.125–132, 1989.

[8] M. Kutylowski and W. Rutkowski, "Adversary immune leader election in ad hoc radio networks," Proc. European Symposium on Algorithms, pp.397–408, 2003.

[9] M.C. Loui, T.A. Matsushita, and D.B. West, "Election in complete networks with a sense of direction," Inf. Process. Lett., vol.22, pp.185–187, 1986.

[10] R.M. Metcalfe and D.R. Boggs, "Ethernet: Distributed packet switching for local computer networks," Commun. ACM, vol.19, pp.395–404, 1976.

[11] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

[12] K. Nakano and S. Olariu, "Randomized O(log log n)-round leader election protocols in radio networks," Proc. International Symposium on Algorithms and Computation, LNCS 1533, pp.209–218, 1998.

[13] K. Nakano and S. Olariu, "Randomized leader election protocols in radio networks with no collision detection," Proc. International Symposium on Algorithms and Computation, pp,362–373, 2000.

[14] K. Nakano and S. Olariu, "Uniform leader election protocols for radio networks," IEEE Trans. Parallel Distrib. Syst., vol.13, no.5, pp.516–526, 2002.

[15] M. Joa-Ng and I.-T. Lu, "A peer-to-peer zone-based two-level link state routing for mobile ad-hoc networks," IEEE J. Sel. Areas Commun., vol.17, pp.1415–1425, 1999.

[16] B. Parkinson and S. Gilbert, "NAVSTAR: Global positioning system—Ten years later," Proc. IEEE, 1983, pp.1177–1186, 1983.

[17] G. Singh, "Leader election in complete networks," Proc. ACM Symposium on Principles of Distributed Computing, 1992, pp.179–190, 1992.

[18] D.E. Willard, "Log-logarithmic selection resolution protocols in a multiple access channel," SIAM J. Comput., vol.15, pp.468–477, 1986.

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by BORDIM, J. L. Articles by NAKANO, K. Search for Related Content Social Bookmarking          What's this?