Selection and prioritization of forwarding candidates information technology essay

Abstract: An efficient and robust data delivery algorithm for distributed data fusion in mobile ad hoc sensor networks, where each node controls its data rows and learns routing decisions solely based on their local knowledge. This can be analyzed the localized algorithm in a formal model and validate our model using simulations. The experiments indicate that controlled data delivery processes significantly increase the probability of relevant data being fused in the network even with limited local knowledge of each node and relatively small hops of data delivery. In this approach there is no querying process and each node proactively forwards the data to one of its neighbors. A novel Position-based Opportunistic Routing (POR) protocol is proposed, in which several forwarding candidates cache the packet that has been received using MAC interception. If the best forwarder does not forward the packet in certain time slots, suboptimal candidates will take turn to forward the packet according to a locally formed order. In this way, as long as one of the candidates succeeds in receiving and forwarding the packet, the data transmission will not be interrupted. Each node has to intelligently deliver data solely based on the knowledge about itself and its neighbors. Moreover, the data delivery processes need to be survivable to failures. The challenge is, with various decisions made by individual sensors, how to minimize the communication overhead and maximize the probability of relevant data being fused in the network.

1. Introduction

An ad hoc network is a collection of wireless mobile nodes dynamically forming a temporary network without the use of any existing network infrastructure or centralized administration. Due to the limited transmission range of wireless network interfaces, multiple network ” hops” may be needed for one node to exchange data with another across the network. This paper focuses reliability in terms of providing robustness to node failures in ad hoc networks. Node failures may be intermittent[2]. Geographic routing [3] uses location information to forward data packets, in a hop-by-hop routing fashion. Greedy forwarding is used to select next hop forwarder with the largest positive progress toward the destination while void handling mechanism is triggered to route around communication voids [3]. No end-to-end routes need to be maintained, leading to GR’s high efficiency and scalability. However, GR is very sensitive to the inaccuracy of location information [4]. In the operation of greedy forwarding, the neighbor which is relatively far away from the sender is chosen as the next hop. If the node moves out of the sender’s coverage area, the transmission will fail. In fact, due to the broadcast nature of the wireless medium, a single packet transmission will lead to multiple reception. If such transmission is used as backup, the robustness of the routing protocol can be significantly enhanced. The concept of such multicast-like routing strategy has already been demonstrated in opportunistic routing ([6], [7], [8]). However, most of them use link-state style topology database to select and prioritize the forwarding candidates. As mentioned in [8], the batching used in these protocols also tends to delay packets and is not preferred for many delay sensitive applications.


The design of POR is based on geographic routing and opportunistic forwarding. The nodes are assumed to be aware of their own location and the positions of their direct neighbors. Neighborhood location information can be exchanged using one-hop beacon or piggyback in the data packet’s header. While for the position of the destination, we assume that a location registration and lookup service which maps node addresses to locations is available just as in [5]. It could be realized using many kinds of location service ([11], [12]). In this scenario, some efficient and reliable way is also available. When a source node wants to transmit a packet, it gets the location of the destination first and then attaches it to the packet header [4].

Selection and prioritization of forwarding candidates

One of the key problems in POR is the selection and prioritization of forwarding candidates. Only the nodes located in the forwarding area [14] would get the chance to be backup nodes. The forwarding area is determined by the sender and the next hop node. A node located in the forwarding area satisfies the following two conditions: 1) It makes positive progress toward the destination2) Its distance to the next hop node should not exceed half of the transmission range of a wireless nodeAccording to the required number of backup nodes, some of them will be selected as forwarding candidates. The priority o f a forwarding c and id at e is decided by its distance to the destination. The nearer it is to the destination, the higher priority it will get. When a node sends or forwards a packet, it selects the next hop forwarder as well as the forwarding candidates among its neighbors. The next hop and the candidate list comprise the forwarder list. Here, Algorithm used to show the procedure to select and prioritize the forwarder list. The candidate list will be attached to the packet header and updated hop by hop. Only the nodes specified in the candidate list will act as forwarding candidates [6].

Limitation on Possible Duplicate Relaying

Due to collision and nodes’ movement, some forwarding candidates may fail to receive the packet forwarded by the next hop node or higher priority candidate, so that a certain amount of duplicate relaying would occur. If the forwarding candidate adopts the same forwarding scenario as the next hop node, which means it also calculates a candidate list, then in the worst case, the propagation area of a packet will cover the entire circle comprising the destination as the center and the radius can be as large as the distance between the source and the destination. Fig. 2. Duplicate relaying is limited in the region enclosed by the bold curve.

