Method and system for controlling messages between communicating entities

Abstract

A method for controlling messages between communicating entities (CE) having computing devices, each CE sending messages to other neighboring CE with a entity-dependent message rate (CEMR), and with an entity-dependent transmission power, the messages being transmitted via one or more channels having a maximum channel capacity, and the CEMR defining a rate interval between a minimum and maximum rate, includes determining the CEMR within the rate interval by: (a) using a utility function for each CE; b) assigning an initial price for each CE; (c) adjusting the CEMR of each CE accounting for received prices of other CE; (d) computing a new price for each CE based on difference between initial price and available channel load for respective CEs; and (e) checking a termination condition for the difference and if unfulfilled, use the new price as initial price and repeat (c)-(e) until a termination condition is fulfilled.

Claims

1. A method for controlling messages between communicating entities (CE) including computing devices, the method being performed in a memory available to a computing device; each CE sending messages to other neighboring CE with a communicating entity-dependent message rate (CEMR), and with a communicating entity-dependent transmission power; the messages being transmitted via one or more channels having a maximum channel capacity; and the CEMR defining a rate interval between a minimum and maximum rate, the method comprising: determining the CEMR within the rate interval by employing a combination of three or more of the following, including at least steps c)-e): a) using a utility function for each CE being at least dependent on the CEMR and at least one parameter including a fairness parameter; b) assigning an initial price for each CE, wherein the price is calculated as a difference between the maximum channel capacity and the number of messages received per time unit; c) adjusting the CEMR of each CE taking into account received prices of the other CE, wherein each CE adjusts its own CEMR, such that the difference between the own utility function for the CEMR and the sum of received prices weighted with the own rate is maximized; d) computing a new price for each CE based on a difference between the initial price and an available channel load for the respective CE, wherein the available channel load is estimated or determined based on at least one of channel busy time, number of correctly received messages, and provided actual rates of CE by the CE, and is proportionally amended using a constant, the constant being multiplied with a sign of the available channel load of the respective CE; and e) checking a termination condition for the difference and, based on the termination condition being not fulfilled, using the new price as the initial price and performing steps c)-e) again until the termination condition is fulfilled.

2. The method of claim 1, wherein at least the channel busy time is used to estimate or determine the available channel load.

3. The method of claim 1, wherein each of steps a)-e) are performed.

4. The method of claim 1, wherein a price is broadcasted by including the price into a message.

5. The method of claim 1, wherein the initial price for each CE is based on an inverse of the maximum channel capacity.

6. The method of claim 1, wherein the termination condition is fulfilled when a difference between a prior and an actual CEMR is below a certain threshold.

7. The method of claim 1, wherein the termination condition is determined to be fulfilled based on an absolute value of the available channel load being smaller than a product of a flapping parameter and a maximum channel load, the flapping parameter being a function of a product of the maximum channel load and the constant.

8. The method of claim 1, wherein the new price is projected into a non-negative price.

9. The method of claim 1, wherein an adjusted CEMR is projected into the rate interval.

10. The method of claim 1, wherein the utility function uses different functions with an argument of the CEMR being dependent on a fairness parameter value.

11. The method of claim 1, wherein the messages are provided in form of status messages of cooperative inter-object applications like beacons which are transmitted periodically.

12. A communicating entity (CE), comprising: a sender for sending messages to other neighboring CE with a communicating entity-dependent message rate (CEMR), and with an communicating entity-dependent transmission power; the messages being transmitted via one or more channels having a maximum channel capacity; and the CEMR defining a rate interval between a minimum and maximum rate; a receiver for receiving messages; and a computing entity having a memory, wherein the following steps are performed by the computing entity using the memory of the communicating entity: a) using a utility function being at least dependent on the CEMR and at least one parameter including a fairness parameter; b) assigning an initial price, wherein the price is calculated as a difference between the maximum channel capacity and the number of messages received per time unit via the receiver; c) adjusting the CEMR of the CE taking into account received prices of the other CE, wherein the CE adjusts its own CEMR, such that the difference between the own utility function for the CEMR and the sum of received prices weighted with the own rate is maximized; d) computing a new price for the CE based on a difference between the initial price and an available channel load for the CE, wherein the available channel load is estimated or determined based on at least one of channel busy time, number of correctly received messages, and provided actual rates of CE by the CE, and is proportionally amended using a constant, the constant being multiplied with a sign of the available channel load of the respective CE; and e) checking a termination condition for the difference and, based on the termination condition being not fulfilled, using the new price as the initial price for the CE and performing steps c)-e) again until the termination condition is fulfilled.

