沈晨

摘要：結(jié)合船舶自組網(wǎng)的特點(diǎn)， 利用中國(guó)北斗定位系統(tǒng)的定位功能， 提出了一種新的基于地理位置信息的路由優(yōu)化算法。該算法利用北斗衛(wèi)星獲取船舶位置和航行方向等信息，傳遞節(jié)點(diǎn)路由信息， 從而減少搜索盲目性， 提高路由效率。仿真結(jié)果表明：改進(jìn)算法提高了路由收斂速度， 提升了數(shù)據(jù)傳輸成功率， 節(jié)約了能量開(kāi)銷，挺升了網(wǎng)絡(luò)的性能。

關(guān)鍵詞：北斗；位置信息；航行方向；船舶自組網(wǎng)；Spray and Wait

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）28-0228-03

1 引言

船舶自組網(wǎng)是一種由移動(dòng)的船舶自配置組成的多跳無(wú)線通訊網(wǎng)絡(luò)，是一種Ad-Hoc網(wǎng)絡(luò)運(yùn)用到海洋上的自組網(wǎng)，其特殊網(wǎng)絡(luò)結(jié)構(gòu)及配置方式使其具有傳統(tǒng)網(wǎng)絡(luò)所不具有的特性，如不需要預(yù)置基礎(chǔ)設(shè)施、網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)性以及節(jié)點(diǎn)的資源受限等。這些特性使得傳統(tǒng)的網(wǎng)絡(luò)路由技術(shù)很難直接應(yīng)用于移動(dòng)自組織網(wǎng)絡(luò)中，因此需要研究適用于船舶自組網(wǎng)的路由算法。

目前，移動(dòng)自組網(wǎng)多采用基于拓?fù)湫畔⒌穆酚伤惴?，此類算法能夠?gòu)造優(yōu)化路徑并保證數(shù)據(jù)傳輸可達(dá)性，然而此類算法直接或間接需要全局網(wǎng)絡(luò)的拓?fù)湫畔?lái)進(jìn)行路由選擇，由此造成的高路由開(kāi)銷使其不適合應(yīng)用于大規(guī)模網(wǎng)絡(luò)中?；谖恢眯畔⒌穆酚伤惴ㄓ捎趦H需要局部網(wǎng)絡(luò)位置信息進(jìn)行路由選擇，在網(wǎng)絡(luò)規(guī)模變大時(shí)能仍保持較低開(kāi)銷，因此具有高可擴(kuò)展性的優(yōu)點(diǎn)。近年來(lái)，網(wǎng)絡(luò)自定位算法、衛(wèi)星定位系統(tǒng)的發(fā)展使節(jié)點(diǎn)獲取位置信息的精度不斷提高且成本不斷降低，利用節(jié)點(diǎn)位置信息來(lái)構(gòu)造路徑的路由算法因其諸多優(yōu)點(diǎn)和不再高昂的成本正日益受到重視。

Spray and Wait[7]協(xié)議具有傳輸延遲較小，接近于最優(yōu)，有較好的適應(yīng)性，有較好的可擴(kuò)展性，無(wú)論網(wǎng)絡(luò)的規(guī)模大小，節(jié)點(diǎn)密度如何改變，都能保持較好的性能且該算法簡(jiǎn)單便于執(zhí)行等優(yōu)點(diǎn)。然而該協(xié)議應(yīng)用在船舶自組網(wǎng)中，由于船舶移動(dòng)的速度相對(duì)較慢，節(jié)點(diǎn)稀疏，固定航道，相遇機(jī)會(huì)概率較低等，無(wú)法適應(yīng)這種背景場(chǎng)景。

本文提出一種利用北斗衛(wèi)星導(dǎo)航定位系統(tǒng)獲取船舶現(xiàn)有位置信息和航行方向，結(jié)合相應(yīng)的算法對(duì)未來(lái)船舶位置進(jìn)行預(yù)測(cè)，對(duì)Spray and Wait進(jìn)行改進(jìn)，增大船舶自組網(wǎng)網(wǎng)的連通性。最后通過(guò)獲取相關(guān)度量值，通過(guò)實(shí)驗(yàn)驗(yàn)證結(jié)果與目前比較流行機(jī)會(huì)網(wǎng)絡(luò)協(xié)議比較傳輸成功率，傳輸?shù)难舆t，路由開(kāi)銷等性能提升來(lái)說(shuō)明其優(yōu)越性。

2 北斗定位與路由算法

