網(wǎng)絡(luò)上的隨機行走及其在通信工程中的應(yīng)用.pdf

1、網(wǎng)絡(luò)動力學(xué)過程是復(fù)雜網(wǎng)絡(luò)理論和應(yīng)用研究的重要領(lǐng)域，而網(wǎng)絡(luò)隨機行走作為網(wǎng)絡(luò)動力學(xué)過程的一種最基本形式，對于揭示網(wǎng)絡(luò)動力學(xué)過程的普遍規(guī)律具有重要意義。近年來，復(fù)雜網(wǎng)絡(luò)上的隨機行走理論和應(yīng)用研究已引起普遍關(guān)注。在理論研究方面，將經(jīng)典的網(wǎng)絡(luò)隨機行走推廣到小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)等。在應(yīng)用研究方面，將隨機行走應(yīng)用于網(wǎng)絡(luò)采樣、網(wǎng)絡(luò)建模、搜索策略、路由策略、網(wǎng)絡(luò)免疫策略等問題。然而，目前復(fù)雜網(wǎng)絡(luò)上的隨機行走理論和應(yīng)用研究均處于初步階段，需要進(jìn)一步發(fā)展與

2、完善基礎(chǔ)理論框架，本文著重對網(wǎng)絡(luò)上的隨機行走理論及其在通信網(wǎng)絡(luò)應(yīng)用問題進(jìn)行了深入研究，具體的研究內(nèi)容和主要貢獻(xiàn)如下：
　　 研究了網(wǎng)絡(luò)上的多布朗粒子運動的問題。雖然網(wǎng)絡(luò)上的單布朗粒子運動理論已趨于完善，但是缺乏網(wǎng)絡(luò)上的多布朗粒子運動相關(guān)理論。首先，本文研究了網(wǎng)絡(luò)多布朗粒子運動的解析理論，分析了多布朗粒子運動的首達(dá)時間問題，給出了其解析表達(dá)式、首達(dá)時間的概率分布、平均首達(dá)時間等。其次，對于小世界網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)、Internet等

3、經(jīng)典復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從不同的角度分析了多布朗粒子運動的性質(zhì)。最后，探討了多布朗粒子運動理論在P2P網(wǎng)絡(luò)通信，小世界網(wǎng)絡(luò)上的最優(yōu)路由，無標(biāo)度網(wǎng)絡(luò)上的不對稱現(xiàn)象，以及互聯(lián)網(wǎng)上的傳播和擴散過程等工程應(yīng)用問題的可行性。
　　 研究了C.Elegance線蟲神經(jīng)網(wǎng)絡(luò)上的多布朗粒子運動問題。線蟲神經(jīng)網(wǎng)絡(luò)上的隨機行走作為研究神經(jīng)元之間傳遞電信號的一種方式，對理解動物的認(rèn)知行為有著重要影響。本文分析結(jié)果表明，特定神經(jīng)元只需發(fā)出為數(shù)不多的信號，

4、就可以將該信號沿近最短路徑快速地傳遞到目標(biāo)節(jié)點；中樞神經(jīng)和末梢神經(jīng)在多布朗粒子運動中的作用有顯著差異；線蟲神經(jīng)網(wǎng)絡(luò)具有快速擴散過程的拓?fù)浣Y(jié)構(gòu)特點。研究結(jié)果從一個側(cè)面表明，C.Elegance線蟲神經(jīng)網(wǎng)絡(luò)已經(jīng)具有優(yōu)化的拓?fù)浣Y(jié)構(gòu)，以保障實現(xiàn)其較復(fù)雜的認(rèn)知行為。
　　 研究了網(wǎng)絡(luò)上基于隨機行走探索未知路徑的問題。雖然基于隨機行走的網(wǎng)絡(luò)上單目標(biāo)節(jié)點搜索問題得到深入研究，但是還沒有關(guān)于目標(biāo)路徑的搜索問題的解決方法。本文利用迭代方法和生成函

5、數(shù)方法給出了目標(biāo)路徑發(fā)現(xiàn)概率的表達(dá)式，并在此基礎(chǔ)上詳細(xì)分析了諸如搜索時間、路徑長度、路徑構(gòu)成、網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)等影響發(fā)現(xiàn)概率的關(guān)鍵因素。研究結(jié)果表明，搜索時間、路徑長度和路徑上的節(jié)點度對目標(biāo)路徑發(fā)現(xiàn)概率具有決定性作用。進(jìn)一步，給出了目標(biāo)路徑發(fā)現(xiàn)的概率分布、平均首達(dá)時間解析表達(dá)式，并根據(jù)此解析理論，給出了布朗運動意義下網(wǎng)絡(luò)最優(yōu)路徑概念，即源節(jié)點和目標(biāo)節(jié)點之間布朗粒子搜索所需要的平均首達(dá)時間最少的路徑。與經(jīng)典的跳數(shù)最少最短路徑概念比較，所提出

6、的布朗運動意義下網(wǎng)絡(luò)最優(yōu)路徑不但符合能量最小化的自然法則，而且具有最低的路徑不確定性性質(zhì)。
　　 研究了布朗運動意義下網(wǎng)絡(luò)最優(yōu)路徑的路由策略。目前基于隨機行走的路由策略大多采用網(wǎng)絡(luò)靜態(tài)和動態(tài)信息相結(jié)合的自適應(yīng)路由策略，無法保證穩(wěn)定的傳輸效果。本文提出了基于布朗運動意義下網(wǎng)絡(luò)最優(yōu)路徑機制的極小化源節(jié)點和目標(biāo)節(jié)點間的節(jié)點度連乘積的路由策略，可以實現(xiàn)實現(xiàn)穩(wěn)定的路由。進(jìn)一步分析與實驗結(jié)果表明，所提出路由策略具有節(jié)點流量與節(jié)點度呈線性對應(yīng)