13. A system for controlling messages between communicating entities, performing cooperative inter-entity applications, the system comprising: more than one communicating entity (CE); wherein each CE is adapted to send messages to, and to receive messages from other neighboring communicating entities with an entity-dependent message rate (CEMR), and with an entity-dependent transmission power; and the messages being transmitted by the CE via one or more channels having a maximum channel capacity; and the CEMR defining a rate interval between a minimum and maximum rate and being determined within the rate interval, and wherein each CE is configured to: a) use a utility function being at least dependent on the CEMR and at least one parameter including a fairness parameter; b) use an initial price, wherein the price is calculated as a difference between the maximum channel capacity and the number of messages received per time unit; c) adjust its own CEMR taking into account received prices of the CE, such that the difference between the own utility function for the CEMR and the sum of received prices weighted with the own rate is maximized; d) compute a new price based on a difference between the initial price and an available channel load seen by itself, wherein the available channel load is estimated or determined based on at least one of channel busy time, number of correctly received messages, and provided actual rates of CE by the CE, and is proportionally amended using a constant, the constant being multiplied with a sign of the available channel load of the respective CE; and e) check a termination condition for the difference and, based on the termination condition being not fulfilled, using the new price as the initial price and performing steps c)-e) again until the termination condition is fulfilled.

14. The CE of claim 12, in the form of a vehicle.

15. The CE of claim 12, in the form of a car, bus, truck, train, or aircraft.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The present invention will be described in even greater detail below based on the exemplary figures. The invention is not limited to the exemplary embodiments. All features described and/or illustrated herein can be used alone or combined in different combinations in embodiments of the invention. The features and advantages of various embodiments of the present invention will become apparent by reading the following detailed description with reference to the attached drawings which illustrate the following:

(2) FIG. 1 shows steps of a method according to an embodiment of the present invention,

(3) FIG. 2 shows steps of a method according to a further embodiment of the present invention, and

(4) FIG. 3 shows a system according to a further embodiment of the present invention.

DETAILED DESCRIPTION

(5) Although applicable to any kind of communicating entity the present invention will be described with regard to vehicles as communicating entities. Although applicable to messages in general the present invention will be described with regard to messages of cooperative inter-vehicular applications

(6) Embodiments of the invention therefore address the above-mentioned problems of providing a realistic controlling of messages avoiding channel congestion while being easy to implement, which require less environmental information than conventional methods and provide fairness in beacon rate allocation throughout the communicating entities.

(7) In an embodiment the present invention provides a method for controlling messages between communicating entities, ‘CE’, said CE comprising computing devices, wherein said method is performed in a memory available to a computing device, and wherein each CE sends messages to other neighboring CE with an entity-dependent message rate, ‘CEMR’, and with an entity-dependent transmission power, and wherein said messages are transmitted via one or more channels having a maximum channel capacity, and wherein the CEMR are between a minimum and maximum rate defining a rate interval and being determined within said rate interval by a) Using a utility function for each CE being at least dependent on the CEMR and at least one parameter including a fairness parameter, b) Assigning an initial price for each CE, wherein said price is calculated as a difference between said maximum channel capacity and the number of messages received per time unit, c) Adjusting the CEMR of each CE taking into account received prices of said other CE, wherein each CE adjusts its own CEMR, such that the difference between the own utility function for the CEMR and the sum of received prices weighted with the own rate is maximized, d) Computing a new price for each CE based on difference between the initial price and available channel load for the respective CE, e) Check a termination condition for said difference and if not fulfilled, use said new price as initial price and perform steps c)-e) again until a termination condition is fulfilled.

(8) In a further embodiment the present invention provides a communicating entity, ‘CE’, comprising a sender for sending messages to other neighboring CE with a communicating entity-dependent message rate, ‘CEMR’, and with an entity-dependent transmission power, and wherein said messages are transmitted via one or more channels having a maximum channel capacity, and wherein the CEMR are between a minimum and maximum rate defining a rate interval, a receiver for receiving messages, and a computing entity having a memory, wherein the following steps are performed in said memory of said CE a) Using a utility function being at least dependent on the CEMR and at least one parameter including a fairness parameter, b) Assigning an initial price, wherein said price is calculated as a difference between said maximum channel capacity and the number of messages received per time unit via said receiver, c) Adjusting the CEMR of said CE taking into account received prices of said other CE, wherein said CE adjusts its own CEMR, such that the difference between the own utility function for the CEMR and the sum of received prices weighted with the own rate is maximized, d) Computing a new price for the CE based on difference between the initial price and available channel load for the CE, e) Check a termination condition for said difference and if not fulfilled, use said new price as initial price for the CE and perform steps c)-e) again until a termination condition is fulfilled.

