Abstract:
Embodiments for providing for dissemination of packets in a network performing distributed beamforming are generally described herein. In some embodiments, distributing packets from nodes in a squad local area network using a first waveform to beamforming nodes, providing scheduling to a long link interface for delivering a stream of packets free of scheduling conflict and distributing a copy of the packets from a long link interface based on the provided scheduling and using a second waveform, the first waveform being different from the second waveform.

Description:
GOVERNMENT RIGHTS 
     This invention was made with Government support under Contract Number W911QX-12-C-0039. The Government has certain rights in this invention. Contract #. 
    
    
     BACKGROUND 
     Transmit beamforming relies on coherent transmission by spatially separated antennas forming constructive interference at the intended receiver. These spatially diverse antennas may be part of an array, multiple-input and multiple-output (MIMO) system or, separate wireless nodes. In the latter case, nodes during beamformed transmissions obtain the packet and a referenced time, common to all, to begin sending. 
     It is often assumed that nodes are within one-hop, or that a time division multiple access (TDMA)-based MAC schedules the beamformed transmission immediately after dissemination. Reliance on TDMA MAC with scheduling of long link transmission in same round as packet dissemination means scheduling is not used for State-of-the-art data dissemination and scheduling on the beamformed link relies on TDMA-based solutions in which a common schedule is established to deliver copies of the original single-sourced packet to beamforming nodes. Packets are sent on the beamformed link immediately after in-network dissemination, thus obviating the need for scheduling. Perfect communications and one-hop networks are generally assumed. Works that have considered multiple-hop networks use a clustering solution to reduce the problem to that of one-hop networks. 
     However, if more than one hop is involved, dissemination means nodes receive a copy of a packet at different times. The network cannot wait for nodes to receive one packet and then transmit on the uplink within the same round. Further, the uplink pipe is to be kept full. Packets are to be sent out on uplink at same time by nodes participating in distributed beamforming and dissemination failure is not a cause of conflict/interference. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates distributed beamforming according to an embodiment; 
         FIG. 2  illustrates a graph of a network of nodes wherein an uplink dissemination process is used according to an embodiment; 
         FIGS. 3 a - f    illustrates a downlink dissemination process according to an embodiment; and 
         FIG. 4  illustrates packet scheduling in a wireless network performing distributed beamforming according to an embodiment. 
     
    
    
     DETAILED DESCRIPTION 
     The following description and the drawings sufficiently illustrate specific embodiments to enable those skilled in the art to practice them. Other embodiments may incorporate structural, logical, electrical, process, and other changes. Portions and features of some embodiments may be included in, or substituted for, those of other embodiments. Embodiments set forth in the claims encompass available equivalents of those claims. 
     A beamforming interface is referred to as the “Long Link” because it may have a long range. Embodiments described herein include two packet dissemination processes and a packet scheduling technique intended to maximize the beamformed Long Link capacity for a Squad Local Area Network (SLAN) or the Squad network. The nodes disseminate copies of the original packet via Squad local area network (LAN). 
     The first dissemination process distributes copies of the same packet to beamforming nodes and the second dissemination process ensures nodes receive packets from the Long Link. The scheduling according to an embodiment delivers a stream of ordered and time synchronized packets to the Long Link module. The SLAN dissemination processes converge in less than 2 seconds and reach non-partitioned nodes. 
       FIG. 1  illustrates distributed beamforming  100  according to an embodiment. In  FIG. 1 , squad nodes  110  send the same signal/packet  112  from one source. At the intended destination  120 , constructive interference occurs resulting in mutual reinforcement to produce a wave  130  with an additive amplitude based on the amplitudes of the individual waves  112 . Everywhere else, destructive interference occurs resulting in cancellation of each of the individual waves thereby evading detection and interception. 
     Thus,  FIG. 1  shows that squad nodes  110  coherently send (beamform) the same packet to a faraway destination  120 . The beamforming interface is referred to as the Long Link interface  140  because it has a long range. In order to successfully beamform, the squad nodes  110  obtain the same copy of the packet before the squad nodes  110  attempt to transmit coherently. The squad nodes  110  disseminate copies of the original packet via Squad Local Area Network (SLAN) or the Squad network  114 . The Squad network interface and the Long Link interface are on different waveforms, i.e., different frequencies, different modulation schemes, etc. In effect, this means the SLAN and Long Link may be used at the same time because they will not interfere. Deconstructive interference is present at the adversary nodes  150 . 
       FIG. 2  illustrates a graph  200  of a network of nodes wherein an uplink dissemination process is used according to an embodiment. In  FIG. 2, 8  nodes  210 - 24  are shown in the SLAN network  230 . According to an embodiment, a dissemination process is iterative by nature. As one node, e.g., node  6   220 , completes the process and decides to become a forwarder or not, its neighbors, e.g., node  7   222  and node  8   224 , may run the process again to take those changes into account. This may change output of the process, which may modify the process output of a neighbor, and which may propagate changes to the output of other nodes. The process is considered to have converged when the output of the process remains the same for each iteration for the nodes. The time to convergence is the time between when the nodes start up and when the nodes reach their final output. 
     A source-independent MultiPoint Relay (MPR) process computes a Connected Dominated Set (CDS). The process starts with graph G  200 . A working graph, G′ is initiated where G′=G. The priority for nodes  210 - 224  is designated according to (degree, ID), wherein nodes with a higher degree have a higher priority so that ties are broken by ID. Nodes  210 - 224  start out by being relays to ensure full coverage at start-up. Each of the nodes  210 - 224  shares its 1-hop neighbor information with its neighbors. The process then prunes down nodes from G′. If a node&#39;s neighbors are neighbors, the node leaves the working graph G′. Nodes compute 2-hop cover set, wherein a node leaves the working graph G′ when neighbor is not used to cover 2-hop neighbors. Each node receives its neighbors&#39; algorithm output indicating whether it should be part of the CDS and accepts only the output of the highest-priority neighbor, that is, the highest priority nodes have the last word over their lower priority neighbors. Nodes  210 - 224  reach their eventual output within at most two seconds in some embodiments in which convergence time is a function of how often nodes exchange information. Thus, the SLAN network achieves high capacity and fair access on the Long Link. Referring to  FIG. 2 , priority is determined according to (degree, node ID), wherein (2, .)&gt;(1, .) and (2,3)&gt;(2,1). 
     In  FIG. 2 , Node  1   210  has a degree of 2, Node  2   212  has a degree of 3, Node  3   214  has a degree of 3, Node  4   216  has a degree of 1, Node  5   218  has a degree of 1, Node  6   220  has a degree of 2, Node  7   222  has a degree of 3 and Node  8   224  has a degree of 1. Node  6 ( 2 )  220  computes its 2-hop cover set and finds node  7 ( 3 )  222  is used to cover  3 ( 3 )  214  and  8 ( 1 )  224 . Only 2-hop information is available. Node  3 ( 3 )  214  determines instead that node  7 ( 3 )  222  is to cover  6 ( 2 )  220  and  8 ( 1 )  224 . Node  7 ( 3 )  222  listens to Node  3 ( 3 )  214  because it has a higher degree than Node  6 ( 2 )  220 . Thus, the Nodes in the computed CDS are 1(2)-2(3)-3(3)-7(3). 
       FIGS. 3 a - f    illustrates a downlink dissemination process  300  according to an embodiment. In  FIG. 3 a - f   , Nodes  0 - 6   310 - 322  are shown. Nodes know they are either download (DL)-connected (●) or DL-disconnected (x). The connected nodes closest to disconnected neighbors are favored for robustness. Nodes are selected with the smallest number of hops to a DL-connected node. Ties are broken with connectivity information (number of neighbors). Ties are further broken with active forwarding information. Ties are further broken by selecting node with lowest ID. Iteration is periodically performed to reach disconnected nodes more than 1 hop away and to handle mobility. 
     In  FIG. 3 a   , Node  1 , Node  3 , Node  5  and Node  6  are DL-disconnected. Node  0 , Node  2  and Node  4  are DL-connected. In  FIG. 3 b   , Node  6   322  only has disconnected neighbors. Thus, Node  6   322  is not selected. Node  3   316  has Node  4   318 , i.e., 4(3), and Node  2   314 , i.e., 2(2) as connected neighbors. Node  4   318 , 4(3), has a higher priority, i.e., 3&gt;2, and is thus selected as a forwarder. Node  3   316  becomes 1-hop connected. In  FIG. 3 c   , Node  5  has Node  4   318 , i.e., 4(3), as a connected neighbor. Thus, Node  4   318  is identified as a forwarder. Node  5   320  becomes 1-hop connected. 
     In  FIG. 3 d   , for Node  1   310 , the connected neighbors is made up of Node  4   318 , Node  2   314  and Node  0   310 , i.e., [●4(3), ●2(2), ●0(1)]. Since Node  4   318  has a higher priority, 3&gt;2&gt;1, Node  4   318  is selected as a forwarder. Node  1  becomes 1-hop connected. In  FIG. 3 e   , Node  6   322  has no DL-connected neighbors. Node  5 ,  320  is a 1-hop connected neighbor and is selected as a forwarder. Node  6   322  becomes a 2-hop connected node. Node  4   318  and Node  5   320  are traffic forwarders.  FIG. 3 f    illustrates the final results, wherein Node  4   318  and Node  5   320  are traffic forwarders. 
       FIG. 4  illustrates packet scheduling  400  in a wireless network performing distributed beamforming according to an embodiment. In  FIG. 4 , three nodes, N 1   410 , N 1   412 , N 1   414 , in a SLAN  402  are shown sending packets. The three nodes, N 1   410 , N 1   412 , N 1   414 , are also shown sending data on the Long Link  404 . The Long Link  404  is divided in epochs  420  and slots  430 . However, the epochs  420  and slots  430  do not necessarily reflect the actual time-division of the Long Link module. A packet is allocated to future epoch  420  to allow time for dissemination. A consistent time reference is used across beamforming nodes. The number of slots  430  is allocated proportional to nodes&#39; load. Mapping is devised using the source node ID and the packet ID, e.g., {Src Node Id; Pkt Id} to specific future epoch/slot. 
     Equation 1 illustrates a formula for performing the mapping: 
     
       
         
           
             
               
                 
                   
                     
                       ts 
                       i 
                     
                     = 
                     
                       
                         
                           ( 
                           
                             
                               [ 
                               
                                 
                                   
                                     t 
                                     now 
                                   
                                   + 
                                   hD 
                                 
                                 
                                   Δ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                               ] 
                             
                             + 
                             1 
                           
                           ) 
                         
                         × 
                         Δ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         N 
                       
                       + 
                       
                         
                           n 
                           i 
                         
                         ⁢ 
                         Δ 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     where 
               (       [         t   now     +   hD       Δ   ⁢           ⁢   N       ]     +   1     )     ×   Δ   ⁢           ⁢   N         
