A Systematic Design Method for Large-Scale Wireless Ad Hoc Network Protocol Based on Optimization Decomposition Theory

Abstract

The idea of network protocol design based on optimization theory has been proposed and used practically in Internet for about 15 years. However, for large-scale wireless ad hoc network, although protocol could be viewed as a recursive solving of a global optimization problem, protocol design is still facing huge challenge because an effective distributed algorithm for solving global optimization problem is still lacking. We solve the problem by putting forward a systematic design method based on optimization decomposition. The systematic method includes primal decomposition method and dual decomposition method, with which a complex optimization problem can be decomposed into several smaller and independent optimization subproblems. By using subgradient method, each of these subproblems can be solved distributively. Further, the above two methods can be combined in different sequences or used recursively to solve more complex optimization problems. Two examples of wireless protocol design, the transmission control protocol and the joint congestion control and power control protocol, are given to demonstrate its validity.

1. Introduction

Optimization method has been explicitly and widely applied in Internet and especially become an important approach to guide the network protocol design. It has been found that the interaction process of network protocol could be viewed as a process of solving a global optimization problem, which has resulted in a new perspective for the design method of network protocol. As the first paper in this field, Kelly et al. introduced this new perspective with the research object of transmission control protocol (TCP) in 1998 [1]. The perspective brought people a theoretical model for TCP mechanism; thus new TCP protocols came into being, such as TCP Reno and TCP Vegas. Since then, people began to cognize and design network protocol via the thought of optimization methods.

The design method is suitable for wireline network but the large-scale ad hoc network. The reason is as follows. To solve a global optimization problem, global information is inevitably needed; in other words, the solving process must be executed in an almighty node, which can get any necessary information at any moment. It is very easy in wireline network because of its powerful communication capability. For the large-scale wireless ad hoc network, it is impossible since it is very difficult to get information from nodes far away because of its weak communication capability. Thus, if the design perspective is still kept in large-scale wireless ad hoc network, a distributed optimization algorithm for solving global optimization problem is indispensable, which can solve a global optimization problem only by communication among neighbor nodes.

In this paper, we put forward a systematic design method based on optimization decomposition. The systematic method includes primal decomposition method and dual decomposition method, with which a complex optimization problem can be decomposed into several smaller and independent optimization subproblems. By using subgradient method, each of these subproblems can be solved distributively. Further, the above two methods can be combined in different sequences or used recursively to solve more complex optimization problems.

Two examples of wireless protocol design (one is the transmission control protocol of single-layer and the other is the joint congestion control and power control protocol of cross-layer) are given to demonstrate its validity.

The organization of this paper is as follows. Section 2 is related works. In Section 3, we introduced the optimization decomposition theory. In Section 4, two design examples are introduced. Simulation experiment is given in Section 5, and the last section is conclusions.

2. Related Works

The design of wireless network protocol is more difficult comparing with its wireline counterpart. Because wireless transmission has the characteristics of signal attenuation and interference, the complex interference among wireless links causes the tight coupling among the network protocol layers. Power control on the physical layer, for example, has direct influence on the congestion control of the transport layer, so it is difficult to make a clear division of network protocol layers for wireless network. Thus, the traditional hierarchical model is no longer valid, and the traditional design method does not work either. What is more, the traditional network design methodology focuses on referencing the existing protocols to engineering projects and lacks the support of design theory, so obtaining satisfactory results for complex wireless network is difficult.

Obviously, it seems to be a good choice of using the theory of optimization method to guide the wireless network protocol design. In this way, characteristics of each layer can be viewed as a uniform constraint set; thereby, the final protocol may not have clear stratification. This feature is very suitable for the characteristics of the wireless network. Therefore, according to the idea of optimization protocol design put forward by Kelly, methods of cross-layer scheduling design combined with multiple factors such as routing, congestion, MAC, power, and adjustable rate appeared in study of the wireless network in recent years. And the cross-layer design method is playing an increasingly important role for improving performance of wireless networks [2]. For example, Lin and Shroff proposed a dual optimization algorithm which jointed rate control and scheduling together, and the algorithm could fully utilize the capacity of the wireless network [3]. Based on network utility maximization (NUM) model [4], Chiang et al. put forward a cross-layer distributed algorithm for power control combining with the TCP [5]. Nama et al. applied the NUM model to optimize power of node [6]. Fu et al. proposed a fast algorithm for joint power control and scheduling [7]. Papandriopoulos et al. presented optimal cross-layer protocols of rate and power control in condition of high SNR. However, these cross-layer designs seem to be disorganized and lack theoretical representation [8], and the practicability of these cross-layer protocols is thus often based on some specific network models which lack universality.

Literature [9] systematically answered some questions seemingly simple about the design of wireless network protocol, which includes whether wireless network protocols need stratification or not, which layers are they divided into, what the function of each layer is, and how the interaction works among these layers. The author proposed the idea of “layering as optimization decomposition.” Its core idea is that network protocol layering should be determined by mathematical results of distributed decomposition of optimization problems. However, the author only focused on the decomposition of problems and did not summarize a universal method for distributed protocol design of wireless network.

3. Optimization Decomposition Theory

We focus on how to solve a global optimization problem distributively.

When both objective function and constraints are linear functions, the problem is a linear optimization problem. In a similar way, when the objective function and constraints are nonlinear, the problem is a nonlinear optimization problem. Particularly, when the objective function and constraints are both convex functions, the problem becomes the convex optimization problem.

There are mature solutions to the above problems; however, most of the existing solutions are centralized. If the optimization problem is solved via a centralized way, each node needs to send related information to base station, and then the base station sends back the solutions to each node after solving the optimization problem in traditional methods, such as gradient method, conjugate gradient method, and feasible direction method. Thus, the mentioned methods above are not suitable for large-scale wireless network because of the restriction of bandwidth, energy consumption, and scalability. So it is necessary to find distributed methods to solve this kind of optimization problems.

Whether an optimization problem could be solved distributively depends on the structure of the problem. Some problems have obviously decomposable structure but they are rare in practice. There are two factors, complex variables and complex constraints, which result in difficulty in optimization decomposition. We employ primal decomposition method and dual decomposition method to deal with them, respectively.

3.1. Primal Decomposition

We consider the following optimization problem:

$$\begin{array}{cc}& \underset{x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_k,x_{k+\mathrm{1}},\dots ,x_n,y}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{\displaystyle \sum }_{i=\mathrm{1},\dots ,k}{f}_i\left(x_i,y\right)+{\displaystyle \sum }_{i=k+\mathrm{1},\dots ,n}{f}_i\left(x_i\right)\\ \text{s.t.}\hspace{1em}{x}_i\in C_i\left(i=\mathrm{1,2},\dots ,n\right).\end{array}$$

(1)

Once the value of y is determined, problem above is obviously decomposable, so y is referred to as complex variable.

Problem with objective function containing complex variable is usually solved via primal decomposition method.

Lemma 1.

One has ${\max }_{x,y}f\left(x,y\right)={\max }_y\hspace{0.17em}{\max }_x\hspace{0.17em}f\left(x,y\right)$ .

According to Lemma 1, (1) can be decomposed into n subproblems with constraints

$$\begin{array}{cc}& {\Phi }_i\left(y\right)=\underset{x_i}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{f}_i\left(x_i,y\right)\\ \text{s.t.}\hspace{1em}{x}_i\in C_i\left(i=\mathrm{1,2},\dots ,k\right)\end{array}$$

(2)

$\begin{array}{cc}& {\Phi }_i\left(y\right)=\underset{x_i}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{f}_i\left(x_i\right)\\ \text{s.t.}\hspace{1em}{x}_i\in C_i\left(i=k+\mathrm{1},\dots ,n\right)\end{array}$

(3)

and a master optimization problem with no constraints. The master problem is used to determine the optimal value of y:

$$\begin{array}{cc}& \underset{y}{\max }{\displaystyle \sum }_{i=\mathrm{1},\dots ,k}{\Phi }_i\left(y\right).\end{array}$$

(4)

Obviously, all subproblems in (2) and (3) are completely independent and can be solved, respectively. While the master optimization problem is not distributed in mathematical view, if all $x_i\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},\dots ,k)$ are in a local area but not the global area, the master optimization problem can still be solved in distributed manner. We are very lucky that most of the models for protocol design in wireless network belong to the case.

From the view of economics, when y is regarded as a public resource, the solution of master optimization problem provides a supply quantity to the public resource, and k suboptimization problems calculate their own maximum benefit, respectively, after the public resource transmitting to them. Then the master optimization problem adjusts value of y again according to feedback from k suboptimization problems. As iteration proceeds, the maximum total efficiency and the values of $x_i\hspace{0.17em}\hspace{0.17em}\left(i=\mathrm{1,2},\dots ,n\right)$ and y can be gotten.

3.2. Dual Decomposition

We consider the following optimization problem with constraints:

$$\begin{array}{cc}& \underset{x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_n,y}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{\displaystyle \sum }_{i=\mathrm{1},\dots ,k,k+\mathrm{1},\dots ,n}{f}_i\left(x_i\right)\\ \text{s.t.}\hspace{1em}{x}_i\in C_i\left(i=\mathrm{1,2},\dots ,n\right)\\ \hspace{1em}{\displaystyle \sum }_{i=\mathrm{1,2},\dots ,k}{h}_i\left(x_i\right)\ge 0.\end{array}$$

(5)

The problem above has distributed solution if there is no constraint of ${\sum }_{i=\mathrm{1,2},\dots ,k}^{}{h}_i\left(x_i\right)\ge 0$ . So the constraint is called complex constraint. We usually use method of Lagrange duality to deal with complex constraint.

Definition 2.

We define the Lagrange function of optimization problem (5) as

$$\begin{array}{l}L\left(x_{\mathrm{1}},\dots ,x_n,\lambda \right)={\displaystyle \sum }_{i=\mathrm{1},\dots ,n}{f}_i\left(x_i\right)+\lambda {\displaystyle \sum }_{i=\mathrm{1},\dots ,k}{h}_i\left(x_i\right)\\ ={\displaystyle \sum }_{i=\mathrm{1},\dots ,k}\left(f_i\left(x_i\right)+\lambda h_i\left(x_i\right)\right)\\ +{\displaystyle \sum }_{i=k+\mathrm{1},\dots ,n}{f}_i\left(x_i\right)\end{array}$$

