Frame slotted ALOHA (FSA) has been thede factomultiple-access protocol for many energy-efficient Internet of Things applications. To improve the age of information (AoI) that measures the freshness of the status update, we devote this paper to designing an age-threshold FSA protocol that adaptively limits the contention in each frame to users with age gains as high as possible, by focusing on a multiple-packet reception (MPR) physical layer model of practical importance for the first time. For an ideal scenario where the coordinator always knows the exact age gain of each user, we propose a low-complexity algorithm to approximate the optimal age gain threshold and frame length for maximizing the expected slot-average AoI reduction within the upcoming frame, which provides a design clue for other scenarios. With this clue, for a practical scenario where the coordinator has to estimate the age gains based on its feasible observations, we design a Bayesian method to update individual distributions of the local ages of all the users based on both the channel statuses and the AoI of each user, and propose an algorithm to approximate optimal access parameters based on these distributions. We also evaluate the computational complexity of the proposed practical scheme and discuss how to generalize it to consider random channel errors. Numerical experiments show that our proposed practical scheme outperforms state-of-the-art schemes for a wide range of MPR configurations.

We investigate coding schemes that map source symbols into multisets of an alphabet. Such a formulation of source coding is an alternative approach to the traditional framework and is inspired by an object tracking problem over proximity sensor networks. We define amultiset combinatorial Gray codeas a mulitset code with fixed multiset cardinality that possesses combinatorial Gray code characteristic. For source codes that are organized as a grid, namely an integer lattice, we propose a solution by first constructing a mapping from the grid to the set of symbols, which we referred to as colors. The codes are then defined as the images of rectangular blocks in the grid of fixed dimensions. We refer to the mapping as acolor mappingand the code as acolor multiset code. We propose the idea of product multiset code that enables us to construct codes for high dimensional grids based on 1-dimensional (1D) grids. We provide a detailed analysis of color multiset codes on 1D grids, focusing on codes that require the minimal number of colors. To illustrate the application of such a coding scheme, we consider an object tracking problem on 2D grids and show its efficiency, which comes from exploiting transmission parallelism. Some numerical results are presented to conclude the paper.

We focus on the Age of Information (AoI) performance in a system where each user generates packets periodically to send to a common access point (AP) for status updating. To avoid heavy overhead, we assume that channel sensing, feedback information from the AP, and time synchronization are not available in the system. We adopt a multi-access scheme called the sequence scheme, where each user is assigned a periodic binary sequence to schedule their transmissions. In our previous work, we have thoroughly studied the AoI performance under the sequence scheme when the sequence period,L, is equal to the status generating period,T. However, the case ofT̸=Lis not covered by the previous work. Therefore, in this paper, we aim at analyzing the AoI performance for general values ofTandL, which is more challenging and requires different approaches. We conduct in-depth analysis and develop a mathematical tool based on integer partitions to facilitate the analysis. We derive low-complexity closed-form expressions for two special cases. Based on the obtained analytical results, we propose an optimization method for parameter selection in sequence construction to minimize the average AoI. Finally, we compare our proposed sequence scheme with two commonly used baselines, and show that our proposed scheme outperforms the baselines in terms of AoI performance while consuming less energy.

This paper considers utilizing the knowledge of age gains to reduce the average age of information (AoI) in random access with event-driven periodic updating for the first time. Built on the form of slotted ALOHA, we require each device to determine its age gain threshold and transmission probability in an easily implementable decentralized manner, so that the contention can be limited to devices with age gains as high as possible. For the basic case that each device utilizes its knowledge of age gain of only itself, we provide an analytical modeling by a multi-layer discrete-time Markov chains (DTMCs), where an external DTMC manages the jumps between the beginnings of frames and an internal DTMC manages the evolution during an arbitrary frame, for obtaining optimal fixed access parameters offline. For the enhanced case that each device utilizes its knowledge of age gains of all the devices, we require each device to adjust its access parameters for maximizing the estimated network expected AoI reduction per slot, through maintaining the a posteriori joint probability distribution of local age and age gain of an arbitrary device in a Bayesian manner. Numerical results validate our study and demonstrate the advantage of the proposed schemes over other schemes.

