# Patent

## Title
Channel assessment scheme

## Abstract

A source node in a multihop network determines whether to transmit in a channel based on whether the channel is occupied by a packet transmission with a large number of relays; whether the source node is in the data tones back-off zone; and the source node is in the busy tone back-off zone.

## Background
CLAIM OF PRIORITY
This application claims the benefit under 35 USC 371 to International Application No. PCT/IB2013/003109, filed Nov. 8, 2013, which claims priority to U.S. Provisional Application No. 61/724,917, filed Nov. 10, 2012, each of which is incorporated by reference in its entirety.


TECHNICAL FIELD
The present invention relates to a multihop network such as a wireless sensor network, and a scheme for a node in the network to assess a channel.
BACKGROUND
Mobile multihop networks have been considered lately as viable alternatives for the delivery and sharing of multimedia content between users. Performance of such networks is typically measured in terms of conflicting objectives, namely: end-to-end latency, end-to-end energy consumption, and network throughput. Subsequently, this calls for a packet delivery protocols which are able to establish a careful balance between these objectives. Recently, a packet forwarding protocol has been developed to meet such objectives. See Bader, Ahmed et al., “An Efficient Multi-Carrier Position-Based Packet Forwarding Protocol for Wireless Sensory Network,” IEEE Transaction on Wireless Communications, Volume 11, no. 1 (January 2012), the content of which is incorporated by reference in its entirety.
For example, the protocol is built using orthogonal frequency division multiplexing (OFDM) for the physical (PHY) layer. Furthermore, the protocol utilizes position-based channel access techniques in conjunction with the OFDM PHY. This allows all eligible relays at a given hop to access the channel concurrently. Due to this property, the protocol is labelled as “multi-relay.” The protocol is indifferent to mobility since it does not mandate relays to have knowledge of the network topology. The use of OFDM makes it also quite resilient to fast fading environments and thus well-suited for mobility.
SUMMARY
One aspect of present invention provides a source node in a multihop network having a circuit that determines whether a channel is occupied by a packet transmission meeting predetermined criteria; wherein the source node determines whether to transmit in the channel based on the determination that the channel is occupied by a packet transmission meeting predetermined criteria; and wherein the criteria is based on a normalized auto-covariance of the power spectral density (PSD) of a total interference signal.
In another aspect of the present invention, the source node further determines whether it is in a data back-off zone by detecting data tones, and determines whether to transmit in the channel based on whether the node is in the data back-off zone. Typically, data tones correspond to subcarriers. Busy tone, however, may be of a single subcarrier dedicated to carrying the busy tone.
In another aspect of the present invention, the source node further determines whether it is in a busy tone back-off zone by detecting a busy tone, and determines whether to transmit in the channel based on whether the node is in the busy tone back-off zone.
In another aspect of the present invention, the source node transmits in the channel in a case that the channel is not occupied by a packet transmission meeting the predetermined criteria, the source node is not in the data tones back-off zone, and the source node is not in the busy tone back-off zone.
In another aspect of the present invention, the source node listens to the channel for an extended period and re-assess in a case that the channel is occupied by a packet transmission meeting the predetermined criteria, the source node is not in the data tones back-off zone, and the source node is in the busy tone back-off zone.
In another aspect of the present invention, the source node extracts a destination position from the busy tone, and transmits in the channel if an angle between the source node's destination and that of an ongoing transmission is >π/2, in a case the source node is in the data tones back-off zone, and the source node is in the busy tone back-off zone.
In another aspect of the present invention, the source node does not transmit in a channel in a case that the channel is not occupied by a packet transmission meeting the predetermined criteria, the source node is not in the data tones back-off zone, and the source node is in the busy tone back-off zone.
In another aspect of the present invention, the source node transmits in the channel in a case that the channel is occupied by a packet transmission meeting the predetermined criteria, the source node is in the data tones back-off zone, and the source node is not in the busy tone back-off zone.
In another aspect of the present invention, the source node does not transmit in the channel in a case that the channel is not occupied by a packet transmission meeting the predetermined criteria, the source node is in the data tones back-off zone, and the source node is in the busy tone back-off zone.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates a channel model of the total interference signal.
FIG. 2 shows the probability mass function for the number of relay at an arbitrary hop.
FIG. 3a illustrates sample realization of the interference-plus-noise auto-covariance of the power spectral density (PSD) in a multi-relay case.
FIG. 3b illustrates sample realization of the interference-plus-noise auto-covariance of the power spectral density (PSD) in a single-relay case
FIG. 4 illustrates the scheme for exposed nodes to capture more transmission opportunities.



