Upper bounds to transport capacity of wireless networks

We derive upper bounds on the transport capacity of wireless networks. The bounds obtained are solely dependent on the geographic locations and power constraints of the nodes. As a result of this derivation, we are able to conclude the optimality, in the sense of scaling of transport capacity with the number of nodes, of a multihop communication strategy for a class of network topologies.     

A deterministic approach to throughput scaling in wireless networks

We address the problem of how throughput in a wireless network scales as the number of users grows. Following the model of Gupta and Kumar, we consider n identical nodes placed in a fixed area. Pairs of transmitters and receivers wish to communicate but are subject to interference from other nodes. Throughput is measured in bit-meters per second. We provide a very elementary deterministic approach that gives achievability results in terms of three key properties of the node locations. As a special case, we obtain /spl Omega/(/spl radic/n) throughput for a general class of network configurations in a fixed area. Results for random node locations in a fixed area can also be derived as special cases of the general result by verifying the growth rate of three parameters. For example, as a simple corollary of our result we obtain a stronger (almost sure) version of the /spl radic/n//spl radic/(logn) throughput for random node locations in a fixed area obtained by Gupta and Kumar. Results for some other interesting non-independent and identically distributed (i.i.d.) node distributions are also provided.     

Optimal throughput-delay scaling in wireless networks - part I: the fluid model

Gupta and Kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is /spl Theta/(1//spl radic/(nlogn)). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. In most applications, delay is also a key metric of network performance. It is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. The focus of this paper is on studying this tradeoff for wireless networks in a general framework. Optimal throughput-delay scaling laws for static and mobile wireless networks are established. For static networks, it is shown that the optimal throughput-delay tradeoff is given by D(n)=/spl Theta/(nT(n)), where T(n) and D(n) are the throughput and delay scaling, respectively. For mobile networks, a simple proof of the throughput scaling of /spl Theta/(1) for the Grossglauser-Tse scheme is given and the associated delay scaling is shown to be /spl Theta/(nlogn). The optimal throughput-delay tradeoff for mobile networks is also established. To capture physical movement in the real world, a random-walk (RW) model for node mobility is assumed. It is shown that for throughput of /spl Oscr/(1//spl radic/(nlogn)), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., D(n)=/spl Theta/(nT(n)). Surprisingly, for almost any throughput of a higher order, the delay is shown to be /spl Theta/(nlogn), which is the delay for throughput of /spl Theta/(1). Our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay.     

无线ad hoc网络多性能指标基本性能边界

在无线ad hoc网络中,基本性能边界对路由算法和资源分配协议的分析和评价具有重要的意义。对无线ad hoc网络多性能指标基本性能边界进行了研究,包括理论上最优的性能边界和实际可以得到的性能边界。提出了一种稳定状态(steady state)下的网络基本性能指标分析模型。该模型考虑了无线网络广播特性和无线信道干扰,可同时分析多个性能指标,包括：吞吐量、端到端延迟和能量消耗。基于该模型,针对ad hoc网络中最常见的多流—单/双中继拓扑分析基本性能指标,求解多目标优化问题得到基本性能边界。仿真结果验证了模型的准确性,均方根误差小于10-3量级。     

Tailbiting codes: bounds and search results

Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are better than the previously known linear codes with the same parameters. Four of them are also superior to any previously known nonlinear code with the same parameters. Also, more than 40 other quasi-cyclic codes have been found that improve the parameter set of previously known quasi-cyclic codes     

Linear authentication codes: bounds and constructions

In this paper, we consider a new class of unconditionally secure authentication codes, called linear authentication codes (or linear A-codes). We show that a linear A-code can be characterized by a family of subspaces of a vector space over a finite field. We then derive an upper bound on the size of the source space when other parameters of the system, that is, the sizes of the key space and the authenticator space, and the deception probability, are fixed. We give constructions that are asymptotically close to the bound and show applications of these codes in constructing distributed authentication systems.     

On adaptive hybrid error control in wireless networks using Reed-Solomon codes

This letter models and analyzes an adaptive radio link level error control protocol using Reed-Solomon codes for wireless networks. Results show that the proposed dynamic rate adaptive strategy provides a much improved throughput relative to a conventional type-I and type-II hybrid-automatic repeat request (ARQ) protocols.     

Training overhead for decoding random linear network codes in wireless networks

We consider multicast communications from a single source to multiple destinations through a wireless network with unreliable links. Random linear network coding achieves the min-cut flow capacity; however, additional overhead is needed for end-to-end error protection and to communicate the network coding matrix to each destination. We present a joint coding and training scheme in which training bits are appended to each source packet, and the channel code is applied across both the training and data. This scheme allows each destination to decode jointly the network coding matrix along with the data without knowledge of the network topology. It also balances the reliability of communicating the network coding matrices with the reliability of data detection. The throughput for this scheme, accounting for overhead, is characterized as a function of the packet size, channel properties (error and erasure statistics), number of independent messages, and field size. We also compare the performance with that obtained by individual channel coding of training and data. Numerical results are presented for a grid network that illustrate the reduction in throughput due to overhead.     

Contention resolution in random-access wireless networks based on orthogonal complementary codes

This paper proposes a new method for contention resolution in random-access wireless networks. Using orthogonal complementary codes to design access-request packets, users can reserve channel access successfully, even in severe contentions. Collisions among access-request packets can be resolved and exploited, whereas collisions among data packets are avoided. System throughput and delay performance can be enhanced, because random-access contention becomes transparent. Specifically, system throughput approaches the offered load up to the maximum value one with improved average packet delay performance. A joint layer design approach is proposed with both the physical layer signal-detection algorithm and the medium access-control layer random-access protocol. The performance is analyzed with the consideration of signal detection errors. Simulations are performed to demonstrate its superior performance.     

Data extraction from wireless sensor networks using distributed fountain codes

A Wireless Sensor Network (WSN) observes a natural field and aims to recreate it with sufficient fidelity at a, perhaps distant, Fusion Center (FC) using a wireless communication channel of arbitrary capacity. We propose a universal and power efficient method for such data extraction, based on Digital Fountain Codes (DFCs) and joint-source channel decoding. Our method implements a distributed `rate-lessiquest DFC which automatically tunes the number of transmissions to the channel capacity. Furthermore, instead of directly compressing the WSN data, we achieve rate reduction by treating the spatiotemporal dependencies in the field as an outer code, and jointly decoding this concatenation at the FC using a multi-stage iterative decoder. We demonstrate that a power efficiency close to the capacity-rate-distortion limit is achieved at moderate distortion levels, irrespective of the channel capacity or field dependencies. As compared to the traditional approach of source-channel separation, the proposed data extraction scheme is particularly attractive for WSN applications due its computationally simple encoding procedure, low latency and the ability to seamlessly trade-off fidelity of reconstruction for power consumption.     

Lower bounds on lifetime of ultra wide band wireless sensor networks

The asymptotic lower bounds on the lifetime of time hopping impulse radio ultra wide band (TH-IR UWB) wireless sensor networks are derived using percolation theory arguments. It is shown that for static dense TH-IR UWB wireless sensor network, which sensor nodes are distributed in a square of unit area according to a Poisson point process of intensity n, the lower bound on the lifetime is \( \Upomega \left( {\left( {{{\sqrt n } \mathord{\left/ {\vphantom {{\sqrt n } {\log \sqrt n }}} \right. \kern-\nulldelimiterspace} {\log \sqrt n }}} \right)^{\alpha - 2} } \right) \), where α > 2 is the path loss exponent, thus dense TH-IR UWB wireless sensor network is fit to be employed in large-scale network. For static extended TH-IR UWB wireless sensor network which sensor nodes are distributed in a square \( \left[ {0,\sqrt n } \right] \times \left[ {0,\sqrt n } \right] \) according to a Poisson point process of unit intensity, the lower bound on the lifetime is \( \Upomega \left( {{{\left( {\log \sqrt n } \right)^{2 - \alpha } } \mathord{\left/ {\vphantom {{\left( {\log \sqrt n } \right)^{2 - \alpha } } n}} \right. \kern-\nulldelimiterspace} n}} \right) \), therefore large-scale extended network will lead to shorten network lifetime. The results also indicate that the lower bound on the lifetime in the ideal case is longer than that of a static network by a factor of \( n^{1/2} \left( {\log \sqrt n } \right)^{\alpha - 4} \). Hence mobility of sensor nodes can improve network lifetime.     

Quantized lower bounds on grid-based localization algorithm for wireless sensor networks

In this paper, we introduce a Quantized Cramer Rao Bound (Q-CRB) method, which adapts the use of the CRB to handle grid-based localization algorithms with certain constraints, such as localization boundaries. In addition, we derive a threshold granularity level which identifies where the CRB can be appropriately applied to this type of algorithm. Moreover, the derived threshold value allows the users of grid-based LSE techniques to probably avoid some unnecessary complexities associated with using high grid resolutions. To examine the feasibility of the new proposed bound, the grid-based least square estimation (LSE) technique was implemented. The Q-CRB was used to evaluate the performance of the LSE method under extensive simulation scenarios. The results show that the Q-CRB provided a tight bound in the sense that the Q-CRB can characterize the behaviour of location errors of the LSE technique at various system parameters, e.g. granularity levels, measurement accuracies, and in the presence or absence of localization boundaries.     

Analysis of generalized optical orthogonal codes in optical wireless local area networks

In this paper we propose and analyze the application of generalized optical orthogonal codes (GOOC) in the optical wireless local area networks (OWLAN). A system deploying GOOC can support more users and achieve better BER performance. We evaluate the system performance of GOOC noting practical constraints of OWLAN applications. We consider average and peak power limitations of free space infrared sources, arising from eye safety and device non-linearity restriction. We include the impact of various noises including background-light induced noise in system evaluation. Proper system design requires appropriate selection of GOOC code parameters. We analyze the influence of code parameters on key system variables such as BER, required bandwidth and power consumption. Using the results, we provide guidelines for proper selection of key GOOC code parameters for OWLAN applications.     

Interference‐resistant cooperative wireless networks based on complementary codes

Spatial diversity in wireless networks can be attained by exploiting the broadcast nature of wireless transmission without the need of multiple antennas in individual device, leading to the implementation of cooperative communication. While most prior works focused on the single source—destination scenario, it should be more realistic to consider how to induce cooperation among multiple source‐destination pairs assisted by multiple relays. In such a case, multiple access interference (MAI) may present due to asynchronous transmissions of the users and relays. In this paper, a cooperative network architecture based on orthogonal complementary (OC) codes inherently immune to MAI is proposed. To efficiently utilize the scarce radio spectrum and codes, a centralized medium access control (MAC) protocol is proposed to coordinate the code assignment and channel access among users and relays. We theoretically analyze the bit error rate (BER) performance of the proposed OC coded cooperative network over multipath Rayleigh fading channel. The performance gain resulted from different numbers of relays is investigated, and compared with a time division multiple access (TDMA) based cooperative scheme. We show that the proposed OC coded cooperative network performs well in the presence of timing offset, and thus is well suited for asynchronous uplink transmission with cooperative relaying. Copyright © 2009 John Wiley & Sons, Ltd.     

Modeling and designing efficient data aggregation in wireless sensor networks under entropy and energy bounds

Sensor networks are characterized by limited energy, processing power, and bandwidth capabilities. These limitations become particularly critical in the case of event-based sensor networks where multiple collocated nodes are likely to notify the sink about the same event, at almost the same time. The propagation of redundant highly correlated data is costly in terms of system performance, and results in energy depletion, network overloading, and congestion. Data aggregation is considered to be an effective technique to reduce energy consumption and prevent congestion in wireless sensor networks. In this paper, we derive a number of important insights concerning the data aggregation process, which have not been discussed in the literature so far. We first estimate the conditions under which aggregation is a costly process in comparison to a non aggregation approach, by considering a realistic scenario where the processing costs related to aggregation of data are not neglected. We also consider that aggregation should preserve the integrity of data, and therefore, the entropy of the correlated data sent by sources can be considered in order to both decrease the amount of redundant data forwarded to the sink and perform an overall lossless process. We also derive the cumulative and the probability distribution functions of the delay in an aggregator node queue, which can be used to relate the delay to the amount of aggregation being considered. The framework we present in this paper serves to investigate the tradeoff between the increase in data aggregation required to reduce energy consumption, and the need to maximize information integrity, while also understanding how aggregation impacts the network propagation delay of a data packet.

Optimal choice of Reed-Solomon codes to protect against queuing losses in wireless networks

This article proposes algorithms to determine an optimal choice of the Reed-Solomon forward error correction (FEC) code parameters (n,k) to mitigate the effects of packet loss on multimedia traffic caused by buffer overflow at a wireless base station. A network model is developed that takes into account traffic arrival rates, channel loss characteristics, the capacity of the buffer at the base station, and FEC parameters. For Poisson distributed traffic, the theory of recurrent linear equations is applied to develop a new closed form solution of low complexity of the Markov model for the buffer occupancy. For constant bit rate (CBR) traffic,an iterative procedure is developed to compute the packet loss probabilities after FEC recovery.     

Assigning spare capacities in mesh survivable networks

This paper analyses one key issue of designing reliable networks: assignment of spare capacities in transmission networks. The spare capacities are optimized to facilitate the restoration of single failures. This problem can be formulated as an integer linear program and approximated by its continuous relaxation. This model is based on arc-path formulation especially efficient for dealing with end-to-end rerouting and providing appreciable economies in comparison with local rerouting. The main idea of our method resides in a linear programming decomposition, which permits us to solve problems for medium and large networks. Our approach could be applicable to both STM and ATM-based networks. This method was tested successfully on medium and large DCS-meshed networks and some numerical examples are given to illustrate its performances in terms of CPU time and ratio of optimality. This revised version was published online in June 2006 with corrections to the Cover Date.     

Information-theoretic upper bounds on the capacity of large extended ad hoc wireless networks

We derive an information-theoretic upper bound on the rate per communication pair in a large ad hoc wireless network. We show that under minimal conditions on the attenuation due to the environment and for networks with a constant density of users, this rate tends to zero as the number of users gets large.     

Some constructions and bounds for authentication codes

We investigate authentication codes, using the model described by Simmons. We review and generalize bounds on the probability that an opponent can deceive the transmitter/receiver by means of impersonation or substitution. Also, we give several constructions for authentication codes that meet one or more of these bounds with equality. These constructions use combinatorial designs, such as transversal designs, group-divisible designs, and BIBDs (balanced incomplete block designs).