Channel Frequency Response Estimation for MIMO Systems with Frequency-Domain Equalization

Since its recent adoption for the uplink transmissions in the next-generation cellular systems 3GPP long-term evolution (LTE) and LTE advanced, single-carrier frequency-domain equalization (SC-FDE), an effective technique to mitigate the distortion induced by long-spanning intersymbol interference has seen a surge of interest in the research community. Implementation of SC-FDE in multiple-input multiple-output (MIMO) systems usually requires, in advance, the channel information in terms of the channel frequency response (CFR). In this paper, we present a training-based CFR estimation scheme, which is hardware efficient when integrated with SC-FDE and space-time coding (STC) inMIMO systems. A thoroughmean square error (MSE) analysis of this CFR estimation scheme is provided, where we consider linear estimators based on both least squares (LS) and minimumMSE (MMSE) criteria by assuming different knowledge of the channel statistics. More specifically, for the LS-based approach, we assume no a priori knowledge of the channel statistics is given other than the noise statistics, while for the MMSE-based method, we assume both the channel covariance matrix and the noise statistics are known. Given a constraint which effectively limits the transmit power of training signals, we also investigate the optimal design of training signals under both criteria. For the special case when the number of transmit antennas is equal to 2, we further demonstrate that the CFR estimation could be implemented in an adaptive manner by means of certain block-wise recursive algorithms. Extensive simulation results are provided, which demonstrate the efficacy of this CFR estimation scheme.

Introduction
The severe frequency selectivity often characterizing wideband radio channels would inevitably induce intersymbol interference (ISI) which can span over many symbol intervals. High-speed broadband wireless systems targeting data rate of tens of megabits or beyond should be, as a result, designed to mitigate the effect of such intense ISI. Traditionally, time-domain equalization (TDE) is a popular approach to compensate for ISI in single-carrier communication systems. But for wideband channels, TDE becomes unattractive as its complexity grows exponentially with channel memory or it requires very long finite impulse response filters to achieve acceptable performance. An alternative approach is the single-carrier frequencydomain equalization (SC-FDE), which has the advantage of large reduction in the computational complexity due to the use of the computationally efficient fast Fourier transform (FFT) (see [1][2][3] for a tutorial treatment). Even compared with orthogonal frequency-division multiplexing (OFDM), a well-recognized multicarrier solution to combat channel delay spread which also uses FFT, single-carrier transmission with FDE can handle the same channels with similar performance and essentially the same overall complexity but smaller peak-to-average transmitted power ratio [1]. This is particularly advantageous to mobile terminals and mobile personal assistants, as it can greatly alleviate the requirements on the radio frequency hardware at the transmitter, such as the digital-to-analog converter and the power amplifier, to name a few. For that reason, a technology named single-carrier frequency division multiple access (SC-FDMA), which is essentially based on SC-FDE, has been 2 EURASIP Journal on Advances in Signal Processing · · · · · · · · · + + TX 1  Figure 1: Block diagram of the CFR estimation for MIMO system with STC and SC-FDE.
adopted for the uplink transmissions in the next-generation cellular systems 3 GPP long-term evolution (LTE) and LTE advanced [4]. SC-FDE has thus grasped more attention in both academic and industrial circles. SC-FDE has also been applied to multiple-input multiple-output (MIMO) communication systems. This, however, is often done jointly with space-time coding (STC), in order that the spatial diversity available in a MIMO system can be exploited to further mitigate the frequency selectivity, for example, [5][6][7][8][9]. For this case, properly designed ST block codes (STBCs) are generally required and there exist some works in that regard. For example, a time-reversal Alamoutilike STBC scheme with FDE was proposed firstly in [5]. This scheme is attractive as it can achieve full spatial diversity, and nearly full transmit rate if the cyclic prefix (CP) overhead is ignored. For SC-FDE in MIMO systems with more than 2 transmit antennas, a general block-level STC was proposed in [6] and a method based on quasi-orthogonal STBCs was proposed in [7].
Note that when performing FDE in MIMO systems, the channel frequency response between each transmit-receive antenna pair is usually required at the receiver to recover the transmitted signals [2,3]. To obtain such channel frequency response (CFR) knowledge, one approach is to obtain the channel impulse response (CIR) firstly and then transfer it back to the frequency domain through FFT processing. As a result, the CFR estimation problem merely reduces to the problem of estimating the CIR in MIMO systems, which has been vigorously investigated over the years, for example, see [10] and references therein. As an alternative, one can apply the FFT firstly, and then estimate the CFR directly afterwards. In fact, we notice that this alternative approach, or the CFR estimation problem, has been studied, for example, in [11] for systems with single transmit and single receive antenna, and in [12] for SC-FDE in ultrawideband communication systems. However, there does not seem to exist a lot of works which explore this alternative approach particularly for MIMO systems employing both STC and SC-FDE. This line of work merits interest on its own terms, for not only can it advance the existing knowledge on the subject of CFR estimation, but the CFR estimation scheme, when designed in a manner to be integrated with the techniques of STC and FDE in MIMO systems, can be amenable to system implementation, and has the potential to induce less hardware complexity and cost. This basically motivates our work as detailed next.
In this paper, we present and investigate a CFR estimation scheme for MIMO systems with both STC and FDE. In this scheme, training sequences are encoded in space and time in a similar manner as data sequences. (We notice that the CIR estimation for MIMO channels using ST codes was considered in [13,14].) In fact, the same set of coding hardware can be reused; thus, no additional hardware complexity is introduced at the transmitter and this is particularly suitable for mobile terminals. At the receiver, different from the traditional approach where CIR is obtained first then transferred to CFR, these training sequences are simply processed in a similar fashion as the data sequences, for example, CP removal and FFT processing. Following these procedures, estimation of the CFR can thus be done directly in the frequency domain. As the CFR estimation can make use of the existing FFT modules for FDE, fewer complexity or cost would be required at the receiver. This scheme is illustrated in Figure 1. Further, in this paper, we provide a thorough mean square error (MSE) analysis for the CFR estimation based on two criteria, least squares (LS) and minimum MSE (MMSE), by assuming different a priori knowledge of the channel statistics. More specifically, for the LS-based approach, we assume no a priori knowledge of the channel statistics is given other than the noise statistics, while for the MMSE-based method, we assume both the channel covariance matrix and the noise statistics are known. Under both criteria, we also study the optimal training sequence design by imposing a constraint on the transmit power of training sequences. Finally, we investigate the adaptive implementation of the proposed CFR estimation scheme for Alamouti-like transmissions. We provide several block-wise recursive algorithms to update the adaptive filter, and also study the convergence behaviors of these recursive algorithms.
The remainder of this paper is structured as follows. In Section 2, we describe the system model and the transmission scheme of the training sequences. In Section 3, we describe in detail the CFR estimation scheme for MIMO systems with more than 2 transmit antennas. We also investigate the optimal training sequence design under both LS and MMSE criteria. In Section 4, we focus on the special Alamouti case with 2 transmit antennas. We discuss an adaptive implementation of the CFR estimation scheme for this special case, and provide a brief convergence analysis. In Section 5, we provide extensive simulation results and also compare with others' work to demonstrate the efficacy of this estimation approach. Section 6 concludes this paper.
Notation. Throughout this paper, we use bold upper case letters to denote matrices and bold lower case letters to signify column vectors. Superscript {·} H , {·} * , and {·} T will be used to denote the complex conjugate transpose, conjugate, and transpose of a matrix or vector, respectively. We use diag{a} for a diagonal matrix with its diagonal vector given by a, and ⊗ for Kronecker product. I K denotes the identity matrix of size K × K, and 0 M×N for a zero matrix of size M × N . We use the subscript {·} F to denote the matrices or vectors in the frequency domain, and (·) + for the nonnegative part of a real-valued scalar or matrix.

Signal and System Model
We consider an ST-coded MIMO system equipped with N T transmit and N R receive antennas. With symbol rate T denote the equivalent baseband discrete-time CIR (including the transmit and receive filters as well as the multipath effect) between the pth transmit antenna and the qth receive antenna, where 1 ≤ p ≤ N T , 1 ≤ q ≤ N R , and ν is the channel order. We assume the channel is quasistatic, that is, its response remains time invariant within one ST-coded frame but can vary from frame to frame. We define N S vectors of dimension as the training sequences, where the symbols in s i belong to the same alphabet A, and L denotes the sequence length and is assumed to be at least equal to the number of multipaths, that is, L ≥ ν + 1. In this proposed CFR estimation scheme, the training sequence s i is encoded in space and time, using the same ST block encoder for data sequences, as depicted in Figure 1. As a result of this, the same set of hardware can be reused without additional complexity and cost. As for the ST encoder, we adopt the code design described in [6]. It is an extension of the original orthogonal STBCs in [15,16] for frequency-selective fading channels. This type of STBCs are capable of achieving full spatial diversity and are particularly amenable to FDE.
Without loss of generality, suppose the N S training blocks are ST coded in a manner that they are transmitted over N c = 2N S time slots, where a time slot is defined as the duration required to transmit a CP appended training block. Thus, the code rate is given by R = N S /N c = 1/2. There exist some sporadic code designs which could achieve code rate higher than 1/2. For example, when N T = 3 and 4, the code design with R = 3/4 can be found in [16]. However, it has been proved in [17] that with complex signal constellation and under the orthogonality assumption, R cannot be greater than 3/4 for N T > 2. For simplicity, in this part we only focus on the case of R = 1/2 for N T > 2. The special case of R = 1 for N T = 2 will be discussed in detail in Section 4.
be a set of N S × N T real-valued matrices of a full-rate generalized orthogonal STBC design for real symbols. Entries of Π i are either 0 or ±1, and Π i further satisfies the following conditions [18,Chapter 7]: Then, for the block-level generalized complex orthogonal STBC that is employed in our work, the code matrix, if denoted as G ∈ C NcL×NT , can be written as where Γ Ai and Γ Bi are both N c × N T matrices, and are, respectively, defined as In (2), P (1) L is an L × L permutation matrix which performs a reverse cyclic shift when applied to an arbitrary L × 1 vector, for example, suppose s = [s(0), s(1), . . . s(L − 1)] T , we then have Given the properties of Π i in (1), it can be easily verified that Γ Ai and Γ Bi have the following properties: Let G(:, i) denote the ith column of G that corresponds to the training blocks to be transmitted from the ith transmit antenna over N c time slots. For notational convenience, we express the ith column of G as follows: where i = 1, . . . , N T . To give an example of G, let us consider a code design with rate R = 1/2 for N T = 3, where N S = 4 and N c = 8. For this instance, G is illustrated as below s 1 (7) s 2 (7) s 3 (7) 4 EURASIP Journal on Advances in Signal Processing After ST coded, the transmission structure of the training sequences is shown in Table 1.
To avoid the interblock interference from preceding information or training sequences, a CP with a length of ν is inserted for each block before transmission. Then, at time slot k, the training sequence s p (k) is forwarded to the pth transmit antenna after CP insertion. The length of total training symbols from each transmit antenna, denoted as N b , is equal to N b = N c (L + ν), and its minimum length is N b = N c (2ν + 1) when L is chosen to be equal to ν + 1.

