Using Opportunistic Routing To Improve Throughput Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract. Widespread use of mobile nodes in wireless communication has paved way for a new paradigm in communication. Dynamic nature of mobility in wireless networks poses many challenges in transmission of information in air. Wireless networks are group of nodes which communicate with each other over a wireless communication channel. Wireless networks have become an attractive communication paradigm, in this communication era. Many cities and public places have deployed wireless networks to provide internet access to residents and local businesses.

Ad hoc networks are a category of wireless networks, whose decentralized nature, minimal configuration and quick deployment make them suitable for applications ranging from emergency situations like natural disasters, military sensing and tracking, disaster rescue after an earth quake, real time traffic monitoring, tracking, etc.

Routing protocol design is critical in order to improve the performance and reliability of wireless networks. A good routing scheme increases the packet delivery ratio and the throughput of the network. Due to unreliable wireless links and interference during concurrent transmissions, routing in wireless network presents a great challenge. Opportunistic Routing (OR) technique attempts to cope with unreliable transmissions by exploiting the broadcast nature and spatial diversity of the wireless medium, in an efficient manner [3]. ***above idea, a new routing scheme, Opportunistic Routing (OR), has been proposed to mitigate the impact of unreliable wireless links by exploiting the broadcast nature and spatial diversity of the wireless medium****

The efficient utilization of resources in ad hoc networks using OR scheme gives lesser throughput than expected when minimum hop count metric is used. To combat the above limitations, Extremely OR (ExOR) scheme with ETX metric in hybrid wireless networks is proposed [7].

A hybrid network is formed by placing a sparse network of base stations in an ad hoc network. Opportunistic routing is a technique, which chooses a path dynamically on per-transmission basis. Expected Transmission Count (ETX) is the routing metric used by OR to choose Candidate Relay Sets (CRS). It minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination [2].

The proposed work is the implementation of ExOR routing protocol by incorporating ETX metric and realised in Hybrid Scenario. The simulation study reveals that this approach efficiently utilises resources and increases the end-to-end throughput.

Keywords: ExOR, ETX, Routing, Throughput, Ad hoc networks, Hybrid networks

1. Introduction

Hybrid wireless networks are integration of both 'ad hoc - infra structure less' and 'Wireless - Infra structure based' networks. The use of base stations in Hybrid wireless networks is to avoid overwhelming burden of relaying packets between source and destination.

Fig. 1. Hybrid Wireless Network Scenario

Portable devices like PDAs and iPhones hosts a wide range of applications, which includes web browsing, online gaming, and audio/video streaming. They have multiple radio interfaces and support different wireless protocols such as Bluetooth, Wi-Fi and 3G. It has become vital for such devices to efficiently utilise resources available in hybrid wireless network environment to achieve high data throughput and support bandwidth intensive applications [7].

In Hybrid wireless networks, wireless nodes have radio interfaces and can communicate with each other through multi hop ad hoc transmissions. Base Stations (BTs) are connected to the Internet using high bandwidth wire line connections. If a wireless node is within the coverage of a BT, it can communicate with the BT using single-hop infrastructure mode. Optionally, a wireless node might have a connection to a 3G base station that covers all wireless nodes under consideration. The optional 3G connection can be used as a control channel for nodes to exchange control information, such as the geographical locations of nodes.

Packets can be transmitted using two transmission modes: ad-hoc mode and infrastructure mode. We assume that all nodes in the network are cooperative and forward each other's packets to their destinations using Opportunistic Routing [4]. Some assumptions concerning the behaviour of the nodes and base stations that participate in hybrid networks are made. They are:

Wireless nodes and Wi-Fi Base stations are randomly located in the square area.

Wireless nodes are homogeneous which have the same set of transmission rates and equivalent effective transmission ranges.

The coverage area of BT does not overlap with each other. Each wireless node could connect to at most one BT.

Each node is identified by a unique ID within the network.

Through a separate control channel (e.g., 3G), every node knows the geographical locations of its neighbours, base stations, and the destination node.

