In wireless communications, the desired wireless signal is typically decoded by treating the sum of all the other ongoing signal transmissions as noise. In the networking literature, this phenomenon is typically abstracted using a wireless channel interference model. The level of detail in the interference model, evidently determines the accuracy of the results based upon the model. Several works in the networking literature have made use of simplistic interference models, e.g., fixed ranges for communication and interference, the capture threshold model (used in the ns2 network simulator), the protocol model, and so on. At the same time, fairly complex interference models such as those based on the SINR (signal-to-interference-and-noise ratio) have also been proposed and used. We investigate the impact of the choice of the interference model, on the conclusions that can be drawn regarding the performance of wireless networks, by comparing different wireless interference models. We find that both in the case of random access networks, as well as in the case of scheduled networks (where node transmissions are scheduled to be completely conflict-free), different interference models can produce significantly different results. Therefore, a lot of caution should be exercised before accepting or interpreting results based on simplified interference models. Further, we feel that an SINR-based model is the minimum level of detail that should be employed to model wireless channel interference in a networking context.

We consider a scenario in which a wireless sensor network is formed by randomly deploying n sensors to measure some spatial function over a field, with the objective of computing a function of the measurements and communicating it to an operator station. We restrict ourselves to the class of type-threshold functions (as defined in the work of Giridhar and Kumar, 2005), of which max, min, and indicator functions are important examples: our discussions are couched in terms of the max function. We view the problem as one of message-passing distributed computation over a geometric random graph. The network is assumed to be synchronous, and the sensors synchronously measure values and then collaborate to compute and deliver the function computed with these values to the operator station. Computation algorithms differ in (1) the communication topology assumed and (2) the messages that the nodes need to exchange in order to carry out the computation. The focus of our paper is to establish (in probability) scaling laws for the time and energy complexity of the distributed function computation over random wireless networks, under the assumption of centralized contention-free scheduling of packet transmissions. First, without any constraint on the computation algorithm, we establish scaling laws for the computation time and energy expenditure for one-time maximum computation. We show that for an optimal algorithm, the computation time and energy expenditure scale, respectively, as Theta(radicn/log n) and Theta(n) asymptotically as the number of sensors n rarr infin. Second, we analyze the performance of three specific computation algorithms that may be used in specific practical situations, namely, the tree algorithm, multihop transmission, and the Ripple algorithm (a type of gossip algorithm), and obtain scaling laws for the computation time and energy expenditure as n rarr infin. In particular, we show that the computation time for these algorithms scales as Theta(radicn/log n), Theta(n), and Theta(radicn log n), respectively, whereas the energy expended scales as , Theta(n), Theta(radicn/log n), and Theta(radicn log n), respectively. Finally, simulation results are provided to show that our analysis indeed captures the correct scaling. The simulations also yield estimates of the constant multipliers in the scaling laws. Our analyses throughout assume a centralized optimal scheduler, and hence, our results can be viewed as providing bounds for the performance with practical distributed schedulers.

Scheduled wireless mesh networks (WMNs) represent an important paradigm in the development of high speed wireless access networks. As a consequence of (Aditya Karnik, 2006), it can be shown that the maximum throughput of a single gateway n node WMN is upper-bounded by 1/n, normalized with respect to the highest available data-rate. The situation is actually worse since with conventional omni-directional antennas, the achievable throughput is considerably lower at low powers. This paper makes a case for smart (directional) antennas. For the same power, smart antennas can provide higher range, and therefore shorter paths, as compared to omni-directional antennas. For the same range, smart antennas can operate at lower powers, reducing the interference, and thereby improving the spatial reuse. Although they cannot change the fundamental throughput limit of 1/n, smart antennas can achieve significantly higher throughput at lower powers, These insights are demonstrated through several numerical examples using the framework of (Aditya Karnik, 2006).

In a wireline network, nodes form links with only those nodes they are wired to, and the links do not interfere with one another. In contrast, in a wireless network, signal transmissions are intrinsically broadcast, and suffer from mutual interference. In several physical layer technologies, a wireless signal is decoded by treating the sum of all the other on-going signal transmissions as noise. Hence, from a networking standpoint, there is a need to model wireless channel interference. An accurate interference model is especially important in a multi-hop network context, since there could be several simultaneous wireless transmissions. Several works in the literature have made use of simplified interference models. Some works assume a fixed range for communication and interference, while others are based on concepts like capture threshold where the desired signal strength is compared with interference from a single node at a time, rather than cumulatively. In particular, the latter model is used in ns2 which is the most common simulation tool. Under isotropic pathloss, the capture threshold model is also equivalent to the protocol model proposed by Gupta and Kumar, which is now the subject of a lot of analytical activity notably through conflict graph based problem formulations. We investigate the accuracy and appropriateness of the capture threshold based interference model, by comparing it with one based on the SINR (signal-to-interference-and-noise ratio) with additive interference calculation. We find that both in the case of random access networks, as well as in the case of scheduled networks (where node transmissions are scheduled to be completely conflict-free), a simplified interference model such as the capture threshold model, can produce significantly different results compared to an additive interference based model. Therefore, a lot of caution should be exercised before accepting or interpreting results based on simplified interference models.

