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.

This paper investigates the gain of inter-Node B macro diversity for a scheduled-based shared channel using single-carrier FDMA radio access in the Evolved UTRA (UMTS Terrestrial Radio Access) uplink based on system-level simulations. More specifically, we clarify the gain of inter-Node B soft handover (SHO) with selection combining at the radio frame length level (=10 msec) compared to that for hard handover (HHO) for a scheduled-based shared data channel, considering the gains of key packet-specific techniques including channel-dependent scheduling, adaptive modulation and coding (AMC), hybrid automatic repeat request (ARQ) with packet combining, and slow transmission power control (TPC). Simulation results show that the inter-Node B SHO increases the user throughput at the cell edge by approximately 10% for a short cell radius such as 100-300 m due to the diversity gain from a sudden change in other-cell interference, which is a feature specific to full scheduled-based packet access. However, it is also shown that the gain of inter-Node B SHO compared to that for HHO is small in a macrocell environment when the cell radius is longer than approximately 500 m due to the gains from hybrid ARQ with packet combining, slow TPC, and proportional fairness based channel-dependent scheduling.

We aim to establish a highly efficient transmitting power control (TPC) scheme suitable for the reverse link of high-speed CDMA packet communication systems. Reservation-based access is assumed to be used for packet transmission in the reverse link. First, we describe a hybrid TPC that we created to cope with average interference changes. The target receiving power in the hybrid TPC is set according to the interference averaged over a comparatively long period of time. We show, using experiments on our high-speed packet communication experimental system, that hybrid TPC can effectively reduce transmission power consumption and PER compared with basic receiving power based TPC. Furthermore, we need to change the transmitting power according to the instantaneous interference to cope with instantaneous interference changes slot by slot. However, in a high-speed packet communication system, the interference level can change dramatically in a very short period of time. The TPC of cdma2000 or W-CDMA cannot efficiently cope with rapidly and greatly changing interference levels. Therefore, we created another two novel TPCs. Interference is divided in these TPCs into intra-cell and inter-cell interference. The supposed inter-cell interference level is changed according to the change in the probability distribution of the inter-cell interference, and the necessary transmitting power for a packet is calculated based on intra-cell allocation information and the supposed inter-cell interference level. Computer simulations show that, with the proposed TPCs, throughput can be increased by more than 200% compared with the type of TPC used in cdma2000 or W-CDMA, and the transmitting power consumption in a mobile host (MH) can also be vastly reduced.

In this paper, a slot-averaged SIR model is derived to analyze the performances of 1/N-slotted DS-CDMA packet radio networks. DS-CDMA packet radio networks can be analyzed with channel threshold model, but it is not appropriate for a 1/N-slotted access scheme since the interference level varies slot by slot during a packet transmission time. A packet in a DS-CDMA system will be channel-encoded and interleaved so that an excessive interference of some slots does not result in a corruption of a packet directly. In a 1/N-slotted DS-CDMA packet system, interleaving and channel coding can cope with the excessive interference in some slots. Proposed slot-averaged SIR model reflects this effect and is simple enough to be used in the performance analyses of various packet access control schemes. This paper verifies the slot-averaged SIR model and evaluates the throughputs of 1/N-slotted access schemes using it. This paper also compares the results with those of the conventional channel threshold model. Packet access schemes such as slotted ALOHA, slotted CLSP and slotted CLSP/CC are analyzed. The results show that many different aspects from the results of the previous works can be evaluated and this work will offer more accurate view on the behavior of 1/N-slotted DS-CDMA packet radio networks.

In this paper, we study macro/micro diversity techniques for code acquisition of a direct-sequence spread-spectrum signal in an indoor packet communication system. In the system discussed, the base station has several radio ports each with a cluster of antennas, and the terminal also has multiple antennas. The performance in the uplink of this system is analyzed under Lognormal shadowing and flat Rayleigh fading. The numerical results show great performance improvements by proposed diversity techniques. In addition, it is clarified that the mean acquisition time, which is often used as the measure of performance, is not suitable for packet radio systems as it underestimates the necessary preamble length for initial code acquisition.

The General Packet Radio Service (GPRS) is a new bearer service for GSM that greatly improves and simplifies wireless access to packet data networks, e.g., to the Internet. It applies a packet radio principle to transfer user data packets in an efficient way between mobile stations and external packet data networks. This tutorial gives an introduction to GPRS. The article discusses the system architecture and its basic functionality. It explains the offered services, the session and mobility management, the routing, the GPRS air interface including channel coding, and the GPRS protocol architecture. Finally, an interworking example between GPRS and IP networks is shown.

The proliferation and development of cellular voice systems over the past several years has exposed the capabilities and the effectiveness of wireless communications and, thus, has paved the way for wide-area wireless data applications as well. The demand for such applications is currently experiencing a significant increase and, therefore, there is a strong call for advanced and efficient mobile data technologies. This article deals with these mobile data technologies and aims to exhibit their potential. It provides a thorough survey of the most important mobile packet data services and technologies, including MOBITEX, CDPD, ARDIS, and the emerging GPRS. For each technology, the article outlines its main technical characteristics, discusses its architectural aspects, and explains the medium access protocol, the services provided, and the mobile routing scheme.