CFR Estimation for MIMO Transmissions (N T > 2)
At the receiver, symbols corresponding to the CP are discarded. Thus, the received signal at the qth receive antenna at time slot k can be written as where H (p,q) is an L × L channel matrix with its (k, l)th entry given by h (p,q) ((k−l) mod L), and n q (k) denotes the additive white Gaussian noise (AWGN) vector. It is easy to verify that H (p,q) is a circulant matrix. Thus, its eigen matrix is the FFT matrix, or in other words, its eigendecomposition can be written as F L is the orthonormal FFT matrix whose (k, l)th entry is given by where k = 1, . . . , L and l = 1, . . . , L. If denoting D where i = 1, . . . , L. Applying the FFT operations on both sides of (8), we obtain where is diagonal, we can rewrite (12) into Stacking N c blocks of received signals at the qth receive antenna, we have . . .
or in a more simplified form Collecting the received signals across all those N R receive antennas, we obtain the received data matrix where Thus, our task is to recover the CFR H F from (16).
Additionally, let us denote as the corresponding CIR associated with the qth antenna, and stack all the CIR across N R receive antennas in matrix ]. Therefore, the corresponding CIR estimate can be computed by where H F is the CFR estimate for H F . In the sequel, we discuss the linear CFR estimators based on both LS and MMSE criteria, along with the respective optimal designs of training sequences.

LS Estimator with Power Constraint.
For the convenience of ensuing analysis, we explicitly make the following assumption.
(A1) All noise components are assumed to be complex, independently and identically Gaussian distributed with zero mean and variance σ 2 n . Thus, EURASIP Journal on Advances in Signal Processing . Except for the noise statistics, we assume no a priori knowledge of the channel parameters (e.g., the covariance matrix of the CFR) is given, and we only consider the conventional LS method. Therefore, the unique LS solution H F that minimizes the cost function defined by X F − S F H F 2 can be written as It should be noted that if we want to obtain the CFR with a length greater than the default length L, interpolation is needed.
Based on assumption (A1), it is clear that this estimate is unbiased since E{ H F } = H F . Let us define the CFR estimation error as E F = H F − H F . Using (16) and (18), we obtain Its correlation matrix, Thus, the MSE for this CFR estimation is given by Now we consider the problem of designing the matrix S F so that the estimation error is minimized. To have a reasonable solution, it is necessary to impose a constraint to limit the power of training sequences. Let such a constraint be S F 2 ≤ P 0 , where P 0 is a given constant. Note that the power used in the cyclic prefix is not included in this formulation. Mathematically, this power constraint can also be written as tr{S H F S F } ≤ P 0 . For simplicity, we start with a general problem formulation, without examining the structure of the data matrix S F but only assuming it has full rank. Therefore, our task is to find S F that minimizes the MSE subject to the power constraint given above. This constrained optimization problem can be cast as To solve this problem, the following lemma will be useful.

Lemma 1.
For any M × M positive semidefinite Hermitian matrix A with its (i, j)th entry given by a i j , the following inequality holds where the equality is achieved if and only if A is diagonal.
Applying this lemma and the method of Lagrange multipliers [19], we could readily solve this optimization problem. For brevity, we omit the details and simply provide the solution which means that the diagonal entries of S H F S F have the same value. Re-examining the matrix S F as defined in (14) and its relation to G in (2), we find that due to the orthogonal structure of the ST code, Then, we arrive at the following result.

Theorem 1. The following equality holds
Proof. S H F S F is an N T L × N T L matrix and can be expressed in the block matrix form as where Ξ i, j , i = 1, . . . , N T , j = 1, . . . , N T , is a square matrix of size L × L. According to both (6) and (14), Ξ i, j can be expressed as To simplify (27), we need to use the mixed-product property of Kronecker product, that is, (A ⊗ B)(C ⊗ D) = AC ⊗ BD, where A, B, C, and D are matrices of such size that one can form the matrix products AC and BD. Further, given the properties of Γ Am and Γ Bn in (5), we have the following: Similar properties also hold for Γ T Bm (:, i)Γ Bn (:, j). Moreover, we have 6 EURASIP Journal on Advances in Signal Processing Based on the above properties, (27) can be simplified into Plugging (30) into (26), we then obtain (25).
Based on (24) and (25), we summarize the following result.
Theorem 2. The optimal training signals under the LS criterion should satisfy the following condition: This condition is the same as where Of note is that although Theorem 2 states the conditions for training signals to be optimal in the sense of achieving the minimum value of MSE, it does not mean any sequences which satisfy (32) would be suitable for practical applications. This is because practical implementation of communication systems will inevitably impose some additional constraints on the sequences. To give an example, let us consider the CP-based communication systems. These systems are usually plagued by the well-known peak-toaverage ratio (PAR) problem; thus, sequences with lower PAR values are, in general, more preferred in practice, for they can greatly alleviate the requirement on the power amplifier. Under this circumstance, training sequences which not only satisfy (32) but have a constant magnitude in both the time domain and the frequency domain would lend themselves to be a superior choice, for they are able to successfully preclude the PAR problem while achieving the minimum value of MSE. Chu sequences [20] and the class of training sequences proposed in [21] are examples of those sequences. Finally, the resulting minimum value of MSE can be calculated by

MMSE Estimator with Power Constraint.
In this section, we consider the linear MMSE estimation of the CFR as well as the optimal training sequence design. For simplicity, we consider only the CFR associated with the qth receive antenna, that is, h q F , which was defined in (14). Besides assumption (A1), we make one additional assumption about the channel statistics as follows.
(A2) The CFR h q F is a Gaussian random vector with zero mean and full-rank covariance matrix Σ q .
For convenience, we denote Σ q by Σ. Since h q F = (I NT ⊗F L )h q , we have where E{h q (h q ) H } is the covariance matrix of the corresponding CIR.
The MMSE estimate of the CFR can be computed through We define the CFR estimation error as e Similar to the approach that we took in Section 3.1, we also impose a power constraint, and the design problem can be formulated into Note that Σ can be diagonalized through its eigenvalue decomposition, that is, where V is a unitary matrix whose columns are eigenvectors of Σ, and Λ is a nonnegative and diagonal matrix consisting of all the eigenvalues of Σ. Then, (36) can be reformulated into where Ψ = S F V is an N c L × N T L matrix. As V is unitary, it follows tr{S H F S F } = tr{Ψ H Ψ}. According to Lemma 1, the minimum value of E{ e q F 2 } is attained when (σ −2 n Ψ H Ψ + Λ −1 ) is diagonal. Let Q = Ψ H Ψ, then Q must be a diagonal matrix with elements Q ii ≥ 0, for i = 1, . . . , N T L. Consequently, we can reformulate the optimization problem into Using the method of Lagrange multipliers [19], we can obtain the following solution to the modified optimization problem where Λ ii denotes the (i, i)th element of Λ, and the value of τ can be found by solving Alternatively, Q can be rewritten as Thus, the resulting MSE can be computed through It is worth noting that Ψ H Ψ is invariant to the postmultiplication of Ψ by a semi-orthogonal matrix. Thus, given the optimal solution for Q in (43), a general solution for Ψ can be composed as Ψ = ZQ 1/2 , where Z is an N c L × N T L matrix with its column forming an orthonormal basis. Since Ψ = S F V, it is clear that the necessary condition for S F to be optimum is S F = ZQ 1/2 V H . Meanwhile, we have S H F S F = VQV H and both sides are diagonal matrices. Considering the structure of S F in (14) and applying Theorem 1, we are thus led to following result. Theorem 3. The optimal training signals under the MMSE criterion should satisfy the following condition for a specific channel statistics (i.e., Σ) Equation (45) specifies the essential characteristics of the optimum sequence under the MMSE criterion. It indicates that the optimal design should employ a water-filling type power allocation. Evidently, the structure of the covariance matrix Σ will have a large impact on the optimal training signal design. For example, when Σ is diagonal, then from (34), we can see that E{h q (h q ) H } can be a block circulant matrix, and the optimum condition (45) would represent a water-filling in power distribution with respect to the power spectral density samples of the CIR. For this special case, the optimal sequence may be generated through the frequencydomain water-filling. For cases where Σ is not diagonal, the optimal condition (45) may need to be jointly considered with the Kronecker product approximation in [22]. We omit further discussions for brevity.

