此篇論文中，我們針對單一跳躍無線網路中的初始化問題進行研究。初始化問題的目的就是要將號碼1到n分配給網路中的每ㄧ個站台，號碼不可重複。論文中，我們整理比較目前已知的初始化協定(分為已知站台數和未知站台數兩類)，並模擬分析相關效率。同時，在站台數未知的情形下，我們提出一改良式的混合協定，透過適當地估計站台數，能夠快速完成初始化。根據模擬結果，當站台數超過50，改良後的初始化協定將比目前常見的協定更為快速有效。

Given a group of n stations, the initialization problem is to assign each station a distinct ID number, from 1 to n. In this paper, we study the initialization problem in signle-hop wireless networks. We review several protocols which consist of that n is known and unknown to all stations. Meanwhile, we propose an improved protocol for the case of that the number of stations is unknown. According to our experiment results, the improved protocol is very efficient when the number of stations is greater than 50.

[1] M. A. Bonuccelli , F. Lonetti and F. Martelli, Tree Slotted Aloha: a New Protocol for Tag Identification in RFID Networks, Proceedings of the 2006 International Symposium on a World of Wireless, Mobile and Multimedia.
[2] J.L. Bordim, J. Cui, T. Hayashi, K. Nakano, S. Olariu, Energy-efficient initialization protocols for ad hoc radio networks, IEEE Transactions Parallel and Distributed Systems, 11, 8, August 2000, 851-863
[3] J.L. Bordim, J. Cui, N. Ishii, K. Nakano, Doubly-logarithmic energy-efficient initialization protocols for single-hop radio networks, Proceedings International Parallel and Distributed Processing Symposium, 2002
[4] Z. Cai, M. Lu, and X. Wang , Distributed Initialization Algorithms for Single-Hop Ad Hoc Networks with Minislotted Carrier Sensing, IEEE Transactions on Parallel and Distributed Systems, VOL. 14, NO. 5, MAY 2003.
[5] J. I. Capetanakis, Tree Algorithms for Packet Broadcast Channels, IEEE Transactions on Information Theory, VOL. IT-25, NO. 5, SEPTEMBER 1979
[6] H-S Choi, J-R Cha, J-H Kim , Fast Wireless Anti-collision Algorithm in Ubiquitous ID System, Vehicular Technology Conference, 2004
[7] D. R. Hush and C. Wood, Analysis of tree algorithms for RFID arbitration, Proc. IEEE Intern. Symposium on Information Theory, Boston, USA, August 1998.
[8] C-S Hsu and J-P Sheu, Design and performance analysis of leader election and initialization protocols on ad hoc networks , Wirel. Commun. Mob. Comput. 2003;
[9] N. Inaba, K. wada, Efficient Initialization Algorithms on Single-Hop Radio Networks, IEICE Transactions on Information and Systems, 2007.
[10] J. L. Massey, Collision-Resolution Algorithms and Random-Access Communications, In G. Longo, editor, Multi-User Communication Systems, number 265 in CISM Courses and Lectures, pages 73–137. Springer- Verlag, 1981.
[11] A. Micic and I. Stojmenovic, A hybrid randomized initialization protocol for TDMA in single-hop wireless networks, Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS.02).
[12] A. Micic, A. Nayak, D. Simplot-Ryl, and I. Stojmenovic, A hybrid randomized protocol for RFID tag identification, Proc. of WoNGeN’05.
[13] K. Nakano, S. Olariu, and A. Y. Zomaya, Energy-Efficient Permutation Routing in Radio Networks, IEEE Transactions on Parallel and Distributed Systems, VOL. 12, NO. 6, JUNE 2001.
[14] K. Nakano, S. Olariu, A Survey on Leader Election Protocols for Radio Networks, Parallel Architectures, Algorithms and Networks, 2002
[15] K. Nakano and S. Olariu, Randomized Initialization Protocols for Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, VOL. 11, NO. 7, JULY 2000.
[16] K. Nakano and S. Olariu, Uniform Leader Election Protocols for Radio Networks, IEEE Transactions on Parallel and Distributed Systems, VOL. 13, NO. 5, MAY 2002.
[17] S. Olariu. I. Stojmenovic and A. Zomaya, On the dynamic initialization of parallel computers, Journal of Supercomputing, 15, 5-24, 1999
[18] V. Ravelomanana, Optimal Initialization and Gossiping Algorithms for Random Radio Networks, IEEE Transactions on Parallel and Distributed Systems, VOL. 18, NO. 1, JANUARY 2007.
[19] N. S. Shankar, A New Contention Resolution Procedure For HFC Access Networks And Its Performance Evaluation, Journal of Scheduling 7: 149–167, 2004.
[20] J-P Sheu , C-H Liu, S-L Wu and Y-C Tseng, A Priority MAC Protocol to Support Real-Time Traffic in Ad Hoc Networks, 2003 Kluwer Academic Publishers.
[21] S-H Shiau and C-B Yang, A Fast Initialization Algorithm for Single Hop Wireless Networks, IEICE Transactions on Commuication, VOL.E88-B, NO.11 NOVEMBER 2005.