The growing demand for new applications, like digital twins, Extended reality(XR), autonomous vehicles, smart environments, and other Internet of Things(IoT) has set the stage for wireless evolution towards 6G. In 6G wireless sensing, communication and computation are expected to be imbued in a ubiquitous manner. However, optimizing resource allocation in such an integrated sensing, communication, and computation (ISCC) raises critical challenges. In this paper, we focus on the efficient and optimal distribution of orthogonal, homogeneous, subcarriers among these computation, communication, and sensing domains. We propose a novel bi-level multi-objective optimization approach to maximize communication throughput, sensing coverage, and data offloaded from user equipment (UE) to the base station (BS) for computation, resulting in a Pareto efficient front for channel allocations. A 2-stage future Pareto front estimation framework is introduced where the exogeneous parameters are forecasted using using a) Long Short Term Memory (LSTM) or b) Convolutional Neural Network (CNN) model. Then, Non-dominated sorting genetic algorithm II (NSGA-II) is used to estimate the Pareto front for each time step within a prediction window. The framework's performance is evaluated by using a comparison of the generational distance (GD) between the estimated Pareto front from the predicted parameters to the Pareto front generated by the true parameters. Simulation results point out that compared to baseline, LSTM and CNN-based frameworks respectively reduce the GD by 47% and 84% in objective space and 56% and 65% in decision space.

Throughput extremization is an important facet of performance modeling for low-power wide-area network (LP-WAN) wireless networks (e.g., LoRaWAN) as it provides insight into the best and worst case behavior of the network. Our previous work on throughput extremization established lower and upper bounds on throughput for random access channel assignment over a collision erasure channel in which the lower bound is expressed in terms of the number of radios and sum load on each channel. In this paper the lower bound is further characterized by identifying two local minimizers (a load balanced assignment and an imbalanced assignment) where the decision variables are the number of radios assigned to each channel and the total load on each channel. A primary focus is to characterize how macro-parameters of the optimization, i.e., the total number of radios, their total load, and the minimum load per radio, determine the regions under which each of the local minimizers is in fact the global minimizer.

A natural basis for the detection of a wireless random reactive jammer (RRJ) is the perceived violation by the detector [typically located at the access point (AP)] of the carrier sensing protocol underpinning many wireless random access protocols (e.g., Wi-Fi). Specifically, when the wireless medium is perceived by a station to be busy, a carrier sensing compliant station will avoid transmission, while an RRJ station will often initiate transmission. However, hidden terminals (HTs), i.e., activity detected by the AP but not by the sensing station, complicate the use of carrier sensing as the basis for RRJ detection since they provide plausible deniability to a station suspected of being an RRJ. The RRJ has the dual objectives of avoiding detection and effectively disrupting communication, but there is an inherent performance tradeoff between these two objectives. In this paper, we capture the behavior of both the RRJ and the compliant stations via a parsimonious Markov chain model and pose the detection problem using the framework of the Markov chain hypothesis testing. Our analysis yields the receiver operating characteristic (ROC) of the detector and the optimized behavior of the RRJ. While there has been extensive work in the literature on jamming detection, our innovation lies in leveraging carrier sensing as a natural and effective basis for detection.

A natural basis for the detection of a wireless random reactive jammer (RRJ) is the perceived violation by the detector (typically located at the access point (AP)) of the carrier sensing protocol underpinning many wireless random access protocols (e.g., WiFi). Specifically, when the wireless medium is perceived by a station to be busy, a carrier sensing compliant station will avoid transmission while a RRJ station will often initiate transmission. However, hidden terminals, i.e., activity detected by the AP but not by the sensing station, complicate the use of carrier sensing as the basis for RRJ detection since they provide plausible deniability to a station suspected of being an RRJ. The RRJ has the dual objectives of avoiding detection and effectively disrupting communication, but there is an inherent performance tradeoff between these two objectives. In this paper we capture the behavior of both the RRJ and the compliant stations via a parsimonious Markov chain model, and pose the detection problem using the framework of Markov chain hypothesis testing. Our analysis yields the receiver operating characteristic (ROC) of the detector, and the optimized behavior of the RRJ. While there has been extensive work in the literature on jamming detection, our innovation lies in leveraging carrier sensing as a natural and effective basis for detection.

This paper analyzes the connection between the protocol and physical interference models in the setting of Poisson wireless networks. A transmission is successful under the protocol model if there are no interferers within a parameterized guard zone around the receiver, while a transmission is successful under the physical model if the signal to interference plus noise ratio at the receiver is above a threshold. The parameterized protocol model forms a family of decision rules for predicting the success or failure of the same transmission attempt under the physical model. For Poisson wireless networks, we employ stochastic geometry to determine the prior, evidence, and posterior distributions associated with this estimation problem. With this in hand, we proceed to develop six sets of results: 1) the maximum correlation of protocol and physical model success indicators; 2) the minimum Bayes risk in estimating physical success from a protocol observation; 3) the receiver operating characteristic (ROC) of false rejection (Type I) and false acceptance (Type II) probabilities; 4) the impact of Rayleigh fading versus no fading on the correlation and ROC; 5) the impact of multiple prior protocol model observations in the setting of a wireless network with a fixed set of nodes in which the nodes employ the slotted Aloha protocol in each time slot; and 6) a numerical investigation of the effect of different pathloss models.

Wireless sensor network applications, including the Internet of Things (IoT), will benefit from message concentration protocols, which gather messages originating at a large number of spatially distributed nodes (devices) into a small subset of those nodes, each holding a subset of the messages. This concentration facilitates more efficient access to the network or cloud, in the aggregate, than when each device seeks individual direct access. Such protocols must be lightweight and capable of operating without knowledge of the (potentially dynamic) network topology. In this paper we propose an extremely simple multi-round Aloha-based protocol, wherein the set of live nodes in each round randomly partition into transmitters and receivers, and the receivers collect messages from all transmitters within range. The protocol requires judicious choice of both the multi-round contention probabilities and transmission powers to effectively tradeoff between the four performance metrics of interest - the degree of message concentration, the fraction of lost messages, the protocol delay, and the transmission power. We analyze a special case of this protocol using basic results from stochastic geometry and branching processes.

We consider a wireless network of static nodes where each transmitter-receiver pair employs slotted Aloha, electing to transmit with a common contention probability p, and we further assume the Rayleigh fading varies with each time slot. The random point processes of actual transmitters in a given time slot (along with their random fades) determine the interference seen by a reference receiver, and the interference across time slots is dependent due to common dependence on the underlying set of potential interferers. It follows that observations of the set of transmitters over several time slots (or summary statistics of this process) may be leveraged to yield improved estimates of the probability of success of the transmission attempted at the reference receiver. In this paper we study the value of several different forms of such observations in improving this estimated success probability. Specifically, we consider five cases: the observer has i) zero knowledge, ii) full knowledge of the point process of potential transmitters, iii) knowledge of the number of "nearby" potential transmitters, iv) N binary observations under the "physical" model at the reference receiver, and v) N binary observations under the "protocol" model at the reference receiver.

The rate regions of multilevel diversity coding systems (MDCSs), a sub-class of the broader family of multi-source multi-sink networks with special structure, are investigated in a systematic way. We enumerate all non-isomorphic MDCS instances with at most three sources and four encoders. Then, the exact rate region of every one of these more than 7000 instances is proven via computations showing that the Shannon outer bound matches with a custom constructed linear code-based inner bound. Results gained from these computations are summarized in key statistics involving aspects, such as the sufficiency of scalar binary codes, the necessary size of vector binary codes, and so on. Also, it is shown how to construct the codes for an achievability proof. Based on this large repository of rate regions, a series of results about general MDCS cases of arbitrary size that they inspired is introduced and proved. In particular, a series of embedding operations that preserve the property of sufficiency of scalar or vector codes is presented. The utility of these operations is demonstrated by boiling the thousands of MDCS instances for which scalar binary (superposition) codes are insufficient down to 12 (26) forbidden the smallest embedded MDCS instances.instances.

Recent algorithmic developments have enabled computers to automatically determine and prove the capacity regions of small hypergraph networks under network coding. A structural theory relating network coding problems of different sizes is developed to make the best use of this newfound computational capability. A formal notion of network minimality is developed, which removes components of a network coding problem that are inessential to its core complexity. Equivalence between different network coding problems under relabeling is formalized via group actions, an algorithm which can directly list single representatives from each equivalence class of minimal networks up to a prescribed network size is presented. This algorithm, together with rate region software, is leveraged to create a database containing the rate regions for all minimal network coding problems with five or fewer sources and edges, a collection of 744119 equivalence classes representing more than 9 million networks. In order to best learn from this database, and to leverage it to infer rate regions and their characteristics of networks at scale, a hierarchy between different network coding problems is created with a new theory of combinations and embedding operators.

We consider a transmitter broadcasting random linear combinations (over a field of size d) formed from a block of c packets to a collection of n receivers, where the channels between the transmitter and each receiver are independent erasure channels with reception probabilities q = (q1,..., qn). We establish several properties of the random delay until all n receivers have recovered all c packets, denoted Yn:n(c). First, we provide lower and upper bounds, exact expressions, and a recurrence for the moments of Yn:n(c). Second, we study the delay per packet Yn:n(c)/c as a function of c, including the asymptotic delay (as c → ∞) and monotonicity (in c) properties of the delay per packet. Third, we employ extreme value theory to investigate Yn:n(c)as a function of n (as n → ∞). Several results are new, some results are extensions of existing results, and some results are the proofs of known results using new (probabilistic) proof techniques.

A well-known inner bound of the stability region of the finite-user slotted Aloha protocol (with fixed contention probabilities) on the collision channel with n users assumes worst case service rates (all user queues non-empty). Using this inner bound as a feasible set of achievable rates, a characterization of the throughput-fairness tradeoff over this set is obtained, where the throughput is defined as the sum of the individual user rates, and two definitions of fairness are considered: the Jain-Chiu-Hawe function and the sum-user α-fair (isoelastic) utility function. This characterization is obtained using both an equality constraint and an inequality constraint on the throughput, and properties of the optimal controls, the optimal rates, and the maximum fairness as a function of the target throughput are established. A key structural property underpinning all theorems is the observation that the vector of contention probabilities that extremizes both fairness objectives has its nonzero components taking at most two distinct values.

A well-known inner bound on the stability region of the finite-user slotted Aloha protocol is the set of all arrival rates for which there exists some choice of the contention probabilities such that the associated worst case service rate for each user exceeds the user's arrival rate, denoted Λ. Although testing membership in Λ of a given arrival rate can be posed as a convex program, it is nonetheless of interest to understand the properties of this set. In this paper, we develop new results of this nature, including, 1) an equivalence between membership in Λ and the existence of a positive root of a given polynomial, 2) a method to construct a vector of contention probabilities to stabilize any stabilizable arrival rate vector, 3) the volume of Λ, 4) explicit polyhedral, spherical, and ellipsoid inner and outer bounds on Λ, and 5) characterization of the generalized convexity properties of a natural “excess rate” function associated with Λ, including the convexity of the set of contention probabilities that stabilize a given arrival rate vector.