Motivated by the estimation of spatio-temporal events with cheap, simple sensors, we consider the problem of estimation of a parameter $\theta$ of a signal $s(x;\theta)$ corrupted by noise assuming that only 1-bit precision dithered quantized samples are available. An estimate that does not require the knowledge of the dither signal and the noise distribution is proposed, and it is analyzed in detail under variety of nonidealities. The consistency and asymptotic normality of the estimate is established for deterministic and random sampling, imprecise knowledge of sampling locations, Gaussian and non-Gaussian noise (with possibly infinite variance), a wide class of dither distributions, and under erroneous transmission of the binary observations via binary-symmetric channels (BSCs). It is also shown that if approximation to the log-likelihood equation in the full precision case yields a good estimate, then there is a corresponding good estimate based on 1-bit dithered samples. The proposed estimate requires no more computation than the maximum-likelihood estimate for the full precision case and suffers only a logarithmic rate loss compared to the full precision case when uniform dithering is used. It is shown that uniform dithering leads to the best rate among a broad class of dither distributions. A condition under which no dithering leads to a better estimate is also given.

We consider a scenario where a wireless sensor network is formed by randomly deploying n sensors to measure some spatial function over a field, with the objective of computing the maximum value of the measurements and communicating it to an operator station. We view the problem as one of message passing distributed computation over a geometric random graph. The network is assumed to be synchronous; at each sampling instant each sensor measures a value, and then the sensors collaboratively compute and deliver the maximum of these values to the operator station. Computation algorithms differ in the messages they need to exchange, and our formulation focuses on the problem of scheduling of the message exchanges. We do not exploit techniques such as source compression, or block coding of the computations. For this problem, we study the computation time and energy expenditure for one time maximum computation, and also the pipeline throughput. We show that, for an optimal algorithm, the computation time, energy expenditure and the achievable rate of computation scale as /spl Theta/(/spl radic/ n/log n), /spl Theta/(n) and /spl Theta/(1/log n) asymptotically (in probability) as the number of sensors n/spl rarr//spl infin/. We also analyze the performance of three specific computational algorithms, namely, the tree algorithm, multihop transmission, and the ripple algorithm, and obtain scaling laws for the computation time and energy expenditure as n/spl rarr//spl infin/. Simulation results are provided to show that our analysis indeed captures the correct scaling; the simulations also yield estimates of the constant multipliers in the scaling laws. Our analyses throughout assume a centralized scheduler and hence our results can be viewed as providing bounds for the performance with a distributed scheduler.

We consider a modification of TCP congestion control in which the congestion window is adapted to explicit bottleneck rate feedback; we call this RATCP (Rate Adaptive TCP). Our goal in this paper is to study and compare the performance of RATCP and TCP in various network scenarios with a view to understanding the possibilities and limits of providing better feedback to TCP than just implicit feedback via packet loss. To understand the dynamics of rate feedback and window control, we develop and analyze a model for a long-lived RATCP (and TCP) session that gets a time-varying rate on a bottleneck link. We also conduct experiments on a Linux based test-bed to study issues such as fairness, random losses, and randomly arriving short file transfers. We find that the analysis matches well with the results from the test-bed. For large file transfers, under low background load, ideal fair rate feedback improves the performance of TCP by 15%-20%. For small randomly arriving file transfers, though RATCP performs only slightly better than TCP it reduces losses and variability of throughputs across sessions. RATCP distinguishes between congestion and corruption losses, and ensures fairness for sessions with different round trip times sharing the bottleneck link. We believe that rate feedback mechanisms can be implemented using distributed flow control and recently proposed REM in which case, ECN bit itself can be used to provide the rate feedback.

The work in this paper is motivated by the idea of using randomly deployed, ad hoc wireless networks of miniature smart sensors to serve as distributed instrumentation. We argue that in such applications it is important for the sensors to self-organise in a way that optimizes network throughput. We then identify and discuss two main problems of optimal self-organisation: (i) building an optimal topology, and (ii) tuning network access parameters such as the transmission attempt rate. We consider a simple random access model for sensor networks and formulate these problems as optimisation problems. We then present centralized as well as distributed algorithms for solving them. Results show that the performance improvement is substantial and implementation of such optimal self-organisation techniques may be worth the additional complexity.

Motivated by TCP over end-to-end ABR, we study the performance of adaptive window congestion control, when it operates over an explicit feedback rate-control mechanism, in a situation in which the bandwidth available to the elastic traffic is stochastically time varying. It is assumed that the sender and receiver of the adaptive window protocol are colocated with the rate-control endpoints. The objective of the study is to understand if the interaction of the rate-control loop and the window-control loop is beneficial for end-to-end throughput, and how the parameters of the problem (propagation delay, bottleneck buffers, and rate of variation of the available bottleneck bandwidth) affect the performance. The available bottleneck bandwidth is modeled as a two-state Markov chain. We develop an analysis that explicitly models the bottleneck buffers, the delayed explicit rate feedback, and TCP's adaptive window mechanism. The analysis, however, applies only when the variations in the available bandwidth occur over periods larger than the round-trip delay. For fast variations of the bottleneck bandwidth, we provide results from a simulation on a TCP testbed that uses Linux TCP code, and a simulation/emulation of the network model inside the Linux kernel. We find that, over end-to-end ABR, the performance of TCP improves significantly if the network bottleneck bandwidth variations are slow as compared to the round-trip propagation delay. Further, we find that TCP over ABR is relatively insensitive to bottleneck buffer size. These results are for a short-term average link capacity feedback at the ABR level (INSTCAP). We use the testbed to study EFFCAP feedback, which is motivated by the notion of the effective capacity of the bottleneck link. We find that EFFCAP feedback is adaptive to the rate of bandwidth variations at the bottleneck link, and thus yields good performance (as compared to INSTCAP) over a wide range of the rate of bottleneck bandwidth variation. Finally, we study if TCP over ABR, with EFFCAP feedback, provides throughput fairness even if the connections have different round-trip propagation delays.