Advanced
Globally Optimal Solutions for Cross-Layer Design in Fast-Fading Lossy Delay-Constr ained MANETs
Globally Optimal Solutions for Cross-Layer Design in Fast-Fading Lossy Delay-Constr ained MANETs
Journal of Korea Multimedia Society. 2015. Feb, 18(2): 168-177
Copyright © 2015, Korea Multimedia Society
  • Received : December 18, 2014
  • Accepted : January 15, 2015
  • Published : February 28, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Quoc-Viet Pham
Dept. of Information and Communication System, Inje University, Gimhae, Gyeongnam, Korea
Hoon Kim
Dept. of Emergency Medicine, Inje University, Ilsan Paik Hospital, Goyang, Gyeonggi, Korea
Won-Joo Hwang
Dept. of Information and Communications Engineering, HSV-TRC, Inje University, Gimhae, Gyeongnam, Korea
ichwang@inje.ac.kr

Abstract
To increase the overall utility and decrease the link delay and power consumption, a joint optimal cross-layer design of congestion control at the transport layer, link delay at the data link layer and power allocation at the physical layer for mobile ad hoc networks is considered in this paper. As opposed to previous work, the rate outage probability in this work is based on exactly closed-form; therefore, the proposed method can guarantee the globally optimal solutions to the underlying problem. The non-convex formulated problem is transformed into a convex one, which is solved by exploiting the duality technique. Finally, simulation results verify that our proposal achieves considerable benefits over the existing method.
Keywords
1. INTRODUCTION
Traditionally, protocols for wireless networks are relied on the strictly-layered structure and implemented isolatedly. Followed from the seminal work on resource allocation in wired networks proposed by Kelly [1] , a lot of researches have been studied and devoted to showing the significant benefits of cross-layer designs (CLDs). Unlike wired networks, resource allocation in wireless networks is critical due to, e.g., scare resource, interference and environment disturbance. Network Utility maximization (NUM) framework has been seen as the efficient and versatile tool to deal with CLD problems, for example, routing at the network layer, congestion control at the transport layer and power control at the physical layer. By jointly using NUM and CLD, the problem can be decoupled and the algorithm can be implemented in a distributed manner.
The lossy feature was first taken into consideration in the effective network utility maximization (ENUM) framework [2] , where the transmission rate at the source is called the “ injection rate ” and the correctly received data rate at the destination is called the “ effective rate ”. Nevertheless, since ENUM does not consider the effects of the transmission power and take it into account of the optimization objective, transmit powers are not adjusted dynamically according to the channel conditions. Followed from [2] , in [3] , the authors considered the problem of congestion control in interference-limited wireless networks with power control, namely ENUM with power control (ENUMP). ENUMP, however, still does not integrate the power control and consider the link delay in the optimization objective. In [4] , the authors examined the effects of lossy features on the power control and link delay as well, namely rate-effective NUM (RENUM), with constraints on rate outage probability, data rate reduction and delay-constrained traffics, by taking them into consideration of the objective function. In [4] , the rate outage probability is, however, based on approximated form; therefore, RENUM may produce suboptimal solutions to the problem [5] .
In this paper, we propose a novel RENUM (nRENUM) which can generate the globally optimal solutions to RENUM, in fast-fading lossy delay-constrained mobile ad hoc networks (MANETs). Summarily, Our main contributions and the considerable differences of this paper can be listed, as follows:
  • In section 3, we show the network model and then formulate a joint optimization problem of congestion control, link delay and power allocation with constraints on rate outage probability, link delay and lossy rate. As opposed to RENUM, in nRENUM, the rate outage probability is based on exactly closed form; therefore, nRENUM can guarantee the globally optimal solutions to the underlying problem. nRENUM is solved by the duality techniques in section 4.
  • In section 5, we investigate the numerical simulation to further verify the outperformance of nRENUM compared to RENUM.
