QoS-aware User Association and Transmission Scheduling for Millimeter-Wave Train-ground Communications

To tackle the optimization problem formulated in the Section IV, we will introduce a coalition game model, where the flows form coalitions to improve the system utility. In our investigated system, there are $N$ flows, and the flows can choose to associate either with the BS or with the MR. Hence, there are two coalitions, and we denote them by $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$. Specifically, $\mathcal{F}_{1}$ represents the set of flows associated with the BS, while $\mathcal{F}_{2}$ represents the set of flows associated with the MR. Clearly, for our entire coalition $\mathcal{F}=\{\mathcal{F}_{1},\mathcal{F}_{2}\}$, we have

where $\big{|}\mathcal{F}\big{|}$ denotes the cardinality of the set $\mathcal{F}$.

Recall that the transmission rate $R^{k}_{{\rm BS},i}$ over the link that flow $i$ is sent from the BS to a user is given by (8). Thus the sum rate associated with the coalition $\mathcal{F}_{1}$ is

Also the transmission rate $R^{k}_{{\rm MR},i}$ over the link that flow $i$ is sent via the MR to a user is given by (9) to (11). Hence the total throughput associated with the coalition $\mathcal{F}_{2}$ is

$R\big{(}\mathcal{F}_{1}\big{)}$ and $R\big{(}\mathcal{F}_{2}\big{)}$ represents the sum profits contributed by the entire coalition $\mathcal{F}$ with the particular coalition partition of $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$. Hence, the user association model with resource sharing relations for our investigated mm-wave train-ground communication system is established in a coalition game with transferable utility. In this model, the data flows, as players, tend to form a coalition to associate either with the BS or with the MR, in order to maximize the total profit of the system.

In this section, We will propose a coalition formation algorithm based on the coalition formation game. One key point to coalition formation is what strategy to adopt by each flow. An efficient coalition formation algorithm should be able to compare the sum profits of the coalitions and to find a suitable coalition for each flow to join so as to achieve the optimization goal. Thus, we first introduce the concept of preference order to enable the comparison of the profits for different coalitions.

Therefore, the flows in our coalition game have the right to choose to join or leave a coalition according to their preference order, and they tends to join a coalition based on which it prefers to being a member. For any given flow $i\in\mathcal{N}$, $\mathcal{F}_{c}\succ_{i}\mathcal{F}_{\bar{c}}$ implies that flow $i$ is more willing to be a member of the coalition $\mathcal{F}_{c}$, that is, $i\in\mathcal{F}_{c}$, than with $\mathcal{F}_{\bar{c}}$, which does not include the case that flow $i$ prefers these two coalitions equally. In different applications, the preferences for flows can be quantified in different way. In this paper, we adopt the utilitarian preference order [46].

In other words, flow $i$ prefers to be a member of coalition $\mathcal{F}_{c}$ than $\mathcal{F}_{\bar{c}}$ under the condition of increasing the sum system throughput.

When flow $i\in\mathcal{N}$ performs a switching from $\mathcal{F}_{c}$ to $\mathcal{F}_{\bar{c}}$, the original partition $\mathcal{F}=\big{\{}\mathcal{F}_{c},\mathcal{F}_{\bar{c}}\big{\}}$ is changed to the new partition $\mathcal{F}^{\prime}=\big{\{}\mathcal{F}_{c}\setminus\{i\},\mathcal{F}_{\bar{c}}\bigcup\{i\}\big{\}}$. The switching can occur if and only if the preference order as defined in (27) is satisfied.

