Catálogo de publicaciones - libros

This chapter deals with the Perron root of nonnegative irreducible matrices. Applications abound with nonnegative and positive matrices so that it is natural to investigate their properties. In doing so, one of the central problems is to what extent the nonnegativity (positivity) is inherited by the eigenvalues and eigenvectors. The principal tools for the analysis of spectral properties of irreducible matrices are provided by Perron–Frobenius theory. A comprehensive reference on nonnegative matrices is [2]. Some basic results are summarized in Appendix A.4. For more information about the Perron–Frobenius theory, the reader is also referred to [3, 4, 5]. We have divided the chapter into two major parts. The purpose of the first part is to characterize the Perron root of irreducible matrices and present some interesting bounds on it. There exists a vast literature addressing the problem of estimating the Perron root of nonnegative irreducible matrices. Tight bounds on the Perron root have attracted a great deal of attention over several decades. A brief (and by no means extensive) summary of some related results can be found at the end of this chapter. In the second part, we consider the Perron root of matrix-valued functions of some parameter vector. In this case, each matrix entry is a continuous nonnegative function defined on some convex parameter set, with the constraint that the matrix is irreducible for every fixed parameter vector. As a result, the Perron root can be viewed as a positive real-valued function defined on a convex set. Now the objective is to provide conditions under which the Perron root is a convex (or concave) function of the parameter vector. Note that the convexity property is a key ingredient in the development of access control and resource allocation strategies for wireless networks.

This chapter deals with a positive solution p to the following system of linear equations with nonnegative coefficients: $${\boldsymbol{\mathrm{p}}}={\boldsymbol{\mathrm{u}}}+{\boldsymbol{\mathrm{X}}}{\boldsymbol{\mathrm{p}}}\,.$$ Here and hereafter, ${\boldsymbol{\mathrm{u}}}\in{\mathbb{R}}_{++}^K$ is a given positive vector, ${\boldsymbol{\mathrm{X}}}\in{\mathbb{R}}_+^{K\times K}$ is a given nonnegative matrix (not necessarily irreducible), and ${\boldsymbol{\mathrm{p}}}\in{\mathbb{R}}_{++}^K$ is a sought vector, provided that it exists.

Wireless networking has been a vibrant research area over the last two decades. During this time, we have observed the evolution of a number of different wireless communications standards that support a wide range of services. They include delay-sensitive applications such as voice and real-time video that usually have strict requirements with respect to quality-of-service (QoS) parameters such as data rate, delay and/or bit error rate. In such cases, a network designer must ensure that the QoS requirements are satisfied permanently. Data applications, however, may have fundamentally different QoS requirements and traffic characteristics than video or voice applications. In fact, most data applications are delay-insensitive, and therefore may tolerate larger transmission delays.

A wireless communications network is a collection of nodes being capable of communicating with each other over wireless communications links. Let $\mathsf{N}:=\{1,\dotsc,N\}$ be the set of nodes, and let ( n , m ) with n ≠ m represent a wireless link from node n ∈ N to node m ∈ N . We say that there is a wireless link ( n , m ) with n ≠ m if both 1 node n is allowed to transmit data to node m , and 2 a minimum signal-to-noise ratio (SNR), being necessary for successful transmission, can be achieved on link ( n , m ), in the absence of interference and with transmit power on this link subject to some power constraints. It is reasonable to assume that wireless links are bidirectional in the sense that ( n , m ) exists if and only if there exists ( m , n ). We label links (in any particular way) by the integers $1,2,\dotsc,L$ and use $\mathsf{L}=\{1,\dotsc,L\}$ to denote a set of all wireless links. The pair ( N , L ) is referred to as the network topology. With any network, we associate the topology graph, which is an undirected graph where a vertex corresponds to a node in the network, and an edge between two vertices represents a wireless link between the corresponding nodes.

This chapter formulates the resource allocation problem for wireless networks. Before that, however, we briefly discuss the fundamental trade off between efficiency and fairness in wired networks. This trade off eventually led researchers to consider the problem of maximizing the sum of increasing and strictly concave utility functions of source rates. We review some existing solutions to this problem and explain the insufficiency of these solutions in case of wireless networks. Section 5.2 reformulates the problem to better capture the situation encountered in wireless networks. We will argue in favor of MAC-layer fair policies that have already been used in wired networks as a basis to achieve end-to-end fairness. We precisely define the concept of joint power control and link scheduling as well as introduce the notion of the feasible rate region. It is shown that this set is not convex in general, which makes the optimization of wireless networks a fairly tricky task. The utility-based power control problem is formulated in Sect. 5.2.4. In particular, we introduce a class of increasing and strictly concave utility functions of link rates for which the power control problem can be converted into a convex optimization problem. The reader will realize a strong connection to the results of the first part of the book because the inverse functions of the considered utility functions are log-convex functions. Finally, we will utilize some results of Chapt. 2 to obtain valuable insights into the problem of joint power control and link scheduling.

This chapter presents algorithmic solutions to the power control problem as stated in the previous chapter. We focus on recursive gradient-based algorithms with a constant step size [83, 11]. Although much more powerful algorithms can be devised to solve the problem, we are going to confine our attention to such methods because of their simplicity. In particular, there is no need for step size control, which is difficult to realize in practice.

The appendix provides some (very) basic concepts and results from linear algebra that are vital to understanding the theory presented in this book. This is also a good opportunity to introduce the notation used throughout the book. Proofs are provided only for the most important results such as the Perron–Frobenius theorem. For other proofs and a detailed treatment of this material, the reader is referred to any linear algebra book and [5, 3, 7, 2, 12, 4].

In this chapter, we collect definitions, notational conventions and several results from convex analysis that may be helpful in better understanding the material covered in this manuscript. Proofs are provided only for selected results concerning the notion of log-convexity and the convergence of gradient projection algorithms. For other proofs, the reader is referred to any standard analysis book (e.g., [98]) and [83, 88, 11].