Multihop Wireless Networks E-Book

Kai Zeng

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wireless Communications and Mobile Computing
• Sprache: Englisch

Seitenzahl: 538

Veröffentlichungsjahr: 2011

Beschreibung

This book provides an introduction to opportunistic routing an emerging technology designed to improve the packet forwarding reliability, network capacity and energy efficiency of multihop wireless networks This book presents a comprehensive background to the technological challenges lying behind opportunistic routing. The authors cover many fundamental research issues for this new concept, including the basic principles, performance limit and performance improvement of opportunistic routing compared to traditional routing, energy efficiency and distributed opportunistic routing protocol design, geographic opportunistic routing, opportunistic broadcasting, and security issues associated with opportunistic routing, etc. Furthermore, the authors discuss technologies such as multi-rate, multi-channel, multi-radio wireless communications, energy detection, channel measurement, etc. The book brings together all the new results on this topic in a systematic, coherent and unified presentation and provides a much needed comprehensive introduction to this topic. Key Features: * Addresses opportunistic routing, an emerging technology designed to improve the packet forwarding reliability, network capacity and energy efficiency of multihop wireless networks * Discusses the technological challenges lying behind this new technology, and covers a wide range of practical implementation issues * Explores many fundamental research issues for this new concept, including the basic principles of opportunistic routing, performance limits and performance improvement, and compares them to traditional routing (e.g. energy efficiency and distributed opportunistic routing protocol design, broadcasting, and security issues) * Covers technologies such as multi-rate, multi-channel, multi-radio wireless communications, energy detection, channel measurement, etc. This book provides an invaluable reference for researchers working in the field of wireless networks and wireless communications, and Wireless professionals. Graduate students will also find this book of interest.

Leseprobe

Table of Contents

Series Page

Title Page

Copyright

About the Series Editors

Preface

List of Abbreviations

Chapter 1: Introduction

1.1 Multihop Wireless Networks

1.2 Routing Challenges in MWNs

1.3 Routing Techniques in MWNs

1.4 Related Work

1.5 Book Contribution

1.6 System Model and Assumptions

References

Chapter 2: Taxonomy of Opportunistic Routing: Principles and Behaviors

2.1 EPA Generalization

2.2 Principles of Local Behavior of GOR

2.3 Least Cost Opportunistic Routing

2.4 Conclusions

References

Chapter 3: Energy Efficiency of Geographic Opportunistic Routing

3.1 EGOR Problem Formulation

3.2 Efficient Localized Node-Selection Algorithms

3.3 Energy-Efficient Geographic Opportunistic Routing

3.4 Performance Evaluation

3.5 Conclusion

References

Chapter 4: Capacity of Multirate Opportunistic Routing

4.1 Computing Throughput Bound of OR

4.2 Impact of Transmission Rate and Forwarding Strategy on Throughput

4.3 Rate and Candidate Selection Schemes

4.4 Performance Evaluation

4.5 Conclusion

References

Chapter 5: Multiradio Multichannel Opportunistic Routing

5.1 Introduction

5.2 System Model and Opportunistic Routing Primer

5.3 Problem Formulation

5.4 Forwarding Priority Scheduling

5.5 Performance Evaluation

5.6 Conclusions and Future Work

References

Chapter 6: Medium Access Control for Opportunistic Routing—Candidate Coordination

6.1 Existing Candidate Coordination Schemes

6.2 Design and Analysis of FSA

6.3 Simulation Results and Evaluation

6.4 Conclusions

References

Chapter 7: Integration of Opportunistic Routing and Network Coding

7.1 A Brief Review of MORE

7.2 Mobile Content Distribution in VANETs

7.3 Related Works on Mobile Content Distribution in VANETs

7.4 Background on Symbol-Level Network Coding

7.5 CodeOn: a Cooperative Popular Content Broadcast Scheme for VANETs Based on SLNC

7.6 CodePlay: a Live Multimedia Streaming Scheme for VANETs Based on SLNC

7.7 Conclusion

References

Chapter 8: Multirate Geographic Opportunistic Routing Protocol Design

