Coding and stability in frequency-hop packet radio networks

A fully connected radio network is considered in which packets are sent using slow frequency-hop (FH) modulation, slotted ALOHA random access, and Reed-Solomon (RS) error-control coding. For this network, the dependence of throughput, delay, and drift on the code rate and block length is examined. It is shown that the drift approaches a simple limiting form as the block length becomes large. This form suggests that, in a bistable FH network, the undesirable stable point can usually be eliminated without increasing the delay or reducing the throughput at the desirable stable point. In particular, bistability can be eliminated by increasing the code block length and retransmission delay, and does not require the use of decentralized control or channel traffic estimates     

Multiple-packet forwarding protocols for frequency-hop packet radio networks

Reliable data distribution within multiple-hop spread-spectrum packet radio networks requires high performance from the network protocols. The high variability in quality among the links and the unique characteristics of frequency-hop spread-spectrum signaling impose special requirements for network protocols that are to be employed in frequency-hop packet radio networks. These features can be exploited in the forwarding protocols by allowing multiple packets to be included in each forwarding attempt. The use of multiple-packet transmissions exploits the capture property of frequency-hop signaling, and it reduces the overhead required for acknowledgments. A potential trade-off arises because the use of multiple-packet transmissions increases the throughput, but in some situations it can also increase the delay. Two new transmission protocols that employ multiple-packet transmissions are described, and their performance is evaluated.     

Hermitian codes for frequency-hop spread-spectrum packet radio networks

Hermitian codes are an attractive alternative to Reed-Solomon codes for use in frequency-hop spread-spectrum packet radio networks. For a given alphabet size, a Hermitian code has a much longer block length than a Reed-Solomon code. This and other considerations suggest that Hermitian codes may be superior for certain applications. Analytical results are developed for the evaluation of the packet error probability for frequency-hop transmissions using Hermitian coding. We find there are several situations for which Hermitian codes provide much lower packet error probabilities than can be obtained with Reed-Solomon codes. In general, as the code rate decreases or the symbol alphabet size increases, the relative performance of Hermitian codes improves with respect to Reed-Solomon codes. Performance evaluations are presented for an additive white Gaussian noise channel and for certain partial-band interference channels, and the packet error probability is evaluated for both errors-only and errors-and-erasures decoding.     

Performance analysis of frequency-hop packet radio networks with generalized retransmission backoff

A fully connected radio network is considered in which packets are sent using Reed-Solomon error-control coding, slow frequency-hop (FH) modulation, and generalized retransmission backoff policy. An easy-to-use analytical method for finite population FH networks is developed which offers insight into how system dynamics is affected by the number of users and the input rate. The performance of several retransmission backoff policies is examined. It is shown that the performance of exponential backoff policy with small minimum retransmission probability is not too far away from the optimum, when the code-block length is small and the number of users is not unreasonably large. It is also shown that packet rejection after a certain number of unsuccessful transmissions can stabilize some networks as one would expect, but may destabilize some others contrarily. Finally, the accuracy of the method is verified by extensive simulation results.     

Staggered interleaving and iterative errors- and-erasures decoding for frequency-hop packet radio

Information about the reliabilities; of the received symbols is very beneficial in frequency-hop communication systems. This information, known as side information, can be used to erase unreliable symbols at the input to an errors-and-erasures decoder. For slow-frequency-hop systems it is common that special redundant symbols, referred to as side-information symbols, are included in each dwell interval, and the demodulation of these symbols provides the side information. The corresponding decrease in the number of message symbols that can be sent in each dwell interval makes it desirable to develop alternative methods that do not require side-information symbols. In this paper, one such alternative is proposed, and its performance is evaluated for channels with partial-band interference. It is shown that staggered interleaving of Reed-Solomon code words and iterative errors-and-erasures decoding facilitates the erasure of unreliable symbols without the need for side-information symbols. The performance of this method is compared with the performance of systems that employ standard block interleaving and errors-only decoding or errors-and-erasures decoding with side information obtained from test symbols.     

Spatial reuse in multihop packet radio networks

Multihop packet radio networks present many challenging problems to the network analyst and designer. The communication channel, which must be shared by all of the network users, is the critical system resource. In order to make efficient use of this shared resource, a variety of channel access protocols to promote organized sharing have been investigated. Sharing can occur in three domains: frequency, time, and space. This paper is mostly concerned with sharing and channel reuse in the spatial domain. A survey of results on approaches to topological design and associated channel access protocols that attempt to optimize system performance by spatial reuse of the communication channel is presented.     

