Need detailed review on Following Topic.

Content Dissemination Over VANET: Boosting Utility Based Heuristics Using Interests

Osamah Dhannoon, Rahul Vishen, Marius C. Silaghi Florida Institute of Technology (FIT)

Abstract—While drivers are not expected to vote while driv- ing, VANETs can be an excellent media for dissemination of decentralized regional polls and for pre-recorded votes/opinions on regional issues in a decentralized opinion poll. We pro- pose and evaluate heuristics for scheduling messages in a VANET broadcasting-based dissemination of decentralized opin- ion polling data among self-interested participants. The goal of the heuristics is to increase dissemination of the polling data and results under the given assumptions. The self-interest of participants is assumed to be manifested by selectivity in the storage and forwarding of topics and opinions for those topics.

The report starts by describing the concepts enabling the fully decentralized organization of the polls. The underlying protocol that we implemented for fully decentralized polling of opinions over VANETs is also introduced and evaluated.

I. INTRODUCTION

A protocol is proposed for dissemination of decentralized opinion polling over wireless, Vehicular Ad-hoc Networks (VANETs). When regional opinion polls are organized in a decentralized fashion, vehicle to vehicle (V2V) communica- tion can be exploited for exchanging pre-recorded votes in neighborhoods (without the drivers being required to interact while driving).

VANETS are composed of wireless devices found in moving cars. Each of these devices can communicate with other devices found in its proximity. Common devices with powerful receivers can record messages sent from emitting devices found hundreds of meters away. A fully decentralized polling can be based on a decentralized authentication and census mechanism. Each device is owned by a self-interested user and we assume that the system is open, which implies that a user has full control over her device and its software.

Since they have full control, self-interested participants can refuse to store and forward information related to polls in which they are not interested. They can also refuse to store and disseminate opinions that they do not share. The communication model assumes that each device broadcasts data it wants to disseminate and simultaneously listens and processes data broadcast by passing-by devices. A challenge is to design heuristics for selecting what to emit to maximize dissemination of polling data under the working assumptions.

We evaluate heuristics that broadcast data either with uni- form randomness, or favoring certain types of items such as: new votes, personal votes, votes similar to the personal votes or the intersection between the interests of the sender and the ones of potential receivers. Some input for these heuristics may come from information about interests of peers, and potentially

their GPS location and velocity (bearing and speed). For efficiency, once packed, data can be broadcast several times. A set of queues are maintained to implement these heuristics.

To enable comparison between the described heuristics, a utility model is introduced where the dissemination of each item is associated with a numerical value. For example, the utility value for disseminating personal votes and opinions can be considered to be the highest, followed by the utility value for disseminating votes with choices similar to the personal ones. The average utility value for disseminating opposing opinions is assumed smaller, but for various users it can be either positive or negative (based on whether they want their choice to succeed by any mean, or they are principled and ready to submit to the opinion of others, or they are open and willing to learn from other’s justifications and to eventually change their minds). The utility for disseminating votes on which the current user abstains can be assumed in certain experiments to have an average value between the utility for similar opinions and opposing opinions. The impact of the actual numerical ranges of these utilities on results can also be evaluated.

After presenting the background and related work, we con- tinue by introducing a sample application involved in decen- tralized polling and a sample data model for the storage of each node. Subsequently we present the protocol for broadcasting in terms of message components and their semantic. In section Heuristics we discuss the tested techniques and the involved data structures. After describing the preliminary experimental settings and results, we end with conclusions.

II. BACKGROUND

The use of broadcast in high traffic areas is known to be challenging due to high rates of transmission collisions between data packets. This problem is known as the broadcast storm problem [1]. Several broadcasting protocols (such as DV-CAST) have been proposed to increase the performance of data transfer in various traffic scenarios for VANET ap- plications [2], [3], [4]. A statistical study of broadcasting between mobile nodes based on requests is available in [5] and implemented in Bluetella.

The Local Peer Group (LPG) clusters neighboring nodes to restrict dissemination range [6]. P2P sharing of content over VANETs based on data popularity is introduced in the Roadcast simulator [7]. It simulates delivery of relevant data (such as MP3 audio files) based on peer queries by applying information retrieval mechanisms. A VANET P2P file sharing

protocol called SPAWN (gossiping) is introduced by [8]. Implementing CarTorrent in a real world scenario is reported in [9] which describes field tests for the SPAWN protocol and exchanges file chunks based on the AODV protocol.

