Managing a Broadcast Infrastructure in Ad Hoc Networks in Presence of Mobility: A New Algorithmic Framework

A virtual backbone forms a source-independent broadcast infrastructure in wireless ad hoc networks. Backbone formation amounts to constructing a connected dominating set (CDS) in the underlying graph. CDS construction in static networks is a well-addressed topic, whereas distributed backbone management in mobile networks has been studied to less extent. We present an algorithmic framework for managing a dynamic backbone in presence of node mobility. The framework is designed to be effective in dealing with mobility as well as in keeping backbone size small. Our approach is fully decentralized. Nodes are not required to acquire network topology information other than its local environment. All operations involved in backbone management are distributed. Moreover, the operations do not require coordination in time. As a result, decisions of joining and leaving the backbone are made locally, individually, and asynchronously at nodes. Our simulation study demonstrates the effectiveness of the framework. Even under high mobility, backbone update is satisfactorily fast to maintain backbone connectivity as well as to keep backbone size moderate