Mobile packet radio networks: State-of-the-art

MUCH WORK HAS been done in the areas of packet switching, packet radio, and random communication channels. However, efforts combining these areas are not as plentiful. There are several reasons for this. One reason is, the packet communications area is relatively young. Much of the research into packet communications has been accomplished by computer scientists rather then communications engineers, with a resulting emphasis on architecture, protocols, software, and so on. Even the development of packet radio has not fostered extensive examination of link effects on system performances. The UHF line-of-sight links and SHF satellite links have been assumed to be perfect with packet collisions as the dominant error source, which is a good assumption under normal circumstances. However, abnormal circumstances including ionospheric scintillations and multipath fading are another source of error on degraded packet radio links, which characterize Mobile Packet Radio Networks (MPRNET). In this paper we define and discuss Mobile Packet Radio Networks and presend their channel characteristics. The performance avaluation of some channel access protocols for a Mobile Packet Radio Network link, which is a typical example of a degraded packet radio channel, is descirbed.     

TDM policies in multistation packet radio networks

A multistation packet radio network with m stations and a finite number of nodes n that uses a conflict-free protocol to access the backbone network of stations through a shared channel is discussed. The goal is to derive an allocation of the channel time slots (time-division multiplexing cycle), so that all transmissions will be conflict-free and some measure of performance (e.g., the expected total weighted throughput, the expected weighted holding cost) will be optimized. The methodology that is used is to bound the performance and to allocate the slots according to the golden ratio policy     

Frequency-hop packet radio networks with coding and retransmission backoff

A fully connected frequency-hop packet radio network is considered. Four packet-combining techniques are presented, which significantly reduce the packet-error rate. An analytical model is used to offer insight into how system dynamics are affected by the error-control method and retransmission backoff policy. It is shown that enhancing the error-control method increases the maximum throughput of the network and alleviates the stability problem, but does not solve the problem. On the other hand, a good choice of retransmission backoff policy solves the stability problem, but does not alter the maximum throughput. These results suggest that in order to construct a stable network with large throughput, a good error-control method and retransmission backoff policy are both necessary.     

Slotted ALOHA multihop packet radio networks with directional antennas

The use of directional antennas in multihop packet radio networks using slotted ALOHA access is considered. Tractable approximations to the network performance in terms of expected forward progress are derived. Results show that packet collisions can be strongly reduced already with moderate gain antennas to allow for a substantial increase in network performance.<>     

High throughput slotted ALOHA packet radio networks with adaptivearrays

The authors consider the use of a multiple-beam adaptive array (MBAA) in a packet radio system. In an MBAA, a given set of antenna elements is used to form several antenna patterns simultaneously. When it is used in a packet radio system, an MBAA can successfully receive two or more overlapping packets at the same time. Each beam captures a different packet by automatically pointing its pattern toward one packet while nulling other, contending packets. It is shown how an MBAA can be integrated into a single-hop slotted ALOHA packet radio system, and the resulting throughput is analyzed for both finite- and infinite-user populations     

Joint delay-power capture in spread-spectrum packet radio networks

Capture phenomena in slotted ALOHA packet radio networks employing spread-spectrum modulation is considered. Probability of capture with both delay and power capture mechanisms are derived and compared with power- and delay-only capture models. Significant improvements in the capture probability is observed. The improvement over the delay-only capture model increases with decreasing arrival-time randomization overhead     

Adaptive forwarding in frequency-hop spread-spectrum packet radionetworks with partial-band jamming

Adaptive protocols that specify the ways in which a radio is permitted to modify its normal forwarding procedures based on information obtained locally in the network are considered. A computer program has been developed to simulate a frequency-hop (FH) packet radio network with partial-band jamming and interference due to other FH and narrowband radios. The radios in the network use time-slotted, receiver-directed, FH spread-spectrum signaling. Results on throughput, delay, and end-to-end probability of success are presented, and comparisons between different forwarding protocols are given for a static network topology with both static and mobile network jamming     

Topology control for multihop packet radio networks

