Abstract:

We consider the problem of monitoring the interference among a collection of entities moving with bounded speed in $d$-dimensional Euclidean space. Uncertainty in entity locations due to unmonitored and unpredictable motion gives rise to a space of possible entity configurations at each moment in time, with possibly very different interference properties. We define different measures of what we call the interference potential of such spaces to describe the interference that might actually occur.

We study the extent to which restricted monitoring frequency impacts interference potential, through the analysis of a clairvoyant scheme (one that knows the trajectories of all entities) subject to the same monitoring frequency restriction.  This forms a benchmark for the analysis of uninformed schemes. In this framework, we describe and analyse an adaptive monitoring scheme for minimizing interference potential over time that is competitive (to within a constant factor) with any other scheme (in particular, a clairvoyant scheme) over modest sized time intervals.

As a natural application, imagine that the entities are transmission sources, with associated broadcast ranges, moving in three dimensions. Two such entities, transmitting on the same channel, interfere if their broadcast ranges intersect.  Uncertainty in the location of a transmission source effectively expands its broadcast range to a potential broadcast range. The chromatic number of the intersection graph of these potential broadcast ranges, one of our interference potential measures, gives the minimum number of broadcast channels required to avoid interference. Our scheme provides an adaptive, locally updated, channel assignment scheme that is competitive over time, in terms of the number of broadcast channels used with a fixed monitoring frequency, with any other such scheme.

---