Prentice Hall Communications Engineering and Emerging Technologies Series
Theodore S. Rappaport, Series Editor
ANDREWS, GHOSH, & MUHAMED Fundamentals of WiMAX: Understanding Broadband Wireless Networking
DI BENEDETTO & GIANCOLA Understanding Ultra Wide Band Radio Fundamentals
DOSTERT Powerline Communications
DURGIN Space–Time Wireless Channels Technologies, Standards, and QoS
GARG Wireless Network Evolution: 2G to 3G
GARG IS-95 CDMA and cdma2000: Cellular/PCS Systems Implementation
LIBERTI & RAPPAPORT Smart Antennas for Wireless Communications: IS-95 and Third Generation CDMA Applications
MURTHY & MANOJ Ad Hoc Wireless Networks: Architectures and Protocols
NEKOOGAR Ultra-Wideband Communications: Fundamentals and Applications
PATTAN Robust Modulation Methods and Smart Antennas in Wireless Communication
RADMANESH Radio Frequency and Microwave Electronics Illustrated
RAPPAPORT Wireless Communications: Principles and Practice, Second Edition
REED Software Radio: A Modern Approach to Radio Engineering
REED An Introduction to Ultra Wideband Communication Systems
SKLAR Digital Communications: Fundamentals and Applications, Second Edition
STARR, SORBARA, CIOFFI, & SILVERMAN DSL Advances
TRANTER, SHANMUGAN, RAPPAPORT, & KOSBAR Principles of Communication Systems Simulation with Wireless Applications
VANGHI, DAMNJANOVIC, & VOJCIC The cdma2000 System for Mobile Communications: 3G Wireless Evolution
WANG & POOR Wireless Communication Systems: Advanced Techniques for Signal Reception
Ad Hoc Wireless Networks
Architectures and Protocols
PRENTICE HALL
PROFESSIONAL TECHNICAL REFERENCE
UPPER SADDLE RIVER, NJ 07458
WWW.PHPTR.COM
Library of Congress Cataloging-in-Publication Data
Murthy, C. Siva Ram.
Ad Hoc wireless networks : architectures and protocols / C. Siva Ram Murthy, B.S. Manoj.
p. cm.
Includes bibliographical references and index.
ISBN 0-13-147023-X
1. Wireless communication systems. 2. Routers (Computer networks) 3. Computer
network architectures. I. Manoj, B.S. II. Title.
TK5103.2.M89 2004
004.6'5--dc22
2004043863
Editorial/production supervision: Jane Bonnell
Composition: Lori Hughes
Cover design director: Jerry Votta
Cover design: B. S. Manoj and C. Siva Ram Murthy
Manufacturing buyer: Maura Zaldivar
Publisher: Bernard M. Goodwin
Editorial assistant: Michelle Vincenti
Marketing manager: Dan DePasquale
©2004 Pearson Education, Inc.
Publishing as Prentice Hall Professional Technical Reference
Upper Saddle River, New Jersey 07458
Prentice Hall PTR offers excellent discounts on this book when ordered in quantity for bulk purchases or special sales. For more information, please contact: U.S. Corporate and Government Sales, 1-800-382-3419, [email protected]. For sales outside of the U.S., please contact: International Sales, 1-317-581-3793, [email protected].
Company and product names mentioned herein are trademarks or registered trademarks of their respective owners.
All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher.
ISBN 0-13-147023-X
Text printed in the United States at Integrated Book Technology in Troy, New York.
6th Printing February 2008
Pearson Education LTD.
Pearson Education Australia PTY, Limited
Pearson Education South Asia Pte. Ltd.
Pearson Education Asia Ltd.
Pearson Education Canada, Ltd.
Pearson Educación de Mexico, S.A. de C.V.
Pearson Education—Japan
Pearson Malaysia SDN BHD
To my wife, Sharada,
my son, Chandrasekhar,
and my daughter, Sarita.
C. Siva Ram Murthy
To my wife, Swapna,
and my daughter, Gouri.
B.S. Manoj
About Prentice Hall Professional Technical Reference
With origins reaching back to the industry's first computer science publishing program in the 1960s, and formally launched as its own imprint in 1986, Prentice Hall Professional Technical Reference (PH PTR) has developed into the leading provider of technical books in the world today. Our editors now publish over 200 books annually, authored by leaders in the fields of computing, engineering, and business.
Our roots are firmly planted in the soil that gave rise to the technical revolution. Our bookshelf contains many of the industry's computing and engineering classics: Kernighan and Ritchie's C Programming Language, Nemeth's UNIX System Administration Handbook, Horstmann's Core Java, and Johnson's High-Speed Digital Design.
PH PTR acknowledges its auspicious beginnings while it looks to the future for inspiration. We continue to evolve and break new ground in publishing by providing today's professionals with tomorrow's solutions.
CONTENTS
1.1 Fundamentals of Wireless Communication Technology
1.2 The Electromagnetic Spectrum
1.3 Radio Propagation Mechanisms
1.4 Characteristics of the Wireless Channel
1.4.5 Transmission Rate Constraints
1.6 Multiple Access Techniques
1.6.1 Frequency Division Multiple Access
1.6.2 Time Division Multiple Access
1.6.3 Code Division Multiple Access
1.6.4 Space Division Multiple Access
1.10 Computer Network Software
1.11 Computer Network Architecture
1.11.1 The OSI Reference Model
1.11.2 The TCP/IP Reference Model
1.11.3 The ATM Reference Model
1.12 IEEE 802 Networking Standard
1.13 Wireless Networks and Book Overview
2.3.2 Basic MAC Layer Mechanisms
2.3.4 Other MAC Layer Functionalities
2.5.1 Bluetooth Specifications
2.5.2 Transport Protocol Group
2.5.3 Middleware Protocol Group
3.2.2 Channel Allocation Algorithms
3.4 The First-Generation Cellular Systems
3.4.1 Advanced Mobile Phone System
3.5 The Second-Generation Cellular Systems
3.5.1 Global System for Mobile Communications
3.5.3 GSM Evolution of Data Services
3.6 The Third-Generation Cellular Systems
3.6.2 The Problems with 3G Systems
3.7.1 Generic WLL Architecture
3.7.3 Broadband Wireless Access
3.9.1 Differences Between IEEE 802.11 and IEEE 802.16
4.2 What Is Wireless Internet?
4.2.2 Inefficiency of Transport Layer Protocols
4.2.3 Inefficiency of Application Layer Protocols
4.3.4 MobileIP Variations – The 4 × 4 Approach
4.3.9 MRSVP – Resource Reservation
4.4.7 Explicit Loss Notification
4.4.10 Transaction-Oriented TCP
4.6 Optimizing Web Over Wireless
5.1.1 Cellular and Ad Hoc Wireless Networks
5.1.2 Applications of Ad Hoc Wireless Networks
5.2 Issues in Ad Hoc Wireless Networks
5.2.4 Transport Layer Protocols
5.2.6 Quality of Service Provisioning
5.2.9 Addressing and Service Discovery
5.2.12 Deployment Considerations
6 MAC PROTOCOLS FOR AD HOC WIRELESS NETWORKS
6.2 Issues in Designing a MAC Protocol for Ad Hoc Wireless Networks
6.2.2 Quality of Service Support
6.2.4 Hidden and Exposed Terminal Problems
6.2.5 Error-Prone Shared Broadcast Channel
6.2.6 Distributed Nature/Lack of Central Coordination
6.3 Design Goals of a MAC Protocol for Ad Hoc Wireless Networks
6.4 Classifications of MAC Protocols
6.4.1 Contention-Based Protocols
6.4.2 Contention-Based Protocols with Reservation Mechanisms
6.4.3 Contention-Based Protocols with Scheduling Mechanisms
6.5 Contention-Based Protocols
6.5.1 MACAW: A Media Access Protocol for Wireless LANs
6.5.2 Floor Acquisition Multiple Access Protocols
6.5.3 Busy Tone Multiple Access Protocols
6.5.5 Media Access with Reduced Handshake
6.6 Contention-Based Protocols with Reservation Mechanisms
6.6.1 Distributed Packet Reservation Multiple Access Protocol
6.6.2 Collision Avoidance Time Allocation Protocol
6.6.3 Hop Reservation Multiple Access Protocol
6.6.4 Soft Reservation Multiple Access with Priority Assignment
6.6.5 Five-Phase Reservation Protocol
6.6.6 MACA with Piggy-Backed Reservation
6.6.7 Real-Time Medium Access Control Protocol
6.7 Contention-Based MAC Protocols with Scheduling Mechanisms
6.7.1 Distributed Priority Scheduling and Medium Access in Ad Hoc Networks
6.7.2 Distributed Wireless Ordering Protocol
6.7.3 Distributed Laxity-Based Priority Scheduling Scheme
6.8 MAC Protocols That Use Directional Antennas
6.8.1 MAC Protocol Using Directional Antennas
6.8.2 Directional Busy Tone-Based MAC Protocol
6.8.3 Directional MAC Protocols for Ad Hoc Wireless Networks
6.9.1 Multichannel MAC Protocol
6.9.2 Multichannel CSMA MAC Protocol
6.9.3 Power Control MAC Protocol for Ad Hoc Networks
6.9.4 Receiver-Based Autorate Protocol
6.9.5 Interleaved Carrier-Sense Multiple Access Protocol
7 ROUTING PROTOCOLS FOR AD HOC WIRELESS NETWORKS
7.2 Issues in Designing a Routing Protocol for Ad Hoc Wireless Networks
7.2.3 Error-Prone Shared Broadcast Radio Channel
7.2.4 Hidden and Exposed Terminal Problems
7.2.6 Characteristics of an Ideal Routing Protocol for Ad Hoc Wireless Networks
7.3 Classifications of Routing Protocols
7.3.1 Based on the Routing Information Update Mechanism
7.3.2 Based on the Use of Temporal Information for Routing
7.3.3 Based on the Routing Topology
7.3.4 Based on the Utilization of Specific Resources
7.4 Table-Driven Routing Protocols
7.4.1 Destination Sequenced Distance-Vector Routing Protocol
7.4.2 Wireless Routing Protocol
7.4.3 Cluster-Head Gateway Switch Routing Protocol
7.4.4 Source-Tree Adaptive Routing Protocol
7.5 On-Demand Routing Protocols
7.5.1 Dynamic Source Routing Protocol
7.5.2 Ad Hoc On-Demand Distance-Vector Routing Protocol
7.5.3 Temporally Ordered Routing Algorithm
7.5.5 Associativity-Based Routing
7.5.6 Signal Stability-Based Adaptive Routing Protocol
7.5.7 Flow-Oriented Routing Protocol
7.6.1 Core Extraction Distributed Ad Hoc Routing Protocol
7.6.3 Zone-Based Hierarchical Link State Routing Protocol
7.7 Routing Protocols with Efficient Flooding Mechanisms
7.7.1 Preferred Link-Based Routing Protocols
7.7.2 Optimized Link State Routing
7.8 Hierarchical Routing Protocols
7.8.1 Hierarchical State Routing Protocol
7.8.2 Fisheye State Routing Protocol
7.9 Power-Aware Routing Protocols
7.9.1 Power-Aware Routing Metrics
8 MULTICAST ROUTING IN AD HOC WIRELESS NETWORKS
8.2 Issues in Designing a Multicast Routing Protocol
8.3 Operation of Multicast Routing Protocols
8.3.1 Source-Initiated Protocols
8.3.2 Receiver-Initiated Protocols
8.4 An Architecture Reference Model for Multicast Routing Protocols
8.5 Classifications of Multicast Routing Protocols
8.6 Tree-Based Multicast Routing Protocols
8.6.1 Bandwidth-Efficient Multicast Routing Protocol
8.6.2 Multicast Routing Protocol Based on Zone Routing
8.6.3 Multicast Core-Extraction Distributed Ad Hoc Routing
8.6.4 Associativity-Based Ad Hoc Multicast Routing
8.6.5 Differential Destination Multicast Routing Protocol
8.6.6 Weight-Based Multicast Protocol
8.6.7 Preferred Link-Based Multicast Protocol
8.6.8 Multicast Ad Hoc On-Demand Distance Vector Routing Protocol
8.6.9 Ad Hoc Multicast Routing Protocol Utilizing Increasing ID-Numbers
8.6.10 Ad Hoc Multicast Routing Protocol
8.6.11 Adaptive Shared-Tree Multicast Routing Protocol
8.7 Mesh-Based Multicast Routing Protocols
8.7.1 On-Demand Multicast Routing Protocol
8.7.2 Dynamic Core-Based Multicast Routing Protocol
8.7.3 Forwarding Group Multicast Protocol
8.7.4 Neighbor Supporting Ad Hoc Multicast Routing Protocol
8.7.5 Core-Assisted Mesh Protocol
8.8 Summary of Tree- and Mesh-Based Protocols
8.9 Energy-Efficient Multicasting
8.9.1 Energy-Efficient Reliable Broadcast and Multicast Protocols
8.9.2 A Distributed Power-Aware Multicast Routing Protocol
8.9.3 Energy-Efficient Multicast Routing Protocol
8.9.4 Energy-Efficient Cluster Adaptation of Multicast Protocol
8.10 Multicasting with Quality of Service Guarantees
8.10.1 Wireless Ad Hoc Real-Time Multicasting Protocol
8.10.2 Multicast Priority Scheduling Protocol
8.11 Application-Dependent Multicast Routing
8.11.2 Content-Based Multicast
8.11.3 Location-Based Multicast
9 TRANSPORT LAYER AND SECURITY PROTOCOLS FOR AD HOC WIRELESS NETWORKS
9.2 Issues in Designing a Transport Layer Protocol for Ad Hoc Wireless Networks
9.3 Design Goals of a Transport Layer Protocol for Ad Hoc Wireless Networks
9.4 Classification of Transport Layer Solutions
9.5 TCP Over Ad Hoc Wireless Networks
9.5.1 A Brief Revisit to Traditional TCP
9.5.2 Why Does TCP Not Perform Well in Ad Hoc Wireless Networks?
9.5.4 TCP with Explicit Link Failure Notification
9.5.8 A Comparison of TCP Solutions for Ad Hoc Wireless Networks
9.6 Other Transport Layer Protocols for Ad Hoc Wireless Networks
9.6.1 Application Controlled Transport Protocol
9.6.2 Ad Hoc Transport Protocol
9.7 Security in Ad Hoc Wireless Networks
9.8 Network Security Requirements
9.9 Issues and Challenges in Security Provisioning
9.10.2 Transport Layer Attacks
9.10.3 Application Layer Attacks
9.11.1 Symmetric Key Algorithms
9.11.2 Asymmetric Key Algorithms
9.11.3 Key Management Approaches
9.11.4 Key Management in Ad Hoc Wireless Networks
9.12 Secure Routing in Ad Hoc Wireless Networks
9.12.1 Requirements of a Secure Routing Protocol for Ad Hoc Wireless Networks
9.12.2 Security-Aware Ad Hoc Routing Protocol
9.12.3 Secure Efficient Ad Hoc Distance Vector Routing Protocol
9.12.4 Authenticated Routing for Ad Hoc Networks
9.12.5 Security-Aware AODV Protocol
10 QUALITY OF SERVICE IN AD HOC WIRELESS NETWORKS
10.1.1 Real-Time Traffic Support in Ad Hoc Wireless Networks
10.1.2 QoS Parameters in Ad Hoc Wireless Networks
10.2 Issues and Challenges in Providing QoS in Ad Hoc Wireless Networks
10.3 Classifications of QoS Solutions
10.3.1 Classifications of QoS Approaches
10.3.2 Layer-Wise Classification of Existing QoS Solutions
10.5.2 Ticket-Based QoS Routing Protocol
10.5.3 Predictive Location-Based QoS Routing Protocol
10.5.4 Trigger-Based Distributed QoS Routing Protocol
10.5.5 QoS-Enabled Ad Hoc On-Demand Distance Vector Routing Protocol
10.5.6 Bandwidth Routing Protocol
10.5.7 On-Demand QoS Routing Protocol
10.5.8 On-Demand Link-State Multipath QoS Routing Protocol
10.5.9 Asynchronous Slot Allocation Strategies
10.6 QoS Frameworks for Ad Hoc Wireless Networks
10.6.2 QoS Resource Reservation Signaling
11 ENERGY MANAGEMENT IN AD HOC WIRELESS NETWORKS
11.2 Need for Energy Management in Ad Hoc Wireless Networks
11.3 Classification of Energy Management Schemes
11.4 Battery Management Schemes
11.4.1 Overview of Battery Characteristics
11.4.2 Device-Dependent Schemes
11.4.3 Data Link Layer Solutions
11.4.4 Network Layer Solutions
11.5 Transmission Power Management Schemes
11.5.1 Data Link Layer Solutions
11.5.2 Network Layer Solutions
11.6 System Power Management Schemes
11.6.1 Processor Power Management Schemes
11.6.2 Device Power Management Schemes
12.1.1 Applications of Sensor Networks
12.1.2 Comparison with Ad Hoc Wireless Networks
12.1.3 Issues and Challenges in Designing a Sensor Network
12.2 Sensor Network Architecture
12.3.4 Sequential Assignment Routing
12.3.6 Sensor Protocols for Information via Negotiation
12.3.9 Small Minimum Energy Communication Network
12.4.2 Power-Efficient Gathering for Sensor Information Systems
12.4.4 Chain-Based Three-Level Scheme
12.5 MAC Protocols for Sensor Networks
12.5.1 Self-Organizing MAC for Sensor Networks and Eavesdrop and Register
12.5.3 CSMA-Based MAC Protocols
12.6.2 Sensor Network Localization
12.7 Quality of a Sensor Network
12.9.1 Energy-Efficient Design
12.9.5 Real-Time Communication
13.2 Next-Generation Hybrid Wireless Architectures
13.2.1 Classification of Hybrid Architectures
13.2.6 The SOPRANO Architecture
13.2.10 The DWiLL Architecture
13.2.12 A Qualitative Comparison
13.2.13 Open Issues in the Next-Generation Hybrid Architectures
13.3 Routing in Hybrid Wireless Networks
13.3.1 Base-Assisted Ad Hoc Routing
13.3.2 Base-Driven Multi-Hop Bridging Routing Protocol
13.4 Pricing in Multi-Hop Wireless Networks
13.4.1 Issues in Pricing in Multi-Hop Wireless Networks
13.4.2 Pricing in Military Ad Hoc Wireless Networks
13.4.3 Pricing in Multi-Hop Wireless WANs
13.4.4 Pricing in Ad Hoc Wireless Networks
13.4.5 Pricing in Hybrid Wireless Networks
13.4.6 Open Issues in Pricing for Multi-Hop Wireless Networks
13.5 Power Control Schemes in Hybrid Wireless Networks
13.5.1 Issues in Using Variable Power in IEEE 802.11
13.5.2 Power Optimization Scheme for Hybrid Wireless Networks
13.6 Load Balancing in Hybrid Wireless Networks
13.6.1 Preferred Ring-Based Routing Schemes
13.6.2 Load Adaptive Routing Schemes for Throughput Enhancement and Load Balancing
14 RECENT ADVANCES IN WIRELESS NETWORKS
14.2 Ultra-Wide-Band Radio Communication
14.2.1 Operation of UWB Systems
14.2.2 A Comparison of UWB with Other Technologies
14.2.4 Advantages and Disadvantages of UWB
14.3 Wireless Fidelity Systems
14.3.1 The Service Provider Models for Wi-Fi Systems
14.3.2 Issues in Wi-Fi Systems
14.3.3 Interoperability of Wi-Fi Systems and WWANs
14.3.4 Pricing/Billing Issues in Wi-Fi Systems
14.3.5 Pricing/Billing Schemes for Wi-Fi Systems
14.4 Optical Wireless Networks
14.4.1 Short-Range Infrared Communication
14.4.3 Optical Wireless WDM LAN
14.5 The Multimode 802.11 — IEEE 802.11a/b/g
14.5.1 Software Radio-Based Multimode Systems
14.6 The Meghadoot Architecture
PREFACE
In the last few years, there has been a big interest in ad hoc wireless networks as they have tremendous military and commercial potential. An ad hoc wireless network is a wireless network, comprised of mobile computing devices that use wireless transmission for communication, having no fixed infrastructure (a central administration such as a base station in a cellular wireless network or an access point in a wireless local area network). The mobile devices also serve as routers due to the limited range of wireless transmission of these devices, that is, several devices may need to route or relay a packet before it reaches its final destination. Ad hoc wireless networks can be deployed quickly anywhere and anytime as they eliminate the complexity of infrastructure setup. These networks find applications in several areas. Some of these include: military communications (establishing communication among a group of soldiers for tactical operations when setting up a fixed wireless communication infrastructure in enemy territories or in inhospitable terrains may not be possible), emergency systems (for example, establishing communication among rescue personnel in disaster-affected areas) that need quick deployment of a network, collaborative and distributed computing, wireless mesh networks, wireless sensor networks, and hybrid (integrated cellular and ad hoc) wireless networks.
The purpose of this book is to provide students, researchers, network engineers, and network managers with an expert guide to the fundamental concepts, design issues, and solutions to the issues — architectures and protocols — and the state-of-the-art research developments in ad hoc wireless networking. A unique feature of the book is that it deals with the entire spectrum of issues that influence the design and performance of ad hoc wireless networks, and solutions to the issues, with easy-to-understand illustrative examples highlighting the intuition behind each of the solutions.
This book, organized into fourteen chapters, each covering a unique topic in detail, first presents (in Chapters 1-4) the fundamental topics involved with wireless networking such as wireless communications technology, wireless LANs and PANs, wireless WANs and MANs, and wireless Internet. It then covers all important design issues (in Chapters 5-11) — medium access control, routing, multicasting, transport layer, security, quality of service provisioning, energy management — in ad hoc wireless networking in considerable depth. Finally, some recent related important topics covered in this book (in Chapters 12-14) include wireless sensor networks, hybrid wireless architectures, pricing in multihop wireless networks, ultra wideband technology, Wi-Fi systems, optical wireless networks, and Multimode 802.11.
The book is intended as a textbook for senior undergraduate and graduate-level courses on ad hoc wireless networks. It can also be used as a supplementary textbook for undergraduate courses on wireless networks, wireless/mobile communications, mobile computing, and computer networks. The exercise problems provided at the end of each chapter add strength to the book. A solutions manual for instructors is available from Prentice Hall. The book is a useful resource for the students and researchers to learn all about ad hoc wireless networking and further their research work. In addition, the book will be valuable to professionals in the field of computer/wireless networking.
We owe our deepest gratitude to Karthigeyan, Jayashree, and Archana for reading line by line all the chapters and suggesting ways to correct technical and presentation problems. We wish to express our thanks to the following HPCN lab students who have contributed mightily to this book writing project: Archana, Bhaya Gaurav Ravindra, Bheemarjun, Jagadeesan, Jayashree, Karthigeyan, Rajendra Singh Sisodia, Srinivas, Subir Kumar Das, Vidhyashankar, and Vyas Sekar. Raj Kumar drew all the illustrations and we thank him for his excellent work. We appreciate the efforts of Steven M. Hirschman, Irving E. Hodnett, and Shivkumar Kalyanaraman in reviewing our draft manuscript and suggesting improvements. We would like to gratefully acknowledge the help rendered by the Indian Institute of Technology (IIT), Madras, especially for creating an excellent working environment, the Department of Science and Technology, New Delhi, and the Curriculum Development Cell of the Centre for Continuing Education, IIT Madras for providing the financial aid for writing this book. Infosys Technologies Ltd., Bangalore, provided financial support to the second author for wireless networking research over the last four years, and he is indebted to Infosys for the same. We are thankful to Bernard Goodwin and his colleagues at Prentice Hall for their excellent work in producing this book. Last though not least, we acknowledge the love and affection from our families. This project would never have been successfully completed but for their understanding and patience.
We have taken reasonable care in eliminating typographical or other errors that might have crept into the book. We encourage you to send your comments and suggestions to us via email. We appreciate your feedback and hope you enjoy reading the book.
C. Siva Ram Murthy, [email protected]
B. S. Manoj, [email protected]