A set of so called Road-Based Vehicular Traffic (RBVT) routing protocols on city roads use current traffic data to initiate the end-to-end communication paths [10]. VANET data dissemination can provide vehicles with parking spots availability [11]. The Traffic View [12] project uses VANET communication to share traffic information among cars moving on roads. It can disseminate road assessments (such as foggy weather) helping to find the best route to a destination. The system aggregates data in packets, to increase efficiency.

CodeTorrent [13] is another protocol for P2P file sharing over VANETs. It aims to decrease file downloading time.

The Segment-Oriented Data Abstraction and Dissemination (SODAD) [14], aims to increase the communication range be- tween vehicles for exchanging traffic safety data, and utilities information (e.g. locating gas stations). SODAD is used in the Self-Organizing Traffic Information System SOTIS.

III. SAMPLE APPLICATION

The proposed ideas are experimented within the framework of a P2P social network called DirectDemocracyP2P [15]. The system makes possible a fully decentralized opinion polling process.In this application, information is linked to entities called peers and organizations.

Definition 1 (Peer): The set of software agents that coordi- nate publicly to represent a given user is referred here as peer. A peer may have agents running on various devices (laptops, desktops, phone of a user) and which share the same public and secret key pair. The peer is globally identified by its public key.

Definition 2 (Organization): An organization is an entity defining the mechanism whereby an authority is defined for specifying and controlling eligibility for voting on a set of issues. An organization is defined by the unchangeable set of parameters describing its governance and function. This unchangeable characteristic is captured in its global identifier.

Each organization describes rules for deciding who is ex- pected to interact (the constituency) and the relevant issues (ju- risdiction) that should be raised and supported in the respective group. The organization can be authoritarian, where an ini- tiator controls the definition, interpretation and application of these rules, or grassroot where the definition is fixed while the interpretation and application of the rules is enforced directly by participants via collaborative filtering [16]. Scalability of the reciprocal verification of members of a constituency (via witness stances) is enhanced by organizing these members in hierarchical neighborhoods.

In DirectDemocracyP2P, issues raised and for which support is sought are called motions. Constituents can disseminate both endorsement and opposition signatures for motions (while peer agents typically only store the last signature submitted by each constituent for each given motion). Each signature may refer to one justification, while one justification can be referred to by

multiple signatures. Each of the aforementioned types of stand- alone entities: peers, organization, constituent, neighborhood, witness stance, motion, justification, and signature, has an identifier that can uniquely distinguish it from other entities, and can be separately exchanged among peers in atomic messages. Other entities exist, such as: news, translation, tester, mirror, plugin data.

A. Data Model

Each self-interested software agent stores the data related to its own interest into a local database. The agent stores the received data if it refers to organizations, neighborhoods, constituents and motions of interest. By default, received defi- nitions of peers and definitions of organizations received from non-blocked peers are stored. This gives users an opportunity to inspect and define their interest about them.

The database schema allows for storing the following types of items that have a stand-alone semantic and that are digitally signed, individually, by the entity generating them: peer, organization, neighborhood, witnessing, motion, justification, vote.

Each item, is tagged with three user controlled flags: blocked, broadcastable, interest. These flags control the communication as described in the next section. Each received data item is also associated with the arrival time, which is the date of the latest registered change to the digitally signed parameters of the item. The signed parameters of each item contain the creation time, which is the data when the signature was issued. The creation time is used to compare and select the newest item among items whose parameters change over time, such as active constituent, vote, and authoritarian organization.

For the case where an attacker or mistake leads to two distinct versions of the same item claiming the same creation time, the comparison is made on the hash of the data. This is used to prove that at convergence all participants have coherent databases.

In this paper we describe how such entities can be ex- changed between peers on devices traveling in vehicles and connected via Ad-Hoc wireless connections.

IV. PROTOCOL

Let us now describe the structure of the exchanged mes- sages. Software agents found on wireless enabled devices with ad-hoc capabilities are assumed to broadcast messages continuously (potentially with short pauses).

a) Communication control: The default settings of our current implementations assume that a self-interested receiver normally refuses to store items about unknown organizations, as well as items relating to organizations, constituents, neigh- borhoods or motions that are specifically blocked by the user. To refuse items about unknown organizations, newly received organizations are blocked by default. Organizations where the user registers are automatically unblocked.

