A Survey on Routing Algorithms for Opportunistic Mobile Social Networks

Ying Cai,Haochen Zhang,Yanfang Fan,Hongke Xia

Department of Computer Science and Technology,Beijing Information Science and Technology University,Beijing 100101,China

Abstract:Opportunistic Mobile Social Networks(OMSNs) are kind of Delay Tolerant Networks(DTNs) that leverage characteristics of Mobile Ad Hoc Networks(MANETs)and Social Networks,particularly the social features,to boost performance of routing algorithms.Users in OMSNs communicate to share and disseminate data to meet needs for variety of applications.Such networks have attracted tremendous attention lately due to the data transmission requirement from emerging applications such as IoT and smart city initiatives.Devices carried by human is the carrier of message transmission,so the social features of human can be used to improve the ability of data transmission.In this paper,we conduct a comparative survey on routing algorithms in OMSNs.We first analyze routing algorithms based on three social features.Since node selfishness is not really considered previously in aforementioned routing algorithms,but has significant impact on network performance,we treat node selfishness as another social feature,classify and elaborate routing algorithms based on incentive mechanism.To assess the impact of social features on routing algorithms,we conducted simulation for six routing algorithms and analyzed the simulation result.Finally,we conclude the paper with challenges on design of routing in OMSNs and point out some future research directions.

Keywords:OMSNs;routing algorithms;social features;selfishness;incentive mechanism

I.INTRODUCTION

Wi-Fi,Bluetooth,and other communication interfaces on most smart devices have brought in new ways of communications to human society and have become a key factor in developing useful networks models to complement existing telecommunications systems.OMSNs [1][2]are special kind of DTNs formed by combining the concepts and characteristics of MANETs and social networks to improve network connectivity.In OMSNs,the mobile nodes communicate by wireless communication interfaces like IEEE 802.11 or Bluetooth.Because of the mobility of nodes,the connections between nodes are intermittent and unstable.To overcome the difficulties,mobile nodes store and carry the messages,and forward them to other nodes by opportunistic encounter.With mobile devices,the users can transmit and share delaytolerant data within a certain delay bound,proactively participating network operations.Thus,OMSNs can assist existing communication networks to cope with increasing data traffic,save valuable spectrum resources for real-time data transmissions,improve data delivery ratio,and reduce data delivery delay.OMSNs attempt to leverage salient features of both MANETs and Social Networks to boost network performance by considering both opportunistic networking and social behaviors of mobile users,significantly differing from traditional MANETs.Users in OMSNs can use mobile devices to form social networks in adjacent areas to communicate and share data with each other.In addition,interest communities can be formed according to social features to communicate and share data among them more effectively.

Opportunistic communications are limited by channel variability due to various factors,such as user mobility,traffic types,and spectrum availability,and limited communication range,may result in unpredictable delays during message forwarding.Therefore,only delay-tolerant traffic is suitable for OMSNs.Compared with traditional communication networks,OMSNs pose severe challenges for data forwarding.Socievoleet al.show that Bluetooth contacts network layer and Facebook friendships network layer are similar by experiment on a campus environment.[3]Since social networks rely on the interaction among nodes,the social features of mobile devices carried by humans have significant impacts on the establishment of communications among mobile nodes.Thus,how to design effective opportunistic routing algorithms based on the social features of mobile nodes has become an active research problem.

In recent years,Social Network Analysis (SNA)[4]and its applications have also attracted many researchers to utilize it to design novel network architectures and effective routing algorithms,such as DTNs[5],Pocket Switched Networks (PSNs) [6],Opportunistic Networks (OppNets) [7],and Social Aware Networking(SANs)[8].SNA plays an important role in providing the basis for using of social features in physical networks and enhancing the performance of routing algorithms in OMSNs by utilizing the social features and node mobility patterns.A typical SNA considers several metrics to characterize the importance of nodes and their social relationships,which are called social features.Those social features are used to design effective and efficient routing algorithms in OMSNs.

In typical OMSNs,there are many social features can be utilized,includingcentrality,similarity,tie strength,popularity,closeness,cumulative contact frequency,stability,influence,social pressure measurement,and so on [2].Among all these social features,centrality,similarity and tie strength are the most widely used.Thus,we can use them to design routing algorithms with high delivery ratio,low latency and low overhead.The reason why we choose these three social features is that they are the most representative among all social features.Centrality can describe how important a single node is in the network.High centrality of a node means that the node is at the center of the network.Not like Centrality,Similarity and Tie-Strength can describe how strong the relationship is between two nodes.The difference of these two social features is that Tie-Strength directly describes the node relationship,while the Similarity indirectly describes the node relationship.These three social features cover almost everything about society that needs to be considered when designing routing algorithms.We analyze the performance of routing algorithms based on these three social features respectively,and identify the pros and cons of these routing algorithms.We also observe that many routing algorithms have not taken the node selfishness caused by the limitations on energy,storage and spectrum resources into consideration.Since node selfishness seriously affects the performance of routing algorithms,many incentive mechanisms are proposed to mitigate the impact of selfishness on the performance of routing algorithms.We classify the routing algorithms with these incentive mechanisms and describe their characteristics,pros,and cons respectively.

There are already some surveys on routing algorithms in OMSNs.Xiaet al.[2]presents a comprehensive survey for Socially Aware Networking.However,they did not classify and analyze routing algorithms according to specific social features.Zhuet al.[9]presents an excellent survey on data routing strategies in MSNs,but they have not covered the effect of selfishness on routing performance and the solutions for selfishness.Our paper intends to provide a comprehensive survey on opportunistic routing algorithms in OMSNs.We first review various routing algorithms based on the aforementioned three social features and identify the common problems in such routing algorithms.To handle the node selfishness,we classify the routing algorithms based on incentive mechanism design and elaborate their characteristics,discuss design challenges and future research directions of routing algorithms for OMSNs.Compared with current surveys,the classification method of this paper is different,and the selected articles are relatively new.

For analysis the routing algorithms more systematic,we divide the design parameters into three levels.(1) Delivery Ratio.No matter the routing algorithm based on social features or the routing algorithm with incentive mechanism,the most important consideration in designing the algorithm must be the delivery ratio,because the delivery of messages is the most basic requirement of the routing algorithm and the primary motivation of designing the routing algorithm.(2)Other macro-metrics.On the premise of improving delivery ratio,designers should consider the secondary requirements like delay and delivery cost.When routing algorithms need infrastructure such as Road Side Units (RSUs),designers should also consider the construction cost.And for the routing algorithms with incentive mechanisms,the metrics about selfishness such as the selfish node detection rate and system utility should also be considered.(3) Micrometrics.The design parameters in (1) and (2) are all from the perspective of the whole system.From the perspective of nodes,the time complexity and computational complexity of the algorithm should also be considered.These metrics are the embodiment of algorithm efficiency at the node level.Therefore,when analyzing the routing algorithms,we can consider the design parameters of the three levels in turn,so as to judge the advantages and disadvantages of the routing algorithms.

