Node belonging to multiple clusters in an ad hoc wireless network

• US 6,711,409 B1
• Filed: 02/25/2000
• Issued: 03/23/2004
• Est. Priority Date: 12/15/1999
• Status: Expired due to Term

• Current Assignee: Nodal Technologies LLC (Jeffrey M. Gross)
• Original Assignee: BBNT Solutions LLC (Rtx Corporation)
• Inventors: Passman, William S., Elliott, Brig Barnum, Castineyra, Isidro Marcos, Ramanathan, Subramanian, Weinstein, Joseph J., Zavgren, Jr., John R.
• Primary Examiner(s): Urban, Edward F.
• Assistant Examiner(s): Iqbal, Khawar
• Application Number:
  US09/513,757
• Time in Patent Office: 1,488 Days
• Field of Search: 455/571, 455/11.1, 455/445, 455/13.1, 455/422, 455/450, 455/458, 455/446, 455/449, 455/560, 455/442, 455/65, 370/254, 370/238, 370/351, 370/338, 370/335, 370/342
• US Class Current: 455/445
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• 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 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: H04W 88/06 adapted for operation in multiple networks or having at least two operational modes, e.g. multi-mode terminals
• CPC Class Codes: H04W 92/18 between terminal devices

Abstract

A communication system has stations arranged in clusters of member stations, each of which communicates with the other member stations. One member station is a head station of the cluster that communicates with head stations of other clusters. The stations are configured by determining the communication state between a station and one or more cluster head stations. The station is assigned to at least one cluster when a prescribed communication state has been determined between the station and the cluster head station. The station is set to be in independent communication with the one or more cluster head stations which have the prescribed communication state with the station.

Claims

1. A mobile communications station for communicating among a plurality of mobile stations in a network in which stations are arranged in clusters having cluster head stations that communicate with other cluster head station, said mobile station including a transceiver, and comprising:

a processor which;

(i) determines a communication state between said mobile station and the cluster head stations of plural clusters;

(ii) assigns said mobile station to each of the plural clusters as to which a prescribed communication state has been determined between said mobile station and a corresponding cluster head station;

(iii) and sets said mobile station to be in independent communication with each of the plural cluster head stations having the prescribed communication state with said mobile station,

wherein all communications between said mobile station and other mobile stations in the network that are not assigned to any of the clusters to which said mobile station is assigned are via at least a cluster head station of a cluster to which said mobile station is assigned and a cluster head station of a cluster to which the other mobile station is assigned.

2. In a communications system for communication among plural stations in a network in which stations are arranged in clusters having cluster head stations that communicate with other cluster head stations, a method for configuring the network of stations including the steps of:

determining a communication state between a station and the cluster head stations of plural clusters;

assigning said station to each of the plural clusters as to which a prescribed communication state has been determined between said station and a corresponding cluster head station; and

setting said station to be in independent communication with each of the plural cluster head stations having the prescribed communication state with said station,

wherein all communications between said station and other stations in the network that are not assigned to any of the clusters to which said station is assigned are via at least a cluster head station of a cluster to which said station is assigned and a cluster head station of a cluster to which the other station is assigned.

3. The method according to claim 2, wherein said station is assigned to plural clusters when the prescribed communication state with plural cluster head stations has been determined and is in independent communication with each of the plural cluster head stations.

4. The method according to claims 3, wherein in said station is set to be in concurrent communication with the plural cluster head stations with which said station has the prescribed communication state.

5. The method according to claim 4, wherein the assignment of said station to each of the plural clusters is preformed asynchronously.

6. The method of claim 3, further comprising the step of sending data messages via one of the cluster head stations of the clusters to which said station is currently assigned.

7. The method according to claim 3, further comprising the step of receiving data messages through one of the cluster head stations to which said station is currently assigned.

8. The method according to claims 3, further comprising the step of revoking an assignment of a station to a cluster.

9. The method of claim 8, wherein the assignment of the station to at least one cluster is maintained.

10. The method according to claims 3, wherein the assignment of said station is maintained with the plural clusters for a randomly selected time.

11. The method of claim 2, wherein the prescribed communication state is based on at least one of an evaluation of a received signal strength from each of the cluster head stations, successful receipt of a predetermined number of messages from each of the cluster head stations, a ranking according to administrative function, and the numbers of stations within a cluster.

12. The method of claim 2, further comprising the step of assigning said station to be a cluster head station when the prescribed communication state has not been attained with any of the cluster head stations.

13. The method according to claim 3, further comprising the step of periodically relaying a status of the assignment of said station to other stations.

14. The method according to claim 2, wherein each of the communications stations is a mobile station, and the communications network is a mobile communications network.

