基于位置信息的船舶編隊(duì)自組網(wǎng)路由協(xié)議設(shè)計(jì)?

（武漢第二船舶設(shè)計(jì)研究所 武漢 430205）

1 引言

隨著科技的不斷發(fā)展，海上船舶裝備越來(lái)越多，船舶編隊(duì)協(xié)同越來(lái)越多。當(dāng)前的船舶網(wǎng)絡(luò)并沒(méi)有構(gòu)成一個(gè)大型的自組網(wǎng)，船舶之間的信息交互和共享能力有待提升［1］，面對(duì)海上的突發(fā)情況，無(wú)法保障船舶編隊(duì)的通信質(zhì)量。而Ad-Hoc網(wǎng)絡(luò)具有無(wú)中心，獨(dú)立組網(wǎng)，自適應(yīng)更新路由的特點(diǎn)，可以提高船舶之間通信的可靠性［2］。不僅如此，在編隊(duì)執(zhí)行任務(wù)的過(guò)程中會(huì)發(fā)生不同隊(duì)形的切換，各節(jié)點(diǎn)之間的距離發(fā)生變化，通信鏈路可能會(huì)發(fā)生斷裂，保障編隊(duì)通信網(wǎng)絡(luò)的穩(wěn)定是至關(guān)重要的［3］。

目前的Ad-Hoc網(wǎng)絡(luò)采取的路由策略主要有兩種:反應(yīng)式和先應(yīng)式，反應(yīng)式是指當(dāng)源節(jié)點(diǎn)要向目的節(jié)點(diǎn)發(fā)送報(bào)文時(shí)，源節(jié)點(diǎn)在網(wǎng)絡(luò)中發(fā)起路由查找過(guò)程，找到相應(yīng)的路由后，才開始發(fā)送報(bào)文，代表協(xié)議有AODV［4］。該類協(xié)議通過(guò)發(fā)送時(shí)刻感知拓?fù)溥M(jìn)行轉(zhuǎn)發(fā)，不需要維持路由，但是尋找路由需要一定的時(shí)間，增加了報(bào)文傳輸時(shí)延。先應(yīng)式主要以O(shè)LSR［5］、DSDV［6］為主，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)周期性地通過(guò)拓?fù)涓兄?，維持并更新路由表。通過(guò)文獻(xiàn)［7］中的實(shí)驗(yàn)分析可以看出，反應(yīng)式路由協(xié)議分組投遞率較為高，但是因?yàn)檗D(zhuǎn)發(fā)之前需要計(jì)算路由表，因此時(shí)延較高，而先應(yīng)式路由協(xié)議因?yàn)槊總€(gè)節(jié)點(diǎn)都維持著路由表，因此傳輸時(shí)延較低，但是路由表存在滯后性，鏈路可能斷裂。為了控制報(bào)文的丟包率，目前有很多算法結(jié)合先應(yīng)式算法與網(wǎng)絡(luò)的特點(diǎn)設(shè)計(jì)鏈路狀態(tài)評(píng)估方式。比如，在文獻(xiàn)［8～9］中通過(guò)對(duì)節(jié)點(diǎn)剩余能量的評(píng)估，優(yōu)先選取剩余能量更高的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，保障網(wǎng)絡(luò)的能量均衡，從而減少了鏈路斷開。

除了上述兩種類型的協(xié)議，目前有人提出了基于強(qiáng)化學(xué)習(xí)的 Q-Routing［10～11］，這類協(xié)議與先應(yīng)式和反應(yīng)式的都不同，其路由表是逐漸收斂形成。該類算法通過(guò)定義節(jié)點(diǎn)之間轉(zhuǎn)發(fā)的反饋策略，不斷學(xué)習(xí)收斂路由表，通過(guò)強(qiáng)化學(xué)習(xí)使節(jié)點(diǎn)在動(dòng)態(tài)變化的拓?fù)浣Y(jié)構(gòu)下自適應(yīng)切換路由。但是對(duì)于不斷變化編隊(duì)網(wǎng)絡(luò)而言，該算法需要不斷學(xué)習(xí)，路由形成所需收斂時(shí)間過(guò)多，而在收斂期間，網(wǎng)絡(luò)的通信性能較差。

根據(jù)上述分析，為了保障編隊(duì)的實(shí)時(shí)通信，需要采取先應(yīng)式的路由策略，同時(shí)為了減少鏈路的斷開，需要根據(jù)編隊(duì)的網(wǎng)絡(luò)特點(diǎn)，量化鏈路狀態(tài)，并且在此基礎(chǔ)上建立最優(yōu)鏈路狀態(tài)拓?fù)涓兄Ｐ?。因此本文提出了一種基于位置信息的船舶編隊(duì)自組網(wǎng)路由協(xié)議（Location-based Routing for Ship Formation，LRSF）。首先節(jié)點(diǎn)之間交互位置信息，通過(guò)位置信息的變化預(yù)測(cè)鏈路狀態(tài)，定義鏈路質(zhì)量，并在此基礎(chǔ)上建立最優(yōu)鏈路拓?fù)涓兄Ｐ?，保障?jié)點(diǎn)感知全網(wǎng)拓?fù)渥兓?，最后進(jìn)行路由計(jì)算，及時(shí)地切換路由，減少鏈路斷開的次數(shù)，保障編隊(duì)通信質(zhì)量。

2 船舶編隊(duì)自組網(wǎng)概述

當(dāng)前海上船舶設(shè)備數(shù)量和種類越來(lái)越多，海上任務(wù)主要是以船舶編隊(duì)的方式執(zhí)行，船舶編隊(duì)頻繁地變化，難以保障船舶之間通信的可靠性。為了提升船舶編隊(duì)的通信性能，可以將編隊(duì)構(gòu)建成一個(gè)移動(dòng)自組網(wǎng)。當(dāng)前的船舶編隊(duì)協(xié)同面臨一個(gè)顯著的問(wèn)題——如何降低隊(duì)形變換的過(guò)程中報(bào)文的丟失率，如圖1所示。

以圖1所示的場(chǎng)景舉例，編隊(duì)從人字形切換到一字形編隊(duì)，初始時(shí)，B與D之間可以直接一跳傳輸進(jìn)行通信，隨著編隊(duì)的變換，B與D同時(shí)繞著C進(jìn)行轉(zhuǎn)動(dòng)，直至呈現(xiàn)一字形，在此過(guò)程中，B與D的距離不斷地增大直至無(wú)法一跳直接通信，需要由C進(jìn)行轉(zhuǎn)發(fā)進(jìn)行轉(zhuǎn)發(fā)。然而當(dāng)前存在的移動(dòng)自組網(wǎng)協(xié)議，并不能很好地感知節(jié)點(diǎn)之間的距離變化，不能及時(shí)地進(jìn)行路由切換，導(dǎo)致B與D之間的通信報(bào)文發(fā)生丟失。

圖1 人字形編隊(duì)切換至一字形編隊(duì)

為了解決上述問(wèn)題，節(jié)點(diǎn)需要感知到節(jié)點(diǎn)之間相對(duì)位置信息的變化并及時(shí)切換路由。因此本文考慮通過(guò)節(jié)點(diǎn)之間的相對(duì)移動(dòng)評(píng)估鏈路質(zhì)量，使節(jié)點(diǎn)感知周圍鄰居的變化趨勢(shì)，同時(shí)結(jié)合節(jié)點(diǎn)之間的運(yùn)動(dòng)趨勢(shì)建立拓?fù)涓兄Ｐ停Ｕ瞎?jié)點(diǎn)感知全網(wǎng)的變化趨勢(shì)，最后結(jié)合全局拓?fù)溥M(jìn)行路由計(jì)算。

3 基于位置信息的船舶編隊(duì)自組網(wǎng)路由協(xié)議設(shè)計(jì)

3.1 基于位置信息的鏈路狀態(tài)量化

船舶編隊(duì)在隊(duì)形變換時(shí)，節(jié)點(diǎn)之間的相對(duì)運(yùn)動(dòng)趨勢(shì)不一樣，相應(yīng)的通信鏈路狀態(tài)也不一樣，為了能夠感知鏈路狀態(tài)的變化，需要結(jié)合節(jié)點(diǎn)之間的位置信息變化對(duì)鏈路狀態(tài)進(jìn)行評(píng)估。在OLSR中并沒(méi)有考慮鏈路質(zhì)量差異，該算法默認(rèn)每一跳鏈路具有相同的鏈路質(zhì)量，并不符合船舶編隊(duì)自組網(wǎng)的特點(diǎn)。在文獻(xiàn)［12］中提出了基于期望傳輸次數(shù)的鏈路質(zhì)量指標(biāo)，如式（1）所示。

