Heterogeneous Resource Allocation Algorithm for Ad Hoc Networks with Utility Fairness

Abstract

Resource allocation is expected to be a most important factor especially for heterogeneous applications in wireless ad hoc networks. In this paper, a novel heterogeneous resource allocation algorithm (HRA) is presented for ad hoc networks, supporting both elastic and inelastic traffic. First, by combining the first order Lagrangian method with pseudo utility, the original nonconvex problem is converted into a new convex one. Then, we successfully solve the heterogeneous problem with the dual-based decomposition approach. In addition, we integrate utility fairness into the resource allocation framework, which can adaptively manage the tradeoff between elastic and inelastic flows. Simulations show and prove that HRA converges fast and can achieve the global optimum starting from many different network conditions, such as elastic, inelastic, and hybrid scenario. With both considerations of flow rate and utility fairness, HRA improves the overall network utility and system throughput greatly.

1. Introduction

With the rapid progress of mobile ad hoc networks (MANETs), the nature of the network is gradually evolving from homogeneous toward heterogeneous [1, 2]. In a heterogeneous ad hoc network, the devices differ in their communicational aspects such as transmission rate, energy consumption, and modes of communication. Compared with a homogeneous network, heterogeneous network imposes additional requirements. For example, it may contain special mobile nodes which consist of both smart and omnidirectional antennas, which can integrate all the physical information available to provide rich and versatile services. In addition, heterogeneous ad hoc network opens up new opportunities in multimedia systems, especially for those operating in real time such as video and voice transmission over wireless channels.

However, due to the heterogeneity in wireless networks such as ad hoc networks and wireless sensor networks (WSN), communication in heterogeneous networks is relatively more complicated than in homogeneous networks. For ad hoc networks, one important research problem is how to allocate resources to the heterogeneous nodes effectively and fairly. For sensor networks, people are usually more concerned with system throughput and performance at the sink node. In the context of sensor networks, nodes are composed of different sensor types which can execute diverse data aggregation tasks. Regardless of the types of wireless networks, ad hoc networks and sensor networks have much in common, such as constrained resource, limited battery capacity, and fully distributed manner. One major challenge for the wide deployment of ad hoc networks and sensor networks is to provide quality-of-service (QoS) support and fair resource allocation.

Since heterogeneous network may contain many different applications associated with particular nodes, flows within it are generally classified as elastic and inelastic [3]. In the case of elastic traffic, the flows can adjust their transmission rate gradually such as file transfer, email, and remote terminal applications. Elastic flows are suitable for variable data rate and non-real-time services. Another class is inelastic traffic, such as video and audio applications. Different from the elastic flow, inelastic flow is very sensitive to latency and jitter and generally has an intrinsic bandwidth requirement. It makes sense only when the transmission rate exceeds a threshold.

From the system perspective, it is very important to emphasize the channel efficiency because the available radio resources are very scarce and the aggregate network utility must be maximized. From the users' point of view, it is more important to guarantee the fairness of resource allocation, such that they will not be in starvation state and their QoS demands can be met. Thus, the resource allocation problem may encounter conflicting goals. The objective of heterogeneous resource allocation is no longer to solely maximize the sum-rate of network. Instead, it is expected to find the optimal tradeoff strategy between resource efficiency and user fairness for a variety of applications associated with different services.

In this paper, we not only focus on the heterogeneity of ad hoc networks, but also emphasize the tradeoff between system efficiency and user fairness of resource allocation. First, we present our resource allocation framework by integrating utility fairness into the objective function. Second, we transform the original nonconvex problem into a new convex optimization problem, which is equivalent to the original one. Then, we extend our resource allocation algorithm to the heterogeneous environment, mixed with elastic and inelastic flows. Finally, we present the heterogeneous resource allocation algorithm to achieve the global fair allocation of bandwidth among contending flows.

The major contribution of our paper is twofold: (1) consider the heterogeneity in ad hoc networks, that is, supporting both elastic and inelastic traffic, and (2) provide feasible balance between user fairness and network efficiency.

2. Related Works

The resource allocation problem has been extensively studied in wireline and wireless networks. As early as 1998, Kelly et al. [4] proposed the network utility maximization (NUM) model, which provides a powerful framework for network resource allocation. In 1999, Low and Lapsley [5] realized the basic version of NUM framework by using a fixed set of source nodes to predict path. However, due to the assumption of strictly concave utilities, the NUM model merely addresses the elastic traffic which is only suitable for non-real-time applications, thus failing to capture the temporal dynamics in heterogeneous networks.

Following the NUM model, various resource allocation schemes have been proposed in typical wireless networks [6, 7], ad hoc networks [8, 9], and wireless sensor networks [10, 11]. Liu et al. [7] extend the basic NUM model into the fading channel. By jointly taking into account power interference and statistical signal variations, two types of nondeterministic fading channels are integrated into the NUM framework. The primary objective of resource allocation is to maximize the network performance [8], which is usually associated with channel capacity, end-to-end delay, system throughput, and so forth. In [10], the authors proposed a middleware platform, which can control running application as well as sensing tasks in heterogeneous wireless sensor networks.

Recently, several novel algorithms [12–14] were presented to support inelastic traffic in wireless networks. In [12], a random access algorithm based on dual decomposition method was proposed in wireless networks, which can allocate the rate and the persistent probability of inelastic flows. In [13], the authors design the queue-based rate control protocol to handle the inelastic traffic in wireless sensor networks. In [14], a new method for spectrum allocation is presented, which can accommodate applications with fixed data rate. However, these algorithms only consider the homogenous link capacities in their schemes. In other words, they are based on either the fixed channel capacity or the assumption that the channel is estimated before allocation. In fact, the channel capacity of heterogeneous networks cannot be estimated in advance, since they are changing with time and depend on the conditions of other links.

User fairness is a critical performance metric in ad hoc networks and should be involved when a resource allocation scheme is designed. A well-known fairness criterion is called max-min fairness (MMF) [15, 16], which tries to allocate bandwidth equally. That is, a resource allocation is said to be max-min fair, if it is impossible to increase the bandwidth of any flow A without decreasing the bandwidth of another flow B where B's allocation was less than or equal to A's allocation. On the other hand, proportional fairness (PF) [4, 17] is an opportunistic algorithm that allocates bandwidth to users in proportion to their data rates. It exploits the users' diversity and provides a good tradeoff between fairness and network throughput. For example, PF primarily allocates resources to users with good channel conditions. These users can finish their data transfers quickly since they can take full advantage of network resources. Then, the remaining resources can be allocated to other users with worse radio conditions.

