# Channel Allocation Policy for Distributed Wireless Network: Derivation and Analysis of Optimal Interference

Authors: Amulya Bhattarai; Prapun Suksompong; Chalie Charoenlarpnopparut
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Distributed wireless networks with smart users (independent and rational) are becoming popular, and researchers are studying distributed equilibrium solutions like Nash Equilibrium (NE) to analyze and predict the convergence of such networks. Our goal is to drive the distributed wireless network to NE with high total throughput. Study of the distribution of network metrics at NE with high total throughput shows that communication links still have significant amount of interference. Adding an interference-received term with an optimal weight (αopt∗) to the link’s payoff can push the distributed network to converge to NE with high total throughput. The channel allocation trend at NE with high total throughput is as follows: each of the C−1 links occupies its own channel, and the remaining N−C+1 links share the remaining one channel, where N is the number of links and C is the number of channels in the network. The links (transmitters and receivers) are randomly located and C<N (limited resources). The transmitter of a link has a direct connection with the receiver of the link; hence, several links overlap. This leads to a dense network with considerable amount of interference especially for links sharing channels. A practical application of our work is when smart devices in a room, hall, or concert arena have a direct communication with other smart devices in the area using limited bandwidth. Using best response technique and definitions of NE, we derive and propose an approximate way to mathematically express αopt∗ (referred to as α^opt) along with its probability density function (PDF) for a specific scenario. Then, a generic equation for α^opt is inferred for varying network sizes (links) and available resources (channels). Implementing such a policy enhances the total throughput of the distributed wireless network by up to 15%. In a more general setting, our distributed policy can achieve up to 75% of the maximum total throughput (benchmark value reached by centralized solution via exhaustive search) at a fraction of the time and computation resources.


---

## Body

## 1. Introduction

Wireless communication and networking is expanding exponentially [1]. Scientists are exploring new techniques to keep up with the escalated traffic. Various technologies in mobile communication (3G, 4G, and 5G) [2], wireless LAN (WiFi) [3], and personal area networking (Bluetooth) [4] are catering to the need of the present wireless communications, but new innovations and techniques are essential to meet up with the future trends and ever growing demand [5].Fixed Resource Allocation (FRA) of power, spectrum, and transmission protocols are inefficient [6] as only a fraction of the allocated resources is utilized by the designated users. By dynamically allocating the resources, the smart radios can enhance the efficiency of the network by several folds in comparison to FRA [7]. Intelligent radios are capable to sense the environment, reason based on the observations made [8], and adopt their transmission parameters to get higher efficiency and performance [9]. In this work, we focus on dynamically allocating the channels (spectrum) to the intelligent wireless users [10].As radios are becoming more intelligent and have greater computational power, distributed networks are becoming popular [11]. Several, mobile devices may connect and share information with each other via Bluetooth or WiFi in the absence of a central entity [4]. Generally, in a distributed network, each user independently makes the decision [12], i.e., each user acts selfishly to maximize its own payoff [13]. Although a central agent might ordain a global optimal strategy to these users, they will mostly drift away by choosing strategies that enhance their own payoff, consequently resulting in a lower overall network performance compared to the global optimal [14]. Centralized solutions via exhaustive search technique result in maximum total throughput; however, it requires massive amount of resources (computation and time) especially in larger networks. Hence, many networks like ad hoc and device to device (D2D) prefer decentralized solutions [15].Nash Equilibrium (NE) is a natural and eventual equilibrium state, which the independent and selfish users converge to in distributed scenarios [16]. As each user tries to enhance its own payoff in every iteration, after considerable amount of iterations, the system converges to a Nash Equilibrium (NE). Depending on the starting point, the definition of a user’s payoff, network size, resources available, etc., the system can converge to NE with varying performance [17]. We want to converge to a NE with high total throughput [18].Several research groups have used game theory techniques to address the resource allocation problem in wireless distributed networks. The authors in [17] have defined the user’s payoff to be the individual throughput. This is a distributed system and there is no information exchange between the users, but mostly, the system converges to NE solutions with poor performance [19]. In [20] the authors have defined the user’s payoff to be the total throughput of all users to emulate a centralized system where each user works to maximize the total performance of the network. The performance is high; however, each user needs to know the throughput of all other users which is not viable for a practical distributed network. In [21], the authors have defined the user’s payoff to be the received power minus interference received plus interference created to other users. The objective is to increase the received power and to minimize the interference received from other users and the interference a user generates to other users [22]. Here, the resource allocation schemes are performed in a distributed way, but complete information exchange among the users is essential, and the performance is only slightly better than its predecessors.In [23, 24], the characteristics of the network metrics, link distance, individual throughput, and interference from/to, were studied. It was found that adding an optimal amount of interference-received term in the user’s utility, the distributed wireless network can be driven towards NE with high total throughput [18]. There, αopt∗ is the optimal weight of the interference-received term for a specific network which is determined by running many random simulations for step size variations of α. In this work, we mathematically derive an approximate expression of αopt∗ (referred to as α^opt) along with its probability density function (PDF), for a random “10-link 4-channel” scenario. Then, a generic equation of α^opt for an “N-link C-channel” scenario is inferred based on the trend of different network sizes. In our work, the links (transmitters and receivers) are randomly located and C<N (limited resources). The transmitter of a link has a direct connection with the receiver of the link; hence, several links overlap. This leads to a dense network with considerable amount of interference especially for links sharing channels. A practical application of our work is when smart devices in a room, hall, or concert arena have a direct communication with other smart devices in the area using limited bandwidth. Implementing the policy enhances the total throughput of the distributed wireless network by up to 15%, and it can achieve up to 75% of the maximum total throughput (the benchmark value reached by the centralized solution via exhaustive search technique) at a fraction of time and computational resources.In Section2, the system model of our distributed wireless network is explained. In Section 3, game theory is analyzed in detail. NE with high total throughput is defined, and how distributed solutions with high total throughput can be achieved by inserting the optimal weight (αopt∗) of the interference-received term in the utility is explained. Section 4 mathematically derives the policy (α^opt) from NE with high total throughput constraints for a “10-link 4-channel” scenario and extends to incorporate a generic solution for varying network sizes and available resources. Section 5 compares the results from centralized and distributed networks. Using various illustrations, it is shown how implementing our policy enhances the performance of the distributed wireless network. Section 6 concludes the work.


