Wireless Communication Network In The Frequency Allocation Algorithm

We study the online frequency allocation problem (FAP in short) for wireless communications networks, whose geographical coverage area is divided into cells and whose phone calls are serviced by assigning frequencies to them, so that no two calls emanating from the same or neighboring cells are assigned the same frequency. Our aim is to minimize the span of frequencies used.In this dissertation, we define and investigate two kinds of models: without deletion and with deletion. In the first model, we assume that all calls are of infinite duration; in the second model, each call must be terminated at some time.In studying the without deletion model, we first fill in the gaps in the competitive analysis of the previously-proposed greedy algorithm [28] for cellular networks.Then, we present the Hybrid algorithm. This algorithm when applied to the popular (3-colorable) cellular and the simple (2-colorable) line networks gives a 2-competitive and 1.5-competitive solution, respectively, and by deriving lower bounds, we show the algorithm is optimal for such networks. We thus have a positive solution to the open problem posed in [28]: does a 2-competitive online algorithm exist for frequency allocation in cellular networks?We also consider the problem when the number of calls emanating from each cell is large. As it turns out, the (lower and upper) bounds on com-petitive ratios we have derived no longer stand. In particular, for line networks, we show new asymptotic lower and upper bounds of 4/3 and 1.382, respectively, which breaks through the optimal absolute bound of 1.5 we have shown. For cellular networks, we show new asymptotic lower and upper bounds of 1.5 and 1.913, respectively, which breaks through the optimal absolute bound of 2.In studying the with deletion model, we first proved that the competitive ratios for Greedy in line network and cellular network are 2 and 3, respectively.In FAL, we proposed an 5/3-competitive algorithm, say MG. After showing that the lower bound of FAL is 5/3, we can say that our new algorithm is optimal. Furthermore, we proved that the asymptotic competitive ratio for line network is 14/9.Finally, we proved that the absolute and asymptotic competitive ratio for FAC are 19/9 and 2, respectively.