标题: 应用近似动态规划于具有闸道设计限制的无线网状网路中进行链结排程
Link Scheduling in Wireless Mesh Networks with Gateway Design Constraint Using Approximate Dynamic Programming
作者: 张书槐
Chang, Shu-Huai
林春成
Lin ,Chun-Cheng
工业工程与管理系所
关键字: 无线网状网路,链结排程,排程,闸道,基因演算法,动态规划,近似动态规划;Wireless mesh networks, link scheduling, gateway, genetic algorithm, dynamic programming, approximate dynamic programming
公开日期: 2013
摘要: 本研究探讨在无线网状网路中传送资料封包到远端客户的网状节点,目标着重于
在给定的时间限制内能将资料封包尽量传送到客户端。无线网状网路模型根据不
同规划目标可以分成许多不同的种类,其中链结排程模型透过规划各阶段封包传
输链结的开启状态,企图在现实中面临的诸多传输限制下,达到有效传输封包的
目的。本研究首先参考诸多类型的无线网状网路链结排程模型,比较模型中各种
针对无线网路特性的设计,并观察这些无线网路模型采用的排程演算法。接着本
研究试图整合出能包含更多无线网状网路排程模型特色的新模型,此模型具有更
符合现况的节点规划资讯存放位置以及可以与网路连接的闸道设计。设计完新模
型后,我们参考文献中表现优良的排程手法对新模型进行排程以比较优劣,这些
排程手法包含动态规划和一些启发式演算法。实验结果显示,本研究的新模型除
了能保有诸多无线网路特性之外,上述的排程演算法亦能有效执行,其中近似动
态规划能有效模拟动态规划并有优于基因演算法的绩效。在大规模网路实验中,
由于动态规划的计算规模呈现指数上升,因此我们将以近似动态规划模拟动态规
划并与基因演算法进行绩效比较。最后结果显示,在我们设计的新网路模型中,
以近似动态规划排程的绩效仍优于基因演算法。
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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070053344
http://hdl.handle.net/11536/73850
显示于类别:Thesis