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.

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 [

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 [

MHD2D is an emerging technology capable of providing service to user-driven demand. Catering for the similar user demand, the authors in [

A standard Dijkstra shortest path-based routing algorithm is developed in [

Interference aware D2D routing is discussed in [

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 [

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.

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).

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.

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.

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

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.

The lower bounds of transmit power _{tlb} is required to ensure that a required threshold signal to noise ratio

where _{rth} in _{rth} can be used for deriving _{tlb} i.e., the lower bound of transmit power to ensure

where _{o}_{o}

For upper bound of _{t}_{rmax} and the received SNR will be _{tlb} and _{tub} (transmit power lower and upper bound respectively), so the maximum receiver power is given by

As it is obvious that received power increases with a decrease in distance between communicating nodes, hence, we denote the minimum distance as _{min}

So, transmit power upper bound is given as in

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

Similarly, the upper bound for capacity can be derived using

Now, the upper bound of EE can be written as in

Similarly, the lower bound for EE can be written as in

In this case, we will use the Signal to Noise and Interference (SINR) ratio represented by

where

The expressions for lower and upper bounds of capacity for a network with interference can be derived similarly and is given by

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

Let

^{p}) is maximization problem or it’s negative (− ^{p}) is minimization problem.

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 [

In MVABC, we take inspiration from the ABC algorithm and propose an algorithm for the implementation of MVABC for multi-hop path selection.

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 with _{i}_{i}

The following sequence takes place during the initialization step:

Fix swarm size

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 on _{p}_{p}

where

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 solution _{p}

If the objective function is within the bound specified in

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.

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

where _{i}

If MBS does not receive a route request reply from one of the nodes which previously sent a node discovery reply, after a wait of _{i}

Initially the generation of _{t}_{t}_{t}

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

where _{min}_{max}

The objective function and fitness of the new solution is calculated using

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

Parameter | Value |
---|---|

Population size | 100 |

Number of iterations | 200 |

1, 0.8, 0.2 | |

Cross over percentage | 0.7 |

Mutation percentage | 0.3 |

5 dbm | |

Number of runs | 30, 60 |

Number of variables | 2 |

Transmit power bounds | (0.02–0.25) J/s |

Capacity bounds | (1000–10000) bps |

A statistical approach similar to one utilized in [

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

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 [

The t-value for the hypothesis is calculated using

where grand standard deviation, _{X1X2} is given by

Run No. | MVABC | Classic ABC | GA | ||
---|---|---|---|---|---|

1 | Mean SDSEM | 0.00240.0120.0008 | 0.00980.10650.0075 | 0.01140.11190.0079 | |

2 | Mean SDSEM | 0.1330.12010.0085 | 0.00530.03850.0027 | 0.0030.02650.0019 | |

3 | Mean SDSEM | 0.00180.00770.00054 | 0.01170.08810.0062 | 0.00670.0580.0041 | |

4 | Mean SDSEM | 0.01220.11020.0078 | 0.0160.09940.007 | 0.00880.06940.0049 | |

5 | Mean SDSEM | 0.007 0.05240.0037 | 0.00940.07660.0054 | 0.00250.02380.0017 | |

6 | Mean SDSEM | 0.0044 0.02630.0019 | 0.0140.10040.0071 | 0.0060.07160.0051 | |

7 | Mean SDSEM | 0.00730.05630.004 | 0.00980.09750.0069 | 0.00560.04260.003 | |

8 | Mean SDSEM | 0.00290.01950.0014 | 0.01120.06370.0045 | 0.00600.04430.0031 | |

9 | Mean SDSEM | 0.00970.0751 0.0053 | 0.02380.1330.0094 | 0.0040.02240.0016 | |

10 | Mean SDSEM | 0.00370.01870.0013 | 0.00730.05120.0036 | 0.00360.0340.0024 | |

11 | Mean SDSEM | 0.006 0.03730.0026 | 0.01230.11080.0078 | 0.00370.04040.0029 | |

12 | Mean SDSEM | 0.00590.03090.0022 | 0.01170.08810.0062 | 0.00210.01830.0013 | |

13 | Mean SDSEM | 0.01120.11710.0069 | 0.0160.09940.007 | 0.00440.04540.0032 | |

14 | Mean SDSEM | 0.01120.09710.0069 | 0.0140.01140.0071 | 0.00540.05280.0037 | |

15 | Mean SDSEM | 0.00240.0120.00085 | 0.0086[0.06540.0046 | 0.0870.0850.06 | |

16 | Mean SDSEM | 0.01320.0830.0059 | 0.00980.09750.0069 | 0.00560.05090.0036 | |

17 | Mean SDSEM | 0.00730.07810.0055 | 0.01120.06370.0045 | 0.00220.01720.0012 | |

18 | Mean SDSEM | 0.0120.1030.0072 | 0.00340.01860.0013 | 0.00250.02150.0015 | |

19 | Mean SDSEM | 0.01540.10140.0072 | 0.00860.10450.0074 | 0.00430.03390.0024 | |

20 | Mean SDSEM | 0.00780.0390.0028 | 0.01230.11080.0078 | 0.00680.0440.0031 | |

21 | Mean SDSEM | 0.00350.02330.0016 | 0.00980.10650.0075 | 0.00460.03510.0025 | |

22 | Mean SDSEM | 0.00520.02830.002 | 0.00480.03040.0021 | 0.00620.0440.0031 | |

23 | Mean SDSEM | 0.01160.15160.0107 | 0.0160.09940.007 | 0.01040.07330.0052 | |

24 | Mean SDSEM | 0.00410.02050.0015 | 0.0090.0590.0042 | 0.00820.07390.0052 | |

25 | Mean SDSEM | 0.00730.07810.0055 | 0.00940.07660.0054 | 0.00230.01590.0011 | |

26 | Mean SDSEM | 0.00180.01070.00075 | 0.0140.10040.0071 | 0.00740.07560.0053 | |

27 | Mean SDSEM | 0.00780.0390.0028 | 0.00860.06540.0046 | 0.03210.37590.0266 | |

28 | Mean SDSEM | 0.00810.05130.0036 | 0.00620.0350.0025 | 0.00670.0530.0037 | |

29 | Mean SDSEM | 0.0050.02110.0015 | 0.00860.10450.0074 | 0.0580.5020.035 | |

30 | Mean SDSEM | 0.00820.04440.0031 | 0.00360.02080.0015 | 0.01540.12760.009 |

where _{X1} is the standard deviation of data for MVABC, and _{X2} is the standard deviation of data for classic ABC and represent the same for GA in subsequent calculations as given in

Group 1 (MVABC) | Group 2 (Classic ABC) | |
---|---|---|

Mean | 0.0073 | 0.0215 |

Variance | 0.0016 | 0.0008 |

STD | 0.04 | 0.0283 |

N | 30 | 30 |

T | −2.7376 | |

d.o.f | 58 | |

Critical value | 2 |

Group 1 (MVABC) | Group 2 (Classic GA) | |
---|---|---|

Mean | 0.0073 | 0.0191 |

Variance | 0.0016 | 0.0007 |

STD | 0.04 | 0.0265 |

N | 30 | 30 |

T | −2.4405 | |

d.o.f | 58 | |

Critical value | 2 |

The t-test will test the null hypothesis to check whether the mean of MVABC, classic ABC and GA are equal

where

Similar t-tests were performed between MVABC and GA. The statistical results are given in

This can further be realized by examining the error bar graph in

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.