基于社区的总线系统作为车载AdHoc网络的路由骨干网资源-CSDN文库

需积分: 5 140 浏览量 2021-04-29 20:34:30 上传评论收藏 4.05MB PDF 举报

资源推荐

资源详情

资源评论

Community-based Bus System as Routing Backbone

for Vehicular Ad Hoc Networks

Fusang Zhang

∗†‡

, Hai Liu

‡

, Yiu-Wing Leung

‡

, Xiaowen Chu

‡

and Beihong Jin

∗§

∗

State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

†

University of Chinese Academy of Sciences

‡

Dept of Computer Science, Hong Kong Baptist University

Abstract—Low delivery latency and high delivery ratio are

two key goals in the design of routing schemes in Vehicular Ad

Hoc Networks (VANETs). The existing routing schemes utilize

real-time information (e.g., geographical position and vehicle

density) and historical information (e.g., contacts of vehicles),

which usually suffer from a long delivery latency and a low

delivery ratio. Inspired by the unique features of bus systems such

as wide coverage, ﬁxed routes and regular service, we propose

to use the bus systems as routing backbones of VANETs. In this

work, we present a Community-based Bus System (CBS) which

consists of two components: a community-based backbone and

a routing scheme over the backbone. We collect real traces of

2515 buses in Beijing and build a community-based backbone

by applying community detection techniques in the Beijing bus

system. A two-level routing scheme is proposed to operate over the

backbone. The proposed routing scheme performs sequentially in

the inter-community level and the intra-community level, and is

able to support message delivery to both mobile vehicles and

speciﬁc locations/areas. Extensive experiments are conducted on

the real trace data of the Beijing bus system and the results show

that CBS can signiﬁcantly lower the delivery latency and improve

the delivery ratio. CBS is applicable to any bus-based VANETs.

Keywords—VANETs; bus systems; backbone; routing;

I. INTRODUCTION

A vehicular ad hoc network (VANET) consists of a set of

mobile vehicles equipped with dedicated short-range commu-

nication (DSRC) devices, which enable inter-vehicle communi-

cations and the communications between vehicles and roadside

units (RSUs). Routing in VANETs is a very challenging task

due to high-speed mobility and dynamic network topologies.

Extensive work has been done in the design of routing schemes

in VANETs. The existing work could be classiﬁed into three

categories. The work in the ﬁrst category is to deliver messages

from source vehicles to speciﬁc geographical locations (i.e.,

vehicle → location), which can support various location-based

applications such as geographic advertising [1], delivery of

parking information [2] and tourist points of interest [3]. The

work in the second category is to deliver messages from source

vehicles to destination vehicles (i.e., vehicle → vehicle), which

is often used for data collection and information sharing [4].

The work in the third category is to disseminate messages,

e.g., emergency messages and trafﬁc alert messages [5], in a

speciﬁed area. A broadcast operation is usually performed in

the routing schemes in this category and the challenge is to

tackle the broadcast storm problem [6] [7].

Low delivery latency and high delivery ratio are two key

design goals of routing schemes in VANETs. In the existing

solutions, delivering a message from one vehicle to another

is usually determined based on either real-time information

[8] [9] [10] [11] [12] or historical information [13] [14]

[15] [16] [17]. With the former strategy, a vehicle holding

a message selects its next-hop relay vehicle based on the real-

time information such as geographical position, vehicle density

and moving direction. This strategy performs well in dense

VANETs but suffers from a long delivery latency and a low

delivery ratio in sparse networks due to the lack of global

optimization. The latter strategy utilizes historical information

of vehicles to estimate the occurrences of their contacts in

future. A vehicle delivers its message to the relay vehicle with

the largest chance in contact with the destination vehicles.

Notice that the contacts of vehicles are not on a regular/routine

basis but random in practice. Two vehicles that contacted

previously may not contact again in the near future. Thus,

this strategy could result in a long delivery latency and failure

of message delivery.