Very recently, a system for a family of fairness models has been proposed, including a-proportional fairness [18, 19]. In fact, a-proportional fairness already contains all the previous allocation models such as max-min fairness and proportional fairness. For instance, the system can achieve maximum throughput ( $\alpha =0$ ), proportional fairness ( $\alpha =1$ ), minimum potential delay ( $\alpha =2$ ), and max-min fairness ( $\alpha =\infty$ ). Thus, a-proportional fairness provides a convenient way to achieve different allocation balance between efficiency and fairness by varying the values of parameter $\alpha$ . A more general class of wireless allocation is based on utility fairness [20, 21]. Utility fairness is usually defined with a utility function that composes the optimization problem of wireless resource allocation. Among them, the resource allocation objective is to find a feasible solution to maximize the utility function specific to the fairness concept used.

However, previous work [22–24] normally focuses on either the rate allocation of elastic flows or QoS demands of real-time services. They do not consider the two issues as a whole. These schemes cannot be directly applied in a heterogeneous ad hoc network which usually contains both elastic and inelastic traffic. To the best of our knowledge, it is still a challenging and open issue to attain the utility fairness in ad hoc networks, especially considering the heterogeneous nature of elastic and inelastic flows.

3. Utility-Based Network Modeling

3.1. Network Model

A wireless ad hoc network is modeled as a directed graph $\mathcal{G}=(\mathcal{N},\mathcal{L})$ , where $\mathcal{N}$ is the set of nodes and $\mathcal{L}$ is the set of wireless links. Each node $n\in \mathcal{N}$ has transmission range $d_{tx}$ and interference range $d_{\mathrm{int}}$ . For any two nodes $n_i$ , $n_j\in \mathcal{N}$ , if node $n_i$ is in the transmission range of node $n_j$ , then node $n_i$ can communicate to node $n_j$ with a transmission link $(n_i,n_j)\in \mathcal{L}$ . We define F to be the set of network flows, where each flow $f\in F$ can span multiple hops. These links are shared by a set of F flows, where flow f uses the set of ${\mathcal{L}}_f\subset \mathcal{L}$ of links ( $f=\mathrm{1,2},\dots ,F$ ). Then we can derive the $L\times F$ routing matrix (link-flow incidence matrix) $\mathbf{R}=\{R_{lf}\}\mathrm{\hspace{0.17em}\hspace{0.17em}}$ as

$$\begin{array}{cc}& R_{lf}=\left\{\begin{array}{cc}\mathrm{1},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{link}\mathrm{\hspace{0.17em}\hspace{0.17em}}l\hspace{0.17em}\hspace{0.17em}\text{carries}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{flow}\mathrm{\hspace{0.17em}\hspace{0.17em}}f\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}\right.\end{array}$$

(1)

For interference we need to convert the connectivity graph G into the corresponding contention graph $G_c=({\mathcal{N}}_c,{\mathcal{L}}_c)$ . $G_c$ is an undirected graph (similar concepts are also used in [25–27]). If the source or destination of one link flow is within the interference range of the source or destination of another one, the two flows are said to contend with each other. The vertex set ${\mathcal{N}}_c$ contains all the link flows in the network. For instance, the vertices of $G_c$ correspond to the edge set of the connectivity graph G; that is, ${\mathcal{N}}_c=\mathcal{L}$ . An edge in set ${\mathcal{L}}_c$ indicates that two link flows in the connectivity graph G contend with each other and cannot transmit simultaneously.

The contention graph $G_c$ captures the interference among various link flows. Another important concept called maximal clique is usually associated with the contention graph. In a graph, a clique is defined as a subgraph whose vertices are adjacent to each other. A maximal clique is referred to as a clique that is not contained in any other clique [28]. In fact, a maximal clique represents a collision region where all link flows interfere with each other such that only one of them can transmit at any time. A maximal clique can also be interpreted as a limited resource contended and shared by different flows. So, maximal cliques are widely used to capture the schedulability. For instance, they can schedule network flows efficiently.

We then denote the set of maximal cliques of a contention graph by $\mathcal{Q}$ . In the contention graph, each maximal clique ${\mathcal{Q}}_q$   ( $q=\mathrm{1,2},\dots ,Q$ ) may consist of several links in the connectivity graph G and each link in graph G may belong to several maximal cliques. According to the relationship between links and maximal cliques, we define a $\mathcal{Q}\times \mathcal{L}$ clique-link incidence matrix $\mathcal{Q}=\{Q_{ql}\}$ as

$$\begin{array}{cc}& Q_{ql}=\left\{\begin{array}{cc}1,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}l\in Q_q\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}\right.\end{array}$$

(2)

3.2. Utility Function

Utility function is widely used to measure user satisfaction in the optimal flow control literature. The utility function of an application is a quantitative measure of its QoS performance. In this paper, we characterize utility in terms of resource allocation, which emphasizes the important relationship between QoS performance and resource allocation. Moreover, the utility has similar characteristics as the perceived quality of a data flow in ad hoc networks.

We denote the utility function of each user $i\in \mathcal{N}$ by $U_i(x_i)$ , which is a nondecreasing function in $x_i$ . Hence, we can control the level of user satisfaction by varying $x_i$ . Each user may have either elastic or inelastic traffic. Let ${\mathcal{N}}_E$ and ${\mathcal{N}}_I$ denote the set of users with elastic and inelastic traffic, respectively.

For elastic flows, we introduce a new concept of elastic utility function as $U_E^j(x_j)$ , which means the utility function of user j with elastic applications. These applications are rather tolerant of throughput and time-delays. We can use a concave and nondecreasing function to model the utility. A typical utility for such elastic traffic is $U_E^j(x_j)=\log (x_j+\mathrm{1})$ . As shown in Figure 1, the utility increases as the bandwidth increases, but the marginal improvement is reduced. The total utility for elastic flows can be expressed as

$$\begin{array}{cc}& U_E={\displaystyle \sum }_j{U}_E^j\left(x_j\right)\hspace{1em}\left(j\in {\mathcal{N}}_E\right).\end{array}$$

(3)

Figure 1

Utility function for elastic flows.

On the other hand, the total utility of the whole class of inelastic flows can be defined as

$$\begin{array}{cc}& U_I={\displaystyle \sum }_k{U}_I^k\left(x_k\right)\hspace{1em}\left(k\in {\mathcal{N}}_I\right),\end{array}$$

(4)

