Handbook of Wireless Networks and Mobile Computing, Edited by Ivan Stojmenovic ? Copyright © 2002 John Wiley & Sons, Inc. ISBNs: 0-471-41902-8 (Paper); 0-471-22456-1 (Electronic) HANDBOOK OF WIRELESS NETWORKS AND MOBILE COMPUTING WILEY SERIES ON PARALLEL AND DISTRIBUTED COMPUTING Series Editor: Albert Y. Zomaya Parallel and Distributed Simulation Systems / Richard Fujimoto Surviving the Design of Microprocessor and Multimicroprocessor Systems: Lessons Learned / Veljko Milutinovic ?

Mobile Processing in Distributed and Open Environments / Peter Sapaty Introduction to Parallel Algorithms / C. Xavier and S. S. Iyengar Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences / Albert Y. Zomaya, Fikret Ercal, and Stephan Olariu (Editors) New Parallel Algorithms for Direct Solution of Linear Equations / C. Siva Ram Murthy, K. N. Balasubramanya Murthy, and Srinivas Aluru Practical PRAM Programming / Joerg Keller, Christoph Kessler, and Jesper Larsson Traeff Computational Collective Intelligence / Tadeusz M.

Szuba Parallel and Distributed Computing: A Survey of Models, Paradigms, and Approaches / Claudia Leopold Fundamentals of Distributed Object Systems: A CORBA Perspective / Zahir Tari and Omran Bukhres Pipelined Processor Farms: Structured Design for Embedded Parallel Systems / Martin Fleury and Andrew Downton Handbook of Wireless Networks and Mobile Computing / Ivan Stojmenovic (Editor) ? HANDBOOK OF WIRELESS NETWORKS AND MOBILE COMPUTING Edited by Ivan Stojmenovic ?

University of Ottawa Universidad Nacional Autonoma de Mexico A WILEY-INTERSCIENCE PUBLICATION JOHN WILEY & SONS, INC. Designations used by companies to distinguish their products are often claimed as trademarks. In all instances where John Wiley & Sons, Inc. , is aware of a claim, the product names appear in initial capital or ALL CAPITAL LETTERS. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration. Copyright © 2002 by John Wiley & Sons, Inc.

All rights reserved No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic or mechanical, including uploading, downloading, printing, decompiling, recording or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without the prior written permission of the Publisher. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc. 605 Third Avenue, New York, NY 10158-0012, (212) 850-6011, fax (212) 850-6008, E-Mail: PERMREQ @ WILEY. COM. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold with the understanding that the publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional person should be sought. ISBN 0-471-22456-1 This title is also available in print as ISBN 0-471-41902-8.

For more information about Wiley products, visit our web site at www. Wiley. com. Contents Contributors Preface 1 Handoff in Wireless Mobile Networks Qing-An Zeng and Dharma P. Agrawal 1. 1 1. 2 1. 3 1. 4 1. 5 1. 6 Introduction Types of Handoffs Handoff Initiation Handoff Decision Handoff Schemes Summary References xiii xvii 1 1 1 2 4 4 24 24 27 2 Location Management in Cellular Networks Jingyuan Zhang 2. 1 2. 2 2. 3 2. 4 2. 5 2. 6 Introduction Cellular Networks Location Management Common Assumptions or Performance Evaluation Location Management Schemes Summary Acknowledgments References 27 27 29 30 34 46 47 47 51 3 Heuristics for Solving Fixed-Channel Assignment Problems Harilaos G. Sandalidis and Peter Stavroulakis 3. 1 3. 2 3. 3 3. 4 3. 5 Introduction Resource Management Tasks Interference in Cellular Systems Frequency Management and Channel Assignment Issues Channel Assignment 51 51 52 54 56 v vi CONTENTS 3. 6 3. 7 3. 8 3. 9 Fixed-Channel Assignment Problem Heuristic Techniques for Combinatorial Optimization Heuristic FCA Schemes Conclusions References 7 60 62 67 67 71 4 Channel Assignment and Graph Multicoloring Lata Narayanan 4. 1 4. 2 4. 3 4. 4 4. 5 4. 6 4. 7 Introduction Preliminaries Basic Types of Algorithms Lower Bounds The Static Case The Online Case Discussion and Open Problems References 71 74 77 78 82 90 91 92 95 5 Channel Assignment and Graph Labeling Jeannette C. M. Janssen 5. 1 5. 2 5. 3 5. 4 Introduction Lower Bounds Algorithms Conclusions and Open Problems Acknowledgments References 95 99 104 114 115 115 119 6 Wireless Media Access Control Andrew D. Myers and Stefano Basagni 6. 6. 2 6. 3 6. 4 6. 5 6. 6 6. 7 Introduction General Concepts Wireless Issues Fundamental MAC Protocols Centralized MAC Protocols Ad Hoc MAC Protocols Summary References 119 119 123 124 127 130 141 142 7 Traffic Integration in Personal, Local, and Geographical Wireless Networks 145 Raffaele Bruno, Marco Conti, and Enrico Gregori 7. 1 Introduction 7. 2 A Technology for WPAN: Bluetooth 7. 3 Technologies for High-Speed WLANs 145 147 153 CONTENTS vii 7. 4 Third-Generation Cellular Systems: UMTS Acknowledgments References 160 168 168 171 Fair Scheduling in Wireless Packet Data Networks Thyagarajan Nandagopal and Xia Gao 8. 1 8. 2 8. 3 8. 4 8. 5 Introduction Models and Issues Wireless Fair Queueing Architecture Algorithms for Wireless Fair Queueing Issues and Future Directions References 171 172 180 186 190 193 195 9 Randomized Initialization Protocols for Radio Networks Koji Nakano and Stephan Olariu 9. 1 9. 2 9. 3 9. 4 9. 5 9. 6 9. 7 9. 8 Introduction State of the Art A Refresher of Basic Probability Theory Energy-Efficient Prefix Sums Protocols Initializing a Single-Channel RN Initializing a k-Channel RN