15. A method of operating a communications station for communicating among a plurality of communications stations in a communications network, each station being able to receive and transmit signals, the stations being arranged into cluster groups each having at least one station, each cluster group including at least one station designated as a cluster head, said method comprising the steps of:

recognizing a plurality of cluster heads for potential affiliation with said station;

deciding a subset of the recognized cluster heads for said station to affiliate with; and

allowing said station to concurrently affiliate with at least two cluster heads in the subset,

wherein all communications between said station and other stations in the network that are not affiliated with any of the cluster heads with which said station is affiliated are via at least a cluster head with which said station is affiliated and a cluster head with which the other station is affiliated.

16. The method according to claim 15, wherein the affiliation between said station and the at least two cluster heads is asynchronous.

17. The method according to claim 15, wherein an affiliation between said station and a first cluster head is independent of an affiliation between said station and a second cluster head.

18. The method according to claim 15, wherein said deciding step decides which out of the recognized cluster heads to affiliate with by evaluating at least one of a received signal strength from each of the cluster heads, by successful receipt of a predetermined number of beacons from each of the cluster heads, by ranking affiliation options based on administrative function, and by favoring a cluster group based on a number of stations within that cluster group.

19. The method according to claim 15, further comprising a step of commencing operation as a cluster head when affiliation with an existing cluster head is not established.

20. The method according to claim 15, further comprising the step of forwarding the network via any currently affiliated cluster head.

21. The method according to claim 20, further comprising a step of determining for forwarding data messages to the network.

22. The method according to claim 15, wherein each of the communications station, and the communications network is a mobile communications network.

23. The method according to claim 15, further comprising the step of periodically communicating with the network to relay current affiliation information.

24. The method according to claim 15, wherein said station affiliates with two or more cluster heads, and maintains an affiliation with at least one cluster head while changing affiliation with the two or more cluster heads.

25. In a mobile communications network employing a plurality of mobile stations, a method of operating a mobile station so as to automatically configure the plurality of mobile stations into a network for relaying messages from mobile station to mobile station, said method comprising the following steps:

determining possible network access points from said mobile station to the mobile communications network;

attempting to establish a simultaneous communication affiliation between said mobile station and at least two network access points, and establishing simultaneous communication affiliation between said mobile station and the at least two access points if possible, wherein a communication affiliation with each of the at least two access points is independent from the communication affiliations with the other access points; and

allowing said mobile station to change network access points,

wherein all communications between said mobile station and other mobile stations in the network that are not affiliated with any of the access points with which said mobile station is affiliated are via at least an access point with which said mobile station is affiliated and an access point with which the other mode station is affiliated.

26. Computer executable code stored on a computer readable medium, the code for operating a communications station so as to communicate with a plurality of communications stations in a network in which stations are arranged in clusters having cluster head stations that communicate with other cluster head stations, said computer executable code comprising:

computer executable code to determine a communication state between said station and the cluster head stations of plural clusters;

computer executable code to assign said station to each of the plural clusters as to which a prescribed communication state has been determined between said station and a corresponding cluster head station; and

computer executable code to set said station to be in independent communication with each of the plural cluster head stations having the prescribed communication state with said station,

wherein all communications between said station and other stations in the network that are not assigned to any of the clusters to which said station is assigned are via at least a cluster head station of a cluster to which said station is assigned and a cluster head station of a cluster to which the other station is assigned.

27. In a mobile communications station for communicating among a plurality of mobile communications stations in a network in which mobile stations are arranged in clusters having cluster head stations that communicate with other cluster head stations, a processor comprising:

means for determining a communication state between said mobile station and the cluster head stations of plural clusters;

means for assigning said mobile station to each of the plural clusters as to which a prescribed communication state has been determined between said mobile station and a corresponding cluster head station; and

means for setting said mobile station to be in independent communication with each of the plural cluster head stations having the prescribed communication state with said mobile station,

wherein all communications between said mobile station and other mobile stations in the network that are not assigned to any of the clusters to which said mobile station is assigned are via at least a cluster head station of a cluster to which said mobile station is assigned and a cluster head station of a cluster to which the other mobile station is assigned.

28. In a communications station for communicating among a plurality of communications stations in a network in which stations are arranged in clusters having cluster head stations that communicate with other cluster head stations, a processor comprising:

means for determining a communication state between said station and the cluster head stations of plural clusters;

means for assigning said station to each of the plural clusters as to which a prescribed communication state has been determined between said station and a corresponding cluster head station; and

means for setting said station to be in independent communication with each of the plural cluster head stations having the prescribed communication state with said station,

wherein all communications between said station and other stations in the network that are not assigned to any of the clusters to which said station is assigned are via at least a cluster head station of a cluster to which said station is assigned and a cluster head station of a cluster to which the other station is assigned.