PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Fundamental Limits of Random Non-orthogonal Multiple Access in Cellular Massive IoT

Mahyar Shirvanimoghaddam, Massimo Condoluci, Mischa Dohler, Sarah Johnson

arXiv:1705.10471v1cs.ITmath.IT

TL;DR

Orthogonal allocation can leave too few radio resources for the large number of M2M devices seeking cellular access. The paper analyzes random NOMA and finds that sub-band choices differ between throughput maximization without delay constraints and arrival-rate maximization under a delay requirement.

Abstract

from arXiv · show

Machine-to-machine (M2M) constitutes the communication paradigm at the basis of Internet of Things (IoT) vision. M2M solutions allow billions of multi-role devices to communicate with each other or with the underlying data transport infrastructure without, or with minimal, human intervention. Current solutions for wireless transmissions originally designed for human-based applications thus require a substantial shift to cope with the capacity issues in managing a huge amount of M2M devices. In this paper, we consider the multiple access techniques as promising solutions to support a large number of devices in cellular systems with limited radio resources. We focus on non-orthogonal multiple access (NOMA) where, with the aim to increase the channel efficiency, the devices share the same radio resources for their data transmission. This has been shown to provide optimal throughput from an information theoretic point of view.We consider a realistic system model and characterise the system performance in terms of throughput and energy efficiency in a NOMA scenario with a random packet arrival model, where we also derive the stability condition for the system to guarantee the performance.

I. INTRODUCTION … II. SYSTEM MODEL

The paper studies cellular M2M access for massive IoT, proposing random NOMA and analyzing its throughput and stability under random packet arrivals. It motivates the approach by radio-resource limits and models devices, channels, and traffic in a single-cell system.

I. INTRODUCTION

  • The study focuses on cellular M2M as infrastructure for IoT connectivity, where devices communicate with one another or data infrastructure with limited or no human intervention.Cellular systems are presented as promising for M2M because of their coverage, mobility, scalability, security, and existing infrastructure.Source: §I · p. 2

A. Background and Motivations

  • Orthogonal allocation can bottleneck cellular M2M when many devices seek limited radio resources, motivating access techniques that let multiple devices share them.NOMA permits overlapping transmissions and uses successive interference cancellation at the base station.Source: A. Background and Motivations · pp. 2–3
  • Prior massive-IoT NOMA studies rely on transmitter and receiver channel knowledge, while system-wide evaluation of random traffic and randomly deployed uplink users is lacking.The paper addresses this gap by evaluating random NOMA and deriving stability and maximum throughput conditions.Source: A. Background and Motivations · p. 4

B. Contributions and Paper Organization

  • In random NOMA, each transmitting device randomly selects a subband and sends an ID-encoded packet; the base station uses rateless-code-enabled SIC to decode overlapping transmissions.Source: B. Contributions and Paper Organization · pp. 4–5
  • Without delay constraints, 2 or 3 subbands maximize random NOMA throughput; under a strict delay constraint, higher throughput is achieved when the whole bandwidth is used.The paper also derives a necessary stability condition and the maximum supportable arrival rate for both delay scenarios.Source: B. Contributions and Paper Organization · p. 5

II. SYSTEM MODEL

  • The system model places MTC devices around a single-cell base station according to a homogeneous Poisson point process, between inner and outer radii Ri and Ro.The base station is at the cell center.Source: §II · p. 5

NOTATION SUMMARY

  • Packet requests arrive at the base station as a Poisson process with mean λ packets per second; devices send L-bit messages including unique IDs in slotted transmissions.Each device requests transmission only at the start of a time slot.Source: NOTATION SUMMARY · p. 8

III. THE PROPOSED RANDOM NOMA STRATEGY FOR M2M COMMUNICATIONS · IV. ANALYSIS OF THE PROPOSED SCHEME · A. Time slot duration

The proposed random NOMA strategy assigns active devices to shared sub-bands and uses seed-based Raptor coding with successive interference cancellation. Its analysis models random slot duration and collision-driven retransmissions to derive throughput and stability, with duration governed by the most heavily loaded sub-band.