By default, all the stored data about items that are not blocked is made available for broadcasting, but that behavior

can be manually controlled for each item using a flag called broadcastable.

For example, if an organization is blocked, then we store only its parameters but any extra data associated with it (e.g., constituents, neighborhoods, motions) are discarded. Similarly we handle blocked constituents, neighborhoods, or motions.

Messages received can refer to the GID of an unknown item (constituent, neighborhood, motion, justification). If users decide to store the item referring to unknown GIDs, then temporary items are created for each of the unknown GIDs, to enable their control (blocking, broadcastability). The enabling of certain temporary items, such as temporary constituents, open the door for Storage Attacks, namely where attackers attempt to fill users databases with data that is more difficult to verify. If temporary data is enabled, then remaining data for temporary items can be advertised as requested in subsequent broadcast messages. Various mechanisms (such as references to source peers) can be used to mitigate these attacks.

Items of particular interest to the user, such as motions, con- stituents or organizations that the user is particularly involved with, can be announced as interests in broadcast messages. This feature can inform cooperating peers, which can thereby give priority in sending such data back to the user. To enable this feature, each stored item is associated with the interest flag that the user can manually set and that the system can use to generate the corresponding interest information in messages.

b) Messages: Each broadcast message contains a self- contained information. The two most complex types of mes- sages are the ones carrying votes and the ones carrying witness acts (since they include data about many other types of items but are not included in other types of data).

A message containing a witness act consists of a tuple 〈p, o, cs, Ns, cd, Nd, w〉 describing the definition of the rele- vant organization o, the definition p of the peer that created the organization, the definition cs of the constituent making the witness stance, the definition cd of the constituent for which the witness stance is made, the definition w of the witness stance. It also contains the set of definitions of ancestor neighborhoods Ns of the neighborhood of cs and the set of definitions of ancestor neighborhoods of the neighborhood of cd.

A message containing a vote consists of a tuple 〈p, o, c, N, m, j, v〉 describing the definition of the relevant organization o, the definition p of the peer that created the organization, the definition c of the constituent making the witness stance, the definition m of the motion, the definition j of the justification and the definition v of the vote. It also contains the set of definitions of ancestor neighborhoods N of the neighborhood of the c.

Each broadcast message is also attaching a set of interest hints. This set contains some of the GIDs of the organizations, neighborhoods, constituents and motions that the user has marked with the interest flag.

Probabilistically, the data concerning the details of the organization, the peer or the constituent can be dropped from a vote message or a witness message to reduce some of the

replication, with the risk of rendering some messages useless (as those messages may be dropped by receivers missing one of the items required for storing it: its organization, neighborhood, etc.).

c) Handling: Here we describe reference procedures for handling received messages. In Algorithm 1 we introduce the method used by a software agent to manage the knowledge it has about interests of peers found in passing-by cars. An interest consists of the GID of an organization, neighborhood, constituent, or motion. Whenever indication of a particular interest is received from a peer, it is stored locally, tagged with the GID of the sending peer and an expiration time. The expiration time is computed based on the arrival time of the message containing this interest, the available information about the relative speed between that peer and the vehicle of the users, and an estimation of the maximal distance within which the two devices can communicate.

When the devices are not equipped with GPS (as in the experiments reported here), then the computation simply re- turns the estimated expiration time as the sum between the current time and a constant life_span (Line 1.3). In our experiments this constant is set to 1 second. Note that each time that a message is received from the same peer, the expiration time of its interests is updated, thereby accounting for devices that are reachable for a longer period of time than the selected life_span constant.

A variable min_interest stores the current time, up- dated on the clock (Line 1.5) and any interests with higher expiration time is removed at that moment (Line 1.6).

Algorithm 1: Management of interest without GPS 1.1 procedure handle interests (Peer, interests) do 1.2 for i in interests do 1.3 set interest-value(i, min interest+life span);

1.4 procedure on clock() do 1.5 min interest++; 1.6 drop expired interests;

Next we describe the algorithms used to handle received witness and vote messages (Algorithms 2 and 3). Similar and simpler algorithms are used to handle messages carrying other types of items.

The algorithms for handling messages employ the pro- cedure handle_interests() defined in Algorithm 1, and a procedure verifySignature(item) that is checks the signature of the item passed in parameter, quitting on failure. The procedure store-or-update(item) verifies whether a previous version of the item is already available and whether its creation date is newer than the received item. On failure it store the item (if no other version was found), or updates it (if a version with earlier date or identical date but lexicographically smaller digest value is found);

