Multiplex communications – Network configuration determination
Reexamination Certificate
2000-04-28
2004-09-14
Kizou, Hassan (Department: 2662)
Multiplex communications
Network configuration determination
C370S312000, C370S410000, C370S432000
Reexamination Certificate
active
06791949
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
Not applicable.
STATEMENT REGARDING FEDERALLY FUNDED RESEARCH
Not applicable.
BACKGROUND OF THE INVENTION
Wireless communication networks have significant application in permitting communication between various types of mobile apparatus, referred to herein as nodes. One such growing application is in tactical military environments in which the network is subject to rapid changes by which nodes are added, removed or moved from one location to another within the network. Such dynamically changing wireless networks are sometimes referred to as wireless ad hoc networks and include nodes which are able to communicate with each other over a wireless media, without any infrastructure, or wired network. Illustrative nodes include cellular telephones and portable computers which communicate by transmitting and receiving radio frequency (RF) signals in the form of packets.
Desirable characteristics of wireless ad hoc networks include the ability to adapt to frequent and rapid changes in node connections, compatibility with the Internet Protocol (IP) and other network protocols, and the ability to provide reliable communication. It is further desirable that the bandwidth necessary to establish and maintain the wireless ad hoc network not be excessive in order to permit a high data throughput and conserve node battery power.
In general, each network node maintains a routing table containing one or more routes to every other node in the network. Routing tables may be updated periodically or in response to detection of a change in the network. Various techniques are used to update routing tables. One such technique requires that each network node broadcast a routing message to every other network node, thereby permitting each node to learn the identity and connectivity of every other network node and, with that information, determine one or more optimal routes to each such node. However, such a broadcast-based approach requires significant bandwidth and thus, reduces data throughput.
In many wireless networks, every network node is capable of receiving packets from a source node and forwarding packets to a destination node. However, in some wireless ad hoc networks, only selected nodes are designated as “backbone nodes” and provide a fully connected packet forwarding infrastructure responsible for forwarding packets from a source node to a destination node, while the remaining network nodes are able to use the network (i.e., send and receive packets), but do not forward packets from a source node to a destination node. Such networks strike a balance between designating as backbone nodes the fewest number of nodes necessary to fully connect the network in order to increase bandwidth efficiency by reducing overhead and competition for channel capacity, while also providing some desirable redundancy in order to provide alternate route options and reduce congestion, or bottlenecking. One such network is described in a paper entitled “Spine routing in ad hoc networks”, R. Sivakumar, et al. Cluster Computing 1 (1998) p. 237-248 and may be characterized as an approximation to a “Minimal Connected Dominating Set” which is the smallest subset of a set of nodes in which all of the nodes of the subset are connected and can reach every node in the set via a single transmission, or hop.
Such networks advantageously reduce the bandwidth associated with updating routing tables. Further, since the backbone nodes have the greatest power requirements, minimizing the number of backbone nodes permits the nodes which may not have the necessary power capability to use the network. Additionally, both broadcast and multicast transmissions (i.e., single source with multiple receivers) are optimized since minimizing the backbone size minimizes replication of data at intermediate backbone nodes. However, care must be taken in providing a protocol for establishing and maintaining such networks in order to achieve these advantages while also providing a network capable of quickly and reliably adapting to a dynamically changing network.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a network protocol which is capable of rapidly adapting to network changes.
It is a further object to provide a network protocol which requires minimal bandwidth for establishing and maintaining the network.
Yet another object of the invention is to provide a network protocol which results in reliable communication between network nodes.
A still further object of the invention is to provide a network protocol which permits efficient multipoint-to-multipoint (multicast) communication among network nodes.
These and other objects of the invention are achieved by a method, or protocol for establishing a network from a plurality of nodes based on the periodic transmission and processing of signaling packets containing one or more protocol support records. The network includes a plurality of backbone nodes which are responsible for forwarding packets containing protocol records and other packets through the network (herein “category black nodes”) and a plurality of non-backbone nodes which are capable of reliably transmitting and receiving packets on the network, but which do not forward packets to other nodes (herein “category green nodes”). A third category of nodes (herein “category white nodes”) implement the protocol of the invention, but are not part of the network backbone and have not identified the existence of a reliable connection with a network backbone node.
Protocol support records include the Transmitter Status Record, Next Hop Information Record, Route Update Record, Address Resolution Notification Record, Address Resolution Query/Response Record, Route Query/Response Record, Multicast Join/Leave Record. The Transmitter Status and Next Hop Information Records are not forwarded through the network (i.e., they support ‘local’ (one hop) protocol information exchange). All other record types are forwarded through the network backbone.
To support the network protocol and routing methods, each node maintains a Node Information Table (herein “NIT”) in which it stores and maintains basic information about other nodes in the network. For each listed node, such information includes, for example, the node's MAC address and a deletion time stamp. Each node's NIT entry also contains pointers to three other protocol tables—the Route Table, the Neighbor Status Table, and the Protocol Support Record Queue. A node's Route Table entry contains primary and secondary routes to reach it, with respect to a plurality of Quality of Service (QoS) routing metrics (i.e., such as bandwidth and delay). Routes are represented by the “next hop address” (gateway node) through which the node can be reached and the level of QoS that the route is capable of supporting. The Route Table also contains received quality information that represents the regularity and estimated rate with which route updates are being received from the destination. The Neighbor Status Table contains status information about neighbor nodes contained in received Transmitter Status Records. Status information includes, for example, category designation (herein “color”), backbone capability, non-category black neighbor count (herein “degree”), category black neighbor count (herein “black degree”), receive link quality data, transmit link quality data (obtained from the node's Next Hop Information Record), and a sequence number counter which supports a CONNECTION process.
Network backbone creation begins with a SELECTION process which is performed only by white nodes. SELECTION is responsible for identifying an initial set of network backbone nodes (i.e., it “seeds” the network with black nodes). In general, a category white node is selected to become a backbone node as a result of having more non-backbone neighbors than any of its neighboring nodes.
An EXPANSION process is also performed by category white nodes and, in particular, by category white nodes that do not pass the SELECTION process. EXPANSION i
Dao Son K.
Erickson Jason C.
Ryu Bong K.
Smallcomb James X.
Daly, Crowley & Mofford LLP
Kizou Hassan
McLoughlin Mike
Raytheon Company
LandOfFree
Network protocol for wireless ad hoc networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network protocol for wireless ad hoc networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network protocol for wireless ad hoc networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3237026