Mail Man Ferry: A Novel Routing Protocol in Intermittently Connected Networks

Abstract

As an important area for mobile wireless networks, Intermittently Connected Networks (ICNs) have received increasing attention in practice and research in recent years. The main goals of the ICN routing protocol are to maximize the delivery probability and to minimize the delivery delay. These challenges have been investigated in previously proposed protocols with an assumption of fully cooperating nodes. Node cooperation directly impacts ICN performance in terms of delivery probability and delay. However, node cooperation is not guaranteed because a cooperating node consumes its buffer size and energy, thereby highlighting the challenges of memory, computation, and energy efficiencies. This paper addresses the challenge of ensuring node cooperation by proposing a novel routing protocol called Mail Man Ferry (MMF). The new protocol includes a node credit mechanism that ensures the cooperation of the network nodes. Extensive simulations were executed to evaluate the proposed protocol. Varying values of node cooperation in ICNs were employed in the simulation tests. The evaluation shows exciting results in which Mail Man Ferry outperforms previously proposed ICN protocols.

1. Introduction

Although computer networks have become easily accessible and wide-spread, mobile wireless networks still suffer from delays, interruptions, and other issues [1]. This is due to several reasons, such as the change in network topology or harsh environment, such as bad weather, and shadowing that affects the nodes’ communications. In order to provide a solution for such issues, there is a need to enhance flexibility and efficiency in the communications between nodes.

Wireless networks can be classified as fixed, ad hoc, and intermittently connected networks (ICNs). An access point is employed in the fixed network to receive and resend data between network users. This form establishes dependency on certain access point locations for wireless communication. The condition of access points existing in fixed wireless network structures has been eased and replaced by ad hoc networks. In ad hoc networks, mobile nodes exchange data without the need for fixed access points. Instead, nodes exchange data via other mobile nodes in the network until they reach their destination. Although ad hoc networks offer a solution to the fixed network structure requirement, their challenge is to keep all the mobile node locations and movements to maintain paths for future routing. This increases the overhead in the mobile nodes where an intermittently connected network has been proposed to solve the issue. The employment of ICNs omits the need for keeping records of network node locations and existing paths as a major overhead in ad hoc network.

An Intermittently Connected Network (ICN) refers to a wireless network without a physical backbone in which end-to-end connectivity between nodes is not guaranteed. Another name for these networks is Delay Tolerant Networks (DTNs). Unlike other kinds of networks, which are commonly understood to have continuous routes between every pair of connected nodes, ICN nodes are not always connected and often only exist for a short time. Nodes in ICNs may forward a message to their destination without needing to monitor the locations of the other nodes along the path.

Due to their ability to support mobile nodes without requiring fixed interconnections, ICNs have been the focus of extensive and ongoing study. This structure offers the adaptability required by mobile wireless networks. Applications of ICNs stimulate the growth of ICNs as a subject of study. For example, the InterPlaNetary (IPN) Internet Project and the Wizzy Digital Courier Service, connect people in remote villages and less-developed areas who do not have access to the Internet. They also connect people during mission-critical operations, such as in natural disasters and disaster areas [2].

The remaining sections of the paper are laid out as follows: Motivation and significance of this study’s contribution are discussed in Section 2. In Section 3, we describe the relevant prior work. In Section 4, the envisioned procedure is detailed. Parameters and outcomes of the simulation are discussed in Section 5. The conclusion and recommendations for further research are presented in Section 6.

2. Motivation and Contribution

ICNs create routing challenges, because commonly used routing protocols may not be applicable in such a structure for delivering data. Thus, ICN networks have several issues that are less likely in legacy networks. These issues include network partitioning, high loss probability, long and varying delays, asymmetric data transmission rates [3], and detecting and preventing intrusion of malicious nodes [4]. Further, nodes in ICNs have limited buffer space and battery life; this could affect their cooperation in carrying messages from other nodes because frequent retransmission leads to occupying their buffer space as well as energy consumption. The continuous exchange of messages also leads to other messages being dropped due to the limited buffer space [5]. The characteristics of ICNs have made it difficult to find an approach that has a high probability of delivery while maintaining energy efficiency. This signifies the importance of utilizing the resources effectively and efficiently. This can be achieved by enhancing the cooperation between nodes.

A node is considered to be cooperating with other nodes when it accepts the responsibility of carrying messages sent by other nodes. Pdrop is the chance that a node drops a message after receiving it, and Pforward is the probability that the messages is forwarded. These probabilities are affected based on node misbehavior or node buffer or energy limitation [6], which influences node cooperation. A similar experiment was carried out in [7]; however, this time, Pforward was used in its place as a dynamic parameter. The assumption in [8] was that a node does not discard a message after receiving it, although an encountered node may not accept it. These studies show the impact of node cooperation in an ICN in which they confirmed that noncooperating nodes sharply decrease the delivery probability in an ICN. Thus, a need for the work in this paper is raised where a routing protocol for ICNs with a node cooperation mechanism is ensured.

In this paper, we propose a novel protocol, Mail Man Ferry, that improves the delivery probability by improving the routing decisions. It includes a node credit mechanism to ensure an informative decision is made as to whether the message is forwarded. Node credits increase by the number of times a node travels through a ferry path to help other nodes deliver their messages.

3. Related Works

This section highlights some of the most relevant research in the context of (i) Data Exchange Methods in ICNs and (ii) ICN Routing Protocols. The discussion of the relevant research highlights the proposed solution’s novelty and scope.

3.1. Data Exchange Methods

The primary benefit of routing in ICNs is that paths between nodes do not need to be maintained. Instead, each node may exchange data in one of the three methods: opportunistic forwarding, prediction-based, or social relationship-based technique. The selection of the corresponding message carrier determines how the techniques are categorized. With the opportunistic technique, messages are routed to any discovered node. Refs. [9,10] present two opportunistic routing protocols. In the prediction-based technique, a node calculates the probability that the encountered node will deliver a message to its intended receiver. If the discovered node is more likely to deliver a message than the present message carrier, a copy of the message is sent to it. The contact history of a node is one component used in the probability calculation. Prediction-based techniques include [11,12,13,14,15,16] as examples. The third routing approach in ICNs is social-based. A copy of a message is given to the encountered node if it shares similar social interests or activities with the destination node. The authors of [17,18,19,20,21,22,23,24,25,26] provide a few examples of routing protocols that are based on social interests or activities. ICN routing strategies seek to improve the delivery probability. The ratio of successfully delivered messages to messages sent is known as the delivery probability. The network will be expected to convey messages more effectively the more widely distributed the messages are.

3.2. Routing Protocols

Epidemic [9] is an opportunistic-based routing method. Messages are flooded in Epidemic until it reaches the message’s destination. Message flooding is defined as sending a copy of a message to all nodes encountered. Another suggested routing system that uses an opportunistic strategy is spray and wait [10]. The spray and wait protocol limits the number of given copies of a message to L copies. The choice of L can be determined based on several factors, including the environment size and number of nodes. The main issue with opportunistic forwarding is the resource consumption in multiple copies of each message. So, a prediction-based routing protocol called PRoPHET (Probabilistic Routing Protocol) has been suggested [13]. In PRoPHET, nodes only receive a copy of a message if their chance of sending it to the destination is higher than the current message carrier’s chance. The contact history with the destination is used to determine how likely each node will deliver the message. The more frequently a node meets a destination node, the more likely it is to meet the destination node again, making it more likely that the package will be delivered. Increasing the node delivery probability in PRoPHET makes a node a candidate to receive a copy of a message.

Status [19] is social networking-based routing. Nodes discovered by this protocol send messages based on two factors: They send the message to the found node if it has a status, and the status indicates the node is heading to the location\point of interest (PoI). Like a shopping mall or park, a PoI has multiple nodes. Second, a nearby node receives a message, and the status simplifies PRoPHET’s calculations. Epidemic utilizes less resources, and Epidemic is more prevalent when resources are unlimited.

4. Mail Man Ferry in ICNs

The concept of the protocol proposed in this paper is inspired by the traditional Mail Man Ferry model. In such a model, a traditional mail man takes a regular path to collect all the mails in this particular path to the mail office. In the mail office, the letters are classified and routed in groups to their destinations. For example, 10 letters could be directed to country A, whereas another 10 letters are directed to country B. The question here is if the Mail Man traditional model has been successful for decades, can the same concept be applied as a routing method in ICN. Therefore, this work examines the benefits of the Mail Man model toward improving the two main metrics in any ICN routing method: delivery probability and delay. The importance of the Mail Man Ferry method is not just to propose a new ICN routing method, but to ensure node cooperation, which is essential to increase delivery probability. In the Mail Man Ferry method, node cooperation is guaranteed because a credit concept for cooperating nodes is employed.

