Improved list coloring algorithm in cognitive radio based on time cost and demand satisfaction
DOI:
https://doi.org/10.3103/S0735272713110046Keywords:
spectrum allocation, connected component, time cost, demand satisfactionAbstract
For the cognitive users to access the licensed frequency bands opportunistically, cognitive radio is the best solution to mitigate the spectrum resource scarcity at the moment. Dynamic spectrum allocation is a key technology to implement cognitive radio efficiently on the condition that the licensed users must not be interfered. Up to now, the spectrum allocation algorithms based on the graph model seldom focus on enhancing spectrum utilization, speedy accomplishing and requirement satisfaction simultaneously. In this paper, an improved algorithm is proposed to decrease time cost and increase demand satisfaction simultaneously based on a List-Coloring algorithm provided by Wei Wang research group. This improved algorithm was studied by handling connected component in parallel and depressing user’s priority which demand has been met, respectively. And the spectrum utilization is effectively guaranteed at the same time. Our experimental results show that the proposed algorithm is an efficient method. Compared with the original List-Coloring algorithm, the time cost is reduced obviously and the demand satisfaction is greatly improved while only a few bandwidth rewards are lost by using the algorithm proposed in our study.
References
MITOLA, J. Cognitive radio for flexible mobile multimedia communications. Proc. of IEEE Int. Workshop on Mobile Multimedia Communications, MoMuC’99, 15–17 Nov. 1999. San Diego, CA, Nov. 1999, p.3-10. doi: http://dx.doi.org/10.1109/MOMUC.1999.819467">10.1109/MOMUC.1999.819467.
MENON, REKHA; BUEHRER, R.M.; REED, J.H. Outage probability based comparison of underlay and overlay spectrum sharing techniques. Proc. of First IEEE Int. Symp. on New Frontiers in Dynamic Spectrum Access Networks, DySPAN 2005, 8–11 Nov. 2005, Baltimore, MD, USA. Baltimore, 2005, p.101-109. doi: http://dx.doi.org/10.1109/DYSPAN.2005.1542623">10.1109/DYSPAN.2005.1542623.
http://grouper.ieee.org/groups/scc41/files/IEICE_SCC41_01Aug08.pdf">http://grouper.ieee.org/groups/scc41/files/IEICE_SCC41_01Aug08.pdf.
WANG, WEI AND LIU, XIN. List-coloring based channel allocation for open-spectrum wireless networks. Proc. of 62 IEEE Vehicular Technology Conf., VTC-2005-Fall, 18–25 Sept., 2005, p.690-694. doi: http://dx.doi.org/10.1109/VETECF.2005.1558001">10.1109/VETECF.2005.1558001.
ZHENG, HAITAO AND PENG, CHUNYI. Collaboration and fairness in opportunistic spectrum access. Proc. of IEEE Int. Conf. on Communications, ICC 2005, 16–20 May 2005, v.5, p.3132-3136. doi: http://dx.doi.org/10.1109/ICC.2005.1494982">10.1109/ICC.2005.1494982.
CHU-LIN, LIAO; JIE, CHEN; YOU-XI, TANG; SHAO-QIAN, LI. Parallel spectrum allocation algorithm in cognitive radio. J. Electron. Inf. Technol., v.29, n.7, p.1608-1611, 2007, http://jeit.ie.ac.cn/EN/10.3724/SP.J.1146.2005.01596">http://jeit.ie.ac.cn/EN/10.3724/SP.J.1146.2005.01596.
BEIWEI, ZHANG; KUNYUAN, HU; YUNLONG, ZHU. Spectrum allocation in cognitive radio networks using swarm intelligence. Proc. of Second Int. Conf. on Communication Software and Networks, ICCSN’10, 26–28 Feb. 2010, Singapore. Singapore, 2010, p.8-12. doi: http://dx.doi.org/10.1109/ICCSN.2010.23">10.1109/ICCSN.2010.23.
WEISS, T.A. AND JONDRAL, F.K. Spectrum pooling: an innovative strategy for the enhancement of spectrum efficiency. IEEE Communications Mag., v.42, n.3, p.8-14, Mar. 2004. doi: http://dx.doi.org/10.1109/MCOM.2004.1273768">10.1109/MCOM.2004.1273768.
FILIN, S.; HARADA, H.; HASEGAWA, M.; KATO, S. QoS-guaranteed load-balancing dynamic spectrum access algorithm. Proc. of IEEE 19th Int. Symp. on Personal, Indoor and Mobile Radio Communications, PIMRC 2008, 15-18 Sept. 2008, Cannes. Cannes, 2008, p.1-6. doi: http://dx.doi.org/10.1109/PIMRC.2008.4699466">10.1109/PIMRC.2008.4699466.
QIU, JING AND ZHOU, ZHENG. Dynamic spectrum sharing strategy in cognitive radio systems. J. Beijing Univ. Posts Telecom., v.32, n.1, p.69-72, 2009.
FAN, YEBIN; YU, SHENGSHENG; ZHAO, HUALONG. A novel line based connected component labeling algorithm. Proc. of 3rd IEEE Int. Conf. on Computer Science and Information Technology, ICCSIT, 9-11 July 2010. Chengdu, 2010, p.168-172. doi: http://dx.doi.org/10.1109/ICCSIT.2010.5563571">10.1109/ICCSIT.2010.5563571.
LIN, CHUNG-YUAN; LI, SZ-YAN; TSAI, TSUNG-HAN. A scalable parallel hardware architecture for connected component labeling. Proc. of 17th IEEE Int. Conf. on Image Processing, ICIP, 26–29 Sept. 2010. Hong Kong, 2010, p.3753-3756. doi: http://dx.doi.org/10.1109/ICIP.2010.5653457">10.1109/ICIP.2010.5653457.
GUOLIANG, CHEN. Design and Analysis of Parallel Algorithms, 3rd ed. Beijing: Higher Education Press, 2009, Ch.15, p.508-521.
