開題答辯(李發(fā)-路由探測)

1、隨機行走在路由探測中的應(yīng)用 指導(dǎo)教師 ： 王林 教授 1212班姓名：李發(fā) 學(xué)號：12081005781 研究背景與意義背景：作為研究復(fù)雜性科學(xué)和復(fù)雜系統(tǒng)的有力工具，復(fù)雜網(wǎng)絡(luò)已成為學(xué)術(shù)界研究的一個熱點，它在工程技術(shù)、社會、政治、醫(yī)藥、經(jīng)濟、管理領(lǐng)域都有著潛在、廣泛的應(yīng)用。隨機行走作為網(wǎng)絡(luò)動力學(xué)過程的一種最基本形式，對于揭示網(wǎng)絡(luò)動力學(xué)過程的普遍規(guī)律具有重要的意義。除此之外，利用隨機行走的方法還以快速有效的發(fā)現(xiàn)網(wǎng)絡(luò)社團結(jié)構(gòu)，探索目標(biāo)節(jié)點和未知路徑，控制網(wǎng)絡(luò)上的數(shù)據(jù)傳輸，因此在學(xué)術(shù)領(lǐng)域得到了廣泛的關(guān)注和研究。意義：人類已經(jīng)進入信息時代，保證信息迅速可靠的傳輸對我們具有重要的意義。目前，一般可以通過兩

2、個方面提高網(wǎng)絡(luò)傳輸能力，即優(yōu)化網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和設(shè)計最佳路由策略。由于更改已知網(wǎng)絡(luò)的拓撲結(jié)構(gòu)比較困難，因此，人們主要致力于尋找合適的路由策略方面。傳統(tǒng)的最短路徑路由策略（SR）雖然所用傳輸時間短、效率高，但實際中，無標(biāo)度網(wǎng)絡(luò)節(jié)點度的異構(gòu)性導(dǎo)致介數(shù)的強異構(gòu)性，使得高介數(shù)的節(jié)點處經(jīng)常發(fā)生阻塞。因此，人們急需一種適應(yīng)范圍更加廣泛的合適的路由策略。2 國內(nèi)外研究進展 國際上的網(wǎng)絡(luò)中的隨機行走最早可以追溯到1905年，當(dāng)年愛因斯坦發(fā)表了五篇學(xué)術(shù)論文，除了著名的狹義相對論、光電效應(yīng)之外，還有一篇題為關(guān)于熱的分子運動論所要求的靜止液體中懸浮小粒子的運動的文章，主要研究了布朗運動的規(guī)律，后來研究者們將這種形式的

3、運動稱為隨機行走。雖然對網(wǎng)絡(luò)中的隨機行走的研究已經(jīng)將近有一個世紀(jì)的歷史了，但是它在工程技術(shù)上的廣泛應(yīng)用則是最近二三十年的事情。 我國對隨機行走的研究相對晚一些，主要研究領(lǐng)域主要集中在以下方面：隨機行走和電路網(wǎng)絡(luò)的聯(lián)系；組合數(shù)學(xué)方法使得隨機行走的研究有了更大的進步；對若干特殊類型圖的譜分析深化了隨機行走的理論；調(diào)和分析理論在隨機行走問題中的應(yīng)用。由于隨機行走是一個分析網(wǎng)絡(luò)資源、發(fā)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)、探索未知路徑、控制數(shù)據(jù)傳播的有力工具，因此將隨機行走理論應(yīng)用到具體實例中去，是研究者們近幾年的主要研究任務(wù)。3 目前網(wǎng)絡(luò)上的路由策略主要有以下幾種： 1. 最短路由策略（SR），這是現(xiàn)在網(wǎng)絡(luò)上普遍采用的一種路

