Autonomous vehicles rely on precise high definition (HD) 3D maps for navigation. This paper presents the mapping component of an end-to-end system for crowdsourcing precise 3D maps with semantically meaningful landmarks such as traffic signs (6 dof pose, shape and size) and traffic lanes (3D splines). The system uses consumer grade parts, and in particular, relies on a single front facing camera and a consumer grade GPS. Using real-time sign and lane triangulation on-device in the vehicle, with offline sign/lane clustering across multiple journeys and offline Bundle Adjustment across multiple journeys in the backend, we construct maps with mean absolute accuracy at sign corners of less than 20 cm from 25 journeys. To the best of our knowledge, this is the first end-to-end HD mapping pipeline in global coordinates in the automotive context using cost effective sensors.

The focus of this paper is on rate and power control algorithms in DSRC. We first design a utility maximization framework by leveraging the well-developed network congestion control, and formulate two subproblems, one on rate control with fixed transmit powers and the other on power control with fixed rates. Distributed rate control and power control algorithms are developed to solve these two subproblems, respectively, and are proved to be asymptotically optimal. Joint rate and power control can be done by using the two algorithms in an alternating fashion. The performance enhancement of our algorithms compared with a recent rate control algorithm, called EMBARC [1], is evaluated by using the network simulator ns2.

We consider the problem of precise range estimation between pairs of moving vehicles using periodic broadcast messages. The vehicles are not time synchronized and one needs to explicitly account for the clock offset and clock drift in addition to the vehicle motion to obtain accurate range estimates. We develop a broadcast range estimation algorithm based on local polynomial smoothing of the vehicle motion and experimentally verify that the performance is close to that obtained using unicast round-trip time ranging. This broadcast approach is of interest particularly in the context of dedicated short-range communication (DSRC) wherein periodic broadcast safety messages are exchanged between vehicles. We propose to exploit these broadcast messages to perform ranging. Our scheme requires additional timestamp information to be transmitted as part of the DSRC messages, and we develop a novel timestamp compression algorithm to minimize the resulting overhead. We validate our proposed algorithm on experimental data and show that it is able to achieve sub-meter ranging accuracies in vehicular scenarios.

The prevalence of smartphones presents a unique opportunity to develop a system that can have a significant impact on reducing the annual 400,000 fatalities from pedestrian traffic accidents. This system gives 360 degrees, extended range, NLOS view where both the driver and the pedestrian are warned of a possible collision. This, the first of its kind, system was developed from a two year collaborative research effort between Honda and Qualcomm to leverage DSRC so vehicles can communicate with smartphones to preempt a possible collision between a pedestrian (with a smartphone) and an approaching vehicle. This paper describes the pedestrian and vehicle-based algorithms and gives an overview of how this system warns both the driver and the pedestrian so they can take evasive action and prevent a collision. We present the results from our field tests where we demonstrate several pedestrian safety scenarios and present the over- the-air performance data collected in the field tests. Finally, we discuss remaining challenges and present possible approaches to reducing false positives, minimizing spectrum and channel congestion and improving security and localization.

A vehicular backbone network (VBN) has the potential to augment the Internet with high-throughput data flows for delay-tolerant traffic. High-throughput flows require a joint utilization of transportation capacity for carrying data packets through physical mobility and wireless capacity for switching data packets from one route to another. This paper establishes a model that incorporates both transportation mobility and wireless switching. Then, it characterizes the network capacity based on flow conservation, wireless communication capacity constraints and data storage limits, and solves a convex optimization that results in joint routing and congestion control. A variant with cost minimization reduces delay while maximizing throughput. Next, this paper develops a distributed algorithm that achieves the global objective with limited infrastructure support. Lastly, a packet-level simulation platform using real-world road map and traffic statistics is used to evaluate the distributed algorithm, and demonstrate the significant performance enhancement achieved.

The broadcast of periodic messages is a key functionality in vehicular ad hoc networks. In the emerging vehicular networks, IEEE 802.11p is the standard of choice to support the PHY and MAC layer functionalities. The broadcast process in IEEE 802.11p is based on the CSMA mechanism where a device transmitting a packet senses the channel for ongoing transmissions and performs a random back-off before accessing the channel. Without RTS/CTS mechanisms, carrier sensing is expected to provide a protection region around the transmitter where no other transmitters are allowed. The point process characterizing the concurrent transmitters is expected to enforce a minimum separation between concurrent transmitters. However, at increasing densities, the CSMA behavior breaks down to an ALOHA-like transmission pattern where concurrent transmitters are distributed as a Poisson point process, indicating the lack of protection around transmitters. In this paper, we model the CSMA mechanism as a slotted system and analytically characterize the critical node/packet arrival density where the CSMA mechanism approaches an ALOHAlike behavior. Further, we use tools from stochastic geometry to establish closed-form expressions for the performance metrics of the broadcast mechanism in the ALOHA regime. Finally, using ns2 (an unslotted asynchronous simulator), we compare the theoretical results with simulations.