In our proposed algorithm based on the coalition game, we first initialize the system by a random coalition partition with two coalitions $\mathcal{F}_{c}$ and $\mathcal{F}_{\bar{c}}$. For any flow $i\in\mathcal{N}$, we denote its present coalition by $\mathcal{F}_{c}$. If $\mathcal{F}_{\bar{c}}\succ_{i}\mathcal{F}_{c}$, there will be a switching of flow $i$ from $\mathcal{F}_{c}$ to $\mathcal{F}_{\bar{c}}$, and the current coalition partition $\mathcal{F}=\big{\{}\mathcal{F}_{c},\mathcal{F}_{\bar{c}}\big{\}}$ will be updated to the new partition $\mathcal{F}^{\prime}=\big{\{}\mathcal{F}_{c}\setminus\{i\},\mathcal{F}_{\bar{c}}\bigcup\{i\}\big{\}}$. In this mechanism, every flow $i$ can leave its current coalition and join the other coalition, given that the new coalition is strictly preferred based on the definition in (27) and the flow can make a greater contribution to the system performance in terms of throughput in the new coalition. It’s worth noting that our proposed algorithm based on coalition formation game needs to find a coalition structure that maximizes the total utility rather than the individual payoffs of the players.

The pseudo code of the proposed coalition game based algorithm is given in Algorithm 1, which contains a user association algorithm for maximizing system throughput, and a transmission scheduling algorithm for maximizing the number of users meeting QoS requirements. More specifically, Algorithm 1 first initializes the parameters, and collects the set of flows that need to be scheduled in the current time slot, as well as the QoS requirements of each flow. Secondly, the proposed algorithm divides all flows into two coalitions randomly. Then, take a flow as the target, calculate $R\big{(}\mathcal{F}_{c}\big{)}$, $R\big{(}\mathcal{F}_{\bar{c}}\big{)}$, $R\big{(}\mathcal{F}_{c}\setminus\{i\}\big{)}$ and $R\big{(}\mathcal{F}_{\bar{c}}\bigcup\{i\}\big{)}$. If the system sum rate when the current flow stays in the current coalition is greater than that when it is moved to another coalition, the current flow will stay in the current coalition, as shown in lines 6 and 7 of Algorithm 1. The user association phase of the proposed algorithm is not completed until all flows have made the above judgments in turn. In the transmission scheduling phase, the proposed algorithm arranges each flow from small to large according to its QoS requirements, finds the maximum $N_{suc}$ flows with the required time slots less than $M$, and then transmits them.

Firstly, according to the QoS requirements, the amount of time slots required by each flow are obtained. Then the user association either with BS or with MR is determined according to the coalition formation algorithm. After the convergence of the algorithm, the flows are sorted according to their required numbers of time slots to meet their QoS requests from small to large. By prioritizing the flows with smaller time slots requirement during transmission scheduling, the number of the flows that satisfy their QoS requests is maximized.

The condition to terminate the algorithm is that the partition converges to the Nash-stable partition. If $\forall i\in\mathcal{N}$, $i\in\mathcal{F}_{c}\subset\mathcal{F}$, $\mathcal{F}_{c}\succ_{i}\mathcal{F}_{\bar{c}}\bigcup\{i\}$, where $\mathcal{F}_{\bar{c}}\bigcup\mathcal{F}_{c}=\mathcal{F}$ and $\mathcal{F}_{\bar{c}}\bigcap\mathcal{F}_{c}=\emptyset$, then the partition $\mathcal{F}=\{\mathcal{F}_{c},\mathcal{F}_{\bar{c}}\}$ is Nash-stable. Starting from any initial coalition structure $\mathcal{F}_{ini}$, the proposed coalition formation algorithm will always converge to a final partition $\mathcal{F}_{fin}$ that is Nash-stable, after a sequence of switching operations. We will give related theoretical proofs in Section V-C.

We then analyze the complexity of Algorithm 1. In a specific time slot, the established train-ground communication system can be regarded as temporarily static, i.e., the coalition of each flow is determined (not necessarily the optimal situation). The computational complexity of the sum rate of the coalition formed by the flows associated with BS is ${\rm O}({n_{B}})$, and that of the coalition formed by the flows associated with MR is ${\rm O}({n_{M}})$. At this time, considering the decision operation shown in the line 6 of Algorithm 1, the complexity corresponding to the user association phase is ${\rm O}(N\cdot({n_{B}}\cdot{n_{M}}+1))$. Then, the computational complexity of directly sorting the QoS requirements corresponding to data flows at one time is ${\rm O}({n_{ts}})$. Considering that the worst case of determining $N_{suc}$ requires $N$ times of judgment, the complexity in the data transmission phase is ${\rm O}({n_{ts}}+N)$. To sum up, the computational complexity of Algorithm 1 is ${\rm O}(N({n_{B}}+{n_{M}}+2)+{n_{ts}})$.

