9512.net
甜梦文库
当前位置:首页 >> 材料科学 >>

An efficient geo-aware peer-to-peer resource discovery and sharing scheme in vehicular ad-hoc



Int. J. Ad Hoc and Ubiquitous Computing, Vol. 14, No. 4, 2013

267

An efficient geo-aware peer-to-peer resource discovery and sharing scheme in vehicular ad-hoc networks Chyi-Ren Dow*
Department of Information Engineering and Computer Science, Feng Chia University, Taichung 40724, Taiwan E-mail: crdow@fcu.edu.tw *Corresponding author

Pei-Jung Lin
Department of Computer Science and Information Engineering, Hungkuang University, Taichung 43302, Taiwan E-mail: pjlin@sunrise.hk.edu.tw

Yu-Hong Lee, Ya-Chen Lin and Shiow-Fen Hwang
Department of Information Engineering and Computer Science, Feng Chia University, Taichung 40724, Taiwan E-mail: wincelyes@gmail.com E-mail: qznd2464@yahoo.com.tw E-mail: sfhwang@fcu.edu.tw
Abstract: There has been a recent increase in research on vehicular ad-hoc network (VANET) technology. Peer-to-peer (P2P) systems have also been widely used for resource sharing. This paper proposes an efficient geo-aware P2P search mechanism to enable resource discovery and sharing on VANETs. The proposed discovery and sharing schemes are based on virtual backbone architecture. The schemes limit the data-exchanging region to reduce unnecessary message transmissions. They establish coordinators to store information and manage local resource information. If more vehicles own the resources, the user has more opportunities to discover and obtain the resources. Three piece selection mechanisms, Nearest-First, Rarest-First and In-Order, are proposed to download resource pieces from other vehicles and to improve the dissemination efficiency speed at which resources piece to networks. Experimental results demonstrate that the searching and sharing schemes are efficient and outperform other schemes in terms of satisfactory ratio and download time. Keywords: VANETs; vehicular ad-hoc networks; P2P; peer-to-peer; resource discovery and sharing; piece selection policy. Reference to this paper should be made as follows: Dow, C-R., Lin, P-J., Lee, Y-H., Lin, Y-C. and Hwang, S-F. (2013) ‘An efficient geo-aware peer-to-peer resource discovery and sharing scheme in vehicular ad-hoc networks’, Int. J. Ad Hoc and Ubiquitous Computing, Vol. 14, No. 4, pp.267–278. Biographical notes: Chyi-Ren Dow received the BS and MS in Information Engineering from National Chiao Tung University, Taiwan, in 1984 and 1988, respectively, and the MS and PhD in Computer Science from the University of Pittsburgh, USA, in 1992 and 1994, respectively. Currently, he is a Professor in the Department of Information Engineering and Computer Science, Feng Chia University, Taiwan. His research interests include mobile computing, ad-hoc wireless networks, agent techniques, fault tolerance, and learning technology. Pei-Jung Lin received her PhD in Information Engineering from Feng Chia University, Taiwan, in 2011. Currently, she is an Assistant Professor in the Department of Computer Science and Information Engineering, Hungkuang University, Taiwan. Her research interests include mobile computing, ad-hoc wireless networks, wireless mesh networks, wireless social networks, and motion-sensing technology.

Copyright ? 2013 Inderscience Enterprises Ltd.

268

C-R. Dow et al.
Yu-Hong Lee received the MS in Institute of Applied Information Technology from Ling Tung University, Taiwan, in 2009. His research interests include vehicular ad-hoc networks, telematics, and sensor web techniques. Ya-Chen Lin received the MS in Information Engineering and Computer Science from Feng Chia University, Taiwan, in 2011. His research interests include vehicular ad-hoc networks and telematics. Shiow-Fen Hwang received her BS, MS and PhD in Applied Mathematics from National Chiao Tung University, Taiwan, in 1985, 1987 and 1991, respectively. Currently, she is a Professor in the Department of Information Engineering, Feng Chia University, Taiwan. Her research interests include interconnection networks, mobile computing and computer algorithms.

1

Introduction

