Minimum-cost gateway placement in wireless mesh networks with QoS constraints
Focusing on gateway optimal placement with QoS constraints in WMNs and aiming to minimize the cost of gateway placement,firstly,a new concept of limited dominating set（LDS） in graph was presented to addresses the gate-way placement problem,and to find the solution of minimum placement cost is to fin...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2009-01-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/74652207/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Focusing on gateway optimal placement with QoS constraints in WMNs and aiming to minimize the cost of gateway placement,firstly,a new concept of limited dominating set（LDS） in graph was presented to addresses the gate-way placement problem,and to find the solution of minimum placement cost is to find the LDS of minimum weight in the graph.Then,in order to find the minimum weighted LDS in graph,a greedy algorithm GREEDY<sub>L</sub>DS was proposed,in which the ratio of LOAD/COST was used as heuristic information to find minimum cost placement of gateway.To get further optimal solution,a particle swarm optimization algorithm PSO<sub>L</sub>DS was proposed,in which two premature avoidance methods were presented to improve the algorithm’s ability of searching for global optimal solution.At last,simulation has been done,and experiment result shows that GREEDY<sub>L</sub>DS has lower computing complexity,and when the number of gateway candidate is more than 17% of the total number of node,the result from GREEDY<sub>L</sub>DS is better than the others.Simulation also shows that PSO<sub>L</sub>DS can get the more optimal solution at the price of increasing of executing time.Compared with GREEDY<sub>L</sub>DS and OPEN/CLOSE,the average cost of gateway placement is decreased by about 15% and 9% respectively. |
|---|---|
| ISSN: | 1000-436X |