Traffic routing in small wireless data networks

• US 6,704,283 B1
• Filed: 02/17/2000
• Issued: 03/09/2004
• Est. Priority Date: 04/20/1998
• Status: Expired due to Term

• Current Assignee: SRI International, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Newman, Nisha Pauline, Stiller, Thomas Michael, Stephens, William Edward
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US09/506,096
• Time in Patent Office: 1,482 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-243, 709/245, 714/1-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 for transmitting message data within a wireless network from a source node to at least one destination node, comprising:

updating a configuration of the wireless network by stacking each N bit word in a route update message vertically from first to last;

selecting a column of bits corresponding to the destination node, and determining a hop count associated with the destination node as the binary number defined by the column of bits corresponding to the destination node;

determining a destination identifier based on the at least one destination node;

determining a route identifier based on the at least one destination node and the configuration of the wireless network known at the source node, the route identifier indicating at least one neighboring node within the wireless network;

determining a route update message including at least one connectivity mask based on the configuration of the wireless network known at the source node; and

transmitting the message data appended with the destination identifier, the route identifier and the route update message.

2. The method of claim 1, wherein:

the destination identifier is an N bit word indicating the at least one destination node, N being a number of nodes within the wireless network,

the route identifier is an N bit word indicating at least one node neighboring the source node, and

the route update message is at least one N bit word indicating a configuration of the wireless network known by the source node.

3. The method of claim 1, wherein:

each destination node has an associated mask,

the destination identifier is a logical OR of the masks associated with each destination node.

4. A method for receiving message data at a node within a wireless network, comprising:

extracting a destination identifier from received message data, the received message data being appended with the destination identifier, a route indicator and a route update message;

comparing the extracted destination identifier with a node address; and

processing the received message data when the extracted destination identifier matches the compared node address;

wherein, when the route update message has more than one N bit word, updating a route table by at least;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding to the destination node; and

determining the hop count associated with the destination node as the binary number defined by the column of bits corresponding to the destination node.

5. The method of claim 4, wherein:

the destination identifier is an N bit word indicating the at least one destination node, N being a number of nodes within the wireless network, and

the node address being an N bit work associated with the node.

6. The method of claim 5, wherein:

said comparing step includes performing a logical AND of the extracted destination identifier and the node address, and

the extracted destination identifier matches the node address when the logical AND is true.

7. The method of claim 4, wherein:

said processing step includes sending the message data to an application program.

8. A node within a wireless network, comprising:

a processor,

a memory coupled to said processor, said memory having stored therein a route table having a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes within the wireless network, said memory having stored therein a plurality of instructions that, when executed by a processor, cause the processor to;

determine a destination identifier based on at least one destination node;

determine a route identifier based on the at least one destination node and a configuration of the wireless network known at a source node, the route identifier indicating at least one neighboring node within the wireless network;

determine a route update message including at least one connectivity mask based on the configuration of the wireless network known at the source node;

transmit the message data appended with the destination identifier, the route identifier and the route update message; and

when the route update message has more than one N bit word;

stack each N bit word in the route update message vertically from first to last;

select a column of bits corresponding to the destination node; and

determine the hop count associated with the destination node as the binary number defined by the column of bits corresponding to the destination node.

9. The node of claim 8, wherein:

the destination identifier is an N bit word indicating the at least one destination node, N being a number of nodes within the wireless network,

the route identifier is an N bit word indicating at least one node neighboring the source node, and

the route update message is at least one N bit word indicating a configuration of the wireless network known by the source node.

10. The method of claim 9, wherein:

each destination node has an associated mask,

the destination identifier is a logical OR of the masks associated with each destination node.

11. A node within a wireless network, comprising:

a processor,

a memory coupled to said processor, said memory having stored therein a route table having a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes within the wireless network, said memory having stored therein a plurality of instructions that, when executed by a processor, cause the processor to;

extract a destination identifier from received message data, the received message data being appended with a destination identifier, a route indicator and a route update message;

compare the extracted destination identifier with a node address;

process the received message data when the extracted destination identifier matches the compared node address; and

,

when the route update message has more than one N bit word;

