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

• US 6,046,978 A
• Filed: 05/18/1999
• Issued: 04/04/2000
• Est. Priority Date: 10/16/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): Patel, Ajit
• Application Number:
  US09/313,598
• Time in Patent Office: 322 Days
• Field of Search: 370/216, 370/217, 370/218-220, 370/221, 370/225, 370/227, 370/228, 370/254, 370/389, 370/392, 370/396, 370/397, 370/409, 714/1, 714/2, 714/3, 714/4, 371/32, 371/33
• US Class Current: 370/221
• 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 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. 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 routing packets in a wireless network which includes a control node and a multiplicity of individual nodes, comprising the steps of:

inserting a routing logical address into each packet which is transmitted between a sending node and a destination node, wherein the routing logical address contains the full routing information required to route the packet from the sending node to the destination node along a communication path prescribed by the routing logical address;

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.

2. The method as set forth in claim 1, wherein each of the individual nodes has a logical address and is programmed to perform the step of comparing its own logical address to the routing logical address contained in each packet which it receives, and to either discard, re-transmit, or process the received packet based upon the results of the comparison.

3. The method as set forth in claim 2, wherein the network is 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.

4. The method as set forth in claim 3, wherein the logical address of each of the individual nodes 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.

5. The method as set forth in claim 4, 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.

6. The method as set forth in claim 5, 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.

7. The method as set forth in claim 6, 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.

8. The method as set forth in claim 6, 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.

9. The method as set forth in claim 8, 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 portion 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.

10. The method as set forth in claim 9, 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.

11. 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.

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