CFR Estimation for Alamouti-Like Transmissions
Here, we study the CFR estimation for the special case of N T = 2 and N R = 1. This corresponds to the Alamoutitype transmission, where N S = N c = 2 and R = 1. The transmission structure for the training sequences is illustrated in Table 2. The length of total training symbols from each transmit antenna, N b , is equal to N b = 2(L + ν), and its minimum length is N b = 4ν+2 when L is chosen to be the minimum value ν + 1. At the receiver, CPs are removed, which yields the channel input-output relationship in matrix vector form as x 1 (k) = H (1,1) s 1 + H (2,1) s 2 + n 1 (k), where x 1 (k) and x 1 (k + 1) denote two consecutive received blocks at the single receive antenna. Applying the orthonormal FFT matrix F L on (46), we obtain the frequency domain input-output relationship as shown below For this special case, the CFR estimation based on both the LS and MMSE criteria can be readily obtained by following the procedures outlined in Section 3. In this section, we further demonstrate that the CFR estimation for this special case can be implemented adaptively with block-wise recursive algorithms. Additionally, we also provide a brief convergence analysis of these algorithms.

Adaptive Implementation of CFR Estimation.
It is easy to show that the CFR estimator for this special case has the following structure We further define L × L diagonal matrices X 1F (k) = diag{x 1F (k)} and X 1F (k + 1) =diag{x 1F (k + 1)}. Then, (49) can be reformulated into or the simplified form where in (50), Φ = [X H 1F (k)X 1F (k) + X H 1F (k + 1)X 1F (k + 1)] −1 ;h F is a 2L × 1 vector; U F is an orthogonal matrix with 8 EURASIP Journal on Advances in Signal Processing the size of 2L × 2L; g F is a 2L × 1 vector that contains the elements of g 1F and g 2F .
We would like to emphasize that this reformulation from (49) to (50) is largely attributed to the benign property of Alamouti's code. This, as a result, enables the CFR estimation to be performed adaptively, and the channel to be tracked when the adaptive filter operates. To be more specific, we can view U F as the tap-input data matrix, g F as the output, andh F as the filter coefficients. The block diagram of this adaptive filter is depicted in Figure 2. We further define the error signalȇ F , which is generated by comparing the filter output with the desired response, that is, Note that as g F is fixed and already available beforehand at the receiver, the adaptive filter can always operate at the training mode. Hence, if the channel is slowly time-varying, the adaptive method, through estimating the current channel gains based on the previous channel estimate, can achieve accuracy refinement without significantly increasing the complexity. Simulation results illustrating this can be found in Section 5. For notational convenience, we add in the time index for vectors or matrices in the ensuing description. And we summarize the recursive algorithms that are used to update the CFR estimate in Table 3, which include the block least mean square (LMS) algorithm and the block recursive least squares (RLS) algorithm. The block RLS algorithm usually achieves a quicker convergence than the block LMS algorithm (as will be shown later by simulation results). But such a quick convergence is attained at the cost of a heavy increase in the computational complexity. To exemplify this, let us examine the computational complexity of both algorithms. At each iteration, the block LMS algorithm requires around O(8L) computations, while the block RLS algorithm requires O(24L 3 + 20L 2 + 4L) operations. A fast version of this block RLS algorithm, namely fast subsampled-updating RLS algorithm [23], can be used to achieve some complexity reduction, but may make this filter cumbersome. Fortunately, thanks to the special structure of the Alamouti's code, it is easy to verify that U H F (k)U F (k) = I 2L . Furthermore, we can induce that P (k) (cf. Table 3) is a 2L × 2L diagonal matrix, that is, P (k) = I 2 ⊗ P(k), where P(k) denotes an L × L diagonal matrix. Then, by following a similar technique used in [24,25], we can avoid the need for matrix inversion in the block RLS algorithm and hence can eventually achieve a substantial reduction in the computational complexity but without losing the convergence advantage. For brevity, we summarize the simplified algorithm in Table 4. This simplified algorithm requires only O(13L) operations for each iteration, which is much less than that of the original block RLS algorithm.
It is worthwhile to make a remark here that the above adaptive implementation of the CFR estimation is a special property owned by the Alamouti scheme with N T = 2. When N T increases beyond 2, the linear CFR estimator G F , under both the LS and MMSE criteria (cf. (18) and (35)), will no longer have the simple Alamouti's structure. And so, a similar transformation as that from (49) to (50) may not necessarily where μ denotes the step size.

Convergence Analysis.
Convergence behaviors of these block-level recursive algorithms are briefly discussed as follows. We are interested in the behavior of ξ(k) = E{ȇ F (k)ȇ H F (k)}, particularly at the steady state, whereȇ F (k) denotes the error signal, as defined in (52). For the block LMS algorithm, we define the weight-error vector as where h F ,0 is the optimum tap-weight vector for the filter.
Defining e F ,0 (k) = g F (k) − U F (k)h F ,0 , we havȇ Let the weight-error correlation matrix be given as Construct data matrix Adaptive algorithm Thus, the MSE of weight vector error can be obtained by simply taking the trace of R vv (k). To facilitate the convergence analysis, we make the following assumptions.
(A3) Elements of e F ,0 (k) are samples of a white noise process, which implies that E{e F ,0 (k)e H F ,0 (k)} = ξ min ·I 2L , where ξ min is the minimum MSE at the filter output.
(A4) U F (k) and e F ,0 (k) are jointly Gaussian, and are uncorrelated with each other.
(A5) v F (k) is independent of U F (k) and e F ,0 (k). Further, we assume R uu = E{U H F (k)U F (k)}/2L, where R uu is the correlation matrix of the filter tap inputs.
Based on the above assumptions and following a similar procedure in [26, Appendix 8A], we can compute the excess MSE, which is defined as the difference between the steadystate MSE (i.e., ξ(k = ∞)) and the minimum MSE ξ min of an adaptive filter, approximately by where tr(R uu ) is equivalent to the sum of the powers of the signal samples at the filter tap inputs. Accordingly, the misadjustment, a dimension-free degradation measure that is defined as the ratio of the steady-state value of the excess MSE to the minimum MSE, can be written as Also, the steady-state MSE of the block LMS algorithm is given by ξ BLMS steady = 2Lξ min + μξ min 2 tr(R uu ).
It is obvious that the convergence behavior of the block LMS algorithm is governed by the eigenvalues of the correlation matrix R uu of the filter tap input. Therefore, similar to the conventional LMS algorithm, the block LMS algorithm in nature is also a stochastic implementation of the steepestdescent method [26]. For the block RLS algorithm, its convergence analysis is undertaken on an adaptive identification scheme [27]. We consider a linear multiple regression model characterized by where h F ,0 is the regression parameter vector, U F (k) is the tap-input matrix, e F ,0 (k) is the measurement noise, and g F (k) is the desired response. We define the weight error vector v F (k) the same as in (53) and its correlation matrix R vv (k) the same as in (56). Further, we assume that the input signal vector is drawn from a stochastic process which is ergodic in the autocorrelation function, thus the time average can be used instead of the ensemble average [28]. Then, for λ < 1, following a similar approach as described in [27] for the analysis of RLS algorithms, the excess MSE for this block RLS algorithm at steady state can be written as and the misadjustment is simply Finally, the steady-state MSE is approximately given by