4、由策略，數(shù)據(jù)包在源節(jié)點和目的節(jié)點之間的最短路徑傳輸，速度快、效率高。然而這種路由策略在網(wǎng)絡(luò)規(guī)模較小、傳輸數(shù)據(jù)量不大的情況下比較有效，當(dāng)網(wǎng)絡(luò)規(guī)模較大、數(shù)據(jù)流量較大時，隨著無標(biāo)度網(wǎng)絡(luò)異構(gòu)性的體現(xiàn)，在高介數(shù)的節(jié)點處容易發(fā)生嚴(yán)重的網(wǎng)絡(luò)阻塞，降低數(shù)據(jù)的傳輸速率。 2.局域信息路由策略（LR），數(shù)據(jù)包根據(jù)各自鄰居節(jié)點的局部信息以的概率隨機選擇選擇下一步路由。我們推導(dǎo)出，在節(jié)點處理能力相同的情況下，當(dāng)a=-1時，網(wǎng)絡(luò)的負載分布最為均勻，整體傳輸能力達到最大。 3.有效路由策略（ER），已知源節(jié)點i和目標(biāo)節(jié)點j，該路由策略通過最小化代價函數(shù)選擇路由路徑 pij ，在節(jié)點處理能力相同的情況下，=1時，該策略有效

5、的把網(wǎng)絡(luò)負載從核心節(jié)點轉(zhuǎn)移到邊緣節(jié)點。較多的利用了網(wǎng)絡(luò)中度較小的節(jié)點，在傳輸平均路徑長度仍符合網(wǎng)絡(luò)特征的基礎(chǔ)上，相比于最短路徑法將網(wǎng)絡(luò)的傳輸能力提高了十倍以上。4 根據(jù)以上三種基本的路由策略，人們又提出了其它幾種路由算法。 一類方法采用諸如節(jié)點隊列長度信息、節(jié)點信息等其它動態(tài)信息替換基礎(chǔ)路由策略中節(jié)點度的信息。 另一類方法則根據(jù)鄰居節(jié)點度、隊列長度、全局拓撲結(jié)構(gòu)和鄰居節(jié)點排隊等待時間等網(wǎng)絡(luò)中各類靜態(tài)或動態(tài)信息自適用調(diào)整路由策略。 還有一類方法通過極值優(yōu)化方法獲得最優(yōu)路由策略。例如，通過更改網(wǎng)絡(luò)中邊的權(quán)值以降低網(wǎng)絡(luò)中最大介數(shù)值的最優(yōu)路徑優(yōu)化策略，以及規(guī)避網(wǎng)絡(luò)中最大介數(shù)節(jié)點以找到次最短路徑的路由策

6、略。5 本文主要研究內(nèi)容 本文將隨機行走理論應(yīng)用到網(wǎng)絡(luò)的路徑發(fā)現(xiàn)中去，提出了一種基于隨機行走的路由探測方法，主要工作有以下方面：1.研究復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)知識，重點分析網(wǎng)絡(luò)拓撲的基本模型和常用的搜索策略。2.研究隨機行走的經(jīng)典理論，如布朗粒子的首達時間、首達概率、平均首達時間、位置概率分布、便宜距離、給定時間內(nèi)的訪問節(jié)點數(shù)量、覆蓋時間等內(nèi)容。3.將隨機行走理論應(yīng)用到網(wǎng)絡(luò)中的路徑發(fā)現(xiàn)中，提出一種基于隨機行走的路由探測策略。4.仿真并測試該策略的可行性和可靠性。6 在對隨機行走的研究過程中發(fā)現(xiàn)，單個粒子通過某條特定路徑的時間正比于該路徑上所有節(jié)點度的連乘積，在此基礎(chǔ)上，以基于隨機行走理論的優(yōu)化路由策略