where $U_I^k(x_k)$ represents the inelastic utility function of user k. Unlike the elastic traffic, inelastic traffic depends on the QoS requirements of real-time applications, which have an intrinsic bandwidth threshold. In a heterogeneous network, the elastic flows will try to reduce their rate when the network is congested, but the inelastic flows always keep sending at their rates without considering the yield of successful transmission. So in the long run, the degradation in bandwidth may cause serious packet drop and the resources are dominated by the users of inelastic flows. Thus, we can choose a sigmoidal utility function to model these real-time applications as shown in Figure 2. Compared with the elastic utility function, the inelastic function is convex instead of concave at lower bandwidth.

Figure 2

Utility function for inelastic flows.

There exists another class of real-time application, which is called hard real-time traffic. Generally, hard real-time applications have strict bandwidth requirements and do not show any adaptive properties. If the system does not meet the minimum requirements, the real-time applications are not allowed to access the network. Examples include audio/video phone, video conference, and remote medical treatment. We can use the following utility function to model the hard real-time traffic:

$$\begin{array}{cc}& U\left(x\right)=\left\{\begin{array}{cc}\mathrm{1},\hfill & \text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}x\ge x_{\min }\hfill \\ \mathrm{0},\hfill & \text{when}\mathrm{\hspace{0.17em}\hspace{0.17em}}x<x_{\min },\hfill \end{array}\right.\end{array}$$

(5)

where $x_{\min }$ is the minimum bandwidth requirement. Such hard real-time applications can be described in Figure 2 (dash line).

It is important to choose an appropriate utility function. For instance, if the network utility is to be maximized, we can select the corresponding utility function as $U_n(x_n)=\log (x_n)$ . On the other hand, if the network throughput is be maximized, we can choose the utility function as $U_n(x_n)=x_n$ . However, system efficiency is always in conflict with fairness. A higher efficient system (i.e., higher network throughput) always means a less fair policy. Therefore, it is necessary to find a tradeoff between fairness and efficiency.

3.3. Resource Allocation Model

Consider a wireless ad hoc network which has resource B. Let N be a set of users who will compete for the resource. And we define k as the cardinality of user set N. Let $x_i$ be the shared resource which is allocated to user $i\in N$ . Then the resource allocation vector is denoted by $x=(x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_k)$ , where $\mathrm{0}<x_i<\infty$ , $i\in N$ .

As mentioned above, elastic traffic and inelastic traffic have significantly different utility functions. In a heterogeneous ad hoc network, various applications with different traffic types can provide different services. Resource allocation algorithm, therefore, should have the ability to provide a good performance balance among various applications.

4. Resource Allocation with Utility Fairness

When considering different performance of various applications, it may be impossible to assign resources simply based on the traditional criteria such as proportional fairness [17] and max-min fairness [15]. Therefore, we design a new resource allocation framework based on utility fairness [29, 30], which can adaptively allocate resources to the users according to their utility requirements. This has inspired two new concepts associated with utility fairness: one is utility max-min fairness [31] and the other is utility proportional fairness [32, 33].

4.1. Utility Fairness Criteria

Utility fairness is defined with a utility function that composes the resource allocation problem, where the objective is to maximize the utility function specific to the fairness concept used.

Definition 1.

A source rate allocation ${\mathbf{x}}^{*}=(x_{\mathrm{1}}^{*},x_{\mathrm{2}}^{*},\dots ,x_n^{*})$ is utility max-min fair (UMMF), if it is feasible, that is, ${\mathbf{x}}^{*}\mathbf{\in }\mathbf{C}$ , and if, for each node k, the utility $U_k(x_k^{*})$ cannot be increased while still maintaining feasibility, without decreasing the utility for any other node j with a lower utility $U_j(x_j^{*})\le U_k(x_k^{*})$ .

Another newly proposed criterion of utility fairness is utility proportional fairness.

Definition 2.

A source rate allocation ${\mathbf{x}}^{*}=(x_{\mathrm{1}}^{*},x_{\mathrm{2}}^{*},\dots ,x_n^{*})$ is utility proportionally fair (UPF), if it is feasible, that is, ${\mathbf{x}}^{*}\in \mathbf{C}$ , and if, for any other feasible allocation x, the following condition is satisfied:

$$\begin{array}{cc}& {\displaystyle \sum }_{i=\mathrm{1}}^n\frac{\partial U_i\left(x_i^{*}\right)}{\partial x_i}(x_i-x_i^{*})\le \mathrm{0},\end{array}$$

(6)

where $U_i(x_i)$ indicates the utility value to source i with the rate $x_i$ , and it is an increasing, strictly concave function for all $i\in \mathcal{N}$ .

The utility proportional fairness (UPF) is tremendously different from traditional proportional fairness (PF). The difference between them is that PF tries to achieve fairness in terms of rate, while UPF strives to achieve fairness in terms of utility. Since the utility can reflect user satisfaction, the utility, rather than rate, is a more meaningful metric of QoS for fair resource allocation in heterogeneous ad hoc networks.

In the following section, we will study the utility proportional fairness (UPF) in detail and propose a new resource allocation algorithm to support utility fairness.

4.2. Problem Formulation

We first define a clique-flow incidence matrix $\mathcal{A}$ as $\mathbf{Q}\times \mathbf{R}$ matrix, where $\mathbf{Q}=\{Q_{ql}\}$ is the clique-link matrix described in (2) and $\mathbf{R}=\{R_{lf}\}$ denotes the link-flow matrix incorporating the routing information as described in (1). In fact, each element in $\mathcal{A}$ , that is, $A_{qf}=Q_{ql}\times R_{lf}$ , represents the number of subflows within a maximal clique q. Then, the fair resource allocation problem can be formulated as the following optimization problem:

$$\mathbf{P}\mathbf{1}\text{:}\hspace{0.17em}\hspace{0.17em}\text{maximize}\hspace{1em}U={\displaystyle \sum }_{i=\mathrm{1}}^n{U}_i\left(x_i\right),$$

(7)

$$\text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{1em}\mathcal{A}\mathbf{x}\le \mathbf{C},$$

(8)

where $x_i$ is the source rate of flow i and $U_i(x_i)$ is the associated utility as a user satisfaction measurement. The constraint in (8) reflects the wireless resource constraint in ad hoc networks. For each clique, $\mathcal{A}=\{{\mathcal{A}}_{qf}\}$ denotes the resource usage pattern of each flow and C represents the feasible capacity region.

Since the objective function in (7) is strictly concave and continuously differentiable, there exists an optimal solution x to the above problem $\mathbf{P}\mathbf{1}$ if the feasible region given in (8) is compact and convex. The objective function in (7) is referred to as the utility function which can reflect utility fairness.

4.3. Resource Allocation Algorithm

