李陟，姜怡，李千目，劉鳳玉

(1. 北京郵電大學(xué) 信息與通信工程學(xué)院，北京100876；2. 南京理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 南京 210094；3. 北京啟明星辰信息安全技術(shù)有限公司，北京 100193)

1 引言

移動 ad hoc網(wǎng)絡(luò)（MANET, mobile ad hoc networks）是一種由移動節(jié)點自組織而成的無中心的多跳無線網(wǎng)絡(luò)。網(wǎng)絡(luò)中數(shù)據(jù)分組從源節(jié)點發(fā)送到目的節(jié)點需要依靠多個中間節(jié)點的轉(zhuǎn)發(fā)，因此如何路由是MANET研究中的一個核心問題，如按需矢量路由AODV[1]、動態(tài)源路由DSR[2]、目的序列距離矢量路由DSDV[3]等都是應(yīng)用在MANET上的路由協(xié)議。MANET路由需要假定網(wǎng)絡(luò)在路由過程中具有連通性和一定的穩(wěn)定性，即網(wǎng)絡(luò)拓撲表現(xiàn)為連通圖，且其節(jié)點移動較緩慢或基本不動。然而，在很多場合下，這種假定并不存在，高速的移動和并不足夠的節(jié)點密度往往造成拓撲的不連通和反復(fù)的劇烈變化，如高速運動的車輛組成的公路車輛網(wǎng)絡(luò)[4]，或是由少量節(jié)點組成的并不時刻連通的生物檢測網(wǎng)絡(luò)[5]等。時延容忍網(wǎng)絡(luò)（DTN, delay tolerant networks）作為一種適應(yīng)性更強的網(wǎng)絡(luò)結(jié)構(gòu)被提出，其存儲轉(zhuǎn)發(fā)機制使用逐跳（hop-by-hop）路由的方式替代傳統(tǒng)MANET中的端到端（end-to-end）路由，從而解決了在不穩(wěn)定拓撲的環(huán)境下，端到端路由無法被成功建立的問題。

相比較MANET路由，DTN路由協(xié)議對網(wǎng)絡(luò)環(huán)境更強的適應(yīng)能力是通過更高的時間和空間代價換取的，其路由協(xié)議往往通過高代價的洪泛來尋找目的節(jié)點，如最早提出的傳染路由（epidemic routing）[6]、通過有限副本約束洪泛的噴射等待路由（spray and wait）[7]、以節(jié)點相遇概率作為效用值進行有條件洪泛的先知路由（PROPHET routing）[8]等。同時，存儲轉(zhuǎn)發(fā)機制也決定了 DTN路由協(xié)議具有更高通信延遲。因此，DTN路由協(xié)議的性能主要體現(xiàn)在其對洪泛和時延的抑制。

在真實的應(yīng)用中，網(wǎng)絡(luò)的拓撲往往不是單一的結(jié)構(gòu)，而是由不同拓撲結(jié)構(gòu)的網(wǎng)絡(luò)之間相互連通構(gòu)成的復(fù)雜結(jié)構(gòu)。如文獻[8]中的校園社交網(wǎng)絡(luò)，文獻[4]中的公路車輛網(wǎng)，文獻[9]中的鄉(xiāng)村道路網(wǎng)絡(luò)等，這些網(wǎng)絡(luò)的特點是拓撲結(jié)構(gòu)隨著時間而發(fā)生變化，網(wǎng)絡(luò)中的部分區(qū)域的拓撲結(jié)構(gòu)相對穩(wěn)定，始終連通，而另外一部分區(qū)域的拓撲結(jié)構(gòu)則具有短暫或間歇性連通的特性。這樣的網(wǎng)絡(luò)環(huán)境一些局部符合MANET的特性，一些局部必須依靠 DTN進行路由。若完全采用MANET路由，則路由成功率很低，無法保證正常的網(wǎng)絡(luò)服務(wù)；若完全采用DTN路由，則在節(jié)點運動能力較低的區(qū)域內(nèi)，DTN依靠多節(jié)點持有副本增加路由成功率的策略又增加了不必要的網(wǎng)絡(luò)負載。因此，有必要設(shè)計一種能夠根據(jù)網(wǎng)絡(luò)的拓撲情況自適應(yīng)的異構(gòu)路由策略，使之能夠在連通區(qū)域采用MANET單副本快速高效路由，在不連通區(qū)域間采用DTN多副本存儲轉(zhuǎn)發(fā)高容錯路由。

2 相關(guān)工作

文獻[10]分析了實現(xiàn)MANET和DTN混合路由的可能性，并實現(xiàn)了一種簡單的混合路由策略，該策略首先基于AODV的RREQ過程尋找連通區(qū)域內(nèi)的目的節(jié)點，若能夠直接使用AODV路由，則更新路由表，并進行路由，否則，以RREQ過程中發(fā)現(xiàn)的DTN節(jié)點為目的節(jié)點，將數(shù)據(jù)轉(zhuǎn)發(fā)到該節(jié)點，并轉(zhuǎn)為 DTN路由。該算法對路由策略的轉(zhuǎn)換條件的判斷較為簡單，雖然能夠在MANET算法失效時通過DTN繼續(xù)路由，但是由于MANET區(qū)域的存在，使得如PROPHET這樣的路由的投遞成功率并不高。文獻[11]對文獻[10]的工作進行了改進，提出了一種基于 DYMO[12]協(xié)議與 PROPHET協(xié)議的混合路由策略—DT-DYMO路由。該路由中每個節(jié)點都計算和維護著其到網(wǎng)絡(luò)中所有節(jié)點的相遇效用值，并以此作為MANET路由階段的路由發(fā)現(xiàn)過程中選擇中繼節(jié)點的依據(jù)，即源節(jié)點將選擇返回RREP的節(jié)點中到達目的節(jié)點效用值最高的節(jié)點作為中繼節(jié)點，并通過 DYMO的方式發(fā)送數(shù)據(jù)分組到該節(jié)點，再由該節(jié)點轉(zhuǎn)換為PROPHET路由，進入 DTN路由階段。DT-DYMO中每個節(jié)點都要維護一份全網(wǎng)的相遇效用信息，這使得維護成本較高，并且當(dāng)數(shù)據(jù)分組傳輸路徑中存在多個MANET區(qū)域時，DT-DYMO不能自適應(yīng)地轉(zhuǎn)換 DYMO協(xié)議，而仍然只能通過DTN來路由，在這種情況下，其路由協(xié)議的網(wǎng)絡(luò)拓撲適應(yīng)性不高，路由性能也低于僅進行MANET到DTN一次路由轉(zhuǎn)換的情況。文獻[13]提出一種基于分簇拓撲結(jié)構(gòu)的 DTNMANET混合路由策略HYMAD，該策略在簇間采用Spray-and-Wait的DTN路由，當(dāng)數(shù)據(jù)分組到達目的節(jié)點所在簇后轉(zhuǎn)換為 MANET中的距離矢量路由。該路由策略僅應(yīng)用在目的節(jié)點所在簇較大時，相對 DTN路由具有較明顯的性能改進。文獻[14]設(shè)計了一種讓少量游離于MANET基礎(chǔ)拓撲邊緣的高速運動節(jié)點具有DTN路由能力的混合路由策略，使得這部分節(jié)點在與 MANET主體拓撲斷開連接后，能夠?qū)?shù)據(jù)分組存儲等待拓撲再次連通后再進行轉(zhuǎn)發(fā)。文獻[15]提出了一種結(jié)合傳染路由和集中式路由的基于統(tǒng)治集的路由策略，該策略首先部署一定數(shù)量的服務(wù)節(jié)點在固定位置，作為超級節(jié)點(super node)，同時假設(shè)這些超級節(jié)點可以穩(wěn)定地接入互聯(lián)網(wǎng)。這些超級節(jié)點同時也作為 DTN網(wǎng)關(guān)，在無法找到目的節(jié)點時，執(zhí)行 DTN路由的存儲轉(zhuǎn)發(fā)策略。該路由策略在超級節(jié)點的選擇上具有較大的局限性，且網(wǎng)絡(luò)拓撲的適應(yīng)能力不強。文獻[16]提出了一種基于DTN的OLSR路由，主要是通過增加部分節(jié)點的時延容忍能力，使得在網(wǎng)絡(luò)分割時，非DTN節(jié)點可以利用相鄰DTN節(jié)點的存儲轉(zhuǎn)發(fā)功能，降低由分組丟失引起的路由性能下降。該路由的實驗設(shè)定為采用mesh結(jié)構(gòu)，DTN功能主要實現(xiàn)于上層的高功率節(jié)點，這種結(jié)構(gòu)靈活性較差，且mesh節(jié)點的部署合理性也對路由影響較大。

綜上所述，設(shè)計高效可行的異構(gòu)路由策略的主要挑戰(zhàn)在于能夠在路由的過程中，讓節(jié)點根據(jù)其本地拓撲環(huán)境，自適應(yīng)地選擇最合理的路由策略，并且能夠在MANET和DTN之間按需進行轉(zhuǎn)換。文獻[10～14]所提出的異構(gòu)混合路由策略都只考慮了從MANET到DTN的路由轉(zhuǎn)換，路由協(xié)議不能夠根據(jù)本地拓撲狀態(tài)自適應(yīng)的發(fā)生轉(zhuǎn)換，即使在節(jié)點處于大范圍穩(wěn)定且連通的網(wǎng)絡(luò)環(huán)境中時，路由也不具有從DTN轉(zhuǎn)換為MANET的功能，并且也都未說明混合路由策略所應(yīng)用的網(wǎng)絡(luò)拓撲模型。文獻[15,16]雖然通過加入類似基站的固定節(jié)點提高了路由的自適應(yīng)性，但是同時也減低了拓撲的環(huán)境適應(yīng)能力。本文首先明確定義了網(wǎng)絡(luò)拓撲模型中MANET和DTN的主次關(guān)系，并基于以DTN為主的拓撲模型下，設(shè)計了一種可以自適應(yīng)轉(zhuǎn)換為MANET的路由協(xié)議，該協(xié)議不需要加入固定基站節(jié)點的支持，完全根據(jù)本地路由環(huán)境自適應(yīng)完成。

3 網(wǎng)絡(luò)模型

在無線移動ad hoc網(wǎng)絡(luò)中，由于節(jié)點的運動，使得由節(jié)點和節(jié)點間通信鏈路為邊而構(gòu)成網(wǎng)絡(luò)拓撲圖也在不斷地變化，因此，網(wǎng)絡(luò)模型也就取決于節(jié)點的分布和運動方式。通常，無論是在MANET或是DTN網(wǎng)絡(luò)中，任何的路由策略都是基于特定的網(wǎng)絡(luò)拓撲模型而設(shè)計，因此對混合路由策略的研究，也必須先定義明確的網(wǎng)絡(luò)拓撲模型。以基礎(chǔ)拓撲作為劃分的依據(jù)，MANET和DTN異構(gòu)共存的網(wǎng)絡(luò)模型可以分為2類：類型1稱為基于MANET的拓撲，記為DOM（DTN over manet）模型，這類網(wǎng)絡(luò)中，大部分的節(jié)點相互連通，拓撲變化頻率較低，存在少量高速移動或與連通區(qū)域間歇性連通的節(jié)點，通?？梢曰谟蒑ANET節(jié)點構(gòu)成的連通統(tǒng)治集[17]來設(shè)計路由策略；類型2稱為基于DTN的拓撲，記為MOD（manet over DTN）模型，這類網(wǎng)絡(luò)中，網(wǎng)絡(luò)拓撲圖被分割為多個不相互連通的區(qū)域，拓撲圖整體不是連通圖，但是，在每個孤立的局部區(qū)域內(nèi)部又是相互連通的和拓撲相對穩(wěn)定的。