北斗衛(wèi)星導(dǎo)航定位系統(tǒng)是中國(guó)自主研制、自行建立的衛(wèi)星導(dǎo)航定位系統(tǒng)。已經(jīng)在軌使用的是由3顆衛(wèi)星組成的北斗一號(hào)區(qū)域定位系統(tǒng)， 正在建設(shè)的是由30 顆衛(wèi)星組成的北斗二號(hào)全球定位系統(tǒng)。與美國(guó)全球定位系統(tǒng)（GPS）、俄羅斯全球?qū)Ш叫l(wèi)星系統(tǒng)（GLONASS ）以及歐洲正在發(fā)展的伽利略（GALILEO）衛(wèi)星導(dǎo)航定位系統(tǒng)不同， 北斗一號(hào)采用雙星定位原理， 而且具有雙向數(shù)據(jù)通信功能， 因此其應(yīng)用系統(tǒng)也是獨(dú)具特色的。

在三維立體空間需要3 個(gè)條件才能唯一地確定一個(gè)點(diǎn)， 而北斗一號(hào)只有2 顆經(jīng)度上相距60°的地球靜止衛(wèi)星（另有一顆備份星）， 為了定位必須要第3個(gè)條件--利用已有的數(shù)字高程地圖， 通過(guò)用戶與地面指揮中心直接的雙向數(shù)據(jù)通信確定用戶至地心的距離（即第3 個(gè)條件）， 從而也就知道了用戶的位置， 再通過(guò)廣域差分標(biāo)校來(lái)提高定位精度。在有標(biāo)校地區(qū)的定位精度一般優(yōu)于10 ～ 20m .這樣的技術(shù)途徑有利也有弊：缺點(diǎn)是用戶終端要有接收和發(fā)送兩種功能， 體積相對(duì)大些；優(yōu)點(diǎn)是把導(dǎo)航定位、雙向數(shù)據(jù)通信和精密授時(shí)結(jié)合在一起， 不僅用戶知道自己所處的位置， 而且調(diào)度指揮中心也可以知道用戶位置， 雙向通信鏈路將作為大范圍網(wǎng)絡(luò)路由鏈路來(lái)使用。當(dāng)北斗二號(hào)系統(tǒng)完整建成后， 其全球定位與通信的特點(diǎn)將發(fā)揮更大作用。

2.1基于船舶位置預(yù)測(cè)的算法判斷

2.1.1.距離判斷

通過(guò)攜帶消息的船舶A相遇另外一只船舶B，通過(guò)計(jì)算預(yù)測(cè)未來(lái)船舶位置，并且計(jì)算到未來(lái)目的船舶的之間距離，通過(guò)比較距離長(zhǎng)短，決定消息轉(zhuǎn)不轉(zhuǎn)發(fā)，選擇距離較近的作為轉(zhuǎn)發(fā)中繼，在此處，距離長(zhǎng)短作為判斷的依據(jù)。

例如兩坐標(biāo)為A：{，，，}，B{，，，}，目的節(jié)點(diǎn)D，分別計(jì)算出兩個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離：

2.1.2航行方向判斷

通過(guò)北斗的定位功能，比較船舶的運(yùn)行方向是否偏離目的船舶，來(lái)判斷決定消息是否轉(zhuǎn)發(fā)。在這里，由于海洋上船舶運(yùn)動(dòng)方向一般按照預(yù)先設(shè)定好的航道，運(yùn)動(dòng)方向，短時(shí)間內(nèi)不會(huì)有大的改變，在預(yù)測(cè)下一刻時(shí)候，可以認(rèn)為船舶的船速和運(yùn)動(dòng)方向沒(méi)有改變。

3 基于北斗定位的Spary-and-Wait路由協(xié)議改進(jìn)

Spary and Wait算法分為兩個(gè)階段。Spray階段，源節(jié)點(diǎn)中的部分?jǐn)?shù)據(jù)包被擴(kuò)散到鄰居節(jié)點(diǎn)；Wait階段，若Spray階段沒(méi)有發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)，包含數(shù)據(jù)包的節(jié)點(diǎn)以Direct Delivery 方式將數(shù)據(jù)包傳送到目標(biāo)節(jié)點(diǎn)。

我們提出了一種基于船舶位置信息的B Spray and Wait 的新協(xié)議，主要對(duì)Spray and Wait協(xié)議在第二階段（wait階段）進(jìn)行改進(jìn)，通過(guò)北斗定位系統(tǒng)來(lái)獲取船舶的位置和航向，并預(yù)測(cè)未來(lái)t時(shí)間的位置，從而增加其與目的節(jié)點(diǎn)船只相遇的可能性，來(lái)達(dá)到一種高效傳輸?shù)臋C(jī)會(huì)路由算法。

在Spray階段，當(dāng)碰到一個(gè)節(jié)點(diǎn)時(shí)，決定多少份給該節(jié)點(diǎn)。最簡(jiǎn)單的分發(fā)策略是一份一份地發(fā)，還有另一種分發(fā)策略是每次將一半復(fù)制給遇到的節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)只有一份消息時(shí)，就退化成Direct Delivery了，則進(jìn)入第二階段。關(guān)于Spray階段其他文獻(xiàn)有詳細(xì)的敘述，這里不再重復(fù)。

在wait階段，在Spray階段經(jīng)過(guò)數(shù)據(jù)分組，每一個(gè)分組之后的副本，在網(wǎng)路環(huán)境中移動(dòng)時(shí)并伴有一定的傳播范圍，如圖中的A和B兩只船舶在航道中不停地移動(dòng)，并且不斷的記錄相關(guān)信息實(shí)時(shí)的更新，根據(jù)以往位置信息我們可以預(yù)測(cè)出未來(lái)船舶的位置，在此時(shí)根據(jù)未來(lái)船舶的位置與未來(lái)目的船舶的距離長(zhǎng)短，即S1和S2，以及速度矢量與 和的夾角，相結(jié)合來(lái)判斷哪個(gè)點(diǎn)更有可能到達(dá)目的船舶節(jié)點(diǎn)，距離最短的和運(yùn)動(dòng)方向偏向目的船舶的方向?yàn)樽罴阎欣^船舶，選擇該船舶進(jìn)行傳輸（如圖3），該方案可以大大可以提高接觸目的節(jié)點(diǎn)相遇可能性，相比以前在wait階段的泛洪，有助于我們?cè)龃笃鋫鬏敵晒β?，減小平均延時(shí)，降低路由的開(kāi)銷等。

綜上所述，改進(jìn)后的新協(xié)議，在Spray階段源節(jié)點(diǎn)以二發(fā)法的方式進(jìn)行數(shù)據(jù)分組，該算法的機(jī)制是源節(jié)點(diǎn)為每個(gè)在該節(jié)點(diǎn)起源的數(shù)據(jù)分組生成L個(gè)副本；若源節(jié)點(diǎn)A包含n個(gè)數(shù)據(jù)分組，當(dāng)其遇到新中繼節(jié)點(diǎn)B，則以n/2個(gè)數(shù)據(jù)分組轉(zhuǎn)發(fā)給B，自己同樣留有n/2分組，依次以同樣的方法分組，直到所有節(jié)點(diǎn)只有一個(gè)數(shù)據(jù)分組，則進(jìn)入到wait階段，攜帶消息節(jié)點(diǎn)（包括源節(jié)點(diǎn)）如果此時(shí)相遇到目的節(jié)點(diǎn)D，則直接轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)，如果沒(méi)有遇到目的節(jié)點(diǎn)D，通過(guò)位置預(yù)測(cè)方案，節(jié)點(diǎn)未來(lái)的位置，在基于與目的節(jié)點(diǎn)的距離長(zhǎng)短和節(jié)點(diǎn)運(yùn)行方向來(lái)判斷那個(gè)節(jié)點(diǎn)更有可能接觸到目的節(jié)點(diǎn)，從而決定轉(zhuǎn)發(fā)時(shí)機(jī)，增大了消息傳遞到目的節(jié)點(diǎn)可能性。

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

4.1 建立仿真場(chǎng)景

建立特定仿真場(chǎng)景，通過(guò)使用ONE軟件來(lái)模擬仿真，通過(guò)比較來(lái)說(shuō)明性能的提升，本文評(píng)價(jià)自組網(wǎng)路由協(xié)議的優(yōu)劣主要通過(guò)以下幾個(gè)指標(biāo)來(lái)分析。由于自組網(wǎng)的主要目標(biāo)是盡最大可能傳遞信息，所以傳輸?shù)某晒β剩―elivery Ratio），即在一定的時(shí)間內(nèi)成功到達(dá)目標(biāo)節(jié)點(diǎn)數(shù)據(jù)包總數(shù)和源節(jié)點(diǎn)發(fā)出的需傳輸數(shù)據(jù)包總數(shù)之比，是最重要的指標(biāo)。另外傳輸延時(shí)，即數(shù)據(jù)包從源節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)所需的時(shí)間，是評(píng)價(jià)路由的另一重要指標(biāo)。最后要考慮到資源消耗。

4.2仿真結(jié)果分析

本文通過(guò)比較Spary and Wait協(xié)議和改進(jìn)過(guò)后的B Spray and Wait協(xié)議以及機(jī)會(huì)網(wǎng)絡(luò)常用路由MaxProp 三者之間的比較，來(lái)表現(xiàn)出三者之間的相關(guān)性，并且通過(guò)設(shè)置不同節(jié)點(diǎn)數(shù)（Number of Nodes），進(jìn)而突出改進(jìn)之后的顯著效果。

從下面仿真的結(jié)果來(lái)看，圖2顯示是三種路由協(xié)議傳輸成功率的一個(gè)比較， MaxProp比Spray and Wait高出10%，而B(niǎo) Spray and Wait比原來(lái)的MaxProp高15%，性能最優(yōu)，這是由于新協(xié)議通過(guò)預(yù)測(cè)未來(lái)船舶可能存在的位置，在一定程度上增加向目的船舶數(shù)據(jù)包的傳遞的可能性。

在實(shí)驗(yàn)中我們發(fā)現(xiàn)MaxProp路由開(kāi)銷呈現(xiàn)的是一種較快增長(zhǎng)形勢(shì)，消耗能量過(guò)多，而Spray and Wait和B Spray and Wait基本同一標(biāo)準(zhǔn)上保持較低的路由開(kāi)銷狀態(tài)，新協(xié)議在遵循原協(xié)議的基礎(chǔ)上開(kāi)銷稍有改善。

而圖3顯示隨著網(wǎng)絡(luò)中節(jié)點(diǎn)的增多時(shí)，MaxProp路由的組內(nèi)直接傳送方式的平均傳送時(shí)延變化并不大，而Spray and Wait傳輸時(shí)延具有明顯降低，所需要的平均時(shí)間較少，而B(niǎo) Spray and wait通過(guò)預(yù)測(cè)來(lái)選擇中繼節(jié)點(diǎn)，縮短傳輸時(shí)間，從而占用更少網(wǎng)絡(luò)資源。

綜上所述，根據(jù)圖中的三種協(xié)議性能指標(biāo)走向，新協(xié)議B Spray and Wait相比其他兩種協(xié)議，評(píng)價(jià)指標(biāo)都有較大的提升，尤其表現(xiàn)在傳輸成功率顯著增高，而路由開(kāi)銷和傳輸時(shí)延，也相應(yīng)地有所降低，基本上達(dá)到了我們預(yù)期想要的效果。

5 總結(jié)

基于Spray and wait協(xié)議本身的一些特性，該協(xié)議比較適合應(yīng)用于海洋互聯(lián)網(wǎng)，但是面對(duì)廣闊的海域，以及移動(dòng)的船舶，由于自身的局限性，執(zhí)行起來(lái)效率并不高，而本文引入了北斗導(dǎo)航定位系統(tǒng)，對(duì)Spray and wait協(xié)議進(jìn)行了改進(jìn)，建立一套船舶自組網(wǎng)路由機(jī)制B Spray and wait，可以有效地解決這一問(wèn)題，提高船舶自組網(wǎng)的連通性。通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證其改進(jìn)過(guò)后的有效性，能提高傳輸成功率，減少延時(shí)，從而提高了船舶自組網(wǎng)的性能。

參考文獻(xiàn)

[1] 任智，黃勇，陳前斌.機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)應(yīng)用，2010，30（3）：723-728.

[2] 曹得勝.機(jī)會(huì)網(wǎng)絡(luò)路由算法研究[D].廣西師范大學(xué)，2013.

[3] 楊奔全.基于位置預(yù)測(cè)的Ad hoc網(wǎng)絡(luò)路由協(xié)議研究[D].湖南大學(xué)，2010.

[4] Byung-Gook Kim ； Jang-Won Lee； Opportunistic Resource Scheduling for OFDMA Networks with Network Coding at Relay Stations. Wireless Communications， IEEE Transactions on 2012，Page：210-221.

[5] Zipf A， Jost M， Location-Based Services， in Springer Handbook of Geographic Information[M]. Springer Berlin Heidelberg， 2012： 417-421.

[6] Gerla M， Kleinrock L. Vehicular Networks and the Future of Mobile Internet[J]. Computer Networks， 2011. 55（2）： 457-469.

[7] Alotaibi E， Mukherjee B. A Survey on Routing Algorithms for Wireless Ad-Hoc and Mesh Networks[J]. Computer Networks， 2012. 56（2）： 940-965.

[8] Chen M， Gonzalez S， Vasilakos A， et al. Body Area Networks： A Survey[J]. Mobile Networks and Applications， 2011.16（2）： 171-193.

[9] 文靜.MP-OLSR在船舶自組網(wǎng)中的優(yōu)化和性能研究[D].華南理工大學(xué)，2014.

[10] 王文濤，鄭芳，王奇楓，等.基于ONE 平臺(tái)的機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議仿真分析[J].中南名族大學(xué)學(xué)報(bào)，2013，9（3）：110-114.