This article models the temporal adoption dynamics of an abstracted Internet technology or service, where the instantaneous net value of the service perceived by each (current or potential) user/customer incorporates three key features: (i) user service affinity heterogeneity, (ii) a network externality, and (iii) a subscription cost. Internet technologies and services with network externalities face a “chicken-and-egg” adoption problem in that the service requires an established customer base to attract new customers. In this article, we study cost subsidization as a means to “reach the knee,” at which point the externality drives rapid service adoption, and thereby change the equilibrium service fractional adoption level from an initial near-zero level to a final near-one level (full adoption). We present three simple subsidy models and evaluate them under two natural performance metrics: (i) the duration required for the subsidized service to reach a given target adoption level and (ii) the aggregate cost of the subsidy born by the service provide. First, we present a “two-target adoption subsidy” that subsidizes the cost to keep the fraction of users with positive net utility at a (constant) target level until the actual adoption target is reached. Second, we study a special case of the above where the target ensures all users have positive net utility, corresponding to a “quickest adoption” subsidy (QAS). Third, we introduce an approximation of QAS that only requires the service provider adjust the subsidy level a prescribed number of times. Fourth, we study equilibria and their stability under uniformly and normally distributed user service affinities, highlighting the unstable equilibrium in each case as the natural target adoption level for the provider. Finally, we provide a fictional case study to illustrate the application of the results in a (hopefully) realistic scenario, along with a brief discussion of the limitations of the model and analysis.

In this paper we present a self-avoiding walk-jump (SAWJ) algorithm for finding a maximum degree node on a large assortative graph. We offer two contributions: i) we use the theory of absorbing Markov chains to effectively approximate the required search time as a function of the number of nodes, the edge density, and the assortativity, and ii) we measure the performance of our algorithm against competing algorithms (including star sampling) from the literature on the class of assortative Erdos-Renyi (AER) random graphs, and on six real-world large graphs from the Stanford SNAP dataset. In most cases SAWJ significantly outperforms the competing algorithms.

Social networks are naturally modeled as graphs, with edges indicating associations of users, and as such user popularity or influence is captured by the degree of the node corresponding to the user. It is of natural interest to seek maximum degree nodes, i.e., most popular members, in this graph, and as these networks are large, this requires an efficient search algorithm. In this paper we address the problem of finding a maximum degree node (as distinct from finding the maximum degree) in Erdos Renyi (ER) random graphs, where these graphs are ``rewired'' in a way to reach a target assortativity without affecting the marginal degree distribution. We address two questions: i) how many maximum degree nodes are in such a graph, on average, and ii) is it easier to find such a node via a biased random walk (BRW) or via random (star) sampling (RSS)? To answer the first question, we show that large ER graphs possess on average a unique maximum degree node. The answer to the second question is that the superiority of BRW vs. RSS depends critically on the assortativity. In particular, RSS is independent of, and BRW is highly sensitive to, the assortativity. We demonstrate numerically the sensitivity of BRW to assortativity is connected to the prevalence of local maxima; these maxima limit the ability of BRW to follow a gradient on the graph. Finally, we establish how the prevalence of local maxima may be computed from the joint degree distribution of the graph.

We study the application of the protocol interference model, in place of the more complex physical interference model, in order to evaluate transmission success/outage in wireless networks. Under the protocol model a transmission is successful if and only if there are no interferers within a specified guard zone around the receiver. We first recognize that the protocol model, parameterized by a guard zone radius, forms a family of decision rules for estimating the physical model feasibility of a typical transmission. We proceed to cast the problem using a binary hypothesis testing framework. For wireless Poisson networks, we employ stochastic geometry to determine the prior and posterior distributions associated with the estimation problem. We then develop expressions for false rejection (Type I) and false acceptance (Type II) rates associated with the protocol model, and investigate the optimal guard zone minimizing the total probability of error associated with the protocol model.

A key aspect of many resource allocation problems is the need for the resource controller to compute a function, such as the max or arg max, of the competing users' metrics. Information must be exchanged between the competing users and the resource controller in order for this function to be computed. In many practical resource controllers, the competing users' metrics are communicated to the resource controller, which then computes the desired extremization function. However, in this paper, it is shown that information rate savings can be obtained by recognizing that the controller only needs to determine the result of this extremization function. If the extremization function is to be computed losslessly, the rate savings are shown in most cases to be at most 2 b independent of the number of competing users. Motivated by the small savings in the lossless case, simple achievable schemes for both the lossy and interactive variants of this problem are considered. It is shown that both of these approaches have the potential to realize large rate savings, especially in the case where the number of competing users is large. For the lossy variant, it is shown that the proposed simple achievable schemes are in fact close to the fundamental limit given by the rate distortion function.

The study of the optimality of low-complexity greedy scheduling techniques in wireless communications networks is a very complex problem. The Local Pooling (LoP) factor provides a single-parameter means of expressing the achievable capacity region (and optimality) of one such scheme, greedy maximal scheduling (GMS). The exact LoP factor for an arbitrary network graph is generally difficult to obtain, but may be evaluated or bounded based on the network graph's particular structure. In this paper, we provide rigorous characterizations of the LoP factor in large networks modeled as Erdös-Rényi (ER) and random geometric (RG) graphs under the primary interference model. We employ threshold functions to establish critical values for either the edge probability or communication radius to yield useful bounds on the range and expectation of the LoP factor as the network grows large. For sufficiently dense random graphs, we find that the LoP factor is between 1/2 and 2/3, while sufficiently sparse random graphs permit GMS optimality (the LoP factor is 1) with high probability. We then place LoP within a larger context of commonly studied random graph properties centered around connectedness. We observe that edge densities permitting connectivity generally admit cycle subgraphs that form the basis for the LoP factor upper bound of 2/3. We conclude with simulations to explore the regime of small networks, which suggest the probability that an ER or RG graph satisfies LoP and is connected decays quickly in network size.

