Abstract
Introduction
Background and Related Work
Methodology
Experimental Results and Analysis
Conclusions  and Future Work
Bibliography
Appendices
Downloads


 

Chapter 2. Background and Related Work


2.1 Wireless Ad Hoc Networks
2.2 Description of the DSR Protocol
2.3 IEEE 802.11 MAC Protocol
2.4 Related Work
2.5 Summary

           This Chapter describes relevant background knowledge and related work for readers to easily understand the analysis conducted in our experiments to be presented and discussed in Chapter 4.
           The first three sections will discuss the relevant background knowledge. In Section 2.1, wireless ad hoc networks and their significant characteristics are discussed. Section 2.2 describes key features of the DSR protocol, in terms of its two main mechanisms, Route Discovery and Route Maintenance. Section 2.3 gives a brief review of the IEEE 802.11 MAC protocol. Since Pocket PCs in our system communicate with each other using Compaq® IEEE 802.11 wireless LAN cards, knowing main characteristics of the IEEE 802.11 MAC protocol will help readers to understand the experimental results reported in Chapter 4. Section 2.4 addresses other related works, primarily focusing on the performance of DSR in ad hoc networks. Finally, Section 2.5 provides a summary of this Chapter.

2.1 WIRELESS AD HOC NETWORKS

           In recent years, wireless technologies and applications have received a lot of attention [Sheu2002]. Owing to rapidly emerging wireless computing, users can communicate with each other through network connectivity without being tethered off of a wired network [Crow1997]. An ad hoc wireless local area network (WLAN) consists of a group of mobile hosts creating a temporary network without the help of any pre-existed infrastructure or centralized administration [Sheu2002, Johnson1994, Frodigh2000, Perkins2000]. Since the nodes in an ad hoc network are able to serve as routers and hosts, they can forward packets on behalf of other nodes and run user applications [Frodigh2000]. That is, when two nodes are within the wireless transmission range of each other, they can communicate with each other directly. However, if they are out of their transmission range to each other, intermediate nodes can forward a packet for the two nodes to communicate with. Since ad hoc networks do not need any help of centralized infrastructure, wireless applications are becoming more and more popular where wired networking is not available or not economically feasible [Sheu2002]. In general, a wireless ad hoc network that consists of mobile nodes and communicates over radio without the aid of any infrastructure is popularly called MANET (Mobile Ad-hoc NETwork) [Gunes2002].
           Figure 2.1 [Frodigh2000] depicts our vision of ad hoc networking including scenarios that may occur at an airport where people carry devices that can be connected based on an ad hoc network. A user’s devices can both interconnect with one another and connect to local information point, for instance, in order to obtain updated information on flight departures, gate changes, and so on. The ad hoc devices can also forward traffic on behalf of two devices that are out of range each other. Thus, the below airport scenario includes a mixture of single and multiple radio hops.

           Figure 2.1 describes the following scenario that can often occur in an airport. At an airport, where people can access local-and wide-area networks, ad hoc Bluetooth connections are used to interconnect carried devices, such as PDAs, WCDMA mobile phones, and notebook computers. For instance, a user might retrieve email via a HiperLAN/2 interface to a notebook computer in a briefcase, but read messages and reply to them via his or her PDA [Frodigh2000].

2.1.1 Characteristics of Wireless Mobile Ad Hoc Networks

           Wireless mobile ad hoc networks have significant characteristics as follows [Hekmat2004, Corson1999, Frodigh2000]:

1) Dynamic Network Topology
Each node in an ad hoc network is free to move randomly. This feature makes the network topology change unpredictably. Also, an ad hoc network may be comprised of both bi-directional and unidirectional links [Corson1999]. Thus, using ad hoc networks could augment mobility and flexibility of nodes in the network [Frodigh2000]. Even though the network topology varies, connectivity in the network should be maintained to allow applications and services to operate without disruption. In particular, this characteristic will affect the design of routing protocols. In addition, a user in an ad hoc network will require access to a fixed network, such as the Internet, even if nodes are mobile. This needs mobility management functions allowing network access for devices located several radio hops away from a network access point [Hekmat2004].

2) Bandwidth-Limited and Fluctuating Capacity Links
Wireless links will remain to have substantially lower capacity compared to their hardwired counterparts [Corson1999]. Besides, the throughput of wireless communications in real environments is often much less than a radio’s maximum transmission rate, because there may be the effects of multiple access, fading, noise, and interference conditions, and so on [Corson1999].
           The effects of high bit-error rates may be more severe in a multi-hop ad hoc network, because the aggregate of all link errors affects a multi-hop path. Moreover, more than one end-to-end route can use a given link if the link were to break. This could disrupt several sessions during periods of high bit-error transmission rates. Thus, this will affect the routing function. However, efficient functions for link layer protection, such as forward error correction (FEC), and automatic repeat request (ARQ), can significantly improve the link quality [Hekmat2004].

3) Low-Power and Resource-Limited Operation
In most cases, the network nodes in a wireless ad hoc network may depend on batteries or other exhaustible means for their energy [Corson1999]. This feature makes the power budget tight for all the power-consuming components in a mobile device. For example, this will affect CPU processing, memory size and usage, signal processing, and transceiver output/input power [Hekmat2004]. For these nodes, energy conservation should be considered for the optimization as a key system design criterion [Corson1999].

4) Constrained Physical Security
In general, mobile wireless networks are more likely to be vulnerable to physical security threats than are fixed-cable nets. For example, there are the increased possibility of eavesdropping, spoofing, and denial-of-service attack that should be carefully considered. Often current link security techniques are applied to wireless networks to diminish security threats [Corson1999, Zhou1999].

5) Decentralized Network Control
As an advantage, the decentralized nature of network control in mobile ad hoc networks supports extra robustness against the single points of failure of more centralized approaches [Corson1999, Zhou1999].

2.2 DESCRIPTION OF THE DSR PROTOCOL

           This Section gives a brief overview of the Dynamic Source Routing (DSR) protocol, in terms of its main two mechanisms, namely, Route Discovery and Route Maintenance.

