Toward the end of 2002 and the beginning of 2003, while working with Professor Horowitz on a legal case between the Recording Industry Association of America (RIAA) and the Motion Picture Associate of America (MPAA) vs. Grokster, I became interested in the various peer-to-peer technologies in existence. The Gnutella protocol presents an open implementation of a peer-to-peer protocol that allows for easy discovery of information on the network. Many papers have been published on peer-to-peer technology, but no papers as of May 2003 had been published on exactly the types of data searched for and shared on a peer-to-peer network. I wrote a paper characterizing the different files searched for and shared on the Gnutella network and published it as a technical paper at the IEEE Consumer Communications and Networking Conference in Las Vegas, Nevada, USA in January 2004.
For a few months thereafter, I began researching software engineering concepts, specifically in code re-engineering. Many companies are forced to produce code very rapidly during the "startup years", and as such, much of the code lacks architectural design and coding standards. I was working for SBC's SmartPages.com, which is now AT&T's YellowPages.com, at the time, where I created coding standards and many process-oriented documents to improve the software engineering process and reduce the number of bugs in the project. During my time at SmartPages.com, the number of bugs were reduced by 15% based on the changes in the software engineering process and the coding standards. In many companies, it eventually becomes necessary to go back through the code and redesign or re-code much of the functionality. New features are not being added, but the code is becoming much more extensible and easier to modify when new requirements come available. There is currently no scientific way to re-engineer code, though this is a much needed process to standardize. I looked into trying to determine if it is possible to standardize code re-engineering or if code re-engineering is specific to the application.
As I was pursuing code re-engineering, I became much more interested in the functionality behind the code rather than the code at a structural point-of-view. Then, while sitting in traffic one day in early 2004 for over an hour on my 23-mile commute to work on the 101 freeway in Los Angeles, I started thinking that there has to be a way to leverage technology to improve traffic flow on freeways. I started looking into what research had been done concerning the transportation community in relation to technology. I found that there was definitely a community that was dedicated to improving transportation through the use of technology, and I realized that I had found my passion. At a few companies and on my own, I had gained some invaluable experience working with mobile devices. The idea of having mobile devices in vehicles communicating with some hardware on the roadway seemed quite logical and feasible. As the brainstorming continued, I eventually reached my dissertation topic - "Algorithms and Data Structure for the Real-Time Processing of Traffic Data".
Currently, the majority of traffic data that is gathered is done through the use of loop detectors and video cameras that are owned by departments of transportation. There are two ways that can be used for vehicles to report their speed and location - Vehicle-to-Infrastructure (V2I) or Vehicle-to-Vehicle (V2V) communication. In either case, a plethora of applications becomes available with this enormous amount of data, including incident identification, incident probability prediction, automated vehicle optimization, macroscopic traffic flow optimization, the ability to accurately determine optimal routes from a vehicle's current location to its desired destination, among others. Representing a transportation system as a graph where the weights of the edges are the amount of time to traverse that edge, different graph algorithms can be used to determine fastest (or shortest) paths. Since the weights of the edges will change almost constantly, static shortest path algorithms, such as Dijkstra's, Bellman-Ford's, Floyd-Warshall's, or Johnson's, are not the most efficient. Professor Camil Demetrescu and Professor Giuseppe Italiano from the University of Rome "La Sapienza" have created dynamic graph algorithms that can compute shortest paths more efficiently with changing edge weights. I extended that work to a transportation network which does not have to worry about edges being added or removed very frequently. The class of algorithms I created are known as the Dynamic All-Pairs All-Paths algorithms, which pre-compute all of the paths between all nodes in the network, then can compute shortest paths much quicker. I published this work as a technical paper at the IEEE 9th Intelligent Tranportation Systems Conference in Toronto, Ontario, Canada in September 2006.
The Dynamic All-Pairs All-Paths algorithms, and Dijkstra's, Bellman-Ford's, and Johnson's algorithms, are available publicly through FreeSim (http://www.freewaysimulator.com), which is a free real-time traffic simulator I created as part of my Ph.D. dissertation. Freesim is an open-source project released under the GNU General Public License. I published a technical paper on FreeSim and the V2V and V2I architectures built into the framework at the IEEE 3rd International Workshop on Vehicle-to-Vehicle Communications, which was in conjunction with the IEEE 3rd International Intelligent Vehicles Symposium in Istanbul, Turkey in June 2007. I also published a technical paper on the general architecture of FreeSim at the IEEE 10th Intelligent Transportation Systems Conference in Seattle, Washington, USA in October 2007.
My current focus is concerned with creating a hybrid Vehicle-to-Vehicle-to-Infrastructure (V2V2I) architecture to leverage the benefits of both the pure V2V and pure V2I architectures. The V2V architecture provides robustness against node failures, but the V2I architecture allows for a 100% accurate representation of the network at all times. Both architectures can produce fastest paths for vehicles, though the V2I architecture can do it with lower bandwidth consumption. Creating an architecture that allows vehicles to communicate with each other, in addition to some special vehicles (known as Super-Vehicles) to also communicate with a central server will provide the benefits of both architectures. The notion of a Super-Vehicle is similar to a Super-Node in the Kazaa peer-to-peer architecture, which is responsible for responding to queries for all of the computers for which it is responsible. The algorithm behind the Super-Vehicle and determining how to choose a Super-Vehicle are open questions for my research still.
I also have a grant submitted in collaboration with Professor Osama Abaza at the University of Alaska,Anchorage to practically test the V2I communication in Anchorage. With all of the theory, I would like to provide a testbed for researchers and engineers to test their applications on live data. All of the data that is currently being used is gathered via loop detectors from departments of transportation and then modified to appear as if the data is gathered continuously. The data that we gather will be fed directly into FreeSim.
If you have any questions about my research or would like more information, please do not hesitate to contact me at
