Traffic routing in small wireless data networks

• US 6,130,881 A
• Filed: 04/20/1998
• Issued: 10/10/2000
• Est. Priority Date: 04/20/1998
• Status: Expired due to Term

• Current Assignee: SRI International, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Stiller, Thomas Michael, Stephens, William Edward, Newman, Nisha Pauline
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US09/063,198
• Time in Patent Office: 904 Days
• Field of Search: 370/230, 370/231, 370/235, 370/236, 370/238, 370/254, 370/255, 370/389, 370/392, 370/400, 370/401, 370/410, 455/445, 709/238, 709/239, 709/240, 709/241, 709/242, 709/243, 709/245, 714/1, 714/2, 714/3, 714/4
• US Class Current: 370/238
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04Q 2213/13098 Mobile subscriber
• CPC Class Codes: H04Q 2213/13106 Microprocessor, CPU
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13174 Data transmission, file transfer
• CPC Class Codes: H04Q 2213/13291 Frequency division multiplexing, FDM
• CPC Class Codes: H04Q 2213/13292 Time division multiplexing, TDM
• CPC Class Codes: H04Q 2213/13294 CDMA, code division multiplexing, i.e. combinations of H04Q2213/13291 and/or H04Q2213/13292 with space division
• CPC Class Codes: H04Q 2213/13353 Routing table, map memory
• CPC Class Codes: H04Q 2213/13389 LAN, internet
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 84/10 Small scale networks; Flat hierarchical networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

A method of transmitting a message from a source node to a destination node in a small, wireless network having up to N nodes in which each message has appended thereto concise network configuration data which eliminates the need for routing protocols without adding significant overhead to the network communications. The method includes the steps of creating for each node a route table containing a count of the number of transmission hops necessary to reach each destination node and a node number of a neighboring node forming a next link in a chain of hops to each destination node, where the node number identifies a unique bit in an N bit address mask. Routing data is appended to the message data which includes an N bit destination word identifying the destination node or nodes, an N bit route word including a logical OR of the address mask of the relay node or nodes, and a route update message identifying what the current node knows about the network configuration. The number of N bit words in the route update message indicates a maximum number of transmission hops away from the current node that the current node could know about the network configuration. Upon receipt of such message data and its routing data, all receiving nodes update their route tables from the route update message. Then, if the receiving node is a destination node, the message data is processed. Also, if the receiving node is a relay node, then the receiving node replaces the route word and route update message with data from its updated route table and retransmits the message data with the destination word, the replaced route word and the replaced route update message as its routing data.

Claims

1. A method of transmitting message data from a source node to a destination node in a wireless network having up to N nodes, where each node includes a transmitter and a receiver, comprising the steps of:

creating for each node a route table containing a count of the number of transmission hops necessary to reach each remaining node in the wireless network and a node number of a neighboring node forming a next link in a chain of hops to each remaining node in the wireless network, said node number identifying a unique bit in an N bit address mask;

appending, to message data to be transmitted from the source node to a destination node, an N bit destination word identifying the destination node or nodes, an N bit route word including a logical OR of the address mask of each node in the wireless network that is expected to retransmit the message data through said network, and a route update message identifying what the source node knows about the network configuration, the route update message having at least one N-bit connectivity word, the number of N-bit connectivity words in the route update message indicating a maximum number of transmission hops away from the source node that the source node could know about the network configuration;

said source node transmitting said message data with said destination word, said route word and said route update message appended thereto;

each node which receives the message data with said destination word, said route word and said route update message appended thereto updating its route table from said route update message;

if said each node is identified in said destination word as a destination node, then said each node processing said message data, else ignoring said message data; and

if said each node is identified in said route word as a relay node, then said each node replacing said route word and route update message with data from the updated route table of said each node and retransmitting said message data with said destination word, said replaced route word and said replaced route update message appended thereto.

2. A method as in claim 1, including the additional steps of determining a route from the source node to the destination node or nodes by selecting a route with a minimum number of transmission hops and selecting the address mask of the first node in the route as the route word.

3. A method as in claim 1, wherein the source node performs the step of creating said destination word by taking a logical "OR" of the address masks of each destination node.

4. A method as in claim 1, wherein each node further performs the steps of determining a transmitting node of received message data and extracting the route update message for updating its route table.

5. A method as in claim 4, wherein each node performs the steps of determining that it is a destination node by taking a logical "AND" of the received destination word and the address mask of said each node and sending the message data to an application program for processing if the logical "AND" is true.

6. A method as in claim 4, wherein each node performs the steps of determining that it is a relay node by taking a logical "AND" of the received route word and the address mask of said each node and retransmitting the message data if the logical "AND" is true.

7. A method as in claim 4, wherein each node receiving a route update message updates its route table by performing the steps of comparing data in said route update message to data in its route table and replacing old data in said route table with new data from said route update message.

