Liang Zhou

Baoyu Zheng

Benoît Geller

Anne Wei

Jingwu Cui

Joint QoS Control for Video Streaming over Wireless Multihop Networks: A Cross-Layer Approach

Keywords: video, QoS, wireless networks, cross-layer, flow control

In this paper, we propose a novel cross-layer framework for jointly controlling and coding for multiple video streams in wireless multihop networks. At first, we develop a cross-layer flow control algorithm which works at the medium access control (MAC) layer to adjust each link's persistence probability and at the transport layer to adjust flow rates. This proposal is designed in distributed manner that is amenable to on-line implementation for wireless networks. And then, a rate-distortion optimized joint source-channel coding (JSCC) approach for error-resilient scalable encoded video is presented, in which the video is encoded into multiple independent streams and each stream is assigned forward error correction (FEC) codes to avoid error propagation. Furthermore, we integrate the JSCC with the specific flow control algorithm, which optimally applies the appropriate channel coding rate given the constraints imposed by the transmission rate obtained from the proposed flow control algorithm and the prevailing channel condition. Simulation results demonstrate the merits and the need for joint QoS control in order to provide an efficient solution for video streaming over wireless multihop networks.

I. INTRODUCTION

Rapid growth in wireless networks is fueling the demand that services traditionally available only in wired networks, such as video, be available to mobile users. However, the characteristics of wireless systems provide a major challenge for reliable transport of video since the video transmitted over wireless channels is highly sensitive to noise, interference and topology change which can cause both packet losses and bit-errors. Furthermore, these errors tend to occur in bursts, which can further decrease the delivered Quality of Service (QoS). Current and future wireless systems will have to cope with this lack of QoS guarantees.

To date, the video transmission over wireless networks is still an open problem. [START_REF] Cho | A full-featured, error-resilient, scalable wavelet video codec based on the set partitioning in hierarchical trees (SPIHT) algorithm[END_REF], [START_REF] Kim | Distrubuted Video Streaming Using Multiple Description Coding and Unequal Error Protection[END_REF] and [START_REF] Fu | A Joint Source and Channel Coding Algorithm for Error Resilient SPIHT-Coded Video Bitstreams[END_REF] present some wavelet-based encoders that divide the original bit-stream into multiple streams, called multiple description coding (MDC), to tradeoff the error-resilience and coding complexity; [START_REF] Tian | Robust and efficient path diversity in application-layer multicast for video streaming[END_REF] and [START_REF] Wang | Multiple-Description Coding for Overlay Network Streaming[END_REF] amplify the benefits of using MDC by combining with path diversity, in these approaches each stream is explicitly transmitted over an independent path to the receiver to achieve higher tolerance to packet loss and delay due to network congestion; In [START_REF] Wang | Optimal Flow Control and Routing in Multi-Path Networks[END_REF], the authors propose two flow control algorithms for network with multiple paths between source-destination pair, both are distributed algorithms over the network to maximize aggregate source utility.

However, these works, as well as much previous work appearing in the literature, target the problem from an individual point of view without considering the overall system performance.

Therefore, it remains unclear what level of video quality can be supported by the wireless networks.

Typically, for video communications over wireless multihop networks, there are two main factors which can greatly affect the perceived video quality: the transmission error and flow control. On one hand, packet loss leading to transmission error is generally caused by channel fading, multi-path effects, interference from other electronic devices, and node mobility. In addition, the video coding standards, including MPEG-4 and H.264, are designed to achieve high compression efficiency at the expense of the error resilience. The coding efficiency in these standards is achieved by using motion-compensated prediction to reduce the temporal and statistical redundancy between the video frames. This poses a severe problem, namely error propagation, where errors due to packet loss in a reference frame propagate to all of the dependent frames leading to visual artifacts that can be long lasting and annoying [START_REF] Martini | Content adaptive network aware joint optimization of wireless video transmission[END_REF]. On the other hand, the optimal flow control is the most reasonable operating rate that can be reliably supported along a path. If the operating rate is lower than the optimal transmission rate along a path, performance loss will occur due to the source coding inefficiency. On the contrary, if the operating rate is higher, many packets will be discarded due to channel over-pumping [START_REF] Qu | Cross-layer QoS control for video communications over wireless ad hoc networks[END_REF]. Thus, a flow control scheme is both desirable and necessary to achieve a satisfactory level of received video quality over wireless networks [START_REF] Zhu | Congestion-distortion optimized video transmission over ad hoc networks[END_REF]. In addition, the flow control scheme must be designed in distributed manner that is amenable to online implementation for wireless network [START_REF] Ge | A Cross-Layer Design Approach to Multicast in Wireless Networks[END_REF]. However, to the best of our knowledge, most of the current literatures has considered above two factors separately and independently. In order to achieve improved video quality supported by wireless networks, and to provide a more robust video delivery system, these two factors are jointly considered in this paper.

The rest of paper is organized as follows. In Section II, we propose a cross-layer distributed flow control algorithm. In Section III, an analytical rate-distortion optimized JSCC is proposed given the optimal transmission rate. And then, we present some selected simulation results for the proposed joint scheme transmission over wireless networks in Section IV, followed by concluding remarks in Section V.

II. DISTRIBUTED FLOW CONTROL ALGORITHM

A. Network Model

Consider this wireless multihop network whose links are denoted by L = {1..., l, ...L}. Let c l be the capacity of link l ∈ L and c = [c 1 ..., c l , ..., c L ] T . Let S = {1..., s, ...S} be the set of sources. Each source s ∈ S has n s potential available paths from the source to the destination. Let the L × 1 vector R s,i denotes the set of links used by source s ∈ S on its path i ∈ {1, 2, ..., n s }, whose lth element equals to 1 if path contains link l and 0 otherwise, and N s,i denotes the number of links on the path i. The set of all the available paths of user s is defined by

R s = [R s,1 , R s,2 , ..., R s,ns ] (1)
and the total paths in the network are defined by a routing matrix R,

R = [R 1 , ..., R s , ..., R S ] (2)
For each source s, let x s,i be the rate of source s on path R s,i , and

x s = ns i=1
x s,i be the total source rate. When each source s transmits at a total rate of x s , it attains a utility U s (x s ). Let

x = [x 1,1 , . . . , x n,n S ] T be the vector of all path rates of all sources. Our objective is to choose appropriate rates x so as to maximize the total utility s∈S U s (x s ):

max xs≥0 s∈S U s (x s ) (3) subject to x s = ns i=1 x s,i , Rx ≤ c, x s,i ≥ 0
In addition, each link has a contention resolution protocol based on the transmission persistence probability. Let L o (s) denotes the set of outgoing links from node s ∈ S, and N I (l) as the set of nodes whose transmissions cause interference to the receiver of link l, excluding the transmitter node of link, and L I (s) as the set of links whose transmissions get interfered from the transmission of node s, excluding the outgoing links from node s. Therefore, if the link l and a node in N I (l) transmit data simultaneously, the transmission of link l fails. If node s and a link l in L I (s) transmit data simultaneously, the transmission of link l also fails. Assuming each node s transmits data with a probability p s , when it determines to transit data, it chooses one of its outgoing paths with a probability q l , l ∈ L o (s). Consequently, link l ∈ L o (s) transmits data with a probability p l = p s q l , which is called persistence probability of link l. Therefore, the data rate on path i, x s,i , is obtained as minimum rate of link in the path:

x s,i (P s ) = min l∈[1,N s,i ] c l p l k∈N I (l) (1 - m∈Lo(k) p m ) (4)
where

P s = [p 1 , ..., p N s,i ].
Based on this, we can specify this wireless networks utility maximization with "contention" link:

max xs≥0 s∈S U s (x s ) (5) subject to x s = ns i=1
x s,i (P s )

Rx ≤ c, x s,i ≥ 0, 0 P s 1

B. Cross-Layer Optimal Control

In the case of multi-path flow control problem, many literatures have been proposed by introducing the variable of path price to maximum the total utility function of the system [START_REF] Lin | Utility Maximization for Communication Networks with Multi-path Routing[END_REF], [START_REF] Chen | Cross-layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless Networks[END_REF]. These works suggest ways to adapt the total source rate to congestion, but they don't specify how to distribute the total rate among the available paths. A naive approach is to simply split it evenly along paths that have the least current price. This algorithm, however, does not converge, e.g. when multiple paths have different path prices. Motivated by this approach, we can view the persistence probability as a special path price, the distributed optimal x s at each source can be adjusted according to the persistence probability of each link. Similarly, the persistence probability can also be adjusted according to current x s . Intuitively, the expected result will allocate the "right" amount persistence probability to the "right" links to alleviate the congestion, which may then induce an increase in end-to-end throughput of the whole system.

Therefore, we need to find an algorithm that distributively and adaptively control the flow rate, persistence probability and routing from the link and source aspects, respectively. Aiming for this, we propose a cross-layer optimal control (CLOC) algorithm as follows:

we assume that time is slotted, and the links are fixed within a time slot but independently change between different slots. During each time slot t, the following three units are carried out simultaneously.

• Step 1: Each link l receives flow rates x s,i (t) for all paths R s,i that contain link l, and computes a new persistence probability

p l (t + 1) = p l (t) + κ c l - s R s,i x p l (t) -κ k∈L I (t l ) ε k 1 - m∈Lo(t l ) p m 1 0 (6)
where the second term is the residual link capacity relative to current persistence probability and the third term is the interference penalty. t l is the transmitter node whose path contains link l, κ > 0, and

ε l =      0, if s x s,i (t) ≤ c l p l k∈N I (l) (1 - m∈Lo(k) p m ) 1, otherwise (7)
Informing new probability p l (t + 1) to all sources s whose path R s,i contains link l; and each source receives p r s,i = P T s R s,i from the network for all its paths R s,i , i = 1, 2, . . . , n s and decides the maximum persistence probability p r * s = max i=1,2,...,ns p r s,i (t). • Step 2: Updates the source rate x s (t + 1):

x s (t + 1) = U -1 s (p r * s (t))
Ms ms [START_REF] Fu | A Joint Source and Channel Coding Algorithm for Error Resilient SPIHT-Coded Video Bitstreams[END_REF] To these paths which do not have the maximum persistence probability, path rate x s,i (t + 1) on path R s,i is:

x s,i (t + 1) = x s,i (t) -γ(p r * s (t) -p r s,i (t)) + , γ > 0 (9)
To the path R s,j that has the maximum persistence probability, we set its rate as:

x s,j (t + 1) = x s (t + 1) - i∈[1,ns],i =j x s,i (t + 1) + ( 10
)
and then informs all the new flow rate x s,j (t + 1) to links l contained in path R s,i .

• Step 3: Over the chosen link, send an amount of bits to destination according to the rate determined by the rate control unit.

C. Convergence Theorem of CLOC

We first associate Lagrange multiplier for each of the constraints, and use the KKT optimality conditions for optimization [START_REF] Rockafellar | Monotone Operators and the Proximal Point Algorithm[END_REF], solving this problem is equivalent to satisfying the complementary slackness condition and finding the stationary points of the Lagrange.

L sys = L(x, P s , λ, λ) = s∈S U s (x s ) -λs (x s - ns i=1 x s,i (P s )) -λ T l (Rx -c) = ( s∈S U s (x s ) -λs x s ) + λs ns i=1 x s,i (P s ) -λ T l (Rx -c) ( 11
)
where λ = [ λ1 , λ2 , . . . , λS ], λ = [λ 1 , λ 2 , . . . , λ L ] T . By linearity of the differentiation operator, this can be decomposed into two separate maximization problems

max x 0 L x (x, λ) = s∈S U s (x s ) -λs x s (12) max Ps 0 L Ps ( λ, λ, P s ) = λs ns i=1 x s,i (P s ) -λ T l (Rx -c) = λs ns i=1 ( min l∈[1,N s,i ] c l p l k∈N I (l) (1 - m∈Lo(k) p m )) -λ T l p l (x l -c l ) (13)
The first maximization is already implicitly solved by the congestion control mechanism for different U s [START_REF] Xiao | Simultaneous routing and resource allocation via dual decomposition[END_REF], while the second maximization also need to solve which aims at allocating exactly the right persistence probability of each link to reduce the congestion at the network bottlenecks. Here, we focus on proving the convergence of the persistence probability problem.

Because max L Ps (P s ) is a typical non-concave/convex problem, it is difficult to take the derivative of L Ps (P s ) with respect to p l directly. To get around the difficulty, we take logarithm operator on L Ps (P s ) to get L P ( P ), that is

L Ps ( P s ) = min l∈[1,N s,i ] ns i=1 log(c l p l k∈N I (l) (1- m∈Lo(k) p m ))+ log p l (x l -c l )
, where pl = log p l . In Appendix I, we will show that the partial Lagrange is a strictly concave function of a logarithmically transformed probability vector. So we can decompose that

L Ps ( P s ) = min l∈[1,N s,i ] ns i=1 log c l p l k∈N I (l) (1 - m∈Lo(k) p m ) + log p l (x l -c l ) = ns i=1 log c l p l k∈N I (l) 1 - m∈Lo(k) p m - n∈L I (t l ) c n p n k∈N I to (n),k =t l 1 - m∈Lo(k) p m + log p l c l - s R s,i x (14)
Assuming ε l as [START_REF] Wang | Multiple-Description Coding for Overlay Network Streaming[END_REF], taking the derivative of L Ps ( Ps ) with respect to Ps , we have

∇ l L Ps ( Ps ) = c l - s R s,i x -p l k∈N I (l) 1 - m∈Lo(k) p m ε k 1 - m∈Lo(t l ) p m = c l - s R s,i x -p l k∈L I (t l ) ε k 1 - m∈Lo(t l ) p m ( 15
)
Coming back to the P s solution space instead of pl , it is easy to verify that the derivate of

L Ps (P s ) with respect to p l is ∇ l L Ps (P s ) = c l - s R s,i x p l - k∈L I (t l ) ε k 1 - m∈Lo(t l ) p m (16)
Therefore, the logarithmic change of variables simply scales each entry of the gradient by p l : ∇ l L Ps (P s ) = ∇ l L Ps ( Ps )/p l . We now use the subgradient method [START_REF] Low | A duality model of TCP and queue management algorithms[END_REF], with a constant step size κ, to maximize L Ps (P s ) This is the exact Step 1 in the CLOC algorithm. Substituting the known equation into x s (t+1) =

