Method and apparatus for communication network cluster formation and transmission of node link status messages with reduced protocol overhead traffic
DCFirst Claim
1. In a communications network including a plurality of communication units, wherein at least one of those units is designated as a member unit for transmitting and receiving messages and at least one of those units is designated as a routing unit for routing said messages from said member units, a communication unit to transmit and receive messages within said network comprising:
- a transmitter to transmit an outgoing message to each neighboring unit of said communication unit;
a receiver to receive an incoming message from said each neighboring unit;
a storage unit to store network connectivity information relating to said communication unit and corresponding neighboring units; and
a processor to control said transmission and reception of said outgoing and incoming messages, wherein said processor includes;
a configuration module to designate a status of said communication unit as one of said routing unit and said member unit to configure said communications network, wherein said configuration module includes;
a neighbor module to examine said network connectivity information and identify neighboring units of said communication unit that are isolated from communications with remaining neighboring units of said communication unit;
a designation module to designate said communication unit as said routing unit in response to determining that said communication unit communicates with at least one neighboring unit that is isolated from communications with remaining neighboring units of said communication unit, wherein said communication unit designation as said routing unit is fixed for routing subsequent network messages; and
a monitor module to re-evaluate said communication unit designation in response to connectivity changes in said network.
11 Assignments
Litigations
0 Petitions
Accused Products
Abstract
The present invention facilitates cluster formation within a communications network by utilizing network topology information to designate network nodes that are crucial for relaying traffic as cluster head nodes, while remaining network nodes are designated as member nodes. A beacon packet transmission rate of a network node or the interval between successive beacon packet transmissions by that node is adjusted by the present invention to facilitate cluster formation independent of network size and varying initial start times of network nodes. In addition, the present invention utilizes the above described cluster formation technique to form a three tier architecture for transmission or flooding of routing information from head node databases throughout the network. The cluster formation technique is applied to cluster head nodes to form an additional network tier of super nodes that distribute routing information, while cluster head nodes route network data traffic. The databases of cluster head nodes are examined subsequent to flooding of head node database information by super nodes, where data missing from a head node database is requested from a corresponding super node, thereby eliminating transmissions of acknowledgment messages.
188 Citations
68 Claims
-
1. In a communications network including a plurality of communication units, wherein at least one of those units is designated as a member unit for transmitting and receiving messages and at least one of those units is designated as a routing unit for routing said messages from said member units, a communication unit to transmit and receive messages within said network comprising:
-
a transmitter to transmit an outgoing message to each neighboring unit of said communication unit; a receiver to receive an incoming message from said each neighboring unit; a storage unit to store network connectivity information relating to said communication unit and corresponding neighboring units; and a processor to control said transmission and reception of said outgoing and incoming messages, wherein said processor includes; a configuration module to designate a status of said communication unit as one of said routing unit and said member unit to configure said communications network, wherein said configuration module includes; a neighbor module to examine said network connectivity information and identify neighboring units of said communication unit that are isolated from communications with remaining neighboring units of said communication unit; a designation module to designate said communication unit as said routing unit in response to determining that said communication unit communicates with at least one neighboring unit that is isolated from communications with remaining neighboring units of said communication unit, wherein said communication unit designation as said routing unit is fixed for routing subsequent network messages; and a monitor module to re-evaluate said communication unit designation in response to connectivity changes in said network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. In a communications network including a plurality of communication units, wherein at least one of those units is designated as a member unit for transmitting and receiving messages and at least one of those units is designated as a routing unit for routing said messages from said member units, a method of configuring a network communication unit to transmit and receive messages within said network comprising the steps of:
-
(a) examining network connectivity information relating to said communication unit and corresponding neighboring units stored in a storage unit of said communication unit and identifying neighboring units that are isolated from communications with remaining neighboring units of said communication unit; (b) designating said communication unit as said routing unit in response to determining that said communication unit communicates with at least one neighboring unit that is isolated from communications with remaining neighboring units of said communication unit, wherein said communication unit designation as said routing unit is fixed for routing subsequent network messages; and (c) re-evaluating said communication unit designation in response to connectivity changes in said network. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
-
-
30. A communications network comprising:
a plurality of communication units to transmit and receive messages within said network, wherein each said communication unit includes; a status transmission module to facilitate periodic transmission of a unit status message; an interval module to adjust the time between each said periodic transmission in response to detecting modifications in connectivity with neighboring units; and a configuration module to determine a status of that communication unit as a routing unit for routing network traffic or as a member unit of a corresponding routing unit in accordance with information contained within received unit status messages, wherein said communication unit status as said routing unit is fixed for routing subsequent network messages and re-evaluated in response to changes in network connectivity. - View Dependent Claims (31, 32)
-
33. In a communications network including a plurality of communication units to transmit and receive messages within said network, a method of transmitting and receiving messages comprising the steps of:
-
(a) periodically transmitting a unit status message from each communication unit; (b) adjusting the time between each periodic transmission of a communication unit in response to that communication unit detecting modifications in connectivity with neighboring units; and (c) determining a status of said each communication unit as a routing unit for routing network traffic or as a member unit of a corresponding routing unit in accordance with information contained within received unit status messages, wherein said communication unit status as said routing unit is fixed for routing subsequent network messages and re-evaluated in response to changes in network connectivity. - View Dependent Claims (34, 35)
-
-
36. A communications network comprising:
a plurality of communication units forming a first network tier to transmit and receive messages within said network, wherein at least one of said communication units is designated as a routing unit to form a second network tier to route network traffic and at least one of said designated routing units is designated as a transmission routing unit to form a third network tier to transmit network information throughout said second and third network tiers, and wherein each said communication unit includes; a configuration module to determine a status of that communication unit as said routing unit of said second network tier for routing network traffic or as a member unit of said first network tier and associated with a routing unit, wherein said communication unit status as a routing unit is fixed for routing subsequent network messages; a routing unit configuration module to determine a status of that communication unit as a transmission routing unit in response to that communication unit being designated as said routing unit, wherein said communication unit status as a transmission routing unit is fixed for flooding subsequent network connectivity messages; and an evaluation module to re-evaluate said communication unit status in response to connectivity changes in said network. - View Dependent Claims (37, 38, 39, 40, 41, 42, 43, 44)
-
45. In a communications network including a plurality of communication units forming a first network tier to transmit and receive messages within said network, wherein at least one of said communication units is designated as a routing unit to form a second network tier to route network traffic and at least one of said designated routing units is designated as a transmission routing unit to form a third network tier to transmit network information throughout said second and third network tiers, a method of configuring said network including the steps of:
-
(a) determining a status of each communication unit as said routing unit of said second network tier for routing network traffic or as a member unit of said first network tier and associated with a routing unit, wherein said communication unit status as a routing unit is fixed for routing subsequent network messages; (b) determining a status of each communication unit as said transmission routing unit to transmit said network information throughout said second and third network tiers in response to that communication unit being designated as said routing unit, wherein said communication unit status as a transmission routing unit is fixed for flooding subsequent network connectivity messages; and (c) re-evaluating said communication unit status in response to connectivity changes in said network. - View Dependent Claims (46, 47, 48, 49, 50, 51, 52, 53)
-
-
54. In a wireless communications network including a plurality of communication units, wherein at least one of those units is designated as a member unit for transmitting and receiving messages and at least one of those units is designated as a relay unit for transferring messages from said member units, a communication unit to transmit and receive messages within said network comprising:
-
a transmitter to transmit an outgoing message in the form of radio signals to each neighboring unit of said communication unit; a receiver to receive an incoming message in the form of radio signals from said each neighboring unit; a storage unit to store network information relating to said communication unit and corresponding neighboring units; and a processor to control said transmission and reception of said outgoing and incoming messages, wherein said processor includes; a configuration module to designate a status of said communication unit as one of said relay unit and said member unit to configure said communications network, wherein said configuration module includes; a neighbor module to examine network connectivity information and identify at least one neighboring unit of said communication unit that is required to utilize said communication unit to communicate with network communication units that are outside the range of and greater than one hop away from that neighboring unit; a designation module to designate said communication unit as said relay unit based on said examination and in response to determining that at least one neighboring communication unit is required to utilize said communication unit to communicate with network communication units that are outside the range of and greater than one hop away from said neighboring communication unit, wherein said communication unit designation as said relay unit is fixed for transferring subsequent network messages; and an evaluation module to re-evaluate said communication unit designation in response to connectivity changes in said network. - View Dependent Claims (55, 56, 57, 58)
-
-
59. In a wireless communications network including a plurality of communication units, wherein at least one of those units is designated as a member unit for transmitting and receiving messages and at least one of those units is designated as a relay unit for transferring messages from said member units, a method of configuring a network communication unit to transmit and receive messages within said network comprising the steps of:
-
(a) examining network connectivity information relating to said communication unit and corresponding neighboring units stored in a storage unit of said communication unit and identifying at least one neighboring unit of said communication unit that is required to utilize said communication unit to communicate with network communication units that are outside the range of and greater than one hop away from that neighboring unit; (b) designating said communication unit as said relay unit based on said examination and in response to determining that at least one neighboring communication unit is required to utilize said communication unit to communicate with network communication units that are outside the range of and greater than one hop away from said neighboring communication unit, wherein said communication unit designation as said relay unit is fixed for transferring subsequent network messages; and (c) re-evaluating said communication unit designation in response to connectivity changes in said network. - View Dependent Claims (60, 61, 62, 63)
-
-
64. A wireless communications network comprising:
a plurality of communication units to transmit and receive messages in the form of radio signals within said network, wherein said communication units;
examine network connectivity information;
identify communication units that are required to be utilized by associated neighboring units to communicate with network communication units that are outside the range of and greater than one hop away from those neighboring units;
designate at least one communication unit as a relay unit to transfer network information based on said examination and in response to determining that said at least one communication unit is required to be utilized by at least one neighboring unit to communicate with communication units that are outside the range of and greater than one hop away from said neighboring units, wherein said communication unit designation as said relay unit is fixed for transferring subsequent network messages; and
re-evaluate said communication unit designation in response to connectivity changes in said network.- View Dependent Claims (65, 66, 67, 68)
Specification