The use of the simulated annealing algorithm for channel allocation in mobile computing

摘要

A mobile network is a distributed communication system that uses radio signals as its information medium. Since the popularization of mobile networks, the rate of connectivity has soared and the subsequent load on the networks is much more significant than original projections. Hence, resource management becomes an important issue when designing mobile networks. This work concentrates on the most important resource available to mobile networks, that is, the limited allocated bandwidth. With the given amount of bandwidth, the network is expected to meet a minimum quality of service, to provide subscribers with access to the network. As the network is based on a cellular design, the way to improve utilization of the bandwidth is to reuse frequencies or channels. However, this reuse comes at a cost. The allocation of reused channels must be subject to the avoidance of interference between allocated channels. This is known as the channel allocation problem (CAP). It will be shown that the problem can be formalized into an optimization problem, for which there are many solution methodologies. In order to meet the demands of solution quality and algorithm efficiency, the decision of which method to use is critical. Biologically inspired techniques provide effective search strategies that enable the discovery of near optimal solutions. They are ideal for problems with large and complex solution spaces such as the CAP. However, the performance of these algorithms in terms of solution quality and efficiency varies greatly with the problems to which they are applied. This work makes an assessment of the application of the simulated annealing for finding optimal solutions to the CAP for a fixed or static allocation of channels. Simulated annealing is based on the annealing process employed to enhance the strength of malleable materials. It provides unique search characteristics that allow the solution space to be searched without the difficulties of other random search methods.