Energy-Efficient Initialization Protocols Concluding Remarks and Open Problems Acknowledgments References 195 197 198 200 202 207 208 215 216 216 219 10 Leader Election Protocols for Radio Networks Koji Nakano and Stephan Olariu 10. 1 10. 2 10. 3 10. 4 10. 5 10. 6 Introduction A Brief Refresher of Probability Theory Oblivious Leader Election Protocols Uniform Leader Election Protocols Nonuniform Leader Election Protocol Concluding Remarks and Open Problems Acknowledgments References 219 222 224 227 234 240 241 241 243 11 Data Broadcast Jianliang Xu, Dik-Lun Lee, Qinglong Hu, and Wang-Chien Lee 11. 11. 2 11. 3 Introduction Data Scheduling Air Indexing 243 245 253 viii CONTENTS 11. 4 11. 5 Other Issues Summary Acknowledgments References 260 262 262 263 267 12 Ensemble Planning for Digital Audio Broadcasting Albert Graf and Thomas McKenney 12. 1 12. 2 12. 3 12. 4 12. 5 12. 6 Introduction The Ensemble Planning Problem Basic Solution Techniques Lower Bounds A Tabu Search Method Conclusion Acknowledgments References 267 268 271 273 274 286 287 287 289 13 Transport over Wireless Networks Hung-Yun Hsieh and Raghupathy Sivakumar 13. 1 13. 2 13. 3 13. 4 13. Introduction Overview of TCP TCP over Wireless Networks Approaches to Improve Transport Layer Performance Summary References 289 291 293 297 306 307 309 14 Security and Fraud Detection in Mobile and Wireless Networks Azzedine Boukerche 14. 1 14. 2 14. 3 14. 4 14. 5 14. 6 14. 7 14. 8 14. 9 Introduction Network Security Problems Network Security Management Plan Intrusion Detection Systems (IDS) Securing Data Transfer in Digital Mobile Systems Securing Wireless Ad Hoc Networks Authentication of Mobile Users Subscription and Fraud Detection in Mobile Phone Systems Conclusion References 09 310 311 311 312 313 315 317 321 322 325 15 Mobile Ad Hoc Networks Silvia Giordano 15. 1 15. 2 Introduction Layered Architecture of Mobile Ad Hoc Networks 325 327 CONTENTS ix 15. 3 15. 4 15. 5 15. 6 15. 7 MAC Layer Mobile Ad Hoc Networks and the Internet Routing in Self-Organized Networks People-Based Networks Conclusion Acknowledgments References 331 335 339 341 342 343 343 347 16 Broadcast Scheduling for TDMA in Wireless Multihop Networks Errol L. Lloyd 16. 1 16. 2 16. 3 16. 4 16. 5 16. 6 16. 7 Introduction What Is Broadcast Scheduling?

The Complexity of Broadcast Scheduling Centralized Algorithms Distributed Algorithms Related Results Summary and Open Problems Acknowledgments References 347 347 351 352 359 366 368 368 368 371 17 Mobile Ad Hoc Networks and Routing Protocols Yu-Chee Tseng, Wen-Hua Liao, and Shih-Lin Wu 17. 1 17. 2 17. 3 17. 4 17. 5 17. 6 17. 7 Introduction Unicast Routing Protocols for MANET Broadcasting Protocols for MANET Multicasting Protocols for MANET QoS Routing Extending Cellular Systems with Ad Hoc Links Conclusions Acknowledgments References 71 372 381 383 385 389 390 391 391 393 18 Routing with Guaranteed Delivery in Geometric and Wireless Networks Jorge Urrutia 18. 1 18. 2 18. 3 18. 4 Introduction Applications to Ad Hoc Wireless Communication Networks Delaunay Triangulations Conclusions Acknowledgments References 393 401 403 404 404 404 x CONTENTS 19 Power Optimization in Routing Protocols for Wireless and Mobile Networks Stephanie Lindsey, Krishna M. Sivalingam, and Cauligi S. Raghavendra 19. 1 19. 2 19. 3 19. 4 19. 5 19. 6 19. 7 19. Introduction Background Energy Analysis of AODV and DSR Routing Protocols Power-Aware Routing Metrics Routing Based on Balanced Energy Consumption of Nodes Broadcast and Multicast Tree Construction Topology Control Using Transmit Power Adjustment Summary Acknowledgments References 407 407 408 409 413 417 418 419 421 421 421 425 20 Dominating-Set-Based Routing in Ad Hoc Wireless Networks Jie Wu 20. 1 20. 2 20. 3 20. 4 20. 5 Introduction Preliminaries Formation of a Connected Dominating Set Extensions Conclusions and Future Directions Acknowledgments References 425 427 431 438 447 448 448 451 1 Location Updates for Efficient Routing in Ad Hoc Networks Ivan Stojmenovic ? 21. 1 21. 2 21. 3 21. 4 21. 5 21. 6 21. 7 21. 8 21. 9 Introduction Classification of Routing Algorithms Location Updates Between Neighboring Nodes Request Zone Routing Doubling Circles Routing Quorum-Based Strategies Home-Agent-Based Strategy Performance Evaluation Issues Conclusion References 451 452 457 458 459 460 463 465 468 468 473 22 Topological Design, Routing, and Handover in Satellite Networks Afonso Ferreira, Jerome Galtier, and Paolo Penna 22. 1 22. 2 Introduction Topologies 473 473 CONTENTS xi 2. 3 22. 4 22. 5 Network Mobility and Traffic Modeling Routing and Handover Conclusions Acknowledgments References 478 484 491 491 491 495 23 Multicasting: From Fixed Networks to Ad Hoc Networks Thomas Kunz 23. 1 23. 2 23. 3 23. 4 23. 5 23. 6 23. 7 Introduction Motivation Multicasting in Fixed/Wired Networks Multicasting in Fixed Infrastructure Cellular Networks Multicasting in Mobile Ad Hoc Networks: Adopting Wireless Protocols Multicasting in Mobile Ad Hoc Networks: MANET-Inspired Multicast Protocols Conclusions Acknowledgments References 495 495 497 497 500 502 506 508 508 509 4 Broadcasting in Radio Networks Andrzej Pelc 24. 1 24. 2 24. 3 24. 4 24. 5 24. 6 Introduction Communication Scenarios The Graph Model The Geometric Model Other Variants of the Problem Conclusion and Open Problems Acknowledgments References 509 510 512 519 521 525 526 526 529 25 Mobile IP Protocols Christos Douligeris and Thanos Vasilakos 25. 1 25. 2 25. 3 25. 4 25. 5 25. 6 25. 7 25. 8 Introduction Mobility Requirements and Constraints in an IP Environment Mobile IP Protocol Overview Route Optimization Mobility Support for IPv6 Connectivity with 3G Networks Management of Information Bases Conclusions References 29 530 531 544 546 547 549 550 551 xii CONTENTS 26 Data Management in Wireless Mobile Environments Sandeep K. S. Gupta and Pradip K. Srimani 26. 1 26. 2 26. 3 26. 4 26. 5 26. 6 26. 7 26. 8 Introduction Data Management Issues in Mobile Environments Caching of Data An Informal Overview Formal Description of the Scheme Performance Analysis Performance Comparison Summary Acknowledgments References 553 553 555 555 557 564 566 570 574 578 578 581 27 Mobile, Distributed, and Pervasive Computing Michel Barbeau 27. 1 27. 2 27. 3 27. 27. 5 Introduction Pervasive Computing Applications Architecture of Pervasive Computing Software Open Protocols Summary Acknowledgments References 581 582 583 584 598 599 599 601 28 Indoor Wireless Environments Lakshmi Ramachandran 28. 1 28. 2 28. 3 28. 4 28. 5 28. 6 28. 7 Introduction The Physical Layer Media Access Control Network Topology Characterization of the Environment Challenges for the Future: Nomadic Computing Summary Acknowledgments References 601 602 604 615 620 621 621 621 622 625 Index Contributors Dharma P.

