# Enabling Device-to-Device (D2D) Communication for the Next Generation WLAN

Authors: Ying Wang; Jianjun Lei; Fengjun Shang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Device-to-device (D2D) communication technology is widely acknowledged as an emerging candidate to alleviate the wireless traffic explosion problem for the next generation wireless local area network (WLAN) IEEE 802.11ax. In this paper, we integrate D2D communication into IEEE 802.11ax for maximizing the spectrum efficiency. Due to the spectrum scarcity, the number of available resource units (RUs) is typically less than D2D pairs and stations (STAs), which makes the management of spectrum resources more complex. To tackle this issue, we design an efficient resource management algorithm for uplink random access and resource allocation in D2D-enabled 802.11ax, which provides more channel access and resource reuse opportunities for STAs and D2D pairs. Specifically, we propose an enhanced back-off mechanism and derive the optimal contention window (CW) by a theoretical model, which improves the uplink random access efficiency. To tackle the complex interference problem in RU scheduling phase, we develop an efficient and low-complexity resource allocation algorithm based on the maximal independent set (MIS), which can schedule multiple D2D pairs to share the same RU with the specific STA. Simulation results demonstrate that the proposed algorithm significantly improves the network performance in terms of system throughput, collision rate, complete time, and channel utilization.


---

## Body

## 1. Introduction

Recently, wireless local area networks (WLANs) have been widely deployed in residential, commercial, and public areas to provide the near-ubiquitous wireless coverage. As the rapid development of wireless communication technology, the wireless devices are becoming more intensive; meanwhile, the reliability of data transmission is more demanding. The legacy IEEE 802.11 faces some fundamental challenges in network performance improvement, e.g., higher spectrum efficiency, lower latency, and less collision, especially in such highly dense networks, owing to the fact that it adopts the bind binary exponential back-off (BEB) scheme and only supports that the single user monopolizes the channel resource. To address these issues, the latest WLAN standard IEEE 802.11ax is designed [1]. Specifically, the orthogonal frequency division multiple access (OFDMA) technology, as a key innovation in 802.11ax, divides the frequency-domain channel into several orthogonal subcarrier groups referred to as resource units (RUs) [2, 3]. Consequently, 802.11ax can effectively solve the negative impact caused by the exclusive channel mode in carrier sense multiple access with collision avoidance (CSMA/CA) protocol by enabling the uplink multiuser transmissions [4].Different from the legacy distributed coordination function (DCF) or enhanced distributed channel access (EDCA) mechanism, the uplink OFDMA-based random access (UORA) mechanism is employed in 802.11ax. In UORA, multiple stations (STAs) can simultaneously access these orthogonal RUs to transmit data, which significantly improves the spectrum efficiency by enabling resource reuse. However, the OFDMA contention window (OCW) in UORA cannot be adaptively adjusted with the dynamic network environment, and hence, collisions are still inevitable especially in the highly dense WLAN [5]. Many works have proposed corresponding modifications to the UORA by optimizing MAC access parameters. Although these works enhance the MAC access efficiency and improve the network performance well, the optimal spectrum efficiency is limited by available RUs especially in highly dense network.More recently, device-to-device (D2D) communication has become an emerging technology in cellular network and WLAN, which can effectively release the infrastructure-based network resource and greatly improve the spectrum efficiency by allowing direct communications between proximal devices [6]. Thus, two STAs in close proximity need to compete for channel access only once because they transmit the data directly. Meanwhile, the serious data collision caused by channel contention can be markedly relieved by offloading STAs into D2D communication mode. Besides, the D2D communication with overlay mode further improves spectrum utilization by scheduling D2D pairs and the specific STA to share the same RU, simultaneously. However, the unreasonable resource allocation strategy could result in the severe cochannel interference among D2D pairs and STA. Most previous studies on D2D offloading in WLAN focus on coordinating the switching of the nodes in infrastructure-based communication mode to D2D communication mode, although the resource allocation has attracted attentions in the D2D-enabled WLAN for improving the spectrum efficiency. However, the resource allocation algorithm for multiple D2D pairs and RU scenario is rarely considered in most existing works due to high computational complexity or overheads.Motivated by these advantages and challenges, this paper integrates D2D technology into 802.11ax and proposes an efficient channel access and resource allocation algorithm for improving the spectrum efficiency. Correspondingly, two significant challenges must be tackled: (1) it is necessary to determine whether or not two STAs can switch from traditional infrastructure-based mode to D2D communication mode; (2) it is crucial to design proper interference management and resource allocation algorithms to allocate RUs for D2D pairs and STAs for maximizing the spectrum efficiency. Many works have been dedicated to coordinating adaptively the communication modes of nodes in D2D-enabled WLAN and achieve the significant performance improvement. Hence, this paper only focuses on the interference management and resource allocation algorithm in D2D-enabled 802.11ax network, where multiple D2D pairs meeting the interference conditions can share one RU with the specific STA so as to maximize the spectrum efficiency. In particular, the proposed algorithm, referred to as MISD, combines an enhanced back-off mechanism for STAs in uplink random access phase and an RU allocation algorithm based on maximum independent sets (MISs) in resource allocation phase. The main contributions of this paper are summarized as follows:(i)
We integrate the D2D communication technology into 802.11ax and develop a spectrum efficiency optimization solution for random access and resource allocation in D2D-enabled 802.11ax network(ii)
We propose an enhanced back-off mechanism in frequency and time domains, where the optimal CW is derived by a theoretical model for maximizing the uplink random access efficiency. Moreover, the proposed algorithm reduces the control overheads and the data collisions significantly by canceling the ACK frame and offloading nodes into the D2D communication mode in the uplink random access phase, respectively(iii)
We propose an efficient resource allocation algorithm based on the MISs, where AP can schedule multiple D2D pairs to share the same RU with the specific STA, simultaneously, which significantly improves the spectrum efficiency. Moreover, the proposed algorithm has low complexity, i.e., AP only needs to estimate the interference between the specific STA and the D2D pairs in the largest MIS(iv)
A numerical analysis model is established to verify theoretically the performance improvement of the MISD algorithm. Furthermore, the extensive simulation results clearly demonstrate the benefits of the proposed MISD algorithm from the enhanced back-off mechanism and the efficient resource allocation algorithmThe remainder of this paper is organized as follows. We summarize the related work in Section2. Section 3 presents the system model and algorithm design. Then, Section 4 describes the numerical analysis. The performance simulations of the proposed algorithm are carried out in Section 5. Finally, Section 6 concludes this paper and indicates the future research direction.


## 2. Related Work

This section describes the related work of the previous studies on OFDMA-based and D2D-based offloading MAC protocols in highly dense WLAN.IEEE 802.11ax introduces the OFDMA technology for supporting concurrent data transmissions [6, 7]. The work in [8] presents that enabling OFDMA in WLAN can enhance the channel utilization in dense scenarios. In [9], Qu et al. propose the whole channel physical sensing and fast back-off mechanisms for IEEE 802.11ax. Although the problems of synchronization and overhead are effectively solved, the MAC efficiency is substantially limited due to the blind CW adjustment strategy. To tackle this issue, Uwai et al. propose an adaptive back-off mechanism by optimizing MAC parameters in [10], which improves the throughput in uplink random access period. However, the spectrum efficiency is not optimal due to the collision in high load network scenario. In [11], Shahin et al. propose a cognitive back-off mechanism that each station adaptively adjusts CW, which solves the critical medium collision problem in dense WLAN, but the channel access delay is not considered. In [12], Wang et al. propose a probability complementary transmission scheme (PCTS) to mitigate the delay caused by retransmission. In PCTS, the stations with unsuccessful transmission trials can transmit directly with the complementary probability. However, it is unsuitable for highly dense networks, which increases the severe data collision. In [13], Lin et al. enable multiple RTS intervals in random access phase and propose a joint grouping and subchannel allocation algorithm to improve the spectrum efficiency. However, it lacks in further analyzing the number of RTS intervals, which has direct impacts on the network performance.Many studies have shown that the scheduling-based MAC protocols in OFDMA WLAN can be exploited to improve the spectrum efficiency. In [14], Bankov et al. investigate the scheduling problem and transfer the well-known schedulers in LTE for different application scenarios in 802.11ax, i.e., high throughput, fairness, and low latency, respectively. In [15], they propose an uplink transmission scheduler for the OFDMA network to minimize the average upload time, which considers various RU configuration. In [16], Dovelos and Bellalta propose another channel resource scheduling scheme to maximize the long-term average rate under the constraints of the average rate and power. However, the nonsaturated traffic condition scenarios are not discussed in [14–16]. Consequently, the hybrid access algorithms including random access and scheduling access are proposed. In [17], a theoretical model is established to adjust the number of RUs for random access and scheduling access in highly dynamic 802.11ax network. However, the corresponding optimization mechanisms are not discussed. In [18], Yang et al. propose a hybrid channel access algorithm, including a greedy scheduling access mechanism based on capacity constraints and a random-access mechanism based on channel quality perception, where the optimization problem for the joint carrying capacity of the networks is a challenge. In [19], Karaca et al. develop two OFDMA-based resource scheduling algorithms: (i) using a fixed scheduling duration and (ii) dynamically adjusting the scheduling duration by comprehensively considering filling overhead, fairness, and user power consumption. Although the previous OFDMA-based literature can improve the spectrum efficiency by enabling multiuser current transmissions, the optimal spectrum efficiency is limited by the available RUs. Besides, they cannot fundamentally tackle the bottleneck that all traffic still needs to be forwarded centrally by the AP.The emerging D2D technology has been widely used in dense network scenarios, which can alleviate data collisions and enhance the spectrum efficiency by offloading nodes to D2D communication mode and enabling spectrum reuse technology. In [20], Mach et al. provide a survey and discuss the advantages, critical challenges, and research directions of in-band D2D in OFDMA cellular network. In [21], Shah et al. review the interference mitigation and radio resource management of in-band D2D communications and discuss the problems of resource management, mode selection, energy efficiency, and coexistence of D2D communications. Correspondingly, the researches on D2D communication technology are mainly divided into D2D link management [22–24], resource allocation, and interference management [25–27].In [22], Cai et al. propose a D2D communication framework based on the Software Defined Network (SDN) and Network Function Visualization (NFV) in virtual wireless networks, which employs a stochastic approximation algorithm to optimize the network-wide welfare by switching the mobile nodes between infrastructure-based and D2D-based communication modes. In [23], Cheng et al. propose another switching scheme for nodes based on SDN technology in D2D-based WLAN. However, the resource allocation-related issues are not considered both in [22, 23]. In [24], a network-assisted D2D technology by utilizing WiFi Direct as the link layer technology for proximal D2D connections has been proposed, which mitigates the disproportion between user demand and available radio resources. However, the resource management for D2D connection is not detailed. In [25], Zhao et al. transform the channel allocation problem into a graph coloring problem by building an interference graph and finding an approximate optimal solution in D2D underlying cellular networks. However, multiple D2D pairs are not allowed to share the same channel resource. In [26], Wen et al. propose a joint power control and resource allocation algorithm that greatly reduces the interference and improves the network performance, but the algorithm is too complex. In [27], Seyedebrahimi et al. propose a novel management framework for D2D communications in dense WiFi network, which proactively establishes and manages D2D connections by considering the available radio resource and the effect of the subsequent interference. However, the overlay D2D communication mode is not considered.The previous studies on OFDMA-based MAC protocols improve network performance by enabling concurrent transmission. However, the optimal spectrum efficiency is limited by the available RUs. Integrating D2D offloading into WiFi network can further improve the spectrum efficiency but also bring the complex interference management problem [28]. The resource allocation and interference management problems in D2D offloading WiFi network are not addressed well in the aforementioned research studies. Specifically, these problems will be more complicated in 802.11ax due to more RUs. Hence, this paper investigates the resource allocation and interference management problems in D2D-enabled 802.11ax network to enhance the spectrum efficiency.


## 3. The Proposed Algorithm

