Inertia-based Distributed Channel Allocation

摘要

We consider distributed channel allocation on planar conflict graphs describing interference couplings of wireless networks. We observe that the corresponding graph colouring problem is riddled by topologic defects that are annihilated when they meet the network boundary, or possibly another defect. Greedy algorithms lead to random walk -like motion of these defects. To increase the probability for them to meet the network boundary, we impose rules that add inertia to the motion of these defects. These rules give rise to a self-organizing resource allocation algorithm on the network which is cognicient of the motion of the defects. The example case of four-colouring a regular triangular lattice is considered. The median convergence time is found to be less than quadratic in the network size.