Method for configuring and routing data within a wireless multihop network and a wireless network for implementing the same

• US 6,842,430 B1
• Filed: 10/16/1996
• Issued: 01/11/2005
• Est. Priority Date: 10/16/1996
• Status: Expired due to Term

• Current Assignee: Philips Lighting BV (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Melnik, George A.
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US08/735,276
• Time in Patent Office: 3,009 Days
• Field of Search: 370/351, 370/392, 370/254, 370/255, 370/256, 370/408, 370/409, 370/338, 370/328, 370/400, 370/310, 455/67.1, 340/825.5, 340/825.51, 340/825.44, 340/825.02
• US Class Current: 370/254
• 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: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 40/34 Modification of an existing route

Abstract

A method for configuring a wireless network comprised of a control node and a multiplicity of individual nodes includes the steps of logically organizing the network into a plurality of bands Bi, wherein each of the bands Bi includes a plurality of the individual nodes and is located a number i of hops away from the control node, where i=0 through N, and N≧1, and then assigning a logical address to each of the individual nodes, and storing the assigned logical addresses in the respective individual nodes. The assigned logical address for each individual node includes a first address portion which indicates the band Bi in which that individual node is located, and a second address portion that identifies that node relative to all other individual nodes located in the same band. The network is preferably a packet-hopping wireless network in which data is communicated by transferring data packets from node-to-node over a common RF channel. Each of the individual nodes is preferably programmed to perform the step of comparing its own logical address to a routing logical address contained in each packet which it receives, and to either discard, re-transmit, or process the packet based upon the results of the comparison. The routing logical address contained in a received packet contains the full routing information required to route the packet from a sending node to a destination node along a communication path prescribed by the routing logical address. The control node is programmed to control the routing of packets by inserting the routing logical address into each packet which it transmit, detecting any unsuccessfully transmitted packets, detecting a faulty node in the communication path prescribed by the routing logical address in response to detecting an unsuccessfully transmitted packet, and changing the routing logical address of the unsuccessfully transmitted packet to a new routing logical address which prescribes a new communication path which does not include the detected faulty node. Also disclosed are a wireless network and a network node which are designed to implement the foregoing network configuration and/or routing methods.

Claims

1. A method for configuring a wireless network comprised of a control node and a multiplicity of individual nodes, comprising the steps of:

logically organizing the network into a plurality of bands Bi, wherein each of the bands Bi includes a plurality of the individual nodes and is located a number i of hops away from the control node, where i=0 through N, and N≧

1;

assigning a logical address to each of the individual nodes, and storing the assigned logical addresses in the respective individual nodes; and

,

wherein the assigned logical address for each individual node includes a first address portion which indicates the band Bi in which that individual node is located, and a second address portion that identifies that node relative to all other individual nodes located in the same band;

wherein the network comprises a packet-hopping wireless network in which data is communicated by transferring data packets from node-to-node;

wherein each of the individual nodes is programmed to perform the step of comparing its own logical address to a routing logical address contained in each packet which it receives, and to either discard, re-transmit, or process the packet based upon the results of the comparison;

wherein the routing logical address contained in a received packet contains the full routing information required to route the packet from a sending node to a destination node along a communication path prescribed by the routing logical address; and

,

wherein each received packet includes;

a direction bit which indicates the direction which the received packet must travel to reach the destination node;

a first set of bits which includes a hops value which indicates a number N of hops required to transfer the received packet from the sending node to the destination node, and a number of hops count;

a second set of bits which includes the routing logical address; and

,

a third set of bits which includes processing instructions for the destination node.

2. The method as set forth in claim 1, further comprising the step of initializing the network in order to obtain nodal connectivity information.

3. The method as set forth in claim 2, wherein the step of logically organizing the network is performed by the control node on the basis of the nodal connectivity information obtained during the step of initializing the network.

4. The method as set forth in claim 1, wherein all data communications are carried out over a common RF channel.

5. The method as set forth in claim 1, wherein each of the individual nodes is programmed to perform the steps of:

incrementing the number of hops count if the received data packet is to be re-transmitted by that node and if the direction is a first direction; and

,

decrementing the number of hops count if the received data packet is to be re-transmitted by that node and if the direction is a second direction.

6. The method as set forth in claim 5, wherein:

the first direction is a downstream direction between the control node and the destination node; and

,

the second direction is an upstream direction between the destination node and the control node.

7. The method as set forth in claim 5, wherein the step of comparing performed by each of the individual nodes includes a first sub-step of comparing the first address portion of its logical address with the number of hops count contained in the received packet, and either discarding the received packet or proceeding with further sub-steps of the step of comparing, depending upon the result of the first comparing sub-step.

8. The method as set forth in claim 7, wherein the further sub-steps of the step of comparing performed by each of the individual nodes include:

a second sub-step of comparing the second address potion of its logical address with a corresponding address portion of the routing logical address contained in the received packet, and proceeding with a next sub-step of the step of comparing if a match is detected; and

,

a third sub-step of comparing the number of hops count with the hops value contained in the received packet, and either processing the received packet or re-transmitting the received packet, depending upon the result of the third sub-step of comparing.

9. The method as set forth in claim 8, wherein:

the routing logical address includes a number N+1 of address portions corresponding to respective bands between the sending node and the destination node; and

,

the corresponding address portion of the routing logical address which is used in the second sub-step of comparing is the address portion which corresponds to the band Bi identified in the first address portion of the individual node which is performing the second sub-step of comparing.

10. The method as set forth in claim 1, wherein the wireless network comprises a building system control network, and the control node comprises a building computer.

11. The method as set forth in claim 10, wherein the building system control network comprises an intelligent lighting control system.

12. A method for configuring a wireless network comprised of a control node and a multiplicity of individual nodes, comprising the steps of:

logically organizing the network into a plurality of bands Bi, wherein each of the bands Bi includes a plurality of the individual nodes and is located a number i of hops away from the control node, where i=0 through N, and N>

1;

assigning a logical address to each of the individual nodes, and storing the assigned logical addresses in the respective individual nodes; and

,

wherein the assigned logical address for each individual node includes a first address portion which indicates the band Bi in which that individual node is located, and a second address portion that identifies that node relative to all other individual nodes located in the same band;

wherein the network comprises a packet-hopping wireless network in which data is communicated by transferring data packets from node-to-node;

wherein each of the individual nodes is programmed to perform the step of comparing its own logical address to a routing logical address contained in each packet which it receives, and to either discard, re-transmit, or process the packet based upon the results of the comparison;

wherein the routing logical address contained in a received packet contains the full routing information required to route the packet from a sending node to a destination node along a communication path prescribed by the routing logical address; and

,

wherein the control node is programmed to control routing of packets by performing the steps of;

inserting the routing logical address into each packet which it transmits;

detecting any unsuccessfully transmitted packets;

detecting a faulty node in the communication path prescribed by the routing logical address in response to detecting an unsuccessfully transmitted packet; and

,

changing the routing logical address of the unsuccessfully transmitted packet to a new routing logical address which prescribes a new communication path which does not include the detecting faulty node.

13. A wireless network, comprising:

a control node;

a multiplicity of individual nodes logically organized into a plurality of bands Bi, wherein each of the bands Bi includes a plurality of the individual nodes and is located a number i of hops away from the control node, where i=0 through N, and N≧

1; and

,

wherein each individual node has a logical address which includes a first address portion which indicates the band Bi in which that individual node is located, and a second address portion that identifies that node relative to all other individual nodes located in the same band;

wherein the network comprises a packet-hopping wireless network in which data is communicated by transferring data packets from node-to-node;

wherein each of the individual nodes is programmed to perform the step of comparing its own logical address to a routing logical address contained in each packet which it receives, and to either discard, re-transmit, or process the packet based upon the results of the comparison;

wherein the routing logical address contained in a received packet contains the full routing information required to route the packet from a sending node to a destination node along a communication path prescribed by the routing logical address; and

,

wherein each received packet includes;

a direction bit which indicates the direction which the received packet must travel to reach the destination node;

a first set of bits which includes a hops value which indicates a number N of hops required to transfer the received packet from the sending node to the destination node, and a number of hops count;

a second set of bits which includes the routing logical address; and

,

a third set of bits which includes processing instructions for the destination node.

14. The network as set forth in claim 13, wherein control node is programmed to execute a network initialization procedure and to logically organize the network on the basis of nodal connectivity information obtained during the network initialization procedure.

15. The network as set forth in claim 13, wherein each of the individual nodes is programmed to increment the number of hops count if the received data packet is to be re-transmitted by that node and if the direction is a first direction, and to decrement the number of hops count if the received data packet is to be re-transmitted by that node and if the direction is a second direction.

16. The network as set forth claim 15, wherein:

the first direction is a downstream direction between the control node and the destination node; and

,

the second direction is an upstream direction between the destination node and the control node.

17. The network as set forth in claim 15, wherein the routing logical address includes a number N+1 of address portions corresponding to respective bands between the sending node and the destination node.

18. The network as set forth in claim 15, wherein the control node is programmed to control the routing of packets by:

inserting the routing logical address into each packet which it transmits;

detecting any unsuccessfully transmitted packets;

detecting a faulty node in the communication path prescribed by the routing logical address in response to detecting an unsuccessfully transmitted packet; and

,

changing the routing logical address of the unsuccessfully transmitted packet to a new routing logical address which prescribes a new communication path which does not include the detected faulty node.

19. The network as set forth in claim 18, wherein the network comprises a building system control network, and the control node comprises a building computer.

20. The network as set forth in claim 19, wherein the building system control network comprises an intelligent lighting control system.

21. A network node for use in a wireless network which includes a control node and a multiplicity of other network nodes, wherein all of the network nodes are logically organized into a plurality of bands Bi, and each of the bands Bi includes a plurality of network nodes and is located a number i of hops away from the control node, where i=0 through N, and N≧

1;

wherein the network node comprises;

a memory for storing a logical address of the network node; and

,

wherein the logical address includes a first address portion which indicates the band Bi in which the network node is located, and a second address portion that identifies the network node relative to all other network nodes located in the same band;

wherein the network comprises a packet-hopping wireless network in which data is communicated by transferring data packets from node-to-node;

wherein the network node is programmed to perform the step of comparing its own logical address to a routing logical address contained in each packet which it receives, and to either discard, re-transmit, or process the packet based upon the results of the comparison;

wherein the routing logical address contained in a received packet contains the full routing information required to route the packet from a sending node to a destination node along a communication path prescribed by the routing logical address; and

,

wherein each received packet includes;

a direction bit which indicates the direction which the received packet must travel to reach the destination node;

a first set of bits which includes a hops value which indicates a number N of hops required to transfer the received packet from the sending node to the destination node, and a number of hops count;

a second set of bits which includes the routing logical address; and

,

a third set of bits which includes processing instructions for the destination node.

22. The network node as set forth in claim 21, wherein the network node is programmed to increment the number of hops count if the received data packet is to be re-transmitted by that node and if the direction is a first direction, and to decrement the number of hops count if the received data packet is to be re-transmitted by that node and if the direction is a second direction.

23. The network node as set forth in claim 22, wherein:

the first direction is a downstream direction between the control node and the destination node; and

,

the second direction is an upstream direction between the destination node and the control node.

24. The network node as set forth in claim 22, wherein the routing logical address includes a number N+1 of address portions corresponding to respective bands between the sending node and the destination node.

25. The network node as set forth in claim 22, wherein the control node is programmed to control the routing of packets by:

inserting the routing logical address into each packet which it transmits;

detecting any unscuccessfully transmitted packets;

detecting a faulty node in the communication path prescribed by the routing logical address in response to detecting an unsuccessfully transmitted packet; and

,

changing the routing logical address of the unsuccessfully transmitted packet to a new routing logical address which prescribes a new communication path which does not include the detected faulty node.

26. The network node as set forth in claim 21, wherein the network comprises a building system control network, and the control node comprises a building computer.

27. The network node as set forth in claim 26, wherein the building system control network comprises an intelligent lighting control system.