To tackle the aforementioned problems, some work [10]

[18] proposed to deploy RSUs at road intersections and bus

stops so as to provide message relay for vehicles. However,

their routing efﬁciencies are limited by the number and loca-

tions of RSUs and it incurs considerable cost in the deployment

and management of the RSUs [19]. In this work, we propose to

utilize bus systems as routing backbones of VANETs without

RSUs. We study the bus system in Beijing, China, where there

are 21293 buses of 989 bus lines in total. We collect real

traces of 2515 buses (from 1 Mar 2013 to 31 Mar 2013) and

conduct extensive analysis of the traces. We ﬁnd that there are

several advantages in using bus systems as routing backbones

of VANETs.

Fig. 1: One-day traces of 2515 buses in Beijing. The bold lines

denote the aggregated traces of the buses.

• Wide coverage. We plot the traces of the 2515 buses

in Beijing in Figure 1. It is clear to see that the

traces form a backbone of Beijing city. Therefore, it is

feasible to use bus systems as routing backbones for

message delivery in VANETs.

• Fixed routes. Compared with routes of other vehicles

(e.g., taxies), the routes of buses are normally ﬁxed.

This unique feature of bus systems enables us to map

a speciﬁc location/area to ﬁxed routes of buses. For

example, the route of bus line No. 944 passes by the

Beijing Olympic Stadium (i.e., the Bird’s Nest). The

messages destined for the Bird’s Nest area can be

delivered by the buses of line No. 944.

• Regular service. The service of a bus line is regular.

For example, bus line No. 988 starts and stops its

service at 5am and 10pm, respectively, in Beijing. If

service hours and ﬁxed routes of two bus lines overlap,

the contact of the buses from these two bus lines is

very likely to occur and thus message delivery among

these buses is highly predictable.

In this work, we propose a Community-based Bus System

(CBS) as routing backbone of VANETs. The idea of CBS

originates from our analysis of real traces of 2515 buses in

Beijing. Speciﬁcally, CBS is composed of a community-based

backbone and a routing scheme over the backbone. We ﬁrst

build a contact graph which shows the closeness relation of

bus lines. We notice that some buses are “closer” than others

in terms of the frequency of contacts and some bus lines are

“more active” in connecting other bus lines. Inspired by the

concept of social networks, we apply community detection

techniques in the contact graph to build a community graph

which identiﬁes potential communities of the Beijing bus

system. A backbone graph is derived from the community

graph by mapping the ﬁxed routes of bus lines to the real map.

Based on the community-based backbone, a two-level routing

scheme is proposed to deliver messages to either a mobile

vehicle or a speciﬁc location. The two-level routing scheme

operates sequentially in the inter-community level and the

intra-community level on the backbone. Our proposed solution

is applicable to any bus-based VANETs.

The main contributions of this work are summarized as

follows.

• We analyze the real traces of 2515 buses in Beijing

and discover a strong community structure in the bus

lines of these buses.

• We propose to utilize bus system as a routing back-

bone of VANETs and build a community-based back-

bone by applying community detection techniques of

social networks.

• We propose a two-level routing scheme that operates

on the community-based backbone. The proposed

routing scheme is able to support message delivery

to both mobile vehicles and speciﬁc locations/areas.

• We conduct extensive experiments on the real bus

traces. The experimental results show that our pro-

posed solution CBS can signiﬁcantly lower the deliv-

ery latency and increase the delivery ratio, compared

to the existing solutions.

The rest of this paper is organized as follows. Related work

is reviewed in Section II. We analyze the traces of the Beijing

bus system in Section III. We apply community detection

techniques to build a community-based backbone in Section

IV, and propose a two-level routing scheme in Section V. The

experimental results are presented in Section VI. Finally, we

conclude our work in Section VII.

II. RELATED WORK

VANET is a kind of mobile ad hoc network (MANET) and

is essentially a delay tolerant network (DTN). We ﬁrst review

existing routing schemes in VANETs and then discuss relevant