stack each N bit word in the route update message vertically from first to last;

select a column of bits corresponding to the destination one of said nodes; and

determine a hop count associated with the destination one of said nodes as the binary number defined by the column of bits corresponding to the destination on of said nodes.

12. The node of claim 11, wherein:

the destination identifier is an N bit word indicating the at least one destination node, N being a number of nodes within the wireless network, and

the node address being an N bit work associated with the node.

13. The node of claim 12, wherein the compare instruction further includes an instruction, when executed by the processor, causes the processor to:

perform a logical AND of the extracted destination identifier and the node address, the extracted destination identifier matches the node address when the logical AND is true.

14. The node of claim 11, wherein the process instruction further includes an instruction, when executed by the processor, causes the processor to:

send the message data to an application program.

15. A wireless network having a plurality of nodes, each node comprising:

a route table having a plurality of hop counts and a plurality of relay indicators associated with the plurality of nodes;

a receiver coupled to said route table, said receiver receiving message data appended with a route identifier and a route update message;

a transmitter coupled to said receiver and to said route table, said transmitter sending message data with the route identifier and the route update message being updated based on the route table; and

,

code for stacking each N bit word in the route update message vertically from first to last, selecting a column of bits corresponding to the destination node, and determining the hop count associated with the destination node as the binary number defined by the column of bits corresponding to the destination node when the route update message has more than one N bit word.

16. A method for relaying, at a node within a wireless network, received message data appended with a route identifier and a route update message, said method comprising:

updating a route table based on the route update message appended to received message data, the route table including a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes within the wireless network, wherein when the route update message has more than one N bit word, said updating comprises;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding to the destination node; and

determining the hop count associated with the destination node as the binary number defined by the column of bits corresponding to the destination node;

selecting said at least one neighboring node within the wireless network based on at least one hop count and at least one relay indicator of the route table, wherein the route identifier is an N bit word indicating the at least one selected neighboring node, N is a number of nodes within the wireless network, and the route update message is at least one N bit work indicating configuration information about the wireless network known by a transmitting node from which the route update message was received;

replacing the route identifier and the route update message appended to the received message data based on at least one hop count and at least one relay indicator of the updated route table; and

transmitting the message data appended with the replaced route identifier and the replaced route update message to the selected at least one neighboring node.

17. The method of claim 16, further comprising:

performing a logical AND of the route identifier and a node address associated with the node, the node address being an N bit word;

performing said updating step, said selecting step, said replacing step and said transmitting step before and when the logical AND is true.

18. The method of claim 16, further comprising:

determining the transmitting node from which the message data was received;

setting the hop count associated with the transmitting node to one; and

updating the relay indicator associated with the transmitting node with a value identifying the transmitting node.

19. The method of claim 18, wherein the value identifying the transmitting node is an N bit word indicating the transmitting mode.

20. The method of claim 16, further comprising:

performing, when a timer exceeds a predetermined time out for a row of the route table, the following;

setting the hop count associated with the transmitting node to an initial value; and

updating the relay indicator associated with an initial state.

21. A method for relaying, at a node within a wireless network, received message data appended with a route identifier and a route update message, said method comprising:

updating a route table based on the route update message appended to received message data, wherein the route table has a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes within the wireless network;

selecting at least one neighboring node within the wireless network based on at least one hop count and at least one relay indicator of the route table;

replacing the route identifier and the route update message appended to the received message data based on at least one hop count and at least one relay indicator of the updated route table; and

transmitting the message data appended with the replaced route identifier and the replaced route update message to the selected at least one neighboring node;

wherein, said updating comprises the following when the route update message has more than one N bit word;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding to a target node;

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

setting, for the selected row, the hop count to zero and the route indicator to an initial state if;

the relay indicator consists of all one'"'"'s or zero'"'"'s, and the relay indicator associated with the selected row corresponds to the node; and

,

setting, for the selected row, the hop count to the value of one plus the column of bits corresponding to the target node if;

the hop count is less than one plus the column of bits corresponding to the target node, and the relay indicator includes a one and a zero.

22. A method for updating a route table associated with a node within a wireless network, the route table having a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes in the wireless network, comprising:

extracting a route update message from received message data, the received message data being appended with a route update message; and

updating the hop count and the relay indicator stored in the route table based on the extracted route update message;

wherein, when the route update message has more than one N bit word, said updating comprises;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding to the destination node; and

determining the hop count associated with the destination node as the binary number defined by the column of bits corresponding to the destination node.

23. The method of claim 22, wherein:

the route update message is at least one N bit word indicating configuration information about the wireless network known by a transmitting node from which the route update message was received.

24. The method of claim 22, further comprising:

determining the transmitting node from which the message data was received;

setting the hop count associated with the transmitting node to one; and

updating the relay indicator associated with a value identifying the transmitting node.

25. The method of claim 24, wherein the value identifying the transmitting node is an N bit word indicating the transmitting mode, N being a number of nodes within the wireless network.

26. A method for updating a route table associated with a node within a wireless network, the route table having a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes in the wireless network, comprising:

extracting a route update message from received message data, the received message data being appended with a route update message; and

updating at least one of said hop counts and the relay indicators based on the extracted route update message;

wherein, when the route update message has more than one N bit word, said updating comprises;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding to the destination node; and

determining the hop count associated with the destination node as the binary number defined by the column of bits corresponding to the destination node.

27. The method of claim 26, further comprising:

performing, when a timer exceeds a predetermined time out for an entry of the route table, the following;

setting the hop count associated with the transmitting node to an initial value; and

updating the relay indicator associated with an initial state.

28. A method for updating a route table associated with a node within a wireless network, the route table having a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes in the wireless network, comprising:

extracting a route update message from received message data, the received message data being appended with a route update message; and

updating at least one of said hop counts and relay indicators stored in the route table based on the extracted route update message;

wherein when the route update message has more than one N bit word, said updating comprises;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding to a target node;

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

setting, for the selected row, the hop count to zero and the route indicator to an initial state if;

the relay indicator consists of all one'"'"'s or zero'"'"'s, and the relay indicator associated with the selected row corresponds to the node; and

,

setting, for the selected row, the hop count to the value of one plus the column of bits corresponding to the target node if;

the hop count is less than one plus the column of bits corresponding to the target node, and the relay indicator includes a one and a zero.

29. A node within a wireless network, comprising:

a processor,

a memory coupled to said processor, said memory having stored therein a route table having a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes within the wireless network, and a plurality of instructions that, when executed by a processor, cause the processor to;

update the route table based on a route update message appended to received message data, wherein the route update message includes at least one N bit word indicating configuration information about the wireless network known by a transmitting node from which the route update message was received, wherein when the route update message has more than one N bit word, said updating comprises;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding to the destination node; and

determining the hop count associated with the destination node as the binary number defined by the column of bits corresponding to the destination node;

select at least one neighboring node within the wireless network based on at least one hop count and at least one relay indicator of the route table;

replace a route identifier appended to the received message data and the route update message appended to the received message data based on at least one hop count and at least one relay indicator of the updated route table, wherein the route identifier includes an N bit word indicating the at least one selected neighboring node, N being a number of nodes within the wireless network.

30. The node of claim 29, wherein:

the route table has a plurality of hop counts and a plurality of relay indicators asssociated with the plurality of nodes within the wireless network;

the at least one neighboring node within the wireless network is selected based on at least one hop count and at least one relay indicator of the route table; and

the route identifier and the route update message appended to the received message data is replaced based on at least one hop count and at least one relay indicator of the updated route table.

31. The node of claim 29, wherein:

the route identifier is an N bit word indicating the at least one selected neighboring node, N being a number of nodes within the wireless network;

the route update message is at least one N bit word indicating configuration information about the wireless network known by a transmitting node from which the route update message was received.

32. The node of claim 29, wherein said memory has stored thereon further instructions that, when executed by a processor, cause the processor to:

perform a logical AND of the route identifier and a node address associated with the node, the node address being an N bit word;

perform said update, said select and said replace before and when the logical AND is true.

33. The node of claim 29, wherein said memory has stored thereon further instructions that, when executed by a processor, cause the processor to:

determine the transmitting node from which the message data was received;

