保證高可靠度和低傳輸開銷的DTN拓撲控制

齊小剛，馬久龍，劉立芳

(1. 西安電子科技大學 數學與統計學院，陜西 西安 710071；2. 西安電子科技大學 計算機學院，陜西 西安 710071)

時延容忍網絡是為設計星際互聯網而被研究和發展的，但目前已被擴展到其他領域，其特點是節點持續運動、拓撲時變、鏈路間歇連通[1-2]．尤其是以衛星網絡作為骨干網的空間信息網絡[3]，衛星節點周期性移動，網絡還面臨隨機的節點和鏈路失效問題[4-5]．研究表明，適用于時延容忍網絡的許多方案也適用于衛星網絡[6-7]．在拓撲周期性變化的時延容忍網絡中，基于時間片[8-9]的方案被廣泛使用．該方案將網絡的周期分割為離散的時間片，在每個時間片內拓撲可視為固定的，這使得一個時間片中只有當兩個節點存在端到端路徑時，數據才可以正常傳輸，忽略了時間片間的聯系．文獻[10]基于連通時序實現了深空網絡的最大吞吐量，文獻[11]在時間片的基礎上提出了幾種有效的拓撲控制方案，這些方法都假定了鏈路是完全可靠的．然而，空間網絡節點間的鏈路在大多數情況下不是完全可靠的，且節點存儲受限．

針對這些問題，筆者基于時空圖模型，提出了新的適用于拓撲周期性變化的時延容忍網絡的拓撲控制方案．它在保證網絡連通的條件下，旨在尋找原時空圖的一個稀疏子圖，該稀疏子圖能夠滿足任意節點對之間的路徑的可靠性，同時降低了網絡的傳輸開銷．

圖1 一個時延容忍網絡的序列圖示例

1 網絡模型和相關定義

1.1 網絡模型

假設由6個節點組成的時延容忍網絡(Delay Tolerant Network，DTN)，如圖1所示，節點分別為一個地面節點T1、兩個低軌道衛星節點L1和L2、兩個中軌道衛星M1和M2以及一個靜止衛星G1．在t0至t1時間段內，節點之間的連接關系是固定的，即拓撲是固定不變的，稱該時間段為一個時隙，即時隙1; 在t1時刻，部分節點之間的連接關系發生了變化，即拓撲出現了新的狀態，t1～t2時間段內網絡維持新的狀態，則t1至t2的時間段為一個新的時隙，即時隙2; 在t2時刻，節點之間的連接關系再次發生變化．依此類推，網絡在一個周期可能出現圖1所示的幾種拓撲狀態．

按此方法將網絡的系統周期T劃分為n個時隙s1，s2，…，sn．用V表示網絡的m個節點組成的集合，V= {v1，v2，…，vm}；Gs= (Vs，Es)，表示網絡在時隙s時的拓撲．其中Vs和Es分別為網絡在時隙s時的節點和鏈路集合，則網絡在周期T的拓撲可表示為G= {Gs|s=s1，s2，…，sn}，它可以完整準確地描述網絡的拓撲．但這樣的離散序列很難進行拓撲控制和路由設計，因為在某些時隙內，網絡并不連通，如圖1中的時隙3、時隙4和時隙5，此時，L1和L2無法和T1通信．因此，直接將靜態圖序列用在時延容忍網絡是不合適的．現考慮使用時空圖來模擬網絡的拓撲．將一系列的靜態圖轉化為時空圖，為此將任意兩個時隙上的任意兩個節點看成是不同的．

1.2 相關定義

定義1(時空圖) 若時延容忍網絡的拓撲表示為G={Gs|s=s1，s2，…，sn}，其中Gs= (Vs，Es)，為網絡在時隙s時的拓撲，則G的時空圖被定義為一個有向圖GTS= (V，E，T)，其中:

(2)E是時空圖的有向鏈路的集合，有向鏈路指的是時間鏈路和空間鏈路，分別定義如下．

圖2 時空圖的一個示例

(3)T是網絡的系統周期．

通過定義時空圖，任意兩個節點間的通信可在時空圖上表示．例如，若T1在t0時刻想發數據給M2，它可能采取的方式是先攜帶數據至t1時刻，在時隙2內，T1將數據轉發給L1，在時隙3內L1轉發數據給L2，在時隙4內L2轉發數據給M1，最后在時隙5內，M1將數據轉發給M2．

