An Active Constraint Method for Distributed Routing, and Power Control in Wireless Networks

Nowadays, there is an increased interest in communication via wireless mesh networks such as ad-hoc, sensor, or wireless mesh backhauling networks [1, 2]. In wireless networks the link capacities are variable quantities and can be adjusted by the resource allocation such as scheduling, and power allocation to fully exploit network performance. Hence, for efficient data transmission an integrated routing, time scheduling and power control optimization strategy are required. This strategy has to take different transmission constraints into account, for example, maximum available power level or limited buffer size at nodes. The inherent decentralized nature of wireless mesh networks mandates that distributed algorithms should be developed to implement the joint routing, scheduling, and power control optimization. The first step towards a distributed implementation is to break up this problem into manageable subproblems and solve these subproblems by iterative algorithms. Cruz and Santhanam [3] have addressed the problem of finding an optimal link scheduling and power control policy while minimizing total average power consumption. Their algorithm is designed for single-path routing only, does not consider buffer limitations and has a worst case exponential complexity. In [4], Li and Ephremedis solve at first power control and scheduling jointly. They use the obtained power values to calculate a routing distance that in turn is used by Bellman-Ford routing. However, the proposed separation is performed by not considering the combinational structure of the entire routing, scheduling and power control problem. Although less computationally intensive, the algorithm ends up in a suboptimal solution. It further fully neglects multiple path routing as well as buffer restrictions. Xiao et al. proposed in [5] the dual decomposition as a promising decomposition approach. By dual decomposition the overall problem is split into two subproblems while the master dual problem coordinates them. In this paper we consider joint routing, time-scheduling, and power control for single frequency wireless mesh networks. The wireless transmissions are arranged in time-slots. However, we take into account that simultaneously active transmissions suffer from multiple access interference. Dual decomposition is a universal approach to solve such optimization problems [5, 6], but it does not consider the specific combinational structures of optimization problems. By contrast, we propose a novel method that explicitly exploits the combinational structure of a joint routing, time-scheduling, and power control problem by means of an active constraint method. The formulation of the optimization problem is yet generally valid, so that the method proposed here is applicable to a plurality of wireless networks. The proposed approach meets the following requirements: ( ) less iterations to an optimum solution, ( ) distributed implementation, ( ) multiple path routing, and ( ) per hop error performance. In particular, the approach is as follows. We separate scheduling from routing and power allocation by including it in the constraint set of a S imultaneous R outing and P ower C ontrol (SRPC) problem. For scheduling, several well known approximations such as Greedy-based approaches exist [7, Section ], that we can leverage on. The constraints we use in the SRPC problem are induced by a precalculated colored graph of the network that, in turn, reflects the scheduling decisions of any arbitrary scheduler. Consequently, the main contribution is to introduce a R outing and P ower C ontrol D ecomposition (RPCD) method to solve the simultaneous routing and power control problem while meeting the above-mentioned requirements. The clever bits of the RPCD are manifold. ( ) We rewrite the SRPC problem to an equivalent problem by applying the active constraint method. ( ) We decouple the equivalent problem by solving a (convex) network and a (convex) power assignment problem separately. ( ) Iterations are performed by switching between the two subproblems for which network and power variables act as interchanging variables. Apart from the mathematical framework we introduce the RPCD algorithm and prove its convergence to a KKT-point of the joint routing and power control problem. We compare the RPCD algorithm with dual decomposition as state-of-art approach with respect to the number of iterations needed to calculate the KKT-point. This verification is performed by applying both algorithms to a wireless cellular mesh backhauling network [1, 2]. The backhauling network describes a "regular" cellular network. This models the situation where, in order to save infrastructure expenses of laying cable or fiber to each node (base station), we try to extend the range of a given source node with wired backhaul connection by using several other nodes. These intermediate nodes have no wired connection and can only communicate with the backhaul via the source node by wireless mesh communications. The simulation set-up correctly models mobile radio channel characteristics such as path-loss and slow fading. The comparison indicates that the RPCD approach requires only one decomposition step to calculate the optimum solution as opposed to dual decomposition. This paper is organized as follows. In Section 2 we describe the network model used for the wireless data network. In Section 3 we formulate the optimization problem and define the standard interference function. The RPCD algorithm for solving the joint routing and power control problem is presented in Section 4. We extend the RPCD algorithm in Section 5 by introducing distributed algorithms for solving the routing and power assignment problem. Finally, in Section 6 we apply the algorithm to a wireless backhaul network and present the simulation results. We conclude the paper in Section 7.

