Received 23 July 2015; accepted 27 September 2015; published 30 September 2015

ABSTRACT

Pocket switched Network (PSN) is an emerging research magnet that has been attracting researchers. This paper provides an introduction to PSN and covers some of its basic features and challenges. Continuous connectivity is difficult in infrastructure independent communication. In this paper, we will see how PSN provides an effective alternative. We also explain some routing protocols that can be incorporated for effective data forwarding. This paper also discusses possible applications and areas where PSN can be effectively used and some ideas that may foster future research in PSN routing.

Keywords:

Pocket Switched networks, Connectivity, PSN Routing protocols, Forwarding

1. Introduction

Since the beginning of Internet, TCP/IP (Transmission Control Protocol/Internet Protocol) is the most used network protocol. For years, we know Internet has been successfully connecting communicating devices worldwide. TCP/IP plays most important role for achieving this effectively. The basic principle for end to end data transfer is based on TCP/IP. But when end to end connectivity is broken or intermittent, then TCP/IP may not work properly with reliability, in many cases, it can completely fail to transfer data from source to destination. This problem occurs mainly in remote areas, or villages that lack basic infrastructure to support internet. In such circumstances, wireless communication networks which are independent of end to end connectivity between nodes can provide better result. One such solution is Pocket Switched Network (PSN). It is a fairly new research area which can work properly without specific infrastructure. PSN is independent of end to end connectivity between humans and it can provide better result in extreme environment which TCP/IP cannot handle. PSN falls into the category of another older network known as Intermittently-Connected Mobile Ad-hoc Networks (ICMANET), which is also popularly known as Delay Tolerant Network. ICMANET/DTN is one of the well-established areas in the field of wireless communication. This network architecture is proposed that can work properly with limited expectations of end to end connectivity and resources [1] . Networks under this class are potentially deployed in challenged environments using isolated mobile devices with limited resources. It is typically different from traditional mobile ad-hoc networks (MANETs). Because, in an ICMANET, paths between two nodes are intermittent and communication is established only by multi-hop paths between two nodes. That means there is no end-to-end path between nodes. DTN architecture can be applicable for interoperability between and among challenged networks (characterized by latency, bandwidth limitation, error probability, and node longevity or path stability). The concept of region and gateway are included in DTN architecture and region boundaries are used as interconnection points between dissimilar network protocols. DTN can be used to change the basic service model, system interface and poor performance presented in some networks.

As mentioned earlier, PSN falls under the category of DTN. PSN and DTN mainly differ in their information carriers. PSN employs human beings for data forwarding, while DTN utilizes any possible carrier, including human beings, to disseminate data. Nowadays, large number of mobile devices is used by people and data collected from them show that “small world” features [2] are strongly existent in them. Small world features are best described by social graph/model theories. Study shows human related network relations are less volatile and long-termed than network depending on simple node mobility. Thus for human-related extreme networking situation, there was need of more social-based DTN than any other types of DTN. From that, the need of PSN was introduced, as PSN is the only type of DTN that uses the knowledge of social characteristics to make better forwarding and routing decision.

PSN is an alternative approach to computer network architecture whose aim is to address the technical issues in heterogeneous network. PSN experience lack of continuous network connectivity and enable data transfer when mobile nodes are only intermittently connected. Since the connectivity is not expected to be consistent in PSN, it employs what is called store-carry-forward mechanism. In this, intermediate nodes carry data packet when they receive it and forward to next node as when contact is established. PSN takes the advantage of human mobility to distribute data from source to destination [3] -[5] . PSN does not require any assistance of infrastructure. That’s why PSN is applicable to rural area and developing regions to realize low cost communications. Mobile devices [6] (like mobile phones, personal digital assistances (PDAs) and laptops etc.) sometime are carried by people in some physical space with high number of nodes and contacts density. Such situation may occur that to individuals at conferences, around office spaces and in case of social communications. Networks that exist in such type of environment are examples of PSNs [7] [8] in which both mobility and multihop forwarding can be supported for communication.

In this paper, we discussed about different features and challenges of PSN routing. We also discussed different possible applications of PSN and different categories of PSN routing protocols. Finally this paper focuses some ideas that may foster future research in PSN routing.

2. Features of PSN

PSN takes the advantages of both human mobility and also intra-networks or internetworks to transfer data. PSN has been created to provide network services for mobile users in such places where they are localized truly between Islands of connectivity.

There is huge amount of portable devices such as laptops, PDAs and mobile phones, active on localized wireless bandwidth (like Bluetooth), storage capacity and CPU power. The only resource needed to run this portable device is power. With first development of power engineering and advancement in battery technologies, once charged it is possible for portable device to last for a week, while remaining in constant network contact. We expect that this innovation will continue, allowing devices to participate in wireless networks while minimizing power consumption. In case of increasing the rate of successful forwarding in PSN, data may travel through via multiple nodes. With development of technology memory has become cheap and accessible for all. However, in PSN nodes do not only carry their own message but store-carry-forward other nodes’ messages as well. So, efficient memory management is a necessity here.

In this type of network, nodes may be mobile or fixed devices within a certain location [9] like a computer with blue tooth, a laptop with a Wi-Fi network, a mobile phone etc. Nodes usually refer to any network enabled component that has the property of receiving and forwarding messages. The main objective of PSN is to make the use of every communication opportunity, and the physical mobility of the devices for transporting data from the source to destinations in situation where there might not be any base station or central hub. Some features of PSN problem space are described as follows.

2.1. Store-Carry-Forward Approach

In PSN, network links may be disrupted for a long time, therefore end to end paths are assumed not to exist. That’s why store-carry-forward mechanism is the main mechanism for data delivery and main-objective of routing to achieve maximum delivery ratio.

This mechanism’s is a real life analogy is postal service. In postal service letters are passed through several post offices, then they are processed and finally forward to their desire destination. This store-carry-forward method works similar to the concept of postal services. In store-carry-forward mechanism message or a chunk of message is forwarded and store in the nodes until it successfully reached to its desire destination.

Figure 1 shows a graphical representation of store-carry-forward approach and also shows how message or a chunk of message is propagated through a network. In this figure, the circle represents a node and the box represents its storage capability. So in Figure 1, each node is relaying its messages to its desire destination and also has storage to store message or a chunk of message, until the message/messages has reached its destination or the node has meet another suitable node.

2.2. User Mobility

Human mobility plays a key role in PSN. Mobility gives rise to new localized opportunities. User mobility also increases the use of network bandwidth as large amount of data needs to be carried around the network. The probability of node mobility is measured by using different mobility model. Some of the models are briefly discussed below:

1) Random waypoint model [10] is one of the most popular models of this category. In Random waypoint model, a node randomly chooses destination (waypoint) and moves towards the destination. In this model nodes are distributed over the simulation area randomly and they stop for a constant time. After the completion of waiting period each node chooses a waypoint (destination). Random waypoint model is used to simulate of wireless communication networks for humans and also used to represent cellular structured network. Other different approaches like the random-direction model [11] , random-border model [12] , and the modified-random- direction model [11] are various type of fully random movement with different node density distributions.

2) There are also different categories of mobility models [13] . Like, Manhattan-grid model [14] where initially nodes are randomly distributed on the streets (total simulation area is divided into several square blocks named as streets). Each node chooses a direction and a velocity. If a node reaches a corner, then the node changes direction with a certain probability. The velocity of node is also changed over time.

3) Obstacle mobility model [15] [16] is another mobility model that use Voronoi-diagrams to determine optimal path. The movement using this model is more realistic, but there is still no movement on optimal paths.

4) Reference-point-group-mobility model (RPGM) [17] models the movement of groups of nodes according to an arbitrary mobility model. According to this model, the actual position of a node is a random movement vector added to the position of node’s reference point that is assigned to it. According to the arbitrary mobility model, the actual position of the node’s reference point may change but the relative positions of the reference point inside a group do not change.

5) Clustered-mobility [18] is a mobility model that follows random based movement and uses similar approach

as random waypoint model. The difference is that the attraction of a point depends on the amount of nodes nearby. This model is applicable in different tactical scenarios.

6) Gauss-Markov model [19] is another example of mobility model. According to this model node’s velocity and direction of the future depend on the current value. The new values are chosen based on a first order autoregressive process.

7) Smooth-random model [20] [21] is a mobility model where nodes are classified concerning their maximum velocity, preferred velocity, maximum acceleration, and deceleration. Velocity and direction may also be chosen by correlation among each other. By doing so, more realistic movements may be realized.

8) The area-graph-based mobility model [22] realizes sub-areas with higher node density. This model also realizes paths between higher node density and lower node density. The sub-areas are considered as vertices of the area graph and the paths are considered as edges. A weight or probability is assigned to each edge. A node moves inside the sub-area for a randomly chosen time according to the random-waypoint model. After this time, node chooses one path according to probabilities at the edges. Next, the node moves on the path to the next area.

9) There are some mobility models that can be applicable on social networks. The social-network-founded mobility model [23] is one of them. This model is based on interaction indicators among all pairs of nodes. If a node has larger interaction indicator, then the probability of social relationship of the node becomes high. Firstly, according to the nodes interaction indicator, they are grouped in clouds. Nodes are moved inside the clouds according to a random waypoint model where the waypoints are chosen according to the interaction indicators. Community based mobility model [24] is used for the classification of the nodes into groups and their movement inside the clouds.

Due to mobility of nodes, forwarding paths becomes unpredictable and probability of mobile reach ability becomes highly dynamic, thus mobility introduces new challenge to PSN.

2.3. Opportunistic Networking

Opportunistic networks are a very promising networking field. In opportunistic networks nodes build a self-or- ganizing ad hoc network without requiring any pre-existing infrastructure [25] [26] . In opportunistic networking, nodes opportunistically exploit these contacts with other nodes to exchange messages to the appropriate destination. In opportunistic network nodes are able to make communication with each other even if there is no route exists to connect them and also collaborate them to exchange data from the source to destination [27] .

Figure 2 shows the basic structure of an opportunistic network. As movements in PSN are not pre-defined thus a neighbor is met is only by chance and collaboration can happen only as opportunity arises. In this type of network, at first a node has to find a neighbor node for starting collaboration. Then they start to exchange data. Nodes pass data to its neighbor node that it has discovered. Data is distributed among all nodes through information sprinkler. Information sprinkler [9] is a dedicated node, which is less likely to be mobile and works like any other opportunistic network nodes. It uses data sharing protocol. The information sprinkler can collect information from other nodes whenever these neighboring ,nodes belonging to sprinkler’s community or any other community, approaches the sprinkler and then the sprinkler distribute the information to other information sprinkler within a short time period. That means in this opportunistic network messages are distributed hop by hop towards the destination.

In case of data forwarding in PSNs, internetwork links are crucial. Both the intranetworking and internetworking opportunities allows PSNs to provide highly robust networking for users, to transfer data. That means

opportunistic networking allow users to make communications with each other in such unavoidable circumstances and also use physical movement of the user to transfer important messages.

2.4. Social Properties

As already mentioned earlier, small world features or social properties are strongly evident in PSN [2] . This is because, PSN comprises of human and humans happen to be social being, one such social nature is the ability to form social graph from the data obtained through PSN. A social graph is a global map which shows how nodes are connected. It is also gives insight to many other social metrics like friendship, community, centrality and modularity. Most of these terms can be found in the work on graph theory by Girvan and Newman et al. [28] . Some definition of common social properties found in PSN is described briefly below:

1) For PSN social graphs, each vertex represent a person carrying device and each edge represents frequency of interaction between these devices.

2) Centrality is the measure of how important a node is or how a node can helps connect other nodes in the graph. A node with high centrality value represents a strongly interacting node, which can be a good candidate for being data carrier to other nodes. For example betweenness centrality of a node measures the number of shortest path passing through it. Higher the betweenness centrality value, better bridging node it is for data exchanging purpose.

3) Similarity value can also be found through social graph. Similarity is the measure of number of common neighbor between individual nodes.

4) Friendship is another concept from sociology which refers to personal relationship between individual nodes.

5) Modularity which is a function that calculates the quality of newly formed communities within a network. In that process community formation, modularity can be used to decide whether to further divide a network into newer communities or to keep it as it is.

3. Challenges of PSN Routing

PSN can be defined as a communication paradigm that can take the advantages of human mobility and intranetwork or internetwork connectivity. As continuous end to end connectivity is absent so successful delivery of data becomes difficult. Here in this section we will discuss about some challenges which we may face in successfully deployment PSNs. These challenges are also beacons for researcher, willing to improve PSN, to work on.

3.1. Mobility

PSNs are formed of human communities. So it must include mobility. That means node mobility is an important issue in PSN. In PSN, it is difficult to build end to end paths for delivering message from source to destination, because user’s undefined mobility is an issue here. Due to the node mobility, it becomes unpredictable to meet a node with other nodes in the network. That’s why continuous end to end connectivity is hardly possible. That means, routing in such network means finding temporal path between sources to destination [29] , but finding an efficient path between sources to destination, i.e. successful routing of data without proper knowledge about the dynamic network topology, is a difficult task [30] .

3.2. Selfishness

As PSN is formed by human beings and they are selfish in nature. Human operated devices forming a PSN may not be willing to forward data for others, except their own desired destinations. PSN’s store-carry-forward nature requires nodes to be willing to carry other’s data but the presence of selfish nodes causing a great challenge in successful data transmission. So, necessary mechanisms should be employed to encourage the node to forward data and get rid of their selfish behaviors.

3.3. Data Forwarding

In PSN data forwarding are occurred based on some policy, as it supports both of intranetworking and internetworking. In the case of local connectivity, nodes forward messages according to the knowledge of their local environment. But to acquire accurate knowledge about the entire local environment is a key challenge because PSN is independent of any predefined infrastructure. As PSN has some limitation on resources, so availability of storage and energy are also the key challenges here.

In PSN, data are forwarded to the carrier nodes that are close to destination. But the main challenge is in the development of a method that will appropriately determine a carrier node, which will provide good forwarding opportunities to the destination, for a given message.

When global connectivity is available, a node forward messages directly to other suitable nodes that are globally connected. Finding which nodes are globally more strongly connected is also a challenge in volatile dynamic infrastructure-less network environment.

3.4. Security

In PSN routing take place by the collaboration, dependency and cooperation among nodes. Nodes have to collect and exchange messages among themselves. In that case, nodes may face different security issues. As messages are exchanged among number of nodes, so it may be altered, affected or modified by a malicious relay [31] . On the other hand, some other security problem may occur such as redirection, eavesdropping, denial of service, fabrication, poisoning etc. So incentive mechanism, like those found in [32] for Wireless Sensor Network, should also be developed for secure and safe delivery of messages and for preserving user’s privacy in PSN.

3.5. Scalability & Clustering

Most of the routing protocols in PSN are flat. This flat approach is suitable for small network but is not scalable. In this case, clustering may provide a better result that can make groups among the mobile nodes with similar mobility pattern into same cluster. So, nodes belonging to same cluster can help each other to reduce overhead, make routing scalable and also share of resources. Clustering approaches can be useful to unfold large networks into different communities [33] . In order to uncover overlapping nodes in complex networks, clustering approach based on particle walking and competing with each other by using random deterministic movement [34] can be used. Another type of clustering technique is discussed in the paper LABEL [35] . According to LABEL, each node within a community is assumed to have a label that informs other nodes about its label. It provides proper knowledge about the communities to forward messages from source to destination and significantly improve the forwarding efficiencies. Overall clustering is a very important field that has lot of scopes to research on. It is undoubtedly an important open issue for future work in PSN.

3.6. Energy and Storage Management

Mobile devices that are carried by human beings have very limited energy and storage capacity. For rapid and reliable data transmission it becomes unreasonable to utilize large amount of storage and energy. Existing PSN routing protocols do not consider low energy consumption and low storage space in their design objectives. These energy and storage management can be an effective metric to evaluate routing in PSN.

4. Applications of PSN

The main objective of PSN is to survive complex and challenging network environment. This includes surviving hardware failure as well as software or protocol failures. As PSN do not require the assistance of any infrastructure, they are applicable in rural and developing regions to allow low cost communication. PSNs can provide efficient communication in place where internet connectivity has disrupted due to infrastructure fails. Some applications of PSN are given below.

4.1. Remote Communication

There are many rural communication projects in remote villages to provide the access to Internet. Some of which is try to reduce the cost of communications using the way of asynchronous information transmission. For example, Wizzy digital courier service¹ provides Internet access for some village schools in South Africa. DAKNET [36] project focused on providing low cost Internet services to the rural areas of India. It is suggested the use of physical means for delivering messages to areas which are not connected via traditional networks.

4.2. Disaster Managements

There are some models that are used for security and disaster communication, search and rescue communication. For example, post disaster mobility model [37] is used for this purpose. This model includes the impact of disasters on the transportation network and models for human and relief vehicle movement.

4.3 Social Network Analysis

