Performance Analysis of DEBT Routing Protocols for Pocket Switch Networks

Khairol Amali bin Ahmad,Mohammad Nazmul Hasan,Md.Sharif Hossen,＊ and Khaleel Ahmad

1Department of Electrical&Electronics Engineering,National Defence University of Malaysia,Malaysia

2Department of Information and Communication Technology,Comilla University,Cumilla,Bangladesh

3Department of Computer Science&Information Technology,Maulana Azad National Urdu University,India

Abstract: Pocket Switched Networks (PSN) represent a particular remittent network for direct communication between the handheld mobile devices.Compared to traditional networks, there is no stable topology structure for PSN where the nodes observe the mobility model of human society.It is a kind of Delay Tolerant Networks (DTNs) that gives a description to circulate information among the network nodes by the way of taking the benefit of transferring nodes from one area to another.Considering its inception,there are several schemes for message routing in the infrastructure-less environment in which human mobility is only the best manner to exchange information.For routing messages,PSN uses different techniques such as Distributed Expectation-Based Spatio-Temporal (DEBT) Epidemic (DEBTE),DEBT Cluster(DEBTC),and DEBT Tree(DEBTT).Understanding on how the network environment is affected for these routing strategies are the main motivation of this research.In this paper,we have investigated the impact of network nodes,the message copies per transmission,and the overall carrying out of these routing protocols.ONE simulator was used to analyze those techniques on the basis of delivery,overhead, and latency.The result of this task demonstrates that for a particular simulation setting,DEBTE is the best PSN routing technique among all,against DEBTC and DEBTT.

Keywords: Pocket switched networks; routings; distributed cluster detections;delay tolerant networks; mobility in network

1 Introduction

In Delay Tolerant Networks (DTNs), the communicative nodes are associated sparsely with one another without any face to face link among the devices which are affected by social and geographic constraints [1-3].In these networks, nodes are connected intermittently and use a store-plus-forward technique for message passing.Nodes use this approach by keeping copies in their buffer and send the message whenever they get the opportunity to an available path under the constraints of limited bandwidth [4-6].Depending on the method of transmission and communication scenario, DTNs are grouped either as flooding, forwarding, or social category;where the last category is based on human relationships, behavior, and pattern in society.From the social-based DTN, pocket switch network (PSN) has been introduced.Hence PSN is a part of DTNs [7-10].The term “pocket” here is employed rather than “packet” to mean that information is transferring from one mobile in the pocket to another.It uses humans and their motion to transfer information.Mobile phones are all over the place and since these devices are placed in pockets, hence the term PSN.It is a network where mobile devices handheld by people are the key to share messages [11-14].It was first introduced by Crowcroft in 2005 to build the complex links among the people [15-17].It gives a particular quality of service for these mobile networks which are dynamically changeable and helps to apply “people-oriented universal mobile computing.”Fig.1 represents such a network where people share their messages until the connection lasts among the mobile phones within certain regions when they move around [18-21].

Figure 1: A PSN where dashed lines and solid arrows show the message forwarding and the movement of device holders, respectively

In relation to such concept, cluster detection methods have been used to ensure effective message delivery in such networks.Hierarchical connections of such networks are made by forming clusters of nodes, which can be used to efficiently transfer messages between the nodes.Cluster-based message delivery techniques show effective data transmission.In this paper, we study distributed cluster detection methods and investigate the related routing protocols for message transmission in PSN [22-24].The paper is shaped as follows.In Section 2, routing approaches in PSNs with the concept of DTNs are discussed.Then, distributed clustering techniques are described in Section 3.The results and discussion are presented in Section 4.Finally, the summary with future work is concluded in Section 5.

2 Routings in Pocket Switched Network(PSN)

In PSN, several routing methods have been projected to increase the performance of message routing.Like DTN, generally, there are two types of routing methods in PSN: forwarding and replicating [19].The first technique delivers only a message to its target node.It works well in a network that has the knowledge to decide the routing path and has good connectivity between the nodes.First contact and Direct delivery are examples of this type of routing.The second approach creates many duplicates of the actual message to increase the message delivery probability.By duplicating the messages, there are higher delivery ratio and lower average latency.An opportunistic network such as PSN uses this type of approach.Unfortunately, there are a lot of redundant messages, which consume network resources, like energy, bandwidth, and buffer space [25-27].Examples of routing protocols using the second approach are epidemic, maxprop,prioritized epidemic (PREP), prophet, and so on.A variation of this method is based on a quota that ensures the proper utilization of resources.Examples of such protocols are encounter-based,SNW, SNF, ORWAR, etc.

