Electrical computers and digital processing systems: multicomput – Computer-to-computer session/connection establishing
Reexamination Certificate
2002-09-04
2003-12-09
Harrell, Robert B. (Department: 2142)
Electrical computers and digital processing systems: multicomput
Computer-to-computer session/connection establishing
Reexamination Certificate
active
06662229
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to an apparatus, program and method for network communications. More particularly, the present invention relates to a cluster head resignation procedure that minimizes data loss in a communications network having member stations arranged in clusters, with each cluster having a head station.
2. Related Art
Communications networks can be formed by arranging a plurality of mobile communications stations into a hierarchical configuration including groups (e.g., “clusters”), with each group having a group or cluster head (e.g., “cluster gateway”). A cluster head represents affiliated cluster members to the network. Cluster head stations communicate with each other to form a network backbone, and cluster member stations relay messages to the network through affiliated cluster heads. In mobile systems, cluster members move into and out of clusters depending on their physical location and radio connectivity. Depending on mobility changes of stations in a mobile network, new clusters form and cluster heads emerge as stations move around.
Wireless communications in a mobile environment has a unique problem in that network topology is constantly changing. As will be appreciated, grouping member stations into clusters addresses this problem since communication nodes outside of a cluster do not need to know about changes of topology within a cluster. Thus, a large amount of changing topology information does not need to be flooded through the network.
An example of a mobile communications network is shown in
FIG. 2
a
. Areas
1
a
,
1
b
and
1
c
represent individual clusters in
FIG. 2
a
. In
FIG. 2
a
, as in the other relevant figures, a double-circle indicates a Cluster Head (“CH”), whereas a single circle indicates a Cluster Member (“CM”). In the
FIG. 2
a
example, CM
2
and CM
3
are affiliated with a cluster headed by CH
1
, and CM
6
and CM
7
are affiliated with a cluster headed by CH
5
.
Another example of a mobile communications network is disclosed in U.S. Pat. No. 5,850,592, issued to S. Ramanathan on Dec. 15, 1998, and assigned to the same assignee. The U.S. Pat. No. 5,850,592 patent discloses a method for a plurality of mobile stations to automatically organize themselves into a hierarchical network, in which some of the stations operate as message gateways (e.g., cluster heads) for a cluster of mobile stations. Initially, mobile stations search for available cluster heads and initiate an affiliation procedure to establish themselves as cluster members. If the affiliation procedure is successful, a mobile station operates as a cluster member. A mobile station monitors its communication link with a cluster head and seeks to reestablish a link when it is compromised or severed. During this reaffiliation, a mobile station may affiliate with a different cluster head if such cluster head is within range. Otherwise, a mobile station promotes itself to operate as a cluster head.
In the arrangement of the U.S. Pat. No. 5,850,592 patent, a plurality of mobile stations is employed, with each station operating in at least two basic modes. In the first mode, the mobile station serves as a message gateway (e.g., a “cluster head” or “network access point”) for a cluster of other member stations (e.g., “non-gateway” stations). The second mode allows the mobile station to operate as a non-gateway (or “cluster member”) station. Each mobile station determines which out of the two modes to operate in, as discussed above.
The mobile stations disclosed in the U.S. Pat. No. 5,850,592 patent can operate at two different power levels. When there are no other available cluster heads, the mobile station operates as a cluster head, and transmits at a relatively high power level. The cluster head transmits at the relatively high power level to communicate with other cluster head stations and to typically provide longer distance network links. Although the cluster head communicates at a higher power level with other cluster heads, the cluster head can still communicate with its cluster members using a relatively lower power level. A cluster head can also periodically broadcast a signal to establish the station's presence and its availability to operate as a cluster head.
The cluster head stations disclosed in the U.S. Pat. No. 5,850,592 patent periodically test their proximity conditions to other cluster head stations, e.g., by signal strength measurements or using data available through the cluster head stations exchanging messages. If the tests indicate that the proximity conditions are exceeded, e.g., that the particular station's operation as a gateway is possibly redundant and/or unnecessary, the station executes a resignation procedure. Before terminating operation as a cluster head, the cluster head broadcasts a termination request and waits for a predetermined time to see if all affiliated cluster members accept the request. Each linked or neighboring cluster head station also receives a resignation request from the resigning cluster head. The receiving cluster head neighbor checks to see if the resigning station is an articulation point. For example, as shown in
FIG. 2
b
, CH
5
is an articulation point since it is the only cluster head linking CH
1
and CH
4
. If, on the other hand, as shown in
FIG. 2
a
, CH
1
and CH
4
are linked independently of CH
5
, CH
5
is not an articulation point for CH
1
or CH
4
. If the resigning cluster head is an articulation point, the receiving cluster head neighbor does not send a confirmation message, essentially blocking the resignation of the cluster head.
This process may not be entirely satisfactory in all settings because the process requires communication between the resigning node and its neighbors as part of the process of attempting to resign. In many cases such communication is not necessary because the resigning cluster head may make this determination itself (e.g., that it is an n-connectivity point) and block its own resignation for that reason. In general, an n-connectivity point is a member of at least one set of ‘n’ nodes which—if that set were deleted from the network—would cause the network to fall into two or more distinct, unconnected portions (e.g., partitions). Thus an “articulation point” is a 1-connectivity point. If a node is a 2-connectivity point, then removal of that node and some other node would partition the network, and so forth. As will be appreciated, it is desirable to have networks remain connected. Hence, in general, it is also desirable to have at least ‘n’ nodes to connect the various portions of the network, where n>1 for redundancy.
Returning to the resignation procedure discussed in the U.S. Pat. No. 5,850,592 patent, if a resignation is successful, and after a random amount of time has expired, the resigning mobile station must reestablish itself as a cluster member. This resignation process is a “break-before-make” approach; that is, the resigning cluster head actually loses network connectivity (as a cluster head) before it attempts to regain network connectivity (as a cluster member). This type of approach is not always satisfactory as it is usually highly desirable or even essential for every node in a network to have network connectivity at all times.
Other implementations of clustering methods do not even employ resignation procedures. In these cases, a network eventually has so many cluster heads that routing overhead overwhelms the limited available bandwidth. This routing overhead may produce a communication scheme that functions as if there was no attempt to use clusters to reduce network topology traffic.
These types of problems are not adequately addressed in the art. Thus, there is a need for a flexible communications station in a communications network to reduce routing overhead by determining when and how a cluster and a cluster head are no longer needed in the network. There is also a need for a communications node that will not resign if it is a critical node. There is another need to pro
Elliott Brig Barnum
Manning Keith W.
Passman William S.
Weinstein Joseph J.
Zavgren John R.
BBNT Solutions LLC
Harrell Robert B.
Le Hiem C.
Suchyta Leonard Charles
Weixel James K.
LandOfFree
Cluster head resignation to improve routing in mobile... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cluster head resignation to improve routing in mobile..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cluster head resignation to improve routing in mobile... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3122198