The proposed work is organised as follows, Section 2 explains the use of OR scheme in comparison with traditional routing protocols. Section 3 depicts ExOR protocol's design aspects. Section 4 describes the performance evaluation of the ExOR routing protocol. Section 5 concludes with the discussion on implementation details of the proposed work.

2. Need for Opportunistic Routing

This section gives the benefits of using OR over the traditional Unicast Routing.

OR scheme extends the concept of Geographical routing [4]. Geographical routing uses the node information in forwarding the packets to the destination, likewise OR also uses the node which is currently available for the transmission of the packet. This node availability reduces the overhead of finding the node information in the network [5].

Opportunistic routing scheme chooses each hop of a packet's route after the transmission for the present hop, so that the choice can reflect on which intermediate node has actually received the transmission [5]. This choice gives multiple opportunities for each transmission to make better progress. OR gives high throughput than the traditional routing, since each transmission may have more independent chances of being received and forwarded [1][14].

Traditional routing protocols follow the concept of routing similar to wired networks by abstracting the wireless links as wired links, and find the shortest, least cost, or highest throughput paths between a source and destination [4]. Owing to these wireless natures, when a packet is unicast to a specific next-hop node of the sender at the network layer, all neighbouring nodes in the effective communication range of the sender will overhear the packet at the physical layer. It's likely that some of the neighbours may receive the packet correctly when the specified next-hop node doesn't exist. So, this work aims to make use of the successful reception on these neighbouring nodes instead of retransmitting the packet on the specified link to save precious bandwidth and energy [3].

ExOR and (MAC independent Opportunistic Routing and Encoding) MORE are few existing opportunistic routing protocols [6]. MORE protocol is independent of MAC and network layer. This protocol randomly mixes packets before forwarding, in order to ensure that routers that hear the same transmission do not forward the same packet. The other advantage is, it does not need any special scheduler to coordinate the routers and can run directly on top of 802.11 [8]. The current opportunistic routing protocol, ExOR is an integration of MAC and network layer [5]. It dynamically chooses the path on a per transmission basis.

Fig. 2. Layered Architecture of ExOR

3. System Design

The following section gives a brief description of the following modules

Routing Methodology in ExOR

ExOR Protocol's design

ETX Metric

3.1. Routing Methodology in ExOR

A source node S has a packet to be forwarded to a distant destination D. Between the source and destination, there are other wireless nodes willing to participate in ExOR. When the source broadcasts the packet, a sub-set of the nodes receive the packet. But, the node which is closer to the destination among the sub-set of nodes only broadcasts the packet. Again, the nodes that receive this second transmission agree on the closest receiver, and broadcast the packet in turn. This process continues until the destination has received the packet [3].

Fig. 3. Traditional Routing and ExOR Routing Methodologies

3.2. Extremely Opportunistic Routing (ExOR) Protocol's Design

Extremely Opportunistic Routing (ExOR) is a combination of routing protocol and media access control. It follows a simple rule, "Of all the nodes that were able to successfully decode the transmission, the one that is closest to the destination should forward it on". ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect those intermediate nodes that actually receive the transmission. This deferred choice gives each transmission multiple opportunities to make progress. As a result, ExOR can use long radio links with high loss rates, which would be avoided by traditional routing. ExOR is a recent technique that achieves high throughput in lossy wireless links and chooses paths dynamically on a per transmission basis.

3.2.1 Design Challenges

Although simple to define, the rule is quite difficult to implement in a distributed network. ExOR's design faces the following challenges:

The nodes must agree on which subset of them receives the packet. For this to happen, an agreement protocol should be implemented. This protocol must have low overhead such that it does not overwhelm ExOR's potential throughput gain.

The node that receives a packet, which is the node "closest" to the ultimate destination, should be the one that forwards the packet. Thus ExOR must have a metric reflecting the likely cost of moving a packet from any node to the destination.

In a large dense network there is a penalty for using too many nodes as potential forwarders, since the costs of agreement grow with the number of participants. Thus ExOR must choose only the most useful nodes as participants.

ExOR must avoid simultaneous transmissions by different nodes to minimize collisions.

The design is achieved with the following inclusions:

Node State

Each ExOR node maintains state for each batch of packets in which it is participating, as indicated by the node's presence in the batch's forwarder list.

