Wireless Systems Design

Mesh Networking Smooths Traffic Flow

From off-the-shelf components, it’s possible to build a DGPS/wireless-mesh system that reduces accidents and congestion.

Two major problems afflict automobile-based transportation systems in the U.S. and around the world: traffic accidents and congestion. About half a million people are killed each year in traffic accidents worldwide. While Americans make up only 3% of the world's population, they account for almost 9% of those traffic fatalities. In 2003, more than 42,000 Americans died in traffic-related accidents. Similarly, 42,000 or more died the year before that.1 In fact, the total number of traffic deaths in the U.S. hasn't changed significantly in 10 years.2 For every fatality, there are approximately 40 injuries that flood hospitals and drive up medical costs. Traffic accidents cost the American economy more than $230.6 billion.

The resulting legal costs and insurance rates escalate faster than the rate of inflation. Recently, a beer company was sued for a traffic accident caused by a drunk driver. Because the beer company had made drinking so attractive, the suit contended, it made the individual lose control of his common sense. It's not a stretch to think that automobile firms could be sued for building vehicles that are capable of excessive speeds and producing advertisements that make reckless driving attractive to inexperienced automobile operators.

The second major automobile-transportation problem is that urban and suburban roads are becoming clogged with vehicles. From 1950 to 1986, the U.S. population increased by 60%. Yet the number of automobiles grew by 257%. During this same time period, new road and highway construction declined. Even if funding was obtained to help alleviate the current congestion, major highway improvements can take 10 to 15 years to complete. The mismatch in demand and resources has significantly increased commuter delays.

For an example, look at the Hollywood Freeway. It was built in 1965 to handle 120,000 cars a day. By 1970, almost twice that volume clogged the road. Rush-hour traffic in Los Angeles crawls along at 35 mph. If no improvements are made, traffic will slow to 11 mph by 2010. According to a Federal Highway Administration study, recurring congestion along urban freeways during 1987 caused 700 million vehicle hours of delay. Non-recurring congestion resulted in over 1.2 million vehicle hours of delay. The costs of national traffic congestion—including lost productivity and accidents—are estimated at $100 billion annually.

Current safety features, such as airbags and reinforced frames, attempt to limit an accident's impact. But they don't prevent the accident from occurring. Many proposed accident-avoidance solutions involve expensive, complex technologies like vehicle-mounted radar or highly automated highway systems. A major concern with these systems is the complexity that's inherent in the designs. That complexity makes it likely that these solutions will only be used in the distant future—if ever.

A more practical solution could be found in a differential Global Positioning System (DGPS)/wireless-mesh system (FIG. 1). This solution uses an inexpensive networked system that is redundant and distributed. The system is therefore more reliable than alternate designs. It also uses off-the-shelf elements, which can be easily integrated into existing vehicles.

Metcalfe's Law drives the DGPS/wireless-mesh design. Bob Metcalfe, the inventor of Ethernet, hypothesized that the value of a network increases along with the number of nodes that are attached to it. Obviously, the value of the network also depends on the information that is passed among the nodes (i.e., the amount of intelligence provided by the node). Linking to a thousand nodes wouldn't be useful if the information dealt with car care and you were tasked with designing a jet engine. The DGPS/wireless-mesh system enhances the value of the network by providing information on the vehicle state (for example, location) to improve safety and traffic flow.

A number of wireless networks in development—all of various frequencies and bandwidths—could satisfy the communications needs of this system. The IEEE provides several Wi-Fi standards, which are generically lumped under 802.11x. Equipment that complies with those Wi-Fi standards is available from a number of sources. Yet research has shown that the performance of a wireless system varies under different vehicle speeds, traffic conditions, and driving areas.3

Mesh networks are an alternative to communication systems that have a commanding transmitter and numerous receivers. A mesh network has no central controlling element. All of the nodes in the mesh system can directly or indirectly communicate by relaying or "hopping" data through intermittent nodes (FIG. 2). This scheme provides a number of benefits over the networks that are based on one central transmitter.

