Method for interference-robust transmitter placement in wireless mesh networks

[0001] This application is a non-provisional application of and claims priority to U.S. Patent Application 62/097,938, filed on Dec. 30, 2014, which is hereby incorporated by reference in its entirety.

[0002] The present invention relates generally to communications systems and particularly to wireless mesh networks. Still more particularly, the invention relates to a computer-implemented system for quickly and particularly designing a wireless mesh network to maximize robustness against jamming attacks by an intelligent adversary.

[0003] Wireless mesh networks (WMNs) are interconnected systems of wireless access points (APs) that provide untethered network connectivity for a group of users that require data, voice, and/or video communication. Each AP has two radio devices: the first connects to local client devices, such as laptops and portable digital assistants (PDAs); the second connects to other APs to create a backhaul network. Communication between users on a WMN passes from a source client through one or more APs before reaching a destination client. To function, APs require only a local power source, such as a battery or portable generator. This property of WMNs make them well-suited to operations in austere environments, such as combat and humanitarian assistance disaster relief (HA/DR) operations. For an introduction to WMNs see Nicholas, P., “Optimal transmitter placement in wireless mesh networks,” (masters thesis, Naval Postgraduate School, 2009).

[0004] The wireless access medium of a WMN makes it particularly vulnerable to attack and exploitation. Such actions may include passive eavesdropping and packet capture, spoofing trusted identities to gain unauthorized access to the network, injecting malicious code, or denial of service (DoS) attacks. During physical-layer noise jamming DoS attacks, an attacker constantly broadcasts noise on the same radio frequency used by the WMN in an attempt to overpower the friendly signal, degrading or denying use of the channels. Powerful commercial and military jamming systems are readily available, but this type of attack can be conducted with inexpensive equipment and little technological prowess, and can be very challenging to defend against. Even unintentional interference can be as harmful as an intentional attack. Hence it is of increasing concern in both civilian and military operating environments.

