Mesh network and piconet work system and method

• US 20050243765A1
• Filed: 07/11/2005
• Published: 11/03/2005
• Est. Priority Date: 07/25/2003
• Status: Abandoned Application

• Current Assignee: ASTER Wireless, Inc. (Iota Communications, Inc.)
• Original Assignee: ASTER Wireless, Inc. (Iota Communications, Inc.)
• Inventors: Schrader, Mark E., Frayer, Eric
• Application Number:
  US11/178,697
• Publication Number:
  US 20050243765A1
• Time in Patent Office: Days
• US Class Current: 370/328
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 72/00 Local resource management
• CPC Class Codes: H04W 74/002 Transmission of channel access control information
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method of distributed control of a wireless mesh network without knowledge of global topology. The method includes: a station joining the network with any current member by propagating the join-request, or two meshes merging using the steps of: one mesh joining the other as a whole and then re-synchronizing its timing. The method further includes: first, each station periodically transmits a beacon; second, in response to a beacon being no longer detected, a station transmitting a bitmap of stations that it can still receive; third, each station responds by adding stations that it can receive with all of the bitmaps received from other members, and retransmitting the updated bitmap; fourth, after time for all stations to respond, all stations base current membership on the bitmap. The method further includes: determining sharable time slots that will not interfere with neighbors or other slot sharers, using and then releasing those slots.

Claims

1. A method for managing a wireless network of member stations, comprising the steps of:

joining a station to a mesh network of stations;

adding together two networks of member stations;

removing a member station from the network;

moving a member station within a network; and

sharing time slots used by other members.

2. The method of claim 1 wherein the step of joining a station to a mesh network further comprises the steps of:

a) operating the unjoined station on the same frequency as the mesh network;

b) if the unjoined station is in a range of a mesh member station, detecting and decoding a beacon transmitted by a mesh member station;

c) the unjoined station transmitting a request-to-join command to the mesh member during its time slot;

d) one mesh member station authenticating the requested unjoined station;

e) the authenticating mesh member station granting permission for the unjoined station to join the mesh network at a specified join time, and propagating that information throughout the joining mesh network;

f) the unjoined station becoming a member of the mesh network at the specified join time, and updating network topology with the new member in the network.

3. The method of claim 1 wherein the step of adding together two networks of member stations further comprises the steps of:

a) a first detecting member station in a first network detecting a second detecting member station in a second network;

b) the second detecting member station detecting the first detecting member station;

c) the first and second detecting member stations exchanging overall network size parameters for comparison;

d) the detecting member station in the smaller network sending to the detecting member station in the larger network a request to join the larger network, which is acknowledged by the larger network;

e) the detecting member station in the larger network completing the authentication process and informing its other members that the smaller network will be joining the larger network at a specific future time;

f) the detecting member station in the smaller network also receiving the larger network join message and the specific future time, propagating to the other members of the smaller network the command to stop transmitting;

g) at the specific future time, the member stations in both networks expanding all of their bitmaps to the length in bits of the combined network and the network size to the value equal to the size of the combined network;

h) at the specific future time, detecting member station in the larger network propagating to its own members and the detecting member station of the smaller network that the merge is beginning and will end at the second future time;

i) at the specific future time, the member stations of the smaller network calculating new ID numbers by adding their current ID number to the size of the larger network;

j) at the specific future time, the detecting member station in the smaller network adopting the larger network'"'"'s cycle count and its current indicator of a change to the mesh membership or topology;

k) at the specific future time, the detecting member station in the larger network propagating a command to both the larger network members and the detecting member of the smaller network to begin the merge with the time of completion set to a second future time.

l) all members of the larger network and the detecting member of the smaller network beginning to propagate the combined total size to other member stations in the combined network;

m) each member of the smaller network restarting its transmissions in synchronization with the detecting member station in the smaller network using the size of the combined network, their updated ID numbers, and the expanded bitmaps of the combined network;

n) all member stations in the combined network propagating the combined network parameters in their transmissions;

o) at the second future time, the start of detecting a possible missing member station of the combined mesh to be removed from the expanded bitmaps of all remaining member stations at a third future time.

4. The method of claim 1 wherein the step of removing a member station from the network further comprises the steps of:

a) a first member station detecting that a neighboring member station is no longer present;

b) the first member station setting a timer to allow for propagation of the identification of the lost neighboring member station;

c) the first member station transmitting a loss of contact signal to notify the loss of the neighboring member station, an indication of current nearest neighbors, and the member(s) no longer present;

d) all member stations receiving the loss of contact signal, determining if the loss of contact signal is redundant and contains the same lost station ID as the one that has already been dropped from processing a previous loss of contact signal, and eliminating redundant loss of contact signals and excluding previously eliminated member stations;

e) each member station propagating the received loss of contact signal to its neighboring member stations, and signaling the identities of all the member stations it can hear pooled with the identities of all the member stations audible to the other member stations in the network as propagated by them;

f) for any listed member stations in the network not audible to any signaling member station, dropping all non-audible member stations from the network; and

all member stations adjusting their identities and remapping the network to eliminate any lost member stations and updating its current indicator of a change to the mesh membership or topology.

5. The method of claim 1 wherein the step of moving a member station within a network further comprises the steps of:

a) a member station detecting that a neighboring member station is no longer present, or a member station in the network detecting a previously unheard member, or both;

b) the detecting member station setting a propagation timer to allow for propagation of the identification of a change in nearest neighbor stations;

c) the detecting member station transmitting a loss of contact signal to notify the change in the neighboring member station, an indication of current nearest neighbors, and the member(s) no longer present, if any;