The rest of the paper is organized as follows.In Section II,we describe the selected social features and analyze the characteristics of the routing algorithms using these social features as forwarding metrics.Section III describes node selfishness and analysis the routing algorithms with incentive mechanisms.Section IV is the simulation study.In Section V,we discuss the design challenges for routing algorithms and future research directions in OMSNs.Section VI concludes this paper.

II.ROUTING ALGORITHMS BASED ON SOCIAL FEATURES

The social features play an important role in the design of routing algorithms for OMSNs.In this section,we discuss three main social features,namely,centrality,similarityandtie strengthand the correspondingly routing algorithms,and elaborate the characteristics,pros and cons among these routing algorithms.It is important to note that the “single copy” and“multiple copies” mentioned later refer to the number of messages in the network.Single-copy routing refers that the node does not copy the messages after receiving them from other nodes,but directly forwards them to the next hop node when encounter,and deletes the local copies of forwarded messages.Thus there is only a single copy of a message in the network at a time.The single-copy routing can effectively control the network overhead and prevent too many message copies from wasting system resources.Multi-copy routing refers that a node makes multiple copies according to the algorithm after receiving a message from another node and forwords them to multiple next-hop nodes.In a multi-copy routing,the delivery rate will increase to some extent due to the increase in the number of nodes that get message copies.According to the number of copies,multi-copy routing can be further divided into unlimited multi-copy routing and limited multi-copy routing.In the former,the replication of messages has no upper limit,but is distributed across the network as much as possible for higher delivery ratio.But sometimes too many copies of a message can cause network congestion and limit transmission efficiency.Limited multi-copy routing generally limits the number of replicated messages in a certain way to avoid the negative impact of too many messages on the network,and the multi-copy routing algorithm based on social features generally falls into this category.

2.1 Centrality-based Routing

In graph theory and network analysis,centralityquantifies the relative importance of a node in a graph or network (i.e.,the importance of a person in a social network).Typically,nodes with high centrality have greater ability to contact with other nodes.Three most widely used measures on centrality aredegree centrality,closeness centralityandbetweenness centralityproposed by Freeman [10][11].Degree centrality(e.g.,node degree)is the number of direct connections containing the current node [11].A node with high degree centrality is connected to many other nodes in the network.Such nodes can be regarded as popular ones with many links to other nodes.Therefore,the node occupying the center of a network can serve as a bridge for information exchange.In contrast,peripheral nodes have few or no relationships and are therefore at the edge of a network.Closeness centrality measures the inverse of the average shortest distance between current node and other nodes,which can be regarded as an indicator to measure how long it takes for information to spread from the current node to other nodes in a network [12].Betweenness centrality measures the degree to which a node is located on the path connecting other nodes,which can be regarded as a measure of the degree to which a node controls the information flow between other nodes [12].A node with high betweenness centrality can facilitate interaction between its connected nodes of a network.

BUBBLE RAP proposed by Huiet al.[13]uses k-Clique Algorithm and Weighted Network Analysis for community detection.It combines the degree centrality with community to design a two-stage routing algorithm.If a node has a message destined for another node,this node would first bubble this message up the hierarchical ranking tree using the global ranking until it reaches a node which has the same label (community)as the destination of this message.Then,the local ranking system will be used instead of the global ranking and continue to bubble up the message through the local ranking tree until the destination is reached or the message expired.This method does not require every node to know the ranking of all other nodes in the system,but just to be able to compare the ranking with the node encountered and push the message using a greedy approach.Experiments show that BUBBLE RAP can improve the forwarding efficiency significantly.As one of the classic routing algorithms,BUBBLE RAP is compared by various social based routing algorithms as a benchmark.The disadvantage is that global network information is required for centralized calculation when community detection and centrality calculation are carried out,which will cause extra cost.

Xiaoet al.[14]developed the Community aware Opportunistic Routing (CAOR),which is a single-copy routing algorithm based on community home.It transforms routing among mobile nodes into routing between communities.In CAOR,mobile nodes with common interests independently form a community,and each community has a star-shaped topology,in which the center is thecommunity home.CAOR divides the entire network into several communities with overlapping star-shaped topologies and then transforms routing into message delivery within and between these communities.It provides its nodes with anIntra-Community Centralitymetric and anInter-Community Betweenness Centralitymetric,respectively,to measure their importance in message delivery within and between these communities.Finally,the reverse Dijkstra algorithm is used to minimize the expected message delivery delay for the optimal opportunistic routing performance.Because the number of communities is much smaller than the number of nodes,the computing cost and maintenance cost for contact information extraction can be greatly reduced.

Wuet al.[15]proposed an efficient data packet iteration and transmission algorithm named EDPIT,which selects data packets via iteration,is proposed to save energy and overhead during transmission.According to the transmission characteristics of nodes,the definition of node relevance degree is proposed to measure the ability of nodes in data transmission,and the center node with better performance is selected to complete the information transmission process.By predicting the energy consumed by packet transmission,it can determine whether the remaining energy of the node meets the transmission demand before packet forwarding,so as to improve the probability of successful transmission.EDPIT can effectively remove the repeated data packets in the transmission process.The lifetime of the node will be relatively longer as the energy loss of the node will decrease due to the removal of repeated packets.Experiments show that EDPIT can effectively reduce energy consumption,improve the delivery ratio and overhead in opportunistic social networks.

Rangoet al.[16]proposed a social-based forwarding strategy for opportunistic networks that exploits both offline and online user’s social network information.Firstly a new metric for OSN edge weights based on users’OSN activity is proposed to modeling a dynamic OSN,where OSN activity is derived by both online and offline users’ behavior.Then novel routing metrics fusing users’ centrality in DSN and OSN are defined,and a novel forwarding strategy exploiting these metrics is proposed.Experiments show that the proposed strategy can improve delivery ratio and overhead ratio.

Socievoleet al.[17]proposed a Multi-layer Social Network based Routing (ML-SOR).Firstly,a multilayer network model combining the social network detected through encounters with other social networks is defined.Then,in order to select an effective forwarding node,ML-SOR measures the forwarding capability of a node when compared to an encountered node in terms of node centrality,tie strength and link prediction.Experiments show that ML-SOR can achieve good routing performance with low overhead cost.

