Evaluation of Physical Carrier Sense Based Backbone Maintenance in Mobile Ad Hoc Networks

Physical carrier sensing has to date mainly been exploited for improving medium access control in wireless networks. Recently, a parallel algorithm striving to extensively exploit physical carrier sensingfor constructing and maintaining a connected dominating set (CDS), which is also known as spanner,backbone, or overlay network in wireless ad hoc networks with interference ranges larger than transmissionranges has been proposed. Existing evaluations of this algorithm are limited to theoretical asymptoticbounds and simulations of static networks. In this paper, we evaluate the physical carrier sensing-basedCDS maintenance for mobile ad hoc networks through discrete event simulations. For a wide range ofnode speeds and node densities, we evaluate the CDS characteristics and message exchanges required formaintaining the CDS. We find that the algorithm maintains a stable leader set dominating all nodes in thenetwork for a wide range of mobility levels but struggles to maintain connectivity at high mobility levels.We also quantify the portions of the control messages for CDS maintenance that are exchanged throughphysical carrier sensing. We find that the parallel algorithm manages to greatly reduce the reliance onintact message receptions