Next Generation Wireless Networks (The Kluwer International Series in Engineering and Computer Science Volume 598)

NEXT GENERATION WIRELESS NETWORKS

THE KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE

NEXT GENERATION WIRELESS NETWORKS edited by

Sirin Tekinay New Jersey Institute of Technology

KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW

eBook ISBN: Print ISBN:

0-306-47310-0 0-792-37240-9

©2002 Kluwer Academic Publishers New York, Boston, Dordrecht, London, Moscow

All rights reserved

No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher

Created in the United States of America

Visit Kluwer Online at: and Kluwer's eBookstore at:

http://www.kluweronline.com http://www.ebooks.kluweronline.com

Contents

Introduction 1.

2.

Infostations: New Perspectives on Wireless Data Networks Ana Lucia Iacono and Christopher Rose

Wireless Broadband Multimedia and IP Applications via Mobile ATM Satellites Abbas Jamalipour

3.

Infocity: Providing QoS to Mobile Hosts Patricia Morreale

4.

Assisted GPS for Wireless Phone Location- Technology and Standards Bob Richton, Giovanni Vanucci, and Stephen Wilkus

5.

Evaluation of Location Determination Technologies Towards Satisfying the FCC E-911 Ruling M. Oguz Sunay

6.

A Series of GSM Positioning Trials Malcolm Macnaughten, Craig Scott, and Chris Drane

7.

Enhancing Terminal Coverage and Fault Recovery in Configurable Cellular Networks Using Geolocation Services Mostafa A. Bassiouni and Wei Cui

1

3

65

109

129

157

195

231

vi

8.

Index

UMTS Applications Development- Designing A “Killer Application” Gunther Popischil, Ernst Bonek, and Alexander Schneider

255

264

Introduction This book is a collection of extended versions of the papers presented at the Symposium on Next Generation Wireless Networks, May 26, 2000, New Jersey Institute of Technology, Newark, NJ. Each chapter includes, in addition to technical contributions, a tutorial of the corresponding area. It has been a privilege to bring together these contributions from researchers on the leading edge of the field. The papers were submitted in response to a call for papers aiming to concentrate on the applications and services for the “next generation,” deliberately omitting the numeric reference so that the authors’ vision of the future would not be limited by the definitive requirements of a particular set of standards. The book, as a result, reflects the top-down approach by focusing on enabling technologies for the applications and services that are the defining essentials for future wireless networks. This approach strikes a balance between the academia and the industry by addressing new wireless network architectures enabling mobility and location enhanced applications and services that will give wireless systems the competitive edge over others. The main theme of the book is the advent of wireless networks as an irreplaceable means of global communication as opposed to a mere substitute for, or a competitor of, wireline networks. Geolocation emerges as the facilitator of mobility and location sensitive services. The fields of geolocation and wireless communications have been forced to merge, following the Federal Commission of Communications’ (FCC) ruling that obliges wireless providers with emergency caller geolocation. This initial driving force has quickly been augmented by the already existing and increasing popularity of positioning and navigation systems using the Global Positioning System (GPS), in addition to the wireless providers’ zeal to add value to the geolocation capability. The result is the currently experienced evolution of wireless networks where mobile location is a natural aid to network management, to a variety of applications and value added services. At this time, the path of the evolution is not clearly focused, neither is the winning set of applications obvious. What we do know is that next generation wireless networks will continue to change the way we live. The first part of the book contains tutorials on three network architectures that aim to achieve this vision. The first chapter, by Ana Lúcia lacono and Christopher Rose of WINLAB, Rutgers University, presents the concept of “Infostations,” that arise from the tradeoff between the size of the radio coverage area of a single transceiver and the feasible information rate. Infostations favor the latter, making use of mobility of users in redeeming the selective patchy coverage pattern. The “anytime, anywhere” motto of PCS is replaced by “manytime, manywhere” access in Infostations. The second chapter by Abbas Jamalipour of the University of Sydney describes the role

2

NEXT GENERATION WIRELESS NETWORKS

of satellites in broadband wireless access. In the third chapter, Patricia Morreale of Stevens Institute of Technology describes the “Infocity” concept, which is based on the integration of wireless and wireline networks in order to provide the envisaged high- speed ubiquitous access to information and communication. The second part of the book includes contributions that describe the state of the art wireless geolocation systems and trends. The first chapter is coauthored by scientists from Bell Labs of Lucent Technologies. Bob Richton, Giovanni Vanucci, and Steven Wilkus depict the widely accepted standard solution to the wireless geolocation problem; i.e., “assisted GPS.” This concept links wireless networks with GPS in order to reach the accuracy and availability requirements for the user geolocation information. The wireless network assumes a supporting role in geolocation, in order to aid the end user equipment through its prescribed communication with GPS. The second contribution, also authored by a Bell Labs scientist, Oguz Sunay, provides a tutorial on all alternatives for wireless geolocation and details the evaluation procedures that are currently under research by standards bodies and relevant work groups. In the third contribution, Malcolm Macnaughton, Craig Scott and Chris Drane, researchers from the University of Technology, Sydney, present the chronicle of research efforts and empirical data collection on the geolocation capability of the existing wireless infrastructure, during which they truly bring theory and practice together in efforts to sharpen the geolocation capability of the wireless system. The third part presents contributions that demonstrate the use of location information in next generation wireless network applications and services. The first contribution, by Mostafa Bassiouni and Wei Cui of the University Central Florida focuses on the use of real time geolocation measurements in improving mobile connectivity and enhancing the effectiveness of fault recovery in configurable cellular networks. The last contribution, by Guenther Popischil, Alexander Schneider, and Ernst Bonek of Technischen Universität Wien, portrays the creation of the “killer application,” for next generation wireless networks. I am proud to have put together this volume comprising of chapters by contributors who are among the elite that are making the future happen. I thank Dr. Oguz Sunay for his invaluable, tireless efforts in ensuring the technical flow and cohesiveness of the book. I would also like to thank Alex Greene, the Publisher of this book from Kluwer Academic Publishers, for his patient, capable help. Finally, I’d like to express my gratitude to my brilliant research associate Mr. Amer Chatovich, whose careful, meticulous pursuance has made this project possible.

Sirin Tekinay

Chapter 1

INFOSTATIONS: NEW PERSPECTIVES ON WIRELESS DATA NETWORKS Ana Lúcia Iacono Christopher Rose WINLAB - Wireless Information Network Laboratory

Department of Electrical and Computer Engineering Rutgers, The State University of New Jersey

Abstract

We discuss file delivery issues for a new approach to inexpensive, high rate wireless data called Infostations. As opposed to ubiquitous coverage, infostations offer geographically intermittent coverage at high speed

(1Mbps to 1Gbps) since data, as compared to voice, can often tolerate significant delay. The infostations paradigm flips the usual “slowradio/fast-network” scenario upside down and offers intriguing new design problems for wireless data networks. Collectively, we at WINLAB believe that the infostations scenario, especially with the emergence of the World Wide Web as both a communications medium and defacto standard is one way to obtain low cost wireless data. And perhaps controversially, we offer arguments that currently proposed extensions to

cellular systems (such as the coming Third Generation) will not be able to offer data as inexpensively. In this chapter we describe the infostations concept and then concentrate on issues above the physical layer. Specifically, we worry about delay bounds on information delivery for variety of simple user mobility scenarios and infostation geometries. We

then provide heuristic algorithms which closely approach these bounds.

Keywords: wireless communications, mobile computing, wireless data, wireless internet, scheduling algorithms, delay bounds, mobility management

4

1.

NEXT GENERATION WIRELESS NETWORKS

INTRODUCTION

Over the past 10 years, wireless voice communication has grown from a rarity to a necessity. In contrast, wireless data services at rates and price sufficient to generate equal excitement remain elusive. In response, the wireless industry has proposed third generation systems with rates in the hundreds of kilobit per second range. However, the dominant traffic on such systems will probably be voice at least initially, and here lies a “Catch-22” first observed by Roy Yates here at WINLAB [1]. Consider that the bit rate currently associated with voice communications is on the order of 10 kbps and let us use this voice channel rate as our unit of measure. This channel costs v cents per minute. It therefore costs approximately 13υ cents to transmit a one megabyte file – prohibitively expensive at current rates. In addition, what is particularly interesting is that this basic fact does not change with the introduction of higher rate services as long as voice is the dominant traffic. One megabyte of data always costs 13υ cents since the basic voice channel rate is unlikely to change drastically for both economic and legacy reasons. Thus, unless normal voice communications becomes essentially free, it seems that wireless data will never be inexpensive when provided using a cellular architecture. This conundrum causes us to re-examine the cellular paradigm. Specifically, cellular wireless was built to carry voice traffic for people accustomed to the reliability and ubiquity of fixed telephone service. Thus, the goal of the cellular industry was coverage anytime and anywhere. However, to provide large coverage the system must be designed so that users both near and far from the access point (a base station) achieve some minimum quality of service. From a systems perspective however, it would be more efficient to serve users closer to the base station at higher rate, be done with them and then serve users farther away. However, for voice systems the implication is intermittent coverage which is incompatible with continuous interactive traffic such as voice. In contrast, data can tolerate delay and the system throughput could be increased by offering rates commensurate with achievable signal to interference ratios. Add to this that customers are often in motion the basic (somewhat surprising) infostations design precept emerges for single non-dispersive, non-directional channels:

Infostations should not be shared between users That is, at any point in time, only one user should be attached to an infostation. This basic idea has roots in information theory and waterfilling of channels in space, time and frequency (see [2] for a development on multiple user dispersive channels). If we consider different frequency

Infostations: New Perspectives On Wireless Data Networks

5

or spatial sub-channels, then the precept still holds if each sub-channel is considered to be an infostation unto itself and users attempt to use the “infostation(s)” with the best channel (s), even though these infostations might be co-located. A possibly non-obvious consequence of such spatio-temporal-frequency water-filling results in another defining characteristic of the infostations paradigm. For users in (ergodic) motion, the places at which transmissions should occur are where the channel quality is above some threshold – a result first shown by Joan Borras [3, 4] and based in part on work by Andrea Goldsmith [5] on fading channels. This implies that a user traveling with uniform velocity in an isotropic environment should transmit or receive only when it is close to an infostation, and from this the notion that

Infostation coverage areas are spatially discontinuous emerges naturally. Thus, we define infostations as a wireless communication system characterized by sequential user access with discontinuous coverage areas and high data rate transmissions. As opposed to the moderate rate ubiquitous coverage in cellular systems, infostations offer high speed discontinuous coverage which may be accessed by users in transiently close proximity to an infostation, and in fact can maximize system capacity. Furthermore, the removal of the need to coordinate channels among multiple users and over the system as a whole should lead to simple inexpensive realizations. And owing to the bursty nature of data communications and its tolerance of moderate delay, the infostation scenario with its inherently lower associated costs might be an attractive alternative to the classical concept of anytime anywhere communications networks.

1.1

EXAMPLES

Although not specifically an infostation, consider a system introduced by Apple, called Airport [6]: a base station that costs $299 and wireless networking cards that cost $99 enable up to 10 computers to share a 11 Mbits/second Internet connection at distances up to 150 feet. As Peter Lewis describes in his article in The New York Times [7]: “ That is so important, and it has such potential to change the way we use computers and information appliances around the house, that I’m compelled to repeat it in a different way: I’m sitting outside the house on the deck, with an iBook on my lap, enjoying a glorious autumn day, reading the current e-news, checking e-mail … There are no wires,

6

NEXT GENERATION WIRELESS NETWORKS

cables or extension cords in sight. As the stars come out, I simply stroll back into the house and continue working from the sofa in the living room.” The salient feature of this narrative is a perceived desire for manytime manywhere web access as opposed to the more traditional anytime anywhere access we expect for voice services. Note in particular that Lewis did not suggest he was using the computer during his journey from deck to sofa. There are a variety of possible infostation system architectures. For example, many infostations may be owned by a single company and they may be clustered and connected to cluster controllers according to their location, creating a hierarchical architecture, as shown in Figure 1.1. This is somewhat analogous to the large telephone company cellular systems where many base stations are connected to mobile telephone switching offices through dedicated high speed lines.

Another possible scenario might have small businesses such as convenience stores carry infostation service as a sideline – analogous to lottery

Infostations: New Perspectives On Wireless Data Networks

7

sales agents. This architecture is shown in Figure 1.2. To be economically attractive, the start up cost to such a “Mom and Pop” operator should be low. There could also be a mixture of the two, as in a franchise setting where infostation operators leased the infrastructure from the founding company.

The network could also be isolated from the Internet and could be used for local communications, as in an office building or home. This is shown in Figure 1.3. Yet another architecture is to integrate infostations with a ubiquitous, low data-rate system (e.g. CDPD or other [8]) and use them as bandwidth boosters. Figure 1.4 shows one example of a hybrid infostation network. According to where infostations are placed, the user mobility can be characterized by three situations [9]: mobile users moving with high speed, such as in a highway, characterize what is called a “drive-through” scenario; users with medium speed, such as in a sidewalk or a mall, characterize a “walk-through” scenario; finally

stationary users, such as in an airport lounge or a classroom, characterize “sit-through” scenario. At WINLAB we have been studying several different problems related to an infostation network. A study of the infostation system performance in terms of capacity, throughput and delay was presented in [4] where various models and different power allocation, symbol rate adaptation

8

NEXT GENERATION WIRELESS NETWORKS

and modulation schemes are presented. A medium access scheme called WINMAC has been proposed in [10] to support efficient packet communications between an infostation and mobile terminals. This protocol adapts to the radio channel condition and achieves enhanced communication reliability through packet retransmission and data rate adjustment. Due to the fact that one of the main services that infostation will provide is Internet access, another area of interest is the design of a link layer protocol to transmit IP packets efficiently via the wireless link. An error control scheme for the Radio Link Protocol is proposed in [11]. The scheme uses multicopy and error threshold detection to improve the system performance. Infostation operation issues such as registration, authentication and billing are addressed in [12]. Some radio design issues are examined in [13]. There is also a variety of other work both at WINLAB and elsewhere ranging from physical layer issues up through applications [3, 12, 14, 15, 16, 4, 17, 18, 19, 1, 8].

1.2

USER MOBILITY AND INFOSTATIONS

One might wish to place an infostations system in an airport lounge, in a conference room or in a small office at an affordable price. One

Infostations: New Perspectives On Wireless Data Networks

9

common characteristic of these situations is relatively low user mobility. Although the coverage area is small, the system is designed based on the fact that the user will stay in the coverage area during the time of the connection and in fact, using beam steering techniques one might “move the infostation” as opposed to moving the user. However, from the perspective of the fixed network, users are in relatively fixed locations. However, when designing system where users roam, then user mobility must be considered since users may visit several infostations during a single connection. For example, a user might roam over a shopping mall with stores offering local infostation services and a user would not stay connected to a single infostation while shopping. Likewise on a highway with infostations at regular intervals users might traverse great distances (from the fixed network perspective) between infostation contacts.

Now consider that data communication, such as messaging systems or web applications, is inherently asymmetric with much greater volume occurring on the downlink from network to user. Under this scenario, if the information is available at the infostation, then the main issue is to

10

NEXT GENERATION WIRELESS NETWORKS

send it to the mobile as rapidly as possible. Since the data rate is high, as long as the user is in the coverage area, this can be done in a few seconds. However, if the information is not available at the infostation and has to be transfered from a server, then the information has to pass through the fixed network before reaching the mobile. Thus, in the “drive-through” scenario, since the coverage area is small, the time which the mobile spends in coverage at a given infostation may not be sufficient to transfer the information from the server to the infostation. This is a situation peculiar to infostations where the radio rate is assumed much higher than the fixed network rate. Given an inexpensive high-speed radio, there are a number possible reasons for this inversion of the status quo. For economy, one could have a low cost relatively low rate connection (i.e. commodity telephone modems) to each infostation. Alternately, even if one connects the infostations with high speed links, some types of services (i.e. HTTP request) have typical transmission rates of the order of Kbits/second. The server transmission rate and network congestion play an important role in determining the speed of the connection. Another scenario would have fixed network links servicing some primary traffic with the infostation as an add-on service sharing these links. Regardless, in all these cases although the radio rate is high, the user would have to restart a request at the next infostation in the path, and this process will increase the delivery delay, especially if only a small fraction of time is spent in coverage by any one user.

1.3

PROBLEM OVERVIEW, MOTIVATION

The obvious solution to this radio/fixed-net mismatch is to cache or prefetch information at the infostations. As an example, an intelligent prefetching algorithm which attempts to predict what the user will need was proposed in [14] as a solution to a location dependent application (map request). The algorithm uses location and speed information to select which of a set of maps should be prefetched. Based on location, time or user dependency, different types of applications would need different schemes for prefetching. However, suppose the information needed is known and can be of any sort such as a web page, a map, or personal e-mail. Then, the issue becomes how to partition the information, and then when and where to send the packets over the fixed network so that they arrive at the user with minimal overall delay. Thus, consider a system where the infostations are connected as a cluster in a hierarchy where there is a higher level with a cluster controller, as shown in Figure 1.5. The cluster controller is the entity that has information on all requests that were made in that cluster and how

Infostations: New Perspectives On Wireless Data Networks

11

many users are being served at every infostation in that cluster. Note that a cluster would be a natural way of connecting different infostations in the same geographical area, but the cluster controller does not have to be necessarily in the same geographical area.

The cluster controller can coordinate the delivery of some packets to the next infostation in the mobile path, so that they are locally available at that infostation when the mobile user arrives in its coverage area. If the path is not known then the cluster controller can send the packets to infostations that are most likely to be in the mobile user path. Therefore, during the time the user is going between two infostations, the system

can download the information to the next coverage area, reducing the delivery delay, as shown in Figure 1.6. The optimization problem is then, given some parameters and system configuration, to deliver the information from its current location(s) to the mobile user in a minimum amount of time. The important parameters that have to be taken into account are: the overall amount of information that is requested, or file size;

12

NEXT GENERATION WIRELESS NETWORKS

the location of the file, which can be stored at the infostation, at the cluster controller, at the home server (Internet) or distributed over a number of locations; the data rate of the wired and wireless network; the number of infostations at the cluster;

the infostations’ location;

the user mobility model. To better understand the approach used here, consider the single user case where there is a cluster with a given number of infostations, M. Let be the rate between the cluster controller and the Internet,

the rate of each link between the cluster controller and the infostations and the radio rate. Assume that the user requests a file, which is then divided into packets, and each packet can be sent to different infostations. Note that if the file is stored in “The Internet” then the network will be able to download the file to the user at the lowest link speed of the network. To take advantage of the fast radio, the cluster controller will prefetch file packets to infostations in the user path. Note that if radio data rate were low, then every request should be re-initiated

Infostations: New Perspectives On Wireless Data Networks

13

at every infostation. That is, with a slow radio, there is little use in prefetching information to the infostations. Therefore we are interested in the case where and . In this case the prefetching approach is helpful and only the radio rate will restrict the maximum amount of information that should be prefetched at a given infostation since there is a limit on how much can be downloaded to the user in the coverage area. Given that the radio data rate is large, the specific delivery problem ranges from the trivial to the difficult. Consider the case when information is stored at some server on the Internet. Since we assume , then the fixed network is the limiting factor. In the case

when then the cluster controller can broadcast all the packets received to all the infostations, as shown in Figure 1.7. All the infostations will have the same information that the cluster controller has, as a copy network. As the user passes through the infostations the radio can then download as many packets as possible to the user and discard packets that were already received.

14

NEXT GENERATION WIRELESS NETWORKS

However if

, then although the cluster controller cannot copy

all the packets to all infostations, it can send different packets to different infostations, as shown in Figure 1.8. As the user passes through new infostations, it can get new packets.

In the same way, if the requested file is locally stored at the cluster controller, then again different file packets can be divided among all infostations in the path, taking advantage of the parallelism of the network. The cluster controller has to decide which packets to put in which infostations so that, when the user passes through the infostations, it obtains the most amount of information possible. The number of packets that can and should be prefetched is a function of the backbone rate and the radio rate . Note that if the Internet rate is very high

then the scenario is similar and we can assume that the file is locally stored at the cluster controller, as shown in Figure 1.9 In general, the cluster controller has a buffer where it queues all the file

packets. According to how large

is, the size of the largest buffer (if the

file is locally stored at the cluster controller then the buffer contains all

the file packets). Thus, the cluster controller can coordinate the delivery

Infostations: New Perspectives On Wireless Data Networks

15

of these packets to different places and it can send copies and/or different packets to every infostation in the cluster. According to the radio rate and time spent in the coverage area, each infostation should only store some maximum amount of information, since the user will not be able to transfer all the packets during its brief visit to the coverage area. This more general case is shown in Figure 1.10 Let us assume that there are N infostations in the user path before completion of file delivery. Note that the value of N will be a function of the file size, the delivery algorithm used, the user mobility model and

the rates and . In any case, we call this number N, although the value could be different in each situation. Assume that bits/second is the maximum data rate necessary so that the radio is able to download all packets that are prefetched to a given infostation. Note that the value of M will be a function of the total file size, the delivery algorithm used and the user mobility model.

For a given value of , the problem space diagram is shown in Figure 1.11. Region (1) is the case where and the cluster controller

16

NEXT GENERATION WIRELESS NETWORKS

should just broadcast every information received to all infostations. Region (2) is where the radio is the bottleneck of the network and there is no reason for caching any information since it will not be delivered to the user anyway. Therefore our study lies in region (3). In region (3a) the rates and are as large as necessary to take the most possible advantage of parallelism of the network for a given file size. That implies that either the file is stored at the cluster controller or . It also implies that the radio rate is very fast and all packets prefetched to the infostations can be downloaded to the user during the time it is in the coverage area. If the rate is not as high then it is not possible to bring the the desired amount of information to the cluster controller in order to spread it over the many slow links. The cluster controller can then send different packets to some infostations and copy others in more than one place. Regions (3b) and (3d) represents this situation. In other words, the queue at the cluster controller will have a small number of packets and

Infostations: New Perspectives On Wireless Data Networks

17

they can be copied to some infostations. In regions (3c) and ( 3 d ) , the radio imposes a l i m i t on the number of packets that should be prefetched to the infostations since only some maximum number of packets can be downloaded to t h e user during its passage through the coverage area. Having exercised the various overall model parameters and identified a number of scenarios – some trivial, some not, we can state the file delivery problem for infostations simply. Let be a set of algorithms which transmit parcels of information to each infostation for delivery to a user. Let D be the delivery delay seen by that user, defined as the

18

NEXT GENERATION WIRELESS NETWORKS

total time between the initiation of the request and delivery of the final parcel. The optimization problem is then to

Find absolute lower bounds on delivery delay

Find algorithms which approach or meet these lower bounds In this chapter, we will consider these problems for different mobility models and infostation structures for single users. The multiple users case is treated elsewhere [17] and will be the subject of near-future publications .

2.

TOURS IN ONE DIMENSION: THE HIGHWAY SCENARIO

Consider a one-dimensional model where users move along a line populated with equidistant infostations. Our objective is to derive lower bounds on information delivery delay. In the first section we study the case of constant velocity, where users move with a fixed velocity and fixed travel direction. In the second section we study the case where users travel with constant speed but random travel direction – a onedimensional random walk. This constant velocity model, although simple, covers important situations such as highway or railroad travel. Furthermore, it serves to illustrate some of the basic concepts of file delivery

under the infostation model. In this section we assume that information can be delivered from the backbone to the clusters at or above the backbone rate and that likewise, the radios are speedy enough that were an entire file available at the infostation, it could be downloaded during one passage through the coverage area.

2.1

CONSTANT VELOCITY

Consider a system with many infostations equally spaced at distance d meters, as shown in Figure 1.12. Assume that the mobile travels at constant velocity v m/s, the size of the coverage area is and that the

wired backbone transmits at a rate of

bits/sec.

The mobile will arrive in a given infostation and request a file of size

F bits. If

then the mobile can receive only a part of the file at the first infostation. Completion of the transaction must be deferred until it arrives at the next infostation. Assuming a start/stop protocol where incremental requests must be initiated at each new infostation visited, the number

Infostations: New Perspectives On Wireless Data Networks

19

of infostations, I, that the mobile has to pass to receive the whole file is

where represents the smallest integer greater than or equal to x. The time required for travel between two infostations is d/v and therefore the delay D in seconds, to transmit the file is

which we can rewrite as

Note that to decrease the delay one could decrease the distance be-

tween infostations thereby increasing the infostations density and moving toward a more ubiquitous coverage area scenario.

In our approach we assume that , which means that all information that is available at the infostation can be downloaded to

the mobile before it leaves the coverage area regardless of the amount. We also assume that , which means that the cluster controller has all the file pieces necessary to be able to prefetch any amount of information necessary to the infostations. Note that if the information

is locally stored at the cluster controller, then the value of

is irrelevant

and the condition always holds. In the case of constant velocity, given the initial position, the path is known. Therefore, rather than initiating new transfers at each infosta-

tion, the time the mobile is traveling between infostations may be used to download part of the file to the other infostations along the mobile

tour. Since the time spent traveling between two infostations is given by , the system can download B (different) bits to each infostation in the tour, where

20

NEXT GENERATION WIRELESS NETWORKS

Likewise when the mobile leaves the second infostation the same amount can be downloaded to the remaining infostations and so on. Therefore, to transmit the whole file we require

Thus, the smallest number of infostations, I, required for delivery of the file of size F is obtained by determining the smallest integer I such that

Therefore

and the delay

, in seconds, is given by

which we rewrite as

Note that the delay now does not depend on the size of the coverage area. In Figure 1.13 we can see the delay as a function of the file size for both situations: The delay without the prefetching approach, which is given by equation 1.3 and the delay obtained when the prefetching approach is used, given by equation 1.9. We can see that there is a large improvement when the prefetching approach is used. We also note that the delay stays invariant for a larger range of file sizes when the prefetching approach is used. Another interesting fact is that the velocity, υ, affects the delay. Equations 1.3 and 1.9 show that the delay decreases as the velocity increases. Thus, it behooves the mobile to move rapidly, passing through a large number of infostations. As can be seen Figure 1.14, equation 1.9 is more sensitive to the velocity. In this case, the network-to-infostation

Infostations: New Perspectives On Wireless Data Networks

21

bottleneck is essentially removed by spreading the communication over many slow links. The ripples in the curve are due to the fact that the ceil function remains constant for a range of values of υ, while the denominator increases with υ Certainly there is a limit to the improvement. It should first be noted that we assumed that there were as many infostations as needed in the user path. This may not be the case since the number of different infostations along a given tour may be limited. Furthermore, since the network usually transmits packets and frames, there may be some minimum number of bits,

, that can be delivered during a transmission. Thus,

deliveries could only be made by every infostation along the tour if v is such that . However, even for infostation placement as close as one city block (0.05 mile), a typical

bytes, and a line transmission rate of 56Kbits/s, υ would have to exceed 2.7 miles per second. For comparison, jetliner velocities are typically on the order of 0.1 miles per second.

22

2.2

NEXT GENERATION WIRELESS NETWORKS

THE RANDOM WALK

Now consider the scenario where the mobile moves with constant velocity, but at each step the direction is random – it can go to the right or to the left with probabilities and , respectively. Note that in this case the path is not known a priori. We would like to have bounds

for file delivery delay for the random walk scenario. Let a step be a motion between two infostations and, at every step, the mobile either goes to the left or to the right, it does not stay at the same infostation. 2.2.1 Delay Bounds. Assume that we have an optimum algorithm, in the sense that it minimizes the delay. That is, the algorithm sends file parts to each infostation as if it knew the path. Assume the initial position is position 0. If the file size is F bits then it can be divided into N segments, such that

Infostations: New Perspectives On Wireless Data Networks

23

If the optimum algorithm is used, then the maximum number of infostations needed to the left and right of the mobile so that the whole file can be downloaded is given by

where represents a boundary where delivery completion. In other words, while pleted, the mobile will be restricted to the shown in Figure 1.15. If the mobile actually

the mobile stays until file the transaction is not comregion , as goes on a straight line, the

delay is the minimum possible given by

If the mobile keeps hopping between two infostations then the maximum number of parts it can get is 1 in the first step and then 2 in all next steps. That will create a situation where the mobile passes through the maximum number of infostations, before file delivery completion. To find will be the smallest integer such that

