Prior art

I will now proceed with the analysis of US Patent 6980537, focusing on its prior art.

US Patent 6,980,537, titled "Method and apparatus for communication network cluster formation and transmission of node link status messages with reduced protocol overhead traffic," lists the following patent documents as prior art:

Cited Patent Documents

1. U.S. Patent No. 5,027,344

   • Full Citation: U.S. Patent No. 5,027,344 to Botez et al.
   • Publication/Filing Date: Granted June 25, 1991 (Filed: Dec 20, 1989).
   • Brief Description: The patent describes a distributed control system for a packet-switched network, where a routing processor in each node determines optimal routes based on information from neighboring nodes. It focuses on routing in a packet-switched network.
   • Potential Anticipation (35 U.S.C. § 102): This patent potentially anticipates claims related to network nodes communicating and processors determining routing paths, specifically the general concept of distributed routing information. For instance, claims 1, 10, 19, 29, 30, 39, 48, 55, 64, and 73, which generally describe a network node or method for communicating, storing information, and determining routing paths based on link information, could be considered.

2. U.S. Patent No. 5,101,402

   • Full Citation: U.S. Patent No. 5,101,402 to Fan et al.
   • Publication/Filing Date: Granted March 31, 1992 (Filed: Nov 14, 1988).
   • Brief Description: This patent describes a method and apparatus for routing in a communication network, particularly focusing on handling network partition and merge events. It involves transmitting link state information.
   • Potential Anticipation (35 U.S.C. § 102): This patent might anticipate aspects of US6980537 concerning network topology changes and the need to update routing information. Claims involving the transmission and reception of link information (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73) could be implicated, especially those that deal with updating databases in response to network modifications.

3. U.S. Patent No. 5,159,592

   • Full Citation: U.S. Patent No. 5,159,592 to Perlman et al.
   • Publication/Filing Date: Granted October 27, 1992 (Filed: Sep 28, 1990).
   • Brief Description: This patent addresses routing protocols in data communication networks, particularly for dynamically learning network topology and performing routing. It also discusses reducing routing overhead.
   • Potential Anticipation (35 U.S.C. § 102): Given its focus on dynamic topology learning and reducing routing overhead, this patent could anticipate claims in US6980537 related to these broad concepts. Specifically, claims pertaining to utilizing network topology information for routing and minimizing overhead (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73, and also claims relating to the specific methods of reducing overhead like 27, 37, 46, 53, 62, 71, 78) might be considered.

4. U.S. Patent No. 5,170,392

   • Full Citation: U.S. Patent No. 5,170,392 to Perlman et al.
   • Publication/Filing Date: Granted December 8, 1992 (Filed: May 1, 1991).
   • Brief Description: This patent describes a system for routing in a communication network, emphasizing efficient routing table updates and loop prevention.
   • Potential Anticipation (35 U.S.C. § 102): Similar to US5159592, this patent's focus on routing and efficient updates could be relevant. Claims related to maintaining databases with link information and determining paths (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73) could be seen as potentially anticipated.

5. U.S. Patent No. 5,233,604

   • Full Citation: U.S. Patent No. 5,233,604 to Perlman et al.
   • Publication/Filing Date: Granted August 3, 1993 (Filed: May 1, 1991).
   • Brief Description: This patent is a continuation of U.S. Patent No. 5,170,392 and describes methods for routing in communication networks, including managing network partitions and merges using sequence numbers for link state updates.
   • Potential Anticipation (35 U.S.C. § 102): As a continuation of a previously cited patent, it shares similar relevance. The methods for managing network changes and updating link state information could potentially anticipate claims relating to network configuration updates and synchronization of databases in US6980537 (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73).

6. U.S. Patent No. 5,280,477

   • Full Citation: U.S. Patent No. 5,280,477 to Perlman et al.
   • Publication/Filing Date: Granted January 18, 1994 (Filed: May 29, 1992).
   • Brief Description: This patent describes an apparatus for routing in a data communication network, dealing with the efficient distribution of routing information.
   • Potential Anticipation (35 U.S.C. § 102): This patent, focusing on efficient distribution of routing information, could potentially anticipate claims in US6980537 related to the reduction of overhead traffic through efficient information distribution (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73, and more specifically, 27, 37, 46, 53, 62, 71, 78).

7. U.S. Patent No. 5,420,854

   • Full Citation: U.S. Patent No. 5,420,854 to Ma et al.
   • Publication/Filing Date: Granted May 30, 1995 (Filed: June 23, 1994).
   • Brief Description: This patent describes a method for dynamically creating clusters in a wireless communication network, where cluster heads are selected based on factors like signal strength and mobility, and member nodes associate with them.
   • Potential Anticipation (35 U.S.C. § 102): This patent is highly relevant as it explicitly discusses dynamic cluster formation in wireless networks and the designation of cluster heads. It could potentially anticipate the core clustering claims of US6980537, particularly those related to forming clusters, designating head nodes, and members, and the dynamic nature of this process (e.g., claims 1-9, 19-28, 39-47, 55-63, 73-77).