To solve the primal problem $\mathbf{P}\mathbf{1}$ , we turn our attention to the dual problem and use the Lagrange duality [5]. The first step is to define the Lagrangian function $L(x,\lambda )$ for the optimization problem as follows:

$$\begin{array}{cc}& L\left(x,\lambda \right)={\displaystyle \sum }_{i=\mathrm{1}}^n{\mathcal{U}}_i\left(x_i\right)-{\lambda }^T\left(\mathbf{C}-\mathcal{A}\mathbf{x}\right),\end{array}$$

(9)

where $\lambda =({\lambda }_q,q\in Q)$ is a vector of Lagrange multipliers.

The dual problem D for the primal problem $\mathbf{P}\mathbf{1}$ can be defined as follows:

$$\begin{array}{cc}& \mathbf{D}\text{:}\hspace{0.17em}\hspace{0.17em}\underset{\lambda \ge \mathrm{0}}{\min }\hspace{0.17em}D\left(\lambda \right).\end{array}$$

(10)

The objective function of the dual problem then becomes

$$\begin{array}{l}D(\lambda )=\underset{x\in X}{max}L(x,\lambda )\hfill \\ =\sum _{f\in F}\underset{x\in X}{max}\left(U_f\left(x_f\right)-x_f\sum _{q\in Q}{\lambda }_q{A}_{qf}\right)+\sum _{q\in Q}{\lambda }_q{C}_q.\hfill \end{array}$$

(11)

Let us also define

$$\begin{array}{cc}& {\mu }_f={\displaystyle \sum }_{q:f\cap q\ne \mathrm{0}}{\lambda }_q{A}_{qf}.\end{array}$$

(12)

In fact, the Lagrange multiplier ${\lambda }_q$ may be interpreted as the price per unit bandwidth consumed at maximal clique q (the shadow price of clique q). Accordingly, ${\mu }_f$ represents the price of flow f which has to pay for transmitting at rate $x_f$ .

Since the objective function ${\mathcal{U}}_i(x_i)$ is increasing and is strictly concave over the range $m_i\le x_i\le M_i$ , the dual function $D(\lambda )$ is continuously differentiable. Thus, we can use the gradient projection method [7] to solve the dual problem D.

The Lagrange multiplier ${\lambda }_q$ is adjusted in the opposite direction to the gradient $\nabla D(\mu )$ as follows:

$$\begin{array}{cc}& {\lambda }_q\left(t+\mathrm{1}\right)={\left[{\lambda }_q\left(t\right)-\alpha \frac{\partial D\left(\lambda \left(t\right)\right)}{\partial {\lambda }_q}\right]}^{+},\end{array}$$

(13)

where t is the iteration number and $\alpha >0$ is the step size. Based on (11), the gradient of $D(\lambda )$ with respect to $\lambda$ is

$$\begin{array}{cc}& \frac{\partial D\left(\lambda \right)}{\partial {\lambda }_q}=C_q-{\displaystyle \sum }_{f\in F^{\prime }}{x}_f{A}_{qf}.\end{array}$$

(14)

Therefore, we have

$$\begin{array}{cc}& {\lambda }_q\left(t+\mathrm{1}\right)={\left[{\lambda }_q\left(t\right)-\alpha \left(C_q-{\displaystyle \sum }_{f\in F^{\prime }}{x}_f{A}_{qf}\right)\right]}^{+}.\end{array}$$

(15)

The above equation can reflect the law of supply and demand. When the bandwidth demand in the maximal clique q exceeds its supply $C_q$ , the price for accessing the clique is increased (i.e., to raise the clique price). On the other hand, if the rate demand is less than the effective capacity of clique q, the clique price will be decreased.

Let $x_f({\mu }_f)$ be the demand of flow f when the flow price is ${\mu }_f$ ; that is,

$$\begin{array}{cc}& x_f\left({\mu }_f\right)=\underset{x_f\in X_f}{\arg \hspace{0.17em}\max }\left(U_f\left(x_f\right)-x_f{\mu }_f\right).\end{array}$$

(16)

Here, $x_f({\mu }_f)=U_f^{\prime -\mathrm{1}}({\mu }_f)$ is the inverse function of $U_f^{\prime }(x_f)$ , which is the derivative function of $U_f(x_f)$ . In fact, $x_f({\mu }_f)$ reflects the optimal rate for flow f, where the network utility will be maximized with a flow price of ${\mu }_f$ .

For each elastic flow f, the source node receives shadow price information from all maximal cliques. Then it updates the transmission rate according to (16). Meanwhile, the link updates the clique price ${\lambda }_q$ according to (15). This is an iterative procedure, where the new transmission rate of flow f is reported to all maximal cliques q every time. It can be shown that, starting from any initial rate, this iterative algorithm will converge to the optimal solution $(x^{*},{\lambda }^{*})$ by choosing a proper step size $\alpha$ . Moreover, since the solution is primal-dual optimal, $x^{*}$ is also the optimal rate for the primal problem. In this way, the network utility can be maximized in a distributed manner.

5. Heterogeneous Resource Allocation Algorithm

In this section, we extend our resource allocation algorithm to the heterogeneous environment. Particularly, we present a distributed resource allocation algorithm to achieve utility fairness, with consideration of both elastic and inelastic traffic.

5.1. Notations and Definitions

In order to handle heterogeneous flows (i.e., elastic and inelastic), we develop a new flow control strategy to ensure utility fairness during the process of resource allocation. This new resource allocation mechanism, which integrates utility fairness, can not only support elastic traffic, but also be suitable for inelastic traffic.

First, we define a “pseudo utility” function for user i:

$$\begin{array}{cc}& {\mathcal{U}}_i\left(x_i\right)={{\displaystyle \int }}_{m_i}^{x_i}\frac{\mathrm{1}}{U_i\left(y\right)}dy,\hspace{1em}{m}_i\le x_i\le M_i,\end{array}$$

(17)

where $M_i<\infty$ and $m_i\ge \mathrm{0}$ are the maximum and minimum transmission rates needed by user i, respectively.

By substituting the “pseudo utility” ${\mathcal{U}}_i(x_i)$ into the original optimization problem $\mathbf{P}\mathbf{1}$ , we can derive a new optimization problem $\mathbf{P}\mathbf{2}$ as follows:

$$\mathbf{P}\mathbf{2}\text{:}\hspace{0.17em}\hspace{0.17em}\text{maximize}\hspace{1em}U={\displaystyle \sum }_{i=\mathrm{1}}^n{\mathcal{U}}_i\left(x_i\right),$$

(18)

$$\text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{1em}\mathcal{A}\mathbf{x}\le \mathbf{C}\mathbf{.}$$

(19)