(9) In a further embodiment the present invention provides a system for controlling messages between communicating entities, ‘CE’, performing cooperative inter-entity applications wherein each CE is adapted to send messages to and to receive messages from other neighboring CE with an communicating entity-dependent message rate, ‘CEMR’, and with an communicating entity-dependent transmission power, and wherein said messages are transmitted by the CE via one or more channels having a maximum channel capacity, and wherein the CEMR are between a minimum and maximum rate defining a rate interval and being determined within said rate interval and wherein each CE is adapted to a) Use a utility function being at least dependent on the CEMR and at least one parameter including a fairness parameter, b) Use an initial price, wherein said price is calculated as a difference between said maximum channel capacity and the number of messages received per time unit, c) Adjust its own CEMR taking into account received prices of said CE, such that the difference between the own utility function for the CEMR and the sum of received prices weighted with the own rate is maximized, d) Computing a new price based on difference between the initial price and available channel load seen by itself and to e) Check a termination condition for said difference and if not fulfilled, use said new price as initial price and perform steps c)-e) again until a termination condition is fulfilled.

(10) Embodiments of the invention may have the following advantage: A realistic controlling of messages between communicating entities significantly outperforming conventional rate control and message control methods and systems.

(11) Embodiments of the invention have further the advantage that convergence is arbitrarily quickly and requires less environmental information than conventional methods and systems. For example embodiments do not require two-hop information.

(12) Embodiments of the invention have the advantage that a network utility maximization NUM can be used by formulating the control of the rate of messages as a NUM rate allocation problem enabled by the convexity and the possibility to use a projected subgradient procedure to its dual problem enabling a distributed implementation while being globally fair. The shape of the utility function maximized by the communicating entities, e.g. vehicles may be dependent on the fairness to be implemented, e.g. proportional fairness, weighted fairness and/or max-min-fairness which was disclosed.

(13) The term “utility function” is to be understood as representation of a usage of at least part of a transmission channel capacity by a communicating entity.

(14) The term “communicating entity” is to be understood in its broadest sense: For example a communicating entity may be any type of static or movable machine or device, wherein a movable machine or device can be manually or automatically moved, for example by an engine, wheels, etc. A communicating entity may be sensor device like a camera, etc., roadside equipment, etc. or in form of a moving object like a car, a bicycle, a bus, a truck, a flying object like an airplane, helicopter, drone, etc. as well as a ship, a boat, a train or the like.

(15) The term “computing device” is to be understood in its broadest sense and may be any kind of device which can be used or is adapted to compute or perform methods, algorithms, programs like applications or the like and may comprise one or more processors having one or more cores and memory for storing.

(16) The “message rate” is defined as the number of messages per time unit.

(17) The term “transmission power” is to be understood as a power with which via a cable-based or via wireless channel a signal in which messages are encoded is transmitted.

(18) The term “price” is to be understood in its broadest sense and means or refers to any kind of value, set of values or sum of values used for indication of congestion seen by a communicating entity.

(19) Further features, advantages and further embodiments are described or may become apparent in the following:

(20) Said available channel load may be estimated or may be determined based on at least one of: a channel business time, a number of correctly received messages, provided actual rates of CE by the CE. This enables a precise estimation of the real channel occupation since it depends on channel conditions and the respective collisions.

(21) Said available channel load may be proportionally amended using a constant. If a constant is used, each price can be determined independently from others by observing the available bandwidth: The link or channel capacity minus the volume of traversing traffic. Therefore signaling is only needed just to inform the demands of all the prices of its traversed links, for example by using a real non-negative number per communicating entity.

(22) Said constant may be multiplied with a sign of the available channel load. This enables the following: The sign function returns the sign either positive or negative of its argument, i.e. the available channel load. Then the price is increased in constant amount of said constant when the channel is congested and decreased in constant units, i.e. in units of said constant otherwise but never falling below zero.

(23) A price may be broadcasted by including said price into a message. This enables in an efficient way to broadcast the prices of the different communicating entities. For example the price may be piggybacked in a beacon to inform the other vehicles about the actual CEMR.

(24) The initial price for each CE may be based on the inverse of the maximum channel capacity. This enables an efficient, i.e. optimal choice for the initial price resulting in a minimum number of steps until the termination condition is fulfilled. Thus, efficiency is significantly enhanced.

(25) Said termination condition may be fulfilled when a difference between a prior and an actual CEMR is below a certain threshold. This enables in an easy way to implement a termination condition.

(26) Said termination condition may be fulfilled when the absolute value of said free available channel load is smaller than a product of a flapping parameter and a maximum channel load, wherein said flapping parameter is a function of a product of the maximum channel load and said constant. This enables an efficient convergence and convergence time of all steps a)-e) by minimizing the oscillations of flapping when computing the new prices.

(27) Said new price may be projected into a non-negative price. This avoids non-valid prices during computing of a new price. Thus, efficiency and precision is enhanced.

(28) Said adjusted CEMR is projected into said rate interval. By projecting an adjusted CEMR into the rate interval non-valid rates are avoided. Thus, efficiency is enhanced.

(29) The utility function may use different functions with the argument of said CEMR being dependent on the value of said fairness parameter. This enhances the flexibility since different functions can be used as utility functions: For instance as utility function a linear function in the CEMR can be used if the fairness parameter is equal to zero, a constant multiplied with a logarithm of rate can be used if the fairness parameter is equal to one and further it may be proportional to the rate to the power of one minus the fairness parameter if the fairness parameter a is greater than zero. Thus, flexibility in terms of fairness is enhanced. Further an adaptation for realistic scenarios is enhanced.

(30) Said messages may be provided in form of status messages of cooperative inter-object applications like beacons which are transmitted periodically. This enables an easy implementation in cooperative inter-object applications like vehicular networks or the like.

(31) Said CE may be a vehicle like a car, bus, truck, train, aircraft of the like. This allows a flexible implementation in a variety of different communicating entities.

(32) FIG. 1 shows steps of a method according to an embodiment of the present invention.

(33) In FIG. 1 six steps of a method for controlling messages between communicating entities, ‘CE’, is shown, said communicating entities comprising computing devices, wherein said method is performed in a memory available to a computing device, and wherein each communicating entity sends messages to other neighboring communicating entities with a entity-dependent message rate, ‘CEMR’, and with an entity-dependent transmission power, and wherein said messages are transmitted via one or more channels having a maximum channel capacity, and wherein the CEMR are between a minimum and maximum rate defining a rate interval and being determined within said rate interval.

(34) The first step a) is performed by using a utility function for each CE being at least dependent on the CEMR and at least one parameter including a fairness parameter.

(35) The second step b) is performed by assigning an initial price for each CE, wherein said price is calculated as a difference between said maximum channel capacity and the number of messages received per time unit.

(36) The third step b′) is optional and is performed by broadcasting the initial price of each CE to the other CE.

(37) The fourth step c) is performed by adjusting the CEMR of each CE taking into account received prices of said other CE, wherein each CE adjusts its own CEMR, such that the difference between the own utility function for the CEMR and the sum of received prices weighted with the own rate is maximized.

(38) The fifth step d) is performed by computing a new price for each CE based on difference between the initial price and available channel load for the respective CE.

(39) The sixth step e) is performed by checking a termination condition for said difference and if not fulfilled, using said new price as initial price and perform steps c)-e) again until a termination condition is fulfilled.

(40) In more detail the basis for NUM modeling for rate allocation in packet switched networks is described in the following, e.g. shown in the non patent literature of Kelly, Frank, “Charging and rate control for elastic traffic.” European transactions on Telecommunications 8.1 (1997): 33-37, and J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556-567, 2000 and in more detail in the non-patent literature of S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, Cambridge, UK, 2004, D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Inc., Upper Saddle River, N J, 1989 and M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle, “Layering as optimization decomposition: A mathematical theory of network architectures,” Proceedings of the IEEE, vol 95, no 1, pp. 255-312.

(41) In the following a general description is provided.

(42) 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, p.sub.d denotes the known set of links traversed by the traffic of the source, and r.sub.d the unknown bandwidth to be allocated to d. D(e) is denoted as the subset of demands whose traffic traverses link e. Then the basic NUM modeling of the rate allocation problem is:

(43) $\begin{array}{cc}\underset{r_d}{\max }\underset{d}{.Math.}{U}_d\left(r_d\right)\mathrm{subject}\mathrm{to}\text{:}& \left(1a\right)\\ \underset{d\in D\left(x\right)}{.Math.}{r}_d\le u_x{\forall }_{\in }\in E& \left(1b\right)\\ r_d\ge 0\forall d\in D& \left(1c\right)\end{array}$

(44) The objective function (1a) maximizes the sum of the utility functions U.sub.d of each source. Constraints (1b) mean that the sum of the traffic traversing a link e, should not exceed link capacity u.sub.e. Finally, constraints (1c) prohibit assigning a negative amount of bandwidth to a source. Functions U.sub.d for each demand d are strictly increasing and strictly concave twice-differentiable functions of the rate r.sub.d of that demand. Being U.sub.d an increasing function means that sources always perceive more bandwidth as more useful, and are always willing to transmit more traffic if allowed.

(45) 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.

(46) Several problem decomposition strategies may be applied and permit finding decentralized implementations of gradient-based algorithms with convergence guarantees to solve problem (1). In the following an approach based on a dual decomposition of the problem is described. First the Lagrangian function L of (1) relaxing the constraints (1b) is formed.