8.1 System Model

8.2 Impact of Transmission Rate and Forwarding Strategy on OR Performance

8.3 Opportunistic Effective One-Hop Throughput (OEOT)

8.4 Heuristic Candidate Selection Algorithm

8.5 Multirate Link-Quality Measurement

8.6 Performance Evaluation

8.7 Conclusion

References

Chapter 9: Opportunistic Routing Security

9.1 Attack on Link Quality Measurement

9.2 Attacks on Opportunistic Coordination Protocols

9.3 Resilience to Packet-Dropping Attack

9.4 Conclusion

References

Chapter 10: Opportunistic Broadcasts in Vehicular Networks

10.1 Related Works on Broadcasts in General MWNs

10.2 Related Works on Broadcasts in VANETs

10.3 Problem Statement

10.4 Overview of OppCast

10.5 OppCast: Main Design

10.6 Parameter Optimization

10.7 Performance Evaluation

10.8 Conclusion

References

Chapter 11: Conclusions and Future Research

11.1 Summary

11.2 Future Research Directions

References

Index

Series Page

Wiley Series on Wireless Communications and Mobile Computing

Series Editors: Dr Xuemin (Sherman) Shen, University of Waterloo, Canada

Dr Yi Pan, Georgia State University, USA

The “Wiley Series on Wireless Communications and Mobile Computing” is a series of comprehensive, practical and timely books on wireless communication and network systems. The series focuses on topics ranging from wireless communication and coding theory to wireless applications and pervasive computing. The books provide engineers and other technical professionals, researchers, educators, and advanced students in these fields with invaluable insight into the latest developments and cutting-edge research.

Other titles in the series:

Misic and Misic, Wireless Personal Area Networks: Performance, Interconnection, and Security with IEEE 802.15.4, January 2008, 978-0-470-51847-2

Takagi and Walke, Spectrum Requirement Planning in Wireless Communications: Model and Methodology for IMT-Advanced, April 2008, 978-0-470-98647-9

Pérez-Fontán and Espiñeira, Modeling the Wireless Propagation Channel: A simulation approach with MATLAB®, August 2008, 978-0-470-72785-0

Ippolito, Satellite Communications Systems Engineering: Atmospheric Effects, Satellite Link Design and System Performance, August 2008, 978-0-470-72527-6

Lin and Sou, Charging for Mobile All-IP Telecommunications, September 2008, 978-0-470-77565-3

Myung and Goodman, Single Carrier FDMA: A New Air Interface for Long Term Evolution, October 2008, 978-0-470-72449-1

Wang, Kondi, Luthra and Ci, 4G Wireless Video Communications, April 2009, 978-0-470-77307-9

Cai, Shen and Mark, Multimedia Services in Wireless Internet: Modeling and Analysis, June 2009, 978-0-470-77065-8

Stojmenovic, Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication, February 2010, 978-0-470-17082-3

Liu and Weiss, Wideband Beamforming: Concepts and Techniques, March 2010, 978-0-470-71392-1

Riccharia and Westbrook, Satellite Systems for Personal Applications: Concepts and Technology, July 2010, 978-0-470-71428-7

Qian, Muller and Chen, Security in Wireless Networks and Systems, February 2013, 978-0-470-512128

This edition first published 2011

© 2011 John Wiley & Sons Ltd.

Registered office

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom.

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

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, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on 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 should be sought.

Library of Congress Cataloging-in-Publication Data

Zeng, Kai.

Multihop wireless networks : opportunistic routing / Kai Zeng, Wenjing Lou, Ming Li.

p. cm.

Includes bibliographical references and index.

ISBN 978-0-470-66617-3 (hardback)

1. Ad hoc networks (Computer networks) 2. Radio relay systems. I. Lou, Wenjing. II. Li, Ming, 1985- III. Title.

TK5105.77.Z46 2011

621.387'82–22

2011007718

A catalogue record for this book is available from the British Library.

Print ISBN: 978-0-470-66617-3

ePDF ISBN: 978-1-119-97361-4

oBook ISBN: 978-1-119-97360-7

