Probing method for a multi-station network

• US 7,590,068 B2
• Filed: 06/24/2004
• Issued: 09/15/2009
• Est. Priority Date: 12/19/2003
• Status: Expired due to Fees

• Current Assignee: Iwics Incorporated
• Original Assignee: Iwics Incorporated
• Inventors: Rodman, Paul Jonathan, Larsen, James David
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): Kavleski; Ryan C
• Application Number:
  US10/876,166
• Publication Number:
  US 20050135270A1
• Time in Patent Office: 1,909 Days
• Field of Search: 370/238, 370/252, 370/400, 370/235, 370/437, 709/221, 709/238, 709/249, 709/232, 709/242
• US Class Current: 370/238
• CPC Class Codes: H04L 43/50 Testing arrangements
• 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/26 Route discovery packet
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

The invention relates to a method of operating a communication network, the network comprising a plurality of stations which are able to transmit data to and receive data from one another. The method comprises defining a first probing channel for the transmission of probe signals to other stations. Other stations which receive the first probe signals from a probing station indicate to the probing station their availability as destination or intermediate stations. A neighbor table comprising details of these other available stations is maintained at each station. Also, second probe signals are sent and received from stations in the neighbor table and a gradient table comprising data related to the cost of communicating with each neighbor station is maintained at each station, thereby to allow each station to select a predetermined number of intermediate stations for onward transmission of data from an originating station to a destination station at minimum cost.

Claims

1. A communication network comprising a plurality of stations each able to transmit and receive data so that the network can transmit a message comprising a plurality of data packets from an originating station to a destination station via at least one opportunistically selected intermediate station, wherein each station is configured to:

select, according to a predetermined criteria, a probing channel for the transmission of probe signals to other stations;

transmit neighbor gathering probe signals of the selected probing channel to other stations which receive the transmitted neighbor gathering probe signals from a probing station responding directly or indirectly to indicate to the probing station availability of the other stations as the destination station or as neighbor stations;

maintain a neighbor table comprising details of other available stations identified using the transmitted neighbor gathering probe signals;

transmit, when needing to send data to the destination station, gradient gathering probe signals to, and to receive gradient gathering probe signals from, stations in the neighbor table to gather gradient data indicative of a cost of connectivity to said destination station (C_ND) from the stations in the neighbor table and from the originating station needing to send data to the destination station; and

maintain, as needed, a gradient table comprising data related to a cost of communicating with each neighbor station from each station (C_N), with the destination station from each station, and with the destination station from each of the stations represented in each station'"'"'s neighbor table;

allow each client station to select an intermediate station, from the stations in its neighbor table having lower costs of communicating to said destination station than each client station, for an opportunistic onward transmission of data from the originating station to the destination station when a minimum sum of all costs Σ

(C_N +C_ND)_min of communicating to the destination station from the originating station does not exceed a maximum cost (maxCost) or does not exceed a current best cost to destination (C_D) or does not exceed a frozen cost (C_DF), wherein the C_DF comprises the C_D previously maintained in the gradient table; and

prevent each station from opportunistically transmitting data from the originating station to the destination station when Σ

(C_N +C_ND)_min>

C_D and/or maxCost>

C_D and/or C_DF>

C_D.

2. The communication network of claim 1 wherein each station is configured to establish a cost to destination test value for each gradient table entry for a predetermined period of time during which stations in the gradient table cannot be replaced by other stations with a higher cost to destination value.

3. The communication network of claim 2 wherein the predetermined period of time is a multiple of the interval between gradient gathering probe signals, calculated to be sufficient for all stations in the gradient table to update their cost to destination values.

4. The communication network of claim 1 wherein each station is further configured to include, in the details of other available stations identified by the neighbor gathering step, a path loss and power required to reach the other available stations.

5. The communication network of claim 4 wherein each station further includes a transmitter configured to transmit gradient gathering probe signals from each station only while the neighbor table of each station contains entries.

6. The communication network of claim 1 wherein each station includes a controller configured to calculate, for each station in the neighbor table, a cost to destination value for the cost of transmitting a message from a given originating station to a given destination station via each such station in the neighbor table.

7. The communication network of claim 1 wherein the network is configured to maintain a calculated cost to destination value for each station constant for a period during which other stations can update their own cost to destination values, to prevent stations using obsolete cost to destination values of other stations in their own calculations.

8. The communication network of claim 1 wherein each station includes a memory configured to maintain a temporary record of its own cost to destination value.