Obviousness

US Patent 6980537, titled "Method and apparatus for communication network cluster formation and transmission of node link status messages with reduced protocol overhead traffic," addresses several challenges in wireless communication networks, particularly ad hoc networks. The patent's objectives include facilitating cluster formation with minimal hops, enabling cluster formation independent of initial node start times, and reducing protocol overhead, especially for transmitting node link status messages.

An analysis under 35 U.S.C. § 103 for obviousness considers whether the claimed invention would have been obvious to a person having ordinary skill in the art (PHOSITA) at the time of the invention, based on prior art. The patent itself describes several prior art techniques and their limitations, which often serve as a motivation for a PHOSITA to combine or modify existing technologies.

Combinations of Prior Art Rendering Claims Obvious

The core inventive aspects of US6980537, as described in its abstract and summary, appear to be rendered obvious by combinations of the prior art explicitly discussed within the patent, driven by the problems the patent itself identifies.

1. Cluster Formation Utilizing Network Topology Information to Designate Crucial Relay Nodes:

• Prior Art: The patent acknowledges hierarchical network architectures where clusters are formed, and one node within each cluster is designated as a cluster head, with these heads forming a backbone network. [cite: "The hierarchal architecture basically arranges a network into plural tiers or hierarchical levels. The first tier typically includes clusters or cells each including a plurality of communication nodes or cluster members. One node within each cluster is designated as the cluster head and has full connectivity to corresponding member nodes. The second tier includes a backbone network formed of the cluster head nodes to enable communications between different clusters (e.g., for data transmitted over greater distances)."] The prior art also includes routing protocols like OSPF and ROSPF, which use "routing databases containing information related to network topology (e.g., links between network nodes)" for path determination. [cite: "Routing is accomplished in the OSPF protocol by each network node having a routing database containing information related to network topology (e.g., links between network nodes)."] Existing clustering techniques designated cluster heads based on node identifiers (e.g., lowest/greatest ID) or a "degree of node connectivity." [cite: "A technique of the related art for cluster head designation and subsequent cluster formation includes determining clusters based on identifiers (e.g., identification codes or numbers) of network nodes.", "The related art has expanded this technique to utilize a node identifier or a degree of node connectivity to designate a cluster head node."]
• Problem Addressed (Motivation): The patent explicitly states that these prior art techniques using simple criteria (like lowest ID) or random start times were suboptimal. They "may result in no direct links between cluster head nodes, thereby requiring additional gateway type nodes... and increasing the quantity of hops required for communication." [cite: "this may result in no direct links between cluster head nodes, thereby requiring additional gateway type nodes (e.g., nodes having communications with two cluster head nodes) to facilitate communication between clusters and increasing the quantity of hops required for communication."] The random start times approach resulted in "significant quantity of nodes as cluster head nodes, where the designations are typically not optimal selections for a network configuration." [cite: "The approach according to node random start times may designate a significant quantity of nodes as cluster head nodes, where the designations are typically not optimal selections for a network configuration."]
• Obvious Combination: A PHOSITA, motivated by the inefficiencies and sub-optimal selections of existing clustering methods, would logically look to use the richer "network topology information" already available in existing routing databases (as used by OSPF/ROSPF) to make a more informed decision about cluster head designation. Given that the prior art already considered "degree of node connectivity," extending this to identify nodes "crucial for relaying traffic" (e.g., by determining if a node's neighbor set is not a subset of any of its neighbors' sets, as the patent describes for node 10(4) in FIG. 5 [cite: "Since set S 4 is not a subset of the neighbor sets of the remaining nodes with that set, this indicates that there exist some nodes within set S 4 that may only establish communications through node 10 ( 4 ) and, therefore, node 10 ( 4 ) is crucial to relay traffic and is designated as a head node."]) would be a predictable engineering step to minimize hops and eliminate gateway nodes. The motivation is directly to solve the problem of suboptimal cluster head selection and inefficient routing.

2. Adaptive Adjustment of Node Status Packet Transmission Interval:

• Prior Art: Each network node in the prior art "periodically broadcasts a beacon type or node status packet" for "keep alive" and "neighbor discovery purposes." [cite: "each network node (e.g., cluster head and member nodes) periodically broadcasts a beacon type or node status packet in accordance with the routing protocol. This packet basically advertises the presence of a node within the network, and is typically utilized by cluster head nodes for 'keep alive' and neighbor discovery purposes."]
• Problem Addressed (Motivation): The patent explicitly identifies that prior art clustering techniques "complicate determination of an appropriate interval between node status packet transmissions. When the interval is set to a value below an acceptable range, large scale networks may become congested. Conversely, if the interval is set to a value above an acceptable range, an extensive time interval is required to complete cluster formation." [cite: "the above clustering techniques complicate determination of an appropriate interval between node status packet transmissions. When the interval is set to a value below an acceptable range, large scale networks may become congested. Conversely, if the interval is set to a value above an acceptable range, an extensive time interval is required to complete cluster formation."]
• Obvious Combination: A PHOSITA facing network congestion or slow formation due to an ill-chosen fixed interval for status packet transmissions would be motivated to implement adaptive control. The general principle of dynamically adjusting transmission rates based on network conditions (e.g., load, congestion, or feedback like packet loss) is well-known in networking. Applying this principle by monitoring the "quantity of neighboring nodes indicated within received node status packets" [cite: "The node processor subsequently determines the appropriate interval between subsequent node status packet transmissions based on the quantity of neighboring nodes indicated within received node status packets."] and adjusting the interval (e.g., increasing it if no new neighbors are discovered or if the neighbor quantity remains stagnant, suggesting lost packets or saturation [cite: "when the quantity of neighboring nodes, N k (e.g., where N is an integer generally greater than or equal to zero), associated with the network node at a time, tk, is the same as the neighbor quantity, N k−1 , at a previous time, t k−1 , as determined at step 38 , the time interval between transmission of node status packets by the network node, T k , is increased at step 42 ."]) would be a predictable optimization. This directly addresses the stated problems of congestion and slow formation, and is a logical application of feedback control to an existing periodic broadcast mechanism.

