Vertical federated learning (VFL) is a collaborative learning scheme where clients share some overlapping samples but have different feature spaces. Existing VFL schemes are restricted in model performance and deployment feasibility due to the scarcity of overlapping labeled samples and high communication costs. To tackle these issues, we propose a practical VFL scheme Semi-VFL using stacked generalization, which can effectively improve model performance with limited aligned labeled samples and only two communication times. A built-in local semi-supervised learning strategy FewMatch with model-level consistency for few-label VFL setting is designed in our scheme. Extensive experiments indicate the superiority of Semi-VFL in both image and tabular datasets. Specifically, Semi-VFL can achieve accuracy improvement by more than 10.9% and communication cost reduction by more than 380× over the state-of-the-art few-shot VFL scheme on CIFAR-10 with 128 aligned samples.

With the emergence of extremely large-scale antenna arrays (ELAAs), the next generation of wireless communication is likely to occur in the radiating near-field region of base stations (BS). In such regions, beam training needs to search both the angle and distance dimensions, leading to a prolonged training process and coverage hole (dead zone). To cope with those issues, we propose a novel codebook design guideline for the uniform circular array by maximizing the overlapping coverage between the beam coverage (BC) and near-field region, where the energy spread effect in the near-field region is exploited to obtain the optimal focusing point to improve the beam gain inside the dead zone. Based on this guideline, we construct the beam coverage-based codebook structure and two-stage beam training (TSBT) scheme. Numerical simulations show that the TSBT scheme with the proposed codebook can potentially reduce beam training overhead while improving the success rate and patching the dead zone.

Extremely large-scale antenna arrays (ELAAs) introduce a new communication paradigm called near-field communications, where users are likely to operate in the near-field region of the base-stations (BSs). In such a region, beam training needs to search both the angle and distance dimensions, leading to a prolonged training process and a coverage hole (dead zone). To cope with this issue, we developed a beam depth-based codebook and training scheme for near-field ELAA systems. As the performance of codebook design is mainly dictated by the array configurations, we study the codebook design considering uniform linear, circular and planar antenna arrays. Specifically, we first offer an integrated model to characterize the near-field channel for the considered array configurations. Then, we propose a novel codebook design guideline by maximizing the overlap depth between the near-field codeword (beam) coverage and near-field region, where the energy spread effect is exploited to obtain the optimal focusing point to improve the beam gain inside the dead zone. Based on this guideline, we respectively construct the beam depth based on two-stage and hierarchical codebooks as well as the corresponding beam training schemes. Numerical simulations show that the proposed codebook based beam training schemes can potentially reduce beam training overhead while improving the success rate and beam gain inside the dead zone.

Extremely large-scale multiple-input multiple-output (XL-MIMO) wideband systems may exhibit the severe delay spread, due to its spatial- and frequency-wideband (dual-wideband) effects. The typical orthogonal frequency division multiplexing (OFDM) technology have to insert a larger number of cyclic prefix (CP) to overcome the inter-symbol interference (ISI) induced by delay spread. The additional CP overhead will counteract the improvement of spectral efficiency by the large antenna array. To address the issue, this paper proposes a structured OFDM (SOFDM) modulation approach to reduce the CP overhead for wideband XL-MIMO systems with dual-wideband effects. As the ability to perform SOFDM is affected by the antenna architecture, we study the modulation technique considering different antenna structures, including fully-digital, phase shifter-based hybrid array, and dynamic metasurface antenna (DMA) architectures. Specifically, we first provide a mathematical model to represent a near-field channel with dual wideband effects. Based on the channel model, we develop the SOFDM modulation and then propose a joint spatial precoding and frequency domain equalization scheme to maximize the system spectral efficiency, where the solutions of precoding/combining and equalization matrices are derived for the three types of antenna array architectures. Numerical simulations indicate that the proposed scheme can effectively deal with the dual-wideband effects and significantly improve the spectral efficiency with low CP overhead.

