We consider the local broadcasting problem in the SINR model, which is a basic primitive for gathering initial information among @math wireless nodes. Assuming that nodes can measure received power, we achieve an essentially optimal constant approximate algorithm (with a @math additive term). This improves upon the previous best @math -approximate algorithm. Without power measurement, our algorithm achieves @math -approximation, matching the previous best result, but with a simpler approach that works under harsher conditions, such as arbitrary node failures. We give complementary lower bounds under reasonable assumptions.
Recently, the SINR model has received considerable attention in the algorithms community, starting with the work of Moscibroda and Wattenhofer @cite_9 . Constant-approximation factors are now known for capacity problems, both with fixed power @cite_12 @cite_7 and power control @cite_0 . See the survey of @cite_5 . Distributed algorithms have been given for dominating sets @cite_22 , scheduling @cite_13 @cite_21 , coloring @cite_11 , and connectivity and capacity @cite_6 .
@cite_22 @cite_7 @cite_9 @cite_21 @cite_6 @cite_0 @cite_5 @cite_13 @cite_12 @cite_11
2950288120 2396986403 1036729261 2111209182 1750839748 2122824681 2540490069 1584433497 2003902046 2950595026
We give algorithms with constant-factor performance guarantees for several capacity and throughput problems in the SINR model. The algorithms are all based on a novel LP formulation for capacity problems. First, we give a new constant-factor approximation algorithm for selecting the maximum subset of links that can be scheduled simultaneously, under any non-decreasing and sublinear power assignment. For the case of uniform power, we extend this to the case of variable QoS requirements and link-dependent noise terms. Second, we approximate a problem related to cognitive radio: find a maximum set of links that can be simultaneously scheduled without affecting a given set of previously assigned links. Finally, we obtain constant-factor approximation of weighted capacity under linear power assignment. The throughput capacity of arbitrary wireless networks under the physical Signal to Interference Plus Noise Ratio (SINR) model has received much attention in recent years. In this paper, we investigate the question of how much the worst-case performance of uniform and non-uniform power assignments differ under constraints such as a bound on the area where nodes are distributed or restrictions on the maximum power available. We determine the maximum factor by which a non-uniform power assignment can outperform the uniform case in the SINR model. More precisely, we prove that in one-dimensional settings the capacity of a non-uniform assignment exceeds a uniform assignment by at most a factor of (O( L_ ) ) when the length of the network is (L_ ). In two-dimensional settings, the uniform assignment is at most a factor of (O( P_ ) ) worse than the non-uniform assignment if the maximum power is (P_ ). We provide algorithms that reach this capacity in both cases. These bounds are tight in the sense that previous work gave examples of networks where the lack of power control causes a performance loss in the order of these factors. To complement our theoretical results and to evaluate our algorithms with concrete input networks, we carry out simulations on random wireless networks. The results demonstrate that the link sets generated by the algorithms contain around 20–35 of all links. As a consequence, engineers and researchers may prefer the uniform model due to its simplicity if this degree of performance deterioration is acceptable. In this paper the problem of wireless transmissions scheduling in the path-loss SINR model is considered for different fixed power schemes. The lower bounds for the optimum schedule length proven by Kesselheim and Voecking are considered. It is shown that the lower bound for the linear power scheme is tight, by presenting a constant-factor approximation algorithm. On the other hand, it is shown that the lower bounds proven for many other interesting power schemes can be essentially far from the optima. In this paper, we consider the classical problem of link scheduling in wireless networks under an accurate interference model, in which correct packet reception at a receiver node depends on the signa-to-interference-plus-noise ratio (SINR). While most previous work on wireless networks has addressed the scheduling problem using simplistic graph-based or distance-based interference models, a few recent papers have investigated scheduling with SINR-based interference models. However, these papers have either used approximations to the SINR model or have ignored important aspects of the problem. We study the problem of wireless link scheduling under the exact SINR model and present the first known true approximation algorithms for transmission scheduling under the exact model. We also introduce an algorithm with a proven approximation bound with respect to the length of the optimal schedule under primary interference. As an aside, our study identifies a class of "difficult to schedule" links, which hinder the derivation of tighter approximation bounds. Furthermore, we characterize conditions under which scheduling under SINR-based interference is within a constant factor from optimal under primary interference, which implies that secondary interference only degrades performance by a constant factor in these situations. We consider the scheduling of arbitrary wireless links in the physical model of interference to minimize the time for satisfying all requests. We study here the combined problem of scheduling and power control, where we seek both an assignment of power settings and a partition of the links so that each set satisfies the signal-to-interference-plus-noise (SINR) constraints. We give an algorithm that attains an approximation ratio of O(log n ċ log log Δ), where n is the number of links and Δ is the ratio between the longest and the shortest link length. Under the natural assumption that lengths are represented in binary, this gives the first approximation ratio that is polylogarithmic in the size of the input. The algorithm has the desirable property of using an oblivious power assignment, where the power assigned to a sender depends only on the length of the link. We give evidence that this dependence on Δ is unavoidable, showing that any reasonably behaving oblivious power assignment results in a Ω(log log Δ)-approximation. These results hold also for the (weighted) capacity problem of finding a maximum (weighted) subset of links that can be scheduled in a single time slot. In addition, we obtain improved approximation for a bidirectional variant of the scheduling problem, give partial answers to questions about the utility of graphs for modeling physical interference, and generalize the setting from the standard 2-dimensional Euclidean plane to doubling metrics. Finally, we explore the utility of graph models in capturing wireless interference. Cognitive radio networks (CRNs) have the potential to utilize spectrum efficiently and are positioned to be the core technology for the next-generation multihop wireless networks. An important problem for such networks is its capacity. We study this problem for CRNs in the SINR (signal-to-interference-and-noise-ratio) model, which is considered to be a better characterization of interference (but also more difficult to analyze) than disk graph model. The main difficulties of this problem are two-fold. First, SINR is a nonconvex function of transmission powers; an optimization problem in the SINR model is usually a nonconvex program and NP-hard in general. Second, in the SINR model, scheduling feasibility and the maximum allowed flow rate on each link are determined by SINR at the physical layer. To maximize capacity, it is essential to follow a cross-layer approach, but joint optimization at physical (power control), link (scheduling), and network (flow routing) layers with the SINR function is inherently difficult. In this paper, we give a mathematical characterization of the joint relationship among these layers. We devise a solution procedure that provides a (1- ) optimal solution to this complex problem, where is the required accuracy. Our theoretical result offers a performance benchmark for any other algorithms developed for practical implementation. Using numerical results, we demonstrate the efficacy of the solution procedure and offer quantitative understanding on the interaction of power control, scheduling, and flow routing in a CRN. In this paper, we study resource allocation for a multicarrier-based cognitive radio (CR) network. More specifically, we investigate the problem of secondary users’ energy-efficiency (EE) maximization problem under secondary total power and primary interference constraints. First, assuming cooperation among the secondary base stations (BSs), a centralized approach is considered to solve the EE optimization problem for the CR network where the primary and secondary users are using either orthogonal frequency-division multiplexing (OFDM) or filter bank based multicarrier (FBMC) modulations. We propose an alternating-based approach to solve the joint power-subcarrier allocation problem. More importantly, in the first place, subcarriers are allocated using a heuristic method for a given feasible power allocation. Then, we conservatively approximate the nonconvex power control problem and propose a joint successive convex approximation-Dinkelbach algorithm (SCADA) to efficiently obtain a solution to the nonconvex power control problem. The proposed algorithm is shown to converge to a solution that coincides with the stationary point of the original nonconvex power control subproblem. Moreover, we propose a dual decomposition-based decentralized version of the SCADA. Second, under the assumption of no cooperation among the secondary BSs, we propose a fully distributed power control algorithm from the perspective of game theory. The proposed algorithm is shown to converge to a Nash-equilibrium (NE) point. Moreover, we propose a sufficient condition that guarantees the uniqueness of the achieved NE. Extensive simulation analyses are further provided to highlight the advantages and demonstrate the efficiency of our proposed schemes. In modern wireless networks devices are able to set the power for each transmission carried out. Experimental but also theoretical results indicate that such power control can improve the network capacity significantly. We study this problem in the physical interference model using SINR constraints. In the SINR capacity maximization problem, we are given n pairs of senders and receivers, located in a metric space (usually a so-called fading metric). The algorithm shall select a subset of these pairs and choose a power level for each of them with the objective of maximizing the number of simultaneous communications. This is, the selected pairs have to satisfy the SINR constraints with respect to the chosen powers. We present the first algorithm achieving a constant-factor approximation in fading metrics. The best previous results depend on further network parameters such as the ratio of the maximum and the minimum distance between a sender and its receiver. Expressed only in terms of n, they are (trivial) Ω(n) approximations. Our algorithm still achieves an O(log n) approximation if we only assume to have a general metric space rather than a fading metric. Furthermore, existing approaches work well together with the algorithm allowing it to be used in singlehop and multi-hop scheduling scenarios. Here, we also get polylog n approximations. We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor. Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines, (ii) bandwidth allocation for sessions between two endpoints, (iii) general caching, (iv) dynamic storage allocation, and (v) bandwidth allocation on optical line and ring topologies. For some of these problems we provide the first constant factor approximation algorithm. Our algorithms are simple and efficient and are based on the local-ratio technique. We note that they can equivalently be interpreted within the primal-dual schema. We study the wireless scheduling problem in the SINR model. More specifically, given a set of @math links, each a sender-receiver pair, we wish to partition (or ) the links into the minimum number of slots, each satisfying interference constraints allowing simultaneous transmission. In the basic problem, all senders transmit with the same uniform power. We give a distributed @math -approximation algorithm for the scheduling problem, matching the best ratio known for centralized algorithms. It holds in arbitrary metric space and for every length-monotone and sublinear power assignment. It is based on an algorithm of Kesselheim and V "ocking, whose analysis we improve by a logarithmic factor. We show that every distributed algorithm uses @math slots to schedule certain instances that require only two slots, which implies that the best possible absolute performance guarantee is logarithmic.