ASurveyonRoutingAlgorithmsforOpportunisticMobileSocialNetworks.pdf资源-CSDN文库

需积分: 5 162 浏览量 2021-10-18 14:05:33 上传评论收藏 1.92MB PDF 举报

《机会性移动社交网络路由算法综述》随着物联网（IoT）和智慧城市等新兴应用对数据传输需求的不断增长，机会性移动社交网络（OMSNs）受到了广泛关注。OMSNs是延迟容忍网络（DTNs）的一种形式，它结合了移动自组网（MANETs）和社交网络的特点，特别是利用社交特性来优化路由算法的性能。在OMSNs中，用户通过共享和传播数据来满足各种应用的需求。由于这些网络中的数据传输由携带设备的人类完成，因此可以利用人类的社会特性来提升数据传输的能力。本文对OMSNs的路由算法进行了比较性的调查研究。我们分析了基于三种社会特性的路由算法：这些特征可能包括节点的社交联系强度、社区结构以及共同兴趣等。然而，节点的自私性在之前的路由算法中并未得到充分考虑，但其对网络性能的影响不容忽视。因此，我们将节点自私性视为另一种社会特性，并根据激励机制对路由算法进行分类和详细阐述。为了评估社会特性对路由算法的影响，我们对六种不同的路由算法进行了模拟实验，并对结果进行了深入分析。模拟结果显示，不同算法在考虑社会特性和自私性时，其性能表现存在显著差异。例如，某些算法可能更擅长利用强联系节点来提高数据传递效率，而其他算法则可能通过激励机制克服节点自私性，以确保网络整体的稳定性。在结论部分，我们指出了在OMSNs中设计路由算法所面临的挑战，如动态网络拓扑、节点移动性、资源限制以及自私行为的管理等。此外，我们还提出了未来的研究方向，这可能包括开发更加智能的社交感知路由策略，改进激励机制以平衡个体与整体利益，以及探索如何更好地利用社会网络信息来优化路由决策。关键词：OMSNs；路由算法；社会特性；自私性；激励机制这篇综述文章为理解OMSNs中的路由算法提供了一个全面的视角，强调了社会特性在优化数据传输中的关键作用，并对未来的研究提供了有价值的指导。通过对不同算法的比较和模拟，有助于研究人员和工程师更好地设计适应OMSNs特点的高效路由策略。

资源推荐

资源详情

资源评论

REVIEW PAPER

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

The corresponding author, email: ycai@bistu.edu.cn

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, par-

ticularly 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 tremen-

dous attention lately due to the data transmission re-

quirement 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 ﬁrst ana-

lyze routing algorithms based on three social features.

Since node selﬁshness is not really considered previ-

ously in aforementioned routing algorithms, but has

signiﬁcant impact on network performance, we treat

node selﬁshness as another social feature, classify and

elaborate routing algorithms based on incentive mech-

anism. To assess the impact of social features on rout-

ing algorithms, we conducted simulation for six rout-

ing algorithms and analyzed the simulation result. Fi-

nally, we conclude the paper with challenges on de-

sign of routing in OMSNs and point out some future

research directions.

Keywords: OMSNs; routing algorithms; social fea-

tures; selﬁshness; incentive mechanism

Received: Aug. 19, 2020

Revised: Sep. 29, 2020

Editor: Kaiping Xue

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 be-

come a key factor in developing useful networks mod-

els to complement existing telecommunications sys-

tems. OMSNs [1] [2] are special kind of DTNs

formed by combining the concepts and characteris-

tics of MANETs and social networks to improve net-

work connectivity. In OMSNs, the mobile nodes com-

municate by wireless communication interfaces like

IEEE 802.11 or Bluetooth. Because of the mobility

of nodes, the connections between nodes are intermit-

tent and unstable. To overcome the difﬁculties ,mobile

nodes store and carry the messages, and forward them

to other nodes by opportunistic encounter. With mo-

bile devices, the users can transmit and share delay-

tolerant data within a certain delay bound, proac-

tively participating network operations. Thus, OMSNs

can assist existing communication networks to cope

with increasing data trafﬁc, save valuable spectrum re-

sources 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, signiﬁcantly differing from

traditional MANETs. Users in OMSNs can use mo-

bile devices to form social networks in adjacent areas

to communicate and share data with each other. In

addition, interest communities can be formed accord-

ing to social features to communicate and share data

among them more effectively.

86 China Communication · February 2021

Opportunistic communications are limited by chan-

nel variability due to various factors, such as user

mobility, trafﬁc types, and spectrum availability, and

limited communication range, may result in unpre-

dictable delays during message forwarding. There-