2.2.1 Properties of the DSR Protocol

           The Dynamic Source Routing (DSR) protocol [Johnson2001, Johnson1996, Maltz2001, Broch1998] is a simple and efficient routing protocol designed particularly for utilization in multi-hop wireless ad hoc networks of mobile nodes. The network using DSR is entirely self-organizing and self-configuring, and it does not require existing network infrastructure or administration, as mentioned in the previous sections. Network nodes cooperate with each other to transmit packets for communication through multi-hops between nodes, which are not directly located within the wireless transmission range of one another.
           The DSR protocol [Johnson2001, Johnson1996, Maltz2001, Broch1998] is based on source routing. Source routing means that a source of each packet has an ordered list of nodes to reach a destination node. The main advantage of a source routing design is that intermediate nodes do not have to contain the latest routing information in order to forward packets because the packet’s source has already decided all of the routing information. Thus, intermediate nodes just forward the packets to the next node based on the route contained in the packet that is forwarded. Because of this characteristic, associated with the completely on-demand nature of the DSR protocol, each node does not have to transmit any type of periodic route advertisement or neighbor detection packets.
           The DSR protocol [Johnson2001, Johnson1996, Maltz2001, Broch1998] consists of two main mechanisms that allow the discovery and maintenance of source routes in ad hoc networks. They are Route Discovery and Route Maintenance. Route Discovery is the mechanism by which a node S trying to send a packet to a destination node D acquires a route from the source node S to the destination node D. Route Discovery is performed only when S wishes to transmit a packet to D but the source S does not know any route to D. Route Maintenance is the mechanism by which the source node S detects a link failure as it sends a packet to the destination node D and repairs or finds a new route to maintain the connectivity. Specifically, when S sends a packet to D, the network topology may have been changed and the source route to D is not valid any longer. Then S can try to utilize alternative routes it knows to D. However, if S does not know any other route, it performs Route Discovery again to find a new route. Route Maintenance is invoked while S is sending data packets to D after Route Discovery.
           Route Discovery and Route Maintenance are respectively performed totally on demand. In particular, different from any other protocols, DSR does not require periodic packets of any kind at any level within the network. For instance, DSR does not send any periodic routing advertisement, link status sensing, or neighbor detection packets, and does not depend on these functions from any basic protocols in the network. Due to this on-demand behavior and no use of periodic advertisement packets, using fewer overhead packets enables DSR to be scalable smaller, especially when all nodes are almost stationary with respect to each other and thus all routes needed for the current interaction have already been found. As the network topology begins to change or communication patterns change, the routing packet overhead of DSR automatically focuses only on the need to track the routes currently in use [Johnson2001, Maltz2001].
           After Route Discovery is performed, a source node may learn and cache multiple routes to any destination. This feature gives more benefits in avoiding the overhead of needing to perform a new Route Discovery every time when a route in use is broken. Figure 2.2 shows the basic functions of the DSR protocol [Maltz2001].

           Maltz explains the construction of a source route by broadcasting a ROUTE REQUEST in his paper, as Figure 2.2 shows [Maltz2001]. The source receives a ROUTE REPLY containing the route found that can be followed to forward data packets. On the other hand, a ROUTE ERROR is sent to the source upon the detection of route failure. The address in parentheses indicates the next hop to forward a packet [Maltz2001].
           In the next subsection we describe basic features of DSR Route Discovery and Route Maintenance [Johnson2001, Johnson1996, Maltz2001]. Then, the following subsections will delve more into additional features of the DSR protocol, in terms of the optimized features of Route Discovery and Route Maintenance [Johnson2001, Johnson1996, Maltz2001].

2.2.2 Basic DSR Route Discovery

           When node S initiates to transmit a new packet to some other node D, it stores a source route indicating the sequence of hops that the packet should be forwarded to be delivered to D in the header of the packet [Johnson2001]. Usually, S will acquire a proper source route by looking at its Route Cache of routes obtained in the past. However, if there is no route available in its cache, it will perform the Route Discovery protocol to dynamically find a new route to D. In this case, S is called the initiator and D is called the target of the Route Discovery.

           For instance, Figure 2.3 [Johnson2001] gives an illustration of an example of the Route Discovery, where node A is trying to discover a route to node E. To perform the Route Discovery, A floods a ROUTE REQUEST message as a single local broadcast packet to all nodes currently within the wireless transmission range of node A [Johnson2001]. Each ROUTE REQUEST message finds the initiator and target of the Route Discovery, and also includes a unique request id, given by the initiator of the ROUTE REQUEST. Each ROUTE REQUEST also holds a record indicating the list of the address of each intermediate node through which this particular copy of the ROUTE REQUEST message has been forwarded [Johnson2001]. This route record is started from an empty list when the initiator starts to perform the Route Discovery. When another node receives a ROUTE REQUEST and if the node is the target of the Route Discovery, it sends a ROUTE REPLY back to the initiator of the Route Discovery, containing a copy of the accumulated route record from the ROUTE REQUEST [Johnson2001]. When the initiator receives the ROUTE REPLY, it stores this route in its Route Cache for utilization in transmitting succeeding packets to this destination. Otherwise, if this node receiving the ROUTE REQUEST has lately seen another ROUTE REQUEST message containing this same request id from the same initiator, or if it recognizes that its own address is already contained in the route record in the ROUTE REQUEST message, it ignores the REQUEST [Johnson2001]. Otherwise, this node appends its own address to the route record in the ROUTE REQUEST message and floods it to its neighbors, which are within the transmission range of this node, as a local broadcast packet with the same request id [Johnson2001].
           When the destination node returns the ROUTE REPLY to the initiator of the Route Discovery, the destination node will usually search its own Route Cache for a route back to the initiator. If the route is available in its Route Cache, the destination node will use it for the source route to return the ROUTE REPLY. Otherwise, the destination node D may perform its own Route Discovery for the target node A. However, in order to avoid possible infinite recursion of Route Discoveries, it must piggyback this ROUTE REPLY on its own ROUTE REQUEST message for the initiator. The destination node can also simply use the reverse route of the route record in the ROUTE REQUEST. For the MAC protocols such as IEEE 802.11 requiring a bi-directional frame exchange as a part of the MAC protocol, this route reversal is preferred since it prevents the overhead of a possible second Route Discovery, and it tests the found route to make sure that it is bi-directional before the Route Discovery initiator starts using the route [Johnson2001].
           When the initiator performs a Route Discovery, it saves a copy of the original packet in a local buffer called the Send Buffer. The Send Buffer includes a copy of each packet that cannot be sent by this node because the initiator does not have a source route to the destination of the packet yet. Each packet in the Send Buffer is stamped with the time that it was stored into the Buffer and is discarded after placing in the Send Buffer for some timeout period [Johnson2001]. In order to prevent the Send Buffer from overflowing, a FIFO or other replacement strategy may be used to evict packets before the timeout period expires. While a packet resides in the Send Buffer, the initiator should initiate a new Route Discovery for the packet’s destination address. However, the initiator should limit the number of initiations of Route Discovery to the same destination because the destination node may not be reachable at the moment [Johnson2001]. Particularly, the limited wireless transmission range and mobility of the nodes may cause disconnection between the initiator and the destination. Due to the movement patterns and the density of nodes in the network, network partitions may be rare or may be common [Johnson2001]. If a new Route Discovery were performed for each packet transmitted by the initiator, a large number of unproductive Route Request packets would be flooded throughout the subset of the ad hoc network within the transmission range of the node. In order to reduce the overhead from such Route Discoveries, exponential backoff can be used to limit the rate of performing new Route Discoveries that may be initiated by any node for the same target. If the node tries to send additional data packets to this same node more frequently than this limit, the following packets should be buffered in the Send Buffer until a Route Reply is received, but the initiator should not perform a new Route Discovery until the minimum allowable interval between new Route Discoveries for this destination has been elapsed [Johnson2001].