finds the epoch in the future (hD from now, where hD is the maximum dissemination delay), and n i Δ is the slot in that epoch with Δ being the slot time and N is the maximum nodes. Dynamic slot allocation and conflict resolution may also be implemented.
 
     The uplink interface provides uplink hand-off by de-queuing one epoch at a time and reordering packets for that epoch to account for dissemination vagaries and transfers to the Long Link module. The receive time reference periodically stores t now  as offset to a monotonically increasing counter and adjusts the time offset. 
     To illustrate scheduling, slot assignments [ 1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ] are considered. For the illustration, the slot time, A, is equal to 50, the maximum dissemination delay is 1000 and the maximum nodes is 7. Two nodes with ID  2  and  6  schedule a packet at time t now =5 according to equations 2 and 3: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           N 
                           2 
                         
                         : 
                         
                           ts 
                           2 
                         
                       
                       = 
                       
                         
                           
                             
                               ( 
                               
                                 
                                    
                                   
                                     
                                       5 
                                       + 
                                       1000 
                                     
                                     
                                       50 
                                       × 
                                       7 
                                     
                                   
                                    
                                 
                                 + 
                                 1 
                               
                               ) 
                             
                             × 
                             50 
                             × 
                             7 
                           
                           + 
                           
                             2 
                             × 
                             50 
                           
                         
                         = 
                         
                           
                             1050 
                             + 
                             
                               2 
                               × 
                               50 
                             
                           
                           = 
                           1150 
                         
                       
                     
                     ; 
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   and 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       N 
                       6 
                     
                     : 
                     
                       ts 
                       6 
                     
                   
                   = 
                   
                     
                       
                         
                           ( 
                           
                             
                                
                               
                                 
                                   5 
                                   + 
                                   1000 
                                 
                                 
                                   50 
                                   × 
                                   7 
                                 
                               
                                
                             
                             + 
                             1 
                           
                           ) 
                         
                         ⁢ 
                         50 
                         × 
                         7 
                       
                       + 
                       
                         2 
                         × 
                         50 
                       
                     
                     = 
                     
                       
                         1050 
                         + 
                         
                           6 
                           × 
                           50 
                         
                       
                       = 
                       1350. 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     Accordingly, uplink dissemination according to an embodiment provides efficient multi-hop dissemination of single-sourced packets throughout the squad. Downlink dissemination according to an embodiment provides robust dissemination of multiple-sourced packets in the squad network. Uplink scheduling according to an embodiment provides a slotted schedule for packet transmissions on long link in the future, sender reservation. A priority rule uses node degrees to break ties using node ID for more efficiency. A pruning process is used to better deal with initializing and partitioning. 
     The above detailed description includes references to the accompanying drawings, which form a part of the detailed description. The drawings show, by way of illustration, specific embodiments that may be practiced. These embodiments are also referred to herein as “examples.” Such examples may include elements in addition to those shown or described. However, also contemplated are examples that include the elements shown or described. Moreover, also contemplated are examples using any combination or permutation of those elements shown or described (or one or more aspects thereof), either with respect to a particular example (or one or more aspects thereof), or with respect to other examples (or one or more aspects thereof) shown or described herein. 
     Publications, patents, and patent documents referred to in this document are incorporated by reference herein in their entirety, as though individually incorporated by reference. In the event of inconsistent usages between this document and those documents so incorporated by reference, the usage in the incorporated reference(s) are supplementary to that of this document; for irreconcilable inconsistencies, the usage in this document controls. 
     In this document, the terms “a” or “an” are used, as is common in patent documents, to include one or more than one, independent of any other instances or usages of “at least one” or “one or more.” In this document, the term “or” is used to refer to a nonexclusive or, such that “A or B” includes “A but not B,” “B but not A,” and “A and B,” unless otherwise indicated. In the appended claims, the terms “including” and “in which” are used as the plain-English equivalents of the respective terms “comprising” and “wherein.” Also, in the following claims, the terms “including” and “comprising” are open-ended, that is, a system, device, article, or process that includes elements in addition to those listed after such a term in a claim are still deemed to fall within the scope of that claim. Moreover, in the following claims, the terms “first,” “second,” and “third,” etc. are used merely as labels, and are not intended to suggest a numerical order for their objects. 
     The above description is intended to be illustrative, and not restrictive. For example, the above-described examples (or one or more aspects thereof) may be used in combination with others. Other embodiments may be used, such as by one of ordinary skill in the art upon reviewing the above description. The Abstract is to allow the reader to quickly ascertain the nature of the technical disclosure, for example, to comply with 37 C.F.R. §1.72(b) in the United States of America. It is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. Also, in the above Detailed Description, various features may be grouped together to streamline the disclosure. However, the claims may not set forth features disclosed herein because embodiments may include a subset of said features. Further, embodiments may include fewer features than those disclosed in a particular example. Thus, the following claims are hereby incorporated into the Detailed Description, with a claim standing on its own as a separate embodiment. The scope of the embodiments disclosed herein is to be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled.