# A Grouping Algorithm for Random Access Networks and Supermartingale Evaluation

Authors: Hongliang Sun; Xuefen Chi; Baozhu Yu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Wireless communications play a critical role in the applications of Internet of Things (IoT). The Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) is a well-proven wireless random access protocol. A crucial factor affecting the performance of random access networks is “hidden node collision,” which incurs performance degradation and lower resource utilization. Grouping is an efficient strategy for hidden node avoidance. In current IoT networks, the terminals usually have different traffic load, so load balance should be considered when grouping algorithm is designed. To mitigate hidden nodes and achieve load balance simultaneously, we propose a grouping algorithm based on the game theory. By introducing the supermartingale theory, the delay performance of the completed groups is analyzed. Simulations prove that the proposed algorithm alleviates collision, balances traffic, and promotes the efficient guarantee for Quality of Service (QoS).


---

## Body

## 1. Introduction

In future communication networks, the wireless Internet of Things (IoT) communications are expected to support extremely massive terminals. The shortage of spectrum resource has always been an important issue. For large numbers of terminals with random arrival traffic, it is not suitable to reserve resource for individual terminals. Obviously, random access strategy can share the bandwidth resource better. The Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) mechanism is widely used in the random access protocol of IoT communications [1, 2]. However, it is well known that CSMA/CA protocol suffers from severe hidden node collision with the increasing number of terminals. The collision could result in packet loss, energy consumption, and performance degradation. Therefore, it is an inevitable problem to mitigate hidden terminals for CSMA/CA networks.Much research has been devoted to settling the hidden node issue in random networks. The main methods include busy tone mechanism, Request-To-Send/Clear-To-Send mechanism, carrier-sense tuning mechanism, interference cancellation mechanism, and node grouping mechanism [3]. In contrast, the grouping-based approach is more applicable to networks with vast quantities of terminals. For the grouping mechanism, the nodes that have hidden node relationship are distributed into different groups as much as possible. In [4], the authors adopt the time difference method to determine the matrix of hidden node relationship, and the groups of hidden node avoidance are formed according to the matrix. The authors of [5] propose a Signal Strength Assistant (SSA) grouping scheme to dispose hidden node problem. The implementation of the algorithm is aided by the reference nodes with known location. In [6], the authors propose a hidden node grouping algorithm based on IEEE 802.11ah Restricted Access Window, in which the hidden node information is collected by the association process. Utilizing the integer programming optimization method, the authors of [7] propose a grouping scheme of hidden terminal avoidance. In [8], the intercluster grouping method is proposed to eliminate the hidden node problem. In [9], the authors propose a hidden terminal aware clustering mechanism, and the clusters are formed based on the detected information of the neighbor learning phase. The grouping access strategy can significantly mitigate the effect of hidden nodes. However, less attention is paid to load balance when using grouping approaches to settle the hidden node issue.Groups with balanced traffic could improve the efficiency guarantee for Quality of Service (QoS), because the service resource does not need to be drastically adjusted to match the requirement of each group. Moreover, the performance of balanced groups would not differ greatly with the same service, which facilitates the fairness guarantee in groups. Therefore, load balance should be taken into account when grouping. In [10], the authors realize load balanced grouping by constructing an optimization problem, in which the different traffic requirement of the nodes is considered. Based on the heuristic approach, the authors of [11] propose a coverage aware load-balanced clustering algorithm. The authors of [12] propose a cluster-based mobility load balance algorithm for heterogeneous cellular networks. In [13], the clustering method with an evolutionary approach is introduced aiming at the load balance. For the above research, only the load balance is considered, and the scheme is not applicable to CSMA/CA networks.In most of the existing grouping algorithms, processing hidden terminals and achieving load balance are considered separately. Relying on the grouping strategy, the authors of [3] propose an H-NAMe mechanism to avoid hidden node collision. In the algorithm, only when a node could select different groups under the grouping principle, the node is considered to be divided into group with fewer nodes to promote load balance. The authors of [14] propose a hidden node aware grouping (HAG) algorithm, in which per-group time is allocated according to the bandwidth demand for load balance. The load balance is settled after the grouping process is executed. It is highly anticipated that an algorithm could perform hidden node avoidance and load balance simultaneously.The game theory is a powerful mathematical tool used to make grouping decisions. The authors of [15] propose a game theoretic clustering algorithm for the nonuniform distributed nodes. The algorithm could effectively balance the number of nodes in each cluster, thus prolonging the effective lifetime of networks. Based on the distributed nature of the M2M networks, the noncooperative power management game is formulated in [16], and the optimal charging transmission powers of the cluster heads are derived. To implement energy-efficient cluster head selection and routing, the authors of [17] propose a game-based clustering and multihop routing scheme. For grouping with multiple constraints, it also could be achieved through the optimization problem. However, the solution would be difficult to be solved with the increasing number of nodes. In this paper, according to the characteristics of CSMA/CA networks, we construct the payoff function that the gain of hidden node reduction and load balance is considered together. By introducing the game theory, the grouping can be realized by adaptive adjustment.Benefiting from the grouping strategy, the hidden terminal issue is mitigated, and the QoS performance would be enhanced. When the grouping is completed, the reasonable performance evaluation is conducive to the resource management. Delay is one of the most significant QoS indicators, but the delay analysis has always been a notorious problem for CSMA/CA mechanism. The large deviation is a typical method for delay QoS evaluation, while the methodology proved to be conservative. Recently, the supermartingale theory demonstrates an advantage in delay analysis, and the more accurate results of delay performance are derived under CSMA/CA service in [18]. Capitalizing on the supermartingale model, the end-to-end delay performance is evaluated for multihop vehicular ad hoc networks and multimedia heterogeneous high-speed train networks in [19, 20], and the delay QoS bounds are proved remarkably tight by simulations. In our previous work, we have estimated the bandwidth requirement for aggregate traffic under delay QoS constraint based on supermartingale theory, which measures bandwidth more accurately [21]. In this paper, we evaluate the delay performance for the completed groups relying on the supermartingale analysis framework. To better estimate the overall delay performance after grouping, we set up a new QoS indicator that is the average delay-violation probability bound.The main contributions of this paper are summarized as follows:(1)
We propose a grouping algorithm based on the game theory for random access networks. The payoff function of each node is defined by taking into account the overall income. Through the game adjustment, the hidden node collision is mitigated and the load balance is achieved simultaneously. The proposed grouping algorithm could improve QoS performance and resource utilization.(2)
We introduce the supermartingale theory to analyze the delay performance. The supermartingale parameters are derived, and a new QoS indicator is established to evaluate the grouping algorithm. The delay analysis results could provide a reference for service resource management.The remainder of this paper is organized as follows. Section2 formulates the grouping problem and the grouping algorithm is designed. In Section 3, we utilize the supermartingale theory to analyze delay performance for the completed groups. Simulation results demonstrate the advantage of this research in Section 4. Finally, we conclude this paper in Section 5.


