node- arbitrated media access control protocol for ad hoc broadcast networks carrying ephemeral information
First Claim
1. A method employed in a plurality of nodes that operate in a shared open communication medium and have access to a single source of time information of permitting a node of the plurality to broadcast a payload message in the medium and the method comprising the steps performed in each node of the plurality which has a payload message to broadcast in the medium of:
- receiving node priority messages in the node which are broadcast by the nodes of the plurality which have a payload message to broadcast during a first interval of time that the node determines using the single source of time information;
determining from the node priority messages whether the node has priority over other nodes with payload messages with regard to broadcasting the node'"'"'s payload message in the medium; and
if the node has priority, broadcasting the node'"'"'s payload message in the medium during a second interval of time that the node determines using the single source of time information.
1 Assignment
0 Petitions
Accused Products
Abstract
Techniques for organizing nodes of an ad hoc broadcast network into sets and employing the sets to arbitrate access by the nodes to a shared communications medium. Each node has a copy of a signal library and the node indicates its membership in the set by associating itself with a signal in the library. In one application, the signals are ranked, the set is a queue, and the node'"'"'s position in the queue is indicated by the rank of the signal associated with the node. Each node has rules for selecting the next signal. The hidden terminal problem is solved by having each node broadcast its tone and all of the other tones it has heard. The techniques are particularly useful for the broadcast of ephemeral information by the nodes.
-
Citations
5 Claims
-
1. A method employed in a plurality of nodes that operate in a shared open communication medium and have access to a single source of time information of permitting a node of the plurality to broadcast a payload message in the medium and the method comprising the steps performed in each node of the plurality which has a payload message to broadcast in the medium of:
-
receiving node priority messages in the node which are broadcast by the nodes of the plurality which have a payload message to broadcast during a first interval of time that the node determines using the single source of time information; determining from the node priority messages whether the node has priority over other nodes with payload messages with regard to broadcasting the node'"'"'s payload message in the medium; and if the node has priority, broadcasting the node'"'"'s payload message in the medium during a second interval of time that the node determines using the single source of time information.
-
-
2. A method of joining a set of nodes in an ad hoc network of nodes, each node in the network operating in an open communications medium which is shared with the other nodes and having access to a single source of time information, the method comprising the steps performed in a joining node which has access to the single source of time information of:
-
in a first interval of time which the joining node determines using the single source of time information, receiving a set of signals belonging to a library thereof, the set of signals being broadcast by the nodes in the set and the library of signals being known to the joining node; selecting a signal from the library which is not in the broadcast set; in a second interval of time which the joining node determines using the single source of time information, broadcasting the selected signal and detecting signals from the library, the detected signals being broadcast individually by the nodes of the network; and in a next first interval of time, broadcasting the selected signal and the detected signals.
-
-
3. A method of arbitrating access among a set of nodes to a communications medium which is shared among the nodes, each node having access to a single source of time information and being associated with a signal belonging to a library thereof, the signals being ranked in the library and the library being known to each node, the method comprising the steps performed in a node of the set of:
-
in a first interval of time which the node of the set determines using the single source of time information, receiving a set of signals belonging to a library thereof, the signals in the set being associated with the nodes of the set and the set of signals being broadcast by the nodes in the set t; determining the rank of the signal associated with the node of the set in the broadcast set of signals; if the associated signal has the highest rank, accessing the shared communications medium during a second interval of time which node of the set determines using the single source of time information; and otherwise not accessing the shared communications medium during the second interval of time.
-
-
4. A frame in a communications medium which is employed by an ad-hoc broadcast network of nodes, the nodes sharing the communications medium and having access to a single source of time information and the frame being employed by the nodes to arbitrate for access by a node to the communications medium to broadcast a payload message, the frame comprising:
intervals of time which each node determines using the single source of time information, the intervals of time including a first interval of time during which each node of the network broadcasts a signal from a library thereof, the signals being ranked in the library and the signal being broadcast by a given node being associated with the given node and during which each node receives signals broadcast by other nodes of the network; a second interval of time during which each node broadcasts an indication of all of the signals received in the node, receives indications of the signals received in the other nodes, and determines a priority relationship between the signal associated with the node and the signals indicated by the received indications; and a third interval of time during which the node whose associated signal has the highest rank in the signals indicated by the received indications broadcasts the payload message.
-
5. A method of forming a queue of nodes belonging to an ad-hoc broadcast network, the queue having a head node which performs an action and each node having a copy of a library of ranked signals, all of the nodes having access to a single source of time information, and nodes in the queue being associated with signals in the library, the method comprising steps performed in each node of the queue during repeated first intervals of time, the repeated first interval of time being determined by each node using the single source of time information and the steps comprising:
-
in a node which is in the queue, broadcasting the signals associated with the nodes in the queue during each repeated first interval of time; in a node which is joining the queue, listening to the signals broadcast in a current first interval of time to determine a signal which is not currently associated with a node in the queue and associating that signal with the joining node; in a node which is in the queue, listening to the signals broadcast in the current repeated first interval of time to determine whether the node is the head node, the head node being the node whose associated signal has the highest rank in the broadcast signals; if the node is the head node, performing the action in a repeated second interval of time which each node determines using the single source of time information and ending the association between the node and the highest ranked signal; and otherwise associating the node with a higher ranked signal in the library before broadcasting the signals associated with the nodes during the next repeated first interval of time.
-
Specification