7、為基礎(chǔ)，通過調(diào)節(jié)可變參數(shù)，提出一種最佳路由策略（IR）。通過比較不同路由策略條件下，平均路由介數(shù)中心度、網(wǎng)絡(luò)的臨界負載量、平均路徑長度以及平均搜索信息量等性能指標(biāo)，表明此路由策略在保證網(wǎng)絡(luò)平均路徑長度較少增加的前提下，使網(wǎng)絡(luò)的傳輸能力獲得最大幅度的提升。7這三幅圖表示的是平均路由介數(shù)中心度g(k)與節(jié)點度k的關(guān)系。圖1顯示，在最短路徑策略中， g(k)- K1.7。圖2顯示，在有效路由策略下，g(k)-k曲線近似呈泊松分布，在k=15附近達到峰值。圖3顯示，優(yōu)化路由策略下， g(k)-k曲線呈現(xiàn)線性關(guān)系。8 此圖表示的是不同控制參數(shù)條件下，優(yōu)化路由策略時的平均路由介數(shù)中心度與節(jié)點度的關(guān)系。可以

8、看出，當(dāng)=1.8和2.0時，g(k)的整體幅值小于=1.4和1.6時的整體幅值，說明當(dāng)1.6時，各個節(jié)點的網(wǎng)絡(luò)負載較小，進一步比較=1.8和=2.0時，有效路由策略下的g(k)可以發(fā)現(xiàn)，當(dāng)k20時，只有=1.8時的g(k)的曲線下降較為緩慢，我們可以得知，當(dāng)=1.8時，網(wǎng)絡(luò)傳輸能力最強。9這是三種路由策略的-R曲線，其中，R為單位時間內(nèi)節(jié)點接受數(shù)據(jù)包的值，W為網(wǎng)絡(luò)上總的負載量。 這三種路由策略下，網(wǎng)絡(luò)的臨界負載量分別為28、433、522，平均路徑長度分別為3.59、5.43、4.71。比較發(fā)現(xiàn)，優(yōu)化路由策略在較小增加平均路徑長度的前提下，大幅度的提高了網(wǎng)絡(luò)的臨界負載量。10左圖表示的是改進路

9、由策略的最大介數(shù)中心度與網(wǎng)絡(luò)規(guī)模呈冪律關(guān)系：gmaxN，IR=1.2，在另外兩種路由策略下，SR=2.0，ER=1.3，改進路由策略的最大介數(shù)中心值始終小于另外兩個策略的對應(yīng)值。右圖顯示，隨著網(wǎng)絡(luò)平均節(jié)點度的增加，改進路由策略所對應(yīng)的RC始終優(yōu)于最短路由策略和有效路由策略。11左圖表示的是平均搜索信息量與網(wǎng)絡(luò)規(guī)模的關(guān)系（網(wǎng)絡(luò)平均節(jié)點度=6），右圖表示的是平均搜索信息量與網(wǎng)絡(luò)平均度的關(guān)系（網(wǎng)絡(luò)節(jié)點數(shù)N=1500）。比較可知，改進路由策略的平均搜索信息量始終小于其它兩個策略。12 研究方案和技術(shù)路線1.研究采用隨機行走的方式探索未知路徑 在復(fù)雜系統(tǒng)中，通過隨機行走發(fā)現(xiàn)未知路徑的現(xiàn)象是常見的。由于網(wǎng)

10、絡(luò)中的數(shù)據(jù)傳輸實際上就是數(shù)據(jù)包從源節(jié)點到目標(biāo)節(jié)點的路由探測，因此考慮將隨機行走的理論應(yīng)用到路由探測中去。布朗粒子在網(wǎng)絡(luò)上行走的時間越長，它發(fā)現(xiàn)指定路徑的概率就越大，再者，布朗粒子所處的環(huán)境越簡單，尋找指定路徑就越容易。盡管不知道什么時候能找到指定路徑，但只要它不停地在網(wǎng)絡(luò)上隨機行走，就一定會找到。與傳統(tǒng)的跳數(shù)最少的最短路徑相比，隨機行走最短路徑的不確定性最小，或者說信道容量最大，這點對于網(wǎng)絡(luò)上的信息傳輸具有重要的意義。 既然是隨機行走，就有不確定性，在此計算通過隨機行走方式發(fā)現(xiàn)指定路徑的概率，使用的數(shù)學(xué)技巧主要是迭代方法和生成函數(shù)。由于涉及到位置參數(shù)，所以此過程分為兩步，首先在特殊情況下求解，

