Sending messages to radio-silent nodes in ad-hoc wireless networks

• US 7,023,818 B1
• Filed: 07/27/2000
• Issued: 04/04/2006
• Est. Priority Date: 07/27/2000
• Status: Expired due to Term

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: BBNT Solutions LLC (Rtx Corporation)
• Inventors: Elliott, Brig Barnum
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/627,083
• Time in Patent Office: 2,077 Days
• Field of Search: 455/445, 455/404.2, 370/328, 370/338
• US Class Current: 370/328
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/126 the source of the received data
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method and apparatus (2, 20) are provided for transmitting a message from a first node (A) to a radio-silent node (S) in a network. The network includes a plurality of nodes. A location area corresponding to the radio-silent node (S) is determined. A set of nearby routers (Z₀–Z₁₀) within the location area is identified. The message is transmitted from the first node (A) to the set of nearby routers (Z₀–Z₁₀). Each router of the set of nearby routers (Z₀–Z₁₀) that receives the message retransmits the message for the radio-silent node (S).

Claims

1. A communications router for use in a communications network including a plurality of routers, the network having at least one radio-silent communications node which can receive messages, said communications router including a transceiver to transmit and receive messages, said communications router comprising:

an electronic memory circuit having network information stored therein; and

an electronic processor circuit which (i) determines a location area corresponding to the radio-silent node based on a maximum velocity of the radio-silent node and an elapsed time since the radio-silent node was known to be at an initial position, (ii) formulates a message for the radio-silent node, (iii) determines a set of routers located within the location area, and (iv) directs a transmission of the message to the set of routers for retransmission for the radio-silent node.

2. A communications router for use in a communications network including a plurality of routers, the network having at least one radio-silent communications node which can receive messages, said communications router including a transceiver to transmit and receive messages, said communications router comprising:

an electronic memory circuit having network information stored therein; and

an electronic processor circuit which (i) determines a location area corresponding to the radio-silent node based on a planned trajectory of the radio-silent node which includes at least one waypoint and a time at which the radio-silent node plans to be in the at least one waypoint, (ii) formulates a message for the radio-silent node, (iii) determines a set of routers located within the location area, and (iv) directs a transmission of the message to the set of routers for retransmission for the radio-silent node.

3. A communications router for use in a communications network including a plurality of routers, the network having at least one radio-silent communications node which can receive messages, said communications router including a transceiver to transmit and receive messages, said communications router comprising:

an electronic memory circuit having network information stored therein; and

an electronic processor circuit which (i) determines a location area corresponding to the radio-silent node, the location area comprises a circle having a center at a last known position of the radio-silent node and a radius equal to a communications range of the radio-silent node, (ii) formulates a message for the radio-silent node, (iii) determines a set of routers located within the location area, and (iv) directs a transmission of the message to the set of routers for retransmission for the radio-silent node.

4. A communications router for use in a communications network including a plurality of routers, the network having at least one radio-silent communications node which can receive messages, said communications router including a transceiver to transmit and receive messages, said communications router comprising:

an electronic memory circuit having network information stored therein; and

an electronic processor circuit which (i) determines a location area corresponding to the radio-silent node, the location area comprises a circle having a center at a last known position of the radio-silent node and a radius smaller than a communications range of the radio-silent node, (ii) formulates a message for the radio-silent node, (iii) determines a set of routers located within the location area, and (iv) directs a transmission of the message to the set of routers for retransmission for the radio-silent node.

5. In a communications system for communications among a plurality of routers in a network, the network having at least one radio-silent node which can receive messages, each of the communication routers including a transceiver to transmit and receive messages, a method of operating a first router of the plurality of routers comprising the steps of:

determining a location area corresponding to the radio-silent node based on a maximum velocity of the radio-silent node, and an elapsed time since the radio-silent node was known to be at an initial position;

formulating a message for the radio-silent node;

determining a set of routers located within the location area; and

directing the message to the set of routers for retransmission for the silent node.

