Method for routing data packets within a wireless, packet-hopping network and a wireless network for implementing the same

• US 5,978,364 A
• Filed: 02/29/1996
• Issued: 11/02/1999
• Est. Priority Date: 02/29/1996
• Status: Expired due to Term

• Current Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Original Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Inventors: Melnik, George A.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/608,910
• Time in Patent Office: 1,342 Days
• Field of Search: 370/422, 370/419, 370/455, 370/352, 370/355, 370/315, 370/389, 370/238, 370/254, 370/255, 370/347, 370/349, 370/320, 370/321, 370/335, 370/342, 395/118, 395/325
• US Class Current: 370/320
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

A random multiple path tabular routing method for routing data packets within a wireless, packet-hopping network, e.g., an intelligent lighting control system, which includes the steps of programming a plurality of the individual nodes to each serve as a repeater node for at least one other individual node, the repeater nodes forming multiple programmed communication paths between the central node and each of at least selected ones of the individual nodes, and randomly hopping the data packets along the programmed communication paths. The repeater nodes are preferably programmed on the basis of nodal connectivity information obtained during a network initialization process. The repeater nodes are preferably programmed by storing compact partial routing tables in a memory portion of each of these repeater nodes. This routing method is partially deterministic or tabular in that routing tables are used to preprogram the multiple communication paths, and partially random, in that the data packets are randomly hopped along these preprogrammed multiple paths, rather than being hopped along preprogrammed singular paths. Each of the individual nodes preferably includes a first address table and a second address table stored in its respective memory. The step of programming is preferably carried out by storing in the first address table of each of the individual nodes at least its own address, and storing in the second address table of each of the individual nodes the address of each node for which that node is selected to serve as a repeater node. The step of randomly hopping the data packets is preferably carried out by programming each of the nodes which receives a data packet to compare the address contained in the address byte of that data packet with the address(es) stored in its first address table, and if a match is detected, to respond to that data packet, and to compare the address contained in the address byte of that data packet with the address(es) stored in its second address table, and if a match is detected, to repeat that data packet. All data communications are preferably carried out in accordance with a CSMA protocol. The invention also relates to a network which is programmed to implement this routing method.

Claims

1. A method for routing data packets within a wireless network including a central node and individual nodes, comprising the steps of:

programming a plurality of said individual nodes to each serve as a repeater node for at least one other one of said individual nodes, said individual nodes programmed to serve as a one of said repeater nodes forming at least two programmed communication paths between said central node and each of at least selected ones of said individual nodes; and

randomly hopping data packets along said programmed communication paths.

2. The method as set forth in claim 1, wherein the step of programming is carried out on the basis of nodal connectivity information obtained during a network initialization process.

3. The method as set forth in claim 1, wherein:

each of said individual nodes includes an address table; and

the step of programming is carried out by storing a routing table in said address table of each of said individual nodes programmed to serve as a repeater node.

4. The method as set forth in claim 1, wherein:

each of said individual nodes includes a first address table which contains at least its own address, and a second address table; and

,

the step of programming includes a sub-step of storing in said second address table of each of said individual nodes programmed to serve as a repeater node the address of each node for which that node is programmed to serve as a repeater node.

5. The method as set forth in claim 4, wherein the step of randomly hopping data packets along said programmed communication paths includes the sub-steps of:

said central node transmitting said data packets to all nodes within its transmitting range;

each of said nodes which receives a data packet transmitted by said central node comparing an address contained in an address byte of that data packet with at least one address stored in each of its first and second address tables, and if a match is detected between said at least one address stored in said first address table and said address contained in said address byte, responding to that data packet, and if a match is detected between said at least one address stored in said second address table and said address contained in said address byte, repeating that data packet; and

,

each of said nodes which receive a data packet repeated by other ones of said nodes comparing said address contained in said address byte of that data packet with said at least one address stored in its first and second address tables, and if a match is detected between said at least one address stored in said first address table and said address contained in said address byte, responding to that data packet, and if a match is detected between said at least one address stored in said second address table and said address contained in said address byte, repeating that data packet.