d) all member stations receiving the loss of contact signal, determining if the loss of contact signal is redundant and contains the same lost station ID as the one that has already been dropped from processing a previous loss of contact signal, and eliminating redundant loss of contact signals and excluding previously eliminated member stations;

e) each member station propagating the received loss of contact signal to its neighboring member stations, and signaling the identities of all the member stations it can hear pooled with the identities of all the member stations audible to the other member stations in the network as propagated by them;

f) when the propagation timer has timed out, for any listed member station in the network not audible to any signaling member station, dropping all non-audible member stations from the mesh network; and

all member stations adjusting their identities and remapping the network to eliminate any lost member;

g) when the propagation timer has timed out, for all listed member stations still audible by at least one other member station, no dropping of any member station from the mesh network;

h) for either dropping or not dropping member stations from the mesh network, updating the current indicator of a change to the mesh membership or topology.

6. The method of claim 2 wherein the step of adding together two networks of member stations further comprises the steps of:

a) an unjoined station detecting member stations of two mutually non-communicating meshes; and

b) the unjoined station using the method of claim 2 to join either of the non-communicating mesh networks, the smaller network being preferred.

9. The method of claim 4 wherein the step of removing a member station from the network further comprises the steps of:

e) one of the member stations stopping transmission of its beacon;

f) one of the remaining member stations detecting the stopping of transmission and updating its NNB;

g) the remaining member station within range of the absent member, transmitting in its own beacon, a nearest neighbor change MCmd (NNC) and a change effect cycle count (CEC) value equal to current BCC+NS−

N_NNB−

RP, where NS is the total number of member stations before any member went off-line and N_NNB is the number of member stations whose beacons are now heard by the remaining member stations, and the parameter BDBF=NNB, and the LBL list of member stations whose beacons are newly lost;

h) each member station that has not already transmitted an NNC, but has received an NNC in the beacon from any other member station with an identical lost beacon list (LBL), retransmitting (thus repeating) an NNC and the smallest CEC received from any master station in its own next beacon;

i) every member station that has received a beacon with an NNC transmitting in its next beacon an NNC with a Beacon Detect Bitmap Flag (BDBF) having non-zero values in locations representing member stations that can be heard by that member station;

j) every member station receiving the BDBFs, logically OR-ing all of the BDBFs together with its own NNB, to produce an ORed BDBFs with NNB, and storing and retransmitting in its next beacon the NNC with ORed BDBFs with NNB as its BDBF parameter; and

k) every member station receiving the NNC with the ORed BDBF, logically OR-ing that BDBF with its stored BDBF to produce an updated BDBF, and storing and transmitting the updated BDBF in the retransmitted NNC; and

repeating the steps of receiving, OR-ing, storing and transmitting until the cycle count BCC is equal to the value CEC;

l) the value of BCC=CEC being reached, and the BDBF containing one or more bits with the value zero, all member stations compressing all bitmaps to eliminate the positions represented by the ‘

0’

s in the BDBF, and reassigning the SIDs such that the remaining bit positions are assigned to the correct member stations;

m) if the value of BCC=CEC being reached and the BDBF containing only bits with the value ‘

1’

, making no changes to bitmaps or bitmap assignments.

n) each member station resuming beacon transmissions at the new beacon time specified by its modified SID.

10. The method of claim 1 wherein member stations compensate for delays in the propagation of time slot data, beacons, commands, and member station data by the steps of:

a) each member station transmitting a propagation bitmap with one bit for each member station corresponding to its station ID, and possibly transmitting an extended time parameter;

b) each station receiving the data with the propagation bitmap, setting the bit corresponding to its station ID, and propagating the data with the revised bitmap;

c) the original propagation time value being reached, each member station determining if there are any zeros remaining in the propagation bitmap;

d) a zero being present in the propagation bitmap, the station either taking no further action or terminating the operation;

e) or a zero being present in the propagation bitmap and the station continuing to propagate the command for an amount of time specified by the extended time parameter received with the propagation bitmap, and propagating a new extended time parameter;

f) a zero not being present in the propagation bitmap, the member station completing the required operation.

11. The method of claim 1 wherein any member station may be the controller of its own local area network (LAN) or personal area network (PAN).

7. A method for a member station to make use of unused time slots in a member station beacon cycle, comprising the steps of:

a) having each member station keep a map of neighbor stations that the member station can hear, and the stations that neighbors can hear (neighbors-of-neighbors);

b) a first member station selecting one or more slots not listed in the map as slots that it requests to share;

c) the first member station transmitting a map of selected slots to the other member stations in the network to notify the member stations of its desire to use the slots;

d) each member station receiving the map of desired slots, removing a time slot from the map if interference would take place when the first member station uses the time slot, and propagating the resulting map to the remainder of the network;

e) after propagation of the map to all mesh members, the map containing the granted time slots that may be used by the first member station to transmit data;

f) The first member station using one or more granted time slots to transmit data;

g) the first member station marking the time slot as no longer in use as a map of released time slots, and transmitting the map to the other member stations in the network to notify them of the release.

h) the neighbor stations of the first member station receiving the map of released time slots, propagating the map to all other member stations, and so on throughout the mesh network.

8. The method claimed in claim 7, further comprising the steps of:

a) any member station using a shared time slot and receiving the loss of contact signal, stopping the use of all shared time slots;

b) the propagation timer for the loss of contact signal timing out with dropouts being resolved, and for all member stations for desiring to use shared time slots, re-determining what time slots can be shared.

c) creating a new neighbor and neighbor-of-neighbor map.

d) propagating a new requested slot map to obtain a new map of sharable time slots;

e) using the time slots specified by the map of sharable time slots to send data;

f) releasing aforementioned timeslots when they are no longer needed.