2.2.3 Basic DSR Route Maintenance

           When a node transmits or forwards a packet to some destination node, Route Maintenance is used to detect if there was any change in the network topology that has caused the route used by the packet to be broken [Maltz2001]. Thus, when a node initiates to send a packet using a source route, each node forwarding the packet has responsibility to confirm that the packet has been received by the next hop along the source route [Johnson2001]. The data packet can be retransmitted up to a maximum number of attempts until this confirmation of receipt is received in the previous node [Johnson2001]. For instance, as illustrated in Figure 2.4, node A has initiated a packet for E using a source route through intermediate nodes B, C, and D. In this situation, node A has the responsibility to confirm the receipt of the packet at node B, node B is responsible for the receipt of the packet at node C, node C is responsible for the receipt at node D, and node D is responsible for receipt at the target E finally.

           In many wireless MAC protocols, such as IEEE 802.11 [Brenner1997], the MAC protocol retransmits each packet until a link-layer acknowledgement is received, or until a maximum number of transmission trials has been made. As an alternative, DSR may utilize a passive acknowledgement or may request an explicit network-layer acknowledgement [Maltz2001].
           If the packet is retransmitted by some hop with the maximum number of times and no receipt confirmation is received, this intermediate node returns a ROUTE ERROR message to the original initiator of the packet [Johnson2001]. When the initiator receives the ROUTE ERROR message, it removes this broken route from its cache. In order to retransmit the original packet, if the initiator has another route in its Route Cache (that stores alternative routes obtained from additional ROUTE REPLYs for its previous Route Discoveries), it can retransmit the packet using the new route without delay. Otherwise, it may initiate a new Route Discovery for this destination node [Johnson2001].

2.2.4 Optimizations of the DSR Protocol

           This subsection will explain additional features of Route Discovery and Route Maintenance of DSR to optimize its performance. The current implementation of our application is mostly based on basic operations of DSR; the advanced features discussed here due to the optimized DSR protocol will be explored in the future work.

2.2.4.1 Additional Route Discovery Features

           This Section introduces four optimization features related with the Route Discovery phase in DSR as follows: caching overheard routing information, replying to ROUT REQUESTs using cached routes, preventing route reply storms, and ROUTE REQUEST hop limits.

1) Caching Overheard Routing Information
           If a node, which is neither a source nor a target, forwards or overhears any packet, the node may add the routing information from the packet to its own Route Cache. That is, the source route used in sending a data packet, the accumulated route in the route record of a ROUTE REQUEST, or the route contained in a ROUTE REPLY may all be cached by any node [Johnson2001].

2) Replying to ROUTE REQUESTs using Cached Routes
           A node receiving a ROUTE REQUEST, which is not a target but an intermediate node, searches its own Route Cache for a route to the target of the ROUTE REQUEST [Johnson2001]. If a route is available in its Route Cache, the node usually returns a ROUTE REPLY to the initiator of the ROUTE REQUEST, rather than forwarding the ROUTE REQUEST to the nodes within the transmission range of the node. In the ROUTE REPLY, it sets the route record to the combined route gained by concatenating the accumulated route record of the current ROUTE REQUEST with the available route to the target found in the Route Cache of the intermediate node [Johnson2001]. This feature may shorten the latency for Route Discovery process.

3) Preventing Route Reply Storms
           In some cases, ROUTE REPLY storms may occur [Johnson2001]. For example, when a node initiates a ROUTE REQUEST to its neighbors, who are located within the wireless transmission range of the node, neighboring nodes having ability to reply to the ROUTE REQUEST based on information in their Route Caches may attempt to reply by transmitting ROUTE REPLYs to the initiator of the ROUTE REQUEST. If each of those nodes has a route to reach the target of the ROUTE REQUEST, it will send a ROUTE REPLY to the initiator of the REQUEST. In that situation, large number of ROUTE REPLYs may be received by the initiator, thereby wasting bandwidth and possibly increasing the number of network collisions in the area [Johnson2001, Maltz2001]. Besides, since some nodes may be closer to other nodes, there will be different ROUTE REPLYs containing routes of different lengths. If nodes are able to promiscuously listen to the channel, they can lessen the number of ROUTE REPLYs transmitted to the initiator of the ROUTE REQUEST by deferring the transmission of ROUTE REPLYs for a random period of time based on the length of the source route in their ROUTE REPLYs. If a node delaying the transmission of ROUTE REPLY hears that the initiator of the ROUTE REQUEST uses a shorter source route to the target than the one it is deferring, the node does not send the ROUTE REPLY because the initiator already has a shorter route to the target [Johnson2001, Maltz2001].

4) ROUTE REQUEST Hop Limits
           In order to limit the number of intermediate nodes to forward the copy of the ROUTE REQUEST, each ROUTE REQUEST message contains a hop limit. As the ROUTE REQUEST is forwarded, this limit is decremented by one, and the REQUEST packet is discarded if the limit reaches zero before finding the destination [Johnson2001]. As an example, at first, a non-propagating ROUTE REQUEST with hop limit zero is transmitted. This mechanism is inexpensive method to decide if the destination is currently a neighbor of the initiator or if a neighbor node has a cached route to the destination, effectively utilizing the caches of the neighbor nodes as an extension of the initiator’s own cache. If no ROUTE REPLY is received within a short timeout, then a propagating ROUTE REQUEST with no hop limit is transmitted [Johnson2001].

2.2.4.2 Additional Route Maintenanc Features

           This Section provides four optimization features associated with Route Maintenance in the DSR protocol as follows: packet salvaging, automatic route shortening, increased spreading of ROUTE ERROR messages, and caching negative information.

1) Packet Salvaging
           When the route used in sending a data packet is broken, a ROUTE ERROR message is sent to a source node, as a part of Route Maintenance mechanism [Johnson2001]. Then, the intermediate node detecting the broken route may attempt to salvage the data packet brought the ROUTE ERROR rather than discarding it. In order to salvage the data packet, the intermediate node sending a ROUTE ERROR looks up its own Route Cache for a route from itself to the target of the data packet causing the ROUTE ERROR. If such a route is available in the node’s Route Cache, the node may salvage the data packet after informing the ROUTE ERROR by substituting the original source route on the data packet with the route from its own Route Cache. Then, the node forwards the data packet to the next node indicated along this source route. When salvaging a packet in this manner, the data packet is also indicated as having been salvaged, in order to avoid salvaging a same packet multiple times. Otherwise, it is possible for the packet to go into a routing loop, as different nodes repeatedly salvage the same packet and replace the source route on the packet with routes from their own Route Caches [Johnson2001].

2) Automatic Route Shortening
           If one or more intermediate hops of the route in use become no longer needed, the source route in use may be automatically shortened. This method of automatically shortening a route in use is quite similar to the use of passive acknowledgements. Specifically, if a node is able to overhear a packet containing a source route by setting its network interface in promiscuous receive mode, this node investigates the unused part of the source route. If the node is not the next hop recorded in the packet but is recorded in the later unused part of the source route, then it can assume that the intermediate nodes before itself in the source route contained in the packet are not needed any more for the packet to be delivered in the target node [Johnson2001].

3) Increased Spreading of ROUTE ERROR Messages
           When a source node receives a ROUTE ERROR from an intermediate node having a route failure, this source node may flood this ROUTE ERROR to its neighbor nodes by piggybacking it on its next ROUTE REQUEST. This method prevents stale information in the caches of nodes around this source node from generating ROUTE REPLYs containing the same invalid link for which this source node received the ROUTE ERROR [Johnson2001].

