A clique-based online algorithm for constructing optical orthogonal codes

Date

2016-05-25

Advisors

Journal Title

Journal ISSN

ISSN

Volume Title

Publisher

Elsevier

Type

Article

Peer reviewed

Yes

Abstract

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.

Description

Keywords

Optical orthogonal codes, Evolutionary algorithm, Maximum clique problem, Online algorithm

Citation

Zhang, Y., Peng, M. and Yang, S. (2016) A clique-based online algorithm for constructing optical orthogonal codes. Applied Soft Computing, 47, pp. 21-32

Rights

Research Institute

Institute of Artificial Intelligence (IAI)