戰場環境下基于節點移動性的DTN路由算法*

和 何，李琳琳，路云飛

（火箭軍工程大學，西安 710025）

0 引言

容遲容斷網絡（DTN）是一種典型的在任意時刻任意兩個網絡節點間缺乏可靠路徑的特殊網絡。不同于傳統通信網絡，DTN使用存儲-攜帶-轉發機制[1]，能夠有效地解決網絡拓撲結構動態變化、通信鏈路經常中斷、間歇性連接、傳送延遲長、資源有限等問題[2]。因此，近年來針對DTN的路由算法已經成為研究網絡通信的一大熱點。

在DTN中有3種經典的路由算法：Epidemic[3]、Spray and Wait[4]、PROPHET[5]。在此基礎上，近年來出現了很多新的路由算法，如：文獻[6]通過將節點接觸信息和消息特性相結合，提出了基于路由協議的期望相遇算法，利用同一個社區內節點間高接觸頻率提出了社區意識路由算法，仿真結果表明，兩種路由算法相比于3種經典路由算法，其消息投遞率、平均時延和有效吞吐量得到了較大提升。文獻[7]中提出了基于用戶中心性和興趣度的路由算法，同時多跳中心性概念的提出使得中繼節點有更多的機會傳送消息，因此，有效地提高了路由算法的消息投遞率。文獻[8]提出了交際度的概念，即為節點經常相遇的其他節點的總量。節點交際度越大，說明該節點有更高的可能性傳送消息到其他節點，因此，路由策略即為選擇交際度最大的節點作為中繼節點。近年來對于DTN的其他研究進展還包括調度車載式 DTN[9]，多播路由方案[10]，ad-hoc網絡的綠色技術假設[11]等。

1 基于節點移動性的路由算法

一個作戰單元在遂行作戰任務時，所面臨的情況是稍縱即逝、難以預知的，加之通信資源稀缺，作戰節點之間很難做到實時通信，即不存在穩定可靠的端到端通信鏈路，即認為在某些戰場環境下通信網絡屬于DTN網絡[12]。

戰場環境下節點類型主要包括：武器平臺、各級指揮所、作戰單兵、通信節點、便攜式移動終端等。基于節點的運動水平指數和歷史接觸信息，把消息傳送給在每個作戰單元內具有最大運動水平指數的節點，其次通過這些節點進行作戰單元間以及作戰單元與上級指揮所間的通信。

MRA算法的主要創新點體現在如下2個方面：1）綜合了Binary Spray and Wait和PROPHET算法，分類討論了單副本傳送和多副本傳送問題，對單副本傳送綜合考慮運動水平指數和歷史接觸信息，對多副本傳送僅考慮運動水平指數，解決了Binary Spray and Wait算法在噴灑階段由于泛洪導致網絡負載增大和在等待階段使用被動的直接投遞算法導致消息投遞率下降的問題；2）解決了戰場環境下，由于高網絡負載和低消息投遞率所帶來的信道擁塞、單點失效和貽誤戰機等問題。

1.1 節點運動水平指數的量化

在本文中，節點運動水平指數MWM（Mean Weighted Moving）如式（1）所示：

其中的v0、vt、…、vn-1為某個樣本節點在10 min內按時間由近及遠隨機抽取n個時刻的瞬時速度。

采樣步長取10 min的主要原因為：仿真過程表明，當采樣步長大于10 min時，采樣精度不夠；而取采樣步長小于10 min時，又會出現采樣節點運動狀態沒有發生變化，而增加了網絡負載率的問題。從實際戰場環境分析，如果一個作戰節點超過10 min對呼叫方沒有應答，則認為該節點喪失通信能力，不可以作為中繼節點進行選擇。

按照時間局部性原則，距離當前時刻越近的移動節點的速度應越契合當前時刻的移動節點的速度，所以v0被賦予的權值最大，為n；vn-1被賦予的權值最小，為1。n既是某個樣本節點被隨機抽取的總個數，同時也是瞬時速度的權值。在本文中，設定n=10。