## 2. System Model

This section discusses the main components of the model. Initially, the links (pairs of receivers and transmitters) and channels in our model are described. Then, calculation of the received power, interference, and throughput at the links and network is explained.


### 2.1. Links and Channels

In our wireless network, there areN links. Each link comprises of a transmitter (Tx) and a receiver (Rx). There are i∈1,2,⋯,N transmitters and j∈1,2,⋯,N receivers. Linkj comprises a transmitter Txi which has a direct connection with a receiver Rxj where i=j. We assume that the maximum communication distance of Linkj is the entire network area. For example, Link1 is the communication between Tx1 and Rx1. Figure 1(a) shows a network with 10 links (N=10) and 4 channels (C=4). Symbols “∗” and “o” represent the Txi and Rxj, respectively. We can observe that several links overlap creating a dense network with considerable amount of interference especially for links sharing channels. The coordinates of the Txi and Rxj are randomly and uniformly generated inside an area of 10 units by 10 units.Figure 1
Distributed wireless network: random, “10-link 4-channel” scenario. The 10 links use a random channel configuration (initially) of “2124342234” (Link1, Link3, Link7, and Link8 use channel “2”).
(a)
There are a total of 10 links which share 4 channels (Link1 is the communication between Tx1 and Rx1 which is using channel “2”). The coordinates of the Txi and Rxj are randomly and uniformly generated(b)
The SINR ofLink1 is the ratio of signal power (from Tx1 equaling 1/d112) over the interference power (from Tx3, Tx7, and Tx8 equaling 1/d312+1/d712+1/d812) and noise power. These links use channel “2”Limited resources are available in the wireless network, and hence, channels need to be shared by the links. The resources allocated toN links are C channels. An interesting case is when there are less channels than the number of links: C<N. A practical application of our work is when smart devices in a room, hall, or concert arena have direct communication with other smart devices in the area using limited bandwidth. We assume each link can occupy only one channel at a time.


### 2.2. Mathematical Formulations

The power at the receiver from a transmitter, using the free space ideal propagation model, can be expressed as(1)Pr=GrGtPt4πd/λ2=Ad2,where Gr and Gt are the antenna gain at the receiving and transmitting sides, respectively. Pr and Pt are the power at the receiver and transmitter, respectively. The distance between the transmitter and the receiver is d, and λ is the wavelength of the electromagnetic wave used in the communication system [25]. In our work, the transmission power of all antennas and the gain of the antennas are constant. Similarly, as we are operating in a narrowband spectrum, we consider the wavelength of the electromagnetic wave used in the wireless network to be constant. These constants are combined into one constant A. Since the main idea is to explore the received power with the variation of the link distance, without loss of generality, we normalize A to unity. The received power at Rxj from Txi can then be simplified to(2)pij=1dij2,where dij is the distance between Txi and Rxj. In order to avoid very high or infinite values of pij when the distance is very small, we consider the minimum value of dij to be 1 [26], avoiding near-field effects [27].Then, the Signal to Interference plus Noise Ratio (SINR) ofLinkj is(3)SINRj=pij∑j=1Npij+σn2=pijIjfrom+σn2wherei=j,samelink,i≠j,differentlinks.In Equation (3), σn2 is the noise power and ∑j=1Npij is the total interference received from other links to Linkj denoted as Ijfrom. The equation assumes all links share the same channel; however, only a certain number of links share a channel and there is interference only between links sharing the same channel as illustrated in Figure 1(b). SINR1 equals the ratio of the power of the signal (due to the Tx1 which equals to p11=1/d112) over the power of the interference and noise. The random channel configuration (initially) used in Figure 1 is “2124342234” (first number signifying the channel used by Link1 and henceforth). Link1, Link3, Link7, and Link8 use channel “2.” Hence, for Link1, there is interference from Tx3, Tx7, and Tx8 which equals to I1from=1/d312+1/d712+1/d812. In this work, to make a concrete example, noise power (σn2) is arbitrarily set at 0.001, which is 30 dB smaller than the transmit power.The throughput ofLinkj based on Shannon Capacity [28] with AWGN channel and SINRj [29] is expressed as(4)Tj=log21+SINRj.Here, the throughput is in bit/s/Hz, i.e., the throughput is normalized over the bandwidth.The total throughput of a wireless network withN links is the sum of all the throughput of N links,(5)Ttot=∑j=1NTj.Ttot varies as different links choose different strategies which will be further explained in Section 3. We define, Ttotmax to be the maximum Ttot from all the different possible pure strategies obtained by exhaustive search of a random scenario.


### 2.3. Assumptions

Four notable assumptions have been made in this work, while focusing on distributed wireless networks, which are as follows:First, the links compute the resource allocation schemes themselves in a distributed way and choose the strategies independently.Second, the links are rational and selfish. Links will choose the strategies in order to increase their own payoff. In our work, utility is defined as in Equation (7) signifying a noncooperative network with independent and selfish users.Third, there is no information sharing between links. Each link can measure the received power and interference it receives from other links assuming the number of links and channels available in the network are broadcasted in the beacon signal, like in cellular or WiFi networks [30].Fourth, good error control techniques are implemented in the links. A system model as mentioned in Section2.1 leads to a dense network with a significant amount of interference. In particular, links sharing channels face considerable amount of interference. We assume the links have good error control techniques which allow them to communicate with some small bit rate even in the presence high interference (as per Shannon’s formula, Equation (4)). Over iterations, links could find other channels that have lower interference and decide to transmit at increased data rate as well.Based on the system model and assumptions stated above, channel allocation policy in our distributed wireless network will be analyzed using game theory in the next section.


