Mobile ad hoc networks: energy-efficient real-time data communications

MOBILE AD HOC NETWORKS

Mobile Ad Hoc Networks

Energy-Efficient Real-Time Data Communications

BULENT TAVLI

University of Rochester, NY, U.S.A.

and

WENDI HEINZELMAN

University of Rochester, NY, U.S.A.

by

A C.I.P. Catalogue record for this book is available from the Library of Congress.

ISBN-10 1-4020-4632-4 (HB)

ISBN-13 978-1-4020-4632-2 (HB)

ISBN-10 1-4020-4633-2 ( e-book)

ISBN-13 978-1-4020-4633-9 (e-book)

Published by Springer,

P.O. Box 17, 3300 AA Dordrecht, The Netherlands.

www.springer.com

Printed on acid-free paper

All Rights Reserved

© 2006 Springer

No part of this work may be reproduced, stored in a retrieval system, or transmitted

in any form or by any means, electronic, mechanical, photocopying, microfilming, recording

or otherwise, without written permission from the Publisher, with the exception

of any material supplied specifically for the purpose of being entered

and executed on a computer system, for exclusive use by the purchaser of the work.

Printed in the Netherlands.

To our families

Contents

Dedication v

List of Figures xi

List of Tables

Preface xxiii

1. INTRODUCTION 1

1.1 Characteristics of MANETs 2

1.2 Importance of QoS and Energy Efficiency in MANETs 4

1.3 Scope and Novelty of the Book 5

1.4 High Level Overview of the Book 7

2. MANET FUNDAMENTALS 9

2.1 Performance Metrics 9

2.2 The Layered Communication Network 11

2.3 Cross-layer Design 23

2.4 Mobility 26

3. MEDIUM ACCESS CONTROL 31

3.1 Fixed Assignment MAC Protocols 31

3.2 Random Access MAC Protocols 37

4. ROUTING 47

4.1 Unicast Routing 47

4.2 Multicast Routing 48

4.3 Broadcasting Routing 50

4.4 Hierarchically Organized Networks 51

xix

viii

5. ENERGY EFFICIENCY AND QOS 59

5.1 Energy Efficiency 59

5.2 Quality of Service 67

6. SH-TRACE PROTOCOL ARCHITECTURE 71

6.1 Introduction 71

6.2 Protocol Architecture 73

6.3 Simulations and Analysis 77

6.4 Discussion 96

6.5 Summary 98

7. MH-TRACE PROTOCOL ARCHITECTURE 99

7.1 Introduction 99

7.2 Protocol Architecture 100

7.3 Simulations and Analysis 108

7.4 Discussion 123

7.5 Summary 124

8. EFFECTS OF CHANNEL ERRORS 125

8.1 Introduction 125

8.2 Related Work 128

8.3 Analytical Model 129

8.4 Simulations and Analysis 138

8.5 Summary 146

9. REAL-TIME DATA BROADCASTING 147

9.1 Introduction 147

9.2 Broadcast Architectures 148

9.3 Simulation Environment 152

9.4 Low Traffic Regime 156

9.5 High Traffic Regime 167

9.6 Summary 172

10. NB-TRACE PROTOCOL ARCHITECTURE 175

10.1 Introduction 175

10.2 Protocol Architecture 175

10.3 Simulations and Analysis 185

10.4 Summary 198

Contents

Contents ix

11. MC-TRACE PROTOCOL ARCHITECTURE 199

11.1 Introduction 199

11.2 Protocol Architecture 200

11.3 Simulations and Analysis 208

11.4 Summary 210

12. CONCLUSIONS AND FUTURE RESEARCH DIRECTIONS 211

12.1 Conclusions 211

12.2 Future Research Directions 218

Bibliography 221

Appendices

A Multi-Stage Contention with Feedback 235

A.1 Generic DR-TDMA Frame Structure 236

A.2 Single-Stage S-ALOHA Contention 236

A.3 Multi-Stage Contention 237

A.4 Optimal Multi-Stage Contention 238

A.5 Discussion 239

A.6 Summary 241

B Effects of Clusterhead Separation on MH-TRACE 243

B.1 Modified Cluster Creation and Maintenance Algorithms 243

B.2 Simulation Results and Discussion 244

B.3 Summary 251