III. THE PROPOSED RANDOM NOMA STRATEGY FOR M2M COMMUNICATIONS

  • Devices randomly choose a sub-band, estimate its channel from the BS pilot, select a seed, and transmit their unique-ID messages using seed-generated Raptor codes.The BS decodes by successive interference cancellation, trying seeds in order on each sub-band.Source: §III · pp. 8–9
  • A limited seed pool lets the BS retry SIC across at most Ms seeds per sub-band, decoding devices with non-colliding seeds while controlling collision probability and receiver complexity.Devices sharing a seed on the same sub-band use identical code structures and cannot be distinguished; assigning every device a unique seed would require impractical exhaustive SIC over the many possible devices.Source: §III · pp. 9–10

IV. ANALYSIS OF THE PROPOSED SCHEME

  • The analysis seeks throughput and the maximum arrival rate that keeps the system stable, accounting for random slot duration and collision-driven retransmissions while omitting pilot and guard times.Source: §IV · p. 10

A. Time slot duration

  • The time slot duration is set by the sub-band with the most active devices, whose lower achievable rate determines the slot length.The number of active devices per sub-band is random, so the analysis characterizes the distribution of the maximum occupancy and average slot duration.Source: A. Time slot duration · pp. 10–11
  • Rateless codes let devices continue transmitting until the BS has enough coded symbols for a realized rate below the achievable common rate, enabling decoding above the corresponding threshold SNR.Source: A. Time slot duration · p. 11
  • The analysis assumes equal message lengths; differing lengths can be handled by grouping sub-bands and assigning each length group to devices with that message length.The proposed extension uses ⌊Ns/Nℓ⌋ sub-band groups, with duration found using approximations.Source: A. Time slot duration · pp. 11–12
  • The scheme uses a common rate equal to the minimum rate across devices and treats them alike; this is suboptimal, but avoids channel-informed SIC optimization suited to delay-tolerant, low-rate IoT traffic.A suitable SIC order could improve individual rates, but requires channel knowledge for all devices at the BS and complex optimization.Source: A. Time slot duration · p. 12

B. Collision probability

A device collides when another selects the same preamble/seed configuration, making their transmissions indistinguishable to the base station. With MsNs configurations, the collision probability is 1 − (1 − 1/(MsNs))^(n−1), and the section uses this probability to specify a minimum seed requirement.

B. Collision probability

  • The base station cannot detect devices that use the same seed on the same sub-band because their transmitted codewords have no structural difference.Such a collision occurs when devices select the same configuration.Source: B. Collision probability · p. 12
  • The collision probability is 1 − (1 − 1/(MsNs))^(n−1), since a device avoids collision only when all other n−1 devices choose different configurations.Each device randomly selects one of MsNs preamble/seed configurations.Source: B. Collision probability · pp. 12–13
  • The system’s minimum seed requirement is set to keep the collision probability at most Pc(n), with a further simplification given for Pc(n) → 0.The supplied passages do not state the resulting minimum-seed formula.Source: B. Collision probability · p. 13

C. Stability Condition without Delay Constraint · 1) Weak Stability Condition: · 2) Strong Stability Condition:

The section defines stability by requiring the steady-state active-device count not to grow from one time slot to the next, then derives maximum-arrival-rate conditions under weak and strong stability.

C. Stability Condition without Delay Constraint

  • Stability requires the next-slot active-device count, including collisions and newly generated packets, to be no greater than the previous-slot count, preventing growth toward saturation.The condition is framed for steady state, and the slot count is random.Source: C. Stability Condition without Delay… · p. 13

1) Weak Stability Condition:

  • Weak stability is defined using the steady-state average number of devices the system can support, for a system with initial backlog n1.Source: 1) Weak Stability Condition · p. 13
  • The active-device count ni includes devices active in slot i and devices that collided in the previous slot and reattempt transmission in slot i.Source: 1) Weak Stability Condition · p. 13
  • Lemma 2 gives the maximum arrival rate the base station can support under weak stability; the supplied passage does not include its formula.Source: 1) Weak Stability Condition · p. 13

2) Strong Stability Condition:

D. Stability Condition with QoS Guarantee