Dedicated Short-Range Communications (DSRC) has been designed to support vehicular communications. In the U.S., DSRC operates in the 5.9 GHz licensed spectrum band. Its physical (PHY) and medium access control (MAC) layers, defined in the IEEE 802.11p standard, are based on the IEEE 802.11 family of Wi-Fi standards. Vehicular communication environments differ significantly from the sparse and low-velocity nomadic use cases of a typical Wi-Fi deployment. Thus, there are many challenges to adapt Wi-Fi technologies to support the unique requirements of vehicular communications such as achieving high and reliable performance in highly mobile, often densely populated, and frequently non-line-of-sight environments. The automotive and the communications industries, academia, and governments around the world have been devoting tremendous efforts to address these challenges, and significant achievements have been made. Remaining challenges can be addressed by the future versions of DSRC. In this paper, we investigate the current technologies used by DSRC to support vehicle safety communications, analyze existing and possible DSRC performance enhancements that can be realized in the near term, and provide a few initial thoughts on the DSRC evolution path.

This paper proposes FlashLinQ-a synchronous peer-to-peer wireless PHY/MAC network architecture. FlashLinQ leverages the fine-grained parallel channel access offered by OFDM and incorporates an analog energy-level-based signaling scheme that enables signal-to-interference ratio (SIR)-based distributed scheduling. This new signaling mechanism, and the concomitant scheduling algorithm, enables efficient channel-aware spatial resource allocation, leading to significant gains over a CSMA/CA system using RTS/CTS. FlashLinQ is a complete system architecture including: 1) timing and frequency synchronization derived from cellular spectrum; 2) peer discovery; 3) link management; and 4) channel-aware distributed power, data rate, and link scheduling. FlashLinQ has been implemented for operation over licensed spectrum on a digital signal processor/field-programmable gate array (DSP/FPGA) platform. In this paper, we present FlashLinQ performance results derived from both measurements and simulations.

In wireless networks, the transmission rate of a link is determined by received signal strength, interference from simultaneous transmissions, and available coding-modulation schemes. Rate allocation is a key problem in wireless network design, but a very challenging problem because: (i) wireless interference is global, i.e., a transmission interferes all other simultaneous transmissions, and (ii) the rate-power relation is non-convex and non-continuous, where the discontinuity is due to limited number of coding-modulation choices in practical systems. In this paper, we consider a realistic Signal-to-Interference-and-Noise-Ratio (SINR) based interference model, and assume continuous power space and finite rate options (coding-modulation choices). We propose a distributed power control and coding-modulation adaptation algorithm using annealed Gibbs sampling, which achieves throughput optimality in an arbitrary network topology.

Ad hoc wireless networks without central authority have attracted much attention in both academic society and industry. A key aspect of communications in such networks is the large dynamic range of interference. OFDMA (multiplexing simultaneous transmissions in different frequency tones) is an effective way of dealing with interference. On the other hand, there are many known distortions in transmit and receive chains of the communication devices, e.g. non linearity of the power amplifier, which can compromise the OFDMA orthogonality among the resources assigned to different transmissions. These distortions, together with the large dynamic range one would expect in ad hoc communications, can pose a threat to the effectiveness of communications in OFDMA ad hoc networks. In this paper, we propose and evaluate different signaling choices for communications in ad hoc networks, via both analysis and simulations. In particular, we observe that OFDMA based single tone signaling, i.e. each user transmits only on a single frequency tone, outperforms other signaling choices in many aspects.

Recent deployments of data-rich smart phones has provided a fresh impetus for designing, deploying and understanding the performance of wide area ad-hoc networks. The most popular medium access mechanism for such ad hoc networks is CSMA/CA with RTS/CTS. In this paper, using tools from stochastic geometry, we study and optimize the throughput performance of such networks. We show that in ad-hoc networks enabled with SIR based scheduling, a simple modification to the transmit power level - setting it to be inversely proportional to the square root of the link gain - leads to large improvements in network throughput. This simple power-level selection is optimal over the class of all ”local” transmit power selection strategies when channels are stationary, and further is at most a factor of two away from optimality in the fading case. Using stochastic geometric techniques, we also provide analytical expressions for the medium access probability in different scenarios.