## 2.1. Links and Channels

In our wireless network, there areN links. Each link comprises of a transmitter (Tx) and a receiver (Rx). There are i∈1,2,⋯,N transmitters and j∈1,2,⋯,N receivers. Linkj comprises a transmitter Txi which has a direct connection with a receiver Rxj where i=j. We assume that the maximum communication distance of Linkj is the entire network area. For example, Link1 is the communication between Tx1 and Rx1. Figure 1(a) shows a network with 10 links (N=10) and 4 channels (C=4). Symbols “∗” and “o” represent the Txi and Rxj, respectively. We can observe that several links overlap creating a dense network with considerable amount of interference especially for links sharing channels. The coordinates of the Txi and Rxj are randomly and uniformly generated inside an area of 10 units by 10 units.Figure 1
Distributed wireless network: random, “10-link 4-channel” scenario. The 10 links use a random channel configuration (initially) of “2124342234” (Link1, Link3, Link7, and Link8 use channel “2”).
(a)
There are a total of 10 links which share 4 channels (Link1 is the communication between Tx1 and Rx1 which is using channel “2”). The coordinates of the Txi and Rxj are randomly and uniformly generated(b)
The SINR ofLink1 is the ratio of signal power (from Tx1 equaling 1/d112) over the interference power (from Tx3, Tx7, and Tx8 equaling 1/d312+1/d712+1/d812) and noise power. These links use channel “2”Limited resources are available in the wireless network, and hence, channels need to be shared by the links. The resources allocated toN links are C channels. An interesting case is when there are less channels than the number of links: C<N. A practical application of our work is when smart devices in a room, hall, or concert arena have direct communication with other smart devices in the area using limited bandwidth. We assume each link can occupy only one channel at a time.


## 2.2. Mathematical Formulations

The power at the receiver from a transmitter, using the free space ideal propagation model, can be expressed as(1)Pr=GrGtPt4πd/λ2=Ad2,where Gr and Gt are the antenna gain at the receiving and transmitting sides, respectively. Pr and Pt are the power at the receiver and transmitter, respectively. The distance between the transmitter and the receiver is d, and λ is the wavelength of the electromagnetic wave used in the communication system [25]. In our work, the transmission power of all antennas and the gain of the antennas are constant. Similarly, as we are operating in a narrowband spectrum, we consider the wavelength of the electromagnetic wave used in the wireless network to be constant. These constants are combined into one constant A. Since the main idea is to explore the received power with the variation of the link distance, without loss of generality, we normalize A to unity. The received power at Rxj from Txi can then be simplified to(2)pij=1dij2,where dij is the distance between Txi and Rxj. In order to avoid very high or infinite values of pij when the distance is very small, we consider the minimum value of dij to be 1 [26], avoiding near-field effects [27].Then, the Signal to Interference plus Noise Ratio (SINR) ofLinkj is(3)SINRj=pij∑j=1Npij+σn2=pijIjfrom+σn2wherei=j,samelink,i≠j,differentlinks.In Equation (3), σn2 is the noise power and ∑j=1Npij is the total interference received from other links to Linkj denoted as Ijfrom. The equation assumes all links share the same channel; however, only a certain number of links share a channel and there is interference only between links sharing the same channel as illustrated in Figure 1(b). SINR1 equals the ratio of the power of the signal (due to the Tx1 which equals to p11=1/d112) over the power of the interference and noise. The random channel configuration (initially) used in Figure 1 is “2124342234” (first number signifying the channel used by Link1 and henceforth). Link1, Link3, Link7, and Link8 use channel “2.” Hence, for Link1, there is interference from Tx3, Tx7, and Tx8 which equals to I1from=1/d312+1/d712+1/d812. In this work, to make a concrete example, noise power (σn2) is arbitrarily set at 0.001, which is 30 dB smaller than the transmit power.The throughput ofLinkj based on Shannon Capacity [28] with AWGN channel and SINRj [29] is expressed as(4)Tj=log21+SINRj.Here, the throughput is in bit/s/Hz, i.e., the throughput is normalized over the bandwidth.The total throughput of a wireless network withN links is the sum of all the throughput of N links,(5)Ttot=∑j=1NTj.Ttot varies as different links choose different strategies which will be further explained in Section 3. We define, Ttotmax to be the maximum Ttot from all the different possible pure strategies obtained by exhaustive search of a random scenario.


## 2.3. Assumptions

Four notable assumptions have been made in this work, while focusing on distributed wireless networks, which are as follows:First, the links compute the resource allocation schemes themselves in a distributed way and choose the strategies independently.Second, the links are rational and selfish. Links will choose the strategies in order to increase their own payoff. In our work, utility is defined as in Equation (7) signifying a noncooperative network with independent and selfish users.Third, there is no information sharing between links. Each link can measure the received power and interference it receives from other links assuming the number of links and channels available in the network are broadcasted in the beacon signal, like in cellular or WiFi networks [30].Fourth, good error control techniques are implemented in the links. A system model as mentioned in Section2.1 leads to a dense network with a significant amount of interference. In particular, links sharing channels face considerable amount of interference. We assume the links have good error control techniques which allow them to communicate with some small bit rate even in the presence high interference (as per Shannon’s formula, Equation (4)). Over iterations, links could find other channels that have lower interference and decide to transmit at increased data rate as well.Based on the system model and assumptions stated above, channel allocation policy in our distributed wireless network will be analyzed using game theory in the next section.


