ABSTRACT

Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

3.4 Genetic Algorithm for Channel Assignment . . . . . . . . . . . . . . . . . . . . . . . . . 108

3.4.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

3.4.2 Algorithm GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

3.4.3 GA on Special Cases of CAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

3.4.3.1 Scheme 1: s1 = s2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

3.4.3.2 Scheme 2: For i) s2 < s1 ≤ 2s2 and ii) s1 ≥ 2s2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

3.4.3.3 Scheme 3: For s1 ≥ s2 . . . . . . . . . . . . . . . . . . . . . . . 125 3.4.4 Overall Bandwidth Requirement . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

3.5 Coalesced CAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

3.5.1 Construction of Coalesced CAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

3.5.2 Technique for Solving Original CAP from Coalesced CAP . . 137

3.6 Fast Near-Optimal Channel Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

3.6.1 Assignment Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

3.6.2 Convergence Behavior of Algorithm . . . . . . . . . . . . . . . . . . . . . . . 159

3.6.3 Worst-Case Time Complexity of Assignment Algorithm . . . . 161

3.6.4 Worst-Case Deviation of Bandwidth from Optimality . . . . . . . 162

3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

3.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

Mobile computing, particularly over cellular networks, has emerged as an im-

portant topic of research because of the need for computing capabilities even when

people are on the move. Over the past decade, the number of such cellular network

dependent mobile users has increased almost exponentially. However, the available

bandwidth for providing services to those users is very limited. Such a limited avail-

ability of the radio spectrum, signal distortion, and the interference caused by the

environment and other mobile users impose inherent limitations on the capacity of

wireless networks. Therefore, developing methods to utilize the scarce radio spec-

trum efficiently is more critical than ever.