3. Three-Tier Hierarchical Network Architecture with Super Nodes for Routing Information Distribution:

• Prior Art: Two-tier hierarchical architectures were known for reducing overhead traffic compared to flat networks. [cite: "The hierarchical architecture reduces overhead traffic relative to the flat network architecture, however, this reduction is insufficient when the network employs on the order of several hundred nodes, thereby limiting application of the routing protocol."] The existing two-tier architecture had nodes (first tier) and cluster head nodes forming a backbone (second tier). [cite: "Thus, the first network tier represents each network node, while the second network tier represents cluster head nodes."] Routing protocols involved "transmitting or flooding routing information from each head node database among cluster head nodes to synchronize those databases." [cite: "This is accomplished by transmitting or flooding routing information from each head node database among cluster head nodes to synchronize those databases."]
• Problem Addressed (Motivation): The patent states that the overhead reduction provided by the two-tier hierarchical architecture was "insufficient when the network employs on the order of several hundred nodes." [cite: "the hierarchical architecture reduces overhead traffic relative to the flat network architecture, however, this reduction is insufficient when the network employs on the order of several hundred nodes, thereby limiting application of the routing protocol."] A PHOSITA would be motivated to seek further overhead reduction for large-scale networks.
• Obvious Combination: Re-applying a known clustering technique (whether the prior art method or the improved method of US6980537) to the existing backbone network (the second tier of cluster heads) to create a further layer of hierarchy (a third tier of "super nodes") is a predictable architectural design choice for improving scalability and reducing administrative overhead in large systems. The patent describes this as applying the "cluster formation technique... to the cluster head nodes or backbone network to form third tier clusters." [cite: "The cluster formation technique is applied to the cluster head nodes or backbone network to form third tier clusters. Nodes within the third tier distribute routing information from head node databases to reduce overhead traffic, while head nodes within the second tier are utilized for data routing."] This is a logical extension of an already successful hierarchical approach to further reduce the scope of routing information flooding.

4. Eliminating Acknowledgment Messages by Requesting Missing Information:

• Prior Art: Conventional link-state routing protocols, when flooding database information, required "a receiving head node transmits an acknowledgment message to a source head node transmitting the database information. If an acknowledgment message is not received within a predetermined time interval, the database information is re-transmitted." [cite: "In order to ensure receipt of database information, a receiving head node transmits an acknowledgment message to a source head node transmitting the database information. If an acknowledgment message is not received within a predetermined time interval, the database information is re-transmitted to the network head nodes that have not acknowledged receipt of the database information."]
• Problem Addressed (Motivation): The patent clearly identifies that "reliability of flooding node database information throughout a network is enhanced by transmission of acknowledgment messages, these messages increase overhead traffic, thereby degrading network performance." [cite: "reliability of flooding node database information throughout a network is enhanced by transmission of acknowledgment messages, these messages increase overhead traffic, thereby degrading network performance."] A PHOSITA would be motivated to reduce this acknowledgment-related overhead.
• Obvious Combination: Instead of sending an explicit acknowledgment for every database update packet (which creates significant overhead), a PHOSITA would consider known techniques for reliable data transfer that involve detecting missing information and requesting only those missing parts. The patent describes this as "examin[ing] head node databases and request[ing] third tier nodes to supply missing information. Thus, the present invention only sends request messages in response to receipt of the database information and discovering missing data within head node databases, thereby significantly reducing overhead traffic." [cite: "Basically, the present invention examines head node databases and requests third tier nodes to supply missing information. Thus, the present invention only sends request messages in response to receipt of the database information and discovering missing data within head node databases, thereby significantly reducing overhead traffic."] This is a predictable engineering trade-off: replace frequent, low-value acknowledgments with less frequent, targeted requests for missing data, especially when a higher-tier node (super node) is already responsible for distributing information.

In summary, the patent itself meticulously lays out the prior art and its deficiencies, which serve as direct motivations for a PHOSITA to combine existing techniques or apply known networking principles (like adaptive control or hierarchical scaling) to arrive at the claimed invention.