基于以上對網(wǎng)絡(luò)拓撲模型的定義，對比文獻[10,11,13]給出的路由策略，可以看出，其相同點是第1階段路由協(xié)議都是基于MANET，當(dāng)MANET失效后，第2階段采用DTN路由以避免路由的失敗。顯然，這樣的設(shè)計在網(wǎng)絡(luò)中存在大量MANET節(jié)點的DOM模型中是比較有效的，但是在路由維護的開銷上增加了為了少數(shù)不連通節(jié)點而需要維護的所有節(jié)點間的相遇效用。對于MOD模型，若發(fā)起路由時所在的區(qū)域內(nèi)相互連通的節(jié)點數(shù)量較少，則這些路由策略基本等同于直接使用DTN路由。下面通過定義1給出本文具體的網(wǎng)絡(luò)拓撲模型的定義。

定義1 設(shè)G為網(wǎng)絡(luò)拓撲圖，V為網(wǎng)絡(luò)中節(jié)點的集合。VM?V為網(wǎng)絡(luò)中一組相互間相對位置穩(wěn)定的節(jié)點，且網(wǎng)絡(luò)拓撲圖GM=(VM,EM)是連通圖。這里，EM為定義在圖GM上的邊集，若節(jié)點u, v∈VM，且u, v之間存在一條穩(wěn)定的通信鏈路，則u, v間存在邊euv∈EM。設(shè)網(wǎng)絡(luò)中存在有n(n為正整數(shù))組這樣的節(jié)點集合VM1,…,VMn，且不存在邊euv，使得節(jié)點u∈VMi,v∈VMj,i≠j。

定義1是基于MOD模型給出的網(wǎng)絡(luò)拓撲模型定義，當(dāng)n=1時，就轉(zhuǎn)變?yōu)镈OM模型。在定義中，每一個GM都是一個連通的拓撲穩(wěn)定的MANET區(qū)域，當(dāng)節(jié)點發(fā)起一次路由時，通常認為會穿過多個這樣的區(qū)域，這就需要路由策略能夠根據(jù)本地局部拓撲信息自適應(yīng)地選擇使用最合適的路由算法，以達到最高的性能。而文獻[10,11,13]中所給出的只轉(zhuǎn)換一次路由算法的策略顯然不能在該網(wǎng)絡(luò)拓撲模型中達到最優(yōu)的性能。

4 穩(wěn)定閉域

4.1 穩(wěn)定閉域的定義及算法

相比DTN路由，在MOD網(wǎng)絡(luò)中，處于拓撲穩(wěn)定區(qū)域內(nèi)的節(jié)點采用單播傳輸方式的MANET路由能夠有效降低網(wǎng)絡(luò)中的冗余數(shù)據(jù)傳輸，并具有更低的傳輸時延和更高的傳輸成功率，但這需要端到端的連通穩(wěn)定拓撲的支持。理想狀態(tài)下，當(dāng)數(shù)據(jù)分組進入MANET區(qū)域后，將改為MANET路由，因此，只有MANET區(qū)域邊界上的節(jié)點需要具有DTN路由能力。如圖1所示，以網(wǎng)絡(luò)中一塊連通且拓撲穩(wěn)定的MANET區(qū)域為例，節(jié)點v1,…,v7的功率覆蓋區(qū)域的外沿形成了一個閉合區(qū)域，該區(qū)域滿足以下條件：1) 區(qū)域內(nèi)任意節(jié)點的功率覆蓋范圍都不超出該閉合區(qū)域的外沿；2) 任意DTN節(jié)點與該區(qū)域內(nèi)任意節(jié)點相遇前都將先與組成該閉合區(qū)域外沿的節(jié)點相遇。可以認為MANET路由的數(shù)據(jù)傳輸速度遠大于DTN節(jié)點的運動速度，因此，DTN節(jié)點與該穩(wěn)定區(qū)域內(nèi)任意節(jié)點間的通信都可以由組成閉域外沿的節(jié)點進行代理。下面給出閉域節(jié)點集的明確定義和求解閉域的分布式算法。

圖1 穩(wěn)定閉域

定義2 從任意方向穿過GM圖，最先遇到的節(jié)點的集合定義為該GM圖的閉域節(jié)點集(EHS, enclosure host set)。

假定網(wǎng)絡(luò)中所有節(jié)點間相對的運動模型不會發(fā)生改變，即若任選節(jié)點u, v，則u, v始終相對移動性較低（即滿足MANET路由對節(jié)點移動性的需求）或始終相對移動性較高（即符合DTN節(jié)點的移動模型），且所有節(jié)點功率半徑都相同，用d表示，那么有以下定義。

定義3 設(shè)節(jié)點u, v∈V，若u, v始終相對移動性較低，u, v在GM圖上的實際距離為D，若D≤nd，則v是u的n倍功率半徑鄰居，所有這樣的節(jié)點v構(gòu)成了u的n倍功率半徑鄰居集合，記為Nbrn( u)。

以下算法假定目標區(qū)域的拓撲滿足GM的定義，每個節(jié)點都有唯一的ID號，且知道自己的位置信息。

算法1 求EHS集的分布式算法

1) 對該區(qū)域內(nèi)任意節(jié)點u，令其與Nbr2( u)中節(jié)點交換位置信息。

2) 對于每個v∈Nbr2( u)，分別計算以v為圓心d為半徑的圓Cv在u為圓心d為半徑的圓Cu上截取的圓弧[rad( u, v)start,rad( u, v)end]，若則u?EHS，否則u∈EHS。

4.2 基于穩(wěn)定閉域的限定連通統(tǒng)治集

在以MOD為拓撲模型的網(wǎng)絡(luò)中，存在著多個移動能力較低，拓撲較為穩(wěn)定的區(qū)域，這些區(qū)域會阻礙DTN中通過有限副本數(shù)量依靠節(jié)點運動能力來把數(shù)據(jù)分組投遞到目的節(jié)點的投遞成功率，如進入等待過程的Spray and Wait路由，當(dāng)副本傳入到這些穩(wěn)定區(qū)域后，就無法再隨著節(jié)點而移動了。因此，本文選用PROPHET這個基于洪泛多副本機制的路由協(xié)議作為混合路由中DTN階段的路由協(xié)議。在PROPHET路由中，需要維護一個所有節(jié)點的通信效用表，以此作為DTN路由選擇下一跳中繼節(jié)點的依據(jù)。顯然，DTN節(jié)點只通過與EHS集合中的節(jié)點交換信息是不能夠構(gòu)建包括閉域中所有節(jié)點的通信效用表的，因此，需要通過構(gòu)造一個包含EHS節(jié)點在內(nèi)的限定連通統(tǒng)治集（CCDS, constrained connected dominating set），用于收集閉域內(nèi)部節(jié)點的信息，并傳送給參與DTN協(xié)議的EHS集合中的節(jié)點。

算法2 求CCDS集的分布式算法

1) 執(zhí)行算法1，若節(jié)點u∈EHS，則把u加入CCDS。

2) 若節(jié)點u存在至少2個不相鄰的鄰居，則把u加入CCDS。

3) 設(shè)u, v, w∈CCDS，u?EHS，IDv＞IDu,IDw＞IDu，v∈Nbr1( u), w∈Nbr1( u), w∈Nbr1( u)，P=EHS∩Nbr1( v), Q=EHS∩Nbr1( w)，則以下情況中把u從CCDS中刪除。

a)Nbr1( u){v}?Nbr1( v){u},不考慮ID的 關(guān)系；

b)Nbr1( u){v}=Nbr1( v){u}；

c)Nbr1( u){v}?Nbr1( v)∪Nbr1( P)；

d)Nbr1( u){v}?Nbr1( v)∪Nbr1( P)∪Nbr1( w)∪Nbr1( Q)。

定理1 CCDS是連通的，且所有節(jié)點或在CCDS上或被CCDS所統(tǒng)治。

證明 由定義1知網(wǎng)絡(luò)拓撲初始是連通圖，對于任意節(jié)點u∈CCDS，顯然節(jié)點v∈Nbr1( u)且v∈CCDS是與其連通的。若w∈Nbr2( u)，由定義1，必存在節(jié)點p，使得w, u在原拓撲圖上連通，由步驟2)知p∈CCDS，因此步驟2)得出的CCDS是連通的。設(shè)節(jié)點u?CCDS且Nbr1( u)∩CCDS=?，則Nbr2( u)∩CCDS≠?，由步驟2)必存在節(jié)點v∈Nbr1( u)，v需要被加入到CCDS中，這與定義1矛盾，因此執(zhí)行步驟2)后滿足定理1。考慮步驟3)的a)、b)，由于節(jié)點u的u所有鄰居都是v的鄰居，同時v∈CCDS，則所統(tǒng)治的節(jié)點同時也被v統(tǒng)治，u在CCDS上的鄰居同時也是v的鄰居，因此從CCDS刪去u仍然滿足定理1?？紤]c)，設(shè)由u統(tǒng)治的節(jié)點集Nbr1( u)=A∪B，其中A?Nbr1( v)，B?Nbr1( P)，A部分性質(zhì)已證，由于P中節(jié)點必定在最終CCDS結(jié)果集中，因此B部分節(jié)點必被P中節(jié)點統(tǒng)治，同時u在CCDS上的鄰居也與v或P中節(jié)點連通，因此從CCDS刪去u仍然滿足定理1，同理可證d)，證畢。

在600×600大小的場景范圍內(nèi)，由算法2構(gòu)建的一個總節(jié)點數(shù)為80個節(jié)點的CCDS拓撲如圖2所示，為EHS節(jié)點，為在CCDS集中的非EHS節(jié)點。在不同網(wǎng)絡(luò)密度下，CCDS集合中的節(jié)點個數(shù)占總節(jié)點數(shù)的百分比如圖3所示。可以看出隨著網(wǎng)絡(luò)密度的增大，使用CCDS來優(yōu)化拓撲，能夠減少50%以上的節(jié)點來參與DTN路由，這將極大地減小DTN路由的效用維護代價，同時很好地限制了DTN數(shù)據(jù)分組的無效洪泛。

圖2 CCDS拓撲

圖3 CCDS節(jié)點數(shù)占總節(jié)點數(shù)比例

5 基于穩(wěn)定閉域的混合路由策略

5.1 混合路由策略

異構(gòu)網(wǎng)絡(luò)間路由協(xié)議設(shè)計的關(guān)鍵問題是解決不同網(wǎng)絡(luò)結(jié)構(gòu)下路由協(xié)議的過渡問題。DTN路由協(xié)議中的PROPHET路由同樣可在MANET的網(wǎng)絡(luò)結(jié)構(gòu)下路由成功，在第2節(jié)所提及的相關(guān)工作由于無法自適應(yīng)地多次進行轉(zhuǎn)換路由，因此都采用了PROPHET作為在MANET失效后的DTN路由策略，使之能夠保證傳輸?shù)某晒β?。然而PROPHET有著近似于傳染路由的路由代價，且需要較長的熱身時間來收集足夠信息用于估計節(jié)點間的相遇概率，因此在可行性上有較大的局限。本文提出的混合路由策略很好地解決了MANET和DTN路由協(xié)議過渡過程中路由協(xié)議轉(zhuǎn)換時機選擇的問題。這種路由策略支持多次轉(zhuǎn)換以最大程度上利用2種路由協(xié)議的優(yōu)勢。

本文把算法1中標記的EHS節(jié)點作為MANET與DTN路由之間的轉(zhuǎn)換網(wǎng)關(guān)，把算法2中求得的CCDS節(jié)點作為參與DTN協(xié)議中節(jié)點通信效用維護的輔助節(jié)點。這樣就對MANET區(qū)域中節(jié)點的路由職責(zé)進行了劃分：EHS集合中的節(jié)點參與DTN路由；CCDS節(jié)點負責(zé)維護其所在MANET區(qū)域內(nèi)的節(jié)點信息；其余節(jié)點只運行MANET路由協(xié)議，不參與DTN路由。路由策略描述如下。

1) 每個節(jié)點基于鄰居行為對自身性質(zhì)進行判定，區(qū)分MANET與DTN。

2) MANET節(jié)點分別執(zhí)行算法1和算法2確定自己在網(wǎng)絡(luò)中的路由角色。

3) 節(jié)點根據(jù)路由角色執(zhí)行相應(yīng)路由協(xié)議。

第3節(jié)已經(jīng)說明了本文的網(wǎng)絡(luò)模型是基于宏觀DTN的，因此，混合路由策略的設(shè)計需要確保對已有DTN路由的完全支持。本文提出的路由策略所做的主要貢獻是減小了MANET和DTN混合結(jié)構(gòu)中DTN路由維護代價并實現(xiàn)了數(shù)據(jù)分組在穿越不同結(jié)構(gòu)網(wǎng)絡(luò)環(huán)境時路由協(xié)議的自適應(yīng)轉(zhuǎn)換。下面分別對以PROPHET為路由的網(wǎng)絡(luò)應(yīng)用混合路由策略的路由轉(zhuǎn)換和路由維護過程進行說明。

5.2 路由算法

當(dāng)數(shù)據(jù)分組為MANET節(jié)點創(chuàng)建或由DTN協(xié)議轉(zhuǎn)發(fā)至EHS節(jié)點時，執(zhí)行以下算法。

算法3 基于穩(wěn)定閉域的混合路由（SEHR,stable enclosure based hybrid routing）算法

1) 數(shù)據(jù)分組攜帶節(jié)點發(fā)起AODV路由協(xié)議在連通區(qū)域內(nèi)尋找目的節(jié)點。

2) 同一連通區(qū)域的EHS節(jié)點在收到RREQ請求后，回復(fù)RREP，該RREP分組包含其到目的節(jié)點的相遇概率值。

3) 數(shù)據(jù)分組攜帶節(jié)點若收到目的節(jié)點的RREP回復(fù)，則直接使用AODV路由到目的節(jié)點；否則，比較前一跳DTN鄰居中和發(fā)出RREP回復(fù)的節(jié)點中，與目的節(jié)點的相遇概率。若前者相遇概率高，則轉(zhuǎn)到4)，否則轉(zhuǎn)到5)。

4) 轉(zhuǎn)發(fā)數(shù)據(jù)分組給該DTN節(jié)點，轉(zhuǎn)到6)。

5) 使用AODV路由協(xié)議，以單播方式發(fā)送數(shù)據(jù)分組到回復(fù)RREP的節(jié)點中到目的節(jié)點相遇概率最高的節(jié)點。

6) 轉(zhuǎn)為PROPHET路由。

EHS作為轉(zhuǎn)換網(wǎng)關(guān)，在路由過程中具有DTN節(jié)點的功能，若從DTN節(jié)點中收到數(shù)據(jù)分組，則使用算法3中的路由，在本地尋找快速通路，圖4給出了數(shù)據(jù)分組從攜帶節(jié)點R1，找到中繼節(jié)點R2，并穿越該MANET區(qū)域的過程，這里源節(jié)點為S，目的節(jié)點為D。同時，EHS節(jié)點也是MANET區(qū)域的中繼節(jié)點，當(dāng)其收到本區(qū)域的數(shù)據(jù)分組后，即轉(zhuǎn)入DTN路由，圖5給出了R1作為中繼節(jié)點使用DTN路由轉(zhuǎn)發(fā)數(shù)據(jù)分組的過程。

圖5 DTN到MANET的路由轉(zhuǎn)換

5.3 路由維護

SEHR使用與PROPHET路由相同的投遞概率公式，即當(dāng)節(jié)點u與v相遇時，按如式(1)更新計算節(jié)點u與v的投遞概率。

其中，pinit∈[0…1]是給定的節(jié)點間初始相遇概率。節(jié)點u按式(2)更新其通過v到w的投遞概率。

其中，β是一給定參數(shù)，用于傳遞節(jié)點間的投遞概率權(quán)值。PROPHET路由在每次與其他節(jié)點相遇時會先對自身投遞概率表進行權(quán)值衰退（ageing），之后按照投遞概率公式進行更新。其衰退公式如下。

其中，γ是衰退因子，在PROPHET中取0.98，k為距離上次衰退的總時間與衰退周期的比。PROPHET路由對所有節(jié)點的γ是相同的，這會導(dǎo)致相對移動性較低的相鄰節(jié)點間的投遞概率一直衰退。因此，同一連通MANET區(qū)域內(nèi)節(jié)點間的衰退因子γ被設(shè)置為1，使得相對移動性較低的節(jié)點間不發(fā)生衰退。

由定理1，CCDS作為MANET區(qū)域的統(tǒng)治集，維護了該區(qū)域中的所有節(jié)點的信息，即任意EHS節(jié)點都通過CCDS維護該MANET區(qū)域內(nèi)節(jié)點的相遇概率。再由定義2可知，當(dāng)DTN節(jié)點與該區(qū)域中任意節(jié)點相遇時，必將先與EHS中的節(jié)點相遇?？梢哉J為，數(shù)據(jù)傳輸速度遠大于節(jié)點移動速度。那么，在DTN節(jié)點與MANET區(qū)域邊緣的EHS相遇時，僅由EHS與DTN節(jié)點維護相遇概率，若該MANET區(qū)域內(nèi)存在與目的節(jié)點相遇概率更高的節(jié)點，則由EHS節(jié)點接受該數(shù)據(jù)分組后，以單播MANET（AODV）路由的方式發(fā)送到目的節(jié)點。這樣既減小了PROPHET數(shù)據(jù)分組的冗余轉(zhuǎn)發(fā)，又減小了衰退概率維護的代價。