Given a synchronous wireless network with N nodes uniformly located at random on a finite plane, we consider the problem of distributed peer discovery: all nodes want to discover as many other nodes as possible. We assume that there are a total of K physical resources dedicated for the discovery purpose. Each node can pick one resource to transmit its node identifier on, and can receive on the remaining K-1 resources. We assume that node identifiers are broadcast via coded transmission on one single physical resource. This paper addresses link level strategies to increase the average number of discovered devices when N ≅ aK, where a is the degree of density of the network. A classical strategy of discovering one node per resource would lead to a maximum of K-1 nodes being discovered. We focus on a multiple-access channel (MAC) scernario where multiple interferer users are jointly decoded. We propose a scheme to improve the performance. The method, based on iterative belief propagation on factor graph, is called joint iterative decoding (JID). It is shown, through system simulations, that JID may gain by significantly more than 100% over the classical single-user decoding, and by 20-25% over the successive interference cancellation (SIC).

In this paper, we study distributed channel assignment in wireless networks with applications to peer discovery in ad hoc wireless networks. We model channel assignment as a coloring problem for spatial point processes in whichnnodes are located in a unit cube uniformly at random and each node is assigned one ofKcolors, where each color represents a channel. The objective is to maximize the spatial separation between nodes of the same color. In general, it is hard to derive the optimal coloring algorithm, and we therefore consider a natural online greedy coloring algorithm first proposed by Ko and Rubenstein in 2005. We prove two key results: 1) with just logn/log logncolors, the distance separation achieved by the greedy coloring algorithm asymptotically matches the optimal distance separation that can be achieved by an algorithm which is allowed to optimally place the nodes but is allowed to use only one color; and 2) when K=Ω(log n), the greedy coloring algorithm asymptotically achieves the best distance separation that can be achieved by an algorithm which is allowed to both optimally color and place nodes. The greedy coloring algorithm is also shown to dramatically outperform a simple random coloring algorithm. Moreover, the results continue to hold under node mobility.

In this paper, we study distributed channel assignment in wireless networks with applications to peer discovery in ad hoc wireless networks. We model channel assignment as a coloring problem for spatial point processes in which n nodes are located in a unit cube uniformly at random and each node is assigned one of K colors, where each color represents a channel. The objective is to maximize the spatial separation between nodes of the same color. In general, it is hard to derive the optimal coloring algorithm and therefore, we consider a natural greedy coloring algorithm, first proposed in [5]. We prove two key results: (i) with just a small number of colors when K is roughly of the order of log(n) loglog(n), the distance separation achieved by the greedy coloring algorithm asymptotically matches the optimal distance separation that can be achieved by an algorithm which is allowed to select the locations of the nodes but is allowed to use only one color, and (ii) when K = Omega(log(n)), the greedy coloring algorithm asymptotically achieves the best distance separation that can be achieved by an algorithm which is allowed to both optimally color and place nodes. The greedy coloring algorithm is also shown to dramatically outperform a simple random coloring algorithm. Moreover, the results continue to hold under node mobilities.

We consider multiple-input multiple-output (MIMO) fading channels and characterize the reliability function in the low signal-to-noise (SNR) regime as a function of the number of transmit and receive antennas. For the case when the fading matrix H has independent entries, we show that the number of transmit antennas plays a key role in reducing the peakiness in the input signal required to achieve the optimal error exponent for a given communication rate. Further, by considering a correlated channel model, we show that the maximum performance gain (in terms of the error exponent and communication rate) is achieved when the entries of the channel fading matrix are fully correlated. The results we presented in this work in the low-SNR regime can also be applied to the infinite bandwidth regime

In this paper, we investigate the fundamental tradeoff between rate and bandwidth when a constraint is imposed on the error exponent. Specifically, we consider both additive white Gaussian noise (AWGN) and Rayleigh-fading channels where the input symbols are assumed to have a peak constraint. For the AWGN channel model, the optimal values of Rz(0) and Rz(0) are calculated, where Rz(1/B) is the maximum rate at which information can be transmitted over a channel with bandwidth B when the error-exponent is constrained to be greater than or equal to z. The computation of Rz(0) follows Gallager's infinite-bandwidth reliability function computation, while the computation of Rz(0) is new and parallels Verdu's second-order calculation for channel capacity. Based on these calculations, we say that a sequence of input distributions is near optimal if both Rz(0) and Rz(0) are achieved. We show that quaternary phase-shift keying (QPSK), a widely used signaling scheme, is near optimal within a large class of input distributions for the AWGN channel. Similar results are also established for a fading channel where full channel side information (CSI) is available at the receiver