1) Convergence: We first examine the convergence of the proposed algorithm theoretically.

Theorem 1: With an arbitrary initial partition $\mathcal{F}_{ini}$, after the limited switching operations, a final partition $\mathcal{F}_{fin}$ obtained by the proposed algorithm can always be found, and the coalitions within $\mathcal{F}_{fin}$ maintain a disjoint relationship.

Proof: Users are divided into $U^{\prime}$ disjoint subsets in the coalition structure (CS), and each subset represents a coalition. We exhaustively examine all the CSs of $U^{\prime}$ users and obtain the set $S$ of all CSs, given by $S=\{{S_{1}},{S_{2}},...,{S_{\left|S\right|}}\}$. Based on the Bell number ${B_{k}}$, the cardinality of $S$ for the $U^{\prime}$ users can be expressed as

In Algorithm 1, the number of switch operations in each iteration is up to $N$, and each user either joins a new coalition or still stays in the original coalition. Thus, the whole number of partitions is $B(N)$, and since we preset the number of the BS and MRs, the number of partitions will be decreased based on the Bell number. As the number of partitions is bounded, we can conclude that after a certain number of switch operations, a final partition $\mathcal{F}_{fin}$ will be obtained.

2) Stability: We next examine the Nash-stable structure of the proposed algorithm theoretically.

Theorem 2: The final partition $\mathcal{F}_{fin}$ obtained by the Algorithm 1 is Nash-stable.

Proof: When the switching operation no longer occurs, the proposed algorithm based on the coalition game will terminate. At the same time, the optimal value of system throughput is obtained, and the final partition is Nash-stable. We have ${{\cal F}^{*}}=\arg{\max_{\cal F}}R({\cal F})$, for all ${{\cal F}_{c}}\subset{\cal F}$, and ${{\cal F}^{*}}=\{{{\cal F}_{0}}^{*},{{\cal F}_{1}}^{*},...,{{\cal F}_{n-1}}^{*},{{\cal F}_{n}}^{*}\}$ is the Nash-stable coalition partition.

If the partition still has tendency of switching, the final partition $\mathcal{F}_{fin}$ has not been found yet, which is contradictory to $\mathcal{F}_{fin}$ is the final partition. Consequently, the final partition $\mathcal{F}_{fin}$ of the proposed algorithm has reached Nash-stable.

Based on the system model described in Section III, the entire train-ground communication system works in the 60GHz mm-wave frequency band, and we consider a single cell scenario where users are randomly distributed in a $300\times 300$ square area. On the other hand, we use the widely used realistic directional antenna model in IEEE 802.15.3c [47] [48], and the antenna gain in units of dB, denoted by ${G\left(\theta\right)}$ , can be expressed as

where $\theta$ denotes an arbitrary angle within ${\left[0^{\circ},180^{\circ}\right]}$, $\theta_{-3dB}$ denotes the angle of the half-power beam width, and $\theta_{ml}$ is the main lobe width in units of degrees, and the relationship between $\theta_{ml}$ and $\theta_{-3dB}$ is ${\theta_{ml}=2.6\cdot\theta_{-3dB}}$. $G_{\rm sl}$ is the side lobe gain given by $G_{\rm sl}\!=\!-0.4111$ $\times\ln\left(\theta_{\rm-3dB}\right)-10.579$. $G_{0}$ is the maximum gain which can be obtained by