## 2. Grouping Algorithm

In this section, our grouping problem is mathematically formulated, and then, the detailed grouping algorithm is described. The main notations and descriptions used in this section are listed in Table1.Table 1
The main notations and descriptions of grouping algorithm.
NotationsDescriptionsNThe number of terminalsαThe level of hidden nodesainThe number of arrival packets from nodei in slot nλiThe arrival intensity of nodeiKThe number of groupsLkThe total traffic load of groupkΓThe set of participantsXiThe strategy space for nodeiUh_iThe gain of hidden node minimizationUl_iThe gain of load balanceHi_nowThe number of hidden nodes in current group for nodeiHi_expThe number of hidden nodes in target group for nodeiLi_maxThe maximum total traffic load after adjustmentLi_minThe minimum total traffic load after adjustmentUi_allThe overall income when nodei is adjustedUi_lastThe final income of each node


### 2.1. Problem Formulation

The simplified scenario under study is as Figure1. The location of nodes is fixed, and the hidden node relationship does not change. The arrival traffic of each node may be different. The access point (AP) is the central device of wireless access, which could interact with each node and process information.Figure 1
Grouping scenario.In [4], the hidden node pairs are detected through the time difference method. To make the AP know the hidden node relationship, two feedback approaches are considered. They are modifying the power-save poll frame structure and sending explicit control frames, respectively. We assume that the relationship of the hidden node has been detected and known by AP. The hidden node relationship could be represented by a hidden node matrix. The hidden node matrix with N nodes could be described as follows:
(1)W=w11w12⋯w1Nw21w22⋯w2N⋮⋮⋱⋮wN1wN2⋯wNN,where wij is 0-1 variable. If node i and node j are hidden node pairs, wij=1; otherwise, wij=0. We define α as the level of hidden nodes, and α is calculated as follows:
(2)α=NhNs,where Nh is the number of hidden node pairs and Ns is the total number of node relation pairs.We assume that the number of arrival packets of each node obeys Poisson distribution. As is shown in formula (3), ain denotes the number of arrival packets from node i in slot n, and Pain=r is the probability that r packets arrive in slot n. λi is the arrival intensity of node i.
(3)Pain=r=λire−λir!,r=0,1,2⋯.Our study applies not only to Poisson traffic, but also to other traffic with stable characteristics.The primary purpose of grouping is to reduce hidden terminals, so the nodes that have hidden relation should be divided into different groups as much as possible. In addition, the load balance of traffic should be maintained to the greatest extent while mitigating hidden terminals. In this model, the load balance of traffic means that the sum of arrival intensity in each group is approximate. The scenario we study is mainly aimed at terminals with relatively stable position and traffic characteristics. After the mechanism runs stably, the groups do not need to be adjusted frequently.


### 2.2. Algorithm Design

In this part, we design a grouping algorithm based on game theory. Initially, the groups are formed only by considering load balance. Then, the algorithm performs multiple rounds of game adjustment. The principle of adjustment is to reduce hidden node pairs while maintaining load balance. We takeK groups as an instance to illustrate the grouping process.The initial groups are formed according to the traffic load of each node. Firstly,K nodes are selected arbitrarily and distributed to the K groups. Then, the remaining nodes are divided into groups one by one according to the following regulation: The selected node is placed in the group with the smallest total traffic load. The total traffic load of group k is as follows:
(4)Lk=∑i=1mλk_i,where m represents the number of nodes in group k and λk_i represents the arrival intensity of node i in group k. The initial grouping ensures that the difference of traffic load in each group is not too large.The initial grouping is performed by AP. After initial grouping, AP broadcasts the hidden node relationship, the node information, and the initial grouping results. Subsequently, the game adjustment algorithm is executed.In this grouping mechanism, a round of gameG is the process that the nodes attempt to regroup. The set of participants Γ in game G consists of all nodes, and Γ=1,2,⋯,N. Each node could be viewed as a player, and they could choose to remain static or join other groups while gaming. The strategy space for node i is as follows:
(5)Xi=xi1,xi2,⋯,xiK,i∈Γ,when nodei joins in group k the decision variable xik is 1; otherwise it is 0. The gain consists of two parts: the gain of hidden node minimization Uh_i and the gain of load balance Ul_i.Uh_i and Ul_i can be calculated as follows:
(6)Uh_i=Hi_now−Hi_exp,Ul_i=e−Li_max−Li_min.Hi_now indicates the number of hidden terminals in current group for node i. Hi_exp indicates the number of hidden terminals in target group for node i, and Hi_exp=minHi_k. Hi_k is the number of hidden terminals for node i after joining in group k. The group that has the minimum Hi_k is the target group for node i. If the node is adjusted to a nontarget group, the Uh_i is 0. Li_max is the maximum total traffic load after adjustment, and Li_max=maxLi_k. Li_min is the minimum total traffic load after adjustment, and Li_min=minLi_k.For the two gains, the hidden node minimization gain plays a decisive role in whether the node is adjusted. We define the overall income when nodei is adjusted, which is as follows:
(7)Ui_all=IUh_iUl_i,where I• is an indicator function, and
(8)IUh_i=1Uh_i>0,0Uh_i≤0.Through (8), we know that the overall income exists only when Uh_i exists. The value of Ui_all depends on Ul_i.We define the payoff function for each node as follows:(9)Ui_last=Ui_allNThenodewiththemaximumUi_allisadjusted,0otherwise.For this income distribution, maximizingUi_all means that each participant can obtain the maximum income. This cooperation mode could maximize the overall income and make the cooperation stable.In the following, we will introduce the detailed process for the game adjustment. Firstly,Hi_now and Hi_k of each node are calculated. Correspondingly, the target group and Hi_exp are determined. Next, the nodes that meet the following condition are counted:
(10)Hi_now‐Hi_exp>0.If none of the nodes satisfies the condition, the game ends. That is, all nodes have the minimum number of hidden node pairs in current group, and the adjustment would not result in the reduction of hidden terminals. Otherwise, the nodes that satisfy inequality (10) calculate the load balance gain Ul_i and calculate the overall gain Ui_all further. We assume that there are m∗ nodes satisfying this condition. According to the definition of Ui_last, except for the m∗ nodes to be adjusted, the gain of other nodes would be 0. Then, the m∗ nodes send the gain information to AP. AP determines the node that could bring the largest Ui_last and adjusts it to target group. If there are multiple nodes with the same largest Ui_last, randomly select one node and adjust it in target group. Finally, Hi_now and Hi_k of each nodes are recalculated, and a new round of game starts.During gameG, every adjustment could reduce the number of hidden terminals. The same game needs to be played many rounds. The grouping results could be represented as follows:
(11)Xi_final=xi1,xi2,⋯,xiK,i∈Γ.When nodei belongs to group k, the decision variable xik is 1; otherwise, it is 0.Obviously, the more groups are divided, the less the number of hidden terminals in each group. The number of groups could be determined relying on the level of the hidden nodes. We could define the thresholdη as the acceptable average level of hidden nodes. When grouping is completed, the average ratio of hidden node pairs α¯ should be satisfied α¯<η. If α¯ does not meet the expectation, we can add the number of groups. However, too many groups will impose a burden on system management. Therefore, the optimal number of groups would be determined according to different situations.The grouping program can be described as the following algorithm1:Algorithm 1: The game-based grouping algorithm.
Input: The number of groupsK, the arrival intensity λi, the hidden node matrix W.Output: The grouping resultsXi_final.1: Select arbitraryK nodes and assign them to the K groups respectively.2: Calculate the traffic load of each group, and determine.the groupM that has the minimum traffic load.3: Assign the next nodei to group M.4: If nodei is the last node5: Go to step 9.6: Else7: Go to step 2.8: End If9: CalculateHi_now and Hi_exp for each node.10: Determine them∗ nodes that satisfy inequality (10).11: Ifm∗=0.12: Stop.13: Else14: CalculateUi_all for the m∗ nodes.15: Adjust the node that could bring the largestUi_last to target group.16: Go to step 9.17: End IfThe grouping process is based on the game theory. It is necessary to illustrate the existence of Nash equilibrium and the astringency of the game algorithm.Theorem 1.
There exists a Nash equilibrium solution for gameG, and the game-based grouping algorithm is convergent.The proof can be seen in AppendixA.