The goal of this research is to investigate the efficient routing for sending the messages in the inter and intra-cluster scenarios based on the distributed expectation based (DEBT) clustering techniques.The three routing techniques are DEBT Epidemic (DEBTE), DEBT Clustering(DEBTC), and DEBT Trees (DEBTT).The first two routing methods, namely DEBTE and DEBTC use the branch information in the local cluster tables for forwarding the messages to the next neighbour nodes as a non-hierarchical approach.The final technique which is DEBTT takes the routing information using a tree-based data structure.It is also capable to find out the routing loops by doing some additional processing in the network.

2.1 Epidemic Based DEBT Forwarding(DEBTE)

This protocol makes the best use of the branch and neighbour data to take decisions in propagating messages in a network.If the destination of a message is in the cluster table of an encountered personal mobile wireless device (PMWD), then a device forwards a message copy to the PMWD.From Fig.2, ifvidesires to transmit a message tovland encountered withvj, at firstviwill send the message tovjsincevjhas a link to thevlsomewhere in the local cluster table.The message forwarding methods for DEBTE create a lot of duplicate messages which may result in loss of bandwidth and energy of the network [25].

Figure 2: Cluster table for the node vi, and the corresponding diagram of the local cluster.(a)Local cluster table for vi.(b) Local cluster of vi

2.2 Cluster Based DEBT Forwarding(DEBTC)

To decrease the number of redundant messages, the cluster-based routing method called DEBTC takes more protective decisions for transmitting messages from the sender device to the destined one.It will not forward a message to an encountered PMWD if there is a transmitting PMWD of the encountered PMWD in a similar line of its local cluster.From Fig.2,viintends to send a message forvlbut it will not copy tovjbecausevjhas a link with bothvlandviin the same row.Another reason for limiting duplication of the messages withinviandvjis thatvjmay get the information about the destination nodevlfrom the transmitting nodevi.So, a message will not be transferred if there exists any routing loop in the local cluster.On the other hand,preventing routing loops may also result in less message delivery.To remove this problem, the final routing method that uses a tree-based approach named Tree-based DEBT (DEBTT) is considered.

2.3 Tree Based DEBT Forwarding(DEBTT)

This method reduces the difficulty of DEBTC where even when there may be a path to send information to the final node, it will not send the message as there may exist a message routing loop in the local cluster.If the messages are processed as a non-hierarchical structure, it is impossible to accurately identify the routing loop in the branch data.So, DEBTT uses a treebased approach by taking the information received from the local cluster table.The same example ofvitrying to transmit a message tovlviavjis shown in Fig.3.There is a path between the transmitting vertexvjand the target vertexvlin the branch column that doesn’t hold any loop and so the message will be sent fromvitovj.The methodology is the same as the other routing techniques, but the local cluster tables are tree-based in DEBTT.Since the clusters are transferred as tree-based on DEBTT, and joined to other trees, there need several parameter measurements so that trees do not extend indefinitely.

Figure 3: An example of a local cluster table for vi using DEBTT and image showing the corresponding cluster.(a) Local cluster table for vi (b) Local cluster of vi

3 Distributed Based Clustering Techniques

A cluster is defined as a set of tightly or loosely connected communicating devices that operate simultaneously so that they can act as a single unit.There is a node-set for every cluster to perform the same job, which is maintained and supervised by software.There are different types of techniques which suited to different purposes while dealing with clustering:

? Clustering for ensuring good performance

? Clustering for reducing duplication

? Storage cluster

The fundamental concept of clustering is to group n nodes to k several clusters.It is possible to separate a cluster from a group of vertices that contain more edges among themselves.There are several types of cluster detection techniques that can be used for network analysis.

3.1 Types of Clustering

There are several types of clustering techniques namely partitioned, density, spatial and budget based.In partitioned based clustering, vertices are directly decomposed within incoherent clusters that utilize several partition standards.Density based clustering creates an arbitrary shape cluster depending on the density of nodes in the network, such as clusters discovered by OPTICS.This method is also capable of producing data points that are not associated with any cluster called outliers.Spatial based clustering is usually applied in grid data structures and spatial data mining.It uses Euclidean distance in the clustering methods.Budget based clustering creates clusters for a specific network by applying different agglomerative clustering techniques including an upper bound which represents the maximum cluster size.In distributed based clustering methods for PSNs, network nodes are accountable for clustering except accessing the central data source.They dynamically create a cluster for message forwarding.