C Broadcast Capacity of Wireless Ad Hoc Networks 253

C.1 Background 253

C.2 Upper Bound on Broadcast Capacity 255

C.3 Summary 256

D Glossary of Terms 257

Index 261

About The Authors 265

235

List of Figures

1.1 TRACE family of protocol architectures. 8

2.1 MANET protocol performance metrics. 10

2.2 TCP/IP reference model. 12

2.3 Free Space and Two-Ray Ground propagation models. 14

2.4 Illustration of ASK, BFSK, and BPSK. 16

2.5 Successive encapsulation. 18

2.6 Block diagram of a data transmission system. 18

2.7 Illustration of unicast, multicast, and broadcast routing.

S and D represent the source and destination nodes,

respectively. 21

2.8 UDP and TCP packet formats. 22

2.9 Audio communications through the network stack. 24

2.10

design where application and transport layers are

are merged. 25

2.11 Average node speed for a simulation scenario created

over 1 km by 1 km area. The node speeds are chosen

randomly from [0, 5 m/s] with zero pause time. 27

2.12

80 nodes over 1 km by 1 km area. The node speeds are

28

The left column shows a conventional layered protocol

stack. The middle column shows a cross-layer design,

where layers share information while keeping the layers

intact. The right column shows another cross-layer

combined into a single entity and network and MAC layers

by the random waypoint mobility model with 80 nodes

Node distribution produced at 1000 s of the mobility

scenario by the random waypoint mobility model with

chosen randomly from [0, 5 m/s] with zero pause time.

xii

2.13

over a 500 m by 500 m grid. The lower-left corner of

corner of the figure. 29

3.1 Node B is closer to node C than node A. Simultaneous

by node B at node C’s receiver (PB,C) is much higher

than that of node A (PA,C). This effect is known as 32

3.2 Fixed assignment medium access control protocols:

Division Multiple Access (FDMA), (c) Code Division

Multiple Access (CDMA). 32

3.3 Digital European Cordless Telephone (DECT) uses

TDMA as the MAC layer.

the mobile nodes) and 12 are used for uplink (i.e., from

the mobile nodes to the base station). 33

3.4 Global System for Mobile communication (GSM) uses

FDMA as the MAC layer. The frequency band is

128 channels for downlink), and the carriers are

34

3.5 Illustration of Frequency Hopping Spread Spectrum (FHSS). 36

3.6 ALOHA medium access. 37

3.7 ALOHA and Slotted ALOHA throughput versus

38

3.8 Slotted ALOHA medium access. 38

3.9 Comparison of the throughput efficiency versus offered

load for the ALOHA and CSMA schemes. The

3.10 Star topology network—the base station is in the center. 40

3.11 Fully connected single-hop wireless network. 41

3.12 Illustration of transmit and carrier sense regions. 42

“ ”

List of Figures

Combined snapshots of node positions in time plotted

the figure is the snapshot at time 0.0 s. The upper-left

final position of the nodes at 100.0 s is in the upper-right

corner shows the nodes in bunching mode at 50.0 s. The

collisions because the signal strength of the transmission

transmissions by node A and node B do not result in

capture .

(a) Time Division Multiple Access (TDMA), (b) Frequency

consisting of 24 time slots of duration 417 s, of which

The frame length is 10 ms