In this section, we introduce the system model of the D2D-enabled 802.11ax network. Then, we propose an uplink channel access and resource allocation algorithm referred to as MISD. In detail, the proposed MISD algorithm is aimed at enhancing the spectrum efficiency and reducing collision by combining an enhanced back-off mechanism with optimal CW and an efficient resource allocation mechanism.


### 3.1. Architecture and Model

We consider an uplink transmission scenario in the single Basic Service Set (BSS) governed by IEEE 802.11ax, which supports two communication modes: AP forwarding and D2D offloading, where the D2D pair can communicate directly. As shown in Figure1, AP is deployed in the geometrical center of the BSS, and all nodes (i.e., STAs and D2D pairs) are randomly distributed in the coverage region of AP. Assume n STAs and m D2D pairs in the D2D-enable 802.11ax network. Let S=S1,S2,⋯,Sn and D=D1,D2,⋯,Dm denote the set of STAs and D2D pairs, respectively. AP and all nodes support MU transmissions which is a basic characteristic of 802.11ax. The whole channel is divided into r subchannels (referred to as RUs), denoted as R=R1,R2,⋯,Rr. To be more specific, the spectrum resource (i.e., RU) can be shared by the communication links under the two communication modes. Moreover, multiple D2D pairs meeting the interference conditions can share the same RU. Since the downlink transmission can be scheduled directly by AP and operated easily [29], this paper only focuses on the uplink data transmission. We also make an assumption that the network is in the saturated condition, i.e., all nodes in the network always have packets to send. Specifically, only STAs need to contend for channel by sending buffer status report (BSR) frame in uplink random access phase. Besides, the RU allocation decisions for STAs and D2D pairs are made by AP according to the interference relationship among nodes.Figure 1
The network scenario.


### 3.2. MISD Algorithm

This subsection details our proposed MISD algorithm. Firstly, we present an overview of the MISD algorithm. Then, the random access, resource allocation, and data transmission phases are introduced in detail, respectively.


#### 3.2.1. MISD Overview

This paper concentrates on maximizing the spectrum efficiency by optimizing jointly random channel access and resource allocation in D2D-enabled 802.11ax, where the complex network scenario, i.e., multiple D2D pairs and RUs, is considered. To this end, we propose an efficient resource management algorithm MISD, which decouples the spectrum efficiency optimization problem into two subproblem in uplink random access and resource allocation phases. Correspondingly, the proposed MISD algorithm separates the channel time into a series of superframes, where each superframe includes uplink random access, resource allocation phase, and uplink data transmission phases, as shown in Figure2. Furthermore, the enhanced back-off mechanism and efficient resource allocation algorithm in resource allocation phase are developed for improving the spectrum efficiency in random access phase and data transmission phase, respectively. In particular, the STA contends for the RU based on the proposed enhanced back-off mechanism, independently; in resource allocation phase, AP allocates RUs for STAs and D2D pairs by the proposed efficient resource allocation algorithm; hence, the specific STA and D2D pairs can share the same RU for concurrent data transmission in data transmission phase.Figure 2
The channel access and data transmission process of MISD.


#### 3.2.2. Random Access Process

In this subsection, we first establish a theoretical analysis model to derive the optimal contention windowCW∗ in order to maximize the system throughput in uplink random access phase. Then, we propose an enhanced back-off mechanism, where the STAs can contend for RUs with the CW∗ in both time and frequency domains.CW optimization. Let τ be the probability that a STA attempts to transmit data packet in the considered RU, which can be expressed as
(1)τ=21+CW,whereCW denotes the contention window for each uplink random access phase, which is calculated and broadcast by AP in the considered system model. Assume that the back-off value of AP is equal to CW.LetPtr denote the transmission probability, i.e., at least one transmission occurs in the considered RU. Therefore, Ptr can be expressed as
(2)Ptr=1−1−τn,wheren is the number of contending STAs. Let PI denote the idle probability, i.e., no transmission in the considered RU, which can be calculated by
(3)PI=1−τn.LetPs denote the probability of successful transmission in considered RU, i.e., only one STA transmits the packet in the considered RU. Accordingly, Ps can be obtained by
(4)Ps=n1−τn−1Ptr=n1−τn−11−1−τn.Analogously, the collision probabilityPc in the considered RU is expressed as Pc=Ptr−Ps. Therefore, the throughput for considered RU is
(5)SRU=PsPtrEP1−PtrTi+PsPtrTs+Ptr1−PsTc,whereEP denotes the average packet payload size. Ti denotes the duration of an empty slot. Ts and Tc are the average length of time periods for a successful packet and a collision packet, respectively. To reduce unnecessary control overheads, there is no ACK frame for each BSR frame in the proposed enhanced back-off mechanism. Consequently, assume that Ts=Tc as
(6)Ts=Tc=TBSR+2TSIFS,whereTBSR denotes the average length of time period for transmitting successfully a BSR frame. Analogously, TSIFS is short interframe space (SIFS). By substituting the above correlation formulas in (5), the SRU can be rewritten as
(7)SRU=EPn1−τn−11−τnTi+1−1−τnTc,where theEP is a fixed value for all nodes. To achieve the maximum theoretical throughput limitation, as seen in (7), we only need to maximize the following equation:
(8)θ=n1−τn−11−τnTi+1−1−τnTc.For a givenn, there exists an optimal CW∗ for maximizing the system throughput SRU in considered RU. Thus, taking the partial derivative in (8) with respect to τ, the derivative of (8) is given as
(9)dθdτ=n1−τn−21−nτTs+Ti−Ts1−τn+n2τTi−Ts1−τ2n−2Ts+Ti−Ts1−τn2=0.Using the simplification rule in [30], the expression of τ can be approximately derived from the following equation:
(10)τ=n+2n−1Ts′−1/n−1n−1/Ts′−1≈1nTs′/2,whereTs′=Ts/Ti. By simplifying and substituting the τ value in (1) into (10), we can obtain an approximate relationship between CW∗ and n from the following:
(11)CW∗≈n2TsTi.Based on the proposed theoretical analysis model, the optimalCW∗ can be calculated according to the variables, i.e., n, Ts, and Ti. In practical 802.11ax networks, these variables might be different and changed with respect to time. Compared to the STAs, AP can track these variables timely and adjust adaptively the CW∗ for optimizing the MAC access efficiency.Enhanced back-off mechanism. Different from the legacy uplink random access mechanism, the proposed enhanced back-off mechanism executes the back-off process in frequency and time domains, simultaneously. As shown in Figure 3, the uplink random access period includes multiple back-off substages and r available RUs in time and frequency domains, respectively. Let CWi=CW∗ denote the CW of STA i,i∈S. Accordingly, let boi∈0,CW∗ denote the back-off value of STA i.Figure 3
The uplink random access mechanism of MISD.LetSi denote the STAi,i∈S. In each back-off substage, Si updates its boi, as boi=boi−r. Specifically, if boi≤0, Si randomly chooses a RU and sends its BSR to AP. After that, the back-off value of Si will be reset as boi=CW∗. Note that the maximum back-off stages are limited by ∣CW∗/r∣; thus, each STA can contend for channel resource once during the current uplink random access phase. Let TSi∈0,1 denote the transmission result of BSR of Si, where TSi=1 denotes that AP has received successfully the BSR frame from Si; otherwise, TSi=0. Correspondingly, AP adds Si into the available scheduling stations set denoted as NS, while TSi=1. Repeat the back-off process until the number of STAs in NS is larger than r or uplink random access phase is over. Since the resource allocation results for data transmission will be announced by AP with the trigger frame (TF) frame, AP will not respond with ACK for each BSR frame in the proposed algorithm, which can reduce control overheads. More specifically, we summarize the enhanced back-off mechanism with optimal CW in Algorithm 1.Algorithm 1: The enhanced back-off mechanism
1: Initialize: Node setS, TSi=0,i∈S2: AP computesCW∗ by (11) and broadcasts it and r3:fori in Sdo:4:Si randomly select a value from 0,CW∗ as boi5:end for6:whilet≤∣CW∗/r∣do:7:foriinSdo:8:boi=boi−r9:ifboi≤0do:10:Si randomly choose a RU to send BSR11:if AP received BSR from Sido:12:TSi=1 and NS=NS∪Si13:end if14:boi=CW∗15:end if16:end for17:if∣NS∣≥rdo:18:      break19:end if20:t+=121:end while


#### 3.2.3. Resource Allocation

