Improving the calculation speed of transmith power minimum problem for multi - Antenna wireless transmission network

C min f  X X (1.46) subject to ( ) 1rank X (1.47) where X is a symmetric matrix PSD and f(X) is convex function. The constrain condition (1.47) of the problem (1.40) is a non-convex function, the problem (1.46) is the optimal-NP-hard problem. Condition (1.47) can be transformed into xe( ) ( ) 0matrac  X X (1.48) where x ( )ma X is the largest eigenvalue of matrix X. If xe( ) λ ( )matrac X X then xe( ) ( )matrac X X , this means that only one unique eigenvalue of X satisfies: x x x( ) H ma ma maX λ X x x (1.49) Where xmax is the unit eigenvalue vector x( 1)ma x of X corresponding to the maximum eigenvalue x ( )ma X . Because x ( )ma X is a convex function on the set of the Hermitian matrix, therefore, constrain condition xe( ) ( )matrac X X is concave function. In order to constraint condition to satisfy (1.48), xe( ) ( )matrac X X should be small enough. Based on the theory of the penalty function, the problem (1.46) is put into the form of problem using the penalty coefficient: N N ma0 C ( ) [ ( ) ( )]xmin f μ trace λ    X X X X (1.50) in which the penalty value 0  should be determined as appropriate to achieve a condition xe( ) ( )matrac X X small enough. To solve the problem (1.50), it is necessary to optimize both components ( )f X and xe( ) ( )matrac X X . Regarding the speed of convergence during the process of formulating algorithm, the choice of coefficients and the steplength of penalty factors after each iteration will affect the convergence rate. 1.7. Computational complexity of the optimization problem In fact, the minimum power problems for wireless transmission models presented in section 1.4 are combined optimal problems belonging to non-deterministic polynomial-time hard (NP-hard) problem. Problems with a small number of operations can be solved by directly search methods. Problems with great complexity using previously proposed optimization techniques often cannot find out the optimal solution or the determined value has a large tolerence with the real optimal value. The complexity of the problem may be the number of calculations (including the number of memory accesses, or write to memory), but it also can be the total program execution time or the capacity of memory that needs to be allocated to run the program (spatial complexity). The procesing time for computer in algorithm performing is not only depending on the algorithm but also computer’s configuration. In order to evaluate the effectiveness of an algorithm, considering the number of calculations that must be processed by algorithm running. The effectiveness of an optimal technique is considered the optimal algorithm of construction techniques in many aspects: 1. Effective application on problems: convex / non-convex problem, constraint/ non-constraint. 2. The speed of convergence of the algorithm: calculation time/ number of iterations. 3. Algorithm's solution quality: The results are obtained through stopping criterium or local/global solutions of the cost function. The problems of optimal transmit power in multi-antenna wireless transmission network belong to the NP-hard problem. Therefore, in order to analyze the computational complexity of algorithms, this section we use the complexity analysis formula of SDP problem. SDP optimization problem with constrain condition is stated follow ( ) NR min trace x CX (1.47) subject to ( ) 0i itrace , , i = 1, 2. . . , M. A X b X (1.48) where C and Ai are symmetric matrices, then the complexity of the problem is determined: ( log log( ))n n n/ε , with ε is the parameter of the algorithm. In order to estimate the complexity of optimization problem SDP, it is necessary to determine the array parameter n of matrices in the object function and constraint condition. Number of calculations depend on the size of the problem,. In the survey models of the thesis, the complexity of problem depend on: the number of transmit antenna at base station, number of antennas at the relay node, number of transmitters and receivers, SINR threshold. 1.8. Conclusion of chapter 1 Research, development and apply effective optimization techniques for solving minimum power transmission problems in multi-antenna wireless transmission network with great scientific and practical significance. In particular, the penalty function technique is selected to determine the minimum transmit power while improving the convergence speed compared with random, SDR optimization techniques,. Based on the outstanding issues, the thesis proposes sollutions for the following chapters: 1. Improvement the calculation speed for the minimum power transmission problem for the base station wireless transmission model by minimum the penalty coefficient. 2. Improvement the calculation speed for the minimum power transmission problem for the transitional wireless transmission model with AF processing by adding additional variables in the penalty function of the object function. The results in chapter 1 have been published in scientific papers [3]. CHAPTER 2. IMPROVEMENT THE CALCULATION SPEED FOR MINIMUM TOTAL TRANSMIT POWER AT BASE STATION 2.1 Minimum problem of transmit power at base station 2.2. Formulating transmit power minimum problem at base station The multi-antenna base station transmission broadcasting multipoint model is shown in Figure 2.2. In particular, the base station is equipped with N transmit antennas that broadcast the same information (without interference) to the destination M users. Figure 2.2: Model of multi-antenna base station transmission broadcasting multipoint where 1 2[ ] T i i i iNh ,h ,...,hh is the channel vector between the base station and the i th user. The problem need to design an optimal weight vector x at the base station with the signal xS that transmitted to all users on the receiver. Then, the total transmit power of the antennas at the base station is determined by ( )HTP trace xx (2.1) The objective of the problem is to find out optimal vectors x that to minimized total radiated power of the antennas at the base station with SINR constraint condition greater than the threshold i . The signal to noise ratio at the i th user is determined by 2 ( ) ; H i i i H i itraceSINR i 1, 2, .., M     xxh h (2.2) with 2i is the additive white Gaussian noise of the i th user on the receiving side. The problem (2.6) is converted to the SDR problem through transformation HX x x , Hi i iH h h with X is a PSD matrix. The problem of minimum transmit power at the base station is determined by ( ) NC min trace X X (2.3) subject to: 2 ( )i i i i Htrace SINR , i 1, 2..., M.     HX (2.4) HX xx (2.5) To solve the problem (2.3), it is necessary to add the constraint condition for X satisfying the condition of rank (X) = 1. So the problem (2.3) is stated as follow ( ) NC min trace X X (2.6) subject to: 2 ( )i i i i Htrace SINR , i 1, 2..., M     X H (2.7) HX xx (2.8) ( ) 1rank X (2.9) If problem (2.7) determines optX that satisfied the condition ( ) 1rank X then optX = xoptxopt H is considered the optimal value of the problem. In case matrix optX is analysed in SVD form to determine the optimal vector xopt. 2.3. Nonsmooth optimization technique used penalty function Constrain condition of the problem (2.7) can be expressed:  max( ) 0trace  X X (2.12) If trace(X)  λmax (X) is always true for all values 0X , then (2.12) becomes  max( )trace X X (2.13) This means that only a specific value of X other than 0 satisfies the condition  max max max HX X x x (2.14) where xmax is the eigenvector of X corresponding to the maximum eigenvalue x ( )ma X . Based on (2.12), the problem (2.7) is presented by 0 ( ) N NC min trace  X X (2.15) subject to 2 ( )i H i i i trace SINR , i = 1, 2,..., M.    HX (2.16)  max( ) 0trace  X X (2.17) When trace(X) - λmax (X) is small enough, then  max max max HX X x x , 1/2x x( )ma ma X x satisfies the constraint condition SINR of the problem (2.7). Therefore, the target of the problem should be optimally implemented so that trace(X) − λmax (X) reaches the minimum value. Under these conditions, using the penalty function technique combined with the objective function, then the problem (2.15) becomes  max 0 ( ) ( ) ( ) N NC min f trace trace        X X X X X  (2.18) subject to 2 ( )i H i i i trace SINR , i = 1, 2,..., M.    HX (2.19) On the other hand, the component gradient is x x H ma max x , by using mathematical properties: max max max max( ) ( ) (( ) ), 0 H Htrace     Y X Y X x x Y (2.20) Based on the repeatability property, if X (k) is the optimal value of the kth iteration of the problem (2.18) with the largest eigenvalue λmax(X(k)) corresponding to the eigenvector X(k) . Then, set up the problem (2.21) at the k + 1 iteration,: ma ( ) ( ) x ) 0 ( ) ( H( ) ( ) ( ) (( ) ) N N k k kH C kmin trace trace trace        X X X X xxX X  (2.21) subject to 2 ( )i H i i i trace SINR , i = 1, 2,..., M.    HX (2.22) become an SDP problem as (2.23)  ( ) ( ) 0 H( ) ( ) ( ) N N kH k C min trace trace trace     X x xX X X (2.23) subject to 2 ( )i H i i i trace SINR , i = 1, 2,..., M.    HX (2.24) When applying the Nonsmooth non-convex optimization technique, the penalty function needs to be performed in two stages to solve the problem (2.21). Specifically, at the initialization stage, choose an appropriate set of values ( , (0) X ). Proceeding to determine the optimal value (k 1)X that satisfied the constraint condition and given value  through solving the problem (2.21). The optimal stage selects the optimal value (k 1)X and fixes the value of µ from the initialization stage, continues to solve the problem (2.21) for determining the Xopt that satisfied the constrain condition. The key steps of algorithm for Nonsmooth technique combined penalty function approach are outlined in Algorithm 1. Algorithm 1 ------------------------------------------------------------------------------------------------ % Initialization stage: - Initial step: Initialize proper  and (0)X to satisfy (2.21), set k = 0 - Step k: Solve (2.21) to obtain its optimal solution (k 1)X + if ( 1) xe( ) ( ) k matrac   X X (rank-one solution found) then Reset (0) ( 1): kX X . Terminate, and output  and (0)X . + else if ( 1) xe( ) ( ) k matrac   X X (no improved solution found, no rank-one result) then Reset : 2  and return to the initial step. else Reset : 1k k  and ( ) ( 1)k kX X for the next iteration. end if % Optimization stage: Set k = 0. Solve (2.21) to obtain its optimal solution ( 1)kX . if ( 1) ( )e( ) e( )k ktrac trac X X then Terminate, and output ( 1)k opt X X . else Reset : 1k k  and ( ) ( 1)k kX X Continue to the next iteration. end if Output the final solution for problem (2.21). ----------------------------------------------------------------------------------------------- Many previous publications when applying algorithm 1, the authors often choose µ empirically but they did not calculate specifically. There are many cases where the optimal value is determined, or some cases where the optimal value cannot be determined because selections does not proceed to the convergence area. There always exists a value so that the problem (2.19) will be finished after only a few iterations. The value is determined by: 0 1 Tmax   ν λ ν (2.25) However  is very difficult to be found as the dual Lagrangian formulation of (2.25) is also NP-hard. Hence the idea of finding the optimal value after only one iteration is almost impossible. Fortunately, if  is obtained by the Lagrangian relaxation of (2.25) it is still useful as this value will help reduce significantly the number of iterations in NSM method. The Lagrangian relaxation of (2.25) is established as, 2 0 1 M i i i i = max    λ (2.26) subject to ( ) 0,HN i i i = 1, 2,..., M. I h h (2.27) The key steps of our newly-devised approach are outlined as follow: Step 1: Obtain (0)X from (2.21) and 0 from (2.26). Step 2: Solve (2.21) and update  with very small amount. The solution is also updated ( 1) ( )k k X X . Step 3: When a rank-one solution is found, stop updating µ. X(k) is still updated and converges after very few iterations. 2.4. Simulation algorithm performance 2.4.1. SDR optimization algorithm performance 2.4.2. Random optimization algorithm performance 2.4.3. NSM1 optimization algorithm performance 2.4.3. NSM2 optimization algorithm performance 2.5. Numerical Results • Simulation 1 Simulation 1 compares SDR, random optimization techniques with Nonsmooth techniques (NSM1 and NSM2) with two criterias: the minimum total transmit power and the number of average iterations. The simulation parameters are shown in Table 2.1. Table 2.1: Simulation parameters 1 No Parameter Value 1 The number of users M on the receiver 16, 24 2 The number of antenna N at base station 8 3 The number of iterations for determining penalty factor µ 30 4 The number of iterations at the optimal stage 20 5 Number of iterations ITE at each SNR threshold 500 6 SNR threshold (dB) 2, 4, 6, 8, 10 7 Initialized power value Pw for random engineering 2000 8 Stopping criterium 1 for NSM1 optimization technique 10-6 9 Stopping criterium 2 for NSM2 optimization technique 10-6 10 Penalty factor µ in the initialization stage for NSM1 optimization technique 0.5 11 The steplength of penalty coefficient after each loop changes according to the exponential rule for NSM1 technique µ(k+1) = 1,5µ(k) - Total transmit power: Observing the simulation results in Figure 2.9 and Figure 2.10 shows that the Nonsmooth technique combined with the penalty function results closer to the lower boundary of SDR and better than the random technique. In particular, the results of the total minimum transmit power of NSM1 and NSM2 techniques are approximately value(the graphs of NSM1 and NSM2 overlap). In the case of Figure 2.9, when the SNR threshold is less than 4 dB, the optimal techniques give approximately results, but when the SNR is greater than 4 dB, the effectiveness of the Nonsmooth technique with the penalty function has been demonstrate advantages. This is also evident in the results of the graph of Figure 2.10 when increasing the number of users (M = 24). Detail data is shown in Tables 2.2 and 2.3. - Number of average iterations: Figures 2.11 and 2.12 describes the evaluation results, comparing the number of average iterations of the NSM2 technique with NSM1. Specifically, in the case of M = 16 and N = 8 when the threshold SNR ≤ 2 dB, the graphs of NSM1 and NSM2 in Figure 2.11 show that the number of average iterations of the two cases is the same. Observing the results in the case of Figure 2.12, the number of average iterations of the NSM2 technique remains stable around the value of 5 times. However, the NSM1 graph at the threshold SNR  6 dB, the number of average iterations tended to decrease because the number of average iterations in the simulation to get the average result was not enough (about a few hundred times). Simulation results do not reflect the theory. Remark: Through the results in simulation 1, it is confirmed that the advantages of Nonsmooth combined with penalty function technique compared to the random Figure 2.9: Comparison of total transmitted power in the case of M = 16, N = 8 Figure 2.9: Comparison of total transmitted power in the case M = 24, N = 8 Figure 2.11: Comparison of average number of iterations between NSM1 and NSM2 techniques (M = 16, N = 8) Figure 2.11: Comparison of average number of iterations between NSM1 and NSM2 techniques (M = 24, N = 8) optimization technique and move towards optimal value of SDR technology. The proposed optimization technique NSM2 has a fast convergence compared to the NSM1 optimization technique. However, the number of iterations ITE run for each SNR threshold is not large enough. That is reason why transmit power and the number of average iterations does not reflect the advantages of the proposed optimization technique. • Simulation 2 In order to demonstrate the effectiveness of the proposed NSM2 optimization technique, we conducted a simulation where the number of antennas at the base station N = 8 and the number of users in destination varied among the three cases: M = 16, M = 24, M = 32. In particular, increase the number of iterations for each SNR threshold is 1000 times. The simulation parameters are shown in Table 2.4. Table 2.4: Simulation parameters 2 No Parameter Value 1 The number of users M on the receiver 16, 24, 32 2 The number of antenna N at base station 8 3 The number of iterations itex for determining penalty factor µ 30 4 The number of iterations at the optimal stage 20 5 Number of iterations ITE at each SINR threshold 100 6 SNR threshold (dB) 2, 4, 6, 8, 10 7 Initialized power value for random engineering 2000 8 Stopping criterium 1 for NSM1 optimization technique 10-6 9 Stopping criterium 2 for NSM2 optimization technique 10-6 10 Penalty factor µ0 in the initialization stage for NSM1 optimization technique 0.5 11 The steplength of the penalty coefficient after each loop changes according to the exponential rule for NSM1 technique µ(k+1) = 1,5 µ(k) - Total transmit power: Observing the results on the graph in Figure 2.13 and detailed data in Tables 2.5, 2.6, 2.7 shows that the minimum power value of the proposed NSM2 technique is better in all cases at each SNR threshold. Based on the calculation of the power ratio in Table 2.8, it was shown that when increasing the number of users (M = 32), the transmit power ratio of PNMS2/PNMS1 fluctuated stably from 0.93 to 0.95. When M = 16 and M = 24 the PNMS2/PNMS1 ranges from 0.96 to 1.0. Thus, the total transmit power has had good results when using the optimal technique proposed NSM2. Table 2.8: Transmit power ratio of PNMS2 / PNMS1 SNR (M,N) = (16,8) (M,N) = (24,8) (M,N) = (32,8) 2 dB 1.00 0.97 0.93 4 dB 0.98 0.97 0.94 6 dB 0.98 0.97 0.94 8 dB 0.98 0.96 0.94 10 dB 0.97 0.96 0.95 Table 2.12: Number of average iteration ratio ITENSM2/ITENSM1 SNR (M,N) = (16,8) (M,N) = (24,8) (M,N) = (32,8) 2 dB 0.26 0.30 0.27 4 dB 0.27 0.27 0.29 6 dB 0.23 0.22 0.24 8 dB 0.22 0.21 0.24 10 dB 0.21 0.20 0.21 - Number of average iterations: The graph in Figure 2.14 and detailed data in tables 2.9, 2.10, 2.11 also demonstrate that the proposed NSM2 optimization technique has decreased significantly when compared to the NSM1 optimization technique. Specifically, from the graph in Figure 2.14, the number of average iterations of the proposed technique is reduced by 3.5 to 6 times and reaches a steady value when changes SNR threshold. Table 2.12 shows the number of average iterations of ITENSM2/ITENSM1 between NSM2 and NSM1 techniques. These data have shown that the ratio of ITENSM2 / ITENSM1 varies from 0.21 to 0.30 for the cases. In particular, in case of M = 32, the number of average iterations of the NSM2 optimization technique has decreased from 71% to 79% compared to the NSM1 technique. Remark: Through simulation results have shown that proposed techniques is not only determining the optimal value but also requiring additional calculations. In the case of small scale problem (M, N is small number), increasing the computational complexity in the case of optimal parameter µ does not improve the Figure 2.13: Comparison of total transmitted power between NSM1 and NSM2 techniques Figure 2.14: Comparison of average number of iterations between NSM1 and NSM2 techniques convergence speed too much. However, in case of large scale problem (M, N is large number), the optimization of penalty parameter µ become to greatly improves the convergence speed in determining the minimum transmit power. 2.6. Conclusion of chapter 2 In chapter 2, the thesis achieved some results as follow: - Formulated simulation algorithms using software Matlab in combination with SDPT3 and Yalmip tools to evaluate the results of the proposed optimization techniques compared to SDR and random optimization techniques. - The simulation results have proved that SDR technique gives better results than random techniques. In addition, the application of Nonsmooth technique combined with penalty function has results is not only asymptotic to SDR technology but also better the convergence speed. However, the random selection of penalty coefficients and the steplength of the coefficients will affect the speed of convergence. - The proposed optimization technique NSM2 has performed the optimal calculation of the penalty coefficient is not only determining the optimal value but also improving the speed of convergence. The effectiveness of the proposed solution is even more evident when the scale of the problem increases in the number of users on the destination as well as the number of antennas at the base station at each SNR threshold. In particular, the number of average iterations of NSM2 technique has decreased from 70% to 80% compared to NSM1 techniques. The results in chapter 2 have been published in two scientific papers [5] and [6]. CHƯƠNG 3. IMPROVEMENT CALCULATION SPEED FOR TOTAL TRANSMIT POWER MINIMUM PROBLEM IN MULTI- ANTENA WIRELESS RELAY TRANSMISSION NETWORK 3.1. The transmit power minimum problem in multi-antenna wireless transmission network. 3.2. Multi-antenna wireless relay transmission model with AF processing protocol 3.2.1. Amplifier and forward method AF 3.2.2. Mathematical basis for formulating the total transmit power minimum problem 3.2.3. Formulating minimum problem for the multi-antenna relay model Consider a scenario of MIMO relaying communication as shown in Figure 3.2, where M sources communicate in pairs to other M receiver destinations with the assist of an N -antenna MIMO relay. Since the use of the MIMO relay is to increase the coverage of communications links, it is reasonable to assume that the direct links between sources and destinations cannot be established. A dual- hop MIMO relay operating in the amplify-and-forward protocol mode is considered. Let 1 2[s ,s ,...,s ] T M Ms   be the vector of signals sent by M sources, which are assumed to be zero mean and component-wise independent with variance 22 [ ]s iE s  . The MIMO Rayleigh flat-fading channels are considered in the chapter. Let 1 2[h ,h ,...,h ] , 1,2,..., T N i i i iNh i M   be the uplink channel vector between source i and the relay while 1 2[l ,l ,...,l ] , 1,2,..., T N j j j jNl i M   denotes the downlink channel vector between the relay and destination j. The signal vector 1 2[s ,s ,...,s ] T M M C s is sent by M sources which assumed to be zero mean independent and variance 22 [ ]s iE  s . For 1 2[h ,h ,...,h ] T N i i i iN C h as the uplink channel vector between the user ith at transmitter and relay node, 1 2[l ,l ,...,l ] T N j j j jN C l is the downlink channel vector between jth the relay and user jth at destination. Figure 3.2: MU-MIMO wireless relay model with AF processing method The signal is processed from the sources to the destination as follows: + On the first hop, all sources simultaneously transmit the signals to the relay. The received signal at the relay is given by up r y Hs n (3.13) where H is the uplink channel matrix that contains all the channel vectors as its columns and 1 2[n ,n ,...,n ] , 1,2,..., N T N r r r rNn i   represents the additive noise at the relay receivers, which is assumed to be white Gaussian noise with zero mean and variance 22 [ ]r rnE n  , + The second stage, relay transmits signal after processing to the users in destination. Then, X is the optimal weight matrix is multiplied by the receiver signal at the relay. Therefore, the relay sends the following signals to the destinations: relay up r  y Xy XHs Xn (3.14) Accordingly, the received signal vector at the destinations is d r dy   LXHs LXn n (3.15) where dn is additive white Gaussian noise at the destination with element variance 2 d and L is the