Maet al.[18]proposed a routing algorithm to alleviate traffic congestion in two-layer networks.In this algorithm,the optimal path in physical layer is selected by considering the node degree of two layers.Lenandoet al.[19]designed Epsoc that incorporates node degree centrality into limited flooding routing.In EpSoc,the Time-to-Live(TTL)for a message is adjusted according to the degree centrality of a forwarding node,and the number of copies of a message is controlled by message blocking mechanism.Igarashi and Miyazaki[20]presented a DTN routing algorithm,which uses community and centrality to control the message forwarding at each forwarding node.Guoet al.[21]used the“gravity”and betweenness centrality of a node for collaborative routing,where the “gravity” between a pair of nodes is computed based on the distance between them and the residual energy.By using the“gravity” and betweenness centrality,the throughput can be increased,and the transmission errors can be reduced.

Since centrality captures the relative importance of nodes in a network,forwarding messages to nodes with high centrality can obviously improve data delivery ratio and reduce latency to some extent.However,centrality of nodes does not consider the social relationships between nodes.Sometimes high centrality of nodes does not necessarily mean high probability of contact with the intended destination node,as is the case when the destination node is at the edge of a network.Thus,other social features should also be considered when designing more effective opportunistic routing algorithms.

2.2 Similarity-based Routing

It is observed that social networks display high degree of transitivity.In real life,everyone has his/her own social features.Two people would have heightened probability of acquaintance if they share one common acquaintance or if they share similar hobbies,careers or geographical locations.Watts and Strogatz showed that real-world networks exhibit strong clustering or network transitivity[22].Similarity,which is a metric to characterize the grouping nodes sharing common interests or connections,was proposed and utilized in[23].

Daly and Haahr[23]leveraged the betweenness centrality and similarity to design their SimBet for message forwarding.They combined Ego Networks with SNA and considered only the local information of nodes when extracting social features.A message is forwarded to a node with high betweenness centrality and high similarity to the destination node,which can increase the successful delivery ratio.Simbet has been shown with good performance in message delivery,even close to Epidemic routing when the cost is controlled.However,its performance may be affected by potential traffic congestion at central nodes.

LABEL,proposed by Hui and Crowcroft [24],is one of the earliest routing protocols that apply social features to opportunistic routing.Assume that each node has a label to inform other nodes of its membership.When a pair of nodes meet,the node carrying the message compares their labels.If the encountered node and the destination node have the same label,the message will be forwarded to the encountered node;otherwise,the current node continues to carry the message.The disadvantage of LABEL is that the delivery ratio will be relatively low when a message can only tolerate a short delay while the distance to the destination is relatively far away.This is because it may be difficult for the source node to encounter the members from the community of the destination node when the destination node is far away.

Zhanget al.[25]applied Mobile Edge Computing(MEC) to OMSNs in order to reduce the computational pressure in routing and forwarding process and designed a corresponding routing algorithm named FRRF.This algorithm is based on fuzzy reasoning systems and information entropy and considers the movement and similarity of mobile devices to determine the transmission priority of mobile devices and compares the transmission priority between mobile devices in a network to select the best relay nodes.Specifically,in this algorithm,two mobile devices meet to collect and update their respective state information,and then unload their respective state information to the nearest vehicle with more powerful computing capability to accurately compute the comprehensive similarity between mobile devices and determine the special transmission relationship between mobile devices.Experiments show that FRRF is efficiency in energy consumption,delay,and transmission efficiency.

Linet al.[26]proposed a routing algorithm,namely cosSim,based on the cosine similarity of packets between nodes.For ease of computing,the packet sets in a network are represented as vectors.The cosine distance algorithm is used to calculate the similarity between packet data.By defining the thresholds to filter the nodes with similarity in the effective range,several relatively reliable transmission paths can be obtained.The simulation results show that the cosine similarity can effectively improve the packet delivery ratio and reduce both the transmission delay and overhead.The deficiency of this algorithm is that it routes all messages in the node as a complete packet,which will forward messages for different destinations to the same direction,causing extra cost and wasting of communication resources.

Wuet al.[27]proposed a method that characteristic interests with neighbors are selected or pushed service by users.Interest behaviors by neighbors are established with multiple values of nodes in social communication.By effectively analyzing the attribute preference of nodes in transmission process,authors define the individual preference of nodes as preference similarity,so as to measure their impact on information transmission.According to the simulation experiments,the proposed method achieves good results in accuracy selected and delivery ratio,transmission delay,and routing overhead.

Wuet al.[28]proposed a method named CRDNT to evaluate contribution by nodes,recombine communities and filter duplication nodes.The rules for node iteration are established through the relationship matrix of nodes and communities.In the light of analyzing module independence degree increment,balanced binary tree(AVL tree)is established to divide networks,the maximization module independence degree increment is selected and communities are combined.If it can not appear duplication node,the community may call Non-Overlapping community.If duplication node is found,it is determined whether the node can join the community by comparing its activity degree with the AVL tree.Experiments show that CRDNT can effectively improve delivery ratio,delay and overhead.

Guan and Wu[29]proposed a a method that effectively divides social communities according to the human activity characteristics in opportunistic networks.Effective communities and structuralization areas are established with multiple values of nodes in social communication.The established effective information transmission based on structuralization areas scheme allows information to be transmitted between resource nodes and communities.Experiments show that the network lifetime of nodes is extended and the energy consumption is reduced in the communication environment.

It is observed that most similarity-based routing algorithms assume that nodes with high similarity have higher probability of contact and data forwarding opportunity.Similarity considers social relationships between nodes and can effectively improve the routing efficiency to some extent.However,in some cases,the lack of effective mechanisms to transfer data to the center of a network may cause the decline of packet delivery ratio when the network is relatively sparse and further research is obviously needed along this line.

2.3 Tie Strength-based Routing

The centrality and similarity mentioned above have not considered the social interactions and link strength between nodes,which obviously have significant impact on the routing performamce.The tie strength,initially introduced by Granovetter [30],was to capture such impact and defined as “a combination of the amount of time,the emotional intensity,the intimacy,and the reciprocal services,which characterize a tie”.In general,ties are represented by edges/links connecting two nodes of a graph with specific weights to characterize their strengths.As discussed by Daly and Haahr[26],there are many tie strength indicators to use,including frequency,intimacy,longevity,reciprocity,recency,multiple social context and trust.A combination of several tie strength indicators can be used for information flow to determine which contact has the strongest social relationship to the destination node.Meanwhile,the effects of weak ties in social networks are also crucial for data dissemination.

Abdelkaderet al.[31]established a mathematical model for a single-copy routing algorithm assuming the existence of a global observer,which could collect information on all nodes in a network.On this basis,a Social Groups-based Routing for DTN was proposed to reduce the redundant replication of packets by using the social relationship between nodes.They argue that if two nodes in a network are in frequent contacts,they should belong to the same social group.Their social relationships with other nodes should be more and less the same.Unlike other schemes that predict the path from source to destination through nodes with strong social relationships,SGBR propagates messages by excluding nodes that do not want to add significant values to the node that carries the message.This exclusion reduces the need to collect information from the whole network and improves the routing performance.But the presence of global observer means that there are still additional costs associated with gathering information from the entire web.