The uplink resource allocation is executed while AP successfully sends the TF on the whole channel. To avoid the waste of channel resources, AP can schedule the downlink transmission during this phase. Since this paper only focuses on uplink resource allocation and data transmission, the downlink data scheduling and transmission processes are skipped. Note that, the resource reuse technology is employed in D2D-enabled 802.11ax network. Hence, AP can schedule multiple D2D pairs to share the same RU with the specific STA based on the efficient resource allocation algorithm, which significantly enhances the spectrum efficiency in data transmission. However, the resource allocation algorithm faces two key challenges: (1) identifying whether or not the STA and D2D link can share the same RU; (2) determining which D2D pairs can reuse the same RU. To tackle these challenges, the complex interference problems among D2D pairs and STAs have been effectively solved in the proposed resource allocation algorithm. Specifically, we introduce the interference graph and the conception of MIS to group the D2D pairs without interference into the same MIS. In addition, the interference matrix for D2D pairs and STAs, denoted asL, is established. Based on MIS and L, we develop an efficient resource allocation algorithm, where multiple D2D pairs and the STA are allowed to share the same RU. To describe the resource allocation mechanism in detail, we decouple it into three parts: formulating D2D interference graph and generating maximum independent set and resource allocation decision, and give the corresponding introduction as follows.Formulating D2D interference graph. The formulating algorithm of D2D interference graph is executed when D2D pairs are established or D2D pairs change. Let G=<V,E> denote the interference graph of D2D pairs. Note that G is constructed according to the interference relationship of D2D pairs. The vertexes in set V represent D2D pairs corresponding to D=D1,D2,⋯,Dm defined in Section 3.1. Besides, the edges in set E represent the interference relationship between D2D pairs defined by the SINR of receiver. It is considered that the communication links will be interfered, when the SINR of receiver of any link has less than the threshold. The instantaneous SINR of receiver for D2D pair is as
(12)SINRD=PDαDPNαN,D+No,wherePD is the transmit power of D2D communication device. αD is the path loss of the D2D pair, and αN,D can be represented as
(13)αN,D=λ4πρ2,whereρ is the distance of the two D2D pairs and λ is the wavelength of the signal.Figure4 shows an illustrative example of generating the interference graph of D2D pairs, where Figure 4(a) gives the network topology of D2D pairs. Based on this, the corresponding interference graph G is formulated in Figure 4(b). Referring to Figure 4(c), when the D1 and D2 transmit data packets in the same RU in parallel, both data links will be interfered, i.e., the communication links from Sender 1 to Receiver 1 and Sender 2 to Receiver 2 will cause the interference for Receiver 1 and Receiver 2, respectively. Accordingly, both Receiver 1 and Receiver 2 cannot receive data correctly. To avoid this issue, the proposed resource allocation algorithm introduces the MIS to avoid allocating the same RU for these interference links.Figure 4
Illustrative example of the interference graph of D2D pairs.
(a)
Network topology(b)
Interference graph(c)
Interference linkMaximum independent sets. In accordance with the graph theory, there is no adjacency between any two nodes of the same MIS. Inspired by this, we introduce the concept of MIS and divide the D2D pairs into multiple MISs according to their interference relationship in an iterative manner. Correspondingly, the D2D pairs without interference will be divided into the same MIS, which can share the same RU for parallel transmission. Note that, the process of generating the MISs is triggered when the interference graph is established or updated. Let IS=IS1,IS2,⋯,ISK denote the information of MISs, where the ISk,k∈1,K stores the D2D pairs’ IDs in the kth MIS. Note that the K varies with the interference graph. Let I=Ii,jm×m,i,j∈D denote the interference relationship between D2D pairs. Specifically, Ii,j can be expressed as
(14)Ii,j=1,mutualinterference,0,otherwise.Consequently, the D2D pairsi and j, where i,j∈ISk, can share the same RU to transmit data, simultaneously due to Ii,j=0. Algorithm 2 describes the procedure of generating MISs in detail. Once the D2D interference graph G is created or changed, AP will run Algorithm 2 to generate or update the IS. For a given interference graph G, it is easy to find the nodes which belongs to the MIS by judging the interference relationship between the D2D pairs in current MIS and the D2D pairs in V. If there is no interference relationship between the D2D pair i∈V and all D2D pairs in the kth MIS ISk, i.e., ∑j∈ISkIi,j=0, the D2D pair i will be added into ISk and removed from V. Repeat the above process to find the next MIS ISk+1 until the node set V is empty. Finally, AP sort IS in descending order, i.e., the number of D2D pairs in IS1 is maximum, which helps to reduce the computational complexity of resource allocation decision process and improve the decision efficiency.Algorithm 2: Generating maximum independent sets
Input:G=<V,E>, I=Ii,jm×m, i,j∈DOutput:IS=IS1,IS2,⋯,ISk1:k⟵02:whenV is not empty do3:k⟵k+1, Im⟵04:   Select a D2D pairv in V as the initial node5:   Addv into ISk, and remove it from V6:fori⟵0 to len(V) do7:forj⟵0 to len(ISk) do8:ifIi,j==1then9:Im⟵Im+110:          Break11:end if12:end for13:ifIm==0then14:      Add D2D pairj into ISk and remove it from V15:        UpdateISk16:end if17:end for18:end when19: Sort (IS)20:ReturnISResource allocation decision. This phase is triggered by the TF frame for maximizing the spectrum efficiency. Let the interference matrix L=Lsi,Din×m, where Si∈S and Di∈D denote the interference relationship of Si and Di. The Li,j can be expressed as
(15)Li,j=1,SiandDiinterferewitheachother,0,otherwise.In the proposed resource allocation algorithm, AP first allocates RUs for STA inNS. Note that NS is obtained in uplink random access phase. Subsequently, based on the IS and L, AP only needs to do match-action operation once to allocate the specific RU for D2D pairs. Accordingly, the time complexity of each match-action equals to the number of D2D pairs in IS1, denoted as m1m1≤m, and the m1 decreases gradually during RU allocation phase. Thus, the worst time complexity of the proposed RU allocation mechanism is Orm in r available RU scenario. Let Si denote the specific STA that can use the ith RU in data transmission phase. In each match-action operation for making the specific RU allocation decision, AP estimates the interference relationship among the Si and Dj∈IS1 only. In particular, AP will allocate the RU for Dj, only when LSi,Dj=0,Dj∈IS1, i.e., adding the Dj into set DRi and removing Dj from IS1, accordingly. Exceptionally, if no D2D pair in IS1 can share the RU with Si, AP will do the same match-action operation for the next MIS IS2 with the Si. After that, AP sorts IS in descending order. Since IS1 always includes maximum noninterference D2D pairs, AP always try to schedule more D2D pairs to share the same RU. Hence, the proposed resource allocation algorithm in MISD can significantly improve decision-making efficiency by enabling the match-action operation based on MISs, meanwhile maximizing spectrum efficiency by providing more spectrum reuse opportunities for nodes. Algorithm 3 depicts the pseudocode of the proposed resource allocation algorithm.Algorithm 3: Resource allocation decision algorithm
Input:NS, IS, L, rOutput:DR1: AP allocates RU for the STA inNS2:i⟵0, T⟵03:whenNS≠∅ or i≠rdo:4:c⟵05:STA⟵NSi6:forj⟵0 to lenSTdo:7:D←IS0j8:ifLSTA,D==0then:9:        AddD into DR and remove it from ST.10:c⟵c+1;11:end if12:end for13:ifc≠0then14:T⟵T+115:else16:      UpdateIS, T⟵117:end if18:i⟵i+1;19:end when20:ReturnDRWe present an example to illustrate the detail of the resource allocation procedure in the proposed algorithm, as described in Figure5. Firstly, AP will allocate a unique RU for each STA in NS. Consequently, these STAs can transmit simultaneously data in the specific RU in the next data transmission phase. To maximize the spectrum efficiency, the multiple D2D pairs are scheduled to share the specific RU based on the proposed resource allocation algorithm. More specifically, AP allocates the specific RU for Si∈NS, where IS1=D1,D2,D3,D5 and the interference relationship matrix of Si is LSi=1,1,0,0,0,1,1. The number of elements in LSi equals to m. Based on this, AP estimates the interference relationships by matching LSi and IS1 to make the RU allocation decision for the D2D pairs in IS1. As shown in Figure 5, the blue box denotes that Si and the corresponding D2D pair exist interference relationship, i.e., LSi,D1=1 and LSi,D2=1. Accordingly, the D1 and D2 cannot reuse the RU. Otherwise, the red box denotes the corresponding D2D pair, (i.e., D3 and D5) can share the current RU with Si due to LSi,D3=0 and LSi,D5=0. The resource allocation results for D3 and D5 are stored in DRi for ith RU; meanwhile, AP will update IS to make the number of D2D pairs in IS1 maximum.Figure 5
An example for allocating RU to D2D link pairs.


#### 3.2.4. Uplink Data Transmission Process

The uplink data transmission phase is performed when AP sends the TF frame. All nodes (i.e., STAs and D2D pairs) sense and parse the TF frame, where the TF frame contains all RU resource allocation results for STAs and D2D pairs. Based on this, each node can identify whether the AP has assigned RU for it or not. Assume that the uplink transmission period is fixed as the transmission opportunity (TXOP). Therefore, the corresponding nodes can share the same RU and transmit data in parallel. Moreover, AP will respond with the multiple block ACK (MBA) for the STAs which has successfully sent the data in uplink data transmission phase.


## 3.1. Architecture and Model

We consider an uplink transmission scenario in the single Basic Service Set (BSS) governed by IEEE 802.11ax, which supports two communication modes: AP forwarding and D2D offloading, where the D2D pair can communicate directly. As shown in Figure1, AP is deployed in the geometrical center of the BSS, and all nodes (i.e., STAs and D2D pairs) are randomly distributed in the coverage region of AP. Assume n STAs and m D2D pairs in the D2D-enable 802.11ax network. Let S=S1,S2,⋯,Sn and D=D1,D2,⋯,Dm denote the set of STAs and D2D pairs, respectively. AP and all nodes support MU transmissions which is a basic characteristic of 802.11ax. The whole channel is divided into r subchannels (referred to as RUs), denoted as R=R1,R2,⋯,Rr. To be more specific, the spectrum resource (i.e., RU) can be shared by the communication links under the two communication modes. Moreover, multiple D2D pairs meeting the interference conditions can share the same RU. Since the downlink transmission can be scheduled directly by AP and operated easily [29], this paper only focuses on the uplink data transmission. We also make an assumption that the network is in the saturated condition, i.e., all nodes in the network always have packets to send. Specifically, only STAs need to contend for channel by sending buffer status report (BSR) frame in uplink random access phase. Besides, the RU allocation decisions for STAs and D2D pairs are made by AP according to the interference relationship among nodes.Figure 1
The network scenario.


## 3.2. MISD Algorithm

This subsection details our proposed MISD algorithm. Firstly, we present an overview of the MISD algorithm. Then, the random access, resource allocation, and data transmission phases are introduced in detail, respectively.


### 3.2.1. MISD Overview

This paper concentrates on maximizing the spectrum efficiency by optimizing jointly random channel access and resource allocation in D2D-enabled 802.11ax, where the complex network scenario, i.e., multiple D2D pairs and RUs, is considered. To this end, we propose an efficient resource management algorithm MISD, which decouples the spectrum efficiency optimization problem into two subproblem in uplink random access and resource allocation phases. Correspondingly, the proposed MISD algorithm separates the channel time into a series of superframes, where each superframe includes uplink random access, resource allocation phase, and uplink data transmission phases, as shown in Figure2. Furthermore, the enhanced back-off mechanism and efficient resource allocation algorithm in resource allocation phase are developed for improving the spectrum efficiency in random access phase and data transmission phase, respectively. In particular, the STA contends for the RU based on the proposed enhanced back-off mechanism, independently; in resource allocation phase, AP allocates RUs for STAs and D2D pairs by the proposed efficient resource allocation algorithm; hence, the specific STA and D2D pairs can share the same RU for concurrent data transmission in data transmission phase.Figure 2
The channel access and data transmission process of MISD.


### 3.2.2. Random Access Process

In this subsection, we first establish a theoretical analysis model to derive the optimal contention windowCW∗ in order to maximize the system throughput in uplink random access phase. Then, we propose an enhanced back-off mechanism, where the STAs can contend for RUs with the CW∗ in both time and frequency domains.CW optimization. Let τ be the probability that a STA attempts to transmit data packet in the considered RU, which can be expressed as
(1)τ=21+CW,whereCW denotes the contention window for each uplink random access phase, which is calculated and broadcast by AP in the considered system model. Assume that the back-off value of AP is equal to CW.LetPtr denote the transmission probability, i.e., at least one transmission occurs in the considered RU. Therefore, Ptr can be expressed as
(2)Ptr=1−1−τn,wheren is the number of contending STAs. Let PI denote the idle probability, i.e., no transmission in the considered RU, which can be calculated by
(3)PI=1−τn.LetPs denote the probability of successful transmission in considered RU, i.e., only one STA transmits the packet in the considered RU. Accordingly, Ps can be obtained by
(4)Ps=n1−τn−1Ptr=n1−τn−11−1−τn.Analogously, the collision probabilityPc in the considered RU is expressed as Pc=Ptr−Ps. Therefore, the throughput for considered RU is
(5)SRU=PsPtrEP1−PtrTi+PsPtrTs+Ptr1−PsTc,whereEP denotes the average packet payload size. Ti denotes the duration of an empty slot. Ts and Tc are the average length of time periods for a successful packet and a collision packet, respectively. To reduce unnecessary control overheads, there is no ACK frame for each BSR frame in the proposed enhanced back-off mechanism. Consequently, assume that Ts=Tc as
(6)Ts=Tc=TBSR+2TSIFS,whereTBSR denotes the average length of time period for transmitting successfully a BSR frame. Analogously, TSIFS is short interframe space (SIFS). By substituting the above correlation formulas in (5), the SRU can be rewritten as
(7)SRU=EPn1−τn−11−τnTi+1−1−τnTc,where theEP is a fixed value for all nodes. To achieve the maximum theoretical throughput limitation, as seen in (7), we only need to maximize the following equation:
(8)θ=n1−τn−11−τnTi+1−1−τnTc.For a givenn, there exists an optimal CW∗ for maximizing the system throughput SRU in considered RU. Thus, taking the partial derivative in (8) with respect to τ, the derivative of (8) is given as
(9)dθdτ=n1−τn−21−nτTs+Ti−Ts1−τn+n2τTi−Ts1−τ2n−2Ts+Ti−Ts1−τn2=0.Using the simplification rule in [30], the expression of τ can be approximately derived from the following equation:
(10)τ=n+2n−1Ts′−1/n−1n−1/Ts′−1≈1nTs′/2,whereTs′=Ts/Ti. By simplifying and substituting the τ value in (1) into (10), we can obtain an approximate relationship between CW∗ and n from the following:
(11)CW∗≈n2TsTi.Based on the proposed theoretical analysis model, the optimalCW∗ can be calculated according to the variables, i.e., n, Ts, and Ti. In practical 802.11ax networks, these variables might be different and changed with respect to time. Compared to the STAs, AP can track these variables timely and adjust adaptively the CW∗ for optimizing the MAC access efficiency.Enhanced back-off mechanism. Different from the legacy uplink random access mechanism, the proposed enhanced back-off mechanism executes the back-off process in frequency and time domains, simultaneously. As shown in Figure 3, the uplink random access period includes multiple back-off substages and r available RUs in time and frequency domains, respectively. Let CWi=CW∗ denote the CW of STA i,i∈S. Accordingly, let boi∈0,CW∗ denote the back-off value of STA i.Figure 3
The uplink random access mechanism of MISD.LetSi denote the STAi,i∈S. In each back-off substage, Si updates its boi, as boi=boi−r. Specifically, if boi≤0, Si randomly chooses a RU and sends its BSR to AP. After that, the back-off value of Si will be reset as boi=CW∗. Note that the maximum back-off stages are limited by ∣CW∗/r∣; thus, each STA can contend for channel resource once during the current uplink random access phase. Let TSi∈0,1 denote the transmission result of BSR of Si, where TSi=1 denotes that AP has received successfully the BSR frame from Si; otherwise, TSi=0. Correspondingly, AP adds Si into the available scheduling stations set denoted as NS, while TSi=1. Repeat the back-off process until the number of STAs in NS is larger than r or uplink random access phase is over. Since the resource allocation results for data transmission will be announced by AP with the trigger frame (TF) frame, AP will not respond with ACK for each BSR frame in the proposed algorithm, which can reduce control overheads. More specifically, we summarize the enhanced back-off mechanism with optimal CW in Algorithm 1.Algorithm 1: The enhanced back-off mechanism
1: Initialize: Node setS, TSi=0,i∈S2: AP computesCW∗ by (11) and broadcasts it and r3:fori in Sdo:4:Si randomly select a value from 0,CW∗ as boi5:end for6:whilet≤∣CW∗/r∣do:7:foriinSdo:8:boi=boi−r9:ifboi≤0do:10:Si randomly choose a RU to send BSR11:if AP received BSR from Sido:12:TSi=1 and NS=NS∪Si13:end if14:boi=CW∗15:end if16:end for17:if∣NS∣≥rdo:18:      break19:end if20:t+=121:end while