A conflict-avoiding code (CAC) is a deterministic transmission scheme for asynchronous multiple access without feedback. When the number of simultaneously active users is less than or equal tow, a CAC of lengthLwith weightwcan provide a hard guarantee that each active user has at least one successful transmission within every consecutiveLslots. In this paper, we generalize some previously known constructions of constant-weight CACs, and then derive several classes of optimal CACs by the help of Kneser’s Theorem and some techniques in Additive Combinatorics. Another spotlight of this paper is to relax the identical-weight constraint in prior studies to study mixed-weight CACs for the first time, for the purpose of increasing the throughput and reducing the access delay of some potential users with higher priority. As applications of those obtained optimal CACs, we derive some classes of optimal mixed-weight CACs.

A conflict-avoiding code (CAC) is a deterministic transmission scheme for asynchronous multiple access without feedback. When the number of simultaneously active users is less than or equal to$w$, a CAC of length$L$with weight$w$can provide a hard guarantee that each active user has at least one successful transmission within every consecutive$L$slots. To deal with different individual performance requirements in heterogeneous systems, in this paper, we relax the identical-weight constraint in prior studies to study mixed-weight CACs for the first time. We first derive a new class of optimal CACs with constant weights, and then propose a general construction of mixed-weight CACs consisting of three different weights. Finally, we obtain a class of optimal mixed-weight CACs containing two different weights by the help of Kneser's Theorem and some techniques in Additive Combinatorics.

This paper focuses on protocol sequences for age of information (AoI) in a multiple-packet reception (MPR) channel without feedback and synchronization. Unlike traditional probabilistic schemes, protocol-sequences-based schemes allow each user to deterministically decide when to transmit only according to its assigned sequence. When the MPR capability$\gamma=2$, we use a previously known construction to generate user-irrepressible (UI) sequences that are favorable for the AoI improvement. Under this construction, by studying the reverse Hamming cross-correlations of the corresponding sequences, which is more complicated than that in prior studies, we provide an analytical approach for evaluating the AoI for$\gamma=2$. When$\gamma > 2$, we also propose a new construction to produce UI sequences for the AoI improvement. Simulation results show that the proposed schemes outperform slotted ALOHA in terms of average AoI and worst-case AoI for various settings.

We consider the tracking problem of an object that can randomly appear on a line of a fixed length. We want to determine the position of the object and rely on sensors that can detect objects with a predefined range and report that to a remote observer. Sensors are equipped with a transmitter that can transmit at a limited data rate. Once a sensor is triggered, it transmits its own ID to inform. A straightforward protocol is to label each sensor with different ID. However, this would require a large number of unique IDs and many bits to represent. As a result, higher data rate is required. We propose a newly defined protocol using multiset color coding with optimal design or efficiency in reusing a much smaller number of IDs for the whole system. We only require the minimal number of bits for labeling each sensor. We derive the factor of reduction and show its significance. We present some optimal constructions for the required multiset color coding sequence. Besides, we derive the general upper and lower bounds for the maximum length (size) of the system. Numerical examples have also demonstrated the effectiveness and improvement by the proposed new method.

In this correspondence, a corrected version of the upper bound on the number of codewords for a multichannel CAC of weight three is presented.

This paper considers designing an optimal policy for deadline-constrained access in cognitive radio networks, where a secondary user needs to complete a packet transmission over the vacant spectrum within a delivery deadline. To minimize the total access cost, it is desirable to design an optimal opportunistic access policy by utilizing channel dynamics and sensing outcomes. We take non-negligible switching overheads, a state-dependent overtime penalty, and practical switching operations into consideration in the Markov decision process formulation of such an access problem under wide-band sensing. Moreover, we establish the existence of monotone optimal decision rules to reduce the complexity of computing an optimal policy. Simulation results verify our theoretical studies and the cost advantage over other policies.