實際上網絡節點間在傳輸數據時會有一定的傳輸開銷．因此，給時空圖的每一條鏈路賦予一個權值來代表傳輸開銷．時間鏈路上的權值代表節點在一個時間段攜帶數據的開銷．類似于衛星網絡的時延容忍網絡一般運行在極其復雜的空間環境中，衛星及星間鏈路在任意時刻都可能發生故障，甚至遭受人為攻擊．筆者考慮衛星節點失效和鏈路故障的情形．賦予時空圖中的有向鏈路e一個介于0到1之間的實數r(e)來表示該鏈路的可靠性，稱r(e)為鏈路e的可靠度．對于時間鏈路，r(e)表征節點緩存和攜帶數據的成功率．當節點緩存不夠時，數據會被丟失．例如在衛星網絡中，軌內星間鏈路的可靠度比軌間星間鏈路的可靠度更高; 層間鏈路的可靠度比層內的星間鏈路可靠度低．此外，時間鏈路比空間鏈路的可靠度高．

定義2(賦權時空圖) 稱G=(V，E，c，r)為賦權時空圖，其中V為時空圖的節點集合;E為時空圖的鏈路集合;c為定義在E上的正實值函數，即c:E→R+，稱c為開銷函數;r為定義在E上取值在[0，1]之間的函數，即r:E→ [0，1]，稱r為可靠度函數．

定義5(路徑的可靠度和最可靠路徑) 在時空圖G中，一個從節點u到節點v的路徑P(u，v)的可靠度是指該路徑上所有鏈路的可靠度的乘積．從u到v的最可靠路徑是指從節點u到節點v的所有路徑中可靠度最高的路徑．

2 可靠拓撲控制問題

可靠拓撲控制問題可以被描述如下．給定一個連通的賦權時空圖G=(V，E，c，r)，拓撲控制的目的是找到一個稀疏時空子圖H(V′，E′，c，r)，使其滿足:V′=V;H在一個周期T上是連通的;H中任意節點對之間的路徑的可靠度最高;子圖H的傳輸開銷c(H)最小．

要保證網絡任意節點對之間的路徑的高可靠度和子圖的低傳輸開銷是極其困難的．為使問題簡化，假定在每條鏈路上的傳輸開銷是相等的，筆者提出兩個有效的啟發式算法解決了該問題．

3 相關算法

解決上面問題的思路是在構造的原始時空圖G中尋找各個節點對之間可靠度較高的路徑．可以將時空圖G中所有節點對之間的最可靠路徑添加到子圖H．顯然，生成的子圖H能夠滿足網絡的可靠需求．為此，首先將所有鏈路的可靠度值取負對數，然后使用Dijkstra算法．算法1顯示了詳細過程．

算法1 最可靠路徑聯合算法．

輸入：原網絡的序列圖{Gs}．

輸出：時空子圖H．

算法2 最可靠路徑的貪婪算法．

輸入：原網絡的序列圖{Gs}．

輸出：時空子圖H．

算法1為了滿足節點對之間數據傳輸的可靠性條件，以最簡單的方式向子圖中添加最可靠路徑．盡管它能夠滿足可靠條件，但是添加了過多不必要的鏈路，不能大幅度降低網絡的傳輸開銷．算法2通過逐次加入最可靠路徑，進一步降低了網絡的傳輸開銷，同時保證網絡具有一定的可靠性．若用N表示問題的規模，由于時空圖最多有n+1 層，所以節點個數為N(n+1)，邊的個數最多為nN2．在時空圖上運行N次Dijkstra算法，算法1的時間復雜度為N2O(nN+nlog(nN))=O(nN3+nN2log(nN))．同理，算法2的時間復雜度為N2O(nN3+nN2log(nN))=O(nN5+nN4log(nN))．

4 性能評估

拓撲控制的目的是為了構建一個滿足任意節點對之間數據傳輸有可靠性保證的稀疏拓撲，并降低網絡的傳輸開銷．仿真采用兩種度量來衡量提出算法的性能：一是稀疏時空子圖H的傳輸開銷與原時空圖G的傳輸開銷的比值，即傳輸開銷比；二是時空子圖H的平均可靠度．網絡的鏈路開銷越小，可靠度越高，表征拓撲控制算法越有效．