There has been a recent increase in research on vehicular ad-hoc network (VANET) technology for industrial and academic purposes. In addition to traffic safety issues, file sharing and entertainment services are also important issues for VANETs (Bai et al., 2009; Chang et al., 2010; Yang et al., 2004). P2P networks are extremely popular distribution channels on the internet. They can also be combined with other infrastructure for file sharing (Atechian et al., 2009; Olariu, 2007; Prinz et al., 2009). Content-sharing applications, including VoIP telephony, streaming video, entertainment services, and anything in digital format, are common. Therefore, with increased attention on inter-vehicular communication, researchers have developed P2P systems on VANETs to enable more versatile content-sharing applications (Barberis and Malnati, 2011; Zhang et al., 2009). Several issues must be addressed before P2P can be efficiently used in VANETs. The first issue is congestion. Unlike with fixed network environments, VANETs do not have centralised management; thus, distributed resource discovery and sharing mechanisms are required. Vehicles are used as a medium for resource sharing in VANETs; therefore, any form of datacasting must be conducted by multi-hop routing, such as centralised client–server architecture. In traffic-heavy conditions, when many users request access to a certain resource from a certain vehicle, large overheads are produced and local congestion may occur. Because of the high mobility of vehicles in VANETs, the routes between peers are unstable. If a client discovers only one server, the route is easily broken and the reliability is low. Thus, much time is wasted discovering the resource node. The second issue is resource discovery. To decrease overheads, resource duplication can convert centralised resources into multiple resource nodes. The problem then becomes how to locate the most suitable node with the target resource among many local nodes in mobile environments. Gnutella (http://rfc-gnutella.sourceforge.net/ src/rfc-0_6-draft.html) proposed a flooding method without a central server to store metadata information. However, such a searching mechanism may cause redundant transmissions and duplicate resources from each node. The formation of P2P network topology directly connects

adjacent nodes. In this type of unstructured P2P network, when a node must look up a resource from other nodes, many search schemes (Stutzbach et al., 2008) broadcast target messages to nodes neighbouring the resource node. The neighbour nodes then continue to rebroadcast. Flooding-based search schemes thus generate many messages and cannot guarantee discovery accuracy. The third issue is efficiency. In distributed network architecture, general flooding-based search methods produce many overhead request messages and cause packet duplication. Therefore, search latency may increase. Many studies have proposed structured search algorithms for P2P distributed systems, such as Chord (Stoica et al., 2001), CAN (Ratnasamy et al., 2001) and Tapestry (Zhao et al., 2001). Distributed hash tables (DHTs) are also used to determine the route. In wired networks, each network node has a unique node ID and IP address and each resource is assigned a number. Each peer must have rules for data searching and routing that require a centralised metadata directory to store node locations. However, these structures do not consider geography and road topology and are not suitable for VANETs. Because vehicles usually move at high speeds, especially in VANETs, and the links between nodes often break, information can become obsolete and maintenance costs are high. A network-structured resource discovery scheme can improve resource accuracy and reduce searching time. To address these issues, this paper proposes geo-aware P2P search mechanisms to enable VANET resource discovery and sharing. The searching scheme is based on a virtual backbone structure and a geo-aware routing mechanism for vehicular communication. The virtual backbone is treated as a distributed share tree, and each node cooperates with other nodes to construct a shared tree, limiting the data-exchanging region. Coordinators are established on a virtual backbone. They store information and manage local resource information. To reduce control packets for information exchange, clusters can support effective resource management in mobile environments. Vehicles are elected as headers using grid-based geographic information that manages collection pieces within the grid header. The data structure design can create a local resource of routing table information based on a virtual backbone to locate and record resources. This study considers three

An efficient geo-aware peer-to-peer resource discovery and sharing scheme policies to select routing discovery and disseminate sharing: Nearest-First, Rarest-First and In-Order. The remainder of this paper is organised as follows. Section 2 details related research on discovery and sharing technology, P2P technologies, and piece searching and selection schemes. Section 3 presents the proposed resource discovery and sharing schemes. Section 4 provides the experiment results. Lastly, Section 5 offers conclusions.

269

2

Related work

This section describes research related to this study, including data discovery, data-sharing approaches and P2P technologies. It describes the piece-searching problem and piece selection strategy research. Anycast-K (Lin et al., 2008) service discovery scheme allows a client to discover any k-services and is deployed on a cluster-based virtual backbone to reduce unnecessary message transmissions in MANETs. The proposed scheme in Liu et al. (2012) also uses virtual backbone, which consists of geo-grids, as an infrastructure to share data. The scheme reserve data on the backbone and minimise the number of data transmissions. However, because the speed and directions of vehicles are usually unstable and unpredictable, grid headers of geo-grids are frequently changed owing to the maintenance process of backbone scheme. In VANET, the researchers usually use the broadcasting protocols to design resource or information-sharing schemes. The broadcasting protocols can be classified to multi-hop broadcasting and single-hop broadcasting (Panichpapiboon and Pattara-atikom, 2012). According to how to avoid the collision problem for rebroadcasting, multi-hop broadcasting protocol can be classified into three categories: delay, probabilistic and network coding. On the contrary, in single-hop broadcasting, the information is kept in a vehicle or roadside and this information will be transmitted to other vehicles in their one-hop neighbourhood in the next broadcast period. According to how to decide this period, single-hop broadcasting protocol can be classified to fixed period and adaptive period. The resource-sharing protocol (Tsoumakos and Roussopoulos, 2003) is intended to reduce a searching area and avoid flooding problems, which may lead to search delay. In VANET, some information-sharing schemes (Bai et al., 2009; Dutta, 2010) design metadata management and search functionalities on zone-based hash tables. This is because the node must determine resource positions with location service support. Distributed location services can effectively decrease average location discovery delay. Most VANET routing protocols use geographic information to forward data packets from the source to the destination (Hong et al., 2011; Lee et al., 2011). GPSR (Karp and Kung, 2000) uses greedy forwarding to forward packets to neighbour nodes closest to the destination.

If the vehicle density in the network is low, no vehicles may be available to deliver the packet. HarpiaGrid (Chen et al., 2010) uses geo-information to generate the shortest route and effectively balances route discovery communication overheads with insignificant computation time. Omnibone (Dow et al., 2010) circulates and discovers service information using public transportation systems, including traffic infrastructure and mobile vehicles. Bus routes can be used to create a grid-based backbone structure and data can be posted and circulated on the structure to avoid broadcast storm problems. In traditional client–server systems, too many client requests to a server may overload servers and congest networks (Ramzan et al., 2003). P2P networks are client–server-type models. P2P applications rely on nodes sharing many different pieces of content. Because clients frequently join and leave P2P networks, file availability changes constantly. P2P systems are classified into unstructured and structured architecture categories. Structured P2P protocols are designed to locate effective objects in wired networks, such as Chord (Stoica et al., 2001), CAN (Ratnasamy et al., 2001) and Tapestry (Zhao et al., 2001). DHT approaches are used to query addresses to improve search efficiency. They are unsuitable for rapid mobility environments, such as MANETs and VANETs (Dutta, 2010; Liu et al., 2008) because maintenance and search costs are high. Gnutella (Stutzbach et al., 2008; http://rfc-gnutella. sourceforge.net/src/rfc-0_6-draft.html) is an unstructured P2P protocol that is a P2P application pioneer. It uses a flooding-based mechanism to discover shared resources in networks. Flooding-based protocols are commonly used in unstructured P2P networks mainly because of their simplicity and increased fault tolerance. Flooding is an easy method of searching for any resource, but it may result in high search overheads. Therefore, many improved algorithms have been proposed to increase the efficiency of searching resources and reduce searches. BitTorrent (Guo et al., 2007) is a file transfer system, originally designed to distribute content quickly and efficiently. Clients find nodes from which to download through a centralised node called the tracker server, which tracks clients serving or downloading a particular file. Thus, BitTorrent requires a mechanism to dynamically assign trackers to manage the dynamic nature of P2P file sharing. Because of the distributed nature of the P2P network, searching and locating data in the network is an important issue (Cao et al., 2009; Zhang et al., 2009). Because nodes may leave at any time in mobile environments, some pieces become rare or lost. Piece selection policies (Acunto et al., 2010; Kawarasaki and Suzuki, 2009; Liu et al., 2010) decide periodically which piece to request from other network nodes available for download. These policies focus on proposed methods to overcome issues such as server dependency, network efficiency and fairness. Therefore, BitTorrent introduced the Rarest-First piece selection

270

C-R. Dow et al.
Figure 1 Grid header election and collection (see online version for colours)

algorithm to manage the last piece problem and increase piece diversity. The main goal of the piece selection algorithm is to provide the best quality with the bandwidth available. This allows more peers better-quality QoS, and free riding is tolerated only when bandwidth resources are abundant. Finally, the performance evaluation of information propagation in VANET is also an important issue. The research in Wang et al. (2012) studies the information propagation in inter-vehicle communication. The authors consider the packet loss rate, data transmission distance, and coverage range of roadside for different equipped rates, wireless communication ranges, and typical distributions of vehicle space headway. These results can be used for reference in comparison of different resource or information-sharing schemes.

3.1.2 Coordinator establishment scheme
A coordinator collects and holds resource information from adjacent grid headers to provide query services, as shown in Figure 2. The establishment of coordinators leads to many query and reply packets. To avoid this problem and increase metadata collection reliability, this study proposes a coordinator establishment scheme based on the virtual backbone. The virtual backbone has many functions during session establishment. Thus, a coordinator is important for deciding which grid header on the virtual backbone is more suitable for collecting resource metadata. The algorithm of coordinator establishment is described as follows: ? According to degree on the virtual backbone of tree structure, the coordinator is selected from the lowest grid number and the grid header whose degree is more than 2. Figure 3 shows that – beginning with the left lowest grid number – each grid number refers to x+y*columni. The coordinator establishment scheme may result in many coordinators adjacent to each other. In this case, the establishment of coordinators for grids 25 and 57 is unnecessary because there are many neighbouring coordinators. To increase metadata information precision, each branch path increases by a coordinator when the number of hop counts is more than 2. The main purpose of this is to avoid redundant metadata collection from the wide range of each path, causing high network loads. To avoid the excessive control overhead of coordinators and to reduce redundant coordinators, a coordinator is not established when it is in the leaf node path in grids 21 and 59. Because the coordinator of grids 21 and 24 collected the same information on the locality of metadata from the grids, an excess of duplicated information causes redundant transmissions if the coordinator of grid 21 is established. Therefore, the coordinator of grid 59 has the same origin as grid 21.

3

Schemes proposed

This section describes the proposed geo-aware P2P search mechanisms, including metadata collection and management, data format design and resource discovery.

3.1 Metadata collection and management
The discovery and sharing schemes are deployed based on virtual backbone architecture that determines an area that limits the data exchange region and increases P2P search mechanism reliability.

3.1.1 Grid header election
Grid header election is based on geo-information from a generic mobile node in the grid. The grid header is selected from vehicles with the longest stay time in the grid. Header nodes must manage other vehicle information and avoid frequent exchange of metadata. Usually, a node can be elected as a coordinator according to the estimated distance to the reference point, defined as the centre of the grid. Figure 1 shows a criterion based on the distance between the reference point and the mobile nodes. This is defined as
Di = ( xrp ? xi ) 2 + ( yrp ? yi ) 2 < r ,

?

where (xrp, yrp) and (xi, yi) are the coordinates of the reference point and the mobile nodes in the same cell, respectively, and r is the transmission range to consider a mobile node to be a possible grid header candidate. Using the distance formula to calculate the distance between each vehicle and the reference point selects the grid header from the smallest distance, D1. Each grid collects the metadata of available pieces around itself and then uses the information to establish its tracker list table (TLT; described in Section 3.2).

?

An efficient geo-aware peer-to-peer resource discovery and sharing scheme
Figure 2 Coordinator collection (see online version for colours)

271

Hash function results are based on RNi and RSi, and there are 40 hexadecimal codes.
Table 1 Tracker list table Tracker information Item I0 I1 … Ii Resource name Linkin.mp3 Boys.avi … RNi Resource size 5 MB 10 MB … RSi Hashing information AdCc2326d2e….. 84a51684Abd8…. … HI1~40

Figure 3

Coordinator establishment (see online version for colours)

3.2.2 Multi-piece item
A multi-piece item (MPI) is established in each grid header to store the information of vehicles that own the pieces. Table 2 shows the data structure of the MPI metadata. The MPI consists of four columns, including Piece ID, Piece Size, Hash Information and Location. Each field in the MPI is defined as follows: ? ? PIDi: indicates a distributed resource that is divided into several segments, called pieces. PSi: the default size of a piece unit is 256 kbytes on P2P systems. A resource is cut into pieces with fixed size. HI1~40: To ensure reliability, each piece has a unique hash function code. They ensure data accuracy similar to a hash function TLT. *Li: must record the possession of vehicles sharing of scattering pieces. MPI reduces data storage using data compression normalisation techniques, including Grid ID, Vehicle ID and Expiration Time, as shown in Table 3. ? GID(x, y): indicates resource location coordinates. Each vehicle is equipped with a GPS navigator to obtain its grid location on the Cartesian coordinate system. VIDi: is the vehicle ID within the grid. EXPi: indicates the expiration time of the MPI and it enhances the accuracy and currency of the metadata information. If Ti expires, the piece is ineffective. If the information is updated, the value of Ti refreshes.
Multi-piece item Multi-piece item[i] Piece ID P0 P1 P2 … PIDi Piece size 256 kB 256 kB 256 kB … PSi Hash information 1ba77a5…. 4a51664…. 31fABaa…. … HI1~40 *Location *L0 *L1 *L2 … *Li

?

3.2 Design of metadata format
Metadata format design must consider the purpose of establishing efficient P2P search mechanisms. When searching resources, the node in the virtual backbone architecture effectively selects a resource according to the metadata information in the table. ?

3.2.1 Tracker list table
A TLT is established in each coordinator from local grid headers to collect resource information. The information is the metric for resource selection. When searching resources, the node effectively selects a resource according to the information in the table. Table 1 shows the data structure of TLT metadata. Each field in a TLT is defined as follows: ? Ii denotes the number of resource indices for all local grid headers in the TLT table. i is the number of resources. RNi denotes the resource name and these columns provide resource enquiry information. RSi denotes the resource size. HI1~40 are resources and pieces realised through the SHA-1 hash function. They distribute each vehicle in the mobile environment based on a unique resource identity for P2P file verification mechanisms.

? ?

Table 2

? ? ?

272
Table 3

C-R. Dow et al.
Multi-piece item of *Li *Li Grid ID Vehicle ID 10 2 … VIDi Expiration time 5 0 … EXPi

(4,2) (4,5) … GID(x, y)

3.2.3 Information table maintenance
Information is stored in a TLT at the coordinator from each search grid header. Scope flooding is used to search and the node effectively selects the resource according to information in the table from the neighbouring coordinator. The information table promotes network searching, but this method leads to inconsistent information. Incorrect information results in incorrect selection. To decrease node loading, only grid headers and coordinators perform information maintenance, including on-demand, periodical enquiry and piggybacking. The on-demand approach is mainly an extension of the routing information protocol (RIP) to maintain information. The two-piece nodes can exchange route information when their information tables change. On-demand does not require frequent message exchange to keep pieces alive. A grid header then queries unknown MPI in a period, to enhance the accuracy of the information table. The inconsistent information problem must also be solved. Piggybacking without additional cost is proposed for TLT and MPI transmission swaps. Each coordinator plays an important role because it contributes to the selection of resource strategies.

3.3 Resource discovery and sharing
When a node desires to search resources, it sends a query message to the local coordinator. Traditional P2P searching schemes using flooding techniques may produce excess overheads and collision may occur in the network. The flooding protocol searches blind, i.e., it does not have resource information and cannot guarantee that reply resources are the best selection. Therefore, this study proposes a policy-based resource selection mechanism. Nodes use previously collected resource information from the MPI table as a criterion to select appropriate piece providers. The resource selection resource mechanism effectively decreases network overheads, searches optimal resources, and reduces searching delay in various applications.

networks. There are three searching strategies for piece selection, Nearest-First, Rarest-First and In-Order. The set pieces are downloaded first. To ensure disseminate performance, nodes must possess enough different pieces to allow efficient data exchange. Nearest-First is always essential to discover the nearest available pieces. The Nearest-First policy locates the nearest content pieces as opposed to continually attempting to locate content from a local coordinator. A user can search for a service from the next nearest available piece from a distributed resource because the user can visit the nearest piece provider with a prompt response. BitTorrent uses the Rarest-First policy to search the rarest pieces in the resource list and download rare pieces that are situated closer to the preferred node. In other words, Rarest-First dictates that a download peer maintains availability of the pieces in the local neighbourhood and attempts to fetch the least available pieces first. By replicating the rarest pieces as quickly as possible, the Rarest-First policy increases the overall robustness of the protocol and avoids missing resource pieces. In-Order downloading policy provides an ideal sequential progress at nodes compared with streaming systems that have continuous audio and video. To maintain the playback continuity of an object and to avoid video loss or distortion, its search strategy is based on the order of the split sequence resource. Therefore, the In-Order download is necessary to preserve stream continuity and shorten start-up delays. These strategies find nearest pieces neighbouring a given query local coordinator. It uses distance as the selection metric and the shortest route between demanders and pieces on the geographic coordinate system. If more than two nodes share the same resource pieces, the piece is first selected according to the minimal expiration time.

3.3.2 Resource discovery and sharing protocol
Resources are node sources to share on VANETs. The proposed P2P searching scheme discovers and shares optimal resources. The resource discovery and sharing algorithm is shown in Figure 4. When a node requires a resource, it must retrieve many pieces to assemble the resource. They query neighbouring coordinators to find the number of pieces. The following assumptions were defined to better describe the protocol: ? ? ? ? V = {v1, v2, …} indicates a set of Vehicles. G = {g1, g2, …} indicates a set of Grid Headers, where G ? V. C = {c1, c2, …} indicates a set of Coordinators, where C ? G. R = {r1, r2, …} indicates a set of Resources, where the set of pieces of resource ri is defined as Pr = {ri1, ri2, …}. Currently, the default size of a piece

3.3.1 Piece selection policy
A piece selection policy selects pieces available from a particular node. Hence, piece selection policies are to download resource pieces in order of discovery and to improve time taken to disseminate resource pieces to

An efficient geo-aware peer-to-peer resource discovery and sharing scheme unit is 256 kbytes on P2P systems. A resource is cut into pieces with a fixed size. ? M = {m1, m2,...} indicates a Multi-piece Item Table, in which mi = {id_of(pi), size_of(pi), key_of(pi), vj}, consists of the id, size and verification code of pi, owned by vj. A Multi-piece Item Table exists in each gi ∈ G. FindPiece(pi) = Vk..
Resource discovery and sharing algorithm

273

piece. First, node A must locate P5, but if each piece has the same ratio, node A selects the minimal grid distance. The performance process is the same as the Nearest-First policy process. For the In-Order policy, MPI records a continuous sequence information piece ID for streaming where pieces of the media resource download in a strictly sequential order, P1 ? P2 ? P3 ? P4 ? P5.
Table 4 Grid (5, 4) of Multi-Piece Item (see online version for colours)

Figure 4

4

Experimental results

This section details the experiment results. It introduces the experiment environment and presents the simulation results of different searching strategies.

4.1 Simulation design
This section evaluates the proposed geo-aware P2P searching scheme. Network simulator 2 (NS-2), Version 2.34 (http://www.isi.edu/nsnam/ns) was used as a simulator. The simulation vehicular movement pattern was generated by Simulation of Urban Mobility (SUMO) (http://sumo. sourceforge.net/index.shtml) and the Taichung City geoinformation. This is shown in Figure 6. The map was obtained from Google. Latitude and longitude coordinates were manually recorded for the Taichung city map. The SUMO tool then generated traffic and road information. As shown in Figure 7, the coordinators were selected according to the virtual backbone coordinator establishment scheme. Table 5 shows the simulation parameters and values. The simulation ran 100 times and each simulation took 300 s. The area was 3500 m × 2750 m. This scheme was compared with other schemes, including flooding-based P2P search mechanisms such as Gnutella. The number of copies and the number of vehicles influence performance for selection policy. Therefore, the simulation did not consider the last piece problem and assumes a stable original resource that never leaves the network to maintain piece availability. The service node was randomly selected as a resource provider and requestor to discover any available resource from each route.

3.3.3 Examples of resource discovery and sharing
As shown in Figure 5, node A, located in grid 43 and represented by coordinate (3, 4), requests a resource, P1 from neighbouring coordinators, grids 41 and 45. Subsequently, node A receives P1 from the MPI coordinator in grid 46. Table 4 shows that node A executes piece selection mechanism, such as R1 = {P1, P2, P3, P4, P5}. The Nearest-First policy calculates the Grid ID field from MPI. For example, node A is associated with other pieces to locate the distance of the nearest point between two given grid numbers on the Cartesian coordinator system. The Rarest-First policy calculates the piece ratio field from MPI. Node A calculated from MPI records the number of pieces and selects the lowest proportion of each

274
Figure 5

C-R. Dow et al.
An example of resource discovery (see online version for colours)

Figure 6

Google map of Taichung city (see online version for colours)

?

Satisfactory ratio: indicates the total query resources to the requestor over the total search resource. A higher value represents better performance. Download time: indicates the number of resources downloading in complete time and time taken to download resources as a whole. A lower value represents better performance. Average hop count: indicates the average number of hops for each piece. Average end-to-end delay: indicates the average time per request and reply process.
Parameters of simulation environment Values Google MAP 3500 × 2750 m Random 300 s 30~60 ± 5Km/h 200~500 1~200 802.11 MAC 250 m 10 MB 256 KB

?

? ?

Table 5 Parameters Figure 7 SUMO simulation generate traffic and road information (see online version for colours) Map size

Mobility model Simulation time Vehicles speed Number of vehicles Number of resource MAC protocol Transmission range Resource size Piece size

4.2 Simulation results for satisfactory ratio
This section compares the satisfactory ratio with various resource densities. The performance of different numbers of resources (from 10 to 200) is evaluated. The value of resource copies influences the satisfactory ratio. With an increase in the number of resource copies, more vehicles own the resource.

The performance metrics were used to evaluate the simulation results as follows:

An efficient geo-aware peer-to-peer resource discovery and sharing scheme As shown in Figure 8, at the beginning, few vehicles own the resources. There are insufficient providers to provide more sharing resources. Subsequently, with resource copies increasing from 50 to 160, the satisfactory ratio of the proposed scheme is better than that of Gnutella. This is because as more vehicles offer resources, more data sharing is gradually obtained. Using coordinator and piece selection mechanisms also improve search efficiency for multiple resources. When more vehicles own the resource, the user has more opportunities to discover the diversity of the region.
Figure 8 Satisfactory ratio vs. varying number of copies Figure 9 Satisfactory ratio vs. varying number of vehicles

275

The experiment results show that the proposed coordinator establishment method does not reduce download time and it is necessary to ensure resource integrity. When more vehicles own the resource, the user has more chances to discover the resource and reduce download time. This means that our scheme effectively shares resources in VANETs. Each vehicle can also share resources and exchange the piece data to expand sharing services. Therefore, the proposed scheme performs downloads with high resource density and the four methods consistently converge until the overall network reaches a saturation state.

According to experiment observations, the number of copies influences the satisfactory ratio. As shown in Figure 8, the satisfactory ratios of all schemes become stable. This is because there are 200 vehicles and 150 resource copies in the networks; therefore, a node has many opportunities to locate a copy in its vicinity. Furthermore, as shown in Figure 9, with an increase in vehicles from 150 to 500 and a fixed number of resource copies (150), the satisfactory ratio slowly decreases for the Nearest-First policy because it always locates the closest resource. An increase in vehicles may cause local resource scarcity. Rarest-First policy must first acquire scarce piece priority and then attempt to maintain piece availability by making nodes remain longer in the network.

The performance with 150–500 vehicles was considered. Figure 11 shows that the proposed scheme is better than Gnutella. As resources become sparse, resource downloading gradually increases over time instead of blind searching. Rarest-First and In-Order methods must follow the piece for policy selection, but this leads to insufficient neighbouring node pieces. Nearest-First chooses the nearest piece as the best download transmission.
Figure 10 Download time vs. varying number of copies

4.3 Simulation results for download time
As shown in Figure 10, with an increase in the number of copies from 30 to 100, download time decreases from 185 s to 30 s. This is because the proposed scheme effectively selects close resources. The Gnutella discovery mechanism struggles to search in a vehicular environment. Thus, the coordinator caches the number of resources in a TLT and requests that each local coordinator locates the insufficient number of resources instead of blind searching.

276

C-R. Dow et al. Figure 13 shows that the Nearest-First average hop count is the shortest because the Nearest-First strategy uses the distance grid as the selection metric. The Nearest-First strategy obtains the nearest available data to download content.
Figure 13 Average hop count vs. varying number of vehicles

Figure 11 Download time vs. varying number of vehicles

4.4 Simulation results for average hop count
Figure 12 shows that the proposed scheme selects the shortest routing strategy better than Gnutella when the number of copies increases from 30 to 75. However, the average hop count and download time of each scheme is almost identical. Increasing the coordinator of the proposed scheme provides more opportunities to acquire resources. It is more efficient to decrease average hop count than to increase duplicated resources. When the number of resources is 190, the average hop count of the proposed scheme is the same as that of Gnutella with high resource density. The main reasons are because of the high density of resource dissemination in the network environment and because the coordinator has a high discovery probability caused by many neighbouring resources.
Figure 12 Average hop count vs. varying number of copies

4.5 Simulation results for average end-to-end delay
The end-to-end delays of various resource densities were compared. Figures 14 and 15 show comparisons between end-to-end delays and number of copies and vehicles. The amount of available resources affects end-to-end delay. Because of vehicle mobility, the frequency of duplicated resources increases. Figure 14 shows the average end-to-end delay of the four approaches when the number of copies is between 10 and 200. The end-to-end delay of Nearest-First and Rarest-First strategies outperforms other search schemes. The average end-to-end delay of the proposed scheme is less than that of Gnutella by 25 ms. This is because Gnutella does not access resource information. The In-Order policy must find the sequence of fragments. However, Nearest-First and Rarest-First must only locate resources in the region.
Figure 14 Average end-to-end delay vs. varying number of copies

A simulation environment evaluated the performance of between 150 and 500 vehicles with copies fixed at 150. Gnutella sends more query packets and reply resources than the proposed scheme. When the number of vehicles is greater than half the resources, the Rarest-First strategy compensates for the shortage of fragments in the region.

An efficient geo-aware peer-to-peer resource discovery and sharing scheme Figure 15 shows the relationship between average end-toend delay and number of vehicles when resource copies are limited to 150. The average hop count and end-to-end delay for each scheme is almost identical. The proposed scheme improves download time and reduces packet delay.
Figure 15 Average end-to-end delay vs. varying number of vehicles

277

5

Conclusions

This study develops an efficient geo-aware P2P search scheme that can be used to discover and shared resources in VANETs. According to geographic information, establishing coordinators decreases the cost of unnecessary transmissions and efficiently collects resource information instead of blindly searching. The proposed scheme improves resource discovery and reduces download dissemination time. The policy used by nodes has a large effect on download performance. Therefore, table information design assists in sharing resource circulation and discovery. Additionally, if more vehicles own the resources, the user has more opportunities to discover and obtain resources. Experiment results show that the proposed geo-aware P2P searching and sharing schemes are efficient and outperform other schemes in terms of satisfactory ratio and download time.

Acknowledgement
The authors thank the National Science Council of the Republic of China for financially supporting this research under Contract No. NSC99-2221-E-035-045-MY2.

References
Acunto, L.D., Andrade, N., Pouwelse, J. and Sips, H. (2010) ‘Peer selection strategies for improved QoS in heterogeneous BitTorrent-like VoD systems’, Proceedings of IEEE International Symposium on Multimedia, December, Washington, DC, USA, pp.89–96.

Atechian, T., Torbey, Z., Bennani, N. and Brunie, L. (2009) ‘CoFFee: cooperative and InFrastructure-free peer-to-peer system for VANET’, Proceedings of the 9th IEEE International Conference on Intelligent Transport Systems Telecommunications, October, Lille, France, pp.510–515. Bai, X.Y., Ye, X.M., Li, J. and Jiang, H. (2009) ‘VLS: a mapbased vehicle location service for city environments’, Proceedings of IEEE International Conference on Communications, June, Dresden, Germany, pp.1–5. Barberis, C. and Malnati, G. (2011) ‘Design and evaluation of a collaborative system for content diffusion and retrieval in vehicular networks’, IEEE Transactions on Consumer Electronics, Vol. 57, No. 1, March, pp.105–112. Cao, J., Zheng, H. and Yuan, J. (2009) ‘Randomness betters nearest-rarest in the P2P clustering networks’, Proceedings of the 5th IEEE International Conference on Wireless Communications Networking and Mobile Computing, September, Beijing, China, pp.1–4. Chang, G.Y., Sheu, J.P. and Wu, J.H. (2010) ‘Typhoon: resource sharing protocol for metropolitan vehicular ad-hoc networks’, Proceedings of IEEE Conference on Wireless Communications and Networking, April, Sydney, Australia, pp.1–5. Chen, K.H., Dow, C.R. and Lee, Y.S. (2010) ‘HarpiaGrid: a reliable grid-based routing protocol for vehicular ad-hoc networks’, Journal of Information Science and Engineering, Vol. 26, No. 3, May, pp.817–832. Dow, C.R., Hsuan, P., Lee, Y.H., Lee, Y.T. and Huang, C.Y. (2010) ‘An efficient data circulation and discovery scheme in VANETs using public transportation systems’, Proceedings of IEEE International Conference Network and Services Management, October, Niagara Falls, Canada, pp.286–289. Dutta, N. (2010) ‘A peer-to-peer based information sharing scheme in vehicular ad-hoc networks’, Proceedings of IEEE International Conference on Mobile Data Management, May, Kanas City, Missouri, USA, pp.309–310. Guo, L., Chen, S., Xiao, Z., Tan, E., Ding, X. and Zhang, X. (2007) ‘A performance study of BitTorrent-like peer-to-peer systems’, IEEE Journal on Selected Areas in Communications, Vol. 25, No. 1, January, pp.155–169. Hong, P.T., Park, H. and Kang, C.H. (2011) ‘a road and traffic-aware routing protocol in vehicular ad hoc networks’, Proceedings of the 13th IEEE International Conference on Advanced Communication Technology, February, Busan, Korea, pp.24–28. Karp, B. and Kung, H.T. (2000) ‘GPSR: greedy perimeter stateless routing for wireless networks’, Proceedings of the 6th Annual IEEE/ACM International Conference on Mobile Computing and Networking, August, Boston, USA, pp.243–254. Kawarasaki, M. and Suzuki, k. (2009) ‘Performance evaluation of cooperative peer selection methods for P2P video-ondemand’, Proceedings of IEEE Conference on Ultra Modern Telecommunications and Workshops, October, St.-Petersburg, Russia, pp.1–6. Lee, J.W., Lo, C.C., Tang, S.P., Horng, M.F. and Kuo, Y.H. (2011) ‘A hybrid traffic geographic routing with cooperative traffic information collection scheme in VANET’, Proceedings of the 21th IEEE International Conference on Advanced Communication Technology, February, Busan, Korea, pp.1496–1501.

278

C-R. Dow et al.
Stoica, I., Morris, R., Karger, D., Kaashoek, M.F. and Balakrishnan, H. (2001) ‘Chord: a scalable peer-to-peer lookup service for internet applications’, Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, August, San Diego, CA, USA, pp.17–32. Stutzbach, D., Rejaie, R. and Sen, S. (2008) ‘Characterizing unstructured overlay topologies in modern P2P file-sharing systems’, IEEE/ACM Transactions on Networking, Vol. 16, No. 2, April, pp.267–280. Tsoumakos, D. and Roussopoulos, N. (2003) ‘Adaptive probabilistic search for peer-to-peer networks’, Proceedings of IEEE International Conference on Peer-to-Peer Computing, September, Linkoping, Sweden, pp.102–109. Wang, Q., Hu, J. and Zhang, J. (2012) ‘Performance evaluation of information propagation in vehicular ad hoc network’, IET Intelligent Transport Systems, Vol. 6, No. 2, June, pp.187–196. Yang, X., Liu, J., Zhao, F. and Vaidya, F. (2004) ‘A vehicle-tovehicle communication protocol for cooperative collision warning’, Proceedings of the 1st Annual IEEE International Conference on Mobile and Ubiquitous Systems, August, Cambridge, MA, USA, pp.114–123. Zhang, Y., Zhao, J. and Cao, G. (2009) ‘Roadcast: a popularity aware content sharing scheme in VANETs’, Proceedings of the 29th IEEE International Conference on Distributed Computing Systems, June, Boston, Massachusetts, USA, pp.223–230. Zhao, B., Kubiatowicz, J. and Joseph, A. (2001) Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing, Tech Report UCB/CSD-01-1141, April, CA, USA.

Lin, P.J., Dow, C.R., Chen, S.C., Li, C.J. and Hwang, S.F. (2008) ‘An efficient anycast scheme for discovering K services in mobile ad-hoc networks’, Proceedings of the 5th ACM International Symposium on Performance Evaluation of Wireless Ad-hoc, Sensor, and Ubiquitous Networks, October, Vancouver, Canada, pp.33–37. Liu, B., Cao, Y., Cui, Y., Lu, Y. and Xue, Y. (2010) ‘Locality analysis of BitTorrent-like peer-to-peer systems’, Proceedings of the 7th IEEE Conference on Consumer Communications and Networking, January, Las Vegas, Nevada, USA, pp.1–5. Liu, C.L., Wang, C.Y. and Wei, H.Y. (2008) ‘Mobile chord: enhancing P2P application performance over vehicular ad-hoc network’, Proceedings of IEEE Globecom Workshop, December, New Orleans, LA, USA, pp.1–8. Liu, N., Liu, M., Chen, G. and Cao, J. (2012) ‘The sharing at roadside: vehicular content distribution using parked vehicles’, Proceedings of the 31st Annual IEEE International Conference on Computer Communications (IEEE INFOCOM 2012), March, Orlando, Florida, USA, pp.2641–2645. Olariu, S. (2007) ‘Peer-to-peer multimedia content provisioning for vehicular ad-hoc networks’, Proceedings of the 3rd ACM Workshop on Wireless Multimedia Networking and Performance Modeling, October, Chania, Crete Island, Greece, pp.1-1. Panichpapiboon, S. and Pattara-atikom, W. (2012) ‘A review of information dissemination protocols for vehicular ad hoc networks’, IEEE Communications Surveys & Tutorials, Vol. 14, No. 3, August, pp.784–798. Prinz, V., Eigner, R. and Woerndl, W. (2009) ‘Cars communicating over publish/subscribe in a peer-to-peer vehicular network’, Proceedings of ACM International Conference on Wireless Communications and Mobile Computing, June, Leipzig, Germany, pp.431–436. Ramzan, N., Quacchio, E., Zgaljic, T., Asioli, S., Celetto, L., Izquierdo, E. and Rovati, F. (2011) ‘Peer-to-peer streaming of scalable video in future internet applications’, IEEE Communications Magazine, Vol. 49, No. 3, March, pp.128–135. Ratnasamy, S., Francis, P., Handley, M., Karp, R. and Shenker, S. (2001) ‘A scalable content-addressable network’, Proceedings of ACM Special Interest Group on Data Communication, October, San Diego, CA, USA, pp.161–172.

Websites
Gnutella, http://rfc-gnutella.sourceforge.net/src/rfc-0_6-draft.html NS-2 network simulator, http://www.isi.edu/nsnam/ns SUMO-Simulation of Urban Mobility, http://sumo.sourceforge.net/ index.shtml



更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图