(47) $\begin{array}{c}L\left(r,\pi \right)=\underset{d}{-.Math.}{U}_d\left(r_d\right)+\underset{e}{.Math.}{\pi }_e\left(u_e-r_d\right)=\\ =\underset{d}{.Math.}\left(U_d\left(r_d\right)-r_d\underset{e}{\overset{}{.Math.}}{\pi }_e\right)-\underset{e}{\overset{}{.Math.}}{\pi }_e{u}_e\end{array}$
where π.sub.e≧0 are the Lagrange multipliers (link prices) associated with the relaxed constraints. The dual function g(π) associated to this relaxation, is defined as:

(48) $\begin{array}{cc}g\left(\pi \right)=\left\{L\left(r,\pi \right)\right\}& \left(2\right)\end{array}$

(49) That is, given a vector of link prices π, the dual function returns the optimal utility of a problem where link constraints are relaxed, and for each link e, a price π.sub.e per bandwidth unit is applied resulting in a virtual cost of using the links. Given a set of prices π, r*(π) is denoted to the maximizer of (2):

(50) $\begin{array}{cc}\left(\pi \right)=\arg \underset{r_d\ge 0}{\max }\left\{L\left(r,\pi \right)\right\}=\underset{r_d\ge 0}{\max }\left\{U_d\left(r_d\right)-r_d\underset{e\in p_d}{\overset{}{.Math.}}{\pi }_e\right\}& \left(3\right)\end{array}$

(51) To compute the rate r*.sub.d(π), each demand d needs to know just its own utility function U.sub.d and the set of prices π.sub.e for the traversed links. Since functions U.sub.d are strictly concave r*.sub.d(π), rates are unique for each π. The dual problem of (1) consists of fπ), r the set of prices π≧0 which minimizes g(π):

(52) $\begin{array}{cc}\underset{\pi \ge 0}{\min }\left\{g\left(\pi \right)\right\}& \left(4\right)\end{array}$

(53) Since the original problem is convex with linear constraints, it has the strong duality property as disclosed in the non-patent literature of S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, Cambridge, UK, 2004, and the Karush-Kuhn-Tucker (KKT) conditions characterize its optimum solution. Then, it can be shown that if Tr* are the link prices that solve the dual problem, then the rates r* (π*) are the optimal solution of the original problem (1).

(54) The conventional dual approach for solving the rate allocation problem consists of finding the dual optimal link prices π*, as a mean to (in parallel) obtain the optimum rate allocation r*. This is enabled by the following well-known property: The dual function g is a convex function of the prices π. A subgradient of g in π is given by

(55) $=\left(u_e-\underset{d\in D\left(e\right)}{.Math.}{r}_d,\in E\right)$
wherein a subgradient is a generalization of the concept of gradient for non-differentiable convex functions. A subgradient s of a convex function f(x): S R in point x.sub.0εS is a vectors for which:
f(x)≧f(x.sub.0)+s(x−x.sub.0)∀xεS

(56) Since the objective function is strictly concave, g is differentiable, and the subgradient computed above is actually a gradient. A standard projected gradient algorithm variant to iteratively first the optimal link prices may be applied, and indirectly the optimal rates. The following procedure III. 1 sketches this:

(57) TABLE-US-00001 Procedure III.1: DECENTRALIZED( ) main Step 0. k = 0. Set feasible initial link prices π.sub.e ≧ 0 e.g. π.sup.0.sub.e = 1 ∀e ε E. Step 1. Each demand d is signaled the prices of traversed links π.sup.k.sub.e e ε p.sub.d. Step 2. Each link computes π.sup.k+1.sub.e according to: ${\pi }_e^{k+1}={\left[{\pi }_e^k-{\beta }_e^k\left(u_e-\underset{d\in D\left(e\right)}{.Math.}{r}_d\right)\right]}_0$ Go to step 1.

(58) In step 1 of the procedure, each demand allocates the rate that solves the dual function g(π), with the only knowledge of the prices of the traversed links. For instance, if U.sub.d(r.sub.d)=log r.sub.d then:

(59) $r_d^k\left({\pi }^k\right)=\arg \underset{r_d\ge 0}{\max }\left\{\log r_d-\underset{}{\overset{}{.Math.}}\right\}=\frac{1}{\underset{e\in p_d}{\overset{}{.Math.}}{\pi }_e^k}$

(60) In step 2 the prices are updated moving in the direction of the negative gradient of the dual function, since minimum has to be found. The obtained solution is projected into the set of valid prices π≧0. This projection is conducted by operator [x].sub.0 which resets with 0 the negative values, and leaves positive values unchanged.