### 3.2.3. Resource Allocation

The uplink resource allocation is executed while AP successfully sends the TF on the whole channel. To avoid the waste of channel resources, AP can schedule the downlink transmission during this phase. Since this paper only focuses on uplink resource allocation and data transmission, the downlink data scheduling and transmission processes are skipped. Note that, the resource reuse technology is employed in D2D-enabled 802.11ax network. Hence, AP can schedule multiple D2D pairs to share the same RU with the specific STA based on the efficient resource allocation algorithm, which significantly enhances the spectrum efficiency in data transmission. However, the resource allocation algorithm faces two key challenges: (1) identifying whether or not the STA and D2D link can share the same RU; (2) determining which D2D pairs can reuse the same RU. To tackle these challenges, the complex interference problems among D2D pairs and STAs have been effectively solved in the proposed resource allocation algorithm. Specifically, we introduce the interference graph and the conception of MIS to group the D2D pairs without interference into the same MIS. In addition, the interference matrix for D2D pairs and STAs, denoted asL, is established. Based on MIS and L, we develop an efficient resource allocation algorithm, where multiple D2D pairs and the STA are allowed to share the same RU. To describe the resource allocation mechanism in detail, we decouple it into three parts: formulating D2D interference graph and generating maximum independent set and resource allocation decision, and give the corresponding introduction as follows.Formulating D2D interference graph. The formulating algorithm of D2D interference graph is executed when D2D pairs are established or D2D pairs change. Let G=<V,E> denote the interference graph of D2D pairs. Note that G is constructed according to the interference relationship of D2D pairs. The vertexes in set V represent D2D pairs corresponding to D=D1,D2,⋯,Dm defined in Section 3.1. Besides, the edges in set E represent the interference relationship between D2D pairs defined by the SINR of receiver. It is considered that the communication links will be interfered, when the SINR of receiver of any link has less than the threshold. The instantaneous SINR of receiver for D2D pair is as
(12)SINRD=PDαDPNαN,D+No,wherePD is the transmit power of D2D communication device. αD is the path loss of the D2D pair, and αN,D can be represented as
(13)αN,D=λ4πρ2,whereρ is the distance of the two D2D pairs and λ is the wavelength of the signal.Figure4 shows an illustrative example of generating the interference graph of D2D pairs, where Figure 4(a) gives the network topology of D2D pairs. Based on this, the corresponding interference graph G is formulated in Figure 4(b). Referring to Figure 4(c), when the D1 and D2 transmit data packets in the same RU in parallel, both data links will be interfered, i.e., the communication links from Sender 1 to Receiver 1 and Sender 2 to Receiver 2 will cause the interference for Receiver 1 and Receiver 2, respectively. Accordingly, both Receiver 1 and Receiver 2 cannot receive data correctly. To avoid this issue, the proposed resource allocation algorithm introduces the MIS to avoid allocating the same RU for these interference links.Figure 4
Illustrative example of the interference graph of D2D pairs.
(a)
Network topology(b)
Interference graph(c)
Interference linkMaximum independent sets. In accordance with the graph theory, there is no adjacency between any two nodes of the same MIS. Inspired by this, we introduce the concept of MIS and divide the D2D pairs into multiple MISs according to their interference relationship in an iterative manner. Correspondingly, the D2D pairs without interference will be divided into the same MIS, which can share the same RU for parallel transmission. Note that, the process of generating the MISs is triggered when the interference graph is established or updated. Let IS=IS1,IS2,⋯,ISK denote the information of MISs, where the ISk,k∈1,K stores the D2D pairs’ IDs in the kth MIS. Note that the K varies with the interference graph. Let I=Ii,jm×m,i,j∈D denote the interference relationship between D2D pairs. Specifically, Ii,j can be expressed as
(14)Ii,j=1,mutualinterference,0,otherwise.Consequently, the D2D pairsi and j, where i,j∈ISk, can share the same RU to transmit data, simultaneously due to Ii,j=0. Algorithm 2 describes the procedure of generating MISs in detail. Once the D2D interference graph G is created or changed, AP will run Algorithm 2 to generate or update the IS. For a given interference graph G, it is easy to find the nodes which belongs to the MIS by judging the interference relationship between the D2D pairs in current MIS and the D2D pairs in V. If there is no interference relationship between the D2D pair i∈V and all D2D pairs in the kth MIS ISk, i.e., ∑j∈ISkIi,j=0, the D2D pair i will be added into ISk and removed from V. Repeat the above process to find the next MIS ISk+1 until the node set V is empty. Finally, AP sort IS in descending order, i.e., the number of D2D pairs in IS1 is maximum, which helps to reduce the computational complexity of resource allocation decision process and improve the decision efficiency.Algorithm 2: Generating maximum independent sets
Input:G=<V,E>, I=Ii,jm×m, i,j∈DOutput:IS=IS1,IS2,⋯,ISk1:k⟵02:whenV is not empty do3:k⟵k+1, Im⟵04:   Select a D2D pairv in V as the initial node5:   Addv into ISk, and remove it from V6:fori⟵0 to len(V) do7:forj⟵0 to len(ISk) do8:ifIi,j==1then9:Im⟵Im+110:          Break11:end if12:end for13:ifIm==0then14:      Add D2D pairj into ISk and remove it from V15:        UpdateISk16:end if17:end for18:end when19: Sort (IS)20:ReturnISResource allocation decision. This phase is triggered by the TF frame for maximizing the spectrum efficiency. Let the interference matrix L=Lsi,Din×m, where Si∈S and Di∈D denote the interference relationship of Si and Di. The Li,j can be expressed as
(15)Li,j=1,SiandDiinterferewitheachother,0,otherwise.In the proposed resource allocation algorithm, AP first allocates RUs for STA inNS. Note that NS is obtained in uplink random access phase. Subsequently, based on the IS and L, AP only needs to do match-action operation once to allocate the specific RU for D2D pairs. Accordingly, the time complexity of each match-action equals to the number of D2D pairs in IS1, denoted as m1m1≤m, and the m1 decreases gradually during RU allocation phase. Thus, the worst time complexity of the proposed RU allocation mechanism is Orm in r available RU scenario. Let Si denote the specific STA that can use the ith RU in data transmission phase. In each match-action operation for making the specific RU allocation decision, AP estimates the interference relationship among the Si and Dj∈IS1 only. In particular, AP will allocate the RU for Dj, only when LSi,Dj=0,Dj∈IS1, i.e., adding the Dj into set DRi and removing Dj from IS1, accordingly. Exceptionally, if no D2D pair in IS1 can share the RU with Si, AP will do the same match-action operation for the next MIS IS2 with the Si. After that, AP sorts IS in descending order. Since IS1 always includes maximum noninterference D2D pairs, AP always try to schedule more D2D pairs to share the same RU. Hence, the proposed resource allocation algorithm in MISD can significantly improve decision-making efficiency by enabling the match-action operation based on MISs, meanwhile maximizing spectrum efficiency by providing more spectrum reuse opportunities for nodes. Algorithm 3 depicts the pseudocode of the proposed resource allocation algorithm.Algorithm 3: Resource allocation decision algorithm
Input:NS, IS, L, rOutput:DR1: AP allocates RU for the STA inNS2:i⟵0, T⟵03:whenNS≠∅ or i≠rdo:4:c⟵05:STA⟵NSi6:forj⟵0 to lenSTdo:7:D←IS0j8:ifLSTA,D==0then:9:        AddD into DR and remove it from ST.10:c⟵c+1;11:end if12:end for13:ifc≠0then14:T⟵T+115:else16:      UpdateIS, T⟵117:end if18:i⟵i+1;19:end when20:ReturnDRWe present an example to illustrate the detail of the resource allocation procedure in the proposed algorithm, as described in Figure5. Firstly, AP will allocate a unique RU for each STA in NS. Consequently, these STAs can transmit simultaneously data in the specific RU in the next data transmission phase. To maximize the spectrum efficiency, the multiple D2D pairs are scheduled to share the specific RU based on the proposed resource allocation algorithm. More specifically, AP allocates the specific RU for Si∈NS, where IS1=D1,D2,D3,D5 and the interference relationship matrix of Si is LSi=1,1,0,0,0,1,1. The number of elements in LSi equals to m. Based on this, AP estimates the interference relationships by matching LSi and IS1 to make the RU allocation decision for the D2D pairs in IS1. As shown in Figure 5, the blue box denotes that Si and the corresponding D2D pair exist interference relationship, i.e., LSi,D1=1 and LSi,D2=1. Accordingly, the D1 and D2 cannot reuse the RU. Otherwise, the red box denotes the corresponding D2D pair, (i.e., D3 and D5) can share the current RU with Si due to LSi,D3=0 and LSi,D5=0. The resource allocation results for D3 and D5 are stored in DRi for ith RU; meanwhile, AP will update IS to make the number of D2D pairs in IS1 maximum.Figure 5
An example for allocating RU to D2D link pairs.


### 3.2.4. Uplink Data Transmission Process

The uplink data transmission phase is performed when AP sends the TF frame. All nodes (i.e., STAs and D2D pairs) sense and parse the TF frame, where the TF frame contains all RU resource allocation results for STAs and D2D pairs. Based on this, each node can identify whether the AP has assigned RU for it or not. Assume that the uplink transmission period is fixed as the transmission opportunity (TXOP). Therefore, the corresponding nodes can share the same RU and transmit data in parallel. Moreover, AP will respond with the multiple block ACK (MBA) for the STAs which has successfully sent the data in uplink data transmission phase.


## 3.2.1. MISD Overview

This paper concentrates on maximizing the spectrum efficiency by optimizing jointly random channel access and resource allocation in D2D-enabled 802.11ax, where the complex network scenario, i.e., multiple D2D pairs and RUs, is considered. To this end, we propose an efficient resource management algorithm MISD, which decouples the spectrum efficiency optimization problem into two subproblem in uplink random access and resource allocation phases. Correspondingly, the proposed MISD algorithm separates the channel time into a series of superframes, where each superframe includes uplink random access, resource allocation phase, and uplink data transmission phases, as shown in Figure2. Furthermore, the enhanced back-off mechanism and efficient resource allocation algorithm in resource allocation phase are developed for improving the spectrum efficiency in random access phase and data transmission phase, respectively. In particular, the STA contends for the RU based on the proposed enhanced back-off mechanism, independently; in resource allocation phase, AP allocates RUs for STAs and D2D pairs by the proposed efficient resource allocation algorithm; hence, the specific STA and D2D pairs can share the same RU for concurrent data transmission in data transmission phase.Figure 2
The channel access and data transmission process of MISD.


