×

Wireless LAN transmitter location under the threat of jamming attacks. (English) Zbl 1458.90194

Summary: This paper studies the optimal placement of wireless access points in a network under the threat of jamming. We addressed this problem with a tri-level mixed-integer program. In the top level, the defender seeks to optimally place a set of capacity-limited access points to maximize total connectivity. In the middle level, an attacker seeks to optimally place a set of jammers that may be relocated between time periods to minimize total connectivity. In the bottom level, demand points seek to connect to capacitated access points such that their connections maximize their network utility. This model was examined from two viewpoints: a non-additive model in which connections were jammed if they fell within a jammer’s radius, and an additive model in which connections were jammed if enough jamming power was interfering with the connection. We proposed a solution methodology which solved a modified bi-level program efficiently via implicit enumeration and dynamic constraint generation. We showed that the addition of just one access point provided a significant increase to network connectivity, different topologies had different robustness when different utility functions were considered, and optimal jammer placement varied significantly across different topologies. Through our experiments on five topologies, we found the Spacious and Median topologies were closest to the optimal access point placement.

MSC:

90B18 Communication networks in operations research
90C11 Mixed integer programming
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aksen, D.; Akca, S. S.; Aras, N., A bilevel partial interdiction problem with capacitated facilities and demand outsourcing, Comput. Oper. Res., 41, 346-358 (2014) · Zbl 1348.91080
[2] Arulselvan, A.; Commander, C. W.; Elefteriadou, L.; Pardalos, P. M., Detecting critical nodes in sparse graphs, Comput. Oper. Res., 36, 7, 2193-2200 (2009) · Zbl 1158.90411
[3] Bard, J. F.; Moore, J. T., A branch and bound algorithm for the bilevel programming problem, SIAM J. Sci. Statist.Comput., 11, 2, 281-292 (1990) · Zbl 0702.65060
[4] Baroud, H.; Ramirez-Marquez, J. E.; Barker, K.; Rocco, C. M., Stochastic measures of network resilience: applications to waterway commodity flows, Risk Anal., 34, 7, 1317-1335 (2014)
[5] Bayraktaroglu, E.; King, C.; Liu, X.; Noubir, G.; Rajaraman, R.; Thapa, B., Performance of ieee 802.11 under jamming, Mobile Netw. Appl., 18, 5, 678-696 (2013)
[6] Capone, A.; Chen, L.; Gualandi, S.; Yuan, D., A new computational approach for maximum link activation in wireless networks under the sinr model, IEEE Trans. Wireless Commun., 10, 5, 1368-1372 (2011)
[7] Cappanera, P.; Scaparra, M. P., Optimal allocation of protective sources in shortest-path networks, Trans. Sci., 45, 1, 64-80 (2011)
[8] Church, R. L.; Scaparra, M. P.; Middleton, R. S., Identifying critical infrastructure: the median and covering facility interdiction problems, Annal. Assoc. Amer. Geograph., 94, 3, 491-502 (2004)
[9] 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
[10] 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
[11] Dallaire, A.; Fleurent, C.; Rousseau, J.-M., Dynamic constraint generation in crewopt, a column generation approach for transit crew scheduling, Comput.-Aided Sched. Public Transp. (CASPT), 73-90 (2004)
[12] Du, W.; Deng, J.; Han, Y. S.; Chen, S.; Varshney, P. K., A key management scheme for wireless sensor networks using deployment knowledge, INFOCOM 2004. Twenty-third Ann. Joint Conf. IEEE comput.Commun.Soc., 1, 597 (2004)
[13] Held, H.; Hemmecke, R.; Woodruff, D. L., A decomposition algorithm applied to planning the interdiction of stochastic networks, Naval Res. Logist. (NRL), 52, 4, 321-328 (2005) · Zbl 1104.90010
[14] Held, H.; Woodruff, D. L., Heuristics for multi-stage interdiction of stochastic networks, J. Heurist., 11, 5-6, 483-500 (2005) · Zbl 1122.90318
[15] Israeli, E.; Wood, R. K., Shortest-path network interdiction, Networks, 40, 2, 97-111 (2002) · Zbl 1027.90106
[16] Iyer, A.; Rosenberg, C.; Karnik, A., What is the right model for wireless channel interference?, IEEE Trans. Wireless Commun., 8, 5, 2662-2671 (2009)
[17] Jiang, S.; Xue, Y., Optimal wireless network restoration under jamming attack, Computer Communications and Networks, 2009. ICCCN 2009. Proceedings of the 18th International Conference on, 1-6 (2009)
[18] Law, Y. W.; Palaniswami, M.; van Hoesel, L.; Doumen, J.; Hartel, P.; Havinga, P., Energy-efficient link-layer jamming attacks against wireless sensor network mac protocols, ACM Trans. Sensor Netw. (TSON), 5, 1, 6 (2009)
[19] Lim, C.; Smith, J. C., Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Trans., 39, 1, 15-26 (2007)
[20] Liu, Y.; Ning, P.; Dai, H.; Liu, A., Randomized differential dsss: jamming-resistant wireless broadcast communication, INFOCOM, 2010 Proceedings IEEE, 1-9 (2010)
[21] Lunday, B. J.; Sherali, H. D., A dynamic network interdiction problem, Informatica, 21, 4, 553-574 (2010) · Zbl 1229.91093
[22] Ma, K.; Zhang, Y.; Trappe, W., Mobile network management and robust spatial retreats via network dynamics, Mobile Adhoc and Sensor Systems Conference, 2005. IEEE International Conference on, 235-242 (2005)
[23] Malaviya, A.; Rainwater, C.; Sharkey, T., Multi-period network interdiction problems with applications to city-level drug enforcement, IIE Trans., 44, 5, 368-380 (2012)
[24] Medal, H. R., The wireless network jamming problem subject to protocol interference, Networks, 67, 2, 111-125 (2016) · Zbl 1390.90177
[25] Morton, D. P., Stochastic network interdiction, Wiley Encyclopedia of Operations Research and Management Science (2011)
[26] Morton, D. P.; Pan, F.; Saeger, K. J., Models for nuclear smuggling interdiction, IIE Trans., 39, 1, 3-14 (2007)
[27] Navda, V.; Bohra, A.; Ganguly, S.; Rubenstein, D., Using channel hopping to increase 802.11 resilience to jamming attacks, INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, 2526-2530 (2007)
[28] Nguyen, D. T.; Shen, Y.; Thai, M. T., Detecting critical nodes in interdependent power networks for vulnerability assessment, IEEE Trans. Smart Grid, 4, 1, 151-159 (2013)
[29] Noubir, G., On connectivity in ad hoc networks under jamming using directional antennas and mobility, WWIC, 186-200 (2004) · Zbl 1128.68308
[30] Noubir, G.; Lin, G., Low-power dos attacks in data wireless lans and countermeasures, SIGMOBILE Mob. Comput. Commun. Rev., 7, 3, 29-30 (2003)
[31] Pan, F.; Charlton, W. S.; Morton, D. P., A stochastic program for interdicting smuggled nuclear material, Netw.Interdict.Stochast.Integer Programm., 1-19 (2003) · Zbl 1049.90049
[32] Pan, F.; Morton, D. P., Minimizing a stochastic maximum-reliability path, Networks, 52, 3, 111-119 (2008) · Zbl 1172.90345
[33] Pelechrinis, K.; Iliofotou, M.; Krishnamurthy, S. V., Denial of service attacks in wireless networks: the case of jammers, IEEE Commun. Surv. Tutor., 13, 2, 245-257 (2011)
[34] Pelechrinis, K.; Koutsopoulos, I.; Broustis, I.; Krishnamurthy, S. V., Lightweight jammer localization in wireless networks: System design and implementation, Global Telecommunications Conference, 2009. GLOBECOM 2009. IEEE, 1-6 (2009)
[35] Ramirez-Marquez, J. E., A bi-objective approach for shortest-path network interdiction, Comput. Indus. Eng., 59, 2, 232-240 (2010)
[36] Salmeron, J.; Wood, K.; Baldick, R., Worst-case interdiction analysis of large-scale electric power grids, IEEE Trans. Power Syst., 24, 1, 96-104 (2009)
[37] 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
[38] Schweitzer, D.; Jafari-Marandi, R.; Medal, H., Analyzing the robustness of a wireless network array to mobile jammers, Comput. Indus. Eng., 1, 1, 111-112 (2017)
[39] Wood, R. K., Deterministic network interdiction, Math. Comput. Model., 17, 2, 1-18 (1993) · Zbl 0800.90772
[40] Zeng, B.; Zhao, L., Solving two-stage robust optimization problems using a column-and-constraint generation method, Oper. Res. Lett., 41, 5, 457-461 (2013) · Zbl 1286.90143
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.