Before handling any item, first the software agent checks whether the item is not blocked by the user (i.e., by being

Algorithm 2: Receiving and Handling a Witness 2.1 Onwitness(Peer, interests, (p, o, cs, Ns, cd, Nd, w))

handle interests(Peer, interests); 2.2 if !verifySignature(p) then return store-or-update(p); 2.3 if (blocked(p)) then return 2.4 if !verifySignature(o) then return store-or-update(o); 2.5 if (blocked(o)) then return 2.6 for n in Ns do 2.7 if verifySignature(n) then 2.8 store-or-update(n); 2.9 if (blocked(n)) then return

2.10 for n in Nd do 2.11 if verifySignature(n) then store-or-update(n) 2.12 if !verifySignature(cs) then return store-or-update(cs); 2.13 if (blocked(cs)) then return 2.14 if !verifySignature(cd) then return store-or-update(cd); 2.15 if verifySignature(w) then store-or-update(w)

Algorithm 3: Receiving and Handling a Vote 3.1 Onvote(Peer, interests, (p, o, c, N, m, j, v))

handle interests(Peer, interests); 3.2 if !verifySignature(p) then return store-or-update(p); 3.3 if (blocked(p)) then return 3.4 if !verifySignature(o) then return store-or-update(o); 3.5 if (blocked(o)) then return 3.6 for n ∈ N do 3.7 if verifySignature(n) then 3.8 store-or-update(n); 3.9 if (blocked(n)) then return

3.10 if !verifySignature(c) then return store-or-update(c); 3.11 if (blocked(c)) then return 3.12 if !verifySignature(m) then return store-or-update(m); 3.13 if (blocked(m)) then return 3.14 if !verifySignature(j) then return store-or-update(j); 3.15 if verifySignature(v) then store-or-update(v)

generated by a blocked peer, or constituent, or for a blocked organization, neighborhood, motion, justification, or choice for the motion).

The procedures to handle messages start by handling first the more basic types of items before handling the ones that are based of the first. The typical order is: peer, organization, constituent, neighborhood, motion, justification, vote. Note that there can be a circular relation between constituent and neighborhood since a constituent may reside in a neighborhood and the neighborhood is supported/created by a constituent (potentially the same). In this case the two are stored only either if they are simultaneously available, or if storage of temporary items is enabled (as discussed earlier).

V. HEURISTICS

To model incentives and their relation with the behavior of the users, we formalize the utility of a message. In practice each item has its own utility, and a different utility for different users.

Definition 3 (Utility of messages): Each user draws a certain utility for learning an item, depending on that item. A user also gains a given utility for disseminating an item. In the following we assume that the utility of storing items is flat for the items in an organization, while the utility of forwarding an item depends of its similarity with the items generated by the user (and therefore describing her values).

d) Uninformed heuristics: for broadcasting correspond to an assumption that hints received from peers are not trusted, and transmission is made based on an a priori model of frequency for encountering vehicles with peers traveling in the two directions. With uninformed heuristics, all peers are assumed to be interested in all items that the current peer has, and to be able to store all messages that they receive from this user. Such a model assumes that a number of A reachable vehicles travel in the same direction with a relative speed vA while a number of B reachable vehicles travel at each moment in opposite direction with relative speed vB. The local computer is able to load new items from a local database with an efficiency of M messages a second. Messages (each with utility uM ) can be emitted at a speed of vM messages a second from a sending queue of size Bs, the buffer of the queue being reloaded from database at a period of time:

Preload ≥ Bs

min(vM, M) . (1)

If D is the communication range of the device then TA = D vA

is the duration for which a car traveling in the same direction is reachable, and TB =

D vB

is the similar duration for the opposite direction. We also assume that the assumption that the queues of preloaded messages used for sending data are long enough to provide data for the whole time TB, i.e.,

Bs vM

≥ D

vB . (2)

Then, the utility of sending data during time TA is:

UTA = uM·A·Bs·d TA

Preload e + uM·B·

TA TB

·TB·vM

where the first part of the right hand expression refers to the utility obtained by sending items to cars in the same direction (cars that each receive the content of d TA

Preload e full buffers

of messages, each of size Bs). Note that in this equation we assume that the reminder of Preload : TA is larger than