This paper investigates physical layer secure communication in a wideband wireless system, where a base station (BS) equipped with an extremely large scale antenna array (ELAA) transmits confidential information to a legitimate receiver under the threat of a potential eavesdropper. Due to the high carrier frequency and large antenna aperture, both the receiver and eavesdropper lie in the near-field region of the BS. In order to mitigate the beam split effect and reduce the hardware cost, a true-time delayer-based hybrid beamfocusing architecture is designed. Then, a nonconvex sum secrecy capacity maximization problem (SSCM) is formulated for securing wideband communications. Based on alternating optimization, the SSCM is decomposed into three subproblems solved iteratively for designing the digital beamfocusing vectors, time delay matrices, and phase shift matrices on each subcarrier, respectively. Simulation results show that the proposed scheme yields significantly high secrecy capacity compared to benchmarks, which validates the effectiveness of our scheme in enhancing secure wideband communications and mitigating the beam split effects.

Extremely large-scale multiple-input multiple-output (XL-MIMO) communication system with extremely large-scale antenna arrays can achieve ultra-high spectral efficiency. However, the conventional far-field beam codebooks may be mismatched with the near-field spherical-wavefront channel caused by large array aperture, which results in severe performance loss. To address this problem, we develop a criterion of code book design to maximize the worst-case beam gain within the beam coverage. Then, a closed-form expression of the near-field full dimensional (FD) codebook with non-orthogonal structure is derived, which can realize the spatial oversampling regardless of the number of antennas at the transceiver. Simulation results show that our proposed non-orthogonal codebook can potentially improve the accuracy of near-field beam training, compared with existing codebooks.

Massive multiple-input multiple-output (mMIMO) channels in wideband systems may exhibit the severe delay spread, due to its spatial- and frequency-wideband (dual-wideband) effects. The typical orthogonal frequency division multiplexing (OFDM) technology have to insert a larger number of cyclic prefix (CP) to overcome the inter-symbol interference (ISI) induced by delay spread. The additional CP overhead will counteract the improvement of spectral efficiency by the large antenna array. To address the issue, this paper proposes a structure OFDM modulation approach to reduce the CP overhead for wideband mMIMO systems with dual-wideband effects. Specifically, we propose a joint spatial precoding and frequency domain equalization scheme to maximize the system spectrum efficiency, where the closed-form solutions of precoding vectors and equalization matrices are derived by exploiting the unique characteristic of composite channel matrix. Numerical simulations indicate that the proposed scheme can effectively deal with the dual-wideband effects and significantly improve the spectral efficiency with low CP overhead.

Finite blocklength (FBL) transmission is a promising technique to meet the stringent delay and reliability requirements. In this paper, based on the FBL transmission mode, we formulate a joint user scheduling and beamforming (USBF) optimization problem with maximizing the system utility related to the long-term average rate, which considers variable user numbers and statistical wireless channels. To address the long-term optimization problem, by utilizing the Lyapunov optimization method, it can be transformed into the admission control subproblem and the joint USBF subproblem with the instantaneous channel state information (CSI) of each user. Then, an iteration method with successive convex approximation (SCA) is presented to solve the transformed instantaneous optimization problem. The simulation results confirm that the proposed scheme can achieve a significant performance gain on the premise of meeting the requirements of uRLLC.

This paper investigates the physical-layer security in a Virtual Antenna Array (VAA)-aided Device-to-Device Multicast (D2DM) communication system, where the User Equipments (UEs) who cache the common content will form a VAA system and cooperatively multicast the content to UEs who desire it. Specifically, with the target of securing the VAA-aided D2DM communication under the threat of multiple eavesdroppers, we propose a secure beamforming scheme by jointly considering the formed VAA and the Base Station (BS). For obtaining the optimal beamforing vectors, a nonsmooth and nonconvex Weight Sum Rate Maximization Problem (WRMP) is formulated and solved using Successive Convex Approximation (SCA) approach. Furthermore, we consider the worst case that eavesdroppers cooperatively form a eavesdrop VAA to enhance the overhearing capacity. In the worst case, we modify the securing beamforming scheme, formulate the corresponding WRMP and solve it using a two-level optimization. Simulation results validate the improvements of the VAA-aided D2DM scheme in terms of communication security compared with conventional D2DM schemes.