As the ultra-reliability and low-latency are essential requirements for grant-free access, in this paper we consider Chinese reminder theorem (CRT) based sequences, which are binary and periodic sequences used for deterministic multiple- access without feedback. Some CRT-based sequences are proved to have user-irrepressible (UI) property, which means they are able to provide a hard guarantee that each user has a successful transmission within a fixed period of time. In this paper, we provide a general sufficient condition of constant weight CRT-based sequence sets being UI, show the obtained sufficient condition is necessary in some cases, and characterize the condition when the best access delay performance occurs under CRT structure by numerical studies. We also provide an example to claim that our approach is a potential way to find UI sequences with a shorter common period. Finally, the reliability issue is concerned in the case when the UI property is not guaranteed.

This paper considers a system in which multiple users send periodically generated status information to a common access point (AP) over a collision channel. To avoid high overhead, there is no time synchronization and no feedback information from the AP to indicate whether a transmission is successful or not. The performance metric that we focus on is the age-of-information (AoI), which represents the freshness of the status information received at the AP. For this model, we propose a sequence based MAC scheme in which each user is pre-assigned a periodic sequence to schedule transmissions. This scheme guarantees each user at least one successful packet transmission within a sequence period, in the absence of time synchronization and feedback information from the AP. To the best of our knowledge, this is the first study investigating AoI performance under a sequence based MAC scheme. We derive the closed-form expressions for average AoI, average peak AoI and average age penalty under the sequence based scheduling. Besides, we derive several critical properties of the sequences to optimize the AoI performance. Comparison results show that our proposed sequence scheme outperforms slotted ALOHA and framed ALOHA in various settings.

Designing efficient random access is a vital problem for urgency-constrained packet delivery in uplink Internet of Things (IoT), which has not been investigated in depth so far. In this paper, we focus on unpredictable frame-synchronized traffic, which captures a number of scenarios in IoT communications, and generalize prior studies on this issue by considering a general ALOHA-like protocol, a general single-packet reception (SPR) channel, urgency-dependent throughput (UDT) based on a general urgency function, and the dynamic programming optimality. With a complete knowledge of the number of active users, we use the theory of Markov Decision Process (MDP) to explicitly obtain optimal policies for maximizing the UDT, and prove that a myopic policy is in general optimal. With an incomplete knowledge of the number of active users, we use the theory of Partially Observable MDP (POMDP) to seek optimal policies, and show that a myopic policy is in general not optimal by presenting a counterexample. Because of the prohibitive complexity to obtain optimal or near-optimal policies for this case, we propose two practical policies that utilize the inherent property of our MDP framework and channel model. Simulation results show that both outperform other alternatives. The robustness under relaxed system settings is also examined.

In the development of predictive models, the problem of missing data is a critical issue that traditionally requires a two-step analysis. Data scientists analyze the patterns of missing values, select variables, impute missing values on the basis of domain knowledge, and then train a model. Models typically have their input sizes hardcoded, and have limitations in handling data with high missing rates or changes in available variables. We propose an attention-based neural network combined with a novel real number representation, which requires little work on manually selecting variables, and in which missing data can be overlooked, making imputation unnecessary. In this proposed model, data analysis can be one step, omitting the first step of imputing missing values. The study included data on 32,709 intensive care unit (ICU) admissions and 60 healthcare variables from the Medical Information Mart for Intensive Care (MIMIC)-IV. The proposed algorithm yielded an area under the receiver operating characteristic curve (AUC) of 0.842 (95% CIs: 0.828–0.856) when predicting prolonged length of stay in the ICU, outperforming current approaches using imputation methods. The proposed algorithm can be applied to a range of problems in data science, as it addresses the issue of incomplete data with automatic variable selection.