The mesh networks have an important advantage over centralized networks, as the Federal Communications Commission (FCC) regulations limit the maximum transmission power of those networks. In a centralized network, each transmitting node emits with enough power to reach any other node in the network with one transmission. When two nodes transmit at the same time, channel contention limits capacity. It also causes problems in environments like urban areas, which have a great deal of high-bandwidth demands. Typical frequency, time, or coding schemes (or a combination of the three) are used to segment the channel into subchannels. N nodes can transmit without contention when the channel is divided into N subchannels. As a result, each subchannel has 1/Nth the capacity of the full channel.

In a mesh network, a node only needs to transmit with enough power to reach adjacent nodes. These nearby nodes will forward the data to more distant nodes. The process is continued until the data is received by the destination node.

In addition to providing spatial separation, the low-transmission power of a mesh network supports higher bandwidth than the centralized system. The signal-to-noise ratio (SNR) declines in a mesh network because the number of errors at the receiver increases as transmission distance increases (assuming a constant power level). To transmit over longer distances, wireless devices
use variable forward-error-correction encoding schemes or less complex modulation approaches. These schemes result in channel capacity that decreases as the transmission distance increases.

To avoid this problem, mesh networking transmits data over several short hops instead of one long hop. By using lower transmit power than centralized networks, the mesh-network nodes that are positioned at different geographic areas can transmit simultaneously without interfering with each other. The potential exists for more than N devices to simultaneously transmit within a mesh network without contention.

Among mesh networks' other advantages is the fact that they provide redundancy. They also are inherently self-balancing. The system leverages intelligence at the edge of the network, thereby enhancing reliability and performance. Each node includes communications equipment. It acts as a relay point to more distant nodes. When the network contains a large number of nodes within a limited geographical area, each mesh-network node has several neighbors that it can contact. It therefore creates multiple paths between two nodes. In the presence of localized interference, attenuation, or a failed node, a mesh network can route data around the problem site and—in effect—create a self-healing system. Mesh networks also avoid the bottlenecks that result from a centralized infrastructure and backhaul.

In areas where frequencies are limited, a multi-hop network provides significant benefits. Multi-hop networking increases the network's aggregate capacity by using limited transmit power—just enough to reach nearby neighboring nodes. This aspect allows channel re-use, thereby improving network capacity.

In addition, mesh networks can adapt to changes in network topology. Examples of such changes include the adding or removing of nodes or changing node location. Routes in mesh systems are self-forming. A mesh network can quickly converge on a route selection—a trait that's essential for high-speed vehicles. In fact, mesh systems are already being deployed in automotive applications. Moteran, a partnership between Mitsubishi and Deutsche Telekom, is an example. It is outfitting cars in some German cities with high-bandwidth mesh-networking equipment for entertainment and communications.

The second element of the proposed system is a DGPS.4 In the standard application utilizing the global navigation satellite systems (GNSSs), a receiver uses timing signals from at least four satellites to calculate the receiver's position. The fourth measurement is needed to bring the receiver clock into synchronization with the system. Each timing signal is erroneous due to atmospheric conditions and multipath reflections. The position calculation further compounds those errors.

If two receivers are located near each other, the atmosphere's effects on the satellite signals will almost be identical. As a result, the signals will incur almost the same timing errors. DGPS reduces these corresponding errors by adding a stationary or reference receiver to the system. In the proposed system, the reference receiver can be a traffic light. The roving Global Positioning System (GPS) receiver is integrated into a car or truck.

The stationary reference station is very accurately surveyed at its location. Although it receives the same GPS signals as the roving receiver, it attacks the equations backwards. Rather than using timing signals to calculate its position, the stationary receiver uses its known position to calculate timing errors. Based on its precisely known position, the reference receiver can calculate what the travel time of the GPS signals should be in ideal conditions. The difference between the received timing and the ideal timing is an error-correction factor. By using this factor, the roving receiver can reduce timing errors and position errors (TABLE 1).

Actually, two methods are combined to reduce errors in the GPS signals: code-phase and carrier-phase correction. With code-phase correction, the receiver determines the travel time of a satellite transmission. Essentially, it compares a pseudo-random code, which is generated within the receiver, with an identical code in the signal that was transmitted by the satellite (FIG. 3). Both codes are generated at the same time. But the code that was transmitted by the satellite has timing delays resulting from the error factors listed in Table 1. The receiver slides its code until it is synchronized with the satellite's code. The amount of mismatch between the codes can be converted into a position error (speed of light multiplied by the delta time).

Yet the bits (or cycles) of the pseudo-random code are very wide. As a result, there is still a margin for timing errors even if the two codes are judged to be in synchrony. The pseudo-random codes are transmitted at 1 MHz, which translates into a cycle width of almost 1 ms. At the speed of light, 1 ms causes an error of about 300 m. Good design reduces the error in the code matching to within 1% to 2% for a position error of 3 to 6 m.

To improve accuracy, the second error-reduction method—carrier-phase correction—uses the shorter wavelength of the carrier frequency (FIG. 4). The 1.57-GHz carrier signal has roughly a 20-cm wavelength. Measuring phase to 1% accuracy with code-phase receivers provides millimeter accuracy.

In essence, this approach counts the number of carrier cycles between the satellite and the reference receiver. Every cycle in the carrier looks like every other cycle, however. Counting is therefore difficult. On the other hand, the pseudo-random code is intentionally complex to make it easier to know which cycle is sampled. Carrier-phase DGPS is combined with code-phase techniques. Only a few cycles of the carrier are considered in determining which cycle marks the edge of the timing pulse.

The reference receiver then transmits error information to the roving receiver. The receiver can use that information to correct its measurements. The reference receiver has no way of knowing which available satellite a roving receiver might use to calculate its position (at least five are visible at every spot in the world). As a result, the reference receiver quickly runs through all of the visible satellites. It computes the errors associated with each satellite. Each roving receiver gets the complete list of errors and applies the corrections for the satellites that it uses. Error transmissions include the timing error for each satellite as well as that error's rate of change. The roving receiver can therefore interpolate its position between updates.

System operation is very simple. A GPS receiver and low-powered radio transmitter are installed in the traffic light. Its location is accurately surveyed. The position is then stored in the traffic light. The system's range is extended by other stationary access points (APs) or mobile nodes, which relay information to more distant vehicles.

A GPS receiver and low-powered radio also are installed in the vehicle. As the vehicle approaches the traffic light, it transmits the vehicle's ID, general location, and speed. The traffic light transmits GPS corrections. The vehicle's computer uses DGPS to ascertain its location to centimeter accuracy.

If there is no cross traffic, the light stays or turns green. If cross traffic is present, the light for the crossing traffic stays or turns green until the intersection is clear or a time limit is met. Traffic flow is thereby regulated according to traffic volume rather than preset conditions.

In addition, the vehicle's precise location is transmitted so that drivers of other vehicles are alerted to its status and progress. By providing additional warnings to drivers, the system prevents accidents. The message structure would be similar to that shown in TABLE 2. Carrier sense and random backoff are used to avoid conflict in the transmissions. It's assumed that missing one or two vehicles isn't critical to the system's performance.

British insurance companies offer their customers significant discounts if they control the speed of their vehicles as well as the manner in which they drive. In the British system, the information is recorded on the vehicles and then transmitted to an insurance-company facility, which analyzes the data. The driver qualifies for an insurance discount of 30% to 50% if he or she meets certain criteria (for example, no speeding and safe operation). American insurance companies could offer similar discounts to DGPS/wireless-mesh users. For the vehicle owner, savings of that magnitude would easily offset the added cost of the DGPS/wireless-mesh system.

The system provides a number of safety advantages:

  • Accident warning: MeshNetworks is working with U.S. car makers on an application that will alert a driver when a car ahead has deployed its airbags. The warning to the trailing driver will provide additional seconds to avert a crash.
  • Locations and velocities of other vehicles: The system can provide the location and velocity of similarly equipped vehicles in the vicinity. Automatic warnings of stalled or halted vehicles could be provided. In addition, the system could detect vehicles in blind spots and provide additional warnings to the operator.
  • Driver attention: A large percentage of accidents are caused when the driver is distracted and the vehicle wanders into another lane. The DGPS/wireless-mesh system can warn of a hazardous drift, thereby allowing the driver to take appropriate action.
  • Traffic-light warning: The system could warn the driver that the vehicle is about to enter an intersection in which the light has changed to red.
  • Speed control: Teenagers—particularly young males—tend to drive vehicles at excessive speeds. There is a strong disconnect between a young person's perception of his ability to handle a speeding vehicle and his capability to control it. In the DGPS/wireless-mesh system, the traffic light would transmit the appropriate speed limit for a section of road. A speed limiter on the young person's vehicle would restrain the speed to the assigned limit. This control also could be employed on the vehicles of chronic speeders.
  • Traffic-delay reductions: The resulting reduction in traffic delays would reduce the amount of fuel that is wasted as a vehicle idles at mistimed lights. It also would lower air pollution. In addition, commuters would experience fewer and shorter delays.

