Resource Allocation Strategy Based on Matching Game

(National Key Laboratory of Science and Technology on Communications,University of Electronic Science and Technology of China,Chengdu 611731,China)

Abstract: With the development of satellite communication technology,the traditional resource allocation strategies are difficult to meet the requirements of resource utilization efficiency.In order to solve the optimization problem of resource allocation for multi-layer satellite networks in multi-user scenarios,we propose a new resource allocation scheme based on the many-to-many matching game.This scheme is different from the traditional resource allocation strategies that just consider a trade-off between the new call blocking probability and the handover call failure probability.Based on different preference lists among different layers of medium earth orbit (MEO) satellites,low earth orbit (LEO) satellites,base stations and users,we propose the corresponding algorithms from the perspective of quality of experience (QoE).The simulation results show that the many-to-many matching game scheme can effectively improve both the resource utilization efficiency and QoE,compared with the oneto-one and many-to-one matching algorithms.

Keywords:satellite network; resource allocation; many-to-many matching game; preference lists;quality of experience

1 Introduction

The rapid development of satellite communication technology has facilitated the provision of multimedia services with high speed,low latency and large capacity.In satellite communication systems,the radio resource management focuses on improving the resource utilization and satisfying the quality of experience (QoE) for different users.In addition to the traditional channel allocation strategies for satellite beams,the existing algorithms for radio resource management in satellite communication systems include the convex optimization algorithm[1],greedy algorithm[2]and matching game algorithm[3],among which the algorithm based on game theory is widely used.

The matching game is one of the game theories,whose founder,Alvin E.Roth[4],won the Nobel Prize in 2012 for his contribution.The original purpose of matching game is to deal with unstable market economy and maximize economic benefits.It usually involves the matching relationship of two sets,such as students and schools,female and male marriages,and employees and companies,which are related to preference lists.There are one-to-one[5],many-to-one[6]and many-tomany[7]matching relations.Nowadays,the matching game has widely been used in the field of wireless communications to solve the optimization problem of wireless resource allocation.

In response to the joint up/down link subcarrier allocation problem,ELHAJJ et al.[8]proposed a new resource allocation algorithm named Bilateral Stable Matching Strategy.Compared with the traditional resource allocation algorithms,this strategy significantly improves the performance of subcarrier allocation in terms of the average utility value of each user.At the same time,the simulation results also show that the proposed method has fairness in improving the subcarrier resource allocation[8].ZHOU et al.[9]adopted an iterative method to jointly allocate spectrum and power,combined with a manyto-one matching game algorithm,and the simulation results verified effectiveness and superior of the algorithm in solving resource allocation problems for D2D communications.In order to improve system throughput,ZHAO et al.[10]proposed a many-to-many matching game to solve the problem of D2D resource allocation.The algorithm can be converged to bilateral exchange stable matching within a limited number of iterations and it is proved that the performance of this algorithm is significantly better than the one-to-one matching algorithm[10].In addition,YAO et al.[11]fully considered user fairness on how to achieve effective matching between users and network resources and used two-layer many-to-many and two-layer many-to-one matching games to solve the problem,which verifies that the algorithm has good convergence,effectiveness and feasibility.SHI et al.[12]proposed a two-layer many-to-one matching game algorithm.The research results show that the algorithm can stabilize resource matching,effectively solve the resource allocation problem in the storage system,and effectively reduce the system delay.Then,in order to further optimize the resource allocation problem,a two-layer many-tomany resource allocation scheme was proposed,which shows that the algorithm can further reduce the system delay and improve social satisfaction[12].

