基于機(jī)會(huì)主義路由的無(wú)線Ad Hoc網(wǎng)絡(luò)關(guān)鍵技術(shù)研究.pdf

1、路由協(xié)議設(shè)計(jì)是無(wú)線Ad Hoc網(wǎng)絡(luò)研究中一個(gè)極其重要而且極富挑戰(zhàn)性的領(lǐng)域。機(jī)會(huì)主義路由思想為無(wú)線多跳網(wǎng)絡(luò)的路由協(xié)議設(shè)計(jì)開(kāi)辟了一條新的康莊大道。由于其能夠更好的適應(yīng)不穩(wěn)定、丟失率高的無(wú)線網(wǎng)絡(luò)環(huán)境，提高無(wú)線網(wǎng)絡(luò)端到端網(wǎng)絡(luò)性能，一經(jīng)被提出就成為研究的熱點(diǎn)。圍繞機(jī)會(huì)主義路由，很多兼容性與優(yōu)化的問(wèn)題應(yīng)運(yùn)而出，如實(shí)現(xiàn)接入控制、多速率控制、機(jī)會(huì)主義多播、性能優(yōu)化。本論文在國(guó)家自然科學(xué)基金等項(xiàng)目的支持下，針對(duì)機(jī)會(huì)主義路由的路由參數(shù)設(shè)計(jì)、轉(zhuǎn)發(fā)節(jié)點(diǎn)列表選擇

2、機(jī)制及大規(guī)模無(wú)線網(wǎng)絡(luò)中的應(yīng)用問(wèn)題進(jìn)行了深入研究，獲得了若干具有創(chuàng)新性的成果，主要的工作和創(chuàng)新點(diǎn)包括以下幾個(gè)方面：
　　 第一，針對(duì)目前的機(jī)會(huì)主義路由協(xié)議所使用的路由參數(shù)不能準(zhǔn)確衡量當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)機(jī)會(huì)主義期望傳輸數(shù)的問(wèn)題，本文通過(guò)用隨機(jī)游走模型對(duì)機(jī)會(huì)主義路由建模的方法，建立了一套研究機(jī)會(huì)主義路由傳輸?shù)睦碚摗２⑶矣眠@套理論將求解機(jī)會(huì)主義路由的期望傳輸次數(shù)問(wèn)題轉(zhuǎn)化為計(jì)算隨機(jī)游走模型狀態(tài)轉(zhuǎn)移次數(shù)的問(wèn)題，從而在理論上計(jì)算出符合機(jī)會(huì)主義

3、路由的路由參數(shù)EN（Expected Number of Transmission）。在與以往常用的ETX路由參數(shù)進(jìn)行仿真對(duì)比時(shí)，結(jié)果顯示使用EN路由參數(shù)可以比ETX參數(shù)提高網(wǎng)絡(luò)端到端吞吐量約40.98％，降低每包平均傳輸數(shù)性能約32.2％的。
　　 第二，針對(duì)目前機(jī)會(huì)主義轉(zhuǎn)發(fā)節(jié)點(diǎn)列表選擇問(wèn)題上沒(méi)有最優(yōu)算法的問(wèn)題，本文使用最優(yōu)化理論對(duì)機(jī)會(huì)主義傳輸方式進(jìn)行理論分析，設(shè)計(jì)出能選出具有最小期望轉(zhuǎn)發(fā)數(shù)的最優(yōu)轉(zhuǎn)發(fā)節(jié)點(diǎn)列表選擇算法（MTS算

4、法），填補(bǔ)了這一問(wèn)題上的理論空白；并采用動(dòng)態(tài)規(guī)劃的方法對(duì)算法進(jìn)行優(yōu)化，降低了算法復(fù)雜度。仿真結(jié)果表明在MIT的Roofnet網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中超過(guò)90％的源目的節(jié)點(diǎn)對(duì)使用MTS算法能比ETX算法獲得性能更優(yōu)得轉(zhuǎn)發(fā)節(jié)點(diǎn)列表，而且每包平均傳輸數(shù)降低最多可達(dá)82％，吞吐量提高百分比可達(dá)322％。
　　 第三，通過(guò)頻譜圖理論（Spectral Graph Theory）建模無(wú)線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法，設(shè)計(jì)出針對(duì)大規(guī)模無(wú)線網(wǎng)絡(luò)拓?fù)涞念l譜圖分割算法

5、（SGP算法，Spectral Graph Partitioning Algorithm）。首先，使用最優(yōu)化理論將拓?fù)浞指顔?wèn)題抽象成特定網(wǎng)絡(luò)限制條件下最小化圖分割間連接度的問(wèn)題；然后應(yīng)用拓?fù)鋱D拉普拉斯矩陣算子的特性，將問(wèn)題進(jìn)一步轉(zhuǎn)發(fā)成標(biāo)準(zhǔn)的矩陣跡最小化問(wèn)題；最后用k-means算法對(duì)求出的分割實(shí)數(shù)解集處理得到最優(yōu)的無(wú)線拓?fù)浞指睢PD算法可以將無(wú)線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分割成具有最小分割度的子網(wǎng)絡(luò)，從而使得各個(gè)子網(wǎng)絡(luò)內(nèi)部相對(duì)連接緊密，而子網(wǎng)絡(luò)之間

6、連接度稀疏。這種分割方法為實(shí)現(xiàn)大規(guī)模無(wú)線網(wǎng)絡(luò)的局部機(jī)會(huì)主義路由協(xié)議提供了先決條件。
　　 最后，針對(duì)大規(guī)模無(wú)線網(wǎng)絡(luò)的應(yīng)用中，機(jī)會(huì)主義路由端到端延時(shí)開(kāi)銷(xiāo)大，節(jié)點(diǎn)生存時(shí)間短的問(wèn)題作深入剖析。提出了GPLS（Graph Partitioningbased Local Scheduling）路由協(xié)議，一種基于無(wú)線子網(wǎng)絡(luò)分割的大規(guī)模無(wú)線網(wǎng)絡(luò)路由協(xié)議。它通過(guò)使用頻譜圖分割SGP算法將無(wú)線拓?fù)浣Y(jié)構(gòu)分割成若干個(gè)子網(wǎng)絡(luò)，在各個(gè)子網(wǎng)絡(luò)內(nèi)部實(shí)現(xiàn)局部機(jī)