Other simulations parameters are given in Table I. In order to show the advantage of the proposed coalition game based scheme, we compare our scheme, which is labeled as Coalition Game $\left(CG-FD\right)$, with other three schemes:

Considering that HST mainly operates in rural areas and viaducts, and the buildings in the communication environments are generally low, so LOS transmission is dominant at this time. Mm-wave communications are directional, so we adopted the real directional antenna model in IEEE 802.15.3c [47] [48]. Secondly, we refer to the classical Shannon channel capacity for data rate. Thirdly, considering that the current algorithm can reduce the SI generated by FD to a low level, but there is still some residual SI in actual communication, a residual SI model such as $\beta\cdot P_{t}$ is built, and the results corresponding to different $\beta$ and $P_{t}$ on system capacity is analyzed in the following. Fourthly, considering the small coverage of the mm-wave BS, the radius of cell is set to 300m during simulation.

At present, train-ground wireless communication in HSR scenario mainly based on GSM-R, while mm-wave and FD are the key technologies of 5G. The details of their practical application in HSR scenarios are still unclear, so the construction of system models and the selection of simulation parameters mainly come from theoretical literatures and standards.

Firstly, we compare the performance of CG-FD with the optimal solution (OS) obtained by traditional exhaustive search method. The simulation results when the number of flows is 1 to 8 as shown in Fig.6 (a), and we can see that there is a good approximation between the sum rate of CG-FD shown by the solid line and that of OS shown by the dot line. This reminds us that under the same parameters, the user association algorithm based on coalition game proposed in this paper has the same optimal sum rate performance as the exhaustive search method, which is consistent with the theoretical analysis in Section IV.

In this section, we use simulation to determine the optimal way to allocate bandwidth. As shown in Fig. 6 (b), we obtain the sum rate with $a$, i.e., the ratio of bandwidth reserved by the BS to the total bandwidth resources, varying from 0.1 to 0.9. From the simulation results, we can easily get that the optimal bandwidth allocation is 0.4 for the BS and 0.6 for the MR. At this time, the sum rate of the system reaches the maximum when other parameters remain unchanged. Therefore, in the following simulation and analysis section, we assume that the ratio of bandwidth to BS is 0.4 and the counterpart of MR is 0.6.

When the number of flows waiting to be scheduled is 10, the sum rate obtained by the proposed coalition game based algorithm and other three comparison schemes when $\beta$ changes from $-$150 dB to $-$110 dB are shown in Fig. 7. When $\beta=-150$ dB, the sum rate of CG-FD is larger than that of FBSC, FMRC and CG-HD about 11%, 351% and 6%. As $\beta$ increases, the data rate of the flows transmitted from the MR decreases due to the increase of the SI, which can explain the trend of curves obtained by the CG-FD and the FMRC. Because there is no SI in the link without MR forwarding, the sum rate obtained by the FBSC scheme is stable. Unsurprisingly, as RSI gradually increases, more users intend to associate with the BS, so the curve corresponding to FMRC shows a trend of downward, which is obviously different from the other three curves. When $\beta$ is about -120dB, the sum rate obtained by CG-FD is lower than that obtained by CG-HD, which indicates when the SI cancellation level is above -120dB, the performance improvement brought by FD cannot offset the adverse effects of SI on the system.

As shown in Fig. 8, we compare system sum rate of the four schemes with different distance between BS and MR. In the investigated mm-wave train-ground communication system, the longitudinal distance between the BS and MR is fixed, so we take the lateral displacement of the MR as the independent variable to simulate the operation of the train. Based on the simulation results, it can be seen that CG-FD has the best performance. When the lateral displacement of the MR is 150m, the sum rate of CG-FD is larger than that of FBSC, FMRC and CG-HD about 26%, 40% and 8%, respectively. In general, when the distance between the BS and MR is too large, the sum rate of the MR is greatly limited, resulting in FMRC being the scheme with the lowest performance. On the whole, when the distance between BS and MR is about 150m, the sum rate have a maximum value. This is related to our planned radius of 300m. When other parameters are fixed and the distance between BS and MR is about 150m, the average distance between the user and the associated device is the shortest and the path loss is the smallest.

