In light of current and projected demands of wireless communications, techniques are needed to make more efficient use of the wireless spectrum. In one class of applications, certain bands of the wireless spectrum are not licensed to specific users, but instead are reserved for users that compete for channel allocation on a dynamic basis; this dynamic spectrum allocation is also envisioned for cognitive radio networks in which unlicensed users compete for bandwidth within the temporarily unused channels, or the white spaces of active channels, of licensed users. Reconfigurability is a key property of the opportunistic users: Their channels may consist of a number of disjoint sub-bands allocated to them dynamically; a channel is not simply a fixed, single continuous band of frequencies. Exploiting this property leads to new and intriguing fragmentation issues. We study a baseline mathematical model of these issues and arrive at a number of important insights that need to be borne in mind in system design. The model and its analysis also applies in the domain of computer resource allocation, viz., linked-list implementations of dynamic storage allocation, in which the spectrum becomes a storage unit and bandwidth requests become requests for blocks of storage. We adopt the most basic model in which a spectrum is shared by unlicensed users only, each characterized by a desired total bandwidth and the duration of a time interval over which it is needed. As users come and go, gaps of available bandwidth develop randomly in both size and position. When allocating bandwidth to a user's channel, the spectrum is searched for gaps to be allocated to the channel until the full requested bandwidth has been provided. Fundamental questions that we address include: Is the number of fragments (sub-bands) into which a user's channel is divided a stable process (e.g., can fragmentation increase indefinitely?) Is there a relation between the numbers of users and gaps similar to the 50% Rule of dynamic storage allocation? Are there normal limit laws similar to those of other fragmentation problems? Rigorous proofs of stability provide new, hard-won contributions to theoretical foundations of fragmentation. A rigorous proof of a 50% Limit Law makes a further such contribution. Answers to the many other questions posed in this thesis are observed experimentally; a number of the results are rather surprising at first glance, but plausible derivations are given for each. The thesis concludes with a number of intriguing open problems dealing with more general assumptions, problems that can be profitably addressed by experimental studies using the simulation tool of this thesis.
展开▼
