基于车载自组织网络的数据和能量协同路由算法

陈翰林,胡 明,2,胡洁珺,颜 辉

(1.长春工业大学 计算机科学与工程学院,长春 130012；2.长春工程学院 计算机技术与工程学院,长春 130012；3.吉林大学 计算机科学与技术学院,长春 130012；4.长春工程学院 吉林省水利电力工程物理级仿真与安全科技创新中心,长春 130012)

0 引 言

车载自组织网络(vehicular ad-hoc networks,VANET)[1]作为智能交通系统(intelligent transport system,ITS)的一个重要组成部分,近年来备受关注[2].ITS系统的主要目标是减少道路交通事故导致的死亡和财产损失,同时提供驾驶舒适性[3].VANET作为结构开放、自组织、方便实用的无线通信网络,为ITS提供了更好的通信环境.一般在ITS中可分为两种通信模型[4]: 车辆到车辆通信(vehicule to vehicule,V2V)和车辆到基础设施通信(vehicule to road,V2R),也称为车辆到路边单元通信.

VANET通常是指具有可选基础设施支持的移动车辆的无线Ad-hoc网络.一种情况是采用基础设施独立的VANET可由一组移动车辆节点自发地构建,这些节点在附近移动并不依赖于基础设施;另一种情况,VANET的许多新兴应用程序(依赖于基础设施)利用各种公共和私有基础设施进行研发,例如公共/私有云、政府机构服务器等.本文采用后一种VANET类型.与基础设施无关的VANET相比,依赖于基础设施的VANET的特点为有大量后端基础设施的存在,例如路边单元(roadside units,RSU)的使用.

RSU在VANET中具有重要作用.RSU是将VANET连接到Inter网的外部网络的中继节点,提供组合有线和无线链路的混合路由路径,用于远程VANET节点间的高速大容量通信.通过使用高速数据链路在远程车辆间的信息通信,可显著减少延迟.而且RSU是VANET中协作和分布式应用程序的关键组件.目前,RSU也被考虑作为连接车载网络和宽带网络(如蜂窝网络)的网关,从而扩展VANET的覆盖范围并为用户提供服务.但存在部署和运营信息系统成本较高的问题.以农村地区为例,RSU通常由电网供电,需要物理基础设施连接RSU,从而导致部署和维护信息系统的成本增加.因此,可通过研究能源合作和可再生能源问题,实现VANET网络周期最大化,以降低成本.在VANET中,使用具有能量收集和能量存储的RSU,能量收集源根据环境提供随机可用的能量,但这种存储设备的容量有限.当RSU未获得足够的能量或没有充分可用的能量时,其充电达不到合适的饱和状态.RSU必须能通过适应能量收集过程要求和通信要求,才能有效管理其可用能量.

近年来,关于VANET的研究已有许多成果,关于RSU的相关研究工作有：RSU设置和管理,车辆到RSU的数据传输和访问调度,车辆与RSU间的通信设置.

1) RSU的能量收集.Atallah等[5]研究了能量收集系统在车辆环境中的挑战和可用性；Vageesh等[6]研究了电网和太阳能供电的RSU,并提出了部署RSU数量的优化策略,证明了将最佳RSU布局策略与高效的睡眠调度方法相结合的策略,可使整体成本降低；Ibrahim[7]提出了太阳能收集电路RSU的设计；Ali[8]提出了一种基本的电源管理方案,降低了RSU的功耗；Muhtar等[9]考虑了RSU由可再生能源——风能提供动力的车载自组网络,并根据所需能量、数据包阻塞概率和平均数据包延迟分析了网络性能.但上述研究只考虑了能量收集下RSU的实时调度成本问题,并未对收集的能量进行管理和合理分配等问题展开相关研究.

2) RSU的功耗和管理.Yang等[10]将数据传输和能量传输的收敛视为一个完整的系统,不仅考虑了物理层,还考虑了更高层;Fouladgar等[11]提出了在接收节点后,循环使用节点的思想,并考虑了能量和数据传输,以达到最大化通信网络中数据速率的效果；Gurakan等[12]提出了具有数据和能量协作的能量收集通信网络延迟最小化问题；Dai等[13]提出了无线传感器网络中数据路由和能量路由的联合优化算法；Wu等[14]提出了一种基于IEEE 802.11的能量MAC层协议,为ITS通信模块提供能量；Zou等[15]研究了RSU调度节能问题,目的是如何在给定时间内打开和关闭它们的最佳可用时间表,以便在网络连接时降低系统中RSU的总能量消耗率；Hammad等[16]考虑了在满足车辆通信需求的同时,最小化路边接入点所需能源的问题,为任何可实现调度算法的性能提供了一个上界,使用车辆位置和速度输入解决该问题;Tao等[17]提出了两种不同的指标确定连通性指数和节能指数,提高了VANET中RSU的连通性和节能效率；雷建军等[18]提出了一种能量有效的数据收集协议，通过在不计算睡眠调度算法获得的能量增益情形下，减少网络整体能耗.