Bs vM

. The second part of the expression is the utility from the items transmitted to cars driving in opposite direction. There are TA

TB road segments of size D with such cars that travel in opposite direction, each holding B cars, and each of these cars receives vM·TB messages.

If one set Preload to the closest (smaller) divisor of TA, then the utility rate per unit of time that the agent gets for

broadcasting from a given queue of messages in this condition is approximated to (obtained by dividing UTA by TA):

∂U

∂t = uM

( A·Bs Preload

+ B·vM )

(3)

The current peer has a number NP of personal items, a number NS of similar items, a number NO of other items and a number NF of opposing opinions of positive utility (opposing opinions of negative utility are not sent). An assumption is that NP � NO. Based on this model we search for the best policy in terms of number of times that items with high utility should be broadcast before broadcasting some items with a lower utility.

e) Informed heuristics: assume that peers announce their interests as sets of GIDs for organizations, constituents, neigh- borhoods, motions or justifications for which they want to get related items, and that they drop any other messages. Senders thereby build special queues with data of interest to these peers and give these messages priority over other items. In our experiments, agents broadcast only data relevant to current peers and found in current queues.

Each message loaded in sending queues is tagged with information about contained organizations, constituents, neigh- borhoods, motions, justification (and potentially vote choice), to help dynamically retrieve those of interest to new detected peers.

While our experiments were run with laptops that were not provided with GPS sensors, such sensors can provide extra information as to when the peers travel in the same direction or in opposite direction, and for how long the peer be reachable.

Fig. 1. Architecture of the Peer

Our utility model can be combined with the statistical model of the efficiency of communication described at uninformed heuristics (as shown in the Experiments section), to decide the policy of transmission for each type of data (what percentage of each type of data should be sent at each moment of time). One can select the ratio of data of each type such as to maximize the expected utility of the sender. Rather than using the model resulting in Equation 3, one can introduce utilities in decisions based on the statistical models in [5].

VI. AGENT ARCHITECTURE DETAILS

We performed experiments with our implementation of a VANET platform, based on agents running on laptops that are located in moving vehicles. We allocate an Ad- Hoc wireless cell based on the open (unencrypted) SSID DirectDemocracy at Frequency 2.462 GHz resulting in the cell 46:32:D1:F2:88:67. The architecture of the server is depicted in Figure 1. Each agent starts a server bound to local port UDP/54321 and accepting broadcast messaged. Our experiments were done with the Network ID of the network card set to “10/8”. The local Host ID part of the IP is set to a random value. If the random part of the IP is considered insufficient to avoid IP collisions between peers, an additional random identifier is also generated to uniquely detect the agent, and messages tagged with this identifier can be discarded assuming that their source is the agent of the server. When the device has more than one wireless card, the agent can be configured to only use a subset of them for this protocol. Each agent has a client that broadcasts messages on the network interfaces allocated to our protocol, sending them to the address “10.255.255.255:54321” from a set of queues prepared with preloaded messages. A small pause (e.g. 5 ms) can be introduced between the transmission of packets, as this was found to slightly improve transmission rates as well as CPU load (see the section Experiments).

Each of the queues with preloaded messages has a special policy as to the type of contained items (personal, similar to personal, recent, random, round-robin, requested) and its mechanisms for loading and reloading. The broadcast client picks items from the various existing queues based on a probability distribution that can be specified by the user. We experiment with various heuristics for specifying these probabilities. To maximize its dissemination efficiency, the probability of sending items of interest must grow with the number of receivers having expressed that interest (potentially serving only the items of interest to most current peers). Before broadcasting a message, the client prepends to it a header describing: the interests of the current user, its random identifier, and available GPS data about current location and velocity. Potentially this header can include extra information about the content of the body of the message (such as GIDs of organizations, motions, etc) to help receivers decide faster on storing or dropping messages that are not of interest. The existence of peers that drop messages not tagged with interest could push self-interested agents to provide this extra information (which otherwise reduces their bandwidth).

The servers may not be fast enough in handling and storing all the data they can receive in real time and therefore incoming data is stored in buffers. Our server has a receiving buffer of size Br set to 20000 messages (average message size being measured to be 5kB in the current experiments). The server extracts the interests advertised by peers from the header of received messages and enqueues all the message bodies deemed new based on their size (or hash). A separate storing thread is used to dequeue received messages and to

Time (minutes)

2

2

2

