车联网络中邻居节点的快速发现

林海霞 甄增荣 白向伟

河北工程技术学院信息技术学院



车联网络中邻居节点的快速发现

林海霞 甄增荣 白向伟

河北工程技术学院信息技术学院

车联网络是智能交通的重要研究热点，网络节点邻居间的快速发现成为影响车联网性能的重要问题。针对车联网中如何快速的确定移动节点邻居的变化情况，提出了一种新的基于状态空间向量的Hello预测模型（State Space Vecor Model ，SSVM）。每个移动节点存储自身的状态空间向量序列，包含有节点的位置、移动速度、加速度、所处网络区域等信息，节点使用卡尔曼滤波器根据前一时隙的状态向量预测出下一时隙的状态，再将预测的状态信息与实际的观测值进行比较，若误差大于给定范围，移动节点将广播Hello包，告知其邻居节点，邻居节点收到Hello包后，会更新自己的邻居列表，在下一时隙使用真实的观测值进行预测。仿真实验表明此模型能够较准确地探测出邻居节点的到达和离开，并能够适应节点数目的变化和车辆行驶速度的变化。

车联网 移动感知网络 邻居发现

1　引言

目前，国内外对于车联网络节点的移动问题、路由算法问题等也都有所研究。但是车联网络还不同于普通的移动自组织网络，VANET的网络拓扑变化较快，节点间的连接时间受限，车辆移动速度快，分布节点较为密集。这些都会影响网络节点间信息的传递，以致于传统网络中使用的传输协议不能很好地应用于车联网络中。

如果要准确而快速地预知车辆间的运动，提前做好车辆间的协商和预警，就需要移动节点快速而准确地把自身节点的位置信息、方向信息、速度信息等告知相邻的邻居节点，便于邻居节点实时探测出周围的环境，动态感知新邻居的到达和就邻居的离开，本文将从车辆间邻居的快速发现算法入手，分析现有的算法，进一步研究出更加适合VANET的快速邻居发现算法。

本文借助原有的Hello协议，提出一种基于状态空间向量的快速预测模型。该模型既考虑了发送Hello消息的时隙，同时考虑了节点所处的网络区域。

2　相关工作

目前，国内外已经存在不少对车联网中邻居发现算法的研究，其中大多是从时间延迟、避免冲突等方面进行分析的。利用监听、时隙划分、广播探测消息、网络区域划分等方法，缺乏对节点移动性的考虑，影响了邻居发现算法的性能。

Cornejo等人在MAC层上实现了一个邻居发现算法，将整个网络区域划分为多个静态区域，每个节点都对静态网络区域信息进行了存储，当某个移动节点进入区域后，该节点可以与同区域的邻居节点建立连接。当移动节点离开这个区域时，与它建立连接的节点在确定其离开后将连接断开。当节点将要进入一个新的网络区域时，它会在适当的时间与其它节点交换通知消息。该协议是在假设每个节点的移动轨迹已知的情况下预测的，但实际情况每个节点的移动轨迹并不确定。

Fiore等人提出了一种轻量级分布式邻居发现算法（SNPD），该算法仅仅是依赖邻居间的消息交换，不预测可信节点，而是通过交换消息。节点之间相互广播消息，记录相关的时间信息，从而计算出邻居节点的位置信息。但在SNPD中，节点间传送的消息存在时间延迟，当一个节点接收到某个邻居节点发送过来的消息时，此邻居节点的位置可能已经发生了大的变化。

另外，有一种广泛使用了的邻居发现算法便是使用Hello协议。其中，开放式最短路径优先算法（OSPF）便是最早使用Hello协议的路由协议。它的思想是在固定的时间间隙内，节点间通过交换Hello消息来探测邻居间的变化情况。当某节点接收到其邻居节点发送过来的Hello包时，将会更新其路由表信息。当某个节点在固定的时间间隔内仍然没有收到其邻居节点发送的探测消息时，就会将邻居删除。

本文将从时隙的划分，网络区域的确定，节点的移动性等方面进行综合考虑，提出基于状态空间向量的预测模型。

3　基于状态空间向量的预测模型

本文提出一种基于状态空间向量的Hello预测模型（State Space Vecor Model ，SSVM），此状态空间向量预测模型借助于卡尔曼滤波器来实现预测。预测模型中时间域被划分为相同的时隙，每个移动节点对下一状态预测的时隙都相同。网络中区域依靠路边设施进行划分，每个区域拥有不同的网络标识符，每个移动节点将预存储这些区域的标识符。当移动节点从一个区域进入到另一个区域时，移动节点启用新的区域标识符。移动节点通过GPS来实时定位自己的位置信息，自己移动的方向性、行驶的速度及加速度。