## 3. Game Formulation

Game theory is a mathematical tool that is used to analyze the strategic interaction of players, especially with conflicting interests. In recent years, game theory has been used in distributed wireless networks for resource allocation purposes.A game can be symbolically expressed as a triplet,<N,Sj,UjSj,S−j> such that there are N players (links) in the game, j∈1,2,⋯,N. Sj is the set of strategies of player j, and S−j represents the strategies played by all players apart from j. The utility or payoff of player j (Linkj) is Uj, which is a function of the strategy chosen by all players [16]. In this work, the players are the links. Each link chooses to transmit in a particular channel resulting in a different payoff. Rational and independent users will try to maximize their Uj in every iteration [31]. After certain iterations, they mostly converge to a Nash Equilibrium (NE) [32].


### 3.1. Nash Equilibrium (NE)

Nash Equilibrium (NE) is a natural and eventual equilibrium state reached by rational and independent players in a distributed network. The players choose strategies that maximize their individual utility. At NE, each player will not be able to increase its utility by unilaterally changing its strategy if the strategies of other players remain unchanged [16], which is expressed mathematically as(6)UjSj∗,S−j∗≥UjSj,S−j∗∀j∈1,2,⋯,N,where Sj∗ represents the best response strategy of link j and S−j∗ represents the best response strategy of all other links except j.A centralized global solution may result in a higher overall performance, but once the rational and selfish players are allowed to make their independent choices, they will drift away from the centralized global solution. However, once the system converges to a NE, none of the rational players will change their strategies as, by doing so, they will get a lowerUj as indicated in Equation (6). Moreover, centralized solutions via an exhaustive search technique require a massive amount of resources (computational and time) especially in larger networks which is unfeasible. Hence, many practical systems prefer distributed solutions.In the next section, we define the utility of a link such that the distributed system will converge to NE with higher performance.


### 3.2. Varying Utility to Converge to NE with High Performance

In [18, 24], total throughput of the network with varying links and channels was analyzed using an exhaustive search method. Distribution of network metrics (Tj, Ijfrom, and dij) reflect that links have a significant amount of interference at NE with high total throughput.In order to converge to NE solution with high total throughput, the utility of a link in this work is defined as(7)Uj=Tj+αopt∗·Ijfrom=log21+1/dij2Ijfrom+Pn+αopt∗·Ijfrom,where Tj is the individual link’s throughput as defined in Equation (4), Ijfrom is the interference received from other links to Linkj as defined in Equation (3), α is the weight of Ijfrom, and dij is the distance between the transmitter and receiver of Linkj.Adding an optimal interference term to the payoff of a link might sound contradictory; however, such characteristics are observed in different spectra of life as well. For example, let us consider a city with a certain population having a limited number of vehicles. An equilibrium point with better well-being can be achieved when the vehicles are shared optimally [33]. By sharing the vehicles, the users have to experience inconveniences like longer ride time and route; however, the overall traffic congestion in the city can be reduced. Hence, the government can give benefits or other incentives to encourage the users in the city to share vehicles to enhance the well-being of the entire city. Similarly, when the wireless users in a distributed network voluntarily (or are hard-wired to) tolerate some level of interference in their payoff, the network can achieve solutions with higher performance. Another befitting example is of the tax payed by a citizen to the government of its country. No one really wants to pay taxes as its being cut off from the salary earned from hard work. Similarly, none of the links in a network wants to share the channel and the implicated interference, which thereby diminishes its throughput. However, all citizens have to pay taxes which are ideally used to run the government and provide social security/benefits like health care, education, and peace/security for the people of the country. Paying taxes facilitates the government to run better, so we can live in a better community [34]. Similarly, if each link in the network tolerates certain levels of interference, then the network can operate at a higher total throughput.Figure2 illustrates the convergence characteristics of the distributed system. The links use a best response technique to converge. In every iteration, each user chooses a strategy that maximizes its own utility, and eventually, the system converges to NE [32]. Generally, the best response technique converges to NE if the game is a potential function [35]. However, in our work, we start by assuming that the system converges to NE at a particular channel configuration (that results in high Ttot) as explained in Section 4.1. Then, from the NE constraints, we derive the PDF and mean value of αopt which is the key parameter in the utility function (Equation (7)). So, using the best response technique in the derived utility pushes the distributed network to converge to NE (mostly) with high performance. In a general distributed system, each user tried to maximize its individual throughput, that is, Uj=Tj. However, the converged solution of the overall system is not so high. Adding an optimal amount of interference in the utility (Uj=Tj+αopt∗·Ijfrom, Equation (7)) pushes the system to converge to NE with high Ttot. In Section 4, we mathematically derive the approximate value of αopt∗ (referred to as α^opt) which gives similar performance at a fraction of the time and computation resources. Figure 2 shows the average Tnorm.cumtot (normalized cumulative total throughput [24]) from 1000 random scenarios in the y-axis and the number of iterations (time) in the x-axis.Figure 2
Convergence characteristics (iterations versusTnor.cumtot) of the distributed system for different definitions of utility. Best response technique is used to converge to NE. An average of 1000 random “10-link 4-channel” scenarios is considered.In the upcoming section, we formulate the policy and derive an approximate mathematical expression and PDF forαopt∗ (referred to as α^opt) from NE constraints that results in high Ttot for a random “10-link 4-channel” scenario and for varying links and channels.


## 3.1. Nash Equilibrium (NE)