4) Caching Negative Information
           In some situations, DSR could probably have a benefit from nodes that cache negative information in their Route Caches [Johnson2001]. As an example in Figure 2.4, if node A caches the information that the link between C and D is currently broken, rather than simply removing the broken route from its Route Cache, node A is able to guarantee that no ROUTE REPLY containing the broken route in response to its new ROUTE REQUEST is accepted. This negative cached information must have a short expiration period, because node A will not accept to place any routes including the broken link in its Route Cache, while this negative information resides in the cache, even if this broken link starts working again [Johnson2001].
           There is another case in which cached negative information might be beneficial. The case is where a link is supporting highly changeable service, sometimes working properly but sometimes not working. For example, this kind of case can occur in the situation where the link is on the border of the limit of the sending node’s wireless transmission range and there are considerable sources of interference near the receiving node on this link. In this situation, caching the negative information containing the broken route can prevent a source node from adding this troublesome link back to its Route Cache during the brief period in which it is working properly [Johnson2001].

2.3 IEEE 802.11 MAC PROTOCOL

           In our system, WLAN cards with the IEEE 802.11 P2P (Peer-To-Peer) capability are used for wireless communication between Pocket PCs. Thus, in order to help readers easily understand the analyses of experimental results reported in Chapter 4, this Section will give a brief overview of the IEEE 802.11 technology, particularly in terms of its architecture, physical layer and MAC sublayer, and basic access method to the medium, known as Distributed Coordination Function (DCF), based on a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) for wireless transmission.

2.3.1 Architecture Components

           The basic service set (BSS) is the primary building block of the IEEE 802.11 architecture [Crow1997]. A BSS refers to a group of stations that are directly controlled by a single coordination function, such as Distributed Coordination Function (DCF) or Point Coordination Function (PCF), which will be explained below. The geographical area composed of the BSS is called as the basic service area (BSA), which is similar to a cell in a cellular communication network. Theoretically, all stations in a BSS can have communications directly with all other stations in a BSS. However, since transmission medium degradation may be caused by multi-path fading or interference from adjacent BSSs reutilizing the same physical-layer characteristics, such as frequency and spreading code or hoping pattern, it can produce some stations to appear “hidden” from other stations [Crow1997].
           An ad hoc network is an intentional grouping of stations into a single BSS for the goals of internetworked communications with no help of any infrastructure network. Figure 2.5 illustrates an independent BSS (IBSS), which is the formal name of an ad hoc network in the IEEE 802.11 standard.

           In the BSS, any station can communicate with any other station without requiring a centralized access point (AP) to channel all traffics through it [Crow1997].
           Different from the ad hoc network, infrastructure networks are utilized to provide wireless users for specific services and range extension. In the context of the IEEE 802.11, infrastructure networks are constructed using APs. The AP is similar to the base station in a cellular communications network. The AP provides range extension by supporting the integration points needed for network connectivity between multiple BSSs, therefore forming an extended service set (ESS) [Crow1997].
           The BSS appears one large BSS to the logical link control (LLC). The ESS is made up of multiple BSSs that are integrated together by a common distribution system (DS). The DS can be regarded as a backbone network that is in charge of MAC layer transport of MAC service data units (MSDUs). Based on the specifications of the IEEE 802.11, the DS is implementation independent. Thus, the DS could be a wired IEEE 802.3 Ethernet LAN, IEEE 802.4 token bus LAN, IEEE 802.5 token ring LAN, fiber distributed data interface (FDDI) metropolitan area network (MAN), or another IEEE 802.11 wireless medium. Even though the DS could physically be the same transmission medium as the BSS, they are logically not same because the DS is exclusively used as a transport backbone to transfer packets between different BSSs in the ESS [Crow1997].
           In addition, an ESS can provide a gateway access for wireless users into a wired network such as the Internet. This is achieved by way of a device known as a portal. The portal is a logical entity specifying the integration point on the DS where the IEEE 802.11 network incorporates with a non-IEEE 802.11 network. If the network is an IEEE 802.x, the portal integrates functions that are similar to a bridge. That is, the portal provides range extension and the translation between different frame formats. Figure 2.6 gives an illustration of a simple ESS developed with two BSSs, a DS, and a portal access to a wired LAN [Crow1997].

2.3.2 IEEE 802.11 Layers Description

           As any other 802.x protocol, the IEEE 802.11 protocol covers the physical layer and the Medium Access Control (MAC) layer [Brenner1997, Crow1997]. Figure 2.7 summarizes a brief description of the IEEE 802.11 layers [Crow1997].

2.3.2.1 Physical Layer

           The IEEE 802.11 draft specification requires three different physical-layer implementations, which are Frequency Hopping Spread Spectrum (FHSS), Direct Sequence Spread Spectrum (DSSS), and Infrared (IR) light [Brenner1997].
           The FHSS uses the 2.4 GHz Industrial, Scientific, and Medical (ISM) band, for instance between 2.4000 and 2.4835 GHz. In the U.S., a maximum of 79 channels are stated in the hopping set. The first channel has a center frequency of 2.402 GHz, and all succeeding channels are spaced 1 MHz apart. The 1 MHz separation is required by the Federal Communications Commission (FCC) for the 2.4 GHz ISM band. The channel separation matches to 1 Mb/s of instantaneous bandwidth. Three different hoping sequence sets are formed with 26 hopping sequences per set. Different hopping sequences make multiple BSSs possible to coexist in the same geographical area, which may become crucial to reduce congestion and maximize the total throughput in a single BSS. Having three different sets is in order to avoid extended collision periods between different hopping sequences in a set. The minimum hop rate allowed is 2.5 hops/s [Crow1997].
           The DSSS also uses the 2.4 GHz ISM frequency band, where the 1 Mb/s basic rate is encoded by differential binary phase shift keying (DBPSK), and a 2 Mb/s enhanced rate uses differential quadrature phase shift keying (DQPSK). The spreading is achieved by dividing the available bandwidth into 11 sub-channels, each 11 MHz wide, and using an 11-chip Barker sequence to spread each data symbol [Crow1997].
           The IR (Infrared) specification recognizes a wavelength range from 850 nm to 950 nm. The IR band is devised for indoor use only and works with non-directed transmissions. The IR specification is created to enable stations to receive line-of-site and reflected transmissions [Crow1997].

2.3.2.2 MAC Layer

           The Medium Access Control (MAC) sublayer has responsibilities for the channel allocation procedures, protocol data unit (PDU) addressing, frame formatting, error checking, and fragmentation and reassembly [Crow1997]. The transmission medium can solely operate in the contention mode. The operation of the transmission medium in the contention mode requires all stations to contend for access to the channel when each packet is transmitted. The medium can also alternate between the contention mode and non-contention mode, known as the contention period (CP) and a contention-free period (CFP) respectively [Crow1997]. While the medium is in the CFP, the medium usage is mediated by the AP, thus removing the need for stations to content for channel access. The IEEE 802.11 provides three different types of frames, which are management, control, and data. The management frames are utilized for station association and disassociation with the AP, timing and synchronization, and authentication and de-authentication [Crow1997]. Control frames are used for handshaking during the CP, for positive acknowledgements during the CP, and to end the CFP. Data fames are used for the transmission of data during the CP and CFP, and can be combined with polling and acknowledgements during the CFP [Crow1997].

           Figure 2.8 illustrates the standard IEEE 802.11 frame format [Crow1997]. Note that if the optional Wired Equivalent Privacy (WEP) protocol is used, the frame body (MSDU) is variable-length field consisting of the data payload and 7 octets for encryption and decryption. The IEEE Standard 48-bit MAC addressing is for identifying a station [Crow1997]. The 2 duration octets present the time (in microseconds) the channel will be allotted for successful transmission of a MAC protocol data unit (MPDU). The type bits indicate the frame as control, management, or data. The subtype bits also show the type of frame such as Clear to Send control frame, etc. Error detection is checked by a 32-bit cyclic redundancy check (CRC) [Crow1997].

