基于機會主義路由的無線Ad Hoc網絡關鍵技術研究.pdf

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

2、機制及大規(guī)模無線網絡中的應用問題進行了深入研究，獲得了若干具有創(chuàng)新性的成果，主要的工作和創(chuàng)新點包括以下幾個方面：
　　 第一，針對目前的機會主義路由協議所使用的路由參數不能準確衡量當前節(jié)點到目的節(jié)點機會主義期望傳輸數的問題，本文通過用隨機游走模型對機會主義路由建模的方法，建立了一套研究機會主義路由傳輸的理論。并且用這套理論將求解機會主義路由的期望傳輸次數問題轉化為計算隨機游走模型狀態(tài)轉移次數的問題，從而在理論上計算出符合機會主義

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

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

5、（SGP算法，Spectral Graph Partitioning Algorithm）。首先，使用最優(yōu)化理論將拓撲分割問題抽象成特定網絡限制條件下最小化圖分割間連接度的問題；然后應用拓撲圖拉普拉斯矩陣算子的特性，將問題進一步轉發(fā)成標準的矩陣跡最小化問題；最后用k-means算法對求出的分割實數解集處理得到最優(yōu)的無線拓撲分割。SPD算法可以將無線網絡拓撲結構分割成具有最小分割度的子網絡，從而使得各個子網絡內部相對連接緊密，而子網絡之間

6、連接度稀疏。這種分割方法為實現大規(guī)模無線網絡的局部機會主義路由協議提供了先決條件。
　　 最后，針對大規(guī)模無線網絡的應用中，機會主義路由端到端延時開銷大，節(jié)點生存時間短的問題作深入剖析。提出了GPLS（Graph Partitioningbased Local Scheduling）路由協議，一種基于無線子網絡分割的大規(guī)模無線網絡路由協議。它通過使用頻譜圖分割SGP算法將無線拓撲結構分割成若干個子網絡，在各個子網絡內部實現局部機