| | Preface | xi |
| 1 | Ad Hoc Networking: An Introduction | 1 |
| 1.1 | Model of Operation | 3 |
| 1.1.1 | Symmetric Links | 6 |
| 1.1.2 | Layer-2 Ad Hoc Solutions | 6 |
| 1.1.3 | Proactive versus Reactive Protocols | 7 |
| 1.1.4 | Multicast | 8 |
| 1.2 | Commercial Applications of Ad Hoc Networking | 8 |
| 1.2.1 | Conferencing | 9 |
| 1.2.2 | Home Networking | 9 |
| 1.2.3 | Emergency Services | 10 |
| 1.2.4 | Personal Area Networks and Bluetooth | 10 |
| 1.2.5 | Embedded Computing Applications | 11 |
| 1.2.6 | Sensor Dust | 12 |
| 1.2.7 | Automotive/PC Interaction | 13 |
| 1.2.8 | Other Envisioned Applications | 14 |
| 1.3 | Technical and Market Factors Affecting Ad Hoc Networks | 14 |
| 1.3.1 | Scalability | 15 |
| 1.3.2 | Power Budget versus Latency | 17 |
| 1.3.3 | Protocol Deployment and Incompatible Standards | 17 |
| 1.3.4 | Wireless Data Rates | 18 |
| 1.3.5 | User Education and Acculturation | 19 |
| 1.3.6 | Additional Security Exposure | 19 |
| 1.3.7 | Spotty Coverage | 20 |
| 1.4 | General Comments on Routing Protocols | 20 |
| 1.5 | Description of the Material Presented | 23 |
| 2 | A DoD Perspective on Mobile Ad Hoc Networks | 29 |
| 2.1 | Motivation | 30 |
| 2.2 | The Past | 33 |
| 2.2.1 | DARPA Packet Radio Network | 34 |
| 2.2.2 | Survivable Radio Networks | 35 |
| 2.2.3 | Other DoD Efforts in MANET | 36 |
| 2.2.4 | Other Efforts in MANET | 38 |
| 2.3 | The Present | 39 |
| 2.3.1 | Tactical Internet | 41 |
| 2.3.2 | ELB | 41 |
| 2.3.3 | GloMo | 42 |
| 2.3.4 | IETF MANET Working Group | 44 |
| 2.4 | The Future | 44 |
| 2.4.1 | Commercial Applications | 44 |
| 2.4.2 | DoD | 46 |
| 2.4.3 | Open Research Issues | 47 |
| 2.5 | Conclusion | 48 |
| 3 | DSDV: Routing over a Multihop Wireless Network of Mobile Computers | 53 |
| 3.1 | Introduction | 54 |
| 3.2 | Overview of Routing Methods | 55 |
| 3.2.1 | Link-State | 55 |
| 3.2.2 | Distance-Vector | 56 |
| 3.3 | Destination-Sequenced Distance Vector Protocol | 57 |
| 3.3.1 | Protocol Overview | 57 |
| 3.3.2 | Route Advertisements | 58 |
| 3.3.3 | Route Table Entry Structure | 58 |
| 3.3.4 | Responding to Topology Changes | 59 |
| 3.3.5 | Route Selection Criteria | 60 |
| 3.3.6 | Operating DSDV at Layer 2 | 61 |
| 3.3.7 | Extending Base Station Coverage | 62 |
| 3.4 | Examples of DSDV in Operation | 62 |
| 3.4.1 | Damping Fluctuations | 65 |
| 3.5 | Properties of the DSDV Protocol | 68 |
| 3.6 | Comparison with other Methods | 70 |
| 3.7 | Future Work | 71 |
| 3.8 | Summary | 72 |
| 4 | Cluster-Based Networks | 75 |
| 4.1 | Clustering for Transmission Management | 77 |
| 4.1.1 | Link-Cluster Architecture | 77 |
| 4.2 | Clustering for Backbone Formation | 81 |
| 4.2.1 | Near-Term Digital Radio Network | 81 |
| 4.2.2 | Virtual Subnet Architecture | 85 |
| 4.3 | Clustering for Routing Efficiency | 90 |
| 4.3.1 | Hierarchical Routing | 91 |
| 4.3.2 | Clustering | 127 |
| 4.4 | Conclusion | 135 |
| 5 | DSR: The Dynamic Source Routing Protocol for Multihop Wireless Ad Hoc Networks | 139 |
| 5.1 | Assumptions | 141 |
| 5.2 | DSR Protocol Description--Overview and Important Properties | 143 |
| 5.2.1 | DSR Route Discovery | 144 |
| 5.2.2 | DSR Route Maintenance | 146 |
| 5.2.3 | Additional Route Discovery Features | 147 |
| 5.2.4 | Additional Route Maintenance Features | 151 |
| 5.2.5 | Support for Heterogeneous Networks and Mobile IP | 154 |
| 5.2.6 | Multicast Routing with DSR | 158 |
| 5.2.7 | Location of DSR Functions in the ISO Network Reference Model | 158 |
| 5.3 | DSR Evaluation | 159 |
| 5.3.1 | Simulation Summary | 159 |
| 5.3.2 | DSR Implementation and Testbed Summary | 162 |
| 5.4 | Related Work | 164 |
| 5.5 | Conclusion | 167 |
| 6 | The Ad Hoc On-Demand Distance-Vector Protocol | 173 |
| 6.1 | AODV Properties | 175 |
| 6.2 | Unicast Route Establishment | 176 |
| 6.2.1 | Route Discovery | 177 |
| 6.2.2 | Expanding Ring Search | 178 |
| 6.2.3 | Forward Path Setup | 179 |
| 6.2.4 | Route Maintenance | 180 |
| 6.2.5 | Local Connectivity Management | 181 |
| 6.2.6 | Actions after Reboot | 182 |
| 6.3 | Multicast Route Establishment | 182 |
| 6.3.1 | Route Discovery | 183 |
| 6.3.2 | Forward Path Setup | 184 |
| 6.3.3 | Multicast Route Activation/Deactivation | 184 |
| 6.3.4 | Multicast Tree Maintanence | 185 |
| 6.3.5 | Actions after Reboot | 190 |
| 6.4 | Broadcast | 190 |
| 6.5 | Simulations | 191 |
| 6.5.1 | Unicast Simulations | 192 |
| 6.5.2 | Multicast Simulations | 197 |
| 6.6 | Optimizations and Enhancements | 203 |
| 6.6.1 | Quality of Service | 204 |
| 6.6.2 | Subnet Routing | 204 |
| 6.6.3 | AODV and Mobile IP | 205 |
| 6.7 | Future Work | 206 |
| 6.7.1 | Security | 206 |
| 6.7.2 | Asymmetric Routing | 206 |
| 6.8 | Conclusion | 207 |
| Appendix A | Message Formats | 209 |
| A.1 | Route Request | 209 |
| A.2 | Route Reply | 210 |
| A.3 | Route Error | 211 |
| A.4 | Multicast Activation | 212 |
| A.5 | Group Hello | 213 |
| Appendix B | Extension Formats | 214 |
| B.1 | Hello Interval | 214 |
| B.2 | Multicast Group Leader | 215 |
| B.3 | Multicast Group Rebuild | 215 |
| B.4 | Multicast Group Information | 216 |
| B.5 | Maximum Delay | 216 |
| B.6 | Minimum Bandwidth | 217 |
| Appendix C | Configuration Parameters | 218 |
| 7 | ZRP: A Hybrid Framework for Routing in Ad Hoc Networks | 221 |
| 7.1 | Reconfigurable Wireless Networks | 221 |
| 7.2 | The Communication Environment and the RWN Model | 223 |
| 7.3 | The Zone Routing Protocol | 225 |
| 7.3.1 | Reactive versus Proactive Routing | 225 |
| 7.3.2 | Routing Zones and Intrazone Routing | 227 |
| 7.3.3 | Interzone Routing and the Zone Routing Protocol | 228 |
| 7.4 | ZRP--Formal Description | 232 |
| 7.4.1 | Neighbor Discovery Protocol | 232 |
| 7.4.2 | The Intrazone Routing Protocol | 234 |
| 7.4.3 | The Interzone Routing Protocol | 235 |
| 7.5 | Evaluation of ZRP | 240 |
| 7.6 | Performance Results | 244 |
| 7.7 | Conclusion | 249 |
| | Appendix | 251 |
| 8 | Link Reversal Routing | 255 |
| 8.1 | General Approach | 255 |
| 8.2 | The Gafni-Bertsekas Algorithm | 258 |
| 8.3 | The Lightweight Mobile Routing Algorithm | 262 |
| 8.3.1 | Protocol Description | 265 |
| 8.3.2 | Properties of the Protocol | 273 |
| 8.4 | The Temporally Ordered Routing Algorithm | 275 |
| 8.4.1 | Protocol Description | 276 |
| 8.4.2 | Properties of the Protocol | 286 |
| 8.5 | Comparison of LRR Algorithms | 295 |
| 8.6 | Conclusion | 295 |
| 9 | The Effects of Beaconing on the Battery Life of Ad Hoc Mobile Computers | 299 |
| 9.1 | Motivation | 299 |
| 9.2 | Ad Hoc Wireless Networks | 300 |
| 9.2.1 | Power Issues | 301 |
| 9.2.2 | Smart Batteries and Battery Characteristics | 301 |
| 9.3 | Associativity Based Routing | 303 |
| 9.3.1 | ABR Protocol Description | 304 |
| 9.3.2 | ABR Route Discovery Phase | 304 |
| 9.3.3 | Handling Mobility in ABR | 305 |
| 9.3.4 | ABR Route Deletion Phase | 306 |
| 9.4 | Effects of Beaconing on Battery Life | 306 |
| 9.4.1 | Experimental Hardware | 307 |
| 9.4.2 | Experimental Software | 308 |
| 9.5 | Experimental Results and Observations | 310 |
| 9.5.1 | Standalone Beaconing at High Frequencies | 310 |
| 9.5.2 | Standalone Beaconing at Low Frequencies | 313 |
| 9.5.3 | Beaconing with Neighboring Nodes at High Frequencies | 314 |
| 9.5.4 | Beaconing with Neighboring Nodes at Low Frequencies | 317 |
| 9.5.5 | Deductions | 318 |
| 9.6 | Conclusion | 320 |
| 10 | Bandwidth-Efficient Link-State Routing in Wireless Networks | 323 |
| 10.1 | Updating Routes in Wireless Networks | 326 |
| 10.2 | STAR Description | 328 |
| 10.2.1 | Information Stored and Exchanged | 329 |
| 10.2.2 | Validating Updates | 330 |
| 10.2.3 | Exchanging Update Messages | 330 |
| 10.2.4 | Example | 336 |
| 10.2.5 | Impact of the Link Layer | 336 |
| 10.3 | Performance Evaluation | 338 |
| 10.3.1 | Comparison with Table-Driven Protocols | 339 |
| 10.3.2 | Comparison with On-Demand Routing Protocols | 340 |
| 10.4 | Conclusion | 347 |
| 11 | Summary and Future Work | 351 |
| 11.1 | Future Work | 351 |
| 11.1.1 | Scalability | 352 |
| 11.1.2 | Quality of Service | 352 |
| 11.1.3 | Is the Client-Server Model Viable? | 353 |
| 11.1.4 | Connecting to the Internet | 354 |
| 11.1.5 | Security | 355 |
| 11.1.6 | Power Control | 356 |
| 11.2 | Other Approaches | 357 |
| 11.2.1 | Location-Assisted Routing | 357 |
| 11.2.2 | Fisheye Routing | 357 |
| 11.2.3 | CEDAR | 358 |
| 11.3 | A Possible Vision of the Future | 358 |
| 11.4 | For More Information | 360 |
| | Index | 363 |