Base station location and channel allocation in a cellular network with emergency coverage requirements. (English) Zbl 1068.90018
Summary: The location of base stations (BS) and the allocation of channels are of paramount importance for the performance of cellular radio networks. Also cellular service providers are now being driven by the goal to enhance performance, particularly as it relates to the receipt and transmission of emergency crash notification messages generated by automobile telematics systems. In this paper, a Mixed Integer Programming (MIP) problem is proposed, which integrates into the same model the base station location problem, the frequency channel assignment problem and the emergency notification problem. The purpose of unifying these three problems in the same model is to treat the tradeoffs among them, providing a higher quality solution to the cellular system design. Some properties of the formulation are proposed that give us more insight into the problem structure. An instance generator is developed that randomly creates test problems. A few greedy heuristics are proposed to obtain quick solutions that turn out to be very good in some cases. To further improve the optimality gap, we develop a Lagrangean heuristic technique that builds on the solution obtained by the greedy heuristics. Finally, the performance of these methods is analyzed by extensive numerical tests and a sample case study is presented.
MSC:
| 90B10 | Deterministic network models in operations research |
References:
| [1] | Akella, M. R.; Bang, C.; Beutner, R.; Delmelle, E. M.; Wilson, G.; Blatt, A.; Batta, R.; Rogerson, P. A., Evaluating the reliability of automated collision notification (ACN) systems, Accident Analysis and Prevention, 35, 349-360 (2003) |
| [2] | Blow, O.; Magliore, L.; Claridge, J. A.; Butler, K.; Young, J. S., The golden hour and the silver day: Detection and correction of occult hypo perfusion within 24 h improves outcome from major trauma, Journal of Trauma, Injury, Infection, and Critical Care, 7, 5, 964-969 (1999) |
| [3] | Bose, R., A smart technique for determining base-station locations in an urban environment, IEEE Transactions on Vehicular Technology, 50, 1, 43-47 (2001) |
| [4] | Chamaret, B., Josselin, S., Kuonen, P., Pizarroso, M., SalasManzanedo, N., Wagner, D., 1997. Radio network optimization with maximum independent set search. In: Proceedings of the IEEE/VTS 47th Vehicular Technology Conference, Phoenix, USA, vol. 2, 1997, pp. 770-774; Chamaret, B., Josselin, S., Kuonen, P., Pizarroso, M., SalasManzanedo, N., Wagner, D., 1997. Radio network optimization with maximum independent set search. In: Proceedings of the IEEE/VTS 47th Vehicular Technology Conference, Phoenix, USA, vol. 2, 1997, pp. 770-774 |
| [5] | Champion, H.R., Augenstein, J.S., Cushing, B., Digges, K.H., Hunt, R., Larkin, R., Malliaris, A.C., Sacco, W.J., Siegel, J.H., 1998. Automatic crash notification: The public safety component of the intelligent transportation system. AirMed, p. 36; Champion, H.R., Augenstein, J.S., Cushing, B., Digges, K.H., Hunt, R., Larkin, R., Malliaris, A.C., Sacco, W.J., Siegel, J.H., 1998. Automatic crash notification: The public safety component of the intelligent transportation system. AirMed, p. 36 |
| [6] | Church, R. L.; ReVelle, C., The maximal covering location problem, Regional Science, 30, 101-118 (1974) |
| [7] | Clark, D. E.; Cushing, B. E., Predicted effect of crash notification on traffic mortality, Accident Analysis and Prevention, 34, 507-513 (2002) |
| [8] | Daskin, M. S., Network and Discrete Location: Models, Algorithms and Applications (1995), John Wiley and Sons, Inc: John Wiley and Sons, Inc New York · Zbl 0870.90076 |
| [9] | Delmelle, E., Rogerson, P., Akella, M., Batta, R., Blatt, A., Wilson, G. A spatial model of remote signal strength indicator values. Transportation Research C, submitted for publication; Delmelle, E., Rogerson, P., Akella, M., Batta, R., Blatt, A., Wilson, G. A spatial model of remote signal strength indicator values. Transportation Research C, submitted for publication · Zbl 1068.90018 |
| [10] | Evanco, W. M., The potential impact of rural mayday systems on vehicular crash fatalities, Accident Analysis and Prevention, 31, 455-462 (1999) |
| [11] | Federal Communications Commission (FCC), 1996. Revision of the Commission’s Rules to Ensure Compatibility with Enhanced 911 Emergency Calling Systems. Available from <http://www.nena.org/govtaffairs/Leg/94-102 |
| [12] | Fritsch, T., Tutschku, K., Leibnitz, K., 1995. Field strength prediction by ray-tracing for adaptive base station positioning in mobile communication networks. In: Proceedings of the 2nd ITG Conference on Mobile Communication’95, Neu Ulm; Fritsch, T., Tutschku, K., Leibnitz, K., 1995. Field strength prediction by ray-tracing for adaptive base station positioning in mobile communication networks. In: Proceedings of the 2nd ITG Conference on Mobile Communication’95, Neu Ulm |
| [13] | Ibbetson, L.J., Lopes, L.B., 1997. An automatic base site placement algorithm. In: Proceedings of the IEEE/VTS 47th Vehicular Technology Conference, Phoenix, USA, vol. 2, pp. 760-764; Ibbetson, L.J., Lopes, L.B., 1997. An automatic base site placement algorithm. In: Proceedings of the IEEE/VTS 47th Vehicular Technology Conference, Phoenix, USA, vol. 2, pp. 760-764 |
| [14] | Jacobs, L. M.; Sinclair, A.; Beiser, A.; D’Agostino, R. B., Prehospital advanced life support: Benefits in trauma, Journal of Trauma, 24, 8-13 (1984) |
| [15] | Lerner, E. B.; Moscati, R. M., The golden hour: Scientific fact or medical “Urban Legend”?, Academic Emergency Medicine, 8, 758-760 (2001) |
| [16] | Macario, R.C.V., 1997. Cellular radio: Principles and design. McGraw-Hill Series on Telecommunications, second ed., p. 276; Macario, R.C.V., 1997. Cellular radio: Principles and design. McGraw-Hill Series on Telecommunications, second ed., p. 276 |
| [17] | National Highway Transportation & Safety Authority (NHTSA), 2000. Traffic Safety Facts 1999. Overview, DOT HS 809 092; National Highway Transportation & Safety Authority (NHTSA), 2000. Traffic Safety Facts 1999. Overview, DOT HS 809 092 |
| [18] | New York State Department of Transportation, 2000. 2000 highway mileage report. Highway Data Service Bureau. Available from <http://www.dot.state.ny.us/tech_serv/high/files/erie.pdf; New York State Department of Transportation, 2000. 2000 highway mileage report. Highway Data Service Bureau. Available from <http://www.dot.state.ny.us/tech_serv/high/files/erie.pdf |
| [19] | Ravindra, A. K.; Thomas, M. L.; James, O. B., Network Flows-Theory, Algorithms and Applications (1993), Prentice Hall · Zbl 1201.90001 |
| [20] | Sherali, H. D.; Pendyala, C. M.; Rappaport, T. S., Optimal location of transmitters for micro-cellular radio communication system design, IEEE Journal on Selected Areas in Communications, 14, 4, 662-673 (1996) |
| [21] | SmartRisk, 1998. The economic burden of unintentional injury in Canada; SmartRisk, 1998. The economic burden of unintentional injury in Canada |
| [22] | Statamatelos, D.; Ephremides, A., Spectral efficiency and optimal base placement for indoor wireless networks, IEEE JSAC, 1, 434-438 (1996) |
| [23] | Tcha, D. W.; Myung, Y. S.; Kwon, J. H., Base station location in a cellular CDMA system, Telecommunication Systems, 14, 163-173 (2000) · Zbl 1076.90514 |
| [24] | Tutschku, K., Gerlich, N., Tran-Gia, P., 1996. An integrated approach to cellular network planning. In: Proceedings of the 7th International Network Planning Symposium (Networks 96), pp. 185-190; Tutschku, K., Gerlich, N., Tran-Gia, P., 1996. An integrated approach to cellular network planning. In: Proceedings of the 7th International Network Planning Symposium (Networks 96), pp. 185-190 |
| [25] | U.S. Bureau of the Census, 2000. Available from <www.geographynetwork.com/data/tiger2000/index.html; U.S. Bureau of the Census, 2000. Available from <www.geographynetwork.com/data/tiger2000/index.html |
| [26] | Walker, J., 1996. Methodology application: Logistics regression using the crash outcome data evaluation system (CODES) data. Technical report for the National Highway Traffic Safety Administration (NHTSA) and National Center for Statistics and Analysis (NCSA) in Department of Transportation, September; Walker, J., 1996. Methodology application: Logistics regression using the crash outcome data evaluation system (CODES) data. Technical report for the National Highway Traffic Safety Administration (NHTSA) and National Center for Statistics and Analysis (NCSA) in Department of Transportation, September |
| [27] | Wright, M.H., 1998. Optimization methods for base station placement in wireless applications. In: IEEE Vehicular Technology Conference Proceedings, pp. 387-391; Wright, M.H., 1998. Optimization methods for base station placement in wireless applications. In: IEEE Vehicular Technology Conference Proceedings, pp. 387-391 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