We study downlink delay minimization within the context of cellular user association policies that map mobile users to base stations. We note the delay minimum user association problem fits within a broader class of network utility maximization and can be posed as a non-convex quadratic program. This non-convexity motivates a split quadratic objective function that captures the original problem's inherent tradeoff: association with a station that provides the highest signal-to-interference-plus-noise ratio (SINR) vs. a station that is least congested. We find the split-term formulation is amenable to linearization by embedding the base stations in a hierarchically well-separated tree (HST), which offers a linear approximation with constant distortion. We provide a numerical comparison of several problem formulations and find that with appropriate optimization parameter selection, the quadratic reformulation produces association policies with sum delays that are close to that of the original network utility maximization. We also comment on the more difficult problem when idle base stations (those without associated users) are deactivated.

Network traffic anomaly detection is now considered a surer approach to early detection of malware than signature-based approaches and is best accomplished with traffic data collected from multiple locations. Existing open-source tools are primarily signature-based, or do not facilitate integration of traffic data from multiple locations for real-time analysis, or are insufficiently modular for incorporation of newly proposed approaches to anomaly detection. In this paper, we describe DataMap, a new modular open-source tool for the collection and real-time analysis of sampled, anonymized, and filtered traffic data from multiple WiFi locations in a network and an example of its use in anomaly detection.

We consider the optimal transmission of distributed correlated discrete memoryless sources across a network with capacity constraints. We present several previously undiscussed structural properties of the set of feasible rates and transmission schemes. These properties are then applied to develop a characterization of an optimal solution and its connection to the corner points of the Slepian-Wolf rate region.

The goal of this article is to develop a principled understanding of when it is beneficial to bundle technologies or services whose value is heavily dependent on the size of their user base, that is, exhibits positive exernalities. Of interest is how the joint distribution, and in particular the correlation, of the values users assign to components of a bundle affect its odds of success. The results offer insight and guidelines for deciding when bundling new Internet technologies or services can help improve their overall adoption. In particular, successful outcomes appear to require a minimum level of value correlation. Categories and Subject Descriptors (2012): Networks -- Network Algorithms -- Network economics; Networks -- Network properties -- Network dynamics; Information systems -- Information systems applications -- Collaborative and social computing systems and tools; Security and privacy -- Human and societal aspects of security and privacy; Human-centered computing -- Collaborative and social computing theory, concepts and paradigms

We introduce a model for capturing the effects of beam misdirection on coverage and throughput in a directional wireless network using stochastic geometry. In networks employing ideal sector antennas without sidelobes, we find that concavity of the orientation error distribution is sufficient to prove monotonicity and quasi-concavity (both with respect to antenna beamwidth) of spatial throughput and transmission capacity, respectively. Additionally, we identify network conditions that produce opposite extremal choices in beamwidth (absolutely directed versus omni-directional) that maximize the two related throughput metrics. We conclude our paper with a numerical exploration of the relationship between mean orientation error, throughput-maximizing beamwidths, and maximum throughput, across radiation patterns of varied complexity.

In this paper, we consider the problem of communicating over an Additive White Gaussian Noise (AWGN) channel with an unknown noise power without feedback. For the case where the noise power is drawn from a distribution with K distinct values, we model the channel as a K-user broadcast channel, with a user for each of the K possible noise powers. We propose two metrics for measuring the loss of using a broadcast code compared to an omniscient transmitter. Using these metrics, we solve for the optimal power allocation in a superposition code. For the case of K = 2, we prove several interesting properties of the optimal power allocation and the minimum loss.

We present a software library that aids in the design of mobile ad hoc networks (MANET). The OMAN design engine works by taking a specification of network requirements and objectives, and allocates resources which satisfy the input constraints and maximize the communication performance objective. The tool is used to explore networking design options and challenges, including: power control, adaptive modulation, flow control, scheduling, mobility, uncertainty in channel models, and cross-layer design. The unaddressed niche which OMAN seeks to fill is the general framework for optimization of any network resource, under arbitrary constraints, and with any selection of multiple objectives. While simulation is an important part of measuring the effectiveness of implemented optimization techniques, the novelty and focus of OMAN is on proposing novel network design algorithms, aggregating existing approaches, and providing a general framework for a network designer to test out new proposed resource allocation methods. In this paper, we present a high-level view of the OMAN architecture, review specific mathematical models used in the network representation, and show how OMAN is used to evaluate tradeoffs in MANET design. Specifically, we cover three case studies of optimization. The first case is robust power control under uncertain channel information for a single physical layer snapshot. The second case is scheduling with the availability of directional radiation patterns. The third case is optimizing topology through movement planning of relay nodes.

The benefit of multi-antenna receivers is investigated in wireless ad hoc networks, and the main finding is that network throughput can be made to scale linearly with the number of receive antennas N_r even if each transmitting node uses only a single antenna. This is in contrast to a large body of prior work in single-user, multiuser, and ad hoc wireless networks that have shown linear scaling is achievable when multiple receive and transmit antennas (i.e., MIMO transmission) are employed, but that throughput increases logarithmically or sublinearly with N_r when only a single transmit antenna (i.e., SIMO transmission) is used. The linear gain is achieved by using the receive degrees of freedom to simultaneously suppress interference and increase the power of the desired signal, and exploiting the subsequent performance benefit to increase the density of simultaneous transmissions instead of the transmission rate. This result is proven in the transmission capacity framework, which presumes single-hop transmissions in the presence of randomly located interferers, but it is also illustrated that the result holds under several relaxations of the model, including imperfect channel knowledge, multihop transmission, and regular networks (i.e., interferers are deterministically located on a grid).

