Title: Graph model for optimal OVSF code placement strategies

Authors: Wen Ouyang; Chang Wu Yu; Meng-Ti Liu; Yu-Wei Chang

Addresses: Department of Computer Science and Information Engineering, Chung Hua University, 707, Sec. 2, WuFu Rd., Hsinchu 30012, Taiwan ' Department of Computer Science and Information Engineering, Chung Hua University, 707, Sec. 2, WuFu Rd., Hsinchu 30012, Taiwan ' Department of Computer Science and Information Engineering, Chung Hua University, 707, Sec. 2, WuFu Rd., Hsinchu 30012, Taiwan ' Department of Computer Science and Information Engineering, Chung Hua University, 707, Sec. 2, WuFu Rd., Hsinchu 30012, Taiwan

Abstract: The code utilisation of OVSF-CDMA systems are significantly impacted by the code placement and replacement schemes which have been studied by many researchers as independent problems. We formally define the placement optimality and present a novel graph model, CIDP, which is proved to be NP-complete for general graphs where the CIDP graphs reduced from the OVSF code placement problem are trivial perfect graphs. A unified algorithm UCMS-1, provided to firstly address both OVSF code placement and replacement jointly, achieves placement optimality in linear time complexity. It shows that OVSF code placement optimality problem is in P.

Keywords: graph models; OVSF-CDMA; code blocking; code placement; constrained independent dominating sets; code replacement; placement optimisation.

DOI: 10.1504/IJAHUC.2012.046931

International Journal of Ad Hoc and Ubiquitous Computing, 2012 Vol.9 No.3, pp.133 - 141

Received: 11 May 2010
Accepted: 08 Aug 2010
Published online: 22 May 2012 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article