A multichannel conflict-avoiding code of length$L$and weight$w$for$M$orthogonal channels, denoted by MC-CAC(M, L, w), is used for deterministic multiple-access without feedback. When the number of simultaneously active users is less than or equal to w, an MC-CAC(M, L, w) is able to provide a hard guarantee that each active user has a successful transmission within every consecutive$L$time slots. An upper bound on the number of potential users, or codewords, that an MC-CAC(2, L, 3) can support is derived in this paper. By means of (hooked) Skolem sequences, we propose a new construction that can provide a series of optimal MC-CAC(2, L, 3)s in the sense that the code sizes achieve the obtained upper bounds.

Conflict-avoiding codes (CACs) were introduced by Levenshtein as a single-channel transmission scheme for a multiple-access collision channel without feedback. When the number of simultaneously active source nodes is less than or equal to the weight of a CAC, it is able to provide a hard guarantee that each active source node transmits at least one packet successfully within a fixed time duration, no matter what the relative time offsets between the source nodes are. In this article, we extend CACs to multichannel CACs for providing such a hard guarantee over multiple orthogonal channels. Upper bounds on the number of codewords for multichannel CACs of weights three and four are derived, and constructions that are optimal with respect to these bounds are presented.

The collision channel without feedback (CCw/oFB) introduced by Massey and Mathys, depicts a scenario where multiple users share a communication channel but have arbitrary time offsets, and can never learn these time offsets due to the lack of feedback. This paper considers an extension of the CCw/oFB, which allows the receiver to use successive interference cancellation (SIC) to cancel the interference caused by those collided packets whose contents have been known by the receiver. We derive the zero-packet-loss throughput regions of this model for both the unsynchronized and slot-synchronized cases. Given an arbitrary number of users and a packet alphabet of arbitrary size, it is shown that these two regions coincide, and the outer boundary of this common region is the set of all points with only nonnegative components that add up to one. It is further shown that all points on this outer boundary with only rational components can be achieved without packet loss in the slot-synchronized case. The constructive proofs are based on a joint design of protocol sequences, identification/location algorithm and erasure correcting codes. These findings indicate that the negative impact of the lack of time synchronization on the throughput performance can be removed by the help of SIC.

This paper considers a multiple-access system with multiple-packet reception (MPR) capability γ, i.e., a packet can be successfully received as long as it overlaps with γ -1 or fewer other packets at any instant during its lifetime. To efficiently utilize the MPR capability, this paper generalizes p-persistent carrier-sense multiple access (CSMA) to consider that a user with carrier sensing capability c adopts the transmission probability p, if this user has sensed n ongoing transmissions for n = 0, 1,⋯, c - 1. This paper aims to model the characteristics of such CSMA and to design transmission probabilities for achieving maximum saturation throughput. To this end, we first formulate such CSMA as a parameterized Markov decision process (MDP) and use the long-run average performance to evaluate the saturation throughput. Second, by observing that the exact values of optimal transmission probabilities are in general infeasible to find, we modify this MDP to establish an upper bound on the maximum throughput, and modify this MDP again to propose a heuristic design with near-optimal performance. Simulations with respect to a wide range of configurations are provided to validate our study. The throughput performance under more general models and the robustness of our design are also investigated.

Optical technologies based on Wavelength Division Multiplexing (WDM) are gaining popularity for Data Center Networks (DCNs) due to their technological strengths such as low communication latency, low power consumption, and high link bandwidth. Observe that the BCube networking topology has been widely applied to modular DCNs due to its high scalability and cost effectiveness. Therefore, it is worth investigating optical techniques into BCube DCNs. Routing and Wavelength Assignment (RWA) is a critical problem in optical networks, which can be formulated as an integer programming problem. To gain better insights into RWA solutions, researchers proposed two concepts: the forwarding and optical indices. Consider the all-to-all traffic in an all-optical network, where every host sets up a connection with every other host. The optical index is defined as the minimum number of wavelengths, required to support simultaneous all-to-all communication, under the restriction that each connection is assigned a fixed wavelength. The forwarding index is measured to be the minimum of maximum link loads over all possible all-to-all routings, where we define the maximum link load as the maximum number of paths passing through any link, and define an all-to-all routing as a set of paths specified for all host pairs. In this paper, we study the forwarding and optical indices of an all-optical BCube DCN. First, we compute the forwarding index, which is also a natural lower bound of the optical index. Second, we propose an oblivious RWA scheme, which is further used to derive an upper bound of the optical index. Finally, we derive a tighter upper bound of the optical index by means of the chromatic numbers in Graph Theory.