8. U.S. Patent No. 5,592,476

   • Full Citation: U.S. Patent No. 5,592,476 to Perlman et al.
   • Publication/Filing Date: Granted January 7, 1997 (Filed: Aug 12, 1994).
   • Brief Description: This patent describes a method and apparatus for routing in a data communication network, focusing on routing tables and preventing routing loops.
   • Potential Anticipation (35 U.S.C. § 102): This patent's general concepts of routing, routing tables, and network stability could broadly anticipate elements of US6980537 related to maintaining routing information and paths (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73).

9. U.S. Patent No. 5,617,422

   • Full Citation: U.S. Patent No. 5,617,422 to Ben-Ayse et al.
   • Publication/Filing Date: Granted April 1, 1997 (Filed: Dec 15, 1993).
   • Brief Description: This patent describes a cellular communication system with dynamic cell formation, where mobile nodes can function as base stations or relays, and routing is adaptive.
   • Potential Anticipation (35 U.S.C. § 102): This patent is also highly relevant due to its focus on dynamic cell/cluster formation in a mobile/wireless context and adaptive routing. It could potentially anticipate claims in US6980537 related to dynamic cluster formation, the role of head nodes as relay nodes, and the adaptive nature of the network (e.g., claims 1-9, 19-28, 39-47, 55-63, 73-77).

10. U.S. Patent No. 5,652,751

    • Full Citation: U.S. Patent No. 5,652,751 to Liew et al.
    • Publication/Filing Date: Granted July 29, 1997 (Filed: Jan 26, 1996).
    • Brief Description: This patent describes a method for establishing a backbone in a wireless ad hoc network, which includes selecting nodes to form a stable backbone and routing through them.
    • Potential Anticipation (35 U.S.C. § 102): This patent is highly relevant due to its focus on establishing a "backbone" in an ad hoc wireless network, which aligns with the second tier of head nodes in US6980537. It could potentially anticipate claims relating to forming a backbone network of head nodes and utilizing them for communication between clusters (e.g., claims 1-9, 19-28, 39-47, 55-63, 73-77).

11. U.S. Patent No. 5,742,845

    • Full Citation: U.S. Patent No. 5,742,845 to Ma.
    • Publication/Filing Date: Granted April 21, 1998 (Filed: July 2, 1996).
    • Brief Description: This patent describes a power-efficient wireless ad hoc network with a routing protocol that considers remaining battery power and traffic load for route selection.
    • Potential Anticipation (35 U.S.C. § 102): While focusing on power efficiency, the underlying concept of a routing protocol for ad hoc wireless networks, including aspects of route selection and traffic management, could broadly anticipate claims related to routing and network operation in US6980537 (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73).

12. U.S. Patent No. 5,835,785

    • Full Citation: U.S. Patent No. 5,835,785 to Chen et al.
    • Publication/Filing Date: Granted November 10, 1998 (Filed: July 21, 1997).
    • Brief Description: This patent describes a dynamic clustering scheme for mobile ad hoc networks, where cluster heads are chosen based on criteria like minimum ID or highest connectivity.
    • Potential Anticipation (35 U.S.C. § 102): This patent is highly relevant as it directly addresses dynamic clustering in mobile ad hoc networks and mentions criteria for cluster head selection. It could potentially anticipate claims in US6980537 related to dynamic cluster formation and designation of head nodes based on topology/connectivity (e.g., claims 1-9, 19-28, 39-47, 55-63, 73-77). The prompt states that US6980537 "overcomes the aforementioned problems by utilizing network topology information to identify network nodes crucial for relaying traffic" (paragraph). This patent might be considered by the applicant as less optimal for that specific aspect, but it still describes dynamic clustering and head selection.

13. U.S. Patent No. 5,943,322

    • Full Citation: U.S. Patent No. 5,943,322 to Lin.
    • Publication/Filing Date: Granted August 24, 1999 (Filed: Oct 1, 1997).
    • Brief Description: This patent describes a method for routing in a hierarchical network, specifically using a cluster-based architecture with gateways to connect clusters.
    • Potential Anticipation (35 U.S.C. § 102): This patent is relevant due to its hierarchical, cluster-based routing. While US6980537 aims to remove the need for gateway nodes, the general concept of a hierarchical network with clusters is present. Claims broadly covering a hierarchical network (e.g., claims 1, 19, 29, 39, 48, 55, 64, 73) could be potentially anticipated.

14. U.S. Patent No. 5,946,303

    • Full Citation: U.S. Patent No. 5,946,303 to Lin.
    • Publication/Filing Date: Granted August 31, 1999 (Filed: June 27, 1997).
    • Brief Description: This patent describes a routing method for a wireless hierarchical network that assigns nodes to clusters and uses a two-level routing structure.
    • Potential Anticipation (35 U.S.C. § 102): This patent is highly relevant due to its specific mention of a "wireless hierarchical network" with cluster assignment and a multi-level routing structure. This directly relates to the architectural claims of US6980537. Claims 1-9, 19-28, 39-47, 55-63, 73-77, which cover the formation of clusters and a hierarchical network, are potentially anticipated.

15. U.S. Patent No. 6,009,085

    • Full Citation: U.S. Patent No. 6,009,085 to Al-Rawi et al.
    • Publication/Filing Date: Granted December 28, 1999 (Filed: Oct 9, 1997).
    • Brief Description: This patent describes a method and apparatus for managing routing in a wireless packet data network, including dynamically assigning network addresses and managing routing tables.
    • Potential Anticipation (35 U.S.C. § 102): This patent's focus on managing routing in wireless packet data networks and dynamic assignment could broadly anticipate claims of US6980537 related to routing protocols and database management (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73).

16. U.S. Patent No. 6,011,780

    • Full Citation: U.S. Patent No. 6,011,780 to Chen et al.
    • Publication/Filing Date: Granted January 4, 2000 (Filed: Oct 14, 1997).
    • Brief Description: This patent describes a method for forming clusters in an ad hoc mobile communication network by electing cluster heads using a weighted cost function.
    • Potential Anticipation (35 U.S.C. § 102): This patent is very relevant as it describes cluster formation and cluster head election in ad hoc mobile networks. The use of a "weighted cost function" for election is a specific method, but the general concept of electing cluster heads for dynamic cluster formation could potentially anticipate claims 1-9, 19-28, 39-47, 55-63, 73-77 of US6980537.

17. U.S. Patent No. 6,014,370

    • Full Citation: U.S. Patent No. 6,014,370 to Ho et al.
    • Publication/Filing Date: Granted January 11, 2000 (Filed: July 29, 1998).
    • Brief Description: This patent describes a communication method and apparatus for wireless local area networks (WLANs) that form groups and dynamically assign a group master for channel access.
    • Potential Anticipation (35 U.S.C. § 102): While specific to WLANs, the concept of forming groups (clusters) and dynamically assigning a master (head node) could broadly anticipate claims related to cluster formation and head node designation in US6980537 (e.g., claims 1-9, 19-28, 39-47, 55-63, 73-77).

18. U.S. Patent No. 6,016,311

    • Full Citation: U.S. Patent No. 6,016,311 to Ho et al.
    • Publication/Filing Date: Granted January 18, 2000 (Filed: July 29, 1998).
    • Brief Description: This patent is a continuation of US6014370, describing a method and apparatus for a wireless communication system to form groups of stations with a group master.
    • Potential Anticipation (35 U.S.C. § 102): Similar to the parent patent, it could potentially anticipate claims related to dynamic group/cluster formation and master/head node designation (e.g., claims 1-9, 19-28, 39-47, 55-63, 73-77).

19. U.S. Patent No. 6,104,712

    • Full Citation: U.S. Patent No. 6,104,712 to Al-Rawi et al.
    • Publication/Filing Date: Granted August 15, 2000 (Filed: Oct 9, 1997).
    • Brief Description: This patent describes a wireless packet data network that uses routing agents (similar to cluster heads) to manage routing and topology changes.
    • Potential Anticipation (35 U.S.C. § 102): This patent's discussion of routing agents and managing topology changes in wireless packet data networks is highly relevant. It could potentially anticipate claims relating to the roles of head nodes in routing and adapting to network changes (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73).

20. U.S. Patent No. 6,118,775

    • Full Citation: U.S. Patent No. 6,118,775 to Chen et al.
    • Publication/Filing Date: Granted September 12, 2000 (Filed: June 27, 1997).
    • Brief Description: This patent describes a clustering algorithm for mobile ad hoc networks, where nodes exchange information to elect cluster heads and form clusters.
    • Potential Anticipation (35 U.S.C. § 102): This is another highly relevant patent, explicitly detailing a clustering algorithm for mobile ad hoc networks with cluster head election based on exchanged information. This could potentially anticipate the core clustering and head node designation claims of US6980537 (e.g., claims 1-9, 19-28, 39-47, 55-63, 73-77), particularly those referring to using local connectivity information to determine head or member status.