[0005] There has been much recent research in defending WMNs from attack. Some approaches describe a method of mapping the areas affected by physical layer jamming to avoid placing sensors in these denied areas, or rely on algorithms to improve the classification rate of jamming attacks. See Wood et al., JAM: A jammed-area mapping service for sensor networks, Proceedings of the 24th IEEE International Real-Time Systems Symposium (RTSS'03) (2003), and see Xu et al., The feasibility of launching and detecting jamming attacks in wireless networks, MobiHoc 05 (2005). Others increase the robustness of wireless networks to attacks, including the use of directional antennae, frequency hopping and spread spectrum technology, lower data rates, fiber-optic backhaul networks, encryption and error correction, frequency-agile control channels, and adjustment of transmission power, but do not specifically consider defensive placement or mobility of APs. See Ståhlberg, Radio jamming attacks against two popular mobile networks, Seminar on Network Security, (2002); see also Lazos et al, Selective jamming/dropping insider attacks in wireless mesh networks. IEEE Network, 25(1) (2011); see also Xu et al., On adjusting power to defend wireless networks from jamming. Proceedings of the 1_st ACM Conference on Wireless Security, (2008); see also Wood et al., DEEJAM: Defeating energy-efficient jamming in IEEE 802.15.4-based wireless networks. 4_th Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks, (2007). Others examine spatial retreats, i.e., moving APs physically away from the sources of interference, as a form of defense against a jamming attack, assume that jammers are stationary, and minimize the damage done by coordinating the retreat of APs from the effective range of the adversary's jammers. However, they also fail to consider jammers that could then move and attack the newly-configured network. See Xu et al., Channel surfing and spatial retreats: defenses against wireless denial of service, Proceedings of 3rd ACM Workshop on Wireless Security (2004); see also Ma et al., Mobile network management and robust spatial retreats via network dynamics, Mobile Adhoc and Sensor Systems Conference, 2005 (2005).

[0006] Some investigations have utilized game theory to model optimal jamming attack and detection strategies, but have considered only strategic-form games wherein players move simultaneously, rather than extensive form games wherein players move sequentially. See Thamilarasu et al., Game theoretic modeling of jamming attacks in ad hoc networks, Proceedings Of the 18_th International Conference on Computer Communications and Networks, (2009). Others have similarly considered the deliberate placement of jammers by an intelligent adversary (called the attacker) to maximally disrupt network operation, but have not investigated a continuous space for jammer placement (and therefore an infinite number of possible locations). See Shankar, Optimal jammer placement to interdict wireless network services, (Master's Thesis). Monterey, Calif.: Naval Postgraduate School (2008).

[0007] Presented here is a computer-implemented system for forming robust wireless mesh networks in environments where jamming is expected. Unlike previous efforts focusing on static or random jamming, the computer-implemented system disclosed considers WMN network design in the presence of an intelligent adversary who observes the network and then places jammer(s) to maximally disrupt network performance. In this way, the computer implemented system provides network designs which maximize robustness to the worst possible jamming attack, rather than defending against a specific one.

[0008] These and other objects, aspects, and advantages of the present disclosure will become better understood with reference to the accompanying description and claims.

[0009] The disclosure provides a computer-implemented system for establishing a wireless mesh network (WMN) resistant to degradation induced by deliberate jamming or other electromagnetic interference (EMI) emanating from point sources within an operating area. The computer-implemented system provides WMN Access Point (AP) locations that minimize disruptions to client coverage caused by jammers, subject to constraints on network service. The computer-implemented system comprises a computer-based apparatus which considers network design in the presence of an intelligent adversary capable of observing the WMN and placing jammers to maximally disrupt coverage, rather than merely considering static or random jamming.

[0010] The computer implemented system comprises a computer-based apparatus which provides AP locations within a geographic area by successively analyzing AP locations λ and jammer locations χ through quantification of an objective function having the general form Z(λ,χ)=Z_coverage(λ,χ)−w Z_flow(λ,χ), where Z_coverage(λ,χ) reflects resulting coverage shortfall within the geographic area for a given λ and a given χ, Z_flow(λ,χ) reflects and traffic flows within the geographic area for the given λ and the given χ, and w is a scalar reflecting the relative weight of the two terms. The computer-based apparatus employs a nested analysis by selecting an initial set of AP locations λ, then iteratively analyzing selected jammer locations χ against the initial set of AP locations λ using the physical characteristics of the geographic area, selected technical specifications of the WMN, and quantification of the objective function Z(λ,χ). Upon completing this inner loop, the computer-based apparatus returns to the outer loop to select a subsequent set of AP locations λ, and repeats the inner loop analysis to determine the most disruptive jammer locations χ for the subsequent set of AP locations λ. This process repeats until selected stopping criterion are satisfied. At the conclusion of the process, the computer-based apparatus provides the final set of AP locations λ which most effectively counters the most disruptive set of jammer locations χ located during the iterative process. The final set of AP locations λ thereby identifies the locations of APs to create a WMN that is the most robust to the worst possible jamming attack identified. Such an attack could represent the actions of a rational human opponent, or the worst-case positioning of unintentional interference sources such as civilian radios, other radio frequency (RF) devices, or high-voltage electrical devices.

[0011] In a particular embodiment, stopping criteria for the inner and outer loops are based on a specified number of iterations. In another embodiment, the stopping criteria is based on the difference between quantified objective functions in successive iterations. In a further embodiment, the computer-based apparatus selects the subsequent set of AP locations λ based on minimizing the impact of the most maximally disruptive set of χ yet encountered in the process, and utilizing that λ configuration as the subsequent set of AP locations λ.

[0012] In some embodiments, the computer-implemented system further comprises a two-dimensional display in data communication with the computer-based apparatus, and provides graphic representation of the operating area and the resultant final set of AP locations λ. In another embodiment, the two-dimensional display provides the discrete coverage regions within the operating area, and provides the coverage shortfalls expected for the final set of AP locations λ given the maximally disruptive jammer placement.

[0013] Embodiments in accordance with the invention are best understood by reference to the following detailed description when read in conjunction with the accompanying drawings.

[0028] Embodiments in accordance with the invention are further described herein with reference to the drawings.

[0029] The disclosure provides a computer-implemented system for establishing a wireless mesh network (WMN) resistant to degradation induced by deliberate jamming or other electromagnetic interference (EMI) emanating from point sources within an operating area. The computer-implemented system may generally be employed against any form of WMN interference in which network performance is a function of the distance between interference sources and WMN Access Points (APs), and provides AP locations that minimize the disruption to client coverage caused by jammers, subject to constraints on network service and considering the effects of radio propagation over terrain. The computer-implemented system utilizes a process which considers network design in the presence of a simulated intelligent adversary capable of observing the WMN and placing jammers to maximally disrupt coverage.

[0030] The computer implemented system comprises a computer-based apparatus which provides AP locations based on inputs including selected inherent technical characteristics of APs and jammers within the WMN, the characteristics of the geographic area within which the WMN will operate, and others. The computer-based apparatus acts to analyze successive AP locations λ and jammer locations χ placed within the operating area by formulating an objective function having the general form Z(λ,χ)=Z_coverage(λ,χ)−w Z_flow(λ,χ), where Z_coverage(λ,χ) reflects resulting coverage shortfall within the geographic area for a given λ and a given χ, Z_flow(λ,χ) reflects and traffic flows within the geographic area for the given λ and the given χ, and w is a scalar reflecting the relative weight of the two terms. Details and quantification of the objective function Z(λ,χ) are further discussed below. The computer-based apparatus provides an optimized set of AP locations λ by initially selecting a set of AP locations λ, where individual λ_i in the set may be any location within the operating area, and may be selected using any methodology. Having defined a set of AP locations λ, the computer-based apparatus evaluates the objective function over multiple iterations in order to locate a set of jammer locations χ within the operating area which most disrupts the WMN established by the set of AP locations λ, based on resulting the value of the objective function Z(λ,χ). Once the most disruptive set of χ for the current set of λ is located, the computer-based apparatus selects a subsequent set of AP locations λ and conducts similar analysis of the objective function to locate a second set of jammer locations χ for maximal disruption of the new WMN established by the subsequent set of AP locations λ. In a particular embodiment, the computer-based apparatus selects the subsequent set of AP locations λ based on minimizing the impact of the most disruptive set of χ yet encountered in the process, and utilizing that λ configuration as the subsequent set of AP locations λ. The methodology continues in this fashion until stopping criterion are met. At the conclusion of the process, the computer-based apparatus provides a final set of AP locations λ which most effectively counters the most disruptive set of jammer locations χ located during the iterative process. The final set of AP locations λ thereby identifies the locations of APs to create a WMN that is the most robust to the worst possible jamming attack encountered. Such an attack could represent the actions of a rational human opponent, or the worst-case positioning of unintentional interference sources such as civilian radios, other RF devices, or high-voltage electrical devices.

[0031] In a particular embodiment, the computer-implemented system further comprises a two-dimensional display in data communication with the computer-based apparatus which provides graphic representation of the operating area and the resultant final set of AP locations λ. In another embodiment, the two-dimensional display provides discrete coverage regions within the operating area, and coverage shortfalls expected for the final set of AP locations λ given the maximally disruptive jammer placement.

[0032] Calculating the Value of a WMN Topology:

[0033] The computer-based apparatus employs a methodology for calculating the value of a WMN physical topology given fixed AP and jammer locations. See Nicholas et al., “Fast, Effective Transmitter Placement in Wireless Mesh Networks,” Military Operations Research, 17(4) (2012); see also U.S. Pat. No. 8,654,672 issued to Nicholas et al., issued Feb. 18, 2014. N is defined to be the set of all AP nodes, indexed by i=1, 2, . . . , n, where n=|N|. M is defined to be the set of all jammer nodes, indexed by k=1, 2, . . . , m, where m=|M|. Let λ=(λ₁, λ₂, . . . λ_n) represent the locations of the APs, and let χ=(χ₁, χ₂ . . . χ_m) represent the locations of the jamming sources. The operating area is the topographic area where an AP i or jamming source k may be physically located. A two-dimensional coordinate (x, y) is associated with each location χ_i and with each χ_k; these coordinates represent the northing and easting for AP node i and each jammer node k, respectively. The APs and jammers, once placed, generally remain stationary. The operating area is divided into a set of discrete coverage regions R, indexed by r=1, 2, . . . |R|. The formulation allows the use of any discretization scheme, however generally the implementation assumes rectangular regions arranged in a grid. Each coverage region rεR may have an associated elevation. In some embodiments, the elevation is assumed to be uniform throughout the region. This assumption is not true in practice, but is consistent with much of the available elevation data. See P. J. Nicholas and D. L. Alderson, “Designing interference-robust wireless mesh networks using a defender-attacker-defender model,” Naval Postgraduate School, Monterey, Calif., Tech. Rep. NPS-OR-15-002 (2015).

[0034] FIG. 1 illustrates an operating area 101 having discrete coverage regions such as 102, a wireless mesh network comprising AP locations such as AP location 103. FIG. 1 depicts a typical WMN in the absence of jamming. AP nodes are illustrated as white circles, and shaded grid elements represent locations that receive sufficient client coverage from the APs. The coverage obtained at each grid location depends on several factors including the local terrain, AP and client radio characteristics, and EMI. The dashed lines in FIG. 1 represent the backhaul network used to communicate between AP nodes. FIG. 2 illustrates the operating area as 201 with discrete coverage regions such as 202, AP locations such as AP location 203, and operating in the presence of a jammer 204. As illustrated, the placement of a jammer, denoted by a black circle, decreases client coverage and disrupts backhaul network connectivity. Each jammer node kεM may have two active transmitters: one interfering with nearby AP client coverage radios and the other interfering with nearby AP backhaul network radios. Generally, the APs are not subject to self-jamming or interference from other APs, and jammers emit signals consisting of random noise perfectly matched in frequency, phase, and polarization to AP transmissions (i.e., perfect physical-layer interference). See e.g. Pelechrinis et al., “Denial of service attacks in wireless networks: The case of jammers,” IEEE Communications Surveys & Tutorials, 13(2) (2011).

[0035] Each AP node iεN may serve as a source of network traffic. Sink or destination nodes dεN are identified as the sinks for all network traffic. Generally all APs serve as destination nodes, as is common in peer-to-peer networks. Typically, the physical location of one destination node, designated the headquarters (HQ) node, is known in advance and fixed. This node may serve as the network gateway and/or location of domain controllers and servers. This is consistent with reality, where network designers must place an AP at their headquarters, satellite gateway, or Internet point of presence (PoP).

[0036] Quantifying the value of a particular WMN topology in the presence of EMI is conducted by calculating two subproblems: the value of coverage provided to client devices Z_coverage, and the value of delivered backhaul network flow Z_flow. The value of the given WMN topology is given by the linear combination:
Z({circumflex over (λ)},{circumflex over (χ)})≡Z_coverage({circumflex over (λ)},{circumflex over (χ)})−w Z_flow({circumflex over (λ)},{circumflex over (χ)}),  (1)

[0037] where w is a positive scalar representing the relative importance of network flow, and the ^ symbol denotes that the locations λ and χ are fixed.

[0038] Given fixed AP locations {circumflex over (λ)} and fixed jammer locations {circumflex over (χ)}, the operator D aims to minimize client coverage shortfall and minimize negative network flow (i.e., maximize positive network flow) by choice of flow variables S, F, T, and P. For clarity, the variables being minimized by the operator D are explicitly stated in the operator's problem:

[0039] $\begin{array}{cc}{Z}_{\underset{\_}{D}}\left(\hat{\lambda },\hat{\chi }\right)=\underset{S,F,T,P}{\min }\left(Z_{\mathrm{coverage}}\left(\hat{\lambda },\hat{\chi }\right)-{\mathrm{wZ}}_{\mathrm{flow}}\left(\hat{\lambda },\hat{\chi },S,F,T,P\right)\right)& \left(2\right)\end{array}$

[0040] Placing Jammers:

[0041] The attacker A, given fixed AP node locations {circumflex over (λ)}, wishes to maximize disruption to the WMN by placing jammer nodes at locations:

[0042] $\begin{array}{cc}\mathrm{DA}\underset{\_}{D}\left(\hat{\lambda },·,·\right):Z_{A\underset{\_}{D}}\left(\hat{\lambda }\right)=\underset{\chi }{\max }\underset{S,F,T,P}{\min }\left(Z_{\mathrm{coverage}}\left(\hat{\lambda },\chi \right)-{\mathrm{wZ}}_{\mathrm{flow}}\left(\hat{\lambda },\chi ,S,F,T,P\right)\right)& \left(3\right)\end{array}$

[0043] The attacker's objective is to maximize coverage shortfall and minimize delivered backhaul network flow.

[0044] The network designer D, given fixed jammer node locations {circumflex over (χ)}, wishes to maximize WMN performance by placing AP nodes at locations λ:

[0045] $\begin{array}{cc}{Z}_{D\underset{\_}{D}}\left(\hat{\chi }\right):\underset{\lambda }{\min }\underset{S,F,T,P}{\min }\left(Z_{\mathrm{coverage}}\left(\lambda ,\hat{\chi }\right)-{\mathrm{wZ}}_{\mathrm{flow}}\left(\lambda ,\hat{\chi },S,F,T,P\right)\right)& \left(4\right)\end{array}$

[0046] The designer's objective is to minimize coverage shortfall and maximize delivered backhaul network flow.

[0047] The DAD Problem:

[0048] The computer-based apparatus nests the problems of the operator, attacker, and designer to utilize an overall SRRA+C DAD formulation:

[0049] $\begin{array}{cc}{Z}_{\mathrm{DA}\underset{\_}{D}}=\underset{\lambda }{\min }\underset{\chi }{\max }\underset{S,F,T,P}{\min }\left(Z_{\mathrm{coverage}}\left(\lambda ,\chi \right)-{\mathrm{wZ}}_{\mathrm{flow}}\left(\lambda ,\chi ,S,F,T,P\right)\right)& \left(5\right)\end{array}$

[0050] In the specific operation of the computer-based apparatus, the designer D first chooses AP locations λ, which the attacker A then aims to maximally disrupt by placing jammers at locations χ. The operator D calculates client coverage and determines how to route traffic given AP and jammer locations. The solution to the DAD problem indicates where the network designer should place APs to minimize the worst-case disruption possible by EMI. That is, when solved to optimality, the obtained AP network topology is completely immune to greater degradation, as the attacker cannot possibly do more damage.

[0051] Solving the DAD Problem:

[0052] To solve the SRRA+C DAD problem, the computer-based apparatus decomposes the DAD problem into a designer D master problem with separate attacker A subproblems. See e.g. Alderson, D. L., Brown, G. G., Carlyle, W. M., & Wood, R. K. (2011). Solving defender-attacker-defender models for infrastructure defense. In R. K. Wood & R. F. Dell (Eds.), Operations Research, Computing, and Homeland Defense (pp. 28-49). Hanover, Md.: INFORMS. In the master problem, the computer-based apparatus chooses AP locations λ_u for each iteration u=1, 2, . . . , max_master_iterations. For those given AP locations, the associated subproblem chooses jammer locations χ_v for each iteration v=1, 2, . . . , max_sub_iterations. Given AP locations λ_u and jammer locations χ_v, the overall objective value is then obtained via solving the operator's problem (2). After max_sub_iterations, the subproblem returns the jammer locations {circumflex over (χ)} yielding the best attack found (i.e., the highest overall objective value). The master problem continues searching for the best AP locations λ* to minimize the damage caused by the worst attack found until max_master_iterations.

[0053] The general process utilized by the computer-based apparatus is presented at FIG. 3. The process has available as input the operating region over the WMN is to be established, the number and operating characteristics of APs and jammers in the operating region, HQ node location, elevation and coverage requirements for each rεR, and desired stopping criterion and second stopping criteria. The process commences at BEGIN, and continues through block 1) to block 2) if the stopping criterion is satisfied. At block 2), the process selects an initial set of AP locations λ, and continues through block 3) to block 3a) if a second stopping criterion is satisfied. The process then begins the methodology for finding the most disruptive jammer locations χ for the current set of AP locations λ established at block 2). The process proceeds by selecting a set of jammers locations χ within the operating region at 3a), then quantifying the objective function parameters Z_coverage (λ,χ) and Z_flow (λ,χ) using the current set of AP locations λ and the current set of jammer locations χ at blocks 3b)(i) and 3b)(ii) respectively. At block 3b)(iii), the process quantifies the objective function Z(λ,χ) using the Z_coverage (λ,χ), the Z_flow (λ,χ), and the scalar w. At block 3c), the quantified Z(λ,χ) just determined at 3b)(iii) is compared against previously quantified objective function values for the current set of AP locations λ, and if the quantified Z(λ,χ) determined at 3b)(iii) is the most disruptive jammer configuration χ encountered thus far for the current set of AP locations λ, the quantified Z(λ,χ) is established as the incumbent χ solution. At block 3d), the process returns to block 3) and selects a second set of jammers locations χ at block 3a), and evaluates that second set against the current set of AP locations λ by performing blocks 3b)(i), 3b)(ii), 3b)(iii), and 3c) as before. This inner loop of blocks 3), 3a), 3b)(i), 3b)(ii), 3b)(iii), 3c) and 3d) is repeated for the current set of AP locations λ until the second stopping criterion is satisfied. In a particular embodiment, the second stopping criteria is a specified number of iterations of the operations of blocks 3), 3a), 3b)(i), 3b)(ii), 3b)(iii), 3c), and 3d). In another embodiment, the second stopping criteria is based on the difference between quantified objective functions in successive iterations. After conducting the operations of blocks 3), 3a), 3b)(i), 3b)(ii), 3b)(iii), 3c), and 3d) iteratively for the current set of AP locations λ, the process determines the most disruptive jammer locations χ for the current set of AP locations λ based on the associated quantified objective function.

[0054] At the conclusion of the inner loop of blocks 3), 3a), 3b)(i), 3b)(ii), 3b)(iii), 3c), and 3d), at block 4), the resulting incumbent solution for the current set of AP locations λ determined at block 3c) is compared against all previously determined incumbent solutions based on the respective quantified objective function values, and if the resulting incumbent solution is the best AP configuration encountered thus far for all sets of AP locations λ evaluated, the resulting incumbent solution is established as the overall incumbent solution.

[0055] At block 5) the process evaluates the stopping criteria, and if the stopping criteria is not satisfied, the process returns to block 1), selects a second set of AP locations λ at block 2), and subsequently conducts the inner loop of operations of blocks 3), 3a), 3b)(i), 3b)(ii), 3b)(iii), 3c), and 3d) in order to determine the maximally disruptive jammer locations χ for the next set of AP locations λ, before continuing to blocks 4) and 5). This outer loop of blocks commencing at 1) and concluding at 5) is repeated for each set of AP locations λ, until the stopping criterion is satisfied. In a particular embodiment, the stopping criteria is a specified number of iterations of the operations of blocks 1), 2), 4), and 5). In another embodiment, the stopping criteria is based on the difference between quantified objective functions in successive iterations.

[0056] Typically, at block 2), the process selects a subsequent set of AP locations λ by receiving the most disruptive jammer configuration χ which generated the overall incumbent solution, and determining the subsequent set of AP locations λ to be analyzed by finding the set of AP locations λ which is maximally effective in terms of the objective function against the current most disruptive jammer configuration χ, such that, given the most disruptive jammer configuration χ at a given point in the process, the subsequent set of AP locations λ selected at block 2) minimizes coverage shortfall and maximizes delivered backhaul network flow.