ePub ISBN: 978-1-119-97429-1

eMobi ISBN: 978-1-119-97430-7

About the Series Editors

Xuemin (Sherman) Shen (M'97-SM'02) received his B.Sc degree in electrical engineering from Dalian Maritime University, China in 1982, and his M.Sc. and Ph.D. degrees (both in electrical engineering) from Rutgers University, New Jersey, USA, in 1987 and 1990 respectively. He is a Professor and University Research Chair, and the Associate Chair for Graduate Studies, Department of Electrical and Computer Engineering, University of Waterloo, Canada. His research focuses on mobility and resource management in interconnected wireless/wired networks, UWB wireless communications systems, wireless security, and ad hoc and sensor networks. He is a co-author of three books, and has published more than 300 papers and book chapters in wireless communications and networks, control and filtering. Dr. Shen serves as a founding area editor for IEEE Transactions on Wireless Communications; Editor-in-Chief for Peer-to-Peer Networking and Application; Associate Editor for IEEE Transactions on Vehicular Technology; KICS/IEEE Journal of Communications and Networks, Computer Networks; ACM/Wireless Networks; and Wireless Communications and Mobile Computing (Wiley), etc. He has also served as Guest Editor for IEEE JSAC, IEEE Wireless Communications, and IEEE Communications Magazine. Dr. Shen received the Excellent Graduate Supervision Award in 2006, and the Outstanding Performance Award in 2004 from the University of Waterloo, the Premier's Research Excellence Award (PREA) in 2003 from the Province of Ontario, Canada, and the Distinguished Performance Award in 2002 from the Faculty of Engineering, University of Waterloo. Dr. Shen is a registered Professional Engineer of Ontario, Canada.

Dr. Yi Pan is the Chair and a Professor in the Department of Computer Science at Georgia State University, USA. Dr. Pan received his B.Eng. and M.Eng. degrees in computer engineering from Tsinghua University, China, in 1982 and 1984, respectively, and his Ph.D. degree in computer science from the University of Pittsburgh, USA, in 1991. Dr. Pan's research interests include parallel and distributed computing, optical networks, wireless networks, and bioinformatics. Dr. Pan has published more than 100 journal papers with over 30 papers published in various IEEE journals. In addition, he has published over 130 papers in refereed conferences (including IPDPS, ICPP, ICDCS, INFOCOM, and GLOBECOM). He has also co-edited over 30 books. Dr. Pan has served as an editor-in-chief or an editorial board member for 15 journals including five IEEE Transactions and has organized many international conferences and workshops. Dr. Pan has delivered over 10 keynote speeches at many international conferences. Dr. Pan is an IEEE Distinguished Speaker (2000–2), a Yamacraw Distinguished Speaker (2002), and a Shell Oil Colloquium Speaker (2002). He is listed in Men of Achievement, Who's Who in America, Who's Who in American Education, Who's Who in Computational Science and Engineering, and Who's Who of Asian Americans.

Preface

Advances in communication and networking technologies are rapidly making ubiquitous network connectivity a reality. Wireless networks are indispensable for supporting such access anywhere and at any time. Among various types of wireless networks, multihop wireless networks (MWNs) have been attracting increasing attention for decades due to its broad civilian and military applications. Basically, a MWN is a network of nodes connected by wireless communication links. Due to the limited transmission range of the radio, many pairs of nodes in MWNs may not be able to communicate directly, hence they need other intermediate nodes to forward packets for them. Routing in such networks is an important issue and it poses great challenges.

On the one hand, due to its open-air nature, the wireless environment presents great challenges when attempting to ensure good routing performance. The wireless channel is unreliable due to fading and interference, which makes it hard to maintain a quality path between a source and a destination. A node's mobility also incurs frequent topology changes, which bring significant overheads on maintaining and recalculating paths. Furthermore, mobile devices and sensors are usually constrained by battery capacity and communication and computation capability, which imposes limitations on the functionality of routing protocols. On the other hand, the wireless medium possesses inherent unique characteristics, which can be exploited to enhance transmission reliability and routing performance. Opportunistic routing (OR) is one promising technique that takes advantages of the spacial diversity and broadcast nature of the wireless medium to improve the packet-forwarding reliability in multihop wireless networks. It combats the unreliable wireless links by involving multiple neighboring nodes (forwarding candidates) for packet relay. This book studies the properties, energy efficiency, capacity, throughput, protocol design and security issues related to OR in multihop wireless networks.