With the development of autonomous driving, task offloading of Internet of vehicles has become a hot research issue. In pedestrian-vehicle interaction scenarios, characteristics of tasks are constantly changing due to the influence of pedestrians and road conditions. Real-time offloading optimization and signaling are time-consuming, which may not meet the low delay requirement of task offloading. Therefore, this paper proposes a location prediction-based resource optimization scheme for task offloading in these scenarios. Firstly, the locations of pedestrians are predicted by the social force model based on their movement rules, and the locations of vehicles are predicted by the car-following model on the basis of ensuring pedestrian safety. The characteristics of tasks are obtained based on the predicted locations of vehicles. Then a neural network trained beforehand based on deep Q-learning is used to obtain a task offloading strategy. Since the tasks are obtained by prediction in advance, this strategy decision can be processed before vehicles arriving the predicted locations, which saves the time consumption of optimization and signaling. Besides, simulation results show that the proposed scheme still guarantees an acceptably low task offloading delay compared with the other methods, especially in congested areas.

The fundamental intelligent reflecting surface (IRS) deployment problem is studied for IRS-aided downlink multi-user communication system, where IRSs are arranged to be deployed in a specific area for enhancing the desired signal and suppressing interference. Specifically, we aim to maximize the minimum achievable rate over all locations in a specific area by jointly optimizing the transmit beamforming at the access point (AP) as well as the placement and reflective beamforming at the IRS. The formulated problem is non-convex and thus difficult to be solved directly. To draw essential insights, we first consider the single-user case and the optimal solution is derived in closed-form. The result shows that the optimal locations are in the connecting line between the AP and user, and the IRSs can be optimally deployed along the connecting line. Besides, a hybrid offline and online design scheme is developed for the multi-user case, where an area discretization strategy and deep neural network (DNN)-based curve fitting technique are proposed for optimizing the IRS locations in the offline manner. Then, an online iterative algorithm is presented to solve the transmit and received beamformig vectors, respectively. Numerical results show that the performance gain is increased by optimizing the IRS locations.

The potential application of intelligent reflecting surfaces (IRSs) for future wireless cellular communication systems has motivated the study of metasurface for achieving additional space degree of freedom, where IRS is used to enhance the desired signal strength and suppress the interference. In this paper, by using the additional design degree of freedom provided by the IRS, we jointly optimize the transmit beamforming vector at the BS and the reflective beamforming vector at the IRS to maximize the minimum rate in the IRS-aided multi-user multiple-input-single-output broadcast channel (MISO-BC), subject to the unit modulus constraints of the reflective beamforming vector. In order to solve the non-convex optimization problem, we propose an efficient algorithm based on alternating optimization. In particular, we optimize the transmit beamforming vectors via the second-order cone problem (SOCP) and reflective beamforming vector by using the semi-definite relaxation (SDR). Numerical results show that the use of IRS leads to significant higher SINR values than benchmark schemes without IRS.

The in-band full-duplex (IBFD) wireless communication has been spotlighted as one of the promising technologies to enhance throughput performance in the future WLANs. One way to leverage full-duplex capability in practical scenario is to enable three-node transmission, where a full-duplex access point (AP) transmits date to one half-duplex user while receives date from another half-duplex user. Such full-duplex communication mode, however, introduces extra uplink-downlink interference, which may degrade the full-duplex gain. In this paper, with the target of fully achieving the performance improvement brought by the full-duplex transmission, we investigate the joint optimization of scheduling and power control in three-node full-duplex WLANs. Specifically, the problem formulation is to maximize the aggregate utility of downlink users under specific date rate constraints of uplink users. In particular, the optimization is conducted by jointly considering the transmit powers of the AP and uplink users, the access-intensity of uplink users, and the uplink-downlink user paring. Such an optimization problem is a classical mixed integer nonlinear programming problem (MINLP) and generally NP-hard. To solve it, we develop an efficient iterative algorithm based on alternating optimization and successive convex approximation (SCA). Numerical results verify that the proposed scheme achieves higher utility compared to other existing schemes.

