Safe and Stabilizing Distributed Cellular Flows

Advances in wireless vehicular networks present us with opportunities for developing new distributed traffic control algorithms that avoid phenomena such as abrupt phase transitions. Towards this end, we study the problem of distributed traffic control in a partitioned plane where the movement of all entities (vehicles) within each partition (cell) is tightly coupled. We present a distributed traffic control protocol that guarantees minimum separation between vehicles at all times, even when some cells´ control software may fail. Once failures cease, the protocol is guaranteed to stabilize and the vehicles with feasible paths to a target cell make progress towards it. The algorithm relies on two general principles: temporary blocking for maintenance of safety and local geographical routing for guaranteeing progress. Our proofs use mostly assertional reasoning and may serve as a template for analyzing other safe and stabilizing distributed traffic control protocols. We also present simulation results which provide estimates of throughput as a function of vehicle velocity, safety separation, path complexity, and failure-recovery rates.