11、得出未知參數(shù)，然后再利用第一步的結(jié)果，計算在一般情況下的路徑發(fā)現(xiàn)概率。132.找出最優(yōu)路徑 既然布朗粒子是通過隨機行走的方式來探索路徑，那么它探索的是哪條路徑呢？ 一方面，從統(tǒng)計物理的角度來看。設(shè)布朗粒子從源節(jié)點s出發(fā)，要探索的路徑為其中路徑的起點為u=0，終點為v=l，通過下式可以計算出布朗粒子發(fā)現(xiàn)路徑C的平均首達時間：其中k(i)為節(jié)點i的度，m為網(wǎng)絡(luò)上邊的總數(shù)，j是矩陣Q=D-1/2PD1/2的特征值，j是相應(yīng)的特征向量，這里P是布朗粒子的概率轉(zhuǎn)移矩陣，D=diag(k(1),.k(n)是對角陣。 從上面的公式可以看出，第一項的大小主要是由除終點之外的所有節(jié)點的節(jié)點度的連乘積決定。因此，

12、在源節(jié)點和目標(biāo)節(jié)點之間的所有路徑中，我們要尋找一條使得連乘積最小的路徑，布朗粒子發(fā)現(xiàn)這條路徑的所用的平均首達時間也是最短的，所用的能量也就最少。把這個結(jié)論應(yīng)用到網(wǎng)絡(luò)中的負載傳輸過程中，則這條節(jié)點度連乘積最小的路徑即是從源節(jié)點到目標(biāo)節(jié)點之間的最優(yōu)路徑。14 另一方面，從信息論的角度來看，一條路徑搜索信息為 也就是說，節(jié)點度的連乘積越大，相應(yīng)路徑上的搜索信息越多，不確定性因素越多，越不利于布朗粒子從該路徑上通過，反之，節(jié)點度的連乘積越小，則該路徑上的不確定性因素越少，越有利于布朗粒子從該路徑上通過。因此在源節(jié)點和目標(biāo)節(jié)點的所有路徑中，節(jié)點度連乘積最小的路徑才是布朗運動意義下的最優(yōu)路徑。 由以上兩個

13、方面可知，我們要找的這條最優(yōu)路徑是從源節(jié)點到目標(biāo)節(jié)點之間的所有路徑中，節(jié)點度連乘積最小的路徑。153.給出算法、編寫程序、仿真測試 研究并給出用隨機行走的方式探索最優(yōu)路徑的算法，編寫程序，并在多種網(wǎng)絡(luò)模型上進行仿真、測試，驗證此方案的可行性。16 課題的主要難點及擬采取解決方案主要難點1.針對不同網(wǎng)絡(luò)模型挑選出合適的隨機行走方式。2.基于隨機行走的路由探測算法的提出與改進。3.程序的編寫與調(diào)試。解決方案1.認真研究不同的網(wǎng)絡(luò)模型的結(jié)構(gòu)和性質(zhì)，分析幾種經(jīng)典的隨機行走方式各自的優(yōu)缺點并進行改進。2.仔細研究隨機行走的經(jīng)典算法，結(jié)合路由探測方法，在此基礎(chǔ)上進行改性。3.認真學(xué)習(xí)C+語言和Matlab語言，多研究前人類似的程序，和同學(xué)們進行討論分析并請教老師。17 預(yù)期研究成果該路由探測方法將具有以下優(yōu)點：1.有效均衡網(wǎng)絡(luò)上的負載，避免對核心節(jié)點的充分依賴，大大減少甚至消除網(wǎng)絡(luò)擁塞。2.大幅度提高網(wǎng)絡(luò)的整體承受能力，從而有效提高網(wǎng)絡(luò)的抗飽和攻擊的能力。3.隨著網(wǎng)絡(luò)規(guī)模和節(jié)點平均度的增加，路徑長度趨于基于最短路徑路由策略的路徑長度，從而在網(wǎng)絡(luò)規(guī)模較大的情況下保證數(shù)據(jù)的快速傳輸。18進度安排1、2013年08月-2013年1