2

Fig. 2. Experiments measuring the speed of messages transmitted (vM ). Averages for duplex communication is: 3ms pauses at 10.2 msg

sec , 5ms pauses

at 10.78 msg sec

, and 10ms pauses at 9.97 msg sec

store their data based on the aforementioned algorithms. If the receiving buffer is full, until the internal storing thread

frees some entries, the server drops new incoming messages except if they are tagged in their header with information specifying that they contain items of interest to the receiver (in which case these messages are used to replace untagged messages from the buffer).

VII. EXPERIMENTS

Our implementation can run on Linux, Windows, and Ma- cOS. The network configuration is automated on Linux and Windows while the MacOS network configuration has to be performed manually.

For the reported measurements, the databases of the agents were filled with 60000 votes for 10 organizations (O1 to O10) and 3816 motions, 9094 justifications, 629 constituents, and 4486 witness stances. These numbers were chosen based on our estimation of the ratio of the various types of items in a deployed system. To generate these items we implement a simulator that allocates each new generated vote proba- bilistically. First we manually generated a certain number of organizations. Then, each generated vote is allocated to a new organization with probability 10−5, otherwise it is uniformly assigned to one of the existing organizations. Similarly, each vote is allocated with probability 10−2 to a new constituent. The size of the text of each artificially generated motion is 1000 characters and the size of each justification is 300 characters.

We performed experiments with transitive dissemination across several vehicles, validating the fact that data can be disseminated between cars that do not have direct contact. First we report numerical results about the measured characteristics of the communication between immediately connected nodes.

We measure the speed of communication vM between two nodes in ideal conditions (when the nodes are placed far from other wireless devices). Communication is measured between an HP G62-111EE with 3GB RAM and an Acer Aspire P5WE0 with 4GB RAM running Ubuntu 12.04 on

an I3 processor. Preliminary measurements were made with different pause duration (0, 3, 5, 10, 15, 250, 500, 750, 1000 ms) between transmitted packets. This pause impacts on the number of packet collisions, and therefore on the transmission efficiency. More extensive measurements were performed on the values that showed promise (3, 5, 10 ms). Measurements were taken over 25 minutes of communication for each pause duration and for each of the following two cases: when both devices transmit data. and when only one device transmits data. The results, averaged over a sliding window of size 30 seconds, are displayed in Figure 2. The maximum value of 26.7 messages per second for one direction broadcasting at 5 ms pause duration is used as reference.

roads speed TB M = vM ·TB Parking lot – crowded 15 15 158

Street – open area 40 4.3 50 Street – school area 35 2.6 15

Highway – free 70 6.3 91 Highway – trucks 70 4.5 34

TABLE I AVERAGE TIME OF ENCOUNTER (SECONDS) AND NUMBER OF

EXCHANGED MESSAGES IN THIS TIME FOR VARIOUS VEHICLE SPEEDS (MPH) AND ENVIRONMENTS, WITH COMMUNICATION IN ONE DIRECTION

(5 MS PAUSES)

We measure an estimate of the range of communication D and of the time TB during which two devices are able to communicate. These measurements are performed with laptops found in two vehicles moving in opposite direction in several scenarios: in a parking lot (crowded) at 15 mph, on a city street in an open area (10 wireless networks) with median strip at 40 mph, on a city street close to a school (35 wireless networks) with median strip at 35 mph, on an empty highway with median strip at 70 mph, and on the same highway (with trucks separating the communicating cars). The measurement in the parking lot and on the city street were averaged over 10 encounters. The numbers of messages successfully transmitted in the three scenarios are shown in Table I, as well as the duration TB estimated from logs. It can be noticed that the speed of communication between devices is strongly influenced by the number of wireless networks in that area.

To have all messages available for a peer encountered while driving in opposite direction in a crowded parking lot, the sender needs queues of size Bs≥D·vMvB , which correspond to the maximum number of messages M in Table I.

f) Dissemination over chains of vehicles: To evaluate and confirm empirically the dissemination between vehicles that do not meet each other but communicate via other intermediary vehicles, we run experiments with three cars: A, B, and C. The car C contains a device with a preloaded database (as per the previous experiments) while the devices in the other two cars are initially empty. We evaluate two topologies of communication patterns between these vehicles: chain and triangle. For each topology the vehicles have a fix trajectory that they repeat 20 times, synchronized in such a way that pairs of vehicles meet at the same location. We evaluate the