8. A method as in claim 7, wherein each node receiving a route update message performs the additional steps of setting a relay word in a row of said route table in which the transmitting node is the destination node to the address mask of the transmitting node and setting a transmission hop count in said row of said route table to 1 to indicate that the current node is directly connected to the transmitting node.

9. A method as in claim 8, wherein each node receiving a route update message performs the further steps of stacking each N bit word in said route update message vertically from first to last, selecting a column of bits corresponding to the unique bit in the N bit address of the destination node, and determining the number of transmission hops to said destination node as the binary number in said column defined by reading said bits in said column downward from said stacked first to last N bit words in said route update message.

10. A method as in claim 9, wherein each node receiving a route update message performs the further steps of, for each column in the stacked N bit words of the route update message:

setting the destination node to correspond to the node identified by said column position in said stacked N bit words of said route update message;

selecting a row of the route table corresponding to the destination node;

if all bits in said column are "0" or all bits in said column are "1", then if the selected row'"'"'s relay node corresponds to the relay word, setting the transmission hop count to zero and setting the relay mask to an initial state in the selected row; and

if all bits in said column are not "0" or "1", add one to the binary number in said column to get a new transmission hop count, then if the new transmission hop count is less than the transmission hop count in the selected row, replacing the transmission hop count with the new transmission hop count and setting the relay mask to the relay word in the selected row.

18. A program storage device readable by a processor of a node in a network so as to control the transmission of message data in said network, said program storage device storing thereon a program of instructions executable by said processor to perform the method steps of claim 1.

11. A wireless network having up to N nodes, each node in said network comprising:

a wireless transmitter;

a wireless receiver; and

a processor which processes software loaded thereon so as to perform the steps of;

creating and updating a route table containing a count of the number of transmission hops necessary to reach each remaining node in the wireless network and a node number of a neighboring node forming a next link in a chain of hops to each remaining node in the wireless network, said node number identifying a unique bit in an N bit address mask,

appending, to message data to be transmitted from a source node in said network to a destination node or nodes in said network, an N bit destination word identifying the destination node or nodes, an N bit route word including a logical OR of the address mask of each node in the wireless network that is expected to retransmit the message data through said network, and a route update message identifying what the current node knows about the configuration of said network, the route update message having at least one N-bit connectivity word, the number of N bit connectivity words in the route update message indicating a maximum number of transmission hops away from the current node that the current node could know about the configuration of said network, and

passing to said wireless transmitter for transmission said message data with said destination word, said route word and said route update message appended thereto.

12. A network as in claim 11, wherein upon receipt of message data with a destination word, a route word and a route update message appended thereto by said wireless receiver, said processor further processes said software so as to perform the steps of:

updating said route table with network configuration data from the received route update message;

if the current node is identified in said destination word as a destination node, then processing the received message data, else ignoring the received message data; and

if the current node is identified in said route word as a relay node, then replacing the received route word and the received route update message with data from the updated route table and retransmitting said message data with said destination word, said replaced route word and said replaced route update message appended thereto.

13. A network as in claim 12, said processor further processing said software so as to perform the steps of determining a route from the current node to the destination node or nodes by selecting a route with a minimum number of transmission hops and selecting the address mask of the first node in the route as the route word.

14. A network as in claim 12, wherein said processor further processes said software so as to perform the steps of determining a transmitting node of received message data and extracting the route update message for updating the route table of the current node.

15. A network as in claim 14, wherein said processor further processes said software so as to perform the steps of setting a relay word in a row of said route table in which the transmitting node is the destination node to the address mask of the transmitting node and setting a transmission hop count in the said row of said route table to 1 to indicate that the current node is directly connected to the transmitting node.

16. A network as in claim 15, wherein said processor further processes said software so as to perform the steps of stacking each N bit word in said route update message vertically from first to last, selecting a column of bits corresponding to the unique bit in the N bit address of the destination node, and determining the number of transmission hops to said destination node as the binary number in said column defined by reading said bits in said column downward from said stacked first to last N bit words in said route update message.

17. A network as in claim 16, wherein said processor further processes said software so as to perform the steps of, for each column in the stacked N bit words of the route update message:

setting the destination node to correspond to the node identified by said column position in said stacked N bit words of said route update message;

selecting a row of the route table corresponding to the destination node;

if all bits in said column are "0" or all bits in said column are "1", then if the selected row'"'"'s relay node corresponds to the relay word, setting the transmission hop count to zero and setting the relay mask to an initial state in the selected row; and

if all bits in said column are not "0" or "1", add one to the binary number in said column to get a new transmission hop count, then if the new transmission hop count is less than the transmission hop count in the selected row of the route table, replacing the transmission hop count with the new transmission hop count and setting the relay mask to the relay word in the selected row.