PSN can be used for analyzing social network. Many research areas, starting from anthropology to E-commerce to engineering, need social network analysis [38] . As PSN deals with people, it can be used to collect data among social entities and then use them to further understand implications, relationships and patterns among peoples, which then can be used to develop new applications for different usages.

4.4. Disease Detection

These days using PSN to understand how epidemic diseases spread is a common tool in the field of epidemiology. PSN helps to track people to collect data for understanding disease, as simple as Flo to deadly as HIV, is spread. One such work is done by Hashemian et al. [39] .

4.5. Community Detection

Community detection is a very common use of PSN. From the data collected using PSN, communities having higher modularity are often grouped together. Works that have done this are refereed in [40] and [41] . Another application of community detection through data tracking using PSN could be used to detect terrorist movement in inhabited jungles or deserts. Another use of Community detection through PSN could be to provide secure access control in social network by finding groups of people who help to spread spams in social network. Such work is done by Grier et al. [42] .

5. Routing Protocols of PSN

Different routing protocols are already proposed for PSN in order to, successful delivery of data. Some popular PSN routing protocols are categorized and discussed briefly below.

5.1. Flooding Based Protocol

Flooding based protocol is one of the categories of routing protocol used in DTNs, passed down to PSN. Epidemic routing [43] falls in the category of flooding based protocol. This protocol mainly work based on the replication of messages. Messages are distributed to every node present in the network, with an aim for messages eventually reached their destination. Epidemic routing protocol guaranteed successful transmission of messages. The main benefit of this routing protocol is that it has low latency in case of message delivery. This protocol increases the overhead drastically in terms of traffic congestion and energy. Different versions of the epidemic routing protocol [44] [45] have also been proposed in order to reduce message overhead by considering different constraints such as time limit, maximum hop count, forwarding probability, or applying different techniques to inform nodes about the successful delivery of the message. Another benefit of flooding based protocol is that it does not require any prior local or global knowledge about the network. In this protocol messages are continuously replicated to every node in the network that results high overhead, consumption of energy and traffic congestions.

Flooding based protocol can also be based on tree structure [46] . Here the decision of how to make copies of message and ensuring the number of copies of message is an important issue. Two hop relay [46] is another category of flooding based protocol. According to this protocol, if there are n nodes around the source are directly connected to the source node, then n copies of message are generated to the source and transmitted to those nodes. Spray and Wait [47] routing protocol is an example of variation in this category. According to this protocol in spray phase a number of message copies are forwarded by the source node to the same number of other nodes (known as relays). In wait phase of this protocol, if destination is not found in the spraying phase each of the nodes carrying a message copy will forward the message only to its destination.

These protocols can provide better result with respect to average message delivery delay but at the cost of huge number of transmissions per message delivered. Flood based protocols are simple to implement in order to achieve good performance.

5.2. Direct Pass

Direct Delivery Routing [48] protocol falls in the category of direct pass. It is the simplest protocol to transmit message or a chunk to its desire destination.

In this protocol a node called as source node will deliver message only to destination node is encountered by it. So direct communication between source and destination node is necessary for successful delivery of message. No relay node is necessary here for successful delivery of message between source node and destination node. Here, in Figure 3, we can see a graphical representation of direct delivery routing approach. In this figure, node A has a message to deliver and according to the direct pass approach when node A encounter the desire destination then it will deliver the message.

This routing protocol always selects the direct path for message delivery between source and destination. Direct delivery routing protocol does not require any information about the network. Because of this simplicity, this protocol does not need to consume too many resources. However this direct delivery routing protocol only works, when source node and destination node comes into direct contact with each other and is accompanied by huge delay.

First Contact Routing [48] is another type of direct pass routing protocol. In this protocol the relay node that come to first contact to the source node work cooperatively to increase the probability of successful message delivery. First contact routing approach also increases the use of bandwidth and storage. It has same advantages and limitations of direct pass routing algorithm.

5.3. Probabilistic Model Based Protocol

Probabilistic model based protocol is another category of routing protocol that is effectively used in PSN. PROPHET [49] routing protocol is a popular example of this category. This protocol is mainly proposed in order to increase the delivery probability in a social network. According to PROPHET if a node visits the same place several times, then there is a probability to repeat this in future. In this protocol each node uses a metric called probabilistic metric in order to deliver message to a reliable node. When two nodes meet, they exchange their stored information which contains delivery probability and encounter related information. Here the probability of message delivery can be calculated by using transitive delivery probabilities. When node i and node j meet one another and their elapsed time unit is k then the delivery probability can represented by the Equation (1) below:

