Toward Consistent Information Release for ExtremelyDynamic Mobile Ad Hoc Networks

Toward Consistent Information Release for ExtremelyDynamic Mobile Ad Hoc Networks

S. Nandhini Devi

Computer science and engineering, Prist University, Trichy

Abstract

Highly dynamic Mobile ad hoc Network addresses the problem of delivering data packets in a reliable and timely manner. Most existing ad hoc routing protocols are susceptible to node mobility, especially for large-scale networks. Driven by this issue, we propose an efficient Position-based Opportunistic Routing (POR) protocol which takes advantage of the stateless property of geographic routing and the broadcast nature of wireless medium. When a data packet is sent out, some of the neighbour nodes that have overheard the transmission will serve as forwarding candidates, and take turn to forward the packet if it is not relayed by the specific best forwarder within a certain period of time. By utilizing such in-the-air backup, communication is maintained without being interrupted. The additional latency incurred by local route recovery is greatly reduced and the duplicate relaying caused by packet reroute is also decreased. In the case of communication hole, a Virtual Destination-based Void Handling (VDVH) scheme is further proposed to work together with POR. Both theoretical analysis and simulation results show that POR achieves excellent performance even under high node mobility with acceptable overhead and the new void handling scheme also works well.

1. Introduction

   Mobile ad hoc networks (MANETs) have gained a great deal of attention because of its significant advantages brought about by multihop, infrastructure-less transmission. However, due to the error prone wireless channel and the dynamic network topology, reliable data delivery in MANETs, especially in challenged environments with high mobility remains an issue. Traditional topology-based MANET routing protocols are quite susceptible to node mobility. One of the main reasons is due to the predetermination of an end-to- end route before data transmission. Owing to the constantly and even fast changing network topology, it is very difficult to maintain a deterministic route. The discovery and recovery

   procedures are also time and energy consuming. Once the path breaks, data packets will get lost or be delayed for a long time until the reconstruction of the route, causing transmission interruption. Geographic routing (GR) 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. No end-to-end routes need to be maintained, leading to GRs high efficiency and scalability. However, GR is very sensitive to the inaccuracy of location information. 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 senders coverage area, the transmission will fail.

   In GPSR (a very famous geographic routing protocol), the MAC-layer failure feedback is used to offer the packet another chance to reroute. However, our simulation reveals that it is still incapable of keeping up with the performance when node mobility increases. 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. However, most of them use link-statestyle topology database to select and prioritize the forwarding candidates. In order to acquire the internode loss rates, periodic network-wide measurement is required, which is impractical for mobile environment. The batching used in these protocols also tends to delay packets and is not preferred for many delay sensitive applications. Recently, location-aided opportunistic routing has been proposed which directly uses location information to guide packet forwarding. However, just like the other opportunistic routing protocols, it is still designed for static mesh networks and focuses on network throughput while the robustness brought upon by opportunistic forwarding has not been well exploited.

   In this project, 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. Potential multipaths are exploited on the fly on a perpacket basis, leading to PORs excellent robustness.

2. Multi-Hop Wireless Ad Hoc Network Routing Protocols

   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. In recent years, a variety of new routing protocols targeted specifically at this environment have been developed, but little performance information on each protocol and no realistic performance comparison between them is available.

   Drawback

   In areas in which there is little or no communication infrastructure or the existing infrastructure is expensive or inconvenient to use, wireless mobile users may still be able to communicate through the formation of an ad hoc network. In such a network, each mobile node operates not only as a host but also as a router, forwarding packets for other mobile nodes in the network that may not be within direct wireless transmission range of each other. Each node participates in an ad hoc routing protocol that allows it to discover multi-hop paths through the network to any other node.

   The idea of ad hoc networking is sometimes also called infrastructure less networking, since the mobile nodes in the network dynamically establish routing among themselves to form their own network on the fly. Some examples of the possible uses of ad hoc networking include students using laptop computers to participate in an interactive lecture, business associates sharing information during a meeting, soldiers relaying information for situational awareness on the battlefield, and emergency disaster relief personnel coordinating efforts after a hurricane or earthquake.

   Solution

   The results of a detailed packet-level simulation comparing four multi-hop wireless ad hoc network routing protocols that cover a range of design choices: DSDV, TORA, DSR, and AODV. We have extended the ns-2 network simulator to accurately model the MAC and physical-layer behavior of the IEEE wireless LAN standard, including a realistic wireless transmission channel model, and present the results of simulations of networks of 50 mobile nodes.

3. ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

   Multi-hop wireless networks typically use routing techniques similar to those in wired networks. These traditional routing protocols choose the best sequence of nodes between the source and destination, and forward each packet through that sequence. In contrast, coperative diversity schemes proposed by the information theory community suggest that traditional routing may not be the best approach. Cooperative diversity takes advantage of broadcast transmission to send information through multiple relays concurrently. The destination can then choose the best of many relayed signals, or combine information from multiple signals. These schemes require radios capable of simultaneous, synchronized repeating of the signal, or additional radio channels for each relay.

   Drawback

   The nodes that receive each packet must agree on their identities and choose one forwarder. The agreement protocol must have low overhead, but must also be robust enough that it rarely forwards a packet zero times or more than once. Finally, ExOR must choose the forwarder with the lowest remaining cost to the ultimate destination. Measurements of an implementation on a 38-node test-bed show that ExOR increases throughput for most node pairs when compared with traditional routing. For pairs between which traditional routing uses one or two hops, ExOR's robust acknowledgments prevent unnecessary retransmissions, increasing throughput by nearly 35%. For more distant pairs, ExOR takes advantage of the choice of forwarders to provide throughput gains of a factor of two to four.

   Solution

   The ExOR is describes, an integrated routing and MAC protocol that increases the throughput of large unicast transfers in multi-hop wireless networks. ExOR chooses each hop of a packet's route after the transmission for that hops, so that the choice can reject which intermediate nodes actually received 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 increases a connection's throughput while using no more network capacity than traditional routing.

4. Robust Cooperative Routing Protocol in Mobile Wireless Sensor Networks

   In wireless sensor networks, path breakage occurs frequently due to node mobility, node failure, and channel impairments. It is challenging to combat path breakage with minimal control overhead, while adapting to rapid topological changes. Due to the Wireless Broadcast Advantage (WBA), all nodes inside the transmission range of a single transmitting node may receive the packet; hence naturally they can serve as cooperative caching and backup nodes if the intended receiver fails to receive the packet.

   Drawback

   Wireless sensor networks are envisioned to be essential to many applications and will impact our daily life significantly. In many application scenarios, wireless sensor networks must be mobile. As an example, in wildlife monitoring or environmental study, sensors are cast in the field as well as are equipped on free-ranging animals to be monitored. In mobile wireless networks, path breakage occurs more frequently due to channel fading, shadowing, interference, node mobility as well as power failure.

   When a path breaks, rerouting or alternative routing may be necessary and should be carried out promptly. Otherwise, packet loss and large delay would occur. Different types of routing protocols have been proposed for mobile wireless ad hoc networks. However, they are not suitable for highly dynamic topologies, especially for energy and computation capability constrained sensor nodes. Therefore, prompt path recovery, energy efficiency and robustness are highly preferred characteristics for routing protocols in mobile wireless sensor networks. The broadcast nature of wireless medium has been exploited widely in literature. Without additional transmissions, nodes inside the transmission range of a sender are able to obtain a copy of the packet forwarded to an intended receiver. Dense wireless sensor networks offer the opportunity to develop novel communication and routing techniques based on cooperation among nodes in the neighborhood. The failure probability of all links is much smaller than that of a single link. Although there are many previous studies on cooperative communication and routing, most of them focus on physical layer design. Robust routing against path breakage still remains unexplored. Our main contribution is the

   investigation of distributed energy efficient robust routing catering to mobile wireless sensor networks.

   Solution

   We present a distributed robust routing protocol in which nodes work cooperatively to enhance the robustness of routing against path breakage. We compare the energy efficiency of cooperative routing with noncooperative routing and show that our robust routing protocol can significantly improve robustness while achieving considerable energy efficiency. In proposed protocol, cooperative relay is performed at each hop, so only local knowledge is necessary. Multi- node cooperation involves lower layer coordination. Our robust cooperative routing is based on cross-layer design with MAC layer as the anchor, operated under MAC protocol, which has been proven effective in our prior work. After establishing a path between source and destination nodes, robust cooperative routing is able to provide reliable packet delivery against both temporary and permanent path breakage. If a node moves away, the resulting path breakage is permanent. Interference and fading may cause temporary path failure. As a distributed approach, robust routing is relieved from the substantial control overhead for route maintenance, update and repair. Only light overhead is incurred during the procedure of robust routing.

   Through cooperation among neighboring nodes, the energy efficiency is also improved since more reliable and stable links are preferred for routing. Choosing reliable links potentially reduces retransmissions, thus saving energy and shortening delay. Our analysis shows that cooperative routing outperforms non-cooperative routing in terms of energy efficiency when link error probability or node mobility is high. Simulation result confirms that our robust cooperative routing protocol improves performance significantly in presence of node mobility and link error.

5. Incentive-Compatible Opportunistic Routing for Wireless Networks

   User-contributed wireless mesh networks are a disruptive technology that may fundamentally change the economics of edge network access and bring the benefits of a computer network infrastructure to local communities at low cost, anywhere in the world. To achieve high throughput despite highly unpredictable and lossy wireless channels, it is essential that such networks take advantage of transmission opportunities wherever they emerge. However, as opportunistic routing departs from the traditional but less effective

   deterministic, shortest-path based routing, user nodes in such networks may have less incentive to follow protocols and contribute.

   Drawback

   User-contributed wireless mesh networks are envisioned as a disruptive technology to deploy broadband network infrastructures to local communities at low cost. Avoiding the problem of rights of installation by installing at private properties and distributing the equipment and management costs among the participating users,such networks present a major cost-effective alternative for overcoming the issues that are stalling the deployment of carrier deployed wireless mesh networks. However, the deployment of user- contributed wireless mesh net- works has its own challenges. A major challenge, which is not limited only to user-contributed wireless mesh networks but applies to wireless mesh networks in general, is throughput scalability. Due to the highly unpredictable and lossy wireless channels, the throughput achieved by traditional wireless mesh networks can be quite poor. Wireless channel variations and losses are particularly serious in urban environments with many sources of interference.

   Solution

   We present the first routing protocols in which it is incentive-compatible for each user node to honestly participate in the routing despite opportunistic transmissions. We not only rigorously prove the properties of our protocols but also thoroughly evaluate a complete implementation of our protocols. We present the first routing system in which each user is stimulated to honestly participate in network routing despite opportunistic transmissions. We make the following contributions:

   • We are the first to study the problem of incentives in opportunistic routing and provide solutions.

   • We present a simple, novel and practical technique to make any member of a class of opportunistic routing protocols incentive compatible. Specifically, this class includes any opportunistic routing protocols that use loss probabilities to calculate the number of forwarding transmissions to impose structure and avoid the scalability issues of opportunistic transmissions. We rigorously prove that our technique guarantees that it is a strict dominant strategy for each user node to behave honestly. Here strict dominant strategy is a very strong solution concept in game theory. Intuitively, it means that the

     strategy (of behaving honestly) is strictly better than any other strategy for each node regardless of other nodes behavior.

   • We also design an enhanced protocol to prevent cheating not only in reporting loss rates but also in measuring them. Formally, we show that, with this enhanced protocol, it is a strict Nash equilibrium for each user node to behave honestly in both measuring and reporting. Intuitively, this means that the strategy of behaving honestly is strictly better than any other strategy for each node when other nodes are honest.

   • We completely implement our protocols in Linux and test their performance on the ORBIT lab. The experimental results verify that, with our protocols, a selfish nodes cheating behavior decreases its utility. Consequently, there are incentives for nodes to follow our protocols. Our experiments also show that compared with an opportunistic routing protocol that does not provide incentives, our protocols have a throughput gain of 5.8%-58.0%. This is because our protocols can prevent cheating behavior by selfish nodes. Hence they can bring the system throughput back to the high level achieved by opportunistic routing.

6. Existing system

   1. Overview

      Most existing ad hoc routing protocols are susceptible to node mobility, Especially for large-scale networks. Traditional topology-based MANET routing protocols (e.g., DSDV, AODV, DSR) are quite susceptible to node mobility. One of the main reasons is due to the predetermination of an end-to-end route before data transmission. Owing to the constantly and even fast changing network topology, it is very difficult to maintain a deterministic route. The discovery and recovery procedures are also time and energy consuming. Once the path breaks, data packets will get lost or be delayed for a long time until the reconstruction of the route, causing transmission interruption.

   2. Disadvantages

      • Predetermination of an end-to-end route before data transmission.

      • Once the path breaks, data packets will get lost or be delayed for a long time until the reconstruction of the route, causing transmission interruption.

