戰(zhàn)場環(huán)境下基于節(jié)點(diǎn)移動(dòng)性的DTN路由算法*

和 何，李琳琳，路云飛

（火箭軍工程大學(xué)，西安 710025）

0 引言

容遲容斷網(wǎng)絡(luò)（DTN）是一種典型的在任意時(shí)刻任意兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)間缺乏可靠路徑的特殊網(wǎng)絡(luò)。不同于傳統(tǒng)通信網(wǎng)絡(luò)，DTN使用存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)機(jī)制[1]，能夠有效地解決網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化、通信鏈路經(jīng)常中斷、間歇性連接、傳送延遲長、資源有限等問題[2]。因此，近年來針對(duì)DTN的路由算法已經(jīng)成為研究網(wǎng)絡(luò)通信的一大熱點(diǎn)。

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

1 基于節(jié)點(diǎn)移動(dòng)性的路由算法

一個(gè)作戰(zhàn)單元在遂行作戰(zhàn)任務(wù)時(shí)，所面臨的情況是稍縱即逝、難以預(yù)知的，加之通信資源稀缺，作戰(zhàn)節(jié)點(diǎn)之間很難做到實(shí)時(shí)通信，即不存在穩(wěn)定可靠的端到端通信鏈路，即認(rèn)為在某些戰(zhàn)場環(huán)境下通信網(wǎng)絡(luò)屬于DTN網(wǎng)絡(luò)[12]。

戰(zhàn)場環(huán)境下節(jié)點(diǎn)類型主要包括：武器平臺(tái)、各級(jí)指揮所、作戰(zhàn)單兵、通信節(jié)點(diǎn)、便攜式移動(dòng)終端等?；诠?jié)點(diǎn)的運(yùn)動(dòng)水平指數(shù)和歷史接觸信息，把消息傳送給在每個(gè)作戰(zhàn)單元內(nèi)具有最大運(yùn)動(dòng)水平指數(shù)的節(jié)點(diǎn)，其次通過這些節(jié)點(diǎn)進(jìn)行作戰(zhàn)單元間以及作戰(zhàn)單元與上級(jí)指揮所間的通信。

MRA算法的主要?jiǎng)?chuàng)新點(diǎn)體現(xiàn)在如下2個(gè)方面：1）綜合了Binary Spray and Wait和PROPHET算法，分類討論了單副本傳送和多副本傳送問題，對(duì)單副本傳送綜合考慮運(yùn)動(dòng)水平指數(shù)和歷史接觸信息，對(duì)多副本傳送僅考慮運(yùn)動(dòng)水平指數(shù)，解決了Binary Spray and Wait算法在噴灑階段由于泛洪導(dǎo)致網(wǎng)絡(luò)負(fù)載增大和在等待階段使用被動(dòng)的直接投遞算法導(dǎo)致消息投遞率下降的問題；2）解決了戰(zhàn)場環(huán)境下，由于高網(wǎng)絡(luò)負(fù)載和低消息投遞率所帶來的信道擁塞、單點(diǎn)失效和貽誤戰(zhàn)機(jī)等問題。

1.1 節(jié)點(diǎn)運(yùn)動(dòng)水平指數(shù)的量化

在本文中，節(jié)點(diǎn)運(yùn)動(dòng)水平指數(shù)MWM（Mean Weighted Moving）如式（1）所示：

其中的v0、vt、…、vn-1為某個(gè)樣本節(jié)點(diǎn)在10 min內(nèi)按時(shí)間由近及遠(yuǎn)隨機(jī)抽取n個(gè)時(shí)刻的瞬時(shí)速度。

采樣步長取10 min的主要原因?yàn)椋悍抡孢^程表明，當(dāng)采樣步長大于10 min時(shí)，采樣精度不夠；而取采樣步長小于10 min時(shí)，又會(huì)出現(xiàn)采樣節(jié)點(diǎn)運(yùn)動(dòng)狀態(tài)沒有發(fā)生變化，而增加了網(wǎng)絡(luò)負(fù)載率的問題。從實(shí)際戰(zhàn)場環(huán)境分析，如果一個(gè)作戰(zhàn)節(jié)點(diǎn)超過10 min對(duì)呼叫方?jīng)]有應(yīng)答，則認(rèn)為該節(jié)點(diǎn)喪失通信能力，不可以作為中繼節(jié)點(diǎn)進(jìn)行選擇。

按照時(shí)間局部性原則，距離當(dāng)前時(shí)刻越近的移動(dòng)節(jié)點(diǎn)的速度應(yīng)越契合當(dāng)前時(shí)刻的移動(dòng)節(jié)點(diǎn)的速度，所以v0被賦予的權(quán)值最大，為n；vn-1被賦予的權(quán)值最小，為1。n既是某個(gè)樣本節(jié)點(diǎn)被隨機(jī)抽取的總個(gè)數(shù)，同時(shí)也是瞬時(shí)速度的權(quán)值。在本文中，設(shè)定n=10。

本文中設(shè)置為每隔2 h采樣一次，即采樣周期為2 h。主要原因?yàn)椋簯?zhàn)場環(huán)境的總體局勢不會(huì)因?yàn)槟硞€(gè)節(jié)點(diǎn)運(yùn)動(dòng)狀態(tài)的變化而發(fā)生重大轉(zhuǎn)變，只有當(dāng)可觀數(shù)目的戰(zhàn)場節(jié)點(diǎn)同時(shí)發(fā)生變化，戰(zhàn)場總體態(tài)勢才會(huì)發(fā)生變化，仿真實(shí)驗(yàn)表明，2 h以內(nèi)節(jié)點(diǎn)的總體運(yùn)動(dòng)態(tài)勢比較平穩(wěn)，因此，把采樣周期設(shè)定為2 h，這便于保證上級(jí)指揮所實(shí)時(shí)掌握戰(zhàn)場全局態(tài)勢的同時(shí)，也不會(huì)因?yàn)轭l繁采樣的原因而增大戰(zhàn)場網(wǎng)絡(luò)資源的開銷。

MWM值每2 h更新一次，通過式（1）分別計(jì)算出不同時(shí)段的節(jié)點(diǎn)運(yùn)動(dòng)水平指數(shù)。每個(gè)節(jié)點(diǎn)的運(yùn)動(dòng)水平指數(shù)分為如下3種：1）MWM≤3時(shí)，第1種：移動(dòng)水平最弱的節(jié)點(diǎn)；2）3＜MWM≤10時(shí)，第2種：移動(dòng)水平適中的節(jié)點(diǎn)；3）MWM＞10時(shí)，第3種：移動(dòng)水平最強(qiáng)的節(jié)點(diǎn)。MWM的單位為m/s。

1.2 路由算法

MRA算法綜合考慮節(jié)點(diǎn)移動(dòng)性的運(yùn)動(dòng)水平指數(shù)（MWM）和歷史接觸信息完成消息傳送。當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí)，要進(jìn)行消息傳送的節(jié)點(diǎn)檢查自身攜帶的消息副本數(shù)是否大于1。MRA算法步驟如下。

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

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

步驟3消息副本數(shù)等于1。檢驗(yàn)到此消息副本在之前的步驟中沒有被傳送過，此時(shí)除了節(jié)點(diǎn)的MWM，節(jié)點(diǎn)的歷史接觸信息也要考慮進(jìn)消息副本的傳送過程當(dāng)中，即：每個(gè)節(jié)點(diǎn)都要保存在過去某段時(shí)間內(nèi)該節(jié)點(diǎn)的相遇信息，超出算法規(guī)定時(shí)窗時(shí)，相遇節(jié)點(diǎn)從某節(jié)點(diǎn)的歷史接觸信息中自動(dòng)丟棄?；诖?，選出曾經(jīng)與目的節(jié)點(diǎn)相遇的中繼節(jié)點(diǎn)。根據(jù)局部性訪問原理，過去的時(shí)窗范圍內(nèi)與目的節(jié)點(diǎn)有過相遇的中繼節(jié)點(diǎn)，更有可能在未來與目的節(jié)點(diǎn)發(fā)生相遇?；诖俗魅缦掠懻摚?）如果要進(jìn)行消息傳送的節(jié)點(diǎn)A的MWM屬于第1種類別，且它所相遇節(jié)點(diǎn)B的MWM高于第1種類別，且B節(jié)點(diǎn)在所規(guī)定的時(shí)窗內(nèi)曾與目的節(jié)點(diǎn)相遇；2）節(jié)點(diǎn)A的MWM不屬于第1種類別，且它所相遇的B節(jié)點(diǎn)在所規(guī)定的時(shí)窗內(nèi)曾與目的節(jié)點(diǎn)相遇。則A將該消息傳送給B。中繼節(jié)點(diǎn)B大于1個(gè)時(shí)，針對(duì)1）選取MWM最大的節(jié)點(diǎn)，如MWM相同，則選取最小時(shí)窗的節(jié)點(diǎn)；針對(duì)2）選取最小時(shí)窗的節(jié)點(diǎn)。

MRA的具體步驟如下所示。

2 仿真分析

本文運(yùn)用離散時(shí)間模擬器ONE對(duì)MRA算法進(jìn)行仿真，比較分析了MRA算法與Epidemic、Spray and Wait和PROPHET 3種DTN經(jīng)典路由算法在消息投遞率、網(wǎng)絡(luò)負(fù)載率、平均時(shí)延等方面的仿真結(jié)果。

2.1 仿真環(huán)境的運(yùn)動(dòng)模型

假設(shè)作戰(zhàn)單元在遂行作戰(zhàn)任務(wù)時(shí)，各作戰(zhàn)節(jié)點(diǎn)依據(jù)各自目標(biāo)，可隨時(shí)調(diào)整運(yùn)動(dòng)路線，具有自主機(jī)動(dòng)性。為了更貼合戰(zhàn)場環(huán)境的實(shí)際，選用隨機(jī)路點(diǎn)移動(dòng)模型（Random Waypoint Mobility Model，RWP）。

2.2 仿真參數(shù)

表1 仿真參數(shù)設(shè)置

表1為本實(shí)驗(yàn)的具體參數(shù)設(shè)置。仿真過程中各類作戰(zhàn)節(jié)點(diǎn)數(shù)固定為50個(gè)，150個(gè)節(jié)點(diǎn)隨機(jī)分布在10 000 m×8 000 m的場地中；第1類節(jié)點(diǎn)、第2類節(jié)點(diǎn)、第3類節(jié)點(diǎn)的移動(dòng)速度分別設(shè)置為1 m/s、3 m/s、10 m/s；節(jié)點(diǎn)生存時(shí)間 TTL（Time To Live）為24 h；每類節(jié)點(diǎn)都配備有藍(lán)牙廣播界面，通信范圍為：10 m、20 m、100 m。

2.3 仿真結(jié)果

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

圖1 消息投遞率

圖2 網(wǎng)絡(luò)負(fù)載率

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

圖3 平均時(shí)延

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

3 結(jié)論

本文通過節(jié)點(diǎn)運(yùn)動(dòng)水平指數(shù)和歷史接觸信息，對(duì)消息副本傳送進(jìn)行了有效控制。MRA算法的核心在于：依據(jù)節(jié)點(diǎn)運(yùn)動(dòng)水平指數(shù)（MWM）進(jìn)行分類，使消息副本傳送到具有更高M(jìn)WM的節(jié)點(diǎn)。該算法需要考慮的另一大因素是節(jié)點(diǎn)的歷史接觸信息，當(dāng)進(jìn)行單副本傳送時(shí)，中繼節(jié)點(diǎn)的選取除了MWM之外還需考慮時(shí)窗內(nèi)與目的節(jié)點(diǎn)的歷史接觸信息。

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

下一步的研究工作主要是：1）針對(duì)多節(jié)點(diǎn)選擇同一高運(yùn)動(dòng)水平指數(shù)節(jié)點(diǎn)作為中繼節(jié)點(diǎn)時(shí)導(dǎo)致的網(wǎng)絡(luò)擁塞問題，主要研究高運(yùn)動(dòng)水平指數(shù)節(jié)點(diǎn)的布設(shè)方法。2）針對(duì)MRA算法中存在的較高平均時(shí)延問題，開展優(yōu)化編碼調(diào)制方法研究。