Resource allocation problems in communication and control systems

Resource allocation in control and communication systems constitutes the distribution of (finite) system resources in a way that achieves maximum system functionality and or cost effectiveness. Specific resource allocation problems in subband coding, Discrete Multi-tone modulation based systems and autonomous multi-agent control are addressed in this thesis.

In subband coding, the number of bits used (out of a target bit budget) to code a sub- band signal are allocated in a way that minimizes the coding distortion. In Discrete Multi-tone modulation based systems, high bit rate streams are split into several parallel lower rate streams. These individual data streams are transmitted over different subchannels. Given a target bit rate, the goal of resource allocation is to distribute the bits among the different subchannels such that the total transmitted power is minimized. The last problem is achieving stable control of a fleet of autonomous agents by utilizing the available communication resources (such as transmitted Power and bandwidth) as effectively as possible.

We present an efficient bit loading algorithm that applies to both subband coding and single-user multicarrier communication system. The goal is to effect an optimal distribution of B bits among N subchannels (subbands) to achieve a minimum transmitted power (distortion error variance) for multicarrier (subband coding) systems. All the algorithms in literature, except a few (which provides a suboptimal solution), have run times that increase with B. By contrast, we provide an algorithm that solves the aforementioned problems exactly and with a complexity (given by O(N log(N)),) which is dependent only on N.

Bit loading in multi-user multicarrier systems not only involves the distribution of bit rates across the subchannels but also the assignment of these subchannels to different users. The motivation for studying suboptimal bit allocation is underscored by implicit and explicit claims made in some of the papers which present suboptimal bit loading algorithms, without a formal proof, that the underlying problem is NP-hard. Consequently, for no other reason than the sake of completeness, we present a proof for NP-hardness of the multiuser multicarrier bit loading problem, thereby formally justifying the search for suboptimal solutions.

There has been a growing interest in the area of cooperative control of networks of mobile autonomous agents. Applications for such a set up include organization of large sensor networks, air traffic control, achieving and maintaining formations of unmanned vehicles operating under- water, air traffic control etc. As in Abel et al, our goal is to devise control laws that, require minimal information exchange between the agents and minimal knowledge on the part of each agent of the overall formation objective, are fault tolerant, scalable, and easily reconfigurable in the face of the loss or arrival of an agent, and the loss of a communication link.

A major drawback of the control law proposed in Abel et al is that it assumes all agents can exchange information at will. This is fine if agents acquire each others state information through straightforward sensing. If however, state information is exchanged through broadcast commu- nication, this assumption is highly unrealistic. By modifying the control law presented in Abel et al, we devise a scheme that allows for a sharing of the resource, which is the communication channel, but also achieves the desired formation stably. Accordingly we modify the control law presented in [23] to be compatible with networks constrained by MAC protocols.