The restless multi-armed bandit (RMAB) framework is a popular model with applications across a wide variety of fields. However, its solution is hindered by the exponentially growing state space (with respect to the number of arms) and the combinatorial action space, making traditional reinforcement learning methods infeasible for large-scale instances. In this paper, we propose GINO-Q, a three-timescale stochastic approximation algorithm designed to learn an asymptotically optimal index policy for RMABs. GINO-Q mitigates the curse of dimensionality by decomposing the RMAB into a series of subproblems, each with the same dimension as a single arm, ensuring that complexity increases linearly with the number of arms. Unlike recently developed Whittle-index-based algorithms, GINO-Q does not require RMABs to be indexable, enhancing its flexibility and applicability. Our experimental results demonstrate that GINO-Q consistently learns near-optimal policies, even for non-indexable RMABs where Whittle-index-based algorithms perform poorly, and it converges significantly faster than existing baselines.

Recent advances in LLM-based multi-agent systems have demonstrated remarkable capabilities in complex decision-making scenarios such as financial trading and software engineering. However, evaluating each individual agent’s effectiveness and online optimization of underperforming agents remain open challenges. To address these issues, we present HiveMind, a self-adaptive framework designed to optimize LLM multi-agent collaboration through contribution analysis. At its core, HiveMind introduces Contribution-Guided Online Prompt Optimization (CG-OPO), which autonomously refines agent prompts based on their quantified contributions. We first propose the Shapley value as a grounded metric to quantify each agent's contribution, thereby identifying underperforming agents in a principled manner for automated prompt refinement. To overcome the computational complexity of the classical Shapley value, we present DAG-Shapley, a novel and efficient attribution algorithm for Directed Acyclic Graph (DAG)-structured multi-agent workflows that leverages the inherent DAG structure of the agent workflow to axiomatically prune non-viable coalitions. By hierarchically reusing intermediate outputs of agents in the DAG, our method further reduces redundant computations, and achieving substantial cost savings without compromising the theoretical guarantees of Shapley values. Evaluated in a multi-agent stock-trading scenario, HiveMind achieves superior performance compared to static baselines. Notably, DAG-Shapley reduces LLM calls by over 80 percent while maintaining attribution accuracy comparable to full Shapley values, establishing a new standard for efficient credit assignment and enabling scalable, real-world optimization of multi-agent collaboration.

Optical wireless communication (OWC) leverages the terahertz-scale optical spectrum to enable ultra-fast data transfer, offering a compelling alternative to often-congested radio frequency systems. However, the highly directional nature of optical signals and their susceptibility to obstruction inherently limit coverage and reliability, particularly in dynamic indoor environments. To overcome these limitations, we propose apervasive optical wireless medium (POWM)framework that transforms indoor spaces into a dynamically controllable optical propagation medium. POWM deploys a distributed network ofprogrammable optical amplifiers (POAs)– devices with tunable gains to extend coverage through diffuse reflections while compensating for signal attenuation. A key challenge in POWM is preventing amplifier saturation from feedback loops. We rigorously derive stability constraints to guarantee system robustness. Beyond coverage extension, POWM dynamically adjusts POA gains in response to user locations and channel conditions, enhancing signal-to-noise ratio, balancing resource allocation, and suppressing interference. As the first framework to harness diffuse reflection for controllable optical propagation, we validate POWM’s effectiveness through analytical modeling, simulations, and prototyping. Proof-of-concept experiments using an infrared-only prototype in a controlled, small-scale setup (1.8 × 1.8m2area) show that the POWM framework can deliver up to a 7 dB improvement in SNR and a tenfold reduction in packet loss. This work lays a foundational framework for future robust, high-speed indoor OWC networks.

Cooperative broadcast is an efficient approach to improve Wi-Fi broadcast performance in crowded scenarios with densely deployed access points (APs). However, existing concurrent transmission MAC protocols cannot perfectly synchronize APs for the receiving user, and the superimposed channels at users vary over time due to multi-path effects with different carrier frequency offsets (CFOs) from the APs. Traditional channel estimation methods, which treat the superimposed channels as a whole and use a portion of the superimposed channels to derive the rest, are unsuitable. To solve the problem, we propose a fine-grained channel estimation approach that first estimates channel taps and CFOs of each AP, and then reconstructs the superimposed channels. We first study a benchmark channel estimation algorithm that utilizes a widely adopted compressed sensing (CS) technique. However, through analysis and simulations, we show that the CS-based algorithm suffers from high correlation problems in the constructed sensing matrix and the non-sparse channel problem in practice, leading to an estimation error floor at high SNRs. To solve these problems, we present a two-stage channel estimation algorithm. It first estimates the CFOs by identifying the most likely CFO combination matching the received signals, and then estimates the time-domain channel taps. Simulation and experimental results show that the two-stage channel estimation algorithm achieves much lower bit error rate (BER) and packet error rate (PER) than the traditional IEEE 802.11 approach, and the two-stage algorithm outperforms the CS-based algorithm, especially at high SNRs. The network-layer simulation results further demonstrate that, empowered by the proposed two-stage channel estimation algorithm, the cooperative broadcast scheme improves throughput by at least 1.4× (up to 46.8×) compared with the unicast-based broadcast schemes, and by approximately 0.6× to 0.8× compared with the simple uncooperative broadcast scheme.

This paper introduces Cellular-X, an LLM-powered agent designed to automate cellular base station (BS) maintenance. Leveraging multimodal LLM and retrieval-augmented generation (RAG) techniques, Cellular-X significantly enhances field engineer efficiency by quickly interpreting user intents, retrieving relevant technical information, and configuring a BS through iterative self-correction. Key features of the demo include automatic customized BS setup, document-based query answering, and voice-controlled configuration reporting and revision. We implemented Cellular-X on a USRP X310 testbed for demonstration. Demo videos and implementation details are available at https://github.com/SeaBreezing/Cellular-X.

This work investigates the design of an omnidirectional optical transceiver, to enable reliable inter-robot communication in mobile settings. The design addresses challenges stemming from the intrinsic directional nature of light, which can restrict signal coverage area and destabilize connections during robot movement. Our experiments demonstrate the system's capability to establish reliable high-speed optical communication links within a circular coverage zone of over 3 meters in radius. Our work advances the state-of-the-art in two significant ways: First, to our knowledge, this is the first demonstration of an omnidirectional optical communication system aligned with the IEEE 802.11bb standard. Second, the system leverages channel diversity to enhance signal quality by incorporating hardware-based omnidirectional signal combinations at the receiver, an analog signal-format agnostic method compatible with Wi-Fi and other wireless signals without modifying the underlying wireless system's digital signal processing chain.

Cooperative broadcast is an efficient approach to improve Wi-Fi broadcast performance in a crowded scenario with densely deployed access points (APs). However, the current concurrent transmission MAC protocols cannot synchronize multi-APs’ signals perfectly for all users. As a result, the superimposed signal from APs is time-varying at the users due to the multiple time-domain channels and carrier frequency offsets (CFOs) from multiple APs. The traditional channel estimation approach that estimates the superimposed channel as a whole is ill-suited for the superimposed signal. In this paper, we propose a fine-grained channel estimation approach to first estimate these channel parameters for each AP, and then reconstruct the superimposed channel. Specifically, we present a two-stage channel estimation algorithm that first estimates the CFOs by discretizing the CFO range and matching the most possible CFOs, and then computes the time-domain channels. Experiment and simulation results show the new channel estimation approach achieves much lower bit error rate (BER) and packet error rate (PER) than the traditional IEEE 802.11 approach. In addition, we propose a distributed mechanism to choose the master AP that initializes multi-APs’ simultaneous transmission, which the current concurrent transmission MAC protocols lack. Network-layer simulation results show that the proposed cooperative broadcast scheme improves the throughput by 64% to 82% compared with the traditional uncooperative broadcast scheme.

This paper investigates the potential of large language models (LLMs) in accelerating the development of complex signal-processing algorithms on field-programmable gate arrays (FPGAs) for software-defined radio (SDR) systems. Using the Fast Fourier Transform (FFT) algorithm as a case study, we identify two common challenges in applying LLMs to realize intricate wireless communication algorithms on FPGA: 1) handling convoluted mathematical problems and 2) scheduling the execution of sub-modules within the hardware structure. To overcome the first problem, we adapt the chain-of-thought (CoT) prompting technique with a length-limit strategy to enhance the LLM’s Verilog writing performance. To handle the second problem, we develop a novel iterative in-context learning (IICL) prompting scheme that utilizes the iterative structure within the FFT module to perform in-context learning (ICL). These efforts significantly reduce the LLM’s error rate in completing the FFT implementation task and make possible the successful generation of a 64-point FFT module in Verilog, marking a significant milestone as the first LLM-written complex signal-processing algorithm for wireless communication on FPGA.

This paper focuses on the information freshness of finite-state Markov sources, using the uncertainty of information (UoI) as the performance metric. Measured by Shannon’s entropy, UoI can capture not only the transition dynamics of the Markov source but also the different evolutions of information quality caused by the different values of the last observation. We consider an information update system with$M$finite-state Markov sources transmitting information to a remote monitor via$m$communication channels ($1\le m < M$). At each time, only$m$Markov sources can be selected to transmit their latest information to the remote monitor. Our goal is to explore the optimal scheduling policy to minimize the sum-UoI of the Markov sources. The problem is formulated as a restless multi-armed bandit (RMAB). We relax the RMAB and then decouple the relaxed problem into$M$single bandit problems. Importantly, analyzing the single bandit problem provides useful properties with which the relaxed problem reduces to maximizing a concave and piecewise linear function, allowing us to develop a gradient method to solve the relaxed problem and obtain its optimal policy. By rounding up the optimal policy for the relaxed problem, we obtain an index policy for the original RMAB problem. Notably, the proposed index policy is universal in the sense that it applies to general RMABs with bounded cost functions. Moreover, we show that our policy is asymptotically optimal as$m$and$M$tend to$\infty $with$m/M$fixed. In non-asymptotic cases, numerical results demonstrate that our index policy is near-optimal and performs as well as the celebrated Whittle index policy in the problems that are Whittle-indexable. Unlike the Whittle index policy, our index policy does not require “indexability”; the indices can be computed regardless of indexability in the Whittle’s sense. Thus, our index policy is a promising alternative method for the class of RMABs of concern: it can be used when the Whittle index policy is not viable and it performs as well as the Whittle index policy even when the Whittle index policy is viable.

This article puts forth a multistream networking paradigm, referred to as soft-source-information-combining (SSIC), to support wireless Internet of Things (IoT) applications with ultrareliability requirements. For SSIC networking, an SSIC dispatcher at the source dispatches duplicates of packets over multiple streams, which may be established over different physical wireless networks. If a packet on a stream cannot be decoded due to wireless interference or noise, the decoder makes available the packet’s soft information. An aggregator then combines the soft information of the duplicates to boost reliability. Of importance are two challenges: 1) how to descramble the scrambled soft information from different streams to enable correct SSIC and 2) the construct of an SSIC dispatching and aggregation framework compatible with commercial network interface cards (NICs) and TCP/IP networks. To address the challenges, we put forth: 1) a soft descrambling (SD) method to minimize the bit-error rate (BER) and packet-error rate (PER) at the SSIC’s output and 2) an SSIC networking architecture readily deployable over today’s TCP/IP networks without specialized NICs. For concept proving and experimentation, we realized an SSIC system over two Wi-Fi’s physical paths in such a way that all legacy TCP/IP applications can enjoy the reliability brought forth by SSIC without modification. Experiments over our testbed corroborate the effectiveness of SSIC in lowering the packet delivery failure rate and the possibility of SSIC in providing 99.99% reliable packet delivery for short-range communication.

This article puts forth a networking paradigm, referred to as just-in-time (JIT) communication, to support client-server applications with stringent request-response latency requirement. Of interest is not just the round-trip delay of the network, but the actual request-response latency experienced by the application. The JIT framework contains two salient features. At the client side, the communication layer will “pull” a request from the client just when there is an upcoming transmission opportunity from the network. This ensures that the request contains information that is as fresh as possible (e.g., a sensor reading obtained just before the transmission opportunity). At the server side, the network ascertains that the server, after receiving and processing the request to generate a response (e.g., a control command to be sent to the client), will have a transmission opportunity at just this time. We realize the JIT system, including the protocol stack, over a time-division-multiple-access (TDMA) network implemented on a System-on-Chip (SoC) platform. We prove that a TDMA network with a power-of-2 time slots per superframe is optimal for realizing the server-side JIT function. Our experimental results validate that JIT networks can yield significantly lower request-response latency than networks without JIT support can.

As an important piece of the multi-tier computing architecture for future wireless networks, over-the-air computation (OAC) enables efficient function computation in multiple-access edge computing, where a fusion center aims to compute a function of the data distributed at edge devices. Existing OAC relies exclusively on the maximum likelihood (ML) estimation at the fusion center to recover the arithmetic sum of the transmitted signals from different devices. ML estimation, however, is much susceptible to noise. In particular, in the misaligned OAC where there are channel misalignments among received signals, ML estimation suffers from severe error propagation and noise enhancement. To address these challenges, this paper puts forth a Bayesian approach by letting each edge device transmit two pieces of statistical information to the fusion center such that Bayesian estimators can be devised to tackle the misalignments. Numerical and simulation results verify that, 1) For the aligned and synchronous OAC, our linear minimum mean squared error (LMMSE) estimator significantly outperforms the ML estimator. In the low signal-to-noise ratio (SNR) regime, the LMMSE estimator reduces the mean squared error (MSE) by at least 6 dB; in the high SNR regime, the LMMSE estimator lowers the error floor of MSE by 86.4%; 2) For the asynchronous OAC, our LMMSE and sum-product maximum a posteriori (SP-MAP) estimators are on an equal footing in terms of the MSE performance, and are significantly better than the ML estimator. Moreover, the SP-MAP estimator is computationally efficient, the complexity of which grows linearly with the packet length.

Most IoT systems use random access protocols for wireless communication. This paper considers an IoT node that generates periodic traffic to be delivered to a destination over a random access network; each packet of the node is expected to be delivered before its deadline. We say that the node is in a stressed period if, within a time interval, its successive packets miss their deadlines. In many systems, the worst-case performance is significantly affected by stressed periods. Characterizing the stochastic properties of stressed periods is thus of fundamental importance. In this paper, we use a fluid flow model to approximate the evolution of the buffer occupancy (i.e., backlog) at the transmitting node. We derive a relationship between buffer occupancy and delay and formally define a stressed period via a time interval in which the buffer occupancy exceeds a certain threshold. With this model, we analyze the dynamics of the buffer occupancy evolution and obtain the probability distributions of stressed period duration and delay. Real network experiments show that our model can well approximate the distributions of stressed period duration and delay in practical WiFi networks. The theoretical results of this paper can be used to analyze the robustness and worst-case performance of IoT monitoring and control systems built on random access networks.

This paper presents the implementation and experimental evaluation of a short-packet physical-layer network coding (PNC) system. Implementation of short-packet PNC systems is challenging. First, short packets may have only a few pilot symbols for synchronization and channel estimation purposes. Increasing the number of pilots increases the overhead; decreasing the number of pilots, on the other hand, degrades the packet error rate performance. Second, many short-packet systems are meant for applications with very stringent delay requirements. Employing advanced but complex PNC channel decoding may result in unacceptable delay due to the processing delay. This work presents a low-complexity and low-overhead physical-layer design of OFDM-based short-packet PNC systems, implemented over the software-defined radio platform. Our design makes use of only a small number of pilots (without separate OFDM preamble symbols) to address issues such as slot synchronization, packet detection, carrier frequency offsets, and mismatched channel state information. Our design employs reduced-complexity XOR channel decoding based code-aided parameter estimation (that includes synchronization and channel estimation) to compensate for the limitations imposed by having a small number of pilots. This is the first demonstration that provides a practical framework for applying PNC to short-packet communications.

Interleaved Frequency Division Multiple Access (IFDMA) has the salient advantage of lower Peak-to-Average Power Ratio (PAPR) than its competitors like Orthogonal FDMA (OFDMA). A recent research effort of ours put forth a new IFDMA transceiver design significantly less complex than conventional IFDMA transceivers. The new IFDMA transceiver design reduces the complexity by exploiting a certain correspondence between the IFDMA signal processing and the Cooley-Tukey IFFT/FFT algorithmic structure so that IFDMA streams can be inserted/extracted at different stages of an IFFT/FFT module according to the sizes of the streams. Although our prior work has laid down the theoretical foundation for the new IFDMA transceiver’s structure, the practical realization of the transceiver on specific hardware with resource constraints has not been carefully investigated. This paper is an attempt to fill the gap. Specifically, this paper puts forth a heuristic algorithm called multi-priority scheduling (MPS) to schedule the execution of the butterfly computations in the IFDMA transceiver with the constraint of a limited number of hardware processors. The resulting FFT computation, referred to as MPS-FFT, has a much lower computation time than conventional FFT computation when applied to the IFDMA signal processing. Importantly, we derive a lower bound for the optimal IFDMA FFT computation time to benchmark MPS-FFT. Our experimental results indicate that when the number of hardware processors is a power of two: 1) MPS-FFT has near-optimal computation time; 2) MPS-FFT incurs less than 44.13% of the computation time of the conventional pipelined FFT.

Time-sensitive wireless networks are an important enabling building block for many emerging industrial Internet-of-Things (IoT) applications. Quick prototyping and evaluation of time-sensitive wireless technologies are desirable for research and development efforts. Software-defined radio (SDR), by allowing wireless signal processing on a personal computer (PC), has been widely used for such quick prototyping efforts. Unfortunately, because of theuncontrollable delaybetween the PC and the radio board, SDR is generally deemed not suitable for time-sensitive wireless applications that demand communication with low and deterministic latency. For a rigorous evaluation of its suitability for industrial IoT applications, this article conducts a quantitative investigation of the synchronization accuracy and end-to-end latency achievable by an SDR wireless system. To this end, we designed and implemented a time-slotted wireless system on the universal software radio peripheral (USRP) SDR platform. We developed a time synchronization mechanism to maintain synchrony among nodes in the system. To reduce the delays and delay jitters between the USRP board and its PC, we devised aJust-in-timealgorithm to ensure that packets sent by the PC to the USRP can reach the USRP just before the time slots they are to be transmitted. Our experiments demonstrate that 90% (100%) of the time slots of different nodes can be synchronized and aligned to within ±0.5 samples or$\pm 0.05\mu \text{s}$(±1.5 samples or$\pm 0.15\mu \text{s}$), and that the end-to-end packet delivery latency can be down to 3.75 ms. This means that SDR-based solutions can be applied in a range of IIoT applications that require tight synchrony and moderately low latency, e.g., sensor data collection, automated guided vehicle (AGV) control, and human–machine interaction (HMI).

This paper studies the minimum-age scheduling problem in a wireless sensor network where an access point (AP) monitors the state of an object via a set of sensors. The freshness of the sensed state, measured by the age-of-information (AoI), varies at different sensors and is not directly observable to the AP. The AP has to decide which sensor to query/sample in order to get the most updated state information of the object (i.e., the state information with the minimum AoI). In this paper, we formulate the minimum-age scheduling problem as a multi-armed bandit problem with partially observable arms and explore the greedy policy to minimize the expected AoI sampled over an infinite horizon. To analyze the performance of the greedy policy, we 1) put forth a relaxed greedy policy that decouples the sampling processes of the arms, 2) formulate the sampling process of each arm as a partially observable Markov decision process (POMDP), and 3) derive the average sampled AoI under the relaxed greedy policy as a sum of the average AoI sampled from individual arms. Numerical and simulation results validate that the relaxed greedy policy is an excellent approximation to the greedy policy in terms of the expected AoI sampled over an infinite horizon.

This paper proposes using the uncertainty of information (UoI), measured by Shannon’s entropy, as a metric for information freshness. We consider a system in which a central monitor observes M binary Markov processes through m communication channels (m

This paper investigates a futuristic spectrum sharing paradigm for heterogeneous wireless networks with imperfect channels. In the heterogeneous networks, multiple wireless networks adopt different medium access control (MAC) protocols to share a common wireless spectrum and each network is unaware of the MACs of others. This paper aims to design a distributed deep reinforcement learning (DRL) based MAC protocol for a particular network, and the objective of this network is to achieve a global$\alpha$-fairness objective. In the conventional DRL framework, feedback/reward given to the agent is always correctly received, so that the agent can optimize its strategy based on the received reward. In our wireless application where the channels are noisy, the feedback/reward (i.e., the ACK packet) may be lost due to channel noise and interference. Without correct feedback, the agent (i.e., the network user) may fail to find a good solution. Moreover, in the distributed protocol, each agent makes decisions on its own. It is a challenge to guarantee that the multiple agents will make coherent decisions and work together to achieve the same objective, particularly in the face of imperfect feedback channels. To tackle the challenge, we put forth (i) a feedback recovery mechanism to recover missing feedback information, and (ii) a two-stage action selection mechanism to aid coherent decision making to reduce transmission collisions among the agents. Extensive simulation results demonstrate the effectiveness of these two mechanisms. Last but not least, we believe that the feedback recovery mechanism and the two-stage action selection mechanism can also be used in general distributed multi-agent reinforcement learning problems in which feedback information on rewards can be corrupted.

Over-the-air computation (OAC) is a promising technique to realize fast model aggregation in the uplink of federated edge learning (FEEL). OAC, however, hinges on accurate channel-gain precoding and strict synchronization among edge devices, which are challenging in practice. As such, how to design the maximum likelihood (ML) estimator in the presence of residual channel-gain mismatch and asynchronies is an open problem. To fill this gap, this paper formulates the problem of misaligned OAC for FEEL and puts forth a whitened matched filtering and sampling scheme to obtain oversampled, but independent samples from the misaligned and overlapped signals. Given the whitened samples, a sum-product ML (SP-ML) estimator and an aligned-sample estimator are devised to estimate the arithmetic sum of the transmitted symbols. In particular, the computational complexity of our SP-ML estimator is linear in the packet length, and hence is significantly lower than the conventional ML estimator. Extensive simulations on the test accuracy versus the average received energy per symbol to noise power spectral density ratio (EsN0) yield two main results: 1) In the low EsN0 regime, the aligned-sample estimator can achieve superior test accuracy provided that the phase misalignment is not severe. In contrast, the ML estimator does not work well due to the error propagation and noise enhancement in the estimation process. 2) In the high EsN0 regime, the ML estimator attains the optimal learning performance regardless of the severity of phase misalignment. On the other hand, the aligned-sample estimator suffers from a test-accuracy loss caused by phase misalignment.

This study applies reinforcement learning (RL) from the AI machine learning field to derive an optimal Bitcoin-like blockchain mining strategy. A salient feature of the RL learning framework is that an optimal (or near-optimal) strategy can be obtained without knowing the details of the blockchain network model. Previously, the most profitable mining strategy was believed to be honest mining encoded in the default blockchain protocol. It was shown later that it is possible to gain more mining rewards by deviating from honest mining. In particular, the mining problem can be formulated as a Markov Decision Process (MDP) which can be solved to give the optimal mining strategy. However, solving the mining MDP requires knowing the values of various parameters that characterize the blockchain network model. In real blockchain networks, these parameter values are not easy to obtain and may change over time. This hinders the use of the MDP model-based solution. In this study, we employ RL to dynamically learn a mining strategy with performance approaching that of the optimal mining strategy. Since the mining MDP problem has a nonlinear objective function (rather than linear functions of standard MDP problems), we design a new multidimensional RL algorithm to solve the problem. Experimental results indicate that, without knowing the parameter values of the mining MDP model, our multidimensional RL mining algorithm can still achieve optimal performance over time-varying blockchain networks.

This article puts forth a new channel coding paradigm for multi-source information streams with Age of Information (AoI) requirements. The recently introduced AoI metric characterizes the freshness of information, defined as the time elapsed since the generation of the last successfully received update. We study a setup in which a large number of sensors want to send update information to a common monitor with the help of aggregators. Specifically, an aggregator collects update packets from sensors and forwards them to the monitor. Conventional block codes (such as LDPC codes) that encode and decode each update packet separately do not perform well in such an information aggregation and update scenario. When update packets suffer from packet loss, we show that block codes lead to high instantaneous AoI because a sensor waits for a long time for the next update opportunity. This article investigates stream-based codes to tackle this problem. A distinguishing feature of stream-based codes is the joint encoding of update packets from different sensors, and a series of coded packets are sent continuously like a stream. Different update packets are then jointly decoded using multiple coded packets from the stream. A key challenge with AoI requirements is the joint design of error corrections of old packets and fast decodings of new packets. We design a practical encoding-decoding scheme and a sliding decoding window mechanism to control the decoding complexity. We evaluate two AoI metrics, average AoI and bounded AoI. In particular, bounded AoI corresponds to an AoI threshold that the instantaneous AoI is below a large percentage of the time. Experimental results on software-defined radio show that stream-based codes significantly outperform block codes in both average AoI and bounded AoI under varying channel conditions. Overall, stream-based codes provide a viable channel coding solution to multi-source information streams with timely update requirements.

Software-defined Internet-of-Things networking (SDIoT) greatly simplifies the network monitoring in large-scale IoT networks by per-flow sampling, wherein the controller keeps track of all the active flows in the network and samples the IoT devices on each flow path to collect real-time flow statistics. There is a tradeoff between the controller’s sampling preference and the balancing of loads among devices. On the one hand, the controller may prefer to sample some of the IoT devices on the flow path because they yield more accurate flow statistics. On the other hand, it is desirable to sample the devices uniformly so that their energy consumptions and lifespan are balanced. This paper formulates the flow sampling problem in large-scale SDIoT networks by means of a Markov decision process and devises policies that strike a good balance between these two goals. Three classes of policies are investigated: the optimal policy, the state-independent policies, and the index policies (including the Whittle index and a second-order index policies). The second-order index policy is the most desired policy among all: 1) in terms of performance, it is on an equal footing with the Whittle index policy, and outperforms the state-independent policies by much; 2) in terms of complexity, it is much simpler than the optimal policy, and is comparable to state-independent policies and the Whittle index policy; 3) in terms of realizability, it requires no prior information on the network dynamics, hence is much easier to implement in practice.

Life-critical warning message, abbreviated as warning message, is a special event-driven message that carries emergency information in Vehicle-to-Everything (V2X). Three important characteristics that distinguish warning messages from ordinary vehicular messages are sporadicity, crowding, and ultra-time-criticality. Specifically, warning messages come only once in a while in a sporadic manner; however, when they come, they tend to come as a crowd and they need to be delivered in short order. This paper puts forth a medium-access control (MAC) protocol for warning messages. The overall MAC protocol operates by means of interrupt-and-access. To circumvent potential inefficiency arising from message sporadicity, we adopt an override network architecture whereby warning messages are delivered on the spectrum of the ordinary vehicular messages. A vehicle with a warning message first sends an interrupt signal to pre-empt the transmission of ordinary messages, so that the warning message can use the wireless spectrum originally allocated to ordinary messages. In this way, no exclusive spectrum resources need to be pre-allocated to the sporadic warning messages. Following the interrupt, for transmissions of ultra-time-critical crowd messages, we employ advanced channel access techniques to ensure reliable message delivery within an ultra-short time in the order of 10 ms.

This article studies information freshness in information update systems with nonorthogonal multiple access (NOMA). Information freshness is characterized by age of information (AoI), defined as the time elapsed since the generation of the last successfully received update. Conventional orthogonal multiple access (OMA) systems, say time-division multiple access (TDMA) systems, lead to high average AoI when a large number of users take turns to transmit their latest samples to a common receiver over a wireless medium. In contrast to OMA, NOMA allows multiple users to transmit simultaneously. Although NOMA could lead to higher packet error rates (PER) due to the wireless interference among users, we show that higher PERs do not always lead to a higher average AoI. Specifically, our experiments on software-defined radio indicate that NOMA with conventional multiuser decoding (MUD) techniques leads to higher PERs but lower average AoI than OMA does in the high SNR regime. Furthermore, to improve the AoI performance in the medium SNR regime, we combine MUD with physical-layer network coding (PNC), a technique that turns wireless interference into useful network-coding information. PNC works well even when the SNRs of different NOMA users do not differ much. This article is the first attempt to apply PNC to information update systems. Experiments show that the combined use of PNC and MUD reduces the average AoI significantly in a practical network setting. Overall, PNC-enabled NOMA is a promising solution to information update systems.

This article presents a cross-layer design of backbone-assisted wireless local area network (WLAN) for dense WLAN deployment. The popularity of 802.11-based WLANs leads to dense WLAN deployment in geographically limited space, including dense access points (AP) and dense users. With dense APs, an AP could overhear packets destined for other APs. Backbone-assisted WLAN is a new system architecture where cooperative APs share the overheard packets through a backbone network, thereby reducing packet retransmission and improving system throughput. Conventional WLAN, such as Wi-Fi, uses Stop-and-Wait ARQ. This article argues that Stop-and-Wait does not work well with backbone-assisted WLAN because of large backbone delays. We first show that with a variant of Selective Repeat ARQ tailored for backbone-assisted WLAN, a single-user backbone-assisted WLAN system can achieve substantial throughput improvement over that with Stop-and-Wait ARQ. Then, we put forth a new system architecture targeted for dense users, referred to as network-coded backbone-assisted WLAN, in which multiple users are allowed to transmit simultaneously. A distinguishing feature of this system is the joint use of physical-layer network-coding (PNC) decoding and multiuser decoding (MUD) in multipacket reception. This article is the first attempt to design an ARQ for multiuser backbone-assisted WLAN. Our overall system design solves a PNC sequence obfuscation problem and addresses long packet latency in Selective Repeat ARQ. Experiments on our software-defined radio prototype indicate that network-coded Ethernet-backbone-assisted WLAN can achieve high system throughput and low packet latency. Specifically, the system throughput can outperform an MUD-only multiuser WLAN and a single-user WLAN by 60 and 100 percent, respectively. Overall, we believe that network-coded backbone-assisted WLAN is a viable solution for boosting throughput and reducing latency in dense WLAN environments.

This paper investigates a new class of carrier-sense multiple access (CSMA) protocols that employ deep reinforcement learning (DRL) techniques, referred to as carrier-sense deep-reinforcement learning multiple access (CS-DLMA). The goal of CS-DLMA is to enable efficient and equitable spectrum sharing among a group of co-located heterogeneous wireless networks. Existing CSMA protocols, such as the medium access control (MAC) protocol of WiFi, are designed for a homogeneous network in which all nodes adopt the same protocol. Such protocols suffer from severe performance degradation in a heterogeneous environment where there are nodes adopting other MAC protocols. CS-DLMA aims to circumvent this problem by making use of DRL. In particular, this paper adopts α-fairness as the general objective of CS-DLMA. With α-fairness, CS-DLMA can achieve a range of different objectives (e.g., maximizing sum throughput, achieving proportional fairness, or achieving max-min fairness) when coexisting with other MACs by changing the value of α. A salient feature of CS-DLMA is that it can achieve these objectives without knowing the coexisting MACs through a learning process based on DRL. The underpinning DRL technique in CS-DLMA is deep Q-network (DQN). However, the conventional DQN algorithms are not suitable for CS-DLMA due to their uniform time-step assumption. In CSMA protocols, time steps are non-uniform in that the time duration required for carrier sensing is smaller than the duration of data transmission. This paper introduces a non-uniform time-step formulation of DQN to address this issue. Our simulation results show that CS-DLMA can achieve the general α-fairness objective when coexisting with TDMA, ALOHA, and WiFi protocols by adjusting its own transmission strategy. Interestingly, we also find that CS-DLMA is more Pareto efficient than other CSMA protocols, e.g., p-persistent CSMA, when coexisting with WiFi. Although this paper focuses on the use of our non-uniform time-step DQN formulation in wireless networking, we believe this new DQN formulation can also find use in other domains.

We design and implement Publication Chain (PubChain), a decentralized open-access publication platform built on decentralized and distributed technologies of blockchain and IPFS peer-to-peer file sharing systems. The existing publication platforms have some severe drawbacks. First, instead of promoting widespread knowledge sharing, access to publications on the platforms owned by publishers is often on a fee basis. This drawback of pay wall prevents researchers from "standing on the shoulders of giants". Moreover, the peer review process on most all existing publication platforms (including both openaccess and publisher platforms) is prone to be ineffective, since there is no proper incentive to reviewers for performing high-qualified reviews. PubChain is an alternative platform to the existing publication venues aiming to address their drawbacks. No central third-party owns the contents (i.e., papers and reviews) of PubChain. Exploiting blockchain technology, we devise an elaborate incentive scheme on PubChain to incentivize key stakeholders (i.e., authors, readers and reviewers) to participate publication activities on PubChain in a substantive manner by earning credits and rewards through self-motivated interactions. We have performed simulations to investigate the robustness of our proposed incentive scheme against fraudulent publications and reviews. We also have implemented a prototype of PubChain to demonstrate its key concepts.

Significant sampling is an adaptive monitoring technique proposed for highly dynamic networks with centralized network management and control systems. The essential spirit of significant sampling is to collect and disseminate network state information when it is of significant value to the optimal operation of the network, and in particular when it helps identify the shortest routes. Discovering the optimal sampling policy that specifies the optimal sampling frequency is referred to as the significant sampling problem. Modeling the problem as a Markov Decision process, this paper puts forth a deep reinforcement learning (DRL) approach to tackle the significant sampling problem. This approach is more flexible and general than prior approaches as it can accommodate a diverse set of network environments. Experimental results show that, 1) by following the objectives set in the prior work, our DRL approach can achieve performance comparable to their analytically derived policy φ' - unlike the prior approach, our approach is model-free and unaware of the underlying traffic model; 2) by appropriately modifying the objective functions, we obtain a new policy which addresses the never-sample problem of policy φ', consequently reducing the overall cost; 3) our DRL approach works well under different stochastic variations of the network environment - it can provide good solutions under complex network environments where analytically tractable solutions are not feasible.

This paper explores the application of physical-layer network coding (PNC) for short-packet transmissions. PNC can potentially reduce the communication delay in relay-assisted wireless networks and can thus be instrumental in realizing short-packet communication systems with stringent delay requirements. In this work, first, we first derive an achievability bound for channel-coded short-packet PNC systems. Based on the random-coding error-exponent, the bound serves as a benchmark for short-packet PNC operating with traditional preamble-aided channel estimation and XOR channel decoding. Second, we design a blind channel estimation algorithm and a code-aided channel estimation algorithm for short-packet PNC systems. Both outperform the traditional preamble-aided channel estimation for PNC systems operating with mismatched channel-state-information. As a case study, we compare the three algorithms for packets of 128 symbols over a two-way relay channel. The results show that the blind algorithm outperforms the code-aided algorithm and preamble-aided algorithm by almost 0.2 and 1.5 dB respectively. Furthermore, the blind algorithm achieves the target packet error rate of 10-4within 0.5 dB of the random coding bound of an imaginary system in which perfect channel-state-information is available at the relay at no cost (i.e., channel estimation is not required in the imaginary system). The bound and the algorithms give us a fundamental framework for applying PNC to short-packet transmissions.

This paper derives the maximum achievable sum-rate and presents the optimal encoding/decoding framework for rate-diverse wireless network coding (RD-WNC) over broadband channels consisting of multiple parallel subchannels. RD-WNC applies to a communication scenario in which a base station wants to deliver two different messages with different rates to two users. The base station combines the two separate messages into one network-coded message and broadcasts the network-coded message to both users. Each user then extracts its desired message from the network-coded message by subtracting from it the other message, which we assume to be side information available to the user. Deriving the maximum achievable sum-rate for RD-WNC is challenging when the channel consists of multiple parallel subchannels with different channel coefficients (e.g., the subcarrier channels of OFDM systems), since apart from the rate allocation between the two users, optimal power allocation among multiple subchannels needs to be identified. The first contribution of this paper is a new “mountain-leveling” power allocation algorithm to achieve the maximum sum-rate. With the resulting power allocation, we can then achieve the corresponding optimal sum-rate by having a separate encoding/decoding mechanism for each subchannels, but doing so is cumbersome and complex when the number of subchannels is large. The second contribution of this paper is a practical encoding/decoding framework using only one encoder-decoder mechanism for all subchannels without sacrificing sum-rate optimality. We provide numerical results to corroborate our theoretical findings and to demonstrate the benefits of our encoding/decoding framework.

Sequences play an important role in many applications and systems. Discovering sequences with desired properties has long been an interesting intellectual pursuit. This article puts forth a new paradigm, AlphaSeq, to discover desired sequences algorithmically using deep reinforcement learning (DRL) techniques. AlphaSeq treats the sequence discovery problem as an episodic symbol-filling game, in which a player fills symbols in the vacant positions of a sequence set sequentially during an episode of the game. Each episode ends with a completely filled sequence set, upon which a reward is given based on the desirability of the sequence set. AlphaSeq models the game as a Markov decision process (MDP) and adapts the DRL framework of AlphaGo to solve the MDP. Sequences discovered improve progressively as AlphaSeq, starting as a novice, and learns to become an expert game player through many episodes of game playing. Compared with traditional sequence construction by mathematical tools, AlphaSeq is particularly suitable for problems with complex objectives intractable to mathematical analysis. We demonstrate the searching capabilities of AlphaSeq in two applications: 1) AlphaSeq successfully rediscovers a set of ideal complementary codes that can zero-force all potential interferences in multi-carrier code-division multiple access (CDMA) systems and 2) AlphaSeq discovers new sequences that triple the signal-to-interference ratio-benchmarked against the well-known Legendre sequence-of a mismatched filter (MMF) estimator in pulse compression radar systems.

This paper puts forth a class of new transceiver designs for interleaved frequency division multiple access (IFDMA) systems. These transceivers are significantly less complex than conventional IFDMA transceivers. The simple new designs are founded on a key observation that multiplexing and demultiplexing of IFDMA data streams of different sizes are coincident with the IFFTs and FFTs of different sizes embedded within the Cooley-Tukey recursive FFT decomposition scheme. For flexible resource allocation, this paper puts forth a new IFDMA resource allocation framework called Multi-IFDMA, in which a user can be allocated multiple IFDMA streams. Our new transceivers are unified designs in that they can be used in conventional IFDMA as well as multi-IFDMA systems. Two other well-known multiple-access schemes are localized FDMA (LFDMA) and orthogonal FDMA (OFDMA). In terms of flexibility in resource allocation, Multi-IFDMA, LFDMA, and OFDMA are on an equal footing. With our new transceiver designs, however, IFDMA has the following advantages (besides other known advantages not due to our new transceiver designs): 1) IFDMA/Multi-IFDMA transceivers are significantly less complex than LFDMA transceivers; in addition, IFDMA/Multi-IFDMA has better Peak-to-Average Power Ratio (PAPR) than LFDMA; 2) IFDMA/Multi-IFDMA transceivers and OFDMA transceivers are comparable in complexity; but IFDMA/Multi-IFDMA has significantly better PAPR than OFDMA.

Interleaved Frequency Division Multiple Access (IFDMA) and Orthogonal FDMA (OFDMA) belong to a class of signal modulation and multiple-access techniques in which information of multiple users are multiplexed and carried on subcarriers within a shared spectrum. Compared with OFDMA, IFDMA has lower Peak-to-Average Power Ratio (PAPR). However, IFDMA poses two rigid constraints on subcarrier allocation: 1) the subcarriers occupied by a user must be evenly-spaced among the available subcarriers. 2) the number of subcarriers used by a user must be a divisor of the total number of subcarriers. Unless these constraints can be overcome, IFDMA may remain impractical despite its excellent PAPR. This paper investigates how to overcome these constraints to allow flexible and fine-grained subcarrier allocation in IFDMA. Specifically, we put forth i) a bit-reversal subcarrier allocation scheme whereby the problem of allocating evenly-spaced subcarriers is transformed to a more intuitive problem of filling contiguous bins; ii) a multi-stream IFDMA scheme whereby a user can have an arbitrary number of subcarriers. For the synchronous scenario in which user requests arrive in a synchronous manner, we show that IFDMA can achieve the same level of flexibility and granularity as OFDMA in subcarrier allocation. For the asynchronous scenario in which user requests arrive and depart asynchronously, we show that the blocking probability of IFDMA is only slightly worse than that of OFDMA: specifically, the gap between the blocking probabilities of IFDMA and OFDMA is only 2.56% at a moderate offered load.

This paper investigates coherent detection for physical-layer network coding (PNC) with short packet transmissions in a two-way relay channel (TWRC). PNC turns superimposed EM waves into network-coded messages to improve throughput in a relay system. To achieve this, accurate channel information at the relay is a necessity. Much prior work applies preambles to estimate the channel. For long packets, the preamble overhead is low because of the large data payload. For short packets, that is not the case. To avoid excessive overhead, we consider a set-up in which short packets do not have preambles. A key challenge is how the relay can estimate the channel and detect the network-coded messages jointly based on the received signals from the two end users. We design a coherent detector that makes use of a belief propagation (BP) algorithm to do so. For concreteness, we focus on binary frequency-shift-keying (FSK) modulation. We show how the BP algorithm can be simplified and made practical with Gaussian-mixture passing. In addition, we demonstrate that prior knowledge on the channel distribution is not needed with our framework. Benchmarked against the detector with prior knowledge of the channel distribution, numerical results show that our detector can have nearly the same performance without such prior knowledge.

We face a growing ecosystem of applications that produce and consume data at unprecedented rates and with strict latency requirements. Meanwhile, the bursty and unpredictable nature of their traffic can induce highly dynamic environments within networks which endanger their own viability. Unencumbered operation of these applications requires rapid (re)actions by Network Management and Control (NMC) systems which themselves depends on timely collection of network state information. Given the size of today's networks, collection of detailed network states is prohibitively costly for the network transport and computational resources. Thus, judicious sampling of network states is necessary for a cost-effective NMC system. This paper proposes a deep reinforcement learning (DRL) solution that learns the principle of significant sampling and effectively balances the need for accurate state information against the cost of sampling. Modeling the problem as a Markov Decision Process, we treat the NMC system as an agent that samples the state of various network elements to make optimal routing decisions. The agent will periodically receive a reward commensurate with the quality of its routing decisions. The decision on when to sample will progressively improve as the agent learns the relationship between the sampling frequency and the reward function. We show that our solution has a comparable performance to the recently published analytical optimal without the need for an explicit knowledge of the traffic model. Furthermore, we show that our solution can adapt to new environments, a feature that has been largely absent in the analytical considerations of the problem.

We propose a deep-learning approach for the joint MIMO detection and channel decoding problem. Conventional MIMO receivers adopt a model-based approach for MIMO detection and channel decoding in linear or iterative manners. However, due to the complex MIMO signal model, the optimal solution to the joint MIMO detection and channel decoding problem (i.e., the maximum likelihood decoding of the transmitted codewords from the received MIMO signals) is computationally infeasible. As a practical measure, the current model-based MIMO receivers all use suboptimal MIMO decoding methods with affordable computational complexities. This work applies the latest advances in deep learning for the design of MIMO receivers. In particular, we leverage deep neural networks (DNN) with supervised training to solve the joint MIMO detection and channel decoding problem. We show that DNN can be trained to give much better decoding performance than conventional MIMO receivers do. Our simulations show that a DNN implementation consisting of seven hidden layers can outperform conventional model-based linear or iterative receivers. This performance improvement points to a new direction for future MIMO receiver design.

This paper investigates a deep reinforcement learning (DRL)-based MAC protocol for heterogeneous wireless networking, referred to as a Deep-reinforcement Learning Multiple Access (DLMA). Specifically, we consider the scenario of a number of networks operating different MAC protocols trying to access the time slots of a common wireless medium. A key challenge in our problem formulation is that we assume our DLMA network does not know the operating principles of the MACs of the other networks-i.e., DLMA does not know how the other MACs make decisions on when to transmit and when not to. The goal of DLMA is to be able to learn an optimal channel access strategy to achieve a certain pre-specified global objective. Possible objectives include maximizing the sum throughput and maximizing α-fairness among all networks. The underpinning learning process of DLMA is based on DRL. With proper definitions of the state space, action space, and rewards in DRL, we show that DLMA can easily maximize the sum throughput by judiciously selecting certain time slots to transmit. Maximizing general α-fairness, however, is beyond the means of the conventional reinforcement learning (RL) framework. We put forth a new multi-dimensional RL framework that enables DLMA to maximize general α-fairness. Our extensive simulation results show that DLMA can maximize sum throughput or achieve proportional fairness (two special classes of α-fairness) when coexisting with TDMA and ALOHA MAC protocols without knowing they are TDMA or ALOHA. Importantly, we show the merit of incorporating the use of neural networks into the RL framework (i.e., why DRL and not just traditional RL): specifically, the use of DRL allows DLMA (i) to learn the optimal strategy with much faster speed and (ii) to be more robust in that it can still learn a near-optimal strategy even when the parameters in the RL framework are not optimally set.

This paper studies the transceiver design of the Gaussian two-pair two-way relay channel (TWRC), where two pairs of users exchange information through a common relay in a pairwise manner. Our main contribution is to show that the capacity of the Gaussian two-pair TWRC is achievable to within$\frac{1}{ 2}$bit for arbitrary channel conditions. For the outer bound, we derive a genie-aided bound of the Gaussian two-pair TWRC, which is tighter than the cut-set bound. For the inner bound, we develop a hybrid coding scheme involving Gaussian random coding, nested lattice coding, superposition coding, and network-coded decoding. We further present a message-reassembling strategy to decouple the coding design for the user-to-relay and relay-to-user links, so as to provide flexibility to fully exploit the channel randomness. We show that judicious power allocation at the users and at the relay is necessary to approach the channel capacity under various channel conditions.

In this paper, we study the multiuser detection (MUD) problem for a grant-free massive-device multiple access (MaDMA) system, where a large number of single-antenna user devices transmit sporadic data to a multi-antenna base station (BS). Specifically, we put forth two MUD schemes, termed random sparsity learning multiuser detection (RSL-MUD) and structured sparsity learning multiuser detection (SSL-MUD) for the time-slotted and non-time-slotted grant-free MaDMA systems, respectively. In RSL-MUD, active users generate and transmit data packets with random sparsity. In SSL-MUD, we introduce a sliding-window-based detection framework, and the user signals in each observation window naturally exhibit structured sparsity. We show that by exploiting the sparsity embedded in the user signals, we can recover the user activity state, the channel, and the user data in a single phase, without using pilot signals for channel estimation and/or active user identification. To this end, we develop a message-passing-based statistical inference framework for the BS to blindly detect the user data without any prior knowledge of the identities and the channel state information (CSI) of active users. The simulation results show that our RSL-MUD and SSL-MUD schemes significantly outperform their counterpart schemes in both reducing the transmission overhead and improving the error behavior of the system.

In this work, we study the non-time-slotted massive-device multiple access (MaDMA) problem where massive user devices transmit sporadic data to a multi-antenna base station (BS). We develop a structured sparsity learning based multiuser detection (SSL-MUD) scheme. By exploiting the structured sparsity naturally embedded in user signals, our SSL-MUD scheme is able to blindly detect the user packets without any prior knowledge of the user activity state (UAS) and the channel state information (CSI), and hence significantly reduces the transmission overhead. For the blind signal detection at the BS, we put forth the turbo bilinear generalized approximate message passing (Turbo-BiG-AMP) algorithm. Simulation results demonstrate that the Turbo-BiG- AMP algorithm significantly outperforms the existing compressed sensing based approach and achieves a performance comparable to that of the oracle linear minimum mean-square error (Oracle- LMMSE) algorithm (which assumes perfect knowledge of UAS and CSI at the BS).

This paper investigates noncoherent detection in a two-way relay channel operated with physical- layer network coding (PNC), assuming FSK modulation and short-packet transmissions. For noncoherent detection, the detector has access to the magnitude but not the phase of the received signal. For conventional communication in which a receiver receives the signal from a transmitter only, the phase does not affect the magnitude, hence the performance of the noncoherent detector is independent of the phase. PNC, on the other hand, is a multiuser system in which a receiver receives signals from multiple transmitters simultaneously. The relative phase of the signals from different transmitters affects the received signal magnitude through constructive-destructive interference. In particular, for good performance, the noncoherent detector of a multiuser system such as PNC must take into account the influence of the relative phase on the signal magnitude. Building on this observation, this paper delves into the fundamentals of PNC noncoherent detector design. To avoid excessive overhead, we assume a set-up in which the short packets in the PNC system do not have preambles. We show how the relative phase can be deduced directly from the magnitudes of the received data symbols, and that the knowledge of the relative phase thus deduced can in turn be used to enhance performance of noncoherent detection. We design a noncoherent detector that jointly estimates relative phase and detects data using a belief propagation algorithm. Numerical results show that our detector performs as well as a “fictitious” optimal detector that has perfect knowledge of the relative phase. Although this paper focuses on PNC with FSK modulation, we believe the insight of this paper applies generally to noncoherent detection in other multiuser systems with other modulations. Specifically, our insight is that the relative phase of overlapped signals affects the signal magnitude in multiuser systems, but fortunately the relative phase can be deduced from the magnitudes and this knowledge can be used to improve detection performance.

Life-critical warning message, abbreviated as warning message, is a special event-driven message that carries emergency warning information in Vehicle-to-Everything (V2X). Two important characteristics that distinguish warning messages from ordinary vehicular messages are sporadicity and ultra-time-criticality. This paper puts forth a medium-access control (MAC) protocol for warning messages. To circumvent potential inefficiency arisen from sporadicity, we propose an override network architecture whereby warning messages are delivered on the network of the ordinary vehicular messages. Specifically, a vehicle with a warning message first sends an interrupt signal to pre- empt the transmission of ordinary messages, so that the warning message can use the wireless spectrum originally allocated to ordinary messages. In this way, no exclusive spectrum resources need to be pre-allocated to the sporadic warning messages. To meet the ultra-time- criticality requirement, we use advanced MAC techniques (e.g., coded ALOHA) to ensure highly reliable delivery of warning messages within an ultra-short time in the order of 10 ms. The overall MAC protocol operates by means of interrupt-and-access. We investigate the use of spread spectrum sequences as interrupt signals. Simulation results show that the missed detection rate (MDR) of the interrupt signals can be very small given sufficient sequence length, e.g., when SIR is -32 dB, a 0.43 ms sequence (64512 symbols, 150 MHz) can guarantee an MDR of 0.0001. For channel access, simulation results indicate that coded ALOHA can potentially satisfy the ultra- time-criticality requirements of warning messages. In the stringent scenario where 30 emergency nodes broadcast warning messages simultaneously, the message loss rate can be kept lower than 0.0001 with delay less than 10 ms.

This paper investigates the use of deep reinforcement learning (DRL) in the design of a "universal" MAC protocol referred to as Deep-reinforcement Learning Multiple Access (DLMA). The design framework is partially inspired by the vision of DARPA SC2, a 3-year competition whereby competitors are to come up with a clean-slate design that "best share spectrum with any network(s), in any environment, without prior knowledge, leveraging on machine-learning technique". While the scope of DARPA SC2 is broad and involves the redesign of PHY, MAC, and Network layers, this paper's focus is narrower and only involves the MAC design. In particular, we consider the problem of sharing time slots among a multiple of time-slotted networks that adopt different MAC protocols. One of the MAC protocols is DLMA. The other two are TDMA and ALOHA. The DRL agents of DLMA do not know that the other two MAC protocols are TDMA and ALOHA. Yet, by a series of observations of the environment, its own actions, and the rewards - in accordance with the DRL algorithmic framework - a DRL agent can learn the optimal MAC strategy for harmonious co-existence with TDMA and ALOHA nodes. In particular, the use of neural networks in DRL (as opposed to traditional reinforcement learning) allows for fast convergence to optimal solutions and robustness against perturbation in hyper- parameter settings, two essential properties for practical deployment of DLMA in real wireless networks.

Applying physical-layer network coding (PNC) to vehicular ad-hoc networks (VANETs) can theoretically boost the network throughput by 100%, thus partially addressing the intermittent node connectivity and short contact time issues caused by high speed vehicle motions. However, the application of OFDM modulated PNC in VANETs faces detrimental effects caused by carrier frequency offsets (CFOs) and time-frequency-selective channels. CFOs may destroy the orthogonality of OFDM subcarriers, resulting in inter-carrier interference (ICI). The CFOs of two transmitters may also be different, and cannot be removed by CFO tracking and equalization at the receiver as in conventional single-user communication even if the CFOs are known. In addition, time-frequency- selective channels due to delay and Doppler spreads are difficult to estimate and non-accurate channel estimations will increase the detection bit error rate (BER). To address the two challenges, this paper proposes an ICI-aware approach that jointly exploits pilot and data for channel estimation and data detection. Specifically, our approach jointly uses the belief propagation (BP) algorithm to mitigate the CFO/ICI effect for data detection, and the expectation maximization (EM) algorithm to accurately estimate the channels. A linear interpolation method and an ICI compensation method are simulated as benchmarks. Simulation results indicate that our approach improves the BER performance compared to the two benchmarks (more than 2 dB SNR gain in most cases), especially in the high SNR regime.

Future multi-terminal communication networks such as machine-to-machine, telecommand and remote control communication systems will be based on short-packet transmissions. Physical-layer network coding (PNC) in such multi-terminal communication systems can potentially enhance network throughput and reduce communication latency. For practical PNC systems, preambles are contained in transmissions for accurate estimation of the channel-state-information (CSI). Identifying good preamble-length regimes, however, is critical for good performance of short-packet PNC systems. Long preambles for short packets reduce spectral efficiency. On the other hand, short preambles compromise accuracy of estimated CSI, leading to sub-par packet error rate (PER) performance. This paper studies the impact of preamble length on the performance of short-packet PNC systems. Specifically, we use random coding bound to quantify PER of channel-coded mismatched-CSI PNC systems and identify the preamble-length regime that achieves the target PER with minimum Eb/No. As an example, we consider a simple yet practically relevant setup of a BPSK modulated PNC system in a two-way relay channel operating with short packets of 128 symbols. Our results show that a preamble of 20 to 30 symbols provides the minimum PER for a wide range of Eb/N0and achieves a target PER of 10-3with minimum Eb/No.

This paper presents the first network-coded multiple access (NCMA) downlink system on unmanned aerial vehicle (UAV). The use of UAV as a mobile aerial base station has received much attention in the 5G community in the context of highly mobile and flexible-configurable communication systems. As UAVs are limited by their flight time in the air, achieving high spectral and power efficiency while they are inflight is of great importance. Non-orthogonal multiple access (NOMA) is a promising technique to increase the spectral and power efficiency. Conventional NOMA downlink that makes use of superposition coding in combination with successive interference cancellation (SIC) decoding does not work well in scenarios where the channel conditions of different downlink users are not readily available at the transmitter side. This is the case, for example, in the UAV scenario in which the UAV transmitter moves quickly, causing the channel conditions to vary in a very dynamic manner. This paper investigates a new NOMA downlink architecture, referred to as network-coded multiple access. In the absence of channel information, an NCMA transmitter allocates equal power to the superposed signals of different downlink users. A key challenge is how to achieve high NOMA throughput under such equal power allocation. Toward this end, NCMA makes joint use of physical-layer network coding (PNC) and multiuser decoding (MUD) together with a new superposition coding scheme, referred to as NCMA-based superposition coding. In NCMA-based superposition coding, equal powers are allocated to the signals of different users, but a relative phase offset between the signals is introduced to optimize PNC and MUD decodings. To demonstrate the feasibility and advantage of the NCMA downlink, we implemented our designs on a software-defined radio and UAV. Our experimental results show that NCMA is robust against varying channel conditions. Moreover, the throughput of NCMA can outperform the state-of-the-art SIC-based superposition coding system and the time-division multiple access system by 50% and 80%, respectively, demonstrating that NCMA is a practical solution to boost throughput in UAV NOMA.

Physical-layer network coding (PNC) is a communications paradigm that exploits overlapped transmissions to boost the throughput of wireless relay networks. A high point of PNC research was a theoretical proof that PNC that makes use of nested lattice codes could approach the information-theoretic capacity of a two-way relay network (TWRN), where two end nodes communicate via a relay node. The capacity cannot be achieved by conventional methods of time-division or straightforward network coding. Many practical challenges, however, remain to be addressed before the full potential of lattice-coded PNC can be realized. Two major challenges are: (1) for good performance in lattice-coded PNC, channels of simultaneously transmitting nodes must be aligned; (2) for lattice-coded PNC to be practical, the complexity of lattice encoding at the transmitters and lattice decoding at the receiver must be reduced. We address these challenges and implement a first lattice-coded PNC system on a software-defined radio (SDR) platform. Specifically, we design and implement a low-overhead channel precoding system that accurately aligns the channels of distributed nodes. In our implementation, the nodes use low-cost temperature-compensated oscillators (TCXO) only-a consequent challenge is that the channel alignment must be done more frequently and more accurately compared with the use of expensive oscillators. The low overhead and accurate channel alignment are achieved by (1) a channel precoding system implemented over FPGA to realize fast feedback of channel state information; (2) a highly-accurate carrier frequency offset (CFO) estimation method; and (3) a partial-feedback channel estimation method that significantly reduces the amount of feedback information from the receiver to the transmitters for channel precoding at the transmitters. To reduce lattice encoding and decoding complexities, we adapt the low-density lattice code (LDLC) for use in PNC systems. Experiments show that our implemented lattice-coded PNC achieves better bit error rate performance compared with timedivision and straightforward network coding systems. It also has good throughput performance in mobile non-LoS scenarios.

This paper presents the Distributed Cooperative Access Points (DCAP) system that can simultaneously serve multiple clients using cooperative beamforming to increase the capacity of WiFi-type wireless networks. The distributed APs are connected by Ethernet and driven by independent low-cost local oscillators. To facilitate cooperative beamforming, we address three major challenges: the phase synchronization, the channel state information (CSI) measurement, and the user selection. Specifically, we develop 1) a cooperative tracking scheme to track signal phase drifts at symbol level without adding extra hardware complexity; 2) an incremental CSI estimation mechanism that removes the per-frame CSI measurement overhead of previous approaches; and 3) a simple random user selection algorithm that scales the network capacity linearly and delivers over 70 percent performance compared to the optimal but complex greedy algorithm. We implement DCAP on the Sora software radio platform and evaluate it in a wireless network with nine nodes. Experimental results show that the cooperative beamforming is feasible in practice, and our cooperative phase tracking can ensure strict phase alignment (≤ 0.03 radian) among APs during the entire beamforming period (1.2 ms). Otherwise, without tracking, phases may drift by 0.3 radian over merely 600 μs, causing that the symbol SNR decreases as large as 20 dB.

This paper investigates the noncoherent detection in a two-way relay channel operated with physical-layer network coding (PNC), assuming FSK modulation and short-packet transmissions. For noncoherent detection, the detector has access to the magnitude but not the phase of the received signal. For conventional communication in which a receiver receives the signal from a transmitter only, the phase does not affect the magnitude, and hence the performance of the noncoherent detector is independent of the phase. PNC, on the other hand, is a multiuser system in which a receiver receives signals from multiple transmitters simultaneously. The relative phase of the signals from different transmitters affects the received signal magnitude through constructive-destructive interference. In particular, for good performance, the noncoherent detector of a multiuser system such as PNC must take into account the influence of the relative phase on the signal magnitude. Building on this observation, this paper delves into the fundamentals of PNC noncoherent detector design. To avoid excessive overhead, we assume a set-up in which the short packets in the PNC system do not have preambles. We show how the relative phase can be deduced directly from the magnitudes of the received data symbols, and that the knowledge of the relative phase thus deduced can in turn be used to enhance performance of noncoherent detection. Our overall detector design consists of two components: 1) a channel gains estimator that estimates channel gains without preambles; and 2) a detector that builds on top of the estimated channel gains to jointly estimate relative phase and detect data using a belief propagation algorithm. Numerical results show that our detector performs nearly as well as a “fictitious” optimal detector that has perfect knowledge of the channel gains and relative phase. Although this paper focuses on PNC with FSK modulation, we believe that the insight of this paper applies generally to noncoherent detection in other multiuser systems with other modulations. Specifically, our insight is that the relative phase of overlapped signals affects the signal magnitude in multiuser systems, but fortunately the relative phase can be deduced from the magnitudes and this knowledge can be used to improve the detection performance.

This paper studies the transceiver design of the Gaussian two-pair two-way relay channel (TWRC), where two pairs of users exchange information through a common relay in a pairwise manner. Our main contribution is to show that our scheme can achieve the capacity of the two-pair TWRC to within 1/2 bit per user. In the proof, we develop a hybrid coding scheme involving Gaussian random coding, nested lattice coding, superposition coding, and network-coded decoding. Further, we present a message-reassembling strategy to decouple the coding design for the user-to-relay and relay-to-user links, so as to provide more flexibility to fully exploit the channel randomness. We also show that judicious power allocation among the superimposed codeword components at the relay is needed to approach the channel capacity.

In practical asynchronous physical-layer network coding (PNC) systems, the symbols from multiple transmitters to a common receiver may be misaligned. The good performance of an asynchronous PNC decoder hinges on accurate estimation of the symbol misalignment. This paper puts forth an optimal symbol misalignment estimator that considerably improves the estimation accuracy over prior schemes. Our scheme makes use of double baud-rate sampling of the received preambles consisting of Zadoff-Chu (ZC) sequences used by different transmitters. The sampling process is information-lossless because the double baud-rate samples capture all the information embedded in the continuous-time signal shaped by the assumed root-raised-cosine (RRC) pulse. The estimation consists of three steps: (i) cross-correlation of the double baud-rate samples with “interpolated double baud-rate ZC sequences” (ii) noise whitening; (iii) maximum likelihood (ML) estimation of the symbol misalignment. Extensive simulations show that the mean-square-error (MSE) performance of our estimator is superior to that of the baudrate estimator - e.g., for the RRC pulse with roll-off factor 1, our double baud-rate estimator yields improvement 8 dB over the baud-rate estimator. Furthermore, our double baudrate estimator yields square errors of less than 0.001 with 90% probability when the SNR is 10 dB in both AWGN and Rayleigh fading channels.

In this paper, we study the cache-aided cloud radio access network (C-RAN) with wireless fronthaul, where multiple cache-enabled users are served by multiple cache-enabled transmitters that are connected to a cloud processor through a wireless fronthaul link. We put forth a caching-and-delivery scheme that combines network-coded fronthaul transmission with cache-aided interference management. By broadcasting network-coded messages, the cloud processor provides additional information of the requested files to the transmitters, so as to reduce the edge delivery time. Based on our scheme, an achievable normalized delivery time (NDT) is derived with respect to the cache sizes and the fronthaul capacity.

This paper presents the first Network-Coded Multiple Access (NCMA) system with multiple users adopting different signal modulations, referred to as rate-diverse NCMA. A distinguishing feature of NCMA is the joint use of physical-layer network coding (PNC) and multiuser decoding (MUD) to boost throughput of multipacket reception systems. In previous NCMA systems, users adopt the same modulation regardless of their individual channel conditions. This leads to suboptimal throughput for many practical scenarios, especially when different users have widely varying channel conditions. A rate-diverse NCMA system allows different users to use modulations that are commensurate with their channel conditions. A key challenge is the design of PNC mapping and decoding mechanisms in NCMA when different users adopt different modulations. While there have been past work on non-channel-coded rate-diverse PNC, this paper is the first attempt to design channel-coded rate-diverse PNC to ensure the reliability of the overall NCMA system. Specifically, we put forth a symbol-splitting channel coding and modulation design so that PNC/NCMA can work over different modulations. We implemented our rate-diverse NCMA system on software-defined radios. Experimental results show that the throughput of rate-diverse NCMA can outperform the state-of-the-art rate-homogeneous NCMA by 80%. Overall, the introduction of rate diversity significantly boosts the NCMA system throughput in practical scenarios.

In this work, we derive the random coding error exponent for the uplink phase of a two-way relay system where physical layer network coding (PNC) is employed. The error exponent is derived for the practical (yet sub-optimum) XOR channel decoding setting. We show that the random coding error exponent under optimum (i.e., maximum likelihood) PNC channel decoding can be achieved even under the sub-optimal XOR channel decoding. The derived achievability bounds provide us with valuable insight and can be used as a benchmark for the performance of practical channel-coded PNC systems employing low complexity decoders when finite-length codewords are used.

This paper is a theoretical-plus-experimental investigation of practical 5G strategies for power-balanced non-orthogonal multiple access (NOMA). By allowing multiple users to share the same time and frequency, NOMA can scale up the number of served users and increase spectral efficiency compared with existing OMA. Conventional NOMA schemes with successive interference cancellation (SIC) do not work well when users with comparable received powers transmit together. To allow power-balanced NOMA (more exactly, near power-balanced NOMA), this paper investigates a new NOMA architecture, named network-coded multiple access (NCMA). A distinguishing feature of NCMA is the joint use of physical-layer network coding (PNC) and multiuser decoding to boost NOMA throughputs. We first show that a simple NCMA architecture in which all users use the same modulation, referred to as rate-homogeneous NCMA, can achieve substantial throughput improvement over SIC-based NOMA under near power-balanced scenarios. Then, we put forth a new NCMA architecture, referred to as rate-diverse NCMA, in which different users may adopt different modulations commensurate with their relative SNRs. A challenge for rate-diverse NCMA is the design of a channel-coded PNC system. This paper is the first attempt to design channel-coded rate-diverse PNC. Experimental results on our software-defined radio prototype show that the throughput of rate-diverse NCMA can outperform the state-of-the-art rate-homogeneous NCMA by 80%. Overall, rate-diverse NCMA is a practical solution for near power-balanced NOMA.

This paper presents several soft decision iterative decoding schemes for physical-layer network coding (PNC) operated with coded modulation (CM) and bit-interleaved coded modulation (BICM). With respect to PNC operated with CM, we consider network coding-based channel decoding (NC-CD) and multi-user complete decoding (MUD-NC) for PNC decoding at the relay. Their BICM counterparts are XOR-based channel decoding (XOR-CD) and MUD-XOR, respectively. First, we show that, when the decoding is non-iterative, there is a gap between the BICM capacities of both XOR-CD and MUD-XOR under Gray mapping and the capacities of their CM counterparts, NC-CD, and MUD-NC. This is in contrast to the conventional point-to-point communication system, for which the BICM capacity with Gray mapping is known to be very close to the CM capacity, without the need for iterative decoding. Second, we investigate the error performance of iteratively decoded BICM XOR-CD and MUD-XOR. Extrinsic information transfer chart analysis and simulation results indicate that for these Gray-mapped BICM PNC systems, iterative decoding can achieve considerable gains over non-iterative decoding. Again, this is in contrast to the Gray-mapped BICM point-to-point communication system, for which iterative decoding provides little gain over non-iterative decoding. We further show that Gray mapping gives rise to best PNC rate for MUD-XOR and XOR-CD systems among several bits-to-symbol mappings under study. Overall, our results indicate that BICM PNC systems exhibit different decoding behavior from conventional BICM point-to-point systems. This paper serves as a first foray into the investigation of this issue.

This paper proposes an encoding/decoding framework for achieving the optimal channel capacities of the two-user broadcast channel where each user (receiver) has the message targeted for the other user (receiver) as side information. Since the link qualities of the channels from the base station to the two users are different, their respective single-user non-broadcast channel capacities are also different. A goal is to simultaneously achieve/approach the single-user non-broadcast channel capacities of the two users with a single broadcast transmission by applying network coding. This is referred to as the rate-diverse wireless network coding problem. For this problem, this paper presents a capacity-achieving framework based on linear-structured nested lattice codes. The significance of the proposed framework, besides its theoretical optimality, is that it suggests a general design principle for linear rate-diverse wireless network coding going beyond the use of lattice codes. We refer to this design principle as the principle of virtual single-user channels. Guided by this design principle, we propose two implementations of our encoding/decoding framework using practical linear codes amenable to decoding with affordable complexities: the first implementation is based on Low Density Lattice Codes (LDLC) and the second implementation is based on Bit-interleaved Coded Modulation (BICM). These two implementations demonstrate the validity and performance advantage of our framework.

This paper presents the results of a comprehensive investigation of complex linear physicallayer network coding (PNC) in two-way relay channels. In this system, two nodes A and B communicate with each other via a relay R. Nodes A and B send complex symbols, wA and wB, simultaneously to relay R. Based on the simultaneously received signals, relay R computes a linear combination of the symbols, wN= αwA+ βwB, as a network-coded symbol and then broadcasts wN to nodes A and B. Node A then obtains wB from wN and its self-information wA by wB = β-1(wN -αwA). Node B obtains wB in a similar way. A critical question at relay R is as follows: “given channel gain ratio η = hA/hB, where hA and hB are the complex channel gains from nodes A and B to relay R, respectively, what is the optimal coefficients (α, β) that minimizes the symbol error rate (SER) of wN = αwA+ βwBwhen the relay attempts to detect wN in the presence of noise?” Our contributions with respect to this question are as follows: 1) we put forth a general Gaussian-integer formulation for complex linear PNC in which α, β, wA, wB, and wNare the elements of a finite field of Gaussian integers, that is, the field of 7G[i]/q, where q is a Gaussian prime. Previous vector formulation, in which wA, wB, and wN were represented by 2-D vectors and α and β were represented by 2 x 2 matrices, corresponds to a subcase of our Gaussian-integer formulation, where q is real prime only. Extension to the Gaussian prime q, where q can be complex, gives us a larger set of signal constellations to achieve different rates at different values of SNR; and 2) we show how to divide the complex plane of η into different Voronoi regions, such that the η within each Voronoi region shares the same optimal PNC mapping (αopt, βopt). We uncover the structure of the Voronoi regions that allows us to compute a minimum-distance metric that characterizes the SER of wN under optimal PNC mapping (αopt, βopt). Overall, the contributions in 1) and 2) yield a toolset for a comprehensive understanding of complex linear PNC in 7G[i]/q. We believe investigation of linear PNC beyond 7G[i]/q can follow the same approach.

The increasingly dense deployments of wireless CSMA networks arising from applications of Internet-of-things call for an improvement to mitigate the interference among simultaneous transmitting wireless devices. For cost efficiency and backward compatibility with legacy transceiver hardware, a simple approach to address interference is by appropriately configuring the carrier sensing thresholds in wireless CSMA protocols, particularly in dense wireless networks. Most prior studies of the configuration of carrier sensing thresholds are based on a simplified conflict graph model, whereas this paper considers a realistic signal-to-interference-and-noise ratio model. We provide a comprehensive study for two effective wireless CSMA protocols: Cumulative-interference-Power Carrier Sensing and Incremental-interference-Power Carrier Sensing, in two aspects: (1) static approach that sets a universal carrier sensing threshold to ensure interference-safe transmissions regardless of network topology, and (2) adaptive approach that adjusts the carrier sensing thresholds dynamically based on the feedback of nearby transmissions. We also provide simulation studies to evaluate the starvation ratio, fairness, and goodput of our approaches.

This paper presents the first reliable physical-layer network coding (PNC) system that supports real TCP/IP applications for the two-way relay network (TWRN). Theoretically, PNC could boost the throughput of TWRN by a factor of 2 compared with traditional scheduling (TS) in the high signal-to-noise (SNR) regime. Although there have been many theoretical studies on PNC performance, there have been relatively few experimental and implementation efforts. Our earlier PNC prototype, built in 2012, was an offline system that processed signals offline. For a system that supports real applications, signals must be processed online in real-time. Our real-time reliable PNC prototype, referred to as RPNC, solves a number of key challenges to enable the support of real TCP/IP applications. The enabling components include: 1) a time-slotted system that achieves μs-level synchronization for the PNC system; 2) reduction of PNC signal processing complexity to meet real-time constraints; 3) an ARQ design tailored for PNC to ensure reliable packet delivery; and 4) an interface to the application layer. We took on the challenge to implement all of the above with general-purpose processors in PC through an SDR platform rather than ASIC or FPGA. With all of these components, we have successfully demonstrated image exchange with TCP and two-party video conferencing with UDP over RPNC. Experimental results show that the achieved throughput approaches the PHY-layer data rate at high SNR, demonstrating the high efficiency of the RPNC system.

In this paper, we study the degrees of freedom (DoF) of the symmetric multi-relay multiple-input multiple-output Y channel, where three user nodes, each with M antennas, communicate via K geographically separated relay nodes, each with N antennas. For this model, we establish a general DoF achievability framework based on linear precoding and post-processing methods. The framework poses a nonlinear problem with respect to user precoders, user post-processors, and relay precoders. To solve this problem, we adopt an uplink-downlink asymmetric strategy, where the user precoders are designed for signal alignment and the user post-processors are used for interference neutralization. With the user precoder and post-processor designs fixed as such, the original problem then reduces to a problem of relay precoder design. To address the solvability of the system, we propose a general method for solving matrix equations. Together with the techniques of antenna disablement and symbol extension, an achievable DoF of the considered model is derived for an arbitrary setup of (K, M, N). We show that for K ≥ 2, the optimal DoF is achieved for (M/N) ∈ [0, max{(√(3K/3)), 1}) ∪ [((3K + (9K2- 12K)1/2)/6), ∞). We also show that the uplink-downlink asymmetric design proposed in this paper considerably outperforms the conventional approach based on uplink-downlink symmetry.

This paper studies protograph low-density paritycheck coded cooperation (CC) schemes for two-hop multi-relay systems with L relays over Nakagami-m quasi-static fading (QSF) channels. We propose two CC schemes, namely schemes I and II, with different maximum code rates to satisfy different transmission requirements. We further design a family of distributed rate-compatible root-protograph (RCRP) codes to achieve full diversity in CC-based multi-relay QSF channels. In particular, our RCRP codes with L + 1 sub-codewords can realize full diversity in scheme I, and our RCRP codes with two sub-codewords can achieve full diversity in scheme II with a maximum-ratio combiner. In addition, we estimate the asymptotic word error rate and bit error rate of our RCRP codes using a generalized protograph extrinsic information transfer algorithm, which is able to characterize the error performance of finite-length codewords accurately. Analysis and simulation show that our RCRP codes can achieve outage-limit-approaching performance in both multi-relay CC architectures. This makes the RCRP coding framework extremely attractive for multirelay cooperative communication applications with slow-varying fading.

In asynchronous physical-layer network coding (APNC) systems, the symbols from multiple transmitters to a common receiver may be misaligned. Knowledge of the amount of symbol misalignment, hence its estimation, is important to PNC decoding. This paper addresses the problems of symbol-misalignment estimation and optimal PNC decoding given the misalignment estimate, assuming the APNC system uses the root-raised-cosine pulse to carry signals (RRC-APNC). Our contributions are as follows. First, we put forth an optimal symbol-misalignment estimator that makes use of double baud-rate samples. Second, we devise optimal RRC-APNC decoders in the presence of non-exact symbol-misalignment estimates. In particular, we show how to whiten the colored noise in the double baud-rate samples to simplify the design of optimal decoders. Third, we investigate the decoding performance of various estimation-and-decoding schemes for RRC-APNC. Extensive simulations show that: 1) our double baud-rate estimator yields substantially more accurate symbol-misalignment estimates than the baud-rate estimator does; the mean square error gains are up to 8 dB and 2) an overall estimation-and-decoding scheme in which both estimation and decoding are based on double baud-rate samples yields much better performance than other schemes. Compared with a scheme in which both estimation and decoding are based on baud-rate samples, the double baud-rate sampling scheme yields 4.5 dB gains on symbol error rate performance in an additive white Gaussian noise channel, and 2 dB gains on packet error rate performance in a Rayleigh fading channel.

