Unicast Routing in Ad Hoc Wireless Networks

Unicast Routing in Ad Hoc Wireless Networks

Wired vs. Wireless networking

In contrast to wired networks, wireless communications use a shared medium which is the radio channel. This means that the nodes can’t use separate communication lines to connect with their neighbors so that they must take care to avoid that concurrent wireless transmissions corrupt each other. The radio channel can’t be bounded and once the radio signal is launch, we can’t estimate the exact distance it will reach in the space which make it  unpredictable and impose additional care about other properties such as signal transmission strength. Also, this channel can’t be isolated or protected against foreign perturbations which cause more transmission errors and less reliability. Another major difference with wired communications is that in wireless communications a node is unable to detect collisions whenever it occurs while transmitting. Radio channel is also more exposed to eavesdropping, jam and spoofing from intruders.
All these limitations make the wireless links really unreliable but in spite of that, wireless networking stays a very interesting choice in many situations because it offers an incomparable flexibility and mobility comparing to wired networks. It is also useful in reducing networking costs in many situations since the installation of a wireless network requires considerably less cabling or no cabling at all. It is also suitable to use a wireless network rather than a wired one in temporary installations. Without missing that the deployment of a wireless network take very less time compared to the deployment of wired ones.

Wireless evolution

The wireless communications has known an exponential growth in the past decade. We have been witnesses of the great advances in network infrastructures, wireless applications and the vulgarization of the usage of wireless devices such as cell phones, PDAs and laptops, all getting smaller and more powerful in their capabilities and also have access to more applications and network services.
Radio transmissions can be considered as the first step on the wireless networking track. Next comes cordless phones which came to answer the need to communicate while on the move, or away from a fixed phone outlet and the MTS (Mobile Telephony System) which has been deployed in some cities in the USA in 1946. MTS, Improved MTS or Advanced MTS in Japan are analog systems which utilize a BS (Base Station) with a high power transmitter to cover the expected area and some dispersed receivers to rely mobile units to the BS. This system has many limitations due mainly to inefficient exploitation of the radio channel (limited simultaneous calls, frequent interferences…). These limitations find the answer in the first generation of cellular systems through the use of the cells concept, it consist of replacing the huge BS with a number of low coverage stations forming adjacent cells

Ad Hoc Mobile Networks

The ad hoc mobile networks (MANET) as can be understood from their name are temporary networks which are formed just for a specific purpose. They are infrastructureless networks, autonomous and entirely distributed systems where different wireless mobile nodes are capable of arbitrary movement and power switching without breaking the network connectivity since it is physically possible. In ad hoc mobile networks nodes are not required to reach every other node directly because of their limited range but they may rely on other intermediate nodes for relaying. Therefore they must operate as hosts and in the same time as routers. The use of such networks is suited when it is impossible or undesirable to use fixed infrastructures.
The concept of ad hoc mobile networks is not new unlike the naming, early ad hoc networking forms can be dated to the DARPA Packet Radio Network (PRNet) project in 1972 which was not a fully distributed architecture because of some centralized controls and which was inspired by the Internet and the packet switching technology. Another similar project was launched in 1983 to address main issues in PRNet, in the areas of network scalability, security, processing capability and energy management . The Survival Adaptive Radio Network (SURAN) was based on link state routing contrarily to PRNet which used Distance Vector based routing. These two projects were purely for military purposes. The US defense aimed behind that to develop a technology which permits connecting different nodes in battlefield.

Ad hoc mobile networks applications

Ad hoc mobile networks seems to be completely absent from our everyday life. This in fact is principally due to the goal for they were originally designed. Historically, MANETs have primarily been designed to be used in particular circumstances where it may be impossible to rely on fixed bases to perform networking operations especially in battlefield or in massive infrastructures failure like in disasters recovery. The MANETs concept is very  original but hard to materialize. Delivering reliable services on such platforms reside a real challenge for researchers.
Today, a new wave has come. Numerous factors speak in favor of ad hoc mobile networking like technological progress and the generalization and wide usage of mobile devices. This with the improvements achieved these last years on MANETs has drawn the attention of professionals from several fields to the importance of this class of networks in our future life.
Future applications of ad hoc networks can only be limited by imagination. This is because the flexibility and mobility they offer and which fit very well to what we need in today’s life. But in the same time, we must recall that big work is yet expected on MANETS to give them to a truly practical level.

