Optimizing vehicle-centered mobility experience requires leveraging the heterogeneous wireless connectivities (e.g., cellular, WiFi, and VANET) between vehicles and the Internet. Towards a foundation for heterogeneous vehicular wireless networking, we investigate the mathematical formulation of the problem, and we analyze the impact of bandwidth aggregation on the problem formulation as well as the computational complexity of the problem. Our analysis shows that the problem can be solved in polynomial time if bandwidth aggregation is employed, but the problem becomes NP-complete and cannot be solved optimally in general if bandwidth aggregation is not employed. Our analysis is constructive such that it suggests efficient approaches to solving the problem in an optimal manner when bandwidth aggregation is employed, and it suggests both optimal and approximate approaches to solving the problem when bandwidth aggregation is not employed. The above analytical insight serves as a guidance on choosing the system architecture and algorithms for heterogeneous vehicular wireless networking.

Interference model is the basis of MAC protocol design in wireless networked sensing and control, and it directly affects the efficiency and predictability of wireless messaging. To exploit the strengths of both the physical and the protocol interference models, we analyze how network traffic, link length, and wireless signal attenuation affect the optimal instantiation of the protocol model. We also identify the inherent trade-off between reliability and throughput in the model instantiation. Our analysis sheds light on the open problem of efficiently optimizing the protocol model instantiation. Based on the analytical results, we propose the physical-ratio-K (PRK) interference model as a reliability-oriented instantiation of the protocol model. Via analysis, simulation, and testbed-based measurement, we show that PRK-based scheduling achieves a network throughput very close to (e.g., 95%) what is enabled by physical-model-based scheduling while ensuring the required packet delivery reliability. The PRK model inherits both the high fidelity of the physical model and the locality of the protocol model, thus it is expected to be suitable for distributed protocol design. These findings shed new light on wireless interference models; they also suggest new approaches to MAC protocol design in the presence of uncertainties in network and environmental conditions as well as application QoS requirements.

Scheduling channel access for interference control is a basic building block of wireless networking. Despite much work in this area, the existing algorithms did not explicitly address the impact of link ordering (i.e., the order in which links are added to the schedule of a time slot) on receiver-side interference accumulation and thus on optimal scheduling. Towards understanding the importance of considering the ordering effect, we formulate the concept of interference budget, and, by modeling the scheduling problem as a knapsack problem, we propose the scheduling algorithm iOrder that maximizes the schedulability of future channel access when scheduling concurrent transmissions. When selecting concurrent transmitters for a time slot, more specifically, iOrder tries to maximize the additional interference that can be tolerated by all the receivers while satisfying the application requirement on link reliability. We analyze the approximation ratio of iOrder, and, through extensive simulation and testbed-based measurement, we observe that addressing the ordering effect can improve the performance of existing algorithms by a significant margin in the case of both backlogged and online traffic, for instance, improving the throughput and reducing the latency of the well-known algorithm LQF by a factor up to 2 and 24, respectively. Thus our study demonstrates the importance of explicitly addressing the ordering effect in wireless scheduling, which opens up new avenues for future research and for optimizing wireless network performance.

Real-time routing is a basic element of closed-loop, real-time sensing and control, but it is challenging due to dynamic, uncertain link/path delays. The probabilistic nature of link/path delays makes the basic problem of computing the probabilistic distribution of path delays NP-hard, yet quantifying probabilistic path delays is a basic element of real-time routing and may well have to be executed by resource-constrained devices in a distributed manner; the highly-varying nature of link/path delays makes it necessary to adapt to in-situ delay conditions in real-time routing, but it has been observed that delay-based routing can lead to instability, estimation error, and low data delivery performance in general. To address these challenges, we propose the Multi-Timescale Estimation (MTE) method; by accurately estimating the mean and variance of per-packet transmission time and by adapting to fast-varying queueing in an accurate, agile manner, MTE enables accurate, agile, and efficient estimation of probabilistic path delay bounds in a distributed manner. Based on MTE, we propose the Multi-Timescale Adaptation (MTA) routing protocol; MTA integrates the stability of an ETX-based directed-acyclic-graph (DAG) with the agility of spatiotemporal data flow control within the DAG to ensure real-time data delivery in the presence of dynamics and uncertainties. We also address the challenges of implementing MTE and MTA in resource-constrained devices such as TelosB motes. We evaluate the performance of MTA using the NetEye and Indriya sensor network testbeds. We find that MTA significantly outperforms existing protocols, e.g., improving deadline success ratio by 89% and reducing transmission cost by a factor of 9.7.

Co-channel interference is a limiting factor to the predictability and performance of wireless networks, thus interference-oriented scheduling of channel access has become a basic building block of wireless networking. Despite much work in this area, the existing algorithms did not address the limiting impact of interference when optimizing transmission scheduling. Towards understanding the importance of considering the limiting impact of interference, we formulate the concept of interference budget, and we propose the scheduling algorithm iOrder that maximizes the schedulability of future channel access when scheduling concurrent transmissions. When selecting concurrent transmitters for a time slot, more specifically, iOrder tries to maximize the additional interference that can be tolerated by all the receivers while satisfying the application requirement on link reliability. We analyze the approximation ratio of iOrder, and, through extensive simulation and testbed-based measurement, we observe that addressing the limiting impact of interference can improve the performance of existing algorithms by a significant margin, for instance, improving the throughput of the well-known algorithm LQF by a factor up to 2. Thus our study demonstrates the importance of explicitly addressing the limiting impact of interference, which opens up new avenues for future research and for optimizing wireless network performance.

To exploit the strengths of both the physical and the protocol interference models and to understand the varying observations on the relative goodness of scheduling based on the two models in literature, we analyze how network traffic, link length, and wireless signal attenuation affect the optimal instantiation of the protocol model. We also identify the inherent tradeoff between reliability and throughput in the model instantiation. Our analysis explains the seemingly inconsistent observations in literature and sheds light on the open problem of efficiently optimizing the protocol model instantiation. Based on the analytical results, we propose the physical-ratio-K (PRK) interference model as a reliability-oriented instantiation of the protocol model. Via analysis, simulation, and testbed-based measurement, we show that PRK-based scheduling achieves a network throughput very close to (e.g., 95%) what is enabled by physical-model-based scheduling while ensuring the required packet delivery reliability. The PRK model inherits both the high fidelity of the physical model and the locality of the protocol model, thus it is expected to be suitable for distributed protocol design. These findings shed new light on wireless interference models; they also suggest new approaches to MAC protocol design in the presence of uncertainties in traffic and application properties.