本文中設置為每隔2 h采樣一次，即采樣周期為2 h。主要原因為：戰場環境的總體局勢不會因為某個節點運動狀態的變化而發生重大轉變，只有當可觀數目的戰場節點同時發生變化，戰場總體態勢才會發生變化，仿真實驗表明，2 h以內節點的總體運動態勢比較平穩，因此，把采樣周期設定為2 h，這便于保證上級指揮所實時掌握戰場全局態勢的同時，也不會因為頻繁采樣的原因而增大戰場網絡資源的開銷。

MWM值每2 h更新一次，通過式（1）分別計算出不同時段的節點運動水平指數。每個節點的運動水平指數分為如下3種：1）MWM≤3時，第1種：移動水平最弱的節點；2）3＜MWM≤10時，第2種：移動水平適中的節點；3）MWM＞10時，第3種：移動水平最強的節點。MWM的單位為m/s。

1.2 路由算法

MRA算法綜合考慮節點移動性的運動水平指數（MWM）和歷史接觸信息完成消息傳送。當兩個節點相遇時，要進行消息傳送的節點檢查自身攜帶的消息副本數是否大于1。MRA算法步驟如下。

步驟1消息副本數大于1。1）要進行消息傳送的節點A的MWM屬于第1種類別且它所相遇節點B的MWM高于第1種類別；2）節點A的MWM不屬于第1種類別且它所相遇節點B的MWM高于或等于節點A的MWM。則A傳送1/2（如果不能被2整除，則向下取整）的消息副本數至B，否則不予傳送。中繼節點B大于1個時，選取MWM最大的節點。

步驟2消息副本數等于1。檢驗到此消息副本在之前的步驟中被傳送過，則無需任何操作。

步驟3消息副本數等于1。檢驗到此消息副本在之前的步驟中沒有被傳送過，此時除了節點的MWM，節點的歷史接觸信息也要考慮進消息副本的傳送過程當中，即：每個節點都要保存在過去某段時間內該節點的相遇信息，超出算法規定時窗時，相遇節點從某節點的歷史接觸信息中自動丟棄。基于此，選出曾經與目的節點相遇的中繼節點。根據局部性訪問原理，過去的時窗范圍內與目的節點有過相遇的中繼節點，更有可能在未來與目的節點發生相遇。基于此作如下討論：1）如果要進行消息傳送的節點A的MWM屬于第1種類別，且它所相遇節點B的MWM高于第1種類別，且B節點在所規定的時窗內曾與目的節點相遇；2）節點A的MWM不屬于第1種類別，且它所相遇的B節點在所規定的時窗內曾與目的節點相遇。則A將該消息傳送給B。中繼節點B大于1個時，針對1）選取MWM最大的節點，如MWM相同，則選取最小時窗的節點；針對2）選取最小時窗的節點。

MRA的具體步驟如下所示。

2 仿真分析

本文運用離散時間模擬器ONE對MRA算法進行仿真，比較分析了MRA算法與Epidemic、Spray and Wait和PROPHET 3種DTN經典路由算法在消息投遞率、網絡負載率、平均時延等方面的仿真結果。

2.1 仿真環境的運動模型

假設作戰單元在遂行作戰任務時，各作戰節點依據各自目標，可隨時調整運動路線，具有自主機動性。為了更貼合戰場環境的實際，選用隨機路點移動模型（Random Waypoint Mobility Model，RWP）。

2.2 仿真參數

表1 仿真參數設置

表1為本實驗的具體參數設置。仿真過程中各類作戰節點數固定為50個，150個節點隨機分布在10 000 m×8 000 m的場地中；第1類節點、第2類節點、第3類節點的移動速度分別設置為1 m/s、3 m/s、10 m/s；節點生存時間 TTL（Time To Live）為24 h；每類節點都配備有藍牙廣播界面，通信范圍為：10 m、20 m、100 m。

2.3 仿真結果