With a fixed slot duration d_p, the scheme is equivalent to dynamic-slot random NOMA under a delay constraint. The section derives weak and strong stability conditions to characterize supported backlog and packet-arrival limits.

D. Stability Condition with QoS Guarantee

  • The analysis fixes slot duration at d_p, requiring devices to be decoded within d_p and to transmit in only one slot, matching dynamic-slot random NOMA under a delay constraint.This modification addresses the usual fixed-duration slot model in wireless systems.Source: D. Stability Condition with QoS… · p. 14
  • The weak stability condition specifies the maximum initial backlog and packet arrival rate that satisfy the delay requirement d_p.The passages state these limits but omit their equations.Source: D. Stability Condition with QoS… · p. 16
  • The strong stability condition likewise specifies maximum initial backlog and packet arrival rate; Fig. 3 plots maximum arrival rate versus initial backlog for weak and strong stability across different M_s values.The plotted setup uses N_s = 20, W = 1 MHz, L = 1000, and threshold probability ε = 0.01 for strong stability.Source: D. Stability Condition with QoS… · p. 16, Figure 3 · p. 16

V. NUMERICAL RESULTS · VI. SYSTEM OPTIMIZATION · A. Number of sub-bands

The numerical results show that seeds and sub-band choices shape supported arrivals and backlog, while optimization favors few sub-bands without a delay constraint and one sub-band with a delay constraint. The section also describes how seed-pool size trades lower collision probability against greater SIC complexity.

V. NUMERICAL RESULTS

  • With Ns = 20, L = 1000 bits, and W = 1 MHz, increasing the number of seeds lets the system support more devices by reducing collisions and retransmissions.The passage discusses different numbers of seeds, Ms, and explains that fewer devices reattempt in the following time slot when collision probability decreases.Source: §V · pp. 16–17
  • With increasing sub-band count, the maximum arrival rate decreases while the system can support a larger initial backlog.The collision probability falls, but narrower sub-bands lengthen slots because devices transmit at lower achievable rates.Source: §V · p. 17, Figure 4 · p. 17
  • As tolerable delay increases, the supported arrival rate increases and approaches the no-delay maximum; short delays support fewer devices.For Ns = 100, the small bandwidth per sub-band leaves a large gap between arrival rates supported with and without delay constraints.Source: §V · p. 17, Figure 5 · p. 18

VI. SYSTEM OPTIMIZATION · A. Number of sub-bands

  • The number of seeds and sub-bands determine collision probability and maximum achievable rate, so the base station can choose them to maximize throughput or meet device QoS requirements.Increasing the seed pool lowers collision probability but makes SIC more complex; adapting the pool to incoming traffic is proposed as a way to fix collision probability.Source: A. Number of sub-bands · p. 18
  • Without a delay constraint, the maximum packet arrival rate is achieved with 3 or 4 sub-bands; with a delay constraint, it is achieved using one sub-band.The reported no-delay optimum holds for different numbers of seeds; under delay constraints, dividing the bandwidth into several sub-bands degrades supported arrival rate.Source: A. Number of sub-bands · pp. 18–19, Figure 6 · p. 19, Figure 7 · p. 19
  • Without a delay constraint, using only a few sub-bands is sufficient because increasing their number narrows each sub-band and reduces its maximum achievable rate.The reported supported-arrival-rate maximum occurs at 3 or 4 sub-bands for different numbers of seeds.Source: A. Number of sub-bands · pp. 18–19, Figure 6 · p. 19
  • To meet a given delay requirement while supporting more devices, the section recommends using the whole bandwidth as one sub-band and controlling collisions with a larger seed pool.The one-sub-band result applies to each given delay constraint considered.Source: A. Number of sub-bands · p. 19, Figure 7 · p. 19

B. MTC Device Fairness · VII. PRACTICAL CONSIDERATIONS OF MASSIVE NOMA FOR M2M COMMUNICATIONS

The fairness discussion allocates bandwidth by cell partition to address distance-related energy differences while maintaining equal average throughput and energy consumption. The practical-considerations section frames three challenges to deploying massive NOMA for M2M and proposes solutions.

