運用泛型演算法解決多頻道無線網狀網路上頻道配置與繞徑問題

Abstract

近年來，無線網狀網路的應用，對於最後一哩(last-mile)寬頻網際網路存取服務，提供了相當大的原動力。儘管實體層技術不斷的進步，干擾依舊是限制傳統單頻道無線網路頻寬的主要因素。因此，利用多個不重疊頻道與多無線網路介面卡，干擾可有效的降低，無線網路頻寬便能大幅的增加。本篇文章首先提出一個探索式頻道配置與繞徑演算法(LASRR)，用來解決單一流量需求的繞徑問題，並配置頻道於未配置的連線上。基於LASRR演算法，針對不同的流量需求，我們進一步發展出兩種以泛型為基礎的演算法：以攀爬式(Hill-Climbing)為基礎的繞徑與頻道配置演算法(HCRCA)，用於靜態流量需求；以模擬退火(Simulated-Annealing)為基礎的繞徑與頻道配置演算法(SARCA)，用於動態流量需求。前者簡明地利用多次重複執行的動作，以達到最大網路傳輸量的目標，後者亦利用預先定義的評估函式，針對各別來到的需求，能有效降低阻塞的機率。最後，經由實際的模擬並且比較現有的演算法，驗證整體效能的增進。

In recent years, the application of wireless mesh network has provided a quite attractive solution for last-mile broadband internet access service. Despite the unceasing advance in wireless physical-layer technologies, interference is still the major factor that limits the bandwidth in conventional single-channel wireless networks. Therefore, by exploiting multiple non-overlap channels and multiple NICs environment, interference can be decreased and the available bandwidth can be increased substantially. In this study, a heuristic routing and channel assignment algorithm, called Load aware Single Request Routing algorithm (LASRR) is first proposed to route a single traffic request and assigns channels to the links on the route that have not been assigned yet. Base on LASRR, we further develop two generic based algorithms that aim at different traffic requirements; Hill-Climbing based Routing and Channel Assignment algorithm (HCRCA) for static traffic requirement and Simulated-Annealing based Routing and Channel Assignment algorithm (SARCA) for dynamic traffic requirement. While the former simply commits several iterations to maximize the network throughput, the later also utilizes a pre-defined cost functions to minimize the blocking probability for each coming request. Finally, simulation is conducted to demonstrate the performance improvement compared to an existing algorithm.