## 3.2.2. Random Access Process

In this subsection, we first establish a theoretical analysis model to derive the optimal contention windowCW∗ in order to maximize the system throughput in uplink random access phase. Then, we propose an enhanced back-off mechanism, where the STAs can contend for RUs with the CW∗ in both time and frequency domains.CW optimization. Let τ be the probability that a STA attempts to transmit data packet in the considered RU, which can be expressed as
(1)τ=21+CW,whereCW denotes the contention window for each uplink random access phase, which is calculated and broadcast by AP in the considered system model. Assume that the back-off value of AP is equal to CW.LetPtr denote the transmission probability, i.e., at least one transmission occurs in the considered RU. Therefore, Ptr can be expressed as
(2)Ptr=1−1−τn,wheren is the number of contending STAs. Let PI denote the idle probability, i.e., no transmission in the considered RU, which can be calculated by
(3)PI=1−τn.LetPs denote the probability of successful transmission in considered RU, i.e., only one STA transmits the packet in the considered RU. Accordingly, Ps can be obtained by
(4)Ps=n1−τn−1Ptr=n1−τn−11−1−τn.Analogously, the collision probabilityPc in the considered RU is expressed as Pc=Ptr−Ps. Therefore, the throughput for considered RU is
(5)SRU=PsPtrEP1−PtrTi+PsPtrTs+Ptr1−PsTc,whereEP denotes the average packet payload size. Ti denotes the duration of an empty slot. Ts and Tc are the average length of time periods for a successful packet and a collision packet, respectively. To reduce unnecessary control overheads, there is no ACK frame for each BSR frame in the proposed enhanced back-off mechanism. Consequently, assume that Ts=Tc as
(6)Ts=Tc=TBSR+2TSIFS,whereTBSR denotes the average length of time period for transmitting successfully a BSR frame. Analogously, TSIFS is short interframe space (SIFS). By substituting the above correlation formulas in (5), the SRU can be rewritten as
(7)SRU=EPn1−τn−11−τnTi+1−1−τnTc,where theEP is a fixed value for all nodes. To achieve the maximum theoretical throughput limitation, as seen in (7), we only need to maximize the following equation:
(8)θ=n1−τn−11−τnTi+1−1−τnTc.For a givenn, there exists an optimal CW∗ for maximizing the system throughput SRU in considered RU. Thus, taking the partial derivative in (8) with respect to τ, the derivative of (8) is given as
(9)dθdτ=n1−τn−21−nτTs+Ti−Ts1−τn+n2τTi−Ts1−τ2n−2Ts+Ti−Ts1−τn2=0.Using the simplification rule in [30], the expression of τ can be approximately derived from the following equation:
(10)τ=n+2n−1Ts′−1/n−1n−1/Ts′−1≈1nTs′/2,whereTs′=Ts/Ti. By simplifying and substituting the τ value in (1) into (10), we can obtain an approximate relationship between CW∗ and n from the following:
(11)CW∗≈n2TsTi.Based on the proposed theoretical analysis model, the optimalCW∗ can be calculated according to the variables, i.e., n, Ts, and Ti. In practical 802.11ax networks, these variables might be different and changed with respect to time. Compared to the STAs, AP can track these variables timely and adjust adaptively the CW∗ for optimizing the MAC access efficiency.Enhanced back-off mechanism. Different from the legacy uplink random access mechanism, the proposed enhanced back-off mechanism executes the back-off process in frequency and time domains, simultaneously. As shown in Figure 3, the uplink random access period includes multiple back-off substages and r available RUs in time and frequency domains, respectively. Let CWi=CW∗ denote the CW of STA i,i∈S. Accordingly, let boi∈0,CW∗ denote the back-off value of STA i.Figure 3
The uplink random access mechanism of MISD.LetSi denote the STAi,i∈S. In each back-off substage, Si updates its boi, as boi=boi−r. Specifically, if boi≤0, Si randomly chooses a RU and sends its BSR to AP. After that, the back-off value of Si will be reset as boi=CW∗. Note that the maximum back-off stages are limited by ∣CW∗/r∣; thus, each STA can contend for channel resource once during the current uplink random access phase. Let TSi∈0,1 denote the transmission result of BSR of Si, where TSi=1 denotes that AP has received successfully the BSR frame from Si; otherwise, TSi=0. Correspondingly, AP adds Si into the available scheduling stations set denoted as NS, while TSi=1. Repeat the back-off process until the number of STAs in NS is larger than r or uplink random access phase is over. Since the resource allocation results for data transmission will be announced by AP with the trigger frame (TF) frame, AP will not respond with ACK for each BSR frame in the proposed algorithm, which can reduce control overheads. More specifically, we summarize the enhanced back-off mechanism with optimal CW in Algorithm 1.Algorithm 1: The enhanced back-off mechanism
1: Initialize: Node setS, TSi=0,i∈S2: AP computesCW∗ by (11) and broadcasts it and r3:fori in Sdo:4:Si randomly select a value from 0,CW∗ as boi5:end for6:whilet≤∣CW∗/r∣do:7:foriinSdo:8:boi=boi−r9:ifboi≤0do:10:Si randomly choose a RU to send BSR11:if AP received BSR from Sido:12:TSi=1 and NS=NS∪Si13:end if14:boi=CW∗15:end if16:end for17:if∣NS∣≥rdo:18:      break19:end if20:t+=121:end while


## 3.2.3. Resource Allocation

The uplink resource allocation is executed while AP successfully sends the TF on the whole channel. To avoid the waste of channel resources, AP can schedule the downlink transmission during this phase. Since this paper only focuses on uplink resource allocation and data transmission, the downlink data scheduling and transmission processes are skipped. Note that, the resource reuse technology is employed in D2D-enabled 802.11ax network. Hence, AP can schedule multiple D2D pairs to share the same RU with the specific STA based on the efficient resource allocation algorithm, which significantly enhances the spectrum efficiency in data transmission. However, the resource allocation algorithm faces two key challenges: (1) identifying whether or not the STA and D2D link can share the same RU; (2) determining which D2D pairs can reuse the same RU. To tackle these challenges, the complex interference problems among D2D pairs and STAs have been effectively solved in the proposed resource allocation algorithm. Specifically, we introduce the interference graph and the conception of MIS to group the D2D pairs without interference into the same MIS. In addition, the interference matrix for D2D pairs and STAs, denoted asL, is established. Based on MIS and L, we develop an efficient resource allocation algorithm, where multiple D2D pairs and the STA are allowed to share the same RU. To describe the resource allocation mechanism in detail, we decouple it into three parts: formulating D2D interference graph and generating maximum independent set and resource allocation decision, and give the corresponding introduction as follows.Formulating D2D interference graph. The formulating algorithm of D2D interference graph is executed when D2D pairs are established or D2D pairs change. Let G=<V,E> denote the interference graph of D2D pairs. Note that G is constructed according to the interference relationship of D2D pairs. The vertexes in set V represent D2D pairs corresponding to D=D1,D2,⋯,Dm defined in Section 3.1. Besides, the edges in set E represent the interference relationship between D2D pairs defined by the SINR of receiver. It is considered that the communication links will be interfered, when the SINR of receiver of any link has less than the threshold. The instantaneous SINR of receiver for D2D pair is as
(12)SINRD=PDαDPNαN,D+No,wherePD is the transmit power of D2D communication device. αD is the path loss of the D2D pair, and αN,D can be represented as
(13)αN,D=λ4πρ2,whereρ is the distance of the two D2D pairs and λ is the wavelength of the signal.Figure4 shows an illustrative example of generating the interference graph of D2D pairs, where Figure 4(a) gives the network topology of D2D pairs. Based on this, the corresponding interference graph G is formulated in Figure 4(b). Referring to Figure 4(c), when the D1 and D2 transmit data packets in the same RU in parallel, both data links will be interfered, i.e., the communication links from Sender 1 to Receiver 1 and Sender 2 to Receiver 2 will cause the interference for Receiver 1 and Receiver 2, respectively. Accordingly, both Receiver 1 and Receiver 2 cannot receive data correctly. To avoid this issue, the proposed resource allocation algorithm introduces the MIS to avoid allocating the same RU for these interference links.Figure 4
Illustrative example of the interference graph of D2D pairs.
(a)
Network topology(b)
Interference graph(c)
Interference linkMaximum independent sets. In accordance with the graph theory, there is no adjacency between any two nodes of the same MIS. Inspired by this, we introduce the concept of MIS and divide the D2D pairs into multiple MISs according to their interference relationship in an iterative manner. Correspondingly, the D2D pairs without interference will be divided into the same MIS, which can share the same RU for parallel transmission. Note that, the process of generating the MISs is triggered when the interference graph is established or updated. Let IS=IS1,IS2,⋯,ISK denote the information of MISs, where the ISk,k∈1,K stores the D2D pairs’ IDs in the kth MIS. Note that the K varies with the interference graph. Let I=Ii,jm×m,i,j∈D denote the interference relationship between D2D pairs. Specifically, Ii,j can be expressed as
(14)Ii,j=1,mutualinterference,0,otherwise.Consequently, the D2D pairsi and j, where i,j∈ISk, can share the same RU to transmit data, simultaneously due to Ii,j=0. Algorithm 2 describes the procedure of generating MISs in detail. Once the D2D interference graph G is created or changed, AP will run Algorithm 2 to generate or update the IS. For a given interference graph G, it is easy to find the nodes which belongs to the MIS by judging the interference relationship between the D2D pairs in current MIS and the D2D pairs in V. If there is no interference relationship between the D2D pair i∈V and all D2D pairs in the kth MIS ISk, i.e., ∑j∈ISkIi,j=0, the D2D pair i will be added into ISk and removed from V. Repeat the above process to find the next MIS ISk+1 until the node set V is empty. Finally, AP sort IS in descending order, i.e., the number of D2D pairs in IS1 is maximum, which helps to reduce the computational complexity of resource allocation decision process and improve the decision efficiency.Algorithm 2: Generating maximum independent sets
Input:G=<V,E>, I=Ii,jm×m, i,j∈DOutput:IS=IS1,IS2,⋯,ISk1:k⟵02:whenV is not empty do3:k⟵k+1, Im⟵04:   Select a D2D pairv in V as the initial node5:   Addv into ISk, and remove it from V6:fori⟵0 to len(V) do7:forj⟵0 to len(ISk) do8:ifIi,j==1then9:Im⟵Im+110:          Break11:end if12:end for13:ifIm==0then14:      Add D2D pairj into ISk and remove it from V15:        UpdateISk16:end if17:end for18:end when19: Sort (IS)20:ReturnISResource allocation decision. This phase is triggered by the TF frame for maximizing the spectrum efficiency. Let the interference matrix L=Lsi,Din×m, where Si∈S and Di∈D denote the interference relationship of Si and Di. The Li,j can be expressed as
(15)Li,j=1,SiandDiinterferewitheachother,0,otherwise.In the proposed resource allocation algorithm, AP first allocates RUs for STA inNS. Note that NS is obtained in uplink random access phase. Subsequently, based on the IS and L, AP only needs to do match-action operation once to allocate the specific RU for D2D pairs. Accordingly, the time complexity of each match-action equals to the number of D2D pairs in IS1, denoted as m1m1≤m, and the m1 decreases gradually during RU allocation phase. Thus, the worst time complexity of the proposed RU allocation mechanism is Orm in r available RU scenario. Let Si denote the specific STA that can use the ith RU in data transmission phase. In each match-action operation for making the specific RU allocation decision, AP estimates the interference relationship among the Si and Dj∈IS1 only. In particular, AP will allocate the RU for Dj, only when LSi,Dj=0,Dj∈IS1, i.e., adding the Dj into set DRi and removing Dj from IS1, accordingly. Exceptionally, if no D2D pair in IS1 can share the RU with Si, AP will do the same match-action operation for the next MIS IS2 with the Si. After that, AP sorts IS in descending order. Since IS1 always includes maximum noninterference D2D pairs, AP always try to schedule more D2D pairs to share the same RU. Hence, the proposed resource allocation algorithm in MISD can significantly improve decision-making efficiency by enabling the match-action operation based on MISs, meanwhile maximizing spectrum efficiency by providing more spectrum reuse opportunities for nodes. Algorithm 3 depicts the pseudocode of the proposed resource allocation algorithm.Algorithm 3: Resource allocation decision algorithm
Input:NS, IS, L, rOutput:DR1: AP allocates RU for the STA inNS2:i⟵0, T⟵03:whenNS≠∅ or i≠rdo:4:c⟵05:STA⟵NSi6:forj⟵0 to lenSTdo:7:D←IS0j8:ifLSTA,D==0then:9:        AddD into DR and remove it from ST.10:c⟵c+1;11:end if12:end for13:ifc≠0then14:T⟵T+115:else16:      UpdateIS, T⟵117:end if18:i⟵i+1;19:end when20:ReturnDRWe present an example to illustrate the detail of the resource allocation procedure in the proposed algorithm, as described in Figure5. Firstly, AP will allocate a unique RU for each STA in NS. Consequently, these STAs can transmit simultaneously data in the specific RU in the next data transmission phase. To maximize the spectrum efficiency, the multiple D2D pairs are scheduled to share the specific RU based on the proposed resource allocation algorithm. More specifically, AP allocates the specific RU for Si∈NS, where IS1=D1,D2,D3,D5 and the interference relationship matrix of Si is LSi=1,1,0,0,0,1,1. The number of elements in LSi equals to m. Based on this, AP estimates the interference relationships by matching LSi and IS1 to make the RU allocation decision for the D2D pairs in IS1. As shown in Figure 5, the blue box denotes that Si and the corresponding D2D pair exist interference relationship, i.e., LSi,D1=1 and LSi,D2=1. Accordingly, the D1 and D2 cannot reuse the RU. Otherwise, the red box denotes the corresponding D2D pair, (i.e., D3 and D5) can share the current RU with Si due to LSi,D3=0 and LSi,D5=0. The resource allocation results for D3 and D5 are stored in DRi for ith RU; meanwhile, AP will update IS to make the number of D2D pairs in IS1 maximum.Figure 5
An example for allocating RU to D2D link pairs.


