林海霞 甄增榮 白向偉

河北工程技術(shù)學(xué)院信息技術(shù)學(xué)院

?

車聯(lián)網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)的快速發(fā)現(xiàn)

林海霞 甄增榮 白向偉

河北工程技術(shù)學(xué)院信息技術(shù)學(xué)院

車聯(lián)網(wǎng)絡(luò)是智能交通的重要研究熱點(diǎn)，網(wǎng)絡(luò)節(jié)點(diǎn)鄰居間的快速發(fā)現(xiàn)成為影響車聯(lián)網(wǎng)性能的重要問題。針對車聯(lián)網(wǎng)中如何快速的確定移動節(jié)點(diǎn)鄰居的變化情況，提出了一種新的基于狀態(tài)空間向量的Hello預(yù)測模型（State Space Vecor Model ，SSVM）。每個移動節(jié)點(diǎn)存儲自身的狀態(tài)空間向量序列，包含有節(jié)點(diǎn)的位置、移動速度、加速度、所處網(wǎng)絡(luò)區(qū)域等信息，節(jié)點(diǎn)使用卡爾曼濾波器根據(jù)前一時隙的狀態(tài)向量預(yù)測出下一時隙的狀態(tài)，再將預(yù)測的狀態(tài)信息與實(shí)際的觀測值進(jìn)行比較，若誤差大于給定范圍，移動節(jié)點(diǎn)將廣播Hello包，告知其鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)收到Hello包后，會更新自己的鄰居列表，在下一時隙使用真實(shí)的觀測值進(jìn)行預(yù)測。仿真實(shí)驗(yàn)表明此模型能夠較準(zhǔn)確地探測出鄰居節(jié)點(diǎn)的到達(dá)和離開，并能夠適應(yīng)節(jié)點(diǎn)數(shù)目的變化和車輛行駛速度的變化。

車聯(lián)網(wǎng) 移動感知網(wǎng)絡(luò) 鄰居發(fā)現(xiàn)

1　引言

目前，國內(nèi)外對于車聯(lián)網(wǎng)絡(luò)節(jié)點(diǎn)的移動問題、路由算法問題等也都有所研究。但是車聯(lián)網(wǎng)絡(luò)還不同于普通的移動自組織網(wǎng)絡(luò)，VANET的網(wǎng)絡(luò)拓?fù)渥兓^快，節(jié)點(diǎn)間的連接時間受限，車輛移動速度快，分布節(jié)點(diǎn)較為密集。這些都會影響網(wǎng)絡(luò)節(jié)點(diǎn)間信息的傳遞，以致于傳統(tǒng)網(wǎng)絡(luò)中使用的傳輸協(xié)議不能很好地應(yīng)用于車聯(lián)網(wǎng)絡(luò)中。

如果要準(zhǔn)確而快速地預(yù)知車輛間的運(yùn)動，提前做好車輛間的協(xié)商和預(yù)警，就需要移動節(jié)點(diǎn)快速而準(zhǔn)確地把自身節(jié)點(diǎn)的位置信息、方向信息、速度信息等告知相鄰的鄰居節(jié)點(diǎn)，便于鄰居節(jié)點(diǎn)實(shí)時探測出周圍的環(huán)境，動態(tài)感知新鄰居的到達(dá)和就鄰居的離開，本文將從車輛間鄰居的快速發(fā)現(xiàn)算法入手，分析現(xiàn)有的算法，進(jìn)一步研究出更加適合VANET的快速鄰居發(fā)現(xiàn)算法。

本文借助原有的Hello協(xié)議，提出一種基于狀態(tài)空間向量的快速預(yù)測模型。該模型既考慮了發(fā)送Hello消息的時隙，同時考慮了節(jié)點(diǎn)所處的網(wǎng)絡(luò)區(qū)域。

2　相關(guān)工作

目前，國內(nèi)外已經(jīng)存在不少對車聯(lián)網(wǎng)中鄰居發(fā)現(xiàn)算法的研究，其中大多是從時間延遲、避免沖突等方面進(jìn)行分析的。利用監(jiān)聽、時隙劃分、廣播探測消息、網(wǎng)絡(luò)區(qū)域劃分等方法，缺乏對節(jié)點(diǎn)移動性的考慮，影響了鄰居發(fā)現(xiàn)算法的性能。

Cornejo等人在MAC層上實(shí)現(xiàn)了一個鄰居發(fā)現(xiàn)算法，將整個網(wǎng)絡(luò)區(qū)域劃分為多個靜態(tài)區(qū)域，每個節(jié)點(diǎn)都對靜態(tài)網(wǎng)絡(luò)區(qū)域信息進(jìn)行了存儲，當(dāng)某個移動節(jié)點(diǎn)進(jìn)入?yún)^(qū)域后，該節(jié)點(diǎn)可以與同區(qū)域的鄰居節(jié)點(diǎn)建立連接。當(dāng)移動節(jié)點(diǎn)離開這個區(qū)域時，與它建立連接的節(jié)點(diǎn)在確定其離開后將連接斷開。當(dāng)節(jié)點(diǎn)將要進(jìn)入一個新的網(wǎng)絡(luò)區(qū)域時，它會在適當(dāng)?shù)臅r間與其它節(jié)點(diǎn)交換通知消息。該協(xié)議是在假設(shè)每個節(jié)點(diǎn)的移動軌跡已知的情況下預(yù)測的，但實(shí)際情況每個節(jié)點(diǎn)的移動軌跡并不確定。

