Method and system for global topology discovery in multi-hop ad hoc networks
First Claim
Patent Images
1. A method of discovering global topology in a barrage relay network comprising:
- receiving, at a receiving node, a first message on a first logical channel from a first node;
updating, at the receiving node, a topology table with a first set of topology information contained in the first message;
receiving, at the receiving node, a second message on a second logical channel from a second node, the second logical channel being different from the first logical channel, the second message being periodically broadcast network wide by the second node, the second message comprising a unique identifier associated with a node in the barrage relay network and a request to transmit local topology information, the unique identifier identifying the node as a destination of the second message;
determining, at the receiving node, whether the unique identifier identifies the receiving node; and
when the unique identifier does not identify the receiving node;
receiving, at the receiving node, a third message comprising a second set of topology information on a third logical channel from a third node and updating the topology table with the second set of topology information contained in the third message, the third logical channel being different from the first logical channel and the second logical channel, the third message being a response to the request to transmit local topology information, and the third message being a spatially-pipelined broadcast through the barrage relay network;
when the unique identifier identifies the receiving node;
transmitting, from the receiving node, a fourth message comprising the topology table on the third logical channel, the fourth message being a response to the request to transmit local topology information, and the fourth message being another spatially-pipelined broadcast through the barrage relay network.
2 Assignments
0 Petitions
Accused Products
Abstract
Systems and methods are presented for topology discovery in a multi-hop ad hoc network. The method operates on two time and distance scales. Nodes periodically transmit messages to their immediate neighbors that enable the discovery of their two-hop network topologies (i.e., within two hops). Less frequently, nodes broadcast messages network-wide that enable the discovery of the global network topology at all nodes. In multi-hop ad hoc network architectures that are characterized by efficient broadcast protocols—e.g., Barrage Relay Networks—the proposed method provides a particularly efficacious means for global topology discovery.
16 Citations
18 Claims
-
1. A method of discovering global topology in a barrage relay network comprising:
-
receiving, at a receiving node, a first message on a first logical channel from a first node; updating, at the receiving node, a topology table with a first set of topology information contained in the first message; receiving, at the receiving node, a second message on a second logical channel from a second node, the second logical channel being different from the first logical channel, the second message being periodically broadcast network wide by the second node, the second message comprising a unique identifier associated with a node in the barrage relay network and a request to transmit local topology information, the unique identifier identifying the node as a destination of the second message; determining, at the receiving node, whether the unique identifier identifies the receiving node; and when the unique identifier does not identify the receiving node; receiving, at the receiving node, a third message comprising a second set of topology information on a third logical channel from a third node and updating the topology table with the second set of topology information contained in the third message, the third logical channel being different from the first logical channel and the second logical channel, the third message being a response to the request to transmit local topology information, and the third message being a spatially-pipelined broadcast through the barrage relay network; when the unique identifier identifies the receiving node; transmitting, from the receiving node, a fourth message comprising the topology table on the third logical channel, the fourth message being a response to the request to transmit local topology information, and the fourth message being another spatially-pipelined broadcast through the barrage relay network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A non-transitory tangible computer-readable medium embodying program code executable by a computing system, the program code comprising:
-
program code for receiving, at a receiving node in a barrage relay network, a first message on a first logical channel from a first node; program code for updating, at the receiving node, a topology table with a first set of topology information contained in the first message; program code for receiving, at the receiving node, a second message on a second logical channel from a second node in the barrage relay network., the second logical channel being different from the first logical channel, the second message being periodically broadcast network wide by the second node, the second message comprising a unique identifier associated with a node in the barrage relay network and a request to transmit local topology information, the unique identifier identifying the node as a destination of the second message; program code for determining, at the receiving node, whether the unique identifier identifies the receiving node, wherein when the unique identifier does not identify the receiving node, program code for receiving, at the receiving node, a third message comprising a second set of topology information on a third logical channel from a third node in the barrage relay network and updating the topology table with the second set of topology information contained in the third message, the third logical channel being different from the first logical channel and the second logical channel, the third message being a response to the request to transmit local topology information, and the third message being a spatially-pipelined broadcast through the barrage relay network; and wherein when the unique identifier identifies the receiving node, program code for transmitting, from the receiving node, a fourth message comprising the topology table on a third logical channel, the fourth message being a response to the request to transmit local topology information, and the fourth message being another spatially-pipelined broadcast through the barrage relay network. - View Dependent Claims (16, 17, 18)
-
Specification