联合频谱切换调度和QoS重路由的性能优化算法

摘要/Abstract

摘要： 频谱切换技术可以降低无线传输干扰、优化网络结构,成为无线网络研究的热点。现有频谱切换技术忽视了频谱切换执行顺序对网络性能的影响,无法保证网络在切换过程中的连通性和吞吐量。为了最大化网络吞吐量,提出一新的频谱切换调度问题(SHSTM:Spectrum Handoff Scheduling for Throughput Maximization),并证明SHSTM是NP难问题。为解决SHSTM问题,提出联合频谱切换调度和QoS重路由的跨层优化算法JSHSQ-R。在JSHSQ-R中,频谱切换分多轮执行。为了减少切换延时并保证网络连通性,该算法基于加权最小生成树来确定每轮需要切换的链路,并在切换过程中为数据流进行重路由来满足数据流的QoS需求。在NS2上进行了大量仿真实验,结果表明所提算法能够充分利用无线网状网多接口多信道资源,并能为多流提供较高的网络吞吐量保证。

关键词: 多接口多信道无线网状网,频谱切换调度,QoS重路由,切换时延中图法分类号TP393文献标识码A

Abstract: Spectrum handoff has attracted the interest of many people as it can reduce interference among wireless transmissions and optimize the structure of wireless network．Current studies on spectrum handoff can’t guarantee the connectivity and high throughput of wireless network when spectrum handoff happens because these studies ignore that spectrum handoff order among multiple links can impact performance．To maximize the throughput of wireless network,this paper proposed a novel spectrum handoff scheduling problem (SHSTM),and proved that SHSTM is an NP-hard problem．To solve the SHSTM problem,we proposed a cross-layer optimization algorithm by jointly considering the spectrum handoff scheduling and QoS Re-routing (JSHSQ-R)．Spectrum handoff executes in several rounds in JSHSQ-R．To reduce the total delay of spectrum handoff and to guarantee the network connectivity,JSHSQ-R computes links sets whose spectrum needs to handoff in every round based on weighted Minimum Spanning Tree．To satisfy the QoS requirement of every flow,JSHSQ-R computes a QoS routing for every flow in every round．We made lots of simulations in NS2．The simulation results demonstrate that the proposed algorithm can make full use of multi-radios and multi-channels in wireless mesh network and obtain high throughput for multiple flows.

Key words: MRMC-WMN,Spectrum handoff and scheduling,QoS Re-routing,Handoff delay

谢鲲,刘学礼. 联合频谱切换调度和QoS重路由的性能优化算法[J]. 计算机科学, 2013, 40(7): 61-66. https://doi.org/

XIE Kun and LIU Xue-li. Joint Spectrum Handoff Scheduling and QoS Re-routing for Performance Optimization[J]. Computer Science, 2013, 40(7): 61-66. https://doi.org/

参考文献

[1] Huang Rong-sheng,Kim S,Zhang Chi,et al.Exploiting the Capacity of Multichannel Multiradio Wireless Mesh Networks[J].Vechicular Technology,2009,8(9):5037-5047
[2] Bhandari V,Vaidya N H.Connectivity and Capacity of Multi-Channel Wireless Networks with Channel Switching Constraints[C]∥INFOCOM 2007.26th.Anchorage,AK:IEEE,2007:785-793
[3] Feng Wei,Cao Jian-nong,Zhang Chi-sheng,et al.Joint Optimization of Spectrum Handoff Scheduling and Routing in Multi-hop Multi-radio Cognitive Networks[C]∥IEEE International Conference on Distributed Computing Systems(ICDCS’09.29th).Montreal,QC:IEEE,2009:85-92
[4] Adisorn L,Naceur M,Serge F.Spectrum handoff strategy using cumulative probability in cognitive radio networks[C]∥Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT).Budapest:IEEE,2011:1-7
[5] Yoon S-U,Ekici E.Voluntary Spectrum Handoff:A Novel Approach to Spectrum Management in CRNs[C]∥2010IEEE International Communications(ICC) Conference.Cape Town:IEEE,2010:1-5
[6] Raniwala A,Chiueh T-C.Architecture and algorithms for anIEEE 802.11-based multi-channel wireless mesh network[C]∥the 24th Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2005).2005:2223-2234
[7] Raniwala A,Gopalan K,Chiueh T-C.Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks[J].ACM SIGMOBILE.Mobile Computing and Communications Review,2004,8(2):50-65
[8] Chen Yin,Kowalik K,Davis M.MeshScan:Performance of Pas-sive Handoff and Active Handoff[C]∥Wireless Communications & Signal Processing(WCSP 2009).Nanjing:IEEE,2009:1-5
[9] Wang Li-chun,Chen A.On the Performance of Spectrum Handoff for Link Maintenance in Cognitive Radio[C]∥Proceedings of ISWPC 2008.Santorini:IEEE,2008:19-22
[10] Wang Chun-li,Wang Chung-wei.Spectrum handoff for cognitive radio networks:reactive-sensing or proactive-sensing[C]∥Performance,Computing and Communications Conference.Austin,Texas:IEEE,2008:343-348
[11] Song Y,Xie J.ProSpect:A Proactive Spectrum Handoff Framework for Cognitive Radio Ad Hoc Networks without Common Control Channel[J].Mobile Computing,2012,1(7):1127-1139
[12] Wang Chung-wang,Wang Li-chung.Modeling and Analysis for Proactive-Decision Spectrum Handoff in Cognitive Radio Networks[C]∥IEEE International Conference on(ICC 2009).Dresden:IEEE,2009:1-6
[13] Song Yi,Xie Jiang.Common Hopping Based Proactive SpectrumHandoff in Cognitive Radio Ad Hoc Networks[C]∥2010IEEE Global Telecommunications Conference(GLOBECOM2010).Miami,FL:IEEE,2010:1-5
[14] Wang Chung-wei,Wang Li-chun,Adachi F.Modeling and Analysis for Reactive-Decision Spectrum Handoff in Cognitive Radio Networks[C]∥2010IEEE Global Telecommunications Confe-rence(GLOBECOM 2010).Miami,FL:IEEE,2010:1-6
[15] Di Felice M,Chowdhury K R,Kassler A,et al.Adaptive Sensing Scheduling and Spectrum Selection in Cognitive Wireless Mesh Networks[C]∥2011Proceedings of 20th International Confe-rence on Computer Communications and Networks (ICCCN).Maui,HI:IEEE,2011,0:1-6
[16] Kalil M A,Al-Mahdi H,Mitschele-Thiel A.Spectrum handoff reduction for cognitive radio ad hoc networks[C]∥Wireless Communication Systems (ISWCS).York:IEEE,2010:1036-1040
[17] Aman M,Mahfooz S,Rehman W.Handoff delay in cognitive radios-A concept paper on utilization of guard channels[C]∥Computer Networks and Information Technology．Abbottabad:IEEE,2011:211-215
[18] Chvatal V.A Greedy Heuristic for the Set-Covering Problem[J].Mathematics of Operations Research,1979,4(3):233-235
[19] Mohsenian-Rad A H,Wong V W S.Joint logical topology design,interface assignment,channel allocation,and routing for multi-channel wireless mesh networks[J].Wireless Communications,2007,6(12):4432-4440
[20] Cormen T H,Leiserson C E,Rivest R L．Clifford Stein.Introduction to Algorithms(Second Edition)[M].Boston:MIT Press and McGraw-Hill,2001
[21] Issariyakul T,Hossain E.Introduction to Network SimulatorNS2[M].New York:Springer Publishing Company,2008

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed