Continuous-Model Communication Complexity With Application in Distributed Resource Allocation in Wireless Ad Hoc Networks

Distributed resource allocation is an important problem in wireless ad hoc networks, in which there is no centralized scheduler and the resource allocation is carried out in a distributed way. Information exchange in the distributed resource allocation incurs overhead since it does not convey data information. The communication complexity, defined as the minimum number of exchanged messages needed for computing a common function with distributed inputs, is studied and the resource allocation is considered to be the procedure of computing a common function whose inputs are the parameters of multiple communication links.