A mode-lock free decentralized timing synchronization algorithm for intervehicle ad-hoc networks

Hisa-Aki Tanaka, and Kenta Shinohara
Nonlinear Theory and Its Applications(NOLTA), IEICE, Apr. 2015


Timing synchronization, Wireless ad-hoc networks, Wireless sensor networks, Deadlock, Mode-lock state, TDMA


Timing synchronization is an important integrating component in wireless dis- tributed systems, such as mobile ad-hoc networks, M2M networks, and wireless sensor networks, and therefore, various timing synchronization algorithms have been proposed so far. Recently, Imai and Suzuki developed a new synchronization algorithm based on a time division multi- ple access (TDMA) protocol. Despite of its efficiency in synchronization for vehicle-to-vehicle communications, their algorithm sometimes suffers from a certain undesired synchronous pat- tern, i.e., a so called mode-lock state or a deadlock. Although their algorithm takes certain precautions to avoid this mode-lock state, in around more than 10% of instances this state is observed to persist and the desired perfect synchronization is not realized. Then, rst we investigate the mechanism of this persisting mode-lock state for their algorithm. With this insight to the mode-lock state, we propose a new mode-lock free (i.e., mode-lock eliminat- ing) distributed algorithm that always leads to a perfect synchronization. From systematic, comparative simulations, we observe that the proposed algorithm always eliminates mode-lock states, and eventually leads to the perfect synchronization. In addition, we observe the algo- rithm realizes even faster synchronization, compared with the algorithm by Imai and Suzuki, although these observed properties are not mathematically proved in this study.

Download PDF

Figures at a glance


  1. Ministry of land, infrastructure, transport, and tourism, “Advanced safety vehicle,” http://www.mlit.go.jp/jidosha/anzen/01asv/index.html.
  2. J. Imai and N. Suzuki, “Study on a self-adaptive timing synchronization : a method to avoid local optimizations,” IEICE Technical Report, vol. 107, no. 53, pp. 67-71, 2007.
  3. S. Makido, N. Suzuki, T. Harada, and J. Muramatsu, “Decentralized TDMA protocol for real-time vehicle-to-vehicle communications,” Transactions of Information Processing Society of Japan, vol. 48, no. 7, pp. 2257-2266, 2007.
  4. Y. Tadokoro, S. Makido, K. Ito, and N. Suzuki, “A proposal of transmission period control scheme for decentralized TDMA protocol in safety applications using inter-vehicle communica- tions,” IPSJ Journal, vol. 51, no. 3, pp. 945-950, 2010.
  5. S. Makido, H. Hayashi, J. Imai, T. Harada, K. Ito, Y. Tadokoro, H. Tanaka, N. Suzuki, and E. Teramoto, “Reliable MAC protocols for next generation V2V communications : eld operation test under simulated high traffic environment,” IEICE Technical Report, vol. 109, no. 440, pp. 89-94, 2010.
  6. H. Tanaka and A. Hasegawa, “Modelock avoiding synchronization method,” IET Electronics Letters, vol. 38, no. 4, pp. 186-187, 2002.
  7. K. Shinohara and H. Tanaka, “Mode-lock eliminating timing synchronization algorithm for intervehicle ad-hoc networks,” Proc. NOLTA'08, pp. 720-723, 2008.
  8. T. Kawazoe, M. Nishijima, K. Sorita, N. Tsuda, and H. Kaneko, “The technical trend of recent car navigation and GPS receiver,” JRC Review, no. 47, pp. 26-30, 2005.
  9. H. Kondo, “Time and timing generation using GPS receiver and its applications,” ISCIE Journal ‘Systems, Control and Information’, vol. 51, no. 6, pp. 273-278, 2007.
  10. Y. Akaiwa, H. Andoh, and T. Kohama, “Autonomous decentralized inter-base-station synchro- nization for TDMA microcellular systems,” Vehicular Technology Conference, 1991. Gateway to the Future Technology in Motion., 41st IEEE, pp. 257-262, 1991.
  11. E. Sourour and M. Nakagawa, “Mutual decentralized synchronization for intervehicle commu- nications,” IEEE Trans. on Vehicular Technology, vol. 48, no. 6, pp. 2015-2027, 1999.
  12. H. Tanaka, K. Shimizu, O. Masugata, and T. Endo, “Flexible phase synchronization control method using partially unlocking oscillator arrays,” IET Electronics Letters, vol. 43, no. 12, pp. 672-674, 2007.
  13. V. Gutnik and A. P. Chandrakasan, “Active GHz clock network using distributed PLLs,” IEEE J. Solid-State Circuits, vol. 35, no. 11, pp. 1553-1560, 2000.
  14. N. Bursac, F. Aguel, and L. Tung, “Multiarm spirals in a two-dimensional cardiac substrate," Proc. National Academy of Science, vol. 101, no. 43, pp. 15530-15534, 2004.
  15. EPSON, “SG-210S*BA (crystal oscillator output : CMOS)  for automotive,” http://www5.epsondevice.com/en/quartz/product/osc/spxo/sg210sxba.html