基于遺傳算法的無線網(wǎng)狀網(wǎng)ＱｏＳ路由算法

摘要：對基于遺傳算法的多QoS約束路由算法進行了研究，實驗結果表明，該算法在無線網(wǎng)狀網(wǎng)中是一種高效的路由算法。

關鍵詞:無線網(wǎng)狀網(wǎng)； 服務質量； 遺傳算法

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2007)11-0248-02

無線網(wǎng)狀網(wǎng)是一種從Ad hoc網(wǎng)絡發(fā)展而來的具有動態(tài)自組織、自愈性的無線網(wǎng)絡，是下一代無線網(wǎng)絡的一種關鍵技術。無線網(wǎng)狀網(wǎng)由兩種無線節(jié)點組成，即網(wǎng)狀路由器(mesh router)和網(wǎng)狀客戶端(mesh client)[1，2]。其中，網(wǎng)格路由器負責維護網(wǎng)格，為移動節(jié)點提供路由功能并構成一個骨干網(wǎng);網(wǎng)格客戶端通常是一些無線節(jié)點，通過多跳的方式與某個網(wǎng)狀路由器建立連接，并接入Internet。這些網(wǎng)格客戶端通常構成一個Ad hoc網(wǎng)絡，雖然它們也具有路由功能，但從硬件平臺和軟件平臺來說，其性能遠不及網(wǎng)格路由器。無線網(wǎng)狀網(wǎng)作為Ad hoc網(wǎng)絡的另一種形式具有很多優(yōu)點，如自組織、自愈性、易構建且成本低等，使無線網(wǎng)狀網(wǎng)成為Ad hoc網(wǎng)絡商業(yè)應用模式而被廣泛接受。

雖然一些學者已提出了大量的Ad hoc網(wǎng)絡路由協(xié)議，但是他們沒有考慮無線網(wǎng)狀網(wǎng)的特點，因此無線網(wǎng)格網(wǎng)路由協(xié)議仍然是一個研究熱點。由于在下一代無線網(wǎng)絡中實時通信(如視頻會議、實時股票信息)的需求增加，基于QoS的路由協(xié)議研究將是一個重點。對于視頻會議、實時股票信息等應用通常需要嚴格的QoS約束，如帶寬、端到端延遲和延遲抖動等，因此本文主要討論無線網(wǎng)格網(wǎng)中基于多QoS約束的路由問題。多QoS約束的路由問題是一個NP難問題[3]，一般對該問題的解決采用啟發(fā)式算法。遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以被廣泛應用于很多學科。一些學者對使用遺傳算法解決多QoS約束的路由問題進行了探討[4]，但在無線網(wǎng)狀網(wǎng)中的應用還較少。

1無線網(wǎng)狀網(wǎng)多QoS約束路由問題

1．1無線網(wǎng)狀網(wǎng)體系結構

在文獻[1，2]中， 給出了無線網(wǎng)狀網(wǎng)的體系結構， 如圖1所示。 無線網(wǎng)狀網(wǎng)的網(wǎng)狀路由器和網(wǎng)狀客戶端都具有路由功能。網(wǎng)狀路由器是無線網(wǎng)狀網(wǎng)的核心，負責路由，一般不具有移動性，并且多個網(wǎng)狀路由器組成網(wǎng)格，并通過接入點(access points)與有線網(wǎng)連接到互聯(lián)網(wǎng)；網(wǎng)狀客戶端一般是一些移動節(jié)點，且使用簡單路由協(xié)議如DSR采用多跳方式與網(wǎng)狀路由器通信。雖然網(wǎng)狀客戶端也具有路由功能，但從硬件、軟件功能及能源上來說其性能都不如網(wǎng)狀路由器。正是由于無線網(wǎng)狀網(wǎng)的這種特點，使其克服了在Ad hoc網(wǎng)絡中需要由資源(如帶寬、能源等)匱乏的移動節(jié)點負責收集路由信息的缺點，從而在無線網(wǎng)狀網(wǎng)中可以實現(xiàn)QoS路由。本文假設一個網(wǎng)狀客戶端打開電源后，首先與距離最近的網(wǎng)狀路由器建立聯(lián)系，并由網(wǎng)狀路由器負責收集當前網(wǎng)絡狀態(tài)；當某個網(wǎng)狀客戶端有一個QoS路由請求時，就將請求信息發(fā)送給網(wǎng)狀路由器，通過網(wǎng)狀路由器計算出合適的路由，然后將路由信息傳送給該客戶端。

1．2網(wǎng)絡模型

3仿真

為了研究算法的性能，采用MATLAB進行了仿真。首先在90 m×120 m的區(qū)域內隨機生成100個節(jié)點，并以通信距離為r=15計算相鄰節(jié)點生成一個鄰接矩陣，然后隨機生成每個節(jié)點的可用帶寬和每條邊的時延及時延抖動；帶寬的取值為[1，10]的整數(shù)，延遲的取值為[10，30]的整數(shù)，時延抖動取值為[0．01，0．1]的小數(shù)。通過反復試驗，當交叉概率大于70%，變異概率在1%左右，初始種群為50，最大遺傳代數(shù)為50時算法性能較好。

表1為在不同QoS需求下，使用基本遺傳算法搜索到的最優(yōu)路徑。從表中可以看出，當條件合理時該算法總是可以找到一條滿足QoS需求的最短路徑，說明算法是收斂的。

4結束語

研究表明遺傳算法用于解決無線網(wǎng)狀網(wǎng)多QoS約束路由問題是一種可行的方法。使用基本遺傳算法具有算法簡單、運行時間短、自組織、自適應和本質并行性等優(yōu)點，同時通過遺傳算法很容易獲得備選路徑，這個特點非常適合移動網(wǎng)絡的特點。但基本遺傳算法的變異概率小，以至于不能驅使搜索轉移，當搜索到局部最優(yōu)時，有時很難轉移到解空間的其他區(qū)域，從而陷入局部最優(yōu)之中，使整個搜索停滯不前；另外，由于遺傳算法中最重要的遺傳算子—交叉算子使種群中的染色體具有局部相似性，父代染色體的信息交換小，容易造成早熟，從而使搜索停滯不前。所以下一步的研究工作是設法改進基本的遺傳算法，使其克服上述缺點，同時應不以算法復雜度和空間復雜度為代價。

參考文獻:

[1]AKYILDIZ I F， WANG Xu－dong. A survey on wireless mesh networks[J].Communications Magazine，2005，43(9):23-30.

[2]BRUNO R， CONTI M， GREGORI E. Mesh network: commodity multihop Ad hoc networks[J]. Communications Magazine，2005，43(3):123－131.

[3]林闖，單志廣，任豐原. 計算機網(wǎng)絡的服務質量[M].北京:清華大學出版社，2004:186-204.

[4]LI La－yuan，LI Chun－lin.QoS multicast routing algorithm based on GA[J]. Journal of Systems Engineering and Electronics， 2004，15(1): 90-97.

[5]王小平，曹立明. 遺傳算法——理論、應用與軟件實現(xiàn)[M].西安:西安交通大學出版社，2002:1-50.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”