The main contribution of this paper is to study resource allocation based on the matching game algorithm.In the case of limited satellite resources and large number of users,how to achieve reasonable scheduling and allocation of resources is a problem that we have to solve.The existing resource allocation technology is difficult to meet system requirements in terms of resource utilization improvement,because this technology is nothing more than a trade-off between the blocking rate of new calls and the failure rate of handover calls and the service quality of the satellite system has reached to the extreme.In addition,it can be seen from the research status at home and abroad that most matching game algorithms in the communication field mainly solve the problem of ground network resource allocation and have not set foot in the satellite communication field.Therefore,we have established a model of medium earth orbit (MEO) satellites,low earth orbit (LEO)satellites,base stations and users in a multi-user scenario,which is used to effectively solve the multi-layer wireless resource allocation problem.Existing representative works,such as the fixed channel reservation scheme and the dynamic channel reservation scheme,mainly use the new call blocking rate,handover call failure rate and system service quality(QoS) for comparison.The proposed work is mainly to simulate the matching game algorithm for the QoE.The simulation results show that the multi-layer many-to-many matching game can effectively improve the resource utilization rate and the overall utility of the system.

2 System Model of Matching Game

The matching game involves several important concepts and performance parameters.

(1) Utility function.In order to measure the satisfaction of all participants in the matching game process,it is necessary to set an appropriate utility functionU,which directly reflects the resource utilization rate and participant satisfaction degree through the specific utility function value.

(2) Preference list.The ultimate goal of matching game is to achieve the best matching state of resources.The preference list is made for each participant in the current set by referring to each factor of all participants in the relative set,and the preference list of each participant is different.

(3) Matching stability.Although the utility of participants is improved in the process of matching,there will always be unmatched objects due to the difference of preference list.However,no single or a pair of participants are allowed to participate during the matching or destroy the stability of the matching game.Therefore,when the utility value is constant for a specified number of consecutive times,the match will eventually tend to be stable.

(4) Matching validity.A group of participants are supposed to be allocated resources.From one allocation state to another,at least one participant becomes better without changing any participants,which means that there must be an increase in the total utility value during the matching process.

(5) Matching uniqueness.Because the preference list of each participant is different and independent,there is only one matching mapping when the matching reaches a stable state,which can be verified by induction.

(6) Matching convergence.All participants send matching connection requests to the most preferred object according to their own preference list.After a few exchange matches within a limited number of iterations,all participants can complete the matching and reach a stable state.The values will inevitably converge to a certain fixed value.

In the multi-layer network scenario,we assume that the number of MEO satellites isR,which is denoted byM={M1,M2,...,Mr}.The number of LEO satellites isS,which is denoted byL={L1,L2,...,Ls}.The number of base stations isT,which is denoted byB={B1,B2,...,Bt},and the average number of users isIper base station.The system model is shown in Fig.1.

The matching process is divided into three stages.The first stage is the establishment of an inter-satellite link between the MEO satellite layer and the LEO satellite layer.This LEO/MEO double-layer satellite network can not only take advantage of short delay and low propagation loss,but also simplify the structure of LEO satellites and reduce their construction costs.The second stage is the establishment of a satellite-toground link between satellites and ground base stations.Here we suppose that all users are connected to base stations and then the base stations are connected to LEO/MEO satellites.The satellite and the ground network are connected by satellite-ground optical links.In this process,we can take advantages of wide satellite coverage and large capacity for the terrestrial communication network.Their mutual complementation can enhance the viability of the whole network.The third stage is the matching between base stations and users.Because the coverage areas of base stations have overlapping parts and the distribution of users is uneven,we regard all base stations as a large resource pool to simplify the layer matching model; all users can use their resource blocks,which simplifies the allocation model to a certain extent.The result of the matching game affects the result of matching decision.The matching framework is shown in Fig.2.

In this system model,three problems need to be solved.The first one is the establishment of inter-satellite links between different orbits,the second one is the establishment of links between satellites and ground base stations,and the third one is the resource matching between base stations and users.

The main impact factor of the inter-satellite links is the loss of free space propagation,which can be expressed as:

wheredis the inter-satellite distance,fis the carrier frequency of transmitter,andLMLdenotes the free space propagation loss between MEO and LEO satellites.In addition to the free space propagation loss,the satellite-to-ground link propagation loss includes an additional loss.Therefore,the total loss of satellite-to-ground links can be formulated as:

whereLfis the additional loss.Besides,the links between base stations and users are modeled as Rayleigh fading where the channel impulse response follows the independent complex Gaussian distribution.Therefore,the channel gain can be expressed as:

whereβis the channel parameter,dis the distance between the user and base station,ηis the path fading exponent,andhdenotes the complex Gaussian channel parameter that followsh∼CN(0,1)[11].

In the many-to-many matching model,each MEO satellite can establish links with multiple LEO satellites.At the same time,each LEO satellite can establish links with multiple MEO satellites.We assume that the total transmit power of each MEO satellite isQ,and the average power allocated to the LEO satellite is denoted bypr,which is expressed as:

On the other hand,the average power allocated to the LEO satellite is denoted bypsr,which is expressed as:

We assume thatMris ther-th MEO satellite,Lsis thes-th LEO satellite.IfMrsuccessfully establishes a link withLs,xrs=1; otherwise,xrs=0.Then the signal-to-noise ratio(SNR) of the received signal from the MEO satellite to the LEO satellite is as follows.

whereGrsis the gain fromMrtoLs.In order to facilitate the calculation,we assume thatGrs=Gsr,whereGsris the antenna gain fromLstoMr.Therefore,we can get a similar formula of the SNR of the received signal from the LEO satellite to the MEO satellite:

▲Figure 1.Model of network based on matching game.

▲Figure 2.The matching framework.

whereN0is the noise power of the receiver.Based on the Shannon Theory,we can get the data rates ofMrandLsas:

whereBMLis the transmission bandwidth between MEO satellites and LEO satellites.In the matching game,we usually use the sum of data rates to reflect the overall satisfaction degree of participants.We describeUtotal1as the overall utility of the link between the MEO and LEO satellites,which can be denoted as:

In addition,there are some restrictions on the above formulas,which can be expressed as:

Eqs.(11) and (12) show each LEO satellite can connect with up topmaxMEO satellites and each MEO satellite can connect with up toqmaxLEO satellites respectively,whereRis the maximum number of MEO satellites andSis the maximum number of LEO satellites.Eq.(13) indicates that the value ofxrscan only be 0 or 1.Eqs.(14) and (15) show that SNRs of the received signal cannot be lower than the minimum SNRsandγsmin.

The second layer is the establishment of the link between satellites and base stations.Similar to the first layer,we can build a many-to-many matching game mathematical model and finally get the overall utility valueUtotal2,which can be denoted as:

In addition,we can get some restrictions similar to the first layer,as we have mentioned before.

The third layer is the establishment of the link between base stations and users.Since the coverage area of each base station and the distribution of users in the cell are different,it is very complicated to model it as a whole.Therefore,we simplify the problem to a single base station covering multiple users.Based on this problem,we construct multiple simplified models and integrate them to obtain the final result without considering user switching among the base stations.Assuming that there areJ(J＜Q) users in a cell covered by a base stationBt,MT={MT1,MT2,...,MTJ} represents the set ofJusers.Similar to the first layer,we finally get the overall utility valueUtotal3,which can be denoted as:

In addition,we get some restrictions similar to the first layer,as we have mentioned before.Therefore,the maximum utility of this three-layer matching model can be finally expressed as:

3 Algorithms of Matching Game

The matching game usually involves the matching relationship between two sets.MEO satellites,LEO satellites,base stations and users are regarded as four different participants in the match game,and they are independent of one another.

In the first-layer matching game,MEO and LEO satellites are considered as two parties.The data transmission requires the establishment of an inter-satellite link between them.Not only can each MEO satellite establish inter-satellite links with multiple LEO satellites for data transmission,but also each LEO satellite can establish multiple links to connect with MEO satellites.Therefore,the matching model can be regarded as many-to-many matching.In the matching game model,we use ≻to indicate the degree of preference of participants to another group of participants.The preference list is comprehensively based on the distance between participants,the speed of movement and the transmission environment.IfL1≻L2,theMrprefers to establish a link with theL1.