### 2.3. Algorithm Complexity Analysis

The algorithm is coordinated by central AP and distributed nodes. AP is responsible for integrating information and making decisions, and the main computation task is transferred to each node. Obviously, the computation task is heavier with more nodes. Nonetheless, each node has computation capacity, and the computational complexity will not increase extremely with the increasing number of nodes. The number of groups is the key factor affecting the computational complexity.For initial grouping, the computational complexity of each node isON, where O. indicates complexity. Then, we analyze the computational complexity for each node in a round of game. In the best case, if only one node adjustment reduces the hidden terminals, the complexity is ON. In the worst case, if the adjustment of each node reduces the hidden terminals, the complexity is ON2.


## 2.1. Problem Formulation

The simplified scenario under study is as Figure1. The location of nodes is fixed, and the hidden node relationship does not change. The arrival traffic of each node may be different. The access point (AP) is the central device of wireless access, which could interact with each node and process information.Figure 1
Grouping scenario.In [4], the hidden node pairs are detected through the time difference method. To make the AP know the hidden node relationship, two feedback approaches are considered. They are modifying the power-save poll frame structure and sending explicit control frames, respectively. We assume that the relationship of the hidden node has been detected and known by AP. The hidden node relationship could be represented by a hidden node matrix. The hidden node matrix with N nodes could be described as follows:
(1)W=w11w12⋯w1Nw21w22⋯w2N⋮⋮⋱⋮wN1wN2⋯wNN,where wij is 0-1 variable. If node i and node j are hidden node pairs, wij=1; otherwise, wij=0. We define α as the level of hidden nodes, and α is calculated as follows:
(2)α=NhNs,where Nh is the number of hidden node pairs and Ns is the total number of node relation pairs.We assume that the number of arrival packets of each node obeys Poisson distribution. As is shown in formula (3), ain denotes the number of arrival packets from node i in slot n, and Pain=r is the probability that r packets arrive in slot n. λi is the arrival intensity of node i.
(3)Pain=r=λire−λir!,r=0,1,2⋯.Our study applies not only to Poisson traffic, but also to other traffic with stable characteristics.The primary purpose of grouping is to reduce hidden terminals, so the nodes that have hidden relation should be divided into different groups as much as possible. In addition, the load balance of traffic should be maintained to the greatest extent while mitigating hidden terminals. In this model, the load balance of traffic means that the sum of arrival intensity in each group is approximate. The scenario we study is mainly aimed at terminals with relatively stable position and traffic characteristics. After the mechanism runs stably, the groups do not need to be adjusted frequently.


