随着汽车工业技术、传感器技术、无线通信技术等现代科学技术的快速发展,智能交通系统(Intelligent Transport System, ITS)的概念应运而生,已成为目前世界上交通运输科学领域的研究前沿。车载自组织网络(Vehicular Ad-hoc NETwork, VANET)作为ITS的重要组成部分,旨在加强车辆间联系,增强道路交通安全性,已经引起工业界、学术界和政府机构的广泛关注,正在从概念走向现实。
车辆间通信通过广播信标消息来实现信息交互和对周围环境的感知,这是VANET和安全应用实现的基础条件。车辆间通信的消息类型主要分为两类:一类是周期性广播的信标消息,主要包含车辆的位置、速度、朝向等核心状态信息;另一类是事件驱动型的安全消息,如因为车祸等紧急事件触发的告警消息。欧洲电信标准化协会分别定义这两种消息为协同感知消息(Cooperative Awareness Message, CAM)和分散环境通知消息(Decentralized Environmental Notification Messages, DENM)。而美国采用的车载环境无线接入(Wireless Access in Vehicular Environment, WAVE)标准,定义前者为基础安全消息(Basic Safety Message, BSM),对后者没有特定的命名。
文献[1]中实验结果表明,当车流密度增大到一定程度时,仅仅是周期性广播的信标消息就会使车联网(Internet of Vehicles, IoV)的无线信道产生拥塞,从而带来时延增大、丢包率上升等问题,影响通信质量。信道拥塞会限制甚至阻碍安全消息的传输,从而会对公共交通安全造成极大的隐患。文献[2]指出,车辆间通信的拥塞控制技术是车联网中的未解决问题和研究挑战,车辆间通信通过发送周期性广播的信标消息和事件驱动的告警消息实现,对于两种消息的拥塞控制能保证安全信息传输的可靠性和可扩展性。
车联网中的拥塞控制一般从三个方面进行动态调控:信标发射速率、发射功率和竞争窗口的大小。本文关注信标消息广播的发射功率,已有学者在这方面开展了研究。Torrent-Moreno等[3]提出了车辆环境分布式公平功率调整(Distributed Fair Power Adjustment for Vehicular environments, D-FPAV)算法来实现拥塞控制、公平性和优先级分配。该算法使每辆车周期性采集周围车辆的状态信息,然后通过本地计算将信标消息发送所需要的最小传输功率最大化,使得本地信道负载低于预先设定的信标负载阈值。这是目前最经典和最被广泛接受的功率控制算法。Mittag等[4]提出分布式车辆密度估计(Distributed Vehicle Density Estimation, DVDE)策略来估计其周围两个感知距离内的车辆密度,并以固定大小的密度直方图进行互相交换,最后以基于分割的功率调整(Segment-based Power Adjustment for Vehicular environments, SPAV)算法来求得需要设置的功率。Egea-Lopez等[5]将每辆车的信标发射功率控制问题建模为网络效用最大化问题,提出公平分布式发射功率拥塞控制(Fair distributed Congestion Control with transmit Power, FCCP)算法,每辆车根据接收到的信息与自身信息计算出最优发射功率,从而能够分布式地动态地调整信标发射功率。Fallah等[6]提出一种基于状态利用的功率调整(Stateful Utilization-based PoweR Adaptation, SUPRA)算法,每辆车根据上一时刻测得的信道忙占比来计算当前时刻的理想功率,然后将其与上一时刻功率的差值乘以系数得到变化量,进而得到当前时刻的理想功率,同时证明了该算法的稳定性和公平性。此外,Egea-Lopez等[7]基于网络效用最大化(Network Utility Maximization, NUM)模型,实现对车联网信标发送速率的自适应控制;刘明剑等[8]基于NUM模型和信道拥塞代价计算,实现车联网自适应消息发送速率控制。
虽然上述功率控制算法的研究能实时调整发射功率,进行拥塞控制,但均未考虑车联网中节点的移动性,不同车辆的速度、车辆间相对距离都是动态变化的,车联网具有快速变化的动态拓扑结构。本文在文献[5]研究的基础上,以网络效用最大化模型为基础,考虑车联网中节点的移动性,设计合适的权重和效用函数,采用Nakagami-m衰落信道模型,结合公平性对车联网中的拥塞控制问题建模,提出分布式加权公平功率控制(Distributed-Weighted Fair Power Control, D-WFPC)算法,使车辆的本地信道负载在设定阈值之下,避免信道拥塞,从而保证消息低时延、高可靠地传输。
1 功率控制优化问题建立 1.1 系统假设考虑车联网本身特性以及未来的发展情况,系统模型如图 1所示,对于系统模型作出以下假设:
1) 所有车辆的功能相同,配备全球定位系统(Global Positioning System, GPS)和必要传感器,不考虑分簇的情况。
2) 道路旁侧部署基站(evolved Node B, eNodeB),通信范围覆盖该路段。
3) 车辆同时配备IEEE 802.11p通信接口和长期演进(Long Term Evolution, LTE)通信接口,车辆之间通过IEEE 802.11p接口进行通信,车辆与基站之间通过LTE接口进行通信。
4) 正常情况下,车辆会周期性广播信标消息来实现车辆间直接通信,信标消息包含车辆自身的位置、速度、朝向等信息,以及根据需要添加的额外信息;紧急情况下,会出现告警信息的传输。
1.2 随机信道模型车联网信道模型的建立使用文献[9]中建议的方法:首先使用简单路径损耗模型求得平均功率,作为Nakagami-m分布的平均功率,然后设定Nakagami-m分布的形状因子,即可得到同时考虑路径损耗和衰落的信道模型。文献[10]表明,Nakagami-m衰落模型更符合车联网环境,并且随机信道比确定信道更接近现实信道。
首先不考虑衰落,只考虑路径损耗。一辆车的发射功率是p,则与其距离为d的车辆处的信号接收功率为pr,采用简单路径损耗模型,则pr的表达式为:
$ {p_r} = p{K_{\rm{0}}}{\left( {\frac{{{d_0}}}{d}} \right)^\beta } = p{\left( {\frac{\xi }{{4{\rm{ \mathit{ π} }}d_0}}} \right)^2}{\left( {\frac{{{d_0}}}{d}} \right)^\beta } $ | (1) |
式中:d0是参考距离; ξ是载波波长,β是路径损耗系数。取d0=1 m,ξ用光速c和载波频率f表示,则可以得到:
$ {p_r} = p{\left( {\frac{{\rm{c}}}{{4{\rm{ \mathit{ π} }}f}}} \right)^2}{\left( {\frac{1}{d}} \right)^\beta } $ | (2) |
再考虑衰落模型,本文采用Nakagami-m衰落模型,即接收信号的包络服从Nakagami-m分布,其概率密度函数为:
$ f\left( {r;m, \mathit{\Omega} } \right) = \frac{{2{m^m}{r^{2m - 1}}}}{{{\mathit{\Omega} ^m}\Gamma \left( m \right)}}{{\rm{e}}^{ - \frac{m}{\mathit{\Omega} }{r^2}}};\;\; m \ge \frac{1}{2}, r \ge 0 $ | (3) |
式中:Ω是平均功率,本文中为pr;m是Nakagami-m分布的形状因子,它描述由于多径效应引起的衰落程度;Γ(m)为Gamma函数。需要指出的是,此时的接收功率不再是无衰落时的定值。
因为接收信号包络服从Nakagami-m分布,则其接收功率pr服从Gamma分布,pr的概率密度函数为:
$ f\left( {x;m, \frac{m}{{{p_r}}}} \right) = {\left( {\frac{m}{{{p_r}}}} \right)^m}\frac{{{x^{m - 1}}}}{{\Gamma \left( m \right)}}{{\rm{e}}^{ - \frac{m}{{{p_r}}}x}} $ | (4) |
pr的累积分布函数为:
$\begin{array}{c} F\left( {x;m, \frac{m}{{{p_r}}}} \right) ={\Upsilon \left( {m, \frac{m}{{{p_r}}}x} \right)}/{{\Gamma \left( m \right)}} =\\ 1 - {\Gamma \left( {m, \frac{m}{{{p_r}}}x} \right)}/{{\Gamma \left( m \right)}}\end{array} $ | (5) |
式中:
综上所述,考虑路径损耗和Nakagami-m衰落信道模型,如果车辆j的发射功率为pj,车辆j与车辆i的相对距离为dji(dji=dij),则车辆i接收到车辆j发出的信标的接收功率为Pr,其大于能正确解析的信号强度S的概率为:
$ P({P_r} > S) = {\Gamma \left( {m, \frac{m}{{{p_j}}}{{\left( {\frac{{4\pi f}}{c}} \right)}^2}d_{ji}^\beta S} \right)}/{{\Gamma \left( m \right)}} $ | (6) |
为方便表示与计算,将式(6)进行如下变换:
$ f\left( {m, \frac{{{G_{ij}}}}{{{p_j}}}} \right) = P\left( {{P_r} > S} \right) ={\Gamma \left( {m, \frac{{{G_{ij}}}}{{{p_j}}}} \right)}/{{\Gamma \left( m \right)}} $ | (7) |
$ {G_{ij}} = {G_{ji}} = m{\left( {{4\pi f}/{c}} \right)^2}d_{ij}^\beta S $ | (8) |
Kelly等[11]和Low等[12]提出NUM模型及其应用,该模型在有线网络中公平有效地分配传输速率,进行拥塞控制。经过多年的发展,NUM模型或者效用的理念已经被广泛应用于有线网络和无线网络的资源分配问题。
经典NUM模型:考虑K(N, E)是一个有线网络,N是节点的集合,E是链接的集合,Z是流量源的集合;对于每个流量源z∈Z,uz是分配给z的传输速率,mz和Mz分别是可分配的最小传输速率和最大传输速率,Uz(uz)是给z分配uz的传输速率得到的效用;对于每个链接e∈E,Z(e)是流量穿过链接e的流量源的集合,Re是链接e的最大容量。
$ {\rm{max}}\sum\limits_{z \in Z} {{U_z}} \left( {{u_z}} \right) $ | (9) |
$ {\rm{s}}{\rm{.t}}{\rm{. }}\sum\limits_{z \in Z\left( e \right)} {{u_z} \le {R_e}}, \forall e \in E $ | (10) |
$ {\rm{ }}{m_z} \le {u_z} \le {M_z}, \forall z \in Z $ | (11) |
最优化问题式(9)为最大化每个流量源z取决于传输速率uz的效用的总和;约束式(10)表示穿过任意链接e的流量总和应该不大于e的最大容量;约束式(11)保证所有分配的传输速率在一定范围之内。
1.4 基于NUM模型的功率控制问题建立虽然NUM模型的提出是为了解决有线网络中的传输速率分配问题,但随着时间的推移,其在无线网络的资源分配问题中也得到应用,其中也包括车联网。如果将车联网中的车辆i同时看作:1)有线网络中的流量源,即车辆i作为网络中的流量源,以每秒ri个的速率发射信标;2)有线网络中的链接,即车辆i作为网络中的链接,其周围邻居车辆和自身发出的信标消息都会经过车辆i自身,该链接的容量即为车辆i的本地信道负载。在此基础上,可以利用NUM模型[7]对车联网中的功率控制问题进行建模,如图 2所示。
假设车联网中所有车辆的集合为V,其车辆数量为I,i∈V代表车联网中的车辆i;Vi代表车辆i能正确接收并解析的信标消息来自的车辆加上车辆i自身的集合,称为邻居车辆集合,其车辆数量为J,j∈Vi代表车辆i的邻居车辆集合中的车辆j;pi代表车辆i的信标发射功率,pimin和pimax分别代表pi的最小值和最大值,Uij(pi)代表车辆i基于发射功率pi的效用;ri代表车辆i的信标发射速率;f(m, Gij/pj),其表达式为式(7),代表采用形状因子为m的Nakagami-m衰落信道,车辆j的信标发射功率为pj,在与其距离为dij处的车辆i的接收功率大于能正确解析的信号强度S的概率;车辆i处的本地负载是其自身的信标发射速率加上总体的信标接收速率,C是最大信标负载。
本文建立的车联网功率分配效用最大化问题可表述为:
$ {\rm{max}}\sum\limits_{i \in V} {\sum\limits_{j \in {V_i}} {{U_{ij}}\left( {{p_i}} \right)} } $ | (12) |
$ {\rm{s}}{\rm{.t}}{\rm{. }}\sum\limits_{j \in {V_i}} {{r_j}f\left( {m, {G_{ij}}/{p_j}} \right)} \le C, \forall i \in V $ | (13) |
$ {\rm{ }}p_i^{{\rm{min}}} \le {p_i} \le p_i^{{\rm{max}}}, \forall i \in V $ | (14) |
最优化目标式(12)是最大化每个车辆i取决于发射功率pi的效用的总和;约束条件式(13)保证任意车辆的本地负载在最大信标负载之下,从而预留一部分带宽给其他消息的传输,预防信道拥塞的产生,实现拥塞控制的目的;约束条件式(14)保证所有发射功率在一定范围之内。
效用函数需要满足严格增、严格凹、二阶连续可微的条件,采用文献[13]中的效用函数:
$ {U_{ij}}\left( {{p_i}} \right) = \left\{ \begin{array}{*{20}{l}} {\omega _{ij}}{p_i}{\rm{ }} ,&\alpha = 0\\ {\omega _{ij}}{\rm{ln}}{p_i}{\rm{ }} ,&\alpha = 1\\ {\omega _{ij}}{p_i}^{1 - \alpha }{\left( {1 - \alpha } \right)^{ - 1}} ,&\alpha > 0且\alpha \ne 1 \end{array} \right. $ | (15) |
式中的α为非负数。当权重ωij都设为1时,α取不同值时可以实现不同的公平性:当α=0时,可以达到最大化网络吞吐量;当α=1时,可以达到比例公平性;当α=2时,可以达到调和平均数公平性;当α→∞时,可以达到最大最小公平性。
2 D-WFPC算法设计 2.1 效用函数权重设计考虑到车联网中节点移动的特性,效用函数需要考虑移动性,即同一车辆与不同车辆之间不同的移动性会产生不同的效用。D-WFPC算法在移动性方面主要考虑相对距离和相对速度,权重ωij的表达式中包含相对距离和相对速度,采用文献[14]中的权重表达式:
$ {\omega _{ij}} = {{\rm{max}}\left\{ {{v_{ij}}, {\rm{Const}}} \right\}}/{{{d_{ij}}}} $ | (16) |
其中:ωij代表车辆i和车辆j之间的权重,ωij=ωji;dij代表车辆i和车辆j之间的相对距离;vij代表车辆i和车辆j之间的相对速度;Const是一个正常数,代表相对速度的最小正值。当相对距离固定时,相对速度越大,权重越大;当相对速度固定时,相对距离越小,权重越大。这是从避免碰撞,提高行车安全性的角度来设计的效用函数权重,并且该设计可以实现加权公平性。
2.2 功率控制优化问题凸优化对于优化问题式(12),首先考察其凹凸性,由1.4节可知效用函数是凹函数;约束条件式(14)是线性的;对于约束条件式(13)中的函数f(m, Gij/pj),其二阶偏导为:
$ \begin{array}{l} \frac{{{\partial ^2}f\left( {m, {G_{ij}}/{p_j}} \right)}}{{\partial {p_j}^2}} = \left( {{G_{ij}} - \left( {m + 1} \right){p_j}} \right) \times {\rm{ }}\frac{{{G_{ij}}^m}}{{\Gamma \left( m \right)}}p_j^{ - m - 2}{{\rm{e}}^{ - \frac{{{G_{ij}}}}{{{p_j}}}}} \end{array} $ | (17) |
由式(17)可以发现,函数f(m, Gij/pj)的二阶偏导的取值与其参数m、Gij和pi之间的关系有关,并不恒大于0,因此不具有严格凸性。
虽然函数f(m, Gij/pj)不具有严格凸性,但如果引入新的变量x,采用变换p=x-1/m[5],则原函数变为:
$ f\left( {m, {G_{ij}}/{p_j}} \right) = f\left( {m, {G_{ij}}{x_j}^{1/m}} \right) ={\Gamma \left( {m, {G_{ij}}{x_j}^{1/m}} \right)}/{{\Gamma \left( m \right)}} $ | (18) |
$ \frac{{{\partial ^2}f\left( {m, {G_{ij}}{x_j}^{1/m}} \right)}}{{\partial {x_j}^2}} = \frac{{{G_{ij}}^{m + 1}}}{{{m^2}\Gamma \left( m \right)}}{x_j}^{1/m - 1}{{\rm{e}}^{ - {G_{ij}}{x_j}^{1/m}}} $ | (19) |
由式(19)可以发现,经过p→x的变换后得到的函数的二阶偏导式(19)恒大于0,因此其具有严格凸性。
采用变换p=x-1/m之后,效用函数的表达式变为:
$ U\left( p \right) = U\left( {{x^{ - 1/m}}} \right) = \omega {{x^{ -\left( {1 - \alpha } \right)/m}}}/(1 - \alpha ) $ | (20) |
其二阶偏导为:
$ \frac{{{\partial ^2}U\left( {{x^{ - 1/m}}} \right)}}{{\partial {x^2}}} = \left( {m + 1 - \alpha } \right)\frac{\omega }{{{m^2}}}{x^{ - (1 - \alpha )/m - 2}} $ | (21) |
因为效用函数需要具有严格凹性,即二阶偏导小于等于0恒成立,可知,当α≥m+1时能保证效用函数具有严格凹性。
经过变量转换和条件限定,本文建立的车联网功率控制优化问题可转变为凸优化问题式(22)。
$ {\rm{max}}\sum\limits_{i \in V} {\sum\limits_{j \in {V_i}} {{U_{ij}}\left( {x_i^{ - 1/m}} \right)} } $ | (22) |
$ {\rm{s}}{\rm{.t}}{\rm{. }}\sum\limits_{j \in {V_i}} {{r_j}f\left( {m, {G_{ij}}{x_j}^{1/m}} \right)} \le C, \forall i \in V $ | (23) |
$ {\rm{ }}{\left( {p_i^{{\rm{max}}}} \right)^{ - m}} \le {x_i} \le {\left( {p_i^{{\rm{min}}}} \right)^{ - m}}, \forall i \in V $ | (24) |
考虑使用文献[15-16]中Lagrange对偶分解的方法来求解凸优化问题式(22),引入对偶变量或称Lagrange乘子向量λ来构造Lagrange函数:
$ \begin{array}{l} L\left( {\boldsymbol{x}, \boldsymbol{\lambda} } \right) =& \sum\limits_{i \in V} {\sum\limits_{j \in {V_i}} {{U_{ij}}\left( {{x_i}^{ - 1/m}} \right)} } - \\ & \sum\limits_{i \in V} {{\lambda _i}\left( {\sum\limits_{j \in {V_i}} {{r_j}f\left( {m, {G_{ij}}{x_j}^{1/m}} \right)} - C} \right)} \end{array} $ | (25) |
$ \begin{array}{l} L\left( {\boldsymbol{x}, \boldsymbol{\lambda} } \right) = &\sum\limits_{i \in V} {\left( {\sum\limits_{j \in {V_i}} {{U_{ij}}\left( {{x_i}^{ - 1/m}} \right) - {\lambda _i}\sum\limits_{j \in {V_i}} {{r_j}f\left( {m, {G_{ij}}{x_j}^{1/m}} \right)} } } \right)} +\\ & C\sum\limits_{i \in V} {{\lambda _i}} \end{array} $ | (26) |
$ \begin{array}{l} L\left( {\boldsymbol{x}, \boldsymbol{\lambda} } \right) = &\sum\limits_{i \in V} {\left( {\sum\limits_{j \in {V_i}} {{U_{ij}}\left( {{x_i}^{ - 1/m}} \right) - {r_i}\sum\limits_{j \in {V_i}} {{\lambda _j}f\left( {m, {G_{ji}}{x_i}^{1/m}} \right)} } } \right)}+ \\ & C\sum\limits_{i \in V} {{\lambda _i}} \end{array} $ | (27) |
其中:λi称为第i个不等式约束的Lagrange乘子,Lagrange乘子向量λ=[λ1, λ2, …, λJ]。
再定义Lagrange对偶函数q(λ)为Lagrange函数关于x取得的最小值,其表达式为:
$ q\left( \boldsymbol{\lambda} \right) = \left\{ \begin{array}{*{20}{l}} \mathop {{\rm{sup}}}\limits_{x \in {\pmb{X}}} L\left( {\boldsymbol{x}, \boldsymbol{\lambda} } \right),& \boldsymbol{\lambda} \ge 0\\ - \infty, &{其他} \end{array} \right. $ | (28) |
因此原优化问题式(22)的对偶问题表述为:
$ \begin{array}{l} &\min q\left( \boldsymbol{\lambda} \right)\\ {\rm{s}}{\rm{.t}}{\rm{. }}&\forall \boldsymbol{\lambda} \in {{\bf{R}}^J} \end{array} $ | (29) |
式中R为有理数集。
原优化问题式(22)是凸优化问题,且其满足Slater条件[16],即存在一组在定义域内的值x,使得约束条件式(23)中的小于等于可以取到小于,即:
$ {\rm{ }}\sum\limits_{j \in {V_i}} {{r_j}f\left( {m, {G_{ij}}{x_j}^{1/m}} \right)} < C; \;\; \forall i \in V $ | (30) |
由文献[16]可知,如果凸优化问题满足Slater条件,则可以推出原问题和对偶问题具有强对偶性;而由强对偶性可以推出该凸优化问题满足Karush-Kuhn-Tucker条件,其存在最优解。
2.4 迭代法求解求解凸优化问题式(22)的思路,先求其对偶问题的最优解λ*,即对偶函数q(λ)取得最小值时的λ;然后将λ*代入Lagrange函数L(x, λ)中,求解其取得最大值时的x*,即为原问题的最优解。对于特定车辆i,Lagrange函数为L(xi, λ),对偶函数为q(λi)。
q(λi)对λi的一阶偏导、二阶偏导分别为:
$ \nabla q\left( {{\lambda _i}} \right) = \frac{{\partial q\left( {{\lambda _i}} \right)}}{{\partial {\lambda _i}}} = C - \sum\limits_{j \in {V_i}} {{r_j}f\left( {m, {G_{ij}}{x_j}^{1/m}} \right)} $ | (31) |
$ {\nabla ^2}q\left( {{\lambda _i}} \right) = \frac{\partial }{{\partial {\lambda _i}}}\left( C - \sum\limits_{j \in {V_i}} {r_j}f\left( m, {G_{ij}}{x_j}^{1/m} \right) \right) = 0 $ | (32) |
因为q(λi)对λi的二阶偏导恒为0,所以D-WFPC算法选择梯度下降法来迭代求得λi的最优值。
L(xi, λ)对xi的一阶偏导、二阶偏导分别为:
$ \begin{array}{l} \nabla L\left( {{x_i}, \boldsymbol{\lambda} } \right) =& \frac{{\partial L\left( {{x_i}, \boldsymbol{\lambda} } \right)}}{{\partial {x_i}}} = - \frac{{{x_i}^{ - \left( 1 - \alpha \right)/m - 1}}}{m}\sum\limits_{j \in {V_i}} {{\omega _{ij}}} +\\ & \frac{{{r_i}}}{{m\Gamma \left( m \right)}}\sum\limits_{j \in {V_i}} {\left( {{\lambda _j}{G_{ji}}^m{{\rm{e}}^{ - {G_{ji}}{x_i}^{1/m}}}} \right)} \end{array} $ | (33) |
$ \begin{array}{l} {\nabla ^2}L\left( {{x_i}, \boldsymbol{\lambda} } \right) = \frac{{{\partial ^2}L\left( {{x_i}, \boldsymbol{\lambda} } \right)}}{{\partial {x_i}^2}} = \frac{{1 - \alpha + m}}{{{m^2}}}{x_i}^{ - \left( 1 - \alpha \right)/m - 2}\times\\ \sum\limits_{j \in {V_i}} {{\omega _{ij}}} - \frac{{{r_i}}}{{{m^2}\Gamma \left( m \right)}}\sum\limits_{j \in {V_i}} {\left( {{\lambda _j}{G_{ji}}^{m + 1}{{\rm{e}}^{ - {G_{ji}}{x_i}^{1/m}}}{x_i}^{1/m - 1}} \right)} \end{array} $ | (34) |
式中:i为车联网中的任意车辆,Vi为车辆i的邻居车辆集合,j∈Vi为车辆i的邻居车辆集合中的车辆; m为Nakagami-m分布的形状因子; α为效用函数中的参数; ωij代表车辆i和车辆j之间的权重;ri为车辆i的信标发射速率;λj为车辆j计算的自身代价;Γ(m)为参数是m的Gamma函数;xi为车辆i的信标发射功率的变化形式;Gji为车辆i和车辆j确定的值,具体定义见式(8)。
因为L(xi, λ)对xi的一阶偏导、二阶偏导都存在,考虑迭代的速度,所以D-WFPC算法选择牛顿法(Newton-Raphson Method)来迭代求得xi的最优值。
由上述步骤可以得到每辆车定时运行的D-WFPC算法的具体步骤:1)车辆i接收其邻居车辆集合中所有车辆广播的信标消息,其中包含邻居车辆的代价λj、信标发射功率的转换形式xj和发射速率rj,以及其他有用信息;2)根据梯度下降法进行一步迭代,更新自身的代价λi;3)根据牛顿法计算自身应该设置的信标发射功率的转换形式xi;4)根据xi设置自身的信标发射功率。
3 D-WFPC算法实现经过功率控制优化问题的建立和求解,最终得到每个车辆周期性运行的分布式加权公平功率控制(D-WFPC)算法。
D-WFPC算法的描述如下:
步骤1 车辆i接收其邻居车辆集合中所有车辆的位置dj、速度vj、代价λj、信标发射功率的转换形式xj和信标发射速率rj(j∈Vi)。
步骤2 车辆i根据接收到的信息更新自身的代价:
${\lambda _i} = \left[{{\lambda _i}-\sigma \left( {C-\sum\limits_{j \in {V_i}} {{r_j}f\left( {m, {G_{ij}}{x_j}^{1/m}} \right)} } \right)} \right]_0^ + $ |
步骤3 车辆i根据牛顿法计算当前需要设置的功率的转化形式:
$ {x_i} = NMP\left( {{x_i},{r_i},{\lambda _j}} \right);\;\;j \in {V_i} $ |
步骤4 车辆i设置发射功率pi=xi-1/m。
牛顿法NMP(xi, ri, λj)的函数描述如下:
输入 车辆i当前发射功率xi、发射速率ri、邻居车辆集合中所有车辆的代价λj(j∈Vi);
输出 车辆i应设定的发射功率的转换形式y。
1) start
2) n=1, x(n)=xi;
3) do
4)
5) n=n+1;
6) while |▽Lxi(x(n))|>ε
7) y=x(n);
8) end
其中,[t]0+=max{0, t},[t]ab=max{a, min{b, t}}。
4 仿真及结果分析文献[2]推荐使用双向耦合的网络模拟器和车辆交通移动模拟器进行仿真,从而得到更具有实际意义的结果。本文采用OMNeT++5.0和SUMO 0.25.0进行仿真,选取的仿真框架为Veins 4.4[17],根据仿真需要进行一定的修改。仿真参数及数值如表 1所示。
仿真场景为单向四车道高速公路场景,总长2.5 km,但仿真周期里所有车辆都在一个长度2 km的区段中。根据文献[10]的结论,取m=3作为Nakagami-m衰落模型的形状因子,因为效用函数具有严格凹性的前提条件为α≥m+1,所以取α=5。路径损耗系数β一般为[2, 4],仿真取β=2。物理层和介质访问控制(Media Access Control, MAC)层的协议分别是IEEE 802.11p和IEEE 1609.4,其载波频率为5.9 GHz,数据传输速率为6 Mb/s。仿真考虑信道的切换,在控制信道(Control Channel, CCH)和服务信道(Service Channel, SCH)之间连续来回切换,切换周期为50 ms,因此,信标传输的理想最大容量为总容量的一半(3 Mb/s)。为了使信道更容易达到拥塞情况,信标大小取5000 b(625 B),信标发射速率每秒取10个。在理想状况下,如果通信质量足够好,即所有车辆都在彼此的通信范围内,一个车辆的邻居车辆集合中的车辆总数最大为60,此值作为一个分界点。文献[18]表明信道在容量为60%~70%时表现最好,因此本文取信道理想最大容量的60%作为最大信标负载C,即1.8 Mb/s。
4.1 平均端到端时延仿真实验对本文提出的D-WFPC算法,与固定发射功率(50 mW、200 mW)方案、FCCP算法[5]在平均端到端时延方面进行比较,固定发射功率方案是没有优化的原始方案,FCCP算法是已有的发射功率动态控制算法。如图 3所示,随着网络中车辆总数的增加,上述方案的平均端到端时延均不断增大,其中固定发射功率200 mW方案所对应的平均端到端时延增长最快。网络中车辆总数为60辆之前,所有方案的平均端到端时延差别不大;超过60辆之后,D-WFPC和FCCP算法均明显优于固定发射功率方案,并且D-WPFC算法与固定发射功率方案相比,最多能减小超过4 ms的平均端到端时延,降幅达到24%;与FCCP算法相比,能减小超过1 ms的平均端到端时延,降幅为10%。WAVE中固有的载波监听多路访问/冲突避免(Carrier Sense Multiple Access with Collision Avoidance, CSMA/CA)机制是基于竞争的MAC机制,在高密度车流环境下会产生频繁的冲突,导致退避次数急剧增多,退避时延不断增大,因此网络中的平均端到端时延随着车辆总数的增加而增大。固定发射功率方案无法改变车辆通信范围内的车辆数量,而D-WFPC和FCCP算法动态调整网络中车辆的发射功率,从而调节通信范围,控制车辆自身通信范围内的车辆数量,减少退避次数,从而减小平均端到端时延。D-WFPC算法考虑了车辆的移动性,将车辆间的相对速度和相对距离作为权重参数设计效用函数,使得分配的发射功率具有加权公平性,平均端到端时延也低于FCCP算法。
仿真将D-WFPC算法与固定发射功率(50 mW、200 mW)方案、FCCP算法在网络丢包率方面进行比较。丢包主要来源于信标接收时的信干噪比(Signal to Interference plus Noise Ratio, SINR)过低和碰撞。如图 4所示,随着网络中车辆总数的增加,上述方案的丢包率均不断增加,其中固定发射功率200 mW方案的丢包率增加最快。车辆总数为80辆之前,固定发射功率50mW方案的丢包率最低;超过80辆之后,D-WFPC和FCCP算法均明显优于固定发射功率方案,相对于固定发射功率200 mW方案,D-WFPC算法能降低44%左右的丢包率。当车辆总数较少时,D-WFPC和FCCP算法均会将车辆发射功率调至最大,随着车辆总数的增加,通信范围内车辆数目增加,两种算法均会自适应地调节发射功率,车辆总数越大,它们相对于固定发射功率方案的性能提升越大。虽然固定发射功率50 mW方案在车辆总数较小时丢包率较低,但是其通信距离较小,感知车辆周围环境的能力不及动态功率调整算法。
由图 4可知,D-WFPC与FCCP算法相比,在车流密度较小时,网络丢包率相似;在车流密度较大以至于出现拥塞时,网络丢包率能降低超过4%。在高密度车流环境下,车辆总数的增加导致网络中同一时间内传输的信标数量增多,从而带来更加频繁的信标碰撞和更大强度的噪声干扰。碰撞次数增大直接会造成丢包数量增多;接收信标时噪声干扰增大导致SINR降低,SINR降低会造成无法正确接收的信标数量增多。因此,网络中的平均丢包率随着车辆总数的增加而增大。固定发射功率方案无法改变车辆通信范围内的车辆数量,而D-WFPC和FCCP算法动态调整网络中车辆的发射功率,从而调整其通信范围,控制车辆自身通信范围内的车辆数量,减少信标传输过程中的碰撞和噪声干扰,从而降低丢包率。D-WFPC算法考虑了车辆的移动性,更符合车联网的节点移动特性,丢包率也略低于FCCP算法。
4.3 算法收敛性D-WFPC算法是基于两层迭代来求解最优值:梯度下降法求解代价,牛顿下降法求解发射功率变换形式的最优解,因此迭代到最优解的收敛速度是需要考察的性能。车辆节点总数为80辆的一次仿真实验中,某辆车前50次执行D-WFPC算法得到的最优发射功率如图 5所示。
从图 5中可以看出,在20次之后该车辆的发射功率达到收敛,符合快速收敛特性。
5 结语针对车联网中高密度车流环境下的信道拥塞问题,本文提出一种基于网络效用最大化的分布式加权公平功率控制算法D-WFPC,每个车辆根据实时本地负载动态调整自身的信标发射功率,使本地负载在阈值之下,从而避免信道拥塞。建模时采用更符合实际车联网环境的Nakagami-m衰落模型,引入随机信道,具有实际意义。仿真结果表明,与固定发射功率方案、FCCP算法相比,D-WFPC算法在网络平均端到端时延和丢包率方面,均有明显的性能提升。改变发射功率,不仅会改变通信范围,还会改变干扰和冲突的布局,因此,更有效地研究发射功率的改变对整个网络的影响,可作为进一步的工作方向。
[1] | MA X M, CHEN X B. Delay and broadcast reception rates of highway safety applications in vehicular Ad Hoc networks[C]//Proceedings of the 2007 Mobile Networking for Vehicular Environments. Piscataway, NJ:IEEE, 2007:85-90. 10.1109/MOVE.2007.4300809 |
[2] | EZE E C, ZHANG S J, LIU E J, et al. Advances in Vehicular Ad-hoc NETworks (VANETs):challenges and road-map for future development[J]. International Journal of Automation and Computing, 2016, 13(1): 1-18. DOI:10.1007/s11633-015-0913-y |
[3] | TORRENT-MORENO M, MITTAG J, SANTI P, et al. Vehicle-to-vehicle communication:fair transmit power control for safety-critical information[J]. IEEE Transactions on Vehicular Technology, 2009, 58(7): 3684-3703. DOI:10.1109/TVT.2009.2017545 |
[4] | MITTAG J, SCHMIDT-EISENLOHR F, KILLAT M, et al. Analysis and design of effective and low-overhead transmission power control for VANETs[C]//Proceedings of the 2008 Fifth ACM International Workshop on Vehicular Inter-networking. New York:ACM, 2008:39-48. http://dl.acm.org/citation.cfm?id=1410051 |
[5] | EGEA-LOPEZ E. Fair distributed congestion control with transmit power for vehicular networks[C]//Proceedings of the 2016 IEEE 17th International Symposium on "A World of Wireless, Mobile and Multimedia Networks". Piscataway, NJ:IEEE, 2016:1-6. https://www.computer.org/csdl/proceedings/wowmom/2016/2185/00/07523571-abs.html |
[6] | FALLAH Y P, NASIRIANI N, KRISHNAN H. Stable and fair power control in vehicle safety networks[J]. IEEE Transactions on Vehicular Technology, 2016, 65(3): 1662-1675. DOI:10.1109/TVT.2015.2411275 |
[7] | EGEA-LOPEZ E, PAVON-MARINO P. Distributed and fair beaconing rate adaptation for congestion control in vehicular networks[J]. IEEE Transactions on Mobile Computing, 2016, 15(12): 3028-3041. DOI:10.1109/TMC.2016.2531693 |
[8] | 刘明剑, 谭国真, 李帅兵, 等. 基于信道拥塞代价计算的车联网自适应消息发送速率控制方法[J]. 通信学报, 2016, 37(10): 108-116. (LIU M J, TAN G Z, LI S B, et al. Adaptive message sending rate control method based on channel congestion cost calculation in VANET[J]. Journal on Communications, 2016, 37(10): 108-116. DOI:10.11959/j.issn.1000-436x.2016202) |
[9] | CHENG L, HENTY B E, STANCIL D D, et al. Mobile vehicle-to-vehicle narrow-band channel measurement and characterization of the 5.9 GHz Dedicated Short Range Communication (DSRC) frequency band[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(8): 1501-1516. DOI:10.1109/JSAC.2007.071002 |
[10] | KILLAT M, HARTENSTEIN H. An empirical model for probability of packet reception in vehicular Ad Hoc networks[J]. EURASIP Journal on Wireless Communications and Networking, 2009, 2009:Article ID 721301. http://dl.acm.org/citation.cfm?id=1554311 |
[11] | KELLY F P, MAULLOO A K, TAN D K H. Rate control for communication networks:shadow prices, proportional fairness and stability[J]. Journal of the Operational Research Society, 1998, 49(3): 237-252. DOI:10.1057/palgrave.jors.2600523 |
[12] | LOW S H, LAPSLEY D E. Optimization flow control-Ⅰ:basic algorithm and convergence[J]. IEEE/ACM Transactions on Networking, 1999, 7(6): 861-874. DOI:10.1109/90.811451 |
[13] | MO J, WALRAND J. Fair end-to-end window-based congestion control[J]. IEEE/ACM Transactions on Networking, 2000, 8(5): 556-567. DOI:10.1109/90.879343 |
[14] | JOSE J, LI C, WU X Z, et al. Distributed rate and power control in DSRC[C]//Proceedings of the 2015 IEEE International Symposium on Information Theory. Piscataway, NJ:IEEE, 2015:2822-2826. http://ieeexplore.ieee.org/document/7282971/ |
[15] | 王飞. 基于网络效用最大化的无线网络资源分配研究[D]. 重庆: 重庆大学, 2012: 7-10. (WANG F. Study on wireless resource allocation based on network utility maximization[D]. Chongqing:Chongqing University, 2012:7-10.) http: //cdmd. cnki. com. cn/Article/CDMD-10611-1013007977. htm |
[16] | BOYD S, VANDENBERGHE L. Convex optimization[M]. Cambridge, MA: Cambridge University Press, 2004: 215-271. |
[17] | SOMMER C, GERMAN R, DRESSLER F. Bidirectionally coupled network and road traffic simulation for improved IVC analysis[J]. IEEE Transactions on Mobile Computing, 2011, 10(1): 3-15. DOI:10.1109/TMC.2010.133 |
[18] | FALLAH Y P, HUANG C L, SENGUPTA R, et al. Congestion control based on channel occupancy in vehicular broadcast networks[C]//Proceedings of the 2010 IEEE 72nd Vehicular Technology Conference Fall. Piscataway, NJ:IEEE, 2010:1-5. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=5594504 |