A method for checking membership in the region of entropic vectors generated fromNbits is presented. A general technique for utilizing this method to create inner bounds for regions of entropic vectors as a function of outer bounds is then presented. These two algorithms are then used to provide new insights regarding relationships among well known bounds for the region of entropic vectors..

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. Most prior work on finding the transmission capacity of ad-hoc networks has focused only on one-way communication where a source communicates with a destination and no data is sent from the destination to the source. In practice, however, two-way or bidirectional data transmission is required to support control functions like packet acknowledgements and channel feedback. This paper extends the concept of transmission capacity to two-way wireless ad-hoc networks by incorporating the concept of a two-way outage with different rate requirements in both directions. Tight upper and lower bounds on the two-way transmission capacity are derived for frequency division duplexing. The obtained bounds are used to derive the optimal solution for bidirectional bandwidth allocation that maximizes the two-way transmission capacity, which is shown to perform better than allocating bandwidth proportional to the desired rate in both directions. Using the proposed two-way transmission capacity framework, a lower bound on the two-way transmission capacity with transmit beamforming using limited feedback is derived as a function of bandwidth and the number of bits allocated for feedback.

The transmission capacity of an ad-hoc network is the maximum density of active transmitters in a unit area, given an outage constraint at each receiver for a fixed rate of transmission. Most prior work on finding the transmission capacity of ad-hoc networks has focused only on one-way communication where a source communicates with destination and no data is sent from destination to the source. In practice, however, two-way or bidirectional data transmission is required to support control functions like packet acknowledgements and channel feedback. This paper develops the concept of transmission capacity for two-way wireless ad-hoc networks, by incorporating the concept of a two-way outage with different rate requirements in both directions. Upper and lower bounds on the two-way transmission capacity are derived for frequency division duplexing, under the assumption that the channel coefficients are independent on different carrier frequencies. The derived bounds are used to derive the optimal solution for bidirectional bandwidth allocation that maximizes the two-way transmission capacity, which is shown to perform better than allocating bandwidth proportional to the desired rate in both directions.

Most bounds on the stability region of Aloha give necessary and sufficient conditions for the stability of an arrival rate vector under a specific contention probability (control) vector. But such results do not yield easy-to-check bounds on the overall Aloha stability region because they potentially require checking membership in an uncountably infinite number of sets parameterized by each possible control vector. In this paper we consider an important specific inner bound on Aloha that has this property of difficulty to check membership in the set. We provide ellipsoids (for which membership is easy-to-check) that we conjecture are inner and outer bounds on this set. We also study the set of controls that stabilize a fixed arrival rate vector; this set is shown to be a convex set.

This paper surveys and unifies a number of recent contributions that have collectively developed a metric for decentralized wireless network analysis known as transmission capacity. Although it is notoriously difficult to derive general end-to-end capacity results for multi-terminal or adhoc networks, the transmission capacity (TC) framework allows for quantification of achievable single-hop rates by focusing on a simplified physical/MAC-layer model. By using stochastic geometry to quantify the multi-user interference in the network, the relationship between the optimal spatial density and success probability of transmissions in the network can be determined, and expressed-often fairly simply-in terms of the key network parameters. The basic model and analytical tools are first discussed and applied to a simple network with path loss only and we present tight upper and lower bounds on transmission capacity (via lower and upper bounds on outage probability). We then introduce random channels (fading/shadowing) and give TC and outage approximations for an arbitrary channel distribution, as well as exact results for the special cases of Rayleigh and Nakagami fading. We then apply these results to show how TC can be used to better understand scheduling, power control, and the deployment of multiple antennas in a decentralized network. The paper closes by discussing shortcomings in the model as well as future research directions.

We develop a new metric for quantifying end-to-end throughput in multihop wireless networks, which we term random access transport capacity, since the interference model presumes uncoordinated transmissions. The metric quantifies the average maximum rate of successful end-to-end transmissions, multiplied by the communication distance, and normalized by the network area. We show that a simple upper bound on this quantity is computable in closed-form in terms of key network parameters when the number of retransmissions is not restricted and the hops are assumed to be equally spaced on a line between the source and destination. We also derive the optimum number of hops and optimal per hop success probability and show that our result follows the well-known square root scaling law while providing exact expressions for the preconstants, which contain most of the design-relevant network parameters. Numerical results demonstrate that the upper bound is accurate for the purpose of determining the optimal hop count and success (or outage) probability.

The benefit of multiple antenna communication is investigated in wireless ad hoc networks, and the primary finding is that throughput can be made to scale linearly with the number of receive antennas even if each transmitting node uses only a single antenna. The linear throughput gain is achieved by (i) using the receive antennas to cancel the signals of nearby interferers as well as to increase signal power (i.e., for array gain), and (ii) maintaining a constant per-link rate and increasing the spatial density of simultaneous transmissions linearly with the number of antennas at each receiver. Numerical results show that even a few receive antennas provide substantial throughput gains, thereby illustrating that the asymptotic linear scaling result is also indicative of performance for reasonable numbers of antennas.

