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.

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.

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.

A total-weighting of a graph $G=(V,E)$ is a mapping $f$ which assigns to each element $y\in V\cup E$ a real number $f(y)$ as the weight of $y$. A total-weighting $f$ of $G$ is proper if the coloring $\phi_{f}$ of the vertices of $G$ defined as $\phi_{f}(v)=f(v)+\sum_{e\in E(v)}f(e)$ is a proper coloring of $G$, i.e., $\phi_{f}(v)\ne\phi_{f}(u)$ for any edge $uv$, where $E(v)$ is the set of edges of $G$ incident to $v$. For positive integers $k$ and $k'$, a graph $G$ is called $(k,k')$-total-weight-choosable if whenever each vertex $v$ is given $k$ permissible weights and each edge $e$ is given $k'$ permissible weights, there is a proper total-weighting $f$ of $G$ which uses only permissible weights on each element $y\in V\cup E$. It is known that every tree is (2,2)-total-weight-choosable and every tree other than $K_2$ is (1,3)-total-weight-choosable. However, the problem of determining which trees are (1,2)-total-weight-choosable remained open. This paper solves this problem and characterizes all (1,2)-total-weight-choosable trees. Based on this characterization, we give an algorithm that determines in linear time whether a given tree is (1,2)-total-weight-choosable.