(61) ${\left[x\right]}_0=\{\begin{array}{cc}x& \mathrm{if}x\ge 0\\ 0& \mathrm{if}x<0\end{array}$

(62) Several values can be chosen for the β.sup.k.sub.e coefficients that e.g. guarantee convergence to the optimum allocation. For instance, convergence is guaranteed for decreasing β.sup.k(β.sup.k.sub.e=β.sup.k, ∀e) such that β.sup.k.fwdarw.0 and Σ.sub.k=∞ i.e. β.sup.k=1/k. Also, constant values β.sup.k=β may guarantee convergence to the optimum for β sufficiently small. Different conventional gradient algorithms appearing in the literature could be used, inheriting their convergence guarantees as disclosed in the non patent literature of S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, Cambridge, UK, 2004 and D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Inc., Upper Saddle River, N J, 1989. In the rate allocation problem context, in gradient procedure variants for which the procedure III.1 can be solved in a decentralized form may be used: For instance, if a constant β coefficient is used, each link can compute its gradient coordinate independently from others, by observing the available bandwidth: the link capacity minus the volume of traversing traffic. Therefore signaling is needed just to inform the demands about the prices of its traversed links: one real non-negative number per link.

(63) As in every resource allocation problem, the optimum rate allocation in a network should balance two competing efforts: maximizing the total network throughput (Σ.sub.dr.sub.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.

(64) Said 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 max-min fair if the rate of any demand d.sub.1 cannot be increased without decreasing the rate of some other demand d.sub.2 which in r received less bandwidth (r.sub.d2≧r.sub.d1). 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:

(65) 0$\underset{d}{.Math.}\frac{r_d-}{}\le 0,\forall r\mathrm{feasible}$

(66) That is, the percentages of increases/decreases respect to any other allocation should sum negative. In the non-patent literature of J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556-567, 2000 the notion of proportional fairness has been extended. Let w=(w.sub.d, wε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:

(67) $\underset{d}{.Math.}{w}_d\frac{r_d-r_d^{*}}{r_d^{*\alpha }}\le 0,\forall r\mathrm{feasible}$

(68) The w.sub.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.sub.d=1,∀dεD), conventional fairness notions are produced for some a values. In particular, 0-proportional fair solutions (α=0) are those which maximize the throughput Σ.sub.d r.sub.d. Actually, these solutions can be arbitrarily unfair, granting all the link bandwidth to some demands, and zero to others. If α=1 proportional fairness is achieved. In addition, it can be shown that max-min fairness solutions are obtained when α.fwdarw.00 e.g. disclosed in the non-patent literature of J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556-567, 2000.

(69) There is no consensus on which particular value of a is best suited for being “fair enough” in the rate allocation context. Actually, this decision is clearly application dependent. Lower values of α tend to produce solutions where the amount of traffic carried Σ.sub.d r.sub.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 a cost of a lower aggregated throughput.

(70) The importance of the previous definition of fairness, is that if appropriate utility functions U.sub.d are used, the optimum solutions of NUM rate allocation problems, are also (w, α)-fair as presented in the non-patent literature of J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556-567, 2000, for the basic NUM rate allocation problem (1).

(71) This concept is now extended, i.e. is applied to a much wider set of problems. When the generalized NUM problem for resource allocation, with decision variables (r, y). Vector r={r.sub.d,dεD} represent the rates (or in general resources) to assign to the demands, while y represent any arbitrary set of auxiliary variables, the resource allocation problem may be defined as:

(72) $\begin{array}{cc}\max \underset{d}{.Math.}U\left(r_d\right)\mathrm{subject}\mathrm{to}\left(r,y\right)\in X& \left(5\right)\end{array}$
here X is an arbitrary non-empty, closed, convex set. Let the utility functions in (5) be:

(73) $\begin{array}{cc}{U}_d\left(r_d\right)=\{\begin{array}{cc}{w}_d{r}_d& \mathrm{if}\alpha =0\\ w_d\log r_d& \mathrm{if}\alpha =1\\ w_d\frac{1-\alpha }{}& \mathrm{if}\alpha >0,\alpha \ne 1\end{array}& \left(6\right)\end{array}$

(74) Then, it holds that a resource allocation (r, y) is (α,w)-proportionally fair if, and only if, it is the optimum solution of (5).

(75) The proof is based on a conventional optimality condition in convex optimization 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 min.sub.xεX F(x) if and only if, (x−x*)′∀F(x*)≧0 for every xεX. Applying this property to problem (5) a solution (r*, y*) optimal to the problem (5) is obtained if and only if:

(76) $\begin{array}{cc}\underset{d}{.Math.}{w}_d\frac{r_d-r_d^{*}}{}\ge 0,\forall \left(r,y\right)\in X& \end{array}$
which coincides with the definition of a solution (r*,y*) being (w, α)-fair. I

(77) In the following the above mentioned principles are now applied in vehicular networks according to an embodiment of the invention: Let V be a set of vehicles in a vehicular network. Each vehicle vεV sends beacons at a rate r.sub.v, beacons/sec, with a fixed transmission power. Beacons propagate and are received by other vehicles, which we call neighbor vehicles. Let n(v) denote the neighbor vehicles of v, which includes v. The total rate received by each vehicle is the sum of the rates of their neighbors and this amount should be limited to a maximum C, that is, a Maximum Beaconing Load (MBL), to avoid channel congestion.

(78) The NUM version of the beaconing rate allocation problem is given by:

(79) $\begin{array}{cc}\underset{v}{.Math.}{U}_v\left(r_v\right)\mathrm{subject}\mathrm{to}\text{:}& \left(7a\right)\\ \underset{}{\overset{}{}}{r}_v\le C\forall v\in V& \left(7b\right)\\ R_{\min }\le r_v\le R_{\max }\forall v\in V& \left(7c\right)\end{array}$

(80) The objective function (7a) is the sum of the utility U.sub.v,(r.sub.v) for each vehicle, which depends on the rate r.sub.v, allocated to it. Vehicle utility functions are chosen to be the ones in (6), so that the fairness in the rate allocation to the vehicles is governed by the α factor selected. Constraints (7b) means that any vehicle has to find the channel busy a give fraction (MBL) of the total time. Since the channel is sensed as busy when it is occupied by the traffic sent by the neighboring vehicles and its own traffic, the sum Σ.sub.vεn(v) r.sub.v must be below the MBL (C). Finally, constraints (7c) force the vehicle rates to be within a minimum (R.sub.min) and maximum (R.sub.max) value.

(81) Taking into account the above comments a rate allocation to the vehicles is α-fair if and only if, it is the optimum solution of (7). Applying the procedure III.I to the beaconing rate problem, a decentralized control with guaranteed properties of convergence to the optimal α-fair solution is achieved. In the procedure IV.I this procedure is sketched for the case of proportional fairness (U(r.sub.v)=log r.sub.v), and constant β value.

(82) TABLE-US-00002 Procedere IV.1: PROPORTIONAL( ) main  Step 0. K = 0, initial vehicle prices π.sub.v = 1  Step 1. Each vehicle v receive the prices of   neighbor vehicles π.sub.v′.sup.k, v′ ∈ n(v).   $\mathrm{Then}\text{:}{r}_v^k={\left[\frac{1}{\underset{{}_{v^{\prime }\in n\left(v\right)}}{.Math.}{\pi }_{v^{\prime }}}\right]}_{R_{\min }}^{R_{\max }}$  Step 2. Each vehicle computes π.sub.v.sup.k+1 according to:   ${\pi }_v^{k+1}={\left[{\pi }_v^k-\beta \left(C-\underset{v^{\prime }\in n\left(v\right)}{.Math.}{r}_{v^{\prime }}\right)\right]}_0$   Go to step 1.

(83) The procedure IV.1 requires each vehicle v to store a non-negative real number, its

(84) $\frac{1}{\underset{v^{\prime }\in n\left(v\right)}{.Math.}{\pi }_{v^{\prime }}}$
price π.sub.v, calculated as the difference between channel capacity C, and the number of beacons received. The difference between channel capacity and the real 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 actual rate by piggybacking it in the beacon, which is used in the following: Periodically, each vehicle broadcasts its price π.sub.v, i.e., piggybacked in a beacon. In parallel, each vehicle v receives and stores the prices π.sub.v, from their neighboring vehicles n(v): the set of vehicles from which it receives beacons. Finally, it periodically updates its beaconing rate r.sub.v according to the rule (3). Note that in this update, the value projected into the R.sub.min, R.sub.max interval.

(85) Another embodiment is described in the following.

(86) The procedure IV.1 described previously is an example of decentralized scheme for producing α-fair allocations in vehicle networks. A variation of this scheme is described, where the weights of the links (Step 2) are updated in a different form:

(87) TABLE-US-00003 Procedure IV.2: FABRIC ( ) main  Step 0. K = 0, initial vehicle prices π.sub.v = 1  Step 1. Each vehicle v receive the prices of   neighbor vehicles $r_v^k={\left[\frac{1}{\underset{{}_{v^{\prime }\in n\left(v\right)}}{.Math.}{\pi }_{v^{\prime }}}\right]}_{R_{\min }}^{R_{\max }}$  Step 2. Each vehicle computes π.sub.v.sup.k+1 according to:   0${\pi }_v^{k+1}={\left[{\pi }_v^k-\mathrm{\beta sign}\left(C-\underset{v^{\prime }\in n\left(v\right)}{.Math.}{r}_{v^{\prime }}\right)\right]}_0$   Go to step 1.
where sign(x) returns the sign (positive or negative) of the argument. That is, in this case the vehicle price is increased in a constants amount β of units when the channel is congested and decreased in β units otherwise, but never falling below zero.

(88) FIG. 2 shows steps of a method according to a further embodiment of the present invention.

(89) In FIG. 2 a method for controlling the rate of beacon messages in a vehicular network is shown comprising the following steps: 1) setting initial link prices; 2) exchanging information about the prices of neighboring vehicles; 3) setting ego vehicle's rate for the next step by using an NUM method to cast a beaconing rate allocation problem and by taking into account information about the prices of neighboring vehicles; and 4) repeating in parallel on all vehicles.

