Research On Parallel Computing Of Frequency Assignment Based On Simulated Annealing Algorithm

With the development and application of digital technology on broadcasting TV,new digital terrestrial TV broadcasting service such as High-Definition TV,mobile TV,data broadcasting,handset TV are familiar with ordinary people.The introduction of new digital terrestrial caused frequency resource more scarce. Frequency assignment plays an important role in TV broadcasting frequency planning, it is an effective way to solve the scarcity of frequency resource.It is an important direction of frequency planning research to resolve large scale frequency assignment problem with optimal algorithm currently.In this paper, simulated annealing was adopted to solve frequency assignment problem, and its parallel computing optimization was deeply studied. It was supported by the special fund for science and technology community, research on key technology and optimization standards for the promotion and implementation of national standards for digital television (200910245), which was supported by General Administration of Quality Supervision, Inspection and Quarantine.At first,the paper analyzed the TV broadcasting ferquency partition and its history in China, introduced several common interferences of TV broadcasting frequency, built a mathematic model of frequency assignment with given transmitter coordinates,usable frequency table and took co-channel constraint, adjacent channel constraint and population coverage into consideration. Then, under the basic idea of simulated annealing and the similarity with optimal combinatorial problem, discussed the Metropolis sampling rule and Markov chain theory and designed the simulated annealing algorithm to resolve frequency assignment problem, studied the parameter setting and the function code of key sections. Then,took local search as reference, experiments shows that simulated annealing is obviously better than local search in solving frequency assignment problem. Designed the module based on MFC from the angle of visualization and geographic infomation assistant,the import of transmitter coordinate data,population data and frequency table data,the display and query of interference graph caused by co-channel and adjacent channel constraint,the manipulation function of map were realized. With the increasing size of the problem and the requirement of assignment quality, the required time also will increase, while the cooling schedule can not fundamentally improve the efficiency of the algorithm. Therefor, the idea of parallel computing was put forward, the common platform of parallel computing and related library were analyzed, the design of parallel algorithm and index of performance was discussed, three methods of parallel simulated annealing algorithm were studied, parallel assignemnt by random selecting cooling schedule was put forward. Finally, according to the theory of software optimization, did the experiment of parallel optimization on loop code in constraint check section by adding OpenMP directions, the result showed the efficiency significantly improved in solving large scale frequency assignment problem on multi-core platform.Through above research, built a simplified mathematical model of frequency assignment, put forward the common routine of solving frequency assignment problem, realized visualization and geographic information assistant for frequency assignment, did some kind of meaningful exploration, achieved parallel optimization of large scale frequency assignment problem by adding OpenMP directions, enriched the theory and method to solve frequency assignment problem.