For the high density of users and accompanying network service requirements in the cellular system, Device-to-Device (D2D) communication is a promising technology to cope with the increasing wireless traffic demands by reusing spectrum resources. In practice, the wireless signal is easy to be eavesdropped in D2D communications underlaying cellular networks, hence, ensuring a secure communication for cellular user equipments (CUEs) is an urgent and meaningful problem. In this paper, we propose a joint subcarrier and power allocation scheme for maximizing the sum data rate of D2D pairs, meanwhile protecting the CUEs against eavesdropping. Specifically, in the proposed scheme, we first quantify the security performance with the secrecy data rate, and obtain the closed-form expression for the optimal power allocation of CUEs and D2D pairs by tightening the quality of service (QoS) and secrecy rate requirement constraints of CUEs. Based on the obtained power allocation solution, by searching the optimal mapping relationship between CUEs and D2D pairs, we develop a subcarrier assignment strategy with the Hungarian algorithm to solve it, which can further enhance the sum data rate of D2D pairs. Simulation results demonstrate that the proposed scheme can significantly yield better performance than other schemes.

This paper investigates the problem of minimizing power consumption under the situation of eliminating the uplink-downlink interference (UDI) through the IC2 technique for a full-duplex WLAN where half-duplex users communicate with the full-duplex AP. In particular, the problem formulation is to minimize the power consumption of half-duplex users and the full-duplex AP in the system while guaranteeing the required data rate of both the uplink and downlink users. The formulated problem falls into a mixed integer nonlinear programming (MINLP) form, which is generally NP-hard to solve. To make the problem tractable, we divide it into user pairing and power allocation sub-problems. Specifically, we devise a user pairing criterion based on the signal-to-interference-plus-noise ratio (SINR) to reduce the interference at downlink users incurred by the uplink transmission, thus decreasing the power that used to eliminate the interference. After that, we adjust the transmit power of both users and the AP to minimize the total power consumption under the constraint of users' minimum data rate requirements. Simulation results are presented to evaluate the performance of our scheme and demonstrate the power consumption reduction compared to other schemes in full-duplex WLANs.

This letter makes a first attempt to design a cooperative relay scheme to secure wireless communications by adopting a fast-forward full-duplex (F3D) node. Different from the conventional full-duplex relay, the F3D node could process and forward the received signal immediately. With such forwarding, the forwarded signal of F3D could enhance the signal to interference plus noise ratio of the receiver, whereas weaken that of the eavesdropper and thus build up a secure channel. Beyond the proposed scheme, we move forward to optimize the signal processing design of the F3D node with the target of maximizing the secrecy capacity. The formulated optimization problem is nonconvex and challenging to deal with. We then design an iterative algorithm based on generalized fractional programming to solve it. One key step in the iterative algorithm involves another nonconvex optimization and we decompose it into a two-level optimization. Simulation results validate the effectiveness of our designed secure cooperative relay scheme and show that adopting F3D node for physical-layer security has good performance in terms of achievable secrecy capacity compared with the scheme without F3D node.

The radio resource management for relay‐assisted access where every terminal user communicates with the base station through relay users is studied. In particular, the problem formulation is to maximise the total utility across relay users and terminal users under the bandwidth constraint of device‐to‐device (D2D) links. To solve such an optimisation problem, the authors first explore the diversity of channels between the relay users and the terminal users based on the maximum weighted bipartite matching theory, and adopt Hungarian algorithm to select the best relay user for each terminal user. Then, to stimulate relay users to participate in the cooperation, they design a two‐stage Stackelberg game to jointly maximise the utilities of the selected relay user and the terminal user. In this doing, every terminal user can obtain the optimal data rate with the aid of relay. Finally, the authors' simulations show that the proposed relay user selection and game‐theoretic resource allocation scheme can effectively improve the downloading rates of terminal users and achieve a ‘win‐win’ strategy between the terminal users and relay users for relay‐assisted access using D2D communications.

