{'fraction_non_alphanumeric': 0.029208604697059402, 'fraction_numerical': 0.006666228099028572, 'mean_word_length': 4.527757575757576, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Novel Relay Selection Algorithms for Machine-to-Machine Communications with Static RF Interface Usage

Machine-to-Machine (M2M) communications have been introduced to improve the communication capacity in dense wireless networks. One of the most important concerns for network designers is maintaining the high performance of the network when the quality of connections between sources and their destinations is poor. Thus the careful selection of relays between data sources and their destinations is a very important issue. The possibility of simultaneous use of different Radio Frequency (RF) interfaces for transmitting data, which communication devices are equipped with them, can increase the capacity of data transmission over the network. In this paper, two novel M2M relay selection algorithms are proposed, named as Optimal Relay Selection Algorithm (ORSA) and Matching based Relay Selection Algorithm (MRSA). ORSA is a centralized algorithm for the optimal selection of relays by transforming the main problem to a k-cardinality assignment problem that can be solved using the Hungarian algorithm. MRSA is a distributed algorithm that leverages concepts from matching theory to provide a stable solution for the relay selection problem. In both proposed algorithms static RF interfaces usage is applied to enable simultaneous use of different interfaces for data transmission. The simulations show that ORSA is optimally solving the relay selection problem. MRSA has an optimal stable result, that when there is no restriction on the number of channels, is only about 1% lower than ORSA. Besides, MRSA provides better results than direct transmission Without any Relay Selection Algorithm (WRSA) and Random Relay Selection Algorithm (RRSA), about 15% and 98%, respectively.


Introduction
Today, the emergence of new applications and new technologies for wireless networks has facilitated human life [1]. Realization of any of these applications needs different requirements such as high capacity, low latency, high data rate and low power consumption [2]. Thus with different Quality of Service (QoS) requirements, the management of the network machines is necessary.
One of the recent communication technologies is Machine-to-Machine (M2M) communication. This kind of communication has to support the different QoS and different requirements of the users in a very dense network. In M2M communications, machines can communicate with each other, without or with minimal human intervention [1,3].
This cooperation between machines in next-generation wireless networks is an appropriate approach to improve the data rate and bandwidth efficiency of the network [4]. In addition, the network coverage of cooperative communications can be improved by utilizing relay nodes in the Long-Term Evolution-Advanced (LTE-A) cellular networks [5]. Therefore, how relays are selected can have a significant impact on network performance and the appropriate relay selection is a challenge to increase network performance [4]. This challenge is referred to as the relay selection problem in this paper.
Due to the high density of machines in M2M networks, each machine only has local information about network conditions. Therefore, in addition to the centralized optimal relay selection in the network, a distributed algorithm can practically help each machine for an appropriate relay selection according to its local information.
In M2M communications, machines can be equipped with different radio frequency (RF) interfaces, such as LTE, Bluetooth, WiFi, or multiple of them simultaneously. Using this feature can increase M2M communication capacity [6]. Due to the high density in M2M communications, simultaneous use of different RF interfaces to transmit data from a machine to other machines and from a machine to a base station can increase network cell transmission capacity.
In this paper, a centralized Optimal Relay Selection Algorithm (ORSA) is proposed. This algorithm uses two steps. The first step is a transformation that converts the relay selection problem to a k-cardinality assignment problem and the second step is another transformation that converts the k-cardinality assignment problem to a standard assignment problem. Then, the standard assignment problem is solved by the Hungarian algorithm.
Although ORSA achieves optimal results, it can create a bottleneck in dense Additionally, it is observed that the number of channels between machines and the base station affects the average capacity of connection between sources and the base station and the number of unmatched sources. For example, due to the constant total available bandwidth for all machines, by reducing the number of channels between machines and the base station, although the portion of bandwidth corresponding to each machine that is connected to the base station increases, the number of unmatched sources increases. In contrast, the fading factor does not affect the average capacity and the number of unmatched sources.
In summary, this paper makes the following contributions: -A novel centralized algorithm is proposed to provide the optimal solution for the relay selection problem. The presented method converts the M2M relay selection problem to a k-cardinality assignment problem.
-A new solution for the k-cardinality assignment problem is proposed by converting it to a standard assignment problem.
-A novel distributed relay selection algorithm using matching theory is provided. This algorithm provides a stable matching between sources, relays and the base station, based on the deferred acceptance procedure [7].
-The parallel usage of different RF interfaces can enable simultaneous transmission among machines and machines with the base station. Therefore, static RF interfaces usage is considered for machines and the base station in the network cell. This static usage of RF interfaces is such that WiFi interface is used for M2M communications and that LTE interface is used for machine to base station communications.
The rest of this article is organized as follows. Related works are described in section II and the system model is described in section III. Then, the proposed centralized relay selection algorithm and the proposed distributed relay selection algorithm are presented in section IV and V, respectively. The simulation results are illustrated in section V. Finally, in section V, the conclusion of this paper is provided.

Related Work
Relay selection may be useful in order to forward data to the base station to deliver to its destination. The network condition parameters, such as Signalto-Noise Ratio (SNR), can be involved in selecting the appropriate relay [4].
Appropriate relay selection can be very important, especially when the direct link between a source and its destination (e.g. the base station) is weak [8] and the network coverage needs to be extended [9,5]. Thus relays can be used to increase network throughput [9]. In this section, some of the previous related works are summarized.
Recently, a relay selection algorithm based on the Basic Sequential Algorithmic Scheme (BSAS) is proposed for high density LTE networks [10]. Two layers of users are considered, in this work. The first layer users are directly connected to the base station and the second layer users use one of the first layer users as a relay to connect the base station. In this algorithm, the users form clusters and each cluster has a cluster head from the first layer nodes. These cluster heads transmit data of all other users in its cluster. The proposed algorithm improves the system capacity and energy consumption compared to other similar work [10].
Another paper provided two new approaches to modify the buffer-aided relay selection algorithms in equal maximum weight link conditions [11]. The authors proposed two metrics to use for this condition in each of the new approaches.
The first parameter is used in one of the approaches is SNR. The results show that involving this parameter in relay selection improves the outage probability.
The other parameter is prioritizing links between relays and destinations based on the occupied buffer space. Involving this parameter in the second approach can improve the delay and throughput performances [11].
In the other work, two relay selection schemes based on two different parameters, Signal-to-Interference Ratio (SIR) or location,for Machine-Type Communication (MTC) are proposed [12]. In this paper, gateways, as relays, receive MTC devices data and transmit it to the base station. In the relay selection based on SIR, gateways attempt to receive data from MTC transmitters that have the highest received power. The possibility of simultaneous data transmission by multiple MTC transmitters in this schema can lead to high interference and reduces the probability of successful data decoding. Furthermore, the data of each MTC transmitter may be received by the base station through multiple gateways. The relay selection based on location modifies the SIR based scheme, by assigning the nearest MTC transmitter to each gateway and farther MTC transmitters blocked by this gateway. Thus despite the cost of sending spatial data by MTC transmitters, the received interference by each gateway is reduced and the duplicate MTC data transmission to the base station is avoided [12].

Hungarian based relay selection
The Hungarian algorithm is a solution for the maximum weighted matching problem in bipartite weighted graphs [13]. Following, a review of Hungarian algorithm based relay selection schemes are mentioned: A relay selection algorithm has been proposed with subchannel reusing in D2D communications [14]. In this algorithm, a graph coloring algorithm is applied to arrange the D2D peers into nonconflicting groups that have minimum intergroup interference. Then a matrix of D2D peers power consumption is constructed, and relay selection of the Device-to-Device (D2D) peers is formulated as a weighted bipartite graph matching problem. In the next phase, this problem is solved by the Hungarian algorithm [14].
A study has been conducted on the effectiveness of relay selection in 3GPP Narrowband networks in Internet of Things (NB-IoT) [15]. To increase the chance of successful transmission, NB-IoT adopts a repetition-based transmission. To reduce the number of repetitions, relay selection can be utilized. In this work, relay selection is modeled as a weighted bipartite matching problem and a solution is obtained using the Hungarian algorithm [15].
The assignment problem and relay selection for the relay-aided D2D communications underlying cellular networks has been studied. It is known that this problem is NP-complete, therefore researchers have proposed an Iterative Hungarian Method (IHM) to obtain a near-optimal solution for this problem [16].
A joint relay selection and resource allocation algorithm is investigated in cognitive networks [17]. In their study, these problems are modeled by bipartite weighted matching in two stages and are solved with the Hungarian algorithm [17].

Matching theory based relay selection
Matching theory can provide an appropriate framework for analysis and designing the distributed methods for interactions between rational and selfish players [18]. Here, some papers that used from the matching theory in relay selection are summarized.
Jointly optimizing resource management, relay selection, spectrum allocation, and power control is an NP-hard problem [19]. A pricing-based twostage matching algorithm is provided to maximize energy efficiency. Firstly, a two-dimensional matching is modeled for the spectrum resources reused by relay-to-receiver links. Then, matching users, relays, optimal power control and the spectrum resources reused by transmitter-to-relay links are conducted by a three-dimensional matching [19].
A distributed satisfaction-aware relay assignment based on the many-to-one matching-game theory is provided [20]. In this work, sources request to relays, with limited resources, regarding their dynamic throughput requirements.
Finally, the satisfaction and fairness of sources have been improved [20].
A distributed matching algorithm to select suitable relays among secondary users for primary users is proposed [8]. The secondary users negotiate with the primary users on the time of both cooperatively relaying the primary users data and allowed spectrum access [8].

System Model
We consider a cell with one base station, and N machines each equipped with at least two different RF interfaces. We consider only the uplink paths.
The machines have fixed positions, and are divided to two sets, active machines (sources) and idle machines (relays). We denote active machines set as M a that includes N s = |M a | sources and each source wants to send data to the base station to deliver its message to its destination. Moreover, the channel between the sources and the base station may have low communication quality, due to fading and shadowing. Therefore, we denote the set of idle machines by M i , which included N r = |M i | relays. In other words, M T otal is considered as a set of machines, such that M T otal = M a ∪ M i and M a ∩ M i = φ. According to what was mentioned, N = N s + N r . It is assumed machines would like to cooperate with each other. The idle machines do not have data to send at that period of time, thus they can work as a relay. Therefore, when active machines need help, the idle machines can assist them as relays to increase data-rate.
The relays are using the decode-and-forward (DF) protocol. Figure 1 shows the scheme of active and idle machines in the system model. The communication capacity between two nodes, i and j, in the network is denoted by C ( i, j), that according to the Shannon-Hartley equation, will be as: where B t is the bandwidth of the communication channel with technology t used by two nodes i and j and SIN R ( i, j) is the Signal to Interference plus Noise Ratio of the channel with ith node as the transmitter and jth node as the receiver.
The possibility of using different RF interfaces of the machines can help to provide high data rates. Therefore, as static RF interfaces usage, we consider a and where P W iF i i and P LT E i are transmission powers of ith node for the WiFi and LTE interfaces, respectively, and σ 2 is noise power and h ( i, j) is the gain of the channel between ith and jth nodes. h ( i, j) depends on path loss model, free space or two ray, according to the distance between two nodes, and shadowing with normal distribution with zero mean and four units standard division. In this model, any source can select a direct path to the base station or a relay for two hop data forwarding to the base station, by using the matching algorithm.
The capacity of the channel between a source and a base station in two hops based on DF relaying is given by [21,22,23]: where C s,r is the communication capacity between the source and the relay and C r,d is capacity between the relay and the base station.

Problem Formulation
In this paper, the aim is finding: -an optimal relay selection that provides the highest capacity for all network sources, -an optimal stable relay selection that provides high capacity for all network sources.
Therefore, we formulate the optimization problem as follows: Max xi,j ,y j,k ,z j,k Subject to the definition of the used variables is as follows:

Proposed Centralized Relay Selection Algorithm
In this section, we propose a centralized relay selection algorithm. To solve the problem (5), we transform our relay selection problem as a k-cardinality assignment problem. Besides, we provide a new solution for k-cardinaltiy assignment problem that finds k maximum weighted matching in a bipartite graph.
The k-cardinality assignment problem can be solved by a polynomial solver [24]. Some papers proposed solutions for this problem [25,26], but we provide a new simple approach for solving it.

A New Solution For The K-Cardinality Assignment Problem
In this section, we provide a solution for the k-cardinality assignment problem, which is a generalization of the standard assignment problem [26]. The k-cardinality assignment problem is defined as finding the maximum weight matching among all matchings with at most k edges in a bipartite graph.
The Hungarian algorithm is a common solution for the standard assignment problems [27], but it can not solve a k-cardinality assignment problem. Therefore, we transform the k-cardinality assignment problem to a standard assignment problem that would be solved by the Hungarian algorithm [28]. The complexity of the algorithm is O(n 3 ) [27,29].
. We want to select k(≤ min{m, n}) number of the edges so that sum of the weights of selected edges is maximized. If k = n or k = m, the new problem will be equal to the standard assignment problem without any constraint on the number of selected edges [25,26]. The scheme of the bipartite graph model of the k-cardinality assignment problem is shown in

4.1.1.
Step 1: Transforming the k-cardinality assignment problem to a standard assignment problem In the first step, we want to transform the assignment problem with the constraint on the number of edges to a standard assignment problem. In the standard assignment problem, we are looking for a set of edges in the bipartite weighted graph with the maximum total weight. Now, we are going to transform the restricted problem into an unconstrained one, so that the results coming from both problems would be corresponding to each other.
For this purpose, we add some additional vertices to each side. The number of vertices that are added to each side is equal to the difference between the size of another side, m or n, and constrained number of edges, k. On other words, we add n V A = m − k vertices to V side and n U A = n − k vertices to U side. The weight of edges connected to new vertices is equal to 0 with another new vertices on the other side and infinite or maximum total weight, A value , with the initial vertices on the other side. Intuitively, adding new vertices and their edges by this method causes the lower weight initial edges to be defeated by A value -weighted edges. Therefore, only k initial edges with maximum total weight can be selected in the optimal assignment. Now, we can find maximum weighted matching in the new bipartite graph by the Hungarian algorithm. Figure 4 shows the transformation of a k-cardinality assignment problem to a standard assignment problem. Theorem 1.

Discussing and analysis of the final results
Problem (16) is the mathematical formulation of finding a maximum matching with k-cardinality (k edges) in a weighted bipartite graph. The purpose of the discussion in this subsection is to prove that the method presented in Section 4.1 provides an optimal solution for problem (16).
where S se is the set of selected edges of the original problem.
The transformation to problem (17) can be summarized as adding new vertices with 0-weighted and A value -weighted edges to each side. It is proved that the optimal solutions of the transformed problem (17) are in one-to-one correspondence with the optimal solutions of the original problem (16).
where n As is the number of selected A value -weighted edges and S se is the set of selected edges of the transformed problem.
Lemma 1. For maximization of the problem (17), the number of selected A valueweighted edges, or n As , is a constant value and n As = (m − k) + (n − k) .
Proof : It is demonstrated by contradiction.
Step 1-We assume n As < (m − k) + (n − k) and the summation of edge weights is equal to w sum . Therefore, at least one of the new vertices does not connect to the initial vetices with a A value -weighted edge. Accordingly, for maximization the problem (17), we can replace at least an A value -weighted edge with the lowest weight edge (w min ). Hence, the new summation of edge weights is greater than or equal to w sumnew = w sum − w min + A value . Since A value > w min , thus w sumnew > w sum . Now, we reach a solution with n As ≥ (m − k) + (n − k). This number of A value -weighted edges contradicts the initial assumption. Therefore, n As ≮ (m − k) + (n − k).
Step 2-Now, we assume n As > (m − k) + (n − k). But, it is impossible, because, we have only (m−k)+(n−k) new vertices in total. Hence, we can have up to (m − k) + (n − k) of A value -weighted edges. It contradicts the previous assumption. Therefore, n As ≯ (m − k) + (n − k).
Hence, it can be concluded that the number of A value -weighted edges is equal Now, we rewrite the problem (17) to the problem (18).
where n * As = (n − k) + (m − k) is the number of selected A value -weighted edges for optimization of the problem (17), S se is the set of selected edges of the transformed problem and E A is the set of A-weighted edges.
Theorem 1. Each answer to the k-cardinality assignment problem corresponds to the answer to the transformed standard assignment problem and vice versa.
Proof : We consider the set of optimal solutions of the problem (16) is equal to S and the set of optimal solutions of the problem (18) is equal to S * . Each solution has up to m + n − k edges. According to Lemma 1, n * A is a constant number and is equal to (n − k) + (m − k). Hence, the number of edges other than A value -weighted edges is equal to k. Therefore, -If S * wants to be constructed of S, it is enough that n * A Selected A valueweighted edges from the unassigned initial vertices are connected to the new vertices. Hence, the obtained edges are the S * solution, and the number of them is equal to m + n − k, and -If S wants to be constructed of S * , it is enough that n * A Selected A valueweighted edges are removed and the k remaining obtained edges are the S solution.

Proposed Centralized Optimal Relay Selection Algorithm
In this section, an optimal relay selection problem is solved. Thus we transform this problem in two steps to become a k-cardinality assignment problem.
In the following, the optimal relay selection problem-solving process is described.

4.3.1.
Step 1: Transform our optimal relay selection problem to a k-cardinality assignment problem The configuration of our relay selection problem is shown in Figure 2. As it can be seen in this figure, we have two sets of machines, the sources and the relays. The sources want to connect to the base station directly or by using a relay.
In the assignment, between the sources and relays through the original problem, each source can connect to only one relay and each relay can connect to only one source. Besides, the base station has Q BS channels for communication with the machines, whether a source or a relay. The conditions of the channels are considered similar. On the other words, each source or relay can connect to only one of the channels of the base station, and the base station can connect to up to Q BS machines. Therefore, in the final assignment, the total number of edges connected to the base station can be equal to Q BS . Now, we want to transform the graph model of our problem that is shown in Figure 2 to a bipartite graph. We consider each channel of the base station such as a relay. That way, we have a bipartite graph that one side is related to the sources and the other side is related to all the next hops. The bipartite graph model of the relay selection problem is shown in Figure 6. The weight of the edge between two vertices on both sides of the graph is defined as follows: -the weight of the edge between a source and a relay is equal to the capacity of two hops path, that is minimum of the capacity of the source and the relay link and the capacity of the relay and the base station link, and -the weight of the edge between a source and each channel of the base station is equal to the capacity of the source and the base station link.
As mentioned, the original problem had the constraint of having at most Q BS connections from the machines to the base station. This constraint is modeled by the selection of at most Q BS edges in the bipartite graph assignment problem.

4.3.2.
Step 2: Transform our k-cardinality assignment problem to a standard assignment problem without edge number constraint We want to find Q BS edges that maximize their total weight in the new problem. The current problem is similar to the problem mentioned in Section 4.1.1. Therefore, it can be solved in the same way. source connects to the base station directly. Finally, the last situation indicates that the ith source can not connect to any next hop of the network.

Proposed Centralized Algorithm
This section describes how to implement the algorithm of transformation of our optimal relay selection problem to a standard assignment problem, we construct a capacity matrix in two steps. To achieve this goal, in the first step, the first part of the matrix is filled by the link capacity of the sources and the relays and each of the base station channels. Hence, we have a capacity matrix of the new k-cardinality assignment problem. Then, to transform our k-cardinality assignment problem to a standard assignment problem, the rest of the matrix cells are filled by A value , that A value > M ax( cells in the f irst part matrix).
For example, A value can be equal to (max(M i,j ) + 1) × (N r + N r ). Now, to find the optimal assignment, the provided capacity matrix is given to an assignment problem solver such as the Hungarian algorithm. Since the Hungarian algorithm can be implemented in two different versions, one of which is used by default to find the maximum weighted matching and the other to find the minimum weighted matching. Therefore, if the Hungarian algorithm is implemented to find the maximum weighted matching, the capacity matrix and the number of vertices on each side are given as its inputs. Otherwise, If the Hungarian algorithm is implemented to find the minimum weighted matching, the negative matrix capacity and the number of vertices on each side are given as its inputs.
Finally, the desired output can be obtained from the output of the Hungarian algorithm using the method described in Section 4.3.3. The pseudo code of our proposed centralized matching relay selection algorithm is presented in Algorithm 1.

Proposed Distributed Matching Based Relay Selection Algorithm
In this section, we propose a distributed algorithm for relay selection with matching theory to select an optimal stable selection. First, we describe the matching theory elements, the proposed algorithm players and their preference lists. Then, the matching algorithm is presented to find an optimal stable solution for the problem (5).

Matching Theory
The matching theory is a framework to model interaction between rational and selfish players. We are mapping our problem to a matching theory problem.
Some elements of our matching problem are mentioned below.

Algorithm 1 Proposed Centralized Optimum Relay Selection Algorithm.
Step 1: Transform our optimal relay selection problem to a k-cardinality assignment problem 1: Construct the first part of the input capacity matrix of the standard assignment problem, Mi,j , according yo the following rules: -Mi,j = min(Cs,r, C r,BS ) for (0 ≤ i < Ns) and (0 ≤ j < Nr), -Mi,j = C s,BS for (0 ≤ i < Ns) and (Nr ≤ j < Nr + Q BS ), Step 2: Transform our k-cardinality assignment problem to a standard assignment problem

10:
else if H o i ≥ Nr + Q BS then -Oi = φ: It means that the ith source can not assigned to the base station.

The Players
In our proposed algorithm, there are two types of players defined as follows: • Machines consist of sources and relays, • Base station.
In other words, each machine or the base station in matching algorithm are the rational and selfish players that they want to maximize their communication capacity.

Utility Function
The Utility function of machines and the base station in our algorithm is based on the capacity of the paths between the machines and with the base station. As previously mentioned, the capacity of direct and two hop paths are formulated by the equation (1) and the equation (4), respectively.

Preference Lists
The preference lists of machines or base stations are formed according to the node utility functions computed by received channel information between the node and its neighbors.
• Each source has a preference list of its neighbor relays and base stations as their candidate next hops.
• Each relay has two preference lists of its neighbors. The first list, or list of the candidate next hops list, ranks its neighbor base station as next hop for data forwarding of applicant sources. The second list, or the list of the previous hops, rank applicant sources that requested to this relay.
For simplicity, in the proposed algorithm, the size of the second list is considered to be one.
• Each base station has a list of its neighbor applicant sources and relays that requested it.
We show the preference list of their candidate next hops of the machines by P L N H and the preference list of the applicants of the base station and the relays by P L AP .
Any source or relay sort candidate neighbors in the next hop preference list according to capacity in the path consist of this hop. Moreover, any relay or the base station sort the list of applications according to the capacity of the path traversed from that node.
In the following, we study the proposed distributed relay selection algorithm players and the preference lists.

Proposed Distributed Algorithm
Due to the high density of M2M communications, each machine can have local information from its neighbors. In this regard, a distributed algorithm for relay selection can be suitable for this type of communication. The main idea of the proposed distributed algorithm for each source is finding an optimal stable matching to select a suitable path, direct path or two hop path, to the base station to reach its data to the destination. To achieve this aim, this algorithm provides a stable best relay selection.
The weak channel between sources and the base station causes a low data rate in the direct path of sources and the base station. Hence, if a relay is selected as a next hop of a source, the selected neighbor relay has two features.
First, it has enough connection capacity and second, the path containing that relay has a higher data rate than the rate of the direct path between the source and the base station and it has an equal or higher data rate than the rate of the paths containing other neighbor relays with enough capacity.
For simplicity, we assume the machines can synchronize with each other, so the algorithm continues until no unmatched source remains. This time is known as the matching time. No machine forward its data to the destination at this time.
At the beginning of the matching time, the relays send estimated capacity with the base station, according to the estimated signal to interference plus noise ratio (SINR) with it. Therefore, the sources can sort the candidate next hops, the relays or the base station, according to estimated SINR. Furthermore, in the initialization section of the algorithm, the machines construct the preference list of their candidate next hops (P L N H ) and the base station and the relays construct the preference list of their applicants (P L AP ). Then all of the sources add to MATCHLIST. Thus any unmatched machines in MATCHLIST sort its candidate next hop, according to channel conditions with its neighbors and received information from them, in the beginning of the matching time.
In step 1, any unmatched machines in MATCHLIST request to the first candidate next hop with the best capacity. On the other hand, each node receiving the request, a relay or the base station, has a given quote. The quota for the base station is equal to LTE channel number and for the relays is equal to one. Therefore, any receiver node accepts to a maximum of its quota from the best applicant machines and rejects other machines. If a relay that receives a request from a source, does not have its specified next hop, it should be added to MATCHLIST to be specified its next hop. Besides, if the relay does not find any next hop, will reject its applicant sources. Then, if an unmatched machine is rejected by a relay or the base station, requests to the next its best neighbor.
It continues until no machine remains in MATCHLIST. Then, in step 2, any nodes match with final best candidate in preference lists of next hops or applicants. The Algorithm 2 presents the psudo code of our proposed distributed matching based relay selection algorithm (MRSA).

Features of algorithms based on the Matching Theory
This prpopsed distributed algorithm is based of the deferred acceptance procedure. It is proved that the result of this algorithm is a stable solution [7].

Stable Result
We claim after finishing this algorithm, the achieved matching result will be stable.
(Definition: In a stable matching, there are no two nodes that they want each other but they match with another node.) Proof : It is demonstrated by contradiction. We assume the proposed matching result is not stable, so there are two nodes, for example, i and j, that prefer each other to the current matched node. Therefore, applicant node i, before requesting to the current matched node, has requested to node j and node j rejected node i. This means that node j prefers current matched node to node i. Thus it is a contradiction and the provided matching is stable.
It is important to note that in order to achieve stability in this procedure, it is necessary that the device's priority is not the same when selecting a path.
In our scenario, according to a random location and channel condition between

Algorithm 2 Proposed Distributed Matching Based Relay Selection Algorithm:
Initialization and Step 1.
Step Step 1: Find a suitable next hop for each source 1: while MATCHLIST = φ 2: The first m, (or mnew), in MATCHLIST request to first element in P L N H (the acceptor shown by N Hcurr)

3:
if N Hcurr has connection capacity then 4: -Add mnew to P L AP of N Hcurr,

5:
if N Hcurr ∈ M i and N Hcurr does not exist in MATCHLIST then

7:
else if mnew demand capacity > the current m with minimum capacity (or m min curr ) demand capacity then

9:
-Delete it from P L AP of this next hop,

10:
-Delete N Hcurr from P L N H of m min curr ,

13:
-Add it to P L AP of N Hcurr,

15:
else if mnew demand capacity ≤ m min curr demand capacity then

17:
-Delete N Hcurr from P L N H of m min curr .

21:
if mnew ∈ M i then

22:
-Delete all of ms in P L AP of mnew.
devices, the probability of equal capacity between two devices is near to zero.
Therefore, it does not hinder the proof of the stability of the problem.
Step 2: Finish matching section and Start data forwarding

Optimal Stable Result
Moreover, we claim the provided stable matching is at least better than other stable possible matchings.
(Definition: The possible matching between an applicant node and another node means that there is at least one stable matching between them.) Proof : By induction, it is assumed a point that any applicant node does not have rejected by the possible recipient node, like R. In this point, any recipient node keeps q, (q is quote of the recipient node), of the best requests, such as r 1 , ..., r q , and other requests, such as r k , is rejected. Now, we must prove that r k is impossible for R. It is clear that each of r i prefers R to another recipient node that rejects r i . Therefore, the other recipient nodes are impossible for r i . Now, we assume a result that r k matched with R. Hence, one of the r i s that has a lower preference than another r (j =i) , rejected by R. But it is unstable matching because the r i prefers R to other possible recipient nodes and R prefers r i to r k . Thus R is impossible for r k . Therefore, the provided result is an optimal stable matching.
In the following, we investigate the simulation results of the proposed algorithms in comparison with the direct transmission of data without a relay selection algorithm, as well as a completely random selection algorithm.

Simulation Results
To evaluate the performance of the proposed relay selection algorithms, we simulate our algorithms in a square environment, 590×590 (m 2 ). In this square, N machines are randomly placed with uniform distribution. Because of the random nature of the scenarios, the algorithm runs n = 100 times and the average value is provided by considering these runs. In each run, the number of sources is constantly N a , and the rest of the N i machines relays, where The simulations are implemented in the C++ language. The simulation parameters are given in Table 1.
We In RRSA, each source selects its next hop completely randomly only once among all the relays and the base station. If the source selects a relay, and the relay is unable to communicate with the base station for any reason, such as lack of connection capacity or inability to communicate with the base station, the source will not change its selected choice. Additionally, if the source selects the base station, and it can not communicate with the source, the source will not change its selected choice.
It is necessary to mention, that to simplify our simulations, we consider maximum interference on both types of RF interfaces, WiFi and LTE, in SINR calculations. This means that the worst possible scenario is considered, so the results of the real world scenario can be more accurate than our simulation results. Table 1 provides the default parameters in our simulations. In the following, we compare the algorithms in different aspects and investigate the impact of some different parameters by changing the default values of parameters in the different scenarios that are discussed below.
The different scenarios are described below: • Scenario 1: The aim of this scenario is to compare all algorithms when

Length of Test Environment 590m
Width of Test Environment 590m the total number of network machines is constant and the number of relays and sources change proportionally.
• Scenario 2: In this scenario, all algorithms are compared where the number of relays is constant and the number of sources is varied in a specific range.
• Scenario 3: The impact of changing the relay number for ORSA and MRSA is investigated in this scenario.
• Scenario 4: The impact of changing the number of the base station LTE channels for ORSA and MRSA is investigated in this scenario.  Table 2.

Unmatched Source Number
As proposed centralized relay selection algorithm. In this algorithm, we transform the relay selection problem to a standard assignment problem in two steps. Each step has a complexity is equal to O(n). But solving the standard assignment problem using the Hungarian algorithm, can be implemented in O(n 3 ) complexity [27,29]. Therefore, the complexity of ORSA is equal to O(n 3 ).
-MRSA can be implemented in a distributed way for each source.
We applied the deferred acceptance procedure [7] to implement this algorithm. At worst case, if the number of sources and the number of relays are of order n, all sources will request to all relays. Hence, the complexity will be O(n 2 ).
The algorithms can be ordered as ORSA, MRSA, WRSA and RRSA, in terms of the average capacity, according to Figure 8. However, in terms of complexity, WRSA and RRSA, have lower complexity than MRSA and ORSA, respectively. Therefore, these algorithms possess a trade off between the better average capacity of sources and lower complexity and vice versa.

Scenario 2
This scenario is similar to Scenario 6.1 with a large enough constant number of LTE channels and the number of sources is varied in a specific range. But, it has a fixed number of relays. In the following, each of the four algorithms is compared under the same conditions as in Table 3.

Unmatched Source Number
As in the previous scenario, when there is no restriction on the number of LTE channels, the number of unmatched sources of WRSA, ORSA and MRSA are zero or nearly to zero. Besides, the presence of more relays in this scenario compared to Scenario 6.1 connects more sources to the base station in two hops and increases the average capacity of sources.
As a result, in RRSA, the number of unmatched sources reduces that is observable in Figure 11.

Scenario 3
The purpose of simulating this scenario is to investigate the effect of changing the number of relays on both ORSA and MRSA. We simulate ORSA and MRSA according to the parameters in Table 4.

Capacity
The results is shown in Figure 12 state that for each of ORSA and MRSA, in the equal condition a greater number of relays, because they connect more sources to the base station, yields in a higher average capacity of sources in the network. As expected, similar to Scenario 6.1, ORSA results are slightly better than MRSA in the absence of channel constraint. The average standard deviation on all runs of ORSA and MRSA results are equal to 0.03 in all cases.

Unmatched Source Number
As shown in Figure 13, due to no constraint on the number of LTE channels, all of the sources can connect to the base station and the number of unmatched sources is zero for both the ORSA and MRSA algorithms in all cases.

Scenario 4
In this scenario, we want to evaluate the influence of changing the number of the base station LTE channels for ORSA and MRSA. Other parameters of this scenario are listed in Table 5.

Capacity
The results of the simulation of this scenario are presented in Figure 14. These curves illustrate the following observations: -Regarding the fact that the total LTE bandwidth has a constant value (20M Hz as stated in Table 1), a lower number of channels causes a greater capacity portion for each source. The optimal results show that despite a lower channel number in total, the ORSA-25 channel curve has the highest average capacity. -Unlike previous scenarios, in this scenario, the channel number constraint caused a more significant difference between ORSA and MRSA.
In other words, the lower the number of channels, the greater the difference between the optimal result and the optimal stable result, and stable matching of MRSA is no longer close to the optimal result of ORSA.
The average standard deviation of the average capacity when the number of channels are 25, 50 and 75 are equal to 0.04, 0.03 and 0.03 for ORSA and 0.09, 0.04 and 0.03 for MRSA, respectively.

Unmatched Source Number
As it can be seen in Figure 15, when the base station has a fewer LTE channel numbers to communicate with machines, thus reducing the number of sources able to communicate with the base station and increasing the number of unmatched sources. The simulation results also show that in both ORSA and MRSA, the number of channels available to the sources determines the number of sources that can be connected to the base station, and the remaining sources over the number of available LTE channels are not matched. For example, when the number of LTE channels is equal to 25, until the number of sources in the graph is less than or equal to 25, there are no unmatched sources. But when the number of channels exceeded the number of channels available, additional sources can not match.
Therefore, regardless of the type of relay selection algorithm, since the number of LTE channels of the base station determines the number of machines that can be connected to the base station, the restriction of the number of LTE channels directly affects the number of unmatched sources.

Scenario 5
In this scenario, the impact of changing the fading factor for ORSA and MRSA is investigated. As mentioned earlier, the fading factor is used to indicate channel attenuation between the sources and the base station. The parameters used in this scenario are presented in Table 6.

Unmatched Source Number
The number of unmatched sources, as well as the average capacity, is independent of the fading factor. So, this value is equal for all cases and depends on the number of channels available for base station communi-cation. The results for the number of unmatched sources in this scenario are shown in Figure 17.

Conclusion
In this paper, two novel algorithms are proposed for relay selection in M2M communications. The first method is a centralized algorithm to find the optimal relay selection. ORSA is implemented by two transformations. Throughout this algorithm a new solution for the k-cardinality assignment problem is provided.
The second method is a distributed Matching based Relay Selection Algorithm (MRSA). This algorithm is designed based on concepts from the matching theory. The result of MRSA is a stable solution for relay selection. In all of the algorithms, static RF interfaces usage is considered to allow the parallel use of interfaces for data transmission. This type of simultaneous usage can help to improve the performance of the network. In future, a dynamic RF interfaces usage can be considered in the design of the relay selection method The results show ORSA has the optimal average capacity, providing solutions about 1% higher than MRSA, when there is no restriction on the number of channels. Following ORSA, MRSA leads to solutions with average capacity higher than WRSA and RRSA, about 15% and 98%, respectively. Moreover, the comparison of both proposed algorithms with WRSA and RRSA, shows that ORSA and MRSA are more successful in increasing the average capacity of connections between sources and the base station and decreasing the number of unmatched sources.