6. The method as set forth in claim 5, wherein said network has a common RF channel, and all data communications within said network are via said common RF channel.

7. The method as set forth in claim 6, wherein all data communications within said network are carried out in accordance with a prescribed channel access protocol.

8. The method as set forth in claim 7, wherein said prescribed channel access protocol is a carrier sense multiple access protocol.

9. The method as set forth in claim 5, wherein each of said nodes includes a packet ID memory and each said data packet includes a packet ID byte which contains a packet identification code identifying that data packet, and the step of randomly hopping data packets along said programmed communication paths includes the further sub-steps of:

each of said nodes which repeats a data packet storing said packet identification code of that data packet in its packet ID memory; and

,

each of said nodes which receives a data packet determining whether said packet identification code of that data packet is already stored in its packet ID memory, and, if so, discarding that data packet.

10. The method as set forth in claim 1, wherein said selected ones of said individual nodes are not directly linked to said central node.

11. The method as set forth in claim 1, wherein each of said individual nodes programmed to serve as a repeater node is programmed to serve as a repeater node for at least one other node, but for less than all other nodes in the network.

12. The method as set forth in claim 1, wherein said network comprises a building system control network, and said central node comprises a building computer.

13. The method as set forth in claim 5, wherein said individual nodes are organized into at least two separate groups of nodes each having a unique group address, and the step of programming includes the further sub-steps of:

storing in said first address table of each of said individual nodes the group address of any group to which it belongs; and

,

programming a selected subset of said individual nodes to each serve as group repeater nodes for each of said groups by storing in said second address table of each of said groups of repeater nodes the group address of any group for which it has been selected to serve as a group repeater node.

14. The method as set forth in claim 5, wherein said entire network has a global address, and the step of programming includes the further sub-steps of:

storing said global address in said first address table of each of said individual nodes; and

,

programming a selected subset of said individual nodes to serve as global repeaters for the entire network by storing said global address in said second address table of each of said global repeaters.

15. A method for routing data packets within a wireless network comprised of a central node and individual nodes, comprising the steps of:

programming multiple paths between said central node and each of at least selected ones of said individual nodes;

randomly hopping data packets between said central node and said selected ones of said individual nodes via the programmed multiple paths;

wherein each of said individual nodes has a unique address and is provided with first and second address tables, and the step of programming includes the sub-steps of;

storing in said first address table of each of said individual nodes at least its own address;

selecting a plurality of said individual nodes to each serve as a repeater node for at at least one other one of said individual nodes; and

,

storing in said second address table of each of said individual nodes programmed to serve as a repeater node the address of said at least one other one of said individual nodes.

16. The method as set forth in claim 15, wherein the step of programming is carried out on the basis of nodal connectivity information obtained during a network initialization process.

17. The method as set forth in claim 15, wherein the step of randomly hopping includes the sub-steps of:

each of said nodes which receives a data packet comparing an address contained in an address byte of that data packet with at least one address stored in said first address table, and if a match is detected between said at least one address stored in said second address table and said address contained in said address byte, responding to that data packet; and

,

each of said nodes which receives a data packet comparing said address contained in said address byte of that data packet with at least one address stored in its second address table, and if a match is detected between said at least one address stored in said second address table and said address contained in said address byte, repeating that data packet.

18. A method for programming a wireless network comprised of a central node and individual nodes each having an address, comprising the steps of:

providing each of said individual nodes with a first address table and a second address table;

storing in said first address table of each of said individual nodes at least its own address;

storing in said second address table of each of selected ones of said individual nodes the address of at least one other one of said individual nodes; and

,

wherein said selected ones of said individual nodes form multiple predetermined paths between said central node and each of at least selected ones of said individual nodes.

19. The method as set forth in claim 18, further comprising the steps of:

programming each of said individual nodes to respond to any data packet which contains an address which matches any address stored in its said first address table; and