## 3.2.4. Uplink Data Transmission Process

The uplink data transmission phase is performed when AP sends the TF frame. All nodes (i.e., STAs and D2D pairs) sense and parse the TF frame, where the TF frame contains all RU resource allocation results for STAs and D2D pairs. Based on this, each node can identify whether the AP has assigned RU for it or not. Assume that the uplink transmission period is fixed as the transmission opportunity (TXOP). Therefore, the corresponding nodes can share the same RU and transmit data in parallel. Moreover, AP will respond with the multiple block ACK (MBA) for the STAs which has successfully sent the data in uplink data transmission phase.


## 4. Numerical Analysis

In this section, we model and derive the system throughput in uplink random access phase. As mentioned in Section3, the channel is divided into r RUs. Assume that all RUs are available in uplink random access phase for STAs. Similar to the legacy 802.11 network, we consider that there is no hidden terminal in network. Meanwhile, we assume that the channel condition is ideal and the packet error occurs only when multiple STAs transmit BSR frame in the same RU, simultaneously. Different from legacy DCF mechanism, we redefine the channel states as idle, successful transmission, and collision, according to the states of r RUs in the same time domain. In particular, the detail description is shown in Figure 6.Figure 6
Illustration of channel status on time domain.LetPI′ denote the probability of channel idle, i.e., all RUs are in idle states, in the same time domain. Ps′ presents the successful transmission probability of channel, i.e., at least one RU is in successful transmission state and others are in idle states in the same time domain. Similarly, Pc′ denotes the collision probability of channel, i.e., at least one RU has occurred collision in the same time domain. Specifically, Ps′ and PI′ are expressed as
(16)Ps′=∑i=1rPsiPIr−i,(17)PI′=PIr.Consider thatr available RUs can be used for different STAs to transmit BSR in the same slot in the proposed algorithm. Correspondingly, we can calculate the system throughput ST in uplink random access phase by the formula derived in Section 3, which can be expressed as
(18)ST=∑k=1rPsEPPs′Ts+Pi′Ti+1−Ps′−Pc′Tc.Consequently, by substituting the above correlation formulas in (16) and (17), the system throughput ST in (18) can be rewritten as the following:
(19)ST=rPsEP1−∏i=1rPiTs+∏i=1rPiTi=rnτ1−τn−1EP1−τ1−τnrTs+1−τnrTi.Hence, the system throughput of the uplink random access phase in the MISD algorithm is determined byr, n, Ps, and Ts. Thereby, the maximum system throughput in uplink random access phase can be obtained by employing the optimal CW for a given n and Ts, which has been derived in Section 3.2.2. Moreover, by integrating D2D into 802.11ax network, less nodes n need to contend for channel resource, and hence, Ps in MISD can be further optimized especially in dense scenarios. Meanwhile, it also reduces the invalid channel occupancy time by canceling ACK for BSR, i.e., the transmission time for data Ts is increased. Obviously, the MAC access efficiency can be improved by enabling the enhanced back-off mechanism with the optimal CW in MISD. Besides, the higher MAC access efficiency implies that the more channel time can be used for data transmission, which indirectly optimizes the spectrum efficiency.


## 5. Performance Simulation

### 5.1. Evaluation Settings

In this section, we conduct extensive simulations to evaluate and analyze the performance of the proposed algorithm in terms of system throughput, completion time, collision rate, and channel utilization using a custom simulator in Matlab. The proposed algorithm is compared with the legacy 802.11ax, G-OFDMA, and InGRA [31]. InGRA is an efficient resource allocation scheme for D2D link pairs in cellular network, and the related simulation results indicate that it also obtains the good performance in WLANs. Table 1 summarizes the related simulation parameters. In the simulations, we focus on uplink transmission condition in a single BSS scenario. Wherein, AP is deployed at the center of a circle with a radius of 100 m and acts as a centralized controller to allocate RU resource and schedule uplink transmission. All nodes (10-100) including STAs and D2D pairs are saturated states and randomly distributed in the simulation field. In particular, the maximum distance between the receiver and transmitter for each D2D pair is less than 30 m. We consider the channel bandwidth is 40 MHz, which is divided into 8 or 18 RUs. Moreover, each simulation run lasts 100 s and the corresponding result is averaged over 10 independent experiments.Table 1
Simulation parameters.
ParametersValueParametersValueSubchannel number8 or 18Channel bandwidth40 MHzSIFS20 usData rate12 or 6 MbpsSlot time10 usCWmin15DIFS50 usCWmax64B-ACK length144 bitsMAC header length240 bitsPacket length1500 bytesPhysical header length120 bits


### 5.2. Simulation Results

In what follows, we consider two simulation scenarios: (1) different number of node (10-100) scenario, where the number of D2D pairs varies with the network topology; (2) different number of D2D pairs (4-28) for a given number of node (100) scenario. Besides, the impact of different RUs (8 and 18) on network performance is considered in both cases. Besides, we investigate the performance of system throughput, completion time, channel utilization, and collision rate, respectively.


#### 5.2.1. Different Number of Nodes

Figure7 illustrates the impact of the different number of nodes on system throughput when the MISD, 802.11ax, G-OFDMA, and InGRA algorithms are used in first considered simulation scenario. Referring to Figure 7, both the proposed MISD and InGRA algorithms have achieved the significant performance improvements in terms of the system throughput, especially in dense scenarios. This result is expected because D2D communication and the channel resource reuse technologies are exploited in both algorithms. Meanwhile, as the increasing of nodes in the network, nodes are offloaded to D2D communication mode with higher probability. Correspondingly, less STAs need to contend channel in uplink random access phase and more D2D pairs can transmit packets in parallel, which improves spectrum access efficiency and further increases spectrum reuse probability. In MISD, AP can schedule more D2D pairs to share the same RU, since it always preferentially allocates RU for the D2D pairs in the largest MIS, which achieves higher resource reuse than InGRA. Particularly, while the number of nodes is less than 30, the G-OFDMA outperforms the MISD in 18 RU scenario. However, the throughput performance of G-OFDMA is almost unchanged as the number of nodes increases. The main reason is that the G-OFDMA adapts the fixed uplink random access stages and the maximum system throughput is limited by the available RUs.Figure 7
System throughput vs. different nodes.Figure8 compares the variation of the average completion time for transmitting 1 Mega bit file when OFDMA-based algorithms and D2D offloading in OFDMA algorithms are used, respectively. Note that more transmission opportunities and higher successful transmission probability can reduce the completion time of transmitting the given data. Irrespective of the number of nodes, both MISD and InGRA algorithms yield the better performance in terms of completion time than that of the legacy 802.11ax and G-OFDMA. This is due to the fact that both MISD and InGRA algorithms offload nodes to D2D communication mode, where D2D pairs can share the spectrum resource with STAs for data transmission, i.e., more nodes can access channel to transmit data, simultaneously, which gives more transmission opportunities for nodes. It also can be observed that the completion time of four algorithms markedly increases with the increases of nodes. Compared with 802.11ax and G-OFDMA, the performance of MISD is significantly improved and outperforms InGRA in most cases. More specifically, the completion time of MISD is 76%, 62%, and 5% less than that of the 802.11ax, G-OFDMA, and InGRA, respectively (8 RUs and 100 nodes). This can be attributed to two factors: (1) the MISD algorithm relieves the data collision in uplink random access by offloading nodes to D2D communication mode and providing higher successful transmission probability for STAs with the enhanced back-off mechanism; (2) in MISD, AP schedules multiple D2D pairs and STA to share the same RU with low time complexity and offers more transmission opportunity for D2D pairs based on the MISs.Figure 8
Completion time vs. different nodes.Figure9 compares the collision rate of the four algorithms, where the number of nodes ranges from 10 to 100, where both 8 and 18 RU cases are considered. Note that the collision rate results are directly related to the uplink random access mechanism and the number of contention nodes. The results depicted in Figure 9 are diverse. The collision rate increases with the increasing number of nodes in both 802.11ax and InGRA. However, the results are almost unchanged for G-OFDMA. More interestingly, the collision rate of MISD decreases as the number of nodes increases. In particular, the collision rate gain of MISD is 64%, 44%, and 64% compared with 802.11ax, G-OFDMA, and InGRA in the case of 8 RUs and 100 nodes, respectively. This can be explained by the fact that the proposed MISD algorithm reduces the number of contention nodes by enabling D2D offloading technique and the proposed enhanced back-off mechanism further relieves data collision by allowing STA access channel only once. Hence, the number of STAs contending for channel has been greatly reduced. Besides, AP derives the optimal CW according to the network condition, which reduces the unnecessary data collisions so as to enhance MAC access efficiency.Figure 9
Collision rate vs. different nodes.Figure10 compares the channel utilization of the four algorithms as a function of the number of nodes. It can be observed that the trends of channel utilization results of all algorithms are almost similar with the number of node changes, since the OFDMA technology has been enabled in all algorithms and each RU will be used for at least one node (STA or D2D pair) to transmit data during uplink transmission phase. As a result, the channel utilization performance is limited by the available RUs and total data transmission time. For both D2D offloading algorithms, i.e., MISD and InGRA can obtain the higher channel utilization compared to the 802.11ax and G-OFDMA under different network densities. This is due to the fact that the MAC access efficiency in uplink random access phase can be improved by reducing the number of contention nodes and hence all nodes have more opportunities to transmit data instead of contending channel resource for the given simulation time.Figure 10
Channel utilization vs. different nodes.


#### 5.2.2. Different Number of D2D Link Pairs

