In this paper, we develop a gneral framework for studying distributed online frequency assignment in cellular networks. The problem can be abstracted as a multicoloring problem on a node-weighted graph whose weights change over time. The graph, with nodes corresponding to network cells, is usually modeled as a subgraph of the triangular lattice andthe instantaneous weitht at a nose models the number of calls requiring service at the corresponding network cell. In this setting, we present several distributed online algorithms for this problem and prove bounds on their ocmpetitive ratios. Specifically, we demonstrate a series of such algorithms that utilize information about increasingly larger neighborhoods around nodes, and thereby acheveprogressively better competitive ratios. We also exhibit lower boudns on the competitive ratios of some natural classes of distributed online algorithms ofr the problem, in some cases, our bounds are shown to be optimal.
展开▼
