A genetic algorithm based hybrid non-orthogonal multiple access protocol①

YAN Zhenzhen (闫珍珍)， LI Bo， YANG Mao， YAN Zhongjiang

(School of Electronics and Information， Northwestern Polytechnical University， Xi’an 710072， P.R.China)

Abstract

Key words: non-orthogonal multiple access (NOMA)， resource allocation， sparse code multiple access (SCMA)， genetic algorithm， hybrid non-orthogonal multiple access

0 Introduction

In recent years， broadband networks are ubiquitous in daily life. With the demands for broadband networks exploding， the existing broadband networks are increasingly unable to meet needs on both enormous connections and ultra-large network capacity[1]. In this situation， the next generation broadband networks need to support both two demands.

Traditional orthogonal multiple access methods can hardly meet needs of massive connectivity and ultra-huge network capacity. Non-orthogonal multiple access (NOMA) technology[2]has been introduced.Here， different user equipment (UE) can multiplex on the same resource. By multiplexing in different dimensions， many NOMA methods have been proposed.Among those methods， sparse code multiple access(SCMA)[3]scheme is a typical representative of NOMA technique and a very competitive multiple access method in the next generation broadband networks.

In traditional multiple access methods， base stations (BSs) serve as scheduling centers. It is inevitably accompanied by more delays and very higher signaling overheads. As an effective solution， SCMA scheme supports both scheduled access and random access， which are called granted access and grant-free access respectively. Among them， granted access applies to UEs with more stable business requirements or large amount of information， and are scheduled by their BSs. Grant-free access is suitable for UEs with small data packets and small business needs， and grant-free UEs compete for access[4]. In addition， the resources assigned to both granted UEs and grant-free UEs are strictly segregated in the current studies. It leads to a decrease in resource utilization to some extent.

As one of the most advantageous key techniques，SCMA scheme has aroused interest from numerous experts and scholars all over the world. They have done many researches and proposed many resource allocation methods[5-9]. Part of those uses random algorithm while part of them just optimizes resources allocated to granted UEs. Fewer studies optimize resources allocated to all UEs or grant-free UEs. And resources assigned to granted UEs and grant-free UEs are strictly separated in the majority. It leads to a serious waste of resources and limits connectivity and network capacity to some degree，as the number of granted UEs and grant-free UEs are time-varying. A new solution needs to be proposed.

To solve those challenges， satisfy increasing massive connectivity and network capacity requirements，and implement the idea of integrating resources， an idea of hybrid non-orthogonal multiple access protocol is proposed. It allows granted UEs and grant-free UEs to share the same resource unit. The central idea is that resources are first allocated to granted UEs and the remaining are allocated to grant-free UEs. But utilization of resources is not well guaranteed because allocation is randomly. On this basis， a genetic algorithm is put forward to optimize resource allocation by mapping resources allocation issue to an optimization problem.By comparing performance of four algorithms， masses of simulation results manifest that genetic algorithm has better throughput gains.

The main contribution can be summarized as follows.

(1) The proposed hybrid non-orthogonal multiple access protocol dynamically allocates resources to granted UEs and grant-free UEs. It breaks down the strict separation of resources. Resources are allocated to granted UEs first， and the remaining are allocated to grant-free UEs.

(2) Genetic algorithm is proposed for resource allocation. And this paper has made systematic modeling and theoretical analysis. The result confirms that genetic algorithm satisfies the demand of both massive connectivity and ultra-huge network capacity.

(3) Simulation results demonstrate throughputs of genetic algorithm are obviously increased compared with other algorithms. It further satisfies the demands of tremendous connectivity and ever-increasing network capacity.

The rest is organized as follows. Section 1 shows the related work. The system model is introduced in Section 2. Resource allocation issue is mapped to an optimization problem in Section 3. Then the main idea of genetic algorithm is introduced in Section 4. Next，simulation and comparison verification are carried out in Section 5. Section 6 is a summary of this article.

1 Related work

As a typical representative of NOMA technique and a very competitive multiple access method in the next generation broadband networks， SCMA protocol attracts keen interests of many experts and scholars worldwide.

Ref. [5] designed a resource allocation method based on downlink of SCMA. Proportional fair method and modifying largest weighted delay first method apply to it. In uplink of SCMA， Ref.[6] presented an optimal resource allocation algorithm to maximize the sum rate. By settling a convex optimization matter， the total throughput has been effectively increased. Ref.[7]put forward a frequency-hopping based sparse code multiple access. By introducing SCMA technique into time domain， Ref.[8] presented a time domain SCMA method and applied it to narrow band networks， which can dramatically increase throughput performance gain.Ref.[9] described a semi-granted multiple access(SGMA) technique on which granted UEs and grantfree UEs can share the same resource unit.