3) RSU数据传输和通信管理.Jiang等[19]提出了一种公共车辆网络,公共车辆和路边单元RSU一起用于交通数据传播,以便得到更高的覆盖率；Huang等[20]提出了一种基于总线的nexthop转发方案,并分析了车载自组网络总线辅助多播容量的上限和下限,车辆在向其他节点发送消息时选择总线作为下一跳转发节点；Reis等[21]设置车辆作为车载自组网络的中继转发节点,即使用普通车辆作为临时路边单元RSU充当网络中其他车辆的通信桥梁,但普通车辆(临时RSU)的短暂停靠有可能使整体系统的稳定性和可靠性极大降低.

4) 网络生命周期.Hu等[22]提出了一种可持续性、高质量的MCS感知任务执行的博弈方法,从而提高了网络的生命周期；林海峰等[23]提出了一种启发式解决方案,可最大化网络生命周期,并尽可能地保证传感器自身的能量大于传输到其最近邻居节点所需的能量限度；Gatzianas等[24]研究了计算数据流的问题,最大化网络生命周期,但两个链路上的传输速率都是固定的,并且只考虑了有效负载传输功率；Yildiz等[25]提出了一个通信和计算功耗之间最佳权衡的框架,并研究了在延迟服务质量约束下的网络寿命最大化问题;曹建玲等[26]提出了一种能量高效分簇算法协议延长网络生存时间.

本文主要研究能量收集的RSU与参与车辆间的能源合作问题,以实现最大网络生命周期的目标.本文将能源合作引入VANET中,即RSU节点与邻居RSU节点协作,并且RSU节点可接收下行链路车辆传输能量,从而达到RSU可维持工作所需的能量.同时为了更好地实现网络生命周期最大化,本文提出一种分布式Lagrange-Newton迭代算法,并证明该算法具有良好的收敛性和准确性.模拟实验结果表明,有能量合作的VANET比无能量合作的传统VANET具有更好的网络生命周期.

1 系统模型

1.1 物理问题

本文研究在具有能量合作的车载自组网络中联合优化数据和能量路由的问题,以实现网络生命周期最大化.假设:

图1 VANET中数据和能量的协作路由Fig.1 Collaborative routing of data and energy in VANETs

1) RSU可部署在静态位置,移动交通车辆可根据需要部署在可控的位置;

2) 每个RSU上都部署能量收集装置；

3) 对于部署车辆,假设每辆参与车辆都不会延误,其运动轨迹是相对静止的,即当参与车辆将数据上传到相邻的RSU时,可检测到车辆位置；

4) 每个参与车辆只能在RSU的感知覆盖范围内进行能量传输.

在上述场景下,RSU向其邻居RSU传输数据和能量,车辆向最近的RSU传输数据和能量,包括其ID、电池状态、感测数据大小.该过程将形成新VANET的拓扑结构,如图1所示.

1.2 模型构建

(1)

1.2.2 能量模型 考虑RSU能源管理和能源合作.每个RSU仅由可再生能源和下行车辆传输能量供电.所有RSU节点都配备了能量收集设备,可从环境中获取能量并将其存储在可充电电池中.由于位置随机,不同环境中的RSU节点具有不同的能量收集率,RSU节点m的能量收集率表示为hm.在RSU节点m的感知范围内,每个车辆n都可将能量上传给RSU节点m,其中单个车辆上传能量表示为En.此外,RSU不接受来自电网的电力供应.因此,RSU节点m收集的电池能量Bm可表示为

(2)

(3)

考虑到能量可持续性条件,类似于传统的数据路由,在网络中最佳能量流的引导和决策同样具有重要作用,称为能量路由.与数据路由类似,每个能量链路标记为q={1,2,…,Q},定义Oe(m)为从RSU节点m流向相邻RSU节点N(m)在链接q上的输出能量流;Ie(m)定义为从相邻RSU节点N(m)到RSU节点m在链接q上的输入能量流;eq为转移的能量;θq表示转移效率.因此,能量可持续性条件应满足：

(4)

确保了每个RSU节点的能量供应率不低于能量消耗率.式(4)中右边两项分别表示通信和能量转移中的能量消耗率;左边三项分别是能源合作中的能量收集率、车辆传输能量和能量接收率.

