CPS: Small: The Roles of Communications in Lane Merging Systems
Lead PI:
Nicholas Maxemchuk
Vehicle automation has progressed from systems that monitor the operation of a vehicle, such as antilock brakes and cruise control, to systems that sense adjacent vehicles, such as emergency braking and intelligent cruise control. The next generation of systems will share sensor readings and collaborate to control braking operations by looking several cars ahead or by creating safe gaps for merging vehicles. Before we allow collaborative systems on public highways we must prove that they will do no harm, even when multiple rare events occur. The events will include loss of communications, failures or inaccuracies of sensors, mechanical failures in the automobile, aggressive drivers who are not participating in the system, and unusual obstacles or events on the roadways. The rules that control the interaction between vehicles is a protocol. There is a large body of work to verify the correctness of communications protocols and test that different implementations of the protocol will interact properly. However, it is difficult to apply these techniques to the protocols for collaborative driving systems because they are much more complex: 1) They interact with the physical world in more ways, through a network of sensors and the physical operation of the automobile as well as the communications channel; 2) They perform time critical operations that use multiple timers; And, 3) they may have more parties participating. In [1] we have verified that a three party protocol that assists a driver who wants to merge between two cars in an adjacent lane will not cause an accident for combinations of rare events. The verification uses a probabilistic sequence testing technique [2] that was developed for communications protocols. We were only able to use the communications technique after designing and specifying the collaborative driving protocol in a particular way. We have generalized the techniques used in the earlier work so that we can design collaborative driving protocols that can be verified. We have 1) a non-layered architecture, 2) a new class of protocols based upon time synchronized participants, and 3) a data management rule. 1) Communications protocols use a layered architecture. Protocol complexity is reduced by using the services provided by a lower layer. The layered architecture is not sufficient for collaborative driving protocols because they operate over multiple physical platforms. Instead, we define a smoke stack architecture that is interconnected. 2) The operation of protocols with multiple timers is more difficult to analyze because there are different sequences of operations depending on the relative times when the timers are initiated. Instead of using timers, we design protocols that use absolute time. This is reasonable because of the accurate time acquired from GPS and the accuracy of current clocks while GPS is not available. 3) Finally, in order for programs in different vehicles to make the same decisions they must use the same data. Our design merges the readings of sensors in different vehicles and uses a communications protocol that guarantees that all vehicles have the same sequence of messages and only use the messages that all vehicles have acquired. 1. Bohyun Kim, N. F. Maxemchuk, "A Safe Driver Assisted Merge Protocol," IEEE Systems Conference 2012, 19-22 Mar. 2012, Vancouver, BC, Canada, pp. 1-4. 2. N. F. Maxemchuk, K. K. Sabnani, "Probabilistic Verification of Communication Protocols," Distributed Computing Journal, Springer Verlag, no. 3, Sept. 1989, pp. 118-129.
Nicholas Maxemchuk

Nicholas F. Maxemchuk



·      Ph.D. Doctor of Philosophy, Systems Engineering, University of Pennsylvania, May 1975.

·      M.S. Moore School of Electrical Engineering, University of Pennsylvania, May 1970.

·      B.S. Bachelor of Electrical Engineering, The City College of New York, June 1968. (Graduated Magna Cum Laude).


Academic Experience

·      2001 - Present  Full Professor  Columbia University

·      2008 - Present  Chief Researsher        IMDEA Networks, Madrid

·      University of Melbourne, Visiting Academic Oct. 99.

·      Opponent: KTH Sweden, June 1997.

·      Department Visiting Committee, Comp. Sci., University of Texas at Austin 1989-92.


Non-Academic Experience

·      2009-2012    Consultant      NYC MTA

·      2008    Chief Scientist Telcordia

·      2007-2010       Consultant      Bell Labs, Murray Hill, NJ

·      Technical Advisory Board -  start-upEnrichnet 2000-2002

·      1996 - 2001     Technology Leader       AT&T Research Labs

·      Technical Advisory Board start-up - BrightLink Networks 1998->2001

·      1984 - 1996     Department Head AT&T Bell Laboratories

·      1976 - 1984     MTS     Bell Labs

·      1968 - 1976     MTS     RCA David Sarnoff Res. Cntr.


Current Membership in Professional Organizations

·      IEEE, Eta Kappa Nu and Tau Beta Pi


Honors and Awards

·      2006 IEEE Koji Kobayashi Award for Computer and Communications

·      1997 William R. Bennett Prize Paper Award for S. Low, N. F. Maxemchuk, S. Paul, "Anonymous Credit Cards and Its Collusion Analysis," IEEE Trans. on Networking, dec. 1996, vol. 4, no.6, pp 809-816

·      1996 R&D 100 Award for "Document Copying Deterrent System"

·      1989 Elected Fellow of the IEEE

·      1988 Leonard G. Abraham Prize Paper Award, for N. F. Maxemchuk, "Routing in the Manhattan Street Network," IEEE Trans. on Commun., May 1987, vol. COM-35, no. 5, pp. 503-512., also s elected for IEEE ComSoc 50th anniv. iss.

·      Selected for IEEE ComSoc 50th anniv. iss., and included in the DQDB standard, E. L. Hahne, A. K. Choudhury, N. F. Maxemchuk, "DQDB Networks With and Without Bandwidth Balancing," IEEE Trans. on Commun., Vol. 40, No. 7, July 1992, pp 1192-1204

Performance Period: 09/01/2010 - 08/31/2014
Institution: Columbia University
Sponsor: National Science Foundation
Award Number: 1035178