,

programming each of said individual nodes to repeat any data packet which contains an address which matches any address stored in its said second address table.

20. A wireless network, comprising:

a central node which includes an RF transceiver, digital signal processing circuitry, and a memory; and

,

individual nodes each of which includes an RF transceiver, digital signal processing circuitry, and a memory, a plurality of said individual nodes being programmed to each serve as a repeater node for at least one other one of said individual nodes, said individual nodes programmed to serve as a repeater node forming at least two programmed communication paths between said central node and each of at least selected ones of said individual nodes.

21. The wireless network as set forth in claim 20, wherein said central node is programmed to execute a network initialization routine for obtaining nodal connectivity information for programming said programmed communication paths.

22. The wireless network as set forth in claim 20, wherein each of said repeater nodes further includes a routing table stored in its memory.

23. The wireless network as set forth in claim 20, wherein each of said individual nodes further includes a first address table which contains at least its own address, and a second address table which contains an address of each node for which that node is programmed to serve as a repeater node.

24. The wireless network as set forth in claim 23, wherein the network is programmed to randomly hop data packets along said programmed communication paths.

25. The wireless network as set forth in claim 20, wherein the network is programmed to randomly hop data packets along said programmed communication paths.

26. The wireless network as set forth in claim 24, wherein:

each of said individual nodes is programmed to compare an address contained in an address byte of a data packet that it receives with at least one address stored in its said first address table, and if a match is detected, to respond to that data packet; and

,

each of said individual nodes is programmed to compare an address contained in an address byte of a data packet that it receives with at least one address stored in its said second address table, and if a match is detected, to repeat that data packet.

27. The wireless network as set forth in claim 26, wherein:

the network has a common RF channel;

all data communications within the network are via said common RF channel; and

,

all data communications within the network are carried out in accordance with a prescribed channel access protocol.

28. The wireless network as set forth in claim 27, wherein said prescribed channel access protocol is a carrier sense multiple access protocol.

29. The wireless network as set forth in claim 25, wherein:

each of said individual nodes includes a packet ID memory, and each data packet includes a packet ID byte which contains a packet identification code identifying that data packet;

each of said individual nodes programmed to serve as a repeater node is programmed to store said packet identification code of each packet that it repeats in its said packet ID memory; and

,

each of said individual nodes programmed to serve as a repeater node is programmed to compare said packet identification code of each data packet that it receives with said packet identification codes stored in its said packet ID memory, and, if a match is found, to discard that data packet.

30. The wireless network as set forth in claim 20, wherein each of said individual nodes programmed to serve as a repeater node for each leg of at least selected ones of said programmed communication paths are located within a common cell comprised of a plurality of said nodes which are within an effective listening range of each other.

31. The wireless network as set forth in claim 20, wherein the total number of individual nodes each of which was programmed to serve as a repeater node is less than the total number of individual nodes in the network.

32. The wireless network as set forth in claim 20, wherein the network is a building system control network, and said central node comprises a building computer.

33. The wireless network as set forth in claim 26, wherein:

said individual nodes are organized into at least two separate groups of nodes each having a unique group address;

said first address table of each of said individual nodes further contains said group address of any group that node belongs to;

a selected subset of said individual nodes are programmed to serve as group repeater nodes for each said group; and

,

said second address table of each of said individual nodes further contains said group address of any group for which that node is programmed to serve as a group repeater.

34. The wireless network as set forth in claim 26, wherein:

the entire network has a global address;

said global address is stored in said first address table of each of said individual nodes; and

,

a selected subset of said individual nodes are programmed to serve as global repeaters for the entire network; and

,

storing said global address in said second address table of each of said global repeaters.

35. The wireless network as set forth in claim 20, wherein the network is an intelligent lighting system control network.

36. The wireless network as set forth in claim 20, wherein at least one of said individual nodes programmed to serve as a repeater node is programmed to serve as a repeater node for at least one other node in the network, but for less than all other nodes in the network.