DOI:10.32604/cmc.2021.014436
| Computers, Materials & Continua DOI:10.32604/cmc.2021.014436 | |
| Article |
Performance Analysis of DEBT Routing Protocols for Pocket Switch Networks
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
*Corresponding Author: Md. Sharif Hossen. Email: mshossen@cou.ac.bd
Received: 20 September 2020; Accepted: 19 October 2020
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
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, if vi desires to transmit a message to vl and encountered with vj, at first vi will send the message to vj since vj has a link to the vl somewhere 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, vi intends to send a message for vl but it will not copy to vj because vj has a link with both vl and vi in the same row. Another reason for limiting duplication of the messages within vi and vj is that vj may get the information about the destination node vl from the transmitting node vi. 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 tree-based approach by taking the information received from the local cluster table. The same example of vi trying to transmit a message to vl via vj is shown in Fig. 3. There is a path between the transmitting vertex vj and the target vertex vl in the branch column that doesn’t hold any loop and so the message will be sent from vi to vj. 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
Figure 4: Illustration of local clusters associated with vi and vj [25]
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.
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.
3.2 Distributed Clustering Characteristics
There are some distinct features for distributed clustering. Let a PSN network has n PMWDs and is using a distributed clustering technique. Then, every PMWD will create a map containing up to 
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 
possible local clusters. If the cardinality is less than of a single local cluster Ci, then Ci will 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).
If these n clusters are separate from each other, then 
. 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 node vi with the node vj in the time frame t2 as shown in Fig. 5 is 
. Eq. (1) shows the mean cumulative encounter calculation methods for node vi during t2 time frame. The calculation of mean cumulative encounter duration also referred to as the metric m, and it has to use the baselines calculation.
Figure 5: Example of a dynamic graph between time frames t1 and t3
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.
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 t1 is first, t2 is second, and tn is the current time frame. The baseline for the present time frame tn for the vertex vi is 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 namely vi and vj in a network. If vertex vi wants to include vj in its local cluster, the cumulative value x between the nodes vi and vj within a particular time frame tn must be greater than a coefficient value, gup, which is multiplied with the baseline value for the vertex vi as demonstrated in Eq. (3). To monitor the cluster size in the distributed clustering mechanism of a network, two parameters are introduced namely gup and gdown. For example, we consider the baseline value of the vertex, vi, is 20, and the cumulative value between the vertex vi and vj in the time frame tn is 30. Then, if we use parameter value gup = 1, Eq. (3) will be satisfied with the condition that the vertex vi will add the vertex vj in its local cluster. On the other hand, if we consider gup = 2, then Eq. (3) will not be satisfied, and the vertex vj will not be added in the cluster.
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].
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
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
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
Figure 11: OR with different values of nodes
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.
1 M. A. Bayir and M. Demirbas. (2014). “On the fly learning of mobility profiles for routing in pocket switched networks,” Ad Hoc Networks, vol. 16, pp. 13–27. [Google Scholar]
2 E. Wang, Y. Yang, J. Wu and W. Liu. (2016). “Phone-to-phone communication utilizing wifi hotspot in energy-constrained pocket switched networks,” IEEE Transactions on Vehicular Technology, vol. 65, no. 10, pp. 8578–8590.
3 P. Hui, A. Chaintreau, R. Gass, J. Scott, J. Crowcroft et al. (2006). , “Pocket switched networking: Challenges, feasibility and implementation issues,” Autonomic Communication, vol. 3854, pp. 1–12. [Google Scholar]
4 P. Hui and J. Crowcroft. (2017). “How small labels create big improvements,” in IEEE Int. Conf. on Pervasive Computing and Communications Workshops (PerComW’07), White Plains, NY, pp. 65–70. [Google Scholar]
5 M. Conti and M. Kumar. (2010). “Opportunities in opportunistic computing,” Computer, vol. 43, no. 1, pp. 42–50.
6 M. Talukdar and M. Hossen. (2019). “Selecting mobility model and routing protocol for establishing emergency communication in a congested city for delay-tolerant network,” International Journal of Sensor Networks and Data Communication, vol. 8, no. 1, pp. 1–9. [Google Scholar]
7 T. Spyropoulos, T. Turletti and K. Obraczka. (2009). “Routing in delay-tolerant networks comprising heterogeneous node populations,” IEEE Transactions on Mobile Computing, vol. 8, no. 8, pp. 1132–1147. [Google Scholar]
8 M. S. Hossen. (2019). “DTN routing protocols on two distinct geographical regions in an opportunistic network: An analysis,” Wireless Personal Communications, vol. 108, no. 2, pp. 839–851.
9 G. Resta and P. Santi. (2012). “A framework for routing performance analysis in delay tolerant networks with application to noncooperative networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 2–10.
10 L. Pelusi, A. Passarella and M. Conti. (2006). “Opportunistic networking: Data forwarding in disconnected mobile ad hoc networks,” IEEE Communications Magazine, vol. 44, no. 11, pp. 134–141. [Google Scholar]
11 Z. Zhang. (2006). “Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges,” IEEE Communication Surveys and Tutorials, vol. 8, no. 1, pp. 24–37. [Google Scholar]
12 M. Ali, M. R. Fida, A. S. Arsalaan and A. Adnan. (2015). “Implementation and analysis of clustering techniques applied on pocket switched network,” International Journal of Distributed Sensor Networks, vol. 11, no. 9, pp. 1–6.
13 M. Rahman and M. S. Hossen. (2018). “Performance evaluation of social aware routing protocols in an opportunistic network,” Opportunistic Networks: Mobility Models, Protocols, Security & Privacy. New York, USA: CRC Press, Taylor & Francis, pp. 267–277.
14 J. Huang and X. Cheng. (2016). “Wireless relay selection in pocket switched networks based on spatial regularity of human mobility,” Sensors, vol. 16, no. 1, pp. 1–20. [Google Scholar]
15 C. Huang, K. Lan and C. Tsai. (2008). “A survey of opportunistic networks,” Int. Con. on Advanced Information Networking and Applications, Okinawa, pp. 1672–1677. [Google Scholar]
16 K. C. Lin, W. Lin and C. Chou. (2011). “Social-based content diffusion in pocket switched networks,” IEEE Transactions on Vehicular Technology, vol. 60, no. 9, pp. 4539–4548.
17 S. Yang, C. K. Yeo and F. B. S. Lee. (2013). “Cooperative duty cycling for energy-efficient contact discovery in pocket switched networks,” IEEE Transactions on Vehicular Technology, vol. 62, no. 4, pp. 1815–1826. [Google Scholar]
18 T. Salam and M. S. Hossen. (2020). “Performance analysis on homogeneous LEACH and EAMMH protocols in wireless sensor network,” Wireless Personal Communications, vol. 113, no. 1, pp. 189–222. [Google Scholar]
19 M. S. Hossen. (2019). “Analysis of delay-tolerant routing protocols using the impact of mobility models, scalable computing,” Practice and Experience, vol. 20, no. 1, pp. 39–48.
20 E. P. C. Jones, L. Li, J. K. Schmidtke and P. A. S. Ward. (2007). “Practical routing in delay-tolerant networks,” IEEE Transactions on Mobile Computing, vol. 6, no. 8, pp. 943–959.
21 D. McGeehan, D. Lin and S. Madria. (2016). “ChitChat: An effective message delivery method in sparse pocket-switched networks,” IEEE 36th Int. Conf. on Distributed Computing Systems, Nara, Japan, pp. 457–466. [Google Scholar]
22 S. Grasic, E. Davies, A. Lindgren and A. Doria. (2011). “The evolution of a DTN routing protocol PRoPHETv2,” ACM Workshop on Challenged Networks, New York, USA, pp. 27–30. [Google Scholar]
23 A. Mathurapoj, C. Pornavalai and G. Chakraborty. (2009). “Fuzzy-spray: Efficient routing in delay tolerant ad-hoc network based on fuzzy decision mechanism,” in IEEE Int. Conf. on Fuzzy Systems, Jeju Island, South Korea, pp. 104–109.
24 J. Makhlouta, H. Harkous, F. Hutayt and H. Artail. (2011). “Adaptive fuzzy spray and wait: Efficient routing for opportunistic networks,” in IEEE Int. Conf. on Selected Topics in Mobile and Wireless Networking, Shanghai, pp. 64–69. [Google Scholar]
25 M. Orlinski and N. Filer. (2012). “Distributed Expectation-Based Spatio-Temporal Cluster Detection for Pocket Switched Networks,” Dublin, Ireland: IEEE IFIP Wireless Days, pp. 1–6. [Google Scholar]
26 M. Liu, X. Zhang, S. Ge, X. Chen, J. Wu et al. (2019). , “An application-oriented buffer management strategy in opportunistic networks,” Computers, Materials & Continua, vol. 60, no. 2, pp. 559–574.
27 W. Li, B. Jia Baoyintu, J. Wang and T. Watanabe. (2020). “An energy based dynamic AODV routing protocol in wireless ad hoc networks,” Computers, Materials & Continua, vol. 63, no. 1, pp. 353–368. [Google Scholar]
28 A. Keränen. (2008). “Opportunistic network environment simulator,” Department of Communications and Networking, Helsinki, Germany, University of Technology. [Google Scholar]
29 Project Page of the ONE Simulator. [Online]. Available: http://www.netlab.tkk.fi/tutkimus/dtn/theone. [Google Scholar]
30 M. S. Hossen and M. S. Rahim. (2016). “Impact of mobile nodes for few mobility models on delay-tolerant network routing protocols,” in Int. Conf. on Networking Systems and Security, Dhaka, pp. 1–6. [Google Scholar]
31 M. S. Islam, S. I. Thaky and M. S. Hossen. (2020). “Performance evaluation of delay-tolerant routing protocols on bangladesh map, ” in Advanced Computing and Intelligent Engineering Advances in Intelligent Systems and Computing, vol. 1089. Singapore: Springer, pp. 461–471. [Google Scholar]
32 M. I. Talukdar and M. S. Hossen. (2018). “Performance analysis of DTN routing protocols: Single-copy and multi-copy in ICMN scenario,” in Int. Conf. on Innovations in Science, Engineering and Technology, Chittagong, Bangladesh, pp. 407–411. [Google Scholar]
 | This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |