A Comprehensive Review of Methods for the Channel Allocation Problem

The study of the channel allocation problem has received much attention during the last decade. Several techniques such as genetic algorithm, artificial neural network, simulated annealing, tabu search and others have been used. This book is devoted to compiling all the techniques that have been used to solve the channel allocation problem. Each of the methods is described fully in a manner that explains the essential parts of how the techniques are formulated and applied in solving the problem. This textbook will be helpful to students studying communications or researchers as it compiles all the techniques used since this problem was first solved.

List of tables vii

List of gures viii

Abbreviations ix

Preface x

Part I: The channel allocation problem 1

1 Introduction 3

2 The channel allocation problem 11

2.1 Channel allocation 11

2.1.1 Interference 11

2.2 Formulation of the CAP 13

2.3 Channel allocation schemes 13

2.3.1 Fixed channel allocation 14

2.3.2 Dynamic channel allocation 14

2.3.3 Comparison between FCA and DCA 15

2.3.4 Hybrid channel allocation 16

3 Mathematical formulation of the CAP 19

3.1 Introduction 19

3.1.1 Problem formulation – FCA 19

3.1.2 Problem formulation – DCA 20

3.1.3 Problem formulation – HCA 20

3.1.4 An example of a four-cellular network 20

3.2 Lower bounds for the CAP 22

3.3 Summary 22

Part II: Methods used to solve channel allocation problem 27

4 Graph theory 29

4.1 Graph colouring approach 29

4.2 Summary 32

 5 Neural networks 35

5.1 Neural network approach 35

5.2 Summary 39

6 Heuristics 43

6.1 Heuristic techniques 43

6.1.1 Summary 45

6.2 Simulated annealing 46

6.2.1 Summary 47

6.3 Tabu search 47

6.3.1 Summary 48

 7 Evolutionary methods 51

7.1 Genetic algorithm 51

7.1.1 Summary 53

7.2 Evolutionary strategy 53

7.2.1 Summary 54

8 Q-learning and other algorithms 59

8.1 Q-learning approach 59

8.1.1 Summary 60

8.2 Other algorithms 60

9 The channel allocation problem from a multi-objective view 63

9.1 Multi-objective approach 63

9.2 Experimental results 63

9.3 Comparison of different approaches 65

9.4 Summary 65