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

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

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

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

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

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

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