Effective Strategies for Cooperative Download to improve delivery ratio and time

Effective Strategies for Cooperative Download to improve delivery ratio and time

Effective Strategies for Cooperative Download

to improve delivery ratio and time

Rekha M S Department of CSE

BNM Institute of Technology Bangalore

Vehicular networks are spontaneously formed between moving vehicles equipped with wireless interfaces that could be of homogeneous or heterogeneous technologies. These Networks, also known as VANETs (Vehicular Ad hoc Networks), are considered as one of the ad hoc networks real life applications enabling communications among nearby vehicles as well as between vehicles and nearby fixed equipments, usually described as roadside equipment. Among the possible applications of infrastructure-based opportunistic vehicular networks, we focus on that of cooperative download.

In this paper, we focus on the download of large- sized files from the Internet. More precisely, we consider a urban scenario, where users aboard cars can exploit roadside Access Points (APs) to access the servers that host the desired contents. We consider that the coverage provided by the roadside APs is intermittent: this is often the case, since, in presence of large urban, suburban and rural areas, a

Mona K Asst.Prof

Department of CSE BNM Institute of Technology

Bangalore

pervasive deployment of APs dedicated to vehicular access is often impractical, for economic and technical reasons. We also assume that not all on-board users download large files all the time: indeed, one can expect a behavior similar to that observed in wired networks, where the portion of queries for large contents is small . As a result, only a minor percentage of APs is simultaneously involved in direct data transfers to downloader cars in their respective coverage area, and the majority of APs is instead idle.

Within such a context, we study how opportunistic vehicle-to-vehicle communication can complement the infrastructure-basedconnectivity, so to speed up the download process. We exploit the APs inactivity periods to transmit, to cars within range of idle APs, pieces of the data being currently downloaded by other vehicles. Cars that obtain information chunks this way can then transport the data in a carry&forward fashion, and deliver it to the destination vehicle, exploiting opportunistic contacts with it, as in Fig. 1. We remark that the concept of cooperative download in vehicular networks

Fig. 1.Example of cooperative download in an urban environment. Vehicle a downloads part of some content from AP A, through a direct link. The idle AP B then gives another portion of the same content to a local vehicle b. When b encounters a, vehicle-to-vehicle communication is employed to transfer to a the data carried by b

1. The cooperative download of contents from users aboard vehicles has been first studied in [1], that introduced SPAWN, a protocol for cooperative content retrieval and sharing among users aboard vehicles. However, their approach is hardly comparable with ours, as it (i) considers

   unidirectional traffic over highways, while we focus on more challenging urban environments, and (ii) proposes a solution inspired by peer to peer networking, assuming that all on-road vehicles are active down loaders of the same contents, whereas our work is more oriented to opportunistic communications.

   In [2], the upload of small-sized contents from vehicles to roadside gateways, rather than the large downloads we target.

   However, most of works focus on routing delay- tolerant information in vehicular networks, while none copes with the problem of cooperative download. Also, techniques for Medium Access Control it [3] utilizes the concept of cooperative communication tailored for vehicular networks, especially for gateway downloading scenarios. VC- MAC leverages the broadcast nature of the wireless medium to maximize the system throughput. The spatial and user diversity are exploited by the concurrent cooperative relaying to overcome the unreliability of the wireless channel in vehicular networks.

   In [4] propose a novel network coding based co- operative content distribution scheme called VANETCODE. The randomization introduced by the coding scheme makes distribution efficient. Their scheme also leverages on the broadcast nature of the wireless medium to expedite the dissemination of the encoded blocks amongst the one-hop neighbors and is entirely independent of routing.

   Finally, since we study the impact of the infrastructure deployment on the cooperative download, our work also relates to the topic of AP placement in vehicular networks. In [5], the authors studied the impact of random AP deployments on data routing in urban road topologies: we will prove that such an approach is inefficient when targeting cooperative download. More complex solutions for the deployment of APs over road topologies have been proposed in [6], to favor delay-tolerant data exchange among vehicles, and in [7], for information dissemination purposes.