為了模擬真實時延容忍網絡的拓撲，采用經典的隨機圖產生器來模擬產生網絡的離散時隙拓撲集G= {Gs|s=s1，s2，…，sn}．設定任意兩個節點間存在鏈路的概率為p，p的大小表明了網絡鏈路的稀疏程度，稱p為鏈路密度．仿真中隨機產生具有10個節點的6個離散序列圖，每條鏈路的可靠度值服從0.8到1.0的均勻分布．設定p的值在0.5到1之間變化，并假定每條鏈路的傳輸開銷相等．仿真隨機產生500組滿足條件的序列圖，并統計網絡的平均性能．

圖3(a)顯示了網絡的傳輸開銷比隨著鏈路密度的變化情況．從圖3(a)中知，兩種算法都能在網絡連通時，保證端到端路徑的高可靠度，并能有效地降低網絡的傳輸開銷，且鏈路密度越大，算法節省的傳輸開銷就越多．另外，從網絡鏈路的傳輸開銷考慮，算法2比算法1更優，原因是算法1只是簡單地向時空圖中添加了最可靠路徑，可能會導致添加一些不必要的鏈路．圖3(b)顯示了平均可靠度隨著鏈路密度變化的情況．隨著鏈路密度的增加，兩種算法下的可靠度都有所提高．另外，算法1得到的平均可靠度略高，因為算法1添加了所有節點對之間的最可靠路徑．

圖3 網絡傳輸開銷比和平均可靠度隨鏈路密度的變化曲線

為了獲得時隙個數對傳輸開銷比和平均可靠度的影響，固定鏈路密度p=0.8，保持其他仿真參數不變，統計網絡具有不同時隙個數時的性能．圖4(a)顯示了傳輸開銷比隨時隙數目變化的關系．兩種算法的傳輸開銷比都隨著時隙數量的增大而下降，這表明時隙數目越多，越能體現兩種算法在傳輸開銷方面的有效性，且算法2體現的更加明顯．圖4(b)顯示了平均可靠度隨時隙數目變化的關系．可以看出，兩種算法的網絡的平均可靠度呈現下降趨勢，這是因為隨著時隙數目的增多，網絡拓撲表現出較強的間歇連通特征，使得數據傳輸可靠性下降．由于算法1中含有最高可靠度的路徑，所以較算法2可靠度更高．

圖4 網絡傳輸開銷比和平均可靠度隨時隙數目的變化曲線

固定鏈路密度p=0.8，時隙數量為6，保持其他仿真參數不變，統計網絡具有不同節點數目時的性能．圖5(a)顯示了傳輸開銷比隨節點數目的變化關系．兩種算法的傳輸開銷比都隨著節點數目的增大而下降，這表明了節點數目越多，越能體現兩種算法在傳輸開銷方面的有效性，且算法2體現的更加明顯．圖5(b)顯示了平均可靠度隨時隙數目變化的關系．兩種算法的平均可靠度隨著節點數目的增多而變大，因為當網絡節點數目增大時，在鏈路密度一定的情況下，鏈路數量相對較多，節點對間更有機會選擇可靠性高的路徑，且算法1具有更高的可靠性．

圖5 網絡傳輸開銷比和平均可靠度隨節點數目的變化曲線

綜上，相比原網絡來說，在保證網絡連通的情況下，兩種算法都能保證數據傳輸的可靠性，同時降低網絡的傳輸開銷．算法1在可靠度方面比算法2略顯優勢，而算法2比算法1在傳輸開銷方面略顯優勢．

5 結 束 語

時延容忍網絡的節點和鏈路動態性為拓撲控制帶來挑戰．筆者基于拓撲周期性可預測的時延容忍網絡，首先將網絡的拓撲結構轉化為時空圖，進而定義了可靠拓撲控制問題．針對此問題，提出了兩種有效的拓撲控制方案．拓撲控制的目的是在不破壞網絡連通性的條件下保證網絡的可靠性和降低網絡的傳輸開銷．最后，仿真驗證了提出的方法的有效性．網絡拓撲的性能會對網絡路由和數據傳輸產生影響，在拓撲控制的基礎上，性能優越的路由技術應該被設計．因此，在未來的工作中，路由的研究將是一個重要話題．