A novel combinatorial optimization algorithm called "Gradual neural network (GNN)" is presented for NP-complete broadcast scheduling problems in packet radio (PR) networks. A PR network provides data communications services to a set of geographically distributed nodes through a common radio channel. A time division multiple access (TDMA) protocol is adopted for conflict-free communications, where packets are transmitted in repetition of fixed-length time-slots called a TDMA cycle. Given a PR network, the goal of GNN is to find a TDMA cycle with the minimum delay time for each node to broadcast packets. GNN for the N-node-M-slot TDMA cycle problem consists of a neural network with N M binary neurons and a gradual expansion scheme. The neural network not only satisfies the constraints but also maximizes transmissions by two energy functions, whereas the gradual expansion scheme minimizes the cycle length by gradually expanding the size of the neural network. The performance is evaluated through extensive simulations in benchmark instances and in geometric graph instances with up to 1000 vertices, where GNN always finds better TDMA cycles than existing algorithms. The result in this paper supports the credibility of our GNN algorithm for a class of combinatorial optimization problems.

This paper proposes a new MAC protocol and physical channel control schemes for TDMA-TDD multi-slot packet channel. The goal of this study is to support both circuit-switched and packet-switched communications on the same resources and to enable high-speed packet transmission using a multi-slot packet channel. In the proposed channel control schemes, three points are taken into account; 1) effective sharing of time slots and frequencies with minimum impact on circuit communications, 2) compatibility with the existing access protocol and equipment, and 3) dynamic allocation of uplink and downlink slots. As for the MAC protocol, we adopt BRS (Block Reservation Scheme) and adaptive access control scheme to the proposed MAC protocol. In addition, to overcome the inherent disadvantage of TDD channels, packet scheduling and access randomizing control are newly proposed in this paper. The results of throughput and delay evaluations confirm that downlink capacity can be drastically enhanced by the dynamic allocation of uplink and downlink slots while corruption under heavy traffic loads is prevented by applying the adaptive traffic load control scheme.

This paper introduces a new analytic method that uses modified state equations to evaluate the performance of PCSD (Packet Channel Sharing protocol for DCA systems) with the goal of increasing the spectrum efficiency of DCA systems by realizing channel sharing between circuit-switched calls and packets. The results of this analysis show that PCSD is more suitable for microcellular systems than cellular systems, and that PCSD system performance improves as the average holding time of circuit-switched calls increases. Moreover, this paper proposes a novel scheme to determine the optimum release delay time of packet channels in order to achieve high throughput for packets as well as high channel capacity for circuit-switched calls. The proposed scheme shows that the optimum release delay time for PHS (Personal Handy-phone System) is greater than 60 frames and less than 100 frames.

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.

The performance of a noncoherent parallel matched-filter (MF) acquisition scheme with a reference filter (RF) is evaluated for a direct-sequence/spread-spectrum multiple access (DS/SSMA) packet radio system in a mobile cellular environment. This acquisition scheme employs a RF to estimate the variance of interference at the output of detecting MF. Acquisition-based packet throughput of the parallel NM-RF scheme is derived for an AWGN and a Rayleigh fading channels. Packet throughput of a parallel MF-RF acquisition scheme is compared with those of a serial MF scheme, a serial MF-RF scheme, and a parallel MF. From the numerical results, it is shown that the packet throughput decreases with the number of users in the system, and increases with the preamble length. Imperfect power control causes packet throughput to decrease especially when the power control error is large. The considerations in this paper can be applied to the reverse link (mobile-to-base station) design of a DS/SSMA system for packet-type services.

This paper proposes a data transfer protocol called Logical Airlink Control Procedure for Packet Radio Systems (LAPPR) which offers a high throughput efficiency in fading channels. Two main ideas are presented in the flow control and retransmission control methods. A new flow control scheme called "P/F Sliding Flow" is proposed where a high channel utilization rate is provided by continuously transmitting the data frames. At that time, the acknowledgements for the data frames are reduced so as not to occupy both the forward and reverse channels and data exchange between different transmitter-receiver pairs is enabled. A retransmission control scheme called "Recovery Confirming Retransmission Control" is also proposed which makes conventional Automatic Repeat Request (ARQ) schemes significantly more effective in the fading environments by continuously sending the same frame. Computer simulations were carried out and the result showed that a throughput higher than conventional protocols can be achieved.

The demand for data communication over Personal Handy-phone System (PHS) is expected to rapidly increase in the near future. Some applications based on the circuit-switched services have been recently developed. However, the packet-switched service is better than the circuit-switched service for personal data communications in terms of the flexible utilization of radio resources. In this paper, we propose PHS with packet data communications system (PHS-PD), which has four system concepts; (i) to supprot the Internet access, (ii) to realize compatibility with circuit-switching services, (iii) to share the common radio channels with circuit-switched calls, and (iv) to utilize idle time slots for packet data. Moreover, a novel packet channel structure for sharing radio resources with circuit-switched calls is introduced. Although packet data are transferred using common radio resources, the proposed channel structure prevents any degradation in call loss performance of the circuit-switching service. An evaluation of the maximum packet transmission rate shows that PHS-PD can offer a data communication rate of 20.1 kbps even if circuit-switched calls are in progress. Furthermore, up to 83.6 kbps is possible if circuit-switched calls are quiescent. It is also shown that enough capacity for a practical e-mail service can be ensured by PHS-PD even if the degradation of throughput performance due to packet collisions on random access channels is considered.

In this paper, we have investigated power control techniques for two different routing schemes in a multi-hop Code Division Multiple Access (CDMA) packet radio network. These techniques control the signal power based not only on the transmission distance, but also on the transmission direction. These techniques reduce the amount of interference from the other terminals, and improve the probability of packet success and the expected forward progress per hop. Our results show that the power control techniques increase the expected packet progress towards the final destination per hop by 16% as compared with that of the no power control case. This performance improvement is achieved without increasing system complexity or sacrificing system performance.

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.