Nash Equilibrium (NE) is a natural and eventual equilibrium state reached by rational and independent players in a distributed network. The players choose strategies that maximize their individual utility. At NE, each player will not be able to increase its utility by unilaterally changing its strategy if the strategies of other players remain unchanged [16], which is expressed mathematically as(6)UjSj∗,S−j∗≥UjSj,S−j∗∀j∈1,2,⋯,N,where Sj∗ represents the best response strategy of link j and S−j∗ represents the best response strategy of all other links except j.A centralized global solution may result in a higher overall performance, but once the rational and selfish players are allowed to make their independent choices, they will drift away from the centralized global solution. However, once the system converges to a NE, none of the rational players will change their strategies as, by doing so, they will get a lowerUj as indicated in Equation (6). Moreover, centralized solutions via an exhaustive search technique require a massive amount of resources (computational and time) especially in larger networks which is unfeasible. Hence, many practical systems prefer distributed solutions.In the next section, we define the utility of a link such that the distributed system will converge to NE with higher performance.


## 3.2. Varying Utility to Converge to NE with High Performance

In [18, 24], total throughput of the network with varying links and channels was analyzed using an exhaustive search method. Distribution of network metrics (Tj, Ijfrom, and dij) reflect that links have a significant amount of interference at NE with high total throughput.In order to converge to NE solution with high total throughput, the utility of a link in this work is defined as(7)Uj=Tj+αopt∗·Ijfrom=log21+1/dij2Ijfrom+Pn+αopt∗·Ijfrom,where Tj is the individual link’s throughput as defined in Equation (4), Ijfrom is the interference received from other links to Linkj as defined in Equation (3), α is the weight of Ijfrom, and dij is the distance between the transmitter and receiver of Linkj.Adding an optimal interference term to the payoff of a link might sound contradictory; however, such characteristics are observed in different spectra of life as well. For example, let us consider a city with a certain population having a limited number of vehicles. An equilibrium point with better well-being can be achieved when the vehicles are shared optimally [33]. By sharing the vehicles, the users have to experience inconveniences like longer ride time and route; however, the overall traffic congestion in the city can be reduced. Hence, the government can give benefits or other incentives to encourage the users in the city to share vehicles to enhance the well-being of the entire city. Similarly, when the wireless users in a distributed network voluntarily (or are hard-wired to) tolerate some level of interference in their payoff, the network can achieve solutions with higher performance. Another befitting example is of the tax payed by a citizen to the government of its country. No one really wants to pay taxes as its being cut off from the salary earned from hard work. Similarly, none of the links in a network wants to share the channel and the implicated interference, which thereby diminishes its throughput. However, all citizens have to pay taxes which are ideally used to run the government and provide social security/benefits like health care, education, and peace/security for the people of the country. Paying taxes facilitates the government to run better, so we can live in a better community [34]. Similarly, if each link in the network tolerates certain levels of interference, then the network can operate at a higher total throughput.Figure2 illustrates the convergence characteristics of the distributed system. The links use a best response technique to converge. In every iteration, each user chooses a strategy that maximizes its own utility, and eventually, the system converges to NE [32]. Generally, the best response technique converges to NE if the game is a potential function [35]. However, in our work, we start by assuming that the system converges to NE at a particular channel configuration (that results in high Ttot) as explained in Section 4.1. Then, from the NE constraints, we derive the PDF and mean value of αopt which is the key parameter in the utility function (Equation (7)). So, using the best response technique in the derived utility pushes the distributed network to converge to NE (mostly) with high performance. In a general distributed system, each user tried to maximize its individual throughput, that is, Uj=Tj. However, the converged solution of the overall system is not so high. Adding an optimal amount of interference in the utility (Uj=Tj+αopt∗·Ijfrom, Equation (7)) pushes the system to converge to NE with high Ttot. In Section 4, we mathematically derive the approximate value of αopt∗ (referred to as α^opt) which gives similar performance at a fraction of the time and computation resources. Figure 2 shows the average Tnorm.cumtot (normalized cumulative total throughput [24]) from 1000 random scenarios in the y-axis and the number of iterations (time) in the x-axis.Figure 2
Convergence characteristics (iterations versusTnor.cumtot) of the distributed system for different definitions of utility. Best response technique is used to converge to NE. An average of 1000 random “10-link 4-channel” scenarios is considered.In the upcoming section, we formulate the policy and derive an approximate mathematical expression and PDF forαopt∗ (referred to as α^opt) from NE constraints that results in high Ttot for a random “10-link 4-channel” scenario and for varying links and channels.


## 4. Proposed Method for Approximating the Bounds and PDF ofαopt∗

In this section, we are going to approximately derive some bounds and PDF ofαopt∗ (referred hereafter as α^opt) that need to be in the individual link’s utility to converge to a NE solution with high Ttot for a random “10-link 4-channel” scenario then for scenarios with a varying number of links and channels. α^opt is quite close to αopt∗, but the main advantage of α^opt is that it can be computed in a fraction of the time and computational resources required to compute αopt∗.To proceed with the analysis, shared utility is defined based on the definition of a link’s utility expressed in Equation (7): when a link gets a single channel, the utility of the link is Us1 which equals to log21+1/da2/Pn. There is no interference received from other links for Us1. When l links share a channel, the utility of the link is defined as Usl which is expressed as(8)Usl=log21+1/da2∑m=1l−11/dIm2+PN+αopt∗·∑m=1l−11dIm2forN≥2.Here,da is the distance of the signal between the transmitter and the receiver of the same link and dIm is the distance from the mth interfering link where m=1,2,⋯,N−1.The probability density function (PDF) of1/da2 is illustrated in Figure 3. da is the distance between the transmitter (with coordinates x2 and y2) and the receiver (with coordinates x1 and y1) and can be mathematically expressed as x2−x12+y2−y12. x1, x2, y1, and y2 are random variables with uniform distribution between 0 and 10 units as illustrated in Figure 1(a). High probability mass occurs at the maximum value of 1/da2=1, as per our assumption in Equation (2). For simplicity of analysis, the distribution of the interfering links dIm (m=1,2,⋯,l−1) is assumed to have the same distribution as da. This distribution is used to compute the PDF of αopt∗ in the upcoming section.Figure 3
Probability density function (PDF) of1/da2. da is the distance of the signal between transmitter and receiver of the same link.