Moreiraet al.[32]proposed dLife,in which the dynamic behaviors of users in daily life are modeled by using the dynamically changing social structure.Based on the assumption that the duration of node contact can be used to measure the strength of their social relationships,dLife defines the following two indicators:(1) Time-Evolving Contact Duration (TECD),which represents the evolution of social interactions between nodes;(2)TECD importance(TECDi),which is used to express the degree of a node and its social intensity with its neighbors.Experimental results based on synthetic mobility models and real human traces show that dLife has better delivery probability,latency,and cost than proposals based on social structures.

ProphSoc proposed by Alrfaayet al.[33]imporved PHoPHET by combine social features with prediction schemes.Compared with the original scheme,which only uses the contact history of nodes to measure the transmission probability,this scheme also considers the social importance and social similarity of nodes.The combination of social featues and prediction improves the effectiveness of the routing algorithm.Experimental results show that ProphSoc perform better in terms of delivary ratio,average delay and overhead compared to other methods.

Liet al.[34]proposed a data forwarding algorithm based on approachability.The mertic “approachability”consists of“space-time approachability”and“social approachability”.The former is used to measure the probability of a vehicle approaching to the destination from physical perspective,vehicle with large space-time approachability may send the messages to the destination fast.And the latter is used to measure the probability of a vehicle approaching the destination from social perspective.Simulation results on real datasets show that the performance of proposed algorithm is better than existing data forwarding algorithms.

Chen and Shen [35]designed SMART,in which each node generates its own social map.The social map includes the nodes that this node has met and the nodes that this node meets frequently,and it is used to record the social conditions for and the social relationships with each node.Social maps are not limited to a hop or two but reflect longer relay paths to help forward messages.First,the weight of each link is calculated according to the encounter frequency and closeness of two connected nodes in the social map,which reflects the probability of successful data transfer between two nodes.After that,the data is forwarded to the node with high packet delivery ratio.When two nodes meet,only the information of the first L frequently encountered nodes needs to be exchanged to construct or update the social map,where L is a design parameter.Simulations results show that SMART are more efficient than many routing algorithms such as SimBet because social maps provide a broader view of relay selections.But social maps take up storage space of the vehicles and are more likely to cause message congestion in message-intensive scenarios than other solutions.

It has been observed that many forwarding schemes based on tie strength only consider the contact frequency of nodes and ignore the impact of contact time on throughput when calculating utility.Li and Shen [36]developed SEDUM to increase throughput and reduce latency.SEDUM has three characteristics.Firstly,it considers both contact frequency and duration in the node mobility pattern of a social network.Secondly,it is a multi-copy routing algorithm,which determines the minimum number of copies of messages to be forwarded while achieving the required routing delay.In addition,it has an effective buffer management mechanism to give higher priority to messages from the buffer with longer lifetime,thereby reducing the total packet delivery delay.Experiments show that SEDUM provides high throughput and low routing delay compared to previous routing approaches.

Menget al.[37]proposed a routing method based on nodes’ relationships.The metric for detecting the quality of the relationships between nodes include the contact time,contact frequency,and contact regularity.Social network analysis is used to detect overlapping community structures and represent them as trees.The routing algorithm include intra-community routing,single-hop inter-community routing and multihop inter-community routing.Simulation results show

that the proposed method perform better than Bubble Rap and SimBet in Delivery Ratio,Average Delay,and Average Number of Hops.

Table1.Opportunistic routing algorithms based on social features.

?

In summary,the routing algorithms based on tie strength fully consider the social interactions between nodes,effectively improves the packet delivery ratio and reduces the delivery delay.

Routing algorithms based on social features and their characteristics aresummarized in Table1.Among them,“complexity” is a qualitative analysis of the time complexity and computational complexity of the routing algorithms.“Low”means less processing time and computation,“medium” means medium processing time and computation,and “High” means more processing time and computation.“Main Object”is the performance metrics that the analyzed routing algorithm mainly focuses on.For example,“Delivery Ratio+”means that one of the main object of the routing algorithm is to improve Delivery Ratio.

III.ROUTING ALGORITHMS WITH INCENTIVE MECHANISMS

All works discussed in Section II utilize different social features to design various opportunistic routing algorithms,which to some extent have already improved the performance of their respective routing algorithms and accelerated the efficiency of message delivery in OMSNs.However,they all assume that the nodes in the network cooperate unconditionally.In the real world,due to the limitations on resources such as energy,storage and bandwidth,selfish nodes are likely to exist,and hence the selfishness becomes another negative social feature that cannot be ignored in OMSNs.Node selfishness can be classified into two types:individual selfishnessandsocial selfishness.Generally,in dividual selfish nodes display consistent selfish behaviors to other nodes to increase their personal utilityand benefits[38].Another kind of selfishness comes from the social perspective.Different from individual selfishness that mobile nodes display selfish behaviors in data relay only because of limited resources,social selfish nodes will alleviate their selfishness based on their social relationships and content knowledge to achieve their social goals [39].Typically,social selfish nodes reduce the degree of cooperation with others according to their social relationships to increase their social utility.In other words,social selfish nodes provide better forwarding services to those who have strong social relationships with them such as friends and colleagues.

Most routing algorithms in OMSNs assume that mobile users cooperate and never reject services from other users.However,in fact,since the nodes in OMSNs are controlled by human users,in order to maximize their utility,the nodes tend to act selfishly,and thus some incentive mechanism is needed to stimulate the nodes to help other nodes forward messages.In recent years,some researchers have already proposed routing algorithms with incentive mechanism design to stimulate cooperation among all nodes,including selfish nodes.Existing incentive mechanisms can be classified into four categories:Tit-For-Tat (TFT) mechanism,Credit-based mechanism,Reputation-based mechanism,andgametheoretic mechanism.

3.1 Routing Algorithms with TFT-based Incentive Mechanism

In the TFT-based incentive mechanism,when two nodes forward messages to each other,the amount of data traffic forwarded by one node for the other must be equal to the amount of data traffic forwarded by the latter for the former,the actual meaning for tit-for-tat.

Shavadeet al.[40]proposed a TFT incentive mechanism consisting of “generosity” and “repentance”,which allows nodes to reward and punish their neighbors based on their observed history in the packet forwarding process.Based on the above mechanism,they developed an incentive-aware routing algorithm that allows selfish nodes to maximize their performance as long as they follow the TFT mechanism.Extensive simulation studies show that this TFT mechanism can indeed improve the packet delivery ratio.

