Cooperative Smartphone Relay Selection Based on Fair Power Utilization for Network Coverage Extension

Abstract

This paper presents a relay selection algorithm based on fair battery power utilization for extending mobile network coverage and capacity by using a cooperative communication strategy where mobile devices can be utilized as relays. Cooperation improves the network performance for mobile terminals, either by providing access to out-of-range devices or by facilitating multi-path network access to connected devices. In this work, we assume that all mobile devices can benefit from using other mobile devices as relays and investigate the fairness of relay selection algorithms. We point out that signal strength based relay selection inevitably leads to unfair relay selection and devise a new algorithm that is based on fair utilization of power resources on mobile devices. We call this algorithm Credit based Fair Relay Selection (CF-RS) and in this paper show through simulation that the algorithm results in fair battery power utilization, while providing similar data rates compared with traditional approaches. We then extend the solution to demonstrate that adding incentives for relay operation adds clear value for mobile devices in the case they require relay service. Typically, mobile devices represent self-interested users who are reluctant to cooperate with other network users, mainly due to the cost in terms of power and network capacity. In this paper, we present an incentive based solution which provides clear mutual benefit for mobile devices and demonstrate this benefit in the simulation of symmetric and asymmetric network topologies. The CF-RS algorithm achieves the same performance in terms of achievable data rate, Jain’s fairness index and utility of end devices in both symmetric and asymmetric network configurations.

1. Introduction

To avoid the infrastructural and operational cost of specialized relay stations in wireless networks, ordinary mobile devices can be used as relays in events of poor network coverage or to enable multi-path communication. These relays can either be used to forward all of the data from a remote device to the nearest network access point or base station or they can create an additional, secondary path to be used to improve overall network capacity and network reliability in the case of a breakdown or poor quality of the original, primary path. As discussed in our previous work [1], when a mobile terminal is used as a relay for data transfer from another mobile terminal, it uses its own power resources, leading to faster battery drainage. Any framework expecting mobile devices to cooperate and accept the role of relays requires incentives for these terminals to participate in the relay assisted network structure [2,3,4,5,6]. Most of the research in this field correctly assumes that a public wireless network is comprised of self-interested devices who are not willing to cooperate and are only interested in their own benefit. The factors that contribute towards the selfishness of the devices are [7]: (1) the lack of resources, e.g., low battery power, available memory or computational capability; (2) the security concern of receiving malicious information from other devices in the network; (3) no incentive to collaborate with other devices. Proper incentives need to be given to these self-interested devices to make them use their resources for providing relay service to other devices in the network [8,9,10,11,12,13,14].

Two commonly used incentive mechanisms for cooperative communication are reputation based mechanisms and credit based mechanisms [15]. Since the devices considered in this paper are self-interested and not malicious, the relay selection algorithm proposed in this paper employs a credit based mechanism, rather than a reputation based mechanism, to encourage the self-interested devices to take part in the data forwarding service for other devices. In a credit based mechanism, a device earns tokens or monetary benefits by assisting fellow network devices. These tokens and monetary benefits compensate for the cost incurred by the collaborating devices, which can be in terms of battery power consumption, sharing of bandwidth or transmission time. The earned tokens can then be utilized to buy cooperation from other devices when needed and putting the devices with no credits at a disadvantage.

The literature on cooperative communication mostly emphasizes fair allocation of bandwidth [16,17], optimal allocation of power [6,18,19,20,21] or energy efficiency of the network [3,22]. However, the physical layer fairness measured by fair dissipation of the battery power of the relays taking part in the cooperation has not been thoroughly addressed [23,24]. Most of the relay selection algorithms choose devices with better signal strength, usually the ones located close to either the base station or the end device, as relays, which implies that some devices spend much of their battery power relaying data, while others located farther spend nothing at all. This results in unfair battery power utilization of relay devices. In addition, the performance of the signal strength based relay selection techniques degrades in an asymmetric network topology.

The network model studied in this paper consists of Access Points (APs) and mobile devices. The mobile devices can access network resources via the APs and in addition can operate in two modes: (1) as a relay or (2) as an end device. The mode of operation of mobile device depends on its location with regard to the AP and on its willingness to act as a relay. All devices are assumed to be selfish and need to be incentivized in order to become relays. This paper defines a new algorithm, which we call a Credit based Fair Relay Selection (CF-RS) algorithm. This algorithm uses the Stackelberg game to enable the ordinary mobile devices to increase their instantaneous benefit by selecting the most suitable relay device and use this device to forward the data. The instantaneous benefit of a mobile device depends on the offered data rate and the price for using relays, advertised by all available relays. These prices, in turn, depend on the relaying cost, calculated using the instantaneous and cumulative battery power dissipation of the relay. The individual benefits are defined in a way that ensures fair utilization of the relays’ battery power. Relays accumulate the price paid for forwarding other devices’ data as credits, which can be used by relay devices to purchase data relaying service from other relays when required. Two network configurations have been analysed in this paper: symmetric and asymmetric. In the symmetric topology, the end devices are uniformly distributed around relays, and relays get to serve almost an equal number of end devices; whereas in the asymmetric topology, the end devices are unevenly distributed, and some relays are surrounded by more end devices compared to other relays. Simulation results presented in this paper show that: (1) with appropriate pricing models, it is possible to achieve fair utilization of relay battery power with minimal effect on the overall data rate, which is not affected by the network topology, i.e., in symmetric and asymmetric network configurations, the performance is comparable; (2) in a number of mobility scenarios, there is clear overall benefit to mobile devices to act as relays.