Figure 4: Illustration of local clusters associated with vi and vj [25]

3.2 Distributed Clustering Characteristics

There are some distinct features for distributed clustering.Let a PSN network hasnPMWDs and is using a distributed clustering technique.Then, every PMWD will create a map containing up to n-1 PMWDs in a local cluster set.

If there are n PMWDs in a network, it will create n non-empty and very similar local clusters.These local clusters are being one of the 2n-1 possible local clusters.If the cardinality is less than of a single local clusterCi, thenCiwill overlap with |Ci|-1 other local clusters.

Let there be a set of local clusters that are created from PSN and named natural cluster (N).

N={x: A local cluster x which belongs to a network P}

If these n clusters are separate from each other, then |N| = n.There are several unique characteristics of natural clusters such as each PMWD is created has to be a natural cluster, and these clusters may be associated with different natural clusters.

To include dynamic encounters in a local cluster, two parameters need to be calculated in the distributed cluster detection technique.These parameters are cumulative encounter duration and baseline calculation.Because of the frequent movement of nodes, it is a very complex task to meaningfully add new nodes in a cluster than to calculate cumulative encounter duration.For example, the cumulative encounter duration for the nodeviwith the nodevjin the time frame t2as shown in Fig.5 isEq.(1) shows the mean cumulative encounter calculation methods for nodeviduring t2time frame.The calculation of mean cumulative encounter duration also referred to as the metric m, and it has to use the baselines calculation.

Using the previous time series values, there needs to calculate expected values for metrics called baselines.So there is no necessity to set the threshold value manually when selecting nodes to the cluster.Baseline calculation for a particular time frame is done at the closing point of the preceding time frame.

Figure 5: Example of a dynamic graph between time frames t1 and t3

To describe the method easily, let there be a time frame whose length is l and it is divided into different time frames labeled by t1, t2, t3,...,t(n-1),tn, where t1is first, t2is second, andtnis the current time frame.The baseline for the present time frametnfor the vertexviis estimated by measuring the mean values of m.To calculate m, it uses previous w complete time frames,which is shown in Eq.(2).

After the expected baseline calculation for the present time frame is obtained, it is used to compare with cumulative value for a particular node within the present time module.There is no strongly linked subgraph constrain in distributed cluster detection techniques.It can continuously keep track of the cumulative meeting duration with the other devices in the network and takes the necessary decision to involve neighbour nodes in the cluster as their cumulative value gets the baseline.

For example, let there are two vertices namelyviandvjin a network.If vertexviwants to includevjin its local cluster, the cumulative value x between the nodesviandvjwithin a particular time frametnmust be greater than a coefficient value,gup, which is multiplied with the baseline value for the vertexvias demonstrated in Eq.(3).To monitor the cluster size in the distributed clustering mechanism of a network, two parameters are introduced namelygupand gdown.For example, we consider the baseline value of the vertex,vi, is 20, and the cumulative value between the vertexviandvjin the time frametnis 30.Then, if we use parameter valuegup=1, Eq.(3)will be satisfied with the condition that the vertexviwill add the vertexvjin its local cluster.On the other hand, if we considergup= 2, then Eq.(3) will not be satisfied, and the vertexvjwill not be added in the cluster.

4 Results and Discussion

Here, we focus on the analysis of DEBT techniques, i.e., DEBTE, DEBTC, and DEBTT in PSN using ONE simulator.In this section, we explain the environment modeling parameters,performance metrics, and simulated results.

4.1 Opportunistic Networking Environment(ONE)

It is an event-driven network simulator that was developed using java programing language.Using various types of movement modes, it can generate node movement, route messages using various routing techniques between the nodes, and visualize both message passing and mobility in its GUI.It can also import real-world traces of data.Collecting the analyzed result, the routing performance is done through reports and visualization [28,29].The key operations of this tool are the simulating of network routing, nodes motion, message handling, and contact between intermediate nodes using various interfaces.Network nodes can change their location according to the movement models.The nodes can keep their connectivity on the basis of their communication distance, present location, and data rate.Message sending is routed by the analyzed methods that take the decision when and how to send messages over a network link.Event generators generate the messages to trace the network.It generates random messages between the nodes.It is also possible to generate traffic using applications based on application interactions.There are source and destination nodes for these unicast messages inside the simulation range.The report module receives events and generates simulation results during the simulation that are collected through the reports.It is also capable of visualizing the simulation result showing the mobility, active contacts, locations, and messages passing in the real scenario by the nodes [30,31].