6. In a communications system for communications among a plurality of routers in a network, the network having at least one radio-silent node which can receive messages, each of the communication routers including a transceiver to transmit and receive messages, a method of operating a first router of the plurality of routers comprising the steps of:

determining a location area corresponding to the radio-silent node based on a planned trajectory of the radio-silent node which includes at least one waypoint and a time at which the radio-silent node plans to be in the at least one waypoint;

formulating a message for the radio-silent node;

determining a set of routers located within the location area; and

directing the message to the set of routers for retransmission for the silent node.

7. In a communications system for communications among a plurality of routers in a network, the network having at least one radio-silent node which can receive messages, each of the communication routers including a transceiver to transmit and receive messages, a method of operating a first router of the plurality of routers comprising the steps of:

determining a location area corresponding to the radio-silent node;

formulating a message for the radio-silent node;

determining a multicast forwarding tree, based on the first router, whose end points comprises the set of routers;

determining a set of routers located within the location area; and

directing the message throughout the network according to the multicast forwarding tree to the set of routers for retransmission for the silent node.

8. In a communications system for communications among a plurality of routers in a network, the network having at least one radio-silent node which can receive messages, each of the communication routers including a transceiver to transmit and receive messages, a method of operating a first router of the plurality of routers comprising the steps of:

determining a location area corresponding to the radio-silent node, wherein the location area comprises a circle having a center at a last known position of the radio-silent node and a radius equal to a communications range of the radio-silent node;

formulating a message for the radio-silent node;

determining a set of routers located within the location area; and

directing the message to the set of routers for retransmission for the silent node.

9. In a communications system for communications among a plurality of routers in a network, the network having at least one radio-silent node which can receive messages, each of the communication routers including a transceiver to transmit and receive messages, a method of operating a first router of the plurality of routers comprising the steps of:

determining a location area corresponding to the radio-silent node, wherein the location area comprises a circle having a center at a last known location of the radio-silent node, the circle having a radius smaller than a communications range of the radio-silent node;

formulating a message for the radio-silent node;

determining a set of routers located within the location area; and

directing the message to the set of routers for retransmission for the silent node.

10. In a communications system for communications in a network among a plurality of wireless nodes, the network including at least one radio-silent node capable of receiving network messages, each of the nodes includes a transceiver to transmit and receive messages, a method of operating the network comprising the steps of:

formulating a message for the radio-silent node in a first node of the plurality of nodes;

determining a location area of the radio-silent node;

defining a multicast routing group comprising a set of the plurality of nodes including at least one node within the location area;

multicasting the message from the first node to the multicast routing group, wherein each node of the multicast routing group that receives the message retransmits the message for the radio-silent node;

receiving a copy of the message in the radio-silent node, wherein the message comprises a node sender sequence number and a node identifier of the first node;

storing the node sender sequence number and node identifier in memory when the copy is the first received copy; and

disregarding the message when the copy is not the first received copy.

11. In a communications system for communications in a network among a plurality of wireless nodes, the network including at least one radio-silent node capable of receiving network messages, each of the nodes includes a transceiver to transmit and receive messages, a method of operating the network comprising the steps of:

formulating a message for the radio-silent node in a first node of the plurality of nodes;

determining a location area of the radio-silent node;

defining a multicast routing group comprising a set of the plurality of nodes including at least one node within the location area;

multicasting the message from the first node to the multicast routing group, wherein each node of the multicast routing group that receives the message retransmits the message for the radio-silent node;

receiving a copy of the message in the radio-silent node, wherein the message comprises a node sender sequence number and a node identifier of the first node;

identifying the node sender sequence number and the node identifier from the message copy;

determining if the node sender sequence number and node identifier are stored in a memory; and

processing the message and storing the node sender sequence number and node identifier in the memory when said determining step determines that the node sender sequence number and node identifier have not been previously stored.

12. The method according to claim 11, further comprising a step of disregarding the message when the node sender sequence number and node identifier have been previously stored.