We consider the problem of distributed scheduling in wireless networks subject to simple collision constraints. We define the efficiency of a distributed scheduling algorithm to be the largest number (fraction) such that the throughput under the distributed scheduling policy is at least equal to the efficiency multiplied by the maximum throughput achievable under a centralized policy. For a general interference model, we prove a lower bound on the efficiency of a distributed scheduling algorithm by first assuming that all of the traffic only uses one hop of the network. We also prove that the lower bound is tight in the sense that, for any fraction larger than the lower bound, we can find a topology and an arrival rate vector within the fraction of the capacity region such that the network is unstable under a greedy scheduling policy. We then extend our results to a more general multihop traffic scenario and show that similar scheduling efficiency results can be established by introducing prioritization or regulators to the basic greedy scheduling algorithm

Abstract — We consider a multi-hop wireless network shared by many users. For an interference model that only constrains a node to either transmit or receive at a time, but not both, we propose an architecture for fair resource allocation that consists of a distributed scheduling algorithm operating in conjunction with an asynchronous congestion control algorithm. We show that the proposed joint congestion control and scheduling algorithm supports at least one-third of the throughput supportable by any other algorithm, including centralized algorithms. I.

We consider the problem of distributed scheduling in wireless networks subject to simple collision constraints. We define the efficiency of a distributed scheduling algorithm to be the largest number (fraction) such that the throughput under the distributed scheduling policy is at least equal to the efficiency multiplied by the maximum throughput achievable under a centralized policy. For a general interference model, we prove a lower bound on the efficiency of a distributed scheduling algorithm by first assuming that all of the traffic only uses one hop of the network. We also prove that the lower bound is tight in the sense that, for any fraction larger than the lower bound, we can find a topology and an arrival rate vector within the fraction of the capacity region such that the network is unstable under a greedy scheduling policy. We then extend our results to a more general multihop traffic scenario and show that similar scheduling efficiency results can be established by introducing prioritization or regulators to the basic greedy scheduling algorithm.

The fundamental tradeoff between bandwidth and rate for wideband additive Gaussian channels, when there is a constraint in the error exponent is investigated in the previous paper. This paper extends these results to fading channels. Specifically, we consider fading channels with large coherent dimension D. which is the defined to be the product of coherent time and coherent bandwidth. The behavior of R/sub z/(1/D) which is the maximum rate at which one can communicate when the coherent dimension is D and the error exponent is constrained to be at least equal to z is considered and calculates two quantities: R/sub z/(0) and R/spl dot//sub z/(0), which together partially characterize the behavior of R/sub z/(1/D) when D is large. We show that QPSK is near-optimal for fading channels with large coherent dimension, in the sense that both R/sub z/(0) and R/spl dot//sub z/(0) can be achieved.

In this paper, a channel which is subject to multipath fading, by considering a doubly block fading model is presented. The performance of the channels with large coherence dimension and the receiver with the full knowledge of channel state information, which leads to a coherent fading model is studied. The calculations of the optimal values and the proof that QPSK is near optimal with the independent of the error-exponent constraint are proved.

We consider noncoherent MIMO fading channels and characterize the reliability function in the low-SNR regime as a function of the number of transmit and receive antennas. We assume no CSI is available at the transmitter or the receiver. For the case when the fading matrix H has independent entries, we show that the number of transmit antennas plays a key role in reducing the peakiness in the input signal required to achieve the optimal error exponent for a given communication rate. Further, by considering a correlated channel model, we show that the maximum performance gain (in terms of the error exponent and communication rate) is achieved when the entries of the channel fading matrix are fully correlated.

In this paper, we will investigate the fundamental tradeoff between bandwidth and rate for a coherent fading channel in the wideband regime, when a constraint on the error exponent is imposed. In an earlier paper (X. Wu, et al., (2003)), we computed optimal values of R(0) and R/spl dot/(0) for a nonfading channel, where R(/spl middot/) is the maximum rate at which information can be transmitted as a function of the inverse of bandwidth B, given a lower bound on the error exponent. Based on this calculation, we defined an input distribution to be near-optimal or second-order optimal if both optimal values for R(0) and R/spl dot/(0) can be achieved. In this paper, we extend this result to coherent fading channels. We show that, although both BPSK and QPSK are first-order optimal, only QPSK is second-order optimal.