6 仿真實驗

實驗的主要目的是驗證不同路由算法對DTN副本轉(zhuǎn)發(fā)次數(shù)的控制能力，從而考察節(jié)點轉(zhuǎn)發(fā)緩沖區(qū)出現(xiàn)溢出造成分組丟失后對路由性能產(chǎn)生的影響。為了排除IEEE 802.11協(xié)議在局部密集拓撲環(huán)境下由于沖突造成的分組丟失對實驗結(jié)果的影響（該問題可通過MANET拓撲控制的方法解決不屬于本文討論的范圍），本文選用ONE[18]平臺作為仿真工具，該平臺為路由協(xié)議的仿真提供了理想狀態(tài)的MAC層環(huán)境，即不考慮由于鏈路沖突造成的路由協(xié)議分組丟失問題，因此MANET路由協(xié)議的投遞成功率比非理想環(huán)境增加約23%，DTN部分由于節(jié)點較稀疏，且使用無路由發(fā)現(xiàn)過程的存儲轉(zhuǎn)發(fā)機制，因此只對投遞時延有很小的影響。實驗通過設(shè)置2種大小不同因子緩沖區(qū)對SEHR、HYMAD和DT-DYMO路由進行了性能分析比較。

6.1 仿真環(huán)境設(shè)置

網(wǎng)絡(luò)拓撲被限定在3 000m×3 000m的區(qū)域，該區(qū)域被分為了9個1 000m×1 000m等大的小區(qū)域，每個小區(qū)域內(nèi)MANET節(jié)點的生成限定在距區(qū)域中心(1 000節(jié)點功率半徑)的范圍，以此保證2個相鄰的區(qū)域間MANET節(jié)點不相互連通。MANET區(qū)域節(jié)點平均密度為 1.1～2.2個/10 000m2，以此保證CCDS中節(jié)點的數(shù)量占總MANET節(jié)點數(shù)的50%以下。圖6給出了有4個MANET區(qū)域的拓撲分布示例，其中M1、M2、M3、M4為4個內(nèi)部連通的，但相互間不連通的MANET區(qū)域。圖7給出了真實的實驗場景截圖，實驗中 DTN節(jié)點為全區(qū)域隨機分布，通過逐漸增加MANET節(jié)點所占百分比和改變數(shù)據(jù)緩沖區(qū)大小來測試在不同環(huán)境下路由協(xié)議的性能。

圖6 實驗場景網(wǎng)絡(luò)拓撲示意

表1給出了實驗參數(shù)設(shè)置，從第1 000s開始，平均每隔8s生成一個新數(shù)據(jù)分組。為了保證路由協(xié)議的可比性，HYMAD的簇間路由被設(shè)置為PROPHET，即所比較的 3個路由協(xié)議都以PROPHET作為DTN路由，而PROPHET是一種有條件的多副本傳染路由，因此，數(shù)據(jù)分組緩沖區(qū)的大小對實驗結(jié)果有較大的影響。若緩沖區(qū)足夠大，則可以避免由于緩沖區(qū)滿而導(dǎo)致丟棄數(shù)據(jù)分組后，重復(fù)接收被丟棄數(shù)據(jù)分組而造成的過量洪泛，同時也可以保證投遞成功率和時延。本文提出的路由策略可以在緩沖區(qū)足夠大時降低網(wǎng)絡(luò)負載，在緩沖區(qū)有限時較明顯地提高路由性能。通過設(shè)計在不同緩沖區(qū)情況下的2組實驗，對SEHR的性能進行了驗證。

圖7 實驗場景

表1 實驗參數(shù)

6.2 大緩沖區(qū)實驗

首先，為每個節(jié)點設(shè)置一個足夠大的數(shù)據(jù)分組轉(zhuǎn)發(fā)緩沖區(qū)，設(shè)該緩沖區(qū)大小為bSize，假設(shè)每個數(shù)據(jù)分組副本在產(chǎn)生后，都能夠立刻被傳染到所有節(jié)點上，則任意節(jié)點可能接收到的數(shù)據(jù)分組副本最大個數(shù)n為

其中，eTimemax-eTimemin為仿真過程中，數(shù)據(jù)分組產(chǎn)生的總時間，mNum/( eTimemax-eTimemin)即產(chǎn)生的總數(shù)據(jù)分組數(shù)除以產(chǎn)生數(shù)據(jù)分組的總時間，得到每秒產(chǎn)生數(shù)據(jù)分組的個數(shù)，用數(shù)據(jù)分組的生存時間mTTL乘以每秒產(chǎn)生數(shù)據(jù)分組的個數(shù)得到在同一時刻網(wǎng)絡(luò)中可能存在的數(shù)據(jù)分組的最大個數(shù)，則能夠存放這些數(shù)據(jù)分組的緩沖區(qū)的大小為

把表1數(shù)據(jù)代入式(4)和式(5)，得bSize最大為37.5Mbyte，因此節(jié)點的數(shù)據(jù)分組緩沖區(qū)設(shè)置為40M，使之足夠大。由于在此實驗設(shè)定下，PROPHET的平均投遞時延約為200～300s，遠小于數(shù)據(jù)分組TTL值，這使得3種協(xié)議在性能指標上較為接近，如表2所示。

表2 大緩沖區(qū)實驗結(jié)果數(shù)據(jù)