Physical-layer network coding (PNC) channel decoding at the relay is of key importance for good performance in PNC systems. However, PNC channel decoders can have prohibitive computation complexity. Low complexity non-iterative PNC channel decoders are desired in practice. For such PNC decoders, decoding performance may degrade significantly when there is a relative phase offset between the simultaneous signals of multiple nodes received at the relay, particularly when bit-likelihood-based decoding is adopted. In this paper, we thoroughly investigate and numerically quantify the impact of relative phase offset on decoding performance. To maintain good decoding performance under relative phase offset, we introduce and experimentally evaluate symbol-likelihood-based decoding (in contrast to bit-likelihood-based decoding) for PNC systems. Our experimental results show that symbol-likelihood-based decoding improves the packet throughput over bit-likelihood-based decoding by 100% to 400% at SNR of 15 dBs. Moreover, we study the computational complexity under both these decoding methods. We find that a reduced-complexity decoder with symbol-likelihood-based decoding provides the best performance-complexity tradeoff for practical PNC systems.

Physical-layer network coding (PNC) can potentially boost the throughput of a two-way relay network by 100% compared with conventional packet forwarding schemes. However, the complexity of PNC channel decoders can be considerably higher than the complexity of channel decoders for point-to-point communication systems. Although many PNC channel decoders proposed to date have good decoding performance, they may not be feasibly implemented in practical systems due to their high computation complexities. This paper presents a reduced-complexity decoder (RCD), a PNC decoder with adjustable decoding complexity that is amenable to real-time implementation. We experimentally evaluate the performance-complexity trade-off of RCD. Our experimental results show that RCD can achieve substantial throughput gain over state-of-the-art decoders proposed for real-time PNC systems.

We study the degrees of freedom (DoF) of a symmetric multi-relay multiple-input multiple-output (MIMO) Y channel, where three users, each equipped with M antennas, exchange messages via multiple geographically separated relay nodes, each with N antennas. We formulate a general DoF achievability problem assuming the use of linear precoding and post-processing. To solve this problem, we present a new uplink-downlink asymmetric strategy where the user precoders are designed for signal alignment and the user post-processors are used for interference neutralization. Based on that, we derive an achievable DoF of the considered model for an arbitrary antenna setup. The optimality of the derived DoF is established under certain antenna configurations. Also, we show that our design considerably outperforms the conventional uplink-downlink symmetric design.

This paper investigates the linear network coding map in a Physical-layer Network Coding (PNC) operated two-way relay network. To realize the full potential of Physical-layer Network Coding in high SNR regimes, we need to use high-order signaling beyond BPSK/QPSK. In a PNC system with high-order signaling, we can have many different choices for the network coding (NC) map. For linear network coding, the network-coding map is realized by coefficients corresponding to the weights of the linearly-combined network-coded message. Prior work on channel-coded linear PNC adopted the same network-coding coefficients as in non-channel-coded linear PNC. We find that the optimal coefficients for such uncoded systems are far from optimal for coded systems. We also show that the coefficients that maximize the computation rate in the “compute-and-forward” framework, which adopts nested lattice codes, are near optimal for linear PNC that adopts the LDPC codes.

This paper investigates various subtleties of applying linear physical-layer network coding (PNC) with q-level pulse amplitude modulation (q-PAM) in two-way relay channels. A critical issue is how the PNC system performs when the received powers from the two users at the relay are imbalanced. In particular, how would the PNC system perform under slight power imbalance that is inevitable in practice, even when power control is applied? To answer these questions, this paper presents a comprehensive analysis of q-PAM PNC. Our contributions are as follows. First, we give a systematic way to obtain the analytical relationship between the minimum distance of the signal constellation induced by the superimposed signals of the two users (a key performance determining factor) and the channel-gain ratio of the two users, for all q. In particular, we show how the minimum distance changes in a piecewise linear fashion as the channel-gain ratio varies. Second, we show that the performance of q-PAM PNC is highly sensitive to imbalanced received powers from the two users at the relay, even when the power imbalance is slight (e.g., the residual power imbalance in a power-controlled system). This sensitivity problem is exacerbated as q increases, calling into question the robustness of highorder modulated PNC. Third, we propose an asynchronized PNC system in which the symbol arrival times of the two users at the relay are deliberately made to be asynchronous. We show that such asynchronized PNC, when operated with a belief propagation decoder, can remove the sensitivity problem, allowing a robust high-order modulated PNC system to be built.

This paper investigates Automatic Repeat request (ARQ) designs for Physical-layer Network Coding (PNC) systems. Most prior work related to PNC explores its use in Two-Way Relay Channel (TWRC). We have previously found that, besides TWRC, there are many other PNC building blocks-building blocks are simple small network structures that can be used to construct a large network. In some of these PNC building blocks, the receivers can obtain side information through overhearing. Although such overheard information is not the target information that the receivers desire, the receivers can exploit the overheard information together with a network-coded packet received to obtain a desired native packet. This can yield substantial throughput gain. Our previous study, however, assumed what is sent always gets received. In practice, that is not the case. Error control is needed to ensure reliable communication. This paper focuses on ARQ designs for ensuring reliable PNC communication. The availability of overheard Information and its potential exploitation make the ARQ design of a network-coded system different from that of a non-network-coded system. In this paper, we lay out the fundamental considerations for such ARQ designs: 1) we put forth a framework to track the stored coded packets and overheard packets to increase the chance of packet extraction, and derive the throughput gain achieved therefore; 2) we investigate two variations of PNC ARQ, coupled and non-coupled ARQs, and prove that non-coupled ARQ is more efficient; 3) we show how to optimize parameters in PNC ARQ - specifically the window size and the ACK frequency - to minimize the throughput degradation caused by ACK feedback overhead and wasteful retransmissions due to lost ACK.

This paper aims at improving the distance-based location management scheme for mobile communication networks. In location management, a mobile terminal (MT) is tracked based on its location-update area (LA). The improvement is brought about by joint optimization of LA center and LA size. For LA center optimization (LCO), we determine the optimal center position of the LA given the initial position of the MT upon each location update. The investigation of optimal LA center has eluded research to date. Based on the popular continuous-time random walk (CTRW) mobility model, we propose an analytical framework that uses a diffusion equation to determine the optimal LA center that minimizes the total cost of location management, consisting of the location update cost and terminal paging cost. This framework allows us to easily model the non-Markovian movement of the MT and evaluate the impact of various measurable physical parameters (such as length of road section, angle between road sections, and road section crossing time) and LA center. In particular, we show that proper LA center can significantly reduce the total cost. For example, for the circular LA and low Poisson call-arrival rate, optimizing the LA center alone has the potential of reducing the cost by up to 37 percent. Joint optimization of the LA center and terminal paging scheme can reduce the cost even further. Simulations results match the theoretical analysis to a gap within 3 percent, indicating that our theoretical model is very accurate.

In this paper, we investigate the optimization of non-uniform linear antenna arrays (NULAs) for millimeterwave (mmWave) line-of-sight (LoS) multiple-input multipleoutput (MIMO) channels. Our focus is on the maximization of the system effective multiplexing gain (EMG), by optimizing the individual antenna positions in the transmit/receive NULAs. Here, the EMG is defined as the number of signal streams that are practically supported by the channel at a finite signal-to-noise ratio. We first derive analytical expressions for the asymptotic channel eigenvalues with arbitrarily deployed NULAs when, asymptotically, the end-to-end distance is sufficiently large compared with the aperture sizes of the transmit/receive NULAs. Based on the derived expressions, we prove that the asymptotically optimal NULA deployment that maximizes the achievable EMG should follow the groupwise Fekete-point distribution. Specifically, the antennas should be physically grouped into K separate ULAs with the minimum feasible antenna spacing within each ULA, where K is the target EMG to be achieved; in addition, the centers of these K ULAs follow the Fekete-point distribution. We numerically verify the asymptotic optimality of such an NULA deployment and extend it to a groupwise projected arch-type NULA deployment, which provides a more practical option for mmWave LoS MIMO systems with realistic nonasymptotic configurations. Numerical examples are provided to demonstrate a significant capacity gain of the optimized NULAs over traditional ULAs.

This paper presents the first network-coded multiple access (NCMA) system operated on higher- order modulations beyond BPSK. NCMA allows multiple nodes to transmit simultaneously to an access point (AP) to boost throughput of wireless local area networks (WLAN): the key idea is to jointly exploit multiuser decoding (MUD) and physical-layer network coding (PNC). High- order modulations are commonly adopted in WLAN systems when the signal-to-noise ratio (SNR) is medium or high. However, direct generalization of the existing NCMA decoding algorithm, originally designed for BPSK, to higher-order modulations will lead to huge performance degradation. We find that the throughput degradation is caused by the relative phase offset between received signals from different nodes. To circumvent the throughput degradation, this paper investigates an NCMA system with multiple receive antennas at the AP, referred to as MIMO-NCMA. We have implemented MIMO-NCMA on software-defined radios. Our experimental results show that, at SNR of 10dB, the throughput of MIMO-NCMA outperforms single-antenna NCMA and conventional distributed MIMO-MUD, respectively. We believe that MIMO-NCMA throughput can be further improved with modulations beyond QPSK (e.g., 64-QAM).

Slotted ALOHA can benefit from physical-layer network coding (PNC) by decoding one or multiple linear combinations of the packets simultaneously transmitted in a timeslot, forming a system of linear equations. Different systems of linear equations are recovered in different timeslots. A message decoder then recovers the original packets of all the users by jointly solving multiple systems of linear equations obtained over different timeslots. We propose the batched BP decoding algorithm that combines belief propagation (BP) and local Gaussian elimination. Compared with pure Gaussian elimination decoding, our algorithm reduces the decoding complexity from cubic to linear function of the number of users. Compared with the ordinary BP decoding algorithm for low-density generator-matrix codes, our algorithm has better performance and the same order of computational complexity. We analyze the performance of the batched BP decoding algorithm by generalizing the tree-based approach and provide an approach to optimize the system performance.

This paper considers physical-layer network coding (PNC) in vehicular ad-hoc network (VANET) to solve the problem of short contact time between fast-moving vehicles. PNC enables data exchange between nodes in a relay network within a short airtime, e.g., twice faster than relay networks based on traditional communication, and can be a powerful performance booster in VANET. One of the most important challenges in applying PNC to VANET, however, is the Doppler shift caused by vehicular motions. Doppler shift leads to carrier frequency offset (CFO) that induces inter-carrier interference (ICI) in OFDM systems. The ICI destroys the orthogonality of modulated symbols, causing degradation in PNC signal detection. This paper puts forth a detection method to mitigate the CFO/ICI effect on PNC. The method, referred to as BP-VPNC, makes use of a belief propagation (BP) algorithm to process the outputs of the OFDM correlators. BP extracts useful hidden information embedded in ICI to improve signal detection in VANET PNC. Our study shows that the BER performance of PNC VANET operated with BP-VPNC can be achieved close to that of traditional VANET at various CFO levels. These results suggest that with BP-VPNC, a potential shortcoming of PNC, vulnerability to CFO, can be circumvented, and that PNC can be used to overcome the short vehicular contact time in VANET.

This paper presents a first real-time network-coded multiple access (NCMA) system that jointly exploits physical (PHY)-layer network coding (PNC) and multiuser decoding (MUD) to boost the throughput of a wireless local area network (WLAN). NCMA is a new design paradigm for multipacket reception wireless networks, in which the access point can receive and decode several packets simultaneously transmitted by multiple users. Conventionally, multipacket reception is realized using MUD only, whereas the key idea of NCMA is to use PNC together with MUD to realize multipacket reception. Although the feasibility of NCMA has previously been studied by the authors, our previous NCMA prototype was a version with offline signal processing. In addition, our previous investigation left open a number of theoretical and implementation issues, the resolution of which is critical to the adoption of NCMA in real practice. The current investigation makes the following state-of-the-art contributions toward NCMA: 1) we demonstrate a first NCMA system with integrated real-time PHY and MAC-layer decoding; 2) we construct a new unified framework for MAC-layer decoding that yields higher throughput with faster decoding-the faster decoding is one of the key enablers of our real-time implementation; and 3) we design new PHY-layer decoding techniques that overcome the poor performance of the first-generation NCMA prototype at low SNR. Experimental results show that, compared with the previous NCMA prototype, our new NCMA prototype improves real-time throughput by more than 100% at medium-high SNR (≥ 8 dB).

In this paper, we investigate the capacity of a known interference channel, where a transmitter sends information to a receiver in the presence of a block-fading interference link, and the receiver knows the interference data but not the channel gain of the interference link. An upper bound and a lower bound for the capacity of this known interference channel are derived. Specifically, the capacity lower bound is achieved by a blind known interference cancellation (BKIC) scheme, which can remove the interference without the knowledge of the interference channel gain. We further show that the achievable lower bound of BKIC can approach the upper bound in high SNR regime. Our results show that the lack of the knowledge of the channel gain of the interfering link causes only a small fractional loss of degrees of freedom (capacity prelog).

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 investigates the fundamental building blocks of physical-layer network coding (PNC). Most prior work on PNC focused on its application in a simple two-way-relay channel (TWRC) consisting of three nodes only. Studies of the application of PNC in general networks are relatively few. This paper is an attempt to fill this gap. We put forth two ideas: a general network can be decomposed into small building blocks of PNC, referred to as the PNC atoms, for scheduling of PNC transmissions; and we identify nine PNC atoms, with TWRC being one of them. Three major results are as follows. First, using the decomposition framework, the throughput performance of PNC is shown to be significantly better than those of the traditional multi-hop scheme and the conventional network coding scheme. For example, under heavy traffic volume, PNC can achieve 100% throughput gain relative to the traditional multi-hop scheme. Second, PNC decomposition based on a variety of different PNC atoms can yield much better performance than PNC decomposition based on the TWRC atom alone. Third, three out of the nine atoms are most important to good performance. Specifically, the decomposition based on these three atoms is good enough most of the time, and it is not necessary to use the other six atoms.

This paper investigates the decoding process of asynchronous convolutional-coded physical-layer network coding (PNC) systems. Specifically, we put forth a layered decoding framework for convolutional-coded PNC consisting of three layers: symbol realignment layer, codeword realignment layer, and joint channel-decoding network coding (Jt-CNC) decoding layer. Our framework can deal with phase asynchrony (phase offset) and symbol arrival-time asynchrony (symbol misalignment) between the signals simultaneously transmitted by multiple sources. A salient feature of this framework is that it can handle both fractional and integral symbol misalignments. For the decoding layer, instead of Jt-CNC, previously proposed PNC decoding algorithms (e.g., XOR-CD and reduced-state Viterbi algorithms) can also be used with our framework to deal with general symbol misalignments. Our Jt-CNC algorithm, based on belief propagation, is BER-optimal for synchronous PNC and near optimal for asynchronous PNC. Extending beyond convolutional codes, we further generalize the Jt-CNC decoding algorithm for all cyclic codes. Our simulation shows that Jt-CNC outperforms the previously proposed XOR-CD algorithm and reduced-state Viterbi algorithm by 2 dB for synchronous PNC. For both phase-asynchronous and symbol-asynchronous PNC, Jt-CNC performs better than the other two algorithms. Importantly, for real wireless network experimentation, we implemented our decoding algorithm in a PNC prototype built on the USRP software radio platform. Our experiment shows that the proposed Jt-CNC decoder works well in practice.

This study designs space-time codes in analog network coding for asynchronous two-way relay networks, where asynchronous transmissions can cause diversity loss. We propose a novel code, called zero-padded interleave reversal Alamouti code (ZP-IR AC) to achieve full diversity with fast maximum likelihood decoding. Specifically, to combat symbol misalignment caused by asynchronous transmissions, the two terminals insert zero padding when transmitting to relays. Thereafter, the second relay performs an interleave reversal procedure to retain full diversity at each terminal. A salient feature of ZP-IR AC is that it can be decoupled into several independent parts that facilitate fast maximum likelihood decoding. Simulations of ZP-IR AC show full diversity gain. The bit error rate performance of ZP-IR AC is comparable to that of the synchronized Alamouti code and outperforms those of some recent schemes.

This work investigates the broadcast channel with the knowledge of noncausal interference at the transmitter and side information at the receivers. The system studied involves one transmitter sending private information to two receivers. We first obtain an achievable rate region of this system by extending Gelfand and Pinsker's (GP's) random binning method, originally designed for point-to-point communications. We then apply the result to Gaussian scalar and vector channels, and consider the design of the auxiliary random variable used in GP's approach. Asymptotic analysis shows that the proposed scheme in both scalar and vector channels is asymptotically capacity-achieving at high signal-to-noise ratio (SNR). We further investigate the system optimization in the finite SNR regime. For the scalar channel, we derive the optimal auxiliary factor that maximizes the weighed sum-rate. For the vector channel, two kinds of suboptimal designing methods for the auxiliary matrix are proposed. Numerical results show that the proposed scheme can achieve a sum-rate close to the cut-set bound in the entire SNR regime, and significantly outperforms the schemes that do not exploit the knowledge of noncausal interference known at the transmitter.

Vehicular Ad-hoc Network (VANET) is expected to play a major role in improving road safety and traffic efficiency in people's daily life. However, the main issue in VANETs remains to be intermittent node connectivity and relatively short contact duration due to the high mobility of vehicles. Physical-layer Network Coding (PNC) that enables data exchange within a much shorter airtime (e.g., twice faster than traditional scheduling) favors the highly-dynamic link condition in vehicular environments and hence appears to be a powerful tool in VANETs. One of the most important challenges in applying PNC to VANETs comes from the Doppler shift due to high-speed vehicle motion, which leads to carrier frequency offset (CFO) and hence introduces inter-carrier interference (ICI) that degrades the bit error rate performance. In this paper, we investigate the impact of motion-induced CFO/ICI on the overall signal detection. In particular, we study whether PNC in VANETs can be made feasible with conventional equalization techniques that suppress the effect of CFO. We found that PNC suffers only a 3 dB SINR penalty in the worst case compared with generic point-to-point (P2P) communications, and generally PNC is feasible in vehicular environments even if the transmission powers of source nodes cannot be finely controlled.

We propose a low-complexity digital fountain approach for network-coded multiple access (NCMA), where each source node encodes its input packets using a fountain code. In NCMA, both physical-layer network coding and multiuser decoding are employed in the physical layer of the sink node, so that the output of the physical layer is the coupling of the fountain codes employed at the source nodes. We demonstrate that a belief propagation (BP) decoding algorithm can effectively decode the coupled fountain codes to recover the input packets of all source nodes. Our approach significantly reduces the decoding complexity compared with the previous NCMA schemes based on Reed-Solomon codes and random linear codes, and hence has the potential to increase throughput and decrease delay in computation-limited NCMA systems.

This paper investigates the decoding process of convolutional-coded physical-layer network coding (PNC) systems. Specifically, we put forth a joint channel-decoding network coding (Jt-CNC) algorithm, based on belief propagation (BP), for convolutional-coded PNC. Previously proposed XOR and channel decoding (XOR-CD) algorithm and reduced-state Viterbi algorithm are not optimal. Our Jt-CNC decoder is BER-optimal with feasible computational complexity. Simulations show that Jt-CNC outperforms XOR-CD and reduced-state Viterbi by 2dB. Furthermore, Jt-CNC is more resilient to phase offset.

There has been an increasing interest in deploying wireless mesh networks (WMNs) for communication and video surveillance purposes thanks to its low cost and ease of deployment. It is well known that a major drawback of WMN is multihop bandwidth degradation, which is primarily caused by contention and radio interference. The use of mesh nodes with multiple radios and channels has been regarded as a straightforward solution to the problem in the research community. However, we demonstrate in this paper through real-world experiments that such an approach cannot resolve the multihop TCP throughput degradation problem in IEEE 802.11n mesh networks. With extensive experimentation, we verify that the degradation is principally caused by the increase in TCP Round-Trip Time (RTT) when the number of hops increases. TCP throughput is fundamentally limited inversely by the RTT. We find that the multihop TCP throughput (up to five hops) when using 802.11n is no better than when using 802.11a, despite the much higher data rate 802.11n. We attempt to use multiple parallel TCP connections as a remedy to the problem, and it turns out that the wireless bandwidth can be fully utilized with a sufficient number of parallel streams. In general, our results give a key message that TCP tuning (e.g., setting the correct TCP buffers and use of parallel streams) is of paramount importance in high-bandwidth multihop wireless mesh networks that employ the latest wireless standards. These tuning techniques have to be implemented into commercial products to fully leverage the ever advancing wireless technologies to support the growing demand of multihop communications in wireless mesh networks.

This paper proposes and experimentally demonstrates a first wireless local area network (WLAN) system that jointly exploits physical-layer network coding (PNC) and multiuser decoding (MUD) to boost system throughput. We refer to this multiple access mode as network-coded multiple access (NCMA). Prior studies on PNC mostly focused on relay networks. NCMA is the first realized multiple access scheme that establishes the usefulness of PNC in a non-relay setting. NCMA allows multiple nodes to transmit simultaneously to the access point (AP) to boost throughput. In the non-relay setting, when two nodes A and B transmit to the AP simultaneously, the AP aims to obtain both packet A and packet B rather than their network-coded packet. An interesting question is whether network coding, specifically PNC which extracts packet A ⊕ B, can still be useful in such a setting. We provide an affirmative answer to this question with a novel two-layer decoding approach amenable to real-time implementation. Our USRP prototype indicates that NCMA can boost throughput by 100 percent in the medium-high SNR regime (≥10 dB). We believe further throughput enhancement is possible by allowing more than two users to transmit together.

Distributed space-time codes (STCs) can achieve cooperative diversity in distributed antenna systems. But the path delay difference may cause diversity loss. In this paper, a family of asynchronous STC is proposed to achieve full diversity, given that the path delay difference is within a tolerance bound. The proposed code structure allows the overall decoding process to be decomposed into several independent sub-processes, which can be tackled by low-complexity maximum-likelihood decoders. Two code designs based on the Alamouti code and the Golden code are given for a system with two distributed antennas. Moreover, two designs based on orthogonal STC and fast group decodable STC are introduced for a system with four distributed antennas, with each transmitter having two antennas. Full diversity gain is proved for all code designs and their associated decoding complexities are analyzed. Simulations of the proposed codes confirm our theoretical results on full diversity gain.

This paper addresses the problem of joint channel estimation and channel decoding in physical-layer network coding (PNC) systems. In PNC, multiple users transmit to a relay simultaneously. PNC channel decoding is different from conventional multi-user channel decoding: specifically, the PNC relay aims to decode a network-coded message rather than the individual messages of the users. Although prior work has shown that PNC can significantly improve the throughput of a relay network, the improvement is predicated on the availability of accurate channel estimates. Channel estimation in PNC, however, can be particularly challenging because of 1) the overlapped signals of multiple users; 2) the correlations among data symbols induced by channel coding; and 3) time-varying channels. We combine the expectation-maximization (EM) algorithm and belief propagation (BP) algorithm on a unified factor-graph framework to tackle these challenges. In this framework, channel estimation is performed by an EM subgraph, and channel decoding is performed by a BP subgraph that models a virtual encoder matched to the target of PNC channel decoding. Iterative message passing between these two subgraphs allow the optimal solutions for both to be approached progressively. We present extensive simulation results demonstrating the superiority of our PNC receivers over other PNC receivers.

This work investigates the maximum broadcast throughput and its achievability in multi-hop wireless networks with half-duplex node constraint. We allow the use of physical-layer network coding (PNC). Although the use of PNC for unicast has been extensively studied, there has been little prior work on PNC for broadcast. Our specific results are as follows: 1) For single-source broadcast, the theoretical throughput upper bound is n/(n+1), where n is the “min vertex-cut” size of the network. 2) In general, the throughput upper bound is not always achievable. 3) For grid and many other networks, the throughput upper bound n/(n+1) is achievable. Our work can be considered as an attempt to understand the relationship between max-flow and min-cut in half-duplex broadcast networks with cycles (there has been prior work on networks with cycles, but not half-duplex broadcast networks).

This work investigates the maximum sum-rate of multi-pair MIMO two-way relay channels (TWRCs), in which a relay is responsible for forwarding information between multiple pairs of users. In this system, each pair of users forms a TWRC, and a user exchanges information only with its counterpart in the same TWRC. We focus on the multi-access channel (MAC) phase of the two-pair TWRCs. We first put forth a new interpretation of the space-division (SD) method based on the classical concept of principal angles in linear algebra. We argue that the signal spaces of the two users in a TWRC can be divided into the physical-layer network coding (PNC) signal subspace and the complete decoding (CD) signal subspace according to the principal angles between the two signal spaces of different user pairs. Based on the principal-angle framework, we then propose an extended SD method to mitigate the interference among the PNC signals and CD signals. We further derive the optimal decoding strategy and optimal precoder design principles that maximize the sum-rate of the MAC phase. The associated optimization problem, however, is non-convex. We therefore propose a suboptimal solution for precoder design and analyze the asymptotic rate gap benchmarked against the cut-set bound. Significant performance improvements have been observed for the proposed hybrid PNC-CD system compared with pure complete decoding and pure PNC decoding.