Since the original utility function $U_i(x_i)$ is continuous, is strictly increasing, and is nonnegative, the pseudo utility ${\mathcal{U}}_i(x_i)$ must be increasing and be strictly concave over the range $m_i\le x_i\le M_i$ . After the transformation, the new problem $\mathbf{P}\mathbf{2}$ stays as a convex optimization problem and is capable of handling both elastic and inelastic flows.

5.2. Heterogeneous Allocation Problem Formulation

Since the flows in heterogeneous ad hoc networks are composed of elastic and inelastic traffic, we can divide the utility function into two parts. One is the utility function $U_e(x_e)$ for elastic flow e and the other is the utility function $U_i(x_i)$ for inelastic flow i. Then, the heterogeneous resource allocation problem ( $\mathbf{H}\mathbf{P}$ ) in ad hoc networks can be formulated as follows:

$$\text{HP}:maxU=\sum _e{U}_e(x_e)+\sum _i{U}_i(x_i),$$

(20)

$$\begin{array}{ll}\text{subject to}\hfill & A_{qe}{x}_e\le C_q^e,\hfill \\ \hfill & A_{qi}{x}_i\le C_q^i,\hfill \\ \hfill & 0\le x_e\le M_e,\hfill \\ \hfill & m_i\le x_i\le M_i.\hfill \end{array}$$

(21)

Here, $C_q^e$ and $C_q^i$ denote the effective capacity of clique q for elastic flow e and inelastic flow i, respectively. Inelastic traffic can be further classified into two subclasses: hard real-time traffic and soft QoS traffic. For inelastic real-time traffic with discontinuous utility, $m_i$ is the threshold rate. When the source rate exceeds the threshold, that is, $x_i\ge m_i$ , the network maintains a constant performance $U_i(x_i)=U_{\mathrm{0}}$ . Otherwise, the utility drops to zero when it is below the threshold. For inelastic soft traffic with sigmoidal utility, $m_i$ is the minimum transmission rate with certain QoS guarantee. The utility function is convex at low transmission rates and becomes concave when $x_i\ge m_i$ .

The formulation of (20) is an extension of the resource allocation problem described in (7). The main advantage of the new formulation is that it supports both elastic and inelastic traffic.

Since the constraints are linear and the objective function is concave over the range $m_i\le x_i\le M_i$ , we can solve the heterogeneous resource allocation problem by convex programming.

The Lagrangian of the regularized primal problem $\mathbf{H}\mathbf{P}$ can be written as

$$\begin{array}{l}L\left(x_e,x_i,\lambda ,\mu \right)=\sum _e{U}_e\left(x_e\right)-{\lambda }^T\left(C^e-A{x}_e\right)\hfill \\ +\sum _i{U}_i(x_i)-{\mu }^T\left(C^i-A{x}_i\right)\hfill \\ =\sum _e\left(U_e\left(x_e\right)-x_e\sum _q{\lambda }_q{A}_{qe}\right)+\sum _q{\lambda }_q{C}_q^e\hfill \\ +\sum _i\left(U_i\left(x_i\right)-x_i\sum _q{\mu }_q{A}_{qi}\right)+\sum _q{\mu }_q{C}_q^i,\hfill \end{array}$$

(22)

where $\lambda$ and $\mu$ are the Lagrangian multipliers with the interpretation of shadow price for elastic and inelastic flows, respectively. Then we can decompose the maximization problem into the following two subproblems:

$$\begin{array}{cc}& D\left(\lambda ,\mu \right)=D_{\mathrm{1}}\left(\lambda \right)+D_{\mathrm{2}}\left(\mu \right),\end{array}$$

(23)

where

$$\begin{array}{l}{D}_1(\lambda )=\underset{x_e}{max}{L}_1(x_e,\lambda )\hfill \\ =\underset{x_e}{max}\left(\sum _e\left(U_e(x_e)-x_e\sum _q{\lambda }_q{A}_{qe}\right)+\sum _q{\lambda }_q{C}_q^e\right),\hfill \end{array}$$

(24)

$$\begin{array}{l}{D}_1(\mu )=\underset{x_i}{max}{L}_2(x_i,\mu )\hfill \\ =\underset{x_i}{max}\left(\sum _i\left(U_i(x_i)-x_i\sum _q{\mu }_q{A}_{qi}\right)+\sum _q{\mu }_q{C}_q^i\right).\hfill \end{array}$$

(25)

The first subproblem $D_{\mathrm{1}}(\lambda )$ can be regarded as the bandwidth allocation for elastic flows and the second subproblem $D_{\mathrm{2}}(\mu )$ may be interpreted as the rate control for inelastic flows. Thus, by solving the two subproblems, we can obtain the optimal resource allocation in heterogeneous ad hoc networks with consideration of both elastic and inelastic traffic.

According to (24), the subgradient of $D(\lambda ,\mu )$ at point ${\lambda }_e$ is given by

$$\begin{array}{cc}& \frac{\partial D(\lambda ,\mu )}{\partial {\lambda }_e}=C_q^e-{\displaystyle \sum }_e{x}_e{A}_{qe}.\end{array}$$

(26)

The subgradient for $D(\lambda ,\mu )$ at ${\mu }_i$ can be obtained in a similar way. Thus, we can obtain the price adjustment scheme with step sizes $\alpha$ and $\beta$ at iteration time t:

$$\begin{array}{l}{\lambda }_e(t+1)={\left[{\lambda }_e(t)-\alpha \frac{\partial D(\lambda ,\mu )}{\partial {\lambda }_e}\right]}^{+}\hfill \\ ={\left[{\lambda }_e(t)-\alpha \left(C_q^e-\sum _e{x}_e{A}_{qe}\right)\right]}^{+},\hfill \end{array}$$

(27)

$$\begin{array}{l}{\mu }_i(t+1)={\left[{\mu }_i(t)-\beta \frac{\partial D(\lambda ,\mu )}{\partial {\mu }_i}\right]}^{+}\hfill \\ ={\left[{\mu }_i(t)-\beta \left(C_q^i-\sum _i{C}_q^i{A}_{qi}\right)\right]}^{+}.\hfill \end{array}$$

(28)

5.3. Elastic Rate Allocation

The subproblem $D_{\mathrm{1}}(\lambda )$ represents an optimal resource allocation problem for elastic flows. The gradient of $L_{\mathrm{1}}(x_e,\lambda )$ with respect to $x_e$ is as follows:

$$\begin{array}{cc}& \frac{\partial L_{\mathrm{1}}(x_e,\lambda )}{\partial x_e}=U_e^{\prime }\left(x_e\right)-{\displaystyle \sum }_{e\in E\left(f\right)}\lambda .\end{array}$$