2. RELATED WORK
Recent researches whose principles focus on designing optimal CLD policies have been proposed [2 - 10] , ranging from wired networks to wireless networks. The seminal work on network resource allocation was first proposed by Kelly et al. in [1] . In [8] , the authors analyzed a joint design of optimal congestion and power control and made use of the high-SIR regime to transform the non-convex underlying problem to a convex one. Due to assuming that link transmissions are orthogonal, this design is not suitable for interference wireless networks. A survey on and challenges of CLDs in wireless networks can be found in [6] . A framework of congestion control and power allocation with an outage probability in fast-faded wireless channels has been studied in [5] . Like [10] , the non-convex underlying problem is transformed into a new convex problem and then solved by the duality method. In addition, the authors proposed a successive convex approximation method in order to turn the original problem to approximated convex problems and keep the TCP stack.
In [2] , the authors first investigated the “leakypipe” flow model, called ENUM, where the transmission rate of a flow decreases along its route. Henceforth, two schemes: ENUM with link outage probability and ENUM with path outage probability have been considered to examine the effects of lossy wireless links. However, power control is not examined and just fixed regardless what the current channel quality is. In addition, ENUM is not suitable for interference-limited wireless environments. Followed from [7] , S. Guo et al. proposed RENUM framework in which the overall transmission power and the link average delay are also used in the optimization objective with a constraint on the link delay requirement. Nonetheless, RENUM may just produce the suboptimal points. Our goal in this paper is to present a design that can provide the accurately optimal solutions to the RENUM problem.
3. SYSTEM MODEL
- 3.1 Network Model
We consider a multi-hop wireless networks consisting of L logical links and S sources. Let Փs = {1,2,..., S } and Ψl = {1,2,..., L } denote sets of sources and links, respectively. Let L ( s ) be the set of links used by flow s , and S ( l ) = { s S|ι L ( s )} be the set of sources using link ι .
Each flow is associated with a utility function which is assumed to be strictly concave, non-decreasing, continuously differentiable. We consider a family of utility functions which have been thoroughly discussed in [11] .
The instantaneous capacity on link ι is modeled by the Shannon capacity Cι ( P ) = W log(1+ ζγι ( P )) where P is a power allocation vector, W is the baseband bandwidth, ξ is a constant value depending on particular modulation, coding scheme and bit-error-rate and γι ( P ) is the instantaneous signal-to-interference-plus-noise ratio (SINR) at link ι , which is
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the thermal noise power at the receiver on link l ,
PPT Slide
Lager Image
is the interference experienced at the receiver on link l . Similar to [5] , we consider the non-light-of-sight propagation and the average link SINR and capacity by utilizing the statistics of γι . Then,
PPT Slide
Lager Image
where exponentially random variables Flk are assumed to be independent and identically distributed (i.i.d) and E [ Flk =1], ∀k . Accordingly,
PPT Slide
Lager Image
- 3.2 Average Delay
We consider the average link delay as a criteria in the optimization problem. Followed from [4] , each link is modeled as a M / M /1 queuing system. Let τ ( ι ) be the sum of the transmission delay and queuing delay on link ι . The link average delay [4] , [13] on link ι is
PPT Slide
Lager Image
where K is the mean of exponentially distributed rate of the input process and xs is the transmission rate of flow s . For delay-sensitive applications, it is required that the upper bound on the link delay is lower than a threshold, i.e. E ( τ ( ι )) ≤ vι . Therefore,
PPT Slide
Lager Image
- 3.3 Rate Outage Probability and Link Effective Rate
It is required to re-track the instantaneous SINR and compelled to rerun the algorithm to seek the optimal solutions when channel states change. It is not efficient and impractical, especially, for the fast-fading environments. To overcome this issue, we consider the term of outage probability [14] , which is
PPT Slide
Lager Image
is a target minimum SINR that below which performance becomes unacceptable.
We formulate the outage probability, as follows:
PPT Slide
Lager Image
where ϕl ( P ) can be viewed as reduction of data rate over link l . In Rayleigh fading model, the exactly closed-form expression [5] , [12] of ϕl ( P ) is given as
PPT Slide
Lager Image
Let ϵl is the maximal outage probability of link l . Then, a combination of (2) and (3) leads to the following equation
PPT Slide
Lager Image
where
PPT Slide
Lager Image
We consider the leaky-pipe flow model [2] , where the transmission rate of each flow changes hop by hop and decrease along its route. The effective rate ys at the destination is calculated as the multiplication of the outage probability on links that flow s traverses and the injection rate xs of flow s , as
PPT Slide
Lager Image
We assume that data generated by source s travels through Hs hops before reaching the receiver. The data rate at link i of flow s is
PPT Slide
Lager Image
and specified, as follows:
PPT Slide
Lager Image
where Pr( l ( s,i )) denotes the outage probability on link i .
- 3.4 Optimization Problem
We formulate a joint cross-layer problem with the optimization objective of maximizing the total effective utility and minimizing the transmission consumption and total link delay, as follows:
PPT Slide
Lager Image
where w 1 and w 2 are the costs per unit of consumed power and suffered delay, respectively. The above optimization problem can be explained as follows. The first and second constraint are feasible sets of flow rate and transmission power, respectively. The third one is the constraint on the rate outage probability. The fourth constrain is the requirement on the link average delay while the last one is a constraint due to the lossy nature of wireless links.
The problem (6) is not a joint convex problem due to the existence of the third and fifth constraints. Therefore, KKT conditions are just necessary, not sufficient solution optimality [15] . To ease the problem, we transform it into new one, as follows:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
In order to make the problem (7) convex, we assume the following assumption
PPT Slide
Lager Image
Then, the problem (7) is the convex optimization problem. Furthermore, strong duality also holds for this problem. The proof of convexity and strong duality of (7) is omitted due to the limited space of the paper.
4. nRENUM DISTRIBUTED ALGORITHM
In this section, we will apply the Langrangian dual method to solve the problem (7). Here, let λ,μ,v be dual variables which associate with the first, second and third constrains in (7), respectively. The Lagrangian function is defined, as follows:
PPT Slide
Lager Image
The Lagrangian dual function is given as
PPT Slide
Lager Image
Accordingly, the dual problem is, as follows:
PPT Slide
Lager Image
Due to the separable nature of the Lagrangian (8), we can make use of the decomposition method to derive subfunctions, as follows:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
The subfunction (10) is the congestion control problem which intends to determine flow rates at each link and at the destination. The subfunction (11) is the delay-constrained problem which aims at specifying link delays. The last one subfunction (12) is the resource allocation problem which determines the transmission power of each link. The subproblems are all interacted through the dual variables.
The dual problem (9) can be solved by the gradient method, from which the proposed method can be implemented in a distributed manner. Let δ ( t ) be a positive scalar step size.
Data rate : the flow rate of flow s on link i is updated via
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the gradient of L with respect to
PPT Slide
Lager Image
We have
PPT Slide
Lager Image
for i = 1,2,..., Hs . For i = H s+1 ,
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the first derivative of the utility function.
Link delay : the link delay is updated as
PPT Slide
Lager Image
Link transmit power : the transmission power is updated, as follows:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
From above updates, we propose an iterative algorithm as illustrated in Algorithm 1 . In addition, we make several remarks on the nRENUM iterative algorithm.
PPT Slide
Lager Image
Lagrange multipliers :
PPT Slide
Lager Image
where [ z ] + = max{ z ,0} and ▽ L ( λl ) is the gradient of L with respect to λl and given by
PPT Slide
Lager Image
Remark 1.
  • As mentioned in the section 1, the rate outage probability constraint in nRENUM is in rightly and explicitly closed-form; therefore, nRENUM can provide exactly optimal solutions. In a meanwhile, that of RENUM is based on approximated form, so there is no guarantee of the globally optimal solutions.
  • The proposal can be implemented in a distributed manner through message passing among links. At each link, message-passing componentsare computed and then broadcast to the other links. The transmitter on link l receives broadcast message passing from all the other links, estimates the channel gainGand then updates its transmission power via (17).