This paper studies the overhead for channel gain monitoring in wireless networks with time division multiple access. We first investigate the scenario in which a receiver needs to track the channel gains with respect to multiple transmitters. Suppose that there are n transmitters, and no more than k channels suffer significant variations since the last round. We prove that “Θ(k log(n=k)) time slots” is the minimum overhead needed to catch up with the k varied channels. We propose a novel channel-gain monitoring scheme named ADMOT. ADMOT leverages recent advances in compressive sensing in signal processing and interference processing in wireless communication, to enable the receiver to estimate all n channels in a reliable and computationally efficient manner within O(k log(n=k)) time slots. To our best knowledge, all previous channel-tracking schemes require Θ(n) time slots regardless of k.

This paper applies the expectation-maximization (EM) algorithm to address the problem of joint channel estimation and channel decoding in Physical-layer Network Coding (PNC) systems. The use of PNC can significantly improve the throughput of a relay network. The throughput advantage, however, is predicated on the availability of accurate channel estimates. For channel-coded PNC systems, a major challenge is that the maximum a posteriori probability (MAP) channel estimation is nontrivial due to 1) the overlapping of signals from multiple users received at the relay; and 2) the correlations among data symbols introduced by channel coding. In this paper, we show that an EM algorithm implemented on a factor graph framework is well suited to tackle this problem. Through iterative message passing, the channel estimation component and the channel decoding component in the factor graph interact to improve each other's results progressively. Simulation results indicate that just one EM iteration of our algorithm can significantly improve the channel estimation accuracy as well as the BER performance of channel-coded PNC systems.

Spectrum sensing, the task of discovering spectrum usage at a given location, is a fundamental problem in dynamic spectrum access networks. While sensing in narrow spectrum bands is well studied in previous work, wideband spectrum sensing is challenging since a wideband radio is generally too expensive and power consuming for mobile devices. Sequential scan, on the other hand, can be very slow if the wide spectrum band contains many narrow channels. In this paper, we propose an analog-filter based spectrum sensing technique, which is much faster than sequential scan and much cheaper than using a wideband radio. The key insight is that, if the sum of energy on a contiguous band is low, we can conclude that all channels in this band are clear with just one measurement. Based on this insight, we design an intelligent search algorithm to minimize the number of total measurements. We prove that the algorithm has the same asymptotic complexity as compressed sensing while our design is much simpler and easily implementable in the real hardware. We show the availability of our technique using hardware devices that include analog filters and analog energy detectors. Our extensive evaluation using real TV “white space” signals shows the effectiveness of our technique.

This paper investigates the fundamental building blocks of physical-layer network coding (PNC). Since its conception, PNC has developed into a subfield of network coding investigated by many. Most of the prior work, however, focused on the simplest communication setup in which PNC could be applied, namely the two-way-relay channel (TWRC). Studies of the application of PNC in general networks are relatively few. This paper is an attempt to fill this gap. To do so, we put forth two ideas: 1) For the purpose of scheduling transmissions, a general network can be decomposed into small building blocks of PNC, referred to as the PNC atoms. 2) TWRC is only one of many possible PNC atoms - besides TWRC, we identify eight other PNC atoms. We present formal definitions for the nine PNC atoms. We then formulate the PNC scheduling problem as a linear program based on the decomposition principle stated in 1) above. Two major results of our simulation experiments are as follows. First, under the decomposition framework, the throughput performance of PNC is significantly better than those of the traditional multi-hop scheme and the non-physical-layer network coding scheme - e.g., under heavy traffic volume, PNC can achieve 100% throughput gain relative to the traditional multi-hop scheme. Second, PNC decomposition based on a variety of different PNC atoms yield much better performance than PNC decomposition based on the TWRC atom alone.

This paper addresses relay design for a wireless multiple-input-multiple-output (MIMO) switching scheme that enables data exchange among multiple users. Here, a multi-antenna relay linearly precodes the received (uplink) signals from multiple users before forwarding the signal in the downlink, where the purpose of precoding is to let each user receive its desired signal with interference from other users suppressed. The problem of optimizing the precoder based on sum-rate maximization criteria is typically non-convex and difficult to solve. The main contribution of this paper is that we show the sum-rate maximization problem can be converted to an equivalent weighted sum-MSE minimization problem and can therefore be solved using an iterative algorithm proposed in our previous work. Asymptotic analysis reveals that, with properly chosen initial values, the proposed iterative algorithms are asymptotically optimal in both high and low signal-to-noise-ratio (SNR) regimes for MIMO switching, either with or without self-interference cancellation (a.k.a., physical-layer network coding). Numerical results show that the optimized MIMO switching scheme based on the proposed algorithms significantly outperforms existing approaches in the literature.

In this paper, we consider a bidirectional cellular relay network with distributed relays where a single base station exchanges information with multiple independent users through multiple single-antenna relays. We design the transceivers at the base station, the relays, and the users. The related optimization problems are generally non-convex and difficult to solve. In this paper, we propose a unified framework to design the transceiver algorithms based on two criteria, i.e. weighted sum MSE minimization and sum rate maximization. Specifically, we show that the sum rate maximization problem can be converted into an iterative weighted sum MSE minimization problem. Low-complexity iterative algorithms are developed for both weighted sum MSE minimization and sum rate maximization optimization problems. However, the convergence points of the proposed iterative algorithms are sensitive to the initial conditions, especially in the high signal-to-noise ratio (SNR) regime. For this reason, we further derive the high-SNR asymptotically optimal solutions and use them as the initials for the proposed iterative algorithms. Simulation results show that the proposed scheme can approximately double the system throughput, compared to the conventional four-stage transmission schemes.

This paper investigates interference-cancellation schemes at the receiver, in which the interference data, which is valid data intended for another receiver, is known a priori. The interference channel, however, is unknown (the blind part). Such a priori knowledge is common in wireless relay networks. For example, a relay could be relaying data that was previously transmitted by a node A. If node A is now receiving a signal from another node B, the interference from the relay is actually self-information known to node A. Besides the case of self-information, the node could also have overheard or received the interference data in a prior transmission by another node. Directly removing the known interference requires accurate estimate of the interference channel, which may be difficult in many situations. In this paper, we propose a novel scheme, Blind Known-Interference Cancellation (BKIC), to cancel known interference without interference channel information. BKIC consists of two steps. The first step combines adjacent symbols to cancel the interference, exploiting the fact that the channel coefficients are almost the same between successive symbols. After such interference cancellation, however, the signal of interest is distorted. The second step recovers the signal of interest amidst the distortion. We propose two algorithms for the critical second steps. The first algorithm (BKIC-S) is based on the principle of smoothing. It is simple and has near optimal performance in the slow fading scenario. The second algorithm (BKIC-RBP) is based on the principle of real-valued belief propagation. Since there is no loop in the Tanner graph, BKIC-RBP can achieve MAP-optimal performance with fast convergence, and has near interference-free performance even in the fast fading scenario. Both BKIC schemes outperform the traditional self-interference cancellation schemes that have perfect initial channel information by a large margin, while having lower complexities.

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.

This paper addresses joint transceiver and relay design for a wireless multiple-input multiple-output (MIMO) switching scheme that enables data exchange among multiple users. Here, a multiantenna relay linearly precodes the received (uplink) signals from multiple users and forwards the signal in the downlink, where the purpose of precoding is to let each user receive its desired signal with interference from other users suppressed. The problem of optimizing the precoder based on various design criteria is typically nonconvex and difficult to solve. The main contribution of this paper is a unified approach to solve the weighted sum mean square error (MSE) minimization and weighted sum rate maximization problems in MIMO switching. Specifically, an iterative algorithm is proposed for jointly optimizing the relay's precoder and the users' receive filters to minimize the weighted sum MSE. It is also shown that the weighted sum rate maximization problem can be reformulated as an iterated weighted sum MSE minimization problem and can, therefore, be solved similarly to the case of weighted sum MSE minimization. With properly chosen initial values, the proposed iterative algorithms are asymptotically optimal in both high- and low-signal-to-noise-ratio regimes for MIMO switching, either with or without self-interference cancellation (a.k.a., physical-layer network coding). Numerical results show that the optimized MIMO switching scheme based on the proposed algorithms significantly outperforms existing approaches in the literature.

This paper proposes the concept of safe carrier-sensing range under the cumulative interference model that guarantees interference-safe (also known as hidden-node-free) transmissions in CSMA networks. Compared with a previous related concept of safe carrier-sensing range under the commonly assumed but less realistic pairwise interference model, we show that the safe carrier-sensing range under the cumulative interference model is larger by a constant multiplicative factor. For example, the factor is 1.4 if the SINR requirement is 10 dB and the path-loss exponent is 4 in a noiseless case. We further show that the concept of a safe carrier-sensing range, although amenable to elegant analytical results, is inherently not compatible with the conventional power-threshold carrier-sensing mechanism (e.g., that used in IEEE 802.11). Specifically, the absolute power sensed by a node in the conventional carrier-sensing mechanism does not contain enough information for the node to derive its distances from other concurrent transmitting nodes. We show that, fortunately, a new carrier-sensing mechanism called Incremental-Power Carrier-Sensing (IPCS) can realize the carrier-sensing range concept in a simple way. Instead of monitoring the absolute detected power, the IPCS mechanism monitors every increment in the detected power. This means that IPCS can separate the detected power of every concurrent transmitter, and map the power profile to the required distance information. Our extensive simulation results indicate that IPCS can boost spatial reuse and network throughput by up to 60 percent relative to the conventional carrier-sensing mechanism under the same carrier-sensing power thresholds. If we compare the maximum throughput in the interference-free regime, the throughput improvement of IPCS is still more than 15 percent. Last but not least, IPCS not only allows us to implement the safe carrier-sensing range, but also ties up a loose end in many other prior theoretical works that implicitly used a carrier-sensing range (interference-safe or otherwise) without an explicit design to realize it.

In a generic switching problem, a switching pattern consists of a one-to-one mapping from a set of inputs to a set of outputs (i.e., a permutation). We propose and investigate a wireless switching framework in which a multi-antenna relay is responsible for switching traffic among a set of N stations. We refer to such a relay as a MIMO switch. With beamforming and linear detection, the MIMO switch controls which stations are connected to which stations. Each beamforming matrix realizes a permutation pattern among the stations. We refer to the corresponding permutation matrix as a switch matrix. By scheduling a set of different switch matrices, full connectivity among the stations can be established. In this paper, we focus on “fair switching” in which equal amounts of traffic are to be delivered for all the N(N - 1) ordered pairs of stations. In particular, we investigate how the system throughput can be maximized. In general, for large N the number of possible switch matrices N! is huge, making the scheduling problem combinatorially challenging. We show that for N = 4 and 5, only a subset of N - 1 of the N! switch matrices need to be considered in the scheduling problem to achieve good throughput. We conjecture that this will be the case for large N as well. This conjecture, if valid, implies that for practical purposes, fair-switching scheduling is not an intractable problem.

This paper investigates interference-cancellation schemes at the receiver, in which the original data of the interference is known a priori. Such a priori knowledge is common in wireless relay networks. Directly removing the known interference requires accurate estimate of the interference channel, which may be difficult in many situations. In [1], we proposed a novel scheme, Blind Known Interference Cancellation (BKIC), for blind cancellation of known interference without interference channel information. BKIC consists of two steps. The first step combines adjacent symbols to cancel the interference, exploiting the fact that the channel coefficients are almost the same between successive symbols. After such interference cancellation, however, the signal of interest is also distorted. The second step recovers the signal of interest amidst the distortion. Two schemes for the second step, BKIC-S and successive BKIC-RBP, were proposed in [1]. BKIC-S removes distortion by smoothing while BKIC-RBP does so using a real-value belief propagation algorithm. Although successive BKIC-RBP performs well and is superior to BKIC-S, it requires a long processing time proportional to the packet length. To overcome this problem, this paper proposes a parallel BKIC-RBP algorithm. Parallel BKIC-RBP has similar performance as successive BKIC-RBP. It has the advantage of being amenable to parallel implementation with a much shorter processing time.

This paper presents the first implementation of a two-way relay network based on the principle of physical-layer network coding. To date, only a simplified version of physical-layer network coding (PNC), called analog network coding (ANC), has been successfully implemented. The advantage of ANC is that it is simple to implement; the disadvantage, on the other hand, is that the relay amplifies the noise along with the signal before forwarding the signal. PNC systems in which the relay performs XOR or other denoising PNC mappings of the received signal have the potential for significantly better performance. However, their implementation also poses many challenges. For example, the relay must be able to deal with symbol and carrier-phase asynchronies of the simultaneous signals received from the two end nodes, and the relay must perform channel estimation before decoding. We investigate a PNC implementation in the frequency domain, referred to as FPNC, to tackle these challenges. FPNC is based on OFDM. In FPNC, XOR mapping is performed on the OFDM samples in each subcarrier rather than on the samples in the time domain. We implement FPNC on the universal soft radio peripheral (USRP) platform. Our implementation requires only moderate modifications of the packet preamble design of 802.11a/g OFDM PHY. With the help of the cyclic prefix (CP) in OFDM, symbol asynchrony and the multi-path fading effects can be dealt with simultaneously in a similar fashion. Our experimental results show that symbol-synchronous and symbol-asynchronous FPNC have essentially the same BER performance, for both channel-coded and unchannel-coded FPNC.

Mixing time is a fundamental property for a number of transient behaviors of stochastic processes, particularly, random access in CSMA networks. We use mixing time to characterize temporal starvation, which is a transient phenomenon where links can starve for prolonged periods indefinitely often despite having good stationary throughput. Considering a general CSMA network, we study a fundamental setting with multiple frequency agility, such that more than one frequency channel is available, and a link can transmit on at most one of the frequency channels not occupied by its neighbors. The characterization of throughput in such a setting is challenging, involving a hidden Markov chain of the associated stochastic process. This paper develops new results based on the mixing time of hidden Markov chains to shed light on the temporal starvation. Our analytical results quantify the effect of the number of frequency channels on temporal starvation. We provide sufficient and necessary conditions for fast mixing time of the corresponding hidden Markov chain.

A wireless relay which forms a one-to-one mapping from the inputs (uplinks) to the outputs (downlinks) is called a multiple-input-multiple-output (MIMO) switch. The MIMO switch carries out precode-and-forward, where all users send their signals in the uplink and then the MIMO switch precodes the received vector signal for broadcasting in the downlink. Ideally, each user employs a receive filter to recover its desired signal from one other user with no or little interference from other users. We propose a joint design of the precoder and the receive filters to achieve the minimum-mean-square-error (MMSE), assuming full channel state information is available at the relay. Our results indicate that the proposed MMSE relaying scheme outperforms the existing ZF/MMSE schemes.

A wireless relay with multiple antennas is called a multiple-input-multiple-output (MIMO) switch if it maps its input links to its output links using "precode-and-forward." Namely, the MIMO switch precodes the received signal vector in the uplink using some matrix for transmission in the downlink. This paper studies the scenario of K stations and a MIMO switch, which has full channel state information. The precoder at the MIMO switch is either a zero-forcing matrix or a network-coding matrix. With the zero-forcing precoder, each destination station receives only its desired signal with enhanced noise but no interference. With the network-coding precoder, each station receives not only its desired signal and noise, but possibly also self-interference, which can be canceled. Precoder design for optimizing the received signal-to-noise ratios at the destinations is investigated. For zero-forcing relaying, the problem is solved in closed form in the two-user case, whereas in the case of more users, efficient algorithms are proposed and shown to be close to what can be achieved by extensive random search. For network-coded relaying, we present efficient iterative algorithms that can boost the throughput further.

“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.

A key issue in physical-layer network coding (PNC) is how to deal with the asynchrony between signals transmitted by multiple transmitters. That is, symbols transmitted by different transmitters could arrive at the receiver with symbol misalignment as well as relative carrier-phase offset. A second important issue is how to integrate channel coding with PNC to achieve reliable communication. This paper investigates these two issues and makes the following contributions: 1) We propose and investigate a general framework for decoding at the receiver based on belief propagation (BP). The framework can effectively deal with symbol and phase asynchronies while incorporating channel coding at the same time. 2) For unchannel-coded PNC, we show that for BPSK and QPSK modulations, our BP method can significantly reduce the asynchrony penalties compared with prior methods. 3) For QPSK unchannel-coded PNC, with a half symbol offset between the transmitters, our BP method can drastically reduce the performance penalty due to phase asynchrony, from more than 6 dB to no more than 1 dB. 4) For channel-coded PNC, with our BP method, both symbol and phase asynchronies actually improve the system performance compared with the perfectly synchronous case. Furthermore, the performance spread due to different combinations of symbol and phase offsets between the transmitters in channel-coded PNC is only around 1 dB. The implication of 3) is that if we could control the symbol arrival times at the receiver, it would be advantageous to deliberately introduce a half symbol offset in unchannel-coded PNC. The implication of 4) is that when channel coding is used, symbol and phase asynchronies are not major performance concerns in PNC.

Abstract This paper investigates the topology control problem with the goal of minimizing mutual interferences in wireless ad hoc networks. It is known that interference is considered as a relationship between link and node in previous works. In this paper, we attempt to capture the physical situation of space‐division multiplex more realistically by defining interference as a relationship between any two bidirectional links. We formulate the pair‐wise interference condition between any two bidirectional links, and demonstrate that the interference condition is equivalent by employing the equal‐power allocation strategy and by employing the minimum‐power allocation strategy. Then we further study the typical interference relationship between a link and its surrounding links. To characterize the extent of the interference between a link and its surrounding links, a new metric, the interference coefficient, is given, and its property is explored in detail by means of analysis and simulation. Based on the insight obtained, a centralized algorithm, BIMA, and a distributed algorithm, LIMA, are proposed to control the network interference. Our simulation indicates that BIMA can minimize the network interference while conserving energy and maintaining good spanner property, and LIMA has relatively good interference performance while keeping low node degree, compared with some well‐known algorithms. Besides, both BIMA and LIMA show good robustness to additive noises in terms of interference performance. Copyright © 2010 John Wiley & Sons, Ltd.

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.

A key issue in physical-layer network coding (PNC) is how to deal with the asynchrony between signals transmitted by multiple transmitters. That is, symbols transmitted by different transmitters could arrive at the receiver with symbol misalignment as well as relative carrier-phase offset. In this paper, 1) we propose and investigate a general framework based on belief propagation (BP) that can effectively deal with symbol and phase asynchronies; 2) we show that for BPSK and QPSK modulations, our BP method can significantly reduce the SNR penalty due to asynchrony compared with prior methods; 3) we find that symbol misalignment makes the system performance less sensitive and more robust against carrier-phase offset. Observation 3) has the following practical implication. It is relatively easier to control symbol timing than carrier-phase offset. Our results indicate that if we could control the symbol offset in PNC, it would actually be advantageous to deliberately introduce symbol misalignment to desensitize the system to phase offset.

Physical-layer Network Coding (PNC) can significantly improve the throughput of two-way relay channels. An interesting variant of PNC is Analog Network Coding (ANC). Almost all ANC schemes proposed to date, however, operate in a symbol by symbol manner (memoryless) and cannot exploit the redundant information in channel-coded packets to enhance performance. This paper proposes a non-memoryless ANC scheme. In particular, we design a soft-input soft-output decoder for the relay node to process the superimposed packets from the two end nodes to yield an estimated MMSE packet for forwarding back to the end nodes. Our decoder takes into account the correlation among different symbols in the packets due to channel coding, and provides significantly improved MSE performance. Our analysis shows that the SNR improvement at the relay node is lower bounded by IIR (R is the code rate) with the simplest LDPC code (repeat code). The SNR improvement is also verified by numerical simulation with LDPC code. Our results indicate that LDPC codes of different degrees are preferred in different SNR regions. Generally speaking, smaller degrees are preferred for lower SNRs.

An interesting distributed throughput-optimal CSMA MAC protocol, called adaptive CSMA, was proposed recently to schedule any strictly feasible rates inside the capacity region. Of particular interest is the fact that the adaptive CSMA can achieve a system utility arbitrarily close to that is achievable under a central scheduler. However, a specially designed transport-layer rate controller is needed for this result. An outstanding question is whether TCP Reno (one of the most mature versions of TCP) is compatible with adaptive CSMA and can achieve the same result. The answer to this question will determine how close to practical deployment adaptive CSMA is. Our answer is yes and no. First, we observe that running TCP Reno directly over adaptive CSMA results in severe starvation problems. Effectively, its performance is no better than that of TCP Reno over legacy CSMA (IEEE 802.11), and the potentials of adaptive CSMA cannot be realized. We then propose a multi connection TCP solution with active queue management and prove that it can work with adaptive CSMA to achieve optimal utility. NS-2 simulations demonstrate that our solution can alleviate starvation and achieve fair and efficient rate allocation. We remark that multi-connection TCP can be implemented at either application or transport layer. Application-layer implementation requires no kernel modification, making the solution readily deployable in networks running adaptive CSMA. Our results show that adaptive CSMA can work well with only light-weight TCP modifications, bringing it a step closer to practicaiity.

This paper investigates the problem of link scheduling to meet traffic demands with minimum airtime in a multi-transmit-receive (MTR) wireless network. MTR networks are a new class of networks, in which each node can simultaneously transmit to a number of other nodes, or simultaneously receive from a number of other nodes. The MTR capability can be enabled by the use of multiple directional antennas or multiple channels. Potentially, MTR can boost the network capacity significantly. However, link scheduling that makes full use of the MTR capability must be in place before this can happen. We show that optimal link scheduling can be formulated as a linear program (LP). However, the problem is NP-hard because we need to find all the maximal independent sets in a graph first. We propose two computationally efficient algorithms, called Heavy-Weight-First (HWF) and Max-Degree-First (MDF) to solve this problem. Simulation results show that both HWF and MDF can achieve superior performance in terms of runtime and optimality.

In the literature, asymptotic studies of multihop wireless network capacity often consider only centralized and deterministic time-division multiple-access (TDMA) coordination schemes. There have been fewer studies of the asymptotic capacity of large-scale wireless networks based on carrier-sensing multiple access (CSMA), which schedules transmissions in a distributed and random manner. With the rapid and widespread adoption of CSMA technology, a critical question is whether CSMA networks can be as scalable as TDMA networks. To answer this question and explore the capacity of CSMA networks, we first formulate the models of CSMA protocols to take into account the unique CSMA characteristics not captured by existing interference models in the literature. These CSMA models determine the feasible states, and consequently the capacity of CSMA networks. We then study the throughput efficiency of CSMA scheduling as compared to TDMA. Finally, we tune the CSMA parameters so as to maximize the throughput to the optimal order. As a result, we show that CSMA can achieve throughput as Ω([1/√(n)]), the same order as optimal centralized TDMA, on uniform random networks. Our CSMA scheme makes use of an efficient backbone-peripheral routing scheme and a careful design of dual carrier-sensing and dual channel scheme. We also address implementation issues of our CSMA scheme.

This paper studies the problem of energy conservation of mobile terminals in a multi-cell TDMA network supporting real-time sessions. The corresponding optimization problem involves joint scheduling, rate control, and power control, which is often highly complex to solve. To reduce the solution complexity, we decompose the overall problem into two sub-problems: intra-cell energy optimization and inter-cell interference control. The solution of the two subproblems results in a "win-win" situation: both the energy consumptions and inter-cell interference are reduced simultaneously. We simulate our decomposition method with the typical parameters in WiMAX system, and the simulation results show that our decomposition method can achieve an energy reduction of more than 70% compared with the simplistic maximum transmit power policy. Furthermore, the inter-cell interference power can be reduced by more than 35% compared with the maximum transmit power policy. We find that the interference power stays largely constant throughout a TDMA frame in our decomposition method. Based on this premise, we derive an interesting decoupling property: if the idle power consumption of terminals is no less than their circuit power consumption, or when both are negligible, then the energy-optimal transmission rates of the users are independent of the inter-cell interference power.

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.

In random-access networks, such as the IEEE 802.11 network, different users may transmit their packets simultaneously, resulting in packet collisions. Traditionally, the collided packets are simply discarded. To improve performance, advanced signal processing techniques can be applied to extract the individual packets from the collided signals. Prior work of ours has shown that the symbol misalignment among the collided packets can be exploited to improve the likelihood of successfully extracting the individual packets. However, the failure rate is still unacceptably high. This paper investigates how channel coding can be used to reduce the failure rate. We propose and investigate a decoding scheme that incorporates the exploitation of the aforementioned symbol misalignment into the channel decoding process. This is a fine-grained integration at the symbol level. In particular, collision resolution and channel decoding are applied in an integrated manner. Simulation results indicate that our method outperforms other schemes, including the straightforward method in which collision resolution and channel coding are applied separately.

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 paper proposes and investigates the concept of a safe carrier-sensing range that guarantees interference-safe (also termed hidden-node-free) transmissions in CSMA networks under the cumulative interference model. Compared with the safe carrier-sensing range under the commonly assumed but less realistic pairwise interference model, we show that the safe carrier-sensing range required under the cumulative interference model is larger by a constant multiplicative factor. For example, the factor is 1:4 if the SINR requirement is 10dB and the pathloss exponent is 4. We further show that the concept of a safe carrier-sensing range, although amenable to elegant analytical results, is inherently not compatible with the conventional power-threshold carrier-sensing mechanism (e.g., that used in IEEE 802.11). Specifically, the absolute power sensed by a node in the conventional mechanism does not contain enough information for it to derive its distances from other concurrent transmitter nodes. We show that, fortunately, a carrier-sensing mechanism called Incremental-Power Carrier-Sensing (IPCS) can realize the carrier-sensing range concept in a simple way. Instead of monitoring the absolute detected power, the IPCS mechanism monitors every increment in the detected power. This means that IPCS can separate the detected power of every concurrent transmitter, and map the power profile to the required distance information. Our extensive simulation results indicate that IPCS can boost spatial reuse and network throughput by more than 60% relative to the conventional carrier-sensing mechanism. Last but not least, IPCS not only allows us to implement our safe carrier-sensing range, it also ties up a loose end in many other prior theoretical works that implicitly assume the use of a carrier-sensing range (safe or otherwise) without an explicit design to realize it.