fore, only delay-tolerant trafﬁc is suitable for OMSNs.

Compared with traditional communication networks,

OMSNs pose severe challenges for data forwarding.

Socievole et al.show that Bluetooth contacts network

layer and Facebook friendships network layer are sim-

ilar by experiment on a campus environment. [3] Since

social networks rely on the interaction among nodes,

the social features of mobile devices carried by hu-

mans have signiﬁcant 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 be-

come an active research problem.

In recent years, Social Network Analysis (SNA)

[4] and its applications have also attracted many re-

searchers to utilize it to design novel network architec-

tures and effective routing algorithms, such as DTNs

[5], Pocket Switched Networks (PSNs) [6], Oppor-

tunistic 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 impor-

tance of nodes and their social relationships, which are

called social features. Those social features are used

to design effective and efﬁcient routing algorithms in

OMSNs.

In typical OMSNs, there are many social features

can be utilized, including centrality, similarity, tie

strength, popularity, closeness, cumulative contact

frequency, stability, inﬂuence, social pressure mea-

surement, and so on [2]. Among all these social fea-

tures, centrality, similarity and tie strength are the most

widely used. Thus, we can use them to design rout-

ing 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 repre-

sentative among all social features. Centrality can de-

scribe 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, Sim-

ilarity 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 al-

gorithms. We analyze the performance of routing al-

gorithms based on these three social features respec-

tively, and identify the pros and cons of these rout-

ing algorithms. We also observe that many routing al-

gorithms have not taken the node selﬁshness caused

by the limitations on energy, storage and spectrum re-

sources into consideration. Since node selﬁshness se-

riously affects the performance of routing algorithms,

many incentive mechanisms are proposed to mitigate

the impact of selﬁshness on the performance of routing

algorithms. We classify the routing algorithms with

these incentive mechanisms and describe their charac-

teristics, pros, and cons respectively.

There are already some surveys on routing algo-

rithms in OMSNs. Xia et al.[2] presents a comprehen-

sive survey for Socially Aware Networking. However,

they did not classify and analyze routing algorithms

according to speciﬁc social features. Zhu et al.[9]

presents an excellent survey on data routing strategies

in MSNs, but they have not covered the effect of self-

ishness on routing performance and the solutions for

selﬁshness. Our paper intends to provide a compre-

hensive survey on opportunistic routing algorithms in

OMSNs. We ﬁrst review various routing algorithms

based on the aforementioned three social features and

identify the common problems in such routing algo-

rithms. To handle the node selﬁshness, we classify the

routing algorithms based on incentive mechanism de-

sign and elaborate their characteristics, discuss design

challenges and future research directions of routing al-

gorithms for OMSNs. Compared with current surveys,

the classiﬁcation method of this paper is different, and

the selected articles are relatively new.

For analysis the routing algorithms more system-

atic, we divide the design parameters into three lev-

els. (1) Delivery Ratio. No matter the routing al-

gorithm based on social features or the routing algo-

rithm 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

China Communication · February 2021 87

the primary motivation of designing the routing algo-

rithm. (2) Other macro-metrics. On the premise of im-

proving 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 con-

sider the construction cost. And for the routing algo-

rithms with incentive mechanisms, the metrics about

selﬁshness such as the selﬁsh node detection rate and

system utility should also be considered. (3) Micro-

metrics. 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 com-

putational complexity of the algorithm should also be

considered. These metrics are the embodiment of al-

gorithm efﬁciency 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. Sec-

tion III describes node selﬁshness and analysis the

routing algorithms with incentive mechanisms. Sec-

tion IV is the simulation study. In Section V, we dis-

cuss the design challenges for routing algorithms and

future research directions in OMSNs. Section VI con-

cludes this paper.

II. ROUTING ALGORITHMS BASED ON

SOCIAL FEATURES

The social features play an important role in the de-

sign of routing algorithms for OMSNs. In this section,

we discuss three main social features, namely, central-

ity, similarity and tie strength and 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 num-

ber of messages in the network. Single-copy routing

refers that the node does not copy the messages af-

ter receiving them from other nodes, but directly for-

wards 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 net-

work at a time. The single-copy routing can effec-

tively control the network overhead and prevent too

many message copies from wasting system resources.

Multi-copy routing refers that a node makes multi-

ple 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 in-

crease in the number of nodes that get message copies.

According to the number of copies, multi-copy rout-

ing 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 efﬁciency. 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, centrality quan-

tiﬁes 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 are degree cen-

trality, closeness centrality and betweenness central-

ity proposed 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, pe-

ripheral nodes have few or no relationships and are