set the hop count associated with the transmitting node to one; and

update the relay indicator associated with the transmitting node with a value identifying the transmitting node.

34. The node of claim 33, wherein the value identifying the transmitting node is an N bit word indicating the transmitting mode.

35. The node of claim 29, wherein said memory has stored thereon further instructions that, when executed by a processor, cause the processor to:

perform, when a timer exceeds a predetermined time out for a row of the route table, the following;

set the hop count associated with the transmitting node to an initial value; and

update the relay indicator associated with an initial state.

36. A node within a wireless network, comprising:

a processor,

a memory coupled to said processor, said memory having stored therein a route table having associated with a plurality of nodes within the wireless network, said memory having stored therein a plurality of instructions that, when executed by a processor, cause the processor to;

update the route table based on a route update message appended to received message data, wherein when the route update message has more than one N bit word, said updating comprises;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding a target node;

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

setting, for the selected row, the hop count to zero and the route indicator to an initial state if;

the relay indicator consists of all one'"'"'s and zero'"'"'s, and the relay indicator associated with the selected row corresponds to the node; and

, setting, for the selected row, the hop count to the value of one plus the column of bits corresponding to the target node if;

the hop count is less than one plus the column of bits corresponding to the target node, and the relay indicator includes a one and a zero;

select at least one neighboring node within the wireless network based on the route table; and

,

replace a route identifier appended to the received message data and the route update message appended to the received message data based on the updated route table;

wherein, the route table has a plurality of hop counts and a plurality of relay indicators associated with the plurality of nodes within the wireless network;

the at least one neighboring node within the wireless network is selected based on at least one hop count and at least one relay indicator of the route table; and

,

the route identifier and the route update message appended to the received message data is replaced based on at least one hop count and at least one relay indicator of the updated route table.

37. A node within a wireless network, comprising:

a processor,

a memory coupled to said processor, said memory having stored therein a route table having a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes within the wireless network, said memory having stored therein a plurality of instructions that, when executed by a processor, cause the processor to;

extract a route update message appended to received message data; and

,

update the hop count and the relay indicator stored in the route table based on the extracted route update message;

wherein, when the route update message has more than one N bit word, said updating comprises;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding to the destination node; and

determining the hop count associated with the destination node as the binary number defined by the column of bits corresponding to the destination node.

38. The node of claim 37, wherein:

the route update message is at least one N bit word indicating configuration information about the wireless network known by a transmitting node from which the route update message was received.

39. The node of claim 37 wherein said memory has stored therein further instructions that, when executed by a processor, cause the processor to:

determine the transmitting node from which the message data was received;

set the hop count associated with the transmitting node to one; and

update the relay indicator associated wit the transmitting node with a value identifying the transmitting node.

40. The node of claim 39, wherein the value identifying the transmitting node is an N bit word indicating the transmitting mode, N being a number of nodes within the wireless network.

41. The node of claim 37, wherein said memory has stored thereon further instructions that, when executed by a processor, cause the processor to:

perform, when a timer exceeds a predetermined time out for a row of the route table, the following;

set the hop count associated with the transmitting node to an initial value; and

update the relay indicator associated with an initial state.

42. A node within a wireless network, comprising:

a processor,

a memory coupled to said processor, said memory having stored therein a route table having a plurality of hop counts and a plurality of relay indicators associated with a plurality of nodes within the wireless network, said memory having stored therein a plurality of instructions that, when executed by a processor, cause the processor to;

extract a route update message appended to received message data; and

,

update the hop count and the relay indicator stored in the route table based on the extracted route update message;

wherein, when the route update message has more than on N bit word, said updating comprises;

stacking each N bit word in the route update message vertically from first to last;

selecting a column of bits corresponding a target node;

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

setting, for the selected row, the hop count to zero and the route indicator to an initial state if;

the relay indicator consists of all one'"'"'s or zero'"'"'s, and the relay indicator associated with the selected row corresponds to the node; and

, setting, for the selected row, the hop count to the value of one plus the column of bits corresponding to the target node if;

the hop count is less than one plus the column of bits corresponding to the target node, and the relay indicator includes a one and a zero.