The two-phase MIMO NC (network coding) scheme can be used to boost the throughput in a two-way relay channel in which nodes are equipped with multiple antennas. The obvious strategy is for the relay node to extract the individual packets from the two end nodes and mix the two packets to form a network-coded packet. In this paper, we propose a new scheme called MIMO PNC (physical network coding), in which the relay extracts the summation and difference of the two end packets and then converts them to the network-coded form. MIMO PNC is a natural combination of the single-antenna PNC scheme and the linear MIMO detection scheme. The advantages of MIMO PNC are many. First, it removes the stringent carrier-phase requirement in single-antenna PNC. Second, it is linear in complexity with respect to the constellation size and the number of simultaneous data streams in MIMO. Simulation shows that MIMO PNC outperforms the straightforward MIMO NC significantly under random Rayleigh fading channel. Based on our analysis, we further conjecture that MIMO PNC outperforms MIMO NC under all possible realizations of the channel.

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.

With the rapid proliferation of broadband wireless services, it is of paramount importance to understand how fast data can be sent through a wireless local area network (WLAN). Thanks to a large body of research following the seminal work of Bianchi, WLAN throughput under saturated traffic condition has been well understood. By contrast, prior investigations on throughput performance under unsaturated traffic condition was largely based on phenomenological observations, which lead to a common misconception that WLAN can support a traffic load as high as saturation throughput, if not higher, under nonsaturation condition. In this paper, we show through rigorous analysis that this misconception may result in unacceptable quality of service: mean packet delay and delay jitter may approach infinity even when the traffic load is far below the saturation throughput. Hence, saturation throughput is not a sound measure of WLAN capacity under nonsaturation condition. To bridge the gap, we define safe-bounded-mean-delay (SBMD) throughput and safe-bounded-delay-jitter (SBDJ) throughput that reflect the actual network capacity users can enjoy when they require finite mean delay and delay jitter, respectively. Our earlier work proved that in a WLAN with multi-packet reception (MPR) capability, saturation throughput scales superlinearly with the MPR capability of the network. This paper extends the investigation to the nonsaturation case and shows that superlinear scaling also holds for SBMD and SBDJ throughputs. Our results here complete the demonstration of MPR as a powerful capacity-enhancement technique for WLAN under both saturation and nonsaturation conditions.

This paper studies the problem of finding a minimum-length schedule of a power-controlled wireless network subject to traffic demands and SINR (signal-to-interference-plus-noise ratio) constraints. We propose a column generation based algorithm that finds the optimal schedules and transmit powers. The column generation method decomposes a complex linear optimization problem into a restricted master problem and a pricing problem. We develop a new formulation of the pricing problem using the Perron-Frobenius eigenvalue condition, which enables us to integrate link scheduling with power control in a single framework. This new formulation reduces the complexity of the pricing problem, and thus improves the overall efficiency of the column generation method significantly - for example, the average runtime is reduced by 99.86% in 18-link networks compared with the traditional column generation method. Furthermore, we propose a branch-and-price method that combines column generation with the branch-and-bound technique to tackle the integer constraints on time slot allocation. We develop a new branching rule in the branch-and-price method that maintains the size of the pricing problem after each branching. Our branch-and-price method can obtain optimal integer solutions efficiently for example, the average runtime is reduced by 99.72% in 18-link networks compared with the traditional branch-and-price method. We further suggest efficient heuristic algorithms based on the structure of the optimal algorithms. Simulation results show that the heuristic algorithms can reach solutions within 10% of optimality for networks with less than 30 links.

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.

With the proliferation of wireless multimedia applications, multicast/broadcast has been recognized as an efficient technique to transmit a large volume of data to multiple mobile stations at the same time. In most multicast systems, the transmitter (e.g. base station) adapts its data rate to the furthest located users, so as to guarantee service quality to as many users as possible. Predictably, the more users in a multicast group, the lower data rate the base station can transmit. On the other hand, grouping more users together leads to a more efficient utilization of spectrum bandwidth, as these users are served simultaneously. This bring the interesting problem that presses for solution: how to group users in a cell into multicast groups and how to allocate a fixed amount of bandwidth resource to the groups, to achieve a good balance between throughput and fairness in multicast systems. In this paper, we formulate the united user grouping and bandwidth allocation strategy into a utility-based optimization problem. One method of signomial programming is used to solve the non-convex optimization problem. Numerical results will show that this suboptimal algorithm performs well even compared to the optimal one. Moreover, through theoretical analysis, we prove that the best user grouping and bandwidth allocation scheme of throughput maximization is to allocate the entire bandwidth to the unique group containing the users located within a ring-shaped region with an optimal outer radius r*.

We study the joint power control and minimum-frame-length scheduling problem in wireless networks, under the physical interference model and subject to consecutive transmission constraints. We start by investigating the complexity of the problem and present the first NP-completeness proof in the literature. We propose a polynomial-time approximation algorithm, called guaranteed and greedy scheduling (GGS) algorithm, to tackle this problem. We prove a bounded approximation ratio of the proposed algorithm relative to the optimal scheduling algorithm. Moreover, the proposed algorithm significantly outperforms the state-of-the-art related algorithm. Interestingly, our algorithm together with its bounded approximation ratio is applicable even when the consecutive transmission constraint is relaxed. To the best of our knowledge, the proposed algorithm is the first known polynomial-time algorithm with a proven bounded approximation ratio for the joint power control and scheduling problem under the physical interference model. We further demonstrate the performance and advantages of our algorithm through extensive simulations.

Most prior studies on wireless spatial-reuse TDMA (STDMA) link scheduling for throughput optimization deal with the situation where instantaneous channel state information (CSI) is available. Under fast fading, however, the channel may change too quickly for the scheduler to track the instantaneous CSI. In this paper, instead of the instantaneous CSI, the scheduler performs its task according to the stochastic behavior of the channel state. A basic schedule consists of a set of simultaneously transmitting links. The essence of the scheduling problem is to determine a mixed schedule consisting of a weighted sum (TDMA mixture) of a number of basic schedules to optimize a certain utility objective. A key to reducing scheduling complexity is to identify the Pareto-efflcient basic schedules, referred to as the extreme-point schedules, so that the construction of the optimal mixed schedule can be based on the extreme-point schedules rather than all the basic schedules. The precise identification of the extreme-point schedules, however, is intractable computationally. We show in this paper that identifying a slightly larger superset of the extreme-point schedules can be highly efficient using a Perron-Frobenius condition: simulation experiments indicate that oftentimes there are only very few extraneous non-extreme-point schedules in the superset. Building on the effective identification method, we propose a fast scheduling algorithm. This algorithm beats the algorithm without using the identification method by a complexity-reduction factor of 166 in a 15-link network. In addition, numerical results suggest that our algorithm is robust to variations of system parameters.

It is known that interference is considered as a relationship between link and node in previous works. In this paper, we attempt to capture the physical situation of space-division multiplex more realistically by defining interference as a relationship between any two undirected links. Here a new metric, the average partial interference coefficients, is given. Then we find that the coefficients are almost independent with node density and can be approximated by different linear functions of the length of link respectively. Based on the insight obtained, a new topology control algorithm, the blocked interference minimum algorithm (BIMA), is proposed to control the network interference. Our simulation indicates that the network topologies produced by BIMA show good performance in terms of network interference, energy cost and node degree.

In the literature, asymptotic studies of multi-hop wireless network capacity often consider only centralized and deterministic TDMA (time-division multi-access) coordination schemes. There have been fewer studies of the asymptotic capacity of large-scale wireless networks based on CSMA (carrier-sensing multi-access), which schedules transmissions in a distributed and random manner. With the rapid and widespread adoption of CSMA technology, a critical question is that whether CSMA networks can be as scalable as TDMA networks. To answer this question and explore the capacity of CSMA networks, we first formulate the models of CSMA protocols to take into account the unique CSMA characteristics, not captured by existing interference models in the literature. These CSMA models determine the feasible states, and consequently the capacity of CSMA networks. %and are functions of various CSMA parameters. We then study the throughput efficiency of CSMA scheduling as compared to TDMA. Finally, we tune the CSMA parameters so as to maximize the throughput to the optimal order. As a result, we show that CSMA can achieve throughput as Ω(1/√n), the same order as optimal centralized TDMA, on uniform random networks. Our CSMA scheme makes use of an efficient backbone-peripheral routing scheme and a careful design of dual carrier-sensing and dual channel scheme. We also address practical implementation issues of our capacity-optimal CSMA scheme.

This study attempts to exploit the potential of link directionality to increase the achievable capacities of ad hoc networks. When an IEEE 802.11 ad hoc network achieves capacity C by using a single channel, the targeted capacity by using two channels should be 2C. However, most of the dual-channel 802.11 protocols proposed in the literature appear only to be able to achieve less than 60% of the 2C targeted capacity. The authors thus propose a link-directionality-based dual-channel medium access control protocol in an attempt to double the capacities of networks using the single-channel IEEE 802.11 protocol. The main idea is to assign channels according to link directionality to allow a link to transmit simultaneously within the carrier-sensing region of another link provided that these transmissions do not interfere with each other. Simulations show that our proposed scheme can achieve more than 85% of our targeted capacities, 0.85×2C=1.7C, in large-scale random topologies. In lattice and irregular topologies, the throughput is boosted up to 2.83C and 2.13C, respectively. An approach for capacity analysis is also introduced to determine the throughput improvements that can be achieved by our proposed protocol. We believe using link directionality for channel allocations is a key step that yields significant potential for multiplying the capacity of ad hoc networks.

This paper investigates link-by-link channel-coded PNC (physical layer network coding), in which a critical process at the relay is to transform the superimposed channel-coded packets received from the two end nodes (plus noise), Y3= X1+ X2+W3, to the network-coded combination of the source packets, S1oplus S2. This is in contrast to the traditional multiple-access problem, in which the goal is to obtain both S1and S2explicitly at the relay node. Trying to obtain S1and S2explicitly is an overkill if we are only interested in S1oplusS2. In this paper, we refer to the transformation Y3rarr S1oplus S2as the channel-decoding- network-coding process (CNC) in that it involves both channel decoding and network coding operations. This paper shows that if we adopt the repeat accumulate (RA) channel code at the two end nodes, then there is a compatible decoder at the relay that can perform the transformation Y3rarr S1oplusS2efficiently. Specifically, we redesign the belief propagation decoding algorithm of the RA code for traditional point-to-point channel to suit the need of the PNC multiple-access channel. Simulation results show that our new scheme outperforms the previously proposed schemes significantly in terms of BER without added complexity.

IEEE 802.11 WLAN has high data rates (e.g., 11 Mbps for 802.11b and 54 Mbps for 802.11g), while voice streams of VoIP typically have low-data-rate requirements (e.g., 29.2 Kbps). One may, therefore, expect WLAN to be able to support a large number of VoIP sessions (e.g., 200 and 900 sessions in 802.11b and 802.11g, respectively). Prior work by one of the authors, however, indicated that 802.11 is extremely inefficient for VoIP transport. Only 12 and 60 VoIP sessions can be supported in an 802.11b and an 802.11g WLAN, respectively. This paper shows that the bad news does not stop there. When there are multiple WLANs in the vicinity of each other-a common situation these days-the already low VoIP capacity can be further eroded in a significant manner. For example, in a 5 times 5, 25-cell multi-WLAN network, the VoIP capacities for 802.11b and 802.11g are only 1.63 and 10.34 sessions per AP, respectively. This paper investigates several solutions to improve the VoIP capacity. Based on a conflict graph model, we propose a clique-analytical call admission scheme, which increases the VoIP capacity by 52 percent from 1.63 to 2.48 sessions per AP in 802.11b. For 11g, the call admission scheme can also increase the capacity by 37 percent from 10.34 to 14.14 sessions per AP. If all the three orthogonal frequency channels available in 11b and 11g are used to reduce interferences among adjacent WLANs, clique-analytical call admission scheme can boost the capacity to 7.39 VoIP sessions per AP in 11b and 44.91 sessions per AP in 11g. Last but not least, this paper expounds for the first time the use of coarse-grained time-division multiple access (CoTDMA) in conjunction with the basic 802.11 CSMA to eliminate the performance-degrading exposed-node and hidden-node problems in 802.11. A two-layer coloring problem (which is distinct from the classical graph coloring problem) is formulated to assign coarse time slots and frequency channels to VoIP sessions, taking into account the intricacies of the carrier-sensing operation of 802.11. We find that CoTDMA can further increase the VoIP capacity in the multi-WLAN scenario by an additional 35 percent, so that 10 and 58 sessions per AP can be supported in 802.11b and 802.11g, respectively.

This paper investigates the many-to-one throughput capacity (and by symmetry, one-to-many throughput capacity) of IEEE 802.11 multihop networks, in which many sources send data to a sink. An example of a practical scenario is that of a multihop mesh network connecting source and relay nodes to an Internet gateway. In the trivial case where all source nodes are just one hop from the sink, the system throughput can approach Ls, where Lsis the throughput capacity of an isolated link consisting of just one transmitter and one receiver. In the nontrivial case where some source nodes are more than one hop away, one can still achieve a system throughput of Lsby sacrificing and starving the non-one-hop source nodes-however, this degenerates to an unacceptable trivial solution. We could approach the problem by the following partitioning: preallocate some link capacity aLs(0 les a les 1) at the sink to the one-hop source nodes and then determine the throughput for the source nodes that are two or more hops away based on the remaining capacity L = (1 - a)Ls. The throughput of the one-hop nodes will be around aLs. This paper investigates the extent to which the remaining capacity L can be used efficiently by the source traffic that is two or more hops away. We find that for such source traffic, a throughput of L is not achievable under 802.11. We introduce the notion of "canonical networks,rdquo a general class of regularly structured networks that allow us to investigate the system throughput by varying the distances between nodes and other operating parameters. When all links have equal length, we show that 2L/3 is the upper bound for general networks, including random topologies and canonical networks. When the links are allowed to have different lengths, we show that the throughput capacity of canonical networks has an analytical upper bound of 3L/4. The tightness of the bound is confirmed by simulations of 802.11 canonical networks, in which we obtain simulated throughputs of 0.74L when the source nodes are two hops away and 0.69L when the source nodes are many hops away. We conjecture that 3L/4 is also the upper bound for general networks. Our simulations show that 802.11 networks with random topologies operated with AODV routing typically achieve throughputs far below 3L/4. Fortunately, by properly selecting routes near the gateway (or by properly positioning the relay nodes leading to the gateway) to fashion after the structure of canonical networks, the throughput can be improved by more than 150 percent: indeed, in a dense network, deactivating some of the relay nodes near the sink can lead to a higher throughput.

Due to its simplicity and cost efficiency, wireless local area network (WLAN) enjoys unique advantages in providing high-speed and low-cost wireless services in hot spots and indoor environments. Traditional WLAN medium-access-control (MAC) protocols assume that only one station can transmit at a time: simultaneous transmissions of more than one station cause the destruction of all packets involved. By exploiting recent advances in PHY-layer multiuser detection (MUD) techniques, it is possible for a receiver to receive multiple packets simultaneously. This paper argues that such multipacket reception (MPR) capability can greatly enhance the capacity of future WLANs. In addition, the paper provides the MAC-layer and PHY-layer designs needed to achieve the improved capacity. First, to demonstrate MPR as a powerful capacity-enhancement technique, we prove a "superlinearity” result, which states that the system throughput per unit cost increases as the MPR capability increases. Second, we show that the commonly deployed binary exponential backoff (BEB) algorithm in today's WLAN MAC may not be optimal in an MPR system, and the optimal backoff factor increases with the MPR capability, the number of packets that can be received simultaneously. Third, based on the above insights, we design a joint MAC-PHY layer protocol for an IEEE 802.11-like WLAN that incorporates advanced PHY-layer signal processing techniques to implement MPR.

This paper provides a queueing analysis for the slotted Aloha network. We assume the use of an exponential backoff protocol. Most prior work on slotted Aloha focuses on the analysis of its saturation throughput. Good saturation throughput, however, does not automatically translate to good delay performance for the end users. For example, it is well-known that the maximum possible throughput of slotted Aloha with a large number of nodes is e-1=0.3679 . Prior work showed that binary backoff factor of r = 2 can achieve a saturation throughput of 0.3466, which is very close to the e-1. However, this paper shows that if mean queuing delay is to be bounded, then the offered load must be below 0.2158, a drastic 41% drop from e-1. Fortunately, setting r= 1.3757 allows us to achieve bounded-mean-delay throughput of 0.3545, less than 4% lower than e-1. A general conclusion is that the backoff factor r may significantly affect the queuing delay performance. Our analysis provides a framework to set system parameters properly.

With the proliferation of wireless multimedia applications, multicast/broadcast has been recognized as an efficient technique to transmit a large volume of data to multiple mobile stations at the same time. In most multicast systems, the transmitter (e.g., base station) adapts its data rate to the worst channel among all users in the multicast group, so as to guarantee service quality to each user. Predictably, the more users in a multicast group, the lower data rate the base station can transmit. On the other hand, grouping more users together leads to a more efficient utilization of spectrum bandwidth, as these users are served simultaneously. A natural question that arises is how to group users to maximize the throughput of multicast systems, given a fixed amount of bandwidth resource. In this paper, we attempt to answer this important question that has not been addressed before. Through theoretical analysis, we prove that (1) the average throughput increases with the number of users in a multicast group, when the number of subcarriers allocated to a group is proportional to the number of users therein. Moreover, the throughput approaches infinite-bandwidth Gaussian channel capacity when the number of users gets large; (2) the number of users, and hence the number of subcarriers, that is needed for throughput to be arbitrarily close to its asymptotic value increases almost linearly with the transmit SNR. Our analysis is validated through simulations.

To date, most analysis of WLANs has been focused on their operation under saturation condition. This work is an attempt to understand the fundamental performance of WLANs under unsaturated condition. In particular, we are interested in the delay performance when collisions of packets are resolved by an exponential backoff mechanism. Using a multiple-vacation queueing model, we derive an explicit expression for packet delay distribution. It is found that under some circumstances, mean delay and delay jitter may approach infinity even when the traffic load is way below the saturation throughput. Saturation throughput is therefore not a sound measure of WLAN capacity when the underlying applications are delay sensitive. To bridge the gap, we define safe-bounded-mean-delay (SBMD) throughput and safe-bounded-delay-jitter (SBDJ) throughput that reflect the actual network capacity users can enjoy when they require bounded mean delay and delay jitter, respectively. The analytical model in this paper is general enough to cover both single-packet reception (SPR) and multi-packet reception (MPR) WLANs, as well as carrier-sensing and non-carrier- sensing networks. We show that the SBMD and SBDJ throughputs scale super-linearly with the MPR capability of a network. Together with our earlier work that proves super-linear throughput scaling under saturation condition, our results here complete the demonstration of MPR as a powerful capacity-enhancement technique for both delay-sensitive and delay-tolerant applications.

Direct application of network coding at the physical layer - physical layer network coding (PNC) - is a promising technique for two-way relay wireless networks. In a two-way relay network, relay nodes are used to relay two-way information flows between pairs of end nodes. This paper proposes a precise definition for PNC. Specifically, in PNC, a relay node does not decode the source information from the two ends separately, but rather directly maps the combined signals received simultaneously to a signal to be relayed. Based on this definition, PNC can be further sub-classed into two categories - PNCF (PNC over finite field) and PNCI (PNC over infinite field) - according to whether the network-code field (or groups, rings) adopted is finite or infinite. For each of PNCF and PNCI, we consider two specific estimation techniques for dealing with noise in the mapping process. The performance of the four schemes is investigated by means of analysis and simulation, assuming symbol-level time synchronization only.

This paper investigates minimizing mutual interferences in wireless ad hoc networks by means of topology control. Prior work defines interference as a relationship between link and node. This paper attempts to capture the physical situation more realistically by defining interference as a relationship between link and link. We formulate the pair-wise interference condition between two links, and show that the interference conditions for the minimum-transmit-power strategy and the equal-transmit-power strategy are equivalent. Based on the pair-wise definition, we further investigate the "typical" interference relationship between a link and all other links in its surrounding. To characterize the extent of the interference between a link and its surrounding links, we define a new metric called the interference coefficient. We investigate the property of interference coefficient in detail by means of analysis and simulation. Based on the insight obtained, we propose a topology control algorithm - minimum interference algorithm (MIA) - to minimize the overall network interference. Simulation results indicate that the network topologies produced by MIA show good performance in terms of network interference and spanner property compared with known algorithms such as LIFE, Gabriel Graph and k-NEIGH.

This paper concerns the problem of finding the minimum-length TDMA frame of a power-controlled wireless network subject to traffic demands and SINR (signal- to-interference-plus-noise ratio) constraints. We formulate the general joint link scheduling and power control problem as an integer linear programming (ILP) problem. The linear relaxation of the ILP problem has been claimed to be NP-hard in the literature. We present a computationally efficient heuristic algorithm, called the increasing demand greedy scheduling (IDGS) algorithm, to solve the general ILP problem. In addition, we propose using a column generation (CG) method as an augmentation to IDGS to further improve its performance. Simulation results show that integration of IDGS and CG can achieve superior performance in terms of both algorithm run time and solution optimality.

Two well-known problems that can cause performance degradations in IEEE 802.11 wireless networks are the exposed-node (EN) and hidden-node (HN) problems. Although there have been isolated and incidental studies of EN and HN, a comprehensive treatment has not been attempted. The contributions of this paper are threefold: First, we provide rigorous mathematical definitions for EN and HN in wireless networks (including wireless local area networks (WLANs) with multiple access points (APs) and ad hoc networks). Second, we relate EN to the nonscalability of network throughput and HN to unfair throughput distributions. Third, we provide schemes to eliminate EN and HN, respectively. We show that the standard 802.11 technology is not scalable because, due to EN, more APs do not yield higher total throughput. By removing EN, our schemes make it possible to achieve scalable throughput commensurate with the seminal theoretical results in [1] and [2]. In addition, by removing HN, our schemes solve the performance problems triggered by HN, including throughput unfairness/starvation and rerouting instability.

This is Part I of a two-part paper series that studies the use of the proportional fairness (PF) utility function as the basis for resource allocation and scheduling in multichannel multi-rate wireless networks. The contributions of Part I are threefold. (i) We present the fundamental properties and physical/economic interpretation of PF optimality. We show that PF leads to equal airtime allocation to users for the singlechannel case; and equal equivalent airtime allocation to users for the multi-channel case. In addition, we also establish the Pareto efficiency of joint-channel PF optimal solution (the formulation of interest to us in this paper), and its superiority over the individual-channel PF optimal solution in that the individual user throughputs of the former are all equal to or greater than the corresponding user throughputs of the latter. (ii) Second, we derive characteristics of joint-channel PF optimal solutions useful for the construction of PF-optimization algorithms. In particular, we show that a PF solution typically consists of many zero airtime assignments when the difference between the number of users U and the number of channels S, |U - S|, is large. We present several PF-optimization algorithms, including a fast algorithm that is amenable to parallel implementation. (iii) Third, we study the use of PF utility for resource allocation in large-scale WiFi networks consisting of many adjacent wireless LANs. We find that the PF solution simultaneously achieves higher system throughput, better fairness, and lower outage probability with respect to the default solution given by today's 802.11 commercial products. Part II of this paper series extends our investigation to the time-varying-channel case in which the data rates enjoyed by users over the channels vary dynamically over time.

This is Part II of a two-part paper series that studies the use of the proportional fairness (PF) utility function as the basis for resource allocation and scheduling in multichannel multi-rate wireless networks. The contributions of Part II are twofold. (i) First, we extend the problem formulation, theoretical results, and algorithms to the case of time-varying channels, where opportunistic resource allocation and scheduling can be exploited to improve system performance. We lay down the theoretical foundation for optimization that "couples" the time-varying characteristic of channels with the requirements of the underlying applications into one consideration. In particular, the extent to which opportunistic optimization is possible is not just a function of how fast the channel characteristics vary, but also a function of the elasticity of the underlying applications for delayed resource allocation. (ii) Second, building upon our theoretical framework and results, we study subcarrier allocation and scheduling in orthogonal frequency division multiplexing (OFDM) cellular wireless networks. We introduce the concept of a W-normalized Doppler frequency to capture the extent to which opportunistic scheduling can be exploited to achieve throughput-fairness performance gain. We show that a "lookback PF" scheduling can strike a good balance between system throughput and fairness while taking the underlying application requirements into account.

In this paper, we clarify inter-link interference in wireless ad-hoc networks by using link-directional interference graphs (I-graph). Most of the interference graphs in the literature simply model the DATA and ACK traffic of a link by a single vertex. They fail to capture the link-directionalities. In fact, some instances of directional traffic can actually transmit simultaneously but are prohibited by the interference graphs. Thus, in our link-directional interference graph, a link is represented by two vertices, one for DATA traffic and the other for ACK traffic. We then apply a colouring algorithm in the I-graphs. The colouring results provide insights in order to boost network capacities in TDMA or FDMA ad-hoc networks. We show that the network capacities can be improved by 100% in a triangular topology and 33% in a lattice topology. Simulations also show that a distributed dual channel protocol assigning channels according to link-directionalities can boost the capacities by 70% in large-scale random networks. We believe this is a first paper in the literature to take into account link-directionalities in interference graphs.