Wireless ad hoc networks require bidirectional data transmission to support two-way traffic and control functions like packet acknowledgement. Most prior work on the capacity of wireless ad hoc networks, however, has focused only on one-way communication. In this paper we develop the concept of transmission capacity of two-way communication in wireless ad hoc networks. The transmission capacity has been used extensively to analyze one-way ad hoc networks - in this paper we provide a generalization that incorporates the concept of a two- way outage. We derive an upper bound and an approximation for the two-way transmission capacity, which are shown to be relatively tight for small outage probability constraints. We also quantify how the two-way success requirement reduces network capacity. Our numerical and simulation results show that for certain two-way networks the capacity loss is considerable.

Via multiterminal information theory, a framework is presented for deriving fundamental rate–delay tradeoffs that delay mitigating codes must have when utilized over multipath routed and random linear network coded networks. The rate–delay tradeoff is formulated as a calculus problem on a capacity region of a related abstracted broadcast channel. Given this general framework for studying such rate–delay tradeoffs, the extreme case of uniform networks, in which each possible received packet arrival order is equally likely, is considered. For these networks, the rate–delay calculus problem is simplified to an integer programming problem, which for small numbers of packets may be solved explicitly, or for larger numbers of packets, may be accurately approximated through the calculus of variations by appropriate relaxation of an integer constraint. Explicit expressions for the rate–delay tradeoff in uniform networks are presented in the special cases of i) constant packet inter-arrival times, and ii) exponential independent and identically distributed (i.i.d.) packet arrival times. Finally, the delay mitigating codes achieving these rate–delay tradeoffs are discussed.

The multihop spatial reuse Aloha (MSR-Aloha) protocol was recently introduced by Baccelli et aL, where each transmitter selects the receiver among its feasible next hops that maximizes the forward progress of the head of line packet towards its final destination. They identify the optimal medium access probability (MAP) that maximizes the spatial density of progress, defined as the product of the spatial intensity of attempted transmissions times the average per-hop progress of each packet towards its destination. We propose a variant called longest edge routing where each transmitter selects its longest feasible edge, and then identifies a packet in its backlog whose next hop is the associated receiver. The main contribution of this work (and of Baccelli et aL) is the use of stochastic geometry to identify the optimal MAP and the corresponding optimal spatial density of progress.

Via multiterminal information theory, we present fundamental rate delay tradeoffs that delay mitigating codes must have when utilized over multipath routed and network coded networks. We formulate plotting the rate delay tradeoff as a calculus problem on a capacity region of a related abstracted broadcast channel. This calculus problem simplifies to an integer programming problem, which for small numbers of packets may be solved explicitly, or for larger values of packets, may be accurately approximated through the calculus of variations by relaxing the integer constraint. We prove the utility of our techniques by plotting the rate delay tradeoff for networks in which the packets experience independent exponentially distributed propagation and queuing delays while traversing the network.

The broadcast capacity of a wireless sensor network (WSN) is defined as the maximum rate at which the network may generate messages intended for distribution to the entire network. Broadcast capacity is limited by factors such as communication collisions and excessive queue lengths incurred under heavy loads. Collisions may be avoided through the use of communication coordination (CC), and excessive queue lengths may be avoided through information coordination (IC), ensuring that only useful messages are transmitted and stored. Our communication model takes into consideration channel variations (using Rayleigh fading) and interference due to overlapping transmissions. Any node's transmission can potentially reach every other node in the network, provided that the received signal to interference plus noise ratio (SINR) at the receiver is above a certain threshold. Our results show the benefits of IC and CC as well as the tradeoffs in terms of the cost incurred when using these mechanisms.

This paper derives the outage probability and transmission capacity of ad hoc wireless networks with nodes employing multiple antenna diversity techniques, for a general class of signal distributions. This analysis allows system performance to be quantified for fading or non-fading environments. The transmission capacity is given for interference-limited uniformly random networks on the entire plane with path loss exponent alpha > 2 in which nodes use: (1) static beamforming through M sectorized antennas, for which the increase in transmission capacity is shown to be thetas(M2) if the antennas are without sidelobes, but less in the event of a nonzero sidelobe level; (2) dynamic eigenbeamforming (maximal ratio transmission/combining), in which the increase is shown to be thetas(M2/alpha); (3) various transmit antenna selection and receive antenna selection combining schemes, which give appreciable but rapidly diminishing gains; and (4) orthogonal space-time block coding, for which there is only a small gain due to channel hardening, equivalent to Nakagami-m fading for increasing m. It is concluded that in ad hoc networks, static and dynamic beamforming perform best, selection combining performs well but with rapidly diminishing returns with added antennas, and that space-time block coding offers only marginal gains.

This paper addresses the following question, which is of interest in the design of a multiuser decentralized network. Given a total system bandwidth of W Hz and a fixed data rate constraint of R bps for each transmission, how many frequency slots N of size W/N should the band be partitioned into in order to maximize the number of simultaneous links in the network? Dividing the available spectrum results in two competing effects. On the positive side, a larger N allows for more parallel, non- interfering communications to take place in the same area. On the negative side, a larger N increases the SINR requirement for each link because the same information rate must be achieved over less bandwidth. Exploring this tradeoff and determining the optimum value of N in terms of the system parameters is the focus of the paper. Using stochastic geometry, the optimal SINR threshold - which directly corresponds to the optimal spectral efficiency - is derived for both the low SNR (power-limited) and high SNR (interference-limited) regimes. This leads to the optimum choice of the number of frequency bands N in terms of the path loss exponent, power and noise spectral density, desired rate, and total bandwidth.

