Spectrum Sharing for Multi-Hop Networking with Cognitive Radios

Cognitive radio (CR) capitalizes advances in signal processing and radio technology and is capable of reconfiguring RF and switching to desired frequency bands. It is a frequency-agile data communication device that is vastly more powerful than recently proposed multi-channel multi-radio (MC-MR) technology. In this paper, we investigate the important problem of multi-hop networking with CR nodes. For such a network, each node has a pool of frequency bands (typically of unequal size) that can be used for communication. The potential difference in the bandwidth among the available frequency bands prompts the need to further divide these bands into sub-bands for optimal spectrum sharing. We characterize the behavior and constraints for such a multi-hop CR network from multiple layers, including modeling of spectrum sharing and sub-band division, scheduling and interference constraints, and flow routing. We develop a mathematical formulation with the objective of minimizing the required network-wide radio spectrum resource for a set of user sessions. Since the formulated model is a mixed-integer non-linear program (MINLP), which is NP-hard in general, we develop a lower bound for the objective by relaxing the integer variables and using a linearization technique. Subsequently, we design a near-optimal algorithm to solve this MINLP problem. This algorithm is based on a novel sequential fixing procedure, where the integer variables are determined iteratively via a sequence of linear programs. Simulation results show that solutions obtained by this algorithm are very close to the lower bounds obtained via the proposed relaxation, thus suggesting that the solution produced by the algorithm is near-optimal.     

Quality of service models for heterogeneous networks: overview and challenges

The proliferation and convergence of different types of wired, wireless and mobile networks (such as WiMAX, Wireless Mesh Networks, WPANs, WLANs, etc) and cellular-based networks are crucial for the success of next-generation networks. Traditional wired/wireless networks can hardly meet the requirements of future integrated-service networks which are expected to carry multimedia traffic with various quality of service (QoS) requirements. Therefore, it is necessary to develop efficient global control mechanisms that can maintain QoS requirements to maximize network resources utilization, and minimize operational costs on all the types of wireless mobile networks. In this paper, we present an overview of QoS paradigms for heterogeneous networks and focus on those based on deterministic and probabilistic QoS.     

Preface

Preface

Preface     

Equivalent weights for lexicographic multi-objective programs: Characterizations and computations

A recent paper [19] demonstrated the existence of a set of equivalent weights for which the optimal solution set of a preemptive priority multi-objective program is precisely equal to the set of optimal solutions to the resulting nonpreemptive program with the objective function given as a linear weighting of the multiple objectives. This paper addresses two further issues. Firstly, for some important special cases or applications, it is demonstrated that not only is the computation of a set of equivalent weights feasible, but it is also highly desirable. Two algorithms are presented to compute a set of equivalent weights. One method is a direct specialization of the approach adopted in [19], whereas the second approach is an alternative technique. The latter method is shown to yield weights of uniformly smaller values than the former method, while being of the same computational complexity, and is hence preferable. Secondly, as opposed to constructing one vector of equivalent weights, a characterization is provided for the entire set of equivalent weights.     

The design of branch and bound algorithms for a class of nonlinear integer programs

This paper is concerned with computational experimentation leading to the design of effective branch and bound algorithms for an important class of nonlinear integer programming problems, namely linearly constrained problems, which are used to model several real-world situations. The main contribution here is a study of the effect of node and branching variable selection and storage reduction strategies on overall computational effort for this class of problems, as well as the generation of a set of adequate test problems. Several node and branching variable strategies are compared in the context of a pure breadth-first enumeration, as well as in a special breadth and depth enumeration combination approach presented herein. Also, the effect of using updated pseudocosts is briefly addressed. Computational experience is presented on a set of eighteen suitably-sized nonlinear test problems, as well as on some random linear integer programs. Some of the new rules proposed are demonstrated to be significantly superior to previously suggested strategies; interestingly, even for linear integer programming problems.     

Models and algorithms for the scheduling of a doubles tennis training tournament

We address a doubles tennis scheduling problem in the context of a training tournament, and develop a 0–1 mixed-integer programming model that attempts to balance the partnership and the opponentship pairings among the players. We propose effective symmetry-defeating strategies that impose certain decision hierarchies within the model, which serve to significantly enhance algorithmic performance via their pruning effect. We also discuss the concept of symmetry compatible formulations, and highlight the importance of crafting formulations in discrete optimization in a fashion that enhances the interplay between the original model structure, branch-and-bound algorithms (as implemented in commercial packages such as CPLEX), and the structure of specific symmetry-defeating hierarchical constraints. Finally, various specialized heuristics are devised and are computationally evaluated along with the exact solution schemes using a set of realistic practical test problems.