It is well known that IEEE 802.11 WLAN is highly inefficient for transporting voice data. For example, if one simply takes the data rate of 802.11 b, 11 Mbps, and divide it by two times 13.2 Kbps (the bit rate of a typical voice stream in one direction), one comes to the conclusion that more than 400 voice sessions can be supported in an 802.11 b WLAN. As shown in previous work, it turns out that at most 12 sessions can be supported due to various header and protocol overheads inherent in 802.11. This paper points out that the "bad news" does not stop there, and that in practice the number of supportable voice sessions could be lower than 2 sessions per access point (AP)! This is so because as 802.11 WLAN gains popularity, it is common to have many WLANs being deployed in the same geographical area, and these WLANs share the common air medium. Our ns2 simulation experiments, for example, show that the capacity of a 5-by-5, 25-cell IEEE 802.11b WLAN, laid out in a square grid manner, is only 1.6 sessions per AP. The second contribution of this paper is the investigation of techniques to improve the dismal capacity. We show that a systematic call admission mechanism based on clique analysis of a conflict graph can increase the capacity to 2.12 sessions per AP. Adding a "restart mode" to the 802.11 protocol boosts the capacity further to 2.72 sessions per AP. We also briefly discuss the impact of higher data rates (e.g., 54 Mbps in 802.tig and 802.11 a), and careful assignment of available frequency channels (e.g., the three and twelve orthogonal frequency channels in 802.11 b/g and 802.11 a, respectively), on capacity. Although all the above techniques can improve the capacity somewhat, the huge penalty relative to the potential remains. Boosting the voice capacity over multiple WLANs is therefore an area that deserves further attention from the research community.

MIMO (multiple input multiple output) is capable of offering several-fold increase in spectral efficiency over single-antenna systems through spatial processing. However, current IEEE 802.11 legacy MAC is designed without taking into consideration the interference cancellation capability of MIMO, thereby resulting in suboptimal use of bandwidth spectrum. In this paper, to fully exploit the spatial dimension of freedom offered by MIMO, we propose a methodology that takes into account the spatial correlation between the signal and interference in the design of MIMO ad hoc networks. Through analysis of the effect of spatial correlations on the system throughput, we conclude that it is a crucial factor that cannot be ignored when optimizing the transmission of the networks. Against this backdrop, we propose and investigate a specific MAC protocol for the transmission in a MIMO ad hoc network which 1) allows links to contend for the channel sequentially and transmit data packets simultaneously, yielding more than 35% throughput improvement compared to the system wherein only one link transmits at a time; 2) closely follows the 802.11 DCF (distributed coordination function), allowing simpler implementation as compared to previously proposed MAC protocols.

Multi-carrier code division multiple access (MC-CDMA) was proposed to improve capacities of wireless networks. Instead of increasing the data transmission rates of wireless links, the authors propose to assign independent data streams obtained by MC-CDMA for transmitting uplink and downlink traffic separately in order to eliminate the hidden-node and exposed-node problems between cochannel BSSs in WLANs. Simulations show that our scheme can improve network throughputs by 106% in an exposed-node scenario and by 113% in a hidden-node scenario. The authors also consider the hardware and MAC requirements of our scheme under different settings of physical carrier sensing range. The authors believe this is a first paper in the literature to assign MC-CDMA generated data streams in WLANs so as to mitigate the hidden-node and exposed-node problems.

Network coding has been receiving much attention recently for its ability to improve network throughput and enhance network robustness. In this paper, we investigate the design of network coding in wireless networks and propose a combined low complexity network coding and channel decoding scheme. We analyze the capacity of the proposed scheme for both the binary symmetric channel (BSC) and AWGN channel and show that it can achieve almost the same channel capacity as traditional network coding with a small degradation in the system bit error rate (BER) performance while achieving almost 50% complexity reduction. It is also shown that the proposed network coding design can be applied in wireless cooperative networks.

Optimizing spectral reuse is a major issue in large-scale IEEE 802.11 wireless networks. Power control is an effective means for doing so. Much previous work simply assumes that each transmitter should use the minimum transmit power needed to reach its receiver, and that this would maximize the network capacity by increasing spectral reuse. It turns out that this is not necessarily the case, primarily because of hidden nodes. This paper shows that in a network with power control, avoiding hidden nodes can achieve higher overall network capacity compared with the minimum-transmit-power approach. It is not always best to use the minimum transmit powers even from the network capacity viewpoint. Specifically, we propose and investigate two distributed adaptive power control algorithms that minimize mutual interferences among links while avoiding hidden nodes. Different power control schemes have different numbers of exposed nodes and hidden nodes, which in turn result in different network capacities and fairness. Although there is usually a fundamental tradeoff between network capacity and fairness, we show that, interestingly, this is not always the case. In addition, our power control algorithms can operate at desirable network- capacity-fairness tradeoff points, and can boost the capacity of ordinary non-power-controlled 802.11 networks by two times while eliminating hidden nodes.

This paper studies the use of the proportional fairness (PF) utility function as the basis for capacity allocation and scheduling in multi-channel multi-rate wireless networks. Examples of applications include (i) access point (AP) association and transmission scheduling in large-scale IEEE 802.11 networks; and (ii) subcarrier assignment and transmission scheduling in orthogonal frequency division multiplexing (OFDM) cellular networks. The contributions of this paper are twofold. First, we study the fundamental properties and physical/economic interpretation of PF. We show by general mathematical arguments that PF leads to equal airtime allocation to individual users for the single-channel case; and equal equivalent airtime allocation to individual users for the multi-channel case, where the equivalent airtime enjoyed by a user is a weighted sum of the airtimes enjoyed by the user on all channels, with the weight of a channel being the price or value of that channel. In addition, we establish the Pareto efficiency of PF solutions and derive characteristics of PF solutions that are useful for the construction of PF algorithms. Second, we generate numerical results for application (i) above. We find that the PF solution simultaneously achieves higher system throughput, better fairness, and lower outage probability with respect to the default AP-association and medium access control (MAC) protocol adopted in today's 802.11 commercial products.

In this paper, we propose a link-directionality-based dual channel MAC protocol in an attempt to double the capacities of networks using the single-channel IEEE 802.11 protocol. When an IEEE 802.11 ad-hoc network achieves capacity C by using a single channel, the targeted capacity by using two channels should be 2 - C. However, most of the multichannel 802.11 protocols proposed in the literature only appear to be able to achieve less than 60% of the 2 ldr C targeted capacity. Simulations show that our proposed scheme can achieve more than 106% of our targeted capacities, 1.06*2 ldr C = 2.12 ldr C. We believe this is a first paper in the literature to propose a MAC protocol to transmit RTS/DATA and CTS/ACK of a link on different channels, a key step that yields significant potential formultiplyingthe network capacities of ad-hoc networks.

Data-collection is an important application of sensor networks. This paper considers the scenario in which data generated from all sensors are to be forwarded to a single "data center" for processing. Although there have been many studies on this many-to-one communication scenario, it has generally been assumed that the data-collection capacity is upper-bounded by the link capacity L. We show that when the IEEE 802.11 protocol is used, the data-collection capacity has a tighter analytical upper-bound of 3L/4, and simulated throughput of 0.601L. In deriving our results, we introduce the notion of "canonical networks", which is a class of regularly-structured networks whose capacities can be analyzed more easily than unstructured networks. We argue that the capacities of canonical networks serve as a good benchmark for general networks in that the maximum possible capacity of any given network is unlikely to exceed the upper-bound capacity established for canonical networks.

The conventional MAC (Medium Access Control) protocols assume that only one packet can be received at a given time. However, with the advent of sophisticated signal processing and antenna array techniques, it is possible to achieve multipacket reception (MPR) in the physical layer (PHY). In this paper, we propose a PHY methodology and the corresponding MAC protocol for MPR in wireless local area networks (WLANs). The proposed MAC protocol closely follows the 802.11 DCF (Distributed Coordination Function) scheme and enables MPR in a distributed manner. For the proposed MPR system, a closed-form expression of the average throughput is derived. Based on the expression, an optimal transmission probability that maximizes the throughput can be attained. In addition, two enhancement schemes are presented to further improve the performance of the MPR protocol. Numerical results show that the proposed MPR system can considerably increase the spectrum efficiency compared to the WLANs with conventional collision models.

In this paper, we propose a link-directionality-based dual channel MAC protocol in an attempt to double the capacities of networks using the single-channel 802.11 protocol. Simulations show that the proposed scheme can achieve more than 78% of our targeted capacities. We believe this is a first paper in the literature to propose a MAC protocol to transmit RTS/DATA and CTS/ACK of a link in different channels. This yields a large potential for multiplying the network capacities of ad-hoc networks by using only two channels.

This paper examines how various carrier-sensing schemes affect the exposed-node (EN) and hidden-node (HN) phenomena. In the process, we identify a new carrier-sensing mechanism for alleviating EN and HN that is more effective than previously proposed schemes. This scheme, referred to as the MP scheme, uses MAC-address-based Physical carrier sensing to determine if the medium is busy. In MP, the addresses of transmitter and receiver of a packet are incorporated into the PHY header. Making use of this address information for its carrier-sensing operation, a node can drastically reduce the detrimental effects of EN and HN. In ns2 simulations, MP yields superior throughput and fairness performance that exceed our original expectation. Specifically, we find that the total network throughput achieved by MP is more than twice that of the 802.11b basic-access mode, and more than four times that of the 802.11b RTS/CTS mode, under various node-density and packet-size assumptions. At the same time, the Jains fairness index of MP is almost twice that of the 802.11b basic-access and RTS/CTS modes. We believe this is a first paper to propose and investigate the merit of cross-layer carrier sensing that jointly makes use of the attributes of the physical and MAC layers in its operation

A collision resolution scheme is essential to the performance of a random-access wireless network. Most schemes employ exponential backoff (EB) to adjust the transmission attempt rate according to the changing traffic intensity. Previous work on exponential backoff was mostly based on the conventional single-packet-reception model where no more than one packet can be successfully received at any one time. In this paper, we analyze the performance of EB based on a multi-packet reception (MPR) model, in which multiple packets can be received successfully at once (i.e., collisions do not occur unless the number of packets transmitted exceeds a threshold that is more than 1). Using a Markov chain model, we derive the throughput expressions for both carrier-sensing and non-carrier-sensing networks with MPR capability under the saturated-traffic condition. We find that the two systems share a number of common performance results. In particular, the state of both systems can be characterized by the same Markov-chain model. The binary exponential backoff (BEB), in which the backoff factor r is set to 2, does not yield the optimum network throughput in both cases. In addition, in both cases, the asymptotic collision probability goes to 1/r and the maximum asymptotic throughput increases roughly linearly with M when the population size approaches infinity. We show how to adjust r to achieve the best throughput performance. Our results show that the optimal r that maximizes the asymptotic throughput increases with M for non-carrier-sensing systems and BEB is close to optimal for carrier-sensing systems. Simulation results validate the accuracy of our theoretical analysis

Optimizing spectral reuse is a major issue in large-scale IEEE 802.11 wireless networks. Power control is an effective means for doing so. Much previous work simply assumes that each transmitter should use the minimum transmit power needed to reach its receiver, and that this would maximize the network capacity by increasing spectral reuse. It turns out that this is not necessarily the case, primarily because of hidden nodes. In a network without power control, it is well known that hidden nodes give rise to unfair network bandwidth distributions and large bandwidth oscillations. Avoiding hidden nodes (by extending the carrier-sensing range), however, may cause the network to have lower overall network capacity. This paper shows that in a network with power control, reducing the instances of hidden nodes can not only prevent unfair bandwidth distributions, but also achieve higher overall network capacity compared with the minimum-transmit-power approach. We propose and investigate two distributed adaptive power control algorithms that minimize mutual interferences among links while avoiding hidden nodes. In general, our power control algorithms can boost the capacity of ordinary non-power-controlled 802.11 networks by more than two times while eliminating hidden nodes

A main distinguishing feature of a wireless network compared with a wired network is its broadcast nature, in which the signal transmitted by a node may reach several other nodes, and a node may receive signals from several other nodes simultaneously. Rather than a blessing, this feature is treated more as an interference-inducing nuisance in most wireless networks today (e.g., IEEE 802.11). The goal of this paper is to show how the concept of network coding can be applied at the physical layer to turn the broadcast property into a capacity-boosting advantage in wireless ad hoc networks. Specifically, we propose a physical-layer network coding (PNC) scheme to coordinate transmissions among nodes. In contrast to "straightforward" network coding which performs coding arithmetic on digital bit streams after they have been received, PNC makes use of the additive nature of simultaneously arriving electromagnetic (EM) waves for equivalent coding operation. PNC can yield higher capacity than straight-forward network coding when applied to wireless networks. We believe this is a first paper that ventures into EM-wave-based network coding at the physical layer and demonstrates its potential for boosting network capacity. PNC opens up a whole new research area because of its implications and new design requirements for the physical, MAC, and network layers of ad hoc wireless stations. The resolution of the many outstanding but interesting issues in PNC may lead to a revolutionary new paradigm for wireless ad hoc networking.

When an IEEE 802.11 ad-hoc network achieves capacity C by using a single channel, the targeted capacity by using two channels should be2middotC. However, most or the multi-channel 802.11 protocols proposed in the literature only appear to be able to achieve less than 60% or the 2middotC targeted capacity. In our paper (2006), we proposed a link-directionality-based dual channel MAC protocol (DCP) to boost the network capacities up to 78% of our targeted capacities, 78%*2middotC = 1.56middotC. However, DCP still failed to reach the 2middotC capacity target due to the overheads incurred by the protocol. In this paper, we implement a power exchange algorithm on top of the DCP in an attempt to double the capacities of networks using the single-channel 802.11 protocol. This algorithm incurs relatively small overheads and can further release the protocol constraints imposed by DCP. Simulations show that the proposed scheme (DCPwPEA) can achieve more than 132% of our targeted capacities, 132%* 2middotC = 2.64middotC. We believe this protocol can be extended to allow multi-link simultaneous transmissions which can multiply the network capacities of ad-hoc networks by using only two channels

This paper investigates the scale law of network capacity of wireless ad hoc networks with phased array antennae and demonstrates its dramatic improvement over that with omni-directional antennae. The contributions of this paper are three-fold. First, we establish a general interference model for directional antennae of generic antenna patterns. Second, we argue that an arbitrary directional antenna pattern can be approximated by that of a phased array antenna. We investigate wireless networks with phased array antennae and derive the impact of nulls and null width in the antenna pattern on the scalability of network capacity. Third, we introduce a novel analytical approach that gives rise to a new set of network-capacity upper and lower bounds when directional antennae are used. We believe that this is the first work that shows that Theta(n) scalability in network capacity is achievable provided the dimension of the antenna array is sufficiently large

In a realistic WLAN environment, frame losses may be caused by collisions or channel noise. The existence of noise-induced losses reduces the effectiveness of the standard WLAN backoff algorithm for contention resolution, which assumes that all losses are caused by collisions and always doubles the contention window to reduce contention upon a frame loss. In this paper, we propose new backoff algorithms that take advantage of a new capability to differentiate the losses, and thereby sharpen the accuracy of the contention resolution process. Analytical models are developed to analyze the performance of these algorithms under heterogeneous link conditions in a WLAN. Both analysis and simulation results show that significant improvement of throughput and fairness can be obtained for WLANs in which contention resolution is. enhanced by the loss differentiation ability

In a WLAN subject to variable wireless channel conditions, rate adaptation plays an important role to more efficiently utilize the physical link. However, the existing rate adaptation algorithms for IEEE 802.11 WLANs do not take into account the loss of frames due to collisions. In a WLAN with coexistence of multiple stations, two types of frame losses due to (a) link errors and (b) collisions over the wireless link can coexist and severely degrade the performance of the existing rate adaptation algorithms. In this paper, we propose a new automatic rate fallback algorithm that can differentiate the two types of losses and sharpen the accuracy of the rate adaptation process. Numerical results show that the new algorithm can substantially improve the performance of IEEE 802.11 WLANs.

The explosive growth of high-data-rate and multimedia real-time applications imposes new challenges on the design of future wireless communications systems. In this paper, a cross MAC-PHY layer link-adaptive largest-weighted-throughput packet scheduling algorithm is proposed to provide QoS guarantees to real-time traffics over wireless packet-switched networks. The proposed algorithm aims to satisfy the stringent packet delay constraints while obtaining a high system spectral efficiency. The objective is achieved by two interactive components: a MAC service discipline and a PHY rate-and-power adaptation scheme. It is demonstrated in the numerical results that the proposed algorithm significantly improves the system performance in terms of spectral efficiency and packet loss rate, thanks to the successful exploitation of the inherent system diversities in the time, frequency, and multiuser domains.

The seminar work of Gupta and Kumar showed that multi-hop wireless networks with capacity scalable with the number of nodes, n, are achievable in theory. The transport capacity scales as /spl Theta/(/spl radic/n), while the capacity scales as /spl Theta/(n). A subsequent study, on the other hand, showed that the capacity of IEEE 802.11 networks does not scale with n due to its carrier-sensing mechanism. This prior work, however, has not considered the use of power control. The main contributions of this paper are three-folds: 1) we provide an analytical framework for deriving the design requirements of adaptive power control strategies; 2) we demonstrate that 802.11 networks are scalable with power control; 3) however, an enhanced MAC protocol called selective disregard of NAVs (SDN) can achieve substantially higher capacity with an adaptive power control scheme; in particular, adaptive power control allows SDN to achieve capacity within 75% of the theoretical optimal capacity of infrastructure-mode wireless networks. A reason why adaptive power control works well is that it takes into consideration the fundamental mutual-interference relationships between links in the vicinity of each other, and adjust their relative transmit powers to reduce these interferences to a large extent that is possible theoretically.

The concept of care-of-address (CoA) is a major cause of excessive handoff delay in Mobile IPv6 for real time multimedia traffic. Many schemes eliminate the use of CoA at the micro-mobility scale, but leave the macro-mobility unsolved. This paper proposes a novel alternative IPv6 mobility scheme based on universal addressing - Cellular Universal IP (CUIP) - for real-time traffic in wireless access networks. In CUIP, a mobile node is addressed with a universal IP address regardless of its location, making CoA and tunneling unnecessary in micromobility and even macromobility handoffs. CUIP manages roaming and handoff differently - whereas explicit signaling is used for roaming, a handoff-on-the-fly route-update scheme is used during handoff to embed signaling information into the outgoing data packets to minimize handoff delay. We prove analytically that, on average, fewer than three routers need to be updated per handoff. As a result, CUIP incurs an expected network layer handoff delay on the order of milliseconds only. In addition, the support of QoS is possible. A simple security scheme is also proposed to enable mutual authentication at the network layer.

Transmission control protocol (TCP) performs well in traditional wired networks where the packet loss rate is low. However, in heterogeneous wired/wireless networks, the high packet loss rate over wireless links may result in excessive invocation of the congestion control algorithm, thus deteriorating the performance of TCP. In this paper, a novel localized link layer retransmission protocol, called clustered-loss retransmission protocol (CLRP), is proposed. CLRP consists of three protocol components, namely, TCP-FH deployed on a fixed host, TCP-MH deployed on a mobile host and CLRP-BS deployed on a base station. CLRP can provide not only explicit distinction between congestion and packet corruption losses, and effective multiple wireless loss information for retransmissions, but also better retransmission control for wireless losses. Thus it is well suited to wireless networks, in which packet loss and bursty packet corruption is a serious problem. Moreover, CLRP does not require any modifications to TCP deployed on fixed hosts.

Unlike wired networks, wireless networks are characterized by channel errors. In wireless LANs (WLANs), link-layer ARQ can be used for error recovery. However, this technique assumes packet losses are due to packet collisions. With FIFO queuing at the access point (AP), ARQ may give rise to a "head-of-line (HOL) blocking" phenomenon that severely degrades the throughput performance. We study a simple adaptive round robin (ARR) scheduler at the LLC (logical link control) layer as a solution to the HOL blocking problem. Salient features of ARR include: 1) an explicit estimate of the channel state is not required; 2) compatibility with the existing IEEE 802.11 MAC protocol; 3) ability to achieve near-optimal throughput; 4) flexibility for meeting various throughput-fairness objectives. Besides extensive simulations, we also give the analytical upper and lower bounds for WLAN throughput with ARR. Our analysis closely matches the simulation results.

The paper considers scenarios in which fairness and efficiency are two conflicting objectives in wireless networks, and investigates the use of a proportional fairness objective to strike a balance between the two objectives. We explain the physical meaning of proportional fairness in a wireless network and give an analysis showing that proportional fairness is equivalent or close to max-min fairness in terms of air-time usage (as opposed to bandwidth usage). For infrastructure WLANs, two approaches to achieving proportional fairness are discussed. For ad hoc networks, achieving proportional fairness is more complex and requires global information on contention among different traffic flows. We propose and evaluate the use of a distributed max-min air-time allocation algorithm to approximate the proportional fairness objective.

In large-scale wireless networks, interference among nodes limits channel spatial re-use and is a main hurdle for scalable performance. There are two types of interference: (1) physical interference due to the receiver's inability to decode a signal when the power received from other signals is large; (2) protocol interference imposed by the specific multi-access protocol being used. The paper models both interference types in terms of a set of inequality constraints for the IEEE 802.11 CSMA/CA protocol. Based on the inequalities, we investigate the impact of some parameters (basic-rate, data-rate, and physical-preamble-rate) on channel spatial re-use. Regardless of the parameter settings, the total capacity in an 802.11 network reaches a ceiling as the number of nodes, n, increases. We identify the fundamental causes for the non-scalable performance, and show that 802.11 can be made to be scalable with a simple modification, achieving O(n) throughput without adaptive power control. We believe that this is the first paper to demonstrate this.

The lack of end-to-end quality of service support in the current Internet has caused significant difficulties to ensuring playback continuity in video streaming applications. This study addresses this challenge by investigating a new adaptation algorithm to adjust the bit-rate of video data in response to the network bandwidth available to improve playback continuity. Unlike previous works, the proposed algorithm is transparent to the video client, requires no parameter tuning, and yet can outperform existing algorithms. This paper presents this algorithm, evaluates and compares its performance with the best algorithm currently available using extensive trace-driven simulations.

This paper proposes and investigates a simple self-adaptive contention window adjustment algorithm for 802.11 WLAN. We present simulation and analytical results showing that the new algorithm outperforms the standard 802.11 window-adjustment algorithm. Compared with the standard and previously proposed enhancement algorithms, a salient feature of our algorithm is that it performs well both when the number of active stations is large and small that is, in both heavy and light contention cases. Furthermore, the adaptive window adjustment algorithm is simpler than previously proposed enhancement schemes in that no live measurement of the WLAN traffic activity is needed.

Voice-over-IP (VoIP) is.an important application on the Internet. With the emergence of WLAN technology and its various advantages compared with the traditional wired LAN, it is fast becoming the "last-mile" of choice for the overall Internet infrastructure. This work considers the support of VoIP over 802.11b WLAN. We show that although the raw WLAN capacity can potentially support more than 500 VoIP sessions, various overheads bring this down to only 12 VoIP sessions when using GSM 6.10 codec. We propose a novel multiplexing scheme for VoIP which exploits multicasting over WLAN for the downlink VoIP traffic. This scheme can achieve nearly 100% improvement in system capacity. In addition, we present results showing that the delay and delay jitter introduced by the proposed scheme are small. We believe that the scheme can reduce the blocking probability of VoIP sessions in an enterprise WLAN significantly.

TCP throughput instability is a well-known phenomenon in IEEE 802.11 multi-hop ad-hoc networks. However, we find that this problem is not restricted to TCP traffic only, but also occurs in UDP traffic. The associated throughput oscillations are not acceptable for real-time applications such as video conferencing and voice-over-IP. The paper re-defines this throughput fluctuation as a "re-routing instability problem" since it is caused by the triggering of the re-routing function. In particular, we show that the throughput instability is mainly induced by re-routing, not the binary exponential back-off of the IEEE 802.11 MAC protocol. Turning off the re-routing function, for example, eliminates the problem. We believe that this is the first paper to study this phenomenon in the context of re-routing instability. We propose to modify the ad-hoc routing protocols with a "don't-break-before-you-can-make" strategy. The scheme does not require modifications of the IEEE 802.11 standard, making it readily deployable using existing commercial wireless LAN (WLAN) products. Simulations show that the proposed scheme can significantly reduce the throughput variation in a traffic flow by 50-70% and improve the average throughput by up to 11%.