(6)

and its Lagrange dual problem as

$$\begin{array}{cc}& \underset{\lambda \ge \mathrm{0}}{\mathrm{m}\mathrm{i}\mathrm{n}}\underset{x_{\mathrm{1}},\dots ,x_n}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}L\left(x_{\mathrm{1}},\dots ,x_n,\lambda \right)\\ \text{s.t.}\hspace{1em}{x}_i\in C_i\left(i=\mathrm{1,2},\dots ,n\right).\end{array}$$

(7)

Lemma 3.

If Slater condition holds, the primal problem and its dual problem have the same optimal solution for a convex optimization problem.

Thus the optimization problem (5) can be solved by solving its dual problem equivalently. And Lagrange dual problem can be decomposed into n suboptimization problems

$$\begin{array}{cc}& {\Phi }_i\left(\lambda \right)=\underset{x_i}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}\left(f_i\left(x_i\right)+\lambda h_i\left(x_i\right)\right)\\ \text{s.t.}\hspace{1em}{x}_i\in C_i\left(i=\mathrm{1,2},\dots ,k\right)\\ {\Phi }_i\left(y\right)=\underset{x_i}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{f}_i\left(x_i\right)\end{array}$$

(8)

$\begin{array}{cc}& \text{s.t.}\hspace{1em}{x}_i\in C_i\left(i=k+\mathrm{1},\dots ,n\right)\end{array}$

(9)

and one master optimization problem. The master optimization problem is used to determine the optimal value of λ:

$$\begin{array}{cc}& \underset{\lambda \ge 0}{\min }{\displaystyle \sum }_{i=\mathrm{1,2},\dots ,k}{\Phi }_i\left(\lambda \right).\end{array}$$

(10)

From the view of economics, when λ is regarded as price of constraints (or shadow price), the solution of master optimization problem provides the price, and k suboptimization problems calculate their own maximum benefit, respectively, under the price. Then the master optimization problem adjusts value of λ again according to feedback from k suboptimization problems. We can get the maximum total efficiency and values of $x_i\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},\dots ,n)$ as iteration proceeds.

Like primal decomposition, while the master optimization problem is not distributed in mathematical view, if all $x_i\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},\dots ,k)$ are in a local area but not the global area, the master optimization problem can still be solved in distributed manner.

Problems of layering a network are equivalent to the vertical decomposition of a convex optimization problem via the method of dual decomposition [10], and the suboptimization problems are representative of different layers of the network.

3.3. Subgradient Method

Both primal decomposition and dual decomposition are easy to solve (e.g., gradient method and Newton method) because their subproblems have specific expressions. However, the expressions of the master problems are not clear; it is difficult in calculating gradient and solving problems in traditional methods. Subgradient method is suitable for the case where the optimization expression is not clear.

Definition 4.

Vector g denotes a subgradient of function $f(x)$ at x if $f\left(y\right)\ge f\left(x\right)+g^T\left(y-x\right)$ , $\forall y$ .

Obviously, the subgradient of function $f(x)$ at x is not unique.

Definition 5.

The set of all the subgradients of function $f(x)$ at x is called the subdifferential of function $f\left(x\right)$ at x, denoted as $\partial f(x)$ .

Property 1.

If $f(x)$ is a convex function and differentiable, the gradient of $f(x)$ at t satisfies $\nabla f(t)\in \partial f(t)$ .

Property 2.

If $g_1\left(x\right)\in \partial f_{\mathrm{1}}\left(x\right)$ , $g_2\left(x\right)\in \partial f_{\mathrm{2}}\left(x\right)$ hold, $g_{\mathrm{1}}\left(x\right)+g_2\left(x\right)\in \partial (f_{\mathrm{1}}\left(x\right)+f_{\mathrm{2}}\left(x\right))$ holds.

For an optimization problem, once a subgradient of object function is gotten, the optimal solution can be computed iteratively.

Let f be the object function, and we solve the minimum value of f by iteration

$$\begin{array}{cc}& x^{\left(k+\mathrm{1}\right)}=x^{\left(k\right)}-a_k{g}^{\left(k\right)},\end{array}$$

(11)

where $x^{(k)}$ is the value of x and $a_k$ is the step size in the kth iteration and $g^{(k)}$ denotes a subgradient of f at $x^{(k)}$ .

The iteration step sizes in subgradient method are determined “offline,” and there are many different types of step size rules, including constant step size, constant step length, square summable but not summable step, and nonsummable diminishing step. Readers can refer to [11] for further explanation.

Now, the focus is how to calculate a subgradient for master optimization problem. Theorems 6 and 8 are used to get a subgradient of a maximal or minimal function.

Theorem 6.

$h\left(x^{\ast }\left({\lambda }_0\right)\right)$ is a subgradient of function $g\left(\lambda \right)={\min }_x(f\left(x\right)+{\lambda }^{T}h(x))$ at ${\lambda }_0$ , where $f\left(x\right)+{\lambda }^{T}h(x)$ gets its minimum at $x^{\ast }(\lambda )$ .

Proof.

For any ${\lambda }_1$ ,

$$\begin{array}{l}g\left({\lambda }_{\mathrm{1}}\right)\ge f\left(x^{\ast }\left({\lambda }_{\mathrm{0}}\right)\right)+{{\lambda }_{\mathrm{1}}}^{T}h\left(x^{\ast }\left({\lambda }_{\mathrm{0}}\right)\right)\\ =f\left(x^{\ast }\left({\lambda }_{\mathrm{0}}\right)\right)+{{\lambda }_{\mathrm{0}}}^{T}h\left(x^{\ast }\left({\lambda }_{\mathrm{0}}\right)\right)\\ +{\left({\lambda }_{\mathrm{1}}-{\lambda }_{\mathrm{0}}\right)}^{T}h\left(x^{\ast }\left({\lambda }_{\mathrm{0}}\right)\right)\\ =g\left({\lambda }_{\mathrm{0}}\right)+{\left({\lambda }_{\mathrm{1}}-{\lambda }_{\mathrm{0}}\right)}^{T}h\left(x^{\ast }\left({\lambda }_{\mathrm{0}}\right)\right).\end{array}$$

(12)

Lemma 7.

$-h(x^{\ast }({\lambda }_0))$ is a subgradient of function $g\left(\lambda \right)={\max }_x(f\left(x\right)+{\lambda }^{T}h(x))$ at ${\lambda }_{\mathrm{0}}$ .

Theorem 6 and Lemma 7 are mainly used in dual decomposition. Based on Property 2, a subgradient of master optimization problem (10) can be gotten by Theorem 6 and Lemma 7.

Theorem 8.

$-{\lambda }^{\ast }\left(y_0\right)$ is a subgradient of convex optimization function $f^{\ast }\left(y\right)={\min }_{x}f\left(x\right)$ , s.t.   $f\left(x\right)\le y$ at $y_0$ , where $f(x)$ is concave, $h(x)$ is convex, $\lambda \left(y\right)\ge 0$ , and ${\lambda }^{\ast }(y)$ is the optimal dual for the convex optimization function with parameter y.

Proof.

Since it is a convex optimization problem,

$$\begin{array}{l}{f}^{\ast }\left(y_{\mathrm{0}}\right)=f\left(x^{\ast }\left(y_{\mathrm{0}}\right)\right)\le f\left(x\right)+{{\lambda }^{\ast }\left(y_{\mathrm{0}}\right)}^T\left(h\left(x\right)-y_{\mathrm{0}}\right)\\ \forall x\\ =f\left(x\right)+{{\lambda }^{\ast }\left(y_{\mathrm{0}}\right)}^T\left(h\left(x\right)-y\right)\\ +{{\lambda }^{\ast }\left(y_{\mathrm{0}}\right)}^T\left(y-y_{\mathrm{0}}\right)\forall y\\ \le f\left(x\right)+{{\lambda }^{\ast }\left(y_{\mathrm{0}}\right)}^T\left(y-y_{\mathrm{0}}\right)\\ \left(\forall x,y\text{\hspace{0.17em}\hspace{0.17em}are\hspace{0.17em}\hspace{0.17em}satisfied\hspace{0.17em}\hspace{0.17em}with\hspace{0.17em}\hspace{0.17em}}h\left(x\right)\le y\right).\end{array}$$

(13)

Now we employ a special value $\acute{x}$ :

$$\begin{array}{cc}& \acute{x}=\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}\hspace{1em}f\left(x\right)\\ \text{s.t.}\hspace{1em}h\left(x\right)\le y\end{array}$$

(14)

and then

$$\begin{array}{l}{f}^{\ast }\left(y_{\mathrm{0}}\right)\le f\left(\acute{x}\right)+{{\lambda }^{\ast }\left(y_{\mathrm{0}}\right)}^T\left(y-y_{\mathrm{0}}\right)\\ =f^{\ast }\left(y\right)+{{\lambda }^{\ast }\left(y_{\mathrm{0}}\right)}^T\left(y-y_{\mathrm{0}}\right).\end{array}$$

(15)

Lemma 9.

${\lambda }^{\ast }\left(y_{\mathrm{0}}\right)$ is a subgradient of function $f^{\ast }\left(y\right)={\max }_x\hspace{0.17em}f\left(x\right)$ , s.t.   $h\left(x\right)\le y$ at $y_{\mathrm{0}}$ .

Theorem 8 and Lemma 9 are mainly used in primal decomposition. Based on Property 2, a subgradient of master optimization problem (4) can be gotten by Theorem 8 and Lemma 9.

4. Two Design Examples

We give two design examples using the systematic design method to verify its validity.

4.1. Problem Formulation

4.1.1. Single-Layer Design: Transmission Control Protocol