### 4.1. The “10-Link 4-Channel” Scenario

For “10 links 4 channels,” it has been observed that the maximumTtot occurs mostly (≈85%) at channel configuration “1234444444” [18]. The left portion of Figure 4 considers the first link (j=1) which is getting a “single channel,” and the right portion considers the fourth link (j=4) which is “sharing channel” with other links. The first, second, and third links get a “single channel” and have a payoff of Us1, as defined in Equation (8). Once the strategy is changed, the payoff of the link will be either Us2 if channel 2 or 3 is selected or Us8 if channel 4 is selected. Hence, the NE conditions are Us1≥Us2 and Us1≥Us8. The fourth to tenth links share channel 4, so the payoff is Us7. Once the strategy is changed to channel 4, the payoff of the link will be Us2. Hence, the NE condition is Us7≥Us2.Figure 4
At NE with highTtot, Linkj can use a “single channel” or “share channel” with other links. Based on the channel configuration at NEGood, the possible outcome after changing the strategy can be categorized. Applying the definition of NE, we can come up with the upper bound (UB) and lower bound (LB) conditions of optimal α.Since the value of optimalα obtained from the condition Us1≥Us2 is larger than the value obtained from the condition Us1≥Us3 which is larger than the value obtained from the condition Us1≥Us4 and so forth as illustrated in Figure 5, the upper bound for optimal α for the above mentioned conditions is exponentially decreasing. As Us1≥Us2 is a subset of Us1≥Us8, we get one unique upper bound (UB) condition: Us1≥Us8, and one lower bound (LB) condition: Us7≥Us2.Figure 5
Upper bound (UB) of optimalα for varying conditions.UB condition: solving for Us1≥Us8, using the definition of shared utility from Equation (8) when l=1 and 8 results in(9)log21+1/da2PN≥log21+1/da21/dI12+⋯+1/dI72+PN+α1dI12+⋯+1dI72,αoptUB≤log21+1/da2/PN−log21+1/da2/1/dI12+⋯+1/dI72+PN1/dI12+⋯+1/dI72.LB condition: solving for Us7≥Us2, using the definition of shared utility from Equation (8) when l=7 and 2 results in(10)log21+1/da21/dI12+⋯+1/dI62+PN+α1dI12+⋯+1dI62≥log21+1/da21/dI12+PN+α1dI12,αoptLB≥log21+1/da2/1/dI12+PN−log21+1/da2/1/dI12+⋯+1/dI62+PN1/dI22+⋯+1/dI62.αoptUB is larger than αoptLB because the first term of αoptUB is much larger than the first term of αoptLB. The absence of 1/dI12 interfering expression (which is much larger than PN) in the denominator of the first term of αoptUB produces such a result, log21+1/da2/PN≫log21+1/da2/1/dI12+PN. This holds true for the “N-link C-channel” scenario presented in the next section as well. αoptUB and αoptLB are computed using the PDF of 1/da2 and 1/dIm2. For a random “10-link 4-channel” scenario, the PDF of α^opt is computed by taking the average of αoptUB and αoptLB, which is illustrated in Figure 6 and has a mean value of 7.03 units. αopt∗ for this network is determined as such: the value of α is stepwise varied from 0 to 30 with an increment of 0.1. For each value of α, many random simulations are run and the average value of Ttot is stored. The α value that results in maximum Ttot is defined as αopt∗ [18]. For this network αopt∗ is equal to 6.8 units which is close to the value of α^opt. In the next section, we are going to generalize the mathematical expression of α^opt for varying network sizes.Figure 6
Probability density function (PDF) ofα^opt for “10-link 4-channel” scenario; the mean is 7.03 units.


### 4.2. The “N-Link C-Channel” Scenario

In this section, we are going to deduce an expression ofα^opt for different network sizes, with varying numbers of links (N) and channels (C).Generalizing the findings from the the Section4.1, NE with high Ttot mostly occurs when (C−1) links get a single channel each and the remaining channel is shared by (N−C+1) links. As illustrated in Figure 4, Linkj can be sharing a channel or using it alone at NE with high Ttot and changing its strategy should yield in lower utility. The left portion of the flow chart shows that initially Linkj is using the strategy “single channel.” Its payoff is Us1 as it is not sharing its channel with any other link. When the link changes its strategy to “share channel,” it results in having two different payoffs. First, it will have to share a channel with a link which was previously getting a single channel, then its payoff will be Us2. Secondly, it will share a channel with links that were previously sharing a channel with (N−C+1) links, then its new payoff will be UsN−C+2. Hence, the UB condition to achieve NE with high Ttot are Us1≥Us2 and Us1≥UsN−C+2. The first condition is the subset of the second condition which was explained earlier and illustrated in Figure 5. The right portion of the flow chart shows that initially, Linkj is using the strategy “shared channel.” Its payoff is UsN−C+1 as it is sharing its channel with (N−C+1) links. When the link changes the strategy, it will share a channel with the link which was previously using a “single channel.” So, its new payoff will be Us2. Hence, the LB condition is UsN−C+1≥Us2.An expression to compute the expected value ofα^opt for the “N-link C-channel” scenario can be computed by taking an expected average of αoptUB and αoptLB as follows:(11)α^opt¯=log21+1/da2/PN−log21+1/da2/∑n=1N−C+11/dIn2+PN/∑n=1N−C+11/dIn2+log21+1/da2/1/dI12+PN−log21+1/da2/∑n=1N−C1/dIn2+PN/∑n=1N−C−11/dIn22Equation (11) holds true for varying values of N and C, but better results are obtained when N/C≥1.8. In the next section, we will compare the results and analyze the performance while implementing our policy: αopt∗ and its approximate mathematical expression α^opt along with benchmark schemes.


