|Table of Contents|

[1] Yu Xutao, Shi Xiaoxiang, Zeng Shaoxiang,. A maximum-independent-set-based channel allocation algorithmfor multi-channel wireless networks [J]. Journal of Southeast University (English Edition), 2015, 31 (1): 12-18. [doi:10.3969/j.issn.1003-7985.2015.01.003]
Copy

A maximum-independent-set-based channel allocation algorithmfor multi-channel wireless networks()
基于最大独立集的多信道无线网络信道分配方法
Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
31
Issue:
2015 1
Page:
12-18
Research Field:
Computer Science and Engineering
Publishing date:
2015-03-30

Info

Title:
A maximum-independent-set-based channel allocation algorithmfor multi-channel wireless networks
基于最大独立集的多信道无线网络信道分配方法
Author(s):
Yu Xutao1;  Shi Xiaoxiang2;  Zeng Shaoxiang1
1State Key Laboratory of Millimeter Waves, Southeast University, Nanjing 210096, China
2No.55 Research Institute, China Electronics Technology Group Corporation, Nanjing 210016, China
余旭涛1;  施小翔2;  曾绍祥1
1东南大学毫米波国家重点实验室, 南京 210096; 2中国电子科技集团公司第55研究所, 南京 210016
Keywords:
wireless networks;  multi-channel;  channel allocation;  maximum independent set
无线网络;  多信道;  信道分配;  最大独立集
PACS:
TP393
DOI:
10.3969/j.issn.1003-7985.2015.01.003
Abstract:
A channel allocation algorithm based on the maximum independent set is proposed to decrease network conflict and improve network performance. First, a channel allocation model is formulated and a series of the maximum independent sets(MISs)are obtained from a contention graph by the proposed approximation algorithm with low complexity.Then, a weighted contention graph is obtained using the number of contention vertices between two MISs as a weighted value. Links are allocated to channels by the weighted contention graph to minimize conflicts between independent sets. Finally, after channel allocation, each node allocates network interface cards(NICs)to links that are allocated channels according to the queue lengths of NICs. Simulations are conducted to evaluate the proposed algorithm. The results show that the proposed algorithm significantly improves the network throughput and decreases the end to end delay.
提出了一种基于最大独立集的信道分配方法, 以减少网络冲突提高网络性能.首先, 建立信道分配模型, 并通过所提出的低复杂度近似算法求取冲突图中的最大独立集序列;然后, 以独立集间的冲突顶点数作为加权值, 获得加权冲突图, 通过加权冲突图, 以最小化独立集间冲突为目标将链路分配至各信道;最后, 每个节点根据本节点网卡中队列长度为已分配信道的链路分配网卡.仿真结果表明, 该方法有效地提高了网络吞吐量, 降低了端到端延时.

References:

[1] IEEE 802.11 Working Group. Part 11: Wireless LAN medium access control(MAC)and physical layer(PHY)specifications: high-speed physical layer in the 5 GHz band [S]. IEEE Standard 802.11a, 1999.
[2] IEEE 802.11 Working Group. Part 11: Wireless LAN medium access control(MAC)and physical layer(PHY)specifications: high-speed physical layer extension in the 2.4 GHz band [S]. IEEE Standard 802.11b, 1999.
[3] IEEE 802.15 Working Group. IEEE standard for wireless medium access control(MAC)and physical layer(PHY)specifications for low-rate wireless personal area networks(LR-WPANs)[S]. IEEE Standard 802.15.4, 2006.
[4] Aryafar E, Gurewitz O, Knightly E W. Distance-1 constrained channel assignment in single radio wireless mesh networks [C]//The 27th IEEE Conference on Computer Communications. Phoenix, AZ, USA, 2008:1436-1444.
[5] Jha S C, Phuyal U, Rashid M M, et al. Design of OMC-MAC: an opportunistic multi-channel MAC with QoS provisioning for distributed cognitive radio networks [J]. IEEE Transactions on Wireless Communications, 2011, 10(10):3414-3425.
[6] So H S W, Walrand J, Mo J. McMAC: a parallel rendezvous multi-channel MAC protocol [C]//Wireless Communications and Networking Conference. Hong Kong, China, 2007: 334-339.
[7] Bahl P, Chandra R, Dunagan J. SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks [C]//The 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing. Tokyo, Japan, 2004:216-230.
[8] Kaur N, Saini J S. Performance enhancement of 802.11 based wireless mesh network by using multi-radio multi-channel [C]//International Conference on Green Computing, Communication and Conservation of Energy. Chennai, India, 2013: 71-76.
[9] Adya A, Bahl P, Padhye J, et al. A multi-radio unification protocol for IEEE 802.11 wireless networks [C]//IEEE Broadnets 2004. San Jose, CA, USA, 2004: 344-354.
[10] Saifullah A, Xu Y, Chen Y. Distributed channel allocation protocols for wireless sensor networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 25(9): 2264-2274.
[11] Li M, Salinas S, Li P, et al. Optimal scheduling for multi-radio multi-channel multi-hop cognitive cellular networks [J]. IEEE Transactions on Mobile Computing, 2014, 14(1): 139-154.
[12] 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]. IEEE Transactions on Wireless Communications, 2007, 6(12): 4432-4440.
[13] Kanagasabapathy A A, Franklin A A, Murthy C S R. An adaptive channel reconfiguration algorithm for multi-channel multi-radio wireless mesh networks [J]. IEEE Transactions on Wireless Communications, 2010, 9(10): 3064-3071.
[14] Yu X T, Fang X, Zhang Z C. Joint link allocation and rate assignment algorithm for multi-channel wireless networks [J]. China Communications, 2012, 9(9): 96-106.
[15] Zheng K, Liu F, Zheng Q, et al. A graph-based cooperative scheduling scheme for vehicular networks [J]. IEEE Transactions on Vehicular Technology, 2013, 62(4): 1450-1458.
[16] Kim S J, Wang X D, Madihian M. Distributed joint routing and medium access control for lifetime maximization of wireless sensor networks [J]. IEEE Transactions on Wireless Communications, 2007, 6(7): 2669-2677.
[17] Kai C H, Liew S C. Applications of belief propagation in CSMA wireless networks [J]. IEEE/ACM Transactions on Networking, 2012, 20(4): 1276-1289.
[18] Tomita E, Tanaka A, Takahashi H. The worst-case time complexity for generating all maximal cliques and computational experiments [J]. Theoretical Computer Science, 2006, 363(1): 28-42.
[19] Massoulie L, Roberts J. Bandwidth sharing: objectives and algorithms [J]. IEEE/ACM Transactions on Networking, 2002, 10(3):320-328.

Memo

Memo:
Biography: Yu Xutao(1975—), female, doctor, professor, yuxutao@seu.edu.cn.
Foundation items: The National High Technology Research and Development Program of China(863 Program)(No.2013AA013601), Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute(No.BY2013095-1-18).
Citation: Yu Xutao, Shi Xiaoxiang, Zeng Shaoxiang.A maximum-independent-set-based channel allocation algorithm for multi-channel wireless networks[J].Journal of Southeast University(English Edition), 2015, 31(1):12-18.[doi:10.3969/j.issn.1003-7985.2015.01.003]
Last Update: 2015-03-20