基于隐马尔可夫模型的高速公路路由算法.pdf
《基于隐马尔可夫模型的高速公路路由算法.pdf》由会员分享,可在线阅读,更多相关《基于隐马尔可夫模型的高速公路路由算法.pdf(9页珍藏版)》请在咨信网上搜索。
1、技术广角 64基于隐马尔可夫模型的高速公路路由算法摘要 在VANET高速公路场景中,由于车辆高速运动导致车辆和车辆、车辆和RSU之间所构成的网络拓扑频繁改变,使得绝大多数路由协议需要及时更新自己的邻居表来指定路由。针对邻居选择错误会导致数据不断重发、传输时延高且不可靠等现象,文章提出SDN-NDHM算法解决邻居选择错误的问题。算法利用典型的GPSR算法思想,运用HMM来预测高速运动节点的下一时刻位置信息,并且利用SDN来修正预测值、集中管理和调度网络资源。通过MATLAB的仿真实验表明,该算法与经典的GPSR改进算法相比能更好判断车辆节点的加入和离开,并且拥有更好的平均邻居正确率和更高的吞吐量
2、。关键词 车载自组网;GPSR协议;隐马尔科夫模型;软件定义网络;平均邻居发现错误率;吞吐量周德宇1 袁学松21 昆明理工大学 昆明 6505002 安徽机电职业技术学院 芜湖 241000引言车载自组网(VehicularAd-hocNetwork,VANET)是包括无线通信、道路交通、自组织系统等交叉学科的一个领域1。它使用车载相关电子设备(如全球定位系统、北斗卫星导航系统、电子地图、车内各种控制传感器和无线通信装置等)来实现车车、车基础设施之间的相互数据通信2。VANET可以提供安全类和非安全类业务两种服务,这两种服务可以提高驾驶员的行车安全性和舒适度。安全类业务主要分为预警交通事故和交
3、通危险信息等,非安全类业务主要分为接入互联网和车载多媒体等1。进入21世纪以来,由于研究人员的大力研究,VANET发展得很快,其中一项研究重点是根据业务的需要,设计可靠性高且安全高效的路由协议。Karp于2000年提出GPSR协议3,该协议是如果数据包不能直接转发到目标节点,则尽量选择最靠近目标节点的节点作为中继进行转发,这样转发次数大大降低,从而使得转发效率提升。但在高速运动情况下,如果不能找到合适的中继或中继在转发数据过程中由于各种原因不能当做中继,GPSR会始终重新发现邻居,因此可能多次重新发送数据包。这样会降低吞吐量,使安全类消息得不到及时传输。为此,我们建立模型并分析车辆的运动规律,
4、使用隐马尔科夫模型(HiddenMarkovModel,HMM)预测出源节点所有邻居节点的下一时刻的位置,并更新源节点的邻居表。这项工作的另一个愿望是选择一个合适的中继,以更高的概率将消息转发到目标车辆。与其他网络不同,车辆网络可以是密集的,也可以是稀疏的,具体取决于位置、时间等。本文我们提出了一种改进方案,在稀疏和密集条件下以最少的时间将数据从源节点传递到目标节点。故本文提出一种适用于高速公路的由SDN、HMM和分簇思想组成的邻居发现方法,重点在于邻居的发现基金项目:2019年度安徽省高校优秀青年人才支持计划(2019gxyq332);2021年安徽省高校自然科学重点项目(KJ2021A15
5、21)。技术广角 65和预测下一时刻节点的位置。1 相关工作针对上述问题,学者进行了大量的研究。到目前为止,基于地理位置路由协议研究主要集中在城市场景4,高速公路场景较少。遭遇感知和基于聚类的路由算法(Encounter-awareandClustering-basedRoutingAlgorithms,ECRA)5:在城市中,为了找到通往目的地的路线,ECRA允许车辆跟踪其他车辆。ECRA用分簇来管理车辆之间的关系。所选簇头在ECRA表中跟踪历史遭遇信息(如遭遇位置、时间、节点ID)并交换该信息以查找下一个相遇点。但这种方法忽略了簇内通信开销,这限制了簇的性能。BTSC算法6为了选择公交车密
6、度最高的最佳路线,分析城市每条街道出现公交车的概率。此外,BTSC使用蚁群算法在两个公交车间获得可靠链接。与其他基于公交体系结构相比,路上所有车辆都可用来中继数据包。故BTSC优化了选择路由和中继策略,以提高数据包传递率(PacketDeliveryRatio,PDR)和延迟性能。NDK算法2使用卡尔曼滤波(KalmanFilter,KF)方法预测高速公路场景下源车辆所有邻居节点的下一时刻的位置。但KF仅能准确地估计线性的过程和测量模型,不能在非线性的场景中准确估计。为了保证线性环境,需假定过程模型为恒定速度模型,但在高速公路场景中多数是非恒定速度的情况,故KF不适合所有的高速公路场景。人工神
7、经网络(ArtificialNeuralNetworks,ANN)是一种通过模仿动物神经的特征,进行分布式并行信息计算或者处理的数学模型7。ANN有以下缺陷:1)ANN没能力来解释自己的推理过程和推理依据;2)ANN需要更多地控制算法的细节,由于它相对复杂,开发需要的时间也更长,相比传统算法的计算代价更高;3)ANN的结果一定丢失信息,因为ANN把所有问题的特征和推理都变为数字和数值计算;4)ANN通常需要更多更充分的数据来训练,而其它算法可用较少的数据很好地解决;5)ANN的计算能力很大程度上取决于数据的大小、网络的深度和复杂程度,如果网络复杂,需要训练几周的时间才能学习到符合条件的结果。为
8、了解决上述问题,本文采用HMM技术。HMM与RuslanL.Stratonovich提出的最优非线性滤波问题有关,故HMM可解决非线性问题,计算复杂度较低。为了扩大数据传输范围,本文通过分簇选择簇头的思想来确定中继。由于选择簇头的目的是确定中继,所以无需考虑簇内通信开销。HMM训练时间需几分钟到几个小时即可。而基于HMM的地理位置路由协议研究主要在城市场景8。由于车辆处于移动状态,其最终位置未知,所以最终车辆位置是隐藏状态,并且车辆到达的路段是可观测状态。然后根据历史记录表中记录的访问时间和次数来判断车辆的频繁访问目的地路段,接着使用这些城市路段作为HMM的转移矩阵的参数。该协议不适合低密度场
9、景(019节点)。一些VANET的研究者通过携带转发使得网络拓扑的联通性提高。文献9提出了一种密度感知定向转发策略,它综合考虑了车辆密度因子和方向转发,用于下一跳选择。TGF10可找到跳数更少、传输延迟更低和控制数据包更少的转发路径。文献9-10所提出的协议均解决了城市场景中低密度节点的问题。尽管携带转发可解决多次重新发现邻居问题,但由于需邻居携带转发,使源节点到目标节点端到端时延(EndtoEndDelay,EED/E2E)较高,故不适合安全消息传输。一些VANET研究人员的研究表明11,在城市和高速公路场景中使用车辆作为邻居节点,可降低RSU的成本和扩大VANET的网络覆盖范围。文献12提
10、出了一种RSU辅助的中继调度算法,这种算法在最大限度地降低RSU能耗的同时能够更快地检索到目标车辆的数据。对于中继节点选择,可以使用基础设施辅助的技术广角 66混合路由,使用RSU帮助车辆节点选择空闲信道和中继节点13。CM14将固定点周围的一些车辆用作通信目的的收发器,称为虚拟交叉点。虚拟交叉点根据交叉点之间的密度和距离为相邻道路分配权重。此外,源车利用CM选择下一个中继车辆。CM点位于距离每个邻居的所有距离之和最小的位置。这些研究均不适合低密度场景。综上所述,现有文献缺乏考虑高速公路稀疏场景和密集场景的邻居选择优化,故本文提出一种基于软件定义网络的隐马尔可夫模型高效邻居发现方法(Softw
11、areDefineNetwork-NeighborDiscoverymethodbyHiddenMarkovmodel,SDN-NDHM)。SDN-NDHM第一个目的是建立模型并分析车辆的运动规律,使用HMM预测源节点所有邻居节点的下一时刻位置,并更新自身邻居表。SDN-NDHM利用车辆和RSU来传送和转发消息,控制器计算所需数据。我们工作第二个目的是通过SDN-NDHM找到一个合适的中继,以更高的概率将消息转发到目标车辆。成功实现SDN-NDHM算法依赖于高速公路中的稀疏和密集车阵场景,不包括堵车和城市场景。2 通过HMM对车辆节点下一时刻位置预测SDN-NDHM算法假设全部车辆节点均安装了
12、定位装置,并且假设车辆和RSU的通信范围是一个标准的圆。同时,车辆节点可以通过车载装置获得基本数据,如该车辆的准确位置、速度值、ID号、加速度和运动方向等。2.1 GPSR在高速公路场景下的一些问题在高速公路(或城市快速路)场景中,使用一些基于地理位置的路由协议(如GPSR等)时会出现中继丢失15。如图1(a)的情况,A节点在t时刻需要和C节点进行数据通信并且已经生成了数据包。依照GPSR的规则,A需要传输的数据包将被转发至B节点,因为B最接近C并且在A的通信范围内。而在t时刻,A分配到信道传输数据,如图1(b)所示。此时,由于C不在B的通信范围内,A无法将数据包传输给C,这样就会造成中继的丢
13、失。这种节点的丢失会使A需要根据GPSR重新发现中继和重传数据包,这使得网络的负载增加。为了防止重新发现节点的情况对网络拓扑的不利影响,路由协议设计的重点是实时预测源节点通信范围内所有节点下一时刻的基本信息(如位置、速度值、加速度和运动方向等)。在下一节中,我们将使用HMM对节点的位置进行预测,以减少中继节点丢失的情况。2.2 隐马尔科夫模型预测节点下一时刻位置HMM是关于时间序列的概率模型16。HMM的工作原理是通过分析可观测的参数来确定隐含参数,然后再分析这些隐含参数,从而得到我们想要的结果。HMM适合对未观测到的状态进行建模。在HMM中,状态不一定是直接可见的,但是可以观测的状态是可见的
14、8。不可测量的时序称为隐含状态序列,可测量的时序称为观测序列。图1(a)正常初始状态 图1(b)下一时刻(t,)状态注:矢量,速度加速度RSU适合当中继的车辆图1 单侧RSU和中继结合的定向传输模型一个HMM模型可由以下几个参数来表示。1)隐藏状态的数量。2)可观察状态的数量。3)隐含状态集合:(1)4)观测状态集合:(2)5)状态转移矩阵:(3)技术广角 67其中。6)输出矩阵:(4)其中。7)初始概率矩阵:(5)其中。我们采用前向后向算法对HMM准确建模。相关变量定义如下:表示前向变量给定模型,累积观测序列和时间 时隐藏状态 的概率;表示后向变量未来观察序列的概率直到时间,给出模型 和时刻
15、的隐藏状态;表示给出模型+1的时间 到隐藏状态的概率 和观察序列;表示给定 和观察序列 时的隐藏状态 的概率。前向-后向算法的调整过程如下17:1)初始化;2)计算和;3)调整和;4)如果增加,请转到2)。在HMM中,转换和观察都可以用于预测下一个状态,应用式(6)来预测在时间t的状态分布下的时间t+1的状态分布:(6)此外,是观察时间+1用于进一步约束状态分布。(7)2.3 邻居节点的维护自从GPSR提出以来,地理位置路由算法是研究的热点,许多学者对其进行了改进。但是这些改进的算法中最佳邻居(OptimalNeighbor,ON)的选择主要利用当前时刻与下一时刻的距离或者导航路径来确定ON是
16、否在源节点和目标节点的通信范围内。在SDN-NDHM中,建立了一个含有适应度函数(fitness(),()的邻居表并且利用分簇的思想选择ON。该邻居表使用HMM预测源节点所有邻居节点下一时隙的位置,得到预测的结果以后根据分簇思想选择簇头,新的簇头用于更新源节点的邻居表信息。下面将重点介绍SDN-NDHM维护邻居表的方案,以及邻居节点加入和离开过程。本文仅仅考虑2跳完成,即在邻居表中只选择一个ON。如果通过一个ON数据传输到目标节点仍然失败,则不传输数据。因为当网络中存在3到4跳时,路由寿命的陡降可能导致路由错误18。在图1(b)中t时刻,若A节点需将数据传递给C,分以下几个情况。1)A搜索自己
17、的邻居表,以确定是否含有C。2)如果含有C,则更新邻居表。邻居表里的数据包含了A的邻居节点、当前时刻的A与所有邻居节点的()值、同时SDN-NDHM计算下一时刻邻居节点的()值、下一时刻邻居节点的基本数据之后加入邻居表。3)如果通过计算可知,C不是邻居表中的邻居节点,SDN-NDHM会将数据传输给节点D,因为D是A的邻居表里下一时刻与源节点同方向邻居节点中()值最大的。ON是通过选择簇头的方法来确定的。我们首先引入了一个与节点功率相关的参量和节点的度,达到延长邻居寿命的目的。其次,设置次佳邻居(SuboptimalNeighbor,SN),以提高PDR。最后,SN的功能是帮助ON降低通信负担,
18、并在需要的时候成为新的ON。在一些特殊情况下,车队组网通信将受到多种因素的影响:节点的功率和节点的度。综合考虑上述因素,技术广角 68权值由()确定:(8)其中 是一个与节点功率相关的参量,为节点的度。选择ON和SN过程如图2所示,描述如下。1)在有车辆需要传输数据时,车辆向RSU发送车辆ID号、车辆的度、功率、位置、车速、方向、通信范围和半径等基本信息,RSU将信息转发给SDN。2)SDN计算源车辆是否在RSU通信范围内,如果不在则计算其通信范围内的车辆的(),并根据内容建立邻居列表。3)SDN计算()后,选择源车辆通信范围内()最大的同方向车辆作为ON。如果有多辆车的()相等,则ON是ID
19、号最小的车辆。4)按照3)的方式选择一个()第二小的车辆为SN,如果按照3)的方式得到多辆车的()相同,则取ID号第二小的车辆作为SN。5)SDN判断BN能否作为中继传输数据。如果能,则将ON的消息通过RSU分发给源车辆、BN和目的车辆。如果不能,则将SN的消息通过RSU分发给源车辆、SN和目的车辆。这样,需要发送数据的每个源节点均通过使用()计算当前和下一时隙邻居节点的权值,并更新源节点的邻居表。这样就无需为了更新邻居表而通过Hello包来交换信息,使吞吐量有很大的提升。SDN根据适应度函数选择ON和SNON是否可以通信ON作为最佳邻居SN作为最佳邻居YN图2 最佳邻居和次佳邻居选择流程为了
20、解决RSU计算和存储过载问题,SDN-NDHM引入SDN技术。如图3所示,SDN放置在与RSU距离5公里的位置。由于SDN计算能力较大,覆盖范围较广,所以可将较多的RSU与SDN控制器连接起来,让控制器计算所需的数据。在SDN-NDHM中,RSU起到转发的功能。BADCABDCSDN控制器RSURSUTruckTruck运动方向车图3 系统模型2.4 具体邻居发现方法和相关路由算法的描述SDN-NDHM算法工作流程如图4所示。车辆进入RSU通信范围,请求发送数据初始化RSU向SDN控制器注册自己的位置、吞吐量、通信范围和半径(rRSU)所有车辆向SDN控制器注册自己的位置、车速、方向、通信范围
21、和半径SDN用HMM预测车辆轨迹,得到t时刻车辆最终位置SDN求t时刻车辆与RSU的距离d1d1rRSU+rVYNNYd2rV+rON不构建拓扑断开拓扑发送数据给车辆计算参数构建拓扑求t时刻车辆与ON的距离d2选择ON,调取ON的通信半径rON图4 SDN-NDHM算法流程图3 性能评估在高速公路场景中应用SDN-NDHM算法,比较SDN-NDHM与DVA-GPSR19的性能,仿真实验在Matlab2020下进行。在MATLAB2020生成一段长技术广角 691km、宽30m的双向8车道高速公路车道模型,具体参数见表1。表1 参数设置表参数值仿真平台及版本Matlab2020仿真场景大小1km
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 隐马尔可夫 模型 高速公路 路由 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。