Routing in conventional networks

Today’s routing protocols in conventional networks like the Internet are based on one of two primary algorithms, the distance vector algorithm or the link state algorithm. Distance Vector (DV) algorithm – also called Bellman–Ford algorithm because it is based on the Bellman equation and is a distributed version of the Ford–Fulkerson shortest path algorithm which is based on the previous relation too – periodically broadcasts routing information which consist of a vector of the learned distances from the entire network hosts but only to neighboring routers (where it will be used to infer shortest routes and update the local routing information). Therefore, the size of routing information to transmit become more and more important as the network raise in size and may slow down the performance of such algorithms. Also, because the DV algorithms are derived from the Bellman–Fulkerson shortest path algorithm, their convergence is very slow and any change in the network topology may require a considerable time to propagate and take effect on all the network hosts. First implementations of the DV algorithms was the RIP [10] protocol which has been widely used (routed for UNIX system, implementation from the Berkeley university) before being
specified by the IETF in 1988 .

Table des matières

Chapter 1 
1. Introduction and Preview 
1.1. Motivation and challenges
1.2. Thesis outline
Chapter 2
2. An Introduction to Ad Hoc Mobile Networks 
2.1. Introduction
2.2. Wired vs. Wireless networking
2.3. Wireless evolution
2.4. Ad Hoc Mobile Networks
2.5. Characteristics of ad hoc mobile networks
2.5.1. Characteristics due to distribution
2.5.2. Characteristics due to wireless links nature
2.5.3. Mobility
2.5.4. Multi hopping
2.5.5. Limited energy source
2.6. Ad hoc mobile networks applications
2.7. Conclusion
Chapter 3 
3. Unicast Routing in Ad Hoc Wireless Networks
3.1. Introduction
3.2. Routing in conventional networks
3.3. Routing in ad hoc mobile networks
3.4. Classifications of routing protocols
3.4.1. Proactive VS On–Demand routing protocols
3.4.2. Distributed VS source routing
3.4.3. Flat VS Hierarchical routing
3.4.4. Geographical approaches
3.5. Proactive routing protocols
3.5.1. Destination–sequenced distance vector protocol (DSDV)
3.5.2. Optimized link state routing protocol (OLSR)
3.5.3. Topology dissemination based on reverse–path forwarding (TBRPF)
3.6. Reactive routing protocols
3.6.1. Temporally Ordered Routing algorithm (TORA)
3.6.2. Dynamic source routing
3.6.3. Ad hoc on–demand distance vector routing protocol
3.7. Conclusion
Chapter 4 
4. MAC Layer Protocols for Ad Hoc Mobile Networks 
4.1. Introduction
4.2. The multiple access to wireless mediums
4.2.1. Time division multiple access
4.2.2. Frequency division multiplexing
4.2.3. Code division multiplexing
4.2.4. Space division multiplexing
4.3. Ad hoc key considerations for Mac protocols design
4.3.1. A shared and multi–access medium
4.3.2. Varying channel condition
4.3.3. Errors ratio
4.3.4. Signals properties (speak XOR hear)
4.3.5. Hidden terminal and exposed terminal problems
4.4. Design goals for MAC protocols in MANETs
4.4.1. Controlled latency
4.4.2. Throughput and goodput
4.4.3. Fairness
4.4.4. Controlled overhead
4.4.5. Power efficiency
4.4.6. QoS delivery
4.4.7. The physical layer facilities
4.5. Review of MAC protocols for ad hoc networks
4.5.1. ALOHA
4.5.2. Slotted ALOHA
4.5.3. Carrier Sense Multiple Access
4.5.4. Elimination yield non–preemptive priority multiple access (EY–NPMA)
4.5.5. Multiple Access Collision Avoidance (MACA)
4.5.6. MACA for Wireless (MACAW)
4.5.7. MACA by invitation (MACA–BI)
4.5.8. Dual Busy Tone Multiple Access (DBTMA)
4.5.9. Floor Acquisition Multiple Access (FAMA/FAMA–NCS )
4.5.10. The distributed coordination function of the IEEE 802.11 (DCF)
4.6. Conclusion
Chapter 5
5. QoS Support in Ad Hoc Mobile Network 
5.1. Introduction
5.2. About Quality of Service
5.3. QoS in the Internet
5.3.1. The Integrated Services model (IntServ)
5.3.2. Differentiated service
5.4. QoS in MANETs
5.5. General models for QoS support in MANETs
5.5.1. IntServ and DiffServ in ad hoc mobile networks
5.5.2. Flexible QoS Model for MANETs (FQMM)
5.5.3. Stateless Wireless Ad hoc Networks (SWAN)
5.5.4. INSIGNIA
5.6. QoS support from a layered perspective
5.6.1. QoS provisioning at the MAC layer
5.6.2. QoS routing
5.6.3. Transport layer in MANETs and QoS
5.6.4. Application layer
5.7. Conclusion
Chapter 6
6. Cross Layer Design of Ad Hoc Mobile Networks
6.1. Introduction
6.2. What is CLD?
6.3. Motivation for CLD
6.4. The cost of cross–layer optimizations
6.4.1. Design, implementation and modeling complexity
6.4.2. Interoperability with existing systems and coexistence of multiple CLDs
6.4.3. The system longevity
6.5. Cross–layer design proposals: a taxonomy
6.5.1. Cross–layering based on added notifications
6.5.2. Cross–layering based on added interactions
6.5.3. Merging adjacent layers
6.5.4. Design coupling
6.5.5. Cross–layering by adding an information sharing mechanism
6.6. Examples involving cross layer
6.6.1. Cross–layer congestion control
6.6.2. MOBILEMAN
6.6.3. CrossTalk
6.7. Performance of cross–layer designs: a bad example
6.7.1. Rate adaptive MAC with minimum hop routing
6.8. Conclusion
Chapter 7
7. EFORTS Every node Feedback for Optimizing Real time Traffic Support
7.1. Introduction
7.2. Why VoIP?
7.3. VoIP transmission
7.3.1. Digitization
7.3.2. Speech coding
7.4. Quality of VoIP
7.4.1. End–to–end delay
7.4.2. Jitter
7.4.3. Loss
7.4.4. Voice quality measurement
7.5. Real time protocols, RTP & RTCP
7.6. Signaling protocols
7.6.1. SIP
7.7. VoIP in ad hoc networks
7.7.1. New challenges
7.7.2. Convenient directions
7.7.3. Permissive error control
7.7.4. Design of specific speech coders
7.7.5. Renew network protocols design
7.8. EFORTS (Every node Feedback for Optimizing Real time Traffic Support)
7.9. Founding our proposal
7.9.1. 1st Ad Hoc networks are poor environments
7.9.2. 2nd Ad Hoc networks are highly dynamic
7.9.3. 3rd Ad Hoc networks offer new opportunities
7.10. The proposed scheme (EFORTS)
7.10.1. Packets deadline aware MAC
7.10.2. The MAC Spy
7.10.3. The reporting agent RA
7.10.4. The state collector SC
7.10.5. RA interaction with routing
7.10.6. RA interaction with adaptive applications
7.10.7. RA and admission control
7.11. Simulations
7.11.1. VoIP support in unloaded MANETs
7.11.2. A more realistic scenario
7.12. Conclusion
Chapter 8 
8. Conclusions and Future Work 
8.1. Conclusions
8.2. Future work

Télécharger le rapport complet