Sparse telephone gateway for internet telephony

摘要

Internet telephony is promising for long-distance calls. To serve the general public, a service provider can operate a telephone gateway in each servicing city to bridge the local telephone network and the Internet, so that users can use telephones or mobile phones to access these telephone gateways for long-distance calls. The service provider should serve many cities to attain good service coverage but it is costly to operate telephone gateways in all of these cities. In this paper, we propose a sparse telephone gateway configuration to serve many cities cost-effectively. Using this configuration, if the service provider serves N cities, it operates telephone gateways in only M cities where M < N. If a telephone gateway is available in a city, users in this city access this gateway for service; otherwise, they access the gateway in a nearby city through inter-city calls for service. It is necessary to optimize the sparse telephone gateway configuration to achieve the best cost-effectiveness. We formulate this problem in which the expected revenue is maximized, prove that it is NP-hard, and design an efficient two-stage heuristic algorithm to solve it. Numerical results show that the sparse telephone gateway configuration is more cost-effective than the existing configuration.