13. In a communications system for communications in a network among a plurality of wireless nodes, the network including at least one radio-silent node capable of receiving network messages, each of the nodes includes a transceiver to transmit and receive messages, a method of operating the network comprising the steps of:

formulating a message for the radio-silent node in a first node of the plurality of nodes;

determining trajectory information of the radio-silent node, the trajectory information including a plurality of waypoints and an associated arrival and departure time for each waypoint;

consulting a current time;

calculating a location area by (i) determining whether the current time falls within a time interval associated with any of the plurality of waypoints, and centering a location area at a waypoint when the current time is within the time interval associated with the waypoint, (ii) calculating a location area between a first and second waypoint when the current time is between a departure time of the first waypoint and an arrival time of the second waypoint, the location area comprising a transversal path between the first and second waypoints, and (iii) determining a location area of the radio-silent node based on a velocity of the radio-silent node and an elapsed time since leaving a last identified waypoint when the current time is later than a departing time for the last identified waypoint;

defining a multicast routing group comprising a set of the plurality of nodes including at least one node within the location area; and

multicasting the message from the first node to the multicast routing group, wherein each node of the multicast routing group that receives the message retransmits the message for the radio-silent node.

14. In a communications system for communications among a plurality of routers in a network, the network having at least one radio-silent node which can receive messages, a planned trajectory of the radio-silent node being available to the plurality of routers, the planned trajectory including a plurality of waypoints and at least one time associated with each waypoint, a method of transmitting a message to the radio-silent node comprising the steps of:

determining an estimated location of the radio-silent node based on the plurality of waypoints and respective associated times;

determining a set of routers comprising at least one router within the estimated location; and

performing multicast routing of the message to the set of routers, the message to be broadcast by the set of routers for the radio-silent node.

15. A method of estimating a location area of a radio-silent node in an ad-hoc network including a plurality of nodes, the method comprising the steps of:

determining an initial position of the radio-silent node; and

calculating a location area for the radio-silent node, the location area centered at the initial position and having a radius equal to a maximum velocity of the radio-silent node multiplied by an elapsed time since the radio-silent node was known to be at the initial position.

16. A method of estimating a location area of a radio-silent node in an ad-hoc network including a plurality of nodes, the method comprising the steps of:

determining an advertised position of the radio-silent node; and

calculating a location area for the radio-silent node based on the advertised position, at least in part by evaluating geographic location indicators for the radio-silent node and at least one time for each indicator.

17. A method of estimating a location area of a radio-silent node in an ad-hoc network including a plurality of communication nodes, the network including trajectory information for the radio-silent node, the trajectory information including a velocity indicator for the radio-silent node, a plurality of waypoints, and an arrival and a departure time associated with each waypoint, each of the plurality of waypoints comprising a geographic location, the method comprising the steps of:

determining a current time;

calculating an estimated location area having a center at a geographic location of a waypoint when the current time falls within the arrival and departure times associated with the waypoint;

calculating an estimated location area comprising a transversal path between a first waypoint and a second waypoint when the current time falls between the departure time of the first waypoint and the arrival time of the second waypoint; and

calculating an estimated location area centered at a last waypoint, the area having a radius extending a distance from the last waypoint to a distance equal to the velocity indicator multiplied by the elapsed time since the departure time associated with the last waypoint, when the current time is later than the departure time associated with the last waypoint.

18. A method of transmitting a message from a first node to a mobile radio-silent node in a network including a plurality of nodes, the method comprising the steps of:

determining a location area corresponding to the radio-silent node including determining a radius of an area centered at an initial position of the radio-silent node by multiplying a velocity of the radio-silent node with an elapsed time since the radio-silent node was known to be at the initial position;

identifying a set of nodes located within the location area; and

transmitting a message from the first node for distribution to the set nodes, wherein each node of the set of nodes that receives the message broadcasts the message for the radio-silent node.