We consider a wireless network with N nodes and L links, where source node s uses link $l\in L(s)$ . Let $S\left(l\right)$ denote the set of source nodes which use link l. If $S\left(l\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\forall l$ is given, it actually defines $L\times N$ routing matrix R. The element of R is defined as follows:

$$\begin{array}{cc}& R_{ls}=\left\{\begin{array}{cc}\mathrm{1}\hfill & l\in L\left(s\right),\text{\hspace{0.17em}\hspace{0.17em}the\hspace{0.17em}\hspace{0.17em}source\hspace{0.17em}\hspace{0.17em}node\hspace{0.17em}\hspace{0.17em}}s\text{\hspace{0.17em}\hspace{0.17em}uses\hspace{0.17em}\hspace{0.17em}link\hspace{0.17em}\hspace{0.17em}}l,\hfill \\ \mathrm{0}\hfill & \text{otherwise.}\hfill \end{array}\right.\end{array}$$

(16)

We assume that the link capacity assignment $C={(c_1,c_2,\dots ,c_L)}^T$ is known. Let $X={(x_1,x_2,\dots ,x_N)}^T$ be the source rate assignment.

Let $U_s(x_s)$ denote the utility when s sends data at rate $x_s$ , and it reflects the satisfaction level of user s when it sends data at a certain rate. The design object for our transmission control protocol is to maximize the sum of sources' utility by finding the optimal X.

Then transmission control protocol is formulated as the following global optimization problem:

$$\begin{array}{cc}& \underset{X}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{\displaystyle \sum }_s{U}_s\left(x_s\right)\\ \text{s.t.}\hspace{1em}RX\le C.\end{array}$$

(17)

Generally, the utility function $U_s(x_s)$ is increasing and is strictly concave. It has different forms according to the different definition of satisfaction level of users. One of its popular definitions is

$$\begin{array}{cc}& U_s\left(x_s\right)=\left\{\begin{array}{cc}{w}_s\log x_s\hfill & {\alpha }_s=\mathrm{1},\hfill \\ w_s{\left(\mathrm{1}-{\alpha }_s\right)}^{-\mathrm{1}}{x_s}^{\mathrm{1}-{\alpha }_s}\hfill & {\alpha }_s\ne \mathrm{1}.\hfill \end{array}\right.\end{array}$$

(18)

4.1.2. Cross-Layer Design: Joint Congestion Control and Power Control Protocol

We consider a joint congestion control and power control protocol as the second example. We still assume that the routing matrix R is known in advance.

Distinct from the above example, the capacity of link is not fixed in this example. We assume that the capacity of a link is only associated with the transmit power of its source node. So the link capacity $c_l(p_l)$ is a nonlinear function of the transmit power $p_l$ .

In order to prevent too large transmit power, which may take adverse effects on other links, a constraint of maximal summed transmit power is added in this example (it is indeed necessary for CDMA cellular network). Thus, the joint congestion control and power control protocol is modeled as follows:

$$\begin{array}{cc}& \underset{X}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{\displaystyle \sum }_s{U}_s\left(x_s\right)\\ \text{s.t.}\hspace{1em}{\displaystyle \sum }_{s:l\in L\left(s\right)}{x}_s\le c_l\left(p_l\right)\forall l.\end{array}$$

(19)

The protocol we designed is trying to find the optimal solution $(x^{\ast },p^{\ast })$ for the above optimization problem distributively.

4.2. Solutions of Examples

Now we solve the two examples using method we suggest.

4.2.1. Solution of Transmission Control Protocol

For optimization problem (17), the only constraint is a complex constraint, so we use the duality decomposition method to solve the problem. We associate a Lagrange multiplier for each constraint,

$$\begin{array}{l}L\left(x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_N;{\lambda }_{\mathrm{1}},{\lambda }_{\mathrm{2}},\dots ,{\lambda }_L\right)\\ ={\displaystyle \sum }_s{U}_s\left(x_s\right)+{\displaystyle \sum }_l{\lambda }_l\left(c_l-x_s{R}_{ls}\right)\\ ={\displaystyle \sum }_s\left(U_s\left(x_s\right)-x_s{\displaystyle \sum }_l{R_{ls}\lambda }_l\right)+{\displaystyle \sum }_l{c_l\lambda }_l.\end{array}$$

(20)

The dual objective function is

$$\begin{array}{cc}& \underset{\lambda \ge \mathrm{0}}{\min }\hspace{0.17em}L\left(x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_N;{\lambda }_{\mathrm{1}},{\lambda }_{\mathrm{2}},\dots ,{\lambda }_L\right).\end{array}$$

(21)

So it can be decomposed as N subproblems

$$\begin{array}{l}{\Phi }_s\left(\lambda \right)=\underset{x_s}{\max }\left(U_s\left(x_s\right)-x_s{\displaystyle \sum }_l{R}_{ls}{\lambda }_l\right)\\ s=\mathrm{1,2},\dots ,N\end{array}$$

(22)

and one master problem

$$\begin{array}{cc}& \underset{\lambda \ge 0}{\min }{\displaystyle \sum }_s{\Phi }_s\left(\lambda \right)+{\displaystyle \sum }_l{c_l\lambda }_l.\end{array}$$

(23)

Since the suboptimization problem is local and its analytic expression is known, it can be solved by using all kinds of linear or nonlinear methods, which depends on properties of the function $U_s\left(x_s\right)$ , while, for the master optimization problem, we use subgradient method. One of its subgradients at λ is ${\left(c_1-{\sum }_s{R}_{1s}{x}_s^{\ast }\left(\lambda \right),c_2-{\sum }_s{R}_{2s}{x}_s^{\ast }\left(\lambda \right),\dots ,c_L-{\sum }_s{R}_{Ls}{x}_s^{\ast }\left(\lambda \right)\right)}^T$ , where $x_s^{\ast }\left(\lambda \right)$ is the optimal solution of the corresponding subproblem. Then the master problem can be solved via iteration as follows:

$$\begin{array}{l}{{\lambda }_l}^{\left(k+\mathrm{1}\right)}={\left[{{\lambda }_l}^{\left(k\right)}-a^{\left(k\right)}\left(c_l-{\displaystyle \sum }_s{R}_{ls}{x}_s^{\ast }\left(\lambda \right)\right)\right]}_{+}\\ l=\mathrm{1,2},\dots ,L,\end{array}$$

(24)

where ${[x]}_{+}$ denotes a projection that if x is less than or equal to zero, we make it be zero, and if it is a positive number, we retain the value. The projection is to ensure that λ should not be negative.

According to the thought above, node i operates in terms of process of the protocol. And we can get the final optimum rate after several iterations. The whole transmission control protocol can be represented as shown in Algorithm 1.

Algorithm 1

//Given ε, $${{\lambda }_i}^{(0)}$$

$$k=-1$$ ;

repeat

   $$k=k+1$$ ;

  The source node of link i collects $$x_s^{\ast }({\lambda }^{(k)})$$ of nodes in $$S(i)$$ , and updates its $${{\lambda }_i}^{(k+1)}$$ according to (24).

  The source node s collects $${{\lambda }_i}^{(k+1)}$$ of links in $$L(s)$$ , solves the optimal solution $$x_s^{\ast }({\lambda }^{(k+1)})$$ .

until ( $$\left|x_s^{\ast }\left({\lambda }^{\left(k+1\right)}\right)-x_s^{\ast }({\lambda }^{(k)})\right|<\epsilon$$ )

$${\lambda }^{(k)}={\lambda }^{(k+1)}$$ ;

4.2.2. Solutions of Joint Congestion Control and Power Control Protocol

We can draw a conclusion from Section 3 that to decompose a constraint needs one decomposition procedure. Thus, when there are multiple constraints, we need to do multiple decompositions. And astonishingly, we could even get different protocols with different sequences of decomposition. For the joint congestion control and power control protocol, we present two types of decomposition sequences, primal-dual decomposition and dual-dual decomposition.

(A) Primal-Dual Decomposition. In the optimization model (19), P is a complex variable, so primal decomposition method can be used. Thus, the problem can be decomposed as follows.

The suboptimization problem (congestion control) is as follows:

$$\begin{array}{cc}& U^{\ast }\left(P\right)=\underset{x_s}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{\displaystyle \sum }_s{U}_s\left(x_s\right)\\ \text{s.t.}\hspace{1em}{\displaystyle \sum }_{s:l\in L\left(s\right)}{x}_s\le c_l\left(p_l\right)\forall l\end{array}$$

(25)

and the master optimization problem (power control) is as follows:

$$\begin{array}{cc}& \mathrm{m}\mathrm{a}\mathrm{x}\hspace{1em}{U}^{\ast }\left(P\right)\\ \text{s.t.}\hspace{1em}{\displaystyle \sum }_l{p}_l\le P_T.\end{array}$$

(26)

The suboptimization problem (25) can be further decomposed by dual decomposition method, which is similar to Section 4.2.1, and it is further decomposed as N subproblems

$$\begin{array}{l}{\Phi }_s\left(\lambda \right)=\underset{x_s}{\max }\left(U_s\left(x_s\right)-x_s{\displaystyle \sum }_{l\in L\left(s\right)}{c}_l\left(p_l\right){\lambda }_l\right)\\ s=\mathrm{1,2},\dots ,N\end{array}$$

(27)

and one master problem

$$\begin{array}{cc}& \underset{\lambda \ge \mathrm{0}}{\min }{\displaystyle \sum }_s^{}{\Phi }_s\left(\lambda \right).\end{array}$$

(28)

Thus, a subgradient of $U^{\ast }\left(P\right)$ at P can be deducted using decomposite function as ${\left[{\lambda }_{\mathrm{1}}^{\ast }\left(P\right)c_{\mathrm{1}}^{\prime }\left(P_{\mathrm{1}}\right),{\lambda }_{\mathrm{2}}^{\ast }\left(P\right)c_{\mathrm{2}}^{\prime }\left(P_{\mathrm{2}}\right),\dots ,{\lambda }_L^{\ast }\left(P\right)c_L^{\prime }\left(P_L\right)\right]}^T$ , where $c_l^{\prime }\left(P_l\right)$ is the derivative.

To solve the mater optimization problem using dual decomposition method, we need to obtain a subgradient of $U^{\ast }\left(P\right)$ under constraints ${\sum }_l{p}_l\le P_T$ . But it is very difficult to obtain. So we employ subgradient projection method [12]. First, we get a subgradient of $U^{\ast }\left(P\right)$ at P. Then, we make a projection of the subgradient to constraints ${\sum }_l{p}_l\le P_T$ . The projection is a subgradient of (26).

Thus, the master optimization problem updates its power value as the following iteration:

$$\begin{array}{l}{P}^{(k+1)}=[P^{(k)}+\alpha [{\lambda }_1^{*}(P)c_1^{\text{'}}(P_1),{\lambda }_2^{*}(P)\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{{\cdot c_2^{\text{'}}(P_2),\dots ,{\lambda }_L^{*}(P)c_L^{\text{'}}(P_L)]}^T]}_{\Omega },\hfill \end{array}$$

(29)

where ${[\hspace{0.17em}]}_{\Omega }$ denotes the projection on the convex set $\Omega =\left\{P:P\ge 0,{\sum }_l{p}_l\le P_T\right\}$ .

For the suboptimization problem (25), it is similar to problem (17) and can be further decomposed by dual decomposition. Thus the joint congestion control and power control protocol can be represented as Algorithm 2, which is executed synchronously. For clearance, we describe the algorithm centralized, although it could be realized distributively.

Algorithm 2

//Given $${\epsilon }_1$$ , $${\epsilon }_2$$ , P, $$\lambda (P^{(0)})$$

$$k=-1$$ ;

repeat

   $$k=k+1$$ ;

  Send P to all other nodes.

  For each node i, calls Algorithm 1 with parameters ( $${\epsilon }_1$$ , $${\lambda }_i^{\ast }(P^{(k)})$$ ).

  Collect all $${\lambda }_l^{\ast }(P^{(k)})$$ and update $$P^{(k+1)}$$ according to (29).

until ( $$\left|P^{(k+1)}-P^{(k)}\right|<{\epsilon }_2$$ )

(B) Dual-Dual Decomposition. We can decompose problem (19) in another way. First, we use dual decomposition method to decompose the problem.

The suboptimization problem includes

$$\begin{array}{l}{\Phi }_s\left(\lambda \right)=\underset{x_s}{\max }\left(U_s\left(x_s\right)-\left({\displaystyle \sum }_{l\in L\left(s\right)}^{}{\lambda }_l\right)x_s\right)\\ s=\mathrm{1,2},\dots ,N,\end{array}$$

(30)

$\begin{array}{cc}& H\left(\lambda \right)=\underset{p_l}{\mathrm{m}\mathrm{a}\mathrm{x}}\hspace{1em}{\displaystyle \sum }_l^{}\left({\lambda }_l{c}_l\left(p_l\right)\right)\\ \text{s.t.}\hspace{1em}{\displaystyle \sum }_l^{}{p}_l\le P_T.\end{array}$

(31)

The master optimization problem is as follows:

$$\begin{array}{cc}& \underset{\lambda \ge \mathrm{0}}{\min }\left(\left({\displaystyle \sum }_{s=\mathrm{1,2},\dots ,N}{\Phi }_s\left(\lambda \right)\right)+H\left(\lambda \right)\right).\end{array}$$

(32)

According to Lemma 7, a subgradient of subproblem (30) at λ is a vector ${(e_1,e_2,\dots ,e_L)}^T$ , where

$$\begin{array}{cc}& e_i=\left\{\begin{array}{cc}{x}_s^{\ast }\left({\lambda }_i\right)\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}i\in L\left(s\right),\hfill \\ 0\hfill & \text{else}.\hfill \end{array}\right.\end{array}$$

(33)

For subproblem (31), its constraint has no effect on variable λ; thus, a subgradient at λ is the negative derivative of λ, that is, $-{(c_1\left(p_1\right),c_2\left(p_2\right),\dots {,c}_L\left(p_L\right))}^T$ .

Thus, a subgradient of the master optimization problem at ${\lambda }_l$ is $c_l\left(p_l\right)-{\sum }_{s\in S(l)}{x}_s^{\ast }\left({\lambda }_l\right)$ for any $l\in [\mathrm{1,2},\dots ,L]$ .

Thus, the master optimization problem updates its “shadow price” as the following iteration:

$$\begin{array}{l}{{\lambda }_l}^{\left(k+\mathrm{1}\right)}={\left[{{\lambda }_l}^{\left(k\right)}-\alpha \left(c_l\left(p_l\right)-{\displaystyle \sum }_{s\in S\left(l\right)}{x}_s^{\ast }\left({{\lambda }_l}^{\left(k\right)}\right)\right)\right]}_{+}\\ \forall l\in \left[\mathrm{1,2},\dots ,L\right].\end{array}$$

(34)

The suboptimization problem (31) is not distributed, so dual decomposition method is employed again to decompose it as follows.

Its suboptimization problem is as follows:

$$\begin{array}{cc}& {\widehat{H}}_l\left({\gamma }_l\right)=\underset{p_l}{\max }\left(c_l\left(p_l\right){\lambda }_l-{\gamma }_l{p}_l\right)\forall l\in \left[\mathrm{1,2},\dots ,L\right],\end{array}$$

(35)

and its master optimization problem is as follows:

$$\begin{array}{cc}& \min \left({\displaystyle \sum }_l{\widehat{H}}_l\left({\lambda }_l\right)+{\gamma }_l{P}_T\right).\end{array}$$

(36)

As in the above case, problem (31) iterates as

$$\begin{array}{l}{{\gamma }_l}^{\left(h+\mathrm{1}\right)}={\left[{{\gamma }_l}^{\left(h\right)}-\beta \left(P_T-{\displaystyle \sum }_l{p}_l^{\ast }\left({{\lambda }_l}^{\left(k\right)}\right)\right)\right]}_{+}\\ \forall l\in \left[\mathrm{1,2},\dots ,L\right].\end{array}$$

(37)

The whole joint congestion control and power control protocol can be represented as Algorithm 3.

Algorithm 3

//Given $${\epsilon }_1$$ , $${\epsilon }_2$$ , α, β

$$k=-1$$ ;

repeat

   $$k=k+1$$ ;

  For all s, solve (30) to get the optimum $$x_s^{\ast }\left({{\lambda }_l}^{(k)}\right)$$ .

  For all l, update $${{\lambda }_l}^{(k+1)}$$ from iteration formula (34).

   $$h=-1$$ ;

  repeat

   $$h=h+1$$ ;

      For all l, solve $$p_l^{\ast }\left({\gamma }^{(h)}\right)$$ from problem (35).

      For all l, update $${{\gamma }_l}^{(h+1)}$$ from iteration formula (37).

  until ( $$\left|p_l^{\ast }\left({\gamma }^{\left(h+1\right)}\right)-p_l^{\ast }({\gamma }^{(h)})\right|<{\epsilon }_1$$ )

until ( $$\left|x_s^{\ast }\left({{\lambda }_l}^{(k+1)}\right)-x_s^{\ast }\left({{\lambda }_l}^{(k)}\right)\right|<{\epsilon }_2$$ )

5. Simulation

We simulate the joint congestion control and power control protocol in MATLAB. A wireless network with 6 nodes is set up. There are 3 source nodes, 2 interim nodes, and 1 destination node. Network topology is shown in Figure 1. Each source node sends data to the unique destination node at a certain source rate; thus, there are 3 end-to-end data flows in the network. The routing path for every flow is as follows. Flow 1 passes through links 1, 3, and 5, flow 2 uses links 2, 3, and 5, and flow 3 uses links 4 and 5. For each link, we designate the node which is the start of each link as the manager of the link. The responsibility of the manager is to collect and update information of link, such as link power, link capacity, and congestion coefficient.

Figure 1

Network topology for simulation of cross-layer protocol design.

For our experiment, the utility function for each user is $U_s\left(x_s\right)=\ln (x_s)$ and the capacity of each link is a function of the link power, $c_l\left(p_l\right)=2\hspace{0.17em}{\log }_2(1+2.5p_l)$ . Given initial values randomly, we solve the optimization problem by using Algorithm 3.

We report the evolution of the total utility and the data rates of all 3 source nodes in Figure 2. We can see clearly in Figure 2 that the value of objective function increases gradually and finally achieves convergence. At the same time, although their rates are set with different initial values, each source node adjusts its rate distributively and eventually achieves the convergence state. Interestingly, since source nodes 1 and 2 are indistinguishable in Figure 1, we expect the evolution of their data rate to be similar. Based on Figure 2, source rates 1 and 2 converge to the same value with different initial values.

Figure 2

Trend of total utility and source rates $x_1,x_2,x_3$ during execution.

We also plotted the evolution of congestion coefficient (Lagrange multiplier) ${\lambda }_l$ and the link power $p_l$ . Figures 3 and 4 show the changing of congestion coefficients and the link powers during the execution of distributed algorithm, respectively. Obviously, both of them are convergent at about 250th iteration. Now we further analyze the implication of trend of the congestion coefficients and the link powers. From the network topology, we know that link 5 is used by all 3 data flows and congestion will take place in link 5. That is the reason why the congestion coefficient ${\lambda }_5$ is higher than other congestion coefficients of links. Similarly, ${\lambda }_3$ is a little higher than ${\lambda }_1,{\lambda }_2,{\lambda }_4$ as link 3 is used by both sources 1 and 2. To maximize the total utility, manager of link 5 needs to update the power as high as possible to increase the capacity of link 5. Because of the total power limit of all links and influence among these links, the power of link 5 cannot increase unboundedly and converges to an optimal value with constraints in the end, which is shown in Figure 4.

Figure 3

Trend of congestion coefficients ${\lambda }_1\text{–}{\lambda }_5$ during execution.

Figure 4

Trend of link powers $p_1\text{–}{p}_5$ during execution.

Though it seems that the scale of our network topology is small, the concise topology can explain all the key ideas of method we proposed. From the results of our simulation above, we obtain the maximum total utility and the optimal solutions of source rate and link power distributively. The reliability and validity of the optimization decomposition theory in large-scale wireless network protocol design are verified by our simulation. So optimization decomposition theory has a strong significance in practical problems.

6. Conclusions

For a decomposable complex optimization problem, to solve it distributively, different sequences of decomposition can be employed, which corresponds to different protocol. These protocols have the same optimization objective but they may have different performance such as power consumption, convergence rate, and the number of interactive messages. We can choose the right sequence according to specification reasonably. Regretfully, we have no knowledge about how to select a suitable decomposition sequence now. But it does not conceal the great value of the method in large-scale wireless network protocol design.

The subgradient method has little requirement of memory and it can solve many complex optimization problems. However, comparing to interior point method, the subgradient method has slower convergence rate and the rate of convergence has a big relationship with the scale of the optimization problems. At present, there are improved subgradient methods like increment subgradient method to speed up the convergence rate. If the convergence speed is fast, it will promote the application value, since it can be suitable for wireless network with rapid varying topology.