This paper proposes to use virtual backbone structure to handle control messages in ad hoc networks. This structure is effective in reducing the overhead of disseminating control information. In the first part, the approach to build the virtual backbone on the setup phase is presented. The construction of backbone is based on the Minimum Connected Dominating Set (MCDS). The novelty is in the way on finding the MCDS. A Linear Programming approach is used to build a Minimum Dominating Set (MDS). Then, a spanning tree algorithm is applied to provide the MCDS. A theoretical analysis based on probabilistic approach is developed to evaluate the size of MCDS. Different techniques of diffusion in ad hoc networks are presented and compared. The flooding technique is simple and efficient, but it is expensive in term of bandwidth consumption and causes broadcast storm problem. Simulation results show that technique using virtual backbone performs flooding and it is compared to MPR (Multipoint Relay). The second part of this paper presents a distributed procedure to maintain the backbone when the mobility of terminals is introduced. A maintenance procedure will be executed by the node which changes its position. This procedure is distributed and guarantees the node connectivity to the backbone. The authors believe that the maintenance of the backbone with small size will be more effective. Simulation results show the performance of this procedure when mobility and scalability are considered.
TopIntroduction
Wireless Ad hoc networks are very useful in emergency operations such as search and rescue, crowd control, and commando operations. The major factors that favour ad hoc wireless networks for such tasks are self-configuration of the system with a minimal overhead, independent of fixed or centralized infrastructure, the nature of the terrain of such applications, the freedom and flexibility of mobility, and the unavailability of conventional communication infrastructure.
Communications in wireless ad hoc networks suppose that there is no physical infrastructure. This supposition makes the communication more costly and conduct to a severe problem defined by (Johansson, 1999); the broadcast storm problem. This problem is induced by flooding inherent in on-demand routing protocols. Recently many propositions have been studied, which are inspired by physical backbone to maximize resource utilization and to minimize the number of exchanged messages caused by flooding. Furthermore, backbone can be used to collect topology information for routing, to provide a backup route, to send multicast or broadcast messages.
In Ad hoc environment, the network is distributed, where all network activity including discovering the topology and delivering messages must be executed by the nodes themselves, i.e. routing functionality will be incorporated into mobile nodes. Also, energy efficiency in a multi-hop network necessitates coordination between the nodes, so that they avoid wasting system resources like energy and bandwidth. While these goals can be met using centralized control, this is not practical in a mobile ad hoc network, or at least not scalable due to the high overhead to monitor and convey the control information throughout the network. A virtual backbone structure is a good solution to significantly reduce the number of nodes which handle control messages on the network. The construction and the maintenance of the virtual backbone impose another control overhead onto the overall communications: the size of the constructed backbone should be as small as possible. And, the role of virtual backbone requires connectivity of nodes. Therefore a minimum connected dominating set can make a good candidate. Nodes belonging to the MCDS set are responsible for relaying messages, while other nodes are not. However, finding the MCDS on a given graph is a NP-complete problem in graph theory.
The study of virtual infrastructures or backbones in wireless ad hoc networks gets more attention in the hope of reducing the communication overhead. But the backbone structure is very vulnerable due to various factors like node mobility and unstable links, and so on.
In most previous propositions (Guha, 1998; Tseng, 2002; Haitao, 2004; Wang, 2005; Ben, 2005; Al-Karaki, 2008), the same idea is used. One algorithm will be charged for the construction and the maintenance of virtual backbone. These propositions differ on the approach used to find the MCDS. They are based on combinatorial technique, graph coloration or marking process approaches. Our approach is different from previous ones; two independent algorithms are developed, the first one is for the construction of the backbone on the setup phase where the whole information of the network is known (number of terminals, capability, position, etc.). This algorithm guarantees a minimal size of the backbone. The second algorithm will be applied to maintain the backbone when mobility is introduced. Each node, which changes its place, applies a distributed maintenance procedure to connect to the backbone.