(29)

Thus, we can derive the following algorithm of source rate adjustment for elastic flow e:

$$\begin{array}{cc}& x_e\left(t+\mathrm{1}\right)={\left[x_e\left(t\right)+\gamma \frac{\partial L_{\mathrm{1}}\left(x_e\left(t\right),\lambda \left(t\right)\right)}{\partial x_e}\right]}^{+},\end{array}$$

(30)

where $\gamma >0$ is a constant step size and ${\left[z\right]}^{+}=\max \{z,0\}$ .

5.4. Inelastic Rate Allocation

The objective of the subproblem $D_{\mathrm{2}}(\mu )$ is to obtain the optimal rate allocation for inelastic flows, such that their QoS demands can be met. We define the objective function of subproblem $D_{\mathrm{2}}(\mu )$ as

$$\begin{array}{cc}& L_{\mathrm{2}}\left({\mathbf{x}}_i,\mu \right)={\displaystyle \sum }_i\left(U_i\left(x_i\right)-x_i{\displaystyle \sum }_q{\mu }_q{A}_{qi}\right)+{\displaystyle \sum }_q{\mu }_q{C}_q^i.\end{array}$$

(31)

Note that the objective function $L_{\mathrm{2}}(x_i,\mu )$ is differential with respect to variable $x_i$ over the range $m_i\le x_i\le M_i$ . According to (31), we have

$$\begin{array}{cc}& \frac{\partial L_{\mathrm{2}}(x_i,\mu )}{\partial x_i}=U_i^{\prime }\left(x_i\right)-{\displaystyle \sum }_{i\in I\left(f\right)}\mu .\end{array}$$

(32)

Thus, the inelastic rate allocation algorithm can be derived as follows:

$$\begin{array}{cc}& x_i\left(t+\mathrm{1}\right)={\left[x_i\left(t\right)+\omega \frac{\partial L_{\mathrm{2}}\left(x_i\left(t\right),\mu \left(t\right)\right)}{\partial x_i}\right]}_{m_i}^{M_i},\end{array}$$

(33)

where $\omega$ is a positive scale step size and $[z{]}_i^j$ denote the projection onto the range $[m_i,M_i]$ .

5.5. Algorithm for Heterogeneous Resource Allocation

To sum up the above analysis, we present the heterogeneous resource allocation algorithm (HRA) as follows.

For each elastic flow e, ${\lambda }_e$ may be interpreted as the shadow price of flow e. First, the source node receives shadow price information from all elastic flows. Then, it calculates the shadow price according to (27) and updates the source rate for elastic flow e according to (30). Finally, it reports the new transmission rate to all links on its path.

For inelastic flows, source rates are allocated according to different types of traffic. If the traffic is hard real-time, each clique q reserves necessary bandwidth $\sum x_f{A}_{qf}$ to support real-time service. Note that hard real-time flows do not change their rates during the iteration, so the bandwidth reservation process will not be affected by elastic flows. On the other hand, if the traffic has sigmoidal utility, the source node calculates the effective capacity $C_q^i$ for inelastic flow i. Then it updates the new transmission rate and broadcasts this message to all the neighboring nodes.

Algorithm HRA

Elastic Rate Allocation

• (1)

Receive rates $x_e(t)$ from all elastic flows e, where $e\in E(f)$ .

(2)

Update shadow price for elastic flows as

$$\begin{array}{cc}& {\lambda }_e\left(t+\mathrm{1}\right)={\left[{\lambda }_e\left(t\right)-\alpha \left(C_q^e-{\displaystyle \sum }_e{x}_e{A}_{qe}\right)\right]}^{+}.\end{array}$$

(34)

(3)

Send ${\lambda }_e(t+\mathrm{1})$ to all flows e such that $e\in E(f)$ .

(4)

Adjust the elastic flow rate at times $t=\mathrm{1,2},\dots$ :

$$\begin{array}{cc}& x_e\left(t+\mathrm{1}\right)={\left[x_e\left(t\right)+\gamma \frac{\partial L_{\mathrm{1}}\left(x_e\left(t\right),\lambda \left(t\right)\right)}{\partial x_e}\right]}^{+}.\end{array}$$

(35)

(5)

Send $x_e(t+\mathrm{1})$ to all links on its path.

Inelastic Rate Allocation

• (1)

For inelastic flows with hard real-time traffic, each clique q first reserves necessary bandwidth $\sum x_f{A}_{qf}$ and then allocates the remaining bandwidth.

(2)

Loop until the bandwidth allocation of all the hard real-time traffic is completed.

(3)

For inelastic flows with sigmoidal utility, the source nodes of clique q calculate the effective capacity $C_q^i$ for inelastic flow i and then broadcast this message to all the neighboring cliques.

(4)

Update the shadow price of inelastic flows according to (28).

(5)

Adjust the inelastic flow rate at times $t=\mathrm{1,2},\dots$ :

$$\begin{array}{cc}& x_i\left(t+\mathrm{1}\right)={\left[x_i\left(t\right)+\omega \frac{\partial L_{\mathrm{2}}\left(x_i\left(t\right),\mu \left(t\right)\right)}{\partial x_i}\right]}_{m_i}^{M_i}.\end{array}$$

(36)

(6)

Send new $x_i(t+\mathrm{1})$ to all nodes along the link.

The HRA algorithm will proceed with a two-stage iteration. First, the inelastic rate allocation process is executed since the QoS requirements for real-time applications should be met in advance. Then, the elastic flow allocation is executed based on the remaining bandwidth for non-real-time service. Furthermore, if we choose appropriate utility functions $U_I$ and $U_E$ for elastic and inelastic flows, respectively, different utility fairness models—such as utility proportional fairness and utility max-min fairness—can be achieved.

6. Performance Evaluation

In this section, we present the simulation results for HRA algorithm in heterogeneous ad hoc networks consisting of both elastic and inelastic flows.

6.1. Simulation Setup

In order to evaluate the performance of HRA algorithm presented in Section 5, we implement the algorithm in NS-2 (version 2.32). In addition, we set up different types of traffic generators over different scenarios. The network scenarios are composed of different traffic, such as Case 1: elastic traffic, Case 2: inelastic traffic, and Case 3: mixed network traffic, respectively. Consequently, users have different utility functions in different network scenarios. A 1200 m × 1200 m ad hoc network consisting of 60 nodes has been built to test the resource allocation scheme. Each node has a bandwidth capacity of 11 Mbps and the transmission range of the node is 30 m. Mobile nodes can travel in different directions with equal probability and using three different speed models: 0 m/s, 3–12 m/s, and 9–20 m/s.

6.2. Case 1: Elastic Network Scenario

In Figure 3, we set up the elastic network scenario composed of six users, where each user's utility function is set to $U(x_n)=\log (x_n)\hspace{0.17em}\hspace{0.17em}(x_n>\mathrm{0})$ for imposing utility proportional fairness. In this case, we can study the optimal utility fairness among the users. As shown in Figure 3, the network consists of six nodes and three unidirectional links through 3 $\to$ 4, 2 $\to$ 3 $\to$ 4 $\to$ 5, and 1 $\to$ 2 $\to$ 3 $\to$ 4 $\to$ 5 $\to$ 6, with the link capacity equal to 1 Mbps. In the simulation, we choose the step size $\gamma =\mathrm{0.1}$ and the simulation time is set to 200 seconds.

Figure 3

6-node topology with elastic flows.

Figure 4 shows the calculated rates of the elastic flows change with time. We observe that the date rates of all flows change sharply at the beginning of the iteration. In a sense, flow 1 and flow 3 are relatively stable, while flow 2 is much more intense than the other flows. Because flow 2 goes across the four nodes (i.e., nodes 2, 3, 4, and 5) and they are all in the middle of the network, the wireless channel competition will be more intense, which causes bigger fluctuations of flow 2. After a period of fluctuation, the algorithm converges to the optimal solution quickly, which shows the effectiveness of our algorithm.

Figure 4

Simulation results for elastic flows.

In addition, we can find something interesting from Figure 4. With the passage of time, the data rate of flow 1 drops rapidly, while flow 2 and flow 3 increase their data rates gradually. To ensure the utility fairness among the elastic flows, the three flows need to adjust their data rate according to the network utility. Finally, they all converge to the optimal value with satisfactory speed, which further verify the convergence of the HRA algorithm.

6.3. Case 2: Inelastic Network Scenario

In Case 2, for comparison purpose, we set the inelastic network scenario which is composed of seven nodes and four flows. As shown in Figure 5, the network consists of four unidirectional data flows A $\to$ C $\to$ D, G $\to$ E $\to$ D, F $\to$ E, and B $\to$ C $\to$ D $\to$ E $\to$ F with capacities fixed, respectively, at 2 MB/s, 1 MB/s, 3 MB/s, and 1 MB/s. There are four sources $S_{\text{A}}$ , $S_{\text{B}}$ , $S_{\text{F}}$ , and $S_{\text{G}}$ with a sigmoidal utility function, which represents an inelastic data flow typically associated with the real-time application.

Figure 5

7-node topology with inelastic flows.

In the simulation, we run the HRA algorithm with $\gamma =\mathrm{0.2}$ and the results are given in Figure 6. It can be seen that the network utility varies over time. At the beginning, the initial utility of each user is set to a lower value, respectively. Later, each source user gradually increases their utility to improve the network throughput. However, the source rate of each user should be also controlled well due to the link capacity limitation. Moreover, the utilities allocated to four sources $S_{\text{A}}$ , $S_{\text{B}}$ , $S_{\text{F}}$ , and $S_{\text{G}}$ are different.

Figure 6

Simulation results for inelastic flows.

At first, the utilities of all sources are almost the same. Then, the source node $S_{\text{F}}$ rapidly improves its data rate, thereby increasing the utility and surpassing the other nodes quickly. In the whole simulation, the data rates of flow GED and flow BCDEF are very close, overlapping constantly. This is determined by the network topology and user utility. As we can see, flow BCDEF travels across multiple nodes and flow GED is in the middle of the network. In this way, each node can adjust its data transfer rate according to the network topology and location automatically, which ensures the overall optimization of network utility and the user fairness. As expected, the oscillation is observed until the flows all converge to the optimal solution. Therefore, this confirms that the HRA algorithm given in this paper can provide an efficient resource allocation scheme with both considerations of network utility and fairness for heterogeneous ad hoc networks.

6.4. Case 3: Mixed Network with Elastic and Inelastic Flows

In Case 3, we evaluate the dynamic performance of our heterogeneous resource allocation algorithm (HRA) in large-scale networks and compare our solution with two other algorithms. As shown in Figure 7, we designed a hybrid wireless ad hoc network scenario, including 60 nodes randomly generated in the area of size 1000 m $*$ 1000 m. The network is composed of three parts, with an isolated node in the middle. Nodes of different colors represent different applications, which belong to the heterogeneous network and can provide versatile services. The transmission range and interference range of all nodes are 250 m and 550 m, respectively.

Figure 7

60-node heterogeneous network with mixed flows.

To test the performance of HRA algorithm under elastic and inelastic conditions, we ran different types of traffic generators over the wireless ad hoc scenario. There are various data sources in the network, which are composed of two elastic flows and two inelastic flows. The utility functions of all sources are given by: $U_{\mathrm{1}}\left(x_{\mathrm{1}}\right)=\log \left(x_{\mathrm{1}}\right)$ , $U_{\mathrm{2}}(x_{\mathrm{2}})=\log (x_{\mathrm{2}}+\mathrm{1})$ , $U_{\mathrm{3}}(x_{\mathrm{3}})=\mathrm{1}/(\mathrm{1}+e^{-\mathrm{2}(x_{\mathrm{3}}-\mathrm{4})})$ , and $U_{\mathrm{4}}(x_{\mathrm{4}})=\mathrm{1}/(\mathrm{1}+e^{-\mathrm{2}(x_{\mathrm{4}}-\mathrm{7})})$ . Each utility function is multiplied by a nonnegative weighting factor w, to adjust the utility ratio of elastic and inelastic flows. The first two functions, which are logarithmic utility functions, represent elastic applications, whereas the last two sigmoidal utility functions approximate real-time applications. All the sources have their maximum data transfer rate at 10 Mbps.

Figure 8 shows how the average transfer rates for inelastic and elastic flows converge when HRA algorithm is used, where the rates are allocated to two elastic and two inelastic flows. From this figure, we can see that the QoS requirements of all flows are satisfied. The average service rate of the inelastic flow on each link l is larger than the minimum threshold, which equals 350 Kbps. Moreover, for each link of the elastic flow, its average service rate is larger than the minimum transmission rate request. Therefore, HRA algorithm not only can allocate elastic flow effectively, but also can be used in the inelastic flow, which guarantees the transmission of real-time applications.

Figure 8

Average elastic and inelastic flow rates.

6.5. Comparison between HRA and Other Algorithms

As utility is our main performance metric, we will compare our solution HRA with two other nonheterogeneous allocation schemes. One is a simple resource allocation algorithm called SRA, in which the heterogeneous characteristics are not exploited for rate allocation. SRA always handles elastic and inelastic flows in the same way. Therefore, it cannot distinguish elastic and inelastic flows well. The other is similar to the “Utility-Based Adaptive Resource Allocation” algorithm proposed by Rodrigues and Casadevall [34]. We make some modifications and call it UBARA. It manages the tradeoff between system resource efficiency and user fairness and can be applied to wireless network scenarios. Since the original algorithm cannot deal with hybrid network scenario, we take the following changes to handle both elastic and inelastic traffic. For inelastic flows, each link l transmits at the same rate level in all network conditions. For elastic flows, it allocates flow rate based on the user utility.

In this part, we will verify the impact of node mobility on the performance of HRA. The mobility model is as follows: a node randomly selects a destination within the network limits and then moves towards it at a speed of 4, 8, 12, 16, and 20 m/s. The simulation lasts 150 seconds and the delay limit is set to 5. The network topology and other parameters are the same as Case 3.

Figure 9 shows how the utility of elastic flow changes with the node mobility. We can derive the following observations. First, when the mobility speed is low, the utility of three algorithms is very close. Among them, HRA performs best. Second, as the node mobility speed increases, UBARA and SRA decrease very quickly. At last, when the node speed increases up to 20 m/s, HRA can still keep a high system utility, while SRA and UBARA fall to less than 3.

Figure 9

Elastic utility comparison in mobile scene.

In Figure 10, we can find something interesting. For inelastic flows, HRA exhibits averagely twice higher utility than UBARA and SRA. When the node speed increases more than 12 m/s, the utility of SRA and UBARA declines less than 1, which means they cannot meet the rate demand of inelastic flows. On the contrary, HRA still keeps a higher utility more than 2. That means HRA can completely meet the demand of real-time applications, which are composed of inelastic flows. In all experiments, HRA performs best among the three algorithms. Specifically in inelastic network scenarios, HRA performs much better than SRA and UBARA.

Figure 10

Inelastic utility comparison in mobile scene.

These results are due to the following reasons. One is that HRA tries to allocate resources to the urgent inelastic flow with higher priority, since inelastic flow is delay-sensitive and elastic flow is delay-tolerant. When the channel is in good condition, HRA tries to allocate a high rate to elastic and inelastic flows according to the user utility. If the channel is in poor condition, HRA decreases the service rate of elastic flows to guarantee the transmission demand of inelastic flows. In this way, the service rate of inelastic flow can exceed the threshold. Thus, the aggregate utility of inelastic flows is always maintained at a high level (i.e., greater than two), which fully meet the demand of real-time applications. However, SRA and UBARA always try to allocate equal bandwidth to elastic and inelastic flows, no matter how poor the network state is. This greatly affects the transmission of inelastic flows, leading to the overall inelastic utility less than 1. Therefore, the demand of real-time applications cannot be met by SRA and UBARA.

The other reason is that when nodes move at a high speed, the network topology is changing dramatically. Since SRA and UBARA do not distinguish between elastic and inelastic flows, they may not find the global optimum. In all experiments, UBARA performs slightly better than SRA, because UBARA is a utility-based resource allocation scheme, considering the user fairness. However, UBARA cannot satisfy the QoS requirement of real-time applications, as it cannot distinguish the two types of traffic.

On the other hand, HRA can find the optimal tradeoff strategy between resource efficiency and user fairness for elastic and inelastic flows, although the network states are changing very fast. With both considerations of flow rate and utility fairness, HRA performs much better than SRA and UBARA especially in highly dynamic and mobile networks. In contrast, SRA and UBARA neither exploit the heterogeneous characteristic nor optimize the service rates of inelastic flows, which lead to the low accumulated system utility in hybrid network scenario mixed with elastic and inelastic flows.

To further show the performance of HRA, we evaluate the throughput of HRA and compare it with the other two algorithms. The simulation results are shown in Figure 11. When the number of users is less than 8, SRA and UBARA are very close and their throughput is higher than 2 Mbps. However, when the number of users is larger than 10, the throughput of SRA and UBARA declines quickly because of the absence of fairness consideration. When the user number reaches 18, the throughput of SRA is below 1 Mbps. In all experiments, HRA achieves the highest aggregate throughput among the three algorithms. The explanation for the above results is straightforward: HRA can guarantee the utility fairness among elastic and inelastic flows, while the other two algorithms cannot.

Figure 11

Average throughput of network users.

Finally, we evaluate the fairness index of HRA, which is a particularization of the well-known Jain fairness index proposed by Jain et al. in [35]. The difference is that the fairness index here considers both elastic and inelastic flows, and we call it mixed fairness index (MFI). From Figure 12, we observe that HRA has a better fairness index than both SRA and UBARA. When the user number is equal to 1, the three algorithms all achieve the same fairness index close to 1. They do not need to allocate rate among different users if the user is only one; therefore, the fairness index must be 1. On the other hand, if users increase, they need to allocate extra bandwidth to other users, so the fairness index will be reduced. When the number of users exceeds 9, the gap between HRA and the other two algorithms becomes larger.

Figure 12

Fairness index of network users.

The above simulation results indicate that, compared with SRA and UBARA, HRA can allocate resources more fairly and more efficiently in a distributed manner, while maintaining a higher system throughput for real-time flows. In fact, HRA can manage the tradeoff between elastic and inelastic flows, which guarantees the utility fairness among various applications. More importantly, the simulation confirms that the flow control algorithm proposed in this paper can provide an efficient utility fair resource allocation in heterogeneous networks, not only suitable for common elastic data traffic but also applicable to inelastic real-time applications.

7. Conclusions

In this paper, we have developed a heterogeneous resource allocation algorithm (HRA) for wireless ad hoc networks, supporting both elastic and inelastic traffic. The proposed algorithm can allocate resource for heterogeneous ad hoc networks, which may contain diverse node types and execute various tasks. Besides rate allocation, utility fairness is also integrated into the framework to provide a good performance balance among various applications. We have shown that HRA algorithm converges fast and can achieve the global optimum starting from many different network conditions, such as elastic network scenario, inelastic network scenario, and hybrid network scenario. As highlighted, HRA can manage the tradeoff between elastic and inelastic traffic, which guarantees the utility fairness among competing flows. Compared with the other two algorithms, HRA can allocate resource more fairly and more efficiently, while maintaining a higher network throughput for the system. Therefore, our algorithm is well suited for heterogeneous ad hoc networks. Moreover, even though the development of this research is in the ad hoc network environment, our algorithm can be generally extended and applied to wireless sensor networks due to the good scalability of the framework.