## 4.1. The “10-Link 4-Channel” Scenario

For “10 links 4 channels,” it has been observed that the maximumTtot occurs mostly (≈85%) at channel configuration “1234444444” [18]. The left portion of Figure 4 considers the first link (j=1) which is getting a “single channel,” and the right portion considers the fourth link (j=4) which is “sharing channel” with other links. The first, second, and third links get a “single channel” and have a payoff of Us1, as defined in Equation (8). Once the strategy is changed, the payoff of the link will be either Us2 if channel 2 or 3 is selected or Us8 if channel 4 is selected. Hence, the NE conditions are Us1≥Us2 and Us1≥Us8. The fourth to tenth links share channel 4, so the payoff is Us7. Once the strategy is changed to channel 4, the payoff of the link will be Us2. Hence, the NE condition is Us7≥Us2.Figure 4
At NE with highTtot, Linkj can use a “single channel” or “share channel” with other links. Based on the channel configuration at NEGood, the possible outcome after changing the strategy can be categorized. Applying the definition of NE, we can come up with the upper bound (UB) and lower bound (LB) conditions of optimal α.Since the value of optimalα obtained from the condition Us1≥Us2 is larger than the value obtained from the condition Us1≥Us3 which is larger than the value obtained from the condition Us1≥Us4 and so forth as illustrated in Figure 5, the upper bound for optimal α for the above mentioned conditions is exponentially decreasing. As Us1≥Us2 is a subset of Us1≥Us8, we get one unique upper bound (UB) condition: Us1≥Us8, and one lower bound (LB) condition: Us7≥Us2.Figure 5
Upper bound (UB) of optimalα for varying conditions.UB condition: solving for Us1≥Us8, using the definition of shared utility from Equation (8) when l=1 and 8 results in(9)log21+1/da2PN≥log21+1/da21/dI12+⋯+1/dI72+PN+α1dI12+⋯+1dI72,αoptUB≤log21+1/da2/PN−log21+1/da2/1/dI12+⋯+1/dI72+PN1/dI12+⋯+1/dI72.LB condition: solving for Us7≥Us2, using the definition of shared utility from Equation (8) when l=7 and 2 results in(10)log21+1/da21/dI12+⋯+1/dI62+PN+α1dI12+⋯+1dI62≥log21+1/da21/dI12+PN+α1dI12,αoptLB≥log21+1/da2/1/dI12+PN−log21+1/da2/1/dI12+⋯+1/dI62+PN1/dI22+⋯+1/dI62.αoptUB is larger than αoptLB because the first term of αoptUB is much larger than the first term of αoptLB. The absence of 1/dI12 interfering expression (which is much larger than PN) in the denominator of the first term of αoptUB produces such a result, log21+1/da2/PN≫log21+1/da2/1/dI12+PN. This holds true for the “N-link C-channel” scenario presented in the next section as well. αoptUB and αoptLB are computed using the PDF of 1/da2 and 1/dIm2. For a random “10-link 4-channel” scenario, the PDF of α^opt is computed by taking the average of αoptUB and αoptLB, which is illustrated in Figure 6 and has a mean value of 7.03 units. αopt∗ for this network is determined as such: the value of α is stepwise varied from 0 to 30 with an increment of 0.1. For each value of α, many random simulations are run and the average value of Ttot is stored. The α value that results in maximum Ttot is defined as αopt∗ [18]. For this network αopt∗ is equal to 6.8 units which is close to the value of α^opt. In the next section, we are going to generalize the mathematical expression of α^opt for varying network sizes.Figure 6
Probability density function (PDF) ofα^opt for “10-link 4-channel” scenario; the mean is 7.03 units.


## 4.2. The “N-Link C-Channel” Scenario

In this section, we are going to deduce an expression ofα^opt for different network sizes, with varying numbers of links (N) and channels (C).Generalizing the findings from the the Section4.1, NE with high Ttot mostly occurs when (C−1) links get a single channel each and the remaining channel is shared by (N−C+1) links. As illustrated in Figure 4, Linkj can be sharing a channel or using it alone at NE with high Ttot and changing its strategy should yield in lower utility. The left portion of the flow chart shows that initially Linkj is using the strategy “single channel.” Its payoff is Us1 as it is not sharing its channel with any other link. When the link changes its strategy to “share channel,” it results in having two different payoffs. First, it will have to share a channel with a link which was previously getting a single channel, then its payoff will be Us2. Secondly, it will share a channel with links that were previously sharing a channel with (N−C+1) links, then its new payoff will be UsN−C+2. Hence, the UB condition to achieve NE with high Ttot are Us1≥Us2 and Us1≥UsN−C+2. The first condition is the subset of the second condition which was explained earlier and illustrated in Figure 5. The right portion of the flow chart shows that initially, Linkj is using the strategy “shared channel.” Its payoff is UsN−C+1 as it is sharing its channel with (N−C+1) links. When the link changes the strategy, it will share a channel with the link which was previously using a “single channel.” So, its new payoff will be Us2. Hence, the LB condition is UsN−C+1≥Us2.An expression to compute the expected value ofα^opt for the “N-link C-channel” scenario can be computed by taking an expected average of αoptUB and αoptLB as follows:(11)α^opt¯=log21+1/da2/PN−log21+1/da2/∑n=1N−C+11/dIn2+PN/∑n=1N−C+11/dIn2+log21+1/da2/1/dI12+PN−log21+1/da2/∑n=1N−C1/dIn2+PN/∑n=1N−C−11/dIn22Equation (11) holds true for varying values of N and C, but better results are obtained when N/C≥1.8. In the next section, we will compare the results and analyze the performance while implementing our policy: αopt∗ and its approximate mathematical expression α^opt along with benchmark schemes.


