Method for optimal transmitter placement in wireless mesh networks

• US 8,654,672 B1
• Filed: 05/03/2010
• Issued: 02/18/2014
• Est. Priority Date: 05/01/2009
• Status: Expired due to Fees

• Current Assignee: The Government Of The United States Of America, As Represented By The Secretary Of The Navy
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Nicholas, Paul J., Alderson, David L. Jr.
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): Sweet, Lonnie
• Application Number:
  US12/772,434
• Time in Patent Office: 1,387 Days
• US Class Current: 370/254
• CPC Class Codes: H04L 41/04 Network management architectures or arrangements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/34 Signalling channels for network management communication
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04Q 1/20 Testing circuits or apparatus; Circuits or apparatus for detecting, indicating, or signalling faults or troubles
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A process for forming a wireless mesh network (WMN) in which client coverage is calculated using a point-to-point propagation loss model and optimal routing and power allocation is determined to quantify the value of network flow. In one embodiment, the process calculates loss based on access point locations, operating characteristics and terrain and environment information. In one embodiment, the network flow and coverage subproblem values are combined via a penalty function. The process creates WMN topologies that maximize client coverage area by choice of access point locations, subject to constraints on network flow and power allocation, number and technical capabilities of access points, background and environmental noise, and radio propagation over terrain.

Claims

1. A computer-implemented method for forming a wireless mesh network that includes a plurality of access points arranged to provide radio communications with a plurality of client devices comprising:

a computer-based apparatus including non-transitory computer readable code for a method for forming a wireless mesh network, when implemented by the computer-based apparatus, the method comprising;

(a) receiving inputs of criteria for a minimum client coverage threshold, a network signal flow weight, the network signal flow weight being a positive scalar representing the relative weight placed on network signal flow, and a stopping criterion, for the wireless mesh network;

(b) receiving an input of an operating region as a two-dimensional topographic area where access points may be placed, the operating region containing an infinite number of potential access point locations;

(c) receiving an input of one or more coverage regions where client coverage is desired, wherein the one or more coverage regions and the operating region need not be the same;

(d) receiving an input of a minimum coverage threshold for each coverage region for a client to connect to an access point in the operating region;

(e) determining an initial partition of the operating region and an associated arrangement of access points in the operating region based on the dimensions of the operating region, the associated arrangement of access points being selected from the potential access point locations;

(f) calculating a client coverage value at each coverage region;

(g) comparing the calculated client coverage value to the minimum client coverage threshold for each coverage region to determine a calculated coverage shortfall value;

(h) determining an optimal signal routing and an optimal power allocation for each access point to determine a calculated network signal flow value;

(i) inputting the calculated coverage shortfall value for each coverage region and the calculated network signal flow value into a weighted multiple-objective optimization function which utilizes the network signal flow weight, to determine an overall objective value associated with that arrangement of access points, and storing the overall objective value; and

(j) determining if the stopping criterion is met, and wherein if the stopping criterion is not met, selecting a next partition of the operating region and an associated arrangement of access points based on the overall objective values of all previously determined arrangements of access points and repeating operations (f)-(j); and

wherein if the stopping criterion is met, selecting the arrangement of access points associated with the minimal objective value of the multiple-objective optimization function of those previously stored, and providing as output the associated arrangement of access points as a wireless mesh network design.

2. The computer-implemented method of claim 1 wherein the stopping criterion is a selected number of iterations of operations (f)-(j).