A few paths are predefined in the Mail Man Ferry method to be known as ferry paths. The predefined ferry paths can be chosen based on the deployed environment. For real mapping of city, as an example, the city highways and major roads could be chosen to be the ferry paths. A node taking these paths is a candidate to carry other messages from nodes in the network. To encourage node cooperation, whenever a node passes through these predefined ferry routes, it receives a credit, and its credits increase as it passes via these routes every time. Note that the node credit can be interpreted as allowing a node to disseminate more messages compared to a node with no credit. A node with high credit is capable of disseminating multiple copies of its own messages to its encountered ferry nodes, whereas a message with low credit is not allowed to disseminate its messages to an encountered ferry node; i.e., nodes without credits have to deliver their messages by themselves. Note that one of the expected costs in the Mail Man Ferry protocol is the need for a dedicated buffer space to identify the predefined ferry paths because nodes are encouraged to travel through to raise their credit as cooperating nodes. This cost can be separately studied in future work.

Figure 1 presents the message exchange when the Mail Man Ferry method is not employed and shows that node S can exchange messages with its encountered nodes L and K although only L is on the ferry route, whereas K does not take a ferry path, i.e., Epidemic message dissemination. Figure 2 shows the message exchange process when the Mail Man Ferry method is employed without taking into consideration the credit concept for node cooperation. Note that S only disseminates messages to L where it takes a Mail Man Ferry path, whereas K does not receive any messages from S because it takes a random path, not a predefined as ferry path. Figure 2 also shows that both R and T are able to disseminate messages to E without consideration of their credit history in cooperation. Finally, Figure 3 presents the message exchanges when both the Mail Man Ferry method and the credit concept of node cooperation are employed. Figure 3 shows that S is able to forward messages only to L because it is on the Mail Man Ferry path. Furthermore, only R is able to disseminate messages to E because it has credit in cooperation, whereas T needs to keep its copies until it reaches its destination because it did not show any cooperation in the past.

5. Performance Evaluation

This part begins with an explanation of the specifics of the cosimulator used and the simulation parameters. Then, an analysis of the performance of the suggested technique is presented. After that, the performance of the proposed method is compared with that of Epidemic and Prophet, which are the two oldest-proposed protocols in the field and have been used as reference methods for the comparison of new ICN protocols in the literature [19,20,21,22,23,24,25,26]. We took into consideration four distinct scenarios of node cooperation, ranging from 25 percent to 100 percent.

5.1. Simulation Environment

In this research, we used the ONE simulator [27] to study the effect of the Mail Man Ferry technique in an ICN routing setting. To put it simply, ONE is software for simulating “one-off” situations. It incorporates tracking locations, planning routes, viewing data, and reports generation. How a node moves in a simulation is set by its mobility model. The random waypoint model (RWPM) is frequently used and is based on random headings and speeds. For people carrying mobile devices, however, this kind of random node mobility is impractical. It is more practical to suppose that nodes travel toward one destination, then another, and so forth. Malls, restaurants, schools, and other commonplace establishments are examples of places of attraction. The more realistic shortest path movement model (SPMM), which has nodes traveling toward specific destinations, was used here.

The simulation settings that were employed for this study are based on the real environment that was discussed in [28], which is where the Helsinki City Scenario (HCS) model is used. The scenario involves nodes moving throughout part of the central business district of Helsinki. The mobility of HCS nodes is determined by modeling the movements of sixty mobile persons as they navigate the streets of downtown Helsinki by foot, vehicle, and tram. Each node illustrates a person moving at a speed that is consistent with real life along the routes that are the shortest distance between a variety of points of interest (POIs) and locations that were chosen at random. In Helsinki, the trams travel along routes that were originally intended for them. The simulation area was designed to be 4500 × 3400 m² in size. The simulation environment parameters were broken down into their essential components and are shown in

Table 1. Simulation environment parameters.

Parameter	Value
Transmit Rate	250 KBps
Transmit Range	50 m
Message Size	50 KB

below.

5.2. Performance Results and Discussions

In this part, simulated experiments were carried out to analyze the performance of the proposed technique compared to two early protocols in ICN, namely the Epidemic routing protocol and the Prophet routing protocol, with different percentages of nodes cooperating.

