A quadratic optimization method for connectivity and coverage control in backbone-based wireless networks:
abstract:
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.
1. Motivation
In a flat network architecture, all wireless nodes are homogeneous in terms of their communication capabilities. It is well known that the throughput capacity of a flat wireless network architecture without an infrastructure support is not scalable as the number of nodes becomes large [1]. Consequently, in order to meet the increasing communication demands of wireless users, it is necessary to supplement the wireless network with a higher layer of communication mode. This new communication mode enables a small group of nodes to communicate with each other over longer distances and at higher bit rates than the ordinary wireless nodes. We refer to these nodes as base
station or backbone nodes. Such nodes are equipped with a hybrid communication mode that enables them to communicate with both the terminal wireless nodes and the other base station nodes. Base station nodes form a backbone for the network, through the use of point-to-point communication technologies such as free space optical communication, fiber optic communication, directional
antennas, etc.
In a backbone-based wireless network architecture, communication between two terminal wireless nodes takes place by a multi-hop transmission scheme over the wireless nodes until the traffic of the source reaches one of the backbone nodes, then it travels over the backbone network until it reaches a backbone node which is close enough to the intended destination, and finally it travels over a few wireless nodes until it reaches its destination. From a networking point of view, some of the most important design aspects of this architecture are: the required number of backbone nodes for a certain target performance, and the efficient placement of the backbone nodes in the network.
Moreover, DWB networks must provide robust end-to end broadband connectivity in a dynamic wireless environment, where the state of wireless links is constantly changing due to node mobility and atmospheric obscuration [3]. The DWB topology, as defined by the location of the backbone nodes and the connections between them, needs to adjust to the changing environment. Thus, it is
important to provide the DWB with the capability of autonomous reconfiguration. The location of the backbone nodes needs to be updated in order to dynamically meet the wireless users demands.
We propose to solve the joint coverage-connectivity optimization problem by formulating it as an energy minimization problem. Convex energy functions for both coverage and connectivity are defined in terms of the distance between each terminal and its assigned backbone node (for network coverage) and between neighbor backbone nodes (for backbone connectivity). We then compute
forces on every node as the negative energy gradient and show how backbone nodes achieve the optimal topology configuration when reacting to local forces exerted by neighbor nodes.
Similar problems have been considered in the past which can be related to the coverage-connectivity optimization problem for DWB networks. In facility location problems (FLPs), a set of client locations are to be serviced by facilities. If a client at location j is assigned to a facility at location i, a cost of c is incurred that is proportional to the distance between i and j. The objective is to find the optimal placement of facilities so as to minimize the total assignment costs. In DWB-based networks, terminal nodes are considered as clients and backbone nodes as facilities. The main difference between facility location problems and our problem is that in FLPs the connectivity between facilities (backbone nodes) is not considered, which is of critical importance in DWBbased networks, as terminal nodes cannot communicate with each other if the backbone is not connected. Also, in
facility location problems, the location of the facilities take discrete integer values. FLPs are thus usually formulated as integer programming problems and are shown to be NPComplete. Approximation algorithms have been developed that give constant approximation guarantees [4].
4. Simulation results
In order to gain more insight on the problem and verify the performance of our optimization algorithm, we present results from initial simulation studies with different design parameters.
In all simulations, N terminal nodes are distributed in a 100 100 two dimensional plane. Terminal nodes are organized in clusters. The first terminal node is placed in the plane according to a uniform random distribution. Each other terminal is placed within clusterRange of the previous terminal node with probability p, and uniformly in the 100 100 plane with probability 1 p cluster
. Next, M backbone nodes are placed at random in the plane and an initial ring topology is built connecting all backbone nodes. Then, our mobility control algorithm is executed to make backbone
nodes adjust their position until convergence to the optimal backbone configuration.
Before we report quantitative results, we first present several figures to visually illustrate the effectiveness of the mobility control algorithm. Fig. 2 shows results for a network with 100 terminal nodes and 10 backbone nodes. The values used for the variables clusterRange and p are 10 and 0.2, respectively. The backbone nodes are labeled and the links between them are shown in thick dotted
lines. Links from each terminal node to its closest backbone node are shown in thinner dotted lines. Fig. 2a shows the initial non-optimal network configuration. Fig. 2b shows the resulting network configuration after running the mobility control algorithm with a balancing factor g ¼ 1. In this case, the low value of g allows backbone nodes to move close to the terminal nodes to optimize network coverage at the expense of low backbone connectivity. Fig. 2c and d show the resulting network configurations with g ¼ 5 and g ¼ 10, respectively. The higher value of g increases the weight on the backbone connectivity objective thus making the backbone nodes move closer to each other. Finally Fig. 2e and f show the resulting network configurations for g ¼ 20 and g ¼ 30, where stronger
backbone networks are produced at the expense of lower network coverage. In Fig. 3 we show a network with 20 backbone nodes. The number of terminals remains 100
and they are randomly placed according to the procedure explained above. As seen in Fig. 3, the increased number of backbone nodes allows more flexibility to optimize network coverage with less penalization on backbone connectivity, and vice versa.
DOWNLOAD LINK:
CLICK ME
abstract:
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.
1. Motivation
In a flat network architecture, all wireless nodes are homogeneous in terms of their communication capabilities. It is well known that the throughput capacity of a flat wireless network architecture without an infrastructure support is not scalable as the number of nodes becomes large [1]. Consequently, in order to meet the increasing communication demands of wireless users, it is necessary to supplement the wireless network with a higher layer of communication mode. This new communication mode enables a small group of nodes to communicate with each other over longer distances and at higher bit rates than the ordinary wireless nodes. We refer to these nodes as base
station or backbone nodes. Such nodes are equipped with a hybrid communication mode that enables them to communicate with both the terminal wireless nodes and the other base station nodes. Base station nodes form a backbone for the network, through the use of point-to-point communication technologies such as free space optical communication, fiber optic communication, directional
antennas, etc.
In a backbone-based wireless network architecture, communication between two terminal wireless nodes takes place by a multi-hop transmission scheme over the wireless nodes until the traffic of the source reaches one of the backbone nodes, then it travels over the backbone network until it reaches a backbone node which is close enough to the intended destination, and finally it travels over a few wireless nodes until it reaches its destination. From a networking point of view, some of the most important design aspects of this architecture are: the required number of backbone nodes for a certain target performance, and the efficient placement of the backbone nodes in the network.
Moreover, DWB networks must provide robust end-to end broadband connectivity in a dynamic wireless environment, where the state of wireless links is constantly changing due to node mobility and atmospheric obscuration [3]. The DWB topology, as defined by the location of the backbone nodes and the connections between them, needs to adjust to the changing environment. Thus, it is
important to provide the DWB with the capability of autonomous reconfiguration. The location of the backbone nodes needs to be updated in order to dynamically meet the wireless users demands.
We propose to solve the joint coverage-connectivity optimization problem by formulating it as an energy minimization problem. Convex energy functions for both coverage and connectivity are defined in terms of the distance between each terminal and its assigned backbone node (for network coverage) and between neighbor backbone nodes (for backbone connectivity). We then compute
forces on every node as the negative energy gradient and show how backbone nodes achieve the optimal topology configuration when reacting to local forces exerted by neighbor nodes.
Similar problems have been considered in the past which can be related to the coverage-connectivity optimization problem for DWB networks. In facility location problems (FLPs), a set of client locations are to be serviced by facilities. If a client at location j is assigned to a facility at location i, a cost of c is incurred that is proportional to the distance between i and j. The objective is to find the optimal placement of facilities so as to minimize the total assignment costs. In DWB-based networks, terminal nodes are considered as clients and backbone nodes as facilities. The main difference between facility location problems and our problem is that in FLPs the connectivity between facilities (backbone nodes) is not considered, which is of critical importance in DWBbased networks, as terminal nodes cannot communicate with each other if the backbone is not connected. Also, in
facility location problems, the location of the facilities take discrete integer values. FLPs are thus usually formulated as integer programming problems and are shown to be NPComplete. Approximation algorithms have been developed that give constant approximation guarantees [4].
4. Simulation results
In order to gain more insight on the problem and verify the performance of our optimization algorithm, we present results from initial simulation studies with different design parameters.
In all simulations, N terminal nodes are distributed in a 100 100 two dimensional plane. Terminal nodes are organized in clusters. The first terminal node is placed in the plane according to a uniform random distribution. Each other terminal is placed within clusterRange of the previous terminal node with probability p, and uniformly in the 100 100 plane with probability 1 p cluster
. Next, M backbone nodes are placed at random in the plane and an initial ring topology is built connecting all backbone nodes. Then, our mobility control algorithm is executed to make backbone
nodes adjust their position until convergence to the optimal backbone configuration.
Before we report quantitative results, we first present several figures to visually illustrate the effectiveness of the mobility control algorithm. Fig. 2 shows results for a network with 100 terminal nodes and 10 backbone nodes. The values used for the variables clusterRange and p are 10 and 0.2, respectively. The backbone nodes are labeled and the links between them are shown in thick dotted
lines. Links from each terminal node to its closest backbone node are shown in thinner dotted lines. Fig. 2a shows the initial non-optimal network configuration. Fig. 2b shows the resulting network configuration after running the mobility control algorithm with a balancing factor g ¼ 1. In this case, the low value of g allows backbone nodes to move close to the terminal nodes to optimize network coverage at the expense of low backbone connectivity. Fig. 2c and d show the resulting network configurations with g ¼ 5 and g ¼ 10, respectively. The higher value of g increases the weight on the backbone connectivity objective thus making the backbone nodes move closer to each other. Finally Fig. 2e and f show the resulting network configurations for g ¼ 20 and g ¼ 30, where stronger
backbone networks are produced at the expense of lower network coverage. In Fig. 3 we show a network with 20 backbone nodes. The number of terminals remains 100
and they are randomly placed according to the procedure explained above. As seen in Fig. 3, the increased number of backbone nodes allows more flexibility to optimize network coverage with less penalization on backbone connectivity, and vice versa.
DOWNLOAD LINK:
CLICK ME
No comments:
Post a Comment