p l (t + 1) = p l (t) + κ∇ l L Ps (P s ) = p l (t) + κ c l - s R s,i x p l (t) -κ k∈L I (t l ) ε k 1 - m∈Lo(t l ) p m 1 0 (17)
U -1 s p r * s (t)
Ms ms to compute the total rate of s at t + 1, the following is the same as the proof in [START_REF] Lin | Utility Maximization for Communication Networks with Multi-path Routing[END_REF]. Since x s,i can be turned into a concave function in P s , each constraint

x s ≤ ns i=1 x s,i (P s )
is upper bound constraint on a convex function in (x, P s ), problem (5) can be turned into maximizing a strictly concave objective function over a convex constraint set [START_REF] Zhou | Cross-layer rate control, medium access control and routing design in cooperative VANET[END_REF]. Therefore, the established convergence is towards the global optimum. It should be noted that when path number is small, few rounds of the CLOC algorithm is needed, hence lower delay for rate control and routing acquisition; when path number is large, however, the distributed algorithm may calculate too many possibilities for each potential paths, and the total video transmission may be further restricted by the long delay in each path. In order to resolve this problem, we choose the first three paths and re-allocate the total probability among them in practical implementation.

III. JOINT SOURCE-CHANNEL CODING

A. The Architecture of JSCC

The proposed coding architecture contains two parts as shown in Fig. 1. Unit-1 uses the 3-D SPIHT (3-D Set Partitioning In Hierarchical Trees) codec that generates independent embedded streams, while Unit-2 uses the coding constraints and channel condition to pack the bit-streams into pack-streams of quality layers. This two-units structure collects incremental contributions from the various streams into SNR scalable quality layers in a way similar to that of embedded block coding with optimized truncation. The streams and rate-distortion functions generated by Unit-1 can be processed independently to channel conditions. The source and channel allocation algorithm in Unit-2 must be efficient to cope with the time varying channel conditions.

Unit-1 uses an embedded coding technique that generates multiple independent embedded streams. A video is divided into several independently encoded for additional functionality in Unit-1. The video coder divides the 3-D wavelet coefficients into multiple blocks according to their spatial and temporal relationships, and then encodes each block independently using the 3-D SPIHT algorithm [START_REF] Cho | A full-featured, error-resilient, scalable wavelet video codec based on the set partitioning in hierarchical trees (SPIHT) algorithm[END_REF]. The proposed method allocates source bits to each embedded bitstream to minimize the total distortion of a video clip. Moreover, the video scalability is imparted by the layering concept and the scalable stream is organized into quality layers.

B. Packet-Loss Pattern Approximation

For the RS code operating on b-bit symbols, the maximum block length is 2 b -1 symbols.

For a (n, k) systematic RS code with a block length n, the source symbol is k. The first k encoded symbols are source symbols correctly when the number of loss symbols is less than the minimum distance d min = n -k + 1 of the code. The performance of an RS decoder P c (n, k) can be characterized by the code correct probability

P c (n, k) = n-k m=0 P (n, m) ( 18
)
where P (n, m) is the probability of m erasure within a block of n symbols. In a binary symmetric channel without memory, we have

P (n, m) =   n m   P m B (1 -P B ) n-m ( 19
)
where P B is the mean packet loss rate. For channels with memory, it is more complicated to calculate the P (n, m). Here, we use a two-state Markov model (i.e.Gilbert model) to simulate the bursty packet loss behavior. The two states of this model are denoted as G (Good) and B (Bad). In state G, packets are received correctly and timely, whereas, in state B, packets are assumed to be lost. This model can be described by the transition probabilities P GB from state G to B and P BG from state B to G. The then the average error probability P B is given by

P B = P GB P GB + P BG (20)
and the average burst length

L B = 1 P BG (21)
which is the average number of consecutive symbol errors. The Markov model is a renewal model, and such models are determined by the distribution of error-free intervals, known as gap.

Let gap of length σ be the event that after a lost packet, σ -1 packets are received correctly and then a packet is lost again. The gap density function g(σ) gives the probability of a gap length σ. The gap distribution function G(σ) gives the probability of the gap length greater than σ -1.

These functions can be derived as [START_REF] Kim | Distrubuted Video Streaming Using Multiple Description Coding and Unequal Error Protection[END_REF] g

(σ) =    1 -P BG , σ = 1 P BG (1 -P GB ) σ-2 P GB , σ > 1 (22) G(σ) =    1 -P BG , σ = 1 P BG (1 -P GB ) σ-2 , σ > 1 (23)
Let R(n, m) be the probability of m -1 erroneous symbols within the next n -1 symbols following an erroneous symbol. It can be calculated using the recurrence

R(n, m) =      G(n), m = 1 n-m+1 σ=1 g(σ)R(n -σ, m -1), 2 ≤ m ≤ n (24)
Then the probability of errors within m a block of n symbols is

P (n, m) =        n-m+1 σ=1 P B G(σ)R(n -σ + 1, m), 1 ≤ m ≤ n 1 - n m=1 P (n, m), m = 0 (25)
C. Proposed JSCC Fig. 2 shows how multiple encoded sequences of different quality levels are protected based on systematic RS codes. For notational convenience, we define the bit-plane 1 as the highest bit-plane and the bit-plane I s as the lowest bit-plane to be sent for stream-s. As to the definition of the bit-plane, we employ the priority classification used in [START_REF] Kim | Distrubuted Video Streaming Using Multiple Description Coding and Unequal Error Protection[END_REF]. Let N s be the number of packets that are used to send the combined source data and redundancy for stream-s in a GOP (Group of Picture) and L be the packet size in bytes. In this scheme, the bits belonging to bit-plane i (1 ≤ i ≤ I s ) are k s,i packets and the remaining c s,i = N s -k s,i packets are filled with channel coding redundancy. In other words, the source data for bit-plane is protected by RS code (N s , k s,i ).

We denote the proposed coding scheme is performed on GOP basis. We define the total number of packets at period t to be sent from all of the sources for a GOP period N (t) as

N (t) = x(t) × N GOP F × L (26)
where x(t) is the total coding rate in bytes/s at period t for the combination of data and redundancy for all sources; N GOP is the number of frames in one GOP; F is the frame rate in frames/s. In this framework, we assume that source-s transmits stream-s to the receiver for s ∈ S.

Then the proposed algorithm divides N ( t) into {N 1 (t)...,N s (t),...N S (t)} so as to maximize the expected quality at the receiver, where N s (t) represents the total number of packets transmitted by source-s at GOP period t for s ∈ S. Taking account into the rate of source s, N s (t) should satisfy the following condition:

N s (t) ≤ x s (t) × N GOP F × L (27)
where x s (t) is the total rate of source-s at the GOP period t, and it can be obtained from the CLOC algorithm introduced in Section II-B.

P SN R s (i)
is the expected quality at the receiver when the receiver decodes up to the ith bitplane for stream-s; I s is the last bit-plane sent from source-s.

Each source independently runs the proposed flow rate algorithm to get its optimal number of packets to transmit for a GOP period, using the information contained in the control packets that the receiver sends to all sources. The proposed algorithm tries all possible combinations of (N s , K s ) that satisfy the constraints in (28) and choose one that maximizes the expected quality. In this work, we have implemented a simple algorithm for finding the global optimal value through exhaustive search. In our future work, we will explore more efficient optimization algorithm to achieve lower complexity.

IV. SIMULATION RESULTS AND DISCUSSION

A. Experimental Setup