This book is intended for networking professionals working in wireless networks and communications, who are familiar with the fundamentals of networking and wireless communications. It may also be used as a supplement to graduate courses in wireless networking, mobile computing, and wireless communications.

The contents of each chapter are described as follows.

Chapter 1 presents the case for opportunistic routing and related work. We first introduce the background of multihop wireless networks (mesh networks, sensor networks, mobile ad hoc networks, vehicular networks, etc.). Next, we discuss general wireless multihop routing, including traditional routing (AODV, DSR, etc.), geographic routing, context-based routing and opportunistic routing. We will discuss the motivation of these routing techniques, how they evolved, and their advantages and disadvantages. We will then discuss related opportunistic and collaborative techniques, including cooperative communication, opportunistic scheduling, network coding and multiple access point (AP) collaboration. We will also introduce related issues about opportunistic routing, including capacity studies of multihop wireless networks, multirate routing, energy-efficient routing, and link quality measurement, etc.

Chapter 2 of this book presents the principles and properties of the local behaviors of opportunistic routing (including geographic and link state based opportunistic routing). We will demonstrate how the performance gain changes according to the selection, prioritization, and coordination of forwarding candidates in opportunistic routing. We will discuss in what scenario or situation, opportunistic routing will work or make sense. We will also present two polynomial algorithms to compute least cost opportunistic routing paths (anypath), and introduce properties of least cost anypath.

Chapter 3 of this book studies the energy efficiency of geographic opportunistic routing (GOR). First, we motivate the energy efficiency issues of opportunistic routing in the context of sensor networks. Next, we propose a metric, Expected Packet Advancement (EPA) per unit energy consumption, in order to balance the packet advancement, reliability and energy consumption of GOR. By leveraging the proved principles in Chapter 2, we then propose two efficient algorithms that select a feasible candidate set that maximizes this local metric. We validate our analysis results by simulations and justify the effectiveness of the new metric by comparing the performance of our GOR with those of the existing geographic and opportunistic routing schemes.

Chapter 4 of this book analyzes the throughput bound and capacity of opportunistic routing given the routing strategy, i.e. the forwarding candidates of each node and the corresponding relay priority. We will first give a brief introduction on computing end-to-end throughput of traditional routing and explain why the corresponding methodology cannot directly apply to opportunistic routing, which motivates the proposed framework and methodology. The maximum end-to-end throughput problem is formulated as a maximum-flow linear programming (LP) problem subject to the constraints of forwarding candidate set conflicts. The methodology establishes a theoretical foundation for the evaluation of the performance limits of variants of opportunistic routing protocols and strategies.

Chapter 5 extends the framework proposed in Chapter 4 to deal with dynamic opportunistic routing strategies and multi-radio, multi-channel scenario. An LP approach and a heuristic algorithm is proposed to obtain an opportunistic forwarding strategy scheduling that satisfies a traffic demand vector for a hyperlink, which contains all the outgoing links from a transmitter to all its forwarding candidates.

Chapter 6 of the book investigates the state-of-the-art of the candidate coordination schemes of opportunistic routing at the medium access control layer. These schemes include GeRaF collision avoidance MAC, contention-based forwarding, ExOR batch-based MAC, slotted acknowledgment (ACK), and compressed slotted ACK. A new scheme, called “fast slotted acknowledgment (FSA)”, is described in detail. The scheme adopts a single ACK to confirm the successful reception and suppress other candidates' attempts to forward the data packet with the help of a channel-sensing technique.

Chapter 7 shows how network coding can help ease the candidate coordination in opportunistic routing. It will include an introduction on network coding, how it can help ease the candidate coordination, and on integrating opportunistic routing/broadcast with network coding. A classical work integrating opportunistic routing and network coding, MORE, will be introduced. Recent advancements on integrating symbol-level network coding and opportunistic routing in wireless broadcast are introduced.

