Transmitter-Receiver Path Selection for Cell Range Extension Using Multi-Hop D2D

Farah Akif,Kiran Sultan,Aqdas N.Malik,Ijaz M.Qureshi and Saba Mahmood

1Department of Electrical Engineering,International Islamic University,Islamabad,44000,Pakistan

2Department of CIT,FAS,King Abdulaziz University,Jeddah,21551,Saudi Arabia

3Department of Electrical Engineering,Air University,Islamabad,44000,Pakistan

4Department of Computer Science,Bahria University,Islamabad,44000,Pakistan

Abstract:Conventional approach of dealing with more users per coverage area in cellular networks implies densifying the amount of(Access Point)AP which will eventually result in a larger carbon footprint.In this paper, we propose a base station off-loading and cell range extension (CRE) scheme based on multi-hop device-to-device(MHD2D)path selection between transmitter and receiver node.The paper also provides derivations of upper and lower bounds for energy efficiency,capacity,and transmit power.The proposed path selection scheme is inspired by the foraging behavior of honey bees.We present the algorithm as a modified variant of the artificial bee colony algorithm(MVABC).The proposed optimization problem is modeled as a minimization problem where we optimize the Energy Efficiency (EE).The proposed path selection MVABC is compared with the Genetic Algorithm (GA) and also with classical artificial bee colony (ABC) through simulations and statistical analysis.The student’s t-test, p-value, and standard error of means (SEM)clearly show that MVABC based path selection out-performs the GA and classical ABC schemes.MVABC based approach is 66%more efficient when compared with classic ABC and about 62%efficient when compared with GA based scheme.

Keywords: Multi-hop; ultra-dense; D2D; path-selection; ABC; GA

1 Introduction

Conventional cellular networks provide coverage to a user by having a direct connection established between a user and the base station.Although the scheme provides communication with less delay, the recent trend of increased wireless data users and devices makes it difficult for the conventional scheme to fulfill the QoS (Quality of Service) requirements [1].This apparent increase in the data requirement or increase in the number of users reduces network reliability and efficiency when it is not able to cater to new users or provide dependable services to the edge users.Hence, the effect is similar to having a cell with reduced coverage.Increasing the number of BS in a cell may solve this issue but at the expense of increased BS and equipment installation charges along with an overall increase in power consumption.D2D communication promises to provide an alternative to this problem by allowing mobile devices to communicate directly with each other using low power in quite possibly the same band being used by some other cellular device [2].This concept is based on space division multiple access.

From 3GPP (third generation global partnership project) LTE (long term evolution) release 12 and onwards, it is quite apparent that a MHD2D network is set to become a necessary part of 5G networks.Standards for D2D communication along with two-hop communication are already part of the latest release [3].Moreover, the cell range of base stations can be extended by utilizing MHD2D relay nodes.To ensure that the cell range extension (CRE) offered by D2D links meet the required QoS demand, the energy efficiency (EE) metric is commonly used [4] which is generally defined as:

1.1 Related Work

MHD2D is an emerging technology capable of providing service to user-driven demand.Catering for the similar user demand, the authors in [5] developed an algorithm for long-range D2D links which is done through multi-hop communication.However, the study lacks any insight regarding optimal path selection.In [6] the authors developed an algorithm for power control and routing in MHD2D where Dijkstra shortest path algorithm is used for routing.A drone-based D2D aided multi-hop network for emergency services is proposed in [7] where stochastic geometry is used for link coverage probability to minimize delay, however, the path selected for emergency message transmission is not considered in this paper.

A standard Dijkstra shortest path-based routing algorithm is developed in [8] for D2D for multi-hop communication in the Internet of Things (IoT) application.D2D based solution for offloading traffic in a cellular network is proposed in [9], the proposed framework offers a multihop routing scheme for different types of data transmissions.In [10] a MHD2D energy-efficient routing protocol is proposed to perform resource allocation while improving throughput and packet delivery ratio.MHD2D routing for the millimeter-wave network is proposed in [11] where received signal strength (RSS) is measured for relay nodes and an algorithm is designed to select a route based on the probability of route selection as generated by their RSS values.

Interference aware D2D routing is discussed in [12] where an adaptive algorithm is proposed which selects a route based on node location and amount of interference at next hop.Optimum path selection for 5G vehicular networks based on mmWave D2D links is discussed in [13] where the optimum path is found based on vehicular information rather than link quality.The authors in [14] investigate multi-hop data transfer between D2D transmitter and receiver by scheduling cellular resource blocks for optimizing transmission power which is done by maximizing the number of relay-based paths.In [15] a greedy algorithm is proposed for MHD2D relay selection.The algorithm works on a distributed local search.

The above-presented literature review on path selection, routing, or relay selection in MHD2D network clearly shows a lack of heuristic approach towards problem-solving, this gap is largely addressed in the proposed research.Literature provides evidence of using an ABC (artificial bee colony) based algorithm for optimization.ABC based scheduling is proposed in [16] where modified ABC is implemented for reducing travel distance and waiting time for a manufacturing workshop.The authors in [17] utilized ABC for the vehicle-to-vehicle emergency information dissemination by using the algorithm minimum route selection from source to destination.In [18]the ABC algorithm is implemented for intrabody nanonetwork where it is used for optimal selection of biosensors along the transmission path.The low energy reliable routing protocol problem is presented as an NP-hard problem in [19] which is solved using an ABC algorithm.

The literature survey supports the argument that heuristic approaches can be applied for optimum path selection, at the same time application for same in CRE for MHD2D remains unaddressed.

1.2 Contribution

The major contributions of the research are:

? An MHD2D link-based cell range extension scheme is proposed.

? Single antenna transmit power and capacity upper and lower bounds calculations for the network without interference are derived.

? Upper and lower bounds of single antenna energy efficiency for a system without interference are calculated are derived.

? Transmit power and capacity upper and lower bound calculations for single antenna network with interference are derived.

? Energy efficiency upper and lower bound calculations for a network with interference derived.

? MVABC proposed for source-destination path selection in a MHD2D based link for CRE.

? Comparison between MVABC and genetic algorithm (GA) based path selection for MHD2D link between the source and destination node through simulation over a large data set of 30 runs of 200 iterations each is presented.

? Comparison between MVABC and classic ABC based path selection for MHD2D link between the source and destination node through simulation over a large data set of 30 runs of 200 iterations each is presented.

? Statistical analysis of simulation results using student’s t-test, p-value, and SEM (standard error of means).

1.3 Paper Organization

Section 2 describes the system model and assumptions.In Section 3 we provide detailed derivations for transmitting power, capacity, and energy efficiency for two cases i.e., case one provides derivations without interference while case two provides derivations while considering the effects of interference in a single antenna network.Section 4 gives the mathematical formulation of the problem.In Section 5 we describe MVABC based path selection for MHD2D, which is followed by simulation and results with discussion in Section 6, and the paper is concluded in Section 7.

2 System Model and Assumptions

We consider a single input single output system without interference.The mobile users are distributed around the Macro Base Station (MBS) as Homogeneous Poisson Point Process (HPPP)and downlink communication from MBS to a far-off destination node is considered.A ‘far-off’node is a node that lies just outside the cell range of MBS.Since the destination node D is located outside the coverage area of MBS, MHD2D links are used for CRE.It is also assumed that nodes independently decide about their willingness to participate in relaying between source and destination.The decision is based on the incentives offered to mobile relay nodes from the service providers.Fig.1 shows that MBS has several options in terms of finding a path to node D via MHD2D users.

Figure 1:Proposed D2D multi-hop source-to-destination communication