We consider a new approach to power control in decentralized wireless networks, termed fractional power control (FPC). Transmission power is chosen as the current channel quality raised to an exponent -s, where s is a constant between 0 and 1. The choices s = 1 and s = 0 correspond to the familiar cases of channel inversion and constant power transmission, respectively. Choosing s isin (0,1) allows all intermediate policies between these two extremes to be evaluated, and we see that usually neither extreme is ideal. We derive closed-form approximations for the outage probability relative to a target SINR in a decentralized (ad hoc or unlicensed) network as well as for the resulting transmission capacity, which is the number of users/m2that can achieve this SINR on average. Using these approximations, which are quite accurate over typical system parameter values, we prove that using an exponent of s* = 1/2 minimizes the outage probability, meaning that the inverse square root of the channel strength is a sensible transmit power scaling for networks with a relatively low density of interferers. We also show numerically that this choice of s is robust to a wide range of variations in the network parameters. Intuitively, s* = 1/2 balances between helping disadvantaged users while making sure they do not flood the network with interference.

Path planning and network design are often treated by architects of mobile communication networks as separate problems. In fact, most mobile ad hoc network (MANET) designs do not consider the path that the network nodes would take as part of the objective set, but incorporate them in an abstract form as general constraints on mobility (limit on the initial configuration and the node velocity). It appears that significant performance improvement may be possible if multiobjective optimization is attempted on performance indices such as connectivity of the network and arrival time of all nodes at a specified terminal set. In this study we provide an efficient decentralized method for computing the Pareto optimal set of plans, and show the benefit of path planning under six different metrics of MANET performance.

This paper derives the exact outage probability and transmission capacity of ad hoc wireless networks with nodes employing multiple antenna diversity techniques. The analysis enables a direct comparison of the number of simultaneous transmissions achieving a certain data rate under different diversity techniques. Preliminary results derive the outage probability and transmission capacity for a general class of signal distributions which facilitates quantifying the gain for fading or non-fading environments. The transmission capacity is then given for uniformly random networks with path loss exponent alpha > 2 in which nodes: (1) perform maximal ratio transmission/combining on M antennas with Theta(M 2/alpha ) gains; (2) various antenna selection combining schemes which give appreciable but rapidly diminishing gains; and (3) orthogonal space-time block coding, for which there is only a small gain due to channel hardening. It is concluded that in ad hoc networks, beamforming performs best, selection combining performs well for smaller numbers of antennas, and that space-time block coding offers only marginal gains.

This paper addresses the following question, which is of interest in the design of a multiuser decentralized network: given a total system bandwidth of W Hz and a fixed data rate constraint of R bps for each transmission, how many frequency slots N of size W/N should the band be partitioned into to maximize the number of simultaneous transmissions in the network? Dividing the available spectrum reduces the number of users on each band and therefore decreases multiuser interference level, but also increases the SINR requirement for each transmission because the same information rate must be achieved over a smaller bandwidth. Exploring this tradeoff between bandwidth and SINR and determining the optimum value of N in terms of the system parameters is the focus of the paper. Using stochastic geometry, we analytically derive the optimal SINR threshold on this tradeoff curve and show that it is a function of only the path loss exponent. Furthermore, the optimal SINR point lies between the low-SINR (power-limited) and high-SINR (bandwidth-limited) regimes.

This paper addresses three issues in the field ofad hocnetwork capacity: the impact of (i) channel fading, (ii) channel inversion power control, and (iii) threshold–based scheduling on capacity. Channel inversion and threshold scheduling may be viewed as simple ways to exploit channel state information (CSI) without requiring cooperation across transmitters. We use thetransmission capacity(TC) as our metric, defined as the maximum spatial intensity of successful simultaneous transmissions subject to a constraint on the outage probability (OP). By assuming the nodes are located on the infinite plane according to a Poisson process, we are able to employ tools from stochastic geometry to obtain asymptotically tight bounds on the distribution of the signal-to-interference (SIR) level, yielding in turn tight bounds on the OP (relative to a given SIR threshold) and the TC. We demonstrate that in the absence of CSI, fading can significantly reduce the TC and somewhat surprisingly, channel inversion only makes matters worse. We develop a threshold-based transmission rule where transmitters are active only if the channel to their receiver is acceptably strong, obtain expressions for the optimal threshold, and show that this simple, fully distributed scheme can significantly reduce the effect of fading.

The transmission capacity (TC) of a wirelessad hocnetwork is defined as the maximum spatial intensity of successful transmissions such that the outage probability does not exceed some specified threshold. This work studies the improvement in TC obtainable with successive interference cancellation (SIC), an important receiver technique that has been shown to achieve the capacity of several classes of multiuser channels, but has not been carefully evaluated in the context ofad hocwireless networks. This paper develops closed-form upper bounds and easily computable lower bounds for the TC ofad hocnetworks with SIC receivers, for both perfect and imperfect SIC. The analysis applies to any multiuser receiver that cancels the$K$strongest interfering signals by a factor$z \in [0,1]$. In addition to providing the first closed-form capacity results for SIC inad hocnetworks, design-relevant insights are made possible. In particular, it is shown that SIC should be used with direct sequence spread spectrum. Also, any imperfections in the interference cancellation rapidly degrade its usefulness. More encouragingly, only a few—often just one—interfering nodes need to be canceled in order to get the vast majority of the available performance gain.

We provide closed form upper and lower bounds on the distribution of the signal to interference ratio (SIR) seen by a typical receiver in an ad hoc network where transmitter locations form a Poisson process. The aggregate co-channel interference in such a network is known to be a power law shot noise process and the distribution is known to be symmetric stable; we will show the same is true of the SIR. Stable distributions are unwieldy in that there is no closed form expression for their PDF and CDF; this is the motivation behind seeking simple bounds on the SIR. We consider a broad class of channel models that have a deterministic, distance dependent path-loss component and a random, distance-independent component. This class of channel models includes lognormal shadowing, Rayleigh fading, the Nakagami model, and others. We show that the lower bound on SIR is tight and that the upper bound has a bounded error that depends on the path loss exponent but not on the random channel variation. Numerical plots of the SIR distribution for a variety of common channel models are provided to illustrate the bounds. The bounds are useful for computing common network performance metrics like outage probability and BER.