In this subsection, we deploy 100 nodes as a dense scenario and further evaluate the performance of MISD with different numbers of D2D pairs. Wherein, we set the number of D2D pairs from 4 to 28 by limiting the total number of D2D pairs under the same network topology. Besides, different numbers of RUs (8 and 18) are considered in this scenario.Figure11 plots the system throughput versus the number of D2D pairs when the MISD and InGRA are used, respectively. It is evident that the system throughput results of MISD and InGRA increase as the number of D2D pairs increases. Moreover, both two algorithms have similar system throughput when the number of D2D pairs is less than 8. The result is reasonable because the system throughput gain is limited by the number of D2D pairs while it is less than the available RU. However, as the number of D2D pairs increases, the throughput performance of MISD is better than InGRA. In particular, when the number of D2D pairs is 28, the system throughput of MISD is higher than that of InGRA by about 21% and 11% under 8 and 18 RUs, respectively. The results confirm that the proposed MISD algorithm effectively improves the spectrum reuse efficiency by scheduling more D2D pairs to share the same RU with the higher probability based on the MISs compared to the InGRA especially in the dense network. Moreover, MISD exploits an enhanced back-off mechanism including adaptive CW adjustment strategy, which reduces the control overheads and further improves the MAC access efficiency in uplink random access phase.Figure 11
System throughput vs. different D2D pairs.Figure12 compares the collision rate of the two algorithms as a function of the number of D2D pairs. The collision rate decreases with the increasing number of D2D pairs in both algorithms, where the collision only occurs in uplink random access phase in both algorithms. Reasonably, the number of STAs will decrease with the number of the D2D pairs that increases for the given number of node scenario. Moreover, it is obvious that the collision rate of using the proposed MISD algorithm is lower than that of the InGRA algorithm. More specifically, the collision rate of MISD can be reduced by 64% over InGRA under 28 D2D pairs and 8 RU case. The result is intuitive because that the proposed MISD algorithm exploits an enhanced back-off mechanism, in which each STA employs the optimal CW to choose its back-off value and only contends channel once. Thus, the collision can be effectively relieved by reducing the number of the contention STAs so as to avoid secondary collision in considered random access phase in MISD.Figure 12
Collision rate vs. different D2D pairs.Figure13 illustrates the variation of the average completion time for transmitting 1 Mega bit file, when the MISD and InGRA algorithms are used. The completion time results for the two algorithms decrease with the increasing of D2D pairs. This result is expected because, for the given number of nodes, more nodes adopt the D2D communication mode that is beneficial not only in reducing the time for uplink random access but also in providing more data transmission opportunities for nodes by enabling spectrum reuse technology. Hence, the node can access the specific RU and transmit data quickly even in highly dense D2D pair scenario. Besides, it can be observed that the completion time of the proposed MISD is slightly lower than that of InGRA. Specifically, when the number of D2D pairs is 28, the MISD achieves about 4% and 2% performance improvement over InGRA with 8 and 18 RUs, respectively. The slight improvement in performance can be attributed to the enhanced back-off mechanism in MISD, where AP will not respond to ACK for each BSR which reduces the channel overheads. Moreover, the optimal CW is enabled to enhance the MAC access efficiency. Consequently, AP can schedule nodes (D2D pairs and STAs) to transmit data timely in data transmission period with the proposed MISD algorithm.Figure 13
Completion time vs. different D2D pairs.In this simulation, we further evaluate the impact of the number of D2D pairs on the performance of channel utilization. Referring to Figure14, both InGRA and MISD can achieve high channel utilization especially in highly dense network scenarios by offloading nodes to D2D communication mode. The channel utilization results are near-optimal because the RU resources are fully used by STAs and D2D pairs according to the direct scheduling of AP during the uplink transmission phase. Besides, simulation results of channel utilization also confirm that enabling D2D offloading schemes in 802.11ax is beneficial not only in improving the spectrum efficiency by enabling resource reuse technology in scheduling mode but also in shortening the period of the random-access process by reducing the number of contention nodes. As a result, high channel utilization can be obtained in both uplink random access and data transmission phases.Figure 14
Channel utilization vs. different D2D pairs.


## 5.1. Evaluation Settings

In this section, we conduct extensive simulations to evaluate and analyze the performance of the proposed algorithm in terms of system throughput, completion time, collision rate, and channel utilization using a custom simulator in Matlab. The proposed algorithm is compared with the legacy 802.11ax, G-OFDMA, and InGRA [31]. InGRA is an efficient resource allocation scheme for D2D link pairs in cellular network, and the related simulation results indicate that it also obtains the good performance in WLANs. Table 1 summarizes the related simulation parameters. In the simulations, we focus on uplink transmission condition in a single BSS scenario. Wherein, AP is deployed at the center of a circle with a radius of 100 m and acts as a centralized controller to allocate RU resource and schedule uplink transmission. All nodes (10-100) including STAs and D2D pairs are saturated states and randomly distributed in the simulation field. In particular, the maximum distance between the receiver and transmitter for each D2D pair is less than 30 m. We consider the channel bandwidth is 40 MHz, which is divided into 8 or 18 RUs. Moreover, each simulation run lasts 100 s and the corresponding result is averaged over 10 independent experiments.Table 1
Simulation parameters.
ParametersValueParametersValueSubchannel number8 or 18Channel bandwidth40 MHzSIFS20 usData rate12 or 6 MbpsSlot time10 usCWmin15DIFS50 usCWmax64B-ACK length144 bitsMAC header length240 bitsPacket length1500 bytesPhysical header length120 bits


## 5.2. Simulation Results

In what follows, we consider two simulation scenarios: (1) different number of node (10-100) scenario, where the number of D2D pairs varies with the network topology; (2) different number of D2D pairs (4-28) for a given number of node (100) scenario. Besides, the impact of different RUs (8 and 18) on network performance is considered in both cases. Besides, we investigate the performance of system throughput, completion time, channel utilization, and collision rate, respectively.


### 5.2.1. Different Number of Nodes

Figure7 illustrates the impact of the different number of nodes on system throughput when the MISD, 802.11ax, G-OFDMA, and InGRA algorithms are used in first considered simulation scenario. Referring to Figure 7, both the proposed MISD and InGRA algorithms have achieved the significant performance improvements in terms of the system throughput, especially in dense scenarios. This result is expected because D2D communication and the channel resource reuse technologies are exploited in both algorithms. Meanwhile, as the increasing of nodes in the network, nodes are offloaded to D2D communication mode with higher probability. Correspondingly, less STAs need to contend channel in uplink random access phase and more D2D pairs can transmit packets in parallel, which improves spectrum access efficiency and further increases spectrum reuse probability. In MISD, AP can schedule more D2D pairs to share the same RU, since it always preferentially allocates RU for the D2D pairs in the largest MIS, which achieves higher resource reuse than InGRA. Particularly, while the number of nodes is less than 30, the G-OFDMA outperforms the MISD in 18 RU scenario. However, the throughput performance of G-OFDMA is almost unchanged as the number of nodes increases. The main reason is that the G-OFDMA adapts the fixed uplink random access stages and the maximum system throughput is limited by the available RUs.Figure 7
System throughput vs. different nodes.Figure8 compares the variation of the average completion time for transmitting 1 Mega bit file when OFDMA-based algorithms and D2D offloading in OFDMA algorithms are used, respectively. Note that more transmission opportunities and higher successful transmission probability can reduce the completion time of transmitting the given data. Irrespective of the number of nodes, both MISD and InGRA algorithms yield the better performance in terms of completion time than that of the legacy 802.11ax and G-OFDMA. This is due to the fact that both MISD and InGRA algorithms offload nodes to D2D communication mode, where D2D pairs can share the spectrum resource with STAs for data transmission, i.e., more nodes can access channel to transmit data, simultaneously, which gives more transmission opportunities for nodes. It also can be observed that the completion time of four algorithms markedly increases with the increases of nodes. Compared with 802.11ax and G-OFDMA, the performance of MISD is significantly improved and outperforms InGRA in most cases. More specifically, the completion time of MISD is 76%, 62%, and 5% less than that of the 802.11ax, G-OFDMA, and InGRA, respectively (8 RUs and 100 nodes). This can be attributed to two factors: (1) the MISD algorithm relieves the data collision in uplink random access by offloading nodes to D2D communication mode and providing higher successful transmission probability for STAs with the enhanced back-off mechanism; (2) in MISD, AP schedules multiple D2D pairs and STA to share the same RU with low time complexity and offers more transmission opportunity for D2D pairs based on the MISs.Figure 8
Completion time vs. different nodes.Figure9 compares the collision rate of the four algorithms, where the number of nodes ranges from 10 to 100, where both 8 and 18 RU cases are considered. Note that the collision rate results are directly related to the uplink random access mechanism and the number of contention nodes. The results depicted in Figure 9 are diverse. The collision rate increases with the increasing number of nodes in both 802.11ax and InGRA. However, the results are almost unchanged for G-OFDMA. More interestingly, the collision rate of MISD decreases as the number of nodes increases. In particular, the collision rate gain of MISD is 64%, 44%, and 64% compared with 802.11ax, G-OFDMA, and InGRA in the case of 8 RUs and 100 nodes, respectively. This can be explained by the fact that the proposed MISD algorithm reduces the number of contention nodes by enabling D2D offloading technique and the proposed enhanced back-off mechanism further relieves data collision by allowing STA access channel only once. Hence, the number of STAs contending for channel has been greatly reduced. Besides, AP derives the optimal CW according to the network condition, which reduces the unnecessary data collisions so as to enhance MAC access efficiency.Figure 9
Collision rate vs. different nodes.Figure10 compares the channel utilization of the four algorithms as a function of the number of nodes. It can be observed that the trends of channel utilization results of all algorithms are almost similar with the number of node changes, since the OFDMA technology has been enabled in all algorithms and each RU will be used for at least one node (STA or D2D pair) to transmit data during uplink transmission phase. As a result, the channel utilization performance is limited by the available RUs and total data transmission time. For both D2D offloading algorithms, i.e., MISD and InGRA can obtain the higher channel utilization compared to the 802.11ax and G-OFDMA under different network densities. This is due to the fact that the MAC access efficiency in uplink random access phase can be improved by reducing the number of contention nodes and hence all nodes have more opportunities to transmit data instead of contending channel resource for the given simulation time.Figure 10
Channel utilization vs. different nodes.


### 5.2.2. Different Number of D2D Link Pairs