MAC Modification and Complementary Techniques

A. MAC Interception

The broadcast nature of 802. 11 MAC: all nodes within the coverage of the sender would receive the signal. However, its RTS/CTS/DATA/ACK mechanism is only designed for unicast. It simply sends out data for all broadcast packets with CSMA. Therefore, packet loss due to collisions would dominate the performance of multicast-like routing protocols. Here, we did some alteration on the packet transmission scenario. In the network layer, we just send the packet via unicast, to the best node which is elected by greedy forwarding as the next hop.

B. MAC Callback

When the MAC layer fails to forward a packet, the function implemented in POR, MAC callback will be executed. The item in the forwarding table corresponding to that destination will be deleted and the next hop node in the neighbor list will also be removed. If the transmission of the same packet by a forwarding candidate is overheard, then the packet will be dropped without reforwarding again;

C. Interface Queue Inspection

One of the key points of POR is that when an intermediate node receives a packet with the same ID, it means a better forwarder has already taken over the function. Hence, it will drop that packet from its packet list. Besides maintaining the packet list, we also check the interface queue.

3. Virtual Destination -Based Void Handling

In order to enhance the robustness of POR, void handling mechanism based on virtual destination is proposed.

Trigger Node

The first is at which node should packet forwarding switch from greedy mode to void handling mode. The mode change happens at the void node, can be used to route around the communication hole. It is better than Path 2. If the mode switch is done at Node A, Path 3 will be tried instead of Path 2 while Path 1 still gets the chance to be used. A message called void warning, which is actually the data packet returned from Node B to Node A with some flag set in the packet header, is introduced to trigger the void handling mode.

Virtual Destination

To handle communication voids, almost all existing mechanisms try to find a route around. During the void handling process, the advantage of greedy forwarding cannot be achieved as the path that is used to go around the hole is usually not optimal.

4. Performance Evaluation

To evaluate the performance of POR, we simulate the algorithm in a variety of mobile network topologies and compare it with AOMDV [15] and GPSR [5]. The following metrics are used for performance comparison: 1. Packet delivery ratio: The ratio of the number of data packets received at the destination(s) to the number of data packets sent by the source(s). 2. End-to-end delay: The average and the median end-to-end delay are evaluated, together with the cumulative distribution function of the delay. 3. Path length: The average end-to-end path length for successful packet delivery. Packet forwarding times per hop (FTH). The average number of times a packet is being forwarded from the perspective of routing layer to deliver a data packet over each hop. Packet forwarding times per packet (FTP). The average number of times a packet is being forwarded from the perspective of routing layer to deliver a data packet from the source to the destination


A. Forwarding Candidate Number Evaluation

First evaluate the effect of the number of forwarding candidates on POR’s performance. Generally, larger value of N will result in higher robustness as more nodes serve as backups. In addition, the increase in the number of forwarding candidates will also enlarge the packet header, thus introducing more overhead.

B. Packet Delay Comparison

The simulation results show that in first scenario, that neighbor nodes have low speed, both strategies packet delay are the same, because of methods similar structure . In second scenario, that neighbor nodes have high speed.

C. Effect of Mobility

To evaluate the effect of mobility on the performance of routing protocols, we first consider the single-flow case in uniformly distributed network. The same simulation scenario as that is used to create a path length controllable dynamic topology. It can be observed that when the maximum node speed is not larger than 15 m/s, GPSR still outperforms AOMDV but the reverse is true when node mobility keeps increasing.

D. Effect of Communication Hole

By changing the maximum node speed, we obtain the simulation results shown in Fig; we can observe that in the face of communication hole, GPSR’s void handling mechanism fails to work well. Even when the maximum node speed is 5 m/s, only 90 percent of the data packets get delivered which is relatively poor compared to the other protocols.


The problem of reliable data delivery in highly dynamic mobile ad hoc networks is addressed. Constantly changing network topology makes conventional ad hoc routing protocols incapable of providing satisfactory performance. In the face of frequent link break due to node mobility, substantial data packets would either get lost, or experience long latency before restoration of connectivity. Inspired by opportunistic routing, this paper propose a novel MANET routing protocol POR which takes advantage of the stateless property of geographic routing and broadcast nature of wireless medium.