The transmission problem we are facing is to transmit messages indexed by each of size in bits via a multiple hop wireless network. Each message has its source node and its destination node . Let be an index set for the set of messages with . With multiple path routing each message is transmitted via several paths from its source node to its destination node. Thus, nodes can send parts of messages to many receivers and receive parts of messages from many transmitters. We denote the nodes by with be a finite set of nodes. At any time, each of these nodes can map any parts of messages onto a single link for transmission. The set of all links is denoted by . A wireless communication link corresponds to an edge between two nodes and is described by the ordered pair such that transmits information directly to . Moreover, we assume that for all . We have that is a directed graph with node set and edge set . For an arbitrary node , denote by and the set of outgoing and incoming edges within at the node , respectively. A link represents a wireless resource characterized by a given bandwidth, time duration, space fraction, or by a given code assignment. We assume a time-slotted single frequency network for which the time is divided into equal slots of length while all nodes occupy the same frequency band of bandwidth . Time slots are indexed by , with as an index set. We take time scheduling into account by assuming that there is a given coloring of the nodes such that adjacent nodes do not have the same color (half-duplex constraint) [4]. That is, we are given a number and a function such that for all nodes with . Here, is at least as large as the chromatic number of . Computing such a coloring can be done by a Greedy approach [7]. To take delay constraints into account we introduce as the maximum number of time slots, a message is allowed to use for transmission from its source to its destination, that is, . The interference model we consider includes multiple access interference caused by simultaneously active transmissions that can not be perfectly separated by, for example, code- or space division multiple access (CDMA/SDMA) techniques. Thus, let be the set of edges interfering edge at time . The signal attenuation from node to node is and it remains unchanged within the duration of a time slot . We further assume perfect knowledge of at the corresponding senders. Let be the transmitting node and let be the receiving node of edge . Hence, denotes the attenuation a signal suffers that is transmitted from but received by node . For link such a signal represents multiple-access interference that is caused by link . Furthermore, with as the (transmit) power to be allocated to link at time slot , the received signal power at node from the transmitter is given by . We define the signal-to-interference-plus-noise ratio (SINR) of edge at time slot as

with as an additive noise power of edge . If we only assume thermal noise to be the same for all edges, we have with noise spectral density . For the optimization problems to be introduced later we have the following design variables. As network flow variables we have as the part of the message sent along edge in time slot (in bits), and as the part of the message stored in a buffer at node directly before the start of time slot (in bits). Communication variable is the transmit power allocated to edge at time slot to transmit the total traffic on edge (in Watt). If we stack the different variables to vectors we obtain , , and . We further use the following parameters. Let be the size of message (in bits) and be the maximum total buffer size at node (in bits). Power constraints are as the maximum transmission power of a node (in Watt) assumed to be the same for all nodes and as the maximum transmission power per edge (in Watt).

In this section we present the RPCD-Algorithm for solving the SRPC problem (15). In contrast to universal approaches, like the dual decomposition method, we fully exploit our knowledge of active constraints of the joint optimization problem.

Based on Theorem 1 we can formulate an equivalent optimization problem but we avoid the extension of the utility function as usually done by applying dual or penalty approaches. We further keep the constraints and we only have to exchange the common network and power variables.

The main idea of the RPCD-Algorithm is to decouple the SRPC problem into two convex subproblems and to find the optimum solution of the SRPC problem by iteratively toggling between the two subproblems (Figure 1).

Generally, we can apply centralized as well as distributed implementation for the RPCD algorithm. In this paper we concentrate on distributed algorithm exclusively. For the interested reader, a detailed survey about the centralized and distributed algorithms and their advantages and disadvantages can be found in [12].

Herein, for the distributed approach locally available information is required and we restrict the internode communication between neighbor nodes only.

As we illustrated in the Figure 2, each node executes the distributed RPCD algorithm in advance before a time slot begins. The algorithm allocates the resources optimally, for given network and power variables and .

In the following, as introduced in Section 4.1, we consider again the two subproblems, routing (26) and power control (27), and present distributed algorithms for solving them.

