Distributed topology learning method and apparatus for wireless networks
AssigneeInnovative Technology Licensing, LLC
InventorsLoren P. Clare, Jonathan R. Agre
Life of this patent
Estimating the term…
Abstract
A wireless network of communicating devices, preferably including sensors, uses a distributed method of topology learning to organize multiple hop, relayed communication among the devices and with users. The method of topology learning identifies interference neighbors and communication neighbors for each device, preferably using ranging between devices and distributed calculation to limit the number of devices involved in each step of the topology learning method, thereby conserving energy and bandwidth. The identification of interference neighbors and communication neighbors for each device in the network facilitates scheduling of communications in any of a variety of multiple access protocols.
Claims19
A method of determining the communication topology of a wireless network consisting of a plurality of distributed nodes, at least one but less than all of which comprise a network of member nodes, each of said nodes having a known maximum communication range g and a known maximum interference range b, said interference range being the range from a transmitting node within which said transmitting node's transmissions may interfere with a receiving node's reception, comprising the steps of:
- selecting an inviting member node, one of said member nodes,
- transmitting to a new non-member node, by wireless transmission from said inviting member node, an invitation to join the network of member nodes,
- identifying a communicating set of member nodes within communication range g of said new node, in response to said invitation, and
- identifying an interfering set of member nodes within the interference range b of said new node, in response to said invitation.
A method of determining the communication topology of a wireless network consisting of a plurality of distributed nodes, at least one but less than all of which comprise a network of member nodes whose positions are known, each of said nodes having a known communication range g, and a known interference range b, said interference range being the range from a transmitting node within which said transmitting node's transmissions may interfere with a receiving node's reception, comprising the steps of:
- selecting an inviting member node from said member nodes,
- selecting a potential interfering set of member nodes, defined as those member nodes within g+b of said inviting member node,
- scheduling a transmission from said inviting node such that said transmission will not interfere with other scheduled transmissions among member nodes in said potential interfering set of member nodes,
- transmitting from said inviting member node an invitation for said new node to join a network,
- determining the approximate distance d from said inviting member node to said new node,
- selecting a potential communicating set of member nodes, defined as those member nodes within range g+d of said inviting member node,
- scheduling a first schedule of transmissions from said new node to each node in said potential communicating set of member nodes,
- executing said first schedule of transmissions from said new node to each node in said potential communicating set of member nodes,
- scheduling a second schedule of transmission from each member node in the potential communicating set,
- executing a second schedule of transmissions from each node in said potentially communicating set of member nodes,
- identifying the transmissions accurately received from said first and second schedules of transmissions,
- selecting, based on said transmissions received, a set of communicating member nodes, defined as those member nodes actually able to accurately transmit to and receive from said new node,
- locating said new node relative to a member node having known location,
- selecting, based on the location of said new node and its known interference range, a set of member nodes actually in interference range of said new node, and
- distributing among member nodes the information identifying said new node, said set of member nodes actually in communicating range of said new node, and said set of member nodes actually in interference range of said new node.
A network having a plurality of nodes, suitable for placement with at least one node having an unknown location and at least one node having a known location, each node comprising:
- a sensor for sensing physical phenomena,
- a programmable computer, monitoring said sensor, and
- a wireless transceiver, controlled by said programmable computer, said transceiver having a known communication range and a known interference range within which its transmissions may interfere with receptions by another similar transceiver,
- said programmable computer being programmed to cause said wireless transceiver to transmit an invitation for another node to join the network,
- said node being capable of estimating its distance to another node by internode transmissions,
- said programmable computer being programmed:
- (1) to calculate, from an estimated distance between a node of known location and a node of unknown location, an estimated position of said node of unknown location,
- (2) to identify a set of communicating nodes in communication range of said node of unknown location, based on said estimated position, and a set of interfering nodes in interference range of a new node,
- (3) to store information identifying both said sets of nodes, and
- (4) to cause said wireless transceiver to distribute said identifying information.
Dependencies are inferred from the claim text.