Fiore等人提出了一種輕量級分布式鄰居發(fā)現(xiàn)算法（SNPD），該算法僅僅是依賴鄰居間的消息交換，不預(yù)測可信節(jié)點(diǎn)，而是通過交換消息。節(jié)點(diǎn)之間相互廣播消息，記錄相關(guān)的時間信息，從而計(jì)算出鄰居節(jié)點(diǎn)的位置信息。但在SNPD中，節(jié)點(diǎn)間傳送的消息存在時間延遲，當(dāng)一個節(jié)點(diǎn)接收到某個鄰居節(jié)點(diǎn)發(fā)送過來的消息時，此鄰居節(jié)點(diǎn)的位置可能已經(jīng)發(fā)生了大的變化。

另外，有一種廣泛使用了的鄰居發(fā)現(xiàn)算法便是使用Hello協(xié)議。其中，開放式最短路徑優(yōu)先算法（OSPF）便是最早使用Hello協(xié)議的路由協(xié)議。它的思想是在固定的時間間隙內(nèi)，節(jié)點(diǎn)間通過交換Hello消息來探測鄰居間的變化情況。當(dāng)某節(jié)點(diǎn)接收到其鄰居節(jié)點(diǎn)發(fā)送過來的Hello包時，將會更新其路由表信息。當(dāng)某個節(jié)點(diǎn)在固定的時間間隔內(nèi)仍然沒有收到其鄰居節(jié)點(diǎn)發(fā)送的探測消息時，就會將鄰居刪除。

本文將從時隙的劃分，網(wǎng)絡(luò)區(qū)域的確定，節(jié)點(diǎn)的移動性等方面進(jìn)行綜合考慮，提出基于狀態(tài)空間向量的預(yù)測模型。

3　基于狀態(tài)空間向量的預(yù)測模型

本文提出一種基于狀態(tài)空間向量的Hello預(yù)測模型（State Space Vecor Model ，SSVM），此狀態(tài)空間向量預(yù)測模型借助于卡爾曼濾波器來實(shí)現(xiàn)預(yù)測。預(yù)測模型中時間域被劃分為相同的時隙，每個移動節(jié)點(diǎn)對下一狀態(tài)預(yù)測的時隙都相同。網(wǎng)絡(luò)中區(qū)域依靠路邊設(shè)施進(jìn)行劃分，每個區(qū)域擁有不同的網(wǎng)絡(luò)標(biāo)識符，每個移動節(jié)點(diǎn)將預(yù)存儲這些區(qū)域的標(biāo)識符。當(dāng)移動節(jié)點(diǎn)從一個區(qū)域進(jìn)入到另一個區(qū)域時，移動節(jié)點(diǎn)啟用新的區(qū)域標(biāo)識符。移動節(jié)點(diǎn)通過GPS來實(shí)時定位自己的位置信息，自己移動的方向性、行駛的速度及加速度。

3.1預(yù)測模型描述

當(dāng)移動節(jié)點(diǎn)加入到一個新的網(wǎng)絡(luò)區(qū)域之后，節(jié)點(diǎn)在每個時隙的開始都會記錄一個向量F（x ，Vx ，Vax ，y ，Vy ，Vay ，Q），向量記錄了當(dāng)前移動節(jié)點(diǎn)的位置信息、速度信息、加速度信息及所處區(qū)域的標(biāo)識符。這樣，每個移動節(jié)點(diǎn)都會記錄一個向量序列Fi（i=1，2，3，…）來清楚地描述移動節(jié)點(diǎn)在不同時隙的空間狀態(tài)變化情況。在某個時隙i，節(jié)點(diǎn)w使用卡爾曼濾波器來預(yù)測自己在下一時隙（i+1）時自身的狀態(tài)情況Fi+1，并且每個移動節(jié)點(diǎn)對自身鄰居表中所有鄰居進(jìn)行相同的預(yù)測。等到下一時隙（i+1）到來時，節(jié)點(diǎn)w將獲取到自身的真實(shí)狀態(tài)信息，節(jié)點(diǎn)會根據(jù)自己獲取的真實(shí)狀態(tài)信息和預(yù)測的狀態(tài)信息進(jìn)行比較，檢測出誤差。

3.2預(yù)測階段描述

