资源描述：
《无线mesh网中费用最小且qos约束的网关部署算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6期曾锋等：无线mesh网中费用最小且QoS约束的网关部署算法研究·87·无线mesh网中费用最小且QoS约束的网关部署算法研究曾锋，陈志刚，邓晓衡(中南大学信息科学与工程学院，湖南长沙410083)摘要：基于图的支配集理论，提出图的有限支配集的概念应用于满足QoS约束的无线mesh网网关优化部署，以获取费用最小网关部署方案，进而把QoS约束的费用最小网关部署问题归结为图的最小权有限支配集的问题。为求解图的最小权有限支配集，提出了贪婪算法GREEDY_LDS，该算法以网关的部署性价比作为启发信息，依次挑选部署性价比高的节点加
2、入有限支配集，最后得到权值较小的有限支配集；为得到更加优化的解，利用粒子群优化算法的全局寻优优势，提出粒子群优化算法PSO_LDS，该算法通过阻止粒子在狭小区域运动来防止算法陷入早熟收敛。模拟实验表明，GREEDY_LDS算法执行速度快，当网关候选节点数超过总节点数的17%时，能得到比其他算法更好的结果；PSO_LDS算法以增加执行时间为代价，与GREEDY_LDS和OPEN/CLOSE算法相比，得到的网关部署方案的费用分别减少约15%和9%。关键词：无线mesh网；网关部署；QoS；支配集；贪婪算法；粒子群优化算法中图分类号
3、：TP393文献标识码：B文章编号：1000-436X(2009)06-0080-09Minimum-costgatewayplacementinwirelessmeshnetworkswithQoSconstraintsZENGFeng,CHENZhi-gang,DENGXiao-heng(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China)Abstract:Focusingongatewayoptimalp
4、lacementwithQoSconstraintsinWMNsandaimingtominimizethecostofgatewayplacement,firstly,anewconceptoflimiteddominatingset(LDS)ingraphwaspresentedtoaddressesthegatewayplacementproblem,andtofindthesolutionofminimumplacementcostistofindtheLDSofminimumweightinthegraph.Then
5、,inordertofindtheminimumweightedLDSingraph,agreedyalgorithmGREEDY_LDSwasproposed,inwhichtheratioofLOAD/COSTwasusedasheuristicinformationtofindminimumcostplacementofgateway.Togetfurtheroptimalsolution,aparticleswarmoptimizationalgorithmPSO_LDSwasproposed,inwhichtwopr
6、ematureavoidancemethodswerepresentedtoimprovethealgorithm’sabilityofsearchingforglobaloptimalsolution.Atlast,simulationhasbeendone,andexperimentresultshowsthatGREEDY_LDShaslowercomputingcomplexity,andwhenthenumberofgatewaycandidateismorethan17%ofthetotalnumberofnode
7、,theresultfromGREEDY_LDSisbetterthantheothers.SimulationalsoshowsthatPSO_LDScangetthemoreoptimalsolutionatthepriceofincreasingofexecutingtime.ComparedwithGREEDY_LDSandOPEN/CLOSE,theaveragecostofgatewayplacementisdecreasedbyabout15%and9%respectively.收稿日期：2008-05-27；修
8、回日期：2009-03-10基金项目：国家自然科学基金资助项目(60873082)；中国博士后科学基金资助项目(20060400879)；湖南省教育厅资助项目(08C510)FoundationItems:TheNationalNaturalScienceFoundation