2.3.3 Basic Access Method: CSMA/CA

           The Distributed Coordination Function (DCF) is a basic channel access protocol for asynchronous data transmission in the contention period based on a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism [Brenner1997, Sheu2002, Issariyakul2003]. As defined in the standard, all stations must support the DCF [Crow1997]. The DCF operates exclusively in the ad hoc network, and either works solely or works with the PCF in an infrastructure network. The MAC architecture is described in Figure 2.9 that shows the DCF sitting directly on top of the physical layer and supporting contention services [Crow1997].
           Contention services imply that each station with an MSDU queued for transmission must contend for access to the channel. If the MSDU is transmitted, the station must contend again for access to the channel for all following frames. Contention services support fair access to the channel for all stations [Crow1997].
           A CSMA protocol works in the following way. A station wishing to transmit senses a medium. If the medium is busy (e.g. some other station is transmitting), then the station will defer its transmission to a later time. If the medium is sensed free, then the station is permitted to transmit [Brenner1997].

           These kinds of protocols are very effective when network loads are not heavy because it allows stations to transmit with minimum latency. However, there is always a chance of occurrence of collision when more than one station transmits simultaneously, because stations sense the medium free and decide to transmit at one. These collision situations must be identified so that the MAC layer can retransmit the packet by itself and not by upper layers, which may cause significant delays [Brenner1997].

           In the Ethernet case, this collision is identified by the transmitting stations, which enter a retransmission stage based on an exponential random backoff algorithm [Brenner1997]. Even though the Collision Detection is a good mechanism on a wired LAN, they cannot be applied to a Wireless LAN environment, due to the following two reasons [Brenner1997]:

  • · Implementation of a Collision Detection Mechanism would require the implementation of a Full Duplex radio, enabling transmitting and receiving at once, which is an approach increasing the price significantly.


  • · Different from the wired LAN environment using the Collision Detection mechanism, the assumption that all stations hear each other is not true on a wireless environment. That is, the fact that a station wishes to transmit and senses the medium free does not necessarily mean that the medium is free around the receiver area.

  •            In order to solve these problems, the IEEE 802.11 provides a Collision Avoidance mechanism combined with a positive acknowledgement scheme, as follows [Brenner1997]:
               A station is willing to transmit and senses the medium. If the medium is busy, then the station defers the transmission. If the medium is free from the specified time (called DIFS, Distributed Inter Frame Space, in the standard), then the station is allowed to transmit. The receiver will check the CRC of the received packet and transmit an acknowledgement packet (ACK). The receipt of the acknowledgement means to the sender no collision occurred. If the sender does not receive ACK, it will resend the same fragment until it receives the ACK or throw away after a certain number of retransmission [Brenner1997].

               In IEEE 802.11 [Crow1997], carrier sensing is done in terms of two layers, which are physical carrier sensing at the air interface and virtual carrier sensing at the MAC sublayer. Physical carrier sensing recognizes the existence of other IEEE 802.11 WLAN users by analyzing all detected packets, and also identifies activity in the channel through relative signal strength from other source [Crow1997].
               A source station performs virtual carrier sensing by transmitting Request To Send (RTS), Clear To Send (CTS), and data frames containing MPDU duration information in their headers. An MPDU, a complete data unit being passed from the MAC sublayer to the physical layer, contains header information, payload, and a 32-bit CRC. The duration information indicates the amount of time (microseconds) after the end of the current frame that the channel will be used to complete the successful transmission of the data or management frame [Crow1997]. Stations in the BSS utilize the duration information to modify their network allocation vectors (NAVs), indicating the amount of time that has to elapse until the present transmission session is done and the channel can be checked out again if it is idle or not. The channel is indicated as busy if either the physical or virtual carrier sensing mechanisms say the channel is busy. The wireless medium is accessed based on priority controlled through the utilization of Inter Frame Space (IFS) time intervals between the transmissions of frames. The IFS intervals are required periods of idle time on the transmission medium. There are three IFS intervals specified in the standard as follows [Brenner1997, Crow1997]:
              

  • Short Inter Frame Space (SIFS): This interval is the smallest IFS, which is followed by PIFS and DIFS respectively. When a station is only required to wait a SIFS, it has priority access over those stations that are required to wait a PIFS or DIFS before transmitting. Therefore, SIFS has the highest-priority for accessing to the communications medium.

  • Point Coordination Function IFS (PIFS): This interval is used by the Access Point (AP) to obtain access to the medium before any other station. This interval value is a SIFS plus slot time, for example 78 microseconds.

  • DCF-IFS (DIFS): This interval is IFS used for a station wishing to start a new transmission, which is calculated as PIFS plus one slot time, for instance 128 microseconds.

               For the basic access mechanism, when a station senses the idleness of the channel, the station waits for a DIFS period and samples the channel again. If the channel is still idle, the station sends an MPDU. The receiver calculates the checksum and decides the correctness of the received packet. If the received packet is correct, the receiver waits a SIFS interval and transmits a positive acknowledgement frame (ACK) back to the sender station for the successful transmission [Crow1997]. Figure 2.10 illustrates a timing diagram explaining the successful transmission of a data frame [Crow1997].

               When the data frame is transmitted, the duration information of the frame is utilized to inform all stations in the BSS how long the medium will be busy. All stations hearing the transmission of the data frame adjust their NAVs according to the duration field value containing the SIFS interval and the ACK of the data frame. When a collision occurs, a source station continues transmitting the complete MPDU because the source station in a BSS cannot hear its own transmissions. If the MPDU is larger, for example 2300 octets, a lot of channel bandwidth is wasted because of a corrupt MPDU. The station can use RTS and CTS control frames in order to reserve channel bandwidth before it transmits an MPDU so that the amount of bandwidth wasted is minimized when a collision occurs [Crow1997]. RTS and CTS control frames are relatively small like 20 octets for RTS and 14 octets for CTS compared to the maximum size of MPDU such as 2346 octets. After successfully contending for the channel, the source station transmits the RTS control frame first with a data or management frame queued for transmission to an indicated destination station. All stations in the BSS hearing the RTS packet read the duration field and adjust their NAVs based on the duration information contained in the RTS, as previously shown in Figure 2.8 [Crow1997]. The destination station transmits a CTS packet in response to the RTS packet after spending an SIFS idle period. Stations hearing the CTS packet update their NAVs based on the duration field value of the received CTS packet. After the source station receives the CTS successfully, the source station virtually confirms that the medium is stable and reserved for the successful transmission of its MPDU. Note that stations can update their NAVs based on the RTS from the source station and CTS from the destination station, which is helpful to combat the “hidden terminal?problem. Figure 2.11 illustrates the transmission of an MPDU using the RTS/CTS mechanism [Crow1997].

               The RTS/CTS mechanism is optional that stations can use RTS/CTS always or use RTS/CTS or not based on the RTS_Threshold (RT: manageable parameter). So, stations use RTS/CTS when the MSDU exceeds the value of RT. Otherwise, they do not use the RTS/CTS. If a collision occurs with RTS or CTS MPDU, bandwidth wasted will be far less when compared to a large data MPDU [Crow1997]. However, if there is a slightly loaded medium, additional latency is imposed by using the RTS/CTS frames causing the extra overhead. Large MSDU passed from the LLC to the MAC may require fragmentation to support reliability. The fragmentation is performed based on the manageable parameter Fragmentation_Threshold [Crow1997].
               A random backoff procedure is used to perform the collision avoidance portion of CSMA/CA. If a station wants to transmit a frame and senses the channel is busy, the station waits for a DIFS until the channel becomes idle, and then calculates a random backoff time [Crow1997]. In the IEEE 802.11, time is slotted in time period that is correspondent to a Slot_Time. The Slot_Time in the IEEE 802.11 is much smaller than an MPDU and is utilized to set the IFS interval and decide the backoff time for stations in the CP [Crow1997]. The random backoff time is an integer value corresponding to a number of time slots. At first, the station calculates a backoff time between 0 and 7. After the medium becomes idle after a DIFS period elapsed, stations decrease their backoff timers until the medium becomes busy again or the time reaches 0. If the time has not decremented to 0 and the status of medium becomes busy, the station freezes its timer. When the timer is reached zero finally, the station transmits its frame. If more than one station reach zero simultaneously, a collision will occur, and each station should generate a new backoff time between 1 and 15 [Crow1997]. The idle time after a DIFS period is called the contention window (CW). The benefit of this channel access method is that it encourages fairness among stations. However, it has weakness in that it probably could not support a distributed time-bounded service (DTBS), which is for traffic bounded by specified time delays to achieve an acceptable quality of service such as packet-sized voice and video [Crow1997]. Fairness is maintained because each station has to contend again for the channel after every transmission of an MSDU. All stations have equal chances of obtaining access to the channel after each DIFS interval. With DCF, there is no mechanism to guarantee minimum delay to stations supporting time-bounded services [Crow1997].
               In order to support time-bounded services, the IEEE 802.11 standard provides the optional use of the point coordination function (PCF) [LaMaire1996, Crow1997]. In the PCF, a point coordinator or PCF station always has a priority control of the medium. PCF station in the PCF means an access point. Hence, the use of PCF and support of time-bounded services are limited to networks with infrastructure mode [Crow1997]. Thus, this PCF will not be covered in details because this document focuses on the ad hoc mode operation of the IEEE 802.11 WLAN.

    2.4 RELATED WORK

               This Section reviews previous studies on the performance evaluation of the DSR protocol when compared with other routing protocols, and the testing of optimization features of DSR, particularly in terms of modifications of conventional cache structure in DSR.

    2.4.1 Comparative Studies

               There are various kinds of comparative studies regarding the performance of the DSR protocol and other routing protocols in ad hoc networks [Camp2002, Raju2002, Jiang2001, Broch1998]. In addition, some researchers compare the traditional DSR protocol with the modified DSR protocol [Zhong2003]. This Section will introduce these comparative works done by other researchers in the past. In particular, when comparative studies are described, the performance of DSR is mainly addressed, rather than other details about the performance of other routing protocols in ad hoc networks.

               Camp and her colleagues [Camp2002] studied performance characteristics of two location-based routing protocols for ad hoc networks, namely, Location-Aided Routing (LAR) and Distance Routing Effect Algorithm for Mobility (DREAM). They compared the performance of these two protocols with the DSR protocol and a protocol flooding all data packets. They simulated 50 moving nodes based on the random waypoint model by using the ns-2 simulator. In the random waypoint model, each node moves from one destination to a next destination with randomly selected locations, speed (speed of mobility of each node), and pause time (time for each node to stay at each random destination). They used four performance metrics, namely, protocol overhead, network-wide data load, end-to-end delay, and data packet delivery ratio. In particular, for the performance analysis of the DSR protocol, the result shows that data packet delivery ratio decreases as the speed increases at a short pause time because the random waypoint model produces a dynamic network topology at a high speed and short pause time. Further, the end-to-end delay increases, as speed increases at a short pause time. More control packets are used when the speed increases at a short pause time. Also, the data packet delivery ratio (the number of data packets delivered over the number of data packet transmitted) decreases at relatively high speeds and short pause times. Finally, data packet load (the number of data byte transmissions per data packet delivered) remains constant as the speed increases at a short pause time because of the behaviors of flooding of DSR in order to find a new route. Additionally, the paper reports that location information and promiscuous mode operation improve the performance of the DSR protocol.

               Zhong and Yuan [Zhong2003] also studied the performance of the DSR protocol in special scenario using location information. They compared the efficiency of the modified DSR protocol with that of the traditional DSR protocol. The modified DSR is the combined protocol of the traditional DSR features in special scenarios with location information. Each node contains local information rather than global information in the routing of wireless ad hoc networks. They integrated the DSR protocol with location information given by the two special scenarios, which are cross and cycle circumstances. Thus, when a node sends a packet, it checks its location table, and then chooses an optimal route to reach its destination. Once the path is defined, the packet is immediately transmitted with a way of multi-hops. The result of these experiments with 8 participating nodes shows that the modified DSR protocol performs more efficiently than the traditional DSR protocol in the two specified scenarios.

               Raju and Garcia-Luna-Aceves [Raju2001] wrote a paper titled Scenario-based Comparison of Source Tracing and Dynamic Source Routing Protocols for Ad Hoc Networks. Their paper proposes source tracing as a new workable method to routing in ad hoc networks where routers communicate the second-to-last hop and distance in preferred routes to destination nodes. They used two source-tracing algorithms. One is Bandwidth Efficient Source Tracing (BEST), which is a table-driven protocol by which routers maintain routing information for all destinations. The other is the Dynamic Source Tree (DST) protocol, which is an on-demand routing protocol by which routers maintain routing information for only those destinations to whom they need to forward data. The DSR protocol is used for simulation experiments to compare those two protocols because DSR has been shown to use less control overhead packets than other on-demand routing protocols. The results of the simulation experiments are that DST demands far less control packets to obtain comparable or better average delays and percentage of packet delivered than DSR, and that BEST accomplishes comparable results to DSR while maintaining routing information for all destinations.

               Jiang and Garcia-Luna-Aceves [Jiang2001] conducted a study on performance comparison of three protocols for ad hoc networks. They compared the performance of three protocols, which are Source Tree Adaptive Routing (STAR), Ad Hoc On-Demand Distance Vector (AODV), and Dynamic Source Routing (DSR). They tested the performance of three protocols using the GloMoSim simulation environment. The metrics used to measure the performance of three routing protocols for ad hoc networks are control overhead, amount of data delivered, and average latency in packet delivery. In particular, the amount of data delivered means the number of data packets delivered with same amount of data flow. For example, when data flow is 20, if the amount of data delivered is 60, 40 data packets are delivered redundantly. They indicate that DSR has the lowest data delivery rate compared to the other two protocols. In addition, DSR has the lowest control overhead in comparison with the other two protocols. However, for the latency in packet delivery, DSR does not perform better. Sometimes, DSR takes more latency to deliver a data packet compared to the other two protocols.

               Finally, we want to introduce the study of Broch and his colleagues [Broch1998]. Their paper shows the results of a detailed packet-level simulation with the comparison of four multi-hop wireless ad hoc network routing protocols covering a range of design choices, such as Destination-Sequenced Distance Vector (DSDV), Temporarily-Ordered Routing Algorithm (TORA), Dynamic Source Routing (DSR), and Ad Hoc On-Demand Distance Vector (AODV). They extended the ns-2 network simulator to correctly model the MAC and physical-layer behavior of the IEEE 802.11 wireless LAN standard, containing a realistic wireless transmission channel model, and demonstrated the results of simulations of networks consisting of 50 mobile nodes. As a movement model, they used the random waypoint model. They used three performance metrics, which are packet delivery ratio, routing overhead (regarding every transmission of the routing packet as one transmission), and path optimality (the difference of used paths and length of the shortest path physically existed). They varied pause time between 0 second and 900 seconds in two different speeds, 1 m/s and 20 m/s. Also, they tried the same experiments with different number of participating nodes, such as 10, 20, 30 nodes during the fixed simulation time, 900 seconds. The result shows, focusing on the performance of the DSR protocol, that DSR performs better than the rest of three protocols. For the data delivery ration, DSR provides above 95 percent delivery ratio of the data packets sent under different scenarios consisting of different number of nodes, various pause times, and two different speeds. In addition, DSR uses much less number of routing packets compared to the other three protocols. Furthermore, DSR optimally utilizes paths it takes. The result regarding the path optimality represents that DSR uses the shortest path in most of times.

    2.4.2 Testing Optimization Features of the DSR Protocol

               Some researchers tried to improve the performance of the DSR protocol in ad hoc networks by testing its optimization features. In particular, this Section will introduce some studies on the effects of improved cache structures on the performance of the DSR protocol in ad hoc networks [Lou2002, Wu2002, Hu2000, Hu2002]. In addition, the study on the optimization of the DSR protocol by reducing Route Discovery Reply packets will be described [Seet2003].

               Lou and Yuguang [Lou2002] studied the effects of different cache organizations on the performance of the DSR protocol in ad hoc networks. They tested two types of cache organizations, namely, a path cache and a link cache. A path cache is structured that each cache entry represents an entire path from a source to all destinations, while a link cache has each individual link to one destination. Thus, a link cache has the potential to use the acquired route information more efficiently. However, if the cache is not updated properly, the out-of-date cache information may cause more route errors. Then, it leads more expensive operation, such as Route Discovery. In their paper, they studied two types of link update mechanisms, which are a static timeout mechanism and an adaptive timeout mechanism. The static timeout mechanism uses the expiration time of a link using a statistically assigned lifetime, while the adaptive timeout is proposed as the link timeout interval to diverse node mobility levels on the basis of the estimation from a moving average of real link lifetime statistics. They uses three metrics to measure the performance of cache organizations in the DSR protocol for ad hoc networks, such as routing overhead, packet delivery ratio, and end-to-end delay. The results shows that a link cache organization without a proper stale link removal method could have severe performance degradation due to the large number of route error messages occurred. However, using a proper timeout method, the link cache organization reduces the routing overhead significantly and outperforms the path cache when the network load is heavy. Also, they recommended that switching between two types of cache organizations dynamically in response to the network load condition could improve the overall performance of the DSR protocol.

               Another study is done to improve the performance of the DSR protocol by optimizing cache structures [Wu2002]. The paper shows the implementation of the extended DSR protocol by maintaining two nodes disjoint path as a consequence of respective Route Discovery process. The paper explains that the efficiency of the DSR protocol largely depends on the “hit ratio” of route cache. That is, the high efficiency occurs when the route from a source to a destination exists in source’s cache. Thus, when the “miss” of route cache occurs, the source cannot avoid invoking the relatively expensive Route Discovery process. Therefore, the paper proposes an approach to reduce the occurrence of Route Discovery process. As a result, the paper explains the effectiveness of multi-path construction process as a way for the reduction of additional overhead caused by the expensive Route Discovery process due to the lack of paths in cache.

               Hu and Johnson [Hu2000] presented the effects of different design choices for the cache structure in the DSR protocol for wireless ad hoc networks in their paper. They insist that caching is a significant component in order to reduce the overhead of performing a new Route Discovery before sending each data packet. However, caching can also bring risks in maintaining routing information in a cache after the information is not valid any more because of a changed network topology. They divided the problem into choices of cache structure, cache capacity, and cache timeout. Using detailed simulations of wireless ad hoc networks of 50 mobile nodes, they studied a larger number of different caching algorithms using a range of design choices, and simulated each cache mainly over a set of 50 different movement scenarios derived from 5 different types of mobility model. Their evaluations includes packet delivery ratio, routing packet overhead, packet delivery latency, and path optimality relative to the shortest path, obtained by each caching algorithm. The result shows that a cache structure based on a graph representation of individual link performs better than that based on complete paths through the network. Moreover, they found that there are some subtle relationships between cache timeout policies and cache capacity limits. Further, caches of unlimited capacity or with no cache timeout limits perform significantly worse.

               Hu and Johnson [Hu2002] conducted another study to improve the performance of the DSR protocol by reducing overhead caused by stale information in the route cache of each node. They explains that stale information in the cache of each node substantially increase the risk of cache cross-pollution because stale routing information in one node’s cache does not exist any longer. Even when a node has actually learned the invalid route, it is still possible for the node to hear the stale information again. In their paper, they present a new mechanism called epoch numbers to reduce this problem of cache staleness, by stopping the re-learning of stale information of a link after knowing that the link is not valid. Their scheme allows a node having heard both of a broken link and a discovery of the same link to sequence the two events in order to decide whether the link break or the link discovery occurred before the other. Their paper reported that their solution performs well in that stale information generally cannot override fresh information and their solution does not increase packet overhead. Hu and Johnson [Hu2002] present that their solution works by providing exactly the information needed to sequence discovery of new network links and notification of broken links, thus preventing nodes from re-learning stale cache information.

               As another way of optimizing the DSR protocol in ad hoc networks, Seet et al. [Seet2003] propose a new way to reduce network traffics. Many works have been done for the optimization of the DSR protocol in reducing the routing packet overhead, especially from a large saving on route requests, which is usually called Route Discovery process. This paper suggests a new way of optimization of the DSR protocol in terms of decreasing route discovery reply packets, which are known as the reply packets in response to the Route Discovery packets. The authors explain why the route reply process is more expensive to transmit than route requests. Since the route replies are unicast packets (while the route requests are broadcast packets), they use additional control packets for RTS/CTS exchanges in the 802.11 MAC. Moreover, the route discovery reply packets will be larger in size because they have to carry the whole source route obtained by the route request. Therefore, a large number of route discovery reply packets can still consist of a significant portion of the wireless bandwidth. In addition, the device power is needed to process them. Both bandwidth and power are the most precious resources in mobile ad hoc networks. Thus, in terms of the efficiency of resources in mobile ad hoc networks, a large portion of cached routes from route discovery reply packets can also be more harmful than beneficial to the routing performance. In particular, the large amount of route discovery reply packets will be detrimental when nodes are highly mobile, because routes acquired become out-of-date more frequently, making their utilization less effective. Therefore, this paper proposes an optimization version of the DSR protocol by minimizing the number of cached route discovery reply packets. Since a source only uses the shortest path in its cache, the longer route than the current route will not be useful when the route discovery reply packet containing the longer route is received in the source. Hence, a destination node only sends the route discovery reply packets when the route request packet contains a shorter route. Otherwise, the destination node discards the route request packet. The authors conclude that the proposed optimization of the DSR protocol reduces the number of Route Discovery overhead at higher node mobility (shorter pause time), while it does not have much benefit at lower node mobility (longer pause time).

    2.4.3 Other Studies

               There are also other types of papers discussing about different aspects of the performance of the DSR protocol for wireless ad hoc networks. This Section will introduce some studies. One is a study focused on improving the Quality of Service (QoS) in respect to data transmission of DSR [Leung2001]. Another study introduces a way to reduce energy consumption in the DSR protocol for ad hoc networks [Xu2001]. In addition, one proposes a new way to improve security of the DSR protocol [Ghazizadeh2002].

               According to the study of Leung et al. [Leung2001], the lack of Quality-of-Service (QoS) is indicated as one of weaknesses of the existing best-effort routing protocols, such as DSR not supporting QoS in regard to the data transmission. They suggest a new QoS metric, which supports end-to-end reliability, in order to select end-to-end routes to give more stability and reliability to routes. Thus, they present a distributed multi-path dynamic source routing (MP-DSR) protocol for wireless ad-hoc networks to increase QoS feature in regard to end-to-end reliability. Their simulation study demonstrates the high effectiveness of the presented protocol particularly, in terms of the higher achievement of successful packet delivery ratio as compared to the current DSR protocol.

               One study introduces a geographical adaptive fidelity (GAF) algorithm to reduce energy consumption in wireless ad hoc networks [Xu2001]. According to the paper of Xu et al. [Xu2001], GAF saves energy by identifying nodes, which are equal from a routing perspective and by turning off unnecessary nodes while maintaining a constant level of routing fidelity. GAF controls this policy using application and system-level information. Nodes that source or sink data remain turned-on and intermediate nodes watch and balance the use of energy. GAF does not depend on the underlying ad hoc routing protocol. Xu and his colleagues simulated GAF with unmodified Ad-hoc On-Demand Distance Vector (AODV) and Dynamic Source Routing (DSR). The result shows that the simulated GAF can consume 40% to 60% less energy than an unmodified ad hoc routing protocol. Furthermore, the simulations of GAF demonstrate that network lifetime increases proportional to node density. For instance, a four-fold increase in node density brings network lifetime increase from 3 to 6 times, depending on the mobility pattern. More generally, GAF is a good example of adaptive fidelity, a method proposed for enlarging the lifetime of self-configuring systems by employing redundancy to conserve energy while keeping application fidelity.

               Ghazizadeh and his colleagues [Ghazizadeh2002] presented Security Aware Adaptive Dynamic Source Routing Protocol (SADSR), which is a secure routing protocol for mobile ad hoc networks. They explain that SADSR verifies the routing protocol messages using digital signatures on the basis of asymmetric cryptography. The basic ground on SADSR is to have multiple paths to each destination and store a local trust value for each node in the network. Each path has an assigned trust value based on the trust values of the nodes, which happen on that path. The preferred paths for routing are selected based on higher trust values. They implemented their approach in the ns-2 simulator and measured the performance of SADSR and DSR. Their results prove that in the existence of malicious nodes, SADSR performs better than DSR in the packet delivery ratio with an acceptable network load.

    2.5 SUMMARY

               This Chapter has given an overview and knowledge backgrounds of this thesis work in the design, implementation and analysis of an ad hoc messenger application in mobile ad hoc networks.
               Section 2.1 discussed wireless ad hoc networks. A wireless ad hoc network consists of a collection of mobile hosts without the aid of any pre-existed infrastructure or centralized administration. Main characteristics of wireless ad hoc networks are described, such as a dynamic network topology, bandwidth-limited and fluctuating capacity links, low-power and resource-limited operations, constrained physical security, and decentralized network control.
               Section 2.2 described main features of the DSR protocol. The DSR protocol is a simple and efficient routing protocol for multi-hop wireless ad hoc networks using mobile devices. The DSR protocol uses source routing for a packet from a source to be delivered in the target node. Instead of flooding a periodic broadcast packet to obtain routing information, this DSR protocol transmits ROUTE REQUEST message to a source’s neighboring nodes located within the wireless transmission range of the source node totally based on a node’s need. Thus, each node does not have to transmit any type of periodic route advertisement or neighbor detection packets. The DSR protocol consists of two main mechanisms, Route Discovery and Route Maintenance. Route Discovery is initiated when there is no available route in the Route Cache of the source node. When a target node received the Route Discovery request, the target node returns route discovery reply packet containing the route found to the initiator of the Route Discovery. Then, the obtained route from the Route Reply sent by the target node is used to transmit subsequent data packets. Route Maintenance is the mechanism where a source node detects link failure, while it sends a packet to the target node using the source route found by Route Discovery. When the route in use is broken, the source node tries to use alternative routes in its Route Cache. If any alternative route is not available in its Route Cache, a Route Discovery is initiated to find a new route again.
               Section 2.3 gave a brief overview of the IEEE 802.11 MAC protocol for readers to understand the analyses of results more easily because our experiments are based on wireless transmission between each node using the IEEE 802.11b technology. The IEEE 802.11 defines three physical layer implementations, which are Frequency Hopping Spread Spectrum (FHSS), Direct Sequence Spread Spectrum (DSSS), and IR. Both FHSS and DSSS operate on the 2.4 GHz ISM band. The IR band is devised for indoor use only and works with non-directed transmissions. The Distributed Coordination Function (DCF) is a basic channel access protocol for asynchronous data transmission in the contention period based on a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism. All stations must support DCF, which mainly operates in an ad hoc network. The CSMA protocol is used for each node to avoid collision by deferring its transmission to a later time when the channel is busy. After each node waits for a certain period of time until the medium is free, a node in DCF mode wishing to transmit a packet can gain access to the medium by using four-way handshake consisting of RTS/CTS (Request-To-Send/Clear-To-Send) packet. The sending node sends RTS packet to the receiving node. If the receiver accepts the request, it sends CTS to the sender of RTS. If no collisions occur, the sender can begin transmitting its data packet.
               Finally, Section 2.4 reviewed some related works that have done previously. Some papers discussing the performance of the DSR protocol by comparing it with other routing protocols in ad hoc networks were introduced. In addition, some studies testing some optimization features of the DSR protocol were discussed. Finally, some studies to improve DSR with different methods were also surveyed.

               In the next Chapter, we will describe design details to realize our system, such as hardware and software components used, network environments, specific design features, metrics to evaluate the performance of the DSR protocol, etc.

  • Last updated: Thursday, July 29, 2004

    Home Contents Contact Us