A survey of Opportunistic Network techniques for message forwarding.

MASTER THESIS TITLE: Survey of Opportunistic Network Schemes for Message Forwarding MASTER DEGREE: Master in Science in Telecommunication Engineering & Management AUTHOR: Sandra Rodríguez Aranguren DIRECTOR: Roc Meseguer Pallarès DATE: November 28th, 2013 Title: Survey of Opportunistic Network Schemes for Message Forwarding Author: Sandra Rodríguez Aranguren Director: Roc Meseguer Pallarès Date: November 28th, 2013 Overview The aim of this Master Thesis is to present the investigation results of the different routing schemes that are used in opportunistic networks, the so-called opportunistic routing schemes. In special the routing scheme with mobile infrastructure DataMULEs is subject of an exhaustive study. Opportunistic routing schemes are from great interest and the subject of several studies, as they offer the possibility to communicate networks that cannot be successfully connected using traditional routing schemes. They allow communications in very sparse networks and also where traditional end- to-end transmissions are not possible. This work begin with the description and characteristics of opportunistic networks and opportunistic routing schemes, it is also presented an extensive description of the classification for these schemes. Furthermore, in this work an important interest is given to the routing schemes that used mobile infrastructures in its communication, such as Message Ferrying and DataMULEs. Finally the main focus is given to two study cases of the DataMULEs routing scheme, they were in detail analyzed and their features and functionality were addressed to summaries the benefits. Título: Survey of Opportunistic Network Schemes for Message Forwarding Autor: Sandra Rodríguez Aranguren Director: Roc Meseguer Pallarès Fecha: 28 de Noviembre del 2013 Resumen El objetivo de esta Tesis de Maestría es ofrecer los resultados de la investigación llevada a cabo sobre los diferentes esquemas de enrutamiento usados en las redes oportunistas, y que son llamadas de igual forma esquemas de enrutamiento oportunista. Así mismo, el esquema de enrutamiento con estructuras móviles “DataMULEs” es de especial interés para este Tesis y será tratado a fondo en el contenido de la misma. Los esquemas de enrutamiento oportunistas son de gran interés y el objetivo de de muchos estudios técnicos, ya que ellos ofrecen la oportunidad de comunicar redes, que no se podrían comunicar usando los esquemas de enrutamiento convencionales. Estos esquemas permiten el enrutamiento de los datos a través de redes dispersas en una gran área geográfica y donde sus enlaces sufren de constantes desconexiones, es decir, donde las transmisiones convencionales, con conexión constante de origen a fin, no se posibles de llevar a cabo. El presente trabajo comienza con la definición de lo que significa redes y esquemas de enrutamiento oportunista así como las características más importantes de ellos, también se presenta una clasificación de los diferentes esquemas de enrutamiento y sus sub-divisiones. Para los esquemas de enrutamiento con estructuras móviles como “Message Ferrying” y “DataMULEs” se dará una descripción más exhaustiva. Finalmente el mayor foco de estudio será para dos casos de estudio de los esquemas de enrutamiento de “DataMULEs”, estos serán objeto de un completo análisis y se presentarán sus características, funcionalidades y beneficios. INDEX INTRODUCTION ................................................................................................ 1 CHAPTER 1. OPPORTUNISTIC NETWORK AND ROUTING ....................... 2 1.1 Opportunistic Network .......................................................................................................... 2 1.1.1 Concept .................................................................................................................. 2 1.1.2 Opportunistic Network Features ............................................................................. 3 1.1.3 Opportunistic Network Architecture ........................................................................ 3 1.2 Routing Background and Overview in Opportunistic Networks ...................................... 4 1.2.1 Routing in MANET and in Opportunity Network ..................................................... 5 1.2.2 Layers and Routing Solutions in Opportunistic Network ........................................ 5 1.3 Opportunistic Routing Approach its Basic and Operations ............................................. 6 1.3.1 Opportunistic Routing Concept............................................................................... 6 1.3.2 General Process Flow in Opportunistic Routing Schemes .................................... 8 1.4 Challenges in Opportunistic Routing Schemes ................................................................. 8 1.5 Objective and Evaluation Metrics for Opportunistic Routing Schemes .......................... 9 CHAPTER 2. OPPORTUNISTIC ROUTING SCHEMES ............................... 11 2.1 Opportunistic Routing Schemes Classification ............................................................... 11 2.1.1 Routing Schemes without Infrastructure .............................................................. 12 2.1.2 Routing Schemes with Infrastructure ................................................................... 13 2.2 Without Infrastructure: Dissemination Based Schemes Classification ........................ 14 2.2.1 MV Scheme (Meetings-Visitings) ......................................................................... 15 2.2.2 Epidemic Scheme ................................................................................................. 16 2.2.3 Network Coding .................................................................................................... 17 2.3 Without Infrastructure: Context Based Schemes Classification .................................... 18 2.3.1 CAR Scheme (Context-Aware Routing) ............................................................... 18 2.3.2 MobySpace Scheme ............................................................................................ 19 2.4 With Infrastructure: Fixed Infrastructure Schemes Classification................................. 20 2.4.1 Infostations Scheme ............................................................................................. 20 2.4.2 SWIM Scheme (Shared Wireless Infostation Model) ........................................... 21 2.5 With Infrastructure: Mobile Infrastructure Schemes Classification .............................. 22 2.5.1 MF Scheme (Message Ferrying) .......................................................................... 22 2.5.2 DataMULEs .......................................................................................................... 24 CHAPTER 3. DATA MULES ROUTING SCHEME ....................................... 26 3.1 Introduction.......................................................................................................................... 26 3.2 Overview and Definition ..................................................................................................... 26 3.3 Comparison to other Schemes .......................................................................................... 27 3.3.1 Mobile Infrastructure Schemes ............................................................................. 27 3.3.2 Sparse Wireless Sensor Network Data Collectors ............................................... 28 3.4 DataMules Three-Tier Architecture ................................................................................... 28 3.5 DataMULEs Scheme Benefits and Limitation ................................................................... 30 3.5.1 Benefits ................................................................................................................. 30 3.5.2 Limitations ............................................................................................................. 31 CHAPTER 4. STUDY CASES AND CONCLUSIONS ................................... 32 4.1 Study Cases ......................................................................................................................... 32 4.1.1 DataMULEs for Energy Efficient Study Case ....................................................... 32 4.1.2 DataMULEs Store Management and Opportunistic Data Collection Study Case 36 4.2 Results Analysis .................................................................................................................. 41 4.2.1 DataMULEs for Energy Efficient Result Analysis ................................................. 41 4.2.2 DataMULEs Store Management and Opportunistic Data Collection Result Analysis ............................................................................................................................. 43 CHAPTER 5. CONCLUSIONS ...................................................................... 47 BIBLIOGRAPHY .............................................................................................. 49 INTRODUCTION 1 INTRODUCTION Routing schemes represent an important issue in network communications, they have the task to transport the data to its destination, to achieve these routing schemes must find and choose the most convenience path that will drive them to the final destination. Routing schemes are mostly separated between traditional and opportunistic routing schemes. In traditional routing schemes the searching and selection of the path is made before the data is sent; in opportunistic routing schemes the searching and selection of a path to destination is made as the data is transmitted. For opportunistic networks, where links between source and destination are very variable and suffers from frequent disruptions, traditional routing schemes are not appropriate; they are not robust enough to support the transmission of data in such unpredictable condition as they assumed that must be end-to-end path to its destination. Opportunistic routing scheme overcome these problems taking advantage of the broadcast features of wireless communications, here the next hop to destination is decided dynamically as the data is transmitted and taking into account the current conditions of network, the broadcast feature allows to transmit the data to multiples nodes in one transmission, thus having more possibilities to find the next best hop close to destination. Thus, opportunistic routing schemes offer many benefits concerning to the data transmission through a challenge network; they increase the robustness of the data transmission, reduce the number of reliable transmissions, create strong links from the combination of weak links and they are able to take advantage of unexpected circumstances that occur in the network in favor of the transmission. For all of these, are suitable for applications that tolerate high error rates and delays. All of these aspects will be addressed in detail in the following chapters, describing the basis and background of the opportunistic routing schemes to follow of a structural classification of these schemes. The rest of the work will be focus in the research of the schemes with mobile infrastructure schemes and in special an intense study of DataMULEs. 2 Survey of Opportunistic Routing Schemes for Message Forwarding Chapter 1. OPPORTUNISTIC NETWORK AND ROUTING In this chapter will be introduced the concepts of opportunistic networks and routing. First will be explained the concept of opportunistic networks and which are their distinct network structure in its architecture, as well some of its main features will be presented. Then will be describing the challenges and solutions in routing suchlike networks, so then the concept and features of an opportunistic routing could be introduced, here will be explained how a basic opportunistic routing scheme works and what are the challenges that such a routing scheme must overcome. Finally some common aims and metrics for opportunistic routing schemes are giving. 1.1 Opportunistic Network 1.1.1 Concept Opportunistic Network is an evolution of the Mobile Ad hoc NETworks (MANETs) [1] and for most of authors Opportunistic Networks are considerate as a sub-class of Delay/Disruption Tolerant Networks (DTNs) with a more flexible environment [2][3]. For simplicity and generalization purpose, throughout this document, we use the term Opportunistic Network for both DTNs and Opportunistic Networks. Figure 1. Mobile Ad-hoc Network Structure Example [4]. Master Thesis 3 Figure 2. Delay/Disruption Tolerant Networks Structure Example [5]. Depending on the capabilities and characteristics of the nodes that form the network an Opportunistic Network can be described as a network where nodes are not connected all the time and are spare in an area without a direct path between them. 1.1.2 Opportunistic Network Features From the articles [6] and [3], the following features can be addressed as the most distinguished of an Opportunistic Network:  Infrastructure-less networks.  Network contacts are intermittent.  Link performance is highly variable or extreme.  Frequently a complete path between source and destination does not exist or is very unstable and break quickly.  Nodes are in constant movement and shut down periodically to save energy, these provoke constant changes in the network’s topology. 1.1.3 Opportunistic Network Architecture Opportunistic Networks have a very dynamically challenging topology, which make harder its process of forwarding the data. This challenging topology is considerate to be separated into several network partitions. This network partitions are the result of the intermittent connectivity features of opportunistic networks where links between its nodes are periodically disconnected; these regions appear every time a node is not available to communicate with others, maybe due to the node moving away of the communication range or the node turning off its power for save energy reason causing. 10 Survey of Opportunistic Routing Schemes for Message Forwarding The routing objective provides a tradeoff between maximizing the delivery ratio and minimizing the overhead ratio. On one hand, the ideal case of delivering the message before its given lifetime with the lowest overhead ratio is to keep this message until the destination is in proximity. While on the other hand, the effective approach to maximize the message delivery ratio is to relay this message at each encounter opportunity taking into account the candidate node selection. Although it is expected that the applications of Opportunistic Networks are inherently tolerant to the long delivery delay, this does not mean they would not benefit from short delivery delay. Master Thesis 11 Chapter 2. OPPORTUNISTIC ROUTING SCHEMES This chapter is entirely focused on the classification of opportunistic routing schemes. Parting from the base that this work will be developed for unicasting schemes in the first part of the chapter will be explained the classification that was chose. In the next section will be explained the upper part of the classification and a description of its several parts is giving. The next sections will contained a basic description of every opportunistic routing scheme of the chosen classification; also it will be explained in general terms how these schemes work. 2.1 Opportunistic Routing Schemes Classification Currently exists many classification for opportunistic routing algorithms depending of the author of the study, a first classification is the one given by authors in [6] where they explain a classification where the existing routing algorithms can be classified in unicasting, multicasting and anycasting issues; nevertheless the aim and focus of this study will be the unicasting schemes, where the message is delivered to its unique destination. For more information about the others classifications refer to [6]. The classification for unicast schemes is made according to the schemes design and characteristic like route design and location deployment. According to [1] a classification for the unicast opportunistic schemes is for those algorithms designed for completely flat ad hoc networks, the so called Schemes without infrastructure and the algorithms in which the ad hoc networks used some kind of infrastructure, these are called schemes with infrastructure. In the followings sections will be explained the different schemes with infrastructure and without infrastructure and their subdivisions. Thus the aim of this work is the study of the schemes with mobile infrastructure; these will be studied with more detail. 12 Survey of Opportunistic Routing Schemes for Message Forwarding Figure 5. Taxonomy of Routing Schemes for Opportunistic networks [1]. 2.1.1 Routing Schemes without Infrastructure These schemes are designed for completely flat ad hoc networks and do not use any kind of infrastructure to forward the message throughout the network. They can be subdivided into dissemination-based and context-based routing schemes [1]. Dissemination-based algorithms are essentially forms of controlled flooding, and differentiate themselves by the policy used to limit flooding. Context-based approaches usually do not adopt flooding schemes, but use knowledge of the context that nodes are operating in to identify the best next hop at each forwarding step [1]. 2.1.1.1 Dissemination Based Some of the most distinguished features for these sub-division schemes presented in [1] are:  Delivers a message to destination by diffusing it all over the network (flooding).  No knowledge of a possible path or appropriate next-hop node.  Well performance in highly mobile networks with frequently contacts opportunities.  Tend to limit message delay.  Consume a lot of resources. Master Thesis 13  High contention and network congestion.  Increase the network capacity by limiting the number of hops of the spreading radius or by limiting the message copies present at the same time.  Network-coding-based-routing outperforms flooding as it is able to deliver the information with fewer messages in the network.  Limits messages’ flooding by exploiting knowledge about direct contact with destination nodes. 2.1.1.2 Context Based Some of the most distinguished features for these sub-division schemes presented in [1] are:  Exploits information about the context in which nodes are operating to identify next hops.  More reduction of message's duplication compare to dissemination.  Tend to increase message’s delay in the delivery process.  The computational cost is higher.  Nodes need to maintain a state to keep track of the utility value. 2.1.2 Routing Schemes with Infrastructure These are schemes that use some kind of infrastructure to deliver the message in an opportunistic form to its destination. A subdivision is made according to the type of infrastructure they rely on; in this case there are fixed infrastructure schemes and mobile infrastructure schemes. Special nodes of a fixed infrastructure are located at specific geographical points, whereas nodes of a mobile infrastructure move around in the network following either predetermined known paths or completely random paths, which will be collaborated in the forwarding of the message [1]. 2.1.2.1 Fixed Infrastructure Some of the most distinguished features for this sub-division schemes presented in [1] are: 14 Survey of Opportunistic Routing Schemes for Message Forwarding  The message is sent only when a base station belonging to the sender node is reachable.  Base stations are generally gateways towards less challenged networks.  Two variations to the protocol are possible: one in which node-to-base- station communications is allowed. Another is in which node-to-base- station and node-to-node communication are allowed.  Node-to-base-station communications experience high delay in delivery message. 2.1.2.2 Mobile Infrastructure Some of the most distinguished features for this sub-division schemes presented in [1] are:  Nodes of the infrastructure are mobile data collectors.  The routes that the nodes follow can be predetermined or arbitrary.  The nodes gather the messages from the nodes that pass by.  In exclusive node-to-carrier communications, the special carrier-node is the only entities allow of delivering the messages.  In exclusive node-to-carrier communications the carrier-node help to increase connectivity in sparse networks and also isolated node can be reached.  In communications where is allow to nodes to communicate to carriers and ordinary nodes the delivery of the messages is accomplish by both. 2.2 Without Infrastructure: Dissemination Based Schemes Classification In the following section will be addressed a detail description and procedure of some of the schemes belonging to this classification. Master Thesis 15 2.2.1 MV Scheme (Meetings-Visitings) The following information is an overview of the features and procedures that defines the MV routing scheme; this information was taken from the work paper [10]. 2.2.1.1 Features:  Forwarding of messages from a mobile source to a stationary destination.  Exploits movement structure by learning the peer’s motion patterns.  These periodic patterns in peer’s movements (structures) are used to estimate the probability of delivery for a specific message and peer.  The information of participants meetings and their visits to locations is used for routing and buffer allocation.  Making informed routing decisions by estimating the probability of a particular message being delivered by a given peer.  Uses autonomous agents to compensate for a mismatch between available capacity and demand, that is, they are able to adapt the bandwidth and latency requirements of a network with the movement of network participants and traffic flows.  Improves the performance of disruption-tolerant networks. 2.2.1.2 How it works: When a peer A meets another peer B, they perform a message exchange through a number of steps. First, A gives to B a list of the messages A carries as well as their destinations. Each message is also annotated by A with A’ likelihood of delivery according to the formula we derive below. A receives the same list from B and calculates the likelihood of delivering B’s messages. A now sorts the unioned lists by likelihood of delivery, removes its own messages, and also deletes all messages that B has a higher likelihood of delivering. A then selects the top n messages remaining, and requests from B all the messages that are not already stored. Note that MV calculates an estimation of delivery likelihood assuming an infinite buffer at each peer and limits the number of hops that are required in practice. 16 Survey of Opportunistic Routing Schemes for Message Forwarding 2.2.2 Epidemic Scheme The following information is an overview of the features and procedures that defines the Epidemic routing scheme; this information was taken from the work papers [11] [12]. 2.2.2.1 Features:  Distribute application messages to hosts called carries, within connected portions of a network.  Node mobility is used to put in contact carriers with another connected portion of the network.  Deliver messages with a high probability of reaching their destinations.  It maximizes message delivery rate and minimizes message delivery latency by placing an upper bound on message hop count and per-node buffer space.  It poses high aggregate resource consumption.  Delivery of messages to arbitrary destinations with minimal assumptions regarding the underlying topology and connectivity of the underlying network.  Relies upon transitive distribution of messages through ad hoc networks.  Use a hash table indexes a list of messages that are originated and buffering by the host. 2.2.2.2 How it works: A source, S, wishes to send a message to a destination, D, but no connected path is available from S to D. S transmits its messages to its two neighbors, C1 and C2, within direct communication range. At some later time, C2 comes into direct communication range with another host, C3, and transmits the message to it. C3 is in direct range of D and finally sends the messages to its destination. The hash table used indexes the list of messages, keyed by unique identifier associated with each message, also each host stores a bit vector, called the summary vector that indicates which entries in their local hash table are set. Master Thesis 17 2.2.3 Network Coding The following information is an overview of the features and procedures that defines the Network Coding routing scheme; this information was taken from the work paper [13]. 2.2.3.1 Features:  Significantly reduces the overhead of probabilistic routing algorithms.  Nodes code the information over the contents of several packets they receive.  Nodes send packets with linear combinations of previously received information.  It has a parameter that controls with which probability the reception of an innovative packet causes the node to send a packet.  The memory available at a node constrains the number of information units a node can code over.  Network coding is much more robust against packet loss than others algorithms.  Allows the dissemination of information with a high probability at a lower overhead.  It is affected by the generation size. 2.2.3.2 How it works: An intermediate node sends a linear combination ∑i gixi of the packets xi it has received or wants to send, where all coefficients gi and the data xi are interpreted as numbers in a finite field. When a node receives m combinations of n packets, it can decode them provided that the set of combinations has a rank n, for m=n this occurs with a probability close to 1 if the coefficients gi are chosen randomly and independently at every node. 18 Survey of Opportunistic Routing Schemes for Message Forwarding 2.3 Without Infrastructure: Context Based Schemes Classification In the following section will be addressed a detail description and procedure of some of the schemes belonging to this classification. 2.3.1 CAR Scheme (Context-Aware Routing) The following information is an overview of the features and procedures that defines the CAR routing scheme; this information was taken from the work paper [14]. 2.3.1.1 Features:  It is based on intelligent placement of messages.  Achieve efficient and timely delivery of message by the evaluation and prediction of context information.  Hosts are not aware of its or others hosts absolute geographical location, they only have logical connectivity information about its position.  CAR uses predicted future values for the context.  It only creates a single copy of each message.  High level of scalability thanks to the almost constant value of the overhead in terms of the number of messages exchanged regardless of buffer size. 2.3.1.2 Hoe it works: Each host calculates its delivery probabilities based on the prediction of future values and its composition. The calculated delivery probabilities are periodically sent to the other hosts in the connected cloud for updating. Each host maintains a logical forwarding table of tuples describing the next logical hop and its delivery probability for all known destinations. The updates are sent only when the evolution of the mobile scenario follows a certain trend. If a host does not store any information about the message recipient, it sends the message to the host in the cloud that has the highest mobility. If the carrier, while moving, meets a host with a higher delivery probability, the message is transferred to the host with higher delivery probability. Master Thesis 19 2.3.2 MobySpace Scheme The following information is an overview of the features and procedures that defines the MobySpace routing scheme; this information was taken from the work papers [15] [16]. 2.3.2.1 Features:  Uses a high-dimensional Euclidean space (MobySpace) constructed upon node’s mobility patterns.  The nodes are represented by the coordinates that correspond to their probability of being found in each possible location.  The messages are routed in a virtual space defined by the basis of mobility patterns.  In the virtual space there is no notion of neighbor.  Nodes are directly connected in a dynamically way to other nodes that are close or very far from each other.  Nodes opportunistically take advantage of connections that promise to advance bundles toward the destination.  The routing decision rely on the notion that a node is a good candidate for taking custody of a bundle if it has a mobility pattern similar to that of the bundle’s destination.  The efficiency of the virtual space tool may be limited if nodes change too rapidly their habits.  Reduce bundle delay and through lower communication costs. 2.3.2.2 How it works: For each of the nodes there is a well defined probability of finding that node at each of the N locations, which is based upon historic information regarding contacts that the node has already had. This set of probabilities is a node’s mobility pattern, and is described by a MobyPoint, in an N dimensional MobySpace (Euclidean virtual space). The MobyPoint is the coordinates of the mobility pattern of a node. The bundles in the MobySpace are routed by sending them to nodes having mobility patterns that are successively closer to the mobility pattern of the destination. 26 Survey of Opportunistic Routing Schemes for Message Forwarding Chapter 3. Data MULEs Routing Scheme The aim of this chapter is to give a more detailed analysis and study of the opportunistic routing scheme DataMULEs, as it is the chosen schemes to analyze on this work. Here will be explained all the important aspects of this scheme, starting with a definition and comparison to other related schemes; also the relevant features of its architecture will be described. The chapter ends with an overview of the benefits and limitations that this schemes offers. 3.1 Introduction As explained before, the “Routing Based on Mobile Infrastructure” approach is based in an infrastructure where its nodes are mobile data collector. As noted in [1], these mobiles nodes are described as carriers, supports, forwarders, ferries, mules etc. They are distributed in the network area and move with or without a predetermined path, and on this movements they collect, store and forward messages to its destination or next hop. In general and basic terms this is the functionality of the DataMULEs routing scheme. DataMULEs are suitable for collecting and transmitting data in a wireless sensor network (WSN). The WSN is composed by a large number of sensors that are sparse in a large area. These kind of networks introduce problems to the communicate between each other sensors, making the transmission of the data to a specific destination which is usually a central controller (base station or access point) a challenge for the system; since in a sparse network the sensors are located far away from each other the communication process required a high level of energy consumption, this reduce the lifetime of sensors and in this way the lifetime of the network. 3.2 Overview and Definition The routing scheme DataMULEs help to overcome the communication problems, helping in the increase of the network’s connectivity and guaranteeing that isolated nodes can be reached [1]. It uses mobiles entities usually nodes called Mule (Mobile Ubiquitous LAN Extensions), as they “carry” data from sensors to access point [20], as forwarding agents. The forwarding of the messages is carried out by opportunistic contacts between the mules through the wireless interface; they also display random pattern movements that are not predictable. Master Thesis 27 DataMULEs can be implemented in a large range of application as environmental monitoring, traffic monitoring, animal migrations and others application where the WSNs are isolated and unattended. Depending on the application the mobiles mules can be chosen as animals, humans, cars, ships, etc. This scheme introduced a three-tier architecture that connects spare sensors within a WNS; for this a third new layer is added just between to the two existing layers of sensors and access points, in this new layer is where the mobile mules are placed. DataMULEs’ architecture collect the sensor data in the WSN using the presence of these mobile entities “MULEs”, the mule’s task is to pick up the data from sensors when they are in close range to it, then buffer it, and finally drop off the data to its designated wired access point [21]. The three-tier architecture consists of a top tier with access points set at convenient places, also a middle tier consists of the mobile mules that are mobile nodes with unknown movements, and finally a bottom tier consists of sensors that are randomly distributed across a region [6]. 3.3 Comparison to other Schemes 3.3.1 Mobile Infrastructure Schemes As it is explained in Chapter 2, we mentioned DataMULEs and Message Ferries with its two versions (NIMF and FIMF) as mobile infrastructure approaches which aim is, as it name indicates, to use its moving structures to collect the data and forward it to its destination. In the survey article [2] and with the information obtained from [19] and [21] a comparison among unicast schemes with mobile infrastructure assistance is giving, from this comparison can be obtained Table 2., in which is possible to compare DataMULEs features with the features of the two other versions of Message Ferries scheme: NIMF (Node-Initiated MF) and FIMF (Ferry-Initiate MF). Table 2. Comparison among unicast schemes with mobile infrastructure assistance. [2] Based on the information founded in the mentioned surveys, the table above shows some features for these schemes; for instance they use as infrastructure the same deterministic movement, also their buffer space is limited for all the three schemes. The only difference found for these schemes is the way they Routing Scheme Infrastructure Movement Assistance Behavior Controlling Buffer Space DataMULEs Deterministic Movement None Limited NIMF Deterministic Movement None Limited FIMF Deterministic Movement Controlling the movement based on request Limited 28 Survey of Opportunistic Routing Schemes for Message Forwarding control their assistance behavior; in DataMULEs and NIMF any control of the movement of their assistances (mules and ferries) is used as they (mules and ferries) just move randomly through the network until they find an opportunity to transmit. Unlike to DataMULEs and NIMF the FIMF approach control the movement of its ferries, as the ferries must adjust their trajectory as they received service request as explained in chapter 2. 3.3.2 Sparse Wireless Sensor Network Data Collectors Besides the DataMULEs there are others schemes to collect data that uses the approach of a sparse wireless sensor network, these are the Base Station approach scheme and Ad-hoc Network approach scheme. As it is mentioned in [21] the Base Station approach consists of a few numbers base station scatter through the whole network area, here every sensors have the possibility to directly communicate to the base station, which will be the closest to each sensor; for the Ad-hoc Netowrk approach the number of sensors are big enough so it is possible to create an ad hoc network with them, these sensors transfer the data through the ad hoc network by multi-hop routing to the wired base station. As it can be appreciate in the next Table 3. DataMULEs gets an overall better result than its similar approaches of the Sparse Wireless Sensor Networks Schemes. In terms of efficiency DataMULEs performs the best for the best price, and even with high latency. Its perform overcome that from the other mentioned approaches as in DataMULEs the sensor power and infrastructure cost are low, which are important features to considerate in order to implement any application, and as long as the application to implement is not a real time application, where the latency can make the communication not possible. Table 3. Performance of Different Approaches for Data Collection in Sparse Wireless Sensor Network [21]. 3.4 DataMules Three-Tier Architecture As mentioned before the DataMULEs architecture adds a new layer to the conventional sensor and access point layers of a WSN, this architecture is called a three-tire architecture. It provides wide-area connectivity for a sparse sensor network by exploiting the use of mobile entities (mules) [21]. These mules can be humans, animals, vehicles, ships or any other moving agent. Performance Metrics Approaches Latency Sensor Power Data Success Rate Infrastructure Cost DataMULEs High Low Medium Limited Base Stations Low High High Limited Ad-hoc Network Medium Medium-low Medium Limited Master Thesis 29 Figure#. DataMULEs three-tier architecture [20]. As it is explained in [20] and [21] the DataMULEs three-tier architecture is comprised by three tiers or layers: • A Upper Tier: In this level the layer consists of a set of wired access points or data repositories, which are set in convenient locations in the network area. They are equipped with Internet/Network’s connectivity; enhance power, storage and processing capabilities. These devices are used to offload the data collected and stored by the mules, they communicate with a central data warehouse that enables them to synchronize the data that they collect, detect duplicates, as well as return acknowledgment to mules (ack maybe necessary to ensure reliability of data for certain applications). • A Middle Tier: This intermediate layer consists of mobile agents, named “MULEs”, which move around an area covered by sensors to gather their data and transfer it to the access points. A mule has the responsibility to discover sensors and access points and to transfer the data between them. Thanks to the mobile mule nodes this layer provides the system with scalability and flexibility for a relatively low cost. Its most important feature is that in comparison to the sensors mules are equipped with a larger storage capacity, renewable power, and have the ability to communicate with sensors and networked access points, as they are in proximity to each other. Mules are assumed to be unpredictable mobile entities whose mobility patterns cannot be calculate or predict in advance. However as a result of their motion, they collect and store data from the sensors, as well as deliver acks back to the sensor 30 Survey of Opportunistic Routing Schemes for Message Forwarding nodes. In addition, in some cases mules can communicate with each other to improve system performance. • A Bottom Tier: This layer is occupied by sensor nodes, which are distributed randomly across the network area. They are stationary sensors with not mobility features and periodically perform data sampling from the surrounding environment, which will depend on the application purpose. Sensors, provides data, communicate via a short-range radio, and have limited power and memory; that is why they cannot perform a lot of work, in order to save energy. The main advantage of this architecture is the potential of large power savings by sensors because communication now takes place over a short range [20], but they suffer from a high latency. 3.5 DataMULEs Scheme Benefits and Limitation As presented in the work article [20], an overview of the benefits and limitation of the DataMULEs scheme. 3.5.1 Benefits  Energy Efficient: Substantial energy is saved because sensors communicate over a short range. Moreover, there are no hotspots in the network, as sensors do not forward data for other sensors.  Spatial Reuse: The three-tier architecture of DataMULEs exploits spatial reuse of bandwidth by using short-range communication without losing long term connectivity and avoids radio communication complexities such as collisions.  No routing overhead: In contrast to ad-hoc networks, this architecture does not have any routing scheme overhead for sensors.  Robustness: Performance degrades gracefully as mules fail. Any single mule failure does not lead to a disconnected network. The primary effect of a mule failure on the overall system is a slight increase in latency as there are now fewer mules to pick up data. In contrast, in an ad-hoc network failure of few critical nodes might lead to a disconnected network.  Scalable: The DataMULEs three-tier architecture is easily scalable as deployment of new sensors or mules requires no network reconfiguration.  Simplicity: The data routing aspect of the mule architecture is very simple and extremely lightweight for the sensors. This is important because Master Thesis 31 sensors are the bottleneck of the system. This architecture does not require any synchronization or location information; an assumption made by many approaches. This help to reduce the costs of the implementation. 3.5.2 Limitations  Latency: The DataMULEs architecture has high latency and this limits its applicability to real time applications (although this can be mitigated by collapsing the mule and accesspoint tiers).  Best-effort delivery: Data delivery in the basic architecture is best effort; delivery is not guaranteed. The system requires sufficient mobility. For example, mules may not arrive at a sensor or after picking the data may not reach near an access-point to deliver it. Also, data may be lost because of radio-communication errors or mules crashing. To improve data delivery, higher-level protocols need to be incorporated in the mule architecture. 32 Survey of Opportunistic Routing Schemes for Message Forwarding Chapter 4. Study Cases and Conclusions This chapter will be focused in the analysis of some works done about the DataMULEs scheme. First will be described how the chosen studies were done, and which kind of consideration were taken into account. After this, and explanation and analysis of the result is giving. Finally some conclusions and new ideas for future works are presented. 4.1 Study Cases 4.1.1 DataMULEs for Energy Efficient Study Case This study case and subsection is entirely based on the research made in [20]. This study focuses in to find a solution to the problem of energy efficient for data collection in a sensor network. The approach used in this study exploit the nature of the DataMules architecture in term of the mobile nodes present in the sensor field as forwarding agents. In this work the authors introduced an analytical model that they used to understand the key performance metrics such as data transfer, latency to the destination and power. The parameters used in this work are: sensor buffer size, data generation rate, radio characteristics, and mobility patterns of mobile nodes. 4.1.1.1 Problem description: For the authors the energy problem in this architecture is due to three things. One is that the energy needed to transmit data over one hop is quite a lot due to the distance between sensors, which can be large in some cases. Another reason is that in this architecture network sensors have to not only send their data, but also forward data for other reasons. The third reason for the energy problem given by the author is the routing hotspots near the access point, where sensors that are near to the access point have to forward many more packets and drain their battery much more quickly. All of these cause a huge demand in the energy consumption from the sensors, which could limit the network performance and design cost. Master Thesis 33 4.1.1.2 Model Contributions This study provides a contribution for the understanding of DataMULEs scheme in terms of the modeling and comparison with ad-hoc networks. Here some its most important contribution:  An analytical model is presented; it is based upon queueing theory that helps to understand the relationship between performance metrics and system parameters. The authors characterized the model’s performance along with three dimensions: data transfer rate, latency, and energy requirements at the sensors. This model incorporates system parameters such as sensor data generation rate, buffer size, sensor duty cycle, radio characteristics such as range and capacity, MULE velocity, MULE mobility model, etc.  Detailed performance simulations to validate the analytical model studied and to gain finer understanding, with comparisons between the results.  An analytical discussion of the benefits of the MULE architecture over adhoc networks both qualitatively and quantitatively using simulation. The model proves some advantage in the implementation of these networks as in comparison to the ad-hoc network, this is in term of operational lifetime and other related features.  An efficient discovery process of sensors is addressed by using a low duty cycle at the sensor and this is incorporated in the analysis. A novel discovery mechanism is discussed that permits significantly lower duty cycles while at the same time has very little impact on performance. 4.1.1.3 Model Characteristics The authors address the following characteristics for their study case:  The model application context is focused on sensor networks unlike previous work to this, where the focus was towards mobile ad-hoc networks.  This model tries to maximize sensor network lifetime by reducing the communication energy required at the sensors.  The architecture used introduces MULE explicitly and encompasses Zebranet (for more exact information on ZebraNet project [22]) like scenarios, and focus on analytical modeling, energy efficient discovery and comparison with ad-hoc networks, which previously to this work were unaddressed. 34 Survey of Opportunistic Routing Schemes for Message Forwarding  The DataMULEs architecture is as was presented in section 3.4 with the typical three tiers architecture: lower tier (sensors), middle tier (MULEs), upper tier (Access points).  In this model MULEs do not communicate with each other.  In this model the Access points are the eventual destination of sensor data. They are used to offload the data collected by and stored in the MULEs.  Depending on the scenario, tiers in the model’s architecture can be collapsed onto one device, increasing the applicability of our architecture that is sensors can be mobile so the sensor and the MULE tier could be mapped to the same device, also if MULE(s) have Internet connectivity they can act as an access-point, combining the MULE and access-point tiers. 4.1.1.4 Model Description The primary component of the model is a queue of generated data, which has not been delivered at each sensor. In queuing theory terminology, generation of new data at a sensor corresponds to an arrival at the sensor’s queue. The buffer size of the sensor defines the capacity of the queue. If the buffer is full then any new data is dropped. The queue is served whenever a MULE is in a sensor’s range. The arrival of a MULE in a sensor’s range is considered as a discrete event. This event causes transfer of data from the sensor’s queue to the MULE. The sensor then waits for the next MULE arrival event to transfer the data. Thus, the time between two MULE arrivals dictates when the queue is served. The amount of data that can be transferred on a MULE arrival event is a random variable and depends on factors such as, the time the MULE is in the communication range of sensor. However, in the model this is taken as a fixed quantity. The interaction between the MULEs and the access-points can be modeled on exactly the same principles. The authors’ model only focuses on interaction between sensors and MULE, as they consider this to be the primary bottleneck of the system. The MULE discovery process for this model is as follow: a sensor needs to discover a nearby MULE to be able to offload its data. In this architecture the prime responsibility of discovery is placed on the MULE, as the objective is to minimize the load on sensors. A MULE continuously sends out a discovery message to detect a nearby sensor. This requires a sensor to listen for discovery messages. Since listening consumes as much power as receiving, as it was proved in [23], the duty cycle at the sensor need to be reduce, which Master Thesis 35 leads to a tradeoff between minimizing the listen energy and maximizing the probability of rendezvous with a passing MULE. The model implemented proves to offer a good impact of sensor duty cycle, by increasing the contact time the sensors can operate at low cycles without substantially affecting the performance. 4.1.1.5 Performance metrics and parameter Metrics used in this study case:  Data success ratio (DSR): This measures the effectiveness of data delivery.  Latency: This is the average time taken by data to reach access-points from the time of its generation.  Communication energy: it is considered both, the average energy consumed per sensor as well as the worst-case consumption, which dictates the network lifetime. Parameters used in this study case:  Sensor related: The data generation rate (λ) defines the average amount of data that a sensor is generating. This directly affects the buffer requirements at the sensor.  MULEs related: The primary aspect is to determine when MULEs come into the communication range of a sensor. The MULE arrival within a sensor’s range is modeled as a discrete event. The key parameter is the distribution of time between two MULE arrivals at a sensor. Our model abstracts out these complexities by assuming the knowledge of interarrival distribution. MULEs buffer size is another parameter, but for the purposes of this paper we assume that MULEs have sufficiently large buffers.  Access point related: The important aspect here is the distribution and the number of access-points. This affects how frequently a MULE visits an access-point to deliver data.  Radio related: The radio parameters affect the amount of data that can be transferred as a MULE passes by a sensor. We use a radial model for the radio, i.e. sensors and MULEs can communicate if they are within a distance r. Our approach is to identify a few basic parameters that are sufficient to characterize the performance metrics. These basic parameters are: (1) sensor data generation, (2) sensor buffer size (SB), (3) amount of data transferred 42 Survey of Opportunistic Routing Schemes for Message Forwarding large, less data is dropped. In general, one can increase DSR by either increasing μ or SB. To determinate the effect of this two metrics on latency, it was assumed that K was sufficiently larger than the SB; with this assumption the results showed that the queuing delay is simply the residual life of the MULE arrival process, which decreases as μ, is increased, also SB has no impact on latency. 4.2.1.2 Data Transferred in One Interaction K Metric In this case as the authors chose for simulations a large SB of 1MB the DSR is always close to one. For the average sensor buffer occupancy and latency the simulations results showed that when K is small the average sensor buffer occupancy and latency are large. As it is explained in (30) this is because a sensor cannot transfer all the data in the queue to a MULE during a single contact, which made the average buffer occupancy to increase, as well as the latency also increased because a data unit has to wait for multiple MULEs to arrive before it can be served. In the other hand when K is large, both average sensor buffer occupancy and latency decrease sharply, this is just until certain limit of K, where it further increase will not have effects in the performance of average sensor buffer occupancy and latency. This is because K only needs to be large enough so as to absorb the occasional burst in the sensor buffer. The next table showed an overview of the impacts in performance due to the increase of the metrics: μ, SB and K. Performance Metrics Parameter Buffer Occupancy DSR Latency μ decrease increase decrease SB no effects increase no effects K decrease increase decrease λ increase decrease increase Table 3. Effect of metrics increase on performance [20]. 4.2.1.3 Mobility Models This study considered four mobility models: (1) Random waypoint (2) Random Walk (new direction is chosen on reaching a street intersection) (3) Deterministic (MULEs arrive at fixed interval) (4) Poisson arrival. The results Master Thesis 43 showed that for all mobility models as μ increases, the DSR increases and the latency decreases. The performance is best when the MULE arrival is deterministic and worst under the manhattan model. The performance of random-waypoint model closely matches that of poisson model. 4.2.1.4 DataMULEs vs Ad-hoc network Varying the sensor density in the network and examining its impact on the metrics average energy ratio and hotspot ratio the authors proved the benefits of using mules’ schemes when compared to the ad-hoc network. The average energy ratio was defined as the average energy consumed at a sensor in the ad-hoc network to the energy consumed in the MULE architecture. As well the hotspot ratio was defined as the ratio of hotspot usage in ad-hoc network to the hotspot usage in the MULE architecture, the hotspot usage is the maximum energy consumed by any sensor. They proved that when the sensor density is low, the MULE architecture has less average energy consumption; this is because with few sensors the average distance between two sensors is large and the communication energy increases; this changes as the sensor density increases and saturate with the average energy ratio. And even the performance worse as sensor density get higher, mules’ architecture is more efficient as traditional ad-hoc network, due to mule’s avoidance to multiple hops. The results obtained in hotspot ratio experiments are similar as the previous on average energy ratio; they indicated that MULE architecture experienced a much longer life-time than ad-hoc networks. 4.2.2 DataMULEs Store Management and Opportunistic Data Collection Result Analysis In this study authors focus their results on the performances of the two strategies DSM and ODE applied to the network and under certain parameters. To analyze the DSM strategy, the authors’ examined the performance result of a WSN in terms of its priority distribution after the DSM is applied. They also examined the performance of DSM in two different topologies, mesh structure and tree structure, thus to understand the influence of the topology in the data collection. In the case of the ODE strategy, the authors examined the performance varying three parameters and their impact on three different metrics; and thus obtain some notions on how ODE has an impact on the information quality and how they are improved by this strategy. 44 Survey of Opportunistic Routing Schemes for Message Forwarding 4.2.2.1 DSM Performance Results Using two different topologies, mesh structure and tree structure, several experiments were executed to prove the benefits of the DSM strategy. Authors varied the numbers of nodes in BA and examined the effects on the average priority of packets at nodes in BA. As explain before (section 4.1.2.5) BA is the buffer area. The results showed that although the hop distance from each node to the sink is same in the shortest-path spanning tree of the mesh and the mesh itself, using a mesh structure has potential to collect higher-priority packets than using a tree structure, which can be explained due to mesh feature that allows much more directions of data exchanges, which will keep the higher-priority packets in BA. In another experiment they varied the mule’s visiting period and the contact duration. With this, they proved that a longer visiting period means that more important packets may be generated/collected during two consecutive visits. Also it was proved that a longer contact duration means that less important packets also have a chance to be collected. They also examined the effect on the performance as the BA’s size (hops to sink) changes, the results showed that the top 1/3 area in the network are mostly occupied by high-priority packets as BA is defined as five hops or more from the sink. As the BA is getting larger the number of packets exchanges (transmission overhead) also increase with a slightly decrease at the beginning. This is because packets with lower priorities have to travel longer to reach the BA when the BA is relatively smaller (3–4 hops). As the BA becomes larger (more than five hops), the cost of packet exchanges inside the BA is more dominant as before, and the transmission overhead is increasing again. Another factor as BA’s size change is the average number of dropped packets, decreases as BA becomes larger, and this is because a larger size of BA can keep more packets and avoid dropping packets when they arrives BA. To study the effects of network density has on the performance results, the number of sensor nodes in the field was varied. The results showed that increasing the packet arrival rate does not increase the overall transmission overhead proportionally; this is because once the BA has collected sufficiently important packets, the competition cost within BA will drop rapidly. It was also proved that a denser network will cause a higher cost of packet exchanges because sensor nodes have more neighbors to facilitate data exchanges for the new packet. Finally, the DSM convergence time (minimal time for all packets in BA to be in order) is studied, for this different data arrival rates were considered. Here they varied the number of nodes and the size of BA; results showed that a dense network incur a longer convergence time because more number of packet exchanges are performed, besides the convergence time is not proportional to the data arrival rate, because packet exchanges in the network at a higher data arrival rate will be triggered frequently, also the convergence time slightly Master Thesis 45 decreases first and then increases again as the BA’s size increases. The convergence time slightly decreases first and then increases again as the BA’s size increases. This is because in a relative small size of BA (from 3 to 7 hops) lower-priority packets have to move by more hops to compete against the higher-priority packets in BA. When the network has a relative large size of BA (from 8 to 13 hops), much more packet exchanges will incur in BA so the convergence time becomes longer. In general, the gaps of convergence time between different data arrival rates shrink as BA’s size increases, because a larger BA provides more storage spaces to allow more concurrent packet exchanges. 4.2.2.2 ODE Performance Results The ODE strategy is analyzed in terms of varying some network parameters and checking their impact in some metrics chosen by the authors. The network parameters are: contact duration between mule-to-mule and between mule-to- BS, the meeting period with the BS, and the aging period of packets. The metrics chosen to examined the ODE’s performance are: (1) packet delivery ratio which is the ratio of the total number of packets collected by the BS to the total number of packets collected by mules, (2) utility delivery ratio which is the ratio of the total utility of packets collected by the BS to the total utility of packets collected by mules, and (3) the total utility of packets collected by the BS. For the contact duration variation the authors noticed the following results. As the contact duration increased the ODE packet delivery ratio also increase and is better as it is compared to the other scheme Greedy; the different between the two schemes are not so big in the beginning but as the contact duration increases the different is more notable. Besides, they examined the utility delivery ratio and noticed that the results from ODE in contrast to the ones from Greedy, presented younger packets collected and have fewer number of copies. The other parameter analyzed when varying the contact duration was the total utility of packets collected by the BS here again ODE showed better results as Greedy, as the contact duration increase ODE improved much more amount of information quality as the Greedy. The other aspect examined in this study was the impact on the performance of the meeting period between the mules and the BS. Results showed that as the meeting period increase the packet delivery ratio also increase, and in comparison to Greedy the ODE results presented at the beginning were slightly better but as the meeting period increase both ODE and Greedy presented almost exactly results. Regarding to the analysis of the utility delivery ratio it was proved that the utility delivery ratio decreased as the meeting period increased; furthermore it was proved that with a larger meeting period mules have fewer opportunities to meet BS, and besides it, ODE as opposite to Greedy was able to collect younger packets and with fewer number of copies, and ODE’s performance was better too even with a very low frequency of 46 Survey of Opportunistic Routing Schemes for Message Forwarding meeting. The results for the total utility of packets collected by BS showed also that as the meeting period increase the total utility of packets decease, and also as this happened ODE obtained always better as the Greedy. As for the analyzed varying the aging period of packets it was proved; first, the packet delivery ratio was more or less constant as the aging period increase, and both ODE and Greedy get similar results with ODE having a little better performance, which is due that ODE avoided copying too many higher-priority packets. The metric utility delivery ratio slightly increases as the aging period increase with ODE performing better than Greedy. Finally it was shown that as aging period increase the total utility of packets collected also increase, and in greater proportion for ODE as it is compared to Greedy. Master Thesis 47 Chapter 5. Conclusions This work has provided an intense and up to date overview of the opportunistic routing schemes, which includes it background and definition, an extensive description of the classification of these schemes, where each schemes is explained from the perspective of its features and functionality. Also comparison with other type schemes is given. It can be summarized that under challenge wireless networks with intermittent contacts and where the sate of network is constantly changing and an end-to- end path to destination may never exist, opportunistic routing schemes offer a significant improve in performance. These schemes use the broadcast techniques of wireless communication to send data to several possible next hops in just one transmission and taking into account the current condition of the network situation, all of these help to avoid unnecessary retransmission and create robustness in the communication against disconnections. This also produces some drawbacks to these schemes as additional delay in messages delivery and the error rate also increase, therefore these schemes are to be applied in not real time application, which are delay-tolerant in nature and these drawbacks do not cause major trouble to the communication. The classification used in this work divide the routing schemes according to the strategies they use for their transmissions, that is, the main classification is between the routing schemes that use some kind of infrastructures assistance in their transmission process and the routing schemes that do not use them. With all routing schemes described and their procedures explained it was noticed that schemes with mobile architecture as Message Ferrying and DataMULE present the more interesting features and opportunities, as they offer the possibility of creating opportunistic communications, this is because their approach is concerned on the deployment of their elements in the network that allows the creation of new and opportunistic route inside the network, this approach and the use of mobile agents to carry the data through the network to its destination improve the encounters opportunities and thus the capacity and connectivity. For this thesis, the DataMULE scheme was chosen as the subject of a more detail study. DataMULE uses randomly moving entities called mules to opportunistically collect and transmit data through the network, this approach turn to overcome the main problems of wireless sensor networks sparse in big areas. With its particular three-tier architecture it effectively uses data mules to enable communications between the other two tiers of the architecture. The implementation of this scheme give the advantage of low energy consumption and easy deploy, the big problem that affects this scheme is the high latency levels, for this reason DataMULEs are considerate to be suitable for delaytolerant application. In relation to the two DataMULE study cases presented in this work; it can be concluded that the study case related to energy efficient proved that using the 48 Survey of Opportunistic Routing Schemes for Message Forwarding present of mobile mules as forwarding agents reduce the demand of energy in sensors and thus increase the lifetime of the network, despite this advantage this DataMULE architecture is only suitable for non real time applications which have mobility, being in this case one of the most effective scheme to take into account. The store management and opportunistic data collection study case concluded that the application of the two proposed strategies DSM and ODE improve the results of the network communication; their results showed that DSM is able to collect optimal data priorities and ODE is able to collect fresher and fewer duplicate packets; therefore DSM and ODE could efficiently work together to collect important data through isolated WSN networks; this strategies could be used in application for outfields and back countries scenarios. This Master Thesis provided a broad overview of the actual state of the opportunistic routing schemes and in special an intense research of the DataMULE scheme, addressing their/its features, advantage and disadvantage. The aim of this work is to offer help and a study material to the people interested in the study and research of such schemes. Master Thesis 49 Bibliography [1] L. Pelusi, A. Passarella, and M. Conti, “Opportunistic Networking: Data Forwarding in Disconnected Mobile Ad Hoc Networks,” IEEE Commun. Mag. vol. 44, N°. 11, pp. 134 –141, 2006. [2] Y. Cao and Z. Sun, “Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges,” IEEE Commun. Mag., 2012. [3] C.M. Huang, K. Lan, and C.H. Tsai, “A Survey of Opportunistic Networks,” IEEE Computer Society, 2008. [4] “(Research Themes 2007) Ad Hoc Networks,“ Hitachi R&D Research Site, http://www.hitachi.com/rd/portal/research/yrl/07/soc_02.html, last reviewed: November 11th 2013. [5] “DTN Network Model Evolution,” Protogenist Blog, http://protogenist.wordpress.com/2012/07/18/dtn-network-model-evolution/, last reviewed: November 12th 2013. [6] Z. Zhang, “Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges,” IEEE Communication Surveys, vol. 8 N° 8, 1st Quarter 2006. [7] Z. Zhong and S. Nelakuditi, “On the Efficacy of Opportunistic Routing,” In Proc. of IEEE SECON, Jun. 2007. [8] A. Triviño-Cabrera and S. Cañadas-Hurtado, “Survey on Opportunistic Routing in Multihop Wireless Networks,” International Journal of Communication Networks and Information Security. vol. 3, N°. 2, August 2011. [9] L. Liu and Z. Chen, “Data forwarding in Opportunistic Networks,” Information Technology Journal 9 (2), 2010. [10] B. Burns, O. Brock and B. N. Levine, “Mv Routing and Capacity Building in Disruption Tolerant Networks,” In Proceedings of IEEE INFOCOM, vol. 1, pp. 398–408, 2005. [11] A. Vahdat and D. Becker, “Epidemic Routing for Partially-Connected Ad Hoc Networks”. Technical Report CS-2000-06, Duke University, July 2000. [12] L. Song and D. F. Kotz, “Evaluating Opportunistic Routing Protocols with Large Realistic Contact Traces,” Technical Report, Institute for Security Technology Studies (ISTS), Dartmouth College, September 2007. [13] J. Widmer and J.-Y. Le Boudec, “Network Coding for Efficient Communication in Extreme Networks,” Proc. ACM SIGCOMM 2005 Wksp. Delay Tolerant Networks, Philadelphia, PA, Aug. 22–26, 2005. 50 Survey of Opportunistic Routing Schemes for Message Forwarding [14] M. Musolesi, S. Hailes, and C. Mascolo, “Adaptive Routing for Intermittently Connected Mobile Ad Hoc Networks,” Proc. 6th IEEE Int’l. Symp. World of Wireless, Mobile and Multimedia Networks (WoWMoM 2005), Taormina-Giardini Naxos, Italy, June 13–16, 2005. [15] J. Leguay, T. Friedman, and V. Conan, “Evaluating Mobility Pattern Space Routing for DTNs,” Proc. IEEE Infocom 2006, Barcelona, Spain, Apr. 2006. [16] J. Leguay, T. Friedman, and V. Conan, “DTN Routing in a Mobility Pattern Space,” SIGCOMM’05 Workshops, Philadelphia, USA, August 2005. [17] D. Goodman et al., “INFOSTATIONS: A New System Model for Data and Messaging Services,” IEEE VTC’97, vol. 2, pp. 969–73, May 1997. [18] T. Small and Z. J. Haas, “The Shared Wireless Infostation Model — A New Ad Hoc Networking Paradigm (or Where There is a Whale, there is a Way),” Proc. 4th ACM Int’l. Symp. Mobile Ad Hoc Networking and Computing (MobiHoc 2003), Annapolis, MD, June 1–3, 2003. [19] W. Zhao, M. Ammar, and E. Zegura, “A Message Ferrying Approach for Data Delivery in Sparse Mobile Ad Hoc Networks,” Proc. 5th ACM Int’l. Symp. Mobile Ad Hoc Networking and Computing (Mobihoc), ACM Press, pp. 187–98, May, 2004. [20] S. Jain et al., “Exploiting Mobility for Energy Efficient Data Collection in Wireless Sensor Networks,” ACM/Kluwer Mobile Networks and Applications (MONET), vol. 11, no. 3, pp. 327–39, June 2006. [21] R. Shah, S. Roy, S. Jain, and W. Brunette, “Data mules: modeling a three-tier architecture for sparse sensor networks,” in IEEE SNPA ’03, Anchorage, Alaska, USA, 2003. [22] P. Juang, H. Oki, Y. Wang, M. Martonosi, D. Rubenstein and L. Peh, “Energy-Efficient Computing for Wildlife Tracking: Design Tradeoffs and early Experiences with Zebranet”, in ASPLOS-X, October 2002. [23] B. Chen, K. Jamieson, H. Balakrishnan and R. Morris, “Span: An Energy- Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks”, in Mobicom , pp. 85–96, Rome, Italy, July 2001. [24] B. Chen, K. Jamieson, H. Balakrishnan and R. Morris, “Opportunistic Data Collection for Disconnected Wireless Sensor Networks by Mobile Mules”, in Ad Hoc Networks Journal, National Chiao Tung University, Taiwan, 11 Januar 2013.