Figure 4 shows the delivery probability of the three compared routing protocols: Epidemic, prophet, and Mail Man Ferry, when node cooperation is 100%. Note that 100% node cooperation means any node during a simulation agrees to carry messages from other encountered nodes to deliver them to their final destinations. Figure 4 shows that Epidemic outperforms Prophet and Mail Man Ferry protocols in such a case. The Epidemic method distributes the highest number of message copies, which helps the protocol achieve the best possible delivery probability of messages. Prophet limits the distribution of messages copied to encountered nodes that have a higher probability of meeting their final destinations. Further, Mail Man Ferry limits its distributed copies to nodes in the Mail Man Ferry paths. More message distributions in an intermittently connected network increase the delivery probability when the node buffer is sufficient. This explains the performance of Epidemic when node cooperation is 100%.

The experiment was also conducted at a node cooperation of 75% (see Figure 5). Note that the Mail Man Ferry method was not largely affected by the decline in node cooperation because the existing nodes in the mail man paths are sufficient to deliver the copies of the messages needed. On the other hand, the delivery probabilities in Epidemic and Prophet decreased by 7% and 3%, respectively. This is because their distributed copies had decreased by 25% without a proper routing mechanism that reduces such a decline in node cooperation. This shows that Mail Man Ferry mechanisms, such as predefined ferry paths, are capable of maintaining best possible delivery probability compared to Epidemic and Prophet.

Figure 6 presents the delivery probability of the three compared protocols when node cooperation is 50%. The Mail Man Ferry method maintains its best message delivery probability performance compared to Epidemic and Prophet. The Mail Man Ferry method outperforms the two protocols by 6%, and this percentage is expected to grow when node cooperation decreases. Note that Mail Man Ferry continues to outperform Epidemic and Prophet in delivery probability taking advantage of the node credit mechanism employed.

Figure 7 shows the delivery probability of the three compared protocols when node cooperation is 25%. There are two important reads from Figure 7. First, the Mail Man Ferry method maintains similar performance when node cooperation is 50%. This result shows that Mail Man Ferry is an efficient method against failure under any circumstances. The other note is that Epidemic and Prophet continue to underperform in delivery probability as node cooperation declines. This is due to the employed message dissemination mechanism in Epidemic and Prophet, whereas nodes in both protocols are expecting full cooperation of the encountered nodes without the node credit concept that is employed in Mail Man Ferry.

The above figures show higher efficiency of the Mail Man Ferry method compared to the other routing protocols in an intermittently connected network (Epidemic and Prophet). The efficiency is proven by being able to resist the decreases in the node cooperation percentages in which it maintains similar delivery probability, while Epidemic and Prophet could not.

The target node average message delay is now investigated.

Table 2. Average latency for the three compared routing protocols.

	Cooperation Probability	Average Latency (min)
Routing		100%	75%	50%	25%
Epidemic		89	91	92	93
Prophet		84	88	93	98
Mail Man Ferry		69	70	72	73

compares the average latency for the three protocols used in our experiment with varying cooperation percentages. This demonstrates that the Mail Man Ferry approach has the lowest average delay when all nodes cooperate. This is because messages are better-directed to their destinations when they are carried by nodes that are anticipated to go along predetermined paths, such as Mail Man paths. On the other hand, the latency rises as the percentage of participating nodes falls. A similar concept is applicable in Epidemic and Prophet, but with much higher latency. Mail Man Ferry starts with 68 min, while Epidemic and Prophet start with 89 and 84, respectively. This shows that Mail Man Ferry not only maintains suitable delivery probability, but also maintains lower average latency to deliver the messages to the nodes.

6. Conclusions

In this paper, a routing method, namely Mail Man Ferry, is proposed. The main goals of the method are to improve the delivery probability and to lower the average latency of delivering messages. These goals are achieved in this work as a result of the implementation of a mechanism within the proposed method that enhances node cooperation. Node cooperation enhancement is attained by taking the form of rewarding points. Nodes receive points if they help each other, and they are expected to receive helps. This method encourages nodes to cooperate and minimizes the effect of noncooperating nodes because of their power concerns or any other issues. The simulation results proved the efficiency of the proposed method compared to other methods in intermittently connected networks. This result contributes to the ongoing research activities that attempt to improve the performance of ICNs in mobile wireless networks.