19. A method of transmitting a message from a first node to a mobile radio-silent node in a network including a plurality of nodes and a trajectory of the radio-silent node, the trajectory including at least one planned geographic location and at least one time associated with the at least one planned geographic location, the method comprising the steps of:

determining a location area corresponding to the radio-silent node using the at least one planned geographic location and the associated time;

identifying a set of nodes located within the location area; and

transmitting a message from the first node for distribution to the set nodes, wherein each node of the set of nodes that receives the message broadcasts the message for the radio-silent node.

20. A method of transmitting a message from a first node to a radio-silent node in a network including a plurality of nodes, the method comprising the steps of:

determining a location area corresponding to the radio-silent node, the location area comprising a radius equal to a radio receive range of the radio-silent node plus a distance equal to a velocity of the radio-silent node multiplied by an elapsed time since the radio silent node was at an initial position;

identifying a set of nodes located within the location area; and

transmitting a message from the first node for distribution to the set nodes, wherein each node of the set of nodes that receives the message broadcasts the message for the radio-silent node.

21. A data structure of a trajectory routing message for a communications node in a network having a plurality of nodes, the data structure being stored on a computer readable medium, said data structure comprising:

an originating node identifier;

a message sequence number;

at least one waypoint including a geographic identifier and at least one time associated with the at least one waypoint; and

a velocity indicator of the communications node.

22. A method of formulating a trajectory routing message for a communications station that communicates among a plurality of similar stations in a network, the method comprising the steps of:

providing an originating node identifier and a message sequence number; and

providing a plurality of geographic location identifiers and at least one associated time for each identifier.

23. In a communications system for communications among a plurality of routers in a network, each router being capable of operating as a radio-silent node, wherein a radio-silent node is adapted to receive messages from the network, each of the communications routers including a transceiver to transmit and receive messages, a method of operating the network comprising the steps of:

generating and transmitting a trajectory message in a first router when the first router operates as a router, the message including planned trajectory information, a node identifier and a sequence number; and

disregarding, in the first router when operating as a radio-silent node, duplicate copies of a received message.

24. A method according to claim 23, wherein after the first node emerges from operating as a silent node, the method comprises a step of flooding a routing update from the first node through the network.

25. A method according to claim 24, wherein the routing update takes priority over the trajectory message.

26. In a communications system for communications in a network among a plurality of wireless stations, the network including at least one silent station, each of the stations including a transceiver to transmit and receive messages, a method of operating a network comprises the steps of:

determining planned trajectory information for each node in the network; and

providing the planned trajectory information to each node in the network.

27. The method according to claim 26, wherein the planned trajectory information is provided as network configuration data, and wherein the planned trajectory information includes waypoints having an associated arrival and departure time, and a velocity indicator of the radio-silent station.

28. The method according to claim 26, wherein the planned trajectory information is provided as a routing update, wherein the planned trajectory information includes waypoints having an associated arrival and departure time, and a velocity indicator of the radio-silent station.

29. The method according to claim 26, wherein said determining step is preformed in a central server.

30. The method according to claim 29, wherein the central server computes a location area for the radio-silent station and determines which out of the plurality of stations are nearby the radio-silent station.

31. A mobile communications station which communicates among a plurality of mobile stations in an ad-hoc network in which stations are arranged in clusters of communication member stations, with one member station in each cluster being a head station for the cluster, each member station communicating with the network through at least one cluster head station, a cluster head station communicating with zero or more cluster head stations, the network including at least one radio-silent cluster member, said mobile station including a transceiver which transmits signals to and receives signals from mobile stations in the network, said mobile communications station comprising:

a memory having network information stored thereon; and

a processor which (i) operates said mobile station as a cluster head or cluster member station;

(ii) determines a location area of the silent cluster member, (ii) formulates a message to be transmitted to the silent cluster member, (iii) determines a set of mobile stations corresponding to the location area of the silent cluster member, and (iv) causes said mobile communications station to transmit the message for distribution to the set of nearby mobile stations.