7. Proposed system

   1. Overview

      The proposed techniques is 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. Potential multi paths are exploited on the fly on a per packet basis, leading to PORs excellent robustness.

   2. Advantages

      • We propose a position-based opportunistic routing mechanism which can be deployed without complex modification to MAC protocol and achieve multiple reception without losing the benefit of collision avoidance.

   • The concept of in-the-air backup significantly enhances the robustness of the routing protocol and reduces the latency and duplicate forwarding caused by local route repair.

8. System Architecture

   1. System Architecture Description:

      A system architecture or systems architecture is the conceptual design that defines the structure and/or behavior of a system. An architecture description is a formal description of a system, organized in a way that supports reasoning about the structural properties of the system. It defines the system components or building blocks and provides a plan from which products can be procured, and systems developed, that will work together to implement the overall system. This may enable one to manage investment in a way that meets business needs. The fundamental organization of a system, embodied in its components, their relationships to each other and the environment, and the principles governing its design and evolution. The composite of the design architectures for products and their life cycle processes. A representation of a system in which there is a mapping of functionality on to hardware

      and software components, a mapping of the software architecture onto the hardware architecture, and human interaction with these components. An allocated arrangement of physical elements which provides the design solution for a consumer product or life-cycle process intended to satisfy the requirements of the functional architecture and the requirements baseline. Architecture is the most important, pervasive, top- level, strategic inventions, decisions, and their associated rationales about the overall structure (i.e., essential elements and their relationships) and associated characteristics and behavior.

   2. System Architecture Diagram

   Figure 1. System Architecture Diagram

9. Data Flow Diagram

   A dataflow diagram (DFD) is a graphical representation of the "flow" of data through an information system. DFDs can also be used for the visualization of data processing (structured design). On a DFD, data items flow from an external data source or an internal data store to an internal data store or an external data sink, via an internal process.

   A DFD provides no information about the timing or ordering of processes, or about whether processes will operate in sequence or in parallel. It is therefore quite different from a flowchart, which shows the flow of control through an algorithm, allowing a reader to determine what operations will be performed, in what order, and under what circumstances, but not what kinds of data will be input to and output.

   Figure 2. Data Flow Diagram

10. Modules Description

    10.1.POR(Position-based Opportunistic Routing)

    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. 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. The packet would be dropped even if it has already been delivered into the neighborhood of the destination. At each hop, the node that forwards the packet will check its neighbor list to see whether the destination is within its transmission range. If yes, the packet will be directly forwarded to the destination. As the data packets are transmitted in a multicast-like form, each of them is identified with a unique tuple (src_ip, seq_no) Every node maintains a monotonically increasing sequence number, and an ID_Cache to record the ID (src_ip, seq_no) of the packets thathave been recently received. If a packet with the same ID is received again, it will be discarded. Otherwise, it will be forwarded at once if the receiver is the next hop, or cached in a Packet List if it is received by a forwarding candidate, or dropped if the receiver is not specified. The packet in the Packet List will be sent out after waiting for a certain number of time slots or discarded if the same packet is received again during the waiting period.

    Figure 3. Position-based Opportunistic Routing

    1. Selecting Best Forwarder

       Only the nodes located in the forwarding area would get the chance to be backup nodes. He forwarding area is determined by the sender and the next hop node. A node located in the forwarding area satisfies the following two conditions: a) It makes positive progress toward the destination. b) Its distance to the next hop node should not exceed half of the transmission range of a wireless node. Some (maybe all) of them will be selected as forwarding candidates. The priority of a forwarding candidate is decided by its distance to the destination. The nearer it is to the destination, the higher priority it will get. 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. The lower the index of the node in the candidate list, the higher priority it has. Every node maintains a forwarding table for the packets of each flow (identified as source-destination pair) that it has sent or forwarded. Before calculating a new forwarder list, it looks up the forwarding table. The forwarding table is constructed during data packet transmissions and its maintenance is much easier than a routing table. It can be seen as a trade-off between efficiency and scalability. As the establishment of the forwarding table only depends on local information, it takes much less time to be constructed. We can set an expire time on the items maintained to keep the table records only the current active flows, while in conventional

       protocols, a decrease in the route expire time would require far more resources to rebuild.

       Figure 4. Selecting Best Forwarder

    2. VDVH(Virtual Destination-based Void Handling )

       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 (e.g., with more hops compared to the possible optimal path). More importantly, the robustness of multicast-style routing cannot be exploited. In order to enable opportunistic forwarding in void handling, which means even in dealing with voids, we can still transmit the packet in an opportunistic routing like fashion; virtual destination is introduced, as the temporary target that the packets are forwarded to. Virtual destinations are located at the circumference with the trigger node as center but radius of the circle is set as a value that is large enough (e.g., the network diameter). It is used to guide direction of packet delivery during void handling.

       Figure 5. VDVH( Virtual Destination-based Void Handling )

    3. Creating Air-Backup

    When the MAC layer fails to forward a packet, the function implemented in PORmac_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; otherwise, it will be given a second chance to reroute. The packets with the same next hop in the interface queue which is located between the routing layer and MAC layer will also be pulled back for rerouting. As the location information of the neighbors is updated periodically, some items might become obsolete very quickly especially for nodes with high mobility. This scheme introduces a timely update which enables more packets to be delivered.

    Figure 6. Creating Air-Backup