Therefore, the maximum delay, in seconds, is given by

and thus, Thus, equation 1.16 gives an upper an lower bound for the delay, in seconds, for file delivery completion using the prefetching approach.

24

NEXT GENERATION WIRELESS NETWORKS

2.2.2 Average Number of Segments. Equation 1.16 provides upper and lower bounds for the delay but it does not provide average delay for a given motion process. Therefore we will calculate the average number of segments that can be downloaded to an infostation if an optimum algorithm that minimizes the delay is used. From this we can infer the approximate average number of steps, and thereby delay, necessary to deliver files of various sizes. Assume that the mobile passes through position i for the first time at time t and once again at time . Assuming the download process starts at time 0, the maximum number of new file segments that can be downloaded to that infostation at time t is t file segments. Furthermore, the maximum number of new file segments that can be delivered at position i at time is n. Thus, it can be seen that for any optimal algorithm, the cumulative number of file segments obtained by a visit to location i at time t is exactly t regardless of the path taken to location i. This result suggests that delay depends on the number of infostations that are revisited in a path, that is, if fewer infostations are revisited then more new file segments are obtained at each step and the time necessary to completely transmit the file is reduced. Let us assume that the path is limited to s steps. Let be the probability that location x was last visited at time given that the path is limited to s steps. If a location was visited at some time t, then the maximum number of segments that could have been downloaded, cumulatively, is t. If an optimum algorithm is used, then the number of segments downloaded would be exactly t. Given that, for an optimum algorithm, the mean number of file segments, , picked up by step s is then

To calculate the value of it is necessary to calculate will do that using first passage times.

. We

2.2.3 First Passage Times. Our goal is to calculate , the probability that location x was last visited at time given that the path is limited to s steps. If one looks at the motion process in the reverse direction, then is simply the probability that, starting at some position n, the first passage through x is at time . Observe that for that to be possible it is necessary that

Infostations: New Perspectives On Wireless Data Networks

25

Without loss of generality, assuming , the number of paths from the origin that pass through position x for the first time at time , , is given by [20]

gives the number of possible paths. Each of these paths has a probability which is a function of p and q. The sum of all these probabilities gives the probability that the first passage time through position x is given at time s – t. In order to calculate this probability we divide the problem in two cases: the positions to the left and right of the mobile. We will assume that the mobile at position 0. We first choose a position to the right of the mobile, say position r. We want to calculate the probability of a path that starts in 0 and passes through r for the first time in steps. We know that there are paths with this property. But the probability of each one of them is exactly the same. This statement

will become more clear with the discussion below. The probability of a path that starts in 0 and passes through r for the first time in steps will be a function of the number of steps taken to the right and to the left. Assuming all steps are independent of each other, if the mobile take steps to the right and steps to the left, the probability, , of this path is given by

In order to satisfy the first passage time condition

In order to arrive to position r, we need that

which implies that

for all the given by

paths. The number of steps to the right,

, is

26

NEXT GENERATION WIRELESS NETWORKS

and then we conclude that the number of steps to the left and the number of steps to the right is the same for all paths that start in 0 and end in r after steps. It is important to note that and must be integers and therefore must be even or, equivalently, must be even. The probability of a given path that starts in 0 and passes through position r for the first time in steps is then given by

And there are

of these paths.

A similar analysis for a given position r to the left of the mobile gives that the probability, , of a path that starts in 0 and passes through position for the first time in steps is given by

The total number of these path is also given by

Note that this case also requires to be even. Finally, the total average number of file segments picked by the mobile after s steps, is given by

where

where the first summation represents the positions to the left of the

mobile and the second summation represents the positions to the right of the mobile.

Infostations: New Perspectives On Wireless Data Networks

27

2.2.4 Special Cases. Two special cases of interest are the symmetric case, where , and the straight line case, where Assuming the symmetric case, the probability of each path is given . Then

and

where

For the case where we have the situation described in Section 2.1 (constant velocity), where the mobile comes from the left to the right in a straight line. In this situation the second summation will be zero, and the first summation is only non zero for , since there is only one possible path. Therefore we have

which is similar to the result in Section 2.1. In Equation 1.6 the variable T represents the number of infostations required for delivery of F bits and plays the role of the variable s in Equation 1.33. The difference between Equations 1.6 and 1.33 is the factor used to transform from number of segments to number of bits. Figure 1.16 shows the bounds on average number of pieces picked after a given number of steps, , as a function of s. We start with and we increase the value of p. Because of the symmetry of the problem, the results increasing the value of q are similar, or, in other words. p and q can be exchanged. As can be seen, the results for the straight line give highest bound. As the probability p increases the bound approaches the lower bound, which is achieved with the symmetric case This suggests that the average number of pieces is closely related to the number of revisits to a given place. In the straight line case the

28

NEXT GENERATION WIRELESS NETWORKS

mobile never revisits a given position, and therefore at every step a higher number of pieces can be downloaded. As we mentioned in Section 2.2.1, the minimum delay is achieved when the mobile moves in a straight line

and the maximum delay is achieved when the mobile hops between two infostations. In the next section we will discuss this topic further.

3.

EXTENDING TO HIGHER DIMENSIONS: THE GRID, THE CUBE, ETC. Results for first passage times helped us to derive the bounds for the

one-dimensional case. Since we were unable to find first passage time results for higher dimensions are not available in the literature, these

results are provided here so that we may derive bounds on the average number of pieces delivered. We assume the same radio and links rate scenario as in the single dimensional case.

Infostations: New Perspectives On Wireless Data Networks

3.1

29

THE TWO-DIMENSIONAL PROBLEM

We first extend the one-dimensional case to two-dimensions. Let us consider that the infostations are equally spaced in a rectangular grid as shown in Figure 1.17. The mobile can go right, left, up or down with probabilities and , respectively. At every step the mobile chooses one direction and does not stay at the same position. The velocity is still assumed constant for internode moves.

We want to calculate the average number of file segments that can be picked up by step s, . Let be the probability that location (x,y) was last visited at time given that the path is limited to s steps. Similar to the one-dimensional case, we have

Observing the motion process backwards, as we did in the last section, then is simply the probability that, starting at some position , the first passage through ( x , y ) is at time . Observe that for that to be possible it is necessary that We need to calculate the first passage time through some position ( x , y ) . Since we were unable to find this result in the literature we will derive it here, starting with the multinomial distribution. Assume x and y positive. Without loss of generality, assume .. We will first calculate the total number of paths that start in (0, 0) and pass through

30

NEXT GENERATION WIRELESS NETWORKS

(x,y) in s steps,

. Note that a necessary condition is that

Let be the number of steps taken upwards, the number of steps downwards, the number of steps taken to the left and the number

of steps taken to the right. The total number of paths that start in the origin and pass through (x, y) in step s is given by

where

In order that the mobile arrives at position y, it is necessary that

And since it will also have to get to position x,

and

The number of steps upwards,

needs to satisfy

Because the number of steps has to be an integer, we also need that (s + x + y) mod 2 = 0. Therefore, for and , we have

Note that the same holds for x or y non positive, depending only on the absolute value of x and y. Therefore the number of paths with s steps, from the origin to (x, y) is given by

Infostations: New Perspectives On Wireless Data Networks

31

gives the total number of paths from the origin to some position ( x , y ) in s steps. That includes paths that pass through ( x , y ) at some time also. In order to obtain the number of paths that have the first passage through (x, y) at step s, it is necessary to remove

the paths that pass through (x, y) at s and before s also. Let be the number of paths that start at some position and return to that same position for the first time in i steps. Note that i must be even. Then, the total number of paths starting at the origin that pass for the first time through position (x, y) in s steps, , is given by

where we eliminated the paths that also pass through that position before time s. These are the paths that pass through that position for the first time at time , and then return to that position in i steps, for all i even, and To calculate we start with the total paths from some position to itself in i steps, . To calculate the total number of paths that

start at some position and return to the same position for the first time in i steps it is necessary to eliminate the paths that also pass through that position before time i. Similarly to before, these are the paths that

pass through that position for the first time at time return to that position in p steps, for all p even, and

, and then

And we know that

therefore the value of , i even.

can be calculated, using recursion, for any

32

NEXT GENERATION WIRELESS NETWORKS

The probability of the paths that start at the origin and pass through position ( x , y ) at time s, and is given by

, will be a function of x, y and s

where

But calculating the probability of the paths that start at the origin and pass for the first time at position ( x , y ) at time s is not trivial. For that reason we will consider here the symmetric case where . Observing the motion process backwards, as we did in the last section for the one-dimensional case, and considering the symmetric case, one can derive the average number of file segments picked up by step s is then given by

The condition is included because we assume that the user is at the origin at step s and therefore it got cumulatively s segments, which are added separately in equation 1.48. In Figure 1.18 we present the average number of segments picked after s steps, for the symmetric two-dimensional case. We also present for the one-dimensional case, for different values of p and q (please refer to Section 2). One could expect that the curve for two-dimensional case would match with the case of . That is not the case because in the one dimensional case the probability of revisits to a given position when is higher than for the twodimensional case. As we can see from the figure, the value that most approaches the 2-d case is

3.2

THE N-DIMENSIONAL PROBLEM

Extending the two-dimensional to the n-dimensional problem is straightforward. Of course, one might ask “why bother?” First, one could easily

Infostations: New Perspectives On Wireless Data Networks

33

imagine 3-dimensional infostations models. However, although the infostations problem was couched in terms of moving matter (people, vehicles, etc.) and radios, a possibly quixotic generalization might include migrant programs (mobile agents) operating over a computer network in an almost arbitrary dimensional data space and other fixed programs

which need to pass large data files to the agents as they move over the network. In addition, practical utility aside, the same machinery to consider three dimensions allows consideration of N dimensions. Thus, since the incremental effort necessary for generalization is minimal, it is therefore provided here. Equation 1.44 is still valid for the n-dimensional case, where now is the number of paths with s steps from the origin to position . This number is easily calculated using the multinomial distribution as in Equation 1.42, but now with n – 1 summations, as

34

NEXT GENERATION WIRELESS NETWORKS

and

For the case where n = 3, for example, we would have

But we know from condition 1.50 that

which implies that

We also know that the maximum value of is obtained when and and therefore from condition 1.50 the maximum value of is obtained when

which implies that

and similarly, the maximum value of

which implies that

is obtained when

Infostations: New Perspectives On Wireless Data Networks

35

and finally we can write

where

and

Returning to the general case, the number of paths that start at

the origin and pass through

for the first time after s steps,

, is given by

where

and

In general, for the symmetric n-dimensional case, we can write the average number of file segments picked at step s as

36

NEXT GENERATION WIRELESS NETWORKS

Figure 1.19 shows the average number of file pieces picked in s steps for one-, two- and three-dimensional problems, for the symmetric cases.

increases as n increases since the number of infostations revisited in a path decreases. Also shown in Figure 1.19 is the case where the mobile never revisits an infostation. Figure 1.20 shows the average number of times the mobile revisits a given position in a motion process along a path of length s. This is simply the number of paths that start in the origin and return to the origin after s steps times the probabilities these paths. For the two-dimensional symmetric case, for example, the average number of revisits in s steps is given by . As can be seen from the figure, as the number of dimensions increases the number of revisits decreases.

4.

A NEAR-OPTIMUM ALGORITHM

In the last two sections we presented bounds on file delivery for a general n-dimensional model. Those results give bounds on the maximum number of file segments that can be downloaded for the user in the case where and and were derived assuming that an op-

Infostations: New Perspectives On Wireless Data Networks

37

timum algorithm is used. But it does not tell us how such an algorithm would work. Therefore, in this section we will provide an algorithm for the one-dimensional case. Given that the file can be divided in many different smaller segments, and we label each segment, the role of the algorithm is to decide after every step which segments should be sent to which infostations. As always, the goal is to minimize the overall file transfer delay.

4.1

OVERVIEW

We will concentrate in the one-dimensional scenario, as shown in Figure 1.21, where infostations are equally spaced at distance d.

38

NEXT GENERATION WIRELESS NETWORKS

Assume a file of size F, and this file is divided in N segments of size B, where

and

Given that the mobile is at some position x, an algorithm that delivers file segments to infostations around that user will have to deliver segments to a given number of infostation to the right and left of the mobile. Therefore our algorithm will work in a range of Infostations. The first important characteristic of the algorithm is the calculation of the boundaries in the range. These boundaries are the maximum number of infostations necessary to the left and right of the mobile so that the mobile is able to receive the whole file. Note that they should be recalculated at every step of the algorithm. In order to maximize the number of file segments received at each step, the algorithm schedules different segments to each infostation, so that there are no repetitions and no segments wasted. After all the segments are spread over the range of infostations, then one can no longer avoid repetitions. From that point on the algorithm avoids sending repeated segments to positions that are in a possible path for the mobile. Details of the algorithm are described in the following sections.

4.2

THE RANGE OF INFOSTATIONS

As seen in Section 2.2, as long as the mobile picks the maximum number of file segments at every step, the maximum number of infostations needed to the left and right of the starting position is given by where

If the mobile is at position i then an optimum algorithm does not have to consider infostations that are outside the range After the mobile moves to the left or right new boundaries must be calculated. To do so the history of the movements is considered. All segments that were already obtained by the mobile and all the segments already delivered to infostations are considered. In addition, undelivered new segments still to be scheduled must also be taken into consideration. The number of new segments that will be scheduled is calculated using the assumption that an optimum algorithm will be used. Note that the

Infostations: New Perspectives On Wireless Data Networks

39

boundaries will be given by one infostation to the left of the mobile and one infostation to he right of the mobile. We define infostation at which the mobile user will receive the last file

segment if it moves from infostation i to in a straight line, taking only steps to the right. We assume that, when this path is taken, the mobile receives all the segments already delivered to the infostations in the path plus new segments that will be delivered using an optimum algorithm (new segments would not be copies of segments delivered before). infostation at which the mobile user will receive the last file segment if it moves from infostation i to in a straight line, taking only steps to the left. We assume that, if this path is take, the mobile receives all the segments already delivered to the infostations in the path plus new segments that will be delivered using an optimum algorithm (new segments would not be copies of segments delivered before). For example, consider the situation where the file can be divided in 10 segments, . In this case the maximum number of infostations needed to each side of the mobile is

Assume that the mobile is at position 5. Then the range of infostations is given by [1,9], as shown in Figure 1.22. position:

1 2 3 4

5

6 7 8 9

M Figure 1.22 Example for a file with 10 segments: calculating boundaries,

and

After the boundaries are calculated, then the algorithm must decide which segments to prefetch in which infostations during the first step. The algorithm will deliver different segments to every infostation in the range, as shown in Figure 1.23

After the mobile moves, say to position 4, one segment up, as shown in Figure 1.24.

is picked

40

NEXT GENERATION WIRELESS NETWORKS

It is now necessary to calculate the new boundaries. The left boundary is still the same, and the right boundary is calculated using the following facts: Mobile has already received to complete the file.

. There are nine segments missing