2. In this we first devise a technique for APs deployment, based on vehicular traffic flows analysis, which fosters cooperative download. Then, we propose and evaluate different algorithms for carriers selection and chunk scheduling in carry &forward data transfers.

   APs deployment: urban roads are not all identical, as some are more congested than others, some are bidirectional and others one-way, some have higher speed limits than others. This must be taken into

   account when deploying APs, since diverse plannings of the infrastructure can yield dramatic differences in terms of download rate achieved by vehicles. APs deployment techniques must be thus devised to favor the cooperative download process among vehicles;

   Carriers selection: contacts between cars in urban environments are not easily predictable like in highway scenarios. Idle APs cannot randomly or inaccurately select vehicles to carry&forward data, as most of the chunks risk to be never delivered to their destinations. Choosing the right carriers for the right downloader vehicles is thus a key issue in urban cooperative download;

   Chunk scheduling: selecting which parts of the information should be assigned to carriers, and in particular choosing the level of redundancy in this assignment, plays a major role in reducing chunk losses in the system.

3. Let us first point out which are the major challenges in the realization of avehicular cooperative download system within complex urban road environments.

   • The selection of the carrier(s): contacts between cars in urban/suburban environments are not easily predictable. Idle APs cannot randomly or inaccurately select vehicles to carry data chunks, or the latter risks to be never delivered to their destinations. Choosing the right carrier(s) for the right downloader vehicle is a key issue in the scenarios we target;

   • The scheduling of the data chunks: determining which parts of the content should be assigned to one or multiple carriers, and choosing in particular the level of redundancy in this assignment, plays a major role in reducing the probability that destination vehicles never receive portions of their files.

     A.Carrier Selection

     Having deployed the APs over the road topology, we can address the carriers selection problem, i.e., answer to the following questions: which of the vehicles in range of an idle AP should be picked as carriers, if any? And which of the downloader cars should such carriers transport data for? Indeed, the key to the answers is to know in advance whether (and possibly when) one or more cars currently within coverage of the AP will meet a specific downloader vehicle, so to perform the selection that leads to the highest gain in terms of download rate. Also, by choosing carriers depending on their future contacts, the destination of the data becomes

     Bb

     Aa

     Bb

     Aa

     constrained to the elected carriers, and the second question above is inherently solved along with the first one.However, the movement of individual vehicles over urbanroad topologies cannot be

     significant characteristics of two production phases, and values, that store the contacts properties for all couples of production phases that share such characteristics. The key for two generic production

     precisely predicted, and we must rely on a

     phases ph

     andpk

     isa vector k(ph

     k ) of the

     , p

     probabilistic approach, leveraging again the constant large-scale mobility patterns of vehicular traffic flows. Wethus let each AP build a contacts map, exploiting historicaldata about contacts between cars, and use it to estimate themeeting probability between local and downloader vehicles. Inthe following, we first discuss how contacts map are structuredand constructed. Then, we present different carriers selectionalgorithms and detail how they exploit such contacts maps.

     Contacts map

     form

     where, t and v are the units (in degrees, seconds, and meters/second, respectively) used to discretize angles, time and speed. A couple of production phases is thus characterized by the identity of the AP involved in the second production phase, the time elapsed between the start of the two production phases, the direction of the two vehicles at the beginning of the respective production phases, and the difference between their speeds at that same time. We stress that the identity

     Aa

     We denote as pk the k-thproduction phase of of

     p

     Bb

     vehicle awith respect to AP A, i.e., the k-th of the disjoint time intervalsduring which vehicle a can steadily download data from A .From a specific APs perspective, we tag production phases aslocal if they involve that particular AP: as an example, h isa local production phase for AP B, b, h.On

     the other AP is not necessary, as the first production phase is always a local one.

     A value is instead a vector of four fields:

     1. nopps, the number of contact opportunities, i.e., the number of times that the AP observed a couple of production phases with characteristics as from

        the other hand, we label as fm the m-thforward

        ab

        phaseof vehicle b with respect to vehicle a, i.e., the m-th of thedisjoint time intervals during which vehicle b can steadilyforward data to vehicle a. We stress that both production andforward phases do not necessarily correspond to actual datatransfer, but just to contacts which could be exploited for datatransfer.We also use t() to indicate the time at which a productionor forward phase starts, and

        t() to tag its duration. Forproduction phases only, () denotes the historical direction ofmovement 1 of the vehicle at the beginning of the productionphase, and v() its speed at that same time.

        Bb

        Bb

        Structure.A contacts map is a data structure that provides an AP with information on the probability of contact between a vehicle involved in a local production phase and another vehicle.The contacts map at AP Ballows B to know the probability of contact between the local vehicle b and the generic vehicle a. In particular, AP B knows that b started a local production phase ph at time t(ph ), while

        the associated key;

     2. ncons, the number of actual contacts, i.e., the number of times that vehicles from the aforementioned couples ofproduction phases actually generated a forward phase;

     3. tdel, the average time elapsed between the start of thelast production phase and the start of the forward phase,when the latter has indeed occurred;

     4. tdur, the average duration of the forward phase, when it has indeed occurred.

     Bb

     , p

     Aa

     It is to be noticed that each AP builds its own contacts map, in which it stores only values associated to keys where the first production phase, as already said, is a local one.As an example, an AP B will only store values for keys of the type k(ph k ), h, b, k,A, a. The rationale is that local production phases are the only vehicle-to- infrastructure contacts that an AP can exploit for carriers selection, and are thus the only ones an AP is interested in recording data for.

     Carriers selection algorithms

     Bb

     Bb

     moving with direction (ph ) and speed v(ph );

     Aa

     Aa

     Aa

     Aa

     Bb

     p

     Aa

     also, let us assume B has been informed that a started a production phase pk with AP A at time t(pk ), while moving with direction (pk ) and speedv(pk ). Then, the contacts map at B allows to associate thecouple of production phases(ph , k )to historical data on the encounters between vehicles that had previously generated production phases at the two APs B and A with timings and mobility similar to those of b and a.

     More formally, a contacts map is a set of one-to- one associations between keys, that encode the

     Contacts map can be exploited by an AP to select local vehicles as data carriers for cooperative download,by retrieving their contact probability estimates with respectto downloader cars. Firstly, it is necessary that APs know which cars in their surroundings are interested in some content. Thus, every time a downloader vehicle starts a production phase, the fact that it is requesting data is attached to the usual information on the production phase that the local AP shares with other APs.

     1. set pequal to Pmin

     2. for each downloader vehicle a do

     3. if a is in range of B do

     4. if a is closer to B than previous direct downloaders do

     5. select a as destination for direct transfer

     6. select no vehicles as carriers for carry&forward transfer

     7. set pequal to

     8. done

     9. else

     Aa

     1. for each production phase pk ofa do

     2. until all on-going local production phases are not processed do

        Aa

        Aa

     3. update delivery potential pk 13 update carriers list k

     1. done

        Aa

     2. if pk is the highest potential computed for a do

        Aa

        Aa

     3. set aequal to pk 17 set aequalto k 18 done

     1. done

     2. if pais strictly higher than pdo

     3. select a as destination for carry&forward transfer 22 select vehicles in aas carriers for carry&forward transfer

     23 set pequal to pa 24 done

     1. done

     2. done

     Fig. 2.Pseudocode for carriers selection at AP B

     01 get next on-going local production phase phBb 02 set pbequal to a random value (0, 1]

     Aa

     03 add b to delivery potential pk 04 add b to carriers list kAa

     05 mark local production phase phBbas processed

     Upon selection of a destination for the carry & forward transfer, jointly with theassociated local carriers, an AP must decide on which portion of the data the downloader is interested in is to be transferred to the carriers. To that end, we assume that each content is divided into chunks, i.e., small portions of data that can be transferred as a single block from the AP to the carriers, and then from the latter to the destination. Since a same chunk can be transferred by one or multiple APs to one or more carriers, the chunk scheduling problem yields a tradeoff between the reliability (i.e., the probability that a downloader will receive at least one copy of a chunk) and the redundancy (i.e., how many copies of a same chunk are carried arond the road topology) of the data transfer.

     Global

     The Global chunk scheduling assumes that APs maintain pervehicle distributed chunk databases, similar to the time databases introduced before. These databases store information on which chunks have already been scheduled for either direct or carry & forward delivery to each downloader.

     The Global scheme, distributes the chunk scheduling among APs, since it forces an AP to pick a new, unscheduled chunk every time it performs a direct or carry&forward transfer. In other words, each chunk is scheduled for transfer just once in the entire network.

     Hybrid

     The Hybrid chunk scheduling, inallows overlapping

     between carry & forward transfers scheduled by

     Fig. 3. Blind pseudocode for pk , k update

     Aa Aa

     Aa

     01 get next on-going local production phase phBb 02 get key k(phBb, pk )

     1. if a contacts map entry for such key exists do

     2. get relative value {nopps, ncons, tdel, tdur} 05 set pbequal to nopps/nopps

     Aa

     1. add b to delivery potential pk

     2. add b to carriers list kAa 08 done

     09 mark local production phase phBbas processed

     Aa

     Aa

     Fig. 4.p-Drivenpseudocode for pk k update

     Aa

     01 get next on-going local production phase phBb 02 get key k(phBb, pk )

     1. if a contacts map entry for such key exists do

     2. get relative value {nopps, nopps, tdel, tdur} 05 set pbequal to nopps /nopps

     Aa

     06 if b is equal to or greater than Pinddo 07 add pbto delivery potential pk

     08 add b to carriers list kAa 09 done

     1. done

     2. mark local production phase phBbas processed

     different APs.

     Local

     The Local chunk scheduling is similar to the Hybrid scheme, since different APs can schedule the same chunks when delegating data to carriers.However, as shown in it also allows overlapping between direct and carry & forward transfers.

     Adaptive Chunk Scheduling

     For Each chunk of the content a timer value is started in the Download server. The timer value is an indication of how much time, the chunk is not yet copied to requested Vehicle. Once the chunk is copied , the time value is closed. Vehicles once chunk is got, updates the feedback to download server. Based on the time value, more copies of chunks are introduced in the carrier Vehicles The algorithm to adaptive, Copies of Chunk in network increases as the transfer rate is lower, so that requested Vehicles will find the chunk to download in lot many places with high probability. Due to this effect, the data transfer rate will increase.

     Aa

     ,

     Aa

     Fig. 5.p-Constrainedpseudocode for pk k update

     1. Chunk Scheduling

     2. AP deployment

     The placement of APs over the urban road topology has a major influence on the cooperative download architecture. In order to capture such an effect, we extend our analysis by considering diverse AP deployments over the different road topologies presented above. The goal of all the deployment strategies is to position, along a road topology.

     The Cross volume-based AP placement is designed to favor carry&forward transfers, by increasing the potential for collaboration among vehicles. This technique exploits the predictability of large-scale urban vehicular traffic flows, which are known to

     follow common mobility patterns over a road topology . By studying such traffic dynamics, it is possible to determine the way vehicular flows spread over the streets layout and employ this information to guide the AP placement. In the remainder of this section, we introduce the concept of cross volume and employ it to determine the relative AP deployment strategy. Let us imagine that the road topology is represented by a graph where vertices are mapped to intersections and edges to streets connecting them, as in Fig 6. The graph is undirected, and an edge exists even if the corresponding road is one-way. Focusing on a particular edge i of the graph, we can track all traffic leaving such edge6, in both directions, and draw a map of how vehicular flows (measured in vehicles/s) from i unfold over the road topology.

     We refer to these flows as the vehicular flows generated at i. As an example, in Fig. 6, the dark grey arrows depict flows generated at edge i.

     Different flows have different size, in vehicles/s, represented by their associated number (values in the example are only illustrative).

     Let us now consider a generic edge k i, and isolate the flows passing in strict sequence through i and

     k. In this case, we distinguish the two directionsof movement over k, and define two traversing flows from i to k:

     the vehicular flow generated at i and subsequently traversing k in the direction;

     the vehicular flow generated at i and subsequently traversing k in the direction.

     Assuming a travel time = 1 at all edges, the partial cross volume hk is equal to min{6, 4} + min{0, 0}

     ij

     = 4, while the crossing volume hij is 4 + 3 = 7

     Traversing flows at an edge k can be translated to traversing volumes (measured in vehicles), by evaluating the average time vehicles spend to travel over the entire road segment corresponding to edge k.

     By considering both sets of flows at once, we can define the partial cross volume of i and j at k, as

     Finally, the concept of cross volume can be unbound from intermediate edges and related to couples of roads only. If I is the set of edges in the road topology graph, we define the cross volume of i and j as

     ij

     which implies that hk = hji 0, i, j I. The cross volume hij provides a measure of the potential for contact, and thus cooperation, over the entire road network, among vehicles leaving edges i and j.