work in MANETs and DTNs. The differences between our

solution and the existing solutions are summarized in Table I.

A. Routing Schemes in VANETs

Basically, there are two strategies in the design of routing

schemes in VANETs. The ﬁrst strategy is to use real-time

information of vehicles such as geographical position, vehicle

density and moving direction. GSR [8] is a typical position

based greedy routing scheme in which a vehicle sends mes-

sages to a neighboring vehicle that is closer to the destination

than itself. A similar idea was used in GPCR [9]. It chooses a

neighboring vehicle whose geographical position is at the inter-

section or closest to the destination, and forwards the message

to this neighbor. In addition to the geographical position, trafﬁc

information are also considered in existing routing schemes.

For example, VADD [11] proposes a stochastic model based

on vehicular trafﬁc information which aims to minimize the

message delivery latency. TBD [12] utilizes traces of vehicles

and the trafﬁc information (e.g., vehicle speed and vehicle

density) to improve the performance of data forwarding. A

localized algorithm is presented to compute the expected data

delivery delay (EDD) at individual vehicles to an access point.

The computed EDD is shared with neighboring vehicles and

the vehicle with the smallest EDD is selected as the next

carrier.

The other strategy is to utilize historical information in-

cluding contacts and traces of vehicles. MaxProp [13] builds

a bus network in the UMass Amherst campus and estimates

the delivery likelihood, i.e., the probability of contact between

buses. However, the testbed of MaxProp is composed of 30

buses only. BLER [14] studies contact length between different

bus lines where the contact length is deﬁned as the length

of overlapping routes of these bus lines. A routing path is

computed from one bus line to another such that the sum of

contact length of the path is maximized. Similar to BLER,

R2R [15] calculates the frequencies of contacts between bus

lines based on historical traces and then utilizes them to

decide the routing paths. A recent work, ZOOM [16], considers

the contact-level mobility and the social-level mobility in the

message delivery. A message is relayed by the vehicle with

the shortest contact delay to the destination of the message. If

information of contact delay to the destination is not available,

the message will be delivered to a popular vehicle that has

high centrality in the social level, because the popular vehicle

can contact more vehicles and can have more opportunities

for message forwarding. Another recent work called GeoMob

[20] determines routes based on the traces of vehicles. GeoMob

captures the trafﬁc volumes in different regions and uses the

K-means clustering method to construct clustered regions. The

route is selected to pass through the regions with high trafﬁc

volumes. The routing from one region to another is determined

based on the mobility patterns of individual vehicles. The

剩余9页未读，继续阅读

评论收藏

内容反馈

weixin_38617297

粉丝: 2
资源: 896

基于社区的总线系统作为车载Ad Hoc网络的路由骨干网

最新资源

基于社区的总线系统作为车载Ad Hoc网络的路由骨干网

Community-based Bus System as Routing Backbone for Vehicular Ad Hoc Networks

Ad Hoc Network Routing

基于深度强化学习的移动Ad Hoc网络路由选择.pdf

基于ADHOC网络路由协议的性能分析.pdf

安全技术-网络信息-城市场景车载AdHoc网络单播路由机制.pdf

车载Adhoc网络中基于位置的路由协议研究论文.doc

一种基于定向技术的Adhoc路由协议

基于蚁群算法的AD HOC网络路由研究

论文研究-一种基于地理位置信息的Adhoc网络路由算法.pdf

移动AdHoc网络中基于动态规划法的QoS路由研究

基于Matlab的Ad Hoc网络定向_全向路由仿真分析.pdf

基于可靠骨干网的Ad Hoc网络安全路由协议.pdf

移动Adhoc网络路由协议分析

基于煤矿安全的Ad hoc网络路由遗传算法研究

论文研究-一种基于跨层功率控制的Adhoc网络路由算法.pdf

安全技术-网络信息-城市场景车载AdHoc网络单播路由机制的研究.pdf

关于AD HOC 网络路由协议

最新资源