(1)

In this protocol forwarding decision is made based on the delivery probability and a message is delivered to a node with high delivery probability to reach the destination. PROPHET has lower overhead, small use of storage space, reduce power consumption and also increase the probability to deliver message to its desire destination than routing protocols of other categories. But in PROPHET average delay is increased to deliver a message from the source to destination. In this protocol forwarding decision is made based on the delivery probability and a message is delivered to a node with high delivery probability to reach the destination.

A similar probabilistic approach is proposed [50] to improve the performance of PROPHET routing protocol. This approach is based on predictability concept to remove message delivery delay and number of message drop. In this approach, an improvement factor is included in the probability calculation equation of PROPHET in order to improve the above mentioned factors.

MaxProp [51] routing protocol calculate the maximum probability of messages to be delivered. Messages in the buffer are prioritized. In this protocol the hop count value is lower and probability set is higher. According to this protocol the priority of packet is determined by calculating the probability of nodes meeting when hop count value exceeds the threshold value.

Plankton [52] routing algorithm also falls in this category. It is possible to improve routing performance in such type of network by controlling through message replication based on reliable contact prediction. Plankton considers two key ideas to predict contacts. Firstly, it classified the communication links into weak link or strong link. This classification is based on how successful a message is delivered to its desire destination using links. Secondly, strong links are identified based on the associative relationships that are observed in different time. In order to deliver a message it firstly assigns an initial replica quota and target delivery probability. Plankton controls message replication when message is duplicated to a node that has high contact probability or high delivery probability. Plankton reduces overhead by controlling replicas and also estimates contact probability in order to improve routing performance. It also dynamically adjust replication quota by estimating contact probabilities and delivery probabilities.

Context-Aware Adaptive Routing (CAR) [53] uses prediction to allow efficient routing. If a host want to send message to any other host it uses a Kalman Filter prediction [54] and multi-criteria decision theory [55] to choose the best next carrier for the message. Kalman Filter prediction techniques were originally developed based on automatic control systems theory and used in CAR to achieve more realistic prediction of the evolution of the context of a host and to optimize bandwidth usage. Multi-criteria decision theory is used to estimate overall delivery probability. According to CAR if both sender and receiver are in the same region of network then forwarding path is determined by synchronous routing protocol. If a message cannot be delivered synchronously then the best carrier for a message is chosen based on calculating the highest delivery probability that is synthesized locally context information. CAR reduces overhead in terms of the number of messages sent and can provide good performance. In dynamic environments, as the number of undetected nodes increases, the overall predictability level increases. This is a limitation of this protocol.

5.4. Social Network Based Protocol

Social Network based protocol is another category of routing protocol. Social network based protocol focuses mainly on social network features of humans for making routing decisions. Social structure helps to build forwarding paths, allowing two nodes to communicate over time using opportunistic contacts and intermediate nodes [56] . Human belongs to different communities’ altogether make human society. This concept is used to build different type of social network based protocol. Routing of messages among different nodes (any network component that has the ability to receive and forward message) in PSN is occurred by detecting community structures throughout the network. Routing protocols that take this human community concept into consideration are fall in the category of social network based protocol.

Bubble-Rap [57] protocol falls in this category. It considers social network for making forwarding decision. In Bubble-Rap there are two important metrics through which nodes of the network is ranked. These two metrics are local ranking and global ranking. Local ranking of individual nodes means the popularity of the node within its own community. Global ranking indicates the popularity of an individual node within the whole network. Bubble-Rap protocol works based on two assumptions and these are: each node must belong to at least one community and each node must have a global ranking and also a local ranking. According to Bubble-Rap if the source node and destination node are in the same community, then firstly it checks whether the encountered node is also in the same community, if so the local ranking of the source node and encountered node is checked and if the local rank of encountered node is greater than the local rank of source node then the message is forwarded. If the source node and destination node are not in the same community, then this routing protocol is forwarded to the encountered node if the encountered node is in the same community of the destination node or if the global ranking of encountered node is higher.

Figure 4 shows an illustration of Bubble Rap forwarding from source (S) to destination (D). Here, source (S) and destination (D) nodes are specified by black color. On the other hand, black and green arrows show the Bubble Rap operations based on global centrality in global community and local centrality in D’s community respectively.