therefore at the edge of a network. Closeness central-

ity measures the inverse of the average shortest dis-

tance 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 cen-

trality measures the degree to which a node is located

88 China Communication · February 2021

on the path connecting other nodes, which can be re-

garded as a measure of the degree to which a node con-

trols the information ﬂow between other nodes [12].

A node with high betweenness centrality can facilitate

interaction between its connected nodes of a network.

BUBBLE RAP proposed by Hui et al.[13] uses k-

Clique Algorithm and Weighted Network Analysis for

community detection. It combines the degree central-

ity with community to design a two-stage routing al-

gorithm. If a node has a message destined for another

node, this node would ﬁrst bubble this message up the

hierarchical ranking tree using the global ranking until

it reaches a node which has the same label (commu-

nity) as the destination of this message. Then, the local

ranking system will be used instead of the global rank-

ing 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 sys-

tem, 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 efﬁciency signiﬁ-

cantly. As one of the classic routing algorithms, BUB-

BLE 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.

Xiao et al.[14] developed the Community aware Op-

portunistic Routing (CAOR), which is a single-copy

routing algorithm based on community home. It trans-

forms routing among mobile nodes into routing be-

tween 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 the community home. CAOR di-

vides the entire network into several communities with

overlapping star-shaped topologies and then trans-

forms routing into message delivery within and be-

tween these communities. It provides its nodes with

an Intra-Community Centrality metric and an Inter-

Community Betweenness Centrality metric, respec-

tively, to measure their importance in message deliv-

ery within and between these communities. Finally,

the reverse Dijkstra algorithm is used to minimize the

expected message delivery delay for the optimal op-

portunistic 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.

Wu et al.[15] proposed an efﬁcient data packet itera-

tion 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 deﬁni-

tion 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 forward-

ing, so as to improve the probability of successful

transmission. EDPIT can effectively remove the re-

peated data packets in the transmission process. The

lifetime of the node will be relatively longer as the en-

ergy 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.

Rango et al.[16] proposed a social-based forward-

ing strategy for opportunistic networks that exploits

both ofﬂine and online user’s social network informa-

tion. Firstly a new metric for OSN edge weights based

on users’ OSN activity is proposed to modeling a dy-

namic OSN, where OSN activity is derived by both

online and ofﬂine users’ behavior. Then novel rout-

ing metrics fusing users’ centrality in DSN and OSN

are deﬁned, and a novel forwarding strategy exploit-

ing these metrics is proposed. Experiments show that

the proposed strategy can improve delivery ratio and

overhead ratio.

Socievole et al.[17] proposed a Multi-layer Social

Network based Routing (ML-SOR). Firstly, a multi-

layer network model combining the social network de-

tected through encounters with other social networks

is deﬁned. Then, in order to select an effective for-

warding node, ML-SOR measures the forwarding ca-

pability 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.

Ma et al.[18] proposed a routing algorithm to allevi-

China Communication · February 2021 89

剩余23页未读，继续阅读

评论收藏

内容反馈

Glen90

粉丝: 1
资源: 12

A Survey on Routing Algorithms for Opportunistic Mobile Social N...

最新资源

A Survey on Routing Algorithms for Opportunistic Mobile Social N...

Opportunistic Mobile Networks Advances and Applications.pdf

Mobile Social Networks_ Architectures, Social__Properties, and Key Research Challenges_【彩云小译】_【非对照】.pdf

Mobile Social Networks_ Architectures, Social__Properties, and Key Research Challenges.pdf

Network Routing Algorithms, Protocols, and Architectures.part3

Federated Learning in Mobile Edge Networks: A Comprehensive Survey .pdf

Survey_of_Randomized_Algorithms_for_Training_Neural_Networks.pdf

kayastha---Applications Architectures and Protocol Design Issues for Mobile Social Networks A Survey.pdf

Network Routing Algorithms, Protocols, and Architectures.part1

A Distributed Geo-Routing Algorithm for Wireless Sensor Networks.pdf

Network Routing Algorithms, Protocols, and Architectures.part2

Performance comparison of two on-demand routing protocols for ad hoc networks.pdf

PUB00123R1_Common-Industrial_Protocol_and_Family_of_CIP_Networks.zip

Knowledge-Embedded Routing Network for Scene Graph Generation.pdf

安全路由: Secure Routing for Mobile Ad hoc Networks

Network.Routing.Algorithms.Protocols.and.Architectures.Mar.2007.part2

Survey_of_multipath_routing_protocols_for_mobile_adhoc_networks

Cisco.Press.CCIE.Professional.Development.Routing.TCP-IP,.Volume.I.pdf

最新资源