A clique-based online algorithm for constructing optical orthogonal codes
A clique-based online algorithm for constructing optical orthogonal codes
复制标题
DOI：
10.1016/j.asoc.2016.05.024
复制
发表时间：
2016-10
期刊：
影响因子：
--
通讯作者：
Yuan Zhang-;Mao Peng;Shengxiang Yang
中科院分区：
文献类型：
--
作者：
Yuan Zhang-;Mao Peng;Shengxiang Yang
光正交码(OOC)是一类具有良好的自相关和互相关特性的二进制序列。在文献中，已经使用各种数学工具来构造具有特定参数的OOC。但是，目前还很难找到构建任意参数设置的OOC的完整解决方案。本文提出了一种基于团的在线算法来构造较大规模的OOC。在该算法中，OOC的构造归结为基于特殊生成图的最大团问题，其中顶点表示OOC的码字，边表示码字对之间的互相关关系。为了克服计算机内存对存储大图的限制，该算法假定部分图的顶点按顺序到达，并使用一种特别设计的进化算法在新的顶点到达时寻找当前图的最大团。该算法不使用特定于参数的技术，因此可以用于不同的码权重和相关性约束。实验表明，该算法在构造OOCs方面优于带引导变异的离线进化算法。
An optical orthogonal code (OOC) is a family of binary sequences with good auto- and cross-correlation properties. In the literature, various mathematical tools have been used to construct OOCs with specific parameters. But, to find a complete solution for constructing OOCs with an arbitrary setting of parameters is still difficult at the moment. In this paper, a clique-based online algorithm is proposed to construct OOCs of relatively large sizes. In the proposed algorithm, the construction of OOCs is reduced to the maximum clique problem based on specially generated graphs, where vertices represent the codewords of an OOC and edges represent the cross-correlation relationships between codeword pairs. In order to overcome the limitation of computer memory for storing large graphs, part of the graph vertices are supposed to arrive sequentially to be fed into the proposed algorithm, and a specially designed evolutionary algorithm is used to find the maximum clique of the current graph when new vertices arrive. The proposed algorithm does not use parameter-specific techniques and hence can be used for different code weight and correlation constraints. Experiments show that the proposed algorithm outperforms an offline evolutionary algorithm with guided mutation on constructing OOCs.