## 2.2. Algorithm Design

In this part, we design a grouping algorithm based on game theory. Initially, the groups are formed only by considering load balance. Then, the algorithm performs multiple rounds of game adjustment. The principle of adjustment is to reduce hidden node pairs while maintaining load balance. We takeK groups as an instance to illustrate the grouping process.The initial groups are formed according to the traffic load of each node. Firstly,K nodes are selected arbitrarily and distributed to the K groups. Then, the remaining nodes are divided into groups one by one according to the following regulation: The selected node is placed in the group with the smallest total traffic load. The total traffic load of group k is as follows:
(4)Lk=∑i=1mλk_i,where m represents the number of nodes in group k and λk_i represents the arrival intensity of node i in group k. The initial grouping ensures that the difference of traffic load in each group is not too large.The initial grouping is performed by AP. After initial grouping, AP broadcasts the hidden node relationship, the node information, and the initial grouping results. Subsequently, the game adjustment algorithm is executed.In this grouping mechanism, a round of gameG is the process that the nodes attempt to regroup. The set of participants Γ in game G consists of all nodes, and Γ=1,2,⋯,N. Each node could be viewed as a player, and they could choose to remain static or join other groups while gaming. The strategy space for node i is as follows:
(5)Xi=xi1,xi2,⋯,xiK,i∈Γ,when nodei joins in group k the decision variable xik is 1; otherwise it is 0. The gain consists of two parts: the gain of hidden node minimization Uh_i and the gain of load balance Ul_i.Uh_i and Ul_i can be calculated as follows:
(6)Uh_i=Hi_now−Hi_exp,Ul_i=e−Li_max−Li_min.Hi_now indicates the number of hidden terminals in current group for node i. Hi_exp indicates the number of hidden terminals in target group for node i, and Hi_exp=minHi_k. Hi_k is the number of hidden terminals for node i after joining in group k. The group that has the minimum Hi_k is the target group for node i. If the node is adjusted to a nontarget group, the Uh_i is 0. Li_max is the maximum total traffic load after adjustment, and Li_max=maxLi_k. Li_min is the minimum total traffic load after adjustment, and Li_min=minLi_k.For the two gains, the hidden node minimization gain plays a decisive role in whether the node is adjusted. We define the overall income when nodei is adjusted, which is as follows:
(7)Ui_all=IUh_iUl_i,where I• is an indicator function, and
(8)IUh_i=1Uh_i>0,0Uh_i≤0.Through (8), we know that the overall income exists only when Uh_i exists. The value of Ui_all depends on Ul_i.We define the payoff function for each node as follows:(9)Ui_last=Ui_allNThenodewiththemaximumUi_allisadjusted,0otherwise.For this income distribution, maximizingUi_all means that each participant can obtain the maximum income. This cooperation mode could maximize the overall income and make the cooperation stable.In the following, we will introduce the detailed process for the game adjustment. Firstly,Hi_now and Hi_k of each node are calculated. Correspondingly, the target group and Hi_exp are determined. Next, the nodes that meet the following condition are counted:
(10)Hi_now‐Hi_exp>0.If none of the nodes satisfies the condition, the game ends. That is, all nodes have the minimum number of hidden node pairs in current group, and the adjustment would not result in the reduction of hidden terminals. Otherwise, the nodes that satisfy inequality (10) calculate the load balance gain Ul_i and calculate the overall gain Ui_all further. We assume that there are m∗ nodes satisfying this condition. According to the definition of Ui_last, except for the m∗ nodes to be adjusted, the gain of other nodes would be 0. Then, the m∗ nodes send the gain information to AP. AP determines the node that could bring the largest Ui_last and adjusts it to target group. If there are multiple nodes with the same largest Ui_last, randomly select one node and adjust it in target group. Finally, Hi_now and Hi_k of each nodes are recalculated, and a new round of game starts.During gameG, every adjustment could reduce the number of hidden terminals. The same game needs to be played many rounds. The grouping results could be represented as follows:
(11)Xi_final=xi1,xi2,⋯,xiK,i∈Γ.When nodei belongs to group k, the decision variable xik is 1; otherwise, it is 0.Obviously, the more groups are divided, the less the number of hidden terminals in each group. The number of groups could be determined relying on the level of the hidden nodes. We could define the thresholdη as the acceptable average level of hidden nodes. When grouping is completed, the average ratio of hidden node pairs α¯ should be satisfied α¯<η. If α¯ does not meet the expectation, we can add the number of groups. However, too many groups will impose a burden on system management. Therefore, the optimal number of groups would be determined according to different situations.The grouping program can be described as the following algorithm1:Algorithm 1: The game-based grouping algorithm.
Input: The number of groupsK, the arrival intensity λi, the hidden node matrix W.Output: The grouping resultsXi_final.1: Select arbitraryK nodes and assign them to the K groups respectively.2: Calculate the traffic load of each group, and determine.the groupM that has the minimum traffic load.3: Assign the next nodei to group M.4: If nodei is the last node5: Go to step 9.6: Else7: Go to step 2.8: End If9: CalculateHi_now and Hi_exp for each node.10: Determine them∗ nodes that satisfy inequality (10).11: Ifm∗=0.12: Stop.13: Else14: CalculateUi_all for the m∗ nodes.15: Adjust the node that could bring the largestUi_last to target group.16: Go to step 9.17: End IfThe grouping process is based on the game theory. It is necessary to illustrate the existence of Nash equilibrium and the astringency of the game algorithm.Theorem 1.
There exists a Nash equilibrium solution for gameG, and the game-based grouping algorithm is convergent.The proof can be seen in AppendixA.