B. MTC Device Fairness

  • Devices farther from the base station must transmit at higher power to match received power, so distance-based bandwidth allocation is proposed to equalize throughput and energy consumption.The proposed approach aims to let distant and nearby devices achieve the same throughput with the same energy use.Source: B. MTC Device Fairness · p. 20
  • The cell is divided into equal-area partitions, and devices identify their partition using pilot-based channel estimates and broadcast received-power thresholds.Equal partition areas yield the same average number of randomly distributed devices in each partition.Source: B. MTC Device Fairness · p. 20
  • Each partition uses its own subband, with bandwidth Wi and received SNR µi; the non-uniform allocation supports energy-fair multiple access.This differs from the original random NOMA strategy, where devices choose among equal-bandwidth subbands and have the same received power.Source: B. MTC Device Fairness · pp. 20–21
  • With equal average slot duration and energy consumption as fairness constraints, Lemma 4 specifies the bandwidth allocation for each subband.Wi denotes the bandwidth of subband i, and W is the total available bandwidth.Source: B. MTC Device Fairness · p. 21
  • As device numbers rise, bandwidth is allocated more evenly across subbands; at relatively low loads, more goes to devices farther from the base station.The paper notes that proper load estimation is needed to allocate bandwidth fairly in energy consumption.Source: B. MTC Device Fairness · p. 21, Figure 9 · p. 22

VII. PRACTICAL CONSIDERATIONS OF MASSIVE NOMA FOR M2M COMMUNICATIONS

  • The practical-considerations section identifies three main challenges to using massive NOMA for M2M and proposes solutions toward a more practical IoT system.It notes that NOMA can improve spectrum efficiency and system capacity, while practical deployment remains challenging.Source: §VII · p. 21

A. System Overload … VIII. CONCLUSIONS

The paper examines random NOMA for massive IoT and shows that optimal bandwidth allocation depends on delay and fairness requirements. It also discusses overload control, SIC delay, and performance relative to NB-IoT.

A. System Overload

  • When arrivals exceed the supportable number of devices, the base station can increase the number of seeds or defer some users’ transmissions to spread traffic over time.Back-off and access barring can manage overload; this does not affect systems without delay constraints but reduces throughput under strict delay constraints.Source: A. System Overload · p. 22

B. Optimal Power Allocation and Throughput

  • Because devices transmit ratelessly without knowing load, they use a common Rmin, preventing optimal throughput when the base station cannot identify devices and select their powers and rates.The passage states that the SIC order is not relevant under this shared-rate operation.Source: B. Optimal Power Allocation and… · p. 23
  • Reaching NOMA’s full potential requires base-station-selected received powers, but device identification and channel estimation add overhead and delay, so the proposal removes identification and optimizes bandwidth allocation.The paper describes device identification as impractical for massive IoT’s small messages and large device counts.Source: B. Optimal Power Allocation and… · p. 23

C. Delay Imposed from the SIC Process

  • SIC decodes devices sequentially by highest SINR, imposing delay; parallel decoding or iterative parallel interference cancellation can decode and cancel multiple devices simultaneously.Devices can be grouped by delay requirements using specific random seeds, with parallel IC applied from high-priority, low-latency groups to delay-tolerant groups.Source: C. Delay Imposed from the SIC Process · pp. 23–24, Figure 10 · p. 24

D. A brief comparison between Narrow-band IoT and Masive NOMA

  • NB-IoT targets low-data-rate devices with relaxed delays and supports up to 50,000 devices per cell at about 6 packets/s, but its two-step access limits capacity and strict-delay support.The passage gives NB-IoT rates of about 250 kbps downlink and 20 kbps uplink, with a 180 kHz bandwidth requirement.Source: D. A brief comparison between… · p. 24
  • With 180 kHz divided into twelve 15 kHz sub-bands, NOMA supports 100 packets/s at 100 ms delay and 180 packets/s at 1 s, versus NB-IoT’s around 18 packets/s.The comparison indicates NOMA can support delay-sensitive applications; NB-IoT uplink latency can reach about 2.8 s for devices with very poor coverage.Source: D. A brief comparison between… · pp. 24–25