0

100

200

300

400

500

600

700

800

900

1000

0 5 10 15 20

N u m

b e r

o f n e w

m e ss

a g e s.

Rounds

Car A triangle Car B triangle

Car B chain Car A chain

Fig. 3. Received items (votes and witness stances) for cars A and B in the chain and triangle topologies. The ratio votes to witness stances is approx 2:1.

Served Organization Interests

2 2

Fig. 4. Comparison of efficiency with and without advertisement of interests.

impact of the studied heuristics and of the user interests on the efficiency of dissemination.

The curves in the diagram in Figure 3 shows the number of new data items received and stored in each of the two cars during 20 rounds of encounters with the chain topology. We remark that the Car A chain curve shows that its device receives approximately 60% of what is received by the device in car B (see Car B chain). It is nevertheless logical to expect that the ratio would decrease with time and rounds due to the expected decrease in overlap between messages received by B from C, and messages sent by B when her database increases. The usage of queue handled (containing data recently received from other peers) is meant to mitigate this effect.

A comparison is made with the situation when the three cars communicate according to a triangular topology. We see that the number of messages received by the car B (and car A) in this topology is approximately 50% more than the number of messages received by car B in the chain topology.

g) Impact of Interests on Efficiency: We count the number of messages of interest to the receiver, successfully transmitted to a given peer, in scenarios with the studied peer

0

200

400

600

800

1000

1200

0 5 10 15 20

Nu m

be r o

f n ew

m es

sa ge

s.

Rounds

Car B with advertisements triangle Car B no advertisements triangle

Car A no advertisements chain Car B no advertisements chain

Fig. 5. Impact of interest advertisement.

expressing interests in two organizations, while other peers also express their interests. The graph in Figure 4 shows the number of received messages given the number of different interests considered by the sender. It can be observed that the efficiency for the receiver decreases with the number of interests submitted by neighboring peers.The other straight horizontal line in the graph shows the efficiency of the receiver when no interests are advertised by anybody and the sender transmits randomly data from its 10 organizations. Note that the efficiency of the server is given by the sum of the efficiency of its receivers, being expected to grow monotonically with the number of peer vehicles receiving its data. The efficiency of the sender in disseminating its data without advertisement of interest is smaller than with advertisement, except when all the available data is of equal interest to receivers.

With the computed parameters, when we use a single sending queue with randomly picked data or with round-robin transmission, the occurrence of personally generated items has a negligible probability and the utility is practically equivalent to sending only messages of type other. Assuming that the transmission of each item has a utility of 1c for the sender and the utility of a personally generated item is 10c, the obtained utility per second with A = 2 vehicles driving in the same direction and B = 2 vehicles traveling in opposite direction on a highway is ≈107 c

s (based on Equation 3). For the case

NP = 10, on a highway, the speed of sending messages with personal items has to be vPM ≥

Bs TB

= 10 3.4

≈ 3. Therefore the speed of sending the other types of messages (assumed to be all of type “other”) can be vmaxM − v

P M ≈ 23.7. The total

utility with this configuration is 117 + 95 = 212 c s

(117 c s

for personal messages). This proves that it is useful to separate messages into queues of specialized types (gaining 212 c

s rather

than 107 c s ).

h) Empirical Results with Interests: We ran experiments with the three cars (A, B, and C) where A is only interested in storing and forwarding the organizations O1 to O7, and B is only interested in storing and fowarding organizations O4 to O10. The impact of advertising their interests is shown in Figure 5, with an improvement of 28%, proportional with the ratio of interest in the available organizations. It can be seen that, when devices filter received data based on their interests, car A eventually receives a lower fraction (36%) of the data received by B than in the absence of such filtering (54%,

see Figure 3). Advertisement of interests compensates for this difference.

VIII. CONCLUSION

A set of techniques for dissemination of data in decentral- ized opinion polls via a Vehicular wireless Ad-hoc Network of self-interested peers is proposed and evaluated. For comparing heuristics we compute the utility of achieved dissemination from the perspective of a given sender. The long term goal is to find the behavior at equilibrium of self-interested senders. A utility model is discussed where the highest utility is for items generated by the sender, followed by items with similar opinion, while the least utility is assigned to items of opposing opinion (potentially negative utility).