## 2.3. Algorithm Complexity Analysis

The algorithm is coordinated by central AP and distributed nodes. AP is responsible for integrating information and making decisions, and the main computation task is transferred to each node. Obviously, the computation task is heavier with more nodes. Nonetheless, each node has computation capacity, and the computational complexity will not increase extremely with the increasing number of nodes. The number of groups is the key factor affecting the computational complexity.For initial grouping, the computational complexity of each node isON, where O. indicates complexity. Then, we analyze the computational complexity for each node in a round of game. In the best case, if only one node adjustment reduces the hidden terminals, the complexity is ON. In the worst case, if the adjustment of each node reduces the hidden terminals, the complexity is ON2.


## 3. Delay Performance Evaluation

In this section, we will analyze the performance of statistical delay QoS for the completed groups. The analysis results could not only evaluate the grouping effect but also provide guidance for service resource management. The main notations and descriptions used in this section are listed in Table2.Table 2
The main notations and descriptions of delay analysis.
NotationsDescriptionspThe transition probability from backoff state to transmission stateqThe transition probability from transmission state to backoff stateRThe transmission rate in transmission stateanThe instantaneous arrivalAnThe cumulative arrivalsnThe instantaneous serviceSnThe cumulative serviceQnThe queue lengthdnThe delayDThe target delayBJThe delay-violation probability bound for nodeJBk_iThe delay-violation probability bound for nodei of group kBk¯The average delay-violation probability bound of groupkha⋅,hs⋅, Ka, Ks, θThe supermartingale parametersWe first conduct delay analysis for the packet transmission process of a single node. The queuing system with Poisson arrival and CSMA/CA service is analyzed. The supermartingale method is introduced to evaluate the delay performance. We transform the processes of arrival and service to supermartingale processes and derive the bound of delay-violation probability relying on stopping time theory.Before performing the supermartingale analysis, we first introduce the definitions of supermartingale, arrival-martingales, and service-martingales, which are as below.Definition 2 (See [22]) (supermartingale).
∀n≥0, the random process Zn,n≥0 is a supermartingale if
(1)
EZn<∞(2)
EZn+1Z0,Z1,⋯,Zn≤ZnDefinition 3 (See [18]) (arrival-martingales).
The arrival processA admits arrival-martingales if for every θ>0, there is a Ka≥0 and a function ha:rnga⟶R+ such that the process
(12)haaneθAn−nKa,n≥0is a supermartingale.Definition 4 (See [18]) (service-martingales).
The service processS admits service-martingales if for every θ>0, there is a Ks≥0 and a function hs:rngs⟶R+ such that the process
(13)hssneθnKs−Sn,n≥0is a supermartingale.In the definitions,rng⋅ indicates the domain operator. an represents the instantaneous arrival, and An represents the cumulative arrival. sn represents the instantaneous service, and Sn represents the cumulative service. θ is an attenuation index, and the parameters Ka,ha⋅,Ks, and hs⋅ all depend on θ.The arrival process of each node obeys the Poisson process. The supermartingale relative to Poisson arrival could be constructed through exponential transform [21]. Then, we give the supermartingale parameters of (12) for Poisson arrival. Poisson arrival is an independent and identically distributed increment process, and we can take haan=1. Ka could be determined according to the following formula:
(14)Eeθan=eθKa.The same CSMA/CA mechanism is adopted for each group. We use the CSMA/CA model from [18]. The Markov chain depicting the service process is shown in Figure 2. The state J refers to the node J in the transmission state, and all sources are in backoff mode in state 0. p is the transition probability from backoff state to transmission state, and q is the transition probability from transmission state to backoff state. R is the transmission rate in transmission state.Figure 2
The Markov chain depicting the service process.The transition matrix for the service process is given as(15)V=1−ppJ⋯pJq1−q⋯0⋮⋮⋱⋮q0⋯1−q.Then, we give the supermartingale parameters of (13) for this service process. Define the exponential column-transform matrix Vθ as
(16)Vθ=1−ppJ⋯pJeθRq1−q⋯0⋮⋮⋱⋮q0⋯1−qeθR.LetspVθ denote the spectral radius and hssn be the corresponding right-eigenvector. Ks can be selected as follows:
(17)Ks=logspV−θ−θ.The queue length could be shown as below.(18)Qn=supΛAn−Sn,where Λ denotes equality in distribution. According to the Little’s Law, the delay dn could be denoted as
(19)dn=QnλJ.For the supermartingale process, the expectation at a stopping time is less than or equal to the expectation of its initial value. Through the stopping time theory, we can obtain the bound of delay-violation probability [21], which is shown as Theorem 5.Theorem 5.
For anyD>0, the following delay-violation probability bound holds:
(20)Pdn≥D≤BJ=Ehaa0Ehss0He−θ′λJD,where
(21)H≔minhaanhssn:an−sn>0,(22)θ′≔supθ>0:Ka=Ks.
BJ represents the delay-violation probability bound for node J.The proof can be seen in AppendixB.To satisfy the requirement of statistical delay QoS, the delay-violation probabilityPdn≥D should be less than a threshold when the target delay value D is given. The results derived in (20) could assist to judge whether the delay requirement is satisfied. Meanwhile, the formula could reflect the delay performance.We establish a new QoS indicator to analyze the delay performance for the completed groups, which is the average delay-violation probability bound of groupk:
(23)Bk¯=∑i=1mBk_im,where Bk_i is the delay-violation probability bound for node i of group k. This indicator can reflect the average level of delay performance for each group.