Simulation Results
In this section, we provide some simulation results to demonstrate the efficacy of our proposed scheme. In our simulations, we employ a specific block structure for both data and training sequences, which is illustrated in Figure 3, taking the case of N T = 2 as an example. This structure would be able to accommodate the proposed CFR estimation  scheme and various FDE techniques. We assume the channel is frequency selective with channel memory ν = 3, and further assume block fading, that is, the channel fading gains are constant over one ST-coded block including both data and training subblocks, but vary from block to block. For simplicity, we assume no a priori knowledge is available regarding the channel second-order statistics. Hence, only LS method is considered in our simulations. Chu sequences [20], a special case which satisfies the optimal condition given in (32), are chosen to be the training sequences. We use 8-PSK for data transmission without channel coding. At the receiver, channel estimation and equalization are both processed in the frequency domain. As a result, the FFT modules for FDE can be easily reused for the CFR estimation. Several different FDE approaches that are applicable to the structure shown in Figure 3 can be found in [9], and are employed in our simulations.
Figures 4(a) and 4(b) illustrate the BER performance corresponding to the frequency-domain MMSE linear equalization and MMSE decision-feedback equalization, respectively, under both CFR estimation and perfect CFR knowledge. When L = 4 (N b = 14), that is, the minimum length to estimate the CFR, we have P 0 = 16. The performance penalties due to inaccurate channel estimation, if evaluated at BER = 10 −4 , are about 2.4 dB for the decision-feedback equalization and 2.8 dB for the linear equalization. When L extends to 7, or equivalently N b extends to 20 as shown in Figure 3, P 0 is accordingly increased to 28. Then, the BER performance penalties for the decision-feedback equalization and the linear equalization are reduced to 1.1 dB and 1.9 dB, respectively.
Furthermore, we also compare the performance of our approach with the method proposed in [29]. The approach reported in [29] was designed for channel estimation in MIMO systems with SC-FDE. It allows the transmitted sequence to be nulled on certain frequency tones, causing the transmitted training sequences to be orthogonal in the frequency domain. Essentially, this approach [29] is equivalent to the on-off type estimation for each channel. To ensure a fair comparison, we apply the reference method [29] to the same structure depicted in Figure 3 for the case of N T = 2. Then, both our scheme and the reference scheme [29] will achieve full rate, that is, R = 1. Since there are 20 symbols in total allocated for the channel parameter estimation in the structure shown in Figure 3, when implementing the approach reported in [29], we allocate 16 for training sequences, and 4 (rather than ν = 3) for the CP. This is because it is required in [29] that the length of training sequences must be evenly divisible by N T . Furthermore, in the simulations, Chu sequences [20] are also adopted as the training sequences for this benchmark approach, as they as well satisfy the condition of optimality described in [29]. The BER performance of such an algorithm is depicted in Figure 4 by dash-dot lines. As illustrated by Figure 4, the system using our proposed scheme performs as well as, if not better than, the system using the approach described in [29]. However, considering the fact that implementation of the method given in [29] requires the transformation from CFR to CIR and then back to CFR (see details in [29]), our approach appears much simpler and straightforward.
Under similar simulation set-up, we also study the case of 2TX-2RX where the Alamouti-type STBC is employed at the transmitter side. At the receiver side, CFR estimation is performed based on the received signals across those two receive antennas, which is followed by FDE. In particular, we consider the equal gain diversity combining in the frequency domain. We further consider the case of 3TX-1RX, where the code design illustrated in (7) is used. BER performance of these scenarios under the frequency-domain linear equalization is depicted in Figure 5. For the purpose of comparison, we also plot in the same figure the BER CFR estimation with L = 4 CFR estimation with L = 7 Reference method [29] Ideal CFR knowledge Reference method [29] Ideal CFR knowledge  performance of the 2TX-1RX case. From these curves, we notice that performance penalties due to inaccurate channel estimation are almost the same for the 2TX-1RX and 2TX-2RX cases, but are relatively smaller for the 3TX-1RX case. Furthermore, because of the addition of one more receive antenna, the BER performance of 2TX-2RX is much improved over that of the 2TX-1RX case. However, as shown in Figure 5, the BER performance of 2TX-2RX is inferior to that of the 3TX-1RX case. This is largely due to the fact that this 3TX-1RX system we consider here is not a full-rate system (i.e., R = 1/2), which is in contrast to those systems employing two transmit antennas and Alamouti-type code.
For the special case of N T = 2, we also conduct simulations to study the behaviors of these adaptive estimation algorithms. For simplicity, Chu sequences [20] are used again in our simulations. We set L = ν + 1, P 0 = 16, and σ 2 n = 0.1. Block fading is still adopted, but the channel fadings are further assumed to be correlated in the time domain. This means the Doppler spread is introduced, and it may affect performance of the adaptive algorithms, as will be confirmed later. The rate of fading in our simulations is determined by f d T, where f d denotes the maximum Doppler frequency shift and T denotes the duration of one whole ST-coded block. A larger value of f d T implies faster fading and vice versa. The following simulation results are obtained by setting f d T = 10 −4 , unless otherwise stated. Figure 6(a) shows a plot of the squared error ȇ F (k) 2 versus the number of iterations for a single run or trial of the block-wise LMS and RLS algorithms. Since those algorithms only iterate once for each ST-coded frame, the number of iterations also corresponds to the number of frames. As is shown by Figure 6(a), the learning curves for a single trial of both adaptive algorithms exhibit a noisy form. However, it is clearly seen that the block RLS algorithm converges much faster than the block LMS algorithm. Additionally, we are also interested in the behavior of the squared error deviation v F (k) 2 for both algorithms. For the same realization, Figure 6(b) shows the transient behavior of v F (k) 2 for both algorithms. As ȇ F (k) 2 converges, v F (k) 2 converges accordingly. But notice that the curves in both figures are plotted at different vertical scales. It is worth noting that in our simulations, we ran the filter from scratch by simply initializing elements of the channel estimate (i.e., the filter coefficients) all to zeros. This is to demonstrate the convergence performance of these block-wise algorithms. However, in practice, it is certainly possible to speed up the convergence process and reduce the amount of training data. For example, for the first frame, we can obtain the channel estimate by using nonadaptive approach from (49) (i.e., hot start initialization). Afterwards, we can apply the adaptive method.
Given the same set of parameters that lead to the results shown in Figure 6, we conduct 100 independent trials and compute the ensemble average. In Figure 7(a), we plot the learning curves of both block-wise algorithms for E{ ȇ F (k) 2 } versus the number of iterations. It is clearly seen that ensemble averaging helps smooth out the effects of gradient noise in the learning curves. For the same set of trials, we also compute the corresponding values of E{ v F (k) 2 }, and plot them in Figure 7(b). In addition, for the purpose of comparison, MSE values obtained from the nonadaptive CFR estimation experiments based on the LS method are also plotted in the same figure, together with the theoretical value. Such a theoretical MSE value can be obtained by plugging these simulation parameters into (33), and we obtain E{ E F 2 } = 0.4. The subplot in Figure 7(b) indicates a very good match between the simulated values and the theoretical one, which in turn corroborates the correctness of our derivations. Moreover, it is also observed that after the learning curves converge (especially for the block RLS algorithm), the MSE values attained are much smaller than those obtained by the nonadaptive method or the one computed theoretically. This basically demonstrates the performance advantage of using this adaptive approach.
Finally, we provide some simulation results in Figure 8 to demonstrate the error performance of both adaptive estimation algorithms at higher Doppler spreads. In particular, we consider three different Doppler spreads: f d T = 10 −4 , 10 −3 , and 10 −2 . And we conduct 100 independent trials for each case. For simplicity, we leave the step sizes unchanged in our simulations, that is, λ = 0.8 and μ = 0.08; but note that it is desirable to reduce them accordingly as the frequency dispersion or Doppler spread increases. Here, we only study the behavior of E{ v F (k) 2 }, and for the ease of comparison, we also plot in Figure 8 the theoretical MSE value of the nonadaptive LS estimation approach. The results shown in Figure 8 indicate that as the Doppler spread increases moderately, for example, from f d T = 10 −4 to f d T = 10 −3 , the estimation accuracy of both algorithms will degrade a little, but not severely. However, further increase in the Doppler spread, for example, from f d T = 10 −3 to f d T = 10 −2 , will lead to a drastic degradation in the estimation accuracy for both algorithms. In fact, in this case, the estimation accuracy of each of these two adaptive algorithms is inferior to that of the nonadaptive estimation approach, indicating that they are unable to track faster channel variations and thus may no longer be usable in practice.

Conclusion
In this paper, we presented and studied a training-based CFR estimation scheme for ST-coded MIMO systems with SC-FDE. This scheme is different from the traditional one which obtains the CIR firstly then transfers it to the CFR. In this scheme, CFR estimation is jointly implemented with FDE; thus, estimate of the CFR can be obtained directly and the hardware complexity of the transceiver can also be reduced. To be more specific, training sequences are ST block encoded at the transmitter using the same encoder for data sequences. At the receiver, similar procedures are applied to both data and training sequences, including the CP removal and FFT processing. Then, estimation of the CFR is performed immediately afterwards. Conditioning on different a priori channel knowledge, we further studied the CFR estimation based on two criteria: LS and MMSE. A thorough analysis of the MSE in estimating the CFR was provided under each criterion. Moreover, imposing a constraint on the transmit power of training sequences, we also investigated the optimal design of training signals. It is shown that under the LS criterion, training sequences having a constant sum magnitude at each frequency tone, such as Chu sequences, will lead to the least MSE. For the MMSE criterion, we have shown that the optimal design of training sequences features a water-filling-type power distribution. Additionally, we demonstrated that adaptive implementation of the CFR is feasible when the number of transmit antennas is equal to 2, which is due to the benign property of Alamouti's code. However, we feel that the identical property may not be possessed when N T increases beyond 2 although it may need further investigation.


Guerrilla Marketing Communication Tools and Ethical Problems in Guerilla Advertising 1

Problem statement: Companies attempt to reach private worlds of consu mers and give them memorable experience with their brands by using guerrilla marketing tools. Guerrilla advertising, which is one of the guerrilla marketing tools, usua lly attracts the attention of consumers but sometim es irritates and annoys the consumers and even breaks the law. Approach: The study determined these ethical aspects by evaluating different guerilla ad vertising strategies of the companies. A critical assessment of the printed and visual discoursed of guerilla ads were made in this context. Results: The assessment indicated that there are some ethical pr oblems about guerrilla advertising implementations. Especially the ads, which include fear-appeal, may irritate people. Also, distraction of attention in traffic is the other important ethical problem. Conclusion/Recommendations: These kinds of guerrilla ads may reduce the effectiveness of advertisements in general and dislike of a company's ad may lead to biased reactions towards future advertisements. Ethical, legal and societal boundaries must be considered in guerilla advertising strategies. In s um today's marketers have to take greater responsibility for the negative impacts of the prac tices of guerilla advertising.