In this section, we present some numerical results of the distributed RPCD algorithm as applied to a wireless mesh backhaul network. Furthermore, we compare the results with the dual decomposition method introduced by Xiao et al. in [5]. The network under consideration is a typical cellular network with hexagonal cell structure. The cells are arranged around a center cell by rings and a node is located in the center of a hexagon as depicted in Figure 3.

This models the situation where, to save infrastructure expenses like laying cable or fiber to each node in a network, we try to extend the range of given source node (center node) by intermediate nodes being wireless connected. The source node has wired backhaul connection only, while all other nodes have no wired backhaul connection and can only communicate with the wireless mesh backhaul via the source node. We require that wireless links can only be formed between nodes in adjacent rings. This means, ( ) a node can not transmit to any node that is more than one ring away, and ( ) intraring communication is not allowed so that nodes belonging to the same ring have no wireless link established. Figure 4 shows the resulting directed graph of the wireless mesh backhaul network for the case where the first ring composes three, the second ring five, and the third ring the destination node only.

Each intermediate node can transmit to and receive along multiple links from nodes, neither multicast nor broadcast is considered. The network is a single frequency network. For the sake of simplicity, we assume that the scheduler does not take in-band signaling users into account, rather we might interpret in-band users as additive noise. We further require in the simulations that simultaneously active links do not interfere. Hence, the SRPC problem under consideration is convex, therefore, the optimum solution is global. This means, we assume orthogonal transmission between links, possibly performed by Space Division Multiple Access (SDMA) schemes such as sending/receiving beamforming [15, 16]. Due to the setup of the wireless backhaul links, the nodes we consider are cellular base stations with high processing capability. Without loss of generality, the objective function we assume is to minimize total transmitted power with .

The scenario shown in Figure 4 is denoted as [ , 3, 5, 1] scenario. So, we have 10 nodes forming a wireless mesh backhauling network with 23 edges. The simulation parameter set up is as follows. The wireless network has to transmit data of = 10 Mbit size from the source node to the destination, but due to the delay constraint the transmission has to be completed within a maximum number of time slots, that is, . The bandwidth per link is = 5 MHz, the length of an time-slot is  ms and the radius per hexagonal cell is  m. We assume an exponential path-loss model with factor 3, but no shadow-fading. The thermal spectral noise density is  dBm/Hz. The buffer size per node is restricted to  Mbit. To account for power constraints we upper bound the power per node by  Watt, whereas for each specific link we assume no explicit power restriction. Regarding the distributed RPCD algorithm, we use a stopping criterion based on the variables to check for convergence. We proceed with the iteration as long as the maximum norm of two consecutive iteration steps is greater than . To show convergence, we apply the algorithm for a huge number of different starting points as well as for several networks, that is, [ , 3, 1], [ , 3, 5, 1], [ , 3, 5, 7, 1].

We observe the following result.

For a given feasible starting point the distributed RPCD algorithm converges to an optimum solution within one step only.

Since the algorithm converges globally the zero vector is always a feasible starting point.

The optimum solution is cross checked twice. First, we verify the solution by applying the NPSOL solver of TOMLAB that reflects centralized implementation. Secondly, we compare our results with another distributed algorithm, the dual decomposition approach [5]. Figure 5 shows the dual function versus iteration . Clearly, the dual function slowly converges to the unique optimum solution (as proposed in [5], we applied the subgradient method to update the dual variables ).

Hence, it is obvious that the proposed method significantly outperforms the dual decomposition approach in terms of required iterations steps towards the optimum solution. Moreover, the distributed RPCD approach requires an inter-node communication where nodes share the power and network variables only. The dual decomposition, however, requires an extra communication of the dual variables [17]. Finally, Figure 6 shows the average rate allocation of the data values per edge, where averaging is performed over the time slots the links are active. The amount of transmitted bits is given in [Mbit] while the power values are given in [Watt]. For illustration purposes, the thickness of the links reflects the amount of data transmitted, while dotted links are never active during the entire transmission. As expected, we observe that due to the geometry of the network traffic is mainly concentrated in inner links and the algorithm use one single route from the source to the destination, although multiple path routing could be performed.

Further, we decrease the bandwidth for every link in the network and use  MHz. In Figure 7 we can observe that the algorithm can not transmit the total amount of the data over one single route anymore and multiple path routing has to be performed. The transmission of the data expands over more routes in the wireless mesh backhaul network. Nevertheless the data traffic is generally concentrated in the inner links, which can be explained with the geometry of the network.