Preemption and adaptation are two common techniques for controlling inelastic traffic such as streaming media. Adaptation policies dynamically increase or decrease the transmission rate of the stream in response to the presence or absence of network congestion. On the other hand, preemption policies select streams to be removed from the congested route. The removed streams may be rerouted through less favorable paths in the network. Adaptation causes a "virtual increase in network capacity" at the cost of reducing the client perceived stream quality (since rate reduction is achieved through lossy compression). Preemption permits improved blocking probabilities and traffic alignment on shortest paths for high priority traffic at the expense of performance degradation for low priority traffic. In this paper, we demonstrate the aforementioned performance trade-offs and the increased efficacy of control achievable through the combined use of preemption and adaptation policies.

We investigate four performance metrics for randomized broadcast protocols on sensor networks: the fraction of nodes that receive the message (coverage), the number of first-time receivers per transmission (energy efficiency), the node-average normalized time till reception (per hop latency), and the average number of control messages per node (overhead). Our focus is to evaluate the extent to which the exchange of local information (either active or passive) can improve protocol performance. To this end we study via simulation three protocols from the literature that exploit local information (GOSSIP3 from [8], SPIN-1 from [10], and PUSH&PULL from [12])and compare their performance against the well known GOSSIP1 ([8]) protocol which does not employ any local information in making transmission decisions. Our findings are that i) local information is of course quite valuable in increasing protocol performance, and ii) it is possible to obtain high coverage and efficiency but one must then incur either increased delay or increased overhead. We study the strengths and weaknesses of the above protocols and propose the new SmartGossip protocol which combines several ideas from the above protocols, as well as several new mechanisms, to achieve superior performance.

In this paper, upper and lower bounds on the transmission capacity of spread-spectrum (SS) wireless ad hoc networks are derived. We define transmission capacity as the product of the maximum density of successful transmissions multiplied by their data rate, given an outage constraint. Assuming that the nodes are randomly distributed in space according to a Poisson point process, we derive upper and lower bounds for frequency hopping (FH-CDMA) and direct sequence (DS-CDMA) SS networks, which incorporate traditional modulation types (no spreading) as a special case. These bounds cleanly summarize how ad hoc network capacity is affected by the outage probability, spreading factor, transmission power, target signal-to-noise ratio (SNR), and other system parameters. Using these bounds, it can be shown that FH-CDMA obtains a higher transmission capacity than DS-CDMA on the order of M/sup 1-2//spl alpha//, where M is the spreading factor and /spl alpha/>2 is the path loss exponent. A tangential contribution is an (apparently) novel technique for obtaining tight bounds on tail probabilities of additive functionals of homogeneous Poisson point processes.

This work investigates support of rate adaptive multimedia streams on communication networks. Optimal and practical mechanisms to maximize the customer average quality of service (QoS), defined in terms of a normalized time average received rate, are established. By scaling the arrival rate and link capacity, we obtain asymptotic expressions for customer average QoS in the case of networks with single bottleneck links. The optimal adaptation policy is identified as the solution to an integer program which has an intuitive "sort by volume" interpretation for the case of single bottleneck links, where stream volume is the total number of bits associated with a stream at its maximum resolution. Our asymptotic analysis shows the optimal adaptation policy may yield performance improvements of up to 42% over baseline policies. We demonstrate that a static multi-class admission control policy can achieve the same asymptotic QoS as that of the optimal adaptation policy. This implies that dynamic adaptation may be unnecessary for large capacity networks with appropriate call admission.

Upper and lower bounds on the transmission capacity of direct-sequence CDMA wireless ad hoc networks are derived. The transmission capacity is a stochastic measure of the allowable number of transmissions per unit area, and is a generalization of previous measures of ad hoc network capacity. Successive interference cancellation (SIC) is attractive for DS-CDMA ad hoc networks since the dominant nearby interferers can be cancelled. Our closed-form results cleanly summarize the dependence of ad hoc network capacity on pathloss, spreading, outage probability, and interference cancellation accuracy. Other multiple access schemes, such as CSMA and DS-CDMA without SIC, are special cases. Perfect interference cancellation increases transmission capacity by nearly two orders of magnitude. Furthermore, cancelling just the strongest interferer generally gives the majority of the capacity gain, so the latency and complexity cost of SIC should be negligible.

Rate adaptive multimedia streams offer significant system and client benefits over nonadaptive streams. These benefits come at the price of increased complexity in providing adequate network support and difficulty in understanding how rate adaptation protocols affect client perceived QoS. In this paper we define quality of service in terms of the mean rate seen by the client. We identify an intuitive optimal adaptation policy that maximizes QoS. We suggest an appropriate scaling regime for rate adaptive streams and identify asymptotic QoS for large capacity networks under the optimal adaptation policy. Implementation of the optimal adaptation policy presents several obstacles that render it infeasible. We define a multiclass admission control policy that achieves asymptotically equivalent QoS to that achieved under the optimal adaptation policy, but without the need for dynamic adaptation. Our work carries implications for network designers and content providers.

We propose a new synthetic trace generation methodology for web server performance benchmarking. We discuss the two primary existing approaches to synthetic trace generation in terms of queueing models. We propose a new methodology as the natural combination of these two approaches. This hybrid approach permits natural modeling of client content and server session caching as well as a natural correspondence between the workload model parameters and the statistics of the resulting synthetic trace.