基于穩定閉域的異構無線網絡混合路由策略

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

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

1 引言

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

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

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

2 相關工作

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

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

3 網絡模型

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

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

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

定義1是基于MOD模型給出的網絡拓撲模型定義，當n=1時，就轉變為DOM模型。在定義中，每一個GM都是一個連通的拓撲穩定的MANET區域，當節點發起一次路由時，通常認為會穿過多個這樣的區域，這就需要路由策略能夠根據本地局部拓撲信息自適應地選擇使用最合適的路由算法，以達到最高的性能。而文獻[10,11,13]中所給出的只轉換一次路由算法的策略顯然不能在該網絡拓撲模型中達到最優的性能。

4 穩定閉域

4.1 穩定閉域的定義及算法

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

圖1 穩定閉域

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

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

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

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

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

1) 對該區域內任意節點u，令其與Nbr2( u)中節點交換位置信息。

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

4.2 基于穩定閉域的限定連通統治集

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

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

1) 執行算法1，若節點u∈EHS，則把u加入CCDS。

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

3) 設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的 關系；

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是連通的，且所有節點或在CCDS上或被CCDS所統治。

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

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

圖2 CCDS拓撲

圖3 CCDS節點數占總節點數比例

5 基于穩定閉域的混合路由策略

5.1 混合路由策略

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

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

1) 每個節點基于鄰居行為對自身性質進行判定，區分MANET與DTN。

2) MANET節點分別執行算法1和算法2確定自己在網絡中的路由角色。

3) 節點根據路由角色執行相應路由協議。

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

5.2 路由算法

當數據分組為MANET節點創建或由DTN協議轉發至EHS節點時，執行以下算法。

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

1) 數據分組攜帶節點發起AODV路由協議在連通區域內尋找目的節點。

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

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

4) 轉發數據分組給該DTN節點，轉到6)。

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

6) 轉為PROPHET路由。

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

圖5 DTN到MANET的路由轉換

5.3 路由維護

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

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

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

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

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

6 仿真實驗

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

6.1 仿真環境設置

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

圖6 實驗場景網絡拓撲示意

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

圖7 實驗場景

表1 實驗參數

6.2 大緩沖區實驗

首先，為每個節點設置一個足夠大的數據分組轉發緩沖區，設該緩沖區大小為bSize，假設每個數據分組副本在產生后，都能夠立刻被傳染到所有節點上，則任意節點可能接收到的數據分組副本最大個數n為

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

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

表2 大緩沖區實驗結果數據

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

6.3 小緩沖區實驗

在實驗中，網絡拓撲被設置為4塊相互間不連通的MANET區域，每塊MANET區域內部是連通的。MANET區域中的總節點數占仿真實驗中全部節點數量的60%，另外40%為DTN節點，這些節點在整個仿真區域內移動。實驗中，通過不斷改變節點數據分組轉發緩沖區的大小，來比較不同路由協議的性能。

圖8 數據分組投遞成功率

圖9 端到端時延

圖10 數據分組轉發次數

圖8～圖10分別給出了相同比例MANET節點，不同緩沖區大小的情況下的投遞成功率、投遞時延和數據分組轉發次數。比較3種路由策略，能夠自適應地進行路由策略轉換的 SEHR充分利用了MANET路由轉發次數少的特點，在網絡局部的MANET連通區域內轉換為MANET路由，從而在數據分組轉發緩沖區減小時仍然能夠保持較高的路由性能。

6.4 實驗結果分析

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

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

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

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

7 結束語

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

[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.