應用模擬退火法於多躍式無線網狀網路中聯合路由、排程與可變寬度頻道配置問題之研究

Abstract

無線網狀網路因其低建置成本及覆蓋範圍大等優點而有越來越多的相關研究。本文擬解決在單介面(Single-radio)多頻道(Multi-channel)的無線網狀網路中封包傳送路由(Routing)、排程(Scheduling)及頻道配置(Channel assignment)之聯合問題，其中包含了三個顯著影響封包的傳輸效率的問題：路由問題是找出每個封包的傳送路徑；排程問題解決封包傳送的先後順序；頻道配置問題則與干擾及傳送同步性相關。雖然過去已有文獻針對此三問題的聯合問題作探討與研究，然而過去研究在確切解方法的使用下只能針對小樣本節點的拓樸做實驗與分析，而且也未考慮訊號干擾對傳送速率的影響，致使得求解無效率且不符合實際情況。為此，本文將以模擬退火法來設計一套嶄新的編碼方式，其概念乃將時間分隔為數個極短的時區以表達封包的動態進程狀態。此外，本文將展示一可變頻寬(Variable-width)的頻道分配方法，以期在有限資源的無線頻譜情況下達成最大的同步性及減少頻道重疊(Overlapping channel)所造成的干擾。本研究藉由啟發式演算法來對此問題的可擴展性及解決效率做更進一步改善，期望在短時間內即能尋找出優質的可行解。實驗結果發現，在節點數目少及封包負荷量較小的情況下，本文所提出之模擬退火法能與過去研究所提出的確切解的變數產生法找到相同或近似之解；而在頻道配置的實驗部分，結果顯示可變頻寬方式的確較固定頻寬方式表現優異，並且當流量負荷增加時，差異越是明顯；而在節點數目增加的實驗下，本文所提出之模擬退火法之表現隨著問題複雜度上升而效率下降，但在一定時間內仍可尋得不錯之可行解。

Wireless Mesh Networks (WMNs) is more focused because of the advantages of low implementation costs and wide coverage. In this thesis, we want to solve the joint routing, scheduling and channel assignment problem in the single-radio, multi-channel WMNs. These three problems all relate to the transmission time. Routing problem is to find the transmission paths for the packets; scheduling problem is to plan the order of packets; channel assignment related about interference and concurrency. There are some researches which focus on the joint routing, scheduling and channel assignment problem in the past. However, they can only solve the problem in a small number of nodes’ topology and didn’t consider the effect of signal interference with the exact methods. Their methods are not efficient and do not meet to reality. With regards to this, we will use the concept of Simulated Annealing to design a new coding method which could divide the time into time slots to show us the dynamic process of packets. In addition, this thesis demonstrates a variable bandwidth channel allocation method which achieves a good balance between higher concurrency and better control of interference. We hope to improve the scalability and efficiency of the problem with the help of the meta-heuristic, expecting to find a feasible solution in a short time. The experimental results showed that in a small number of nodes and low traffic load case, the simulated annealing can find a good solution like the exact methods and variable-width channel allocation indeed better than fixed-width method. Besides, in more number of nodes case, the simulated annealing still can find a feasible solution in a short time.