We propose here a new and optimal one-to-all broadcasting algorithm for cellular networks. The one-to-all broadcasting is used in cellular mobile network in order to answer to the following problem: when a subscriber would call, he communicates the destination phone number to the closest base station. Then, the base station should broadcast a message (containing the destination phone number) to all other base stations in order to connect the subscriber to the being phoned.
To cover the biggest area with the minimum number of base stations without empty spaces, and to minimize the interference problem between cells, a tessellation of the plane is needed. Classically, the regular hexagonal mesh is used for this tessellation. The locations of central offices of a large telephone network form an irregular point pattern, because of spatial variations of population density, consumer demand, other geographical and technological factors... In this way the classical model based on hexagonal cells does not really take into account these constraints: a more realistic model presented here is based on Voronoï diagram and Delaunay triangulation. This cellular network can be seen as a planar triangular graph and the triangles making up it are not regular.
We present here the classical cellular model and its associated one-to-all broadcasting algorithm. Next, the cellular network based on Voronoï diagram and the Delaunay triangulation are described. Then we give the full description of our one-to-all broadcasting algorithm with an analysis of the complexity and a complete example.