For the sake of simplicity, we assume that MBS is already operating at optimized power.Hence, we have to find upper and lower bound for transmitting power of relaying devices and capacity along the path from MBS to node D to optimize an energy-efficient path as described by Eq.(1).It is also assumed that the dissipation in transceiver hardware and baseband processing is negligible.We consider a scenario (refer to Fig.1) where a source node S wants to communicate with node D.Node S sends a connection request (Con.Req.) to MBS.Since MBS cannot directly locate node D in its cell range so it forwards a route request to the users at its cell boundary who then forwards the request to their neighbors and ultimately the request reaches the destination node.In this centralized model of route discovery, the MBS discovers the multi-hop route between node S and node D.In a decentralized case node S will directly broadcast a route request to its neighbors which will then further broadcast it to their neighbor until node D is reached.Both centralized and decentralized modes have their advantages and disadvantages, however, the comparison of the two is beyond the scope of the current research.

3 Energy Efficiency and Transmit Power Limits

We will consider two cases wherein the first case we find the transmit power and EE limits for the channel without interference while in the second case we derive the limits for the channel with interference.

3.1 Single Antenna Transmit Power Without Interference

The lower bounds of transmit powerPtlbis required to ensure that a required threshold signal to noise ratioγthcan be ensured during transmission.As:

wherePrthin Eq.(2) is the received power threshold which is the minimum acceptable received power that can ensure a signal to noise ratio (SNR) at least equal to the thresholdγth, soPrthcan be used for derivingPtlbi.e., the lower bound of transmit power to ensureγth, which is given by Eq.(4):

whereNis the noise power,dis the distance between nodes,dois the reference distance which is taken equal to 1 meter for indoor communication and 100 m to 1 Km for outdoor communication,Lis a constant which is the path loss computed atdoandαis the pathloss exponent.

For upper bound ofPt(transmit power) we will receive maximum powerPrmaxand the received SNR will beγmaxwhile staying withinPtlbandPtub(transmit power lower and upper bound respectively), so the maximum receiver power is given by Eq.(5):

As it is obvious that received power increases with a decrease in distance between communicating nodes, hence, we denote the minimum distance asdmin.So, the upper bound of transmit power can be derived as in Eq.(6):

So, transmit power upper bound is given as in Eq.(7):

3.2 Single Antenna Capacity and EE Without Interference

Here we are going to derive the expressions for upper and lower bounds of capacity and EE in a system without interference.Since the capacity is directly proportional to SNR so for the lower bound of capacity the transmit power will also be the lower bound and hence the SNR lower bound ofγthwill be used for the expression of lower bound of capacity as given by Eq.(8):

Similarly, the upper bound for capacity can be derived usingγmaxas in Eq.(9):

Now, the upper bound of EE can be written as in Eq.(10):

Similarly, the lower bound for EE can be written as in Eq.(11):

3.3 Single Antenna Transmit Power with Interference

In this case, we will use the Signal to Noise and Interference (SINR) ratio represented byγ′which can be written as Eq.(12):

whereP′is the interference power received from neighboring nodes.After substituting values of received power as in the case of single antenna transmit power without interference, we can write the expression for lower bounds of transmit power for nodei() and upper bound of transmit power for nodei() as given in Eqs.(13) and (14) respectively:

3.4 Single Antenna Capacity and EE with Interference

The expressions for lower and upper bounds of capacity for a network with interference can be derived similarly and is given by Eqs.(15) and (16) respectively:

Energy efficiency upper and lower bounds can be expressed in terms of the ratio of capacity and transmit power for a network with interference and can be expressed in Eqs.(17) and(18) respectively:

4 Problem Formulation

LetV= {v0,v1,...,vn} is the set of nodes,E= {e0,e1,...,en} is the set of edges whereE?{|i,j=0,1,2,...,n}.Path selection problem for maximizing EE can mathematically be represented as:

Such that:

Eq.(19) states the energy efficiency for a particular pathpwritten as (EEp) is maximization problem or it’s negative (?EEp) is minimization problem.Eqs.(20) and (21) enforce the capacity constraint on the selected path for the case without interference and the case with interference respectively.Similarly, Eqs.(23)-(25) impose the constraints of transmit power without and with interference on SNR and SINR lower and upper bounds for path selection.

