The broadcast scheduling problem (BSP) in wireless ad-hoc networks is a well-known NP-complete combinatorial optimization problem. The BSP aims at finding a transmission schedule whose time slots are collision free in a wireless ad-hoc network with time-division multiple access (TDMA). The transmission schedule is optimized for minimizing the frame length of the node transmissions and maximizing the utilization of the shared channel. Recently, many metaheuristics can optimally solve smaller problem instances of the BSP. However, for complex problem instances, the computation of metaheuristics can be quite time and memory consuming. In this work, we propose a greedy genetic algorithm for solving the BSP with a large number of nodes. We present three heuristic genetic operators, including a greedy crossover and two greedy mutation operators, to optimize both objectives of the BSP. These heuristic genetic operators can generate good solutions. Our experiments use both benchmark data sets and randomly generated problem instances. The experimental results show that our genetic algorithm is effective in solving the BSP problem instances of large-scale networks with 2,500 nodes.

The symbol basis side information generated by Viterbi's ratio threshold test technique is proposed to improve the performance of the asynchronous slow-frequency-hopped multiple access system with BFSK signaling in the frequency non-selective fading channel. By properly setting the ratio threshold to produce erasure decisions for the received symbols, the system performances are optimized. The relationship among the hit symbols in a hop duration is exploited by this symbol basis side information to greatly reduce the packet error probability. This packet error rate improvement can be as large as two order of magnitude, compared with perfect hop basis side information systems.

In packet radio networks with TDMA, the throughput performance of network should be degraded due to the unequal traffic of each user. To overcome this problem, Mini-Slotted Alternating Priorities (MSAP) and TDMA with Parallel Transmission (TDMA/PT) were proposed. Especially, TDMA/PT can attain the thorughput performance more than one, even under unequal traffic. However, TDMA/PT cannot be used for mobile networks, because each terminal should know the location of every other terminal. In this paper, we propose an entirely new protocol named Slot Reservation TDMA with Parallel Transmissino: SR-TDMA/PT," which is suitable for mobile networks because a central station is able to locate every terminal easily. The central station also reserves time slots for each terminal so as to transmit packets in parallel as much as possible. Therefore, the throughput performance of SR-TDMA/PT is higher than TDMA/PT. We describe SR-TDMA/PT in detail and evaluate the performance of this protocol by simulation under various conditions.

We investigate the multipacket message transmissions and variable length message transmissions in slotted ALOHA systems with capture effect. First, we propose an approach that the transmission power level is controlled probabilistically depending on message length for multipacket messages. We consider the multipacket messages model with capture. We derive explicit equations of the effective channel utilization of the model. It is demonstrated that if we increase the numbar of power levels, we can get more effective channel utilization of the system. Secondly, we propose how to assign the slot size and show that the effective utilization of the channel is improved for variable length messages using the approach proposed for multipacket messages. Channel design issue about length of the slot depending on the number of power levels used for transmission is discussed. Thirdly, we propose the multiple messages per slot model with capture. The analytical results show that the multiple messages per slot model can achieve the highest channel utilization among the models discussed in this paper.

In Spread Spectrum Packet Radio Networks (SS/PRNs), different spreading codes are required for different stations for transmitting packets. Therefore multihop SS/PRNs with a large number of stations would require a large number of codes and hence a large channel bandwidth. In this paper we design a code assignment algorithm which could reduce the number of codes required to about 22%. Further reducing the number of codes is found to cause little throughput degradation. The Coded Tone Sense protocol is designed for using these codes in multihop PRNs. Simulation result shows that in a 80 node network using only 5 spreading codes, the maximum network throughput is about 73% higher than the BTMA protocol.

The effectiveness of error-control coding in a frequency-hop radio system can be increased greatly by the use of side information that is developed in the radio receiver. The transmission of test symbols provides a simple method for the derivation of side information in a slow-frequency-hop receiver. Requirements on the reliability of the side information are presented, and their implications in determining the necessary number of test symbols are described. Other methods for developing side information are reviewed briefly, and applications of side information to routing protocols for frequency-hop packet radio networks are discussed.

Concatenated coding techniques are applied to slow frequency-hop packet radio communications for channels with partial-band interference. Binary orthogonal signaling (e.g., binary FSK) is employed with noncoherent demodulation. The outer codes are Reed-Solomon codes and the inner codes are convolutional codes. Two concatenated coding schemes are compared. The first employs an interleaver between the outer Reed-Solomon code and the inner convolutional code. The second scheme employs an additional interleaver following the convolutional code. Comparisons are made between the performance of these concatenated coding schemes and the performance of Reed-Solomon codes alone.