Chapter 8 of this book studies the impacts of multirate, candidate selection, prioritization, and coordination on the throughput of GOR under a contention-based medium-access scenario. It will also introduce distributed algorithms to compute the optimal path and transmission rate in multirate opportunistic routing.

Chapter 9 of the book discusses possible attacks on opportunistic routing and countermeasures. We analyze the security vulnerabilities of the existing link quality-measurement mechanisms, and their impacts on opportunistic routing and traditional routing. We present a broadcast-based secure link quality measurement mechanism that prevents a neighboring node from maliciously claiming a higher measurement result. The secure link quality measurement helps to secure the link-state-based opportunistic routing and traditional routing.

Chapter 10 studies the opportunistic broadcast in vehicular networks. Traditional connected dominant set-based broadcast or multi-point relay-based broadcast both suffer from unreliable wireless links in the similar way as that in traditional unicast routing. The broadcast performance can also be improved by introducing the concept of opportunistic forwarding.

Chapter 11 presents the conclusion of this book and discusses some future research topics related to opportunistic routing.

List of Abbreviations

ACKACKnowledgementAODVAd hoc On-Demand Distance Vector RoutingAoIArea of InterestAPAccess PointAPRPAccumulated Packet Reception ProbabilityARQAutomatic Repeat reQuestBACKBroadcast AcknowledgementBBTBroadcast Backoff TimerCBDContention-Based DisseminationCBFContention-Based ForwardingCBRConstant Bit RateCCAClear Channel AssessmentCCTSConservative Concurrent Transmission SetCDSConnected Dominant SetCLPCoordinated Local PushCRCommunication RangeCSACompressed Slotted AcknowledgmentCSMA-CACarrier Sensing Multiple Access with Collision AvoidanceCTFClear-To-ForwardCTSConcurrent Transmission Set/Clear-To-SendDDBDynamic Delayed BroadcastingDIFSDistributed Inter-Frame SpaceDSDVDestination-Sequenced Distance Vector routingDSRDynamic Source RoutingDSRCDedicated Short Range CommunicationsDTNDelay/Disruption Tolerant NetworkEARExpected Advancement RateECCError Correction CodingEDEnergy DetectionEGOREnergy-efficient Geographic Opportunistic RoutingEMDVEmergency Message Dissemination for Vehicular environmentsEMTExpected Medium TimeEOTExpected One-hop ThroughputEOTXExpected Opportunistic Transmission CountEPAExpected Packet AdvancementETFExpected number of Transmissions over Forward linksETTExpected Transmission TimeETXExpected Transmission countEWMAExponentially Weighted Moving AverageExORExtremely Opportunistic RoutingFFDFast-forward-DisseminationFPSPForwarding Priority Scheduling ProblemFRForwarding RangeFSAFast Slotted AcknowledgementFSRFisheye State RoutingGCTSGreedy Concurrent Transmission SetGeRaFGeographic Random ForwardingGORGeographic Opportunistic RoutingGPSGlobal Positioning SystemGRGeographic RoutingGTRGeographic Traditional RoutingIRInterested RegionITSIntelligent Transportation SystemsLCORLeast Cost Opportunistic RoutingLDPCLow-Density Parity-CheckLMSLive Multimedia StreamingLMTORLeast Medium Time Opportunistic RoutingLPLinear ProgrammingLQMLink Quality MeasurementLRRLocal Round-Robin SchedulingMACMedium Assess ControlMANETMobile Ad hoc NETworkMCDMobile Content DistributionMCDSMinimum Connected Dominant SetMFRMakeup-For-ReliabilityMGORMultirate Geographic Opportunistic RoutingMIBManagement Information BaseMIMOMultiple-Input Multiple-OutputMPRMultipoint RelayMRDMulti-Radio DiversityMTMMedium Time MetricMWNMultihop Wireless NetworkNADVNormalized ADVanceNAVNetwork Allocation VectorNCNetwork CodingNCDDNetwork Coding based Data DisseminationOBCFOpportunistic Broadcast Coordination FunctionOBUOn-Board UnitOB-VANOpportunistic Broadcast in VANETsOEOTOpportunistic Effective One-hop ThroughputOETTOpportunistic Expected Transmission TimeOFDMOrthogonal Frequency-Division MultiplexingOLRROpportunistic Local Round-Robin schedulingOLSROptimized Link State RoutingOppCastOpportunistic BroadcastOROpportunistic RoutingPCDPopular Content DistributionPDPreamble DetectionPDRPacket Delivery RatioPLNCPacket Level Network CodingPRPPacket Reception ProbabilityPRRPacket Reception RatioQoSQuality of ServiceRCRRelay Candidate RegionRERRRoute ErrorRLNCRandom Linear Network CodingRREPRoute ReplyRREQRoute RequestRSSIReceived Signal Strength IndicatorRSURoad Side UnitRTERReception to Transmission Energy RatioRTFReady-To-ForwardRTSReady-To-SendSASlotted AcknowledgmentSAVSelf Allocation VectorSBSmart BroadcastSIFSShort Inter-Frame SpaceSINRSignal to Interference and Noise RatioSLNCSymbol Level Network CodingSLQMSecure Link Quality MeasurementSNRSignal to Noise RatioTCTopology ControlTCPTransport Control ProtocolTORATemporally-Ordered Routing AlgorithmTRTraditional RoutingUDGUnit Disk GraphUMBUrban Multihop Broadcast protocolVANETVehicular Ad Hoc NetworkWCETTWeighted Cumulative Expected Transmission TimeWLANWireless Local Area NetworkWMWarning MessageWMNWireless Mesh NetworkWSNWireless Sensor NetworkXORExclusive OR