5 MVABC for MHD2D Path Selection

The ABC algorithm is a nature-inspired algorithm where the natural behavior of honey bee for rich nectar source exploration is used for real-world problem-solving.The idea was first proposed by Karaboga in 2005 [20] and ever since then the idea has been refined and also it has found numerous problem-solving applications [21-27].Each food source corresponds to the solution for the optimization problem.The ABC algorithm consists of three types of bees based on their roles in the exploration process.

Scout:All potential food sources are explored by the scout bee.

Onlooker:Evaluate the nectar quality and quantity as learned from scouts traversing.

Employed Bees:Responsible for nectar collection from sources identified by the onlooker bees.If a food source is exhausted, the corresponding employed bee becomes a scout and looks for a new food source.

In MVABC, we take inspiration from the ABC algorithm and propose an algorithm for the implementation of MVABC for multi-hop path selection.Fig.2 shows a flow chart of the pseudocode for the MVABC algorithm for path selection.The proposed algorithms are presented in the Algorithms 1-4.

Algorithm 1:Initialization 1.For i=Np 2.For j=1 to D 3.M BS generates xi solutions 4.Where xi represents the nodes from SN 5.End 6. failurei=0 7.End

When node S sends a connection request to MBS, MBS broadcasts to users/devices at the cell edge for node discovery.Through MHD2D relays, node D is discovered and a reply is generated by each intermediate node (which previously received MBS request for node discovery)and sent back to MBS.Based on the received replies, MBS generates an initial population withSNsolutions representing the nodes which sent replies.Each of these D2D relay (food source positions) represent a possible solutionXi=(i=1,2,...,SN)which is aDdimensional vector representing the number of optimization parameters that are taken as two to represent capacity and transmit power.In the algorithmfailureirepresents the abandonment limit of a solutionxiand is equal to the number of unimprovedxi.

The following sequence takes place during the initialization step:

? Fix swarm sizeSNand number of cycles

? Determine the number of employed bees (EB), onlooker bees (OB), and food sources, i.e.,

For path selection problem this will equal the number of nodes.

? MBS generates random variables that will serve as the initial population within the domain of decision variables.

? MBS then calculates the fitness of the population.

? Generate initial trial vector for the population.

In this phase, MBS sends a route discovery message onNpwhereNprepresents all the possible nodes between S and D, each message sent from MBS behaves similarly to an EB.This route discovery message performs a neighborhood search similar to the EB.Since the node may already have forwarded node discovery request and received a reply, it will compare previous interaction with new interaction, similar to comparing the nectar amount of previous food source in EB memory with the nectar amount of the new food source.The old food location in memory is replaced by a new location if the new location has better nectar quality.The updated location is given by Eq.(27):

where ?is randomly chosen between [?1,1] andj∈{1,2,...,D}.

Figure 2:Flow chart of MVABC algorithm

Algorithm 2:MBS initiates employed bee phase 1.For i=Np 2.Node i receives route request from MBS 3.Node i generates new solution using (27)4.Node i compares fitness using (29)5.If fit(xi+1)>fit(xi)6.newsol=currentsol 7.failurei=0 8.Else 9.newsol=oldsol 10.failurei=failurei+1 11.End

To generate a new solution, first, we randomly choose a variable to change for the first food source i.e., first neighbor node, then we randomly choose a partner solutionXpand generate a new solution using Eq.(27).The solution is checked for obeying upper and lower bounds and after that fitness of the new solution is calculated using the objective function of Eq.(28):

If the objective function is within the bound specified in Eqs.(10) and (11) for the case without interference or satisfies Eqs.(17) and (18) for the case with interference, then, the fitness of the population is calculated using Eq.(29):

A greedy selection is performed between old and new solutions and the fittest of the two solutions is retained.The process continues until all the nodes who sent route request-reply (food sources) have been exhausted.