(90) FIG. 3 shows a system according to a further embodiment of the present invention.

(91) In FIG. 3, three communicating entities CE1, CE2 and CE3 are shown. Each CE1, CE2 and CE3 is equipped with a wireless transponder WT for sending and receiving prices, in detail for sending its own price π.sub.v.sup.k and receiving prices of other vehicles π.sub.v′.sup.k.

(92) The communicating entities CE1, CE2 and CE3 perform for example network utility maximization by performing procedure IV.1 or performing procedure IV.2 as shown above.

(93) FIG. 4 shows a diagram showing beacon rates over time obtained according to a further embodiment of the present mentioned and compared with a conventional method.

(94) In FIG. 4 a selected beaconing rate in a one-hop scenario for FABRIC and LIMERIC with 100 and 200 vehicles and different price steps β and flapping parameters is shown. The LIMERIC parameters have been set to ∝.sub.L=0.01 and

(95) $\beta =\frac{1}{}.$
Optimal values are shown with a straight line.

(96) In the following the validity of an embodiment and assumptions are shown. For the validation a scenario is simulated, where vehicles do not move and so the vehicle density and position can be controlled accurately.

(97) In at least one embodiment the present invention provides a control scheme aimed at solving a general congestion problem by beaconing rate adjustment and modeling it as a network utility maximization rate allocation problem. The beaconing rate allocation problem is modeled as network utility maximization NUM enabling to design a broad family of decentralized and efficient methods with proved convergence guaranteeing a fair location solution wherein the convergence is enabled by the convexity of the network utility maximization problem and a possibility to solve it by applying a projected subgradient procedure to its dual problem, which permits a distributed implementation.