其中R表示兩點(diǎn)之間的通信鏈路，LQ(R)表示R的鏈路質(zhì)量，η表示R中的某一跳鏈路，ETX代表報(bào)文從源節(jié)點(diǎn)成功發(fā)送到目的節(jié)點(diǎn)的期望傳輸次數(shù)，φ(η)代表報(bào)文經(jīng)過(guò)η的接收成功率，ρ(η)代表反向接收成功率，也即是相應(yīng)的ACK報(bào)文的接收成功率。ETX越小，則鏈路傳輸效率越高。對(duì)于拓?fù)渥兓l率低的移動(dòng)自組網(wǎng)而言，ETX可以較好地反映鏈路狀態(tài)。但是船舶編隊(duì)中，節(jié)點(diǎn)之間的拓?fù)渥兓^為頻繁，節(jié)點(diǎn)之間會(huì)因?yàn)橄鄬?duì)移動(dòng)而導(dǎo)致鏈路突然斷開，僅僅靠ETX無(wú)法真實(shí)地反映相對(duì)移動(dòng)節(jié)點(diǎn)之間的鏈路狀態(tài)。

為了解決這個(gè)問(wèn)題，需要分析節(jié)點(diǎn)之間的相對(duì)位置變化和鏈路狀態(tài)的聯(lián)系。船舶編隊(duì)隊(duì)形變化導(dǎo)致了鏈路狀態(tài)發(fā)生變化，而節(jié)點(diǎn)之間的相對(duì)加速度是隊(duì)形開始變化的一個(gè)重要指標(biāo)，感知節(jié)點(diǎn)之間的相對(duì)加速度可以預(yù)測(cè)鏈路狀態(tài)。因此本文結(jié)合節(jié)點(diǎn)之間的相對(duì)加速度建立鏈路質(zhì)量預(yù)測(cè)鏈路狀態(tài)，鏈路質(zhì)量如式（2）所示。

其中LQ(η)表示η的鏈路質(zhì)量，節(jié)點(diǎn)i與j為一跳鏈路η的相鄰節(jié)點(diǎn)，ai,j是節(jié)點(diǎn)i，j之間的相對(duì)加速度，μ是非負(fù)經(jīng)驗(yàn)參數(shù)。在鏈路擁有相同的ETX情況下，節(jié)點(diǎn)之間的相對(duì)加速度越大，拓?fù)渥兓絼×遥溌乏歉菀讛嚅_，因此在路由計(jì)算中，源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間選擇LQ(R)最小的鏈路作為通信鏈路。

相對(duì)加速度ai,j如式（3）所示:

其中vi,j(t2)為節(jié)點(diǎn)i和j在t2時(shí)刻的相對(duì)速度，vi,j(t1)為節(jié)點(diǎn)i和j在t1時(shí)刻的相對(duì)速度。vi,j(t2)和vi,j(t1)分別如式（4）、式（5）所示。

其中(xi(t),yi(t),zi(t))代表t時(shí)刻i節(jié)點(diǎn)的位置坐標(biāo)，(xj(t),yj(t),zj(t))代表t時(shí)刻j節(jié)點(diǎn)的位置坐標(biāo)。

3.2 最優(yōu)鏈路狀態(tài)拓?fù)涓兄Ｐ?/h3>

當(dāng)前的船舶編隊(duì)可以利用GPS或者北斗衛(wèi)星獲取實(shí)時(shí)位置信息，采取上述鏈路質(zhì)量評(píng)估方式，節(jié)點(diǎn)只需知曉鄰居節(jié)點(diǎn)之間的相對(duì)位置信息的變化，便可以預(yù)測(cè)鏈路狀態(tài)變化。但是對(duì)于船舶編隊(duì)移動(dòng)自組網(wǎng)而言，節(jié)點(diǎn)本身的通信范圍有限，并不能感知全網(wǎng)的所有鏈路變化，需要結(jié)合拓?fù)涓兄Ｐ瓦M(jìn)行全網(wǎng)拓?fù)涓兄?，才可以選擇最小鏈路質(zhì)量的鏈路進(jìn)行路由。