如圖1所示，所有算法的消息投遞率都隨著仿真時間的增加而得到提升，在經過4天的仿真后，所有算法的消息投遞率都到達一個最大值。Epidemic算法消息投遞率最低的主要原因是：Epidemic算法的核心是把消息復制并傳送到本身遇到的每一個節點，導致節點緩沖區的容量嚴重不足，發生“溢出”的現象，于是新到來的消息不能及時得到傳送；MRA算法和PROPHET算法則都因沒有使用Epidemic的洪泛機制，因此，與Epidemic相比，兩者具有較高的消息投遞率；而Spray and Wait算法的Spray階段與Epidemic算法的原理一樣，是多副本拷貝路由，而Wait階段則是單副本路由，所以Spray and Wait算法的消息投遞率低于MRA算法和PROPHET算法，高于Epidemic算法。通過圖1可以發現，MRA算法和PROPHET算法經過4 d的仿真后消息投遞率均超過了80%。

圖1 消息投遞率

圖2 網絡負載率

如圖2所示，PROPHET算法的消息副本數的上限只與DP（Delivery Predictability）值有關：節點只要遇到比自身DP值大的鄰居節點，就進行傳送。因此，與Epidemic算法一樣，大量冗余的消息副本將產生擁塞問題，增大網絡負載率，所以Epidemic算法和PROPHET算法的網絡負載率都較大，約為MRA算法和Spray and Wait算法的100倍。而MRA算法取得了最優的結果，其主要原因是：MRA算法通過運動水平指數（MWM）和歷史接觸信息對圖2網絡負載率傳送的消息副本數進行有效控制，在仿真過程中，Spray and Wait中每個消息的副本數控制為32個；而MRA算法中第1類節點的副本數為16個，第2類節點為8個，第3類為1個。因此，MRA算法的網絡負載率比Spray and Wait還低。

圖3 平均時延

如圖3所示，Epidemic算法在平均時延中的仿真結果是最理想的，主要原因是：Epidemic算法對每一個消息都進行快速復制并傳送，導致在路由環境中每一個消息都存在大量副本，便于迅速傳送到目的節點。PROPHET算法的平均時延結果比Epidemic算法高，但均低于Spray and Wait和MRA算法。Spray and Wait和MRA算法平均時延較高的主要原因在于網絡傳送過程中對消息副本數的控制，其中MRA主要是通過運動水平指數（MWM）和歷史接觸信息控制消息副本數，使消息副本數遠小于Epidemic中的副本數，因此，該消息被傳送到目的節點的機會隨之減少，延長了從源節點到目的節點所消耗的時間。

3 結論

本文通過節點運動水平指數和歷史接觸信息，對消息副本傳送進行了有效控制。MRA算法的核心在于：依據節點運動水平指數（MWM）進行分類，使消息副本傳送到具有更高MWM的節點。該算法需要考慮的另一大因素是節點的歷史接觸信息，當進行單副本傳送時，中繼節點的選取除了MWM之外還需考慮時窗內與目的節點的歷史接觸信息。

仿真結果表明，MRA算法與 Epidemic、Spray and Wait、PROPHET算法相比，首先具有最低的網絡負載率，有效地控制了網絡擁塞，使得消息在生存時間TTL內能得到及時傳送，避免了消息失效，而在戰場環境下，消息的實時投遞是非常重要的；其次具有較高的消息投遞率，戰場環境下保證消息從上級指揮所到下級作戰平臺的成功投遞率也是要重點考慮的因素之一。雖然MRA算法增大了一定的平均時延，但一般情況下，在戰場環境下降低決策等級較高節點的網絡負載率和提高消息投遞率的意義高于降低平均時延。

下一步的研究工作主要是：1）針對多節點選擇同一高運動水平指數節點作為中繼節點時導致的網絡擁塞問題，主要研究高運動水平指數節點的布設方法。2）針對MRA算法中存在的較高平均時延問題，開展優化編碼調制方法研究。