Decentralized Coding Algorithms for Distributed Storage in Wireless Sensor Networks

We consider large-scale wireless sensor networks with η nodes, out of which κ are in possession, (e.g., have sensed or collected in some other way) κ information packets. In the scenarios in which network nodes are vulnerable because of, for example, limited energy or a hostile environment, it is desirable to disseminate the acquired information throughout the network so that each of the η nodes stores one (possibly coded) packet so that the original κ source packets can be recovered, locally and in a computationally simple way from any κ(1 + ϵ) nodes for some small ϵ > 0. We develop decentralized Fountain codes based algorithms to solve this problem. Unlike all previously developed schemes, our algorithms are truly distributed, that is, nodes do not know η, κ or connectivity in the network, except in their own neighborhoods, and they do not maintain any routing tables.     

Expected interference in wireless networks with geometric path loss: a closed-form approximation

In this letter, we derive 2λπP/((α - 2)g^{(α - 2)} as a closed-form approximation of the expected interference around a receiver in wireless networks. We use a geometric path loss model, assume that nodes are randomly distributed, and that only nodes outside a guard zone around the receiver simultaneously transmit. The derived solution depends on the path loss exponent α, node density λ, transmission power per node P, and the radius g of the guard zone. The simplicity of this solution makes it widely applicable in wireless network analysis.     

Optimal Unicast Capacity of Random Geometric Graphs: Impact of Multipacket Transmission and Reception

We establish a tight max-flow min-cut theorem for multi-commodity routing in random geometric graphs. We show that, as the number of nodes in the network n tends to infinity, the maximum concurrent flow (MCF) and the minimum cut-sparsity scale as θ(n²r³(n)/k), for a random choice of k = ω(n) source-destination pairs, where n and r(n) are the number of nodes and the communication range in the network respectively. The MCF equals the interference-free capacity of an ad-hoc network. We exploit this fact to develop novel graph theoretic techniques that can be used to deduce tight order bounds on the capacity of ad-hoc networks. We generalize all existing capacity results reported to date by showing that the per-commodity capacity of the network scales as θ(1/r(n)k) for the single-packet reception model suggested by Gupta and Kumar, and as θ(nr(n)/k) for the multiple-packet reception model suggested by others. More importantly, we show that, if the nodes in the network are capable of (perfect) multiple-packet transmission (MPT) and reception (MPR), then it is feasible to achieve the optimal scaling of θ(n²r³(n)/k), despite the presence of interference. In comparison to the Gupta-Kumar model, the realization of MPT and MPR may require the deployment of a large number of antennas at each node or bandwidth expansion. Nevertheless, in stark contrast to the existing literature, our analysis presents the possibility of actually increasing the capacity of ad-hoc networks with n even while the communication range tends to zero!     

Upper tail of distribution of power received from many sources

Consider the total power received from many identical, randomly scattered RF sources in a plane (that is, in Poisson fashion). If RF propagation follows a power law model with exponent α > 2, the right tail of the probability distribution approximately follows a Pareto distribution with exponent 2/α.     

End-to-end delay in wireless random networks

The focus of this letter is to derive a scaling law for the ene-to-end delay of wireless random networks under node mobility, where n nodes randomly move with the speed of v. To that end, we apply the cover time analysis and relate it to the delay scaling law. As a result, we derive that the mean delay per S-D pair as θ(n) or θ(√n÷v), and the worst case delay is θ(n log n) or θ(√log n÷v), corresponding to one slot time length that is either constant or 1÷v√n .     

On Unbounded Path-Loss Models: Effects of Singularity on Wireless Network Performance

This paper addresses the following question: how reliable is it to use the unbounded path-loss model G(d) = d^?α, where α is the path-loss exponent, to model the decay of transmitted signal power in wireless networks? G(d) is a good approximation for the path-loss in wireless communications for large values of d but is not valid for small values of d due to the singularity at 0. This model is often used along with a random uniform node distribution, even though in a group of uniformly distributed nodes some may be arbitrarily close to one another. The unbounded path-loss model is compared to a more realistic bounded path-loss model, and it is shown that the effect of the singularity on the total network interference level is significant and cannot be disregarded when nodes are uniformly distributed. A phase transition phenomenon occurring in the interference behavior is analyzed in detail. Several performance metrics are also examined by using the computed interference distributions. In particular, the effects of the singularity at 0 on bit error rate, packet success probability and wireless channel capacity are analyzed.     

On the connectivity in finite ad hoc networks

Connectivity and capacity analysis of ad hoc networks has usually focused on asymptotic results in the number of nodes in the network. In this letter we analyze finite ad hoc networks. With the standard assumption of uniform distribution of nodes in [0, z], z > 0, for a one-dimensional network, we obtain the exact formula for the probability that the network is connected. We then extend this result to find bounds for the connectivity in a two-dimensional network in [0, z]²     

Impacts of Topology and Traffic Pattern on Capacity of Hybrid Wireless Networks

In this paper, we investigate the throughput capacity in wireless hybrid networks with various network topologies and traffic patterns. Specifically, we consider n randomly distributed nodes, out of which there are n source nodes and n^d (0≪d≪1) randomly chosen destination nodes, together with n^b (0≪b≪1) base stations in a network area of [0, n^w]times [0, n^{1-w}] (0≪w le {1over 2} ). We first study the throughput capacity when the base stations are regularly placed and their transmission power is large enough for them to directly transmit to any nodes associated with them. We show that a per-node throughput of max { min {n^{b-1}, n^{d-1}}, min {{n^{w-1}over sqrt{log n}}, n^{d-1}} } bits/sec is achievable by all nodes. We then investigate the throughput capacity when the base stations are uniformly and randomly placed, and their transmission power is as small as that of the normal nodes. We present that each node can achieve a throughput of max { min {{n^{b - 1}over log n}, n^{d-1}}, min {{n^{w-1}over sqrt{log n}}, n^{d-1}} } bits/sec. In both settings, we observe that only when d ≫ b and d ≫ w, the maximum achievable throughput can be determined by both the number of base stations and the shape of network area. In all the other cases, the maximum achievable throughput is only constrained by the number of destination nodes. Moreover, the results in these two settings are the same except for the case d ≫ b ≫ w, in which the random placement of base stations will cause a degradation factor of log n on the maximum achievable throughput compared to the regular placement. Finally, we also show that our results actually hold for different power propagation models.     

Capacity and delay of hybrid wireless broadband access networks

An optical network is too costly to act as a broadband access network. On the other hand, a pure wireless ad hoc network with n nodes and total bandwidth of W bits per second cannot provide satisfactory broadband services since the pernode throughput diminishes as the number of users goes large. In this paper, we propose a hybrid wireless network, which is an integrated wireless and optical network, as the broadband access network. Specifically, we assume a hybrid wireless network consisting of n randomly distributed normal nodes, and m regularly placed base stations connected via an optical network. A source node transmits to its destination only with the help of normal nodes, i.e., in the ad hoc mode, if the destination can be reached within L (L /spl geq/ 1) hops from the source. Otherwise, the transmission will be carried out in the infrastructure mode, i.e., with the help of base stations. Two transmission modes share the same bandwidth of W bits/sec. We first study the throughput capacity of such a hybrid wireless network, and observe that the throughput capacity greatly depends on the maximum hop count L and the number of base stations m. We show that the throughput capacity of a hybrid wireless network can scale linearly with n only if m = Ω(n), and when we assign all the bandwidth to the infrastructure mode traffics. We then investigate the delay in hybrid wireless networks. We find that the average packet delay can be maintained as low as Θ(1) even when the per-node throughput capacity is Θ(W).     

Network Design and Architectures for Highly Dynamic Next-Generation IP-Over-Optical Long Distance Networks

The DARPA CORONET project seeks to develop the target network architectures and technologies needed to build next-generation long-distance IP-over-Optical-Layer (IP/OL) networks. These next-generation networks are expected to scale 10–100 times larger than today's largest commercial IP/OL network. Furthermore, DARPA has established advanced objectives for very rapid provisioning of new IP or private line connections, very rapid restoration against up to three simultaneous network failures, and future dynamic “wavelength” services ranging from speeds of 40–800 Gigabits per second. Besides these ambitious goals, the CORONET project seeks to establish a commercially-viable network architecture that supports both commercial and government services. In this paper, we describe the CORONET program requirements, and present our initial architectures and analysis of the early phases of this long-term project. We propose a novel 2-Phase Fast Reroute restoration method that achieves 50–100 ms restoration in the IP-Layer in a cost-effective manner, and a commercially viable OL restoration method that can meet the rapid CORONET requirements. We also estimate the magnitude of the extra capacity needed to provide dynamic wavelength services compared to that of static services, and show that the extra capacity to restore a small percentage of high priority traffic against multiple failures requires a small amount of extra capacity compared to that of single failures.      

Sharp thresholds for relative neighborhood graphs in wireless Ad Hoc networks

In wireless ad hoc networks, relative neighborhood graphs (RNGs) are widely used for topology control. If every node has the same transmission radius, then an RNG can be locally constructed by using only one hop information if the transmission radius is set no less than the largest edge length of the RNG. The largest RNG edge length is called the critical transmission radius for the RNG. In this paper, we consider the RNG over a Poisson point process with mean density η in a unit-area disk.     

Energy-Optimal Distributed Algorithms for Minimum Spanning Trees

Traditionally, the performance of distributed algorithms has been measured in terms of time and message complexity.Message complexity concerns the number of messages transmitted over all the edges during the course of the algorithm. However, in energy-constrained ad hoc wireless networks (e.g., sensor networks), energy is a critical factor in measuring the efficiency of a distributed algorithm. Transmitting a message between two nodes has an associated cost (energy) and moreover this cost can depend on the two nodes (e.g., the distance between them among other things). Thus in addition to the time and message complexity, it is important to consider energy complexity that accounts for the total energy associated with the messages exchanged among the nodes in a distributed algorithm. This paper addresses the minimum spanning tree (MST) problem, a fundamental problem in distributed computing and communication networks. We study energy-efficient distributed algorithms for the Euclidean MST problem assuming random distribution of nodes. We show a non-trivial lower bound of ω(log n) on the energy complexity of any distributed MST algorithm. We then give an energy-optimal distributed algorithm that constructs an optimal MST with energy complexity O(log n) on average and O(log n log log n) with high probability. This is an improvement over the previous best known bound on the average energy complexity of ?(log2 n). Our energy-optimal algorithm exploits a novel property of the giant component of sparse random geometric graphs. All of the above results assume that nodes do not know their geometric coordinates. If the nodes know their own coordinates, then we give an algorithm with O(1) energy complexity (which is the best possible) that gives an O(1) approximation to the MST.     

Pre-planned optical burst switched routing strategies considering the streamline effect

Optical burst switching is a promising paradigm for the next IP over optical network backbones. However, due to its bufferless nature, it can be highly affected by burst contention. Several methods have been proposed to address this problem, most of them without considering a phenomenon unique to optical burst switched networks called streamline effect. Most of the reported studies also assume the existence of total wavelength conversion capacity on all nodes, presently a very expensive and somewhat unrealistic configuration, and additionally, the contention resolution schemes adopted increase in the complexity of the core nodes, hampering scalability. In this study, we present a traffic engineering approach for path selection with the objective of minimizing the contention considering the streamline effect and using only topological information. The main idea is to balance the traffic across the network in order to prevent congestion while keeping simple the architecture of the core nodes and without incurring into link state dissemination penalties. We propose and evaluate the path selection strategies in both networks with full wavelength conversion capability and networks with imposed wavelength continuity constraint. Results show that our strategies can outperform the traditionally used shortest path routing.     

Multiwavelength optical networks with limited wavelength conversion

This paper proposes optical wavelength division multiplexed (WDM) networks with limited wavelength conversion that can efficiently support lightpaths (connections) between nodes. Each lightpath follows a route in a network and must be assigned a channel on each link along the route. The load λ_max of a set of lightpaths is the maximum over all links of the number of lightpaths that use the link. At least λ_max wavelengths will be needed to assign channels to the lightpaths. If the network has full wavelength conversion capabilities, then λ_max wavelengths are sufficient to perform the channel assignment. Ring networks with fixed wavelength conversion capability within the nodes are proposed that can support all lightpath sets with load λ_max at most W-1, where W is the number of wavelengths in each link. Ring networks with a small additional amount of wavelength conversion capability within the nodes are also proposed that allow the support of any set of lightpaths with load λ_max at most W. A star network is also proposed with fixed wavelength conversion capability at its hub node that can support all lightpath sets with load λ_max at most W. These results are extended to tree networks and networks with arbitrary topologies. This provides evidence that significant improvements in traffic-carrying capacity can be obtained in WDM networks by providing very limited wavelength conversion capability within the network     

On the Fairness of Large CSMA Networks

We characterize the fairness of decentralized medium access control protocols based on CSMA/CA, in large multi-hop wireless networks. In particular, we show that the widely observed unfairness of these protocols in small network topologies does not always persist in large topologies. In regular networks, this unfairness is essentially due to the unfair advantage of nodes at the border of the network, which have a restricted neighborhood and thus a higher probability to access the communication channel. In large 1D lattice networks these border effects do not propagate inside the network, and nodes sufficiently far away from the border have equal access to the channel; as a result the protocol is long-term fair. In 2D lattice networks, we observe a phase transition. If the access intensity of the protocol is small, the border effects remain local and the protocol behaves similarly as in one-dimensional networks. However, if the access intensity of the protocol is large enough, the border effects persist independently of the size of the network and the protocol is strongly unfair. In irregular networks, the topology is inherently unfair. This unfairness increases with the access intensity of the protocol, but in a much smoother way than in regular two-dimensional networks. Finally, in situations where the protocol is long-term fair, we provide a characterization of its short-term fairness.     

Stability and capacity of regular wireless networks

We study the stability and capacity problems in regular wireless networks. In the first part of the paper, we provide a general approach to characterizing the capacity region of arbitrary networks, find an outer bound to the capacity region in terms of the transport capacity, and discuss connections between the capacity formulation and the stability of node buffers. In the second part of the paper, we obtain closed-form expressions for the capacity of Manhattan (two-dimensional grid) and ring networks (circular array of nodes). We also find the optimal (i.e., capacity-achieving) medium access and routing policies. Our objective in analyzing regular networks is to provide insights and design guidelines for general networks. The knowledge of the exact capacity enables us to quantify the loss incurred by suboptimal protocols such as slotted ALOHA medium access and random-walk-based routing. Optimal connectivity and the effects of link fading on network capacity are also investigated.     

Performance analysis of relative location estimation for multihop wireless sensor networks

In this paper, we present new analytical, simulated, and experimental results on the performance of relative location estimation in multihop wireless sensor networks. With relative location, node locations are estimated based on the collection of peer-to-peer ranges between nodes and their neighbors using a priori knowledge of the location of a small subset of nodes, called reference nodes. This paper establishes that when applying relative location to multihop networks the resulting location accuracy has a fundamental upper bound that is determined by such system parameters as the number of hops and the number of links to the reference nodes. This is in contrast to the case of single-hop or fully connected systems where increasing the node density results in continuously increasing location accuracy. More specifically, in multihop networks for a fixed number of hops, as sensor nodes are added to the network the overall location accuracy improves converging toward a fixed asymptotic value that is determined by the total number of links to the reference nodes, whereas for a fixed number of links to the reference nodes, the location accuracy of a node decreases the greater the number of hops from the reference nodes. Analytical expressions are derived from one-dimensional networks for these fundamental relationships that are also validated in two-dimensional and three-dimensional networks with simulation and UWB measurement results.     

Asymptotic Critical Total Power for $k$ -Connectivity of Wireless Networks

An important issue in wireless ad hoc networks is to reduce the transmission power subject to certain connectivity requirement. In this paper, we study the fundamental scaling law of the minimum total power (termed as critical total power) required to ensure k -connectivity in wireless networks. Contrary to several previous results that assume all nodes use a (minimum) common power, we allow nodes to choose different levels of transmission power. We show that under the assumption that wireless nodes form a homogeneous Poisson point process with density lambda in a unit square region [0, 1]², the critical total power required to maintain k-connectivity is Theta((Gamma(c/2 + k)/(k - 1)!) lambda^1-c/2) with probability approaching one as lambda goes to infinity, where c is the path loss exponent. If k also goes to infinity, the expected critical total power is of the order of k^c/2 lambda^1-c/2. Compared with the results that all nodes use a common critical transmission power for maintaining k-connectivity, we show that the critical total power can be reduced by an order of (log lambda)^c/2 by allowing nodes to optimally choose different levels of transmission power. This result is not subject to any specific power/topology control algorithm, but rather a fundamental property of wireless networks.     

On the Capacity of Multihop Slotted ALOHA Networks with Regular Structure

In this paper we investigate the capacity of networks with a regular structure operating under the slotted ALOHA access protocol. We first consider circular (loop) and linear (bus) networks and then proceed to two-dimensional networks. For one-dimensional networks we find that the capacity is basically independent of the network average degree and is almost constant with respect to network size. For two-dimensional networks we find that the capacity grows in proportion to the square root of the number of nodes in the network provided that the average degree is kept small. Furthermore, we find that reducing the average degree (with certain connectivity restrictions) allows a higher throughput to be achieved. We also investigate some of the peculiarities of routing in these networks.     

Hierarchical Cooperation Achieves Optimal Capacity Scaling in Ad Hoc Networks

n source and destination pairs randomly located in an area want to communicate with each other. Signals transmitted from one user to another at distance r apart are subject to a power loss of r^-alpha as well as a random phase. We identify the scaling laws of the information-theoretic capacity of the network when nodes can relay information for each other. In the case of dense networks, where the area is fixed and the density of nodes increasing, we show that the total capacity of the network scales linearly with n. This improves on the best known achievability result of n^2/3 of Aeron and Saligrama. In the case of extended networks, where the density of nodes is fixed and the area increasing linearly with n, we show that this capacity scales as n^2-alpha/2 for 2lesalpha<3 and radicn for a alphages3. The best known earlier result of Xie and Kumar identified the scaling law for alpha > 4. Thus, much better scaling than multihop can be achieved in dense networks, as well as in extended networks with low attenuation. The performance gain is achieved by intelligent node cooperation and distributed multiple-input multiple-output (MIMO) communication. The key ingredient is a hierarchical and digital architecture for nodal exchange of information for realizing the cooperation.