3.1预测模型描述

当移动节点加入到一个新的网络区域之后，节点在每个时隙的开始都会记录一个向量F（x ，Vx ，Vax ，y ，Vy ，Vay ，Q），向量记录了当前移动节点的位置信息、速度信息、加速度信息及所处区域的标识符。这样，每个移动节点都会记录一个向量序列Fi（i=1，2，3，…）来清楚地描述移动节点在不同时隙的空间状态变化情况。在某个时隙i，节点w使用卡尔曼滤波器来预测自己在下一时隙（i+1）时自身的状态情况Fi+1，并且每个移动节点对自身邻居表中所有邻居进行相同的预测。等到下一时隙（i+1）到来时，节点w将获取到自身的真实状态信息，节点会根据自己获取的真实状态信息和预测的状态信息进行比较，检测出误差。

3.2预测阶段描述

在预测阶段中，网络中的每个移动节点w都会在每个时隙开始记录自己的状态信息Fi（i=1，2，3，…），这些不同时隙的状态信息构成一个时间序列F0，F1，F2，…Fi，…。使用一个Fi=（xi ，Vxi ，Vaxi ，yi ，Vyi ，Vayi ，Qi）T来表示节点的状态信息，包括此节点的坐标和移动速度等信息。其中，x和y分别表示节点在x轴和y轴方向上的坐标，Vx ，Vy表示节点在x轴和y轴上的速度， Vax ， Vay分别表示节点沿x轴和y轴上的加速度，Q表示节点所在的区域。则每个节点计算下一时隙的坐标信息如下：

将（1）式代入卡尔曼滤波器。

3.3更新阶段描述

在此阶段中，使用第i次观测值Zi来将Fi更新为一个最优值。移动节点的真实状态信息是等到节点到达下一个时隙时取得的观测值，因此，Zi是由x轴和y轴坐标构成的向量，而移动节点的状态Fi是一个向量，这就要从Fi中提取出移动节点的位置坐标。此阶段，每个移动节点使用预测阶段的数值，对相关参数进行更新，同时计算出自身所处的最优位置向量，将估算量保存在预测的模型中，一直等到下一个预测阶段的使用。

3.4邻居节点的离开描述

大多数现有的邻居发现算法都是利用时间来判断邻居节点的离开，而SSVM中移动节点使用邻居表中邻居节点的位置信息来对邻居的离开进行判断，从而提高了判断的准确性。

移动节点能够在每个时隙计算出自己与邻居节点的距离，能够准确地探测出节点的离开。比如计算出的距离如果大于给定的范围s，节点就在邻居表中将与此邻居的链接删除。

3.5预测误差范围描述

在SSVM中，为了保证预测位置的准确性，定义一个误差范围D，令，同时，使用一个预定义的误差阈值r来衡量预测误差。一旦节点w获取到自身在时隙i时刻的位置是xi，w将会广播一个包含xi真实信息的Hello包。

而此方法的性能将随变量r的变化而变化，r值偏小，会导致Hello包的发送频率变高，浪费资源；若r值偏大，则会导致预测模型的准确率降低。为了使SSVM在不同的场景下都能达到较高的性能，采用仿真实验对r进行了仿真预算，通过在不同环境下的仿真，实验确定将预测的误差范围设为1m，以便打到较为理想的预测性能。

4　结束语

本文提出了一种新型的基于状态空间向量的Hello预测模型（SSVM）。每个移动节点存储自身的状态空间向量序列，向量包含有节点的位置、移动速度、加速度、所处网络区域等信息，节点使用卡尔曼滤波器根据前一时隙的状态向量预测出下一时隙的状态，再将预测的状态信息与实际的观测值进行比较，若误差大于给定范围的时候，移动节点将广播Hello包告知其邻居节点，其邻居节点收到Hello包后，会更新自己的邻居列表，在下一时隙使用真实的观测值进行预测。

［1］Cornejo A Lynch N Neighbor discovery in moile Ad hoc networks using an abstract MAC Layer［C］//Proc of the 47th Annual Allerton Conference on Communication，Control，and Computing.2009：1461-1470

［2］Fiore M，Casetti C，Cshiasserini C，et al，Secure neighbor postion discovery in vehicular networks［C］// Proc of the 10th IFIP Annual Mediterranean Ad hoc Networking Workshop.2011：70-78

林海霞（1978-），女（汉族），河北唐山玉田人，副教授，硕士，主要研究领域为计算机网络与通信技术。

河北工程技术学院自然科学基金项目（2016HG08）资助。