基于北斗定位的新型船舶自組網路由研究

沈晨

摘要：結合船舶自組網的特點， 利用中國北斗定位系統的定位功能， 提出了一種新的基于地理位置信息的路由優化算法。該算法利用北斗衛星獲取船舶位置和航行方向等信息，傳遞節點路由信息， 從而減少搜索盲目性， 提高路由效率。仿真結果表明：改進算法提高了路由收斂速度， 提升了數據傳輸成功率， 節約了能量開銷，挺升了網絡的性能。

關鍵詞：北斗；位置信息；航行方向；船舶自組網；Spray and Wait

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2016）28-0228-03

1 引言

船舶自組網是一種由移動的船舶自配置組成的多跳無線通訊網絡，是一種Ad-Hoc網絡運用到海洋上的自組網，其特殊網絡結構及配置方式使其具有傳統網絡所不具有的特性，如不需要預置基礎設施、網絡拓撲的動態性以及節點的資源受限等。這些特性使得傳統的網絡路由技術很難直接應用于移動自組織網絡中，因此需要研究適用于船舶自組網的路由算法。

目前，移動自組網多采用基于拓撲信息的路由算法，此類算法能夠構造優化路徑并保證數據傳輸可達性，然而此類算法直接或間接需要全局網絡的拓撲信息來進行路由選擇，由此造成的高路由開銷使其不適合應用于大規模網絡中?；谖恢眯畔⒌穆酚伤惴ㄓ捎趦H需要局部網絡位置信息進行路由選擇，在網絡規模變大時能仍保持較低開銷，因此具有高可擴展性的優點。近年來，網絡自定位算法、衛星定位系統的發展使節點獲取位置信息的精度不斷提高且成本不斷降低，利用節點位置信息來構造路徑的路由算法因其諸多優點和不再高昂的成本正日益受到重視。

Spray and Wait[7]協議具有傳輸延遲較小，接近于最優，有較好的適應性，有較好的可擴展性，無論網絡的規模大小，節點密度如何改變，都能保持較好的性能且該算法簡單便于執行等優點。然而該協議應用在船舶自組網中，由于船舶移動的速度相對較慢，節點稀疏，固定航道，相遇機會概率較低等，無法適應這種背景場景。

本文提出一種利用北斗衛星導航定位系統獲取船舶現有位置信息和航行方向，結合相應的算法對未來船舶位置進行預測，對Spray and Wait進行改進，增大船舶自組網網的連通性。最后通過獲取相關度量值，通過實驗驗證結果與目前比較流行機會網絡協議比較傳輸成功率，傳輸的延遲，路由開銷等性能提升來說明其優越性。

2 北斗定位與路由算法

北斗衛星導航定位系統是中國自主研制、自行建立的衛星導航定位系統。已經在軌使用的是由3顆衛星組成的北斗一號區域定位系統， 正在建設的是由30 顆衛星組成的北斗二號全球定位系統。與美國全球定位系統（GPS）、俄羅斯全球導航衛星系統（GLONASS ）以及歐洲正在發展的伽利略（GALILEO）衛星導航定位系統不同， 北斗一號采用雙星定位原理， 而且具有雙向數據通信功能， 因此其應用系統也是獨具特色的。

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

2.1基于船舶位置預測的算法判斷

2.1.1.距離判斷

通過攜帶消息的船舶A相遇另外一只船舶B，通過計算預測未來船舶位置，并且計算到未來目的船舶的之間距離，通過比較距離長短，決定消息轉不轉發，選擇距離較近的作為轉發中繼，在此處，距離長短作為判斷的依據。

例如兩坐標為A：{，，，}，B{，，，}，目的節點D，分別計算出兩個節點到目的節點的距離：

2.1.2航行方向判斷

通過北斗的定位功能，比較船舶的運行方向是否偏離目的船舶，來判斷決定消息是否轉發。在這里，由于海洋上船舶運動方向一般按照預先設定好的航道，運動方向，短時間內不會有大的改變，在預測下一刻時候，可以認為船舶的船速和運動方向沒有改變。

3 基于北斗定位的Spary-and-Wait路由協議改進

Spary and Wait算法分為兩個階段。Spray階段，源節點中的部分數據包被擴散到鄰居節點；Wait階段，若Spray階段沒有發現目標節點，包含數據包的節點以Direct Delivery 方式將數據包傳送到目標節點。

我們提出了一種基于船舶位置信息的B Spray and Wait 的新協議，主要對Spray and Wait協議在第二階段（wait階段）進行改進，通過北斗定位系統來獲取船舶的位置和航向，并預測未來t時間的位置，從而增加其與目的節點船只相遇的可能性，來達到一種高效傳輸的機會路由算法。

在Spray階段，當碰到一個節點時，決定多少份給該節點。最簡單的分發策略是一份一份地發，還有另一種分發策略是每次將一半復制給遇到的節點，當節點只有一份消息時，就退化成Direct Delivery了，則進入第二階段。關于Spray階段其他文獻有詳細的敘述，這里不再重復。

在wait階段，在Spray階段經過數據分組，每一個分組之后的副本，在網路環境中移動時并伴有一定的傳播范圍，如圖中的A和B兩只船舶在航道中不停地移動，并且不斷的記錄相關信息實時的更新，根據以往位置信息我們可以預測出未來船舶的位置，在此時根據未來船舶的位置與未來目的船舶的距離長短，即S1和S2，以及速度矢量與 和的夾角，相結合來判斷哪個點更有可能到達目的船舶節點，距離最短的和運動方向偏向目的船舶的方向為最佳中繼船舶，選擇該船舶進行傳輸（如圖3），該方案可以大大可以提高接觸目的節點相遇可能性，相比以前在wait階段的泛洪，有助于我們增大其傳輸成功率，減小平均延時，降低路由的開銷等。

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

4 實驗結果與分析

4.1 建立仿真場景

建立特定仿真場景，通過使用ONE軟件來模擬仿真，通過比較來說明性能的提升，本文評價自組網路由協議的優劣主要通過以下幾個指標來分析。由于自組網的主要目標是盡最大可能傳遞信息，所以傳輸的成功率（Delivery Ratio），即在一定的時間內成功到達目標節點數據包總數和源節點發出的需傳輸數據包總數之比，是最重要的指標。另外傳輸延時，即數據包從源節點到達目標節點所需的時間，是評價路由的另一重要指標。最后要考慮到資源消耗。

4.2仿真結果分析

本文通過比較Spary and Wait協議和改進過后的B Spray and Wait協議以及機會網絡常用路由MaxProp 三者之間的比較，來表現出三者之間的相關性，并且通過設置不同節點數（Number of Nodes），進而突出改進之后的顯著效果。

從下面仿真的結果來看，圖2顯示是三種路由協議傳輸成功率的一個比較， MaxProp比Spray and Wait高出10%，而B Spray and Wait比原來的MaxProp高15%，性能最優，這是由于新協議通過預測未來船舶可能存在的位置，在一定程度上增加向目的船舶數據包的傳遞的可能性。

在實驗中我們發現MaxProp路由開銷呈現的是一種較快增長形勢，消耗能量過多，而Spray and Wait和B Spray and Wait基本同一標準上保持較低的路由開銷狀態，新協議在遵循原協議的基礎上開銷稍有改善。

而圖3顯示隨著網絡中節點的增多時，MaxProp路由的組內直接傳送方式的平均傳送時延變化并不大，而Spray and Wait傳輸時延具有明顯降低，所需要的平均時間較少，而B Spray and wait通過預測來選擇中繼節點，縮短傳輸時間，從而占用更少網絡資源。

綜上所述，根據圖中的三種協議性能指標走向，新協議B Spray and Wait相比其他兩種協議，評價指標都有較大的提升，尤其表現在傳輸成功率顯著增高，而路由開銷和傳輸時延，也相應地有所降低，基本上達到了我們預期想要的效果。

5 總結

基于Spray and wait協議本身的一些特性，該協議比較適合應用于海洋互聯網，但是面對廣闊的海域，以及移動的船舶，由于自身的局限性，執行起來效率并不高，而本文引入了北斗導航定位系統，對Spray and wait協議進行了改進，建立一套船舶自組網路由機制B Spray and wait，可以有效地解決這一問題，提高船舶自組網的連通性。通過仿真實驗，驗證其改進過后的有效性，能提高傳輸成功率，減少延時，從而提高了船舶自組網的性能。

參考文獻

[1] 任智，黃勇，陳前斌.機會網絡路由協議[J].計算機應用，2010，30（3）：723-728.

[2] 曹得勝.機會網絡路由算法研究[D].廣西師范大學，2013.

[3] 楊奔全.基于位置預測的Ad hoc網絡路由協議研究[D].湖南大學，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在船舶自組網中的優化和性能研究[D].華南理工大學，2014.

[10] 王文濤，鄭芳，王奇楓，等.基于ONE 平臺的機會網絡路由協議仿真分析[J].中南名族大學學報，2013，9（3）：110-114.