Protocol sequences are deterministic binary sequences of a common period, which enjoy some special Hamming cross-correlation property by design. In contrast to random or contention-based medium access control schemes, a protocol sequence-based scheme can serve to provide at least a certain number of contention-free packet transmissions within a bounded delay for each asynchronous user in a feedback-free multiple access system. However, all protocol sequence-based schemes in the literature require that all sequence entries are mapped to slots with the same time duration, which produces a relatively low channel utilization. To overcome this inefficiency that is undesirable in delay-constrained wireless sensor networks, building on the idea of combining sequence-based access and carrier sensing, this paper proposes a new protocol sequence-based scheme, called the PS-CS. We derive the theoretical average throughput, average access delay, worst-case delay, and average energy consumption of the PS-CS. It is shown that the PS-CS produces average throughput close to the optimal capacity of p-persistent carrier sense multiple access (CSMA), and enjoys smaller access delay than the optimal p-persistent CSMA. In addition, we study the energy-delay tradeoff, impact of carrier sensing fault and channel error, and how to modify the PS-CS to support real-time downlink for feedback control.

Protocol sequences are periodic zero-one sequences for the scheduling of packet transmissions in a time-slotted channel. A special class of protocol sequences, called shift-invariant sequences, plays a key role in achieving the information-theoretic capacity of the collision channel without feedback. This class of shift-invariant protocol sequences has the property that the pairwise Hamming crosscorrelation functions are invariant to relative delay offsets. However, the common period of shift-invariant sequences grows exponentially as a function of the number of supported users. In this paper, we consider a family of protocol sequences, whose period increases roughly as a quadratic function of the number of the users, and show that it is close to shift-invariant by establishing a bound on the pairwise Hamming crosscorrelation. The construction is based on the Chinese remainder theorem (CRT), and hence the constructed sequences are called CRT sequences. Applications to collision channel allowing successive interference cancellation at the receiver are discussed.

The collision channel without feedback (CCw/oFB) model depicts a scenario in which multiple users share a communication channel with random relative time offsets among their clocks. This paper considers an extension of this model, which allows the receiver to use successive interference cancellation (SIC) to iteratively cancel the interference caused by those collided packets that have been decoded by the receiver. We derive the zero-error capacity region of this channel in the slot-synchronous case, and present a zero-error capacity achieving scheme by joint protocol sequences and channel coding design. It is shown that the negative impact on the zero-error capacity due to a lack of time synchronization can be removed by SIC.

Data centers play an important role in today's Internet development. Research to find scalable architecture and efficient routing algorithms for data center networks has gained popularity. The fat-tree architecture, which is essentially a folded version of a Clos network, has proved to be readily implementable and is scalable. In this paper, we investigate routing on a fat-tree network by deriving its global packing number and by presenting explicit algorithms for the construction of optimal, load-balanced routing solutions. Consider an optical network that employs wavelength division multiplexing in which every user node sets up a connection with every other user node. The global packing number is basically the number of wavelengths required by the network to support such a traffic load, under the restriction that each source-to-destination connection is assigned a wavelength that remains constant in the network. In mathematical terms, consider a bidirectional, simple graph, G and let N ⊆ V(G) be a set of nodes. A path system P of G with respect to N consists of |N|(|N| -1) directed paths, one path to connect each of the source-destination node pairs in N. The global packing number of a path system P, denoted by Φ(G, N, P), is the minimum integer k to guarantee the existence of a mapping φ : P → (1, 2, ..., k), such that φ(P) ≠ φ(P̅) if P and P̅ have common arc(s). The global packing number of (G, N), denoted by Φ(G, N), is defined to be the minimum Φ(G, N, P) among all possible path systems ?. In additional to wavelength division optical networks, this number also carries significance for networks employing time division multiple access. In this paper, we compute by explicit route construction the global packing number of (Tn, N), where Tndenotes the topology of the n-ary fat-tree network, and N is considered to be the set of all edge switches or the set of all supported hosts. We show that the constructed routes are load-balanced and require minimal link capacity at all network links.

