[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 Xutao¹;  Shi Xiaoxiang²;  Zeng Shaoxiang¹

¹State Key Laboratory of Millimeter Waves, Southeast University, Nanjing 210096, China
²No.55 Research Institute, China Electronics Technology Group Corporation, Nanjing 210016, China

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]

Common functions