4.2 Parameter Setup

Simulation parameters and related protocols are specified in Tab.1.It exhibits the outline of the simulation using random waypoint as mobility and shortest path map-based movement as movement model with update interval 1s for analyzing the performance metrics with the different values of the message (Msg) copies per minutes (MCPM), and the number of nodes (NN) in the network.

Table 1: Simulation characteristics with values

4.3 Comparing the Performance of Routing Methods with Metrics

Here, we investigate the performance analysis of DEBT routing strategies, i.e., DEBTE,DEBTC, and DEBTT using ONE simulator with different values of Msg copies per minutes, and the number of nodes with three metrics as discussed below.

4.3.1 Delivery Probability(DP)

It is determined as the ratio of the number of successful data arrived at the target node sent by source nodes [32].Fig.6, illustrates that DEBTE routing has the highest message delivery probability than DEBTC and DEBTT for each generation rate of the message since it sends the messages to all possible nodes.On the other hand, DEBTT has the lowest delivery probability since it does not allow any looping nodes in the network before transferring messages.DEBTE also shows the highest DP than DEBTC and DEBTT for the changes of nodes while DEBTT has the lowest DP for every node (Fig.7).

Figure 6: DP with different values of Msg/min

Figure 7: DP with different values of nodes

4.3.2 Average Latency(AL)

AL is the duration time obtained on average between the creation of messages and the acceptance of those messages successfully by target node [13,32].If there is low average latency in any network, then it can be considered a good performance.From Fig.8, AL of DEBTE is higher than DEBTC and DEBTT for every message generation rate.In Fig.9, we see that the average latency of DEBTE increases while for DEBTC and DEBTT decreases with the increase of network nodes.When we use less than 50 nodes, DEBTC showed the highest delay (Fig.9) while DEBTE had the best performance as indicated by the lowest latency than DEBTC and DEBTT.

Figure 8: AL with different values of Msg/min

Figure 9: AL with different values of nodes

4.3.3 Overhead Ratio(OR)

It is determined by the calculation of the number of duplicate copies sent redundantly to successfully reach the destined node [32].It is directly related to the transmission cost in a network.Good network performance has a less overhead ratio.Fig.10 depicts that OR decreases for different values of msg/min where DEBTE shows slightly higher OR than DEBTC and DEBTT.In comparing the OR against the number of nodes, DEBTT clearly demonstrated lower OR compared to DEBTC and DEBTE (Fig.11).Meanwhile, DEBTE showed the highest OR in both Figs.10 and 11.

Figure 10: OR with different values of Msg/min

5 Conclusion and Future Works

Pocket switched network (PSN) represents a particular remittent network for direct communication between mobile nodes.Its existence comes from the delay-tolerant networks that work in a challenging environment like terrorist attacks, hurricanes, and other natural disasters.It enables message communication when traditional cellular networks are not applicable because of geographical position.PSN can be very useful in real-life scenarios.Since it can operate without any infrastructure when any geographical location or country gets hit by any natural disaster, namely tsunami, earthquake, etc., it can help the rescuers to find out the people who are trapped inside buildings.Under such scenarios, we analyze the performance of different routings, namely, Distributed Expectation-Based Spatio-Temporal (DEBT) Epidemic (DEBTE),DEBT Cluster (DEBTC), and DEBT Tree (DEBTT) in PSNs.The performance evaluation is done using ONE simulator.The simulation outcome exhibits the performance comparison of these approaches for average latency, delivery, and overhead calculation with various values of message copies (msg/min) and network nodes per group, respectively.From these results, we can conclude that DEBTE performed the best.In the near future, we would like to extend this task by comparing these routing protocols with other available routings.

Acknowledgement:Authors would like to thank anonymous reviewers and the Journal Editor.

Funding Statement:This research is fully supported by UPNM Grant J0117-UPNM/2016/GPJP/5/ICT/2.The authors fully acknowledged Ministry of Higher Education (MOHE) and National Defence University of Malaysia for the approved fund which makes this important research viable and effective.The authors also would like to thank University Grant Commission of Bangladesh,Comilla University for the financial support.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.