Packet Buffer: Stores the successfully received packets in the current batch.

Local Forwarder List: It contains a copy of the prioritized list of nodes.

Forwarding Timer: It is the time that when a node predicts that it should start forwarding packets from its packet buffer.

Transmission Tracker: Records the measured rate at which the currently sending node is sending, along with expected number of packets it has left to send.

Batch Map: It indicates, for each packet in a batch, the highest priority node known to have received a copy of that packet.

Packet Format

ExOR operates on batches of packets. ExOR header follows the Ethernet header information and is followed by the packet's data.

Ver: It indicates the current ExOR version.

HdrLen and PayloadLen: They indicate the size of the ExOR header and payload respectively.

BatchID: Indicates which batch the packet belongs to.

PktNum: It is the current packet's offset in the batch. This offset corresponds to the batch map entry for the packet.

BatchSz: It indicates the number of packets in the batch.

Fig. 4. ExOR packet Header format [5]

FragSz: Indicates the size of the currently sending node's fragment.

FragNum: It is the current packet's offset within the fragment.

FwdListSize: It specifies the number of forwarder in the list.

ForwarderNum: It is the current sender's offset within the list.

Forwarder List: It is a copy of the sender's local forwarder list.

Batch Map: It is the copy of the sending node's batch map.

Batch Preparation

The source node begins by collecting a batch of packets all destined to the same destination node. The source chooses a unique batch ID and selects a Forwarder List. The source prepends an ExOR header to each packet of the batch, containing the batch ID and a forwarder list.

Forwarder List

The source specifies the forwarder's list in priority order based on the expected cost of delivering a packet from each node in the list to the destination. The cost metric is the number of transmissions required to move a packet along the best traditional route from the source to the destination counting both hops and retransmissions.

The cost metric used is ETX, ultimately aims to find the path with higher throughput. ExOR uses only the forward delivery probability and also uses the knowledge of the complete set of inter node loss rates.

Packet Reception

A node examines the header of every successfully decoded packet. If the forwarder list includes the node, the node adds the packet to the buffer for the corresponding batch. For each entry on the batch map contained in the packet, the node compares the entry with the corresponding entry in the local batch map, and replaces the later if the packet's entry indicates a high priority node.

Scheduling Transmissions

ExOR attempts to schedule the time at which nodes send their fragments, so that only one node sends at a time. This scheduling allows high priority nodes to be sent first. It also helps avoid collision, which is particularly important since ExOR chooses a sub-set of nodes (CRS) to forward one packet at a time.

3.3 ETX Metric Design

3.3.1 General

Expected transmission count (ETX) is a metric that finds high throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination [2]. It incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.

The metric must account the following issues:

Wide range of link loss ratios.

The existence of links with asymmetric loss ratios.

The interference between successive hops of multi-hop paths.

3.3.2 Metric Calculation

The ETX of a route is a sum of the ETX for each link in the route. The ETX of the link is calculated using the forward (df) and reverse (d­r) delivery ratios of the link. The forward delivery ratio (df) is the measured probability that a data packet successfully arrives at the recipient. The reverse delivery ratio (dr) is the probability that the ACK packet is successfully received.

But ExOR uses only the forward delivery ratio (df) of the ETX metric.

Other important ETX characteristics are,

ETX is based on delivery ratios, which directly affects throughput.

ETX detects and appropriately handles asymmetry by incorporating loss ratios in each direction.

ETX can use precise link loss ratio measurements to make ¬ne-grained decisions between routes.

ETX penalizes routes with more hops, which have lower throughput due to interference between different hops of the same path.

ETX tends to minimize spectrum use, which should maximize overall system capacity.

ETX decreases the energy consumed per packet, as each transmission or retransmission may increase a node's energy consumption.

The delivery ratios df and dr are measured using dedicated link probe packets. Each node broadcasts link probes of a fixed size, at an average period (one second in the implementation). To avoid accidental synchronization, is jittered by up to ±0.1 per probe. Because the probes are broadcast, 802.11b does not acknowledge or retransmit them. Every node remembers the probes it receives during the last w seconds (ten seconds in our implementation), allowing it to calculate the delivery ratio from the sender at any time t as:

r(t) =


Count (t-w, t) is the number of probes received during the window w, and w/ is the number of probes that should have been received. In case of the link X→Y, this technique allows X to measure dr, and Y to measure df. Because Y knows it should receive a probe from X every seconds, Y can correctly calculate the current loss ratio even if no probes arrive from X.

Calculation of a link's ETX requires both df and dr parameters. Each probe sent by a node X contains the number of probe packets received by X from each of its neighbours during the last w seconds. This allows each neighbour to calculate the df to X whenever it receives a probe from X.

4. Performance Evaluation

In this section, the packet delivery ratio and throughput of hybrid wireless networks using ExOR routing protocol is compared with that of the ad hoc wireless networks.

4.1 Methodology

This section covers the implementation of the designed protocol. The protocol builds on a C++ implementation that is included in the NS2. The code has been implemented so it corresponds well to the design.

NS2 has many built-in routing protocols such as AODV, DSDV, and DSR etc. The routing protocol, ExOR is added to NS2. NS2 is open source and has a feature of adding new protocol. NS2 analyses the routing protocol and it is very useful for researches for discovering new protocols in the area of networks.

Network topologies are simulated and trace files generated are analysed using 'Awk' Script. AWK is a data driven programming language designed for processing text based data, either in files or data streams. Using Awk script, the data points for packet delivery ratio and throughput for wireless and hybrid networks has been calculated. The values thus computed are used to visualize the results graphically using 'Gnuplot'. Gnuplot is a command driven interactive function plotting program. It can be used to plot functions and data points in both two and three dimensional plots in many different formats. It is designed primarily for the display of scientific data.

4.2 Packet Delivery Ratio

The packet delivery ratio is defined as a ratio between the number of packets received by the destination to the number of packets sent by the source.

Packet Delivery Ratio =


4.2.1 Scenario I

The hybrid wireless networks are simulated using small network setting. The network area of 200 m x 200 m is considered. There are 14 wireless ad hoc nodes, 4 wired nodes and 2 base stations located. The initial range for all the nodes in the network is 100 m. Movement of nodes and data transfer takes place according to the scenario and connection patterns. By using this setting, packet delivery ratio with different simulation times of 30, 60, 90, 120, 150, 180 seconds is calculated [Table 1].

Fig. 5. Scenario I

Table 1 Data points for plotting Packet delivery ratio in Ad hoc wireless and Hybrid networks

Time (Sec)








Ad Hoc














Fig. 6. Comparison of Packet Delivery Ratio for Ad hoc wireless and Hybrid Networks using ExOR Routing Protocol

4.3 Throughput

Throughput refers to the total amount of bytes being transferred over a particular time.

4.3.1 Scenario II

The hybrid wireless networks are simulated using small network setting. The network area of 150 m x 150 m is considered. There are 14 wireless ad hoc nodes, 2 wired nodes and 1 base station located. The initial range for all the nodes in the network is 100 m. Movement of nodes and data transfer takes according to the scenario and connection patterns. By using this setting, throughput with different simulation times of 30, 60, 90, 120, 150, 180 seconds is calculated [Table 2].

Fig. 7. Scenario II

Table 2 Data points for plotting throughput in Ad hoc wireless and Hybrid networks

Time (Sec)








Ad Hoc














Fig. 8. Comparison of throughput for Ad hoc wireless and Hybrid Networks using ExOR Routing Protocol

5. Conclusion

This paper addresses the use of opportunistic routing and proposes that it is better than the traditional routing and also presents Extremely Opportunistic Routing (ExOR), an integrated routing and MAC protocol for hybrid wireless networks in which the 'best' of multiple receivers forwards each packet. ExOR improves performance by taking advantage of long-distance but lossy links which would be avoided by traditional routing protocols. ExOR protocol is implemented using Expected Transmission Count (ETX) Metric that finds the optimal path from source to destination with higher throughput. The packet delivery ratio and throughput has been calculated. The results show that there is a 20 to 30 % increase in throughput and packet delivery ratio compared to that if implemented in ad hoc wireless networks.