If the mobile goes in a straight line to the right it will pick all the segments that are scheduled plus new segments that will be scheduled. If we assume that the next segments will be scheduled using an optimum algorithm, then the mobile would pick two segments in position 5, three segments in position 6 and finally four segments in position 7, which gives a total of nine segments and therefore the mobile would finish the transmission at position 7 (please see Figure 1.25.

Infostations: New Perspectives On Wireless Data Networks

41

Therefore the new boundaries are and and positions 8 and 9 do not have to be considered anymore in our scheduling process. Now the algorithm has to schedule segments to be delivered to the range [1,7]. Note that the only segment delivered to the mobile is and therefore should not be scheduled. Note also that segments and are already delivered to the infostations in the

range. Therefore segments and should be scheduled. The other five segments must be a copy of segments already delivered to the infostations. One way of scheduling segments is shown in Figure 1.26

Now suppose the mobile moves to position 5 and picked segments and . The boundaries must be re-calculated. The mobile has already received 3 segments . To the left

the mobile can receive two segments at infostation 4, four segments at infostation 3 and five segments at infostation 2, a total of eleven segments (please see Figure 1.27) Since only seven segments are missing,

the left boundary is

. To the right, since segments

and

were already delivered to the user, they are wasted at infostation 6. Therefore at infostation 6 the mobile can receive only one new segment,

four segments at infostation 7 and four segments at infostation 8, a total of nine segments (please see Figure 1.28. Thus the right boundary is

Note that the scheduling choice was not very smart and some segments were wasted. Choosing where to copy which segments is not an easy task, and it is the objective of the algorithm. We will discuss the scheduling of segments in the next sections. Note that if the algorithm is optimum then the new boundaries may decrease, but never increase. We then define, at any given step:

42

NEXT GENERATION WIRELESS NETWORKS

N: total number of segments in the file. i: mobile user position. total number of segments already delivered to the mobile user. set of segments that were scheduled to infostation j but not delivered to the mobile user.

set with segments that were scheduled to infostations in the range [i, j]. Thus

And with these definitions we can write

and

The right boundary is the smallest integer

as follows.

such that:

Infostations: New Perspectives On Wireless Data Networks

The left boundary is the largest integer

4.3

43

such that:

PARTIAL PATHS

To maximize the number of file segments received at each step, the algorithm should schedule different segments to each infostation, so that there are no repetitions and no segments wasted. After all the segments are spread over the range of infostations, then one can no longer avoid repetitions. The problem is then to decide which copies of segments should be sent to each infostation. It is important to note that although we can calculate the boundaries, that does not imply that the mobile will pass through all the infostations in that range. For example, if the mobile goes in a straight line to the left, it will never visit infostations to the right of its initial position. This fact is very important and will be used in the algorithm. To be able to describe the algorithm we will define:

maximum number of file segments that can be delivered to the mobile if it takes a given path P.

Partial Path from infostation i through infostation j: a path that starts at infostation i, passes through infostation j, and the mobile has the potential to receive at most the total number of file segments still needed. Thus a path P is a partial path if and only if

set of all infostations that belong to all partial paths from i through j. set with all segments scheduled to infostations that belong to

To better understand the idea of partial paths, we consider the exam-

ple given before. The mobile started at position 5, moved to position 4 and received one segment , as shown in Figure 1.29.

44

NEXT GENERATION WIRELESS NETWORKS

Let us obtain the partial paths from infostation 4 through infostation 5. The paths and are all partial paths from 4 through 5. In path A the mobile can receive at most two segments at infostation ; in path B the mobile can receive two segments at infostation 5 and three segments at infostation 6, a total of five segments and in path C the mobile can receive two segments at infostation 5, three segments at infostation 6 and four segments at infostation 7, a total of nine segments Note that the path is also a partial path from 4 through 5, but it includes the same infostations. The paths and are also a partial paths from infostation 4 through infostation 5. In path D (please refer to Figure 1.30) the maximum number of segments that can be delivered is segments (at infostation 3) segments (at infostation 4) segments (at infostation 5)

In path E (please refer to Figure 1.31) the maximum number of segments that can be delivered is segments (at infostation 5) segments (at infostation 4) segments (at infostation 3)

Infostations: New Perspectives On Wireless Data Networks

45

We then know that infostations [3,7] belong to partial paths from 4 through 5, or belong to . In order to find if infostation 2 belongs to we observe the paths (Figure 1.32) and (Figure 1.33). Since segments (at infostation 5) segments (at infostation 4) segments (at infostation 3) segments (at infostation 2) and segments (at infostation 3) segments (at infostation 2) segments (at infostation 3) segments (at infostation 4) segments (at infostation 5) then

and

and thus G and F are not partial paths from 4 through 5. Therefore infostations 1 and 2 do not belong to partial paths from infostation 4 through 5, and

It is important to note that after the boundaries are calculated, all the infostations to the left of the mobile, except from , always belong to a partial path between the mobile and any infostation to the left of the mobile. The infostation may or may not belong to a partial path. The same argument applies to infostations to the right of the mobile. For example, consider the case where the file divided in a total of segments. Assume the mobile is at position 3. The boundaries

46

NEXT GENERATION WIRELESS NETWORKS

in this case are and . but infostation 5 does not belong to a partial path from 3 through 4, since 4.3.1 Calculating . As seen in the last section, in order to verify if a path P is a partial path one need to find . Therefore it is important to have a general equation for Consider the scheme shown in Figure 1.34.

Infostations: New Perspectives On Wireless Data Networks

47

Consider the path A as

can be written as (please see Figure 1.35):

It is interesting to observe the example in Figure 1.35 where we can clearly see that at step s the mobile can pick cumulatively at most s segments. Consider now a path B given by

Similarly

And therefore, in general, for a path and y are at opposite sides of i and x is visited before y, function of (i, x, y) and can be written as

where x will be a

48

NEXT GENERATION WIRELESS NETWORKS

where if then and if then and x is visited before y. For example let us consider again the example given in Figure 1.29 and the paths and . Then, for path . From Equation 1.80

For path from equation 1.78

and the results match with the one presented in the last section, given by Equations 1.74 and 1.75. 4.3.2 Infostations in Partial Paths. As we mentioned before, after the boundaries are calculated, all the infostations to the left of the mobile, except from , always belong to a partial path between the

mobile and any infostation to the left of the mobile. The infostation may or may not belong to a partial path. The same argument applies to infostations to the right of the mobile. In order to guarantee the inclusion of and we define

Our goal now is to obtain the set or . We want to find all the infostations that belong to all partial paths from i through j. As we saw in the example in the last section, it is not necessary to obtain all partial paths from i through j in order to obtain Consider again the scheme shown in Figure 1.34. The mobile is at position i and one wants to find , where , or j is an infostation to the right of the mobile. We know that he set is constituted of all

Infostations: New Perspectives On Wireless Data Networks

49

infostations in , where k is the left-most infostation that belongs to a partial path. In order to check if an infostation k belongs to a partial

path one could check if the paths

and

are partial paths. Therefore it is necessary to verify, for each path, if the number of segments that the mobile can receive if the path is taken is less than or equal to the total number of file segments still needed. We need to verify if

and Note that both paths contain the same infostations, but they may be

of different sizes, or different number of steps. Define the number of steps in a given path P. But we know that

and therefore, it is that starts at i and So we conclude partial path from i if

necessary and sufficient to check if the shortest path passes through j and k is a partial path. that, in general, to check if an infostation k is in a through j, where i is in the middle of k and j

, to check if an infostation k is in a partial path from i

through j it is necessary and sufficient to check

if then to check if an infostation k is in a partial path from i through i it is necessary and sufficient to check if

Therefore: if

then

50

NEXT GENERATION WIRELESS NETWORKS

if min * if

if min * if if

then then belongs to a partial path from i through j.

then then belongs to a partial path from i through j.

then if

then * k belongs to a partial path from i through i.

4.3.3

Obtaining

. As we saw in the last section, we can

write

or,

if

then

, where

is the

left-most infostation that belongs to a partial path from i through

if then , where is the rightmost infostation that belongs to a partial path from i through j.

Infostations: New Perspectives On Wireless Data Networks

51

if then , where is the rightmost infostation that belongs to a partial path from i through i and is the left-most infostation that belongs to a partial path from i through i.

In other words, it is necessary to find the first infostation to the right (or left) to the mobile that belongs to a partial path from i through j. 4.3.4 The set v(i, j). Once the set is obtained, obtaining v(i,j) is straightforward. If the importance of this set in the algorithm is not clear yet, it should be after this section. Assume the mobile is at position i and all the segments that were not delivered to the mobile are already scheduled to the infostations. The algorithm has to decide what to schedule to a given infostation j. Once we calculate the set of infostations that belong to partial paths, , the best solution is to schedule a segment that is not scheduled to any infostation in the set , or a segment that do not belong to If a segment that belongs to is scheduled to an infostation that belongs to then there is a probability (different than zero) that this segment will be wasted if the mobile takes one of the partial paths. On the other hand, if the segment does not belong to then this segment could be scheduled to any infostation in . Assume . As we mention before the set may or may not include the the last infostation in the range, . But we also do not want to copy a segment that is scheduled to in j since there is a probability (different than zero) that this segment will be wasted. The same applies to infostation , if . For this reason we will work with the set and v(i, j). In order to clarify the importance of these sets, please refer to the example shown in Figure 1.24. The file is divided in 10 segments, the mobile is at position 4 and picked one segment . The algorithm has to schedule new segments for the next step. Since segments and are not scheduled, they can be scheduled to positions 2, 3 and 4, for example, as shown in Figure 1.39.

52

NEXT GENERATION WIRELESS NETWORKS

In order to decide what to schedule at the other infostations it is necessary to consider each infostation separately. Let us consider infostation 5. Starting at the user position (infostation 4) there are several partial paths from 4 through 5. The set

includes all the infostations in all partial paths. This set creates a box, as shown in Figure 1.40.

All segments that are already scheduled to infostations in the box, or were delivered to infostations in the box in previous steps, should not be scheduled to infostation 5. The set with these segments is given by

Thus, we could schedule segment Figure 1.41.

to infostation 5, as shown in

It is clear from the figure that the segment would never be delivered twice to the mobile, since the file delivery would end before the mobile passes through both infostations, 5 and 1, no matter which path is taken. The configuration shown in Figure 1.42 would also be possible, where segment is copied in two infostations. Note that in this case segment

Infostations: New Perspectives On Wireless Data Networks

53

could be delivered twice if path is taken. But note that this would not increase the delivery delay in terms of number of infostations, since at infostation 2 only one segment need to be delivered (assuming that infostations 3, 4 and 5 always deliver new segments).

4.4

THE ALGORITHM

Let N be the total number of file segments. Let i be the infostation where the mobile is located at a given step. At every step the algorithm will do:

1. Calculate boundaries 2. Obtain 3. For each infostation

Find If

and do:

and v(i,j) then

– schedule a segment – add the segment to Else – If

then

to infostation j;

54

NEXT GENERATION WIRELESS NETWORKS * schedule a segment * add the segment – If

to infostation j; to

then * schedule a segment

and:

• If then schedule from the range ing from the set

start-

• If then schedule from the range ing from the set

start-

• If

then schedule from the set

or

• add the segment to

The algorithm loses its optimality if, at a given step, and, for some j, At this point the choice of what to send to j is heuristic. Using the idea that the boundaries may decrease, we bring something from the boundaries since that infostation may be removed from the range considered. This choice is not proven to improve the performance, but it is a good heuristic choice. Other methods could be used.

4.5

AN EXAMPLE

In this section we will present an example of the algorithm application to a file that is divided in 10 segments. The number of infostations that have to be considered is nine (four on each side of the mobile). We assume that the mobile starts at position 5, and the parts are scheduled at every step. Below is the output of the algorithm: step 0:

mobile starts at position 5: step 0: mobile: position:

step 1:

1

2

3

M 4 5

6

7

8

9

mobile goes to position 4: new boundaries are and are repeated out of partial paths:

Infostations: New Perspectives On Wireless Data Networks step 1: step 0: position: mobile: step 2:

1

2

3

4 M

5

mobile goes to position 3: new boundaries are

6

7

8

55

9

;

nothing is scheduled to position 6 since all parts belong to v(3, 6): step 2: step 1: step 0: position:

1

2 3

mobile: step 3:

4 5

6 7 8 9

M

mobile goes to position 4:

new boundaries are

;

nothing is scheduled to position 6 since all parts belong to

v(4,6); contains all the segments and therefore

is brought

from position 6: step 3: step 2: step 1: step 0: position:

mobile: step 4:

1 2 3

4 5

6 7 8 9

M

mobile goes to position 3: new boundaries are ; nothing is scheduled to position 2 since all parts belong to v(3,2); nothing is scheduled to position 5 since all parts belong to v(3,5); contains all the segments and therefore is brought from position 5; is repeated in position 3 since it is not in v (3,3):

56

NEXT GENERATION WIRELESS NETWORKS step 4: step 3: step 2: step 1: step 0:

position: mobile: step 5:

4.6

1

2

3

4

5

6 7 8 9

M

mobile goes to position 2; file transfer is complete.

PERFORMANCE OF THE ALGORITHM

The average number of file segments picked up by step s,

, was

obtained through simulations. We performed 900 trials for each value of s, meaning that we have 900 independent random walks for each value of

s. Assuming a large enough number of file segments that it is impossible for them all to be picked up by step s, we take s steps and count the total number of segments that are picked up by the mobile. This result is compared with the theoretical result given by Equation 1.31 and a simulation assuming an optimum algorithm. The results are shown in Figure 1.43 with confidence intervals about each point smaller than the

symbol size. As can be seen, the three curves are hard to differentiate. Because the number of segments picked even with the optimal algorithm depends on the path chosen, there is considerable variance in the number of segments picked up at any given step. Shown in Figure 1.44 is the corresponding standard deviation for our algorithm and for the

optimum which again suggests the near-optimality of our algorithm. In Figure 1.45 we provide the complementary CDF of the difference between the delay for an optimal algorithm applied to a file of size 200 pieces and the delay associated with our algorithm for the same random mobile user path. We did 1000 trials, and it can be seen that the heuristic algorithm fails by more than 3% only 16% of the time and by more than 10% only 0.4% of the time.

The excellent performance of the algorithm is in part due to the fact that we are transmitting in all infostations that will possibly be in the path. In the single user case this is not a problem since all the links can be used for one user. If we increase the number of users it may not be possible to coordinate all transmissions to all users if the boundaries overlap.

Therefore, to evaluate the algorithm efficiency we change the number of infostations to where the system transmits to. We consider the case

Infostations: New Perspectives On Wireless Data Networks

57

where the system transmits to C infostations to the right and to the left total number of infostations). Figure 1.46 shows the total number of file pieces transmitted before completion of file delivery, as a function of the file size, for different values of C. The total transmitted minus the file size represents the wastage of the system. Figure 1.47 shows the average delivery delay. As can be seen, reducing the value of C to 3, for example, increases considerably the efficiency and does not affect as much the delay performance. That shows that it may be possible to accommodate more users without affecting very much the system performance. of the mobile (

5.

CONCLUSIONS AND WORK IN PROGRESS

In this work we considered the problem of delivering a file in system which features high rate discontinuous coverage. The collection of access points and the algorithms which support file delivery we call an

58

NEXT GENERATION WIRELESS NETWORKS

Infostation System. Assuming that there are several infostations in the mobile path, the file is divided into segments and different segments can be transmitted to different infostations along the path. The constant velocity case was studied and the most interesting result is that higher mobile velocity reduces delay if different data can be delivered to multiple infostations in parallel over the fixed network. Then a random walk mobility model was introduced with constant velocity but with randomly chosen travel direction at each step. Results for bounds on the average number of file segments picked after a given number of steps for a general infostations topology were obtained. It was shown

that the fewer infostations are revisited in a path, the larger the average number of segments obtained at each step. An algorithm for the one-dimensional case was proposed. The algorithm simply tries to avoid repetitions of segments in places where the mobile is likely to visit along a path. The algorithm is not optimum in the sense that it does not achieve the absolute bound associated with foreknowledge of the user path, and it fails when it cannot avoid the

Infostations: New Perspectives On Wireless Data Networks

59

repetitions. However, it is an open question whether this algorithm is indeed optimal among all algorithms which do not know the user path beforehand. Regardless, simulation results showed that its delay performance is extremely close to the known-path optimum. Currently the authors are working on the scheduling problem for the multiple user case. This problem is much more complex than the single user case since each infostation has to decide not only which segments

to transmit but also which user to serve. Some other suggestions for future work are: We have assumed a constant velocity between infostations.

It

would be interesting to consider the situation where the time spent traveling between two infostations is a random variable. Yet another important factor is that in our analysis we assumed a grid scenario. When considering discontinuous coverage area, though, the system can be modeled as a complete graph, where every node represents the infostations and the weight of every edge is the transition probability between the two infostations.

60

NEXT GENERATION WIRELESS NETWORKS

We assumed that the bottleneck of the system was the wired backbone and that the radio was always capable of transmitting all the segments to the mobile during the time the mobile is in the coverage area. It is necessary to consider imperfections over the wireless channel, such as errors and retransmissions, which may cause some file segments to be probabilistically missed at any given infostation.

Infostations: New Perspectives On Wireless Data Networks

61

62

NEXT GENERATION WIRELESS NETWORKS

References

[1] R.D. Yates and N.B. Mandayam. Issues in wireless data. In IEEE Signal Processing Magazine, May 2000. To appear. [2] R.S. Cheng and S. Verdu. Gaussian Multicast Channels with ISI:

Capacity Region and Multiuser Water-Filling. IEEE Transactions on Information Theory, 39(3), May 1993. [3] D.J. Goodman, J. Borras, N.B. Mandayam, and R.Y. Yates. INFOSTATIONS : A New System Model for Data and Messaging Services. In Proceedings of IEEE VTC'97, volume 2, pages 969-973,

May 1997, Phoenix, AZ. [4] J. Borras. Capacity of an Infostation System. PhD thesis, Ruthers University, January 2000. [5] A. Goldsmith and P. Varaiya. Capacity of fading channels with channel

side information. IEEE Trans. Inform. Theory, pages 1218-1230, Oct 1997.

[6] Apple, 1999. Apple Computer Inc., URL=http://www.apple.com/airport

[7] P.H. Lewis. Not born to be wired. The New York Times, Circuits Section, November 25, 1999. [8] J. Borras and R.D. Yates. Infostations overlays in cellular systems. In Proceedings of the Wireless Communications and Networking Conference, WCNC, Volume 1, pages 495-499, 1999.

[9] R.H. Frenkiel and T. Imelinski. Infostations: The joy of "manytime, many-where" communications. Technical Report TR119, WINLAB, Rutgers, The State University of New Jersey, April 1996.

Infostations: New Perspectives On Wireless Data Networks

63

[10] G. Wu, C.-W. Chu, K. Wine, J. Evans, and R. Frenkiel. Winmac: A novel transmission protocol for infostations. Vehicular Technology Conference, 1999. [11] H.Mao, G. Wu, C.-W.Chu, J. Evans, and M. Carggiano. Performance evaluation of radio link protocol for infostations. Vehicular Technology Conference, 1999. [12] J. Irvine, D. Pesh, D. Robertson, and D. Girma. Efficient umts data service provision using infostations. Vehicular Technology

Conference, 3:2119-2123, 1998. [13] J.G. Evans. A low cost asymmetric radio for infostations. Technical Report TR-130, WINLAB, Rutgers, The State University of New Jersey, September 1996. [14] T. Ye, H.-A. Jacobsen, and R. Katz. Mobile awarness in a wide area wireless network of info-stations. ACM Mobicom, pages 109-102, 1998. Dallas. [15] J. Irvine and D. Pesh. Potential of dect terminal technology for providing low-cost internet access through infostations. In IEE Colloquium on UMTS Terminal and Software Radio, pages 12/1-6, 1999. [16] A.L. Iacono and C. Rose. Minimizing file delivery delay in an infostations system. Technical Report TR-167, WINLAB, Rutgers, The State University of New Jersey , August 1998.

[17] A.L. Iacono. File Delivery Delay in and Infostations System. PhD thesis, Rutgers, The State University of New Jersey, June 2000 [18] A.L. Iacono and C. Rose. Bounds on File delivery delay in an

information system. In Proceedings of the IEEE Technology Conference, 2000. To appear.

Vehicular

[19] R.H. Frenkiel, B.R. Badrinath, J. Borras, and R.D. Yates. The infostations challenge: Balancing cost and ubiquity in delivering wireless data. Submitted to IEEE Personal Communications, 1999.

[20] W. Feller. An Introduction to Probability Theory and Its Applications, Volume I, Chapters IV through XIV. Wiley, third edition, 1968.

This page intentionally left blank.

Chapter 2 WIRELESS BROADBAND MULTIMEDIA AND IP APPLICATIONS VIA MOBILE ATM SATELLITES Abbas Jamalipour University of Sydney, Australia

Abstract

ATM is the promising technology for supporting high-speed data transfer potentially suitable for all varieties of private and public telecommunications networks. IP, on the other hand, is the fast-growing internet layer protocol that is potentially applicable over any data link layer. New IP-based multimedia applications require much higher bandwidth compared to the traditional applications run over the Internet which ignited the usage of the ATM in IP networks. With the revolutionary development in wireless cellular network in recent years and the requirements of broadband data applications over the

wireless channel, ATM and IP networks find their way of contribution in this underlying network. Mobility in wireless environment could however take its ultimate freedom when an integrated cellular-satellite supports the physical layer of the network. In order to provide a global mobility for the future multimedia personal terminals, thus, there is a requirement of integration of all these telecommunications technologies. Wireless ATM came to integrate the cell-switched ATM facilities in wireless environment and mobile IP has a similar goal for IP networks. IP over ATM also proposed to merge the two

leading technologies of IP and ATM into a fast and efficient way of multimedia data transmission. Broadband ATM satellite systems also have been proposed in order to make the satellite channel a high-speed link for future networks. In this chapter, we will explain all these technologies and their mutual integration and then look into the issues of mobile satellites,

ATM, and IP in a novel way in order to introduce the integration of the three technologies for future high-speed, global mobility-supporting, Internetcompatible wireless communication networks. We will discuss the applications and their traffic and quality of service requirements. These are crucial issues that need careful considerations for future multimedia applications over the Internet.

Keywords:

mobile satellite networks, cellular systems, wireless ATM, IP networks,

routing, teletraffic, quality of service, mobility management.

66

NEXT GENERATION WIRELESS NETWORKS

1.

INTRODUCTION

The idea of establishing personal telecommunication services via satellites on non-geostationary constellations for commercial purposes was first proposed in the early 90’s [1-8]. The proposal suggested that with satellites on low earth orbit (LEO) or medium earth orbit (MEO), it is possible to get rid of the highly restrictive long propagation delay and power loss characteristics of the traditional geostationary earth orbit (GEO) satellites. Long propagation delay has always been a strict parameter in establishing long-distance real-time communications such as voice and video telephony via satellites. Long propagation loss, on the other hand, has always put a lower bound on the size of mobile terminals directly connecting to satellites. This is mainly because of the requirement of large battery capacity for transmitting signal on the uplinks. By having satellites on orbits much lower than the geostationary orbit, it is now possible to reduce the

transmission delay and the power of the transmitters so that satellite handheld terminals could become a reality. These small satellite mobile phones also could provide users to have a unique and international network access identification number (NAIN) regardless of their location on the globe and the availability of the terrestrial telecommunications infrastructures. These characteristics were so important and attractive for modern telecommunications era that several satellite systems of this type were proposed one after the other in a short period of time [1, 3, 9]. Although the majority of these systems have been proposed by the US companies, they were highly supported internationally soon after so that the first system of this type started its service in the late 1998. An architectural example of the future mobile satellite systems for providing personal communications is shown in Fig. 1 [8]. Mobile satellite systems for commercial purposes were developed in parallel with the development of the second generation of the terrestrial cellular systems. Both systems look somehow to the same goal; that is achieving the issue of terminal mobility in telecommunications services. Some of the second generation terrestrial cellular systems such as GSM (Global System for Mobile communications), however, went further to provide additional personal mobility. The differentiation between these two comes from the way the moving object is defined. In the first proposal of mobile satellite systems for commercial applications, the main purpose was to provide basic telecommunication services1 (which were the dominant services at that time) such as voice, telemessage, and paging regardless of the location of the user, specifically in remote areas. The user in such a system can buy a specific terminal and subscribe to specific service(s) 1

For this reason, we may call this generation of mobile satellites as narrowband systems.

Wireless Broadband Multimedia and IP Applications

67

available within that terminal and the subscribed network. In order to subscribe to other network services however, the user needs to buy a different terminal compatible with the new services. In GSM system on the other hand, the mobility is given to a user regardless of his terminal, and the user is free to purchase and use any GSM-compatible terminals and subscribe to new services after inserting his personalised SIM (subscriber identity module) card in the new terminal. In both systems, however, the main idea of the mobility, that is, the ability of accessing telecommunication services from different locations by a terminal and the capacity of the network to identify and locate the terminal are kept.

Another difference in these two parallel developing mobile systems is in the range of mobility. Mobile satellite systems provide mobility in a much broader concept compared to the terrestrial systems. For example, if we consider the mobility in the coverage area of a single base station (BS), it would be in the order of a few kilometres in radius for a cellular system and several hundreds to a few thousands of kilometres for a LEO satellite (based on the altitude of the satellite). Erection of a BS tower in a terrestrial system will also be limited to areas where the network service provider (NSP) expects to have some manhood population, such as cities, towns, and major roads. This limitation is completely removed in the case of a mobile satellite which will cover anywhere on the globe including areas with no population. Therefore, the total coverage of the satellite systems (which is based on geographical coverage and not on population coverage as in terrestrial

68

NEXT GENERA T1ON WIRELESS NETWORKS

cellular system) could be global. In this sense, we may consider the relation of satellite mobile systems and different terrestrial wireless systems in a hierarchical order, as shown in Fig. 2.

Mobile object also needs to be defined clearly when comparing terrestrial cellular systems and mobile satellite systems. The mobile object in a terrestrial system is the subscriber terminal, usually called a mobile station (MS), with a linear speed between zero and a few hundred km/h. In a mobile satellite system, the moving object (or the mobile) is the satellite which has a much higher speed; for example, in a LEO satellite system with a satellite altitude of 1,500 km, the speed of the mobile comes to around 7.1 km/s or 25,200 km/h! The changes in mobility characteristics, both the moving object and speed, make the mobility management issues in mobile satellites more complicated when compared to that in terrestrial mobile systems. Mobile satellite systems have a unique ability to establish a mobile telecommunications network with or without their terrestrial counterpart. In the regions with no terrestrial wireless infrastructure, because of either economical or technical reasons, mobile satellites can provide almost full range of telecommunications services. In the regions with developed wireless facilities, such as capital cities, the satellite can complement the service or assist the terrestrial network in hotspot teletraffic handling.

1.1

Mobile satellites and cellular networks

As discussed above, the main reason for the success of the mobile satellite system proposals was their ability to provide a ubiquitous means of telecommunications. This ability has shown its importance in comparison

Wireless Broadband Multimedia and IP Applications

69

with GEO satellite systems because of the lower propagation delay and loss accessible in lower orbit constellations and also service to the polar regions using inclination angles close to 90°. This latter characteristic of mobile satellites (which is not possible in GEO constellation), secures a onehundred percent global coverage possibility in the telecommunication system. The idea was strong enough to support launching a very expensive infrastructure, both the initial and the consequent running and maintenance costs, to the space. However, after the development of the second generation of terrestrial cellular systems in which at least a majority of countries use the same standard, such as GSM in European and Asian countries (except Japan), roaming has put the usefulness of mobile satellite systems under a big question. Roaming is an internetwork service in which a user or a terminal who is subscribed to a particular network, can ask to use temporarily a different network with the same standard which is not his home network (HN). The second network, which we may call it a foreign network (FN), might have the similar regional coverage as the HN or a completely different coverage. An example for the former roaming between networks could happen when the subscriber requires a network service which is not available in his HN but can be supplied (maybe with a charge) from a FN in the same region. For the latter roaming, a good example would be the case when a cellular subscriber travels abroad and wants to use his phone during his stay in the foreign country. This latter roaming clashes with the idea of the single global number merit of the mobile satellite systems. Though the cellular phone user still cannot use his cellular phone on the way to the other country and even in the country of FN without a prior arrangement, the advantage of having a satellite phone for ordinary people who only travel to major cities of countries and not “deserts” ceases significantly. The issue becomes even more apparent when we consider the fast growth of popularity and simultaneously decrease in price of cellular services in all parts of the world and even in developing countries where the satellite phones had targeted telecommunications services to those areas. As we approach the third generation wireless mobile systems and the IMT-2000 (International Mobile Telecommunications in the year 2000) [10], in which the internetwork connectivity is even considered between different standards, the advantages of the mobile satellite systems to terrestrial cellular networks are losing their importance gradually.

1.2

Future position of mobile satellites networks

Network service providers of the mobile satellite systems can still declare that there is no terrestrial wireless system which can provide personal

70

NEXT GENERATION WIRELESS NETWORKS

telecommunication access to all parts of the globe including remote areas and polar regions. Also, there is no other wireless network infrastructure (or even fixed networks) which could be reliable in the case of major natural disasters, whereas the mobile satellite systems have this ability to configure a complete network-in-the-space through satellites which will be independent of any land system, and hence, reliable in the case of any type of disaster on the earth. In addition, mobile satellite networks will provide their subscribers a unique NAIN which they can use at any time without a pre-arrangement before each travel, as in GSM networks. In addition to the basic telecommunications services, these satellite-based networks can provide other services such as vehicle navigation and GPS (Global Positioning System) on a personal basis. But the question that remains is that whether these services are sufficient to promote the satellite personal communication networks so that we can see

a rapid increase in number of subscribers to these systems as in the case of terrestrial cellular systems. A quick answer would be “no” as it is experienced in the recent financial failure of the first LEO satellite system. The above mentioned services and advantages could be attractive for corporate and governmental subscribers but not for ordinary users as the costs of satellite handset phones and subscription and call tariffs are too high and there is no optimistic expectation of significant reduction in the near future. In order to achieve the goal in number of subscribers, the NSP of the mobile satellite systems should focus on commercial applications that are attractive to ordinary people. These applications include broadband multimedia and especially Internet applications with lower costs that could compensate other expensive applications. The satellite NSPs have no choice other than to compete the terrestrial cellular systems with their additional services and to integrate with them whenever this competition is not possible in order to provide compatible service charges. In order to achieve this goal, the mobile satellite systems have to modify and adapt base on the new multimedia applications. In this chapter, we will discuss some of these issues related to the usage of the asynchronous transfer mode (ATM) to achieve higher data rates required in broadband networks and the Internet protocol (IP) applications. Such new mobile satellite systems, thus, will be referred to as broadband satellite systems.

1.3

Outline of the chapter

In the following section, we will review the characteristics of the mobile satellite networks with emphasis on LEO constellations. In Section 3, we will explain the ATM network originally developed for wired networks as the most significant contribution to B-ISDN (broadband integrated services

Wireless Broadband Multimedia and IP Applications

71

digital network) and how it has been involved in wireless environment, namely the wireless ATM. Section 4 gives an overview to IP networks and how they also came into the wireless world after the invention of mobile IP (MIP) in l996. In Section 5, we will discuss specific issues related on the way of integration of ATM and IP networks with wireless and particularly with the mobile satellite systems. The most important issues necessary to be considered are the quality of service (QoS) and traffic management. These issues are important in the sense that if considered carefully and then sophisticated techniques are designed and implemented, it would be possible to provide more and better services to users and hence achieve higher number of satellite mobile users. The quality of service has been vastly considered for wired network but needs to be redefined when mobile and wireless channels are being involved. Different types of traffic and their management techniques are also required when considering multimedia and broadband applications over the wireless link. After exploring these issues, we will introduce perspectives and applications of an integrated wireless IPATM network via mobile satellites. Finally, we will conclude our results and discussions in Section 6.

2.

MOBILE SATELLITE NETWORKS

Mobile satellite networks refer to systems in which the telecommunications satellites are on orbits other than the geostationary orbit. According the Kepler’s third law, the geostationary orbit is a unique equatorial orbit at a distance around 35,800 km from the earth surface [8]. A satellite on the geostationary orbit can cover almost one-third of the earth, and hence, three satellites would be sufficient to cover almost all part of the globe. This coverage excludes polar regions and other high latitudinal areas. The reason is simple if considering spherical shape of the globe and the position of satellite over the equator. Since the satellites are stationary in relation to the movement of the earth, antenna tracking and control would be minimal and the satellite gateways to the terrestrial public switching telephone networks (PSTNs) can always be faced to satellites for maximum signal reception and transmission. This type of satellites, then, can be easily used for long-distance telecommunications and broadcasting purposes. Because the length of the satellite transmission link is independent of the actual land distance of any given pair of the hosts on the earth, the longdistance communications cost will only depend on whether or not a satellite link is used.

72

NEXT GENERATION WIRELESS NETWORKS

GEO satellite systems were successful in providing commercial services, both in telecommunications and broadcasting, since the establishment of the first system, the INTELSAT, in 1965. The key characteristic of the GEO satellite systems was that they could be considered as a part of the fixed public switching network. In 1982, INMARSAT, another key-pioneered in satellite systems especially for mobile purposes, introduced its mobile satellite services, or MSS, using GEO satellites in order to provide telecommunications services to ships and other large mobile vehicles. This could be considered as the starting point of mobile communications via satellites. However, there was always the problem of the round-trip distance between the earth and a GEO satellite which makes it impractical to have small-size terminals other than those mounted on vehicles. This restrictive issue has become more visible when the people started to think about communications based on personal perspectives, or the personal communications services (PCS). It was clear that with GEO satellites it is difficult, if it not impossible, to provide personal communications with small handheld terminals and phones. Requirements of lower propagation delay and propagation loss together with the coverage of high latitude regions for personal communication services have started a vast research on employment of satellites on lower orbits, which in nature will have non-geostationary characteristics. Due to the existence of the two Van Alien radiation belts, these mobile satellites were categorised into low earth orbit with a altitude of 500-2000 km and medium earth orbit at around 10,000 km height. Generally, the lower the orbit the lower the propagation delay and loss and the higher the number of satellites (and the orbital planes) to cover the entire globe is resulted. Figures 3 and 4 show the relationship between the altitude of satellites and the number of satellites and the number of orbits, respectively [8]. Besides, the figures spot the actual constellation of some PCS non-geostationary satellite systems.

Wireless Broadband Multimedia and IP Applications

73

74

NEXT GENERATION WIRELESS NETWORKS

As discussed in the previous section, the idea behind these mobile satellite system which could provide a single and worldwide access number was so attractive that in a short period of time many of these systems have

been proposed and found multi-national support [3]. Table 1 summarises some of these PCS-based (narrowband) mobile satellite systems. In addition to these systems, there is another LEO proposal for global coverage, named Teledesic, as a multimedia satellite system using Ka-band. The system is planned to have data and Internet services at high data rates and in its original proposal 840 LEO satellites were considered. With a compromise on the data rate actually required for the subscribers and the integration with the Internet service providers (ISPs), Teledesic has now changed its design to a higher orbit height at 1,400 km which reduces the total number of satellites into 288 and may change further. Teledesic will use 1-Gbps links and 13.3Gbps capacity satellites which state the potential applications of the system to be broadband multimedia. For this reason, we may put the newly designed

Teledesic as a broadband satellite system, why it is missed from Table 1.

Among the systems shown in Table 1, the Iridium [9], the first completed

LEO satellite PCS system, has a unique design to achieve essential coverage with minimal requirements of land-based gateways that connect to the PSTN. This is achieved by employing links between satellites, or intersatellite-links (ISLs) working at 23 GHz, which enable the system to

Wireless Broadband Multimedia and IP Applications

75

route the traffic from one satellite to another, forming a network in the space. A general overview of the Iridium system is shown in Fig. 5.

Each Iridium satellite has powerful on-board processing and routing facilities. Traffic arrived in a TDMA (time division multiple access)

timeslot, will be processed by the satellite and the routing decision will be made. The next destination could be a ground gateway station via 20-GHz links or one of the four nearest satellites via ISLs. This type of user-satellitegateway connectivity is shown in Fig. 6. The Iridium system employs

circular polar orbits (86.5° inclination) which guarantee the service coverage to high latitude regions. The global coverage of the Iridium is one

of the main characteristics that distinguish this system from other mobile satellite proposals. The footprint of each Iridium satellite is divided into 48 cells via three L-band antennas forming a total of 3,168 cells on the earth surface-A cellular-type satellite system. From those cells only 2,150 cells would be enough for a global coverage, but with this plenty of cells, it is possible for any given user to be in two or more cells simultaneously at most of the times, providing a highly reliable communication.

76

NEXT GENERATION WIRELESS NETWORKS

The next Big-LEO satellite system to be in service soon is the Globalstar. This system does not claim offering a global coverage; instead it will provide coverage to its partners in different countries with sufficient population. This fact, together with higher altitude of the satellites, results in a less number of satellites than the Iridium system. Since the satellite orbits have a 52° inclination, little or no coverage is provided beyond latitude. At most of the times, two or more Globalstar satellites will be visible from the designated areas on the earth. Another difference between the Iridium and the Globalstar is that the latter does not employ ISLs, and as a result, a subscriber can access to the system on a bent-pipe fashion through a gateway station, as shown in Fig. 7. For a typical service area of about 1,600 km around a gateway station, global coverage requires more than 200 earth stations which is not planned in the system. Therefore, Globalstar will likely

serve national roamers in general. A satellite that is working as a repeater (e.g., the one used in bent-pipe scenario), is sometimes referred to as a transparent satellite.

Wireless Broadband Multimedia and IP Applications

77

The above discussion and explanation on mobile satellite network proposals should make it clear that these systems will have a significant, if not dominant, role in the next generation wireless communications. The recent financial failure of the Iridium however, does not change this role. On the contrary, it states the fact that the future trend in wireless communications is the Internet and broadband services and any system optimised for voice-only communications subjects to failure, regardless whether it is terrestrial or satellite. In the following sections, we will explore the ATM and IP networks and the potential integrity of the mobile satellites with these networks. This will be the most important issue for the mobile satellite systems in order to compete or complement the next generation terrestrial cellular networks.

3.

WIRELESS ATM NETWORKS

In this section, we will briefly explain the concept of ATM-based networks and how asynchronous mode of transfer provides extremely high data rates in digital communication networks. The ATM switching is the promising backbone technology for any data communication network, including telephony systems and the Internet. We will then develop the new topic of wireless ATM and discuss the new elements added to the traditional ATM protocol stack. The wireless ATM will then be developed in applications using mobile satellite networks in order to let those satellites be practicable for the transmission of multimedia and broadband traffic.

78

NEXT GENERATION WIRELESS NETWORKS

3.1

ATM Networks

With the introduction of modern digital and high-speed telecommunications with relatively low error rates, the requirements of long overheads on the packets of the traditional packet switching networks (PSNs) became unnecessary. Since those overheads contain no user information, reduction in the amount of overhead bits could result in more efficient utilisation of the channel capacity and higher data rates than what can be achieved in traditional PSNs. Frame relay networks make use of this fact to increase the data rate from 64 kbps of the PSN up to 2 Mbps. ATM networks, on the other hand, reduce the overheads further by employing fixed-size packets, called cells, and increase the data rate to 10s and 100s of Mbps. As an analogy to frame relay, the ATM service sometimes is referred to as cell relay. ATM has the most significant contribution in standardisation of B-ISDN [11-12]. In ATM, user information is split into 53-byte fixed-sized cells, as

shown in Fig. 8, and then switched using fast hardware-based cell switching. Cell header, a 5-byte label, carries the minimum of overhead to support multiplexing and switching of the ATM cells. ATM leaves most of the error detection and error correction and also out-of-sequence cell detection tasks to the higher layers of the network protocol stack, above the ATM layer and the ATM adaptation layer (AAL). Asynchronous feature of the ATM may seem conflicting to the periodic nature of the existing traffic from analogue

sources, such as voice or video. However, the apparent periodicity is a property of the channel coding process and not of the information sources themselves. With the powerful source coding mechanisms available now, it is possible to exploit the ability of ATM to absorb the essential burstiness that characterises the analogue sources. ATM has the ability to multiplex and switch data from various sources with varying rates and information statistics, and thus, is the most promising transfer mode for multimedia data whether originating in B-ISDN or the Internet and intarnet segments.

In ATM, logical connections are referred to as virtual channel connections (VCCs). A VCC is the basic unit of switching in B-ISDN and is set up between end user pairs through the network. A variable-rate, fullduplex flow of ATM cells is exchanged over the connections. These connections are also used for control signalling between user and the network and for network management and routing between one network and

Wireless Broadband Multimedia and IP Applications

79

another. All VCCs with the same endpoints are bundled in a virtual path connection (VPC) and switched along the same route. By grouping connections sharing common paths through the network into a single unit, it is possible to control the cost of the high-speed networks significantly. Relation between the above connections is shown in Fig. 9. Virtual path level and virtual channel level form the two sublayers of the ATM layer.

The cell header consists of 5 bytes. The format of the ATM cell header for the user-network interface (UN1) is shown in Fig. 10. For the networknetwork interface (NNI), there is no generic flow control (GFC) field and the virtual path identifier (VPI) field fills the whole first byte of the header. An n-bit label will support separate channels in the aggregate cell stream and as we will see in Section 3.3, it would be sufficient to support ISL routing in mobile ATM satellite systems. Resilience in the presence of errors is achieved by means of the header error check (HEC) mechanism. HEC is also used as a mechanism to control out-of-sequence cell arrival errors in ATM networks.

Payload type identifier (PTI), a 3-bit field, distinguishes particular classes of information flow and a single-bit cell loss priority (CLP) signals the cell to be discarded in the case of congestion in the network, similar to the technique used in frame relay networks. The GFC field is used to control the

80

NEXT GENERATION WIRELESS NETWORKS

traffic flow at the UNI in order to alleviate short-term overload conditions. This flow control is part of a controlled cell transfer (CCT) capability intended to meet the requirements of non-ATM local area networks (LANs) connected to a wide area ATM network. As a final comment to the ATM networks, it is worthwhile to state that the ATM is intended to transfer many different types of traffic simultaneously, including real-time flows such as voice, video, and bursty TCP (transmission control protocol) flows of the Internet. Traffic management techniques have been developed for ATM in order to handle these different types of traffic in an efficient manner based on the characteristics of the traffic flow and the requirements of the applications. All these issues are important in development and operation of a network, regardless of the medium whether it is wireless or wired, that is designed to handle multimedia traffic and broadband applications. These issues will be discussed in Section 5.

3.2

Extension of ATM into Wireless Environment

The ATM indeed can be considered as the main standard technology for broadband communications in wireline infrastructure. However, the recent development in wireless networks which supports the mobility of users and the strong requirement of supporting multimedia and specifically the Internet-based applications have opened new researches toward the integration of ATM with the wireless, namely the wireless ATM (WATM). ATM has the advantages of high efficiency and QoS support for users and if integrates with wireless networks, can provide mobility-supported highefficiency multimedia services. WATM can be considered as an extension of a wired backbone network with the flexibility of wireless access and mobility support [13-17]. The standardisation of the WATM has been started within the ATM Forum and ETSI (European Telecommunications Standards Institute) with contribution from other standardisation institute such as the IETF (Internet Engineering Task Force). The first draft specification related to the WATM has been released in December 1998 [13]. The WATM network has the traditional wired ATM network as its backbone. Therefore, we may consider a WATM network as a modified version of a wired ATM network with new wireless links and equipment. To include mobility, the traditional ATM switches are now complemented with mobility-supporting ATM switches connecting through enhanced public/private network node interface (PNNI). These new switches are connecting the wireless access points (APs) or BSs to the wired network. Mobile terminals (MTs) which can be for example laptop or palmtop

Wireless Broadband Multimedia and IP Applications

81

computers and mobile phones are connecting via new wireless UNI using radio channels. Connectivity between mobile and fixed hosts in the network thus will be through wireless UNI, mobility supporting ATM switches, traditional ATM switches, and traditional wired UNI. The BS in this configuration is sometimes named as the radio access unit (RAU) which contains all the link layer functional elements, including radio resource management and medium access control (MAC) functions, necessary to operate over a shared radio frequency (RF) medium. Figure 11 shows a generic configuration of such a WATM network. The protocol architecture of the WATM also needs modifications for mobility support [14]. Figure 12 shows such a modified protocol in which new mobility-related layers are shown in grey colour. As seen in the figure, both the user plane and control plane should be modified to support the mobility in the network. Much attention should be given to inclusion of proper MAC and wireless control protocols. More details on this architecture can be found in [13-14].

82

NEXT GENERATION WIRELESS NETWORKS

Wireless Broadband Multimedia and IP Applications

83

In the case of mobile networks, including WATM, the main mobility functions are location management and handover management. Since in these networks users have not committed to be in any specific location, there is the requirement of finding the real location of the MT from time-to-time and also specifying its nearest point of attachment to the wired network. This issue will be required during the process of routing the information packets from a MT to another MT or to a fixed host and vice versa. An efficient, reliable and quick handover technique is also necessary in order to maintain and reroute an ongoing session while the MT moves from the coverage area

of a BS to the next one. The location management and handover management together is usually referred to as mobility management in mobile networks.

3.3

Wireless ATM and Mobile Satellite Networks

In the discussion on WATM given in the previous section, we have not specified any type of physical channel used for transmitting the radio signals. Consequently, it is possible in general to consider any type of wireless media including satellite channels. Indeed, this is actually the idea behind the new generation of mobile satellite systems based on the ATM architecture as their mode of transfer [18-22]. The satellites in these systems

are usually multispot beam with onboard processing capabilities. These

84

NEXT GENERATION WIRELESS NETWORKS

systems will provide services at high data rates in the order of 2 Mbps or higher usually at Ka-band (30/20 up/down GHz) where the required bandwidth is available. Table 2 summarises some of satellite system proposals for broadband applications [19]. Among these systems, SkyBridge is the only one that will use Ku-band (14/11 up/down GHz). This band has already been used by the fixed satellite service (FSS).

Both the transparent satellite networks and the systems with onboard processing satellites can be integrated with ATM networks. In the former satellite ATM network, all protocol processing is performed on the ground at user terminal, gateway stations, and the network control centre (NCC), since there is no such onboard processing facilities in the satellite to perform the required processing at the ATM layer or above. These systems, however, can provide a quick deployment of ATM connectivity using exiting satellites, and hence, providing high-speed network access by user terminals and highspeed interconnection of remote ATM networks. We will not discuss this type of satellite ATM networks here, but a detailed discussion on the network architecture of these systems can be found in [18]. In the networks with onboard processing satellites, the control functions perform proportionally in the onboard ATM switch and the NCC on ground. The ATM interfaces between the payload switch and ground terminals can be either a UNI or a NNI [18]. If the satellite links are low speed, then they will be used to connect remote ATM hosts to a terrestrial network. Here, the interface between the ATM hosts and onboard switch is a UNI and the one between the onboard switch and the terrestrial ATM network is an NNI. With high-speed satellite links, onboard satellite will function as an ATM node and the interfaces will be NNI type. In a satellite system which employs ISLs, each satellite in the space network will act as a complete ATM node and the network provides both network access and network interconnectivity. Here the interfaces between satellites are NNI type. Figure 13 shows simple end-to-end communications between two satellite mobile terminals, and and between a mobile terminal and a fixed terminal connected to the PSTN, respectively. In this figure, it is assumed that the mobile terminals have direct access to LEO satellites

Wireless Broadband Multimedia and IP Applications

85

and that the satellites are networked together via ISLs. What this simple figure illustrates is that in a mobile satellite system with ISL networking, it is possible to achieve high data rate long-distance communications directly between terminals, both mobility supported and fixed ones. The directly connectable terminal in such a system contains a satellite adaptation unit which performs all the necessary user terminal protocol adaptations to the satellite protocol platform. This unit also includes all physical layer functionality such as channel coding, modulation/demodulation, the radio frequency, and the antenna parts. The satellite contains onboard signal regeneration, and performs multiplexing/demultiplexing, channel coding/decoding, and ATM switching. In the communication path between the mobile terminal and the fixed terminal, there is a gateway station which provides connectivity between the space and the ground segments. An interworking unit (IWU) included in the gateway station performs all necessary translations between the space (satellite) segment and other ground-based networks. The ground networks include PSTN, narrowband and broadband types of ISDN, frame relay networks, the Internet, and private and public ATM networks. A fixed user

terminal equipment could be belonged and connected to any of these networks. A network control centre might be required for an overall control of the satellite network resources and operations. This includes allocation of radio resources to the gateway stations, call routing and call management functions such as location update, handover, authentication, registration, deregistration, and billing. In a complete LEO satellite system employing ISLs, however, all these tasks could be distributed among the satellites, providing a more reliable control and then no NCC will be required. An illustrative architecture for a global ATM connectivity using mobile satellites is shown in Fig. 14.

86

NEXT GENERATION WIRELESS NETWORKS

Wireless Broadband Multimedia and IP Applications

87

Another viewpoint that relates the mobile satellite systems employing

ISLs with ATM networks is that we can consider each satellite as an ATM node, each ISL as a single VCC, and the routing path of a connection as a VPC of an ATM network. Therefore, we can build a complete high-speed ATM network in the space using the LEO satellites as its nodes and then apply similar ATM-based algorithms in that network. Specifically, applying the VPC and VCC concepts in a mobile satellite system will benefit us by utilising many advantages of the ATM routing and transmitting schemes. It

would also be much more convenient for mobile satellite networks to access fixed terrestrial ATM networks. As explained in Section 3.1, an ATM cell header in the NNI format contains 12 bits for VPI. This allows a maximum

of VPs for each single ISL step. This number is more than adequate for a mobile satellite system since the number of ISLs for each satellite nodes of the system is only between two and four (two links to satellites in the same orbital plane and two to satellite in the first neighbouring planes). Actually, one VPC has impact on only one ISL if the

node is at the terminal point and on two if the node is middle transient one. Thus the maximum number of simultaneous VPCs equals to the total number

of the all pair nodes, which can be defined as N(N-1)/2, where N is the total

88

NEXT GENERATION WIRELESS NETWORKS

number of the satellites in the system. More discussion on applying ATM routing concepts for mobile satellite systems can be found in [20-25]. As a conclusion, we can say that satellite ATM networks can be used to provide broadband access to remote areas and also to serve as an alternative

to the wired backbone networks. These satellite networks can effectively provide both real-time and non-real-time communication services in a global basis to remote areas and other regions where land-based facilities are not sufficient or not available.

4.

IP NETWORKS

In this section, we will overview the traditional IP networks in order to briefly explain the new concept of mobile IP networks. The mobile IP is one of solutions in providing macro-mobility in IP networks. This concept,

though originally developed based on terrestrial wireless infrastructure, could have no logical objection to be integrated in mobile satellite networks. This integration will be discussed shortly in Section 5.

4.1

Conventional IP Networks

The Internet can be defined as a connection of nodes on a global network use a DARPA-defined (Defence Research Projects Agency) Internet address. The protocol suite that consists of a large collection of protocols that have been issued as Internet standards, is referred to as TCP/IP (transmission control protocol/Internet protocol) [26]. TCP/IP was a result of protocol research and development conducted on the experimental packet-switched network ARPANET funded by DARPA. In contrast to the OSI (open system interconnection) reference model which was developed by the International Organisation for Standardisation (ISO), TCP/IP has no official protocol model, but can be organised into five layers of application, transport, Internet, network access, and physical. The network access layer can further be divided into two sublayers called logical link control (LLC) and medium access control (MAC). Information data processed in each application on a host computer should go through all these layers until it can be passed through the physical media on a LAN and through intermediate routing and

switching facilities on the wide area networks (WAN) and the Internet. Figure 15 illustrates the connections and the required protocol stack in a simple TCP/IP-based network.

Wireless Broadband Multimedia and IP Applications

89

90

NEXT GENERATION WIRELESS NETWORKS

The two main components of the Internet, which are shown in Fig. 15, are the hosts and the routers. Hosts include any type of computer such as PCs and workstations. Routers forward datagram packets between hosts and other routers when there is no same link (e.g., a bus) connecting them. A router operates at the network layer of the OSI model to route packets between potentially different networks. Another component that could be considered here is a bridge, which operates at data link layer and acts as a relay of frames between similar networks. In order the routers perform their task, they use special procedures called routing protocols. Routing tables are built using these procedures and then a router can select a path (hopefully the optimum one) for any given packet

from a source host to a destination host. In the case of many routers between a source and a destination, routing will be performed on a hop-by-hop basis, in which each router finds the next node (router) for sending a given packet u n t i l the packet is being reached at its requested destination.

The IP is the most widely used internetworking protocol at the Internet layer. An IP datagram includes a header and the payload. Payload of the IP packet contains all the higher layer headers such as TCP in addition to the application layer data. The header for the IPv4 (currently deployed version of IP) contains 20 bytes in addition to a variable size options field requested by the sending host, as shown in Fig. 16.

The version field shows the version of the protocol, which is 4 for the currently used protocol. IHL (Internet header length) shows the size of IP header. Type of service field specifies QoS parameters such as reliability, precedence, delay, and throughput. The maximum time that a datagram is allowed to remain in the Internet is specified in the “time of live” field. Header checksum is an error-detecting code for the header only and the protocol field indicates the next higher level protocol that is to receive the data field at the destination. The identification field is a sequence number to

identify a datagram uniquely together with the source address, destination address, and user protocol.

Wireless Broadband Multimedia and IP Applications

91

The most important parts of the header are the source address and the destination address. These are 32-bit IP addresses, as shown in Fig. 17, assigned to each network interface of a node. A node with multiple interfaces, such as routers, then has more than one IP address. Each IP address has a network-prefix portion and a host portion. A network-prefix is identical for all nodes attached to the same link whereas the host portion is unique for each node on the same link. In the next generation IP, or IPv6, address fields are extended into 128 bits which increases more number of hosts in the network. Moreover, in IPv6 options are placed in separate optional headers that are located between the IPv6 header and the transportlayer header. This will speed up router processing of datagrams. In addition, other enhancements such as address autoconfiguration, increased addressing flexibility for scalable multicast routing, and resource allocation that allows labelling of packets belong to a particular traffic flow for special handling, are included in this new version of IP.

The most important task to be performed by the IP layer is routing. Whenever a packet received by a node, a host or a router, for which the node is not its final destination (i.e., having different destination IP address as the receiving node), the node must find where the packet should be route in order to be closer to its final destination. Therefore, in the process of routing a packet, a forwarding decision must be made by each node. This decision can be made using an IP routing table, which is maintained in each node. Each row of the routing table usually has four components, namely, target, prefix-length, next-hop, and interface. Whenever a node has a packet to forward, it checks for matching between the packet’s IP destination address field and the left-most prefix-length bits of the target field within the rows of the table. If such a match is found, the packet will be forwarded to the node identified by the next-hop field via the link specified in the interface field in that row. In the case of more than one matching, the packet forwards to the one which has the largest prefix-length. This will ensure that the next node is the closest node to the final destination. An entry in the routing table might be a host-specific route, with the prefix-length of 32 which can match with only one IP destination address; a network-prefix route, with a prefix-length between 1 and 31 bits which match all destination IP addresses with the same network-prefix; or a default route, with a prefixlength of zero. This last route will match all IP addresses but will be used only when no other matching were found.

92

NEXT GENERATION WIRELESS NETWORKS

The routing tables might be created statically (manually) or dynamically. Usually, these routing tables are produced using one of common shortestpath or least-cost algorithms such as Dijkstra or Bellman-Ford algorithms [26], widely used in other packet-switched networks. Because the Internet routing is based upon the network-prefix portion of the packet destination address, it is greatly improves the scalability of the Internet.

4.2

Mobile IP Networks

Mobile IP (MIP) is an extension to the currently deployed (fixed) Internet protocol in order to provide wireless access to the Internet users [27-30]. MIP is described in a request for comments (RFC) published by IETF first in October 1996 [27]. The most important barrier in developing mobile internetworking is the way IP operates. Conventional IP supports interconnection of multiple networking technologies into a single, logical internetwork and is the most widely used internetworking protocol. An IP address is used to identify a host and contains information used to route the packets. Generally, in a mobile Internet the two lower layer protocol functionalities, i.e. physical and data link, are provided by cellular networks. However, the next higher layer protocols, that is network and transport layers, should be modified in order to enable them to route and deliver packets correctly in a mobile environment. As explained in Section 4.1, an IP address is assigned uniquely to each machine in the network and is used by the network layer to route the datagrams. The concept of network prefix as part of an IP address however, is contradictory with the idea of mobility. This is because of this fact that in the case of movement of a terminal in the network, it is not possible to maintain a single point of attachment for the terminal to the network; i.e. no logical network prefix would be available. Thus, any solution for supporting mobility in the Internet is constrained by the requirement of the existing IP function and networking applications. As the mobile user is roaming between foreign networks, it will acquire a new IP address causing the established connection of the node to be lost. MIP provides a means of delivering the packets addressed to the mobile node. By defining special entities, home agents (HAs) and foreign agents (FAs), a mobile node (MN) is able to cooperate in moving without changing

its IP address. Inversely, it provides a means for MIP to deliver packets addressed to a particular MN in the network. Furthermore, the solution can be appropriately expanded to accommodate an increasing population of mobile users (i.e., supporting the scalability). In MIP, each mobile node is given a virtual home network. This remains

unchanged, and is used to assign the mobile node a constant IP address in the

Wireless Broadband Multimedia and IP Applications

93

same manner that a standard IP address is given to a stationary host. On the home network, a location information database is maintained for each of its attached MNs (which are currently visiting other networks). The accuracy of this information become vital when routers are to deliver any MN addressed datagrams. The core operations involved in MIP include agent discovery, registration, and packets tunnelling. This is exactly what mobility management is defined to be; i.e. to detect MN’s change of location, register the new location with HA (either directly or via FA), and finally to perform handover as MN moves to a new network. Upon detecting a change in location, the roaming MN acquires a new IP address, a care-of address (CoA), either from the received foreign agent advertisement (FACoA), or from an external dynamic host configuration protocol (DHCP) server, a co-located CoA (CCoA). MH then notifies HA of the new location through the process of registration. Figure 18 gives a brief illustration to how Mobile IP works.

Data packets from a corresponding node (CN) are generally routed by default to the MN’s home address. HA attracts packets destined for those nodes that are away from their home network, and redelivers them according to the corresponding CoAs being registered by each roaming node. After the registration with the HA is completed, the mobility management protocols should secure a way for packets to be routed to the current point of attachment, namely the tunnelling. The method used to forward data to roaming MN is known as encapsulation. Though MIP

94

NEXT GENERATION WIRELESS NETWORKS

assumes an IP-within-IP encapsulation methodology, shown in Fig. 19, other encapsulation mechanisms are applicable upon agreement made between relevant networks.

In general, M1P provides a good framework for handling users’ mobility in a way that was never possible within the conventional IP networks. There are many benefits associating with this particular mobility management technique. Table 3 briefly summaries some of these characteristics.

In spite of the advantages of the MIP in providing a mobile computing environment, there are a few concerns about its efficiency. Basically, the inefficiencies in MIP can be classified into three main categories according to each step of the mobility management process, say location management, routing management, and handover management. Regarding the location management, a serious inefficiency is widely evident because a registration

Wireless Broadband Multimedia and IP Applications

95

process with HA is required at every handover when changing either the network or the link within the same network. This results in wasting resources that are associated with the frequent location updates arising from every single MN’s movement. For the routing management, one of the biggest concern in MIP is the inefficiency associated with the way packets are delivered to roaming MNs, namely the triangle routing; an asymmetric routing with respect to topology. Specific concerns in this aspect include packet losses during handovers, high data latency, and inefficient use of the network resources due to tunnelling. Route optimisation techniques are being developed to cope with this issue. The handover management also would be necessary to develop in order to control large number of handovers by MNs as the size of cells in cellular system becomes smaller. MIP which uses the terrestrial cellular infrastructure could be a good starting point for the implementation of IP services over mobile satellite links. The inefficiencies discussed above, however, should be carefully considered in long-delay satellite links.

5.

INTEGRATION OF WIRELESS ATM AND IP IN SATELLITE NETWORKS

The integration of IP in ATM networks requires considerations of both service and performance issues. This consideration becomes even more important when we apply the two protocols in a mobile and wireless environment. In principle, the quality of service is the major issue which is supported in ATM networks and the applicability of IP over any data link layer is the main characteristic of the IP networks. The integration of these two networks aims to take the advantages of both and to optimise the integrated network. Another important topic which requires more investigation in this integration, is the different types of traffic to be transmitted over the integrated network and the traffic management policies. Therefore, in this section we will first look over the issues of quality of service and traffic management and then discuss the perspectives and applications of the integration of IP and ATM in wireless and satellite environment.

5.1

Quality of Service Requirements

The commonly used metrics for QoS in the telecommunications networks include bandwidth, throughput, timeliness (including jitter), reliability, perceived quality, and cost [31-34]. The management of the system

96

NEXT GENERATION

WIRELESS NETWORKS

components becomes more complicated as we move from simple voice or data services into multimedia and broadband applications. In this sense, because of certain limitations in portable computers, such as the restrictions of battery life, screen size, and connection cost, management of delivering the required QoS in a mobile environment becomes even more complicated. Depends on the type of an application, we may define different QoS characteristics. For example, in transferring an image file, the picture quality and the response time could be considered as appropriate factors. In general, the main technology-based QoS parameters are [31]: Timeliness, including several parameters such as: delay (transmission time for a message) response time (time between the transmission of a request and the receiving a reply)

jitter (variation in delay time) Bandwidth, which may be defined at: system level data rate (required or available bandwidth in bit per second) application level data rate (application specific bandwidth in its unit per second) transaction rate (processing rate or requested rate of the operations) Reliability, which can be measured by: mean time to failure mean time to repair meantime between failures loss or corruption rate (e.g., because of network errors) From a user-level QoS requirements, the following categories might be considered:

Critically, i.e. priority among different flows in multimedia stream perceived QoS, which is based on the type of data transmission application can be defined by: picture detail (e.g. resolution) picture colour accuracy video rate (frame per second) video smoothness (frame rate jitter) audio quality (sampling rate) video/audio synchronisation Cost (a significant parameter considered by users) which can be either of the two:

Wireless Broadband Multimedia and IP Applications

97

per-use cost (connection establishment and/or resource access cost) per-unit cost (per second or per unit of data cost) Security, required in most probable applications, including; confidentiality integrity digital signatures authentication Certain controls and supervision, namely QoS management techniques, are required to attain and sustain the desired quality of service properties [31]. These techniques are required not only at the initiation of an interaction (namely, the static functions) but also during that interaction (namely, the dynamic functions). Definition of QoS requirements, negotiation, admission control, and resource reservation are some of the static functions, whereas measuring the QoS actually provided, policing, maintenance, renegotiation, adaptation, and synchronisation (e.g. combining speech and video streams with temporal QoS) are the examples of dynamic functions. In the case of ATM satellite networks with onboard processors in which multiple IP flows are aggregated onto a single VC, a QoS manager classifies the flows of IP traffics in order to utilise the bandwidth efficiently [35]. This QoS manager uses IP source and destination address pairs. The manager also can further classify the IP datagrams based on the type of service field (see Fig. 16) requested and available in the IP header. In a mobile environment, mobility results in significant changes in QoS and a mobile system has to be able to adapt such changes. For the first QoS metric, i.e. the bandwidth, we have to accept that for some time the wireless networks can provide only bandwidth in an order much lower than fixed networks. The freedom in mobility of terminals will also be limited by the coverage area of the wireless infrastructure that a user is subscribed. Obviously, here another issue of QoS, i.e. the cost, will arise. As we move to a larger coverage and higher mobility during connection, e.g. from wireless LAN into cellular phone networks and to satellite systems, higher costs may be required though they may not provide higher data rate supports proportionally2. Table 4 summarises the relationship between area of coverage and bandwidth for several common wireless networks. As it can be seen from this table, all these wireless networks provide much lower data rates than typical Ethernet LAN networks of 10 Mbps-1 Gbps.

2

Note that here we consider real terminal mobility and not nomadic systems which can provide acceptable data rates at relatively low cost by using dial-up connections.

98

NEXT GENERATION WIRELESS NETWORKS

Nevertheless, in a mobile environment with data traffic applications, QoS management requires much more sophisticated techniques than fixed networks, because: A short loss of communication during a handover, which is usually acceptable in voice-application system, is not desirable in data applications. New point of attachment after a handover requires to have similar facilities and resources as the old one, thus renegotiation procedures would be required. Blind spots where the signal is very weak, and hence, low quality, are unavoidable in mobile and wireless systems. Certain specifications of portable terminal such as laptop computers may also affect the end-user QoS requirements in mobile environment compared to fixed networks. These limitations include the battery limits, processing power with low power consumption, screen size and their screen resolution.

5.2

Traffic Considerations

As explained in Section 4, the main structure of an IP application is based on TCP and thus the performance of TCP is crucial in running IP applications efficiently. In principle, TCP should work anywhere regardless of underlying network architecture, however, it is optimised for operating in a wired network with relatively low bit error rates (BER), say in the order of or less [36]. Consequently, TCP assumes that the major cause of problems in packet handling in the network is the congestion. In the case a wireless link is used for transmission of packets, however, this assumption would be no longer valid as the main cause will change to the packet loss because of high BER of the wireless link. In the case a satellite link is used as the wireless channel, the situation becomes even worse. For GEO satellites the long delay and for LEO/MEO satellites the rapid delay variation causes the acknowledgement- and time-out-based TCP congestion control mechanism performs weakly. This in turn results in large number of retransmissions which degrades the performance of the TCP. Therefore, the

Wireless Broadband Multimedia and IP Applications

99

relation of bandwidth-delay product and round-trip delay variation to the performance of TCP requires development of new congestion control and traffic management mechanisms in the TCP layer [35-36]. One issue in integration of IP traffic into ATM mobile satellite is to accommodate multiple IP traffic onto a single VC. The primary reason for this to be important is that the IP traffic must be transmitted within the ATM cells and through ATM VCs and that the number of these VCs are limited because of the limitation of the earth stations and onboard satellites. The classification of large number of IP datagrams into limited number of available VCs is performed by a QoS manager, as discussed in previous section. ATM is intended to carry different types of traffic simultaneously including real-time flows such as voice and video streams and bursty TCP flows [11]. Therefore, the ATM Forum has defined real-time and non-realtime service categories to accommodate all applications that require either constant or variable bit rates. In general, real-time services concern about the amount of delay and the variability of delay (jitter). These applications typically involve a flow of information to a user that is intended to reproduce that flow at a source (e.g., voice or audio transmission). On the other hand, non-real-time services are intended for applications that have bursty traffic characteristics and do not have tight constraints on delay and delay variation (more flexibility for the network to handle traffic and to use statistical multiplexing). The real-time services of the ATM include constant bit rate (CBR), and real-time variable bit rate (rt-VBR). Non-real-time services also include nonreal-time VBR (nrt-VBR), unspecified bit rate (UBR), and available bit rate (ABR). Among these services, UBR is suitable for applications that can tolerate variable delays and some cell losses (such as TCP-based traffic). Thus, no initial commitment is made to a UBR source and no feedback concerning congestion is provided. This service is best suited for the IP applications in which a best-effort QoS (i.e., the primary service of IP) is sufficient. The ABR service has been defined to improve service provided to bursty sources. In this service, a peak cell rate (PCR) and a minimum cell rate (MCR) are specified and the network allocates at least MCR to an ABR source. The leftover capacity or unused capacity is shared fairly among all ABR and then UBR sources. A guaranteed frame rate (GFR) has recently been proposed by the ATM Forum which provides a minimum rate guarantee to VCs at the frame level and could enhance the UBR service [37]. Considering unavoidable delay and delay variation in mobile satellite networks, UBR and ABR seem to be the most practicable options for the implementation of TCP/IP over ATM satellites. In particular, with UBR routers connecting through satellite ATM network can make the use of GFR

100

NEXT GENERATION WIRELESS NETWORKS

service to establish VCs between one another. In the case of the ABR service, the network can maintain low cell loss ratio by changing the ACR through the usage of a rate-based closed-loop end-to-end feedback congestion control mechanism. In the case of satellite systems that suffer from long round-trip delay, the control loop can be segmented using virtual source and virtual destination concept which results in less buffer requirements. More discussions on the teletraffic issues and operation of TCP over wireless channel can be found in [38-40]. Nevertheless, new algorithms are being developed in order to evolve the best effort service of the Internet into a QoS-supported one. Among them, the RSVP (resource reservation protocol) is enabling reservation of resources within IP network [41]. This protocol provides a way for every sender to establish paths for identified IP flows. With such protocols, it would be possible to define guaranteed QoS services for the delivery of IP datagrams within a fixed delay and no loss.

5.3

Perspectives and Applications

ATM and IP networks have several common structural viewpoints so that the concept of “classical IP over ATM” has been ignited in the IETF working groups [42]. In particular, IP datagrams, IP addresses, IP routing, IP QoS, and IP multicast could be mapped onto the corresponding ATM cells, ATM addresses, ATM VC switching, ATM QoS, and ATM point-multipoint features [43]. Thus, in this model the IP layer is entirely mapped onto the ATM layer in order to use the general applicability of the IP over any data link layer. In spite of the disadvantage of having many task duplications in the two layers in this approach, this example shows that IP and ATM have sufficient potentiality for the integration. Such an integration, however, could provide new services for the IP networks other than its traditional best effort; i.e. the QoS-supported services. Nevertheless, some optimisation is required for an efficient integration of IP and ATM. Since the ATM is based on cell switching and not the conventional circuit switching, the network resources can be utilised optimally. The guaranteed-QoS, the variable-rate support, and low-cost ATM chips are also additional advantages of ATM in implementation of high-speed broadband wireless pipes within the base station and advanced mobile terminals. By the usage of wireless ATM technologies, including signalling, access control, and resource management, it is possible to achieve high data rate broadband personal communication services in the order of 2 to 10 Mbps or more. Transmission of a number of IP flows on individual VCs according to their source and destination addresses for a better QoS has opened lots of research activity in the area of IP over ATM networks (e.g., [44-46]).

Wireless Broadband Multimedia and IP Applications

101

According to the discussions given already on QoS and traffic requirements, broadband mobile satellites with ATM switching would be suitable for some applications but less appropriate for others [47]. Some of potential applications are shown in Fig. 20. Telnet, or remote computer access, which is categorised in interactive computing applications, is feasible in satellite systems on low earth orbits. The LEO satellite systems can provide a relatively prompt response to a telnet connection. Multicasting and broadcasting of large data files, as in the case of information dissemination and video broadcast, could be efficiently supported by the mobile satellite networks. The primary reason for this is the global coverage and star topology of the satellite networks. Video broadcasting is usually sensitive to delay variation but not to the delay itself. The reason is that for a QoS playback of video streams, it is necessary to have each frame being equally spaced. Multicasting of image and video files through group mailing list and email also could be feasible with the broadband satellite networks. Included in multicast applications is the transmission of geographical position information to be used in GPS and other navigation instruments. Net conferencing and video conferencing are also ideal point-to-point and multipoint applications of broadband satellites networks. The delay would be a problem in transmission of high-speed and high-quality video images but the LEO satellite link can be comparable with other long-distance communication media. Applications which are not delay sensitive are the most promising services of the satellite networks. This includes bulk transfer of data. In addition to the above applications, low bit rate voice and image transmissions, paging, short message services would be included in basic applications of the broadband satellites.

102

NEXT GENERATION WIRELESS NETWORKS

Wireless Broadband Multimedia and IP Applications

6.

103

CONCLUDING REMARKS

Next generation broadband satellite networks is being developed to carry bursty Internet and multimedia traffic in addition to the traditional circuitswitched traffic. These satellites provide direct network access for personal applications as well as interconnectivity to the terrestrial remote network segments. In a data transmission environment, the traditional circuit switching method would be insufficient, as it cannot utilise the link capacity efficiently. ATM, on the other hand, can provide high quality of service support at a high data rate and good channel utilisation. Moreover, because of the existence of the real time traffic such as voice and video transmission, satellites on non-geostationary orbits have found much attention in the development of broadband satellite networks. In this regard, the next generation of broadband satellite networks would have the concept of integration of mobile satellites and the ATM networks. With the exponential increase in the Internet and web-based applications in addition to the requirement of supporting mobility, wireless IP networks such as mobile IP and cellular IP, have been developed by the integration of cellular networks and IP networks. ATM could provide the high-data rate requirement of the multimedia applications and thus, many works have been done in integrating of the ATM and IP. In this chapter, we examined mobile satellite, ATM, and IP technologies as well as wireless ATM and wireless IP and their mutual integration for providing high-speed wireless multimedia services. In addition, we discussed the new concept of integration of the three technologies in order to provide global mobility to the future multimedia terminals. Different types of traffic to be handled through these networks and the quality of service requirements have been explained. The mutual integration and the new idea of integration of the three technologies can be considered as a hierarchical research activities, as shown in Fig. 21.

104

NEXT GENERATION WIRELESS NETWORKS

Wireless Broadband Multimedia and IP Applications

105

REFERENCES [1]

W. W. Wu, et al., “ Mobile satellite communications,” Proceedings of the IEEE, vol. 82, no. 9, pp. 1431-1448, September 1994.

[2]

R. L. Pickholtz, “Communications by means of low earth orbiting satellites,” 25th

General Assmebly of International Union Radio Science (URSI), Lille, France, 1996. J. V. Evans, “Personal satellite communications systems,” The Radio Science Bulletin, URSI, no. 290, pp. 8-15, September 1999. [4] F. Abrishamkar and Z. Siveski, “PCS global mobile satellites,” IEEE Communications Magazine, vol. 34, no. 9, pp. 132-136, September 1996. [5] M. Werner, et al., “Analysis of system parameters for LEO/ICO-satellite communication networks,” IEEE Jour. Selec. Areas Commun., vol. 13, no. 2, pp. 371[3]

[6]

381, February 1995. E. Del Re, “A coordinated European effort for the definition of a satellite integrated environment for future mobile communications,” IEEE Communications Magazine,

[8]

vol. 34, no. 2, pp. 98-104, February 1996. B. Miller, “Satellites free mobile phones,” IEEE Spectrum, vol. 35, no. 3, pp. 26-35, March 1998. A. Jamalipour, Low Earth Orbital Satellites for Personal Communication Networks,

[9]

Norwood, MA: Artech House, 1998. S. R. Pratt, et al., “ An operational performance overview of the IRIDIUM low earth

[7]

orbit satellite system,” IEEE Communications Surveys, Second Quarter 1999. [10] F. Adachi and M. Sawahashi, “Challenges in realizing the multimedia mobile

communications era: IMT-2000 and beyond,” Personal, Indoor and Mobile Radio Communications Conf. (PIMRC '99), Osaka, Japan, 1999. [11] W. Stallings, ISDN and broadband ISDN with frame relay and ATM, 4th ed., Upper Saddle River, NJ: Prentice Hall, 1999. [12] M. Sexton and A. Reid, Broadband networking-ATM, SDH and SONET, Norwood, MA: Artech House, 1997.

[13] R. R. Bhat, K. Rauhala, eds., “Draft baseline text for wireless ATM capability set 1 specifications,” BTD-WATM-01, ATM Forum, December 1998. [14] B. Kraimeche, “Wireless ATM: Current standards and issues,” IEEE Wireless Communications and Networking Conference (WCNC '99), New Orleans, 1999.

[15] C. K. Toh, et al., “Emerging and future research directions for mobile wireless ATM networks,” IEEE Wireless Communications and Networking Conference (WCNC '99), New Orleans, 1999. [16] H. Nakamura, et al., “ Applying ATM to mobile infrastructure networks,” IEEE Communications Magazine, vol. 36, no. 1, pp. 66-73, January 1998. [17] R. J. Sanchez, et al., “ Design and evaluation of an adaptive data link control protocol

for wireless ATM networks,” IEEE Global Telecommunications Conference (Globecom '98), pp. 2239-2244, Sydney, Australia, 1998.

[18] P. Chitre and F. Yegenoglu, “Next-generation satellite networks: Architectures and implementations,” IEEE Communications Magazine, vol. 37, no. 3, pp. 30-36, March

1999. [19] I. Mertzanis, et al., “Protocol architectures for satellite ATM broadband networks,” IEEE Communications Magazine, vol. 37, no. 3, pp. 46-54, March 1999. [20] M. Werner, et al., “ATM-based routing in LEO/MEO satellite networks with intersatellite links,” IEEE Jour. Select. Areas Commun., vol. 15, no. 1, pp. 69-82,

January 1997.

106

NEXT GENERATION WIRELESS NETWORKS

[21] M. Werner, “ATM concepts for satellite personal communication networks,” Proceedings European Conference on Networks and Optical Communications (NOC '96), pp. 247-254, Heidelberg, Germany, 1996. [22] S. Ray, “Network segment mobility in ATM networks,” IEEE Communications Magazine, vol. 37, no. 3, pp. 38-45, March 1999. [23] G. Dommety, M. Veeraraghavan, and M. Singhal, “A route optimization algorithm and its application to mobile location management in ATM networks,” IEEE Jour. Select. Areas Commun., vol. 16, no.6, pp. 890-908, August 1998. [24] H. Uzunalioglu, “Probabilistic routing protocol for low earth orbit satellite networks,” IEEE International Conference on Communications (ICC '98), pp. 89-93.

[25] J. Chen and A. Jamalipour, “An improved handoff scheme for ATM-based LEO satellite systems,” Proceedings of the 18th AIAA International Communication Satellite Systems Conference, Oakland, CA, April 2000. [26] W. Stallings, Data and Computer Communications, 6th ed., Upper Saddle River, NJ: Prentice Hall, 2000. [27] C. E. Perkins, “IP mobility support,” IETF RFC 2002, October 1996.

[28] J. D. Solomon, Mobile IP–The Internet unplugged, Upper Saddle River, NJ: Prentice Hall PTR, 1997.

[29] C. E. Perkins, Mobile IP–Design, principles and practice, Reading, MA: Addison Wesley Longman, 1998. [30] A. Seneviratne and B. Sarikaya, “Cellular networks and mobile Internet, ” Computer

Communications, vol. 21, Elsevier Publishers, pp. 1244-1255, 1998. [31] D. Chalmers and M. Sloman, “A survey of quality of service in mobile computing environments,” IEEE Communications Surveys, Second Quarter 1999.

[32] X. Xiao and L. M. Ni, “Internet QoS: A big picture,” IEEE Network, pp. 8-18, March/April 1999. [33] R. Guerin and V. Peris, “Quality-of-service in packet networks: basic mechanisms and directions,” Computer Networks, vol. 31, Elsevier Publishers, pp. 169-189, 1999.

[34] A. Iera, A. Molinaro, and S. Marano, “Adaptive QoS for multimedia applications in personal communication networks,” Personal, Indoor and Mobile Radio Communications Conf. (PIMRC '99), Osaka, Japan, 1999. [35] R. Goyal, et al., “Traffic management for TCP/IP over satellite ATM networks,” IEEE Communications Magazine, vol. 37, no. 3, pp. 56-61, March 1999. [36] P. Tran-Gia and K. Leibnitz, “Teletraffic models and planning in wireless IP networks,”

IEEE Wireless Communications and Networking Conference (WCNC '99), New Orleans, 1999. [37] I. Andrikopoulos, et al., “ Providing rate guarantees for Internet application traffic across ATM networks,” IEEE Communications Surveys, Third Quarter 1999.

[38] F. Anjum and L. Tassiulas, “An analytical model for the various TCP algorithms operating over a wireless channel,” IEEE Wireless Communications and Networking Conference (WCNC '99), New Orleans, 1999. [39] R. Prakash and M. Sahasrabudhe, “Modifications to TCP for improved performance and reliable end-to-end communications in wireless networks,” IEEE Wireless Communications and Networking Conference (WCNC '99), New Orleans, 1999.

[40] D. Grillo, et al., “Teletraffic engineering for mobile personal communications in ITU-T work: The need to match practice and theory,” IEEE Personal Communications, pp. 38-

58, December 1998. [41] L. Zhang, et al., “ RSVP: A new resource reservation protocol,” IEEE Network, vol. 7, no.5, September 1993. [42] M. Laubach, “Classical IP and ARP over ATM,” IETF RFC 1577, January 1994.

Wireless Broadband Multimedia and IP Applications

107

[43] E. Guarene, P. Fasano, and V. Vercellone, “IP and ATM integration perspectives,” IEEE Communications Magazine, vol. 36, no. 1, pp. 74-80, January 1998. [44] J. Hu, “Applying IP over wmATM technology to third-generation wireless communications,” IEEE Communications Magazine, vol. 37, no. 11, pp. 64-67,

November 1999. [45] J. Aracil, D. Morato, and M. Izal, “Analysis of Internet services in IP over ATM networks,” IEEE Communications Magazine, vol. 37, no. 12, pp. 92-97, December 1999. [46] M. A. Labrador and S. Banerjee, “Packet dropping policies for ATM and IP networks,” IEEE Communications Surveys, Third Quarter 1999. [47] D. P. Connors, B. Ryu, and S. Dao, “Modeling and simulation of broadband satellite networks-Part I: Medium access control for QoS provisioning,” IEEE Communications

Magazine, vol. 37, no. 3, pp. 72-79, March 1999.

108

NEXT GENERATION WIRELESS NETWORKS

ABOUT THE AUTHOR Abbas Jamalipour is a Senior Lecturer in the School of Electrical and Information Engineering at the University of Sydney, Australia, where he is responsible for teaching and research in data communication networks and satellite systems. He received his Ph.D. in Electrical Engineering from Nagoya University, Japan, in 1996. He was an Assistant Professor at Nagoya University before moving to Sydney. His current areas of research include data communication and ATM networks, mobile IP networks, mobile and satellite wireless communications, traffic and congestion control, switching systems, and switch design. He is the author of the first technical book on LEO satellites, entitled Low Earth Orbital Satellites for Personal Communication Networks published by Artech House, Norwood, MA, 1998. He has served as the Registration Chair at the 1998 IEEE Global

Telecommunications Conference (GLOBECOM ‘98) held in Sydney. He is a Senior Member of the IEEE and an organizing committee member of the joint IEEE NSW Communications and Signal Processing chapter. He is the recipient of a number of technology and paper awards and the author for many papers in IEEE and IEICE Transactions and Journals as well as in international conferences.

Chapter 3 INFOCITY: PROVIDING QOS TO MOBILE HOSTS Mobile Multimedia on the Wireless Internet PATRICIA MORREALE Stevens Institute of Technology, Hoboken, NJ, USA

Abstract:

Future wireless networks will be integrated with existing wired networks. Together, this environment will compose a multimedia network infrastructure, providing advanced data, voice, and video services, which is referred to here as “InfoCity”. In this chapter, several emerging technologies, which might be used to provide the mobile multimedia

services needed in the event of such a technology integration and convergence are presented. Careful consideration is given as to how these new technologies could best be used to offer a state-of-the-art, networked “InfoCity”, as a solution for next generation distributed multimedia applications. InfoCity, as presented here, is envisioned as a wired and wireless co-existence environment, with seamless service delivery of full multimedia applications, regardless of the user’s location and receiving device. Frame relay and ATM are presented as facilitating high-speed connections to a future broadband architecture. In order to support the diverse service needs of multimedia, Quality of Service (QoS) must be assured. Resource reservation protocol (RSVP) is considered as an example of the type of service-arbitration technique which could be used to provide users with such QoS assurance based on user need, rather than fair allocation. Finally, mobile IP is included as one approach to providing mobile host support in this new environment.

Keywords:

multimedia network infrastructure, frame relay, ATM, QoS, RSVP, mobile IP

110

NEXT GENERATION WIRELESS NETWORKS

1. INTRODUCTION

The computer market has been the compelling force behind Internet development and technological growth. The market focus has been to connect countless computers together in large business, government or university communities. The computer market will continue to grow in future decades due to expansion in new areas but growth will not be endlessly exponential. Saturation in the PC market, as demand moves towards integrated services, will result in this deceleration. New markets will emerge as mobile computing and networked entertainment becomes more and more ubiquitous. The possibility that every TV will become an Internet host is not far away. The device control market will play an important role in the future. The electronic network-control of everyday devices – such as lighting equipment, heating and cooling motors, home appliances, which are today controlled via analog switches consuming important amounts of electrical power – will bring enormous future opportunities. The potential of these markets is huge and requires simple, robust and easy to use solutions. In this context it is imperative to imagine “InfoCity” as a geographical location containing a state of the art multimedia network that facilitates the integration of new interactive applications as e-shopping and video on demand with classical data services as fax and email and TV. This InfoCity is approaching reality, as more and more residential users network their home environments. This complements the wiring of the office environments, which has taken place in previous years. The interconnection of these sites, both residential and industrial, either by wired or wireless means, would result in the InfoCity, a vision of the network infrastructure of the future. To make InfoCity a reality in the coming century, currently available and proposed technologies must be analyzed in order to design a cost-effective solution. Multiple WAN and LAN services should be managed using common software tools, in order to deliver bundled and premium services without compromising performance or scalability. The InfoCity architecture must be efficient for low bandwidth networks, such as wireless, while incorporating high-performance networks as ATM.

InfoCity: Providing QoS to Mobile Hosts

111

The Internet Engineering Task Force (IETF), ATM forum and other standards organizations have addressed all these issues in detail but technology standards no longer drive the data and telecommunications market. Customers do. Service providers are struggling to determine a suite of protocols that match the requirements of today’s applications and also meets the needs of new emerging markets. The new markets will create either a immense interoperable world wide information infrastructure, the InfoCity depicted here, based on open

112

NEXT GENERATION WIRELESS NETWORKS

protocols, or an interconnection of disjointed networks with protocols controlled by individual vendors. In this paper we will analyze first WAN technologies as Frame Relay and ATM, as they promise to provide high-speed connections in a future broadband architecture. This would be needed for InfoCity in order to provide a WAN infrastructure for communication. Speed alone won’t be sufficient in a future InfoCity infrastructure. It has become clear in the last decade that users should not be treated equally but according to their needs or willingness to pay for a specific service. Resource Reservation Protocol (RSVP) – a QoS protocol - is one example of a service arbitration technique which is representative of this “pay-as-yougo” need. Therefore, RSVP is also considered here. There is currently significant industry interest in providing wireless data services. In a global economy people seek to have Internet access and networking resources whenever and wherever they are. This can be easily achieved with laptops and pocket devices such as Windows CE, or Palm Pilot. Mobility improves the quality of people’s lives and gives them new business opportunities such as: on the move collaborative and communication tools, access to corporate databases on the field, and location-based services. In wireless networks mobile hosts should be able to enjoy interruptible network connectivity and different quality of services just like wired networks. To ensure the mobile hosts with interruptible network access mobile IP schemes were developed. Mobile IP is also considered here. Rather than presenting a specific implementation, this paper analyzes all the above protocols and discusses the merits of proposed modifications in order to offer a cost-effective, robust solution, such as that which might be used in the InfoCity of the future. 2. MULTIMEDIA APPLICATIONS Consider networking applications whose data contains continuously evolving content, such as audio and video content. These will be called “multimedia networking applications”. Multimedia networking applications are typically highly sensitive to delay; for a given multimedia network application, packets that incur more than an x second delay are useless, where x can range from a 100 milliseconds to five seconds. On the other hand, multimedia distributed applications are typically loss tolerant, as occasional loss only causes occasional glitches in the audio/video playback. Often these losses, which are local, not global, can be partially or fully concealed. Thus, in terms of service requirements, multimedia applications are diametrically opposed to fixed-content applications: multimedia

InfoCity: Providing QoS to Mobile Hosts

113

applications are delay sensitive and loss tolerant whereas the fixed-content applications are delay tolerant and loss insensitive. 3. WHERE ARE THE CHALLENGES?

Demand for increased bandwidth is coming from both the residential and business community. Gaming web sites and interactive multimedia eshopping are gaining rapid acceptance by consumers. The number of people accessing these sites and the volume and density of the offered applications

is expanding faster than ever. A new generation of high-performance low-cost PCs is coming out with free Internet connectivity as an initial inducement to try the hardware. The core Internet is changing to a high-speed backbone to reduce congestion. This change has been so significant, an “Internet 2” structure has been proposed and developed in the U.S. to, once again, develop research community isolation, from the more mundane and ordinary traffic on the existing Internet. This is discussed in detail in a following section. In an expanding global economy, as corporations became geographically disperse, users are increasingly less happy with WAN bottlenecks and they look for near-LAN speed for all their connection within the enterprise network.

The content of the information exchanged between major services of an enterprise is driving companies to consider high-speed solutions.

We see over the last years an increasing demand in Tl services for LAN interconnections and for high-speed Internet at 64kbps, 128 kbps or fractional Tl, as well as for DS-3 (44.636 Mbps). The majority of users need T-l and greater services for running multi-applications using a common bandwidth. ATM has been designed specifically for broadband distributed multimedia applications; therefore it will support the needs of the wide-band services. Frame relay will remain in the future a sub-Tl data networking service. 4. FRAME RELAY OR ATM Internet Service Providers use Frame Relay to provide high performance cost-effective solutions to their customers. For mow, Frame Relay is the choice for networks of E1/T1 services and below. Currently the major Frame Relay switch vendors as Cisco or Nortel, support speeds up to DS3 and support for OC-3 has come into the market in the last year. Frame Relay is a circuit switching technology designed from the necessity to have a dial-on-demand service to handle multiple connections using a single physical line. It alleviates the scalability problem of the leased lines

114

NEXT GENERATION WIRELESS NETWORKS

and it makes a better use of the line. In Frame Relay a subscriber site leases a permanent dedicated line that is connected to a Frame Relay switch in a telephone central office. So logical connections are established to one or more remote Frame Relay sites. The logical connections are called virtual circuits and all share the same physical port on a router and the same leased line and data service unit (DSU). The cost of a leased line is proportional with its length. The cost of Frame Relay service is proportional with the required bandwidth. The speed of a Frame Relay service does not need to be the same for all the subscriber sites. A company can have a DS-3 connection for the headquarters office and several DS-1 circuits for branch offices. In conclusion Frame Relay solutions have access rates at a lesser cost as leased lines so they are a good economical solution. Frame Relay is a technology deployed to provide the end user with a Virtual Private Network capable of supporting high-speed transmission requirements. A lot of functions performed by the classical data networks as error correction and retransmissions are eliminated by taken into advantage of relatively error free transmission systems as optical fibers. As the intelligence is build more and more into the end hosts, the Frame Relay network does not need to perform many QoS functions and the management operations are few. It is so called "bare-bone" approach that results in fast networks but places more responsibility on the end-user systems and management entities. The typical applications for frame relay networks are bursty data with high capacity requirements, client server database queries, broadcast video email and file transfer. Frame Relay is not topology dependent but is currently implemented as point to point in a star scheme similar to the leased lines network. A very important advantage of this network is the low cost. Let's take an example. The computer at the headquarter site that receives the traffic from many point to point connections is set initially as a percentage of the aggregate remote sites traffic. If the congestion becomes a burden at the headquarter location, another DS1 facility should be installed so the access rate to the main site is increased from DS1 to DS3 in increments of Tl (1.544Mbps) or El (2Mbps). Frame Relay is used as a high-speed technology to interconnect LANs. It has explicit flow control and the sequencing of data is the user responsibility. A node is informing the network of a problem and does not take any action as ceasing the transmission. Congestion and flow control are optional and some vendors have not implemented them yet. ATM is a circuit-oriented technology that was designed to provide different QoS levels to transport any type of user traffic: data, voice, and video. ATM traffic is transported into fix-length cells identified by a virtual

InfoCity: Providing QoS to Mobile Hosts

115

circuit identifier (VCI) in the header of the cell. The VCI is used to route the cells through the network. ATM does not support error correction operations. Only the signaling traffic can be retransmitted. ATM was designed to deliver at least OC-1 (155 Mbps) but went down to support T3 and Tl widely in demand. Tl ATM has too much of overhead and does not justify the cost when compared to Frame Relay for data networking applications. But for applications that mix different types of data - voice, video - the most important issue are the QoS guarantee and the bandwidth optimization. The overhead is irrelevant in this case. ATM can be seen as a solution to a core transport mechanism interconnecting different types on networks. There are 2 methods to interconnect ATM and Frame Relay. The first one is tunneling the Frame Relay frames through the ATM network. The variable Frame Relay frames are segmented and encapsulated into the payload of the ATM cells without disturbing the Frame Relay header. The increased overhead is paid back by higher switching speeds. The second method would be a translation service between ATM and Frame Relay. The frame header information is mapped into an ATM header so an ATM device can talk to a frame relay device. But ATM promises much more than only core network interconnections. Frame Relay has a place in InfoCity as a cheap solution for providing Tl and up to T3 speeds in access networks. But this place could be challenged by ATM soon. 5. IP OVER ATM

Exploring the demand for data networking and Internet services, researchers reached the conclusion that the classical solution of deploying different networks and trying to interconnect them is very costly and resource intensive. What if someone can deliver all the required services from the same infrastructure? Many efforts were put in designing integrated IP and ATM solutions - LAN emulation [1], classical IP over ATM [2], address resolution [3], next-hop resolution protocol [4] - with the hope that the results will deliver well known and widely used IP application taking advantage of the ATM speeds. When high - speed multimedia application are offered as an IP over ATM service the real network topology is hidden from the IP layer and we face inefficiency and duplication of functionality. In case of LAN emulation for example, the higher layer (IP) is encapsulated into the appropriate LAN MAC packet format and then is sent on the ATM network. The advantage is that no modifications are necessary to the higher protocols to cooperate with ATM. In classical IP over ATM both IP and ATM need their own routing protocols. There is duplication in the maintenance and management

116

NEXT GENERATION WIRELESS NETWORKS

functions. New management functions are required for address translation and data format conversion. The problems are hard to identify and locate [5]. When one tries to interconnect IP router using ATM switches the number of neighboring routers in a cloud can become very large and the nest-hop routing table is expanding uncontrollably. For N routers the update process is increased with N2. If a failure occurs a complex protocol should be employed to deal with the recovery [6]. It is desirable to keep the best part of both technologies and try to unify them in a common service architecture than to try to superimpose them. ATM offers link bandwidth scalability and speed and switching capacity for various types of traffic. TCP/IP has been imposed as the widest spread data protocol because of its connectionless nature that brings simplicity, scalability and robustness to failures. IP makes no assumption of the underlying network beyond the capacity of forwarding a data gram packet to the destination. No state has to be maintained in the intermediary routers for

individual connections since the destination address in contained in the

forwarded packet. From here the robustness to failures. Some researchers have proposed to implement IP directly on top of the ATM hardware using the flow concept [7]. A flow is a sequence of datagrams that follows the same route through the network and receives same service policies at intermediary routers. Flow carrying real time traffic would be mapped to the ATM connections. Short duration flows as database queries will be carried by classical IP forwarding between routers interconnected using an ATM network. Establishing an ATM connection for every IP flow would impose a big burden on the ATM signaling protocol. The ideal solution will combine the easy to use and scalability of IP with the high QoS, speed and performance of the ATM. It has to provide virtual private networks that let users run critically IP-based applications securely. A variety of value-added IP and ATM services should be able to deploy easily to meet customers needs. The service providers networks must be integrated with a range of already installed technologies to cut the cost of connecting new users. If past attempts in offering simultaneous IP/ATM services resulted in tunneling, most recent ones as multiprotocol label switching [8] enable a more integrated and expandable solution. In multiprotocol label switching the core network switches provide automatically set up calls and dynamically switch IP traffic over ATRM network in real-time, and the multiservice switches provide subscriber interfaces for multiple data network service type: frame relay, ATM cell relay, etc. By adapting each service to a common protocol and applying traffic management functionality, a multiservice switch can significantly increase the network performance [8].

InfoCity: Providing QoS to Mobile Hosts

117

ATM could provide the core network for InfoCity. Even though the cost of ATM is still high for small private networks, it is definitely the future backbone solution. As a core technology ATM will be integrated in multiprotocol switches capable or interconnecting different types of network in a cost –effective manner. Beside using ATM as a core technology tor InfoCity, LAN emulation could be used in its small business private networks for videoconference applications or for on-demand video services. IP services and well known IP applications could be run over a high-speed ATM network to provide for example, distance learning applications before different university campuses of InfoCity. 6. HIGH SPEED INTERNET: BACKBONE NETWORK SERVICE NEXT GENERATION INTERNET AND INTERNET2

An example of IP over ATM implementation is Backbone Network Service (vBNS) [9]. MCI's very-high performance network is designed to serve the research communities that require superior performance than available commercial network. It runs on an OC-12 (622.08 Mbps) and OC-48 SONET pipes and

aims to provide a test-bed to new Internet technologies and services. With more than 91 connections throughout United States, 4 supercomputer centers, vBNS is a promising infrastructure that provides research and development institutions with high-speed data connectivity. Within vBNS congestion is not so much of a problem comparing with Internet because a limited number of research institutes, each with a separate Internet connection, use vBNS only to test advanced networking applications and experiments. Next Generation Internet [10] is implemented by DARPA to provide a network that is at least 100 or even 1000 times faster than today's Internet. Intenet2 is a collaborative project for more than 120 universities that aims to facilitate the development of state of the art distributed applications using networks as vBNS and NASA Research and Education Network. With this infrastructure in place (Figure 2) the question is which are the core services offered in order to be tested and improved by the research community?

118

NEXT GENERATION WIRELESS NETWORKS

Beside best effort IP, switched virtual circuit logical IP subnets and point to point permanent virtual circuits, an ongoing effort is concentrated towards reserved bandwidth services because the traffic pattern - some bursty flows and delay sensitive applications - require a dynamic and efficient allocation of the bandwidth on a session per session basis. Resource Reservation Protocol (RSVP) may be implemented to trigger the reserved bandwidth service. There is a growing impression in networking research world in the last years that connections to the Next Generation Internet, Internet 2, or vBNS is vital for a place in future networking research. Having a broadband pipe for classical “best-effort” IP traffic is not a suitable solution for InfoCity due to the rate at which developed applications are growing and bandwidth requirements are exploding in recent years. Rather, in InfoCity, it would be better to concentrate our efforts toward technologies that bring controlled quality and can differentiate between users in term of resource allocation and management.

InfoCity: Providing QoS to Mobile Hosts

119

7. RSVP – BRINGING QoS TO AN IP NETWORK

The RSVP protocol allows applications to reserve bandwidth for their data flows (see Figure 2). It is used by a host, on the behalf of an application data flow, to request a specific amount of bandwidth from the network. The routers use RSVP to forward bandwidth reservation requests. To implement RSVP, RSVP software must be present in the receivers, senders, and routers. The two principle characteristics of RSVP are:

1. It provides reservations for bandwidth in multicast trees (unicast is handled as a special case). 2. It is receiver-oriented, i.e., the receiver of a data flow initiates and maintains the resource reservation used for that flow. RSVP is sometimes referred to as a signaling protocol. By this it is meant that RSVP is a protocol that allows hosts to establish and teardown reservations for data flows. The term signaling protocol comes from the terminology of the circuit-switched telephony community. RSVP operates on top of IP, occupying the place of a transport protocol in the protocol stack. RSVP does not transport application data and it is comparable to a control protocol like ICMP or IGMP. RSVP makes receivers responsible for requesting QoS control. A QoS control request from a receiver host application is passed to a local RSVP

implementation. The RSVP protocol caries the request to all the nodes on the reverse path to the data source.

120

NEXT GENERATION WIRELESS NETWORKS

In truth, the RSVP reservation message does not simply reserve bandwidth. Instead it contains a flowspec, which has three parts: a service class, a Rspec and a Tspec. The service class identifies the type of QoS the receiver desires from the network. Two service classes are in the process of becoming Internet standards: the Controlled Load service class [11], which promises applications that their packets will usually see no queuing delays and minimal loss; and the Guaranteed QoS service class [12], which provides deterministic delay bounds to packets. The Rspec (R for reserved) defines the specific QoS, such as the fraction of lost packets the receiver is prepared to tolerate. The Tspec (T for traffic) describes the data flow, typically described in terms of leaky bucket parameters. RFC 2210 [13] describes the use of the RSVP resource reservation protocol with the Controlled Load and Guaranteed QoS services. The RSVP protocol defines several data objects that carry resource reservation information but are opaque to RSVP itself. The usage and data format of those objects is given in this RFC.

Path messages are another important RSVP message type; they originate at the senders location and flow downstream towards the receivers. The principle purpose of the path message is to let the routers know on which links they should forward the reservation messages. Specifically, a path message sent within the multicast tree from a Router A to a Router B contains Router A's unicast IP address. Router B puts this address in a path-state table, and when it receives a reservation message from a downstream node it accesses the table and learns that it should send a reservation message up the multicast tree to Router A. In the future some routing protocols may supply reverse path forwarding information directly, replacing the reverse-routing function of the path state. Along with some other information, the path messages also contain a sender Tspec, which defines the traffic characteristics of the data stream that the sender will generate. This Tspec can be used to prevent over reservation. Through its reservation style, a reservation message specifies whether the merging of reservations from the same session is permissible. A reservation style also specifies from which senders in a session the receiver desires to receive data. Recall that a router can identify the sender of a datagram from the datagram's source IP address. There are currently three reservation styles defined: wildcard-filter style; fixed-filter style; and shared-explicit style. Wildcard-Filter Style: When a receiver uses the wildcard-filter style in its reservation message, it is telling the network that it wants to receive all flows from all upstream senders in the session and that its bandwidth reservation is to be shared among the senders. Fixed-Filter Style: When a receiver uses the fixed-filter style in its reservation message, it specifies a list of senders from which it wants to

InfoCity: Providing QoS to Mobile Hosts

121

receive a data flow along with a bandwidth reservation for each of these senders. These reservations are distinct, i.e., they are not to be shared. Shared-Explicit Style: When a receiver uses the shared-explicit style in its reservation message, it specifies a list of senders from which it wants to receive a data flow along with a single bandwidth reservation. This reservation is to be shared among all the senders in the list. Shared reservations, created by the wildcard filter and the shared-explicit styles, are appropriate for a multicast session whose sources are unlikely to transmit simultaneously. Packetized audio is an example of an application suitable for shared reservations; because a limited number of people talk at once, each receiver might issue a wildcard-filter or a shared-explicit reservation request for twice the bandwidth required for one sender (to allow for over speaking). On the other hand, the fixed-filter reservation, which creates distinct reservations for the flows from different senders, is appropriate for video teleconferencing. The reservation can be removed by senders with a PathTear message or by receivers with a ResvTear message. Alternatively they can stop sending PATH and RESV messages and the reservation state times out.

RSVP will be an option in a future modernized IP networks. Right now it is supported by CISCO routers and some research versions of a RSVP daemon are in tests. But few commercial applications really make use if it.

So the protocol will have a limited use in InfoCity at the beginning. 8. MOBILE IP In the traditional Internet Protocol the IP address identifies without any

ambiguity the user’s location. This assumption simplifies the work in all routers in the network since every time a router receives a packet with a destination host address, it only needs to look into its routing tables to determine on which port the packet has to be sent to that destination. Mobile IP allows a host to move and connect to different subnetworks in a way transparent to higher layer protocols such TCP [14]. In mobile IP every user has two addresses. The first one is the permanent home address and the second one is the temporary “care of” address. The home address is the normal IP address that points to the location where the

mobile user is found most of the time, this is also the subnetwork the user is registered with. The care of address is an indication of the actual location of the user as it moves to different subnetworks. Following this mobile user we

will have a router called Home Agent (HA) in the home subnetwork that will keep track of the mobile user temporary location. A router in the visiting subnetwork is called the Foreign Agent and assigns the care of address to the mobile user during as long as it visits the subnetwork. (Figure 4)

122

NEXT GENERATION WIRELESS NETWORKS

Mobile IP is a layer 3 technology that can be used with any link-layer

device wired or wireless. The mobility support is provided using tunneling for data forwarding from permanent home network to the visiting network. When a mobile host connects to a subnetwork it realizes that it is visiting a different subnetwork by listening to a periodic beacon signal transmitted by the foreign agent at that location. The mobile host initiates a registration procedure with the foreign agent that ends with an IP care of address assigned to it. This IP address is also transmitted to its home agent. When a packet is sent to the mobile host it finally reaches the home agent, because

the packet contains the permanent address as destination. The home agent encapsulates the original IP packet into another IP packet with the care of address as destination and it transmits the packet again. The packet reaches the foreign agent using normal routing since the intermediary routers see

only the care of address. This is called tunneling. The foreign agent decapsulates it and send the original packet to the mobile host. The time a mobile user is registered with a foreign agent is volatile so the mobile host

has to register periodically. There are two operation modes defined by the protocol. In basic mode the home agent responds to registration request of mobile nodes away from home network. After completing the registration process it forwards the receiving packet to the foreign agent of the foreign network. In advanced mode, after performing basic mode operations, the home agent sends mobile binding information to the network router of sender. The router keeps this information during communication. After receiving binding information from the home agent packets generated from the sender are directly

forwarded to the foreign agent of the mobile node without connection with home agent. The biggest issue facing Mobile IP is security. Strong authentication is needed because the mobile node may be accessing corporate resources from

InfoCity: Providing QoS to Mobile Hosts

123

the Internet. Fortunately, standards are available for authentication. For example, FTP Software's Mobile IP implementation provides mutual authentication of the mobile node and the home agent. The thornier security problem is one of traversing firewalls. This problem is twofold because it involves firewalls both at the home network and at the foreign network. Many firewalls rely on packet filtering to implement some or all of their security. If the mobile node is trying to communicate with the home agent or other hosts on its home network, the firewall there may reject datagrams from the mobile node because the datagrams have the source address of an internal node, but appear on an external port. A similar problem can occur at the foreign network. Many firewalls are configured so that they will not pass datagrams from inside a network to the Internet if the source address differs from what is expected. The intent is to prevent the internal network from being a haven for malicious users spoofing source addresses and perpetrating mischief on the Internet. Unfortunately, the Mobile IP node's address does not belong on the internal network, so its transmissions may be blocked. Although these firewall problems usually will arise during Internet communication, they also may come up in corporate Intranets as companies increase their use of internal firewalls. For instance, you may need to configure the firewall protecting the home network to allow ICMP datagrams addressed to the home agent, which will allow the mobile node to register its new location. 9. INTEGRATING RSVP WITH MOBILE IP – WHERE ARE THE CHALLENGES?

There are some enhancements to Mobile IP in the scope of combining mobility with QoS. When one tries to put RSVP and mobile IP to work together some interesting questions appear. Is it enough to perform an enhancement on both protocols to guarantee QoS to mobile users or the accent should be put on the coordination between the two protocols? The well-known characteristics of the wireless environment – high nonstationary BER, less bandwidth, etc - have a great impact on both protocols. When a mobile host moves to a different location all the packets in transit will reach the old location and get lost. This situation may represent a nondesired long period of time in which the mobile host will stop receiving audio or video stream. Here the basic hand-off protocols are not enough to handle the situation and RSVP should be invoked to help during the recovery process. In the original IETF draft for mobile IP every packet sent to the mobile host had to go through the home agent. This leads to a non-optimal triangular routing. The situation increases not only the delay end-to-end but

124

NEXT GENERATION WIRELESS NETWORKS

also generates wasted bandwidth in non-optimal paths that cannot be used for other connections. For this reason optimal routes play a key point in providing QoS to mobile hosts. Here the challenge is how to manage route optimization while supporting QoS as well. In Mobile IP route optimization is done by transmission of short messages among source, home agent (HA), foreign agent (FA) using normal best-effort IP transmissions. This might be fast enough for data connections but for real time voice and video application it might not be satisfactory. Another important issue would be to see when is better to call RSVP: before, during, or after optimization. 10. RSVP AND MOBILE IP ENHANCEMENTS RSVP was designed to work in wired networks. When one tries to extend it to include mobile hosts, some issues have to be solved. First, there is the

fast movement of the mobile host. Instead of making a fresh reservation on the move, it is better to provide the mobile host with the capacity to make an active reservation in one foreign subnetwork and many passive ones in neighboring subnetworks. The challenge is that the mobile nodes change their location up to once per second. Every time a mobile node changes its location a new reservation should be made. Another problem appears because of the Mobile IP encapsulation. RSVP messages have a descriptor of the flow for which the reservation is

requested. The flow descriptor contains a list of packets headers fields that a router can use to distinguish the packets of the real-time flow which has requested QoS from a other data flows. When the packets travel encapsulated in the tunnel between the home agent and the foreign agent, the intermediary routers will treat all the flows as best-effort because they cannot see that a reservation is being made for a specific real-time flow. There must be a way to inform intermediary routers which flow should accept which kind of services. IP in IP tunnels are a widespread mechanism to transport datagrams in the Internet. Tunnels are used to route packets through portions of the network which do not implement a desired protocol (Ipv6 for example) or to enhance the behavior of the deployed routing architecture (e.g. Mobile IP). There are many IP in IP tunneling protocols. To deploy RSVP with the maximum flexibility it is desirable for tunnels to act as RSVP-controllable links within the network. A tunnel can participate in an RSVP aware network in three ways: as a logical link that may not support resource reservation or QoS control at all, as a logical link that may be able to allocate some resources specifically to individual data flows or as a logical link that may be able to make

InfoCity: Providing QoS to Mobile Hosts

125

reservation for individual end-to-end data flows. The first one is called the best-effort link, the second one is a configured resource allocation over the tunnel. For the last one the tunnel reservations are created and torn down dynamically as end-to-end reservation come and go. When the two end points of a tunnel are capable of supporting RSVP over tunnels the proper resources have to be reserved along the tunnel. Depending on the requirements of the situation one might want to have one client’s data flow placed into an aggregate reservation (as in second type of tunnel) or, if possible, to have a new separate reservation for the data flow. Currently RSVP signaling over tunnels is not possible. RSVP packets get encapsulated with an outer IP header and do not carry Router Alert option, making them invisible to RSVP routers between the two points of the tunnel. It is impossible to distinguish between packets that use reservation and those who don’t, or to differentiate the packets belonging to different RSVP sessions while they are in the tunnel. Some enhancement should be added to IP tunneling to allow RSVP to make reservations across all IP in IP tunnels. If packets require reservation within the tunnel there has to be some attribute other than the IP address visible to the intermediate routers, so that the routers may map any packet to an appropriate reservation. The solution chosen was to encapsulate such data

packets with an UDP header and to use UDP port numbers to distinguish between packets of different RSVP reservations. A procedure to map the end-to-end session to the tunnel session is

detailed in [15]. The tunneling introduces new security issues as the need to control and authenticate access to enhanced quality of service. This requirement is discussed in RFC 2205 [16]. The IP in IP encapsulation is not sufficient because it does not provide a transparent way to classify the tunnel packets. The IP in UDP solves the problem but the security issues are not negligible. The Encapsulation Security Payload and an authentication header can be used but the encryption can change the location of the header. RSVP can handle slow changes in the established paths due to variations in the topology or congestion conditions. A mobile node could provide an explicit indication to a receiver that it has changed its location and the receiver should reserve resources along a new path. It could use mobile IP registration (the home agent will perform reservation between itself and the mobile host). When a mobile host moves into a new foreign subnetwork there should be some resources already reserved for this host with a high probability. Although this reservation may not satisfy the largest resource reservation requirement of this mobile host, a partial resource reservation should be able to satisfy the basic service requirement of the mobile host. Also the latency

126

NEXT GENERATION WIRELESS NETWORKS

between requesting a service and getting served with some degree of service should be minimized. Mobility will be a key functionality in InfoCity not only in corporate business networks but also in access networks, as the management functions will benefit enormously from it. Mobile IP is a new technology and it is not well integrated in commercial products. Only few available products as RomIn from IKV++ (http://www.ikv.de/products/index.html) have integrated Mobile IP. These products should be considered as they can be integrated with classical IP applications to provide mobility in InfoCity’s distributed business networks

11. CONCLUSIONS We have presented and discussed different candidate technologies and protocols that could be integrated into a future Infocity state-of-the-art network, as part of a multimedia network infrastructure, supporting both mobile and stationary users. No implementation solutions were proposed;

rather, a general view into the problem was provided, to identify where the outstanding issues are that remain to be solved.

REFERENCES [1] LAN Emulation over ATM Version 2 - LNNI Specification, ATM forum af-lane.0l12.000, Feb 1999 [2] RFC 1577, “Classical IP and ARP over ATM,” 1/20/94. Update in http://www.internic.net/internetdrafts/draft-ietf-ion-classic2-01 .txt. 11/26/1996 and "Classical IP and ARP over ATM", 04/22/1997, http://www.internic.net/ internet-drafts/draft-ietf-ion-classic2-02.txt [3] "NHRP Protocol Applicability Statement", D. Cansever, 07/25/1997, draft-ietf-ion-nhrp-appl-02.txt [4] Cisco Implementation of NARP at http://www.cisco.com/univercd/cc/ td/doc/product/ software/ios111 /mods/4mod/ 4c book/4cip.htm#xtocid 1050321

[5] Newman, P. “ATM local area networks” IEEE Communications, March 1994 [6] Liping An, N.Ansari, “Traffic over ATM networks with ABR Flow and congestion control”, IEEE Selected Areas in Communications, August 1997

[7] P.Newman, “ I P switching – ATM under IP”, IEEE/ACM Transactions on Networking, vol.6 no.2, April 1998 [8] E.Roberts “Getting a Handle on Switching and Routing”, IBM white paper Oct 1997

InfoCity: Providing QoS to Mobile Hosts

127

[9] K.Thompson, G.J. Miller, and R. Wilder “Performance Measurement on the vBNS”, Interop ’98 Engineering conference [10] http://www.ngi.gov/pub [11] RFC 2211 J. Wroclawski, “Specification of the controlled load network element service”, IETF Network Working Group, September 1997 [12] RFC 2212 Shenker, et al, “Specification of Guaranteed Quality of Service”, IETF Network Working Group, September 1997 [13] RFC 2210 J. Wroclawski, “The use of RSVP with IETF Integrated Services”, IETF Network Working Group, September 1997 [14] C. Perkins, “IP Mobility Support”, RFC2002, October 1996 [15] A. Terzis, J. Krawczyk, J. Wroclawski, and L. Zhang, “RSVP Operation over IP Tunnels”, Internet Draft, draft-ietf-rsvp-tunnel-02.txt, February 1999. [16] R. Braden, L. Zhang, S. Berson, S. Herzog and S. Jamin, “Resource Reservation Protocol (RSVP) – Version 1 Functional Specification”, RFC2205, September 1997

ABOUT THE AUTHOR

Patricia Morreale is an Associate Professor in the Department of Computer Science and Director of the Advanced Telecommunications

Institute (ATI) at Stevens Institute of Technology, Hoboken, NJ. Her research interests include network management and performance, wireless system design and mobile agents. She received her Ph.D. in Computer Science from Illinois Institute of Technology, Chicago, IL in 1991. She is co-editor of the Telecommunications Handbook (1999) and the Advanced Telecommunications Handbook (2000), both published by IEEE Press, and holds a patent in the area of real-time information processing. She has more than 25 journal and conference publications. She is an editorial board member of the Journal of Multimedia Tools and Applications (Kluwer Academic). She has served on the technical program committees of several workshops and conferences, and has organized and chaired sessions at IEEE conferences. She was a Guest Editor of the IEEE Communications Special Issue on Active, Programmable, and Mobile Networks. She will be ViceChair, IEEE INFOCOM 2002. Morreale is a member of Association for Computing Machinery and Senior Member of Institute of Electrical and Electronic Engineers.

This page intentionally left blank.

Chapter 4

ASSISTED GPS FOR WIRELESS PHONE LOCATION – TECHNOLOGY AND STANDARDS

BOB RICHTON, GIOVANNI VANNUCCI, AND STEPHEN WILKUS Lucent Technologies/Bell Laboratories, Whippany, NJ, USA

Abstract:

Many approaches have been advanced for locating the geographic position of wireless phones, both for emergency response purposes and for emerging

location-based services. Depending mainly upon the services envisioned and the particulars of the air interface, one or another approach appears appealing,. Increasingly, the assisted-GPS approach is gaining recognition as the approach that can best meet all requirements. Among the important requirements are those mandated in the USA by the Federal Communications Commission (FCC) for Enhanced 911. Assisted GPS provides the best accuracy for use in

location services. It is rooted in the suitability of wireless networks to provide data over the air to enable fast acquisition and lower power consumption, as

well as provide indoor operation—capabilities that conventional GPS cannot provide. The assisted-GPS approach promises to enable a new industry of

location-based services and important new safety measures. Keywords:

cellular systems, geolocation, standards, wireless location, assisted-GPS, FLT, E-OTD, observed time difference of arrival, IS-801, WAG, FINDS.

130

NEXT GENERATION WIRELESS NETWORKS

1.

INTRODUCTION

By now, the need for wireless geolocation* is well established. The need is driven in the USA largely by the Federal Communications Commission (FCC), which ruled that the location of a Mobile Station (MS) calling 911 must be provided to the Public Safety Answering Point (PSAP). Besides

emergency services, many other geolocation-based applications have been described[1]. Among these applications are: – Location sensitive billing: Enabling price differentials based on

the caller location. – Location-based information services: Providing directions to find restaurants, hotels, cash machines, gas stations, etc. – Network optimization: Used to improve daily operations of a wireless network – Fleet management and asset tracking: Giving ability to locate

(FCC), which ruled that the location of a Mobile Station (MS) calling 911 vehicles, personnel, or property to more efficiently manage operations.

Many more applications have been described[2]. Realizing this need, people unfamiliar with the details of wireless technology often think that Global Positioning System (GPS)[3] could be combined with Mobile Stations to support geolocation. However, combining GPS and mobile in a straightforward way turns out to be unsuitable for wireless applications because GPS: – Does not work in buildings or shadowed environments, including urban canyons – Is too slow for some services, particularly for emergency use – Is too costly and too bulky to be included in a modern mobile terminal – Drains common mobile station batteries at an unacceptably high rate – Despite recent, dramatic advances in GPS technology, these problems persist. However, “Assisted GPS” overcomes all these limitations while providing better accuracy than any terrestrialbased approach, or conventional, stand-alone GPS. This paper describes the basic technology of assisted GPS, which circumvents the problems listed above and achieves high accuracy at reasonable cost. The technique exploits the availability of the bi-directional wireless link to divide the job of determining the mobile phone's location * The term geolocation is used here to refer specifically to “location on the earth” (as latitude and longitude) as opposed to “location within the network,” which is the more common meaning of the word “location” when used in the context of wireless communications.

Assisted GPS for Wireless Phone Location

131

between the phone itself and the wireless network. This results in a level of performance that exceeds that of a conventional GPS receiver, even as complexity is reduced. Assisted GPS is, therefore, neither purely a networkbased, nor a handset-based solution, and is sometimes called a hybrid. Note that for purposes of the FCC mandate, however, it would be considered handset-based because it requires new handsets. In assisted GPS, the mobile includes a "partial" GPS receiver that is controlled (a better term might be "primed") by the network (which we'll refer to as the "server") and the received GPS signal needs only minimal processing in the phone before being retransmitted to the server over the wireless link. The server can then perform the location computation taking advantage of additional information (such as terrain and network data) not generally available to a GPS receiver. There are two reasons why assisted GPS works so well: a) The assistedGPS server has its own GPS receiver and, therefore, already knows with great accuracy what signals the mobile phone's GPS receiver is receiving; and b) the wireless system already has a reasonable estimate of the phone's location. These two elements enable the assisted-GPS receiver to detect a received signal that is orders of magnitude weaker than is required by conventional GPS techniques, and to do so in a fraction of a second. Note that while, on the surface, this technique sounds similar to the wellknown Differential GPS (DGPS) technique, the underlying principles are completely different. The DGPS technique does not provide any improved ability to detect GPS signals under low Signal-to-Noise Ratio (SNR) conditions; it only improves the accuracy of the GPS location estimate. Of course, the assisted GPS technique can (and should) also employ DGPS methods in its location estimates, so that the expected accuracy of assisted GPS will be equivalent to that of DGPS.

1.1

Some Previous Works

Although assisted GPS has been widely described in standards bodies and wireless industry meetings, few papers on the technology appear to have been published. NAVSYS Corporation’s description of TIDGET may have presaged assisted GPS[4]. Another step towards GPS-mobile phone integration was described by DiEsposti et.al.[5] early in 1998, with perhaps the first public description of assisted GPS coming from Moeglin and Krasner[6] later that year. A recent article by Norman Krasner provides a very readable account of assisted GPS and an interesting implementation of it in the handset.[7]. Two other papers from the ION ’99 Conference, one from L. J. Garin et. al. [8] and one from A. J. Pratt,[9] cover architecture issues concerning assisted GPS.

132

NEXT GENERATION WIRELESS NETWORKS

2.

FUNDAMENTAL CONCEPTS

2.1

The Global Positioning System (GPS)

A detailed discussion of GPS is beyond the scope of this document; we simply summarize a few essential features that are needed for understanding

assisted GPS. Additional details and parameters of GPS will be introduced as necessary. For a thorough description of GPS and additional references see [3,10]. The heart of GPS is a constellation of 24 satellites orbiting the earth at an altitude of about 20,000 km. The orbits are chosen to ensure that there are always at least four satellites visible (i.e., sufficiently high above the horizon) from any place on earth at any time. The satellites act like beacons, sending down radio signals that are carefully timed at the source in a predetermined way. At a GPS receiver, signals from different satellites arrive with different propagation delays, depending on the position of the receiver. The receiver makes an accurate measurement of the time of arrival of each signal, and the difference between the time of arrival and the (predetermined and, therefore, known) time of departure yields the distance (range) to each satellite. Unfortunately, in most cases, the receiver does not initially have a very accurate notion of time and the computed ranges will contain a large error. Nonetheless, since the signals were perfectly synchronized at transmission, the differences in their times of arrival are very accurate and carry information about the mobile's position. Because of the inaccuracy of the measured satellite ranges, they are commonly referred to as “pseudo-ranges,” and the number of satellites required for a location fix is four instead of three, as one must solve for four variables of latitude, longitude, altitude, and time. To compute latitude, longitude, and altitude based on the pseudo-ranging measurements, the mobile must detect signals from at least four satellites† and it must know the exact position of those satellites at the time the signals were transmitted. For this purpose, each satellite also transmits a digital bit stream (at 50 bps) with precise information on the satellite's orbital parameters (called ephemeris). An important feature of the GPS system is that the same signal is used for both pseudo-ranging and for transmitting the data. As we shall see, the fact that the signal carries data bits that are a priori unknown, limits the detectability of the signal. A key feature of Assisted-GPS techniques is that this uncertainty is removed, resulting in much improved signal detectability. †

If altitude is already known, as is the case for a receiver that is known to be at sea level, three satellites are sufficient.

Assisted GPS for Wireless Phone Location

133

The satellites travel at high speed. The distance between satellite and receiver may vary by more than one half mile per second. This results in a doppler shift in the signal carrier that may be as large as ±4500 Hz. Each GPS satellite transmits several signals. The signal most commonly used by civilian GPS receivers is the so-called C/A signal (C/A stands for "Coarse Acquisition") The C/A signal is a Direct-Sequence SpreadSpectrum signal with a chip rate of 1.023 MHz. Chip modulation is Binary Phase-Shift Keying (BPSK) and the underlying (unspread) 50-bps data is also modulated using BPSK. The spreading code is a shift-register sequence (or PRN sequence, for "Pseudo-Random Noise") with a repetition period of 1023 chips. Each satellite uses a different PRN code and all the satellite signals are transmitted in the same band centered around 1.57542 GHz. Satellite orbits and antenna radiation patterns are such that there is little variation in the received signal level on the ground as the satellite moves in its orbit. GPS specifications for the C/A signal call for a minimum userreceived power of -130 dBm at a linearly polarized antenna with 3-dB gain [11] although, in practice, the system routinely delivers –125 dBm.

2.2

Assisted GPS

Figure 1 shows a diagram of a typical assisted GPS system: The mobile phone has a "partial" GPS receiver (or GPS “sensor”) that picks up the signals from the GPS satellites. At the same time, the assisted-GPS server monitors the same satellite signals through a reference GPS receiver.‡ We expect each GPS server to support many base stations (for example, the assisted-GPS server might be co-located with the Mobile Switching Center, or MSC). The assisted-GPS server should have exact knowledge of the GPS signal being transmitted by the satellites. Through its connection with the MSC, the assisted-GPS server knows the cell and sector where the mobile is located (which defines its position to within a couple of miles or so). In more refined systems, the server may have even better knowledge of the mobile’s coarse location; the better this initial “guess” at the mobile’s location, the better the overall system will operate. Through the wireless link, the assisted-GPS server will exchange information with the assisted-GPS receiver, essentially asking it to make specific measurements and collecting the results of those measurements.

‡

The GPS server does not actually need a GPS receiver in physical proximity, it can, in fact, use a service such as differential-GPS (DGPS) available through the internet or low frequency broadcast media.

134

NEXT GENERATION WIRELESS NETWORKS

The basic idea behind assisted GPS is to reduce the workload on the mobile's GPS receiver as much as possible, at the expense of the assistedGPS server. To this end, all complex calculations are done by the assistedGPS server and, since the assisted-GPS server has its own source of GPS data, there is no need to demodulate the ephemeris information from the signal received by the assisted GPS receiver at the mobile, which is needed only for the pseudo-ranging measurements. The signal processing required to obtain those measurements is divided between the assisted-GPS server and the assisted-GPS receiver. The real power of assisted GPS is that we can go beyond simply dividing the labor between the assisted-GPS receiver and the assisted-GPS server: As mentioned above, the assisted-GPS server already knows a coarse location for the phone, and it sees the signal coming down from the GPS satellites. It can, therefore, predict what signals the assisted-GPS receiver will be receiving at any given time with great accuracy. Specifically, it can easily predict the doppler shift experienced by the signal due to satellite motion, and it can also accurately predict other signal parameters that depend more strongly on the mobile’s exact location. For example, the typical size of a cell sector is about 2 miles or less, which corresponds to an uncertainty of about ±5 µs in the predicted time of arrival of a satellite signal at the mobile.

Assisted GPS for Wireless Phone Location

135

This, in turn, corresponds to an uncertainty of only ±5 chips of the spreading

code of the C/A signal. Thus, the assisted-GPS server can predict the PRN sequence that the mobile receiver should use to de-spread the C/A signal from a particular satellite to within ±5 chips; and can communicate that prediction to the mobile. Let's say that the assisted-GPS server conveys to the mobile the correct doppler shift and PRN synchronization for a nominal position in the center of the sector. Then, if the mobile happens to be near the center of the sector, it can immediately begin to de-spread the corresponding satellite signal at the doppler-shifted carrier frequency; but, even if the mobile is not exactly

in the center of the sector, a small amount of trial and error will be sufficient to hit the correct PRN. This is because, as we observed, PRN phase uncertainty is only ±5 µs, and the doppler shift is virtually the same over the entire sector. After de-spreading, the bandwidth of the signal is that of the underlying 50-bps navigation data bits (the bits containing mainly ephemeris information). This bandwidth is so small that the assisted-GPS receiver could, in principle, digitize the signal and convey it to the assisted-GPS

server over the wireless phone link. In practice, there is a wide range of possibilities for how to split the job of obtaining a GPS fix between the mobile and the server. As will be described later, one solution involves

additional processing in the mobile; indeed, the recently-issued IS-801 standard and the TIA/EIA-136 Rev. C draft standard allow for the possibility of the mobile completing the location fix locally, with or without additional information from the server.

2.3

Assisted GPS Advantages

The above procedure for locating a mobile phone through assisted GPS

should be contrasted to what a conventional GPS receiver needs to do. When it is first turned on, a conventional receiver has no idea where in the world it is, which satellites are visible, where they are in the sky, what their

Doppler frequency offsets are, and what the timing is of the associated PRN sequences. It has to start a lengthy search over a vast parameter space (all possible satellite PRN sequences, all possible PRN synchronizations, all possible doppler shifts) to find the satellite signals. When it hits the correct PRN sequence with the correct timing and the correct doppler for one of the satellites, it knows that it's good because a 50-bps signal emerges; however, since it doesn't know a priori what the bit modulation is supposed to be, that signal has to be fairly strong to both avoid false positives and allow reliable demodulation of the bits. By contrast, the search space for an assisted-GPS

mobile receiver is much smaller. Furthermore, the mobile can learn what

136

NEXT GENERATION WIRELESS NETWORKS

the 50-bps bit stream is supposed to be from the server and, therefore, it can determine the presence or absence of the signal with a small fraction of the signal strength otherwise required for full demodulation. The first advantage reduces acquisition time from minutes to less than a second; the second advantage allows operation in severely faded conditions such as indoors.

2.4

The Need For Accurate Timing

In this high-level description of the assisted-GPS technique we have, by necessity, glossed over many details that must be dealt with in practical implementations. One of these, however, deserves special attention. It is the assumption that the assisted-GPS server can communicate to the mobile the correct timing of the PRN sequence with an accuracy of a few microseconds. In practice, the assisted-GPS server communicates with the mobile through a slow channel (e.g., 8 kbps) that goes through several interfaces and buffers before reaching the mobile. In general, there will be

an unknown delay much larger than a few µs in that connection. For the accurate PRN timing specification to be meaningful, the mobile must have a

notion of time that matches that of the assisted-GPS server to an accuracy better than the hoped-for PRN timing accuracy. Otherwise, the signal search space will have to be widened to include the larger timing uncertainty. Through its GPS reference receiver, the assisted-GPS server can synchronize itself to the GPS system which, in turn, is synchronized with Universal Time (within a few nanoseconds). In the case of the ANSI-95 wireless standard, all base stations are also synchronized to GPS Time, and the mobiles derive their timing from the forward link, so that they, too, are synchronized to GPS Time. The ANSI-95 standard specifies a synchronization accuracy of a few µs, which meets the needs of assisted GPS well. Other communication standards (e.g., GSM, TIA/EIA-136 or AMPS) do not have a similarly stringent synchronization specification, and the design of an assisted-GPS system based on such standards must therefore either include a solution to the timing requirement or endure a larger search space in the time domain. A possible solution for systems based on TIA/EIA-136 or GSM involves adding calibration receivers in the field to monitor both wireless signals and GPS (or equivalent) timing signals used as a time reference. It is worth noting that a “Time Calibrator” of this sort does not require synchronous timing in the exchange of messages with the assisted-GPS server as long as both the calibrator and the server can unambiguously identify the same specific reference event in the wireless signal. Even in the absence of a very accurate timing reference, the assisted-GPS technique offers improved performance at lower cost compared to

Assisted GPS for Wireless Phone Location

137

conventional GPS. For example, a timing uncertainty of several milliseconds (which perhaps might occur in AMPS) implies a much larger search space for PRN sequence synchronization (up to about a thousand chip periods) which will increase acquisition time and require more signal processing in the assisted-GPS receiver; but this is still a lot less than for a stand-alone GPS receiver. More importantly, the availability of assisting GPS data provided by the server still allows the detection of the GPS signal at signal levels that are much lower than required by a stand-alone GPS receiver.

3.

PRACTICAL IMPLEMENTATION

This section describes the two parts of assisted GPS: the receiver/terminal and the server/network part. Figure 2 shows more detail for the mobile and the server parts of the overall system, and each is described in greater detail here.

138

NEXT GENERATION WIRELESS NETWORKS

3.1

The Terminal

As shown in Figure 2, and like most any receiver, the assisted-GPS mobile has an RF, an IF, and a digital section, although the IF may be a so called, “low-IF” type. Both the GPS and ANSI-95 signals use spread spectrum signaling with comparable carrier frequencies and chip rates. Therefore, acquiring a GPS signal requires functions somewhat like those used to acquire the pilot of a cellular or PCS COMA signal. This presents opportunities to leverage commonalties in the IF and digital sections of an assisted-GPS mobile following the ANSI-95 standards. This has been pointed out by Qualcomm, Inc. in their GPSOne product.12

3.2

The Assisting GPS Server

The main roles of the server are: 1. To interface with the network entities that will request and/or consume location data (note these are widely expected to be either in the private Wireless Intelligent Network [WIN] or the Internet) 2. to provide the assisting GPS data to the mobile 3. to calculate the location of mobiles 4. to interface to wireless network entities that may help the server to improve the assisting data it will generate and/or provide data to the server for more robust and accurate solutions for a mobile’s location The third function may not always be needed, since some high-end mobiles may conclude the location calculation themselves. Similarly, the fourth function may not always be needed—these are refinements of server functions that improve performance but may not be essential to assisted GPS. Starting with the left-hand side of Figure 2, we show input from a reference GPS. The reference GPS’ function is to maintain current data for all visible GPS satellites. It is beneficial, and in some cases necessary, for the GPS data to be project a short time into the future. The GPS data will be used to construct a Navigation Data Message for assisted GPS. A table or database within the PDE (server) will maintain a record for each GPS satellite, with information such as the PRN codes and observed or calculated doppler shifts for all visible satellites. The reference GPS could be a conventional, high-quality GPS deployed at each server or could be a service derived from existing, commercial Differential GPS service providers. The Reference GPS could be thought of as maintaining GPS data on expected satellite visibility within the server area, on the basis of cell and sectors covered by the assisted-GPS system, as well as the ephermeris of

Assisted GPS for Wireless Phone Location

139

each satellite that is expected to be useable and other orbital correction parameters may be useful for the location calculation done at the server. Constellations of GPS satellites are visible over areas extending for hundreds of kilometers, so large networks may be supported with only a few Reference GPS sites. The Assisting Message Constructor may formulate the assisting message based on network data such as Round Trip Delay (RTD), pilot phase offset, etc. These data can greatly help by reducing the size of the search window that the mobile will have to use in looking for GPS signals, and can be made available in IS95 networks. Search window size is a parameter called for in the IS801 standard, which will be described later in this paper. The functioning of the server in most cases will be initiated via a request from a location application, such as E911, a location-based billing service, or a navigation service. This function is shown in the lower center portion of Figure 2. The application could run in or through a Service Control Point (SCP) and would likely communicate to a wireless network via the Wireless Intelligent Network (WIN) using standard IS-41 messaging. The work of TIA’s committee TR45.2 on projects PN3890 and PN4288 are expected to standardize such messages. The interface can be expected to also

communicate either directly or indirectly with an authentication server to ensure privacy of user's location data, which must be assumed to be sensitive. Further discussion of location applications and their interactions with assisted-GPS system are beyond the scope of this document. The above discussion covers how the assisted GPS navigation message is constructed for transmission to the assisted-GPS terminal. All that remains to describe within the assisted-GPS server is the Location Calculator, whose function is obvious from the name. The Location Calculator receives data coming from the assisted-GPS receiver, it performs the necessary calculations to determine location. These calculations will likely include steps to: – Begin, of course, by determining which terminal is being located and which satellites it has detected. We assume here that the terminal has sent the assisted-GPS terminal PRN synch information (as described previously) for each satellite that it was able to lock onto. Of course, there are many variations and the location calculator could operate on "raw" data from the terminal. – The Location Calculator would calculate pseudoranges and then do typical GPS receiver functions of converting pseudoranges to distances and distances to specific locations such as latitude/longitude. Commonly used GPS techniques such as Kalman Filtering would be used as appropriate, depending on specific designs.

140

NEXT GENERATION WIRELESS NETWORKS

– Options to calculate velocity and heading in addition to location could be added. Many variations are possible. While most are beyond the scope of this document, we must mention differential GPS, which would be expected to be used. Since Selective Availability causes most of the inaccuracy in GPS usage today, differential GPS (DGPS) corrections would be applied to improve the solution accuracy. The inclusion of DGPS to the Location Calculator would likely make assisted GPS the most accurate way to locate terminals; DGPS is commonly able to provide 10 meter accuracy or better. Other techniques, such as applying atmospheric corrections, knowledge of local terrain, altitude aiding, etc. would likely be applied. These techniques are not likely to be available if the location calculation is concluded in the mobile.

4.

PERFORMANCE

Performance of wireless location systems is a complex subject13 and not addressed here. We describe only key concepts relating to performance of assisted GPS technology, not system performance of either mobiles or systems.

4.1

Link Budget For Assisted GPS

The nominal loss from a 1-2 story building at 1.5 GHz is ~20 dB. This

implies that most conventional (i.e., not assisted) GPS receivers will not work (or not get enough satellites) in such a building. This is consistent with everyday experience. For example, in a typical 1-2 story open frame construction-house, a GPS will work somewhat in 20-50% of the rooms, working more often on the top floor and near windows. In a large building such as a major commercial location, conventional GPS receivers will not work at all. The SNR improvement of assisted GPS is enough to make GPS location work in most such environments; note that the details of implementation become most important in this aspect of assisted GPS: the percentage of buildings (and other obstructed sites) that can be covered varies dramatically with implementation details: in particular the hybrid approaches that use network data with GPS data greatly enhance in-building coverage. Table 1 is a GPS link budget for two scenarios.

Assisted GPS for Wireless Phone Location

141

Conventional GPS receivers typically integrate coherently over one

millisecond (one code period) and incoherently for six milliseconds and, consequently, have an acquisition threshold of (typically) –34 dB-Hz. Thus, a conventional GPS receiver can only acquire signals above approximately

-130 dBm. Weaker signals require more processing gain (longer integration) for successful acquisition. Knowing “true” GPS time at the mobile station and the approximate range to the satellite will enable the sensor to integrate

coherently over 20 milliseconds (one navigation bit period). Furthermore, if the network can predict (or obtain advance copies of) the bit sequence for some parts of the navigation message, the bit polarity can be sent to the MS to enable integrating coherently over multiple bits. This technique is known as “modulation wipeoff.” In addition to the sensitivity enhancement, knowing “true” GPS time at the MS reduces the time required to acquire the GPS signal for a given satellite. The serving BS sends information regarding the search window center and the search window size to the MS. Hence, the MS need only search a small window in the time

domain rather than the whole code space. Once the network makes a coarse estimate of the position of the MS, that estimate can be used to compute the

search window. Even if the uncertainty in the coarse estimate is as large as four miles, the search window size for a satellite at the horizon is only 20 chips, even less for satellites more directly overhead. This reduces search time per satellite compared with the case of no knowledge by a factor of 50. Search window size can be tightened substantially further if network data are used to estimate the position of the phone.

4.2

Time Required For A Location Fix

Typically, a conventional GPS receiver takes a long time (minutes) to provide a location fix when first turned on. This is because it has to search a large parameter space in order to find the signals from the

142

NEXT GENERATION WIRELESS NETWORKS

satellites that are currently visible and, once it has acquired the signals, it takes about 30s per satellite to obtain a full set of ephemeris from the 50-bps data. By contrast, in an assisted-GPS system all that

information is already available in the assisted-GPS server. In situations where a conventional GPS receiver has enough signal to operate, the assisted-GPS receiver will take only a fraction of a second to make the measurements and relay them to the assisted-GPS server. This is because, under such conditions, the integration time needs to be no longer than the 20-ms bit period. Thus, from the point of view of the human user, the location fix is nearly instantaneous. The actual time it takes to make the measurements depends on four parameters: – The integration time, which is determined by the available SNR

and can be as long as 1s to achieve maximum sensitivity. – The timing uncertainty, which determines how many different

PRN synchronizations must be tried. – The frequency uncertainty, which determines the Doppler frequency shift space that must be evaluated. – The number of correlation channels available in the assisted-GPS receiver. These parameters can be handled as follows:

Integration Time Initially, there is no way to know what SNR can be expected at the mobile receiver, so it makes sense to have the receiver first make a quick measurement with a short integration time, and then increase it progressively if no signal is detected. Timing Uncertainty If the receiver knows GPS time to within a few

microseconds, and it is given the navigation bits for “modulation wipeoff,” then it can coherently integrate beyond the 20 millisecond limit for conventional GPS receivers. Frequency Uncertainty Through simple calculations in the server, the Doppler shifts for each satellite can be calculated for the center of the cell and provided to the GPS receivers. By locking the receiver clocks to the base station’s clocks (which in the case of TIA/EIA-95 are also tied to GPS time) the mobile terminal frequency error can be minimized. Number of Channels The number of channels will determine the Time to First Fix (TTFF). We discuss this in terms of the number of correlators. To simultaneously detect, say, 5 satellites with 20 correlators, where the search window, as discussed above might be ±5 chips, one might use a half-chip search approach to find the correlation peak. Satellites would then be found sequentially. If 100 correlators were employed, all 5 satellites could be simultaneously located.

Assisted GPS for Wireless Phone Location

5.

143

STANDARDS COVERING ASSISTED GPS

U.S.-based service providers mandated by the FCC to provide E911 geolocation are free to deploy either proprietary or standards-based technology. Angle of Arrival, Reverse Link Time of Arrival, and other network-based systems are being considered and have the virtue of potentially working with legacy terminals. However, there is concern that to be fully deployed, these approaches require extensive build out of the infrastructure and the siting of new base stations to provide geometries good for triangulation. Considering cost, coverage, and accuracy needed to achieve FCC mandated performance, handset-based geolocation, and assisted GPS in particular, becomes very attractive. To ensure that many handsets and various networks work together, as well as to improve manufacturing efficiencies, standards are needed. Several standards bodies have been actively working to specify the messages, parameters, and procedures needed for interoperability among various proposals for assisted GPS. One of the first standards completed that was primarily aimed at supporting assisted GPS was TIA/EIA 1S801, which was published in final form in November, 1999 by the TR45.5 standards body. IS801 addresses both ANSI-95B and IS2000 (cdma2000). However, many of the techniques are applicable to all CDMA systems and the general concepts are applicable to other systems as well. TIA/EIA-136 TDMA, GSM, AMPS, although sometimes starting from different perspectives, have progressed to various stages of completeness, as shown in Table 2. Because GSM defines network and air interface standards together, while TIA’s TR committees for network-side and air interfaces are separate, resulting documents may appear quite different, but important similarities exist that underline the base technology. Perhaps because creation of the standards have been somewhat rushed, with standards committees having been strongly admonished about the need to complete their work in time for the FCC mandate, assisted-GPS standards may offer more options than would ideally be the case. The only way to reach rapidly obtain consensus was to accept all options that were contributed in a reasonably complete and timely way. The marketplace may eventually determine which options from assisted-GPS standards work best. For now, we describe the basics of each standard in the following sections, emphasizing IS801 as the most mature of the assisted-GPS standards. Note that Table 2 is labeled 2G/2G+; although there has been considerable, additional work done in 3G standards, that 3G work is beyond the scope of this document. Other standards are not covered here because they do not touch upon assisted GPS.

144

NEXT GENERATION WIRELESS NETWORKS

5.1

IS95 & IS2000 CDMA: The IS801 Standard

IS801 could be said to support three technologies: GPS (autonomous and assisted); Advanced Forward Link Triangulation (abbreviated AFLT; this is CDMA pilot phase measurement); and a Hybrid Technique combining GPS and AFLT. IS801 location reports use the specification shown in Table 3. Note all parameters except latitude and longitude are optional. We focus here on assisted GPS and review IS801 operations, which are shown in a simplified view in Figure 3.

Assisted GPS for Wireless Phone Location

145

Figure 3 shows a simple, three-step ping-pong diagram representing the basic operations for what can be regarded as the most common case of IS-801. The process begins with the network sending a request for location and assisting data. Several points are worth noting here: – IS801 specifies only over-the-air messages, leaving all network processing to other standards, such as the work now being done as PN-3890. Fig. 3 shows an actual Base Station, but note that IS801 uses the words “Base Station” to refer not only the Base Station itself, but to all network entities, including the MSC, PDE (Position Determining Entity), MPC (Mobile Positioning Center), SCP, etc. – Before the network sends a request for location as shown in Fig. 3, it may recognize that a call has been placed to 911, and resulting special handling calls for location to be determined. Alternatively, some other location-based application may have requested this mobile be located. – The first message sent performs two functions: requesting location and providing assistance: IS-801 calls for requests and responses and allows compound messages; thus the request for location can

146

NEXT GENERATION WIRELESS NETWORKS

be combined with assisting data for efficiency—just as the mobile receives the request to perform the location function, it also receives data that may be helpful in acquiring GPS signals. – The data returned may also include multiple parts, such as the GPS and pilot phase data shown in the second step here. – The last step (labeled optional) shows that the location result, or output as shown in Table 3, may be returned to the mobile, reflecting IS801’s consideration of location-based applications that are concluded at the mobile, rather than in the network. 5.1.1

Types of GPS Assistance in IS801

1S801 specifies three types of GPS assistance: acquisition assistance, location assistance, and sensitivity assistance. Each is described briefly here:

Acquisition assistance provides basic GPS information to enable mobiles to rapidly acquire GPS signals. Specifically, satellite IDs, Doppler shifts, and the timing of spreading codes is provided such that the acquisition of GPS signals, which could take several minutes in conventional receivers, is

reduced to seconds or fractions of seconds. Location assistance provides enough detailed information so a (properly equipped) mobile can compute its own location with the accuracy of differential GPS. The sequence of steps to use Location Assistance could be: – PDE estimates a rough location (e.g., cell/sector) for the mobile. – PDE predicts GPS signal at estimated location at a future time. – PDE conveys to MS a Location-Assistance Message containing: (a) the location estimate, and (b) the predicted GPS signal. – MS measures the discrepancy between the predicted and the observed GPS signal at the specified time. – MS computes its own location through simple, linear math. The key data for location assistance include: Elevation and azimuth angles of visible satellites, high-precision satellite Doppler shifts, and highprecision timing of spreading codes. An important alternative also supported by optional parameters of location assistance messages conveys GPS almanacs, almanac corrections, and ephemerides, thus enabling equivalent calculations to those implied by the above list.

Sensitivity assistance enables better penetration into buildings and faded environments, as well as certain lower-cost implementations, by conveying predicted GPS modulation bits and their associated timing to the mobile. The steps envisioned are: – PDE monitors periodic 50-bps modulation pattern of GPS signal.

Assisted GPS for Wireless Phone Location

147

– PDE predicts (or obtains advance copies of) future modulation bits.

– PDE conveys to MS the predicted bits (with their associated timing) and Doppler shift estimates. – MS applies predicted BPSK. modulation to received GPS signal (also called modulation wipeoff); received signal becomes pure carrier (BW=0 Hz). – Bandwidth reduction from ~50 Hz to 0 Hz allows MS to detect GPS signal with substantial sensitivity gain (10-17 dB). 5.1.2

Advanced Forward Link Trilateration (A-FLT) in IS801

As mentioned, IS801 also supports location by better enabling trilateration (also called triangulation) by having the mobile measure the offsets of pilots received from several Base Stations. Forward Link Trilateration (FLT) presents an attractive option to locate CDMA mobiles because only software changes would be needed—no new network hardware and no modified mobiles would be needed. Unfortunately FLT does not work well enough to satisfy accuracy and coverage requirements of important applications including E911, because of the coarseness of the chip resolution in ANSI-95 and ANSI-95’s power control imposing a regime where pilots from multiple Base Stations are too seldom “heard” by mobiles. AFLT is accomplished by sending: Base Station Almanacs – Giving the mobile base station locations and reference time correction. This supports position computations made at the mobile. Pilot Phase Measurements - Provides BS with forward link pilot phase measurements made by the MS. Position computation made at BS. The mobile also returns data on pilot offsets and pilot RMS errors, which relate to pilot strength. These data can be used to perform trilateration at the server.

5.1.3

Items Not Addressed in IS801

Several important items were discussed in the committee that wrote IS801, but were considered outside the scope of IS801, either because they are not part of the air interface or because they were not essential to basic functioning of assisted GPS. These items will, respectively, be considered by other standards bodies or in later versions of IS801. They include: – Location of idle-mode mobiles—services such as location-based billing require location of mobiles in the idle state, and some efficiencies can be gained over having mobiles on traffic channels by proper design of idle-mode operation. However, because this is

148

NEXT GENERATION WIRELESS NETWORKS

not needed for E911 services, idle mode operations are not now covered in IS801. – Network-Side Messaging— is outside the scope of IS801; however, message exchanges between PDE and Base Stations, MSC and location-based applications have been defined, and considerable work has been done on PN3890 in the TR45.2 organization.[14] In addition, there is new work to go beyond the FCC mandated requirements in Project Number PN4288.[15]

5.2

GSM Standards for Geolocation

Considerable work as also gone into the creation of the ETSI GSM standard for geolocation where several important new documents have just

been published. [16,17,18] This work, conducted by SMG3, in a European context, was not driven by the FCC mandate on accuracy or coverage, but

even so, these standards provide for a type of assisted GPS. This parallel development of the same fundamental technology is an indication of the broad technical appeal of assisted GPS. Of course, the GSM standard has options for many other geolocation

approaches, namely: – TOA – Time Of Arrival: Trilateralization by 3 or more base stations of the reverse link from the mobile terminal. Works with

legacy handsets but may require additional siting of infrastructure. – AOA –Angle of Arrival: Trilateralization by 2 or more base stations. This approach requires installation of substantial antenna and processing capabilities at well sited towers, but it works with legacy terminals. – Mobile Assisted E-OTD: The Enhanced - Observed Time Difference of Arrival method can be used by new terminals that can record the relative time of arrival of bursts from two BTSs or (in the case of nonsynchronized networks) three BTSs. The mobile provides the location server with the time measurements and the server computes the location of the MS with information about the

location and timing advance setting of each BTS involved. – Mobile Based E-OTD: E-OTD can be implemented with new mobiles collecting all information including the assistance data

concerning the location and timing advance information for each signal source. This requires new software/firmware but no new hardware, provided geometries are good. – Mobile Assisted GPS: This is fundamentally the same approach described throughout this paper. The differences are highlighted below but are not fundamental.

Assisted GPS for Wireless Phone Location

149

– Mobile Based GPS: In case of a high-end mobile, sufficient assistance information can be provided the terminal that it can calculate its location without providing the network any information other than its request for assistance. This capability would be particularly useful in a navigation application where a driver is given navigation information continuously, without burdening the network with a stream of assistance. – Conventional GPS: There is a provision in GSM 09.31 for a conventional GPS receiver that would communicate it’s position through the GSM network. While in contact with the network, it seems appropriate to use network resources to help improve the speed and accuracy of the GPS network, but one can still conceive of times in which having a high-end “backpacker’s” phone that can double as a GPS receiver even without contact to the base station would be useful. The primary differences between the assisted GPS approaches of GSM and CDMA are network difference including an network element, the LMU (Location Management Unit) that the GSM networks use for timing measurements and calibration through the coverage area. These LMUs may use the air interface to report these measurements to the location server so that they do not need extensive backhauling, but they do need to be situated where multiple LMUs are able to “see” most locations in the coverage area. They need to be situated where they provide good trilateralization over the field. Another difference between the GSM and CDMA approach is that the sensitivity assistance is not included per se. The expectation that it will be needed to meet the FCC mandate in indoor (highly faded) environments has led to some recent activity to include it in the North American version of the GSM standards effort (T1P 1.5). In that forum, some navigation bits are allowed to be used as part of the sensitivity assistance, particularly over the broadcast channel. It is likely that harmonization between the ETSI and T1P1 bodies will address this deficiency in future releases.

5.3

TDMA Standards for Geolocation

The ANSI organization TR45.3 has recently begun the standardization effort for the TIA/EIA-136 TDMA air interface, in working group 6 (TR45.3.6). As of this writing, TR45.3.6 has drafted a stage one document describing the requirements for geolocation, but it seems clear from earlier work done in the UWCC-corel36 organization that assisted GPS will be the sole standard method. Other methods might be used, but would not need standards support.

150

NEXT GENERATION WIRELESS NETWORKS

The TIA/EIA-136 wireless standard has a relatively narrowband RF channel of 30 kHz, which limits ones ability to transport good timing information. The Cramer-Rao formula gives the limit on the ability to measure a transition in time that is inversely proportional to bandwidth and Signal-to-Noise Ratio.

Unlike CDMA, the TDMA networks are often unsynchronized, which further complicates the task of calibrating the TDMA time. Consequently, the TDMA standards effort is calling for “timing calibrator” a network element similar to the Location Measurment Unit (LMU) defined in GSM standards, but with the sole function of reporting on the time relationship between GPS and TDMA time as measured in bits in time slots in frames and superframes. Figure 4 below shows the expected block diagram of components in the TDMA geolocation reference model. Unlike Figure 1, this includes the time calibrator function shown. Just as the LMU can be operated through

the air interface, so too, can the time calibrator in this model.

Assisted GPS for Wireless Phone Location

5.4

151

Analog/AMPS Standards for Geolocation

The ANSI organization TR45.1 in its Working Group 1 has endeavoured since midyear 1999 to standardize messaging required for geolocation in analog AMPS under project number PN4662. The work of that group is expected to be published in the Spring of 2000 as IS817. Key points of analog support for assisted GPS are: – Assistance information is conveyed through existing “blank-and-

burst” messaging mode. This means no hardware changes will be required to Base Stations. – Low bit rates that AMPS can accommodate (200-300 BPS) allow for only limited assistance—nothing like the Sensitivity Assistance of IS801. – “Hybrid” solutions, as described previously, are not possible without additional infrastructure changes. – Performance of assisted GPS in analog modes will likely be inferior to digital-mode by Decreased yield (decreased GPS sensitivity) Longer TTFF Nevertheless, assisted GPS in AMPS is expected to meet FCC mandate, when considered in conjunction with superior performance of digital-mode locations.

6.

SUMMARY OF BENEFITS

To summarize the key benefits that have been mentioned throughout this document, assisted GPS's advantages are: – Inexpensive, particularly for ANSI-95-CDMA terminals— Assisted-GPS terminals are expected to incorporate geolocation functions at the chip level, particularly in IS-95 terminals, which therefore might be made for only a few dollars per handset more than conventional terminals. The network-side equipment promises to be much less costly than alternative approaches. – Applicable to all air interfaces—although more straightforward for CDMA, as is reflected by the fact that IS801 standard was the first to be completed in support of this technology. – Differential GPS level of accuracy—particularly notable versus terrestrial triangulation systems seems unlikely to improve beyond 100 meter accuracy of so; assisted GPS should be an order of magnitude more accurate.

152

NEXT GENERATION WIRELESS NETWORKS

– Locations available in buildings and other heavily-faded situations—the major problem with using conventional GPS is overcome. – Little or no new hardware needed in Base Stations; no new connections between network elements – Rapid acquisition time-this is essential for emergency calling (911 calling).

7.

CONCLUSION

Other techniques that have been proposed to locate wireless phones|19]do not require any additional hardware in the phone itself. While the assistedGPS technique has the obvious disadvantage of requiring special-purpose hardware in the phone, it should be noted that the added hardware cost is

modest while the overall cost to the service provider is significantly reduced because, assisted GPS does not require modifications of all base stations. Indeed, the assisted-GPS server may be part of the Mobile Switching Center (MSC) or attached at even higher concentration levels of the wireless network and thus be shared by a very large number of base stations. Close scrutiny of the associated costs are necessary for a fair cost comparison; however, the main advantage of assisted GPS lies in its superior performance; other techniques are typically characterized by comparatively poor accuracy and limited availability[3,6,20,21] which makes them unsuitable for advanced location-based services.[1] The FCC currently requires service providers to locate 67% of E911 calls to within 100 meters or 50 meters depending upon whether network based or handset based technologies are used[22]. This recent rulemaking reflects a easing of requirements from the FCC's 1996 (NPRM)[23] that expressed a desire of the emergency services community to have wireless location provide an accuracy of 40 feet on 90% of all 911 calls, including a determination of altitude. While we believe that assisted GPS is the only approach that can

meet the current FCC requirements indoors, we are even more convinced that it is the only way to meet the intention of the original emergency services community request for 40 feet accuracy. We see few prospects that

this goal can be economically achievable by any other proposed technique.

ACKNOWLEDGEMENT Our sincere thanks to Dr. Samir Soliman of Qualcomm, Inc. for valuable input to this paper.

Assisted GPS for Wireless Phone Location

153

1

Mark Flolid, “Wireless Location Services,” NENANews (published by the NENA, the National Emergency Number Association), December 1998 page 17. 2 E. McCabe, “Start Now, Evolve to the Future,” Telephony, Volume 236, Number 22, May 31, 1999, page 36. 3 Elliot D. Kaplan, ed., Understanding GPS - Principles and Applications, Artech House, Boston (1996). 4 A. Brown/NAVSYS Corporation, “GPS Phone: An Integrated GPS/Cellular Handset,” issued at ION-GPS-97, The Institute of Navigation GPS-97 Conference, Kansas City, Missouri, September 16-19, 1997. Navsys Corp., 14960 Woodcarver Road, Colorado Springs, CO 80921. 5 Raymond DiEsposti, Steven Saks, Lubo Jocic, and Capt. Jordan Kayloe, “Of Mutual Benefit: Merging GPS and Wireless Communications,” GPS World, Volume 9, Number 4, April, 1998, page 44. 6 Mark Moeglin and Norman Krasner, “An Introduction to SnapTrack™ Server-Aided GPS Technology,” ION-GPS-98: Proceedings of the 11th International Technical Meeting of the Satellite Division of the Institute of Navigation, September 15-18. 1998, Nashville, Tennessee, page 333. 7 Norman Krasner, “Homing In On Wireless Location,” Jan, 2000, Communications Systems Design. 8 L.J. Garin, M. Chansarkar, S. Miocinovic, C. Norman, D. Hilgenberg, “Wireless Assisted GPS—SiRF Architecture and Field Test Results,” ION-GPS-99: Proceedings of the 12lh International Technical Meeting of the Satellite Division of the Institute of Navigation, September 14-17, 1999, Nashville, Tennessee, page 489. 9 A. R. Pratt, “Combining GPS and Cell Phone Handsets—The Intelligent Approach,” IONGPS-99: Proceedings of the 12th International Technical Meeting of the Satellite Division of the Institute of Navigation, September 14-17, 1999, Nashville, Tennessee, page 529. 10 J . J. Spilker, "Signal Structure and Performance Characteristics," Navigation, The Journal of the Institute of Navigation, Vol 25, Number 2, page 121. See also other articles within that issue of Navigation. 11 Elliot D. Kaplan, ibid., page 97. 12 Qualcomm, Inc. datasheets for MSM3300™ Mobile Station Mobile and gpsOne™ enhanced by SnapTrack; see http://www.qualcomm.com/ProdTech/asic/products/documents/MSMS3300.pdfand http://www.qualcomm.com/ProdTech/asic/products/documents/gpsOneSnapTrack.pdf 13

14

15

16

17

S. Tekinay, E. Chao, and B. Richton, “Performance Benchmarking in Wireless Location Systems,” IEEE Communications Magazine, Volume 36, Number 4, page 72, April, 1998. TR45:PN-3890, “Enhanced Wireless 9-1-1 Phase 2,” Rev. 13, February 15, 2000, Preballot Version TR45:PN4299, “Wireless Emergency Services Features Beyond FCC Mandates,” charter available online at: http://www.tiaonline.org/pubs/pulse/1998/pulse0998-7.cfm. ETSI GSM 03.71: “Digital cellular telecommunications system (Phase 2+); Location Services (LCS); (Functional description) - Stage 2 (GSM 03.71 version 7.2.1 Release 1998),” ETSI TS 101 724 V7.2 1 (2000-01), Published January 2000. (Available on line at: http://webapp.etsi.org/workprogram/Report_WorkItem.asp?WKI_ID=9269. ) ETSI GSM 04.31: “Digital cellular telecommunications system (Phase 2+); Location Services (LCS); Mobile Station (MS) – Serving Mobile Location Centre (SMLC) Radio Resource LCS Protocol (RRLP) (GSM 04.31 version 7.0.1 Release 1998),” ETSI TS 101

154

NEXT GENERATION WIRELESS NETWORKS

527 V7.0.1 (2000-01), Published January 2000. (Available on line at: http://webapp.etsi.org/workprogram/Report_ Workltem.asp?WKI_ID=9263). 18 ETSI GSM 09.31:“Technical Specification Digital cellular telecommunications system (Phase 2+); Location Services (LCS); Base Station System Application Part LCS Extension (BSSAP-LE) (GSM 09.31 version 7.0.0 Release 1998),” ETSI TS 101 530 V7.00 (2000-01), Published January, 2000. (Available on line at: http.//wehapp.etsi.org/workprogram/Report_Workltem.asp?WKI_ID=9217). 19 L. Stilp, “Time Difference of Arrival Technology for Locating Narrowband Wireless Signals,” Proceedings of the SPIE, Vol. 2602, October 25-26, 1995, pp. 134-144. 20 M J. Meyer, T. Jacobson, M. E. Palamara, E. A. Kidwell, R. E. Richton, G. Vannucci, “Wireless Enhanced 9-1-1 Service - Making it a Reality,” Bell Labs Technical Journal vol. 1, n. 2, Autumn 1996. 21 E. Benedetto, V. Biglieri, and V. Castellani, Digital Transmission Theory, Prentice Hall, Englewood Cliffs, NJ (1987). 22 Federal Communications Commission, CC Docket Number 94-102, Action by the Commission September 15, 1999, by Third Report and Order (FCC 99-245), released 23

October 6, 1999. Further information available at: http://www.fcc.gov/e911. Federal Communications Commission, CC Docket Number 94-102, Report and Order and

Further Notice of Proposed Rulemaking (FCC 96-264), adopted June 12, 1996; released July 26, 1996. Available at: http://www.fcc.gov/e911.

ABOUT THE AUTHORS Bob Richton is a member of technical staff in the Wireless Technology Applications Department at Lucent Technologies’ Bell Labs in Whippany, New Jersey. Since 1996, his work has focused mainly on systems engineering, architecture, and opportunity analysis for wireless E9-1-1 and other wireless geolocation applications. Mr. Richton has a B.S. degree in physics from the University of Massachusetts in Amherst, and an M.S. in physics and chemistry from the Stevens Institute of Technology in Hoboken, New Jersey. Giovanni Vannucci is a member of technical staff at Bell Labs in Holmdel, New Jersey. His primary responsibility is research in the area of wireless and portable communications. He also conducts research in microwave, satellite, and optical communications, light statistics, quantum electrodynamics, and visual psychophysics. Mr. Vannucci, a member of the American Association for the Advancement of Science and a senior member of the IEEE, received M.S. and Ph.D. degrees in electrical engineering from Columbia University in New York. He also has a doctor's degree in physics from the University of Pisa in Italy

Assisted GPS for Wireless Phone Location

155

Stephen Wilkus is a Technical Manager in the Wireless Technology Laboratory of Lucent Technologies. He received his MSEE degree from the University of Illinois, Urbana-Champaign, in 1981. After working as a

senior design engineer developing SAW devices and automated design software, he began work at AT&T Bell Labs in 1986. He has led the development of several low-cost radio systems for indoor wireless LAN and Electronic Shelf Labels a product currently being sold by NCR and has spearheaded several initiatives such as the development of the spectral etiquette approach to frequency allocation. He has authored several technical papers in IEEE publications and has presented invited talks in a number of International conferences and symposia, most recently at the ICM conference Wireless Positioning and Location Services Conference in London, March 6, 2000.

This page intentionally left blank.

Chapter 5 EVALUATION OF LOCATION DETERMINATION TECHNOLOGIES TOWARDS SATISFYING THE FCC E-911 RULING M.

Sunay

Bell Labs, Lucent Technologies 67 Whippany Road, Whippany, NJ 07981, USA [email protected]

Abstract

The recent FCC ruling has prompted the emergence of significant research on location determination technologies for wireless systems. Various technologies have been proposed in the literature. The wireless operators need to select a location determination technology that satisfies the FCC requirements and is most appropriate to their needs by October 2000. For this reason, proper evaluation techniques are necessary to make an extensive and fair comparison of the different technologies. This tutorial chapter gives an overview of the specifics of the FCC ruling and the different location determination technologies that are being considered by the wireless operators. A brief synopsis on how the individual location determination technologies may be evaluated is given in this chapter as well.

Keywords: E-911, Location Determination Technologies, Wireless Assisted GPS, Time Difference of Arrival, Angle of Arrival, Multipath Fingerprinting, Evaluation and Testing Criteria.

1.

INTRODUCTION

The concept of using a single emergency phone number to report any kind of emergency to a centralized reporting agency first originated in Britain. Other countries, including the United States, followed suit shortly thereafter. In the United States, interest for a nationwide emer-

158

NEXT GENERATION WIRELESS NETWORKS

gency number sparked in 1957 when the National Association of Fire Chiefs recommended the use of a nationwide single phone number for reporting fires [1]. In 1967, the President’s Commission of Law Enforcement and Administration of Justice recommended that a single number be established nationwide, solely for the purpose of reporting emergencies. With support from other Federal Government Agencies and various government officials, the President’s Commission on Civil Disorders turned to the Federal Communications Commission (FCC) for a solution. Later that year, FCC asked AT&T to find a means of establishing a universal emergency number that could be implemented quickly. In 1968, AT&T announced that it would use the three digits, 911, as the emergency code throughout the United States. 911 was selected because it was short and easy to remember. Furthermore, 911 had never been used as an area or service code and also met the long range numbering plans and switching configurations of AT&T. With recommendation from AT&T, FCC designated 911 as the only “Universal Emergency Number” for public use in the United States to request emergency assistance. On February 16th, 1968, Alabama Senator Rankin Fite became the first person to place a 911 call. In March of 1973, the Executive Office of the President issued a bulletin, endorsing the concept of 911 and urging its implementation nationwide. The bulletin also provided for the establishment of the Federal Information Center to assist units of government in the planning and implementation of 911 systems. In 1976, approximately 17% of the United States’ population had access to 911 services. In the early 1970’s, AT&T began the development of sophisticated features for the 911 system, paving the way for the Enhanced-911 (E-911) service. Today’s wireline E-911 service provides the PSAPs an automatic caller identification (ALI) in the form of caller’s name, phone number and address. Furthermore, ALI can be used to selectively route the 911 call to the proper PSAP which is normally closest to the scene. As of November 1999, nearly 92% of the population in the United States is covered by some type of 911 system [2]. However, the service footprint covers only 50% of the country’s physical landscape. The current 911 service coverage in the United States is mapped in Figure 5.1. Coverage percentages in the individual states are shown in the figure. The 1990s saw a tremendous growth in the acceptance and use of wireless systems throughout the world. In fact, in the United States alone, the number of wireless subscribers grew from 44 million to 67 million from 1996 to 1998. Needless to say, provision of the E-911 service to wireless users is now a necessity. Statistics show that as high as 25% of all 911 calls made in the last year have originated from a mobile phone.

Evaluation of Location Determination Technologies

159

Furthermore, wireless subscribers identify the ability to be able to call 911 from wherever they are as one of the very important factors influencing their decision in subscribing to a wireless service [3]. However,

unlike most wireline phones in the United States, which have access to the E-911 service that automatically reports the caller’s location, when a 911 call is placed using a mobile station, currently the dispatcher at the 911 Public Safety Answering Point (PSAP) does not know where the caller is and the wireless users who dial 911 usually cannot describe

their exact location. On June 12, 1996, the Federal Communications Commission (FCC) adopted a Report and Order which established performance goals and timetables for the identification of the wireless caller’s phone number and physical location when dialing the 911 emergency services telephone number [4]. The FCC requirements have boosted much research in Location Determination Technologies (LDTs). Various different technologies have appeared in the literature. These technologies may be grouped into three general categories: Mobile Station Based LDTs, Network Based LDTs and Hybrid Methods. This chapter is intended to give an overview of the LDTs that have been proposed in the literature as possible solutions to the FCC requirements. A detailed summary of the FCC ruling on wireless E-911 is given next in this chapter. Overviews of the Mobile Station Based,

160

NEXT GENERATION WIRELESS NETWORKS

Network Based and Hybrid LDTs follow. Evaluation criteria and evaluation methods to compare these different technologies is briefly outlined in this chapter as well.

2.

FCC RULING ON E-911 FOR WIRELESS SYSTEMS

To improve public safety and extend ALI to wireless callers, the FCC established a ruling, subject to certain conditions, for deployment of E911 features by wireless carriers [4]. In Phase I, which began on April 1, 1998, the wireless operators were required to forward the 911 calls from mobile phones to a PSAP without any interception for any validation procedures or credit checks. Additionally, analogous to the wireline E-911 service, the wireless operators were required to relay the caller’s telephone number and the location of the base station or cell site receiving the 911 call. According to the June 12 ,1996 ruling, in Phase II, scheduled for October 1, 2001, wireless operators were required to provide a much more precise location identification, within 125 meters, of the caller’s location to the PSAPs in 67 percent of all cases. The need for the Phase II requirement stemmed from how wireless systems operate.

In a practical wireless system, due to the imperfections of the mobile radio transmission terrain or network congestion, the base station that processes the 911 call need not necessarily be the closest to where the call is actually placed. With the Phase II implementation, ALI may be applied to route these calls immediately to the proper PSAP, normally one that is nearest the mobile station, not nearest the serving base station. In wireless systems, once Phase II is implemented, ALI may also help PSAPs deal with sudden bursts of calls, which often occur after incidents such as highway accidents. Knowing the location of the incoming calls, the PSAP can better distinguish redundant calls about a particular accident from calls concerning a different emergency. Since the 1996 ruling a variety of LDT proposals surfaced. While some of these proposals required hardware changes to the mobile stations, others did not. Clearly, though they might be more accurate, LDTs that require hardware changes to the mobile stations will potentially delay

the full availability of the Phase II ruling. FCC, taking this into account, recently revised its Phase II ruling [5]. According to the October 6, 1999 ruling, FCC now requires that LDTs requiring mobile station hardware modifications be held to a higher accuracy standard than the LDTs that do not require such modifications. Allowing a rapid phase-in implementation, FCC requires that for such LDTs, the modified mobile stations be made available earlier than the current October 1, 2001 de-

Evaluation of Location Determination Technologies

161

ployment date. Additionally, wireless carriers employing mobile station based LDTs take additional steps to provide location information for roamers and callers with legacy mobile stations. FCC also replaced the RMS reliability methodology with a simpler statistical measure. The 1999 ruling sets levels of accuracy that must be achieved for 67 percent and 95 percent of all calls. The revised ruling now allows the wireless carriers to reach a 50 percent LDT coverage within six months of a PSAP request for Phase II services and 100 percent coverage eighteen months after a PSAP request. Specifically, requirements are placed in three categories [5]: 1. Decision for Technology Adoption: Wireless carriers are required to report the LDT (or LDTs) of their choice to FCC by October 1, 2000. 2. Deployment Requirements:

(a) LDTs Requiring New, Modified or Upgraded Mobile Stations: Regardless of whether there is a PSAP request for Phase

II implementation, – The ALI-capable mobile stations need to be made available to the public by no later than March 1, 2001. – By October 1, 2001, at least 50 percent of all new mobile stations activated need to be ALI-capable. – By October 1, 2001, at least 95 percent of all new digital mobile stations activated need to be ALI-capable. Specifically, once a PSAP request is received for a Phase II implementation, – Within six months of the request or by October 1, 2001, whichever is later, * The wireless operator needs to ensure that 100 percent of all new mobile stations activated are ALIcapable. * The wireless operator needs to implement any necessary network upgrades to ensure proper operation.

* The wireless operator needs to begin delivering to the PSAP the location information that satisfies the Phase II requirements. — Within two years of the request or by December 31, 2004, whichever is later, the wireless operator needs

162

NEXT GENERATION WIRELESS NETWORKS

to strive for 100 percent penetration of ALI-capable mobile stations in its total subscriber base. The wireless operators need to support a minimum of Phase I requirements for roamers and other callers without ALI-capable mobile stations. For users with modified mobile stations, roaming among different wireless operators employing the same LDT needs to be allowed.

(b) LDTs Not Requiring New, Modified or Upgraded Mobile Stations:

The wireless operators need to deploy Phase II to 50 percent of callers within 6 months of a PSAP request. The wireless operators need to deploy Phase II to 100 percent of callers within 18 months of a PSAP request.

3. Accuracy: (a) LDTs Not Requiring New, Modified or Upgraded Mobile Stations: An accuracy of 100 meters for 67 percent of calls and 300 meters for 95 percent of calls needs to be maintained.

(b) LDTs Requiring New, Modified or Upgraded Mobile Stations: An accuracy of 50 meters for 67 percent of calls and 150 meters for 95 percent of calls needs to be maintained.

3.

LOCATION DETERMINATION TECHNOLOGIES

A variety of technologies are available for accurate location determination. These technologies may be grouped based on where the measurements towards location estimation are made in the system. LDTs that

use radiolocation measurements performed only by the mobile station can be grouped under the class, Mobile Station Based Methods. Similarly, LDTs that use radiolocation measurements performed only by the base stations can be grouped under the class, Network Based Methods. LDTs that utilize radiolocation measurements performed at both the mobile station and the base stations can be grouped under the class, Hybrid Methods [6]. Note that even though this classification is made based on where the radiolocation measurements are performed, it does not specify where the actual location estimation calculations are made. That is, a Mobile Station Based Method, where the measurements towards the location estimation are performed by the mobile station, may have the calculations done either at the mobile station, at the network

Evaluation of Location Determination Technologies

163

or both. Under the current classification all such alternatives fall under the same category.

3.1

MOBILE STATION BASED METHODS

Broadly defined, a mobile station based LDT is one that detects and processes signal(s) transmitted from multiple base stations and/or satellites. Specifically, such methods may be divided into three subcategories:

3.1.1 MS Based Methods Using Wireless System Signals. The location determination technologies that use signals transmitted by base stations serving the system to perform algorithms fall into this category. Theoretically, the position of a receiver can be estimated from the measurements of the arrival times, directions of arrival, or Doppler shifts of electromagnetic waves sent by various transmitters whose exact locations are known. If the arrival times are known, the distances between the individual transmitters and the receiver are also known. Suppose that we know the distance, d, between a single base station and the mobile station whose location is to be found. As can be seen from Figure 5.2, this knowledge narrows down all possible locations the mobile station could be to the surface of a sphere that is centered around the base station and has a radius of d. Suppose next that the distance between a second base station and the mobile station is also known. It is then possible to draw two spheres, each centered around one of the two base stations. The mobile station has to be somewhere on the circle where the two spheres intersect as seen in Figure 5.3. From Figure 5.4, if the distance of the mobile station from a third base station is known as well, the position estimation region narrows down to only two points where the three spheres intersect. In order to decide between the two intersection points, a fourth measurement could be made. In practice however, usually one of the two

164

NEXT GENERATION WIRELESS NETWORKS

points is an improbable solution and can be rejected without a measurement. Following this reasoning, forward link hyperbolic location systems, often called forward link time difference of arrival (TDOA) systems, locate a mobile station by processing signal arrival-time measurements from three or more base stations. The arrival time measurements from two base stations are combined to produce a relative arrival time that, in the absence of noise and interference, restricts the possible mobile location to a hyperboloid with the two stations as foci. Mobile station location is estimated from the intersection of two or more hyperboloids determined from at least three base stations. In the current TIA/EIA-95 based CDMA networks, all base stations continually transmit pilot signals which amount to approximately 20% of the total transmitted power. Therefore, forward link time difference of arrival algorithms are readily applicable to TIA/EIA-95 systems, where the relative arrival times of three or more pilot signals emanating from different base stations are used for the mobile station location estimation.

Evaluation of Location Determination Technologies

165

The requirement for the forward link TDOA to work is for the mobile station to detect signals from at least three base stations in a tightly synchronized network. The relative arrival times of the signals from the visible base stations are then used to form hyperboloids, the intersection of which gives us the location estimates. If there is information from more than base stations, it is possible to form more than two hyperboloids and find the intersection of all of the hyperboloids. As in Figure 5.5, assume that the coordinates of the three base stations are known. Without any loss of generality, one can form local coordinates where the first base station, BS# 1 is centered at the origin and the second base station, BS# 2 is somewhere along the local y-axis. The local coordinates of the third base station, BS# 3 and the mobile station, MS can then easily be defined relative to those of BS# 1 and BS# 2. In other words, assume that the coordinates of the three base stations are as follows:

Furthermore, assume that the mobile station is located at, Then, the distances between the mobile station and each of the base stations can be calculated using,

166

NEXT GENERATION WIRELESS NETWORKS

where and are the time it takes for the signals (Pilot Signals in the case of TIA/EIA-95) to travel from BS# 1, BS# 2 and BS# 3 to the MS, respectively and c is the speed of light. Now, for the 1.2288 MHz TIA/EIA-95 system, the arrival times can be described in terms of PN chip offsets using the following ratio,

where PN — OFFi is the offset between the actual PN chip of the i’th base station (which is the base station identification) and its measured counterpart. The TDOA algorithm draws two hyperboloids using,

The above two equations have two unknowns, x and and are known from the base station GPS coordinates and as well as is measured and thus and are known as well. The two equations in (5.5) and (5.6) can be solved in many different ways. They can be solved iteratively using the Steepest Descent Method, or visually by plotting the hyperboloids, using Taylor series expansion etc. It is also possible to solve the set of equations analytically (for a two-dimensional solution) since it is possible to reduce the problem to the solution of a quadratic equation [7, 8]. For a three-dimensional solution, the problem becomes a quartic equation whose analytical solution, though algebraically more complicated, is still available. Taking the squares of both sides of the equalities in (5.5) and (5.6) yields,

Provided that

is not equal to zero we can write,

Evaluation of Location Determination Technologies

167

One can re-write (5.9) as,

where

Now, substituting (5.10) into (5.7) results in

which results in

(5.14) is a quadratic equation whose roots give the two coordinates of the intersection points of the hyperboloids. The corresponding x coordinates may be found using (5.10). In an ideal world, where there are no detection errors, no multipath and non-line-of-sight propagation and perfect synchronization amongst the base stations, the TDOA algorithm will always converge to the true mobile position. In the wireless channel none of these conditions hold. Multipath propagation is prevalent and especially in urban areas, there is a very high probability that most of the received multipaths will be nonline-of-sight. Synchronization errors and detection errors (measurement errors) are also present. All such impairments cause errors in the location estimation algorithm. The existence of multipath causes errors in the timing estimates even when there is a line-of-sight path between the base station and the mobile station. Conventional delay estimators such as the delay locked loop, are influenced by the presence of multipath especially when the multipath signals arrive within a chip period of one another [9]. When the first arriving multipath is less powerful than those

arriving later, the delay estimators detect a delay in the vicinity of the more powerful multipath signals. The non-line-of-sight propagation, on the other hand, introduces a bias in the TDOA measurement because the signal arriving at the mobile station from the base station is reflected and thus takes a longer path relative to the line-of-sight path. The presence of multiple access interference also influences the accuracy of

TDOA systems. Analogous to the multipath propagation effects, the

168

NEXT GENERATION WIRELESS NETWORKS

existence of multiple access interference deteriorates the performance of the delay estimators. If the base station signals follow a direct line of path, and if the signal arrival times can be detected exactly, the TDOA approach always gives the true mobile location. This ideal case is illustrated for a specific example in Figure 5.6. In this case, the true mobile location lies on one of the intersection points. Figure 5.7, on the other hand, represents a

situation where all possible impairments are present. In both figures the represents the locations of the base stations and the ’o’ represents the calculated mobile station location. In Figure 5.7, the solid curves are the hyperboloids drawn when impairments are present in the system and the dotted curves are the hyperboloids if there were no impairments, i.e., if a genie were to tell us the true distances between the mobile and

all three base stations. The ‘o’ represents the estimated mobile location whereas the represents the true mobile location.

The relative geometry of the base stations performing the TDOA measurements is critical in the performance of the TDOA algorithm. Poor

geometry can lead to high geometric dilution of precision (GDOP). If the geometry of the three base stations performing the TDOA measurements is such that the intersecting hyperboloids intersect at a very small

Evaluation of Location Determination Technologies

169

angle, significant estimation errors are observed even with the slightest of impairments. If on the other hand, the hyperboloids intersect at almost right angles, the impairments present in the system translate to small offsets from the true location.

3.1.2 MS Based Methods Using Satellite Signals. The location determination technologies that use signals transmitted by a number of satellites to perform algorithms fall into this category. Note that here,

technologies make use of only the satellite signals for location determination. Each mobile station needs to be furnished with a stand alone satellite receiver in this case. The Global Positioning System (GPS) is a worldwide radio-navigation system formed from a constellation of 24 satellites, each 11,000 nautical miles above the Earth, arranged in 6 orbital planes with 4 satellites per plane as shown in Figure 5.8 [12]. The constellation is designed so that signals from at least six satellites may be received nearly 100% of the time from any non-obstructed place on earth. The GPS satellites each take 12 hours to orbit the earth. Each satellite is furnished with an atomic clock that keeps accurate time to within three nanoseconds so it can broadcast its information signals coupled with a precise timing

170

NEXT GENERATION WIRELESS NETWORKS

message. In this regard, the GPS system can also be used as an accurate timing reference. A global network of ground stations monitor the condition of the satellites. Five stations exist: Hawaii and Kwajelein in the Pacific Ocean, Diego Garcia in the Indian Ocean, Ascension Island in the Atlantic Ocean and Colorado Springs in the continental USA. This network regularly uploads navigation information an