The SINR model for wireless networks has been extensively studied recently. It tries to model whether a particular transmitter is heard at a specific location, with @math transmitting simultaneously. The SINR diagram consists of @math regions where each transmitter can be heard and the remaining space where no one can be heard. Efficient point location in the SINR diagram, i.e., building a data structure to determine, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated. Previous such planar data structures are constructed in time at least quadratic in @math and support logarithmic-time approximate queries. Moreover, the performance of these depends not only on the number @math of transmitters and on the approximation parameter @math , but also on some geometric parameters that cannot be bounded a priori as a function of @math or @math . We address the question of batched point location queries, i.e., answering many queries simultaneously. Specifically, in one dimension, we can answer @math queries exactly in amortized polylogarithmic time per query, while in the plane we can do it approximately. All these results can handle arbitrary power assignments to the transmitters. Moreover, the amortized query time in these results depends only on @math and @math . We also show how to speed up the preprocessing in a previously proposed point-location structure in SINR diagram for uniform-power sites, by almost a full order of magnitude. For this we obtain results on the sensitivity of the reception regions to slight changes in the reception threshold, which are of independent interest. Finally, these results demonstrate the (so far underutilized) power of combining algebraic tools with those of computational geometry and other fields.
The papers most relevant to ours are those by @cite_9 and @cite_23 discussed above. @cite_14 also considered the problem of handling queries of the following form (in the uniform-power setting): Given a transmitter @math and query point @math , does @math receive @math by successively applying interference cancellation? (Interference cancellation is a technology that enables a point @math to receive a transmitter @math , even if @math 's signal is not the strongest one received at @math ; see @cite_14 for further details.)
@cite_9 @cite_14 @cite_23
1995382207 2130228237 2952813714
We study an interference network where equally-numbered transmitters and receivers lie on two parallel lines, each transmitter opposite its intended receiver. We consider two short-range interference models: the "asymmetric network," where the signal sent by each transmitter is interfered only by the signal sent by its left neighbor (if present), and a "symmetric network," where it is interfered by both its left and its right neighbors. Each transmitter is cognizant of its own message, the messages of the @math transmitters to its left, and the messages of the @math transmitters to its right. Each receiver decodes its message based on the signals received at its own antenna, at the @math receive antennas to its left, and the @math receive antennas to its right. For such networks we provide upper and lower bounds on the multiplexing gain, i.e., on the high-SNR asymptotic logarithmic growth of the sum-rate capacity. In some cases our bounds meet, e.g., for the asymmetric network. Our results exhibit an equivalence between the transmitter side-information parameters @math and the receiver side-information parameters @math in the sense that increasing decreasing @math or @math by a positive integer @math has the same effect on the multiplexing gain as increasing decreasing @math or @math by @math . Moreover---even in asymmetric networks---there is an equivalence between the left side-information parameters @math and the right side-information parameters @math . We consider a system, comprising a library of @math files (e.g., movies) and a wireless network with a @math transmitters, each equipped with a local cache of size of @math files and a @math receivers, each equipped with a local cache of size of @math files. Each receiver will ask for one of the @math files in the library, which needs to be delivered. The objective is to design the cache placement (without prior knowledge of receivers’ future requests) and the communication scheme to maximize the throughput of the delivery. In this setting, we show that the sum degrees-of-freedom (sum-DoF) of @math is achievable, and this is within a factor of 2 of the optimum, under uncoded prefetching and one-shot linear delivery schemes. This result shows that (i) the one-shot sum-DoF scales linearly with the aggregate cache size in the network (i.e., the cumulative memory available at all nodes ), (ii) the transmitters’ caches and receivers’ caches contribute equally in the one-shot sum-DoF, and (iii) caching can offer a throughput gain that scales linearly with the size of the network. To prove the result, we propose an achievable scheme that exploits the redundancy of the content at transmitter’s caches to cooperatively zero-force some outgoing interference, and availability of the unintended content at the receiver’s caches to cancel (subtract) some of the incoming interference. We develop a particular pattern for cache placement that maximizes the overall gains of cache-aided transmit and receive interference cancellations. For the converse, we present an integer optimization problem which minimizes the number of communication blocks needed to deliver any set of requested files to the receivers. We then provide a lower bound on the value of this optimization problem, hence leading to an upper bound on the linear one-shot sum-DoF of the network, which is within a factor of 2 of the achievable sum-DoF. We study the degrees of freedom (DoF) of the @math -user interference channel with coordinated multipoint (CoMP) transmission and reception. Each message is jointly transmitted by @math successive transmitters, and is jointly received by @math successive receivers. We refer to this channel as the CoMP channel with a transmit cooperation order of @math and receive cooperation order of @math . Since the channel has a total of @math transmit antennas and @math receive antennas, the maximum possible DoF is equal to @math . We show that the CoMP channel has @math DoF if and only if @math . The key idea is that the zero forcing of the interference corresponding to the @math message at the decoder of the @math message, where @math , can be viewed as a shared responsibility between the @math transmitters carrying the @math message, and the @math receivers decoding the @math message. For the general case, we derive an outer bound that states that the DoF is bounded above by @math . For the special case with only CoMP transmission, i.e, @math , we propose a scheme that can achieve @math DoF for all @math K @math M_ t @math M_ t -1$ receivers, thereby allowing each of these receivers to enjoy 1 DoF, and asymptotic interference alignment is used to align the interfering signals at each other receiver to occupy half the signal space. The achievability proofs are based on the notion of algebraic independence from algebraic geometry. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . We consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node @math in a given tree @math . Upon querying a node @math of the tree, the strategy receives as a reply an indication of the connected component of @math containing the target @math . The cost of querying each node is given by a known non-negative weight function, and the considered objective is to minimize the total query cost for a worst-case choice of the target. Designing an optimal strategy for a weighted tree search instance is known to be strongly NP-hard, in contrast to the unweighted variant of the problem which can be solved optimally in linear time. Here, we show that weighted tree search admits a quasi-polynomial time approximation scheme: for any @math , there exists a @math -approximation strategy with a computation time of @math . Thus, the problem is not APX-hard, unless @math . By applying a generic reduction, we obtain as a corollary that the studied problem admits a polynomial-time @math -approximation. This improves previous @math -approximation approaches, where the @math -notation disregards @math -factors. The calculation of the SIR distribution at the typical receiver (or, equivalently, the success probability of transmissions over the typical link) in Poisson bipolar and cellular networks with Rayleigh fading is relatively straightforward, but it only provides limited information on the success probabilities of the individual links. This paper focuses on the meta distribution of the SIR, which is the distribution of the conditional success probability @math given the point process, and provides bounds, an exact analytical expression, and a simple approximation for it. The meta distribution provides fine-grained information on the SIR and answers questions such as “What fraction of users in a Poisson cellular network achieve 90 link reliability if the required SIR is 5 dB?” Interestingly, in the bipolar model, if the transmit probability @math is reduced while increasing the network density @math such that the density of concurrent transmitters @math stays constant as @math , @math degenerates to a constant, i.e., all links have exactly the same success probability in the limit, which is the one of the typical link. In contrast, in the cellular case, if the interfering base stations are active independently with probability @math , the variance of @math approaches a non-zero constant when @math is reduced to 0 while keeping the mean success probability constant. In this paper we study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multi-station network, we use the convenient representation of a . In the SINR model, the resulting partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. We consider the general case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques as well as the theoretical challenge of understanding the geometry of SINR diagrams. We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line. In addition, one of our key results concerns the behavior of a @math -dimensional map. Specifically, although the @math -dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected. In addition, as a step toward establishing a weaker form of convexity for the @math -dimensional map, we study the interference function and show that it satisfies the maximum principle. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location. The transmission capacity of an ad-hoc network is the maximum density of active transmitters per unit area, given an outage constraint at each receiver for a fixed rate of transmission. Assuming that the transmitter locations are distributed as a Poisson point process, this paper derives upper and lower bounds on the transmission capacity of an ad-hoc network when each node is equipped with multiple antennas. The transmitter either uses eigen multi-mode beamforming or a subset of its antennas without channel information to transmit multiple data streams, while the receiver uses partial zero forcing to cancel certain interferers using some of its spatial receive degrees of freedom (SRDOF). The receiver either cancels the nearest interferers or those interferers that maximize the post-cancellation signal-to-interference ratio. Using the obtained bounds, the optimal number of data streams to transmit, and the optimal SRDOF to use for interference cancellation are derived that provide the best scaling of the transmission capacity with the number of antennas. With beamforming, single data stream transmission together with using all but one SRDOF for interference cancellation is optimal, while without beamforming, single data stream transmission together with using a fraction of the total SRDOF for interference cancellation is optimal. At present, operators address the explosive growth of mobile data demand by densification of the cellular network so as to reduce the transmitter-receiver distance and to achieve higher spectral efficiency. Due to such network densification and the intense proliferation of wireless devices, modern wireless networks are interference-limited, which motivates the use of interference mitigation and coordination techniques. In this work, we develop a statistical framework to evaluate the performance of multi-tier heterogeneous networks with successive interference cancellation (SIC) capabilities, accounting for the computational complexity of the cancellation scheme and relevant network related parameters such as random location of the access points (APs) and mobile users, and the characteristics of the wireless propagation channel. We explicitly model the consecutive events of canceling interferers and we derive the success probability to cancel the n-th strongest signal and to decode the signal of interest after n cancellations. When users are connected to the AP which provides the maximum average received signal power, the analysis indicates that the performance gains of SIC diminish quickly with n and the benefits are modest for realistic values of the signal-to-interference ratio (SIR). We extend the statistical model to include several association policies where distinct gains of SIC are expected: (i) minimum load association, (ii) maxi- mum instantaneous SIR association, and (iii) range expansion. Numerical results show the effectiveness of SIC for the considered association policies. This work deepens the understanding of SIC by defining the achievable gains for different association policies in multi-tier heterogeneous networks. We consider distance queries in vertex-labeled planar graphs. For any fixed @math we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex @math and a label @math return a @math -approximation of the distance from @math to its closest vertex with label @math . For a directed planar graph with @math vertices, such that the ratio of the largest to smallest arc length is bounded by @math , the preprocessing time is @math , the data structure size is @math , and the query time is @math . We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect. The transmission capacity of an ad-hoc network is the maximum density of active transmitters in an unit area, given an outage constraint at each receiver for a fixed rate of transmission. Assuming channel state information is available at the receiver, this paper presents bounds on the transmission capacity as a function of the number of antennas used for transmission, and the spatial receive degrees of freedom used for interference cancelation at the receiver. Canceling the strongest interferers, using a single antenna for transmission together with using all but one spatial receive degrees of freedom for interference cancelation is shown to maximize the transmission capacity. Canceling the closest interferers, using a single antenna for transmission together with using a fraction of the total spatial receive degrees of freedom for interference cancelation depending on the path loss exponent, is shown to maximize the transmission capacity. Suppose that we have @math sensors and each one intends to send a function @math (e.g., a signal or an image) to a receiver common to all @math sensors. During transmission, each @math gets convolved with a function @math . The receiver records the function @math , given by the sum of all these convolved signals. When and under which conditions is it possible to recover the individual signals @math and the blurring functions @math from just one received signal @math ? This challenging problem, which intertwines blind deconvolution with blind demixing, appears in a variety of applications, such as audio processing, image processing, neuroscience, spectroscopy, and astronomy. It is also expected to play a central role in connection with the future Internet-of-Things. We will prove that under reasonable and practical assumptions, it is possible to solve this, otherwise, highly ill-posed problem and recover the @math transmitted functions @math and the impulse responses @math in a robust, reliable, and efficient manner, from just one single received function @math by solving a semidefinite program. We derive explicit bounds on the number of measurements needed for successful recovery and prove that our method is robust in the presence of noise. Our theory is actually suboptimal, since numerical experiments demonstrate that, quite remarkably, recovery is still possible if the number of measurements is close to the number of degrees of freedom. We study the aggregate group nearest neighbor searching for the MAX operator in the plane. For a set @math of @math points and a query set @math of @math points, the query asks for a point of @math whose maximum distance to the points in @math is minimized. We present data structures for answering such queries for both @math and @math distance measures. Previously, only heuristic and approximation algorithms were given for both versions. For the @math version, we build a data structure of O(n) size in @math time, such that each query can be answered in @math time. For the @math version, we build a data structure in @math time and @math space, such that each query can be answered in @math time, and alternatively, we build a data structure in @math time and space for any @math , such that each query can be answered in @math time. Further, we extend our result for the @math version to the top- @math queries where each query asks for the @math points of @math whose maximum distances to @math are the smallest for any @math with @math : We build a data structure of O(n) size in @math time, such that each top- @math query can be answered in @math time. In wireless networks, interference that is generated by undesired transmitters dominantly limits network performance. The correlation of node locations (in mobile or static networks) makes the interference temporally correlated. In this paper, we quantify the temporal correlation of the interference in mobile Poisson networks. More specifically, we obtain closed-form expressions for the interference correlation coefficient @math in Poisson line networks under various mobility models. When the mean speed of nodes @math increases, we show that @math is asymptotically proportional to @math . Moreover, multi-path fading and random MAC schemes reduce the temporal correlation of the interference. These results are extended to higher-dimensional networks. The capacity of a wireless network is the maximum possible amount of simultaneous communication, taking interference into account. Formally, we treat the following problem. Given is a set of links, each a sender-receiver pair located in a metric space, and an assignment of power to the senders. We seek a maximum subset of links that are feasible in the SINR model: namely, the signal received on each link should be larger than the sum of the interferences from the other links. We give a constant-factor approximation that holds for any length-monotone, sub-linear power assignment and any distance metric. We use this to give essentially tight characterizations of capacity maximization under power control using oblivious power assignments. Specifically, we show that the mean power assignment is optimal for capacity maximization of bi-directional links, and give a tight @math -approximation of scheduling bi-directional links with power control using oblivious power. For uni-directional links we give a nearly optimal @math -approximation to the power control problem using mean power, where @math is the ratio of longest and shortest links. Combined, these results clarify significantly the centralized complexity of wireless communication problems. This paper develops a new communication strategy, ergodic interference alignment, for the K-user interference channel with time-varying fading. At any particular time, each receiver will see a superposition of the transmitted signals plus noise. The standard approach to such a scenario results in each transmitter-receiver pair achieving a rate proportional to 1 K its interference-free ergodic capacity. However, given two well-chosen time indices, the channel coefficients from interfering users can be made to exactly cancel. By adding up these two observations, each receiver can obtain its desired signal without any interference. If the channel gains have independent, uniform phases, this technique allows each user to achieve at least 1 2 its interference-free ergodic capacity at any signal-to-noise ratio. Prior interference alignment techniques were only able to attain this performance as the signal-to-noise ratio tended to infinity. Extensions are given for the case where each receiver wants a message from more than one transmitter as well as the “X channel” case (with two receivers) where each transmitter has an independent message for each receiver. Finally, it is shown how to generalize this strategy beyond Gaussian channel models. For a class of finite field interference channels, this approach yields the ergodic capacity region. Interference alignment has emerged as a powerful tool in the analysis of multiuser networks. Despite considerable recent progress, the capacity region of the Gaussian @math -user interference channel is still unknown in general, in part due to the challenges associated with alignment on the signal scale using lattice codes. This paper develops a new framework for lattice interference alignment, based on the compute-and-forward approach. Within this framework, each receiver decodes by first recovering two or more linear combinations of the transmitted codewords with integer-valued coefficients and then solving these linear combinations for its desired codeword. For the special case of symmetric channel gains, this framework is used to derive the approximate sum capacity of the Gaussian interference channel, up to an explicitly defined outage set of the channel gains. The key contributions are the capacity lower bounds for the weak through strong interference regimes, where each receiver should jointly decode its own codeword along with part of the interfering codewords. As part of the analysis, it is shown that decoding @math linear combinations of the codewords can approach the sum capacity of the @math -user Gaussian multiple-access channel up to a gap of no more than @math bits. Let @math be a simple polygon of @math vertices. We consider two-point @math shortest path queries in @math . We build a data structure of @math size in @math time such that given any two query points @math and @math , the length of an @math shortest path from @math to @math in @math can be computed in @math time, or in @math time if both @math and @math are vertices of @math , and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem. In this paper, we investigate the problem of spectrally efficient operation of a cognitive radio, also called secondary spectrum user, under an interference from the primary system. A secondary receiver observes a multiple access channel of two users, the secondary and the primary transmitter, respectively. The secondary receiver applies Opportunistic Interference Cancelation (OIC) and Suboptimal Opportunistic Interference Cancelation (S-OIC) thus decoding the primary signal when such an opportunity is created by the rate selected at the primary transmitter and the power received from the primary transmitter. First, we investigate how the secondary transmitter, when using OIC and S-OIC for fixed transmitting power, should select its rate in order to meet its target outage probability under different assumptions about the channel-state-information available at the secondary transmitter. We study three different cases and for each of them identify the region of achievable primary and secondary rates. Second, we determine how the secondary transmitter should select its transmitting power not to violate the target outage probability at the primary terminals. Our numerical results show that the best secondary performance is always obtained when the secondary transmitter knows the instantaneous channel-state-information toward the intended receiver. We also evaluate the degradation in terms of achievable rate at the secondary receiver when it uses suboptimal decoding (S-OIC rather than OIC) and the interplay between the allowed power at the secondary transmitter (which depends on the target outage probability at the primary receiver) and the decodability at the secondary receiver. While cognitive radio enables spectrum-efficient wireless communication, radio frequency (RF) energy harvesting from ambient interference is an enabler for energy-efficient wireless communication. In this paper, we model and analyze cognitive and energy harvesting-based device-to-device (D2D) communication in cellular networks. The cognitive D2D transmitters harvest energy from ambient interference and use one of the channels allocated to cellular users (in uplink or downlink), which is referred to as the D2D channel, to communicate with the corresponding receivers. We investigate two spectrum access policies for cellular communication in the uplink or downlink, namely, random spectrum access (RSA) policy and prioritized spectrum access (PSA) policy. In RSA, any of the available channels including the channel used by the D2D transmitters can be selected randomly for cellular communication, while in PSA the D2D channel is used only when all of the other channels are occupied. A D2D transmitter can communicate successfully with its receiver only when it harvests enough energy to perform channel inversion toward the receiver, the D2D channel is free, and the signal-to-interference-plus-noise ratio @math at the receiver is above the required threshold; otherwise, an outage occurs for the D2D communication. We use tools from stochastic geometry to evaluate the performance of the proposed communication system model with general path-loss exponent in terms of outage probability for D2D and cellular users. We show that energy harvesting can be a reliable alternative to power cognitive D2D transmitters while achieving acceptable performance. Under the same @math outage requirements as for the non-cognitive case, cognitive channel access improves the outage probability for D2D users for both the spectrum access policies. When compared with the RSA policy, the PSA policy provides a better performance to the D2D users. Also, using an uplink channel provides improved performance to the D2D users in dense networks when compared to a downlink channel. For cellular users, the PSA policy provides almost the same outage performance as the RSA policy.