基於社群之粒子群優化法用於無線網際網路中具社群感知之動態路由器節點配置問題

Abstract

無線網狀網路是一種由網狀客戶與網狀路由器所構成的通訊網路。此網路的主要特色是維持網路中網狀客戶之間的連線完整，當有某個網狀路由器失效時，原本透過此網狀路由器進行通訊的路徑會重新找一條替代路徑，以確保通訊不被中斷。由於在現實生活中，客戶跟客戶會有集中在一起的這種群聚現象且路由器之間也可以直接或間接溝通，形成一種社群網路。因此，本文研究在動態無線網狀網路中具社群感知之路由器配置問題，社群感知即為路由器之間會互相溝通來感知以群為單位移動的客戶，對客戶提供網路連接的服務；而路由器配置問題的目標是找出每一個時間點的路由器配置使得網路拓樸圖的連結率和被路由器服務到的網狀客戶數量最大化。 用先前研究的粒子群優化法在求解時，會有許多客戶並未被路由器服務到的情形，這情形的產生是因為路由器的配置尚未調整到較佳的位置，而下個時間點以群為單位移動的客戶又往別的位置移動走。因此我們提出一個新式的粒子群優化法：基於社群之粒子群優化法，其中加入新的向量來改善先前研究的粒子群優化法，此向量是利用屬於同一子群集路由器間可以相互溝通的關係對客戶的群聚移動行為做出快速的調整，讓已達到服務上限的路由器能被其他路由器支援，以增進網路的通訊效能。我們解的表現可以模擬網狀路由器如何對網狀客戶的群聚移動作出反應，持續地調整網狀路由器的位置。實驗是在不同大小的網路規模下，將客戶分為兩群或三群並設計群聚移動的路線，而初始位置以均勻分配產生。接著與先前研究的粒子群優化法做比較。實驗結果顯示提出的方法在動態情境下，能有效地減少未被路由器服務到的網狀客戶數量，並且讓整體網路拓樸的連結率更大。

Wireless mesh network is a communication network consisting of mesh routers and mesh clients. The main characteristic of this network is the ability to maintain an active network connection path between each mesh client pair. When a mesh router fails, an alternative path will be created to ensure communication is not interrupted. Real world usage patterns indicate clustering effects amongst clients of mesh clients and through mesh routers, can connect and communicate with each other directly, forming a social network. Thus, the purpose of this research is to develop social-based PSO algorithms for social-aware dynamic router node placement in wireless mesh networks. The concept of social-aware refers to routers that communicate with each other to sense movements by clusters of clients in order to provide them with internet access services. The role of the router node placement problem is to maintain up to date router information to map with the latest network topology as well as connectivity rates to maximize the number of clients serviced by the mesh router. Prior research that involve using particle swarm optimization method in solving the router node placement problem results in many clients that cannot receive network services. The main cause of this issue is the result of routers not being placed at optimal locations and moving clusters of clients. Therefore, we devise a new particle swarm optimization method: based on a Social-based PSO Algorithm with an additional vector based mechanism to improve upon prior research that are based on particle swarm optimization methods. The vector based mechanism utilizes the property that enables router to router communications to continuously make rapid adjustments in response to movements by clusters of clients so that routers that have reached their maximum limit can enhance the network performance by offloading clients to other routers. The experiment was conducted on networks of various sizes, where clients are divided into two or three groups. Cluster of clients move according to planned paths and their initial positions are uniformly distributed. Next our Social-based PSO Algorithm is compared with prior particle swarm optimization methods. Experimental results show that the use of the Social-based PSO Algorithm in a dynamic scenario can effectively reduce the number of clients not able to receive the service, so that the overall network topology coverage and connectivity rates are greater using this algorithm.