The consequence is that only neighbors previously detected are considered, thereby minimizing estimation inaccuracies when shadowing is present. On one hand, underestimated transmission range values may lead to vehicles beyond the estimated set R still receiving the message broadcast. Clearly, letting these vehicles rebroadcast would result in an excessive number of transmissions occurring near simultaneously, since they have not been coordinated into different transmission priorities. Instead, we introduce the following policy.
This policy may increase the end-to-end delay but it maintains the protocol robust against collisions and contention. On the other hand, overestimated values may result in longer delays, since vehicles unnecessarily wait for the rebroadcast of other vehicles that actually did not receive any message. We tackle overestimated values by being conservative when assuming the maximum distance from the sender that neighbors are still able to receive a message. This can be done by requiring a low outage probability in the propagation model assumed [ 34 ].
In [ 4 ], we have extensively elaborated on positioning and transmission range estimation and showed by means of simulation that our approach is robust against errors for different time slot density values of t s d. In this work, our focus is rather on evaluating the new aspects of generalizing our approach to a multi-directional dissemination in both highway and urban scenarios. In this line, one potential source of error lies in the estimation of the number of directional sectors whenever the required mapping information is inaccurate or unavailable.
Inaccurate estimates of this value may lead to sub-optimal performance. On the one hand, if an excessive high number of sectors is employed, vehicles are assigned to sectors that do not represent any real road, thereby unnecessarily increasing the number of transmissions. On the other hand, choosing an excessive low number of sectors may lead to the suppression of transmissions of vehicles driving in potential road directions of dissemination, thereby causing higher delays and lower delivery ratio.
We elaborate further on these consequences later in the Performance evaluation section. With our proposed time slot scheme, selected vehicles are chosen to rebroadcast whenever new messages are received. In this way, messages are immediately disseminated throughout the network to every possible road direction. However, such a scheme still depends on additional measures to cope with disconnected networks when the transmission range does not reach farther vehicles in the each directional sector. To cope with radio gaps in the network, we rely on a store-carry-forward approach that is based on our previous single directional dissemination scheme named SRD protocol, presented in [ 5 ].
The general idea lies in assigning the responsibility of storing, carrying, and forwarding to vehicles located at the tail of a directional cluster, since these vehicles have the highest probability of meeting later other vehicles farther in the cluster direction. As we exemplified in Figure 2 , a vehicle is the tail of a directional cluster if there is no other vehicle farther in that direction. A vehicle can in fact be the tail of multiple directional clusters simultaneously, for example, when a vehicle divides its transmission range into four sectors in an intersection as it occurs with v 5 in Figure 2.
The complete AMD protocol combines both our proposed time slot broadcast suppression and store-carry-forward schemes, as shown in Figure 6. Every vehicle updates its local neighborhood information T n with the content received from either a beacon or a data message. When a data message is received, our time slot scheme is executed as defined by the diagram in Figure 5.
On the other side of the diagram, beacons are used to update the tail status of the receiving vehicle for each of its directional sectors. When a vehicle makes the transition from tail to non-tail in one of its directional sectors, it is an indication that there is now connectivity to farther vehicles in that direction and that previously stored messages can be relayed. Dividing the transmission range into directional sectors is a crucial task done by the sender in order to determine the rebroadcast priority of the receiving neighbors. Figure 7 shows how such division is done.
By convention, we define that the index number of directional sectors increases anti-clock wise as in the regular unit trigonometric circle. Both data messages and beacons have vehicle and message IDs to enable vehicles to distinguish different broadcast messages. An example of vehicle ID is the MAC address, while the message ID can either be a sequence number or a timestamp of the message generation time. This prevents both the circulation of old messages and that messages travel beyond the boundaries defined by the application.
As explained previously, in order for vehicles to suppress their scheduled rebroadcasts correctly, they must know whether an echo of a message comes from a vehicle that is farther in the directional sector defined by the previous sender. The performance evaluation of AMD is carried out by means of simulations. Our goal is to study the scalability of AMD under both highway and urban realistic scenarios. We select three state-of-the-art protocols for comparison, namely:. It uses one of the three suppression techniques proposed in [ 3 ]. In this work, we set DV-CAST to use the Slotted 1-Persistence suppression technique, which is the mechanism that has shown to achieve best performance in terms of end-to-end delay.
SRD : it is a protocol that we previously designed for highway scenarios in [ 5 ]. Just as with DV-CAST, it combines both a store-carry-forward approach and suppression technique to tackle disconnected and dense networks, respectively. UV-CAST : it is a protocol that specifically addresses urban scenarios with zero infrastructure support [ 7 ].
It combines 1 a suppression technique for dense networks that gives higher priority to vehicles near intersection points; 2 and a gift-wrapping algorithm to select vehicles to store, carry, and forward messages. Table 1 contains a summary of the simulation parameters. In the physical layer, we operate on the 5. Efforts put on selecting a proper transmission power value include the decentralized congestion control DCC mechanism as defined by the ETSI European standardization [ 37 ] that controls the network load by adjusting the transmission power level and transmission rate.
However, our goal here is limited to achieving a proper balance between choosing realistic values i. Here, we are interested in guaranteeing that multi-hop communication is used in our simulation scenarios in order to properly compare the protocols. Despite leading to higher delay, lower transmission ranges are clearly more suitable to meet this goal. In [ 4 ], we evaluate the effects of employing different power levels for different suppression techniques. Following this reasoning, we set the transmission power to mW to achieve approximately m of communication range when assuming the propagation model as described in the following.
Finally, we use the shadowing obstacle model proposed in [ 35 ] to simulate obstacles caused by the presence of buildings in urban scenarios. For all suppression mechanisms, we set the slot time st to 5 ms. The value chosen for Slotted 1-Persistence is based on simulation parameters used in [ 6 ]. The maximum additional delay D max used by Optimized Slotted 1-Persistence is set to 1 ms. For our suppression mechanism, we set the time slot density t s d to 1 and additional delay d to DIFS. Finally, we also map all the intersection points in our urban scenario to allow for a higher priority broadcast by vehicles near intersections, as required by UV-CAST.
For all simulation scenarios, the data message size is 2, bytes large, the maximum allowed by the This allows us to evaluate the protocols in the worst-case scenario in terms of medium occupation caused by the transmission of messages. Regarding the message generation frequency, we define that data messages are generated at every 2 s, i. Although this parameters should be adjusted according to the application requirements, our main concern in this evaluation is to choose a value that gives enough statistical relevance in terms of number of messages generated and at the same time achieve scalability in the simulations, i.
The size of beacons can vary from 24 bytes to the maximum message size depending on the message list included. Such limit is chosen based on the proper balance achieved between the number of unnecessary transmissions avoided due to loops in the network and beacon size in the scenarios considered in our simulations. However, further analysis is required to determine the most appropriate value for a wider variety of scenarios. Beacons are sent at the frequency of 1 Hz. This is usually the highest frequency expected to be used for the transmission of beacons [ 32 ], which gives the worst-case scenario in terms of freshness of the one-hop neighborhood information.
Furthermore, varying the beaconing rate in our experiments has not led to significant changes in our simulation results, except for more message collisions. We consider one highway scenario and one urban scenario. The highway consists of a 1-km straight road with two lanes in each road direction. Each message is generated by one fixed vehicle positioned in one end of the road and gathered by another fixed vehicle in the other end of road. For this scenario, in total 20 runs of s are executed. This segment has an area of 1. Messages are generated by one fixed vehicle in the center of the map and gathered by one of the four fixed vehicles that are positioned in each corner of the map.
Figure 8 shows the complete map fragment considered, where buildings represented by dark rectangles serve as radio obstacles. Simulations for this urban scenario consist of 20 runs of s. Both scenarios were created with SUMO [ 40 ]. Therefore, they includes realistic mobility patterns such as vehicle overtaking, lane changing, and relies on the well-known car-following mobility model.
Delivery ratio : the percentage of data messages generated that fully propagate the scenario considered until they are received by one of the fixed vehicle responsible to gather data messages. Delay : the total time taken for a data message generated to fully propagate the scenario considered until it is received by one of the vehicles responsible to gather data messages. This is particularly important for critical safety messages that must be disseminated as quickly as possible. We additionally compare the performance of each protocol with a theoretical optimum which serves as lower bound.
This value is simply calculated as the minimum number of hops that a message must travel times the transmission delay, given the transmission range employed.
- The Very Slow Time Machine!
- To Group Coupon Or Not: Small Business Guide to Groupon, Google Offers, LivingSocial and Others (To Groupon or not).
- Two energy and time-efficient data dissemination protocols for large-scale wireless sensor networks!
- Honor Among Thieves (Star Wars: Empire and Rebellion, Book 2).
- Human Dimensions of Global Environmental Change: Research Pathways for the Next Decade.
- Change They Cant Believe In: The Tea Party and Reactionary Politics in America.
We limit this estimation of the theoretical optimum to our highway scenario, since each message has a clear straight trajectory to travel, which leads to a predictable optimum end-to-end delay. The same does not occur for urban scenarios, due to its complexity in terms of multiple possible trajectories, mobility of vehicles, and radio obstacles.
Total number of transmissions : the total number of transmissions performed on average by an arbitrary vehicle. We consider only data messages in these results, thereby excluding transmissions of beacons. This value is normalized by the total number of vehicles in each scenario. When not properly chosen, the total number of directional sectors can negatively affect the performance of the AMD protocol.
As previously explained, AMD uses mapping information provided by a GPS navigation system to adaptively adjust the number of directional sectors according to the number of road directions and the presence of vehicles in the local region. In our simulations, each vehicle is pre-loaded with a simplified version of the scenario map. Such map contains the geographical positions corresponding to the center of each road intersection.
Since the scenarios considered contain either straight roads highway or follow a Manhattan grid shape urban scenarios , we define that the number of sectors can be either two or four. More specifically, the number of sectors is four whenever 1 the vehicle about to broadcast is within a radius of 15 m from the center point of the nearest intersection and 2 at least one neighboring vehicle has been previously detected via the reception of beacons in one of the orthogonal road directions relatively to the velocity vector of the sender.
Otherwise, two-directional sectors are employed. In the following, we analyze the effects of varying the number of directional sectors in both highway and urban scenarios when compared to the adaptive algorithm used by AMD. Figure 9 shows the results for varying the total number of sectors from 2 to 8. Each number is fixed during the whole simulation run regardless of the number of road directions in the map.
In Figure 9 a,b, we can observe that choosing a number higher than two for the highway scenario has a negative impact in the delivery ratio and delay. The same occurs for the urban scenario when fixing a number of sectors lower than four.
Both results are explained by the fact that choosing two sectors for highways and four or more for urban scenarios provides a better matching to the actual road mapping. On the one hand, an excessive number of sectors leads to too many vehicles being assigned to a different sector. Since the transmission of vehicles can only be suppressed by other vehicles in the same sector, this results in a high number of transmissions and possible collisions in the network Figure 9 c.
On the other hand, an excessive low number of sectors leads to an inefficient division of sectors, thereby causing higher delays and lower delivery ratio. Overall, using mapping information to adaptively choosing the number of directional sectors provides a performance near or equal the best result achieved when fixing the number of sectors beforehand for the whole simulation. In Figures 10 and 11 , we show the results for each protocol when varying the network density. Varying the network density evaluates the protocols in terms of scalability, which is crucial in vehicular networks due to its dynamic nature.
We additionally show the results for the suppression techniques used by each protocol separately in order to isolate the gains in performance when employing store-carry-forward mechanisms in very low densities. For lower densities, the delivery ratio is lower for all protocols because at the moment that a message is generated, there are cases when no vehicle is in neighborhood to received and disseminate the message to other vehicles in the road. The reason lies in the higher contention delay generated when more vehicles attempt to rebroadcast in a single time slot.
Both protocols achieve similar performance in terms of delivery ratio and end-to-end delay, as shown in Figure 11 a,b. This is explained by the fact that when protocols have to resort to using their store-carry-forward mechanisms, their performance in terms of delay and delivery ratio becomes dependent on the movement of vehicles, which is equal for both protocols.
This shows that AMD is able to quickly disseminate messages whenever there exist end-to-end connectivity to one of the fixed vehicles responsible for gathering data messages. We can observe that the suppression techniques alone present a lower delivery ratio when compared with their complete protocols. This behavior is particularly expected in urban scenarios where radio obstacles make disconnections predominant, thereby increasing the dependency on store-carry-forward strategies.
The reason lies in the ability of AMD to correctly select vehicles to perform the task of carrying and forwarding messages as well as in the ability of its suppression technique to separate vehicles in independent directional sectors, which allows vehicles to properly rebroadcast and suppress transmissions.
A scalable data dissemination protocol for both highway and urban vehicular environments
After this point, the network becomes mostly connected and fewer transmissions are needed due to the more frequent use of each suppression technique. In general, AMD scales more efficiently with increasing network densities when compared with protocols especially designed for either highway or urban scenarios. Compared to these solutions, AMD presents up to seven times lower number of transmissions in dense highway scenarios. In particular, SRD uses doubled number of time slots to distribute the number of time slots equally among the two road directions, as detailed in [ 5 ].
Figure 12 shows the results when varying the time slot parameter of each protocol for highway scenarios. With more time slots, a lower number of vehicles is assigned to a single time slot. Therefore, a lower level of rebroadcast redundancy is expected and messages can travel with less interference throughout the road length. The opposite effect occurs when the time slot density is increased in AMD. Similarly to what occurs when varying the network density, the end-to-end delay tends to increase when more vehicles attempt to transmit nearly simultaneously in a single time slot Figure 12 b.
Such an increase in the number of transmissions can be verified in Figure 12 c. With regard to our urban scenario Figure 13 , varying the time slot parameter for both AMD and UV-CAST shows to have little impact when considering their complete protocol with a store-carry-forward mechanism. Their performance is again dependent on the movement of vehicles, which is equal for both protocols. Differently from the results for highway scenarios, delay values are lower with higher t s d Figure 13 b , which is a result of the better matching of the number of simultaneous transmission allowed with the multiple road directions present in more complex urban scenarios.
Data Dissemination in Wireless Computing Environments | Kian-Lee Tan | Springer
Overall, all protocols perform best when fewer vehicles attempt to transmit nearly simultaneously. AMD, in particular, presents best performance in terms of delay when the number of simultaneous transmission allowed t s d equals the number of road directions, however, at the cost of a lower delivery ratio in urban scenarios. All protocols considered in this evaluation require that a certain overhead is added into beacons or data messages in order to guarantee their proper functioning. Such overhead is generally translated into a fixed number of bytes which correspond to extra fields appended to either beacon or data messages.
However, both AMD and UV-CAST resort to appending a message list with variable length to beacons in order to prevent that repeated messages are unnecessarily disseminated in the network. In particular, AMD also includes a small variable list in data messages to guarantee that the order of rebroadcast in the neighborhood is achieved.
Therefore, in this last section, we measure the message overhead required by these two protocols when increasing network densities are considered. Figure 14 shows the message overhead in number of bytes for both protocols in our urban scenario. Although setting an unbounded value for the number of entries k is obviously unadvisable, we additionally evaluate in this section the total overhead when the maximum list size possible is allowed for each network density.
As shown in the same figure, the maximum overhead reached for each density follows a similar pattern as the number of transmissions Figure 11 c. Overall, both AMD and UV-CAST protocols require additional message overhead of variable length to guarantee a proper functioning and to prevent unnecessary transmissions due to potential dissemination loops in the network. Especially for emergency applications, we expect that the message list size introduced in beacons be much lower than what has been considered here, since a single message might be repeated over time by the source vehicle, thereby reducing the number of entries of unique messages in the message list.
We have presented a data dissemination protocol that works seamlessly in both highway and urban scenarios: the A daptive M ulti-directional data D issemination AMD protocol. AMD combines a generalized time slot scheme based on directional sectors and a store-carry-forward algorithm to support multi-directional data dissemination.
Data dissemination in wireless computing environments
By means of simulation, we showed that AMD scales properly in various network densities in both highway and urban scenarios. We considered in our simulation scenarios realistic features such as a real map fragment of the Manhattan area in New York City with buildings serving as radio obstacles. In particular, AMD presented up to seven times lower number of transmissions in dense highway scenarios. In this work, we have considered an adaptive algorithm for defining the number of directional sectors for dissemination that is based on the road map and the presence of neighbors in each road direction.
However, in our simulations, the focus has been mainly on applying this method on typical straight highway or Manhattan grid scenarios urban. Therefore, one direction for future work is to consider more complex scenarios, e. In such scenarios, the angle allocated for each direction could be customized and, therefore, flexible to individual attributes of each road direction, for example, by adjusting the angle according to the road width.
In addition, we will aim to consider the support of infrastructure to further improve the end-to-end delay in sparse urban scenarios as well as additional mechanisms to limit the overhead inserted in beacons and data messages. IEEE Commun. Tutorials , 13 4 New York: ACM; Commun , 34 17 Williams B, Camp T: Comparison of broadcasting techniques for mobile ad hoc networks. Lausanne: ACM; Lim H, Kim C: Multicast tree construction and flooding in wireless ad hoc networks. Boston: ACM; Peng W, Lu X: On the reduction of broadcast redundancy in mobile ad hoc networks. Boston: IEEE; Peng W: Efficient broadcast in mobile ad hoc networks using connected dominating sets.
IEEE Trans. Vehicular Technol , 58 7 Panichpapiboon S, Pattara-atikom W: A review of information dissemination protocols for vehicular ad hoc networks. Tutorials , 14 3 Ad Hoc Netw , 1 4 Philadelphia: ACM; Transportation Syst , 12 3 Blum JJ, Eskandarian A: Avoiding timeslot boundary synchronization for multihop message broadcast in vehicular networks. VTC Spring Barcelona, 26—29 April Amsterdam: IEEE; Seoul: IEEE; Signal Process , Vahdat A, Becker D: Epidemic routing for partially connected ad hoc networks.
TON , Hong Kong: ACM; Barcelona: IEEE; Transportation Res. Part C: Emerg.
Technol , Morne: IEEE; Edited by: Smari WW. Nicosia; 14—16 April In IEEE Piscataway: IEEE; Tokyo: IEEE; Goldsmith A: Wireless Communications. Cambridge: Cambridge University Press; Bardonecchia: IEEE; In 6th Karlsruhe WSR. Karlsruhe; 03—04 March Busan; 25—29 October Download references.
Correspondence to Ramon S Schwartz. Reprints and Permissions. Search all SpringerOpen articles Search. Abstract Vehicular ad hoc networks VANETs enable the timely broadcast dissemination of event-driven messages to interested vehicles. Introduction Vehicular ad hoc networks VANETs are expected to serve as support to the development of a wide range of applications related to safety, transport efficiency, and even infotainment [ 1 ]. The key contributions of this work can be summarized as follows: A generalized time slot scheme based on directional sectors to support multi-directional data dissemination.
Related work Various solutions for VANETs have been proposed to cope with message dissemination under different traffic conditions. Figure 1. Full size image. Adaptive multi-directional data dissemination In this work, we address the limitations of current data dissemination approaches with the A daptive M ulti-directional data D issemination AMD protocol. To achieve this goal, we focus on the following aspects: Adaptive multi-directional dissemination : to achieve an efficient wide-spreading data dissemination, each data message is simultaneously disseminated to multiple directions that are adaptively adjusted according to the local map of the road provided, for example, by a GPS navigation system.
Concept definitions To better understand the protocol, we define the following concepts which are used throughout the remaining sections: Definition 1 Directional sector. Figure 2. Protocol concepts applied in an urban environment. Figure 3. Figure 4. Figure 5. Time slot scheme used by AMD. Figure 6. The complete AMD protocol diagram. Figure 7. Example of how directional sectors are defined. Performance evaluation The performance evaluation of AMD is carried out by means of simulations. We select three state-of-the-art protocols for comparison, namely: DV-CAST : it is a protocol designed to cope with both sparse and dense networks in highways [ 6 ].
Table 1 Simulation parameters Full size table. Energy-efficient clustering rumor routing protocol for wireless sensor networks. Ahvar, E. EQR: A new energy-aware query-based routing protocol for wireless sensor networks. WWIC Lecture Notes in Computer Science, Vol.
RER: A real time energy efficient routing protocol for query-based applications in wireless sensor networks. Telecommunication Systems , 61 1 , — Mann, C. A trajectory-based selective broadcast query protocol for large-scale, high-density wireless sensor networks. Telecommunication Systems , 35 , 67— ARR: Appointment-base rumor routing in wireless sensor networks. Surabaya, Indonesia. Rumor routing by appointment in center of gravity in wireless sensor networks.
Yu, C. A small-world routing protocol for wireless sensor networks. Kouassi, N. Performance study of an improved routing algorithm in wireless sensor networks. Procedia Computer Science , 19 , — Gu, H. Relative coordinate rumor routing in wireless sensor networks. Master tech dissertation, Tshwane University of Technology. Luo, H. TTDD: Two-tier data dissemination in large-scale wireless sensor networks. Wireless Networks , 11 , — Guerroumi, M.
Strengths and weaknesses of prominent data dissemination techniques in wireless sensor networks. Mobile sink and power management for efficient data dissemination in wireless sensor networks. Telecommunication Systems , 58 , Arya, R. WSN: Lifetime maximization of rumor routing protocol with optimization scheme and bandwidth evaluation. Khan, A. Wireless Networks. Saleh, A. A multi-aware query driven MAQD routing protocol for mobile wireless sensor networks based on neuro-fuzzy inference. Journal of Network and Computer Applications , 88 , 72— Mawloud, O.
Reliable and energy aware query-driven routing protocol for wireless sensor networks. Annals of Telecommunications , 71 1—2 , 73— Khelifi, M. Localization algorithms for wireless sensor networks: A review. International Journal of Sensor Networks , 19 2 , — Han, G. Localization algorithms of wireless sensor networks: A survey. Telecommunication Systems , 52 , Oliver, R.
Timeliness in wireless sensor networks: Common misconceptions. Brussels, Belgium. Bulusu, N. Self-configuring localization systems: Design and experimental evaluation. Li, X. Complexity of data collection, aggregation, and selection for wireless sensor networks. Fall, K. Network simulator NS-2 the NS manual. Ahmed, N. The holes problem in wireless sensor networks: A survey. Title Two energy and time-efficient data dissemination protocols for large-scale wireless sensor networks.
Publication date OriginalPaper Zone-based load balancing in two-tier heterogeneous cellular networks: a game theoretic approach.