Consider a time-slotted communication channel that is shared by K active users transmitting to a single receiver. It is assumed that the receiver has the ability of the multiple-packet reception to correctly receive up to γ (1 ≤ γ <; K) simultaneously transmitted packets. Each user accesses the channel following a deterministic binary sequence, called the protocol sequence, and transmits a packet within a channel slot if the sequence value is equal to one. If the users are not time synchronized, the relative shifts among them can cause significant fluctuation in throughput. If the throughput of each user is independent of relative shifts, then the adopted protocol sequence set is said to be throughput-invariant (TI). If we define worst-case system throughput as the minimal system throughput that can be guaranteed for any set of relative shifts, then TI sequences maximize it and hence are of fundamental interest. This paper investigates TI sequences for γ ≥ 1. Several new results are obtained including throughput value as a function of the duty factors, a lower bound on the sequence period, a construction that achieves the lower bound on the sequence period, and theorems on the intrinsic structure that establish connections with some other families of binary sequences.

Let $$\mathbb{C }$$ be a code of length $$n$$ over an alphabet of $$q$$ letters. The descendant code $$\mathsf{desc}(\mathbb C _0)$$ of $$\mathbb C _0 = \{\mathbf{c}^1, \mathbf{c}^2, \ldots , \mathbf{c}^t\} \subseteq \mathbb{C }$$ is defined to be the set of words $$\mathbf{x} = (x_1, x_2, \ldots ,x_n)$$ such that $$x_i \in \{c^1_i, c^2_i, \ldots , c^t_i\}$$ for all $$i=1, \ldots , n$$ . $$\mathbb{C }$$ is a $$\overline{t}$$ -separable code if for any two distinct $$\mathbb{C }_1, \mathbb{C }_2 \subseteq \mathbb{C }$$ such that $$|\mathbb{C }_1| \le t$$ , $$|\mathbb{C }_2| \le t$$ , we always have $$\mathsf{desc}(\mathbb{C }_1) \ne \mathsf{desc}(\mathbb{C }_2)$$ . The study of separable codes is motivated by questions about multimedia fingerprinting for protecting copyrighted multimedia data. Let $$M(\overline{t},n,q)$$ be the maximal possible size of such a separable code. In this paper, we provide an improved upper bound for $$M(\overline{2},2,q)$$ by a graph theoretical approach, and a new lower bound for $$M(\overline{2},2,q)$$ by deleting suitable points and lines from a projective plane, which coincides with the improved upper bound in some places. This corresponds to the bounds of maximum size of bipartite graphs with girth $$6$$ and a construction of such maximal bipartite graphs.

We consider the slot-synchronized collision channel without feedback, in which K active users all transmit their packets to one sink. It is assumed that the channel has the ability of the multiple-packet reception (MPR), i.e., can accommodate at most γ (1 ≤ γ1. For both design objective, we establish a lower bound on sequence period and prove the lower bound can be achieved by some construction.

A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, we prove that a complete graph on 2m (m \neq 2) vertices K 2m can be properly edge-colored with 2m - 1 colors in such a way that the edges of K 2m can be partitioned into m multicolored isomorphic spanning trees.