In this paper, an analytical framework is proposed for the optimization of network performance through joint congestion control, channel allocation, rate allocation, power control, scheduling, and routing with the consideration of fairness in multi-channel wireless multi-hop networks. More specifically, the framework models the network by a generalized network utility maximization (NUM) problem under an elastic link data rate and power constraints. Using the dual decomposition technique, the NUM problem is decomposed into four subproblems — flow control; next-hop routing; rate allocation and scheduling; power control; and channel allocation — and finally solved by a low-complexity distributed method. Simulation results show that the proposed distributed algorithm significantly improves the network throughput and energy efficiency compared with previous algorithms.
A fundamental problem in networking is the allocation of limited resources among the users of a network. In the traditional layered network architecture, resources are allocated independently within each layer in the Open Systems Interconnection (OSI) model. This methodology has many advantages. For example, protocols in one layer can be designed, enhanced, or even replaced without any impact on other protocol layers. However, design problems that have been studied in isolation, such as routing, channel assignment, power control, topology control, and so on, are so closely linked through the reality of wireless interference. For example, it may happen that data packets are routed on a high interference path in the network. This necessitates the link scheduling to yield a high throughput schedule and the channel allocation to re-allocate appropriate channels along this path. This highlights the need for the designing of link scheduling, channel allocation, and routing as a joint problem.In fact, there has been a fast expansion of research interest in this area since Kelly first modeled the framework of cross-layer design as an NUM problem in his seminal work [1]. Motivated by it, the researches model the cross-layer resource allocation as different network utility maximization (NUM) problems, most of which are concerned with maximizing the data rate of each user [2]–[3], minimizing power consumption [4]–[5] and outage probability [6]. With these generalized objectives, problems between different layers are studied together. For example, a joint design of power control in the physical layer and congestion control in the transport layer for wireless ad hoc networks was proposed in [7]. A jointly optimal channel assignment and congestion control problem for multi-channel wireless mesh networks was solved in [8]. In [9], Chen and others presented a jointly optimal design of cross-layer congestion control, routing, and scheduling for ad hoc networks. In [10], an analytical framework was introduced for the optimization of transmission control protocol performance through joint channel coding and power management in satellite communications. Reference [11] endeavored to address the lack of a joint routing and sleep scheduling scheme in wireless sensor networks by incorporating the design of the two components into one optimization framework. Reference [12] discussed a joint routing, congestion control, channel allocation, and scheduling algorithm for multi-channel multi-interface wireless multi-hop networks. In addition, a joint multipath routing, channel allocation, and scheduling problem was discussed in [13] for wireless multi-hop and wireless multi-channel systems. References [14] to [17] are different research results on cross-layer design, proposed recently. However, cross-layer resource allocation has not been fully explored yet. None of these algorithms have jointly considered congestion control, channel allocation, rate allocation, power control, scheduling, and routing this complex problem.In this paper, we propose a distributed joint congestion control, channel allocation, rate allocation, power control, scheduling, and routing algorithm (JCCRPSR) for multi-radio multi-channel wireless multi-hop networks (MRMC-WMHNs). The cross-layer resource allocation is modeled as an NUM problem with an elastic link data rate and power constraints. Using the dual decomposition technique, the NUM problem can be decomposed into the following four subproblems: flow control; next-hop routing; rate allocation and scheduling; power control; and channel allocation. Finally, these subproblems are solved with different low-complexity distributed methods.The rest of this paper is organized as follows. The system model and constrained optimization problem are described in Section II. The distributed algorithm is presented in Section III. Simulation results and discussions are presented in Section IV, and Section V concludes the paper.
II. System Model and Problem Formulation
- 1. Network Model
Consider a WMHN that contains a set 𝒩 of nodes and a set 𝓛 of logical links. The nodes and links are labeled with the integer values n = 1, 2, ..., N and the integer values l = 1, 2, ..., L, respectively. Let 〈m, n〉 denote a bidirectional link, which contains two logical links, (m, n) and (n, m); that is, the connectivity between the nodes is assumed to be symmetric. The sets of incoming and outcoming logical links of node n are defined as
L n in ∈𝓛
and
L n out ∈𝓛,
respectively. Similarly, the sets of in-neighbors and out-neighbors of node n are labeled
N n in ={m:(m,n)∈ L n in }
and
N n out ={m:(n,m)∈ L n out }
, respectively. Each node n is provided with I_{n} half-duplex wireless interfaces, and the set of logical links that use radio k ∈ I_{n} at node n is denoted by
L n k
. At any given time, each interface can be tuned to any one of C channels, and the set of available channels is denoted by Θ = {1, 2, ... C}.Traffic flows are, in general, carried over multi-hop routes. A sequence of connected logical links l ∈ L(s) forms a route for flow s ∈ 𝑆 where 𝑆 = {1, 2, ..., S} is the set of flows in the network. Let f_{s} ∈ F be the transmission rate of flow s, where F = [f_{1}, f_{2}, ..., f_{s}] is the set of transmission rate. For an arbitrary node n, let
f n (s)
≥ 0 denote the sth flow rate generated by node n. If node n is not the source node of flow s, then
f n (s)
= 0; otherwise,
f n (s)
= f_{s}.In addition, the link flow rate vector, R, is defined to be R =
[ r mn (1) , r mn (2) , … , r mn (S) ]
, in which the element signifies the rate for each flow on link (m, n). Based on this, the aggregated flow rate on link (m, n) can be denoted as
r mn = ∑ s∈S r mn (s)
. The topology generation algorithm Hyacinth, proposed in [8], is used to form a logical topology that is free from the ripple effect. The general protocol interference model is adopted so that the conflict graph can be employed to capture the contention relations among links. The network is assumed to operate in slotted time, with the slots being normalized to a set of integer values t (t = 1, 2, ...).
- 2. Problem Formulation
The goal of the proposed algorithm is to solve the following optimization problem:$$\underset{\bm{F},\bm{X},\bm{P},\bm{R}}{\mathrm{max}}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}{\displaystyle {\sum}_{s\in S}U({f}_{s})}$$s.t. $${\bm{x}}_{l}{1}^{T}=1,\text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}\forall l\in \U0001d4db\text{\hspace{0.05em}},$$$$\sum}_{c=1}^{C}{y}_{n}^{(c)}}\le {I}_{n}\text{\hspace{0.05em}\hspace{0.05em}},\text{\hspace{0.05em$$$$\begin{array}{c}\text{\hspace{0.05em}}0\le {\displaystyle {\sum}_{m\in {N}_{n}^{out}}{P}_{nm}\le {P}_{n}^{\mathrm{max}}},\text{\hspace{0.05em}}\\ {f}_{n}^{(s)}+{\displaystyle \sum _{m:(m,n)\in {L}_{s},\text{\hspace{0.17em}}m\in {N}_{n}^{\text{in}}}{r}_{mn}^{(s)}}\le {\displaystyle \sum _{q:(n,q)\in {L}_{s},\text{\hspace{0.17em}}q\in {N}_{n}^{out}}{r}_{nq}^{(s)}},\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\end{array}$$$$\forall n\in \mathcal{N},\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}n\ne {d}_{s},\text{\hspace{0.05em}\hspace{0.17em}}\forall s\in S\text{,}$$$${r}_{l}={\displaystyle \sum _{s\in S}{r}_{l}^{(s)}}\le {C}_{l}(\bm{X}\text{,}\bm{P})\text{,\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}l\in \U0001d4db\text{,}$$and$$\begin{array}{l}{C}_{l}(\bm{X}\text{,}\bm{P})=\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}B{\mathrm{log}}_{2}\left[1+\left(K\times \frac{{P}_{l}{g}_{ll}}{{\displaystyle {\sum}_{i\ne l}({\bm{x}}_{l}^{T}{\bm{x}}_{i}{P}_{i}{g}_{il}+{n}_{l})}}\right)\right],\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}l\in \U0001d4db\text{.\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\end{array}$$Equation (1) is the objective function. Here, the utility, U(f_{s}), is equivalent to log f_{s}[3] and is proved to be twice continuously differentiable, non-decreasing, and strictly concave. The objective function is used to implement proportional fairness among the flows.Equation (2) represents the channel constraint. A binary link-channel allocation matrix, X_{L×C}∈ R^{L×C} is firstly defined. Then, let x_{l} = [x_{l1}, x_{l2}, ... , x_{lL}]^{T} denote the lth row of X, in which the element is defined as follows: for any logical link l ∈ 𝓛 and any channel c ∈ Θ, the element x_{lc} is equal to one if channel c is allocated to logical link l; otherwise, it is equal to zero.According to this, the constraint in (2) denotes that only one frequency channel can be assigned to each given logical link l.Equation (3) indicates that the number of allocated channels to each node should be less than the number of network interface cards (NICs) equipped on the corresponding node. Here,
y n (c)
represents the binary node channel allocation variable, which is equal to one if channel c is allocated to logical node n; otherwise, it is equal to zero.
▪ Equation (4) is the power constraint for each node.
▪ Equation (5) is the flow conservation constraint; that is, for flows, the sum of all incoming flows in a non-destination node (n) must be no less than the sum of all outgoing flows.
▪ Equation (6) is the link capacity constraint. The aggregated flow rate on each link should not exceed its link capacity.
▪ Equation (7) is the available link capacity. Here, the constantBis the transmission bandwidth on each channel,K= −φ1/ log(φ2E), whereφ1andφ2are constants depending on the modulation andEis the required bit error rate;gildenotes the path gain between the transmitter of linkiand the receiver of linkl; andnlis the additive thermal white noise power.
Note that the NUM problem has binary variables X; real variables F and P; and mixed binary-real cubic constraints. It is a complex non-linear mixed integer programming problem. Here, the objective function is twice continuously differentiable, non-decreasing, and strictly concave. In addition, here, the constraints are all linear, except for those in (5) and (6). For the constraints in (5) and (6), binary linearization [18], and log-transformed convex optimization techniques [7] are applied to transform C_{l}(X, P) into a linear function, as mentioned in our previous work [3]. Therefore, the NUM problem can be converted into a convex optimization problem so that the centralized manner, such as branch and bound algorithm, can be applied to find the global optimal solution of the NUM problem. The optimal solution is used as an ideal reference in Section IV. Next, we introduce a more practical distributed method to solve this NUM problem.
III. Cross-Layer Design via Dual Decomposition
Dual decomposition is used to solve the NUM problem. By introducing {
λ n (s)
≥ 0 for all n, s : n ≠ d_{s}} as the set of Lagrange multipliers to relax the constraint in (5), the dual to the primal NUM problem can be expressed as a max–min problem as follows:$$\text{\hspace{0.05em}}\underset{\lambda \ge 0}{\mathrm{min}}D(\lambda ),$$with partial dual function$$\begin{array}{l}\text{\hspace{0.05em}}D(\lambda )=\underset{{f}_{s}\ge 0,\text{\hspace{0.17em}\hspace{0.17em}}{r}_{mn}^{(s)}\ge 0}{\mathrm{max}}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}{\displaystyle {\sum}_{s\in S}U({f}_{s})}-\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}{\displaystyle {\sum}_{s,\text{\hspace{0.17em}\hspace{0.17em}}n:n\ne {d}_{s}}{\lambda}_{n}^{(s)}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\left({f}_{n}^{(s)}\text{\hspace{0.05em}}+\text{}{\displaystyle \sum _{m\text{:}mn\in {L}_{s}\text{,\hspace{0.17em}\hspace{0.17em}}m\in {N}_{n}^{in}}{r}_{mn}^{(s)}}-\text{\hspace{0.05em}}{\displaystyle \sum _{q:nq\in {L}_{s},\text{\hspace{0.17em}\hspace{0.17em}}q\in {N}_{n}^{out}}{r}_{nq}^{(s)}}\right)}\end{array}$$s. t. (2), (3), (4), (6), and (7).The optimization problem D(λ) in (9) can be directly decomposed into the following two subproblems:$$\text{\hspace{0.05em}}{D}_{1}(\lambda )=\underset{{f}_{s}\ge 0}{\mathrm{max}}\text{\hspace{0.05em}\hspace{0.05em}}{\displaystyle {\sum}_{s\in S}U({f}_{s})}-{\displaystyle {\sum}_{s\in S}{\lambda}_{s}{f}_{s}}$$and$$\begin{array}{l}\text{\hspace{0.05em}}{D}_{2}(\lambda )=\underset{{r}_{mn}^{(s)}\ge 0}{\mathrm{max}}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\\ {\displaystyle {\sum}_{s,\text{\hspace{0.17em}}n:n\ne {d}_{s}}{\lambda}_{n}^{(s)}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\left({\displaystyle \sum _{q:nq\in {L}_{s},\text{\hspace{0.17em}}q\in {N}_{n}^{out}}{r}_{nq}^{(s)}}-{\displaystyle \sum _{m:mn\in {L}_{s},\text{\hspace{0.17em}}m\in {N}_{n}^{\text{in}}}{r}_{mn}^{(s)}}\right)}\end{array}$$s. t. (2), (3), (4), (6), and (7).If
λ n (s)
≥ 0 is interpreted as the congestion price, then (10) is considered as a congestion control problem, while (11) is a joint routing, scheduling, power control and channel allocation problem. The two interact through the congestion price
λ n (s)
.For congestion price
λ n (s)
, the subgradient algorithm is employed to solve it. By taking the derivative of D(λ) with respect to λ, we obtain the following:$${\nabla}_{n}\text{\hspace{0.05em}}D(\lambda )={\displaystyle \sum _{q:nq\in {L}_{s},\text{\hspace{0.17em}}q\in {N}_{n}^{\text{out}}}{r}_{nq}^{(s)}}-{\displaystyle \sum _{m:mn\in {L}_{s},\text{\hspace{0.17em}}m\in {N}_{n}^{\text{in}}}{r}_{mn}^{(s)}}-{f}_{n}^{(s)}$$So, the congestion price
λ n (s)
can be updated as$$\text{\hspace{0.05em}}{\lambda}_{n}^{(s)}(t+1)\text{\hspace{0.05em}\hspace{0.05em}}={\left\{{\lambda}_{n}^{(s)}(t)-\left(\eta \times {\nabla}_{n}\text{\hspace{0.05em}}D(\lambda )\right),0\right\}}^{+},$$where f_{s} and
r mn (s)
are the solutions of (10) and (11), respectively; {·, 0}^{+} = max(·, 0); η is a sufficiently small step size, and t is an iteration time slot.According to (10), with known {
λ n (s)
≥ 0 ∀n, s : n ≠ d_{s}} the congestion control problem can be solved at each iteration time slot by$${f}_{s}^{(t+1)}={U}_{s}^{\text{'}-1}({\lambda}_{s}),$$where
U s '−1 (⋅)
is the inverse of the first derivative of the utility.For problem (11), it is a queue length–based model with a feasible-rate region constraint. It can be transformed into the following formula:$$\begin{array}{l}{\displaystyle {\sum}_{s,\text{\hspace{0.17em}}n:n\ne {d}_{s}}{\lambda}_{n}^{(s)}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\left({\displaystyle \sum _{q:nq\in {L}_{s},\text{\hspace{0.17em}}q\in {N}_{n}^{out}}{r}_{nq}^{(s)}}-{\displaystyle \sum _{m:mn\in {L}_{s},\text{\hspace{0.17em}}m\in {N}_{n}^{in}}{r}_{mn}^{(s)}}\right)}\\ ={\displaystyle \sum _{mq\in {L}_{s}}{r}_{mq}^{(s)}}({\lambda}_{m}^{(s)}-{\lambda}_{q}^{(s)});\end{array}$$that is,$$\text{\hspace{0.05em}\hspace{0.05em}}{D}_{2}(\lambda )=\underset{{r}_{mn}^{(s)}\ge 0}{\mathrm{max}}\text{\hspace{0.05em}}{\displaystyle \sum _{mq\in L}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}{r}_{mq}^{(s)}({\lambda}_{m}^{(s)}-{\lambda}_{q}^{(s)})}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}$$s. t. (2), (3), (4), (6), and (7).For each link (m, q), we find s* such that$${s}^{*}\text{\hspace{0.05em}}=\mathrm{arg}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\underset{s\in S}{\mathrm{max}}({\lambda}_{m}^{(s)}\text{\hspace{0.05em}}-{\lambda}_{q}^{(s)}),$$where
λ mq (s) = λ m (s) − λ q (s)
is the differential price on link (m, q). To maximize
∑ mq∈L r mq (s) ( λ m (s) − λ q (s) )
all available link capacity should be allocated to the flow s^{*} that has the largest differential price,
λ mq (s)
, that fits the dynamic back pressure (DBP) [9] scheduling algorithm well. It implies that for each link (m, q),
r mq (s)
= C_{mq} (X, P) if s=s^{*} and
r mq (s)
= 0 otherwise. Therefore, (16) is equivalent to the following capacity maximization problem:$${D}_{3}(\lambda )=\text{\hspace{0.05em}\hspace{0.05em}}\underset{\bm{X}\text{,\hspace{0.05em}\hspace{0.05em}}\bm{P}}{\mathrm{max}}{\displaystyle \sum _{l\in L}\text{\hspace{0.05em}\hspace{0.05em}}{\lambda}_{l}^{({s}^{*})}{C}_{l}(\bm{X},\bm{P})}$$s. t. (2), (3), (4), and (7).
- 1. Joint Channel Allocation and Power Control
The objective in (18) is to maximize the whole weighted capacity by assigning the channel and power to the network links according to the congestion price information. To decouple the optimization variables X and P, we can directly decompose (18) into two subproblems: congestion-aware channel allocation and congestion-aware power control.A. Congestion-Aware Channel Allocation Subproblem$$\begin{array}{l}{D}_{4}(\lambda )=\text{\hspace{0.05em}\hspace{0.05em}}\underset{\bm{X}}{\mathrm{max}}\text{\hspace{0.05em}\hspace{0.05em}}{\displaystyle \sum _{l\in \U0001d4db}\text{\hspace{0.05em}\hspace{0.05em}}{\lambda}_{l}^{({s}^{*})}{C}_{l}(\bm{X})}\\ \text{s.\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}t.\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}{\bm{x}}_{l}{1}^{T}=1,\text{\hspace{0.17em}\hspace{0.17em}}\forall l\in \text{\hspace{0.05em}}\U0001d4db,\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}{\displaystyle {\sum}_{c=1}^{C}{y}_{n}^{(c)}}\le {I}_{n}\text{\hspace{0.05em}\hspace{0.05em}},\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\\ {C}_{l}(\bm{X})=B{\mathrm{log}}_{2}\left[1+\left(K\times \frac{{P}_{l}^{\ast}{g}_{ll}}{{\displaystyle {\sum}_{i\ne l}({\bm{x}}_{l}^{T}{\bm{x}}_{i}{P}_{i}^{\ast}{g}_{il}+{n}_{l})}}\right)\right],\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}l\in \U0001d4db\text{\hspace{0.05em}},\end{array}$$where P_{l}^{*}, ∀l ∈ 𝓛, is obtained from solving the power control subproblem (20). The local implementation of (19) is given by$$\begin{array}{l}{D}_{5}(\lambda )=\text{\hspace{0.05em}\hspace{0.05em}}\underset{{\bm{x}}_{l},\text{\hspace{0.17em}\hspace{0.17em}}l\in {L}_{n}}{\mathrm{max}}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}{\displaystyle \sum _{l\in \U0001d4db}\text{\hspace{0.05em}\hspace{0.05em}}{\lambda}_{l}^{({s}^{*})}{C}_{l}(\bm{X})}\\ \text{s.\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}t.\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}{\bm{x}}_{l}{1}^{T}=1,\text{\hspace{0.17em}\hspace{0.17em}}\forall l\in \U0001d4db\text{\hspace{0.05em}},\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}}{\displaystyle {\sum}_{c=1}^{C}{y}_{n}^{(c)}}\le {I}_{n}\text{\hspace{0.05em}\hspace{0.05em}},\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\\ {C}_{l}(\bm{X})=B{\mathrm{log}}_{2}\left[1+\left(K\times \frac{{P}_{l}^{\ast}{g}_{ll}}{{\displaystyle {\sum}_{i\ne l}({\bm{x}}_{l}^{T}{\bm{x}}_{i}{P}_{i}^{\ast}{g}_{il}+{n}_{l})}}\right)\right],\text{\hspace{0.05em}\hspace{0.05em}}l\in \U0001d4db\text{\hspace{0.05em}}.\end{array}$$The local implementation process is asynchronous. Each node (n) is responsible for assigning the optimal channels to some local links L_{n} ⊂ 𝓛 and periodically exchanges its individual channel usage x_{l}, ∀l ∈ L_{n}, and collected data λ_{l}, ∀l ∈ L_{n}, with all other nodes.B. Congestion-Aware Power Control Subproblem$$\begin{array}{l}{D}_{5}(\lambda )=\text{\hspace{0.05em}\hspace{0.05em}}\underset{\bm{P}}{\mathrm{max}}\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}{\displaystyle \sum _{l\in L}\text{\hspace{0.05em}\hspace{0.05em}}{\lambda}_{l}^{({s}^{*})}{C}_{l}(\bm{P})}\\ \text{s.\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}t.\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}0\le {\displaystyle {\sum}_{m\in {N}_{n}^{out}}{P}_{nm}\le {P}_{n}^{\mathrm{max}}},\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}\\ {C}_{l}(\bm{P})=B{\mathrm{log}}_{2}\left[1+\left(K\times \frac{{P}_{l}{g}_{ll}}{{\displaystyle {\sum}_{i\ne l}({\bm{x}}_{l}^{\ast}{}^{T}{\bm{x}}_{i}^{*}{P}_{i}{g}_{il}+{n}_{l})}}\right)\right],\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}l\in \U0001d4db\text{,}\end{array}$$where
𝒙 l ∗
, ∀l ∈ L_{n}, are obtained from solving the local channel allocation subproblem (20). Equation (21) can be solved distributively by the algorithm proposed in [17]. We describe it as follows.Step 1. At the iterative time slot t, the transmitter of link l ∈ 𝓛 calculates a power message$${m}_{l}(t)=\frac{{\lambda}_{l}{I}_{l}(t)}{{P}_{l}(t){g}_{ll}},$$where I_{l} denotes the signal-to-interference-plus-noise ratio; I_{l} and g_{ll} are measured locally.Step 2. The power message m_{l}(t) is passed to all the other nodes through a flooding protocol.Step 3. Each transmitter adjusts its power as$${P}_{l}(t+1)={P}_{l}(t)+\beta \left(\frac{{\lambda}_{l}(t)}{{P}_{l}(t)}-{\displaystyle \sum _{i\ne l}{g}_{il}{m}_{i}(t)}\right),$$where β > 0 is a constant step size.Step 4. Let t=t+1. Return to Step 1 until convergence.This algorithm is proved to converge to the global optimum solution
denote the set of links connecting to the jth interface of node m. For a bidirectional link 〈m, n〉, define λ_{＜m, n＞} = max{λ_{mn}, λ_{nm}} as the largest differential price. Assume that interface j ∈ m operates on channel i, which is pre-allocated by the local channel allocation algorithm. The distributed scheduling algorithm can be briefly described as follows.Each interface j ∈ m carries out the following steps:
A. Find neighborn*=argmaxn:(m,n)∈Lmjλ with free interfaceu, free channeli, and such that it satisfies(m,n*)=Lmj∩Ln*u.
• If having received the matching request from the interfaceuof noden*, then nodemaccepts link 〈m,n*〉 as a matched link and sends back a matched reply. At the same time, nodemsends a drop message about the interfacejand channelito all other neighbors with free interfaces and channels.• Otherwise, nodemsends a matching request to noden*.
B. Upon receiving a matching request information from neighborn, the following is carried out:
• Ifn=n*and channeliis free, then nodemaccepts the request and sends back a matched reply. At the same time, nodemsends a drop message about the interfacejand channelito all other neighbors with free interfaces and channels.• Otherwise, nodemjust stores the message.
C. Upon receiving information of a matched reply from neighborn, nodemsends a drop message about the interfacejand channelito all other neighbors with free interfaces and channels.
D. Upon receiving a drop message form neighborn, nodemupdates the free information of the interface and channel by deleting the interfacejand the channeli.
E. If nodemis busy or has no free neighbors, then it keeps the current state. Otherwise, it takes action according to the aforementioned steps A–D.
F. The matched links are allowed to transmit with the allocated rate
$${r}_{mq}^{(s)}=\{\begin{array}{l}{C}_{mq}({\bm{X}}^{\text{*}}\text{,}{\bm{P}}^{\text{*}})\text{\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}if\hspace{0.05em}\hspace{0.05em}\hspace{0.05em}}s={s}^{*},\\ \text{0\hspace{0.17em}\hspace{0.17em}otherwise.}\end{array}$$According to the above discussion, the main idea of this algorithm is to activate the local bidirectional link with the maximum differential price.
- 3. Distributed JCCRPSR
The proposed JCCRPSR can be described as follows:
A. The network topology is initially generated by using the Hyacinth algorithm in[8]andxl= [1 0 ··· 0], ∀l∈L, is set.
B. During each iteration time slott, the following three operations are carried out simultaneously:
• Each transmittern∈ 𝒩 updates the congestion priceξn={ξl,∀l∈Lnout}, power messagemn={ml,∀l∈Lnout}, and power priceζn={ζl,∀l∈Lnout}.• Each transmittern∈ 𝒩 sendsξlback to the source nodes of the flows if linklis on the paths of the flows.• Each transmitter passesmnto the corresponding transmitters by the routing protocol.
C. In the time slots that belong to the set ΓD.n, each noden∈ 𝒩 carries out the following algorithms at a period ofTDtime slots:
• If the node belongs to the source node of a flow, then the node updates thefs*according to equation (14).• Each node updates the local channel allocation according to (20) and informs the results to other nodes in the network.• Each transmitter updates the transmitted power according to equation (23).• Each nodenallocatesrnm(s) according to the scheduling algorithm. According to the rate offered by the scheduling, the routing is determined.
In JCCRPSR, each node calculates five parameters: congestion price (ξ_{n}), power message (m_{n}), power price (ζ_{n}), traffic rate (f_{s}), and transmitted power (P_{l}). The JCCRPSR then solves the local congestion-aware channel allocation subproblem and scheduling problem. For any node n ∈ 𝒩, the computational complexity of the parameters ξ_{n}, m_{n}, ζ_{n}, f_{s}, and P_{l} is linear. The local channel-allocation subproblem is a combinatorial optimization problem, with at most C^{Vmax} combinations, where V_{max} =
max n∈𝒩 | L n |
. The complexity of the scheduling problem is O(0.5L). So, the whole computational complexity is O(5 + C^{Vmax} + 0.5L).In addition, the convergence of the joint congestion control, routing, and scheduling algorithm is proved in [9]. The congestion-aware channel allocation algorithm can at least converge to the local optimal solutions. While the distributed power control subproblem can be solved with zero duality gap. So, the proposed distributed algorithm is guaranteed to be convergent. Since the congestion-aware channel allocation subproblem is sub-optimal, the global optimality of the proposed algorithm is not guaranteed. The sub-optimality and convergence of the proposed algorithm is investigated further in the next section.
IV. Simulation Results and Discussion
In this section, the proposed distributed JCCRPSR is compared with the joint congestion control, channel allocation, scheduling, and routing algorithm (JCCSR) in [11] and the centralized optimal algorithm. In the JCCSR, each node computes three parameters: two Lagrange multipliers and a traffic rate (f_{s}). It then computes both a local selfish channel allocation subproblem and a greedy centralized scheduling subproblem. The JCCRPSR and JCCSR algorithms are simulated using MATLAB, and the centralized algorithm is solved with MOSEK [19].In the simulation model, the size of the network field is 700 m × 700 m. Fifteen wireless nodes are generated randomly. The communication and interference ranges are 250 m and 450 m, respectively. Once the physical topology is created, a ripple effect–free logical topology can be formed by using the algorithm proposed in [8]. Two thousand time slots are simulated. The parameters used in the simulations are listed in Table 1.
The performance among the optimal, JCCSR, and JCCRPSR algorithms is firstly compared in terms of network utility and energy efficiency, which are defined as
∑ s∈S log f s
and
∑ s∈S f s / ∑ l∈𝓛 P l
, respectively.Figure 1 shows the evolution of the network utility. The number of NICs and non-overlapping channels is denoted by I and C, respectively. We can see that the JCCRPSR converges to a relatively stable value within a short time. The utility of the JCCRPSR with I = 2, C = 4, and I = 4, C = 6, reaches nearly 98.47% and 99.12% of the optimal values, respectively. Thus, the proposed JCCRPSR algorithm can lead to a near-optimal solution for the NUM problem. The utility of the JCCSR with I = 2, C = 4, and I = 4, C = 6, reaches 89.94% and 90.63% of the optimal values, respectively. It is obvious that the JCCRPSR shows better performance than the JCCSR. The reason for this is that, on the one hand, the JCCRPSR adjusts the transmit power to reduce the interference to the bottleneck links by a power control strategy, whereas on the other hand, the congestion-aware channel allocation strategy of the JCCRPSR takes congestion control and whole system capacity into consideration, while the channel allocation strategy of the JCCSR just tries to alleviate any local congestion.
Figure 2 shows the evolution of the energy efficiency. The JCCRPSR takes more time to converge to the suboptimal value compared to the JCCSR. However, the JCCRPSR with I = 2, C = 4 and I = 4, C = 6, converges to nearly 96.4% and 97.59% of the optimal values, respectively, while the JCCSR with I = 2, C = 4 and I = 4, C = 6, only converges to nearly 57.97% and 60.24% of the optimal values, respectively. This is because the JCCRPSR needs to coordinate the power for each lnk; hence, it takes more time to converge. Nonetheless, each node optimally adjusts the transmit power and hence the energy efficiency is improved.
To evaluate the impact of the maximum power constraints, we vary the maximum power constraint from 0.05 W to 1 W.Figure 3 shows the utility-power trade-off curves. As we can see from the figure, with the increasing of the maximum power constraint, the utilities of the JCCRPSR and JCCSR algorithms increase, and the network utility increments are decreasing. In addition, the proposed JCCRPSR algorithm achieves a better utility performance, since the JCCSR doesn’t have a power control strategy.
In this paper, we have studied the problem of joint congestion control, channel allocation, rate allocation, power control, scheduling, and routing with the consideration of fairness in multi-channel wireless multi-hop networks. A suboptimal distributed algorithm based on dual composition has been proposed. Simulation results have been presented to demonstrate the performance of the proposed scheme.For future work, we plan to extend our algorithm to a dynamic network environment, as well as considering the impact of outdated information or imperfect information to the resource allocation.
This work was supported by the National High Technology Research and Development Program of China (863 Program) (No. 2012AA050801).
BIO
Corresponding Author396843354@qq.comWei Feng received her MS and PhD degrees in communication and information systems from South China University of Technology, Guangzhou, China, in 2006 and 2014, respectively. Currently, she is a teacher at the School of Communication Engineering, Hangzhou Dianzi University, China. Her research interests are in the areas of resource allocation and routing in wireless mesh networks, and optimization theory and its applications in wireless networking.
f.wei08@mail.scut.edu.cnSuili Feng received his BS degree in communication and information systems from South China Institute of Technology (now, South China University of Technology) Guangdong, China, in 1982 and his MS and PhD degrees in communication and information systems from South China University of Technology, Guangdong, China, in 1989 and 1998, respectively. Currently, he is a professor at the School of Electronic & Information Engineering, South China University of Technology, Guangdong, China. His research interests include computer networks, digital signal processing, and wideband wireless communication.
zyzanis@vip.sina.comYongzhong Zhang received his BS degree in automatic control from Anhui University of Technology, Hefei, China, in 1993 and his MS degree in communication and information systems from South China University of Technology, Guangzhou, China, in 2003. He is currently working as an engineer at the No.7 Research Institution of China Electronics Technology Group Corporation, Guangdong, China. His research interests include ad hoc networks and mobile access networks.
xiaxw@hxdi.comXiaowei Xia received his BS degree in communication engineering from Beijing University of Posts and Telecommunications, China, in 2007. He is currently working as a chief engineer for Huaxin Consulting Co. Ltd., Hangzhou, Zhejiang, China. His research interests include computer networks and mobile access networks.
Nguyen M.V.
2012
“Optimal and Sub-optimal Resource Allocation in Multi-hop Cognitive Radio Networks with Primary User Outage Constraint,”
IET Netw.
1
(2)
47 -
57
DOI : 10.1049/iet-net.2011.0028
Lee J.
“Outage Probability of Cognitive Relay Networks with Interference Constraints,”
IEEE Trans. Wireless Commun.
10
(2)
390 -
395
DOI : 10.1109/TWC.2010.120310.090852
Chiang M.
“Balancing Transport and Physical Layers in Wireless Multi-hop Networks: Jointly Optimal Congestion Control and Power Control,”
IEEE J. Sel. Areas Commun.
23
(1)
104 -
116
DOI : 10.1109/JSAC.2004.837347
Rad A.H.M.
,
Wong V.W.S.
2006
“Joint Optimal Channel Assignment and Congestion Control for Multi-channel Wireless Mesh Networks,”
IEEE Int. Conf. Commun.
Istanbul, Turkey
1984 -
1989
DOI : 10.1109/ICC.2006.255061
Chen L.
“Cross-Layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless Networks,”
IEEE INFOCOM
Barcelona, Spain
Apr. 23–29, 2006
1 -
13
DOI : 10.1109/INFOCOM.2006.142
Galluccio L.
“Optimizing TCP Performance through Joint Channel Coding and Power Management in Power Constrained Satellite Networks,”
IEEE GLOBECOM
New Orleans, LO, USA
Nov. 30–Dec. 4, 2008
1 -
5
DOI : 10.1109/GLOCOM.2008.ECP.561
Merlin S.
,
Vaidya N.
,
Zorzi M.
“Resource Allocation in Multi-radio Multi-channel Multi-hop Wireless Networks,”
IEEE INFOCOM
Phoenix, AZ, USA
Apr. 13–18, 2008
610 -
618
DOI : 10.1109/INFOCOM.2008.110
Shin B.
2011
“Cross-Layer Resource Allocation with Multipath Routing in Wireless Multihop and Multichannel Systems,”
J. Commun. Netw.
13
(3)
221 -
231
DOI : 10.1109/JCN.2011.6157431
Cheung W.C.
,
Quek T.Q.S.
,
Kountouris M.
2012
“Throughput Optimization, Spectrum Allocation, and Access Control in Two-Tier Femtocell Networks,”
IEEE J. Sel. Areas Commun.
30
(3)
561 -
574
DOI : 10.1109/JSAC.2012.120406
Zhang L.
,
Zhou X.
2013
“Joint Cross-Layer Optimized Routing and Dynamic Power Allocation in Deep Space Information Networks under Predictable Contacts,”
IET Commun.
7
(5)
417 -
429
DOI : 10.1049/iet-com.2011.0419
@article{ HJTODO_2014_v36n6_960}
,title={Cross-Layer Resource Allocation in Multi-interface Multi-channel Wireless Multi-hop Networks}
,volume={6}
, url={http://dx.doi.org/10.4218/etrij.14.0113.1150}, DOI={10.4218/etrij.14.0113.1150}
, number= {6}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Feng, Wei
and
Feng, Suili
and
Zhang, Yongzhong
and
Xia, Xiaowei}
, year={2014}
, month={Oct}
TY - JOUR
T2 - ETRI Journal
AU - Feng, Wei
AU - Feng, Suili
AU - Zhang, Yongzhong
AU - Xia, Xiaowei
SN - 1225-6463
TI - Cross-Layer Resource Allocation in Multi-interface Multi-channel Wireless Multi-hop Networks
VL - 36
PB - Electronics and Telecommunications Research Institute
DO - 10.4218/etrij.14.0113.1150
PY - 2014
UR - http://dx.doi.org/10.4218/etrij.14.0113.1150
ER -
Feng, W.
,
Feng, S.
,
Zhang, Y.
,
&
Xia, X.
( 2014).
Cross-Layer Resource Allocation in Multi-interface Multi-channel Wireless Multi-hop Networks.
ETRI Journal,
36
(6)
Electronics and Telecommunications Research Institute.
doi:10.4218/etrij.14.0113.1150
Feng, W
,
Feng, S
,
Zhang, Y
,
&
Xia, X
2014,
Cross-Layer Resource Allocation in Multi-interface Multi-channel Wireless Multi-hop Networks,
ETRI Journal,
vol. 6,
no. 6,
Retrieved from http://dx.doi.org/10.4218/etrij.14.0113.1150
[1]
W Feng
,
S Feng
,
Y Zhang
,
and
X Xia
,
“Cross-Layer Resource Allocation in Multi-interface Multi-channel Wireless Multi-hop Networks”,
ETRI Journal,
vol. 6,
no. 6,
Oct
2014.
Feng, W
,
Feng, S
,
Zhang, Y
,
Xia, X
Cross-Layer Resource Allocation in Multi-interface Multi-channel Wireless Multi-hop Networks.
ETRI Journal
[Internet].
2014.
Oct ;
6
(6)
Available from http://dx.doi.org/10.4218/etrij.14.0113.1150