INTRODUCTION
Uncertainty, brought about by changes associated with globalization, makes it necessary for businesses to produce more and react to changes more quickly. However, many large companies, today, carry on their activities by means of traditional marketing strategies. The managers of these companies plan their marketing policies by analyzing research done by their own company or other market research companies. The product and brand managers of these businesses also lack the creativity and passion of guerilla marketers. At this point, these managers should leave their offices and spend time with their prospects in order to create new values for their lives and they should find new ways to do so as quickly as possible (Kotler, 2003). Such dynamism, while making it possible to respond to changes in the market quickly, also makes it necessary that companies adopt original strategies that are based on their primary abilities and advantages. This necessity has made it almost inescapable for companies to employ unconventional marketing strategies such as guerilla marketing. Guerilla marketing, which consists of strategies that can be applied by businesses easily and with little cost, is an important marketing tool that companies should learn and make use of in order to be successful in such a competitive environment.
The guerrilla marketing concept, which was created by Levinson (1984), implies an unconventional way of performing promotional activities on a very low budget. In recent years, many companies, looking for ways of getting out of clutter of traditional marketing implementations, tend to apply guerrilla marketing which is a different way of marketing communication. Not only the effect of guerilla marketing strategies is important, but also the direction and the intensity of the effects are also crucial. According to Rossiter and Percy (1987) the message and the theme should take social and individual values into account. When the message and theme are coded correctly, positive reactions develop, but in those cases in which the message is coded and directed in a wrong way, the communicative effect of the advertisement is usually negative (Firlar, 2005). That is why, despite the unrestricted creative applications, ethical, legal and societal boundaries must be preserved in guerilla marketing strategies. In this sense, there must be a boundary between the creative strategies of guerilla marketing and its irresponsibly developed applications (Zuo and Veil, 2006;Levinson and Rubin, 1996;Wilson et al., 1992).
Guerilla marketing: Guerilla marketing is a tool that allows SME's to demoralize their rivals with small, periodical and surprising attacks, requires swift action and utilizes creativity and imagination (Tek, 1999). Through guerilla marketing, businesses aim at forming a marketing management that is dynamic, sensitive to customer needs and that is able to adapt to changes easily. Today, the increasing variety of products and services as well as their similarity negatively affect business profits.
On the other hand, economic uncertainty, brought about by constant changes, has made it necessary to reconsider the costs of marketing activities making up a substantial portion of firms' budgets. As a response, firms have been seeking to find different, novel, effective and less costly marketing strategies. In such a context, although it resembles traditional marketing, guerilla marketing differs from such conventional approaches in terms of the ways used to reach ends and techniques that are employed and offers many advantages to those who execute it. Gallagher (2004) explains this difference as: "What matters in guerilla marketing is, rather than what the firm does to be successful but what it does to differentiate itself from its rivals and its success in reaching a broader customer potential".
Guerilla marketing and marketing communication tools: Currently, costs of promotion in sales are on the rise. Despite the fact that businesses spend more money on promotions, they cannot guarantee effectiveness either. The most important reason for that is the media crowd caused by new businesses that resort to promotions and advertisements to introduce their products and services to their target customers and the old businesses that increase their already existing advertising and promotional activities in an effort to compete with the new businesses. At this point, the first action to be taken by the guerilla marketer is to overcome this media crowd without increasing the costs of promotion in sales and second, increase the firm's profits not through direct sales parameters such as costpromotion-discount but by creating a difference in the perception of the study and the product.
Marketing communication tools (such as advertising, personal selling, sales promotion and public relations) play an important role in increasing the volume and quality of communications of the businesses with their customers. Innovative implementations by guerilla marketers provide important advantages to the businesses. However, guerilla marketing strategies that are developed without considering certain principles and especially guerilla ads cause important ethical problems. This affects the marketing efforts of businesses in a negative way.
This study, first discusses marketing communication tools (advertising, personal selling, sales promotion and public relations) and guerilla marketing strategies and elaborates on ethical problems related to guerilla advertising. Then, some of the high profile guerilla ads examples will be evaluated.

Guerilla advertising strategies:
The innovative and entrepreneurial spirit of guerilla marketers is mostly observed in the advertising activities of companies. Through the use of various media, tools and slogans, the guerilla marketer both differentiates the company's ads from those of its rivals to a great extent and positions its products and services distinctly in the minds of the prospects. The differentiation created by the positioning of the ad's message in the prospect's mind not only communicates its message but also ensures that the message is imprinted for a longer period. This plays an important role in the effectiveness of the ad.
The person who is responsible from the advertising activities of the company following a guerilla marketing strategy should possess the ability to realize the company's vision. Levinson (1998), who introduced guerilla marketing concept, stressed the importance of the following principles for the advertising activities of the companies that use guerilla marketing strategies: • By being as specific as possible, these advertisements should be persuasive and directly contribute to the company's profits • In the case of an ad that includes a witness, the witness should be a real customer and the ad should refer to real events and real names • The realistic goals should be communicated to the target customers in a creative way Adhering to these principles when developing the advertising activities enables the company that employs guerilla marketing strategy to increase its ad's effectiveness, gain new customers and increase its profits. Apart from these principles, the ethical aspect of such ads should also be taken into consideration.
Guerilla personal selling strategies: Personal selling is a process in which a salesperson engages in face-toface marketing in an effort to direct the existing and the potential customers to the products and/or services of the company that she represents. Meetings with the customers, informational presentations at such meetings and small gifts and presents that are intended to increase participation in and effectiveness of such activities are among the most important tools of this process (Kotler, 2005). Personal selling is crucial for companies to establish long-term and continuous relations with their customers.
To be able to successfully apply guerilla marketing, companies need guerillas (salespersons) that would invest all their time and energy to the marketing activities of the company. Personal selling is particularly important for guerilla marketing since the salesperson is the public face of the company and first point of contact. Guerillas can be recruited either from within the company or from outside sources when needed. For companies that are planning to employ guerilla marketing strategies, training guerillas is the most important step of the strategy.
The sincerity of the guerillas towards their customers in all matters, their entrepreneurial spirit and their intense efforts and disciplined work to provide solutions to the problems in their field leads to increased customer loyalty as the customers would not want to go anywhere else. The study itself is what motivates the guerilla in the first place. Being chosen by their customers is a reward for the guerilla. That is why; the reward of the guerilla is to satisfy the needs of more customers by engaging in business with more of them. The trust towards guerilla and her company is the guarantee of the sales that the company will make to these prospects (Levinson, 1994).

Guerilla public relations strategies: International
Public Relations Association defines public relations as the continuous activities of public or private organizations in order to maintain the recognition, sympathy and the support of the people that the organization may have contact with. Based on this definition, we may say that public relations has three objectives: Providing comprehensive information about an activity, maintaining positive personal relations within the establishment and establishing an effective communication network (Budak and Budak, 1998). These are also the targets of the guerilla marketing process. Such that, guerillas are those people who are aware that they could increase their profits by engaging in better relations with target customers and by producing more value for them. Public relations is the main instrument both for getting to know prospects who are at the core of unconventional marketing approaches and for being able to produce economic worth for them as effectively as possible. Guerillas, by using these activities to get in touch with more consumers and in engaging in better relations with them aim at increasing the profits. From this perspective, the foremost duty of the guerilla is to understand the characteristics and the desires of the society and the prospect he/she is in relation with and to communicate the policies and the practices she follows to the public using various communication tools.
A smart guerilla marketer pays special attention to public relations. In case the business have been earning profits from its customers for some time, there is no harm in paying part of the profits back to the customers through public relations activities such as sponsorships (Levinson, 1998).
An important part of public relations activities that the managements carry out is the efforts by the businesses to engage in efforts to provide solutions to the common problems of the society. The fact that the businesses want to engage in public relations activities is not enough by itself. For such efforts to be successful and effective, companies need innovative and entrepreneurial ideas of the guerillas.
Guerilla sales promotion strategies: Sales promotion consists of sales promotion tools such as exhibitions, premiums to salespersons, discounts and competitions in an effort to encourage prospects to buy and to increase the effectiveness of the intermediators. Through the use of these tactics, businesses aim at getting customers to take immediate action. Within the scope of integrated marketing, whereas advertising increases the effectiveness of sales promotion, personal selling and public relations support these efforts to a great extent (Kotler, 2005).
Advertising specials and free gifts distributed in the process of sales promotion have a special place in guerilla marketing. Especially in markets where competition is intense and where it is hard to attract the attention of the consumers, sales promotion tools are used more frequently. In such cases, free gifts distributed by businesses affect all demographic groups to a great extent. Research on sales promotion shows that 40% of those who were given gifts remember the company name for at least 6 month sand 31% up to 1 year. According to a recent research, free gifts, due to increased interest on part of the customers, also lead to an increase in sales revenues (Ay and Unal, 2002). In addition, the fact that these gifts naturally lead to positive feelings among consumers is reflected not only in sales but also in the close relations of the company with customers. Guerillas aim at increasing the number of interactions with the customers and their sales through the help of these sales promotion tools (Levinson, 2009).

