無線自組網(wǎng)絡MAC層鏈路調(diào)度算法設計.pdf

1、隨著通訊與計算技術的不斷發(fā)展，無線自組網(wǎng)絡(無線Adhoc網(wǎng)絡)正在發(fā)揮越來越重要的作用，其目標是使信息可以在“所有時間，所有地點”進行交互。它跟目前的蜂窩網(wǎng)絡最大的區(qū)別在于，與蜂窩網(wǎng)絡的集中式結構不同，無線自組網(wǎng)絡采用一種松散的，自組織的結構，這種結構使得無線自組網(wǎng)絡在許多應用中有非常廣闊的前景，例如端對端通信網(wǎng)絡和傳感器網(wǎng)絡。 在無線Adhoc網(wǎng)絡設計中有許多重要問題，其中一個就是如何優(yōu)化物理層，數(shù)據(jù)鏈路層與網(wǎng)絡層的資源(帶

2、寬，時間片等)分配算法，使得在滿足網(wǎng)絡層傳輸速率的同時可以減少整個網(wǎng)絡的資源消耗。在TDMA介質(zhì)訪問控制協(xié)議中，傳輸過程被分為不同的離散時間片來完成，每個要傳輸數(shù)據(jù)包的鏈路分配一個特定時間片。一個對TDMA機制的有效改進方法是空分TDMA機制，它將無線節(jié)點之間的物理距離考慮在內(nèi)，規(guī)定互相不干擾的通訊鏈路可以在相同的時間片內(nèi)傳輸，從而減少了網(wǎng)絡所需時間片的總量，從而提高了單位時間內(nèi)可傳輸數(shù)據(jù)包的數(shù)量，即提高了整個網(wǎng)絡的吞吐量(throug

3、hput)。于是，在目前TDMA機制的無線網(wǎng)絡中，一個非常重要的問題是，在空分TDMA機制下，給定路由信息與網(wǎng)絡負載的條件，通過對MAC層進行鏈路調(diào)度來最大化網(wǎng)絡的吞吐量。 此問題的難點在于，由于其蘊含數(shù)學問題的復雜性，之前的研究工作對于實際規(guī)模的網(wǎng)絡并不適用。絕大部分方法在網(wǎng)絡中有20-30個結點，100-200條鏈路時就需要花幾天甚至更多的時間來尋找最優(yōu)調(diào)度。而這在實際應用中是完全不可行的。因此，非常有必要繼續(xù)研究和探索這一

4、領域的新理論和新方法。 本文通過運籌學中的規(guī)劃理論對此問題進行建模，利用改進后的columngeneration方法對網(wǎng)絡吞吐量進行優(yōu)化。實驗結果表明此方法在實際規(guī)模的網(wǎng)絡中也能在可控制時間內(nèi)得到最優(yōu)解；同時，文中還提出了一種簡單易用的貪心算法，并對這兩種方法進行比較。此外，作為前述問題的延伸，本論文還深入地探討了吞吐量與延時(delay)的組合優(yōu)化問題，目的是設計更加有效而實用的算法來推動STDMA機制在無線多媒體流中的應用。

5、 本論文中有特色的工作體現(xiàn)在如下幾個方面：1.利用setcovering規(guī)劃與columngeneration方法將有效地解決了實際規(guī)模網(wǎng)絡中鏈路時間片分配問題；2.有效改進columngeneration方法的優(yōu)化過程，使其收斂性大大改善，進一步縮短了尋找最優(yōu)調(diào)度所需時間；3.給出了一種適用于大規(guī)模網(wǎng)絡的貪心算法，并對兩種方法進行比較；4.為吞吐量-延時組合優(yōu)化問題指明了可行研究方向，以拓展對這一研究領域的探索，促進STDMA