μ1is the mapping fromM∪Lto 2M∪L.For ∀Mr∈MandLs∈L,we can come up with the following conclusions:

Conclusions (1) and (2) indicate that MEO and LEO satellites can establish many-to-many links andμ1(Mr)=Mrshows thatMrhas no link connection.Conclusion (3) implies that,ifMrmatches withLs,Lsmatches withMr.The secondlayer matching game is similar to the first layer,which can also be seen as a many-to-many matching.

In the third-layer matching game,in order to further simplify the calculation,the total channel resources in all base stationsB={B1,B2,...,Bt}are regarded as a resource pool,which can be expressed withRB={RB1,RB2,...,RBI}.Each mobile terminal can use one or more resource blocks,but one resource block can only be used by one mobile terminal at the same time.Therefore,the matching model can be regarded as many-to-one matching.μ3is the mapping fromRB∪MTto 2RB∪MT,MT={MT1,MT2,...,MTJ}.For ∀RBi∈RBandMTj∈MT,we can come up with the following conclusions:

Conclusions (1) and (2) explain the nature of many-to-one matching with mathematical formulas.Conclusion (3) implies the bidirectional matching betweenRBiandMTj.

Based on the above analysis,we establish a corresponding many-to-many matching game algorithm between the MEO and LEO satellites,as shown in Algorithm 1.First of all,according to the preferences,we assume a list of preferences forMrisβs,whose quota isQL.Similarly,the preference list ofLsisβr,whose quota isQM.ThenMrsends a request to the LEO satellite according to its preference list and letxrs=1.After that,Lschooses its favoriteMrto accept or reject other requests.IfLshas extra connection space at this time,which means that∑s=1xrs＜QL,it will remain in Θ1.Otherwise it will be deleted from Θ1.At last,we calculate the current utilityUtotal1.

Algorithm 1.The many-to-many matching algorithm at the first layer

The second-layer matching game is similar to the first-layer matching game,so we then focus on the third-layer matching game.In the process of resource matching at the third layer,the definition of preference list is different from the first two layers.Each resource block establishes its own preference list according to the priority of various users,while the users sort each resource block according to the required type and SNR,as shown in Algorithm 2.

Algorithm 2.The many-to-one matching algorithm at the third layer

At the beginning,the preference lists of resource blocksRBandMTare initialized asβiandβj,where the quota ofMTjisQJ.ThenMTjsends a request to its favoriteRBi,removes it from the preference listβj,and letxij=1.After that,eachRBiassigns it to the specifiedMTjaccording to the preference listβiand rejects other requests.At last,we calculate the current utilityUtotal3.

Because the basic algorithms of the second and third layers are similar to that of the first layer,we can easily calculate their utilityUtotal2andUtotal3through the corresponding algorithm respectively.

Finally,we can obtain the total utility according to Eq.(18).

4 Simulation Results

In this paper,we use Matlab for simulation analysis and comparison.In order to verify the effectiveness of the threelayer many-to-many matching game algorithm,we also adopt some of the parameters of the satellite and terrestrial communication system[11-17].At the first layer,we assume thatdML=10 355 km,fML=30 GHz,andBML=100 MHz.The maximum inter-satellite transmission power is 27 W,the inter-satellite total gain of the receiving and transmitting antenna is 68 dB,and the quota of MEO satellites is 2.At the second layer,we assume thatdLG=1414 km,fLG=14.5 GHz,BLG=32 MHz,andLrest=2 dB.The maximum transmission power of LEO satellite is 30.72 dBW,the receiving and transmitting antenna gain for satellite-to-ground link is 19.5 dB,and the quota of LEO satellites is 2.At the third layer,we assume thatBBM=10 MHz,the maximum transmission power of BS is 23 W,the quota of base stations is 2,the cell radiusr=500 m,α=4,β=0.02,and the noise power of user receiver is -134 dBm.The quota of users is 2,the maximum number of iterations is 30 and the receiving and transmitting antenna total gain from ground is 17.5 dB.