## 5. Results: Comparing Centralized and Distributed (Basic,αopt∗, and α^opt) Schemes

In this section, we are going to compare the results obtained by implementing our policy with a standard centralized and basic distributed network. Figure7 plots the Ttot for four different schemes in the y-axis and varying network sizes in the x-axis. The maximum value of Ttot for each scenario is obtained from the centralized solution via an exhaustive search technique. In the exhaustive search method, all possible channel configurations are listed and Ttot is sorted to obtain Ttotmax. This is denoted by the blue line. For large networks, it is not possible to perform the exhaustive search method. For example, for the “13-link 6-channel” scenario, the total number of channel configurations is 613 which is over 13 billion. So, the exhaustive search results for “13L6C” and larger scenarios is omitted. The lowest Ttot is obtained when Uj=Tj, which represents a basic distributed wireless network (gray line). The value of Ttot obtained by implementing the policy Uj=Tj+αopt∗×Ifrom is illustrated by the red line. αopt∗ is the optimal value of α, which is obtained by varying the value of α for a wide range (here, from 0 : 0.2 : 50) and choosing the value of α that results in maximum Ttot. In this work, we proposed a mathematical expression that approximates the real optimal α which is referred to as α^opt, represented by the orange line. Computing the optimal α via the proposed approximation is much faster and consumes only a fraction of computational resources, and the performance is quite close to αopt∗, as illustrated in Table 1. Implementing the policy can enhance the total throughput of a distributed network by up to 15% as illustrated in Figure 7.Figure 7
Illustration of how the distributed policy (addingα^opt×Ifrom term in the utility) increases the Ttot by up to 15% for distributed wireless networks. αopt∗ is the value of optimal α obtained from many random simulations for a wide range of α. α^opt is obtained from a mathematical expressions that approximates the αopt∗ and can be obtained at a fraction of computational and time resources. Although, the centralized solution from exhaustive search is the ideal solution, it is not feasible to adopt it especially for larger networks, due to its tremendous consumption of time and computational resources.Table 1
Comparing the resources (time and computation) needed and the performance of the converged solution by centralized scheme via exhaustive search technique and our distributed policy (addingα^opt×Ifrom term in the utility).
NetworkCentralized solution via exhaustive searchDistributed solution, policy (α^opt)Total channel configurationsTime (estimated) consumedTime consumed5L2C25=3.2×10132τ milliseconds39τ ms7L3C37≈2.19×1038.74τ seconds42τ ms12L4C412≈1.68×10718.64τ hours48τ ms13L6C613≈1.31×101020τ months50τ ms15L7C715≈4.75×1012602τ years53τ ms18L9C918≈1.50×10171.90×107τ years56τ ms20L10C1020≈1.00×10201.27×1010τ years60τ msTable1 enlists seven different network sizes with varying links (N) and channels (C). As N and C of a network increases, the total possible channel configurations drastically increase to CN, which is shown in the second column of the table. The 3rd column lists the time consumed to run all the CN channel configurations and find Ttotmax. Computation time for single configuration is around τ=4 ms (considered as a unit time) in our desktop computer. The fourth column shows the time consumed (computing α^opt plus running best response technique) using the distributed policy proposed in this work. From the table, it is evident that as the link size increases, it is impossible (due to time and computational resources required) to go through each channel configuration and obtain Ttotmax. Implementing the policy, the system can reach to a distributed NE solution with ≈75% of the Ttotmax consuming a fraction of the time and computational resources in comparison to the general distributed system (Ui=Ti).


## 6. Conclusion

With the increment of smart users (independent and rational), distributed and decentralized wireless networks are gaining prominence. In such networks, there is no central entity that supervises/decides the strategies of each user, and the users do not share information with each other as well. Our network has many links (with a direct communication between a transmitter and receivers) within a limited area. Hence, links generally overlap, and when resources are limited (C<N), there is high interference especially to links sharing channels. If the communication distance is limited to a certain range and channels are spatially reused, a different solution is expected (we plan to explore it further in our future work). The smart user in these networks tries to maximize its own utility in every iteration, and eventually, the network converges to an equilibrium solution called the Nash Equilibrium (NE). However, not all NE have high performance. From the analysis of different network metrics, it was found that communication links still have significant amount of interference values at NE with high Ttot. Adding weighted interference-received term in the payoff of a link can drive the decentralized system to converge to a solution with higher Ttot. In this work, we derived an approximate mathematical expression along with the PDF for αopt∗, referred as α^opt for a random “10-link 4-channel” scenario. Then, we extracted the general trend of channel configuration at NE with high Ttot and proposed a mathematical expression for α^opt for varying links (N) and channels (C).Some limitations of our work are the value of noise power, area/dimension of the network, and the wireless path loss exponent is fixed. In reality, these values can vary which may result in different channel allocation at NE with high total throughput. This might cause a shift in the value ofαopt∗ and pdf of α^opt. When we derived a generic equation for α^opt, we obtained the NE conditions from the channel allocation: “each of the C−1 links occupies its own channel and the remaining N−C+1 links share the remaining one channel” because, most of the time, NE with high Ttot occurs at the channel configuration. However, at times especially when the ratio of N/C is less than 1.8, NE with high Ttot occurs at other channel allocations. We plan to address these issues in our future work.In this work, we implement the policy and addition of an optimally weighted (α^opt) interference-received term in the payoff of a communication link. This enhances the performance of the distributed wireless network by up to 15%, and the system can achieve up to 75% of the maximum total throughput (benchmark value reached by centralized solution via exhaustive search technique) at a fraction of the time and computation resources.



---

*Source: 8868443-2020-11-06.xml*