On the insensitivity of user distribution in multicell networks under general mobility and session patterns

Wei Bao, Ben Liang

TL;DR

This paper proves that the distribution of users across a mobile network is "insensitive" to complex factors like specific movement paths or correlated stay times. Despite the messiness of real-world mobility, the number of users in each cell behaves like a simple, independent $M/M/\infty$ queueing system that depends only on local average arrival rates and stay durations.

What Problem Does This Paper Address?

Predicting where users will be in a multicell network (like a campus Wi-Fi or a cellular network) is a nightmare for engineers. In theory, a user's location depends on a tangled web of variables: how fast they walk, their specific route, how long their total session lasts, and the fact that the time spent in one cell is often correlated with the time spent in the next.

Most existing mathematical models take a "spherical cow" approach, assuming that everything follows a simple exponential distribution (the "memoryless" property) to make the math work. However, real-world data shows that mobility is anything but memoryless. The authors tackle a fundamental question: Does all this real-world complexity actually change the final "stationary" distribution of users, or can we get away with a much simpler model?

Methods

The authors model the multicell network as a multi-route queueing network with Poisson inputs (meaning new sessions arrive randomly but at a steady average rate).

To prove their "insensitivity" theory, they use a decomposition-composition approach:

  1. Decomposition: They break down complex, arbitrary user routes into a massive collection of "sub-routes" with deterministic (fixed) service times.
  2. Equivalence Proof: They mathematically demonstrate that this complex system of deterministic routes has the exact same stationary distribution as a "reference" network where everything is simple and exponential (a Jackson network).
  3. Composition: They re-aggregate these results to show that the total number of users in any given cell follows a Poisson distribution, regardless of the underlying complexity of the movement patterns.

Datasets

The study validates its theoretical findings using the Dartmouth user mobility traces, a gold-standard dataset in the field.

  • Scope: 17 weeks of SNMP logs from 152 Access Points (APs) and over 5,000 users.
  • Preprocessing: The authors filtered the data to focus on active work hours (9 AM – 5 PM) and handled "trace gaps" (where a user briefly disappears from the log) to ensure a high-quality representation of continuous sessions.
  • Comparison: They compared the real-world user distributions from these traces against their analytical model using Kullback-Leibler (KL) divergence to measure the "distance" between the two.

Key Insights and Ideas

  • The Insensitivity Property: This is the "aha" moment. The steady-state distribution of users is insensitive to the shape of the probability distribution for how long users stay in a cell. It doesn't matter if the stay-times are "heavy-tailed" or highly correlated across cells; only the mean (average) values matter.
  • Independence in a Connected System: Even though users move between cells—which usually implies a dependency—the number of users in Cell A at any given moment is statistically independent of the number of users in Cell B.
  • Jackson Network Equivalence: The entire complex multicell system can be perfectly captured by a simple open Jackson network with $M/M/\infty$ queues. This is a massive win for practitioners because $M/M/\infty$ models are computationally trivial to solve.

Key Results

  • High Accuracy: The analytical model closely matched the Dartmouth traces. For APs that passed a basic Poisson arrival test, the real-world distribution and the theoretical model were nearly identical.
  • Robustness to Non-Poisson Noise: Even when the authors included "invalid" APs (those where arrivals weren't perfectly Poisson, such as in classrooms where everyone arrives at once), the model remained a useful approximation.
  • Spatial Correlation: The authors tested APs that were physically close to each other (within 500m) to see if spatial correlation broke the model. It didn't. The insensitivity held up even when handoff traffic was high.

Limitations and Future Work

  • The Poisson Assumption: The model's biggest dependency is that new session arrivals must form a Poisson process. While this is generally true for large-scale networks, it fails in specific scenarios like a stadium or a lecture hall where hundreds of people connect simultaneously.
  • "Closed" Users: The authors excluded "closed" users—people who stay connected for their entire 8-hour shift. These users don't follow the "arrival-departure" logic of the queueing model and would require a separate "closed network" analysis.
  • Future Applications: Now that we know the distribution is simple, the authors suggest this can be used to simplify complex network optimization problems, such as dynamic bandwidth allocation or energy-efficient AP sleeping patterns.

Summary updated

Abstract

The location of active users is an important factor in the performance analysis of mobile multicell networks, but it is difficult to quantify due to the wide variety of user mobility and session patterns. In particular, the channel holding times in each cell may be arbitrarily distributed and dependent on those in other cells. In this work, we study the stationary distribution of users by modeling the system as a multi-route queueing network with Poisson inputs. We consider arbitrary routing and arbitrary joint probability distributions for the channel holding times in each route. Using a decomposition-composition approach, we show that the user distribution (1) is insensitive to the user movement patterns, (2) is insensitive to general and dependent distributed channel holding times, (3) depends only on the average arrival rate and average channel holding time at each cell, and (4) is completely characterized by an open network with M/M/∞ queues. This result is validated by experiments with the Dartmouth user mobility traces.
BibTeX
@article{bao2013insensitivity,
  author = {Wei Bao and Ben Liang},
  title = {{On the insensitivity of user distribution in multicell networks under general mobility and session patterns}},
  journal = {IEEE Trans. Wireless Communications},
  year = {2013},
  doi = {10.1109/twc.2013.102313.130169},
}
Figure