The variation of system sum rate under different transmission power is shown in Fig. 9. When $P_{t}=30$dBm, the sum rate of CG-FD is larger than that of FBSC, FMRC and CG-HD about 11%, 351% and 6%. As $P_{t}$ increases, the SI of MR also increases, so the curve of FMRC scheme has a flat trend. Since there is no SI in the flows associated with the BS, increasing $P_{t}$ is not bad for them and certainly has a greater effect on the growth of the FBSC. When the $P_{t}$ is low, the proposed CG-FD scheme is closer to the FMRC, and shows great advantages when $P_{t}$ is high.

As shown in Fig. 10, we compare system sum rate of the four schemes under different number of flows from 20 to 55. It can be seen that the performance of CG-FD proposed in this paper is best. When the number of the flows is 55, the sum rate of CG-FD is larger than that of FBSC, FMRC and CG-HD about 18%, 254% and 13%. From overall view, the sum rate of these four schemes improve as the number of flows increases.

In this simulation, we evaluate the system performance of our proposed transmission scheduling scheme. At first, we randomly set the throughput requirements of each flow and the upper limit of the required number of time slots. The simulation results of system performance under different number of CTAs are shown in Fig. 11.

When the total number of flows is 50, the system throughput under different upper limit of number of time slots are shown in Fig. 11 (a). We can see that the proposed transmission scheduling scheme produces higher throughput and better performance. After sorting the number of slots required by all the flows, the proposed scheme were able to achieve much higher throughput than the one without sorting with limited slots, thus improving the performance of the system.

The variation of number of users whose throughput requirements are met under different restrictions of time slots are shown in Fig. 11 (b). We can see that the performance of the proposed transmission scheduling scheme is better. By sorting the number of slots required by all flows, we are able to meet the needs of more users with a limited number of time slots.

To examine the convergence performance of the proposed coalition game based algorithm, the number of switch operations under different number of flows are shown in Fig. 12 where the proposed CG scheme converges to the final partition. As we can see, as the number of flows increases, so does the number of switching operations, and the average number of switching operations is 0 to 25. Given $N$ flows, the exhaustive operation requires $2^{N}$ iterations to find the optimal solution. Therefore, the proposed coalition game based algorithm allows users to establish the final Nash-stable partition with a very fast convergence rate, which greatly reduces the computational complexity.

The above results show that the proposed algorithm can effectively improve the system throughput while maintaining a certain QoS awareness, but there are still some challenges in applying them in real-life environments.

Firstly, the established train-ground communication system works in the mm-wave band, which requires the antenna array to be arranged at MR and BS simultaneously. Considering the inherent high path loss of mm-wave communications, we also need to optimize the beamforming at the transmitter and receiver to maximize the directional gain of the antenna. At present, the method based on deep reinforcement learning has been proposed, which has great potential to solve this problem.

Secondly, considering that the operation of HST is based on a fixed timetable and its trajectory is predictable, the track-side train-ground wireless communication system also has a regular pattern, and artificial intelligence is good at capturing this hidden pattern, which has great potential to optimize the beamforming in the HSR scenarios [51] [52]. In addition, as the HST mainly runs in rural areas and viaducts, the buildings in the communication environments are generally low. At this time, LOS transmission is dominant, but there is still the possibility that the service may be interrupted due to blocking. At present, scholars have proposed to deploy IRS on HST windows or track-side [53].

Thirdly, in the actual scenarios, BS should timely count the QoS requirements of users, and send the results of user association and transmission scheduling to users through the control channel. However, because the speed of HST is fast and not constant, there is usually additional queuing and transmission delay, so a more detailed model needs to be established to further evaluate the control channel bandwidth that needs to be reserved when the HST speed is different, and the implementation complexity of the algorithm can also be reduced by referring to historical user association and transmission scheduling data.