To afford effective service of real-time monitoring and responses for smart cities, it is desired to provide ubiquitous network connections and high data rate services. However, the huge demands for ubiquitous high data rate wireless communications have caused a sharp increase in energy consumption and green house gas emission. In order to realize a sustainable smart city, it is critical to incorporate green communication technique into smart city developments. Device-to-device (D2D) communication has been recognized as one of the key technologies to improve data rate and reduce power consumption, which allows two physically nearby located user equipments to communicate directly with each other. In this paper, with the target of achieving green communications through D2D, we investigate the joint optimization of uplink subcarrier assignment (SA) and power allocation (PA) in D2D underlying cellular networks. Specifically, the problem formulation is to minimize the energy cost of all users in the system while guaranteeing the required data rate of both the D2D user equipments (DUEs) and cellular user equipments. Such an optimization problem is in general a mixed-integer nonlinear programming problem that is NP-hard. To make this problem tractable, we decompose it into the SA and PA subproblems. In particular, we design a heuristic algorithm to assign subcarrier by assuming that the transmit power is evenly allocated over all subcarriers. After that, we solve the PA subproblem by exploiting the difference between the concave function (D.C.) structure of the constraints and transform it into a convex optimization problem. Simulation results demonstrate the remarkable improvement in terms of power consumption by using our algorithms.

This paper proposes a device-to-device (D2D) communications based scarcity-aware two-stage multicast mechanism for delivering video streaming, in which the Base Station (BS) and D2D perform cooperative retransmissions to improve the mobile video quality and relieve the load of BS as well. In prior works, after BS's one-round multicast, the clients directly resort to D2D communications to obtain the missing frames by forming social groups. However, after the first-round multicast of BS, it is possible that some frames have not been correctly received by most of the clients, especially when the channel conditions are not good. That is, there are scarce frames in the network and the clients have very limited copies of them. In this case, it is inefficient for the clients to form social groups and directly exchange frames through D2D communications. Instead, this paper proposes an adaptive two-stage multicast mechanism: the BS first multicast video packets to the clients who request the same video services, after which the clients collect the information of missing frames and send it to the BS. Then the BS evaluates the scarcity of frames and re-multicast the scarce frames, if any, to the clients. After the BS's second-round multicast, the clients can then form groups to perform D2D communications so as to obtain the remaining missing packets from each other. Numerical studies show that the proposed simple scarcity-aware two-stage multicast mechanism can achieve about 5% video quality improvement than the existing one-stage multicast mechanism and have the potential to enhance the downlink capacity of the future 5G wireless network.

To meet rapidly increasing data rate requirements in WLANs, one important technique adopted in 802.11ac is the channel bonding (CB) scheme that combines multiple 20MHz channels for a single transmission in 5GHz band. In order to effectively access channel after a series of contention operations, 802.11ac specifies two different CB operations: Dynamic Channel Bonding (DCB) and Static Channel Bonding (SCB). This paper proposes an optimal channel allocation algorithm to achieve maximal throughputs in DCB WLANs. Specifically, we first adopt a continuous-time Markov Chain (CTMC) model to analyze the equilibrium throughputs. Based on the throughput analysis, we then construct an integer nonlinear programming (INLP) model with the target of maximizing system throughputs. By solving the INLP model, we then propose an optimal channel allocation algorithm based on the Branch-and-Bound Method (BBM). Simulations show the proposed algorithm can achieve the maximal system throughput under various network settings. Importantly, it turns out that the maximal throughput performance can be achieved under the channel allocation scheme with the least overlapped channels among WLANs, which brings new insights into the design and optimization of future WLANs, especially for those adopting CB technique.