表2分別給出了不同MANET節(jié)點比例下的投遞成功率、端到端投遞時延和數(shù)據(jù)分組轉(zhuǎn)發(fā)次數(shù)。可以看出，只有SEHR可以隨著MANET區(qū)域的增加而有效地減小冗余轉(zhuǎn)發(fā)次數(shù)，同時在傳輸時延上與其他2種協(xié)議基本一致。DT-DYMO和HYMAD分別在路由的初始簇和目的簇內(nèi)使用 MANET路由。實驗表明，這樣的路由策略并不能隨著MANET節(jié)點數(shù)的增加而明顯降低數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)，雖然MANET節(jié)點總數(shù)增加了，但不同MANET區(qū)域之間并不相連，因此若目的節(jié)點和源節(jié)點不在同一MANET區(qū)域，那么對于DT-DYMO路由就等同于直接執(zhí)行PROPHET，而HYMAD也僅在數(shù)據(jù)分組被傳入目的簇后才能轉(zhuǎn)換為單副本MANET路由，但總體數(shù)據(jù)分組轉(zhuǎn)發(fā)次數(shù)仍然較高。

6.3 小緩沖區(qū)實驗

在實驗中，網(wǎng)絡(luò)拓撲被設(shè)置為4塊相互間不連通的MANET區(qū)域，每塊MANET區(qū)域內(nèi)部是連通的。MANET區(qū)域中的總節(jié)點數(shù)占仿真實驗中全部節(jié)點數(shù)量的60%，另外40%為DTN節(jié)點，這些節(jié)點在整個仿真區(qū)域內(nèi)移動。實驗中，通過不斷改變節(jié)點數(shù)據(jù)分組轉(zhuǎn)發(fā)緩沖區(qū)的大小，來比較不同路由協(xié)議的性能。

圖8 數(shù)據(jù)分組投遞成功率

圖9 端到端時延

圖10 數(shù)據(jù)分組轉(zhuǎn)發(fā)次數(shù)

圖8～圖10分別給出了相同比例MANET節(jié)點，不同緩沖區(qū)大小的情況下的投遞成功率、投遞時延和數(shù)據(jù)分組轉(zhuǎn)發(fā)次數(shù)。比較3種路由策略，能夠自適應(yīng)地進行路由策略轉(zhuǎn)換的 SEHR充分利用了MANET路由轉(zhuǎn)發(fā)次數(shù)少的特點，在網(wǎng)絡(luò)局部的MANET連通區(qū)域內(nèi)轉(zhuǎn)換為MANET路由，從而在數(shù)據(jù)分組轉(zhuǎn)發(fā)緩沖區(qū)減小時仍然能夠保持較高的路由性能。

6.4 實驗結(jié)果分析

在大緩沖實驗及不考慮MAC層沖突分組丟失的理想狀態(tài)下，由于節(jié)點的轉(zhuǎn)發(fā)緩沖區(qū)足夠大，使得基于傳染策略傳輸?shù)?DTN路由階段在移動性較小的MANET連通區(qū)域內(nèi)傳輸?shù)亩说蕉送哆f時延和成功率與 AODV基本相同。但是，隨著 MANET節(jié)點比例的增加，基于多副本的PROPHET路由將產(chǎn)生數(shù)倍于AODV的轉(zhuǎn)發(fā)次數(shù)，這不僅消耗大量的網(wǎng)絡(luò)計算資源，也會在真實環(huán)境中由于MAC層沖突而大量產(chǎn)生分組丟失。因此，在MOD的混合拓撲結(jié)構(gòu)中，需要明確定義路由策略的轉(zhuǎn)換條件，以確保進入MANET連通區(qū)域后，能盡量采用單副本方式的MANET路由，限制DTN在MANET區(qū)域內(nèi)的多副本傳染，DT-DYMO路由并沒有很好地解決這一問題。HYMAD雖然定義了明確的轉(zhuǎn)發(fā)邊界，即節(jié)點簇，但是其分簇算法在完全分布式環(huán)境下具有一定的可行性問題，因此，在本文中采用的是直接指定MANET區(qū)域為一個簇的方法。

在小緩沖實驗中，由于采用了小數(shù)據(jù)分組轉(zhuǎn)發(fā)緩沖區(qū)的設(shè)置，使得在冗余數(shù)據(jù)分組的數(shù)量增加后，轉(zhuǎn)發(fā)緩沖區(qū)很快被填滿，在這種情況下，不斷接收的新數(shù)據(jù)分組就導(dǎo)致大量未來得及轉(zhuǎn)發(fā)的存儲在緩沖區(qū)中的數(shù)據(jù)分組被丟棄，丟棄未成功轉(zhuǎn)發(fā)的數(shù)據(jù)分組還會造成該數(shù)據(jù)分組的重復(fù)傳染，更加重了網(wǎng)絡(luò)的負載。本文提出的SEHR混合路由策略，通過自適應(yīng)地轉(zhuǎn)換為 MANET路由，減少了 DTN階段參與路由的節(jié)點的數(shù)量，同時也通過MANET階段的路由減小了數(shù)據(jù)分組副本的產(chǎn)生數(shù)量和轉(zhuǎn)發(fā)次數(shù)，從而很好地釋放了多副本協(xié)議對數(shù)據(jù)轉(zhuǎn)發(fā)緩沖區(qū)的壓力，有效地提高了路由的性能。

考慮到對各種拓撲情況的兼容性，由于可能存在節(jié)點移動性不強的網(wǎng)絡(luò)環(huán)境，因此，本文所提出的路由策略在 DTN階段主要適用于以多副本傳染為主要策略路由協(xié)議。對于依靠節(jié)點的移動性來傳遞攜帶的數(shù)據(jù)分組，以減小轉(zhuǎn)發(fā)的如噴霧等待（spray-and-wait）這類DTN路由并不適用。

綜上所述，SEHR通過按需的局部MANET路由減小 DTN的多副本數(shù)據(jù)分組復(fù)制策略造成的洪泛，在高網(wǎng)絡(luò)負載的情況下有效地抑制了由于轉(zhuǎn)發(fā)緩沖區(qū)被填滿引起分組丟失所造成的路由性能下降的問題。同時，在MANET路由發(fā)現(xiàn)失效的情況下，SEHR能夠按需的轉(zhuǎn)換為DTN路由以保證路由過程不會因為暫時無法找到端到端路由而中斷。因此，SEHR是一種非常適合在高流量的、變化的、混合的、復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)下使用的路由策略。但SEHR同時也存在一定的缺陷，由于穩(wěn)定閉域的邊界節(jié)點需要同時維護2種路由協(xié)議，因此其節(jié)點成本較高，也會在工作時消耗較高的能量，可能導(dǎo)致節(jié)點電量較早耗盡，成為網(wǎng)絡(luò)的瓶頸，因此SEHR在實際應(yīng)用中還需要進一步改進以減小閉域邊界節(jié)點的能量消耗，避免其過早失效。

7 結(jié)束語

本文提出了一種基于MANET轉(zhuǎn)發(fā)閉域的，可應(yīng)用于混合異構(gòu)網(wǎng)絡(luò)拓撲場景中的混合路由策略。該路由策略通過當(dāng)前攜帶數(shù)據(jù)分組節(jié)點所在網(wǎng)絡(luò)拓撲的本地信息自適應(yīng)地選擇MANET或DTN路由協(xié)議，以充分發(fā)揮MANET路由相對的高性能和DTN路由的高容錯的特點。通過構(gòu)建基于MANET閉域的連通統(tǒng)治集使得 DTN路由可以感知網(wǎng)絡(luò)中所有節(jié)點，利用閉域內(nèi)的MANET路由降低數(shù)據(jù)分組在整個路由轉(zhuǎn)發(fā)過程中的冗余副本數(shù)量，并在局部提高了端到端的投遞性能，同時也有效降低了DTN路由的維護成本。通過實驗證明了在復(fù)雜的異構(gòu)網(wǎng)絡(luò)拓撲環(huán)境中，當(dāng)網(wǎng)絡(luò)中產(chǎn)生的流量較高時，本文提出的路由策略相對于不能自適應(yīng)路由轉(zhuǎn)換的混合路由策略具有更好的適應(yīng)性和更高的性能。進一步的研究目標是擴展SEHR路由策略對其他性能更高的 DTN路由協(xié)議的兼容能力，以在更加復(fù)雜的網(wǎng)絡(luò)拓撲環(huán)境中提供更高效的路由轉(zhuǎn)發(fā)能力。

[1] RFC 3561[EB/OL]. http://tools.ietf.org/html/rfc3561.

[2] RFC 4782[EB/OL]. http://tools.ietf.org/html/rfc4782.

[3] PERKINS C E, BHAWAT P. Highly dynamic destination-sequenced distance vector routing (DSDV) for mobile computers[A]. Proceedings of the Conference on Communications Architectures, SIGCOMM'94[C]. New York, NY, USA, 1994. 234-244.

[4] BLUM J, ESKANDARIAN A, HOFFMAN L J. Performance characteristics of inter-vehicle ad hoc networks[A]. Proceedings of the 6th IEEE International Conference on Intelligent Transportation Systems[C]. Shanghay, China, 2003. 114-119.

[5] JUANG P, OKI H, WANG Y, et al. Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with Zebra-Net[A]. Proceeding ASPLOS-X Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems[C]. New York, NY, USA, 2002. 96-107.

[6] VAHDAT, BECKER D. Epidemic Routing for Partially Connected Ad hoc Networks[R]. Tech Rep CS-2000-06, Department of Computer Science, Duke University, Durham, NC, 2000.

[7] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks[A]. Proceedings of the ACM SIGCOMM 2005 Workshop on Delay Tolerant Networks[C]. Philadelphia, PA, USA, 2005. 22-26.

[8] SU J, CHIN A, POPIVANOVA A, et al. User mobility for opportunistic ad hoc networking[A]. Proceedings of the 6th IEEE Workshop on Mobile Computing System and Applications (WMCSA)[C]. UK, 2004.

[9] PENTLAND A, FLETCHER R, HASSON A. DakNet: rethinking connectivity in developing nations[J]. IEEE Computer, 2004, 37(1):78-83.

[10] OTT J, KUTSCHER D, DWERTMANN C. Integrating DTN and MANET routing[A]. CHANTS ’06: Proceedings of the 2006 SIGCOMM Workshop on Challenged Networks[C]. 2006. 221-228.

[11] KRETSCHMER C, RüHRUP S, SCHINDELHAUER C. DT-DYMO:delay-tolerant dynamic MANET on-demand routing[A]. The 29th IEEE International Conference on Distributed Computing Systems Workshops[C]. Montreal, Quebec, Canada, 2009.493-498.

[12] CHAKERES I, PERKINS C. Dynamic MANET on-demand (DYMO)Routing[S]. IETF Internet Draft, draft-ietf-manet-dymo-14, 2008.

[13] JOHN W, VANIA C.HYMAD: hybrid DTN-MANET routing for dense and highly dynamic wireless networks[J]. Computer Communications, 2010, 33(13): 1483-1492.

[14] ESPOSITO F, MATTA I. PreDA: predicate routing for DTN architectures over MANET[A]. Proceedings of the 28th IEEE Conference on Global Telecommunications, GLOBECOM'09 [C]. 2009. 5018- 5023.

[15] SAMUEL H, ZHUANG W H, PREISS B. DTN based dominating set routing for MANET in heterogeneous wireless networking[J]. Mobile Networks and Applications, 2009, 14(2): 154-164.

[16] PANT R, TUNPAN A, MEKBUNGWAN P, et al. DTN overlay on OLSR network[A]. Proceedings of the Sixth Asian Internet Engineering Conference, AINTEC '10[C]. Bangkok, Thailand, 2010. 56-63.

[17] WU J, LI H. On calculating connected dominating set for efficient routing in ad hoc wireless networks[A]. Proceedings of the 30th Annual International Conference on Parallel Processing[C]. Valencia,Spain, 2001.

[18] KER?NEN A, OTT J, K?RKK?INEN T. The ONE simulator for DTN protocol evaluation[A]. SIMUTools ’09: Proceedings of the 2nd International Conference on Simulation Tools and Techniques[C].New York, NY, USA, 2009.