{'fraction_non_alphanumeric': 0.030498849561854408, 'fraction_numerical': 0.008689479610319675, 'mean_word_length': 4.710791165781381, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed and Fair Beaconing Congestion Control Schemes for Vehicular Networks

Cooperative inter-vehicular applications rely on the exchange of broadcast single-hop status messages among vehicles, called beacons. The aggregated load on the wireless channel due to periodic beacons can prevent the transmission of other types of messages, what is called channel congestion due to beaconing activity. In this paper we approach the problem of controlling the beaconing rate on each vehicle by modeling it as a Network Utility Maximization (NUM) problem. This allows us to formally define the notion of fairness of a beaconing rate allocation in vehicular networks. The NUM model provides a rigorous framework to design a broad family of simple and decentralized algorithms, with proved convergence guarantees to a fair allocation solution. In this context, we propose the Fair Adaptive Beaconing Rate for Intervehicular Communications (FABRIC) algorithm, which uses a particular scaled gradient projection algorithm to solve the dual of the NUM problem. Simulation results validate our approach and show that, unlike recent proposals, FABRIC converges to fair rate allocations in multi-hop and dynamic scenarios.


I. INTRODUCTION
Inter-vehicle communications based on wireless technologies pave the way for innovative applications in traffic safety, driver-assistance, traffic control and other advanced services which will make up future Intelligent Transportation Systems (ITS) [1]. Communications for Vehicular Ad-Hoc Networks (VANET) have been developed and standardized in the last years. At the moment, a dedicated short range communication (DSRC) bandwidth has been allocated to vehicular communications at 5.9 GHz and both American and European standards [2] have adopted IEEE 802.11p [3] as physical and medium access control layers, based on carrier-sense multiple access with collision avoidance (CSMA/CA). These networks are characterized by a highly dynamic environment where shortlife connections between vehicles are expected as well as adverse propagation conditions leading to severe or moderate fading effects [4]. Cooperative inter-vehicular applications usually rely on the exchange of broadcast single-hop status messages among vehicles on a single control channel, which provide detailed information about vehicles position, speed, heading, acceleration, curvature and other data of interest [5]. These messages are called beacons and are transmitted periodically, at a fixed or variable beaconing rate. Beacons provide very rich information about the vehicular environment and so are relatively long messages, between 250 and 800 bytes, even more if securityrelated overhead is added [5]. In addition, vehicles exchange other messages on the control channel: service announcements and event-driven messages as a result of certain events. For instance, emergency messages are transmitted only when a dangerous situation is detected.
The aggregated load on the wireless channel due to periodic beacons can rise to a point where it can limit or prevent the transmission of other types of messages, what is called channel congestion due to beaconing activity. Control schemes are required to prevent this situation. The alternatives are: (1) decreasing the beaconing rate or (2) decreasing the number of vehicles in transmission range of each other or (3) a combination of both of them [6]. In this paper we focus on the control of the beaconing rate of each vehicle, whose requirements are discussed next. In addition to keep the channel load under a desired level, the practical implementation of the system impose two strong requirements on the control scheme: to be distributed and to grant beacon rates to each vehicle in a fair way. Being distributed means that vehicles should control their rate making use only of the signaling information exchanged with their neighbor vehicles and without relying on any centralized infrastructure. Besides, to reduce the signal overhead, the exchanged information should be kept to a minimum. Fairness must be guaranteed as a safety requirement since beacons are used to provide vehicles with an accurate estimate of the state of their neighbors. In general, the higher the beaconing rate, the higher the quality of the state information [6]. Consequently, the fairness goal implies that no vehicle should be allocated arbitrarily less resources than its neighbors, under the constraints imposed by the available capacity. Moreover, global fairness should be achieved, that is, not only among neighboring vehicles but among all vehicles contributing to congestion. Finally, the control scheme should also provide quick and effective adaptation to changes in the environment, such as the channel conditions and the number of vehicles in range. The limits on such capabilities are captured by the convergence properties of the algorithm in use.
Several beaconing rate control schemes have been proposed in the literature [7]- [10]. Although most of them are able to bring the channel load to the desired level, none of them is able to meet all the aforementioned requirements. In particular, most of them provide a very basic notion of fairness in how beaconing rates are allocated, without a formal definition and rigorous convergence support. Moreover, either global fairness is not achieved in multi-hop scenarios, where not all vehicles are in range of each other, or a remarkable overhead is introduced in order to meet only an approximate goal. As we shall show in the following sections, when faced with nontrivial (realistic) arrangements of vehicles, they converge to clearly unfair beaconing rate allocations.
On the other hand, distributed rate control has been extensively studied in other contexts. In particular, Network Utility Maximization (NUM) has received much attention in the field of congestion control in packet switched data networks since the seminal work of Kelly [11], and the connection found by Mo and Walrand [12] with fairness in bandwidth allocation. Surprisingly and in spite of the similarities, such an approach has not been adopted for congestion control in vehicular networks. Therefore, in this paper we describe a new approach to the problem of beaconing rate control in vehicular networks, modeling it as a NUM rate allocation problem, where each vehicle is associated a so-called utility function, such that the problem objective becomes the maximization of the sum of utilities of each vehicle. Applying the NUM theory allows us to design a broad family of decentralized and simple algorithms, with proved convergence guarantees to a fair allocation solution, supported by the rigorous developments of NUM theory. In addition, thanks to the work in [12], the notion of fairness of a beacon rate allocation in vehicular networks can be formally defined and generalized. The particular (concave) shape of the utility function of the vehicles is related to the different notions of fairness induced globally, the socalled (α, ω)-fairness allocations. As a result, different control schemes can be designed in order to enforce a particular type of fairness, such as proportional fairness (α = 1), or maxmin fairness (α → ∞). As we will show, NUM modeling allows us to design beaconing rate control algorithms with all the discussed requirements: they are distributed, they require the exchange of a small amount of signaling information and they achieve global fairness, in its different notions, with well-defined and guaranteed convergence properties. Then, we propose a particular algorithm to achieve proportional fairness and validate it with extensive simulations in static and dynamic scenarios. Its performance is evaluated and compared to an alternative state-of-the-art proposal.
In the remainder of this paper we first review related works in section II. In section III we provide a background on the classical NUM approach for rate allocation in packet switched networks and its connection with fairness. Afterwards, the beaconing congestion control problem for vehicular networks is formulated as a NUM rate allocation problem in section IV, where we also propose a particular algorithm . In section V, it is validated and compared with other proposals in static scenarios. In section VI we extend the comparison and evaluation in different dynamic scenarios. Finally, conclusions and future work are discussed in section VII.

II. RELATED WORK
In this section we put our work in context by describing the regulatory and technological environment and discussing previous beaconing rate control proposals. Transmissions are broadcast in nature and use a CSMA-based medium access control (MAC) with constant contention window and no acknowledgment or retransmission. ETSI standards define a 10 MHz control channel for vehicular communications at 5.9 GHz [2]. Periodic beaconing over one-hop broadcast communications supports cooperative inter-vehicular applications by disseminating status and environmental information to vehicles on the control channel [5].
The rate of beacons has an influence on the quality of service of the applications. Since safety-related applications usually need the maximum beaconing rate of 10 beacons/s [5], this is expected to be the default rate. However, in a medium or high-density traffic scenario, more than a hundred vehicles may be in range even for moderate transmission ranges, saturating the control channel. A framework for decentralized congestion control (DCC) in the control channel has been published by ETSI [13], which can accommodate a variety of controls such as transmit power, message rate or receiver sensitivity, though the currently suggested mechanisms are very basic, and extensions are being discussed. Transmit power control (TPC) has been investigated in recent proposals [6], [14], which show that TPC can be prone to instabilities, and its accuracy relies on the quality of the propagation model. Joint transmit power and rate control may be a necessary approach, especially to enforce particular application quality of service requirements, as in [6], [9], [10]. In this paper we do not consider it further and focus on control alternatives in which only the beaconing rate is adapted to traffic conditions. Even using exclusively rate control, enforcing weighted fairness may be used to provide vehicles with different beaconing rates according to their particular requirements.
Regarding pure beaconing rate control proposals, the most relevant works, [7], [8] propose rate control algorithms that comply with a global generic beaconing rate goal. The former, called LIMERIC, uses a linear control based on continuous feedback (beaconing rate in use) from the local neighbors, whereas the latter, called PULSAR, uses an additive increase multiplicative decrease (AIMD) iteration with binary feedback (congested or not) from one and two-hop neighbors. Both of them, however, show several limitations. Regarding fairness, LIMERIC claims targeting proportional fairness whereas PULSAR claims targeting max-min fairness allocations, but none of them define this formally. LIMERIC is shown to converge to a single fixed point, that is, a unique rate for every vehicle, which is below the optimal proportional fairness rate by design. In fact, there is a trade-off between the convergence speed and the distance to the optimal value. What is more problematic is the fact that the convergence is only guaranteed when all the vehicles are in range, which is clearly unrealistic. Indeed, as we shall show in the following sections, in multi-hop scenarios it converges to unfair configurations and below the optimum. Regarding PULSAR, it requires synchronized updates and piggybacking congestion information from vehicles at a two hops. A recent work [15] also shows that both LIMERIC and PULSAR actually may fall into unfair configurations. The authors propose as a solution heuristic techniques that ensure that two neighbor vehicles cannot diverge in their allocated rate. As we show later, it may actually prevent the algorithm to achieve an optimal fair allocation in some scenarios. In summary, these and other techniques proposed to date do not ensure correct convergence to a fair configuration and have no theoretical support for global convergence.

III. BACKGROUND
In this section we describe the key ideas on the NUM modeling for rate allocation in packet switched networks, that lay the foundations of our work in vehicular networks. For more detailed information we refer to [11], [12]. For a deeper background in convex optimization, problem decomposition and its applications to communication networks we refer to [17]- [19], and references therein.

A. The NUM problem for rate allocation in packet switched networks
Let G(N, E) be a packet switched network, being N the set of nodes and E the set of links. Let D be a set of traffic sources. For each traffic source d, we denote as p d the known set of links traversed by the traffic of the source, and r d the unknown bandwidth to be allocated to d. We denote as D(e) the subset of demands whose traffic traverses link e. The basic NUM modeling of the rate allocation problem is: The objective function (1a) maximizes the sum of the utility functions U d of each source. Constraints (1b) mean that the sum of the traffic traversing a link e, should not exceed link capacity u e . Finally, constraints (1c) prohibit assigning a negative amount of bandwidth to a source.
Functions U d for each demand d are strictly increasing and strictly concave twice-differentiable functions of the rate r d of that demand. Being U d an increasing function means that sources always perceive more bandwidth as more useful, and are always willing to transmit more traffic if allowed. Being concave means that a sort of diminishing returns effect occurs in rate allocation, i.e. increasing the bandwidth of a source from r to r + 1 means a higher increase in utility, than increasing a unit of bandwidth from r + 1 to r + 2. The objective function (1a) is strictly concave, and problem (1) is a convex program with a unique optimum solution.
Several problem decomposition strategies allow to find decentralized implementations of gradient-based algorithms with convergence guarantees to solve problem (1). Interested readers can find a surveyed view in [22] and references therein. In section IV, we will use as starting point of our proposal for vehicular networks the dual decomposition of problem (1), adapting the technique in [16].

B. Connection with fairness
As in every resource allocation problem, the optimum rate allocation in a network should balance two competing efforts: maximizing the total network throughput ( d r d ) but in a fair manner. In this context, fair means avoiding those allocations where some demands are granted a high amount of bandwidth while others suffer starvation.
Capturing the essence of what a fair resource allocation is not an easy task, and fairness has been defined in a number of different ways. One of the most common fairness notions is max-min fairness. A rate allocation r is said to be maxmin fair if the rate of any demand d 1 cannot be increased without decreasing the rate of some other demand d 2 which in r received less bandwidth (r d2 ≤ r d1 ). Kelly [11] proposed the concept of proportional fairness. A vector r * is proportionally fair if for any other feasible rate allocation r, the aggregate of the proportional change of r respect to r * is negative: That is, the percentages of increases/decreases respect to any other allocation should sum negative. In [12], Mo and Walrand extended the notion of proportional fairness. Let w = (w d , d ∈ D) be a vector of positive weight coefficients, α ≥ 0. A rate allocation r * is said to be (α, w)-proportionally fair if for any other feasible allocation r it holds that: The w d values can be used to give more importance to the rates allocated to some demands. If all demands are equal for the system (w d = 1, ∀d ∈ D), classical fairness notions are produced for some α values. In particular, 0-proportional fair solutions (α = 0) are those which maximize the throughput d r d . Actually, these solutions can be arbitrarily unfair, granting all the link bandwidth to some demands, and zero to others. If α = 1 we have the Kelly notion of proportional fairness. In addition, it can be shown that max-min fairness solutions are obtained when α → ∞ [12].
There is no consensus on which particular value of α is best suited for being "fair enough" in a resource allocation context. Actually, this decision is clearly application dependent. Lower values of α tend to produce solutions where the amount of traffic carried d r d is higher, but with larger differences between the rates allocated to different demands (more "unfair"). In its turn, higher α values reduce the difference between demands, commonly at the cost of a lower aggregated throughput.
The importance of the previous definition of fairness is that, if appropriate utility functions U d are used, the optimal solutions of NUM rate allocation problems are also (w, α)fair. This connection was shown in [12], for the basic NUM rate allocation problem (1). The following proposition extends the application of the result in [12] to a much more general class of problems.
Proposition 3.1: Let us define the generalized NUM problem for resource allocation, with decision variables (r, y). Vector r = {r d , d ∈ D} represent the rates (or in general resources) to assign to the demands, while y represent any arbitrary set of auxiliary variables. We define a generalized resource allocation problem as: where X is an arbitrary non-empty, closed, convex set. Let the utility functions in (3) be: Then, it holds that a resource allocation (r, y) is (α, w)proportionally fair if, and only if, it is the optimum solution of (3). Proof: The proof is based on a classical optimality condition in convex optimization [18,Prop.3.1] that states that given X a non-empty, closed and convex set, and F a convex function in X, a vector x * ∈ X is an optimal solution of the problem for every x ∈ X. Applying this property to problem (3) we have that a solution (r * , y * ) is optimal to the problem (3) if and only if it is (w, α)-fair according to (2).

IV. NUM MODELING OF THE BEACONING RATE CONTROL PROBLEM IN VEHICULAR NETWORKS
Let V be a set of vehicles in a vehicular network. Each vehicle v ∈ V transmits beacons at a rate r v beacons/sec, with a constant transmit power. Beacons are broadcast and are received by neighbor vehicles in reception range. Let n(v) denote the set of neighbor vehicles of v, which includes v. The total rate received by each vehicle is the sum of the rates of their neighbors and we are interested in limiting this amount to a maximum C, that is, a Maximum Beaconing Load (MBL), to avoid channel congestion.
The NUM version of the beaconing rate allocation problem is given by: The objective function (5a) is the sum of the utility U v (r v ) for each vehicle, which depends on the rate r v allocated to it. We assume vehicle utility functions as the ones in (4). Applying Prop. 3.1 to problem (5) we have that a rate allocation to the vehicles is α-fair if and only if, it is the optimum solution of (5). Constraints (5b) mean that the beaconing load at a given vehicle, which is the one generated by the neighboring vehicles plus its own load ( v∈n(v) r v ), must be below the MBL (C). Finally, constraints (5c) force the vehicle rates to be within a minimum (R min ) and maximum (R max ) value.

A. Dual decomposition
In order to find a decentralized algorithm solving (5) we use a dual decomposition of the problem. We first form the Lagrangian function L of (5) relaxing the constraints (5b): where π v ≥ 0 are the Lagrange multipliers (prices) associated with the relaxed constraints. Multiplier π v is usually interpreted as the price that vehicle v pays per traffic unit transmitted. Given a set of non-negative prices π v , the optimal rate allocation solving the relaxed problem max Rmin≤rv ≤Rmax L(r, π) is: We see that, to compute its rate, each vehicle v needs to know just its own utility function U v and the set of prices π v of its neighbor vehicles. Since the original problem is convex with linear constraints, it has the strong duality property [17] and the Karush-Kuhn-Tucker (KKT) conditions characterize its optimum solution. Then, it can be shown that there are a set of optimum link prices π * such that the associated rate according to (6) are the optimal solution of the original problem (5). The problem of finding such optimum prices is called the dual problem, which can be defined as: In our case, it can be shown that the objective function in (7), called the dual function, is strictly convex and differentiable, since the objective function in (5) is strictly concave. Thus, the dual problem (7) has a unique set of optimum prices π * v . In addition, given a set of prices π, the gradient of the dual function g evaluated at π is given by: The classical dual approach for solving the rate allocation problem consists of finding the dual optimal link prices π * using a gradient-based algorithm, as a mean to (in parallel) obtain the optimum rate allocation r * .
In Algorithm 1 we sketch this scheme for vehicular networks, applying a constant-step gradient method to the case of proportional fairness (α = 1, U (r v ) = log r v ), so eq. (6) becomes: Algorithm 1 ProportionalFairness -constant gradient step 1: At k = 0, set initial vehicle prices π 0 v and rates r 0 v 2: Then, at each time k: 3: Step 1. Each vehicle v receives the prices of neighbor vehicles π k v ′ , v ′ ∈ n(v). Then: Step 2. Each vehicle computes π k+1 v according to: Note that the implementation of this algorithm is decentralized. Each vehicle measures its own perceived congestion relative to the MBL when the gradient is computed at each step, and broadcast it to its neighbors. Then, each vehicle updates its rate using only the information from its neighboring vehicles. Note that contrary to other proposals arguments [7], [8], to achieve global fairness it is not necessary to explicitly disseminate information about two-hop congestion.
Convergence of Algorithm 1 can be guaranteed even for asynchronous operation of the vehicles, for a sufficiently small β, adapting the sufficient convergence conditions in [16] to our scenario. To see it, let us assign a virtual link l ∈ L to each vehicle, L = 1, . . . , V , with capacity C. Then consider that each virtual link l v is used by every vehicle which has vehicle v is in reception range with a rate r j , j ∈ n(v), plus is own rate r v . That is, we assume that each vehicle virtual link is used by its own rate plus the rates of all the neighbors in range. Now, problem (5) is equivalent to problem P in [16], where its convergence to the optimal allocation is proved. Let us notice that, unlike in [16], in the case of a vehicular network this solution can be implemented in practice with little effort, since the link processing is done by the vehicles themselves, that is, each vehicle acts as source and link. In fact, each vehicle measures its own perceived congestion relative to the MBL when the gradient is computed at each step, prior to the computation of the next price, and broadcast it to its neighbors.
Even though Algorithm 1 is a valid algorithm to solve problem (5), in the next section we present a variation of this proposal, where we introduce some modifications and discuss practical considerations. Finally, let us also note, that problem (5) and the above procedure can be adapted to achieve not only other kinds of fairness but also to incorporate heterogeneous utility functions and constraints for different vehicles. Further considerations on this are left as future work and we focus on only proportional fairness with homogeneous constrains in this paper.

B. Fair Adaptive Beaconing Rate for Intervehicular Communications (FABRIC)
In this section, we propose FABRIC (Fair Adaptive Beaconing Rate for Intervehicular Communications), a variation of Algorithm 1, where the prices of the links (Step 2) are updated in a different form: where sign(x) returns the sign (positive, negative or zero) of the argument. That is, in this case the vehicle price is increased by a constant β when the channel is congested and decreased by β otherwise, but never below zero. Even though it is not a gradient projection, this variation also converges to the optimal value. In fact, let us note that it can be equivalently considered a scaled gradient projection algorithm [18,Sec. 3

.3.3], where the price update is done by
, and the sequence of symmetric positive definite diagonal matrices M (k) is given by Therefore, the algorithm meets the conditions given in [21] for convergence for β small enough.
Let us now discuss implementation details. First, regarding overhead, the algorithm requires at least each vehicle v to store and send a non-negative real number, its price π v . The perceived congestion, that is, the difference between channel capacity and the fraction used can be obtained in several ways, either by monitoring the channel, that is, measuring the Channel Busy Time (CBT), or by counting the number of correctly received beacons. In both cases, the result is an estimate of the real channel occupation, since it depends on channel conditions and collisions. Another possibility is to let vehicles inform others of their current beaconing rate by piggybacking it in the beacon. This is the more reliable option with regard to the accuracy of the rate control results, since it informs about the actual congestion in absence of errors, such as fading or interference, Therefore, vehicles should broadcast at most their current beaconing rate plus the price, both piggybacked in a beacon, which adds little overhead to the current procedures, around 1% for 500-byte beacons. Second, we consider synchronous or asynchronous implementations. In the first case, all the vehicles update their rates at the same instant with the received prices. This is possible in practice for vehicles equipped with a GPS device. In that case, all the neighbor prices are available prior to the beaconing rate update. In the second case, each vehicle may update its rate at different instants. Thus, some vehicles may not have all the updated prices from their neighbors and oscillations may occur, which are called flapping. To avoid them, we propose to use an anti-flapping parameter, f , so that we consider that a gradient coordinate is 0 when its absolute value is below to a fraction f of the capacity. This way vehicles lock their prices when they are close to the MBL, and rate oscillations are prevented. In Section V we preliminary validate this procedure experimentally, but leave a more detailed study for a future work.

V. VALIDATION
In this section we test the validity of our algorithm and assumptions, in a static scenario where vehicles do not move which allows us an accurate control of the vehicles interactions. The results of FABRIC are compared with those of LIMERIC [7].
Simulations setup. We summarize first the simulation parameters that are common to the simulations studies in this and the following section. The simulations have been implemented with the OMNET++ framework and its inetmanet-2.0 extension [23], which implements the 802.11p standard. This library also implements a realistic propagation and interference model for computing the Signal to Interference-plus-Noise Ratio (SINR) and determining the packet reception probabilities, considering also capture effect.
In our tests, vehicles are located on a straight single lane road and their positions are either deterministic, that is equally spaced with distance d m or randomly positioned according to Beaconing rate (beacons/s) FABRIC N=100 sync f=0 FABRIC N=100 async f=0 FABRIC N=100 async f=0.022 FABRIC N=200 sync f=0 FABRIC N=200 async f=0 FABRIC N=200 async f=0.022 LIMERIC N=100 LIMERIC N=200 a Poisson distribution of average density ρ vehicles/m. Both free space and Nakagami-m propagation models have been used. In both cases, the path loss exponent has been set to 2 or 2.5 depending on the scenario. These are slightly lower values than those reported by [20], measured in suburban scenarios. Higher values result in shorter transmission range and so congestion is more unlikely and its effects milder. Thus, our values model a worst case scenario. Nakagami-m shape parameter has been set to m = 1, to model severe (Rayleigh) fading conditions. Values reported by [20] suggest even stronger fading. The MBL has been set to L M = 3.6 Mbps, which is 60% of the available data rate of 6 Mbps, and can be expressed as a maximum capacity of C = 781.25 beacons/s. Table I summarizes the rest of common parameters. All the simulations have been replicated 10 times with different seeds. The propagation model is a deterministic free space model, with path loss exponent of 2 and vehicles using 1000 mW of transmit power, which makes all of them to be in range of each other. The optimum value for the beaconing rate is r * = C/N , that is r * = 7.8125 and r * = 3.906 beacons/s respectively. In Fig. 1 we show the evolution of the beaconing rate with time, in algorithm steps. Vehicles update their beaconing rate every T s s. In the synchronous case all the vehicles perform their updates at the same time instant, whereas in the asynchronous one the instant is uniformly distributed along the period. As can be seen, FABRIC quickly converges to the optimum value without oscillations in the synchronous case, whereas in the asynchronous some oscillations can occur, that are corrected with the use of the anti-flapping technique described in the previous section. The amplitude of the oscillations decreases with the number of vehicles since the relative weight of the outdated prices is lower in the updates.
Regarding LIMERIC, Fig. 1 shows that, although it assigns the same fraction of the bandwidth to all vehicles, such fraction is 15% below and 7% below the optimal one respectively. It is noticeable that LIMERIC does not achieve the optimal value [7] even in an ideal scenario like this one. The reason is that the LIMERIC operation is controlled by two parameters α L and β L , such that by design the rate allocation uses a fraction of the available channel capacity equal to N βL αL+N βL . Better utilizations result when α L is small respect to β L N , but this also results in slow convergence times. The values used in this paper are the ones suggested by the authors in [7]. Scenario 2: Linear scenario with hidden nodes. In these tests, we evaluate two more demanding scenarios where not all vehicles have the same number of neighbors and hidden nodes are present. In the first one, vehicles are deterministically positioned along a 1500 m long line, equally separated d = 7 m. An ideal channel is considered. This scenario results in an optimal allocation with abrupt changes between the rate of neighbor vehicles at some points, that stress the ability of the algorithm to converge to a correct solution. In the second scenario vehicles are positioned along a 1500 m long line, with a Poisson distribution of average density ρ = 0.14 vehicles/m. The propagation models have been set to free space and Nakagami-m with path loss exponent equal to 2.5. In both cases, the transmit power has been set to 251 mW which results in a transmit range of 531.5 m for free space and (an average of) 471.5 m for Nakagami-m.
In Fig. 2 we plot the results for the beaconing rate selected versus the position on the road of the vehicles in the deterministic case. As a comparison, we plot the optimal allocation calculated by solving the NUM problem (5) with a numerical optimization solver, provided by JOM [24]. Results show that FABRIC, without channel access or propagation effects, and with a synchronous execution, converges to a solution very close to the optimal value. Note that an scenario like the one shown in this paper, in which the optimal allocation has abrupt differences between neighbor rates, is a counter-example to the proposal of [15], which suggests enforcing fairness by limiting the differences in the rate allocations of neighbor vehicles.
The solution in Fig. 2 has been achieved after 1000 steps of the algorithm. In practice, for randomly positioned scenarios and realistic propagation models, it is not necessary such a long convergence time to observe acceptable results. The results for the Poisson-like vehicle positioning, shown in Fig.  3, and results in the next section are an example of this. As Fig. 3 shows, with free space propagation, asynchronous FABRIC approximately tracks the optimal allocation after only 90 algorithm steps. With strong fading (Nakagami-m), the allocation is closer to the optimal one at the center where the congestion is also greater. At the center, the channel utilization constraint is tightly met: the CBT is around 15% below the MBL, which is consistent with a 12% of packets lost due to fading effects [14]. On the contrary, LIMERIC fails to provide a fair allocation of the beaconing rate in both cases. At the center of the road, approximately half of the vehicles are allocated a rate quite above the optimum, while others suffer starvation being assigned the minimum rate. Moreover, this starvation occurs even though the measured CBT (not shown), is below the MBL constraint.

VI. DYNAMIC SCENARIOS
In this section we investigate the FABRIC performance in dynamic configurations, where vehicles move. Our goal is to test the ability of FABRIC to perform smooth transitions from low to high congestion situations and whether it results in oscillating behavior.
Scenario 3: Single vehicle and traffic jam. The first scenario involves (i) a cluster of statically positioned vehicles along a 1500 m road segment, using the same random Poisson positioning of scenario 2 in Section V, and (ii) a single vehicle approaching the cluster, starting 1000 m away from the last cluster car, and moving at a constant speed of 32 m/s until it passes the cluster. This configuration can model different real scenarios such a highway with a traffic jam in one direction and a single vehicle moving in the opposite direction. The goal of this configuration is to show the dynamics of FABRIC in an extreme case where a vehicle switches from no or very few neighbors to a congested state, and back again. Let us note that, with the selected parameters shown in Table I, a channel can accommodate approximately 78 vehicles in range at the maximum rate. The case of a congested cluster approaching another one is considered in the next configuration.
Since the results for the 10 test replications (with different seed) are very similar, we plot the results of only one. In Fig. 4(a) we show the time evolution of the beaconing rate of the moving vehicle in the FABRIC and LIMERIC cases. Beaconing rates of the cluster vehicles are not shown since the effect of the single moving vehicle in their rate is small. FABRIC can keep the single vehicle at the maximum rate until the vehicle is in range of at least 78 neighbors, at t = 35 s. Afterwards it reduces its rate according to the state of the channel in exactly the same way as its neighbors (compare with Fig 3). This happens both in free-space and Nakagami-m configurations. In the latter, variations are even more smooth, showing that in the presence of a large number of neighbors (e.g. in congested areas), the effects of packet losses caused by a strong fading are compensated, and at the same time convergence is faster since the feedback is higher. In its turn,   the moving LIMERIC vehicle starts earlier than necessary to reduce its rate and recovers it later, even with free space propagation. In fact, it does not recover the maximum rate until it is completely out of range. Finally, Fig. 4(b) shows the channel utilization of all the vehicles in the FABRIC case. Interestingly, FABRIC quickly moves rates out of congestion. Moreover, results reinforce that it is not necessary to achieve the optimal allocation to meet the MBL constraint, showing that after only a few steps, 80% of the vehicles experience a load below the MBL. Scenario 4: Bridge over highway. Finally, we examine a extreme scenario, where a static cluster of approximately 200 vehicles is set along a 1500 m highway segment oriented in the y direction, and it is crossed at the middle position by another highway in the x direction. A bridge is situated at the cross, so that x direction highway passes over direction y highway. A moving cluster of 100 vehicles moves in the x direction at a constant speed of 32 m/s, starting 1500 m away from the bridge. The moving cluster approaches the static cluster, crosses the bridge, and moves away. For both clusters, the initial position and propagation configurations have been set as in the previous scenarios: Poisson and free space and Nakagamim and again the transmission range results in hidden nodes. Due to lack of space, only the Nakagami-m results are shown in this paper, yielding to the same conclusions as the ones for free-space.
In Fig. 5 we show the time evolution of the beaconing rates and CBT for all the vehicles in both clusters. In both cases, FABRIC reduces the rate of the vehicles in the highway to accommodate the passing vehicles, but never below 3 beacons/s in any cluster. Fig. 5(a) illustrate the evolution of the rate allocations in the moving cluster. With FABRIC, vehicles at the rear increase at the beginning their rates, as the front ones reduce theirs when they are entering the range of the highway vehicles, and conversely as they move away from the bridge. Again, higher variability occurs at the distant vehicles, since the feedback from their neighbors is weaker. The rate evolution of the static vehicles plotted in Fig. 5(c) shows an analogous evolution in FABRIC for them. As shown in Fig.  5(b) and Fig. 5(d), FABRIC succeeds in keeping the channel at a high utilization (approx. 50%, close to the 60% limit). On the other hand, LIMERIC reduces up to the minimum the beaconing rates of vehicles in both clusters unnecessarily, since there is margin in capacity, as can be seen in the CBT figures.

VII. CONCLUSIONS
In this paper we model for the first time, to the best of our knowledge, the problem of beaconing rate control in vehicular networks as a NUM rate allocation problem. This modeling opens the door to formally define and apply the fairness concept in beaconing rate allocation to vehicles. In addition, it provides a mathematical framework to develop decentralized and simple algorithms with proved convergence guarantees to a fair allocation solution. In this respect, we have presented a family of algorithms based on the gradient optimization of the dual of the rate allocation problem. Within this family, we have focused on proportional fairness and we have proposed the Fair Adaptive Beaconing Rate for Intervehicular Communications (FABRIC) algorithm. FABRIC, is   a decentralized rate allocation algorithm with theoretical and empirical convergence properties, which requires a reduced signaling overhead between vehicles.
We validate FABRIC by exhaustive simulations in both static and dynamic scenarios, for different position distributions and propagation models. Results show that FABRIC effectively generates fair beaconing rates allocations. Moreover, only in a few steps, the algorithm is able to move the rates out of the congestion state and close to the optimal allocation. Our results have been compared with LIMERIC, a state-ofthe-art rate allocation scheme in vehicular networks. We show that LIMERIC fails to achieve fairness in the general case, arbitrarily allocating high rates to some vehicles and low rates to others, even in situations in which idle capacity exists in the channel.
In addition to the practical utility of our proposal, in our opinion, one of the main contributions of this paper is the establishment of the NUM model as an effective and rich framework for developing beaconing rate control schemes in vehicular networks. In this sense, as a future work, we intend to further explore variations of the discussed problem in the context of vehicular networks. In particular, a comparative application and evaluation of alternative fairness notions, such as max-min, and the introduction of heterogeneous utility functions and constraints in the problem. The last possibility is related to the quality of service requirements of the applications, which might be very restrictive. In that case, joint rate and power control may be necessary, and we are working on a reformulation of the problem to include power control.