×

Radio communications interdiction problem under deterministic and probabilistic jamming. (English) Zbl 1458.90196

Summary: The radio communications interdiction problem (RCIP) seeks to identify the locations of transmitters on the battlefield that will lead to a robust radio communications network by anticipating the effects of intentional radio jamming attacks used by an adversary during electronic warfare. RCIP is a sequential game defined between two opponents that target each other’s military units in a conventional warfare. First, a defender locates a limited number of transmitters on the defender’s side of the battlefield to optimize the relay of information among its units. After observing the locations of radio transmitters, an attacker locates a limited number of radio jammers on the attacker’s side to disrupt the communication network of the defender. We formulate RCIP as a binary bilevel (max-min) programming problem, present the equivalent single level formulation, and propose an exact solution method using a decomposition scheme. We enhance the performance of the algorithm by utilizing dominance relations, preprocessing, and initial starting heuristics. To reflect a more realistic jamming representation, we also introduce the probabilistic version of RCIP where a jamming probability is associated at each receiver site as a function of the prevalent jamming to signal ratios leading to an expected coverage of receivers as an objective function. We approximate the nonlinearity in the jamming probability function using a piecewise linear convex function and solve this version by adapting the decomposition algorithm constructed for RCIP. Our extensive computational results on realistic scenarios show the efficacy of the solution approaches and provide valuable tactical insights.

MSC:

90B18 Communication networks in operations research
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adamy, D. L., EW 101 A First Course in Electronic Warfare (2001), Artech House
[2] Ahmed, I. E.; Qazi, B. R.; Elmirghani, J. M., Energy-efficient base stations locations optimisation in an airport environment, Next Generation Mobile Applications, Services and Technologies (NGMAST), 199-204 (2012), IEEE
[3] Akella, M. R.; Batta, R.; Delmelle, E. M.; Rogerson, P. A.; Blatt, A.; Wilson, G., Base station location and channel allocation in a cellular network with emergency coverage requirements, Eur. J. Oper. Res., 164, 2, 301-323 (2005) · Zbl 1068.90018
[4] Aksen, D.; Piyade, N.; Aras, N., The budget constrained r-interdiction median problem with capacity expansion, Cent. Eur. J. Oper. Res., 18, 3, 269-291 (2010) · Zbl 1204.90058
[5] Alekseeva, E.; Kochetova, N.; Kochetov, Y.; Plyasunov, A., Heuristic and exact methods for the discrete \((r|p)\)-centroid problem, Evolutionary Computation in Combinatorial Optimization, 11-22 (2010), Springer
[6] Aragon-Zavala, A., Antennas and Propagation for Wireless Communication Systems (2008), John Wiley & Sons
[7] Bard, J. F., Practical Bilevel Optimization: Algorithms and Applications, 30 (2013), Springer Science & Business Media
[8] Bard, J. F.; Moore, J. T., An algorithm for the discrete bilevel programming problem, Nav. Res. Logist., 39, 3, 419-435 (1992) · Zbl 0751.90111
[9] Batta, R.; Dolan, J. M.; Krishnamurthy, N. N., The maximal expected covering location problem: revisited, Transp. Sci., 23, 4, 277-287 (1989) · Zbl 0692.90040
[10] Beidel, E.; Magnuson, S.; Erwin, S., 10 technologies the US military will need for the next war, Natl. Def. Mag., November (2011)
[11] Ben-Ayed, O., Bilevel linear programming, Comput. Oper. Res., 20, 5, 485-501 (1993) · Zbl 0783.90068
[12] Berman, O.; Drezner, T.; Drezner, Z.; Wesolowsky, G. O., A defensive maximal covering problem on a network, Int. Trans. Oper. Res., 16, 1, 69-86 (2009) · Zbl 1153.90332
[13] Brown, G.; Carlyle, M.; Abdul-Ghaffar, A.; Kline, J., A defender-attacker optimization of port radar surveillance, Nav. Res. Logist., 58, 3, 223-235 (2011)
[14] Brown, G.; Carlyle, M.; Diehl, D.; Kline, J.; Wood, K., A two-sided optimization for theater ballistic missile defense, Oper. Res., 53, 5, 745-763 (2005) · Zbl 1165.90704
[15] Brown, G.; Carlyle, M.; Harney, R.; Skroch, E.; Wood, K., Interdicting a nuclear-weapons project, Oper. Res., 57, 4, 866-877 (2009) · Zbl 1226.90142
[16] Brown, G.; Carlyle, M.; Salmerón, J.; Wood, K., Defending critical infrastructure, Interfaces, 36, 6, 530-544 (2006)
[17] Chapman, S. J.; Hurley, S.; Kapp-Rawnsley, R., Optimising radio network design, NATO Symposium Frequency Assignment, Sharing and Conservation (1999)
[18] Church, R.; ReVelle, C., The maximal covering location problem, Papers of the Regional Science Association, 32, 101-118 (1974), Springer
[19] Church, R. L.; Scaparra, M. P., Protecting critical assets: the \(r\)-interdiction median problem with fortification, Geogr. Anal., 39, 2, 129-146 (2007)
[20] Colson, B.; Marcotte, P.; Savard, G., An overview of bilevel optimization, Ann. Oper. Res., 153, 1, 235-256 (2007) · Zbl 1159.90483
[21] Commander, C. W.; Pardalos, P. M.; Ryabchenko, V.; Shylo, O.; Uryasev, S.; Zrazhevsky, G., Jamming communication networks under complete uncertainty, Optim. Lett., 2, 1, 53-70 (2008) · Zbl 1145.94008
[22] Commander, C. W.; Pardalos, P. M.; Ryabchenko, V.; Uryasev, S.; Zrazhevsky, G., The wireless network jamming problem, J. Comb. Optim., 14, 4, 481-498 (2007) · Zbl 1149.90124
[23] Daskin, M. S., A maximum expected covering location model: formulation, properties and heuristic solution, Transp. Sci., 17, 1, 48-70 (1983)
[24] Dempe, S., Foundations of Bilevel Programming (2002), Springer · Zbl 1038.90097
[25] Dempe, S., Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52, 3, 333-359 (2003) · Zbl 1140.90493
[26] Feng, J.; Li, X.; Pasiliao, E. L.; Shea, J. M., Jammer placement to partition wireless network, Globecom Workshops (GC Wkshps), 2014, 1487-1492 (2014), IEEE
[27] Grover, K.; Lim, A.; Yang, Q., Jamming and anti-jamming techniques in wireless networks: a survey, Int. J. Ad Hoc Ubiquitous Comput., 17, 4, 197-215 (2014)
[28] Iellamo, S.; Alekseeva, E.; Chen, L.; Coupechoux, M.; Kochetov, Y., Competitive location in cognitive radio networks, 4OR, 13, 1, 81-110 (2015) · Zbl 1314.90048
[29] Israeli, E.; Wood, R. K., Shortest-path network interdiction, Networks, 40, 2, 97-111 (2002) · Zbl 1027.90106
[30] Ji, Z.; Sarkar, T. K.; Li, B.-H., Methods for optimizing the location of base stations for indoor wireless communications, IEEE Trans. Antennas Propag., 50, 10, 1481-1483 (2002)
[31] Jones, D. R.; Perttunen, C. D.; Stuckman, B. E., Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 1, 157-181 (1993) · Zbl 0796.49032
[32] Konak, A.; Kulturel-Konak, S.; Snyder, L. V., A game-theoretic genetic algorithm for the reliable server assignment problem under attacks, Comput. Ind. Eng., 85, 73-85 (2015)
[33] Kouhbor, S.; Ugon, J.; Mammadov, M.; Rubinov, A.; Kruger, A., Coverage in WLAN: optimization model and algorithm, Proceeding of the First IEEE International Conference on Wireless Broadband and Ultra Wideband Communications, 13-16 (2006)
[34] Labbé, M.; Violin, A., Bilevel programming and price setting problems, 4OR, 11, 1, 1-30 (2013) · Zbl 1259.90112
[35] Lakashminarasimman, N.; Baskar, S.; Alphones, A.; Iruthayarajan, M. W., Multiobjective mobile antenna location identification using evolutionary optimization algorithm, International Conference on Computing Communication and Networking Technologies (ICCCNT), 1-4 (2010), IEEE
[36] Lee, G.; Murray, A. T., Maximal covering with network survivability requirements in wireless mesh networks, Comput. Environ. Urban Syst., 34, 1, 49-57 (2010)
[37] Mahmutogullari, A. I.; Kara, B. Y., Hub location under competition, Eur. J. Oper. Res., 250, 1, 214-225 (2016) · Zbl 1346.90507
[38] Mathar, R.; Niessen, T., Optimum positioning of base stations for cellular radio networks, Wirel. Netw., 6, 6, 421-428 (2000) · Zbl 1012.68927
[39] Medal, H. R., The wireless network jamming problem subject to protocol interference, Networks, 67, 2, 111-125 (2016) · Zbl 1390.90177
[40] Moore, J. T.; Bard, J. F., The mixed integer linear bilevel programming problem, Oper. Res., 38, 5, 911-921 (1990) · Zbl 0723.90090
[41] Morton, D. P.; Pan, F.; Saeger, K. J., Models for nuclear smuggling interdiction, IIE Trans., 39, 1, 3-14 (2007)
[42] Mpitziopoulos, A.; Gavalas, D.; Konstantopoulos, C.; Pantziou, G., A survey on jamming attacks and countermeasures in WSNs, IEEE Commun. Surv. Tutorials, 11, 4, 42-56 (2009)
[43] Nandi, A. K.; Medal, H. R.; Vadlamani, S., Interdicting attack graphs to protect organizations from cyber attacks: a bi-level defender-attacker model, Comput. Oper. Res., 75, 118-131 (2016) · Zbl 1349.90821
[44] Nebro, A. J.; Alba, E.; Molina, G.; Chicano, F.; Luna, F.; Durillo, J. J., Optimal antenna placement using a new multi-objective CHC algorithm, Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, 876-883 (2007), ACM
[45] Nicholas, P. J.; Alderson, D. L., Fast, effective transmitter placement in wireless mesh networks, Military Oper. Res., 17, 4, 69-84 (2012)
[46] Nicholas, P. J.; Alderson, D. L., Designing Interference-Robust Wireless Mesh Networks Using a Defender-Attacker-Defender Model, Technical Report, DTIC Document (2015)
[47] OHanley, J. R.; Church, R. L., Designing robust coverage networks to hedge against worst-case facility losses, Eur. J. Oper. Res., 209, 1, 23-36 (2011) · Zbl 1208.90105
[48] Patel, D. J.; Batta, R.; Nagi, R., Clustering sensors in wireless ad hoc networks operating in a threat environment, Oper. Res., 53, 3, 432-442 (2005) · Zbl 1165.90370
[49] Pessoa, A. A.; Poss, M.; Roboredo, M. C.; Aizemberg, L., Solving bilevel combinatorial optimization as bilinear min-max optimization via a branch-and-cut algorithm, Anais do XLV Simpósio Brasileiro de Pesquisa Operacional (2013)
[50] Prasad, S.; Thuente, D. J., Jamming attacks in 802.11g — a cognitive radio based approach, MILCOM Military Communications Conference, 1219-1224 (2011), IEEE
[51] Rappaport, T. S., Wireless Communications: Principles and Practice (2002), Prentice Hall
[52] Roboredo, M. C.; Pessoa, A. A., A branch-and-cut algorithm for the discrete \((r|p)\)-centroid problem, Eur. J. Oper. Res., 224, 1, 101-109 (2013) · Zbl 1292.90172
[53] Ryan, M. J.; Frater, M. R., Tactical Communications for the Digitized Battlefield (2002), Artech House
[54] Scaparra, M. P.; Church, R. L., A bilevel mixed-integer program for critical infrastructure protection planning, Comput. Oper. Res., 35, 6, 1905-1923 (2008) · Zbl 1139.90439
[55] Schleher, D. C., Electronic Warfare in the Information Age (1999), Artech House, Inc.
[56] Shankar, A., Optimal jammer placement to interdict wireless network services, Technical Report, DTIC Document (2008)
[57] Sherali, H. D.; Pendyala, C. M.; Rappaport, T. S., Optimal location of transmitters for micro-cellular radio communication system design, IEEE J. Sel. Areas Commun., 14, 4, 662-673 (1996)
[58] Simaan, M.; Cruz, J. B., On the Stackelberg strategy in nonzero-sum games, J. Optim. Theory Appl., 11, 5, 533-555 (1973) · Zbl 0243.90056
[59] Stackelberg, H., The Theory of the Market Economy (1952), Oxford University Press
[60] Starita, S.; Scaparra, M. P., Optimizing dynamic investment decisions for railway systems protection, Eur. J. Oper. Res., 248, 2, 543-557 (2016) · Zbl 1346.90228
[61] U. S. Joint Chief of Staff, Joint Interdiction, Joint Publication 3-03 (2016), U.S. Joint Chief of Staff
[62] Vadlamani, S.; Eksioglu, B.; Medal, H.; Nandi, A., Jamming attacks on wireless networks: a taxonomic survey, Int. J. Prod. Econ., 172, 76-94 (2016)
[63] Vadlamani, S.; Medal, H.; Eksioglu, B.; Li, P., A bi-level programming model for the wireless network jamming placement problem, IIE Annual Conference. Proceedings, 1003 (2014)
[64] Vadlamani, S.; Schweitzer, D.; Medal, H.; Nandi, A.; Eksioglu, B., A mixed-integer programming approach for locating jamming devices in a flow-jamming attack, Comput. Oper. Res., 95, 83-96 (2018) · Zbl 1458.90177
[65] Whitaker, R. M.; Hurley, S., On the optimality of facility location for wireless transmission infrastructure, Comput. Ind. Eng., 46, 1, 171-191 (2004)
[66] Wood, R. K., Deterministic network interdiction, Math. Comput. Model., 17, 2, 1-18 (1993) · Zbl 0800.90772
[67] Wood, R. K., Bilevel network interdiction models: formulations and solutions, Wiley Encyclopedia of Operations Research and Management Science, 1-11 (2011)
[68] Xiao, L.; Johansson, M.; Boyd, S. P., Simultaneous routing and resource allocation via dual decomposition, IEEE Trans. Commun., 52, 7, 1136-1144 (2004)
[69] Zimmermann, J.; Höns, R.; Mühlenbein, H., Encon: an evolutionary algorithm for the antenna placement problem, Comput. Ind. Eng., 44, 2, 209-226 (2003)
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.