Theorem 1. Convergence of the nRENUM algorithm : let x (0), v (0), P (0), λ (0), μ (0) and v (0) are initial values. Here, let x ( t ), v ( t ), P ( t ), λ ( t ), μ ( t ) and v ( t ) are the sequences generated by (13), (16), (17), (18), (19), and (20). If the step size δ satisfies the diminishing rule
PPT Slide
Lager Image
and be positive, there actually exists a sufficiently large T 0 that ∀t ≥ T 0 , x ( t ), v ( t ) P ( t ), λ ( t ), μ ( t ) and v ( t ) converge to the globally optimal points.
PROOF : the proof is omitted, see [16] , [17] .
5. SIMULATION RESULTS
This section represents examinations of the performance of the proposed method in comparison with the alternative framework [4] .
- 5.1 Simulation settings
We consider a MANET composed of five nodes, four links and four flows with the network topology as illustrated in Fig. 1 . Nodes are separated and placed equidistantly at d = 50 meters. The outage probability thresholds and SINR thresholds for links are set to (0.20, 0.20, 0.20, 0.20) and (1.0, 1.0, 1.0, 1.0), respectively. The fast-fading channel gain is assumed to be i.i.d. while the slow-fading channel gain is assumed to be glk = g 0 ( dlk /50) -AF , where dlk is the distance between transmitter of link k and receiver of link l , AF = 4 is the path loss attenuation factor, and g 0 is the reference channel gain at a distance 50 meters and meets a condition that the average receive SINR at 50 meters is 30 dB. Without loss of generality, weights w 1 and w 2 are assumed to be 1.
PPT Slide
Lager Image
Network topology used for numerical examples.
- 5.2 Performance of nRENUM and compared framework
We now compare the proposed method with the framework [4] . We use the Jain’s index, which is one of the most widely studied fairness measures and defined as
PPT Slide
Lager Image
where X = [ x 1 , x 2 ,..., xN ] and 0≤ f ( X )≤1. We keep the other parameters fixed and change the α value, from 1 to 12, to examine its effects on the fairness. The fairness comparison is illustrated in Fig. 2 where both fairness indices changes when α varies. Specifically, nRENUM’s fairness increases with the α increment while that of RENUM decreases. In addition, nRENUM can achieve better fairness when α ≥ 4. Furthermore, we can observe that two fairness indices are almost the same when α = 4; therefore, to compare the performance of RENUM and nRENUM, we use α = 4.
PPT Slide
Lager Image
Fairness: nRENUM vs RENUM.
Fig. 3 a and 3 b represent the comparison of the injection rates and effective rates. We can observe that the flow effective rates become smaller and smaller along its routes when compared to its injection rates. In addition, a flow traversing a larger number of hops suffers higher data rate loss compared to a flow traveling less hops (e.g., flow 1 traverses 1 link and flow 3 travels 2 links). It is due to the lossy nature of wireless links. The total transmission power is depicted in Fig. 3 c, where we can realize that RENUM consumes more powers than nRENUM. The flow-3 and flow-4 delays are demonstrated in Fig. 3 d, where packets in RENUM experience longer delays than that in nRENUM. To be more specific, we examine delays experienced by packets traveling through link 3 and link 4, which is represented in Fig. 3 e. For that, should a packet travel through both link 3 and link 4 in RENUM and nRENUM respectively, it will sustain much rate losses on link 3 and in RENUM.
PPT Slide
Lager Image
The performance comparison between nRENUM and RENUM. (a) injection rates, (b) effective rates, (c) total transmission power, (d) flow delays, (e) link delays.
The above results are since the constraint on rate outage probability in RENUM reduces the original solution region and uses the approximated form. In a meanwhile, the rate outage probability constraint in nRENUM is in the rightly closedform; therefore, nRENUM can provide the globally optimal solutions. Moreover, the framework [4] does not take into consideration the SINR threshold
PPT Slide
Lager Image
so RENUM can not vary the SINR thresholds for different links to get the appropriately optimal solutions.
We continue exploring the impacts of the hop number on the performance of RENUM and nRENUM by varying flow-3 Hs , from 2 to 6. The flow-3 effective rates are described in Fig. 4 a, from which we can realize that the effective rates decrease as the number of hops increases and when Hs reaches the sufficiently large number (e.g., Hs =5), the effective rates decrease to the minimum rates. This result can be explained by the lossy feature of the wireless links. Another observation shown in Fig. 4 b is that the flow delays increase with the increment of Hs . Obviously, the flow delays experienced in nRENUM are lower than that in RENUM and nRENUM provides better the effective rate in comparison to RENUM.
PPT Slide
Lager Image
Effects of the hop number on the performance of nRENUM and RENUM. (a) flow-3 effective rate, (b) flow-3 delay.
6. CONCLUSION
This paper studied the cross-layer problem of congestion control, link average delay and power allocation in fast-fading lossy delay-constrained multi-hop wireless networks. As opposed to RENUM framework, which cannot guarantee the globally optimal solutions, we proposed the nRENUM based on exactly closed form of the link outage probability, which can provide the optimal solutions to the problem. The non-convex original problem is converted into a convex one by logarithmic transformation and auxiliary variables. Then, the problem can be solved by the duality technique and implemented distributedly. Finally, the numerical results confirmed that the proposed method can achieve superior performance and significant improvements compared to the alternative design.
BIO
Quoc-Viet Pham
He received the B.Eng. degree in Electronics and Telecommunications Engineering from Hanoi University of Science and Technology, Hanoi, Vietnam in 2013. He is currently working toward the M.S. degree in the Department of Information and Communication System, Inje University, Republic of Korea. His interests of research include mathematical optimization theories, resource allocation in wireless networks.
Hoon Kim
He received the MSc Degree from Graduate School, College of Medicine, Inha University, Korea in 2006. He received his M. D. degree from Inha University, Republic of Korea in 2002. Since September 2010, he has been a professor at Inje University, Republic of Korea. His research interests are in Health Information System and International Cooperation in Healthcare.
Won Joo Hwang
He received the Ph.D Degree from Department of Information Systems Engineering, Osaka University, Japan in 2002. He received his B.S. degree and M.S. degree from Computer Engineering, Pusan National University, Republic of Korea in 1998 and 2000 respectively. Since September 2002, he has been a professor at Inje University, Republic of Korea. His research interests are in Network Optimization and Health Information System.
References
Kelly F.P. , Maulloo A.K. , Tan D.K. 1998 "Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability," Journal of the Operational Research Society 49 (3) 237 - 252    DOI : 10.1057/palgrave.jors.2600523
Gao Q. , Zhang J. , Hanly S.V. 2009 "Cross-Layer Rate Control in Wireless Networks with Lossy Links: Leaky-Pipe Flow, Effective Network Utility Maximization and Hop-by-Hop Algorithms," IEEE Transactions on Wireless Communications 8 (6) 3068 - 3076    DOI : 10.1109/TWC.2009.080604
Wang F. , Liao X. , Guo S. , Huang H. 2013 "Jointly Optimal Congestion and Power Control for Rayleigh-faded Channels with Outage Constraints," Wireless Personal Communications 77 (1) 101 - 125    DOI : 10.1007/s11277-013-1497-x
Guo S. , Dang C. , Yang Y. 2014 "Joint Optimal Data Rate and Power Allocation in Lossy Mobile Ad Hoc Networks with Delay-Constrained Traffics," IEEE Transactions on Computers 64 (3) 747 - 762    DOI : 10.1109/TC.2013.2296043
Tran N.H. , Hong C.S. , Lee S. 2013 "Cross-Layer Design of Congestion Control and Power Control in Fast-fading Wireless Networks," IEEE Transactions on Parallel and Distributed Systems 24 (2) 260 - 274    DOI : 10.1109/TPDS.2012.118
Fu B. , Xiao Y. , Deng H. , Zeng H. 2014 "A Survey of Cross-Layer Designs in Wireless Networks," IEEE Communications Surveys & Tutorials 16 (1) 110 - 126    DOI : 10.1109/SURV.2013.081313.00231
Bui D. , Choi M. , Hwang W. 2008 "Joint Scheduling and Rate Optimization in Multichannel Multi-radio Wireless Networks with Contention-based MAC," Journal of Korea Multimedia Society 11 (12) 1716 - 1721
Chiang M. 2005 "Balancing Transport and Physical Layers in Wireless Multihop Networks: Jointly Optimal Congestion Control and Power Control," IEEE Journal on Selected Areas in Communications 23 (1) 104 - 116    DOI : 10.1109/JSAC.2004.837347
Pham Q. , Hwang W. “A Novel Cross-Layer Design for Fast-Fading Multihop Wireless Networks,” Proceeding of the Fall Conference of the Korea Multimedia Society 2014
Papandriopoulos J. , Dey S. , Evans J. 2008 "Optimal and Distributed Protocols for Cross-Layer Design of Physical and Transport Layers in Manets," IEEE/ ACM Transactions on Ne9tworking 16 (6) 1392 - 1405    DOI : 10.1109/TNET.2008.918099
Mo J. , Walrand J. 2000 "Fair End-to-End Window-Based Congestion Control," IEEE/Association for Computing Machinery Transactions on Networking 8 (5) 556 - 567
Kandukuri S. , Boyd S. 2002 "Optimal Power Control in Interference-Limited Fading Wireless Channels with Outage-Probability Specifications," IEEE Transactions on Wireless Communications 1 (1) 46 - 55    DOI : 10.1109/7693.975444
Bertsekas D.P. , Gallager R.G. , Humblet P. 1987 Data Networks Prentice-hall Englewood Cliffs, NJ
Goldsmith A. 2005 Wireless Communications Cambridge University Press UK CB2 8RU
Boyd S. , Vandenberghe L. 2009 Convex Optimization Cambridge University Press UK CB2 8RU
Bertsekas D.P. , Tsitsiklis J.N. 2000 "Gradient Convergence in Gradient Methods with Errors," Society for Industrial and Applied Mathematics Journal on Optimization 10 (3) 627 - 642
Bertsekas D.P. , Tsitsiklis J.N. 1989 Parallel and Distributed Computation: Numerical Methods Prentice-Hall, Inc. USA