Ethical problems of guerilla advertising strategies:
Although there are successful applications of guerilla marketing strategies and related advertisements, guerilla advertising activities that are not developed and executed properly may lead to certain ethical problems. Especially those advertisements that embrace fearappeals irritate the target consumers or those that are distracting may be ethically problematic.
Contemporary advertisements aim at arousing the viewer's emotions. Advertisers try to arouse emotions for three purposes (Higbee, 1969): • Emotions per se are an important benefit derived from a product or brand • Emotions may help to communicate the benefits of a product or brand • Emotions can directly affect attitudes As effective as emotion-arousing advertisement might be, its improper use may have side-effects. Hyman and Tansey (1990) refer to those emotionarousing ads that cause a group of viewers to feel extremely anxious, hostile toward others or feel a loss of self-esteem as psychoactive ads. The planning of advertising without taking into consideration such facts may lead to certain ethical problems. In such ads, the advertiser may target a specific result, or may aim at increasing product sales. Whatever the goal is, it affects and draws the attention of the audience. Such ads do not aim at entertaining the audience. They make the audience feel angry, disturbed, fearful and sad (Hyman and Tansey, 1990). Such irritating ads provoke the viewers and lead to discontent and temporary impatience. The emotions aroused are in fact worse than dislike (Aaker and Bruzzone, 1985). The aim is to evoke negative emotions such as fear or sadness rather than positive feelings of happiness, peace, or love. These factors that irritate the viewers or consumers may lead to the development of negative attitudes towards the brand.
Some research discusses the irritation caused by the fear appeal of some ads and examines their ethical aspect. According to Duke et al. (1993) and LaTour and Zahra (1989), the use of fear appeals leads to negative, unwanted reactions on individual consumers. Higbee (1969) argues that too much fear-appeal leads to anxiety disorders. On the other hand, as mentioned above, fear appeals in advertisements also attract attention and intensify the persuasive power of the ad. Higbee (1969) and LaTour and Pitts (1989) find that powerful fear appeals in health and security-related products are more effective than weak fear appeals (Snipes et al., 1999). However, it is also crucial to decide on the right amount of fear-appeal to be used. The effectiveness of fear appeal depends more on the probability and reality of the fear rather than its extensive intensity.
The process of the use of fear appeals in advertising has three steps. The first step consists of the design of a fearful situation in order to evoke risk perceptions and vulnerability of the individual. Marketers are in fact quite brilliant in doing this and there are interesting examples of such ads in which the fear appeal is cleverly used. The second step involves the illustration of the danger in an effort to guarantee attention. Solution is presented by alleviating the fear in the third step. Accordingly, a connection is established between fear and assurance of "protection from fear" in order to convince customers to view the recommended action. Leventhal (1970) and LaTour and Zahra (1989) presents this process in Fig. 1.
As can be seen in the Fig. 1, emotional response follows the fear stimulant, which leads to stress. This stress leads individual to watch the recommended action. In case the recommended action is sufficient in reducing the fear and the stress, it leads to relief. This means "there is no fear". In this case, the process is completed. However, in case of failure to reduce fear, it could be possible for the danger to be denied or be ignored. This means that the process continues due to new reaction.
Some authors have argued that increase in the number of ads with fear appeals may reduce the effectiveness of advertisements in general. For example, according to Greyser (1973), public dislike of the ad leads to the erosion of the goodwill on which public receptivity to it depends. In addition, public dislike of advertisement specific to a company may reduce the short-term and particularly, the long term effectiveness of that ad (Gallagher, 2004). At the same time, dislike of the company's ad may lead to biased reactions towards future advertisements. Fig. 1: The fear drive model. Source: Leventhal (1970)

Am. J. of Economics and Business Administration 2 (3): 280-286, 2010
Other ethical problems of guerilla marketing include the trespassing on private property, defacing private or public property and not getting permission from the property owners. Curran and Seaton (1997) has argued that placing Burger King stickers on bus schedules to indicate store locations may be considered an act of vandalism (Zuo and Veil, 2006). Pictures or pamphlets placed illegally on other places (public buses, bus stops, building walls) also point out to the same problem.
Guerilla marketing may include some dangers. For example, ads placed in the middle of the road may distract the drivers, thus causing traffic accidents (Zuo and Veil, 2006). In addition, guerilla ads placed on public buses, cabs, or private vehicles, both because of their content and their design carry the risk of traffic accidents by jeopardizing the traffic flow.

MATERIALS AND METHODS
In this study, a critical assessment of the printed and visual discourses of guerilla ads is made. For this part of the study, first an internet search of guerilla ads were carried out and then, five examples that are believed to be ethically problematic were chosen. These five examples are presented below.

D.D. Dirin (pesticide firm):
In a guerilla ad for an exterminator company called D.D. Dirin, a fake cockroach is placed through the houses' doors. The person who enters the house sees the roach and attempts at killing it, but realizes that the insect is not alive. When the cockroach is turned upside down, it is seen that it is nothing more than a brochure. The brochure includes a short note about how easy it is for the insects to get inside the houses and together with the name and the contact information of the company.

(serialized film):
Channel 2 in Belgium executed a guerilla campaign for the TV series 24, which is also broadcast in Turkey in Cnbc-E and has a lot of fans. The poster that was prepared for the campaign shows scenes of traffic pull over in the city center of Antwerp, creating the sense that there is a biological danger. In the poster, there are pictures of men with masks and special uniforms distributing flyers that state the presence of a deadly virus. In these flyers, after the word "Caution" comes the statement: "There is a fatal virus in the city. Go home now; close your windows and doors. Turn on your television". Under the flyer, there is the logo of the TV channel and the series 24.

Perlodent (toothpaste):
In a toothpaste ad that is attached to the bottle opener apparatus of the Coca Cola vending machine a woman opening the bottle with her strong and white teeth is displayed. When a customer uses the bottle opener part of the vending machine it is the woman with her white teeth that opens the bottle, thus the advertisement aims at giving the impression that the toothpaste is very effective.

Kill Bill (movie):
In this guerilla advertisement that was used in the washroom of a movie theatre, there is a shocking image seen from the outside the toilet cabin. In the image there is blood leaking from under the door of the cabin. But when the door is opened it is realized that this is a sticker that shows the release date of the movie "Kill Bill".

Pringles (potato chips):
In this guerilla type ad, a fake potato chip is placed on the wiper of the back window of a cab. On the right side of this window, there is the picture of a man and a Pringles box is placed on the left side. Every time the wiper is turned on, it moves from left to right, thus leading to the impression that the potato chip that goes out of the Pringles box goes into the mouth of the men in the picture.

RESULTS
D.D. Dirin advertisement is not only inventive and catchy but also irritating because the feelings of disgust it evokes in the prospects.
In terms of ethical terms, we may say that fearappeal is used intensely in serialized film 24. Both the uniforms and the masks and the warning text reflect a fatal danger and this leads to anxiety and misunderstanding.
In Perlodent ad, on which the brand name and logo also displayed, is ethically questionable especially for the potential effects it can have on children. It is not hard to imagine the negative consequences of the ad on children especially when we consider the fact that kids usually imitate the behaviors they find interesting. In the absence of a parent or a guard, the kid may attempt at opening such metal lids, which may lead to serious injuries.
It is possible to argue that the horrifying fearappeal used in Kill Bill study is ethically problematic. The images used in this ad may have negative consequences for the viewers. Especially if the person that is exposed to these scenes is a kid, this may cause psychological problems and even end up the kid not being able to go to the restroom alone.
In Pringles ad, it is highly likely for the driver that is behind the cab to be distracted when going through the traffic. This ad which may lead to accidents is just as ethically problematic as the others.

DISCUSSION
As previously mentioned, nature of guerilla advertising brings the ethicality of some practice into question. Guerrilla ads that use extensive fear-appeal may cause irritation and lead to anxiety disorder in consumers. Assessment of the ads above indicated that 24, D.D. Dirin and Kill Bill examples used this appeal. Apart from causing ethical problems, such guerilla advertising strategies that irritate prospects may also lead to the development of negative attitudes towards the brand.
Guerilla advertising even carries some dangers. For instance, ads placed in the middle of the road or on public buses, cabs, or private vehicles (as in the case of the Pringles ad) may cause traffic accidents as it distracts the drivers. Their content and design may carry the risk of jeopardizing the traffic.
Guerilla advertisement sometimes may have a negative effect on children. Behavior imitations like opening metal lids by teeth, which is mentioned in Perlodent ad, may be a problem for kids as it may cause tooth or mouth injuries. Therefore, firms should add a caution note at the bottom of the poster to warn the kids not to try the same thing.
Trespassing on private or public property without getting permission is the other ethical problem of guerrilla advertising. Placing pictures or flyers illegally on public buses, bus stops, building walls etc. indicates this problem.
As it can be understood from the discussion of the subject and the examples presented, a boundary must be maintained between creative strategies of guerilla marketing and their irresponsible applications. Despite the unrestrained nature of guerilla activities, ethical, legal and social boundaries must be achieved.
In order to obtain more effective and generalizable results, future studies should address the ethical problems caused by other guerilla marketing tools instead of guerrilla advertising. Different types of guerilla marketing applications and the ethical problems they cause should be demonstrated using concrete examples and data.

CONCLUSION
The goal of guerilla ad is to increase customer awareness and interest through the product and its associated brand. Acceptability of a guerilla ad is related to its ends rather than its means. Although there are successful examples of guerilla marketing strategies, some of guerilla advertising implementations that are prepared and executed without certain boundaries may lead to ethical problems. Those ads, which include fear-appeal, irritate the prospects and distract attention, may be problematic in ethical terms.
It is argued that the use of extensive fear-appeal may reduce the effectiveness of advertisements in general. Public dislike of an ad may lead to the erosion of the goodwill and may reduce the short-term and particularly, the long term effectiveness of that advertisement. At the same time, dislike of a company's ad may have negative effects on future advertisements. Firms should continue to search for creative ways to connect with their customers, but they have to implement these new strategies in a more responsible manner because the ethicality of guerilla ad is measured by its consequences.


s2fieldsofstudy:
Business
Computer Science

text:
Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas

Long-distance multi-hop wireless networks have been used in recent years to provide connectivity to rural areas. The salient features of such networks include TDMA channel access, nodes with multiple radios, and point-to-point long-distance wireless links established using high-gain directional antennas mounted on high towers. It has been demonstrated previously that in such network architectures, nodes can transmit concurrently on multiple radios, as well as receive concurrently on multiple radios. However, concurrent transmission on one radio, and reception on another radio causes interference. Under this scheduling constraint, given a set of source-destination demand rates, we consider the problem of satisfying the maximum fraction of each demand (also called the maximum concurrent flow problem). We give a novel joint routing and scheduling scheme for this problem, based on linear programming and graph coloring. We analyze our algorithm theoretically and prove that at least 50\% of a satisfiable set of demands is satisfied by our algorithm for most practical networks (with maximum node degree at most 5).

I. INTRODUCTION
Standardization of the air interface for IEEE 802.11 and 802.16 has resulted in rapid production and deployment of WiFi and WiMAX based mesh networks. Such multi-hop mesh networks have several applications including wireless backhauling for 3G cellular networks, and low cost networking for rural connectivity [1], [2], [3], [4]. In such networks, one typically makes a distinction between long-distance links and much shorter local access links [5]. In this paper, we are concerned only about long-distance links which set up the backbone of the network. These links are set up by highgain directional antennas mounted on top of tall towers to achieve Fresnel clearance above obstructions [6], [7]. Typically, a subset of network nodes (called gateways) have direct connectivity to the Internet. The remaining nodes (called mesh nodes) use multi-hopping to access the Internet through the gateway nodes.
The focus of this paper is the design of joint routing and scheduling algorithms for throughput maximization in such multi-hop wireless mesh networks.
We assume that nodes are equipped with multiple radios and directional antennas. Directional antennas are helpful in mitigating interference and improving spatial reuse [8], [9]. A node communicates with its neighboring nodes using line-of-sight point-to-point wireless links. Each antenna is * This work was done when the authors were at Bell Labs Research India.
connected to a single radio at the node. For such a setting, it has been experimentally demonstrated on commercial off-theshelf wireless equipment [8], [10] that either (i) concurrent transmission on all the radios of a node, or (ii) concurrent reception on all the radios of a node is possible. This is because the directional antennas effectively isolate the signals of all the incoming links. However, if one radio is transmitting during a given time slot, and another radio on the same node is receiving concurrently, then due to radiation leakage and the proximity of the two antennas, the transmitted signal can drown the received signal. Hence transmission on one radio, and concurrent reception on another radio of the same node is not permitted. We refer to this operation of concurrent transmission or concurrent reception on all the radios of a node as SynOP (synchronous operation). For the above network model, we consider the problem of joint routing and scheduling to best meet a given set of source-destination demands.
Kodialam and Nandagopal have studied the joint routing and scheduling problem for the omni-directional antenna setting with single radio nodes in [11], and multi-radio nodes in [12]. In [13], Narlikar et al. consider the multi-radio setting with directional antennas, and propose heuristic algorithms for joint routing and scheduling. We show that the routing-scheduling problem that arises in multi-radio directional antenna setting is fundamentally different from the multi-radio omni-directional antenna scenario considered in [11], [12]. Furthermore, in contrast to [13], we provide a provably near-optimal scheme for joint routing and scheduling for this scenario. Our main contributions are: • Formulation of the problem as an (exponential-sized) linear program (LP) with joint routing and scheduling constraints. • A novel scheduling algorithm based on directed edge coloring in a multi-graph. • An algorithm for joint routing and scheduling based on solving a modified (polynomial-sized) version of the above LP, and then using the scheduling algorithm to produce a valid schedule for the LP solution. • Analysis of the above algorithm showing that for a large class of network graphs (maximum node degree of 9), at least 40% of the maximum concurrently satisfiable demand for each source-destination pair is satisfied by our algorithm. For network graphs with maximum node degree of 5, which encompass most practical mesh network deployments, our solution has a provable performance of at least 50% of the optimum. Although we focus on only a TDMA model, our results can  be easily extended to a mix TDMA-FDMA model, as well as  the OFDMA model of IEEE 802.16. II. SYSTEM MODEL AND PROBLEM FORMULATION Consider a mesh network graph G = (V, E) where V is the set of mesh nodes, and E ⊆ V × V is the set of directed links. A link is formed between two nodes by aligning the directional antennas on each of the nodes. Results in [8] show how to dimension the transmit powers of radios of different nodes so that desired SINR (Signal to Interference and Noise) requirements are met despite side lobe leakage, and concurrent reception on multiple directional links at a node is possible. 1 In the network graph, the same physical link is modeled using two opposite directed links, and we say that a directed link is active when the underlying physical link is active in that direction. Throughout this paper links refer to directed links. Let C(e) be the capacity of link e. Since the nodes are static, and the links are line-of-sight, we assume that the link capacities are fixed, i.e., there are no shadow-fading time variations. However, note that slow time variations in link capacities can be easily incorporated in our framework by adapting the routing and scheduling policies over longer time scales.
We are given a set of M demands (rates), where the k th demand requires a rate of r k from source s k ∈ V to destination d k ∈ V . If all the traffic is only between the mesh nodes and the Internet, and if the gateway nodes are assumed to be directly connected to the Internet through a high speed connection (a typical mesh network architecture), then the above model can be easily modified as follows. We add a node (corresponding to the Internet) to the network graph, and connect it to all the gateways using links of infinite capacity. We make the following assumptions about the capabilities of the nodes, and the interference constraints: • Each node has a dedicated radio and a corresponding directional antenna for communicating with each of its neighbors. • All the radios operate on a common channel. • Transmissions are synchronized in time (TDMA operation), and in each slot, a subset of links in the network are activated. • During each time slot, a node can concurrently transmit on all its outgoing links, or concurrently receive on all its incoming links. However, concurrent transmission on one link and reception on another link within the same slot at a node is not allowed. 1 Note than, when omni-directional antennas are employed, it is not possible to dimension the transmit powers for concurrent reception. Consequently, with omni-directional antennas, for a given time slot/channel, only a single radio can be actively receiving, while with directional antennas all the radios can concurrently receive packets. This important difference between omnidirectional and directional antennas results in two fundamentally different scheduling problems.
The last constraint arises because of side-lobe radiation leakage from the directional antennas. Due to this leakage, a transmission on a radio can completely drown a reception on a nearby radio. Thus in a slot, the set of nodes can be bipartitioned into a set of transmitters and a set of receivers. This immediately implies that the set of active links in each slot forms a directed bipartite subgraph from the transmitters to the receivers. 2 In the rest of this paper, unless stated otherwise, a bipartite graph refers to a directed bipartite graph.
A schedule of length T specifies for each slot 1 to T , the set of links that are active in that slot. In our setting, a schedule is valid if the set of links that are active in any time-slot forms a directed bipartite graph. In other words, a valid schedule is a sequence of bipartite subgraphs. Note that the bipartite subgraphs need not be disjoint and the same link may appear in multiple time-slots, either as part of different directed bipartite subgraphs or in the same subgraph which is repeated in multiple time-slots. The utilization of a link e in the schedule is then defined as the ratio of the number of slots in which e is active to the length of the schedule. The effective capacity of link e in a schedule is therefore the product of its utilization and its total capacity C(e).
A routing specifies the amount of flow on every link for every source-destination demand. The link flow vector of a routing specifies the total flow load (due to all sourcedestination demands) on each link. We say that a routing can be scheduled if there is a valid schedule such that the effective capacity of every link in the schedule is at least as much as the total flow load on the link. Note that some routings may not have a feasible schedule. The concurrent flow value of a routing is the largest λ such that the routing satisfies at least λ fraction of every source-destination demand. For a graph G and a set of source-destination demands, the maximum concurrent flow (or max flow) is defined as the maximum λ such that there is a routing that has concurrent flow value of λ. Then, our joint routing and scheduling problem is the following: Given a network graph and a set of sourcedestination demands, among all routings that can be scheduled in our model, find a routing (and its corresponding schedule) that has the maximum concurrent flow.
An LP formulation. Let B be the set of all directed bipartite subgraphs of the given graph G = (V, E). By simple counting arguments, |B| = 2 n − 2 where n = |V |. Thus, any feasible activation of links in a time slot is one of the subgraphs in B, and any schedule can be represented as a weighted combination of elements B i ∈ B. Here the weight of a particular directed bipartite subgraph B i is the fraction of time-slots in which B i is active. For a schedule π, let w B1 , w B2 , . . . , w B |B| be the associated weights. Let 1 e,B be the indicator function which is 1 if link e is present in the directed bipartite subgraph B ∈ B.
Maximize λ (1) Subject to: Let N in (v) represent the set of incoming links at node v, and N out (v) represent the set of outgoing links at node v. As mentioned in Section II, we are given a demand vector of M flows, such that, demand k consists of source node s k and destination node d k with a desired rate r k . Let f (e, k) denote the load on link e due to demand k, and let S and D denote the set of source and destination nodes for these demands. Then the maximum concurrent flow problem in our model can be formulated as the LP in Figure 1. In the above LP, Eq. (2)-(5) are the regular flow constraints, while Eq. (6)-(7) are the scheduling constraints. The LP finds the optimum weights w Bi for all the bipartite graphs, and the corresponding link flow values. While solving the above problem gives the optimal max-flow solution, its computational complexity is very high. This is because the number of bipartite subgraphs in B is exponential in the number of nodes, and hence the LP has exponential number of variables w Bi . We therefore look for approximation algorithms for the above problem. Our general plan in designing the approximation algorithms is as follows. Consider a particular routing with a link flow vector f : E → R + 0 representing the total flow load on each directed link in E. The corresponding routing can be scheduled in our setting provided there exists a schedule which can achieve a utilization of at least f (e)/C(e) for each link e ∈ E. We first derive a set of necessary conditions for scheduling a particular link flow vector. In other words, if there exists a schedule that achieves the required utilization, then these conditions have to be satisfied. The optimal flow vector given by the solution to the LP must therefore satisfy the necessary conditions. Then, we derive a set of sufficient conditions for the same problem, i.e. if these sufficient conditions are satisfied, then the link flow vector can be scheduled. Our sufficient conditions are based on a scheduling algorithm that can schedule any link flow vector that satisfies these conditions. Adding the sufficient conditions to the LP formulation possibly changes the optimal value of λ. However, by comparing the necessary and sufficient conditions, we bound the decrease in the optimal LP value when the sufficient conditions are added to the LP. The sufficient conditions replace the exponential number of constraints involving w Bi in the LP and make the LP tractable. We solve the LP to obtain a flow vector which can now be scheduled since it satisfies the sufficient conditions. The ratio between the necessary and sufficient conditions gives the approximation bounds on our algorithm. We may note that the overall plan of our algorithm is similar to [11], however our necessary and sufficient conditions as well as our scheduling algorithms are very different.