目前OLSR采用最少中繼節(jié)點(diǎn)拓?fù)涓兄Ｐ停?jié)點(diǎn)在鄰居集合中選取最少的能夠覆蓋兩跳鄰居的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，構(gòu)成中繼節(jié)點(diǎn)集合，一跳以外的節(jié)點(diǎn)可以通過(guò)中繼節(jié)點(diǎn)與該節(jié)點(diǎn)進(jìn)行通信，為了減少控制開銷，只將節(jié)點(diǎn)與中繼節(jié)點(diǎn)集合的鏈路加入拓?fù)浣Y(jié)構(gòu)。因?yàn)镺LSR無(wú)法感知相對(duì)移動(dòng)節(jié)點(diǎn)之間的鏈路狀態(tài)的差異，選取的中繼節(jié)點(diǎn)的不一定最優(yōu)，形成的拓?fù)浣Y(jié)構(gòu)并非最優(yōu)，以圖2所示菱形拓?fù)鋱?chǎng)景為例，其中A節(jié)點(diǎn)兩端來(lái)回勻速移動(dòng)，S、B、D靜止，S為源節(jié)點(diǎn)，D為目的節(jié)點(diǎn)，在OLSR算法下，D一旦選擇A加入中繼集合，將拓?fù)銩->D發(fā)送到網(wǎng)絡(luò)中洪泛，S只能感知到A->D，無(wú)法感知B->D拓?fù)洌荒苌蒘->A->D的路由。

圖2 菱形拓?fù)鋱?chǎng)景

為了保證節(jié)點(diǎn)盡可能按照最優(yōu)鏈路進(jìn)行轉(zhuǎn)發(fā)，本文建立最優(yōu)鏈路狀態(tài)拓?fù)涓兄Ｐ汀Ｔ谠撃Ｐ椭?，?jié)點(diǎn)優(yōu)先鏈路質(zhì)量最小的鄰居節(jié)點(diǎn)加入中繼節(jié)點(diǎn)集合，直至通過(guò)該集合可以覆蓋所有的兩跳鄰居節(jié)點(diǎn)。在圖2所示的場(chǎng)景下，D優(yōu)先選擇B加入中繼節(jié)點(diǎn)集合，S感知到B->D的拓?fù)洌蒘->B->D的路由。與OLSR的拓?fù)涓兄Ｐ拖啾龋顑?yōu)鏈路拓?fù)涓兄Ｐ涂梢员ＷC最優(yōu)的中繼節(jié)點(diǎn)的鏈路參與全網(wǎng)的路由計(jì)算，提升網(wǎng)絡(luò)通信的穩(wěn)定性。

4 仿真實(shí)驗(yàn)及結(jié)果分析

為了評(píng)估LRSF算法的性能，在QualNet上模擬船舶編隊(duì)變換的場(chǎng)景，比較LRSF和OLSR的網(wǎng)絡(luò)性能指標(biāo)。實(shí)驗(yàn)場(chǎng)景如圖3所示，開始在QualNet上布置了8個(gè)節(jié)點(diǎn)組成人字形編隊(duì)，隨后經(jīng)過(guò)時(shí)間t1切換成一字形，經(jīng)過(guò)時(shí)間t2切換成菱形，為了研究算法在不同的拓?fù)渥兓炻龍?chǎng)景下的性能，設(shè)定多組t1和t2進(jìn)行多次實(shí)驗(yàn)（因?yàn)榇熬庩?duì)從一個(gè)隊(duì)形切換到另一個(gè)隊(duì)形，拓?fù)涞某跏紶顟B(tài)和結(jié)束狀態(tài)一致，變化的時(shí)間越短，拓?fù)渥兓娇欤?，本次?shí)驗(yàn)做了五組不同變換時(shí)間的對(duì)比實(shí)驗(yàn)，船舶編隊(duì)切換時(shí)間參數(shù)配置如表1所示。

表1 船舶編隊(duì)切換時(shí)間（s）配置

為了評(píng)估網(wǎng)絡(luò)的性能，本文選取如下的網(wǎng)絡(luò)性能指標(biāo)。

1）平均端到端時(shí)延，如式（7）所示，指的是數(shù)據(jù)包從源節(jié)點(diǎn)發(fā)送到目的節(jié)點(diǎn)接收所需的時(shí)間，反映了路由協(xié)議的有效性。

其中表示平均端到端時(shí)延，Tr代表接收到數(shù)據(jù)包的時(shí)間，Ts代表發(fā)送數(shù)據(jù)包的時(shí)間，N表示發(fā)送數(shù)據(jù)包的個(gè)數(shù)。