[0057] The attacker and designer's problems (like the SRRA+C problem) are nondifferentiable, nonconvex, nonlinear optimization problems. The difficulty of finding exact solutions to such problems increases the desirability of using heuristic computational techniques, such as genetic or simulated annealing algorithms, and sampling algorithms, such as mesh adaptive direct search (MADS). In a particular embodiment, the computer-based apparatus utilizes the DIviding RECTangles (DIRECT) algorithm to sample the SRRA+C solution space (i.e., the designer's problem with no jammers) to quickly find solutions. This same approach may be utilized for the attacker's problem Z_AD (given fixed AP nodes), and for the designer's problem Z_DD (given fixed jammers).

[0058] DIRECT is a sampling optimization algorithm based on Lipschitzian optimization The algorithm iteratively samples from the solution space, where the number of dimensions is 2m (attacker's problem) or 2 (n−1) (designer's problem), the length of each dimension is proportional to the operating area length or width, and a single point in the solution space represents the locations of all the nodes being placed (whether AP locations λ in the designer's problem, or jammer locations χ in the attacker's problem). The algorithm progressively samples from and divides the space into smaller hyper-rectangles. At each step, it chooses to explore a particular sub-hyper-rectangle based on both the solution value of the center point and the total volume of the given shape, where larger volumes are more desirable because they indicate greater unexplored territory and hence greater potential for an improved incumbent solution. The DIRECT algorithm is continuous, i.e., it can place APs or jammers at any location within the user-specified operating area. The DIRECT algorithm is guaranteed to eventually converge to the optimum solution, as it will eventually sample within an arbitrary distance of any point in the solution space. See e.g. Jones et al., “Lipschitzian optimization without the Lipschitz constant,” Journal of Optimization Theory and Applications, 79(1), (1993). For example, the DIRECT algorithm running on a laptop computer quickly finds good solutions to the attacker and designer's problems for networks consisting of up to at least 10 APs where the operating area is discretized into r=6,000 regions.