Agrawal, University of Cincinnati, Department of Electrical Engineering and Computer Science, Cincinnati, Ohio 45221 Michel Barbeau, Carleton University, School of Computer Science, Ottawa, Ontario KIS 5B6, Canada Stefano Basagni, University of Texas at Dallas, Department of Computer Science, Richardson, Texas 75083 Azzedine Boukerche, University of North Texas, Department of Computer Science, Denton, Texas 762034 Raffaele Bruno, Consiglio Nazionale delle Ricerche (CNR), Istituto CNUCE, 56010 Ghezzano, Pisa, Italy Marco Conti, Consiglio Nazionale delle Ricerche (CNR), Istituto CNUCE, 56010 Ghezzano, Pisa, Italy Christos Douligeris, Institute of Computer Science, FORTH, Heraklion, Crete, Greece Afonso Ferreira, CNRS Mascotte, 13S INRIA Sophia Antipolis, BP 93, F-06902 Sophia Antipolis Cedex, France Jerome Galtier, France Telecom R&D and CNRS Mascotte, 13S INRIA Sophia Antipolis, BP 93, F-06902 Sophia Antipolis Cedex, France Xia Gao, University of Illinois at Urbana-Champaign, Coordinated Science Laboratory, Urbana, Illinois 61801 Silvia Giordano, Swiss Federal Institute of Technology, Institute of Computer Communications and Applications, CH-1015 Lausanne, Switzerland Albert Graf, Johannes Gutenberg University, Department of Music Informatics, 55099 Mainz, Germany xiii xiv CONTRIBUTORS Enrico Gregori, Consiglio Nazionale delle Ricerche (CNR), Istituto CNUCE, 56010 Ghezzano, Pisa, Italy Sandeep K. S. Gupta, Arizona State University, Department of Computer Science and Engineering, Tempe, Arizona 85287 Hung-Yun Hsieh, Georgia Institute of Technology, School of Electrical and Computer Engineering, Atlanta, Georgia 30332 Qinglong Hu, IBM Almaden Research Center, San Jose, California Jeannette C. M.

Janssen, Dalhousie University, Department of Mathematics and Statistics, Halifax, Nova Scotia B3H 3J5, Canada Thomas Kunz, Carleton University, Systems and Computer Engineering, Ottawa, Ontario K1S 5B6, Canada Dik-Lun Lee, Hong Kong University of Science and Technology, Department of Computer Science, Clear Water Bay, Hong Kong Wang-Chien Lee, Verizon Laboratories, Waltham, Massachusetts Wen-Hua Liao, National Central University, Department of Computer Science and Information Engineering, Tao-Yuan, Taiwan Stephanie Lindsey, Washington State University, School of Electrical Engineering and Computer Science, Pullman, Washington 99l64 Errol L. Lloyd, University of Delaware, Department of Computer Science and Information Sciences, Newark, Delaware 19716 Andrew D.

Myers, University of Texas at Dallas, Department of Computer Science, Richardson, Texas 75083 Thomas McKenney, Johannes Gutenberg University, Department of Music Informatics, 55099 Mainz, Germany Koji Nakano, Japan Advanced Institute for Science and Technology Thyagarajan Nandagopal, University of Illinois at Urbana-Champaign, Coordinated Science Laboratory, Urbana, Illinois 61801 Lata Narayanan, Concordia University, Department of Computer Science, Montreal, Quebec H3G 1M8, Canada CONTRIBUTORS xv Stephan Olariu, Old Dominion University, Department of Computer Science, Norfolk, Virginia 23529 Andrzej Pelc, Unversite du Quebec a Hull, Departement d’Informatique, Hull, Quebec J8X 3X7, Canada Paolo Penna, CNRS Mascotte, 13S INRIA Sophia Antipolis, BP 93, F-06902 Sophia Antipolis Cedex, France Cauligi S. Raghavendra, University of Southern California, Department of Electrical Engineering, Los Angeles, California 90089 Lakshmi Ramachandran, Trillium Digital Systems, International Tech Park, Bangalore 560 066, India Harilaos G. Sandalidis, Telecommunications Systems Institute, 37 Iroon Polytechniou Str. Crete, Greece Raghupathy Sivakumar, Georgia Institute of Technology, School of Electrical and Computer Engineering, Atlanta, Georgia 30332 Krishna M. Sivalingam, Washington State University, School of Electrical Engineering and Computer Science, Pullman, Washington 99164 Pradip K. Srimani, Clemson University, Department of Computer Science, Clemson, South Carolina 29634 Peter Stavroulakis, Telecommunications Systems Institute, 37 Iroon Polytechniou Str. , Crete, Greece Ivan Stojmenovic, DISCA, IIMAS, Universidad Nacional Autonoma de Mexico, Mexico ? D. F. , Mexico Yu-Chee Tseng, National Chiao-Tung University, Department of Computer Science and Information Engineering, Hsin-Chu 300, Taiwan Jorge Urrutia, Universidad Nacional Autonoma de Mexico, Instituto de Matematicas, Mexico D. F. Mexico Thanos Vasilakos, FORTH, Institute of Computer Science, Heraklion, Crete, Greece Jie Wu, Florida Atlantic University, Department of Computer Science and Engineering, Boca Raton, Florida 33431 Shih-Lin Wu, Chang Gung University, Department of Electrical Engineering, Tao-Yuan, Taiwan xvi CONTRIBUTORS Jianliang Xu, Hong Kong University of Science and Technology, Department of Computer Science, Clear Water Bay, Hong Kong Qing-An Zeng, University of Cincinnati, Department of Electrical Engineering and Computer Science, Cincinnati, Ohio 45221 Jingyuan Zhang, University of Alabama, Department of Computer Science, Tuscaloosa, Alabama 35487 Preface The past five decades have witnessed startling advances in computing and communication technologies that were stimulated by the availability of faster, more reliable, and cheaper electronic components.

The design of smaller and more powerful devices enabled their mobility, which is rapidly changing the way we compute and communicate. For instance, the worldwide number of cellular phone subscribers has quadrupled in the last five years and has grown to over half a billion (see www. gsmdata. com). Wireless and mobile networks are emerging as networks of choice, due to the flexibility and freedom they offer. The use of satellite, cellular, radio, sensor, and ad hoc wireless networks, wireless local area networks (LAN), small portable computers, and personal communication systems (PCS) is increasing. These networks and devices support a trend toward computing on the move, known as mobile computing, nomadic computing, or computing anywhere anytime.

The applications of mobile computing and wireless networks include e-commerce, personal communications, telecommunications, monitoring remote or dangerous environments, national defense (monitoring troop movements), emergency and disaster operations, remote operations of appliances, and wireless Internet access. This handbook is based on a number of self-contained chapters and provides an opportunity for practitioners and researchers to explore the connection between various computer science techniques and develop solutions to problems that arise in the rapidly emerging field of wireless networks. The mobile computing area deals with computing and communication problems that arise in packet radio networks, mobile cellular systems, personal communication systems, and wireless local area networks. The main direction of the book is to review various algorithms and protocols that have been developed in this area, with emphasis on the most recent ones.