It is well known that links in CSMA wireless networks are prone to starvation. Prior works focused almost exclusively on equilibrium starvation. Links in CSMA wireless networks are also susceptible to temporal starvation. Specifically, although some links have good equilibrium throughputs and do not suffer from equilibrium starvation, they can still have zero or little throughputs for extended periods from time to time. For real-time applications such as VoIP and video streaming, it is desirable to understand and characterize temporal starvation in CSMA wireless networks. To this end, we develop a “trap theory” to analyze temporal throughput fluctuations. The trap theory serves two functions. First, it allows us to derive new mathematical results that shed light on the transient behavior of CSMA networks. For example, we show that the duration of a trap, during which some links receive zero or little throughputs, is insensitive to the distributions of the transmission time (packet duration) and the backoff countdown time in the CSMA protocol given their respective means. This implies that the phenomenon of temporal starvation is fundamental and cannot be solved by simply manipulating the probability distributions of the backoff countdown time and transmission time alone. Second, with the trap theory, we can develop analytical tools for computing the “degrees of starvation” for CSMA networks to aid network design. For example, given a CSMA network, we can determine whether it suffers from starvation, and if so, which links will starve. Furthermore, the likelihood and durations of temporal starvation, if any, can also be computed. To further motivate the study of temporal starvation, we show that the existing remedies designed to solve equilibrium starvation may not work well as far as temporal starvation is considered. We believe that the ability to identify and characterize temporal starvation as established in this paper will serve as an important first step toward the design of effective remedies for it.

This paper studies a two-way relay channel where two single-antenna users exchange messages via a relay with$K$antennas. A new physical-layer network coding (PNC) method is proposed, referred to as channel-quantized PNC (CQ-PNC), that can achieve full diversity gain of$K$. The proposed method converts$K$received signals at the relay into two signals by a QR decomposition. The first one is a weighted summation of the two users' messages and the second one is a scaled version of one user's message. Then, the first signal is quantized at the relay by using the channel coefficient and the quantization error is cancelled by using the side information of the second signal. Finally, a Gaussian-integer weighted summation of the two users' messages is obtained, mapped to network codeword, and then broadcast to the two users. It is proved that the proposed CQ-PNC can achieve the full diversity gain of$K$with receiver side channel information, low computational complexity and symbol level synchronization. Simulation results demonstrate that the proposed method obtains optimum performance results with negligible gap.

This paper proposes an approximate method, equivalent access intensity (EAI), for the throughput analysis of CSMA wireless networks in which links have finite offered-load and their MAC-layer transmit buffers may be empty from time to time. Different from prior works that mainly considered the saturated network, we take into account in our analysis the impacts of empty transmit buffers on the interactions and dependencies among links in the network that is more common in practice. It is known that the empty transmit buffer incurs extra waiting time for a link to compete for the channel airtime usage, since when it has no packet waiting for transmission, the link will not perform channel competition. The basic idea behind EAI is that this extra waiting time can be mapped to an equivalent “longer” backoff countdown time for the unsaturated link, yielding a lower link access intensity that is defined as the mean packet transmission time divided by the mean backoff countdown time. That is, we can compute the “equivalent access intensity” of an unsaturated link to incorporate the effects of the empty transmit buffer on its behavior of channel competition. Then, prior saturated ideal CSMA network (ICN) model can be adopted for link throughput computation. Specifically, we propose an iterative algorithm, “Compute-and-Compare”, to identify which links are unsaturated under current offered-load and protocol settings, compute their “equivalent access intensities” and calculate link throughputs. Simulation shows that our algorithm has high accuracy under various offered-load and protocol settings. We believe the ability to identify unsaturated links and compute links throughputs as established in this paper will serve an important first step toward the design and optimization of general CSMA wireless networks with offered-load control.

