Price-based Research On Fairness For End-to-End Flow In Wireless MESH Networks

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.