This book is intended for researchers and graduate students in computer science and electrical engineering, and researchers and developers in the telecommunications industry. Although much has been written, especially recently, in this rapidly growing field, no other book treats problems in wireless networks from a computer science perspective, although a number of books that follow the engineering approach exist. The editor taught a computer science graduate course with the same title and contents as this handbook, but was not able to find any book that covered even half of the topics covered here (the course outline and transparencies for lectures given by me in the course can be found at www. site. uottawa. ca/~ivan). This andbook can be used as a textbook and a reference for use by students, researchers, and developers. xvii xviii PREFACE MOBILE AND WIRELESS NETWORKING ISSUES Mobile users do not necessarily use wireless interfaces. Instead, they can simply connect to fixed networks with a wired interface while away from their home or office. On the other hand, a fixed-location user may use a wireless interface (via a LAN) in an office environment. Other examples include wireless local loops, which provide fixed wireless access for voice and data transfer and high-speed Internet access. Wireless networks may use a fixed infrastructure as a backbone. For instance, cellular networks connect a mobile phone to the nearest base station (BS).

A BS serves hundreds of mobile users in a given area (cell) by allocating frequencies and providing hand-off support. BSs are linked (by wireline, fiberline, or wireless microwave links) to base station controllers that provide switching support to several neighboring BSs and serve thousands of users. Controllers are in turn connected to a mobile switching center that is capable of serving more than 100,000 users. Mobile switching centers are finally connected directly to the public service telephone network (PSTN). Therefore only the first and perhaps the last connection (if the other user is also using a mobile phone) are normally wireless.

However, the wireless link poses design challenges. The main difference between wired and wireless links is in the type of communication. Wired links normally provide one-to-one communication without interference, whereas wireless links use one-to-many communication that has a considerable noise and interference level and bandwidth limitations. Simultaneous wireless communications require channel separation, where channel may refer to time, frequency, or code. The channel capacity typically available in wireless systems is much lower than what is available in wired networks. The regulated frequency spectrum further limits the number of users that can be served concurrently.

Mobile devices use battery power, and limited power resources pose further design challenges. High noise levels cause larger bit-error rates. Forward error correction algorithms or error detection schemes (such as cyclic redundancy control) followed by buffering and selective retransmission must be used. One-to-many free space communication is also insecure, since a third party may easily receive the same messages. Encryption and decryption procedures that provide security require, at the same time, significant power and bandwidth resources. Some wireless networks do not have a fixed infrastructure as a backbone. Examples are ad hoc networks, sensor networks, and wireless LANs.

Wireless networks of sensors are likely to be widely deployed in the near future because they greatly extend our ability to monitor and control the physical environment from remote locations and improve the accuracy of information obtained via collaboration among sensor nodes and online information processing at those nodes. Networking these sensors (empowering them with the ability to coordinate among themselves on a larger sensing task) will revolutionize information gathering and processing in many situations. Sensors are normally small, cheap devices with limited computing power. The typical size of a sensor is about one cubic centimeter. However, the SmartDust project is attempting to determine whether an autonomous sensing, computing, and communication system can be packed into a cubic millimeter mote to form the basis of integrated, massively distributed sensor networks. Sensors can be placed in an indoor environment at convenient locations.

Alternatively, hundreds or thousands of them can be placed in a field. For example, sensor nodes can be air-dropped from a helicopter to cover an open field and report on vehicular activity or PREFACE xix troop movement. Each node contains one or more of the following sensor types: acoustic, seismic, magnetic, infrared, and visual imaging. Once the sensors are in place, each of them can detect neighboring sensors and decide about their transmission radius so that the number of sensors receiving signals is within some limit. This is a nontrivial problem in itself. For instance, a recently published algorithm, in which each node transmits hello messages sing radius kr, where r is a fixed small radius and k is modified until the number of responses is within limits, is not deterministic, has collision problems, and does not guaranty the process convergence or connectivity of the obtained network. Sensors should alternate between sleeping and active periods so that the life of each sensor, and overall network life, is maximized. They could be divided into clusters for further power savings. The detection and reporting of target movements is also a nontrivial problem. If every sensor that detects movement reports it to a center, too many messages are generated, causing collision problems and reducing sensor energy too quickly.

A recently proposed algorithm (which assumes that each sensor knows its own geographic location and is able to detect the direction of an object that is “visible”) suggests that all nodes whose neighboring nodes lie on the same side of a straight line from the node to the detected object should report the object’s presence. It was expected that there would be exactly two such nodes (located at tangents from the object to the convex hull of the sensors). This solution, however, may activate more sensors (the criteria can be satisfied for more nodes) or may not activate any sensor at all (for example, when the object is located inside the convex hull of the sensors). Even when exactly two such sensors are selected, the sensors could be too close to the line segment between them, causing computational errors in object location based on two object directions.

