Construction of Connected Dominating Sets in Large-Scale MANETs Exploiting Self-Stabilization
Available algorithms for the distributed construction of connected dominating sets in mobile ad hoc networks are inapplicable or suffer from a high complexity. This is mainly due to the resource-restricted nature of wireless devices, such as sensor nodes, and the error-prone character of the communication medium. This paper introduces and evaluates a new local, probabilistic self-stabilizing algorithm providing fault-tolerance and scalability for networks of high density. Routing in Mobile Ad hoc NETworks (MANETs) is a challenging task due to the lack of a fixed infrastructure. Nodes must frequently perform routing decisions. This is aggravated by the error-prone communication channel and the mobility of the devices. A well-known structure upon the inherently flat hierarchy of nodes is that of a virtual backbone.