초록 ▼

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 transmis

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.

대표청구항 ▼

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

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; anda 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; anda monitor module to re-evaluate said communication unit designation in response to connectivity changes in said network.2. The unit of claim 1 wherein said transmitter transmits said outgoing message in the form of radio signals.3. The unit of claim 1 wherein said receiver receives said incoming message in the form of radio signals.4. The unit of claim 1 wherein said processor further includes:a status transmission module to facilitate transmission of a unit status message at a periodic time interval, wherein said unit status message includes unit connectivity information relating to network connectivity of said communication unit; anda status reception module to facilitate reception of said unit status message from said each neighboring unit and to update said connectivity information within said storage unit in accordance with unit connectivity information contained within each received unit status message.5. The unit of claim 4 wherein said processor further includes:an interval module to adjust said periodic time interval in response to detecting modifications in network connectivity indicated by said updated connectivity information within said storage unit.6. The unit of claim 5 wherein said interval module further includes:an interval adjustment module to increase said periodic time interval in response to determining that a quantity of neighboring units of said communication unit is equal to said neighboring unit quantity of an immediately preceding periodic time interval.7. The unit of claim 4 wherein said configuration module further includes:a transmission interval module to maintain a count of unit status message transmissions by said communications unit and to determine when a predetermined quantity of said unit status messages has been transmitted;an evaluation module to determine the presence of modifications to said connectivity information within said storage unit during said unit status message transmissions; anda unit status module to determine said status of said communication unit as said routing unit in response to an absence of modifications to said connectivity information as determined by said evaluation module.8. The unit of claim 7 wherein said unit status module further includes:a routing status 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;a master status module to designate said communication unit as a master unit in response to determining that said communication unit and each neighboring unit are in communication with the same units and said communication unit is associated with an identifier superior to identifiers of said neighboring units; anda member status module to designate said communication unit as a member unit of a corresponding routing unit in response to said master status module determining that said communication unit and each neighboring unit are in communication with at least one different unit and said routing status module determining that said communication unit fails to qualify as said routing unit.9. The unit of claim 8 wherein said master status module further includes:a routing unit selection module to determine said status of said neighboring units as said routing and member units in response to said communication unit being designated as said master unit; anda status transmission module to facilitate transmission of status information to neighboring designated routing units to inform those units of their designation as routing units by said communication unit serving as said master unit.10. The unit of claim 1 wherein said configuration module further includes:a link storage unit to store connectivity information relating to routing units; anda routing unit configuration module to examine said network connectivity information within said link storage unit in response to said communication unit being designated as said routing unit and to designate said communication unit as a transmission routing unit in response to determining that said communication unit communicates with at least one neighboring routing unit that is isolated from communications with remaining neighboring routing units of said communication unit.11. The unit of claim 10 wherein said transmission routing unit transmits update messages including network connectivity information, and said routing unit configuration module further includes:a message forwarding module to receive an update message from a neighboring transmission routing unit in response to said communication unit being designated as said transmission routing unit and to transmit said received message to neighboring routing units to facilitate synchronization of said link storage unit of each said routing unit.12. The unit of claim 11 wherein said routing unit configuration module further includes:an update module to receive an update message from a neighboring transmission routing unit in response to said communication unit being designated as said routing unit and to update said link storage unit with said connectivity information contained within said received update message;a data integrity module to examine said network connectivity information within said link storage unit and determine information missing from said link storage unit in response to said update by said update module; anda request module to request said neighboring transmission routing unit to transmit said missing information in response to said data integrity module determining that information is missing from said link storage unit.13. The unit of claim 12 wherein said routing unit configuration module further includes:a request processing module to receive said request from a neighboring routing unit in response to said communication unit being designated as a transmission routing unit and to process said received request to transmit information identified in said request to that neighboring routing unit.14. The unit of claim 11 wherein said message forwarding module further includes:a data accumulation module to accumulate information received within plural update messages and to transmit said accumulated information in the form of a single transmission to neighboring routing units to facilitate synchronization of said link storage unit of said each routing unit.15. The unit of claim 11 wherein said message forwarding module further includes:a timer to indicate expiration of periodic reception intervals; anda data accumulation module to accumulate information received within each of said periodic reception intervals and to transmit said accumulated information of each periodic reception interval in the form of a single transmission to neighboring routing units at expiration of that periodic reception interval to facilitate synchronization of said link storage unit of said each routing unit.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.17. The method of claim 16 wherein said messages are transmitted in the form of radio signals.18. The method of claim 16 wherein step (a) further includes:(a.1) transmitting a unit status message at a periodic time interval, wherein said unit status message includes unit connectivity information relating to network connectivity of said communication unit; and(a.2) receiving said unit status message from said each neighboring unit and updating said connectivity information within said storage unit in accordance with unit connectivity information contained within each received unit status message.19. The method of claim 18 wherein step (a) further includes:(a.3) adjusting said periodic time interval in response to detecting modifications in network connectivity indicated by said updated connectivity information within said storage unit.20. The method of claim 19 wherein step (a.3) includes:(a.3.1) increasing said periodic time interval in response to determining that a quantity of neighboring units of said communication unit is equal to said neighboring unit quantity of an immediately preceding periodic time interval.21. The method of claim 18 wherein step (b) further includes:(b.1) maintaining a count of unit status message transmissions by said communications unit and determining when a predetermined quantity of said unit status messages has been transmitted;(b.2) determining the presence of modifications to said connectivity information within said storage unit during said unit status message transmissions; and(b.3) determining said status of said communication unit as said routing unit in response to an absence of modifications to said connectivity information as determined in step (b.2).22. The method of claim 21 wherein step (b.3) further includes:(b.3.1) 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;(b.3.2) designating said communication unit as a master unit in response to determining that said communication unit and each neighboring unit are in communication with the same units and said communication unit is associated with an identifier superior to identifiers of said neighboring units; and(b.3.3) designating said communication unit as a member unit of a corresponding routing unit in response to step (b.3.2) determining that said communication unit and each neighboring unit are in communication with at least one different unit and step (b.3.1) determining that said communication unit fails to qualify as said routing unit.23. The method of claim 22 wherein step (b.3.2) further includes:(b.3.2.1) determining said status of said neighboring units as said routing and member units in response to said communication unit being designated as said master unit; and(b.3.2.2) transmitting status information to neighboring designated routing units to inform those units of their designation as routing units by said communication unit serving as said master unit.24. The method of claim 16 further including:(d) examining network connectivity information relating to routing units stored within a link storage unit of said communication unit in response to said communication unit being designated as said routing unit; and(e) designating said communication unit as a transmission routing unit in response to determining that said communication unit communicates with at least one neighboring routing unit that is isolated from communications with remaining neighboring routing units of said communication unit.25. The method of claim 24 wherein said transmission routing unit transmits update messages including network connectivity information, and step (e) further includes:(e.1) receiving an update message from a neighboring transmission routing unit in response to said communication unit being designated as said transmission routing unit and transmitting said received message to neighboring routing units to facilitate synchronization of said link storage unit of each said routing unit.26. The method of claim 25 wherein step (e) further includes:(e.2) receiving an update message from a neighboring transmission routing unit in response to said communication unit being designated as said routing unit and updating said link storage unit with said connectivity information contained within said received update message;(e.3) examining said network connectivity information within said link storage unit and determining information missing from said link storage unit in response to said update by step (e.2); and(e.4) requesting said neighboring transmission routing unit to transmit said missing information in response to step (e.3) determining that information is missing from said link storage unit.27. The method of claim 26 wherein step (e) further includes:(e.5) receiving said request from a neighboring routing unit in response to said communication unit being designated as a transmission routing unit and processing said received request to transmit information identified in said request to that neighboring routing unit.28. The method of claim 25 wherein step (e.1) further includes:(e.1.1) accumulating information received within plural update messages and transmitting said accumulated information in the form of a single transmission to neighboring routing units to facilitate synchronization of said link storage unit of said each routing unit.29. The method of claim 25 wherein step (e.1) further includes:(e.1.1) indicating expiration of periodic reception intervals; and(e.1.2) accumulating information received within each of said periodic reception intervals and transmitting said accumulated information of each periodic reception interval in the form of a single transmission to neighboring routing units at expiration of that periodic reception interval to facilitate synchronization of said link storage unit of said each routing unit.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; anda 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.31. The network of claim 30 wherein said each communication unit transmits messages in the form of radio signals.32. The network of claim 30 wherein said interval module further includes:an interval adjustment module to increase said time between each said periodic transmission in response to determining that a quantity of neighboring units of that communication unit is equal to said neighboring unit quantity associated with an immediately preceding periodic transmission.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.34. The method of claim 33 wherein said each communication unit transmits messages in the form of radio signals.35. The method of claim 33 wherein step (b) further includes:(b.1) increasing said time between each said periodic transmission in response to determining that a quantity of neighboring units of that communication unit is equal to said neighboring unit quantity associated with an immediately preceding periodic transmission.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; andan evaluation module to re-evaluate said communication unit status in response to connectivity changes in said network.37. The network of claim 36 wherein said each communication unit transmits messages in the form of radio signals.38. The network of claim 36 wherein said configuration module further includes a unit designation module to examine network connectivity information relating to that communication unit and to designate that communication unit as said routing unit in response to that communication unit communicating with at least one neighboring unit that is isolated from communications with remaining neighboring units of that communication unit.39. The network of claim 36 wherein said routing unit configuration module further includes a routing unit designation module to examine network connectivity information relating to designated routing units stored within a link storage unit of that communication unit and to designate that communication unit as a transmission routing unit in response to that communication unit communicating with at least one neighboring routing unit that is isolated from communications with remaining neighboring routing units of that communication unit.40. The network of claim 39 wherein said transmission routing unit transmits update messages including network connectivity information, and said routing unit configuration module further includes:a message forwarding module to receive an update message from a neighboring transmission routing unit in response to that communication unit being designated as said transmission routing unit and to transmit said received message to neighboring routing units of that communication unit to facilitate synchronization of said link storage unit of each said routing unit.41. The network of claim 40 wherein said routing unit configuration module further includes:an update module to receive an update message from a neighboring transmission routing unit in response to that communication unit being designated as said routing unit and to update said link storage unit of that communication unit with said connectivity information contained within said received update message;a data integrity module to examine said network connectivity information within a link storage unit of that communication unit and determine information missing from that link storage unit in response to said update by said update module; anda request module to request said neighboring transmission routing unit to transmit said missing information in response to said data integrity module determining that information is missing from said link storage unit of that communication unit.42. The unit of claim 41 wherein said routing unit configuration module further includes:a request processing module to receive said request from a neighboring routing unit in response to that communication unit being designated as a transmission routing unit and to process said received request to transmit information identified in said request to that neighboring routing unit.43. The network of claim 40 wherein said message forwarding module further includes:a data accumulation module to accumulate information received within plural update messages and to transmit said accumulated information in the form of a single transmission to neighboring routing units of that communication unit to facilitate synchronization of said link storage unit of said each routing unit.44. The network of claim 40 wherein said message forwarding module further includes:a timer to indicate expiration of periodic reception intervals; anda data accumulation module to accumulate information received within each of said periodic reception intervals and to transmit said accumulated information of each periodic reception interval in the form of a single transmission to neighboring routing units of that communication unit at expiration of that periodic reception interval to facilitate synchronization of said link storage unit of said each routing unit.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.46. The method of claim 45 wherein said each communication unit transmits messages in the form of radio signals.47. The method of claim 45 wherein step (a) further includes:(a.1) examining network connectivity information relating to each communication unit and designating as said routing unit each communication unit communicating with at least one neighboring unit isolated from communications with remaining neighboring units of that communication unit.48. The method of claim 45 wherein step (b) further includes:(b.1) examining network connectivity information relating to designated routing units and stored within a link storage unit of said each communication unit and designating as said transmission routing unit each communication unit that communicates with at least one neighboring routing unit isolated from communications with remaining neighboring routing units of that communication unit.49. The method of claim 48 wherein said transmission routing unit transmits update messages including network connectivity information, and step (b) further includes:(b.2) receiving an update message from a corresponding neighboring transmission routing unit at each communication unit designated as said transmission routing unit and transmitting said received message to neighboring routing units of that communication unit to facilitate synchronization of said link storage unit of each said routing unit.50. The method of claim 49 wherein step (b) further includes:(b.3) receiving an update message from a corresponding neighboring transmission routing unit at each communication unit designated as said routing unit and updating said link storage unit of that communication unit with said connectivity information contained within said received update message;(b.4) examining said network connectivity information within said link storage unit of each communication unit and determining information missing from that link storage unit in response to said update; and(b.5) requesting said corresponding neighboring transmission routing unit of each communication unit designated as said routing unit to transmit said missing information in response to said data integrity module determining that information is missing from a link storage unit of that communication unit.51. The method of claim 50 wherein step (b) further includes:(b.6) receiving at each communication unit designated as said transmission routing unit said request from a corresponding neighboring routing unit and processing said received request to transmit information identified in said request to that neighboring routing unit.52. The method of claim 49 wherein step (b.2) further includes:(b.2.1) accumulating information received within plural update messages at each communication unit designated as said transmission routing unit and transmitting said accumulated information in the form of a single transmission to corresponding neighboring routing units of that communication unit to facilitate synchronization of said link storage unit of said each routing unit.53. The method of claim 49 wherein step (b.2) further includes:(b.2.1) indicating expiration of periodic reception intervals; and(b.2.2) accumulating information received within each of said periodic reception intervals at each communication unit designated as said transmission routing unit and transmitting said accumulated information of each periodic reception interval in the form of a single transmission to corresponding neighboring routing units of that communication unit at expiration of that periodic reception interval to facilitate synchronization of said link storage unit of said each routing unit.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; anda 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; andan evaluation module to re-evaluate said communication unit designation in response to connectivity changes in said network.55. The unit of claim 54, wherein said network is an ad-hoc wireless communications network.56. The unit of claim 54, wherein said processor further includes:a status transmission module to facilitate transmission of a unit status message at a periodic time interval, wherein said unit status message includes network connectivity information.57. The unit of claim 56, wherein said processor further includes:an interval module to adjust said periodic time interval to accommodate network conditions.58. The unit of claim 54, wherein said plurality of communication units include said member units and said designated relay units, and wherein said relay units generate and forward network connectivity information through said network.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.60. The method of claim 59, wherein said network is an ad-hoc wireless communications network.61. The method of claim 59, wherein step (a) further includes:(a.1) transmitting a unit status message at a periodic time interval, wherein said unit status message includes network connectivity information.62. The method of claim 61, wherein step (a) further includes:(a.2) adjusting said periodic time interval to accommodate network conditions.63. The method of claim 59, wherein said plurality of communication units include said member units and said designated relay units, and said method further includes:(d) generating and forwarding network connectivity information through said network via said designated relay units.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.65. The network of claim 64, wherein said network is an ad-hoc wireless communications network.66. The network of claim 64, wherein said communication units each include:a status transmission module to facilitate transmission of a unit status message at a periodic time interval, wherein said unit status message includes network connectivity information.67. The network of claim 66, wherein said communication units each further include:an interval module to adjust said periodic time interval to accommodate network conditions.68. The network of claim 64, wherein said designated relay units generate and forward network connectivity information through said network.