Chapter 1

Introduction

This chapter presents the case for opportunistic routing and related work. We will first introduce the background of multihop wireless networks (mesh networks, sensor networks, mobile ad hoc networks, vehicular ad hoc networks, etc.). We then point out the routing challenges in multihop wireless networks. Secondly, we discuss general wireless multihop routing, including traditional routing (AODV, DSR, etc.), geographic routing, context-based routing and opportunistic routing. We will discuss the motivation of these routing techniques, how they evolved, and their advantages and disadvantages. We will then discuss related opportunistic and collaborative techniques, including cooperative communication, opportunistic scheduling, network coding, multiple AP collaboration, etc. This will help to put opportunistic routing in perspective. We will also introduce related issues about opportunistic routing, including capacity studies of multihop wireless networks, multirate routing, energy-efficient routing, and link-quality measurement, etc.

1.1 Multihop Wireless Networks

A multihop wireless network (MWN) is a network of nodes (e.g. computers) connected by wireless communication links. The links are usually implemented with digital packet radios. Due to the limited transmission range of the radio, many pairs of nodes in MWNs may not be able to communicate directly; hence they may need other intermediate nodes to forward packets for them. Multihop wireless networks have broad military and civilian applications in many critical situations. They have received increasing attention in the past decade due to their broad applications and easy deployment at low cost without relying on existing infrastructure (Akyildiz and Kasimoglu 2004; Akyildiz et al. 2002, 2005; Cerpa et al. 2001; Chong and Kumar 2003; Estrin et al. 2002; Lorincz et al. 2004). Different names are used to refer to them in different scenarios.

Mobile ad hoc Networks (MANETs)

Generally speaking, a mobile ad hoc network (MANET) is a self-configuring network of mobile devices connected by wireless links. Each device in a MANET is free to move independently in any direction. So the node-to-node connection and network topology will change frequently. The primary challenge in MANETs is continuously to maintain the routing information at each node required to properly route traffic. The applications of MANETs include search-and-rescue operations. Such scenarios are characterized by a lack of installed communications infrastructure because all the equipment might already be destroyed or the region could be too remote. MANETs can also provide communications between autonomous vehicles, aircraft and ground troops in the battlefield where a fixed communication infrastructure is always unavailable and infeasible.