[0059] In an embodiment, the computer-based apparatus utilizes the following pseudo-code for the nested DIRECT algorithm:

[0060] Algorithm DIRECT for SRRA+C DAD

[0061] Input: Full SRRA problem data (number and operating characteristics of APs and jammers, HQ node location, and elevation and coverage requirements for each rεR and desired number of iterations max_master_iterations and max_sub_iterations.

[0062] Output: Best estimate of optimal AP locations λ*=(λ*₁, λ*₂, . . . , λ*_n) and χ*=(χ*₁, χ*₂, . . . , χ*_m), and operator solution Z_D(λ*,χ*).

[0063]

	begin
	Store map data
	Initialize u ← 1
	Master Problem (Designer)
	while (u < max_master_iterations) do
	Calculate AP locations λu using DIRECT
	Initialize v ← 1
	Subproblem (Attacker)
	while (v < max_sub_iterations) do
	Calculate EMI locations χv using DIRECT
	Solve operator's problem for ZD for λu and χv
	if ZD (λu, χv) > ZD (λu, {circumflex over (χ)} ) /* If this is the best attack yet, store
	as incumbent */
	{circumflex over (χ)} ← χk
	ZD (λu, {circumflex over (χ)}) ← ZD (λu, χv)
	endif;
	v ← v + 1
	end;
	if ZD (λu, {circumflex over (χ)}) < ZD (λ*, χ*) /* If this is the best design yet, store
	as incumbent */
	λ* ← λu
	χ* ← {circumflex over (χ)}
	ZD (λ*, χ*) ← ZD (λu, {circumflex over (χ)} )
	endif;
	u ← u + 1
	end;
	Return best AP locations λ*, EMI locations χ* , and operator's
	solution
	ZD (λ*, χ*)
	end;

For given AP locations λ_u and given enough iterations, DIRECT will eventually find a solution within an arbitrary distance of the solution space point defining the optimal jamming attack.

[0064] Quantifying Particular WMN Topologies:

[0065] The computer-based apparatus quantifies the value of a particular WMN topology in the presence of EMI by calculating the value of coverage provided to client devices Z_coverage, and calculating the value of delivered backhaul network flow Z_flow:

[0066] Calculating Client Coverage:

[0067] The client coverage provided by a WMN topology is a function of its AP and jammer locations. Given these locations, the computer-based apparatus quantifies the value of client coverage by first calculating the received signal strength (RSS) in Decibel-milliwatts (dBm from each discrete coverage region rεR from each AP node i or jammer node k (and the reverse path) using the standard link budget formula:
RSS=power_tx+g_tx−l_tx−l_path−l_misc+g_rs−l_rx,
where power_tx is transmission power in dBm, g_tx and g_rx are, respectively, the gains of the transmitter and receiver in dBi, l_tx and l_rx are, respectively, the losses (i.e., from cables, connectors, etc.) of the transmitter and receiver in dB, l_path is the total path loss in Decibels (dB), and l_misc is the miscellaneous loss (such as fade margin) in dB. See e.g., Olexa, R., Implementing 802.11, 802.16, and 802.20 wireless networks: Planning, troubleshooting and operations (2005). Using the standard link budget formula, the computer-based apparatus defines ρ_ir (ρ_ri) as the received signal strength from (to) a transmitting AP node i to (from) coverage region r, and η_kr (η_ri) as the received signal strength from a transmitting jammer node k to coverage region r (AP i). All of the terms in the standard link budget formula are input data, determined by the equipment technical characteristics, except for the total path loss l_path, which depends on the position of the transmitting device (a client device, AP node λ_i, or jammer node χ_k)

[0068] Various methods may be utilized for computing l_path, such as a simple inverse-square calculation, the Irregular Terrain Model (ITM), or Hata-COST 231 (COST, 1999). See Longley, A. G., & Rice, P. L. (1968). Prediction of tropospheric radio transmission loss over irregular terrain. A computer method-1968 (1968); and see COST (European Cooperation in the Field of Scientific and Technical Research) Digital mobile radio towards future generation systems: COST 231 (1999). In an embodiment, the computer-based apparatus utilizes the Terrain Integrated Rough Earth Model (TIREM). This model computes path loss by sampling terrain elevation at fixed points between transmitter and receiver. It considers the effects of free space loss, diffraction, and atmospheric absorption and reflection, but does not consider foliage, buildings, or other nonterrain obstructions. While TIREM is computationally more expensive than simpler models, it provides fairly accurate results.

[0069] In an embodiment, to quantify the value of client coverage, the computer-based apparatus calculates in dBm the total interference received at region rεR and AP node iεN using:

[0070] $\begin{array}{cc}{\mathrm{Interference}}_r\equiv 10{\log }_{10}\left(1000\sum _{k\in M}\frac{10\frac{{\eta }_{\mathrm{kr}}}{10}}{1000}\right)=10{\log }_{10}\sum _{k\in M}10\frac{{\eta }_{\mathrm{kr}}}{10}& \forall r\in R\end{array}$ $\begin{array}{cc}{\mathrm{Interference}}_i\equiv 10{\log }_{10}\left(1000\sum _{k\in M}\frac{10\frac{{\eta }_{\mathrm{ki}}}{10}}{1000}\right)=10{\log }_{10}\sum _{k\in M}10\frac{{\eta }_{\mathrm{ki}}}{10}& \forall i\in N\end{array}$

[0071] The computer-based apparatus calculates in dB the signal-to-interference ratio (SIR) σ between each region rεR and AP node iεN. SIR is calculated in both directions (i to r and r to i), as two-way communication is necessary for a client device to successfully exchange traffic with an AP, and terrain, obstructions, and the effects of EMI may cause these quantities to be very different.
(Signal to Interference Ratio)_ir=σ_ir≡ρ_ir−interference_r∀iεN,∀rεR
(Signal to Interference Ratio)_ri=σ_ri≡ρ_ri−interference_i∀rεR,∀iεN

[0072] The computer-based apparatus defines or receives as input a minimum allowable SIR or sensitivity threshold τ in dB for each region rεR and AP node iεN. Higher τ values indicate a higher priority or a requirement for a higher quality signal and thus greater data transfer rates. In a typical embodiment, the computer-based apparatus uses a value of 10 dB. A positive difference of τ and σ indicates insufficient signal quality. The computer-based apparatus calculates this client coverage shortfall between region r and AP node i and penalizes the weakest component of the bidirectional link between the AP and region (i.e., the link with the greatest coverage shortfall):

[0073] ${\left(\mathrm{Coverage}\mathrm{Shortfall}\right)}_{\mathrm{ir}}\equiv \underset{i\in N,r\in R}{\max }\left({\left({\tau }_r-{\sigma }_{\mathrm{ir}}\right)}_{+},{\left({\tau }_i-{\sigma }_{\mathrm{ri}}\right)}_{+}\right)$
where ( )+ denotes the projection onto the nonnegative real line. Because a positive difference represents inadequate client coverage, the computer-based apparatus acts to minimize this quantity. In an embodiment, it considers only the minimum coverage shortfall from each AP node iεN and assumes each client device will connect only to that AP with the strongest available σ_ir. The computer-based apparatus sums over all rεR to calculate total coverage shortfall, denoted Z_coverage:

[0074] $z_{\mathrm{coverage}}\left(\lambda ,\chi \right)=\left(\mathrm{Total}\mathrm{Coverage}\mathrm{Shortfall}\right)\equiv \sum _{r\in R}\underset{i\in N}{\min }\left\{\max \left({\left({\tau }_r-{\sigma }_{\mathrm{ir}}\right)}_{+},{\left({\tau }_i-{\sigma }_{\mathrm{ri}}\right)}_{+}\right)\right\}$

[0075] The total coverage shortfall is a function of AP node locations λ and EMI node locations χ. By allowing only positive terms, this disallows the benefit of transmitting received power to any given coverage region.

[0076] Calculating Network Flow:

[0077] To assess the value of network flow, arc capacities for the arc paths between each node are calculated. In an embodiment, the computer-based apparatus utilizes the Shannon capacity formula, which establishes a theoretical upper bound on transmission capacity in bits per second (bps), and the capacity from AP node i to j in bps is:

[0078] ${\left(\mathrm{Capacity}\right)}_{\mathrm{ij}}=\mathrm{bandwidth}{\log }_2\left(1+\frac{{\mathrm{gain}}_{\mathrm{ij}}}{{\mathrm{interference}}_j{\mathrm{loss}}_{\mathrm{ij}}}{P}_{\mathrm{ij}}\right)\forall \left(i,j\right)\in A$
where bandwidth is channel bandwidth in Hertz and gain_ij is the sum of the antilog gain terms (g_tx and g_rx). Loss_ij is the sum of the antilog loss terms (l_tx, l_rx, l_path, and l_misc) from AP node i to j. Note interference_j is converted to watts with simplified notation for clarity. These input data are calculated by the known locations of AP node locations λ and jammer node locations χ. In this embodiment, each AP has limited total transmission power denoted p_i (in watts), and the computer-based apparatus defines P_ij to be the fraction of p_i used to transmit from i to j. Thus, each AP is additionally constrained by

[0079] $\sum _{j:\left(i,j\right)\in A}{P}_{\mathrm{ij}}\le p_i$

[0080] Here, P_ij is a decision variable representing the AP-to-AP transmission power from node I to node j, whereas the transmission powers for AP-to-client, jammer-to-client, and jammer-to-AP power_tx is a (constant) input parameter.

[0081] The computer-based apparatus measures each individual traffic flow in bps and quantifies the value of total network flow according to a log-utility function that places a zero value on unit flow, positive values on flows greater than one, and negative values on flows less than one. Note that a zero flow has an infinite penalty, and therefore there is strong incentive to ensure that each source-destination pair receives some flow. Defining S_i^d to be the total flow originating at node i and destined for node d:

[0082] $\left(\mathrm{Utility}\mathrm{of}\mathrm{Total}\mathrm{Network}\mathrm{Flow}\right)\equiv \sum _d\sum _{i\ne d}{\log }_2\left(S_i^d\right)$

[0083] Collectively, the computer-based apparatus calculates the value of network flow, denoted Z_flow. In an embodiment, the computer-based apparatus utilizes a Simultaneous Routing and Resource Allocation (SRRA) technique to calculate Z_flow using the relationships and constraints:

SRRA Formulation

Index Use

• • [0084] iεN AP node (alias j)
  • [0085] kεM jammer node
  • [0086] (i,j)εA directed arc (link)
  • [0087] dεD⊂N destination node
    Input Data
  • [0088] {circumflex over (λ)}_i locations of AP nodes, {circumflex over (λ)}={{circumflex over (λ)}_i, iεN} [none]
  • [0089] {circumflex over (χ)}_k locations of jammer nodes, {circumflex over (λ)}={{circumflex over (χ)}_k, kεM} [none]
  • [0090] p_i maximum total transmission power per AP node, iεN [watts]
  • [0091] bandwidth channel bandwidth [hertz]
    Calculated Data
  • [0092] gain_ij product of analog gain terms from iεN to jεN [none]
  • [0093] loss_ij product of analog gain terms from iεN to jεN [none]
  • [0094] interference_j Total received EMI and background noise power
    • [0095] at jεN [watts]
      Decision Variables
  • [0096] S_i^d total flow of traffic from origin iεN to destination dεD [bps]
  • [0097] F_ij^d traffic flow along arc (i, j)εA to destination dεD [bps]
  • [0098] T_ij total flow along arc (i, j)εA [bps]
  • [0099] P_ij total transmission power along arc (i, j)εA [watts]
    Formulation

[0100] $\begin{array}{cc}{Z}_{\mathrm{flow}}\left(\hat{\lambda },\hat{\chi }\right)=\underset{S,F,T,P}{\max }\sum _d\sum _{i\ne d}{\log }_2\left(S_i^d\right)& \left(S0\right)\\ \begin{array}{cc}s.t.\sum _{i:\left(j,i\right)\in A}{F}_{\mathrm{ji}}^d-\sum _{i:\left(i,j\right)\in A}{F}_{\mathrm{ij}}^d=S_j^d& \forall j\in N,\forall d\in D\end{array}& \left(S1\right)\\ \begin{array}{cc}{T}_{\mathrm{ij}}=\sum _d{F}_{\mathrm{ij}}^d& \forall \left(i,j\right)\in A\end{array}& \left(S2\right)\\ \begin{array}{cc}{T}_{\mathrm{ij}}-\mathrm{bandwidth}{\log }_2\left(1+\frac{{\mathrm{gain}}_{\mathrm{ij}}}{{\mathrm{interference}}_j{\mathrm{loss}}_{\mathrm{ij}}}{P}_{\mathrm{ij}}\right)\le 0& \forall \left(i,j\right)\in A\end{array}& \left(S3\right)\\ \begin{array}{cc}\sum _{j:\left(i,j\right)\in A}{P}_{\mathrm{ij}}\le p_i& \forall i\in N\end{array}& \left(S4\right)\end{array}$
S_i^d≧0i≠d  (S5)
F_ij^d≧0∀(i,j)εA,∀dεD  (S6)
T_ij≧0∀(i,j)εA  (S7)
P_ij≧0∀(i,j)εA  (S8)

[0101] Given AP locations {circumflex over (λ)} and jammer locations {circumflex over (χ)}, this is a multicommodity network flow problem. The objective function (S0) maximizes the total utility of traffic flow between each source-destination pair. Constraints (S1) ensure balance of flow at each AP node. Constraints (S2) define the total flow along any arc as the sum of all traffic flows along that arc. Constraints (S3) ensure that total flow along any arc is less than or equal to the arc capacity. Constraints (S4) restrict total transmission power at each AP. Constraints (S5-S8) ensure nonnegativity.

[0102] As stated, the overall jammer-cognizant SRRA+C objective function is obtained using a linear combination of client coverage (calculated as client coverage shortfall) and network flow (calculated via the SRRA problem):
Z({circumflex over (λ)},{circumflex over (χ)})≡Z_coverage({circumflex over (λ)},{circumflex over (χ)})−wZ_flow({circumflex over (λ)},{circumflex over (χ)}).

[0103] Here, w is a positive scalar representing the relative importance of network flow. Larger values of w indicate network flow is of greater importance and, in general, increase network flow by valuing more compact network topologies.

[0104] Exemplary Results:

[0105] The attacker's problem is illustrated by finding the optimal single jammer attack against a network of two fixed APs. Consider a one square kilometer operating area (gridded into 100×100 regions) with flat terrain with an AP placed near the top and bottom of the region. This is illustrated at FIG. 4 with no jammer present, where the two APs (depicted as open circles) provide the client coverage shown in white and deliver network traffic to each other at a maximum rate of 419 kilobits per second (kbps). The computer-based apparatus generally penalizes solutions based on the degree of insufficient client coverage, depicted in FIG. 5 as darker areas. In a single-channel jamming attack, the optimal attack is to simply place the single jammer directly on top of either AP, depicted as an “X” on the bottom AP at FIG. 5. This direct-AP attack eliminates the client coverage by the bottom AP, and reduces network traffic flow between the APs to essentially zero. In barrage jamming, the optimal attack is to place the jammer in between the two APs in a between-AP attack, illustrated at FIG. 6. In such a location, the barrage jammer is able to significantly reduce the client coverage provided by both APs, and reduce the delivered network traffic flow to both devices to essentially zero. Because the computer-based apparatus penalizes the degree of coverage shortfall, a jammer in between each AP maximizes this penalty by making the centerline region receive worse client coverage than would be provided if the jammer was placed directly on top of either AP. Likewise, network flow is maximally disrupted in a barrage jamming attack by placing the jammer between each AP because this reduces delivered flow to both APs.

[0106] FIG. 7 shows the optimal y location(s) for one barrage jammer placed between the two APs at locations (50, 20) and (50, 80) at FIGS. 4-6 to minimize client coverage, as a function of jammer transmission power relative to client device power. The solid line 705 indicates client coverage shortfall. FIG. 8 presents the same analysis for a barrage jammer to minimize backhaul network flow, represented by solid line 806. Equivalent solutions in each figure are shown by two points at a given power ratio. When jamming power relative to AP and client transmission power is low enough, the optimal barrage jamming strategy may become a direct-AP attack. The sudden jump in FIG. 7 is an artifact of continuous client service—which, on perfectly flat terrain, is essentially a circle around each AP—being discretized into the gridded operating area. As the relative transmission power of an AP changes, the “circle” of client coverage around each AP will change in a discontinuous fashion, occasionally jumping in value. In this case, it occurs when the area receiving adequate client service no longer overlaps the upper and lower boundaries of the operating area. The calculation of network flow (i.e., FIG. 8) is not affected by the discretization of the operating area, so these jumps are not present. FIGS. 7 and 8 illustrate that an optimal jamming strategy (i.e., direct-AP or between-AP attack) for attacking client coverage and network flow occurs at different power ratio levels. That is, the best location to place a jammer to maximize client coverage shortfall may not always be the best place to minimize network flow. The best overall location will be a function of w, the positive scalar indicating the value of network flow in the SRRA+C objective function (6).

[0107] In the designer's problem, the designer is faced with of finding optimal locations for APs with jammers at fixed locations. While attempting to minimize the effects of jamming, the designer must consider the competing objectives of client coverage and network flow: network flow can be maximized by simply placing the APs as far as possible from the jammers (i.e., on the farthest border of the operating area), but such placement will likely provide very little client coverage. The optimal solution to the designer's problem balances these competing concerns. For example, with a single-channel jammer, the best strategy may be to place the jammed AP far from the jammer and place the unjammed AP near the jammer, maximizing the utility of providing client coverage in the unjammed area. With a barrage jammer, the best strategy may be to move the APs away from the jammer to a point that maximizes client coverage while balancing the competing requirement of network flow. In this scenario, these locations are in the corners of the operating area.

[0108] For the full DAD problem, the computer-based apparatus determines the optimal strategy for minimizing the damage caused by the optimal jamming attack. Many variables may affect the optimal solution to the operator's, attacker's, and designer's problems. In these examples, the AP and jammer radio characteristics are modeled on the Cisco Aironet 1550 WMN AP, and client devices are modeled on a generic internal 802.11n wireless interface card. Results for two exemplary situations are presented at FIGS. 9-14 in a tri-panel format, where the left panel (FIGS. 9 and 12) depicts the best unjammed solution found (i.e., the designer's problem without jammers); the middle panel (FIGS. 10 and 13) depicts the best undefended solution found when the attacker now jams the unjammed solution (i.e., the solution to the attacker's problem (3)); and the right panel (FIGS. 11 and 14) depicts the best defended solution found when the designer chooses that network topology which minimizes the effects of the best jamming attack found (i.e., the DAD solution (5)). In these examples, the computer-based apparatus utilizes the nested DIRECT optimization, which samples many different jamming attacks for many different network designs. For each solution panel, the thickness of the lines between APs is directly proportional to delivered network flow. The computer-based apparatus runs DIRECT until the solution objective values have not changed significantly for more than 10 function evaluations, or 20 master and subproblem iterations of DIRECT (whichever occurs first).

[0109] FIGS. 9, 10, and 11 illustrate the operations of the computer-based apparatus with a network of four APs being attacked by one barrage jammer, with the fixed HQ node located in the lower left of the operating area. At FIGS. 9, 10, and 11, APs are shown as circles. At FIG. 9, the designer places four APs to cover most of the operating area. Given this fixed design, at FIG. 10, the attacker places a barrage jammer 1007 in the middle of the operating area, greatly increasing client coverage shortfall and decreasing total delivered network flow. Finally, at FIG. 11, the designer chooses a more dispersed network topology that minimizes the damage of the worst attack (generated by barrage jammer 1107), generating reduced client coverage shortfall.

[0110] FIGS. 12, 13, and 14 illustrate a similar progression of the computer-based apparatus with a network of four APs being attacked by two barrage jammers. At FIG. 12, the designer has placed four APs to cover most of the operating area. At FIG. 13, the attacker now places barrage jammers 1308 and 1309 each near an AP, rather than directly between the APs. In the DAD solution at FIG. 14, the designer again chooses an AP topology that minimizes the effectiveness of a between-AP attack. The DAD solution decreases coverage shortfall and increases network flow over the undefended solution.

[0111] Thus, provided here is a computer-implemented system for establishing a wireless mesh network resistant to degradation induced by deliberate jamming or other electromagnetic interference emanating from point sources within an operating area. The computer-implemented system provides WMN AP locations that minimize disruptions to client coverage caused by jammers, subject to constraints on network service. The computer-implemented system considers jammers placed by an intelligent adversary and identifies the AP locations λ through quantification of an objective function of the general form Z(λ,χ)=Z_coverage(λ,χ)−w Z_flow(λ,χ), where Z_coverage(λ,χ) reflects resulting coverage shortfall, Z_flow(λ,χ) reflects traffic flow within the WMN, and w is a scalar reflecting the relative weight of the two terms. The final set of AP locations λ identifies the locations of APs to create a WMN that is the most robust to potential degradation induced by deliberate jamming or other electromagnetic interference (EMI) emanating from point sources within an operating area.

[0112] It is to be understood that the above-described arrangements are only illustrative of the application of the principles of the present invention and it is not intended to be exhaustive or limit the invention to the precise form disclosed. Numerous modifications and alternative arrangements may be devised by those skilled in the art in light of the above teachings without departing from the spirit and scope of the present invention. It is intended that the scope of the invention be defined by the claims appended hereto.

[0113] In addition, the previously described versions of the present invention have many advantages, including but not limited to those described above. However, the invention does not require that all advantages and aspects be incorporated into every embodiment of the present invention.

[0114] All publications and patent documents cited in this application are incorporated by reference in their entirety for all purposes to the same extent as if each individual publication or patent document were so individually denoted.