WIAS Preprint No. 2392, (2017)

A Gibbsian model for message routing in highly dense multi-hop networks


  • König, Wolfgang
  • Tóbiás, András

2010 Mathematics Subject Classification

  • 60F10 60G55 60K30 82B21 90B15


  • Gibbs distribution of trajectories, high-density limit, large deviations, empirical measure, variational formula, multihop ad-hoc network, signal-to-interference ratio, message trajectories, congestion




We investigate a probabilistic model for routing in relay-augmented multihop ad-hoc communication networks, where each user sends one message to the base station. Given the (random) user locations, we weigh the family of random, uniformly distributed message trajectories by an exponential probability weight, favouring trajectories with low interference (measured in terms of signal-to-interference ratio) and trajectory families with little congestion (measured by how many pairs of hops use the same relay). Under the resulting Gibbs measure, the system targets the best compromise between entropy, interference and congestion for a common welfare, instead of a selfish optimization. We describe the joint routing strategy in terms of the empirical measure of all message trajectories. In the limit of high spatial density of users, we derive the limiting free energy and analyze the optimal strategy, given as the minimizer(s) of a characteristic variational formula. Interestingly, expressing the congestion term requires introducing an additional empirical measure.

Download Documents