圖3 船舶編隊(duì)切換場(chǎng)景

2）分組投遞率，如式（8）所示，定義為到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)包的個(gè)數(shù)與源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包的個(gè)數(shù)的比值。投遞率反映路由的可靠性，投遞率越大，丟失分?jǐn)?shù)據(jù)包越少，通信越可靠。

其中Pd指分組投遞率，Pr表示目的節(jié)點(diǎn)接收數(shù)據(jù)包的個(gè)數(shù)，Ps表示源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包的個(gè)數(shù)。

為了保證實(shí)驗(yàn)結(jié)果的可靠性，隨機(jī)選取源節(jié)點(diǎn)-目的節(jié)點(diǎn)并且設(shè)置CBR數(shù)據(jù)流，進(jìn)行多次實(shí)驗(yàn)，取多次實(shí)驗(yàn)的平均結(jié)果作為網(wǎng)絡(luò)性能指標(biāo)的評(píng)估值。

本次實(shí)驗(yàn)中，隨著編隊(duì)切換的時(shí)間增加，兩種算法的分組投遞率如圖4所示。隨著編隊(duì)變換所用時(shí)間的減少，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)劇烈程度增加，OLSR和LRSF的分組投遞率都有一定程度的減少，但是LRSF的分組投遞率明顯高于OLSR，而且在80s以上的編隊(duì)變化時(shí)間范圍內(nèi)，LRSF的分組投遞率都在90%左右，而OLSR只有大約70%，LRSF此時(shí)的分組投遞率遠(yuǎn)高于OLSR。

圖4 分組投遞率比較

隨著編隊(duì)切換的時(shí)間增加，兩種算法的平均端到端時(shí)延如圖5所示。在編隊(duì)切換時(shí)間60s以上的范圍內(nèi)，OLSR的平均端到端時(shí)延一直都是高于LRSF，但是隨著編隊(duì)切換時(shí)間的減少，OLSR的時(shí)延開始快速下降，而LRSF可以保持平緩，主要是LRSF能夠保持一個(gè)良好的分組投遞率，而OLSR在此期間分組投遞率下降較多，導(dǎo)致參與時(shí)延統(tǒng)計(jì)的報(bào)文數(shù)量減少，從而統(tǒng)計(jì)的平均端到端時(shí)延減少。在編隊(duì)切換時(shí)間60s以內(nèi)的范圍，OLSR的平均端到端時(shí)延下降至LRSF以下，而LRSF此時(shí)的平均端到端時(shí)延也存在一定程度的下降，主要原因是此時(shí)的編隊(duì)拓?fù)浣Y(jié)構(gòu)變化較快，LRSF的分組投遞率也存在一定程度的降低。

圖5 平均端到端時(shí)延比較

綜上，在船舶編隊(duì)進(jìn)行簡(jiǎn)單的隊(duì)形變化時(shí)，本文設(shè)計(jì)的LRSF算法能夠保持一個(gè)較高的分組投遞率，并且端到端時(shí)延有所下降，相較于OLSR具有一定的優(yōu)越性。

5 結(jié)語(yǔ)

本文針對(duì)海上船舶編隊(duì)提出了LRSF路由算法，通過(guò)實(shí)驗(yàn)結(jié)果可以看出在面向動(dòng)態(tài)拓?fù)渥兓膱?chǎng)景下，LRSF比OLSR具有更高的報(bào)文投遞率，網(wǎng)絡(luò)通信更為可靠，盡管犧牲了些許時(shí)延，但是并未影響到網(wǎng)絡(luò)通信的及時(shí)性，相較于傳統(tǒng)的移動(dòng)自組網(wǎng)協(xié)議具有一定的優(yōu)越性。盡管如此，本文研究的是簡(jiǎn)單場(chǎng)景下船舶編隊(duì)變換，拓?fù)渥兓^為單一，一旦發(fā)生網(wǎng)絡(luò)拓?fù)鋭×一蚴遣灰?guī)則的變化，LRSF算法也不能保持良好的分組投遞率，丟包較多，無(wú)法保持良好的通信性能，因此如何應(yīng)用拓?fù)淇刂茰p少拓?fù)渥兓?，并與路由算法相結(jié)合需要后續(xù)進(jìn)行深入的研究。