1.3 目标函数

本文的优化目标是最大化网络生命周期,首个RSU节点的能量耗尽将导致整个网络生命周期结束.网络生命周期Tnet定义[28]为

(5)

2 模型求解方案

针对式(6)采用分布式优化的方法,每个RSU节点与其邻居RSU交换数据时可计算出最佳路由,并伴随着网络中的迭代,每个节点的计算复杂度不随网络规模而变化.因此本文提出一种分布式Lagrage-Newton迭代算法[29]求解该问题.

问题转换后,应用Lagrange更新式(10)的优化变量,得

其中γq和ηl是Lagrange乘数.KKT最优性条件为

其中:

n(l)和m(l)分别为数据链路l的源节点和目的节点;k(q)和z(q)分别为能量链接q的源节点和目标节点.互补的松弛条件为

(20)

其中Δ是防止出现复根而影响算法收敛性的算子,Δ≥0.通过计算式(20),可在迭代中获得最优变量值为

目标函数中的变量将在迭代后逐步改变,可表示为

(22)

根据Newton算法的收敛性,式(22)的步长需满足的条件为

(23)

通过迭代允许能量一次通过链路的前提条件是所有链路都经常被访问.

需在迭代前调查任何可能传输的能量,跟踪每个能量链路上的传输能量,以便在最优解中确定哪些能量链路处于活动状态.在迭代检测时,当γk(q)<θqγz(q)时,搜索满足式(21)的γq.如果无解,则有γk(q)>θqγz(q), 表明RSU节点不具备转移的能量,需要车辆进行能量传输.因为目标函数的严格凸性,因此确定每次迭代都减小了目标函数.由于算法的收敛性,有界实单调序列总收敛,并且极限点是局部最小值,因为迭代只能在能量链路的γk(q)=θqγz(q)时停止,其中eq>0,因此它们与式(16)的KKT最优条件相同.由于问题的凸性,因此这个局部最小值也是唯一的全局最小值.

算法1分布式协同Lagrange-Newton优化算法.

步骤1) 初始化: 设定k=1,Δ≥0,λ∈(0,1),ε≥0;

步骤2) 更新变量: 利用式(21)更新其主要变量；

步骤3) 传递权重变量：RSU节点和车辆节点需要将初始值发送给邻近RSU;

步骤4) 行搜索变量: 计算步长λk,如果满足式(23),则转步骤5)；否则步长λk=λk/4,转步骤4)；

步骤5) 增加迭代次数: 设置k=k+1,转步骤2)；

3 实验结果

图2为当有100辆车参与时,将数据包发送到sink事件区域内RSU节点的能量消耗.由图2可见,与无能量合作的情形相比,有能源合作将消耗更少的能量.图3为在车载自组网络中彼此通信所需的额外时间.由图3可见,与无能量收集的情形相比,有能量收集时的网络延迟减少了.

图2 RSU节点的能量消耗Fig.2 Energy consumption of RSU node

图3 网络开销Fig.3 Network overhead

图4 车辆数量与网络生命周期的关系Fig.4 Relationship between vehicle quantity and network life cycle

图4为车辆数量与网络生命周期的关系.由图4可见,随着车辆数量的增加,网络生命周期不断递增,最终趋于平稳.这是因为当车辆达到RSU感知覆盖范围饱和时,网络生命周期将不会随着车辆数量而增加.因此,有能量收集的情形比无能量收集的情形具有更长的网络生命周期.图5为RSU数量与网络生命周期的关系.由图5可见,有能量合作时的网络生命周期远大于无能量合作时的网络生命周期,但这种情形也不是绝对的.当RSU数量小于50时,无能源合作情形下有200辆车参与比有能源合作情形下有100辆车参与时网络生命周期更优.图6为次梯度算法与本文算法的收敛性对比.由图6可见,本文算法收敛性更好.

图5 RSU数量与网络生命周期的关系Fig.5 Relationship between RSU quantity and network life cycle

图6 不同算法的收敛性对比Fig.6 Comparison of convergence of different algorithms

综上所述,本文在车载自组网络中,通过RSU间的能量合作和RSU与下行车辆的能量传输,实现了网络生命周期最大化.在提出的协同路由策略中,车载自组网络的每个RSU和车辆都需要考虑数据流和能量流,确定数据流与能量流的联合问题,以及RSU之间的能量合作和能量收集.本文提出了一种分布式Lagrange-Newton迭代算法求解该问题,为算法的收敛性建立了必要条件.实验数值结果表明,VANET策略中的能量和数据路由协作可有效改善网络生命周期.