In order to provide a representative evaluation of system performance, for each simulation run we generate a random topology in the disc of 500m-by-500m square as a 2D Poisson point process with total number of nodes equal to 15. Nodes within 150 m of each other are considered neighbors, and can communicate directly. We assume that if the distance between the transmitter node and the receiver node is less than 50m, the receiver node gets interference from the transmitter node. For the link from node i to node j (l ij ), its capacity c l ij is computed as:

c l ij = BW 2 log(1 + ζSIN R ij ) (29)
where signal-to-interference-plus-noise-ratio SIN R ij is calculated assuming simultaneous fixed power transmission at all nodes, BW is the double-sided bandwidth for transmission, and the coding gain ζ < 1 indicates the performance gap of RS coder with respect to Shannons information theoretical limit.

In the following simulations, we set U s (x s ) = log 10 x s , step-size κ = γ = 0.1. Standard video sequence, Weather Forecast, is used at F = 30fps, N GOP = 30. We use 3 levels of spatial wavelet decomposition with 9-7 biorthogonal filters and 3 levels of temporal wavelet decomposition with a Haar filter. The number of the bit-plane I s for each source is 3 for all experiments. For simplicity, we use the constant bit rate (CBR) model to represent video traffic.

In the following, assuming two streams transmit data simultaneously from the two sources to two receivers. Fig. 3 shows the topology and routing for sources (node 1 and node 4) simultaneously stream to receivers (node 12 and node 15) over different paths. Fig. 4 shows the convergence of link persistence probabilities regulated by CLOC for the potential links from node 1 (Note:

the initial persistence probability of each link is random distributed from 0 to 1).

Given a randomly generated topology, we initially choose a source-destination pair and stream the video from the source to the destination using the path with the highest transmission rate as described in Section II. During transmission, the environment are updated every one GOP transmission which can cause changes in the transmission rate and channel conditions. During successive one GOP transmission interval, the environment keeps constant. In order for objective comparison, PSNR (Peak Signal-to-Noise Ratio) at the receiver relative to the original video sequence is used and its definition is

P SN R(dB) = 10 log 10 ( 255 2 M SE ) ( 30
)
where MSE is the mean-square error between the original and the decoded luminance frame.

B. Selected Simulation Results and Discussions

To demonstrate the effectiveness of our proposed rate control algorithm, we use a representative fixed source coding rate R f = 96Kbps and when the rate exceeds the current optimal transmission rate available for the selected source-destination pair, it will drop the subsequent encoded packets.

In Fig. 5, we show a performance comparison between our proposed rate control scheme and the drop-tail scheme in the scenario where packet losses are caused only by channel over-pumping 1 .

It should be noted that due to the use of CBR encoding, the video quality is not constant and varies periodically. In Fig. 5, the average PSNR using the proposed rate control scheme is 35.33 dB while it is 34.70 dB for the case of no rate control, thus, 0.63 dB performance gain can be 1 Here, we assume that no transmission errors occurred achieved using the proposed rate control scheme. From the channel profile, illustrated in Table I, we can see that for GOP No. 1, No. 2, and No. 4, the optimal transmission rate is higher than the fixed 96 Kbps. Thus, using rate control can fully exploit the optimal transmission rate resulting in improved performance compared to using a fixed-rate coding scheme. On the other hand, for GOP No. 3, it is obvious that the fixed source coding rate is higher than the optimal transmission rate. Therefore, packet losses will occur when the transmission buffer is full resulting in the last couple of frames being lost which cause substantial performance degradation.

A lost frame is concealed by just copying the previous frame and if several consecutive frames are lost, the degradation will be even more serious since the concealed frames are then used as correctly received frames to conceal the subsequent lost frames. This results in substantial error propagation. For example, in Fig. 5, we can see that there is substantial performance degradation around the 90th frame for the no-rate control case due to channel over-pumping. Furthermore, although the performance degradation caused by the channel over-pumping packet losses has been partially compensated using passive error concealment, the performance is still not as good as using the rate-control scheme. To evaluate the performance of the joint flow control and JSCC approach, different simulations are conducted for the test sequence. These results allow us to observe the relative performance of the proposed error-resilience approach compared to the two fix-rate schemes where either no channel coding or the RS (15, 9) code is used exclusively. Furthermore, the proposed rate control scheme is used for all the above three approaches. In Fig. 6, we illustrate a plot of PSNR versus the frame number for the test sequence and the corresponding channel profile is illustrated in Table II. Obviously, the proposed JSCC scheme can be seen to achieve a much higher performance in terms of end-to-end PSNR compared to the no channel coding and fixed RS [START_REF] Qu | Cross-layer QoS control for video communications over wireless ad hoc networks[END_REF][START_REF] Lin | Utility Maximization for Communication Networks with Multi-path Routing[END_REF] schemes. From the Fig. 6, we can see that although using the RS (15, 9) code can provide protection, a substantial performance loss is observed compared to the proposed JSCC scheme which is so flexible that it can achieve an optimal value according to current condition. In addition, although using no channel coding results in the best source coding efficiency, however, there are no error correcting capabilities which can be used to combat transmission errors.

Therefore, the corresponding performance is considerably worse than the JSCC scheme.

In order to provide a more comprehensive evaluation of the proposed joint scheme, in Table III, we repeat the results for other QCIF video sequences under the same simulation configuration as the previous experiments (Note: method 1 is only JSCC without rate control, method 2 is only rate control without JSCC, method 3 is the joint flow control and fixed RS (15,9) and method 4 is proposed joint flow control and JSCC). From Table III, it can be observed that the proposed joint rate control and JSCC scheme has considerable performance advantage comparing to the other competitive methods, which is due to the proposed scheme has the characteristics of network-adaptive and error-resilient. In addition, we also can observe that the imposed bit-plane I s and packet loss P B do play a important role. In particular, as the I s gets larger and the P B becomes smaller, the performance of the proposed scheme improves. It should be noted that all the simulation results in this table have been obtained using 300 runs in order to obtain statistically meaningful average values.

V. CONCLUDING REMARKS

In this paper, we use cross-layer technique to maximize the perceived video quality by combining distributed flow control with joint source-channel coding. At first, we propose a crosslayer distributed flow control scheme which can dynamically control the optimal transmission rate for wireless communications from source to destination. And then, we provide an analytical ratedistortion optimized joint source-channel coding approach to optimally select the channel coding strategy given the optimal transmission rate obtained from the proposed flow control scheme and the prevailing channel condition. Finally, the simulation results demonstrate the effectiveness of our proposed approach for multiple video streams over wireless multihop networks.

we obtain the Hessian

H l = -p l ( k (z lk ) + c l p l ) 2 (( k z lk + c l p l )diag(z l ) -z l z T l ) (31)
where z lk = exp( pl ) + c l p l k∈N I (l)

Fig. 1 .

 1 Fig. 1. The architecture of JSCC.

Fig. 2 .

 2 Fig. 2. Packetization of source-channel bits of different bit-layers for stream s.

Fig. 3 .

 3 Fig. 3. An example for wireless multihop network with 15 nodes randomly placed in a 500m-by-500m area. Lines indicates the link between two neighboring nodes. Video traffics are streamed from node 1 to node 12 and node 4 to node 15.

16 Fig. 4 .

 164 Fig.4. Convergence of link persistence probabilities for node 1, corresponding to the same setting in Fig.3.

Fig. 6 .

 6 Fig.6. Performance comparison between the proposed JSCC scheme with the representative fixed channel coding and without channel coding scheme.