An alternative solution is to select only locally extreme sensors in four directions (N, S, E, and W) or possibly eight directions (including NW, NE, SW, and SE), and to combine the data obtained along the paths from them to a center that collects the data. Sensors that combine data will only forward “significant” improvements in the object’s location. We can envision similar applications for monitoring environmental pollutants and their source and direction of movement. Several computer science projects along these lines (e. g. , sensor information technology, diffusion-based networking, mobile scripts for target tracking, queries for collaborative signal processing), are currently ongoing (www. darpa. mil/ito/research/sensit, http://netweb. usc. edu/scadds, http://strange. arl. psu. du/RSN, www. cs. columbia. edu/dcc/asn, etc. ). A similar wireless network technology that has received significant attention in recent years is the ad hoc network. Mobile ad hoc networks consist of wireless hosts that communicate with each other in the absence of a fixed infrastructure. They are used in disaster relief, conferences, and battlefield environments. Wireless LANs are designed to operate in a small area such as a building or office complex. The communication between two hosts in wireless LANs, sensor, and ad hoc networks is not always direct. Hosts in wireless LANs, sensor, and ad hoc networks use the same frequency for communication.

Direct (or single-hop) transmission between any two hosts may require significant power (power normally decreases with the square or higher degree of distance between hosts) and is prone to collisions with other such transmissions. Thus, two hosts normally communicate via other hosts in the network (multihop communication). The solution to this involves solving routing problems. Collisions are difficult to detect because of the hidden station xx PREFACE problem. Two hosts that do not communicate directly may simultaneously transmit messages to a common neighbor, causing collision. Mobile networks should provide support for routing by maintaining communication during mobility. In order to maintain an ongoing routing task (e. g. ongoing phone call) or to facilitate route establishment or paging, mobile networks must also provide support for location management, that is, keeping track of the host location. The performance of wireless networks greatly depends on the choice of the medium access control (MAC) scheme. For instance, MAC protocols used in cellular networks in the United States and Europe differ. The IS-95 standard used in the United States uses code division multiple access (CDMA), whereas the GSM standard used in Europe uses TDMA (time division multiple access) on the top of FDMA (frequency DMA). CDMA provides more channels but at the expense of more noise and interference.

These differences prevent interoperability and global mobility, and also create obstacles to standardization of the third generation (3G) of cellular systems. Ad hoc, sensor, and wireless local area networks may use the IEEE 802. 11 standard for medium access, in which hosts wait for a randomly selected number of transmissionfree slots (back-off counter) before transmitting a message. Other standards (e. g. , HIPERLAN) are also available. One emerging MAC layer technology is Bluetooth (www. bluetooth. net). It provides short-range (about 10 meters), low-cost wireless connectivity among hosts such as computers, printers, scanners, PCs, or sensors.

In Bluetooth environments, hosts are organized into piconets, with one host in each piconet serving as master and a limited number (up to seven) of slave hosts directly linked to the master. Satellites are in wide use for broadcast services and long distance and international phone services to stationary users. Low-earth orbit (LEO) satellite systems, such as Teledesic (expected to be operational in 2003 and consisting of 288 satellites), will provide mobile communications to every point on earth. Satellites are organized in concentric orbits and maintain links with several satellites in neighboring orbits and nearest satellites in the same orbit.

Wireless ATM (asynchronous transfer mode) is an emerging technology for support of voice and data transmission. ATM connections rely partly on wireless networks. New challenges in the design of wireless ATM include varying channel characteristics, quality of service support, and support of end-to-end ATM connection as the user moves from one location to the other. ATM is a connection-oriented technology, so after a mobile user’s move to a new location, connection rerouting has to be performed. In a cellular network or ATM connections, location management schemes are needed in order to provide updated location information when a connection to a mobile user needs to be set up (routed) or rerouted. The Wireless Application Protocol (WAP, www. wapforum. rg) allows the development of applications that are independent of the underlying wireless access technology, and adapts existing website contents for transmission over wireless links and display on mobile devices. WAP architecture consists of a mobile client that sends an encoded request to a gateway and receives an encoded response from the gateway via a wireless network. The gateway, in turn, sends a request to a server and receives a response (content) from it over a wired network. WAP consist of application, session, transaction, security, transport, and wireless layers. Mobile devices require mobile operating systems (OSs) that are small in PREFACE xxi size and memory (e. g. , 300 KB) and are able to operate with little processing power and satisfy real-time requirements, such as voice traffic.

BRIEF OUTLINE OF THIS HANDBOOK The wide range of topics in this handbook makes it an excellent reference on wireless networks and mobile computing. Because each chapter is fully self-contained, readers can focus on the topics that most interest them. Most of the chapters (if not all) in this handbook have great practical utility. The handbook emphasizes computer science aspects, including implementation. Mathematical and engineering aspects are also represented in some chapters, since it is difficult to separate clearly all the issues among the three areas. Even when other aspects are clearly dominant, they are a good supplement to the rest of the handbook. A short outline of the material presented in each of the chapters of this volume follows.

The purpose is to identify the contents and also to aid diverse readers in assessing just what chapters are pertinent to their pursuits and desires. Each chapter should provide the reader with the equivalent of consulting an expert in a given discipline by summarizing the state of the art, interpreting trends, and providing pointers to further reading. It is a challenging task to clearly divide chapters into discrete areas because of overlaps. One such classification that will be attempted here is to divide the chapters into five main research areas: multiple access schemes, cellular networks, data communication, multihop networks, and mobile computing. Many chapters deal with more than one of these areas, so clear separation is difficult.

As a quick guide through the chapter topics, the first half of the chapters deal with multiple access schemes, data communication, and cellular networks; and other half deal with multihop networks and mobile computing. We shall now elaborate in more detail on each chapter, and try to group chapters into the five listed areas. Cellular networks were certainly the first and so far most successful commercial application of wireless networks. The research in this area is hence more advanced than in the others. Nevertheless, it remains a hot research topic because of emerging technologies such as the third generation (3G) of mobile phone systems. Chapters 1–5 deal primarily with cellular networks.

Chapter 1 discusses handoff, which is the mechanism for transferring an ongoing call from one base station to another as a user moves through the coverage area of a cellular system. It must be fast and efficient to prevent the quality of service from degenerating to an unacceptable level. Admission control is a related problem, in which the radio resource management system has to decide if a new call arrival or a request for service or handoff may be allowed into the system. Handoffs are normally prioritized with respect to new calls. Four conventional handoff schemes in a voice-based, single traffic system (nonpriority schemes, priority schemes, handoff call queuing schemes, and originating and handoff calls queuing schemes) are summarized in this chapter.

In addition, two handoff schemes with and without preemptive priority procedures for integrated voice and data wireless mobile networks are also covered in detail. Mobile phone users move among base stations but do not always register with the cur- xxii PREFACE rent base station, to avoid communication overhead and excessive battery use. There exists a trade-off between the frequency of location update by the mobile phone user and the delay in locating a user when a phone call is made. Chapter 2 reviews existing solutions to the location management problem. Chapters 3, 4, and 5 discuss the media access control problem in cellular networks. They are therefore at the intersection of the first two research areas of this handbook— multiple access schemes and cellular networks.

Media access control in cellular networks is achieved primarily by assigning different frequencies to users that are connected to the same or neighboring base stations, and repeating the same frequencies when the corresponding base stations are sufficiently far apart to avoid or minimize the interference. Chapter 3 describes fixed-channel assignment schemes in cellular networks, with the emphasis on recent heuristic algorithms that apply genetic algorithms, tabu search, neural networks, fuzzy logic, and other heuristics in solving problems. Channel assignment is generally classified into fixed and dynamic. In fixed channel assignment (FCA), channels are nominally assigned in advance according to the predetermined estimated traffic intensity at various base stations.

In dynamic channel assignment (DCA), channels are assigned dynamically as calls arrive. It is more efficient in terms of channel usage, but requires more complex and time-consuming control. Hybrid channel assignment (HCA) combines the two approaches by dividing the frequencies into two separate ranges, one for FCA and other for DCA. In borrowing channel assignment (BCA), the channel assignment is initially fixed. If there are incoming calls for a cell whose channels are all occupied, the cell borrows channels from its neighboring cells and thus call blocking is prevented. Cochannel interference is the most critical of all interference that occurs in cellular radio.

The same channel cannot be assigned to two users that are connected to the same or two “close” base stations since such cochannel interference is likely to cause an unacceptable signal-to-noise ratio. The minimal distance between two base stations that can use the same channel is called the reuse distance. If this is the only type of interference considered, the channel assignment problem reduces to a multicoloring problem. In a multicoloring problem defined on a graph, each base station is demanding a certain number of colors (that is, frequencies), so that any two neighboring nodes get a disjoint set of colors (and, of course, colors assigned to each node are all distinct).

When translated to cellular systems, nodes are base stations, and two base stations are “neighbors” in graph terms if the distance between then is less than the reuse distance. Chapter 4 studies this simplified version of the famous graph coloring problem that is known to be computationally difficult. Algorithms and lower bounds for this problem (including FCA, DCA, BCA, and HCA problem statements) are surveyed. The secondary source of interference in cellular systems is adjacent channel interference. The filters for each channel at base stations are not ideal, and allow the signals from neighboring channels, with reduced strength, to generate noise. In a general problem statement, two base stations (i. e. cells) that are at a distance i (where i is the minimal number of cell crossings between two cells) cannot be assigned two frequencies that differ by less than ci. The cosite constraint c0 indicates the channel separation at the same base station, which is normally high compared to other constraints. The intersite constraints ci (i > 0) most often take smaller values, especially one or two. An intersite constraint of one PREFACE xxiii indicates that the two base stations must use distinct frequencies, whereas zero constraint indicates that the two cells may reuse frequencies. More precisely, in a good channel assignment, they actually should reuse the frequencies. Chapter 5 gives an overview of algorithms and lower bounds for this problem.

It also discusses relevant results on graph labeling, which form the basis of many of the algorithms. Several chapters deal with multiple access schemes. Since the wireless medium is inherently a shared resource, controlling channel access becomes a central theme that determines the system capacity, complexity, and cost. Chapter 6 focuses on the design and implementation of media access control (MAC) protocols for cellular telephony, wireless ATM, and ad hoc networks. Fundamental MAC protocols include frequency division multiple access (FDMA), time division multiple access (TDMA), code division multiple access (CDMA), and random access schemes such as ALOHA and carrier sense multiple access (CSMA).

Chapter 7 discusses the integration of voice and data traffic in wireless networks. It concentrates on Bluetooth technology (the de facto standard for wireless personal area networks), IEEE 802. 11 technology (the main standard for wireless local area networks), and the UMTS technology for third generation cellular systems. Fairness among mobile or wireless users implies that the allocated channel bandwidth is in proportion to the “weights” of the users. Fair queuing in the wireless domain poses significant challenges due to unique issues in the wireless channel such as location-dependent and bursty channel error. Hence, it is imperative to provide fair channel access among multiple contending hosts.

Chapter 8 identifies key issues in wireless fair queuing, defines a wireless fair service model, and surveys algorithms from contemporary literature. Chapters 9 and 10 deal with organization issues for medium access in radio networks, which are distributed systems with no central arbiter, consisting of n radio transceivers, also called stations. The wireless environment is single-hop one, meaning that each station is able to hear a transmission from any other station. The time is slotted, and all transmissions occur at slot boundaries. Chapter 9 describes how each station can assign to itself a unique identifier in the range [1, n] so that the i-th user is able to transmit the message in the i-th slot. This provides collision-free TDMA transmission in a round robin fashion.

The algorithms are distributed, and their analysis is based on combinatorial facts of binomial distribution, tree partitions, and graphs. Initialization protocols with and without collision detection capabilities, and using one of several channels for communication, are presented. The leader election problem designates one of the stations as leader. Chapter 10 surveys recent protocols on the leader election problem in single-hop, single-channel radio networks. Chapters 10–14 deal primarily with data communication issues in wireless networks, with considerable overlap with all other listed areas. Mobile wireless environments are characterized by asymmetric communication.

The downlink communication from base station, satellite, or other server is much greater than the uplink communication capacity. In broadcast, data are sent simultaneously to all users residing in the broadcast area. Each user in a data broadcast problem has a list of desired files or data it wants to receive from the server. The order and frequency for each file or datum that is broadcast should take access efficiency and power conservation into ac- xxiv PREFACE count. Access efficiency concerns how fast a request is satisfied, whereas power conservation concerns how to reduce a mobile client’s power consumption when it is accessing the data it wants.

Chapter 11 surveys various techniques and problem formulations for wireless data broadcast, sometimes also refereed to as broadcast scheduling. Digital broadcasting systems are expected to replace current FM radio and television technology. Chapter 12 considers the design of DAB (digital audio broadcasting) networks. The DAB system transmits whole ensembles consisting of multiple radio programs and other data services, and allows an ensemble to be transmitted on a single channel even if the corresponding transmitters may interfere. The task is to arrange services into a collection of ensembles for each request area, and to assign channels to the resulting ensembles.

The problem can be formulated as the combined bin packing and graph coloring problem. Several basic heuristics, lower bounding algorithms, and the tabu search solution are described. With the increasing number of wireless and mobile devices using the Internet, researchers have been studying the impact of wireless networking technologies on the different layers of the network protocol stack. Chapter 13 focuses on the transport layer in microcell and macrocell wireless networks. The task in the transport layer is to organize the speed of transmissions, acknowledgment, and possible retransmissions of every packet of a data transfer. It deals primarily with the network congestion problem.

The unique characteristics of wireless networks that result in poor performance for existing protocol standards are identified (such as reduced bandwidth, which needs to be distinguished from congestion), and approaches that have been proposed to address these characteristics are surveyed. Chapter 14 focuses on security and fraud detection problems in mobile and wireless networks, and presents some solutions to several aspects of the security problem, such as authentication of mobile users and fraud detection in mobile phone operations. Further increases in network security are necessary before the promise of mobile telecommunication can be fulfilled. Chapters 14–24 deal with multihop wireless networks. Their primary characteristic is that mobile or wireless stations, phones, users, sensors, or other devices (let us call them nodes) cannot communicate directly with any other node in the network.

Thus, they communicate with each other via other nodes, through several hops. The network is then modeled by a graph where two nodes are linked if and only if they can directly communicate. If that graph is a complete graph (where each node can directly communicate to any other node), the network is called a single-hop one. Cellular networks and transport protocols also deal with multihop networks, but the problems studied and solution presented are not significantly based on the underlying graph model. Ad hoc networks are a key to the evolution of wireless networks. They are typically composed of equal nodes that communicate over wireless links without any central control.

Ad hoc wireless networks inherit the traditional problems of wireless and mobile communications, such as bandwidth optimization, power control, and transmission quality enhancement. In addition, the multihop nature and the lack of fixed infrastructure bring new research problems such as configuration advertising, discovery and maintenance, as well as ad hoc addressing and self-routing. Many different approaches and protocols have been proposed and there are even multiple standardization efforts within the Internet En- PREFACE xxv gineering Task Force, as well as academic and industrial projects. Chapter 15 focuses on the state of the art in mobile ad hoc networks.

It highlights some of the emerging technologies, protocols, and approaches (at different layers) for realizing network services for users on the move in areas with possibly no preexisting communications infrastructure. People-based networks, where information is transmitted using “people” (i. e. , personal devices such as personal digital assistants), are also discussed. To avoid interference of signals arriving from several neighbors to a single host, or simultaneous transmissions from two neighboring hosts, each host should create its own transmission schedule. That is, each host should decide which time slots are available for collision-free transmissions. Chapter 16 explores the computational and algorithmic complexity of broadcast scheduling, which, in general form, is an NP-complete problem.

The chapter reviews existing broadcast scheduling approximation, off-line and on-line, and centralized and distributed algorithms, and discusses their effect on the quality of the schedules produced. In a wireless network, routing the message (finding a path between a source and a destination node) is a basic data communication protocol. A mobile ad hoc network consists of a set of mobile hosts capable of communicating with each other without the assistance of base stations. Chapter 17 reviews the existing routing algorithms for networks consisting of nodes that do not have information about their geographic position. Recently, the location of a sensor or station was made feasible by adding a GPS lowpower, small-size receiver that is able of etermining its location (latitude, longitude, and height) within a few millimeters by cooperating with existing satellite and auxiliary earth networks. GPS also provides global timing to stations. Position information enables development of localized routing methods (greedy routing decisions are made at each node, based solely on the knowledge of positions of neighbors and the destination, with considerable savings in communication overhead and with guaranteed delivery provided location update schemes are efficient for a given movement pattern). When GPS is not available, the relative position of neighboring nodes may be determined based on strength of signals from neigboring nodes, or some other alternative means.

Chapter 18 surveys routing algorithms in communication networks, where nodes are aware of their geographic position and those of their neigboring nodes. The algorithms take advantage of geometric properties of planar networks, constructing a planar subgraph of a given wireless network. Guaranteed delivery is a salient property of the algorithms, assuming destination location is accurate and the network is modeled by unit graphs. In a unit graph, all nodes have the same transmission radius, and two nodes can directly communicate if and only if their distance is less than that radius. Chapter 19 surveys energy-efficient routing protocols for wireless ad hoc networks.

It includes evaluation of energy consumption in ad hoc routing protocols, localized routing algorithms that optimize based on power and other metrics, network topology generation designed to optimize power consumption, routing algorithms that balance power consumption among all network nodes, and algorithms that maximize nodes’ lifetimes. A set of nodes in a network is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. Chapter 20 reviews simple and efficient distributed algorithms for calculating a connected dominating set in ad hoc wireless networks, where connections of nodes are determined by their geographic distances. Applications of domi- xxvi PREFACE nating sets in reducing the cost of routing, multicasting, and broadcasting are also discussed.

Chapter 21 reviews research on routing in ad hoc and sensor wireless networks in the light of node mobility, changes in node activity, and availability of methods to determine the absolute or relative coordinates of each node. Various approaches in the literature are classified according to some criteria. Mobility is apparently a very difficult problem to handle in ad hoc networks, and all proposed solutions have significant drawbacks. Additional problems arise with “sleep” period operation, that is, changes in a node’s activity status with or without mobility. Although significant progress has been made on routing with a known destination location, issuing location updates to enable efficient routing requires further investigation.

Chapter 22 surveys communication-related issues arising in the context of low earth orbit (LEO) satellite constellations. In particular, it studies the impact of the predictable movement of the satellites on the techniques used in topological design, routing, and handover strategies. In a multicasting problem, a message is to be sent from a node to several other nodes in the network. Chapter 23 briefly reviews multicasting methods that were proposed in the literature for wired networks, and then gradually relaxes the requirement that all nodes be stationary, discussing multicast protocols for cellular networks (characterized by a fixed infrastructure with mobile end nodes) and ad hoc networks (infrastructureless mobile networks).

Broadcasting is the task of forwarding a message from a source (or central facility) to all the nodes in the network. Chapter 24 reviews broadcasting algorithms in radio networks, under different communication scenarios and different amounts of knowledge of the network. The chapter primarily deals with the worst-case analysis of algorithms. Chapters 25–28 deal primarily with mobile computing or computing and communication protocol issues in the presence of node mobility. Chapter 25 presents the basic characteristics of mobile IP, which is a protocol that allows transparent routing of IP datagrams to mobile nodes on the Internet. Each mobile node is always identified by its home address, regardless of its current point of attachment to the Internet.

When away from its home, information about its current point of attachment to the Internet is provided through a care-of address associated with the node. The home agent sends datagrams destined for the mobile node through a tunnel to the care-of address. After arriving at the end of the tunnel, each datagram is then delivered to the mobile node. Routing, security, and management issues are discussed based on the most recent activities of the relevant standardization bodies. Chapter 26 surveys data management schemes in wireless mobile environments. Mobile computing can possibly be viewed as a variation of traditional distributed computing from the data management point of view. In general, there are two possible scenarios.

In the first, the entire database is distributed only among the wired components, e. g. , the mobile switching stations (MSS), each base station managing its own share of the database with the additional capability of locating the components of the databases that are not locally available. In the second approach, the entire database is distributed over both the wired and wireless components of the system. The functionality of a database management system depends on the design of database and replication of data schemes. These issues are handled, in some form or other, via caching data in the mobile units and periodi- PREFACE xxvii cally validating this data using different techniques.

The protocols and frequency of validation of the data have a profound influence on the performance of data management in mobile environments. The advent of distributed computing has had a major influence in the computing industry in recent years, witnessed by the growth of mobile computers and networked computing systems. The desire to share resources, to parcel out computing tasks among several different hosts, and place applications on machines most suitable to their needs, has led to distributed programming systems such as CORBA and DCOM, which predominate in the marketplace. Pervasive computing can be defined as access to information and software applications anytime and anywhere.

Users are mobile and services are provided by collections of distributed components collaborating together. Recent advances in mobile computing, service discovery, and distributed computing are key technologies to support pervasive computing. Chapter 27 is about software technologies used to address problems in mobile, distributed, and pervasive computing. It reviews characteristics, software architecture, and key open communication technologies (service discovery and distributed computing) to support pervasive computing. Recent advances in wireless and mobile computing, and inexpensive, portable devices have resulted in the emergence of indoor wireless networks.

Chapter 28 focuses on challenges specific to this environment. It discusses design issues and options for the physical layer, and dwells at length on a few media access control (MAC) layer protocols that have been proposed for the indoor environment. It is shown how these problems have been dealt with in some popular and well-accepted technologies, namely, Wireless LAN (IEEE 802. 11), HomeRF and Bluetooth. Network topology and self-organization of such networks, with special reference to Bluetooth, which has very interesting topology construction problems, is also discussed. RECOMMENDED READING Each chapter in the handbook is accompanied by its own reference section.

However, it is necessary for the reader to refer to journals and conference proceedings to keep up with the recent developments in the field. Some of the important journals that publish articles in the area of wireless networks and mobile computing in the field are: ACM Computer Communication Review (www. acm. org) ACM Mobile Computing and Communications Review (http://www. acm. org/sigmobile/MC2R) Communications of the ACM (www. acm. org) IEEE/ACM Transactions on Networking (www. ton. cc. gatech. edu) IEEE Communications Magazine (www. computer. org) IEEE Pervasive Computing (www. computer. org/pervasive) IEEE Transactions on Mobile Communications (www. computer. org/tmc) IEEE Transactions on Parallel and Distributed Systems (www. computer. org) xxviii PREFACE

IEEE Transactions on Selected Areas in Communication (www. computer. org) IEEE Transactions on Vehicular Technology (www. computer. org) IEEE Transactions on Wireless Communications (www. ee. ust. hk/~eekhaled) International Journal of Wireless Information Networks (www. baltzer. nl) IEEE Communication Letters (www. computer. org) International Journal of Communication Systems International Journal of Satellite Communications Journal of Parallel and Distributed Computing Mobile Networks and Applications (www. baltzer. nl/monet) Wireless Communications and Mobile Computing (www. wiley. com) Wireless Networks (www. acm. org/journals/125. html) Wireless Personal Communication (www. baltzer. l) The reader is also encouraged to refer to the proceedings of some of the main events and conferences that cover the topics, for example: ACM International Conference on Mobile Computing and Networking MOBICOM (www. acm. org/sigmobile) International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL M for Mobility) International Workshop on Wireless Mobile Multimedia, WoW MoM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, MSWiM ACM Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc ACM Wireless Mobile Internet Workshop IEEE INFOCOM (www. ieee-infocom. rg) IEEE International Parallel and Distributed Processing Symposium, IPDPS (www. ipdps. org) IEEE Vehicular Technology Conference, VTC IEEE Hawaii International Conference on System Sciences, Software Technology Track (www. hicss. org) International Conference on Parallel Processing IEEE International Conference on Distributed Computing and Systems IASTED International Conference on Parallel and Distributed Computing and Systems (www. iasted. com/confrences) IEEE International Conference on Computer Communications and Networks, ICCCN (www. icccn. cstp. umkc. edu) International Conference on Communications in Computing, CIC (www. cs. utep. edu/~cic) IEEE GLOBECOM PREFACE xxix

IEEE Symposium on Computers and Communications (www. comsoc. org/iscc) IEEE International Conference on Universal Personal Communications The Internet is becoming the major source of information in this area, since the majority of researchers put their own papers on their web pages. From my own experience, the primary source of information is the research index that can be found at http://citeseer. nj. nec. com/cs. This is a citation database that links papers according to their subject and mutual citations, and provides the web and e-mail addresses for many of the authors (and, of course, Internet search engines can locate most of the remaining ones).

ACKNOWLEDGMENTS The editor is grateful to all the authors for their contributions to the quality of this handbook. The assistance of reviewers for all chapters is also greatly appreciated. The University of Ottawa and Universidad National Autonoma de Mexico provided an ideal working environment for the preparation of this handbook, including computer facilities for efficient Internet search, communication by electronic mail, and writing my own contributions. The editor is thankful to Dr. Albert Zomaya, editor of the Parallel and Distributed Computing book series at Wiley, for his support and encouragement in publishing this handbook. The editor also appreciates the support of Dr.

Stephan Olariu for encouraging publication of this handbook by Wiley instead of other publishers that also offered contracts. Dr. Philip Meyler, editor at Wiley, also deserves special mention for his timely and professional cooperation, and for his decisive support of this project. Finally, I thank my children Milos and Milica and my wife Natasa for making this effort worthwhile and for their patience during the numerous hours at home that I spent in front of the computer. I hope that the readers will find this handbook informative and worth reading. Comments from readers will be greatly appreciated. SITE, University of Ottawa, Ottawa, Ontario, Canada Ivan@site. uottawa. ca ivan@leibniz. iimas. unam. mx; www. site. uottawa. a/~ivan DISCA, IIMAS, UNAM, Mexico D. F. , Mexico April 2001 IVAN STOJMENOVIC ? HANDBOOK OF WIRELESS NETWORKS AND MOBILE COMPUTING Handbook of Wireless Networks and Mobile Computing, Edited by Ivan Stojmenovic ? Copyright © 2002 John Wiley & Sons, Inc. ISBNs: 0-471-41902-8 (Paper); 0-471-22456-1 (Electronic) CHAPTER 1 Handoff in Wireless Mobile Networks QING-AN ZENG and DHARMA P. AGRAWAL Department of Electrical Engineering and Computer Science, University of Cincinnati 1. 1 INTRODUCTION Mobility is the most important feature of a wireless cellular communication system. Usually, continuous service is achieved by supporting handoff (or handover) from one cell to another.

Handoff is the process of changing the channel (frequency, time slot, spreading code, or combination of them) associated with the current connection while a call is in progress. It is often initiated either by crossing a cell boundary or by a deterioration in quality of the signal in the current channel. Handoff is divided into two broad categories— hard and soft handoffs. They are also characterized by “break before make” and “make before break. ” In hard handoffs, current resources are released before new resources are used; in soft handoffs, both existing and new resources are used during the handoff process. Poorly designed handoff schemes tend to generate very heavy signaling traffic and, thereby, a dramatic decrease in quality of service (QoS). In this chapter, a handoff is assumed to occur only at the cell boundary. ) The reason why handoffs are critical in cellular communication systems is that neighboring cells are always using a disjoint subset of frequency bands, so negotiations must take place between the mobile station (MS), the current serving base station (BS), and the next potential BS. Other related issues, such as decision making and priority strategies during overloading, might influence the overall performance. In the next section, we introduce different types of possible handoffs. In Section 1. 3, we describe different handoff initiation processes. The types of handoff decisions are briefly described in Section 1. and some selected representative handoff schemes are presented in Section 1. 5. Finally, Section 1. 6 summarizes the chapter. 1. 2 TYPES OF HANDOFFS Handoffs are broadly classified into two categories—hard and soft handoffs. Usually, the hard handoff can be further divided into two different types—intra- and intercell handoffs. The soft handoff can also be divided into two different types—multiway soft handoffs and softer handoffs. In this chapter, we focus primarily on the hard handoff. 1 2 HANDOFF IN WIRELESS MOBILE NETWORKS BS 1 MS BS 2 BS 1 MS BS 2 a. Before handoff b. After handoff Figure 1. 1 Hard handoff between the MS and BSs. A hard handoff is essentially a “break before make” connection.

Under the control of the MSC, the BS hands off the MS’s call to another cell and then drops the call. In a hard handoff, the link to the prior BS is terminated before or as the user is transferred to the new cell’s BS; the MS is linked to no more than one BS at any given time. Hard handoff is primarily used in FDMA (frequency division multiple access) and TDMA (time division multiple access), where different frequency ranges are used in adjacent channels in order to minimize channel interference. So when the MS moves from one BS to another BS, it becomes impossible for it to communicate with both BSs (since different frequencies are used). Figure 1. 1 illustrates hard handoff between the MS and the BSs. . 3 HANDOFF INITIATION A hard handoff occurs when the old connection is broken before a new connection is activated. The performance evaluation of a hard handoff is based on various initiation criteria [1, 3, 13]. It is assumed that the signal is averaged over time, so that rapid fluctuations due to the multipath nature of the radio environment can be eliminated. Numerous studies have been done to determine the shape as well as the length of the averaging window and the older measurements may be unreliable. Figure 1. 2 sh