摘要
近年来,随着用户对无线网络需求的不断提高,各种无线网络的大量技术得到了迅速发展,其中无线Mesh网(Wireless Mesh Netwok,WMN)作为“最后一英里”(Last Mile)的无线宽带接入的关键技术日益成为热门的研究课题。WMN是一种网状的“多点—多点”结构的无线多跳网络,它打破了传统无线局域网(Wireless Local Area Network,WLAN)的“点—多点”的结构,将WLAN的“热点”(Hot Spot)概念推广到高覆盖率的“热区”(Hot Area)。WMN具有许多潜在的突出的优点,如高覆盖率、高带宽高容量、低成本的基础设施投入等,这也吸引了越来越多的研究机构和政府部门投入大量的人力物力对其关键技术进行研究。
大量研究表明要发挥WMN的巨大潜能必须要解决很多极具挑战性的问题,如有限的网络容量、路由、QoS、安全等,以IEEE 802.11为例,研究表明在无线多跳环境中,802.11的MAC协议带来的冲突和不公平性使网络的容量低到令人吃惊的地步,某些情况下甚至会导致个别多跳流被“饿死”(Starvation),因而WMN中端到端流的公平性是本文集中研究的问题,着重在基于价格的流量控制的(Price-based Flow Control,PFC)的框架下研究如何改进现有协议以适应WMN的特征来提高WMN的传输性能,具体内容包括:WMN中PFC框架描述,不同公平性准则下的基于价格控制的分布式算法以及跨层设计方案,WMN作为无线宽带接入的无线回程网(Wireless Backhaul Networks,WBN)上的公平性参考模型等。
本文在第1章首先对WMN的相关背景以及论文的研究目标和方法进行了综述,在Kelly和Low等人的工作基础上给出了WMN中基于价格的流量控制框架,用以研究架构式WMN中端到端流的公平性。第2章通过对WMN中IEEE802.11的MAC协议和TCP协议采用有线状态的Markov链建模分析,指出影响公平性的几个重要因素以及在实现公平性目标时实际改进的方面;最后讨论了数据网络中几种经典的的公平性准则下的有效性与公平性的关系。这些分析为WMN中的公平性方案设计提供了指导方针。
公平性问题本质上属于一个优化问题,其目标函数是各种公平性准则,约束条件是有限的网络资源,基于此WMN中PFC框架下的公平性问题可数学描述为含约束条件的非线性规划问题。本文第3章介绍了关于数学优化的一些重要理论,包括线性规划、整数规划、目标规划、非线性优化、对偶规划、Lagrange松弛、梯度及子梯度法等,这些理论为实际设计WMN中的公平性方案、算法提供了坚实的数学理论基础。
PFC框架中核心的控制变量是“价格”(Price),在经济学中价格是控制商品供求关系的一只无形的手,市场运行的过程是一个供求平衡向另一个供求平衡不断变化的动态过程,类似的,WMN中的流量控制也可建模为一个市场运行过程,由于无线环境的开放性,一定范围内共享信道的无线链路不能同时工作,否则将会发生冲突,这些互相冲突的无线链路的集合构成了WMN中的一个虚拟实体:集群(Clique),因此WMN中PFC框架下的“供”是集群的容量,“求”是集群内各链路上流量之和,供过于求集群价格下跌,供不应求集群价格上涨。本文在第4章中介绍了PFC框架的基本概念,并将不同的公平性准则下的优化问题归纳为社会福利最大化和最大最小公平两类,针对WMN中的这两类优化问题本文提出了在PFC框架下的通过双重SumNet和双重MaxNet控制模式来实现分布式算法,给出了一种自适应步长的双重MaxNet分布式算法实现最大最小公平性速率控制。
WMN中公平性问题是一个典型的跨层问题,它与物理层、MAC协议、TCP协议以及路由协议均密切相关,第5章首先介绍了WMN中的跨层设计的原则和方法,然后描述了PFC框架下非协作式和协作式两种跨层设计方案,最后提出了MAC约束下实现最大最小公平性目标的跨层设计方案,本文的跨层方案仅针对MAC层和传输层之间的跨层协作。
无线网络中由于无线信道的时变性,追求端到端流的时间片公平性比吞吐量公平性可以更好地折中系统的有效性和公平性的矛盾,WBN作为一种特殊的无线多跳网络,其上的传输接入点(Transit Access Point,TAP)为无线用户提供到有线Internet的多跳接入,各TAP上的聚集流之间须满足公平性。本文在第6章提出WBN中一种含权支流的公平性参考模型,该模型定义了四大目标:聚集流、时间片、空间差异、空间利用,为各TAP聚集流内支流分配不同的权重,该模型可在PFC框架下通过分布式算法实现。
本文对WMN中PFC框架下的端到端流的公平性问题做了一些有益的尝试,但在该领域中还有很多值得我们进一步深入研究的课题,如跨层路由协议、基于认知无线电(Cognitive Radio,CR)的认知Mesh网上资源分配等,第7章对未来进一步研究方向做了一些展望。
In recent years,as the user demands for wireless networks grow,many technologies for different kinds of wireless networks developed rapidly.Wireless Mesh Networks(WMN)has emerged as a key technology for wireless broadband last-mile access.As a kind of wireless multi-hop networks with new multipoint to multipoint mesh architecture,it is different from the traditional Wireless Local Area LAN(WLAN)with point to multipoint architecture.WMN extends the concept of hot spot of WLN to large coverage level hot area.Its advantages are numerous and include:high coverage level,excellent spectral efficiency and capacity,low initial investments and so on.Due to these advantages,more and more research organizations and government departments draw a lot of attention on the key technical issues of WMN.
There are many researches on how to bring the great potential of WMN into full play and lots of challengeable technical issues still exist in this field,such as finite network capacity,routing protocol,QoS,safety and so on.For example,some research results show the capacity of wireless multi-hop networks becomes startlingly low because of the contend and unfairness of IEEE 802.11 MAC protocol, sometimes the flow with much more hops will even be starved.In this dissertation we study on the fairness flow control for end-to-end flow in WMN,and focus on how to improve the existing protocols under the framework of price-based flow control(PFC)to make it adapt to the characteristics of WMN resulting in better performance.There are three main contents in this dissertation,include the framework of PFC in WMN,the distributed algorithms and schemes of cross-layer design,the fairness reference model for Wireless Backhaul Networks(WBN).
In chapter l,the related background of WMN and the study object and method of this dissertation were firstly introduced.Based on the work of Kelly and Low,we provided a PFC framework of WMN which was used to realize the fairness of end-to-end flow in WMN.In chapter 2,we analyzed the MAC protocol and TCP protocol of IEEE 802.11 by modeling with finite-state Markov chain.Then several key influence factors on unfairness were given and some advice to improve fairness was proposed.Finally we discussed the relationship between fairness and efficiency under different fairness criteria.All of these provide a guideline for fairness design in WMN.
In nature fine fairness problem belongs to an optimization problem.Its objective function is the different fairness criteria and the constraint condition is the finite network resource.So under the PEC framework the fairness problems in WMN can be mathematically described as the problems of Non-Linear Programming (NLP).Chapter 3 introduced some important theory about optimization,include Linear Programming.Integer Programming,Goal Programming,Dual Programming, NLP,Lagrange Relaxation.Gradient method,Sub-Gradient method.These theories of optimization provide a solid mathematical foundation for fairness algorithm design in WMN.
In the approach of this dissertation the central control variable under PFC framework is price.In economics,price is an invisible hand which is taken as a tool to control supply and demand on the market for certain goods.A market process is a dynamic process which develops from one equilibrium to another equilibrium. Indeed,price-based flow control in WMN can be modeled as a market process with the goal to achieve an equilibrium.Because wireless environment is open,in a certain area wireless links which share common channel can not be simultaneously active,otherwise there will be conflict among them.The set of wireless links that conflict with each other forms a virtual entity of WMN:Clique.So under PFC framework in WMN the equilibrium is that between the supply in form of the clique capacity and the demand for end-to-end flow rate allocation.Supply exceeding demand makes the price of clique decrease and demand exceeding supply makes the price increase.Chapter 4 introduced the basic concept of PFC framework and then summarized the optimization problems for different fairness criteria into two categories:Social Welfare Maximization and Max-Min fairness.To resolve these two kinds of optimization problems we proposed a fully distributed algorithm by using Double-Level SumNet control mode and Double-Level MaxNet control mode under PFC framework.Furthermore a Double-Level MaxNet algorithm with adaptive stepsize was given to realize max-min fairness in WMN.
The fairness problem in WMN is a typical cross-layer problem,correlating with physical layer.MAC protocol.TCP protocol and routing protocol.In chapter 5,at first we introduced the principles and methods of cross-layer design in WMN,and then described two different cross-layer schemes under PFC framework:cooperative and non-cooperative cross-layer schemes.Finally a cross-layer scheme under MAC constraints was proposed for max-min fairness.The cross-layer schemes in this dissertation only considered the cross-layer cooperation between MAC layer and Transport layer.
In wireless networks,due to the time variation of wireless channel,time rather than throughput should be considered as the basic network resource that needs to be fairly shared.It obtains a good tradeoff between fairness and efficiency.As a special wireless multi-hop network,WBN provides a multi-hop access through the Transit Access Points(TAP)to wired Internet for wireless users.The targeted granularity of fairness must be a TAP-aggregated flow.So a weighted sub-flow fairness reference model for WBN was given in chapter 6,which defined four objectives:temporal fairness,TAP-aggregated flow.spatial reuse and spatial bias.If the weights of sub-flows of different TAP-aggregated flow are allocated,the model can be easily realized by distributed algorithms under PFC framework.
The dissertation was in an attempt to make some things right on fairness problems under PFC framework in WMN.Many issues for further study still exist in this field,such as cross-layer routing protocol,the resource allocation in cognitive mesh networks based on Cognitive Radio.They are pointed out in Chapter 7.
引文
[1]Wiliam S,2005.Wireless communication & network(the second Edition)[M]Prentice Hall,Cambridge University Press
[2]Sesay S,Yang Z,He J.2004.A survey on Mobile Ad Hoe Wireless Netwoks,[J]Information Technology Journal.3(2):168-175
[3]Ian F.Akyildiz.WellJan Su.Yogesh Sankarasubramaniam,etl.2002.A survey on Sensor Networks,[J]IEEE Communication Magazine,40(8):102-114
[4]Akyildiz I.F.,Xudong W..2005.A survey on wireless mesh networks.[J]IEEE Communications Magazine,43(9):p.S23-S30.
[5]Bruno R,Conti M.and Gregori E,2005.Mesh networks:commodity multihop ad hoc networks.[J]IEEE Communications Magazine,43(3):p.123-131.
[6]Whitehead P,2000.Mesh networks:a new architecture for broadband wireless access systems.[C]Radio and Wireless Conference,2000,RAWCON 2000.IEEE,pp.43-46
[7]方旭明等,2006.下一代无线因特网技术:无线Mesh网络,[M]人民邮电出版社
[8]Ghosh,S,Basu K,Das S.K.,2005.An architecture for next-generation radio access networks.[C]Network,IEEE.19(5):p.35-42.
[9]Karrer R,Sabharwal A,Knightly E.2004.Enabling Large-Scale Wireless Broadband:The Case for TAPs.[C]ACM SIGCOMM Comp.Commun.Rev.34(1):27-34
[10]Jangeun,J,Sichitiu M.L.,2003.The nominal capacity of wireless mesh networks.Wireless [C]Communications,IEEE,10(5):p.8-14.
[11]P.Gupta,P.R.Kumar,2000.The capacity of wireless networks,IEEE Trans.on Information Theory,46(2):388-404
[12]Gupta P,Gray R,Kumar R R,An experimental scaling law for ad hoc networks,http://www,black.csl.uiuc.edu/~prkumar
[13]Jane-Hwa H,Li-Chun W,Chung-Ju C,2005.Coverage and capacity of a wireless mesh network.[C]International Conference on Wireless Networks,Communication and Mobile Computing,Vol.1 458-463.
[14]Nomoto S,Asano M,Ito Y,et al.2004.Fully adaptive MODEM up to 1024 QAM for 26GHz broadband fixed wireless access systems with mesh topology.[C]Wireless Communication Systems.1st International Symposium on,pp 100-104.
[15]Alicherry M,Bhatia R,Li L.E.,2006.Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks.[J]Selected Areas in Communications.IEEE Journal on,24(11):1960-1971.
[16]Kishi Y,Tabata K.Konishi S.Nomoto S.2003.A proposal of an adaptive channel allocation and traffic engineering algorithm in multi-hop mesh networks for broadband fixed wireless access.[C]IEEE Wireless Communications and Networking,WCNC Vol.2:1043-1048.
[17]Talooki V.N.,Ziarati K.2006.Performance Comparison of Routing Protocols For Mobile Ad Hoc Networks.[C]APPC'06.pp1-5
[18]Chunhui Z,Lee M.J.,Saadawi T,2005.On the route discovery latency of wireless mesh networks.[C]IEEE CCNC'05.pp 19-23
[19]Draves R,Padhye J.Zill B,2004.Comparison of Routing Metrics for Static Multi-Hop Wireless Networks.[C]SIGCOMM'04.Portland,Oregegon,USA.
[20]Draves R,Padhye J.Zill B,2004.Routing in Multi-Radio,Multi-Hop Wireless Mesh Networks,ACM Annual int'l.[C]Mobicom'04,pp.114-128
[21]Xu S,Saadawi T.2001.Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks?[J]Communications Magazine,IEEE,39(6):p.130-137.
[22]Fu Z,Zerfos P,Luo H,et al.2003.The impact of multihop wireless channel on TCP throughput and loss,[C]Proc.IEEE Infocom,vol 3:1744-1753
[23]Gambiroza V,Sadeghi B,Knightly E,2004.End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks.[C]Proc.Mobicom'04,287-301
[24]John B,Daniel A.Sanjit B.et al.2005.Architecture and Evaluation of an Unplanned 802.11b Mesh Network.[C]Mohicom'05 pp 31-42
[25]Yuan S,Irfan S,Elizabeth M.et al.2005.An Experimental Study of Multimedia Traffic Performance in Mesh Networks,[C]Proceeding of the International Workshop on Wireless Traffic Measurement and Modeling,Seattle,WA
[26]Lei Z,Shoubao Y,Weifeng S,2006.Markov-Based Analytical Model for TCP Unfairness over Wireless Mesh Networks.[C]Computer and Computational Sciences,IMSCCS '06.First International Multi-Symposiums on,vol.2,642-648,
[27]Baochun L.2005.End-to-End Fair Bandwidth Allocation in Multi-Hop Wireless Ad Hoc Networks.[C]25th IEEE International Conference on Distributed Computing Systems,ICDCS 2005,pp471-480.
[28]Mo J,Walrand J,2000.Fair end-to-end window-based congestion control.Networking,[J]IEEE/ACM Transactions on,8(5):pp556-567.
[29]Zuyuan F,Bensaou B,Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks.[C]IEEE Infocom 2004,Vol 2,pp1284-1295.
[30]Lijun C,Low S.H.,Doyle J.C.,2005.Joint congestion control and media access control design for ad hoc wireless networks.[C]Proc.of IEEE Infocom,Miami,3:2212-2222.
[31]Lijun C,Low S.H..Chiang M,Doyle J.C.,2006.Cross-Layer Congestion Control,Routing and Scheduling Design in Ad Hoc Wireless Networks,[C]INFOCOM 2006.25th IEEE International Conference on Computer Communications.Proceedings,pp.1-13
[32]Tang K,Gerla M.2003.Fair sharing of MAC under TCP in wireless ad hoc networks,[C]Proc.IEEE MMT
[33]Xu K,Gerla M,Qi L,Shu Y,2003.Enhance TCP fairness in ad hoc wireless networks using neighborhood RED.[C]Proc.ACM Mobicom pp16-28
[34]Yi Y,Shakkottai S.2004.Hop-by-Hop congestion control over a wireless multi-hop network[C]Proc.IEEE Infocom,vol 4:2548-2558
[35]Low S H,Lapsley D E.1999.Optimization flow control 1:basic algorithm and convergence [J]IEEE/ACM Transactions on Networking(TON),7(6):861-874
[36]Kelly F.R,Maulloo A,Tan D.1998.Rate control for communication networks:shadow prices,proportional fairness and stability.[J]Journal of the Operational Research Society,49(3):237-252
[37]The Network Simulator-ns-2,http://www.isi.edu/nsnam/ns/
[38]Andrew S.Tanenbaum著,潘爱民译,2006.计算机网络(第4版)[M]清华大学出版社
[39]Allman M,Paxson V,Stevens W,1999.TCP Congestion Control,IETF RFC2581,
[40]Bertsekas D and Gallager R,1992.Data Netwokrs.2nd edition,[M]Prentice Hall
[41]Jeffrey M.Jaffe,1981.Bottleneck flow control.[J]IEEE/ACM Transactions on Networking,Com-29(7):954-962
[42]Hayden H.P.,1981.Voice flow control in integrated packet networks.[D]Master's thesis,MIT
[43]Kelly E P.,1997.Charging and rate control for elastic traffic.[J]European Transactions on Telecommunications,8:33-37
[44]Massoulie L,Roberts J,2002.Bandwidth sharing:objectives and algorithms.[J]Networking,IEEE/ACM Transactions on,10(3):p.320-328.
[45]Jain R,Chiu D,Hawe W.A quantitative measure of fairness and discrimination for resource allocation in shared computer systems[R]DEC Research Report TR-301,1984
[46]Tang A,Wang J.Low S.H..2004.Is fair allocation always inefficient[C]INFOCOM 2004.Twenty-third AnnualJonint Conference of the IEEE Computer and Communications Societies,vol 1:7-11
[47]Bertsekas D,1999.Nonlinear Programming,2nd edition,[M]Athena scientific
[48]Boyd S.and Vandenberghe.2004.Convex Optimization,[M]Cambridge University Press,
[49]甘应爱,田丰,2006.运筹学(第三版)[M]清华大学出版社
[50]Winston W 著,杨振凯,周红等译2006.运筹学应用范例与解法(第四版)[M]清华大学出版社
[51]Gibbens R.J..Kelly F.P.,1999.Resource pricing and the evolution of congestion control.[C]Automatic,35:1969-1985,
[52]Low S.H.,2003.A duality model of TCP and queue management algorithm.[J]IEEE/ACM Transications on Networking,11(4):525-536
[53]Adam S,1904.An Inquiry into the Nature and Causes of the Wealth of Nations.[M]Methuen and Co.Ltd,London,5th edition
[54]Floyd S,Jacobson Van,1993.Radorn early detection gateways for cogestion avoidance.[J]IEEE/ACM Transications on Networking,1(4):397-413
[55]Ramakrishnan KK,Floyd S,Black D,2001.The addition of explict cogestion notification (ECN)to IP.RFC 3168,IETF
[56]Athuraliya S,Li V.H.,Low S.H.,et al.2001.REM:active queue management.[C]IEEE Network,15(3):48-53
[57]Kunniyur S,Srikant R..2001.Analysis and design of an adaptive virtual queue algorithm for active queue management.[C]Proceedings of ACM Sigcomm,pp:123-134
[58]Wydrowski B,Zukerman M,2003.MaxNet:a new network congestion control architecture for max-min fairness[C]IEEE ICC.Alaska,1:132-136
[59]Lawrence S.B.,Larry L.P.,1995.TCP Vegas:end-to-end congestion avoidance on a global Interact.[J]IEEE Journal on Selected Areas in Communications,13(8):1465-1480
[60]Cheng J,David X.W.,Low S.H.,2004.FAST TCP:Motivation,Architecture,Algorithms,Performance.[C]Proceedings of IEEE INFOCOM 14(6):1246-1259
[61]Wydrowski B,Zukerman M,2002.QoS in best-effort networks.[J]IEEE Communications Magazine,40(12):44-49
[62]Jeffrey K.Mackie-Mason.Hal R.Varian.1995.Pricing congestible network resources.[J]IEEE Journal of Selected Areas in Communications,13(7):1141-1149
[63]Wydrowski B,Andrew L.L.H.,Zukerman M.,2003.MaxNet:a congestion control architecture for scalable networks.[J]IEEE Communications Letters 7(10):p.511-513.
[64]Wydrowski B,Zukerman M,2002.MaxNet:a congestion control architecture.[J]IEEE Communications Letters,6(11):512-514.
[65]R.Diestel,1997.Graph Theory,[M]Springer-verlag
[66]王树禾,1990.图论及其算法,[M]中国科学技术大学出版社
[67]Bar-Noy A,Mayer A.Schieber B,Sudan M,1998.Guaranteeing fair service to persistent dependent tasks.[C]SLAMJ.COMPUT..27(4):1168-1189
[68]Hajek B,Sasaki G,1998.Link scheduling in polynomial time[J]IEEE Transactions on Information Theory,34(5):910-917
[69]L.H.Andrew,D.Helm,S.H.Low.et al.2005.Weighted max-min fair flow control.[C]IEEE INFOCOM
[70]秦晓卫,徐佩霞,2007.无线Mesh网中基于最大价格的最大最小公平性速率分配,[C]2007年通信理论与信号处理年会,pp:116-123
[71]Shakkottai S,Rappaport T.S,,Karlsson RC.,2003.Cross-layer design for wireless networks,[J]Communications Magazine.IEEE,41(10):74-80
[72]徐明霞,2007.Ad Hoc例络中的时分址接入及跨层没计研究,[D]浙江大学博士论文
[73]Srivastava V,Motani M,2005.Cross-layer design:a survey and the road ahead.[J]IEEE Communications Magazine,43(12):112-119.
[74]Lin X,Shroff N.B.,Srikant R.,2006.A Tutorial on Cross-layer Optimization in Wireless Networks.[J]IEEE Journal on SelectedAreas in Communication,24(8):1452-1463
[75]Toumpis S.,Goldsmith A.J.,2003.Performance,optimization and cross-layer design of media access protocols for wireless ad hoc networks.[C]IEEE ICC'03 vol 3:2234-2240
[76]邵振付,张有林,2005.Ad Hoc网络的跨层设计研究.[J]中国数据移动通信,7(6)
[77]Iannone I.,Khalili R.,Salamatian K.,et al.2004.Cross-layer routing in wireless mesh networks.[C]1st International Symposium on Wireless Communication System,319-323
[78]Nandagopal T.,.Kim T.E,Gao X.,Bharghhavan V.,2000.Achieving MAC layer fairness in wireless packet networks,[C]Proc.ACM Mobicom pp87-98.
[79]Hahne E,1991.Round-robin Scheduling for Max-Min Fairnessin Data Networks[J]IEEE J.on Selected Area in Communications,9(7):1024-1039
[80]Tassiulas L,Sarkar S.2005.Maxmin fair scheduling in wireless ad hoc networks[J]IEEE J.on Selected Area in Communications,23(1):163-173
[81]秦晓卫,徐佩霞,无线多跳网络的一种端到端的最大最小公平调度算法[J]小型微型计算机系统,已录用,2008年发表
[82]Akyildiz I.F.,W.-Y.Lee,Vuran M.C.,Mohanty S,2006.Next generation/dynamic spectrum access/cognitive radio wireless networks:a survey,[C]Computer Networks,vol.50,pp.2127-2159
[83]Chowdhury K.R.,Akyildiz I.F.,2008.Cognitive Wireless Mesh Networks with Dynamic Spectrum Access,[J]Selected Areas in Communications,IEEE Journal on,26(1):168-181
[84]Liansheng T,2006.Price-based max-min fair rate allocation in wireless multi-hop networks. [J]IEEE Communications Letters.10(1):p.31-33.
[85]Garcia-Luna-Aceves J.J.,Raju J.,1997.Distributed assignment of codes for multihop packet-radio networks.[C]Proc.Of MILCOM,Monterey California,1:450-454
[86]Xiaowei Qin,Peixia Xu.2007.A Distributed Scheduling Algorithm for End-to-End Flow Fairness in Wireless Multi-hop Networks[C]IEEE Parallel and Distributed Computing,Applications and Technologies,PDCAT '07.Seventh International Conference on page:385-390
[87]秦晓卫,徐佩霞,2008.无线回程网中的公平性模型研究[J]小型微型计算机系统,已录用,vol 29(6):1070-1074