Enhanced Clustering Techniques for Hyper Network Planning using Minimum Spanning Trees and Ant-Colony Algorithm | Science Publications

Journal of Computer Science

Lamiaa F. Ibrahim¹ 

关键词: Multi Service Access Node (MSAN);    agglomerative algorithm;    clustering techniques;    network planning;    cable layout network;    short path;    Minimum Spanning Tree (MST);    ant-colony algorithm;    meta-heuristic;    NetPlan algorithm;   

DOI  :  10.3844/jcssp.2011.440.447

学科分类：计算机科学（综合）

来源: Science Publications

【 摘 要 】

Problem statement: The process of network planning is divided into two sub steps. Thefirst step is determining the location of the Multi Service Access Node (MSAN). The second step is theconstruction of subscriber network lines from MSAN to subscribers to satisfy optimization criteria anddesign constraints. Due to the complexity of this process artificial intelligence and clusteringtechniques have been successfully deployed to solve many problems. The problems of the locations ofMSAN, the cabling layout and the computation of optimum cable network layouts have beenaddressed in this study. The proposed algorithm, Clustering density-Based Spatial of Applicationswith Noise original, minimal Spanning tree and modified Ant-Colony-Based algorithm (CBSCAN-SPANT),used two clustering algorithms which are density-based and agglomerative clustering algorithmusing distances which are shortest paths distance and satisfying the network constraints. This algorithmused wire and wireless technology to serve the subscribers demand and place the switches in a realoptimal place. Approach: The density-based Spatial Clustering of Applications with Noise original(DBSCAN) algorithm has been modified and a new algorithm (NetPlan algorithm) has been proposedby the author in a recent work to solve the first step in the problem of network planning. In the presentstudy, the NetPlan algorithm is modified by introduce the modified Ant-Colony-Based algorithm tofind the optimal path between any node and the corresponding MSAN node in the first step of networkplanning process to determine nodes belonging to each cluster. The second step, in the process ofnetwork planning, is also introduced in the present study. For each cluster, the optimal cabling layoutfrom each MSAN to the subscriber premises is determining by introduce the Prime algorithm whichconstruct minimal spanning tree. Results: Experimental results and analysis indicate that theCBSCAN-SP-ANT algorithm was effective, leads to minimum costs for network construction andmake the best grade of service. Conclusion: Using mobile network to serve the area with low densityis decreasing the cost of design the fixed wire network. Also, using the modified ANT algorithm andminimum spanning tree, are helping to construct the cable layout from each MSAN to subscriberswhen the network is complicated and the number of intersections and streets are large.

【 授权许可】

Unknown