(98) In at least one embodiment the present invention takes into account the unique characteristics of vehicular embodiment which is decentralized, lossy and rapidly changing within the information locally available in said vehicular networks, for example information from direct neighbors about channel load to set up a network utility maximization optimization problem and near-optionally assign appropriate beaconing rates for each vehicle in a distributed manor.

(99) At least one embodiment of the present invention provides a method for rate control and/or a location e.g. in vehicular network environment that a) uses information about the price (congestion level) from neighboring vehicles or in general communicating entities to form a Network Utility Maximization optimization problem; b) employs a projected subgradient algorithm to arrive at a fair and bandwidth efficient rate allocation in a distributed way; c) introduces the concept of utility function of each vehicle, and relates the particular shape of the utility function of the vehicles with the type of fairness induced globally; d) employs the flapping parameter to minimize the oscillation of the rate; and e) generalizes and formally defines the notion of fairness of a beacon rate allocation in vehicular networks.

(100) At least one embodiment of the present invention enables a realistic simulation, which performs better than existing conventional algorithms, procedures, methods and systems specifically, it significantly outperformed a rate control algorithm that is proposed to be used by both ETSI and C2C-CC requiring less environmental information than conventional algorithms, procedures, methods and systems specifically, it was shown to perform as well or better than methods requiring two-hop information by using one-hop information only convergence arbitrarily quickly, depending on the granularity of the used time step.

(101) Many modifications and other embodiments of the invention set forth herein will come to mind to the one skilled in the art to which the invention pertains having the benefit of the teachings presented in the foregoing description and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.

(102) While the invention has been illustrated and described in detail in the drawings and foregoing description, such illustration and description are to be considered illustrative or exemplary and not restrictive. It will be understood that changes and modifications may be made by those of ordinary skill within the scope of the following claims. In particular, the present invention covers further embodiments with any combination of features from different embodiments described above and below. Additionally, statements made herein characterizing the invention refer to an embodiment of the invention and not necessarily all embodiments.

(103) The terms used in the claims should be construed to have the broadest reasonable interpretation consistent with the foregoing description. For example, the use of the article “a” or “the” in introducing an element should not be interpreted as being exclusive of a plurality of elements. Likewise, the recitation of “or” should be interpreted as being inclusive, such that the recitation of “A or B” is not exclusive of “A and B,” unless it is clear from the context or the foregoing description that only one of A and B is intended. Further, the recitation of “at least one of A, B, and C” should be interpreted as one or more of a group of elements consisting of A, B, and C, and should not be interpreted as requiring at least one of each of the listed elements A, B, and C, regardless of whether A, B, and C are related as categories or otherwise. Moreover, the recitation of “A, B, and/or C” or “at least one of A, B, or C” should be interpreted as including any singular entity from the listed elements, e.g., A, any subset from the listed elements, e.g., A and B, or the entire list of elements A, B, and C.