Constant Delivery Delay Protocol Sequences for the Collision Channel Without Feedback

Lou Salaün, Chung Shue Chen, Yi Chen, Wing Shing Wong

TL;DR

This paper introduces "Constant Individual Delivery Delay" (CIDD) sequences, a new type of protocol sequence for wireless communication systems that guarantees a fixed time interval between successful packet transmissions for each user, even without feedback. While these sequences offer improved reliability and predictable performance, they come at the cost of reduced overall throughput compared to existing "shift-invariant" (SI) sequences, especially as the number of users increases.

What Problem Does This Paper Address?

In wireless communication systems, especially those with limited resources like sensor networks or ad-hoc mobile networks, multiple devices need to share a common channel. When multiple devices transmit simultaneously, their signals collide, and the data is lost. Traditional methods like TDMA offer collision-free communication but require strict synchronization, which is often impractical. Contention-based protocols like CSMA/CA are more flexible but rely on feedback mechanisms that can be resource-intensive.

This paper focuses on a "collision channel without feedback" model. In this scenario, devices cannot know if their transmissions have collided, and they cannot synchronize their transmissions perfectly. This leads to unavoidable collisions and unpredictable data delivery. The authors build upon the concept of "protocol sequences," which are pre-defined transmission schedules for each device, to manage channel access. Existing "shift-invariant" (SI) sequences ensure that each user's throughput remains constant regardless of timing differences (offsets) between users. However, SI sequences can have very long lengths, growing exponentially with the number of users, and their throughput might not be optimal. The problem this paper addresses is how to achieve predictable and stable packet delivery for each individual user in such a challenging environment, going beyond just constant throughput.

Methods

The core contribution of this paper is the introduction and characterization of Constant Individual Delivery Delay (CIDD) sequences. These sequences are a specific type of protocol sequence designed for the collision channel without feedback.

The authors define CIDD sequences by the property that the time interval between any two successfully delivered packets for a given user is constant. This is a stronger condition than the "shift-invariant" (SI) property, which only guarantees a constant throughput.

The paper then proceeds to:

  • Define and analyze properties of SI sequences: They leverage existing theorems on SI sequences regarding throughput and period length.
  • Introduce CIDD sequences: They formally define what it means for a sequence set to have CIDD.
  • Characterize CIDD sequences: They prove that CIDD sequences are a very specific subset of SI sequences. Specifically, for a system with $K$ users, CIDD sequences require each user to have a duty factor of $1/2$ and the sequence length (period) to be $2K$.
  • Prove equivalence with Uniform Individual Delay (UID) sequences: They introduce another class of sequences called Uniform Individual Delay (UID) sequences and demonstrate that they are equivalent to CIDD sequences. This equivalence is established by analyzing the distribution of individual delivery delays over all possible timing offsets.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on the properties of protocol sequences rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Beyond constant throughput: Constant delivery delay: The paper highlights that while constant throughput (SI sequences) is desirable, guaranteeing a fixed time between successful transmissions for each individual user (CIDD) offers a more robust form of predictable Quality of Service (QoS).
  • CIDD sequences are a highly constrained subset of SI sequences: The characterization theorem reveals that CIDD sequences are not arbitrary. For $K$ users, they must have a duty factor of $1/2$ for each user, and the sequence length must be $2K$. This implies that CIDD sequences are only possible for a limited number of users and specific configurations.
  • Trade-off between reliability and throughput: The paper clearly illustrates a fundamental trade-off. CIDD sequences provide excellent reliability and predictable delivery timing, but their throughput is significantly lower than optimal SI sequences, especially as the number of users ($K$) increases. This is visualized in Figure 1, showing a substantial "performance loss."
  • Equivalence of CIDD and UID: The demonstration that CIDD and UID sequences are equivalent is a significant theoretical result, suggesting that the property of having a uniform distribution of delivery delays across all offsets is fundamentally linked to the constant individual delivery delay property.

Key Results

  • Characterization of CIDD sequences: The paper proves that a set of $K$ sequences has CIDD if and only if it is SI, has a sequence length $L=2K$, and each user's duty factor is $f_i = 1/2$.
  • Throughput vs. Number of Users: For $K$ users, CIDD sequences achieve a throughput of $1/(2K)$ for each user. This is optimal only for $K=2$. For $K>2$, the performance loss compared to optimal SI sequences grows exponentially with $K$.
  • Minimal Sequence Length for SI: CIDD sequences achieve the minimal possible sequence length for SI sequences, which is $2K$.
  • Equivalence Proof: The paper provides a formal proof that Uniform Individual Delay (UID) sequences are equivalent to CIDD sequences.

Limitations and Future Work

  • Throughput Limitation: The most significant limitation is the reduced throughput of CIDD sequences, especially for a large number of users. The paper acknowledges this and suggests that reducing the number of users communicating on the same channel could mitigate this issue.
  • Construction of CIDD Instances: The paper focuses on characterizing CIDD sequences rather than explicitly constructing them. It mentions that existing methods for generating minimal period SI sequences can be used to generate CIDD instances when duty factors are set to $1/2$.
  • Application to Network Topologies: The authors propose exploring the application of CIDD sequences in structured networks, such as graph networks. They suggest that the chromatic number of the graph could determine the number of sequences needed, potentially reducing the performance drop. For example, for planar graphs (chromatic number $\leq 4$), the performance drop would be approximately $41\%$.
  • Practical Implementation: While the paper provides theoretical foundations, practical implementation details and performance evaluations in real-world scenarios are not discussed.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{salaun2016constant,
  author = {Lou Salaün and Chung Shue Chen and Yi Chen and Wing Shing Wong},
  title = {{Constant Delivery Delay Protocol Sequences for the Collision Channel Without Feedback}},
  booktitle = {HAL},
  year = {2016},
}

Loading related content...

Figure