以新型模擬退火演算法加入服務優先限制實現無線網狀網路路由器節點配置之研究

Abstract

無線網狀網路的服務品質主要由網路拓樸的連結量和覆蓋用戶數量所量測決定，在每位網路用戶被服務的機會皆相同的條件下，前述的兩項測量與本研究欲探討的路由器節點配置問題存在著高度相關。然而，在現實生活中，每位用戶支付不同的金額理當來說應該要獲得不同的網路連結量和服務品質，故為了反應前述的實際需求情況，本研究加入服務優先權的限制提出一個相較複雜的無線網狀網路路由器節點配置的問題，此問題針對用戶群額外多考慮了服務優先順序而優先順序值越小的用戶在有限度的無線網狀網路中則享有較高優先級的服務。從原始節點配置問題所延伸出來相較複雜的服務優先限制路由器節點配置問題一般來說是一個計算複雜的問題，因此，本文提出了一個新型模擬退火演算法來求解，此方法是以原模擬退火演算法為基礎加入動量項後的有效解決方法，而加入動量項的目的是提高原降溫機制的速度和解的準確性並預防接受機率函數值的極端變化。最後，本文針對不同網域大小來模擬新型模擬退火法求解，並探討不同參數和退火機制的影響。

The quality of service (QoS) performance of wireless mesh networks (WMNs) is measured by the topology connectivity as well as the client coverage, both of which are related to the problem of router node placement (RNP), in which each mesh client is served as equal. In practice, however, mesh clients with different payments for the network services should be provided by different qualities of network connectivity and QoS. As a result, to respond to the practical requirements, this paper considers a more complicated RNP problem with service priority constraint in WMNs (WMN-RNP) in which each mesh client is additionally associated with a priority value, in which the mesh clients with smaller priority values are served with higher priority. The WMN-RNP problem with service priority constraint inherited from the original RNP problem is computationally intractable in general, and hence this paper further proposes a novel simulated annealing (SA) approach that adds momentum terms to search resolutions more effectively. Momentum terms can be used to improve speed and accuracy of the original annealing schedulers, and to prevent extreme changes in values of acceptance probability function. Finally, this paper simulates the proposed novel SA approach for different-size instances, and discusses the effect of different parameters and annealing schedulers.