11. Conclusion

    In this project, we address the problem of reliable data delivery in highly dynamic mobile ad hoc networks. 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, we propose a novel MANET routing protocol POR which takes advantage of the stateless property of geographic routing and broadcast nature of wireless medium. Besides selecting the next hop, several forwarding candidates are also explicitly specified in case of link break. Leveraging on such natural backup in the air, broken route can be recovered in a timely manner. The efficacy of the involvement of forwarding candidates against node mobility, as well as the overhead due to opportunistic forwarding is analyzed. We further confirm the effectiveness and efficiency of POR: high packet delivery ratio is achieved while the delay and duplication are the lowest. On the other hand, inherited from geographic routing, the problem of communication void is also investigated. To work with the multicast forwarding style, a virtual destination-based void handling scheme is proposed. By temporarily adjusting the direction of data flow, the advantage of greedy forwarding as well as the robustness brought about by opportunistic routing can still be achieved when handling communication voids. Traditional void

    handling method performs poorly in mobile environments while VDVH works quite well.

12. References:

1. J. Broch, D.A. Maltz, D.B. Johnson, Y.-C. Hu, and

   J. Jetcheva, A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols, Proc. ACM MobiCom, pp. 85-97, 1998.

2. M. Mauve, A. Widmer, and H. Hartenstein, A Survey on Position-Based Routing in Mobile Ad Hoc Networks, IEEE Network, vol. 15, no. 6, pp. 30- 39, Nov./Dec. 2001.

3. B. Karp and H.T. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, Proc. ACM MobiCom, pp. 243- 254, 2000.

4. S. Biswas and R. Morris, EXOR: Opportunistic Multi-Hop Routing for Wireless Networks, Proc. ACM SIGCOMM, pp. 133-144, 2005.

5. S. Chachulski, M. Jennings, S. Katti, and D. Katabi, Trading Structure for Randomness in Wireless Opportunistic Routing, Proc. ACM SIGCOMM, pp. 169-180, 2007.

6. E. Rozner, J. Seshadri, Y. Mehta, and L. Qiu, SOAR: Simple Opportunistic Adaptive Routing Protocol for Wireless Mesh Networks, IEEE Trans. Mobile Computing, vol. 8, no. 12, pp. 1622-1635, Dec. 2009.

7. N. Arad and Y. Shavitt, Minimizing Recovery State in Geographic Ad Hoc Routing, IEEE Trans. Mobile Computing, vol. 8, no. 2, pp. 203-217, Feb. 2009.

8. Z. Ye, S. Krishnamurthy, and S. Tripathi, A Framework for Reliable Routing in Mobile Ad Hoc Networks, Proc. IEEE INFOCOM, pp. 270-280, 2003.

9. M.-H. Lu, P. Steenkiste, and T. Chen, Design, Implementation and Evaluation of an Efficient Opportunistic Retransmission Protocol, Proc. ACM MobiCom, pp. 73-84, 2009.

10. F. Wu, T. Chen, S. Zhong, L.E. Li, and Y.R. Yang, Incentive- Compatible Opportunistic Routing for Wireless Networks, Proc. ACM MobiCom, pp. 303-314, 2008.