Based on a set of experiments with our VANET imple- mentation we compute the parameters of a model for the vehicle to vehicle interaction. Strategies for broadcasting based on several queues are evaluated as well as percentages of broadcast time to allocate to different types of data items. The tested heuristics can be uninformed or informed with data received from peers such as their interests, identity, position and relative speed and bearing. Interests of peers are expressed in terms such as opinion (vote choice), issues (motions), voters (constituents), or topics (organization).

Separate outgoing queues can be maintained for data of different types (random, generated by sender, similar with sender, opposing senders, others). Cars traveling in opposite direction should get the most valuable data (generated by this sender) while cars traveling in the same direction and in contact for a long time should eventually fully synchronize with the sender on all items with positive utility and of interest to them.

REFERENCES

[1] Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” Wirel. Netw., vol. 8, no. 2/3, pp. 153–167, Mar. 2002. [Online]. Available: http://dx.doi.org/10.1023/A:1013763825347

[2] R. Kumar and M. Dave, “A review of various vanet data dissemination protocols,” Intl. Journal of u- and e-Service, Science and Technology, vol. 5, no. 3, pp. 27–44, Sep. 2012.

[3] O. Tonguz, N. Wisitpongphan, F. Bai, P. Mudalige, and V. Sadekar, “Broadcasting in VANET,” in Mobile Networking for Vehicular Envi- ronments, may 2007, pp. 7 –12.

[4] EUREKA, http://www.eurekanetwork.org/project/-/id/6252, 2010. [5] G. Karlsson, V. Lenders, and M. May, “Delay-tolerant broadcasting,”

IEEE Transactions on Broadcasting, vol. 53, no. 1, pp. 369–381, March 2007.

[6] W. Chen and S. Cai, “Ad hoc peer-to-peer network architecture for vehi- cle safety communications,” Communications Magazine, IEEE, vol. 43, no. 4, pp. 100 – 107, april 2005.

[7] Y. Zhang, J. Zhao, and G. Cao, “Roadcast: A popularity aware content sharing scheme in VANETs,” in ICDCS, june 2009, pp. 223 –230.

[8] A. Nandan, S. Das, G. Pau, M. Gerla, and M. Sanadidi, “Co-operative downloading in vehicular ad-hoc wireless networks,” in WONS, jan. 2005, pp. 32 – 41.

[9] K. Lee, S.-H. Lee, R. Cheung, U. Lee, and M. Gerla, “First experience with cartorrent in a real vehicular ad hoc network testbed,” in 2007 Mobile Networking for Vehicular Environments, may 2007, pp. 109 – 114.

[10] J. Nzouonta, N. Rajgure, G. Wang, and C. Borcea, “VANET routing on city roads using real-time vehicular traffic information,” IEEE Trans. on Vehicular Technology, vol. 58, no. 7, pp. 3609 –3626, sept. 2009.

[11] M. Caliskan, D. Graupner, and M. Mauve, “Decentralized discovery of free parking places,” in VANET, 2006, pp. 30–39. [Online]. Available: http://doi.acm.org/10.1145/1161064.1161070

[12] T. Nadeem, S. Dashtinezhad, C. Liao, and L. Iftode, “Trafficview: traffic data dissemination using car-to-car communication,” SIGMOBILE Mob. Comput. Commun. Rev., vol. 8, no. 3, pp. 6–19, Jul. 2004. [Online]. Available: http://doi.acm.org/10.1145/1031483.1031487

[13] U. Lee, J.-S. Park, J. Yeh, G. Pau, and M. Gerla, “Code torrent: content distribution using network coding in vanet,” in MobiShare, 2006, pp. 1–5. [Online]. Available: http://doi.acm.org/10.1145/1161252.1161254

[14] L. Wischhof, A. Ebner, and H. Rohling, “Information dissemination in self-organizing intervehicle networks,” IEEE Trans. on Intel. Transporta- tion Systems, vol. 6, no. 1, pp. 90 – 101, march 2005.

[15] M. C. Silaghi, K. Alhamed, O. Dhannoon, S. Qin, R. Vishen, R. Knowles, I. Hussien, Y. Yang, T. Matsui, M. Yokoo, and K. Hirayama, “Directdemocracyp2p: Decentralized deliberative petition drives,” in IEEE P2P, 2013.

[16] S. Qin, M. Silaghi, T. Matsui, M. Yokoo, and K. Hirayama, “Reputation system for decentralized population census,” in IJCAI WIT-EC, 2013.