This paper studies a MIMO Two-Way Relay Channel (TWRC) where two single-antenna nodes communicate with each other through a K-antenna relay. In the uplink phase, the two end nodes send their respective information simultaneously to the relay, and it is usually regarded as a virtual MIMO system. With traditional VBLAST MIMO detection, the maximum achievable diversity is K - 1. By noting that only the network coded packet, rather than the two individual packets, is needed at the relay node in TWRC, we propose a channel quantized physical-layer network coding (CQ-PNC) scheme based on VBLAST to achieve the full diversity K. Specifically, relay first uses QR decomposition to convert the K received signals into two valid signals, the first signal is a weighted summation of the two end nodes' symbols and the second signal is a scaled version of one end node's symbol. The relay first quantizes the first signal with the channel coefficient of one node and estimate the Gaussian integer summation of the two end nodes' information. At the same time, the quantization error is further canceled with the help of the second signal. After that, we adaptively map the Gaussian integer weighted summation to the network coding form. Moreover, we theoretically prove that our CQ-PNC can achieve the maximum diversity K. Finally, the numerical simulation shows that CQ-PNC performs within 2dB gap from the theoretical bound.

Many important network design problems are fundamentally combinatorial optimization problems. A large number of such problems, however, cannot readily be tackled by distributed algorithms. The Markov approximation framework studied in this paper is a general technique for synthesizing distributed algorithms. We show that when using the log-sum-exp function to approximate the optimal value of any combinatorial problem, we end up with a solution that can be interpreted as the stationary probability distribution of a class of time-reversible Markov chains. Selected Markov chains among this class yield distributed algorithms that solve the log-sum-exp approximated combinatorial network optimization problem. By examining three applications, we illustrate that the Markov approximation technique not only provides fresh perspectives to existing distributed solutions, but also provides clues leading to the construction of new distributed algorithms in various domains with provable performance. We believe the Markov approximation techniques will find applications in many other network optimization problems.

“Belief propagation” (BP) is an efficient way to solve “inference” problems in graphical models, such as Bayesian networks and Markov random fields. It has found great success in many application areas due to its simplicity, high accuracy, and distributed nature. This paper is a first attempt to apply BP algorithms in CSMA wireless networks. Compared to prior CSMA optimization algorithms such as ACSMA, which are measurement-based, BP-based algorithms are proactive and computational, without the need for network probing and traffic measurement. Consequently, BP-based algorithms are not affected by the temporal throughput fluctuations and can converge faster. Specifically, this paper explores three applications of BP. 1) We show how BP can be used to compute the throughputs of different links in the network given their access intensities, defined as the mean packet transmission time divided by the mean backoff countdown time. 2) We propose an inverse-BP algorithm to solve the reverse problem of how to set the access intensities of different links to meet their target throughputs. 3) We introduce a BP-adaptive CSMA algorithm to find the link access intensities that can achieve optimal system utility. The first two applications are NP-hard problems, and BP provides good approximations to them. The advantage of BP is that it can converge faster compared to prior algorithms like ACSMA, especially in CSMA networks with temporal throughput fluctuations. Furthermore, this paper goes beyond BP and considers a generalized version of it, GBP, to improve accuracy in networks with a loopy contention graph. The distributed implementation of GBP is nontrivial to construct. A contribution of this paper is to show that a “maximal clique” method of forming regions in GBP: 1) yields accurate results; and 2) is amenable to distributed implementation in CSMA networks, with messages passed between one-hop neighbors only. We show that both BP and GBP algorithms for all three applications can yield solutions within seconds in real operation.

It is well known that links in CSMA wireless networks are prone to starvation. Prior works focused almost exclusively on equilibrium starvation. In this paper, we show that links in CSMA wireless networks are also susceptible to temporal starvation. Specifically, although some links have good equilibrium throughputs and do not suffer from equilibrium starvation, they can still have no throughput for extended periods from time to time. For real-time applications such as VoIP and video streaming, it is desirable to understand and characterize temporal starvation in CSMA wireless networks. To this end, we develop a "trap theory" to analyze the temporal throughput fluctuations. Based on the trap theory, we can develop analytical tools for computing the "degrees of starvation" for CSMA networks to aid network design. For example, given a CSMA wireless network, we can determine whether it suffers from starvation, and if so, which links will starve. Furthermore, the likelihood and durations of temporal starvation can also be computed. We believe that the ability to identify and characterize temporal starvation as established in this paper will serve as an important first step toward the design of effective remedies for it.