The reminder of the paper is organized as follows: Section 2 summarizes the literature on relay selection and credit based incentive techniques encouraging the selfish devices to participate in cooperative communication. The network model with the formulation of the formal relay selection problem is discussed in Section 3. A credit based game using the extended form of the Stackelberg game for the relay selection problem is described in Section 4. Derivation of the pricing function is examined in Section 5, and the CF-RS algorithm is discussed in Section 6. The results obtained are provided in Section 7, and Section 8 concludes our paper.

2. Related Work

Many relay selection techniques have been proposed in the literature; however, most of them either ignore the fact that public networks are composed of selfish devices or ignore the importance of the fair utilization of the relay’s battery power. To motivate self-interested devices, different credit based mechanisms and pricing schemes have been proposed, which can be broadly classified into three categories. In the first category, the threat of future punishment is utilized to enforce cooperation among network devices [8,9,10]. The second category provides network devices with opportunities to earn credits and tokens that can be used later when needed, giving them incentives to help one another [11,12,25,26,27]. The third category of credit and pricing mechanisms employs auction theory to promote collaboration among network devices [13,14]. Zhou et al. [28] proposed an auction-matching based algorithm for relay selection and spectrum allocation and analysed spectrum efficiency in cooperative vehicular relay networks. Auction based schemes require a central controlling entity called the auctioneer to govern the interaction between the seller and the buyer, making it an infeasible option for the network model studied in this paper. The drawback of punishment based incentive mechanisms is that there is no instantaneous benefit for relay devices, and there is no choice available to them to reserve their resources for their own data transmission; whereas the incentive based mechanisms are more suitable for the network model studied in this paper to encourage the selfish devices to cooperate with each other.

Lam et al. [2] proposed a game-theoretic mechanism introducing the idea of deploying pricing as an incentive to motivate self-interested devices to participate in relaying data for other devices of a public wireless mesh network. Coalitional game theory was employed by Saghezchi et al. [3] and Khayatian et al. [19] for relay selection. In a coalitional game, all players cooperate to follow a group strategy that maximizes their collective benefit. Zhou et al. [29] also used the coalition game for resource allocation in device-to-device based cooperative vehicular networks. Connections between vehicles were predicted using data from the Global Positioning and Geographic Information System, and then, coalition game theory was employed to determine content distribution groups to minimize the network delay. Mastronarde et al. [4] devised a token based system to incentivize self-interested devices to act as relays in cellular networks and used the Markov Decision Process (MDP) to predict when it is beneficial for a device to provide relay services to other devices of the network.

The Stackelberg game has been widely used to address the relay selection problem in wireless networks comprised of self-interested devices [5,6,30,31,32]. The Stackelberg game was utilized by Wang et al. [5] for relay selection and modelling of the power control mechanism in cooperative networks. Their algorithm determines the optimal price a relay shall advertise for its data forwarding services, the optimum number of relays to be selected by the source device and how much power to buy from each chosen relay. Cao et al. [6] considered a single relay network and also utilized the Stackelberg game for the selection of the optimal price advertised by a relay and the Kalai–Smorodinsky bargaining solution to fairly allocated relays’ power among users. Zhou et al. in [33] utilized Time-Dependent Pricing (TDP) to mitigate peak-time congestion in software defined cellular networks. They proposed a Stackelberg game based hierarchical framework to model the interaction between Internet Service Providers (ISPs) and users. By estimating the traffic demand from the network users, the ISP calculates the optimum congestion price with the objective of maximizing its revenue. This price motivates the delay tolerant users to defer their demand for bandwidth usage from peak to off-peak time. However, none of these incentive based techniques have considered the fair utilization of the battery power of relays.

Michalopoulos and Karagiannidis [23] studied the fair utilization of the battery power of relays in cooperative networks employing Amplify and Forward (AF) cooperative mode. Their technique ensured that the average energy consumption of all relays in the network remained equal by assigning a weight coefficient to each relay, which was then used to calculate the timer value for every relay. The relay with the highest weight coefficient had the smallest timer value and was chosen as the best relay for cooperative communication. Liu et al. [24] complemented the work in [23] by developing a distributed algorithm for path selection imposing the constraint of equal power consumption for Decode and Forward (DF) cooperative mode. Ahmed et al. [34] also analysed the relay selection and fair power assignment problem and promoted the idea of forming the relay subset and choosing the best relay from the subset of relays. Li et al. [35] proposed an outage priority based proportional fair scheduling, which urges that it is not necessary to always employ the relay with the best channel conditions to support the source destination communication. The timer value dependent on the channel quality of both source-relay and relay-destination channels was multiplied by a weighted value to increase the probability of the selection of the relay with mediocre channel quality. The work in [35] further enhanced fairness by designing a cross-layer opportunistic scheme in which an energy counter is assigned to each relay node, and the node with the smallest counter value is selected as the best relay.

Zhao and Pan [36] advocated that by increasing the probability of choosing relays with poor channel conditions, as well as decreasing the probability of picking the relays with good channel quality, fairness in terms of battery power consumption can be achieved. However, the works in [23,24,34,35,36] considered obedient relays, and there was no incentive for relays to help the source-destination communication, though relays were consuming their battery power fairly, but without gaining any benefit. Most public networks consist of self-interested devices who, along with incentives, require insurance for fair utilization of their power. Therefore, a new credit based relay selection algorithm is needed, which takes into account the fair utilization of the battery power of relays, as well as provides incentives to self-interested relays to participate in the relay process.