( 1 -+ c l p l ) 2 +

 12 m∈Lo(k)p m ), and z l is a column vector [z l1 , z l2 , . . . , z lL ] T . Matrix H l is indeed negative definite: for all vectors v,v T H l v = -p l ( k (z lk ) + c l p l )( k∈N I (l) p m )z lk ) 2 ( k z lk + c l p l ) 2 < 0 (32)This is because the Cauchy Schwarz inequality(a T a)(b T b) ≥ (a T b) 2 .Therefore, L Ps ( Ps ) is a strictly concave function of Ps , and its Hessian is a negative definite block diagonal matrix diag(H 1 , H 2 , . . . , H L ).

  (t), j) is the probability that j packets are lost out of N s (t) packets sent by source-s;

		Is	Ns-k s,l-1	Is
				P (N s (t), j)	P SN R s (i)	(28)
	s∈S	l=1	j=Ns-k s,l +1	i=l
	subject to	N s (t) = N (t),
			s∈S
			N s (t) ≤ xs(t)×N GOP F ×L
	P (N s

Now, we can state our source and channel allocation algorithm as follows: Given x s (t), the proposed algorithm finds N s (t) and K s (t) = (k s,1 (t), k s,2 (t), ..., k s,Is (t)) for s ∈ S, that maximize the expected quality at the receiver given by P SN R(t) =

  drop-tail scheme for comparison which does not use rate control. More specifically, it employs a

		40
		38
	PSNR(dB)	34 36
		32
			With Rate Control
		30	Without Rate Control
		0	20	40	60	80	100	120
				Frame Number
	Fig. 5. Performance comparison between using rate control and without rate control (fixed source coding 96Kbps)

ACKNOWLEDGMENTS

This work is supported by the International Project PRA-SI (financed by France and China government) under Grant No. SI04-03, the Key Project of Nature Science Foundation of Jiangsu (China) under Grant BK2007729 and the Climbing Plan in NJUPT under Grant NY207061.

Moreover, we also thank the anonymous reviewers for insightful comments and suggestions.

APPENDIX I PROOF OF STRICTLY CONCAVE FUNCTION

Taking derivatives again, for each of the nonlinear


Liang Zhou

Baoyu Y Zheng

Jingwu W Cui

Benoît Geller

Anne Wei

Shan Xu

Cross Layer Rate Control, Medium Access Control and Routing Design in Cooperative Multi-Hop Wireless Networks

Keywords: cooperative, wireless network, multi-hop, medium access control, rate control, routing

In this paper, we address the rate control, the medium access control (MAC) and the routing problem for cooperative multi-hop wireless networks (MHWN) in the framework of the utility function maximization. Compared to its counterpart in traditional wireless network, control method in the cooperative wireless network is much more complex, which is due to the constraints arising from the cooperation among the users and the contention for the wireless channel access. At first, we construct a general mathematics model for the cooperative MHWN. And then, we develop a cross-layer solution which consists of the link capacity detection by adjusting persistence probability at the MAC layer, the flow rate control by achieving the maximal utility at the transport layer and the optimal routing at the network layer. This proposal is designed in distributed manner in order to support a simple and efficient implementation for MHWN. Finally, fairness issue for the cooperative network is presented to improve the practical performance of the proposed solution. The simulation results show the effectiveness of the proposed solution for the cooperative network.

I. INTRODUCTION

In a wireless cooperative communication system, each user is assumed to transmit data and act as a cooperative agent for another user. That is to say, each user transmits both its own bits as well as some information for its partner [START_REF] Nosratinia | Cooperative communication in Wireless Networks[END_REF]. The idea of cooperative network is first proposed to handle "flash crowds" on the Internet, where end-hosts cooperate in order to improve the overall network performance [START_REF] Yao-Win | Cooperative Communications in Resource-Constrained Wireless Networks[END_REF].

In recent years, some cooperative strategies for content delivery and sharing in wireless network have been proposed [START_REF] Scaglione | Cooperative communications in mobile ad hoc networks[END_REF][START_REF] Jakllari | On broadcasting with cooperative diversity in multi-hop wireless networks[END_REF][START_REF] Sadek | Multinode Cooperative Communications in Wireless Networks[END_REF]. However, most of research in this area is to optimize physical layer performance without considering much detail about how cooperation interacts with higher layers and improves network performance. Specially, there is no specific solution describing how to solve the data flow movement problem over multiple hops in this architecture. In fact, since the cooperative network is a classic multisource-multi-path system, one of the most challenge issues is the flow rate control: the Internet is based on an end-to-end paradigm, where the transport protocol (e.g. TCP) instances at the endpoints to detect overload conditions at intermediate nodes. When congestion occurs, the source reduces flow rate [START_REF] Yuan | A Cross-Layer Optimization Framework for Multihop Multicast in Wireless Mesh Networks[END_REF].

However, cooperative network is usually a distributed dynamic system and the congested nodes might not be adjusted at all when the sources react to the congestion.

In this paper, we jointly formulate the rate control, medium access control and routing problem for cooperative multi-hop wireless networks (MHWN), and it is designed in distributed manner in order to support a simple and efficient implementation for MHWN. The fundamental purpose is to decompose the utility function into a flow control problem which determines the total source rate, and a division problem which describes how to split the total rate among a set of least congested paths according to the link persistence probability. The main contributions of this research are showed as follows: Firstly, we construct a general multi-source-multi-path model for this cooperative MHWN. Secondly, we develop a cross-layer solution which consists of the link capacity detection by adjusting persistence probability at the MAC layer, the flow rate control by achieving the maximal utility function value at the transport layer and the optimal routing at the network layer. The realization of joint rate control, MAC control and routing for the specific cooperative MHWN system is the highlight of this paper. Finally, fairness issue for the cooperative network is presented to improve the practical performance of the proposed solution.

The remainder of this paper is organized as follows. Section II constructs a general mathematics model for the cooperative MHWN. Based on the problem analysis, a joint optimal rate control, medium access control and routing algorithm is proposed in Section III. In Section IV, we present numerical results using the proposed algorithm, followed by the concluding remarks in Section V.

II. SYSTEM MODEL

The system consists of a set of N nodes with same computation and transmission capabilities, communicating through bidirectional wireless links between each other. There are wireless gateways providing access to the other networks (i.e.,Internet), and the system architecture is composed of such two kinds of communications as Node-to-Gateway and Node-to-Node, as shown in Fig. 1. The characteristics of the wireless cooperative architecture and its differences with the traditional always-connected model motivate the need to revisit the design of the protocols designed for wired infrastructure. In this paper, we employ the cooperative protocol introduced in [START_REF] Gentian | On Broadcasting with Cooperative Diversity in Multi-Hop Wireless Networks[END_REF], which designs a network-wide broadcasting protocol that exploits cooperative diversity and addresses the challenges of: (a) enabling cooperation and (b) exploiting the diversity benefits due to cooperation.

Consider this wireless network whose links are denoted by L = {1, 2, ...L}. Let c l be the capacity of link l ∈ L and c = [c 1 , c 2 , ..., c L ] T . Let S = {1, 2...S} be the set of sources. Each source s has n s potential available paths from the source to the destination. Let the L × 1 vector R s,i denotes the set of links used by source s ∈ S on its path i ∈ {1, 2, ..., n s }, whose lth element equals to 1 if path contains link l and 0 otherwise, and N s,i denotes the number of links on the path i. The set of all the available paths of user s is defined by

R s = [R s,1 , R s,2 , ..., R s,n s ] (1)
and the total paths in the network are defined by a routing matrix R,

R = [R 1 , R 2 , ..., R S ] (2)
For each source s, let x s,i be the rate of source s on path R s,i , and

x s = n s i=1
x s,i be the total source rate.

Let m s ≥ 0 and M s ≤ ∞ be the minimum and maximum rates, respectively, i.e., m s ≤ x s ≤ M s . When each source s transmits at a total rate of x s , it attains a utility U s (x s ). We assume that U s : R + → R is continuous, increasing and strictly concave. Let

x = [x 1,1 , . . . , x 1,n1 , x 2,1 , . . . , x 2,n2 , . . . , x n,1 , . . . , x n,nS ] T ∈ R R + (3)
be the vector of all path rates of all sources. Our objective is to choose rates x so as to maximize the total utility

s∈S U s (x s ): max x s ≥0 s∈S U s (x s ) (4) subject to x s ≤ ns i=1 x s,i , Rx ≤ c x s,i ≥ 0, m s ≤ x s ≤ M s
However, in the cooperative system, each node and each link has a contention resolution protocol based on the transmission persistence probability. Let L out (s) denotes the set of outgoing links from node s ∈ S, N I to (l) as the set of nodes whose transmissions cause interference to the receiver of link l, excluding the transmitter node of link, and L I f rom (s) as the set of links whose transmissions get interfered from the transmission of node s, excluding the outgoing links from node s. Therefore, if the transmitter of link l and a node in N I to (l) transmit data simultaneously, the transmission of link l fails. If node s and the transmitter of a link l in L I f rom (s) transmit data simultaneously, the transmission of link l also fails. Assuming each node s transmits data with a probability p s , when it determines to transit data, it chooses one of its outgoing paths with a probability q l , l ∈ L out (s). Consequently, link l ∈ L out (s) transmits data with a probability p l = p s q l , which is called persistence probability of link l. Therefore, the data rate on path i, x s,i , is obtained as minimum rate of link in the path:

x s,i (P s ) = min l∈[1,Ns,i] c l p l k∈N I to (l) (1 - m∈Lout(k) p m ) (5)
where

P s = [p 1 , ..., p N s,i ], P = [P 1 , P 2 , ..., P S ].
With the above analysis, we can specify the cooperative wireless networks utility maximization with "contention" link:

max x s ≥0 s∈S U s (x s ) (6) subject to x s ≤ n s i=1 x s,i (P s ) Rx ≤ c x s,i ≥ 0, m s ≤ x s ≤ M s , 0 P 1 III. JOINT OPTIMAL CONTROL ALGORITHM
In this section, we present a Joint Optimal Control (JOC) algorithm to jointly optimize rate control, medium access control and routing for the aforementioned cooperative wireless networks based on the cross-layer design.

A. JOC Algorithm

In the case of multi-path flow control problem, many literatures have been proposed by introducing the variable of path price to maximum the total utility function of the system [START_REF] Lin | Utility Maximization for Communication Networks with Multi-path Routing[END_REF][START_REF] Wang | Optimal Flow Control and Routing in Multi-Path Networks[END_REF][START_REF] Chen | Cross-layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless Networks[END_REF]. In [START_REF] Wang | Optimal Flow Control and Routing in Multi-Path Networks[END_REF], the author solves the optimal congestion control problem by taking the path price into consideration, and the optimal source rate x * s is given by s,i of source s. The above equation suggests a way to adapt the total source rate to congestion, but it does not specify how to distribute the total rate among the available paths. A naive approach is to simply split it evenly along paths that have the least current price. This algorithm, however, does not converge, e.g. when multiple paths have different path prices. In the cooperative wireless system, we can view the persistence probability as a special path price, the distributed optimal x s at each source can be adjusted according to the persistence probability of each link. Similarly, the persistence probability can also be adjusted according to current x s . Intuitively, the expected result will allocate the "right" amount persistence probability to the "right" links to alleviate the congestion, which may then induce an increase in end-to-end throughput of the whole system. Therefore, we need to find an algorithm that distributively and adaptively control the flow rate, persistence probability and routing from the link and source aspects, respectively.

x * s = R * s,i ∈R * s x * s,i = U s (p
JOC Algorithm:We assume that time is slotted, and the links are fixed within a time slot but independently change between different slots. During each time slot t, the following three units are carried out simultaneously until convergence.

• MAC: Each link l receives flow rates x s,i (t) for all paths R s,i that contain link l, and computes a new persistence probability

p l (t + 1) = p l (t) + κ c l - s R s,i x p l (t) -κ k∈L I f rom (t l ) ε k 1 - m∈L out (t l ) p m 1 0 ( 7
)
t l is the transmitter node whose path link l, κ > 0, and

ε l =      0, if s x s,i (t) ≤ c l p l k∈N I to (l) (1 - m∈Lout(k) p m )

1, otherwise

Informing new probability p l (t + 1) to all sources s whose path R s,i contains link l; and each source receives p r s,i = P T s R s,i from the network for all its paths R s,i , i = 1, 2, . . . , n s and decides the maximum persistence probability p r * s = max i=1,2,...,n s p r s,i (t). • Rate control: Updates the source rate x s (t + 1):

x s (t + 1) = U s (p r * s (t))
Ms ms [START_REF] Lin | Utility Maximization for Communication Networks with Multi-path Routing[END_REF] To these paths which do not have the maximum persistence probability, path rate x s,i (t + 1) on path R s,i is:

x s,i (t + 1) = x s,i (t) -γ(p r * s (t) -p r s,i (t)) + , γ > 0 (9)
To the path R s,j that has the maximum persistence probability, we set its rate as:

x s,j (t + 1) = x s (t + 1) - i∈[1,n s ],i =j x s,i (t + 1) + ( 10
)
and then informs all the new flow rate x s,j (t + 1) to links l contained in path R s,i .

• Routing: Over the chosen link, sending an amount of bits to destination according to the rate determined by the rate control unit.

Note that, the persistence probability of the link l depends on two aspects: one is the current flow rate relative to link capacity, while the other one is the current link affected by other users. In the case of path rate, the rates on all paths that have less than the maximum persistence probability are reduced by an amount proportional to the absent probability, and the rate on the maximum probability path is increased, so that the new rates on all paths sum up to the new total source rate determined in the flow control decision.

B. Performance Evaluation

We first associate Lagrange multiplier for each of the constraints, and use the KKT optimality conditions for optimization [START_REF] Rockafellar | Monotone Operators and the Proximal Point Algorithm[END_REF][START_REF] Chiang | To layer or not to layer: balancing transport and physical layers in wirless multihop networks[END_REF], solving this problem is equivalent to satisfying the complementary slackness condition and finding the stationary points of the Lagrange.

L sys = L(x, P, λ, λ) = s∈S U s (x s ) -λs (x s - ns i=1 x s,i (P s )) -λ T l (Rx -c) = ( s∈S U (x s ) -λs x s ) + λs n s i=1 x s,i (P s ) -λ T l (Rx -c) ( 11
)
where λ = [ λ1 , λ2 , . . . , λS ], λ = [λ 1 , λ 2 , . . . , λ L ] T . By linearity of the differentiation operator, this can be decomposed into two separate maximization problems

max x 0 L x (x, λ) = s∈S U s (x s ) -λs x s max P 0 L P ( λ, λ, P ) = λs ns i=1 x s,i (P ) -λ T l (Rx -c) = λs n s i=1 ( min l∈[1,N s,i ] c l p l k∈N I to (l) (1 - m∈L out (k) p m )) -λ T l p l (x l -c l )
The first maximization is already implicitly solved by the rate control mechanism for different U s [START_REF] Xiao | Simultaneous routing and resource allocation via dual decomposition[END_REF],

while the second maximization still need to be solved which aims at allocating exactly the right persistence probability of each link to reduce the congestion at the network bottlenecks. Here, we focus on proving the convergence of the persistence probability problem.

Because max L P (P ) is a typical non-concave/convex problem, it is difficult to take the derivative of L P (P ) with respect to p l directly. To get around the difficulty, we take logarithm operator on L P (P )

to get L P ( P ), that is L P ( P ) = min l∈[1,N s,i ] n s i=1 log(c l p l k∈N I to (l) (1 - m∈L out (k) p m )) + log p l (x l -c l )
, where pl = log p l . In appendix I, we will show that the partial Lagrange is a strictly concave function of a logarithmically transformed probability vector. So we can decompose that

L P ( P ) = min l∈[1,N s,i ] ns i=1 log c l p l k∈N I to (l) (1 - m∈Lout(k) p m ) + log p l (x l -c l ) = n s i=1 log c l p l k∈N I to (l) 1 - m∈L out (k) p m - n∈L I f rom (t l ) c n p n k∈N I to (n),k =t l 1 - m∈L out (k) p m + log p l c l - s R s,i x (12)
Assuming

ε l =      0, s x s,i (t) ≤ c l p l k∈N I to (l) 1 - m∈Lout(k) p m

1, otherwise

Taking the derivative of L P ( P ) with respect to pl , we have

∇ l L P ( P ) = c l - s R s,i x -p l k∈N I to (l) 1 - m∈L out (k) p m ε k 1 - m∈L out (t l ) p m = c l - s R s,i x -p l k∈L I f rom (t l ) ε k 1 - m∈L out (t l ) p m (13)
Coming back to the P solution space instead of P , it is easy to verify that the derivate of L P (P ) with respect to p l is

∇ l L P (P ) = c l - s R s,i x p l - k∈L I f rom (tl) ε k 1 - m∈Lout(tl) p m (14)
Therefore, the logarithmic change of variables simply scales each entry of the gradient by p l : ∇ l L P (P ) = ∇ l L P ( P )/p l . We now use the subgradient method [START_REF] Low | A duality model of TCP and queue management algorithms[END_REF], with a constant step size κ, to maximize L P (P )

p l (t + 1) = p l (t) + κ∇ l L P (P ) = p l (t) + κ c l - s R s,i x p l (t) -κ k∈L I f rom (t l ) ε k 1 - m∈Lout(tl) p m 1 0
This is the exact MAC unit in the JOC algorithm. Substituting the known equation into x s (t + 1) =

U s p r * s (t)
Ms m s to compute the total rate of s at t + 1, the following is the same as the proof in [START_REF] Lin | Utility Maximization for Communication Networks with Multi-path Routing[END_REF]. Since x s,i can be turned into a concave function in P , each constraint x s ≤ ns i=1

x s,i (P ) is upper bound constraint on a convex function in (x s , P s ), problem (6) can be turned into maximizing a strictly concave objective function over a convex constraint set. Therefore, the established convergence is towards the global optimum.

C. Extension: Fairness Issue for Cooperative Network

As stated previously, each user may transmit both its own bits as well as some information for its partner in the cooperative system, so how to keep the relative fairness between its own bits and partner's bits is a practical problem to be solved. In generic wireless network, the fairness strategy adopts the per-flow fairness, in which every flow has the equal "opportunity" to get to the destination, however, this is impractical in cooperative MHWN system. Here we can employ a content-based fairness strategy described in [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF], which is scalable and does not require maintenance of any state information beyond a time slot which is important in a dynamic network. As to the content-based fairness strategy, that is when each node receives the packets, it judges the packet content whether it has hold or not. If has, it will throw out the packet directly and inform his partner do not transmit after that moment. If not, it will receive the packet and adjust the flow rate and persistence probability as stated before.

In addition, utility functions can also be interpreted as the "knobs" to control the tradeoff between the fairness and efficiency. Different shapes of utility functions lead to different types of fairness defined in the economics literature. For example, a family of utility functions, parameterized by α ≥ 0, is proposed as

U α =    (1 -α) -1 x 1-α , if α = 1 log x, otherwise (15)
If α = 0, utility maximization reduces to system throughput maximization. If α = 1, proportional fairness among competing users is attained; if α = 2, then harmonic mean fairness; and if α → ∞, then maxmin fairness. To accommodate multi-class services and attain the desired tradeoff between efficiency and fairness, it is important that the utility maximization framework can handle general types of convex or concave utility functions [START_REF] Lee | Jointly optimal congestion and medium access control based on network utility maximization[END_REF].

IV. NUMERICAL RESULTS

An illustrative numerical example is summarized below for the network with end-to-end paths and logical links shown in Fig. 2. Each of the three sources has its utility function parameterized by α as in [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]. Due to page limit, we summarize the numerical results for the case of Node-to-Node. More specifically, there are two alternate paths from node A to C, i.e. a direct one-link path A → C, and an indirect two-link path A → B → C. We assume that if the distance between the transmitter node and the receiver node is less than 2d, the receiver node gets interference from the transmitter node.

Fig. 3 shows the convergence of link persistence probabilities regulated by JOC for the case of α = 3.

Fig. 4 shows the optimized source rates with each data point being the result of solving (6) for a given A number of interesting observations can be made from this graph. For example, since source 1 traverses more heavily interfered links, at the optimal rate allocation that maximizes the network utility, it is allocated the lowest data rate. However, as the value of α increases, the gap among the source decreases, and the fairness among sources is improved.

V. CONCLUDING REMARKS

In this paper, we have been focusing on resolving the rate control, the medium access control and the routing problem for cooperative MHWN. At first, we construct a general mathematics model for the cooperative MHWN based on problem formulation. And then, we develop a joint optimal control algorithm which consists of the link capacity detection by adjusting persistence probability at the MAC layer, the flow rate control by achieving the maximal utility at the transport layer and the optimal routing at the network layer. In addition, fairness issue for the cooperative network is presented to improve the practical performance of the proposed algorithm. (1 -

m∈L out (k) p m )z lk ) 2 ( k z lk + c l p l ) 2 < 0 (17)
This is because the Cauchy Schwarz inequality (a T a)(b T b) ≥ (a T b) 2 . Therefore, L P ( P ) is a strictly concave function of P , and its Hessian is a negative definite block diagonal matrix diag(H 1 , H 2 , . . . , H L ).

Fig. 1 .

 1 Fig. 1. The topology structure of the distributed cooperative MHWN.

Fig. 2 .

 2 Fig. 2. Physical and logical topologies

  supported by the International Project PRA-SI (financed by France and China government) under Grant No.SI04-03, and the Nature Science Foundation of China under Grant No.60372107. What's more, we also thank the anonymous reviewers for insightful comments and suggestions.

Fig. 3 .Fig. 4 . 1 - 2 +

 3412 Fig. 3. Convergence of link persistence probabilities


S-G Cai

A Ouahsine
email: ouahsine@utc.fr

H Smaoui

J Favier

Y Hoarau

An e cient implicit direct forcing immersed boundary method for incompressible flows

. Numerical simulations performed with the proposed method are in good agreement with those in the literature.

Introduction

Immersed boundary method (IBM) is a type of non-body-conforming method, which significantly simplifies the flow simulations with arbitrary complex boundaries. Our work is based on the Uhlmann's explicit direct forcing immersed boundary method [1], which is known not to precisely satisfy the non-slip boundary condition on the interface. To improve this, we propose a low computer-consuming implicit scheme in conjunction with the rotational incremental pressure-correction projection method of Guermond and Shen [2] for solving the incompressible Navier-Stokes equations. Numerical simulations of a two-dimensional flow over a circular cylinder at two di↵erent Reynold numbers are performed, which are in good agreement with the previous experimental and numerical results in the literature.

Numerical method

Rotational incremental pressure-correction projection method

Consider the incompressible Navier-Stokes equations

@u @t + r • (uu) = rp + 1 Re r 2 u (1) r • u = 0 (2)
where u, p, Re are the non-dimensionalized velocity vector, pressure, and the Reynolds number, respectively. The equations are discretized with finite di↵erence scheme on a staggered grid [3].

All the spatial derivatives are approximated by the second-order central di↵erence. The secondorder Adams-Bashforth scheme is used for the temporal discretization of convective term and the Crank-Nicolson scheme for the di↵usive term. This results in the following set of equations:

u n+1 u n t +  3 2 H(u n ) 1 2 H(u n 1 ) = Gp n+1 + 1 2Re L u n+1 + u n (3)
Du n+1 = 0 (4)
where H, G, D, L are the discrete convection, gradient, divergence and di↵usion operators, respectively.

The above equations are solved with the rotational incremental pressure-correction projection method [2], in which an auxiliary velocity u ⇤ is estimated with the pressure value at previous time level in the viscous step, and the pseudo pressure is used to project the predicted velocity into the divergence-free field. The two sub-steps are performed as:

u ⇤ u n t +  3 2 H(u n ) 1 2 H(u n 1 ) = Gp n + 1 2Re L(u ⇤ + u n ) (5) u n+1 u ⇤ t = G n+1 (6)
By taking the divergence of Eq. ( 6) and applying the incompressibility constraint (4), the pressure corrector is obtained

L n+1 = 1 t Du ⇤ (7)
The pressure is then advanced by

p n+1 = p n + n+1 1 2Re Du ⇤ (8)
Therefore, the preceding equations are solved in the order (5), ( 7), ( 6), (8) at each time step.

Direct forcing immersed boundary method

In the direct forcing immersed boundary method of Uhlmann [1], the force F n+1 is determined on the Lagrangian points such that the desired velocity U d is satisfied on the embedded boundary

F n+1 = U d U ⇤ t (9)
where the upper-case letters indicate the quantities evaluated at the Lagrangian locations, and U ⇤ is the estimated velocity by all the explicit terms in the momentum equation. Therefore, the non-slip boundary condition is not fully verified. As the Navier-Stokes equations are inherently implicit, we need to iterate the whole system such that F n+1 is calculated by the final divergencefree velocity U n+1 , which, however, is too cumbersome to perform.

In the present study, we propose to evaluate the force after the viscous step. Instead of iterating the whole system, we iterate the force within a small system coupled with the pressure poisson equation (PPE), which is often the most time-consuming part. As implied by Ji [4] that a considerable amount of computational time could be saved if the PPE is solved only once at each iteration within a time step no matter whether it is converged, since the intermediate pressure is not the true value. We follow this idea and iterate the small system in combination with GAMG (geometric algebraic multi-grid) pre-conditioner and BICGSTAB solver for the PPE by the library PETSc [START_REF] Balay | Modern Software Tools in Scientific Computing[END_REF]. The modified algorithm is as follows:

Prediction: u ⇤ u n t +  3 2 H(u n ) 1 2 H(u n 1 ) = Gp n + 1 2Re
L (u n + u ⇤ );

Initialization: u k = u ⇤ , k = 0; while TRUE do U k (s) = P x2⌦ f u k (x) h (x X(s)) x; F k+1 (s) = U d (s) U k (s) t ; f k+1 (x) = P X2 b F k+1 (s) h (x X(s)) s; L k+1 = 1 t Du ⇤ + Df k+1 ; u k+1 = u ⇤ tG k+1 + tf k+1 ; if ku k+1 u k k < ✏ and k k+1 k k < ✏ then u n+1 = u k+1 ; n+1 = k+1 ; break; else k = k + 1; end end Correction: p n+1 = p n + n+1 1 2Re
Du ⇤ .

The three-points discrete delta function of Roma et al. [START_REF] Roma | [END_REF] is employed for the regularization and interpolation.

h (r) = 8 > > > > < > > > > : 1 3h (1 p 3(r/h) 2 + 1), |r|  0.5h, 1 6h (5 3|r/h| + p 3(1 |r/h|) 2 + 1), 0.5h  |r|  1.5h, 0, otherwise.
(10)

Results

Flow over a stationary circular cylinder

In the present work, the two-dimensional simulations of flow around a circular cylinder at two di↵erent Reynolds numbers Re = 30, 185 are performed, with the initial uniform velocity u 1 = 1 and the cylinder diameter D = 1. The flow is simulated in a domain of [ 10D, 40D] ⇥ [ 15D, 15D]. Inlet boundary condition is set to uniform (u = u 1 , v = 0), while @u/@x = 0 is applied at the outlet plane. Free-slip conditions are assigned at lateral boundaries.

At Re = 30, the flow presents steady-state characteristics with a recirculating region in the wake of the cylinder. Whose dimensions are characterized by the length of the wake l, the distance a from the cylinder to the vortex center, the distance b between two symmetry vortex centers, and the angle ✓ of flow separation measured from x-axis. The wake properties in the present study is compared against previous experimental and numerical studies in Table 1 and proved to be in accord. The streamlines and vorticity contours for this flow are shown in Fig.

Conclusions

An implicit direct forcing immersed boundary method is developed with a small coupled system solved in an e cient way. The rotational incremental pressure-correction projection method is employed to enforce the incompressibility constraint. The accuracy of the proposed method has been proven by the numerical simulations and comparisons with the previous experimental and numerical result in the literature.

1 .Figure 1 :

 11 Figure 1: (a) streamlines at Re = 30, (b) vorticity contours at Re = 30, (c) vorticity contours at Re = 185, where all the contours levels are set from -3 to 3 in increments of 0.4.

Table 1 :

 1

		l/D a/D b/D	✓ o
	Coutanceau and Bouard [8] ? 1.55 0.54 0.54	50
	Pinelli et al. [7]	1.70 0.56 0.52 48.05
	Present	1.71 0.61 0.53 49.46

Comparison of experimental and numerical studies of steady-state wake dimensions for Re = 30, where experimental study is listed with ( ? ).

Content from this work may be used under the terms of the Creative Commons Attribution 3.0 licence. Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI. Published under licence by IOP Publishing Ltd 1

Acknowledgement

The first author acknowledge the China Scholarship Council for the financial support. The computations were performed on the computer cluster PILCAM2.