Abstract:
In one embodiment, a computer-based system to schedule network traffic in a communication network comprises a processor coupled to a first node of a network, a memory module coupled to the processor and comprising logic instructions stored on a tangible computer readable medium which, when execute by the processor, configure the processor to receive at the first node of the network, situational awareness information from at least a second network node which is directly accessible by the first node, identify, in the first node, situational awareness information commonly known by multiple nodes across the network, generate a network schedule based on said commonly known situational information, generate a shortest path routing table from the first node to all other network nodes based on said network schedule, and route network traffic at the first node using said network schedule. Other embodiments may be disclosed.

Description:
BACKGROUND 
       [0001]    Ad hoc communication networks comprise a number of nodes corresponding to one or more transmitter/receiver pairs. For any node, there will be some nearby nodes that are in range for direct communication, and these are commonly referred to as neighbor, or one-hop nodes. Other nodes will be out of range for direct communication and so may only be contacted indirectly with multiple hops via intermediate nodes. The ad hoc nature of the network means that, for any particular message, there may be many possible routes through different intermediate nodes that connect a source node with a destination node. 
         [0002]    Mobile networks are inherently dynamic and ad-hoc. Continuous communications between mobile terminals in an ad-hoc network necessitates sharing of each terminal&#39;s state, link status, available bandwidth, and information traffic demands. As mobile networks increase in size the load on the network to support this maintenance or network situation awareness information sharing takes an ever increasing percentage of the total bandwidth. 
         [0003]    Accordingly, systems and methods to support the distribution and employment of network situation awareness information for distributed scheduling of bandwidth in ad-hoc networks may find utility. 
       SUMMARY 
       [0004]    Embodiments of systems and methods in accordance with the present disclosure may provide a protocol for distributed bandwidth scheduling which may be implemented in the nodes of an ad-hoc network. 
         [0005]    In one embodiment, a computer-implemented method to schedule network traffic in a communications network comprises receiving at a first node of the network, situational awareness information from at least a second network node which is directly accessible by the first node, identifying, in the first node, situational awareness information commonly known by multiple nodes across the network, generating a network schedule based on said commonly known situational information and routing network traffic at the node using said network schedule. 
         [0006]    In another embodiment, a computer-based system to schedule network traffic in a communication network comprises a processor coupled to a first node of a network, a memory module coupled to the processor and comprising logic instructions stored on a tangible computer readable medium which, when execute by the processor, configure the processor to receive at the first node of the network, situational awareness information from at least a second network node which is directly accessible by the first node, identify, in the first node, situational awareness information commonly known by multiple nodes across the network, generate a network schedule based on said commonly known situational information, generate a shortest path/hops routing table from the first node to all other network nodes using the generated network schedule and route network traffic at the first node using said routing table. 
         [0007]    In a further embodiment, a computer program product comprising logic instructions stored on a tangible computer readable medium which, when execute by the processor, configure the processor to implement a method to schedule network traffic in a communication network by performing operations comprising receiving at a first node of the network, situational awareness information from at least a second network node which is directly accessible by the first node, identifying, in the first node, situational awareness information commonly known by multiple nodes across the network, generating a network schedule based on said commonly known situational information and routing network traffic at the node using said network schedule. 
         [0008]    Further areas of applicability will become apparent from the description provided herein. It should be understood that the description and specific examples are intended for purposes of illustration only and are not intended to limit the scope of the present disclosure. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]    Embodiments of methods and systems in accordance with the teachings of the present disclosure are described in detail below with reference to the following drawings. 
           [0010]      FIG. 1  is a schematic illustration of an ad-hoc network, according to embodiments. 
           [0011]      FIG. 2  is a schematic illustration of a mobile, wireless networking station, according to embodiments. 
           [0012]      FIG. 3  is a flowchart illustrating operations in methods for distributed bandwidth scheduling, according to embodiments. 
           [0013]      FIG. 4  is a schematic illustration of a method for distributed bandwidth scheduling, according to embodiments. 
           [0014]      FIG. 5  is a schematic illustration of a computer-based system to implement distributed bandwidth scheduling, according to embodiments. 
       
    
    
     DETAILED DESCRIPTION 
       [0015]    Systems, methods, and computer program products to provide a method to support distributed bandwidth scheduling in a wireless, ad-hoc network are described herein. Specific details of certain embodiments are set forth in the following description and in the Figures to provide a thorough understanding of such embodiments. One skilled in the art will understand, however, that alternate embodiments may be practiced without several of the details described in the following description. 
         [0016]    In some embodiments, each network node maintains a chronological set of network situation awareness snapshots/frames for a duration that exceeds the maximum information transit time across the network. The snapshots are stored at the end of each schedule end time. The first node reads its neighbors&#39; time tagged network situation awareness information and updates its appropriate network situation awareness frames with the new information. In conjunction with this embodiment the first node determines the maximum time or hops for information transit across the network and uses that time/hops to select the network situation awareness information frame to pass to the network bandwidth scheduler for determining the upcoming schedule frame. The selected network situation awareness frame passed to the distributed bandwidth scheduler is common to all network nodes since it will no longer receive any new updates. 
         [0017]      FIG. 1  is a schematic illustration of an ad-hoc network, according to embodiments. Referring to  FIG. 1 , the wireless network  100  comprises a plurality of nodes which can receive and/or transmit communication across the network. In the embodiment depicted in  FIG. 1  the nodes are mobile and may comprise one or more satellites  110 , one or more aircraft such as airplanes  112  and helicopters  114 , and one or more ground-based vehicles  116 . The various vehicles which comprise the nodes may be referred to generically herein by the term “mobile platform.” In the embodiment depicted in  FIG. 1  the various network nodes are mobile. Thus the number of nodes in the network and the network configuration may vary over time as the satellites, aircraft, and vehicles move relative to one another. Further, nodes may be added to the network  100  when a mobile platform moves into range to communicate with another mobile platform that is a part of the network  100 , or may be removed from the network  100  when a mobile platform moves out of range to communicate with another node in the network. In some embodiments the network may also comprise one or more fixed, ground based nodes. 
         [0018]    Direct communication is possible between certain pairs of nodes as indicated by the dashed lines between the nodes. Whether a pair of nodes can form a direct link may be determined by multiple factors such as the distance between the nodes, the power at which a node transmits, whether any obstacles exist between the nodes, etc. For example, the effects of the prevailing weather and altitudes of one or both the nodes may be taken into account as they may alter the distance over which a direct link may be maintained. 
         [0019]    The nodes form a mesh covering the ad hoc network  100 . Certain parts of the mesh may be well populated with nodes, while other parts of the mesh may be sparsely populated with nodes, forming holes in the mesh. 
         [0020]    A message may travel between any pair of nodes either directly or via other nodes where a direct link between the nodes is not available. Each node treats an outgoing message in the same way, irrespective of whether the message originates from that node or whether the message was received for forwarding. Hence, a message is likely to pass through a number of nodes, each of which will act in the same manner as they forward the message. Hence, effectively, each node forwarding the message becomes a transmit node for the next hop of the message&#39;s route. 
         [0021]    In the network depicted in  FIG. 1  each of the nodes may function as both a source node which originates communications and as a destination node which receives communications. Each node computes a routing table reflecting the communication paths through the ad hoc network  100  and may also determine which neighbor node to send a message for forwarding to a particular destination node. A source node may also maintain a limited number of links to neighbor nodes as active and leave a number of links to neighbor nodes as inactive based on the bandwidth as scheduled. Maintaining active links may include reconfiguring the links in response to changes in the relative position of the nodes in the network  100 . 
         [0022]    In some embodiments each node in the network  100  may comprise a wireless networking station which enables the node to send and receive messages across the network  100 . Referring now to  FIG. 2 , a block diagram of a wireless network station  200  in accordance with one or more embodiments will be discussed.  FIG. 2  illustrates an example block diagram of wireless network station  200  which may be included within a satellite  110 , an aircraft  112 ,  114 , or a land-based vehicle  116 , as depicted in  FIG. 1 .  FIG. 2  depicts the major elements of an example wireless network station  200 , however fewer or additional elements may be included in alternative embodiments in addition to various other elements that are not shown herein, and the scope of the claimed subject matter is not limited in these respects. 
         [0023]    Wireless network station  200  may comprise a baseband processor  210  coupled to memory  212  for performing the control functions of wireless network station  200 . Input/output (I/O) block  214  may comprise various circuits for coupling wireless network station  200  to one or more other devices. For example, I/O block  214  may include one or more Ethernet ports and/or one or more universal serial bus (USB) ports for coupling relay station  200  to modem  220  or other devices. For wireless communication, relay station  200  may further include a radio-frequency (RF) modulator/demodulator for modulating signals to be transmitted and/or for demodulating signals received via a wireless communication link. A digital-to-analog (D/A) converter  216  may convert digital signals from baseband processor  210  to analog signals for modulation and broadcasting by RF modulator/demodulator via analog and/or digital RF transmission techniques. Likewise, analog-to-digital (A/D) converter  218  may convert analog signals received and demodulated by RF modulator/demodulator  220  digital signals in a format capable of being handled by baseband processor  210 . Power amplifier (PA)  222  transmits outgoing signals via one or more antennas  228  and/or  230 , and low noise amplifier (LNA)  224  receives one or more incoming signals via antennas  228  and/or  230 , which may be coupled via duplexer  226  to control such bidirectional communication. In one or more embodiments, wireless network station  200  may implement single input, single output (SISO) type communication, and in one or more alternative embodiments wireless network station  200  may implement multiple input, multiple output (MIMO) communications, although the scope of the claimed subject matter is not limited in these respects. 
         [0024]    In some embodiments a wireless networking station  200  will implement communication protocols to facilitate distributed bandwidth scheduling in network  100 . In such embodiments a control module  213  may implement communication operations in accordance with the description provided herein. In some embodiments the control module  213  may be implemented as logic instructions stored in the computer readable medium of memory  212 . When executed by a processor, e.g., the baseband processor  210  or another processor in or coupled to wireless networking station, the control module  213  may implement one or more operations to manage information distribution for distributed bandwidth scheduling between network nodes. 
         [0025]      FIG. 3  is a flowchart illustrating operations in methods to implement distributed bandwidth scheduling, according to embodiments, and  FIG. 4  is a schematic illustration of a method for supporting distributed bandwidth scheduling, according to embodiments. Operations in a method to implement support of distributed bandwidth scheduling will be explained with reference to  FIGS. 3 and 4 . 
         [0026]    By way of overview, the method described herein efficiently distributes the information necessary for distributed network scheduling of bandwidth resources to support point-to-point, wireless communications between mobile terminals. The method uses scheduled communications between localized/neighbor terminals, for total network wide distributed schedule optimization to more efficiently allocate total network bandwidth resources by distributed schedulers on each terminal. In some embodiments the same scheduling algorithm is executed on each terminal and operates on the same global situation awareness information to provide a low latency technique. 
         [0027]    The method described herein distributes each node&#39;s latest network information only to its immediate one hop neighbors. Each node uses knowledge about the maximum end-to-end time for information to flow across the network to identify what information is common to all network terminals. The distributed network scheduling algorithm on each terminal uses network wide converged information common on every network terminal. Thus the outcome of the scheduler is the same on each of the terminals and total network bandwidth scheduling may be accomplished using a lowest possible latency method that requires no negotiations and without exchanging schedules between nodes. 
         [0028]    Referring to  FIGS. 3-4 , in some embodiments each terminal maintains network situation awareness (SA) information  410  in a bandwidth scheduler frame time structure, such as indicated by frame  0  through frame n in  FIG. 4 . By way of example, a bandwidth scheduler may produce one frame time (e.g., 0.1 seconds) of transmit and receive control commands for all active communication links in the network. This schedule may be executed at the start of each frame (operation  310 ). 
         [0029]    At operation  315  and  411  the network situation awareness information is sent by each network node to the one-hop neighbors in network  100 . In some embodiments each node sends its frame  0  situational awareness data, which contains the transmitting node&#39;s latest situational awareness information about the entire network. That information is time tagged by the originating node, not the node that is transmitting the situational awareness frame  0  information. The content of this frame of information is all of the information necessary for the bandwidth scheduler  412  to perform its task. By way of example, in some embodiments the situational awareness information may include but not limited to node state information, link status information, information traffic demands, link traffic demands, and maximum network hop information. The situational awareness information may be transmitted  411  on a priority basis in multiplexed transmission data units (TDUs). 
         [0030]    At operation  320  and  413  the node receives network situation awareness information transmitted by its one-hop neighbors. Thus, each node in the network receives the network situational awareness information from all its one-hop nodes. At operation  325  and  414  the node assigns the time tagged received information to the appropriate situational awareness frames. In some embodiments each terminal maintains its network situation awareness time tagged information over a number of frames that exceeds the maximum number of shortest path hops across the network (assuming 1 hop per frame time). 
         [0031]    At operation  330  and  415  the node determines the maximum number of network hops from each node&#39;s maximum hops across the network in the network situation awareness information. At operation  335  the node selects the situational awareness frame network state for scheduling. In some embodiments the node uses the network&#39;s maximum shortest path hops  416  and the frame time tag to select the appropriate latent network situation awareness frame  420  for calculating the network bandwidth optimal schedule. By way of example in some embodiments the frame is selected such that the Network Situation Awareness Frame Number is equal to the network maximum shortest path hops. By way of another example the accumulated transmit times in the current bandwidth schedule  417  with the current shortest path routing  418  is used to determine the maximum transit time  419  from this node across the network which is used by  415  to select the appropriate Network Situation Awareness Frame Number  416  to provide to the scheduler  420 . In this manner, each node uses knowledge about the maximum end-to-end time for information to flow across the network to identify what information is common to all network terminals. 
         [0032]    At operation  340  and  412  the node performs network bandwidth schedule planning for the next frame execution. In some embodiments the node calculates a network bandwidth schedule using network situation awareness frame selected in operation  335  and  416 . Since each terminal has converged global network information determined by network max hops or max transit time, the distributed schedulers know where all the terminals are with their demands, priorities, and link states. Projecting each node&#39;s location to its next scheduled link execution time is possible by maintaining tracks from the situation awareness history frames. Each terminal can schedule the entire network independently with the same result using the same topology and interference mitigation rules. Because the network information is global, interference mitigation may be performed on a network-wide basis. 
         [0033]    At operation  345  and  418  the schedule developed in operation  340  and  412  may be used to determine a shortest path routing from this node for the next frame execution. In some embodiments the schedule identifies the active links in the next frame such that the shortest path from the first node to all other nodes in the network may be calculated. This routing information may be used in the next executed frame to route forward traffic. 
         [0034]    Finally, at operation  350  and  419  shortest path routing from the first node may be used to determine the first node&#39;s maximum hops across the network. In some embodiments, the maximum hops (shortest path) from the first node across the network may be calculated and inserted into the network situation awareness frame  0 . Prior to completion of the current executing bandwidth schedule each network situation awareness frame is pushed down the stack, i.e., frame n−1 is set to frame n, and on up the stack, frame  0  is copied to frame  1 , and the frames will be updated with the upcoming active frame received neighbor data). 
         [0035]    Control then passes back to operation  310  and operations  310 - 350  are repeated for the current terminal as the current frame. Thus, operations  310 - 350  define a loop by which a network node may support distributed scheduling of bandwidth for transmissions across the network. In practice, each node on the network may include a bandwidth scheduler which implements the operations depicted in  FIG. 3 . Further, because each node executes the same algorithm using the same information set, each node will produce the same bandwidth allocation solution. 
         [0036]    In some embodiments the bandwidth selection operations depicted in  FIGS. 3-4  may be implemented by a computing system coupled to the respective network nodes.  FIG. 5  is a schematic illustration of a computing system. In one embodiment, system  500  comprises one or more input/output devices including a display  502  having a screen  504 , one or more speakers  506 , a keyboard  510 , one or more other I/O device(s)  512 , and a mouse  514 . The other I/O device(s)  512  may include a touch screen, a voice-activated input device, a track ball, and any other device that allows the system  500  to receive input from a user. 
         [0037]    The computing system  500  includes system hardware  520  and memory  530 , which may be implemented as random access memory and/or read-only memory. A file store  580  may be communicatively coupled to computing system  500 . File store  580  may be internal to computing device  108  such as, e.g., one or more hard drives, CD-ROM drives, DVD-ROM drives, or other types of storage devices. File store  580  may also be external to computer  530  such as, e.g., one or more external hard drives, network attached storage, or a separate storage network. 
         [0038]    System hardware  520  may include one or more processors  522 , a graphics processor(s)  524 , network interfaces  526 , and bus structure(s)  528 . As used herein, the term “processor” means any type of computational element, such as but not limited to, a microprocessor, a microcontroller, a complex instruction set computing (CISC) microprocessor, a reduced instruction set (RISC) microprocessor, a very long instruction word (VLIW) microprocessor, or any other type of processor or processing circuit. 
         [0039]    Graphics processor(s)  524  may function as adjunct processors that manage graphics and/or video operations. Graphics processor(s)  524  may be integrated onto the motherboard of computing system  500  or may be coupled via an expansion slot on the motherboard. 
         [0040]    In one embodiment, network interface  526  could be a wired interface such as an Ethernet interface (see, e.g., Institute of Electrical and Electronics Engineers/IEEE 802.3-2002) or a wireless interface such as an IEEE 802.11a, b or g-compliant interface (see, e.g., IEEE Standard for IT-Telecommunications and information exchange between systems LAN/MAN—Part II: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 4: Further Higher Data Rate Extension in the 2.4 GHz Band, 802.11G-2003). Another example of a wireless interface would be a general packet radio service (GPRS) interface (see, e.g., Guidelines on GPRS Handset Requirements, Global System for Mobile Communications/GSM Association, Ver. 3.0.1, December 2002). 
         [0041]    Bus structures  528  connect various components of system hardware  528 . In one embodiment, bus structures  528  may be one or more of several types of bus structure(s) including a memory bus, a peripheral bus or external bus, and/or a local bus using any variety of available bus architectures including, but not limited to, 11-bit bus, Industrial Standard Architecture (ISA), Micro-Channel Architecture (MSA), Extended ISA (EISA), Intelligent Drive Electronics (IDE), VESA Local Bus (VLB), Peripheral Component Interconnect (PCI), Universal Serial Bus (USB), Advanced Graphics Port (AGP), Personal Computer Memory Card International Association bus (PCMCIA), and Small Computer Systems Interface (SCSI). 
         [0042]    Memory  530  may include an operating system  540  for managing operations of computing device  500 . In one embodiment, operating system  540  includes a hardware interface module  554  that provides an interface to system hardware  520 . In addition, operating system  540  may include a file system  550  that manages files used in the operation of computing device  500  and a process control subsystem  552  that manages processes executing on computing system  500 . 
         [0043]    Operating system  540  may include (or manage) one or more communication interfaces that may operate in conjunction with system hardware  520  to transceive data packets and/or data streams from a remote source. Operating system  540  may further include a system call interface module  542  that provides an interface between the operating system  540  and one or more application modules resident in memory  530 . Operating system  540  may be embodied as a Windows® brand operating system or as a UNIX operating system or any derivative thereof (e.g., Linux, Solaris, etc.), or other operating systems including real time operating systems such as QNX. 
         [0044]    In one embodiment, memory  530  includes a bandwidth scheduling module  560  to schedule bandwidth in the network  100 , a situation awareness update and selection module  570 , and a shortest path routing module  575 . Bandwidth scheduling module  560  may include logic instructions encoded in a tangible computer-readable medium which, when executed by processor  522 , cause the processor  522  to perform the operations depicted in  FIG. 3  to schedule bandwidth on each node in the network  100 . Situation awareness operations module  570  may include logic instructions encoded in a tangible computer-readable medium which, when executed by processor  522 , cause the processor to perform the operations depicted in  FIG. 3  to maintain network situation awareness on each node in the network  100 . Shortest path routing module  575  may include logic instructions encoded in a tangible computer-readable medium which, when executed by processor  522 , cause the processor to perform a shortest path routing depicted in  FIG. 3  to transmit this node&#39;s latest network situation awareness out to its neighboring nodes in the network  100 . 
         [0045]    In the foregoing discussion, specific implementations of exemplary processes have been described, however, it should be understood that in alternate implementations, certain acts need not be performed in the order described above. In alternate embodiments, some acts may be modified, performed in a different order, or may be omitted entirely, depending on the circumstances. Moreover, in various alternate implementations, the acts described may be implemented by a computer, controller, processor, programmable device, firmware, or any other suitable device, and may be based on instructions stored on one or more computer-readable media or otherwise stored or programmed into such devices (e.g. including transmitting computer-readable instructions in real time to such devices). In the context of software, the acts described above may represent computer instructions that, when executed by one or more processors, perform the recited operations. In the event that computer-readable media are used, the computer-readable media can be any available media that can be accessed by a device to implement the instructions stored thereon. 
         [0046]    While various embodiments have been described, those skilled in the art will recognize modifications or variations which might be made without departing from the present disclosure. The examples illustrate the various embodiments and are not intended to limit the present disclosure. Therefore, the description and claims should be interpreted liberally with only such limitation as is necessary in view of the pertinent prior art.