MobiTrade,proposed by Krifaet al.[41],offers another classical TFT incentive design.In MobiTrade,a utility-driven trading system is proposed to optimize content sharing.As we observe,a simple traditional TFT mechanism can force a node to “trade one for one”,but a node in a TFT mechanism tends to demand a lot and give a little in return,which can quickly result in deadlocks when something of interest has to be acquired through the network in some way.To solve this problem,MobiTrade proposes a trading mechanism that allows nodes to purchase,store,and carry contents for other nodes so that they can later exchange contents of interest.However,MobiTrade does not consider TTL of the messages/contents.Experiments show that Mobitrade can gets higher query success rates and can successfully isolates selfish devices.

Like MobiTrade,Content Subscribing (ConSub),proposed by Zhouet al.[42],is also a TFT-based scheme designed to address the aforementioned problems.Specifically,during node contact,the order in which messages are exchanged is determined by the content index,which is calculated based on the probability of contact and the level of collaboration between the current node and the subscriber.In order to ensure the freshness of the content,they improved ConSub by considering TTL in[43].Simulation results show that ConSub can improve the delivered rate and transmission hops with reasonable transmission cost.

Compared with other algorithms,the TFT-based routing algorithms can achieve higher efficiency.However,due to highly variable network conditions and the lack of a complete end-to-end path,it is quite challenging to implement a TFT-based routing with incentive design in a network with intermittent connections such as in OMSNs and the mandatory requirement to exchange the same number of messages in TFT-based routing may result in unfair packet delivery situations.

3.2 Routing Algorithms with Credit-based Incentive Mechanism

In order to address fairness issue in TFT-based routing,virtual credit has been used to design routing algorithms with credit-based incentive mechanism.

Luet al.[44]proposed Pi,a single-copy incentive scheme,to encourage selfish nodes to cooperate in data forwarding.When a source node sends a packet,it will append some kind of incentive to the packet to attract the nodes in the network to participate in this packet forwarding to address the fairness issue.Experiments show that Pi can improve delivery ratio and average delay.

MobiCent,proposed by Chen and Chan in [45],makes use of trusted third parties to store key information for nodes and provide verification and payment services.It allows the underlying routing protocol to discover the most efficient path,and it is also incentive compatible.In MobiCent,nodes pay a fee for a forwarding service,and no node is to intentionally waste transmission opportunities or increase rewards by creating non-existent contacts.

Mzeeet al.[46]proposed the incentive mechanism,namely,MCoST,that facilitates content sharing in mobile social networks and ensures that only trusted content can be shared.This mechanism is built upon collective bidding,cost sharing and trust evaluation,and ensures the individual rationality.MCoST leverages the broadcast nature of wireless communications to enable content providers to share content with multiple users simultaneously.The content cost is collectively compensated by the content receiver through the content bidding mechanism in MCoST.Moreiver,MCoST includes a robust trust evaluation framework to ensure that content review is immutable and tamper-proof and be able to resist witch attacks and denial of service attacks,and that users cannot have multiple identities or false identities,and reject negative comments on the network.This is achieved by integrating a distributed cryptographic hash content review mechanism into the design of MCoST.Experiments show that MCoST can efficiently evaluates contents’ trustworthiness by detecting and discriminating review-chains under sybil or rejection attacks,reduces the time and cost to collect the desired contents,and improves network utilization.

Goka and Shigeno[47]designed a distributed trust and reward management system,namely,DMTR,which can effectively detect uncooperative nodes illegally dropping data packets to be forwarded.DMTR uses blockchain to manage virtual credit in P2P networks.In order to ensure that nodes propagate transactions and speed up consensus convergence over blockchains in untrusted networks,DMTR sets up mining nodes and reduces block size by modifying block structures and transactions.In DMTR,the mining node plays the role in managing the blockchain and forming multicast groups in MANETs.In addition,DMTR introduces collaborative mining to accelerate the settlement speed on the premise of ensuring security.In DMTR,the mining node generates the same block by sharing the target block,thus reducing the mining block time while keeping the total computation in check.Besides,DMTR can effectively detect non-cooperative nodes in the network through the global node reputation.When a node transmits a packet (a block) to another node,the node reports to the mining node the number of packets forwarded and dropped by its neighbors.The mining node receiving the report multicasts them to other mining nodes,makes a transaction based on the report,and calculates the global reputation.The mining nodes then start collaborative mining.When a mining node successfully completes the mining,it will multicast a block to other mining nodes.The mining node that receives the block validates the block and adds it,if passing validation test,to the blockchain.After adding the block to the blockchain,the mining node updates the blacklist according to what has been received from the blockchain and then broadcasts the blacklist.The blacklist records nodes with negative credit or bad reputation(below a predetermined threshold).Nodes in MANETs determine the behaviors of other nodes based on the blacklist.

One common feature in the routing algorithms with credit-based mechanism is the need for a centralized third party to manage payment services,which increases system costs and challenges system security.In addition,most schemes are unfair to edge nodes and inactive nodes.

3.3 Routing Algorithms with Reputationbased Incentive Mechanism

Credit can sometimes be assessed based on operational reputation in the wireless mobile networks which rely on node relay services.Active participation in providing network services will definitely earn more credit and gain higher reputation.Thus,reputationbased incentive mechanism can also be used to detect the selfish behaviors of nodes.

Based on the existing Ad hoc On-Demand Distance Vector Routing (AODV) protocol,Abiramiet al.[48]designed NCV-AODV through routing enhancement based on credit values.Here,each node maintains a new field called Neighbor Credit Table(NCT),which updates the credit values of its neighbors over time.Each time a packet is directed or sent to a neighbor,the neighbor’s credit is increased in the table.Some nodes are considered malicious because they cannot receive packets and thus have low credit.To avoid this,each node in the network sends a virtual packet to obtain a credit value in an adjacent credit table.When a node is ready to pass their forwarding packet,the node’s credit value is checked in its neighbor’s credit table.If the credit value is not enough,it discards the packet.

To improve the performance of NCV-AODV,an enhanced protocol called iNCV-AODV [49]was proposed.The assumption in iNCV-AODV is that nodes in the network are not malicious in nature,and that only new nodes may be added to the network to instill malicious intent.This type of attack is common in sensor networks,where all initially deployed sensor nodes work properly,and some new malicious nodes may be deliberately added by the adversary to launch some attacks in the network.In this mechanism,a node first initializes its neighborhood credit table by providing credit values to all its member nodes.It then updates its neighbors’credit scores throughout the network.If and only if these nodes work properly,can competitors add new nodes to the network,and the credit table is then updated with the existing nodes.If these nodes act selfishly,their credit will not be updated in their neighbor’s credit table.Therefore,no neighbor expects to forward or send any packets through these malicious nodes.Based on this assumption,the results show that the performance can be significantly improved.

Wanget al.[50]presents a routing algorithm based on reputation incentive mechanism.When a node forwards messages to other nodes and consumes its resources(e.g.energy,storageetc.),the value of the contribution function increases.Then,when two nodes meet,they will consider the other node’s contribution function to calculate the forwarding probability of the other node.The messages in buffer of the node with larger the contribution function will have a greater probability of being received in process of forwarding.Besides,a buffer management mechanism is proposed to solve the issue of extremely limited network resources can be used efficiently.The simulation results show that ARAG performs well in delivery ratio,average delay and network overhead.

Akliluet al.[51]proposed a bio-inspired rewardbased message forwarding scheme.The metrics for incentive mechanism contains credit and reputation.The scheme used Ants broadcasting method for drivers’cooperation and message forwarding.Road Side Units(RSUs)controls whether the nodes are cooperative or not and pay the nodes by reward packet.Simulation results show that the proposed scheme can stimulate the selfish nodes effectively.

Vedhavathyet al.[52]devised a three-referee incentive mechanism,which uses three referees to monitor the behaviors of any intermediate node.If any selfish behavior occurs,the packet will be bypassed by the mediation node,leaving the data transmissions in the network undisturbed.In addition.Cryptographic hashing is used instead of public key cryptosystem in data packets and acknowledgment packets to make the average packet cost lower than that for the incentive mechanism based on public key cryptosystem.Hash values are used to achieve payment non-repudiation and inhibit hitchhiking attacks.

Yuet al.[53]proposed a method for flitering information by computing trust scores based on the value of social relations.Authors calculate the value of social relations by frist screening out the available nodes according to the characteristics of nodes,calculating feature weights according to the characteristics of node characteristics and social relations transitivity.Then,the social relationship values of the flitered nodes are calculated by the weight of each feature and the nodes that satisfy the characteristics.In calculating the value of social relations,the authors consider that social relations change dynamically with time and increase the flexibility of socialrelations.In the new round of message information transmission process,according to the dynamic changes of social relations at different times,regenerate a new routing table,so that the social relationship calculation model has suffciient adaptability to the dynamic changes of the networkand improve the accuracy of the model.The experimental results show that NSFRE algorithm can effectively improve the transmission success rate,reduce transmission delay,ensure the safe and reliable transmission of information in the network,and require low buffer space and computing capacity.

The routing algorithms with reputation-based mechanism could fgiht against black hole attacks.However,in the network environments with frequent disconnections as in delay-tolerant networks,reputation may be hard to manage effectively,and packet losses due to unintended packet drops will also have a signif-i cant impact on reputation systems.Thus,how to manage trust and reputation in untrusted networks with intermittent connections such as OMSNs is still highly challenging and further research is still needed.

3.4 Routing Algorithms with Game-based Incentive Mechanism

In order to incentivize selfish nodes to participate in packet forwarding,game theory has also been explored,resulting in routing algorithms with gametheoretic incentive mechanism.

In[54],Preethiet al.proposed a Price Based Game Theory Routing (PBGTR) algorithm.In PBGTR,a node is called a player and Minimum Cost Routing Path(MCRP)is called outcome.To achieve this outcome,4 strategies,called Price based Game Theory Routing,Extract All Gateway Nodes,Routes Discovery,and Estimate Transmission Cost,are applied.Source node applies the PBGTR algorithm to stimulate selfish intermediate nodes to forward packets.In this algorithm,source offers some amount of reward to compensate intermediate nodes who forward its packets.On the other hand,each source node also wants to spend less for packet forwarding.Thus,there is a game between a source node and intermediate forwarding nodes,and PBGTR routing algorithm is to find the minimum cost routing path between source node to destination while maximizing the packet delivery ratio.

Fanet al.[55]investigated a game theoretic method based on bargaining.It is observed that routing information exchange is similar to the commodity exchange in stock market,and thus as in real life,goods can be traded from people with low valuations to people with high valuations.Similarly,a message can be transferred from the nodes with lower successful delivery probability (i.e.,the probability that the node successfully delivers the message to the destination node) to the nodes with higher successful delivery probability.With this analogy,Fanet al.proposed a incentive schemes for probabilistic routing that stimulates selfish nodes to participate.Experiments show that the proposed scheme can effective improve delivery ratio.

In hybrid wireless mobile networks(networks with or without infrastructure),Akkarajitsakulet al.[56]devised a game to send packets to mobile nodes cooperatively.When there exist selfish nodes,they developed a method for a joint game to send packets from the base station to the destination beyond the transmission range of the base station.In their scheme,mobile nodes form an alliance in which well-behaved nodeswill always agree to help others in the alliance to forward packets.It works as follows.A group of nodes decides to join or leave an alliance based on their respective benefits.The benefit of each node is a function of the average transmission delay from the base station to the node and the cost of forwarding a packet to other nodes.A Markov chain model is constructed to obtain the expected cost and packet transmission delay when the node is in the federated state (in the alliance).Since both expected cost and packet transmission delay depend on the probability that nodes helping other nodes in the same alliance forward packets successfully to target nodes in the same alliance,a bargaining game is constructed to find such optimal probability.After obtaining the benefit of each node,the solution to the alliance game can be calculated to obtain a stable alliance.Performance analysis shows that,compared with that case when a node acts alone,the node can obtain higher benefits when an alliance is formed.

Table2.Opportunistic routing algorithms with incentive mechanism.

?

Caiet al.[57]proposed an incentive-compatible routing algorithm for two-Hop DTN named ICRP based on the algorithmic game theory.It takes both the encounter probability and transmission cost into consideration to deal with the misbehaviors of selfish nodes.Moreover,the optimal sequential stopping rule and Vickrey-Clarke-Groves(VCG)auction are used as a strategy to select optimal relay nodes to ensure that nodes that honestly report their encounter probability and transmission cost can maximize their rewards.A signature scheme based on a bilinear map to prevent the malicious nodes from tampering and ensure that the selected relay nodes can receive their rewards securely.Simulation results show that ICRP can effectively stimulate nodes to forward/carry messages and achieve higher packet delivery ratio with lower transmission cost.

Behrouzet al.[39]also presented an incentive scheme called GISSO based on game theory.Different from other schemes that only focus on individual selfish nodes,GISSO focuses on how to stimulate selfish nodes socially to participate in data forwarding.First,the social benefit of each message to the intermediate node is determined according to the social relationships between the message and the strength of message attributes,and then a bargaining game is applied to maximize the benefits of both parties in the exchange of messages.Subgame-perfect equilibrium was used to show the effectiveness of the game.Moreover,GISSO was also evaluated using real data sets.The results show that GISSO overcomes the social selfishness of nodes,is superior to other routing algorithms in terms of message delivery ratio and delay,and achieves lower communication cost.

The common limitation of these four incentive mechanisms,however,is that they all assume that there are only a small number of selfish nodes in the network.If most of the nodes in the network are selfish,these incentive mechanisms will not handle well with selfish behaviors as we expect.

Table2 shows all routing algorithms with incentive mechanism with their properties and main ideas.

IV.SIMULATION STUDIES

Table3.Simulation parameters.

To assess the impact of social features on routing algorithms,we conducted a simulation experiment in the ONE (Opportunistic Networking Environment) Simulator [58]which is a commonly used simulator for DTN routings.We selected Haggle Cambridge dataset for the simulation.The dataset contains 36 iMote devices contact by Bluetooth.We simulated and compared six routing algorithms,including three social features based algorithms:BUBBLE RAP,SimBet,and EpSoc,and three benchmark algorithms:Epidemic,DirectDelivery,and FirstContact.The former three algorithms have been described and analyzed above.Epidemic routing is a flooding routing algorithm in which nodes copy information to each encounter node to reach the upper limit of transmission rate.In the DirectDelivery algorithm,the source node directly single-hopped the message to the target node to reach the lower limit of delivery cost.FirstContact is a simple aimless routing algorithm in which the node forwards the message to the first node it meets and then deletes the local copy after forwarding.The metrics selected in the simulation include Delivery Ratio,Average Delay,Average Hops and Overhead Ratio,which can help us judge the performance of the routing algorithm better.The specific simulation parameters are shown in Table3.

Figure1.Buffer size fixed,influence of message TTL change on(a)Delivery ratio;(b)Average delay;(c)Average hops;(d)Overhead ratio.

4.1 Fixed Buffer Size,Influence of Message TTL Change on Routing Algorithm Performance

In the first experiment,we studied the change of performance metrics of different routing algorithms when the nodes’Buffer Size was fixed and the message TTL changed.According to the general assumption,in a large sparse network,tiny TTL will cause messages to be discarded before reaching the destination due to expiration,leading to an unacceptable Delivery Ratio.And in a network with dense nodes or messages,huge TTL will cause message congestion,occupy the storage space and transmission channel of the node,and also lead to low Delivery Ratio.We fixed the Buffer Size at 15MB,that is,a node can store 120 messages for 128KB at the same time,and set the TTL of the messages to 12 scenarios ranging from 10 minutes to 1 week (10080 minutes).The simulation results are shown in Figure1.

Figure2.Message TTL fixed,influence of Buffer size change on(a)Delivery ratio;(b)Average delay;(c)Average hops;(d)Overhead ratio.

Figure1 shows the changes of different performance metrics of six routing algorithms when Buffer Size is fxied at 15MB and TTL is set as 10 minutes,30 minutes,1 hour,3 hours,5 hours,12 hours,1 day,1.5 days,2.5 days,3 days,4 days and 1 week.When TTL is short (≤1 day),many messages are dropped due to expiration before arriving at the destination,the performance is limited by message TTL,most of the messages that can be successfully delivered are close to the destination.It is also proved by the rapid growth of Average Hops and Overhead Ratio.As the TTL increases,more messages have a chance to be delivered,the Delivery Ratio and the Average Delay increases rapidly.Till TTL more than 1 day,the factor that limit algorithm performance has changed from TTL to the Buffer Size of nodes.Due to the excessive message generation speed(25-35s/message),and limited node Buffer Size (120 messages at the same time),plenty of messages blocking the transmission path,the single-copy routing algorithms,such as First-Contact and DirectDelivery,have much more superiority.For DirectDelivery,the messages are forwarded from source node to the destination node by single hop,so the nodes do not need to help other nodes to store-carry-forward any message.Therefore,the huge number of messages will not affect its performance.Due to the limitation of the efficiency of the algorithm itself,its Delivery Ratio finally reached 27%.Unlike DirectDelivery,FirstContact requires nodes to do the store-carry-forward process for other nodes,so its performance is limited by Buffer Size with the transmission rate remaining at 24%.Due to the strategy of unlimited flooding,Epidemic reaches the other extreme,with an undesirable Delivery Ratio (18%) and extremely high delivery costs (high Average Hops &Overhead Ratio).As an improved algorithm of Epdemic,EpSoc can maintain the Delivery Ratio(19%)in the case of message congestion,and greatly reduce the cost waste caused by unlimited flooding(50%reduction in Average Hops and 40%reduction in Overhead Ratio).This suggests that the use of social functions can have a positive impact on the performance of routing algorithms.SimBet and BUBBLE RAP are single-copy routing algorithms based on social feature,both of them reached a surprisingly low performance in this kind of message congestion environment.This situation is because that the generation of the message is too fast,even the node do not save the message copies,their buffers are still filled with different messages,resulting in the consequence that a large number of messages are directly dropped,keeping Delivery Ratio in a low level(17%).

4.2 Fixed Message TTL,Influence of Buffer Size Change on Routing Algorithm Performance

In the second experiment,we fixed the TTL of the messages to 2.5 days (3600 minutes) and set the nodes’ Buffer Size to 7 scenarios ranging from 1MB(8 messages for 128KB) to 55MB (440 messages for 128KB).The simulation results are shown in Figure2.

Figure2 shows the changes of different performance metrics of six routing algorithms when TTL is fxied at 2.5 days and Buffer Size is set as 1MB,5MB,15MB,25MB,35MB,45MB and 55MB.It can be seen that with the increase of Buffer Size,the Delivery Ratio of almost all routing algorithms keeps a relatively stable growth.For DirectDelivery,the Delivery Ratio is positively correlated with the Buffer Size when it is less than 25MB,because the source node can carry more messages generated by itself,so as to directly forward the message to the destination node.After the Buffer Size exceeds 25MB,the number of generated messages and the number of dropped messages reach a balance,and the Delivery Ratio fnially reaches 34%.The situation of other algorithms is similar to experiment (1).Due to the increase of the Buffer Size,the time of message existence in the network is longer,and the Average Delay is increased by about 50%.However,due to the fast speed of message generation,even if the Buffer Size is increased to 55MB,the performance of routing algorithms other than DirectDelivery is still limited by Buffer Size,but it is improved by about 70%.

4.3 Reduce the Limit of Buffer Size

In the first two simulations,we directly (Buffer Size)and indirectly(TTL) limited the number of messages in the network.In this section,we choose SimBet as the most disappointing routing algorithm in the first two simulations to compared with three other benchmark algorithms.The difference between this simulation and the former ones is that we adjusted the simulation parameters,weakened the limitation to the performance by Buffer Size.This kind of adjustment would help us to study how the social features influent the performance of routing algorithms.The simulation results are shown in Figure3.

As can be seen from Figure3,when the limitation of buffer size is released,the performance of SimBet is improved,surpassing the performance of FirstContact and DirectDelivery and even approximates Epidemic in terms of delivery ratio.This shows that using social features to design routing algorithms can effectively improve algorithm performance under the premise of cost control.

It can be seen from the above three simulations:

1)Generally,social features can effectively enhance performance of routing algorithms,improve message delivery efficiency and reduce delivery cost.This is because social features are abstractions of node movement patterns and node relationships,which tend to have regularity.

2) Generally,the delivery cost of single-copy routing is less than that of multi-copy routing,but the latter has more opportunities to forward messages to more nodes.Therefore,more considerations should be given to make single-copy routing efficiency close to the multi-copy ones,including more effective social metrics.

3)The buffer management strategy of nodes is very important.When there are many messages in the network,an excellent buffer management strategy should consider with social features and network information to determine the priority of message forwarding and decide which messages to drop when buffer is insufficient,so as to improve the performance of routing algorithm at peak times.

4) Different environments should be considered when designing routing algorithms.Routing algorithms that perform well in some environments may perform poorly in others.

V.CHALLENGES ON THE DESIGN OF ROUTING ALGORITHMS IN OMSNS

The performance of a routing algorithm in OMSNs depends on many aspects,including the understanding and application of different social features.There are still many problems to be solved when designing effective routing algorithms in OMSNs.In this section,we discuss design challenges and possible research directions for routing in OMSNs.

Handling Various Social FeaturesThe utility of various social features may vary greatly for different application scenarios.When designing routing algorithms,appropriate social features should be carefully selected according to specific applications and their design requirements.In order to overcome the shortcomings of using a single social feature,various social features are sometimes combined to form a new forwarding metric in a new routing algorithm.How to choose social features intelligently,how to combine them to design more effective forwarding strategy,and how to determine the weighting on each social feature become challenging but important research problems.

Figure3.Message TTL and Buffer size fixed,Simulation duration versus(a)Delivery ratio;(b)Average delay;(c)Average hops;(d)Overhead ratio.

Making Practical Tradeoffs Among Performance MetricsWhen designing routing algorithms,we may have to consider various tradeoffs among conflicting key performance indices (KPIs) (i.e.,packet delivery ratio,communications and computational overhead,packet delivery delay,etc.).For example,maximizing packet delivery ratio by increasing the number of copies of messages/packets will signifciantly increase communications overhead.Collecting network information proactively does help select relay nodes intelligently,yielding higher packet delivery ratio,but it will increase control signaling overhead with more delays,resulting in longer packet delivery delay.Therefore,the relationships among various performance metrics should be carefully investigated I order to achieve a good balance among them.

Considering More Comprehensive Performance MetricsWhen designing routing algorithms,researchers usually consider performance metrics such as delivery ratio,delivery delay,and communication overhead,among which delivery rate is the most concerned.However,the above metrics often cannot fully reflect the performance of the algorithms.Researchers should focus on more comprehensive performance indicators,such as time complexity and computing overhead.High time complexity or computing overhead of the algorithm often means that the algorithm needs to occupy more computing resources,resulting in the reduction of transmission efficiency.The more comprehensive the performance indicators are,the more efficient the routing algorithm can be designed.

Dealing with Social SelfishnessSince OMSNs rely on relaying nodes to forward packets,it is important to consider both individual and social selfishness of relaying nodes when designing routing algorithms.Several approaches have already been proposed to detect selfsih nodes in the current literature.To stimulate selfsih nodes to participate in packet forwarding,many incentive mechanisms have also been devised.However,most research works only consider the individual selfsihness.There is also another kind of selfsihness,namely,social selfsihness,which,in addition to pursuing personal utility,targets at the maximization of social utility.At present,there is not much work to study the effect of social selfsihness on performance of routing algorithms,and there are no corresponding incentive mechanisms to overcome the social selfsihness in data forwarding.Further research is in high demand.

Buffer ManagementEarly work generally assumed that the node had unlimited storage space,so there was no need to consider buffer management.However,in reality,in the peak period of communication,a large number of messages will be generated,besides some multi-copy routing algorithms will also lead to the generation of a large number of message copies.These messages (or copies) may occupy the storage space of the node for a long time,which will greatly affect the performance of message transmission on the node,and ultimately affecting the transmission eff-i ciency.Therefore,in recent years,when designing routing algorithm,buffer management will be considered to improve the effciiency of data transmission.

The simplest and traditional buffer management method are random-drop and the First-In-First-Out(FIFO).For the random-drop method,in the case of the buffer overflow,the carried messages would be dropped at random.This method is blind,no consideration of any conditions.For the FIFO method,messages that enter the buffer queue frist are dropped preferentially.This method is better than the former,but still blind.

Moreover,there are some buffer management methods discarding and scheduling decisions based on the characteristics of the message itself(such as age,hop count,message TTL,copies number,message size,etc.).Such methods can improve the transmission effciiency to some extent.For example,lower TTL or higher age means that the message may have been in the network for a long time and therefore has a better chance of being propagated so that the message can be dropped preferentially from the buffer of node.

Furthermore,some work considers the relationship between nodes and messages for buffer management.For example,the distance to the destination,the closeness or friendship with the destination node and other information related to the message across the whole network.This kind of method can effectively prevent too many messages from blocking the buffer of the node and ultimately improve the routing performance.

However,while plenty of buffer management methods already exist as mentioned above,researchers still need to design buffer management methods that appropriate for their routing algorithms when facing with large number of messages or copies,to minimize the impact of limited storage space on message transmission efficiency.

VI.CONCLUSION

OMSNs attempt to leverage salient features of both MANETs and Social Networks to boost network performance.Users do not have to establish end-to-end paths when forwarding messages by taking advantage of the opportunistic encounters among mobile nodes.In this paper,based on recent studies on OMSNs,we have analyzed various routing algorithms based on three social features,namely,centrality,similarity and tie strength and provide a comprehensive survey on opportunistic routing algorithms.Since node selfishness is not really considered previously in the aforementioned routing algorithms,but has significant impact on the network performance,we treat the node selfishness as another social metric,study the routing algorithms based on incentive mechanism,and elaborate their characteristics.To assess the impact of social features on routing algorithms,we conducted simulation experiment for six routing algorithms and analyzed the simulation result.We have also identified the design challenges and point out some future research directions.Although many works have been already carried out to improve efficiency while reducing endto-end latency in the opportunistic routing algorithms in OMSNs,we still need to explore how to leverage social features more effectively to design novel and more efficient opportunistic routing algorithms.We hope this survey could stimulate more research in opportunistic routing for OMSNs.

ACKNOWLEDGEMENT

This work was supported by National Natural Science Foundation of China(No.61672106)and Natural Science Foundation of Beijing,China(L192023).