保證高可靠度和低傳輸開銷的DTN拓?fù)淇刂?/h1>
2018-10-11 12:32齊小剛馬久龍劉立芳
西安電子科技大學(xué)學(xué)報 2018年5期
齊小剛，馬久龍，劉立芳
(1. 西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，陜西 西安 710071；2. 西安電子科技大學(xué) 計算機學(xué)院，陜西 西安 710071)
時延容忍網(wǎng)絡(luò)是為設(shè)計星際互聯(lián)網(wǎng)而被研究和發(fā)展的，但目前已被擴展到其他領(lǐng)域，其特點是節(jié)點持續(xù)運動、拓?fù)鋾r變、鏈路間歇連通[1-2]．尤其是以衛(wèi)星網(wǎng)絡(luò)作為骨干網(wǎng)的空間信息網(wǎng)絡(luò)[3]，衛(wèi)星節(jié)點周期性移動，網(wǎng)絡(luò)還面臨隨機的節(jié)點和鏈路失效問題[4-5]．研究表明，適用于時延容忍網(wǎng)絡(luò)的許多方案也適用于衛(wèi)星網(wǎng)絡(luò)[6-7]．在拓?fù)渲芷谛宰兓臅r延容忍網(wǎng)絡(luò)中，基于時間片[8-9]的方案被廣泛使用．該方案將網(wǎng)絡(luò)的周期分割為離散的時間片，在每個時間片內(nèi)拓?fù)淇梢暈楣潭ǖ?，這使得一個時間片中只有當(dāng)兩個節(jié)點存在端到端路徑時，數(shù)據(jù)才可以正常傳輸，忽略了時間片間的聯(lián)系．文獻(xiàn)[10]基于連通時序?qū)崿F(xiàn)了深空網(wǎng)絡(luò)的最大吞吐量，文獻(xiàn)[11]在時間片的基礎(chǔ)上提出了幾種有效的拓?fù)淇刂品桨?，這些方法都假定了鏈路是完全可靠的．然而，空間網(wǎng)絡(luò)節(jié)點間的鏈路在大多數(shù)情況下不是完全可靠的，且節(jié)點存儲受限．
針對這些問題，筆者基于時空圖模型，提出了新的適用于拓?fù)渲芷谛宰兓臅r延容忍網(wǎng)絡(luò)的拓?fù)淇刂品桨福诒ＷC網(wǎng)絡(luò)連通的條件下，旨在尋找原時空圖的一個稀疏子圖，該稀疏子圖能夠滿足任意節(jié)點對之間的路徑的可靠性，同時降低了網(wǎng)絡(luò)的傳輸開銷．
圖1 一個時延容忍網(wǎng)絡(luò)的序列圖示例
1 網(wǎng)絡(luò)模型和相關(guān)定義
1.1 網(wǎng)絡(luò)模型
假設(shè)由6個節(jié)點組成的時延容忍網(wǎng)絡(luò)(Delay Tolerant Network，DTN)，如圖1所示，節(jié)點分別為一個地面節(jié)點T1、兩個低軌道衛(wèi)星節(jié)點L1和L2、兩個中軌道衛(wèi)星M1和M2以及一個靜止衛(wèi)星G1．在t0至t1時間段內(nèi)，節(jié)點之間的連接關(guān)系是固定的，即拓?fù)涫枪潭ú蛔兊?，稱該時間段為一個時隙，即時隙1; 在t1時刻，部分節(jié)點之間的連接關(guān)系發(fā)生了變化，即拓?fù)涑霈F(xiàn)了新的狀態(tài)，t1～t2時間段內(nèi)網(wǎng)絡(luò)維持新的狀態(tài)，則t1至t2的時間段為一個新的時隙，即時隙2; 在t2時刻，節(jié)點之間的連接關(guān)系再次發(fā)生變化．依此類推，網(wǎng)絡(luò)在一個周期可能出現(xiàn)圖1所示的幾種拓?fù)錉顟B(tài)．
按此方法將網(wǎng)絡(luò)的系統(tǒng)周期T劃分為n個時隙s1，s2，…，sn．用V表示網(wǎng)絡(luò)的m個節(jié)點組成的集合，V= {v1，v2，…，vm}；Gs= (Vs，Es)，表示網(wǎng)絡(luò)在時隙s時的拓?fù)洌渲蠽s和Es分別為網(wǎng)絡(luò)在時隙s時的節(jié)點和鏈路集合，則網(wǎng)絡(luò)在周期T的拓?fù)淇杀硎緸镚= {Gs|s=s1，s2，…，sn}，它可以完整準(zhǔn)確地描述網(wǎng)絡(luò)的拓?fù)洌@樣的離散序列很難進(jìn)行拓?fù)淇刂坪吐酚稍O(shè)計，因為在某些時隙內(nèi)，網(wǎng)絡(luò)并不連通，如圖1中的時隙3、時隙4和時隙5，此時，L1和L2無法和T1通信．因此，直接將靜態(tài)圖序列用在時延容忍網(wǎng)絡(luò)是不合適的．現(xiàn)考慮使用時空圖來模擬網(wǎng)絡(luò)的拓?fù)洌畬⒁幌盗械撵o態(tài)圖轉(zhuǎn)化為時空圖，為此將任意兩個時隙上的任意兩個節(jié)點看成是不同的．
1.2 相關(guān)定義
定義1(時空圖) 若時延容忍網(wǎng)絡(luò)的拓?fù)浔硎緸镚={Gs|s=s1，s2，…，sn}，其中Gs= (Vs，Es)，為網(wǎng)絡(luò)在時隙s時的拓?fù)洌瑒tG的時空圖被定義為一個有向圖GTS= (V，E，T)，其中:
(2)E是時空圖的有向鏈路的集合，有向鏈路指的是時間鏈路和空間鏈路，分別定義如下．
圖2 時空圖的一個示例
(3)T是網(wǎng)絡(luò)的系統(tǒng)周期．
通過定義時空圖，任意兩個節(jié)點間的通信可在時空圖上表示．例如，若T1在t0時刻想發(fā)數(shù)據(jù)給M2，它可能采取的方式是先攜帶數(shù)據(jù)至t1時刻，在時隙2內(nèi)，T1將數(shù)據(jù)轉(zhuǎn)發(fā)給L1，在時隙3內(nèi)L1轉(zhuǎn)發(fā)數(shù)據(jù)給L2，在時隙4內(nèi)L2轉(zhuǎn)發(fā)數(shù)據(jù)給M1，最后在時隙5內(nèi)，M1將數(shù)據(jù)轉(zhuǎn)發(fā)給M2．
實際上網(wǎng)絡(luò)節(jié)點間在傳輸數(shù)據(jù)時會有一定的傳輸開銷．因此，給時空圖的每一條鏈路賦予一個權(quán)值來代表傳輸開銷．時間鏈路上的權(quán)值代表節(jié)點在一個時間段攜帶數(shù)據(jù)的開銷．類似于衛(wèi)星網(wǎng)絡(luò)的時延容忍網(wǎng)絡(luò)一般運行在極其復(fù)雜的空間環(huán)境中，衛(wèi)星及星間鏈路在任意時刻都可能發(fā)生故障，甚至遭受人為攻擊．筆者考慮衛(wèi)星節(jié)點失效和鏈路故障的情形．賦予時空圖中的有向鏈路e一個介于0到1之間的實數(shù)r(e)來表示該鏈路的可靠性，稱r(e)為鏈路e的可靠度．對于時間鏈路，r(e)表征節(jié)點緩存和攜帶數(shù)據(jù)的成功率．當(dāng)節(jié)點緩存不夠時，數(shù)據(jù)會被丟失．例如在衛(wèi)星網(wǎng)絡(luò)中，軌內(nèi)星間鏈路的可靠度比軌間星間鏈路的可靠度更高; 層間鏈路的可靠度比層內(nèi)的星間鏈路可靠度低．此外，時間鏈路比空間鏈路的可靠度高．
定義2(賦權(quán)時空圖) 稱G=(V，E，c，r)為賦權(quán)時空圖，其中V為時空圖的節(jié)點集合;E為時空圖的鏈路集合;c為定義在E上的正實值函數(shù)，即c:E→R+，稱c為開銷函數(shù);r為定義在E上取值在[0，1]之間的函數(shù)，即r:E→ [0，1]，稱r為可靠度函數(shù)．
定義5(路徑的可靠度和最可靠路徑) 在時空圖G中，一個從節(jié)點u到節(jié)點v的路徑P(u，v)的可靠度是指該路徑上所有鏈路的可靠度的乘積．從u到v的最可靠路徑是指從節(jié)點u到節(jié)點v的所有路徑中可靠度最高的路徑．
2 可靠拓?fù)淇刂茊栴}
可靠拓?fù)淇刂茊栴}可以被描述如下．給定一個連通的賦權(quán)時空圖G=(V，E，c，r)，拓?fù)淇刂频哪康氖钦业揭粋€稀疏時空子圖H(V′，E′，c，r)，使其滿足:V′=V;H在一個周期T上是連通的;H中任意節(jié)點對之間的路徑的可靠度最高;子圖H的傳輸開銷c(H)最?。?/p>
要保證網(wǎng)絡(luò)任意節(jié)點對之間的路徑的高可靠度和子圖的低傳輸開銷是極其困難的．為使問題簡化，假定在每條鏈路上的傳輸開銷是相等的，筆者提出兩個有效的啟發(fā)式算法解決了該問題．
3 相關(guān)算法
解決上面問題的思路是在構(gòu)造的原始時空圖G中尋找各個節(jié)點對之間可靠度較高的路徑．可以將時空圖G中所有節(jié)點對之間的最可靠路徑添加到子圖H．顯然，生成的子圖H能夠滿足網(wǎng)絡(luò)的可靠需求．為此，首先將所有鏈路的可靠度值取負(fù)對數(shù)，然后使用Dijkstra算法．算法1顯示了詳細(xì)過程．
算法1 最可靠路徑聯(lián)合算法．
輸入：原網(wǎng)絡(luò)的序列圖{Gs}．
輸出：時空子圖H．
算法2 最可靠路徑的貪婪算法．
輸入：原網(wǎng)絡(luò)的序列圖{Gs}．
輸出：時空子圖H．
算法1為了滿足節(jié)點對之間數(shù)據(jù)傳輸?shù)目煽啃詶l件，以最簡單的方式向子圖中添加最可靠路徑．盡管它能夠滿足可靠條件，但是添加了過多不必要的鏈路，不能大幅度降低網(wǎng)絡(luò)的傳輸開銷．算法2通過逐次加入最可靠路徑，進(jìn)一步降低了網(wǎng)絡(luò)的傳輸開銷，同時保證網(wǎng)絡(luò)具有一定的可靠性．若用N表示問題的規(guī)模，由于時空圖最多有n+1 層，所以節(jié)點個數(shù)為N(n+1)，邊的個數(shù)最多為nN2．在時空圖上運行N次Dijkstra算法，算法1的時間復(fù)雜度為N2O(nN+nlog(nN))=O(nN3+nN2log(nN))．同理，算法2的時間復(fù)雜度為N2O(nN3+nN2log(nN))=O(nN5+nN4log(nN))．
4 性能評估
拓?fù)淇刂频哪康氖菫榱藰?gòu)建一個滿足任意節(jié)點對之間數(shù)據(jù)傳輸有可靠性保證的稀疏拓?fù)?，并降低網(wǎng)絡(luò)的傳輸開銷．仿真采用兩種度量來衡量提出算法的性能：一是稀疏時空子圖H的傳輸開銷與原時空圖G的傳輸開銷的比值，即傳輸開銷比；二是時空子圖H的平均可靠度．網(wǎng)絡(luò)的鏈路開銷越小，可靠度越高，表征拓?fù)淇刂扑惴ㄔ接行В?/p>
為了模擬真實時延容忍網(wǎng)絡(luò)的拓?fù)?，采用?jīng)典的隨機圖產(chǎn)生器來模擬產(chǎn)生網(wǎng)絡(luò)的離散時隙拓?fù)浼疓= {Gs|s=s1，s2，…，sn}．設(shè)定任意兩個節(jié)點間存在鏈路的概率為p，p的大小表明了網(wǎng)絡(luò)鏈路的稀疏程度，稱p為鏈路密度．仿真中隨機產(chǎn)生具有10個節(jié)點的6個離散序列圖，每條鏈路的可靠度值服從0.8到1.0的均勻分布．設(shè)定p的值在0.5到1之間變化，并假定每條鏈路的傳輸開銷相等．仿真隨機產(chǎn)生500組滿足條件的序列圖，并統(tǒng)計網(wǎng)絡(luò)的平均性能．
圖3(a)顯示了網(wǎng)絡(luò)的傳輸開銷比隨著鏈路密度的變化情況．從圖3(a)中知，兩種算法都能在網(wǎng)絡(luò)連通時，保證端到端路徑的高可靠度，并能有效地降低網(wǎng)絡(luò)的傳輸開銷，且鏈路密度越大，算法節(jié)省的傳輸開銷就越多．另外，從網(wǎng)絡(luò)鏈路的傳輸開銷考慮，算法2比算法1更優(yōu)，原因是算法1只是簡單地向時空圖中添加了最可靠路徑，可能會導(dǎo)致添加一些不必要的鏈路．圖3(b)顯示了平均可靠度隨著鏈路密度變化的情況．隨著鏈路密度的增加，兩種算法下的可靠度都有所提高．另外，算法1得到的平均可靠度略高，因為算法1添加了所有節(jié)點對之間的最可靠路徑．
圖3 網(wǎng)絡(luò)傳輸開銷比和平均可靠度隨鏈路密度的變化曲線
為了獲得時隙個數(shù)對傳輸開銷比和平均可靠度的影響，固定鏈路密度p=0.8，保持其他仿真參數(shù)不變，統(tǒng)計網(wǎng)絡(luò)具有不同時隙個數(shù)時的性能．圖4(a)顯示了傳輸開銷比隨時隙數(shù)目變化的關(guān)系．兩種算法的傳輸開銷比都隨著時隙數(shù)量的增大而下降，這表明時隙數(shù)目越多，越能體現(xiàn)兩種算法在傳輸開銷方面的有效性，且算法2體現(xiàn)的更加明顯．圖4(b)顯示了平均可靠度隨時隙數(shù)目變化的關(guān)系．可以看出，兩種算法的網(wǎng)絡(luò)的平均可靠度呈現(xiàn)下降趨勢，這是因為隨著時隙數(shù)目的增多，網(wǎng)絡(luò)拓?fù)浔憩F(xiàn)出較強的間歇連通特征，使得數(shù)據(jù)傳輸可靠性下降．由于算法1中含有最高可靠度的路徑，所以較算法2可靠度更高．
圖4 網(wǎng)絡(luò)傳輸開銷比和平均可靠度隨時隙數(shù)目的變化曲線
固定鏈路密度p=0.8，時隙數(shù)量為6，保持其他仿真參數(shù)不變，統(tǒng)計網(wǎng)絡(luò)具有不同節(jié)點數(shù)目時的性能．圖5(a)顯示了傳輸開銷比隨節(jié)點數(shù)目的變化關(guān)系．兩種算法的傳輸開銷比都隨著節(jié)點數(shù)目的增大而下降，這表明了節(jié)點數(shù)目越多，越能體現(xiàn)兩種算法在傳輸開銷方面的有效性，且算法2體現(xiàn)的更加明顯．圖5(b)顯示了平均可靠度隨時隙數(shù)目變化的關(guān)系．兩種算法的平均可靠度隨著節(jié)點數(shù)目的增多而變大，因為當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)目增大時，在鏈路密度一定的情況下，鏈路數(shù)量相對較多，節(jié)點對間更有機會選擇可靠性高的路徑，且算法1具有更高的可靠性．
圖5 網(wǎng)絡(luò)傳輸開銷比和平均可靠度隨節(jié)點數(shù)目的變化曲線
綜上，相比原網(wǎng)絡(luò)來說，在保證網(wǎng)絡(luò)連通的情況下，兩種算法都能保證數(shù)據(jù)傳輸?shù)目煽啃?，同時降低網(wǎng)絡(luò)的傳輸開銷．算法1在可靠度方面比算法2略顯優(yōu)勢，而算法2比算法1在傳輸開銷方面略顯優(yōu)勢．
5 結(jié) 束 語
時延容忍網(wǎng)絡(luò)的節(jié)點和鏈路動態(tài)性為拓?fù)淇刂茙硖魬?zhàn)．筆者基于拓?fù)渲芷谛钥深A(yù)測的時延容忍網(wǎng)絡(luò)，首先將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)化為時空圖，進(jìn)而定義了可靠拓?fù)淇刂茊栴}．針對此問題，提出了兩種有效的拓?fù)淇刂品桨福負(fù)淇刂频哪康氖窃诓黄茐木W(wǎng)絡(luò)連通性的條件下保證網(wǎng)絡(luò)的可靠性和降低網(wǎng)絡(luò)的傳輸開銷．最后，仿真驗證了提出的方法的有效性．網(wǎng)絡(luò)拓?fù)涞男阅軙W(wǎng)絡(luò)路由和數(shù)據(jù)傳輸產(chǎn)生影響，在拓?fù)淇刂频幕A(chǔ)上，性能優(yōu)越的路由技術(shù)應(yīng)該被設(shè)計．因此，在未來的工作中，路由的研究將是一個重要話題．
猜你喜歡
移火柴小獼猴智力畫刊(2021年6期)2021-08-05 5G承載網(wǎng)部署滿足uRLLC業(yè)務(wù)時延要求的研究通信電源技術(shù)(2020年8期)2020-07-21 基于時分多址的網(wǎng)絡(luò)時隙資源分配研究艦船電子對抗(2020年2期)2020-06-23 基于GCC-nearest時延估計的室內(nèi)聲源定位電子制作(2019年23期)2019-02-23 基于市場機制的多機場時隙交換放行策略經(jīng)濟(jì)研究導(dǎo)刊(2018年26期)2018-11-14 復(fù)用段單節(jié)點失效造成業(yè)務(wù)時隙錯連處理鐵道通信信號(2018年9期)2018-11-10 一種高速通信系統(tǒng)動態(tài)時隙分配設(shè)計艦船電子對抗(2016年3期)2016-12-13 簡化的基于時延線性擬合的寬帶測向算法現(xiàn)代防御技術(shù)(2016年1期)2016-06-01 《哲對寧諾爾》方劑數(shù)目統(tǒng)計研究中國民族醫(yī)藥雜志(2016年5期)2016-05-09 牧場里的馬作文大王·低年級(2016年3期)2016-03-11
齊小剛，馬久龍，劉立芳
(1. 西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，陜西 西安 710071；2. 西安電子科技大學(xué) 計算機學(xué)院，陜西 西安 710071)
時延容忍網(wǎng)絡(luò)是為設(shè)計星際互聯(lián)網(wǎng)而被研究和發(fā)展的，但目前已被擴展到其他領(lǐng)域，其特點是節(jié)點持續(xù)運動、拓?fù)鋾r變、鏈路間歇連通[1-2]．尤其是以衛(wèi)星網(wǎng)絡(luò)作為骨干網(wǎng)的空間信息網(wǎng)絡(luò)[3]，衛(wèi)星節(jié)點周期性移動，網(wǎng)絡(luò)還面臨隨機的節(jié)點和鏈路失效問題[4-5]．研究表明，適用于時延容忍網(wǎng)絡(luò)的許多方案也適用于衛(wèi)星網(wǎng)絡(luò)[6-7]．在拓?fù)渲芷谛宰兓臅r延容忍網(wǎng)絡(luò)中，基于時間片[8-9]的方案被廣泛使用．該方案將網(wǎng)絡(luò)的周期分割為離散的時間片，在每個時間片內(nèi)拓?fù)淇梢暈楣潭ǖ?，這使得一個時間片中只有當(dāng)兩個節(jié)點存在端到端路徑時，數(shù)據(jù)才可以正常傳輸，忽略了時間片間的聯(lián)系．文獻(xiàn)[10]基于連通時序?qū)崿F(xiàn)了深空網(wǎng)絡(luò)的最大吞吐量，文獻(xiàn)[11]在時間片的基礎(chǔ)上提出了幾種有效的拓?fù)淇刂品桨?，這些方法都假定了鏈路是完全可靠的．然而，空間網(wǎng)絡(luò)節(jié)點間的鏈路在大多數(shù)情況下不是完全可靠的，且節(jié)點存儲受限．
針對這些問題，筆者基于時空圖模型，提出了新的適用于拓?fù)渲芷谛宰兓臅r延容忍網(wǎng)絡(luò)的拓?fù)淇刂品桨福诒ＷC網(wǎng)絡(luò)連通的條件下，旨在尋找原時空圖的一個稀疏子圖，該稀疏子圖能夠滿足任意節(jié)點對之間的路徑的可靠性，同時降低了網(wǎng)絡(luò)的傳輸開銷．
圖1 一個時延容忍網(wǎng)絡(luò)的序列圖示例
1 網(wǎng)絡(luò)模型和相關(guān)定義
1.1 網(wǎng)絡(luò)模型
假設(shè)由6個節(jié)點組成的時延容忍網(wǎng)絡(luò)(Delay Tolerant Network，DTN)，如圖1所示，節(jié)點分別為一個地面節(jié)點T1、兩個低軌道衛(wèi)星節(jié)點L1和L2、兩個中軌道衛(wèi)星M1和M2以及一個靜止衛(wèi)星G1．在t0至t1時間段內(nèi)，節(jié)點之間的連接關(guān)系是固定的，即拓?fù)涫枪潭ú蛔兊?，稱該時間段為一個時隙，即時隙1; 在t1時刻，部分節(jié)點之間的連接關(guān)系發(fā)生了變化，即拓?fù)涑霈F(xiàn)了新的狀態(tài)，t1～t2時間段內(nèi)網(wǎng)絡(luò)維持新的狀態(tài)，則t1至t2的時間段為一個新的時隙，即時隙2; 在t2時刻，節(jié)點之間的連接關(guān)系再次發(fā)生變化．依此類推，網(wǎng)絡(luò)在一個周期可能出現(xiàn)圖1所示的幾種拓?fù)錉顟B(tài)．
按此方法將網(wǎng)絡(luò)的系統(tǒng)周期T劃分為n個時隙s1，s2，…，sn．用V表示網(wǎng)絡(luò)的m個節(jié)點組成的集合，V= {v1，v2，…，vm}；Gs= (Vs，Es)，表示網(wǎng)絡(luò)在時隙s時的拓?fù)洌渲蠽s和Es分別為網(wǎng)絡(luò)在時隙s時的節(jié)點和鏈路集合，則網(wǎng)絡(luò)在周期T的拓?fù)淇杀硎緸镚= {Gs|s=s1，s2，…，sn}，它可以完整準(zhǔn)確地描述網(wǎng)絡(luò)的拓?fù)洌@樣的離散序列很難進(jìn)行拓?fù)淇刂坪吐酚稍O(shè)計，因為在某些時隙內(nèi)，網(wǎng)絡(luò)并不連通，如圖1中的時隙3、時隙4和時隙5，此時，L1和L2無法和T1通信．因此，直接將靜態(tài)圖序列用在時延容忍網(wǎng)絡(luò)是不合適的．現(xiàn)考慮使用時空圖來模擬網(wǎng)絡(luò)的拓?fù)洌畬⒁幌盗械撵o態(tài)圖轉(zhuǎn)化為時空圖，為此將任意兩個時隙上的任意兩個節(jié)點看成是不同的．
1.2 相關(guān)定義
定義1(時空圖) 若時延容忍網(wǎng)絡(luò)的拓?fù)浔硎緸镚={Gs|s=s1，s2，…，sn}，其中Gs= (Vs，Es)，為網(wǎng)絡(luò)在時隙s時的拓?fù)洌瑒tG的時空圖被定義為一個有向圖GTS= (V，E，T)，其中:
(2)E是時空圖的有向鏈路的集合，有向鏈路指的是時間鏈路和空間鏈路，分別定義如下．
圖2 時空圖的一個示例
(3)T是網(wǎng)絡(luò)的系統(tǒng)周期．
通過定義時空圖，任意兩個節(jié)點間的通信可在時空圖上表示．例如，若T1在t0時刻想發(fā)數(shù)據(jù)給M2，它可能采取的方式是先攜帶數(shù)據(jù)至t1時刻，在時隙2內(nèi)，T1將數(shù)據(jù)轉(zhuǎn)發(fā)給L1，在時隙3內(nèi)L1轉(zhuǎn)發(fā)數(shù)據(jù)給L2，在時隙4內(nèi)L2轉(zhuǎn)發(fā)數(shù)據(jù)給M1，最后在時隙5內(nèi)，M1將數(shù)據(jù)轉(zhuǎn)發(fā)給M2．
實際上網(wǎng)絡(luò)節(jié)點間在傳輸數(shù)據(jù)時會有一定的傳輸開銷．因此，給時空圖的每一條鏈路賦予一個權(quán)值來代表傳輸開銷．時間鏈路上的權(quán)值代表節(jié)點在一個時間段攜帶數(shù)據(jù)的開銷．類似于衛(wèi)星網(wǎng)絡(luò)的時延容忍網(wǎng)絡(luò)一般運行在極其復(fù)雜的空間環(huán)境中，衛(wèi)星及星間鏈路在任意時刻都可能發(fā)生故障，甚至遭受人為攻擊．筆者考慮衛(wèi)星節(jié)點失效和鏈路故障的情形．賦予時空圖中的有向鏈路e一個介于0到1之間的實數(shù)r(e)來表示該鏈路的可靠性，稱r(e)為鏈路e的可靠度．對于時間鏈路，r(e)表征節(jié)點緩存和攜帶數(shù)據(jù)的成功率．當(dāng)節(jié)點緩存不夠時，數(shù)據(jù)會被丟失．例如在衛(wèi)星網(wǎng)絡(luò)中，軌內(nèi)星間鏈路的可靠度比軌間星間鏈路的可靠度更高; 層間鏈路的可靠度比層內(nèi)的星間鏈路可靠度低．此外，時間鏈路比空間鏈路的可靠度高．
定義2(賦權(quán)時空圖) 稱G=(V，E，c，r)為賦權(quán)時空圖，其中V為時空圖的節(jié)點集合;E為時空圖的鏈路集合;c為定義在E上的正實值函數(shù)，即c:E→R+，稱c為開銷函數(shù);r為定義在E上取值在[0，1]之間的函數(shù)，即r:E→ [0，1]，稱r為可靠度函數(shù)．
定義5(路徑的可靠度和最可靠路徑) 在時空圖G中，一個從節(jié)點u到節(jié)點v的路徑P(u，v)的可靠度是指該路徑上所有鏈路的可靠度的乘積．從u到v的最可靠路徑是指從節(jié)點u到節(jié)點v的所有路徑中可靠度最高的路徑．
2 可靠拓?fù)淇刂茊栴}
可靠拓?fù)淇刂茊栴}可以被描述如下．給定一個連通的賦權(quán)時空圖G=(V，E，c，r)，拓?fù)淇刂频哪康氖钦业揭粋€稀疏時空子圖H(V′，E′，c，r)，使其滿足:V′=V;H在一個周期T上是連通的;H中任意節(jié)點對之間的路徑的可靠度最高;子圖H的傳輸開銷c(H)最?。?/p>
要保證網(wǎng)絡(luò)任意節(jié)點對之間的路徑的高可靠度和子圖的低傳輸開銷是極其困難的．為使問題簡化，假定在每條鏈路上的傳輸開銷是相等的，筆者提出兩個有效的啟發(fā)式算法解決了該問題．
3 相關(guān)算法
解決上面問題的思路是在構(gòu)造的原始時空圖G中尋找各個節(jié)點對之間可靠度較高的路徑．可以將時空圖G中所有節(jié)點對之間的最可靠路徑添加到子圖H．顯然，生成的子圖H能夠滿足網(wǎng)絡(luò)的可靠需求．為此，首先將所有鏈路的可靠度值取負(fù)對數(shù)，然后使用Dijkstra算法．算法1顯示了詳細(xì)過程．
算法1 最可靠路徑聯(lián)合算法．
輸入：原網(wǎng)絡(luò)的序列圖{Gs}．
輸出：時空子圖H．
算法2 最可靠路徑的貪婪算法．
輸入：原網(wǎng)絡(luò)的序列圖{Gs}．
輸出：時空子圖H．
算法1為了滿足節(jié)點對之間數(shù)據(jù)傳輸?shù)目煽啃詶l件，以最簡單的方式向子圖中添加最可靠路徑．盡管它能夠滿足可靠條件，但是添加了過多不必要的鏈路，不能大幅度降低網(wǎng)絡(luò)的傳輸開銷．算法2通過逐次加入最可靠路徑，進(jìn)一步降低了網(wǎng)絡(luò)的傳輸開銷，同時保證網(wǎng)絡(luò)具有一定的可靠性．若用N表示問題的規(guī)模，由于時空圖最多有n+1 層，所以節(jié)點個數(shù)為N(n+1)，邊的個數(shù)最多為nN2．在時空圖上運行N次Dijkstra算法，算法1的時間復(fù)雜度為N2O(nN+nlog(nN))=O(nN3+nN2log(nN))．同理，算法2的時間復(fù)雜度為N2O(nN3+nN2log(nN))=O(nN5+nN4log(nN))．
4 性能評估
拓?fù)淇刂频哪康氖菫榱藰?gòu)建一個滿足任意節(jié)點對之間數(shù)據(jù)傳輸有可靠性保證的稀疏拓?fù)?，并降低網(wǎng)絡(luò)的傳輸開銷．仿真采用兩種度量來衡量提出算法的性能：一是稀疏時空子圖H的傳輸開銷與原時空圖G的傳輸開銷的比值，即傳輸開銷比；二是時空子圖H的平均可靠度．網(wǎng)絡(luò)的鏈路開銷越小，可靠度越高，表征拓?fù)淇刂扑惴ㄔ接行В?/p>
為了模擬真實時延容忍網(wǎng)絡(luò)的拓?fù)?，采用?jīng)典的隨機圖產(chǎn)生器來模擬產(chǎn)生網(wǎng)絡(luò)的離散時隙拓?fù)浼疓= {Gs|s=s1，s2，…，sn}．設(shè)定任意兩個節(jié)點間存在鏈路的概率為p，p的大小表明了網(wǎng)絡(luò)鏈路的稀疏程度，稱p為鏈路密度．仿真中隨機產(chǎn)生具有10個節(jié)點的6個離散序列圖，每條鏈路的可靠度值服從0.8到1.0的均勻分布．設(shè)定p的值在0.5到1之間變化，并假定每條鏈路的傳輸開銷相等．仿真隨機產(chǎn)生500組滿足條件的序列圖，并統(tǒng)計網(wǎng)絡(luò)的平均性能．
圖3(a)顯示了網(wǎng)絡(luò)的傳輸開銷比隨著鏈路密度的變化情況．從圖3(a)中知，兩種算法都能在網(wǎng)絡(luò)連通時，保證端到端路徑的高可靠度，并能有效地降低網(wǎng)絡(luò)的傳輸開銷，且鏈路密度越大，算法節(jié)省的傳輸開銷就越多．另外，從網(wǎng)絡(luò)鏈路的傳輸開銷考慮，算法2比算法1更優(yōu)，原因是算法1只是簡單地向時空圖中添加了最可靠路徑，可能會導(dǎo)致添加一些不必要的鏈路．圖3(b)顯示了平均可靠度隨著鏈路密度變化的情況．隨著鏈路密度的增加，兩種算法下的可靠度都有所提高．另外，算法1得到的平均可靠度略高，因為算法1添加了所有節(jié)點對之間的最可靠路徑．
圖3 網(wǎng)絡(luò)傳輸開銷比和平均可靠度隨鏈路密度的變化曲線
為了獲得時隙個數(shù)對傳輸開銷比和平均可靠度的影響，固定鏈路密度p=0.8，保持其他仿真參數(shù)不變，統(tǒng)計網(wǎng)絡(luò)具有不同時隙個數(shù)時的性能．圖4(a)顯示了傳輸開銷比隨時隙數(shù)目變化的關(guān)系．兩種算法的傳輸開銷比都隨著時隙數(shù)量的增大而下降，這表明時隙數(shù)目越多，越能體現(xiàn)兩種算法在傳輸開銷方面的有效性，且算法2體現(xiàn)的更加明顯．圖4(b)顯示了平均可靠度隨時隙數(shù)目變化的關(guān)系．可以看出，兩種算法的網(wǎng)絡(luò)的平均可靠度呈現(xiàn)下降趨勢，這是因為隨著時隙數(shù)目的增多，網(wǎng)絡(luò)拓?fù)浔憩F(xiàn)出較強的間歇連通特征，使得數(shù)據(jù)傳輸可靠性下降．由于算法1中含有最高可靠度的路徑，所以較算法2可靠度更高．
圖4 網(wǎng)絡(luò)傳輸開銷比和平均可靠度隨時隙數(shù)目的變化曲線
固定鏈路密度p=0.8，時隙數(shù)量為6，保持其他仿真參數(shù)不變，統(tǒng)計網(wǎng)絡(luò)具有不同節(jié)點數(shù)目時的性能．圖5(a)顯示了傳輸開銷比隨節(jié)點數(shù)目的變化關(guān)系．兩種算法的傳輸開銷比都隨著節(jié)點數(shù)目的增大而下降，這表明了節(jié)點數(shù)目越多，越能體現(xiàn)兩種算法在傳輸開銷方面的有效性，且算法2體現(xiàn)的更加明顯．圖5(b)顯示了平均可靠度隨時隙數(shù)目變化的關(guān)系．兩種算法的平均可靠度隨著節(jié)點數(shù)目的增多而變大，因為當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)目增大時，在鏈路密度一定的情況下，鏈路數(shù)量相對較多，節(jié)點對間更有機會選擇可靠性高的路徑，且算法1具有更高的可靠性．
圖5 網(wǎng)絡(luò)傳輸開銷比和平均可靠度隨節(jié)點數(shù)目的變化曲線
綜上，相比原網(wǎng)絡(luò)來說，在保證網(wǎng)絡(luò)連通的情況下，兩種算法都能保證數(shù)據(jù)傳輸?shù)目煽啃?，同時降低網(wǎng)絡(luò)的傳輸開銷．算法1在可靠度方面比算法2略顯優(yōu)勢，而算法2比算法1在傳輸開銷方面略顯優(yōu)勢．
5 結(jié) 束 語
時延容忍網(wǎng)絡(luò)的節(jié)點和鏈路動態(tài)性為拓?fù)淇刂茙硖魬?zhàn)．筆者基于拓?fù)渲芷谛钥深A(yù)測的時延容忍網(wǎng)絡(luò)，首先將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)化為時空圖，進(jìn)而定義了可靠拓?fù)淇刂茊栴}．針對此問題，提出了兩種有效的拓?fù)淇刂品桨福負(fù)淇刂频哪康氖窃诓黄茐木W(wǎng)絡(luò)連通性的條件下保證網(wǎng)絡(luò)的可靠性和降低網(wǎng)絡(luò)的傳輸開銷．最后，仿真驗證了提出的方法的有效性．網(wǎng)絡(luò)拓?fù)涞男阅軙W(wǎng)絡(luò)路由和數(shù)據(jù)傳輸產(chǎn)生影響，在拓?fù)淇刂频幕A(chǔ)上，性能優(yōu)越的路由技術(shù)應(yīng)該被設(shè)計．因此，在未來的工作中，路由的研究將是一個重要話題．
猜你喜歡
小獼猴智力畫刊(2021年6期)2021-08-05
通信電源技術(shù)(2020年8期)2020-07-21
艦船電子對抗(2020年2期)2020-06-23
電子制作(2019年23期)2019-02-23
經(jīng)濟(jì)研究導(dǎo)刊(2018年26期)2018-11-14
鐵道通信信號(2018年9期)2018-11-10
艦船電子對抗(2016年3期)2016-12-13
現(xiàn)代防御技術(shù)(2016年1期)2016-06-01
中國民族醫(yī)藥雜志(2016年5期)2016-05-09
作文大王·低年級(2016年3期)2016-03-11