images/BZ_621_613_1560_716_1622.pngAlgorithm 3:MBS Initiates Onlooker Bee Phase 1.For i=Np 2.MBS calculates pi using (31)3.End 4. trial=0, i=1 5.Repeat 6.If pi<λ 7.trial=trial+1 8.For j=1toD 9.MBS produces Xjnew using (27)10.End 11.If newpi

Once the search process is complete and all possible paths have been visited by EB, i.e., MBS has sent route request messages on all possible paths, the D2D relays share their neighborhood information with MBS, this is similar to nectar amount being shared with OB through dance.The probability of a food source is calculated by OB (processing within MBS) using Eq.(30):

wherefitiis the fitness of solutionifor the EE ratio (nectar amount) it represents, where a comparison is made between old and new EE ratio values and the new one replaces the old position (node) if the new position (node) has a better fitness.

If MBS does not receive a route request reply from one of the nodes which previously sent a node discovery reply, after a wait ofttime intervals, that particular node will be abandoned.In classical ABC algorithm, in the onlooker bee phase, once the probabilities are calculated for all the possible fitness values, a random number is generated.The randomly generated number is compared with the probability ofith food source (pi).If the probability is less than the random number, then a new solution is generated using Eq.(27), otherwise, the old solution is maintained.In MVABC, we replace this randomly generated number with a number (λ) for making intelligent decision whether new solution should be generated or not.

Initially the generation ofλdepends on food source generated using lower bounds ofptandC, for these values we find the objective function, fitness and probability using Eqs.(28)-(30)respectively.We label this particular value of probability for lower bounds of transmit power and capacity asλ.As shown in algorithm 3, ifpi<λ, i.e., probability of ith food source is less than a predefined threshold for acceptable ranges ofptandC, then a new solution is generated using Eq.(27), otherwise the old solution is retained and probability of next food source is compared.In the simulation we have chosen three difference values ofλnamely 0.2, 0.8 and 1 for the sake of demonstration of results for its different values.For simulationλmay be assigned any value within in acceptable bounds ofptandC.This value can be fixed to generated most optimum results.

Algorithm 4:MBS Initiates Scout Bee Phase 1.If trial>maxt rial 2.MBS generates new solution using (31)

The SB phase is entered when any solution having a trial limit greater than a maximum exceeds.When MBS cannot improve an established path any further through route discovers, then,the previous best solution is stored in the memory and a new solution is generated randomly between upper and lower bounds using Eq.(31):

whereXminandXmaxare lower and upper bound of population respectively.

The objective function and fitness of the new solution is calculated using Eqs.(28) and(29) respectively and it replaces the old solution even if it has poor fitness compared to the old solution.

6 Simulation and Results

The comparison and performance analysis of the proposed algorithm was carried out in Matlab R2018b.The simulation parameters are presented in Tab.1.

6.1 Performance Metrices

A statistical approach similar to one utilized in [28] was used to evaluate the results.We will briefly describe the performance metrices in this sub-section and their details are given in the sub-section below along with discussion on results.

Table 1:Simulation parameters

Best Cost(Mean abs(-EE)):As described in Section 1, in this research we consider maximizing the EE or minimizing the (-EE) and is presented for proposed algorithm MVABC along with classic ABC and GA.

Standard Deviation(SD):Describes the variation in mean data values.

Standard Error of Means(SEM):Measures deviation of sample’s mean from population mean.

6.2 Results

The proposed algorithm was compared with classic ABC and GA based path selection.Both algorithms were tested using large data set with 30 and 60 runs with 200 iterations per run.The population size and cycle limit were kept the same for all the simulated cases of MVABC, GA and classic ABC.

For GA based algorithm we kept the crossover percentage at 0.7, mutation percentage at 0.3,and mutation rate at 0.1.A population size of 100 was used for all three algorithms.We calculated the mean best cost, SD and the SEM for each run.

We compared GA, classic ABC and MVABC based path selection through simulation over a large data set with randomly generated seed values.The mean best, standard deviation, and SEM are given in Tab.2 for 30 runs of each algorithm.

To show whether the experimental results obtained from MVABC, classic ABC and GA for path selection are significantly different, we perform Student’s t-test hypothesis [28].The t-test statistically verifies if the difference in the mean values is due to the variation in sampling or does it present evidence that MVABC provides better convergence to the solution.

The t-value for the hypothesis is calculated using Eq.(32):

where grand standard deviation,SX1X2is given by Eq.(33):

Table 2:Statistical results from 30 runs of MVABC, classic ABC and GA

Table 2(continued).

whereis mean of data for MVABC,is mean of data for classic ABC for obtaining results as in Tab.3 and in subsequent calculations it represents mean of GA where results are presented in Tab.4.SX1is the standard deviation of data for MVABC, andSX2is the standard deviation of data for classic ABC and represent the same for GA in subsequent calculations as given in Tab.4.

Table 3:Summary of statistical T-test results for MVABC and classic ABC

The t-test will test the null hypothesis to check whether the mean of MVABC, classic ABC and GA are equalvs.an alternate hypothesis that the mean of MVABC, classic ABC and GA are not equal and the MVABC test results hold more significance.The result of the t-test performed on the data set labeled as Group1 (MVABC) and Group 2 (classic ABC) is given in Tab.3.

Table 4:Summary of statistical T-test results for MVABC and GA

whereNis the total number of runs of each algorithm,Tis the t-test value (who’s absolute is compared to the critical value), d.o.f (degree of freedom) refers to maximum logically independent values that can vary with freedom in a sample of data and is given byd.o.f=2n?2, wherenis the total number of iterations.Its value is important because it helps in determining the critical value against which a hypothesis is tested.The test shows that the means of MVABC and classic ABC are significantly different atp<0.05 significance level.Wherepis the probability of having a value less than the significance level indicates that the null hypothesis is rejected and the alternate hypothesis is accepted, in other words, we can say that the mean path cost calculated by MVABC is less than that using classic ABC.This implies that the nodes selected between source to destination using MVABC represented a more energy efficient path.

Similar t-tests were performed between MVABC and GA.The statistical results are given in Tab.4.As in the case of comparison with classic ABC, MVABC compared to GA is again capable of providing a more energy efficient path.

This can further be realized by examining the error bar graph in Fig.3.MVABC was tested for different values ofλ.Since the error bars are not overlapping (Fig.3) hence it can be seen that there is a significant difference in the results generated by MVABC and those by classic ABC and GA, so, the null hypothesis is rejected and the alternative hypothesis is accepted.Moreover,the difference in means calculated using the MVABC, classic ABC and GA can also be observed for various values ofλ, the results can be seen in Fig.4.The results represent better convergence of MVABC and better overall best cost value compared to classical ABC.In Fig.5a comparison is drawn between different values ofλapplied in MVABC with classic ABC.Various values ofλfor MVABC clearly offer least cost solution compared to the classic ABC.

Figure 3:SEM comparison between MVABC, Classic ABC and GA

Figure 4:Comparison of means between MVABC, Classic ABC and GA

Figure 5:Comparison of different values of λ in MVABC with classic ABC

7 Conclusion

This paper proposed an MHD2D link for CRE or offloading of the base station.An MVABC algorithm was proposed for path selection between source and destination for an MHD2D link.Upper and lower bounds of transmit power, capacity, and energy efficiency for the network with and without interference were derived.The proposed MVABC approach for MHD2D path selection was compared with classical ABC and GA-based MHD2D path selection for a large data set with the same population size and same upper and lower bounds for population generation.The simulated results signified the improved performance of MVABC over classic ABC and GA based approach.The simulated results were further verified using statistical techniques namely the student’s t-test, p-value, and SEM.The detailed statistical analysis confirmed that MVABC outperformed GA based MHD2D based path selection.

As future work, we will consider multi-antenna system with both centralized and decentralized approaches for path finding.We also plan on improving MVABC further in this respect and develop a generalized algorithm for single and multi-antenna systems.

Funding Statement:The authors received no specific funding for this study.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.