4. We selected real-world road topologies to assess the performance of the cooperative download solutions.

   The main metrics we are interested in evaluating are:

   • thedownload rate, i.e., the average file transfer speed experienced by downloader vehicles traveling through the scenario. Such rate is the aggregate of a direct rate, due to direct data downloads from APs, and a cooperative rate, due to carry&forward transfers.

     Fig. 6. Sample vehicular flows over a road topology graph. Flows generated at edge i are dark grey, while those generated at j are light grey.

   • theundelivered chunk ratio, i.e., the average ratio of chunks that are not delivered to a downloader vehicle, computed over all those scheduled for that vehicle.

We presented a study of cooperative download in urban vehicular environments, proposing solutions for APs deployment, carriers selection and chunk scheduling. We proved the feasibility of cooperative download and demonstrated the significant performance improvements it can bring to users.

1. A. Nandan, S. Das, G. Pau, M. Gerla, M.Y. Sanadidi, Co-operative downloading in vehicular

   ad-hoc wireless networks, WONS05, St.Moritz, Switzerland,January 2005.

2. J. Zhao, G. Cao, VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks, IEEE INFOCOM06, Barcelona, Spain, April 2006

3. J. Zhang, Q. Zhang,W. Jia, A novel MAC protocol for cooperative downloading in

   vehicular networks, IEEE GLOBECOM07, Washington, USA, December 2007.

4. S. Ahmed, S.S. Kanhere, VANETCODE: network coding to enhance cooperative downloading in vehicular ad hoc networks, ACM IWCMC06, Vancouver, Canada, July 2006.

5. G. Marfia, G. Pau, E. Giordano, E. De Sena, M. Gerla, Evaluating vehicle network strategies for downtown Portland: opportunistic infrastructure and importance of realistic mobility models, ACM MoBiOpp07, San Juan, Puerto Rico, June 2007.

6. Y. Ding, C. Wang, L. Xiao, A Static-Nod Assisted Adaptive Routing Protocol in Vehicular Networks, ACM VANET07, Montreal, Canada, September 2007.

7. C. Lochert, B. Scheuermann, C. Wewetzer, A. Luebke, M. Mauve, Data aggregation and roadside unit placement for a vanet traffic information system, ACM VANET08, S.Francisco, USA, September 2008.