DETAILED DESCRIPTION OF THE SYSTEM
A multihop network includes a plurality of communication devices. An example is a wireless communication device. In a wireless sensor network, each of the communication devices is also a sensor.
The communication device is referred to as a node. A node transmitting data is a source node. Nodes that transmit or retransmit the data are also called relays.
A source node may not able to estimate the number of relays in the nearby ongoing packet transmission for the following reasons:
1. Current known packet structure does not provide information for such estimation. The estimation of the number of relays requires an “improved packet structure” such as one described in 61/717,289, filed Oct. 23, 2012, incorporated by reference in its entirety.
2. To exploit the improved packet structure, a node should switch to coherent channel assessment mode, i.e. it should synchronize with the ongoing packet transmission. This is typically a less-efficient method of channel assessment.
3. The source node will be able to synchronize to the ongoing packet transmission only if it lies inside the coverage perimeter shown in FIG. 4 below. This is a case which does not occur very often.
4. Furthermore, one aspect of present invention is directed to cases where a source node lies inside one or both of the back-off zones but outside the coverage perimeter (discussed below).
Consequently, a source node utilizes a multi-stage channel assessment scheme:
1. The classical non-coherent energy detection method, whereby the node measures the energy on the data tones as well as the busy tone.
2. The source node performs the normalized auto-covariance computation described below to estimate whether it is in the vicinity of a packet transmission with a large number of relays. It will not be able to estimate how many relays there are, but just determine whether it is a large number or not, which is sufficient to make an educated decision. This is also a non-coherent method, which makes sense to use here, since the node may typically be outside the coverage perimeter of the ongoing transmission, i.e. it will not be able to synchronize with that transmission.
3. The third stage is reverted to only in certain scenarios as explained in the decision table below. In this stage, the source node extracts the position of the destination from the busy tone signal.
One aspect of present invention provides feature-based assessment of a channel. A node wishing to access the channel performs an analysis of the interference signal's features. Using such an approach, it gains valuable knowledge about its vicinity in comparison to the case where only traditional assessment techniques are used. The improved scheme increases the throughput performance and reduces of channel access delay. A direct consequence of this is the reduction of jitter, which is one of the major concerns within the context of multimedia content delivery.
A source node assesses a channel before accessing it. A channel model is illustrated in FIG. 1. See Bader, Ahmed et al., “An Efficient Multi-Carrier Position-Based Packet Forwarding Protocol for Wireless Sensory Network,” IEEE Transaction on Wireless Communications, Volume 11, no. 1 (January 2012), the content of which is incorporated by reference in its entirety. Very often, the observing node (the source node) will lie in the vicinity of a packet transmission featuring a large number of relays. Under such circumstances, the features of the resulting total interference signal are dominated by that transmission. In fact, it is quite likely to be in such a situation. The probability mass function (PMF) of the number of relays per transmission is plotted in FIG. 2 for various node densities. As illustrated in the figure, transmissions with large K are quite probable particularly at higher node densities. Under such circumstances, the total interference signal will show noticeable correlation across the frequency domain. Such a correlation is best captured by the observing node by computing the normalized auto-covariance of the power spectral density (PSD) of the total interference signal. This can be conveniently accomplished by exploiting the fact that nodes readily deploy Fast Fourier Transform (FFT) circuits which are required for the operation of the OFDM PHY. There are various algorithms in practice for the computation of the FFT. However, they are almost all based around the Discrete Fourier Transform (DFT) which is a well-known algorithm. The normalized auto-covariance is computed by the observing node as follows:




  
    
      
        
          
            X
            cov
          
          ⁡
          
            (
            c
            )
          
        
        =
        
          {
          
            
              
                
                  
                    
                      
                        
                          
                            1
                            
                              X
                              o
                            
                          
                          ⁢
                          
                            
                              ∑
                              
                                n
                                =
                                0
                              
                              
                                
                                  N
                                  s
                                
                                -
                                c
                                -
                                1
                              
                            
                            ⁢
                            
                              
                                (
                                
                                  
                                    
                                      P
                                      I
                                    
                                    ⁡
                                    
                                      (
                                      
                                        n
                                        +
                                        c
                                      
                                      )
                                    
                                  
                                  -
                                  
                                    
                                      P
                                      _
                                    
                                    I
                                  
                                
                                )
                              
                              ⁢
                              
                                (
                                
                                  
                                    
                                      P
                                      I
                                    
                                    ⁡
                                    
                                      (
                                      n
                                      )
                                    
                                  
                                  -
                                  
                                    
                                      P
                                      _
                                    
                                    I
                                  
                                
                                )
                              
                            
                          
                        
                        ,
                      
                      ⁢
                      
                        
                      
                    
                  
                  
                    
                      c
                      =
                      
                        
                          0
                          ⁢
                          
                            
                          
                          ⁢
                          ...
                          ⁢
                          
                            
                          
                          ⁢
                          
                            N
                            s
                          
                        
                        -
                        1
                      
                    
                  
                
                
                  
                    
                      
                        
                          X
                          Cov
                        
                        ⁡
                        
                          (
                          
                            -
                            c
                          
                          )
                        
                      
                      ,
                    
                  
                  
                    
                      c
                      =
                      
                        
                          -
                          
                            N
                            s
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        ...
                        ⁢
                        
                          
                        
                        ⁢
                        0
                      
                    
                  
                
              
              ⁢
              
                

              
              ⁢
              
                
              
              ⁢
              where
              ⁢
              
                
              
              ⁢
              
                
                  P
                  _
                
                I
              
            
            =
            
              
                
                  1
                  
                    N
                    a
                  
                
                ⁢
                
                  
                    ∑
                    
                      i
                      =
                      0
                    
                    
                      
                        N
                        s
                      
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      
                        P
                        I
                      
                      ⁡
                      
                        (
                        i
                        )
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    and
                    ⁢
                    
                      
                    
                    ⁢
                    
                      X
                      o
                    
                  
                
              
              =
              
                
                  ∑
                  
                    n
                    =
                    0
                  
                  
                    
                      N
                      s
                    
                    -
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      (
                      
                        
                          
                            P
                            I
                          
                          ⁡
                          
                            (
                            n
                            )
                          
                        
                        -
                        
                          
                            P
                            _
                          
                          I
                        
                      
                      )
                    
                    2
                  
                  .
                
              
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




In contrast, the interference PSD in the case of single-relay systems features very low correlation across the frequency domain. In fact, the more concurrent single-relay transmissions there are, the less correlation is observed. Sample realizations of the interference PSD for both cases are shown in FIGS. 3a and 3b. 
A simple yet effective characterization of the correlation featured by Xcov is the first zero-crossing. The larger the number of relays K is, the larger this zero-crossing is expected to be. The improved scheme developed in this invention further introduces an additional feature. The busy tone (BT) signal is conventionally a continuous analog signal. In our case, the BT signal is modulated with the position of the destination node.
The ability of the observing node to detect the presence of a “large-K” transmission and to know the destination of that transmission opens the door wide for more channel access opportunities. This is illustrated in FIG. 4. An exposed node utilizing classical channel assessment schemes will refrain from accessing the channel if it lies inside the back-off zone. The back-off zone is composed of two subzones, BODATA and BOBT, corresponding to the data tones back-off zone and busy tone back-off zone respectively. This is true even if the node lies outside the coverage perimeter of the nearby packet transmission. This is where feature detection lends itself to a more opportunistic channel access process.
In one aspect of present invention, a node determines whether it is in a back-off zone by means of an “energy detector.” For the data tones back-off zone, the energy detector measures the aggregate energy level on those tones, outputs the average and compares it to a preset threshold. If larger than the threshold, the node decides that it is inside the data tones back-off zone.
An exposed node utilizing the improved assessment scheme of this invention first measures the PSD at the output of the FFT block. It then computes the first zero-crossing, denoted by nfo, of Xcov. Denoting the decision threshold by nT, then if nfo>nT the node declares the channel as being one with a large number of relays.
The threshold nT setting depends on few factors such as the typical traffic load, node density, large-scale path loss coefficient, among other parameters. One way to set the threshold at a meaningful value is by means of simulations. One aspect of present invention provides that for typical network scenarios, setting nT=6 is a reasonable choice.
Accordingly, it knows that injecting a new packet into the network is unlikely to interfere with the ongoing nearby transmission. At the same time, it is likely to find a few potential receivers. Such a scenario is applicable to node A in FIG. 4. Here, w is the forwarding strip width. L is the number of receivers for that packet transmission. As such, the number of nodes energizing the busy tone is also L. The coverage perimeter is simply the perimeter of the geographical area where the packet transmission can be received correctly. Additional information may be found in the incorporated “An Efficient Multi-Carrier Position-Based Packet Forwarding Protocol for Wireless Sensory Network” article.
For node B however, the improved algorithm introduces an additional stage in the decision-making process. Node B might not be able to properly characterize the PSD of the interference signal, since it lies outside BODATA. Nevertheless, it will be able to extract the position of the transmission's destination. The angle between the observing node's destination and that of the ongoing transmission is denoted by ΔΘdist. The observing node decides to transmit if |ΔΘdst|>π/2.
The various decision-making cases for this improved channel assessment scheme are highlighted in Table I below:







TABLE I







DECISION TABLE FOR CHANNEL ACCESS












Case
in BODATA
in BOBT
Large K
Prior Art
Improved Scheme





1
n
n
n
transmit
transmit


2
n
n
y
transmit
keep listening to the







channel for a







period < Tp







then re-assess.


3
n
y
—
back off
extract destination







position from the







BT signal.







if Δθdst > π/2 then







transmit, otherwise







back off.


4
y
n
n
back off
back off


5
y
n
y
back off
transmit


6
y
y
n
back off
back off


7
y
y
y
back off
back off









Case 3 of Table I may occur in lightly-loaded networks. For the sake of extracting the position of the destination, the observing node needs to switch from simple energy detection to coherent channel assessment. The node needs to synchronize with the BT signal in that case.
For Case 2, the packet flow is very likely to be moving away from the observing node. For a higher degree of confidence, it may be possible to extend the channel sensing activity for a few more samples (extended period) and then re-assess.

## Claims

1. A source node in a multihop network, comprising:
a transmitter circuit that is configured to transmit a packet over a wireless channel; and
a sensor circuit that is configured to assess a correlation of a frequency spectrum of the wireless channel;
wherein the sensor circuit is configured to compute zero-crossings for an auto-covariance of a power spectral density of a total interference signal;
wherein the sensor circuit determines the wireless channel to be highly correlated when a spacing between the zero-crossings is larger than a predetermined threshold value;
wherein the sensor circuit determines whether the source node is in a data tones back-off zone by averaging aggregate energy levels on the data tones, and determines whether to transmit in the wireless channel based on whether the source node is in the data tones back-off zone;
wherein the sensor circuit determines whether the source node is in a busy tone back-off zone by at least detecting a busy tone, and further determines whether to transmit in the wireless channel based on whether the source node is in the busy tone back-off zone; and
wherein the sensor circuit extracts a destination position from the busy tone, and transmits in the wireless channel if an angle between the source node's destination and that of an ongoing transmission is >π/2, in a case the source node is not in the data tones back-off zone, and the source node is in the busy tone back-off zone.

2. The source node according to claim 1, wherein the busy tone is modulated with position information of a destination node.

3. The source node according to claim 1, wherein the power spectral density is measured at an output of a Fast Fourier Transform circuit.

4. The source node according to claim 1, wherein the predetermined threshold value is based on typical traffic load, node density, or large-scale path loss coefficient.

5. The source node according to claim 1, wherein the transmitter circuit is configured to transmit in the wireless channel in a case that the wireless channel is determined to not be highly correlated, the source node is not in the data tones back-off zone, and the source node is not in the busy tone back-off zone.

6. The source node according to claim 1, wherein the sensor circuit of the source node listens to the wireless channel for an extended period and is configured to re-assess in a case that the wireless channel is determined to be highly correlated, the source node is not in the data tones back-off zone, and the source node is not in the busy tone back-off zone.

7. The source node according to claim 1, wherein the transmitter circuit of the source node does not transmit in the wireless channel in a case that the wireless channel is determined to not be highly correlated, the source node is in the data tones back-off zone, and the source node is not in the busy tone back-off zone.

8. The source node according to claim 1, wherein the transmitter circuit of the source node transmits in the wireless channel in a case that the wireless channel is determined to be highly correlated, the source node is in the data tones back-off zone, and the source node is not in the busy tone back-off zone.

9. The source node according to claim 1, wherein the transmitter circuit of the source node does not transmit in the wireless channel in a case that the wireless channel is determined to not be highly correlated, the source node is in the data tones back-off zone, and the source node is in the busy tone back-off zone.

10. The source node according to claim 1, wherein the transmitter circuit of the source node does not transmit in the wireless channel in a case that the wireless channel is determined to be highly correlated, the source node is in the data tones back-off zone, and the source node is in the busy tone back-off zone.

11. The source node according to claim 1, wherein the sensor circuit of the source node further determines whether the source node is in a busy tone back-off zone by the detection of the busy tone and determining whether the wireless channel is highly correlated.

12. The source node according to claim 11, wherein the sensor circuit of the source node determines itself to be in the busy tone back-off zone when the busy tone is detected and the wireless channel is determined to not be highly correlated.

13. The source node according to claim 11, wherein the sensor circuit of the source node determines itself to not be in the busy tone back-off zone and the data tone back-off zone when the busy tone is not detected and the wireless channel is determined to not be highly correlated.

14. The source node according to claim 11, wherein the busy tone is modulated with position information of a destination node, wherein the source node is configured to determine its position with respect to a packet flow direction based at least in part on the position information of the destination node.

15. A method for operating a source node in a multihop network, comprising:
computing zero-crossings for an auto-covariance of a power spectral density of a total interference signal over a wireless channel of the multihop network;
determining the wireless channel to be highly correlated when a spacing between the zero-crossings is larger than a predetermined threshold value;
determining whether the source node is in a data tones back-off zone by detecting energy on the data tones;
determining whether the source node is in a busy tone back-off zone by detecting a busy tone;
extracting a destination position from the busy tone; and
selecting to transmit a signal from the source node over the wireless channel based at least in part on the following determinations:
whether the wireless channel is highly correlated,
whether the source node is in the data tones back-off zone,
whether the source node is in the busy tone back-off zone by detecting a busy tone, and
whether an angle between the source node's destination position and that of an ongoing transmission is >π/2, in a case that the source node is not in the data tones back-off zone, and the source node is in the busy tone back-off zone.

16. The method according to claim 15, wherein the busy tone is modulated with position information of a destination node.

17. The method according to claim 15, wherein the power spectral density is measured at an output of a Fast Fourier Transform circuit.

18. The method according to claim 15, further comprising transmitting in the wireless channel in a case that the wireless channel is determined to not be highly correlated, the source node is not in the data tones back-off zone, and the source node is not in the busy tone back-off zone.

19. The method according to claim 15, further comprising listening to the wireless channel for an extended period and re-assessing in a case that the wireless channel is determined to be highly correlated, the source node is not in the data tones back-off zone, and the source node is not in the busy tone back-off zone.

20. The method according to claim 15, further comprising not transmitting in the wireless channel in a case that the wireless channel is determined to not be highly correlated, the source node is in the data tones back-off zone, and the source node is not in the busy tone back-off zone.

21. The method according to claim 15, further comprising transmitting in the wireless channel in a case that the wireless channel is determined to be highly correlated, the source node is in the data tones back-off zone, and the source node is not in the busy tone back-off zone.

22. The method according to claim 15, further comprising not transmitting in the wireless channel in a case that the wireless channel is determined to not be highly correlated, the source node is in the data tones back-off zone, and the source node is in the busy tone back-off zone.

23. The method according to claim 15, further comprising not transmitting in the wireless channel in a case that the wireless channel is determined to be highly correlated, the source node is in the data tones back-off zone, and the source node is in the busy tone back-off zone.