In this subsection, we deploy 100 nodes as a dense scenario and further evaluate the performance of MISD with different numbers of D2D pairs. Wherein, we set the number of D2D pairs from 4 to 28 by limiting the total number of D2D pairs under the same network topology. Besides, different numbers of RUs (8 and 18) are considered in this scenario.Figure11 plots the system throughput versus the number of D2D pairs when the MISD and InGRA are used, respectively. It is evident that the system throughput results of MISD and InGRA increase as the number of D2D pairs increases. Moreover, both two algorithms have similar system throughput when the number of D2D pairs is less than 8. The result is reasonable because the system throughput gain is limited by the number of D2D pairs while it is less than the available RU. However, as the number of D2D pairs increases, the throughput performance of MISD is better than InGRA. In particular, when the number of D2D pairs is 28, the system throughput of MISD is higher than that of InGRA by about 21% and 11% under 8 and 18 RUs, respectively. The results confirm that the proposed MISD algorithm effectively improves the spectrum reuse efficiency by scheduling more D2D pairs to share the same RU with the higher probability based on the MISs compared to the InGRA especially in the dense network. Moreover, MISD exploits an enhanced back-off mechanism including adaptive CW adjustment strategy, which reduces the control overheads and further improves the MAC access efficiency in uplink random access phase.Figure 11
System throughput vs. different D2D pairs.Figure12 compares the collision rate of the two algorithms as a function of the number of D2D pairs. The collision rate decreases with the increasing number of D2D pairs in both algorithms, where the collision only occurs in uplink random access phase in both algorithms. Reasonably, the number of STAs will decrease with the number of the D2D pairs that increases for the given number of node scenario. Moreover, it is obvious that the collision rate of using the proposed MISD algorithm is lower than that of the InGRA algorithm. More specifically, the collision rate of MISD can be reduced by 64% over InGRA under 28 D2D pairs and 8 RU case. The result is intuitive because that the proposed MISD algorithm exploits an enhanced back-off mechanism, in which each STA employs the optimal CW to choose its back-off value and only contends channel once. Thus, the collision can be effectively relieved by reducing the number of the contention STAs so as to avoid secondary collision in considered random access phase in MISD.Figure 12
Collision rate vs. different D2D pairs.Figure13 illustrates the variation of the average completion time for transmitting 1 Mega bit file, when the MISD and InGRA algorithms are used. The completion time results for the two algorithms decrease with the increasing of D2D pairs. This result is expected because, for the given number of nodes, more nodes adopt the D2D communication mode that is beneficial not only in reducing the time for uplink random access but also in providing more data transmission opportunities for nodes by enabling spectrum reuse technology. Hence, the node can access the specific RU and transmit data quickly even in highly dense D2D pair scenario. Besides, it can be observed that the completion time of the proposed MISD is slightly lower than that of InGRA. Specifically, when the number of D2D pairs is 28, the MISD achieves about 4% and 2% performance improvement over InGRA with 8 and 18 RUs, respectively. The slight improvement in performance can be attributed to the enhanced back-off mechanism in MISD, where AP will not respond to ACK for each BSR which reduces the channel overheads. Moreover, the optimal CW is enabled to enhance the MAC access efficiency. Consequently, AP can schedule nodes (D2D pairs and STAs) to transmit data timely in data transmission period with the proposed MISD algorithm.Figure 13
Completion time vs. different D2D pairs.In this simulation, we further evaluate the impact of the number of D2D pairs on the performance of channel utilization. Referring to Figure14, both InGRA and MISD can achieve high channel utilization especially in highly dense network scenarios by offloading nodes to D2D communication mode. The channel utilization results are near-optimal because the RU resources are fully used by STAs and D2D pairs according to the direct scheduling of AP during the uplink transmission phase. Besides, simulation results of channel utilization also confirm that enabling D2D offloading schemes in 802.11ax is beneficial not only in improving the spectrum efficiency by enabling resource reuse technology in scheduling mode but also in shortening the period of the random-access process by reducing the number of contention nodes. As a result, high channel utilization can be obtained in both uplink random access and data transmission phases.Figure 14
Channel utilization vs. different D2D pairs.


## 5.2.1. Different Number of Nodes

Figure7 illustrates the impact of the different number of nodes on system throughput when the MISD, 802.11ax, G-OFDMA, and InGRA algorithms are used in first considered simulation scenario. Referring to Figure 7, both the proposed MISD and InGRA algorithms have achieved the significant performance improvements in terms of the system throughput, especially in dense scenarios. This result is expected because D2D communication and the channel resource reuse technologies are exploited in both algorithms. Meanwhile, as the increasing of nodes in the network, nodes are offloaded to D2D communication mode with higher probability. Correspondingly, less STAs need to contend channel in uplink random access phase and more D2D pairs can transmit packets in parallel, which improves spectrum access efficiency and further increases spectrum reuse probability. In MISD, AP can schedule more D2D pairs to share the same RU, since it always preferentially allocates RU for the D2D pairs in the largest MIS, which achieves higher resource reuse than InGRA. Particularly, while the number of nodes is less than 30, the G-OFDMA outperforms the MISD in 18 RU scenario. However, the throughput performance of G-OFDMA is almost unchanged as the number of nodes increases. The main reason is that the G-OFDMA adapts the fixed uplink random access stages and the maximum system throughput is limited by the available RUs.Figure 7
System throughput vs. different nodes.Figure8 compares the variation of the average completion time for transmitting 1 Mega bit file when OFDMA-based algorithms and D2D offloading in OFDMA algorithms are used, respectively. Note that more transmission opportunities and higher successful transmission probability can reduce the completion time of transmitting the given data. Irrespective of the number of nodes, both MISD and InGRA algorithms yield the better performance in terms of completion time than that of the legacy 802.11ax and G-OFDMA. This is due to the fact that both MISD and InGRA algorithms offload nodes to D2D communication mode, where D2D pairs can share the spectrum resource with STAs for data transmission, i.e., more nodes can access channel to transmit data, simultaneously, which gives more transmission opportunities for nodes. It also can be observed that the completion time of four algorithms markedly increases with the increases of nodes. Compared with 802.11ax and G-OFDMA, the performance of MISD is significantly improved and outperforms InGRA in most cases. More specifically, the completion time of MISD is 76%, 62%, and 5% less than that of the 802.11ax, G-OFDMA, and InGRA, respectively (8 RUs and 100 nodes). This can be attributed to two factors: (1) the MISD algorithm relieves the data collision in uplink random access by offloading nodes to D2D communication mode and providing higher successful transmission probability for STAs with the enhanced back-off mechanism; (2) in MISD, AP schedules multiple D2D pairs and STA to share the same RU with low time complexity and offers more transmission opportunity for D2D pairs based on the MISs.Figure 8
Completion time vs. different nodes.Figure9 compares the collision rate of the four algorithms, where the number of nodes ranges from 10 to 100, where both 8 and 18 RU cases are considered. Note that the collision rate results are directly related to the uplink random access mechanism and the number of contention nodes. The results depicted in Figure 9 are diverse. The collision rate increases with the increasing number of nodes in both 802.11ax and InGRA. However, the results are almost unchanged for G-OFDMA. More interestingly, the collision rate of MISD decreases as the number of nodes increases. In particular, the collision rate gain of MISD is 64%, 44%, and 64% compared with 802.11ax, G-OFDMA, and InGRA in the case of 8 RUs and 100 nodes, respectively. This can be explained by the fact that the proposed MISD algorithm reduces the number of contention nodes by enabling D2D offloading technique and the proposed enhanced back-off mechanism further relieves data collision by allowing STA access channel only once. Hence, the number of STAs contending for channel has been greatly reduced. Besides, AP derives the optimal CW according to the network condition, which reduces the unnecessary data collisions so as to enhance MAC access efficiency.Figure 9
Collision rate vs. different nodes.Figure10 compares the channel utilization of the four algorithms as a function of the number of nodes. It can be observed that the trends of channel utilization results of all algorithms are almost similar with the number of node changes, since the OFDMA technology has been enabled in all algorithms and each RU will be used for at least one node (STA or D2D pair) to transmit data during uplink transmission phase. As a result, the channel utilization performance is limited by the available RUs and total data transmission time. For both D2D offloading algorithms, i.e., MISD and InGRA can obtain the higher channel utilization compared to the 802.11ax and G-OFDMA under different network densities. This is due to the fact that the MAC access efficiency in uplink random access phase can be improved by reducing the number of contention nodes and hence all nodes have more opportunities to transmit data instead of contending channel resource for the given simulation time.Figure 10
Channel utilization vs. different nodes.


## 5.2.2. Different Number of D2D Link Pairs

In this subsection, we deploy 100 nodes as a dense scenario and further evaluate the performance of MISD with different numbers of D2D pairs. Wherein, we set the number of D2D pairs from 4 to 28 by limiting the total number of D2D pairs under the same network topology. Besides, different numbers of RUs (8 and 18) are considered in this scenario.Figure11 plots the system throughput versus the number of D2D pairs when the MISD and InGRA are used, respectively. It is evident that the system throughput results of MISD and InGRA increase as the number of D2D pairs increases. Moreover, both two algorithms have similar system throughput when the number of D2D pairs is less than 8. The result is reasonable because the system throughput gain is limited by the number of D2D pairs while it is less than the available RU. However, as the number of D2D pairs increases, the throughput performance of MISD is better than InGRA. In particular, when the number of D2D pairs is 28, the system throughput of MISD is higher than that of InGRA by about 21% and 11% under 8 and 18 RUs, respectively. The results confirm that the proposed MISD algorithm effectively improves the spectrum reuse efficiency by scheduling more D2D pairs to share the same RU with the higher probability based on the MISs compared to the InGRA especially in the dense network. Moreover, MISD exploits an enhanced back-off mechanism including adaptive CW adjustment strategy, which reduces the control overheads and further improves the MAC access efficiency in uplink random access phase.Figure 11
System throughput vs. different D2D pairs.Figure12 compares the collision rate of the two algorithms as a function of the number of D2D pairs. The collision rate decreases with the increasing number of D2D pairs in both algorithms, where the collision only occurs in uplink random access phase in both algorithms. Reasonably, the number of STAs will decrease with the number of the D2D pairs that increases for the given number of node scenario. Moreover, it is obvious that the collision rate of using the proposed MISD algorithm is lower than that of the InGRA algorithm. More specifically, the collision rate of MISD can be reduced by 64% over InGRA under 28 D2D pairs and 8 RU case. The result is intuitive because that the proposed MISD algorithm exploits an enhanced back-off mechanism, in which each STA employs the optimal CW to choose its back-off value and only contends channel once. Thus, the collision can be effectively relieved by reducing the number of the contention STAs so as to avoid secondary collision in considered random access phase in MISD.Figure 12
Collision rate vs. different D2D pairs.Figure13 illustrates the variation of the average completion time for transmitting 1 Mega bit file, when the MISD and InGRA algorithms are used. The completion time results for the two algorithms decrease with the increasing of D2D pairs. This result is expected because, for the given number of nodes, more nodes adopt the D2D communication mode that is beneficial not only in reducing the time for uplink random access but also in providing more data transmission opportunities for nodes by enabling spectrum reuse technology. Hence, the node can access the specific RU and transmit data quickly even in highly dense D2D pair scenario. Besides, it can be observed that the completion time of the proposed MISD is slightly lower than that of InGRA. Specifically, when the number of D2D pairs is 28, the MISD achieves about 4% and 2% performance improvement over InGRA with 8 and 18 RUs, respectively. The slight improvement in performance can be attributed to the enhanced back-off mechanism in MISD, where AP will not respond to ACK for each BSR which reduces the channel overheads. Moreover, the optimal CW is enabled to enhance the MAC access efficiency. Consequently, AP can schedule nodes (D2D pairs and STAs) to transmit data timely in data transmission period with the proposed MISD algorithm.Figure 13
Completion time vs. different D2D pairs.In this simulation, we further evaluate the impact of the number of D2D pairs on the performance of channel utilization. Referring to Figure14, both InGRA and MISD can achieve high channel utilization especially in highly dense network scenarios by offloading nodes to D2D communication mode. The channel utilization results are near-optimal because the RU resources are fully used by STAs and D2D pairs according to the direct scheduling of AP during the uplink transmission phase. Besides, simulation results of channel utilization also confirm that enabling D2D offloading schemes in 802.11ax is beneficial not only in improving the spectrum efficiency by enabling resource reuse technology in scheduling mode but also in shortening the period of the random-access process by reducing the number of contention nodes. As a result, high channel utilization can be obtained in both uplink random access and data transmission phases.Figure 14
Channel utilization vs. different D2D pairs.


## 6. Conclusions

In this paper, we have investigated the uplink resource allocation problem for dense WLAN to improve the spectrum efficiency by introducing the D2D offloading into IEEE 802.11ax. We first developed an adaptive CW optimization model for the enhanced back-off mechanism in uplink random phase to optimize the MAC access efficiency. The conception of MIS has been introduced to manage the interference among D2D pairs. Based on this, we proposed an efficient resource allocation algorithm to maximize the spectrum efficiency, i.e., AP effectively schedules multiple D2D pairs and specific STA to share the same RU. The performance analysis results have demonstrated that the proposed algorithm minimizes the completion time and improves system throughput, channel utilization. Besides, it has shown that the use of the enhanced back-off mechanism with optimal CW renders the random-access process more efficient and also reduces the control overhead. The results confirm the feasibility of the proposed algorithm, which can be flexibly integrated into the next generation IEEE 802.11ax without extra hardware modification requirements. However, the proposed MISD algorithm is only a starting point to explore innovation resource allocation protocol by combining D2D offloading and 802.11ax. In future research, it can examine the feasibility of extending the proposed MISD algorithm to the cases of dynamic network scenario and heterogeneous node types. Moreover, the deep reinforcement learning-based approach can be designed and trained to intelligently optimize the resource allocation for D2D pairs and STAs.



---

*Source: 1949352-2021-10-22.xml*