WiMax mesh网络带宽调度与信道分配问题的研究
|
摘要
随着通信技术的发展,宽带无线接入受到越来越多的关注.全球微波接入互操作性(WiMax)技术是宽带无线接入领域的关键技术之一,具有传输距离远,传输速率高的特点,可以以较低的成本提供与有线基础设施相近的服务质量,因此具有广阔的发展前景。目前较为成熟的WiMax技术标准是IEEE802.16-2004.该标准定义了WiMax网络的两种工作模式,即点到多点(PMP)模式和多点到多点(mesh)模式。同PMP模式相比,mesh模式在可靠性、覆盖范围、传输距离等方面都有较好表现,但也面临着更复杂的带宽管理及与之相关的信道分配、路由等问题。本文针对这些问题进行了深入研究。
集中式调度是WiMax网络mesh模式下的主要调度方式,用于端到端带宽分配。本文第三章研究了多信道WiMax mesh网络中的调度问题.我们假定每个站点支持一个收发器且该收发器可以在不同信道间切换,在此基础上讨论了网络中需要的信道个数并给出线型网络上的最优调度算法。同时,我们提出了适用于一般拓扑结构多信道网络的集中式调度与信道分配算法,从理论上分析了算法的时间复杂度和近似比,并通过实验说明了该算法的有效性。实验结果还表明,对单收发器系统,使用两个信道可以获得与多个信道相近的性能。
在第三章的基础上,第四章研究了多收发器WiMax mesh网络中的路由和调度问题。我们首先提出了遵循IEEE 802.16协议的以最小化网络干涉为目标的路由树构造策略,然后给出了适用于多收发器WiMax mesh网络的集中式调度算法并分析了算法性能.最后,这一章通过实验研究了信道个数和收发器个数对总传输时间的影响。
在WiMax mesh网络中,相邻站点可以采用非协调分布式信道接入算法进行通信,通信前首先通过“请求.授权.授权确认”三次握手建立连接,然后根据握手时的协商结果传输数据。如果握手时发生冲突,则按照二进制指数退避算法进行重传。第五章建立了非协调分布式调度的性能分析模型。假定网络构成规则的网格状,站点始终处于饱和状态,我们通过分析握手失败概率与站点传输概率间的关系建立方程,从而计算出系统所能达到的吞吐率。这一章还通过实验验证了理论模型的正确性。
随着网络技术的发展,如何利用网络上的计算及存储等资源成为当前研究的热点问题。第六章研究以WiMax为骨厂网的混合mesh网络中的资源管理问题。我们将资源分为网格资源和p2p资源两类,针对这两种资源,分别设计了资源发布和资源搜索算法。同时,针对资源管理对底层传输的需求,这一章还提出了专门的MAC层带宽调度算法。
World Interoperability for Microwave Access(WiMax) is one of the leading technologies in the context of Broadband Wireless Access(BWA).The PHY and MAC layer specifications of WiMax networks are defined by the IEEE 802.16-2004 standard.According to this standard,WiMax systems can work in Point-to-Multipoint(PMP) mode or mesh mode.However,this standard does not specify the MAC layer bandwidth allocation and channel assignment algorithms for the mesh mode,which is decisive to the system performance in terms of throughput and quality of service.We investigate these issues in this thesis.
As specified in the IEEE 802.16-2004 standard,time slot allocation for end-to-end traffic flow in WiMax mesh networks is controlled by a centralized scheduling algorithm.To support high-quality multimedia services on the network,the scheduling algorithm should be able to minimize the total transmission time for all traffic flows.Chapter 3 studies the multi-channel scheduling problem in order to explore the potential of simultaneous transmissions and thus minimize the total transmission time in WiMax mesh networks.For a given network topology with fixed routing tree,we first analyze how many channels are sufficient for the avoidance of interference.Then we present an efficient scheduling algorithm along with the channel assignment strategy for time slot allocation.The simulation results show that our scheme can improve the system performance substantially as compared with the single channel system.Also,we observe that double channel settings may provide a performance similar to the multiple channels.
Chapter 4 studies the routing,time slot allocation and channel assignment problem in multi-channel multi-transceiver WiMax mesh networks,where multiple transceivers are supported on each station and can switch between different channels.We develop an interference-aware route construction algorithm,which construct a routing tree during the network entry process,in order to minimize the interference.We also propose a time slot allocation algorithm for multi-transceiver networks.In this algorithm,each transceiver is allowed to switch between at most 2 channels, according to the result of chapter 3.The simulation part shows the impact of channels and transceivers on total transmission time.
In WiMax mesh networks,transient traffic between neighbor stations can be controlled by an uncoordinated distributed scheduling algorithm.According to this algorithm a three-way handshake must be initiated before data transmission.If the handshake fails,the transmitter must wait for a certain period before its next transmission,In Chapter 5 we analyze the performance of this algorithm. Due to the complexity of the problem,we only present a model for infinite networks with grid topology so all nodes can be considered identical.The behavior of each station in stable stage can be described as a Markov regeneration process.We analyze the impact of neighbor nodes on the transmission fail probability of a certain node,then calculate the throughput of each node.In the simulation part a custom simulator is used to show the effectiveness of our analytical model.
Chapter 6 studies the problem of resource management on hybrid wireless mesh networks,where WiMax is used as the backbone.We propose resource publishing/discovery algorithms for two kinds of resources,resources that can only be provided by WiMax stations and resources that can be on both WiMax and client stations.In our solution we use the base station to coordinate the transmissions of resource publishing/discovery messages.We also propose a time slot allocation schema to support the application layer resource management.
Although the PHY and MAC layer specifications of WiMax mesh networks has been well defined,there is still work to do in order to increase the system throughput and improve the quality of service.In final chapter,we summarize our main contribution and conclude this thesis by pointing out our future work.
集中式调度是WiMax网络mesh模式下的主要调度方式,用于端到端带宽分配。本文第三章研究了多信道WiMax mesh网络中的调度问题.我们假定每个站点支持一个收发器且该收发器可以在不同信道间切换,在此基础上讨论了网络中需要的信道个数并给出线型网络上的最优调度算法。同时,我们提出了适用于一般拓扑结构多信道网络的集中式调度与信道分配算法,从理论上分析了算法的时间复杂度和近似比,并通过实验说明了该算法的有效性。实验结果还表明,对单收发器系统,使用两个信道可以获得与多个信道相近的性能。
在第三章的基础上,第四章研究了多收发器WiMax mesh网络中的路由和调度问题。我们首先提出了遵循IEEE 802.16协议的以最小化网络干涉为目标的路由树构造策略,然后给出了适用于多收发器WiMax mesh网络的集中式调度算法并分析了算法性能.最后,这一章通过实验研究了信道个数和收发器个数对总传输时间的影响。
在WiMax mesh网络中,相邻站点可以采用非协调分布式信道接入算法进行通信,通信前首先通过“请求.授权.授权确认”三次握手建立连接,然后根据握手时的协商结果传输数据。如果握手时发生冲突,则按照二进制指数退避算法进行重传。第五章建立了非协调分布式调度的性能分析模型。假定网络构成规则的网格状,站点始终处于饱和状态,我们通过分析握手失败概率与站点传输概率间的关系建立方程,从而计算出系统所能达到的吞吐率。这一章还通过实验验证了理论模型的正确性。
随着网络技术的发展,如何利用网络上的计算及存储等资源成为当前研究的热点问题。第六章研究以WiMax为骨厂网的混合mesh网络中的资源管理问题。我们将资源分为网格资源和p2p资源两类,针对这两种资源,分别设计了资源发布和资源搜索算法。同时,针对资源管理对底层传输的需求,这一章还提出了专门的MAC层带宽调度算法。
World Interoperability for Microwave Access(WiMax) is one of the leading technologies in the context of Broadband Wireless Access(BWA).The PHY and MAC layer specifications of WiMax networks are defined by the IEEE 802.16-2004 standard.According to this standard,WiMax systems can work in Point-to-Multipoint(PMP) mode or mesh mode.However,this standard does not specify the MAC layer bandwidth allocation and channel assignment algorithms for the mesh mode,which is decisive to the system performance in terms of throughput and quality of service.We investigate these issues in this thesis.
As specified in the IEEE 802.16-2004 standard,time slot allocation for end-to-end traffic flow in WiMax mesh networks is controlled by a centralized scheduling algorithm.To support high-quality multimedia services on the network,the scheduling algorithm should be able to minimize the total transmission time for all traffic flows.Chapter 3 studies the multi-channel scheduling problem in order to explore the potential of simultaneous transmissions and thus minimize the total transmission time in WiMax mesh networks.For a given network topology with fixed routing tree,we first analyze how many channels are sufficient for the avoidance of interference.Then we present an efficient scheduling algorithm along with the channel assignment strategy for time slot allocation.The simulation results show that our scheme can improve the system performance substantially as compared with the single channel system.Also,we observe that double channel settings may provide a performance similar to the multiple channels.
Chapter 4 studies the routing,time slot allocation and channel assignment problem in multi-channel multi-transceiver WiMax mesh networks,where multiple transceivers are supported on each station and can switch between different channels.We develop an interference-aware route construction algorithm,which construct a routing tree during the network entry process,in order to minimize the interference.We also propose a time slot allocation algorithm for multi-transceiver networks.In this algorithm,each transceiver is allowed to switch between at most 2 channels, according to the result of chapter 3.The simulation part shows the impact of channels and transceivers on total transmission time.
In WiMax mesh networks,transient traffic between neighbor stations can be controlled by an uncoordinated distributed scheduling algorithm.According to this algorithm a three-way handshake must be initiated before data transmission.If the handshake fails,the transmitter must wait for a certain period before its next transmission,In Chapter 5 we analyze the performance of this algorithm. Due to the complexity of the problem,we only present a model for infinite networks with grid topology so all nodes can be considered identical.The behavior of each station in stable stage can be described as a Markov regeneration process.We analyze the impact of neighbor nodes on the transmission fail probability of a certain node,then calculate the throughput of each node.In the simulation part a custom simulator is used to show the effectiveness of our analytical model.
Chapter 6 studies the problem of resource management on hybrid wireless mesh networks,where WiMax is used as the backbone.We propose resource publishing/discovery algorithms for two kinds of resources,resources that can only be provided by WiMax stations and resources that can be on both WiMax and client stations.In our solution we use the base station to coordinate the transmissions of resource publishing/discovery messages.We also propose a time slot allocation schema to support the application layer resource management.
Although the PHY and MAC layer specifications of WiMax mesh networks has been well defined,there is still work to do in order to increase the system throughput and improve the quality of service.In final chapter,we summarize our main contribution and conclude this thesis by pointing out our future work.
引文
方旭明.2006.下一代无线因特网技术:无线MESH网络[M].2006.第一版.人民邮电出版社,103-138.
陆文彦,贾维嘉,杜文峰,等.2007.IEEE 802.16竞争解决方案的性能分析。软件学报,18(9):2259-2270.
单九龙.2004.网络计算环境中资源管理任 务调度的研(?):[博士].合肥:中国科学技术大学,18-24.
Abramson N.1970.The ALOHA System-Another alternative for computer communications[C].Proceedings of the November 17-19,1970,fall joint computer conference,Huston,USA,28 i-285.
Abramson N.1973.Packet switching with satellites[C].Proceedings of the June 4-8,1973,national computer conference and exposition,New York,USA,695-702.
Akyildiz IF,Wang XD,Wang WL.2005.Wireless Mesh Networks:a survey[J].Computer Networks,47(4):445-487.
Alavi HS,Mojdeh M,Yazdani N.2005.A Quality of Service Architecture for IEEE 802.16 Standards [C].Proceedings of 11th Asia-Pacific Conference on Communications,Perth,Australia,249-253.
Alizadeh-Shabdiz F,Subramanian S.2006.Analytical Models for Single-Hop and Multi-Hop Ad Hoc Networks[J].Mobile Networks&Applications,11(1):75-90.
Arikan E.1984.Some complexity results about packet radio networks[J].IEEE Transactions on Information Theory,30(4):681-685.
Bharghavan V,Demers A,Shenker S,et.al.1994.MACAW:A media access protocol for wireless LANs.Proceedings of the conference on Communications architectures,protocols and applications,London,UK,212-225.
Bhatia R,Kodialam M.2004.On Power Efficient Communication over Multi-hop Wireless Networks:Joint Routing,Scheduling and Power Control[C].Proceedings of the 23rd IEEE International Conference on Communications,2:1457-1466.
Bianchi G.2000.Performance Analysis of the IEEE 802.11 Distributed Coordination Function[J].IEEE Journal on Selected Area in Communications,18(3):535-547.
Broch J,Maltz DA,Johnson DB,et al.1998.A performance comparison of multi-hop wireless ad hoc network routing protocols[C].Proceedings of the 4th ACM/IEEE international conference on Mobile computing and networking,Dallas,USA,85-97.
陆文彦,贾维嘉,杜文峰,等.2007.IEEE 802.16竞争解决方案的性能分析。软件学报,18(9):2259-2270.
单九龙.2004.网络计算环境中资源管理任 务调度的研(?):[博士].合肥:中国科学技术大学,18-24.
Abramson N.1970.The ALOHA System-Another alternative for computer communications[C].Proceedings of the November 17-19,1970,fall joint computer conference,Huston,USA,28 i-285.
Abramson N.1973.Packet switching with satellites[C].Proceedings of the June 4-8,1973,national computer conference and exposition,New York,USA,695-702.
Akyildiz IF,Wang XD,Wang WL.2005.Wireless Mesh Networks:a survey[J].Computer Networks,47(4):445-487.
Alavi HS,Mojdeh M,Yazdani N.2005.A Quality of Service Architecture for IEEE 802.16 Standards [C].Proceedings of 11th Asia-Pacific Conference on Communications,Perth,Australia,249-253.
Alizadeh-Shabdiz F,Subramanian S.2006.Analytical Models for Single-Hop and Multi-Hop Ad Hoc Networks[J].Mobile Networks&Applications,11(1):75-90.
Arikan E.1984.Some complexity results about packet radio networks[J].IEEE Transactions on Information Theory,30(4):681-685.
Bharghavan V,Demers A,Shenker S,et.al.1994.MACAW:A media access protocol for wireless LANs.Proceedings of the conference on Communications architectures,protocols and applications,London,UK,212-225.
Bhatia R,Kodialam M.2004.On Power Efficient Communication over Multi-hop Wireless Networks:Joint Routing,Scheduling and Power Control[C].Proceedings of the 23rd IEEE International Conference on Communications,2:1457-1466.
Bianchi G.2000.Performance Analysis of the IEEE 802.11 Distributed Coordination Function[J].IEEE Journal on Selected Area in Communications,18(3):535-547.
Broch J,Maltz DA,Johnson DB,et al.1998.A performance comparison of multi-hop wireless ad hoc network routing protocols[C].Proceedings of the 4th ACM/IEEE international conference on Mobile computing and networking,Dallas,USA,85-97.