计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2014年
2期
344-355
,共12页
无线Mesh网络%Mesh路由器部署%用户带宽需求%混合整数线性规划%最大流
無線Mesh網絡%Mesh路由器部署%用戶帶寬需求%混閤整數線性規劃%最大流
무선Mesh망락%Mesh로유기부서%용호대관수구%혼합정수선성규화%최대류
wireless mesh networks%mesh router placement%bandwidth requirements%mixed integer linear programming%maximum flow
无线Mesh网络是移动互联网的一种重要接入方式,如何合理、高效地部署Mesh路由器(Mesh Router,MR),从而以较低的部署成本获得较好的网络性能,是当前的研究热点.文中首先给出一种分层的部署场景模型及相关假设,并在此基础上利用混合整数线性规划方法对MR部署问题进行形式化描述;然后提出一种基于网络流的MR部署贪心算法NF Greedy,该算法以迭代的方式从MR候选位置集中选择权重最大的节点进行相应的节点部署,其中节点权重定义为当前网络可满足的最大用户带宽需求的平均增量,可利用网络流方法进行求解;最后通过一系列仿真实验将NF Greedy算法与现有算法进行对比,实验结果表明该算法与基于MILP的算法相比,虽然所部署的MR数量略多,但是能适用于较大规模的WMN;而与启发式的ILSearch算法相比,则大大减少了所部署MR的数量.
無線Mesh網絡是移動互聯網的一種重要接入方式,如何閤理、高效地部署Mesh路由器(Mesh Router,MR),從而以較低的部署成本穫得較好的網絡性能,是噹前的研究熱點.文中首先給齣一種分層的部署場景模型及相關假設,併在此基礎上利用混閤整數線性規劃方法對MR部署問題進行形式化描述;然後提齣一種基于網絡流的MR部署貪心算法NF Greedy,該算法以迭代的方式從MR候選位置集中選擇權重最大的節點進行相應的節點部署,其中節點權重定義為噹前網絡可滿足的最大用戶帶寬需求的平均增量,可利用網絡流方法進行求解;最後通過一繫列倣真實驗將NF Greedy算法與現有算法進行對比,實驗結果錶明該算法與基于MILP的算法相比,雖然所部署的MR數量略多,但是能適用于較大規模的WMN;而與啟髮式的ILSearch算法相比,則大大減少瞭所部署MR的數量.
무선Mesh망락시이동호련망적일충중요접입방식,여하합리、고효지부서Mesh로유기(Mesh Router,MR),종이이교저적부서성본획득교호적망락성능,시당전적연구열점.문중수선급출일충분층적부서장경모형급상관가설,병재차기출상이용혼합정수선성규화방법대MR부서문제진행형식화묘술;연후제출일충기우망락류적MR부서탐심산법NF Greedy,해산법이질대적방식종MR후선위치집중선택권중최대적절점진행상응적절점부서,기중절점권중정의위당전망락가만족적최대용호대관수구적평균증량,가이용망락류방법진행구해;최후통과일계렬방진실험장NF Greedy산법여현유산법진행대비,실험결과표명해산법여기우MILP적산법상비,수연소부서적MR수량략다,단시능괄용우교대규모적WMN;이여계발식적ILSearch산법상비,칙대대감소료소부서MR적수량.