VIII. CONCLUSIONS

  • Without delay constraints, 3 or 4 sub-bands maximize supported packet arrivals; with delay constraints, one sub-band supports large arrivals while satisfying the delay requirement.The study derives stability conditions and maximum arrival rates with and without QoS guarantees, and optimizes parameters for throughput, delay, and fairness in throughput and energy consumption.Source: §VIII · p. 25

APPENDIX A PROOF OF LEMMA 1

The appendix derives the distribution of the maximum number of devices assigned to any sub-band, using occupancy approximations for randomly selected sub-bands.

APPENDIX A PROOF OF LEMMA 1

  • q(c, n) denotes the probability that the maximum occupancy across sub-bands is c when n devices are active.The proof uses k_i for the number of devices selecting sub-band i.Source: Appendix A · p. 25
  • For sufficiently large n and N_s, each sub-band occupancy is approximated by a binomial distribution and then by a normal distribution.The binomial approximation relies on devices independently selecting uniformly among the available sub-bands.Source: Appendix A · pp. 25–26
  • The proof derives the cumulative and probability mass functions of the maximum occupancy across all available sub-bands, conditional on n active devices.The cumulative event is that every sub-band contains at most ℓ devices.Source: Appendix A · p. 26

APPENDIX B PROOF OF LEMMA 2

The proof derives the next-slot active-device probability by combining collided packets from the current slot with newly generated packets. It uses independent collision and arrival counts, with normal approximations under the stated conditions.

APPENDIX B PROOF OF LEMMA 2

  • For sufficiently large device counts, collided packets follow a binomial model with success probability Pc(n_i) and are approximated by a normal distribution with mean n_iPc(n_i) and variance n_i(1−Pc(n_i)).Source: Appendix B · pp. 26–27
  • Newly generated packets are modeled as Poisson with mean λ packets/sec and may be approximated by a normal distribution when T(n_i) is sufficiently large.Source: Appendix B · p. 27
  • The next-slot probability is obtained by summing over j collided packets and n_(i+1)−j newly generated packets, whose counts are treated as mutually independent.The proof multiplies the corresponding probabilities for each j before summing.Source: Appendix B · pp. 26–27

APPENDIX C PROOF OF LEMMA 3

The appendix derives the strong stability condition and obtains the maximum arrival rate by solving an inequality for λ and maximizing over n.

APPENDIX C PROOF OF LEMMA 3

  • The strong stability condition is derived using (39) and then rewritten using (40).Source: Appendix C · p. 27
  • Solving the inequality for λ yields (17), and maximizing over n gives the maximum arrival rate in (16).Source: Appendix C · p. 28

APPENDIX D PROOF OF LEMMA 4

Appendix D proves Lemma 4 by deriving sub-band duration and energy conditions for randomly partitioned devices. It uses a small-μᵢ approximation to relate the sub-bands’ average durations, transmit powers, energy consumption, and bandwidths.

APPENDIX D PROOF OF LEMMA 4

  • The proof models the number of active devices assigned to a cell partition using a binomial distribution with success probability 1/Nₛ.It identifies the expected number assigned to a partition as n/Nₛ.Source: Appendix D · p. 28
  • The proof derives the average duration for devices transmitting in the ith sub-band and uses it to require equal average durations across all sub-bands.The derivation refers to the message-delivery time in (7) and applies a small-μᵢ approximation.Source: Appendix D · pp. 28–29
  • For sufficiently small μᵢ, the proof approximates the average sub-band duration using the first-order Maclaurin expansion of ln(1 + x).The resulting duration approximation relies on the assumption that the μᵢ values are very small.Source: Appendix D · pp. 28–29
  • Equal average energy across devices requires equal average sub-band durations and transmit powers chosen to achieve each sub-band’s SNR μᵢ.The proof derives the average transmit power for the ith sub-band and imposes equal energy consumption across cell partitions.Source: Appendix D · p. 29
  • The bandwidth of the ith sub-band is calculated from the preceding equal-energy relation.The proof states that it obtains the bandwidth using the relation established in (50).Source: Appendix D · p. 29
Loading 1705.10471v1…