在預(yù)測階段中，網(wǎng)絡(luò)中的每個移動節(jié)點(diǎn)w都會在每個時隙開始記錄自己的狀態(tài)信息Fi（i=1，2，3，…），這些不同時隙的狀態(tài)信息構(gòu)成一個時間序列F0，F(xiàn)1，F(xiàn)2，…Fi，…。使用一個Fi=（xi ，Vxi ，Vaxi ，yi ，Vyi ，Vayi ，Qi）T來表示節(jié)點(diǎn)的狀態(tài)信息，包括此節(jié)點(diǎn)的坐標(biāo)和移動速度等信息。其中，x和y分別表示節(jié)點(diǎn)在x軸和y軸方向上的坐標(biāo)，Vx ，Vy表示節(jié)點(diǎn)在x軸和y軸上的速度， Vax ， Vay分別表示節(jié)點(diǎn)沿x軸和y軸上的加速度，Q表示節(jié)點(diǎn)所在的區(qū)域。則每個節(jié)點(diǎn)計(jì)算下一時隙的坐標(biāo)信息如下：

將（1）式代入卡爾曼濾波器。

3.3更新階段描述

在此階段中，使用第i次觀測值Zi來將Fi更新為一個最優(yōu)值。移動節(jié)點(diǎn)的真實(shí)狀態(tài)信息是等到節(jié)點(diǎn)到達(dá)下一個時隙時取得的觀測值，因此，Zi是由x軸和y軸坐標(biāo)構(gòu)成的向量，而移動節(jié)點(diǎn)的狀態(tài)Fi是一個向量，這就要從Fi中提取出移動節(jié)點(diǎn)的位置坐標(biāo)。此階段，每個移動節(jié)點(diǎn)使用預(yù)測階段的數(shù)值，對相關(guān)參數(shù)進(jìn)行更新，同時計(jì)算出自身所處的最優(yōu)位置向量，將估算量保存在預(yù)測的模型中，一直等到下一個預(yù)測階段的使用。

3.4鄰居節(jié)點(diǎn)的離開描述

大多數(shù)現(xiàn)有的鄰居發(fā)現(xiàn)算法都是利用時間來判斷鄰居節(jié)點(diǎn)的離開，而SSVM中移動節(jié)點(diǎn)使用鄰居表中鄰居節(jié)點(diǎn)的位置信息來對鄰居的離開進(jìn)行判斷，從而提高了判斷的準(zhǔn)確性。

移動節(jié)點(diǎn)能夠在每個時隙計(jì)算出自己與鄰居節(jié)點(diǎn)的距離，能夠準(zhǔn)確地探測出節(jié)點(diǎn)的離開。比如計(jì)算出的距離如果大于給定的范圍s，節(jié)點(diǎn)就在鄰居表中將與此鄰居的鏈接刪除。

3.5預(yù)測誤差范圍描述

在SSVM中，為了保證預(yù)測位置的準(zhǔn)確性，定義一個誤差范圍D，令，同時，使用一個預(yù)定義的誤差閾值r來衡量預(yù)測誤差。一旦節(jié)點(diǎn)w獲取到自身在時隙i時刻的位置是xi，w將會廣播一個包含xi真實(shí)信息的Hello包。

而此方法的性能將隨變量r的變化而變化，r值偏小，會導(dǎo)致Hello包的發(fā)送頻率變高，浪費(fèi)資源；若r值偏大，則會導(dǎo)致預(yù)測模型的準(zhǔn)確率降低。為了使SSVM在不同的場景下都能達(dá)到較高的性能，采用仿真實(shí)驗(yàn)對r進(jìn)行了仿真預(yù)算，通過在不同環(huán)境下的仿真，實(shí)驗(yàn)確定將預(yù)測的誤差范圍設(shè)為1m，以便打到較為理想的預(yù)測性能。

4　結(jié)束語

本文提出了一種新型的基于狀態(tài)空間向量的Hello預(yù)測模型（SSVM）。每個移動節(jié)點(diǎn)存儲自身的狀態(tài)空間向量序列，向量包含有節(jié)點(diǎn)的位置、移動速度、加速度、所處網(wǎng)絡(luò)區(qū)域等信息，節(jié)點(diǎn)使用卡爾曼濾波器根據(jù)前一時隙的狀態(tài)向量預(yù)測出下一時隙的狀態(tài)，再將預(yù)測的狀態(tài)信息與實(shí)際的觀測值進(jìn)行比較，若誤差大于給定范圍的時候，移動節(jié)點(diǎn)將廣播Hello包告知其鄰居節(jié)點(diǎn)，其鄰居節(jié)點(diǎn)收到Hello包后，會更新自己的鄰居列表，在下一時隙使用真實(shí)的觀測值進(jìn)行預(yù)測。

［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-），女（漢族），河北唐山玉田人，副教授，碩士，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與通信技術(shù)。

河北工程技術(shù)學(xué)院自然科學(xué)基金項(xiàng)目（2016HG08）資助。