## 4. Results and Discussion

In this section, we will present the simulation results for the grouping algorithm, and the performance of the scheme is evaluated. 50 nodes that the arrival traffic obeys Poisson distribution are simulated, and the hidden node matrix is simultaneously generated. The arrival intensity of each node is randomly generated from 6 to 9 packets/slot. The ratio of hidden node pairs is 20%. The number of groupsK is set to 1~10. The target delay D is taken as 10~100 slots. All results are implemented by MATLAB.We first investigate the effectiveness and advantages of the proposed algorithm. Figure3 demonstrates the relationship between the number of groups and the average level of hidden nodes. For the proposed algorithm, the ratio of hidden node pairs decreases rapidly with the increasing groups, which reveals that the grouping strategy has a great effect on solving hidden node problem.Figure 3
The average level of hidden nodes with different number of groups.The hidden matrix-based regrouping (HMR) algorithm is proposed in [4], and it has a similar scenario to our research. HMR algorithm first finds hidden node pairs and generates a hidden node matrix and then regroups nodes to reduce collision using the hidden node matrix. In our work, we focus on the grouping process after the hidden node relationship is detected, and load balance is considered when grouping. We perform a comparison with the hidden node regrouping algorithm, and it is called the existing algorithm in the following. As is presented in Figure 3, the average level of hidden nodes of the proposed algorithm descends faster than that of the existing algorithm, which illustrates that the game-based algorithm is more effective in mitigating hidden terminals. When the group number is more than 4, the ratio of hidden node pairs is rare. In the subsequent analysis, we take 4 groups as an example.In the grouping algorithms of [4–9], only the hidden node problem is considered. In our work, the load balance is synchronously considered. Figure 4 displays the results after game adjustment. Not only the number of hidden node pairs is small, but also the load balance is realized. Figure 5 manifests the grouping results of the existing algorithm. Compared with the proposed algorithm, the number of hidden node pairs is more, and the difference in traffic load is larger. The results demonstrate that the proposed algorithm could settle the hidden node problem more effectively, and achieve load balance simultaneously.Figure 4
The results of the proposed grouping algorithm.
(a)
Hidden node pairs(b)
Traffic loadFigure 5
The results of the existing grouping algorithm.
(a)
Hidden node pairs(b)
Traffic loadIn the grouping algorithms of [10–13], only the load balance is considered. In our algorithm, the load balance is not the main income in the grouping process, so the load balance effect may not be superior to other research. In relative terms, the advantage of this algorithm is to obtain two kinds of income simultaneously. The initial grouping algorithm is formed according to the traffic of each node, and it is an algorithm that only considers load balance. Figure 6 presents the results of the initial grouping algorithm. Although the load balance is implemented, there exist many hidden node pairs.Figure 6
The results of the initial grouping algorithm.
(a)
Traffic load(b)
Hidden node pairsThen, we analyze the delay performance of each group. The average delay-violation probability bound is used as an indicator to evaluate delay performance. In Figure7, the results present the delay performance curves for the groups with the best delay performance and the worst delay performance. It is shown that the average delay-violation probability bound decreases with the increasing target delay. The greater target delay corresponds to the looser delay requirement, so the QoS violation is not easy to occur and the average delay-violation probability bound is smaller. There is a small difference in delay performance between the two groups. To further guarantee the trade-off of the groups, we could allocate a larger available resource to the group with the large average delay-violation probability bound. Also, we compare the delay performance between the proposed algorithm and the existing algorithm. As is shown in the results, the gap of delay performance curves for the proposed algorithm is smaller. The results illustrate that the delay performance of each group is more similar, and the proposed algorithm could make for a fairness QoS guarantee, which is beneficial for resource management.Figure 7
The best delay performance and the worst delay performance of the completed groups.Subsequently, we change the range of arrival intensity. We take the standard deviation of traffic load as the measure of load balance degree. The minimum arrival intensity keeps at 6 packets/slot and the maximum arrival intensity increases. Figure8 shows that the overall trend of standard deviation becomes larger with the increasing range of arrival intensity. For a large difference in arrival intensity, if we perform grouping directly, the nodes with heavy traffic are prone to congestion. We could assign the terminals with small difference in traffic load into one cluster and then group the nodes for the cluster.Figure 8
The standard deviation of traffic load with different range of arrival traffic.From the computational complexity analysis of the algorithm, we know that the main factor affecting the complexity is the number of partitioned groups. In the simulation of Figure9, we set the acceptable average level of hidden nodes as 10%. As expected, the required number of groups increases rapidly with the increasing ratio of hidden nodes. The results manifest that the ratio of hidden nodes has a significant effect on the algorithm complexity. If the level of hidden nodes is too high, we could not merely rely on the grouping strategy, and other methods of hidden node avoidance should be considered synchronously.Figure 9
The required number of groups with different ratios of hidden node pairs.


## 5. Conclusion and Future Work

In this paper, we proposed a grouping algorithm for random access networks based on the game theory. The income of hidden node minimization and load balance was considered simultaneously. Moreover, the supermartingale theory was introduced to analyze the delay performance, and a new QoS indicator was established to support the delay analysis. The proposed algorithm could mitigate hidden terminal collision, achieve traffic load balance, and facilitate the QoS guarantee efficiently. The analysis results could provide a reference for the allocation of service resource. However, when the traffic difference is large and the number of terminals is small, the grouping algorithm will not get a good result for load balance. In addition, if the traffic and location of terminals are not fixed, the updating mechanism needs to be explored. To ensure the QoS requirement of individual terminals, the scheduling scheme after grouping also needs to be studied. We are interested in investigating the above issue in future work.



---

*Source: 2554226-2022-09-09.xml*