Lobby Influence [58] is also fall in the category of social network based routing protocol. In this protocol message forwarding decision is made by considering the local and global popularity of the nodes and their lobby index. Lobby index is measured by the strength of the relationship with neighbor nodes. Lobby influence protocol allows more popular nodes to forward message to the less popular node that has high lobby index in the network. Lobby Influence protocol is an enhanced work of Bubble-Rap protocol. The main difference between these two protocols is in their forwarding decision. As we discussed earlier Bubble-Rap takes forwarding decision based on the node popularity. On the other hand, the forwarding decision of Lobby Influence depends not only on node popularity but also on Lobby index.

In this protocol there is consider three assumptions and they are:

1) Each node must have a label and must associate with at least one community;

2) Each node has one global rank and one local rank to identify global and local centrality. But a node may have multiple local ranks and multiple label;

3) Each node has its lobby index that indicates the strength of the relationship with its neighbors.

This protocol increase the probability of message delivery and at the same time decreases the overhead of more popular nodes. Another similar work that builds on [57] is discussed in [59] and this focuses on betweenness centrality value to enhance Bubble-rap’s global routing decision.

Another social network based routing protocol is SimBet [60] . According to this protocol when two nodes meet one another, they are compared with one another by using SimBet utility. SimBet utility is a combination of similarity utility and betweenness utility. Similarity utility means number of common neighbors between a node and the destination. On the other hand, betweenness means number of indirectly connected nodes one node can link. That means these utilities can be estimated by the statistics of the direct links between itself and other nodes in the network. When two nodes meet they exchange their contact information with other and then determine SimBet utility to destination node. As a result the number of node and amount of exchanged data are proportionally increased. In SimBet routing, when node n, carrying a message for destination d, meets node m, n calculates betweenness and similarity value of node m. The functions used for calculating Similarity is shown in Equation (2) and Betweenness centrality are given in Equation (3) below:

(2)

(3)

PRO [61] profile based routing protocol is another example of social network based protocol. PRO use community structure of social network, in order to cover maximum number of community to reach the destination.

In PRO, nodes that belong to the same community are called as local neighbors and nodes that are connected to other community is called as remote neighbors. PRO works through the regularity of inter-contact events between nodes. This regularity is measured in terms of meeting duration and number of meeting between nodes. In PRO each node maintain a local observation table which keep track of periodic inter contact events and updates

the observation score. Observation score can be defined as a metric that indicate the probability of observing a node periodically. In case of forwarding PRO gives priority to the observation score. The nodes that observe the destination node regularly are more suitable candidates for forwarding directly to destination.PRO also checks the information dissemination score of nodes in the communication range. If the current nodes encounter another node, which is known as candidate node, having higher information dissemination score than the internal threshold score of the current node, then the message is forwarded to the candidate node. PRO also controls the number of copies for each message that can be forwarded by single node which is known as Forwarding-Quota.

PRO achieve fast and efficient routing in intermittently connected PSNs. That means PRO has low-delivery- latency and low-message-overhead. PRO is also self-learning, completely decentralized and local to nodes but sometime it can be costly.

CAS [62] Community-based Adaptive Spray routing protocol is also falls in this category. This protocol mainly based on two aspects, firstly, this protocol select the intermediate nodes that are closest to destination and secondly, it dynamically control the number of message copies according to taking into consideration the time-to-live of a message. According to the community graph firstly this protocol finds the shortest path to destination. In order to find gateway node gateway table is used here. The gateway table contains community ID, gateway node ID, the ID of the community that is connected by the gateway node, average inter contact time between gateway node and community and also a timestamp of last update of the table. Then optimal number of message copies needed to route is calculated. The gateway node is set as an intermediate target node and route specific number of messages. If the gateway node is the destination node then the process is ended. According to CAS, if a node is carried message of L > 1 (L is the number of message copies permitted to route the message to the intermediate target node) copies and encounters another node, then it checks whether this encountered node is inside its community. If they are in the same community, then it checks whether this encounter node is the intermediate target node. If so then the message is forwarded to the encountered node. Otherwise, L/2 copies of message are forwarded to the encountered node and the remaining copies of message is kept by the source node. If they are in different community then it checks whether the encountered node is the destination node, if so then copies of message is forwarded to the encountered node. The main goal of improving routing performance is to increase the delivery ratio and minimize resource consumption. In order to achieve this goal Community based adaptive spray (CAS) considers both of the mobility pattern and time-to-live of message. According to this time-to-live CAS dynamically control the number of message copies.

SANE [63] social-aware stateless forwarding is also an example of social network based protocol. In case of routing in PSN, SANE takes the advantage of both social aware and stateless approaches. SANE supports two communication services unicast and interest-cast. According to interest-cast a message should be forwarded to individuals whose interest profile closely resembles to destination. That means according to this service a user can communicate certain information to the maximum possible number of interested users, within a certain period of time. According to SANE a message has a header that contains a target interest profile, which is also known as message relevance profiles, this is an integer value that represents the number of replicas of the message that is allowed to a node to forward to other nodes and a time-to-live value. In human society individuals with similar interests often meet one another than individuals with reverse interest. This concept is used in SANE and then according to the above observation social-aware and stateless forwarding mechanism is designed.

Friendship based routing [64] is a social network based routing protocol in which forwarding decisions of messages are made based on temporally differentiated friendships. This protocol firstly identifies accurately the relations between nodes by considering a metric named social pressure metric (SPM) that motivate friends to meet to share their experiences. SPM considers three behavioral features of close friendship high frequency, longevity and regularity. Secondly, Local community is formatted by considering link qualities from nodes contact history. A node can define a community as a set of nodes with link quality itself larger than a threshold. This community will include only direct friends. But two nodes that are not directly close friends still can be close indirect friends. So finally, this protocol identifies the way of handling temporal differentiations of node relations by allowing different friendship communities in different periods. In case of forwarding, if a node i has a message for noded and meets with node j. Then i forwards the message to j if and only if j and d’s current friendship community is same and j is a stronger friend of d than i. i will not forward the message , if j and d are not in the same friendship community but j has better link with d. This protocol can achieve better delivery ratio without maximizing the cost compared to other protocols. As this protocol allows different friendship communities in different period, it may require more space and that can increase cost.

In order to increase the performance of social network based protocols in large scale networks community aware framework (CAF) [65] can be used. CAF can be easily integrated with some of these social network based algorithms. This framework extension relies on the fact that social forwarding algorithms normally operates within the same sub-community. Here particular nodes are defined as MultiHomed (MH) nodes (nodes that belong to multiple sub communities) that circulate the message to other sub-communities. These MH nodes are ranked by the number of sub-communities they belong to (MHrank). CAF mainly relies on local social/contact information to predict future transfer opportunities. By integrating CAF with forwarding algorithm may increase delivery ratio, but sometime it can be costly.

6. Conclusions

In this article, we have discussed about basic features, challenges, routing protocols of different categories of PSN. We also focus on some open issues that may foster future research in PSN. This paper was written keeping in focus to introduce newcomer researchers to PSN and its routing protocols.

PSN becomes an important emerging facet of modern day networking. TCP/IP protocol is not suitable for modern day networking in extreme scenarios because it requires end to end connectivity. On the other hand, PSN takes the advantage of both human mobility and intranet/internet communication opportunities. PSN also does not require any end to end connectivity. PSN is mostly applicable in modern social networks where contacts are intermittent and challenged network conditions like disaster communication, search and rescue communication. PSN has also some challenges that are already discussed above. Table 1 provides an overall summary of routing protocols that we have discussed in this work.

Our experience shows that security implementation remains one of the biggest challenges in PSN. As the data transfers are intermittent and data may end up with relay node for a longer period of time. So security of data should be maintained properly. While making this study, we have seen that merging multiple metrics of different protocols together can improve routing performance of PSN. However, care must be while merging as

no general guaranteed rule is there and like any other ad-hoc network, PSN is also application-specific. Overall, it’s an interesting research challenge to decide how to smartly incorporate ideas of different categories of PSN together to come up with a hybrid category.

Acknowledgements

We want to acknowledge BRAC University for allowing us to put this work together. The authors are grateful to the reviewers and the Editor of this journal for their time and valuable comments.

Cite this paper

Ratna R.Sarkar,KhadijaRasul,AmitabhaChakrabarty, (2015) Survey on Routing in Pocket Switched Network. Wireless Sensor Network,07,113-128. doi: 10.4236/wsn.2015.79010

References

NOTES

¹Wizzy digital courier. http://agln.aspeninstitute.org/projects/wizzy-digital-courier