3. Network Model

The network model analysed in this paper consists of an AP and mobile devices. The mobile devices, depending on their location, can either directly communicate with the AP or require the relay services of intermediate devices to reach the AP. In Figure 1a, the devices denoted as R (Relays) can directly access the AP whereas for devices labelled as ED (End Device), similar to [35], it was assumed that the direct link quality is unsatisfactory and that these devices require assistance for their data transmission and reception from the AP. When a mobile device is in idle mode, it can act as a relay for end devices by receiving data from the AP and can forward this to the end device. Providing data forwarding service comes with an inherited cost in terms of the battery power consumption, i.e., the relay will use some of its battery power to receive and forward end device’s data. There should be some incentives to encourage the mobile devices to provide relaying service to the end devices. The considered network model employs simple AF cooperative mode for providing relay service to the end devices. Since no direct link exists between the AP and the end devices, an end device can only access the AP with the help of a relay; see Figure 1b.

An end device will prefer a relay having a good channel quality, hence providing the largest data rate. On the other hand, a relay needs to be motivated to serve an end device by providing incentives like earning some benefit with minimum consumption of its battery power. The incentive in the considered network model is the price paid to the relay by the end device, i.e., the device pays the relay for its services. The price paid to the relay becomes the credits earned by the relay, which can be utilized to buy data forwarding service for itself when it becomes the end device. Furthermore, each relay present in the network will want a fair chance to be selected by the end device to earn a benefit, and the battery power of all relays is utilized fairly. Fair utilization of the battery power of relays can be achieved using the concept of proportional fairness [37,38], i.e., by minimizing the cumulative to instantaneous battery power consumption of each relay. Thus, the relay selection problem can be formulated as a multi-objective problem given by Equations (1)–(3):

$$max{U}_j=\left[R_{ij}-p_{ij}{P}_{ij}\right]x_{ij}\forall i,j$$

(1)

$$max{U}_i=\left[p_{ij}{P}_{ij}-c_{ij}\right]x_{ij}\forall i,j$$

(2)

$$min\left[\frac{\overline{CB{P}_i}}{CB{P}_{ij}}\right]x_{ij}\forall i,j\mathrm{and}CB{P}_{ij}\propto P_{ij}$$

(3)

where $U_j$ is the utility of end device j, $U_i$ is the utility of relay i and $\overline{CB{P}_i}$ and $CB{P}_{ij}$ are the cumulative and the instantaneous battery power consumption of relay i, which is the cost incurred while providing relaying service. Thus, Equation (3) then becomes:

$$min{c}_{ij}{x}_{ij}\forall i,j\mathrm{and}CB{P}_{ij}\propto P_{ij}$$

(4)

The optimization problem is to find the optimal relay i and how much power $P_{ij}$ to buy from i that maximizes the utility of end device j, as well as minimizing the $\frac{\overline{CB{P}_i}}{CB{P}_{ij}}$ ratio in order to achieve fair utilization of the battery power of all relays and the optimal price $p_{ij}$ to be advertised by the relay considering the cost $c_{ij}$ of its relaying services in order to maximize its utility and earn credits. The price advertised by the relay is the controlling parameter governing the relay selection process. $x_{ij}$ is a binary variable taking values:

$$x_{ij}=\left\{\begin{array}{cc}1\hfill & \mathrm{relay}i\mathrm{serving}\mathrm{end}\mathrm{device}j\hfill \\ 0\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

whereas $p_{ij}$$\in \mathrm{I}\mathrm{R}$ and $P_{ij}$$\in Z$. The relay selection problem studied in this paper is subject to the following system constraints:

• An end device can communicate with the access point only with the help of a relay:

  $$\sum _{i=1}^N{x}_{ij}=1\forall j$$

  (5)
• The battery power of a mobile device to be selected as the relay should be greater than a predefined threshold:

  $$\sum _{j=1}^{M}B{P}_i{x}_{ij}>B{P}_{th}\forall i$$

  (6)
• The relay should be in the transmission range of the AP, as well as that of the end device in order to be selected as the relay:

  $$\sum _{j=1}^M{d}_{Ai}{x}_{ij}\le T_A\forall i$$

  (7)

  $$\sum _{j=1}^M{d}_{ij}{x}_{ij}\le T_j\forall i$$

  (8)

  where $d_{Ai}$ is the distance between the AP and relay i, $T_A$ the transmission range of the AP, $d_{ij}$ the distance between relay i and end device j and $T_j$ is the transmission range of end device j
• The budget of the end device j should be greater than the price $p_{ij}$ advertised by the relay i:

  $$\sum _{i=1}^N{\beta }_j\times x_{ij}>p_{ij}\forall j$$

  (9)

The relay selection problem, being a multi-objective non-linear programming problem, with binary $x_{ij}$, integer $P_{ij}$ and real $p_{ij}$ variables, is mathematically expensive to solve. We propose a heuristic solution based on game theory, described in Section 6, to solve this relay selection problem.

4. Credit Based Fair Relay Selection Game

The CF-RS game consists of two sets of players: relays and end devices. The relay is the seller in CF-RS game since it is selling its data forwarding service, whereas the end device is the buyer of this data forwarding service. The extensive form was used to represent all steps of the CF-RS game. The extensive form of the game was basically a decision tree outlining the set of options available to each player during different steps of the game [39,40]. In the beginning of the CF-RS game, the relay determined whether to provide data forwarding service to a particular end device or not, by analysing its utility. Depending on which strategy the relay decides to follow, the end device determines whether to accept the data forwarding service from the relay or refuse the service. If the end device denies the service, the game ends. After providing service to the end device, the relay makes a decision on whether to (1) increase the price of its service, (2) keep the price constant or (3) not to provide service any further. The relay advertises price for its unit power, and the end device, depending on its available budget, can choose from three possible strategies, which are: (1) buy more units of power from the relay (compared to what was bought from the same relay before); (2) buy less units of power; or (3) not to accept the service. The game ends when the relay decides not to participate in the relaying process or when the end device rejects the service of the relay. Figure 2 presents the extensive form of the CF-RS Stackelberg game along with the strategy set of each player at each step of the game.

The strategy a player follows at each step of the game is determined using the utility function of the player. The utility function of the relay has been defined as the difference between the price per unit power paid by the end device and the cost the relay experiences while providing the data forwarding service given in Equation (10).

$$max{U}_i=p_{ij}{P}_{ij}-c_{ij}$$

(10)

$p_{ij}$ is the price per unit power advertised by relay i for end device j and $P_{ij}$ is the amount of power end device j buys from relay i. The smaller the price per unit power, the more transmission power is bought by the end device. The price advertised by the relay should be greater than its cost in order to be incentivized to participate in the data relaying service.

The decision on availing assistance from a particular relay is made by the end device considering its budget, i.e., does it have enough budget to pay for the relay’s service? The end device also makes a decision on which strategy to adopt at each step of the game using its utility function (Equation (11)), which is defined as the difference between the achieved data rate via a relay and the price paid to that relay. The relay, as well as the end device tend to maximize their utility functions. The CF-RS Stackelberg game provides a balance between the objectives of the end device and the relay by making them opt for a strategy that results in providing a benefit for both devices.

$$max{U}_j=R_{ij}-p_{ij}{P}_{ij}$$

(11)

The relay also needs to decide the price it should advertise for its service in order to attract more end devices. Along with attracting the end devices, a relay is also concerned about its own cost in terms of its battery power consumption. The cost function used in the CF-RS game takes into account the instantaneous power dissipation of a relay for a particular end device, as well as its cumulative battery power consumption utilizing the idea of proportional fairness as shown in Equation (12).

$$c_{ij}=\frac{\overline{CB{P}_i}}{CB{P}_{ij}}$$

(12)

where $\overline{CB{P}_i}$ is the cumulative power consumption of relay i and $CB{P}_{ij}$ is the instantaneous battery power relay i uses for transmission to end device j. This formulation of the cost function of relays utilizing the concept of proportional fairness provides a fair opportunity to each relay to participate in the relay selection process. This fair participation results in diminishing the monopoly of the mobile devices located close to the end devices from being repeatedly selected as relays, as well as fair utilization of the battery power of all relays. In order to determine how fairly the battery power of relays is being consumed, Jain’s fairness index [41] was used, Equation (13). Equation (13) has been modified to calculate the fairness index for the consumption of the battery power of relays, given in Equation (14):

$$f\left(X\right)=\frac{{\left[{\sum }_{i=1}^n{x}_i\right]}^2}{n{\sum }_{i=1}^n{x}_i^2}$$

(13)

$$f\left(X\right)=\frac{{\left[{\sum }_{i=1}^{n}CB{P}_i\right]}^2}{n{\sum }_{i=1}^{n}CB{P}_i^2}$$

(14)

where $CB{P}_i$ is the battery power consumption of relay i.

Existence of Equilibrium for the CF-RS Game

Stackelberg equilibrium for the CF-RS game can be defined as follows:

$$U_j\left(P_{ij}^{SE}\right)=\underset{P_{ij}\in \left[0,P_{max}\right]}{max}{U}_j\left(P_{ij}\right)$$

(15)

$$U_i\left(p_{ij}^{SE}\right)=\underset{p_{ij}>c_{ij}}{max}{U}_i\left(p_{ij}\right)$$

(16)

In the equation, $P_{ij}^{SE}$ and $p_{ij}^{SE}$ are the Stackelberg equilibrium. To find the equilibrium condition for the proposed game, we need to determine the optimal power $P_{ij}$ the end device shall buy from the relay and the optimum price $p_{ij}$ the relay shall advertise that will maximize their respective utilities. By taking the second order partial derivative of $U_j$ defined in Equation (11) with respect to $P_{ij}$, we obtain:

$$\frac{{\partial }^2{U}_j}{\partial P_{ij}^2}=-AB\overline{W}\left[\frac{2\left(1+A\right)+2B+AB}{{\left\{\left(1+A\right)P_{ij}^2+\left(2B+AB\right)P_{ij}+B^2\right\}}^2}\right]$$

(17)

where $A=\frac{P_{Ai}{G}_{Ai}}{{\sigma }^2}$, $B=\frac{P_{Ai}{G}_{Ai}+{\sigma }^2}{G_{ij}}$ and $\overline{W}=\frac{W}{ln 2}$. $P_{Ai}$ is the transmission power of the AP and relay i link, $G_{Ai}$ the channel gain of the AP and i link, $G_{ij}$ the channel gain of i and j link, ${\sigma }^2$ the noise power and W the bandwidth. Since $\frac{{\partial }^2{U}_j}{\partial P_{ij}^2}<0$, this implies that the function $U_j$ given in Equation (11) is strictly concave, and the local maximum at $P_{ij}$ is also the global maximum. Thus, $P_{ij}$ maximizes the utility function of the end device for a given $p_{ij}$. By equating $\frac{\partial U_j}{\partial P_{ij}}=0$, the optimal power the end device shall buy from the relay can be obtained and is given by Equation (18):

$$P_{ij}=\frac{-p_{ij}\left(2B+AB\right)+\sqrt{AB{p}_{ij}\left\{AB{p}_{ij}+4\overline{W}\left(1+A\right)\right\}}}{2p_{ij}\left(1+A\right)}$$

(18)

For a detailed derivation, see [42]. Similarly, by taking the second order partial derivative of $U_i$ given by Equation (10) with respect to price $p_{ij}$, we get:

$$\frac{{\partial }^2{U}_i}{\partial p_{ij}^2}=\frac{-\overline{W}AB}{p_{ij}\sqrt{A^2{B}^2{p}_{ij}^2+4\overline{W}AB{p}_{ij}}}$$

(19)

Since $\frac{{\partial }^2{U}_i}{\partial p_{ij}^2}<0$, therefore the function $U_i$ given in Equation (10) is strictly concave, and there exists an optimal price $p_{ij}$, which will maximize the utility function of the relay. By equating $\frac{\partial U_i}{\partial p_{ij}}=0$, the value of $p_{ij}$ is determined as given below:

$$p_{ij}=\frac{\overline{W}A}{B}$$

(20)

Equation (20) presents the optimal price the relay shall advertise for helping the end devices in order to maximize its own utility.

5. Derivation of Pricing Function

The relay determines its price using its initial optimal price, which is calculated using the channel parameters and the cost it will suffer when assisting the end devices. A detailed mathematical derivation of the optimal initial price can be found in [42]. Since the cost experienced by the relay depends on the battery power used by it to fulfil the data demand of the end device, the price is also dependent on the available battery power. Two battery power threshold values were defined for the CF-RS game. The relay increases its price linearly after relaying data to an end device until its battery power reaches the first threshold value, i.e., $B{P}_{t{h}_1}$. From $B{P}_{t{h}_1}$ to the second threshold value, the critical threshold $B{P}_{t{h}_c}$, the price is incremented exponentially, and after $B{P}_{t{h}_c}$, the relay does not participate in the relaying process.

$$f\left(p_{ij}\right)=\left\{\begin{array}{cc}{p}_{ij}+c_{ij}\hfill & B{P}_i\ge B{P}_{t{h}_1}\hfill \\ p_{ij}{e}^{c_{ij}}\hfill & B{P}_{t{h}_1}>B{P}_i>B{P}_{t{h}_c}\hfill \\ \infty \hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(21)

The formulated pricing function is given by Equation (21) and is graphically represented in Figure 3. In Equation (21), $p_{ij}$ is the initial price of relay i for end device j determined using the channel parameters between relay i and end device j, $c_{ij}$ the cost experienced by relay i for providing data forwarding service to end device j and $B{P}_i$ the battery power of relay i. $B{P}_{t{h}_1}$ is the first battery power threshold value until which relay i increases its price linearly and $B{P}_{t{h}_c}$ the critical battery power threshold. The purpose of initially increasing the price linearly is that the end devices can receive assistance from the relays with the best channel conditions providing a maximum data rate. However, as the battery power of the best relays is dissipated beyond $B{P}_{t{h}_1}$, they need to push the end devices towards other relays to conserve their battery power. Thus, beyond $B{P}_{t{h}_1}$ till $B{P}_{t{h}_c}$, the price is incremented exponentially with respect to cost. Another advantage of this formulation of the pricing function is to ensure that each relay gets a fair opportunity to forward data for the end devices, thus resulting in fair utilization of the battery power of relays providing longer service time to the end devices.

The price received by the relay for relaying data provides an instantaneous benefit to relays. The CF-RS game converts this price into credits for the relay, which it can use when it moves away from the AP and cannot directly access the AP, thus giving a long term benefit to the relays. The long term benefit for the relay is given by Equation (22).

$$B_k=R_k-C_k$$

(22)

where k is the relay moving away from the AP and becoming the end device, $R_k$ the data rate device k received as the end device, $C_k$ the cost it bore as the relay and $B_k$ its long term benefit. It is advantageous for a device to provide relaying service only if its long term benefit is greater than zero. This implies that along with being paid for its services as a relay, a device also enjoys receiving data via other relays for the cost it experienced in terms of its battery power when it was a relay. Exchanging of the roles of relays and end devices maintains the flow of credits in the network, providing instantaneous benefit to the relay along with the opportunity to utilize the earned credits, thus giving a long term benefit to the relays.

6. Credit Based Fair Relay Selection Algorithm

The Credit based Fair Relay Selection (CF-RS) algorithm is based on the CF-RS Stackelberg game described in Section 4. In the CF-RS algorithm, for simplification, it was considered that an end device can obtain service from one relay at a time, thus buying all available transmission power from that relay, and also, whenever a relay assists an end device, it will always increase its price in order to compensate for its cost. The CF-RS algorithm is a five stage process as illustrated in Figure 4, where Stages 1 and 3 are run by end devices and Stages 2, 4, and 5 by the relays. Stage 1 is comprised of each end device sending a broadcast message for which it requires assistance for its data transmission and reception. In Stage 2, each relay in range of the end devices runs Step 1 of Algorithm 1 to determine its willingness to help the end devices. The willingness of the relay depends on its available battery power $B{P}_i$ being greater than a critical threshold $B{P}_{t{h}_c}$ and its utility $U_i>0$. The relay calculates its cost for the end device present in the network using the cumulative to instantaneous power dissipation ratio ($\frac{\overline{CB{P}_i}}{CB{P}_{ij}}$). The power the relay will be using to provide the relay service is distance dependent, i.e., $P_{ij}\propto d_{ij}$, and its battery power will be consumed accordingly, i.e., $CB{P}_{ij}\propto P_{ij}$. The relay i then uses Equation (21) to determine the price of its data forwarding service for end device j depending on its battery power $B{P}_i$. The relay then sends an Acknowledgement (ACK) message to the end devices along with the price for its services.

The end device then initiates the relay selection process in Stage 3. Algorithm 2 checks for each relay whether it is in the transmission range of the AP and the end device or not and the end device’s budget to pay for the service from the relay is greater than the price advertised by the relay. The end device then calculates its utility for all the relays that fulfil the criteria of transmission range and available budget. The relay providing the maximum utility is selected as the relay by the end device. The end device updates its budget, subtracting the price it pays for the services, and informs the selected relay. In Stage 4, the relay updates its average battery power consumption $\overline{CP{B}_i}$ and its cost. and the price it receives from the end device is added to its credits $C{R}_i$. The selected relay informs the AP to send the data of end device j to it in Stage 5.

Algorithm 1 Stage 2 of the CF-RS algorithm.

1: Initialization 2: $P_{ij}\propto d_{ij}$,   $\overline{CB{P}_i}=0$,    $C{R}_i=0$,    $U_i=0$ 3: Request received from end device j 4: $CB{P}_{ij}\propto P_{ij}$ 5: Step 1: determination of willingness 6: if$B{P}_i>B{P}_{t{h}_c}$then 7:   $c_{ij}\leftarrow \frac{\overline{CB{P}_i}}{CB{P}_{ij}}$ 8:   Calculate $f\left(p_{ij}\right)$ using Equation (21) 9:   if $U_i>0$ then 10:    Send ACK to end device j along with $p_{ij}$ 11:   end if 12: end if 13: Step 2: accepted as relay 14: $\overline{CB{P}_i}\leftarrow \overline{CB{P}_i}+P_{ij}$ 15: $C{R}_i\leftarrow C{R}_i+p_{ij}$

Algorithm 2 Stage 3 of the CF-RS algorithm.

Received ACK from relays 2: for$i=[1,2,\dots ,N]$do      if $d_{ij}\le T_i\&\&d_{iA}\le T_A$ then 4:    if ${\beta }_j>p_{ij}$ then         $U_j\leftarrow R_{ij}-p_{ij}$ 6:    end if      end if 8: end for     $I\leftarrow max\left(U_j\right)$,     I is selected as the Relay (R) 10: ${\beta }_j\leftarrow {\beta }_j-p_{ij}$     Inform the selected relay $R_i$

7. Simulation Results

To evaluate the performance gains provided by the CF-RS algorithm, in terms of achievable data rate, fair utilization of the battery power of relays, utility gains for relays and end devices and the long term benefit for the relays, the CF-RS algorithm was compared with the best relay selection algorithm ([43]). The best relay selection algorithm employs the Signal-to-Noise Ratio (SNR) as the relay selection criterion, thus repeatedly choosing mobile devices with the best channel conditions as relays for end devices. A fixed relaying cost experienced by the relays was considered for the best relay selection algorithm (constant cost of 0.2, the same as taken in [4]), and the price advertised by the relays is chosen between the cost and a predefined upper limit, such that the price is always greater than the cost. In simulations, for the best relay selection algorithm, the upper limit for price was set to 0.6; whereas for the CF-RS algorithm, the price advertised by the relay was incremented linearly until 20% of its battery power was consumed and then exponentially until its battery power reached 50%, after which it declined the end devices’ requests. A relay can serve more than one end device, and the capacity it can offer was dependent on the number of end devices it was currently serving.

7.1. Effect of Network Topology on the CF-RS Algorithm’s Performance

To analyse the effect of network topology on the performance of the proposed CF-RS algorithm using the formulated pricing scheme, two different topologies were simulated. In the symmetric configuration, there was a uniform distribution of end devices around the relays, and every relay served the same number of end devices. For example, for the symmetric network topology shown in Figure 5a, each relay had approximately two end devices in its close vicinity; whereas in the asymmetric configuration, the end devices were randomly and unevenly distributed around the relays, i.e., some relays were surrounded by more end devices compared to other relays. Figure 5b is an example of an asymmetric topology in which Relay 4 has about six end devices in its close vicinity, Relay 3 has about four and Relays 1 and 2 have two each. The network model depicted in Figure 5 is comprised of five relays and ten end devices. The half semi-circle in Figure 5 represents the distance from the AP beyond which devices cannot directly communicate with the AP owing to poor channel quality. The reason for choosing ten end devices and five relays is to examine the performance of the CF-RS algorithm when there are more end devices in the network than the available relays.

The total average data rate achieved by all ten relays against varying data demand from end devices in symmetric and asymmetric network configurations when best relay selection and the CF-RS algorithm were used is depicted in Figure 6a. Data demand actually represented the percentage of assistance requests generated by the end devices. For example, a data demand of 100% means that in the simulation duration of x number of slots, the end device is asking for data in every slot, and a data demand of 50% implies that during each slot, the probability that the end device requires assistance is 0.5. From Figure 6a, it can been seen that when data demand is small, in both symmetric and asymmetric network configurations, the best relay selection algorithm, as well as the CF-RS algorithm provide approximately the same average data rate to end devices. However, with the increase in data demand, the data rate achievable with the best relay selection algorithm in the asymmetric topology gradually deceased; whereas in the case of the CF-RS algorithm, the network topology did not have a significant impact on the data rate achieved at the end devices. This was because the CF-RS algorithm utilized the ratio of cumulative to instantaneous battery power consumption to determine relaying cost and took into account both the achievable data rate at the end devices, as well as the price advertised by the relays for the relay selection.

Jain’s fairness index [41] was used to determine the fairness of consumption of the battery power of relays when the best relay selection and the CF-RS algorithms were used in the symmetric and asymmetric configuration for relay selection, and this is presented in Figure 6b. In the symmetric configuration, irrespective of whether the best relay selection algorithm was used for relay selection or the CF-RS algorithm, each relay participated in the data forwarding process and served an equal number of end devices. The battery power of all relays was fairly utilized, and Jain’s fairness index of approximately one was achieved, as shown in Figure 6b. However, in the asymmetric topology for the best relay selection algorithm, the fairness index was only about 0.4 (40%) since end devices had a finite relaying budget and they ran out of their budget sooner when the best relay selection algorithm was used. This was because of the fixed cost and price considered for the best relay selection algorithm and also the mobile devices that did not have the best channel conditions did not get the opportunity to be selected as relays; whereas in the case of the CF-RS algorithm, the fairness increased with the increase in data demand from the end devices, since the designed pricing function for the CF-RS algorithm encouraged the end devices to avail themselves of the relaying service from the relays that not only provided the data rate, but also had a lower relaying price.

The average utility gained by the relays by participating in the relaying process for symmetric and asymmetric network topologies is shown in Figure 6c. It can be clearly seen that network topology did not have any significant effect on the utility of relays when the CF-RS algorithm was used for relay selection. However, in the case of the best relay selection algorithm, for the asymmetric configuration, the utility of relays was comparatively very low since the end devices only chose the mobile devices with the best channel conditions as relays and the battery power of these selected relays reached their critical threshold value quickly, after which they could not participate in providing the data forwarding service and thus gained no benefit.

The utility of the end devices depended on the data rate achievable through the relay and the price paid to the relay. In the symmetric topology, the utility of end devices was greater than that achieved in the asymmetric topology, as depicted in Figure 6d, since each relay was serving an equal number of end devices. However, in the asymmetric topology, the utility achieved by the end devices through the best relay selection algorithm decreased with the increase in data demand because of the fast depletion of the battery power of relays with the best channel conditions. On the other hand, the CF-RS algorithm outperformed the best relay selection algorithm in both the symmetric and asymmetric network configuration.

7.2. Exchange of Roles: Long Term Benefit

To demonstrate the long term benefit of the CF-RS algorithm given by Equation (22) and the accumulation and usage of credits earned by a device, a network model with devices exchanging their roles as the relay and end devices was analysed. The network model was still comprised of 15 devices, as presented in Figure 7a, five relays and 10 end devices, and half way through the simulation duration, five of the end devices swapped their roles with the relays. For the ease of presentation, both relays and end devices are represented as D in Figure 7a. To assess the performance of the CF-RS algorithm when such an exchange of roles occurred, two test case scenarios were considered. In Scenario 1, the relays and end devices changed their positions only once, as shown in Figure 7; whereas for Scenario 2, four such exchanges of positions were examined. For both test case scenarios, the CF-RS algorithm was compared with the best relay selection algorithm.

For the test case Scenario 1, the CF-RS algorithm was compared with two different variations of the best relay selection algorithm: the best relay selection algorithm with obedient devices and the best relay selection with selfish devices. The purpose of the comparison was to establish the long term benefit provided by the CF-RS algorithm owing to its credit based mechanism and fair consumption of battery power. The configuration of these two variations of the best relay selection algorithm are given below:

• In Variation 1, for the best relay selection algorithm it was assumed that the relays were obedient devices and did not ask for any price for their services.
• Variation 2 dealt with the selfish relays who asked for a price for their services, but there was no mechanism to ensure fair utilization of the battery power of the relays.

The results obtained when the relays and end devices exchanged their roles for these two variations of the best relay selection algorithm in comparison with the CF-RS algorithm are discussed below.

7.2.1. Variation 1: Obedient Relays

Figure 8a presents the overall benefit gained by the devices who were relays in Position 1 depicted in Figure 7a and became the end devices in Position 2 shown in Figure 7b. The overall benefit of a device depended on the cost it experienced being a relay and the data rate it received being the end device. A simulation duration of 120 slots with a request probability of 50% from the end devices and the exchange of positions occurring after first 60 slots was simulated. Since the relays for the best relay selection algorithm were considered to be obedient, irrespective of whether the devices $D1$, $D2$, $D3$, $D4$ and $D5$ provided data forwarding service in Position 1 or not, they always received assistance when they became the end devices. This was because the devices $D6$, $D7$, $D8$, $D9$ and $D10$ in Position 2 were also obedient devices. Therefore, all five devices $D1$, $D2$, $D3$, $D4$ and $D5$ achieved good positive overall benefit for the best relay selection algorithm as well.

There were five relays in Position 1 (Figure 7a); however, despite the relays being obedient devices, the end devices only availed themselves of the services of $D5$ in case of the best relay selection algorithm. Therefore, in Figure 8b, the service time of only $D5$ is plotted. The service time is the duration in which the relay is assisting the end devices before its battery power reaches the critical threshold value, i.e., 50% of its battery power. From Figure 8b, it can be concluded that the CF-RS algorithm provided approximately 50% longer service time compared to the best relay selection algorithm with obedient relays in this scenario. This was due to the pricing function given in Equation (21), which took into account fair consumption of battery power. The formulated pricing function conserved the battery power of relays with the best channel conditions and provided incentives to both relays to help the end devices and to end devices to buy services from the relays that did not provide the best SNR, but were asking for a lesser price.

The acquisition of credits by devices $D1$, $D2$, $D3$, $D4$ and $D5$ when they were the relays and then the expenditure of these earned credits when these five devices became the end devices are exhibited in Figure 9a. The black vertical line represents the transition when these five devices changed their role from providing assistance to requiring assistance. The flat period in Figure 9a in Position 1 represented that either the device had run out of its battery power or was asking for too high a price that the end device could not afford. In Position 2, the flattening meant that the device exhausted its credits bank or in other words its budget was fully used and it had no more budget to buy the relaying service for itself.

7.2.2. Variation 2: Selfish Relays

In Variation 2, the best relay selection algorithm also offered a price to the relays assisting the end devices irrespective of the cost in terms of battery power consumption they underwent. Figure 9b shows the overall benefit gained by the devices $D1$, $D2$, $D3$, $D4$ and $D5$ when the best relay selection algorithm and the CF-RS algorithm were used for relay selection. In case of the CF-RS algorithm, the benefit was more evenly distributed among the five devices as compared to the best relay selection algorithm. Furthermore, device $D4$ received almost negligible benefit. This was because in Position 1 of Figure 7, in case of the best relay selection algorithm $D4$ had no incentive to help the end devices, thus it earned zero credits and could not avail itself of relaying services when it became the end device in Position 2 of Figure 7. Furthermore, the cost of providing assistance, as well as fair dissipation of the battery power of relays had not been taken into account while determining the willingness of the devices to act as relays in the case of the best relay selection algorithm.

For the test case Scenario 2, the relays and the end devices exchanged their roles four times as depicted in Figure 7 and Figure 10. In Positions 1 and 3 (in Positions 1 and 4) of Figure 7 and Figure 10, devices $D1$ and $D2$ ($D3$, $D4$ and $D5$) were the relays, whereas in Positions 2 and 4 (Positions 2 and 3), they become the end devices. In the test case Scenario 2 of swapping of roles, the best relay selection algorithm with pricing irrespective of the relaying cost for the selfish relays was considered.

Figure 11a displays the overall benefit gained by devices $D1$, $D2$, $D3$, $D4$ and $D5$ swapping their role as the relays and end devices multiple times during the simulation period of 120 slots, twice acting as the relays and twice as the end devices. Even when the devices change their roles multiple times, all devices received a benefit when the CF-RS algorithm was used; whereas the best relay selection algorithm provided a benefit to only $D1$, $D2$ and $D5$ and almost a negligible one to $D3$ and $D4$, thus giving no long term benefit to $D3$ and $D4$ to assist the end devices. Therefore, the cumulative utility achieved by $D1$, $D2$, $D3$, $D4$ and $D5$ when helping the end devices was approximately 80% less than that achieved with the CF-RS algorithm, as depicted in Figure 11b.

8. Conclusions

This paper proposed a Credit based Fair Relay Selection (CF-RS) algorithm for coverage extension of mobile networks with emphasis on the fair power utilization of relays. The CF-RS algorithm based on the Stackelberg game used credits as an incentive to encourage the self-interested mobile devices to provide the relaying service to end devices and employed the ratio of cumulative to instantaneous battery power consumption for relaying cost calculation, thus resulting in fair utilization of the battery power of relays present in the network. The results obtained demonstrated that the CF-RS algorithm performed better than the best relay selection algorithm, which used SNR for relay selection, in terms of achievable data, Jain’s fairness index and the utility of the end devices. The CF-RS algorithm achieved the same performance in the symmetric and asymmetric network configuration. Simulation results also confirmed that the CF-RS algorithm gave enough incentives to encourage the self-interested relays to take part in the data forwarding process and provided long term benefit to all participating devices. Despite the cost experienced when relaying data to the end devices, it was beneficial for a device to act as a relay considering its overall benefit in terms of earned credits, utility and data rate when the CF-RS algorithm was used for relay selection. Future work will be comprised of the performance evaluation of the CF-RS algorithm under different mobility models and the network scenario with high mobility users.