Fig.3 shows the total utility varying with the number of MEO satellites whenS=6,T=10,andI=20.Fig.4 shows the total utility varying with the number of LEO satellites whenR=3,T=10,andI=20.Fig.5 shows the total utility varying with the number of base stations whenR=3,S=6,andI=20.

It can be seen from Figs.3 to 5 that the overall utility of the system is improved with the increasing number of MEO satellites,LEO satellites or base stations.Because the participants will get more diversity gains and have more opportunities to get resource allocation as the number of MEO satellites,LEO satellites or base stations increases,the total throughput of the system improves.Moreover,as the number of iterations increases,three curves increase continuously,which means that the utility value of individual will increase after participating in the exchange.At the same time,after the three curves increase with the number of iterations increasing for a period of time,the total utility value becomes stable,which means that the system utility value will be stable when there is no blocking pair.The three figures well prove the effectiveness and stability of the matching game.

According to the figures,the average number of iterations required for stable matching can be accurately obtained.In addition,as the number of participants increases,the preference lists become more complex,which will bring more connection opportunities for each participant as well as increase average iterations required.

▲Figure 3.Sum of data rates varying with different MEONum.

▲Figure 4.Sum of data rates varying with different LEONum.

▲Figure 5.Sum of data rates varying with different BSNum.

Fig.6 shows the total data rates of three matching game algorithms varying with different LEO satellites whenR=4,T=10 andI=20.Fig.7 shows the total data rates of three matching game algorithms varying with different base stations whenR=3,T=4 andI=20.It can be seen from these two figures that as the number of LEO satellites and that of base stations increase,the data rates of the three algorithms are positively correlated,which proves the validity of the matching game.Besides,we can also see that the total data rate of the three-layer many-to-many matching game is always higher than those of the others,which shows that the many-to-many matching game may improve the resource utilization of the communication system.

Fig.8 shows the total data rates of the three matching game algorithms varying with the average number of users per base station whenR=3,S=4 andT=10.We can see that the total data rate of three algorithms is gradually decreasing with the number of users increasing.This is because when the number of users increases gradually,the spectrum resources obtained by each user are decreasing.And when the number of users grows to a certain extent,the total data rate will gradually stabilize because of the resources fixed and the number of users matched limited.Besides,it can also be seen from Fig.8 that the decline rate of the many-to-many matching game is the slowest,and the sum of data rates is always higher than the other two strategies,which also proves the superiority of the many-to-many matching game strategy.

5 Conclusions

In this paper,in order to effectively solve the problem of radio resource allocation based on data services,we propose a new resource allocation strategy based on the matching game.The matching game includes many-to-many matching between MEO satellites and LEO satellites,many-to-many matching game between LEO satellites and base stations,and many-toone matching game between base stations and users.Based on the proposed multi-layer many-to-many matching game model among MEO satellites,LEO satellites,base stations and users,the corresponding matching game algorithms are designed from the perspective of utility function QoE and we use total data rates to reflect the performance.The simulation results show the effectiveness and stability of the proposed matching game compared with the many-to-one matching and one-toone matching games,and the results also show that the manyto-many matching game makes communication systems more efficient with higher resource utilization.

However,the matching game algorithm proposed in this paper has limitations,without considering the impact of the movement of the MEO and LEO satellites relative to the ground on resource allocation.Therefore,the future research will focus on matching games in the environment with dynamic changes.Moreover,radio resource allocation is not only based on matching game technology,but also can be combined with cooperative game or non-cooperative game to improve the effective utilization of resources.

▲Figure 6.Sum of data rate versus different number of LEO satellites among the three algorithms.

▲Figure 7.Sum of data versus different number of base stations among the three algorithms.

▲Figure 8.Sum of data rates versus different user numbers with the three matching algorithms.