A quadratic optimization method for connectivity and coverage control in backbone-based wireless networks

The use of directional wireless communications to form flexible mesh backbone networks, which provide broadband connectivity to capacity-limited wireless networks or hosts, promises to circumvent the scalability limitations of traditional homogeneous wireless networks. The main challenge in the design of directional wireless backbone (DWB) networks is to assure backbone network requirements such as coverage and connectivity in a dynamic wireless environment. This paper considers the use of mobility control, as the dynamic reposition of backbone nodes, to provide assured coverage-connectivity in dynamic environments. This paper presents a novel approach to the joint coverage-connectivity optimization problem by formulating it as a quadratic minimization problem. Quadratic cost functions for network coverage and backbone connectivity are defined in terms of the square distance between neighbor nodes, which are related to the actual energy usage of the network system. Our formulation allows the design of self-organized network systems which autonomously achieve energy minimizing configurations driven by local forces exerted on network nodes. The net force on a backbone node is defined as the negative energy gradient at the location of the backbone node. A completely distributed algorithm is presented that allows backbone nodes to adjust their positions based on information about neighbors' position only. We present initial simulation results that show the effectiveness of our force-based mobility control algorithm to provide network configurations that optimize both network coverage and backbone connectivity in different scenarios. Our algorithm is shown to be adaptive, scalable and self-organized. (C) 2008 Elsevier B.V. All rights reserved.