A distributed topology-control algorithm has been developed for each node in a packet radio network (PRN) to control its transmitting power and logical neighbors for a reliable high-throughput topology. The algorithm first constructs a planar triangulation from locations of all nodes as a starting topology. Then, the minimum angles of all triangles in the planar triangulation are maximized by means of edge switching to improve connectivity and throughput. The resulting triangulation at this stage, the Delaunay triangulation, can be determined locally at each node. The topology is modified by negotiating among neighbors to satisfy a design requirement on the nodal degree parameter. Simulations show that the final topology is degree-bounded, has a rather regular and uniform structure, and has throughput and reliability that are greater than that of a number of alternative topologies     

Deterministic access protocols for packet radio networks

In this paper, multiple-phase deterministic protocols for packet radio networks are introduced and analysed. Two modes of information transfer are considered, namely (a) broadcasting and (b) point-to-point transmission. We explore systematic ways of designing multiple-phase protocols and apply them on Manhattan networks. The proposed protocols are studied primarily from the point of view of throughput efficiency. Delay analysis is also presented.     

Jamming in slotted ALOHA multihop packet radio networks

The properties of a packet radio network in the presence of active interference are discussed. Both the jammer and the network nodes are subject to an average power constraint. The network uses slotted ALOHA multiple access schemes and some simple fixed routing strategies with constant transmitter power. By using a game-theoretic approach the situation is considered as a two-person constant-sum game. The author defines network performance as the values of the game in terms of the expected forward progress of a packet. Both the performance and the optimum strategies for access and jamming are investigated     

Capture models for mobile packet radio networks

The probability q_i of successful reception in a nonfading mobile radio channel with i contending mobiles transmitting to a central base station is studied for a number of different capture and spatial distribution models. It is shown that a generalized capture model can be used to estimate q_i's for a simplified example system which uses noncoherent frequency shift keying modulation. This model can be applied to other systems as well. An example of the use of the q_i 's in the throughput evaluation of a finite population slotted ALOHA system is given. In most practical systems, the mobiles cannot get arbitrarily close to the base station. The effect of this constraint on q_i is examined. Finally, the dependence of the capture probability for a test mobile on its distance from the base station is obtained     

Network protocols for frequency-hop packet radios with decoder sideinformation

Reliable data distribution within spread-spectrum packet radio networks requires high performance from the network protocols. This paper describes research in forwarding and routing protocols that are designed specifically for slow-frequency hop (SFH) packet radio networks in which some of the radios are subjected to excessive interference. It is shown that information extracted from the decoder can be used to aid the network protocols. New metrics are introduced that use this information to give a quantitative assessment of the interference environment experienced by the receiver in an SFH radio. Forwarding protocols are developed that can react quickly to local sources of interference, and the metrics that are introduced permit the routing algorithm to react to changes in the interference conditions in the network     

Information efficiency of multihop packet radio networks with channel-adaptive routing

This paper analyzes the benefit of adaptive routing based on knowledge of the channel state information in multihop, ad hoc wireless networks that use direct-sequence code-division multiple access. Cross-layer, channel-adaptive routing exploits the inherent spatial diversity of multihop wireless networks to select links with favorable channel conditions. The information efficiency, an extension of a previously used measure called expected progress, is used to evaluate performance. Results show that, combined with adaptive modulation, adaptive routing can improve performance in ad hoc networks by a factor of four to five in channels with Rayleigh fading and lognormal shadowing. The lack of position information in the routing decision would reduce performance by 25%. New approaches to channel-adaptive routing that enable rapid adaptivity to channel conditions are discussed.     

Frequency-hop transmission for satellite packet switching and terrestrial packet radio networks

The performance of frequency-hop transmission in a packet communication network is analyzed. Satellite multiple-access broadcast channels for packet switching and terrestrial packet radio networks are the primary examples of the type of network considered. An analysis of the effects of multiple-access interference in frequency-hop radio networks is presented. New measures of "local" performance are defined and evaluated for networks of this type, and new concepts that are important in the design of these networks are introduced. In particular, error probabilities and local throughput are evaluated for a frequency-hop radio network which incorporates the standard slotted and unslotted ALOHA channel-access protocols, asynchronous frequency hopping, and Reed-Solomon error-control coding. The performance of frequency-hop multiple access with error-control coding is compared with the performance of conventional ALOHA random access using narrow-band radios.