12 are used for downlink (i.e., from the base station to

divided into 256 channels (128 channels for uplink and

separated by 200 kHz.

offered load.

length. 39

propagation delay is small when compared to the packet

List of Figures xiii

3.13 The hidden terminal problem: Node A is cannot hear

43

3.14 The exposed terminal problem. Node C is transmitting

C’s transmission, node B cannot transmit. However,

node C’s transmission to node D. Thus, by preventing

underutilization of the channel. 43

3.15 Illustration of IEEE 802.11 DCF four-way handshaking. 44

4.1 Illustration of the lowest-ID clustering algorithm.

Squares, triangles,

gateways, and ordinary nodes, respectively. 54

4.2

algorithm. Squares, triangles, and disks represent

clusterheads, gateways, and ordinary nodes, respectively. 56

5.1 Aironet PC4800 PCMCIA Network Interface Card

(900 mW), idle (110 mW), and sleep (20 mW) modes. 61

5.2

61

5.3 Energy dissipated on transmit, receive, idle, and carrier

by 800 m network with 40 nodes. 63

5.4 Delay-Packet Delivery Ratio (PDR) utility function. 68

5.5 Illustration of R-ALOHA medium access control.

Notation X | Y stands for Reservation for X,

Transmission by Y . 69

5.6 IEEE 802.15.3 superframe. 70

6.1 Overview of SH-TRACE operation. 72

6.2 SH-TRACE frame format. 74

6.3 Average number of voice packets per frame vs. total

number of nodes with active voice sources. 80

6.4 Average number of voice packets delivered per frame

per node vs. number of nodes. 82

“ ” “

”

transmissions destined to node B by node A and node C

node C, and vice versa. Therefore, simultaneous

will result in collisions.

to destination D. Since the channel is busy due to node

node B’s transmission for node A will not interfere with

node B’s transmission, bandwidth is wasted due to the

and disks represent clusterheads,

Illustration of the highest degree (connectivity) clustering

power consumption in transmit (2500 mW), receive

interface Card.

Schematic of Aironet PC4800 PCMCIA Network

sense modes for ooding with IEEE 802.11 in an 800 m

xiv

6.5

as a function of time with NN = 50 and NA = 21.26.

same traffic. 83

6.6

packets per frame as a function of NN , and the lower

panel displays the average value of packet drop ratio, RP D. 84

6.7 Average network energy dissipation per frame vs.

87

6.8 (a) Transmit energy dissipation per node per frame for

802.11. (c) Idle energy dissipation per node per frame

for SH-TRACE and IEEE 802.11. 89

6.9

frame structure used for packet delay analysis. The

pdf’s of x, y, and z are plotted in middle and bottom rows. 90

6.10 Pdf of packet delay with NN = 50. RMS error between

the simulation and theory is 0.16%. 92

6.11 Packet delay vs. number of nodes. 93

6.12 Network failure time vs. number of nodes. 94

6.13 Delivered voice packets per frame per alive node vs. time. 95

6.14 Average number of node changes in listening clusters

per node per frame as a function of time. 96

7.1

nodes. Nodes C1 through C7 are clusterhead nodes. 101

7.2 MH-TRACE frame format. 101

7.3 MH-TRACE sleep/active states. 104

7.4 MH-TRACE cluster creation flow chart. 105

7.5 MH-TRACE cluster creation flow chart. 106

7.6 Network partitioning into clusters. Nodes A-G are

transmission radii. Node X is an ordinary node with its

reception range shown with the shaded disk. 108

List of Figures

(a) Actual number of voice packets generated per frame

(b) Number of dropped packets per frame for the voice

traffic in (a). (c) Number of collisions per frame for the

The upper panel displays the average number of dropped

number of nodes.

SH-TRACE and IEEE 802.11. (b) Receive energy

dissipation per node per frame for SH-TRACE and IEEE

Packet delay calculations. The top row displays the

access for a portion of an actual distribution of mobile

A snapshot of MH-TRACE clustering and medium

clusterhead nodes, and the circles around them show their

List of Figures xv

7.7

simulation time versus number of frames. (b) Average

number of data packet collisions per superframe. (c)

per superframe.

packets per superframe. (e) Average number of

transmitted data packets per superframe. (f) Average

number of received data packets per superframe. 110

7.8 Average packet loss per superframe versus number of frames. 113

7.9 Comparison of clusterhead selection methods.

number of nodes. (b) Average number of dropped data

packet collisions per superframe. 115

7.10 Average number of received packets per node per

117

7.11

number of data collisions per node per superframe. 118

7.12 Average packet delay versus number of nodes. 119

7.13 Average energy dissipation per node per superframe

versus number of nodes. 121

8.1 Illustration of coordinated and non-coordinated MAC

distributions for nodes N0-N4. The lower left panel

where node N0

0

transmissions of N1 and N3 lead to a collision. 126

8.2 MH-TRACE performance degradation in terms of

packet losses. 131

8.3 Average number of received packets per node per

133

8.4 Rectangular field partitioned into three different regions. 135

8.5 Calculation of the percentage coverage of a node inside

region 2. 136

(a) Total number of clusterheads throughout the entire

Average number of data packet receptions per transmission

(d) Average number of dropped data

(a) Average number of received packets per superframe versus

packets per superframe. (c) Average number of data

superframe versus number of nodes.

per superframe versus number of nodes. (b) Average

(a) Average number of dropped data packets per node

protocols. The upper left and right panels show the node

shows the medium access for the coordinated scheme,

is regulated through a schedule transmitted by N . The

is the coordinator and the channel access

non-coordinated scheme (e.g., CSMA). Overlapping data

lower right panel shows the channel access for the

dropped data packets for beacon, header, and contention

Second versus bit error rate (BER).

xvi

8.6 Calculation of the percentage coverage of a node inside

region 3. 137

8.7

versus number of nodes (mobile). 139

8.8 (100 nodes): Average number of received packets per

node per second versus bit error rate (BER). 141

8.9 (200 nodes): Average number of received packets per

node per second versus bit error rate (BER). 142

8.10 Average CH lifetime versus bit error rate (BER). 143

8.11 Average data packet delay versus bit error rate (BER). 144

8.12

versus bit error rate (BER). 145

9.1 Illustration of the IEEE 802.11 medium access control

mechanism in broadcasting. 149

9.2 SMAC frame structure. 150

9.3 Sampling the traffic-density-area space. 155

10.1 Illustration of NB-TRACE broadcasting. The hexagon

large circles centered at the disks represents the transmit

arrows represent the data transmissions. 178

10.2 NB-TRACE flowchart. 178

10.3 Illustration of IFL and IS contents. Squares and

Node-0 is the source node. The entries below the nodes

[Packet ID] [Upstream Node ID] [(CH Status)] [IFL

ID]) fields of their IS packets (ti’s represent time instants). 179

10.4

the source node. Dotted lines represent the links

the data and IS flows, respectively. 180

10.5 Illustration of the RPB mechanism. 181

10.6 Illustration of the CRB mechanism. 182

10.7 Illustration of the ACB mechanism. 183

10.8 Normalized histograms of node energy dissipations for

different broadcast architectures. 193

List of Figures

Average number of received packets per node per second

Average energy consumption per node per second versus

represents the source node; disks are clusterheads; the

range of the clusterheads, squares are gateways, and the

represent the contents of ([Source Node ID] [Flow ID]

represent CHs and ordinary nodes, respectively. Node-0 is

Illustration of IFL and PRN. Squares and diamonds

between the nodes. Solid and dash-dotted lines represent

diamonds represent CHs and ordinary nodes, respectively.

List of Figures xvii

11.1 Illustration of initial flooding. Triangles, squares,

members, multicast relays, and non-relays, respectively.

The entries below the nodes represent the contents of

IS packets (f represent null IDs and ti’s represent time

instants). 201

11.2 Illustration of pruning and multicast tree creation. 203

11.3 Illustration of the Maintain Branch Mechanism. 204

11.4 Illustration of the Repair Branch Mechanism. 206

11.5 Illustration of the Create Branch Mechanism. 207

A.1 Generic DR-TDMA frame. 236

A.2 Single-stage S-ALOHA contention. 237

A.3 Expected number of successful contentions vs. number

of contention slots for a 25-node network (N = 25).

Simulation results are the mean of 1000 independent runs. 237

A.4 Multi-stage contention. 238

A.5 The upper panel shows the total number of stages, K, as

shows the total number of contention slots required for

the termination of the contention, S, as a function of N.

Simulation results are the mean of 1000 independent runs. 240

B.1 MH-TRACE modified cluster creation algorithm flow

chart. Modified blocks are marked with shaded background. 244

B.2 MH-TRACE modified cluster maintenance algorithm

flow chart. Modified blocks are marked with shaded

background. 245

B.3 Average number of clusterheads versus clusterhead separation. 246

B.4 Total number of clusterheads throughout the entire

247

B.5 Average number of blocked nodes per frame versus

clusterhead separation. 248

B.6 Average number of transmitted MAC packets per

248

B.7

249

diamonds, and circles represent sources, multicast group

[Multicast Group ID], [Multicast Relay Status]) elds of their

([Upstream Node ID], [Downstream Node ID],

a function of the number of nodes, N. The lower panel

simulation time (100 s) versus clusterhead separation.

superframe versus minimum clusterhead separation.

minimum clusterhead separation.

Average number of collided packets per superframe versus