開題答辯(李發(fā),路由探測(cè))

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

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

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

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

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

6、網(wǎng)絡(luò)中最大介數(shù)節(jié)點(diǎn)以找到次最短路徑的路由策略。 本文主要研究?jī)?nèi)容 本文將隨機(jī)行走理論應(yīng)用到網(wǎng)絡(luò)的路徑發(fā)現(xiàn)中去，提出了一種基于隨機(jī)行走的路由探測(cè)方法，主要工作有以下方面：1.研究復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)知識(shí)，重點(diǎn)分析網(wǎng)絡(luò)拓?fù)涞幕灸Ｐ秃统Ｓ玫乃阉鞑呗浴?.研究隨機(jī)行走的經(jīng)典理論，如布朗粒子的首達(dá)時(shí)間、首達(dá)概率、平均首達(dá)時(shí)間、位置概率分布、便宜距離、給定時(shí)間內(nèi)的訪問節(jié)點(diǎn)數(shù)量、覆蓋時(shí)間等內(nèi)容。3.將隨機(jī)行走理論應(yīng)用到網(wǎng)絡(luò)中的路徑發(fā)現(xiàn)中，提出一種基于隨機(jī)行走的路由探測(cè)策略。4.仿真并測(cè)試該策略的可行性和可靠性。 在對(duì)隨機(jī)行走的研究過程中發(fā)現(xiàn)，單個(gè)粒子通過某條特定路徑的時(shí)間正比于該路徑上所有節(jié)點(diǎn)度的連乘積，在此基

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

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

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

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

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

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

13、路徑上的不確定性因素越少，越有利于布朗粒子從該路徑上通過。因此在源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的所有路徑中，節(jié)點(diǎn)度連乘積最小的路徑才是布朗運(yùn)動(dòng)意義下的最優(yōu)路徑。 由以上兩個(gè)方面可知，我們要找的這條最優(yōu)路徑是從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的所有路徑中，節(jié)點(diǎn)度連乘積最小的路徑。112020log (1/ ( )log ( )lliiiikk3.給出算法、編寫程序、仿真測(cè)試 研究并給出用隨機(jī)行走的方式探索最優(yōu)路徑的算法，編寫程序，并在多種網(wǎng)絡(luò)模型上進(jìn)行仿真、測(cè)試，驗(yàn)證此方案的可行性。 課題的主要難點(diǎn)及擬采取解決方案主要難點(diǎn)1.針對(duì)不同網(wǎng)絡(luò)模型挑選出合適的隨機(jī)行走方式。2.基于隨機(jī)行走的路由探測(cè)算法的提出與改進(jìn)。3.程序的

14、編寫與調(diào)試。解決方案1.認(rèn)真研究不同的網(wǎng)絡(luò)模型的結(jié)構(gòu)和性質(zhì)，分析幾種經(jīng)典的隨機(jī)行走方式各自的優(yōu)缺點(diǎn)并進(jìn)行改進(jìn)。2.仔細(xì)研究隨機(jī)行走的經(jīng)典算法，結(jié)合路由探測(cè)方法，在此基礎(chǔ)上進(jìn)行改性。3.認(rèn)真學(xué)習(xí)C+語言和Matlab語言，多研究前人類似的程序，和同學(xué)們進(jìn)行討論分析并請(qǐng)教老師。 預(yù)期研究成果該路由探測(cè)方法將具有以下優(yōu)點(diǎn)：1.有效均衡網(wǎng)絡(luò)上的負(fù)載，避免對(duì)核心節(jié)點(diǎn)的充分依賴，大大減少甚至消除網(wǎng)絡(luò)擁塞。2.大幅度提高網(wǎng)絡(luò)的整體承受能力，從而有效提高網(wǎng)絡(luò)的抗飽和攻擊的能力。3.隨著網(wǎng)絡(luò)規(guī)模和節(jié)點(diǎn)平均度的增加，路徑長(zhǎng)度趨于基于最短路徑路由策略的路徑長(zhǎng)度，從而在網(wǎng)絡(luò)規(guī)模較大的情況下保證數(shù)據(jù)的快速傳輸。進(jìn)度安排1、2013年0