In the majority of studies on CSMA wireless networks, a contention graph is used to model the carrier sensing relationships among links. This is a 0-1 model in which two links can either sense each other completely or not. In real experiments, we observed that this is generally not the case: the carrier sensing relationship between the links are often probabilistic and can vary dynamically over time. This is the case even if the distance between the links is fixed and there is no drastic change in the environment. Furthermore, this ``partial carrier sensing'' relationship is prevalent and occurs over a wide range of distances between the links. This observation is not consistent with the 0-1 contention graph and implies that many results and conclusions drawn from previous theoretical studies need to be re-examined. This paper establishes a more accurate carrier sensing model with the objective of laying down a foundation for future theoretical studies that reflect reality. Towards that end, we set up detailed experiments to investigate the partial carrier sensing phenomenon. We discuss the implications and the use of our partial carrier sensing model in network analysis.

Many important network design problems can be formulated as a combinatorial optimization problem. A large number of such problems, however, cannot readily be tackled by distributed algorithms. The Markov approximation framework studied in this paper is a general technique for synthesizing distributed algorithms. We show that when using the log-sum-exp function to approximate the optimal value of any combinatorial problem, we end up with a solution that can be interpreted as the stationary probability distribution of a class of time- reversible Markov chains. Certain carefully designed Markov chains among this class yield distributed algorithms that solve the log-sum-exp approximated combinatorial network optimization problem. By three case studies, we illustrate that Markov approximation technique not only can provide fresh perspective to existing distributed solutions, but also can help us generate new distributed algorithms in various domains with provable performance. We believe the Markov approximation framework will find applications in many network optimization problems, and this paper serves as a call for participation.

This work started out with our discovery of a pattern of throughput distributions among links in IEEE 802.11 networks from experimental results. This pattern gives rise to an easy computation method, which we term back-of-the-envelop (BoE) computation. For many network configurations, very accurate results can be obtained by BoE within minutes, if not seconds, by simple hand computation. This allows us to make shortcuts in performance evaluation, bypassing complicated stochastic analysis. To explain BoE, we construct a theory based on the model of an “ideal CSMA network” (ICN). The BoE computation method emerges from ICN when we take the limit c \to 0, where c is the ratio of the mean backoff countdown time to the mean transmission time in the CSMA protocol. Importantly, we derive a new mathematical result: the link throughputs of ICN are insensitive to the distributions of the backoff countdown time and transmission time (packet duration) given the ratio of their means c. This insensitivity result explains why BoE works so well for practical 802.11 networks, in which the backoff countdown process is one that has memory, and in which the packet size can be arbitrarily distributed. Our results indicate that BoE is a good approximation technique for modest-size networks such as those typically seen in 802.11 deployments. Beyond explaining BoE, the theoretical framework of ICN is also a foundation for fundamental understanding of very-large-scale CSMA networks. In particular, ICN is similar to the Ising model in statistical physics used to explain phenomena arising out of the interactions of a large number of entities. Many new research directions arise out of the ICN model.

This paper presents a simple method for computing throughputs of links in a CSMA network. We call our method back-of-the-envelop (BoE) computation, because for many network configurations, very accurate results can be obtained by simple hand computation. BoE beats prior methods in terms of both speed and accuracy. To explain BoE, we construct a theory based on the model of an "ideal CSMA network" (ICN). We find that link throughputs are insensitive to the distributions of the backoff countdown time and transmission time in ICN given the ratio of their mean c. The BoE computation method emerges from ICN in the limit c rarr 0 . The insensitivity result explains why BoE works so well for IEEE 802.11 networks, in which the backoff countdown process is one that has memory and the transmission time can be arbitrarily distributed. Furthermore, c does not have to be very small for BoE to be highly accurate. BoE allows us to make shortcuts in performance evaluation, bypassing complicated stochastic analysis. An immediate application of BoE is for quick identification of starved links in the network so that remedies can be devised to solve the problem.