In a multi-hop ad-hoc network, stations may pump more traffic into it than can be supported, resulting in high packet-loss rate, rerouting instability and unfairness problems. The paper shows that controlling the offered load at the sources can eliminate these problems. In addition, we provide an analysis to estimate the optimal offered load that maximizes the throughput of a multi-hop traffic flow. We use this result to devise schemes that can achieve fairness when there are multiple flows from different sources to different destinations. We believe this is the first paper in the literature to provide a quantitative analysis (as opposed to simulation) for the impact of hidden nodes, exposed nodes, and signal capture on sustainable throughput. The analysis is based on the observation that a large-scale 802.11 network with hidden nodes is a network in which the carrier-sensing capability breaks down partially. Its performance is therefore somewhere between a carrier-sensing network and an ALOHA network. Indeed, our analytical closed-form solution has the appearance of the throughput equation of the ALOHA network. Our approach allows one to identify whether the performance of an 802.11 network is hidden-node limited or spatial-reuse limited.

TCP is the most widely adopted transport layer communication protocol. In heterogeneous wired/wireless networks, however, the high packet loss rate over wireless links can trigger unnecessary execution of TCP congestion control algorithms, resulting in performance degradation. TCP performs poorly on wireless links with bursty losses, when it is forced to rely on limited information available from batched acknowledgements, (i.e., multiple packets are acknowledged with one acknowledgment packet). In this paper, a selective negative acknowledgement (SNACK) mechanism is designed to overcome the limitation of batched acknowledgments. A new link layer retransmission protocol, called, SNACK-NS (new snoop), is proposed. Through the detection and retransmission functions that are provided by the two protocol components of SNACK-NS, namely, SNACK-snoop and SNACK-TCP, the transmission performance of TCP over wireless network is greatly enhanced in both fixed host (FH) to mobile host (MH) and MH to FH transmissions.

The rapid growth of wireless LAN (WLAN) deployments will bring about many novel mobile applications. Among them will be real-time multimedia streaming applications running on UDP, which may interfere with current data applications running on TCP. This paper is a first attempt to investigate how to ensure the performance of these two groups of applications when they co-exist over a WLAN. Toward this end, we have designed and implemented a UDP rate adaptation scheme called adaptive-buffer rate control (ABRC) for multimedia streaming over WLAN. ABRC has two distinguishing features compared with other schemes: 1) it can achieve arbitrary bandwidth allocations between UDP and TCP in the WLAN, as opposed Io previously proposed "TCP friendly" schemes, which can only achieve uniform bandwidth allocations; and 2) the majority of previously proposed flexible bandwidth-allocation schemes achieve arbitrary bandwidth allocations by prioritizing and scheduling packet transmissions within network equipment (i.e., within routers, base stations, etc.). In contrast, ABRC is an end-to-end application-layer solution that does not require changes to current WLAN products, making it more readily deployable over existing networks.

Abstract In this paper, a simple self‐adaptive contention window adjustment algorithm for 802.11 wireless local area networks (WLAN) is proposed and analyzed. Numerical results show that the new algorithm outperforms the standard 802.11 window adjustment algorithm. Compared with the standard and previously proposed enhancement algorithms, a salient feature of our algorithm is that it performs well in both heavy and light contention cases regardless of the packet sizes and physical versions. Moreover, the adaptive window adjustment algorithm is simpler than previously proposed schemes in that no live measurement of the WLAN traffic activity is needed. Copyright © 2004 John Wiley & Sons, Ltd.

In the traditional IEEE 802.11 wireless LAN using infrastructure mode, all users share the same channel and all packets are forwarded by an access point (AP). As a result, as the number of users in the cell increases, the throughput for each user degrades substantially. If there are users communicating with each other within the cell (as in conferencing or file exchange applications), such throughput degradation could be relieved by making these users communicate through ad hoc connections without going through the AP. The advantages are multi-fold. First, the traffic load at the AP is reduced, hence relieving the contention. Second, ad hoc connections are single-hop, hence improving the channel efficiency. Moreover, ad hoc connections could use different channels, hence multiplying the system bandwidth. In this paper, we propose to integrate the infrastructure mode and the ad hoc mode in a wireless network so as to achieve these advantages. We present a framework for such mixed-mode wireless LAN (termed M/sup 2/-WLAN). In such a network, a node can dynamically switch between the infrastructure mode and the ad hoc mode according to the instruction of the AP, and hence the switching is transparent to the users. Using simulations, we show that M/sup 2/-WLAN can indeed improve system throughput substantially without user's manual configuration.

This paper examines the impact of RED on two versions of TCP - traditional TCP Reno and a newly proposed variant, TCP Veno - over 802.11b WLAN. TCP Reno was originally designed for wired networks where packet losses are primarily due to network congestion. This assumption is not always true in wireless networks, in which packet losses can be due to transmission errors on the noisy wireless link. TCP Veno refines the algorithms in Reno by distinguishing between noncongestive and congestive states, and avoids the unnecessary reduction of TCP congestion window when packet losses are not due to congestion. Our results show that TCP Veno can achieve up to 30% more throughput than TCP Reno when link quality is poor. Our results also show that TCP Veno is compatible with RED. In addition, although RED does not help to further improve the throughput in Veno, it can improve fairness among co-existing TCP flows.

Wireless access networks in the form of wireless local area networks, home networks, and cellular networks are becoming an integral part of the Internet. Unlike wired networks, random packet loss due to bit errors is not negligible in wireless networks, and this causes significant performance degradation of transmission control protocol (TCP). We propose and study a novel end-to-end congestion control mechanism called TCP Veno that is simple and effective for dealing with random packet loss. A key ingredient of Veno is that it monitors the network congestion level and uses that information to decide whether packet losses are likely to be due to congestion or random bit errors. Specifically: (1) it refines the multiplicative decrease algorithm of TCP Reno-the most widely deployed TCP version in practice-by adjusting the slow-start threshold according to the perceived network congestion level rather than a fixed drop factor and (2) it refines the linear increase algorithm so that the connection can stay longer in an operating region in which the network bandwidth is fully utilized. Based on extensive network testbed experiments and live Internet measurements, we show that Veno can achieve significant throughput improvements without adversely affecting other concurrent TCP connections, including other concurrent Reno connections. In typical wireless access networks with 1% random packet loss rate, throughput improvement of up to 80% can be demonstrated. A salient feature of Veno is that it modifies only the sender-side protocol of Reno without changing the receiver-side protocol stack.

Voice communications such as telephony are delay sensitive. Existing voice-over-IP (VoIP) applications transmit voice data in packets of very small size to minimize packetization delay, causing very inefficient use of network bandwidth. This paper proposes a multiplexing scheme for improving the bandwidth efficiency of existing VoIP applications. By installing a multiplexer in an H.323 proxy, voice packets from multiple sources are combined into one IP packet for transmission. A demultiplexer at the receiver-end proxy restores the original voice packets before delivering them to the end-user applications. Results show that the multiplexing scheme can increase bandwidth efficiency by as much as 300%. The multiplexing scheme is fully compatible with existing H.323-compliant VoIP applications and can be readily deployed.

TCP Vegas employs congestion avoidance, early detection of packet loss and conservative slow-start algorithms to improve TCP performance. With its proactive congestion detection, it utilizes network bandwidth more efficiently and achieves a higher throughput than TCP Reno. This paper shows that in asymmetric networks in which the bottleneck is on the reverse path rather than on the forward path, its performance can be significantly lower than that of Reno. In particular, Vegas may erroneously converge to an operating region in which the available bandwidth on the forward path is under-utilized by a large margin. Even worse, when connections running Vegas and Reno co-exist and compete on the same network, Vegas suffers a severe penalty. We propose an approach to improve Vegas' throughput in asymmetric networks.

The three-stage Clos network has been studied extensively as a framework for the implementation of large-scale ATM switches. Previously, a quasi-static routing scheme for three-stage Clos networks, called the path-switching scheme, has been proposed by Lee and Lam to achieve low switch complexity and high throughput. We derive in this paper the nonblocking conditions when the bandwidth requirements of traffic are rounded up to simplify switch operation. We discuss the implications of these results for switch implementation. In particular, we show how use the results to build a semi-optical network to reduce switch complexity.

We investigate the problem of destination address resolution in closed multicast networks. By making use of the recirculating property of the closed networks, we propose a lookup node-based destination address resolution (LUNDAR) mechanism and a hybrid approach that facilitate destination address resolution by means of a lookup process. We show that these two strategies result in a tradeoff between the memory consumption and the incurred throughput reduction. Depending on the relative costs of memory and throughput, the network parameters can be adjusted to obtain the best balance between these costs.

This paper investigates in detail the blocking and nonblocking behavior of multirate Clos switching networks at the connection/virtual connection level. The results are applicable to multirate circuit and fast-packet switching systems. Necessary and sufficient nonblocking conditions are derived analytically. Based on the results, an optimal bandwidth partitioning scheme is proposed to reduce switch complexity while maintaining the nonblocking property. The blocking behavior of blocking switches supporting multicast connections is investigated by means of simulation. We propose a novel simulation model that filters out external blocking events without distorting the bandwidth and fanout (for multicasting) distributions of connection requests. In this way, the internal blocking statistics that truly reflect the switch performance can be gathered and studied. Among many simulation results, we have shown that for point-to-multipoint connections, a heuristic routing policy that attempts to build a narrow multicast tree can have relatively low blocking probabilities compared with other routing policies. In addition, when small blocking probability can be tolerated, our results indicate that situations with many large-fanout connection requests do not necessarily require a switch architecture of higher complexity compared to that with only point-to-point requests.

Future broad-band communications networks are expected to be dominated by video and image traffic. Variable bit-rate (VBR) video compression is generally preferred to constant bit-rate (CBR) compression because constant image quality can be provided. In contrast, CBR transport is preferred to VBR transport from the networking standpoint because of its simplicity. This paper studies the important issue of adapting VBR compressed video for transport over a CBR channel. We focus on temporal traffic smoothing using an elastic buffer. The target image quality and the output rate of the video encoder is controlled by feedback based on the buffer-occupancy level. Previous adaptation schemes are not readily analyzable. An analyzable control-theoretic adaptation framework is proposed. It allows systematic and quantitative investigation of issues such as stability, robustness against scene changes, robustness against image-quality oscillations due to coding-mode switching, and tradeoffs between image-quality and buffer-occupancy (delay) fluctuations. Perhaps more importantly, the framework opens up many new possibilities for further research.

Multicast capability can be incorporated into any interconnection network by using a general packet replication scheme. The network can then be used for both packet replication and routing processes. Unfortunately, such a multicast network can easily evolve to saturation due to instability. Once the network is saturated, the throughput drops to zero. The operation of the multicast network must therefore be carefully controlled to avoid the unstable region. Not well-thought-out control schemes, however, may result in a small throughput and inefficient utilization of the network. This paper investigates the stability issue in the multicast shuffle-exchange network in detail. Several schemes are then proposed to remove network instability. Our study indicates that a dynamic access control scheme can potentially achieve high network throughput even under nonuniform traffic conditions.

MPEG is a popular compression standard used in many multimedia applications. In video distribution systems, a CBR communications channel is often shared among several VBR MPEG video streams. Since there are fluctuations of data rates in video streams, traffic congestion may occur and video quality may be affected. We propose a frame-skipping aggregation technique to multiplex several MPEG streams (outside the network) to feed into a CBR channel (within the network). The salient feature of the scheme is that the transmission of bi-directionally predicted frames will be slipped (outside the network) before the onset of traffic congestion so as to minimize the image quality degradation. Our result shows that using this technique, more users can be supported compared to regular video transmission systems. This technique allows us to adopt a simple call admission strategy in which video requests are granted based on their mean rates.

This paper examines the application of a simple yet general packet replication scheme to achieve multicasting in closed interconnection networks. The performance of these networks is studied and a general throughput equation is obtained to express the overall network throughput in terms of the average routing delay of the corresponding point-to-point network. The multicast performance results are thus built on top of the previously-established, and often simpler, point-to-point results. Making use of this formula, we investigate the multicast closed shuffle-exchange network in detail. Analytical results are compared with simulation results to obtain further insights into the network operation and ways to improve the network performance.

This paper introduces a new concept called lossless aggregation for the transmission of video information. It is a scheme for the delivery of variable bit-rate (VBR) video streams from a video server to a group of users over a shared channel. No data are dropped at the source during the adaptation process that reshapes the VBR video traffic to conform to the channel bit-rate characteristics. The transmission schedules of individual video streams evolve in a dynamic way that depends on their relative traffic characteristics. Receiver buffer underflow and overflow are prevented. Therefore, the data delivery process does not cause any loss of image quality. We show that very significant receiver-buffer reduction can be achieved with aggregation compared with the independent transmission of individual video streams over separate channels. Several bandwidth allocation methods for aggregation are studied extensively. The frame equalization algorithm stands out in terms of its simplicity and optimality.

This paper describes an end-to-end parallel communications scheme based on a vector routing algorithm (VRA) for ATM network control and management. An information string is partitioned into m parts, which are then coded into k > m parts and sent out on k separate subchannels to the receiver. When m of the k parts are received correctly, the original information can be reconstructed. Two desirable effects are achieved in the context of ATM traffic control: (1) the burstiness of the source traffic can be smoothed out by the partition process; (2) the quality of service in terms of error, loss and delay can be controlled using the number of redundant routes k — m as a control parameter. Our results show that VRA is especially suitable for services with highly bursty traffic. We argue that several network management issues, including reliability, evolution and integration, security, and administration and billing can be addressed in a simple manner using the VRA framework.

In a stable packet-switched network, throughput equals offered load and packet backlogs do not build up in an unbounded manner. A network with an unstable operating region poses the problem that it may evolve eventually to a stable but saturated operating point with a low throughput. This paper considers the shuffle-exchange and bidirectional shuffle networks when operated with deflection routing. It is shown that both networks exhibit instability when packet contention is resolved in a random manner. However, instability can be avoided if contention is resolved in a manner that favors packets closest to their destinations. This obviates the need for complicated network access control to prevent instability.

Video information can be transmitted using a variable bit rate (VBR) or a constant bit rate (CBR) virtual channel in a broadband network (e.g., an ATM network). CBR transmission has many advantages from the networking standpoint: multiplexing, bandwidth allocation, user/network contractual agreement, and network-usage tariff are all simpler under the CBR transmission framework. This paper considers how to deliver video over a CBR channel. It introduces a new concept called lossless aggregation for the transmission of a bundle of stored videos over a common channel. No data is dropped during the adaptation process and hence it does not cause any image degradation. We show that significant receiver buffer reduction can be achieved using lossless aggregation.

This paper investigates how video source data should be compressed to conform to the leaky-bucket (LB) specification for transmission over a communications network. The buffer occupancy of the compressed data is used to effect compression of future video frames. Two general strategies for using the tokens in the LB are investigated. The greedy transmission strategy will send out a cell whenever a token is available-that is, a token will not be saved while there is a data backlog in the buffer. We show a general way to modify any existing constant bit rate compression (or rate-control) scheme for a corresponding LB compression scheme using the concept of a virtual buffer. The non-greedy transmission strategy uses "extra" tokens only when buffer overflow is impending and saves up tokens for future usage when underflow is about to occur. The non-greedy strategy is generally better than the greedy strategy. The overall conclusion is that tokens should be used only under the "emergency" situation when overflow occurs and not during the normal situation just to smooth image quality from time slot to time slot.

A new transform, called the rounding transform (RT), is introduced which employs a pair of rounding operations namely, rounding up and rounding down operations. The RT is of interest in pyramid data structured coding for progressive and lossless image transmission, since the total number of data to be transmitted is the same as that of the original without overhead bits and since it has the advantages of both implementation with various elementary block sizes and filters. Additionally, the previous methods, reduced difference pyramid (RDP) and hierarchy embedded differential image (HEDI) are proved to be only simple cases of the rounding transform. Computer simulations prove that several kinds of rounding transform can be found, which perform better than the previous methods.

Future broadband integrated services networks based on the asynchronous transfer mode (ATM) technology are expected to carry information from a large variety of different services and applications. This paper investigates video aggregation, a concept that integrates compression and statistical multiplexing of video information for transport over a communication network. We focus on the transmission of a group of video sessions as a bundle, the practical examples of which include entertainment-video broadcast and video-on-demand (VoD). In this situation, the advantage of constant bit-rate (CBR) transport (which facilitates simple network management and operation) and the advantage of variable bit-rate (VBR) video compression (which yields smoother image quality) can be achieved simultaneously. We show that it is better to integrate compression and statistical multiplexing before the bundle of video traffic enters the network than performing them as independent processes. We present experimental results which indicate the advantages of video aggregation in terms of superior image quality and efficient bandwidth usage.

To simplify traffic control in a network, it is desirable that the traffic-control policy at a network node depends only on the external traffic loads on the input and output links, but not on the detail addressing or distribution of packets from inputs to outputs. In other words, it should be possible to guarantee the grade-of-service of an input-output connection by controlling the aggregate loads on the input and output. Switch nodes in which such a traffic-control policy is possible are said to have the property of the sufficiency of the knowledge of external loads (SKEL). One way to demonstrate the feasibility of SKEL for a particular switch is to show that the performance under any nonuniform traffic distribution from inputs to outputs is better than or close to the performance under the uniform traffic distribution. The contributions of this paper are twofold: clarifying issues related to SKEL and establishing its feasibility for generic input- and output-buffered switches on a rigorous basis. The following summarizes our major results: (1) The packet-loss probability due to the Knockout switch-design principle for packets destined for an arbitrary output is maximum when the traffic to that output originates uniformly from all inputs; (2) The packet-loss probability for packets destined for a particular output under uniform traffic closely approximates the loss probability for packets from the worst-case input to that output under nonuniform traffic; (3) For mean and variance of delay, similar results as in (1) and (2) can be obtained; (4) For an input-queued switch, external link loadings that do not give rise to queue saturation under uniform traffic will not do so under nonuniform traffic either.

Multicasting in broadband packet switches and metropolitan networks can be achieved by first replicating the packets and then routing them to their destinations. This paper studies a simple but general replication scheme that can be applied to arbitrary interconnection-network topologies. The replication process of a packet adapts itself according to the network topology and the traffic condition. Hot spots of replication activities are diffused by this scheme which automatically migrates the replication efforts to less active network regions. The scheme can potentially be used in networks (e.g., the Manhattan-street network) in which multicasting was thought to be inherently difficult. This paper, however, focuses on the shuffle-exchange copy network for a detailed study of the replication algorithm and its implementation at the logic-diagram level. It is found that the performance of the algorithm improves with the increase in network dimensions. Cascading the copy network with a point-to-point switch makes a multicast switch. A novel strategy for reducing the memory size of its routing tables is proposed.

Multicasting in broadband packet switches and metropolitan networks can be achieved by first replicating the packets and then routing them to their destinations. This paper studies a very simple but general replication scheme that can be applied to arbitrary interconnection-network topologies. The replication process of a packet adapts itself according to the network topology and the traffic condition. Hot spots of replication activities are diffused by this scheme which automatically moves part of the replication efforts to less active network regions. The scheme can potentially be used in networks (e.g., the Manhattan-street network) in which multicasting were thought to be inherently difficult. Fundamental issues and critical problem areas are laid out, and solutions addressing them are proposed. The performance of the replication algorithm and its implementation (logic diagram level) in the shuffle-exchange copy network are investigated in detail. It is found that the performance of the algorithm improves with the increase of network dimensions.

This paper formulates a general framework that includes and extends the existing definitions for network survivability. Based on this framework, network survivability is characterized by a survivability function rather than a single-value survivability measure, and various quantities of interest can be derived from the function. Examples are the expected survivability, the worst-case survivability, the r-percentile survivability, and the probability of zero survivability. The survivability function is especially useful for the study of large-scale disasters. For illustration, the authors derive the survivability function in closed form for a simple ring network under link failures. They also discuss the general procedure for finding survivability functions for complex networks, and show that the survivability function reveals useful information about a network. This framework provides a unified and practical approach to analyzing and designing highly survivable communications networks.>

A theoretical foundation for the evaluation and comparison of a very broad spectrum of fast packet-switching techniques is developed. Based on this framework, the authors investigate the complexity of various packet switch designs, and demonstrate the advantage of dilation as a switch-design technique. Packet switches are classified either as loss systems or waiting systems, according to whether packets losing contention are dropped or queued. In a loss system, the packet loss probability can be made arbitrary small by providing enough paths between inputs and outputs. The authors focus on the question: how does the switch complexity grow as a function of switch size for a given loss probability requirement? A uniform approach to this problem is developed. It is shown that for an N/spl times/N switch, the required number of switch elements for both the parallel-banyan network and the tandem-banyan network is of order N(log N)/sup 2/, whereas the complexity of a dilated-banyan network is of order N log N(log log N). Within the class of waiting systems, it is shown that the parallel banyan networks in a Batcher-parallel-banyan network can be replaced by a dilated-banyan network without sacrificing the nonblocking property. Thus, as with parallelization, dilation can also be used to increase the throughput of a waiting system. In addition, the authors also explore the application of dilation in a large modular switch design which is realized by an interconnection structure consisting of Batcher-dilated-banyan networks and statistical multiplexers.>

This paper investigates the packet loss probabilities of several alternative input-buffered and output-buffered switch designs with finite amounts of buffer space. The effects of bursty traffic, modeled by geometrically distributed active and idle periods, are explored. Methods for improving switch performance are classified, and their effectiveness for dealing with bursty traffic discussed. This work indicates that bursty traffic can degrade switch performance significantly and that it is difficult to alleviate the performance degradation by merely restricting the offered traffic load. Unless buffers are shared, or very large buffers provided, strategies that improve throughput under uniform random traffic are not very effective under bursty traffic. For input-buffered switches, our investigation suggests that the specific contention resolution scheme we use is a more important performance factor under bursty traffic than it is under uniform random traffic. In addition, many qualitative results true for uniform random traffic are not true for bursty traffic. The work also reveals several interesting, and perhaps unexpected, results: 1) output queueing may have higher loss probabilities than input queueing under bursty traffic; 2) speeding up the switch operation could result in worse performance than having several output ports per output address under bursty traffic; and 3) if buffers are not shared in a fair manner, sharing buffers could make performance worse than not sharing buffers at high traffic loads. Simulation results and intuitive explanations supporting the above observations are presented.>

An approach to building a large ATM switch is to simply set up a regularly-structured network in which smaller switch modules are interconnected. Routing is an issue if there are multiple paths from any input to any output in such a network. We focus on the 3-stage Clos network, not only because it is the architecture of choice for several potential switch manufacturers, but also because its high connectivity poses a stringent test on routing algorithms. One optimal and two heuristic algorithms have been designed and tested. Our results show that the heuristic algorithms can find multicast routes that are close to optimal within a response time that is significantly lower than that of the optimal algorithm. Further analysis of the experimental data suggests a hybrid implementation in which the optimal and heuristic algorithms are run in parallel with a set time limit. Finally, although this paper is motivated by the Clos switching network, the algorithms and the discussion here also apply to communications networks with a two-hop structure.>

Describes a dual shuffle-exchange switching network (DSN) that makes use of the principle of error-correcting routing. For motivation, parallels are drawn between error-correcting routing in switching and error-correcting coding in transmission. Based on a novel error-correcting and self-routing algorithm, the authors show by analysis and simulation that the DSN can achieve the Shannon's lower bound Nlog N on switch complexity while satisfying four desirable criteria: 1) self-routing property; 2) no queueing of packets at the inputs or inside the switch; 3) arbitrarily small packet-loss probability; 4) close-to-100% throughput. Different implementations of the basic DSN concept and their trade-offs are discussed.>

It is desirable that the traffic control policy at a network node depend on the external traffic loads on the input and output links, but not on the detailed addressing or distribution of packets from inputs to outputs. It should be possible to guarantee the grade of service of an input-output connection by controlling the aggregate loads on the input and output. Switch nodes in which such a traffic control policy is possible are said to have the property of the sufficiency of the knowledge of external loads (SKEL). The authors clarify issues related to SKEL and establish its feasibility for a generic switch node on a rigorous basis.>

The performance of a class of asymmetric packet switch modules with channel grouping is analyzed. The switch module considered has n inputs and m outputs. A packet destined for a particular output address (out of g) needs to access only one of the r available physical output ports: m=gr. These switch modules are the key building blocks in many large multistage switch architectures. The focus is on the performance of input-buffered and output-buffered switch modules under geometrically bursty traffic. A combination of exact derivation, numerical analysis, and simulation yields the saturation throughput of input-buffered switch modules and the mean delay of the input-buffered and output-buffered switch modules. Tables and formulas useful for traffic engineering are presented. The results show that increasing the number of output ports per output address (r) can significantly improve switch performance, especially when traffic is bursty. Although output-buffered switch modules have significantly better performance than input-buffered switch modules when there are equal numbers of input and output ports, this performance difference becomes significantly smaller when the switch dimensions are asymmetric.>

The switch modules are studied because they are the key building blocks in large multistage switch architectures. The switch module considered has n inputs and m outputs. A packet destined for a particular output address (out of g) needs to access only one of the r available physical output ports: m=gr. Input-buffered, output-buffered, and unbuffered switch modules are studied. The results show that increasing the number of output ports per output address (r) can significantly improve the performance of buffered as well as unbuffered switch modules. For acceptable performance, the difference in throughput between buffered and unbuffered switch modules is considerable. For buffered switch modules, an interesting observation is that although output-buffered switch modules have significantly better delay performance than input-buffered switch modules when n=gr, the performance difference is diminished as one deviates from these switch dimensions.>

The problem in the above paper (see ibid., vol.COM-35, p.755-61, July 1987) is formulated in terms of a max-flow network problem. The main theorem can be proved quite simply using the max-flow-min-cut theorem once the proper way of looking at the problem is identified.>