應用近似動態規劃於具有閘道設計限制的無線網狀網路中進行鏈結排程

Abstract

本研究探討在無線網狀網路中傳送資料封包到遠端客戶的網狀節點，目標著重於 在給定的時間限制內能將資料封包盡量傳送到客戶端。無線網狀網路模型根據不 同規劃目標可以分成許多不同的種類，其中鏈結排程模型透過規劃各階段封包傳 輸鏈結的開啟狀態，企圖在現實中面臨的諸多傳輸限制下，達到有效傳輸封包的 目的。本研究首先參考諸多類型的無線網狀網路鏈結排程模型，比較模型中各種 針對無線網路特性的設計，並觀察這些無線網路模型採用的排程演算法。接著本 研究試圖整合出能包含更多無線網狀網路排程模型特色的新模型，此模型具有更 符合現況的節點規劃資訊存放位置以及可以與網路連接的閘道設計。設計完新模 型後，我們參考文獻中表現優良的排程手法對新模型進行排程以比較優劣，這些 排程手法包含動態規劃和一些啟發式演算法。實驗結果顯示，本研究的新模型除 了能保有諸多無線網路特性之外，上述的排程演算法亦能有效執行，其中近似動 態規劃能有效模擬動態規劃並有優於基因演算法的績效。在大規模網路實驗中， 由於動態規劃的計算規模呈現指數上升，因此我們將以近似動態規劃模擬動態規 劃並與基因演算法進行績效比較。最後結果顯示，在我們設計的新網路模型中， 以近似動態規劃排程的績效仍優於基因演算法。

This study consider that in wireless mesh networks (WMNs), mesh routers transmit multiple packets to the mesh clients with a long distance. Our design for the WMN model aims at transmitting packets to mesh clients within a given time limit. There have been plenty types of WMNs models for different targets, among which the WMN link scheduling model attempts to achieve the goal that can transmit packets efficiently by programming the open-and-shut control of links in WMNs under multi- ple real-world constrains. At first, this study refers many different conventional link scheduling models in WMNs, compares their characteristics, and inspects the algo- rithms that was used to schedule these models, respectively. Next, this study attempts to design a link scheduling model that contains more characteristics of WMNs in the realistic circumstance. This model puts the programming information on a more cor- rect position and has the design of gateways that can connect WMNs to Internet. After completing the new link scheduling model, this study adopts some algorithms which have showed superior performance over the other link scheduling models such as dy- namic programming (DP) and some heuristic algorithms. According to the experiment results, our scheduling model not only can contain several characteristics of WMNs but also can let the above-mentioned algorithms operate efficiently. Among these al- gorithms, approximate dynamic programming (ADP) can simulate the performance of DP efficiently and have a better performance than genetic algorithm (GA). When we extend the scale of our WMNs model, we use ADP to replace dynamic programming due to the concern of computational complexity. According to the experiment results, ADP still shows a superior performance than GA.