139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
This text introduces the principles of routing protocols and metrics as they affect wireless networking environments, specifically in urban areas. Timely because of the recent rise in small city life, this topic includes the consideration of ad hoc, mesh, vehicular, sensor, and delay tolerant networks. These approaches are each unique, and author Miguel Mitre Campista provides a thorough, but accessible, explanation of their individual characteristics for engineers, computer scientists, IT professionals, and curious Internet users.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 220
Veröffentlichungsjahr: 2014
Ähnliche
Contents
Preface
Introduction
I.1. Wireless networks
I.2. Wireless networking scenarios
I.3. Organization
1 Wireless Networking Basic Aspects
1.1. Introduction
1.2. Link layer
1.3. Physical layer
1.4. IEEE 802.11
1.5. Summary
2 Basic Routing Concepts
2.1. Introduction
2.2. Distance-vector-based algorithms
2.3. Link-state-based algorithms
2.4. Summary
3 Ad Hoc Routing
3.1. Introduction
3.2. Architecture
3.3. Routing metrics
3.4. Routing protocols
3.5. Summary
4 Mesh Routing
4.1. Introduction
4.2. Architecture
4.3. Routing metrics
4.4. Routing protocols
4.5. Summary
5 Vehicular Routing
5.1. Introduction
5.2. Architecture
5.3. Routing metrics
5.4. Routing protocols
5.5. Summary
6 Sensor Routing
6.1. Introduction
6.2. Architecture
6.3. Routing metrics
6.4. Routing protocols
6.5. Summary
7 Delay- And Disruption-Tolerant Network Routing
7.1. Introduction
7.2. Architecture
7.3. Routing metrics
7.4. Routing protocols
7.5. Summary
Conclusion
Bibliography
Index
First published 2014 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK
www.iste.co.uk
John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA
www.wiley.com
© ISTE Ltd 2014The rights of Miguel Elias M. Campista and Marcelo G. Rubinstein to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2014935741
British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISSN 2051-2481 (Print)ISSN 2051-249X (Online)ISBN 978-1-84821-627-3
Preface
In this book, we aim at introducing the main concepts of routing applied to wireless networking environments. We focus on networks that can be deployed within an urban scenario, which is vertiginously gaining importance given the recent efforts toward smart cities. We first review physical medium characteristics and the main underlying access methods. Then we move on to present basic concepts related to routing. In the following, we introduce the main metrics and protocols used for routing in ad hoc, mesh, vehicular, sensor, and delay- and disruption-tolerant networks. Throughout the book, we discuss the main differences between the approaches.
We would like to thank the Brazilian agencies CNPq, CAPES, FAPERJ and FINEP for their support. We would also like to thank Professors Marcelo D. Amorim, Luís Henrique M.K. Costa, Otto Carlos M.B. Duarte, Igor M. Moraes and Célio Vinicius N. de Albuquerque for their indirect participation. We would also like to thank our institutions, Universidade Federal do Rio de Janeiro (UFRJ) and Universidade do Estado do Rio de Janeiro (UERJ), for the required infrastructure. Finally, we would like to thank ISTE Ltd. for believing in our work.
Miguel Campista would like to thank his beloved wife Renata, who is pregnant with their first child, Gabriel. Marcelo Rubinstein would like to thank his wife Cláudia and his sons Pedro and Tiago for their patience during the hard process of writing this book.
Miguel Elias M. CAMPISTAMarcelo G. RUBINSTEINApril 2014
Introduction
Wireless networking is widely used in everybody’s daily lives. Nevertheless, not everyone has considered the reasons for such increasing utilization and nor have they understood the consequences. In this introduction, we provide a brief background regarding wireless networking evolution and the main scenarios where these networks are currently deployed.
I.1. Wireless networks
Wireless communications started a long time ago, even before the organized society we know today. If we consider that talking was the first rudimentary type of communication system, this analogy permits us to conclude that the wireless medium has played a fundamental role for mankind since the beginning. Intuitively or not, the wireless medium was the very first substrate for communications because people were able to use it instinctively, without the need of any device, besides their own bodies and voices. If we continue along this line of thought, even at that time, signal propagation was an issue and, consequently, the communication range was limited. To circumvent this obstacle, new alternatives were developed, starting from written letters, culminating many years later in wired technologies. This last alternative, the wired technology, is more sophisticated since it requires suitable equipment to transmit and receive information through the wired medium. The evolution of such wired systems, firstly pushed by the telephony industry, has allowed long-range communications at real-time. This, of course, is neither possible with human voices, limited by a short range, nor with written letters, which can take days or weeks to reach the final destination.
The relatively recent explosion of the Internet, and the possibility of “connecting” people from different cities or even countries, has reinforced the importance of the wired medium. Hence, this substrate became preferred over the wireless, which was not, however, totally left behind. Wireless communications have experienced some advances, but with less impact, or with an impact restricted to certain specific scenarios where no other technology was suitable, e.g. satellite communications. This condition, however, has also changed again, because of the Internet. The success of this network was so huge that people started to require communication capability not only on their desktops. The need for networking services has gone beyond confined places during work hours, such as during the day at an office or during a class at a university, and has moved to “no matter where or when”. In this direction, wireless networking has again emerged as the single possibility that is able to provide, at the same time, ubiquitous connectivity and mobility. All the known challenges regarding wireless communications cannot hold back the advances of upcoming wireless technologies, which are still being proposed at a fast pace.
Nowadays, wireless networks can be viewed as part of the Internet in scenarios where users are mobile or in scenarios where no other alternatives are possible, as a consequence of a lack of infrastructure. For example, in Figure I.1, we can observe a city where people may be interested in:
Although there are many wireless technologies capable of fulfilling almost all the above list of interests, the one currently attracting attention is the IEEE 802.11 [IEE 99a]. The IEEE 802.11 standard, also known as Wi-Fi, is a huge success for Local Area Networks (LANs), given its worldwide acceptance and low cost. Nevertheless, as a LAN technology, its communication range is limited to a few hundred meters. In addition, in wireless networking, this communication range can dynamically change since transmissions are governed by wireless medium propagation laws. Indeed, the signal attenuation is large and can be influenced by many characteristics, such as:
Figure I.1.City-wide scenario where many different wireless networks adapted to their specific use cases can coexist
In wireless networks, the presence of obstacles for transmissions imposes many propagation phenomena, such as reflection, diffraction, etc. These can reduce the signal power at the destination, hindering the correct reception of packets. Besides these physical issues, node mobility can also impact on wireless communications. Indeed, this is a great challenge for wireless communications since the ever-changing network topology requires adaptations on-the-fly. If the network dynamics are too high, such adaptations may not be simple. The level of interference influences the signal-to-noise ratio at the receiver, which is an important parameter for wireless signal decoding. All of these issues can lead to connectivity problems, since two communicating nodes may not be in range during the whole data exchange. There are techniques, however, that have been made commercially available to improve wireless communications. The presence of directional antennas and the possibility of transmission power adjustments can be used, respectively, for increasing the transmission range and for controlling the transmission power. In both cases, they can further influence the final communication range.
The solution for the wireless connectivity problem was partially inspired by the Internet. Since the days of telephony, the participation of intermediate entities has always existed. In telephony wires were switched in central stations to permit a more scalable infrastructure, as well as longer ranges. Imagine if communications always involved a pair of nodes connected by a single wire. This would not be feasible since wires connecting all possible pairs of nodes would be needed. In addition, although attenuation is not as strong as in the wireless medium, it also exists. Therefore, one cannot indefinitely lengthen a wire to connect a pair of nodes, simply neglecting the wire attenuation. On the Internet, this problem is also addressed by the utilization of intermediate nodes in charge of connecting source–destination pairs. Unlike telephone networks, however, these nodes do not play the role of wire switches, but of packet forwarders. The utilization of routers again permits better system scalability even at longer distances. In local wireless networks, intermediate nodes can also be introduced for packet forwarding. In this case, however, they play a subtly different role since they are more important for maintaining the network connectivity than for allowing more scalable designs. This is a consequence of the limited range of these networks, which is more severe than in the wired networks.
In a local wireless network, for example, if a node A cannot directly communicate with a node B, it can use an intermediate node I lying simultaneously within the range of A and B. This node I can be used to forward packets from A to B and vice-versa, maintaining the communication. This means that node I has to receive the packet, obtain the identification of the destination node (e.g. the IP address), perform a forwarding table lookup, and finally send the packet to the node selected to intermediate the transmission toward the destination. In the communication between A and B, upon receiving the packet from A, I sends the packet to B. In our example, the next intermediate node coincides with the final destination and, therefore, the packet is delivered. If, however, node B was not in the range of I, the packet would have been forwarded to another node between I and B. Note that this procedure could be recursively repeated by a sequence of nodes connecting the source–destination pair. This sequence of nodes can be found in advance or on-the-fly. Nevertheless, independent of the strategy, there is always an algorithm to compute the sequence of nodes and a protocol to permit information exchange regarding the current network status. Typically, the routing algorithm is related to the routing protocol.
Let us take a deeper look at the urban scenario in Figure I.1. The presence of routing protocols is of the utmost importance since wireless nodes may not always be directly connected. Again, the following situations may arise:
These different scenarios suggest the utilization of specific routing protocols, tailored to each case. Note that the routing protocol running on the nodes inside a stadium can be different from the protocol running on a node inside a vehicle. Inside a car, the node speed is much higher than within a stadium when watching a soccer game. The node speed, for instance, can dramatically interfere on contact duration, since the distance between a pair of nodes can change very quickly. These differences hinder the utilization of a single routing protocol, no matter which wireless scenario is in use. Of course, we cannot ignore the possibility of using a single protocol, but we must bear in mind the impact of that on the network’s efficiency. What we have observed so far in the literature is that authors always aim at improving the wireless network performance using specific protocols. This would likely permit a higher gamma of applications, even those with quality constraints, such as the real-time applications. In this direction, considering the specific characteristics of the deployment scenario can make the protocol more suitable to a given environment or to a given application. Consequently, the more assumptions we have, the more optimized the routing protocol becomes for a particular case. This rationale has been used so far for motivating the proposal of several routing protocols adapted to each specific situation. These routing protocols have been evolving over the years from adaptations of previous protocols to totally new ideas.
I.2. Wireless networking scenarios
Many scenarios can be envisaged as candidates for wireless network deployment. These scenarios have different characteristics that must be considered by the many routing protocols, as briefly discussed in the following.
I.2.1. Ad hoc networks
The IEEE 802.11 standard defines two basic types of operation: infrastructure and ad hoc. Whereas the former employs access points, the latter does not count on the existence of any infrastructure. Ad hoc networks were designed for catastrophic or military scenarios, where the infrastructure was destroyed or accessible by enemy forces; and to temporary settings, such as a stadium where a game happens once a week.
If no infrastructure is around, users must play the role of communication infrastructure by relaying packets to and from other nodes. The participating nodes collaborate with the network operation, routing packets between any source–destination pair. In Figure I.2, users in a stadium have set an ad hoc network during the game so as to exchange data related to the ongoing event. These nodes have to run a routing protocol so that they can forward data back and forth.
Figure I.2.Ad hoc network composed of users watching a game in a stadium
I.2.2. Mesh networks
One of the main problems with ad hoc networks is the lack of connectivity. For instance, if users start roaming, the network can easily become disconnected. If we consider the infrastructure mode of the IEEE 802.11, we come across other problems, such as the network range. In the infrastructure mode, only users in range of an access point can communicate, since access points must intermediate all communications.
Mesh networks can be seen as an intermediate solution between ad hoc and infrastructure networks, as they extend the connectivity of access points by using a stationary backbone of wireless routers. These routers then must run a routing protocol to permit communications. Figure I.3 highlights a mesh network backbone used by roaming users to communicate. The backbone can be installed on top of buildings or street lights.
I.2.3. Vehicular networks
In big cities, the time users spend within vehicles is growing rapidly, mainly due to traffic jams. Therefore, staying connected even while driving a car is an appealing option, not only for info-tainment applications, but also for safe driving. The problem, however, is how to deal with the connectivity problem, which is far more severe among cars than among roaming users (pedestrians). Taking into account that cars can move at high speeds, the network dynamics become even more challenging.
Figure I.3.Wireless mesh network backbone serving as an extended infrastructure for users walking on the streets.
Vehicular networks are investigated as a different case, if compared with ad hoc networks. Although, in both cases, nodes participate in packet forwarding, the former has to deal with a larger range of speeds, predetermined trajectories confined to streets and roads, and driving laws. Figure I.4 depicts two possible scenarios: the first scenario, where vehicles communicate only between them; and the second scenario, where vehicles communicate only with the infrastructure. In the first case, vehicles need to run a routing protocol to reach the destination and can also count on auxiliary information such as city maps.
I.2.4. Sensor networks
Sensor networks are somewhat different from all the previous networks, since they are deployed for a specific task. Unlike ad hoc, mesh and vehicular, users do not use sensor networks as an underlying infrastructure for intercommunications. Instead, they use these networks to collect and send data to a predetermined point (the network sink) with higher communications capability. Users then access this point to obtain the monitored data. The idea is to use sensor networks in areas where the human access is not easy or in areas where permanent monitoring is needed.
Figure I.4.Vehicular networks can communicate via an infrastructure deployed alongside roads or streets or can communicate as in ad hoc mode
Sensor nodes have stringent restrictions concerning hardware resources. Because they are used for a well-defined task and are typically deployed in large amounts, they must be inexpensive. As a consequence, resources are limited and saving them becomes the main concern considered by all routing protocols proposed so far. Figure I.5 shows a typical sensor network deployed for a single task, which is monitoring the lake depth to predict possible floodings. Sensor nodes must execute a routing protocol to send the monitored data toward the network sink.
I.2.5. Delay- and disruption-tolerant networks (DTNs)
All typical wireless networks rely on the existence of an end-to-end path connecting source–destination pairs. This assumption, however, is not always valid, representing a great issue for wireless communications. Whereas ad hoc, mesh, vehicular, and sensor networks only send data packets upon end-to-end path connectivity, DTNs send data packets even if such a path is unknown. To this end, these networks use persistent data storage and forward data using message switching.
Figure I.5.Sensor networks communicate via multiple hops to send the data toward a network sink
DTNs are suitable for scenarios where no other infrastructure is available and thus data forwarding needs to be conducted upon contact opportunities. These opportunities can be deterministic or stochastic depending on the available information. Figure I.6 shows a communication between a node in a house at a rural location and a node in an urban scenario. The car is used to forward the data from the farm to the user as the so-called “data mule”. Finding the destination, however, may not be trivial and requires a routing protocol suitable for this.
I.3. Organization
This book is organized into seven chapters. Chapter 1 reviews some fundamentals of wireless communications and of the IEEE 802.11 standard. Chapter 2 presents two classic algorithms for route computation: distance-vector- and link-state-based algorithm. Chapters 3, 4, 5, 6 and 7 present main metrics and routing protocols used in ad hoc, mesh, vehicular, sensor and delay- and disruption-tolerant networks. Final remarks are presented in the Conclusion.
Figure I.6.Delay- and disruption-tolerant networks (DTNs) rely on persistent message switching to overcome the lack of end-to-end connectivity guarantees
1
Wireless Networking Basic Aspects
Before presenting wireless routing protocols, it is important to review some of the fundamentals of wireless communications and of the IEEE 802.11 standard [IEE 99a]. In this chapter, we introduce details regarding the physical medium and the technologies used for medium access. In addition, we highlight the physical and link layer standards as defined in IEEE 802.11.
1.1. Introduction
The design of a wireless network has to take into account several interesting and difficult problems. Traditional wireless communication issues often related to the physical medium, such as a low transmission rate, high bit error rates, noise, limited range and significant variation in physical medium conditions, must be overcome. In the Medium Access Control (MAC) sublayer, the difficulty of collision detection and the hidden terminal problem demand new medium access methods.
1.2. Link layer
The link layer is composed of two sublayers: Logical Link Control (LLC) and MAC. LLC provides frame communication services with flow and error controls, whereas one of the main functions of the MAC sublayer is the access control to a wireless shared medium.
MAC protocols can be classified as contention-free or contention-based, depending on the medium access strategy. Some authors, such as Kumar et al. [KUM 06], also classify contention-based protocols as multiple channel, power-aware and Quality of Service-aware (QoS-aware) protocols, but we will not use this subclassification. The contention free schemes predefine assignments to allow stations to transmit without contending for the medium, e.g. polling, reservation, Time Division Multiple Access (TDMA) and Frequency Division Multiple Access (FDMA). Contention-free mechanisms are usually employed to provide bounded end-to-end delay and minimum bandwidth. However, contention-based schemes are more appropriate for sporadic data transfers. Main contention-based protocols for wireless networks are ALOHA, Carrier Sense Multiple Access (CSMA), Multiple Access with Collision Avoidance (MACA), Multiple Access with Collision Avoidance for Wireless (MACAW), Floor Acquisition Multiple Access (FAMA) and Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA).
1.2.1. Contention-based protocols
In ALOHA [ABR 70], a station accesses the medium as soon as it has a frame to send. The station that receives the frame without errors sends an acknowledgment (ACK) back. If two or more stations send data at the same time, a frame collision occurs. This collision can be inferred by the non-reception of the ACK in a random interval of time T. In this case, each station must retransmit its frame after the random time. Although being simple and practical, ALOHA presents a low efficiency, since the effective utilization is not greater than 18% of the channel capacity.
CSMA [KLE 75a] can be considered as an evolution of ALOHA. CSMA uses carrier sensing before transmitting a frame in order to reduce the number of collisions. In CSMA, a station that has data to send becomes aware of current transmissions by sensing the medium. If a carrier is sensed, the medium is considered busy and the station postpones its medium access. Nevertheless, if the medium is idle, the station transmits its data frame immediately1. In CSMA, a collision is also inferred by the non-reception of the corresponding ACK in a time T.
In wireless networks, because of the great power difference between the transmitted and the received signal(s) and also because there are no guarantees that all stations can hear the others, collision detection is not used. The power difference between the transmitted and the received signals occurs mainly because of the medium attenuation (see section 1.3). So, it is hard to separate signal from noise and also transmission from reception at the sender, because the signal of the transmitter has a higher power than the received signal at the sender. Moreover, collision detection is not used because a collision at the sender does not mean the same at the receiver, because of the great and variable attenuation. Another problem that makes the collision detection more difficult is the hidden terminal issue [KLE 75b]. This problem is illustrated in Figure 1.1, in which ranges are represented by circles. Stations A and C are not in range and can only communicate with station B, whereas station B reaches A and C. If A starts to transmit to B, C cannot detect A’s transmission. Therefore, if C starts to send to B, there will be a collision in B. This problem occurs because the interference at the transmitter does not matter, but the interference at the receiver does. That is why pure CSMA is not used in wireless networks.
Figure 1.1.An example of the hidden terminal problem
MACA [KAR 90] has been proposed for wireless networks. MACA does not use carrier sensing, since although sensing reduces the number of collisions, it does not eliminate all of them. Moreover, MACA tries to solve the hidden terminal problem. It uses request to send (RTS) and clear to send (CTS) frames to deal with the problem. A station A that wants to transmit data to a station B, sends an RTS before transmitting a data frame. RTS is a short frame that includes the length of the data frame that will eventually be transmitted. When station B receives the RTS, it sends a CTS to station A indicating that it is ready to receive data. The CTS also contains the length of the data frame to be sent. On hearing the RTS, all stations that are in range of station A will postpone their transmissions by the time needed for the CTS to be transmitted. Neighbors of station B, on hearing the CTS, must postpone their transmissions until the end of the data frame transmission. Thus, the medium is reserved, avoiding data frame collisions. Collisions of RTS frames can still occur, but as these frames are shorter, collisions are less severe. An RTS collision is inferred if the CTS is not received in a time T by the station that has sent an RTS. In this case, the station will postpone its transmission using a binary exponential back off algorithm.
The MACAW protocol [BHA 94] extends MACA by adding link level ACK for data frames. The data ACK at link layer is an important improvement because it accelerates the recovery of frames with errors, which was only initiated at higher levels.
The FAMA protocol [FUL 95] uses carrier sensing and the RTS/CTS mechanism to augment efficiency. Another problem tackled by FAMA is presented hereafter by an example illustrated in Figure 1.2. Suppose A and C have data to send to B. First, A sends an RTS to B that transmits a CTS back to A. Then C transmits an RTS to B, because depending on the propagation delay, the CTS from B may not have been received by C, but already by A. If A starts to send data to B, the RTS from C to B