At the University of Duisburg-Essen, scientists developed such a traffic-simulation system. Their system is based on traffic data gathered in real time. As a result, this system can predict traffic jams up to an hour before they happen. The simulation factors in the way that drivers and their cars actually perform. With advanced knowledge of where a slow-down will occur, drivers are able to plot routes around the congestion.5

A second way to improve traffic flow is to interject "intelligence" into traffic lights. The states of the lights are preset based on previous traffic patterns. The control of those states doesn't use feedback. Nor are provisions made to sense and make use of the number of vehicles that are waiting to use the intersection. Without information on vehicle numbers or waiting periods, traffic lights change their state based upon programmed durations. Lights may change when no vehicle is waiting to use the intersection, but they'll stop oncoming traffic. Or lights may not change, holding traffic at a light when no one is coming from an opposing direction.

The multiple traffic lights that are synchronized to ease traffic delays might actually make matters worse. Such traffic lights are set. Each one changes to green just as an unimpeded vehicle, which is moving at the speed limit, approaches from the previous light. Queues build up behind red lights in heavy traffic. The stack-up will probably not fully clear during a single "green-light" period.

When traffic is light, cleverly synchronizing the lights improves traffic flow over a scheme with no synchronization. A good choice of delay times produces a flow that is similar to having no lights at all. If light changes are out of synchronization with the flow of traffic, however, they'll make the flow slower than if the lights were set at random.

Above a certain density of traffic, the choice of delay time stops making any difference at all. In such traffic, the lights that are turning green fail to clear the queue that developed in front of them. Vehicles almost always wait at every set of lights, giving journeys that all too familiar stop-and-go pattern. Traffic flow is sensitive to random fluctuations in density, which obliterates any advantage that was gained by synchronization.

If drivers view a series of changing lights early on, they may face an irresistible temptation to drive recklessly. If a driver sees a green light ahead of him and believes it will soon change, for instance, he may exceed the speed limit. Or he'll recklessly pass slower vehicles in an attempt to reach the next light before it turns red. The driver also may cut the timing too close and enter the intersection after the light turns red.

The proposed system could provide real-time reports on the number of vehicles passing or waiting at a particular intersection. A vehicle that is not moving is an indication that a problem exists. In London, traffic is metered onto the roads. As traffic builds toward the road's capacity, the fee for driving on that particular road rises. The DGPS/wireless-mesh system could monitor the traffic at various points on a road to provide a similar service. Motorists would pay a higher fee to enter the road as it becomes more congested or they could just choose an alternate route.

An inexpensive system that uses DGPS and wireless-mesh networks can reduce traffic accidents and congestion. Unlike many other proposed systems, this design uses off-the-shelf components that could be rapidly installed in the near future. In addition, the system is redundant and distributed to deliver reliable operation.

REFERENCES:

  1. "DOT Releases Preliminary Estimates of 2003 Highway Fatalities," NHTSA-04, April 28, 2004.
  2. Evans, Leonard, "Traffic Crashes," American Scientist, May/June 2002, pp. 244-253.
  3. Singh, Jatinder Pal; Bambos, Nicholas; Srinivansan, Bhaskar; and Clawin, Detlef, "Wireless LAN Performance Under Varied Stress Conditions in Vehicular Traffic Scenarios," IEEE, 0-7803-7468-1/02, 2002.
  4. Tutorial on GPS and DGPS provided at www.trimble.com/gps/how.html.
  5. Mullins, Justin, "Bad Driving the Secret to Traffic Forecasts," New Scientist web site, July 2, 2004.
  6. Huang, D. W., and Huang, W. N., "Traffic Signal Synchronization," Physical Review E, 67, 056124, 2003.
TAGS: Mobile
Hide comments

Comments

  • Allowed HTML tags: <em> <strong> <blockquote> <br> <p>

Plain text

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.
Publish