However， some studies use random algorithm on resource allocation， some researches are optimized resource allocation of granted UEs and there are very few optimization studies on resource allocation of grant-free UEs or all UEs. It is even worse that almost all resources assigned to granted UEs and grant-free UEs are strictly separated. The fact that the number of granted UEs and grant-free UEs is time-varying leads to a waste of resources. In order to improve resource utilization，it is necessory to put forward new ideas for whole UEs and mix their resources together.

2 System model

2.1 Network resources scenario

In network resources topology， each BS can be seen as the centre of a broadband network community and UEs are randomly distributed around the BS in Fig.1. All UEs are divided into two categories: granted UEs and grant-free UEs. For granted UEs， its BS acts as the scheduling centre. They are represented asU={u1，u2， …，uNg} andNgis the number of them.For grant-free UEs， there is no scheduling centre and all of them access resources randomly. They are expressed asV= {v1，v2， …，vNgf} whereNgfis the number of them.

The frequency domain can be divided intoJsubchannels. EveryKadjacent sub-channel forms a channel resource unit. The number of channel units can be got from Eq.(1).

For downlink， all information transmissions are scheduled by their BSs. For uplink， UEs not only can be scheduled by their BSs， but also can randomly access resources[10-11]. So this paper mainly considers information transmission in uplink.

Fig.1 Network resources scenario

2.2 Principle of SCMA

In SCMA， UEs generateLpossible access schemes by using a codebook set and achieve multiplexing onJsub-channels. The codebook set is represented byCodebook= {codebook1，codebook2， …，codebookL}.AndcodebookicontainsJrows andBcolumns.Bshows a bitstream of all UEs information.Lis the number of virtual layers.

On the sender， all UE information is directly mapped to multidimensional codewords on complex domain by SCMA encoder in the form of bitstreams.Codewords of different UEs are non-orthogonal superimposed in sub-channels through sparse code spread spectrum[12-15]. In order to reduce decoding complexity of receiver， non-zero elements of each codeword are less than half of the total number of elements in a codeword.

Based on the sparsity，overloading and other characteristics of SCMA technique， receiver can complete decoding and restore the original information bitstreams using low complexity multi-user joint detection algorithm.

2.3 Hybrid non-orthogonal multiple access

Although SCMA protocol is able to increase connectivity and system network capacity to some extent，resources assigned to granted UEs and grant-free UEs are strictly divided. It causes a waste of resources. On this basis， this paper needs to seek a new approach to break the resource allocation barriers.

A hybrid non-orthogonal multiple access protocol is proposed that allows granted UEs and grant-free UEs to share the same channel unit in a fine-grained fusion manner. Virtual layers can be assigned to both granted UEs and grant-free UEs. This method not only does not suppress the connection of granted UEs， but also breaks previously strict isolation between granted UEs and grant-free UEs. That is to say， resources are first allocated to granted UEs and then the remaining are available for grant-free UEs. Since throughputs of granted UEs are more stable than that of grant-free UEs，the total throughputs of all UEs will increase partly.

Fig.2 is a comparative analysis diagram between SCMA and hybrid non-orthogonal multiple access protocol. The left side shows the proposed protocol and the right side shows traditional NOMA method as half of its sub-channels are allocated to granted UEs and the remaining are allocated to grant-free UEs. But in hybrid non-orthogonal multiple access protocol， resources are firstly allocated to granted UEs and then the remaining are allocated to grant-free UEs. It can improve the connection of granted UEs and grant-free UEs and further meet time-varying network needs， shorten waiting delay of granted UEs and improve network throughput.

Fig.2 Comparison between SGMA and SCMA

3 Problem formulation

For wireless networks， capacity or throughput is one of the most important objectives. It reflects the resource utilization degree to certain extent. In this paper， the optimizing objective is to maximize the capacity of whole system.

For the broadband network community which adopts hybrid non-orthogonal multiple access scheme based on genetic algorithm， it can be known that: (1)business demands of all UEs;(2) the SNR information that each UE at different sub-channels; (3) resources allocated to each granted UE. On this basis，the objective optimization function of resource allocation problem can be obtained according to Shannon theorem.