21. U.S. Patent No. 6,160,808

    • Full Citation: U.S. Patent No. 6,160,808 to Lin.
    • Publication/Filing Date: Granted December 12, 2000 (Filed: May 12, 1998).
    • Brief Description: This patent describes an adaptive routing protocol for a hierarchical wireless communication network with two-level routing, addressing issues like node mobility.
    • Potential Anticipation (35 U.S.C. § 102): This patent's focus on adaptive routing in a hierarchical wireless network with a two-level structure is very pertinent. It could potentially anticipate claims relating to the multi-tier architecture and adaptive routing protocols within US6980537 (e.g., claims 1, 10, 19, 29, 30, 39, 48, 55, 64, 73, and those specifically mentioning a two-tier or three-tier structure).

22. U.S. Patent No. 6,170,051

    • Full Citation: U.S. Patent No. 6,170,051 to Ma et al.
    • Publication/Filing Date: Granted January 2, 2001 (Filed: Nov 25, 1997).
    • Brief Description: This patent describes a method for forming clusters in a mobile ad hoc network, where cluster heads are selected to minimize routing overhead and improve network stability.
    • Potential Anticipation (35 U.S.C. § 102): This is another highly relevant patent, explicitly addressing cluster formation in mobile ad hoc networks with the goal of minimizing routing overhead and improving stability. This directly relates to several key objectives and claims of US6980537, particularly claims related to cluster formation, head node designation, and reducing overhead traffic (e.g., claims 1-9, 19-28, 39-47, 55-63, 73-77, and 27, 37, 46, 53, 62, 71, 78).

Claim Structure of US6980537

To better understand potential anticipation, here's a high-level overview of US6980537's claims:

• Claims 1-9: Method claims for cluster formation, including transmitting node status packets, determining neighbors, adjusting transmission intervals, determining head/member status based on neighbor sets (subset criteria), and forming a hierarchical network.
• Claims 10-18: Method claims for transmitting information, focusing on a three-tier architecture, super nodes flooding information, and requesting missing data.
• Claims 19-28: Apparatus claims for cluster formation, mirroring method claims 1-9.
• Claims 29-38: Apparatus claims for transmitting information, mirroring method claims 10-18.
• Claims 39-47: Another set of method claims for cluster formation, similar to 1-9 but with slight variations.
• Claims 48-54: Another set of method claims for transmitting information, similar to 10-18.
• Claims 55-63: Another set of apparatus claims for cluster formation, similar to 19-28.
• Claims 64-72: Another set of apparatus claims for transmitting information, similar to 29-38.
• Claims 73-79: Another set of method claims for a communication system, encompassing both cluster formation and information transmission aspects.

Analysis of Potential Anticipation

Several prior art patents, particularly those from Ma et al. and Chen et al., directly address dynamic cluster formation and cluster head selection in wireless or ad hoc networks. For example, US5420854, US5617422, US5652751, US5835785, US6011780, US6118775, and US6170051 are highly relevant for the claims (1-9, 19-28, 39-47, 55-63, 73-77) that describe:

• A plurality of network nodes forming a network.
• Nodes transmitting status packets and receiving status packets.
• Identifying neighboring nodes.
• Forming clusters and designating cluster head nodes and member nodes.
• The dynamic nature of this process.

The specific "subset" criteria for head node designation (e.g., in claim 1: "determining whether or not a neighbor set associated with the network node is a subset of a neighbor set associated with another network node") would need to be compared against the specific algorithms disclosed in these prior art documents. While they generally describe cluster head election, the exact deterministic logic might vary.

Furthermore, the patents describing hierarchical networks (e.g., US5943322, US5946303, US6160808) are relevant to claims pertaining to the multi-tier architecture of US6980537.

The claims in US6980537 related to "reduced protocol overhead traffic" (e.g., claims 27, 37, 46, 53, 62, 71, 78) by eliminating acknowledgments and requesting missing information from super nodes would need to be carefully distinguished from general overhead reduction techniques found in patents like US5159592, US5280477, and US6170051. The "three-tier architecture" where super nodes handle flooding and head nodes route data, with a specific mechanism for requesting missing information instead of universal ACKs, is a key differentiating feature. Patents like US5652751 (establishing a backbone) and those generally discussing hierarchical routing could anticipate the structure, but perhaps not the specific mechanism of overhead reduction involving super nodes and selective requests for missing information.

Therefore, the most relevant prior art would be those patents that describe:

1. Dynamic cluster formation in wireless/ad hoc networks.
2. Selection of cluster heads based on network topology/connectivity information.
3. Hierarchical network architectures for routing.
4. Mechanisms for reducing routing overhead.

Many of the cited patents, particularly those by Ma, Chen, and Lin, touch upon these aspects, indicating that the core concepts of dynamic clustering and hierarchical routing in wireless networks were known in the art prior to US6980537's priority date of November 12, 1999. The specific method of determining head nodes using the subset criterion for neighbor sets and the detailed mechanism for overhead reduction in a three-tier architecture (super nodes, selective requests instead of ACKs) would be the key areas for novelty in US6980537.