III. NECESSARY CONDITION
To schedule a link flow vector f corresponding to a routing, each link e must have a utilization of at least f (e)/C(e). Since a node cannot activate an incoming and an outgoing link simultaneously, the sum of utilization of an incoming link and that of an outgoing link (at the same node) must add up to at most 1.
Theorem 1: If a link flow vector f can be scheduled, then The above necessary condition at a node depends only on the most heavily loaded pair of incoming and outgoing links. This is because in our model we are allowed SynOP at a node (synchronous reception on all the links, and synchronous transmission on all the links). In sharp contrast, the model considered in [11] has omni-directional antennas, and therefore only allows one link to be active per channel, at a node. Thus their necessary condition depends on the sum of the loads on all links of a node.

IV. SUFFICIENT CONDITIONS USING EDGE COLORING OF A DIRECTED MULTIGRAPH
In this section, we give a new scheduling algorithm and an associated set of sufficiency conditions. We first introduce some terminology that we use throughout this section. A multigraph is a graph in which there could be multiple parallel edges between two nodes. In the rest of the paper, unless explicitly specified, by multi-graph, we refer to a directed multi-graph. The underlying simple (directed) graph of a multi-graph is produced by replacing each multi-edge by a single (directed) edge. The multiplicity of an edge in the underlying simple graph is defined as the number of copies of the edge that are present in the multi-graph. Any two different copies of the same simple edge in the multi-graph are said to be parallel edges. Note that an edge from u to v is not a parallel edge of an edge from v to u. Such edges are referred to as anti-parallel or opposite edges. For any directed graph (either a multi-graph or a simple graph), the corresponding undirected graph is produced by replacing each set of parallel and anti-parallel edges (i.e. all edges between two vertices u and v in both directions) by a single undirected edge.
Let τ be the duration of a time slot. Since C(e) bps is the capacity of link e, in order to carry a traffic of f (e) bps, link e should be scheduled in at least f (e) C(e)τ slots every second. We therefore associate weight w(e) with link e, and consider a multi-graph G where link e = (u, v) is replaced by w(e) directed links from u to v. (We assume that f (e)/C(e) are rational, and we choose τ so that all the w(e) are integers.) Now, our scheduling problem reduces to allocating timeslots to each edge in the multi-graph G, where the duration of each time-slot is τ seconds. Considering each time-slot as a color, the slot allocation problem is an edge coloring problem for a directed multi-graph such that, the following two types of interference constraints are satisfied. Local Overlap Constraint: At every node, the color (timeslot) allocated to an outgoing edge is different from the colors allocated to the incoming edges. This ensures that no node concurrently transmits over one radio, and receives over another radio. Parallel Overlap Constraint: No two parallel edges are allocated the same color. If two parallel edges get the same color, then it implies that the corresponding link needs to be activated twice in the same time-slot; clearly, this is not possible.
A similar multi-graph edge coloring problem was considered in [11] for undirected multi-graphs where the local overlap constraints don't exist. In another related work in [10], a similar edge coloring problem was studied in the context of simple (directed) graphs where the parallel overlap constraint does not exist. The authors called this problem the directed edge coloring problem or the DEC problem. In the following subsection, we provide a brief overview of the DEC algorithm proposed in [10].
DEC algorithm for simple graphs. Let G be the given simple directed graph with maximum vertex degree Δ. Consider the vertex coloring of the undirected graph corresponding to G with K ≤ Δ + 1 colors. 3 Let each vertex color class (set of vertices with the same color) form a supervertex and let N be the set of supervertices in G. First, note that each supervertex is an independent set of vertices (i.e., no pair of vertices with 3 Recall that the vertex coloring problem on an undirected graph aims to color all the vertices in the graph using the minimum number of colors such that no two vertices sharing an edge are assigned the same color. It is wellknown that the vertex coloring problem is NP-hard [14]. However, for our purpose a (sub-optimal) polynomial-time vertex coloring algorithm suffices: the well-known greedy algorithm using Δ+1 colors where Δ is the maximum degree of a vertex in a graph. Thus we assume K ≤ Δ + 1. ≥ K; therefore, we have sufficiently many edge colors for each supervertex to get a distinct edge color set. The edge color set at a supervertex v represents the colors that may be used to color an edge leaving v. Now, it can be easily shown that corresponding to each edge in G, there is at least one edge color which is in the edge color set at its origin supervertex and is not in the edge color set at its destination supervertex. This color is assigned to the corresponding edge. Thus, this algorithm uses ξ(K) colors for the DEC problem. It was shown in [10] that ξ(K) log K for large values of K. For smaller values of K, see Figure 3.

A. Multi-DEC scheduling algorithm
Since our problem of edge coloring the multi-graph generated by weights w(e) in Eq. (9) is similar to the DEC problem, we call it the directed multi-edge coloring problem or the multi-DEC problem. Formally, we are given a multi-graph G = (V, E), and we need to color the edges of this multigraph with the minimum set of colors such that the local and the parallel overlap constraints are satisfied. Roughly speaking, the algorithm we propose for multi-DEC splits the given multigraph into several "almost" simple subgraphs, and edge colors each of these subgraphs using a modified DEC algorithm.
We first present some definitions required to describe our scheduling algorithm. A (directed or undirected) multi-graph is said to be almost simple if the maximum multiplicity of any edge in the graph is 2. The weight of a node v in a multi-graph H = (V, F ) (denoted by W (v, H)) is the sum of multiplicities of the most heavily loaded incoming and outgoing links of the node. Thus, if w(e) is the multiplicity of edge e in H, then vertex v is said to be tight if W (v, H) = W max (H). For example, the edge between nodes u and v in Fig. 2(a) is Let G s and G u be the underlying simple graph and corresponding undirected graph of the multi-graph G that is to be directed edge colored. Suppose that G u can be vertex-colored using K colors. Then, from [10], G s or any of its subgraphs can be directed edge colored using ξ(K) colors. We now give a scheduling algorithm that assigns colors to the edges of G.
Scheduling Algorithm. Case (i): ξ(K) = 1: G s is a directed bipartite graph. We partition G into W max (G) directed bipartite graphs, each of which is given a distinct color. Case (ii): ξ(K) ≥ 2: We use the following iterative procedure. Let G k be the subgraph of G used in the k th iteration of the algorithm. Initialize G 1 = G. In each iteration k, perform the following steps (each iteration uses a new set of colors): 1) Form an almost simple graph, G k as , as follows. Initialize G k as = G k s , the underlying simple graph of G k . If edge (u, v) is tight in G k , then add another copy of (u, v) to G k as (see Fig. 2(c)). Let these second copies of edges form the setÊ k as . 2) Color the edges in G k s using the DEC algorithm from [10] (at most ξ(K) new colors). For any edge e ∈Ê k as , assign one of the ξ(K) colors (that were used in coloring the edges in G k s ) excluding the color assigned to its parallel edge in G k s . 3) The subgraph G k+1 used in the next iteration is the residual graph obtained by removing the edges colored in this iteration from G k (see Fig. 2(d)). If G k+1 has no edge then the algorithm terminates. Otherwise, increment k, and go to Step 1.
It can be shown that the color assignment given by the above algorithm does not violate local and parallel overlap constraints [15]. Also we can show the following theorem (proof in [15]) on the number of colors required by the above algorithm. Theorem 2: The multi-DEC algorithm uses W max colors when ξ(K) = 1, and ξ(K)W max /2 colors when ξ(K) ≥ 2, where the corresponding undirected graph of G can be vertex colored using K colors. This theorem gives the following sufficiency conditions.
for each pair of edges e ∈ N in (v) and e ∈ N out (v) for each vertex v.

B. Joint Routing and Scheduling Algorithm
We exploit the sufficiency conditions of Corollary 1 in our algorithm. In the original LP formulation (Eq. (2)-(7)), we replace the scheduling constraints (Eq. (6)- (7)) with the constraints: f (e) C(e) + f (e ) C(e ) ≤ Y, ∀v ∈ V, e ∈ N in (v), e ∈ N out (v) (11) where Y = min 1, 2 ξ(K) . Note that the above constraint amounts to no more than Δ 2 constraints for each node. Thus, the LP is tractable. The link flow vector in the solution of the LP is now scheduled using the Scheduling Algorithm. The approximation ratio of this algorithm is given by the following theorem (full proof in [15]).
Theorem 3: The above LP (along with the Scheduling Algorithm) provides a 2/ξ(K)-approximation to the joint routing and scheduling problem when ξ(K) > 2, and provides an exact solution for the cases of ξ(K) = 1 and ξ(K) = 2.
Proof Sketch: Comparing the necessary condition in Eq. (8) and the sufficient condition in Eq. (10), we note if ξ(K) = 1 or ξ(K) = 2, the necessary and sufficient conditions are identical, and for ξ(K) > 2, their ratio is at most 2/ξ(K). Thus, any flow vector that satisfies the sufficient condition is at least 2/ξ(K) times the optimum. Recall that, K ≤ Δ + 1, where Δ is a maximum degree of a node in a graph. Noting the values of ξ(K) from Figure 3, we observe that for a large class of practical network deployments (maximum node degree of 9), our proposed algorithm obtains a solution that is within 40% of the optimum. For more typical network deployments (maximum node degree of 5), our solution comes to within 50% of the optimum.