Objective:

Eqs(3) -(6) specify each UE can occupy one virtual layer at most and each virtual layer can be assigned to one UE at most. Eq.(7) and Eq.(8) indicate that UEs assigned to certain channels are allocated and unallocated.

Based on it，this is a non-deterministic polynomial(NP) problem and an optimal polynomial time solution cannot be found. Under this premise， genetic algorithm will be introduced to optimize resource allocation.

4 The genetic algorithm

For a network community using hybrid non-orthogonal multiple access protocol， the genetic algorithm is introduced to optimize resource allocation. The genetic algorithm mainly includes initialization， integer encoding， calculation of fitness function， selection， crossover and mutation operation as shown below. Repeat those steps until reaching the maximum number of iterations or termination criteria.

4.1 Initialization

Set the termination criteria and the maximum number of iterations. Generate the initial population randomly. The population size is determined by the number of chromosomes and the number of genes in each chromosome. Among them， the positions of genes on each chromosome represent virtual layers. Assume the probability of crossover and mutation respectively.

4.2 Integer encoding

Each chromosome can be defined as

where，ximeans the UE on theith position of genes on each chromosome. Whenxi=0， theith position is allocated to grant-free UE. And whenxi=u(u≠0)， theith position is assigned to granted UEu. Lrepresents the total number of genes on each chromosome or says the total number of virtual layers.

4.3 Calculate fitness

Shannon formula is used to describe the information transmission rate and the sum of Shannon capacity of all UEs on each chromosome is taken as the fitness function of each chromosome as shown in Eq.(11).

4.3.2 Fitness of grant-free UEs

For grant-free UEs， Shannon capacity is obtained based on the estimated number of successful accessed UEs. Shannon capacity of all grant-free UEs on each chromosome can be obtained as

4.4 Selecting operation

Following a principle of ‘survival of the fittest’，a selection operator is applied to population. It means the chromosome who has least value of fitness function is replaced by the one who has maximal value. Meanwhile the optimal retention strategy is adopted. After selection operation is finished， the chromosome with largest value of fitness function is directly reserved and enters the next iteration. It ensures the optimal chromosome who has maximal value of fitness function can emerge in next round.

4.5 Crossover operation

The operation adopts an improved single point intersection method. Its steps are shown below. First，two chromosomes are selected randomly from population for pairing. If the number of chromosomes is odd，the one with largest value of fitness function will not participate in pairing. The paired chromosomes perform crossover operation according to an improved single point intersection principle by the probability ofpcand remain the original by the probability of (1 -pc). Two chromosomes are selected randomly from the remaining and execute the previous steps until all chromosomes are paired.

An example is shown in Fig.3. Assuming the selected two chromosomes are represented asc1=(0，1，2，3，4，5) andc2=(4，2，1，5，0，3) respectively. And two new chromosomes are expressed asc3andc4. Location of intersection point selects the third gene randomly. According to the probability ofpc， choose all genes on the left side of crossover point onc1as the left side ofc3in turn. Next find genes from the left side ofc2which have not yet appeared inc3and put them sequentially after the existing genes onc3until all genes have been found out. So farc3=(0，1，4，2，5，3) can be got. Lastlyc4=(4，2，0，1，3，5) can also be got by the same way.

Fig.3 An example of crossover operation

4.6 Mutation operation

A mutation operator is applied to the population.First， a mutation operator is generated randomly by selecting two different positions of genes on each chromosome. Then， the two genes are swapping with the probability ofpmand keeping the original genes by the probability of (1 -pm).

5 Performance evaluation

5.1 Simulation configuration

In simulations consider a single-cell network in which UEs are uniformly distributed. Default simulation parameters are summarized in Table 1. Besides，SNR values of different UEs on different sub-channels are different. The SNR values follow a uniform distribution from 2 to 20.

Table 1 Simulation parameters

5.2 Performance comparison

Simulations are used to evaluate performances of the proposed algorithm and study how the number of granted UEs and the ratio of resources assigned to granted UEs affect bit error rate (BER) and throughputs.Four algorithms are compared through simulations， including a random algorithm with traditional non-orthogonal multiple access scheme， a random algorithm with hybrid non-orthogonal multiple access scheme， a heuristic algorithm using SGAM[9]scheme and a genetic algorithm utilizing hybrid non-orthogonal multiple access scheme.

5.2.1 Impact of the number of granted UEs on performance

Assuming that the resources are allocated to granted UEs and grant-free UEs equally. The number of granted UEs is changed and values of BER and throughput are recorded.

Fig.4 shows mean BER curves， the performance simulation of physical layer， based on the four cases.It is obvious that genetic algorithm performs optimally.On the basis， throughputs of four algorithms will be compared next.

Fig.4 Mean BER of all UEs versus the number of granted UEs

Fig.5 and Fig.6 show that genetic algorithm performs optimally compared with the other three algorithms on average throughput.

For random algorithm with traditional non-orthogonal multiple access method， average throughput curve increases firstly， then keeps stable and lastly decreases. As resources allocated to granted UEs and grantfree UEs are strictly separated， their throughputs continue to grow until half of the resources are allocated to granted UEs. Then throughputs remain constant.Meanwhile as the number of grant-free UEs decreases，the probability of collision between grant-free UEs decreases.

For the other three algorithms， their average throughputs increase first and then keep stable. This is because resources are first assigned to granted UEs，then the remaining are accessed by grant-free UEs.Throughputs of granted UEs continue to increase until all resources are allocated to them and then stay unchanged. Meanwhile throughputs of grant-free UEs are reduced as resources allocated to them decline to 0. As heuristic algorithm and genetic algorithm optimize resources allocation of granted UEs and all UEs respectively， their throughputs are apparently better. Moreover， throughputs of genetic algorithm are superior to that of heuristic algorithm.

Fig.5 Mean throughputs of all UEs versus the number of granted UEs

Fig.6 Mean throughputs of granted UEs and grant-free UEs versus the number of granted UEs

5.2. 2 Impact of the ratio of resources assigned to granted UEs on performance

The simulation scenario consists of 50 granted UEs and 50 grant-free UEs. Due to the randomness of access probability， the number of grant-free UEs successfully transmitted is at most 25 theoretically. Then， this paper changes the ratio of resources assigned to granted UEs and records the values of BER and throughput.

Fig.7 shows mean BER curves based on the four cases. It is obvious that genetic algorithm performs optimally. Based on it， throughputs of the four algorithms will be compared.

Fig.7 Mean BER of all UEs versus the ratio of resources assigned to granted UEs

Fig.8 and Fig.9 illustrate mean throughputs varying with the ratio of resources assigned to granted UEs. Obviously， genetic algorithm is optimized than the other three algorithms.

For random algorithms with traditional non-orthogonal multiple access protocol， the average throughput goes up first and then down. Because in this algorithm resources assigned to granted UEs and grant-free UEs are strictly divided， throughputs of granted UEs continue to grow until all of them are allocated resources.Then their throughputs remain roughly unchanged.Meanwhile throughputs of grant-free UEs remain constant as all grant-free UEs can access resources at the beginning. Then with fewer and fewer resources available for grant-free UEs， the probability of collision between grant-free UEs goes up. As a result，their throughputs gradually descend.

For the other three algorithms， their average throughputs basically remain unchanged. Because resources are firstly allocated to granted UEs and then the remaining are randomly accessed by grant-free UEs，the ratio of resources allocated to granted UEs has no impact on throughputs. Therefore， their throughputs keep unchanged. In addition， heuristic algorithm and genetic algorithm have better throughputs because they optimize resources allocation for granted UEs and all UEs respectively. Further genetic algorithm is optimal.

Fig.8 Mean throughputs of all UEs versus the ratio of resources assigned to granted UEs

Fig.9 Mean throughputs of granted UEs and grant-free UEs versus the ratio of resources assigned to granted UEs

Fig.10 Resource utilization rate versus the ratio of resources assigned to granted UEs

Fig.10 shows resource utilization rate curves based on all the four cases. It is obvious that genetic algorithm outperforms other schemes. It means the proposed genetic algorithm based hybrid non-orthogonal multiple access protocol not only guarantees granted UEs access performance， but also improves the resource utilization.

6 Conclusions

As wireless connections become denser and network scale expands， a hybrid non-orthogonal multi-access approach is proposed. It further highlights its advantages. But random access brings more uncertainty.If the traditional allocation method based on resource isolation is still followed， the resource utilization rate will be lower. The method proposed in this paper fully considers the joint performance of scheduled access and random access. On the basis， a genetic algorithm based resource allocation is proposed. Simulation results show the presented scheme has stable performance gain with the increase of UEs. In conclusion， the scheme proposed in this paper has better adaptability and expansibility.